Computer system architecture for performing nested loop operations to effect a discrete Fourier transform

摘要

A computer system architecture and method for performing the Discrete Fourier Transform on a set of N sampled input signals wherein N is chosen to be the product of a group of predetermined relatively prime factors (n. sub.1 ·n.sub.2 ·...·n.sub.L). The present architecture then proceeds to the solution of the Fourier transform via a unique nested loop solution method, wherein each loop is specifically related to each factor and wherein no multiplications are performed in the outer loops said method being further characterized by the fact that the system control is automatically passed to the next inner loop whenever a multiplication instruction is encountered. A unique predetermined sequence of operations which is unique to each factor (n. sub.l) is built into the system controls and automatic control means proceed from one sequence to another depending upon the factors (n) associated with a chosen N. The unique set of instruction sequences for each small factor of (n) is predicated upon a unique solution for the small Fourier transform matrix associated with said factor.P P Means are included in the system so that in all outer loops all addition operations required are performed on vector quantities and, in the single innermost loop, additions and multiplications are performed on scalar quantities. Means are additionally provided for determining composite coefficients to be used in multiplications occuring in the innermost loop, said composite coefficients comprising the product of the multiplication coefficient to be currently performed in the innermost loop as well as the coefficient essential with each pseudo multiply in each outermost loop currently involved in the current innermost loop computation.PPAfter all loop input adds, multiplications, and output adds have been performed the resultant output vector is the Fourier transform of the original input vector.P PIn addition to the actual transform procedure an input vector reordering operation must be performed and an output vector reordering operation.