Today we’ll continue our exploration of linear codes by learning more general decoding methods. We will build on the idea of using the syndrome for our decoding as we did for 1-error-correcting codes, but apply it in two algorithms that work for codes with larger minimum distances. To do this, we’ll need to understand the concept of cosets of a linear code.
Let \(C\) be a linear \([n,k,d]\) code over \(\F_q\text{.}\) A standard array for \(C\) is an array of elements from \(\F_q^n\) with \(q^{n-k}\) rows and \(q^k\) columns constructed as follows:
The first row consists of the codewords of \(C\text{,}\) starting with the zero codeword.
Each subsequent row is starts with a word \(e\in\F_{q}^{n}\) of smallest Hamming weight that has not yet appeared in the array, followed by the words \(e+c\) where \(c\) runs through all non-zero codewords of \(C\) in the same order as they appear in the first row.
Which rows of the standard array had only one choice for their leading element? What was the weight of that element? How is this related to the minimum distance of the code?
Use the standard array decoding algorithm to decode and determine the error pattern that occurred if the received word is (a) \(\by=01111\) and (b) \(\by=11010\) using the standard array you constructed in the first exercise.
Use syndrome decoding to decode and determine the error pattern that occurred if the received word is (a) \(\by=01101\) and (b) \(\by=10111\) using the syndrome table you constructed in the previous exercise.
