# Blind Feedforward Timing Estimation for Constant-Modulus Signalling in Time-Varying Fading Channels

Authors: Shankar Prakriya
Journal: Journal of Electrical and Computer Engineering
 (2010)

---

## Abstract

A simple low-complexity algorithm is proposed for blind feedforward symbol timing estimation in time-varying flat-fading channels, assuming constant modulus
signalling. Its important properties are brought out using asymptotic analysis. It is shown that at high Signal-to-Noise Ratios (SNRs), the algorithm results in a timing estimate with negligible bias. It also has a Mean-Square-Error (MSE) performance that is superior for short data records and small roll-off factors to that of the Square-Law-(SQL-) and the CycloStationarity-(CS-) based algorithms available to date. Computer simulations are presented to demonstrate effectiveness of the algorithm.


---

## Body

## 1. Introduction

All communication receivers require accurate symbol timing recovery to provide high data rates. In dynamic environments, use of training sequences for timing estimation is impractical, and blind algorithms [1–7] are preferred. Of these, the SQL algorithm of [4] (which performs poorly for small roll-off factors), the logarithmic nonlinearity-based algorithm (LOGN) of [2], and the recently proposed Constant-Modulus (CM) algorithm [1] are blind feedforward algorithms with low complexity. Further, the complexity involved in the search can be avoided by an approximate Fourier Series (FS) method [1]. In many applications like Wireless Sensor Networks (WSNs), algorithms withlow-complexity are often desired.Most blind feedforward timing estimation algorithms proposed to date assume adeterministic channel and cannot be used for time-varying flat-fading channels assumed in this paper. This problem is of practical importance these days because of increased mobility. The SQL algorithm is an exception and can be applied to such channels, though its properties in such channels have not been investigated so far. The constant modulus algorithm of [1] can indeed be applied in quasistatic fading channels (though it was proposed for deterministic channels). However, it cannot be applied to time-varying fading channels. The Conditional Maximum Likelihood estimator of [6] is applicable to only to static flat fading channels, and not to time-varying fading channels. This is also true of the algorithm developed in [5]. Despite its practical importance, there has been little research effort to develop blind feedforward algorithms for such links. Theonly exception is the cyclostationary-based algorithm [7], that is specifically designed to work with time-varying fading channels. However, it performs quite poorly with low excess bandwidth signals commonly used today, and for small data records. In this paper we propose a novel low-complexity CM-based blind algorithm for estimation of the timing and demonstrate its effectiveness in such links for small excess bandwith (small roll-off factors), and small data records. We study its asymptotic properties.


## 2. Problem Formulation

