On Apr 22, 2:41�pm, Ian Shef <inva...@avoiding.spam> wrote:> "markt" <tak...@pericle.com> wrote innews:poKdncZlcadctJPVnZ2dnUVZ_jydnZ2d@giganews.com: > > >>Does anyone knows about code/package to handel this sort of "signal" > >>very efficiently ? > > > The speed (or efficiency) of an FFT is generally considered independent of > > the data. �The gents over at FFTW (www.fftw.org) run their benchmarks on > > all zeros data. �They do this to allow repeated calls on the same array > > preventing divergence in the output. �There are plenty of good resources > > for FFT knowledge at the FFTW website, btw. > > > Mark > > It depends... > > In general you would be correct, but maybe not in this case. > Assuming no windowing, then some multiplies can be eliminated, replaced by a > simple decision to add or not to add. > > Whether this helps or not depends upon the implementation. �A hardware > implementation might be able to take advantage of this. �In a software > implementation, the decisions could cause pipeline flushes that are worse > (with respect to throughput) than just doing the multiplies. > > Unfortunately, the original poster did not provide any information on where > this would be implemented.In the case you mention, for an FFT of size N, what is the maximum percentage of operations you might save in hardware? Do you think that it is what you would classify as a significant "advantage"? Dirk
FFT of 0s and 1s signal
Started by ●April 22, 2008
Reply by ●April 22, 20082008-04-22
Reply by ●April 22, 20082008-04-22
On Apr 22, 4:25 pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:> However, these savings would only accrue at the leaves of the > transform; subsequent stages would have to go back to ordinary > floating-point arithmetic, so the savings would be negligible for > large enough N.Well, perhaps this is too pessimistic; you might get some non- negligible cache benefits for large out-of-place transforms because the input fits into a smaller space. (And there are a few other games you could play, e.g. using a lookup table once you have broken the transform into small enough pieces.) I still doubt it is worth it for all but the most demanding applications, however. Steven
Reply by ●April 22, 20082008-04-22
Steven G. Johnson wrote: ...> In practice, I doubt it's worth it to try optimizing this case.I don't think that Luc was looking for an optimization. At least, that's how I read his post: "I am wondering if someone knows about a FFT algorithm able to handle such a cose [sic]." If others had not answered him already, I would have written that 0 and 1 are numbers just like others, and that any FFT will handle them. I suspect Luc knows that now. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 22, 20082008-04-22
On Apr 22, 11:01 am, Nils <n.pipenbri...@cubic.org> wrote:> Luc Moulinier schrieb: > > > Hello !! > > > I have to FFT a signal made of 0s and 1s, i.e., my sequence is for > > example, 0,1,1,0,0,0,0,1,0,1,1,0 ... etc This is a true serie of 0s > > and 1s, not a number, written as binary. > > If you number of elements is small enough you can precalculate all > possible FFT results and put them into a lookuptable. > > Maybe this is to obvious but your signal is *just* a binary number and > would perfectly work as a table index. > > It depends on your N, your system and your memory requirements. > > NilsOr if N is too large for a lookup table to fit in memory, or in cache without causing thrashing, you could factor the FFT into one pass done by a table look-up with the largest table that does fit, with the rest completed by more common FFT algorithms. IMHO. YMMV.
Reply by ●April 22, 20082008-04-22
On Apr 22, 6:39 pm, Jerry Avins <j...@ieee.org> wrote:> I don't think that Luc was looking for an optimization. At least, that's > how I read his post: "I am wondering if someone knows about a FFT > algorithm able to handle such a cose [sic]." If others had not answered > him already, I would have written that 0 and 1 are numbers just like > others, and that any FFT will handle them. I suspect Luc knows that now.I prefer to answer questions if I can at least pretend that they are interesting. =) Steven
Reply by ●April 22, 20082008-04-22
Numbers grow through the stages of an FFT, so your 1's and 0's will increase in size. Other posters have mentioned that, for large N (too big for look-up tables) there might be some savings in the first few stages by optimizing for the smaller numbers, but it probably won't result in a big overall impact. I know from doing two stage higher radix and mixed radix FFTs for real inputs that replacing the first stage butterflies with butterflies for real inputs results in a relatively small improvement in running speed (3.75 sec vs. 4 sec. for a large number of runs). This was in spite of the fact that my butterflies for real inputs were highly optimized with no loops - e.g.: my radix 8 butterfly used 20 real add/subtracts and 2 real multiplies). But I was wondering. Is your binary data real only, or complex? If the former, then you could make use of the techniques from: C. Bingham, M. D. Godfrey, J. W. Tukey, �Modern Techniques of Power Spectrum Estimation,� IEEE Trans. Audio and Electroacoustics, AU-15, no. 2, June 1967, pp. 56-66. You can do either: 1) two N point real FFTs using an N point complex FFT, or 2) a 2N point real FFT using an N point complex FFT. The latter would apply to your case. The alternative is to use a 2N point FFT for real inputs. FFTs for real valued inputs can actually have half the complex multiplies of an FFT for complex valued inputs, and slightly less than half the add/subtracts. But in my experience, the added addressing overhead of a 2N real FFT versus one complex N FFT makes the complex version more efficient. I have a tutorial on the techniques from the Bingham paper on my web site: fftguru.com (I've been doing FFTs for nearly 30 years and had a long FFT research project in the 1980's - a lot of it hardware related, and 'fftguru' sounded better than 'fftguy'). And if you do go that route, be careful of the fact that the Bingham paper used a positive coefficient forward FFT, and many people still do both techniques either inefficiently and/or wrong. The code shown in the tutorial has been thoroughy tested, so I know it works. And if you're interested, there's another tutorial that's an introduction to signal processing and FFT. I spent a LOT of time and effort on it. You might be surprised to find that I�ve actually done FFTs on binary inputs, and the application mentioned in the tutorial is probably the strangest one you�ll ever see.
Reply by ●April 23, 20082008-04-23
kevinjmcgee@netscape.net wrote:> Numbers grow through the stages of an FFT, so your 1's and 0's will > increase in size. Other posters have mentioned that, for large N (too > big for look-up tables) there might be some savings in the first few > stages by optimizing for the smaller numbers, but it probably won't > result in a big overall impact.... This is what I think of as a runaway thread. The OP posed his question early today and hasn't posted again. He's gotten many answers, and asked for no clarification. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 23, 20082008-04-23
A binary sequence has some properties that make it an attractive
application for a Sliding FFT. With reference to: "http://
groups.google.com/group/comp.dsp/browse_frm/thread/c5596b60090972f/
06800ec6bc25deb8?hl=en&lnk=st&q=&fwc=1",
The DFT value in frequency bin "k" at sample "n0" is:
N-1
X(k,n0) = SUM [x(n+n0)�exp(-j2PIkn/N)].
n=0
In the "traditional" Sliding FFT formulation, the DFT in frequency bin
"k" at sample "n1=n0+1" is:
X(k,n1) = exp(+j2PIk/N) � {X(k,n0) + [x(N+n0)-x(n0)]}.
If the sequence is binary and real, then [x(N+n0)-x(n0)] can only take
values of [-1, 0, 1] and each subsequent X(k) value can be computed
from the previous by means of a real addition and a complex
multiplication.
However, in the "synchronous" Sliding FFT formulation,
X(k,n1) = X(k,n0) + {[x(N+n0)-x(n0)] � exp(-j2PIk(n0)/N)}.
Again, if the sequence is binary and real, then [x(N+n0)-x(n0)] can
only take values of [-1, 0, 1]. In this case, however, each
subsequent X(k) value can be computed from the previous by means of a
complex addition (two real additions).
Greg Berchin
Reply by ●April 23, 20082008-04-23
On Apr 22, 12:20�pm, Luc Moulinier <mou...@igbmc.u-strasbg.fr> wrote:> Hello !! > > I have to FFT a signal made of 0s and 1s, i.e., my sequence is for > example, 0,1,1,0,0,0,0,1,0,1,1,0 ... etc This is a true serie of 0s > and 1s, not a number, written as binary. > > I am wondering if someone knows about a FFT algorithm able to handle > such a cose. I'm not (far not!) an expert in FFT algorithm, but I can > imagine that such a "signal" to FFT should impact the FFT code. > > Does anyone knows about code/package to handel this sort of "signal" > very efficiently ? > > Many thanks in advance ! > > ---------------------------------- > Luc Moulinier > IGBMC, Laboratoire de Bioinformatique et G�nomique Int�gratives > Illkirch , FranceLuc, I am wondering what the source of the signal is that results in strictly 0's and 1's as sampled data, and what is the need for (or use of) the fft? Dirk
Reply by ●April 23, 20082008-04-23
