The Arithmetic Cube

We present the design of a VLSI processor which can be programmed to compute the discrete Fourier transform of a sequence of n points and which achieves the theoretical AT² lower bound of ¿(n²) for n ¿ n where n is an infinite set. Furthermore, since the set n is also sufficiently dense, the processor achieves for any n the theoretical AT² lower bound of ¿(n²) for computing the cyclic convolution of two sequences of n points. Uniquely, our design achieves this bound without the use of data shuffling or long wires. Also, the processor uses only approximately ¿n multipliers, while many other designs need ¿(n) multipliers to achieve the same time bounds. Since multipliers are usually much larger than adders, the processor presented in this paper should be smaller. The design also features layout regularity, minimal control, and nearest neighbor interconnect of arithmetic cells of a few different types. These characteristics make it an ideal candidate for VLSI implementation.