Calculating Hamming distance effectively: a fast approach

Question

Let us say that we have a database of 5000 entries. Each entry is a 32 point discrete signal (min. amplitude: 0 and max. amplitude: 10 (signal value ranging only in integers)) i.e. each discrete point in the entry signal has a value ranging from 0 to 10. Now, a new signal (again a 32 point discrete signal with each point haveing amplitude range from 0 to 10 and integers only) is captured and it has to be compared with each of the 5000 signals and hamming distance has to be calculated for each of the entry.

The easiest way to do this is to compare sample by sample for each entry and the incoming signal and increment the counter for each entry if there is a mismatch.

For example, the hamming distance for the below one of the database entry and the incoming signal will be 7.

Database (32 point discrete):

5 0 5 0 7 3 0 8 8 9 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0

Signal (32 point discrete):

6 0 5 0 9 4 0 7 0 9 0 0 8 0 0 0 2 3 0 0 0 0 0 0 0 0 0 8 0 0 0 0

Hamming distance for the above entry and the incoming signal is 7.

However, the bottleneck is the sample by sample comparison for each of the entry. The total number of comparisons that have to be made will be 32*5000.

I am looking for an efficient way to calculate the hamming distance, which can make this calculation fast. One of the ways that I think is whether it will be possible to represent the 32 point discrete signal in a reduced (compressed) way (e.g. 4 point coded number, 8-point coded number) and the hamming distance remains the same as before? Or any other technique / idea which can make the hamming distance calculation fast?

Answer 1

In 4-bit packed binary-coded decimal (BCD) each of your strings will take 4*32 = 128 bits, which just fits in two 64-bit registers. With some binary wizardry you can calculate the Hamming distance in two highly parallelized runs working on the first 16 and the last 16 packed BCD's. Because your strings are so short, I doubt you can go any faster by higher-level algorithmic means. Dunno what your platform is, but in this pseudocode the SSE4 POPCNT (population count) instruction finishes one half of the job (because only half of the packed BCD's fit in a 64-bit register):

// Inputs: A, B. Both are 64-bit, containing 16 packed BCD's
C = A xor B // For each bit: do the corresponding bits differ?
D = C shr 1 
C = C or D  // For each tuple of 2 bits: Do the corresponding tuples differ?
D = C shr 2
C = C or D  // For each 4-bit packed BCD: Do the corresponding BCD's differ?
C = C and 0x1111111111111111 // 0b00010001 repeated
return popcnt(C) // Number of packed BCD's that differ

The shifts can be either logical or arithmetic, and if they are single-instruction-multiple-data (SIMD) instructions, the word length does not matter, because the last and zeros the most significant bits. It might or might not be useful to employ SSE's 128-bit XMM registers, because POPCNT operates on normal 64-bit registers or memory. If POPCNT is not available, it can be implemented by continuing the tree-like calculation with adds instead of ors, potentially making 128-bit registers more useful. The last line of the above pseudocode can be replaced with the following POPCNT-free pseudocode:

// Code to replace popcnt(C)
D = C shr 4
C = C + D // Hamming distance of each pair of BCD digits fits in 2 bits
D = C shr 8
C = C + D // Hamming distance of each 4-tuple of BCD digits fits in 3 bits
D = C shr 16
C = C + D // Hamming distance of each 8-tuple of BCD digits fits in 4 bits
C = C and 0x0000000f0000000f // 0b00001111 twice
D = C shr 32
C = C + D // Hamming distance of the 16-tuple of BCD digits fits in 5 bits
return C and 0x000000000000001f // 0b00011111

For SIMD adds, the word length does not matter. SIMD shuffle instructions may be available that can be used in place of some of the shifts. Even multiply-accumulate instructions could be useful just for the accumulation. Or the code can be implemented without any SIMD instructions.

Answer 2

First, note that any form of compression, clustering etc. will require its own computational power. So only if it can significantly reduce the complexity such that the overall task has a reduced complexity, then the extra processing is useful. This turns out not to be the case often.

My suggestion is to make the procedure itself as efficient as possible. Some options can be:

1. Try to use matrix operations. Specially if you use Matlab, it is optimized for matrix operations. For instance, you may consider your database as a $5000\times 32$ matrix such as A.

2. Convert logical comparisons to algebraic expressions. For instance, although you can compare two binary vectors $a$ and $b$, element-by-element to find the hamming distance, you can simply do d=sum(xor(a,b)). For non-binary vectors d=sum(a~=b) or d=nnz(a-b), could be a good beginning. So if you want to compare a vector b with all vectors in database matrix A, then replicate your vector to form a matrix B (by repeating it $5000$ times using repmat). Then the hamming distance of b and each row in A is d=sum(A~=B,2) in vector form.

3. Look for patterns in your database. I can see the sample vectors from your database are rather sparse . There are many zero elements that don't change anything but maybe you can reduce the dimensionality of your data by ignoring some indices, if certain indices are always zero.

I think you can make it even more efficient by adding more items...

Answer 3

Your problem might be easier if you trade memory for speed.

First of all, you only got ten values, so the whole "hamming distance of sub-element" can be sped up by either a elegant SIMD, or really by a 10x10 look-up table.

Then, you "blow up" your 5000 entry table – which really, if we don't pack at all and use native types, i.e. 1 byte per sub-entry, is laughably small by modern computing hardware standards (5000x32B = 156.something kB):

With each entry, you also store ten further rows, storing the respective distance to a signal that was [0,...,0], [1,...,1] and so on:

Entry:                5 0 5 0 7 3 0 8 8 9 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0
Distance to [0,0,...] 2 0 2 0 3 2 0 1 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
Distance to [1,1,...] 1 1 1 1 2 1 1 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
...
Distance to [10,10,...] ...

That of course increases your database size von 156kB to more than 1MB. Which still fits into modern CPU's cache. Generating this should, even unoptimized, take microseconds at most. Looking one signal's cumulative distance up will indeed take 5000 x 32 lookups, and 5000 x 31 summations, but since memory access is nice and linear here, we can assume a throughput of maybe 0.25 lookup per CPU cycle, and one addition per cycle, so with a meager 1 GHz CPU, you'd use 4*5000*32 + 5000*31 = 5000 * 159 = 795,000 cycles, or roughly 0.8 ms. Now, this might be far too long for high-throughput realtime decoding, but I get the feeling that's not what you're after...

It's almost certainly slower than Olli's SIMD solution (it's pretty much impossible to beat the throughput of modern x86 on SIMD bitwise operations), but can be realized even without any assembler/SIMD handling, and also efficiently on machines without a POPCNT instruction (which IIRC is a relatively new addition to the SSE set of ISA extensions).