Présentée et soutenue par Monsieur Amir SAEMI

UNIVERSITE DE LIMOGES

ECOLE DOCTORALE SCIENCE – TECHNOLOGIE –SANTE

FACULTE DES SCIENCES ET TECHNIQUES

XLIM – DEPARTEMENT C2S2 (UMR CNRS 6172)

Année : 2007 N°29-2007

THESE

Pour obtenir le grade de

DOCTEUR DE L'UNIVERSITE DE LIMOGES

Discipline : Télécommunications des Hautes Fréquences et Optique

Présentée et soutenue par

Monsieur Amir SAEMI

Le 20 Septembre 2007

SYNCHRONISATION DES SYSTEMES DE

TRANSMISSION MIMO-OFDM

Directeurs de Thèse : Jean-Pierre CANCES et Vahid MEGHDADI

JURY

Président M. Jean-Michel DUMAS, Professeur, Université de Limoges

Rapporteurs M. Samir Saoudi, Professeur, ENST Bretagne

M. Philippe Ciblat, Maître de conférences, HDR, ENST Paris

Examinateur Mme. Yi Yuan, France TELECOM R&D

Co-directeurs de thése M. Jean-Pierre CANCES, Professeur, Université de Limoges

M. Vahid MEGHDADI, HDR, Université de Limoges

2 Amir Saemi

University of Limoges, XLIM/C2S2/ESTE UMR CNRS 6172, ENSIL 3

Acknowledgement

This manuscript is the result of my efforts in three years spent at the department C2S2

in the XLIM laboratory within the project “Etudes des systèmes de

Télécommunications de l’ENSIL” (ESTE). Funding of this thesis was provided by

France Telecom R&D under grant 46 129562.

During this time, I was fortunate enough to have excellent supervisors: Vahid

Meghdadi and Jean-Pierre Cances and I am so thankful to them for their continuing

guidance, support and insights. Also, I have to express my thanks to Jean-Michel

Dumas, the head of the project at the time, who supported all of us very kindly and

generously.

Moreover, I would like to thanks the R&D section of France Telecom for their

continuing guidance and their scientific and financial supports. A special mention for

Mr. Patrick Tortelier, Mrs. Maryline Hélard.

I would also like to thank my colleagues, nay, friends, at ENSIL. I specially think to

Reza Zahabi who was a great help and support for me during these years. I would

also like to mention Ahmed Kora and Hamid Meghadadi.

Needless to say, I am very grateful to my parents. Although we were separated by

thousands of miles, they provided me unlimited love and support throughout my

many years of education. Without them, I would not achieve what I have

accomplished.

Last but not least, thanks to my wife, Maryam Alaeddini, whose love, understanding,

encouragement and support are endless. I would like to express my profound

gratitude and love to her.

.

4 Amir Saemi


CONTENTS

CHAPTER 1 INTRODUCTION ........................................................................11

1.1 MIMO-OFDM....................................................................................................................11

1.2 Synchronization of MIMO OFDM.....................................................................................14

1.3 Outline and Contribution....................................................................................................15

1.3.1 Outline.................................................................................................................................................. 15

1.3.2 Contribution ......................................................................................................................................... 16

CHAPTER 2 CHANNEL ESTIMATION .........................................................19

2.1 Introduction ........................................................................................................................19

2.2 Data aided methods ............................................................................................................21

2.2.1 Preamble based training ....................................................................................................................... 21

2.2.2 Pilot based training............................................................................................................................... 27

2.2.3 Comparison between preamble based training and pilot based training .............................................. 34

2.3 Blind and semi blind methods ............................................................................................36

2.4 Iterative channel estimation................................................................................................37

CHAPTER 3 CARRIER FREQUENCY OFFSET ESTIMATION................39

3.1 Introduction ........................................................................................................................39

3.2 Carrier frequency offset estimation....................................................................................42

3.2.1 FFT method by using frequency domain training sequence................................................................. 42

3.2.2 Hopping pilots method......................................................................................................................... 45

3.2.3 Iterative method ................................................................................................................................... 49

3.2.4 Autocorrelation method ....................................................................................................................... 51

3.3 Comparison and conclusion ...............................................................................................53

CHAPTER 4 TIME SYNCHRONIZATION ....................................................57

4.1 Introduction ........................................................................................................................57

4.2 Non MIMO-OFDM time synchronization .........................................................................59

4.2.1 MIMO non-OFDM time synchronization ............................................................................................ 59

4.2.2 Non-MIMO OFDM time synchronization ........................................................................................... 73

4.3 MIMO OFDM frame synchronization ...............................................................................79

4.3.1 Autocorrelation method ....................................................................................................................... 80

4.3.2 Advanced autocorrelation method ....................................................................................................... 83

6 Amir Saemi

4.4 MIMO OFDM symbol timing ........................................................................................... 88

4.4.1 Methods with the knowledge of channel coefficients .......................................................................... 89

4.4.2 ML MIMO-OFDM symbol timing method.......................................................................................... 96

CHAPTER 5 JOINT TIME FREQUENCY MIMO−OFDM SYNCHRONIZATION . 103

5.1 Introduction...................................................................................................................... 103

5.2 Signal model .................................................................................................................... 104

5.3 ML Synchronizer ............................................................................................................. 107

5.3.1 Packet arrival instant and initial CFO estimation............................................................................... 107

5.3.2 Residual CFO estimatition ................................................................................................................ 111

5.4 Simulation results and complexity................................................................................... 115

5.4.1 Cramer-Rao Lower Bound ................................................................................................................. 115

5.4.2 Algorithm complexity ........................................................................................................................ 117

5.4.3 Simulation results............................................................................................................................... 118

CHAPTER 6 EM-BASED MIMO-OFDM SYNCHRONIZATION.............. 125

6.1 Introduction...................................................................................................................... 125

6.2 System model................................................................................................................... 126

6.3 EM algorithm................................................................................................................... 129

6.4 EM synchronizer.............................................................................................................. 131

6.5 Simulation results............................................................................................................. 136

CHAPTER 7 PERSPECTIVE: MIMO-OFDMA SYNCHRONIZATION....... 147

7.1 Introduction...................................................................................................................... 147

7.2 System Description .......................................................................................................... 150

7.3 EM synchronization algorithms....................................................................................... 153

7.3.1 Using EM algorithm........................................................................................................................... 154

7.3.2 Using SAGE algorithm ...................................................................................................................... 160

7.3.3 Initialization Strategies....................................................................................................................... 161

7.3.4 Algorithms complexity....................................................................................................................... 161

7.4 Simulation results............................................................................................................. 162

CHAPTER 8 CONCLUSION ............................................................................. 169

REFERENCES..................................................................................................... 173


FIGURES CAPTION

Figure 1: a typical MIMO-OFDM realization................................................................................13

Figure 2: Outline of the channel estimation ...................................................................................20

Figure 3: System diagram for a channel estimator.........................................................................21

Figure 4 : un1 (l) for OFDM with optimum training sequence [62] ...............................................24

Figure 5: A single training sequence transmission scheme for two antennas that achieves zero

cross-correlation .............................................................................................................................26

Figure 6: The lower bound in capacity as a function of T (Nt=Nr=10) ..........................................28

Figure 7: The optimal value of Np (Nt=Nr=10) ..............................................................................29

Figure 8: Average capacity bound with increasing number of transmit antennas .........................29

Figure 9: Discrete time baseband equivalent Tx-Rx MIMO model...............................................31

Figure 10: Training scheme example (Nt=3)..................................................................................33

Figure 11: Training scheme example (Nt=3, L=3) .........................................................................34 Figure 12: Channel MSE comparison (Nt=2,Nr=1 and L=6)..........................................................35 Figure 13: Comparison of the channel MSE (Nt=2,Nr=1 and L=6) ...............................................35 Figure 14: BER vs Eb/N0 for various existing CFOs in a 2×2 STBC-OFDM system ...................41

Figure 15: BER vs CFO for various Eb/N0 in a 2×2 STBC-OFDM system...................................41

Figure 16: Data burst structure for FFT method. ...........................................................................45

Figure 17: One example of training structure ................................................................................48

Figure 18: Two identical consecutive preambles ...........................................................................52

Figure 19: Simplified baseband model for space-time coding system...........................................60

Figure 20: MSE performance of the ML estimator for the different training sequence ................69

Figure 21: Comparison of MSEs of the MLNDA and MLDA and their corresponding CCRBs and

MCRBs for a 4 × 4 system. ............................................................................................................72

Figure 22: the repeated preamble used in the literature .................................................................75

Figure 23: Using cross correlation for fine timing .........................................................................76

Figure 24: Packet structure for IEEE 802.11a WLANs .................................................................77

Figure 25: Timing metrics in [40] ..................................................................................................78

Figure 26: A typical MIMO-OFDM transmitter and receiver .......................................................79

Figure 27: Time orthogonal preamble suitable for MIMO systems with two transmit antennas ..81

Figure 28: Orthogonal preamble for MIMO systems with two transmit antennas ........................82

Figure 29- Peak of the y(n) (equation (104)) helping to detect the exact timing ...........................86

Figure 30: Comparison of symbol timing results obtained by the methods with the knowledge of

channel............................................................................................................................................95

Figure 31: Illustration of symbol timing problem..........................................................................96

Figure 32: OFDM symbol and FFT position .................................................................................98

Figure 33 : Pf(0.5) for the algorithms in [28] and [27] as a function of SNR ..............................102

Figure 34: Pf(0.05dB) for the proposed algorithm in 4×4 MIMO system with 100 and 150 ns

delay spread as a function of SNR ...............................................................................................102

Figure 35- Finding the correct time instant (k=0) assuming sliding windows observations .......107

Figure 36: Timing failure probability resulted in time synchronizer without compensating CFO

with respect to ε. Various SNRs are considered ..........................................................................111 Figure 37: simulation results for the probabilities of missing a ±p interval.................................119 Figure 38: Simulation results for the lock-in probabilities in a dispersive channel. The simulation

are performed for various SNR ....................................................................................................120

8 Amir Saemi

Figure 39: Mean-Square-Error of Carrier Frequency Offset (CFO) for four presented methods

together with Cramer-Rao-Lower-Bound (CLRB)...................................................................... 121

Figure 40: BER of an iterative synchronizer with respect to various training sequence length. . 122

Figure 41: Comparison of our synchronizer and the best known synchronizer for a 2×2 MIMO-

OFDM system.............................................................................................................................. 123

Figure 42: MIMO-OFDM iterative synchronization ................................................................... 128

Figure 43: Data burst structure. ................................................................................................... 129

Figure 44: Comparison of iterative synchronization performance. Perfect synchronization;

unbiased code-aided synchronization; Decision Directed synchronization; the approximation of

Decision Directed synchronizer; the approximation of code-aided synchronization, the first

iteration in the synchronization that corresponds to the performance of system without

synchronization ............................................................................................................................ 137

Figure 45: Comparison of iterative channel estimation with different methods: Decision Directed

channel estimation; the approximation of Decision Directed channel estimator; unbiased code-

aided channel estimator; the approximation of code-aided channel estimator; unbiased code-aided

channel estimator. ........................................................................................................................ 138

Figure 46: Comparison of the normalized mean square error of carrier frequency offset for both

methods: Decision-Directed and Code-Aided. The Cramer-Rao lower bound is also shown..... 139

Figure 47: Exponentially improvement of the performance per iteration. .................................. 140

Figure 48: Exponentially improvement of the normalized minimum square error of carrier

frequency offset per iteration. An unbiased code-aided synchronizer is used at Eb/N0=5 dB..... 141

Figure 49: Exponentially improvement of the minimum square error of channel estimation per

iteration. An unbiased code-aided synchronizer is used at Eb/N0=5 dB...................................... 141

Figure 50: Comparison of channel estimation in different situations: Decision Directed channel

estimation in the case where we do not have any carrier frequency error (genie); Decision

Directed channel estimation; The results of the first iteration in the EM algorithm in the case

where we do not have carrier frequency offset; The results of the first iteration in the EM

algorithm; Data aided estimation of a genie estimator. ............................................................... 143

Figure 51: Timing failure probabilities to miss a ±5 interval ...................................................... 144 Figure 52: Illustration of multipath and timing errors for user 1, receive antenna 1. .................. 152

Figure 53:CFO estimation performance with equal power assignment....................................... 164

Figure 54: CFO estimation performance in a near-far situation .................................................. 164

Figure 55: Channel estimation performance in a near-far situation ............................................ 166

Figure 56: Success rate for the transmitted packets for EM and SAGE algorithms.................... 166

Figure 57:BER performance comparison between synchronisation algorithms.......................... 167


NOTATIONS

The following notations are usually used in this manuscript unless another notation is explicitly

mentioned.

1) ( ) ( ). , .T H

denote transpose and conjugate transpose of ( ). , respectively.

2) ( ) ( ), ,:

. , .m n m

denote the th( , )m n element and mth row of ( ). , respectively.

3) ( ).E denotes the expectation (.).

4) K P×A denotes a matrix with K rows and P columns.

5) a denotes the estimate of a.

6) ⊗A B denotes the Kronecker tensor product of matrices A and B.

11 12 1

21

1 2

. . .

.

. . .

n

n n nn

a a a

a

a a a

⊗ =

L

L L M

M O L M

L

B B B

BA B

B B B

7) Scalars are printed in italic and vectors and matrices are printed in bold.

8) We generally assume that we have a MIMO system with Nt transmit and Nr receive

antennas.

9) n and m are usually used as the indexes for transmit and receive antenna. (In chapter 7 p and

q are used as the indexes for transmit and receive antenna.

10) In an OFDM system we assume that we have Nc subcarriers and NCP is the length of cyclic

prefix.

11) Np is used to represent the length of training sequence or pilots.

12) k is usually used as an index for time. In chapter 7, k is used to refer to different users.

13) ∆f represents the frequency error. ε which is normally called CFO is the multiplication of

frequency error by sampling time: i.e. CFO (or ε) ≡ ∆f × Ts (Ts is sampling time)

14) η0 represents the time offset less than sampling time.

15) h and H represent the channel. hnm(l) is the lth taps of equivalent channel between nth

transmit antenna and mth receive antenna. We normally assume a quasi-static channel with

length L. Moreover the following definitions are normally used through this manuscript:

[ ]1

(0) (1) ... ( 1)T

nm nm nm nm Lh h h L

×= −h

10 Amir Saemi

1 21

...t

t

TT T Tm m m N m LN ×

= :h h h h

11 12 1

21 22 2

1 2

( ) ( ) ( )

( ) ( ) ( )( )

( ) ( ) ( )

r

r

t t t r

N

N

N N N N

h l h l h l

h l h l h ll

h l h l h l

=

H

L

L

M M M

L

The above mentioned notations are used for time domain channels. On the other hand,

[ ]mn pH represents the frequency domain channel corresponding pth sub carrier and between

nth and mth transmit and receive antenna.

16) r represents the received vector and rm,k represents the kth received sample at the mth

receive

antenna.

Moreover, rm,k denotes a column vector of received signal at the mth receive antenna

starting from the kth instant i.e. , , 1 , 1...T

m k m k m k Nr r r+ + − . and

1, 2, , 1...

k k N krr

TT T T

kNN ×

=

r r r r .

r(k) denotes all the received sample at the kth instant from all receive antenna i.e.

1, , ,...r

T

k m k N kr r r

In frequency domain, rm[p] presents the signal of mth antenna corresponding pth subcarrier.

The same indexation rules are applied to all the other signals represented by s,u, etc.

17) w represents the noise vector and wm,k represents the kth noise sample at the mth

receive

antenna. In this manuscript we suppose that we have zero mean complex Gaussian noise

with covariance matrix σw²I.


1. INTRODUCTION

1.1 MIMO-OFDM

Orthogonal frequency division multiplexing (OFDM) has become a popular technique for

transmission of signals over wireless channels. OFDM has been adopted in several wireless

standards such as digital audio broadcasting (DAB), digital video broadcasting (DVB-T), the

IEEE 802.11a / Wi-Fi [15] local area network (LAN) standard and the IEEE 802.16a / WiMax

[16] metropolitan area network (MAN) standard. OFDM is also being pursued for dedicated

short-range communications (DSRC) for road side to vehicle communications and as a potential

candidate for fourth-generation (4G) mobile wireless systems.

OFDM converts a frequency-selective channel into a parallel collection of frequency flat

subchannels. The subcarriers have the minimum frequency separation required to maintain

orthogonality of their corresponding time domain waveforms, yet the signal spectra

corresponding to the different subcarriers overlap in frequency. Hence, the available bandwidth is

used very efficiently. If knowledge of the channel is available at the transmitter, then the OFDM

transmitter can adapt its signalling strategy to match the channel. Due to the fact that OFDM uses

1Chapter

12 Amir Saemi

a large collection of narrowly spaced subchannels, these adaptive strategies can approach the

ideal water pouring capacity of a frequency-selective channel. In practice, this is achieved by

using adaptive bit loading techniques, where different sized signal constellations are transmitted

on the subcarriers. OFDM is a block modulation scheme where a block of information symbols is

transmitted in parallel on subcarriers. An OFDM demodulator can be implemented as a discrete

Fourier transform (IDFT) on a block of information symbols followed by an analogue-to-digital

converter (ADC). To mitigate the effects of intersymbol interference (ISI) caused by channel time

spread, each block of IDFT coefficients is typically preceded by a cyclic prefix (CP) or a guard

interval consisting of samples, such that the length of the CP is at least equal to the channel

length. Under this condition, a linear convolution of the transmitted sequence and the channel is

converted to a circular convolution. As a result, the effects of the ISI are easily and completely

eliminated. Moreover, the approach enables the receiver to use fast signal processing transforms

such as a fast Fourier transform (FFT) for OFDM implementation [17].

Multiple antennas can be used at the transmitter and receiver, an arrangement called a multiple-

input multiple-output (MIMO) system. A MIMO system takes advantage of the spatial diversity

that is obtained by spatially separated antennas in a dense multipath scattering environment.

MIMO systems may be implemented in a number of different ways to obtain either a diversity

gain to combat signal fading or to obtain a capacity gain. Generally, there are categories of

MIMO techniques. The first aims to improve the power efficiency by maximizing spatial

diversity. Such techniques include delay diversity, space–time block codes (STBC) [18], [19] and

space–time trellis codes (STTC) [20]. One can think also in layered approach to increase

capacity. One popular example of such a system is V-BLAST suggested by Foschini et al. [21]

where full spatial diversity is usually not achieved.

OFDM has been adopted in the IEEE802.11a LAN (Wi-Fi) and IEEE802.16a LAN/MAN

standards (WiMAX). OFDM is also being considered in IEEE802.20a, a standard for maintaining

high-bandwidth connections to users moving at speeds up to 96 km/h. The IEEE802.11a LAN

standard operates at raw data rates up to 54 Mb/s (channel conditions permitting) with a 20-MHz

channel spacing, thus yielding a bandwidth efficiency of 2.7 b/s/Hz. The actual throughput is

highly dependent on the medium access control (MAC) protocol.


Likewise, IEEE802.16a operates in many modes depending on channel conditions with a data

rate ranging from 4.20 to 22.91 Mb/s in a typical bandwidth of 6 MHz, translating into a

bandwidth efficiency of 0.7 to 3.82 bits/s/Hz. Recent developments in MIMO techniques promise

a significant boost in performance for OFDM systems. Broadband MIMO-OFDM systems with

bandwidth efficiencies on the order of 10 b/s/Hz are feasible for LAN/MAN environments. The

physical (PHY) layer techniques described in this manuscript are intended to approach 10 b/s/Hz

bandwidth efficiency.

A multicarrier system can be efficiently implemented in discrete time using an inverse FFT

(IFFT) to act as a modulator and an FFT to act as a demodulator. The transmitted data are the

“frequency” domain coefficients and the samples at the output of the IFFT stage are “time”

domain samples of the transmitted waveform. Figure 1 shows a typical MIMO-OFDM

implementation.

Figure 1: a typical MIMO-OFDM realization.

14 Amir Saemi

1.2 Synchronization of MIMO OFDM

Apparently, the synchronization of MIMO systems might seem closely related to the problem of

synchronization in single-input-single-output (SISO) systems. In MIMO systems, the

synchronization problem takes a special form because signals from different antennas are

superimposed together, and some algorithms commonly proposed for SISO systems do not work

well in MIMO systems and the other need some modifications.

The problem of synchronization in MIMO-OFDM systems as well as in all OFDM systems

consists in three parts: channel estimation, frequency and time synchronization. The main focus

of this thesis is on the problem of time and frequency synchronization for MIMO-OFDM

systems. However, in chapter 2 a literature survey on the channel estimation will be presented.

Channel state information is essential for channel equalization. Moreover, most MIMO

algorithms suppose that channel state information is available. To acquire the channel state

information normally some known data is used. The known data can be either a training sequence

is used in the first of the data packet or some known pilots are inserted in the data packet.

However, there are some other algorithms which use the information of data packet in order to

increase the performance of information. Moreover, blind algorithms are discussed in the

literature.

One of the most important tasks in a MIMO-OFDM receiver is frequency synchronization. A

frequency offset can be introduced due a difference between the transmitter and receiver clock or

due to the Doppler effect. OFDM systems work in frequency domain by using frequency

orthogonal sub-carriers; Fourier transformation is used in an OFDM receiver as the modulator.

Because of these facts even a very small frequency offset in a MIMO-OFDM system can destroy

the orthogonality between the sub-carriers and thus the performance of the system significantly

degrades. Chapter 3 is about frequency synchronization. We will investigate there how much

carrier frequency error can affect in the performance of receiver. In this chapter several frequency

synchronization algorithms will be discussed.

Although OFDM is well known for its ability to combat inter-symbol interference (ISI)

introduced by multipath channel, incorrect positioning of the FFT window within an OFDM

symbol reintroduces ISI during data demodulation, causing serious performance degradation.


Time synchronization is therefore one of the important tasks performed in the receiver. The

problem of time synchronization in MIMO systems is divided into two parts:

• Frame synchronization: The task of the frame synchronization is to identify the preamble

in order to detect a packet arrival

• Symbol-timing: The task of symbol timing is to identify the beginning of the symbol.

Thanks to use of FFT as demodulator in OFDM receiver, the time delay smaller than a symbol

time will be converted to a phase shift in frequency domain and this phase shift can be estimated

in the channel estimation stage. Hence, symbol timing in an OFDM system is to find the exact

place of FFT window or, in other words, the exact beginning of the OFDM symbol. Moreover,

concerning OFDM synchronization, one can find another problem referred as sampling clock

frequency offset. This problem is not investigated in this manuscript due to preliminary

assumption on the precision of clock frequency and small and moderate OFDM frame length.

1.3 Outline and Contribution

1.3.1 Outline

The chapter 2 deals with channel estimation. Data aided methods are discussed first. In the data

aided methods we distinguish the case where a training sequence is used and the case where the

pilots are used. Then, a brief introduction of blind and semi-blind channel estimation methods

will be presented and at the end of this chapter we will see the iterative channel estimation

methods which use that information of data packet to improve the estimation.

Chapter 3 is about frequency synchronization. In this chapter several methods for frequency

synchronization will be presented and compared.

The issue of time synchronization will be discussed in chapter 4. To understand MIMO-OFDM

time synchronization methods, we begin this chapter by speaking about non MIMO-OFDM time

synchronization methods. These non MIMO-OFDM time synchronization methods can be either

MIMO non-OFDM methods or non-MIMO OFDM methods. After a rather long introductory

16 Amir Saemi

section, chapter 4 will address MIMO OFDM time synchronization issue. MIMO-OFDM time

synchronization problem, as it is previously said, is divided into frame synchronization and

symbol timing and each issue will be presented in a separate section.

In Chapter 5, we will present a joint ML synchronization method. Using this method time and

frequency synchronization as well as channel estimation will be performed. To describe this

algorithm first a signal model will be appeared. Then, the algorithm will be presented and finally

the result of this algorithm will be compared to the results of the algorithms presented in the

previous chapter.

Chapter 6 deals with iterative synchronization method by using EM (Expectation-Maximization)

algorithm. This algorithm by using the information of data packet will improve the spectral

efficiency. Also this algorithm can be served in the data-transmission mode for estimating of

parameters. After a signal model, a brief description of EM algorithm will be appeared and then

the EM synchronization algorithm will be explained and simulation results will show the

performance of algorithm.

A multi user version of MIMO-OFDM systems is an interesting issue to consider. Therefore, in

chapter 7, as a perspective, we investigate the problem of synchronization in MIMO OFDMA

systems. In this chapter we will explain how the EM algorithm can be served to tackle this

problem in MIMO-OFDMA systems.

1.3.2 Contribution

1) In Chapter 4 section 4.3.2 we propose some modifications in autocorrelation algorithm to

be served as a symbol timing algorithm. This new algorithm was presented in [7]. This

algorithm was originally designed for flat fading channels but we showed experimentally

in [8] that this algorithm has a rather good performance in frequency selective channels.

2) In chapter 4 section 4.4.2 we propose a new symbol timing algorithm that has been

presented in [5]

3) Chapter 5 is the results of our efforts to develop a ML joint time-frequency

synchronization algorithm. Our initial idea that was to develop a new fine frame

synchronization algorithm has been presented in [6]. Since the algorithm, in its first


version, did not consider CFO, the algorithm has been elaborated in [4] to estimate CFO.

Finally, our results has been submitted in [2] as an invited paper.

4) In chapter 6 we propose a new EM MIMO-OFDM synchronization method. The results

of this algorithm will be published in [9] and submitted as a journal paper in [3]

5) Chapter 7 proposes EM algorithm to tackle the problem of synchronization in OFDMA

systems. The result of this algorithm will be presented in [10]. Moreover, it will be

published in IEEE transaction on wireless communication [1].

18 Amir Saemi


2. CHANNEL ESTIMATION

2.1 Introduction

For channel state information (CSI) acquisition, three classes of methods are available in

literature:

• Data aided methods which rely on training symbols that are known to the receiver.

• Differential ones that bypass CSI estimation by means of differential encoding

• EM and blind methods, which estimate CSI merely from the received symbols

In comparison with training based schemes, differential approaches, by design, incur performance

loss [59], while blind methods typically require longer data records to converge and entail higher

complexity ([75],[76],[77]). On the other hand, the insertion of known training symbols can be

suboptimal and bandwidth consuming but it remains attractive especially when it decouples

symbol detection from channel estimation and thus simplifies the receiver implementation, and

relaxes the required identification conditions ([78]). Training symbols can be placed either at the

beginning of each burst (as a preamble) or regularly through the burst.

2Chapter

20 Amir Saemi

Besides, there are some iterative channel estimation algorithms where a minimal amount of

training is used to provide preliminary channel estimates. These estimates are used as side

information for decoding the unknown data signals. Then, data estimates obtained via decoding

are used as an uncertain training sequence in order to improve channel estimation. This process is

continued in an iterative fashion until some stopping criteria is met.

In this section we investigate data aided methods both in preamble and pilot forms and also in

both OFDM and non OFDM system. Then, we take a look at blind and semi blind algorithms,

and finally we consider iterative channel estimation algorithm and EM approach.

Figure 2 shows the outline of the channel estimation methods.

Figure 2: Outline of the channel estimation

Channel estimation

Data aided Blind and semi blind Iterative and EM algorithms

Preamble based training Pilot based training

TDM

FDM

Preamble symbols are OFDM

symbols

Preamble symbols are non OFDM

symbols


2.2 Data aided methods

2.2.1 Preamble based training

2.2.1.1 Frequency domain preambles

In the packet based MIMO OFDM system in wireless local area networks (LAN), due to the low

mobility in this network, a quasi static channel can be assumed for each packet. Training signals

are thus needed only at the beginning of the packet as in IEEE 802.11 a [79] and Hiperlan/2.

Different articles discuss about the constraints over this training sequence, such as low peak-to-

average power-ratio (PAPR) [80], easy time and frequency synchronization properties, DC offset,

the problem of using subcarriers at high frequencies [61] and so on. There are several papers

which discuss about OFDM training sequence design [60] [61] [62]. Anyway, a very important

question concerning OFDM training sequence is that if we use the preambles in the frequency

domain (i.e. before applying IFFT) or in the time domain (i.e. after applying IFFT), in other

words, if our preamble are itself a OFDM symbol or not. Here, we take a look at [62] as a

frequently cited reference that uses an OFDM symbol as a preamble:

Figure 3: System diagram for a channel estimator

Considering an OFDM system with two transmit and two receive antennas. For every OFDM

symbols, a data block of length 2Nc represented by s[p]: p=0,1,…,2 Nc -1 is transformed into

two data blocks of size Nc using a convenient space-time coding : sn[p]: p=0,…, Nc -1 and

s[p]

s1[p]

s2[p]

r1[p]

r2[p]

ĥnm

22 Amir Saemi

m=1,2.. These two blocks are then modulated using OFDM signaling scheme to generate two

OFDM symbols which propagate simultaneously through lowpass equivalent channel (see Figure

3). In these representations, Nc, p and m are the number of subchannels of the OFDM systems,

subchannel (or tone) index and antenna index, respectively (for simplicity the index for number

of OFDM symbol has been omitted). The frequency domain signal received at the mth receive

antenna after can be expressed as:

2

1

[ ] [ ] [ ] [ ]m nm n mi

r p p s p w p=

= +∑H (1)

where wm[p] denotes the additive zero mean complex Gaussian noise with variance σ2w for p

th

tone and at the mth receive antenna. [ ]nm pH is the channel complex coefficient in frequency

domain for pth tone between nth and mth transmit and receive antenna. These coefficients can be

calculated from the time domain channel taps as:

1

0

[ ] ( )c

Llp

nm nm Nl

p h l W−

== ∑H (2)

where L is the number of nonzero taps of the channel impulse response. c

lNW is equal to

2

e c

j

N

π−

Hence, to obtain [ ]nm pH , we only need to estimate ( )nmh l . Supposing ˆ ( )nmh l the temporal

estimation of ( )nmh l , it is shown [82] that it can be found by

1

1 111 21

212 222

ˆ

ˆ

m m

mm

− =

h uQ Q

uQ Qh (3)

where ˆ nmh is defined as ˆ ˆˆ [ (0), ... , ( 1)]Tnm nm nmh h L= −h and, nn′Q and mnu are defined as:

[ ]

[ ]

1 2

1*

0

1

1 2 , 0

1*

0

( ) [ ] [ ]

( )

( ) [ ] [ ]

(0),..., ( 1)

c

c

c

c

Npl

nn n n Np

L

nn nn l l

Npl

nm m n Np

T

nm nm nm

q l s p s p W

q l l

u l r p s p W

u u L

−−

′ ′=

−′ ′ =

−−

=

= ∑

= −

= ∑

= −

Q

u

(4)

As it can be seen in (3), the problem of channel estimation is reduced to a 2L × 2L matrix

multiplication. Since the preamble is known and the fact that the Q matrix depends only on the

preamble, the inversion operation can be done once and the inverse matrix is stored in receiver.


The vectors unm are the functions of the received signals and the training symbols. It is seen that

here is no constraint over the preamble. However, with a clever design of preamble, the matrix

multiplication can de done more simply. In [81], the authors propose significant-tap-catching

method (STC) in order to reduce the computational complexity. In this method, only the more

significant coefficients are identified and calculated and it is shown that the degradation is not

significant.

There is another method to reduce the complexity proposed in [62]. It proposes that the preamble

for the first transmit antenna be chosen arbitrary. The preambles of other transmit antennas for a

system with Nt transmit antennas are a simple phase shifted of the first one and can be calculated

as:

where /c tL N N L= ≥ and x denotes the largest integer no larger than x. With this

constraint on the preambles, we obtain the following interesting result:

• 0ij =Q for all i j≠

• ii cN=Q I

The condition required is that Nt should be less than or equal to Nc/L. Using equation (3):

1ˆ ( ) ( )nm nmc

h l u lN

= (6)

It is easy to show that ˆ ( )nmh l can be written as a function of u1m alone:

1

1ˆ ( ) ( ( 1) )nm mc

h l u l n LN

= − − (7)

Figure 4 depicts calculated sequences un1(l) for 4 transmit antennas. As it can be seen, by

carefully selecting the relative phase between the training sequence for different transmit

antennas, the effect of the channels, corresponding to different transmit antennas on un1(l) is

shifted to different region. So channel estimation complexity is reduced to the calculation of u.

( 1)

1[ ] [ ]c

L n pn Ns p s p W − −= (5)

24 Amir Saemi

Figure 4 : un1 (l) for OFDM with optimum training sequence [62]

Moreover, Geoffrey Li [62] presented some modification in his algorithm to be able to track the

variation of channel. In fact he used a simplified algorithm to track channel variation without

using pilot symbols (Figure 3):

|h11(l)|

|h31(l)| |h41(l)|

|h21(l)|

|u11(l)|/Nc

|u21(l)|/Nc

|u41(l)|/Nc

|u31(l)|/Nc


By using the same notation as before, for systems with constant modulus modulation,

ii cN=Q Iwe have:

1 1 21 2

2 2 2

1ˆ ˆ( )

1ˆ ˆ( )

m m mc

m m mc

N

N

= −

= − 12

h p Q h

h p Q h

(8)

From the above equation, if 2ˆ

mh is known, then 1ˆ

mh can be estimated without any matrix

inversion. However, neither 2ˆ

mh nor 1ˆ

mh is known but we can use the channel estimation result at

previous time i.e. ( 1)

2ˆ k

m−h , ( 1)

1ˆ k

m−h to substitute 2

ˆmh , 1

ˆmh in the right sides of (8). This substitution

reduces the computational complexity of the channel estimation [62]. It is claimed in this paper

that the performance degradation of the simplified estimation is negligible when the square of

normalized Doppler frequency is much less than the noise power. Furthermore, the simplified

estimator does not require a large matrix inversion; therefore, it has lower complexity and also is

numerically stable, so we can use it in transmission mode.

2.2.1.2 Time domain preambles

Using time domain preambles, the same methods are used for both OFDM and non-OFDM

systems, that is we use either MMSE estimation or Least Square estimation as follows:

2 1ˆ ( )H HMMSE wσ −= +h s s I s r (9)

1ˆ ( )H HLS

−=h s s s r (10)

In these equations

• h is a matrix of size LNt Nr ×1 where Nt and Nr are the number of TX and RX antennas

respectively and L is the length of multi path channel.

• s is an Nc×LNt matrix generated from all the samples in one cyclic extended OFDM symbol

sent by all the TX antennas and all the Nc sub carriers

• r is an NrNc×1 matrix containing the received signals of all the RX antennas for one OFDM

symbol.

• σw is the variance of Gaussian noise

Space–time codes exploit the spatial diversity of multiple antennas to increase the capacity of

wireless links and thus satisfy current demands for higher data rates. The receivers observe the

26 Amir Saemi

superposition of training sequence transmitted through different channels. The preamble based

training sequences that achieve minimum mean square error have an impulse like autocorrelation

sequence and additionally zero cross-correlation. This last property makes the channel estimation

problem different for multiple antenna systems from single antenna system. Training based

estimation for a single-input single-output frequency selective channel has been widely

investigated in the literature (see for example [82] and the reference therein). For frequency

selective channels, a straightforward method to achieve zero cross-correlation is to transmit

training symbols only from one antenna at time, while not transmitting from the other antennas,

as Figure 5 demonstrates for a two transmit antenna system. This approach results in high pick to

average power ratio and hence is undesirable in practice.

Figure 5: A single training sequence transmission scheme for two antennas that achieves zero

cross-correlation

The construction of training sequence with constant envelope can be classified in two main

categories according to the training sequence alphabet size N. the first approach [83] constructs

optimal sequence from an Nth root of unity alphabet AN=exp(i2πk/N), k=0,1,…,N-1, without

constraining the alphabet size N. Such sequences are the perfect roots-of-unity sequences or

polyphase sequences that have been proposed in the literature for different applications (see [84]

and the references therein). For any training sequence length Np, there exist optimal training

sequences that belong to an Nth root-of-unity alphabet. The training sequence length Np

