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,


  • $\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$ – Chris Godsil Sep 9 '11 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$ – Jean-Michel Sep 9 '11 at 15:27
  • $\begingroup$ Oops. You're right. $\endgroup$ – Chris Godsil Sep 9 '11 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.

| cite | improve this answer | |
  • $\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$ – Emil Jeřábek Sep 9 '11 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 '11 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$ – Emil Jeřábek Sep 9 '11 at 18:16
  • $\begingroup$ @Gil: Thanks for editing it in the answer. $\endgroup$ – Emil Jeřábek Sep 12 '11 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 '15 at 7:23

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.