SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Sparse Signal Processing.

Open Access Highly Accessed Research

OFDM pilot allocation for sparse channel estimation

Pooria Pakrooh1*, Arash Amini2 and Farokh Marvasti2

Author Affiliations

1 Electrical and Computer Engineering Department, Colorado State University, Fort Collins, Colorado, USA

2 Advanced Communication Research Institute (ACRI), Electrical Engineering Department, Sharif University of Technology, Tehran, Iran

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2012, 2012:59  doi:10.1186/1687-6180-2012-59

The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2012/1/59

Received:4 October 2011
Accepted:8 March 2012
Published:8 March 2012

© 2012 Pakrooh et al; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


In communication systems, efficient use of the spectrum is an indispensable concern. Recently the use of compressed sensing for the purpose of estimating orthogonal frequency division multiplexing (OFDM) sparse multipath channels has been proposed to decrease the transmitted overhead in form of the pilot subcarriers which are essential for channel estimation. In this article, we investigate the problem of deterministic pilot allocation in OFDM systems. The method is based on minimizing the coherence of the submatrix of the unitary discrete fourier transform (DFT) matrix associated with the pilot subcarriers. Unlike the usual case of equidistant pilot subcarriers, we show that non-uniform patterns based on cyclic difference sets are optimal. In cases where there are no difference sets, we perform a greedy method for finding a suboptimal solution. We also investigate the performance of the recovery methods such as orthogonal matching pursuit (OMP) and iterative method with adaptive thresholding (IMAT) for estimation of the channel taps.

1 Introduction

In wireless communications, orthogonal frequency division multiplexing (OFDM) is a well-known solution for overcoming the problem of multipath fading channels [1,2]. However, this solution is effective only when the receiver is provided with tools to estimate the channel frequency response (CFR). To this end, the transmitter should send some predefined data in a predefined order that the receiver is a priori aware of. These predefined data are usually called pilots.

There are two main approaches for inserting pilot data in OFDM signals. In block-type pilots, all the subcarriers in some OFDM blocks (the whole spectrum) are reserved as pilot tones. In comb-type pilot models, some predefined subcarriers in each block serve as pilots. Hence, CFR at these subcarriers can be estimated using methods such as least square (LS) or minimum mean square error (MMSE). Now for estimating the CFR at non-pilot subcarriers, interpolation methods ranging from simple linear or second order techniques [3] to time domain [4] and even more complex approaches are used. It is clear that by decreasing the frequency gap between the adjacent pilot subcarriers, the performance of the interpolation techniques improves. Therefore, the pilots are preferably put at equidistant subcarriers to provide uniformity.

Considering the inherent sparsity in the impulse response of the wireless channels which is due to the sparse structure of the scattering objects, it is possible to estimate the channel impulse response (CIR) more accurately even from non-uniform pilot patterns. The common estimation techniques in this case are those introduced in the field of compressed sensing such as basis pursuit [5] and orthogonal matching pursuit (OMP) [6]. Unlike the interpolation case, equidistant pilot locations are not the best choices here. In [7], using the results of [5] for sparse signal recovery, it is mentioned that uniformly random pilot locationsa can provide the possibility of perfect channel reconstruction with overwhelming probability. Although this is an important theoretical result, it is not practical. In this article, we suggest a deterministic structure for the pilot locations in sparsity-based channel estimation methods which minimizes the inter-atom interference in discrete fourier transform (DFT) submatrices. Simulation results confirm the efficiency of the proposed pilot allocation method when greedy methods are used for channel estimation. Also, we propose an iterative thresholding method for channel estimation which results in appropriate performance in time-variant frequency selective OFDM channels.

2 Problem statement

In OFDM systems with comb-type pilot arrangement, ignoring the effects of inter-symbol interference (ISI) and inter-carrier interference (ICI), the received data at the kth subcarrier (1 ≤ k ≤ N) of the nth OFDM frame can be formulated as:

Y ( n , k ) = X ( n , k ) H ( n , k ) + W ( n , k ) , (1)

