17 aspttdftaf

Purpose

Performs sample-per-sample filtering and coefficient update using the Transform Domain Fault Tolerant Adaptive Filter (TDFTAF) algorithm. TDFTAF contains redundant filter coefficients to improve the filter robustness against partial hardware failure during operation.

Syntax

[W,y,e,p,w] = aspttdftaf(x,W,d,mu,p,b,T)

Description

Fault tolerant adaptive filters address the issue of robustness against hardware failure. When a hardware failure occurs during the operation of a non fault tolerant adaptive filter, the filter diverges and will never converge again, unless special measures are taken to guarantee recovery. Fault tolerant adaptive filters makes sure that the filter can recover as quickly as possible after the occurrence of a hardware failure. The aspttdftaf() algorithm achieves hardware fault tolerance by introduces one or more redundant filter coefficients that will allow the filter to quickly recover to the optimal solution after the occurrence of a hardware failure in the underlying hardware running the filter. The type of hardware failure usually encountered in practice is partial memory failure. This type of hardware failure makes filter coefficients stored at the faulty memory locations appear to remain at an arbitrary constant value. Similar to the aspttdlms(), aspttdftaf() implements the Transform Domain LMS adaptive algorithm used to update transversal adaptive filters. The algorithm performs filtering and coefficient update in the transform domain, T. Normalization of the step size by the input signal power is also performed in each band in the T-domain, which usually improves the convergence behavior compared to the conventional LMS when T is an orthogonal transformation. The only difference between TDFTAF and TDLMS is that the former updates $L+R$ filter coefficients, where $L$ is the number of original filter coefficients and $R$ is the number of redundant coefficients. The block diagram of the TDFTAF is shown in Fig. 4.18. aspttdftaf() takes an input samples delay line $\vx (n)$ and applies the transformation T on this vector. This T-domain data vector is filtered through the vector of T-domain adaptive filter coefficients from previous iteration $\vW (n-1)$ to produce the time-domain filter output $y(n)$. The error $e(n) = d(n) - y(n)$ is then calculated and the power of the input vector is estimated in the T-domain at each band and used to normalize the step size. The update equation used by aspttdftaf() to update each T-domain coefficient is given by

$$W_i(n) = W_i(n-1) + \frac{\mu} {P_i(n)} e(n) X_i(n); \;\; i=0,1,\cdots,L+R-1.$$ (39)

Where $W_i(n)$, $X_i(n)$, and $P_i(n)$ are the filter coefficient, input signal, and input signal power in band $i$ at time index $n$, respectively. The input and output parameters of aspttdftaf() for an FIR adaptive filter of $L$ coefficients are summarized below.

Input Parameters [Size]:: 
  x   : input samples delay line [L+R x 1]
  W   : previous T-domain coef. vector W(n-1) [L+R x 1]
  d   : desired output d(n) [1 x 1]
  mu  : adaptation constant
  p   : last estimated power of x p(n-1) [L x 1]
  b   : AR pole for recursive calculation of p
  T   : The transform to be used {fft|dct|dst|...}
        user defined transforms are also supported.
        use transform T and its inverse iT. 
Output parameters::
  W   : updated T-domain coef. vector
  y   : filter output y(n)
  e   : error signal; e(n) = d(n)-y(n)
  p   : new estimated power of x p(n)
  w   : updated t-domain coef. vector w(n), only 
        calculated if this output argument is given.

Figure 4.18: Block diagram of the Transform Domain Fault Tolerant Adaptive Filter.

Example

% TDFTAF used in a simple system identification application.
% During simulation two coefficients are fixed at arbitrary 
% values to simulate a hardware failiar.
%
iter = 5000;                  % Number of 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, zero mean random.
% although xn is real, dn will be complex since h is complex
dn   = osfilter(h,xn);        % Unknown filter output 
en   = zeros(iter,1);         % vector to collect the error
% Initialize the TDFTAF with a filter of 5 coef. and 3 redundant
[W,w,x,d,y,e,p]=init_tdftaf(5,3); 
% Initialize a TDLMS filter for comparizon
[W1,w1,x,d,y1,e1,p1]=init_tdlms(5);

Figure 4.19: Learning curves for the TDLMS and TDFTAF when hardware failure is encountered.

%% Processing Loop
for (m=1:iter)   
   x = [xn(m,:); x(1:end-1,:)];  % update the input delay line
   d = dn(m,:) + 1e-3*rand;      % additive noise of var = 1e-6 
   % call TDFTAF and TDLMS to calculate the filter output, 
   % estimation error and update the coefficients. 
   [W,y,e,p,w]     = aspttdftaf(x,W ,d,0.05,p ,0.98,'fft');
   [W1,y1,e1,p1,w1] = aspttdlms(x,W1,d,0.05,p1,0.98,'fft');
   % save the last error sample to plot later
   en(m,:)  = e;  en1(m,:) = e1;     
   if (m > 2000), W(3) = 0.0; W1(3) = 0.0; end  % memory failiar
   if (m > 3000), W(4) = 1.0; W1(4) = 1.0; end  % memory failiar    
end;
% display the results
eb  = filter(0.1, [1 -0.9], en  .* conj(en ));
eb1 = filter(0.1, [1 -0.9], en1 .* conj(en1));
subplot(2,2,1);plot(10*log10(eb1  )); grid
subplot(2,2,2); plot(10*log10(eb  )); grid

Running the above script will produce the graph shown in Fig. 4.19. The left side graph of the figure shows the learning curve of the TDLMS and the right side graph shows the learning curve of the TDFTAF. It is clear that the TDFTAF can recover after a failure while the TDLMS can not.

Remarks

• aspttdftaf() supports both real and complex data and filters. The adaptive filter for the complex TDFTAF algorithm converges to the complex conjugate of the optimum solution.
• aspttdftaf() does not update the input delay line for $x(n)$, this has been chosen to provide more flexibility, so that the same function can be used with transversal as well as linear combiner structures. Delay line update, by inserting the newest sample at the beginning of the buffer and shifting the rest of the samples to the right, has to be done before calling aspttdftaf() as in the example above.
• aspttdftaf() not only supports standard transformations such as FFT, DCT, and DST, but also user-defined transformations. To use this feature, provide your transformation in two separate functions, one for the forward and the other for the backward transformation. For example if you implement a forward transformation in the file xyz.m you should implement its inverse transformation in the file ixyz.m and call aspttdftaf with parameter T='xyz'. Care should be taken in scaling the transformation coefficients to ensure that the time-domain filter coefficients have the correct values.

Algorithm

aspttdftaf() performs the following operations

• Calculates the transformation of $\vx (n)$ and filters this through the filter coefficient vector $\vW (n-1)$ to produce the filter output $y(n)$.
• Calculates the error sample $e(n) = d(n) - y(n)$ and the input power vector $\vP (n)$
• Calculates the updated T-domain adaptive coefficients $\vW (n)$ and their inverse transformation $\vw (n)$ if required.

Resources

The resources required to implement the TDFTAF algorithm for a transversal adaptive FIR filter of $M$ coefficients, where $M = L + R$, in real time is given in the table below. The computations given are those required to process one sample. The complexity of the transformation T of length $M$ is indicated as $C(T)$ in the table below.

MEMORY	$4M + 4$
MULTIPLY	$6M + C(T)$
ADD	$4M+C(T)$
DIVIDE	$M + C(T)$

See Also

INIT_ TDFTAF, ASPTTDLMS.

Reference

[7] for an introduction to fault tolerant adaptive filters.