Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-04-16
2004-06-29
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06757702
ABSTRACT:
The invention relates to an adaptive filter.
PRIOR ART
Adaptive filtering can advantageously be used to restore digital signals subjected to interference, particularly if the interference is caused by crosstalk or by a transmission channel whose channel characteristics are unknown or affected by a timing error.
A simple adaptive filter algorithm is the known LMS algorithm, which requires 2N multipliers for an N stage filter structure. However, each of these multipliers must be sufficiently accurate to ensure the requisite stability. The known LMS algorithm can be realized by software or by a combination of software and hardware filter structures. In the case of a real-time hardware realization, however, there is the disadvantage of the high outlay on circuitry, which is too cost-intensive for some applications.
INVENTION
The invention is based on the object of specifying a hardware realization of an adaptive filter which has the requisite stability in conjunction with a reduction in the outlay on hardware.
According to the invention, an adaptive filter is realized by modification of the LMS algorithm. This saves a large part of the multipliers in such a way that the coefficient adaptation is suppressed and a coefficient register is preferably divided into two sub-areas, in order to reduce the bit width of the filter multipliers.
An adaptive filter is described mathematically by:
y
⁡
(
n
)
=
∑
i
=
0
N
-
1
⁢
⁢
bi
⁡
(
n
)
*
x
⁡
(
n
-
i
)
.
When the adaptive filter according to the invention is used for lower frequency components, it is preferable to take only every second sample, according to:
y
⁡
(
n
)
=
∑
i
=
0
N
-
1
⁢
⁢
b
i
⁡
(
n
)
*
x
⁡
(
n
-
2
*
i
)
where n=cycle index, x(n) and y(n) are the input and output samples, and
b
i
(n),i=0,1, . . . N−1 are the filter coefficients of the cycle n.
The LMS algorithm for the adaptation of the coefficients is calculated according to:
b
i
(
n
)=
b
i
(
n
−1)+&mgr;*
e
(
n
−1)*
x
(
n−i
−1),
i
=0,1
, . . . , N
−1
where
e
(
n
):=
d
(
n
)−
y
(
n
)
where d(n) is the so-called desired output and m is the adaptation constant. It is evident that an LMS-adaptive filter requires two multipliers, one for the filtering and one for the coefficient adaptation, for each coefficient digit position, called tap below.
The adaptation &mgr;*e(n−1)*x(n−i−1) should be small enough to guarantee the stability of the adaptation procedure, that is to say to obtain a sufficient accuracy of the coefficients b
i
(n),i=0,1 . . . N−1.
The inventive modification of LMS algorithm reads as follows:
b
i
(
n
)=
b
i
(
n
−1)+
e
(
n
−1)*
x
(
n−i
−1)*2
−(k−12)
, i
=0,1,2, . . . ,14,
where
e
(
n
):=SIGN(
d
(
n
)−
y
(
n
)),
and
SIGN
⁡
(
ξ
)
:=
{
-
1
,
ξ
<
0
0
ξ
=
0
1
ξ
>
0
and k=0,1,2,3 is the user option, which can be designated as the adaptation constant.
For each tap, only one multiplier for the filtering is used. The adaptation requires a register with a sufficient length of e.g. 18 bits in order to achieve the requisite accuracy for the stability of the adapted LMS algorithm.
In order further to reduce the outlay on hardware, only a number of MSBs, the coefficient bits, preferably 8 bits of the register, are taken as filter coefficients and used for the multiplication.
In a further refinement of the invention, the 8 bits of the register are fed to an evaluation circuit which, depending on the value of the 8 bits, performs windowing in order to achieve a further reduction to e.g. 5 bits. The evaluation circuit preferably eliminates leading equivalent bits by a shift function and clips a number of LSBs. This reduced value is used for the further calculation. The result of the evaluation circuit, preferably a 2-bit value, is used in a further, downstream shift function in order to recover the correct value.
The effect advantageously achieved by the inventive adaptation of the LMS algorithm is that only one multiplier is required for each tap register. It is advantageous that, by virtue of the separate utilization of the tap registers for the adaptation and the filter multiplications, only a small bit width is required for the multipliers, without the accuracy and the requisite stability for the adaptation process being impaired. The use of the window moving technique according to the invention achieves a further reduction in the necessary bit width for the multipliers. As a result, it is no longer necessary to take account of the dynamic range of the coefficient values when selecting the multiplier bit width.
REFERENCES:
patent: 4649335 (1987-03-01), Lassaux et al.
patent: 5894495 (1999-04-01), Kase
patent: 6519342 (2003-02-01), Opitz
patent: 0146175 (1985-06-01), None
patent: 0543568 (1993-05-01), None
patent: 0813301 (1997-12-01), None
S. Maginot et al, “A General Purpose High Speed Equalizer”, Proceedings of the Custom Integrated Circuits Conference, Boston May 13-16, 1990, No. CONF. 12,pp. 2561-2564.
J.B. Evans et al, “A CMOS Implementation of a Variable Step Size Digital Adaptive Filter”, Spectral Estimation, VLSI, Underwater Signal Processing, Glasgow, May 23-26, 1989, vol. 4, No. CONF. 14, Institute of Electrical and Electronics Engineers, pp. 2489-2492.
H.S. PUnjabi et al, “A Modified Mu-Weighted Normalized Frequency-Domain LMS Algorithm” Proceedings of the Global Telecommunications Conferencd San. Francisco, Nov. 28-Dec. 2, 1994, vol. 1, Institute of Electrical and Electronics Engineesisbn: 0-7803-1821-8, pp. 232-236.
Nicol, Chris J., et al. “A Low-Power 128-Tape Digital Adaptive Equalizer for Broadband Modems” in IEEE Journal of Solid-State Circuits, vol. 32, No. 11, Nov. 1997, S. 1777-1789.
Report from German Patent Office.
Erbar Maximilian
Lin Jinan
Kurdyla Ronald H.
Laks Joseph J.
Malzahn David H.
Thomson Licensing S.A.
Tripoli Joseph S.
LandOfFree
Adaptive 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 Adaptive filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive filter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3361572