Problem/Finish Description

edit

Introduction to Hamming Code for Error Detection and Correction

In the world of digital information, accuracy and reliability are paramount. Whether it's transmitting data across wireless networks or storing critical information on hard drives, errors can creep in and compromise the integrity of the data. This is where error detection and correction techniques play a crucial role. One such pioneering method is the Hamming Code, a mathematical construct that has revolutionized error detection and correction in various domains, including communication systems and data storage devices.

The Hamming Code, named after its inventor Richard Hamming, presents an elegant solution to the age-old problem of identifying and rectifying errors that can occur during data transfer. This article delves into the intricacies of the Hamming Code, exploring its fundamental principles, applications in error detection and correction, and a practical demonstration of its implementation on both hard drives and communication systems, whether wired or wireless.

Conceive

edit

Introduce Electrical/Computer Engineering by simulating circuit board on bottom of hard drive:

Design

edit

Implement

edit

Used 8 slide switches and 7 LED's to implement this demonstration of hard disk drive corrective circuitry.

The VHDL (VHSIC (Very High Speed Integrated Circuit) Hardware Description Language) Code
----------------------------------------------------------------------------------
-- Engineer: Scott Foerster
-- 
-- Create Date:    11:36:24 02/25/2014 
-- Design Name: 	 Hamming Code Demo
-- Module Name:    Main - Behavioural 

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity Main is
    Port ( SWITCH : in  STD_LOGIC_VECTOR (7 downto 0);
           LED : out  STD_LOGIC_VECTOR (6 downto 0));
end Main;

architecture Behavioral of Main is
	signal S : STD_LOGIC_VECTOR(3 downto 1) := (others => '0'); -- Sent parity
	signal R : STD_LOGIC_VECTOR(3 downto 1) := (others => '0'); -- Received parity
	signal C : STD_LOGIC_VECTOR(3 downto 1) := (others => '0'); -- sent Compared to received parity
	signal cb : STD_LOGIC_VECTOR(3 downto 0) := (others => '0'); -- Corrected Bits (is 1 if bit needs correction)
begin

-- original parity computation (switches 0 - 3 contain 4 bits being sent)
   S(1) <= SWITCH(0) XOR SWITCH(1) XOR SWITCH(3);
	S(2) <= SWITCH(0) XOR SWITCH(2) XOR SWITCH(3);
	S(3) <= SWITCH(1) XOR SWITCH(2) XOR SWITCH(3);
-- received parity computation (switches 4-7 contain 4 bits being received .. so can introduce error)
   R(1) <= SWITCH(4) XOR SWITCH(5) XOR SWITCH(7);
	R(2) <= SWITCH(4) XOR SWITCH(6) XOR SWITCH(7);
	R(3) <= SWITCH(5) XOR SWITCH(6) XOR SWITCH(7);
-- connecting the received parity to LED's so can see the parity circles going bad
   LED(4) <= C(1);
	LED(5) <= C(2);
	LED(6) <= C(3);
-- Comparing sent versus received parity
   C(1) <= NOT(S(1) XOR R(1));
   C(2) <= NOT(S(2) XOR R(2));
   C(3) <= NOT(S(3) XOR R(3));
-- computing the Corrected Bits (is 1 if bit needs correction)
	cb(0) <= NOT(C(1)) AND NOT(C(2)) AND C(3);
	cb(1) <= NOT(C(1)) AND C(2) AND NOT(C(3));
	cb(2) <= C(1) AND NOT(C(2)) AND NOT(C(3));	
	cb(3) <= NOT(C(1)) AND NOT(C(2)) AND NOT(C(3));
	
-- fixing the 4 bits being received ... should match the original four bits
-- and connecting the bottom 4 LEDs
   LED(0) <= cb(0) XOR SWITCH(4);
	LED(1) <= cb(1) XOR SWITCH(5);
	LED(2) <= cb(2) XOR SWITCH(6);
	LED(3) <= cb(3) XOR SWITCH(7);
end Behavioral;

Operate

edit

This is the intended sequence:

  1. Practice the graphical technique on paper
  2. Operate the physical circuit
  3. Study how the receive/corrective circuit operates in the design above
  4. Figure out all the software pieces to generate the bit file
  5. Take a digital design class and a lab and become an electrical/computer engineer

Demo

edit

Next Steps

edit

The algorithm for correcting many bits is well known. Demonstrating this at a larger scale is going to require some imagination.

  • How do we corrupt bits on demand, accurately, in a way that can be checked?
  • What hardware is going to display this?