Description

The invention refers to a partitioned block frequency domain adaptive filter device. In particular, the invention refers to a novel constraining concept for partitioned block frequency domain adaptive filter (PBFDAF) devices.

Partitioned block frequency domain adaptive filter devices are known, for example, from reference [10]. One disadvantage of devices according to reference [10] is their high complexity.

It's an objective of the present invention to provide an improved partitioned block frequency domain adaptive filter device.

The objective is achieved by a partitioned block frequency domain adaptive filter device comprising: a frequency domain adaptive filter configured for filtering a frequency domain representation of a time domain input signal depending on a set of filter coefficients consisting of a plurality of blocks of filter coefficients in order to produce a filtered signal; a plurality of parallel arranged filter update blocks, each of the filter update blocks being configured for updating one of the blocks of filter coefficients based on an update signal gathered by a circular correlation of a block of the frequency domain representation signal and a frequency domain control signal comprising a representation of the filtered signal; wherein each of the filter update blocks comprises an adaptation module configured for executing an adaptation sequence comprising the steps of calculating an approximation of the constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying an approximated constraining matrix having a lesser complexity than a constraining matrix to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal , and calculating a cumulative error introduced on the unconstrained gradient update by applying the approximated constraining matrix to the unconstrained gradient update; wherein each of the filter update blocks comprises a correction module configured for executing a correction sequence comprising the steps of calculating a corrected constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying the constraining matrix to a sum of the approximation of the constrained gradient update and the cumulative error.

The constraining matrix is the frequency domain equivalent of applying a rectangular window function to a circular correlation of a block in the time domain, to select only the linear components, which may be defined as:

wherein n is the time index, M is the length of the discrete Fourier transform (DFT) and N is the number of filter coefficients in a block.

Following the analysis provided in reference [4], the elements of the constraining matrix, G, may be defined in the following way:

