Cascadable Digital Filter Processor Employing Moving Coefficients

This invention relates generally to dedicated systolic processing arrays, and more particularly the invention relates to a pipelined digital filter processor employing moving coefficients.

The digital filter processor (DFP), also referred to as a finite impulse response (FIR) processor or convolver, forms vector operations in the form of ##EQU1## where X.sub.n-i --input samples

Y.sub.n --output filtered signal

c.sub.i --filter coefficients

k--filter length, number of taps

A number of DFP integrated circuits are commercially available. Typically, sampled data is fed sequentially to multipliers having fixed coefficients, and the partial products are then summed and outputed.

An object of the present invention is a DFP having increased processing speed.

Another object of the invention is a DFP circuit which is flexible in application.

Still another object of the invention is a DFP circuit having a plurality of multiplier accumulators that are accessible through a common bus, and may operate in four modes according to the number representation (i.e. 2's complement, unsigned and mixed modes) of the multiplicands.

Another object of the invention is a DFP circuit which can be cascaded for operation on data with greater filter lengths.

Yet another of the invention is a DFP circuit that can perform sample rate reduction or decimation.

Another object of the invention is a DFP circuit that can be concatenated for longer word length of data and coefficients.

Briefly, a DFP circuit in accordance with the invention includes a plurality of cells organized to operate on data, that enters all the cells in parallel and includes a sign mode bit for 2's complement or unsigned representation, with filter coefficients being pipelined to the individual cells as the data is supplied in parallel to the cells. Each cell has a multiplier/accumulator (MAC), and each MAC is connected through a common multiplex bus (MUX) to a cell output/accumulator.

Filters of increased lengths can be created by cascading together several DFP circuits or by recycling in a single circuit. By using multiple circuits the sample rate need not be reduced. By recycling data in a one or more circuits the increased filter length is accommodated by reducing sample rate. The circuits can be operated in parallel to get maximum sample rate by computing partial products and then adding to obtain a final result.

Coefficients in each cell are connected to adjacent cells through a plurality of registers and multiplexers. The registers allow the coefficients to be delayed through the cell by one or more clocks for resampling or decimation for rate reduction. The decimation registers can be employed also to provide convolution of image points. The coefficients and data include a sign mode bit which specifies the 2's complement or unsigned number representation.

The invention and objects and features thereof will be more readily apparent from the following detailed description and appended claims when taken with the drawing.

FIG. 1 is a logic symbol and signal identification for a DFP circuit in accordance with one embodiment of the invention.

FIG. 2 is a functional block diagram of the DFP of FIG. 1.

FIG. 3 is a functional block diagram of one cell in the DFP circuit of FIG. 2.

FIG. 4 is a functional block diagram of the output stage of the DFP circuit of FIG. 2.

FIG. 5 is a table illustrating operation of the DFP circuit of FIG. 2 in a simple four tap filter mode of operation.

FIG. 6 is a schematic of the four tap filter operation using the logic symbol of FIG. 1.

FIG. 7 is a timing diagram for the four tap filter operation.

FIG. 8 is a functional block diagram of an eight tap FIR implemented by cascading two DFP's of the specified embodiment illustrated in FIG. 1.

FIG. 9 is a timing diagram of the eight tap FIR cascade operation of FIG. 8.

FIG. 10 is a table illustrating operation of the single circuit for implementation of an eight tap filter.

FIG. 11 is a schematic diagram of circuitry with DFP word size extension.

FIG. 12 is a table illustrating operation of a single DFP circuit with word size extension.

FIG. 13 is a timing diagram of the operation illustrated in the table of FIG. 12.

FIG. 14 is a table illustrating operation of the circuitry of FIG. 2 in a decimate by two mode of operation.

FIG. 15 is a timing diagram of the operation illustrated in the table of FIG. 14.

FIG. 16 is a schematic diagram of the circuitry of FIG. 2 for image convolution.

The invention has been reduced to practice in a digital filter processor device designated ZR33481 to be announced by Zoran Corporation, Assignee of the application. FIG. 1 is a logic symbol diagram and pin definition for the device. The device 10 comprises four multiplier/accumulator (MAC) stages cascaded internally and a shift and add output stage, all in a single integrated circuit. Each MAC stage contains an 8.times.8 bit multiplier. This multiplier may operate in 4 modes--according to the mode bit of the multiplicands: 2's complement.times.unsigned, 2's complement.times.2's complement, unsigned.times.unsigned, unsigned.times.two's complement, a 26 bit accumulator and three decimation registers. The output stage contains an additional 26 bit accumulator which can add the contents of any MAC stage accumulator to the output stage accumulator shifted right by 8 bits. This feature is used in implementing more than 8 bits MAC (data or coefficients) with several cells. As will be described below, the DFP can be configured to process expanded coefficient and word sizes. Multiple circuits can be cascaded for larger filter lengths at up to 20 MHz sample rate or a one or more DFP circuits can process larger filter lengths at less than 20 MHz. The architecture permits processing filter lengths up to 1028 taps with no overflows. The circuit supports unsigned or two's complement arithmetic, independently selectable for coefficients and signal data.

Each cell (MAC stage) contains three resampling or decimation registers which permit output sample rate reduction at rates of one-half, one-third, or one-fourth the input sample rate. These registers also provide the capability to perform 3.times.3 or 4.times.4 convolutions for image processing applications using one DFP. A 256.times.256.times.8 image can be convolved with a 3.times.3 kernel in real time (i.e., 6.64 MHz video rate).

Before describing the circuit structure and function, the following interface signal descriptions for the logic symbol of FIG. 1 are provided:

As illustrated in FIG. 2, the Digital Filter Processor (DFP) is composed of four filter cells 12 cascaded together and an output stage 14 for combining or selecting filter cell outputs. Each filter cell contains a multiplier-accumulator (MAC) 16 that may operate in four modes according to the multiplicands, as above noted, and several registers 18, as illustrated in FIG. 3. Each MAC multiplies an 8-bit (plus mode bit) coefficient 20 by an 8-bit (plus mode bit) data sample 22, adds this result to the 26-bit accumulator contents in MAC 16 and stores the 26-bit addition result back into the accumulator. The coefficient output at 24 of each cell is cascaded to the coefficient input of the next cell to its right.

An 8-bit coefficient with a ninth sign mode bit 20 enters each cell through the Y REGISTER 26 on the left and exits the cell on the right. The coefficient may exit on the clock following its entrance, it may be frozen for any number of clocks or it may be delayed 1, 2 or 3 clocks by passing through one or more decimation registers 18. The decimation operation will be described in more detail later. The coefficient output 24 of each cell connects to the coefficient input of the cell to its right. In normal operation a sequence of coefficients is shifted from left to right through the chip one cell at a time.

The CIENB input signal controls the CIN 0-7 input bus. When CIENB is low a new coefficient is read into the leftmost cell and all the previous coefficients are shifted right (according to the decimation control, DCMO-1). If CIENB is high, the coefficients are frozen. The CIENB signal is delayed by one clock internal to the chip. Therefore it must be low during the clock cycle immediately preceding presentation of the desired coefficient on the CINO-7 inputs. Detaled operation is shown in later timing diagrams.

The COENB input signal enables the COUT 0-7 and TCCO outputs for retrieving the right-most coefficient. These outputs are typically connected to the CINI-7 and TCCI inputs of another DFP chip for cascading to construct longer filters.

A data sample enters each cell through its X REGISTER 28 and is multiplied by the coefficient in the Y REGISTER. All four cells receive the same data sample simultaneously via the DIN 0-7 bus and sign mode. When low, the DIENB signal enables the DIN 0-7 bus to every cell X REGISTER simultaneously. When high, DIENB presents a zero value to every X REGISTER. The DIENB signal is delayed by one clock internal to the chip. Therefore it must be low during the clock cycle immediately preceding presentation of the data sample on the DIN 0-7 inputs. Detailed operation is shown in later timing diagrams.

When both CIENB and DIENB are high (inactive), the DFP is effectively in a wait mode; previous internal results remain unchanged except in the shift and add mode (SHADD).

The ERASE and RESET signals clear the DFP internal registers and state as follows:

The RESET signal is delayed by one clock internally. The registers are actually cleared on the clock cycle immediately following the cycle during which RESET is asserted low. ERASE is also delayed by one clock internally. However, for clearing a single accumulator selected by ADRO-1, ERASE is not delayed.

Referring now to FIG. 4, the output stage consists of a 26-bit adder 30, 26-bit register 32, feedback multiplexer 34 from the register to the adder, and an output multiplexer 36.

The 26-bit output adder 30 can add any MAC cell accumulator result to the 18 most significant bits of the output buffer 32. This result is stored back in the output buffer. This operation takes place in one clock period. The 18 most significant bits of the output buffer are obtained by shifting (actually hardwired) the output buffer contents right 8 bits. The 8 LSBs are lost. The MAC cell accumulator used is selected by the ADR 0-1 inputs.

The 18 MSBs of the output buffer 32 actually pass through the zero mux 34 on their way to the output adder input. The zero mux is controlled by the SHADD input signal and selects either the output buffer 18 MSBs or all zeros for the adder input. A low on the SHADD input selects zero. A high on the SHADD input selects the output buffer MSBs, thus activating the shift and add operation. The SHADD signal is delayed by one clock internally.

The 26-bit results from either a cell accumulator or the output buffer are output on the SUM 0-25 bus 38. The output mux 36 determines whether the cell accumulator selected by ADR 0-1 or the output buffer is output on the bus. This mux is controlled by the SHADD input signal. Control is based on the state of the SHADD during two successive clocks, that is the output mux selection contains memory. If SHADD is low during a clock cycle and was low during the previous clock, the output mux selects the contents of the MAC cell accumulator addressed by ADR 0-1. Otherwise the output mux selects the contents of the output buffer.

If the ADR 0-1 lines remain at the same address for more than one clock, the output at SUM025 will not change to reflect any subsequent accumulator updates in the addressed cell. Only the result available during the first clock when ADR 0-1 selects the cell will be output. This does not hinder normal operation since the ADR 0-1 lines are changed sequentially. This feature facilitates the interface with slow memories where the output is required to be fixed for more than one clock.

The SUM 0-25 output bus is controlled by the SENBH and SENBL signals. A low on SENBL enables bits SUM 0-15. A low on SENBH enables bits SUM16-25. Thus all 26 bits can be output simultaneously if the external system has a 26-bit or larger bus. If the external system bus is only 16 bits, the bits can be enabled in two groups of 16 and 10 bits (sign extended).

Both data samples and coefficients can be represented as either unsigned or two's complement numbers. The TCS and TCCI input signals determine the type of arithmetic representation. Internally all values are represented by a 9-bit two's complement number. The value of the additional ninth bit depends on arithmetic representation selected. For two's complement arithmetic, the sign is extended into the ninth bit. For unsigned arithmetic, bit 9 is 0.

The multiplier output is 18 bits and the accumulator is 26 bits. The accumulator width determines the maximum possible number of terms in the sum of products without overflow. The maximum number of terms depends also on the number system and the distribution of the coefficient and data values. As a worst case assume the coefficients and data samples are always at their maximum absolute values. Then the maximum numbers of terms in the sum products are:

For practical FIR filters, the coefficients are never all near maximum value, so even larger vectors are possible in practice.

A sample, 20 MHz 4-tap FIR filter example serves to illustrate more clearly the operation of the DFP. The sequence table (FIG. 5) shows the results of the multiply accumulate in each cell after each clock. The coefficient sequence, C.sub.n, enters the DFP 10 on the left and moves from left to right through the cells. The data sample sequence, X.sub.n, enters the DFP 10 from the top, with each cell receiving the same sample simultaneously. Each cell accumulates the sum of products for one output point. Four sums-of-products are calculated simultaneously, but staggered in time so that a new output is available every system clock.

The sequence table ignores pipeline details. Detailed operation of the DFP to perform a basic 4-tap, 8-bit coefficient, 8-bit data, 20 MHz FIR filter is best understood by observing the schematic (FIG. 6) and timing diagram (FIG. 7). The internal pipeline length of the DFP is three (3) clock cycles. Therefore the delay from presentation of data and coefficients (from memory 40) at the DINO-7 and CINO-7 inputs to a sum appearing at the SUMO-25 output is:

where

k=filter length

Td=3, the internal pipeline delay of DFP

After the pipeline has filled, a new output sample is available every clock. The delay to last sample output from last sample input is Td.

The output sums, Yn, shown in the timing diagram are derived from the sum-of-products equation:

Note that due to the pipeline, clock period #9 in the timing diagram corresponds to clock period #3 in the unpipelined state table above.

Filter lengths greater than four taps can be created by either cascading together multiple DFP chips or "reusing" a single chip. Using multiple chips, an FIR filter of up to 1024 taps can be constructed to operate at a 20 MHz sample rate. Using a single chip clocked at 20 MHz, an FIR filter of up to 1024 taps can be constructed to operate at less than a 20 MHz sample rate. Combinations of these two techniques are also possible. Even more taps can be accommodated but with the risk of overflow.

To design a filter of length k>4, k/4 chips are cascade by connecting the COUT 0-7 outputs of the (i)th chip to the CIN 0-7 inputs of the (i+1)th chip. The DIN 0-7 inputs of all the chips are also tied together. A specific example of two cascaded chips illustrates the technique (FIG. 8). Timing (FIG. 9) is similar to the sample 4-tap FIR, except the ERASE and SENBL/SENBH signals must be enabled independently for the two DFP chips in order to clear the correct accumulators and enable the SUM 0-25 output signals at the proper times.

Using a single DFP chip, a filter of length k>4 can be constructed by processing in k/4 passes as illustrated in the table shown in FIG. 10 for an 8-tap FIR. Each pass is composed of Tp=3+k+Td cycles and computes 4 output samples. In pass i, the samples with indexes (i-1)*4+1 to i*4 enter the DIN 0-7 inputs. The coefficients Cl-Ck enter the CIN 0-7 inputs, followed by 3 zeros. As these zeros are entered, the result samples are output and the accumulators reset. Initial filling of the pipeline is not shown in this sequence table. Filter outputs can be put through a FIFO to even out the sample rate.

The sample and coefficient word size can be extended by utilizing several DFP chips in parallel to get the maximum sample rate or a single chip with resulting lower sample rates. The technique is to compute partial products of 8.times.8 and combine these partial products by shifting and adding to obtain the final result. The shifting and adding can be accomplished with external adders (for full speed) or with the DFP's shift and add mechanism contained in its output stage (at reduced speed).

Before discussing these techniques, appropriate notation must be established. Consider the multiplication of two 16-bit numbers. Let

where

C.sub.M =most significant byte,

C.sub.L =least significant byte

where

X.sub.M =most significant byte

X.sub.L =least significant byte

Then

The partial product bits line up as follows: ##STR20##

A fourth order FIR with 16-bit coefficients and data and 20 MHz sample rate can be constructed with four DFP chips 10 and three external adders 44 (FIG. 11). Different 8.times.8 partial products are accumulated in each DFP chip at a 20 MHz rate and combined by the external adders to form the result. The least portions (X.sub.L and C.sub.L) are in unsigned mode.

A single 4-tap DFP can multiply word sizes up to n.times.32 bits with any number of bits. A single 4 tap DFP may be used, for example to implement 24.times.16 MAC or 8.times.32 MAC. The technique can be illustrated by the sample of a 16.times.16 multiplication.

Using the partial product notation above, consider the multiplication of two 16.times.16 numbers. Three MAC cells are used to accumulate three overlapping partial products. CELL 0 accumulates the LSBs, CELL1 the middle bits and CELL2 the MSBs. Finally the partial products are combined using the shift and add capabilities of the output stage. CELL 0 operates in unsigned mode. CELL1 is MIXED mode and CELL2 is two's complement mode.

The 16-bit operands are input one byte at a time in the sequence shown in FIG. 12. Detailed timing of 16.times.16 multiplication, including pipelining, is shown in FIG. 13.

A useful function in many digital signal processing systems is sample rate reduction or decimation. Prior to decimation the signal must be low pass filtered to prevent aliasing when the sample rate is reduced. If, for example, decimation by a factor of 2 is desired, only every other output of the low pass filter is used. If only the needed outputs are calculated, the processing requirements are halved. FIR filters are particularly convenient for decimation since their output depends only on present and past inputs and not on past outputs.

The DFP of FIG. 2 provides a mechanism for decimating by factors of 2, 3 or 4. From the DFP filter cell block diagram (FIG. 3), note the three D registers 18 and two multiplexers 19 in the coefficient path through the cell. These allow the coefficients to be delayed by 1, 2, or 3 clocks through the cell. The sequence table (FIG. 14) for a decimate-by-two filter illustrates the technique (internal cell pipelining ignored for simplicity):

Detailed timing for a 20 MHz input sample rate, 10 MHz output sample rate (i.e. decimate-by-two), 8-tap FIR filter, including pipelining, is shown in FIG. 15.

The decimation registers can be used to provide a 3.times.3 or 4.times.4 correlation with one DFP device (FIG. 16). In the 4.times.4 application for example, the 16 kernel coefficients are stored properly interleaved within the decimation registers and recycled as the DFP is clocked. The image pixels are entered in column-scanned order into the DFP data input. Each DFP MAC cell accumulates the correlation sum for a single image point. Four points are being accumulated simultaneously, but overlapped. Once the pipeline is full, a new correlation result is available every four clocks. Hence the correlation proceeds at a rate of 20 MHz/4=5 M points/sec. For a 3.times.3 correlation, the rate is 6.67 M points/sec. In a similar manner image convolution may be implemented with the DFP device.

The high performance and cascadability of the DFP is very attractive for implementing various functions in a radar system. In a typical radar system the DFP can implement the matched filter pulse compressor as well as various other digital filters in the system. Other applications include adaptive filters, Butterfly computations, echo cancellation, and complex multiplications.

Thus while the invention has been described with reference to a specific embodiment and specific applications the description is illustrative of the invention and not to be construed as limiting the invention. Various modifications and applications may occur to those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims.