Design of Systolic Algorithms and Architectures for Digital Signal Processing

摘要

In this thesis, the design methods of systolic algorithms and architectures arestudied. Several systolic algorithms and systolic architectures have been developed for implementations of different transformations, the least squares problem and the circular convolution. A new systolic algorithm based on the even-odd decomposition method is first proposed. The algorithm provides an efficient way to reduce the array size of the discrete Fourier transform and the discrete Hartley transform. Using this algorithm, several important systolic architectures are derived, where the sizes of the arrays are only one fourth or one sixteenth of the original size. Next, two systolic architectures for the least squares problem are introduced. The algorithms and their mapping to the implementation are studied and each is shown to have some advantages over existing architectures. One of them, is derived using the orthogonal-inverse updating algorithm. By this means, the resulting architecture is decreased from two triangular systolic arrays to only one. Finally, an algorithm for performing the circular convolution is proposed based on the Chinese remainder theorem.