where X(n, k) is the transmitted OFDM symbol, H(n, k) is the CFR and W(n, k) is the AWGN noise. If P denotes the set of all pilot indices, at a given pilot subcarriers k p P and using the LS method, the CFR can be estimated as:

H ̃ ( n , k p ) = Y ( n , k p ) X ( n , k p ) = H ( n , k p ) + W ( n , k p ) X ( n , k p ) . (2)

As explained earlier, conventional methods for estimation of the CFR at non-pilot subcarriers (given the noisy measurements at pilots) are interpolation-based techniques which require relatively high sampling rates (number of pilots) to produce acceptable mean squared error (MSE). Also, the optimum structure of the pilot locations for these techniques which minimizes the MSE of the estimated channel, is the uniform distribution (equidistance) of the pilots in the spectrum.

In the sparsity-based channel estimation methods, instead of finding the CFR, the goal is to estimate the inherently sparse CIR in each OFDM frame from limited number of noisy measurements of the CFR obtained at pilot locations. The estimated CIR is then, translated into the frequency domain by means of FFT which results in an estimation of the CFR that can be used for data equalization process. In these methods, we are dealing with the following system of equations:

H ̃ p = F p h + n p , (3)

where Fp is the DFT submatrix with N p = P rows associated with the pilot locations, H ̃ p is the vector of LS-estimated CFR at pilot locations, h is the sparse CIR vector, and np is the vector of noise values.

Generally, there are two main categories of sparsity-based methods to solve the set of equations presented in (3). One approach is to minimize the 1 norm of h subject to (3), either directly or iteratively (such as SPGL [8]). Although the performance of such methods are considered among the bests, they are extremely slow for real-time implementation. The other approach which is considered in this article, is to use fast greedy methods such as OMP which iteratively detect and estimate the location and value of the channel taps. These methods are usually faster than 1 minimization techniques by orders of magnitude while they may fall short of performance. Our simulation results confirm that their performance is acceptable for the purpose of OFDM channel estimation.

The main advantages of sparsity-based approaches can be categorized into two parts:

(1) Decreasing MSE: Generally, the purpose of using compressed sensing methods in solving a linear set of equations with the sparsity constraint is to achieve the Cramer Rao lower bound on MSE [9]. In extreme cases, the structured LS estimator [9] which knows the location of nonzero taps (support) through an oracle, and estimates their corresponding values using LS estimation is the best estimator. The MSE of this estimator is called CRB-S [9]. However, in general, there is no information about the location of the nonzero coefficients of h at the receiver and the structural LS estimator is not realizable. Simulation results indicate that we can get close to this bound by using proper sparsity-based methods.

(2) Reducing Overhead: Although the pilot subcarriers occupy a fraction of the spectrum, they do not convey any data. By reducing the number of pilot subcarriers, we increase the utilization efficiency of the spectrum while we may degrade the performance of the channel estimation block. As mentioned in [7], by considering the sparsity of the CIR, it is possible to capture the necessary information in the frequency domain in fewer number of pilots. The results in [5] show that 1 minimization technique almost perfectly reconstructs the sparse CIR from (3) when the number of pilots is proportional to the number of channel taps. Furthermore, the reconstruction performance is independent of the location and value of the taps; i.e., unlike the interpolation-based methods, the number of required pilot subcarriers does not depend on the delay spread and degree of frequency selectivity of the channel.

3 Iterative thresholding method for sparse channel estimation

In this section, we propose an iterative method with adaptive thresholding (IMAT) [10] for the purpose of estimating the sparse CIR. In other words, we aim to identify non-zero channel taps and estimate their corresponding values using IMAT.

In our general OFDM channel estimation problem presented in (3), our main goal is to estimate h from H ̃ p given the fact that h has a few non-zero coefficients. To obtain an initial estimate, we multiply the sides of (3) by Moore-Penrose pseudo-inverse of Fp to find the solution with minimum 2-norm:

