4
$\begingroup$

Background

I've just learned a bit about linear codes. Hamming codes have the property that up to one bit in a block can be corrupted, and we still communicate the message correctly. This is done by making all the non-zero vectors in $\newcommand\ZZ{\mathbb Z}(\ZZ/2)^k$ columns in a $k\times (2^k-1)$ matrix $H$. Valid transmissions are vectors $t$ of length $2^k-1$ so that $Ht=0$. If you receive an invalid transmission $\tilde t$, then look for the column of $H$ which is equal to $H\tilde t$, flip the corresponding bit of $\tilde t$, and you have the unique valid transmission which differs from $\tilde t$ in one bit.

Note: the number of data bits that are transmitted is the dimension of the kernel of $H$, $2^k-1-k$. That is, for each block of $2^k-1$ bits sent, $k$ of them are used for purposes of correcting errors, so they can't be used for transmitting information.


General question: is there a similarly elegant scheme for correcting up to two corrupted bits in a block?

Here's what I've done so far. I'd like to find an $m\times n$ matrix $H$ over $\ZZ/2$ and declare that valid transmissions are vectors $t$ of length $n$ so that $Ht=0$. Moreover, I'd like to have the property that any non-zero vector of length $m$ (think of this as $H\tilde t$ for some invalid transmission $\tilde t$) is uniquely expressible as either one of the columns of $H$, or the sum of two of the columns of $H$. Uniqueness is important because that's what tells me which bit (or which two bits) of $\tilde t$ needs to be corrected.

This is clearly only possible if $n + \binom{n}{2} = \binom{n+1}{2} = 2^m -1$, so I set out looking for triangle numbers that are one less than a power of two. $1$ and $3$ have $n=m$ (so $\dim\ker H=0$, so no data can be sent), so the first one of interest is $15 = \binom{5+1}{2} = 2^4-1$. Here we can take $$H = \pmatrix{1&0&0&0&1\\ 0&1&0&0&1\\ 0&0&1&0&1\\ 0&0&0&1&1},$$ which works, but is extremely boring, since the corresponding code sends $5-4=1$ actual bits of data for every $5$ bits transmitted by simply sending each bit five times in a row and decoding by majority vote in each block of five.

The only other case is $4095 = \binom{90+1}{2} = 2^{12}-1$, which is much more interesting. If such an $H$ exists, we get a scheme for transmitting $90-12=78$ bits of data in blocks of size $90$, which is resistant to corruption of any two bits in a block. My specific question is whether such an $H$ does in fact exist. In case it's catchier, we can interpret the columns of $H$ as $12$-bit integers to get the following question:

Specific question: Does there exist a set $S\subseteq \{1,2,3\dots, 4095\}$ of size $90$ so that $S\cup (S\text{ xor }S) = \{1,2,3\dots, 4095\}$?

Bonus question: why is this the only other case? I've checked that $2^m-1$ isn't a triangle number for $12<m\le 6000$, but I don't see a reason there couldn't be any more.

$\endgroup$
  • 1
    $\begingroup$ If I am translating correctly from one problem to another, "This suggests the existence of a perfect, double-error-correcting (90,78) code, but it was proved by Golay and Zaremba that no such code exists." A proof of Tompkins is more elegant (namely 3 does not divide 88). Did a search for "90 78 error correcting" to find this, see the book (page 86 or so) books.google.com/books?isbn=0883850370 $\endgroup$ – v08ltu Jul 6 '13 at 2:00
4
$\begingroup$

Here is the Tompkins proof, from page 86 of From Error-Correcting Codes Through Sphere Packings to Simple Groups, Volume 21 By Thomas M. Thompson http://books.google.com/books?isbn=0883850370

Assume such a code exists, w/o loss of generality it contains 0. Each 90-tuple with exactly three 1s must be in a Hamming sphere of radius 2 centered on a codeword which has exactly five 1s, three of which are in the same coordinates as those of the 90-tuple. Consider in particular the set of eighty-eight 90-tuples with 1's in the first two coordinates and one 1 elsewhere. Each member of this set must be within two units of a unique codeword. Each such codeword has 1s in the first two positions and three 1s elsewhere. Two such codewords cannot have 1s in the same coordinate positions other than the first two, otherwise some 90-tuple in the above set would be within two units of two codewords. This means the eighty-eight coordinate positions other than the first two must be divided into equinumerous disjoint sets of three. Since three does not divide eighty-eight, this is impossible.

$\endgroup$
  • 1
    $\begingroup$ That's a nice argument, and it even excludes the existence of any two error-correcting code with this length and size, not only of linear ones. $\endgroup$ – user9072 Jul 6 '13 at 13:20
4
$\begingroup$

For your general question you might be interested in BCH codes. The construction is nice, from an algebraic point of view, and you can have two-error correction and also more general things.

For your specific question no there is no binary linear code of block length $90$ and size $78$ that corrects $2$ errors. The optimal minimal distance of such a code is $4$, and for correcting two erros one needs minimal distance $5$.

To find such information http://www.codetables.de/ is a useful resource. You can give $n=90$ and $k=78$ and will get the minimal distance (you can also get more information there than only that the minimal distance is $4$).

For the bonus question: $0,1,3,15,4095$ are indeed all triangular numbers of the form $2^m-1$. This was conjectured by Ramanujan and proved by Nagell, thus also called Ramanujan–Nagell numbers see http://oeis.org/A076046 and Ramanujan–Nagell equation.

Note that the Ramanujan–Nagell equation is $2^n - 7 = x^2$, and its solutions are $n=3,4,5,7,15$. A short argument shows that from this one can also solve the above problem, roughly multiplying by $8$ and adding $1$ the triangular number becomes an odd square while $2^n - 1$ becomes $2^{n+3} -7$ (for details see the links above).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.