Frequency tracking by method of least squares combined with channel estimation for OFDM over mobile wireless channels

To track frequency offset and time-varying channel in orthogonal frequency division multiplexing (OFDM) systems over mobile wireless channels, a common technique is, based on one OFDM training block sample, to apply the maximum-likelihood (ML) algorithm to perform joint frequency tracking and channel estimation employing some adaptive iteration processes. The major drawback of such joint estimation techniques is the local extrema problem arising from the highly nonlinear nature of the log-likelihood function. This makes the joint estimation process very difficult and complicated, and many a time the results are not very satisfactory if the algorithm is not well designed. In this study, rather than using the ML algorithm, we shall apply the method of least squares (LS) for frequency tracking utilizing repeated OFDM training blocks. As will be seen, by using such an LS approach, the frequency offset estimation requires no channel knowledge. The channel state can be estimated separately after the LS frequency offset correction. This not only circumvents the local extrema complication, but also obviates the need for the lengthy adaptive iteration process of joint estimation thus greatly simplifies the entire estimation process. Most importantly, our technique can achieve excellent estimation performance as compared to the usual ML algorithms.

In orthogonal frequency division multiplexing (OFDM) communications over mobile wireless channels, after initial time and frequency acquisition, fine frequency offset and time variation of the channel state will continue to exist due to Doppler shift, instability of local oscillators, and multipath fading and hence must be continuously or frequently tracked [1]. To perform fine frequency tracking and channel estimation, the most widely adopted technique is the maximum-likelihood (ML) estimation algorithm. Usually, one OFDM symbol block is used as the training data. When using the ML technique to track frequency offset, one needs to have the channel knowledge. Likewise, to perform ML channel estimation, frequency offset estimation must be given. Therefore, to track both fine frequency offset and the channel state, a popular method is to alternately estimate the frequency offset and channel state by adaptive iterations. In the literature, there exist many proposed ML algorithms of joint frequency tracking and channel estimation for both linear modulation and OFDM systems [2-6]. A major difficulty is the local extrema or multiple solution complication arising from the highly nonlinear nature of the multi-dimensional log-likelihood function. As a result, some schemes of simplification or approximation are often used to help solve the problem [5,6]. In addition, complex algorithms must usually be accompanied to aid the tedious search of the global solution [2-6]. How well such algorithms are designed will greatly affect the global solution convergence performance. When the initial frequency offset is large (close to half the subcarrier spacing), it usually becomes rather difficult to achieve global solution convergence. Carefully observing the simulation results of most of the cited works above, we can perceive that, when the initial frequency offset exceeds ± 0.1 of the subcarrier spacing, the mean square errors (MSEs) or variances of both the frequency and channel estimators given in these works start to depart away from the Cramer-Rao bound (CRB) as signal-to-noise ratio (SNR) is increased. Thus, their tracking ranges are well below half or ± 0.5 of the subcarrier spacing. This is due to the less accurate results arising from the approximations and/or simplifications when initial frequency offset values become large. In [1], by using the linear minimum-mean-square-error (LMMSE) combiner to optimally combine frequency offset estimators based on single time slot pilot samples from a received time-domain OFDM block, they successfully circumvent the multiple solution difficulty and meanwhile achieve very satisfactory joint estimation performance with wide tracking range (up to half the subcarrier spacing). Moreover, in [1], the estimator MSE will not depart away from the CRB at large SNRs. However, their algorithm still requires the lengthy adaptive iteration process due to joint estimations. Since, as stated earlier, it is necessary to continuously or frequently perform tracking of frequency and channel state, the lengthy adaptive iteration process, which is time-consuming, should be highly undesirable.

In this article, rather than using the ML technique, we apply the method of least squares (LS) to perform fine frequency tracking utilizing repeated OFDM training blocks. Our LS formulation for frequency offset estimation will not require channel knowledge. Then, based on the frequency offset estimator thus obtained, channel estimation is readily performed. This way, not only the multiple solution complication due to nonlinearity of the log-likelihood function can be avoided, but also the need for lengthy adaptive iterations is obviated. Thus, the entire process becomes much simpler and faster. Most important, our estimator performance outperforms those of the existing ML techniques. However, it is to be noted that the advantages and superiority of our technique are achieved at the expense of data transfer rate reduction due to the use of repeated training blocks.

The article is organized as follows: Section 2 presents the signal and system model. Section 3 delineates our LS formulation for frequency tracking. Section 4 addresses the channel estimation techniques after frequency offset correction. Section 5 analyzes our estimation performances. Then, Section 6 presents simulation results. Performance comparisons will be made between our LS algorithm and the usual ML algorithms based on single training block. Finally, Section 7 draws conclusions.

Consider OFDM communications over mobile wireless channels. Assume time and frequency acquisitions have been completed. Due to Doppler shift, instability of the oscillators, and multipath fading, fine frequency offset and time variation of the channel state will continue to exist. Let x_n, h_n, and w_n, respectively, represent the discrete-time baseband data sample, channel impulse response (CIR), and noise sample at the nth time slot of a received time-domain OFDM block having the length of N sample units or T seconds. The fine frequency offset normalized to subcarrier spacing Δf = 1/T is denoted as δ. Then, discarding the cyclic prefix, the demodulated baseband received sample at the nth time slot can be expressed as

where * denotes convolution and y_n = x_n * h_n is the received noise-free data sample which can be expressed in terms of frequency-domain quantities as

where H_k and X_k are, respectively, the kth subcarrier channel frequency response (CFR) and transmitted data symbol or the discrete Fourier transform (DFT) of h_n and x_n. We have adopted the unitary DFT here for the signal data. Note that {w_n} are independent, identically distributed (i.i.d.) complex Gaussian random variables (RVs) with zero mean and variance and we shall use the familiar notation for convenience.

For frequency-selective channels, the discrete-time CFR is expressed as

where we have assumed the channel is causal and its length spans v data samples. The discrete-time baseband CIRs {h_m} are spatially uncorrelated. The DFT output at the receiver is given by

where . Apparently, {W_k} are i.i.d. Gaussian RVs. With the completion of initial frequency acquisition, we can reasonably assume that the maximum fine frequency offset is less than half the subcarrier spacing or δ < 0.5 [1-6].

We shall use P_k to denote training or pilot symbols to distinguish it from the data symbol X_k. To each transmitted block which is labeled as the initial block or 0th block, we append L identical blocks (i.e., N pilot symbols in each appended block are exact the same as those of the transmitted block). With this arrangement, the received sample of the nth time slot in the lth block can be denoted as

where is a complex Gaussian RV having zero mean and variance , and

In (6), we assume L is not so large that the channel fading remains unchanged at least over (L + 1) blocks. Define the vectors , , and with T denoting transpose. Using (6), we can rewrite (5) in vector form as

It is easy to see that the combined noise vector is a complex Gaussian random vector with mean 0 and variance . We can stack the vectors of (7) to obtain

We further define three N (L + 1) × 1 vectors , , and . Equation (8) can then be rewritten as

We can view (9) as an over-determined system of complex linear simultaneous equations in one complex variable x = e^j2πδ. Then, we can apply the method of LS to obtain the estimate of x as

where H denotes Hermitian transpose. Then, an estimate of δ can be found as

where Re(·) and Im(·), respectively, denote the real and imaginary parts. It is apparent that the range of given by (11) is ± 0.5 or half the subcarrier spacing, and it has no multiple solution problem, requires no channel knowledge and only takes a one step computation process without adaptive iterations. However, these advantages are not without cost. The price paid is that the estimator of (11) requires the use of more than one OFDM training blocks. This results in a reduction of system throughput or data transfer rate.

It is to be noted that (11) is based on the premise that fading remains unchanged over at least L + 1 OFDM blocks. In other words, we have assumed slow quasi-static fading. This implies that the maximum Doppler frequency must satisfy f_M = υf_c/c≪1/T corresponding to a mobile speed υ ≪ c/(f_cT), where c is the speed of light, T is one OFDM block length in seconds, and f_c is the carrier frequency in Hz. Taking an 802.11a standard with f_c = 5 GHz and Δf = 1/T = 312.5 kHz, this requires υ ≪ 67,500 km/h. Apparently, this requirement for slow quasi-static fading is easily met in practice. For example, if υ = 60 km/h, then f_M ≈ 10^-3/T which is one thousandth of an OFDM block, it is thus reasonable to assume fading to remain unchanged over several hundred OFDM blocks.

