VLSI architectures for computing the arithmetic Fourier transform

Modular and area-efficient VLSI architectures are proposed for computing the arithmetic Fourier transform (AFT). By suitable 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 proposed design employs 2N+1 PEs to compute 2N+1 Fourier coefficients. Each PE has an adder and a fixed amount of local storage and one PE has a multiplier. I/O with the host is performed using a fixed number of channels. The design achieves O(N) speed up. Compared with known designs for AFT, the proposed design uses significantly less PEs and supports real-time applications. This design can be extended to achieve linear speed up in a fixed size array with 2p+1 PEs, 1⩽p⩽N