COMPUTATION OF PRIME FACTOR DFT AND DHT/DCCT ALGORITHMS USING CYCLIC AND SKEW-CYCLIC BIT-SERIAL SEMISYSTOLIC IC CONVOLVERS

作     者：GUDVANGEN, S HOLT, AGJ 

作者机构：Department of Electrical and Electronic Engineering University of Newcastle upon Tyne Merz Court Newcastle upon Tyne Tyne and Wear NE1 7RU UK 

出 版 物：《IEE PROCEEDINGS-G CIRCUITS DEVICES AND SYSTEMS》 (IEE Proc Part G Electron Circuit Syst)

年 卷 期：1990年第137卷第5期

页      面：373-389页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

主　　题：virtual machines prime factor decomposition transforms multiplexed pipelined machine Algorithms simple reconfiguration VLSI cyclic bit-serial semisystolic IC convolvers skew-cyclic bit-serial semisystolic IC convolvers discrete Fourier transforms pipeline processing Convolvers discrete cas-cas transform Very large scale integration array machine Transforms discrete Hartley transform pipelined bit-serial arithmetic Rader method digital arithmetic application specific integrated circuits ASIC throughput rate microprocessor chips recombination stage subspace evaluation VLSI building block processors fast Fourier transforms 

摘      要：The paper presents the results of a study of the use of cyclic and skew-cyclic convolvers for the evaluation of the subspace discrete Fourier transforms (DFT) and discrete Hartley transform (DHT) modules resulting from a prime factor decomposition of the DFT and the DHT/discrete cas-cas transform (DCCT), respectively. The method of Rader is employed to convert the subspace DFT/DHT modules into cyclic convolutions (CCs). These are further dissected into CCs and skew-cyclic convolutions (SCCs), respectively, of length ½(Ni − 1), where Ni is the DFT/DHT module length in the ith stage. That allows both real and complex DFT modules, as well as DHT modules, to be computed with the same convolver structure, by a simple reconfiguration of a recombination stage. This has important consequences for hardware implementations as only one type of convolver needs to be fabricated. A family of VLSI building block processors (BBPs) with pipelined bit-serial arithmetic is proposed. All inner products are computed in parallel within each BBP, resulting in a throughput rate inversely proportional to ½(Ni + 1). This leads to easy load balancing, which is discussed first in the context of a array machine and then in that of a multiplexed pipelined machine.