MAT 3343, APPLIED ALGEBRA, FALL 2003

Answers to Problem Set 6

Peter Selinger

Problem 1. Let p(x) = x^{3} + x + 1 be the generator polynomial.

(a) The sixteen codewords are shown here with their corresponding plaintext words:

0000000 0000 0100111 0100 1000101 1000 1100010 1100
0001011 0001 0101100 0101 1001110 1001 1101001 1101
0010110 0010 0110001 0110 1010011 1010 1110100 1110
0011101 0011 0111010 0111 1011000 1011 1111111 1111

(b) 0011101 1011000 1110100

(c) The Hamming distance is 3; thus this code detects 2 errors and corrects 1.

(d) The syndrome is the remainder of the division by p(x). We have

x^{5} + x^{4} + x^{2} + x = p(x)(x^{2} + x + 1) + (x^{2} + x + 1)
x^{6} + x^{5} + x^{4} = p(x)(x^{3} + x^{2}) + x^{2}
x^{5} + x^{4} + x^{2} = p(x)(x^{2} + x + 1) + (x^{2} + 1)

so therefore:

codeword syndrome
0110110  111
1110000  100
0110100  101

We can decode using the “nearest neighbor” method. We find 0010110 1110100 1110100 for the corrected codewords, and 0010 1110 1110 for the decoded message. Alternatively, we can do part (f) first and use the parity check matrix to find the error positions corresponding to each syndrome.

(e) The rows of the generator matrix are the codewords for 1000, 0100, 0010, 0001:

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

(f) The columns of the parity check matrix form a basis for the null space of G.

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

Problem 2. A primitive element is an element of order 15. From Handout 5, we already know that α is a primitive element. More generally, if β = α^{k}, then we have β^{m} = 1 iff α^{km} = 1 iff 15|km. So the order of β is the smallest m such that 15|km. We can use this to calculate the order of each element:

Element Order
α^{0}  1
α  15
α^{2}  15
α^{3}  5
α^{4}  15
α^{5}  3
α^{6}  5
α^{7}  15

Element Order
α^{8}  15
α^{9}  5
α^{10}  3
α^{11}  15
α^{12}  5
α^{13}  15
α^{14}  15

So the primitive elements are: α, α^{2}, α^{4}, α^{7}, α^{8}, α^{11}, α^{13}, α^{14}. Indeed, these are precisely the element α^{m} such that gcd(m, 15) = 1.

Problem 3. For calculations in GF (32), we refer to the representation shown in Table 1 (on page 4).

(a) We first calculate p_{3}(x).

Method 1: We are looking for an irreducible polynomial p(x) such that p(α^{3}) = 0. Letting x = α^{3}, we first calculate x^{n} for various n:

\begin{matrix}x^{0} = α^{0} = 1 & (00001) \\ x^{1} = α^{3} & (01000) \\ x^{2} = α^{6} = α^{3} + α & (01010) \\ x^{3} = α^{9} = α^{4} + α^{3} + α & (11010) \\ x^{4} = α^{12} = α^{3} + α^{2} + α & (01110) \\ x^{5} = α^{15} = α^{4} + α^{3} + α^{2} + α + 1 & (11111) \end{matrix}

These six expressions correspond to six vectors in a 5-dimensional vector space (shown in vector notation in the right column). Thus, they must be linearly dependent. Using linear algebra, we find the linear dependency: x^{5}+x^{4}+x^{3}+x^{2}+x^{0} = 0. Thus the polynomial p(x) = x^{5}+x^{4}+x^{3}+x^{2}+1 has α^{3} as a root. Since x^{0}, …, x^{4} are linearly independent, no smallerdegree polynomial has α^{3} as a root, and thus p(x) is irreducible.

Method 2: There is a second, more complicated method for calculating p_{3}(x). It is not very practical, but interesting. Since α^{3} is a root of p_{3}(x), and using the fact that p_{3}(x^{2}) = p_{3}(x)^{2}, it follows that α^{6}, α^{12}, α^{24}, α^{48} = α^{17}, and α^{34} = α^{3} are also roots of p_{3}(x). Moreover, since p_{3}(x) is a polynomial of degree at most 5 (as we know from method 1!), these are the only roots of p_{3}(x), and we calculate:

