Summary:
The scope of the thesis is the exploration of the Butterfly Computation Unit, and the introduction of two alternative architectures for the implementation of the said unit.
The Butterfly Computation Unit is the most essential unit for the implementation of the algorithm of the Fast Fourier Transform, for Decimation in Time, that is used widely in applications for Digital Signals Processing like Spectral Analysis, Data Compression, and in solving Partial Differential equations, Filtering algorithms, Polynomial Multiplication and Convolution.
The purpose of this thesis is the exploration of a conventional implementation of the Butterfly Computation Unit, but also three more alternative schemes that have been designed in order to be more efficient than the conventional one.
Specifically, we propose the use of the Gauss algorithm for multiplying two complex numbers as this operation contains the largest computational effort in the Butterfly Computation Unit. Also, we proposed the use of pre-encoded multipliers to implement the complex number multiplication unit, in order to further improve its functioning, in juxtaposition with the conventional implementation, which uses Modified Booth multipliers.
The units described above have been implemented, using Verilog hardware description language, next, their functionality has been behaviorally verified and we synthesized the circuits in order to experimentally compare them in delay, area and power consumption, using the Synopsys tools.
Lastly, we presented the results that arose, and we also presented a comparative study for various input bit-widths. This way, we reached the necessary conclusions for the operation of the different proposed schemes that we designed and implemented, and according to the findings each proposed scheme showed its advantages, depending on the application that they are targeted for, where they appear to perform optimally.
Keywords:
Fast Fourier Transform, Buttergly Computation Unit, Modified Booth, Gauss’s Algorithm, ASIC, VLSI
