2 asptbfdaf

Purpose

Block filtering and coefficient update in frequency domain using the Block Frequency Domain Adaptive Filter (BFDAF) algorithm.

Syntax

[W,x,y,e,Px,w]=asptbfdaf(M,x,xn,dn,W,mu,n,c,b,Px)

Description

Figure 4.2: Block diagram of the Block Frequency Domain Adaptive Filter.

asptbfdaf() is an efficient frequency domain implementation of the block NLMS algorithm. asptbfdaf() performs filtering and coefficient update in frequency domain using the overlap-save method, and therefore provide efficient implementation for long adaptive filters usually used in applications such as acoustic echo cancelers where the adaptive filter can be as long as a few thousand coefficients. asptbfdaf() is a block processing algorithm which is called every $L$ samples. Every call processes $L$ input and $L$ desired samples ($L$ is the block length), to produce $L$ filter output samples and $L$ error samples, besides updating all filter coefficients in the frequency domain. Fig. 4.2 shows the parameters of asptbfdaf() which are summarized below.

Input Parameters [Size]:: 
   M  : filter length [1 x 1]
   x  : previous overlap-save input vector [B x 1]
   xn : new input block [L x 1]
   dn : new desired block [L x 1]
   W  : F-domain filter coefficients vector [B x 1]
   mu : adaptation constant (step size) [1 x 1]
   n  : if not 0, normalization is performed
   c  : if not 0, constrains filter to length M 
   b  : forgetting factor for estimation of Px
   Px : previous estimate of the power of x [B x 1]
Output parameters::
   W  : updated F-domain filter coefficients 
   x  : updated overlap save input vector
   y  : filter output at block n (t-domain)
   e  : error vector (t-domain)
   Px : updated estimate of the power of X

Example

iter = 5000;        % Number of samples to process
% Complex unknown impulse response
h    = [.9 + i*.4; 0.7+ i*.2; .5; .3+i*.1; .1];     

xt   = 2*(rand(iter,1)-0.5);   % Input signal
% although xn is real, dn will be complex 
dt   = osfilter(h,xt);         % Unknown filter output 
en   = zeros(iter,1);          % estimation error

% Initialize BFDAF with a filter of 5 coef.
M = 5; L = 3;
[W,x,dn,e,y,Px,w]=init_bfdaf(L,M); 

%% Processing Loop
for (m=1:L:iter-L)
   xn = xt(m:m+L-1,:);             % input block
   dn = dt(m:m+L-1,:)+ 1e-3*rand;  % desired block   
   
   %  call BFDAF to calculate the filter output, 
   %  estimation error and update the filter coef. 
   [W,x,y,e,Px,w]=asptbfdaf(M,x,xn,dn,W,0.05,1,1,0.98,Px);
   % save the last error block to plot later
   en(m:m+L-1,:) = e;  
end;

% display the results
subplot(2,2,1);stem([real(w) imag((w))]); grid;
subplot(2,2,2);
eb = filter(.1,[1 -.9], en(1:m) .* conj(en(1:m)));
plot(10*log10(eb ));grid

Figure 4.3: The adaptive filter coefficients after convergence and the learning curve for the complex FIR system identification problem using the BFDAF algorithm.

Running the above script will produce the graph shown in Fig. 4.3. The left side graph of the figure shows the adaptive filter coefficients after convergence which are almost identical to the unknown filter h. The right side graph shows the mean square error in dB versus time during the adaptation process, which is usually called the learning curve. The lower limit of the error signal power in the learning curve is defined here by the additive white noise added at the filter output (-60 dB).

Algorithm

asptbfdaf() performs the following operations (see Fig. 4.2).

• buffers $L$ input samples, composes an overlap-save input vector $\vx (n)$ and computes its FFT, $\vX (f)$
• element-wise multiplies $\vX (f)$ by the adaptive filter coefficients vector $\vW (f)$ (circular convolution in time domain). The result is converted to time domain using IFFT and the linear convolution samples are extracted to produce the filter-output vector $\vy (n)$
• buffers $L$ desired samples and evaluates the current error block $\ve (n) = \vd (n) - \vy (n)$. The error vector is padded with zeros and transformed to frequency domain giving $\vE (f)$
• estimates the input signal power at each frequency bin and normalizes the step size at each bin.
• evaluates the cross-correlation between $\vX (f)$ and $\vE (f)$ to produce the block gradient vector. This vector is used to update the frequency domain filter coefficients.
• constrains the filter if required. This is performed by first taking the IFFT of $\vW (f)$, applying a rectangular window on the time domain coefficients, and taking the FFT of the windowed coefficients.

Remarks

• Supports both real and complex signals.
• asptbfdaf() constrains the filter coefficients $\vW (f)$ rather than the gradient vector as in the official BFDAF algorithms since this proved to result in a more stable update.
• The unconstrained BFDAF (c = 0) saves two FFT operations on the cost of accuracy.
• The time domain filter coefficients $\vw (n)$ will be calculated and returned by asptbfdaf() only if the output variable $w$ is given.
• The convergence properties of the BFDAF algorithm are superior to time domain algorithms since normalization is performed at each frequency bin which eliminates the eigenvalue spread problem.
• BFDAF introduces a processing delay between its input $x(n)$ and output $y(n)$ equals to the block length $L$, since the algorithm has to collect $L$ samples before processing a block.
• Very efficient for long adaptive filters since convolution and correlation are performed in frequency domain. Maximum efficiency is obtained when the block length is chosen to be equal to the filter length $L = M$.
• Choosing $L$ for maximum processing efficiency might result in a long delay for long filters. This can be solved either by reducing $L$ on the cost of computational efficiency or using the Partitioned BFDAF (asptpbfdaf()) instead.

Resources

The resources required for direct implement of the BFDAF algorithm in real time is given in the table below. The computations given are those required to process L samples using the constrained BFDAF. Unconstrained BFDAF uses two FFT operations less than the constrained BFDAF. In the table below $C(FFT_B)$ is used to indicate the number of operations required to implement an FFT or IFFT of length $B=2^{nextpow2(M+L-1)}$

MEMORY	$6B + 3L + 3$
MULTIPLY	$6B + 5* C(FFT_B)$
ADD	$3B + L + 5* C(FFT_B)$
DIVIDE	$B + 5* C(FFT_B)$

See Also

INIT_ BFDAF, ECHO_ BFDAF, ASPTPBFDAF, ASPTRCPBFDAF.

Reference

[3], Chapter 3 for detailed description of BFDAF, [8] for the overlap-save method, and [9] for frequency domain adaptive filters.