Loading patent…
AssigneeInternational Business Machines Corporation
InventorShmuel Winograd
Estimating the term…
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 .multidot.n.sub.2 .multidot.....multidot.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. 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. After all loop input adds, multiplications, and output adds have been performed the resultant output vector is the Fourier transform of the original input vector. In addition to the actual transform procedure an input vector reordering operation must be performed and an output vector reordering operation.
A digital electronic computing system architecture for performing a discrete Fourier Transform on a plurality (N) of electrical input signals, wherein N is selected to be factorable into a plurality of mutually prime factors (n.sub.l) chosen from the group 2, 3, 4, 5, 7, 8, 9, 13 and 16, said system incorporating a nested loop solution method characterized by performing only vector additions and subtractions in the outer loops and scalar additions, subtractions and multiplies in the innermost loop, each loop operation being controlled by a unique control mechanism, dedicated to each said loop,
A digital electronic computing system architecture uniquely adapted for performing a discrete Fourier Transform on an N-dimensioned input signal vector wherein N is chosen so that it is factorable into a plurality of mutually prime factors (n.sub.l) chosen from the group consisting of 2, 3, 4, 5, 7, 8, 9, 13 and 16, said system including control means for effecting said transform utilizing a nested loop solution method wherein the various loops are each related to particular factors whose product equals the input vector dimension N, said nested loop solution method being characterized by the performance of vector additions and subtractions in the outer loops and all scalar additions, subtractions and multiplications in the innermost loop, wherein each loop operation is controlled by a unique dedicated loop operation control sequence based upon a unique optimized solution method for the particular factor to which said loop is related, said system architecture comprising as many arithmetic/logic units as there are loops for a particular transform solution and a dedicated memory for each of said arithmetic and logic units, the width of each arithmetic/logic unit and its associated memory associated with each outer loop operational sequence being sufficient to perform full vector width additions and subtractions as required of each outer loop sequence, the arithmetic and logic unit associated with each outer loop sequence includes only addition and subtraction functions, and wherein the arithmetic and logic unit associated with the innermost loop includes addition, subtraction and multiplication functions, the width of said innermost loop arithmetic unit being equal to the greatest number of addition, subtraction and multiplication operations which may be performed that do not require as an input the result of a prior addition, subtraction or multiplication operation, respectively, whereby maximum parallel operation is obtained, said control means including further means for causing inward loop transitions to occur whenever a multiply operation is encountered in an outer loop, and outward loop transitions to occur whenever an inner loop sequence is completed, said system further including means for transferring specified data subvectors on both inner and outer loop transitions.
Dependencies are inferred from the claim text.