Arithmetic-Free Digital Interpolation Filter Architecture

The present invention pertains in general to digital filters and, more particularly, to a finite impulse response filter for use in a digital-to-analog converter.

This application is related to U.S. Pat. No. 5,212,659, entitled "Low Precision Finite Impulse Response Filter for Digital Interpolation", issued May 18, 1993, which patent is incorporated herein by reference.

Digital-to-analog converters have recently seen an increased use of an oversampled architecture. Oversampled digital-to-analog conversion typically runs four, eight or even sixty-four times faster than the input word rate, requiring a corresponding by higher number of samples to be generated for every input sample. Typically, in this type of architecture, digital or discrete-time interpolation is utilized to provide this increase in the input word rate. In digital interpolation, two distinct steps are utilized. The first step of interpolation is to receive the input sequence x[n], representing the Fourier Transform X[f], at a sample rate of f.sub.s. This input sequence x[n] is processed to provide the output sequence y[n], which is essentially the sequence x[n] with M-1 zeroes interspersed between samples, where M is the interpolation factor.

In the frequency domain, the interspersing of zeroes simply rescales the frequency axis. However, the rescaled frequency domain now contains images of the original, low frequency signal. The images can be removed by straightforward, digital low pass filtering, which comprises the second step of the interpolation process. Therefore, the output of the digital low pass filtering step will be the sequence z[n], representing the Fourier Transform Z[f]. The sequence z[n] is the y[n] sequence with the zeroes "filled in". The end result is an interpolator output sequence whose samples occur at a rate that is faster than the input sample rate by a factor of M. The general process of interpolation is disclosed in R. E. Crochiere and L. R. Rabiner, "Interpolation and Decimation of Digital Signals: A Tutorial Review", Proc. IEEE, Vol. 69, pp. 300-331, March 1981, and A. B. Oppenheim and R. W. Schafer, "Discrete-Time Signal Processing", Englewood Cliffs, N.J.: Prentice Hall, 1989. Both of these references are incorporated herein by reference.

The first interpolation step is very conventional and generally comprises the steps of interspersing zeroes between the input samples, which is a relatively straightforward process. However, the second step of digital low pass filtering presents a problem to a hardware designer. Typically, a Finite Impulse Response (FIR) filter of length N is utilized due to the superior phase characteristics and out of band image rejection provided by this type filter. The input to the FIR filter is the y[n] sequence with a second input, the coefficient input, being provided from a storage area that has the coefficients h[0], h1], h2] . . . h[N-1]. This set of filter coefficients completely defines the frequency response of the FIR filter. The number of binary bits required to accurately represent each coefficient is dictated by filter performance parameters, the most sensitive one typically being stop-band rejection. This is disclosed in D. S. K. Chan and L. R. Rabinier, "Analysis of Quantization Errors in the Direct Form for Finite Impulse Response Digital Filters", IEEE Transactions on Audio and Electroacoustics, Vol. AU-21, pp. 354-366, August 1973, which is incorporated herein by reference.

In the case of interpolation, the filter stop-band rejection directly determines the extent to which the out-of-band images will be attenuated. The conventional rule of thumb is about 6 dB of stop-band or image rejection for every binary bit utilized to represent filter coefficients. The conventional filter is realized with a plurality of delay blocks, each having the input multiplied by the associated filter coefficient and then summed, the output rate of the FIR filter being faster than the word rate of the x[n] input sequence by a factor of M. Therefore, the filter must perform N/M multiplies and adds for every output word. Assuming the input data is represented by k binary bits and the FIR filter coefficients are represented by m binary bits, the computational requirement is that at the z[n] output word rate, there are required N/M (k.times.m) multiplies/adds or, that at the x[n] input word rate, there are required N(k.times.m) multiplies/adds. For example, if a 16-bit digital audio data input were interpolated from a word rate of 48 kHz to a rate 4.times. faster, this would result in a word rate of 192 kHz. A digital audio quality FIR filter operating at 4.times. may have a length N=128 with 14-bit coefficients. The resulting computational burden is 128 (16-bit.times.14-bit) multiplies/adds at 48 MHz. Note that the computation rate must double for a stereo implementation and, therefore, a single 16-bit.times.14-bit hardware multiplier must operate at 2.times.28.times.48 KHz=12.28 MHz for digital audio quality 4.times. interpolation.

Since this computation rate is close to the limit for state-of-the-art CMOS technology, and since fast parallel multipliers are too expensive in terms of silicon area to consider utilizing more than one, higher interpolation ratios (M>4) are typically realized in steps. For example, one conventional part number, Part No. SAA7322, manufactured by Philips, provides a stereo CMOS DAC for Compact Discs Digital Audio Systems that realizes a 256.times. interpolation factor in three separate steps: 4.times., 32.times. and 2.times.. The first step of 4.times. is implemented utilizing a multiplier-based 128 tap FIR. The second step of 32.times. is a simple linear interpolator, and the final 2.times. step is a zero-order hold. One can safely draw the general conclusion that although the last steps in a multi-step interpolation process can be quite rudimentary, the need for a fast (parallel) digital multiplier of k-bit input data by m-bit filter coefficients has persisted in conventional, digital audio quality interpolation architectures.

In view of the above disadvantages, there exists a need for an interpolation scheme that provides a relatively high precision FIR filter to result in significant rejection in the stop-band without requiring the expensive and complex multipliers of conventional units.

The present invention disclosed and claimed herein comprises an interpolation filter for filtering a digital input signal sampled at a sampling frequency and providing a filtered digital interpolated output signal. A first memory device is provided for storing the digital input signal. A second memory device is provided for storing filter coefficients that are associated with a Finite Impulse Response (FIR) filter function. The filter coefficients are restricted to only discrete values with the filter coefficients associated with each of the interpolated digital outputs requiring a predetermined number of arithmetic operations in accordance with the FIR filter function. At least one of the arithmetic operations associated with each of the outputs results in a zero value. An operational device is provided for performing all but the at least one of the arithmetic operations. The results output by the operational device are input to an accumulator for accumulation thereof. After all the arithmetic operations are performed for a given digital output, the accumulator provides the digital output value.

In another aspect of the present invention, a defined number of the filter coefficients for each of the digital output signals are set to a "0" value, and the set of arithmetic operations that are performed exclude ones associated with the defined number of "0" filter coefficients. The set of filter coefficients of the remaining ones of the arithmetic operations not included within the set of "0" filter coefficients is restricted to the set of {-1, 0, +1}, such that the arithmetic device need only change the sign of the selected value from the first memory device when the value of the coefficients is "-1" before input to the accumulator, input the selected value from the first memory device directly to the accumulator for a "+1" filter coefficient value and enter a "0" value to the accumulator for a "0" filter coefficient. Further, the operation is performed in a sequential manner such that no multipliers or additioal adders are required.

In a further aspect of the present invention, the first memory device is comprised of a random access memory having a plurality of storage locations therein that are addressable. The FIR filter coefficients are stored in a read only memory in a predetermined sequence. The sequence is comprised of a plurality of subsequences, with each subsequence associated with one of the digital output values. Each of the subsequences of filter coefficients has associated therewith the address of the stored input sample in the random access memory. When the read only memory is sequenced through each subsequence, the random access memory is addressed, the output value from the random access memory input to the operational device and the operational device controlled by the filter coefficient output by the read only memory to either change the sign, input a zero value or directly input the value to the accumulator.

In a yet further aspect of the present invention, an output filter is provided having a low-pass function. The output filter has a predetermined frequency response having a pass-band droop. This pass-band droop is compensated for by the design of the FIR filter coefficients. Further, the low-pass output filter function is performed in part by the accumulator. This aspect can also applied to providing phase equalization for the output filter, wherein the FIR filter coefficients are designed to compensate for any phase perturbations in the output filter.

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying Drawings in which:

FIG. 1 illustrates a block diagram of the interpolation filter utilizing the low-precision FIR coefficients;

FIG. 2 illustrates the required interpolation frequency response required for the overall interpolation filters;

FIGS. 3a and 3b illustrate the frequency responses of the FIR filter with low-precision coefficients and the subsequent low pass filter;

FIG. 4 illustrates a block diagram of the FIR interpolation filter of the present invention, utilizing a digital-to-analog converter;

FIGS. 5a-5e illustrate the frequency response plots for the various stages of the embodiment of FIG. 4;

FIG. 6 illustrates the preferred embodiment of the present invention;

FIG. 7 illustrates a block diagram of the FIR interpolation filter;

FIG. 8 illustrates a more detailed block diagram of the interpolator of the present invention;

FIG. 9 illustrates a block diagram of the preferred embodiment;

FIG. 10 illustrates a diagrammatic view of the ROM address space;

FIG. 11 illustrates a flowchart for the overall process flow;

FIG. 12 illustrates a block diagram of the switched capacitor analog low pass filter and one-bit DAC utilized in the output section;

FIG. 13 illustrates a block diagram of the software delta-sigma modulator utilized to generate the low precision coefficients; and

FIGS. 14 and 15 illustrate plots for an example utilizing FIR filter coefficients in the set {-1, 0, +1}.

Referring now to FIG. 1, there is illustrated a block diagram of the interpolator of the present invention. The interpolator is generally represented by a block 10 that is labelled "FIR interpolator". The interpolator is comprised of the interpolation block that is operable to intersperse zeroes between the samples in the x[n] input sequence and the filtering step wherein the passband response is defined and the images are partially filtered out. As will be described hereinbelow, this provides the low frequency response which is required for high quality interpolators. This results in the output z[n] sequence, which is a filtered output that is interpolated by a factor M. This is input to a low pass filter block 12, which has a cutoff frequency f.sub.c that is equal to f.sub.s/2. This results in an output z'[n] that operates at a sampling frequency Mf.sub.s. It should be noted that the FIR interpolator 10 operates on low precision FIR coefficients stored in a block 13, which coefficients are utilized to define the frequency response of the filter portion of the FIR interpolator 10 at the low frequency. However, as will be described hereinbelow, the low precision coefficients do not result in a desirable stop band response at higher frequencies. This is achieved with low pass filter block 12.

