Skip to main content

Exercises 8.10 Sage Exercises

1.

Create the (binary) Golay code with the codes.GolayCode() constructor. Read the documentation to be sure you build the binary version (not ternary), and do not build the extended version (which is the default).

  1. Use Sage methods to compute the length, dimension and minimum distance of the code.

  2. How many errors can this code detect? How many can it correct?

  3. Find a nonzero codeword and introduce three errors by adding a vector with three 1's (your choice) to create a received message. Show that the message is decoded properly.

  4. Recycle your choices from the previous part, but now add one more error. Does the new received message get decoded properly?

2.

One technique for improving the characteristics of a code is to add an overall parity-check bit, much like the lone parity-check bit of the ASCII code described in Example 8.3. Such codes are referred to as the extended version of the original.

  1. Construct the (binary) Golay code and obtain the parity-check matrix. Use Sage commands to enlarge this matrix to create a new parity check matrix that has an additional overall parity-check bit. You may find the matrix methods .augment() and .stack() useful, as well as the constructors zero_vector() and ones_matrix()(remembering that we specify the binary entries as being from the field GF(2).)

    Create the extended code by supplying your enlarged parity-check matrix to the codes.from_parity_check_matrix() constructor and compute the length, dimension and minimum distance of the extended code.

  2. How are the properties of this new code better? At what cost?

  3. Now create the extended (binary) Golay code with the Sage constructor codes.GolayCode() and the correct keyword to obtain the extended version. With luck, the sorted lists of your codewords and Sage's codewords will be equal. If not, the linear code method .is_permutation_equivalent() should return True to indicate that your code and Sage's are just rearrangements of each other.

3.

Note: This problem is on holiday (as of Sage 6.7), while some buggy Sage code for the minimum distance of a Hamming code gets sorted out. The r = 2 case produces an error message and for r > 5 the computation of the minimum distance has become intolerably slow. So it is a bit harder to make a reasonable conjecture from just \(3\) cases.

The dual of an \((n,k)\) block code is formed as all the set of all binary vectors which are orthogonal to every vector of the original code. Exercise 8.6.25 describes this construction and asks about some of its properties.

You can construct the dual of a code in Sage with the .dual_code() method. Construct the binary Hamming codes, and their duals, with the parameter r ranging from 2 to 5, inclusive. Build a table with six columns (perhaps employing the html.table() function) that lists \(r\text{,}\) the length of the codes, the dimensions of the original and the dual, and the minimum distances of the orginal and the dual.

Conjecture formulas for the dimension and minimum distance of the dual of the Hamming code as expressions in the parameter \(r\text{.}\)

4.

A code with minimum distance \(d\) is called perfect if every possible vector is within Hamming distance \((d-1)/2\) of some codeword. If we expand our notion of geometry to account for the Hamming distance as the metric, then we can speak of a sphere of radius \(r\) around a vector (or codeword. For a code of length \(n\text{,}\) such a sphere will contain

\begin{equation*} 1 + {n\choose 1} + {n\choose 2} + \cdots + {n\choose r} \end{equation*}

vectors within in it. For a perfect code, the spheres of radius \(d\) centered at the codewords of the code will exactly partition the entire set of all possible vectors. (This is the connection that means that coding theory meshes with sphere packing problems.)

A consequence of a code of dimension \(k\) being perfect is that

\begin{equation*} 2^k\left({n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose \frac{d-1}{2}}\right) = 2^n \end{equation*}

Conversely, if a code has minimum distance \(d\) and the condition above is true, then the code is perfect.

Write a Python function, named is_perfect() which accepts a linear code as input and returns True or False. Demonstrate your function by checking that the (binary) Golay code is perfect, and then use a loop to verify that the (binary) Hamming codes are perfect for all lengths below \(32\text{.}\)