PROBLEM SET #5 Solution

$30.00

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(22) based on the primitive polynomial X2 + 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).

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

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

  1. The polynomial p(X) = X2 + 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 XN − 1 is divisible by p(X) is n = 42 − 1. Just check that it is irreducible.

  1. Construct a table for GF(42) based on the primitive polynomial p(X) = X2 + 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, ω, ω2}), and vector (i.e., (a, b) where a, b are in GF(4)= {0, 1, ω, ω2}) representations of each of the sixteen elements. To check your solution, α8 = ω2 +α which is represented

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

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

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

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

I=0

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

Problem 3

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

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

Problem 4 Decode the polynomial r(X) = ω2X9 + ωX8 + X3 + X with respect to the BCH code of Problem 3 using the Berlekmap-Massey algorithm.


error: Content is protected !!