Suboptimal frequencial equalisation of a mono or multicarrier system Carine Simon and Juan Jose Da˜nobeitia Unidad de Tecnolog´ıa Marina, CSIC Passeig Maritim de la Barceloneta, 37 08003 Barcelona. S PAIN Email:
[email protected]
Abstract— We present a low complexity iterative method for estimation of symbols in mono or multicarrier systems where cyclic prefixes are combined to data symbols. We take advantage of the special structure of unknown convolutive channels of such systems and of the fact that the symbols belong to a finite alphabet. Even in a noisy environment, it gives good results for detection and estimation.
I. I NTRODUCTION Among transmission techniques, those using cyclic prefix (CP) have raised considerable interest, including in local area mobile context or video–broadcasting. Indeed, using systems where data symbols are combined with CP of length larger than the finite impulse response (FIR) channel order is an efficient way to avoid inter symbol interference (ISI). In order to do this, the cyclic structure created by the CP is used together with fast Fourier Transform (FFT) and inverse FFT (IFFT) operations applied on data. Another equivalent structure is the Known Symbol Padding (KSP) where the cyclic prefix is known. Here this will be used but it can be noticed that an unknown cyclic prefix would just change the channel estimate initialisation technique. In this paper, the case single–carrier block transmission over stationary multipath channel where the channel is convolutive and unknown is considered. It should be noted that the extension to the multicarrier case (i.e. orthogonal frequency decision multiplexing (OFDM)) is direct and thus won’t be detailed here. In this context, we examine an iterative technique for symbol estimation which uses the special cyclic structure of the FFT of the convolutive channel as well as the finite alphabet property of the data. Details on the model are given in the next section. The third section explains the proposed method, starting with [2] and improving it. Various ways of amelioration are detailed in the fourth section. Before concluding, the fifth section shows simulations, comparing our method with the one of [2]. II. M ODELS The convolutive transmission channel is of order L : h = [h0 . . . hL ]T where (.)T denotes the transpose operator.
Antoni M`anuel Centre Tecnol`ogic de Vilanova i la Geltr´u UPC-SARTI Rambla Exposici´o s/n 08800 Vilanova i la Geltr´u
The transmitted sequence is of the form x = [t s1 t . . . sV t] where t is cyclic prefix KSP of size M and sk is the k th data block of the burst. sk = [skB+1 , . . . , s(k+1)B ] : B × 1. Symbols are Binary Phase Shift Keyed (BPSK). In order to get the results for multicarrier, transmitted symbols should be replaced by their Fourier transform. We set P = B + M . Finally, ∀i = M + 1, . . . , P V + M the received sequence is of the form: yi =
L
h xi− + ni
=0
where ni is a white Gaussian noise. Considering V such data bursts, we can rewrite this model in a matrix form by defining yn = [yM +(n−1)P +1 . . . yM +nP ], and omitting the first t we set: Y X
[(y1 )T . . . (yV )T ] : P × V 1 T S (s ) . . . (sV )T = :P ×V = tV t ... t
=
and the (P × P ) circulant h0 0 . . . h1 h0 0 .. .. . . . . . h Hc = L 0 hL . . . . .. .. . 0
...
matrix ... .. . h0
0
hL 0
0 h0
... 0
..
. 0
hL
... hL .. . ... .. . ...
h2 ... .. .
h1 h2 .. .
0
hL 0 .. .
..
.
h0
Defining the noise matrix N in the same way as Y , the model can then be rewritten as: Y = Hc X + N
(1)
As the channel matrix is circulant, it will diagonalise in the Fourier vector basis: Hf = FP Hc IP where we recall that 2iπkn the FFT matrix is defined by (FP )kn = P −1/2 e− P and 2iπkn (IP )kn = P −1/2 e P . We have Y = IP Hf FP X + N or Yf = Hf Xf + Nf where Af = FP A for A = Y, X, N . In this paper, we will set L = M . We recall that the size of the matrices are then: Yf : P ×V , Hf : P ×P and Xf : P ×V .
III. P ROPOSED METHOD The maximum–likelihood approach is optimal when the noise is additive white and Gaussian. It leads to the following joint least square minimisation problem: min y − hx2
(2)
x,h
As this method is very complex, suboptimal techniques are often used. The iterative least square with projection (ILSP) technique cf [3] for example) consist in minimizing the function in (2) alternatively with respect to the channel and to the symbols. In order to use the fact that the symbols belong to the BPSK alphabet, a projection of the estimated symbols to that alphabet is then performed. A. Channel estimation The first minimisation is done on h. The idea, inspired by [2], is to use the fact that Hf is diagonal in order to decouple that minimisation: as the FFT is bijective, we can equivalently minimise min Yf − Hf Xf 2 Hf
As Hf is diagonal, we can decouple the problem: 2
min Yf (j, :) − Hf (j, j)Xf (j, :)
Hf (j,j)
∀j
(3)
Here and in the following, norm 2 is used for vectors and Fr¨obenius norm for matrices and A(j, :) represents the j th row of matrix A. [2] directly use (3) and find the following channel estimation: ˆ −1 (j, j) = Xf (j, :)Yf (j, :) (Yf (j, :)Yf (j, :) )−1 H f where denotes the transconjugate of a matrix or a vector. However, we can improve this estimation, noticing that Hf has a specific structure. Indeed, let us set Hv the vector made of the diagonal terms of Hf . It can be shown that Hv = Ch where the elements of the matrix C of size P × (L + 1) are 2iπm(n−1) P Cnm = e− . The norm in (3) thus gives: Yf (j, :) − Hf (j, j)Xf (j, :)2 = [Yf (j, :) − Hf (j, j)Xf (j, :)] ∗ [Yf (j, :) − Hf (j, j)Xf (j, :)] = Yf (j, :) ∗ Yf (j, :) − C(j, :)hXf (j, :)Yf (j, :) −Yf (j, :)h C(j, :) Xf (j, :) +C(j, :)hXf (j, :)Xf (j, :) C(j, :) h (4) And minimizing (4) with respect to hm ∀m, ∂ Yf (j, :) ∂h∗ m
− Hf (j, j)Xf (j, :)2 = −Yf (j, :)C(j, m)∗ Xf (j, :) +C(j, :)hC(j, m)∗ Xf (j, :)Xf (j, :) Vectorizing this result, we get ˆ = C Yf , Xf C diag(Xf , Xf )C h
(5)
where A, B = diag(AB ) and following Matlab notations, if V is a matrix, diag(V ) is the vector of its diagonal
components, if V is a vector, diag(V ) is a diagonal matrix with the elements of V on its main diagonal. Due to the hermitian T¨oplitz structure of C diag(X, X)C, it should be noticed that it is easily invertible. B. Symbol estimation Minimizing Yf (j, :) − Hf (j, j)Xf (j, :)2 with respect to Xf (j, :) ∀j, we get ˆ f (j, :) = H ˆ −1 (j, j)Yf (j, :) X f
∀j
and as Hf is diagonal, this is equivalent to ˆ −1 Yf ˆf = H X f
(6)
ˆ f by setting We can directly get the data symbol part out of X IBP = IP (1 : B, :). Then, ˆ −1 Yf Sˆ = IBP H f
(7)
Finally, Sˆ is projected onto the finite alphabet (BPSK). IV. I MPROVEMENTS In this section, we propose a few ideas in order to improve our method. A. Estimation of the variance of the noise In this section, we suggest to replace the zero forcing estimation (6) by a Minimum Mean Square Estimation of the symbols. We suppose that the noise is an additive Gaussian white noise (AWGN) with constant variance σn2 . It can be shown that σ ˆn2 = σ 2y − h2
V k where σ 2y = k=1 var(y ). Since in the simulations, the estimation of the channel is always very good from the second iteration onward, the estimation of the variance of the noise is accurate enough to be used. Remarking that the noise variance is not changed by FFT, we then modify the estimation of the data (7) in the following way: ˆf + σ ˆ f Yf ˆ f H Sˆ = IBP (H ˆn2 I)−1 H (8) This idea is very attractive as it is nearly costless : the mean of the variance of the observation just has to be computed once. Then, the matrix in (8) to be inverted is still diagonal. B. Real and imaginary parts In the specific case of BPSK, data is real, therefore it is possible to split the equation set into its real and imaginary parts: HR NR YR = X+ YI HI NI Taking this set of equations instead of the original one allows to get twice as many degrees of freedom as with the original set (1). If it can easily be shown that this separation leads to an equivalent channel estimation, it can be worth using that structure to estimate the symbols. The same concept is used in frequency domain.
C. Reducing the noise? Knowing the CP and its estimation, it is tempting to reduce the noise by deducing its part due to the CP. Unfortunately, we are going to show that this is not possible. In the same way we have estimated the data part, we can estimate the training part: ˆ −1 Yf tˆV = IM P H f where IM P are the first M rows of IP . We need a few more definitions for the rest of the section: FP B = FP (:, 1 : B) FP M = FP (:, B + 1 : P ) t f = FP M t S f = FP B S where A(:, C1 : C2) means that the submatrix of A containing all the rows and columns from C1 to C2 are taken. ˆ f Hf , we can write Now, if we assume H εt
= tˆV − tV = IM P Hf−1 (Yf − Hf Xf ) = IM P Hf−1 Nf
It thus seems natural to replace Yf by Zf = Yf −Hf ∗FP M εt in (7). But Zf
= Hf Sˆf + Hf tˆV f − Hf ∗ FP M (tˆV − tV ) = Hf (Sf + εSf ) + Hf tˆV f − Hf ∗ (tˆV f − tV f ) = Hf Xf + Hf εSf
where εSf is the error made on the estimation of Sf . We thus see that using Zf instead of Yf in the estimation (7) won’t improve: SˆZ
= IBP Hf−1 Zf = IBP (Xf + εSf ) = S + εS = Sˆ
where εS = IP εSf . V. A LGORITHM SUMMARY 1) 2) 3) 4)
Compute the mean variance of the observation. Initialisation: random data symbols are generated. Channel coefficient estimation with (5). If number of iterations > 1, noise variance estimation (cf section IV-A). Symbol estimation (8) and projection onto BPSK alphabet 5) Compute the difference between this symbol estimation and the previous one. If any change, back to step 3. VI. S IMULATIONS
The simulations have been performed with a Rayleigh channel of memory length L = 5, with a cyclic prefix of length M = 5 per burst and each burst has P = 64 elements. Moreover, there are V = 100 such bursts. For each noise variance from -10 to 20 dB with an increase of 5 dB per step, we ran 10000 Monte–Carlo simulations. The following plots only show different mean values.
Two types of channels have been used: the first one is an L + 1 tap frequency selective channel. The second one comes from a model proposed by France Telecom R& D [1]. In the plots, • metH = 1 means that [2] technique has been used. • metH = 2 means our channel estimation technique has been used. • RI means that observations are split into their real and imaginary parts (section IV-B). • noise means we have used the estimated noise variance (section IV-A). • inSex represents one iteration of the algorithm initialising the symbols to their real value. For inSex, any technique using RI gives the same result. The x–axis represents the variance of the noise in dB. For each channel in figure 1, on the top plot, the y–axis represents the mean of error rate among the Monte–Carlo simulations. In both cases, in particular for a σn > 0dB, our method leads to better results than the one in [2]. Moreover, it can be seen that the estimation of the noise variance does give good improvement. Decomposing the observation into its real and imaginary parts also gives interesting results. The middle sets of plots give the normalized mean error on ˆ the final estimation of the channel: moy h − h/h . The same conclusions can be drawn. Finally, the bottom plots give insight on the mean number of iterations necessary for each method to converge over the Monte–Carlo simulations. From this point of view, our method again leads to fewer iterations and decomposing the signal also reduces the number of necessary iterations. It is interesting to notice that simulations have also been run initialising the channel to its real value but the final results being very similar to the ones presented in figure 1, they are not shown here. Furthermore, we have tested the case where metH = 1 was used to estimate the channel combined with the alternatives proposed in section IV but no improvement was noticed, even on the contrary, as can be seen on figure 2. In fact as the estimation of the channel is bad in this case (cf results on figure 1) and the estimation of the variance of the noise uses the norm of the channel estimation, it was predictable that no improvement would be noticed. But the decomposition in RI did not help either in improving the results. On the plots, metH = 1 and metH = 1 noise are one on the top of each other and the scale for the channel estimation have been changed with respect to figure 1 for obvious reasons. VII. C ONCLUSION This paper presents a suboptimal ML procedure for the detection–estimation problem of mono or multicarrier systems with CP and unknown convolutive channels. An ILSP type algorithm has been used, exploiting the special structure of the channel. Indeed, the FFT of a circulant matrix is diagonal, which allows to decouple the optimisation of the channel. We have also used the fact that the symbols belong to a finite alphabet.
Mean error on symbol estimation, channel 1
Mean error on symbol estimation, channel 2 0.2 metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise
0.25
metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise
0.18
0.16
0.14 0.2 0.12
0.15
0.1
0.08 0.1 0.06
0.04 0.05 0.02
0 −6
−4
−2
0
2
4
6
8
0 −6
10
−4
−2
0
2
4
6
8
10
6
8
10
(a) Mean error on symbol estimation Mean error on channel estimation, channel 1
Mean error on channel estimation, channel 2
metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise metH = 1, inSex metH = 2, inSex
0.25
0.25
0.2
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0 −6
−4
−2
0
2
4
6
8
0 −6
10
metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise
−4
−2
0
2
4
(b) Normalised mean error on channel estimation Mean number of iterations, channel 1
Mean number of iterations, channel 2 metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise
30
25
25
20
20
15
15
10
10
5
5
0 −6
−4
−2
0
2
4
6
8
metH = 1 metH = 2 metH = 2 RI metH = 2 noise metH = 2 RI noise
30
10
0 −6
−4
−2
(c) Mean number of iterations Fig. 1.
Channel 1 on LHS. Channel 2 on RHS
0
2
4
6
8
10
Mean error on symbol estimation, channel 1
Mean error on channel estimation, channel 2
metH = 1 metH = 1 RI metH = 1 noise metH = 1 RI noise
0.25
0.25
0.2
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0 −6
−4
−2
0
2
4
6
8
metH = 1 metH = 1 RI metH = 1 noise metH = 1 RI noise
0 −6
10
−4
−2
0
2
4
6
8
10
8
10
(a) Mean error on symbol estimation Mean error on channel estimation, channel 1
Mean error on channel estimation, channel 2
30
30
metH = 1 metH = 1 RI metH = 1 noise metH = 1 RI noise
25
25
20
20
15
15
10
10
5
5
0 −6
−4
−2
0
2
4
6
metH = 1 metH = 1 RI metH = 1 noise metH = 1 RI noise
8
10
0 −6
−4
−2
0
2
4
6
(b) Normalised mean error on Fig. 2.
Channel 1 on LHS. Channel 2 on RHS, [2] method
Our algorithm is found to work in a few iterations even with 10 dB of noise, showing excellent results on the estimation of channel coefficients and on data detection. Two interesting modifications have been suggested, among which a good way to estimate the variance of the noise which allows a noticeable improvement in data estimation with only little added effort. ACKNOWLEDGMENT This work was supported by the project SigSensual ref. REN2003-08341-C03- C01-02 and CTM2004-04510-C03-02, the Marine Technology Unit, the Public University of Navarra and the Catalan Polytechnical University, SPAIN. C. Simon is financed by the I3P program.
R EFERENCES [1] P. Pajusco, “Experimental characterization of DOA at the base station in rural and urban area”, IEEE Vehicular Technology Conference, Ottawa, pp. 993–997, 1998. [2] O. Rousseaux, G Leus & M. Moonen, “A suboptimal Iterative Method for Maximum–Likelihood Sequence Estimation in a Multipath Context”, EURASIP Journal on Applied Signal Processing, pp. 1437–1447, dec. 2002. [3] S. Talwar, M. Vilberg & A. Paulraj, “Blind separation of synchronous co–channel digital signals using an antenna array–Part I: Algorithms”, IEEE Trans. on Signal Processing, vol. 44, no 5, pp. 1184–1197, 1996.
