Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
The Walsh transform is the "binary DFT" you're looking for. –  Steve Huntsman Jan 16 '11 at 21:03
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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! –  MathGeek Jan 17 '11 at 0:52
1  
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. –  Brian Borchers Jan 17 '11 at 2:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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