× 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 7 months ago  • written 8 months ago by gravatar for Veena Nandi Veena Nandi90
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 7 months ago  • written 8 months ago by gravatar for Veena Nandi Veena Nandi90
Please log in to add an answer.


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