Abstract
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 nonuniform 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 wellknown 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 blocktype pilots, all the subcarriers in some OFDM blocks (the whole spectrum) are reserved as pilot tones. In combtype 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 nonpilot 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 nonuniform 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 locations^{a }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 sparsitybased channel estimation methods which minimizes the interatom 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 timevariant frequency selective OFDM channels.
2 Problem statement
In OFDM systems with combtype pilot arrangement, ignoring the effects of intersymbol interference (ISI) and intercarrier interference (ICI), the received data at the kth subcarrier (1 ≤ k ≤ N) of the nth OFDM frame can be formulated as:
where X(n, k) is the transmitted OFDM symbol, H(n, k) is the CFR and W(n, k) is the AWGN noise. If denotes the set of all pilot indices, at a given pilot subcarriers and using the LS method, the CFR can be estimated as:
As explained earlier, conventional methods for estimation of the CFR at nonpilot subcarriers (given the noisy measurements at pilots) are interpolationbased 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 sparsitybased 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:
where F_{p }is the DFT submatrix with rows associated with the pilot locations, is the vector of LSestimated CFR at pilot locations, h is the sparse CIR vector, and n_{p }is the vector of noise values.
Generally, there are two main categories of sparsitybased 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 realtime 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 sparsitybased 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 CRBS [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 sparsitybased 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 interpolationbased 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 nonzero 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 given the fact that h has a few nonzero coefficients. To obtain an initial estimate, we multiply the sides of (3) by MoorePenrose pseudoinverse of F_{p }to find the solution with minimum ℓ_{2}norm:
Using the properties of the MoorePenrose psuedoinverse for underdetermind set of equations we have:
Now we can rewrite (4) as:
The elements of the N × N nonnegative matrix G which is usually referred to as the distorting matrix, are given by:
where f_{i }represents the ith column of F_{p}. If the columns of F_{p }are orthogonal and there is no additive noise, will be a scaled version of h; in general case where the columns are not orthogonal, 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:
where λ and k are the relaxation parameter and the iteration number, respectively, is the output of the distorting operator to the input and is defined in (6). The steps (8) are known to compensate for the nonorthogonality of the columns of F_{p }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.
Figure 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 goodenough approximation of the identity matrix, we can expect satisfying results. Thus, a given set of pilot locations is considered as good if the offdiagonal 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 F_{p }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 suboptimum pilot locations when greedy sparsitybased 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:
where y is the observed vector, x is an ssparse vector (contains at most s nonzero elements) and Φ is an m×n (m ≪ n) measurement matrix which in our case is the partial DFT matrix formed by selecting N_{p }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 crosscorrelation between the normalized columns:
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 wellknown results demonstrates that the sparsitybased methods such as ℓ_{1 }minimization and greedy methods, are guaranteed to perfectly recover the ssparse vectors when [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, F_{p}, becomes as small as possible. Considering the unitnorm property of the elements of F_{p}, we have:
If the pilot indices are , F_{p }becomes:
According to the periodic structure of the DFT submatrix F_{P}, the inner product of f_{l }and f_{k }used in (12) only depend on r = k  l:
Here we aim to choose the set with in order to minimize . For the simplicity of analysis, let us define . Hence, (14) turns into:
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 which minimizes the coherence, is found by:
If the set of cyclic differences of is defined as , and a_{d }denotes the number of repetitions of the number 0 ≤ d≤ N  1 in the set , we have:
Therefore, it is clear that we should look for the set of indices which minimizes the maximum value of the function g(r, {a_{d}}) over all 1 ≤ r ≤ N. Since
it is obvious that
and the equality happens when
which is valid only for
Hence, if there exists an index set for which a_{1}= ⋯ = a_{N}_{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,N_{p}).
4.2 Greedy coherence minimization for improper pairs of N and N_{p}
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 bound^{b }[15]. In other words, not only is such a submatrix optimum among all DFT submatrices of its size, but also is the optimum codebook in the sense of minimum coherence among all the matrices with the same size. Nevertheless, for many pairs of N and N_{p}, 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 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 of the set of pilot indices has equal number of repetitions (a_{d}) for its different elements; i.e., the variance of the set of repetitions {a_{d}}_{d }is equal to zero. In our greedy method, we choose N_{p }pilot indices in the following N_{p }stages: since rather than the exact value of the indices, their cyclic difference are important, we initialize the index set by (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 ielement subsets by adding an element to :
2. For each ielement set generated in step (1), form the set of cyclic differences and the set of repetitions ({a_{d}}).
3. Choose the set (or one of the possible sets) with the minimum variance in the elements of the respective repetition set ({a_{d}}).
4. If i < N_{p}, 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 DVBH 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.
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.
Figure 2. BER of different estimators at various SNRs.
Figure 3. SER of different estimators at various SNRs.
5.2 Pilot allocation in sparsitybased 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 3tap 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 CRBS to give us a meaningful goal standard. This bound is given by [9]:
Figure 4. MSE of proposed and random pilot allocation methods for OMP reconstruction.
where σ^{2 }is the noise variance and F_{p,Λ }is the submatrix of F_{p }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 F_{p }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 offdiagonal elements of the distorting matrix results in the decrease of the MSE values of the estimated channel (Figure 5).
Figure 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 N_{p}= 16 pilots. Since there is no cyclic difference set for this pair of N and N_{p}, 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.
Figure 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 sparsitybased 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.
Endnotes
^{a}That means all possible choices of pilot indices are equally likely. ^{b}In this article, we have used a different mathematical approach to prove the optimality of such a submatrix.
References

ETSI EN 302 304, Digital video broadcasting(dvb); transmission system for handheld terminals (dvbh)

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

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

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

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

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

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)

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)

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

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

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

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)

Z BenHaim, YC Eldar, M Elad, Coherencebased near oracle performance guarantees. IEEE Trans Wirel Commun 6(5), 1743–1763 (2007)

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

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

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