1 asptftrls

Purpose

Performs filtering and coefficient update using the Fast Transversal Recursive Least Squares (FTRLS) algorithm, also known as the Fast Transversal Filter (FTF) algorithm.

Syntax

[ff,bb,k,cf,c,g,w,e,y] = asptftrls(ff,bb,k,cf,c,g,w,a,x,d)

Description

asptftrls() is an efficient implementation of the joint process estimator, and is therefore an improvement over the asptrlslattice() and asptrlslattice2() functions. In the RLSLATTICE functions, the problem of prediction and filtering (joint process estimation) is solved for lattice sections and linear combiner of length $1, 2, \cdots L$ simultaneously, where $L$ is the linear combiner length. The improvement brought about by the FTRLS algorithm is obtained by concentrating on solving the problem only for a filter of length $L$, and therefore removing redundant calculations. Although the FTRLS has about half the computational complexity of the RLSLATTICE algorithms, it is known to be sensitive to round-off errors. This problem derive the algorithm unstable when finite precision calculations are used, for instance when implemented on a fixed-point DSP platform. There exist two solutions for this round-off error problem. The first is to detect the instability before occurring and reinitializing the algorithm with the current filter coefficients (soft initialization). This approach is implemented in asptftrls(). The second is to calculate the sensitive quantities in different ways (introduce computation redundancy), an approach followed by the Stabilized Fast Transversal RLS (SFTRLS) algorithm. The input and output parameters of asptftrls() of length $L$ are summarized below.

Input Parameters:: 
   ff  : last autocorrelation of forward prediction error (f)
   bb  : last autocorrelation of backward prediction error (b)
   k   : normalized gain vector
   cf  : last conversion factor 
   c   : forward transversal predictor coefficients vector
   g   : backward transversal predictor coefficients vector
   w   : transversal linear combiner coefficients vector
   a   : forgetting factor
   x   : input samples vector
   d   : desired response d(n)

Output parameters::
   ff  : updated autocorrelation of forward prediction error 
   bb  : updated autocorrelation of backward prediction error 
   k   : updated normalized gain vector
   cf  : updated conversion factor vector
   c   : updated forward predictor coefficients vector
   g   : updated backward predictor coefficients vector
   w   : updated linear combiner coefficients vector
   y   : linear combiner output 
   e   : error signal

Example

Figure 5.1: The adaptive linear combiner coefficients after convergence and the learning curve for the complex system identification problem using the FTRLS algorithm.

% FTRLSL used in a simple system identification application.
% By the end of this script the adaptive filter w 
% should have the same coefficients as the unknown filter h.

iter = 5000;                  % samples to process
% Complex unknown impulse response
h  = [.9 + i*.4; 0.7+ i*.2; .5; .3+i*.1; .1];     
xn = 2*(rand(iter,1)-0.5);   % Input signal
% although xn is real, dn will be complex since h is complex
dn = osfilter(h,xn);         % Unknown filter output 
en = zeros(iter,1);          % error signal
% Initialize FTRLS with a filter of 10 coef.
L   = 10;                    % filter length
a   = .9;                    % forgetting factor
[ff,bb,k,cf,c,g,w,x,d,e,y]=init_ftrls(L);

%% Processing Loop
for (m=1:iter)
  
   x = [xn(m,:); x(1:end-1)];  % input samples vector
   d = dn(m,:) + 1e-3*rand;    % additive noise var = 1e-6 
   [ff,bb,k,cf,c,g,w,e,y]=asptftrls(ff,bb,k,cf,c,g,w,a,x,d); 
   % save the last error sample to plot later
   en(m,:) = e;  
end;

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

Running the above script will produce the graph shown in Fig. 5.1. The left side graph of the figure shows the adaptive linear combiner coefficients after convergence which are almost identical to the unknown filter h. The right side graph shows the square error in dB versus time during the adaptation process. 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

asptftrls() performs the following operations each iteration

• Calculates the forward and backward prediction errors for the $L^{th}$ lattice stage,
• Calculates the backward (bb) and forward (ff) autocorrelations for the $L^{th}$ lattice stage,
• Calculates the conversion factor of the $L^{th}$ and $L+1^{th}$ lattice stages,
• Updates the normalized gain vector, and the forward and backward prediction coefficient vectors,
• Evaluates the linear combiner output and error signals,
• Updates the linear combiner coefficients,

Remarks

• asptftrls() supports real as well as complex signals and filters. The complex linear combiner FTRLS filter converges to the complex conjugate of the optimal solution.
• FTRLS algorithms have been found to be more sensitive to numerical rounding errors compared to RLS Lattice algorithms. asptftrls() detects the sign of instability, and reinitializes the algorithm before such instability occurs using the current coefficients vector.
• Stabilized versions of the FTRLS exist that introduce redundant calculations to improve robustness against numerical rounding errors, on the cost of extra computation. Even those stabilized versions have unstable modes that are excited when $\lambda$, the forgetting factor, is not close enough to unity. Since $\lambda$ should be set smaller for fast tracking applications, this certainly can be seen as a limiting factor.

Resources

The resources required to implement an FTRLS filter of length $L$ in real time is given in the table below. The computations given are those required to process one sample.

MEMORY	$5L + 9$
MULTIPLY	$7L +20$
ADD	$7L + 12$
DIVIDE	3

See Also

INIT_ FTRLS, ASPTRLSLATTICE.

Reference

[2] and [4] for analysis of the adaptive Lattice filters.