From: Greg Berchin on 17 Jun 2010 13:48 On Thu, 17 Jun 2010 10:38:17 -0500, "Intuitive" wrote: >I don't understand the approach proposed by Greg too. Can you give a better >explanation? (Possible step by step). Use a fixed-width font. The DFT value in frequency bin "k" of the data set starting at sample "n0=0" is: 1023 X(k,n0) = SUM [x(n)*exp(-j2PIkn/1024)] n=0 The DFT in frequency bin "k" of the data set starting at sample "n1=128" is: 1151 X(k,n1) = SUM [x(n)*exp(-j2PIkn/1024)] n=128 1023 = SUM [x(n)*exp(-j2PIkn/1024)] n=0 1151 + SUM [x(n)*exp(-j2PIkn/1024)] n=1024 127 - SUM [x(n)*exp(-j2PIkn/1024)] n=0 1023 = SUM [x(n)*exp(-j2PIkn/1024)] n=0 127 + SUM [x(n+1024)*exp(-j2PIk(n+1024)/1024)] n=0 127 - SUM [x(n)*exp(-j2PIkn/1024)] n=0 1023 = SUM [x(n)*exp(-j2PIkn/1024)] n=0 127 + SUM [x(n+1024)*exp(-j2PIk(n+1024)/1024) - x(n)*exp(-j2PIkn/1024)] n=0 1023 = SUM [x(n)*exp(-j2PIkn/1024)] n=0 127 + SUM {[x(n+1024)-x(n)]*exp(-j2PIkn/1024)} n=0 127 = X(k,n0) + SUM {[x(n+1024)-x(n)]*exp(-j2PIkn/1024)} n=0 So the DFT at of the data set starting at sample 128 is equal to the DFT of the data set starting at sample 0 plus something resembling a 128-point DFT of the difference between the "newest" 128 samples and the "oldest" 128 samples. (Note the "1024" in the denominator, however.) Since you are building the DFT gradually, you can define the "oldest" 128 samples to be zeroes: 127 X(k,n1) = X(k,n0) + SUM {x(n+1024)*exp(-j2PIkn/1024)} n=0 Similarly, the DFT in frequency bin "k" of the data set starting at sample "n2=256" is: 1279 X(k,n2) = SUM [x(n)*exp(-j2PIkn/1024)] n=256 1151 = SUM [x(n)*exp(-j2PIkn/1024)] n=128 1279 + SUM [x(n)*exp(-j2PIkn/1024)] n=1152 255 - SUM [x(n)*exp(-j2PIkn/1024)] n=128 1151 = SUM [x(n)*exp(-j2PIkn/1024)] n=128 255 + SUM [x(n+1024)*exp(-j2PIk(n+1024)/1024)] n=128 255 - SUM [x(n)*exp(-j2PIkn/1024)] n=128 1151 = SUM [x(n)*exp(-j2PIkn/1024)] n=128 255 + SUM [x(n+1024)*exp(-j2PIk(n+1024)/1024) - x(n)*exp(-j2PIkn/1024)] n=128 1151 = SUM [x(n)*exp(-j2PIkn/1024)] n=128 255 + SUM {[x(n+1024)-x(n)]*exp(-j2PIkn/1024)} n=128 255 = X(k,n1) + SUM {[x(n+1024)-x(n)]*exp(-j2PIkn/1024)} n=128 So the DFT at of the data set starting at sample 256 is equal to the DFT of the data set starting at sample 128 plus something resembling a 128-point DFT of the difference between the "newest" 128 samples and the "oldest" 128 samples. (Note the "1024" in the denominator, however.) Since you are building the DFT gradually, you can define the "oldest" 128 samples to be zeroes: 255 X(k,n2) = X(k,n1) + SUM {x(n+1024)*exp(-j2PIkn/1024)} n=128 And so on. From: glen herrmannsfeldt on 17 Jun 2010 16:25 Intuitive wrote: (snip) > At this moment I'm following the advice of Vladimir. I tested > the second approach in matlab and It works. However I don't > understand the his first proposed apporach. > What is the meaning of: > "The best and the simplest is get the data back by inverse FFTs, > then compite the large FFT." > Can you give me a more simple explanation? (Possible step by step). That sounds obvious enough for me, but you don't want to do it. It comes from a theorist who doesn't care how long it takes. Given eight FFTs of 128 samples each, do an inverse FFT on each, concatenate the result, and do a 1024 point FFT. Slow, but it does work. > I don't understand the approach proposed by Greg too. > Can you give a better explanation? (Possible step by step). -- glen From: Greg Heath on 18 Jun 2010 22:54 On Jun 16, 7:44 am, "Intuitive" wrote:> Hello everybody. > > I have got a DSP question for all of you. > I'd like to know if it is possible to obtain a large FFT (for example 1024 > samples) combining small SEQUENTIAL FFTs(128 samples). > > It is really important for me that the input samples are consecutive (so it > is not possible to apply the usual trick of even and odd samples). > I'm working on a real time system with a RT constraint of 128 samples. > Actually I'm accumulating samples for 8 iterations (128*8=1024) until to > obtain the 1024 samples to perform the FFT of the input signal. However I'd > like to decompose the FFT in small sequential FFTs in order to distribute > the compute for each frame. > > If you have any question don't hesitate to contact me. > > I'm looking forward to hearing from you, Andrea. It is readily accomplished by accounting for time delays via a linear phase shift and zeropadding transforms to length N=8*N0 for N0 = 128.. The following example has N0 = 4 and N = 4*N0 = 16. close all, clear all, clc N0 = 4 N = 4*N0 Fs = 16 dt = 1/Fs t = dt*(0:N-1); t0 = N0*dt ind1 = (1:N0); ind2 = (N0+1:2*N0); ind3 = (2*N0+1:3*N0); ind4 = (3*N0+1:N); rand('state',0); f0 = Fs/8 x = cos(2*pi*(f0*t+rand)); df = Fs/N f = df*(0:N-1); X = fft(x); X1 = fft(x(ind1),N); X2 = exp(-i*2*pi*t0*f).*fft([x(ind2)],N); X3 = exp(-i*4*pi*t0*f).*fft([x(ind3)],N); X4 = exp(-i*6*pi*t0*f).*fft([x(ind4)],N); Xc = X1 + X2 + X3 + X4; check = maxabs(X-Xc) % = 1.0782e-014 Hope this helps. Greg From: Ron N. on 19 Jun 2010 01:51 On Jun 16, 4:44 am, "Intuitive" wrote:> Hello everybody. > > I have got a DSP question for all of you. > I'd like to know if it is possible to obtain a large FFT (for example 1024 > samples) combining small SEQUENTIAL FFTs(128 samples). > > It is really important for me that the input samples are consecutive (so it > is not possible to apply the usual trick of even and odd samples). > I'm working on a real time system with a RT constraint of 128 samples. > Actually I'm accumulating samples for 8 iterations (128*8=1024) until to > obtain the 1024 samples to perform the FFT of the input signal. However I'd > like to decompose the FFT in small sequential FFTs in order to distribute > the compute for each frame. If you are willing to give up latency and memory usage for a more even distribution of FFT computation over time, you could try a pipelined approach. After collecting 8 groups of 128 samples in 8 time slots, you could start doing a 1024 pt fft in 8 pipe stages, 1 pipe stage per time slot, each pipe stage consisting of 1.25 layers of 1024 FFT butterflys (e.g. 1280 butterflys per time slot). After 8 more pipe stages you will end up with all 10 butterfly layers of your 1st 1024 pt FFT, just as you've finished collecting the data to start your next 1024 point FFT. The latency from 1st data group to FFT result will be 16 very computationally balanced pipe stages, instead of 8 pipe stages with a huge summation lump the 8th stage. The memory usage will also be approximately double since you will be gathering data for one FFT while still computing the previous one. This is a typical technique in hardware design (ASIC or FPGA). IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M http://www.nicholson.com/rhn/dsp.html From: Rick Lyons on 20 Jun 2010 15:56 On Wed, 16 Jun 2010 06:44:18 -0500, "Intuitive" wrote: >Hello everybody. > >I have got a DSP question for all of you. >I'd like to know if it is possible to obtain a large FFT (for example 1024 >samples) combining small SEQUENTIAL FFTs(128 samples). > >It is really important for me that the input samples are consecutive (so it >is not possible to apply the usual trick of even and odd samples). >I'm working on a real time system with a RT constraint of 128 samples. >Actually I'm accumulating samples for 8 iterations (128*8=1024) until to >obtain the 1024 samples to perform the FFT of the input signal. However I'd >like to decompose the FFT in small sequential FFTs in order to distribute >the compute for each frame. > >If you have any question don't hesitate to contact me. > >I'm looking forward to hearing from you, Andrea. > Hi, You might want to have a look at: http://www.dsprelated.com/showarticle/63.php Good Luck, [-Rick-] First  |  Prev  |  Pages: 1 2 3 Prev: OMAP-L1x Processor Universal Serial Bus 2.0Next: Measure frequenzy?