h ̃ 0 = F p   H ̃ p = F p   F p h + F p   n p . (4)

Using the properties of the Moore-Penrose psuedo-inverse for underdetermind set of equations we have:

F p   = F p H ( F p F p H ) - 1 1 N I N P × N p = 1 N F p H . (5)

Now we can rewrite (4) as:

h ̃ 0 = 1 N F p H F p G N × N h + 1 N F p H n p . (6)

The elements of the N × N non-negative matrix G which is usually referred to as the distorting matrix, are given by:

g i , j = 1 N f i , f j i j N p N i = j , (7)

where fi represents the ith column of Fp. If the columns of Fp are orthogonal and there is no additive noise, h ̃ 0 will be a scaled version of h; in general case where the columns are not orthogonal, h ̃ 0 is a distorted estimate of h. Now through a series of iterations and by employing the sparsity constraint, we try to improve this estimate. In each iteration, we perform one step of the iterative method studied in [11] followed by a thresholding operator:

h ̃ ̃ k = λ ( h ̃ 0 - G h ̃ k - 1 ) + h ̃ k - 1 , (8)

h ̃ k ( i ) = h ̃ ̃ k ( i ) h ̃ ̃ k ( i ) > β e - α k 0 otherwise , (9)

where λ and k are the relaxation parameter and the iteration number, respectively, G h ̃ k is the output of the distorting operator to the input h ̃ k and h ̃ 0 is defined in (6). The steps (8) are known to compensate for the non-orthogonality of the columns of Fp while the thresholding operator takes the sparsity constraint into account. We employ adaptive thresholds in (9) which can be tuned through the parameters α and β, and decrease exponentially with respect to the iteration number. The optimality of the exponential function in our method can be derived in a similar manner as in [12]. The block diagram of the proposed channel estimation method is shown in Figure 1.

thumbnailFigure 1. Block diagram of the IMAT method.

In the proposed method, the ideal but unrealistic case would be when there is no distortion; i.e., when G is a scaled version of the identity matrix. Although this never happens, it shows that when G is a good-enough approximation of the identity matrix, we can expect satisfying results. Thus, a given set of pilot locations is considered as good if the off-diagonal elements of the matrix G are relatively small compared to the diagonal elements. In the following section, we will investigate the problem of selecting the DFT submatrix Fp which results in a suitable distorting matrix G.

4 Pilot allocation by minimizing the coherence in partial DFT matrices

As mentioned before, the performance of a channel estimation block depends on both the reconstruction technique and the set of pilot locations. In this section, we will study the sub-optimum pilot locations when greedy sparsity-based methods such as OMP and the introduced IMAT are employed.

4.1 Cyclic difference sets: minimum coherence

To begin with, consider the following underdetermined set of equations:

y m × 1 = Φ m × n x n × 1 (10)

where y is the observed vector, x is an s-sparse vector (contains at most s non-zero elements) and Φ is an m×n (m n) measurement matrix which in our case is the partial DFT matrix formed by selecting Np rows. In this section, we seek to find a proper location for pilots in each OFDM block, using the following definition.

Definition 1: The coherence of a measurement matrix Φ ∈ ℂm×n is the maximum absolute cross-correlation between the normalized columns:

μ Φ = max 1 l , k n l m | φ l , φ k | φ l 2 φ k 2 . (11)

Although the so called restricted isometry property (RIP) [5] is the best known tool for characterizing the performance of a given matrix Φ in sampling the sparse vectors, there is currently no polynomial time algorithm to check this property [13]. The common alternative for measuring how well a matrix preserves the information of the sparse vectors (x) in the produced samples (y) is the coherence; the smaller the better. In addition, the performance of the greedy methods is more influenced by the coherence of the measurement matrix rather than its RIP order [6]. One of the well-known results demonstrates that the sparsity-based methods such as 1 minimization and greedy methods, are guaranteed to perfectly recover the s-sparse vectors when μ Φ < 1 2 s [6].