determines the smallest possible alphabet size. Chu [85] shows that for any length Np, there is a

perfect roots-of-unity sequence with alphabet size N=2Np, and Mow [86] shows that for some Np

smaller alphabet sizes are possible.

The second approach in the literature constrains training sequence symbols to belong to a specific

constellation, typically BPSK or QPSK, to have a simpler transmitter/receiver implementation

S1 0

0 S2


[87]. In this case optimal sequence does not exist for all training length Np. Instead, exhaustive

searches can identify suboptimal sequence according to some performance criteria.

The training sequence best suited to particular applications depends on the training sequence

length Np, (which for standardized systems is predetermined), the number of channel taps to

estimate, and the signal constellation used. Perfect roots-of-unity sequences of a predetermined

length may not belong to a standard constellation, while exhaustive searches are, in many cases,

computationally prohibitive. For a system with Nt transmit antennas over frequency selective

channels with L taps each, an exhaustive search must identify Nt training sequence. Fargouli in

[74] presented some way to reduce the amount of exhaustive search. Her main idea is to reduce

problem of designing multiple training sequence with impulse-like autocorrelation and zero cross

correlation to designing a single truing sequence with impulse-like autocorrelation. In fact the

restriction from multiple to a single training sequence makes exhaustive searches more practical

and thus facilitates the identification of good sequences. In some case no search is necessary

since optimal sequences are available from the literature.

2.2.2 Pilot based training

In rapidly fading preamble based training may not work well and this may motivate embedding

training sequence in each transmitted block, instead of concentrating them in the preambles. It is

obvious that by using more training symbols, we achieve less MSE for channel estimation but on

the other hand, given a constant burst length, the use of training sequence reduces the information

symbol count. So there is a trend to link training sequence discussion with channel capacity or

it’s bound. For flat fading channel, Hassibi in [63] showed how training affects the capacity of a

fading channel. With too little training the channel will be estimated improperly. On the other

hand, with too much training there is no time left for data transmission before the channel

changes. The question then is the relation between capacity which can be obtained from a MIMO

channel and the number of symbols attributed to training sequence. We will discuss about

optimum amount of training sequence based on [63] and [64]. We will do it in this subsection as

a preface to pilot design discussion. Then, we will concentrate on the methods to design training

and to arrange them in the burst. This will be done for OFDM and non OFDM system separately

in two following subsections.

28 Amir Saemi

It is shown that the minimum and sufficient (optimum) number of pilot symbols (training

sequence length) is equal to the number of transmitter antennas [63]. This is correct if

optimization over the training and data powers is allowed, i.e., one can use different transmit

power for data and pilots. In the contrary, if the training and data powers are required to be equal,

then the optimal number of training symbol should be larger than the number of antennas.

Figure 6 displays the lower bound of capacity obtained as a function of block length T for

Nt=Nr=10. Nt is the number of transmit antennas, Nr is the number of receive antennas, ρt and ρd

are the SNR during the training and data transmission respectively. The larger the block is, the

ratio of data over pilot is more important, so we achieve to more capacity. As it can be seen by

comparing the curves, a power control over pilot symbols can increase 10-15% the capacity

achieved. Figure 7 displays the optimal number of pilots (Np) in respect of the length of the block

when we can not adjust the power of pilots and we use the same power for pilots and the data.

We see the trend that as the SNR decreases the amount of training increases. It can be shown that

in SNR equal to zero the training amounts increases until it reaches to half of the packet (T/2).

Figure 6: The lower bound in capacity as a function of T (Nt=Nr=10)


Figure 7: The optimal value of Np (Nt=Nr=10)

X. Ma in [64] showed that for a system with T=69, Nr=3, L=6 (L is the channel length) in a

frequency fading channel, when 3≥Nr≥1, the average capacity increase with the number of

transmit antennas (Figure 8). However when Nr>3, the average capacity starts decreasing. This is

because training symbols take over larger and larger portion of the whole transmitted block,

leaving less and less to be used for transmitting information symbols.

Figure 8: Average capacity bound with increasing number of transmit antennas

30 Amir Saemi

Therefore, we found that choosing optimum number of pilots have to be done carefully and also

we saw that if we want use the pilots inside the packets in opposition of common idea that

increasing transmitter antenna will end to more performance, there is an optimum amount for the

number of transmitters.

In the following section we will take a look at the pilot design in OFDM and non-OFDM

systems. Note that in two following subsection we suppose that hnm(l), l ∈ [0,L] is the discrete-

time baseband equivalent channel that includes transmit-received filters as well as the frequency-

selective propagation effects between the nth transmit antenna and mth receive antenna. With τnm

denoting the delay spread between the nth transmit antenna and mth receive antenna, we define the

maximum delay spread as τmax=maxτnm, the maximum channel order is then given by

L:=[τmax/Ts] where Ts is symbol time.

2.2.2.1 Pilot base training for MIMO non-OFDM

systems

Suppose a general multi-antenna system that employs Nt transmit and Nr receive antennas

(Figure 9). At the transmitter, the information bearing symbols having a symbol rate 1/Ts are

parsed into blocks of size Ndata×1. Each block s is first encoded and/or multiplexed in space and

time. The resulting Nt blocks , , , 1 , 11,...,

...data data data data data

t

T

n qN n qN n qN n qN N n Nc c c+ + − = = c (where ,n kc is

transmitted at the kth instant and from nth transmit antenna) have length Ndata and each is directed

to one transmit antenna).

If we want to consider the training symbols in the most general form we can suppose that at each

nth transmit antenna , datan qNc is proceed by a matrix An, so the vector of , datan qNc with length Ndata is

extended to , datan n qNA c with length Nc by matrix An ( Nc×Ndata ). Training blocks ,n qNcb of length Nc,

which are known to both transmitter and receiver, are then added to , datan n qNA c . Now (11) is a

general term for embedding pilots imposed to the data:

, , ,datan qNc n n qN n qNc= +u A c b (11)

Where , , , 1 , 1...c c c c c

T

n qN n qN n qN n qN Nu u u+ + − = u and , , , 1 , 1...c c c c c

T

n qN n qN n qN n qN Nb b b+ + − = b


This affine model is fairly general: it encompasses linear precoding via An as well as inserted

training symbols by having non zero entries of ,n qNcb where , datan n qNA c has zero entries.

Because of channel length we have Inter Block Interference IBI between two adjacent block

, cn qNu and ,( 1) cn q N+u so we have to add something like a guard interval to eliminate IBI. One way

to separate each block , cn qNu from the adjacent one is to insert sufficiently zeros (L) at the end of

each block.

For this purpose we can consider a matrix T which adds redundant (guard) symbol to , cn qNu .

In fact we can multiply T by , cn qNu to model guard interval adding and of course in the receiver

we need to remove this added guard interval. We can model it by multiplying matrix R in the

received vectors (Figure 9). To achieve this, we can select the matrices T and R as follows:

,c c c

T

N N L N L× + = = T I 0 R I (12)

To estimate h, from r (the received vector after removing guard interval) we can use linear

MMSE estimator as follows:

2 1 1( ( )) ( )r r

H Hh N Nσ − −= + ⊗ ⊗h R I B B I B r

) (13)

Figure 9: Discrete time baseband equivalent Tx-Rx MIMO model

r1

rNr

32 Amir Saemi

where Rh=E[hhH] (E(.) means the expected value of (.) )and 1[ ,..., ]=

tNB B B which nB is an

Nc+L × (L+1) Toeplitz matrix having first column , , 1[ ,..., ,0,...,0]c c c

Tn qN n qN Nb b + − and h

) is an

estimation of :1 :: [ ... ]r

T T TN=h h h with : 0 1[ (0)... ( ) ... (0)... ( ) ]

t t

T T Tm m m N m N mh h L h h L=h . Besides,

, , , 1 , 1...c c c c c

T

m qN m qN m qN m qN Nr r r+ + − = r and 1, 2, ,...c c r c

TT T TqN qN N qN

= r r r r

X. Ma in [64] has discussed that it is better to decouple channel estimation from symbol

decoding. She argues that without being decoupled we encounter the following problems:

- The nonlinear search required is not only computationally complex but also its

convergence to a globally optimum solution is not guaranteed.

- Symbol identifiability can not be ensured in general.

- The designed training sequence will be tailored for only a specific encoder.

Since in the r there are unknown symbols in addition to the training sequence we can not use

(13) to estimate channel. In [64] it has been proved that in order to decouple channel estimation

from symbol decoding, the superimposed model ( ), , ,datan qNc n n qN n qNc= +u T A c b results to time

division multiplexing (TDM) of the ST blocks cn with the training symbol blocks bn.

,

data

c

c data data

N L

n n qNN N N n

+

− ×

= =

0ΘA b

0 b (14)

where bn contains all the non zero entries of bn,qNc and ΘΘΘΘ is an Ndata × Ndata matrix that optionally

precodes (if ΘΘΘΘ ≠ INdata) the information bearing block , datan qNc linearly. Certainly TDM ensures

decoupling, but the inverse is not obvious and it has been proved in [64].

Besides, in order to minimize channel mean square error it can be proved that the training

sequence across transmit antennas have to be orthogonal. The optimal parameters of training

sequence such as training length , power allocation has been derived in [64] by maximizing

channel capacity when the source data is Gaussian and remains Gaussian after ST-mapper also

(in ST-mappers as BLAST type multiplexer, block codes and even other codes when the block

size is large). The optimal number of training sequence is Nt(L+1) and the optimal power

allocation factor is : ( 1)

data

data t

N

N N L+ +. Figure 10 shows the optimal training sequence which

purposed by [64].


Figure 10: Training scheme example (Nt=3)

2.2.2.2 Pilot base training for OFDM systems

We use the same model as previous section (Figure 9). There is only one difference for the

OFDM systems for separating different block in multi path channel. Here instead of having zeros

at the end of each block, cyclic prefix is used. In fact instead of adding L zeros at the end of each

block un, in previous model an alternative way to eliminate IBI is by adding a cyclic prefix (CP)

of length L at the transmitter, and removing it at the receiver, so instead of (12) we have:

,c c c

T T

CP N N L N× = = T I I R 0 I (15)

where ICP contains the last L columns of INc.

In fact in an OFDM system we have the same consideration as previous section as to decouple

channel estimation from symbol detection. We can estimate channel linear MMSE estimator as

(13). Here in OFDM systems Ma has proved that for decoupling channel estimation from symbol

detection instead of equation (14) we have to respect this criterion:

,c c

H Hn N A n N b n= =A F P Θ b F P b (16)

Where F is Fourier matrix, ΘΘΘΘ is a Ndata×Ndata matrix that optionally precodes (if ΘΘΘΘ ≠ Itd) the information bearing block , datan qNc linearly. bn consists of the L possibly non zero training symbol

from the ith transmit antenna, and permutation matrices PA, Pb satisfy ( )A data c data

Tb N N N× −=P P 0 in fact

the permutation matrices play the role of assigning carriers to each (possibly precoded)

information symbol and training symbol (pilot tones). As a result, in order to decouple the

channel estimation and symbol detection the superimposed model boils down to frequency

division multiplexing (FDM) the ST codewords , datan qNc with the training blocks bn. Also

according to [64] in order to minimizing MSE one can result that one pilot tone can not be shared

Ndata

34 Amir Saemi

by more than one non zero training symbols on different transmit antennas in other words, the

non zero pilot tones across the Nt transmit antenna are mutually orthogonal. In this case also like

non OFDM system as the number of non-zero pilot tones increases, the capacity lower bound

decreases. Therefore, the number of non-zero pilot tones should be chosen to the minimum

possible i.e. L+1 per transmit antenna. The optimal power allocation factor is

( 1)

data c

datadata t

N N

NN N L+ + where the length of cyclic prefix is Nc-Ndata. In [65] by optimizing a

lower bound on channel capacity, the optimal amount of resource allocated to the pilot symbols

have been derived in varying fading Rayleigh channel. Figure 11 shows an optimal training

sequence which purposed by [64].

Figure 11: Training scheme example (Nt=3, L=3)

2.2.3 Comparison between preamble based

training and pilot based training

Here by using [64] we are going to compare pilot base training (section 2.2.2.2) and preamble

base training 2.2.1.1). Figure 12 shows that with the same power per training block, in quasi

static channels, both of them achieve similar channel MSE.


Figure 12: Channel MSE comparison (Nt=2,Nr=1 and L=6)

Figure 13 plot the channel MSE for the three cases when the channel is slowly time-varying.

Each channel tap is generated by Jakes’ model with a terminal speed of 3, 5, 10 m/s, and a carrier

frequency of 5.2 GHz. The variances of channel taps satisfy the exponential power profile. To

maintain the same information rate, every training block is followed by four information blocks

for the preamble scheme of 2.2.1.1 .Figure 35 shows the channel MSE versus the number of

transmitted blocks for the two schemes at SNR= 10dB. Although the channel is slowly time-

varying, the MSE of the scheme of section 2.2.2.2 remains invariant from block to block, while

that of 2.2.1.1 increases very fast. Note that the scheme of 2.2.1.1 yields smaller MSEs at the

beginning of each re-training burst, because the total transmitted power is used for training.

Figure 13: Comparison of the channel MSE (Nt=2,Nr=1 and L=6)

36 Amir Saemi

2.3 Blind and Semi blind methods

Existing blind channel estimation methods for OFDM system can be classified as pre DFT (time

domain) methods post DFT (frequency domain) methods. Pre DFT methods explore the

cyclostationarity that the cyclic prefix induces to the transmitted signal. They recover the channel

using cyclic statistics of the received signal [73] or subspace decomposition of the correlation

matrix of the pre DFT received blocks [93].

The post DFT methods process the post DFT received blocks, and exploit the finite alphabet

property of the information bearing symbol. Besides several papers which apply a transformation

to blocks of symbols before they enter the OFDM system, and they perform channel blind

estimation at the output of the OFDM system via cross correlation operations ([66] and its

references).

Also there is some articles which use the redundancy of space-time coded signals to apply

subspace method in [94] in order to channel identification [67] [95].

In semi blind channel estimation we encounter two approaches. In the first approach a

combination between data aided methods and blind methods is used. In fact pilot symbols as

known symbols used to estimate the channel coefficients but since there are a number of channel

coefficients, a large number of pilot symbols may be required. It would result in a decrease of

data throughput. To avoid it, the semi blind channel estimation methods with fewer pilot symbols

can be used. For example Choi in [67] by using a L × Nt pilot symbol (the minimum number of

know data to avoid ambiguity) present a semi blind method that improve channel estimation MSE

in comparison with using equal pilots in LS (Least square) method. Although there are other

approaches for the semi blind method as in [96].

In the second approach in semi blind methods in MIMO channel estimation, there is a trend to

use superimposition of pilot and data symbols[68][69]. In fact, these methods by superimposing

pilot and data symbols in the same time economize the bandwidth.

Since the blind channel estimation is time-consuming and complicated, it seems that for practical

purpose it can not be suitable.


2.4 Iterative channel estimation

The channel estimates can be improved if the estimation process is included in the iterative

receiver chain, and the channel is re-estimated in several iterations, using not only the training,

but also information on the data symbols obtained from decoder in the feed back loop. Such

iterative estimation of the frequency flat fading channel in SISO system is considered in [97][98].

A solution to the corresponding problem in MIMO system is proposed in [71], where the channel

estimate is updated in each iteration using hard decisions on the data symbols obtained from the

decoder. For getting the initial estimation of channel one can use the TDM pilot symbols;

however there are some other solutions like using pilot embedding as in [73]. In fact [73] propose

transmission of pilot symbols that are transmitted along with data. These pilots, which are at a

level much lower than signal level, are used to obtain the initial coarse estimates of the channel.

The idea of pilot is transmitting of pilots symbol The idea of pilot embedding was first proposed

in [99] in the context of single input single output single carrier systems and has been extended to

multicarrier systems [100]. The initial work in [100] uses pilot symbols to obtain an initial

estimate of the channel so that subsequently the receiver can work in a decision directed mode for

tracking. In [100] pilot symbols are used to initialize an iterative joint channel estimation and data

detection loop in an OFDM system. [73] extends the idea of pilot embedding to ST turbo coded

systems.

Using Expectation-Maximization (EM) algorithm is a good way to profit the information of data

symbols and perform channel estimation iteratively. In [124]-[128] one can find the general

explanation and discussion about EM-algorithm and its application to the estimation problem.

Xie in [130] propose two EM type channel estimation algorithm in OFDM system to convert a

multiple-input channel estimation problem into a number of single-input channel estimation

problems, a much more palatable problem. EM algorithm we calculate channel in two steps: At

the E-step it estimates the corresponding component in the received signal for each of the OFDM

links. At the M-step, as in the conventional OFDM scheme, it divides the corresponding

component by the reference symbol (either known from training, or previously decode symbols)

in the frequency domain and performs an inverse fast Fourier transform (IFFT) to obtain an

updated estimate of channel impulse response. For high speed wireless data packet applications,

if a data packet is short compared to the channel coherence time, channel fading can be assumed

to be the same for the whole packet, for each transmitter, one or two pilot symbol can be at the

beginning of each packet. In [130] two different EM-algorithm, classical EM algorithm and

SAGE algorithm, has been compared with each other in terms of convergence and it has been

38 Amir Saemi

shown that the convergence rate of both algorithm are unrelated to the channel delay profile and

the. In [118] an iterative MIMO-OFDM receiver has been presented that use ML channel

estimation based on EM algorithm.

Finally in [120] there is an interesting approach to perform joint channel estimation and frame

synchronization in MIMO systems in flat fading channel based on EM algorithms. We will

discuss more about the EM algorithm in chapters 6 and 7.


3. CARRIER FREQUENCY OFFSET

ESTIMATION

3.1 Introduction

One of the most important tasks in a MIMO-OFDM receiver is frequency synchronization. As a

matter of fact, even a very small frequency offset in a MIMO-OFDM system can destroy the

orthogonality between the sub-carriers and as a result performance of the system degrades

significantly. In this chapter we are to summarize the best existing methods for MIMO frequency

synchronizations in unknown channels. Four recent algorithms for MIMO frequency

synchronization is collected in this chapter. For each method, first we will state its specification,

and then we will describe the algorithm. In the next section we perform some simulations to

compare these algorithms and in conclusion we compare these algorithms with each other.

3Chapter

40 Amir Saemi

In this chapter we suppose that we have an Nt×Nr MIMO-OFDM system. The channel is

frequency selective with length L. Each OFDM symbol is composed of Nc subcarrier and Ncp

cyclic prefix.

Before simulation of our methods, we might like to have a sense about maximally tolerated error

of frequency synchronization in a MIMO-OFDM system, that is, how much carrier frequency

error can be left as a residue without degrading performance or with acceptable performance

degradation. Concerning this subject, we investigate the relation between carrier frequency offset

and bit error rate (BER) of a 2 × 2 STBC-OFDM system. For the simulation setup we considered

an OFDM symbol with length 64 and a cyclic prefix for each OFDM symbol with length 8. Also,

an exponentially decaying channel power delay profile of length 8 is used.

Figure 14 and Figure 15 represent such a relation. Figure 14 depicts the BER of a MIMO-OFDM

system in terms of Eb/N0 for various residual carrier frequency errors. Figure 15 represents BER

of a MIMO-OFDM system in terms of carrier frequency offset for various EbN0s. In these

figures, CFO or ε is the multiplication of frequency error by sampling time: i.e. CFO (or ε)

≡ ∆f × Ts (Ts is sampling time). Based on Figure 15, one can claim that for a system with this

setup the residual carrier frequency error must be less than 10-4 to have no sensible degradation

over BER.


Figure 14: BER vs Eb/N0 for various existing CFOs in a 2×2 STBC-OFDM system

Figure 15: BER vs CFO for various Eb/N0 in a 2×2 STBC-OFDM system

42 Amir Saemi

3.2 Carrier frequency offset estimation

In this section we present and compare some good carrier frequency offset estimation methods

which are presented in literature or developed by us. For each method its algorithm will be

described and then its specification will be outlined.

3.2.1 FFT method by using frequency domain

training sequence

In this method appeared in [118], using FFT, carrier frequency offset can be estimated from the

preamble.

3.2.1.1 Description of method

Let the training sequence at the pth subcarrier of the nth transmitter be Bn[p] and the received

vector in frequency domain of mth receiver be Rm[p]. In [118] only a 2×Nr MIMO system was

considered but it seems that this method is extendable over MIMO systems for Nt>2. We assume

that at each transmitter, K out of the total of Nc OFDM subcarriers are used to transmit symbols.

This is different from inserting guard interval in OFDM systems, because nothing is transmitted

from the remaining (Nc − K) subcarriers. This truncated observation window of subcarriers is

need for good estimation of the carrier frequency offset (CFO). The MIMO OFDM system model

subject to CFO can be written as:

:

1,...,

Im N K KL m m

rm N

= +=

R W EW BW h Z

(17)

with

[ ]1

[0], [1],..., [ 1]c

T

m m m m c NR R R N

×= −R

(18)

(2 / ) (2 ( 1) / )(1, ,..., )c c cj N j N Ndiag e eπε πε −=E (19)

0 1 2( , )K K×=B B B and (20)

0 0 0 0( [0], [1],..., [ 1])K Kdiag B B B K ×= −B (21)


1 1 1 1( [0], [1],..., [ 1])K Kdiag B B B K ×= −B (22)

[ ] (2 / )

,

1,

0,1,..., 1 ; 0,1,..., 1

cj N rsN r s

c

c c

eN

r N s N

π−=

= − = −

W

(23)

(2 / )

,

1,

0,1,..., 1 ; 0,1,..., 1

cj N rsIK r s

c

c

eN

r N s K

π =

= − = −

W

(24)

2 2( , )KL KL KL K Ldiag ×=W w w (25)

2 2( , )KL KL KL K Ldiag ×=W w w (26)

[ ] (2 / )

,,

0,1,..., 1 ; 0,1,..., 1

j N rsKL r s

e

r K s L

π−=

= − = −

w

(27)

0 1:2 1

(0), (1),..., ( 1)

m m

nm

TT Tm L

T

nm nm nmh h h L

× =

= −

h h h

h

(28)

where ( ), 0,1,..., 1nmh l l L= − is the fading coefficient of the lth tap associated with the nth transmit

antenna and mth receive antenna. Zm denotes the additive with Gaussian noise at each receive

antenna. The carrier frequency offset (CFO) ε is introduced through the matrix E, since E≠INc for

ε≠0, orthogonality among all Nc subcarriers is destroyed. W represents the DFT matrix.

In the receiver, first of all, we remove the cyclic prefix. Let the received signal after removing

cyclic prefix at mth receive antenna in the kth instant be rm(k). For ML CFO estimation one have to

write the ML criterion as follows:

( )1

argmax log ( | , )rN

m mm

pε

ε ε=

=

∑ R h (29)

Since the channel coefficients are unknown, we have to eliminate them. To this purpose, as EM

algorithm, we calculate the expectation of the probability function over h i.e.

2| ,

1

argminr

m m

NI

m N K KL mm

E εε

ε=

= −

∑ R R W EW BW hh (30)

Using this approach, after some simplifications and approximations, CFO, ε, can be estimated as

[118]:

ˆ argmin ( )ε

ε ε= Ψ (31)

44 Amir Saemi

( )( ) ( )Fε εΨ = ℜ (32)

12

1

( )cN

j ss

s

F r e πεε−

−

=

′= ∑ (33)

, ,

1*

,

1 0

[ ]cr

m p k m p s k

N sN

s p p sm p

r r r+ + +

− −

+= =

′ =∑ ∑ T (34)

H=T S S (35)

( )(2 / ) I H H IHK KL KL KK= −S I W BW W B W (36)

Therefore, for frequency synchronization first we calculate matrices S and T (eq. (36) and (35) )

(which are constants and can be calculated only once) and at the receive antennas after packet

arrival, we remove cyclic prefix and then by using T, the coefficients , 1,..., 1s cr s N′ = − can be

calculated (eq. (34) ). Eq. (33) is similar to Discrete Fourier Transform and so E can be easily

calculated by Fast Fourier Transform (FFT) algorithm. Better frequency resolution can be

achieved by zero-padding to effectively increase the length of symbol sequence. The minimum of

real part of Fourier transform indicates the estimated carrier frequency offset, ε .

3.2.1.2 Specifications

i. This method is a frequency-time domain method i.e. at the transmitter, training sequence

is inserted in the frequency domain (before IFFT operation). At the receiver frequency

estimation is performed based on time domain received signal. (cyclic prefix is removed

before applying this method )

ii. Time synchronization (frame synchronization + symbol timing) has to be done before

this method.

iii. One OFDM word (with its cyclic prefix) is used as training sequence in the beginning of

each packet, the structure of training sequence and information blocks can be seen in

Figure 16.


iv. For frequency synchronization orthogonality between preambles is not supposed but for

channel estimation the orthogonal preamble was used according to [62]

v. The criterion is derived by supposing SNR>0 dB [118].

vi. For frequency synchronization, at each transmitter, K out of the total of Nc OFDM

subcarriers have to be used to transmit symbols (this is different from inserting a cyclic

prefix for each OFDM word) e.g. if we have Nc=128 we can choose K=120.

vii. The fading multi-path channel is considered to be quasi static

viii. The only constraint over the length of the channel is that it must be less than cyclic

prefix length.

ix. After frequency offset compensation channel can be estimated using [62].

x. This method is designed for an EM based iterative receiver.

Figure 16: Data burst structure for FFT method.

3.2.2 Hopping pilots method

In this method appeared in [114], by inserting hopping pilots into information block, CFO can be

estimated in frequency domain.


Let , , , 1 , 1...data data data data data

T

n qN n qN n qN n qN Nx x x+ + − = x be the qth information block at nth transmit

antennas where ,n kx is the kth sample transmitted from the nth transmit antenna. Also, let

46 Amir Saemi

, , , 1 , 1...data p p p p

T

n qN n qN n qN n qN Nb x x+ + − = b the qth training block at nth transmit antennas. Ndata and

Np is the number of information symbol and training symbol per block respectively. At the

transmitters, we insert Nt training symbol 1

( ) tN

n nk

=b in the information blocks corresponding to

the Nt transmit antennas ,1

t

data

N

n qN n=x , as follows:

, , ,data datan qK A n qN B n qN= +u x b% P P (37)

where ( )%n ku contains both information-bearing symbols and training symbols. PA and PB are two

permutation matrices with sizes N×Ndata and K×Np respectively (K is the number of non-zeros

subcarriers), and are selected to be mutually orthogonal: ×=data p

TA B N N0P P . Note that Ndata+Np=K

and K<Nc (Nc is the number of subcarriers). One example of permutation matrices is to form PA

with the last Ndata column of p dataN N+I and PB with the first Np column of

p dataN N+I , given as:

-1 0 -1 ... and ... p pA N K B N

= = P e e P e e (38)

e is a zero vector with a one corresponding to its index. Afterwards, we insert Nc − K zeros per

block to obtain , cn qNu . This insertion can be implemented by left-multiplying ( )%n ku , with the null-

subcarrier insertion matrix:

, ,

(mod ) -1(mod )

( )

( ) [ , ... , ]

c

q c q c

n qN sc n qK

sc v N v K N

q

q +

=

=

u u% %T

T e e (39)

Where vq=q[Nc/(L+1)] (L is the channel length). Dependence of the null-subcarrier insertion

matrix Tsc on the block index q implies that the position of the inserted zero is changing from

block to block. In other words, (39) implements a null-subcarrier hopping operation from block to

block.

Subsequently we perform the standard OFDM operations of IFFT and CP insertion per transmit

antenna. We perform CFO estimation at receivers as follows:

Let the qth received vector with length Nc at mth receive antenna after removing cyclic prefix be

rm,qNc. We collect P vector namely ,1c

P

m qN q=r . We multiply each vector by dehopping

matrix ( )c

HN qD :

, ,( )c c c

Hm qN N m qND q=r r (40)

where:


2 2 ( 1)

( ) 1, ,...,

q q c

c c

c

v v Nj jN NH

ND q diag e e

π π −− −

=

(41)

CFO destroys the orthogonality among subcarriers, and the training information is mingled with

the unknown symbols and channel. The dehopping matrix makes the null subcarriers in different

blocks done at the same location.

Then, we form the covariance matrix of , cm qNr averaged over M blocks (M ≥ K).

1

, ,

0

1ˆm c c

MH

r m qN m qNqM

−

=

= ∑R r r (42)

It has been shown that the column space of ˆmr

R consists of two parts, the signal subspace and the

null subspace. In the absence of CFO, the null space of ˆmr

R is spanned by the missing columns

(the location of the null subcarriers) of the FFT matrix. The presence of CFO introduces a shift in

the null space. A cost function can be built to measure this CFO-induced shift for MIMO-OFDM

setup. CFO can be estimated by minimizing the cost function by the following equations:

ˆ argmin ( )Jε

ε ε= (43)

11

1

2 2ˆ( ) ( ) ( ) ( ) ( )c r

c c m c c

N NHN N r N N

s K mc c

s sJ

N N

π πε ε ε−

−

= =

=

∑ ∑f D R D f (44)

where:

[ ]( ) 1,exp( ),..., exp( ( 1) )c

T

N cj j Nω ω ω= −f

[ ]( ) 1,exp(2 ),..., exp(2 ( 1))cN cdiag j j Nε π ε π ε= −D

(45)

Complexity of the estimator in (43) depends on the number of points searched over the interval

[ ),π π− and so as usual, there are tradeoffs emerging among complexity acquisition range and

variance of the CFO estimator. The finer the search, the higher the complexity one incurs.

48 Amir Saemi

Figure 17: One example of training structure


i. This method is a frequency-time domain method. That is, at the transmitter training

sequence is inserted in frequency domain before IFFT operation but at the receiver

frequency synchronization is performed based on time domain received signal. Cyclic

prefix is removed before applying the method.

ii. Time synchronization (frame synchronization + symbol timing) has to be performed

before applying this method

iii. In each OFDM word we have to insert at least Nn hopping null subcarrier and to perform

frequency synchronization we have to use M≥Nc-Nn words, the structure of OFDM word

can be seen in Figure 17.

iv. The channels remain time-invariant during M blocks.

v. This method is highly dependent on training symbols design.

vi. This method is flexible to adjust the training sequence, depending on the channel’s

coherence time and the pertinent burst duration; e.g., if the burst is long, we can insert

fewer symbols per block.

vii. A phase estimation method is presented in [114] asserting that it leads to BER

performance enhancement.

viii. Using the structure of training sequence presented in [78], the channel can be estimated

as well.

0

Null

0

0

Training Information

1th

block

2th

block

3th

block


3.2.3 Iterative method

In this method, using time domain training sequence, CFO can be estimated in two stages: in the

first stage a rough estimation is calculated by using FFT and then in the second stage in an

iterative manner fine frequency estimation is provided.

This algorithm is developed by us and presented for the first time in [4] and then will be

published in [2]. We will describe this method in detail in Chapter 5. But here to cover all of the

good CFO estimation methods we will outline the algorithm without mathematical proof.


Supposing that time synchronization is already performed. Let the training sequence of nth

transmit antenna be ,0 ,0 , 1[ ... ]−Pn n n Nc c c (NP is the length of training sequence) and the received

signal at mth receive antenna and kth instant be rm(k). If the length of the cyclic prefix for the

OFDM symbol is NCP, we have , , 1 , , 1[ ... ] [ ... ]− − − −≡CP P CP Pn N n n N N n Nc c c c as the cyclic prefix of

training sequence.

In the first step, CFO is estimated by FFT method. To this purpose we define matrix ΦΦΦΦ as

follows:

1( )H H−= C C C CΦΦΦΦ (46)

where:

1 2 ...t

p tN N LN

C C C×

= C (47)

,0 , 1 , 1

,1 ,0 , 2,

, 1 , 2 ,

...

...

. . . .

...p P P

p

n n n L

n n n L

n

n N n N n L NN L

c c c

c c cC

c c c

− − +

− +

− − − + ×

=

(48)

Now, CFO, ε , is the maximum of real part of Fast Fourier Transformation (FFT) of [ ] 1

1

−

=′ pN

s sr ; That

is:

50 Amir Saemi

[ ]( )( )1

12

11

ˆ argmax argmax FFTπε

ε εε

−−−

==

′ ′ == ℜ = ℜ ∑p

p

NNj s

s s ss

r e re e (49)

where:

, ,

1

*

,

1 0

[ ]pr

m p k m p s k

N sN

s p p sm p

r r rφ+ + +

− −

+= =

′ =∑ ∑ (50)

and (.)ℜe denotes the real part of (.).

Better frequency resolution can be achieved by zero-padding to effectively increase the FFT

length but for initial estimation, a 512-FFT point FFT would be sufficient. After frequency

compensation, channel can be estimated as follows:

1[( ) ( )] ( )−= ⊗ ⊗ ⊗)

r r r

H HN N Nh I C I C I C r (51)

where 1 2 1

...×

= Nr

p r

TT T T

N Nr r r r and

1(0) (1) ... ( 1)

× = −

p

T

m m m m p Nr r r Nr .

In the next step we are going to estimate the residual frequency in an iterative manner. To this

purpose we use the channel estimated in (51) and we re-estimate ε by using a cross correlation

method: we define 1

*

0

( ) ( ) ( )N s

p

r s y p y p s− −

=

′′ = +∑ and : 0 ,0

1

( ) ( ,:) ( )=

=∑)rNH Hm m

m

y s s sh C r where ( ,:)H sC is

sth row of matrix C (eq. (48)) and : 1 21

...×

= tt

TT T Tm m m N m LN

h h h h ,

[ ]1

(0) (1) ... ( 1)×

= − T

nm nm nm nm Lh h h Lh . ε can be calculated as follows:

1

1

1

2

1

( ) arg( ( ))1

ˆ2

( )

επ

−

=−

=

′′ ′′=

′′

∑

∑

p

p

N

sN

s

s r s r s

s r s

(52)

We have to note that because of presence of the arg(.) in (52), ε is ambiguous when arg( ( ))r s′′

exceed π. This limits ε to be less than 1/2Np.

Now algorithm can be expressed as follows: in the first stage we estimate arrival packet instant,

the channel coefficients, and CFO (as describe in eq. (49)), after compensating CFO, the channel

can estimated (51) and then residual CFO can be estimated by eq. (52). Estimating residual CFO,


the channel can be re-estimated by (51). Better channel estimation leads to better CFO estimation

and so we re-estimate CFO by eq. (52). This procedure is performed for several iterations.


i. This method is time domain i.e. both at the transmitter and at the receiver we deal with

the time domain signals.

ii. Time synchronization (frame synchronization) can be incorporated in this method.

iii. One preamble is used as training sequence in the beginning of each packet.

iv. For frequency synchronization (and incorporated time synchronization) orthogonality

between preambles is not supposed.

v. The fading multi-path channel is considered to be quasi static and the length of the

channel must be less than cyclic prefix length.

vi. This method incorporates an estimation of channel coefficients.

vii. This method presents a very accurate and rather complicated CFO estimator

3.2.4 Autocorrelation method

In this method presented in [111] CFO can be estimated by autocorrelation of two same

consecutive preambles.


Let the received signal at mth receive antenna and kth instant be rm(k). To estimate CFO, we

calculate the correlation function over received signal and delayed version of it. This operation

should be done in the maximum of the correlation function. The correlation function Λ is defined

as:

0

1*

01

( ) ( ) ( )pr

m NN

m m pm k k

k r k r k N+ −

= =Λ = −∑ ∑ (53)

The estimated frequency offset ε is the phase of autocorrelation function in its maximum, it can

be given by:

52 Amir Saemi

max max( )ˆ

2 2

k s

P s P

f k

N T N

θε

π π∠Λ= =

where ( )k kθ = ∠Λ indicates the phase of Λ(k) and Λ(k) reaches to its maximum at kmax,

1/=s sf T is sampling frequency.

In this method the preambles on the different TX antennas have to be orthogonal and shift-

orthogonal for at least the channel length. To meet these requirements reference [111] proposes

the use of constant envelope orthogonal codes with good periodic correlation properties, such as

