Fixed size array architectures for computing arithmetic Fourier transform

The authors propose modular and area efficient VLSI architectures for computing the arithmetic Fourier transform (AFT). The proposed design uses 2p+1 PEs and external memory of size O(N) to compute 2N+1 Fourier coefficients, 1⩽p⩽N. Each PE has an adder and a fixed amount of local storage and one PE has a multiplier. Input/output (I/O) with the host is performed using a fixed number of channels. By suitable choice of the I/O schedule and activation of PEs, nonuniform data dependencies in the AFT computation, which require nonequidistant inputs and assignment of Mobius function values are resolved. The design achieves linear speedup and can also be used to compute the discrete cosine transform