5
$\begingroup$

I want as many 80-bits words as possible with the constraint that the hamming distance between any couple of words is exactly 40. How many can I generate? Is there a generic formula telling me how many n-bits words I can generate with the constraint that any couple of words is at hamming distance exactly n/2? Any general algorithm to generate them?

For 2 bits codewords, "00, 01" are at HD=1. For 4-bits codewords, "0000, 0011, 0101, 1001" are all at HD=2. And then?

Thank You,

JMC

$\endgroup$
3
  • $\begingroup$ Suppose you have such a code. If you add one of words to each of the others, you have a constant-weight code. Now see the wikipedia page on constant-weight codes. (There's no simple formula for the size, nor is there an algorithm to generate them.) $\endgroup$ Sep 9, 2011 at 15:10
  • $\begingroup$ Thank you for your answer. But doesn't a constant weight code imply that the hamming distance between any pair of words is at least d? This does not suit me because I need it to be exactly n/2. $\endgroup$ Sep 9, 2011 at 15:27
  • $\begingroup$ Oops. You're right. $\endgroup$ Sep 9, 2011 at 16:06

1 Answer 1

11
$\begingroup$

There cannot be more than $n$ such words. To see this, consider the words as elements of $\{-1,1\}^n$. If two such words have Hamming distance $\Delta$, then their scalar product in $\mathbb R^n$ is $n-2\Delta$. In particular, if they all have distance $n/2$, then they are orthogonal, hence linearly independent, hence there are at most $n$ many.

An array of $n$ $\pm 1$ vectors such that every two are orthogonal is called a Hadamard matrix. Such a matrix does not exist unless n=1,2 or n is a multiple of 4. The famous Hadamard conjecture asserts that when $n$ is a multiple of 4, there exists a Hadamard matric of order $n$, This is known to be true in many cases and, in particular, when $n<668$.

An important special case is when $n=2^k$ is a power of two. Then you can construct a set of $n$ such words as follows. We identify bits with elements of the field $\mathbb F_2$, and coordinates $x< n$ with elements of $\mathbb F_2^k$, and thus consider words as functions $f\colon\mathbb F_2^k\to\mathbb F_2$. For any $x,y\in\mathbb F_2^k$, let $f_x(y)=\langle x,y\rangle:=\bigoplus_{i< k}x_iy_i$, where $\oplus$ denotes addition in $\mathbb F_2$ (i.e., modulo $2$). Then $\{f_x:x\in\mathbb F_2^k\}$ is a set of words of size $2^k$, and pairwise Hamming distance $2^{k-1}$, as for any distinct $x,x'$, we have $f_x(y)=f_{x'}(y)$ iff $\langle x\oplus x',y\rangle=0$, which holds for exactly one half of all $y$’s.

$\endgroup$
5
  • $\begingroup$ I should also mention that the construction for $n=2^k$ is know as the Walsh–Hadamard code en.wikipedia.org/wiki/Walsh%E2%80%93Hadamard_code . $\endgroup$ Sep 9, 2011 at 15:53
  • 2
    $\begingroup$ Indeed it is a famous conjecture that such codes exist whenever n =0 (mod 4). It is easy to see that this is necessary. See en.wikipedia.org/wiki/Hadamard_matrix $\endgroup$
    – Gil Kalai
    Sep 9, 2011 at 17:44
  • $\begingroup$ That’s a good point. Moreover, the conjecture holds for Jean-Michel’s $n=80$: one can take the tensor product of an order 4 Hadamard matrix as above with an order $2(9+1)$ Paley construction II as explained in en.wikipedia.org/wiki/Paley_construction . So the answer to the original question is 80. $\endgroup$ Sep 9, 2011 at 18:16
  • $\begingroup$ @Gil: Thanks for editing it in the answer. $\endgroup$ Sep 12, 2011 at 15:52
  • $\begingroup$ Actually, if you don't require constant Hamming distance, you can double the size of the Walsh-Hadamard code by allowing the binary complement of each codeword to be also a codeword. $\endgroup$
    – kodlu
    May 20, 2015 at 7:23

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.