Question

A (7, 4) cyclic code is designed with a generator polynomial, g(D) = D3 + D + 1. a) (10 points) Determine the code word for the message, 1010. b) (10 points) Determine the code word for the message, 1100. c) (9+1= 10 points) Determine the error polynomial for the received word, 1110101. Is the received word correct?

Answer 1

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 q^k codewords.

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

x⁷ − 1 = (x − 1)(x³ + x + 1)(x³ + x² + 1).

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

x⁷ + 1 = (x + 1)(x³ + x + 1)(x³ + x² + 1).

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

(i) 1 = 1

(ii) x + 1 = x + 1

(iii) x³+ x + 1 = x³ + x + 1

(iv) x³ + x² + 1 = x³ + x² + 1

(v) (x + 1)(x³ + x + 1) = x⁴ + x³ + x² + 1

(vi) (x + 1)(x³ + x² + 1) = x⁴ + x² + x + 1

(vii) (x³ + x + 1)(x³ + x² + 1) = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1

(viii) (x + 1)(x³ + x + 1)(x³ + x² + 1) = x⁷ + 1

Here in (i) the polynomial 1 generates all F⁷2. 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 x⁷ + 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+x⁷ can be factorized as 1+x⁷=(1+x)(1+x+x³)(1+x²+x³), G(x) =1+x+x³, the minimum distance is 3 of single-error.

Dividing x³, x⁴, x⁵& x⁶ by g(x), we have

x³ =g(x) +1+x

x⁴ =xg(x)+x+x²

x⁵=(1+x²)g(x)+1+x+x²

x⁶=(1+x+x³)g(x)+1+x²

Rearranging the above, we have

V₀(x)=1+x+x³

V₁(x)=x+x²+x⁴

V₂(x)=1+x+x²+x⁵

V₃(x)=1+x²+x⁶

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

(A)

(B)

(C)