Mathematics 392 – Seminar in Coding Theory Final Problem Set April 26, 2002

Ground Rules

The problems below form the final problem set announced in the course syllabus. This is an open book, open notes, open Swords 335 assignment. You must work independently on these problems, and you may not consult with other faculty members or students. You may consult other sources in the library, on the Internet, etc. but if you find something relevant there, please footnote it. When you have finished your solutions, please write out a short statement that you have abided by these ground rules, sign it, and return it with your solutions.

This assignment is due no later than 5:00pm on Saturday, May 4.

I. (20) In class, we stated that if F_{1} and F_{2} are finite fields of the same size 2^{r}, then F_{1} and F_{2} are isomorphic – that is, there exists a one-to-one, onto mapping ϕ : F_{1} → F_{2} such that

(1)  \begin{aligned}ϕ(a + b) & = ϕ(a) + ϕ(b), and \\ ϕ(a · b) & = ϕ(a) · ϕ(b) \end{aligned}

for all a, b ∈ F_{1}. (Such a mapping is, in particular, a group homomorphism for the additive groups, so ϕ(0) = 0 will always be true.) In this problem, you will exhibit such a mapping ϕ explicitly if F_{1} is the field of size 8 constructed using the irreducible polynomial h_{1}(x) = x^{3} +x+1 and F_{2} is the field of size 8 constructed using the irreducible polynomial h_{2}(y) = y^{3} + y^{2} + 1.

A) (5) Call the primitive element x mod h_{1}(x) = α in F_{1}. Show that if ϕ satisfies (1), then ϕ(α) must be a root of x^{3} + x + 1 = 0 in F_{2}. What choices does this give for ϕ(α)? To standardize notation, write β = y mod h_{2}(y) for the primitive element in F_{2}, and write the nonzero elements of F_{2} as powers of β.

B) (5) If ϕ satisfies the second equation in (1), show that the choice of ϕ(α) determines

ϕ(α^{j}) for all j. C) (10) Find a choice of ϕ(α) so that both parts of (1) hold for all a, b ∈ F_{1}.

II. Let C be a binary linear code of block length n and dimension k. The weight enumerator of C is the polynomial W_{C}(t) = ∑_{i=0}^{n} A_{i}t^{i} where A_{i} = |{c ∈ C : wt(c) = i}|. (W_{C}(t) is the generating function of the weight sequence A_{i}, and is important for more refined study of decoding error probabilities.)

A) (10) Show that the weight enumerator of the binary cyclic code C with n = 7 and g(x) = x^{3} + x + 1 is W_{C}(t) = 1 + 7t^{3} + 7t^{4} + t^{7}.

B) (10) Recall that the dual code C^{⊥} of C is

C^{⊥} = {y ∈ F_{2}^{n} : x · y = 0 mod 2 for all x ∈ C}.

It is a famous theorem of MacWilliams that the weight enumerators of C and C^{⊥} are related by the MacWilliams identity:

2^{k}W_{C^{⊥}}(t) = (1 + t)^{n}W_{C} (\frac{1 − t}{1 + t}) .

Use the MacWilliams identity to find the weight enumerator of the dual of the code from part A.

C) (10) Show that the dual code of the code from part A is also a cyclic code and find its generator polynomial.

III. In this problem you will justify our alternate construction of the Reed-Solomon code RS(2^{r}, δ) (k = 2^{r} − δ), via the evaluation mapping. Let β be a primitive element of F_{2^{r}}, and define

\begin{matrix}ev : Span\{1, t, …, t^{k−1}\} & → F_{2^{r}}^{2^{r}−1} \\ p(t) & ↦ (p(1), p(β), …, p(β^{2^{r}−2})) \end{matrix}

A) (5) Show that the image of ev is a cyclic code of length n = 2^{r} − 1. (Recall that

question B from Discussion 4 gives a criterion for when a code is cyclic.) B) (5) What happens if you multiply 1 + x + x^{2} + ⋯ + x^{2^{r}−2} times x + 1 (mod 2)? What

are the roots of 1 + x + x^{2} + ⋯ + x^{2^{r}−2} = 0 in F_{2^{r}}? C) (10) The codeword polynomial corresponding to ev(t^{j}) is 1 + β^{j}x + (β^{j}x)^{2} + ⋯ +

(β^{j}x)^{2^{r}−2}. What are the roots of this polynomial in F_{2^{r}}? D) (10) Using part C, deduce that the common roots of the codeword polynomials corre-

sponding to ev(1), ev(t), …, ev(t^{k−1}) are β, β^{2}, …, β^{2^{r}−2−k+1}, and explain why this shows that the image of the evaluation map equals the Reed-Solomon code RS(2^{r}, δ). (Hint: What is the generator polynomial of this code?)

IV. Let β be a primitive element for F_{2^{r}}. In the derivation of the Key Equation for decoding of Reed-Solomon codes, we introduced the set of error locations, L, the error values e_{i}, the error locator polynomial: σ(x) = ∏_{i∈L}(1 − β^{i}x) whose roots are β^{−i} for i ∈ L, and the error evaluator polynomial: ω(x) = ∑_{i∈L} e_{i}β^{i} ∏_{j∈L,j≠i}(1 − β^{j}x). In this problem, you will prove two important steps in the connection between the Key Equation and decoding.

A) (10) (Lemma 1 from class on 4/19) Show that σ(x) and ω(x) have gcd equal to 1 in F_{2^{r}}[x]. (Hint: σ(x) is given in factored form so we know what its divisors and roots are.)

B) (10) (Lemma 2 from class on 4/19) Show that if the roots of σ(x) = 0 are known, then we can get the error values by “Forney’s formula”: For all ℓ ∈ L,

e_{ℓ} = \frac{ω(β^{−ℓ})}{β^{ℓ} ∏_{j∈L,j≠ℓ}(1 − β^{j−ℓ})}.

Have an enjoyable, productive summer, and best wishes to the graduating seniors!