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 1

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.

For each of the following statements, determine whether it is true or false. A justification is not required for credit, but it may be useful for your own understanding to include one.
🔗

1.

True or False: The parity code \(C_{\oplus}\) over the binary alphabet which consists of all message vectors with a parity check bit appended can detect any single bit error.
🔗
Solution.
True. The parity code has minimum distance 2, so it can detect any single bit error.
🔗
🔗
🔗

2.

True or False: The dimension of a code can be larger than its block length.
🔗
Solution.
False. Since the dimension is the logarithm (base size of the alphabet) of the number of codewords, and each codeword has length equal to the block length, the dimension cannot exceed the block length.
🔗
🔗
🔗

3.

True or False: The rate of a code is always a number between 0 and 1.
🔗
Solution.
True. The rate of a code is the ratio of the dimension to the block length, so by the previous question it cannot exceed 1.
🔗
🔗
🔗

4.

True or False: In order for a code to be useful for error detection and correction, it must have minimum distance at least 2.
🔗
Solution.
False. Because we want the code to be useful for both detection and correction, the minimum distance must be at least 3. A code with minimum distance 2 could detect single bit errors, but could not correct any errors.
🔗
🔗
🔗
🔗

Short Response.

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

6.

For the code below over the binary alphabet, determine the block length, dimension, rate, and minimum distance.
\begin{gather*} C=\{000000, 101110, 011011, 110101, 111111, 010001, 100100, 001010\} \end{gather*}
🔗
Solution.
The block length is the length of each codeword, which is 6 here. The dimension is \(\log_2(8)=3\) since there are 8 codewords and this is a binary code. The rate is the ratio of dimension to block length, which is \(3/6=1/2\text{.}\) To find the minimum distance, we compute the Hamming distance between each pair of codewords. This is slightly tedious, but doing so systematically, we find that the minimum distance is 2. See the table below for the distances between each pair of codewords, ordered as in the list above.
🔗
\(c_{1}\) \(c_{2}\) \(c_{3}\) \(c_{4}\) \(c_{5}\) \(c_{6}\) \(c_{7}\) \(c_{8}\)
\(c_{1}\) 0 4 4 4 6 2 2 2
\(c_{2}\) 4 0 4 4 2 4 2 2
\(c_{3}\) 4 4 0 4 2 2 4 2
\(c_{4}\) 4 4 4 0 2 2 2 4
\(c_{5}\) 6 2 2 2 0 4 4 4
\(c_{6}\) 2 4 2 2 4 0 4 4
\(c_{7}\) 2 2 4 2 4 4 0 4
\(c_{8}\) 2 2 2 4 4 4 4 0
A quicker way to see this is that each codeword has even length and an even number of ones, so the distance must be even. Since there are codewords that differ in only two positions (for example, \(000000\) and \(010001\)), the minimum distance is 2.
🔗
🔗
🔗

7.

Can the code \(C\) above detect any single bit error? Why or why not?
🔗
Solution.
Yes. Since the minimum distance is 2, the code can detect any single bit error.
🔗
🔗
🔗

8.

Can the code \(C\) above correct any single bit error? Why or why not?
🔗
Solution.
No. Since the minimum distance is 2, the code cannot correct any single bit errors. For example, the received vector \(000001\) results from a single bit error in either sent word \(000000\) or \(010001\text{,}\) so there is no way to know which codeword was sent.
🔗
🔗
🔗

9.

For the code
\begin{gather*} C_2=\{000000, 100101, 010110, 001011, 110011, 101110, 011101, 111000\} \end{gather*}
which codeword is the received vector \(111110\) decoded to using nearest neighbor decoding?
🔗
Solution.
To decode the received vector \(111110\) using nearest neighbor decoding, we find the codeword in \(C_2\) that is closest to \(111110\) in terms of Hamming distance. The vector \(101110\) differs from the received vector in only one position, and every other codeword differs in at least two positions, so the nearest neighbor decoding of \(111110\) is \(101110\) for this code.
🔗
🔗
🔗
🔗
🔗
PrevTopNext