Addressable memory fft processor with exponential term generation

Claim 2

A special purpose digital computer for implementing the fast Fourier transform, the computer comprising: a data store for storing the real and imaginary parts Xl 1 and Yl 1 of the terms Al 1; an address register for storing the address of a term; pulse generator means connected to said address register for progressively stepping the stored address cyclically through all values thereof during each level of computation; a level register for storing a bit identifying the level l of the computation; means responsive to each stored address in said address register and the level bit in said level register to extract the values Xl 1(1), Yl 1(1), Xl 1(0) and Yl 1(0) from said data store and for producing a signal representative of the value of theta from the most significant bits of the stored address; means connected to said means for extracting and producing thereby to receive said extracted values Xl 1(1) and Yl 1(1) and said signal representative of the value of theta for effecting vector rotation of said values Xl 1(1) and Yl 1(1) through an angle having said value of theta , said means for effecting rotation including means for operating iteratively upon the values Xl 1(1) and Yl 1(1) to compute values KX1l 1(1) and (KX1l 1(1)) KY1l 1(1) where K is a constant and X1+iY1 (X+iY) Exp(2 pi i theta ), said iterative operations being of the form Xj l Xj + aj2 jYj (6) Yj l Yj - aj2 jXj (7) where the multipliers aj change between + 1 and - 1 so that

Claim 3

A digital computer according to claim 1, wherein the means for operating iteratively further includes a store holding the first values only of tan 12 j and means connected to said store for repeatedly dividing by two the preceding values in order to derive subsequent values.

Claim 4

A digital computer according to claim 1, wherein said address register and said level register are both shift registers, and wherein there is further provided an adder; means for connecting said address register in a recirculating loop including said adder for incrementing the address by 1 in each recirculation; and means for connecting said level register in a recirculating loop to recirculate in step with said address register.

Claim 5

A digital computer according to claim 3, wherein said means foR extracting and producing further comprises first and second buffer registers for holding the addresses of Xl 1(0) and Yl 1(0) on the one hand and Xl 1(1) and Yl 1(1) on the other hand; means for shifting the address in said address register into both said first and second buffer registers; and means for forcing the bit corresponding to the l bit in said level register to 0 in said first buffer register and to 1 in said second buffer register under control of said level register.

Claim 6

A digital computer according to claim 3, wherein said means for producing the value of theta includes a shift register for storing theta , means for synchronous reverse circulation of said address register and said level register, means for shifting bits from said address register into said shift register for storing theta , and means stopping said means for shifting bits when the l bit in the level register is detected.

Claim 7

A digital computer according to claim 3, further comprises means responsive to overflow of said address register for shifting the l bit in said level register to the next less significant position.

Claim 8

A digital computer according to claim 3, wherein said means for recirculating further comprises means for detecting, during the incrementing recirculation of the address, when the bit in said address register located in the same position as the l bit in said level register has a predetermined one of its two possible values and wherein said means for detecting is operative to institute immediately a further incrementing recirculation without performance of equations (6) to (11).

Claim 9

A digital computer according to claim 1, wherein said means for producing the value of 0 includes a register holding (0- 1/4 ), and wherein said means for operating iteratively comprises control means for adding to or subtracting from the contents of said register for holding ( theta - 1/4 ) the values of tan 12 j in accordance with the values of aj, said control means being responsive to the values of

Claim 10

A digital computer according to claim 1, wherein said means for operating iteratively includes means for counting the iterative operations, first and second shift registers for storing X and Y values, respectively, first and second adder/subtractors connected in recirculating loops including said first and second shift registers, respectively, first and second scalers connected between said first and second shift registers each being connected to the respective non-corresponding one of said first and second adder/subtractors wherein said first and second scalers are controlled by said means for counting so as to introduce the multipliers 2 j in equations (6) and (7), and means for controlling the add and subtract functions of said first and second adder/subtractors to add and subtract selectively in dependence upon the values of aj.

Claim 11

A digital computer according to claim 9, wherein the means for removing the constant K further comprises means for connecting said first and second scalers to the corresponding said first and second adder/subtractors and means for recirculating said first and second shift registers wherein said first and second scalers progress through states of different significance while said first and second adder/subtractors are caused to add and subtract in a predetermined sequence, such that KXl1(1) and KYl1(1) are both multiplied by 1/K.

Claim 12

A special purpose computer for performing the fast Fourier transform on a plurality of data terms in a succession of levels of computation, the number of levels being dependent upon the number of the data terms to be transformed, the computer compriSing: i. data storage means for storing each data term at a predetermined address therein; ii. means for extracting data terms in pairs from said data storage means, the data term pairs being determined in accordance with the level of computation and with their addresses in said data storage means; iii. a central processor arranged, at each level of computation, to receive the pairs of terms extracted from said data storage means said central processor including means for effecting vector rotation of one of the terms of each pair through an angle determined by the addresses of the terms of the pair and the level of computation, and means for adding and subtracting the result of the vector rotation to the other term to form a new pair of terms; and iv. means for returning each new pair of terms to said data storage means, to the respective addresses of the pair of terms from which the new pair of terms was derived; wherein said means for effecting vector rotation comprises: a. means for subjecting the real and imaginary parts, X and Y respectively, of said one term of each pair to a succession of rotational steps, of which the first step is of magnitude 1/4 radians/2 pi and the remaining steps are of magnitude aj tan 12 j radians/2 pi and are constituted by a series of iterative operations of the form Xj 1 Xj + aj 2 jYj (6) Yj 1 Yj - aj 2 jXj (7) where the multipliers aj change between +1 and -1 in such a manner that the algebraic sum of said rotational steps and the respective angle through which vector rotation is to be effected tends to zero, whereby to effect said vector rotation and simultaneously to effect multiplication by a constant K; and b. dividing means for dividing the result of said iterative operations by said constant K.

Claim 13

A special purpose computer for performing the fast Fourier transform on a plurality of data terms in a succession of levels of computation, the number of levels being dependent upon the number of the data terms to be transformed, the computer compriSing: i. data storage means for storing each data term at a predetermined address therein; ii. means for extracting data terms in pairs from said data storage means, the data term pairs being determined in accordance with the level of computation and with their addresses in said data storage means; iii. a central processor arranged, at each level of computation, to receive the pairs of terms extracted from said data storage means said central processor including means for effecting vector rotation of one of the terms of each pair through an angle determined by the addresses of the terms of the pair and the level of computation, and means for adding and subtracting the result of the vector rotation to the other term to form a new pair of terms; and iv. means for returning each new pair of terms to said data storage means, to the respective addresses of the pair of terms from which the new pair of terms was derived; wherein said means for effecting vector rotation comprises: a. means for subjecting the real and imaginary parts, X and Y respectively, of said one term of each pair to a succession of rotational steps, of which the first step is of magnitude 1/4 radians/2 pi and the remaining steps are of magnitude aj tan 12 j radians/2 pi and are constituted by a series of iterative operations of the form Xj 1 Xj + aj 2 jYj (6) Yj 1 Yj - aj 2 jXj (7) where the multipliers aj change between +1 and -1 in such a manner that the algebraic sum of said rotational steps and the respective angle through which vector rotation is to be effected tends to zero, whereby to effect said vector rotation and simultaneously to effect multiplication by a constant K; and b. dividing means for dividing the result of said iterative operations by said constant K.