>First of all, MANY THANKS for all these replies !! I'm glad to see FFT
>carries still so much enthsiasm !
It is one of the most important tools in signal analysis. Not
surprisingly, also one of the first taught in any linear system theory
class.
>Interestingly, the biggest is not the best.
As in fastest? An FFT grows in computational complexity on the order of
N*log(N), so if you're referring to speed, yes, larger N with fewer blocks
would take longer than smaller N with more blocks. I spent a good deal of
effort explaining to my previous boss why a 1024-point FFT takes more than
twice the time of a 512-point FFT (we were using FFTW, too, btw). He asked
quite innocently "why not just do two 512-point FFTs?" Of course, I
followed up by explaining that you can, but you then have to "tie the two
together" with a 2-point FFT on each of the 512 output pairs. He did not
believe me. I left that company shortly thereafter. :)
>As the background of my collaborators is crystallography, we were
>wondering if the fact of using signal of 0s and 1s can be of any
>effect on the algorithm, so my post !
You might be better served by mapping your 0s and 1s as +1 and -1, btw.
By using 0/1, you're artificially inserting a DC bias into your results.
It may not matter, but might be worth a try just to see what happens.
Mark
Reply by Ron N.●April 25, 20082008-04-25
On Apr 23, 8:25 am, dbell <bellda2...@cox.net> wrote:
> 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?
I seem to recall people attempting use FFTs as part of
a 2-d pattern recognition algorithm on 1-bit monochrome
images or glyphs and such. The first FFT pass would
consist of only 0's and 1's.
IMHO. YMMV.
Reply by Luc Moulinier●April 25, 20082008-04-25
First of all, MANY THANKS for all these replies !! I'm glad to see FFT
carries still so much enthsiasm !
Some answers and details :
- the signal is the result of the transcoding of DNA (yes, I'm a
biologist !) sequence. This signal can be as long a 300 milions (a big
human chromosome for example).
- Our purpose is to find the FASTEST way for finding a pattern in this
signal. Some solutions exists, bui we wanted to evaluate finely the
power of a convolution through FFT.
The pattern to be found is FFTed, the signal is FFTed, mutiply the
FFTs, backtransform.
This works, but the speed in our case is of great importance. The
human genome is made of 23 pairs of chromosome, for a total length of
3 bilions (3Gbases).
A first test using FFTW (beware ! we were using then an other
tanscoding system than 0s and 1s. The signal was here transcoded using
complexes) to find 440 different patterns in the whole genome takes
roughly 2 days ....
You can now infer by yourself (and cerainly much better than me !!)
that the size of the FFT can be what you want. The signal has to be
cut in pieces. I tried pieces of length 2^N, ranging from 1024 to
1048576. Interestingly, the biggest is not the best.
Technically, I tried the FFTW package, with the _many_fft plan. The
pattern to be found is padded up to the 2^N length. The step that
seems to require the most time is the multiplication of FFTs.
As the background of my collaborators is crystallography, we were
wondering if the fact of using signal of 0s and 1s can be of any
effect on the algorithm, so my post !
Luc Moulinier
>It is not really like most useful signals you would find. Only 2
>values. That is not really samples of something you would normally
>think of as made up of sines and cosines. In your example of a CVSD
>bit stream, what would the useful interpretation of the FFT of that
>bit stream be?
Off hand, I would find it interesting to study the noise spectrum.
SACD uses some severe noise shaping, and it would be interesting to
see its effects in the context of some pathological signals.
Greg
Reply by dbell●April 23, 20082008-04-23
On Apr 23, 1:53�pm, Greg Berchin <gberc...@sentientscience.com> wrote:
> On Apr 23, 1:37�pm, dbell <bellda2...@cox.net> wrote:
>
> > But why do want the fft of that?
>
> Same reason you'd want the FFT of any signal, I guess. �Not trying to
> be flippant; it's just a signal like any other.
>
> Greg
It is not really like most useful signals you would find. Only 2
values. That is not really samples of something you would normally
think of as made up of sines and cosines. In your example of a CVSD
bit stream, what would the useful interpretation of the FFT of that
bit stream be?
Dirk
Reply by Greg Berchin●April 23, 20082008-04-23
On Apr 23, 1:37�pm, dbell <bellda2...@cox.net> wrote:
> But why do want the fft of that?
Same reason you'd want the FFT of any signal, I guess. Not trying to
be flippant; it's just a signal like any other.
Greg
Reply by dbell●April 23, 20082008-04-23
On Apr 23, 12:07�pm, Greg Berchin <gberc...@sentientscience.com>
wrote:
> On Apr 23, 11:25�am, dbell <bellda2...@cox.net> wrote:
>
> > I am wondering what the source of the signal is that results in
> > strictly 0's and 1's as sampled data,
>
> One that comes to mind is a delta-sigma modulated signal such as
> Sony's Direct Stream Digital.
>
> Greg
But why do want the fft of that?
Dirk
Reply by Greg Berchin●April 23, 20082008-04-23
On Apr 23, 11:25�am, dbell <bellda2...@cox.net> wrote:
> I am wondering what the source of the signal is that results in
> strictly 0's and 1's as sampled data,
One that comes to mind is a delta-sigma modulated signal such as
Sony's Direct Stream Digital.
Greg
Reply by dbell●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 , France
Luc,
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 Greg Berchin●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