Sum and difference conjugate discrete Fourier transform

摘要

A special purpose computer and method of computation for performing an N-length discrete Fourier transform (DFT) using a sum and difference conjugate prime factor transform. The transform length N is selected as equal to the product of L mutually prime factors N.sub.1, N. sub.2, . . . , N.sub.i, . . . , N.sub.L. For each one of the L mutually prime factors N. sub.i, an N.sub.i -length DFT is performed. Each N.sub.i -length DFT transform is performed using a data processing element called a kernel. Each kernel includes one or more memory elements for reordering data and a computational element. The computational element includes adder circuit means for forming the sum term, SUM(n.sub.i) equal to the quantity x(n. sub.i)+x(N.sub.i -n.sub.i) and the difference term, DIFF(n. sub.i) equal to x(n.sub.i)-x(N.sub.i -n.sub.i).