Hi forum, I have a complex input FFT core implementation for FPGA. Now I want redesign the core to reduce the logic for real input sequences. I use SDF (single delay feedback) architecture. Output is 1 complex sample per clock. The standard 2N real FFT with N complex FFT doesn't work for me. The difference between 2N and N point FFTs is only one butterfly stage (one complex multiplication and 2 complex addition). But this will be compensated with post processing stage which has 4 real multiplications and 4 additions. So what I save? Nothing. Is there any other way to implement real point FFT which will reduce the logic? Thank you very much, Tiksan
real input FFT for SDF architecture
Started by ●October 18, 2011
Reply by ●October 19, 20112011-10-19
On Oct 18, 11:57�am, "Syswip" <syswip@n_o_s_p_a_m.gmail.com> wrote:> Hi forum, > > I have a complex input FFT core implementation for FPGA. Now I want > redesign the core to reduce the logic for real input sequences. > I use SDF (single delay feedback) architecture. Output is 1 complex sample > per clock. > The standard 2N real FFT with N complex FFT doesn't work for me. > The difference between 2N and N point FFTs is only one butterfly stage (one > complex multiplication and 2 complex addition). But this will be > compensated with post processing stage which has 4 real multiplications and > 4 additions. > So what I save? Nothing.So a 2N uses the same amount of memory as an N ??!! Well ... I suppose it could ... if you use the 2N real with an N complex technique.> Is there any other way to implement real point FFT which will reduce the > logic?Yes, there are other ways, but they often lead to irregular architectures. Read the literature. Kevin McGee
Reply by ●October 19, 20112011-10-19
>On Oct 18, 11:57=A0am, "Syswip" <syswip@n_o_s_p_a_m.gmail.com> wrote: >> Hi forum, >> >> I have a complex input FFT core implementation for FPGA. Now I want >> redesign the core to reduce the logic for real input sequences. >> I use SDF (single delay feedback) architecture. Output is 1 complexsampl=>e >> per clock. >> The standard 2N real FFT with N complex FFT doesn't work for me. >> The difference between 2N and N point FFTs is only one butterfly stage(o=>ne >> complex multiplication and 2 complex addition). But this will be >> compensated with post processing stage which has 4 real multiplicationsa=>nd >> 4 additions. >> So what I save? Nothing. > >So a 2N uses the same amount of memory as an N ??!! Well ... I >suppose it could ... if you use the 2N real with an N complex >technique. > >> Is there any other way to implement real point FFT which will reducethe>> logic? > >Yes, there are other ways, but they often lead to irregular >architectures. Read the literature. > >Kevin McGee >Hi Kevin McGee, Could you please recommend me some literature? I googled a lot but didn't find anything useful.
Reply by ●October 20, 20112011-10-20
On Oct 19, 3:45�pm, "Syswip" <syswip@n_o_s_p_a_m.gmail.com> wrote:> Could you please recommend me some literature? I googled a lot but didn't > find anything useful.Step 1: Search for 'pruned + FFT + architectures.' I think you get about 348,000 hits. Step 2: Read and understand all 348,000. Pruning is one way to get rid of extraneous calculations when your inputs are real only. Using the '2N real with an N complex' is another. Many software and hardware designers use it. But I think that just exploring real only graphs and architectures would be a huge mistake. It is abundantly clear to me that you need a much stronger background in FFT basics. Two references for basic info would be: "L. R. Rabiner, B. Gold, Theory and Application of Digital Signal Processing." Englewood Cliffs, NJ, Prentice-Hall, 1975." Chapters 6 and 10 are important for FFT (and the DFT sections are valuable, too). Another is: Tran-Thong, "Algebraic Formulation of the Fast Fourier Transform," IEEE Circuits and Systems magazine, vol. 3, no. 2, June 1981, pp. 9-19. And that's just for starters. There are literally hundreds if not a thousand or more references that you would need to know about. You can't learn this stuff in a day, or a week, or a month, or a year. It takes years ... literally. And you have to have an aptitude or natural talent for it. Kevin McGee
Reply by ●October 20, 20112011-10-20
On 10/18/2011 8:57 AM, Syswip wrote:> Hi forum, > > I have a complex input FFT core implementation for FPGA. Now I want > redesign the core to reduce the logic for real input sequences. > I use SDF (single delay feedback) architecture. Output is 1 complex sample > per clock. > The standard 2N real FFT with N complex FFT doesn't work for me. > The difference between 2N and N point FFTs is only one butterfly stage (one > complex multiplication and 2 complex addition). But this will be > compensated with post processing stage which has 4 real multiplications and > 4 additions. > So what I save? Nothing. > Is there any other way to implement real point FFT which will reduce the > logic? > > Thank you very much, > Tiksan > > >What might you expect to save? Surely N memory locations out of 2N at the input (counting 1 for real and 1 for imaginary) and 2N memory locations out of 4N at the output considering conjugate symmetry is something. Some might think that's a lot. But maybe you're relatively insensitive to memory/register requirements? I think that doubling up on real samples going into a complex FFT block halves the processing time (roughly) by processing 2N real samples in the place of a presumed N complex samples. That is, the processing time is fixed and the number of samples is doubled. But, I hasten to add that this is just one limited perspective. I'm not sure about your assertion re: reducing by one butterfly stage because the point is to *use* a complex-input FFT structure while *knowing* that it's really 2N real inputs. Seems to me that the operations remain the same internal to the block and, yes, there is some rearranging to do at the output if you want to see a full 4N array (2N complex) with the symmetry. It seems like you want to save clocks more than anything... is that right? In that case I don't know what to suggest because I'm ignorant on that subject. But, for others, you might be clearer on your ultimate objective. e.g. when you say "reduce the logic" are you thinking "1 clock", "5% of the gates", 50% of something??? Folks could spin their wheels on "1 clock" just to find that it's much too small a goal for you. Fred
Reply by ●October 21, 20112011-10-21
>On 10/18/2011 8:57 AM, Syswip wrote: >> Hi forum, >> >> I have a complex input FFT core implementation for FPGA. Now I want >> redesign the core to reduce the logic for real input sequences. >> I use SDF (single delay feedback) architecture. Output is 1 complexsample>> per clock. >> The standard 2N real FFT with N complex FFT doesn't work for me. >> The difference between 2N and N point FFTs is only one butterfly stage(one>> complex multiplication and 2 complex addition). But this will be >> compensated with post processing stage which has 4 real multiplicationsand>> 4 additions. >> So what I save? Nothing. >> Is there any other way to implement real point FFT which will reducethe>> logic? >> >> Thank you very much, >> Tiksan >> >> >> >What might you expect to save? >Surely N memory locations out of 2N at the input (counting 1 for real >and 1 for imaginary) and 2N memory locations out of 4N at the output >considering conjugate symmetry is something. Some might think that's a >lot. But maybe you're relatively insensitive to memory/register >requirements? > >I think that doubling up on real samples going into a complex FFT block >halves the processing time (roughly) by processing 2N real samples in >the place of a presumed N complex samples. That is, the processing >time is fixed and the number of samples is doubled. But, I hasten to >add that this is just one limited perspective. > >I'm not sure about your assertion re: reducing by one butterfly stage >because the point is to *use* a complex-input FFT structure while >*knowing* that it's really 2N real inputs. Seems to me that the >operations remain the same internal to the block and, yes, there is some >rearranging to do at the output if you want to see a full 4N array (2N >complex) with the symmetry. > >It seems like you want to save clocks more than anything... is that >right? In that case I don't know what to suggest because I'm ignorant >on that subject. But, for others, you might be clearer on your ultimate >objective. e.g. when you say "reduce the logic" are you thinking "1 >clock", "5% of the gates", 50% of something??? Folks could spin their >wheels on "1 clock" just to find that it's much too small a goal for you. > >Fred > > >Thank you very much guys.