<?<*. *') = 7∑ W ^' M l - _c -j2*{*-*')/Af

with G(k, k') = N/M if k=k) where k and k' are the discrete frequency indices and W _M = e ^(~i2n/M) is the DFT basis function. The term approximated constraining matrix refers to any approximation of the constraining matrix in the frequency domain which has the same number of columns and rows as the constraining matrix but a lower complexity as the constraining matrix. The reduction of complexity may be, in particular, achieved by setting some of the elements to zero.

The invention reduces the complexity of partitioned block frequency domain adaptive filter devices by simplifying the constraining operation. In contrast to other previously proposed devices, the device according to the invention allows to reduce the complexity without noticeably reducing the convergence rate of the adaptive filtering, it is flexible in terms of the design parameters and it is fully parallelizable, as it corrects the approximation of the gradient update of one block based only on the cumulative error of that block.

The partitioned block frequency domain adaptive filter device according to the invention may be used for acoustic echo cancellation. Furthermore, the invention can be used to reduce the complexity of any partitioned block frequency domain adaptive filter device independently of a specific application. More precisely, it may be used in other applications such as system identification, noise reduction, channel equalization, etc.

According to a preferred embodiment of the invention the partitioned block frequency domain adaptive filter device comprises a correction sequence control module configured for deciding whether and at which of the filter update blocks the correction sequence is applied after executing the adaptation sequence.

According to a preferred embodiment of the invention the correction sequence control module is configured for deciding whether and at which of the filter update blocks the correction sequence is applied based on the cumulative errors of the filter update blocks.

According to a preferred embodiment of the invention the correction sequence control module comprises a correction scheme defining for each of the filter update blocks a number of adaptation sequences after which the correction sequence is applied at the respective filter partition.

According to a preferred embodiment of the invention for each of the filter update blocks the number of adaptation sequences after which the correction sequence is applied at the respective filter partition is diminished in response to a change of the frequency domain control signal which exceeds a threshold.

According to a preferred embodiment of the invention for each of the filter update blocks the number of adaptation sequences after which the correction sequence is applied at the respective filter partition is dynamically adapted based on a measure of the frequency domain control signal.

According to a preferred embodiment of the invention the partitioned block frequency domain adaptive filter device comprises an approximated constraining matrix update module configured for dynamically adapting the complexity of the approximated constraining matrix.

According to a preferred embodiment of the invention the approximated constraining matrix update module is configured for dynamically adapting the complexity of the approximated constraining matrix depending on a measure of the frequency domain control signal.

According to a preferred embodiment of the invention the approximated constraining matrix update module is configured for enlarging the complexity of the approximated constraining matrix in response to a change of the frequency domain control signal which exceeds a threshold.

In a further aspect the invention provides a device for cancelling an echo signal of a time domain input signal. The device comprises a partitioned block frequency domain adaptive filter device, the partitioned block frequency domain adaptive filter device comprising: a frequency domain adaptive filter configured for filtering a frequency domain representation of the time domain input signal depending on a set of filter coefficients consisting of a plurality of blocks of filter coefficients in order to produce a filtered signal; a frequency domain to time domain converter configured for converting the filtered signal into an estimated echo signal representing an estimation of the echo signal in time domain; a subtraction module for producing an output signal by subtracting the estimated echo signal from a signal-to-be-processed comprising the echo signal; a plurality of parallel arranged filter update blocks, each of the filter update blocks being configured for updating one of the blocks of filter coefficients based on an update signal gathered by a circular correlation of a block of the frequency domain representation signal and a frequency domain control signal comprising a representation of the filtered signal; wherein each of the filter update blocks comprises an adaptation module configured for executing an adaptation sequence comprising the steps of calculating an approximation of the constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying an approximated constraining matrix having a lesser complexity than a constraining matrix to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal, and calculating a cumulative error introduced on the unconstrained gradient by applying the approximated constraining matrix to the unconstrained gradient update; wherein each of the filter update blocks comprises a correction module configured for executing a correction sequence comprising the steps of calculating a corrected constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying the constraining matrix to a sum of the approximation of the constrained gradient update and the cumulative error.

In a further aspect the invention provides an adaptive filtering method comprising the steps of: using a frequency domain adaptive filter for filtering a frequency domain representation signal of a time domain input signal depending on a set of filter coefficients consisting of a plurality of blocks of filter coefficients in order to produce a filtered signal; using each filter update partition of a plurality of parallel arranged filter update blocks for updating one of the blocks of filter coefficients based on an update signal gathered by a circular correlation of a block of the frequency domain representation signal and a frequency domain control signal comprising a representation of the filtered signal; executing an adaptation sequence for each of the filter update blocks by using an adaptation module of the respective filter update block, the adaptation sequence comprising the steps of calculating an approximation of the constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying an approximated constraining matrix having a lesser complexity than a constraining matrix to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal, and calculating a cumulative error introduced on the unconstrained gradient by applying the approximated constraining matrix to the unconstrained gradient update; executing a correction sequence for each of the filter update blocks by using a correction module of the respective filter update block, the correction sequence comprising the steps of calculating a corrected constrained gradient update for the filter coefficients of the respective block of filter coefficients by applying the frequency domain constraining matrix to a sum of the approximation of the constrained gradient update and the cumulative error.

Computer program for adaptive filtering, when running on a processor, executing the inventive method.

Preferred embodiments of the invention are subsequently discussed with respect to the accompanying drawings, in which:

Fig. 1 provides an overview of a general structure of a frequency domain adaptive filter (FDAF) device according to prior art in a schematic view, taken from reference [1 ];

Fig. 2 provides an overview of a general structure of a frequency domain adaptive filter (PBFDAF) device according to prior art in a schematic view;

Fig. 3 illustrates a first embodiment of a partitioned block frequency domain filter device according to the invention in a schematic view;

Fig. 4 illustrates a second embodiment of a partitioned block frequency domain filter device according to the invention in a schematic view;

Fig. 5 illustrates a constraining operation according to the invention in a schematic view;

Fig. 6 provides examples of time domain constraining windows corresponding to different constraining matrices, wherein a window overlap of 50% is assumed; Fig. 7 provides examples of time domain constraining windows corresponding to different constraining matrices, wherein a window overlap of 75% is assumed;

Fig. 8 shows a principle of operation of a first embodiment of a correction sequence control module in the form of a block diagram;

Fig. 9 provides examples of correction schemes;

Fig. 10 shows a principle of operation of a second embodiment of a correction sequence control module in the form of a block diagram;

Fig. 1 1 provides examples of time domain windows and their corresponding constraining matrices in frequency domain; and

Fig. 12 illustrates a first embodiment of a device for cancelling an echo signal of a time domain input signal according to the invention in a schematic view.

Prior to the description of the new features of the invention, first some insight in the problems presented by performing the convolutions in the discrete Fourier transform domain (DFT domain) and a description of the constraining operation will be given. This will be followed by a formulation of the problem of frequency domain adaptive filters and their partitioned block based implementation in the specific context of acoustic echo cancellation (AEC).

Acoustic echo cancellation is used to cope with the electro acoustic coupling between loudspeakers and microphones in, for example, hands free communication scenarios. The electro acoustic coupling is the result of the loudspeaker, or far-end, signal being propagated through the room and acquired by the microphone. As a consequence, the microphone signal does not only contain the desired near-end speech and background noise, but also the acoustic echo signal. Acoustic echo cancelers use adaptive filter algorithms, see for example references [1] and [2], to identify the acoustic echo path which is necessary to estimate the acoustic echo signal. The estimated echo is then subtracted from the microphone signal prior to transmission.

Fig. 1 provides an overview of a general structure of a frequency domain adaptive filter (FDAF) device according to reference [1 ]. Frequency domain adaptive filter devices provide a lower algorithmic complexity compared to their time domain counterparts due to the fact that the convolutions (and correlations) are calculated in the DFT domain. However, a convolution or a correlation performed in the DFT domain corresponds to a circular convolution, or correlation, of length M, M being the length of the DFT, in the time domain, see reference [3], i.e.,

A(m)B(m) ί→ a(m)®b(m) (l)

A(w« )B ^{l [} ! w) f→ a(m)®b(-m) (2) where m is the discrete frame index, @ denotes circular convolution of length M and the superscript ( ·) ^Η denotes Hermitian transpose. In the remainder the following notation is used, bold letters are used for vectors and underlined bold letters for square matrices. Capital letters are used for denoting variables in the DFT domain. As in the following the focus is set on the correlations performed in the DFT domain, the constraining operation for a circular correlation will be described. The time domain circular correlation is defined by, see reference [3],

M-l

a{m)<g>b<-m) = T £i(»)l»(((m + n)) _M (3)

where n denotes the discrete time index and ((-))/w denotes M modulo operation. If it is assumed that the length of a(m) is M and that b(m) is of length L < M, in reference [3] only the first M - L + 1 coefficients coincide with the linear correlation, while the last L - 1 taps are the result of the wrap-around. As described in reference [1 ], the outcome of the circular correlation can be linearized by selecting only the linear coefficients and setting the rest of the coefficients to zero. This procedure is denoted as constraining operation. The general structure of a FDAF algorithm using the overlap-save (OLS) method is depicted in Fig. 1 , taken from reference [1 ]. It must be mentioned that the overlap-add (OLA) method could also be used, but for brevity only the OLS will be described. The notation used in the problem formulation is as follows, x(n) is the input or far-end signal which is propagated through the near-end room, d(n) = x{n) * h(n) is the echo signal and y(n) = d(n) + r(n) is the signal acquired by the microphone - which, in this context, is considered to be disturbed by the near-end signal, which may be denoted as s(n), and background noise, which may be denoted as v(n), so that r n)=s(n)+v(n). The acoustic echo path between the loudspeaker and microphone, denoted by h(n), is modeled as a finite impulse response filter (FIR filter) of length L. The adaptive algorithm is used to identify h(n), which is necessary to obtain the estimated echo signal, d{n), where the superscript ^" denotes estimation.

In reference [1 ] it is stressed that the error signal, which drives the adaptive algorithm, should be calculated in the time-domain, i.e., e{n) = y{n)-d(n) or be perfectly constrained if calculated in the DFT domain. Hereafter, throughout this document the terms 'constrained' and 'unconstrained' only refer to the gradient update, A (m), which is the result of a correlation computed in the DFT domain. The adaptive filter is updated by

H(m + 1 ) = H(wi) + DFT{gIDFT{/x(m)X ^W (m)E(m) }} (4)

= Hf ^' m) + D FT { gIDFT { A.H _UC {?« ) } } = H(m) + ΔΗ(τη), where m is the time frame index and cj = diag{g} is a diagonal matrix with the elements of g, g is a time domain window which eliminates the undesired components in the unconstrained gradient update, AH _uc (m), on its main diagonal. Following the OLS method definition in reference [1 ], the DFT domain input signal is X(m) = diag DFT{x(m)}} and the error signal is denoted by E(m) = DFT{[0i x _L , e ^T {m)] ^J }, with x(/77) = [x(mR - + 1 ), ....x(mR)]T and e(m) = [e(mR - V + 1 ), ,...e(mR)] respectively; where R is the frame shift, the input signal has the same length as the DFT and V > R is the length of the error signal. In addition, the gradi- ent update, AH(m), already includes the step-size matrix, jj(m), for compactness. In order to obtain L linear taps of the filter update, the length of the DFT has to be M≥ L + V - 1 . The OLS and OLA methods described in reference [1 ] are defined for V = L, and hence M = 2L is chosen as an even length fast Fourier transform (FFT) can be more efficiently implemented as an odd one. Given the definition of X(m) and E(m), the resulting AH _uc (m) will contain L + 1 linear components and M - L - 1 = V - 1 wrap-around components. However, for consistency H(m) is defined as,

H(m) = I) FT{ lh ^, i ^), Oi _x v] ^T }, (5) where it can be observed that the estimated echo path vector,