Frank-Zadoff codes [112] and reference [47] proposes the time orthogonal codes as shown in

Figure 18 (see 4.3.1).

Figure 18: Two identical consecutive preambles


i. This method is a time domain method i.e. both at the transmitter and at the receiver we

deal with the time domain signals.

ii. Time synchronization (frame synchronization) can be incorporated in this method easily.

iii. Two same consecutive preambles are used as training sequence in the beginning of each

packet. (Figure 18)

iv. For frequency synchronization (and incorporated time synchronization) different

preambles have to be orthogonal and each preamble has to be shift-orthogonal and so the

challenge in this method is to find appropriate preambles.

v. This method is performed before removing cyclic prefix and this methods works well

even if the time synchronization has an error within the cyclic prefix.

vi. The fading multi-path channel is considered to be quasi static and the length of the

channel must be less than cyclic prefix length.

vii. This method reduces the spectral efficiency.

viii. This method provides a very simple CFO estimator with a rather good accuracy.

2NCP NP NP

Data

Ntrain

2NCP NP NP

Data

Ntrain

TX1

TX2


METHOD Number of complex multiplication A typical order

FFT 2 ) 2 log− +rN N N R R( 10

4

Hopping pilots 2 3 2 2( ) 2rN N N N N N R+ + + + 10

7

Initial estimation 2( 3 2) 2 logrN N N R R− + + 10

4

Iterative: Each iteration

2)

2

+ + r t

N NNN N L

( 10

3

Autocorrelation rNN 102

Table 1: An approximation of required complex multiplication to implement

the methods

3.3 Comparison and conclusion

Table 1 represents an approximation of required complex multiplication to implement the

presented methods. In this table R stands for selected resolution in the algorithm, e.g in FFT

method with a 512 FFT length, R is 512, and N stands for preamble length for example a typical

order is 64. Nr and Nt are typically equal 2.

According to Table 1 the simplest method is autocorrelation method and the most complicated is

hopping pilots method. Table 2 represents a brief comparison between different methods. In this

table we see a column dedicated to accuracy of these methods. The accuracy of these methods

will be illustrated in chapter 5 section 5.4.3 by numeric simulation. FFT method, as stated in the

table, has a good spectral efficiency with a rather simple implementation, it can be incorporated

in an EM receiver (as described in [118]) but it has a rather poor accuracy. Hopping pilots

method is a rather complicated method and with increasing its complexity it can be more

accurate. This method would be suitable if one perform synchronization with inserting the pilots.

Iterative method has a good initial estimation and by several iterations its MSE can be reach to

Cramer-Rao lower bound (it will be calculated in 5.4.1). It can be also incorporated into time

synchronization algorithm (see chapter 5 ). However, the disadvantage of this algorithm is its

rather high complexity. On the other hand, autocorrelation method is a very simple method and

54 Amir Saemi

its MSE is near to Cramer Rao lower bound. It is rather robust against timing error and can be

incorporated in time synchronization method. The disadvantage is that we have to force the

preambles to be consecutive and also orthogonal. If we use time orthogonal code spectral

efficiency is poor otherwise we have to generate orthogonal and shift orthogonal preambles.

Altogether, it seems the best methods for MIMO frequency synchronization is either

autocorrelation or iterative method but our final decision depends on the selected time

synchronization method and performance of the complete synchronization system.

University of Limoges, XLIM/C2S2/ESTE UMR CNRS 6172, ENSIL 55 55

Table 2: Comparison between different methods

METHODS COMPLEXITY ACCURACY* SPECTRAL

EFFICACY DOMAIN

TIME

SYNCHRONIZATION ORTHOGONALITY

FFT method by using

frequency domain

training sequence

Intermediate Rather Poor Rather good Frequency-

Time

Time synchronization must

already be done Not required

Hopping pilots method High

Good

more complexity more

accuracy

Rather good

inserted pilots

Frequency-

Time

Time synchronization must

already be done Not required

Iterative method Intermediate Excellent Good Time-Time Can be joint with time

synchronization Not required

Autocorrelation

method Low Very good Rather poor Time-Time

Can be joint with time

synchronization Required

* The simulations are described in chapter 5 section 5.4.3

56 Amir Saemi


4. TIME SYNCHRONIZATION

4.1 Introduction

The problem of time synchronization in MIMO systems is divided into two parts:

• Frame synchronization: The task of the frame synchronization is to identify the

preamble in order to detect a packet arrival

• Symbol-timing: The task of symbol timing is to identify the beginning of the symbol.

Symbol timing in an OFDM system is to find the exact place of FFT window or, in

other word, the beginning of the OFDM symbol.

The task of frame synchronization for both MIMO and MIMO-OFDM systems is same and so

the same algorithms are used for both MIMO and MIMO-OFDM systems. In contrary, the

4Chapter

58 Amir Saemi

problem of symbol timing is different for MIMO and MIMO-OFDM systems. This difference is

due to different definition of the symbol in MIMO and MIMO-OFDM systems. In fact, an

OFDM symbol is composed of several sub-carriers and thanks to Fourier transformation the

time offset smaller than sampling time can be absorbed as a phase offset in the channel

coefficients whereas in a non-OFDM MIMO system the major task of a symbol timing

algorithm is to find the time offset smaller than sampling time. In other words, if we suppose

that the received signal is sampled at t=kTs+η0Ts, where Ts is the sampling rate, and η0 ∈ [0,1)

is the unknown time offset induced by the combination of channel delay and the sampling

phase offset, in OFDM systems η0 after Fourier transformation will be appeared a channel

phase and thus, contrary to non-OFDM systems, we do not need to estimate η0. On the other

hand, MIMO symbol-timing synchronization for non OFDM is an important issue in space-time

coding systems because perfect symbol timing at the receiver is usually assumed in literature.

The goal of this chapter is to present the different approaches to MIMO-OFDM time

synchronization. Since MIMO-OFDM time synchronization approaches are quite influenced by

non MIMO−OFDM time synchronization methods, we will first look at some well-known non

MIMO−OFDM time synchronization methods that are designed either for MIMO non-OFDM

or for SISO OFDM systems. After this rather long introductory section on non MIMO−OFDM

approaches, the different methods for MIMO-OFDM time synchronization will be discussed


4.2 non MIMO-OFDM time synchronization

4.2.1 MIMO non-OFDM time synchronization

The same methods that are generally used for MIMO frame synchronization are employed for

MIMO-OFDM frame synchronization too. Therefore, the difference between MIMO time

synchronization and MIMO-OFDM time synchronisation is due to different methods used for

symbol timing. Hence, here we take a look at the problem of symbol timing in MIMO and not

MIMO-OFDM systems. However, these ideas can be used also for MIMO-OFDM time

synchronization.

Apparently, the synchronization of MIMO systems might seem closely related to the symbol

timing estimation in single-input-single-output (SISO) systems. In MIMO systems, the

synchronization problem takes a special form because signals from different antennas are

superimposed together, and the symbol timing estimation algorithms commonly proposed for

SISO systems do not work well in MIMO systems. Furthermore, in MIMO systems, training

sequences must be used to estimate simultaneously a number of channels. This opens up two

questions. How can we make use of the training sequences to perform symbol timing

estimation? What kind of training sequences is beneficial to symbol timing estimation?

The problems that we have to handle in symbol timing are as follows:

How to estimate the timing delay in MIMO system for the case i) when the transmitted data is

assumed to be known, ii) and when it is unknown? iii) How to design optimal training

sequences in data-aided case in order to get the best estimation performances?

In this section, we divide MIMO symbol timing problem into two parts: the blind or non data

aided approaches and the data aided ones

Symbol timing synchronization in MIMO uncorrelated flat fading channel was first studied by

Naguib [50]; where the timing delay is estimated by selecting the sample with maximum

amplitude from the oversampled approximated log-likelihood function. This algorithm was

extended in [51] to increase its estimation accuracy and the authors again generalize the

algorithm in [54]. On the other hand, because of the problem of identifying training sequence

60 Amir Saemi

epoch, non data aided methods are also interesting. For the first time a good algorithm for non

data aided synchronization was presented by Oerder and Meyr [52]. The well-known squaring

algorithm by Oerder and Meyr for non data aided symbol timing estimation in SISO channels

was extended in MIMO channels in [53] and [54], resulting in a non data aided MIMO

estimator. However the estimator proposed in these references as well as [52] suffers from the

problem of self noise, which is inherited from the original squaring algorithm.

4.2.1.1 Data aided Symbol timing

Both ST block coding (STBC) and ST trellis coding (STTC) systems can be described by the

same basic communication model [50]. The simplified baseband equivalent model with Nt

transmit and Nr receive antennas is shown in Figure 19.

Figure 19: Simplified baseband model for space-time coding system

Let cn,i (i=0,…,Np-1) (n=1,…,Nt) be the ith orthogonal training sequence of length Np. Let the

received signal be sampled Q times faster than the symbol rate 1/Ts. Each received sample can

be indexed by the lth training bit and kth phase such as s lQ k= + . The sth symbol of the received

signal rm,s in a flat fading channel according to [50] can be written as:

, , ,1

, ,( )1

( / )

( / ( ) )

0,1,..., 1 0,1,..., 1

t

t

NS

m s nm n i s s s m sn it

NS

nm n i s s s m lQ kn it

p

Er h c p sT Q iT T w

N

Eh c p kT Q l i T T w

N

for l N and k Q

η

η

=

+=

= − − +∑ ∑

′= + − − +∑ ∑

= − = −

(54)

Where p(t) is the result of convolution between transmit and receive filter. Ts is the symbol

duration, η′ denotes the distance between the first sample of current symbol and optimal instant

while η represents the distance between center sample and optimal instant. wm,s denotes

n m


complex circularly distributed Gaussian white noise at the mth receive antenna and the sth

instant. Grouping the samples with the same phase, one can form the vector rm,k as follows:

, , ,( ) ,(( 1) )...P

T

m k m k m Q k m N Q kr r r+ − + = r (55)

And we can rewrite (54) in matrix form as follows:

, ,

1

( )tN

sm k nm n m k

nt

Eh k

N == +∑r C p w

(56)

Where:

,(mod( , )) ,(mod( 1, )) ,(mod( , )

,(mod( 1, )) ,(mod( 2, )) ,(mod( 1, )

,0

,(mod( 1, )) ,(mod( , )) ,(mod( 1, )

)

)

)

CP p CP p CP p

CP p CP p CP p

CP p p CP p p CP p p

n N N n N N n N N

n N N n N N n N N

n

n N N N n N N N n N N N

c c c

c c c

c c c

− − +

− + − + +

− + − − + + −

=

C

L

L

M M M

L

(57)

[ ]( ) ( / ) ( / ( 1) ) ( / )CP s CP s s CP s sk p kt Q N T T p kt Q N T T p kt Q N T Tη η η′ ′ ′= − − − − − + −p L (58)

, , ,( ) ,(( 1) )t

T

m k m k m Q k m L Q kw w w+ − + = w L (59)

In these equations NCP the size of prefix and suffix (here we use a cyclic prefix and cyclic

suffix, each of length NCP [51]).

We multiply the received signal by training sequence to form Ψnm(k)= CnHrn(k). Supposing the

relative delay is zero and Cn ‘s of different antennas are orthogonal to each other we have:

2

,0 ,1

( ) ( / ) ( ) wtN H Hs s

nm nm s s n nm n n n m knt t

E Ek h p kT Q T h k

N Nη

=′Ψ = − + +∑C C C p C%%

(60)

nC% is the same as Cn but with (NCP+1)th column removed and %p is the same as p but with the

(NCP +1)th entries removed. The second term in (60) represents the ISI which reduce to zero if

the training sequences are orthogonal and the relative delay is zero. The last term in (60) is the

noise term. From (60), it can be observed that, if the second and the third terms are very small,

Ψnm(k) has the same shape as p(t) except that it is scaled by a complex channel gain. In order to

remove the effect of the channel, consider the sequence 2

( ) ( )nm nmk kΛ = Ψ which has a same

shape as |p(t)|². Now the optimum sampling phase k=k0 is selected such that it

maximizes ( )nm kΛ .

)(max1,...,1,0

kk MLQk

o Λ=−=

(61)

62 Amir Saemi

= =

Λ = Λ∑∑1 1

( ) ( )tr NN

ML nmm n

k k

Under optimistic assumption that the sample closest to the optimum sampling position is

correctly estimated (at high SNR) the estimation error, normalized with respect to the symbol

duration, is a uniformly distributed random variable in the rang [-1/2Q, 1/2Q]. Therefore, the

MSE normalized with respect to the symbol duration Ts is (1/12Q²). As a result, the

performance of this timing synchronization highly depends on the oversampling ratio. In fact,

relatively high oversampling ratio might be required for accurate symbol timing estimation. Wu

[51] has proposed an interpolation algorithm based on Fourier series in order to estimate

symbol timing. The advantage of this algorithm is that accurate timing estimates can be

obtained even if the oversampling ratio is small. Both analytical and simulation results in [51]

show that for modest oversampling ratio (such as Q=4), the MSE of the proposed estimator is

significantly smaller than that of the optimum sample selection algorithm.

In order to explain Wu’s algorithm let’s construct a periodic sequence ( )nm sΛ% by periodically

extending the approximation log-likelihood sequence ( )nm kΛ in (61). Further, denote η′Λ )% ( )nm

as the continuous and periodic approximated log likelihood function with its samples given

by ( )nm sΛ% . According to sampling theorem, as long as the sampling frequency Q/Ts is higher

than twice the highest frequency of η′Λ )% ( )nm , then η′Λ )% ( )nm can be represented by its samples

( )nm sΛ% without loss of information. The relationship between ( )nm sΛ% and η′Λ )% ( )nm is then given

by:

ηη π∞

=−∞

′ −′Λ = Λ

∑/

( ) ( )sinc/

s sML ML

s s

T sT Qs

T Q

))% %

(62)

Then we can expand η′Λ )% ( )nm into a Fourier series and calculate the coefficient of series which

are necessarily factors of ( )nm kΛ . By determining these coefficients, the timing delay η′) can be

estimated by maximizing η′Λ )% ( )nm . For efficient implementation, η′Λ )% ( )nm can be approximated

by an K-point sequence, by zero padding the high frequency of Fourier coefficients and

performing a K-point inverse Discrete Fourier Transform (IFFT) ( for large value of K i.e.

K>>Q).

To avoid the complexity in performing the K-point IFFT, we can approximate Fourier series

only by first three terms:


πηη η′′ ′Λ ≈ + ≤ ≤)) )% 2

0 1( ) 2Re 0 1jnm A A e (63)

Now our problem reduces to calculate the η′) which maximizes η′Λ )% ( )nm . It ends to the

following estimation:

πηπ

−−

=

′ = − Λ ∑

) 12 /

0

1arg ( )

2

Qj k Q

MLk

k e (64)

It has been found that an oversampling factor Q of 4 is sufficient to yield good estimates in

practical applications. Therefore, the previous terms in (64) can be computed easily without any

multiplication since je kj ±±∈− ,14/2π

Wu in [51] calculates variance of his estimator analytically and he justifies the validity of the

approximation that he had used in his development.

Wu in [54] presents a ML data aided estimator by considering correlation between antennas and

claims that approximated ML algorithms in the estimators in [51] and [50] are just a special

case of this estimator. He drives two performance bound, the first one is the conditional

Cramer-Rao bound (CCRB) (see the references of [54]) which is the Cramer-Rao bound (CRB)

for the symbol timing estimation conditioned that the nuisance parameters are treated as

deterministic and are jointly estimated together with unknown symbol timing. Therefore the

CCRB serves as a performance lower bound for the ML estimator. The second one is the

modified CRB (MRCB) (see the references of [54]), which is a lower bound for any unbiased

symbol timing estimator, irrespective of the underlying assumption about the nuisance

parameters. Being easier to evaluate than CRB, MCRB serves as the ultimate estimation

accuracy that may be achieved. Wu shows that the MSE of the derived Data Aided (DA) ML

estimator is close to the CCRB and MCRB. It means that the DA ML estimator is almost the

best estimator (in term of MSE performance) for the symbol timing. Also he proves that

correlation between antennas has little effect on the MSEs of DA ML estimators unless the

correlation between adjacent antennas is larger than 0.5, in which case small degradations

occur.

About the effect of number of transmit and receive antennas he showed that increasing of

receive antenna leads to considerable MSE improvements (almost inversely proportional) but in

contrary different numbers of transmit antennas result in the same estimation accuracy and

therefore the MSE are approximately independent of the number of transmitters. It is tempted

64 Amir Saemi

to argue that using more transmit antennas, should also improve the performances of symbol

timing estimation since from the experience of Alamouti and Tarokh, more transmit antennas

also provide diversity gain. However, notice that the diversity gain of STBC does not come

automatically by just increasing the number of transmit antennas. In STBC, the observation

length for demodulating a symbol has to be increased with the number of transmit antennas. For

symbol timing estimation, irrespective of the number of transmit antennas, the total transmit

power and the observation length are kept constant so it is not unreasonable to have MSE

performance independent of the number of transmitters. For multiple receive antennas, although

the observation length is kept constant, the observation from different receive antennas are

independent (similar to the situation of maximum-ratio receive combining scheme). These

independent observations increase the effective length and performance is improved due to

longer effective observation.

Here, Wu’s algorithm in [54] will be briefly presented as the most general algorithm in the

literature for flat fading channels.

With the same notation which is used in equation (54) we have:

,, ,1

( / )s s m s

t

tNS

m s nm n in i

Er h c g st Q iT T w

Nη

== − − +∑ ∑ (65)

g(t) is the transmit filter with unit energy. After passing through the anti-aliasing filter the

receive signal is then sampled Q times faster than the symbol rate 1/Ts. Note that the

oversampling factor Q is determined by the frequency span of g(t); if g(t) is band-limited to

f=±1/T (e.g. root raised cosine (RRC) pulse) then Q=2 is sufficient. The received vector rm

which consists of NQ consecutive received symbol (N is observation length) from the mth

receive antenna, can be expressed as (without loss of generality, we consider that the received

sequence starts at t=0)

:m m mηξ= +A ZH wr

(66)

Where ξ = S

t

E

N and

,0 , ,( 1)...s s

T

m m m T m NQ Tr r r − = r (67)


1 1( ) ( ) ... ( )g g gN N N Nη η η η− − + + −

= a a aA (68)

[ ]( ) ( ) ( )... (( 1) )T

i s s s s s s s sg iT T g T iT T g NQ T iT Tη η η η= − − − − − − −a (69)

1 2 ... tNZ = d d d (70)

, , 1 , 1...g g g

T

n n N n N n N Nc c c− − + + − = d (71)

, ,0 ,1 , 1

T

m k m m m NQw w w − = w L (72)

11 12 1

21 22 2

1 2

r

r

t t t r

N

N

N N N N

h h h

h h h

h h h

=

H

L

L

M M M

L

(73)

With , , /m i m iT Qw w= and Ng denotes the number of the symbols affected by inter symbol

interference introduced by one side of g(t). Stacking the received vectors from all the receive

antennas gives:

( ( )vecηξ= ⊗ +rN

I A ) ZH wr (74)

where 1 2 ...r

TT T TN

r = r r r and 1 2 ...r

TT T TN

w w w w==== .

In order to include correlation between channel coefficients, the channel transfer function is

expressed as:

. .

T

R i d d TΦ ΦH = H (75)

Where RΦ and TΦ are the power correlation matrices [55] of receive and transmit antenna

arrays respectively (which are assumed known) . .i d dH contains independently and identically

zero mean, unit variance, circular symmetric complex Gaussian entries. This model is based on

the assumption that only immediate surroundings of the antenna array impose the correlation

between antenna array elements and have no impact on the correlation at the other end of the

66 Amir Saemi

communication link. The validity of this model for narrow-band non-line-of-sight MIMO

channels is verified by measurements (see [7–10] within [54]).

When matrix Z contains known training sequence the only unknown is Hidd. By resorting (74)

and using well-known properties of the Kronecker product we have:

η= +A hr && ηηηη (76)

Where ( )R Tη ηξ= Φ ⊗ ΦA A Z&& and h is vec(Hiid). Now for ML estimation of η and h we

have to maximize:

( )

2

22

1, ) expNQ

ww

p hηη

σπσ′

= −

A h(

r -r

&&

(77)

Where η′ is trial values for η . In [54] it is shown that to maximize the above probability we

have to maximize the following metrics:

( )-11

( )rN

HDA m m

mη η η ηη ′ ′ ′ ′

=

′ =Λ ∑ H H H HA Z Z A A Z Z Ar r (78)

And ML data aided symbol training estimator can be written as:

argmax ( )DAη

η η′

′= Λ)

(79)

The maximization of the likelihood function usually involves two-step approach. The first step

(coarse search) computes ΛDA(η’) over a grid of timing delay ηk=k/K k=0,…,K-1, and then ηk

that maximize ΛDA(η’) is selected in the next step (fine search) finds a global maximum by

using either gradient method or interpolation or dichotomous. By using parabolic interpolation

we can reach to following term:

1 3

1 3 22 ( 2 )k

I I

K I I Iη η −= +

+ −)

)

(80)

Where 1 2 31 1( ), ( ) , ( )DA DA DAk k k

I I Iη η η− += Λ = Λ = Λ) ) ) and k

η ) is the value that maximizes ΛDA

in the coarse search. The likelihood function at each receive antenna can be calculated

independently and then added together to obtain the overall likelihood function.

The correlation in the transmit and receive antenna arrays does not appear in the estimator that

is, the MLDA symbol training estimator is independent of the antenna correlations.

For large observation interval N, if we suppose g(t) being a Root-Raised-Cosine (RRC) pulse

and the training sequence from different antennas being orthogonal we can reduce (78) to [50]


and [51] algorithms. But the sufficient amount of N for this reason depends on the signal to

noise ratio. Wu claims that in SNR< 20 for N=32, two estimators have similar performance.

Anyway, it can be seen that Wu’s estimator in [54] is a very good estimator however it has been

designed for flat fading channels.

In the next sub-section we take a look at preamble design discussion in symbol timing based on

[54] and [56].

4.2.1.2 Training sequence design

In [51] the problem of how to design the training sequence for symbol timing estimation has

addressed. It is said that in order to minimize MSE in the symbol timing we have to use

orthogonal training sequence in order to minimize the ISI and noise term in (60). So a design

procedure for designing orthogonal preambles in MIMO system was presented by using [74]. In

fact, in [74] one can find some methods to construct several orthogonal sequences from one

shift orthogonal sequence. (See also the references within [74])

Here we mention the method of constructing perfect sequences which has been used in [51]

1) Construct a sequence s=[s(0), s(1),…, s(Np)] (NP is training sequence length) such that all of

its out-of-phase periodic auto-correction terms are equal to zero.

2) Construct another sequence s' (NCP is cyclic prefix length) as follows:

s’=[s(0), s(1),…, s(NP -1), s(0), s(1)... s(2NtNCP-1)]

Note that Np>2NtNCP must be satisfied. That is, if the number of transmit antenna is large, we

cannot use training sequences with short length.

3) The orthogonal training sequences are given by :

ci=[s’((2i-1) NCP), …, s’((2i-1) NCP+Np-1)]

But if approximated log-likelihood function is not used in the estimation (e.g. the true ML

estimator [54], these type of training sequence may not be optimal anymore so another

approach has been in [56] for training sequence design. In [56] it has been investigated that how

one can derive optimal training sequences independent of the estimation methods. Toward this

68 Amir Saemi

end, the orthogonal training sequences have been found by minimizing the modified Cramer-

Rao bound (MCRB) with respect to the training data; in this paper it has been shown that when

the transmit pulse is root raised cosine and there is no correlation among antennas, the optimal

orthogonal training sequence resemble the Walsh sequences. Furthermore it has been also

shown that the knowledge of antenna correlation is not important for designing training

sequence. Figure 20 compares the performance of MLDA with different kinds of training

sequence in a 4 × 4 receive antenna system with N=32, Ng=4, g(t) being a RRC pulse with α=.3.

Three different kinds of training sequences are considered. The first one is the optimal training

sequence derived in [56]. The second one is the Walsh sequences w31, w30, w29, w28 and

extended to length 40 by adding a cyclic prefix and suffix each of length equal 4. The final one

is the perfect sequence as we described above. From Figure 20, it can be seen that the perfect

sequences perform not as well as Walsh sequences and the optimal sequences. This is because

the true ML estimator is used in simulation and perfect sequences (which were derived based

on the approximated log-likelihood function) may not have any optimality. Due to the

resemblance of the optimal orthogonal sequences and the Walsh sequences, the performance of

the MLDA by using these two kinds of sequence are close to each other, with the case of optimal

orthogonal sequences performing marginally better. Of course we have to mention that the

perfect sequences and Walsh sequences are constant modulus sequences while the optimal

orthogonal sequences are not. The derived optimal training sequence in [54] belongs to the

class of orthogonal sequences. The question of whether there exists any non orthogonal training

sequence with better performances and how to find them is an open question.


Figure 20: MSE performance of the ML estimator for the different training sequence

4.2.1.3 Non Data Aided Symbol Timing

The data aided algorithms are based on orthogonal training sequences and hence transmission

efficiency is decreased. It also requires the epoch of training sequence to be perfectly known.

Any misalignment of the orthogonal training sequence with the local copies causes serious

performance degradation due to the loss of orthogonality. It, therefore, motivates us to develop

a non-OFDM symbol timing estimation algorithm that does not rely on training sequences.

In fact, the well-known Oerder and Meyr [52] algorithm presents a non data aided symbol

timing algorithm in SISO channels. Here we extend this algorithm in MIMO channels based

on [53].

With the same notation as (54) we have the magnitude square of the sampled received signal as: 2

2

, , ,

1

( / )tN

Sm s nm n i s s s m s

n it

Er h d p sT Q iT T w

Nη

=

= − − +∑ ∑ (81)

where dn is the encoded information by a ST trellis or block encoder at the nth receive antenna.

By taking expectation with respect to the joint distribution of channel coefficients, data and

70 Amir Saemi

noise and noting that the channel coefficients are independent and uncorrelated with noise and

also the encoded data di are uncorrelated for different values of n, we have:

2 22 2 2

, ,

1

( / )tN

Sm s nm n i s s s w

n it

Er h d p sT Q iT T

Nη σ

=

= − − + ∑ ∑E E E

(82)

where 2

wσ is the noise power. If the statistical properties of encoded symbols dn,i and the

channel coefficient hnm are independent of n and m then (82) can be rewritten as: 2 2 2

, ( / )m s S s s s wi

r E K p sT Q iT Tη σ = − − + ∑E (83)

K is a constant number. With the use of Poisson sum formula, and with the fact the p(t) is

bandlimited to f=1/T, (83) can be rewritten as: 2 2

, 0 1

*

[ cos(2 / 2 )]

1 2( ) ( )

2q

m s S w

s

E r E K z z m Q

z P P q dT

π πη σ

πω ω ωπ

∞

−∞

= + − +

= −∫

(84)

Where P(ω) is the Fourier transform of p(t). Since p(t) is symmetric P(ω) is real and zq are real

too. From (84), as ling as z1≠0, which is true for raised cosine pulse with excess bandwidth

α>0, the squared signal contains spectral lines at symbol rate (f=1/Ts) and its phase is closely

related to η . Thus we can estimate the timing delay by computing the Fourier coefficient at

symbol rate as the case of signal-transmit-single-receive system antenna [52]. It follows that ( 1) 1

2 2 /

,

1arg( )

2

r NQj s Q

m ss rNQ

r e πηπ

+ −−

=

= − ∑)

(85)

Where N is the observation length and r is any non negative integer. Further more, if the same

clock is used at all receivers. The squared signal from different antennas can be averaged before

estimation to increase the diversity as:

22

,

1

1 rN

s m smr

r rN =

= ∑ (86)

Wu in [54] develop a true ML approach for non data aided symbol timing and he shows that

(86) is a special case of his algorithm. For describing his algorithm we use the same notation as

equation (74) but in this case no training sequence is used and Z contains real data. In this case

Z and H can not be separated so we define x as ( )vec ZH here instead of (77) we have to

minimize following criterion:


( )

2

22

1, ) expNQ

ww

p hηη

σπσ′

′ = −

A x(

r -r

&&

(87)

With the linear model of equation (86) the ML estimation of x can be found and by putting it

into (87) and after some calculation and dropping irrelevant terms we have:

( )-11

( )rN

HNDA m m

mη η η ηη ′ ′ ′ ′

=

′ =Λ ∑ H HA A A Ar r (88)

And non data aided ML symbol training estimator can be written as:

argmax ( )DAη

η η′

′= Λ)

(89)

Like data aide case MLNDA can be implemented by the two-step approach.

Note that the implementation of the MLNDA estimator does not require the knowledge of

correlation among antennas. Note also that the likelihood function in Equation (88) is the sum

of individual likelihood functions for each receive antenna, just as the case of training-based

likelihood function in Equation (78). Furthermore, applying the low complexity maximization

technique [57] to the likelihood function (88) and with the approximation ( ) 2 gN NIη η′ ′ +=HA A

for Nyquist zero-ISI pulse, it can be easily shown that the MLNDA (89) reduces to the extension

of squaring algorithm proposed in Reference [53]. The effect of increasing the number of

transmitter and receiver in MLNDA estimator is the same as data aided estimator.

4.2.1.4 Comparison

Here, we compare the performance of the MLDA and MLNDA estimators with their corresponding

CCRBs and MCRBs for a 4 x 4 system. For simplicity, it is assumed that there is no correlation

among antennas and there is no space-time coding for NDA case (since the effects of these are

small as shown earlier). Figure 21 shows the results. Note that from Figure 21, the MSE

performances of MLDA and MLNDA estimators are very close to their corresponding CCRBs. This

means that MLDA and MLNDA are efficient estimators conditioned that the nuisance parameters

are being jointly estimated together with the unknown timing delay. Also, note that the

performance of MLDA estimator is very close to the MCRBDA, which implies that MLDA is

almost the best possible estimator under the problem at hand, regardless of how we deal with

72 Amir Saemi

the nuisance parameters. For the NDA case, unfortunately, although the performance of MLNDA

estimator reaches the corresponding CCRBNDA, the CCRBNDA is quite far away from the

MCRBNDA. It means that there is a possibility that some other NDA estimators (probably

employing higher order (>2) non-linearity) would have performances closer to the MCRB.

If we want to compare data aided estimator and non data aided, as expected, MLDA estimator

performs much better than the MLNDA estimator. However, there are some advantages for non

data aided estimator as follows: i) The MLDA estimator requires training sequences, resulting in

lower transmission efficiency. ii) The estimation has to be performed at specific times when the

training data is available, while MLNDA can be performed at any time during transmission. iii)

For the DA case, there is a need to synchronize the training sequences before timing estimation.

This requires extra implementation complexity. In addition, degradation may occur if the

positions of the training sequences are dislocated.

Figure 21: Comparison of MSEs of the MLNDA and MLDA and their corresponding CCRBs and

MCRBs for a 4 × 4 system.


Therefore MLDA and MLNDA provide a performance, transmission efficiency and complexity

trade-off for symbol timing estimation in MIMO channels.

There are some few other papers which discuss about symbol timing in MIMO systems like

[58]. In this dissertation I just present the most important ones. There is a major problem in all

of the papers which have been seen in the literature that all of them investigate synchronization

problem for the case of flat fading channel and there is no reference in the literature (by the

knowledge of the author) about symbol timing over frequency selective Rayleigh channels.

4.2.2 non-MIMO OFDM time synchronization

We already noted that in an OFDM system, thanks to using Fourier transformation, a time shift

smaller than sampling rate time can be converted to a shift in phase in frequency domain.

Therefore, in OFDM systems the delay smaller than sampling rate will be absorbed in channel

coefficients phase and there is no need to estimate it in time synchronization stage.

Numerous techniques have been suggested in the literature for Single Input Single Output

(SISO) OFDM time synchronization, however a lot of them can not be applied without major

modification to Multi input Multi output systems (for example [22],[23]).

Within SISO OFDM time synchronization algorithms we can distinguish two approaches in

literature. As a matter of fact, a number of methods for OFDM time synchronization have been

proposed for OFDM system in general (for example the methods that exploit the periodic

structure of cyclic prefixes and algorithms based on the use of repeated preambles). These

techniques were originally developed for general OFDM systems, but they can be also applied

to IEEE 802.11a WLANs. In the second approach, there are time synchronization techniques

that are specifically designed for IEEE 802.11a WLAN.

74 Amir Saemi

4.2.2.1 Time Synchronization for general

SISO-OFDM systems

By exploiting the known structure of a training symbol or a cyclic prefix, several schemes have

been proposed for coarse estimation of the carrier frequency offset and time synchronization

[22]-[36]. Moose in [24] proposes the repetition preamble scheme for the first time for

frequency synchronization. He describes a technique to estimate frequency offset by using a

repeated training sequence and derives a maximum likelihood estimation procedure. Then, this

idea was used for time synchronization by Schmidle [23], Speth [33] and Keller [35]. The

principle of exploiting a double training sequence preceded by a cyclic prefix (CP) for frame

synchronization was originally suggested for single-carrier transmission in [36].

It seems that the best way for time synchronization is to calculate correlation between a known

reference and received sequence. But the presence of frequency offset reduces the peak of

correlation function. In fact, this frequency offset prevents coherent addition of individual term

in correlation calculation and results in a drop of the correlation peak so Shmidl [23] proposed

to use the preambles like Figure 22, and calculate autocorrelation function (instead of cross

correlation) as:

*

1

( ) ( 1) ( 1)τ τ τ=

= − + − − +∑pN

pi

y r i r N i (90)

where r(τ) is received signal and NP is the size of each preamble. According to (90) the coarse

time is the instant where y reaches to its peak. This method is robust against frequency offset

but the drawback of this method is that the correlation function exhibits a plateau at the arrival

of the data packet [29],[8]. In fact during the CP period, the correlation function remains

constant and there is no abrupt falling edge outside this period. This edge can not be localized

precisely in low signal quality. This phenomenon, inherent to the structure of training sequence,

makes it difficult to find the fine timing. Therefore, this method can only be used for frame

synchronization (coarse search) and for fine timing or symbol timing one have to use another

method.


Figure 22: the repeated preamble used in the literature

Muller-Weifurtner in [25] provided a ranking for different metrics in repetition preamble

method which proposed in literature [26],[23],[35],[36] via a simulation assessment. In fact he

compared Minimum Mean Squared criterion [36], Maximum-Likelihood criterion [26],

Maximum Correlation criterion [35] and Shmidle’s criterion [23] with each other. He proved

that ML metrics in [26] performs the best and for moderate noise is asymptotically identical

with the slightly less complex MMSE metric in [36].

Similar to the signaling set up adopted in [23], Coulson used two repeated m-sequences as a

training symbol [31],[32]. However the proposed time synchronization algorithm is likely to

fail in the presence of large carrier frequency offsets, and presents high implementation

complexity due to the matched filtering. Moreover, a training sequence with the same structure

as the one proposed in [31] is exploited [22] to develop reliable frequency and time acquisition

scheme. However, the proposed time synchronization algorithm is also sensitive to large

frequency offset.

Recently Shi and Serpedin in [37] based on [29] have proposed using the preambles as follows:

[ ± B ± B ± B ± B ] (91)

where B stands for a sequence of Np/4 training samples with constant variance (amplitude)

(e.g., an m-sequence) and it can be generated with good approximation by using an Np/4-point

IFFT of an m-sequence. They claimed that their method exhibits nearly the same performance

as [31] in term of estimation accuracy (better than [23] and [29]). In addition, the proposed

estimator assumes a reduced implementation complexity and is more robust against large

frequency offset in comparison with [31].

2NCP Np Np

Data 2N

Training Sequence

76 Amir Saemi

Figure 23: Using cross correlation for fine timing

Symbol timing (fine timing): In a SISO OFDM system, fine timing can be performed by

cross-correlation the received signal and transmitted ones after frequency synchronization

(Figure 23) or estimate the power of channel impulse responses as [38 pp 88-92], or by finding

