Patent GB-1211859-A (GB)
Title: Data processing
Inventor: GILMARTIN MICHAEL JOSEPH JR
IPC: G06F17/14
Filed: 1967-09-28
Abstract: 1,211,859. Data processor. WESTERN ELECTRIC CO. Inc. 28 Sept., 1967 [29 Dec., 1966], No. 44105/67. Heading G4A. Data processing apparatus adapted for obtaining complex Fourier series coefficients of at least one time varying input signal comprises a memory unit, a trigonometric fimction generator, an indexing circuit and an arithmetic circuit adapted for iteratively forming successive sequences of Fourier series coefficients based on values selected by the indexing circuit from the trigonometric function generator, and on previously-generated Fourier coefficients selected by the indexing circuit from the memory unit. N samples of the time varying signal are taken and stored. Each can be considered as an independent one sample Fourier coefficient of the signal. If the N samples are then considered as N/2 sets of two sample records then new coefficients D(o) = ¢ [F(o) + G(o)] D(1) = ¢ [F(o) - G(o)] can be calculated, D(o) and D(l) being stored in the locations previously holding the F(n) and G(n) just used. This is repeated for each of the N/2 sets. These sets can then be considered as N/4 sets of four sample records and new coefficients D(o) = ¢ [F(o) + G(o)] D(2) = ¢ [F(o) - G(o)] D(1) = ¢ [F(1) + WG(1)] D(3) = ¢ [F(1) - WG(1)] can be calculated. This can be continued until N/N sets of N sample records exist so preferably N = 2<SP>m</SP>. With N = 2<SP>m</SP> and the N samples of signal having a period T taken at intervals of T/N and stored in chronological order in position O - - - N-1 of an array A o  Fig. 1) the position of the succeeding coefficients Ai + 1 and the positions of the coefficients used to obtain the succeeding coefficients are given by Ai + 1 is in position km-1 km-2 - - - ko F(n) is in position km-1 km-2 - - km-i O Km G(u) is in position km-1 km-2 - - kmil km-i-2 - - - ko Thus for array A1 where N = 8, m = 3 i = o four interlaced groups of Do and Di are produced. Do in position 0 = 000 is taken from positions 0 to 100 and form (D(oo, 4). Do in position 001 is taken from position 001 and 101 to form DO/1,5 &c. In array A2 where i = 1 two interlaced groups of Do D1 D2 D3 are produced. Do in position 0 = 000 is taken from 000, 010 Do for the second series in position 001 is taken from 001 011 the initial Do, D1, D2 or D3 of each pair being in a position corresponding to a binary reversal of its subscript i.e. Do is in 000 D1 is in 100. D2 is in 010 D3 is in 110. For the final array A3 coefficients Do-D, are produced each located in a position corresponding to a binary reversal of its subscript, each coefficient being of the form D(n) = D1(n) +  j D2(n). The process can be used with four interleaved samples instead of 2. Cooley-Tukey algorithm. Operation.-The N values of the function are read into a store and form array Ao of Fig. 1. The values are read into an arithmetic unit which operates on the values and on trigonometric function values supplied by a generator in accordance with Aim(km-1 km-2 - - - ko) = Ai (km-1 - - km-i O km-i-2-- ko) + (-1)<SP>km-i-1</SP> Ai (km-1 - - - km-i 1 km-i-2 - - kO) erpjO where # = 2<SP>-i-1</SP>#[2<SP>i</SP>km -i + 2<SP>i-1</SP> km-i+1<SP>+</SP>--- 2<SP>1</SP>km-1]  Because the resulting coefficients are obtained from coefficients occupying the storage spaces required the results can be held in the same store. The iterative process thus continues until array Am is calculated. Replacement is under control of an indexing circuit. The arithmetic units are duplicated to provide the simultaneous computation of the real and imaginary parts of the coefficients-sine and cosine function generators can be recirculating shift registers or numerical values stored in part of the main memory. Indexing logic. Generation of the address pattern is achieved by an Iteration shift register and a binary address counter. If the contents of the registers ISR 12  1BR 11  - - ISR o  AC l2  AC 11  - - AC 0  the current value of i is stored in the ISR register such that IS Rm-i-1 = 1 and all other bits are zero. Register AC stores the member K corresponding to the position of Aim in the array. Logic operation with the contents of ISR or the complement of the contents, and the value Aim can thus give the values of Ai according to the equation above, i.e. Ai + 1 and 1SR gives the first value of Ai in the equation and Ai + 1 AND 1SR gives the second values. At the end of each pair of logic operations the contents of Ai + 1 are increased by 1 and at the end of each iteration the one bit in 1SR is shifted one position. The same registers also sequence the trigonometric coefficients.