In many applications, channel may have fast time variations. Then, our algorithm may lose its advantage, viz., fast processing due to no need for iterations. In such cases, the LMMSE algorithm of [1], which is shown better than most other ML schemes in the literature, may be the best choice. However, if time variation is not so fast or is only moderately fast (in between fast and slow varying), our LS algorithm can be still quite useful as we can cope with the moderately fast time-varying environment by reducing the number of repeated blocks.

After the fine frequency offset has been corrected, the channel estimation can readily be performed. Here, both the methods of LS and the ML technique will be investigated for channel estimation.

4.1. LS channel estimation

Given , we can correct the offset by multiplying (5) by to obtain (before is fed to the DFT). If the estimate is of good accuracy, the estimate error will be very small. Then, after frequency offset correction, the kth subcarrier DFT output (during training mode) can be approximated as

where α_l ≡ π (2lN + N - 1)/N, , and we have used the approximations , , and p - k +Δδ ≈ p-k.

If the frequency offset correction were perfect (offset-free), then Δδ = 0 and (12) would reduce to

where stands for the offset-free DFT output. There are L + 1 equations in (13) and they form a system of simultaneous linear equations for one variable H_k and we can thus easily apply the method of LS to get the channel estimators as

where P_k = P_k[1,1,...,1]^T is an (L + 1) × 1 vector and .

In reality, perfect frequency offset correction is not very likely to happen. That is, it is not very likely to obtain the offset-free outputs of (13). The best one can do is to use the of (12). Thus, in practice, we shall take

Note that only one sample (the kth sample ) in each training block (frequency-domain OFDM block) has been selected to estimate H_k and there are L + 1 blocks resulting in only L + 1 samples used for the LS channel estimation. In order not to reduce data transfer rate too much, L is not to be too large. Thus, with the small number of L + 1 samples used, the LS estimator Ĥ_k is expected to perform not quite so satisfactorily, though perfectly workable. We will thus seek an alternative approach using the ML technique to be described next.

4. 2. ML channel estimation

To perform ML channel estimation, we first need to find the log-likelihood function in terms of the variables to be estimated. These variables must be independent of each other. We shall assume a frequency-selective Rayleigh fading channel of dispersion length v having the CIR vector h = [h₀, h₁,..., h_v-1]^T. Then {h_m, m = 0,1,...v} are uncorrelated and hence independent of each other. However, the CFRs {H_k, k = 0,1,..., N}, which are DFTs of {h_m}, are obviously correlated and hence dependent upon each other. Consequently, unlike the above case of LS channel estimation where CFR can be estimated directly due to the special one variable over-determined system formulation, here we must first obtain the ML CIR estimator ĥ from a log-likelihood function in terms of h from which we then get the CFR estimator Ĥ through DFT.

Now, assume that frequency offset has been corrected so that δ = 0. Using (5) and (6) with δ = 0, we can readily get

where is the offset-free noiseless received signal vector with P = diag{P₀, P₁,..., P_N-1} being a diagonal matrix and

Then, stacking L + 1 repeated blocks, we have

The log-likelihood function for (18) is given by

From (19), it can readily be shown that the ML estimate of h is given by

Training sequence with constant amplitude has been proven optimal for channel estimation [7]. Chu sequence [8], for example, falls onto this category. Using a Chu sequence {, m being any integer relatively prime to N} results in P^HP = I_N. Then, (20) can be simplified to

where the fact has been used. Note that, by using a Chu sequence, (21) can avoid the computation of matrix inversion given in (20). The estimate of the CFR vector H = [H₀, H₁,..., H_N-1]^T can be readily obtained as

Since all samples in each of the entire OFDM block are utilized in this ML estimation, we have used a total of N (L + 1) samples for this ML channel estimation. As a result, we expect that the ML channel estimator will outperform the previous LS channel estimator. Later in simulations, we shall make performance comparisons between the CFR estimators given by (15) and (22).

