Definitions

hamming, richard

Hamming(7,4)

Hamming(7,4) is a Hamming code that encodes 4 bits of data into 7 bits by adding 3 parity bits.

Today, Hamming code really refers to a specific (7,4) code Richard W. Hamming introduced in 1950. The code stemmed from his work as a theorist at Bell Telephone laboratories in the 1940s. Hamming invented the code in 1950 to provide a error-correcting code to reduce value computer resources / time being wasted.

Hamming Code adds three additional check bits to every four data bits of the message. Hamming's (7,4) algorithm can correct any single-bit error, or detect all single-bit and two-bit errors. This means that for transmission medium situations where burst errors do not occur, Hamming's (7,4) code is effective (as the medium would have to be extremely noisy for 2 out of 7 bits to be flipped). In other words, the Hamming distance between the transmitted and received words must be no greater than one to be correctable.

Goal

The goal of Hamming codes is to create a set of parity bits that overlap such that a single-bit error (the bit is logically flipped in value) in a data bit or a parity bit can be detected and corrected. While multiple overlaps can be created, the general method is presented in Hamming codes.

Bit # 1 2 3 4 5 6 7
Transmitted bit p_1 p_2 d_1 p_3 d_2 d_3 d_4
p_1
p_2
p_3

This table describes which parity bits cover which transmitted bits in the encoded word. For example, p_2 covers bits 2, 3, 6, & 7. It also details which transmitted by which parity bit by reading the column. For example, d_1 is covered by p_1 and p_2 but not p_3. This table will have a striking resemblance to the parity-check matrix (mathbf{H}) in the next section.

Furthermore, if the parity columns in the above table were removed

d_1 d_2 d_3 d_4
p_1
p_2
p_3
then resemblance to rows 1, 2, & 4 of the code generator matrix (mathbf{G}) below will also be evident.

So, by picking the parity bit coverage correctly, all errors of Hamming distance of 1 can be detected and corrected, which is the point of using a Hamming code.

Hamming matrices

Hamming codes can be computed in linear algebra terms through matrices because Hamming codes are linear codes. For the purposes of Hamming codes, two Hamming matrices can be defined: the code generator matrix mathbf{G} and the parity-check matrix mathbf{H}:
mathbf{G} := begin{pmatrix}
1 & 1 & 0 & 1 
1 & 0 & 1 & 1 
1 & 0 & 0 & 0 
0 & 1 & 1 & 1 
0 & 1 & 0 & 0 
0 & 0 & 1 & 0 
0 & 0 & 0 & 1 
end{pmatrix}

and

mathbf{H} := begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 0 & 1 
0 & 1 & 1 & 0 & 0 & 1 & 1 
0 & 0 & 0 & 1 & 1 & 1 & 1 
end{pmatrix}.

As mentioned above, rows 1, 2, & 4 of mathbf{G} should look familiar as they map the data bits to their parity bits:

  • p_1 covers d_1, d_2, d_4
  • p_2 covers d_1, d_3, d_4
  • p_3 covers d_2, d_3, d_4

The remaining rows (3, 5, 6, 7) map the data to their position in encoded form and there is only 1 in that row so it is an identical copy. In fact, these four rows are linearly independent and form the identity matrix (by design, not coincidence).

Also as mentioned above, the three rows of mathbf{H} should be familiar. These rows are used to compute the syndrome vector at the receiving end and if the syndrome vector is the null vector (all zeros) then the received word is error-free; if non-zero then the value indicates which bit has been flipped.

The 4 data bits — assembled as a vector mathbf{p} — is pre-multiplied by mathbf{G} (i.e., mathbf{Gp}) and taken modulo 2 to yield the encoded value that is transmitted. The original 4 data bits are converted to 7 bits (hence the name "Hamming(7,4)") with 3 parity bits added to ensure even parity using the above data bit coverages. The first table above shows the mapping between each data and parity bit into its final bit position (1 through 7) but this can also be presented in a Venn diagram. The first diagram in this article shows three circles (one for each parity bit) and encloses data bits that each parity bit covers. The second diagram (shown to the right) is identical but, instead, the bit positions are marked.

For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example:

mathbf{p} = begin{pmatrix} d_1 d_2 d_3 d_4 end{pmatrix} = begin{pmatrix} 1 0 1 1 end{pmatrix}

