1
$\begingroup$

I want to generate a code on n bits for k different inputs that I want to classify. The main requirement of this code is the error-correcting criteria: that the minimum pairwise distance between any two encodings of different inputs is maximized. I don't need it to be exact - approximate will do, and ease of use and speed of computational implementation is a priority too.

In general, n will be in the hundreds, k in the dozens.

Also, is there a reasonably tight bound on the minimum hamming distance between k different n-bit binary encodings?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

My answer that I gave on StackOverflow:

The problem of finding the exact best error-correcting code for given parameters is very hard, even approximately best codes are hard. On top of that, some codes don't have any decent decoding algorithms, while for others the decoding problem is quite tricky.

However, you're asking about a particular range of parameters where n ≫ k, where if I understand correctly you want a k-dimensional code of length n. (So that k bits are encoded in n bits.) In this range, first, a random code is likely to have very good minimum distance. The only problem is that decoding is anywhere from impractical to intractible, and actually calculating the minimum distance is not that easy either.

Second, if you want an explicit code for the case n ≫ k, then you can do reasonably well with a BCH code with q=2. As the Wikipedia page explains, there is a good decoding algorithm for BCH codes.

Concerning upper bounds for the minimum Hamming distance, in the range n ≫ k you should start with the Hamming bound, also known as the volume bound or the sphere packing bound. The idea of the bound is simple and beautiful: If the minimum distance is t, then the code can correct errors up to distance floor((t-1)/2). If you can correct errors out to some radius, it means that the Hamming balls of that radius don't overlap. On the other hand, the total number of possible words is 2n, so if you divide that by the number of points in one Hamming ball (which in the binary case is a sum of binomial coefficients), you get an upper bound on the number of error-free code words. It is possible to beat this bound, but for large minimum distance it's not easy. In this regime it's a very good bound.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks - just to be clear though, I don't need to decode - codes will be stored in a lookup table. All that matters is maximizing minimum distance. I'll look into BCH, though they look sort of intimidating. $\endgroup$
    – DoubleJay
    Jul 4, 2010 at 19:58
  • 1
    $\begingroup$ If the code is small enough for a lookup table, then of course you can check the minimum distance even if it is a random code. On the other hand, you won't be able to decode a word with errors in it. Removing the errors is the hard part. $\endgroup$
    – Greg Kuperberg
    Jul 4, 2010 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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