4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ lowest $\mapsto$ highest $\:$ ? $\;\;\;\;$ $\endgroup$
    – user6973
    Commented Aug 28, 2015 at 1:35
  • $\begingroup$ Ah yes, that was a typo. $\endgroup$
    – Thomas Ahle
    Commented Aug 28, 2015 at 7:59

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Sep 1, 2015 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
    Commented Sep 1, 2015 at 14:44
  • $\begingroup$ Can we be smarter with randomization that just picking uniformely random vectors? $\endgroup$
    – Thomas Ahle
    Commented Sep 1, 2015 at 15:06
  • 1
    $\begingroup$ Not as far as I know. $\endgroup$
    – Or Meir
    Commented Sep 1, 2015 at 19:16
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Aug 28, 2015 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
    Commented Aug 28, 2015 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
    Commented Aug 28, 2015 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
    Commented Aug 28, 2015 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
    Commented Aug 28, 2015 at 14:19

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.