Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 '11 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 '11 at 15:27
    
Oops. You're right. –  Chris Godsil Sep 9 '11 at 16:06

1 Answer 1

up vote 11 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.