Filter With a Reduced Number of Shift Register Taps

This invention relates to signal filtering and, more particularly, to signal filtering of discrete-time signals. For a general discussion of discrete-time (sampled) filters and particularly of discrete-time and amplitude (digital) filters and some of their application, reference is made to Digital Processing of Signals by B. Gold and C. M. Rader, McGraw-Hill Book Company, 1969.

Recursive filters comprise a powerful class of filters because they can be easily designed to have sharp cutoffs and because high order recursive filters can be constructed by concatenating low order filters. Nonrecursive filters, on the other hand, can be designed to have a linear phase response but cannot obtain sharp cutoffs without the use of filter orders which are much higher than the filter orders of equivalent recursive filters. Because of the increased hardware required for sharp cutoff filters, nonrecursive filters have not, heretofore, been extensively used in the filter art. With the advent of large scale integrated circuit technology, however, this impediment of nonrecursive filters is circumvented because the circuitry can be integrated and thus be made conveniently small and economical. The one problem which still remains with high order nonrecursive (transversal) filters is the large number of leads that need to be provided between the integrated shift register stages required in the filters and the arithmetic circuits of the filters. Leads occupy space, require pins for connecting to the integrated circuits, and require internal interconnections. This translates into increased costs.

It is, therefore, an object of this invention to provide a more economical configuration for high order nonrecursive filters.

It is another object of this invention to provide a filter configuration which reduces the number of shift register taps required in the implementation of various filter configurations.

These and other objects are achieved by realizing that a filter input-output relationship of the form ##EQU1## CAN BE REWRITTEN IN THE FORM ##EQU2## WHERE N is the order of the filter, x is the input signal, D.sup.i is an i unit delay, the C.sub.i' s are filter coefficients, m is a preselected integer, N/m' is the fraction N/m truncated to its largest integer, and C.sub.i is taken as zero for i > N.

In accordance with the principles of this invention, the rewritten form is implemented with a shift register having N/m' taps at intervals of m units delay (developing thereby (N/m'+1) signals defined by the expression D.sup.mk x with k assuming the values 0, 1, 2, . . . N/m'), and with a filter processing network which includes a) means for multiplying the D.sup.mk s signals by appropriate filter coefficients, b) means for appropriately summing and delaying the (N/m'+1) product signals and c) means for appropriately summing the summed and delayed product signals to develop the signal z.

FIG. 1 depicts a prior art configuration of a nonrecursive filter;

FIG. 2 illustrates one embodiment of a filter configuration in accordance with the principles of this invention;

FIGS. 3 and 4 present alternate representations of the filter configuration of FIG. 2;

FIG. 5 depicts a recursive filter configuration which employs the principles of this invention; and

FIG. 6 illustrates a filter configuration having recursive and nonrecursive sections, both of which employ the principles of this invention.

FIG. 1 depicts a block diagram of a prior art transversal filter. The order 19 filter shown in FIG. 1 includes a 19 stage shift register 10 responsive to an input signal on lead 12, and a filter processing network 100 responsive to the input signal and to the output signal of every stage of shift register 10. Filter processing network 100 comprises a set of multipliers 31.sub.1, 31.sub.2, . . . 31.sub.20 associated with the signals applied to network 100. Each one of the multipliers in network 100 is connected to a corresponding one of the signals applied to network 100 and is arranged to multiply the applied signal by a preselected constant, or a filter coefficient. Thus, in FIG. 1, a multiplier 31.sub.1 multiplies the input signal on lead 12 by coefficient C.sub.O, multiplier 31.sub.2 multiplies the signal output of the first stage of register 10 by coefficient C.sub.1, while multiplier 31.sub.19 multiplies the signal output of the last stage of register 10 by coefficient C.sub.19. The output signals of multipliers 31.sub.1, 31.sub.2, . . . 31.sub.20 are added to each other in a summing network 20. Signal z, which is the output signal of network 20, comprises the output signal of the filter processing network 100 and also comprises the output signal of the transversal filter of FIG. 1.

The prior art filter of FIG. 1 is a discrete-time filter which is responsive to a sampled input signal x. The input signal may be an analog sampled signal or a quantized and coded sampled signal, i.e., a digital signal. Shift register 10 and processing network 100 are, of course, compatible with the nature of the input signal appearing on lead 12.

Because it is a sampled system, each stage of shift register 10 stores one signal sample, or word, of the sampled signal x, and thus each stage of shift register 10 provides a one word delay D. Therefore, the output signals of shift register 10 can be expressed as Dx, D.sup.2 x, D.sup.3 x, . . . D.sup.19x s, where D.sup.3 x, for example, represents the signal x delayed by a 3 word delay -- or the signal output of the third stage of shift register 10. Utilizing the above nomenclature, the output signal z of the FIG. 1 circuit may be expressed by the canonic equation ##EQU3## where N is the order of the filter and the C.sub.i are the filter coefficients.

It has been discovered that the canonic expression of equation (1) may be equivalently written in the form ##EQU4## where m is an arbitrarily chosen integer, where N/m' is the fraction N/m truncated to its integer portion and where C.sub.i equals zero for i > N. It has been further discovered that the signal z may be computed by evaluating equation (2) in two steps.

The first step evaluates the expression ##EQU5## for various values of i, and the second step develops the signal z by evaluating the expression ##EQU6##

Equation (3) is similar in form to equation (1). It is different from equation (1) in that the number of terms in equation (3) is N/m' rather than N, in that only coefficients C.sub.km.sub.+i are employed rather than all the C.sub.i coefficients, and in that instead of the unit delays of equation (1) equation (3) contains delays of m units delays each. Because of the similarity in form, equation (3) may be implemented with structure not unlike that which implements equation (1), i.e., FIG. 1. Thus, the circuit implementing equation (3) employs a shift register having N/m' number of delays with each delay being m units long, and a filter processing network which computes the signals Y.sub.i by employing coefficients C.sub.mk.sub.+i. Once the Y.sub.i signals of equation (3) are evaluated, the desired signal z may be developed by evaluating equation (4). The circuit for evaluating equation (4) involves a relatively simple structure, as shown below.

