Mathematics 392 – Seminar in Coding Theory Final Problem Set Solutions May 6, 2002

I. A) We have α = x mod h_{1}(x). So α satisfies α^{3} + α + 1 = 0 in F_{1}. If ϕ : F_{1} → F_{2} satisfies both properties in (1), then

0 = ϕ(0) = ϕ(α^{3} + α + 1) = ϕ(α^{3}) + ϕ(α) + ϕ(1) = ϕ(α)^{3} + ϕ(α) + 1

(where ϕ(1) = 1 since by the second equation in (1), ϕ(1) = ϕ(1 · 1) = ϕ(1)ϕ(1), but we dont want ϕ(1) = 0 – otherwise ϕ cannot be one to one). Hence ϕ(α) is a root of the equation x^{3} + x + 1 = 0 in F_{2}. The powers of β = y mod h_{2}(y) in F_{2} are

\begin{aligned}β^{0} & = 1 \\ β^{1} & = β \\ β^{2} & = β^{2} \\ β^{3} & = β^{2} + 1 \\ β^{4} & = β^{2} + β + 1 \\ β^{5} & = β + 1 \\ β^{6} & = β^{2} + β \\ β^{7} & = 1 \end{aligned}

Of these we see (β^{3})^{3} +β^{3} +1 = β^{9} +β^{3} +1 = β^{2} +β^{2} +1+1 = 0. Hence β^{3} is a root of the equation x^{3} + x + 1 = 0 in F_{2}. Similarly β^{5} and β^{6} are also roots of this equation. These are the only possibilities for ϕ(α): ϕ(α) ∈ {β^{3}, β^{5}, β^{6}}. (Note: {3, 5, 6} is the cyclotomic coset of 3 mod 8 − 1 = 7.)

B) Using the second equation in (1),

ϕ(α^{j}) = ϕ(α · α · · · · · α) = ϕ(α) · ϕ(α) · · · · · ϕ(α) = (ϕ(α))^{j}

Hence the choice ϕ(α) will determine the values of ϕ on all of the nonzero elements of the field.

C) Any one of the choices ϕ(α) = β^{3}, β^{5}, β^{6} will yield an isomorphism between F_{1} and F_{2}, if you extend ϕ to the powers of α using part B. For instance, with ϕ(α) = β^{3}, we have ϕ(α^{j} + α^{k}) = ϕ(α^{j}) + ϕ(α^{k}) for all j, k. (You needed to check this case by case. For example with j = 1, k = 2:

ϕ(α + α^{2}) = ϕ(α^{4}) = (β^{3})^{4} = β^{12} = β^{5}

And

ϕ(α) + ϕ(α^{2}) = β^{3} + (β^{3})^{2} = β^{3} + β^{6} = β^{2} + 1 + β^{2} + β = β + 1 = β^{5}

II. A) A generator matrix for C is

G = ( \begin{matrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{matrix} )

Forming all linear combinations of the rows, we get the following list of words in C:

\begin{matrix}\{0000000, 1101000, 0110100, 0011010, & 0001101, 1011100, 0101110, 0010111, \\ 1110010, 0111001, 1100101, 1000110, & 1010001, 1111111, 0100011, 1001011\} \end{matrix}

From this, we see that there is one word of weight 0, 7 of weight 3, 7 of weight 4, and 1 of weight 7, so W_{C}(t) = 1 + 7t^{3} + 7t^{4} + t^{7}.

B) This is just algebra: Since k = 4 for C, we substitute in the the McWilliams identity, simplify, and expand using the binomial theorem:

2^{4}W_{C^{⊥}}(t) = (1 + t)^{7} (1 + 7 (\frac{1 − t}{1 + t})^{3} + 7 (\frac{1 − t}{1 + t})^{4} + (\frac{1 − t}{1 + t})^{7})
= (1 + t)^{7} + 7(1 − t)^{3}(1 + t)^{4} + 7(1 − t)^{4}(1 + t)^{3} + (1 − t)^{7}
= (1 + 7t + 21t^{2} + 35t^{3} + 35t^{4} + 21t^{5} + 7t^{6} + t^{7})
+ 7(1 − 3t + 3t^{2} − t^{3})(1 + 4t + 6t^{2} + 4t^{3} + t^{4})
+ 7(1 + 3t + 3t^{2} + t^{3})(1 − 4t + 6t^{2} − 4t^{3} + t^{4})
+ (1 − 7t + 21t^{2} − 35t^{3} + 35t^{4} − 21t^{5} + 7t^{6} − t^{7})
= 16 + 112t^{4}

Hence W_{C^{⊥}}(t) = 1 + 7t^{4}.

