Title :
Negacyclic convolution using polynomial transforms on hypercubes
Author_Institution :
Thayer Sch. of Eng., Dartmouth Coll., Hanover, NH, USA
fDate :
8/1/1992 12:00:00 AM
Abstract :
A polynomial-transform-based algorithm for calculating products modulo Zn+1 on a hypercube is presented. All interprocessor communication in this algorithm occurs over a Hamming distance of one; that is processors communicate only with their immediate neighbors. This algorithm has been implemented on a Connection Machine, and the performance results are discussed. Current figures show a time of 358 ms for negacyclic convolution of 1 K 16 bit samples, up to about 8 s for a 64 K data set. The authors discuss the use of this algorithm in the calculation of convolution, compare communication costs with the FFT, and discuss directions for future work
Keywords :
computerised signal processing; hypercube networks; parallel algorithms; polynomials; transforms; Connection Machine; Hamming distance; digital signal processing; hypercubes; interprocessor communication; negacyclic convolution; polynomial transforms; Arithmetic; Contracts; Convolution; Costs; Hamming distance; Hypercubes; Multidimensional systems; Multiprocessor interconnection networks; Polynomials; Signal processing algorithms;
Journal_Title :
Signal Processing, IEEE Transactions on