¾m) = ./i , _fl H i ). .„, ¾ _B (L - l)] ^T . {6) has to be zero-padded, and the length of the zero padding is V. The wraparound components are usually eliminated in the time domain, as depicted in Fig. 1 , however it is also possible to select the linear components by multiplying the unconstrained filter update by a constraining matrix in the frequency domain,

ΔΗ(τιι) = DFT{g - IDFT{AH _uc (·?»} } } = ¥g¥^AM _uc (m] = GA≡ _lK ( ) _f (7) where F is the M*M DFT matrix and G = FgF ¹ is the frequency domain constraining matrix. In order to analyze the structure of G, first the constraining window in the time domain has to be defined

Hereafter, following the analysis provided in reference [4], the elements of the constraining matrix, G, are with G(/ , / ^' ) = L/M if k=k'; where / and /(' are the discrete frequency indices irβ- π/Μ)

and W _M = e is the DFT basis function. The latter expression highlights the fact that the operation is equivalent to a frequency domain to frequency domain transform (similar to a decimation operation). It is possible to deduce from (9) that if the relation L/M is sufficiently large, the main diagonal of G will be dominant. In addition, if M is sufficiently large, the values on the off- diagonals will decay fast and towards negligible values, see reference [4].

Fig. 2 shows an example of a partitioned block frequency domain adaptive filter device. The partitioned block based formulation of a FDAF, first proposed in reference [5], provides a lower algorithmic delay as a non- partitioned FDAF implementation. In order to reduce the delay, the adaptive filter is partitioned into B blocks of length N=ceil(L/B), hence, h*(m) = [ WK -■■ ₅ WV + N - ¹ no; where b denotes the block index. The DFT length can now also be reduced, thus, using the OLS method, to obtain N linear coefficients the input signal frames have to be of length M≥ N ÷ V - 1 , where V is the length of the error signal and of the zero padding of h(m) (as already defined for the FDAF problem formulation). Hereafter, a block of input signal is defined as, x ^fr (f?i) = [x(mR - bN - M + 1), . .. , x(mR - 6iY)] ^T , (11) and the error signal is obtained by subtracting from the microphone signal the estimated echo, which is obtained as the sum over all the contributions per block, D ^b (m) = ^b (m)H ^b (m), i.e., [0 _{l x} * _t e ^T (m)] ^T = IOi _xJ v _s y ^T (m)] ^T - [0 _{l x} *, d ^T (m)] ^T

= IOi _xW , y ^T (m)] ^T - g - IDFT (12)

with

0 if n < N

and a(m) = [a(mR - V + 1) , . . . , α(πιΒ)] ^τ , with a€ (e, y, d) where g is the window needed to linearize a circular convolution, which, in the remainder, is assumed to be perfectly applied. Finally, the update of one block of the adaptive filter is described by

H*(m + 1 ) = H*(m) + iJ.(m)GX ^Mi (m)E(ffl) = H, ^b (m) + GAH* _c (m). (13)

It is obvious that now the length of the FFT's is reduced, but 2B FFT's have to be performed per frame to correctly linearize the circular correlations. In some applications it is desirable or even necessary to further reduce the complexity of the partitioned block based adaptive algorithms, and the most straightforward possibility is to reduce the number of transforms per frame by omitting the constraining operation. Another possibility is to simplify the frequency domain constraining matrix, G. Yet, these simplifications usually come at the cost of a loss of performance of the PB-FDAF algorithm.

On one hand, if the non-partitioned problem formulation is used only one IFFT and one FFT per frame are needed, whose length is usually sufficiently long to enable the omission of the constraining operation without noticeably impairing the performance. The omission of the constraining operation is usually denoted as unconstrained method. On the other hand, if a partitioned block based formulation is used, the length of the FFTs is reduced. Consequently, the error introduced by omitting the constraining operations becomes non-negligible, as this error increases with decreasing M - which is related to the decrease rate of the values on the off-diagonals of G.

In the past, several methods were proposed to reduce the complexity of the PB-FDAF algorithms without impairing the performance. These methods will be shortly described in the following. However, first it must be mentioned that the constraining operation per block can be performed in two ways, i.e. M ^b (rn + 1) = BT'I. M ί - GAH ) ; J : H ⁶ {ro + 1) = G(H ^fr (m) + ΔΗ ⁶ (τη) ) (15) where (14) can be interpreted as coping with the wrap-around errors before adaptation and (15) after adaptation. If the constraining matrix G is used without any simplification, both expressions are mathematically equal, but are the result of different implementations.

Some of the previously proposed methods to reduce the algorithmic complexity of the PBFDAF algorithms are

• the unconstrained FDAF and PBFDAF, references [6] and [7]

• the alternative unconstrained PBFDAF, reference [7]

• the alternated constraining method, reference [8]

• the modified alternated constraining method, reference [9].

The aim of all these methods, as well as of the invention, is to reduce the total number of FFTs per frame. The previously mentioned unconstrained method as proposed in references [6] and [7], directly omits the constraining operation, i.e.

H*(ra + 1 ) = H ^ft (m) + AH*(m), ¥6. (16)

It can also be applied as proposed in reference [4],

H ⁶ (m + 1 ) = H''i m ) + G _i AH ^b {m), ¥&.. (17) where, G _uc =™ \M*M is a scaled identity matrix, which is equivalent to considering only the main diagonal of G. The alternative unconstrained method proposed in reference [7], alternatively constrains one block per frame using (14). However, these three methods constantly accumulate the wrap-around errors in the updated filter coefficients, which reduce the convergence speed. The alternated constraining method uses (15) on top of the unconstrained algorithm, as proposed in reference [8]. By doing this, the accumulated wraparound errors between corrections are eliminated. This method allows for a further complexity reduction, which can be achieved if the frame interval between corrections P, is enlarged. The filter is then updated in two steps,