5.1. Frequency tracking performance

From (11), we see that . Then, using the fact that , we can readily show that, for high SNR and small estimate error ,

Note that is the noiseless received signal vector of the initial training block, with , n = 0,1,..., N-1 (see Equation (6)). For given and δ, we easily see that the mean . Hence, for small errors at high SNR, the frequency offset estimate is unbiased. Using (23), the variance or MSE of the estimate can be evaluated as

Note that the block signal power will increase with N. We have thus defined the block SNR as . We can see that for a given γ, as L and/or N are increased, the estimate gets better.

5.2. Channel estimation performance

5.2.1. Estimation by method of LS

We substitute (12) into (15) to get

whence, for given H_k and δ, the mean of Ĥ_k is

where we have used E[Δδ] = 0. Hence, for small offset errors at high SNR, the channel estimate is unbiased. Then, using (23), (24), and (25), we can readily calculate the channel estimator variance or MSE (at given H_k and δ) as

where

The overall average variance is defined as

Equations (26) to (29) give the theoretical mean and variance of the ML channel estimators when the frequency offset estimate is imperfect. From (27), we see that, with a given training sequence {P_k}, the channel estimate variance is a function of H_k. If frequency offset estimate were perfect and a Chu sequence had been used, we would get

5.2.2. Estimation by ML technique

With imperfect frequency offset estimate as most likely would be the usual case, we would actually have

where is the frequency offset estimate error which is very small and

and

Substituting (31) into (20), we can readily get

With E[Δδ] = 0, we can readily see from (34) that

Therefore, the estimator ĥ is also unbiased.

Defining Δh = ĥ -h, we can compute the covariance as follows:

Now using a Chu sequence such that P^HP = I_N, (36) reduces to

where y₀ has been defined earlier in Section 4 and as from (24). Note that if the estimate of frequency offset were perfect, i.e., E[Δδ²] = 0, we would have

and hence

This leads to

Comparing (30) and (40), it is apparent that the ML channel estimation outperforms the LS channel estimation.

In this section, we shall present various performance results of our LS frequency tracking combined with channel estimation in OFDM systems. Also included will be the QAM symbol error rate (SER) performance of an OFDM system employing our tracking algorithm in frequency-selective Rayleigh fading channels. Comparison will be made with the usual ML techniques based on one OFDM training block.

For a frequency-selective channel of dispersion length v = 9, we choose a given exponential power profile with normalized channel power, i.e., , Figure 1 gives the variance or MSE of the frequency offset estimator as a function of SNR γ for three values of L = 1,3,9 as obtained from Monte Carlo simulations as well as from the theoretical result of (24). We have used 64-point DFT (N = 64) and assume an actual frequency offset of δ = 0.2. From the figure, we see that the simulated and theoretical curves coincide well at high SNR values as expected since the theoretical result of (24) was derived based on high SNR values. Also incorporated in Figure 1 for comparison purpose is the CRB for the usual ML frequency estimator based on one OFDM block as the training sample as for [1] and other earlier cited ML algorithms employing adaptive iterations for joint frequency tracking and channel estimation. After LS frequency tracking, using the LS channel estimation for the same frequency-selective channel with the same offset δ = 0.2, Figure 2 gives the CFR estimator variance or MSE against SNR obtained from Monte Carlo simulations as well as from the theoretical results of (29) under imperfect frequency offset estimations for the same three L values. Also incorporated in Figure 2 for comparison is the CRB for the usual ML CFR estimator based on one OFDM block as the training sample. We see that this CRB lies in between the L = 3 and the L = 9 LS curves. Thus, roughly, we may need to use at least L = 6 to obtain better LS channel estimators when compared with the usual one-block-sample-based ML channel estimator. Then, Figure 3 presents the MSE versus SNR curves for the multiple-block-sample-based ML CFR estimator as obtained from Monte Carlo simulations as well as from the theoretical results of (37) under imperfect frequency tracking for L = 1,3,9. This time, we see that the multiple-block-sample-based ML channel estimators have MSEs lower than the CRB for the one-block-sample-based ML channel estimator as it should. Apparently, the ML channel estimator outperforms the LS channel estimator as predicted earlier by theory.

