Multidelay block frequency domain adaptive filter

The Multidelay block frequency domain adaptive filter (MDF) algorithm is a block-based frequency domain implementation of the (normalised) Least mean squares filter (LMS) algorithm.

Introduction

The MDF algorithm is based on the fact that convolutions may be efficiently computed in the frequency domain (thanks to the Fast Fourier Transform). However, the algorithm differs from the Fast LMS algorithm in that block size it uses may be smaller than the filter length. If both are equal, then MDF reduces to the FLMS algorithm.

The advantages of MDF over the (N)LMS algorithm are:

Variable definitions

Let N be the length of the processing blocks, K be the number of blocks and \mathbf{F} denote the 2Nx2N Fourier transform matrix. The variables are defined as:

\underline{\mathbf{e}}(\ell) = \mathbf{F}\left[ \mathbf{0}_{1xN}, e(\ell N),\dots,e(\ell N-N-1) \right]^T
\underline{\mathbf{x}}_k(\ell) = \mathrm{diag} \left\{ \mathbf{F}\left[ x((\ell -k+1) N),\dots,x((\ell -k-1) N-1) \right]^T \right\}
\underline{\mathbf{X}}(\ell) = \left[ \underline{\mathbf{x}}_0(\ell), \underline{\mathbf{x}}_1(\ell), \dots, \underline{\mathbf{x}}_{K-1}(\ell) \right]
\underline{\mathbf{d}}(\ell) = \mathbf{F}\left[ \mathbf{0}_{1xN}, d(\ell N),\dots,d(\ell N-N-1) \right]^T

With normalisation matrices \mathbf{G}_1 and \mathbf{G}_2:

\mathbf{G}_1 = \mathbf{F}\begin{bmatrix} \mathbf{0}_{NxN} & \mathbf{0}_{NxN} \\ \mathbf{0}_{NxN} & \mathbf{I}_{NxN} \\ \end{bmatrix}\mathbf{F}^H
\tilde{\mathbf{G}}_2 = \mathbf{F}\begin{bmatrix} \mathbf{I}_{NxN} & \mathbf{0}_{NxN} \\ \mathbf{0}_{NxN} & \mathbf{0}_{NxN} \\ \end{bmatrix}\mathbf{F}^H
\mathbf{G}_2 = \mathrm{diag} \left\{ \tilde{\mathbf{G}}_2, \tilde{\mathbf{G}}_2, \dots, \tilde{\mathbf{G}}_2 \right\}

In practice, when multiplying a column vector \mathbf{x} by \mathbf{G}_1, we take the inverse FFT of \mathbf{x}, set the first N values in the result to zero and then take the FFT. This is meant to remove the effects of the circular convolution.

Algorithm description

For each block, the MDF algorithm is computed as:

\underline{\hat{\mathbf{y}}}(\ell) = \mathbf{G}_1 \underline{\mathbf{X}}(\ell) \underline{\hat{\mathbf{h}}}(\ell-1)
\underline{\mathbf{e}}(\ell) = \underline{\mathbf{d}}(\ell) - \underline{\hat{\mathbf{y}}}(\ell)
\mathbf{\Phi}_\mathbf{xx}(\ell) = \underline{\mathbf{X}}^H(\ell)\underline{\mathbf{X}}(\ell)
\underline{\hat{\mathbf{h}}}(\ell) = \underline{\hat{\mathbf{h}}}(\ell-1) + \mu\mathbf{G}_2\mathbf{\Phi}_\mathbf{xx}^{-1}(\ell) \underline{\mathbf{X}}^H(\ell) \underline{\mathbf{e}}(\ell)

It is worth noting that, while the algorithm is more easily expressed in matrix form, the actual implementation requires no matrix multiplications. For instance the normalisation matrix computation \mathbf{\Phi}_\mathbf{xx} = \underline{\mathbf{X}}^H(\ell)\underline{\mathbf{X}}(\ell) reduces to an element-wise vector multiplication because \underline{\mathbf{X}}(\ell) is block-diagonal. The same goes for other multiplications.

References

See also

This article is issued from Wikipedia - version of the 5/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.