Returning to our main problem stated in (3), we aim to choose pilot indices in such a way that the coherence of the resulted measurement matrix, Fp, becomes as small as possible. Considering the unit-norm property of the elements of Fp, we have:

μ F P = max 1 l , k n l k | f l , f k | N p . (12)

If the pilot indices are P = { P 1 , , P N P } , Fp becomes:

F p = 1 e - j 2 π N P 1 e - j 2 π N P 1 ( N - 1 ) 1 e - j 2 π N P 2 e - j 2 π N P 2 ( N - 1 ) 1 e - j 2 π N P N p e - j 2 π N P N p ( N - 1 ) . (13)

According to the periodic structure of the DFT submatrix FP, the inner product of fl and fk used in (12) only depend on r = k - l:

μ ̃ F P = N p μ F P = max 1 r N - 1 f l , f l + r = max 1 r N - 1 i = 1 N p e - j 2 π N P i r . (14)

Here we aim to choose the set P with P = N P in order to minimize μ ̃ . For the simplicity of analysis, let us define f ( x ) = i = 1 N p x P i . Hence, (14) turns into:

μ ̃ F P = max 1 r N - 1 f e - j 2 π N r . (15)

Since we are interested in the modulus values of the function f(.) on the unit circle, instead of |f(x)| it is simpler to work with |f(x)|2 = f(x)f*(x) = f(x).f(1/x). This shows that the optimum set P which minimizes the coherence, is found by:

P o p t = arg min P max 1 r N - 1 f ( e - j 2 π N r ) f ( e j 2 π N r ) arg min P max 1 r N - 1 l = 1 N p k = 1 N P e - j 2 π N r ( P l - P k ) . (16)

If the set of cyclic differences of P is defined as D = { P k - P l ( mod N ) | 1 l , k N p ; l m } , and ad denotes the number of repetitions of the number 0 ≤ d≤ N - 1 in the set D , we have:

l = 1 N p k = 1 N P e - j 2 π N r ( P l - P k ) = N P + d = 1 N - 1 a d e - j 2 π N r d g ( r , { a d } ) . (17)

Therefore, it is clear that we should look for the set of indices P which minimizes the maximum value of the function g(r, {ad}) over all 1 ≤ r ≤ N. Since

r = 1 N - 1 g ( r , { a d } ) = N p ( N - 1 ) - d = 1 N - 1 a d = N p ( N - N p ) , (18)

it is obvious that

max 1 r N - 1 g ( r , { a d } ) N P ( N - N P ) N - 1 , (19)

and the equality happens when

g ( 1 , { a d } ) = = g ( N - 1 , { a d } ) = N P ( N - N P ) N - 1 , (20)

which is valid only for

a 1 = a 2 = = a N - 1 = i = 1 N - 1 a d N - 1 = N p ( N - 1 ) N - 1 . (21)

Hence, if there exists an index set P for which a1= ⋯ = aN-1 happens, it is for sure the best possible choice for minimizing the coherence. Such index sets are already known as cyclic difference sets [14]; unfortunately, the existence of difference sets are limited to some specific pairs (N,Np).

4.2 Greedy coherence minimization for improper pairs of N and Np

Cyclic difference sets described in Section 4.1 are the optimal choices for the OFDM pilot locations with respect to the coherence criterion. In fact, if we make a DFT submatrix based on a cyclic difference set, the resultant matrix meets the Welch lower boundb [15]. In other words, not only is such a submatrix optimum among all DFT submatrices of its size, but also is the optimum code-book in the sense of minimum coherence among all the matrices with the same size. Nevertheless, for many pairs of N and Np, there is no cyclic difference set. Therefore we have to find proper indices for pilot allocation, using efficient search methods. In [16], it is suggested to use random exhaustive search among all N N p DFT submatrices to find the one with the minimum coherence. As N increases, the cardinality of the search space grows exponentially and the results of the random search in relatively small steps might not be satisfactory. Here we propose a greedy method to find suitable pilot index set.

