Skip to main content
Clarified family vs single codes
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

By sphere packing arguments you can't do better in general than the Hamming bound $$ \# T \left(1+ \binom{n}{1}+ \cdots+ \binom{n}{r-1}\right)\leq 2^n, $$ or $$ \#T \#S_{r-1}(x)\leq 2^n, $$ in your notation. $t=r-1$ is the number of errors the code can correct.

Codes achieving the above are called perfect, there are only 4 of them in the binary alphabet case:

  • the full space with $t=0,$ admittedly trivial,
  • the $n$ odd length repetition codecodes consisting of the all zero and all one vectors with $t=(n-1)/2$, which exists for all positive odd $n$
  • the family of Hamming codes with $t=1$ and $n=2^m-1$, and
  • the binary Golay code of length $n=23$ and $t=3$ which is related to many combinatorial objects.

There is also a lower bound called Gilbert Varshamov which asserts the existence of sets $T$ with size at least equal to the bound given $n$ and $r$.

Nice coding theory texts include those by MacWilliams and Sloane, Roman, Bierbrauer, Roth.

By sphere packing arguments you can't do better in general than the Hamming bound $$ \# T \left(1+ \binom{n}{1}+ \cdots+ \binom{n}{r-1}\right)\leq 2^n, $$ or $$ \#T \#S_{r-1}(x)\leq 2^n, $$ in your notation. $t=r-1$ is the number of errors the code can correct.

Codes achieving the above are called perfect, there are only 4 of them in the binary alphabet case:

  • the full space with $t=0,$ admittedly trivial,
  • the $n$ odd length repetition code consisting of the all zero and all one vectors with $t=(n-1)/2$
  • the family of Hamming codes with $t=1$ and $n=2^m-1$, and
  • the binary Golay code of length $n=23$ and $t=3$ which is related to many combinatorial objects.

There is also a lower bound called Gilbert Varshamov which asserts the existence of sets $T$ with size at least equal to the bound given $n$ and $r$.

Nice coding theory texts include those by MacWilliams and Sloane, Roman, Bierbrauer, Roth.

By sphere packing arguments you can't do better in general than the Hamming bound $$ \# T \left(1+ \binom{n}{1}+ \cdots+ \binom{n}{r-1}\right)\leq 2^n, $$ or $$ \#T \#S_{r-1}(x)\leq 2^n, $$ in your notation. $t=r-1$ is the number of errors the code can correct.

Codes achieving the above are called perfect, there are only 4 of them in the binary alphabet case:

  • the full space with $t=0,$ admittedly trivial,
  • the $n$ length repetition codes consisting of the all zero and all one vectors with $t=(n-1)/2$, which exists for all positive odd $n$
  • the family of Hamming codes with $t=1$ and $n=2^m-1$, and
  • the binary Golay code of length $n=23$ and $t=3$ which is related to many combinatorial objects.

There is also a lower bound called Gilbert Varshamov which asserts the existence of sets $T$ with size at least equal to the bound given $n$ and $r$.

Nice coding theory texts include those by MacWilliams and Sloane, Roman, Bierbrauer, Roth.

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

By sphere packing arguments you can't do better in general than the Hamming bound $$ \# T \left(1+ \binom{n}{1}+ \cdots+ \binom{n}{r-1}\right)\leq 2^n, $$ or $$ \#T \#S_{r-1}(x)\leq 2^n, $$ in your notation. $t=r-1$ is the number of errors the code can correct.

Codes achieving the above are called perfect, there are only 4 of them in the binary alphabet case:

  • the full space with $t=0,$ admittedly trivial,
  • the $n$ odd length repetition code consisting of the all zero and all one vectors with $t=(n-1)/2$
  • the family of Hamming codes with $t=1$ and $n=2^m-1$, and
  • the binary Golay code of length $n=23$ and $t=3$ which is related to many combinatorial objects.

There is also a lower bound called Gilbert Varshamov which asserts the existence of sets $T$ with size at least equal to the bound given $n$ and $r$.

Nice coding theory texts include those by MacWilliams and Sloane, Roman, Bierbrauer, Roth.