Distributed arithmetic realisation of cyclic convolution and its DFT application

H. C. Chen*, Jiun-In Guo, C. W. Jen, Tian-Sheuan Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The authors present a new hardware-efficient group distributed arithmetic (GDA) design approach for the one-dimensional (1-D) discrete Fourier transform (DFT). The approach adopts distributed arithmetic (DA) computation and exploits the good features of cyclic convolution to facilitate an efficient realisation of the 1-D N-point DFT using small ROM modules, a barrel shifter, and N accumulators. The proposed GDA design is achieved by rearranging the contents of the ROM into several groups such that all the elements in a group can be accessed simultaneously in accumulating all the DFT outputs to increase ROM utilisation. Moreover, combining the symmetrical property of the DFT coefficients with the proposed GDA design requires only half the ROM contents to be stored, which further reduces ROM size by a factor of two. Realisation of a long-length DFT formulated in cyclic convolution is based on data permutation of the rows and columns in the matrix to directly partition the long-length cyclic convolution into short ones, so that short length DFTs may be realised efficiently by the proposed GDA design to achieve low hardware cost. This design approach is termed the 'block-based group distributed arithmetic approach'. Compared with existing systolic array designs and DA-based designs, the proposed GDA design can reduce the delay-area product by 29%-68% based on a 0.35 μm CMOS cell library.

Original languageEnglish
Pages (from-to)615-629
Number of pages15
JournalIEE Proceedings: Circuits, Devices and Systems
Issue number6
StatePublished - 1 Dec 2005

Fingerprint Dive into the research topics of 'Distributed arithmetic realisation of cyclic convolution and its DFT application'. Together they form a unique fingerprint.

Cite this