As stated in 4.1, it is important that the set of cyclic differences D of the set of pilot indices P has equal number of repetitions (ad) for its different elements; i.e., the variance of the set of repetitions {ad}d is equal to zero. In our greedy method, we choose Np pilot indices in the following Np stages: since rather than the exact value of the indices, their cyclic difference are important, we initialize the index set by P ( 1 ) = { 1 } (1 is arbitrary). The rest of the stages are summarized in the following:

For the ith pilot index allocation:

1. Form all N - i + 1 possible i-element subsets by adding an element to P ( i - 1 ) :

{ P ( i ) } = P ( i - 1 ) s | s { 1 , , N } \ P ( i - 1 ) (22)

2. For each i-element set generated in step (1), form the set of cyclic differences and the set of repetitions ({ad}).

3. Choose the set (or one of the possible sets) with the minimum variance in the elements of the respective repetition set ({ad}).

4. If i < Np, go to step (1).

5 Simulation results

In order to give an insight toward theoretical results presented in Sections 3 and 4, we conduct several computer simulations using MATLAB. The simulations are presented in two parts:

5.1 IMAT method for sparse channel estimation results

The IMAT presented in the block diagram of Figure 1 is simulated in an OFDM system based on DVB-H standard with slight modifications. All the parameter specifications are presented in Table 1. For the channel, we have considered a Rayleight multipath fading channel with 4 significant nonzero taps at normalized (to carrier spacing) doppler frequency of 1%; the average delay and power of the taps are presented in Table 2.

Table 1. Simulation parameters

Table 2. Fading channel parameters

The IMAT method is compared with the linear interpolation method which estimates the channel at pilot frequencies using LS estimate (2) and then uses a linear interpolation function to estimate the CFR at data subcarriers. Also OMP is simulated as a proper sparse reconstruction method for channel estimation. The obtained curves of the obtained Bit Error Rate (BER) and Symbol Error Rate (SER) shown in Figures 2 and 3 indicate that the IMAT method outperforms the other competitors.

thumbnailFigure 2. BER of different estimators at various SNRs.

thumbnailFigure 3. SER of different estimators at various SNRs.

5.2 Pilot allocation in sparsity-based estimation methods

In this part, we compare the MSE and perfect reconstruction percentage in channel estimation for pilot allocation methods presented in this article. For our simulations in this part, we generated a random 3-tap channel with varying fading parameters in each OFDM block and averaged the results over 5000 runs. Figure 4 shows the MSE of the estimated channel for two different methods of pilot allocation. In the first scenario, the pilots are chosen uniformly at random for each block; in our proposed scheme, the pilots are arranged according to a (73,9,1) cyclic difference set and its cyclic shifts for different OFDM blocks. The MSE of the structured LS estimator is also presented in the figures as CRB-S to give us a meaningful goal standard. This bound is given by [9]:

thumbnailFigure 4. MSE of proposed and random pilot allocation methods for OMP reconstruction.

CRB-S = σ 2 trace F p , Λ H F p , Λ - 1 , (23)

where σ2 is the noise variance and Fpis the submatrix of Fp obtained by keeping the columns corresponding to the channel taps. This lower bound is a fair criterion to measure the quality of our pilot allocation method, since it is the MSE of an estimator that knows the exact location of the channel taps. Therefore, in OMP channel estimation, if we select pilot locations properly, the maximum cross correlation between the columns of Fp becomes small. Hence, the columns of the resultant measurement matrix in (3) become less correlated which makes it easier to detect and estimate the CIR. Similarly for IMAT, decrease in the off-diagonal elements of the distorting matrix results in the decrease of the MSE values of the estimated channel (Figure 5).

thumbnailFigure 5. MSE of the proposed and random pilot allocation methods for IMAT reconstruction.

Finally, we compare successful channel recovery percentage in noiseless case for different pilot allocation methods. For this purpose, we have considered the OFDM communication with N = 256 subcarriers and Np= 16 pilots. Since there is no cyclic difference set for this pair of N and Np, we have employed the proposed greedy search in Section 4.2 to find a pattern for pilots with small coherence. The recovery percentage which is the percentage of exact channel recovery without error for various number of channel taps and OMP reconstruction method is presented in Figure 6.

