Patent GB-1350904-A (GB)
Title: Implementation of fast fourier transform
IPC: G06F7/544
Filed: 1970-05-12
Abstract: 1350904 Fast fourier transformations SOLARTRON ELECTRONIC GROUP Ltd 3 May 1971 [12 May 1970] 23002/70 Heading G4A A special purpose digital computer adapted to perform The Fast Fourier Transform includes a data store 10 arranged to contain at the start of each of m levels of computation the real and imaginary parts X #-1 , and Y #-1  respectively of N terms A #-1 (b m-1 , b m-2 , ..... b 0 ), b i  being the addresses of the terms and # the level of the computation, an address register arranged to cycle through all values of the addresses during each level of computation, a level register storing a single bit indicative of the current level of computation, means responsive to each stored address to extract the terms X #-1 (..... 1 .....), Y #-1 (.....1.....), X #-1 (.....0.....), and Y #-1 (.....0.....), the notation (.....1....) indicating that the term is that stored at the address indicated by the address counter except for the bit b m-#  which is given by 1 or 0 as specified, means to determine a value # from the #-1 most significant bits of the address register contents, means arranged to effect a vector rotation of the terms X #-1 (1) and Y #-1 (1) through an angle #, the vector rotating means comprising means to effect an initial rotation of 90 degrees and subsequently to perform p iterative operations on the values X #-1 (1), and Y #-1 (1) resulting from the initial rotation to compute the values KX<SP>1</SP> #-1 (1), and KY<SP>1</SP> #-1 (1) where K is a constant such that the iterative operations being of the form where j = 0t 0 (p-1), X<SP>1</SP> = Xp, Y<SP>1</SP> = Yp, and the coefficients aj are Œ 1 chosen such that tends to zero, means adapted to remove the constant K to obtain X<SP>1</SP> #-1 (1) and Y<SP>1</SP> #-1 (1), and means adapted to generate the new terms A # (1), A # (0) by means of the following equations The input data can be represented by N terms of the form A 0 (b m-1 , b m-2 , ..... b 0 ) where b i  are the m bits of the address code for the terms. The computation proceeds in a series of levels in which the terms A 1 , A 2 , .... A m  respectively are calculated, the Fast Fourier Transform algorithm being where Two terms A # (...1...) and A # (...0...) are thus calculated from the corresponding pair of terms A #-1 , the rotation A # (...1...), A # (...0...) being used to mean that the bit b m-#  = 1 or 0, and the remaining bits b being the same in all three terms. The algorithm requires the vector A #-1 (...1...) to be rotated through an angle #<SP>1</SP> and added to A #-1 (...0...), #<SP>1</SP> having two values differing by 180 degrees depending on the value of b m-# , to produce two new terms. The algorithm may be rewritten as The equations above are equivalent to vector rotations through # and the arrangement produces the rotations by implementing a series of rotations of successively decreasing size (eqns. 1-3). The process is as described in "The Cordic Trigonometric Computing Technique" by J.E. Volder, IRE Trans. on Electronic Computers, Sept. 1959 pages 330-334. Data store 10 initially stores 2<SP>m</SP> terms A 0  as real, X, and imaginary, Y, parts. The terms are addressed by an m bit counter 11 in conjunction with an m bit shift register 12 holding a single bit identifying (by its location) the level (#) of the computation. The bit position in the counter 11 identified by the level bit is modified to produce two addresses (...1...), (...0...) referred to as D(1) and D(0). The (#-1) most significant bits of counter 11 identified by register 12 are entered in reverse order in register 14 to provide a value for #. The store is accessed at addresses D(1) and D(0) to access the real X #-1 (1), X #-1 (0) and imaginary Y #-1 (1), Y #-1 (0) parts of the pair of terms A #-1 (1), A #-1 (0) to be processed. Processor 15 which includes a means (not described) for performing an initial 90 degrees vector rotation on the two terms (each treated as a vector), and two adders (arranged to perform equations 1 and 2, a multiplication by 1/k and equations 4-7, then operates on the terms to produce a new pair A # (1), A # (0) from the old pair A #-1 (1), A #-1 (0). The multipliers aj for equations 1 and 2 are determined in accordance with equation 3 by recirculating the contents of register 14 through full adder 16 the second input to which is tan<SP>-1</SP>2<SP>-#</SP> read from a read only store. In practice the read only store holds only the first six values, the remainder being derived by means of the algorithm As each addition (or subtraction) is performed in adder 16 the overflow is monitored, an overflow causing the operation to be reversed, i.e. add instead of subtract and vice versa, the state of flip-flop 18 indicating the value of a j (= Œ 1). The newly calculated terms are returned to the store 10 at the addresses D(1), D(0) from which the old terms were taken and the process continues with the next pair of terms. When all pairs have been processed the level identifying bit is shifted one place and the procedure repeated, the number of levels depending on the number of terms being processed. The Specification describes the arrangement in some detail with reference to Figs. 2-6 (not shown). The adders include recirculating registers connected in loops via full adders.