COMPUTER SYSTEM ARCHITECTURE FOR PERFORMING NESTED LOOP OPERATIONS TO EFFECT A DISCRETE FOURIER TRANSFORM

摘要

COMPUTER SYSTEM ARCHITECTURE FORPERFORMING NESTED LOOP OPERATIONS TOEFFECT A DISCRETE FOURIER TRANSFORMAbstract of the DisclosureA computer system architecture and method for performing theDiscrete Fourier Transform on a set of N sampled input signals whereinN is chosen to be the product of a group of predetermined relativelyprime factors (n1?n2?...?nL). The present architecture then proceedsto the solution of the Fourier transform via a unique nested loopsolution method, wherein each loop is specifically related to each factorand wherein no multiplications are performed in the outer loops said methodbeing further characterized by the fact that the system control isautomatically passed to the next inner loop whenever a multiplicationinstruction is encountered. A unique predetermined sequence of operationswhich is unique to each factor (n?) is built into the system controlsand automatic control means proceed from one sequence to another dependingupon the factors (n) associated with a chosen N. The unique set ofinstruction sequences for each small factor of (n) is predicated upon aunique solution for the small Fourier transform matrix associated withsaid factor.Means are included in the system so that in all outer loopsall addition operations required are performed on vector quantities and,in the single innermost loop, additions and multiplications are performedon scalar quantities. Means are additionally provided for determiningcomposite coefficients to be used in multiplications occuring in the innermostloop, said composite coefficients comprising the product of the multiplicationcoefficient to be currently performed in the innermost loop as well asthe coefficient essential with each pseudo multiply in each outermostloop currently involved in the current innermost loop computation.-1-After all loop input adds, multiplications, and output addshave been performed the resultant output vector is the Fourier transformof the original input vector.In addition to the actual transform procedure an input vectorreordering operation must be performed and an output vector reorderingoperation.