Solved–Reading Assignment: Lecture Notes: 6. Textbook: Sections 7.1–7.4. —–PROBLEM SET #5– Solution

Description

Reading Assignment: Lecture Notes: 6. Textbook: Sections 7.1–7.4.

Solve problems by hand, i.e., do not use symbolic and/or numerical mathematics software package to solve the problems. However, you can use them, if you want, to check your answers.

Remark You have to solve the problems in order since each problem depends on the previous problems.

Problem 1 In this problem we construct addition and multiplication tables for GF(4) which we will use later to define a BCH code over this field.

1. Construct a table for GF(2²) based on the primitive polynomial X² + X + 1. Display the power, polynomial, and vector representations of each of the four elements, similar to Table 2.8 in textbook. However, use ω instead of α (which will be used later in another context).

2. GF(4) is composed of four elements, 0, 1, ω, and ω². Construct addition and multiplication tables for GF(4).

Problem 2 In this problem, we will construct GF(4²) as an extension field of GF(4) constructed in Problem 1 with elements 0, 1, ω, and ω².

1. The polynomial p(X) = X² + X + ω is a primitive polynomial over GF(4), i.e., p(X) is irreducible (does not factor as a product of polynomials of degree less than two) and the minimal positive integer n such that X^N − 1 is divisible by p(X) is n = 4² − 1. Just check that it is irreducible.

2. Construct a table for GF(4²) based on the primitive polynomial p(X) = X² + X + ω as an extension field of GF(4) rather than GF(2) as in Table 2.8 in textbook. Display the power (i.e., 0, 1, α^I for i = 1, 2, . . . , 14 where α is a root

of p(X)), polynomial (i.e., a + bα where a, b are in GF(4) = {0, 1, ω, ω²}), and vector (i.e., (a, b) where a, b are in GF(4)= {0, 1, ω, ω²}) representations of each of the sixteen elements. To check your solution, α⁸ = ω² +α which is represented

by the vector (ω², 1). (The fact that all powers of α^I, i = 1, 2, . . . , 14 have distinct nonzero polynomial representations and α¹⁵ has the same polynomial representation as 1 proves that the minimal positive integer n such that X^N − 1 is divisible by p(X) is n = 4² − 1, which completes the proof that p(X) is a primitive polynomial.)

3. Find the minimal polynomial over GF(4) of each nonzero element in GF(4²). To do this, you need to determine the exponent of each nonzero element β in

GF(4²) with respect to GF(4). This is the least positive integer e such that

β^4E = β. Then, the minimal polynomial of β is ^E−¹(X − β^4I ). The minimal

I=0

polynomial should have coefficients in GF(4)= {0, 1, ω, ω²}. To check your solution, the minimal polynomial of α³ is (X + α³)(X + α¹²) = X² + ω²X + 1.

Problem 3

1. Find the generator polynomial of a double error correcting primitive BCH code over GF(4) of length 15.

2. Determine the dimension and the number of codewords in this BCH code.

Problem 4 Decode the polynomial r(X) = ω²X⁹ + ωX⁸ + X³ + X with respect to the BCH code of Problem 3 using the Berlekmap-Massey algorithm.