The Arithmetic Cube

Robert Michael Owens, Mary Jane Irwin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 AT2 lower bound of Ω(n2) 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 AT2 lower bound of Ω(n2) 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 [formula omitted] 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.

Original languageEnglish (US)
Pages (from-to)1342-1348
Number of pages7
JournalIEEE Transactions on Computers
Issue number11
StatePublished - Nov 1987

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'The Arithmetic Cube'. Together they form a unique fingerprint.

Cite this