algcodes-sage.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section8.8Sage

¶

Sage has a full suite of linear codes and a variety of methods that may be used to investigate them.

SubsectionConstructing 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.

codes.

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{.}$

H = codes.HammingCode(GF(2), 3); H

SubsectionProperties of Linear Codes

We can examine the Hamming code we just built. First the dimension.

H.dimension()

The code is small enough that we can list all the codewords.

H.list()

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.

H.minimum_distance()

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.

C = H.parity_check_matrix(); C

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.

G = H.generator_matrix(); G

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.

C*G.transpose() == zero_matrix(3, 4)

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 , and the Sage method is .systematic_generator_matrix().

H.systematic_generator_matrix()

SubsectionDecoding with a Linear Code

We can decode received messages originating from a linear code. Suppose we receive the length $7$ binary vector r.

r = vector(GF(2), [1, 1, 1, 1, 0, 0, 1]); 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.

C*r

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.

H.decode_to_code(r)

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.

message = vector(GF(2), [1, 1, 0, 1, 0, 0, 1])
errors = vector(GF(2), [0, 0, 1, 0, 1, 1, 0])
received = message + errors
received

It then appears that we have received a codeword, so we assume no errors at all, and decode incorrectly.

H.decode_to_code(received) == message

H.decode_to_code(received) == received