Error correcting

CS 527 / ECE599 Error Correcting Codes Assignment No. 6, Due: Friday March 6th 2020

1. Find all monic irreducible polynomials of

(a) degree 5 over GF(2).

(b) degree 3 over GF(3).

2. Using extended GCD algorithm, find the multiplicative inverse of

(a) 23 mod 101

(b) (X6 + X4 + X2 + X + 1) (mod X8) over GF(2)

3. Prove the following properties of Euclid’s algorithm.

(a) tiri−1 − ti−1ri = (−1)ia (b) siri−1 − si−1ri = (−1)i+1b (c) siti−1 − si−1ti = (−1)i+1

(d) sia + tib = ri (proved in the class).

(e) deg (si) + deg (ri−1) = deg (b) for 1 ≤ i ≤ n + 1 (f) deg (ti) + deg (ri−1) = deg (a) for 0 ≤ i ≤ n + 1

4. Factor

(a) X15 − 1 over GF(2). (b) X9 −X over GF(3).

5. Find the degrees of the irreducible polynomials which are factors of X2

10 − X over GF(2). Further, find the number of these polynomials (note that you don’t have to find the factors).