CH3_ChannelCoding_4thyear_Part2

Lecture 3/3
If the first k bits of a codeword are the data bits, then the code is called a systematic code. In a systematic parity-check code, the first k bits are the data bits, and the last bits are the parity-check bits formed by linear combination of data bits
c1=d1
c2=d2
ck=dk
ck+1=p11d1? p12d2? . . . ? p1kdk (6.1)
ck+2=p21d1? p22d2? . . . ? p2kdk
ck+m=pm1d1? pm12d2? . . . ? pmkdk
where ? denotes modulo-2 addition. Equation (6.1) can be written in matrix form as [ ][ ]
and [ ] (6.3)
where Ik is the k-th order identity matrix and PT is the transpose of the coefficient matrix P given by [ ]
the matrix is called the generator matrix.
7. Parity Check Matrix
Let H denote an m×n matrix defined by
H = [P Im]=[ ] (7.1)
where . Then [ ]
and [ ][ ] [ ]
where [0] denotes the k×m zero matrix. Post multiplying both sides of Eqn.(6.2) by HT and then using Eq.(7.3), we obtain
c HT = d GHT=[0] (7.4)
The matrix H is called the parity-check matrix of the code, and Eq.(7.4) is called the parity-check equation.
8. Syndrome Decoding
Let r denote the 1×n received vector that results from sending the code vector c over a noisy channel. Then
? (8.1)
The vector e is called the error vector and is given by
Lecture 3/4
e = [e1 e2 . . . . en] (8.2)
where
?
?
?
?
1 if channel changes during the transmission
0 if channel does not change during the transmission.
i
i
i
c
c
e
Next we evaluate rHT and obtain
rHT=(c ? e)HT=0 ?e HT=e HT=s (8.3)
[ ] [ ] [
]
[ ] [ ] [ ] [ ]
the 1×m vector s is called the syndrome of r. thus, using s and noting that eHT is the ith row of HT
(or ith column of H) we can identify the error position by comparing s to the rows of HT. Note that
not all error patterns can be correctly decoded by syndrome decoding. The zero syndrome may
indicates that r is a code vector and is presumably correct.
Two points of note here;
1. If any row of HT consists of all 0?s, then an error in that position will have no effect on the
syndrome.
2. If any two rows of HT are the same then an error in one position has the same syndrome as an
error in the other.
Thus a linear binary code is capable of correcting all patterns of single errors if, and only if, all rows
of HT are distinct and non-zero.
Code having these characteristics is known as Hamming codes. The decoding procedure for single
errors consists of the following steps;
1. Compute the syndrome s = rHT.
2. if s = 0 then no error and r = c
3. if s ? 0 then:
a. if s = ith row of HT, then the ith digit of „r? is in error and c = r with the ith digit changed.
b. If s is not equal to any row of HT then two or more errors have occurred and the
procedure fails.
Example 8.1: A parity check code has the parity check matrix
[
]
a) Determine the generator matrix
b) Find the codeword that begins 101….
c) Suppose that the received word is 110110. Decode this received word.
Solution:
a) Since is a 3×6 matrix, n = 6, m= 3 and k=3. Then
[
]
and the generator matrix is