This dissertation presents a formal hardware design approach using bilinear algorithms for fast digital signal processing (DSP) applications. In particular, we focus on the design of application specific integrated circuit (ASIC), where dedicated algorithmic accelerators are implemented in fixed-point arithmetic.

Most signal processing algorithms involve a transform kernel with a known structure. Using concepts of group theory, the kernel matrix can be recursively partitioned into computations of small length of cyclic convolutions and Hankel matrix products. Bilinear algorithms for these smaller blocks are then combined together to obtain the required bilinear algorithm of the transform. Bilinear algorithms have a high degree of concurrency as all multiplication operations are independent of each other and can be computed at the same time. As a result, the hardware realizations of bilinear algorithms are much faster than any other implementations. The structural modularity also allows simple pipelining and greatly reduces the number of input and output (IO) pins.

In this dissertation, we develop new bilinear algorithms and implementations for the discrete Hartley transform (DHT), the modified discrete cosine transform (MDCT) and the modulated complex lapped transform (MCLT). In case of bilinear DHT algorithms, we show that the kernel divisions are identical for all prime power lengths. Our implementations are 20%-60% faster than existing implementations. For MPEG-1/2 audio layer III (MP3) application, our proposed MDCT algorithms have about 30% lower computational complexity as compared with other fast algorithms in the literature. The modularity of our algorithms also permits one to design, for the first time, a unified architecture for forward and inverse transforms using different MP3 block sizes. In case of the MCLT, we achieve a bilinear algorithm by merging the external sine window function with the main computation through trigonometric manipulations. As compared with most algorithms, our MCLT algorithm requires about N -less multiplications, where the typical block size, N, for applications such as audio watermarking is 2048.