p_{3}(x) = (x − α^{3})(x − α^{6})(x − α^{12})(x − α^{24})(x − α^{17})
= (x^{2} + αx + α^{9})(x^{2} + α^{4}x + α^{5})(x − α^{17})
= (x^{2} + αx + α^{9})(x^{3} + α^{18}x^{2} + α^{14}x + α^{22})
= x^{5} + (α^{18} + α)x^{4} + (α^{14} + α^{19} + α^{9})x^{3}
+ (α^{22} + α^{15} + α^{27})x^{2} + (α^{23} + α^{23})x + (α^{31})
= x^{5} + x^{4} + x^{3} + x^{2} + 1

(b) Next, we calculate p_{5}(x). We only use Method 1. Let x = a^{5}, then

\begin{matrix}x^{0} = α^{0} = 1 & (00001) \\ x^{1} = α^{5} = α^{2} + 1 & (00101) \\ x^{2} = α^{10} = α^{4} + 1 & (10001) \\ x^{3} = α^{15} = α^{4} + α^{3} + α^{2} + α + 1 & (11111) \\ x^{4} = α^{20} = α^{3} + α^{2} & (01100) \\ x^{5} = α^{25} = α^{4} + α^{3} + 1 & (11001) \end{matrix}

We find the linear dependency: x^{5} + x^{4} + x^{2} + x + 1 = 0. So p_{5}(x) = x^{5} + x^{4} + x^{2} + x + 1.

Problem 4. For calculations in GF (16) relative to β where β^{4} = 1+β^{3}, we refer to the representation shown in Table 2 (on page 4).

We need to calculate p_{1}(x), p_{3}(x) and p_{5}(x), where p_{n}(x) is the irreducible polynomial with root β^{n}. We already know that p_{1}(x) = x^{4} + x^{3} + 1. To calculate

\begin{aligned}α^{0} & = & 1 & 00001 \\ α^{1} & = & α & 00010 \\ α^{2} & = & α^{2} & 00100 \\ α^{3} & = & α^{3} & 01000 \\ α^{4} & = & α^{4} & 10000 \\ α^{5} & = & α^{2} + 1 & 00101 \\ α^{6} & = & α^{3} + α & 01010 \\ α^{7} & = & α^{4} + α^{2} & 10100 \\ α^{8} & = & α^{3} + α^{2} + 1 & 01101 \\ α^{9} & = & α^{4} + α^{3} + α & 11010 \\ α^{10} & = & α^{4} + 1 & 10001 \\ α^{11} & = & α^{2} + α + 1 & 00111 \\ α^{12} & = & α^{3} + α^{2} + α & 01110 \\ α^{13} & = & α^{4} + α^{3} + α^{2} & 11100 \\ α^{14} & = & α^{4} + α^{3} + α^{2} + 1 & 11101 \\ α^{15} & = & α^{4} + α^{3} + α^{2} + α + 1 & 11111 \end{aligned} \begin{aligned}α^{16} & = & α^{4} + α^{3} + α + 1 & 11011 \\ α^{17} & = & α^{4} + α + 1 & 10011 \\ α^{18} & = & α + 1 & 00011 \\ α^{19} & = & α^{2} + α & 00110 \\ α^{20} & = & α^{3} + α^{2} & 01100 \\ α^{21} & = & α^{4} + α^{3} & 11000 \\ α^{22} & = & α^{4} + α^{2} + 1 & 10101 \\ α^{23} & = & α^{3} + α^{2} + α + 1 & 01111 \\ α^{24} & = & α^{4} + α^{3} + α^{2} + α & 11110 \\ α^{25} & = & α^{4} + α^{3} + 1 & 11001 \\ α^{26} & = & α^{4} + α^{2} + α + 1 & 10111 \\ α^{27} & = & α^{3} + α + 1 & 01011 \\ α^{28} & = & α^{4} + α^{2} + α & 10110 \\ α^{29} & = & α^{3} + 1 & 01001 \\ α^{30} & = & α^{4} + α & 10010 \\ α^{31} & = & 1 & 00001 \end{aligned}