the magnitude of channel impulse response larger than a proper threshold [48],[49]. In [34]

based on [33] Speth performs fine timing with a post-FFT algorithm using pilots and estimated

channel.

4.2.2.2 Time synchronization for IEEE 802.11

WLAN

OFDM is employed as the transmission technique in the IEEE 802.11a WLAN standard. In the

IEEE 802.11a standard, the preamble is dedicated to various synchronization tasks. However,

there is no mention in the standard how to use the preamble to achieve synchronization.

IEEE 802.11a is a packet-based communication system. Each packet is preceded by a preamble

as defined in IEEE 802.11a specification [79]. The preamble structure shown in Figure 24

consists of two parts. The first part comprises 10 short training symbols, each of length 800ns;


in the second part a cyclic prefix of length 1.6µs is followed by two long training symbol each

of length 3.2µs.

Figure 24: Packet structure for IEEE 802.11a WLANs

There are several papers which propose synchronization algorithms specifically designed for

IEEE 802.11a WLAN [39]-[45].

Nandula in [39] proposes a frame timing algorithm using auto-correlation and cross-correlation

of short preambles. In the absence of an analytical discussion in [39] it seems that this

algorithm is not robust against frequency offset. However he claimed that his algorithm by

using an average, can withstand somewhat against frequency offset. Wang in [40] has proposed

a coarse time synchronization scheme based on the short training symbols. He calculated two

normalized auto-correlation timing metrics. The first metrics M1 is the normalized correlation

between the received signal and itself with a delay of one short training which creates a plateau

of the length of nine short training. The second metric M2 is the normalized correlation between

the received signal and itself with a delay of two short training which creates a plateau of the

length of eight short symbols. By subtracting M2 from M1 a triangular shaped timing metric is

obtained, which its pick indicates start of 9-th short symbol as Figure 25.

In [40], for fine timing synchronization, some schemes have been proposed such as

conventional cross correlation method with the long training symbol or the method proposed in

78 Amir Saemi

[38] that selects the window which contains the maximum power of the estimated channel

response.

Figure 25: Timing metrics in [40]

The most recent approaches to WLAN synchronization are discussed in [28] and [42] in which

a maximum likelihood symbol synchronizer is developed for IEEE 802.11a WLANs in

frequency selective fading channel by using the ideas in [27]. Wu in these articles derives a ML

criterion to estimate both channel length and the arrival packet time by using the short training

symbols. The observation vector length in the proposed algorithm is 16 (rather than 64 in [27])

so compared with [27] he reduced complexity considerably with the same performance. In fact

he used a two-stage algorithm. In the first stage, the current time offset with respect to the last

short training symbol and thus the beginning of the next expected short training symbol is

determined. In this stage he derived a general ML criterion by using an observation vector of

length 16. In the second stage, he determines if the incoming vector belongs to a short training

symbol or a cyclic prefix of a long training symbol. The authors of this article have shown by

simulation that this ML algorithm has good results with rather low complexity.


Figure 26: A typical MIMO-OFDM transmitter and receiver

4.3 MIMO OFDM frame synchronization

A typical MIMO-OFDM transmitter and receiver system is represented in Figure 26.

As previously said the OFDM time synchronization algorithms often include two steps. The

first step is Frame Synchronization/Coarse Timing. The task of the frame synchronization is to

identify the preamble in order to detect a packet arrival. This preamble detection algorithm can

also be used as a coarse symbol timing since inherently provides a rough estimate of the starting

80 Amir Saemi

point of the packet. The second step is symbol timing which indicates where to place the start

of the OFDM window within the OFDM symbol. An OFDM system is well known for its

ability to combat inter-symbol interference (ISI) introduced by multipath channel, nevertheless

incorrect positioning of the FFT window within an OFDM symbol reintroduces ISI during data

demodulation, causing serious performance degradation [33]. This section is dealt with frame

synchronization and the following section is about symbol timing.

The first paper which published about MIMO OFDM time synchronization in multipath

channel, to the best of our knowledge, was [45] by Mody. He used a simple MIMO extension of

Schmidl’s synchronization algorithm [23] by using the modulatable orthogonal sequence

proposed by Suehiro [46]. For fine time acquisition he used cross correlation techniques. Zelst

in a article on the implementation of a MIMO OFDM based wireless LAN system in frequency

selective channels [47] presented another extension of Schmidl’s synchronization algorithm.

Zelst’s method is based on calculation of autocorrelation between two repeated preambles. The

maximum of autocorrelation should normally show the beginning of the packet. The periodicity

of preambles makes his algorithm robust against the frequency offset. In the following section

we well describe the classical autocorrelation method. Then in the next sub-section, an

advanced version of autocorrelation method which has been developed by us and presented in

[7] will be discussed.

Moreover, we presented another new method for frame synchronization in [6]. This method

first was presented in a conference and then it has been elaborated in [4] and submitted as an

invited paper in [2]. This algorithm in detail will be discussed in the chapter 5.

4.3.1 Autocorrelation method

In the autocorrelation method which is largely accepted as one of the best methods for frame

synchronization a training sequence that is orthogonal and shift orthogonal is needed.

Moreover, to estimate the MIMO channel, it is important that each path from the different TX

antennas to each RX antenna can be uniquely identified. There are several other methods to

construct the training sequence; some of them were described in 4.2.1.2. Anyway, there are at


least two constraints to design a sequence as a preamble. The first condition is the orthogonality

between the preambles of different transmit antennas and the second condition is shift-

orthogonality for at least the length of the channel (to remove the effects of multipath channel).

A straightforward way to generate the preamble is to turn off all other transmitters while one

transmitter is transmitting the preamble. The resulted preamble generated by this method is

showed in the Figure 27. This way is the simplest method of generating preambles because the

orthogonality between deference antennas is assumed. This method results in simpler time

synchronization algorithm but since the total length of the proposed preamble grows linearly

with Nt, it is not highly efficient.

Figure 27: Time orthogonal preamble suitable for MIMO systems with two transmit antennas

To design orthogonal sequences, apart from the methods presented in 4.2.1.2, we present here a

simple method based on reference [112] to construct a orthogonal code with length 2

PN . This

kind of codes is called Frank-Zadoff codes.

In order to generate this kind of code we construct the following matrix:

2

1 2 ...

2 4 ... 2

. . . .

2

P

P

P P P

N

N

N N N

(92)

We form a long vector by putting side by side the rows of matrix (92) :

21 2 ... 2 4 ... 2 ... 2 ...PP P P PP N N N N N = (93)

Then, the sth symbol of preamble will be obtained by the following formula:

2 ( ) / 2( ) ( ) 0,2,..., 1PjP s NPB s e s Nπ= = − (94)

Having constructed the Frank-Zadoff codes, we use it as the training sequence of the first

transmit antenna and the other transmit antennas’ training sequence will be the shifted version

2NCP NP NP

Data

Ntrain

2NCP NP NP

Data

Ntrain

TX1

TX2

82 Amir Saemi

of the first training sequence. One has to consider that the amount of shift must be greater than

the channel length.

Using the orthogonal training sequence, the correlation function Λ can be defined as:

1*

, ,1

( )pr

p

k NN

m s m s Nm s k

k r r+ −

−= =

Λ = ∑ ∑ (95)

where rj,k is the received signal at the mth receive antenna and at the kth instant. NP is the length

of a preamble and since we use two preamble plus cyclic prefix the length of the training

sequence is 2Np+2NCP (Figure 28). s is the beginning of a sliding window over received signal.

Figure 28: Orthogonal preamble for MIMO systems with two transmit antennas

The beginning of the packet will be:

argmax ( )startk

t k= Λ (96)

However, the drawback of this method is that the correlation function does not produce a sharp

peak at the arrival of the data packet. In fact, during the CP period, the correlation function

remains constant and there is no abrupt falling edge outside this period. This edge can not be

localized precisely in a cheap signal quality. This phenomenon, inherent to the structure of

training sequence, makes it difficult to find the fine timing and we need necessarily another

algorithm to perform fine timing (symbol timing). We will discuss about MIMO OFDM symbol

timing algorithms in section 4.4 but in the following sub-section a new method presented by us

in [7] will be discussed. In this new method which is called advanced autocorrelation method,

contrary to the autocorrelation method, we do not have a plateau during CP period and the new

correlation method produces a sharp peak.

2N CP N N

Data

N train

TX1

2N CP N N

Data

N

TX2

train


4.3.2 Advanced autocorrelation method

In absence of frequency carrier offset, the best way for symbol-timing is to calculate correlation

between a known reference and received sequence. However the presence of frequency offset

reduces the peak of correlation function. In fact, this frequency offset prevents coherent

addition of individual term in correlation calculation and results in a drop of the correlation

peak. This method proposes an advanced auto-correlation method in the presence of frequency

offset and produces a sharp peak in contrast with conventional autocorrelation method which is

used for coarse timing (frame synchronization). Therefore, in this method the coarse time

synchronization and fine time synchronization step are merged into a single step and our frame

synchronizer and time synchronizer are merged into a simple time synchronizer. The main

drawback of this method is that it is designed for flat fading channels. However, according to

the experimental results presented in [8] it has a good performance in frequency selective

channels .

4.3.2.1 Signal Model

The received signal by the mth antenna at instant τ can be written as:

1

, , ,

1 0

( )tN L

m n l nm mn l

r u h l wτ τ τ

−

−= =

= +∑∑ (97)

where wm,τ represents complex additive Gaussian noise at instant τ and at the mth receive

antenna with variance (1/2)σw2, stationary and independent from the other antennas. hnm(l) is the

(n,m)th element of the matrix H(l) and represents the path between the nth transmit and mth

receive antenna This equation can be written for all the receive antennas as follows:

84 Amir Saemi

τ τ τ−

== − +∑

1

0

( ) ( ) ( ) ( )L

l

l lr H u w (98)

where r(τ) and w(τ) are column vectors of dimension Nr and u is a column vector of dimension

Nt.In the presence of frequency error due to local oscillator deviation or Doppler effect, each

received symbol undergoes a phase rotation proportional to the delay between the transmit and

receive instants and the frequency error. The received complex vector can be written as follow:

π ττ τ τ−

∆

== − +∑

12

0

( ) ( ) ( ) ( )L

j f

l

e l lr H u w (99)

where f∆ is frequency offset.

4.3.2.2 Advanced auto correlation

synchronizer

Instead of conventional autocorrelation function, we propose a new function, which has a very

sharp response, even in the presence of relatively large frequency offset. We define the function

ymn for the mth receive antenna while the nth transmit antenna is considered:

1* *

, 1 , , , 11

( )p

p p

N

mn m k n N k m k n N kk

y r c r cτ ττ−

− + − − − −=

= ∑ (100)

where cn,k represents the cyclic prefix sequence at the nth transmit antenna and at the kth instant.

and rn,k represents the the kth sample of received signal at the mth

receive antenna. Np is the

length of each preamble. Considering a training sequence as presented in Figure 27, it is clear

that the received signal in each instant is only the function of one training sequence of

corresponding emitting transmitter. In order to simplify notation assuming the time reference at

the instant where the preamble arrives at the receivers (τ =0), Assuming a flat fading channel,

rm,τ when the nth transmitter is on can be written as follows:


2

, , ,(1) sj fTm n nm mr c h e wπτ

τ τ τ∆= + (101)

Replacing (101) in (100) and we obtain:

1 2 2 22max

1 , , 1 , 11

( ) (1)p

s

p p p p

Nj fT

mn N mn n N k n N k nm m Nk

y y c c h e wπττ

−− ∆

= − − − − −=

′= = +∑ (102)

Hence, ymn(NP-1) presents a sharp peak at packet arrival independent of the channel phase

coefficient and frequency error. Using the principle of maximum ratio combining and since the

phase effect due to channel and frequency error is already cancelled out, we can add up ymn(τ)

directly to form our decision function for the nth transmit antenna.

1

( ) ( )rN

n mnm

y yτ τ=

= ∑ (103)

In order to take advantage of the other codes sent by the other transmit antennas, we can sum up

a shifted version of all the yn(τ) to obtain our final decision function:

1

( ) ( ( 1) )tN

n trainn

y y n Nτ τ=

= − −∑ (104)

Figure 29 represents ( )y τ . The correlation function proposed in literature is presented also to

make clear the decision algorithm. As soon as maximum correlation function exceeds a fixed

threshold, we search for a peak in (104) that gives the exact packet arrival.

86 Amir Saemi

Figure 29- Peak of the y(n) (equation (104)) helping to detect the exact timing

4.3.2.3 Training sequence design for

advanced auto correlation synchronizer

Here we describe how we can construct the training sequence for the first transmit antenna. The

training sequence should be designed so that it has a maximum in 1PNτ = − according to

equation (102) and it is about zero near the maximum. Defining *

1, 1, 1, 1k k kc c c −′ = , the required

condition is:

1*

1, 1,( )mod

00

0P

P

N

p p q Npq

c c−

+=≠

′ ′ =∑ (105)

It guaranties a sharp peak of the function defined by (100) and consequently by (104). Applying

this code to c'(p), the training sequence c(p) can be calculated by means of a simple recursion

algorithm as follow:

• 1,0 1c =

• *

1, 1

1, *

1, 1

kk

k

cc

c−

−

′=


4.3.2.4 Advanced Autocorrelation method in

frequency selective channel

Although our algorithm is designed for flat fading channels, we wanted to quantify the

performance degradation when this algorithm is applied directly to frequency selective

channels. The performance is measured by the probability of time synchronization failure,

which can be compared with the results of autocorrelation time synchronization algorithm

presented in [48].

Table 3 shows the results [8]. The simulations have been performed for a 2×2 MIMO system

with SNR=6 dB. Exponential decay channel was considered with Rayleigh fading coefficients.

The rms delay spread range varies between 50 and 250 ns and sampling rate is fixed to 20

MHz. As it can be seen from the table, this algorithm quite outperforms the autocorrelation

method especially in low dispersive channel, as expected.

Table 3: Synchronization failure probability in autocorrelation and proposed

algorithms

τrms Pfail in conventional time

synchronization algorithm

Pfail in proposed time

synchronization algorithm

50 ns

100 ns

150 ns

200 ns

250 ns

9.4 x 10-3

6.4 x 10-2

1.2 x 10-1

1.8 x 10-1

2.4 x 10-1

1.7 x 10-3

1.7 x 10-2

6.1 x 10-2

1.0 x 10-1

2.0 x 10-1

88 Amir Saemi

4.4 MIMO OFDM symbol timing

To overcome the Inter-Symbol-Interference (ISI) most OFDM based systems apply a cyclic

prefix (CP) in front of every symbol. This CP, often also referred to as guard interval (GI),

introduces redundancy, which is removed in the receiver, before data detection. In this way the

influence of the ISI caused by the multipath channel can be largely reduced.

The CP, however, also significantly decreases the effective data rate of the system. It is,

therefore, important that the ratio between the length of the CP and the number of carriers is

minimized. One solution is to keep the CP length low compared to the channel impulse

response (CIR) length. Then, however, ISI will possibly become the performance limiting

factor and the placement of the discrete Fourier transform (DFT) window within the stream of

received OFDM symbols, here referred to as symbol timing, becomes important. Note that

symbol timing in literature is sometimes referred to as fine timing, in contrast to coarse timing

which indicates the packet detection.

Several frame timing approaches for single-input single output (SISO) OFDM have been

proposed previously in literature. Generally, they are based on a maximizing of a timing

measure which is found by either correlation between repeated dedicated training symbols, or

correlation between the redundant parts in the data symbols. The limited accuracy of these

algorithms makes their applicability to systems with short CP lengths questionable. In this

chapter we illustrate several symbol-timing which exhibit good performance.

The symbol timing algorithms that will be presented in this section can be divided into two

types. The methods that will see first use the knowledge of channel coefficients. In fact, the

idea of this kind of methods firstly appeared in [38, pp 88-92]. Zelst extended the technique

proposed in [38] over MIMO channels. Since, this technique relies on the knowledge of the

channel response, their powers are estimated by correlating the received signals with the known

training sequence and subsequently the powers of all paths in MIMO channel are summed.


Schenk in [121] elaborated on this idea and presented several symbol timing methods for

MIMO OFDM systems. In the following section we will present his symbol timing methods.

Then, in the next subsection a new symbol timing algorithm, introduced by us in [5], will be

presented.

4.4.1 Methods with the knowledge of

channel coefficients

4.4.1.1 Signal Model

Consider a MIMO OFDM system with Nt transmitter (TX) and Nr receiver (RX) branches, Nc

subcarriers and a CP of length NCP samples. The vector of (complex) data symbols in the

frequency domain is denoted by u here, the size of which equals NcNt×1. After the inverse

discrete Fourier transform (IDFT) and the addition of the CP the NsNt × 1 signal vector is given

by u, where the symbol length is denoted by Ns = Nc +NCP. The upconverted signal is

transmitted through the wireless channel and downconverted at the RX, here modeled by

transmission through the baseband equivalent channel H. The Nr ×1 received time-domain

vector during sample time k is expressed by:

1

1, 2, ,

0

( ) , , ... , ( ) ( ) ( )r

LT

k k N kl

k r r r l k l k−

=

= = − + ∑r H u w (106)

where rm,k represents the received signal at the mth receive antenna and during kth instant. u(k)

and r(k) denote the Nt×1 and Nr×1 transmitted and received vector during sample time k, L is

the length of the channel and T denotes the matrix transpose. For the following it is useful to

group these vectors per OFDM symbol. Therefore, we introduce the following short notation

for the kth sample of the pth OFDM symbol at the mth and nth receive and transmit antenna:

rpm,k = r m,(p − 1)Ns + k and u pn,k = u m,(p − 1)Ns + k.

90 Amir Saemi

Using this notation, the noiseless received signal in (106) can be rewritten for the kth sample of

the pth received symbol vector as:

1, 2, ,

1 11

0 0

( ) , , ... , ( ) ( ) ( ) ( )k k N kr

L L kTp p p p p p

sl l

k r r r l k l l k N l− − −

−

= =

= = − + + − ∑ ∑r H u H u (107)

for k = 1, . . . , Ns and where we assumed L ≤ Ns. rpm,k represents the k

th sample of the pth

OFDM symbol at the mth receive antenna We can conclude from (107) that the received signal

contains samples from the regarded and the previous symbol, i.e., the first term is the useful

signal term and the second term is the ISI. The symbol timing now determines which Nc out of

Ns samples of rp are used to determine the frequency domain signal vector. This vector is then

used by the MIMO processing to estimate the transmitted data.

If the symbol timing is chosen to be km, the Nc –dimensional vector input to the DFT for the mth

RX is given by:

, , 1 , ,, , ... , m m k m k N m k m km m c m m

Tp p p p sig p isim k r r

+ − = = +

r r r (108)

where the ,m km

p sigr and

,m km

p isir are the desired and ISI vector, respectively.

Their kth elements are given by:

1

, :

0

( ) 11

, :

0

( ) ( ) ,

( ) ( )

m

m m

m

m s

k kp sig T pm k m k k l

l

L k kp isi T pm k m m N l

l

k l

k l k k

+ −

+ −=

− + −−

−=

=

= + +

∑

∑

r H u

r H u

(109)

for k = 0, . . . , Nc − 1, respectively. Here the mh column of H is denoted by H:m .

As a performance measure of the timing we now consider the power of the desired signal and

ISI terms. Hereto we calculate the expected power value of the desired signal term for timing

point p and a given channel realization H. Since the DFT is applied per RX branch, it is derived

here for the mth RX branch. For a timing point k, the expected signal power is given by:

, , :

12 2

: : : :

0 1

( )

( ) ( ) ( ) ( ) ( )

m k m k

c

sig p sig H p sigm m

NkH H

c u m m u c m mi i

P k

N i i N i i k i kσ σ+

= =

=

= + − + +∑ ∑

r r H

H H H H

E

(110)


where the elements of u are assumed to be independently and identically distributed and to have

zero-mean and a variance of σu2.

In a similar way the expected value of the ISI power can be derived as:

, , :

12 2

: : : :

1

( )

( ) ( ) ( ) ( )

m k m k

c

c

isi p isi H p isim m

NkH H

c u m m u m mi N k i

P k

N k k i i k i kσ σ−

= + =

=

= + + +∑ ∑

r r H

H H H H

E

(111)

The expressions for the wanted signal and ISI power, in two previous equations are defined for

1 ≤ k ≤ NCP. Note that for k > NCP these expressions change slightly, since samples of the next

symbol will be included in the DFT window, also causing ISI.

Clearly the expressions for the expected power of the desired signal and ISI in two previous

equations depend on the channel realization.

Knowledge of the MIMO channel coefficients is, therefore, required to be able to apply these

expressions for symbol timing. In a practical system, however, full knowledge of the channel is

often not available and an estimate of the channel has to be acquired.

Let us now consider a packet transmission, where the channel can be assumed to be quasi static,

i.e., the channel is constant during the reception of a packet. For such a system often a piece of

known data, i.e., preamble is transmitted in front of the data part to enable estimation of the

MIMO channel coefficients, which is also required for MIMO detection. MIMO channel

estimation and the design of an efficient preamble has been the subject of many contributions

over the last few years and details are, therefore, omitted here.

Although the different channel estimation/preamble combinations will result in a different

performance, we can generally write the resulting estimate of the lth tap of the Nt×Nr MIMO

channel matrix H[l] by ( )lΗ% =H(l)+er(l) , where er(l) is the estimation error in the lth tap of the

channel coefficients, which is here assumed to be zero-mean circular symmetric complex

Gaussian distributed with a variance of σ2 . Clearly this variance decreases with increasing

signal-to-noise ratio (SNR). We have to note that although only an estimate of channel is

available, we will assume perfect channel knowledge in these sections.

92 Amir Saemi

4.4.1.2 Dominant path detection

The straightforward method to determine the symbol timing is to relate the timing to the

maximum path in the channel. This is based on the observation that paths in the CIR with the

smallest delay will generally experience the lowest attenuation. Generally an offset of several

samples is applied to take into account possible smaller taps preceding the path with the

maximum power in the channel

4.4.1.2.1 RX-branch timing

When this technique is applied for a MIMO system to calculate the symbol timing for one of

the RX branches, i.e., m, the estimated symbol timing point is given by:

: :ˆ argmax ( ) ( )Hm m m CP

k

k k k c N= − +H H (112)

where c is the above mentioned offset parameter. Furthermore, the constant NCP is added since

the outcome of the argmax indicates the beginning of the OFDM symbol, rather than the

beginning of the DFT window. This is also the case for following equations. It is noted that for

the RX-branch timing every RX branch uses separate symbol timing.

4.4.1.2.2 Joint timing

To make the processing in the MIMO RX less complex, a common symbol timing for the

whole MIMO RX can be calculated. The timing point is then found as:

: :

1

argmax ( ) ( )rN

Hm m CP

k m

k k k c N=

= − +

∑H H

%

% % (113)


4.4.1.3 SIR (Signal to ISI Ratio) optimization

A more optimal approach to symbol timing in the case of perfect channel knowledge is

proposed here. It maximizes the SIR (Signal to ISI ratio) at the input of the DFT, i.e., the

method finds a timing point that minimizes the amount of ISI and maximizes the amount of

signal falling into the DFT window.


For this approach the symbol timing point for the nrth RX branch is found by:

ˆ argmax ( ) / ( )sig isim m m

k

k P k P k= (114)

where the expected signal and ISI power are given by (110) and (111), respectively. An

alternative approach would be to maximize the desired signal power in (110) or to minimize ISI

power in (111).


For the case of joint symbol timing for the entire MIMO receiver, the ratio of the total signal

power and total ISI power is calculated. The symbol timing point is then found by:

1 1

ˆ argmax ( ) ( )r rN N

sig isim m

k m m

k P k P k= =

=

∑ ∑

%

% % (115)

4.4.1.4 Reduced complexity algorithm

A less computational complex algorithm, i.e., requiring less operations for implementation, and

finds the maximum of the convolution of the CIR powers with a rectangular window of length

NCP, i.e., the length of the guard interval. In doing so, the algorithm attempts to maximize the

amount of ISI within the CP, i.e., minimizing the ISI within the DFT window.

94 Amir Saemi


In the extension for MIMO systems, the resulting timing point for the nrth RX branch is:

: :ˆ argmax ( ) ( )

CPk NH

m m m CPk i k

k i i N+

=

= + ∑ H H

%

% %

(116)


The extension for joint timing is given by:

: :

1

ˆ argmax ( ) ( )CPr k NN

Hm m CP

k m i k

k i i N+

= =

= + ∑ ∑ H H

%

% %

(117)

4.4.1.5 Simulation results

Here, our aim is to compare the different approaches of the methods with the knowledge of

channel to find the best algorithm between them. The performance of the algorithms are

evaluated by Monte Carlo simulations for a 4×4 MIMO extension of the IEEE 802.11a

standard, i.e., for Nc = 64 and NCP = 16.

In the following we will derive the performance of the symbol timing as function of the

accuracy of the channel estimation. Therefore, we define the Channel estimation -to-Channel

estimation Error Ratio (CCER) for the nrth RX branch as:

1

: :

0

1

: :

0

( ) ( )

( ) ( )

LH

m ml

m LH

m ml

l l

CCER

er l er l

−

=−

=

=

∑

∑

H HE

E (118)

which in fact equals the inverse of the normalized mean-squared-error (MSE) of the MIMO

channel estimate for the mth branch. The CCER averaged over the different RX antennas is then

denoted by CCER.

Although the MSE in symbol timing gives a measure for the error in the timing, it does not

show the degradation in performance due to this error. Therefore, the following figure will


report the achieved SIR (Signal to ISI ratio) with a certain timing algorithm as function of the

CCER. When the SIR has the same order of magnitude as or is larger than the experienced

SNR, the system performance will be limited by the ISI. In Figure 30 the SIR performance is

given for the channel delay equal to τ = 3NCP/8. The optimal SIR values obtained with perfect

timing are depicted as dashed lines. It can be observed that the reduced complexity model

achieves the bound for the lowest CCER value, closely followed by the SIR maximization

method. It is observed that the dominant path search method shows flooring below the

optimum, while it performs better than the SIR maximization algorithm for very inaccurate

channel estimates.

By comparison of the performance of the joint (dashed line) and RX timing (solid line), it can

be concluded that for the SIR maximization the joint timing performs a little worse than the

separate timing for low CCER values. For the reduced complexity and dominant path detector

this is the other way around.

Figure 30: Comparison of symbol timing results obtained by the methods with the knowledge

of channel

96 Amir Saemi

NCP Data

Np

robs N

Packet arrival instant estimated in the frame

synchronization phase

observation vector

k0

k k=0

4.4.2 ML MIMO-OFDM symbol timing

method

In ML MIMO OFDM symbol timing, we have assumed that the arrival of the preamble can be

identified by detecting the received signal energy in the frame synchronization procedure. It

means that, the coarse frame synchronization has succeeded to detect a packet arrival but the

precise beginning is not known. This could be due to dispersive effect of the propagation

channel and the use of a simple autocorrelation algorithm.

Figure 31: Illustration of symbol timing problem

Suppose the beginning of the preamble, as shown in Figure 31, is chosen as the time reference,

i.e. k=0. The receiver takes a signal vector of size N from estimated instant in frame

synchronization procedure as the observation vector (robs). Assume k0 as time offset of

observation vector with respect to beginning of the training sequence (Figure 31). We have to

perform symbol timing in order to find the exact place of the beginning of the training sequence

packet. By knowing the exact place of the training sequence packet, we are able to align the

start of FFT window within the OFDM symbol. The received observation vector at the mth

receive antenna, rm,obs, begins from k0th sample from the beginning of the training sequence

packet, in other words 0, , , 1 1[ ... ]+ − ×= T

m obs m k m k N Nr rr . The objective of our algorithm is to estimate

k0 from the observation vector rm,obs.


Suppose k0∈[−NCP, NP –N] the training sequence of nth transmit antenna is

,0 ,2 , 1... − Pn n n Nc c c where NP is the length of training sequence and the length of cyclic

prefix is NCP, the joint ML estimate of k0 and h0 can be obtained by maximizing:

2

, ,

1 1

2 2

1( , ) exp -

( )

tr NN

m obs n k nmm n

Nw w

p kπσ σ

= =

− =

∑ ∑C h

hobs

r

r (119)

where:

, ( , ) , ( 1, ) , ( 1, )

, ( 1, ) , ( , ) , ( 2, )

,

, ( 1, ) , ( 2, ) , ( , )

...

...

. . . .

...

− − +

+ − +

+ − + − − + ×

=

P P P

P P P

P P P

n mod k N n mod k N n mod k L N


n k

n mod k N N n mod k N N n mod k L N N N L

c c c

c c c

c c c

C (120)

[ ]1

(0) (1) ... ( 1)×

= − T

nm nm nm nm Lh h h Lh and hnm(l) is the equivalent channel between n

th

transmit antenna and mth receive antenna.

The development of this algorithm is somewhat similar to the ML-MIMO-OFDM joint

algorithm that will be presented in the next chapter. Therefore, we avoid here describing the

mathematical detail of algorithm. By maximizing (46) we find the following criterion to

estimate k0:

0ˆ argmax ( )= Ψ

k

k k (121)

where:

1

, ,

1

( ) ( )−

=

Ψ =∑ k

NrH H Hm obs k k k m obs

m

k r C C C C r (122)

SYMBOL SYNCHRONIZATION PERFORMANCE CRITERION

In [28] Erchin Serpedin states that since in Rayleigh multipath fading channel, the channel may

contain some small taps at the beginning, the starting position of the channel is not clear. So,

the beginning of the packet can be defined in so many ways: as the first non-zero tap of the

channel, as the first tap with energy larger than a certain threshold, as the position of the

98 Amir Saemi

strongest path or any other definition. In MIMO case the problem is even more complicated

because we have several different paths. Therefore, the symbol boundary of a received OFDM

symbol is not well defined. According to [28], even if we choose one of the above definitions as

the reference position, there is no guarantee that a certain synchronization algorithm giving

estimates close to the reference position would provide good performance in OFDM systems.

Moreover in OFDM systems, due to the existence of cyclic prefix, some timing offset can be

tolerated as long as the samples within the FFT window are influenced by only one transmitted

OFDM symbol. Therefore the criterion that the synchronization error has to be within certain

limits of a fixed reference point is not an appropriate performance measure for OFDM systems

in frequency selective fading channels. Hence, Erchin Serpedin uses the loss in system

performance due the synchronization error as a criterion for symbol timing. Serpedin derives

his criterion for the SISO systems. Here, we extend this criterion on the MIMO systems and

then we evaluate the performance of our algorithm by using this criterion.

Figure 32: OFDM symbol and FFT position

Suppose that the fast Fourier transform (FFT) window starts at position k0 (Figure 32), the

signal at the sub-carrier p after FFT operation has been written in [101] for SISO case. Using

the linearity properties we extend it over MIMO system, so the signal at the sub-carrier p, at the

mth receiver, after FFT operation, zm[p], can be written as:

[ ] [ ] [ ] [ ] [ ]02 ( / )

1

( ) It

FFT

Nj p N k

m nm n nm m mn

z p e k a p p p v pπηα

=

= + +∑ H (123)

where an[p] is the transmitted data from nth transmit antenna at sub-carrier p, [ ]nm pH is the

channel transfer function between nth transmit and mth receive antenna at sub−carrier p, wm[p]

NFFT - point FFT window

OFDM data

symbol

cyclic

prefix

k0


is the noise sample at sub-carrier p and mth receive antenna. NFFT is the number of FFT points in

the OFDM system. 0( )nm kα is the attenuation caused by the synchronization error, which is

approximated for SISO in [101] and we use it for MIMO system as well:

12

0

0

( ) ( )L

FFT lnm nm

l FFT

Nk h l

N

κα−

=

− ∆=∑ (124)

where:

0 0

0 0 ( )

0

l

k l k l

l N k k N l

otherwise

κ− >

∆ = − − < − −

(125)

and [ ]Im p is the ISI plus inter-carrier interference (ICI) term at sub-carrier p and mth receive

antenna because of timing offset that can be well approximated by Gaussian noise with power

[101]:

122 2

0

1 0

( ) ( ) 2 ( )t

m

N Ll l

I nmn l FFT FFT

k h lN N

κ κσ−

= =

∆ ∆= −

∑∑ (126)

The signal to interference-plus-noise ratio (SINR) per receiver can be written as:

[ ] [ ] 22

0

10 2 2

1 0

( )1

( )( )

t

r

m

N

N nm n nmn

mr I w

k a p pSINR k

N k

α

σ σ=

=

=+

∑∑

E H

(127)

We can rewrite also SINR by using (137):

[ ] 2 2 2

0

0 2 21 0

( )1( )

( )

rm

m

N m I w

mr I w

z p kSINR k

N k

σ σ

σ σ=

− −=

+∑E

(128)

When we know the channel coefficients, which is the ideal case, we can calculate k0 for the

ideal MIMO synchronizer by maximizing SINR. Note that for each of receive antennas (m),

[ ] 2| | mz pE is independent of m and p and thus we can maximize the following term to

maximize SINR.

100 Amir Saemi

0 2 21 0

1( )

( )

r

m

N

m I w

kkσ σ=

Γ =+∑ (129)

Using the equations (128), (124)-(126) we can calculate k0 of the ideal MIMO synchronizer

numerically by maximizing Γ(k0). The ideal symbol synchronizer can be served as a reference

to our practical synchronization algorithms.

For a particular realization of channel, let k0 be the start of FFT window estimated by our

symbol synchronization algorithm and kid be that of the ideal symbol synchronizer. Then the

loss of SINR, defined as the ratio of SINR obtained from the ideal symbol synchronizer to that

from non-ideal synchronizer is given by:

0

0

( )( )

idloss

SINRSINR k

SINR k= (130)

Noting that [ ] 2na pE is independent of n and [ ] 12 2

0

( )nm

L

nml

p h l−

==∑E H by using (127) we

have:

2 2

0

1 10 2 2 2 2

1 1 0

( ) ( )

( )( ) ( )

t t

r r

m m

N N

N Nnm id nmn n

lossm mI id w I w

k kSINR k

k k

α α

σ σ σ σ= =

= =

=+ +

∑ ∑∑ ∑

(131)

As In [28] and [43] we assume that a synchronization failure happens when the probability of

loss in SINR is greater than a certain thresholds, that is:

10( ) (10 log ( ) )γ γ∆ = > ∆f lossP P SINR (132)

where Pf(∆γ) is the probability of synchronization failure when the tolerable system degradation

(in dB) is ∆γ .

SIMULATION RESULTS

We provide a few Monte Carlo simulation results to illustrate the effectiveness of this

algorithm. In all of the simulations, the channel between a certain transmit and receive antenna

is modelled using an exponentially decaying power delay profile (PDP) with independent

Rayleigh fading on every tap. We assume that each channel has L = 15 and the channel delay is

50 nS, and a. The channel is fixed during transmission of one packet and independent of that of


another packet. Furthermore it is assumed that the length of FFT window or the OFDM symbol

is 64 and there is a cyclic prefix for each OFDM symbol with length 16.

As preamble, we use a single sequence with the length of an OFDM symbol and we use a cyclic

prefix of length 32 for our preamble. The preamble is generated randomly for each transmit

antenna. Our sampling vector length, N, is 64. So, the index k in (121) belongs to [32,0] and

also k0 is treated as a uniform random variable over this interval and value of k0 was randomly

generated in each iteration. For each simulation run, the loss of SINR is calculated using (131),

where the ideal symbol synchronizer uses kid such that (129) is maximized. Each point of result

is obtained by averaging over 104 Monte-Carlo runs.

Since this algorithm is somewhat similar to the algorithms presented [28] and [27], we compare

it with them.

Figure 33 represents the result of [28] and [27] for IEEE 802.11a specification SISO system.

The channel models are considered with 100nS and 30nS delay spread respectively.

Figure 34 presents our simulation results for a 4 × 4 MIMO system, but in comparison with

Figure 33 we have considered the channel models with 100 and 150 nS delay spread and the

curve shows the Pf (0.05dB) in contrast with Pf (0.5dB) for the case of SISO. As it can be seen

in the figure, the probabilities of failure are very small. Note that as it is described in [28] the

curves of Pf in general have a U shape form. This is because: At low SNRs, due to high level of

noise the synchronizer is not accurate and the error in time leads to a reduction in nmα and thus

an increase in the amount of loss (see(131)). At low SNRs nmα has a major role in the increase

of loss while at high SNR, in addition to nmα , 2

mIσ has a considerable effect on the increase of

loss. In fact, in high SNRs 2

mIσ is greater than 2

wσ and thus 2

mIσ will be directly proportional to

the increase in loss. Therefore, eve though at high SNRs the estimated positions can be quite

accurate, a small error with respect to ideal position leads to a large amount of loss in SINR.

Finally we want to mention that although we can not compare directly our results with that of

[28] and [27] because of different assumptions, but it is evident from the figures that the

performance of the proposed algorithm is much better than the SISO case. This improvement in

performance is quite reasonable since we have used a 4×4 MIMO system instead of SISO one.

102 Amir Saemi

Figure 33 : Pf(0.5) for the algorithms in [28] and [27] as a function of SNR

Figure 34: Pf(0.05dB) for the proposed algorithm in 4×4 MIMO system with 100 and 150 ns

delay spread as a function of SNR

Reported in [28]

Reported in [27]

SNR(dB)


5. JOINT TIME-FREQUENCY

MIMO−OFDM SYNCHRONIZATION

5.1 Introduction

We saw in the previous chapter that a number of methods for OFDM synchronization have

been proposed in the literature. The algorithms used for frame synchronization are not able to

determine the precise packet time arrival. This is a critical step since we have to perform

symbol timing after these algorithms. This chapter is our effort to establish a more sophisticated

time synchronization algorithm in MIMO−OFDM systems for both frame synchronization and

symbol timing. In addition to time synchronization, frequency synchronization and channel

estimation are addressed in this chapter. Part of this chapter has been presented in [4] but the

most part of this chapter will be submitted in [2].

5Chapter

104 Amir Saemi

5.2 Signal model

We consider a MIMO-OFDM communication system with Nt transmit and Nr receive antennas.

At each receiving antenna, a superposition of faded signals from all transmit antennas plus

noise is received. Let sn(t) be the baseband-equivalent signal of the preamble at nth transmitter.

This signal will be passed through a transmission filter and it will be up converted and sent to

the multipath fading channel. At the receiver, the signal is downconverted into baseband and it

will be passed through a receive filter. Let hnm(t) be the equivalent channel between the nth

transmit antenna and the mth receive antenna receive antenna which is quasi-static, i.e. it is fixed

during transmission of one packet and varies independently for each packet. The received signal

rm(t) at mth receive antenna can be written as:

2

1

( ) ( ) ( ) ( )tN

j t fm n nm m

n

r t e s t u u du w tπ+∞ ∆

−∞=

= − +∑∫ h (133)

where the term 2j t fe π ∆ denotes the phase rotation due to Carrier Frequency Offset (CFO).

As the previous chapters, we denote ε as: ε = ∆f × Ts (Ts is the sampling rate) and we use the

term CFO equivalent with ε. It is worthy to mention that theoretically each transmit–receive

antenna pair may have a different CFO [141]. In practice, however, the difference among these

CFOs is usually negligible, because, according to Giannakis [117]: 1) even if collocated

antennas do not share a radio frequency (RF) oscillator, achieving frequency synchronization

among collocated oscillators is relatively easy; and 2) in a number of applications, the

difference between Doppler shifts among all transmit–receive antenna pairs are approximately

negligible, so, similar to some other researchers like [114] [117] [142], we have considered in

our simulations a MIMO-OFDM system experiencing a single common CFO among transmit–

receive antennas.

Now we suppose that the received signal is sampled at t=kTs+η0Ts, , where k is the number of

sampled symbol and η0 ∈ [0,1) is the unknown time offset induced by the combination of

channel delay and the sampling phase offset, so we have:


2

0 0

1

( ) ( ) ( ) ( )tN

j km s s n s nm m s

n

r kT T e s kT u h u du w kT Tπ εη η+∞

−∞=

′ ′ ′+ = − + +∑∫

(134)

where 0 su u Tη′ = − . In an OFDM system due to FFT a delay in the time domain will be

converted into an offset in phase in frequency domain. Therefore, η0 will be appeared as a

channel phase and we do not need to estimate η0. Hence, the question of time synchronization

in OFDM systems is reduced to estimate k. According to [143], if the equivalent channel

bandwidth (Bh) satisfies Bh<1/Ts−Bs (Bs is the bandwidth of s(t) ), then by the equivalence of

digital and analogue filtering for band-limited signals, the sampled received signal can be

expressed as:

2

, ,

1

( ) ( )tN

j km k n s s nm s m k

n l

r e s kT lT lT wπ ε∞

= =−∞

= − +∑∑ h (135)

where rm,k rm(kTs+η0Ts), wm,k wm(kTs+η0Ts) and wm(t) is the stationary additive Gaussian

noise at the mth receive antenna which is independent of the other antennas.

The fading multi-path channel is considered to be quasi static. Supposing the channel length

equal to L, we have Nt×Nr paths, each of which can be modelled by an equivalent FIR complex

filter of order L−1 with hnm(l)=hnm(lTs) as the taps with l=[0,1,…, L-1]. These taps are assumed

to be independent zero mean complex Gaussian random variables with variance 1/2.P(l) per

dimension. The set P(l) with l=[0,1,…, L-1] is called the power delay profile (PDP) of the

channel and its total power is assumed to be normalized to σc2=1, which is the average total

channel power. Therefore (135) can be written as:

12

, ,

1 0

( ) ( )tN L

j km k n s s nm m k

n l

r e s kT lT h l wπ ε−

= =

= − +∑∑ (136)

Let rm,k be a received-signal vector of size N, sampled from time k to N+k−1 at mth antenna:

, , , 1 , 1 1...

T

m k m k m k m k N Nr r r+ + − × = r (137)

Let the training sequence of nth transmit antenna be ,0 ,1 , 1...Pn n n Nc c c − where NP is the

length of training sequence. If the length of the cyclic prefix for the OFDM word is NCP, we

take , , 1...P CP Pn N N n Nc c− − as the cyclic prefix of training sequence. Supposing -NCP+L-1 ≤ k

≤NP –N, we have:

106 Amir Saemi

, , ,

1

tN

m k k n k nm m kn=

= +∑r E C h w (138)

where:

, ( , ) , ( 1, ) , ( 1, )

, ( 1, ) , ( , ) , ( 2, )

,

, ( 1, ) , ( 2, ) , ( , )

...

...

. . . .

...

P P P

P P P

P P P



n k

n mod k N N n mod k N N n mod k L N N N L

c c c

c c c

c c c

− − +

+ − +

+ − + − − + ×

=

C (139)

[ ]1

(0) (1) ... ( 1)T

nm nm nm nm Lh h h L

×= −h (140)

matrix Ek denotes the phase rotation due to Carrier Frequency Offset (CFO) as follows:

2 2 ( 1) 2 ( 1)diag ...j k j k j k Nk N N

e e eπ ε π ε π ε+ + −

× = E (141)

Index k adds a constant phase that can be absorbed in channel coefficients, so it can be removed

without loosing generality. wm,k is a column vector containing the noise samples at the mth

receive antenna with covariance matrix σ²wIN (IN is the N × N identity matrix).

Stacking the received vectors from all the Nr receive antennas and using Kronecker product, we

have:

0 0( )rk N k k= ⊗ +r I E C h w (142)

where:

1, 2, ,1

...r

r

TT T Tk k k N k NN ×

= r r r r (143)

1, 2, ,...t

tk k k N k N LN×

= C C C C (144)

0 1 : 21

...r

t r

TT T TN LN N ×

= h h h h: : (145)

1 21

...t

t

TT T Tm m m N m LN ×

= :h h h h (146)


1, 2, ,1

...r

r

TT T Tk k k N k NN ×

= w w w w (147)

Figure 35- Finding the correct time instant (k=0) assuming sliding windows observations

5.3 ML Synchronizer

5.3.1 Packet arrival instant and initial CFO

estimation

As already mentioned in literature, two stages of time synchronization for an OFDM system are

normally distinguished. The first one is frame synchronization or coarse timing synchronization

and the other one is symbol timing or fine timing synchronization. In this section we propose a

new single-stage algorithm for time synchronization, that is, in our algorithm the result of frame

synchronization is accurate enough to indicate the fine starting point of the packet. Hence, in

our synchronization method, the two stages of synchronization are merged into a single stage.

The idea of calculation of complex correlation of two preambles, proposed in literature, is a

good way to detect packet arrival. This method calculates the correlation of received signal by a

delayed version of itself. The drawback of this method is that the correlation function does not

produce a sharp peak at the arrival of the data packet and thus, during the cyclic prefix period,

the correlation function remains constant and there is no abrupt falling edge outside this period.

Due to this phenomenon, which is inherent to the structure of training sequence, it is difficult to

find the fine packet time arrival instant. On the other hand, the performance of cross correlation

Sliding observation

windows

NCP

Data

N

rk

N

k

k=0

108 Amir Saemi

methods, which produces a sharp peak, is poor in dispersive and unknown channels [28].

Moreover, a frequency offset can degrade these methods considerably. We propose, hence, a

new robust solution to find the exact time of packet arrival in unknown dispersive channels and

in the presence of CFO.

Suppose we have a sliding window with length N, which starts from k to k+N. Hence, rk is the

observed received vector (Figure 35). We suppose also that the beginning of the preamble, as

shown in (Figure 35), is chosen as the time reference, i.e. k=0. The objective, then, is to find the

correct time instant k=0. To this purpose, we have to maximize the probability of receiving rk,

given the preamble, the carrier frequency offset, the time offset and the channel coefficients.

This probability can be calculated by using (142) as follows:

2

0 0 0

2 2

( )1( , ) exp

( )

r

r

k N

k N Nw w

p k επσ σ

− ⊗ = −

I E C hh,

rr (148)

where C0 is the training sequence matrix given in (144) can be written as:

0 1,0 2,0 ,0...×

= tt

N N LNC C C C (149)

By varying k and maximizing the probability of equation (148) the arrival instant of the

beginning of the packet can be estimated.

To estimate the arrival instant, instead of maximizing the probability we can equivalently

minimize following metric:

0 0 0 0( , ) ( ( ) ( ( )r r

Hk k N k NJ k ε = − ⊗ − ⊗h, I E C h) I E C h)r r r (150)

Setting the partial derivative of J(r | ε,k,h) with respect to h to zero, the ML estimate for h

(when k is fixed) is obtained as :

1

0 0 0 0 0 0[( ) ( )] ( )r r r

H HN N N k

−= ⊗ ⊗ ⊗h I E C I E C I E C r)

(151)

In order to have a unique solution for this equation, the number of observation points must be

more than the number of unknown channel coefficients i.e.: N×Nr > L×Nt×Nr.


Substituting equation (151) into equation (150), after some straightforward manipulations and

dropping the irrelevant terms, the packet arrival time is estimated by maximizing the following

likelihood function:

1

0 0 0 0 0 0 0 0( , ) ( )[ ( ) ( ) ] ( )r r r r

H H Hk N N N N kk ε −Ψ = ⊗ ⊗ ⊗ ⊗r I E C I E C I E C I E C r (152)

Using the well-known properties of the Kronecker product ( A ⊗ B ) -1 = A-1 ⊗ B-1 ,

(A ⊗ B)H= AH ⊗ BH and (A ⊗ B) (C ⊗ D) = (AC) ⊗ (BD), we have:

1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0( )[( ) ( )] ( ) ( )r r r r r

H H H H HN N N N NI − −⊗ ⊗ ⊗ ⊗ = ⊗E C I E C I E C I E C I E C C C C E (153)

Substituting this result into equation (152) the likelihood function would be:

1 1

0 0 0 0 0 0 , 0 0 0 0 0 0 ,

1

( , ) ( ( ) ( )r

H

r

NH H H H H

k N k m k m km

k ε − −

=

Ψ = ⊗ =∑H Hr I E C C C C E )r r E C C C C E r (154)

The arrival packet instant (k=0) and the carrier frequency offset ε can be calculated from the

received signal vector rk as follows:

,

ˆ ˆ( , ) argmax ( , )k

k kε

ε ε= Ψ (155)

Here we have to maximize a two dimensional function where one of the parameters is discrete

and the other is continuous. We use the following approach: we know that k can only take on

values in a finite set K , so we keep k fixed to some value k ∈K% , and we calculate ε :

( )ˆ( ) argmax ,k kε

ε ε= Ψ% % (156)

We will shortly explain how we can calculate ε from equation (156) . The final estimate of k

then becomes:

( )ˆ ârgmax , ( )k

k k kε∈

= ΨK%

% % (157)

Since k is a discrete parameter within a finite set we can estimate it by a numeric search. We

propose the following method to calculate continuous parameter ε from equation (156). We

rewrite equation (156) by using equation (154):

110 Amir Saemi

( ) 1

0 0, ,1

1 1* 2 ( )

,, ,1 0 0

ˆ( ) argmax , argmax ( )

argmax [ ]

rNH H H H

m k m km

Nr N Nj q p

p qm p k m q km p q

k k

r r e

ε ε

πε

ε

ε ε

φ

−

=Φ

− − − −+ +

= = =

= Ψ = ∑

= ∑ ∑ ∑

0 0 0 0r E C C C C E r% %

% %

% %1442443

(158)

Considering Hermitain symmetry of Φ we have:

1 2 12* 2 ( )

, ,, , ,1 0 0 1

( , )

( , ) [ ] 2 [ ]rN N N N

j q pp p p qm p k m p k m q k

m p p q p

k

k r r r e πε

ε

ε φ φ− − −

− −+ + +

= = = = +

′Ψ

Ψ = + ℜ

∑ ∑ ∑ ∑% % %

%

%

14444444244444443

(159)

(.)ℜ denotes the real part of a given quantity. Note that the first term in (159) is independent of

ε and has no role in the maximization of equation (158) so, to estimate ˆ( )kε % , we have to

maximize the second term. By denoting s = q – p, we can further simplify the second term:

12

1

( , )N

j ss

s

k r e πεε−

−

=

′ ′Ψ = ℜ ∑% (160)

Where we have 1

*

, , ,1 0

[ ]rN N s

s p p s m p k m p s km p

r r rφ− −

+ + + += =

′ =∑ ∑ % % . If we assume 0r′=0, equation (160) can be easily

computed by using the FFT algorithm:

( ) ( )ˆ( ) argmax , argmax ( )sk k FFT rε ε

ε ε′ ′= Ψ =% % (161)

By using the estimated ε , the packet time arrival index k can be found from equation (157) .

We make the following remarks:

• In our algorithm there is no constraint over training sequence structure. It means that we

can use one preamble or two consecutive repeated preambles

• Better frequency resolution can be achieved by zero-padding to effectively increase the

FFT length.

• FFT-based implementation, will significantly accelerate the search algorithm for ε

• The orthogonality between the preambles of different antennas is not assumed.


• By calculating arrival instant, the channel can be estimated using (151)

5.3.2 Residual CFO estimation

So far, by using the algorithm presented in section5.3.1, the arrival packet and CFO and

channel can be estimated. As we have seen just before, the frequency offset is estimated by

equation (156) and to solve the problem of maximization we have presented an FFT-based

algorithm. But, in the FFT algorithm, the accuracy of the frequency estimation is limited by the

length of FFT. The more accuracy we need, the longer the FFT is and thus the more

complexity is required.

It is possible however to propose two methods to solve the problem of maximization in (156)

when the carrier frequency offset is small. Hence, in this section we are going to present a new

simple iterative algorithm to estimate small carrier frequency offset in OFDM systems. we

suppose that carrier frequency offset estimation is performed in two levels. In the first level, a

coarse estimation is preformed by the FFT algorithm. As it will be shown shortly, a coarse

frequency estimate is sufficient for time synchronization. In the second level, after

compensating the frequency offset, we estimate CFO using more precise method. At this level,

the problem of time synchronization does not exist any more.

Figure 36: Timing failure probability resulted in time synchronizer without compensating CFO

with respect to ε. Various SNRs are considered

112 Amir Saemi

Figure 36 represents the probability of time failure for a 4×4 MIMO system as a function of ε

when the system lacks frequency estimation and compensation. In this system the arrival packet

time instant is estimated by following equation:

ˆ argmax ( )kε

ε = Ψ (162)

where , ,

1

1

( ) ( )r

m k m k

NH H H

m

k −

=

Ψ =∑ 0 0 0 0r C C C C r (as in (154) with ε = 0). The breaking point in Figure 36

denotes the maximum residual CFO that has no effect on time synchronization algorithm, and

this is done for each SNR. For example, for SNR ≥ 0dB, the residual ε can be up to 0.002

without significant loss in timing estimation. Thus, the resolution of our frequency estimator

should be at least about 0.002 corresponding to a 512-point FFT. Therefore, the arrival packet

can be estimated by using only a 512-point FFT to compensate CFO without the loss of

performance. When the arrival packet and channel coefficient and initial CFO are estimated, we

can then use the following method to improve CFO estimation. In the following frequency

synchronization algorithms, therefore, we suppose that the frame synchronization has been

performed perfectly, i.e. ˆ 0k = .

A) Residual frequency estimation --- method A

The goal is to maximize the criteria presented in equation (160). To this aim we set its

derivative with respective to CFO to zero that is:

(0, )0

d

d

εε

′Ψ = (163)

And we obtain the following equation:

12

1

0N

j ss

s

s r e πε−

−

=

′ = ∑I mage (164)

And so:

1

1

sin(arg( ) 2 ) 0N

ss

s r r sπε−

=

′ ′ − =∑ (165)

If we were to use the approximation arg( ) 2sr sπε′ ≈ , the problem could be solved very easily.

However it would be better if we find a better estimation for arg( )sr′ . Since we know that


1*

, , ,

1 0

[ ]rN N s

s p p s m p m p sm p

r r rφ− −

+ += =

′ =∑ ∑ and 2

, 0 :,:

j p H Hm p mpr e noiseπε = + C h , where 0 ,:

H

p C is pth row of

matrix C0 (eq.(149)), one can infer that arg( ) 2s sr s noiseπε β′ = + + where sβ is the angle of

1*

, 0 : 0 :,: ,:1 0

[ ] ( ) ( )rN N s

H H H Hp p s m mp p s

m p

φ− −

+ += =

∑ ∑ C h C h . By calculating sβ we can rewrite (165) as:

1

1

sin(arg( ) 2 ) 0N

s s s ss

very small

s r r sβ πε β−

=

′ ′ − − + =∑ 144424443

(166)

And by using the approximation sin( )x x≈ we can find CFO as:

( )1

1

1

2

1

cos( )(arg( ) ) sin( )1

ˆ2 p

N

s s s s ss

N

ss s

s r r

s r

β β βε

π

−

=−

=

′ ′ − +=

′

∑

∑

(167)

Therefore one can use the above equation to improve the frequency estimation. Equation (167)

is a bit complex, however by using a simple method we can achieve to the same performance as

equation (167). We will discuss about this new method in the following section (method B).

Moreover, it is worth consideration that the method B has exactly the same performance as

method A, while the method B is less complex.

B) Residual frequency estimation --- method B

The classical method to estimate the carrier frequency offset is to use cross correlation between

received signal and noiseless received vector but in this method channel knowledge is required.

Let us suppose that we have channel knowledge, CFO estimation can be derived as follows:

2

0 0 : ,0

1

2

: 0 0 ,0

1

21

2

: 0 ,0,:1 0

ˆ arg max

arg max

arg max ( )

r

r

r

NH

m mm

NH H Hm m

m

N NH H j sm ms

m s

s e

ε

ε

πε

ε

ε=

=

−−

= =

=

=

=

∑

∑

∑∑

(E C h ) r

h C E r

h C r

(168)

where 0 ,:

H

s C is sth row of matrix C0 (eq. (144)) and ,0 ( )m sr denotes the sth element of vector

,0mr . If we define : 0 ,0,:1

( ) ( )rN

H Hm ms

m

s s=

∆ = ∑h C r we have:

114 Amir Saemi

21 1

2 2

0 1

ˆ argmax ( ) arg max ( )N N

j s j s

s s

s e r s eπε πε

ε εε

− −− −

= =

′′== ∆ = ℜ

∑ ∑ (169)

where 1

*

0

( ) ( ) ( )N s

p

r s p p s− −

=

′′ = ∆ ∆ +∑ . Setting the derivative of (169) with respect to ε equal to zero,

we have:

1ˆ2

1

( ) 0N

j s

s

m sr s e πε−

−

=

′′ℑ = ∑ (170)

Or equivalently:

( )1

1

ˆ( ) sin arg( ( )) 2 0N

s

s r s r s sπε−

=

′′ ′′ − =∑ (171)

Lemma 1: arg( ( )) 2r s j sπε′′ ≈

Proof: We have defined : 0 ,0

1

( ) ( ,:) ( )rN

H Hm m

m

s s s=

∆ =∑h C r

We know from equation (138) , , , ,

1

tN

m k k n k n m m kn=

= +∑r E C h w and so:

2 ( 1)

,0 0 : ,( ) ( ,:) ( )j sm m m ks e s sπ ε−= +r C h w

Therefore: ( ) 22 ( 1) 2 ( 1)

: 0 0 : , : 0

1 1

( ) ( ,:) ( ,:) ( ) ( ,:)r rN N

H H j s j sm m m k m

m m

s s e s s e s noiseπ ε π ε− −

= =

∆ = + = +∑ ∑h C C h w h C

and

1 12 2

* 2

: 0 : 0

0 0 1 1

( ) ( ) ( ) ( ,:) ( ,:)r rN NN s N s

j sm m

p p m m

r s p p s e p p s noiseπ ε− − − −

+′

′= = = =

′′ = ∆ ∆ + = + +∑ ∑ ∑∑ h C h C

So, we can conclude that ârg( ( )) 2r s j sπε′′ ≈ . The more the power of noise is lower or the more

N is greater, the more this approximation is accurate.

Here, in contrast with method A, based on lemma 1, if the training sequence is sufficiently long

we have: ârg( ( )) 2r s j sπε′′ ≈ . Therefore, using the approximation sin(x)≈x, ε can be calculated

as follows:


1

1

1

2

1

( ) arg( ( ))1

ˆ2

( )p

N

sN

s

s r s r s

s r s

επ

−

=−

=

′′ ′′=

′′

∑

∑ (172)

We have to note that due to the presence of function arg(.) in (172), ε is ambiguous when

arg( ( ))′′r s exceeds π. This limits ε to be less than 1/2Np. For Np=64, ε have to be less than

1/128, therefore, if in the coarse frequency estimation we use an FFT with length 512, the

residual carrier frequency offset would be less than 1/128.

So our algorithm can be expressed as follows: in the first stage we estimate arrival packet

instant, the channel coefficients, and initial CFO (as described in method A.). After

compensating initial CFO by using channel coefficients estimated in the first stage, the residual

CFO is estimated by (172). Having estimated residual CFO, the channel estimation is updated

by (151), and by using this new channel coefficients, residual CFO estimate is updated by

(172). This procedure is repeated in an iterative manner.

5.4 Simulation results and complexity

5.4.1 Cramer-Rao Lower Bound

Stoica in [123] based on [122] has derived the Cramer-Rao lower bound for frequency

estimation in a SISO system. Following the same approach, we develop the Cramer-Rao lower

bound for carrier frequency offset in the MIMO systems:

Considering equation (142), the received signal r is a complex valued circularly symmetric

Gaussian vector with mean 0 0( )rN k= ⊗M I E C h (since we assume a perfect time

synchronization we can replace k by 0) and covariance matrix 2

wσ I . The parameter vector of

interest is [ ]TR Iε=Ω h h where Rh and Ih stand for real and imaginary part of 0h . For this

type of problem the estimation of 2

wσ is decoupled from that of Ω [144][123].

The Ficher Information Matrix (FIM) for Ω is given by [144][123]:

116 Amir Saemi

2

2 H

Twσ

∂ ∂= ∂ ∂

M MF

Ω ΩRe (173)

Besides, we have:

0

0

0 0 0

0

0

2 ( )

( )

( )

r

r

r

N

HH H

N

R

HH H

N

I

j

j

πε

∂ = ⊗∂∂ = ⊗∂

∂ = − ⊗∂

MI DE C h

MI C E

h

MI C E

h

(174)

where (0,1..., 1)diag N= −D . Using of (174) in (173) as well as using the well-known

properties of the Kronecker product yields:

2 2

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 02

0 0 0 0 0 0 0

4 ( ) 2 ( ) 2 ( )

22 ( ) ( ) ( )

2 ( ) ( ) ( )

r r r

r r r

r r r

H H H H H HN N N

H H HN N N

wH H H

N N N

π π π

πσ

π

=

⊗ ⊗ ⊗ − ⊗ ⊗ ⊗ ⊗ ⊗ ⊗

F

h I C D C h h I C DC h I C DC

I C DC h I C C I C C

I C DC h I C C I C C

I m Re

I m Re - I m

Re I m Re

(175)

The Cramer-Rao lower bound is obtained as the inverse of the FIM. For CRB of frequency

offset we only need to calculate the first element of the FIM’s inverse matrix.

In [123] stoica through a lemma ([123]-App. A) shows that if we have 1

2

2H

w h

F

F

ασ α

=

F the

first element of 1−F will be:

21 1 1

11 1( )2

TwhF

σ− − −= −F α F α (176)

Here we have:

2 2

1 0 0 0 04 ( )r

H HNF π= ⊗h I C D C h ,

0 0 0

0 0 0

2 ( )

2 ( )

r

r

HN

HN

π

π

− ⊗ = ⊗

I C DC hα

I C DC h

I m

Re and


0 0 0 0

0 0 0 0

( ) ( )

( ) ( )

r r

r r

H HN N

h H HN N

⊗ ⊗ = ⊗ ⊗

I C C I C CF

I C C I C C

Re - I m

I m Re

It can be proved that

1 1

0 0 0 01

1 1

0 0 0 0

( ) ( )

( ) ( )

r r

h

r r

H HN N

H HN N

− −

−

− −

⊗ ⊗ = ⊗ ⊗

I C C I C CF

I C C I C C

Re - I m

I m Re

Moreover, for any hermitian matrix O (e.g. 1

0 0( )r

HNI

−⊗C C ) and any vector x= xR+ xI (R and I

stand for real and imaginary part) it holds that R I RH T T

R II R I

− =

C C xx Ox x x

C C x

Therefore, the CRB for frequency offset which is equal to 1

11

−F is:

( )

( )( )( )( )

21

2 2 2 1

0 0 0 0 0 0 0 0 0 0 0 0

2 11

2

0 0 0 0 0 0 0 0 0 0 0 02

2 -11

0 0 0 0 0 02

( ) 4 ( ) 4 ( )( ) ( )2

( ) ( )8

( )8

r r r r

r r

r

H H H H H HwN N N N

H H H H H HwN N

H H HwN

CRBσε π π

σπ

σπ

−−

−−

−

= ⊗ − ⊗ ⊗ ⊗

= ⊗ − ⊗

= ⊗ 0

h I C D C h h I C DC I C C I C DC h

h I C D C h h I C DC C C C DC h

h I C D I -C C C DC h

(177)

Equation (177) can be written as:

-12

21

( )8

rNHw

m

CRBσεπ =

= Θ

∑ :m 0 0 :m

h C D C Dh (178)

where:

1( )H HNI

−Θ = −0 0 0 0

C C C C (179)

5.4.2 Algorithm complexity

To evaluate the complexity of the algorithm, we calculate the number of complex

multiplications which are needed to implement the algorithm. The algorithm is composed of

two stages. At the first stage initial frequency and timing offset and channel coefficients are

calculated. The second stage deals with the estimation of residual frequency error.

118 Amir Saemi

For frequency estimation using FFT algorithm, the needed number of complex multiplications

is equal to ( )2 ) 2 logrN N N R RΟ − +( , where R is the length of FFT. For the estimation of the

packet arrival instant the number of needed multiplications would be ( )2 3 ) rN N N DΟ +( where

D is the interval width in which we search for the arrival of packet. Although it seems that the

complexity of timing synchronization is rather high, but we have to note that its complexity is

at the same order as the complexity of classical approach in time synchronization. The

complexity of residual frequency estimation is equal to 2 )

2r t

N NNN N L

+Ο +

( in terms of the

number of multiplications. Our algorithm is a bit complex. But this complexity is the price to

pay to achieve high performance.

5.4.3 Simulation results

In practice, in a Rayleigh multipath fading environment, the channel may contain some small

taps at the beginning, so the starting position of the channel is not clear. Taking this into

account and in order to evaluate the performance of our ML time synchronization algorithm, we

introduce the criterion to reveal the probability that how far our time synchronizer calculated

instant is from the exact instant of packet arrival. Timing failure (tf) probability is introduced

similar to [25] as an indicator to illustrate the robustness of our algorithm. Ptf(p) is the

probability that the frame synchronizer misses an interval of 2p+1 samples centered at k=0.

This probability is expressed as follows:

( ) PrtfP p k p= >)

(180)

For the simulation setup we use a MIMO-OFDM system with QPSK modulation, the length of

an OFDM word is 64 symbols and there is a cyclic prefix for each OFDM word with length 8.

Exponentially decaying channel power delay profile of length 8 is used, decaying 3 dB per tap

in positive time direction. The channel is fixed during transmission of one packet and

independent of those of other packets. It is assumed that the average total TX power P is

distributed among the TX antennas such that σu2 = P/Nt. The SNR per receive antenna is

P/σw2=Ntσu

2/σw2.


As preamble, we use a single sequence with the length of an OFDM word (NP=64) and a cyclic

prefix; preambles are generated randomly for each transmit antenna. Our observation vector

length N is 64. The simulated burst consists of a preamble plus cyclic prefix, surrounded by two

random 64-carrier OFDM symbols (Nc=64) plus cyclic prefix. Hence, the synchronizer have to

search for the frame beginning at an interval of Nc+2Ncp=80 samples to the left and Nc+Ncp=72

samples to the right of the correct frame synchronization instant at k=0. Each point of result is

obtained by averaging over 105 Monte-Carlo runs.

Figure 37: simulation results for the probabilities of missing a ±p interval

Figure 37 presents our simulation results for a 4 × 4 MIMO together with the reported results in

[25]. The probability to miss a ±5 and a ±15 interval is plotted in the figure. It is clear from the

figures that the performance of the proposed algorithm is better than the SISO case. Simulation

results of lock-in probabilities are given in Figure 38 for various SNR. The asymmetry of the

120 Amir Saemi

figure is due to the channel length, that is, because Lock-in probability is represented

mathematically as follows:

Pr 0lock inP k− = =)

(181)

Figure 38: Simulation results for the lock-in probabilities in a dispersive channel. The

simulation are performed for various SNR

Figure 39 compares the performance of frequency estimation for this method with the different

method presented in chapter 3.2 together with Cramer-Rao Lower bound. The simulation setup

used for different methods is as follows:

To be able to compare our results with the presented results in the literature we use a 2×2

MIMO-OFDM system to illustrate the results of frequency synchronization. The other

specifications are the same as before. The carrier frequency offset (ε) is set to 0.1.

For FFT method (3.2.1), we used the same preamble as the preamble used by [118] (It was

proposed by [62]). For hopping-pilots method (section 3.2.2), in each OFDM transmitted block

we insert one pilot plus one zero symbol serving as a null subcarrier, and 64 OFDM blocks are

used for CFO estimation. By such a preamble, we are able to compare this method with the


others. For autocorrelation method (section 3.2.4), we use two same consecutive preambles

with length 32, each are made by a shift orthogonal code (Figure 18).

For FFT method a 1024 FFT are used. For our method that is the method presented in chapter

(so called iterative method) for initial estimation a 512 FFT is used. In hopping pilots the

resolution is set to .001.

Figure 39: Mean-Square-Error of Carrier Frequency Offset (CFO) for four presented methods

together with Cramer-Rao-Lower-Bound (CLRB)

All the diagrams have plotted in terms of Eb/N0. One can write Eb/N0 in terms of SNR as

follows:

b 0SNR=E /N +10 log(Rate)-10 log(.5)× × (182)

where Rate is the modulation rate, for example we use QPSK modulation so Rate=2.

Note that we have the floor effect of MSE at high SNR for FFT method and Hopping pilots

method. This effect, in FFT method, is due to the limited frequency resolution of FFT, which is

122 Amir Saemi

determined by the size of FFT, and in the Hopping pilots method is due to resolution of our

search. The next three curves residual CFO is estimated in an iterative manner as presented in

section 5.3.2. The last curve, which is the mean of Cramer-Rao lower bound for ε which is

estimated in (178)

Based on Figure 39, excluding FFT method, the three other methods have approximately same

result (Apart from consideration of the floor effect of hopping pilots method). So for

comparison between these algorithms we will need other criteria than the Minimum Square

Error.

In addition, Figure 15 showed us that a CFO less than 10-4 assures that we have no degradation

due to frequency error in a 2x2 MIMO OFDM systems. On the other hand by considering CRB

curve in Figure 39, one can find that for a large range of Eb/N0, the residual CFO is more than

10−4. Therefore, we simulated the iterative frequency synchronizer with various training

sequence length. The result of this simulation (Figure 40) shows us that either training sequence

length must be more than 64 or we have to accumulate the result of at least two packets to

estimate CFO.

Figure 40: BER of an iterative synchronizer with respect to various training sequence length.


Figure 41: Comparison of our synchronizer and the best known synchronizer for a 2×2 MIMO-

OFDM system

Figure 41 represents the comparison of our ML-MIMO-OFDM synchronizer with the best

synchronizer presented in literature. To the best of our knowledge, one of the best synchronizer

presented in literature can be achieved by using the autocorrelation method as both frame

synchronizer and frequency synchronizer (we have discussed about them in section 4.3.1

section 3.2.4, respectively) and by using the algorithm presented in 4.4.1.4 for symbol timing

estimation.

In Figure 41 the dashed line is the bit error rate for perfect synchronized 2×2 MIMO-OFDM

system. We compare our algorithm with the known synchronizer in two different cases: the

case of lacking carrier frequency offset and the case of existing frequency offset. In the case of

124 Amir Saemi

lacking CFO the best known algorithm is composed of autocorrelation method (section 4.3.1)

plus fine synchronization method 4.4.1.4). In the case of the presence of CFO the frequency

synchronization is performed with the method presented in section 4.3.1. As we can see from

the figure, in both cases the performance of our algorithm outperforms the performance of the

best known synchronizer however this is achieved at the price of higher complexity


6. EM-BASED MIMO-OFDM

SYNCHRONIZATION

6.1 Introduction

All of the algorithms presented in the previous chapters use a training sequence to perform

synchronization and thus can be categorized as data-aided algorithms. There are two problems

with data-aided algorithms: first, there would be a loss in spectral efficiency and second, data-

aided algorithms cannot be used in transmission mode and so they cannot be used for tracking

the synchronization parameters. To avoid these two problems so-called code-aided algorithms

can be used. As a matter of fact in these algorithms both frequency offset estimation and

symbol timing estimation can be performed by using the data portion of the frame containing

the information-bearing symbols. Recently, a great deal of papers has attempted to develop

6Chapter

126 Amir Saemi

code-aided (CA) estimation techniques. By using code-aided estimation one can use soft

information provided from the decoding process, in order to fully exploit the code properties

during estimation. Expectation-Maximization (EM) algorithm [124]-[128] is an efficient tool

for iterative joint estimation and decoding. There is much literature [129]-[132] on using EM

for channel estimation and decoding, whereas literature on code-aided synchronization is less

[131][132] and in particular, to the best of our knowledge, there is no paper dealing with code-

aided MIMO-OFDM synchronization. In this chapter we propose a code aided MIMO-OFDM

synchronizer by which carrier frequency offset and symbol timing as well as channel

