CH3_ChannelCoding_4thyear_Part3

Lecture 3/5
[ ] [ ]
b) = [1 0 1][ ] [ ]
c) [ ]
[ ][ ] [ ]
Since s is equal to the second row of , an error is at the second bit, the correct codeword is 100110, and the data bits are 100
9. Hamming Distance
The Hamming distance d(ci,cj) between two code vectors ci and cj (having the same number of elements) is defined as the number of positions in which their elements differ.
The Hamming weight w(ci) of a code vector ci is defined as the number of 1?s in ci. Thus, the Hamming weight of ci is the Hamming distance between ci and 0, that is,
w(ci) = d(ci,0) (9.1)
where 0 is the zero code vector whose elements are all zeros. Similarly, the Hamming distance can be written in terms of Hamming weight as
d(ci,cj) = w(ci?cj) (9.2)
The minimum distance dmin of a linear block code is defined as the smallest Hamming distance between any pair of code vectors in the code. If the all zero word 0 is a codeword in the code space, we can redefine the minimum distance of a linear block code as the smallest Hamming weight of the nonzero code vector in the code.
10. Error Detection and Correction Capabilities
An (n,k) linear block code of minimum distance dmin can correct up to t errors if and only if
(10.1)
Equation (10.1) can be illustrated geometrically by Fig.10.1. In two Hamming spheres, each of radius t, are constructed around the points that represent code vectors ci and cj. Figure(10.1a) depict the case where two sphere are disjoint, that is, . For this case, if the code vector ci is transmitted, the received vector is r, and , then it is clear that the decoder will choose ci since it is the code vector closest to the received vector . On the other hand, Fig.(10.1b) depict the case where the two spheres intersect, that is, . In this case we see that if ci is transmitted, there exist a received vector such that , and yet is as close to as it is to . Thus the decoder may choose , which is incorrect.
Lecture 3/6
11. Hamming Bound
In order to find a relationship between n and k, we observe that 2n words are available for 2k data words, and are redundant words.
The number of ways in which up to t errors can occur is given by ?( ) . Thus for each codeword, we must leave ?( ) number of words unused. Because we have codewords, we must leave ?( ) words unused. Hence the total number of words must be at least ?( ) ?( )
But the total number of words available is 2n. Hence, ?( )
or ?( )
Observe that , thus ?( )
This known as the Hamming bound. A block code for which the equality hold for Eq.(11.1) is known as the perfect code. Single error-correcting perfect codes are called Hamming codes. For Hamming code, t=1 and dmin =3, and from Eq.(11.1) we have ?( )
and,
Example 11.1: for a (6,3) code, the generator matrix is [ ]
For all eight possible data words, find the corresponding codewords, and verify that this code is a single-error corresting code. If the receiver receives r =100011, determine the corresponding data word.
Solution: Table (11.1) shows the eight data words and the corresponding codewords found from
.
t
ci
r
cj
ci
cj
r
t
t
t
Fig.10.1
(a)
(b)
Ik
PT