# Homework 9

Due: Tuesday, December 2, 1997

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?

Problem 4.
• (a) Draw the linear sequential circuit (LSC) that multiplies by the polynomial
h(x) = 1 + x3 +x6
• (b) Draw the linear sequential circuit (LSC) that divides by the polynomial
g(x) = 1 + x2 + x4 + x6 + x7
• (c) Draw the linear sequential circuit (LSC) that simultaneously multiplies by h(x)  and divides by  g(x).

Problem 5.  Draw an LSC which takes as inputs polynomials  a(x)  and  b(x)  and then produces the output  h(x)a(x) + k(x)b(x), where  h(x)  and  k(x)  are the polynomials:

h(x) = 1 + x4 + x10       and       k(x) = x + x2 + x4 + x7 + x9