× Close
Join the Ques10 Community
Ques10 is a community of thousands of students, teachers, and academic experts, just like you.
Join them; it only takes a minute
Sign up
Question: For (7,4) cyclic code,find out the generator matrix if G(D)=1+D+D3
0

Mumbai University >Information Technology> Sem 4 > Information Theory & Coding

Marks: 10 Marks

Year: May 2016

ADD COMMENTlink
modified 12 months ago  • written 13 months ago by gravatar for Veena Nandi Veena Nandi120
0

The generator matrix will be a kn matrix with rank k. Since the choice of the basic vectors is not unique, the generator matrix is not unique for a given linear code. The generator matrix converts the vector of length k to a vector of length n. Let the input vector be represented by i. The coded symbol will be given by

C = iG

Where c is called the codeword and I is called the information word.

The generator matrix provides a concise and efficient way of representing a linear block code. The n× k matrix can generate qk codewords.

For length 7 binary cyclic codes we have the factorization into irreducible polynomials:

x7 − 1 = (x − 1)(x3 + x + 1)(x3 + x2 + 1).

Since we are looking at binary codes, all the minus signs can be replaced by plus signs:

x7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).

As there are 3 irreducible factors, there are 23 = 8 cyclic codes.The 8 generator polynomials are:

(i) 1 = 1

(ii) x + 1 = x + 1

(iii) x3+ x + 1 = x3 + x + 1

(iv) x3 + x2 + 1 = x3 + x2 + 1

(v) (x + 1)(x3 + x + 1) = x4 + x3 + x2 + 1

(vi) (x + 1)(x3 + x2 + 1) = x4 + x2 + x + 1

(vii) (x3 + x + 1)(x3 + x2 + 1) = x6 + x5 + x4 + x3 + x2 + x + 1

(viii) (x + 1)(x3 + x + 1)(x3 + x2 + 1) = x7 + 1

Here in (i) the polynomial 1 generates all F72. In (ii) we find the parity check code and in (vii) the repetition code. As mentioned before, in (viii) we view the 0-code as being generated by x7 + 1.

The polynomials of (iii) and (iv) have degree 3 and so generate [7, 4] codes, which we shall later see are Hamming codes. The [7,3] codes of (v) and (vi) are the duals of the Hamming codes.

For (7, 4) cyclic code, the polynomial 1+x7 can be factorized as 1+x7=(1+x)(1+x+x3)(1+x2+x3), G(x) =1+x+x3, the minimum distance is 3 of single-error.

Dividing x3, x4, x5& x6 by g(x), we have

x3 =g(x) +1+x

x4 =xg(x)+x+x2

x5=(1+x2)g(x)+1+x+x2

x6=(1+x+x3)g(x)+1+x2

Rearranging the above, we have

V0(x)=1+x+x3

V1(x)=x+x2+x4

V2(x)=1+x+x2+x5

V3(x)=1+x2+x6

Considering above equation in matrix form, we obtain the generator matrix of order of (4*7) in systematic form in cyclic code.

1 1 0 1 0 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 0
0 0 0 1 1 0 1
ADD COMMENTlink
modified 12 months ago  • written 13 months ago by gravatar for Veena Nandi Veena Nandi120
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.