Subsection Properties of Linear Codes
We can examine the Hamming code we just built. First the dimension.
The code is small enough that we can list all the codewords.
The minimum distance is perhaps one of the most important properties. Hamming codes always have minimum distance so they are always single error-correcting.
We know that the parity-check matrix and the generator matrix are useful for the construction, description and analysis of linear codes. The Sage method names are just a bit cryptic. Sage has extensive routines for analyzing matrices with elements from different fields, so we perform much of the subsequent analysis of these matrices within Sage.
The generator matrix here in the text has columns that are codewords, and linear combinations of the columns (the column space of the matrix) are codewords. In Sage the generator matrix has rows that are codewords and the row space of the matrix is the code. So here is another place where we need to mentally translate between a choice made in the text and a choice made by the Sage developers.
Here is a partial test that these two matrices are correct, exercising Lemma 8.27. Notice that we need to use the transpose of the generator matrix, for reasons described above.
Note that the parity-check may not be canonical and the generator matrix may not be standard. Sage can produce a generator matrix that has a set of columns that forms an identity matrix, though no guarantee is made that these columns are the first columns. (Columns, not rows.) Such a matrix is said to be systematic, and the Sage method is .systematic_generator_matrix().
Subsection Decoding with a Linear Code
We can decode received messages originating from a linear code. Suppose we receive the length binary vector r.
We can recognize that one or more errors has occured, since r is not in the code, as the next computation does not yield the zero vector.
A linear code has a .decode method. You may choose from several different algorithms, while the Hamming codes have their own custom algorithm. The default algorithm is syndrome decoding.
So if we are willing to assume that only one error occured (which we might, if the probability of an indivual entry of the vector being in error is very low), then we see that an error occured in the third position.
Remember that it could happen that there was more than just one error. For example, suppose the message was the same as before and errors occurred in the third, fifth and sixth locations.
It then appears that we have received a codeword, so we assume no errors at all, and decode incorrectly.
