## binary code with constant hamming distance

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

-
 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.) – Chris Godsil Sep 9 2011 at 15:10 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. – Jean-Michel Sep 9 2011 at 15:27 Oops. You're right. – Chris Godsil Sep 9 2011 at 16:06

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.

-
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 . – Emil Jeřábek Sep 9 2011 at 15:53
Thank you for the very detailed answer – Jean-Michel Sep 9 2011 at 15:58
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 – Gil Kalai Sep 9 2011 at 17:44
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. – Emil Jeřábek Sep 9 2011 at 18:16
@Gil: Thanks for editing it in the answer. – Emil Jeřábek Sep 12 2011 at 15:52