coefficients can be estimated. This algorithm can be used to track the change of synchronization

parameters as well as an estimation of residual parameters. This algorithm has been developed

by us and is presented in [9] and submitted as a journal paper in [3].

6.2 System model

A MIMO-OFDM transmitter and receiver using EM synchronizer are shown in Figure 42. Let

us consider such a MIMO-OFDM communication system with Nt transmit and Nr receive

antennas.

Let the baseband equivalent signal at nth transmitter be sn(t), and hnm(t) be the equivalent

channel between nth transmit antenna and mth receive antenna. The received signal rm(t) at m

th

receive antenna is sampled at t=kTs+η0Ts , where Ts is the sampling time, and η0 ∈ [0,1) is the

unknown time offset induced by the combination of the channel first path delay and the

sampling phase offset. In OFDM systems η0 can be absorbed in channel coefficient and so the

sampled received signal can be expressed as:

12

, ,

1 0

( ) ( )tN L

j km k n s s nm m k

n l

r s kT lT h l e wπ ε−

= =

= − +∑∑ (183)


where rm,k rm(kTs), wm,k wm(kTs), wm(t) is the stationary additive Gaussian noise at mth

receive antenna which is independent of the other antennas and ε is the carrier frequency offset

induced through the term 2π εj ke . The carrier frequency offset is the multiplication of frequency

error by sampling time that is sf Tε = ∆ × where f∆ is the frequency error and sT is the

sampling time. The fading multi-path channel hnm(l) is considered to be quasi static. Supposing

the channel length equal to L, we have Nt×Nr paths, each of which can be modeled by an

equivalent FIR complex filter of order L-1. These taps are assumed to be independent zero

mean complex Gaussian random variables with variance 1/2P(l) per dimension.

Let the coded QPSK symbols of nth transmit antenna be ,0 ,1 , 1... − = cn n n n Na a aa where Nc

is the length of OFDM symbol. To convert coded symbols to an OFDM symbol we use the

inverse Fourier transformation. Suppose that IFFT of ,0 ,1 , 1... − cn n n Na a a is

,0 ,1 , 1... − cn n n Nc c c . That is:

1

,0 ,1 , 1 ,0 ,1 , 1... ...−− − = c cn n n N n n n Nc c c a a aF (184)

F denotes the normalized DFT matrix with (k,l) element equal to 2 ( 1)( 1) /

1/π− − − cj k l N

cN e .

By using the same notation as the previous chapter we can rewrite (183) as:

, , ,

1

tN

m k k n k nm m kn=

= +∑r E C h w (185)

Information

bits

encoder

Mapping

STBC

IFFT

IFFT

CP

CP

synchronization

synchronization

FFT

FFT

STBC

MAP decoder

p(ak|r,de(i))

de(i+1)

de(i+1)

∏

CP-1

CP-1

demapping

∏

∏-1

an cn

DETECTOR

128 Amir Saemi

Figure 42: MIMO-OFDM iterative synchronization

Each STBC code word consists of (P×Nt) STBC symbols, which are transmitted from Nt

transmitter antennas and across P consecutive OFDM slots at a particular OFDM subcarrier

(Figure 43). The STBC code words at different OFDM subcarriers are independently encoded,

therefore, during OFDM slots, altogether STBC Nc code words (or NcPNt ) STBC code

symbols) are transmitted. The first OFDM word is a preamble that is sent for initial

synchronization.

According to Tarokh [20], the STBC is defined by a P×Nt code matrix G, where Nt denotes the

number of transmitter and P denotes the number of time slots for transmitting a STBC code

word. Each row of G is a permuted and transformed (i.e., negated and/or conjugated) form of

the Nt dimensional vector of complex data symbols x. As a simple example, we consider a 2×2

STBC (i.e. Nt=2, P=2). Its code matrix G1 is defined by

1 2

1 * *

2 1

= −

x x

x xG (186)

The input to this STBC is the data vector x=[x1 , x2]T. During the first time slot, the two symbols

in the first row [x1 , x2] of G1 are transmitted simultaneously from the two transmitter antennas;

during the second time slot, the symbols in the second row [-x2*,x1

*] of G1 are transmitted.

In our STBC-OFDM system, we apply the above STBC encoder to data symbols transmitted at

different subcarriers independently. For example, by using the STBC defined by G1, at the kth

subcarrier, during the first OFDM slot, two symbols c1,k c2,k are transmitted simultaneously

from two transmitter antennas; during the next OFDM symbols, -c2,k* c1,k

* symbols are

transmitted.


Figure 43: Data burst structure.

6.3 EM algorithm

Expectation-Maximization (EM) algorithm is an algorithm to estimate a parameter de based on

an observation r in the case where the observation r depends also on another unknown

parameter (which is called the nuisance parameter) and estimation could have been easily

computed if we had access to this parameter. MAP and ML estimation are two possible

techniques to compute estimates of a parameter. MAP estimation exploits a-priori information

on the parameter. ML estimation is suited to problems where a-priori information is missing, or

when the parameter is non-random (i.e. unknown but deterministic). Straightforward

application of ML or MAP procedure is not possible in most estimation problems due to their

complexity. The EM algorithm is a technique that solves the MAP or ML problem in an

iterative way [124]-[128]. The EM algorithm at each iteration breaks down in two steps: the

Expectation step (E-step) and the Maximization step (M-step). The algorithms starts with an

initial estimate de(0) of de, E- and M-steps are performed successively and after each M-step a

new estimate of de is produced. Therefore, a sequence of estimates de: [de(0)

, de(1), de

(2) , …] is

obtained. When de is continuous, the EM algorithm will converge to a value de(∞).

Complete data

We refer to dc as the complete data. In order to qualify as valid complete data, we have the

following sufficient condition on dc:

0 1 2 … P … … P(Q-1)+1 P(Q-1)+2

…

PQ

one STBC-OFDM word one STBC-OFDM word

one

OFDM

word

Q STBC-OFDM words = PQ OFDM words

Pilot slot

130 Amir Saemi

p(dc,r| de) = p(r| dc) p(dc | de) (187)

so that the observation can depend on de only through dc. In other way, we can rewrite (187) as:

p(de |dc, r)= p(de |dc) (188)

Initial estimate: An initial estimate de(0) of de is required to start the EM algorithm.

E-step: At iteration i ≥ 0, the E-step is given by:

( )

( ) ( )

( )

( )

log ( , ) ,

log ( ) log ( ) ,

log ( ) log ( ) ( , )

=

= +

= + ∫

c

c

i ie e c e e

ie c e e

ie c e c e c

Q p

p p

p p p d

dd d d d r d

d d d r d

d d d d r d d

E

Ed (189)

M-step: Following the E-step, the M-step is given by:

( )( 1) ( )argmax+ =e

i ie e eQ

d

d d d (190)

Missing data: In many technical papers, dc = [r, dm], where dm is referred to as the missing (or

unobserved) data. In that case, dc is always a valid complete data. Often, dm will be independent

of de, so that the E-step becomes:

( )( ) ( )

( )

= log ( ) log ( , ) ( , )

log ( ) log ( , ) ( , )

i ie e e m e m e m

ie m e m e m

Q p p p d

p p p d

+ ∫

∝ + ∫

d d d r d d d r d d

d r d d d r d d (191)

Discrete parameters: When de is – or contains – a discrete parameter (finite value) there might

be the convergence problems. For example, symbol timing involves estimating a discrete

parameter. To avoid the convergence problems associated with (finite valued) discrete

parameters one can use the following approach [131]:

Let ,c d=b b b , where cb and db denote the discrete and continuous components of b ,

respectively. Assume that bd can only take on values in a finite set Bd. We keep bd fixed to

some value d d∈b B% and iteratively update only cb :


( ) ( 1) ( )argmax , ,+ = % %

c

i ic d c d cQ

b

b b b b b (192)

Let us denote by ˆ ( )%c db b the estimate obtained after convergence of the above equation. The

final estimate of db then becomes:

( ) ˆ ârgmax , ( )∈

=%

% %

d d

d d c dB

Qb

b b b b (193)

While the final estimate of cb is given by ˆ ˆ( )c db b .

6.4 EM synchronizer

We assume that the initial synchronization has already been done (e.g. using data aided

methods). It means that, the coarse frame synchronization has succeeded to detect a packet

arrival but the precise beginning is not well determined and despite the fact that carrier

frequency offset has been already estimated and compensated, there still exists a residual carrier

frequency offset.

We take the observation vector robs with length Nc. Assume k0 as time offset of observation

vector with respect to beginning of the training sequence. The objective of our algorithm is to

estimate h, k0 and CFO from the observation vector robs. Since the transmitted signal is not

known, a-priori information provided by MAP decoder is used to estimate the unknown

parameters. Estimation will be performed in an iterative manner by using EM algorithm. It is

worth mentioning the fact that there is a small residual correlation between the MAP encoder

(extern code) and STBC code (inner code) which is ignored because of the interleaver (Figure

42).

We now make use of the EM algorithm to estimate de=[k0, h, ε]. The coded data symbols can

be considered as the nuisance parameters. Defining the complete data dc=[robs, c], the E-step in

EM algorithm can be written as:

132 Amir Saemi

( ) ( ) ( )log ( ) ,=i ie e e eQ pcd d r d r dE (194)

and

2

0

2 2

( )1( , , ) exp -

( )

robs N k

obs Nw w

Ip kε

πσ σ

− ⊗ =

r E C hr h (195)

So we have:

( ) ( )

( )

2( ) ( )

0

2( )

0 0

0

- ( ) ,

- ( ) 2 ( ) ,

- ( ) 2 (

⊗ ⊗

⊗ ⊗

∝ − ⊗

∝ +

∝ ℜ

r

r r

Hr r kk k

i ie e obs N k e

H iN k obs N k e

H HN obs N

Q I

I I

I I

c

c

+CC C

d d E C h r d

E C h E C h r d

h h r Ε )h

E

E

E E

r

rRe

e

(196)

where ( ),Hk k

H ik k e=

C CC C r dE E and ( ), i

k e=C C r dE E .

To calculate the expectation of matrix C we use a-posteriori probabilities provided by MAP

decoder. Interleaved a-posteriori outputs of the MAP decoder are equal to p(ak|r,de(i)) and by

(184) we know that 1

,0 ,1 , 1 ,0 ,1 , 1... ...−− − = c cn n n N n n n Nc c c a a aF . We denote the

vector ,0 , 1...cn n Na a −

by nav

.

Since ( ) ( ) ( )=∑f f px

x x xE , the expectation of matrix C would be calculated as:

( )( ) ( ) 1 1 ( )1,

, , ( ) . ,n

i i ie e k n n k en k k n nc p

− − −

= = =∑a

r d f a r d f a a f a r dv

v v v vE E E

(197)

where 2 /1 1

[ ] 0,..., 1π− = = −cjpk N T

p c

c

e k NN

f is a row of IDFT matrix. The precise value of

Hk kC C

E is calculated in the appendix. However Hk kC C

E is approximately equal to ILNt×LNt. In order

to maximize Q we set the partial derivative of Q (eq. (196)) with respect to h to zero, we obtain

the estimate for h0 as:

( 1) 1

0( ) ( )+ −= ⊗ ⊗Hr rk k k

i HN N obsI I

C C Ch E rE E (198)

Intuitively speaking, the decoder does not work well in the first iterations and so kC

E would be

very small, whereas Hk kC C

E is always equal to ILNt×LNt and thus the estimate of h would be close


to zero; hence we may infer that our EM channel estimator is biased. Wautelet cites the same

phenomenon in [129]. By calculating the expectation of EM channel estimator one can

analytically verify that the EM channel estimator is a biased estimator. That is, the expected

value of channel taps by using (185) can be calculated as:

( 1) 1

0

1

0 0 0

1

0

ˆ ) ( ) ( ) )

( ) ( ) ( )

( ) ( ) ( )

Hr rk k k

Hr r rk k k k

Hr r rk k k k

i HN N obs

HN N N

HN N N

I I

I I I

I I I

+ −

−

−

= ⊗ ⊗

= ⊗ ⊗ ⊗

= ⊗ ⊗ ⊗

C C C

C C C C

C C C C