6 ⁶ (m + 1) = ttim) + A¾c(m); 6 = Q B— I (18a) ff'- t m - I ί < ; Π _{ W + 1) b _e = ((m/P)) _B , , l s ) where block b _c will only be corrected if the result of {{m/P)) _B i.e. is a non-negative natural number.

In reference [9] the modified alternated constraining method is proposed which is based on the alternated constraining method and is also applied in two steps, adaptation and correction. The main novelty of the method described in references [9] and [10] is that it uses an approximation of the constraining window g to reduce the wrap-around components per block in the adaptation step. The proposed approximation of the constraining window in [9] is

{ 1/2 if it = k ^f

-j/4 if k = k ¹ - 1 . (19) j/4 if Jfe = + 1 for a 50% overlap. The resulting window in the time domain is an elevated sine window, which is able to reduce the wrap-around errors. However, the linear coefficients are also modified and have to be compensated for in the correction step, in which also the remaining wrap-around errors are eliminated.

The modified alternated constraining method uses the wrap-around components of the previous and posterior blocks, in [10] denoted as adjacent blocks, to compensate the errors introduced on the linear coefficients of one block. Hence, it is necessary to correct two blocks to be able to completely compensate the linear components of one block; as a consequence the first and final blocks are not completely compensated for.

Fig. 3 illustrates a first embodiment of a partitioned block frequency domain filter device 1 according to the invention in a schematic view.

The partitioned block frequency domain adaptive filter device 1 comprises: a frequency domain adaptive filter 2 configured for filtering a frequency domain representation FDS of a time domain input signal IS depending on a set of filter coefficients consisting of a plurality of blocks FB.1 , FB.2, FB.B of filter coefficients in order to produce a filtered signal FS; a plurality of parallel arranged filter update blocks 3.1 , 3.2, 3.B, each of the filter update blocks 3.1 , 3.2, 3.B being configured for updating one of the blocks FB.1 , FB.2, FB.B of filter coefficients based on an update signal US.1 , US.2, US.B gathered by a circular correlation of a block BFDS.1 , BFDS.2, BFDS.B of the frequency domain representation signal FDS and a frequency domain control signal FCS comprising a representation RFS of the filtered signal FS; wherein each of the filter update blocks 3.1 , 3.2, 3.B comprises an adaptation module 4.1 , 4.2, 4.B configured for executing an adaptation sequence AS (see Fig. 5) comprising the steps of calculating an approximation of a constrained gradient update CU.1 , CU.2, CU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying an approximated constraining matrix ACM (see Fig. 12) having a lesser complexity than a constraining matrix FCM to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal US.1 , US.2, US.B, and calculating a cumulative error CE.1 , CE.2, CE.B introduced on the unconstrained gradient update by applying the approximated constraining matrix ACM to the unconstrained gradient update; wherein each of the filter update blocks 3.1 , 3.2, 3.B comprises a correction module 5.1 , 5.2, 5.B configured for executing a correction sequence CS (see Fig. 5) comprising the steps of calculating a corrected constrained gradient update CCU.1 , CCU.2, CCU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying the frequency domain constraining matrix FCM to a sum of the constrained gradient update CU.1 , CU.2, CU.B and the cumulative error CE.1 , CE.2, CE.B.

The partitioned block frequency domain adaptive filter device 1 functions as follows: the time domain input signal IS is converted into a frequency domain representation signal FDS by time domain to frequency domain converter 6. A block processor 7 extracts blocks BFDS.1 , BFDS.2, BFDS.B of the frequency domain representation signal FDS, which are conjugated to obtain the conjugated blocks BFDSM , BFDS'.2. BFDS'.B, which are necessary to calculate a correlation in the DFT domain. The frequency domain representation signal FDS is converted by the frequency domain adaptive filter to into a filtered signal FS in frequency domain, wherein blocks FB.1 , FB.2, FB.B of filter coefficients are used. The filtered signal FS is then transformed by frequency domain to time domain converter 8 into a time domain filtered signal FTS. Afterwards the time domain filtered signal FTS is subtracted from a signal-to-be-processed STP by subtraction module 9. The so produced output signal OS is converted back into a frequency domain by a time domain to frequency domain converter 10, which outputs a frequency domain control signal FCS which comprises the representation RFS of the filtered signal FS.

The circular correlation module 1 1 .1 executes a circular correlation by multiplying the frequency domain control signal FCS and the conjugated block BFDSM of the frequency domain representation signal FDS in order to produce the update signal US.1 . In the same way the circular correlation module 1 1 .2 executes a circular correlation by multiplying the frequency domain control signal FCS and the conjugated block BFDS'.2 of the frequency domain representation signal FDS in order to produce the update signal US.2. Similarly the circular correlation module 1 1 .B executes a circular correlation by multiplying the frequency domain control signal FCS and the conjugated block BFDS'.B of the frequency domain representation signal FDS in order to produce the update signal US.B.

Each of the update signals US.1 , US.2 and US.B is fed to one of the adaptation modules 4.1 , 4.2, 4.B. Each of the adaptation modules calculates an approximation of the constrained gradient update CU.1 , CU.2, CU.B and a cumulative error CE.1 , CE.2, CE.B. The cumulative errors CE.1 , CE.2, CE.B are forwarded to the correction modules 5.1 , 5.2, 5.B whereas the approximation of the constrained gradient updates CU.1 , CU.2, CU.B may be forwarded alternatively to the correction modules 5.1 , 5.2, 5.B or to the blocks FB.1 , FB.2, FB.B of filter coefficients by switching the respective switch of the switches 12.1 , 12.2, 12. B.

According to a preferred embodiment of the invention the partitioned block frequency domain adaptive filter device 1 comprises a correction sequence control module 13 configured for deciding whether and at which of the filter update blocks 3.1 , 3.2, 3.B the correction sequence CS is applied after executing the adaptation sequence AS.

In a further aspect the invention provides an adaptive filtering method comprising the steps of: using a frequency domain adaptive filter 2 for filtering a frequency domain representation FDS of a time domain input signal depending on a set of filter coefficients consisting of a plurality of blocks FB.1 , FB.2, FB.B of filter coefficients in order to produce a filtered signal FS; using each filter update block 3.1 , 3.2, 3.B of a plurality of parallel arranged filter update blocks 3.1 , 3.2, 3.B for updating one of the blocks FB.1 , FB.2, FB.B of filter coefficients based on an update signal US.1 , US.2, US.B gathered by a circular correlation of a block BFDS.1 , BFDS.2, BFDS.B of the frequency domain representation signal FDS and a frequency domain control signal FCS comprising a representation RFS of the filtered signal FS; executing an adaptation sequence AS for each of the filter update blocks 3.1 , 3.2, 3.B by using an adaptation module 4.1 , 4.2, 4.B of the respective filter update block 3.1 , 3.2, 3.B, the adaptation sequence AS comprising the steps of calculating an approximation of a constrained gradient update CU.1 , CU.2, CU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying an approximated constraining matrix ACM having a lesser complexity than a constraining matrix FCM to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal US.1 , US.2, US.B, and calculating a cumulative error CE.1 , CE.2, CE.B introduced on the unconstrained gradient by applying the approximated constraining matrix ACM to the unconstrained gradient update; executing a correction sequence CS for each of the filter update blocks 3.1 , 3.2, 3.B by using a correction module 5.1 , 5.2, 5.B of the respective filter update block 3.1 , 3.2, 3.B, the correction sequence CS comprising the steps of calculating a corrected constrained gradient update CCU.1 , CCU.2, CCU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying the constraining matrix FCM to a sum of the approximation of the constrained gradient update CU.1 , CU.2, CU.B and the cumulative error CE.1 , CE.2, CE.B..

In another aspect the invention provides a computer program for adaptive filtering, when running on a processor, executing the method according to the invention.

Fig. 4 illustrates a second embodiment of a partitioned block frequency domain filter device according to the invention in a schematic view. For the sake of convenience only the adaptation module 4.B and the correction module 5.B are shown. In the following, the invention is described. The proposed method is applied in two steps, as the alternated constraining method, and uses an arbitrary simplification of the constraining matrix, in the following denoted as arbitrary constraining window G _ar b, to reduce the wrap-around components during adaptation. Moreover, it is flexible in terms of the overlap between frames and the design of the constraining window approximation - it is valid for any constraining window approximation. In addition, the frame interval between corrections, P, can be selected differently for each block, which will be denoted as P _b , as the correction step depends only on the past states of the corrected block and not on the adjacent blocks. To start with (18b) can be reformulated as

H ^& = (fB + 1) = G{H ^fc (fii) + Δ¾(ηι)) = G H ^fc (m - P _b B + I ) + Γ Δ¾¾?τι - p) (20)