Letan denote the i.i.d complex CM (|an|2=1) transmitted symbols. In a typical communications receiver, the baseband received signal y(t) (after the receiver matched filter) is given by
(1)y(t)=Ah(t)ejωt∑n=-∞∞ang(t-τ-nT)+w(t),
where A is the gain, h(t) is the (time-varying) fading channel, g(t) is the convolution of the transmitter's signaling pulse and the impulse response of the receiver filter, T is the symbol interval, τ is the delay that is to be estimated, and w(t) the Gaussian noise after the receiver matched filter. We assume the following.(AS1): the basic pulse used is Nyquist so that g(0)=1 and g(lT)=0 for l≠0.The received signal (after receiver match filtering) sampled with a time offset ofτ̃ is given by(2)y(kT+τ̃)=Aejω(kT+τ̃)hk∑n=-∞∞ang(kT+τ̃-τ-nT)+w(kT+τ̃)=Aejω(kT+τ̃)hk(akg(τ̃-τ)+ck,τ̃-τ+w(kT+τ̃)),
where hk=h(kT+τ̃), w(kT+τ̃) is white Gaussian because of  (AS1), and ck,τ̃-τ=∑n≠kang(kT+τ̃-τ-nT)=ck,ϵ is the weighted sum of adjacent symbols that arises due to sampling at the improper instant (ϵ=τ-τ̃ denotes the error in timing). Clearly, ck,ϵ is approximately (circular) Gaussian by virtue of the central limit theorem. Notice that gϵ=g(τ̃-τ) takes the maximum value of 1 when τ̃=τ, or ϵ=0 (in which case ck,τ̃-τ=ck,ϵ=0). Notice that when the excess bandwidth is large, the variance σc,ϵ2 of ck,ϵ is small (the impulse response decays faster for large roll-off factors, as is well known). Also, when the roll-off factor is small, σc,ϵ2 increases sharply with ε for small ϵ. We will cosider the following.(AS2): the channel does not change significantly within two symbol durations (h(kT+τ̃)=h(kT+T+τ̃)=hk).With slow channel fading, this is a reasonable assumption and is commonly made.With the popular Jakes model,rh(m)=E{hkhk-m*}=J(2πfDmT), where fD denotes the doppler frequency, and J() denotes the zeroth-order Bessel function of the first kind. Assumption (AS2) holds when fDT≪1, which is the case with slow fading. Using computer simulations, we establish later in this paper that the algorithm performs well for slow to medium fading channels, but not in the case when the channel changes significantly from one symbol interval to the next. This is not a serious limitation however, and the proposed algorithm will find wide applicability in practical links. To the best knowledge of the author, this is the only work other than [7] that specifically addresses the problem of timing estimation in time-varying fading channels. As noted already, all previous works have assumed deterministic or static fading channels.The SQL estimator uses the cost function(3)ΓSQL(τ̃)=∑k=0Lo-1|y(τ̃+kT)|‍2,
where Lo is the observation interval. The recent CM algorithm [1] minimizes the cost function
(4)ΓCM(τ̃)=∑k=0Lo-1(|y(τ̃+kT)|-Ã)2,
where Ã=(1/Lo)∑k=0Lo-1|y(τ̃+kT)|. In [1], only determinsitic channels were considered. The algorithm is not applicable for time-varying fading channels. Since y(t) is CS, autocorrelation r(t,Δ)=E{y(t)y*(t-Δ)} is periodic, with the FS coefficient at cycle frequencies α given by rα(α). It has been shown in [7] (CS algorithm) that the frequency offset can be estimated using the phase of rα(Δ)rα(-Δ), and the timing estimate subsequently as the phase difference between rα(Δ) and r-α(Δ) at various Δ. This requires the cyclic correlations to converge, and the roll-off factor to be large so that the nonzero cycle frequency components are significant. In addition, the algorithm first estimates the frequency offset, and this estimate is used to obtain an estimate of the timing in a two-step procedure. The proposed algorithm on the other hand estimates the timing independent of the CFO.


## 3. Estimation Algorithm

