1.
True/False: In a BCH code over \(\F_2\text{,}\) the block length can be even.
Print preview
Worksheet Weekly Practice 10
Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credit for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
To abide by the class academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
True/False, Multiple Choice, & Fill-In.
For these problems a justification is not required for credit, but it may be useful for your own understanding to include one. True/False problems should be marked True if the statement is always true, and False otherwise. Multiple choice problems may have more than one correct answer if that is indicated in the problem statement; be sure to select all that apply. Fill-in problems require a short answer such as a number, word, or phrase.
2.
True/False: The minimum distance of a concatenated code with outer code parameters \([N,K,D]\) and inner code parameters \([n,k,d]\) is exactly \(dD\text{.}\)
3.
True/False: In a BCH code over \(\F_2\text{,}\) the redundancy \(n-k\) is always at most \((D-1)m\)
Short Response.
Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
4.
Recall from Daily Prep 16 that a burst of \(t\) errors is an error pattern where the difference \(i-j\) of the first and last changed positions of the transmitted codeword is \(t\text{.}\) Determine a general formula for the length of the longest burst of \(t\) errors that is guaranteed to be decodable by a concatenated code with outer code parameters \([N,K,D]_{q^k}\) and inner code parameters \([n,k,d]_q\text{.}\)
Solution.
Let \(e_o=\lfloor(D-1)/2\rfloor\) and \(e_i=\lfloor(d-1)/2\rfloor\) be the error-correction capabilities of the outer and inner codes respectively. Our burst must result in no more than \(e_o\) blocks of the code being corrupted. The maximal burst for which this holds will fully corrupt \(e_o-1\) blocks of the code in the interior of the burst giving \(n(e_o-1)\) errors. On the sides of the burst, it must just barely corrupt one block more, requiring another \(e_i+1\) errors. Then another \(e_i\) errors can occur without corrupting the next block. Shifting this block further left or right will never corrupt more than \(e_o\) blocks so is guaranteed to be decodable. But adding one more error on the end can corrupt the next block too resulting in \(e_o+1\) block corruptions and potential loss of decodability. So the answer is
\begin{equation*}
t=n(e_0-1)+2e_i+1\text{.}
\end{equation*}
5.
Construct a binary BCH code of length 5 from a narrow-sense Reed Solomon code with designed distance 3. This means giving either a parity-check matrix (without redundant rows) or a generator matrix for the code. The same argument we used in class to show how to turn the polynomial equations \(c(\alpha^{\ell})=0\) into linear equations over \(\F_2\) shows that a parity-check matrix for a BCH code can be constructed by replacing the symbols of a parity-check matrix for the underlying RS code with their coordinate representation with respect to some basis over \(\F_2\) as column vectors.
Solution.
We need a binary code of length \(5\text{,}\) so we need to choose \(m\) such that \(2^m-1\) is a multiple of \(5\text{,}\) which first happens when \(m=4\text{.}\) Then if \(\beta\) is the primitive generator of \(\F_{2^4}=\F_2[\beta]/(\beta^4+\beta+1)\) we can choose \(\alpha=\beta^3\) to get our element of order \(5\text{.}\) Since the code is narrow-sense we take \(b=1\text{.}\) To get a designed distance of \(3\) we need a dimension of \(5-3+1=3\) so a parity-check matrix for the underlying RS code is
\begin{equation*}
H_{\RS} = \begin{bmatrix}
1 \amp \beta^3 \amp \beta^6 \amp \beta^9 \amp \beta^{12} \\
1 \amp \beta^6 \amp \beta^{12} \amp \beta^3 \amp \beta^9
\end{bmatrix}\text{.}
\end{equation*}
As in the example in class, the second row corresponding to the root condition \(c(\alpha^2)=0\) is implied by the first row’s root condition of \(c(\alpha)=0\text{.}\) So we construct a check matrix for the BCH code by replacing the first row of \(H_{\RS}\) with the column vector coordinate representations of these elements of \(\F_{2^4}\) in terms of the basis \(\{1,\beta,\beta^2,\beta^3\}\) of \(\F_{2^4}\) over \(\F_{2}\) to get
\begin{equation*}
H_{\mathrm{BCH}}=\begin{bmatrix}
1 \amp 0 \amp 0 \amp 0 \amp 1\\
0 \amp 0 \amp 0 \amp 1 \amp 1\\
0 \amp 0 \amp 1 \amp 0 \amp 1\\
0 \amp 1 \amp 1 \amp 1 \amp 1
\end{bmatrix}\text{.}
\end{equation*}
This matrix has full rank (seen quickly by swapping row 2 and row 4), so this is the parity-check matrix for the code and this BCH code is a \([5,1,5]_2\) code, since a quick check shows that \((1,1,1,1,1)\) is orthogonal to \(H_{\mathrm{BCH}}\text{.}\)
