Reviewing Codes Derived from RS Codes & More Minimal Polynomials

Print preview

Worksheet Reviewing Codes Derived from RS Codes & More Minimal Polynomials

Today we are going to start by going back to exercises 3 and 4 from Problem Set M5A before returning to the problems we did not finish from last class.

🔗

1. Building a Concatenated Code.

Give a construction of a concatenated code \(C_{\mathrm{cont}}\) which is a \([765,248,\geq 63]_2\) code. This means identifying explicitly the inner code \(C_{\mathrm{in}}\text{,}\) the outer code \(C_{\mathrm{out}}\text{,}\) and the mapping from symbols of \(C_{\mathrm{out}}\) to codewords of \(C_{\mathrm{in}}\text{.}\) Justify that your construction indeed achieves the desired parameters. How many errors can your code correct?

🔗

Hint.

Find an appropriate RS code to use as the outer code and an appropriate binary code to use as the inner code, noticing that \(765=51\cdot 15, 248=31\cdot 8\) and \(63=21\cdot 3\text{.}\)

🔗

2. BCH Code Example.

Let \(C_{\RS}\) be a \([21,17]\) normalized RS code over an extension field \(E\) of \(F=\GF(2)\) and let \(C_{\mathrm{BCH}}\) be the BCH code \(C_{\RS}\cap F^{21}\) over \(F\text{.}\)

🔗

(a)

Find the smallest possible size of \(E\text{.}\)

🔗

(b)

Show that the dimension of \(C_{\mathrm{BCH}}\) is at least \(8\text{.}\)

🔗

(c)

Show that the minimum distance of \(C_{\mathrm{BCH}}\) is at least \(6\text{.}\)

🔗

In the next series of problems you will investigate the structure of a field \(K\) of order \(2^6\) with primitive element \(\beta\text{.}\) It may be useful to recall that the irreducible polynomials of degree 4 or lower over \(\F_2\) are

\begin{gather*} x, x+1\\ x^2+x+1 \\ x^3+x+1, x^3+x^2+1 \\ x^4+x+1, x^4+x^3+1, x^4+x^3+x^2+x+1 \text{.} \end{gather*}

🔗

3.

What sizes of subfields can \(K\) have?

🔗

4.

What degrees can minimal polynomials of elements of \(K\) have?

🔗

5.

Identify the minimal polynomials which are factors of \(x^4-x\) and corresponding elements (as powers of \(\beta\)) that comprise the subfield of size \(4\) in \(K\text{.}\)

🔗

Hint.

If \(a\) is an element of order \(n\) then \(a^{n/m}\) has order \(m\) when \(m \mid n\text{.}\)

🔗

6.

Identify the minimal polynomials which are factors of \(x^8-x\) and corresponding elements (as powers of \(\beta\)) that comprise the subfield of size \(8\) in \(K\text{.}\)

🔗

7.

What is the intersection of these two subfields?

🔗

8.

Based on your work above, how many elements of \(K\) have minimal polynomials of degree \(6\text{?}\) What does this tell you about the number of monic irreducible polynomials of degree \(6\) over \(\GF(2)\text{?}\)

🔗

Theorem 91. Finite Fields of the Same Size are Isomorphic.

All finite fields of the same size are isomorphic.

🔗

The goal of the next problem is to prove the theorem above. To this end, let \(E\) and \(K\) be finite fields of characteristic \(p\) and size \(p^n\text{.}\) We may assume without loss of generality that the prime subfield of both is \(\GF(p)\text{.}\) Further, fix an irreducible polynomial \(a(x)\) of degree \(n\) over \(\GF(p)\text{.}\) This is a minimal polynomial for some element \(\alpha \in E\) and for some element \(\beta \in K\text{.}\)

🔗

In your problem set over this material, you will show that

\begin{align*} E \amp =\{u(\alpha) \mid u(x) \in F[x], \deg(u(x))\leq n-1\} \\ K \amp =\{u(\beta) \mid u(x) \in F[x], \deg(u(x))\leq n-1\} \end{align*}

🔗

9.

Define the map \(\varphi: K \to E\) by

\begin{equation*} \varphi(u(\beta))=u(\alpha), \quad u(x) \in F[x], \deg(u(x))\leq n-1\text{.} \end{equation*}

Show that \(\varphi\) is a field isomorphism, i.e. that it is one-to-one, onto, additive, and multiplicative.

🔗

Prev Top Next