DSP Algorithm Implementation of Synchronization and Frequency Offset

Estimation for IEEE 802.16e Downlink

Nuzli Mohamad Anas, Mohamad Yusri Mohamad Yusof, Mohammed Abdo Saeed, Mohd Shafiq Alias

Wireless Software Development

MIMOS Berhad

Kuala Lumpur, Malaysia

{nuzli.anas, myusri.myusof, m.saeed, shafiq.alias}@mimos.my

Abstract— This paper presents synchronization and frequency

offset estimation of IEEE 802.16e downlink implementation

using preamble on digital signal processor. We considered time

division duplex mode, physical layer baseband processing, to

detect the preamble and further calculate the symbol timing,

frequency/phase offset and frame synchronization of the

received signal. Consequent information of cell identification

such as preamble index, ID cell and segment used can be

deduced from detected preamble start symbol. In this paper,

we further described a software implementation of the

downlink transceiver function on Tensilica LX3 DSP.

Numerical profiled data presented indicate the areas where

further improvement can be investigated.

Keywords-component; formatting; orthogonal frequency

division multiple access (OFDMA); carrier frequency;

synchronization

I. INTRODUCTION

Worldwide Interoperability for Microwave Access

(WiMAX) is a wireless broadband technology caters for

Metropolitan Area Network (MAN) based on IEEE 802.16

standard. The current WiMAX incarnation, Mobile WiMAX,

based upon IEEE 802.16e standard, essentially standardizes

the several air interfaces for its physical (PHY) layer and

medium access control (MAC) layer. Research activities on

the mobile WiMAX deployment is under way to support

higher bit rate up to 15 Megabit per second for 5 Megahertz

bandwidth at a considerable 5 km reach of distance. The

mobility mode of 802.16e uses Orthogonal Frequency-

Division Multiplexing Access (OFDMA) transmission,

which achieves multiuser access by dynamically

multiplexing different users in both time and frequency

domains. The mobile WiMAX system also utilizes

bandwidth scalability, where the FFT size typically increases

with the bandwidth.

IEEE 802.16e support two multiplexing modes,

Frequency-Division Duplexing (FDD) and Time-Division

Duplexing (TDD), which the later is widely deployed, where

downlink (DL) and uplink (UL) transmission are time

multiplexed in each frame as shown in Fig. 1. DL sub frame

preceded the UL sub frame in OFDMA frame duration. The

first symbol in DL is a preamble that uniquely identifies the

serving base station (BS). It allows mobile station (MS) to

obtain initial synchronization including time acquisition,

carrier frequency synchronization and cell identification. It is

required during initial power-up, neighboring cell search or

re-synchronization due to momentary loss of

synchronization.

In this paper, we proposed techniques that best suits for

synchronization and frequency offset estimation, exploiting

the preamble properties in both time and frequency domain.

This work utilizes the mandatory features of the IEEE

802.16e standard that have been selected for mobile WiMAX

certifications [1].

Delay correlation technique has been employed to

calculate the coarse preamble location taking advantage time

domain characteristic of the preamble structure. This process

acquires frame and symbol timing at the mobile receiver

during initial synchronization. Consequently, the coarse

integer frequency offset is calculated in terms of subcarrier

spacing where the captured preamble is cross correlated with

the set of all possible preamble pattern defined in 802.16e

standard. Then, the cell identification information used for

this transmission such as preamble index, ID cell and the

segment can be retrieved.

Once the integer part of the frequency offset is

calculated, the fractional part is further estimated using auto-

correlation of the preamble symbols in time domain. Both

frequencies offset and phase shift of the carrier frequency

can be retrieved in term of Hertz and radians units

respectively. In 802.16e, the preamble symbols are

Figure 1. TDD OFDMA Frame Structure

Second International Conference on Computational Intelligence, Modelling and Simulation

978-0-7695-4262-1/10 $26.00 © 2010 IEEE

DOI 10.1109/CIMSiM.2010.100

318

Second International Conference on Computational Intelligence, Modelling and Simulation

978-0-7695-4262-1/10 $26.00 © 2010 IEEE

