|
Hi C6x, I have a project that requires a Real FFT/IFFT algorithm. I found several DSP libraries (DY4 and Kanegineering). But I hate to have to pay $5000 to $5500 for a library when I really only need the real FFT function. TI's benchmarks web site has a listing for several FFTs, but they are all complex FFTs. If anyone knows where I can find efficient real FFT/IFF code I'd appreciate it if you would let me know. It would also help, if you know of a C67x DSP Library vendor that would be welling to sell just the FFT/IFFT portion. Thanks in advance Khalid |
|
|
Real FFT/IFFT on C6711
Started by ●March 11, 2002
Reply by ●March 11, 20022002-03-11
|
khaild66 wrote: > Hi C6x, > I have a project that requires a Real FFT/IFFT algorithm. I > found several DSP libraries (DY4 and Kanegineering). But I hate to > have to pay $5000 to $5500 for a library when I really only need the > real FFT function. TI's benchmarks web site has a listing for > several FFTs, but they are all complex FFTs. > If anyone knows where I can find efficient real FFT/IFF code I'd > appreciate it if you would let me know. It would also help, if you > know of a C67x DSP Library vendor that would be welling to sell just > the FFT/IFFT portion. > > Thanks in advance > > Khalid Hi Khalid, FFTs are normally operating on complex input samples. However, if you need only the real part then simply set the imaginary part of all input samples to zero. The fft-output will be complex and you may have to descramble the output sequence. BTW: TI's cfftr2_dit worked fine for us on real valued input samples and it's free.. Regards, Phil -- --------------------------- Dipl.- Inf. Phil Alder Field Application Engineer DSPecialists GmbH Rotherstra 22 10245 Berlin Email: Germany www.DSPecialists.de --------------------------- DSPecialists Making the Impossible Work ! |
Reply by ●March 11, 20022002-03-11
|
At 11:31 PM 3/10/02, khaild66 wrote: >Hi C6x, > I have a project that requires a Real FFT/IFFT algorithm. I >found several DSP libraries (DY4 and Kanegineering). But I hate to >have to pay $5000 to $5500 for a library when I really only need the >real FFT function. TI's benchmarks web site has a listing for >several FFTs, but they are all complex FFTs. > If anyone knows where I can find efficient real FFT/IFF code I'd >appreciate it if you would let me know. It would also help, if you >know of a C67x DSP Library vendor that would be welling to sell just >the FFT/IFFT portion. > >Thanks in advance > >Khalid It has been awhile since I have done much work with FFTs, but let me add my 2 cents worth here. The FFT is inherently a complex operation on complex data producing a complex result. When people speak of a REAL FFT, they are really talking about the REAL part of the result of processing a REAL input stream, ignoring the imaginary part. So one way to process a real input stream is to fill the imaginary part with zeros, run a full sized FFT and toss the imaginary part of the result which contains no additional data, IIRC. If I am wrong about that, then you need to combine the real and imaginary parts as the square root of the sum of the squares. The efficiency of this can be improved upon by taking advantage of the symmetry of the FFT result. This is where I get a little fuzzy on how it works. The output of an FFT with real input data will be symmetrical. The real part will have "even" symmetry and the imaginary part will have "odd" symmetry. There is a simple way to put two REAL sequences into an FFT and then extract them from the result as two separate sequences. In effect, you can do a pair of N point, real input FFTs in one complex FFT. If you don't want to buffer up two input buffers, you can do one N point, real input FFT using an N point transform and a final pass. Just consider your N point real buffer to be two N/2 inputs and process them in a complex N/2 FFT. Once you have extracted the two sets of results, you can then perform a final pass to combine the two N/2 FFTs into a single N point FFT. This will require that you do some processing with twiddle factors, etc. So using the FFT on real data is not hard, but you will need to scan the web to get the details on the "unscramble" pass and/or the FFT final pass. Since it is only a single pass of the FFT, you likely don't need to worry about getting the full efficiency out of the DSP. That is the tricky part of coding FFTs on DSPs. Good luck! Rick Collins Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX |
|
|
Reply by ●March 11, 20022002-03-11
|
Good afternoon everybody ;8-) Rick wrote: So one way to process a real input stream is to fill the imaginary part with zeros, run a full sized FFT and toss the imaginary part of the result which contains no additional data, IIRC. If I am wrong about that, then you need to combine the real and imaginary parts as the square root of the sum of the squares. >>>When tossing the imaginary parts, you will loose all information required to calculate the phase of the signal or to process the IFFT. It's the magnitude (i.e. the amplitude) which is calculated as square root of the sum of the squares. Speaking about improving the efficiency, Rick has opened an interesting topic: If I want to perform a 4096 point real valued FFT using a complex routine then I would combine 2*2048 samples into one "complex" input vector??? The result would be a 4096 point complex output vector which is odd/even symmetrical about bin N/2 48 (hence I would normally discard results above N/2). So how to combine that result with the second stage (i..e. the remaining 2048 samples) and how to run the final pass? Has anybody done this on C6x or found more information on scrambling two sequences? Moroever, could you please direct me to the references Rick was talking about? Would love to squeeze some MIPS out of the C67x... Thanks for your help! Phil |
|
|
Reply by ●March 11, 20022002-03-11
|
The result of using an N/2 FFT to process N real inputs is the COMBINED FFTs of the two real sequences. Each of these FFT results has symmetry, which IIRC, can be used to separate them. I believe you end up with the real part containing the real real sequence plus the imaginary imaginary sequence. Sine the RR will have even sym, you can add point N-1 to point 0 and get 2*RR and if you subtract the two you get 2*II. I am not sure of the exact indexing as the point N/2 does not have a corresponding point. But this is all very hazy to me. Likewise you can do the same thing with the imaginary part of the result. The imaginary result from the sequence placed in the real input (RI) will have odd symmetry and the real result from the sequency placed in the imaginary input (IR) will have even symmetry. So the same process works here. I can't point you to references, but I know there are many. Just do a web search using all the keywords that are relevant. Or you can get a ton of help by posting your question to the comp.dsp or comp.arch.fpga newsgroups. At 12:00 PM 3/11/02, Phil Alder wrote: >Good afternoon everybody ;8-) > >Rick wrote: >So one way to process a real input stream is to fill the imaginary part >with zeros, run a full sized FFT and toss the imaginary part of the result >which contains no additional data, IIRC. If I am wrong about that, then >you need to combine the real and imaginary parts as the square root of the >sum of the squares. > > >>>When tossing the imaginary parts, you will loose all information >required to calculate the phase of the signal or to process the IFFT. >It's the magnitude (i.e. the amplitude) which is calculated as square >root of the sum of the squares. > >Speaking about improving the efficiency, Rick has opened an interesting topic: >If I want to perform a 4096 point real valued FFT using a complex routine >then I would combine 2*2048 samples into one "complex" input vector??? >The result would be a 4096 point complex output vector which is odd/even >symmetrical about bin N/2 48 (hence I would normally discard results >above N/2). >So how to combine that result with the second stage (i..e. the remaining >2048 samples) >and how to run the final pass? > >Has anybody done this on C6x or found more information on scrambling two >sequences? >Moroever, could you please direct me to the references Rick was talking about? >Would love to squeeze some MIPS out of the C67x... Thanks for your help! >Phil > >_____________________________________ >Note: If you do a simple "reply" with your email client, only the author >of this message will receive your answer. You need to do a "reply all" if >you want your answer to be distributed to the entire group. > >_____________________________________ >About this discussion group: > >To Join: Send an email to > >To Post: Send an email to > >To Leave: Send an email to > >Archives: http://www.yahoogroups.com/group/c6x > >Other Groups: http://www.dsprelated.com >">http://docs.yahoo.com/info/terms/ Rick Collins Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX |
Reply by ●March 12, 20022002-03-12
|
On 3/11/02 11:21 AM, "Arius - Rick Collins" <> wrote: > At 11:31 PM 3/10/02, khaild66 wrote: >> Hi C6x, >> I have a project that requires a Real FFT/IFFT algorithm. I >> found several DSP libraries (DY4 and Kanegineering). But I hate to >> have to pay $5000 to $5500 for a library when I really only need the >> real FFT function. TI's benchmarks web site has a listing for >> several FFTs, but they are all complex FFTs. >> If anyone knows where I can find efficient real FFT/IFF code I'd >> appreciate it if you would let me know. It would also help, if you >> know of a C67x DSP Library vendor that would be welling to sell just >> the FFT/IFFT portion. >> >> Thanks in advance >> >> Khalid > It has been awhile since I have done much work with FFTs, but let me add my > 2 cents worth here. > > The FFT is inherently a complex operation on complex data producing a > complex result. When people speak of a REAL FFT, they are really talking > about the REAL part of the result of processing a REAL input stream, > ignoring the imaginary part. > > So one way to process a real input stream is to fill the imaginary part > with zeros, run a full sized FFT and toss the imaginary part of the result > which contains no additional data, IIRC. If I am wrong about that, then > you need to combine the real and imaginary parts as the square root of the > sum of the squares. > > The efficiency of this can be improved upon by taking advantage of the > symmetry of the FFT result. This is where I get a little fuzzy on how it > works. The output of an FFT with real input data will be symmetrical. The > real part will have "even" symmetry and the imaginary part will have "odd" > symmetry. There is a simple way to put two REAL sequences into an FFT and > then extract them from the result as two separate sequences. In effect, > you can do a pair of N point, real input FFTs in one complex FFT. > > If you don't want to buffer up two input buffers, you can do one N point, > real input FFT using an N point transform and a final pass. Just consider > your N point real buffer to be two N/2 inputs and process them in a complex > N/2 FFT. Once you have extracted the two sets of results, you can then > perform a final pass to combine the two N/2 FFTs into a single N point > FFT. This will require that you do some processing with twiddle factors, > etc. > > So using the FFT on real data is not hard, but you will need to scan the > web to get the details on the "unscramble" pass and/or the FFT final > pass. Since it is only a single pass of the FFT, you likely don't need to > worry about getting the full efficiency out of the DSP. That is the tricky > part of coding FFTs on DSPs. > > Good luck! > Ok, now I'm confused. I always thought that input to FFT is a real data and output of FFT is a complex data. Physically, input is amplitude array of the signal that we want to find spectrum of and output is pairs of in-phase and quadrature of spectral bins, which could be used to find magnitude and phase of each spectral line. So, the statement that input to FFT is actually a complex number is new to me. Am I missing something here? Clarification would be appreciated. Mike. |
Reply by ●March 12, 20022002-03-12
|
At 06:46 PM 3/11/02, Mikhail Fridberg wrote: >On 3/11/02 11:21 AM, "Arius - Rick Collins" <> wrote: > > The FFT is inherently a complex operation on complex data producing a > > complex result. When people speak of a REAL FFT, they are really talking > > about the REAL part of the result of processing a REAL input stream, > > ignoring the imaginary part. > > > > So one way to process a real input stream is to fill the imaginary part > > with zeros, run a full sized FFT and toss the imaginary part of the result > > which contains no additional data, IIRC. If I am wrong about that, then > > you need to combine the real and imaginary parts as the square root of the > > sum of the squares. I am wrong about that. It is the upper vs. lower halves which are symmetric and have duplicate data in this case. So you can toss the data in one half. But you keep and process the real and imaginary data in the half you keep. :) ...snip... >Ok, now I'm confused. I always thought that input to FFT is a real data and >output of FFT is a complex data. Physically, input is amplitude array of the >signal that we want to find spectrum of and output is pairs of in-phase and >quadrature of spectral bins, which could be used to find magnitude and phase >of each spectral line. So, the statement that input to FFT is actually a >complex number is new to me. Am I missing something here? Clarification >would be appreciated. > >Mike. Whoever told you that the "normal" input to an FFT is real was mistaken. If you look at the calculations within an FFT, they are all based on complex arithmetic. So there is no way to use real data in performing an FFT. You can convert real data to complex in several ways including zeroing the imaginary part, but you MUST use complex data as the input to the calculation since it is defined as an operation on complex numbers. A complex series defines a waveform as a sum of rotating vectors which are like the polar coordinate equivalent of sine waves. A real sine wave can be thought of as two counter rotating vectors on the complex plane which are equal in frequency, phase and amplitude. In that case the imaginary parts cancel out and the real part remains. This helps to explain the result of the FFT on real input data (with zero imaginary parts) as having the symmetry it does. The real parts of the two vectors will be equal in all respects (even symmetry). The imaginary parts will have opposite signs (odd symmetry). This is reflected in the frequency results. BTW, rotating in opposite directions is equivalent to having positive and negative frequencies. :) Hows that for a mind bender??? This can be put to use in the real world. If you down convert a signal, you can produce a complex result (with non-zero imaginary data). If you down convert to a center freq of 0 Hz, you will have a signal centered around zero and your complex FFT result will contain valid, unique data in both the upper and lower halves of the FFT result; positive and negative frequencies, right? This is very common in digital receivers. I know this is not easy to learn intuitively. You need to look at the math and push around a few examples. Having a good teacher is very useful. I worked at Applied Signal Technology and learned a few things from John Treichler. They have video tapes of some of his lectures to us but I don't think they have ever provided them to anyone outside of APSG. I wish I had made copies while I was there. They explained a lot of good, clear DSP theory and practice. Rick Collins Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX |
Reply by ●March 12, 20022002-03-12
|
Question: Ok, now I'm confused. I always thought that input to FFT is a real data and output of FFT is a complex data. Physically, input is amplitude array of the signal that we want to find spectrum of and output is pairs of in-phase and quadrature of spectral bins, which could be used to find magnitude and phase of each spectral line. So, the statement that input to FFT is actually a complex number is new to me. Am I missing something here? Clarification would be appreciated. Mike. Answer: Inherently the FFT is a complex transform, as in it is hard to implement and optimize and as in it accepts complex data and produces complex data. When one writes the expression: X[k] = Sum x[n] e^-j*2*pi*n*k/N for the FFT, what usually misses the eye is that x[n] = xr[n] + jxi[n] and that x[n] has a real and imaginary part. However most real-world data is purely "real" as in simple numbers like 3, 255, 123, etc and not 2+3j, 4+5j which only exist in the math world. Therefore to apply an FFT on this one assumes all the imaginary terms to be zero, and the sequence becomes 3+0j, 255+0j, 123+0j. However the computation of the FFT results in a lot of wasted multiplies with zero, that people came up with efficent ways of computing FFT for real data that took advantage of symmetry. For those of you who really want to do this, take a look at "SPRA291" an excellent application note by Robert Matuziak of Texas Instruments titled, "Implementing Fast Fourier Trnasforms of Real Valued Sequences on the TMS320 family". He has got C code, and optimized assembly code detailing two possible approaches showing how to take TI's radix-4 complex FFT and use it along with the necessary modifications for implementing a real FFT. The date of this app note is Dec 1997. URL: http://www-s.ti.com/sc/psheets/spra291/spra291.pdf Regards Jagadeesh Sankaran |
Reply by ●March 14, 20022002-03-14
|
Thank you very much Jagadeesh. That's the kind of info that I was
looking for. It seems that, ultimately, in the C6x world real valued FFT computation needs to be carried out through the "packing" method (two real FFT input arrays packed into the real and imaginary parts of a complex FFT input). In the C3x world, there are implementations that are purely real FFT, which exploits the symmetry of the FFT of a real valued time series around frequency 0. The nice features were (1) The sine table required was of length N/2 (saves memory) (2) The output for a length N input data was a size N array (no redundant real and imaginary outputs). To go back to time domain, a corresponding IFFT algorithm, which used the same N/2 sine table, is implemented such that the input is a size N frequency domain array and the output is a size N real time series. The execution time was almost exactly half that of an N size complex FFT (no surprise here, but at least you don't have to worry about unpacking the output of a complex FFT). Of course this is comparing same radix size real and complex FFTs (in C3x radix-2 was optimum). The difference in the C6x is that radix-4 is optimum (generally higher radix results in smaller number of multiply and adds required, the C3x, however, is more suited to radix-2). I was under the impression that you could not do the packing trick in the reverse direction (IFFT), but on first glance, the App. Note you mentioned shows that it is possible, which is great! Regards, Khalid |
|
|
Reply by ●March 14, 20022002-03-14
|
The C3x algorithm you are describing is most likely one that does the "packing" of N real data points and does a N/2 FFT and then does the unpacking. There is nothing "real" about an FFT and the only other way I am aware of processing real data is to zero the imaginary part and do a N point FFT. The more you look at the FFT and the IFFT, you will realize that the two are really identical. The only difference comes from a 1/N scale factor that must be arbitrarily applied to the data at some point before you close the loop, so to speak. You can multiply by 1/N in the FFT, or you can do it in the IFFT, or you can scale both by SQRT(1/N). The FFT output will have different magnitudes in each case, but there is no factual basis for determining where it will be applied. But if you FFT data and then IFFT to get back the same data, you have to apply the 1/N scale factor before the data will match. I believe that there is a convention to use the 1/N scale factor in the IFFT and no scale factor on the FFT, but it is not universal. At 07:26 PM 3/13/02, wrote: >Thank you very much Jagadeesh. That's the kind of info that I was looking >for. It seems that, ultimately, in the C6x world real valued FFT >computation needs to be carried out through the "packing" method (two real >FFT input arrays packed into the real and imaginary parts of a complex FFT >input). > In the C3x world, there are implementations that are purely real > FFT, which exploits the symmetry of the FFT of a real valued time series > around frequency 0. The nice features were (1) The sine table required > was of length N/2 (saves memory) (2) The output for a length N input data > was a size N array (no redundant real and imaginary outputs). To go back > to time domain, a corresponding IFFT algorithm, which used the same N/2 > sine table, is implemented such that the input is a size N frequency > domain array and the output is a size N real time series. The execution > time was almost exactly half that of an N size complex FFT (no surprise > here, but at least you don't have to worry about unpacking the output of > a complex FFT). Of course this is comparing same radix size real and > complex FFTs (in C3x radix-2 was optimum). The difference in the C6x is > that radix-4 is optimum (generally higher radix results in smaller number > of multiply and adds required, the C3x, however, is m! >ore suited to radix-2). > I was under the impression that you could not do the packing trick > in the reverse direction (IFFT), but on first glance, the App. Note you > mentioned shows that it is possible, which is great! > >Regards, >Khalid > >_____________________________________ >Note: If you do a simple "reply" with your email client, only the author >of this message will receive your answer. You need to do a "reply all" if >you want your answer to be distributed to the entire group. > >_____________________________________ >About this discussion group: > >To Join: Send an email to > >To Post: Send an email to > >To Leave: Send an email to > >Archives: http://www.yahoogroups.com/group/c6x > >Other Groups: http://www.dsprelated.com >">http://docs.yahoo.com/info/terms/ Rick Collins Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX |
