Real-time fourier transformation apparatus
[ 1 Apr. 29, 1975 l l REAL-TIME FOURIER TRANSFORMATION APPARATUS Inventors: George A. Works, Wayland; Harry Vickers. Oakham. both of Mass [73] Assignee: Raytheon Company, Lexington.  
 Mass.  
 [22] Filed: Oct. 30. 1973 [21] Appl.No.:4ll.l0l  
 Related U.S. Application Data OTHER PUBLlCATlONS G. Di Bergland &amp; H. W. Hale, Digital Real-Time Spectral Analysis,&#34; IEEE Trans. on Electronic Computers. Apr. 1967. pp, 180-185.  
 Primary Examiner-Charles E. Atkinson Amixmm hraminerDavid Hv Malzahn Attorney; Agent, or Firni.lohn R. lnge; Joseph D, Pannone; Milton Dv Bartlett l57| ABSTRACT An apparatus for performing real-time Fourier transformation of a time varying signal by taking successive digital samples in a shift register means and repeatedly transforming preselected pairs of said samples as the samples are progressively shifted down the register, The successive samples are ordered in the register in a binary sequence from 0 to 2&#34;l while the pairs are selected when the binary distance between them is equal to 2&#34; m being the transformation number each pair x,, X,, being related to its transformed magnitude X,, and X,, by the relations IIJII &#39;l mm lmu where d) is the radian value determined by the transform number in and the position of the sample pair X,, X,, in their original position order of successlont 9 Claims. ll Drawing Figures 50 5? a l&#39; ll F 5? 500 I 520 l I l i ll l 78 5; l ize-n-mr n-BIT FREQUENCY TIME I FUNCTION FUNCT&#39;ON REGlSTEFl I REGISTER l I 1 wono n r n z l l (CLOCK W72] 1 [54b 1 l l i ARITHMETIC I umr l L we fl g -w CLOCK l 50 l PULS l 72 GENERATOR I 68 70 Ll- &#34;a (READ DNLY MEMORY TRlG. FUNCTlONSl ROTATION V ECTO R 58 STORAGE mgmmmzsms 3.881 100 SHEET 10$ 6 DIAGRAM OF COOLEY TUKEY FFT ALGORITHM SWITCH CONTROL DATA SHIFT REGISTER DATA f f M #051 A= 2 SAMPLES r 5 AU F/G ARITHMIXETIC Xum X x FFT MODULE b,m+| UNIT u,m+l 29 REAL  |4u Ix n90 l SIYGD IMAGINARY s Q IMAGINARY IN /4 OUT HTENIEBIIPII29I9I5 3.881.100  
 saw 2 0F 6 ROTATION 80 ROTATION vEcTOR VECTOR ADDREss STORAGE 7 II ROTATION 50 52 54 s I I I DATA m= I m: DATA MODULE MODULE MODULE 62 54 66 w T T I BINARY BINARY 76 60 COUNTER B&#39;NARY COUNTER I won STAGE COUNTER STAGE CLOCK M36, STAGE SB) INPUT I i J x v I OUTPUT FREQUENCY CHANNEL AND ROTATION VECTOR NUMBER TO 82 ADDREss TO 80 FFT PROcEssOR 500 520 540 78 DATA 56 SR SR I DATA INPUT m=I m=2 m=n OUTPUT /02\ 104 /06i\ I08 //0 //2 1/4 H6 DATA BUs&#39; ARITIINIETII:  
 UNIT  
 IOI  
 PATENTEDmzsma 3.881.100  
 SHEET 5 or 6 690 SHIFT PULSES MASTER TIMING CONTROLLER CTR 8 SYNCH AU SELECTOR SYNCH. COUNTER RO M S l NE COS ADDRESS TRANSLATO R ROM ROM SlNE/COSINE REVERSE LOGIC PATENTEDAPR29I915 SHEET B U? 6 FFT OUTPUT ADDRESS UNIT SHIFT PULSES RTER ANALOG! DIGITAL F/G. 6B  
 REAL-TIME FOURIER TRANSFORMATION APPARATUS CROSS REFERENCE TO RELATED APPLICATIONS This is a division of application Ser. No. l ,948 filed Nov. 24, I971 now US. Pat. No. 3,8l6,729, which is a streamlined continuation of application Ser. No. 863,776 filed Oct. 6, I969, now abandoned.  
 BACKGROUND OF THE INVENTION This invention relates to improvements in real-time signal processing, and more particularly, to real-time digitalized Fourier transformation of signals. The following paragraphs briefly describe the relevant attempts to mechanize. using analog and digital apparatus, the computation of these transforms. First, the Fourier transform and signal processing is discussed to provide a basis for appreciating the real-time requirements. Second, the discussion centers on the problem of squaring real time requirements with the use of general purpose digital computers. Lastly, consideration is given to the limitations of the current Fast Fourier Transform technique as used on digital computers.  
 Fourier Transforms and Signal Processing The Fourier transform of a signal greatly enhances certain signal characteristics such as energy or amplitude distribution as a function of frequency. This helps discriminate between a signal and noise. Typically, a transmission environment includes broad-band noise. Such noise has a fairly uniform distribution of energy over a large frequency range. In contrast, the Fourier transformation of a signal will show a great deal of energy concentrated in a comparatively narrow frequency band. The Fourier relation is said to map a signal from the time domain into the frequency domain. Mathematically, the relation between a signal as a function of time .\&#39;(I) and the transformation as a function of frequency X(w) is In this formulation, .\&#39;(I) is an analytic continuous func tion. It, theoretically, requires integration of an infinite time interval and a knowledge of the future. However, the capacity of the transform to yield frequency spectrum information about a time varying signal greatly outweighs the failure of real world electrical signals to conform to the exactitude of mathematical analytic continuity. This is illustrated in the following several examples.  
  A. B. Cunningham et al., US. Pat. No. 3,087,674 issued on Aprv 30, 1963, shows an analog Fourier transformation apparatus in which a time varying electrical signal .r(r) is partitioned to form sinusoidal component product signals .rt!) sin w t and .r(1) cos w t. These product signals are in turn integrated over time to yield I .t(1) sin w,-r dr and j .r(!) cos w tdr. Finally, the integrated product signals are combined to form an output signal X(w) such that By varying the given frequency of the range of interest m, W, s w, s W and recording the magnitude |X(w,-) l at each w,- there is obtained an analog record corresponding to a Fourier transformation of the signal .\&#39;(I).  
  Spectrum analyzers often include a bank of tuned narrow band width contiguous filters whose output yields a voltage versus frequency spectrum. The square of the voltage versus frequency is proportional to the power density spectrum of the corresponding signal. Also, a Doppler radar range gate filter bank is one illustrative example of such a spectrum analyzer. In this regard, the filter bank may be thought of as a twodimensional spectrum of range versus Doppler frequency. Reference also may be made to a voice communication example of M. R. Schroeder, U.Sv Pat. No. 3,344,349 issued on Sept. 26, 1967.  
 Real-Time Fourier Transform Processing A system reacts in real time when the complete response of a stimulated system occurs at, or about, the same time as the stimulus. Generally, where a system needs the results of processing a time varying signal (stimulus) immediately, then a very broadband width system is required. Such an overall signal processing requirement exists for the Fourier transformation of radar echo returns. To impose the microsecond response time requirements of volume radar data upon prior art analog systems, in addition to a high degree of accuracy and precision, would clearly exceed all reasonable bounds of cost, size, weight and power. Attention is directed to both Cunningham et al. and Schroeder as illustrative of the high degree of complexity of even the low frequency band width analog processing arrangement.  
 Prior Art Digitalization of Fourier Transform Process If digital techniques are to be used for analyzing continuous waveforms, then it is necessary that the data be sampled (usually at equally spaced intervals oftime) in order to produce a time series of discrete samples which can be fed into a digital computer. This time series can completely represent the continuous waveform, if the waveform is frequency band-limited and the samples are taken at a rate at least twice the highest frequency present in the waveform.  
  A Discrete Fourier Transform (DFT) suitable for digital computational use is described in William T. Cochran et al., Proceedings of the IEEE, Volume 55, Number l0, October l967 at pages I665 to 1667. The DFT is defined by the relation:  
  N1 XI: -215mm where X,- is the r component of the DFT; .r denotes the k sample of the time series consisting of N samples; r=0. l. 2. N l; and where j= l. Cochran further shows the substantial equivalence of DFT t0 the continuous Fourier transform. lnspection of the above DFT relation reveals that each .o. must be multiplied N times to form N sums. Since be formed N times. Thus, every product term must be there are N different values ofx there must be comformed N times. The FFT algorithm basically seeks to puted N multiplications and N additions. remove such redundancy. For a derivation of the Coo- Programs for performing the DFT on general purley-Tukey version of FFT, reference is again made to pose digital computers have long been extant HOW- 5 Cochran et al,, especially between pages 1667 and ever, there are severe limitations to the speed with 1669. which such machines can execute the programsv Typical processing times are in the order of 50 milliseconds. A variety of notations have been used by different auln contrast, the channel capacities (data volume) of thors in discussing the Fourier transform, DFT and such systems are not sufficient to accommodate reall0 FFT. For convenience all references in this disclosure time radar data processing. lllustratively, a radar havhave been converted to a standard notation; the following a one microsecond pulse width may require a data ing table compares Cochrans notation and the stanrate of million bits per second, dard notation.  
 Quantity Standard Cochran Number of time or frequency samples in a transform block N N Base or radix of a transform R Number of stages in a radix R transform.  
 equal to log N n n K&#39; time sample a :k Mali-. 1.  
 r&#39;&#34; frequency sample X l&#39;,. Z, 4,. 8,.  
 K&#39;&#34; output from m stage of FET Weighting term. or  
 rotation vectorv used in transform 1&#39; t &#34;-11&#39; I It&#34; The limitations of a general purpose device arise Briefly,Cochran et al.assumesatime scriesx having from the fact that such machines access main memories N samples divided into two functions y and z,,, each seriallyv Many of these have word organized memories. comprising N/elements or points. y comprises even Even the look ahead&#34; machines, such as the IBM numbered points X X x It comprises odd num- 7094 (STRETCH are limited to the extraction of only bered points .1 x .r Then,  
 a few words at a time from main core. Where data is y X packed and extracted on a word basis, there is difficulty x in accessing different units in different addresses. Thus, it W I. what emerges from the early attempted digital process- Let r and r represent the DFT yk and Zr. PfiC- ing was the need for a machine in which the data was iv lyu accessible in parallel and byte organized.  
  1131 3 N The Fast Fourier Transform and Digitization -34m The Fast Fourier Transform (FFT) is an algorithm Z fs r:0 1 2 A g for computing the Discrete Fourier Transform (DFT) r i 2 of a series of N (complex numbers) data points in approximately N log N operations. As was pointed out by James W. Wooley et al., Proceedings of the IEEE, Vol Let W e &#39;rr then X E .r W&#39; 2 (y -l-zflw&#39; ume 55, Number 10 at pages 1675 to I677, the FFT al- Now for O s r N/2 gorithm was devised specifically because the DFT re I 2 r (H217 r r r quiring N operations was using hundreds of machine hours of computing time&#34;. To appreciate FFT, it is nec- For values of r N/2, the DFT Y, a d Z periodically essary to understand some ofits derivation and relation repeat values taken when r N/2. Thus, -12 lr+.\l2ll.\&#39; j2 rIA&#39; It should be recalled that in DFT NH YT+ 1r e y, w&#39;z, km r Xr 1 1 l t21rr/\H f r 0 s r N/2. Then X, Fatc it where e 45 cos d) +j sin d). According to Cochran, if the input digital data se- There are many repetitions in N computations of quence is stored in computer memory in the order,  
 DFT. As an example. at k 0, the product 1 8 must for example, x .14. 13;, I x x x then the computation may be done in placeY That is. the intermediate results will be written over&#34; the original data sequence. Thus. no storage is needed beyond that required for the original N complex numbers. However. what Cochran failed to appreciate was that in a general purpose digital computer having serially accessed stor age. R&#34; data words must be transferred from the storage to the arithmetic unit in order to execute a fixed radix R transform upon N R&#34; samples. Also. R&#34; partial results must be transferred from the arithmetic unit back to storage for each of n stages required to com pute the transform. Consequently. 2nR&#34; accesses to storage are required.  
 Summary of the Invention It is. accordingly. an object of this invention to devise an apparatus for computing Fourier transforms in real time upon input time varying data. Itis a related object to devise a digital responsive apparatus having substantially simplified machine organization.  
  The foregoing objects are attained in a preferred embodiment in which successive digital samples of a time varying signal taken at regularly spaced intervals are inserted into shift register means. Preselected pairs of said samples are repeatedly transformed as the sample pairs are progressively shifted down the register. The successive samples are ordered in the register in a binary sequence from 0 to 2&#34;-l. The pairs are so chosen before each transformation such that the binary distance between them is equal to 2&#34; m being the transformation number. Each pair X,, X is related to its transformed magnitude X,, and Xiunfl by the relations n.m+t mm lmn liJiHi uun Inm where d) is the radian value determined by the transform number m and position of the sample pair in their inverted position order of succession. In this regard. e&#34; 4) is equivalent to Cochran&#39;s W. The successive signal samples are sequentially shifted such that each sample is selected and transformed n times.  
  It may be stated as a general proposition that N!/(NR)ER. different combinations of N samples taken R at a time may be extracted and transformed in apparatus embodying the invention. Experience dictates that the invention is most efficient where R 2, 3. or 4.  
  There exist several embodiments of the machine. One embodiment uses an arithmetic unit common to all of the logic modules and time shared among them. Another embodiment uses a separate arithmetic unit for each logic module and is time shared only as between the Real and Imaginary data channels of the logic module. In this latter embodiment. standard modules are serially arranged. Time digital data samples reporting complex numbers are applied at the input of this cascade. Each logic module includes an arithmetic portion which operates upon the digital data sample transferred into the unit. This sample is then progressively shifted down the chain or cascade and transformed at each module.  
  The successive states or iteration of the fundamental (ooley-Tukey algorithm are each carried out in the separate cascaded modules In both embodiments. shift registers are used as digital delay lines so as to permit new data to be entered into the processor while the processing of earlier data can be carried out. Advantageously. the overall dclay required is only equal to the time necessary to gather the block of data in each of the Real and Imaginary channels. As the last or N&#34; complex data sample is loaded into this digital delay line, the first analysis appears at the output. The output frequencies appear in a sequence associated with the algorithm. A control device. namely. a binary counter. yeilds digital numbers identifying both the channel number and the frequency currently appearing at the output of the shift register digital delay line chain. Additionally. this binary counter specifies the instant at which the separate modules are to be switched and the digital number identifying the sine/cosine values needed by each of the modules.  
  As mentioned in the Background. the requirement for real-time processing is most in demand with respect to radar information. In this context. data information is obtained at a high volume. In Doppler radar. it is often desired to treat the phase shift information derived from the received echo signals as having a Real and Imaginary component. This is accomplished by multiplying the detected Doppler signal by a sinusoidal function and processing it separately from the same signal multiplied by a sinusoidal function out of phase. Thus. the first stage of the serially connected logic modules may be made to terminate the radar receiver in two parallel interconnected channels. one for processing the Real component of the radar data and the second channel for processing the Imaginary component. Because the transform requires multiplying a portion of the data word in either channel by cd: an Imaginary component will be produced as a result of the multiplication. Accordingly. provision is further made for switching the Imaginary component produced by multiplication in the Real channel to the Imaginary channel of the next successive module. Similarly. a Real component produced by multiplication in the Imaginary channel is switchably connected to the Real channel at the next successive module.  
  It should be apparent that Imaginary components will be produced even if only Real components are present at the data input to the first processing stage. Thus. it is necessary to retain this processing capacity independent of the orthogonality requirements of the data as originally inputted to the FFT processor.  
 BRIEF DESCRIPTION OF THE DRAWINGS FIG. I is a signal flow graph of an eight-point Cooley- Tukey Fast Fourier Transform algorithm.  
  FIGSv 2A and 28. respectively. show a block diagram and a detailed logic diagram of a typical module used in the invention.  
  FIGS. 3A and 3B show the cascade of modules in relationship to the binary counter stages and the rotation vector storage inputs.  
  FIG. 4 shows a block diagram of one embodiment of the invention in which an arithmetic unit is time shared with all of the modules on a common bus.  
 FIG. 5A is the signal flow diagram of a single module.  
  FIG. 5B is a detailed signal flow diagram of a 16- point transform as performed by the invention. while FIG. 5C diagrammatically illustrates the effect of the rotation vector 2 4,  
  FIGS. 6A and 6B are detailed logic block diagrams of the invention using the modules of FIGS. 2A and 2B and arranged generally as in FIG. 3.  
 DESCRIPTION OF THE PREFERRED EMBODIMENTS Referring now to FIG. I of the drawings, there is shown a signal flow graph of the Cooley-Tukey algu rithm. At the left of the graph are the data points .r through x; of the time series 14,. which are to be trans formed by repeated applications ofthe transform equations. Basically, this signal flow diagram is composed of nodes and arrows terminating in those nodes. The nodes represent the data or the data as transformed. The arrows originate at the nodes whose variables contribute to the value of the variable at the node at which the arrow terminates. The contributions at any node are additive. The weight of each contribution, if other than unity, is indicated by the constant written close to the terminating arrow head. Thus, taking an arbitrary node and designating it u in FIG. I, it may be seen to be vectorally equal to x W.\&#39;,. Similarly, taking another arbitrary mode in FIG. I, I) would be equal to .r Wit As previously mentioned, the computation may be done in place&#34;, that is, by writing all interme diate results over the original data sequence. Thus, for example. the value of intermediate computations a and b are needed only for two computations in the next successive transform T A iumllltlllud, each of the input nodes affects only t corresponding nodes immediately to the right. If the computation deals with two nodes taken at a time, the newly computed quantites may be ritten into the registers from which the input values 1 ere taken since the input values are no longer needed for further computation (T,). The second step T also involves, for example, pairs of nodes. After a new pair of results has been computed, the pair also may be stored in the registers which held the old results and are no longer needed.  
  A number ofimportant features of the algorithm may be seen by examining this figure. First, each stage follows a succeeding stage from left to right. Accordingly, each stage needs only the data generated from the preceding stage. Second, if each stage processes information in the order of arrival, then the first stage examines data points displaced by half the data length (N/2). The second stage examines data points separated by one quarter the data length (NM). Third, if the data were available in a continuous stream, then the first stage would process one block of data while the second stage processed the next earlier block of data and so on through all M stages. Fourth, the rotation vector 6 W has the same periodicity as the inverse of the data displacement interval, Finally, the data output is scrambled with respect to the order of the data presented in the input.  
  Referring now to FIG. 2A, there is shown the basic module component of the invention. The m&#39;&#34; module alternately transfers blocks of 2&#34;&#34;&#34; data samples at input I through switch 311 into the shift register SR on path 1] and into the arithmetic unit AU on line 5. When the data block just fills the shift register SR, the arithmetic unit AU obtains at input 74 a rotation vector from an external memory and begins its operation. The next block of 2&#34;&#34;&#34; data samples are sent to the arithmetic unit which now produces two complex number outputs X X in response to the two complex number inputs X,, and X,, One of the outputs X is immediately transferred over path 29 through switched connection 3b to a next successive stage while the other output X is returned to the input path II of shift register SR through switched connection 3a. Thus. in the interim period when shift register SR is being filled with new input data, then the former con tents of shift register SR containing the earlier transferred blocks are transferred to the next stage. With re spect to all the data, the arithmetic unit AU computes the complex number twopoint transform X X X ,,,L and X,, I X,, X,, ,,,e where d) is the radian value determined by the transform number m and the position of the sample pair in their original position order of succession, a and 17.  
  Referring now to FIG. 28, there is shown a more detailed implementation of the logic module set forth in FIG. 2A. It should be recalled that the time varying analog signal values are converted to a binary digital equivalent. It should further be recalled that many ap plications of sampled data signals require processing of the original signal, sometimes called the Real signal, and the same signal shifted 90 out of phase therewith. This is sometimes called an Imaginary signal. Each of the data points may be represented by a complex number. Accordingly, the Real and the Imaginary signals are represented collectively by complex numbers. Furthermore, because the same two-point transform is applied to both the Real and Imaginary signals, it is possible to share the arithmetic unit between them. This fact is amply illustrated in FIG. 2B. The Real signal is applied to input 4a, while the digits corresponding to the Imaginary input signal are applied to 4b. Arithmetic unit AU is shown in relationship to shift registers 16a and 16b and externally programmed switches 12a,! um and ttimh- Referring now to the Real signal processing, the data input 4a is switchably connected through switch S to either multiplier 32 or delay 14a. When S is coupled to multiplier 32, the portion of the Real signal input constituting the Real component of the complex number X,, is fed into the multiplier 32.  
  Switch S connects the shift register 16a to either the X output of adder 38 through delay 400 or to the X,,,,,, input of the Real signal through switch S and delay 14a. Similarly, switch S couples register I60 to the output through delay I or applies the input X,, to adders 38 and 34. It should be noted that the lmaginary signal input applied at 412 is switchably connected to multiplier 32 simultaneously with the real portion of the signal, and similarly to shift register 16!) through delay 14b and switch S Also, register 16b is selectively coupled to accept the X output from adder 38 that is transmitted through delay 40b and also through switch S Shift register 16b is selectively coupled through switch S to the Imaginary output through delay 18b, as well as coupling the Imaginary signal X component into adders 38 and 34.  
  Switches 8, by selectively connecting delays 36a and 18a in the case of switch 8, and delays 36b and 18b in the case of switch S permit the Real and Imaginary two-point transforms to be read out simultaneously with the application of a new complex input sample. Thus, X and X constituting the Real signal transform appear respectively through delays 36a and I80. Likewise, X and X constituting the Imaginary signal transform appear respectively through delays 36b and 18b. The rotation vector is applied as an input to multiplier 32.  
  In order to analyze the gross operation of the module, let us recall the formulas The first step in solving the equations is to multiply e by X,, The X,, and X,, are obtained from a serial storage shift register where Real and Imaginary components are stored in parallel. The e 11 term is of the form cos d) +j sin d). This is stored in rotation vector storage means 58. The correct e 1: term is sent to the arithmetic unit AU by external control logic. This will be discussed in greater detail with reference to FIGS 6A and 6B.  
  The complex multiplication is done in parts. This consists of four real multiplications to form all the products of the two complex words and two real additions to form the final answer. The next step then is to add and subtract this product from X,. to compute the final sum of the transform. This requires four additions.  
  Referring now to FIG. 2B, the X,, input is applied in is complement format and is converted into sign plus magnitude format. The multiplier 32 works on numbers in sign plus magnitude format because of its economy and convenience. The multiplier 32 output is also converted into 1&#39;s complement format. Adders 34 and 38 utilize ls complement format in addition. Also, the final output is further in ls complement format.  
  The detailed logic of multiplier 32 is not set forth explicity as this is deemed to be well within the purview of one having ordinary skill in the art. In this regard, reference may be made to any one ofa number of standard known works. such as Logic Design of Digital Computers&#34; by Montgomery Phister, Jr., New York, John Wiley &amp; Sons, 1959; A Survey of Switching Circuit Theory by McCluskey, Jr. and Bartee, McGraw- Hill Book Company, Inc., New York, 1962&#39;, and Arithmetic Operations in Digital Computers&#34; by Richards, published by de Van Nostrand Company, Inc., New York, 1955. Suffice it to say that in the multiplier, provision must be made for clocking the X terms in. The Real part may be stored in one register and the Imaginary part in another register, all within multiplier 32. In this regard, attention is directed to pages l36 through l76 of Richards for several forms of multiplier logic.  
  The X terms should take only one word time in order to be clocked into these multiplier registers. It is evident that the terms should be available from these registers in the form of the logical variable X and its logical complement form E The associated e do may be read in a multiplier buffer register also in parallel format. Preferably, it should be read in at the same time that X,, is read in. Thus, both e it and X,, both their Real and imaginary parts, are available to be selected by the multiplier. In the design of such multiplier, it must be anticipated that several different clock times are necessary for forming different products. Now, the multiplication of two complex numbers should yield four partial products. of which two are Real and two are Imaginary. A sign determination circuit can functionally comprise two cascaded half adders in sign magnitude multiplication. If each multiplier and the multiplicand form the same sign, then the partial product is positive. If the signs mismatch, then the partial product is negative.  
  The output of multiplier 32 is X e This output is applied respectively as an input over two paths to ad ders 34 and 38. When either serial register 16a or 16b is coupled to respectively paths constituting the X,, inputs for adders 34 and 38 through respective switch connections S and S then X,, is also applied as an input to adders 34 and 38. The output of adder 34 provides the sum X,, X,, ,,,e This sum is provided for the Real signal through delay 36:: and the Imaginary signal through delay 36h. In a similar manner, the output of adder 38 is of the form X X,, ,,,e This dif ference for the Real signal appears through delay 40a. It is switchably connected to the Real output through switch S register 16a, switch S and delay 18a. The difference relating to the Imaginary output appears through delay 40b. It is switchably connected to the Imaginary output through switch S register 16b, switch S and delay 18b. It is further apparent that the reading out of the two-point transform X,, X,, for the Real and Imaginary signals is achieved by alternating respective switches S between their re spective contacts.  
  Referring now to FIG. 3A, modules 50, 52, and 54 are serially arranged with data being applied at input 56 to the m=l module 50. Control counter 60, having counter stages 68, 70, and 72 corresponding to the modules. performs a timing or frequency division function as activated by the word clock input 76. Each of the modules contains the logic shown in FIG. 2B. Paths 62, 64, and 66 couple corresponding counter stages 68, 70, and 72 to modules 50, 52, and 54.  
  Rotation vector storage 58 supplies vector information 0 over a common bus 74 to each of the modules. The rotation vector storage 58 may comprise a read-only memory which is a table of sines and cosines shared by all m modules. In FIG. 1, M2 different pairs of sines and cosines are read to process one block of N samples. It is important to note that exactly M arithmetic units and exactly N complex number data points of storage are needed in the system. The first transform output from module 54 appears at terminal 78 immediately after the last data sample in the block of N data samples has been entered at the input 56.  
  The FFT processor shown in FIGS. 3A and 33 has a considerable speed advantage. However, one-word delays must be inserted in or between the processing stages 50, 52, 54, etc., to make use of this speed. These delays. discussed in reference to FIG. 2B, permit each module to begin computation at the start of a word time rather than waiting for the preceding modules to compute the input it requires.  
  These intermodule delays do not appreciably complicate the control circuitry of the FFT processor. It is only necessary to delay the data input 56 and the rotation vector storage input 58 to each of the modules 50, 52, and 54 by a number of word times equal to the total delay of the data input. The control input to each module is a bit from the control counter 60. These bits may be transmitted to the modules over paths 62, 64, and 66 from binary counter stages 68, 70, and 72, respectively. The bits may be transmitted through actual delays (not shown). Delay corrected control words for each module may be computed by subtracting the appropriate delays from the control counter word.  
  Leaving the question of delays for a moment, each time a bit in the control counter word changes from a zero to a one. the corresponding module controlled by that bit begins performing two-point transforms using a new rotation vector (&#34;4; Rotation vectors are therefore required at an average rate of one for each word time. These may be distributed to the processing modules on a single data bus 74. When intermodule and control delays are considered, then the average rate at which rotation vectors are required is unchanged. However. buffer storage must be included between the data bus 74 and the modules for delay compensation.  
  Referring now to FIG. 313, there is shown a more de tailed block diagram of the embodiment illustrated in FIG. 3A. The time varying signal applied at input 56 is in analog form and converted to digital form by analogtodigital converter 57. A clock input signal is applied on bus 76 for synchronizing converter 57, counter 60, and each of the shift register portions 50a, 52a, and 54a of the logic modules. As is apparent from the discussion of FIGS. 2A and 2B. the arithmetic units 50b, 52b, and 54b circulate a portion of their results into and out of the corresponding shift register. The stages 68, 70, and 72 of counter 60 perform a frequency division function. It should be noted that the digital word from converter 57 is applied in parallel to the appropriate gated shift register and gated in and out of the various registers in parallel. Of course, such an operation could also be done entirely in serial fashionv Rotation vector storage 58 comprises a storage medium in which a tabular form of sines and cosines may be stored in vector addresses corresponding to the posi tion indices and b of the extracted data pair X,, and X,, in the serially arranged informationv The position angle (1: 2111/2 where It is apparent that is determined by the length 2&#34;&#34;&#39; of the shift register involved with each module since each module operates on strings of data of given lengths. This fact may be observed by considering that m indicates the number of the arithmetic unit and that 1&#39; lies within the range 0 s i 2&#34;. The variable i is defined as the greatest integer not greater than a/2- Il-Il|+l The structure of FIGS. 3A and 38 may be readily modified to calculate inverse transforms when the spectral components are given in scrambled order. This structure permits the same trade-off of channels pro cessed for data length per channel by taking outputs at an intermediate stage.  
  Referring now to FIG. 4, there is shown an arithmetic unit 10] time shared with shift registers 50a, 52a, and 540. on a common data bus 100. The output of shift register 500 results in N/2 independent two-point transforms. The output of shift register 52a yields N/4 independent four-point transforms. Likewise. the output of shift register 54a yields N/S independent eightpoint transforms. If two independent streams of complex number data were applied at data input 56 and interleaved one with the other. then the m=first stage (500) would produce two independent discrete Fourier transforms of each data stream. The spectral component of each channel of data is outputted before the spectral frequency is changed. What this means for pulsed radar or sonar is that where the data representing many range samples is received, the data will be processed in order of arrival without modification and without requiring the data to be re-assembled into consecutive and non-interleaved data streams.  
  The switches 102, 104, 106, I08, I10, 112, 114, and 116 are symbolically shown to indicate that the arithmetic unit 101 operating on a common data bus may time share and process the output from any of the logic modules 50a, 52a, and 54a.  
  Referring now to FIG. 58, there is shown a signal flow diagram of the Cooley-Tukey algorithm for a 16- point transform. The input time samples are in natural or monotonically progressive orderx x x r The transform results in outputs X in bit reversed order X x X4 15 In order to implement the transformation, it is necessary that successive modules must wait until the preceding module has completed its two-point transform and the X,, results have been passed on before the next module can begin transforming.  
  Alternatively. this signal flow diagram represents a series of operations to be performed on R-tuples of words of various distance in the data string .r A data manipulating system which implements this algorithm must sequentially access all word Rtuples of distance R&#34; R&#34; 13 R in the data string for a total of ZnR&#34; accesses for a data string of length R&#34;. The parameter R is the radix of the algorithm and n is an integerv The value R is usually two or three. In FIG. 5B, R Z and the data string is of length 2. Thus. for the first transformation time interval T the distance between pairs of digits which are to be transformed together is d R&#34; 2*&#34; 8, where m is the transformation number. Accordingly, the following digit pairs are se lected: x x .r,, .n, x 1, During the second trans formation time interval T the distance between pairs of digits taken from the transformation results of the first time interval T is d= 2&#34;&#34; 4. Then, the digits .t&#39; occupying the former cells may be combined as follows: .r&#39; .r&#39;,,&#39; .r&#39; 1&#34;, Similarly. during the third transformation interval T the digits are selected with a distance of two units apart. Thus, the digits .t&#34;  
 would be combined as follows: .r&#34; x&#34; x m lfi- As may be recalled, with respect to the direction of the signal flow diagram in FIG. 1, the nodes at any point represent the summation of values terminating at the node with those nodes which have a weighting other than one. Thus, .t&#34;, .r&#39;,, W.r&#39;  
  FIG. 5A is a simplified signal flow diagram illustrating the two-point transform. As can be seen, the complex number X,, ,,,e 41 is algebraically added to X to form X,, As can be seen in this figure, the rules for vector addition are the same as shown in FIGS. 1 and 5B.  
  Referring now to FIG. 5C, there is shown the rotational aspect of the vector e e 1 indicates a counterclockwise rotation of the vector, whereas e&#39; i? is indicative of a clockwise rotation of the vector.  
  Referring to FIGS. 6A and 68, there is shown a detailed block diagram of the invention. A master or basic clock for the entire system is contained within master timing control apparatus 600. The selected hard wire output lines 602, 604, 606 activate remote functional units of the system. Path 602 activates analog-to-digital converter 610. Input control path 604 activates register means 612 through 628 to respectively accept digital information from A/D converter 610. Output control path 606, also coupling register means 612 through 628, causes the contents of register means 612 through 628 to be entered into Real register 63! and Imaginary register 630. Shift pulse path 632 is terminated in Real and Imaginary registers 630 and 631. Pulses on this path initiate the serial read-out of the contents of those registers. Paths 634, 636. 638, 640., 642, 644, 646, and 648 activate sample and hold circuits of the Real and Imaginary channel input means 650. As previously discussed, these means essentially are used for radar applications and other applications where it is desired to form quadrature or separate channel signals. Thus, sample data input signals multiplied by a sinusoid component are entered in Real register 652. Sample data signals multiplied by a sinusoid 90 out of phase with the first sinusoid are entered into Imaginary register 653. The contents of these registers are respectively serially read out on paths 656 and 655 and are accordingly demultiplexed through switch means 658 as energized over path 659 from the timing controller 600. The parallel entry of data into selector switches 652 and 653 is controlled over paths 660, 661, and 662.  
  Logic modules 664 664,,,-: 664. are shown in cascade. Each of the shift registers SR is switchably connected in series with the shift register SR of the next successive logic module. Data is entered into the logic module cascade on path 665 from Imaginary selector switch 630 and Real selector switch 631. The activation of the arithmetic unit ofa preselected logic module is controlled by AU selector 666 over paths 667,,, 667 c 667,. The rotation e 4: vector is also gated into the corresponding logic module from either read only memory 668 (for logic module 664 or readonly memory array 670 over path 672 (for logic modules 664,,, 664,). The timing sequence for initiating the operation of the logic modules is controlled by Master Timing Controller 600 through Master Synch Counter 674 over paths 667,,, 667 Similarly, the activation of the appropriate vector is derived from Master Timing Controller 600 over path 675 to Synch Counter 676. Synch Counter 676 also regulates FFT output and address unit 678 over path 679. It will be observed that FFT output unit 678 is appropriately fed the Fourier transform data from module 664 over path 680.  
  The two point transformation data and the progressive shifting and transforming of this data from the first logic module 664,,, through 664 is described in detail with regard to FIGS. I through 5B. Broadly, the regularly spaced digitalized time data samples are entered on line 665 into the first module and are progressively shifted under control of the Master Timing Controller 600 and the appropriate Synchronizing and Selecting units 674, 666 to enable the presentation of the rotation vector from either memory unit 668 or memory arrangement 672 to be present at the appropriate logic module multiplier. The read-only memories (ROM) may be constructed from appropriate permanent memory material or from any form of suitable bistable remanent magnetic material such as ferrite core arrays with an automatic rewriting of data after read. Synch Counter 676 also provides an input on path 672 over path 682 in order to assure the proper gating in the rotation vector information.  
  Memory arrangement 670 includes an address decoder 684, a translator 685, driving each of three readonly memories 686, 687, and 688. The address deoder is stimulated by the Synch Counter 676 upon signals on path 675 from Timing Controller 600.  
  It is believed that the logical design of each of the requisite subordinate units is well within the scope of the man ordinarily skilled in this art. For example, analog-to-digital converter 610 may range from a shaft po sition encoder to an appropriate diode resistance matrix. The sample and hold circuits ofthe Real and Imaginary channel input means 650 may be served by weighted capacitive means. These and other arrangements described in detail. while suitable for one embodiment of this invention, are to be taken as suggestive and not as limiting. As previously mentioned, a large variety of bistable remanent switching devices arranged in addressable register form may be devised to satisfy the requirements of this invention.  
 We claim:  
  I. A system for performing a Fourier transform com prising a plurality of serially coupled computational stages, each stage comprising in combination:  
 means for performing arithmetic operations upon sets of data; means for storing at least portions of said sets; means for coupling at least portions of the results of said arithmetic operations upon said sets to said storing means; and said system further comprising single means for controlling each of said coupling means, said controlling means operating independently from any stored set of instructions.  
  2. The combination of claim I wherein said means for performing arithmetic operations comprises means for performing at least a portion of a discrete Fourier transform upon said sets.  
  3. The combination of claim 2 wherein said storing means comprises shift register storage means.  
  4. The combination of claim 2 wherein said storing means comprises an addressable register.  
  5. The combination of claim 2 wherein said controlling means comprises a cyclical binary counter.  
 6. In combination:  
 a single means for providing a cyclic count;  
 a plurality of memory means; and  
 arithmetic computation means coupled to each of said memory means for calculating a discrete Fourier transformation upon a set of data samples, said computation means including means for weighting at least some of said samples, said plurality of memory means and said arithmetic computation means all being synchronized by said single count providing means.  
  7. The combination of claim 6 wherein said means for providing a cyclic count comprises a cyclical binary counter.  
  8. The combination of claim 6 wherein said memory means comprises shift register means.  
 9. The combination of claim 7 wherein said memory means comprises an addressable register.