US 4,604,721 AGranted

Computer and method for high speed prime factor transform

AssigneeTRW Inc.

InventorJoseph H. Gray

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.1, . . . , 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).

Claims15

Dependent claims

A computer for performing an N-length discrete Fourier transform of N initial data values, where the number N equals the product of a number L of mutually prime factors N.sub.1, N.sub.2, . . . N.sub.i, N.sub.i +1, . . . N.sub.L, comprising:

(a) a set of one or more kernels;
(b) each kernel being adapted to perform a discrete Fourier transform characterized by a transform length equal to one or more of said prime factors N.sub.i ;
(c) wherein for each value of i in the range from 1 to L, said set of kernels includes a kernel adapted to perform a N.sub.i -length transform;
(d) wherein each kernel includes:
first reorder means for receiving N input data values and reordering them into (N/N.sub.i) groups, with each group consisting of N.sub.i input data values x(n), n=0, 1, 2, . . . N.sub.i -1,
computational means for performing a sum and difference conjugate N.sub.i -length discrete Fourier transform upon each of the (N/N.sub.i) groups of N.sub.i reordered input data values x(n), thereby producing (N/N.sub.i) groups of N.sub.i transformed data values X(k), for k=0, 1, 2, . . . N.sub.i -1, and
second reorder means for reordering the (N/N.sub.i) groups of N.sub.i transformed data values X(k) into N output data values, wherein N.sub.i equals any of said transform lengths for which that kernel is adapted to perform a discrete Fourier transform;
(e) means for connecting said N initial data values to the kernel performing the N.sub.1 -length transform so that said initial data values are received as the N input data values of the N.sub.1 -length transform;
and
(f) for each value of i in the range from 1 to L-1, means for connecting the N output data values produced by the kernel performing the N.sub.i -length transform to the kernel performing the N.sub.i+1 -length transform so that said output data values are received as the N input data values of the N.sub.i+1 -length transform;
(g) whereby the N output data values produced by the kernel performing the N.sub.L -length transform are the N-length discrete Fourier transform of the N initial data values.

8 more elements

(a) L kernels designated the 1st kernel, 2nd kernel, . . . i-th kernel, (i+1)-th kernel, . . . and the L-th kernel;
(b) wherein the i-th kernel , for i ranging from 1 to L, produces N output data values;
(c) wherein the 1st kernel receives as its N input data values the N initial data values;
(d) wherein the i-th kernel, for i ranging from 2 to L, receives as its N input data values the N output data values produced by the preceding (i-1)-th kernel;
and
(e) wherein the i-th kernel, for i ranging from 1 to L, includes
first reorder means for reordering the N input data values received by the i-th kernel into (N/N.sub.i) groups, with each group consisting of N.sub.i input data values x(n), n=0, 1, 2, . . . N.sub.i -1,
computational means for performing a sum and difference conjugate N.sub.i -length discrete Fourier transform upon each of the (N/N.sub.i) groups of N.sub.i reordered input data values x(n), thereby producing (N/N.sub.i) groups of N.sub.i transformed data values X(k), for k=0, 1, 2, . . . N.sub.i -1, and
second reorder means for reordering the (N/N.sub.i) groups of N.sub.i transformed data values X(k) into N output data values;
(f) whereby the N output data values produced by the L-th kernel are the N-length discrete Fourier transform of the N initial data values.

7 more elements

Dependencies are inferred from the claim text.