Open Collections

On the VLSI complexity and architecture of the Arithmetic Fourier Transform (AFT)

University of British Columbia

This thesis presents a novel logarithmic-depth VLSI network for implementing a fundamental computation of the Arithmetic Fourier Transform (AFT). The VLSI optimality —in terms of area-time trade-off— of this Orthogonal Flat Tree (OFT) network is proved. Namely, it is proven that the area of the network is 0(N2) and the corresponding total time delay is 0(log N). In addition, a number of layout rules for the construction of this network is proposed. The topology of this network is fairly simple and is based on an orthogonal interconnection of binary trees and linear arrays, or flat trees, where the nodes of the trees are bit-serial devices (adders and distributed shift registers). This OFT network uses only a small number of bit-serial adders to implement a matrix-vector multiplication. Moreover, two architectures for the computational area are considered and their respective bounds are proved. From this discussion it can be concluded that the interconnection area is dominant as the area for computation is relatively small of the order Nlog²N. In addition, an upper-bound on the area of the butterfly network , proposed in [31] for the first stage of the AFT, is introduced. This network computes the Bruns averages vector which constitutes one of the inputs to the OFT network. These two networks can lead to a practical implementation of the AFT. Finally, the oversampling problem of the AFT algorithm is also studied. When using the butterfly network it is proved that to obtain all the samples required takes an area slightly larger than 0(N2) which can result in a non-optimal AT2 bound. This is due to the large number that need to be averaged, up to 2N numbers, for a single multiple-input AFT butterfly. However, for practical sizes (N=16, 32) of a butterfly network the AT2 bound is very close to the optimal bound.

Thesis/Dissertation

application/pdf

2009-02-26

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/5177

Electrical and Computer Engineering

University of British Columbia

UBCV

DSpace