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.