Abstract: In multiple-input-multiple-output (MIMO) orthogonal frequency-division multiple-access (OFDMA) systems the Least Square (LS), Linear Minimum Mean Square Error (LMMSE) and LMMSE Singular Value Decomposition (SVD) algorithms are commonly used in channel estimation. For this reason the paper addresses analysis and compare of these channel estimation algorithms based on complexity theory. In the paper, the channel platform is first supplied by MMO-OFDMA systems. Then these algorithms are simply introduced. Finally we have analyzed and compared time and space complexity of these channel algorithms and these results owned important reference value to the design of MIMO-OFDMA systems based on different channel environment.
INTRODUCTION
Broadband mobile communication has enabled MIMO technology and OFDM technology to become the most promising research direction in the field of wireless mobile communication in the future. OFDMA technology growing up based on OFDM is a multiple-access technology, whose channel design will generate more influence for system capability. OFMDA technology can apply suitable channel design for bringing about high efficiency communication in allusion to different environment. And the channel could select or device a better estimator algorithm by algorithm t- heory to enhance communication reliability (Huang et al., 2009).
Crux information of the processing of wireless systems is provided by channel parameters Zhaogan et al. (2007). There is to use various demodulations in OFDMA systems for obtaining channel information (Noh et al., 2006). And these algorithms are invented to improve the capability of the system or sum rate (Wang et al., 2010c; Ramesh and Vaidehi, 2006). The detection of MIMO-OFDMA signals demands channel estimation to mediate amplitude and phase in a fading channel (Salari et al., 2008). It is very known that these LS, LMMSE and LMMSE-SVD algorithms are often adopted in channel estimation. The simplest algorithm is the LS algorithm, which can partition these received signals in the frequency domain (Hoeher et al., 1997). The LMMSE channel estimator derives from the MMSE that exploits channel correlation and reduces intra/inter-cell interference in time and freque- ncy domain (Wang et al., 2010a). But the disadvantage of the estimator algorithm is that it needs some prior knowledge about the channel frequency correlation and the matrix inversion (Edfors et al., 1998). At the moment the paper also introduces a modified LMMSE algorithm using optimal rank reduction by SVD. But there has no too much investigation on the performance of the MIMO-OFDMA systems.
The kernel of the algorithm theory is the complexity theory. There is to analyze an algorithm by time and space complexity elements these can observe and study time and space cost for improving or comparing various algorithm. And time complexity measures the length of executive time of the algorithm. Another natural measure space complexity is to mark the amount of memory consumed on executiving. The people usually only consider time complexity when memory is very plenty. But in order to reflect more reference value of the result, there is to observe and study the algorithm by time and space complexity.
In the study, the LS, LMMSE and LMMSE-SVD estimation algorithms are first introduced. Then there is to focus on studying and comparing time and space complexity of these algorithms. In the end the performance is presented both in term of Mean-square Error (MSE) and Bit Error Rate (BER) as a part of reference information.
SYSTEMS DESCRIPTION
In general an OFDMA system can be described as a set of parallel gaussian channels with correlated attenuations hk. For example a kind mode of MIMO-OFDMA systems is designed by Zhou et al. (2010) and Wang et al. (2010b). The comp-lex channel atenuations is:
| (1) |
where, gk is the frequency response of the channel during the OFDMA symbol.
The transmitted symbol Xn(k) from the nth transmit antenna on the kth subcarrier is given by:
| (2) |
where, Sn(k) indicates the data symbol and Cn(k) represents the pilot symbol (Wang et al., 2010d). It is assumed that perfect synchronization and cyclic prefix longer than the channel impulse response length. The model of MIMO-OFDMA systems can be expressed as:
| (3) |
where, y is a vector of the received signal, X is a matrix containing these transmitted symbols, n is a vector of compl-ex gaussian noise with variance σn2, expectation 0.
The paper will use a uniform channel model, where every one impulse has the same average power and every one delay is uniformly and independently distributed over the length of the CP (Edfors et al., 1998).
CHANNEL ESTIMATION RESEARCH
In OFDMA system, the accuracy of channel estimation directly affects the performance. The channel estimation has some important parameters, such as the order of the channel, doppler frequency shift or channel impulse response. And the channel estimation from channel impulse response and the order of the channel will be studied in this sector. It is assumed that the received OFDMA symbol contains data known either training data or receiver data (The LAN/MAN Standards Committee, 2006).
Firstly, this section presents the LS estimation and the LMMSE estimation. Then by using the SVD in the LMMSE estimation, the rank of channel impulse response can be reduced and the number of multiplications is also reduced.
LS and LMMSE ESTIMATION: If the channel vector h is uncorrelated with the channel noise n, the LS estimation of h is described as:
| (4) |
where n’ is X-1n with variance
From formula (4), it is clear that the LS estimator has higher noise. But the LMMSE estimation is good at restrain-ing noise. The LMMSE estimation of channel attenuation h based on the LS estimation is displayed as (Scharf, 1991).
| (5) |
where these covariance matrices are:
| (6) |
The orthogonal design of matrix X has a significant feature that decoding complexity is lower than other designs. Thus in the following we assume matrix X meets:
| (7) |
where I is the identity matrix. And we assume E|hk|2 = 1 and all points are equal probability too. At the same time, we define the average SNR as:
| (8) |
Now we can gain a simplified LMMSE channel estimation:
| (9) |
Because the amount of computation of inverse matrix is very high, so the estimation requires N2 multiplications per subchannel under these conditions. To further reduce the complexity of the estimator, we process the LMMSE estim- ation by recommending the SVD.
LMMSE-SVD estimation: The complexity reduction of estimation is implemented under optimal rank reduction. And the rank reduction of the LMMMSE is obtained by using the SVD (Edfors et al., 1998; Shaoshuai and Gang, 2008). The SVD of the channel correlation matrix can be shown as:
| (10) |
where, U is a matrix that consists of orthonormal columns and
| (11) |
where, Δ is a diagonal matrix containing these values:
| (12) |
Form Eq. 9 to 10, we know that the LMMSE estimator in (8) can become a rand-p matrix as:
| (13) |
where Δp is a upper left pxp corner of Δ.
COMPLEXITY ANALYSIS
These complexity measures of the system are shown in Fig. 1, each processing block. The LS estimation, the LMMSE estimation and the LMMSE-SVD estimation can be implemented equivalently with interpolation operations in the same system.
Operational efficiency of the algorithm mainly include time and space efficiency. These are the most valid methods for measuring the efficiency of the algortihm. The best algo-rithm should has lest memory space and executive time. In this sector these algorithms introduced above are analyzed through time and space complexity.
Time complexity analysis: To further analyze the computati- onal complexity of the LMMMSE-SVD estimation, formula (13) may be written by a sum of column vectors as:
By defining
| (15) |
It is clear that the estimation requires 3pN multiplications and every subchannel requires p multiplications. And it is shown obviously that p is a crucial parameter in the computational complexity. The smaller p is, the lower the computational complexity.
Considering inverse operation of the LMMSE channel estimation, there is to use Cholesky decomposition for opp- ortunely reducing the complexity of the LMMSE estimation (Chang, 2008).
| Fig. 1: | Block diagram for channel estimations based on multiplexed pilot |
| Table 1: | Time complexity |
| Table 2: | Space complexity |
Now these calculations are presented in Table 1 and the time complexity is shown as T(n).
The Table 1 shows that the time complexity of the LMMSE estimation is significantly reduced by using the SVD. The LMMSE-SVD algorithm can drop the rate of the code in effect. But the LS algorithm obviously has the least executive time in these three estimation algorithms only considering the rate.
Space complexity analysis: The space complexity of the alg- orithm that considered here is mainly auxiliary memory in code executing. And it is often described as S(n) = O(g(n)), where g(n) is gained by order of magnitude.
It is well known that the space complexity of the LS and the LMMSE estimation are separate O(N) and O(2N2+p+N). From formula (9) the space complexity of the LMMSE estimation comes mainly from matrix inverse operation. The inverse operation requires about O(N4) in interim memory by analyzing the code of algorithm. And the Rhh can only hold about O(N2) in memory. Thus the space complexity of the LMMSE algorithm is O(N4). Now these calculations are presented in Table 2 about the space complexity.
It is shown that the LS algorithm can require least stored memory in these algorithms and by using the SVD the LMMSE algorithm could reduce validly the stored memory. At the same time the people can see that the p parameter is very important for the space complexity of the LMMSE-SVD estimation.
SIMULATION RESULT AND ANALYSIS
In order to study the performance of the LS, LMMSE and LMMSE-SVD channnel estimations, the BER simulate-on and the MSE simulation are used. There will be considered the condition that the transmit antenna number is two and the receive antenna number is one only.
| Fig. 2: | BER performance curve for 16-QAM |
| Fig. 3: | MSE performance curve for 16-QAM |
These basic parameters used in the simulations are given as the following:
| • | Number of OFDM symbols in each frame: 31 |
| • | The data modulation constellation size: 16QAM |
| • | The number of interference users: 0 |
| • | Bandwidth of the system: 20 MHz |
| • | Frequency of carrier: 2.6 GHz |
| • | Ratio of CP to the period of an OFDM symbol: 1/8 |
| • | The number of FFT points: 2048 |
| • | DIUC: 0 |
| • | Coding scheme: CC and support encoding sub- channel concatenation |
| • | Channel model: SUI_5, Ray |
To test the performance, there has calculated the BER and the MSE by using the formula presented in Wilson (1994). The obtained BER curves are displayed in Fig. 1, And the MSE curves are showed in Fig. 2.
From Fig. 2 people can find that the rank-5 LMMSE- SVD estimator improves the performance over the LS estimator by about 3 dB in SNR for the BSE. Compared to the LMMSE estimator, its loss in SNR is only about 0.9 dB. The rank-5 estimator requires 3p = 16 multiplication per estimated subchannel. In addition the coding gain is 10 dB at the BSE than the uncoded system (Hussain et al., 2011). According to the Fig. 3, we can analyze the simulation result of the MSE. We see that the proposed algorithm is obvious better than the LS algorithm performance and that is lower than the LMMSE algorithm performance.
CONCLUSIONS
The study, is to study and analyze the merit of the algorithm. The paper first introduces these algorithms. And it focuses on analyzing and comparing the time and space complexity of these estimation algorithms.
From the complexity analysis and performance simulation, the people can conclude:
| • | When there is a slow fading channel, the LS algorithm is the best select because of the least time and space complexity |
| • | When there is a rapid fading channel, the LMMSE- SVD algorithm is the best choice because of higher performance than the LS algorithm and lower complexity than the LMMSE algorithm |
| • | The time and space complexity are often influenced each other. And a better time complexity generally appears because of requiring more memory in the same algorithm |
| • | All performances of the algorithm exit more or less mutual influence. For example, the LMMSE-SVD algo- rithm has a lower complexity than the LMMSE algor- ithm by sacrificing a little system performance |
To sum up these conclusions, the quality of a algorithm is effected by many elements such as execution time, stored memory, algorithm description language and computer env- ironment etc. The people could design a good system by modifying properly various elements.