DOI 10.1109/CIMSiM.2010.100

351

Second International Conference on Computational Intelligence, Modelling and Simulation

978-0-7695-4262-1/10 $26.00 © 2010 IEEE

DOI 10.1109/CIMSiM.2010.100

351

6 3 3 0

Figure 2. Preamble Symbol Structure

modulated using a boosted binary phase shift-keying (BPSK)

modulation on every third subcarrier in frequency domain.

The rest of this paper is organized as follows: In section-

II, we briefly discuss the system model for OFDMA mode of

mobile WiMAX and the properties of its preamble symbol.

Section-III explain the preamble detection and

synchronization algorithm used in this work. Section-IV

presents the implementation and numerical profiled data on

Xtensa LX3 hardware platform of Tensilica architecture and

finally we conclude the findings of the paper by

recommending further research on the hardware optimization

techniques.

II. OVERVIEW OF IEEE 802.16E OFDMA

The mobile WiMAX air interface utilizes OFDMA as

one of the radio access method to improve multipath

performance in non-line-of-sight (NLOS) environments

operating in frequency band below 11 GHz. The use of

multiple-input multiple-output (MIMO) antenna techniques

along with flexible sub-channelization schemes, adaptive

modulation and coding enable the mobile WiMAX

technology to support peak DL data rates up to 32 Mbps per

sector and peak UL data rates up to 4 Mbps per sector in 20

MHz bandwidth.

A. TDD Mode Frame Structure

The IEEE 802.16e air-interface supports both FDD and

TDD modes; however, the initial release of mobile WiMAX

profiles [2] only includes the TDD mode of operation due to

several reasons. It enables dynamic allocation of DL and UL

resources to efficiently support asymmetric DL/UL traffic. It

also ensures channel reciprocity for better support of link

adaptation; MIMO and other closed-loop advanced antenna

techniques such as transmit beam-forming. Unlike FDD,

which requires a pair of channels, TDD only requires a

single channel for both downlink and uplink providing

greater flexibility for adaptation to varied global spectrum

allocations.

Among several mode specified under IEEE 802.16e

standards [1], OFDMA is the most interesting modes that

offers bandwidth scalability from 1.25 MHz to 20 MHz

depending on the FFT size used depicted in Table I. Thus,

the deployment scenario can be varying towards the cell size,

available spectrum, system capacity etc. Fig. 1 shown TDD

transmission mode where the same frequency band is used

for DL and UL transmission in different time intervals. The

DL/UL sub frames and UL/DL sub frames are separated by

transmit/receive transition gap (TTG) and receive/transmit

transition gap (RTG) respectively.

B. Preamble Symbol Structure

Preamble signal, which is an orthogonal frequency

division multiple access (OFDMA) symbol transmitted at the

beginning of each frame, i.e. at the first symbol of the DL

transmission. Each preamble has its own unique patterns

transmitted from the base station.

There are three types of preamble carrier set, which are

defined by allocation of different subcarrier for each one of

them. Those subcarriers are modulated using a boosted

BPSK modulation with a specific pseudo-noise (PN) code.

The preamble carrier sets are defined using equation below.

PreambleSetn = n + 3k. (1)

Each segment uses one type of preamble out of the three

sets, whereby n is 0, 1 and 2 and k is an integer. A segment is

a subdivision of the set of available orthogonal frequency

division multiple access (OFDMA) sub channels. Fig. 2 is

the illustration of on preamble carrier set transmitted on n

segment.

III. SYNCHRONIZATION AND FREQUENCY OFFSET

ESTIMATION

A. Time Synchronization

The algorithm for time synchronization is based on

correlating the preamble with a delayed version of N/3 where

N is the FFT size. Hence, this technique named as delay

correlation. The preamble samples in the time domain are

repeated three times because the preamble bits modulate at

each third subcarrier in frequency domain.

The samples Xk in the frequency domain exist only for k

= 3l where l is integer. Taking the inverse Discrete Fourier

Transform (IDFT) of Xk, we get xn as

∑−

=

=1

