Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-11-15
2003-12-16
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S319000
Reexamination Certificate
active
06665695
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of digital signal processors. More specifically, this invention relates to a circuit architecture and method for implementing a delayed adaptive least-mean-square digital filter in a general purpose, programmable digital signal processor.
BACKGROUND OF THE INVENTION
Adaptive digital filters may be used to perform many different tasks, including system identification, equalization, echo cancellation, active noise control, adaptive beamforming, and adaptive reception (i.e. in smart antennas). One method of adjusting the coefficients of an adaptive digital filter is by way of a least-mean-square (“LMS”) procedure, in which the filter coefficients are updated based on the error between the LMS filter output and a desired filter output.
More specifically, the error desired to be minimized is the difference between the filter's calculated output, which is calculated by convolving the most recent known input signal sequence with the filter transfer function, and the filter's desired output. The desired output may be based on the measured output of the system. A digital filter whose transfer function is based on a finite number of data samples is called a finite impulse response (“FIR”) filter.
For a filter with n coefficients, each coefficient corresponding to a tap, the system retains the most recent n samples of a data sequence and multiplies it by the n coefficients of the filter to get the calculated output. The data sequence x
m
includes the last n data samples x
0
, x
1
, x
2
, . . . , x
k−1
, x
k
, x
k+1
. . ., x
n−1
, the most recent retained data sample being x
0
, and the FIR filter includes coefficients h
0
, h
1
, h
2
. . . , h
k−1
, h
k
, h
k+1
. . . , h
n−1
. Every time a data sample is taken (in a telephone system that samples a data signal at 8 kHz, this occurs every 125 &mgr;s), the LMS procedure requires two main steps that involve each data sample and coefficient: (1) calculating the filter output and (2) updating the coefficients. (Hereinafter, the time period between data sample acquisitions will be referred to as a“frame.”) The filter output is calculated by multiplying the data sequence samples by the FIR coefficients; i.e.
y
=
∑
k
=
0
n
-
1
x
k
h
k
.
This requires n multiplications and n additions (x
0
*h
0
+x
1
*h
1
+x
2
*h
2
, etc.). The updating of coefficients requires two substeps. First, an update term is calculated by multiplying each data sample x
k
by a fraction &bgr; of the error (i.e. x
k
*&bgr;e). Next, the corresponding coefficient is updated by adding the update term to the old coefficient (e.g. h
k
(new)=h
k
(old)+x
k
*&bgr;e). This coefficient updating also requires n multiplications and n additions. Because the calculation to determine the &bgr;e term can be performed independently of the updating routine, this multiplication does not need to be performed for each individual coefficient.
In an attempt to simplify memory accesses and minimize power, some conventional implementations perform a“delayed” version of the LMS procedure, in which the data sample acquired during the previous frame and the error based on the data samples retained during the previous frame are used to update the coefficients (e.g. h
k
(new)=h
k
(old)+x
k+1
*&bgr;e
prev
). Conventional digital signal processor (DSP) filter architectures that perform this LMS procedure include an arithmetic logic unit (“ALU”) and a multiply and accumulate unit (“MAC”). The ALU is capable of performing addition, subtraction, or boolean algebra on two numbers and placing the result in an accumulator. The MAC is capable of multiplying two numbers, adding this result to another number, and placing the result in an accumulator. To calculate the filter output as well as to update the coefficients, two multiplications and two additions are required to be performed for each tap. Because there is only one multiplier available, two cycles of the clock must be used for each tap. For example, in an n-tap filter, x
k
is kept in the data memory buffer and h
k
is kept in the coefficient memory buffer. The error term, &bgr;e is calculated based on the previous frame's data samples and is stored in a temporary register because its value is constant for all n taps. The first cycle of the LMS procedure takes x
k+1
from the data memory buffer and uses the multiplier of the MAC to calculate the update term, x
k+1
*&bgr;e
prev
. That update term is stored in a first accumulator. The other cycle of the LMS procedure uses the multiplier of the MAC to calculate the part of the FIR output due to data sample x
k
, x
k
*h
k
, and that result is stored in a second accumulator. This cycle also uses the ALU to add the contents of the first accumulator (which holds the update term) to the coefficient h
k
, and the result is put back into the first accumulator. Then, at the beginning of the first cycle of the LMS procedure for the next tap, the contents of the first accumulator are stored in the coefficient memory buffer, writing over the old h
k
and leaving the first accumulator to store the update term corresponding to x
k
and h
k−1
.
Thus, the LMS procedure requires two clock cycles for each coefficient—one for the coefficient update term multiplication and one for the FIR output multiplication and coefficient update addition. Because this LMS procedure is constantly being performed, any savings in the numbers of clock cycles that it takes could result in significant time and power savings.
SUMMARY OF THE INVENTION
Although application-specific LMS filters may implement filters that reduce the number of clock cycles from two cycles per coefficient, a need has arisen for an improved adaptive LMS digital filter which performs the LMS procedure in a programmable digital signal processor in one clock cycle. In accordance with the present invention, a method for implementing a delayed adaptive LMS filter in a programmable DSP, in which the filter has one filter coefficient per tap and acquires a new data sample each frame, includes calculating an FIR filter output and updating the filter coefficients using an error term based on the FIR filter output calculated during the preceding frame. The calculations for each tap are performed in a single clock cycle.
Preferably, the FIR filter output is calculated by multiplying, in each clock cycle, a data sample and a corresponding coefficient and accumulating the products. Each filter coefficient is preferably updated by multiplying, in each clock cycle, a data sample and the error term to form an update term, and adding the update term to the coefficient. Preferably, the error term includes an adaptation gain. Preferably, the error term is the difference between a desired output and the FIR filter output calculated during the preceding frame. The desired output is preferably based on a system output value measured during the preceding frame.
Also in accordance with the present invention is a method for implementing a one-clock-cycle-per-tap delayed adaptive least-mean-square filter in a programmable DSP, in which the filter acquires a new data sample each frame. This method includes reading a coefficient from a coefficient buffer, reading from a data buffer a first data sample which corresponds to the coefficient, multiplying the coefficient by the first data sample and accumulating the product in a register to form an FIR filter output, updating the coefficient by adding to the coefficient the product of an error term, calculated during the preceding frame, and a second data sample, acquired during the frame preceding the frame in which the first data sample was acquired, and writing the immediately preceding coefficient to the coefficient buffer. Preferably, the error term includes an adaptation gain. Preferably, the error term is the difference between a desired output and the FIR filter output calculated during the preceding frame. The desired out
Alter David M.
Brokish Charles W.
Chaoui Jamil
Brady III W. James
Mai Tan V.
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Delayed adaptive least-mean-square digital filter does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Delayed adaptive least-mean-square digital filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Delayed adaptive least-mean-square digital filter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103776