# Homework 6

Due: Monday, April 30, 2001

Problem 1.  Let  V = ( g(x) )  be the binary cyclic code of length  7  with generator polynomial

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

• (a) Find the systematic basis  { xj + rj(x) }  of  V.
• (b) Use the above systematic basis of  V  to construct a systematic generator matrix  G  of  V .
• (c) Use the remainders  rj(x)  to construct a systematic parity check matrix  H  of  V .

Problem 2.  Let  a  be the primitive element of  GF(24)  which is the zero of the primitive polynomial

p(x) = x4 + x + 1 .

Let  g(x)  be the binary polynomial of smallest degree having

a  and  a5

as roots.  Let  V = ( g(x) )  be the cyclic code of smallest length having  g(x)  as a generator polynomial.  Use  a  and  a5  to construct a parity check matrix  H  of  V .  (Do not explicitly compute  g(x) .  )

Hint: Let  K  denote the matrix:

[ 1    a      a2      a3      a4        ...     a14          ]
K=       [                                                                         ]
[ 1 (a5)1 (a5)2 (a5)3 (a5)4 ... (a5)]14    ]

Then

f(x) = f0+f1x+f2x2+ ... f14x14   e   V

iff

(f0, f1, f2, ... , f14)KT = [ f(a), f(a5) ] = [ 0, 0 ]

Next  let  H'  denote the binary matrix formed by replacing each element of  GF(24)  in  K'  with the corresponding binary 4-tuple written as a column vector.  Then the row space of  H'  is  VPerp.  Unfortunately, the rows of  H'  may be linearly dependent.  Form the parity check matrix  H  by putting  H'  in row echelon canonical form and deleting the all zero rows.

Problem 3.  Let  x  be the primitive element of  GF(26)  which is the zero of the primitive polynomial:

p(x) = x6 + x + 1 .

Let  g(x)  be the polynomial of smallest degree having the following zeros:

x, x2, x3, x4, x5, x6, x7, x8

Let  V = ( g(x) ) be the corresponding cyclic code of shortest length.

• (a) Write  g(x)  as a product of minimal polynomials  mi(x), where  mi(x)  is the minimum polynomial of  xi.  (Do not explicitly compute the  mi(x)'s.)
• (b) Find the degree of  g(x).
• (c) Find the length  n  of  V.
• (d) What is the dimension  k  of  V?