Patent GB-1407401-A (GB)
Title: Apparatus for performing the fast fourier transform
IPC: G06F17/14
Filed: 1971-09-09
Abstract: 1407401 Fast Fourier transformations SOLARTRON ELECTRONIC GROUP Ltd 11 Sept 1972 [9 Sept 1971] 42186/71 Heading G4A Apparatus for performing the Fast Fourier transform algorithm on a number, 2<SP>m</SP>, of data points in a series of m iterations includes a store having four serial access sections A, B, C, D, each arranged to store 2<SP>m-2</SP> of the data points, a processor arranged to generate a sum and a difference point from a pair of data points fed thereto in accordance with the algorithm, and control logic arranged to feed to the processor the pairs of data points read successively from sections A and B (one point in each pair from A and the other from B), and from sections C and D (one point in each pair from C and the other from D), and to write each sum point into section A or B and each difference point into section C or D, the section into which each point is written being selected in accordance with the value of one bit of an address counter arranged to count the pairs of points fed to the processor. The processing of the pairs of data points is not described other than by reference to Specification 1,350,904 which utilizes cordic vector rotation to produce from each pair a new pair, referred to as sum and difference points. The present arrangement allows relatively cheap serial access stores to be used for the data points rather than the relatively expensive random access store as in the specification referred to. The data points may be referred to in terms of an m-bit address b m-1  ... b 0 . In the qth iteration the points in each pair processed are given by the notation meaning that the address bits of the two points in the pair are the same with the exception of address bits b m-q  which are as specified. The address bits, with the exception of bit b m-q  are produced by a counter 11 which counts the pairs fed to the processor in each iteration to produce a count p m-2 , ..., p 0 , each p bit corresponding to one of the b bits with the exception of b m-q , the correspondence changing from iteration to iteration but always being such that p m-q-1  = b m-q-1  except in the last iteration. The points are read out serially from sections A and B, and then from sections C and D, are processed, and are returned to the appropriate one of the sections so that they are presented in the correct sequence in the next iteration. As described, Fig. 5, two sets of registers A-D may be provided, the points being read from one set, processed, and written in the other set, the roles of the two sets being reversed for the next iteration. Alternatively a single set of registers may be provided, the processed points being rewritten into the registers. The points are read out from the reigsters in turn, the registers A1 and B1 being sleeted first by gates 12 followed by the registers C1, D1 selected by gates 13, the gates being responsive to the most significant counter bit p m-2  which divides the count into two halves. The sum points from processor 14, for which by definition b m-q  = 0, are fed to register A2 or B2, and the difference points to register C2 or D2, the choice between registers A2 and B2, and between C2 and D2 being made in accordance with the counter bit f m-q-1  = b m-q-1  (which is the same in both points used to produce the sum or difference point) except in the last iteration when q = m when bit p m-2  = b 1  is used. A shift register 10 holds a single bit in a location indicative of the level of the current iteration and via gates 21, 22, 18, 24, and 17 controls gates 15, and 16 to feed the sum and difference points to the correct register under the control of counter bit f m-q-1  = b m-q-1  for all q # m. When q = m one input to each gate 21 is 0 so that the output of gate 22 and hence one input of gate 18 is 1. The q = m input of gate 17 is 1 so that the output of gate 18 is determined by the state of the counter bit p m-2  which corresponds to address bit b 1  in the final iteration. The value of # (the angle through which the Cordic vector rotation is performed) is determined by a counter 20 which specifies 0 in terms of bits below the binary point. For iterations where q#1 and q #m the bit of counter 20 (i.e. the (q-1)th below the binary point), marked by the output from level register 10 via gates 25, 26, is incremented (starting at zero) each time the address bit b m-q-1  = p m-q-1  changes from 1 to 0. In the first iteration, q = 1, 0 remains at zero and in the last iteration, q = m, counter 20 is incremented, via gates 23 and 24 for each pair of data points processed, i.e. by the pulses P which step counter 11, the incrementing occuring at the (m-1)th position below the binary point. The derivation of # is somewhat different than in Specification 1,350,904, merely because the points are processed in a different order. The registers A-D may be shift registers serial by character (data point), serial or parallel by bit.