0

N

k

nk

Nkn WXx , (2)

TABLE I. PRIMITIVE PARAMETERS FOR WIMAX

Bandwidth (MHz) 20 10 5 1.25

FFT size 2048 1024 512 256

Sampling factor 28/25

CP ratio 1/8

Sampling frequency (MHz) 22.4 11.2 5.6 1.4

Subcarrier spacing (kHz) 10.94

Symbol time (µs) 91.42

CP time (µs) 11.42

OFDMA symbol time 102.86

319352352

Figure 3. Delay Correlation of Received Preamble

∑−

=

=

13

0

3

3

N

l

nl

NlWX , (3)

∑−

=

=

13

0

33

N

l

nl

NlWX . (4)

Replacing n by (n+N/3) in the right hand side of the

above equation, we conclude that

3/23/ NnNnn xxx ++ == , (5)

for n = 0, 1, 2,…., N/3. Therefore, the samples in the time

domain are periodic every N/3. This property is used for time

synchronization of frames starting with the preamble symbol

consists of N (1+CP) number of samples, where cyclic

prefix, CP is 1/8. The first part of this OFDM symbol of NCP

samples is a repetition of the last NCP samples. Therefore, if

the first N (1+CP)-(N/3) samples are delayed by N/3, they

will be identical to the original preamble samples as shown

in fig. 3.

In other words, xn = xn+N/3 for n = 0, 1, 2, … , N(1+cp)-

(N/3)-1 samples. Since the preamble N(1+cp) samples are

followed by random samples representing other data, the first

preamble sample can be identified by using the fact that the

following sum is maximum for preamble signal delay, D = 0

assuming that the first preamble sample exist at n = 0

∑−−+

=

+++

1)3

