CH3_ChannelCoding_4thyear_Part4

Lecture 3/7
Note that dmin=3, hence, from Eq.(10.1), t=1. Figure (11.1) shows a possible encoder for this code, using a three-digit shift register and three modulo-2 adders.
s = r HT =[1 0 0 0 1 1][ ] [ ]
this corresponds to the 3rd row of HT. Hence the 3rd bit in the received word is in error. The error pattern is e=[0 0 1 0 0 0].
The corrected word is c = r?e = [101011].
12 Cyclic Code
A binary code is said to be a cyclic code if it exhibits two fundamental properties:
1. Linearity property: The sum of any two codewords in the code is also a codeword.
2. Cyclic property: Any cyclic shift of a code word in the code is also a codeword.
it is convenient to associate with a codeword a polynomial of degree at most n ? 1, defined as
where { }. Now let ( )
Recognizing, for example, that in modulo-2, we manipulate the first i terms of Eqn.(12.2) as follows:
Define
Eqn.(12.3) is reformulated in the compact form
? ?
Table (11.1)
Data word d
Codeword c
111
111000
110
110110
101
101011
100
100101
011
011101
010
010011
001
001110
000
000000
Fig.11.1
Lecture 3/8
is the remainder that results from dividing by . The cyclic property state that: If is a code polynomial, then the polynomial is also a code polynomial for any cyclic shift i;
We can generate a cyclic code by using a generator polynomial of degree n ? k. The generator polynomial of an (n, k) cyclic code is a factor of and has the general form
Define a message polynomial
where { }.Clearly, the product is a polynomial of degree less than or equal to n ? 1, which may represent a codeword. We note that there are polynomials { }, and hence there are possible codewords that can be formed from a given
To show that the codewords in Eqn.(12.10) satisfy the cyclic property, let us consider the cyclic shift of (applying Eqn.(12.6) for =1)
Since divides both and (Eqn.(12.10)), it also divides ; i.e., can be represented as Therefore, a cyclic shift of any codeword generated by Eqn.(12.10) yields another codeword.
? From the above, we see that codewords possessing the cyclic property can be generated by multiplying the message polynomials with a unique polynomial , called the generator polynomial of the (n, k) cyclic code, which divides and has degree n ? k.
Example 12.1: Find a generator polynomial for a (7, 4) cyclic code, and find code vectors for all data (information) vectors d.
Solution: For the block length n = 7, the polynomial has the following factors:
we may take as a generator polynomial with [ ] one of the following two polynomials: and
The codewords in the (7, 4) code generated by using Eqn.(12.10) are given in Table 12.1.
For example if the information polynomial
Then
In binary form
??????????????????