prob036: Fixed Length Error Correcting Codes

proposed by Alan Frisch, Chris Jefferson, and Ian Miguel
frisch@cs.york.ac.uk, caj@cs.york.ac.uk, ianm@cs.york.ac.uk

Modelling

The most obvious model for fixed length error correcting codes is to place them in a matrix where each row represents one of the elements of a code. The distance constraint can then be placed between all pairs of rows.

Clearly this will give us symmetry of the rows of the matrix, but many distance functions have much more symmetry. Both the Hamming and Lee distances have column symmetry in this matrix model as the definitions of distance between codes does not distiguish the columns. They also they allow value symmetry in each of the columns independantly. The value symetry group of the hamming distance is Sn. The value symmetry group of the Lee distance over a set of size 4 can be generated by (0123) and (13).

In the Lee distance as each column has independant value symmetry we can assume that without loss of generality the code we generate has the element which is a vector of zeroes. This does not remove all the value symmetry but removes a much.

We can also do this in the Hamming distance but it removes much less of the symmetry.