()1(

0

3/

*

NCPN

n

NDnDn xx . (5)

In the following, N/3 is called the correlation delay and N

(1+cp)-N/3 is called the moving average window length. If

the first preamble sample does not exist at n = 0, the

preamble signal delay, D is determined by finding the value

of D that maximizes the above sum. The searching for this

value is done by processing at a given range of the signal

samples. The process is repeated for a predefined range of D.

At the end, the value of D is the output start of frame of the

function corresponding to maximum correlation.

B. Integer Frequency Offset Estimation

The algorithm used to estimate the carrier integer

frequency offset in terms of subcarrier spacing is simply the

cross correlation between the received noisy shifted

preamble with all or some of the original preambles defined

in the IEEE 802.16e standard according to the FFT size. The

correlation is done in the frequency domain with various

shifted versions of each original preamble. The maximum

value of the correlation corresponds to the result of

autocorrelation of the preamble with itself considering the

absence of noise. We can summarize the algorithm in the

following equations.

m(n,k,f) = Pk(f-n) x R(f), (6)

c(n,k) = ∑Re{m(n,k,f) x m(n,k,f+2)}, (7)

where, m (n, k, f) denotes the multiplication of the kth

preamble with nth shift by the received preamble in the

frequency domain at each value of f according to the FFT

size, and

n∈{-windowSpacing, windowSpacing}, (8)

k = preamble index {0, 1, 2, …, 113} and c(n, k) denotes the

summation of the real part of the results of multiplication of

each non zero value of m(n,k,f1) by the next non zero value

of m(n,k,f2). The evaluation of c(n, k) corresponds to the

evaluation of the cross correlation between an original

preamble and the received preamble. At the maximum value

of the correlation process, the preamble index, ID cell and

the segment number used for the transmission can be

extracted with the estimated integer frequency offset as a

multiple of the subcarrier spacing.

C. Fractional Frequency Offset Estimation

This section explained the estimation of the phase error

in term of radians between two successive samples and the

frequency offset in Hertz in the sampling frequency. Let say,

the received noisy preamble samples in the time domain are

given by

∑−

=

++=

1

0

/)(2N

k

n

Nknj

kn neXrεπ

, (9)

where ε is the relative frequency offset which is the ratio of

the actual frequency offset to the inter carrier spacing.

Assuming negligible noise samples nn, then

∑−

=

+=

13

0

)3(2

3

N

l

lnj

ln eXr επ (10)

320353353

∑−

=

++

+=

1

0

))(3/(2

3

N

k

N

kNnj

kNn

eXr

επ

(11)

∑−

=

++

=

13

0

)3)(3/(2N

l

N

lNnj

keX

επ

(12)

∑−

=

+

=

13

0

3

2)3/(2N

l

j

N

Nnj

k eeX

πεπ

(13)

Comparing the equations (10) and (13), we conclude that

3

2

3

πεj

nNn

err =+

, for v = 0, 1, 2, ... , (Ν/3)−1. (14)

Therefore, ε can be determined by comparing preamble

samples spaced by N/3. The resulting phase rotation between two successive samples is related to ε by θ = 2πε/N

and can be obtained by multiplying rn+N/3 with the conjugate

of rn.

Since the FFT sizes, i.e: 512 and 1024, are not divisible

by 3, an interpolation from the original preamble value is

calculated to find the 1/3 and 2/3 of the three repetitive part

of preamble. Then, we correlate the parts between each other

as follows: first R12 is computed from comparing the first

and second thirds of preamble samples. Then R23 is

computed from comparing the second and third parts of

preamble samples

∑−

=

+=

13

0

3/

*

123/

1

N

n

Nnn rrN

R (15)

∑−

=

++=

13

0

3/2

*

3/233/

1

N

n

NnNn rrN

R (16)

The average of the products R = (R12 + R23)/2 is then

computed and its phase from

=−

)Re(

)Im(tan 1

R

Rθ (17)

The phase rotation between two successive samples θ is

finally obtained by dividing it by N/3. The frequency offset

is obtained by multiplying θ with the sampling frequency

over 2π.

IV. IMPLEMENTATION AND RESULTS

We present the result of the synchronization and

frequency offset estimation implementation on Tensilica

LX3 platform. The main parameters are tabulated in Table 2.

The synchronization algorithm involves the correlation

process between the received samples and its delayed

replica. Then, the output of correlation is passing through a

moving average filter to remove errors and finding the peak

value that corresponding to the start of frame. This process

consumes an extensive clock cycles as the calculation is

carried throughout the downlink received symbol which

exceed 14 million cycles.

V. CONCLUSION

In this paper, we have proposed a timing synchronization

algorithm and frequency offset estimation that is suitable for

synchronization and preamble detection for downlink IEEE

802.16e. Our approached exploiting preamble structure and

FFT properties as the key signal processing function. We

also tabulate the clock cycle’s consumption implemented on

Tensilica LX3 DSP platform. Intuitively, there are still lots

of room for improvement and optimization. The cycle count

can be further reduced by commonly used Single Instruction

Multiple Data (SIMD) techniques.

REFERENCES

[1] IEEE 802.16e-2005, Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands

[2] WIMAX Forum Mobile System Profile 4 Release 1.0 Approved Specification 5, Revision 1.2.2: 2006-11-17.

[3] J. Heiskala, J. Terry, OFDM Wireless LANs: A Theoretical and Practical Guide, 1st Edition, Sams, 2001.

[4] Hua Zhou , Hayashi, H. , Kubo, T. , Jie Zhang , “A Novel Carrier Frequency Offset Estimation Method for IEEE 802.16E System”, Proc IEEE GLOBECOMM 2007, Nov. 2007

[5] A. Salbiyono , T. Adiono , “Preamble Structure-based Timing Synchronization for IEEE 802.16e”, Proc IEEE ISPACS 2009

[6] Bhatt, T. , Sundaramurthy, V. , Jianzhong Zhang , McCain, D. , “Initial Synchronization for 802.16e Downlink”, Proc IEEE ACSSC 2006

TABLE II. PROFILING RESULT OF SYNCHRONIZATION AND FREQUENCY OFFSET

ESTIMATION

Function Clock Cycles Code Size

Time Synchronization 14,142,416 1,804

Integer Frequency Offset 2,798,400 607

Fractional Frequency Offset 2,811,613 324

321354354