What is known about computing all binary error correcting codes of given parameters?

Question

Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.

Are there any sources about using algorithms to find all given codes of certain parameters? I suspect that there are some ways to reduce the search space or some other clever techniques for finding all codes that are more subtle than a brute force search of all possible $M$ subsets of $\mathbb{F}^n_2$ and then computing the Hamming distance for every such subset. Certainly I would still expect that such a problem cannot be solved in polynomial time. I could not however, find any good sources on this material and was wondering if anyone knew of any. Partial answers or computational results and methods related to special classes of binary codes are welcome as well.

Answer 1

People are generally only interested in "good" codes. Which means maximum minimum distance $d$ for given $n,M$ or minimum length for given $M,d$ etc. Let $A(n,d)$ be the maximum $M$ for which an $(n,M,d)$ code exists.

Even for such codes the computational complexity of the problem is overwhelming. There are too many bad codes (if $d$ is small relative to $(n,M)$ as determined by bounds such as Hamming, Plotkin, Gilbert-Varshamov the search space is way too big).

There is the idea of code equivalence under the automorphism group of the code, which is used to reduce search complexity. At a very basic level if you find a code with certain parameters, and apply a permutation to the coordinates, this gives another code with the same paramaters. If the code has algebraic structure, you can do more.

The site http://www.codetables.de/ maintained by Markus Grassl has some tables of good codes, for example, and links to other tables. If you restrict to, for example, self-dual codes or codes with only two nonzero weights, etc. you can do more.

The tables by Litsyn, Rains and Sloane at http://www.eng.tau.ac.il/~litsyn/tableand/index.html of lower bounds on $A(n,d)$ may not have been updated in a long time. But a snippet from that site gives an idea about how hard the problem is.

Memo to algorithms specialists: This file contains a large number of clique-finding problems. Construct the graph whose vertices represent binary strings of length $n.$ Join two vertices by an edge if and only if the Hamming distance bewteen the strings is at least $d.$ Then what we are interested in is the quantity $A(n,d),$ the size of the largest clique in this graph. This file contains a large number of lower bounds on this clique size. If you can improve any of these entries or establish the optimality of any entries that we don't already know are optimal (these are indicated by a period after the number) please let us know (send us the clique too!).

Edit: I haven't used it for this purpose but the Magma package http://magma.maths.usyd.edu.au/calc/can do computations related to automorphism groups of codes. See here for details. There is a publicly accessible calculator at the first link I gave, but the memory and computation time allowed is limited. I am less familiar with Pari/GP but they may have a similar functionality.