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
The seven-bit encoded data is represented as;
The encoding process of the Hamming code can be
represented as modulo-2 multiplication;
where the 4 x 7 matrix is known as a generator matrix
represented by？，. G
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) ？，v？uG
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.
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
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
？，4 x 4 identity submatrix I4 x 3 parity submatrix？， P
Figure 1: Deconstruction of generator matrix ？， G
， 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
， 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
The code rate given as; ;；r
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
Thus the generator matrix for the (15, 11) Hamming code is given as follows;
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
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
As discussed the matrix can be decomposed into a 4 x ？，G
3 parity matrix and 4 x 4 identity matrix ？，？，PI
Let’s consider forming a new 3 x 7 matrix ？， H
Note that ？， becomes a matrix of dimension 3 x 4. P
Transpose is to turn the rows into column or columns into
The matrix is is thus ？，H
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
Suppose we post multiply the received codeword by the
transpose of ？，H
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.
Similar results are obtained for v；v and v；v 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
EEE332 – G: Hamming code Part 2 10/17 October 2008