Referring now to FIG. 2, there is illustrated an overall frequency response for the complete interpolation process. Once the zeroes are interspersed among the samples in the input sequence x[n], it is necessary to provide this type of overall response for applications such as digital-to-analog converters. In the preferred embodiment, the interpolation operation is a single step 64.times. interpolation with a 1408 tap FIR filter with the FIR filter coefficients restricted to the set {-1, 0, +1}. The pass band ripple of the filter response is .+-.0.10 dB, with a pass band definition of +0.20 dB, -0.50 dB. The transition band is a transition between the pass band and the stop band with this existing between 0.442-0.567F.sub.s. The stop band rejection is desired to be greater than 70 dB. Therefore, a very sharp filter is required, which is the purpose for utilizing a FIR digital filter.

Referring now to FIG. 3a, there is illustrated a frequency plot of the FIR interpolation filter utilized in the present invention. The filter is designed such that the pass band and the transition band meet the overall design requirements for a FIR filter designed with high precision FIR filter coefficients such that, proximate to the transition band, the stop band has a desirable amount of attenuation. However, it can be seen that the attenuation of the stop band above the point proximate to the transition band gradually degrades and is unacceptable. This will be described in more detail hereinbelow.

Referring now to FIG. 3b, there is illustrated a frequency response plot for a low pass filter function that is associated with the low pass filter 12 and which filters out the degradation in the stop band that is unacceptable with respect to the frequency response of FIG. 3a. The combination of the response of FIG. 3a and the response of FIG. 3b results in the desired response of FIG. 2. However, the response of FIG. 3a was obtained with very low precision FIR filter coefficients and the response of FIG. 3b was obtained with the use of the relatively straightforward filter design. In the preferred embodiment, the low pass filter 12 is comprised of an output switched capacitor filter operating in the analog domain on a digital-to-analog converter. However, it should be understood that the digital filter function could be implemented in the digital domain at the higher sampling frequency.

Referring now to FIG. 4, there is illustrated a functional block diagram of the preferred embodiment of the present invention. The input sequence x[n] is a multi-bit input, typically sixteen bits, that is input to sample rate converter 16 that is operable to increase the sampling rate to a factor of 64.times. the sampling frequency of the input sequence x[n]. This results in an output sequence of y[n] that is also a multi-bit signal. The sequence y[n] is input to a FIR low pass filter 18, which has FIR filter coefficients restricted to the set {-1, 0, +1} for each stage of the filter, as described above. The FIR low pass filter 18 is operable to filter out the images resulting from the interspersing of zeroes in the sample rate converter 16. This results in the filtered sequence z[n], which is also a multi-bit sequence operating at 64.times. the sampling frequency. This is input to a conventional delta-sigma modulator 20 that is operable to output a digital 1-bit output at 64.times. the sampling frequency, which output is then input to an analog low pass filter/1-bit digital-to-analog converter (DAC) 22. This provides the analog output of the overall digital-to-analog converter. As will be described hereinbelow, the sample rate converter 16 and filter 18 are implemented with a single RAM device, with a final accumulator and coefficients stored in ROM.

Referring now to FIGS. 5a-5e, there are illustrated frequency plots for each step of the conversion process. FIG. 5a illustrates the frequency response X[f], which is the frequency response for the input data. As expected, this is merely a sinusoid with a single frequency component 24 in the frequency spectrum. It can be seen that this is substantially less than f.sub.s /2. FIG. 5b illustrates the frequency response for the sinusoid of FIG. 5a at the output of the sample rate converter 16, illustrating the images of the sinusoid that result after the interspersing of zeroes between the samples in the x[n] input sequence. FIG. 5c illustrates the output of the FIR low pass filter 18 with the low precision FIR coefficients, where it can be seen that the sinusoid is passed through the pass band, as illustrated by a frequency component 26, and the remaining images are filtered out with the images most proximate to the transition band and just outside the pass band, being heavily attenuated, and the remaining images being less heavily attenuated in a gradual manner. FIG. 5e illustrates the output of the analog low pass filter/DAC 22, wherein all of the images in the stop band are significantly attenuated. Therefore, it can be seen that the use of the low precision FIR low pass filter, that provides the desired low frequency response in the pass band and about the transition band, can be combined with the low pass filter to result in an overall frequency response that is equivalent to that of a high precision FIR low pass filter for utilizing multi-bit FIR coefficients. For example, a high precision FIR low pass filter could require in excess of fourteen bits for each coefficient, which would require relatively complex multiplier stages in the circuitry that is utilized to realize the FIR low pass filter.

Referring now to FIG. 6, there is illustrated the preferred embodiment of the digital-to-analog converter utilizing the low precision FIR low pass filter. The output of the FIR low pass filter 18 results in high frequency images that approach or exceed the magnitude of the pass band sinusoid. It would therefore be anticipated that the operation of a digital delta-sigma modulator 20 would be degraded due to the image energy at the high end of the stop band being input to the digital delta-sigma modulator. To prevent this, a relatively simple image attenuating digital filter is provided after the low precision coefficient FIR low pass filter 18 to reduce these stop band images. To attenuate these high frequency images, the filter need only attenuate the gradual rise in the image energy resulting from the use of the low pass filter 18 with the low precision coefficients. The filter that is utilized in the present invention is a zero-order hold or SINC filter. This filter is described in E. B. Hogenauer, "An Economical Class of Digital Filters for Decimation and Interpolation", IEEE Trans. Acoust. Speech, Signal Processing, Vol. ASSP-29, pp. 155-162, April 1981, which reference is incorporated herein by reference. The zero-order hold filter provides an impulse response that is defined by the following transfer function: ##EQU1## When N in the zero-order hold transfer function that is equal to the oversampling or interpolation ratio M, this filter is relatively easy to implement. It utilizes a low speed differencing block 30 that provides the transfer function "1-z.sup.-1 ", which operates at the input sampling frequency. The input sequence x[n] is a 16-bit word input on a bus 32 to the input of the block 30. The output of the block 30 is provided on a bus 34, which comprises a seventeen-bit output operating at the sampling frequency f.sub.s. This is input to the sampling rate converter 16. The sampling rate converter 16 is then operable to increase the sampling rate by a factor of 64 to provide a seventeen-bit output on a bus 36. This is then input to the FIR low pass filter 18 that utilizes low precision FIR filter coefficients stored in the coefficient memory 14. This will then provide a digitally filtered output on a bus 38 that is a twenty-one-bit output operating at 64.times. the sampling frequency f.sub.s. This is input to a high speed accumulator 40, having a transfer function equal to: ##EQU2## The high speed accumulator 40 operates at 64.times. the input sampling frequency, whereas the difference block 30 operates at the lower speed sampling frequency. The combination of the accumulator 40 and the difference block 30 provide the zero-order hold filter function, which is sometimes referred to as a Comb-Integrate-Cascade filter (CIC). One disadvantage to the utilization of the zero-order hold filter having an impulse response length equal to the interpolation function ratio is that a pass-band droop of approximate 4 dB results. However, this can be compensated for in the design of the FIR filter by being designed to offset this pass-band droop.

The output of the accumulator 40 is a twenty-three-bit output, operating at 64.times. the sampling frequency f.sub.s, which is output on a bus 42 to the digital delta-sigma modulator 20. The one-bit output of the modulator 20 is then input to a one-bit digital-to-analog converter 44 and then to a switched capacitor low pass filter 46. This provides the analog output. The design of the one-bit digital-to-analog converter 44 and the switched capacitor low pass filter 46 is described in U.S. Pat. application Ser. No. 07/571,376, filed Aug. 20, 1990, now issued as U.S. Pat. No. 5,061,925, which is incorporated herein by reference. The 5,061,925 patent also discloses a phase equalization technique which is also utilized in the digital-to-analog converter of the present invention. In this manner, the overall phase and frequency response of the FIR filter 18 and the switched capacitor filter 46, which is an Infinite Impulse Response Filter (IIR), are designed together such that phase deficiencies in either filter can be compensated by the design of the other filter.

Referring now to FIG. 7, there is illustrated a block diagram of a conventional FIR filter of filter length N. The input sequence y[n] is received on an input 48 and input to a sequence of delay blocks 50, each providing a delay of "z.sup.-1 ". Input y[n] is also input to one of a series of multipliers 52, which input is multiplied by a FIR filter coefficient h[n]. The output of this multiplier 52 is then input to a summing block 54 to perform an addition operation. The output of each of the subsequent delay blocks 50 are also input to an associated one of the multipliers 52 and multiplied by successive ones of the filter coefficients. The output of each of the multipliers 52 is input to the summing block 54 that provides the addition operation. The output of the summing block 54 provides the output sequence z[n].

If the FIR coefficients are consistent with the design of a high precision FIR filter, they will have a word length in excess of fourteen bits. Whenever utilizing a multi-bit FIR coefficient, this results in the requirement for a relatively complex multiplication block. This is due to the fact that a number of shifting operations and addition operations will be required in accordance with conventional digital multiplication techniques. It is one important aspect of the present invention to reduce this complexity, if not eliminate it. In the preferred embodiment of the present invention, the FIR filter utilized to perform the low pass filtering function on the output of the interpolator to adequately attenuate the first out-of-band image is designed utilizing very trivial coefficients restricted to the set {-1, 0, +1}. However, it could have been designed restricted to the set coefficients restricted to the set {-1, +1} or {-2, -1, 0, +1, +2}.

For a conventional 2048 tap FIR filter utilizing 64.times. interpolation, the filter will have 2048/64=32 words of non-zero input data in the tapped delay line in any given instance. If one ignores the fact that some coefficients in the h[n] set are zero instead of .+-.1, each interpolator output requires a selective summation of thirty-two input data words. If one were to assume that 256 f.sub.s is the maximum available clock rate for performing the required additions, the total number of clock cycles available for each 64 f.sub.s interpolator output is four. Therefore, the required number of hardware adders would be eight, which is four clock cycles for each thirty-two additions per interpolator output. If, on the other hand, a 512 f.sub.s clock were available for an equivalent 2048 tap FIR realization, the hardware requirement would be reduced to four adders per every channel.

Although the hardware requirements are reduced by utilizing a higher speed clock to minimize the number of adders that are required and the non-trivial set of coefficients that alleviate the need for multipliers, some hardware is required in the form of adders to generate the appropriate inputs to the accumulator. As will be described in detail hereinbelow, the h[n] coefficient set has a large number of zeroes associates therewith. The large number of zeroes can be utilized to reduce the number of adders to zero.

An important aspect of the present invention is storage of the interpolator data in a random access memory (RAM) to allow random accesses for each interpolator output. Since each operation merely requires accessing of the data and changing of its sign prior to input to the accumulator, the number of operations are minimized. Further, only the input data words that correspond to "non-zero" coefficients of the FIR filter are accessed. There is no need to access an input data word if it is merely being multiplied by zero.

By way of background, in a single frame, the interpolator output z[n] can be expressed as illustrated in Table 1:

where, y[k] is the input data and h[n] is the set of FIR coefficients belonging to the trivial set {-1, 0, +1}. A normal convolution implementation would access every y[k] and multiply it by the corresponding h[n], whether it was zero or not. In the present invention, only the y[k] that are multiplied by "non-zero" h[n] are accessed. Since a great number of h[n] are zero for the {-1, 0, +1} set of FIR filter coefficients, this can significantly reduce the number of addition operations that are required to calculate the z[n] outputs.

Referring now to FIG. 8, there is illustrated a 4.times. interpolation filter with a length of sixteen. There are four data words from the input stream y(k+1), y(k+2), y(k+3) and y(k+4), that are input and shifted through the delay line formed of a plurality of delay blocks 56. There are sixteen coefficients, h[0]-h[15] in the nontrivial set {+1, 0, -1}. There are only four non-zero inputs for the data position in the delay line which need to be calculated. These are associated with the coefficients h[3], h[7], h[11] and h[15]. However, the coefficient h[15] and the coefficient h[11] are equal to zero, with the coefficient h[7]=+1 and the coefficient h[3]=-1. For this set of coefficients, only two additions are actually required. However, it can be seen that for the next interpolator output, the data is shifted over one delay line such that the input value y[k] is now input to the h[0] coefficient block and so forth. Depending on the coefficient set, some outputs may require the entire four additions and some may require as little as one addition. The additions are performed in an accumulator 58 to provide an output therefrom at the 4 f.sub.s sampling rate to the delta-sigma converter. It should be understood that the above description was for illustrative purposes, as a filter of length sixteen would not suffice in a data conversion application since it could not be realized with low precision coefficients.

Referring now to FIG. 9, there is illustrated a block diagram of the preferred embodiment of the FIR filter. The input data stream at sampling frequency f.sub.s is received on an input data bus 60 and input to an adder 62. The input data on the input data bus 60 is also processed through a delay block (z.sup.-1) 64, the output thereof input to a negative input of the adder 62 such that the adder 62 performs a subtraction operation. This provides the difference between the input data on bus 60 and the output of the delay block 64 on a bus 66 as a 17-bit data word. This data is then input to a random access memory (RAM) 68, which RAM 68 allows for storage of thirty-two words of 17-bit data to allow the possibility of implementing the 2048 tap filter. However, as will be described hereinbelow, the preferred embodiment utilizes a filter that is 1408 taps.

The RAM 68 is illustrated as being a dual port RAM having an input bus 66 and an output bus 70. The RAM 68 is addressed for output purposes by a ROM 72, which provides on the output thereof an address input for the RAM 68 on an address bus 74. In the dual port RAM 68, an address will also be provided on the input associated with the bus 66, although it is not shown. However, the RAM 68 illustrated in FIG. 9 could be a single conventional RAM wherein the address bus to the RAM 68 is multiplexed for the input operation and the output operation. In this mode, the data would first be input to the RAM 68 in one cycle and then accessed in another cycle using the same address bus and the same data bus, with the address and data buses multiplexed. Again, this is a conventional operation.

For the output operation, the output data bus 70 from the RAM 68 is input to a sign change block 76 which is operable to selectively change the sign of the data, the output thereof input to one input of a two-input multiplexer 78. The other input of the multiplexer 78 is connected to a "0" digital value. Therefore, the multiplexer 78 selects from a "0" value or the output of the sign change block 76 to provide on the output thereof a 17-bit word on a data bus 80. However, as will be described hereinbelow, this output is at a much higher rate, a rate of 512 f.sub.s. This is input to an output accumulator 82, which output accumulator effectively provides the function: ##EQU3## The output accumulator 82 is sampled on the output thereof at a rate of 64 f.sub.s by the delta-sigma converter.

The data in the RAM 68 is accessed at eight times the 64 f.sub.s clock rate, although it is input in the f.sub.s clock sampling rate. This therefore requires a 512 f.sub.s clock 84 to be present. This clock is utilized to control the ROM 72 and the output accumulator 82. The ROM is operable to selectively address the ones of the data words that are to be multiplied by "non-zero" coefficients, and since the coefficient set is restricted to the trivial set {-1, 0, +1}, it is only then necessary to change the sign of the output data if it is a negative coefficient.

The coefficient set is selected such that only eight data words will be multiplied by "non-zero" coefficients wherein each interpolator output requires only eight additions, as compared to thirty-two additions. Of course, if a faster clock were available, more additions could be performed. Additionally, if one of the sets of coefficients for any of the interpolator outputs results in less than eight multiplications with "non-zero" coefficients, this will of course be a "0" value and the multiplexer 78 is utilized to select the "0" value for output.

The ROM 72 is controlled with a ROM sequencer 73, which is operable to sequentially address the word locations in the ROM 72. For each frame, the storage locations in the ROM 72 are completely sequenced through by sequentially stepping through the addresses of the ROM 72. At the end of the sequence, i.e., the end of the frame, the ROM sequencer 73 is reset and then the data stored in the RAM 68 incremented, such that the oldest data sample is discarded and a new data sample stored in a First-In-First-Out (FIFO) manner. This will begin the next frame.

Referring now to FIG. 10, there is illustrated a diagrammatic view of the ROM address space. The ROM address space is arranged such that each interpolator output z[n] has eight addresses associated therewith. The eight addresses each comprise three fields, a RAM address field 92, a sign change bit field 94 and a "0" field 96. The RAM address field 92 defines the address of the RAM that is input on the bus 74, the sign change bit field 94 comprises a single bit that is output on a line 98 to the sign change block 76 to indicate whether the sign is to be changed. If the bit is set high, this indicates a negative operation and if the bit is set "low", this indicates a positive operation wherein the sign is not changed. If the bit in the "0" field 96 is set high, this indicates that the multiplexer 78 is to have the "0" value passed therethrough. This field 96 has the output thereof connected to a line 100 to the input of a multiplexer 78 to control the operation thereof.

The ROM address space is arranged such that the first eight ROM addresses are associated with the first interpolator output z[0] and the last eight addresses stored therein are associated with the z[63] output. The ROM 72 is controlled to output the data in a sequential manner at a rate of 512 f.sub.s as controlled by the clock 84 utilizing an input address counter (not shown). This allows the ROM 72 to operate in the most efficient manner. Therefore, it is only necessary to sequence the ROM 72 from its initial address through 512 cycles and then reset the ROM sequencer 73.

Referring now to FIG. 11, there is illustrated a flowchart depicting the overall process flow. The flowchart is initiated at a start block 101 and then proceeds to a function block 102 wherein data is loaded at the sampling frequency f.sub.s. The program then flows to a function block 104 to process the data during loading with the function (1-z.sup.-1). The program then flows to a function block 106 to set the value of an arbitrary designator "n" to zero, and then flows to a function block 108. The function block 108 begins the access operation for the first interpolator output z[n] at the sampling rate 64 f.sub.s. The addresses associated with each of the z[n] outputs are accessed at the 512 f.sub.s rate. The program then flows to a function block 110 to address the RAM 68 and then to a function block 112 to change the sign of the data output from the RAM 68. The program then flows to a function block 114 to input the data to the accumulator 82, again at the 512 f.sub.s rate. The program then flows to a decision block 116 to determine if the address number eight has been reached. If not, the program flows along an "N" path through a function block 118 to select the next address and then back to the input of function block 110. This continues until all eight address have been accessed for a given output z[n], the RAM 68 addressed and the sign of the output value changed if necessary. At this point in time, the program will flow along the "Y" path to a function block 120 to output the accumulated value from the accumulator 82 at the 64 f.sub.s rate. The program then flows to a decision block 122 in order to determine if the value of "n" is equal to a maximum. If not, the program flows along an "N" path to a function block 124 to increment the value of "n" by one and then back to the input of the function block 108 to begin the operation for the next interpolator output. When the value of "n" is equal to a maximum, this indicates the completion of the operation on the loaded data and then the program flows back to the input of function block 102 to load the next data word at the beginning of a new frame.

In the preferred embodiment, it is important to determine what length FIR filter can be designed and trivialized such that each interpolator output requires at most eight non-zero summations of input data. At present, the longest known FIR filter has a length of 1408 taps, for which a sparsity-ignorant implementation would demand 1408/64=22 operations per interpolator output. For this type of filter, the use of the arithmetic-free interpolation architecture would reduce the number of additions required by 64%. In this configuration, only 22 words of data need to be loaded into the RAM, as compared to 32 words for a 2048 tap filter.

Referring now to FIG. 12, there is illustrated a detailed logic diagram of the switched capacitor filter 46 and the one-bit DAC. The one-bit DAC is comprised of a capacitor 121 and a capacitor 123 and voltage reference V.sub.REF. Two switches 125 and 126 are provided, having two poles, one connected to V.sub.REF, and one connected to ground. Each of the switches 125 and 126 has a switching arm connected to one side of capacitors 123 and 121, respectively. The other side of capacitors 123 and 121 are connected to the switching arms of switches 128 and 130. Switches 128 and 130 have two poles, one connected to ground and one connected to the input of a switched capacitor filter. In operation, capacitor 123 has one of its plates connected to the positive voltage and one of its plates connected to ground and then switches the one plate to ground and the other plate to the input of the switched capacitor filter. When the capacitor 122 is configured to have the one plate associated with switch 128 connected to ground and the one plate associated with switch 125 connected to the positive voltage, both plates of capacitor 121 are connected to ground. When the charge is transferred to the input of the switched capacitor filter, the one plate of capacitor 121 associated with switch 126 is connected to a positive voltage and the one plate of the capacitor 121 associated with switch 130 is connected to the input of the switched capacitor filter. This is a conventional 1-bit DAC.

The switched capacitor filter is a third order Butterworth low pass filter that is comprised of three switched capacitor stages. The first stage is comprised of an amplifier 132 having a negative input connected to one pole of switches 128 and 130 and the positive input thereof connected to ground. A capacitor 134 is connected between the output of amplifier 132 and the input thereof. A capacitor 136 has the plates thereof connected to the switching arms of switches 133 and 135. Capacitor 136 operates in a switched capacitor configuration with one plate tied to ground and the other plate tied to the non-ground pole. Switch 133 switches the one plate of capacitor 136 between the output of amplifier 132 and ground and switch 135 switches the other plate of capacitor 136 between the negative input of a second amplifier 138, associated with the second stage, and ground. The positive input of amplifier 138 is connected to ground. A capacitor 140 is connected between the negative input and the output of amplifier 138, and a switched capacitor 142 is disposed between the negative input and the output of amplifier 138 and switched between the input and output thereof and ground through switches 139 and 141, such that in one mode it is connected in parallel with capacitor 140 and, in another mode, has both plates connected to ground.

A switched capacitor 144 is connected between either the output of amplifier 138 and the negative input of amplifier 132 or ground through switches 143 and 145, such that either both plates are connected to ground or the capacitor is disposed across the output of amplifier 138 and the negative input of amplifier 132. A third amplifier stage 147 is provided, with a switched capacitor 148 connected in a switched configuration between the output of amplifier 138 and the negative input of amplifier stage 147 through switches 149 and 151. Switches 149 and 151 operate to connect one side of the capacitor to ground and the other side of the capacitor to the non-grounded pole. A capacitor 153 is disposed in parallel between the input and output of amplifier stage 147 and a switched capacitor 155 is connected in parallel with capacitor 153 through switches 157 and 159. Switches 157 and 159 operate to either connect both plates of capacitor 155 to ground or in parallel with capacitor 153. The output of amplifier stage 147 comprises the output of the third order filter.

In the preferred embodiment, the data is comprised of one-bit data output from the digital delta-sigma modulator, wherein switch 128 is closed as a function of the data input anded with a clock .psi..sub.2, and the switch 130 is controlled by the anding of inverted data and clock signal .psi..sub.2. This is a conventional operation. The switched capacitor filter operates on a sample rate equal to 64f.sub.s and with a -3 dB frequency equal to f.sub.s /2. The ratio utilized in the preferred embodiment for the capacitors are as follows:

In order to determine what the initial low precision filter coefficients are for the present invention, it is first necessary to design the filter utilizing floating point precision FIR low pass filter coefficients. This is done utilizing a very conventional Parks-McClellan design, which coefficients are then processed through a software delta-sigma modulator or quantizer. The frequency response with the floating point coefficients would be as follows: ##EQU4## After processing through the software delta-sigma modulator, the following frequency response would occur: ##EQU5## This would result in the response of FIG. 3a. The software delta-sigma modulator is therefore utilized to truncate the floating point precision FIR coefficients to a very low or trivial level in a frequency selective manner, such that the frequency response error due to truncation is gradually concentrated to higher frequencies. This is illustrated by the gradual rise in frequency distortion illustrated in FIG. 3a.

The truncation of the floating point precision FIR coefficients has been described in T. W. Wong and R. M. Gray, "FIR Filters with Sigma-Delta Modulation Encoding", IEEE Trans. on Acous., Speech and Signal Processing, Vol. 38, pp. 979-990, June 1990, which reference is incorporated herein by reference. Although this paper describes only a first or second order delta-sigma modulator, the preferred embodiment has utilized a fourth order software delta-sigma modulator to quantize the FIR coefficients. This is illustrated in FIG. 13. In FIG. 13, the floating point precision FIR coefficients h[n] are input to a summing block 150, the output of which is input to an accumulator 152. The output of the accumulator is input through a scaling block 154 to a summing block 156 and also to the input of a second accumulator 158. The output of accumulator 158 is input to the summing block 156 through a scaling block 160 and also to the input of a third accumulator 162. The output of the accumulator 162 is input through a scaling block 164 to the summing block 156 and also to the input of a fourth accumulator 166. The output of the fourth accumulator 166 is input through a scaling block 168 to the summing block 156. The summing block 156 sums the outputs of the scaling blocks 154, 160, 164 and 168 and inputs them to a quantizer 170. The quantizer 170 is operable to quantize the output of summing block 156 into the specified number of coefficients, which in the preferred embodiment is restricted to the set {-1, 0, +1}. The output of the quantizer 170 is then input to the summing block 150, the output of quantizer 170 also representing the low precision filter coefficients.

The state variables that exist at the output of each of the accumulator blocks 152, 158, 162 and 166 are set to an initial value of zero. This was described in the Wong and Gray reference. However, if the final value of the state variables is not equal to zero, this will result in quantization noise smearing. This can be understood by interpreting the finite length sequence of FIR coefficients as one period of a periodic sequence. Due to the non-linear nature of the Delta-Sigma encoder, the quantization error introduced when encoding a periodic input sequence will not, in general, be periodic. A rectangular window of length equal to one period must be applied to the Delta-Sigma output to isolate a set of low precision FIR coefficients. The consequence of the smearing that results from the existence of this rectangular window is that the stop band attenuation of the low precision coefficient FIR will be limited, since high frequency quantization noise will inevitably be smeared into the sensitive stop band region immediately following the transition band. The solution to this is to force periodicity in the delta-sigma output sequence by forcing the final value of the Delta-Sigma state variables to be equal to zero, which will result in a periodic low precision FIR coefficient sequence. By forcing equivalence of the state variables initial and final values, the noise smearing effects of the rectangular window are nullified. In order to ensure that no more than eight non-zero coefficients exist for any operation, some iterative operations are performed. This can involve manipulating the set of coefficients after calculation thereof, or adjusting the quantizer thresholds in block 170.

In one example, a 64.times. interpolation filter was designed, having a multiplier-free FIR length of 1408 taps. The FIR coefficients allowed were -1, 0, and +1. The resulting coefficients are attached as Appendix A. FIG. 14 illustrates the response of the FIR filter 18 where it can be seen that significant stop band rejection is provided immediately after the transition band. It can also be seen that some peaking is provided at the end of the pass band to account for pass band droop as a result of the zero-order hold filter and also to compensate for any attenuation in the switched capacitor filter. FIG. 15 illustrates a plot at the output of the accumulator 82, illustrating further attenuation of the higher frequency images. It can be seen that the zero-order hold circuit places a number of zeroes at the images. The overall response curve for the filter after the analog low pass filtering operation of the low pass filter will result in further attenuation of the higher frequencies.

Although, as noted above, the trivial set of coefficients is restricted to the set of {-1, 0, +1} other coefficients having an integer value can also be utilized as part of the non-trivial set. For example, the coefficients could be restricted to the set of {-2, -1, 0, +1, +2} or {-3, -2, -1, 0, +1, +2, +3}. In order to facilitate the use of higher integer values than "1", it will be necessary to perform an arithmetic operation utilizing such a coefficient. The one advantage to the system described hereinabove is that no arithmetic operation is performed other than the accumulation operation. This is due to the fact that only a +1 or a -1 coefficient is utilized, with the "0" coefficient operations being ignored. With a coefficient higher than "1", it is necessary to perform a multiplication with the higher value coefficient. However, in the preferred embodiment, this would merely require additional accumulation operations. For example, if there were eight collected multiplications, then either eight arithmetic operations utilizing a +1 or -1 coefficient could be accommodated or six arithmetic operations involving a +1 or a -1 operation and one involving either a +2 or a -2 operation. When performing the operation for the +1, +2 or -2 operation, it is only necessary to perform the accumulation twice for that input data value, i.e., rather than multiplying by a factor of "2", it is only necessary to add the value twice. For a value of "3", it will be necessary to add the value three times. As such, the set of coefficients can be generated such that for each output, the non-zero coefficients will acquire only a finite number of clock cycles to perform all of the arithmetic operations. This will therefore require one additional zero coefficient if one of the coefficients is a value of "2" and two additional zero coefficients if one of the coefficients is a "3" value. Utilizing higher value coefficients than "1", another degree of versatility is provided through the step of generating the coefficient set.

In summary, there has been provided an arithmetic free interpolation filter that operates with minimum precision FIR coefficients. In the preferred embodiment, only three coefficients in the set of {-1, 0, +1} are utilized such that a multiplierless filter can be designed. Further, for each operation, the number of non-zero coefficients for any interpolator output is minimized to a predetermined number. By so limiting the number of non-zero coefficients for any given interpolator output, the number of additions and/or subtractions can be set. In the preferred embodiment, the data is stored in a RAM and then addressed in accordance with the coefficients for any given interpolator output and stored in an accumulator after the sign thereof is changed. Since the number of operations for each interpolator output is known, it is only necessary to increase the clock speed of the accumulation operation and the addressing address of the RAM such that the predetermined number of operations results in a predetermined number of RAM accesses for output thereof and storage in the accumulator during a given operation cycle for a given interpolation output.

Although the preferred embodiment has been described in detail, it should be understood that various changes, substitutions and alterations can be made therein without departing from the spirit and scope of the invention as defined by the appended claims.