Hamming

Problem/Finish Description

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

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

• Hamming(7,4) Code
• Digital Class (typically freshman or sophomore year)
• Discrete Math Class (typically freshman or sophomore year)
• FPGA VHDL Lab Class (becoming a sophomore class ... mostly senior class)

Design

• 
  Digital Design Classes use graphical techniques to design circuits including hamming(7,4)
• 
  digital logic diagram for hamming(7,4) receive circuit that is taught in digital logic class
• 
  boolean code for hamming(7,4) code receive circuit that is taught in a discrete math class
• 
  Hamming(8,4) another hamming code that could be implemented with the hardware below
• 
  Hamming(11,7) corrects/detects more errors

• Video on how to use the graphical technique
• Hamming recevieve circuit animation
• Link to Logisim (open source .. free software)
• Link to the logisim circuit used for the screen shot and the video

Implement

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

• 
  Flow chart describing physical implementation of hamming(7,4) with 8 switches and 7 LEDs
• 
  User Constraints File (UCF file) used with Xilinx IDE showing how LogicWing is physically connected to the pins of the FPGA on the Papilio
• 
  VHSIC Hardware Description Language (VHDL) file colored with NotePad++ VHDL shell showing the hardware description language of this circuit

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;

• OpenSource hardware platform chosen papilio
• Switches and LEDs provided by the LogicStart MegaWing
• Drew the flow chart with Lucid Chart ... which is free with an email ending in *.edu .. name is Hamming Circuit Outline
• The UCF file was created from various sources
• It was implemented in one hardware entity .. one VHDL file
• Scanned engineering notebook pages written during this process
• The bit file (the code actually sent down USB cable to the Papilio) was created Xilinx ISE Design Suite
• The bit file is sent down the USB cable to the Papilio using the papilio loader
• The colored template or shell for displaying the VHDL code was found in OpenSource editor Notepad + +
• The graphics above were edited with the open source photo editor gimp.

Operate

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

• 
  Print out to introduce students to the graphical technique for understanding error correction
• 
  Operating a very simple haming7-4 circuit using VHDL on a papilio FPGA

Demo

• Printout this page on paper to hand to everyone in the audience
• Presentation
• Video

Next Steps

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?