CMSC 442 Fall 2003
Homework 9

---

• Reading assignment: Peterson & Weldon, "Error-Correcting Codes," MIT Press, (Second Edition), (1986), Chapter 8.

---

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

p(x) = x⁴ + x + 1 .

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

a  and a⁵

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

Hint: Let K  denote the matrix:

[ 1 a a² a³ a⁴        ...     a¹⁴          ]
    K=       [                                                                         ]
[ 1 (a⁵)¹ (a⁵)² (a⁵)³ (a⁵)⁴ ... (a⁵)]¹⁴    ]

Then

f(x) = f₀+f₁x+f₂x²+ ... f₁₄x¹⁴ e   V

iff

(f₀, f₁, f₂, ... , f₁₄)K^T = [ f(a), f(a⁵) ] = [ 0, 0 ]

Next  let H'  denote the binary matrix formed by replacing each element of  GF(2⁴)  in  K'  with the corresponding binary 4-tuple written as a column vector.  Then the row space of H'  is  V^Perp.  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 2. Let x  be the primitive element of  GF(2⁶)  which is the zero of the primitive polynomial:

p(x) = x⁶ + x + 1 .

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

x, x², x³, x⁴, x⁵, x⁶, x⁷, x⁸

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

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

Note: If you have not installed the symbolic fonts on your web browser, then the above ksi's will look like x's.

---