which highlights the fact that between corrections the gradient updates are accumulated. Hereafter, if an arbitrary approximation of the constraining matrix, Garb, is applied during adaptation, the corrected filter update is defined by,

H ^fc (TO + 1 ) = G I H ^fc (m - P _b B + 1 ) + ∑ β _Μ¾ ΔΪ¾ (m - p) j . (21 )

p=0

By doing this an error is introduced per frame and block on the linear correlation components, which has to be compensated before the correction step, i.e.

!\B-1

H ^6t (TO + 1} = G j H^™ - PtB + l) + T G _aA A¾(ffl. - p) + ] .

Hence, by equating (20) and (21 ), the compensation factor A ^b ^ _rb is obtained. ¾ ^β -1 J\B-1

∑ Ai¾(m ^{^} p) = J G^AH^irn ^{^} ^ + A^ (23a) A^ _b = ∑ (A¾m " P) " G _arb A _ffl -- p)) . (23b)

.6. I]

Thus, A ^b ^ _rb can be interpreted as the cumulative error introduced on the unconstrained gradient update by applying an approximated constraining matrix. The proposed method is summarized in Table 2.

The procedure is as follows. First, an arbitrary approximation of the constraining window in the frequency domain is used, to enhance the adaptation process, and the cumulative difference A ^b _rb , is updated. Afterwards, for example every P _b frames, A ^b _rb is used to reconstruct the unconstrained filter update, prior to eliminating the wrap-around components. Finally, the cumulative difference is reset to zero. Hereafter, the linear components are perfectly corrected using only the error introduced on the to-be-corrected block, be, in the past. Thus, the implementation of the proposed constraining method can be easily parallelized. Table 2 provides a pseudo code for the implementation of the adaptation sequence and the correction sequence according to the invention. The constraining method according to the invention may also be called enhanced alternated constraining method.

