Inside Collection: A First Course in Electrical and Computer Engineering

This module is part of the collection, *A First Course in Electrical and Computer Engineering*. The LaTeX source files for this collection were created using an optical character recognition technology, and because of this process there may be more errors than usual. Please contact us if you discover any errors.

The idea behind Hamming codes is to intersperse, or append, extra binary digits to a binary code so that errors in transmission of the code over a channel may be detected and corrected. For example, suppose we transmit the code 01101001, and it is received as 01001001. In this transmission, the third most significant bit is received erroneously. Let's define the following “modulo-2 addition” of binary numbers:

Multiplication in modulo-2 arithmetic is simply *error sequence* 00100000 is “added” to the *transmission* 01101001 to produce the erroneous reception:

Hamming error correcting codes will permit us to receive the erroneous transmission and to detect and correct the error. This is obviously of great value in transmitting and storing information. (Imagine how upset you would be to have the binary code for your checking account confused with that of Mrs. Joan Kroc.)

**Choosing the Number of Check Bits.** Let's suppose we have

where

How many check bits do you require to code seven bits of information for single error correction?

**Code Construction.** Let's suppose we have constructed an

The first ordering is “natural” (as we will see), and the second is “systematic” (a term that is used to describe any code whose head is information and whose tail is check). If a single error occurs in an

We would like to operate on this received code word in such a way that the location of the error bit can be determined. If there were no code word, then an obvious solution would be to premultiply the error word by the *parity check* matrix

The

If the error word contains no error bits, then the product is 0, indicating no errors.

This seems like a good idea, but what about the effect of the code word? In Exercise 1, you are asked to show that the effect of the parity check matrix

In this equation all sums and products obey the rules of modulo-2 arithmetic.

Let

We have designed the parity check matrix *syndrome*

This constraint actually *defines* the Hamming code. Let's illustrate this point
by applying the constraint to a code word in its “natural format”

**Natural Codes.** When the information bits and the check bits are
coded in their natural order

We use the rules of modulo-2 arithmetic to write these constraints as

Therefore the check bits

This finding may be organized into the matrix equation

This equation shows how the code word *coder matrix*
and write it as

This summarizes the construction of a Hamming code

Check to see that the product of the parity check matrix

Fill in the following table to show what the Hamming

Design a Hamming

**Decoding.** To decode a Hamming code, we form the syndrome

Convert this binary number into its corresponding integer location and change the bit of

Use the table of Hamming *received* codes that contain either no bit errors or exactly one bit error. Apply the decoding algorithm to construct

**Digital Hardware.** The tables you have constructed in Exercise 3 and 5 for coding and decoding Hamming

Discuss the possibility of detecting a received

What fraction of received seven-bit words can be correctly decoded as Hamming

**Systematic Codes.** Systematic Hamming codes are codes whose information bits lead and whose check bits trail. The format for a

The coder matrix takes the form

The problem is to find the matrix *C* that defines the construction of check bits. The constraint

These constraints produce all the equations we need (twelve equations in
twelve unknowns) to determine the

Solve Equation 19 for the

Show that the coder matrix of Exercise 7 is a permutation of the coder matrix in Equation 14. (That is, the rows are reordered.)

(MATLAB) Write a MATLAB program that builds Hamming

- « Previous module in collection Binary Codes: Huffman Codes for Source Coding
- Collection home: A First Course in Electrical and Computer Engineering
- Next module in collection » Binary Codes: Numerical Experiment (Huffman Codes)

Comments:"Reviewer's Comments: 'I recommend this book as a "required primary textbook." This text attempts to lower the barriers for students that take courses such as Principles of Electrical Engineering, […]"