thumbnailFigure 6. Recovery percentage for the proposed and random pilot allocation schemes.

6 Conclusion

In this article, we investigated the problem of OFDM pilot allocation in sparsity-based channel estimation methods. First, we proposed an IMAT which detects channel nonzero taps and their corresponding values iteratively for the purpose of OFDM channel estimation. As it was shown in the simulation results, this method outperforms typical interpolation methods such as Linear Interpolation and greedy algorithms in sparse channel estimation. We derived the optimum pilot location for greedy methods in sparse channel estimation, based on minimizing the coherence in DFT submatrices. Simulation results show the improvement in the MSE of the estimated channel for our proposed pilot allocation method compared to uniformly random insertion of pilots.

Competing interests

The authors declare that they have no competing interests.


aThat means all possible choices of pilot indices are equally likely. bIn this article, we have used a different mathematical approach to prove the optimality of such a submatrix.


  1. ETSI EN 302 304, Digital video broadcasting(dvb); transmission system for handheld terminals (dvb-h)

  2. ETSI TS 102 428, Digital audio broadcasting(dab);dmb video service; user application specification

  3. M Hsieh, C Wei, Channel estimation for OFDM systems based on comb-type pilot arrangement in frequency selective fading channels. IEEE Trans Consum Electron 44(1), 1–5 (1998). Publisher Full Text OpenURL

  4. R Steele, Mobile Radio Communications (Pentech Press Limited, London, England, 1992)

  5. E Candes, J Romberg, T Tao, Stable signal recovery from incomplete and inaccurate measurements. Comm Pure Appl Math 59, 1207–1223 (2006). Publisher Full Text OpenURL

  6. JA Tropp, Greed is good: algorithmic results for sparse approximation. IEEE Trans Inf Theory 50(10), 2231–2242 (2004). Publisher Full Text OpenURL

  7. G Taubock, F Hlawatsch, A compressed sensing technique for OFDM channel estimation in mobile environments: Exploiting channel sparsity for reducing pilots. IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2008, Las Vegas, NV, 2885–2888 (2008)

  8. MAT Figueiredo, RD Nowak, SJ Wright, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J Sel Top Signal Process 1(4), 586–597 (2007)

  9. C Carbonelli, S Vedantam, U Mitra, Sparse channel estimation with zero tap detection. IEEE Trans Wirel Commun 6(5), 1743–1763 (2007)

  10. F Marvasti, A Amini, F Hadadi, M Soltanolkotabi, BH Khalaj, A Aldroubi, S Holm, S Sanei, J Chambers, A unified approach to sparse signal processing [http://arxiv.org/abs/0902.1853] webcite OpenURL

  11. F Marvasti, Nonuniform Sampling: Theory and Practice (Kluwer Academic/Plenum Publishers, New York, 2001)

  12. M Soltanolkotabi, M Soltanalian, A Amini, F Marvasti, A practical sparse channel estimation for current OFDM standards. International Conference on Telecommunications, 2009. ICT'09, Marrakech, 217–222 (2009)

  13. Z Ben-Haim, YC Eldar, M Elad, Coherence-based near oracle performance guarantees. IEEE Trans Wirel Commun 6(5), 1743–1763 (2007)

  14. CJ Colbourn, JH Dinitz, CRC Handbook of Combinatorial Designs (CRC Press, Boca Raton, FL, 1996)

  15. P Xia, S Zhou, GB Giannakis, Achieving the Welch bound with difference sets. IEEE Trans Inf Theory 51(5), 1900–1907 (2005). Publisher Full Text OpenURL

  16. BM Hochwald, TL Marzetta, TJ Richardson, W Sweldens, R Urbanke, Systematic design of unitary space-time constellations. IEEE Trans Inf Theory 46(6), 1962–1973 (2000). Publisher Full Text OpenURL