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

<p>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$.</p>

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

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

CC BY-SA 3.0
2015-09-01T14:34:46.407Z
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?
Thomas Ahle
CC BY-SA 3.0
2015-09-01T14:44:26.960Z
We can do better if we allow randomness, in the same sense that a random code is better than our best deterministic constructions.
Or Meir
CC BY-SA 3.0
2015-09-01T15:06:41.603Z
Can we be smarter with randomization that just picking uniformely random vectors?
Thomas Ahle
CC BY-SA 3.0
2015-09-01T19:16:34.493Z
Not as far as I know.
Or Meir
CC BY-SA 3.0
2015-09-01T11:02:13.387Z
2015-09-01T11:08:01.297Z
2015-09-01T11:08:01.297Z
Or Meir
<p>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}.$</p>

<p>Simplex code has similar parameters and is constant distance.</p>

<p>Justesen codes are a concatenated construction that give fixed distance.</p>

<p>There are codes with few distances as well, e.g., the Golay code.</p>

CC BY-SA 3.0
2015-08-28T08:56:32.220Z
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..
Thomas Ahle
CC BY-SA 3.0
2015-08-28T09:06:15.497Z
I fixed a typo. Regarding the first two codes, their dimension (i.e., logarithm of the number of codewords) is logarithmic in their length.
kodlu
CC BY-SA 3.0
2015-08-28T10:10:23.940Z
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)
Thomas Ahle
CC BY-SA 3.0
2015-08-28T11:36:16.247Z
Have a look at  http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes6.pdf (last section) and http://www.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).
kodlu
CC BY-SA 3.0
2015-08-28T14:19:47.603Z
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?
Thomas Ahle
CC BY-SA 3.0
2015-08-28T15:09:30.330Z
I'm starting to think Justesen codes have "constant relative distance" simply because it is $\Omega(1)$ and doesn't decrease like 1/logn or so. It seems like it doesn't actually have anything to do with the distances being equal..
Thomas Ahle
CC BY-SA 3.0
2015-08-28T08:33:10.927Z
2015-08-28T09:05:13.420Z
2015-08-28T09:05:13.420Z
kodlu
<p>I'm trying to find a low distortion embedding of the trivial metric space into hamming space.</p>

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

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

<p>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?</p>

<p>I tried to count the distances in some of the codes from <a href="http://koti.kapsi.fi/pottonen/codes/" rel="nofollow">this list of optimal binary codes</a>:</p>

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

<p>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?</p>

CC BY-SA 3.0
2015-08-28T07:59:06.617Z
Ah yes, that was a typo.
Thomas Ahle
<graph-theory><coding-theory><metrics><embeddings><metric-spaces>
Are there Similar Distance Binary Error Correcting Codes?
Thomas Ahle
# Are there Similar Distance Binary Error Correcting Codes?

(Asked by: username_0 on 2015-08-28)

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](http://koti.kapsi.fi/pottonen/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?

**Tags:** graph-theory, coding-theory, metrics, embeddings, metric-spaces
> **Comments:**
> **username_0**: Ah yes, that was a typo.  

---

## 2 answers

### Answer by username_1 on 2015-09-01. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: We can do better if we allow randomness, in the same sense that a random code is better than our best deterministic constructions.  
> **username_0**: Can we be smarter with randomization that just picking uniformely random vectors?  
> **username_1**: Not as far as I know.  

---

### Answer by username_2 on 2015-08-28. Score: 0

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.

> **Comments:**
> **username_0**: 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..  
> **username_2**: I fixed a typo. Regarding the first two codes, their dimension (i.e., logarithm of the number of codewords) is logarithmic in their length.  
> **username_0**: 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)  
> **username_2**: Have a look at  http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes6.pdf (last section) and http://www.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).  
> **username_0**: 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?  
> **username_0**: I'm starting to think Justesen codes have "constant relative distance" simply because it is $\Omega(1)$ and doesn't decrease like 1/logn or so. It seems like it doesn't actually have anything to do with the distances being equal..  

---

