Jump to content

Talk:Fast folding algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

I can't find a good description of this algorithm on the net, so I've started my own. You'll notice it's got a big hole where all the technical detail should be! Contributions welcome ...

How it works

[edit]

I implemented an FFA in python some time ago, so I can give a rough description of how it works.

During one pass of the FFA, all periods between n samples and n+1 samples are folded at once. The key idea is to divide the time series into m nonoverlapping blocks of n samples. Then the period-n profile is obtained by simply adding all the blocks. For a period between n and n+1, if one were simply folding the data, one would accumulate the profiles, but because the period is slightly longer than n, the phase would drift slightly. When the phase was wrong by one bin, you would begin cyclically shifting profiles to compensate for the drift. Thus to look at all possible periods, you should look at many different sequences of cyclic shifts. But the set of folds of m periods can be obtained from the set of folds of m/2 periods on the first and second halves by combining them both with and without shifting. So there's a divide-and-conquer algorithm.

In a way, this is very much like an FFT algorithm where the complex values have been replaced by profiles and the multiplication by "twiddle factors", roots of unity, has been replaced by cyclic shifts. —Preceding unsigned comment added by 65.95.19.27 (talk) 07:33, 21 March 2010 (UTC)[reply]


could I know the contact method of the author? I have several ffa questions to ask. Thanks.