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 Weekly Practice 4

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.
🔗

1.

True or False: If \(\bx\) and \(\by\) are in the same coset of a linear code \(C\text{,}\) then they have the same syndrome with respect to \(C\text{.}\)
🔗
Solution.
True. If \(\bx\) and \(\by\) are in the same coset of a linear code \(C\text{,}\) then there exists some codeword \(\bc\in C\) such that \(\by=\bx+\bc\text{.}\) Then the syndrome of \(\by\) is given by
\begin{equation*} H\transpose{\by}=H\transpose{(\bx+\bc)}=H\transpose{\bx}+H\transpose{\bc}=H\transpose{\bx} \end{equation*}
since \(H\transpose{\bc}=0\) for all codewords \(\bc\in C\text{.}\)
🔗
🔗
🔗

2.

True or False: If \(\bx\in \F_q^n\) has syndrome \(\bs\in \F_q^{n-k}\) with respect to a linear code \(C\text{,}\) then there is a unique coset leader with syndrome \(\bs\text{.}\)
🔗
Solution.
False. This is true only if \(\wt(\bx)\leq \lfloor(d-1)/2\rfloor\text{.}\)
🔗
🔗
🔗

3.

Fill-In: A code is if every vector in the ambient space is contained in exactly one sphere of radius \(\lfloor (d-1)/2 \rfloor\) centered at a codeword, where \(d\) is the minimum distance of the code.
🔗
Solution.
Such a code is called a perfect code.
🔗
🔗
🔗

5.

Fill-In: The Singleton bound for linear codes says for a linear code with parameters \([n,k,d]_q\text{,}\) we have \(d\leq \fillinmath{n-k+1}\text{.}\)
🔗
Solution.
The Singleton bound states that for a linear code with parameters \([n,k,d]_q\text{,}\) we have \(d\leq n-k+1\text{.}\)
🔗
🔗
🔗
🔗

Short Response.

Your responses to these questions should be complete solutions with justifications, as per the Grading Specifications.
🔗

6.

Let a parity check matrix for a \([4,2]_3\) code \(C\) be
\begin{equation*} H=\begin{bmatrix} 1 \amp 0 \amp 2 \amp 1 \\ 0 \amp 1 \amp 1 \amp 1 \\ \end{bmatrix}\text{.} \end{equation*}
🔗
(a)
Determine whether or not \(C\) is a perfect code.
🔗
Solution.
\(H\) has distance \(d=3\) since all columns are nonzero and no two columns are multiples of each other and the fourth column is the sum of the first two columns. The Hamming bound for these parameters states that
\begin{equation*} M\leq \frac{3^4}{\sum_{i=0}^{\lfloor(3-1)/2\rfloor}\binom{4}{i}(3-1)^i}=\frac{81}{1+8}=9 \end{equation*}
so the code meets the Hamming bound with equality and is thus a perfect code. (Actually this is the ternary Hamming code of length \(4\text{.}\))
🔗
🔗
🔗
(b)
Construct a lexicographic standard array for \(C\text{.}\) A standard array is lexicographic if the coset leaders are chosen in lexicographic order (within the vectors of minimal weight at each step). For example, the first few vectors in \(\F_3^3\) in lexicographic order are
\begin{equation*} 000, 001, 002, 010, 011, 012, 020, 021, 022, 100\text{.} \end{equation*}
🔗
Solution.
The code \(C\) has size \(M=3^2=9\) so there are \(3^4/3^2=9\) cosets. Since this is a perfect code with distance \(d=3\text{,}\) the coset leaders are given by the vectors of weight at most \(\lfloor (3-1)/2 \rfloor=1\text{.}\) The vectors of weight 0 or 1 in lexicographic order are
\begin{equation*} 0000,0001,0002,0010,0020,0100,0200,1000,2000\text{.} \end{equation*}
The standard array is given by the table below.
🔗
0000 1210 2201 2120 1102 0111 0222 2012 1021
0001 1211 2202 2121 1100 0112 0220 2010 1022
0002 1212 2200 2122 1101 0110 0221 2011 1020
0010 1220 2211 2100 1112 0121 0202 2022 1001
0020 1200 2221 2110 1122 0101 0212 2002 1011
0100 1010 2001 2220 1202 0211 0022 2112 1121
0200 1110 2101 2020 1002 0011 0022 2212 1221
1000 2210 0201 0120 2102 1111 1222 0012 2021
2000 0210 1201 1120 0102 2111 2222 1012 0021
🔗
🔗
(c)
Construct a one-to-one correspondence between coset leaders in (b) and syndromes.
🔗
Solution.
Coset Leader Syndrome
0000 00
0001 11
0002 22
0010 21
0020 12
0100 01
0200 02
1000 10
2000 20
🔗
🔗
(d)
Decode the received vectors \(\by_1=(2,2,1,1), \by_2=(2,2,2,1)\) and \(\by_3=(2,2,2,2)\text{.}\)
🔗
Solution.
\(\by_1\text{.}\) The syndrome of this vector is \(s_1=H\transpose{\by_1}=21\text{.}\) From our table we see this corresponds to the coset leader \(0010\) so we decode to \(\bc_1=2211-0010=2201\text{.}\)
🔗
\(\by_2\text{.}\) The syndrome of this vector is \(s_2=H\transpose{\by_2}=12\text{.}\) From our table we see this corresponds to the coset leader \(0020\) so we decode to \(\bc_2=2221-0020=2201\) again.
🔗
\(\by_3\text{.}\) The syndrome of this vector is \(s_3=H\transpose{\by_3}=20\text{.}\) From our table we see this corresponds to the coset leader \(2000\) so we decode to \(\bc_3=2222-2000=0222\text{.}\)
🔗
🔗
🔗
🔗

7.

Determine whether or not a binary \((n,k,d)=(12,7,5)\) code \(C\) exists. Justify your answer.
🔗
Solution.
The Hamming bound states that for a binary code of block length \(n\text{,}\) size \(M\text{,}\) and minimum distance \(d\text{,}\) we have
\begin{equation*} 2^k=M\leq \frac{2^n}{\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom{n}{i}}\text{.} \end{equation*}
In this case, we have \(\lfloor (5-1)/2 \rfloor=2\) so that the Hamming bound states that
\begin{equation*} 128=2^7\leq \frac{2^{12}}{\sum_{i=0}^{2}\binom{12}{i}}=\frac{4096}{1+12+66}=\frac{4096}{79}\approx 51.85 \end{equation*}
which is false. Thus no such code can exist.
🔗
🔗
🔗
🔗
🔗
PrevTopNext