Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » A First Course in Electrical and Computer Engineering » Binary Codes: Hamming Codes for Channel Coding

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Click the "IEEE-SPS" link to see all content they endorse.

  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    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, […]"

    Click the "College Open Textbooks" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "A First Course in Electrical and Computer Engineering provides readers with a comprehensive, introductory look at the world of electrical engineering. It was originally written by Louis Scharf […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Evowl

    This collection is included inLens: Rice LMS's Lens
    By: Rice LMS

    Comments:

    "Language: en"

    Click the "Evowl" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Binary Codes: Hamming Codes for Channel Coding

Module by: Louis Scharf. E-mail the author

Note:

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:

0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0 . 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0 .
(1)

Multiplication in modulo-2 arithmetic is simply 0·0=0·1=1·0=00·0=0·1=1·0=0 and 1 ·1=1·1=1. Then we can say that the error sequence 00100000 is “added” to the transmission 01101001 to produce the erroneous reception:

01101001 transmitted 00100000 error 01001001 received. 01101001 transmitted 00100000 error 01001001 received.
(2)

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 NN bits of information that we wish to transmit and that we wish to intersperse “check bits” that will enable us to detect and correct any single bit error in the transmission. If we use NN information bits and n n check bits, then we will transmit a code word containing N+nN+n bits. The n n check bits can code 2 n 2 n events, and we want these events to indicate whether or not any errors occurred and, if so, where they occurred. Therefore we require

where (N+n)(N+n) is the number of single error events that can occur and +1 is the number of no-error events. For example, when N=4N=4, we require n=3n=3 so that 23(4+3)+123(4+3)+1.

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 (N,n)(N,n) Hamming code consisting of N N information bits and n n check bits (or parity bits). We denote the information bits by x1,x2,...,xNx1,x2,...,xN and the check bits by c1,c2,...,cnc1,c2,...,cn. These bits may be interspersed. When N=4N=4 and n=3n=3, then a typical array of bits within a code word would be one of the following:

c 1 c 2 x 1 c 3 x 2 x 3 x 4 or x 1 x 2 x 3 x 4 c 1 c 2 c 3 . c 1 c 2 x 1 c 3 x 2 x 3 x 4 or x 1 x 2 x 3 x 4 c 1 c 2 c 3 .
(3)

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 (N,n)(N,n) code, then the received code word will be the modulo-2 sum of the code word and the error word that contains a 1 in its ithith position:

c1c2xlc3x2x3x4000l000.c1c2xlc3x2x3x4000l000.
(4)

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

A T = 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) . A T = 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) .
(5)

The ithith column of A T A T is just the binary code for i i. When A T A T premultiplies an error word, the error bit picks out the column that codes the error position:

Figure 1
Figure 1 (pic015mi.png)

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 A T A T applied to the modulo-2 sum of a code word x x and an error word e e is

AT(xe)=ATxATe.AT(xe)=ATxATe.
(6)

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

Exercise 1

Let y=xey=xe denote the modulo-2 sum of a code word x x and an error word e;ATe;AT is a parity check matrix. Show that

A T y = A T x A T e . A T y = A T x A T e .
(7)

We have designed the parity check matrix A T A T so that the syndromeATeATe produces a binary code for the error location. (The location of the error is th'eth'e syndrome for the error word.) The product ATxATx will interfere with this syndrome unless A T x = 0 . A T x=0. Therefore we will require that the code word x x satisfy the constraint

ATx=0.ATx=0.
(8)

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

Natural Codes. When the information bits and the check bits are coded in their natural order (c1c2x1c3x2x3x4)(c1c2x1c3x2x3x4), then we may determine the check bits by writing ATxATx as follows:

1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 c 1 c 2 x 1 c 3 x 2 x 3 x 4 = 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 c 1 c 2 x 1 c 3 x 2 x 3 x 4 = 0 0 0
(9)

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

c 1 x 1 x 2 x 4 = 0 c 2 x 1 x 3 x 4 = 0 c 3 x 2 x 3 x 4 = 0 . c 1 x 1 x 2 x 4 = 0 c 2 x 1 x 3 x 4 = 0 c 3 x 2 x 3 x 4 = 0 .
(10)

Therefore the check bits c1,c2c1,c2, and c 3 c 3 are simply the following modulo-2 sums

c 1 = x 1 x 2 x 4 c 2 = x 1 x 3 x 4 c 3 = x 2 x 3 x 4 . c 1 = x 1 x 2 x 4 c 2 = x 1 x 3 x 4 c 3 = x 2 x 3 x 4 .
(11)

This finding may be organized into the matrix equation

c1c2xlc3x2x3x4= 1101 1011 1000 0111 0100 0010 0001 x1x2x3x4.c1c2xlc3x2x3x4= 1101 1011 1000 0111 0100 0010 0001 x1x2x3x4.
(12)

This equation shows how the code word x x is built from the information bits (x1,x2,x3,x4)(x1,x2,x3,x4). We call the matrix that defines the construction a coder matrix and write it as H H:

x = H Θ x T = ( c 1 c 2 x 1 c 3 x 2 x 3 x 4 ) Θ T = ( x 1 x 2 x 3 x 4 ) x = H Θ x T = ( c 1 c 2 x 1 c 3 x 2 x 3 x 4 ) Θ T = ( x 1 x 2 x 3 x 4 )
(13)
H = 1101 1011 1000 0111 0100 0010 0001 H= 1101 1011 1000 0111 0100 0010 0001
(14)

This summarizes the construction of a Hamming code x x.

Exercise 2

Check to see that the product of the parity check matrix A T A T and the coder matrix H H is ATH=0ATH=0. Interpret this result.

Exercise 3

Fill in the following table to show what the Hamming (4,3)(4,3) code is:

x 1 x 2 x 3 x 4 c 1 c 2 x 1 c 3 x 2 x 3 x 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 x 1 x 2 x 3 x 4 c 1 c 2 x 1 c 3 x 2 x 3 x 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
(15)

Exercise 4

Design a Hamming (11,n)(11,n) code for coding eleven information bits against single errors. Show your equations for c1,c2,...,cnc1,c2,...,cn and write out the coder matrix H H for x=HΘ.x=HΘ.

Decoding. To decode a Hamming code, we form the syndrome ATyATy for the received (and possibly erroneous) code word y=xey=xe. Because ATx=0ATx=0, the syndrome is

s=ATe.s=ATe.
(16)

Convert this binary number into its corresponding integer location and change the bit of y y in that location. If the location is zero, do nothing. Now strip off the information bits. This is the decoding algorithm.

Exercise 5

Use the table of Hamming (4,3)(4,3) codes from Exercise 3 to construct a table of received codes that contain either no bit errors or exactly one bit error. Apply the decoding algorithm to construct (x1,x2,x3,x4)(x1,x2,x3,x4) and show that all received code words with one or fewer errors are correctly decoded.

Digital Hardware. The tables you have constructed in Exercise 3 and 5 for coding and decoding Hamming (4,3)(4,3) codes may be stored in digital logic chips. Their functionality is illustrated in Figure 1. The coder chip accepts (x1x2x3x4)(x1x2x3x4) as its address and generates a coded word. The decoder chip accepts (c1c2x1c3x2x3x4)(c1c2x1c3x2x3x4) as its address and generates a decoded word. In your courses on digital logic you will study circuits for implementing coders and decoders.

Figure 2: Digital Logic for Hamming Code
On the left of this image are four horizontally oriented lines. They are labeled from top to bottom x_1, x_2, x_3, x_4. These line end on the left side of a rectangle labeled Coder. From the right side of the rectangle extend seven horizontally oriented lines labeled from top to bottom: c_1, c_2, x_1, c_3, x_2, x_3, x_4. To the right of these lines in another set of seven horizontally oriented lines labeled exactly the same extending to the right and ending on the left side of a rectanlge labeled Decoder. From the right side extend four horizontally oriented lines labeled from top to bottom x_1, x_2, x_3, x_4.

Exercise 6

Discuss the possibility of detecting a received (4,3)(4,3) code word that is neither a valid code word nor a code word with a single error. How would you use such a detector?

Exercise 7

What fraction of received seven-bit words can be correctly decoded as Hamming (4,3)(4,3) codes?

Systematic Codes. Systematic Hamming codes are codes whose information bits lead and whose check bits trail. The format for a (4,3)(4,3) code is then (x1x2x3x4c1c2c3)(x1x2x3x4c1c2c3). The construction of a (4,3)(4,3) code word from the information bits may be written as

x 1 x 2 x 3 x 4 c 1 c 2 c 3 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 c 1 c 2 c 3 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 x 1 x 2 x 3 x 4
(17)

The coder matrix takes the form

H = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 = I _____ C . H= 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 = I _____ C .
(18)

The problem is to find the matrix C that defines the construction of check bits. The constraint ATx=0ATx=0 produces the constraint ATH=0ATH=0 so that ATHΘ=0ATHΘ=0. The constraints ATH=0ATH=0 may be written out as

1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 = 0 0 0 0 0 0 0 0 0 0 0 0 . 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 = 0 0 0 0 0 0 0 0 0 0 0 0 .
(19)

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

Exercise 8

Solve Equation 19 for the cijcij. Show that the coder matrix for a systematic Hamming (4,3)(4,3) code is

H = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 . H= 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 .
(20)

Exercise 9

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

Exercise 10

(MATLAB) Write a MATLAB program that builds Hamming (4,3)(4,3) codes from information bits (x1x2x3x4)(x1x2x3x4) and decodes Hamming (4,3)(4,3) codes (c1c2x1c3x2x3x4)(c1c2x1c3x2x3x4) to obtain information bits (x1x2x3x4)(x1x2x3x4). Synthesize all seven-bit binary codes and show that your decoder correctly decodes correct codes and one-bit error codes.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks