01-12-2012, 03:38 PM
Error Correcting Codes 2. The Hamming Codes
hamming.pdf (Size: 188.34 KB / Downloads: 78)
Introduction
Imagine two individuals, call them the sender and the receiver.
The sender wishes to transmit a sequence of binary digits across
a medium called a channel to the receiver. If she sends a one, a
one will probably be received, and if she sends a zero, a zero will
probably be received. The channel, however, is not totally
reliable. Therefore, occasionally, a transmitted one will be
received as a zero, and a transmitted zero as a one. The sender is
unable to prevent the channel from making such errors. Can
something be done to reduce their effects?
Encoding in the Hamming Code
In a code where each codeword contains several message bits
and several check bits, each check bit must be some function of
the message bits. In the Hamming code each check bit is taken
to be a mod 2 sum of a subset of the message bits. Assume that
the rate of the code is 4/7, so that for every four information
symbols transmitted, there are three check symbols introduced
in the codeword. Call these the parity check symbols. It is
customary to index the bits from left to right beginning with 0.
Let c = (c0, c1, ... c6 ) denote the vector representing a seven bit
codeword, with the first four bits being information bits.
Syndrome Decoding
Given the received pattern r, the decoder must eventually decide
what the transmitted codeword was. If the decoder is able to find
the error pattern e, then the codeword is c = r + e. To estimate
e, it first forms the product HrT = HcT + HeT = HeT . This
product is called the syndrome, and reveals the pattern of parity
check failures on the received pattern.
The Minimum Distance of a Code
The last result in the table displayed indicates that since this
Hamming code can correct all single errors, the minimum
distance of the code must be at least three. Actually we can
deduce that there is a codeword of Hamming weight three from
the example given earlier, where flipping one bit in a codeword
could give the same syndrome as is obtained by flipping two
other bits in some other codeword. For if e1 and e2 are the
single and double error patterns respectively, that give the same
syndrome, then H e1
T = He2
T or H( e1+e2)T = 0. Thus e1+e2
is a codeword with exactly three 1’s i.e. it has Hamming weight
three, and is at distance three from the all zero codeword. The
parity check matrix of a code provides us a means of determining
a lower bound on the minimum distance of the code, without
either having to examine all pairs of codewords or looking at
syndromes.