Pipeline signal processor
United States Patent Shapiro et al. Apr. 1, 1975 PIPELINE SIGNAL PROCESSOR [57] 1 ABSTRACT [75] Inventors: Gerald N. Shapiro, Arlington;  
  Herbert S. Sobel, Wayland, both of A signal processor including a programmable arithme- Mass. tic controller and a pipeline arithmetic unit controlled by such controller is disclosed. The arithmetic unit in- [73] Asslgnee&#39; g g Company Lexington cludes a plurality of serially coupled processing levelsl The arithmetic controller includes a corresponding [22] Filed: Nov. 2, 1973 plurality of serially coupled control levels. each one of such control levels being coupled to a corresponding [2]] Appl&#39; L070 one of the processing levels. Each one of the process ing levels passes digital data applied thereto in accor- [52] US. Cl.. 235/156, 340/172.5 dance with a control instruction applied to such pro- [51] Int. Cl G06f 7/38, GOof lS/OO cessing level by the arithmetic controller. As data [58] Field of Search 235/l56, 159, 160, i614, passes through the various processing levels, the con- 8; 340/1715 trol instruction associated with such data passes through the corresponding control level so that such [56] References Cited control instruction follows&#34; such data as both data N ED STATES PATENTS and control instruction pass through the processor. In 3.346,85l 10/1967 Thornton et al 23S/l56 x way Processor is adapmd Star a new T 3.771.!38 11/1973 Ccltruda ct al. 340/1725 C655 Concurrently as Such Processor Completes PrIOr 3 771 141 11/1973 c1111 .l 340/1725 process, 3,787,673 l/l974 Watson et al. M 235/156 Primary Examiner-Malcolm A. Morrison Assistant E.\&#39;aminerDavid H. Malzahn Attorney, Agent. or Firm-Richard M. Sharkansky; Philip J. McFarland; Joseph D. Pannone 9 Claims, 20 Drawing Figures CONTROL IE IOIY IEINS menu cournot W&#34;? I2 new I? c c v 1 515&#34; m s-1m n.  
 tan SELECTOR J&#34; SHEET D3DF16 PROGRAM CONTROL FIEL&#39;D MEMORY ADDRESS REGISTER 5 4 v T w l m) m L L R Mm m 2 c o E P PT 0 R D [VJ m 1 U 2 T N T w M m m V, m m &#34;m m M V&#34; c T U F 2 K R O 8 0 C Q R L WM 0/0) H 8 u N EE PT 7 l B M m UW r P M. w w m U C m N H S K D S 2 0 C 4 mm wm a w A m w 6 O l.- E .3 N Y O P n w u w P O A L L X H MC E0 M H H 4 k k w 0 I I k1 m vr 2 6 4 A T M w/ mJ Tm m 8 M c 1 PROGRAM CONTROLLER WEf&#39;JMAPR ms SHEET CSUF 16 m mmmooma w wmmoOma k QM mmmooma N mmmoomm H mwwoomm FL TrL ....l  
 SHEET 10 SF :T&#39;JEHTED APR 1 iQF lSBF 16 SHEET ER mm S E R nb L 7 W Ac J S L L R \l E N C E S k u G x N L m A U R Du D1 L L k L L n A A S K m I Q E a 1 N B 1 X R Q k Y Y 1 =8 k D k BB k R W2 Du Ei 7 u C k R 2 C W II&#39;. we N P W M I ki 2 m It&#34; PIPELINE SIGNAL PROCESSOR BACKGROUND OF THE INVENTION This invention relates generally to pipeline digital processing systems, and more particularly to programmable pipeline signal processors which are adapted for use in radar and/or sonar systems to provide a wide range of real time signal processing tasks.  
  As is known in the art, in recent years many large radar systems have been required to perform a variety of tasks using real time digital processing techniques. The digital processing in such systems involves the analysis of a large volume of data. In performing such analysis a digital signal processor may be required to perform a number of signal processing functions, such as: Pulse compression by means of convolution or discrete Fast Fourier Transform (FFT) techniques; Doppler processing; moving target indication (MTI); constant false alarm rate averaging (CFAR); or monopulse alignment calibration.  
  One suggested digital signal processor incorporates the architecture of a general purpose computer. Data are fed into a main memory. An arithmetic section is included sequentially to perform calculations on the data. Each arithmetic calculation (i.e., add or subtract) is controlled by a separate instruction. A sequence of instructions for any group of calculations, for example, those required for a desired transform, forms a subroutine and a particular sequence of subroutines corresponds to one processing mode or signal processing function. While such architecture requires no specialized (or hard-wired&#34;) hardware design, sufficient computation time must be available so that the time interval between successive sets of data be sufficiently long to enable performance of all required calculations during such time interval.  
  Another suggested approach includes the use of sequentially arranged pipeline processing modules. Each one of such modules is designed to perform only one ofa variety of signal processing functions. That is, the configurations of the arithmetic and memory elements within each module is tailored specifically to its assigned task or signal processing function. Each module performs calculations in accordance with its hardwired configuration and then passes the result to the next succeeding, specially configured, hardwired module. While this type of architecture is not generally speedlimited, (each module being capable of handling a relatively high data rate) it is very inefficient from a hardware utilization aspect. That is, because each module is highly specialized and specific in design, many different modules, each of a separate design, are required in any practical application. Consequently, if one signal processing function is changed, an entirely new module design may be required. Further, any such design change may also require alterations in the design of other modules, as where a change in sequence of the data processing function is desired.  
  In this connection a known signal processor includes a pipeline arithmetic unit which is adapted to have the processing elements therein interconnected in a selected one of a number of possible configurations, such configuration being selected by a control signal supplied in accordance with a stored program. Once selected in a particular configuration, data associated with a particular process are sequentially fed through the various processing elements. After completion of such process the arithmetic unit may be reconfigured in accordance with a different control signal to a new configuration for processing data associated with a second process. While such signal processor obviates many of the disadvantages in the above suggested approaches, in many applications (as those requiring real time processing) it is undesirable that the arithmetic unit be confined to one selected configuration for all the data being processed concurrently therein. This is so because the arithmetic unit in such known pipeline signal processor must complete one process before it can be reconfigured to a different process even though a portion of the data associated with the second process is available for processing by the arithmetic unit at the same time the last portion of the data associated with the first process is being processed by the arithmetic unit.  
 SUMMARY OF THE INVENTION With this background of the invention in mind, it is an object of this invention to provide an improved digital signal processor which is adapted to perform a variety of real time signal processing functions, such processor having greater speed and flexibility than has been known heretofore.  
  This and other objects of the invention are attained generally by providing a signal processor including a programmable arithmetic controller and a pipeline arithmetic unit controlled by such controller. The arithmetic unit includes a plurality of serially coupled processing levels and the arithmetic controller includes a corresponding plurality of serially coupled control levels, each one of such control levels being coupled to a corresponding one of the processing levels. Each one of the processing levels passes digital data applied thereto in accordance with a control instruction applied to such processing level by the arithmetic controller. As data passes through the processing levels of the arithmetic unit, the control instruction associated with such data passes through corresponding control levels of the arithmetic controller so that the control instruction follows the data associated therewith as both pass through the processor.  
 BRIEF DESCRIPTION OF THE DRAWINGS The foregoing features of this invention, as well as the invention itself, may be more fully understood from the following description read together with the accompanying drawings, in which:  
  FIG. I is a block diagram of a signal processor according to the invention;  
  FIG. 2 is a block diagram of an exemplary data mem ory address generator used in the signal processor of FIG. 1;  
  FIG. 3 is a block diagram of the macrocontrol generator used in the signal processor of FIG. 1&#39;,  
  FIG. 4 is a table of the instructions stored in the macromemory of the macrocontrol generator of FIG. 3;  
  FIG. 5 is a block diagram of the program controller used in the signal processor of FIG. 1;  
  FIGS. 6a 6c are block diagrams showing the configurations of the level 1 decoder and selector, level 2 decoder and selector, level 3 decoder and selector, respectively, used in the signal processor of FIG. 1, in response to various macroinstruction numbers;  
  FIG. 7 is a flow diagram of a 32 point Fast Fourier Transform (FFT) algorithm;  
  FIG. 8 is a table of instructions stored in the control memory means of the signal processor of FIG. 1, such instructions being associated with the 32 point FFT flow diagram of FIG. 7;  
  FIGS. 9-16 are charts showing the condition, where relevant, of the various elements of the signal processor of FIG. 1 as such processor executes the 32 point FFT process;  
  FIG. 17 is a program flow diagram of an MTI (Moving Target Indicator) process; and,  
  FIG. 18 is a table of instructions stored in the control memory means of the signal processor of FIG. 1, such instructions being associated with the MTI process of FIG. 17.  
 DESCRIPTION OF THE PREFERRED EMBODIMENT General Referring now to FIG. 1, a signal processor 9 is shown to include a control memory means 10, a programmable arithmetic controller 12, a pipeline arithmetic unit 14, an address generator unit 16, a data memory A 18, a data memory B 20 and a coefficient memory 22, all arranged as shown in a manner to be described to perform any one of a repertoire of signal processing functions.  
  The control memory means here includes a core memory, addressing means, and reading means, the details of which are not shown, all being of conventional design and arrangement, to store the repertoire of signal processing functions (i.e., MTI, FFT, etc.). Each one of the signal processing functions is comprised of a set of stored digital words or instructions. Each one of the digital words includes a program control field, a macroinstruction control field, a data memory A&#34; address field, a data memory B address field, and a coefficient memory address field.  
 Programmable Arithmetic Controller The programmable arithmetic controller 12 includes a program controller 24, (the details of which will be described later in connection with FIG. 5), which responds in accordance with the program control portion of an addressed or selected one of the stored digital words and generates, at the end of each current clock period, (c.p.), the memory location or address of the stored digital word to be selected during the succeeding clock period. Each clock period is defined by the terminal portion of a clock pulse (CLCK). Such clock pulses are supplied by a suitable clock means, not shown. Included in the programmable arithmetic controller 12 is a macrocontroller 26. Macrocontroller 26 responds in accordance with the macroinstruction portion of the selected digital word and includes a macrogenerator 28, the details of which will be discussed later in connection with FIG. 3. Suffice it to say here that such macrogenerator 28 produces a macroinstruction in ac cordance with the macroinstruction control field portion of the selected digital word. The macroinstruction of the selected digital word is decoded by a level 1&#34; decoder, here decoder 30. Such decoder 30 here is a read only memory. Such decoder, in response to each macroinstruction applied thereto, develops a control signal on a bus 32. During each clock period {c.p.) the macroinstruction produced by macrocontrol generator 28 also is passed through serially coupled registers 34, 36, 38, respectively, as shown. The macroinstruction stored in register 36 is decoded by a level 2&#34; decoder, here also a read only memory, as decoder 40. Such decoder 40, also in response to each macroinstruction applied thereto, develops a control signal on bus 42. Likewise, the macroinstruction stored in register 38 is decoded by level 3 decoder, here also a read only memory, as decoder 44. Such decoder 44, in response to each macroinstruction applied thereto, also develops a control signal on bus 46. It is here noted, in passing, that macrocontroller 26 may be considered as including a plurality of (here three) serially coupled control levels, each one thereof being adapted to produce an independent control signal on buses 32, 42, 46. Further, each macroinstruction applied to decoder 30 is stored in each of the registers 34, 36, 38 sequentially during consecutive clock periods.  
 Pipeline Arithmetic Unit Pipeline arithmetic unit 14 includes a plurality (here 3) of serially coupled data processing levels, the number of such levels corresponding to the number of control levels of the macrocontroller 26. In particular, processing level 1 of the pipeline arithmetic unit 14 includes a level 1 selector 48, registers 50, 52, 54, 56, 58 and a complex multiplier 60, all arranged as shown. Level 1 selector 48 is of conventional design to couple data on buses 62, 64, 68 selectively to output lines 70, 72 in accordance with the control signal on bus 32, such control signal being developed by the decoder 30, as mentioned. Data processing level 2 of the pipeline arithmetic unit 14 includes a level 2 selector 74, regis ters 76, 78, a complex adder and complex sub tractor 82. Level 2 selector 74 also is of conventional design and couples data on buses 84, 86, 88 to output buses 90, 92, 94, 96 selectively in accordance with the control signal on bus 42, such control signal being developed by the decoder 40 as mentioned above. It is here noted that, for reasons to be apparent, bus 84 is coupled to a suitable voltage supply, not shown, such supply representing a decimal 0. Processing level 3 of the pipeline arithmetic unit 14 includes a level 3 selector 98, also of conventional design, to couple the data on buses 100, 102 to output buses 104, 106, 107 in accordance withe the control signal on bus 46, such control signal being developed by level 3 decoder 44 as mentioned above.  
 Referring now to FIG. 6A, the configuration of level 1 selector 48, in response to a macroinstruction applied.  
 to level 1 decoder 30, is shown for the following such macroinstructions Nos. 1, 2, 5, 6, 10, ll, 12 and 13 to.  
 perform both MTI processing and a 32 point Fast Fourier Transform. FIGS. 68 and 6C show the configurations of level 2 and level 3 selectors respectively in response to the macroinstructions applied to level 2 decoder 40 and level 3 decoder 44, respectively, for macroinstructions Nos. 1, 2, 5, 6, 10, 11, 12 and 13. It is here noted that to perform other types of processing the macroinstructions may be changed with a concomitant change in the level selectors.  
  The relationship between macrocontroller 26 and the pipeline arithmetic unit 14 is such that each data processing level of the pipeline arithmetic unit is configured in accordance with the control signal provided by the corresponding control level of the macrocontroller 26. In particular, data, here, for example, complex digital words representative of the quadrature components of the video signal of a radar system, (not shown) are applied to the input of level 1 selector 48 during each clock period and are processed in processing level 1 in accordance with the configuration of such processing level as defined by the macroinstruction field of the selected digital word. The time delay provided by the various logic elements in each such processing level, together with the time delay provided by the registers therein, are balanced by the time delays provided by registers 34, 36 of the macrocontroller 26. Therefore, when a first set of data processed by processing level 1 is applied to level 2 selector 74 (i.e., two clock periods later) the macroinstruction associated with such first set of data is decoded by the level 2 decoder 40 and applied to the level 2 selector 74. Concurrently, as a second succeeding set of data is applied to the level 1 selector 48, the selected digital word associated with such second set of data has its macroinstruction control field decoded by the decoder 30. Continuing in like manner, when the first set of data is applied to the level 3 selector 74 (i.e., three clock periods after entering level 1) the macroinstruction associated therewith is decoded by the decoder 44 and applied to such level 3 selector and when the second set of data is applied to the level 2 selector the macroinstruction associated therewith is decoded by the decoder 40 and applied to such level 2 selector. Also, as the next succeeding set of data (i.e., the third set of data) is applied to the level 1 selector 48, the selected digital word associated therewith has its macroinstruction control field decoded by the decoder 30. Consequently, each macroinstruction may be viewed as passing through the control levels of the macrocontroller 26 in synchronism with the associated data as that data passes through each data processing level of the pipeline arithmetic unit 14. Therefore, the elements in each one of the data processing levels are interconnected, independently of each other, but in accordance with the macroinstruction associated with each data processing level as the process is being carried out.  
 Address Generator Unit Completing FIG. 1, address generator unit 16 is shown to include a data memory A&#34; address generator 108, a data memory B address generator 110 and a coefficient memory address generator 112. Data memory address generators A&#34; and B are identical in construction and an exemplary one thereof, say data memory A&#34; address generator 108, is shown in detail in FIG. 2. Such exemplary data memory A address generator 108 responds to the data memory A&#39; address field portion of the selected digital word in the control memory means 10. Such address field portion includes a location (i.e., LOC.) portion and an initiallincrement (i.e., INIT/INCR.) portion. The exemplary data memory A address generator 108 includes: a selector 114, one input thereof being coupled to a suitable voltage supply (not shown) to represent a decimal 0 and another input thereof being coupled to the output of a register 116. Register 116 stores the address, R, of the loc ation of data memory A&#34; from which data is to be read. Selector 114 is controlled by the [NIT- IINCR. portion of the selected digital word and couples selectively either the decimal decimal 0 or the contents of register 116 to the output of such selector 114 in accordance with the INIT/INCR. portion of such selected word. In particular, if such INIT/INCR. portion of the selected digital word is an INIT&#34; signal, the decimal zero is coupled to the output of selector 114 and the address stored in register 116 does not change at the end of the current clock period. If such INIT/INCR. portion of the selected digital word is INCR.,&#34; register 116 will ultimately have stored therein at the end of the current clock period the address previously stored therein, incremented by an amount indicated in the LOC portion of the selected digital word. In particular, in response to the INCR. signal, selector 114 couples the contents of register 116 to its output. The data in the LOC portion of the selected digital word is then combined with the output of selector 114 in an adder 118. For reasons to become apparent later, the addressing of the data A&#34; memory 18 by the register 116 is in a read (R)-write (W) sequence. The time interval between the read addressing and write addressing in the sequence is equal to the time delay within the pipeline arithmetic unit 14 (FIG. 1). With the particular three level pipeline arithmetic unit 14 shown in FIG. 1, a three clock period delay is provided by a delay line 120, of conventional design, here a three stage shift register.  
  Coefficient memory address generator 112 (FIG. I) is identical to the exemplary data memory address generator shown in FIG. 2 except that such coefficient memory address generator 112 does not produce a write address signal W. That is, coefficient memory address generator 112 contains a selector, an adder and a register but no delay line.  
  Data memories A&#34; and 13&#34; are coupled respectively to the data memory address generators A&#34; and B as shown in FIG. 1. Such data memories A&#34; and B are random access memories which are here adapted to have data written therein concurrently as data stored therein is read therefrom. One such memory is described in US. Pat. No. 3,761,898 issued Sept. 25, 1973, entitled Random Access Memory, Henry C. Pao, Inventor, and assigned to the same assignee as the present patent application. Data read from data memories A&#34; and B&#34; appear on buses 64 and 68 respectively as shown in FIG. 1. Data written into data memories A and B&#34; are applied on buses 106 and 104 respectively as shown. The address of the location wherein data is to be written appears on bus W and the location wherefrom data is to be read is on bus R, as mentioned above. Coefficient memory 112 is here a conventional random access memory. Data read from such coefficient memory appears on bus 126 as shown in FIG. 1. The address of the location in such memory wherefrom data is to be read is on bus R as mentioned above.  
 Program Controller Referring now to FIG. 5, the details of program controller 24 are shown to be adapted to perform FFT and MTI signal processing functions. Program controller 24 responds in accordance with the program control field portion of the selected digital word and obtains the address for the digital word which is to be selected during the next clock period. Such control field includes a next address&#34; portion and an instruction portion here made up of a number of times instruction and a control&#34; instruction. The control instruction may take one of four different forms. Such forms may be summarized as follows:  
  TRA transfer during the next clock period to the digital word indicated by the next address field of the