1.
What condition does Proposition 2.3.7 place on the columns of a parity-check matrix \(H\) for its associated code to be 1-error-correcting?
Print preview
Worksheet 1-Error Correcting Codes
In this activity, we’ll explore construction of 1-error correcting codes using parity-check matrices. We will also see how to efficiently decode for these codes. Afterwards, we’ll discuss as a class some of the following topics: generalizing this construction to more errors, extending binary Hamming codes to \(q\)-ary Hamming codes, or the dual of a linear code.
2.
Construct a parity-check matrix for a 1-error-correcting code over \(GF(3)\) with block length 4 and dimension 2.
3.
Construct a generator matrix for the code in the previous exercise. It may be helpful to use Calculation Tools to do the needed calculations depending on the form of the parity-check matrix you chose.
4.
Have a group member choose a secret message in \(GF(3)^2\text{,}\) encode it using the generator matrix from the previous exercise, and then introduce a single error into the resulting codeword. Share the received erroneous codeword with the rest of your group.
5.
Have the rest of the group decode the received erroneous codeword from the previous exercise by checking distances to the codewords. What was the original codeword and message?
Definition 18. Syndrome.
The syndrome of a received word \(\mathbf{y}\) is defined as
\begin{equation*}
\mathbf{s}=H\transpose{\mathbf{y}}
\end{equation*}
where \(H\) is a parity-check matrix for the code.
6.
Now let’s use the parity-check matrix to decode the received erroneous codeword from two exercises ago. Compute the syndrome of the received erroneous codeword. Can you find a relationship between the syndrome, the columns of the parity-check matrix, and the error that was introduced?
7.
Using the ideas from the previous exercise, propose an efficient decoding algorithm for 1-error-correcting codes using their parity-check matrices.