(h E (r

E E h

h

E E E E

E E E

E E E

(199)

It can be seen from (199) that there is a bias factor equal to 1( ) ( ) ( )−⊗ ⊗ ⊗H

r r rk k k k

HN N NI I I

C C C CE E E . To solve this problem we divide the EM channel

estimate by the biased factor and so the channel estimate will be:

( 1) 1

0( ) ( )+ −= ⊗ ⊗

r rk k k

i H HN N obsI I

C C Ch E rE E E (200)

Substituting equation (200) into equation (196), the delay [k0 , ε] can be estimated by

maximizing the following likelihood function:

( ) ( ) 1

0

1

0 0 ,

1

( , , ) ( ( )

( )

ε ε −

−

=

∝ ⊗

=∑

r k k k k

k k k k

i i H H Hm obs N obs

NrH H H Hm obs m obs

m

Q k k IC C C C

C C C C

r E )r

r E E r

,

,

E E E E

E E E E (201)

Therefore:

( 1) ( 1) ( ) ( )

0,

, argmax ( , , )ε

ε ε ε+ + = i i i i

k

k Q k k (202)

From (200) and (202), it appears that the estimation of channel is decoupled from the estimate

of time and frequency, that is, once one calculates the estimate of carrier frequency and timing

offset one can estimate the channel coefficients. In contrast, timing offset and frequency seems

not to be decoupled. However by using the method suggested in the previous chapter, we try to

decouple the estimation of frequency offset from timing offset.

To estimate ε, let suppose that [ ]0= ∈ −%CPk k N . Now we can simplify Q further as the

previous chapter:

134 Amir Saemi

, ,

1 1( ) 1 * 2 ( )

,

1 1 0 0

( , , ) ( ) [ ] πεε ε φ− −

− − −

= = = =Φ

∝ =∑ ∑∑ ∑% %144424443

r

obs m p m qk k k k

N Nr Nc Nci H H H H j q p

obs p qm m p q

Q k k r r e0 0C C C C

r E E rE E E E (203)

Considering Hermitain symmetry of Φ we have:

, ,

( )

1 2 12

( ) * 2 ( )

, , ,

1 0 0 1

( , , )

( , , ) [ ] 2 [ ] πε

ε ε

ε ε φ φ+

− − −− −

= = = = +

′

∝ +

∑ ∑ ∑ ∑

% %

% %

14444444244444443

r

m p k m q

i

N Nc Nc Nci j q p

p p m p p qm p p q p

Q k k

Q k k r r r eRe (204)

(.)Re is the real part of a quantity. Note that the first term in (204) is independent of ε and has

no role in frequency estimation and thus to estimate ( 1)ε +i we have to maximize the second

term. i.e. ( 1) ( )argmax ( , , )ε

ε ε ε+ ′= % %i iQ k k . By denoting s = q – p, we can further simplify the

second term:

1( ) 2

1

( , , ) πεε ε−

−

=

′ ′= ∑% %N

i j ss

s

Q k k r eRe (205)

where , ,

1*

,

1 0

[ ]φ+

− −

+= =

′ =∑ ∑r

m p m p s

N N s

s p p sm p

r r r .

Using equation (205), ( 1)ε +i can be estimated by the FFT algorithm. A better frequency

resolution can be achieved by zero-padding to effectively increase the FFT length. Moreover,

one can use the algorithm of Chirp z-transform (CZT), to increase sufficiently the FFT length

without considerable increase in complexity. Although using FFT (and CZT) algorithm

significantly reduces the complexity of the estimator, in the case of low carrier frequency

offsets, we propose a more reduced complexity algorithm to estimate ( 1)ε +i . Setting the

derivative of the equation (205) with respect to ε equal to zero, we have:

( 1)1

2

1

0πε +−

−

=

′ℑ = ∑c

iN

j ss

s

m sr e (206)

Or equivalently:

( )1

( 1)

1

sin arg( ) 2 0πε−

+

=

′ ′ − =∑cN

is s

s

s r r s (207)


Let’s suppose ( 1)arg( ) 2πε +′ ≈ isr j s for the moment. For small values of frequency error this

approximation can be supposed valid. However, if one is not satisfied with the approximation,

he can use one of the two methods presented in chapter 5.3.2). Using the approximation

sin(x)≈x, we have:

1 1( 1) 2

1 1

arg( ) 2πε− −

+

= =

′ ′ ′=∑ ∑Nc Nc

is s s

s s

s r r s r (208)

( 1)ε +i can be thus calculated as follow:

1

( 1) 1

12

1

arg( )1

2ε

π

−

+ =−

=

′ ′=

′

∑

∑

Nc

s si s

Nc

ss

s r r

s r

(209)

Presence of the arg(.) in (209) makes ε ambiguous when arg( )′sr exceed π. Therefore, ε must

to be less than 1/2Nc.

In brief, we keep k fixed to [ ]0 ∈ −%CPk N and we estimate ( 1)ε +i from (209) and update it

iteratively. An initial estimate is required to find the residual carrier frequency offset and in our

case where we had supposed that carrier frequency offset is very small, we can set the initial

value to zero. Let us denote by ˆ( )kε % the final estimate obtained for CFO after convergence, the

symbol timing can be estimated as follows:

( ) 0

ˆ ârgmax , ( )ε ∈ −

=%

% %

cpk N

k Q k k (210)

Note that no initial estimate is required for k. The final estimate of CFO is given by ˆˆ( )ε k .

As previously mentioned, EM algorithm is a biased channel estimator. To solve this problem

we proposed an unbiased version of EM algorithm. But still there is another solution for the

bias problem: In fact, if we use our EM algorithm in a Decision-Directed (DD) mode we can

avoid the bias problem. In the Decision-Directed (DD) mode the hard decisions on the symbols

are used instead of their expected values. In other words, the equations remain unchanged,

except that kC

E will be replaced by kC(

which is filled with ,

(n pc according to the pattern

presented in (144) and (139). ,

(n pc is the pth element of the inverse Fourier transformation of

(na

where ,0 , 1,..., − = ( ( (

cn n n Na aa and ,

(n qa is the hard decision made by the MAP decoder on the pth

136 Amir Saemi

symbol of the nth transmit antenna. Consequently, the EM estimator in DD mode is unbiased

and there is no need for a bias factor.

6.5 Simulation results

In the simulation we used a 2×2 MIMO OFDM system with 256 subcarriers. The length of

cyclic prefix is 32. As channel encoder, we used a (5,7) convolutional code. The log-MAP

algorithm is used for decoding. The size of each STBC-OFDM word is equal to 2 OFDM words

and each OFDM word is composed of 256 QPSK symbols. For sake of EM convergence and

supposing that an initial coarse frequency synchronization has already been done, we set the

maximum value of ε equal to 0.1 percent. Exponentially decaying channel power delay profile

of length 8 is used, decaying 3 dB per tap in positive time direction. The channel is fixed during

transmission of one packet and independent of those of other packets. It is assumed that the

average total TX power P is distributed among the TX antennas such that σu2 = P/Nt. The SNR

per receive antenna is P/σw2=Ntσu

2/σw2 . For the initial synchronization we used a training

sequence with length of 64 QPSK symbols.

Figure 44 represents the Bit-Error-Rate (BER) versus the Eb/N0. The dashed-line curve

corresponds to the case where synchronization is perfect. Figure 44 shows also BER for both

case of unbiased code aided synchronization (soft synchronization) and Decision Directed (DD)

synchronization. As previously mentioned, in the DD estimation we use the same algorithm but

instead of kC

E the hard decisions made by the decoder are used. The performance of the DD

synchronizer and the unbiased code-aided synchronizer is very close to each other (about 0.5

dB far from perfect synchronization). However, in both cases DD synchronizer and unbiased

code aided synchronizer a matrix inverse must be calculated in each iteration. In practice, we

know that both k k

H

C CE E in case of unbiased code-aided synchronizer and H

K KC C( (

in case of using

DD synchronizer are close to the unity matrix and so one can approximate them by the unity

matrix. This leads us to two further algorithms which can be called the approximation of code

aided and decision directed algorithms. In these algorithms a matrix inversion will be avoided

in each iteration and thus a great amount of complexity will be reduced. We note that the


approximation of unbiased code-aided algorithm is the same as the approximation of biased

code aided algorithm. Figure 44 shows that the performance of the approximation of DD and

code-aided (CA) synchronization is very close to the performance of unbiased CA and DD

algorithm. The first curve in the Figure 44 corresponds to the first iteration in the EM algorithm

and shows the case where we have an uncompensated residual synchronization error. As it can

be seen, even a very small amount of frequency offset can drastically degrade the overall

performance of the MIMO-OFDM system.

Figure 44: Comparison of iterative synchronization performance. Perfect synchronization;

unbiased code-aided synchronization; Decision Directed synchronization; the approximation of

Decision Directed synchronizer; the approximation of code-aided synchronization, the first

iteration in the synchronization that corresponds to the performance of system without

synchronization

BER

Eb/N0

138 Amir Saemi

Figure 45 represents the minimum square error of channel estimation. The unbiased EM

channel estimator has a poor performance in low SNRs but it outperforms other methods in

high SNRs. DD channel estimation has a good performance for all SNRs. Using the

approximation of the DD method, the performance of channel estimation is degraded slightly.

Moreover, the performance of biased estimator and approximate code-aided estimator resemble

to the performance of approximation of DD estimator.

Figure 45: Comparison of iterative channel estimation with different methods: Decision

Directed channel estimation; the approximation of Decision Directed channel estimator;

unbiased code-aided channel estimator; the approximation of code-aided channel estimator;

unbiased code-aided channel estimator.

.


Figure 46 represents the normalized mean square error of carrier frequency offset (CFO). In this

figure the results of both code-aided and decision-directed method are depicted. The

performance of frequency estimation is approaching the Cramer Rao lower bound in high

SNRs. The results of the approximations of code-aided and decision-directed methods are very

close to code-aided and decision-directed methods and thus the corresponding curves are not

drawn.

Figure 46: Comparison of the normalized mean square error of carrier frequency offset for both

methods: Decision-Directed and Code-Aided. The Cramer-Rao lower bound is also shown

Figure 47 depicts the performance of the MIMO-OFDM system per iteration. For this figure

(and for the Figure 48 and Figure 49 as well) we had an unbiased code-aided synchronizer

which works in Eb/N0=5dB. The performance of the system improves exponentially. In the first

iteration the performance is quite poor and within few iterations it improves considerably.

Figure 48 shows the normalized minimum square error of carrier frequency offset estimation.

Our estimation improves again exponentially. Figure 49 represents the improvement of channel

140 Amir Saemi

estimation. Unlike two previous figures, we do not have the best estimation in the first iteration.

That is due to the important effect of the carrier frequency offset on channel estimation. We

have set a rough initial value for the carrier frequency error and the performance of channel

estimation improves as soon as an improvement is made on the CFO estimate. It can be seen

from these figures that even by few iterations carrier frequency offset can be compensated

considerably and thus a great deal of improvement in performance is achieved. We can

conclude that code-aided synchronization can be a crucial task in the data transmission mode.

Figure 47: Exponentially improvement of the performance per iteration.

An unbiased code-aided synchronizer is used at Eb/N0=5 dB


Figure 48: Exponentially improvement of the normalized minimum square error of carrier

frequency offset per iteration. An unbiased code-aided synchronizer is used at Eb/N0=5 dB

Figure 49: Exponentially improvement of the minimum square error of channel estimation per

iteration. An unbiased code-aided synchronizer is used at Eb/N0=5 dB

142 Amir Saemi

Figure 50 shows the effect of the carrier frequency offset in the EM estimation of the channel

coefficients. In the figure the performance of the data-aided method in the genie estimator,

where there is no carrier frequency error and the information of training sequence is fully

exploited, is shown; this curve is approximately equivalent with the Cramer-Rao lower bound

for the channel estimation. Moreover, in this figure there are the curves for which we have used

decision directed EM algorithm to estimate the channel coefficients. For the initial estimation,

the existence of carrier frequency offset has little effect on the estimation of channel

coefficients. On the other hand, the existence of the carrier frequency offset has a relatively

considerable impact on the final channel estimation. However this effect will be attenuated in

the high SNRs, that is in Eb/N0=5 MSE of channel estimation is in about 0.5 dB from Cramer

Rao lower bound. Another interesting point in the figure is that the final estimation of channel

in EM method is worse than the initial estimation for the Eb/N0’s lower than 2dB. However,

since in the low SNRs part of the carrier frequency offset is compensated the overall

performance of the system in terms of BER is improved (Figure 44).

To evaluate the performance of time-synchronization algorithm, we use the same metric as

(180) Figure 51 shows the probability of timing failure. The first and the last curves correspond

to the optimised Data-Aided algorithm presented in the previous chapter for SISO and MIMO

cases. The performances of CA and DD methods, which are close to each other, are between

these two curves and in high SNRs the performance of CA and DD symbol timing approaches

the optimised data-aided algorithm.


Figure 50: Comparison of channel estimation in different situations: Decision Directed channel

estimation in the case where we do not have any carrier frequency error (genie); Decision

Directed channel estimation; The results of the first iteration in the EM algorithm in the case

where we do not have carrier frequency offset; The results of the first iteration in the EM

algorithm; Data aided estimation of a genie estimator.

144 Amir Saemi

Figure 51: Timing failure probabilities to miss a ±5 interval


Appendix 1: Computation of Hk kC C

E

Concerning the calculation of Hk kC C

E , we know from (144) that:

1, ,...t

rc

k N k N N L× =kC C C

Therefore:

1, 1, 1, ,

, ,

, 1, , ,

...

: :

...×

=t

t t tt t

H Hk k k N k

H Hm k n k

H HN k k N k N k

LN LN

k k

C C C C

C C C C

C C C C

Now, we can calculate ( ),, ,

ie

Hn k m k r dC CE as follows:

( )( ), , ,, , ,,,

1* ( )

, ,, 2

,( , )

( , , )

m n

c

m n

se

se

HHm nm k n kn k m k i j

i j

Ns

m n em k i n k jk

p

c c p

+

− −=

=

=

∑

∑ ∑

r dC C

c c

c c

r dC C c c

c c r d

v v

v v

v v

v v

E

1* ( )

, ,2 ,

1

,2

( , , )

c

m n

c

Ns

m n em k i n k jk

Nmnk i k j

k

c c p

y

+

− −=

+

− −=

=

=

∑ ∑

∑

c c

c c r dv v

v v

where ,0 , 1... − =v

cn n n Nc cc and ,

( )*, ,

,

,( , )p q

m n

se

mnm p n q m ny c c p= ∑

c c

r dc cv v

v v

Suppose 2 /1

[ ] 0,..., 1cjpk N Tp c

c

e k NN

π= = −f is a row of IDFT matrix. Therefore,

, = v Hm p m pc a f where ,0 , 1... −

=vcn n n Na aa .

,p q

mny can be calculated as below:

,

( )*, ,

, ,

* ( ), ,

,

* ( ), ,

,( , ) ( , )

( , , )

, )

p q

m n m n

c cm n

c c

se

mn H Hm p n q m n p m n q m n

H sp m i n j q m n eN N

s Hp m i n j e q

N N

Hq

y c c p p

a a p

a a

×

×

= =

=

=

=

∑ ∑

∑c c a a

a a

r dc c f a a f a a

f f a a r d

f r d f

fMf

v v v v

v v

v v v v v v

v v

E(

and therefore:

. .= Hy F M F

where F is Nc×Nc IDFT matrix equal to[ ] 2 /

,

1 π= cjmn N

mnc

eN

F .

am,i and an,j are independent if m≠n and i≠j and so:

146 Amir Saemi

( ) ( ) ( )* ( ) ( ) ( )

, , , ,, , ,*

s s sm i n j e m i e n j ea a a a=r d r d r dE E E (if m≠n and i≠j)

And if m=n and i=j, ( )*

, , 1=m i n ja aE in case of using QPSK modulation.

Hence to calculate HkC C

E we have to calculate ( ),, ,

ie

Hn k m k r dC CE and we showed that the ith, jth

element of ( ),, ,

ie

Hn k m k r dC CE is equal to

1

,2

+

− −=∑cN

mnk i k j

k

y where . . H=y F M F . The off-diagonal

elements of matrix M are equal to ( ) ( )( ) ( ), ,H

s sm e n ea r d a r dv v

E E and the diagonal elements of

M are equal to one.

However, k

HkC C

E is, in practice, approximately equal to identity matrix.


7. MIMO-OFDMA

SYNCHRONIZATION

7.1 Introduction

OFDM systems have given birth to OFDMA (Orthogonal Frequency Division Multiple Access)

systems. In the case of OFDMA, the set of available carriers is divided into groups called

subchannels and each user is assigned with one or multiple subchannels.

Of course, as the classical OFDM transmission scheme, OFDMA is very sensitive to Carrier

Frequency Offset (CFO) between the transmitter and the receiver. The presence of CFO entails

loss of orthogonality among carriers, leading to severe BER performance

7Chapter

148 Amir Saemi

degradation. In addition, coherent detection which constitutes the most performing demodulation

principle, implies an accurate Channel Impulse Response (CIR) estimation algorithm at the

receiver. The combination of CFO compensation algorithm and CIR guessing algorithm leads to

particularly complex algorithms in uplink OFDMA due to the number of unknowns.

The CFO estimation problem for uplink OFDMA has been already addressed in several papers

[133]-[135]. However, except the recent papers of Morelli [136]-[138], none considers the

extreme case in which any available carrier frequency can be allocated to each user. In fact two

methods are classically proposed for carrier assignment: the sub-band carrier assignment and the

interleaved carrier assignment. In each case, frequency carriers are always assigned by groups

according to particular spectrum sharing rules.

Morelli [136] proposes to investigate the case where a new user enters the network and, assuming

that the remaining users are already synchronized, he shows how to synchronize the new user. In

this chapter we investigate a more complex case because we propose a ML algorithm which

enables to jointly estimate CFO and channel for all new users simultaneously and regardless of

the carrier assignment scheme. We propose to study the case where all users enter simultaneously

the system. In this case, we assume that they send out pilot symbols on the carriers only assigned

to them. The proposed synchronization procedure is based on the EM algorithm and it can be

easily interfaced with MAP-EM demodulators. Using the EM principle for OFDMA

synchronization in a MIMO system is a new approach and, within the EM loop, we propose

MIMO OFDM original synchronization algorithms which yield to closed form solutions for the

estimation of each user’s CFO and channel parameters. Particularly, we propose a new powerful

joint CFO-channel estimation algorithm within the EM loop which enables to converge within

only a few iterations. The main drawback of the proposed algorithms is that new users entering

the network have to send training data sequentially on their transmit antennas i.e. at a given time

instant, only one transmit antenna per user is switched on. In fact, using an EM-based approach

enables to decompose a computationally intensive multi-dimensional optimization problem into

separate smaller ML optimization problems. Very recently, Morelli & al in [138] followed a

similar approach with the alternating-projection algorithm. As in our case, this enables the

authors to consider whatever kind of carrier assignment schemes. However, similar to our above

mentioned constraint on the way training data are sent into the network, the carrier


synchronization algorithm in this paper proceeds sequentially instead of jointly. As for Morelli’s

paper, simulation results show the ability of our proposed algorithm to reach the Cramer Rao

lower bound. However, the big difference between the two proposed papers, is that we consider

here the case of MIMO OFDMA systems whereas [138] deals with the case of Single Input

Single Output (SISO) systems and, due to this difference, a fair comparison between the two

systems is difficult. We think that the algorithm presented in [138] can be extended to the case of

MIMO systems but, due to the use of performing algorithms within the EM loop, we believe that

our algorithms will converge faster than an extended version of [138].

150 Amir Saemi

7.2 System Description

We consider a MIMO OFDMA system with Nc carriers and Nu users using LDPC channel

encoders. Each user is equipped with Nt transmit antennas and the Base Station has Nr received

antennas. We denote Ω the set of all possible transmitted symbols. The Nt. Nc. 2log Ω

information bits of user k are first encoded by a rate 1/R N= LDPC encoder into

2( . . .log ( ))t cN N N Ω coded bits and then the binary LDPC coded bits are modulated into

( . . )t cN N N MPSK symbols. These ( . . )t cN N N symbols are split into N streams of ( . )t cN N

symbols.

Then, the ( . )t cN N symbols 1,0 1, 1 2,0 2, 1 ,0 , 1( ),..., ( ), ( ),..., ( ),..., ( ),..., ( )c c t t c

k k k k k kN N N N Nx n x n x n x n x n x n− − − enter

Nt IFFT modules of size cN . The number of IFFT modules is equal to the number of transmit

antennas. For a given output block 1( ) , 1, 2,...,c

kp N tn p N× =s of an IFFT module (pth block for

example corresponding to ,0 ,1 , 1 1( ) [ ( ), ( ),..., ( )]

c c

Tk k k kp p p p N Nn x n x n x n− ×=x ), there are some zero

components where the corresponding carriers are not used ( , ( ) 0kp js n = for carriers j = n1,n2,…).

The corresponding time-domain output of the IFFT module can be written as:

1 1( ) . ( )c c c c

k H kp N N N p Nn n× × ×=s W x (211)

with 1

( , ) .exp( .2. .( 1).( 1) / )cc

n m j n m NN

π= − − −W . A cyclic prefix (CP) of length CPN is then

inserted in ( )kp ns to form ( )k

p nu of length s c CPN N N= + to combat the dispersive nature of the

transmission channel. This operation can be described as: 1 1( ) . ( )s s c c

k k kp N p N N p Nn n× × ×=u sΘΘΘΘ where k

pΘΘΘΘ

denotes the matrix of CP added symbols. The channel between transmit antenna p and receive

antenna q for user k is a MIMO frequency selective channel and it is denoted as:

,[ (1),..., ( )]k k k k Tpq pq pq p qh h L=h (212)

This expression takes the shaping filters’ impulse response into account. Using (212) and the

definition of ( )kp nu and assuming the presence of CFO and timing errors in reception we can

write the output of the BS receive filter at time m for receive antenna q as:

,.2 .

,1 1 1

( ) ( ). ( ) ( )

kp qu t

k

LN Nj m k k k

q pq p p q qk p l

r m e h l u m l w mπε µ= = =

= − − +∑ ∑ ∑

(213)


k k sf Tε = ∆ is the normalized angular frequency offset with respect to the carrier spacing for the

kth user. ,kp qµ corresponds to the kth user’s integer-valued timing error encountered over the pth

transmit qth receive antenna link. The fractional timing error is indistinguishable from the phase

of the channel impulse response and is incorporated in kpqh . wq(m) is a zero-mean white Gaussian

noise sample. Note that for normalization purpose, the transmitted power on each antenna is

equal to 1/Nt. Figure 52 illustrates the synchronization problem with the definition of ,kp qµ in the

case q = 1. At the BS station, the serial-to-parallel (S/P) conversion transforms rq(m) into rq(n)Q×1.

We then form the vector yq(n) by discarding the CP from rq(n). To simplify the complex

estimation problem of the relative delays ,kp qµ , the MIMO channel impulse response ,

kp qh of each

user and the offset frequency kε we first show that the estimation of the relative delays can be

embedded into the channel impulse response estimation problem. To do this we define at first

max , , , ,max k kp q k p q p qL Lµ= + . If we assume that maxCPN L≥ , each received block rq(n) q =

1,…,Nr contains only intersymbol interference from its immediate previous block and, after the

cyclic prefix removal, the blocks ( ) [ ( . ), ( . 1),...., ( . 1)] Tq q s q s q s cn y n N y n N y n N N= + + −y , contain

no intersymbol interference. This condition generally holds for OFDMA systems. After CP

removal, the received signal yq(n) can be written in matrix form as:

., ,

1 1

( ) ( ) ( ) ( )u t

kN N

j k k kq k p p q p q q

k pn e nε ε µ

= == +∑ ∑ w

%y A hΕΕΕΕ (214)

We have ( )k k s CPnN Nε ε= +% which is the phase term associated with block n and

.2 2 ( 1)( ) (1, , , )k k

c c

j j Kk N Ndiag e eπε π εε −

×= LΕΕΕΕ . The definition of the circulant matrix ,( )k kp p qµA is

given just below.

,

, , , ,

, , , ,,

, , , ,

( ) ( 1 ) ( 1 )

( 1 ) ( ) ( 2 )( )

( 1 ) ( 2 ) ( ) kc p q

k k k k k k kp p q p p q p p q p q

k k k k k k kp p q p p q p p q p qk k

p p q

k k k k k k kp c p q p c p q p c p q p q N L

u n u n u n L

u n u n u n L

u n N u n N u n N L

µ µ µ

µ µ µµ

µ µ µ×

− − − + − − + − + + − −

= + − − + − − + − −

L

L

M M O M

L

A (215)

Using the definition of )( ki

ki µA we have the following relationship:

152 Amir Saemi

Figure 52: Illustration of multipath and timing errors for user 1, receive antenna 1.

,

, , , ,

, , , ,, , ,

, , , ,

( ) ( 1 ) ( 1 )

( 1 ) ( ) ( 2 )( ).

( 1 ) ( 2 ) ( ) kc p q

k k k k k k kp p q p p q p p q p q

k k k k k k kp p q p p q p p q p qk k k k

p p q p q p q

k k k k k k kp c p q p c p q p c p q p q N L

u n u n u n L

u n u n u n L

u n N u n N u n N L

µ µ µ

µ µ µµ

µ µ µ×

− − − + − − + − + + − −

= + − − + − − + − −

L

L

M M O M

L

A h h,

,

,

, ,

,

1

1

, 1

( ) 11

, ,

( ) ( 1) ( 1)

( 1) ( ) ( 2).

( 1) ( 2) ( )

( ).

kp q

kp q

kp q

k kg p q p q

CPc CP

kp q

L

k k kp p p CP

k k kp p p CP k

p qL

k k kN Lp c p c p c g NN N

p p q

u n u n u n N

u n u n u n N

u n N u n N u n N N

n

µ

µ

µ

×

×

×

− − × ××

− − + + − + = + − + − + −

=

L

L

M M O M

L

k

h

A h

0000

0000

k

(216)

Equation (216) clearly shows that the estimation of the delays ,kp qµ can be embedded into the

estimation of the channel impulse response. Hence, the CIR ,kp qh becomes

,, , kp q

kp q µh . In fact, the

position of the first non-zero element in ,, , k

p q

kp q µh indicates the timing error associated with user k

11,1µ +

11,1L

1,1tN

µ

1,1tN

µ +1

,1tNL

y(n)

11,1µ

multipath 1

multipath 2

uNt(n) multipath 1

uNt(n) multipath 2

uNt(n)

discarded

multipath 1

1,1L

multipath 1

,1NtL

1

1( )u n

1

1( )u n

1

1( )u n

1

( )Nt

u n

1

( )Nt

u n

1

( )Nt

u n


and the parameter ,kp qL can be found by counting the number of non-zero elements in

,, , kp q

kp q µh . We

can rewrite (216) in the following form:

,

,

.

, ,1 1

, ,1 1

( ) ( ) ( ) ( )

( ) ( )

u tk

kp q

u t

kp q

N Nj k k

q k p qp qk p

N Nk kp k qp q

k p

n e n n

n

εµ

µ

ε

ε

= =

= =

= +∑ ∑

= +∑ ∑

y A h

G h

%w

w

ΕΕΕΕ (217)

with .

( ) ( ). ( )kjk kp k k pe nεε ε= %

G AΕΕΕΕ . For the next section and the EM algorithm derivation, we

assume the case when all users are new users who want to enter the system. It constitutes the

most difficult situation due to the high number of unknowns. To solve this critical issue, we

suppose that all users send out pilot symbols on the carriers assigned only to them in the nth

block simultaneously. The pilot symbols are organized in the same way as those given in [140],

that is, the first OFDM word in the packet contains pilot symbol and the others carry out

information symbols.

7.3 EM synchronization algorithms

For the following steps we will consider the most difficult case when all users are new users.

Since w(n) is assumed to be a zero-mean Gaussian noise, the least-squares solution is also the

maximum likelihood (ML) solution. The maximum likelihood estimates of kε and , k

i

ki µh are given

by minimizing the following quadratic cost function:

,

2

ε, , ,1 1 1

min ( ) ( )u tr

kp q

N NNk k

q p k p qq k p

n µε= = =

−∑ ∑ ∑

h y G h (218)

with: 1 2, , ,u

T

Nε ε ε = ε L and

1 1 1 1 1 11,1 1,2 1, ,1 ,2 ,

1,1 1,2 1, ,1

1 1 1 1 1 1

1,1, 1,2, 1, , ,1, ,2, , ,

1,1, 1,2, 1, , ,1,

[( ) , ( ) ,..., ( ) ,..., ( ) , ( ) ,..., ( ) ,...

,..., ( ) , ( ) ,..., ( ) ,..., (

r N t N t N t r N Nr t t t r

u u u uN N N Nu u u u

r tN Nr t

T T T T T TN N N N N

N N N NT T T

N N

µ µ µ µ µ µ

µ µ µ µ

=h h h h h h h

h h h h,2 ,

,2, , ,) , ( ) ,..., ( ) ]u u

N Nu ut t rN N Nt t r

N NT T T T

N N Nµ µh h

Instead of directly solving the multi-dimensional optimization problem we propose to use an EM

(Expectation-Maximization) approach. Our approach here is based on Feder and E.Weinstein’s

approach in [126]. They use EM-algorithm for parameter estimation of superimposed signals. Xie

and Georghiades in [130] used the same method to convert MIMO-OFDM channel estimation

154 Amir Saemi

into several SISO OFDM channel estimation. We use here the same method for OFDMA

synchronization. It should be noted that Feder and E.Weinstein use EM algorithm in a special

case and although their equations are driven from the classical EM equations they appear

somewhat different:

7.3.1 Using EM algorithm

y is the observed data and as the complete data we choose kqd , k = 1,2,…,Nu which is given by:

,, ,1

( ). wkp q

k k k kq p k qp q

pµε

== +∑

tN

d G h (219)

where 1

uN kq q

k== ∑w w . Thus,

1

uN kq q

k== ∑y d , where k

qd is the component in the received signal yq

contributed by the kth user. The EM algorithm starts with an arbitrary initial guess (0)kε) k =

1,…,Nu, and ,, ,

ˆ (0)kp q

kp q µh , k = 1,…,Nu, p = 1,…, Nt, q = 1,…,Nr. We suppose that at the mth

stage

of the algorithm, we have obtained the set of estimated values ˆˆ[ ( ), ( )]m mε h :

1 2ˆ ˆ ˆ ˆ( ) ( ), ( ), , ( )

u

T

Nm m m mε ε ε = Lε and

1 1 1 11,1 1, ,1 ,

1,1 1, ,1

1 1 1 1

1,1, 1, , ,1, , ,

1,1, 1, , ,1, , ,

ˆ ˆ ˆ ˆ ˆ( ) [( ( )) ,..., ( ( )) ,..., ( ( )) ,..., ( ( )) ,...

ˆ ˆ ˆ ˆ,..., ( ( )) ,..., ( ( )) ,..., ( ( )) ,..., (

r N t N t r N Nr t t r

u u uN N Nu u u

r t t rN Nr t

T T T TN N N N

N N NT T T

N N N N

m m m m m

m m m

µ µ µ µ

µ µ µ µ

=h h h h h

h h h h,

( )) ]uNuN Nt r

N T Tm

For the (m+1)th iteration, the parameters are updated by the following procedure:

E-step (Expectation Step): As Feder and Weinstein showed in [126] the calculation of expected

value of Q function will lead to calculate the following terms:

For k = 1,…,Nu, p = 1,…,Nt and 1,..., rq N= :

,, , ,

ˆ ˆˆ( ) ( ( )). ( )kp q

k k kp q p k p q

m m mµε=b G h (220)

, , , ,1

ˆ ˆ ˆ( ) ( ) ( )uNk k j

p q p q k p q p qj

m m mβ=

= + − ∑

d b y b (221)

,1

ˆ ˆ( ) ( )tNk k

q p qp

m m=

= ∑d d (222)


where 'k sβ are chosen such that 1

1uN

kk

β=

=∑ and ,p qy represents the sum of the contributions from

transmit antenna p to the complete receive vector of antenna q: , ,1 1

t uN Nk

q p q p qp k= =

= =∑ ∑ ∑p

y y y . In

general, , ,1

uN kp q p q

k== ∑y y can’t be obtained directly from qy . To obtain this parameter vector, one

has to assume that the different transmit antennas of each user send their training data

sequentially in the network i.e. the other transmit antennas are switched off. This means that

during the training period, we have to solve Nu parallel SIMO identification problems. This

implies a quasi-synchronous system in a micro-cell environment for example. In this case, each

user would achieve timing acquisition through a downlink synchronization channel before

initiating the uplink transmission. In the case of SIMO systems where each user is equipped with

only one transmit antenna, the problem is directly simplified and the Expectation Step can be

written with obvious notations:

,ˆ ˆˆ( ) ( ( )). ( )k

q

k k kq k qm m mµε=b G h

(223)

1

ˆ ˆ ˆ( ) ( ) ( )uNk k j

q q k q qj

m m mβ=

= + − ∑

d b y b (224)

M-step (Maximization Step): Moreover, Feder and Weinstein showed in [126] that the

maximization of Q function entails the following minimization:

For k = 1,…,Nu:

,

2

, ,1 1,

ˆ ˆˆ[ ( 1), ( 1)] argmin ( ) ( ).tr

kp qk

k

NNk k k k

k q p k p qq p

m m m µε

ε ε= =

+ + = −∑ ∑ h

h d G h (225)

with: 1, , 1, ,1,1, ,1, 1, , , ,

ˆ ˆ ˆ ˆ ˆ( 1) [ ( 1),..., ( 1),..., ( 1),..., ( 1)]k k k kq t N q r q t r N qt t

k k k k k TN N N N

m m m m mµ µ µ µ+ = + + + +h h h h h . The

problem with (225) is that we have to estimate two parameters with only one cost function. We

propose at first to estimate the parameter ˆ ( 1)k mε + . We have:

, ,

.

, , , ,1 1

( ). ( ). ( ).t t

kk kp q p q

N Njk k k k

p k k pp q p qp p

e nεµ µε ε

= ==∑ ∑

%G h A hΕΕΕΕ (226)

We can use a matrix form to rewrite equation (226). We obtain:

156 Amir Saemi

,. . 1, ,

1

( ). ( ) .t

kt g t gp q

Nk k kp k F k K N N q N Np q

pµε ε × ×

==∑ G h V h (227)

with: ( )1, 2, ,1, , 2, , , ,

. 1

...k k kq q t N qt

t CP

Tk k k kq q q N q

N Nµ µ µ

×=h h h h ,

.( ) ( ). ( )kj

F k k ke nεε ε= %V A.Ε.Ε.Ε.Ε

and 1.

( ) ( ),..., ( )t

t g

k kk N K N Nn n n

× = A A A

The ML estimation of kε leads to the following mathematical development:

1

ˆˆ argmax ( ) argmax log ( ( ) ( ))rN

kk k k q k

qQ p mε ε ω

== = ∑ d ΕΕΕΕ (228)

Assuming that: ,, ,

1

ˆ ( ) ( ). ( )t

kp q

Nk k k kq p k qp q

pm mµε

== +∑ wd G h and following the same approach as those

given in [140], we obtain:

2ˆ ( ),1

2

1

ˆ( ) ( ( ) ( ). )

ˆ ˆ( ( ) ( ). trace( ( ). . ( )) )

r

k qq kk

r

kq

Nk k

k k q F k qmq

Nk k Hq F k q F k F k

q

Q m const

m const

εε ε

ε ε ε

=

=

= − − +∑

= − − + +∑ %

h d

h

d V h

d V h V VΣΣΣΣ

E

(229)

with:

( ) 1-1 1ˆ ( ). . ( )k k k

q q q

HF k F kε ε

−−= +

wh hV VΣ Σ ΣΣ Σ ΣΣ Σ ΣΣ Σ Σ (230)

and

-1 ˆˆ . ( ). . ( )k kq q

k H kq F k q mε

w%

hh = V dΣ ΣΣ ΣΣ ΣΣ Σ

(231)

Using (229), we propose two different ways to obtain the estimation of the frequency offset: they

are named algorithm 1 and algorithm 2. The first one does not need estimation of users’ channel

parameters whereas the second one uses at each step the former estimation of the channel

parameters to help enhance the estimation of the carrier frequency offset.

- Algorithm 1 (FFT–based algorithm): It is possible to further simplify the expressions given in

(230),(231). We have:

( ) 2 2 2 21, 1, , ,( . ) diag[( (1)) ,..., ( ( )) ,..., ( (1)) ,..., ( ( )) ]k

t tq

Hk k k k k kq q q q CP N q N q CPN Nσ σ σ σ= =

hh hΣΣΣΣ E (232)


with:2

2, ,( ( )) ( )k ki q i qj h jσ =

E . Concerning the computation of k

qwΣΣΣΣ , we have directly:

( ) 2

w( . ) .k k

q q

Hk kq q Kσ= =

ww w IΣΣΣΣ E (233)

A great simplification is then made if we remark that the matrix product leads to diagonal

matrices with value /c tN N on the main diagonal. Using the

approximation .( ). ( ) .t CP

H cF k F N N

t

N

Nε ε ≈V V I , we obtain first:

1

2 1 2. .

ˆ .1/ . . . for classical SNR valuesk k k kt CP t CPq q q q

c tN N N N

t c

N N

N Nσ σ

−−

≈ + ≈

w wh hI IΣ ΣΣ ΣΣ ΣΣ Σ (234)

and then, ( ) ˆ/ . ( ). ( )k H kq t c F k qN N mε≈%h V d . Eventually, ( )k kQ ε is simplified as:

22

1

.ˆ ˆ( ) ( ( ) . ( ). ( ). ( ) trace ( ). ( ) )

kr qN t

k H k Htk k q F k F k q F k F k

q c c

NNQ m m

N N

σε ε ε ε ε

=

= − − +∑

wd V V d V V (235)

The second term,

2.trace ( ). ( )

kq

tH

F k F kc

N

N

σε ε

wV V , is independent of kε and hence has no

contribution to the detector. The ML algorithm for the determination of kε is thus:

2

.1

ˆˆ ( 1) argmin ( . ( ). ( )). ( )r

k t CP

NH kt

k N N F k F k qq c

Nm m

Nεε ε ε=

+ = −∑ I V V d (236)

Expression (236) enables to obtain a rough guess of the frequency offset kε . However, it is

possible to obtain a more accurate estimation by using a FFT-based search algorithm. Developing

(236) and dropping terms irrelevant of kε , we obtain:

[ ]

1

1 1 *. ( )

,1 0 0

ˆ ˆˆ ( 1) argmin ( ) . ( ). ( ). ( )

ˆ ârgmin ( ) ( ) .

r

k

c crk

k

Nk H H k

k q F k F k qq

N NNj p rk k

q k qp rp rq p r

m m m

m m e

ε

εε

ε ε ε=

− −−

= = =

+ = ∑

= ∑ ∑ ∑

d V V d

d Q d

(237)

with ( ). ( )Hk k kn n=Q A A , (237) can be further written in the form:

158 Amir Saemi

[ ]

[ ]

21

,1 0

-2 -1. .( )

,=0 = +1

ˆˆ ( 1) argmin . ( ) ...

ˆ ˆ2. . ( ) . ( ) .

cr

k

c ck

NNk

k k qp p pq p

N N H j r pk kk q qp r p rp r p

m m

m m e

ε

ε

ω−

= =

−

+ = +∑ ∑

∑ ∑

Q d

Q d dRe

(238)

The first term in (238) is constant. By denoting n r p= − , we can further simplify (238) to:

( )

1. .

=1 1

ˆ ( 1) arg min 2. ( ).

arg min 2. ( )

crk

k

k

NNj nk

k qq n

kk

m r n e

R

εε

ε

ε

ε

−−

=

+ = ∑ ∑

=

Re

Re

(239)

where 1

. .

1

( ) ( ).c

kN

j nk kk

nR r n e εε

−−

== ∑ and [ ]

1 *

=1 0 ,

ˆ ˆ( ) ( ) . ( )cr N nN

k k kk q q

m m nq m m m n

r n m m− −

+= + = ∑ ∑ Q d d .

( )kkR ε can be easily computed using the FFT algorithm. When ˆ ( 1)k mε + has been obtained, it

is straightforward, using (225) and (227), to estimate ˆ ( 1)k m +h . We solve (225) by finding the

LMS solution of each term in the sum, this yields to:

1

ˆ ˆˆ( 1) pinv( ( ( 1))). ( )

ˆˆ ˆ ˆ( ( ( 1)). ( ( 1))) . ( ( 1)). ( )

k kq F k q

H H kF k F k F k q

m m m

m m m m

ε

ε ε ε−

+ = +

= + + +

h V d

V V V d (240)

- Algorithm 2 (joint CFO and channel estimation): In the former algorithm the CFO was

estimated independently of the channel parameters since ( )F kεV does not depend on them. In the

new proposed algorithm we estimate the carrier frequency offset using channel parameters

obtained at the former EM iteration steps. We suppose that we used algorithm 1 (FFT-based

search method) for the first steps. Using the FFT based method enables to obtain a rough estimate

of the channel parameters (237) and we found that reusing equation (229) by replacing kq%h by the

estimate ˆ ( )kq mh of k

qh obtained at iteration step m yields to results very close to the theoretical

Cramer-Rao bound. This original method proceeds as follows. We have now:

2

1

ˆ ˆ( ) ( ( ) ( ). ( ) )rN

k kk k q F k q

qQ m m constε ε

== − − +∑ d V h (241)

and developing ( )k kQ ω with dropping the terms irrelevant of kω , this gives the estimation rule:


2

1

2

.

1

ˆ ˆˆ ( 1) argmax ( ( ). ( )) . ( )

ˆ ârgmax . ( ) . ( ). ( ) . ( )

r

k

rk

k

Nk H k

k F k q qq

Nj k H H H k

q k k qq

m m m

e m n m

ε

εε

ε ε

ε

=

−

=

+ = ∑

= ∑%

V h d

h A dΕΕΕΕ

(242)

Then, we use vector , ,k q nΛΛΛΛ of size 1 cN× defined as: , ,ˆ ( ) . ( )k H H

k q n q km n= h AΛΛΛΛ and we denote

, , ( )k q n pΛ as the thp element of this vector. (29) can be further developed as:

21

. . ., ,

1 0

ˆˆ ( 1) argmax ( ). . ( )cr

k k

k

NNj j p k

k k q n qpq p

m e p e mε εεε Λ

−− −

= = + = ∑ ∑ d

% (243)

or:

21

. .

0

ˆ ( 1) argmax ( ).c

k

k

Nj p

kp

m u p e εεε

−−

=+ = ∑ with , ,

1

ˆ( ) ( ). ( )r

kN

j kk q n q

pqu p e p mε Λ−

= = ∑ d

% Denoting

1*

0

( ) ( ). ( )cN p

sp u s u p sχ

− −

== +∑ , the search procedure for kε is then obtained as:

-12 .

=1

ˆ ( 1) argmax ( ).

argmax( ( ))

ck

Nj p

kp

k

m p e π εε χ

ε

− + = ∑

= Ψ

Re (244)

with -1

2 .

=1

( ) ( ).c

kN

j pk

pp e π εω χ − Ψ = ∑

Re . Setting the derivative of ( )kεΨ to zero, we obtain:

12

1

( )Im . ( ). 0k

Kj pk

pk

p p e π εε χε

− −

=

∂ Ψ = =∑ ∂

or, equivalently: 1

1

. ( ) .sin(arg( ( ) 2 . )) 0cN

kp

p p p pχ χ π ε−

=− =∑ . To obtain a close form solution, we

need to use the approximationsin( )x x≈ , this implies that the initial guessed value for kε

obtained by the FFT-based search algorithm is sufficiently close to the true value. In this case, we

eventually obtain:

1

1

12

1

. ( ) .arg( ( ))1

ˆ ( 1)2 . ( )

cN

pk K

p

p p p

mp p

χ χε

π χ

−

=−

=

∑+ =

∑ (245)

ˆ ( 1)k m +h is then obtained in the same way as given in equation (27). The advantage of the EM

algorithm is that its complexity grows linearly with the number of users and the maximization

step can be accomplished in parallel for all Nu users. However, such algorithm exhibits some

known drawbacks. The first one concerns its slow convergence rate since it is inversely related to

160 Amir Saemi

the Fisher information of the complete data space (113). The second one is the introduction of

free variables kβ ’s. Inappropriate values of kβ ’s may not only lead to slower convergence rate

but also may give birth to convergence to local stationary points. In fact, it seems that no accurate

rules for the choice of kβ ’s exist at the moment. For the presented simulation results we found

that kβ constitutes the best trade-off between accuracy and convergence rate.

7.3.2 Using SAGE algorithm

The space-alternating generalized expectation-maximization (SAGE) algorithm was proposed in

[126][127] to overcome the drawbacks of the conventional EM algorithm. The advantage of this

new algorithm is that instead of optimizing over all “complete” data kqd ’s simultaneously in each

iteration, we consider one kqd per iteration, for 1,..., uk N= sequentially, and associate all noise

with the current kqd . The complete SAGE algorithm in the mth

iteration step is given just below.

- E-step (Expectation Step): For k = 1,…,Nu, p = 1,…,Nt and 1,..., rq N= , compute

,, , ,

ˆ ˆ( ) ( ( )). ( )kp q

k k kp q p k p q

m m mµε=b G h (246)

, , ,1

ˆ ˆ ˆ( ) ( ) ( )uNk k j

p q p q k p,q p qj

m m mβ=

= + − ∑

d b y b (247)

,1

ˆ ˆ( ) ( )tNk k

q p qp

m m=

= ∑d d (248)

- M-step (Maximization Step): Compute

,

2

, , ,1 1

ˆ ˆˆ[ ( 1), ( 1)] argmin ( ) ( ).tr

i ii p q

NNi i i i

i q p k p qq p

m m mε µε ε= =

+ + = −∑ ∑

hh d G h

(249)

and for k i≠

ˆ ˆˆ ˆ[ ( 1), ( 1)] [ ( ), ( )]k kk km m m mε ε+ + =h h (250)

Equation (249) can be optimized using Algorithm 1 and Algorithm 2 already mentioned in

section 7.3.1.


7.3.3 Initialization Strategies

EM-based algorithms do not always converge to the global maximum point particularly if there

exists multiple stationary points. To avoid this, one can think of two initialization strategies.

1- Since, for classical OFDM systems, the absolute value of the carrier frequency offset (CFO) is

bounded by half of the OFDM subcarrier spacing, we can assume that kε is a zero-mean

uniformly distributed random variable and so we take ˆ (0) 0kε = . Then, ˆ (0)kqh is obtained by

substituting ˆ (0)kε in equation (27) with q = 1,…,Nr.

2- We use the MLE estimation method proposed by Morelli in [136] for OFDMA systems. By

regarding all other users’ signals as noise, we make a rough guess on ˆ (0)kε and ˆ (0)kqh for

1,..., uk N= . However, we found in our simulations that this method yields to poor results and so

we have only retain strategy 1.

7.3.4 Algorithms complexity

To evaluate the complexity of our algorithms, the number of complex multiplication needed to

implement them could be calculated.

- For the first EM algorithm, we proceed first with a FFT based search method for CFO

estimation. The needed number of multiplication is equal to ( )2( ) 2 logc c rN N N R Rϑ − + , where R

is the length of FFT. The accuracy of CFO estimation in this algorithm is limited to FFT length

and better frequency resolution can be achieved by zero-padding to effectively increase FFT

length.

For the second algorithm within the EM loop, that is joint CFO and channel estimation, the

number of complex multiplication needed at each iteration is equal to 2( )

2c c

r t

N NN N LKϑ

++ .

So we find :

- ( )2.(( ) 2 log )u c c rN N N N R Rϑ − + multiplications per iterations for CFO estimation with FFT.

- 2

).( )

(2

c cc ur t N

N NN N LNϑ

++ multiplications per iterations for CFO estimation with the joint

CFO-channel estimation.

162 Amir Saemi

To calculate channel coefficients we need to calculate pseudoinverse of a matrix cN ×Nt.Ng and to

calculate pseudoinverse of a matrix we use the SVD decomposition of that matrix. The

complexity of calculating SVD of such a matrix in the worst case is equal to

( )( ).min ² ², ²u c ct t gCPN N N N N N Nϑ × × . Therefore, the complexity of calculating h is equal to

: ( )( )).(min ² ², ²u c t t g tCP CPN N N N K N N KN Nϑ + .

- For the SAGE algorithm, the big difference is that we have to update only one user’s parameters

at each iteration. So, the results obtained for EM still holds omitting Nu.

As it can be seen, our algorithm requires a heavy computational burden. However, we achieve an

accurate synchronizer for an OFDMA system which employs general carrier assignment scheme.

7.4 Simulation results

The OFDMA system we used in our simulation is a simplified version of IEEE 802.11a. We

consider an OFDMA system with QPSK modulation and cN = 128 carriers, NCP 18, Nu = 4 users.

Each user has 32 carriers randomly assigned and Nt = 2 transmit antennas. In the simulation runs

we will deal with the case where the BS station is equipped with 2rN = receive antenna. We

consider here MIMO independent frequency selective channels for each link between one

transmit and one receive antenna at the BS. They are modelled as typical GSM urban quasi-static

channels and we use here the models provided in [122][123]. With such kind of channel, it is

easy to show that , ( )kp qh l only takes significant values for 7l ≤ , which means

, 8, , ,kp qL k p q= ∀ ∀ ∀ for our signal model (see equation (215)). For the delays ,

kp qµ we use uniform

random laws with maximum value , max , max 18 8 10k kp q g p qN Lµ = − = − = . For the LDPC channel

encoder, we use a (3,6) regular codes with parity check matrix of 512 × 1024, i.e. with coding

rate 0.5. The packet size is equal to 512 QPSK symbols and the first OFDM word contains pilot

symbols. Random simulated channels are quasi-static ones i.e. they remain constant over the time

duration of a packet. For the generation of CFO we use a random uniform law with maximum

value 2. /128 0.05π ≈ , hence a random value kε is generated from the interval [-0.31,0.31].


The structure of the receiver for each user is similar to those presented in [140] except that we

incorporate the joint CFO-channel algorithm presented in previous section at the front end of the

base-station receiver. Hence, we obtain two iterative structures: the first one is our EM or SAGE

based joint CFO-channel estimation algorithm of section 7.3 and the second one is the joint

MAP-EM LDPC decoder of B.Lu and Wang. Our joint EM based CFO-channel estimation

algorithm iterates ten times: the first five steps are done with the FFT based search algorithm

(Algorithm 1 of section 7.3.1) with a FFT size of 512 and the remaining ones use the joint CFO-

channel estimation procedure (Algorithm 2 of section 7.3.1). After this first stage we enter the

MAP-EM LDPC decoder circuit with the resulting CFO and channel estimates. We use five inner

iterations for the EM MAP demodulator and thirty inner iterations within the LDPC decoder

[140] Five complete iterations in the MAP-EM LDPC decoder structure are made before we

compute the BER. The performance of our synchronization algorithms is first evaluated with the

mean square error (MSE) of the estimated parameters. Without loosing any generality, we will

consider user 1 as the user of interest.. Then, in order to quantify the efficiency of the proposed

algorithms, we can use the mean CRB’s of 1f∆ and 1h . In the following simulation result we

consider a situation in which 4uN = users want to enter the system simultaneously.

At first we consider the case where the mean power of each user is the same, equal to 1/ tN . The

MSE is averaged for each SNR over 1000 packet Monte-Carlo runs. For the initialization strategy

of the EM algorithms, we use the first one described in section 7.3.3 . The simulation results are

presented on Figure 53 for Nr = 2 receive antennas. We add simulation results for comparison

purpose from the simple algorithm of Morelli presented in [136]. EM and SAGE algorithms

exhibit the same performances and they work very close to the mean Cramer Rao Bound (mean

CRB) 1( )CRB ε : the difference between SAGE or EM and the mean CRB is less than 0.5 dB.

Morelli’s algorithm [136] leads to poorer performance and exhibits a MMSE floor at high SNR’s

due to the fact that it was originally devoted to mono-user systems.

We consider a near-far effect on Figure 53 with Nr = 2 receive antennas when user 1’s average

signal power is 3 dB lower than the other users. It is clear in this case that only the EM based

methods can lead to satisfactory results. Morelli’s algorithm can’t accommodate the strong

interference power from the other users and exhibits no improvement by increasing the SNR. EM

based algorithms perform within 0.7 dB from the mean CRB: 1( )CRB ε .

164 Amir Saemi

Figure 53:CFO estimation performance with equal power assignment

Nr = 2, two receive antennas

Figure 54: CFO estimation performance in a near-far situation


Nr = 2, two receive antennas

To illustrate the performances of the proposed EM algorithms in the case of channel estimation,

we give the MSE performances in the context of the near-far effect. The results are plotted on

Figure 55. One can remark that the two proposed algorithms perform extremely close to each

other. They work within 1 dB from the mean CRB 1( )CRB h .

Figure 56 examines the convergence behaviour of the proposed iterative algorithms in the near-

far context. We define a convergence threshold for the square error of the CFO equal to 10-3. That

means all the packets having a CFO square error superior to 10-3 are considered rejected. We

compute the ratio of the number of correct received packets over the total number of transmitted

packets, this gives the success rate illustrated on Figure 56. One can remark on Figure 56 a better

success rate for EM algorithm compared to SAGE. That means that despite a slower

convergence, EM is less likely to encounter data blocks that cause divergence. However, the

difference between the two curves is always inferior to ten percent.

The similar behaviour of EM and SAGE is confirmed by the study of the BER on Figure 57. The

performances exhibited by the EM algorithm are slightly better than those of the SAGE algorithm

(the difference is 0.3 dB at BER = 10-4). On the other hand, the simple Morelli’s algorithm [136]

exhibits an error floor in this case. When compared to EM-SAGE algorithms the loss is

approximately equal to 2 dB at BER = 10-3.

166 Amir Saemi

Figure 55: Channel estimation performance in a near-far situation

Figure 56: Success rate for the transmitted packets for EM and SAGE algorithms

near-far situation (Decion Directed mode), Nr = 2, two receive antennas


Figure 57:BER performance comparison between synchronisation algorithms

near-far situation (DD mode), Nr = 2, two receive antennas

168 Amir Saemi


8. CONCLUSION

The problem of synchronization in MIMO-OFDM systems is addressed in this dissertation. Apart

from introduction and conclusion, this manuscript is composed of six main chapters.

At first, in chapter 2 the problem of channel estimation was discussed. Since the channel

estimation is not in the center of attention of this dissertation, this chapter is, in fact, a literature

survey of works dealing with channel estimation methods, especially data aided channel

estimation methods. Therefore, some good data aided channel estimation methods were presented

and within the data aided methods two different cases were distinguished, one was the case where

we use a training sequence in the beginning of the data packet and the other was the case where

we insert known pilots inside the data packet. Chapter 2 finishes with a quick look at blind and

iterative channel estimation methods.

Subsequently, chapter 3 deals with the problem of the frequency synchronization in MIMO-

OFDM systems. The aim of this chapter is to estimate the carrier frequency offset induced either

by a small difference in frequency of transmitter and receiver oscillators or by the Doppler effect.

In this chapter three of the best existing methods for frequency synchronization, which were

called FFT method, hopping pilots method and autocorrelation method, were presented. Along

with these three methods another new method (so called iterative method) developed by us was

8Chapter

170 Amir Saemi

presented. This method is, in fact, a part of the joint algorithm presented in chapter 5. Hence

chapter 3 only attempts to outline the section of frequency estimation of the joint algorithm.

Then, we compared these four methods and concluded that the autocorrelation method and

iterative method outperform two other algorithms. Iterative method shows a slightly better

performance with higher complexity. It has to be mentioned that since the iterative method is a

part of joint method presented in chapter 5 the complete simulation of this method as well as

other methods along with the simulation is presented in chapter 5.

Chapter 4 addresses the problem of time synchronization. Since MIMO-OFDM time

synchronization approaches are influenced by non MIMO−OFDM time synchronization methods,

Chapter 4 starts with a review of non MIMO−OFDM time synchronization methods designed for

either MIMO non-OFDM or non-MIMO OFDM systems. Then, the problem of time

synchronization in MIMO-OFDM systems was discussed. The problem of time synchronization

is divided into frame synchronization and symbol timing and each issue was separately

addressed. Concerning frame synchronization, the conventional method of autocorrelation was

presented first and then we proposed some modifications to make this algorithm more precise.

The results are presented under the title of advanced autocorrelation method. The advanced

autocorrelation method was originally designed for flat fading channels however it presents good

results for frequency selective channels. Concerning symbol timing, some of well known

methods were presented. In addition, a new symbol timing method developed by us was

discussed.

Chapter 5 is about a new joint time-frequency synchronization and channel estimation method for

MIMO-OFDM systems. In this chapter we developed an ML criterion for MIMO-OFDM

synchronization. Maximizing this criterion leads to find the exact packet arrival time as well as

carrier frequency offset and channel coefficients. Since, the estimation of frequency offset by

numerical search is almost impossible we have proposed a two-stage algorithm to find

analytically frequency offset. At the first stage we do frequency synchronization by using an FFT

algorithm. This rough estimation permits us to compensate the main part of frequency error and

so at this level time synchronization can be done. Then, at the second stage, we propose an

iterative method to compensate the residual frequency error. Chapter 5 finishes with presenting

the result of this algorithm and comparing it with other algorithms. It is concluded at the end of


this chapter that the best synchronizer would be either the joint algorithm presented in this

chapter or a mixed synchronizer that use autocorrealtion method for frequency synchronization

and frame synchronization and reduced complexity method (presented in chapter 4) for symbol

timing. The complexity of the latter is less while the performance of the former is slightly better.

Chapter 6 attempts to present the concept of code-aided algorithm. Actually, by using code-aided

algorithm data portion of the frame can be used for synchronization and that leads to improve the

spectral efficacy as well as the possibility of finding the possible changes in the estimation

parameters. In this chapter we use soft information provided from the decoding process, in order

to fully exploit the code properties during estimation. EM algorithm as a tool toward code aided

algorithm is described in this chapter and then we have explained how one can use EM algorithm

for MIMO-OFDM synchronization. The results are depicted at the end of the chapter.

MIMO OFDM systems have given birth to OFDMA systems. In the case of OFDMA, the set of

available carriers is divided into groups called subchannels and each user is assigned with one or

multiple subchannels. Hence, we dedicated the perspective chapter to some suggestion about

MIMO OFMA synchronization. Actually we proposed a synchronization procedure based on the

EM algorithm. Here, we used EM-based approach to decompose a computationally intensive

multi-dimensional optimization problem into separate smaller ML optimization problems. The

result of this chapter shows acceptable performance. However, we have supposed that the

different transmit antennas of each user send their training data sequentially in the network i.e.

the other transmit antennas are switched off. This implies a quasi-synchronous system in a micro-

cell environment for example. Also, the correction of one’s frequency and timing cannot be

accomplished at the Base Station. Hence, this problem can be still considered as an open problem

which demands further works.

172 Amir Saemi


REFERENCES

Author’s publications

[1] Amir Saemi, Jean-Pierre Cances, Vahid Meghdadi, “Synchronization Algorithms for MIMO

OFDMA Systems”, Accepted by IEEE transaction on Wireless Communications March

2007.

[2] Amir Saemi, Vahid Meghdadi, Jean-Pierre Cances, Mohammad Reza Zahabi, “Joint ML

time-frequency synchronization and channel estimation algorithm for MIMO-FDM systems”,

invited by IET Proceeding of Circuit, Devices and Systems.

[3] Amir Saemi, vahid Meghdadi, Jean-Pierre Cances, and Mohammad Reza Zahabi, “Iterative

time-frequency synchronizer for MIMO-OFDM systems”, submitted in EURASIP Journal on

Wireless Communications and Networking (EURASIP JWCN).

[4] Amir Saemi, Vahid Meghdadi, Jean-Pierre Cances, M.Reza Zahabi, Jean-Michel Dumas,

“ML Time-Frequency synchronization for MIMO-OFDM Systems in Unknown Frequency

Selective fading channels.”, PIMRC 2006.

[5] Amir Saemi, Vahid Meghdadi, Jean-Pierre Cances, Mohammad Reza Zahabi, Jean-Michel

Dumas,”ML Symbol Synchronization For General MIMO-OFDM Systems In Unknown

Frequency-Selective Fading Channels”, EUSIPCO 2006.

[6] Amir Saemi, Vahid Meghdadi, Jean-Pierre Cances, M.Reza Zahabi, Jean-Michel Dumas,

“ML Time Synchronization Algorithm Joint with Channel Estimation for MIMO-OFDM

Systems in Frequency Selective Fading Channel” CSNDSP 2006, ISBN: 960-89282-0-6.

[7] V. Meghdadi, A. Saemi, J.P. Cances, M.J. Syed, G. Ferre; J.M. Dumas, “Improving frequency

synchronization by means of new correlation criteria for fine time synchronization in MIMO

system”, ELMAR, 2005. 47th International Symposium, pp 283-286.

[8] A. Saemi, V. Meghdadi, JP. Cances, et al. “Fine Timing and Frequency Synchronization for

MIMO System,“ Proc. of IST Mobile and Wireless Communications Summit, 2005.

174 Amir Saemi

[9] Amir Saemi, Vahid Meghdadi, Jean-Pierre Cances, “MIMO-OFDM iterative time-frequency

synchronization”, will be published in Proc PIMRC 2007, Sept. 2007.

[10] A. Saemi, G. Ferré, J. P. Cances and V. Meghdadi, “Synchronization algorithms for MIMO-

OFDMA systems”, will be published in Proc PIMRC 2007, Sept. 2007.

[11] M.R. Zahabi, V. Meghdadi, J.P. Cances, A. Saemi, J.M. Dumas, B. Barelaud, “Analog

CMOS Kernel for ML Decoding of Convolutional Codes” Proc. ICEE 2006.

[12] M. R. Zahabi, V. Meghdadi, J.P. Cances and A. Saemi, “A Mixed-signal matched-filter

design and simulation”, will be published in Proc of the International Conference on

Digital Signal Processing (DSP), July 2007.

[13] M. R. Zahabi, V. Meghdadi, J.P. Cances and A. Saemi, “Mixed-signal realization of

matched-filters for high rate communication systems”, will be published in Proc. PIMRC

2007, Sept. 2007.

[14] Ferre, G.; Cances, J.P.; Meghdadi, V.; Dumas, J.M.; Saemi, A.; “Layered Space-Time

Coding for 3n Transmit Antenna Communication Systems”, Proc. PIMRC 2006.

Other references

[15] Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)

Specifications: High-Speed Physical Layer in the 5 GHz Band, IEEE Standard 802.11a-

1999.

[16] Local and Metropolitan Area Networks—Part 16, Air Interface for Fixed Broadband

Wireless Access Systems, IEEE Standard IEEE 802.16a.

[17] L. J. Cimini, Jr., “Analysis and simulation of a digital mobile channel using orthogonal

frequency division multiplexing,” IEEE Trans. Commun., vol. COM-33, pp. 665–675, July

1985.

[18] S. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J.

Select. Areas Commun., vol. 16, pp. 1451–1458, Oct. 1998.

[19] V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space–time block codes from orthogonal

designs,” IEEE Trans. Inform. Theory, vol. 45, pp. 1456–1467, July 1999.


[20] V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space–time codes for high data rate wireless

communication: Performance criterion and code construction,” IEEE Trans. Inform.

Theory, vol. 44, pp. 744–765, Mar. 1998.

[21] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Valenzuela, “V-Blast: An

architecture for realizing very high data rates over the rich-scattering channel,” in Proc. Int.

Symp. Signals, Systems and Electronics (ISSE 1998), pp. 295–300.

[22] Fredrik Tufvesson, Mike Faulkner and Ove Edfors, "Time and frequency synchronization

for OFDM using PN-sequence preambles", Proceedings of IEEE Vehicular Technology

Conference, Amsterdam, The Netherlands, September 19-22, 1999, pp. 2203-2207

[23] M. Schmidl and D. C. Cox, “Robust frequency and timing synchronization for OFDM,”

IEEE Trans. Commun., vol. 45, pp. 1613-1621, Dec. 1997.

[24] P.Moose, “A technique for orthogonal frequency division multiplexing frequency offset

correction,” IEEE Trans. Commun., vol. 42, pp. 2908-2914, Oct. 1994.

[25] S. H. Müller-Weinfurtner, “On the optimality of metrics for coarse frame synchronization in

OFDM: A comparison,” in Proc. PIMRC , Sept. 1998, pp. 533-537.

[26] J.J. van de Beek, M. Sandell, and P.O. Borjesson,”Timing and frequency synchronization in

OFDM system using the cyclic prefix”, In Proceedings of International Symmposium on

Synchronization, pp. 16-19, Essen,Germany, December 1995.

[27] E.G. Larsson, G. Liu, J. Li, and G. Giannakis, “Joint symbol timing and channel estimation

for OFDM based WLANs,'' IEEE Communications Letters, Vol. 5, No. 8, pp. 325-327,

August 2001.

[28] Yik-Chung Wu, Kun-Wah Yip, Tung-Sang Ng and E. Serpedin, “ML Symbol

Synchronization for OFDM-based WLANs in Unknown Frequency-Selective Fading

Channels,” Proceedings of the 38th Asilomar Conference on Signals, Systems and

Computers, pp. 339-344, Nov. 7-10, 2004.

[29] H. Minn, M. Zeng, and V. K. Bhargava, “On timing offset estimation for OFDM systems,”

IEEE Commun. Lett., vol. 4, pp. 242-244, July 2000.

[30] N. Lashkarian and S. Kiaei, “Class of cyclic-based estimators for frequency-offset

estimation of OFDM systems,” IEEE Trans. Commun., vol. 48, pp. 2139-2149, Dec. 2000.

176 Amir Saemi

[31] A. J. Coulson, “Maximum likelihood synchronization for OFDM using a pilot symbol:

Algorithm,” IEEE J. Select. Areas Commun., vol. 19, pp. 2486-2494, Dec. 2001.

[32] A. J. Coulson, “Maximum likelihood synchronization for OFDM using a pilot symbol:

Analysis,” IEEE J. Select. Areas Commun., vol. 19, pp. 2495-2503, Dec. 2001.

[33] Speth, M. Classen, F. Meyr, H. “Frame synchronization of OFDM systems in frequency

selective fadingchannels”, Vehicular Technology Conference, 1997 IEEE 47th,Vol 3,

pp.1807-1811, May 1997

[34] Speth M, Fechtel S A, et al. “Optimum receiver design for OFDM-based broadband

transmission .part II. A case study.” IEEE Trans. Communication, vol. 49(4): pp 571-578,

Apr. 2001

[35] T. Keller and L. Hanzo, “Orthogonal frequency division multiplex synchronization

techniques for wireless local area networks,” in Proc. PIMRC Taipei, Taiwan R.O.C., 1996,

pp. 963-967.

[36] Pierre R. Chevillat, Dietrich Maiwald, and Gottfried Ungerboeck, “Rapid Training of a

Voiceband Data–Modem Receiver Employing an Equalizer with Fractional–T Spaced

Coefficients,” IEEE Trans. on Commun., vol. 35, no. 9, pp. 869–876, 1987

[37] K. Shi and E. Serpedin, “Robust Coarse Frame and Carrier Synchronization for OFDM

Systems: A New Metric and Performance Evaluation'' IEEE Trans. on Wireless

Communications, vol. 3, no. 3, pp. 1271-1284, July 2004.

[38] R. van Nee and R. Prasard, OFDM for Wireless Multimedia Communications, Norwell,

MA: Artech House, 2000.

[39] Nandula, S. Giridhar, K, “Robust timing synchronization for OFDM based wireless LAN

system”, TENCON 2003. Conference on Convergent Technologies for Asia-Pacific Region,

Vol 4,pp. 1558- 1561, Oct. 2003

[40] Wang, K., Faulkner, M., Singh, J. and Tolochko, I., “Timing Synchronization for 802.11a

WLANS under Multipath Channels”, Australian Telecommunications Networks &

Applications Conference, Melbourne, Australia, 8 - 10 December, 2003.


[41] Kun-Wah Yip, Yik-Chung Wu and Tung-Sang Ng, “Timing-synchronization analysis for

IEEE 802.11a wireless LANs in frequency-nonselective Rician fading environments,” IEEE

Transactions on Wireless Communications, vol. 3, no. 2, pp.387-394, Mar. 2004.

[42] Yik-Chung Wu, Kun-Wah Yip, Tung-Sang Ng and E. Serpedin, “Maximum-Likelihood

Symbol Synchronization for IEEE 802.11a WLANs on Unknown Frequency-Selective

Fading Channels,'' IEEE Trans. on Wireless Communications, (submitted July 2003, revised

Jan. 2004, June 2004, accepted Aug. 2004).

[43] M. Speth, D. Daecke and H. Meyr, “Minimum overhead burst synchronization for OFDM

based broadband transmission,” Proc. Globecom 98, pp. 3227-3232, 1998

[44] H. Sampath, S. Talwar, J. Tellado, V. Erceg, and A. Paulraj, “A fourth-generation MIMO-

OFDM: Broadband wireless system: Design, performance, and field trial results,” IEEE

Commun. Mag., vol. 40, no. 9, pp. 143-149, Sept. 2002.

[45] A. N. Mody and G. L. Stüber, “Synchronization for MIMO OFDM systems,” in Proc. IEEE

Global Commun. Conf., vol. 1, Nov. 2001, pp. 509-513.

[46] Suehiro N. and Hatori M., “Modulatable Orthogonal Sequences and their Application to

SSMA Systems”, Trans. on Inform. Theory, 34, 93–100, 1998.

[47] A. van Zelst and T. C. W. Schenk, “Implementation of a MIMO OFDM- based Wireless

LAN System,” IEEE Trans. on Signal Processing, vol. 52, no. 2, pp. 483–494, Feb. 2004.

[48] N.Duc Long and H. Park ,” Joint Fine Time Synchronization and Channel Estimation for

MIM0-OFDM WLAN”, IEEE Intelligent Signal Processing and Communication Systems

Conference (ISPACS 2004).

[49] En Zhou, Xing Zhang, Hui Zhao and Wenbo Wang, “Synchronization algorithms for

MIMO OFDM systems”, Wireless Communications and Networking Conference, IEEE,

Vol. 1, pp. 18- 22, March 2005.

[50] Ayman F. Naguib, Vahid Tarokh, Nambirajan Seshadri, and A. Robert Calderbank, “A

space-time coding modem for high-data-rate wireless communications,” IEEE J. Selected

Areas Commun., vol. 16, no. 8, pp. 1459–1478, Oct. 1998.

178 Amir Saemi

[51] Yik-Chung Wu, S. C. Chan and E. Serpedin, “Symbol-Timing Estimation in Space-Time

Coding Systems based on Orthogonal Training Sequences," IEEE Trans. on Wireless

Communications, vol. 4, no. 2, pp. 603-613, Mar. 2005.

[52] M. Oerder and H. Meyr, “Digital filter and square timing recovery”, IEEE Trans. on

Comm., vol.36, pp. 605-612, May 1988

[53] Yik-Chung Wu and Shing-Chow Chan, “On the Symbol Timing Recovery in Space-Time

Coding Systems,” Proceedings of the IEEE Wireless Communications and Networking

Conference (WCNC) 2003, pp.420-424, Mar. 2003.

[54] Yik-Chung Wu and E. Serpedin, “Symbol Timing Estimation in MIMO Correlated Flat-

Fading Channels,”" Wireless Communications and Mobile Computing (WCMC) Journal ,

Special Issue on "Multiple-Input Multiple-Output (MIMO) Communications", Wiley, vol.

4, Issue 7, pp. 773-790, Nov. 2004.

[55] Schumacher L, Kermoal JP, Frederiksen F, Pedersen KI, Algrans A, Mogensen PE. MIMO

channel characterisation. Deliverable D2 V1.1 of IST-1999-11729 METRA Project, pp.1–

57, February 2001. Available online: http://www.ist-metra.org

[56] Yik-Chung Wu and E. Serpedin, “Training Sequences Design for Symbol Timing

Estimation in MIMO Correlated Fading Channels,” Proceedings of the IEEE Globecom

2004, vol. 1, pp. 81-85, Nov. 2004.

[57] Yik-Chung Wu and E. Serpedin, “Low-complexity feedforward symbol timing estimator

using Conditional Maximum Likelihood principle,” IEEE Communications Letters, vol. 8,

no. 3, pp.168-170, Mar. 2004

[58] Y. Liu, T. F. Wong, and A. Pandharipande, "Timing Estimation in Multiple-Antenna

Systems over Rayleigh Flat-Fading Channels," IEEE Transactions on Signal Processing,

June 2004. Accepted for publication

[59] S.N. Diggavi, N. Al-Dhahir et al “Differential Space-Time Transmission for Frequency

Selective Channel” Proc of 36th Conf. on Info. Sciences and Systems;, pp. 859-862,

Princeton Univ., Mar 20-22, 2002.


[60] Sumei Sun Wiemer, I. Ho, C.K. Tjhung, T.T., “Training sequence assisted channel

estimation for MIMO OFDM”, Wireless Communications and Networking, 2003. WCNC

2003, IEEE Vol. 1, pp. 38- 43, March 2003

[61] Changho Suh, Chan-Soo Hwang, Hokyu Choi, "Preamble design for channel estimation in

MIMO-OFDM systems", GLOBECOM 2003 - IEEE Global Telecommunications

Conference, vol. 22, no. 1, Dec 2003 pp. 317-321

[62] Y. (Geoffrey) Li, ``Simplified channel estimation for OFDM systems with multiple transmit

antennas,'' IEEE Transactions on Wireless Communications, vol. 1, pp. 67-75, January

2002.

[63] Hassibi, B.; Hochwald, B.M.; ”Hassibi “How much training is needed in multiple-antenna

wireless links?” Information Theory, IEEE Transactions on Volume 49, Issue 4,

Page(s):951 – 963, April 2003

[64] Xiaoli Ma; Liuqing Yang; Giannakis, G.B.; “Optimal training for MIMO frequency-

selective fading channels”, Wireless Communications, IEEE Transactions on Volume 4,

Issue 2, pp. 453 – 466, March 2005

[65] X. Deng and A.M. Haimovich, “On Pilot Symbol Aided Channel Estimation for Time

Varying Rayleigh Fading Channels,” in Proc. the 38th Annual Conference on Information

Sciences and Systems (CISS'04), Princeton, New Jersey, Mar. 2004.

[66] A.petropulu, R.Zhang and R. Lin “Blind OFDM channel estimation through simple linear

precoding” IEEE Transaction on Wireless Communication, Vol.3, No.2, pp.647-655, Mar

2004

[67] Jinho Choi “Equalization and semi-blind channel estimation for space-time block coded

signals over a frequency-selective fading channel”, Signal Processing, IEEE Transactions

on, Volume 52, Issue 3,Page(s):774 - 785, March 2004

[68] C. Budianu and L. Tong "Channel Estimation for Space-Time Orthogonal Block Codes,” in

IEEE Transactions on Signal Processing, vol. 50 , no. 10 , pp. 2515 - 2528, Oct. 2002.

[69] Xiaohong Meng and J.K. Tugnait, ``MIMO channel estimation using superimposed

training,'' in Proc. 2004 IEEE International Conf. on Communications, Paris, France, June

20-24, 2004.

180 Amir Saemi

[70] M. Loncar, R. Müller, J. Wehinger, C. Mecklenbräuker, T. Abe, ”Iterative Channel

Estimation and Data Detection in Frequency Selective Fading MIMO Channels “,in

European Transactions on Telecommunications (ETT), 09-2004, pp. 459-470

[71] A. Grant, “Joint decoding and channel estimation for space-time codes,”.

IEEE Vehicular Technology Conference, pp. 416-420, 2000.

[72] X. Deng, A.M. Haimovich, and J. Garcia-Frias, “Decision Directed Iterative Channel

Estimation for MIMO Systems” in Proc. IEEE International Conference on Commun. 2003

ICC’03, vol:4, pp. 2326-2329.

[73] Zhu Haidong, Farhang-Boroujeny B, Schlegel C. “Pilot embedding for joint channel

estimation and data detection in MIMO communication systems.” IEEE Communications

Letters, 7(1): 30-32, 2003

[74] C. Fragouli, N. Al-Dhahir, and W. Turin “Training-Based Channel Estimation for Multiple

Antenna Broadband Transmissions” , IEEE Transactions on Wireless Communications,

March 2003

[75] H. Bölcskei, R. W. Heath Jr., and A. J. Paulraj, “Blind channel identification and

equalization in OFDM-based multi-antenna systems,” IEEE Trans. Signal Process., vol. 50,

no. 1, pp. 96–109, Jan. 2002.

[76] Z. Liu, G. B. Giannakis, S. Barbarossa, and A. Scaglione, “Transmit-antennae space-time

block coding for generalized OFDM in the presence of unknown multipath,” IEEE J. Select.

Areas Commun., vol. 19, no. 7, pp. 1352–1364, Jul. 2001.

[77] S. Zhou, B. Muquet, and G. B. Giannakis, “Subspace-based (semi-) blind channel

estimation for block precoded space-time OFDM,” IEEE Trans. Signal Process., vol. 50,

pp. 1215–1228, May 2002.

[78] S. Ohno and G. B. Giannakis, “Optimal training and redundant precoding for block

transmissions with application to wireless OFDM,” IEEE Trans. Commun., vol. 50, no. 12,

pp. 2113–2123, Dec. 2002.

[79] IEEE 802.11a Standard, ISO/IEC 8802-11:1999/Amd 1:2000(E).

[80] B. M. Popović, “Synthesis of power efficient multitone signals with flat amplitude

spectrum,” IEEE Trans. on Commun., vol.39, pp.1031-1033, 1991


[81] Y. (G.) Li, N. Seshadri, and S. Ariyavisitakul, “Channel estimation for OFDM systems with

transmitter diversity in mobile wireless channels,” IEEE J. Select. Areas Commun., vol. 17,

pp. 461–471, Mar. 1999.

[82] P. Spasojevic and C.Georghiades, “Complementary sequence for ISI channel estimation,”

IEEE Trans. Inform. Theory, vol. 47, pp. 1145-1152, Mar. 2001.

[83] G. Caire and U. Mitra, “Training sequence design for adaptive equalization of multi-user

systems,” in Proc. 32nd Asilomar Conf., vol. 2, 1998, pp. 1479-1483.

[84] W. H.Mow, Sequence Design for Spread Spectrum Hong Kong: The Chinese University

Press: Chinese Univ. Hong Kong, 1995.

[85] D. C. Chu, “Polyphase codes with good correlation properties,” IEEE Trans. Inform.

Theory, vol. IT–18, pp. 531-532, July 1972.

[86] W. H. Mow, “A new unified construction of perfect root-of-unity sequences,” in Proc.

Spread-Spectrum Techniques and Applications , vol. 3, 1996, pp. 955-959.

[87] S. N. Crozier, D. D.Falconer, and S. A.Mahmoud, “Least sum of squared errors (LSSE)

channel estimation,” in Proc. IEEE, pt. F, vol. 138, no. 4, Aug. 1902, pp. 371-378.

[88] C. Fragouli, N. Al-Dhahir, and W. Turin, “Finite-alphabet constant- amplitude training

sequence for multiple-antenna broadband transmissions,” in Proc. IEEE Int. Conf.

Commun., vol. 1, New York,NY, Apr. 28–May 1 2002, pp. 6–10.

[89] C. Fragouli, N. Al-Dhahir, “Reduced-complexity training schemes for multiple-antenna

broadband transmissions,” in Proc. Wireless Communications Networking Conf., vol. 1,

Mar. 17–21, 2002, pp. 78–83.

[90] I. Barhumi, G. Leus, and M. Moonen, “Optimal training sequences for channel estimation

in MIMO OFDM systems in mobile wireless channels,” in Proc. Int. Zurich Seminar on

Access, Transmission, Networking of Broadband Communications. Zurich, Switzerland,

Feb. 19–21, 2002, pp. 44-1–44-6.

[91] T.-L. Tung, K. Yao, and R. E. Hudson, “Channel estimation and adaptive power allocation

for performance and capacity improvement of multiple-antenna OFDM systems,” in Proc.

3rd IEEE Workshop Signal Processing Advances in Wireless Communications, Taoyuan,

Taiwan, R.O.C., Mar. 20–23, 2001, pp. 82–85.

182 Amir Saemi

[92] Z. Wang, X. Ma, and G. B. Giannakis, “Optimality of single-carrier zero-padded block

transmissions,” in Proc. Wireless Communications Networking Conf., vol. 2, Orlando, FL,

Mar. 17–21, 2002, pp. 660–664.

[93] B. Muquet, M. de Courville, and P. Duhamel, “Subspace-based blind and semi-blind

channel estimation for OFDM systems,” IEEE Trans. Signal Processing, vol. 50, pp. 1699-

1712, July 2002.

[94] E. Moulines, P. Duhamel, J.-F. Cardoso, and S. Mayrague, “Subspace methods for the blind

identification of multichannel FIR filters,” IEEE Trans. Signal Processing, vol. 43, pp.

516–525, Feb. 1995.

[95] A. L. Swindlehurst and G. Leus, “Blind and semi-blind equalization for generalized space-

time block codes,” IEEE Trans. Signal Processing, vol. 50, pp. 2489–2498, Oct. 2002.

[96] V. Buchoux, O. Cappe, E. Moulines, and A. Gorokhov, “On the performance of semi-blind

subspace-based channel estimation,” IEEE Trans.Signal Processing, vol. 48, pp. 1750–

1759, June 2000.

[97] Li Q, Georghiades N, Wang X. An iterative receiver for turbo-coded pilot-assisted

modulation in fading channels. IEEE Communications Letters 2001; 5(4):145–147.

[98] Valenti M, Woerner B. Iterative channel estimation and decoding of pilot symbol assisted

turbo codes over flat-fading channels. IEEE Journal on Selected Areas in Communications

2001; 19(9):1697–1705.

[99] B. Farhang-Boroujeny, “Pilot-based channel identification: A proposal for semi-blind

identification of communication channels,” Electronic Letter. vol. 31, pp. 1044–1046, June

1995.

[100] F. Chin, B. Farhang-Boroujeny, and C. K. Ho, “Added pilot semi-blind channel estimation

scheme for OFDM in fading channels,” in Proc. IEEE Globecom’01, vol. 5, San Antonio,

TX, Nov. 25–29, 2001, pp. 3075–3079.

[101] Speth, M., Fechtel, S. A., Fock, G., Meyr, H.: “Optimum Receiver Design for Wireless

Broad-Band Systems Using OFDM - Part I” , IEEE Transactions on Communications, Vol.

47, No. 11, November 1999


[102] S. A. Fechtel, “OFDM carrier and sampling frequency synchronization and its performance

on stationary and mobile channels,” IEEE Trans. Consum. Electron., vol. 46, pp. 438–441,

Aug. 2000.

[103] K. K. Dong, H. D. Sang, C. B. Hong, C. J. Hyung, and K. B. Ki, “A new joint algorithm of

symbol timing recovery and sampling clock adjustment for OFDM systems,” IEEE Trans.

Consum. Electron., vol. 44, pp. 1142–1149, Aug. 1998.

[104] M. J. F.-G. Garcia and J. M. Paez-Borrallo, “Tracking of time misalignments for OFDM

systems in multipath fading channels,” IEEE Trans. Consum. Electron., vol. 48, pp. 982–

989, Nov. 2002.

[105] M. Luise and R. Reggiannini, “Carrier frequency recovery in all-digital modems for burst-

mode transmissions,” IEEE Trans. Commun., vol. 43, pp. 1169–1178, Feb.-Apr. 1995.

[106] K. Shi, E. Serpedin et P. Ciblat, “Decision-Directed Fine synchronization in OFDM

systems”, IEEE Transactions on Communications, vol. 53, no. 3, pp. 408-412, Mars 2005.

[107] Oberli, C.; Daneshrad, B., “Maximum likelihood tracking algorithms for MIMO-OFDM”

Communications, 2004 IEEE International Conference on, Volume 4, 20-24, Page(s):2468

- 2472 June 2004

[108] G. Santella, “Frequency and symbol synchronization system of OFDM signals: Architecture

and simulation results”, IEEE Trans. on Vehicular Technology, vol. 49, no. 1, pp. 254-275,

Jan 2000.

[109] H. Liu and U. Tureli, “ A high efficiency carrier estimator for OFDM communications”,

IEEE Communication Letters, vol. 2, no. 4, pp. 104-106, April 1998.

[110] J.-J. van de Beek, M. Sandell, and P. O. Börjesson, “ML estimation of time and frequency

offset in OFDM systems,” IEEE Trans. Signal Process., vol. 45, pp. 1800–1805, Jul. 1997.

[111] T.C.W. Schenk and A. van Zelst, "Frequency Synchronization for MIMO OFDM Wireless

LAN Systems", Proc. IEEE Vehicular Technology Conference Fall 2003 (VTC Fall 2003),

Orlando (FL), 6-9 October 2003, paper 05D-03.

[112] R.L. Frank and S.A. Zadoff, “Phase Shift Pulse Codes With Good Periodic Correlation

Properties”, IRE Trans. on Information Theory, vol. IT-8, pp. 381-382. 1962.

184 Amir Saemi

[113] D. C. Rife and R. R. Boorstyn, "Single-Tone Parameter Estimation From Discrete-Time

Observations", IEEE Trans. Inform. Thoery, vol. IT-20, pp. 591-598, Sept. 1974.

[114] X. Ma, M.-K. Oh, G. B. Giannakis, and D.-J. Park, “Hopping Pilots for Estimation of

Frequency-Offsets and Multi-Antenna Channels in MIMO-OFDM,” IEEE Transactions on

Communications, vol. 53, no. 1, pp. 162-172, January 2005.

[115] S. Barbarossa, M. Pompili, and G. B. Giannakis, “Channel-Independent Synchronization of

Orthogonal Frequency Division Multiple Access Systems,” IEEE Journal on Selected

Areas in Communications, vol. 20, no. 2, pp. 474-486, February 2002.

[116] H. Bölcskei, “Blind estimation of symbol timing and carrier frequency offset in wireless

OFDM systems,” IEEE Trans. Commun., vol. 49, pp.988–999, Jun. 2001.

[117] Y. Yao, and G. B. Giannakis, “Blind Carrier-Frequency Offset Estimation of SISO, MIMO,

and Multi-User OFDM,'” IEEE Transactions on Communications, vol. 53, no. 1, pp. 173-

183, January 2005.

[118] Y. Sun, Z. Xiong and X. Wang, “EM-based iterative receiver design with carrier frequency

offset estimation for OFDM-coded MIMO systems,” IEEE Trans. Comm., to appear in Apr.

2005

[119] B. Lu, X. D. Wang, and Y. (Geoffrey) Li, `Ìterative receivers for space-time block coded

OFDM systems in dispersive fading channels,'' IEEE Transactions on Wireless

Communications, vol. 1, pp. 213-225, April 2002.

[120] Henk Wymeersch, Frederik Simoens and Marc Moeneclaey "Code-aided joint channel

estimation and frame synchronization for MIMO systems", Workshop on Signal Processing

Advances in Wireless Communications (SPAWC'04), Lisbon, Portugal, July 2004.

[121] Tim C.W. Schenk, Maurice M. de Laat, Peter F.M. Smulders and Erik R. Fledderus,

“Symbol timing for multiple antenna OFDM systems”, in: Vehicular Technology

Conference, 2006. VTC 2006-Spring.

[122] M. Morelli and U. Mengali, “Carrier-frequency estimation for transmissions over selective

channels,” IEEE trans. Commun., vol. 48, pp.1580-1589, Sept 2000

[123] P. Stoica, O. Besson, “Training sequence design for frequency offset and frequency-

selective channel estimation” IEEE trans. Commun. Vol 51, pp:1910 – 1917, 2003


[124] J. A. Fessler and A. O. Hero, “Space-alternating generalized expectation- maximization

algorithm,” IEEE Trans. Signal Processing, vol. 42, pp. 2664–2677, Oct. 1994.

[125] T. Moon, “The expectation-maximization algorithm”, IEEE Signal Processing Mag., vol.

13, n°6, pp. 47-60, 1996.

[126] M. Feder and E. Weinstein, “Parameter estimation of superimposed signals using the EM

algorithm”, IEEE Trans. ASSP, vol. 36, n°4, April 1998.

[127] C. Georghiades and J. C. Han, “Sequence estimation in the presence of random parameters

via the EM algorithm”, IEEE Trans. Commun., vol. 45, n°3, pp. 300-308, 1997.

[128] A.P. Dempster, N.M. Laird and D.B. Rubin, “Maximum likelihood from incomplete data

via the EM algorithm”. Journal of the Royal Statistical Society, 39(1):pp. 1-38,1977, Series

B.

[129] X. Wautelet, C. Herzet, A. Dejonghe, L. Vandendrope, “MMSE-base and EM Iterative

Channel Estimation Methods”, Symposium IEEE Benelux Chapter on Communications and

Vehicular Technology, 2003

[130] Y. Xie and C.N. Georghiades, "Two EM-type channel estimation algorithms for OFDM

with transmitter diversity," IEEE Trans. Commun., vol.51, no.1, pp.106–115, Jan. 2003.

[131] Henk Wymeersch, , “Software Radio Algorithms for Coded Transmission”, Faculty of

Engineering, Ghent University, September2005. Advisors: Prof. M. Moeneclaey and Prof.

H. Steendam

[132] Henk Wymeersch, Frederik Simoens and Marc Moeneclaey “Code-aided joint channel

estimation and frame synchronization for MIMO systems”, Workshop on Signal

Processing Advances in Wireless Communications (SPAWC'04), , July 2004

[133] J. J. Van de Beek, P.O. Borjesson, M. L. Boucheret, D. Landstrom, J. M. Arenas, O.

Odling, M. Wahlqvist and S. K. Wilson, “A time and frequency synchronization scheme for

multiuser OFDM,” IEEE JSAC, vol. 17, pp. 1900-1914, Nov. 99.

[134] S. Barbarossa, M. Pompili and G. B. Giannakis, “Channel-independent synchronization of

orthogonal frequency division multiple access systems,” IEEE JSAC, vol. 20, pp. 474-486,

Feb. 2002.

186 Amir Saemi

[135] Z. Cao, U. Turelli and Y. D. Yao, “Efficient structure-based carrier frequency offset

estimation for interleaved ofdma uplink,” ICC Proc., May 2003.

[136] M. Morelli, “Timing and frequency synchronization for the uplink of an OFDMA system,”

IEEE Trans. Commun. vol. 52, pp. 296-306, Feb. 2004.

[137] M. Morelli and U. Mengali, “Carrier-frequency estimation for transmissions over selective

channels”, IEEE Trans. Commun., vol. 48, pp. 1580-1589, Sept. 2000

[138] M.O Pun, M. Morelli, C. C. Jay Kuo, “Maximum-Likelihood Synchronization and Channel

Estimation for OFDMA Uplink Transmissions”, IEEE Trans. Commun., vol. 54, pp. 726-

736, Apr. 2006.

[139] I. Ziskind and M. Wax, “Maximum likelihood localization of multiple sources by

alternating projection”, IEEE trans. Acoust. Speech, Signal Process., vol. 36, n°10, pp.

1553-1560, Oct. 1998.

[140] B. Lu, X. Wang, and K. R. Narayanan, “LDPC-based space-time coded OFDM systems

over correlated fading channels,” IEEE Trans. Commun., vol. 50, pp. 74-88, Jan. 2002.

[141] T. Roman et al, "Joint time-domain tracking of channel and frequency offsets for MIMO-

OFDM systems", Wireless Personal Communications, vol31, pp181-200, 2004.

[142] U. Tureli and P. J. Honan, “Modified high-efficiency carrier estimator for OFDM

communications with antenna diversity,” in Proc. 35th Asilomar Conf. Signals, Syst.,

Comput., vol. 2, Pacific Grove, CA, Nov. 2001, pp.1470–1474

[143] H. Meyr, M. Oerder and A. Polydoros, “On sampling rate, analog pre.ltering, and suf.cient

statistics for digital receivers,” IEEE Trans. Commun., vol. 42, pp. 3208-3213, Dec. 1994.

[144] S. Kay, Fundamentals of Statstical Signal processing: Estimation theory. Englewood

Cliffs, NJ: Prentice-Hall, 1993.

[145] P.Stoica and R. Moses, Introduction to Spectral analysis. Upper Saddle River, NJ:

Prentice-Hall, 1997.


188 Amir Saemi

SYNCHRONISATION DES SYSTEMES DE TRANSMISSION MIMO-OFDM

ABSTRACT Theoretical studies of communication links employing multiple transmit and receive antennas,

also known as multiple-input multiple-output (MIMO), have shown great potential for providing

highly spectrally efficient wireless transmissions. The early investigations focused almost

entirely on flat fading channels. To consider frequency selective channel one efficient method in

high rate wireless systems is Orthogonal Frequency-Division Multiplexing (OFDM). MIMO-

OFDM combines OFDM and MIMO techniques thereby achieving spectral efficiency and

increased throughput.

However, because of using Discrete Fourier Transform (DFT), an OFDM system is very

sensitive to carrier frequency offset (CFO), which introduces inter-carrier interference. Accurate

frequency synchronization is thus essential for reliable reception of the transmitted data. On the

other hand, incorrect positioning of the DFT window within an OFDM word reintroduces ISI

during data demodulation, causing serious performance degradation. This dissertation deals with

MIMO-OFDM synchronization. To this aim, several synchronization algorithms are studied in

this manuscript and a new Maximum-Likelihood (ML) joint time-frequency MIMO-OFDM

synchronization algorithm together with channel estimation is presented. Moreover, an iterative

Expectation-Maximization (EM) time-frequency synchronization algorithm is introduced and at

the end the problem of synchronization in MIMO-OFDMA systems is considered.

KEYWORDS SISO, MIMO, OFDM, OFDMA, synchronization, symbol timing, frame synchronization, carrier

frequency offset, CFO, channel estimation, ML, EM

RESUME La technique multi-antenne dans les systèmes de communication numérique (MIMO) sans fil

augmente considérablement la capacité du canal de propagation. Les premières études se sont

concentrées sur les canaux non-sélectifs en fréquence. Afin de combattre l'effet multi trajet des

canaux radio-mobile, la modulation OFDM a été proposée depuis quelques années. La

combinaison d'OFDM avec MIMO ouvre la porte vers des communications hauts débits.

Cependant, un système OFDM est très sensible à une erreur de fréquence porteuse qui détruit

l'orthogonalité entre les porteuses. Cet effet va dégrader radicalement la performance du système.

Les recherches rapportées dans ce mémoire aborde le problème de la synchronisation

fréquentielle et temporelle ainsi que l'estimation du canal MIMO des systèmes MIMO-OFDM.

Après avoir dressé l'état de l'art de la problématique correspondante, de nouveaux algorithmes

basés sur l’algorithme de maximisation de vraisemblance et l'algorithme d'espérance et

maximisation (EM), ont été proposés, puis simulés. Les résultats obtenus ont été comparés avec

ceux de la littérature en terme de performance et de complexité. A la fin de ce mémoire le

problème de la synchronisation dans les systèmes MIMO-OFDMA est étudié et un algorithme

original est proposé.

MOT CLES SISO, MIMO, OFDM, OFDMA, synchronisation, timing de symbole, synchronisation de trame,

CFO, estimation de canal, maximisation de vraisemblance, ML, EM

Documents

Présentée et soutenue par Monsieur Amir SAEMI