FIG. 2 depicts one embodiment of a circuit employing the principles of this invention. As in FIG. 1, lead 12 applies the input signal x to a shift register. Unlike in FIG. 1, however, lead 12 is connected to a shift register 11 which provides only N/m' output leads. These leads emanate from shift register stages that are m units delay apart. Thus, including lead 12, shift register 11 provides (N/m'+1) output leads. In the particular embodiment illustrated in FIG. 2, m=5, N/m'=19/5 truncated, or 3, and N/m'+1 =4. The (N/m'+1) output leads of register 11 are connected to filter processing network 101 and to a computation network 41 within filter processing network 101. In computation network 41, the (N/m'+1) output leads of register 11 are connected to each of computation processors 40.sub.1, 40.sub.2, . . . 40.sub.i, . . . 40.sub.m. Within each computation processor 40.sub.i there are multipliers 40.sub.i0, 40.sub.i1, . . . 40.sub.ik, . . . 40.sub.i(N/m.sub.' ) for multiplying signals x, D.sup.m x, . . . D.sup.mk x, . . . D.sup. m(N/m.sup.') x by coefficients C.sub.(i.sub.-1), C.sub.m.sub.+(i.sub.-1), C.sub.2m.sub.-(i.sub.-1), . . . C.sub.(N/m.sup.') m.sub.+( .sub.-1), respectively. Additionally, within each computation processor 40.sub.i there is an adder circuit 400.sub.i for adding the multiplied signals to each other to form the intermediate signal Y.sub.i. For example, computation processor 40.sub.3 (i=3) in FIG. 2 multiplies the input signal x by C.sub.2 (in multiplier 40.sub.30), the signal of the first shift register output signal by C.sub.7 (in multiplier 40.sub.31), the signal of the second shift register output by C.sub.12 (in multiplier 40.sub.32), and the signal of the third shift register output by C.sub.17 (in multiplier 40.sub.33). The multiplied signals are added in summer 400.sub.3 to form the signal Y.sub.3.

Combining network 60 develops the signal z in accordance with equation (4). Therefore, combining network 60 is a responsive to the Y.sub.i signals developed by the computation processors in computation network 41 and comprises delay elements and adders arranged to properly delay and add the Y.sub.i signals to form the signal z. In the illustrative embodiment of FIG. 2, combining network 60 comprises a series, or cascade, interconnection of addition units 60.sub.1, 60.sub.2, . . . 60.sub.i, . . . 60.sub.m.sub.-1. Ech addition unit 60.sub.i includes a unit delay element 60.sub.i1 having its input comprise a first input terminal of addition unit 60.sub.i, and further includes a two input adder 60.sub.i2 whose one input is connected to the output terminal of unit delay element 60.sub.i1, whose other input comprises a second input terminal of addition unit 60.sub.i, and whose output comprises the output terminal of addition unit 60.sub.i. The cascade interconnection of the addition units is formed by connecting the output signal of each addition unit 60.sub.i to the first input terminal of the subsequent addition unit 60.sub.i.sub.+1. Combining network 60 is connected to computation network 41 by connecting the second input terminal of each addition unit 60.sub.i to the output signal of each computation processor 40.sub.i, i.e., to signal Y.sub.i. With respect to the end point connections, the first input terminal of addition unit 60.sub.m.sub.-1 (the last addition unit in the cascade interconnection) is connected to the output signal of computation processor 40.sub.m, and the output signal of addition unit 60.sub.1 comprises the output signal z.

A perusal of FIG. 2 reveals that the adder in each addition unit in FIG. 2 is responsive to the summer output signal within a corresponding computation processor. These two summing elements may conveniently be combined to form a single adder, and when thus combined, the filter processing network of FIG. 2, can be represented as shown in FIG. 3. For easier graphical representation, the elements in the filter processing network of FIG. 3 may be grouped into signal subprocessors, e.g., element 52, interconnected in cascade with a single unit delay element interposed between each pair of signal subprocessing. Alternatively, the elements in the filter processing network of FIG. 3 may be grouped into a cascade interconnection of signal processors, e.g., element 51. Thus, both FIGS. 2 and 3 perform the same function and develop the same output signal z by the use of essentially identical structural elements. Only the graphical positioning and grouping of the structural elements, i.e., the representation, is different between the illustrations of FIGS. 2 and 3.

FIG. 4 depicts a still different representation of the circuits of FIGS. 2 and 3. In FIG. 4, all of the multipliers located in the filter processing network (101) of FIG. 2 are grouped in a multiplication network 30, while the adders and the delay elements remaining in filter processing network 101 are grouped in a sum-delay network 50. The output signal z of network 50 is, thus, identical to the output signal z of FIGS. 2 and 3. For easier representation, network 30 may be thought of comprising (N/m' + 1) sets of multipliers (e.g., element 300) with each set of multipliers being responsive to one of the input signals of network 30.

FIGS. 2, 3, and 4, as shown, depict a transversal filter. To wit, the output signal z of the FIGS. 2, 3, and 4 circuits is a linear combination of a fixed number of past samples of the input signal x. The filter processing network 101 is not limited, however, to transversal filter applications. For example, FIG. 5 depicts a recursive filter configuration utilizing a shift register 11 responsive to a first signal, a filter processing network 101 connected to the above-mentioned first signal and to the output signals of shift register 11, and a summing network 60 for appropriately combining the input signal x with the output signal of network 101 to form the above-mentioned first signal. The output signal of the FIG. 5 circuit may be derived from any accessible terminal in the circuit and is, effectively, a function of all of the past samples of the input signal x. Accordingly, the output signal of the FIG. 5 circuit may be the output signal of adder 60, the output signal of any of the stages of shift register 11, or any combination thereof. In fact, a FIG. 5 filter output signal which is a linear combination of the input and output signals of register 11 can be implemented with a secondary filter processing network. This is illustrated in FIG. 6 where a secondary filter processing network 101' is added to the FIG. 5 circuit structure and is connected to the output signal of adder 60 and to each of the output signals of shift register 11.