Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations
Hardware-based implementations of the Fast Fourier Transform (FFT) are highly regarded as they provide improved performance characteristics with respect to software-based sequential solutions. Due to the high number of operations involved in calculations, most hardware-based FFT approaches completel...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-03-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2079-9292/7/3/33 |
| _version_ | 1798003767461806080 |
|---|---|
| author | Felipe Minotta Manuel Jimenez Domingo Rodriguez |
| author_facet | Felipe Minotta Manuel Jimenez Domingo Rodriguez |
| author_sort | Felipe Minotta |
| collection | DOAJ |
| description | Hardware-based implementations of the Fast Fourier Transform (FFT) are highly regarded as they provide improved performance characteristics with respect to software-based sequential solutions. Due to the high number of operations involved in calculations, most hardware-based FFT approaches completely or partially fold their structure to achieve an efficient use of resources. A folding operation requires a permutation block, which is typically implemented using either permutation logic or address generation. Addressing schemes offer resource-efficient advantages when compared to permutation logic. We propose a systematic and scalable procedure for generating permutation-based address patterns for any power-of-2 transform size algorithm and any folding factor in FFT cores. To support this procedure, we develop a mathematical formulation based on Kronecker products algebra for address sequence generation and data flow pattern in FFT core computations, a well-defined procedure for scaling address generation schemes, and an improved approach in the overall automated generation of FFT cores. We have also performed an analysis and comparison of the proposed hardware design performance with respect to a similar strategy reported in the recent literature in terms of clock latency, performance, and hardware resources. Evaluations were carried on a Xilinx Virtex-7 FPGA (Field Programmable Gate Array) used as implementation target. |
| first_indexed | 2024-04-11T12:13:09Z |
| format | Article |
| id | doaj.art-9da99493582645b187a8c13ea34e4374 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-04-11T12:13:09Z |
| publishDate | 2018-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-9da99493582645b187a8c13ea34e43742022-12-22T04:24:33ZengMDPI AGElectronics2079-92922018-03-01733310.3390/electronics7030033electronics7030033Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT ImplementationsFelipe Minotta0Manuel Jimenez1Domingo Rodriguez2Electrical and Computer Engineering Department, University of Puerto Rico at Mayagüez, Mayagüez 00681-9000, Puerto RicoElectrical and Computer Engineering Department, University of Puerto Rico at Mayagüez, Mayagüez 00681-9000, Puerto RicoElectrical and Computer Engineering Department, University of Puerto Rico at Mayagüez, Mayagüez 00681-9000, Puerto RicoHardware-based implementations of the Fast Fourier Transform (FFT) are highly regarded as they provide improved performance characteristics with respect to software-based sequential solutions. Due to the high number of operations involved in calculations, most hardware-based FFT approaches completely or partially fold their structure to achieve an efficient use of resources. A folding operation requires a permutation block, which is typically implemented using either permutation logic or address generation. Addressing schemes offer resource-efficient advantages when compared to permutation logic. We propose a systematic and scalable procedure for generating permutation-based address patterns for any power-of-2 transform size algorithm and any folding factor in FFT cores. To support this procedure, we develop a mathematical formulation based on Kronecker products algebra for address sequence generation and data flow pattern in FFT core computations, a well-defined procedure for scaling address generation schemes, and an improved approach in the overall automated generation of FFT cores. We have also performed an analysis and comparison of the proposed hardware design performance with respect to a similar strategy reported in the recent literature in terms of clock latency, performance, and hardware resources. Evaluations were carried on a Xilinx Virtex-7 FPGA (Field Programmable Gate Array) used as implementation target.http://www.mdpi.com/2079-9292/7/3/33Discrete Fourier TransformFast Fourier TransformLinear TransformPease Factorizationscalable address generationDigital Signal Processinghardware generation |
| spellingShingle | Felipe Minotta Manuel Jimenez Domingo Rodriguez Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations Electronics Discrete Fourier Transform Fast Fourier Transform Linear Transform Pease Factorization scalable address generation Digital Signal Processing hardware generation |
| title | Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations |
| title_full | Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations |
| title_fullStr | Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations |
| title_full_unstemmed | Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations |
| title_short | Automated Scalable Address Generation Patterns for 2-Dimensional Folding Schemes in Radix-2 FFT Implementations |
| title_sort | automated scalable address generation patterns for 2 dimensional folding schemes in radix 2 fft implementations |
| topic | Discrete Fourier Transform Fast Fourier Transform Linear Transform Pease Factorization scalable address generation Digital Signal Processing hardware generation |
| url | http://www.mdpi.com/2079-9292/7/3/33 |
| work_keys_str_mv | AT felipeminotta automatedscalableaddressgenerationpatternsfor2dimensionalfoldingschemesinradix2fftimplementations AT manueljimenez automatedscalableaddressgenerationpatternsfor2dimensionalfoldingschemesinradix2fftimplementations AT domingorodriguez automatedscalableaddressgenerationpatternsfor2dimensionalfoldingschemesinradix2fftimplementations |