Skip to main content
added 509 characters in body
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

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.

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!).

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.

Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

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!).