For the same frequency-selective channel system as for Figures 1, 2, and 3, the same performance curves are plotted in Figures 4, 5, and 6 for the case of δ = 0.48. As expected, with the larger initial frequency offset of 0.48, estimator performances are degraded. The degradations are especially pronounced at low SNR values as can easily be observed from the figures.

It is important to note that comparison of different algorithms may not be always fair due to different system conditions applied to different algorithms. Thus, making trade-off decisions between different algorithms may well be intuitional. Many a time, the intuitional decision is quite obvious and hence rather easy to make. In our cases here, it is certainly unfair to compare the CRB for an ML estimator based on one training block sample with the estimator MSE using multiple training block samples. Nonetheless, the key point here is, by avoiding adaptive iterations, we can achieve considerable time-saving and substantial process simplification, meanwhile accomplish the purpose of lower estimator MSE. In fact, one can also go to great lengths to apply the ML algorithm to perform the usual joint frequency tracking and channel estimation but using multiple training block samples. This will bring the CRBs down a little further than our estimator MSEs. But, such processes would be overly complex and much time-consuming, and hence prohibitively expensive to implement.

Next, we would like to examine the impact of our estimators on the system error rate performance. We shall take square 16-QAM signaling for the OFDM system over frequency-selective Rayleigh fading channels. As before, we again assume a channel length of v = 9 and an OFDM block length of N = 64 samples. Also, we choose an exponential channel power profile with normalized channel power. Define the received SNR for kth subcarrier as , where is the average transmitted data power, and the total average SNR as with . It can readily be shown that , where is just the block SNR defined earlier in Section 5. Then, for initial frequency offset of δ = 0.2, Figure 7 presents the Monte Carlo simulation results of SER versus average SNR for the OFDM system employing LS frequency tracking combined with channel estimation with L = 1 and L = 3. Both LS and ML channel estimations are tested. Also included in Figure 7 for comparison is the ideal system 16-QAM SER with perfect frequency synchronization and channel estimation. In fact the ideal QAM SER for an OFDM system over a Rayleigh fading channel can readily be derived in a closed form by using the moment generating function approach given in [9]. We shall not carry out the derivation here, which will carry us afar and take too much space but present the final result as follows:

where M = 16 has been used for our square 16-QAM signaling and . From the figure, we can see that the Monte Carlo results for LS channel estimations are slightly above the ideal SER result with the L = 3 curve being better as expected, while the Monte Carlo curves for the ML channel estimations almost coincide with the ideal SER curve as the differences are not easily detected by eye. This further confirms the fact that using ML channel estimation after frequency tracking is better than LS channel estimation. We have performed similar simulations for various other values of δ including values close to δ = 0.5 and found the results very much the same as given by Figure 7. This means, in so far as the SER performance is concerned, within the tracking range of half the subcarrier spacing, the estimators of our algorithm are robust against the frequency offset.

Finally, Figure 8 compares SER performances versus SNR between various algorithms under δ = 0.2 using QAM transmission over the same channel as given for Figure 7. To compare with the LMMSE algorithm of [1], we have used Version B which has a faster convergence speed and wider estimation range than Version A. In the comparisons, we take L = 1 for our algorithms, i.e., two repeated OFDM blocks are used for training. Thus, to be fair, we have also used two OFDM blocks as training data for the LMMSE [1] and the EM [5] algorithms so that same bandwidth efficiency is given for all algorithms under consideration. The simulation results show that our proposed algorithm using LS frequency tracking with ML channel estimator gives almost the same SER performance as those given by LMMSE and by the ideal case (i.e., perfect frequency tracking and channel estimation). While our algorithm using LS frequency tracking with LS channel estimation gives a slightly less SER performance. The EM algorithm given in [5] yields a very poor performance under δ = 0.2. Simulation results (not given here) show that the EM algorithm can only work when δ is very small (less than 0.02).