Table 1: Representation of GF (32) with α^{5} = α^{2} + 1

\begin{aligned}β^{0} & = & 1 & 0001 \\ β^{1} & = & β & 0010 \\ β^{2} & = & β^{2} & 0100 \\ β^{3} & = & β^{3} & 1000 \\ β^{4} & = & β^{3} + 1 & 1001 \\ β^{5} & = & β^{3} + β + 1 & 1011 \\ β^{6} & = & β^{3} + β^{2} + β + 1 & 1111 \\ β^{7} & = & β^{2} + β + 1 & 0111 \end{aligned} \begin{aligned}β^{8} & = & β^{3} + β^{2} + β & 1110 \\ β^{9} & = & β^{2} + 1 & 0101 \\ β^{10} & = & β^{3} + β & 1010 \\ β^{11} & = & β^{3} + β^{2} + 1 & 1101 \\ β^{12} & = & β + 1 & 0011 \\ β^{13} & = & β^{2} + β & 0110 \\ β^{14} & = & β^{3} + β^{2} & 1100 \\ β^{15} & = & 1 & 0001 \end{aligned}

Table 2: Representation of GF (16) with β^{4} = β^{3} + 1 p_{3}(x), let x = β^{3}. We have

\begin{matrix}x^{0} = β^{0} = 1 & (0001) \\ x^{1} = β^{3} = β^{3} & (1000) \\ x^{2} = β^{6} = β^{3} + β^{2} + β + 1 & (1111) \\ x^{3} = β^{9} = β^{2} + 1 & (0101) \\ x^{4} = β^{12} = β + 1 & (0011) \end{matrix}

so we get the linear dependency x^{4} + x^{3} + x^{2} + x + 1 = 0, so p_{3}(x) = x^{4} + x^{3} + x^{2} + x + 1. To calculate p_{5}(x), let x = β^{5}. We have

\begin{matrix}x^{0} = β^{0} = 1 & (0001) \\ x^{1} = β^{5} = β^{3} + β + 1 & (1011) \\ x^{2} = β^{10} = β^{3} + β & (1010) \end{matrix}

We get the linear dependency x^{2} + x + 1 = 0, so p_{5}(x) = x^{2} + x + 1.

It follows that the generator polynomial for the 2-error correcting code is

\begin{aligned}lcm(p_{1}(x), p_{3}(x)) & = & (x^{4} + x^{3} + 1)(x^{4} + x^{3} + x^{2} + x + 1) \\ & = & x^{8} + x^{4} + x^{2} + x + 1 \end{aligned}

This code is therefore a (15, 7)-code.

The generator polynomial for the 3-error correcting code is

lcm(p_{1}(x), p_{3}(x), p_{5}(x)) = (x^{4} + x^{3} + 1)(x^{4} + x^{3} + x^{2} + x + 1)(x^{2} + x + 1)
= (x^{8} + x^{4} + x^{2} + x + 1)(x^{2} + x + 1)
= x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{2} + 1

This code is therefore a (15, 5)-code.

Problem 5. We use the representation of GF (32) from Table 1. This problem is easy because we already found p_{3}(x) = x^{5} + x^{4} + x^{3} + x^{2} + 1 in Problem 3. We have p_{1}(x) = x^{5} + x^{2} + 1. Thus, the generator polynomial for the 2-error correcting BCH code is:

\begin{aligned}lcm(p_{1}(x), p_{3}(x)) & = & (x^{5} + x^{2} + 1)(x^{5} + x^{4} + x^{3} + x^{2} + 1) \\ & = & x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{3} + 1 \end{aligned}

The resulting code is a (31, 21)-code.