Hamming distance - how to count the 1s?

[Felix Deichmann]

Hi.

I want to calculate the Hamming distance of two 8 bit wide numbers,
call them A and B.

I know that the first step would be:
(bit n of A) XOR (bit n of B) ; n in [0;7].
Or add instead of the XOR, ignoring the carry.

Then I have to count the number of 1s in the result to get the
distance. But how would "counting the 1s" be implemented (preferably
with basic logic like gates, encoders, flip-flops etc.)?

8-to-3 (priority) encoders don't seem to do the job (?).
And is there a way to avoid flip-flops without getting too complex?

Help would be greatly appreciated

Felix

 

[Active8]

Hi.

I want to calculate the Hamming distance of two 8 bit wide numbers,
call them A and B.

I take it you want the result in binary, not one of eight LEDs.

I know that the first step would be:
(bit n of A) XOR (bit n of B) ; n in [0;7].
Or add instead of the XOR, ignoring the carry.

XOR *is* add without carry. bits that are different output 1.

Then I have to count the number of 1s in the result to get the
distance. But how would "counting the 1s" be implemented (preferably
with basic logic like gates, encoders, flip-flops etc.)?

FYI here's your full adder

__
--+-----| X|
| | O|- sum
--|-+---|_R|
| |
| | __
o-|---| |
| |& |- carry
o---|__|

created by Andy´s ASCII-Circuit v1.22.310103 Beta www.tech-chat.de

8-to-3 (priority) encoders don't seem to do the job (?).

right, they encode the bit number (position) into binary.

And is there a way to avoid flip-flops without getting too complex?

draw up your options, add up the pennies, consider PCB real estate,
and compare to price of a MCU. don't forget, 2 bytes can be
multiplexed onto the same data buss of an MCU. An XOR, and 8 rotates
with bit test and jumps will do the job.

parallel load a shift regiter with the sum and ripple count them as
you shift them out. have fun with race conditions and all. You'll
want a decade counter to indicate when the 8th bit has been shifted
out. Hell so far, not even considering the glue logic, we're looking
at a big board to do something small. 2 quad XORs, 1 SR, 2 counters,
clock, glue, ...

try looking though the functional blocks sections of the variouse
logic family books. I'm thinking 74HC165 or 597 shift registers.
maybe there's another shortcut, but nothing is striking me as
obvious at this brain-dead moment except a MCU which is probably the
best solution - all else being a mere academic excersize.

Help would be greatly appreciated

Felix

the cat? Ask Poindexter.

Oh, my NNTP server is offline. There's probably an answer here
already. SFASM

 

[John Fields]

Hi.

I want to calculate the Hamming distance of two 8 bit wide numbers,
call them A and B.

I know that the first step would be:
(bit n of A) XOR (bit n of B) ; n in [0;7].
Or add instead of the XOR, ignoring the carry.

Then I have to count the number of 1s in the result to get the
distance. But how would "counting the 1s" be implemented (preferably
with basic logic like gates, encoders, flip-flops etc.)?

8-to-3 (priority) encoders don't seem to do the job (?).
And is there a way to avoid flip-flops without getting too complex?

Help would be greatly appreciated

 

[Active8]

Hi.

I want to calculate the Hamming distance of two 8 bit wide numbers,
call them A and B.

I know that the first step would be:
(bit n of A) XOR (bit n of B) ; n in [0;7].
Or add instead of the XOR, ignoring the carry.

Then I have to count the number of 1s in the result to get the
distance. But how would "counting the 1s" be implemented (preferably
with basic logic like gates, encoders, flip-flops etc.)?

8-to-3 (priority) encoders don't seem to do the job (?).
And is there a way to avoid flip-flops without getting too complex?

Help would be greatly appreciated

Good use of the quad NOR and the dual counter, John. It's 5 chips if
you count the quad XORs Felix will need to compare the bits - 2
chips less than I thought.

 

[John Fields]

Good use of the quad NOR and the dual counter, John. It's 5 chips if
you count the quad XORs Felix will need to compare the bits - 2
chips less than I thought.

 

[Tom Bruhns]

Is this a homework problem? "Counting the 1s" is just the same as
"Adding up all the 1s," no? So you just need an adder that takes 8
bits of input (all at the same weight; not an 8-bit-wide binary
adder). One way to do it is with several full-adders; or you can draw
up Karnaugh maps for the four output bits. (The output is never
greater than a 4-bit number, right?) It would be easy to do with a
PROM, for example: just feed the 8 x-or'd bits to the address port,
and read out your pre-programmed result. It's all combinatorial
logic, no f/f's needed. Or, you COULD do it with somewhat simpler
logic and a shift register or selector: reset a counter, then cycle
through the x-or'd bits and increment the count for each 1 you find.

Cheers,
Tom