Abstract Algebra: Theory and Applications

Subsection Constructing Linear Codes

The codes object can be used to get a concise listing of the available implemented codes. Type codes. and press the Tab key and most interfaces to Sage will give you a list. You can then use a question mark at the end of a method name to learn about the various parameters.

We will use the classic binary Hamming \((7,4)\) code as an illustration. “Binary” means we have vectors with just 0's and 1's, the \(7\) is the length and means the vectors have \(7\) coordinates, and the \(4\) is the dimension, meaning this code has \(2^4=16\) vectors comprising the code. The documentation assumes we know a few things from later in the course. We use GF(2) to specify that our code is binary — this will make more sense at the end of the course. A second parameter is r and we can see from the formulas in the documenation that setting r=3 will give length \(7\text{.}\)

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 \(d=3\text{,}\) 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 \(7\) 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.