COMPUTATION OF THE FAST FOURIER-TRANSFORM ON THE STAR-CONNECTED CYCLENETWORKS

Two parallel algorithms for computing fast Fourier transform (FFT) on a new type of architecture called the n-star-connected cycles (n-SCC) have been considered. The n-SCC architecture is based on the n-star in terconnection graph and has all the desirable features which exist in the n-star interconnection graph. To demonstrate the main properties o f an n-SCC network. we present two parallel algorithms for computing t he FFT. These algorithms are based on the Cooley-Tukey FFT algorithm a nd combine the principles of parallelism and pipelining. Considering t he same number of inputs, the second algorithm in this paper has bette r performance in compare to the algorithm implemented on star graph. C opyright (C) 1996 Elsevier Science Ltd