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. > > GregBut why do want the fft of that? Dirk
FFT of 0s and 1s signal
Started by ●April 22, 2008
Reply by ●April 23, 20082008-04-23
Reply by ●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 ●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. > > GregIt 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 ●April 23, 20082008-04-23
On Wed, 23 Apr 2008 15:29:19 -0700 (PDT), dbell <bellda2005@cox.net> wrote:>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 ●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
Reply by ●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 ●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 !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