Skip to main content

Algebraic Coding Theory MATH 4012 Spring 2026

Dr. Hunter Lehmann

Print preview

Paper size
Additional printing options
Print headers
Print footers

Worksheet Concatenated Codes and BCH Codes

Today we will practice working with the concatenated code construction introduced in the Daily Prep. We will also learn about BCH codes, which are an important family of codes that we can construct from Reed-Solomon codes as subfield subcodes. We’ve actually seen this technique before - this is the technique we used in Frobenius Maps & a 2-Error Correcting Code to construct our first code that could correct more than one error.
🔗

1.

In this exercise we will build a \([35,6,12]\) binary linear code.
🔗

(a)

Construct (give a generator matrix for) a \([5,2,4]\) GRS code over \(F=\F_2[\beta]/(\beta^3+\beta+1)\) with code locators \(\alpha_i=\beta^i\) for \(i=1,\dots,5\) and generator column multipliers \(u_i=1\) for \(i=1,\dots,5\text{.}\) You will use this code as \(C_{\mathrm{out}}\text{.}\)
🔗
Solution.
We have
\begin{equation*} G_{\mathrm{out}}=\begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \amp 1 \\ \beta \amp \beta^2 \amp \beta^3 \amp \beta^4 \amp \beta^5 \end{bmatrix}\text{.} \end{equation*}
🔗
🔗
🔗

(b)

For the inner code, let’s use the \([7,3,4]_2\) simplex code, the dual code of the \([7,4,3]\) Hamming code. Based on what you know about the parity-check matrix for this Hamming code, write down a generator matrix for \(C_{\mathrm{in}}\text{.}\)
🔗
Solution.
This generator matrix is the parity-check matrix for the Hamming code so we have
\begin{equation*} G_{\mathrm{in}}=\begin{bmatrix} 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \\ 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \end{bmatrix}\text{.} \end{equation*}
🔗
🔗
🔗

(c)

Now let’s practice using the concatenated code with encoding map \(\mathcal{E}:F\to C_{\mathrm{in}}\) which takes each symbol \(z\) to the product \(\vec{z}G_{\mathrm{in}}\) where \(\vec{z}\) is the coefficient vector of \(z\) with respect to the standard basis \(\{1,\beta,\beta^2\}\) of \(F\) over \(\F_2\text{.}\) Consider the message \((101111)\text{.}\)
🔗
(i)
Split the message vector into appropriately sized chunks and convert it into a vector over \(F\) for encoding with \(C_{\mathrm{out}}\text{.}\)
🔗
Solution.
We need to split the message into chunks of length three since \([F:\F_2]=3\text{.}\) So we have
\begin{equation*} (101111)=(101\mid 111) = (\beta^6 \mid \beta^5)\text{.} \end{equation*}
🔗
🔗
🔗
(ii)
Encode this message vector to get a codeword of \(C_{\mathrm{out}}\text{.}\)
🔗
Solution.
Now we multiply our vector in \(F^2\) by \(G_{\mathrm{out}}\) to get
\begin{equation*} (\beta^6 \, \beta^5)\begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \amp 1 \\ \beta \amp \beta^2 \amp \beta^3 \amp \beta^4 \amp \beta^5 \end{bmatrix} = (0, \beta^2, \beta^5, 1, \beta^4)\text{.} \end{equation*}
🔗
🔗
🔗
(iii)
Compute \(\mathcal{E}(z_i)\) for each symbol in the codeword of \(C_{\mathrm{out}}\) and concatenate them to get a codeword in \(C_{\mathrm{cont}}\text{.}\)
🔗
Solution.
We have
\begin{align*} \mathcal{E}(z_1) \amp = (0\,0\,0)G_{\mathrm{in}} = (0\,0\,0\,0\,0\,0\,0) \\ \mathcal{E}(z_2) \amp = (0\,0\,1)G_{\mathrm{in}} = (1\,0\,1\,0\,1\,0\,1) \\ \mathcal{E}(z_3) \amp = (1\,1\,0)G_{\mathrm{in}} = (0\,1\,1\,1\,1\,0\,0) \\ \mathcal{E}(z_4) \amp = (1\,0\,0)G_{\mathrm{in}} = (0\,0\,0\,1\,1\,1\,1) \\ \mathcal{E}(z_5) \amp = (0\,1\,1)G_{\mathrm{in}} = (1\,1\,0\,0\,1\,1\,0) \text{.} \end{align*}
So our codeword is
\begin{equation*} \bc=(0\,0\,0\,0\,0\,0\,0\mid 1\,0\,1\,0\,1\,0\,1 \mid 0\,1\,1\,1\,1\,0\,0 \mid 0\,0\,0\,1\,1\,1\,1 \mid 1\,1\,0\,0\,1\,1\,0)\text{.} \end{equation*}
🔗
🔗
🔗
🔗
🔗

2.

Let \(f(x)\in \F_2[x]\text{.}\) Show that if \(\alpha\) is a root of \(f\) in some extension field \(E\) of \(\F_2\) then so is \(\alpha^2\text{.}\)
🔗
Solution.
Let \(f(x)=\sum_{i=0}^d a_i x^i\) where \(a_i\in \F_2\text{.}\) Now we have \(a_i^2=a_i\) and since \(\char(E)=2\) squaring distributes over sums in \(E\) so
\begin{align*} 0 \amp = (f(\alpha))^2\\ \amp = (\sum_{i=0}^d a_i\alpha^i)^2\\ \amp = \sum_{i=0}^d a_i^2 \alpha^{2i}\\ \amp = \sum_{i=0}^d a_i \alpha^{2i}\\ \amp = f(\alpha^2)\text{.} \end{align*}
🔗
🔗
🔗

3.

Use the fact you just showed to argue that in a binary BCH code, the constraint \(c(\alpha^{2k})=0\) is redundant with the constraint \(c(\alpha^k)=0\) for any \(k\geq 1\text{.}\)
🔗
Solution.
By the previous result, if \(c(\alpha^k)=0\) then \(c((\alpha^k)^2)=c(\alpha^{2k})=0\text{.}\) So the latter constraint is implied by the former.
🔗
🔗
🔗

4.

Use this result to give a better bound for the dimension of a binary narrow-sense BCH code of length \(n\) and designed distance \(D\text{.}\) Remember that such a code has a consecutive root sequence
\begin{equation*} \alpha, \alpha^2,\dots, \alpha^{D-1}\text{.} \end{equation*}
🔗
Solution.
Because the root sequence is consecutive beginning at \(\alpha^1\) if we have a root \(\alpha^{2k}\) we must also have the root \(\alpha^k\text{.}\) So we can remove all even-power constraints on the polynomial, which will leave \((D-1)/2\) polynomial root constraints if \(D\) is odd, or \((D-1)/2+1\) if \(D\) is even. After converting them into linear constraints, we get therefore
\begin{equation*} k\geq n - m\left\lceil\frac{D-1}{2}\right\rceil\text{.} \end{equation*}
🔗
🔗
🔗
🔗
PrevTopNext