Coding Theory

Coding Theory is an interest of mine and I have used Magma many times for students to explore properties of codes, make conjectures, and then try to prove theorems. I’d like to give you an example of this.

Suppose you want to investigate the construction of codes using other objects in discrete mathematics. I’ve done this in the past, generating codes by incidence matrices. The idea is pretty straight-forward. You create some discrete object, such as a graph or a combinatorial design (in my case, I would use finite geometry to do this). Then you construct an incidence matrix from the object. For a graph, this might be the 01-matrix with rows labeled by vertices, columns by edge, for example, and 1/0 represents incidence/non-incidence. Now, use this matrix to generate a binary linear code and analyze the parameters of the code.

For example, Magma has a command which will generate the graph determined by a cube in any dimension. In the case of dimension 3:

> G := KCubeGraph(3);

Now, let’s use Magma to create the incidence matrix for this graph, change the coefficient ring to be GF(2) (right now, Magma thinks the 0s and 1s are integers), and then use the matrix to generate a code. Typically, researchers let the matrix be the parity-check (which is just a fancy name for the matrix whose rows generate the dual space). Codes generated by a sparse parity-check matrix are called LDPC (low-density parity-check) codes and are of interest for a variety of reasons.

> I := IncidenceMatrix(G);
> I2 := ChangeRing(I,GF(2));
> C := Dual(LinearCode(I2));

Now that we have the code, we can ask for its parameters. Notice that Magma will even give us a generator matrix:

> C;
[12, 5, 4] Linear Code over GF(2)
Generator matrix:
[1 0 1 0 1 0 0 0 0 1 1 1]
[0 1 1 0 0 0 1 0 0 1 0 0]
[0 0 0 1 1 0 0 1 0 0 1 0]
[0 0 0 0 0 1 1 1 0 0 0 1]
[0 0 0 0 0 0 0 0 1 1 1 1]

OK, so at this point we know that we can generate a [12, 5, 4] binary linear code from the 3-dimensional cube. But what if we bump it up a notch? If we start with a 4-dimensional cube, what does that code look like?  Let’s see:

> G := KCubeGraph(4);
> I := IncidenceMatrix(G);
> I2 := ChangeRing(I,GF(2));
> C := Dual(LinearCode(I2));
> C;
[32, 17] Linear Code over GF(2)
Generator matrix:

<snip>

> MinimumDistance(C);
4

Notice that Magma did not compute the minimum distance automatically for us. That’s because the minimum distance computation is actually an NP-hard problem and may take a while to compute for larger codes. If you want it, you have to ask for it explicitly (as I did above). Let’s also check the 5-dimensional cube-code:

> G := KCubeGraph(5);
> I := IncidenceMatrix(G);
> I2 := ChangeRing(I,GF(2));
> C := Dual(LinearCode(I2));
> Length(C);
80
> Dimension(C);
49
> MinimumDistance(C);
4

In summary, we have found three codes with the following properties.

Cube Dimension Length Dimension Min distance
3 12 5 4
4 32 17 4
5 80 49 4

 

Now comes the mathematics… is there a pattern? You might now conjecture a formula for the length, dimension and minimum distance. Looks like the minimum distance is 4 in every case. Can we prove that this is always true, regardless of the dimension of the original cube graph? Is there a formula for the length?  What about the dimension? I tell my students to start by figuring out what you’re trying to prove. Then go work on it!