The following cost function is maximized by the timing estimation algorithm proposed in this paper:(5)ΓCMTV(τ̃)=-1Lo∑k=0Lo-1(|y(kT+τ̃)|2-|y(kT+T+τ̃)|2)2.
In what follows, we briefly study the properties of an estimator based on the above cost function. While a finite sample analysis is analytically difficult, significant insight into properties of the estimator can be obtained from an asymptotic analysis. Denote y(kT+τ̃) by yk,τ̃. It can be seen that the squared magnitude of the received signal is given by
(6)|yk,τ̃|2=A2|hk|2(gϵ2+|ck,ϵ|2+(akck,ϵ*+ck,ϵak*)gϵ)+|wk|2+wkAhk*e-jω(kT+τ̃)(ak*gϵ+ck,ϵ*)+wk*Ahkejω(kT+τ̃)(akgϵ+ck,ϵ).
Insight into the asymptotic performance of the squared-law algorithm can be obtained from the above expression. For large Lo, ΓSQL≈A2σh2(gϵ2+σc,ϵ2) in the absence of noise (where σh2=rh(0) since hk is assumed to be zero mean). This explains the major failing of the square law algorithm. Clearly, when the excess bandwidth is small, the peak of the cost function will occur at the correct point. However, when the excess bandwidth is large, the baud-rate sampled pulse g(t) is aliased. This results in bias for large excess bandwidths. However, σc,ϵ2 is small for large excess bandwidth so that the Mean-Squared Error (MSE) in the estimate is small. For the new cost function, it can be seen that
(7)(|yk,τ̃|2-|yk+1,τ̃|2)2≈A42|hk|4(-2(|ck,ϵ|2|ck+1,ϵ|2)+(|ck,ϵ|2+|ck+1,ϵ|2)gϵ2)+2A2|hk|2(|wk|2(gϵ2+|ck,ϵ|2)+|wk+1|2(gϵ2+|ck+1,ϵ|2))+termswithzeromean,
where σw2 is the variance of the noise, and the higher-order terms involving ck,ϵ and the noise wk are ignored (assuming high SNR). The second term in the first line of the above equation has a factor of A4, and this ensures good MSE performance of the algorithm.We assume a small offset ϵ, exploit the Gaussian nature of hk, and write the cost function as
(8)ΓCMTV≈4A4σh4E{|ck,ϵ|2|ck+1,ϵ|2}-4σc,ϵ2gϵ2A4σh4-4A2σh2σw2gϵ2.
First consider the case when there is no noise so that σw2=0 (so that only the first two terms in the above expression are relevant). Notice that the cost function is zero when ϵ=0. To establish that the unbiased nature of the estimator, we only need to verify that it is not greater than zero for other ϵ (in other words, it is negative for other ϵ). Since ck,ϵ is circular Gaussian as noted already, E{|ck,ϵ|4}=2(E{|ck,ϵ|2})2. From the Cauchy-Schwartz inequality, |E{XY}|2≤E{|X|2}E{|Y|2}. Using this, we have |E{|ck,ϵ|2|ck+1,ϵ|2}|≤2σc,ϵ4. Also, in the range ϵ∈[-T/2,T/2], gϵ2≫σc,ϵ2 or σc,ϵ2gϵ2≫σc,ϵ4, so that σc,ϵ2gϵ2≫E{|ck,ϵ|2|ck+1,ϵ|2}. This implies that the second term is much larger in magnitude than the first, so that the cost function is maximum only when ϵ=0, and there is no bias. This implies that a search-based algorithm will always estimate the timing without bias. A careful look at the cost function also reveals that the cost always decreases with an increase in ϵ for ϵ∈[-T/2,T/2]. This is true because of the fact that the first term is negligible as compared to the second term, and the product of σc,ϵ2 and gϵ2 in the second term is zero at ϵ=0 and continuously decreases for ϵ in the range. This once again is because of the fact that gϵ2≫σc,ϵ2 for all ϵ in the range. For this reason, the commonly used first-order method [1] can be used with this algorithm, thereby reducing the complexity, though with loss in performance.Now consider the case when there is additive noise (σw2>0). Neglecting the first term involving higher-order products of ck,ϵ, we get
(9)ΓCMTV≈-4gϵ2A2σh2σw2[SNRσc,ϵ2+1],
where SNR=A2σh2/σw2 (the symbols are of unit variance, and the pulse of unit energy). The above cost function is negative of the product of two terms, one that falls with ϵ, and another (within the square brackets) that rises quite sharply with ϵ (with a minimum of 1), especially at high SNRs. It is easy to verify that the minimum is no longer at ϵ=0, and there is always a bias in the estimation. However, this bias is clearly small because of the high slope of the term in the square brackets. Also, as SNR increases, this bias decreases.


## 4. Performance Analysis

Performance of proposed algorithm is compared to that of the SQL and CS algorithms (using an oversampling rate of4) in this section. The proposed and SQL algorithms are assumed to use the FS approximation to avoid a search [1]. In all the simulations, the true delay is assumed to be a random variable uniformly distributed between -T/2 and T/2. Observation windows of length 50 and 100 are used. (Lo=50 or Lo=100). A time-varying flat fading channel with fDT=0.01 is assumed unless stated otherwise.Figure1 depicts the MSE in the estimation of τ of all three algorithms for various SNRs assuming a roll-off factor of 0.1. It can be seen that the proposed algorithm yields performance that is far superior to the other two in all cases, and performance of the CS algorithm is unacceptable for these data record sizes and for the small roll-off factor used (it requires at least 400–500 symbols, and 50 percent excess bandwidth to yield comparable performance). Figure 2 shows that the proposed estimate has a small bias. Further, this bias decreases with an increase in length of the observation window. Figure 3 depicts the MSE versus the roll-off factor for an SNR of 20dB for the proposed and the SQL algorithm, assuming a time-varying fading channel with fDT=0.03. We note that the proposed algorithm is more insensitive to roll-off factor than the SQL algorithm, which is an important advantage.Figure 1
MSE versus SNR of proposed, CS and SQL algorithms for roll-off factor of 0.1.Figure 2
Bias versus SNR of proposed and SQL algorithms.Figure 3
MSE versus roll-off factor for proposed and SQL algorithm.


## 5. Conclusions

A simple low complexity blind feedforward timing estimation algorithm is proposed for time-varying fading channels that exploits the constant modulus property of the transmitted symbols and is advantageous as compared to existing algorithms.



---

*Source: 620789-2010-03-15.xml*