Design and implementation of low complexity fast Fourier transform architecture
Hasanin, Mohamad Elsayed Hussein Ali (2020)
2020
Tietotekniikan DI-tutkinto-ohjelma - Degree Programme in Information Technology, MSc (Tech)
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-20
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202004273927
https://urn.fi/URN:NBN:fi:tuni-202004273927
Tiivistelmä
This thesis discusses the problem of the large area consumption required to perform fast Fourier transform (FFT) operations. Fast Fourier transform architectures require a large amount of processing elements to perform its operation. The larger the required FFT size, the more processing elements needed and, therefore, a larger implementation area needed. The main sources for the area consumption are the large number of multiplications FFT computations.
In this thesis, a study has been made about most common FFT architectures like memory based FFT architectures and pipelined FFT architectures. Moreover, some studies have been made about the previously implemented FFT butterfly architectures, and some ideas about how to optimize area in the entire FFT system and inside FFT butterflies.
The objective of the thesis is to optimize the area usage inside a single FFT butterfly. Area optimization is achieved by developing a unified FFT butterfly architecture that contains multiradix FFT architectures. That concept enables the usage of fewer amount of FFT butterflies inside the system to achieve larger FFT operations. In addition, by using shift-add concept instead of multipliers, the area can be optimized significantly. Memory organization has been put into consideration when implementing the proposed FFT architectures, which implied the need of sequential version of the FFT butterflies. All these concepts were mixed together to result in a final version that is the best area-optimized in this thesis.
After implementing the various versions of FFT architectures using sharing resources, sequential processing, and shift-add concepts, their results were compared into the previously implemented traditional version. The final proposed architectures, which are sequential and multiplierless radix-2, 3, 4, 5, and multi-radix FFT architectures. From the comparison results, the proposed implementations achieved thesis objectives, resulting in about 60% of area reduction compared to the previously implemented FFT butterflies’ architectures.
In this thesis, a study has been made about most common FFT architectures like memory based FFT architectures and pipelined FFT architectures. Moreover, some studies have been made about the previously implemented FFT butterfly architectures, and some ideas about how to optimize area in the entire FFT system and inside FFT butterflies.
The objective of the thesis is to optimize the area usage inside a single FFT butterfly. Area optimization is achieved by developing a unified FFT butterfly architecture that contains multiradix FFT architectures. That concept enables the usage of fewer amount of FFT butterflies inside the system to achieve larger FFT operations. In addition, by using shift-add concept instead of multipliers, the area can be optimized significantly. Memory organization has been put into consideration when implementing the proposed FFT architectures, which implied the need of sequential version of the FFT butterflies. All these concepts were mixed together to result in a final version that is the best area-optimized in this thesis.
After implementing the various versions of FFT architectures using sharing resources, sequential processing, and shift-add concepts, their results were compared into the previously implemented traditional version. The final proposed architectures, which are sequential and multiplierless radix-2, 3, 4, 5, and multi-radix FFT architectures. From the comparison results, the proposed implementations achieved thesis objectives, resulting in about 60% of area reduction compared to the previously implemented FFT butterflies’ architectures.