Table 2: Enhanced alternated constraining method far b = 0 I B - I:

H ^b (m + 1) = H*(m) + G _fHt ,a¾ _c (ro)

H ^fr« (m + 1) = G(H ^fc (m + 1) + A¾. _b )

Fig. 5 illustrates a constraining operation according to the invention in a schematic view. Although the adaptation sequence AS and the correction sequence CS are both executed in the frequency domain, the graphs show the equivalent windowing elements in the time domain.

The proposed method is schematically depicted for one block in Fig. 5, with Gar _b = Gs and 50% frame overlap (block overlap in time domain). The selection of the constraining window and P _b will, of course, influence the performance of the adaptive algorithm and the final algorithmic complexity.

The design of the constraining window approximation can be done flexibly. For example, a limited number T of pairs of off-diagonals of G can be taken into account. By doing this, the time domain counterpart could become negative. This can be avoided, if desired, by adding an offset to the time domain window, and modifying G _arb accordingly. Another possibility is to design a window in the time domain, and use its frequency domain counterpart.

Fig. 6 provides examples of time domain constraining windows corresponding to different constraining matrices, wherein a window overlap of 50% is assumed.

Fig. 7 provides examples of time domain constraining windows corresponding to different constraining matrices, wherein a window overlap of 75% is assumed.

Figs. 6a and 7a depict the approximated windows obtained by taking a limited number of off-diagonals of G into account, which is equivalent to taking the inter-band correlations into account. Figs. 6b and 7b depict extensions of G _s , as defined in (19), adding T-1 pairs of off-diagonals to G _s . For clarity, it must be mentioned that G _S ² stands for (G _s ) ² .

The complexity introduced by the application of these windows is proportional to the number of pairs of off-diagonals T, used for the design of Gar _b - Moreover, the lowest complexity is obtained if the values on the off-diagonals are real or purely imaginary. Finally, the proposed method is not only flexible with respect to the approximation of the windows and the overlap between frames, but in addition, for a fixed overlap, G _arb can be modified on-line. This can be desirable if a certain performance is reached, if there is a sudden need to further reduce the complexity - for example if the device used enters an energy saving mode - or if the adaptive filtering process has to be reinitialized, for example due to the detection of an echo path change.

Fig. 8 shows a principle of operation of a first embodiment of a correction sequence control module in the form of a block diagram.

It should be mentioned that the order and the frequency in which the blocks are corrected can be designed flexibly, and can be modified on-line. Consequently, one embodiment of the present invention is proposed with the gradient update procedure AS and correction procedure CS as described in Table 3 and depicted in Fig. 8.

Table 3: Controlled im lementation of the EAC method for b = 0 : B - 1:

A = A| _rb + A,i¾ _c {m) - G„ _b A¾,.(m)

if {(¾ + /(m)/i¾))fl = & _B :

H ^fre (m + 1) = G{H ^fc (fii + 1) + A^ _rb )

Hereafter the decision on whether a block and which block has to be corrected is given by ((S& + f {m) / P _b )) _B = b _c , with b _c = (0, 1 , . . . , B - 1 ); where Sj> is an offset factor which determines the order in which the corrections start, and f {m) is a counter function. The counter function can be controlled or reset by, for instance, the output of an echo path change (EPC) detector, see for example reference [1 1 ], as depicted in Fig.10, or based on a measure of the error signal, for instance, the normalized mean squared error (NMSE). As already mentioned, P _/ , determines the frequency in which each block is corrected. Some possible schemes for the correction intervals, for S _/ , = 0 v£>, are depicted in Fig. 1 1 .

Fig. 9 provides examples of correction schemes CSC. According to a preferred embodiment of the invention the correction sequence control module 13 is configured for deciding whether and at which of the filter update blocks 3.1 , 3.2, 3.B the correction sequence CS is applied based on the cumulative errors of the filter update blocks 3.1 , 3.2, 3.B.

According to a preferred embodiment of the invention the correction sequence control module 13 comprises a correction scheme CSC defining for each of the filter update blocks 3.1 , 3.2, 3.B a number of adaptation sequences AS after which the correction sequence CS is applied at the respective filter partition 3.1 , 3.2, 3.B.

According to a preferred embodiment of the invention for each of the filter update blocks 3.1 , 3.2, 3.B the number of adaptation sequences AS after which the correction sequence CS is applied at the respective filter partition 3.1 , 3.2, 3.B is diminished in response to a change of the frequency domain control signal FCS which exceeds a threshold.

According to a preferred embodiment of the invention for each of the filter update blocks 3.1 , 3.2, 3.B the number of adaptation sequences AS after which the correction sequence CS is applied at the respective filter partition 3.1 , 3.2, 3.B is dynamically adapted based on a measure of the frequency domain control signal FCS.

