7
$\begingroup$

Given two long binary strings of length N, it's easy to find the Hamming distance between them. If you're allowed to cyclically shift one of the strings, you'll get N different Hamming distances when comparing the two. What is an efficient way to find the maximum Hamming distance over all N shifts?

This question is motivated by a sensor which tends to emit streams of "random" bits. There's potential slight correlations at unknown delays of millions of bits, a kind of slight bias of a ghost echo. I'm looking for a test to see if these correlations can be detected.

I think the problem can be solved with application of the discrete Fourier transform, but I'm not sure if there's a "binary" Fourier transform analogue and how it could identify the maximum Hamming over all the circular shifts.

Thanks!

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The Walsh transform is the "binary DFT" you're looking for. $\endgroup$
    – Steve Huntsman
    Jan 16, 2011 at 21:03

1 Answer 1

Reset to default
6
$\begingroup$

I'd suggest that you start by encoding your signal in terms of the symbols +1 and -1 rather than 0 and 1. If you have two signals x and y, then take elementwise products of x and y and sum to get a measure of the distance between x and y. If the signals are identical, then the sum will be n. If the signals differ in each position, the sum will be -n. If there are matches in k positions, then the sum will be k-(n-k)=2k-n.

e.g. (using MATLAB notation)

x=[1; 1; 1];

y=[-1; 1; -1];

sum(x.*y)=-1

Once you know this, then you can consider taking the circular convolution of two signals x and y. The elements of the circular convolution of x and y are these sums for various circular shifts of z. e.g.

x=[+1, -1, +1]

y=[+1, +1, -1]

let

z=circconv(x,y)=ifft(fft(x).*fft(y))

z=[3, -1, -1]

This tells us that shifting y circularly to the left by one position results in a perfect match, and that the other two circular shifts of y result in largest mismatches.

This algorithm takes O(n*log(n)) time to compute z and then O(n) time to find the max (and/or min) elements of z.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah! So the simple realization is that this doesn't have to be done bitwise at all.. just move it into reals and use standard tools. Thanks for the -1 to 1 remapping trick, that makes the output very clean! $\endgroup$
    – MathGeek
    Jan 17, 2011 at 0:52
  • 1
    $\begingroup$ I'd expect that single precision would be quite accurate enough for your purposes and would run somewhat faster than double precision, particularly if you're using a GPU to do this. $\endgroup$
    – Brian Borchers
    Jan 17, 2011 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.