DOC

# Hamming codes

By Anita Wallace,2014-06-20 12:01
10 views 0
Hamming codes

HAMMING CODES

Hamming code with matrix manipulation

Consider the four un-encoded information bits u,u,u123

and . This 1 x 4 matrix can be represented as; u4

？，？， uuuuu1234

The seven-bit encoded data is represented as;

？，？， vvvvvvvv1234567

The encoding process of the Hamming code can be

represented as modulo-2 multiplication;

1101000?

?0110100

?？，？，uuuuvvvvvvv 12341234567

1110010?

?1010001(

where the 4 x 7 matrix is known as a generator matrix

represented by？，. G

Note:

If we examine carefully this multiplication operation it is

consistent with Eq (1) above.

EEE332 G: Hamming code Part 2 1/17 October 2008

We can represent the encoding process by multiplying our information vector by a generator matrix to obtain ？，？，Gu

the encoded bit sequence？，. v

？，？， (2) ？，vuG

EXAMPLE 3

Encoding by matrix multiplication

A source outputs the four information bits 1100. These four bits are to be encoded using the Hamming code just described. Using the generator matrix in Eq (2), determine the encoded seven-bit pattern to be transmitted.

Solution

EEE332 G: Hamming code Part 2 2/17 October 2008

Let’s take a closer look on generator matrix for our ？，G

Hamming code. From the above

1101000?

?0110100

?？，G

1110010?

?1010001(

We can see that the generator matrix has the following properties;

1. The matrix is k rows by n columns: where k=4, the

number of information bits from the source; and n=7,

the total number of encoced bits.

2. The last four columns of ？， form an identity matrix. G

The identity matrix maps the four information bits into

the last four bits of the encoded sequence (seven-bit).

3. The first three columns of ？， shows the relationship G

between the parity (check) bits with data bits.

4. The generator matrix is not unique. For example, we

can develop an equally valid Hamming code by

？，switching the first and second columns in. G

EEE332 G: Hamming code Part 2 3/17 October 2008

Now let’s de-construct the generator matrix into two submatrices as i.e. a 4 x 4 identity submatrix and 4 x 3 ？，I

parity submatrix (which produce the parity bits). ？，P

?1101000

?

0110100?？，G ?1110010

?

1010001?(

？，？，？，？， GPI4x4

？，4 x 4 identity submatrix I4 x 3 parity submatrix？， P

Figure 1: Deconstruction of generator matrix ？， G

Terminology

Systematic code A code in which the information

bits are always repeated in a portion of the encoded

sequence (the input data are embedded in the

encoded output). A non-systematic code is the one in

which the output does not contain the input bits.

EEE332 G: Hamming code Part 2 4/17 October 2008

The systematic code is very much desirable because

they make it easy to extract the original data from the

encoded sequence.

Block code divides the bit stream from the source

encoder into k-bit blocks. Each k-bit blocks is then

encoded into an n-bit block prior to transmission.

The Hamming code that we’ve just developed is a block

code which takes data stream from source encoder, divides it into four-bit block, and then encodes each four-bit block into a seven-bit block prior to transmission.

Block codes are described in term of n and k, stated

as. The code we’ve developed is called a ;；;；n,k7,4

Hamming code.

The code rate given as; ;；r

k r

n

Sometimes the Hamming code above is also called “rate four-sevenths” code

EEE332 G: Hamming code Part 2 5/17 October 2008

Hamming code (15, 11)

Suppose we want to develop a Hamming code that provides single-error detection and correction capabilities for a larger block of data.

Suppose we want to use four parity bits (instead of three)

we can produce eleven (11) different combinations of those four bits with two or more “1”s. Therefore, we can

use four parity bits to provide single-error detection and correction capabilities for a block of 11 information bits. (Why 11 information data bits? check previous matrix

multiplication).

Thus the generator matrix for the (15, 11) Hamming code is given as follows;

110010000000000?

?101001000000000

?

100100100000000?

?011000010000000?

?010100001000000

?

？，G001100000100000?

?111000000010000

?

110100000001000?

?101100000000100

?

011100000000010?

?111100000000001(

EEE332 G: Hamming code Part 2 6/17 October 2008

This new (15, 11) code is not as powerful as our (7, 4) code for protecting information since we can only protect the information from only single-bit error in 11

information bits.

If we break the 11 bit information data into three four-bit blocks, and use the (7, 4) code in order to get better protection.

However, the new code provides less overhead i.e. only four parity bits required for 11 information data bits.

If we break up into three four-bit data will end up with 3 x 3 = 9 parity bits.

EEE332 G: Hamming code Part 2 7/17 October 2008

Decoding the Hamming code

Use the (7, 4) code for decoding, error detection and

correction

As discussed the matrix can be decomposed into a 4 x ？，G

3 parity matrix and 4 x 4 identity matrix ？，？，PI

？，？，？，？，GP;I44

Let’s consider forming a new 3 x 7 matrix ？， H

T

？，？，？，？，HI;P33

T

Note that ？， becomes a matrix of dimension 3 x 4. P

Transpose is to turn the rows into column or columns into

rows.

The matrix is is thus ？，H

1001011?

?？，H0101110

?

0010111?(

3x3 identity submatrix 3x4 transpose of parity matrix ？，I？，P

？，Figure 2: deconstruction of matrix H

EEE332 G: Hamming code Part 2 8/17 October 2008

Now let represents the received codeword ？，r

？，？，rvvvvvvv 1234567

Suppose we post multiply the received codeword by the

transpose of ？，H

100?

?010

?

001?

T?？，？，？，110rHvvvvvvv1234567?

?011

?

111?

?101(

？，vvvvvvvvvvvv 146724563567？，vvvvvv11ex22ex33ex

The resulting 1 x 3 matrix is called the syndrome, tells us which expected check bits agree with their received counterpart and which check bit do not.

vv0;ifvv 11ex11ex

vv1;ifv(v 11ex11ex

Similar results are obtained for vv and vv 22ex33ex

EEE332 G: Hamming code Part 2 9/17 October 2008

As we’ve already seen, this agreement or disagreement is exactly what we need for single-bit error detection and correction in the received seven-bit sequence.

Let’s use to represent the three-bit syndrome. Thus, ？，s

we can crate a table similar to the Table 2 (Note F).

Bit received in Error ？，s

None ？，000

？，100v1

？， 010v2

？， v0013

？， 110v4

？， v0115

？， v1116

？， v1017

EEE332 G: Hamming code Part 2 10/17 October 2008

Report this document

For any questions or suggestions please email
cust-service@docsford.com