FFT of 0s and 1s signal

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 , France

On Tue, 22 Apr 2008 09:20:49 -0700, Luc Moulinier 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
> , France

Just a regular FFT will work fine, and probably come close to optimal 
processing time, for that matter.

-- 
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com

Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html

you may download octave or scilab from web and use
their functions fft, for example in octave you will
have to do something like this on command line,

%--------------------------------------------------

clear all;
close all;

x  = [ 0 1 1 0 0 0 0 1 0 1 1 0];

xz = fft(x)/length(x);

%If you know the sample rate then you can create
%freq vector

Fs = 10000; % assumed, put your actual numbers here
n  = 0 : length(x)-1;

f  = n*Fs/length(x);

figure; clf;
plot(f, abs(xz));

%----------------------------------------------------

Regards
Bharat Pathak

www.Arithos.com

DSP design consulting and Training company.







>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=E9nomique Int=E9gratives
>Illkirch , France
>

>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

"markt" <takatz@pericle.com> wrote in 
news: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.

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.

    Nils

On Apr 22, 2:09 pm, "markt" <tak...@pericle.com> wrote:
> >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.

A clarification: given a general-purpose FFT implementation (e.g.
FFTW), the runtime on any modern CPU is independent of the input data
(barring floating-point exceptions).

However, if you know that your data is of a certain form, you can
sometimes write a faster FFT that only works for data of that form.
(e.g. I can certainly write a faster FFT if I know the input is all
zeros...just call memset!)

For the original poster's case, assuming I understand him correctly, I
am dubious that you could gain much, but in principle you might be
able to gain a little.  Let's suppose you have data of (highly
composite) length N consisting of all zeros and ones, but you don't
know anything else about the 0/1 pattern in advance (and N is too
large for a lookup table of the 2^N possible results).  When you do an
FFT, you decompose the transform into smaller transforms.  Once you
get down to size-4 transforms, there are no multiplications, only
additions and subtractions, so at that point you might be able to take
advantage of e.g. SSE instructions (or similar special-purpose
hardware) to do e.g. 16 1-byte integer additions in parallel.
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.  And it would be very difficult in practice to beat a
highly optimized FFT like FFTW or Intel MKL unless you started with
(e.g.) the FFTW code and then optimized the transform leaves for your
binary data to get your marginal speedup.

In practice, I doubt it's worth it to try optimizing this case.

Regards,
Steven G. Johnson

>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.

That can be said for any pre-determined case and hence a lookup would
suffice.  There are implementations that are faster than others, depending
upon the radices required for the given FFT (the FFTW folks discuss all
this, with prime radices up to 173 points now I believe).

Mark

>A clarification: given a general-purpose FFT implementation (e.g.
>FFTW), the runtime on any modern CPU is independent of the input data
>(barring floating-point exceptions).

Thanks for the follow-up Steve.   Hope you don't mind the plug for your
website, btw. :)

Mark

On Apr 22, 5:12 pm, "markt" <tak...@pericle.com> wrote:
> That can be said for any pre-determined case and hence a lookup would
> suffice.  There are implementations that are faster than others, depending
> upon the radices required for the given FFT (the FFTW folks discuss all
> this, with prime radices up to 173 points now I believe)

FFTW handles arbitrary prime factors.  (The pre-packaged FFTW only
comes with optimized hard-coded kernels for prime factors up to 13,
and uses generic O(n log n) code for larger factors.  However, if you
really care about prime factors of 173, you could easily tell FFTW to
generate special-purpose code for this case.  Highly composite sizes
are still best, of course.)

Steven