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