Computing Hamming Distances

[reedsolomon]

Hello,

Is there an easy way to compute the Hamming Distance of two m-bit values in VHDL/Verilog?

Thanks for your time.

 

[Buriedcode]

Hi,

I assume you mean 'hamming distances' by simply comaring two binary numbers? And how many 'bits' are different. I imagine a simple XOR of the two numbers is all thats needed. Since if the inputs of an XOR gate are the same (0,0 or 1,1) the output is zero. Different inputs gives a '1' output.

I tend to work in schematics (unless its really complicated) I understand logic better when I can see it, but say you have two bytes, and you wish to find the hamming distance between them. Simply XOR the bytes together, and the outputs loaded into a 'parallel in-serial out' shift register. Then shift output the bits with the data out and clock of the shift register AND'ed, and them make this the clock input to a counter. Whenever two bits are different, a '1' would increment the counter. A '0' (when two bits are the same) would not increment the counter.

Really all you're doing in comparing the two numbers and counting the number of differences.

Thats how I would do it

Hope this helps,

BuriedCode.

Update: This could all be simplified, and work for ANY bit length number if you simply have two shiftregisters, each containing your two numbers. The outputs are XOR'ed, and this can increment your counter. In verilog/VHDL this should be very simple.

 

[reedsolomon]

Hi BuriedCode,

Thanks for your help! Is there a way to compute the distance in one clock cycle (or would the most efficient way be using a lookup table)?

 

[Buriedcode]

hi again,

I've been racking my brains trying to think of a 'one clock' solution (just in my head...). You will still need to XOR the two values, each bit XOR'ed with the coresponding bit in the other value. Eg: for binary numbers 'm' and 'n'

m7 XOR n7; m6 XOR n6; m5 XOR n5 etc....

For 8 bits (just for this example) that gives us 8 outputs. Every '1' indicates a difference in bit value. Now, you mentioned a look-up table, that would have 256 entries :/ Since there are 256 combinations of 8 bits. If you go for a wider data width (32 bits?) your lookup table will become huge! Plus, if this is all done in boolean logic (non synchronous) its the same deal, the complexity increases dramatically (2 fold) every bit you add to the data width.

I'm afriad, synchronous logic, is the only way to go, you will need more more than one clock cycle. That said.....as with all things like this (hamming decoders etc...) its a balance, or a comprimise between 'size' and 'time'.

For example, say we wanted to calculate parity. For 8 bits, we need quite a large XOR tree if we wish to calculate a parity bit instantly (without a clock). In CPLD's/FPGA's XOR tree can take up a fair few CLB. On the other hand, if we are restricted by 'size' (say we have a small CPLD) then we can do this calculation over time. By shifting each bit through a register, and incrementing a counter (a 1-bit counter, basically, switching between odd and even). This only requires 9 registers, and one AND gate.........but, it takes 8 clocks.

Back to your problem:
Now, if you want it done quickly, but want a wider bus width, you could use a combination of the two idea's above....use both time AND size. Instead of having a massive logic circuit, or using up one clock cycle for each bit, break it down into, say, 4 bit nibbles.
You work out the hamming distance in these 4-bit nibbles, each nibble takes 1 clock cycle, and requires a bit of logic. From this circuit, you have a counter, which can be incremented by 0,1,2,3,4. That way, you *could* use a look-up table, with only 16 entries, but alas, a byte would take 2 clocks, 2 bytes 4 clocks etc...

The above idea is what I used to make a 13,8 hamming encoder/decoder fit into a 64 MC CPLD, along with lots of counters......the support guy for lattice said, it could not be done

In a schematic, 'getting' your data in 4-bit nibbles can be tricky, but in Verilog or VHDL it should be straightforward. As I said in my first post, I only use VHDL for complicated designs, and for this, it really is a great tool. Is your data coming in serially? or in parallel load?

Regards,

BuriedCode.

 

[reedsolomon]

Hey BuriedCode,

I appreciate the hard work. A new m-bit value would be received every clock cycle. I'm guessing I'm going to have to pipeline the data...

 

[Buriedcode]

hi agian,

I appreciate the hard work.

You're welcome

A new m-bit value would be received every clock cycle. I'm guessing I'm going to have to pipeline the data...

Yep, I guess thats the only practical solution. I will still give it some thought though, after all, if your 'm-bit' values are fairly short (I'm still saying 8-bits as the practical maximum) it *should* be possible to do this in one clock. Also, sticking an inverter on the clock line of a FF can help, loads in a value on the falling edge. All depends on how big/complex your FPGA/CPLD is.

Assuming you can simulate this sort of design, it might be worth using your look-up table anyway, just in simulation. I often set my software (LatticeLEVER) for the biggest FGPA it has, just for massive designs, and see how it optimises them. Sometimes, its easier to 'tell' software what you want it to do, by using look-up tables, and letting it work out what the best way and then 'copying' this idea. I'm always surprised at how well the software optimises the design, depending on the parameters, it can reduce it down to 10% of its original size. I know this is what the software is designed for, but its still handy, if not for a final design, then to see if there is a 'simple' solution to a problem.....if you put in your lookup table, and it only uses a few % of resources once optimised, you know theres a good idea.

Regards,

BuriedCode.