High-speed bilinear algorithms for hardware implementation
Meghanad D. Wagh, Venkatram Muddhasani · 2006
This dissertation deals with the design of high-speed, bilinear algorithms for digital signal processing applications that are especially suited for implementation on dedicated hardware platforms. Bilinear algorithms exhibit a high degree of concurrency as all multiplication operations involved are independent of each other and can be computed at the same time. Consequently, the critical path delay for hardware implementations of these algorithms is very low. The algorithms developed here have other important properties such as a well defined recursive structure, modularity and low complexity. The first two properties are important for efficient mapping of the algorithm onto hardware and the last property helps in reducing hardware cost. Bilinear algorithms also have the advantage that two or more smaller algorithms can be used to obtain a larger, composite algorithm. This dissertation develops bilinear algorithms for the discrete Fourier transform (DFT) and the discrete cosine transform (DCT). We use concepts of group theory to identify computational blocks within the transform kernel that can be transformed into cyclic, skew-cyclic or Hankel structures. By combining bilinear algorithms for these structures we get the required bilinear algorithm of the transform. We deal with transform lengths ranging from 2 n to prime lengths and even lengths that are powers of odd primes. The algorithms thus obtained have a recursive structure and computational blocks developed for smaller algorithms can be used in the computation of larger algorithms of related lengths. To verify the concepts developed here, the DFT algorithms (of lengths 2n and 3 n) were synthesized using Mentor Graphics synthesis tools and laid out as an ASIC. A comparison of these algorithms against the fast Fourier transform (FFT) and the more recently developed quick Fourier transform (QFT) shows that, as expected, our algorithms perform better than these algorithms. For a 64-point DFT, the bilinear algorithm is twice as fast as the QFT and three times faster than the FFT. Further, its area complexity is half that of the QFT and about a fourth of the FFT complexity.