The order in which the blocks are corrected can be designed flexibly, for example based on the energy of the cumulative difference of each block, i.e., A ^b _arb . It must be noted that the higher the energy of the cumulative difference of one block, the bigger the error introduced on the linear components. Hereafter, a gain in the performance can be obtained by correcting first the blocks FB.1 , FB.2, FB.B with the highest cumulative differences.

Fig. 10 shows a principle of operation of a second embodiment of a correction sequence control module in the form of a block diagram.

According to a preferred embodiment of the invention the partitioned block frequency domain adaptive filter device 1 comprises an approximated con- straining matrix update module 14 configured for dynamically adapting the complexity of the arbitrary constraining matrix.

According to a preferred embodiment of the invention the approximated constraining matrix update module 14 is configured for dynamically adapting the complexity of the approximated constraining matrix ACM depending on a measure of the frequency domain control signal FCS.

According to a preferred embodiment of the invention the approximated constraining matrix update module 14 is configured for enlarging the complexity of the approximated constraining matrix ACM in response to a change of the frequency domain control signal FCS which exceeds a threshold.

It must be stressed that for the proposed method neither the approximation of the constraining window nor the frame overlap are specified, as they can be arbitrarily designed. Moreover, it is even possible to use different approximations of the constraining matrices and frame intervals between correction sequences CS for each block FB.1 , FB.2, FB.B (number of adaptation sequences AS after which the correction sequence CS is applied at the respective filter block). These parameters can be modified on-line depending, for example, on an echo path change detector 16 (EPC detector) or on a measure of the frequency domain control signal FCS, as for example the normalized mean squared error (NMSE), as depicted in Fig. 12.

The inventive provides flexibility in terms of nearly all the design parameters, i.e., the approximated constraining matrix ACM, frame overlap, order of the corrections and different interval between corrections for each block. Moreover, for a fixed frame overlap, all the other design parameters can be modified on-line without having to reinitialize the adaptive algorithm. This enables to control the trade-off between the algorithmic complexity and the convergence speed of the PBFDAF device. However, the algorithmic complexity will highly depend on both the design of the approximated constraining matrix ACM and the correction scheme for each block.

Fig. 1 1 provides examples of time domain windows and their corresponding constraining matrices in frequency domain. Fig. 1 1 (a) illustrates the con- straining matrix FCM, whereas Fig. 1 1 (b) and Fig .1 1 (c) each illustrate an approximated constraining matrix ACM having a lesser complexity than the constraining matrix FCM. The grey scale values correspond to the values of the elements of the respective matrix.

Fig. 12 illustrates a first embodiment of a device for cancelling an echo signal of a time domain input signal according to the invention in a schematic view. The device 16 comprises a partitioned block frequency domain adaptive filter device 1 , the partitioned block frequency domain adaptive filter device 1 comprising: a frequency domain adaptive filter 2 configured for filtering a frequency domain representation signal FDS of the time domain input signal IS depending on a set of filter coefficients consisting of a plurality of blocks FB.1 , FB.2, FB.B of filter coefficients in order to produce a filtered signal FS; a frequency domain to time domain converter 8 configured for converting the filtered signal FS into an estimated echo signal EES representing an estimation of the echo signal ES in time domain; a subtraction module 9 for producing an output signal OS by subtracting the estimated echo signal EES from a signal-to-be-processed STP comprising the echo signal ES; a plurality of parallel arranged filter update blocks 3.1 , 3.2, 3.B, each of the filter update blocks 3.1 , 3.2, 3.B being configured for updating one of the blocks FB.1 , FB.2, FB.B of filter coefficients based on an update signal US.1 , US.2, US.B gathered by a circular correlation of a block BFDS.1 , BFDS.2, BFDS.B of the frequency domain representation signal FDS and a frequency domain control signal FCS comprising a representation of the filtered signal FS; wherein each of the filter update blocks 3.1 , 3.2, 3.B comprises an adaptation module 4.1 , 4.2, 4.B configured for executing an adaptation sequence AS comprising the steps of calculating an approximation of a constrained gradient update CU.1 , CU.2, CU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying an approximated constraining matrix ACM having a lesser complexity than a constraining matrix FCM to an unconstrained gradient update for the filter coefficients of the respective block of filter coefficients, wherein the unconstrained gradient update is derived from the update signal US.1 , US.2, US.B, and calculating a cumulative error CE.1 , CE.2, CE.B introduced on the unconstrained gradient by applying the approximated constraining matrix ACM to the unconstrained gradient update; wherein each of the filter update blocks 3.1 , 3.2, 3.B comprises a correction module 5.1 , 5.2, 5.B configured for executing a correction sequence CS comprising the steps of calculating a corrected constrained gradient update CCU.1 , CCU.2, CCU.B for the filter coefficients of the respective block FB.1 , FB.2, FB.B of filter coefficients by applying the frequency domain constraining matrix FCM to a sum of the approximation of the constrained gradient update CU.1 , CU.2, CU.B and the cumulative error CE.1 , CE.2, CE.B.

The partitioned block frequency domain adaptive filter device 1 of Fig. 12 is equivalent to the partitioned block frequency domain adaptive filter device 1 discussed above. In the example of Fig. 12 an echo sound signal SES, which may comprise far end speech, is produced by a loudspeaker LS to which the input signal IS is fed. A microphone Ml acquires the echo sound signal SES as a well as a wanted sound signal SWS, which may comprise near end speech and background noise, so that the signal-to-be-processed STP comprises an echo signal ES based on the echo sound signal SES and of a wanted signal WS based on the wanted so signal SWS. As the estimated echo signal EES is subtracted from the signal-to-be-processed STP, the echo signal ES is effectively canceled in the output signal OS.

