I'm trying to find a low distortion embedding of the trivial metric space into hamming space.

It seems this should be doable by using a large set of low dimensional vectors, with approximately equal pairwise distance.

My question is if it makes sense to expect error correcting codes to have this property?

Usually when designing error correcting codes, we are interested in finding the highest achievable rate, given a minimum distance between points. A similar question is to consider, instead of the minimum distance, the ratio between the maximum and minimum distance, $\rho=max/min$. Given $\rho$, what codes should one consider for maximizing the rate?

I tried to count the distances in some of the codes from this list of optimal binary codes:

  • The $(7,2^3,4)$ code has all distances equal to four, so $\rho=1$.
  • The $(8,2^4,4)$ code has $112$ pairs of distance $4$ and $8$ of distance $8$, so it has $\rho=2$.
  • The $(9,40,3)$ code has maximum distance $8$, so $\rho=8/3$.
  • The $(24,2^{12},8)$ golay code has maximum distance $24$, so $\rho=3$.

The two later codes are nearly as bad as possible. Are there any codes for which I shouldn't expect this to be the case? If not, can I at least say something about the distribution of distances being fairly concentrated?

  • $\begingroup$ lowest $\mapsto$ highest $\:$ ? $\;\;\;\;$ $\endgroup$ – user6973 Aug 28 '15 at 1:35
  • $\begingroup$ Ah yes, that was a typo. $\endgroup$ – Thomas Ahle Aug 28 '15 at 7:59

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.

To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the relative distance between codewords is always between $0.5 - \epsilon$ and $0.5 + \epsilon$.

One particular construction of such sets will give you a code whose dimension is linear in its block length. It is mentioned here: http://www.wisdom.weizmann.ac.il/~benaroya/SmallBiasNew.pdf

Basically, the idea is to take AG codes of constant rate and relative distance close to $1$, and concatenating them with the Hadamard code.

| cite | improve this answer | |
  • $\begingroup$ Interesting, I haven't heard of those before. However it seems they are all about derandomization. Does that mean we can do better if we allow randomization? $\endgroup$ – Thomas Ahle Sep 1 '15 at 14:34
  • 2
    $\begingroup$ We can do better if we allow randomness, in the same sense that a random code is better than our best deterministic constructions. $\endgroup$ – Or Meir Sep 1 '15 at 14:44
  • $\begingroup$ Can we be smarter with randomization that just picking uniformely random vectors? $\endgroup$ – Thomas Ahle Sep 1 '15 at 15:06
  • 1
    $\begingroup$ Not as far as I know. $\endgroup$ – Or Meir Sep 1 '15 at 19:16

Hadamard code [Sylvester Hadamard Matrices] has length $2^n$, $2^n$ codewords (if you take only the so called linear codewords but not their opposites) and minimum distance $2^{n-1}.$

Simplex code has similar parameters and is constant distance.

Justesen codes are a concatenated construction that give fixed distance.

There are codes with few distances as well, e.g., the Golay code.

| cite | improve this answer | |
  • $\begingroup$ Hadamard and Simplex are hardly "low dimension", and the Golay code is fixed size (?), but the Justesen code looks very interesting. Thanks a lot! Do I understand correctly that it is binary, equal pairwise distance and only gives a linear increase in dimension? That seems nearly too good to be true.. $\endgroup$ – Thomas Ahle Aug 28 '15 at 8:56
  • $\begingroup$ I fixed a typo. Regarding the first two codes, their dimension (i.e., logarithm of the number of codewords) is logarithmic in their length. $\endgroup$ – kodlu Aug 28 '15 at 9:06
  • $\begingroup$ But is it correct, as Wikipedia says, that if I have message length $k$ and take block length like $2k$ then with Justesen I get positive constant relative distance? So an embedding of the complete graph into hamming space with no distortion at all? (Sorry, I got tricked by some of the definitions before, and just want to be sure I understand it correctly) $\endgroup$ – Thomas Ahle Aug 28 '15 at 10:10
  • 1
    $\begingroup$ Have a look at cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes6.pdf (last section) and cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes7.pdf where concatenated coding is explained. Each codeword in the inner code is mapped to a code symbol in the outer code, so the outer code alphabet is GF(2^m) or if you like GF(2)^m if the inner code alphabet was GF(2). $\endgroup$ – kodlu Aug 28 '15 at 11:36
  • $\begingroup$ In the notes, as well as on Wikipedia, all that is proved are lower bounds on the distance. I don't see any upper bounds anywhere, shouldn't I expect that? $\endgroup$ – Thomas Ahle Aug 28 '15 at 14:19

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.