Channel coding

Suppose we want to transmit this data over a noisy communications channel. Specifically, a binary symmetric channel meaning that error corruption does not favor either zero or one (it is symmetric in causing errors). Furthermore, all source vectors are assumed to be equiprobable. We take the product of G and p, with entries modulo 2, to determine the transmitted codeword x:

mathbf{x} = mathbf{G} mathbf{p} =
begin{pmatrix}
1 & 1 & 0 & 1 
1 & 0 & 1 & 1 
1 & 0 & 0 & 0 
0 & 1 & 1 & 1 
0 & 1 & 0 & 0 
0 & 0 & 1 & 0 
0 & 0 & 0 & 1 
end{pmatrix} begin{pmatrix} 1 0 1 1 end{pmatrix} = begin{pmatrix} 2 3 1 2 0 1 1 end{pmatrix} = begin{pmatrix} 0 1 1 0 0 1 1 end{pmatrix}

This means that 0110011 would be transmitted instead of transmitting 1011.

In the diagram to the right, the 7 bits of the encoded word are inserted into their respective locations; from inspection it is clear that the parity of the red, green, and blue circles are even:

  • red circle has 2 1's
  • green circle has 2 1's
  • blue circle has 4 1's

What will be shown shortly is that if, during transmission, a bit is flipped then the parity of 2 or all 3 circles will be incorrect and the errored bit can be determined (even if one of the parity bits) by knowing that the parity of all three of these circles should be even.

Parity check

If no error occurs during transmission, then the received codeword r is identical to the transmitted codeword x:

mathbf{r} = mathbf{x}

The receiver multiplies H and r to obtain the syndrome vector mathbf{z}, which indicates whether an error has occurred, and if so, for which codeword bit. Performing this multiplication (again, entries modulo 2):

mathbf{z} = mathbf{H}mathbf{r} =
begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 0 & 1 
0 & 1 & 1 & 0 & 0 & 1 & 1 
0 & 0 & 0 & 1 & 1 & 1 & 1 
end{pmatrix} begin{pmatrix} 0 1 1 0 0 1 1 end{pmatrix} = begin{pmatrix} 2 4 2 end{pmatrix} = begin{pmatrix} 0 0 0 end{pmatrix}

Since the syndrome z is the null vector, the receiver can conclude that no error has occurred. This conclusion is based on the observation that when the data vector is multiplied by mathbf{G}, a change of basis occurs into a vector subspace that is the kernel of mathbf{H}. As long as nothing happens during transmission, mathbf{r} will remain in the kernel of mathbf{H} and the multiplication will yield the null vector.

Error correction

Otherwise, suppose a single bit error has occurred. Mathematically, we can write

mathbf{r} = mathbf{x} +mathbf{e}_i

modulo 2, where e_i is the i_{th} unit vector, that is, a zero vector with a 1 in the i^{th}, counting from 1.

e_2 = begin{pmatrix} 0 1 0 0 0 0 0 end{pmatrix}

Thus the above expression signifies a single bit error in the i^{th} place.

Now, if we multiply this vector by H:

mathbf{Hr} = mathbf{H} left(mathbf{x}+mathbf{e}_i right) = mathbf{Hx} + mathbf{He}_i

Since x is the transmitted data, it is without error, and as a result, the product of H and x is zero. Thus

mathbf{Hx} + mathbf{He}_i = mathbf{0} + mathbf{He}_i = mathbf{He}_i

Now, the product of H with the i^{th} standard basis vector picks out that column of H, we know the error occurs in the place where this column of H occurs.

For example, suppose we have introduced a bit error on bit #5

mathbf{r} =
left(mathbf{x}+mathbf{e}_5 right) = left(begin{pmatrix} 0 1 1 0 0 1 1 end{pmatrix} + begin{pmatrix} 0 0 0 0 1 0 0 end{pmatrix} right) = begin{pmatrix} 0 1 1 0 1 1 1 end{pmatrix} = begin{pmatrix} 0 1 1 0 1 1 1 end{pmatrix}

The diagram to the right shows the bit error (shown in blue text) and the bad parity created (shown in red text) in the red and green circles. The bit error can be detected by computing the parity of the red, green, and blue circles. If a bad parity is detected then the data bit that overlaps only the bad parity circles is the bit with the error. In the above example, the red & green circles have bad parity so the bit corresponding to the intersection of red & green but not blue indicates the errored bit.

