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
    Commented 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
    Commented 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
    Commented Jan 17, 2011 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .