VLSI Signal Processing Term Report
Echo Cancellation
Using Adaptive Interpolated FIR Filter
R89921151
郭仁智
I. Introduction
Echo is an undesired signal impedance mismatch in the system. A hybrid circuit with a 10~20 dB echo return loss might be enough for voice conversation. But in modern high-speed communication system, the received signals are usually attenuated by more than 40 dB. Therefore, additional echo cancellers with 60 dB or better echo return loss enhancement (ERLE) performance requirement is usually required. Adaptive filters usually serve as this role.
Finite impulse response (FIR) digital filters are known to have some very desirable properties over infinite impulse response (IIR) filter, such as guaranteed stability, absence of limit cycles, and linear phase if desired. However the large number of arithmetic operations, especially the multiplications, is a major drawback in the practical implementation. The number of multipliers needed in the direct form implementation is the same as the length of the impulse response. Neuvo et al. [1] proposed a novel FIR filter design called interpolated FIR (IFIR) filter. By reducing the redundancy in FIR filter coefficients, the IFIR filter can save significant savings in the number of arithmetic operations. The basic idea is to implement the filter as a cascade of two FIR sections, where one section generate the sparse set of impulse response values with every Lth sample being nonzero and the other one performs the interpolation.
In some systems, the echo has a very long impulse response. In these applications, the traditional adaptive FIR (AFIR) structure may have a large number of taps. Thus, adaptive IFIR (AIFIR) filter may represent an interesting alternative to AFIR filters. Additional AIFIR filters retain most of the desirable features of the traditional AFIR filters.
In this report, we will review some basic concept of IFIR. The adaptive IFIR (AIFIR) and some related adaptive algorithm would also be discussed. The rest of this report is organized as followed. In section II, we’d like to see how IFIR works. In section III, the adaptive IFIR will be discussed. In section IV, a brief hardware complexity of AIFIR is shown. In section V, we will show some simulation result. Some conclusions are given in final section.
II. Interpolated FIR filters
(a) Basic IFIR Structure
FIR filters are generally composed of several nonzero taps. Now, we might use an alternative way. That is, we can use a sparse filter that has nonzero taps only at every Lth sample and a cascade filter, which perform interpolation. The block diagram is shown in Fig. 1.
Fig.1 Block diagram of an interpolated FIR filter
Let’s consider a digital filter HM(z) with impulse response hM(n). We call it the model filter, as it will determine the frequency behavior of the final interpolated impulse response filter. Then we insert L-1 zero-valued samples between the original samples of hM(n), we obtain the sequence h’M(n)
The z transform H’M(z) of (1) is H’M(z) = HM(zL). Thus the implementation of H’M(z) is simply obtained form the implementation of HM(z) by replacing each delay with L delays. To generate the interpolated impulse response, we can cascade HM(zL) with an interpolator G(z). The overall frequency response Hi(z) is thus Hi(z) = HM(zL) G(z).
The design of G(z) is most conveniently performed in the frequency domain. Hi(ejω) is periodic with a period 2π/L. Any passband in the interval [0, π] can be selected to be the desired on. The purpose of the interpolator is thus to attenuate the unwanted replicas of the desired passband. Note that the passband and transition bandwidth are now 1/Lth of the corresponding widths of the model filter.
The largest value of L, Lmax, that we can use depends on the specifications of the IFIR filter. If the stopband edge frequency of the low-pass IFIR filter is denoted by ωSL, the maximum value for L is Lmax = [ π / ωSL ] , where [] denote truncation. This ensure that the model filter stopband edge is less than π. For high-pass filters we replace ωSL by π-ωSH. In bandpass filter, we can replace ωSL by (ωS1 -ωS2)/2, where ωS1 and ωS2 are the desired stopband edge frequencies.
The design of the interpolator G(z) can be formulated as the design of a multi-stopband FIR filter having passband matching the wanted passband of HM(zL) and stopbands overlapping the unwanted replicas of the passband. We might see that the choice of L will affect the complexity of HM(zL) and G(z). Thus there have been many design approach proposed trying to find out the optimal solution.
We can summarize the design steps of IFIR as follows.
(1)From given filter stopband edge frequencies, choose a proper L.
(2)Design Interpolator G(z) to attenuate unwanted replicas.
(3)Design model filter HM(z)
(4)Cascade HM(zL) with G(z) and we have the desired response.
The above procedure is for narrowband low-pass, bandpass and high-pass filters. To design wideband low-pass filters and bandstop filters, some additional steps must be done.
(b) IFIR Properties
Let’s discuss the advantages of IFIR from these two aspects
(1) Computational Savings
If the length of an FIR filter required to meet given specifications is approximately . Where δ1 and δ2 are the passband and stopband ripples, and ΔF is the relative transition bandwidth ΔF = (ωS1 -ωS2)/2π. Thus, the IFIR filter requires approximately 1/Lth of the multipliers and adders of an equivalent conventional FIR filter. At the point, we neglect the interpolator section. If L=2J, J=1,2,3,… and NM is the length of the model filter, we can compare the computational complexity from the below list.
Multiplier / AdderFIR / [ ( L * NM – L + 1) / 2 ] / L * NM – L
IFIR / [ ( NM + 1 ) / 2 ] + J / NM – L + 2*J
The main goal of this design is to reduce the computational complexity. And from the list, we can see that it does comply with what it claims.
(2) Finite wordlength properties
Besides the hardware savings, the IFIR have an additional advantage over conventional FIR filters. That is, coefficient sensitivities and output roundoff noise properties. An upper bound for the standard deviation of the error in the frequency response due to coefficient quantization is given by
In the implementation of the IFIR filter, we can assume that the interpolator does not increase the coefficient sensitivity. This is reasonable assumption as in the neighborhood of the passband, where the gain of the interpolator is approximately on, the distances to the zeros of the interpolator are large. Closer to the zeros of the interpolator the required stopband attenuation is exceeded so much that the coefficient sensitivity is no long a problem. On the unwanted replicas of the passband, the attenuation caused by the interpolator is easy to check using quantized interpolator coefficients. Based on these arguments, it is sufficient to analyze only the effect of quantizing the coefficient of HM(zL). It is easy to see that the coefficient sensitivities of HM(zL) will have the same upper bound for the standard deviation as the model filter HM(z) has.
If we compare the standard deviation of the coefficient quantization error of a conventional filter of length LN with that of an IFIR filter derived from a model filter of length N. By using (3) , they are related as σFIR ≈ LσIFIR, for large N. The output round off noise variance at the output of a conventional filter of length LN is approximately , if N is large. In IFIR case, , where g(i) are the impulse response coefficients of the interpolator and C comes form the noise generated in the interpolator section. For large N and assuming that the noise gain of the interpolator is one we get υFIR ≈ LυIFIR.
III. Adaptive IFIR filters
The available AIFIR analyses have extended the classical FIR-LMS assumption to the interpolated case. In this way, two important facts are not regarded. First, in an AIFIR filter, just N/L weights of the possible N of a corresponding AFIR are adapted, i.e., the weight space is constrained. The classical analysis does not take into account this question in the model derivation. The second point concerns about the use of the well-known independence theory, used to simplify the analysis of LMS-type filters. However, due to the presence of the interpolator block, which creates input signal correlations, the IT can no longer be adopted in this case.
Fig.2 Adaptive IFIR filter for system identification
Fig. 2 shows the classical scheme of adaptive transversal filtering, in which an AIFIR filter composed of the cascade of an interpolator and an adaptive sparse filter is used. The fact that the commutation between the sparse filter and the interpolator does not influence in the result of the optimization process makes this possible.
W(n)=[w0(n),…, wN-1(n-N+1)]T is the sparse weight vector; the impulse response of the interpolator, I, is represented by an M-coefficients FIR filter [i0,…, iN-1]T. d(n), y(n) and e(n) are the desired, sparse filter output, and error signals, respectively. X(n)=[x(n),…,x(n-N+1)]T and Xf(n)=[xf (n),…,xf (n-N+1)]T are the system input and filtered input signal vectors, respectively.
By now, we first review the original LMS algorithm. The Wiener solution of unconstrained weight vector is Wopt = R-1P. Where R is the autocorrelation matrix of the tap inputs and P is the cross-correlation vector between the tap inputs and the desired response. And the recursive relation for updating the tap weight vector is
.
From now, we will discuss the analytical models for the AIFIR-LMS filters, which take into account the particular topology of this structure and consider the input signal correlations. The idea is to use constrained LMS algorithm (CLMS). The mathematical representation is shown below.
The block diagram to determine the optimum-constrained weight vector for the filter weight is given in Fig. 3. The linear constraints on the weight vector, taking into account the adaptive sparse filter topology, i.e., how many weights are settled to zero between nonzero weights are expressed by CTW=f.
Where C is the constraint matrix and f is the response vector. Then by using the method of Lagrange multiplier, the cost function is stated as minimizing E[e2(n)], subject to CTW=f.
Where e(n) is the instantaneous error, W is the sparse weight vector. Lz is the number of zero weights in the sparse weight vector, the dimension of C is N x L, consequently the dimension of f is L X 1.
Fig. 3 : Block diagram to determine the optimum-constrained weight vector
The instantaneous error is given by e(n)=d(n)-y(n)=d(n)-XLT (n)W.
and adding the Lz dimensional vector of Lagrange multipliers, λ, we can obtain the cost function
Minimize the cost function, it is easy to obtain the optimum constrained weight vector, given by
It is important to point out that the expected value of the input signal autocorrelation matrix, Rll and the cross correlation vector between the input signal and the desired signal, Pl, are computed without invoking IT.
Now let’s see the weight update equation using the constrained filtered-LMS algorithm. The error signal is expressed by
And the weight update equation is expressed as follows.
Next, let’s consider the mean weight behavior.
Here we make an assumption that the correlation between input signal vectors is more important than the correlation between weight vector and input signal vectors.
Then we define the weight-error vector as V(n) = W(n) – Wopt. And the recursive expression for the weight-error vector is given by
and
IV. Echo Canceller Based on Adaptive IFIR filter
The goal of our design is to reduce the computational complexity. In this section, we should compare the cost of AFIR and AIFIR. Because considering only the number of multipliers can be highly misleading, we would measure the complexity both with the number of multipliers and the number of bits/multiplier. Let r be the number of bits/coefficient and x the number of bits/input.
Where NF and NG are the number of taps of sparse filter and interpolator, respectively. NF = [ N / L ]. If we want to achieve the cost-efficient design, the following inequality should be considered.
Let’s consider a case that s = 3 bits and r = 16 bits. Than choosing L ≥4 would meet our requirement.
V. Simulation
(a)Realize a 128 taps low-pass FIR filter with stopband edge normalized frequency 0.01. with different value of L.
(i) L=2
Reference filter with length 128
Model filter of length 64
Design IFIR filter with nonzero taps = 67
(ii) L=4
Reference filter with length 128
Model filter of length 32
Design IFIR filter with nonzero taps = 38
(iii) L=8
Reference filter with length 128
Model filter of length 16
Design IFIR filter with nonzero taps = 25
(b) Next, we will repeat an example in the paper. The impulse response of the plant is [1 0.8 0.6 0.1 –0.2]. The impulse response of the interpolator is [0.5 1 0.5]. The input signal is white with variance 1. The upper step size μmax = 0.1, which is experimental determined. The interpolator factor is L = 2. The Wiener solution is Wopt = [1.0608 , 0 , 0.0353 , 0 , -0.0725]. However, we will use standard LMS algorithm to estimate the error between the constrained-filtered LMS algorithm.
As we can see, even if we use standard LMS, the weight vector will still approach the optimal solution but more iteration are needed.
The weight error vectors are accordingly approaching zeros.
The aim of this simulation is to estimate the error between these two algorithms and then we might make tradeoff. When the performance counts, we could use more hardware to achieve. In the other hand, when hardware cost is first consideration, the standard LMS still provide an acceptable solution.
VI. Conclusion
Several other methods that utilize the redundancy of the tap coefficients to achieve computationally effective FIR realization have been proposed. However the design of IFIR filter is rather simple and regular.
In the other hand, the HM(z) and G(z) are needed to be tuned simultaneously for best performance. There are several algorithms proposed to solve these questions. But we should notice that the filter designs are different case by case. Although there are so-called optimal designs, it’s hard to find a general one that suit for all circumstances. It should depend on where they are used to and the way we implement them.
The particular structure of the AIFIR filter leads to the usual analysis can no longer adequate in every case. The filtered version of the CLMS algorithm is therefore another solution for this kind of problem.
Adaptive IFIR filters may also represent an interesting alternative for substituting classical adaptive FIR filters. In applications such as noise and echo cancellation, channel equalization, and so on, that require a large number of filter coefficients, it exhibits better convergence rate and a smaller computational complexity for both filtering and coefficient updating operations.
According to the channel and modulation themes, echo is different in many systems. Therefore, if we want to design a general purpose echo canceller using AFIR to fit any system, the performance will surely deteriorate, as we can see in [7].
Reference:
[1] Y. Neuvo, C. Y. Dong, and S. K. Mitra, “Interpolated finite impulse response filters”, IEEE Trans. on Acoust., Speech and Signal Processing; vol. ASSP-32; pp563~570, June 1984.
[2] T. Saramaki, Y Neuvo, S.K. Mitra, “Design of Computationally Efficient Interpolated FIR Filters”, IEEE Trans. Circuits and system, vol 35, No 1, Jan 1988.
[3] J Webb, D.C Munson, Jr, “A New Approach to Designing Computationally Efficient Interpolated FIR Filters”, IEEE Trans on Signal Processing, Vol 44, No 8, Aug 1996.
[4] L.S. Resende, C.A.F Rocha and M.G. Bellanger, “ A Linearly-Constrained Approach to the Interpolated FIR Filtering Problem”, ICASSP 2000, vol 1, pp392~295, 2000.
[5] O.J. Tobias, R. Seara, “Analytical Model for the Mean Weight Behavior of Adaptive Interpolated-FIR Filters Using the Constrained Filtered LMS Algorithm”, AS-SPCC 2000, pp272~277, 2000.
[6] A. Abousaada, T. Aboulnasr, W. Steenaart, “An Echo Tail Canceller Based on Adaptive Interpolated FIR Filtering”, IEEE Trans on Circuit and system II, Vol 39, No 7, July 1992.
[7] S.S Lin, W.R Wu, “A Low Complexity Adaptive Interpolated FIR Echo Canceller”, ISCAS 2001, Vol 4, pp.438~441.