With respect to the devices and the methods of the described embodiments the following shall be mentioned: Although some aspects have been described in the context of an apparatus, it is clear that these aspects also represent a description of the corresponding method, where a block or device corresponds to a method step or a feature of a method step. Analogously, aspects described in the context of a method step also represent a description of a corresponding block or item or feature of a corresponding apparatus.

Depending on certain implementation requirements, embodiments of the invention can be implemented in hardware or in software. The implementation can be performed using a digital storage medium, for example a floppy disk, a DVD, a CD, a ROM, a PROM, an EPROM, an EEPROM or a FLASH memory, having electronically readable control signals stored thereon, which cooperate (or are capable of cooperating) with a programmable computer system such that the respective method is performed.

Some embodiments according to the invention comprise a data carrier having electronically readable control signals, which are capable of cooperating with a programmable computer system such that one of the methods described herein is performed.

Generally, embodiments of the present invention can be implemented as a computer program product with a program code, the program code being operative for performing one of the methods when the computer program product runs on a computer. The program code may for example be stored on a machine readable carrier.

Other embodiments comprise the computer program for performing one of the methods described herein, which is stored on a machine readable carrier or a non-transitory storage medium.

In other words, an embodiment of the inventive method is, therefore, a computer program having a program code for performing one of the methods described herein, when the computer program runs on a computer. A further embodiment of the inventive methods is, therefore, a data carrier (or a digital storage medium, or a computer-readable medium) comprising, recorded thereon, the computer program for performing one of the methods described herein.

A further embodiment of the inventive method is, therefore, a data stream or a sequence of signals representing the computer program for performing one of the methods described herein. The data stream or the sequence of signals may be configured, for example, to be transferred via a data communication connection, for example via the Internet.

A further embodiment comprises a processing means, for example a computer, or a programmable logic device, in particular a processor comprising hardware, configured or adapted to perform one of the methods described herein.

A further embodiment comprises a computer having installed thereon the computer program for performing one of the methods described herein.

In some embodiments, a programmable logic device (for example a field programmable gate array) may be used to perform some or all of the functionalities of the methods described herein. In some embodiments, a field programmable gate array may cooperate with a microprocessor in order to perform one of the methods described herein. Generally, the methods are advantageously performed by any hardware apparatus.

While this invention has been described in terms of several embodiments, there are alterations, permutations, and equivalents which fall within the scope of this invention. It should also be noted that there are many alternative ways of implementing the methods and compositions of the present invention. It is therefore intended that the following appended claims be interpreted as including all such alterations, permutations and equivalents as fall within the true spirit and scope of the present invention.

Reference signs: 1 partitioned block frequency domain adaptive filter device

2 frequency domain adaptive filter

3 filter update block

4 adaptation module

5 correction module

6 time domain to frequency domain converter

7 block processor

8 frequency domain to time domain converter

9 subtraction module

10 time domain to frequency domain converter

1 1 circular correlation module

12 switch

13 correction sequence control module

14 approximated constraining matrix update module

15 echo path change detector

16 device for cancelling an echo signal

FDS frequency domain representation signal

IS time domain input signal

FB block of filter coefficients

FS filtered signal

US update signal

BFDS block of the frequency domain representation signal

BFDS' conjugated block of the frequency domain representation signal

FCS frequency domain control signal

RFS representation of the filtered signal

CU approximation of the constrained gradient update

CE cumulative error

CCU corrected constraint gradient update

FTS time domain filtered signal

STP signal-to-be-processed

OS output signal

CSC correction scheme

AS adaptation sequence

CS correction sequence FC constraining matrix

ACM approximated constraining matrix

EES estimated echo signal

ES echo signal

WS wanted signal

LS loudspeaker

Ml microphone

References:

[1 ] J. J. Shynk, "Frequency-domain and multirate adaptive filtering," IEEE Signal Process. Mag., vol. 9, no. 1 , pp. 4-37, Jan. 1992.

[2] S. Haykin, Adaptive Filter Theory, 4th ed. Prentice-Hall, 2002.

[3] A. Oppenheim and R. W. Schafer, Digital Signal Processing, 2nd ed.

Prentice-Hall Inc., Englewood Cliff, NJ, 1993.

[4] J. Benesty and D. R. Morgan, "Frequency-domain adaptive filtering revisited, generalization to the multi-channel case, and application to acoustic echo cancellation," in Proc. IEEE ICASSP, vol. 2, pp. 289- 292, 2000.

[5] P. C. W. Sommen, "Partitioned frequency-domain adaptive filters," in Proc. Asilomar Conf. on Signals, Systems and Computers, pp. 677- 681 , 1989.

[6] D. Mansour and A. J. Gray, Jr, "Unconstrained frequency-domain

adaptive filter," IEEE Trans. Acoust., Speech, Signal Process., vol. 30, no. 5, pp. 726-734, Oct. 1982.

[7] J. S. Soo and K. K. Pang, "Multidelay block frequency domain adaptive filter," IEEE Trans. Acoust., Speech, Signal Process., vol. 38, pp. 373-376, Feb. 1990. [8] M. Joho and G. S. Moschytz, "Connecting partitioned frequency- domain filters in parallel or in cascade," IEEE Trans. Circuits Syst. II, vol. 47, no. 8, pp. 685-697, Aug. 2000.

[9] R. M. M. Derkx, G. P. M. Engelmeers, and P. C. W. Sommen, "New constraining method for partitioned block frequency-domain adaptive filters," IEEE Trans. Signal Process., vol. 50, no. 3, pp. 2177-2186, 2002.

[10] "Partitioned block frequency domain adaptive filter," Dutch European Patent PCT/EP2001/009 625, Aug. 13, 2001 .

[1 1 ] M. A. Iqbal and S. L. Grant, "A novel normalized cross-correlation based echo-path change detector," in 2007 IEEE Region 5 Conference, Fayetteville, AR, pp. 249-251 , Apr. 2007.