Int. J. Communications, Network and System Sciences, 2012, 5, 569-578 Published Online September 2012 (
Predictive FTF Adaptive Algorithm for
Mobile Channels Estimation
Qassim Nasir
Department of Electrical and Computer Engineering, University of Sharjah, Sharjah, UAE
Received January 27, 2012; revised March 9, 2012; accepted July 25, 2012
The aim of this research paper is to improve the performance of Fast Transversal Filter (FTF) adaptive algorithm used
for mobile channel estimation. A multi-ray Jakes mobile channel model with a Doppler frequency shift is used in the
simulation. The channel estimator obtains the sampled channel impulse response (SIR) from the predetermined training
sequence. The FTF is a computationally efficient implementation of the recursive least squares (RLS) algorithm of the
conventional Kalman filter. A stabilization FTF is used to overcome the problem caused by the accumulation of
roundoff errors, and, in addition, degree-one prediction is incorporated into the algorithm (Predictive FTF) to improve
the estimation performance and to track changes of the mobile channel. The efficiency of the algorithm is confirmed by
simulation results for slow and fast varying mobile channel. The results show about 5 to 15 dB improvement in the
Mean Square Error (Deviation) between the estimated taps and the actual ones depending on the speed of channel time
variations. Slow and fast vehicular channels with Doppler frequencies 100 Hz and 222 Hz respectively are used in these
tests. The predictive FTF (PFTF) algorithm give a better channel SIR estimation performance than the conventional
FTF algorithm, and it involves only a small increase in complexity.
Keywords: Mobile Channel Estimation; Fast Transversal Filter; Prediction; Adaptive Filtering Algorithms
1. Introduction
The time varying multi-path fading channel that exists in
mobile communications environment lead to severe In-
ter-symbol Interference (ISI). In order to achieve high
speed reliable communication, channel estimation is ne-
cessary to combat ISI [1]. Channel estimators estimates
SIR by periodically adjusting an adaptive linear filter ac-
cording to an algorithm so as to minimize the error between
the output of the channel estimator and the received sig-
nal [2,3]. There are two major families of adaptive algo-
rithms. The first family is around the stochastic gradient
or least mean-square (LMS) algorithm which works well
if the communications channel is fixed or slow time vary-
ing [4]. LMS is popular because of its low complexity,
which is 2N (N is the number of adaptive filter length)
and its robustness. For fast time varying mobile channel,
the performance of LMS tracking scheme is poor [4].
The second family is based on recursive least squares
(RLS) algorithm that minimizes a deterministic sum of
squared error [2]. The RLS algorithm is known to be
capable of performing better performance than LMS, but
suffers from computational complexity of O(N2) opera-
tions per symbol [5,6]. When channel estimator has no
prior knowledge of the channel, a algorithm gives better
convergence rate compared to that of LMS [2]. The RLS
computational complexity restrict its use, so a number of
fast RLS algorithms have been presented such as Fast
Transversal Filter (FTF) [7,8], and fast a posteriori error
sequential technique (FAEST) [9]. They reduce the com-
putational complexity from O(N2) to O(N) operations per
symbol by using shifting and avoiding matrix-by-vector
multiplications. This paper studies the application of the
improved FTF algorithm to mobile channel estimation. A
lower computational complexity FTF has been introduced
in [10] which reduces the computation to O(7N).
The FTF algorithm in its original form is known to ex-
hibit an unstable behavior and a sudden divergence, due to
accumulation of roundoff errors in finite precision com-
putation [11]. Methods to overcome these roundoff errors
have been suggested in [12-14]. These introduce a limit
on a particular parameters in the algorithm which de-
grade the tracking ability of the FTF [12]. A numerically
stable FTF algorithm using redundancy in the calculation
of certain parameters and feedback of numerical errors is
suggested in [14]. FTF with “leakage correction” stabili-
zation method to overcome the roundoff error accumula-
tion is used in this paper, and a one-step prediction is in-
corporated into the FTF algorithm that takes into account
the rate of change in the estimate of the sampled impulse-
opyright © 2012 SciRes. IJCNS
Prediction is coupled with LMS to improve chhanel
estimation of the VHF radio links channel taps as in [15]
and for also for mobile channels estimation as in [16].
Shimamura et al. [17] applied the same technique to de-
sign estimation based equalizers. Multistep adaptive al-
gorithm has been presented by Gazor as Second Order
LMS (SOLMS) for slow time varying channel to im-
prove the tracking capabilities when some prior informa-
tion is available on the time variation of the channel [18].
To track time varying channels, he applied a simple
smoothing on the increments of the estimated weights to
estimate the speed of the weights. The estimated speed is
then used to predict the weights of the next iteration [18].
In this paper stabilized FTF with degree-1 Least Square
(LS) fading expanded memory prediction (Predictive
FTF-PFTF) is proposed for mobile channel estimation.
The prediction technique in [19] is applied to update the
estimates of the sampled impulse response (SIR) of mobile
The performance of conventional FTF, PFTF is dem-
onstrated by simulations. The results show that PFTF
provides superior steady state performance relative to the
conventional FTF.
2. FTF Algorithm for Mobile Channel
The mobile channel is assumed to follow Jakes fading
Model [20]. The Jakes fading model is a deterministic
method for simulating multi-path fading channels. The
model assumes that multiple rays arrive at a mobile re-
ceiver with uniformly distributed arrival angles (αn).
Every ray experiences a Doppler shift of fd = fmcos(αn),
where mc
vf c, v is the speed of the mobile receiver,
fc is transmitter carrier frequency, c is the speed of light
=3 10 m
The fading in each path of the channel follows Rayleigh
distribution and has U-shaped power spectral density as
given by Jakes [20].
()= ,
fff mm
ff f
=,,,yy y
The relative strength of the paths has assumed to have
an exponential power delay profile. For simulation pur-
pose, the mobile channel is modeled as three tap finite
impulse response (FIR) filter with delay between succes-
sive filter taps is assumed to be symbol period. The filter
taps or coefficients, Yi, are time varying and generated as
complex Gaussian according to the Jakes model for fad-
ing channel simulator [20]. The performance of proposed
channel estimator algorithm is evaluated for doppler fre-
quencies of 100 Hz and 222 Hz, corresponding to a ve-
hicular channels with speeds of 54 km/hr and 120 km/hr
Assume that Si is the transmitted sequence (assumed
stationary), Yi is channel sampled impulse response, ni is
the noise, ri is the received symbol, i is the i-th esti-
mate of the received symbol and i is the estimate of
the channel impulse response. All of the above quantities
are measured at iT time instant, where T is the sampling
time. The received signal (ri) is given by
where ,0,1, 1ii iN
i, and Si = [si, si–1, ···,
siN]. Yi, Si are N component vector, where N is the
number of paths in the multi-ray mobile channel. Si is a
pseudo-random signal with values of either +1 or –1. The
channel output signal is corrupted by an additive white
Gaussian noise (AWGN), ni, with variance σ2 and zero
mean, which is assumed to be uncorrelated to Si. Adap-
tive digital filter can be used to estimate the sampled
channel impulse response. It consists of Finite Impulse
Response (FIR) filter with variable tap weights. These
tap weights are adjusted according to FTF method of
updating weights as shown in the estimator block dia-
gram in Figure 1.
The conventional FTF algorithm forms an estimate of
the received sample i
. The estimator next forms the
error signal ei. The estimated channel sampled impulse
i is obtained recursively in such a way that
the cumulative squared error measure ci is minimized
The quantity ci is the cumulative sum of the weighted
squared errors. The parameter λ is a real-valued constant
in the range 0 to 1. λ is a weighting factor that introduces
an exponential window into the processed samples and is,
therefore, sometimes called the fade factor or the for-
Figure 1. Mobile channel stimator block diagram. e
Copyright © 2012 SciRes. IJCNS
Q. NASIR 571
iii1 i
YY )
k, is the Kalman gain vecto
n estimate of the sampled impulse-
ivation of fundamental fast trans-
explain this diver-
ng factor for the filter. It is similar to pre-window
except that one fixed λ slightly less than unity to track
time variations.
Y is determined recursively as in [7].
k (4
r. FTF which will be
used inis paper as a recursive computation of Kalman
gains shows a complexity of O(N) where N is the number
of taps of the channel ( number of mobile channel rays in
this paper) [7]. The FTF algorithm uses four transversal
filters in order to obtain the channel estimate [7,8] as
shown in Figure 2.
One filter gives a
sponse of the HF channel. The other three filters, called
the forward predictor filter, the backward predictor filter,
and the gain transversal filter are used in the estimation
of the Gain Transversal Filter gain vector (
k, in (4)).
For each of the four filters an estimation error is first
evaluated followed by the updating of the tap coefficients
(tap gains) of the filter. All of the four filters share the
same input data vector. The complete derivation of the
algorithm is beyond the scope of this paper and is given
elsewhere [2] and [7].
In [2] and [7], a der
rsal filter equations comes to a 7N fast RLS algorithm
for system identification. The prediction part of the algo-
rithm uses a system of four different filters that are cou-
pled by the recursions A, B are, respectively, forward
and backward prediction error filters, and is K is Gain
Transversal Filter. αi, and βi are real valued scalars rep-
resent the weighted sum of squares of forward and back-
ward prediction errors. γi is a real valued scalar which
gives a measure of error in adjustment of gain transversal
filter weights.
3. Stabilized FTF Algorithm
Four main reasons can be given to
gence: erroneous or approximate equation (inclusion of
Figure 2. FTF estimator transversal filters components.
de to stabilize the FFT by rescue
r γ(n)
e forgetting factor), ill conditioning of the compute
correlation matrices, effects of the suboptimal initializa-
tion procedure, and accumulation of finite precision er-
rors [21]. There exits a tradeoff exists in the selection of
the forgetting factor λ. Decreasing λ stabilizes the RLS
algorithm, however, at the cost of increasing noise due to
round-off error [21].
Attempts were ma
ethods [23]. [23] has introduced a rescue method that
effectively monitors the rescue variable until a point just
prior to the sign reversal, and then rescues the algorithm
by restarting with a weighted initial condition. Alterna-
tive methods for stabilizing the FTF algorithm have been
introduced in [22-25]. These algorithms use a multiplica-
tive leakage factor (v1) in the forward and backward pre-
dictor updates, such that the numerical errors associated
with their calculations decay to zero over time. Table 1
shows the FTF algorithm with leakage correction.
The algorithm computes the convergence facto
rectly using the normalized Kalman gain vector
Table 1. FTF algorithm with leakage correction.
Stabilized FTF No. Multi.
nn n
 
rn nn
1 + 1(÷)
 
 
vr n
vn vrn
 
2N + 1
 
 2
AnAn1k1 + 1
 
kk Bn1
  N + 1
 
Snk N + 1 (÷)
=bnn n
 
 2
=vvbnBnBn 1kn + 1
 
SnYn1 N
 
YY k
Total 11N + 14 + 2 (÷)
Copyright © 2012 SciRes. IJCNS
aput signal vector X(n). The mkage
Toerformance of FTF algorithm for track-
nd inultiplicative lea
factor (v1) has to be in the rage 0 v1 λ for stable op-
eration. This algorithm has O(11N) computational com-
plexity if leakage is employed at each time instant. While
simulations in [25] indicate the useful behavior of the
new stabilized algorithm. [24] analyze the stabilized FTF
algorithm and show that the FTF algorithm employing
the leakage-based update in Table 1 is numerically stable
if v1 is chosen in the range 0 < v1 < λ. Computer simula-
tions indicate the level of accuracy and show the useful-
ness of the stabilized FTF algorithm with leakage correc-
tion to track mobile channel estimation.
4. Proposed Predictive FTF (PFTF)
improve the p
ing time varying channel a prediction scheme is used. In
[19], so called “degree-1 Least Square fading memory
prediction” was employed to take a priori information
about the channel into the estimation scheme. The meth-
od of least square fading memory prediction is based on
the fact that a better prediction of
Y from the se-
quence of vectors
Y, ···, is otained by deter-
mining the set of n + 1 polomials of given degree (0, 1
or 2) each of which gives the LS fit to the components in
the corresponding locations in the vectors
Y, ···,
and then using the values of the polynomial at tim
t = (i + 1)T to determine the i-th component of
st f
ve shown that degree-1 polynomial
Each chosen polynomial is such that it gives the beit
to the sequence of past measurements, in the sense that
the exponentially weighted sum of the squares of the pre-
diction errors is minimized, for the given degree of the
polynomial [26,27].
Extensive tests ha
filters generally give the best overall performance, and,
in spite of the additional coupling (feedback) introduced
here by using updated estimates in place of independent
measurements, the technique substantially improves the
overall performance of the estimator, without any sign of
instability. Further details of the polynomial filters are
given elsewhere [26,27].
Thus, it behaves as a coefficient prediction filter. So,
FTF with LS expanded fading memory prediction algo-
rithm (PFTF) which is proposed in this paper to improve
mobile channel estimation is given by the following set
of equations [16,26,27]:
 
1 i
i1 ii
where α = (1 – θ2) and β = (1 – θ2) are real-valued scalars,
n by equation 5, for use with the FTF
ons were carried out to com-
conventional FTF, proposed
and θ is the smoothing constant (should be between 0
and 1) that controls the forgetting amount of the past in a
compromise with an accurate estimate. θ has to be tuned
depending on signal to noise ratio (SNR) and channel
behavior (speed of variation). PFTF algorithm assumes
that the sampled impulse-response of the channel varies
linearly with time.
Computer-simulation tests, on the accuracy of the one
step prediction give
gorithm, have shown a useful improvement in the per-
formance of the channel estimator without any sign of
instability. The additional complexity is only 2N opera-
tions per symbol.
5. Simulation R
Extensive computer simulati
pare the performance of the
predictive FTF (PFTF) for tracking mobile channels. The
input to the channel is a pseudo random sequence of +1,
–1 and white Gaussian noise of different variances is
used through out the test. In these simulations, slow and
fast vehicular mobile channels with doppler frequency of
100 Hz, and 222 Hz respectively is used (equivalent to
the mobile speed of 54 km/hr, and 120 km/hr at 2 GHz
carrier frequency and signal rate of 15 ksymbol/sec). The
mobile channels are assumed to have three paths. The
variations of theses taps against time is shown in Figure
3. The Signal to Noise Ratio (SNR) used is
10log 1
where σ2 is the noise variance. Each
transmission burst consist of 10000 symbo
rror (MSE) between the estimated chan-
nel taps and the actual once is obtained as average of 10
independent trials. The MSE is a measure of actual error
in channel estimation. During the first 500 of these tests,
the estimator is in startup, so no measurements is done s
it is in a transient period. MSE is defined as
ls and the
Mean Square E
100000 2
MSE=10log 
Figure 4 shows and for SNR = 40 dB a
mobile channel, the conventional and stabilized FTF
5 and 6.
othing constant)
nd fast varying
rformance. It is clear that and after few thousands of
received symbols, the unstabilized estimators got a di-
vergence operation when used for such channels.
The MSE has been collected for different values of λ
(weighting factor) and SNRs is shown in Figures
e purpose of these tests is to collect the optimum val-
ues of λ. These values which correspond to minimum
MSE will be used in comparisons with PFTF perform-
ance. It is clear that optimum values of λ decrease as the
speed of channel variations is increases.
Using these optimum values, the MSE of PFTF is
plotted against different values of θ (smo
shown in Figures 7 and 8. The optimum value of θ
depends on the input SNR and the speed of channel
variations. The optimum value for λ and θ will be used
Copyright © 2012 SciRes. IJCNS
Copyright © 2012 SciRes. IJCNS
Figure 3. Mobile channel taps weights variations according to Jakes’ Model.
St Stabilzed
Figure 4. Stabilized and un-stabilized FTF channel estimation performance.
Figure 5. FTF performance against weighting factor (λ) for slow channel.
Figure 6. FTF performance against weighting factor (λ) for fast channel.
Copyright © 2012 SciRes. IJCNS
Q. NASIR 575
Figure 7. PFTF performance against smoothing constant (θ) for slow channel.
Figure 8. PFTF performance against smoothing constant (θ) for fast channel.
Copyright © 2012 SciRes. IJCNS
Figure 9. PFTF and FTF transient channel estimation performance.
F igure 10. PFTF and FTF performance against SNR for slow channel.
Copyright © 2012 SciRes. IJCNS
Copyright © 2012 SciRes. IJCNS
Figure 11. PFTF and FTF performance against SNR for slow channel.
for performance comparisons.
longer than for FTF as shown in Figure 9, so it is rec-
ommend that the receiver starts with FTF for a few hun-
dreds and then switch to PFTF.
Figures 10 and 11 compares the performance of mobile
channel estimation using conventional FTF and PFTF
schemes. It can be seen that the steady state performance
of the proposed PFTF compared with the conventional
FTF is improved by about 5 dB for poor SNR (20 dB)
while it gains around 15 dB for a SNR of 50 dB. PFTF
achieve considerable improvements in mobile channel
estimation performance compared to conventional FTF,
this due to prediction used in PFTF within the channel
estimator operation.
6. Conclusion
Mobile Channel estimation based on FTF with degree-1
Least Square fading memory prediction (PFTF) has been
explored. Based on a steady state mean performance
PFTF offers a quite distinct benefit in comparison with
the conventional FTF—based method. Simulation results
show that under the well accepted Jakes’ fading channel
model, the PFTF based offers about 5 dB to 15 dB bene-
fit vehicular mobile channel estimation over FTF based
algorithm when SNR is 20 dB and 50 dB respectively. It
is shown that the algorithm has the capability of tracking
le channels. Also PFTF
does not add any substantial computation complexity.
[1] J. G. Proakis, “Digital Communications,” McGraw Hill
Inc., Boston, 1995.
[2] S. Haykin, “Adaptive Filter Theory,” 3rd Edition, Pren-
tice Hall, Upper Saddle River, 1996.
[3] A. Benveniste, M. Metivier and P. Priouret, “Adaptive Al-
gorithms and Stochastic Approximation,” Springer-Ver-
lag, New York, 1990.
[4] L. Lindbom, A. Ahlen, M. Sternad and M. Falkenstrom,
“Tracking of Time-Varying Mobile Radio Channels. I.
The Wiener LMS Algorithm,” IEEE Transactions on Com-
munications, Vol. 49, No. 12, 2001, pp. 2207-2217.
The setup time for PFTF is slow and fast time varying mobi
[5] E. Eleftheriou and D. Falconer, “Tracking Properties and
Steady-State Performance of RLS Adaptive Filter Algo-
rithms,” IEEE Transactions on Acoustics, Speech and
Signal Processing, Vol. 34, No. 5, 1986, pp. 1097-1110.
[6] S. F. A. Shah and Q. Nasir, “Tracking of Mobile Fading
Channels by Predictive Type RLS Algorithm,” Interna-
tional Symposium on Wireless Systems and Networks,
Dhahran, 24-26 March 2003.
[7] M. Cioffi and T. Kailath, “Fast Recursive Least Squares
Transversal Filters for Adaptive Filtering,” IEEE Trans-
actions on Acoustics, S
32, No. 2, 1984, pp. 304-337.
peech and Signal Processing, Vol.
[8] J. M. Cioffi and T. Kailath, “Windowed Fast Transversal
Filters Adaptive Algorithms with Normalization,” IEEE
Transactions on Acoustics, Speech and Signal Processing,
Vol. 33, No. 3, 1985, pp. 607-625.
[9] G. Carayannis, D. Manolakis and N. Kalouptsidis, “A Fast
Sequential Algorithm for Least Squares Filtering and Pre-
diction,” IEEE Transactions on Acoustics, Speech and
Signal Processing, Vol. 31, No. 6, 1983, pp. 1394-1402.
[10] M. Arezki, A. Benallal, A. Guessoum and D. Berkani, “Im-
provement of the Simplified FTF-Type Algorithm,” Jour-
nal of Computer Science, Vol. 5, No. 5, 2009, pp. 347-
[11] J. M. Cioffi, “Limited Precision Effect in Adaptive Fil-
ransactions on Circuits and Systems, Vol.
pp. 1097-1100.
tering,” IEEE T
34, No. 7, 1987,
[12] Y. H. Wang, K. Ikeda and K. Nakayama, “A Numerically
Stable Fast Newton-Type Adaptive Filter Based on Order
Recursive Least Squares Algorithm,” IEEE Transactions
on Signal Processing, Vol. 51, No. 9, 2003, pp. 2357-
2368. doi:10.1109/TSP.2003.815357
[13] J. L. Botto and G. V. Moustakides, “Stabilization of Fast
RLS Transversal Filters,” Institute de Recherche en In-
formatique et en Automatique, Paris, 1986.
[14] D. T. M. Slock and T. Kailath, “Numerically Stable Fast
Recursive Least-Squares Transversal Filters,” Proceed-
ings of International Conference on Acoustics, Speech,
and Signal Processing, New York, 11-14 April 1988, pp.
[15] A. P. Clark anl Estimation for an
HF Radio Link,”
d S. Hariharan, “Channe
IEEE Transactions on Communications
Vol. 37, No. 9, 1989, pp. 213-218. doi:10.1109/26.35371
[16] Q. Nasir, “Predictive LMS for Mobile Channel Tra
ing,” Journal of Applied Sciences, Vol. 5, No. 2, 2005, pp.
337-340. doi:10.3923/jas.2005.337.34
C. F. N. Cowan, “Equali-
zation of Time-Variant Communications Channels via
Adaptive Algorithms
nments,” IEEE Tran-
[17] T. Shimamura, S. Semnani and
Channel Estimation Based Approaches,” Signal Process-
ing, Vol. 60, No. 2, 1997, pp. 181-193.
[18] S. Gazor, “Prediction in LMS-Type
for Smoothly Time Varying Enviro
sactions on Signal Processing, Vol. 47, No. 6, 1999, pp.
1735-1739. doi:10.1109/78.765152
[19] A. P. Clark, “Channel Estimation for an HF Radio Link,”
IEEE Proceedings of Communicatio
Processing, Vol. 128, No. 1, 1981, p
ns, Radar and Signal
p. 33-42.
[20] W. C. Jakes, “Microwave Mobile Communication,” Wiley,
New York, 1974.
[21] S. M. Kuo and L. Chen, “Stabilization and Implementa-
tion of the Fast Transversal Filter,” Proceedings of the
32nd Midwest Symposium on Circuits and Systems, Cham-
paign, 14-16 August 1989, pp. 1139-1142.
[22] D. Lin, “On Digital Implementation of the Fast Kalman
Algorithms,” IEEE Transactions on Acoustics, Speech
and Signal Processing, Vol. 32, No. 5, 1984, pp. 998-
1005. doi:10.1109/TASSP.1984.1164427
[23] E. Eleftheriou and D. Falconer, “Restart Methods for
Stabilizing FRLS Adaptive Equa
HF Transmission,” IEEE Globa
lizer Filters in Digital
l Communications Con-
ference, Atlanta, 26-29 November 1984.
[24] J. K. Soh and S. C. Douglas, “Analysis of the Stabilized
FTF Algorithm with Leakage Correction,” Conference Re-
cord of the Thirtieth Asilomar Conference on Signals,
Systems and Computers, Pacific Grove, 3-6 November
1996, pp. 1088-1092. doi:10.1109/97.388912
[25] S. Binde, “A Numerically Stable Fast Transversal Filter
with Leakage Correction,” IEEE Signal Processing Let-
ters, Vol. 2, No. 6, 1995, pp. 114-116.
[26] N. Morrison, “Introduction to Sequential Smoothing and
Prediction,” McGraw Hill, Boston, 1969.
[27] E. Brookner, Tacking and Kalman Filtering Made Easy,”
John Wiley and Sons Inc., Hoboken, 1998.
Copyright © 2012 SciRes. IJCNS