We note that the LMMSE has comparatively the best performance due to the additional iteration process which gives further refined results. Nonetheless, our algorithm using LS frequency tracking with ML channel estimation yields a comparable performance but without the iteration process. This saves considerable computation time and hence contributes the major advantage of our algorithm. Table 1 displays the computational complexity needed for various algorithms. The complexity is counted by the arithmetic operations of two real numbers. One complex multiplication is equivalent to four real multiplications. Also, some composite data matrices can be calculated in advanced and stored in memory before performing estimation algorithm. in (17) of [1], for example, can be pre-computed and stored in memory for later use in adaptive iterations. The needed arithmetic operations displayed in Table 1 exclude such situations. Moreover, S represents the number of iterative adaption needed in the proposed LMMSE algorithm [1]. Referring to the simulation results in [1], the number of iterations for achieving convergence for various values of CFOs is somewhere between 10 and 20. The reasonable value S for use in practice is thus a little more than 20.

As an example, we take S = 20 and v = N/4. Then, the LMMSE requires 40N² + 240N real multiplications, while the proposed LS frequency tracking with LS channel estimation needs N² + LN + 1 real multiplications, and the proposed LS frequency tracking with ML channel estimation takes only real multiplications. Notably, the proposed LS frequency tracking with ML channel estimation has the least complexity, while the LMMSE algorithm has the heaviest load of mathematical operations.

By using repeated OFDM training blocks, we successfully implement the method of LS to perform frequency tracking combined with channel estimation for OFDM systems over mobile wireless channels. Unlike the usual ML algorithms commonly adopted for joint frequency tracking and channel estimation using one OFDM training block, our algorithm has no local extrema problem arising from the highly nonlinear nature of the multi-dimensional log-likelihood function and does not require the use of time-consuming adaptive iterations. Simulation results show that both the tracking performance and the error rate performance for OFDM systems using our proposed method are very satisfactory.

CFR: channel frequency response; CIR: channel impulse response; CRB: Cramer-Rao bound; DFT: discrete Fourier transform; i.i.d.: independent: identically distributed; LMMSE: linear minimum-mean-square-error; LS: least squares; ML: maximum-likelihood; MSE: mean square error; OFDM: orthogonal frequency division multiplexing; RV: random variable; SNR: signal-to-noise ratio.

The authors declare that they have no competing interests.

1. HY Liu, RY Yen, Effective adaptive iteration algorithm for frequency tracking and channel estimation in OFDM systems. IEEE Trans Veh Technol 59(4), 2093–2097 (2010)

2. M Morelli, U Mengali, Carrier-frequency estimation for transmissions over selective channels. IEEE Trans Commun 48(9), 1580–1589 (2000). Publisher Full Text

3. X Ma, H Kobayashi, SC Schwartz, Joint frequency offset and channel estimation for OFDM. Proceedings of the IEEE GLOBECOM 2003 (San Francisco, USA, 2003) 1, pp. 15–19

4. L Zheng, W Cheng, J Hu, D Yuan, The ML frequency tracking algorithm for OFDM systems based on pilot symbols and decision data. Proceedings of the IEEE Symposium on Microwave, Antenna, Propagation, and EMC Technology for Wireless Communication. Beijing, China 2, 1611–1614 (2005)

5. JH Lee, JC Han, SC Kim, Joint carrier frequency synchronization and channel estimation for OFDM systems via the EM algorithm. IEEE Trans Veh Technol 55(1), 167–172 (2006). Publisher Full Text

6. FZ Merli, GM Vitetta, Iterative ML-based estimation of carrier frequency offset, channel impulse response and data in OFDM transmissions. IEEE Trans Commun 56(3), 497–506 (2008)

7. P Stoica, O Besson, Training sequence design for frequency offset and frequency-selective channel estimation. IEEE Trans Commun 51(11), 1910–1917 (2003). Publisher Full Text

8. DC Chu, Polyphase codes with good periodic correlation properties. IEEE Trans Inf Theory 18(4), 531–532 (1972). Publisher Full Text

9. MS Alouin, A Goldsmith, A unified approach for calculating error rates of linearly modulated signals over generalized fading channels. IEEE Trans Commun 47(9), 1324–1334 (1999). Publisher Full Text