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
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.
