Making Error Correcting code with FindIndependentVertexSet

Suppose you want to transmit information over a lossy channel. Your channel flips some bits at random and you want to choose your code-words so that you can recover the original codeword with high probability.

One approach is to pick a set of codewords of length n so that the Hamming distance between any two of them is at least d. This means that if the number of errors is less than (d-1)/2, you can recover the original word by picking code word closest in Hamming distance to the received word.

For example, for 3 bits and d=2, the code would be

100
010
001
111

Essentially when d=2, this is equivalent to finding a set of non-adjacent vertices of hypercube in n dimensions. For instance, code above can be visually represented as follows



For n=4 we can visualize it as follows


Essentially the problem is one of independent set, we construct a graph where vertices correspond to codewords and are connected if and only if hamming distance between them is 1.

Two graphs above correspond to "CubicalGraph" and "TesseractGraph" in GraphData, but if you want to recover the codewords, you want to control the ordering of vertices and construct the graph yourself. Getting the code is straightforward from the independent vertex set

words = Tuples[{0, 1}, 4];
distMat = Outer[HammingDistance, words, words, 1];
g = AdjacencyGraph[Map[Boole[# == 1] &, distMat, {2}]];
verts = FindIndependentVertexSet[g];
code = words[[verts]]

The result gives you a set of code-words over n-bits that are at least 2 bit flips apart from one another.

Now suppose we want to make our code more robust against errors. We construct graph as before, but augment it with the command "GraphPower[g,d-1]" to create a graph where vertices in an independent set are at least d steps apart. For n=6,d=2, VertexIndependentSet finds a code consisting of 8 codewords, which is the best possible.

It is known that for n=7,d=3 there's a code consisting of 16 codewords, although this problem seems to be too difficult to solve using version of VertexIndependentSet that ships with version 8.0

I'm experimenting with a message passing algorithm to solve this problem in the independent vertex set formulation, I'll post an update if it turns out better than the built-in

Notebook