Hamming distance

[Niv]

I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Now there are 65536 possible 16 bit codes, but what is the maximal
number of codes with 5 bit differences; I'm assuming, possibly
incorrectly, it'll vary depending on the seed code used.

i.e. "000000000000000" could be used as seed, then next code could be
"0000000000011111" etc etc.

I could perhaps write a programme to generate a sequence of
incrementing code, testing for 5 bit differences against all previously
generated codes, and counting how many I get, then loop back and
increment the start value.

This seems like a fairly useful algorithm; length N bits, M bit
differences, maximal sequence length to be found.

Has anyone got a pointer to somethingalready done please to save me
some time.

(I guess it fairly simple to write a process to fill arrays with codes
of 5 bit diffs, count the number of codes and then increment the seed
and see if more codes are generated & then update the filled array if
so.

 

[Brian Drummond]

On 19 Jan 2006 07:47:16 -0800, "Niv" <kev.parsons@mbda.co.uk> wrote:

I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Now there are 65536 possible 16 bit codes, but what is the maximal
number of codes with 5 bit differences; I'm assuming, possibly
incorrectly, it'll vary depending on the seed code used.

i.e. "000000000000000" could be used as seed, then next code could be
"0000000000011111" etc etc.

Since there are only 2^16 codes to test, I would use a sieve, like
"Sieve of Eratosthenes" but testing for Hamming distance instead of
primeness.

Start by testing (and eliminating) every number for distance against
X"0000". Then test every remaining number for distance against the
lowest number which remains in the sieve. And so on.
Two nested loops, but the outer loops get faster as the sieve gets
sparser.

- Brian

 

[Ben Jones]

"Niv" <kev.parsons@mbda.co.uk> wrote in message
news:1137685636.583316.300160@g47g2000cwa.googlegroups.com...

I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Now there are 65536 possible 16 bit codes, but what is the maximal
number of codes with 5 bit differences; I'm assuming, possibly
incorrectly, it'll vary depending on the seed code used.

Your assumption is indeed incorrect. The seed code is irrelevant, because
the code is linear.

To see why:

The Hamming distance between two words is the number of bits in which those
words differ. The "difference" function is just logical XOR, e.g.

01001
xor 11010
-------
10011

Those two words differ in bits 0, 1 and 4. So bitcount(A xor B) gives you
the Hamming distance.

Now repeat the calculation above, but first flip bit 0 in both words:

01000
xor 11011
-------
10011

Same answer. If you do the same flip(s) in both words, they will be "just as
different" as they were before you flipped any bits, because the flips
cancel out. It doesn't matter how many bits you flip or where they are, the
result is the same. (Note that flipping arbitrary bits is exactly the same
as XORing with an arbitrary word.)

What does this means for you? Say you have a code set that was based on the
seed code of "0100101001011101". This set is exactly equivalent to a set
based on the seed code of "0000000000000000". All you have to do to obtain
this set is XOR every code word with "0100101001011101". Now, since every
code set can be reduced to one containing the all-zero code word, they must
all be the *same* set. So, you only need to invesetigate starting from
all-zeroes, and you are still guaranteed to find the optimum solution.

Hope that helps.

Cheers,

-Ben-

 

[Eric Smith]

Niv wrote:

I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Brian Drummond wrote:

Since there are only 2^16 codes to test, I would use a sieve, like
"Sieve of Eratosthenes" but testing for Hamming distance instead of
primeness.

As it happens, I have a C program that does that. I dusted it off and put
it on my web site:
http://www.brouhaha.com/~eric/software/hamming/

In addition to the source code, there's a file giving the 256 16-bit
codes with a minimum distance of 5. Thus this code could be used to
detect all three-bit errors in eight bits of data, and correct all
single- and two-bit errors.

 

[Kai Harrekilde-Petersen]

Eric Smith <eric@brouhaha.com> writes:

Niv wrote:
I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Brian Drummond wrote:
Since there are only 2^16 codes to test, I would use a sieve, like
"Sieve of Eratosthenes" but testing for Hamming distance instead of
primeness.

As it happens, I have a C program that does that. I dusted it off and put
it on my web site:
http://www.brouhaha.com/~eric/software/hamming/

In addition to the source code, there's a file giving the 256 16-bit
codes with a minimum distance of 5. Thus this code could be used to
detect all three-bit errors in eight bits of data, and correct all

Shouldn't that be 4-bit errors? As I recall d_min > t+1 for detection,
and d_min > 2t+1 for corrections.

single- and two-bit errors.

Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

 

[Eric Smith]

Niv wrote:

I have to generate some unique codes of 16 bits length, but each code
must be at least differnt by 5 bits from any other code.

Now there are 65536 possible 16 bit codes, but what is the maximal
number of codes with 5 bit differences;

Conjecture:

For an n-bit code (n >= 4) with minimum distance d (1 <= d < n/2),
if d is odd there are 2^(n+2-2*d) codes, and if d is even there
are 2^(n+3-2*d) codes.

 

[Niv]

Thanks Eric, I'll try & run your prog,or just the values provided.

Niv.

 

[Eric Smith]

I wrote:

In addition to the source code, there's a file giving the 256 16-bit
codes with a minimum distance of 5. Thus this code could be used to
detect all three-bit errors in eight bits of data, and correct all

Kai Harrekilde-Petersen wrote:

Shouldn't that be 4-bit errors?

Yes, my mistake.

As I recall d_min > t+1 for detection, and d_min > 2t+1 for corrections.

d_min > t for detection of up to t bits in error
d_min > 2t for correction of up to t bits in error

 

[Kai Harrekilde-Petersen]

Eric Smith <eric@brouhaha.com> writes:

I wrote:
In addition to the source code, there's a file giving the 256 16-bit
codes with a minimum distance of 5. Thus this code could be used to
detect all three-bit errors in eight bits of data, and correct all

Kai Harrekilde-Petersen wrote:
Shouldn't that be 4-bit errors?

Yes, my mistake.

As I recall d_min > t+1 for detection, and d_min > 2t+1 for corrections.

d_min > t for detection of up to t bits in error
d_min > 2t for correction of up to t bits in error

And now that was my mistake I should have written >= instead of >.


Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>