Now,

mathbf{z} = mathbf{Hr} = begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 0 & 1 
0 & 1 & 1 & 0 & 0 & 1 & 1 
0 & 0 & 0 & 1 & 1 & 1 & 1 
end{pmatrix} begin{pmatrix} 0 1 1 0 1 1 1 end{pmatrix} = begin{pmatrix} 3 4 3 end{pmatrix} = begin{pmatrix} 1 0 1 end{pmatrix} which corresponds to the fifth column of mathbf{H}. Furthermore, since the general algorithm used (see Hamming code#General algorithm) was intention in its construction then the syndrome of 101 corresponds to the binary value of 5, which also indicates the fifth bit was corrupted. Thus, an error has been detected in bit 5, and can be corrected (simply flip or negate its value):
mathbf{r}_{corrected} = begin{pmatrix} 0 1 1 0 overline{1} 1 1 end{pmatrix} = begin{pmatrix} 0 1 1 0 0 1 1 end{pmatrix} This corrected received value indeed, now, matches the transmitted value mathbf{x} from above.

Decoding

Once the received vector has been determined to be error-free or corrected if an error occurred (assuming only zero or one bit errors are possible) then the received data needs to be decoded back into the original 4 bits.

First, define a matrix mathbf{R}:

mathbf{R} = begin{pmatrix}
0 & 0 & 1 & 0 & 0 & 0 & 0 
0 & 0 & 0 & 0 & 1 & 0 & 0 
0 & 0 & 0 & 0 & 0 & 1 & 0 
0 & 0 & 0 & 0 & 0 & 0 & 1 
end{pmatrix}

Then the received value, p_r is

mathbf{p_r} = mathbf{R} mathbf{r}

and using the running example from above

mathbf{p_r} =
begin{pmatrix}
0 & 0 & 1 & 0 & 0 & 0 & 0 
0 & 0 & 0 & 0 & 1 & 0 & 0 
0 & 0 & 0 & 0 & 0 & 1 & 0 
0 & 0 & 0 & 0 & 0 & 0 & 1 
end{pmatrix} begin{pmatrix}
0  1  1  0  0  1  1
end{pmatrix} = begin{pmatrix}
1  0  1  1
end{pmatrix}

Multiple bit errors

It is not difficult to show that only single bit errors can be corrected using this scheme. Alternatively, Hamming codes can be used to detect single and double bit errors, by merely noting that the product of H is nonzero whenever errors have occurred. In the diagram to the right, bits 4 & 5 were flipped. This yields only one circle (green) with an invalid parity but the errors are not recoverable.

However, the Hamming (7,4) and similar Hamming codes cannot distinguish between single-bit errors and two-bit errors.


All codes

Since the source is only 4 bits then there are only 16 possible transmitted words. Included is the 8-bit value if an extra parity bit is used (see Hamming code#Hamming codes with additional parity). (The data bits are shown in blue; the parity bits are shown in red; and the extra parity bit shown in green.)
Data
({color{blue}d_1}, {color{blue}d_2}, {color{blue}d_3}, {color{blue}d_4})
Hamming(7,4) Hamming(7,4) with extra parity bit (Hamming(8,4))
Transmitted
({color{red}p_1}, {color{red}p_2}, {color{blue}d_1}, {color{red}p_3}, {color{blue}d_2}, {color{blue}d_3}, {color{blue}d_4})
Diagram Transmitted
({color{red}p_1}, {color{red}p_2}, {color{blue}d_1}, {color{red}p_3}, {color{blue}d_2}, {color{blue}d_3}, {color{blue}d_4}, {color{green}p_4})
Diagram
0000 0000000 00000000
1000 1110000 11100001
0100 1001100 10011001
1100 0111100 01111000
0010 0101010 01010101
1010 1011010 10110100
0110 1100110 11001100
1110 0010110 00101101
0001 1101001 11010010
1001 0011001 00110011
0101 0100101 01001011
1101 1010101 10101010
0011 1000011 10000111
1011 0110011 01100110
0111 0001111 00011110
1111 1111111 11111111

References

Search another word or see hamming, richardon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature