Wednesday, 18 September 2013

Generating all n-bit strings whose hamming distance is n/2.

Generating all n-bit strings whose hamming distance is n/2.

I'm playing with some variant of Hadamard matrices. I want to generate all
n-bit binary strings which satisfy these requirements:
You can assume that n is a multiple of 4.
The first string is 0n.
Ë a string of all 0s.
The remaining strings are sorted in alphabetic order.
Ë 0 comes before 1.
Every two distinct n-bit strings have Hamming distance n/2.
Ë Two distinct n-bit strings agree in exactly n/2 positions and disagree
in exactly n/2 positions.
Due to the above condition, every string except for the first string must
have the same number of 0s and 1s.
Ë Every string other than the first string must have n/2 ones and n/2 zeros.
For example, this is the list that I want for when n=4.
0000
0011
0110
0101
You can easily see that every two distinct rows have hamming distance n/2
= 4/2 = 2 and the list satisfies all the other requirements as well.
Note that I want to generate all such strings. My algorithm may just
output three strings 0000, 0011, and 0101 before terminating. This list
satisfies all the requirements above but it misses 0110.
What would be a good way to generate such sets?
A python pseudo-code is preferred but any high-level description will do.
What is the maximum number of such strings for a given n?
For example, when n=4, the max number of such strings happen to be 4. I'm
wondering whether there can be any closed form solution for this upper
bound.
Thanks.

No comments:

Post a Comment