C) (There were a number of different approaches used in the submitted solutions. Here is another one, even more elementary.) In fact the dual code of a cyclic code is always cyclic. Proof: Since we assume C is cyclic, the cyclic shift π maps C to itself. If v ∈ C and w ∈ C^{⊥} are arbitary words, then 0 = v · w = π(v) · π(w) (since cyclically shifting the two words simultaneously does not change the dot product). This says that π(w) is perpendicular to every word in C, so π(w) ∈ C^{⊥} and C^{⊥} is also closed under π. Hence C^{⊥} is also cyclic. A generator matrix for C^{⊥} is obtained by taking the transpose of a parity check matrix for C. I applied our usual method to get the H for C then took the transpose to yield:

G^{⊥} = ( \begin{matrix}1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix} )

The word in C^{⊥} giving a corresponding codeword polynomial of minimal degree comes from the first row: g^{⊥}(x) = 1 + x^{2} + x^{3} + x^{4}. This is the generator polynomial for C^{⊥}.

III. A) The question from Discussion 4 referred to in the problem said: If C = ⟨v_{1}, …, v_{k}⟩ and π(v_{i}) ∈ C for all i, then C is cyclic. Here we have the spanning set

{ev(1), ev(t), …, ev(t^{k−1})},

where ev(t^{j}) = (1, β^{j}, β^{2j}, …, β^{(2^{r}−2)j}), 1 ≤ j ≤ k − 1. Applying the cylic shift, we have

\begin{aligned}π(ev(t^{j}) & = (β^{(2^{r}−2)j}, 1, β^{j}, β^{2j}, …, β^{(2^{r}−3)j}) \\ & = ev(β^{(2^{r}−2)j}t^{j}) \end{aligned}

(using β^{2^{r}−1} = 1). The polynomial β^{(2^{r}−2)j}t^{j} is in the span of {1, t, t^{2}, …, t^{k−1}}. So this is also a codeword. Hence the image of ev is a cyclic code.

B) The product

(1 + x)(1 + x + x^{2} + ⋯ + x^{2^{r}−2}) = 1 + x^{2^{r}−1}

Every nonzero element in F_{2^{r}} satisfies 1 + x^{2^{r}−1} = 0, so every nonzero element is a root of one of the two factors on the left side of the last equation. Since x = 1 is a root of the first, the roots of 1 + x + x^{2} + ⋯ + x^{2^{r}−2} = 0 are all the nonzero elements of F_{2^{r}} except x = 1. Note: The polynomial 1 + x + x^{2} + ⋯ + x^{2^{r}−2} = 0 is the codeword polynomial corresponding to ev(1) = (1, 1, 1, …, 1). The next part deals with the ev(t^{j}) for j ≠ 0.

C) The codeword polynomial corresponding to ev(t^{j}) is

1 + β^{j}x + (β^{j}x)^{2} + ⋯ + (β^{j}x)^{2^{r}−2}

This has the form 1 + u + u^{2} + ⋯ + u^{2^{r}−2} with u = β^{j}x. By part B, the roots of this last polynomial are all u ≠ 0, 1 in F_{2^{r}}, so β^{j}x ≠ 0, 1. This yields all x ≠ 0, β^{−j}.

D) We must determine the common roots of all the polynomials corresponding to ev(t^{j}), j = 0, 1, …, k − 1. Combining parts B and C, we have the sets of roots as follows:

ev(1) ↔ all x ≠ 0, 1 ⇒ {β, β^{2}, …, β^{2^{r}−2}}
ev(t) ↔ all x ≠ 0, β^{−1} = β^{2^{r}−2} ⇒ {1, β, β^{2}, …, β^{2^{r}−3}}
ev(t^{2}) ↔ all x ≠ 0, β^{−2} = β^{2^{r}−3} ⇒ {1, β, β^{2}, …, β^{2^{r}−4}, β^{2^{r}−2}}
⋮  ⋮
ev(t^{k−1}) ↔ all x ≠ 0, β^{−k+1} = β^{2^{r}−k} ⇒ {1, β, β^{2}, …, β^{2^{r}−k−1}, β^{2^{r}−k+1}, …, β^{2^{r}−3}}

The set of common roots is found by removing 1, β^{2^{r}−2}, …, β^{2^{r}−k} from the nonzero elements of the field. The remaining set is

β, β^{2}, …, β^{2^{r}−k−1} = β^{δ−1}

This is the same as the set of roots of the generator polynomial of the Reed-Solomon code RS(2^{r}, δ) (with m = 0).

IV. A) Let β^{−ℓ} be any one of the roots of σ(x). Of the terms in the sum defining ω(x), all but the one with j = ℓ contain the factor (1 − β^{ℓ}x). Hence all those terms will go to zero when we substitute x = β^{−ℓ}. The remaining term is

(1)  ω(−ℓ) = e_{ℓ}β^{ℓ} ∏_{j≠ℓ}(1 − β^{j}β^{−ℓ})

This is not zero, since the error values are nonzero by definition, β ≠ 0, and (1 − β^{j−ℓ}) ≠ 0 if j ≠ ℓ. Hence none of the factors of σ(x) divide ω(x), so the gcd is 1.

B) This follows from (1). Just divide through to solve for e_{ℓ}.