Source: https://patents.google.com/patent/WO2002017488A1/en
Timestamp: 2019-08-22 10:17:36
Document Index: 723520666

Matched Legal Cases: ['art 10', 'art 12', 'art 12', 'art 10', 'art 10', 'art 12', 'art 10', 'art 12', 'art 10', 'art 12', 'art 10']

WO2002017488A1 - Partitioned block frequency domain adaptive filter - Google Patents
Partitioned block frequency domain adaptive filter Download PDF
WO2002017488A1
WO2002017488A1 PCT/EP2001/009625 EP0109625W WO0217488A1 WO 2002017488 A1 WO2002017488 A1 WO 2002017488A1 EP 0109625 W EP0109625 W EP 0109625W WO 0217488 A1 WO0217488 A1 WO 0217488A1
PCT/EP2001/009625
Gerardus P. M. Egelmeers
Rene M. M. Derkx
2000-08-21 Priority to EP00202917 priority Critical
2000-08-21 Priority to EP00202917.1 priority
2002-02-28 Publication of WO2002017488A1 publication Critical patent/WO2002017488A1/en
The partitioned block frequency domain adaptive filter according to the invention comprises a plurality of parallel arranged filter partitions. Each filter partition models a part of an impulse response of the adaptive filter and has update means for updating filter coefficients of that filter partition by means of a circular convolution. The update means intermittently constrain these filter coefficients by eliminating circular wrap-around artifacts of the circular convolution. The update means are arranged for updating the filter coefficients in dependence on at least part of the circular wrap-around artifacts of adjacent update means, resulting in an improved convergence behavior of the adaptive filter.
Partitioned block frequency domain adaptive filter
A partitioned block frequency domain adaptive filter (PBFDAF) according to the preamble is known from the paper "Multidelay block frequency domain adaptive filter", IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 38, no. 2, pp. 373-376, by J.S. Soo and K.K. Pang. Adaptive filters can be very useful devices in several applications of digital signal processing. Examples of such applications are: channel equalization, array signal processing and noise and echo cancellation. Here, the Acoustic Echo Canceller (AEC) is merely used as a means for demonstrating the invention, and it is noted that the invention is not restricted to this specific application. Acoustic Echo Cancellers are used, for example, in teleconferencing systems or in speech recognition systems. The structure of an AEC is depicted in Figure 1 and will be explained as part of a teleconferencing system.
In a teleconferencing system with two speakers in two different rooms, an AEC is implemented twice. The speech signal from the far-end speaker x[k] is generated in the near-end room by the loudspeaker 14. The transmission between the loudspeaker 14 and the microphone 16 can be modeled by a room impulse response. The echo signal e[k], picked up by the microphone 16, can be seen as a convolution of the signal x[k] with this room impulse response. In the case that both parties are speaking (i.e. double-talk), the microphone 16 also picks up a near-end speech signal s[k]. If there was no adaptive filter present, the signal e[k] -β <?[£] + [&] would be directly passed on to the far-end speaker. Besides the wanted near-end speech signal, the far-end speaker also hears echoes of his own speech signal. For the overall teleconferencing system, this results in a non-optimal communication between the two speakers.
The adaptive filter, which is formed by the update means or correlation means
10 and the convolution means 12, reduces these unwanted echoes by modeling the real room impulse response with a Finite Impulse Response (FIR) filter. The filter-coefficients or filter- weights w[k] of this FIR filter are updated in the update means 10 by correlating the residual signal r[k] with the input signal x[k]. By convoluting or convolving the input signal x[k] with the filter-coefficients w[k] in the convolution means 12, the adaptive filter estimates the unknown acoustic echo signal e[k], indicated by e[k]. This estimate of the echo is subtracted from the real echo by means of a subtractor 18. As a result, the echo level is reduced, leading to improved communication between the speakers.
An elementwise multiplication of two frequency-domain vectors corresponds to a convolution in the time-domain. If both vectors are transformed with the Fast Fourier Transform this convolution is a circular convolution. In adaptive filtering linear convolutions in stead of circular convolutions are needed to convolve an infinite length input data stream with a finite length vector. By means of the so-called Overlap-Save (OLS) method a linear convolution can be performed using FFT/IFFTs. It is noted that the Overlap-Add (OLA) method can also be used for efficiently convolving an infinite length vector with a finite length vector. However, adaptive filters using the OLS are usually less computational complex than adaptive filters that use the OLA method. An adaptive filter comprises a linear correlation part 10 and a linear convolution part 12. The convolution part 12 is needed for filtering an input signal with the filter- weights, while the correlation part 10 calculates a gradient estimation needed to update these adaptive filter-weights. After convergence the adaptive weights have adjusted to the optimum solution and represent the room impulse response. The correlation part 10 and the convolution part 12 may both be implemented by means of the Overlap-Save method. The correlation part 10 is similar to the convolution part 12 in that in both parts a linear convolution is calculated. The correlation part 10 differs from the convolution part 12 in that in the correlation part 10 one input block has to be mirrored in time. This mirroring in time can be performed in frequency domain by means of a complex conjugate operator 32 as shown in Figure 2.
Figure 2 shows a block diagram of a PBFDAF. Samples of the input signal x[k] are collected into blocks with 50% overlap by means of the serial to parallel converter 20 and the 50% overlap block 22. These blocks of input samples are then converted into the frequency domain by a FFT 26. In block 42 N zeros are appended on the left of a block of N samples of the residual signal or control signal r[k]. The resulting block of 2N time domain values is thereafter converted into the frequency domain by another FFT 26. Next, the power of this frequency domain signal is normalized by means of an elementwise multiplication with a normalization factor in an elementwise multiplier 40.
Each partition comprises a complex conjugate operator 32, an update block 34 and an elementwise multiplier 36. Additionally, all partitions with the exception of the leftmost partition, comprise a block delay element 30. The update means or correlation means 10 comprise the complex conjugate operator 32 and the update block 34. The convolution means 12 comprise the elementwise multiplier 36. The output of the complex conjugate operator 32 is the signal representative of the input signal. The output of the elementwise multiplier 36 is the signal representative of the control signal. The update block 34 updates and outputs the filter coefficients on the basis of the signal representative of the input signal and the signal representative of the control signal. Next, the updated filter coefficients are convoluted with blocks of samples of the input signal by means of the elementwise multiplier 36. The outputs of the elementwise multipliers 36 of all the partitions, i.e. the results of all the partial convolutions, are added together in an adder 38 in order to form the overall convolution result. This overall convolution result is then transformed into the time domain by means of an IFFT 28. Finally, the left-most N samples of the block of 2N time domain samples of the overall convolution result are discarded in order to form the estimated echo signal e[k]. This estimated echo signal is subtracted from the signal picked up at the near end by means of subtractor 18. The result of this subtraction is the residual signal r[k]. Figure 3 shows a block diagram of an embodiment of the update block 34. In this embodiment the adaptive weights are stored in time-domain. Note that the index i indicates the partition number. Furthermore, the following variable W, is defined as:
The signal representative of the input signal and the signal representative of the control signal are elementwise multiplied with each other by elementwise multiplier 50. This elementwise multiplication in frequency domain constitutes a circular convolution in time domain. The result of this convolution comprises circular wrap-around artifacts which are removed by means of a rectangular time domain constraint window which is formed by IFFT 52, element disposal window 54, zero appender 60 and FFT 62. First, the convolution result is transformed into the time-domain by the IFFT 52. Next, the window 54 discards N points of the convolution result. This is needed to remove the circular wrap-around artifacts from the Overlap-Save method. The remaining N samples are used to update the adaptive weights with the adder 56 and the delay element 58. After this update, N zeros are augmented. This is needed for the efficient convolution of the adaptive weights with the input signal, by means of the Overlap-Save method. Finally, the result is transformed back to frequency-domain. The two mirroring operators JN can be eliminated by storing the vector
in time-reverse order. Furthermore, the two time-domain windows, the FFT and the IFFT, can be combined in a time-domain gradient constraint operator. As a consequence of the gradient constraint operator or constraint operator, the adaptive coefficients need to be stored and up-dated in frequency domain instead of time-domain. These frequency-domain coefficients will be denoted by W . The separation of the constraint operator and the adaptive coefficients can be illustrated by the following deduction:
as WJNlκN] + ^G2NiilN ' -iZ^N[κNl (3.2)
is the rectangular constraint window vector, containing ones in the first N elements and zeros in the last N elements. Here, this constraint window is referred to as the rectangular constraint window. The constraint means comprise this rectangular constraint window. Figure 4 shows the frequency-domain coefficient update together with the rectangular constraint window.
Mostly, the rectangular constraint is placed before the update, but it is advisable to place this constraint after the update as is shown in Figure 5. Calculating the rectangular constraint with infinite precision gives results, which are the same for both situations (Figures 4 and 5). However when calculating the weight update in Figure 4 with finite precision (e.g. fixed-point arithmetic), numerical round-off errors are accumulated in the weight update. Eventually, after many iterations of the weight update, this leads to large errors in the last N points of the coefficients. Correction of these accumulated errors is prevented by the right half part of the constraint. When placing the constraint after the weight update as depicted in Figure 5, the result after calculating the constraint also contains numerical round-off errors in cases of finite precision. However, as the constraint operation is performed on the actual coefficients, there is no accumulation of these errors, which could lead to long-term problems. Hence, rectangular constraint operations are preferably placed after the weight update. Figure 6 shows a block diagram of an embodiment of the update block 34 which illustrates the operation of the PBFDAF which is disclosed in the above mentioned paper. The use of the rectangular constraint window 82 is computationally relatively complex. Constraining the coefficient vector of a particular partition only once in a while can lower this complexity. For this purpose the update block 34 comprises two switches 80 and 84. The operation of these switches 80 and 84 may be described by the following function:
H- i e mod KP zs i rfm*. ' <3 β)
In this formula the parameter K indicates the number of partitions and the parameter P is the alternative constraining period in number of block iterations of the algorithm. The rectangular constraint window is calculated only when the switches 80 and 84 are both in the 1 -position. When the switches 80 and 84 are both in the 0-position the convolution results are not constrained at all.
It is an object of the invention to provide a PBFDAF with an improved convergence behavior. This object is achieved in the PBFDAF according to the invention, which is characterized in that the update means are arranged for updating the filter coefficients in dependence on at least part of the circular wrap-around artifacts of adjacent update means. Experiments have shown that the PBFDAF as described in the above mentioned paper exhibits jumps in the convergence curve at the moments when the rectangular constraint 82 is applied: at these moments the NMSE is suddenly worse than before. Since the degradation in the NMSE occurs exactly after the moment that the rectangular constraint is applied, the removal of the circular-errors are responsible for this phenomenon. Apparently the accumulated circular-errors in the adaptive weights somehow contribute to the model of the room impulse response, and removing these circular-errors by means of rectangular constraining results in a temporarily degradation of the NMSE in the next block-iteration. The invention is based upon the recognition that at least part of the accumulated circular wrap-around artifacts in a partition I comprise useful convolution results that can be used by the update means of adjacent partitions i-l and i+1 for updating the filter coefficients. In this way, the calculated filter coefficients are more accurate and the filter has an improved convergence behavior, i.e. it more swiftly converges to a steady state. An embodiment of the PBFDAF according to the invention is characterized in that the update means are arranged for updating the filter coefficients in dependence on the at least part of the circular wrap-around artifacts only when the filter coefficients are constrained.
By this measure the act of updating the filter coefficients in dependence on the at least part of the circular wrap-around artifacts is only performed when it is useful, i.e. at the moments that there are jumps in the convergence curve, i.e. at the moments that the constraint means performs a constraint of the filter coefficients.
An embodiment of the PBFDAF according to the invention is characterized in that the update means comprise selection means for selecting the at least part of the circular wrap-around artifacts. The selection means enable the selection of the useful convolution results for use by adj acent update means .
An embodiment of the PBFDAF according to the invention is characterized in that the selection means are arranged for selecting those circular wrap-around artifacts which are substantially equal to at least part of the result of a linear convolution of the signal representative of the input signal and the signal representative of the control signal. By this measure the useful convolution results, i.e. those results which are substantially equal to results of the linear convolution of the signal representative of the input signal and the signal representative of the control signal, are selected and can be used by adjacent update means for updating the filter coefficients.
An embodiment of the PBFDAF according to the invention is characterized in that the selection means comprise an approximation of a rectangular constraint window. The approximation of the rectangular constraint window, e.g. a sinusoid constraint window, allows to select a large part of the circular wrap-around artifacts in a computationally efficient way.
An embodiment of the PBFDAF according to the invention is characterized in that the selection means further comprise a raised cosine window and/or a raised inverse cosine window for selecting the at least part of the circular wrap-around artifacts. The raised cosine window and the raised inverse cosine window are computationally efficient replacements for rectangular windows and may be used as part of the selection means for selecting circular wrap-around artifacts. An embodiment of the PBFDAF according to the invention is characterized in that time domain values of the approximation are larger than or equal to zero and in that the approximation in time domain has substantially high slopes near the positions which correspond to the positions of the transitions in a rectangular constraint window. Negative values in the time-domain window need to be avoided in order to avoid divergence of the adaptive weights. The reason for the divergence in the case of negative values in the constraint window can be explained in an intuitive way. Because of the negative values, the correlation part produces results that are negatively correlated with the residual signal. Hence the adaptive weights are updated in the wrong direction. As the adaptive weights become less accurate, there is more negative correlation and worsening of the weights in every next block-iteration.
By means of the high slopes near the positions of the transitions, a relatively large amount of the circular results that converge to a non-zero value is eliminated by the selection means. For example, when using a 50% overlap, the high slopes should be positioned at 0 and N, with N being the block size of the filter and 2N being the FFT size. When using a 75% overlap, the high slopes should be positioned at 0 and 3N, with N being the block size of the filter and 4N being the FFT size.
An embodiment of the PBFDAF according to the invention is characterized in that frequency domain values of the approximation each comprise a real value and mutually conjugate imaginary values, whereby at least part of the imaginary values form a row of numbers, the numbers being obtainable from one another by multiplication. By this measure, at least part of the frequency domain values of the approximation can easily be calculated, i.e. merely by multiplying other frequency domain values with a multiplication factor, resulting in a PBFDAF with a relatively low computational complexity. An embodiment of the PBFDAF according to the invention is characterized in that the frequency domain values of the approximation are defined as:
with i being an index number, m being a multiplication factor, a being a mean value. Because of the relation between two subsequent frequency components in this constraint- window, the frequency domain circular-convolution of this window with a complex valued Hermitian signal can be calculated in a very efficient way.
The above object and features of the present invention will be more apparent from the following description of the preferred embodiments with reference to the drawings, wherein: Figure 1 shows a block diagram of an embodiment of the acoustic echo canceller,
Figure 2 shows a block diagram of an embodiment of a PBFDAF comprising an update block 34, Figures 3 to 7 show block diagrams of embodiments of the update block 34,
Figures 8 to 13 show diagrams by means of which the compensation of circular wrap-around artifacts in the PBFDAF according to the invention is illustrated,
Figure 14 shows a block diagram of an embodiment of a generator means for generating forward and backward compensation signals, Figure 15 shows some signal diagrams by means of which the operation of the generator means as shown in Figure 14 is explained,
Figure 16 shows a block diagram of another embodiment of a generator means for generating forward and backward compensation signals,
Figure 17 shows some signal diagrams by means of which the operation of the generator means as shown in Figure 16 is explained,
Figures 18 and 19 show some signal graphs illustrating the operation of the generator means,
Figure 20 shows a block diagram of an embodiment of a PBFDAF according to the invention, Figure 21 shows a block diagram of an embodiment of the update block 34 for use in the PBFDAF of Figure 20,
Figure 22 shows a block diagram of a further embodiment of a generator means for generating forward and backward compensation signals,
Figure 23 shows a block diagram of an embodiment of a generator means for generating a backward compensation signal.
In the Figures and in this description uppercase symbols are used to denote frequency-domain variables and lowercase symbols for time-domain variables. A boldface font is used to denote matrices, while vectors are denoted by underlining fonts. Furthermore the superscripts t , * and h are used to denote the transpose, complex conjugate and the complex conjugate transpose (Hermitian) respectively. ON and IN represent a zero and identity matrix, the superscript indicating the dimension of the matrix. Generally, superscripts indicate the dimension and subscripts indicate the element number of the vector or matrix. As most of the vectors and matrices used here have dimension 2N x 1 and 2N x 2N, a vector or matrix with omitted superscript indicates a vector of length 2N or a matrix with dimension 2N x 2N. The indices between square brackets (e.g. x[k]), indicate a time-index, diag {.} denotes the operator that transforms a 2N x 1 vector into a 2N x 2N matrix containing the vector coordinates as diagonal elements while other elements are zero. The mathematical expectation is denoted by ε{>\.
which the zero matrices O have appropriate dimensions. Note that nlN — t-t-V
The data of an 2N dimensional vector can be mirrored with the 2N x 2N mirrored matrix J2N that is defined as:
A reverse circular shift over L positions, in opposite direction to
is carried out by the matrix
•>F = ( Jo . )• -3)
The Normalized Mean Square Error (NMSE), in dB, is a performance measure of adaptive filters and is defined as follows: NMSE[A] ∞ 10- log ≡≥-jj , ( 1.7)
∑ .[*3)2
where N is the length of the block that contains the residual samples for which we calculate the NMSE[k]. The steady-state NMSE is the value of the NMSE after convergence of the adaptive filter, and is a measure of the residual echo. The lower the steady-state NMSE, the better the performance of the adaptive filter. The CTC, which is another performance measure of adaptive filters, is defined as the slope of the NMSE curve, during the transient of the algorithm. It assumes that the initial part of the learning curve is linear. The CTC is defined in dB/ms.
O(N logN) operations, where 2N is the length of the FFT/IFFT. This constraint can also be performed by calculating a circular convolution directly in frequency-domain. The straightforward calculation of the circular convolution requires
O(N2) operations. The frequency-domain coefficients
( 2jV)f
When using a first order approximation, only use the real coefficient and the first two mutually complex conjugates are used. This results in a sinusoid constraint window that can be computed in frequency-domain with much less computational complexity than by means of an FFT/IFFT. Off course, also other low-order approximations of the rectangular constraint window could be used Constraint windows with other than 50% overlap (half overlap) contain frequency components that have both real and complex values. Hence such a calculation needs additional computational complexity compared with the 50% overlap windows. As mentioned before, in most practical cases half overlap constraint windows are used. The rectangular constraints need to be placed after the update. This is however different for the constraint approximations. If the approximations were placed after the update, the time-domain adaptive weights would constantly be multiplied by the weights of the approximation window. As most of the weights in the approximation window are generally not equal to one, this would lead to adjustments of the weights in every block- iteration and the adaptive filter would not converge. Hence all constraint approximations are best applied before the update, e.g. before the adder 56.
Negative values in the time-domain window need to be avoided in order to avoid divergence of the adaptive weights. The reason for the divergence in the case of negative values in the constraint window can be explained in an intuitive way. Because of the negative values, the correlation part produces results that are negatively correlated with the residual signal. Hence the adaptive weights are updated in the wrong direction. As the adaptive weights become less accurate, there is more negative correlation and worsening of the weights in every next block-iteration. As the frequency-domain coefficients of equation 3.8 result in time-domain coefficients that can be negative, we need to scale the frequency coefficients. Using more frequency components in the constraint approximation, results in better performance, but enlarges the computational complexity. To achieve an optimal performance with low computational complexity, it is investigated which properties of the constraint are important. Therefore we perform an experiment with two constraint windows.
An efficient method for convolving a signal with an approximation of the rectangular constraint is by assuming that the odd frequency components in equation 3.8 are related with the neighbor odd components by a multiplicative factor. As this window also contains higher-order frequency components, the slope of this constraint approximation is very steep. Hence this window is called the high-slope constraint window. The high-slope constraint window G2N in frequency domain for 50% overlap partitions is defined as:
Because of the relation between two subsequent frequency components of this above defined constraint- window, the frequency domain circular-convolution of this window with a complex valued Hermitian signal can be calculated in a very efficient way.
Experiments have shown that good results can be obtained when the constraint- window g2N in time domain qualifies the following conditions:
1. (g^- ≥ O , v/,
2. High-slope on j =- 0 and / = Λr.
From the experiments it follows that a steep transition on i = 0 and i = N (i.e. high-slope) is of more importance than the nulling in the range N < i < 2N By choosing m = 2.166 and a = 0.57, the high-slope constraint window
just qualifies the first condition above, while maximizing the derivative of the slope in the middle, as proposed in condition 2. This optimal value of m is found experimentally. With the value a, the area between the zero level and the high-slope window can be adjusted. For a=0.57, the mean amplitude in the range 0 < i < N is normalized to 1. To derive an efficient algorithm for convolving the high-slope window with the complex- valued Hermitian input-signal, we start with the definition of the circular- convolution:
As the circular convolution is a linear operation, we can apply the superposition theorem and split up the circular convolution with G2N into three parts:
ΔIV .=(... odd v /
As there is a direct relation between formula 4.5 and formula 4.6, we only need to calculate one of these circular convolutions in the algorithm. This relation between the two formulas is expressed in the following lemma:
Lemma 4,2.1 // (σf . (σ }t:A,_fr «rf (x = QP*)^ ii. XiN Hermitian), then:
IS-*)*. can be expressed as a function of the actual convolution-element
a very efficient convolution algorithm can be derived. The iterative expression is formulated in the following lemma: 0 for 0 < i < IN, i even
Len-π-a 4.2.2 If C?f 2M-β • m - for 0 ≤ i < 2N, i odd
and T2N)k « (Λ?A')JjV_f (te. X2* Hemtttan), then:
2N \— ^' ^-i )k+2 m ' (--"V, • §• («. - ™-(Λ'-") ) ■ (*-»
On a similar way as the above derivation, we can derive an expression for calculating a convolution element
as a function of the convolution element
Note that the above two expressions are numerically stable iterations, because of the multiplication with the factor m"1. One can also derive an expression where in each iteration a multiplication with factor m is done; however, such an expression leads to less accurate results.
In order to calculate a convolution with the high-slope constraint in frequency- domain, we basically need to do the following sub-calculations:
1. Calculation of ^- X2j¥ ® a) (i.e scale operation),
2. Initial calculation of ^~ (X © G Λ')0 and ^ (-Y2,v © gjw)r
4. Calculation of fc- ( N ® G M)k out-of the calculations above
The convolution with the mean- value a can be calculated by scaling the input-signal X2N with the factor a. We note that when performing more than one circular convolution with the high- slope constraint window (as is the case in the PBFDAF algorithm), this convolution with the mean-value
can be performed at the cost of only 1 multiplication.
is needed for the first iteration of the iterative calculation of the circular convolution, one for the odd points and one for the even points. As the sum of the first few mutually complex conjugate frequency components of equation 3.8 is almost equivalent to the total sum of all mutually complex conjugate frequency components, there is no need to calculate w 1 (X2JV ® £ι Jo and
bas. ;d on all the coefficients of
2 Ϊ (4.10) N
need to be considered (i.e. Q = 1,3) in order to get accurate results.
|. (wt _ „.-( -.) in lemma 4.2.2 can be precalculated beforehand by the input-data X2N . As the multiplication with a can be performed elsewhere, as described in 4.2.2, the precalculation factor is
For large N, the pre-calculation is approximately m/2. m = 2.166 results in a pre-calculation of 1.083. We can approximate this value by 1.0, resulting in a reduced complexity of 2N multiplications, without violating the condition fe2'V G, Vi.
The complexity of the iteration-steps can be reduced even further, as a multiplication by two can be performed by a shift operation. When using a precalculation of
1.0 and m =2, the constraint- window slightly drops below zero, thus violating the condition
(gW)f > 0, forO i < 2N.
As negative values in the constraint should be avoided, it is not advisable to use m = 2.When we perform the iterative calculations with the pre-multiplication of 1.0, a single iteration in the convolution algorithm is done at the cost of two additions and one multiplication.
according to lemma 4.2.1, only the convolution with Gj need to be calculated. Also half of the output-points of
need to be calculated, as the frequency-domain vectors are Hermitian.
Figure 7 shows an embodiment of the update block 34 in which an approximation of a rectangular constraint window 92, e.g. the high slope constraint window, is employed in combination with the rectangular constraint window or constraint means 82. The selection means comprise in this embodiment the approximation of a rectangular constraint window 92. The switches 80 and 84 control the operation of the update block 34. When both switches 80 and 84 are in the 1 -position, the exact rectangular constraint window 82 is used to eliminate all the accumulated circular wrap-around artifacts. This exact rectangular constraint has a relatively high computational complexity and is performed only once in a while. When both switches 80 and 84 are in the 0-position, the approximation of the rectangular constraint window 92 is applied in order to eliminate a large part of the circular wrap-around artifacts in a computationally efficient way. In this way it is prevented that a too large accumulation of the circular wrap-around artifacts takes place, which would result in a relatively bad convergence behavior. Experiments have shown that the PBFDAF as described in the above mentioned paper exhibits jumps in the convergence curve at the moments when the rectangular constraint 82 is applied: at these moments the NMSE is suddenly worse than before. Since the degradation in the NMSE occurs exactly after the moment that the rectangular constraint is applied, the removal of the circular-errors are responsible for this phenomenon. Apparently the accumulated circular-errors in the adaptive weights somehow contribute to the model of the room impulse response, and removing these circular-errors by means of rectangular constraining results in a temporarily degradation of the NMSE in the next block-iteration.
We start with an analysis, where we demonstrate that it is useful to compensate some of the wrap-around artifacts. This analysis is done by means of graphical construction of the convolution part in the adaptive filter. After this analysis we show how the compensation signals can be constructed. We can eliminate the temporarily degradation in the convergence curve of the known PBFDAF by compensating the removed circular-errors in the other partitions after a rectangular constraint is applied. As a result, the output of the partitioned convolution is approximately the same as when the constraint was not applied. For explaining this method, we consider Figure 8, which shows the input-blocks in time-domain. After the circular
correlation of the residual signal with the input signal blocks is performed, the result contains the wanted linear correlation in the range [0..N-1], while the range [N..2N-1] is polluted with circular wrap-around artifacts. In the full-constrained PBFDAF all these wrap-around artifacts are eliminated. In this analysis we assume that the results near the correlation outputs N and 2N can be considered to approximate a linear correlation. In the PBFDAF without power normalization, this can be easily understood by correlating the residual signal in time-domain (augmented with N zeros) with the input signal blocks of Figure 8. For the correlation output points higher but close to N, the amount of wrap-around artifacts is low. This is also true for the points lower but close to 2N. For correlation output points in the direction of 3N/2 the approximation gets worse as the amount of wrap-around artifacts increase. Therefore we refer the correlation output points higher but close to N as being the left tail and the points lower but close to 2N as being the right tail. As the right tail approximates the linear correlation for negative time lags, it is better to change the principal interval as is depicted in Figure 9. As both tails are approximately results of a linear correlation, the coefficients of the tails in the adaptive weights
We explain the method of compensation graphically. In Figure 10 we see the two weight vectors of the adaptive filter. For the adaptive weight vector
In the previous section we discussed the weights in the adaptive filter as being constructed out of results related with linear correlations and the circular wrap-around artifacts. It is also explained that a part of these wrap-around artifacts (the two tails) are useful results. The compensation discussed in this section explains how these tails can be reused. As we have two useful tails we can use them for a backward and a forward compensation. Figures 11 and 12 are used for explaining the forward and backward compensation.
The circular convolution of χ ■ r[κN) with wfN[κN]
by mirroring one signal (e.g. the adaptive weights) and moving this signal to the right; this is indicated in Figure 11. The total sum of products of both signals in one convolution-iteration is the output-element of that specific iteration. As we perform a circular convolution, shifting the adaptive weights is actually a rotation of the 2N length vector. The convolution output can be described by the following formula: * (5.1)
In Figure 11, three stages of graphical construction of the convolution-output are shown. We note that this figure shows the circular convolution in time-domain while in our efficient implementation, the circular-convolution is performed in frequency-domain.
In Figure 11, we see the graphical construction of the correlation-output for k = 0, N and 2N-1. The convolution-results of k = 0 to k = N-l don't play any role, as the window after the IFFT in the PBFDAF discards these points. For the points N to 2N-1 in
we see that convolution of tail 1 is largely concerned with input block B2. When we assume that this tail is small, this convolution can be approximated by the convolution of input block B2 with this tail in the next partition. This is achieved by removing tail 1 in the right side of the adaptive weights and placing this tail inside the first N points of the adaptive weight of the next partition, depicted in Figure 12. We see that for small tails, the convolution output concerning the original tail 1 in this partition is approximately equal to the convolution output of this tail in the next partition.
On the other hand, we see that in Figure 12 there is also a right tail indicated by the number 2. For the points N to 2N-1 of the convolution output, we see that the convolution of tail 2 is also largely concerned with block B2. For convolution outputs close to 2N-1, there is only a small wrap-around with block B3. Again, for small tails, this convolution of tail 2 with input block B2 can also be obtained (approximately) in the previous partition. The destination of this tail 2 is depicted in Figure 11. When the adaptive weights are shown with modified principal intervals as in Figure 9, we can visualize the compensation in the partition i as shown in Figure 13. We note that this works well for the middle K-2 partitions, but there are problems for the first and the last partition. This topic is discussed later. Figure 14 shows a block diagram of an embodiment of a generator means for generating forward and backward compensation signals and Figure 15 shows some signal diagrams by means of which the operation of the generator means of Figure 14 is explained. For every weight vector constrained with a rectangular constraint, the forward and backward compensation signals Cj^N[κN mdC^N[κN] are generated. For reasons of transparency, all signals are constructed in time-domain. If we consider the unconstrained weight- vector as consisting of a linear convolution part and tailed circular wrap-around artifacts, the signals 1 to 6 of Figure 14 can be visualized as depicted in
Figure 15. A PBFDAF using this compensation has an improved convergence curve which does not have the large degradations in the NMSE on the moments that the exact rectangular constraint is performed. The positive effect of the compensation is clearly visible on the moments rectangular constraints are applied. The known PBFDAF shows large degradation in NMSE on these moments, whereas the compensated version shows an improvement. This improvement is due to the fact that the circular wrap-around artifacts are constrained to zero, while the useful information of the approximately linear correlation results is saved.
Furthermore, the compensation of the circular-errors from one partition into the neighbor partitions has a positive effect on the convergence time-constant or CTC.
We compensate N/2 time-domain points out of the circular wrap-around artifacts into the next and N/2 time-domain points into the previous partition. Only a part of these N/2 points are approximately linear (i.e. the tails in the figures) and thus useful, while the points between the tails are polluted with artifacts that have approximately 50% wraparound, and can be assumed to be noisy and useless. When we also compensate the noisy artifacts as depicted in Figure 14, the steady-state NMSE is slightly worsened. A solution for this problem is not to compensate the noisy part and only compensate the two tails. For this purpose, the compensated alternative constraining method in combination with the use of sinusoid windows as an approximation of the rectangular constraint may be used. The sinusoid window constrain the noisy parts in the update, while two tails remain for the compensation.
Using an unconstrained PBFDAF, the convergence behavior is impaired and the region of convergence is smaller than with a fully constrained PBFDAF. When applying a sinusoid constraint approximation g2N in combination with the alternative constraining method, improved results are obtained, compared with the unconstrained PBFDAF. The sinusoid approximation constraint g2N is defined as: ϋ2*),- " J (l + » (^)) - 0 < i < 2N. (5-2)
When applying sinusoid constraints, the noisy parts in the neighborhood of 3N/2 are reduced. On the other hand, the tails are not effectively reduced by the approximation constraint, but can be successfully compensated into the neighbor partitions with the method described in the previous section. The application of the rectangular windows of length N/2 in Figure 14 requires two extra FFTs. This complexity can be reduced by replacing the rectangular windows by a raised cosine and an raised inverse cosine window, as indicated in Figure 16. In Figure 14 the selection means comprise window block 104 and/or window block 106.
Figure 16 shows a block diagram of another embodiment of a generator means for generating forward and backward compensation signals and Figure 17 shows some signal diagrams by means of which the operation of the generator means as shown in Figure 16 is explained. Again all signals in are constructed in time-domain for transparency reasons. The raised cosine windows can be easily implemented in frequency-domain without the use of extra FFTs. The signals 1 to 6 are the same as in Figures 14 and 15 except that the noisy part is largely reduced by the sinusoid constraint approximations. The window for the backward compensation in the range N - i < 2N can be calculated by multiplying the sinusoid constraint window and the raised inverse cosine window. The window for the forward compensation can be calculated by multiplying the sinusoid constraint window and the raised cosine window. Figure 18 shows the window for the backward compensation. Figure 19 shows the window for the forward compensation. The selection means comprise here the combination of the sinusoid window and the raised cosine window (block 104)and/or the combination of the sinusoid window and the raised inverse cosine window (block 106).
In figure 20 we can see that the compensation leads to connections between the update blocks 34 of adjacent partitions. For the first partition, there is no compensation to the previous partition. For the last partition we omit the compensation to the next (non- existent) partition. Omitting this forward compensation for the last partition leads to removal of circular wrap-around artifacts, which could be useful for modeling a higher order impulse response. The update blocks 34 in Figure 20 exploit the compensation method as also explained in the previous section. The structure of these update blocks 34 is depicted in Figure 21. The sinusoid constraint 140 is placed before the coefficient update 142, while the rectangular constraint 150 is placed after the coefficient update 142, 144. The compensation signals are indicated with
signals are omitted (i.e. state 0 of the switches 146, 148, 152, 154). A linear way of rectangular constraining is applied, where the switches 146, 148, 152, 154 are described by the following formula:
I if K mod (KP) s= i 0 otherwise * ^ '
The use of an approximation constraint when also a rectangular constraint is applied seems to be needless. However, the compensation after applying a rectangular constraint also compensates the extra noise in the wrap-around artifacts (due to the omitting of the sinusoid constraint). Hence this leads to degradation in convergence behavior. Therefore it is preferred to also apply the approximation constraint when applying of a rectangular constraint with the compensation (see Figure 21). When implementing the rectangular constraint together with the compensation, we need additional computational complexity for the compensation part. This is because of the need of splitting up the two tails for the compensation in the next and previous partition and doing a time-domain shift of the two individual tails. A direct implementation as in Figure 14 is possible, but needs an abundant amount of extra computational complexity as all operations are performed in time-domain. A more efficient implementation can be obtained when generating the signals in frequency-domain. The shift in the time-domain is a N point shift of a 2N point signal
5.1 » resulting in the 2N point signal
And respectively. This shift can be easily implemented in the frequency-domain via lemma
5.3.1, which uses the shift-theorem. Lemma 5.3.1 If h » ti - Λ ' then:
The generation of the time-domain signals 2, 3 and 4 of Figure 14 can be easily calculated in frequency-domain. Figure 22 shows this efficient implementation. We note that <-zi2 ). - (-ι .
The elementwise multiplication of a frequency domain vector by this vector implements the time-domain shift of N points. As the compensation signals need to be added to the neighbor partitions, these elementwise multiplications by -1 and 1 can be omitted if we use both additions and subtractions. The raised cosine window is now applied in frequency-domain. The other (raised inverse cosine window) is calculated by simple subtraction operations and saves computational complexity. It is also noted that the multiplications by 1/2 and j/4 can be implemented as simple shift operations.
We already mentioned that it is not possible to perform the forward compensation in the last partition. Usually the circular wrap-around artifacts of this left tail are nulled by the rectangular constraint. As the wrap-around artifacts of this tail can be used for a higher order (>KN) adaptive filter, we could leave this tail unconstrained. The implementation of the compensation in the last partition is depicted in Figure 23. We note that the computational complexity of this implementation is slightly lower compared to the implementation of Figure 22. In the embodiments of Figures 22 and 23, the selection means comprise the
IFFT 160, zero appender 162, FFT 164 and the convolution block 168.
We already mentioned that the first partition in the PBFDAF does not retrieve a forward compensation signal from its predecessor partition, and the first partition does not have to generate a backward compensation signal. Hence the implementation of the update- block in the first partition can also be implemented with reduced computational complexity. Good constraint approximations for the Partitioned BFDAF algorithm do not result in a near-optimal convergence behavior compared with the fully constrained PBFDAF. This is caused by unconstrained circular wrap-around artifacts, which are accumulated in the weight-update and cause problems in the convolution part of the PBFDAF as the different partitions are coupled. When combining the constraint approximations with the Alternative constraining mechanism, we get an improvement, but still achieve non-optimal convergence behavior. A specific part of the accumulated wrap-around artifacts not removed by the constraint approximations are removed once in a while with the Alternative constraining mechanism. This specific part are approximately results of a linear correlation, that can be successfully reused (compensated) in the neighbor partitions. When we combine this method of compensation with the simplest form of constraint approximations (i.e. sinusoid constraint), we get a near-optimal convergence behavior compared to the fully constrained PBFDAF, while obtaining an enormous reduction in computational complexity. For four and more partitions, the number of operations of the PBFDAF is reduced by a factor two. Simulations show that the performance of this consfraining mechanism is also very good for highly correlated, non-stationary input signals.
« Adaptation constant
Backward compensation signal from partition i .
Desired signal (echo in ABC).
Desired signal corrupted with s [k].
-F Fourier transform matrix.
G2N Generalised constraint window. i Stochastic gradient vector. km Impulse response vector.
I* Identity matrix. j Imaginary unit. * Mirror matrix.
K Number of partitions in the PBFDAF algorithm.
K, Threshold partition for Hybrid constrained PBFDAF.
K Block time index. m Multiplicative factor for high-slope constraint approximation.
M{ - } Number of real multiplications.
Θ Memory occupation.
N Block length.
O. O All zero vector, matrix.
P Alternating constraint period. p*m Normalisation (power) vector. m Estimate of P_x.
Ψ Computational complexity measure. r[k] Residual signal s[k] Near-end signal.
X2N[lζN] m JF"1 • W [if N
.τ Vi y[κN - N + 1 + ] = (^v[*fJ ])., 0 < t < Λr
l-to-2 switch
2-to-l switch
Append zeros on the right
*' .vi . . ^'-.-]
-_---cEJ=_> yw[* j ] = ( o" ) ■£*!*"]
x_ N] „2Λ I«AΠ y∞ cN] X VNN π\=> [KN]
Nulling right part π =>
Dispose elements xTltNl yN[κN -* ( ΪN QM ) -x≤jV[/-iV]
Raised Cosine window YM[tcN] =
® N), where.
Rectangular constraint ( 2 @ GiV ) , where
High-slope window m G2N) . where
Sinusoid window ¥ N[κN] = j{Iω[(. JV] ® C?2Λ'), where
1. A partitioned block frequency domain adaptive filter for filtering an input signal in dependence on a control signal, the adaptive filter comprising a plurality of parallel arranged filter partitions, each filter partition being arranged for modeling a part of an impulse response of the adaptive filter, each filter partition having update means for updating filter coefficients of that filter partition by circular convoluting a signal representative of the input signal and a signal representative of the control signal, the update means comprising constraint means for intermittently constraining the filter coefficients by eliminating circular wrap-around artifacts of the circular convolution, characterized in that the update means are arranged for updating the filter coefficients in dependence on at least part of the circular wrap-around artifacts of adj acent update means.
2. The partitioned block frequency domain adaptive filter according to Claim 1 , characterized in that the update means are arranged for updating the filter coefficients in dependence on the at least part of the circular wrap-around artifacts only when the filter coefficients are constrained.
3. The partitioned block frequency domain adaptive filter according to Claim 1 or 2, characterized in that the update means comprise selection means for selecting the at least part of the circular wrap-around artifacts.
4. The partitioned block frequency domain adaptive filter according to Claim 3, characterized in that the selection means are arranged for selecting the at least part of the circular wrap-around artifacts when the filter coefficients are not constrained by the constraint means.
5. The partitioned block frequency domain adaptive filter according to Claim 3 or 4, characterized in that the selection means are arranged for selecting those circular wraparound artifacts which are substantially equal to at least part of the result of a linear convolution of the signal representative of the input signal and the signal representative of the control signal.
6. The partitioned block frequency domain adaptive filter according to any one of Claims 3 to 5, characterized in that the selection means comprise an approximation of a rectangular constraint window.
7. The partitioned block frequency domain adaptive filter according to Claim 6, characterized in that the approximation comprises a sinusoid window.
8. The partitioned block frequency domain adaptive filter according to Claim 6 or 7, characterized in that the selection means further comprise a raised cosine window and/or a raised inverse cosine window for selecting the at least part of the circular wrap-around artifacts.
9. The partitioned block frequency domain adaptive filter according to Claim 6, characterized in that time domain values of the approximation are larger than or equal to zero and in that the approximation in time domain has substantially high slopes near the positions which correspond to the positions of the transitions in a rectangular constraint window.
10. The partitioned block frequency domain adaptive filter according to Claim 9, characterized in that frequency domain values of the approximation each comprise a real value and mutually conjugate imaginary values, whereby at least part of the imaginary values form a row of numbers, the numbers being obtainable from one another by multiplication.
11. The partitioned block frequency domain adaptive filter according to Claim 10,
< 2iV, / even < 2N, i odd
characterized in that the frequency domain values of the approximation are defined as: with i being an index number, m being a multiplication factor, a being a mean value.
12. The partitioned block frequency domain adaptive filter according to Claim 11 , characterized in that m is substantially equal to 2.166.
13. An acoustic echo canceller comprising a partitioned block frequency domain adaptive filter for filtering an input signal in dependence on a control signal, the adaptive filter comprising a plurality of parallel arranged filter partitions, each filter partition being arranged for modeling a part of an impulse response of the adaptive filter, each filter partition having update means for updating filter coefficients of that filter partition by circular convoluting a signal representative of the input signal and a signal representative of the control signal, the update means comprising constraint means for intermittently constraining the filter coefficients by eliminating circular wrap-around artifacts of the circular convolution, characterized in that the update means are arranged for updating the filter coefficients in dependence on at least part of the circular wrap-around artifacts of adjacent update means.
14. The acoustic echo canceller according to Claim 13, characterized in that the update means are arranged for updating the filter coefficients in dependence on the at least part of the circular wrap-around artifacts only when the filter coefficients are constrained.
15. A method of adaptively filtering an input signal in dependence on a control signal, the method comprising the steps of: partitioning the input signal into partitions, for each partition updating filter coefficients by circular convoluting a signal representative of the input signal and a signal representative of the control signal, - for each partition intermittently constraining the filter coefficients by eliminating circular wrap-around artifacts of the circular convolution, characterized in that the method further comprises the step of updating the filter coefficients in dependence on at least part of the circular wrap-around artifacts of adjacent partitions.
16. The method according to Claim 15, characterized in that the step of updating the filter coefficients in dependence on the at least part of the circular wrap-around artifacts is performed only when the filter coefficients are constrained.
PCT/EP2001/009625 2000-08-21 2001-08-13 Partitioned block frequency domain adaptive filter WO2002017488A1 (en)
EP00202917 2000-08-21
EP00202917.1 2000-08-21
JP2002522066A JP2004507923A (en) 2000-08-21 2001-08-13 Partitioned block frequency domain adaptive filter
DE2001626105 DE60126105T2 (en) 2000-08-21 2001-08-13 Adaptive frequency domain filter blocks partitioned
EP20010971938 EP1314247B1 (en) 2000-08-21 2001-08-13 Partitioned block frequency domain adaptive filter
WO2002017488A1 true WO2002017488A1 (en) 2002-02-28
ID=8171932
PCT/EP2001/009625 WO2002017488A1 (en) 2000-08-21 2001-08-13 Partitioned block frequency domain adaptive filter
US (1) US7103623B2 (en)
EP (1) EP1314247B1 (en)
JP (1) JP2004507923A (en)
AT (1) AT352124T (en)
DE (1) DE60126105T2 (en)
WO (1) WO2002017488A1 (en)
JP4510795B2 (en) * 2005-11-25 2010-07-28 日本電信電話株式会社 Train estimating device, method, program, recording medium
JP4705554B2 (en) * 2006-11-14 2011-06-22 日本電信電話株式会社 Echo canceling device, the method, the program, and the record medium
KR101007384B1 (en) 2009-11-26 2011-01-13 삼성탈레스 주식회사 Method for adaptive filtering reflecting features of neighbor blocks
JP6151213B2 (en) * 2014-04-25 2017-06-21 日本電信電話株式会社 Echo canceller, echo cancellation method, program
EP3125429A1 (en) * 2015-07-28 2017-02-01 Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. Partitioned block frequency domain adaptive filter device comprising adaptation modules and correction modules
2001-08-13 DE DE2001626105 patent/DE60126105T2/en not_active Expired - Fee Related
2001-08-13 AT AT01971938T patent/AT352124T/en not_active IP Right Cessation
2001-08-13 JP JP2002522066A patent/JP2004507923A/en active Pending
2001-08-13 EP EP20010971938 patent/EP1314247B1/en not_active Not-in-force
2001-08-13 WO PCT/EP2001/009625 patent/WO2002017488A1/en active IP Right Grant
2001-08-20 US US09/933,556 patent/US7103623B2/en not_active Expired - Fee Related
JP2004507923A (en) 2004-03-11
DE60126105D1 (en) 2007-03-08
US7103623B2 (en) 2006-09-05
DE60126105T2 (en) 2007-08-30
US20020073128A1 (en) 2002-06-13
EP1314247B1 (en) 2007-01-17
AT352124T (en) 2007-02-15
EP1314247A1 (en) 2003-05-28
KR100799780B1 (en) 2008-01-31 Noise removing method and device
Buchner et al. 2004 Blind source separation for convolutive mixtures: A unified treatment
CA1266893A (en) 1990-03-20 Frequency-domain block-adaptive digital filter
EP0454242A1 (en) 1991-10-30 Digital echo canceller comprising a double-talk detector
EP0709999A2 (en) 1996-05-01 Method and apparatus for multi-channel acoustic echo cancellation
EP0735674A2 (en) 1996-10-02 Method and apparatus for adaptive filtering
Glentis et al. 1999 Efficient algorithms for Volterra system identification
EP0488575B1 (en) 1997-03-26 Technique for adjusting signal dispersion cancellation apparatus in communications systems
Shynk 1989 Adaptive IIR filtering using parallel-form realizations
US6522747B1 (en) 2003-02-18 Single-sided subband filters
Inouye et al. 2000 Super-exponential algorithms for multichannel blind deconvolution
Ref document number: 2002 522066
Ref document number: 2001971938