Frequency Synchronization Algorithms for OFDM Systems
`suitable for Communication over Frequency Selective Fading Channels
`
`Ferdinand Classen, Heinrich Meyr
`Aachen University of Technology; ISS; Templergraben 55, 52056 Aachen, Germany
`email: classen Q ert.rwth-aachen.de
`
`Abstract
`In this paper, the problem of carrier synchronization of
`OFDM systems in the presence of a substantial frequency
`offset is considered. New frequency estimation algorithms
`for the data aided (DA) mode are presented. The resulting
`two stage structure is able to cope with frequency offsets in
`the order of mukbles of the spacing between subchannels.
`Key features of the novel scheme - W ~ i c h are presented in
`terms of estimation error variances, the required amount of
`training symbols and the computational load - ensure high
`speed synchronization with negligible decoder performance
`degradation at a low implementation effort.
`
`1 Introduction
`Recently an OFDM system with M-PSK modulation has
`
`where adjacent subchannels carry the elements of a differen-
`tially encoded pseudo noise PN sequence and he based his
`algorithm on a correlation rule applied to this PN sequence.
`A similar idea is used in our contribution. But in contrast to
`[5] our algorithm allows the condition on the frame format to
`be relaxed and we do not have to require - as Muller did -
`that the channel is quasi constant within a fbted bandwidth.
`Besides that the synchronization task is performed into two
`steps, an acquisition step and a tracking step. The paper
`is organized as follows. We begin by proposing the OFDM
`receiver and analyzing the effect of a frequency error. Sec-
`tions 3 - 4 describe the synchronizer structures and the paper
`ends. with the presentation and discussion of the simulation
`results for the AWGN and various frequency selective fading
`channels.
`
`ing channel, i.e. a sophisticated equalization unit mandatory
`for a single carrier transmission scheme becomes obsolete.
`However, on the other hand, the frequency synchronization
`for multi carrier (multi sub~hannel~) systems is more compli-
`cated than for sinale carrier svstems. In the case of a carrier
`offset the orthog&lity pr&rty
`is disturbed and the result-
`ing inter-channel interference between the subchannels of
`the OFDM systems severely degrades the demodulator per-
`formance. For high order modulation schemes such as those
`under consideration for TV applications, a frequency offset of
`a small fraction of the subchannel symbol rate leads to an in-
`tolerable degradation. Therefore, frequency synchronization
`is one of the most prominent tasks performed by a receiver
`suitable for OFDM.
`Several authors have addressed the frequency synchro-
`nization problem for OFDM. Daffara [2] proposed a non data
`aided (NDA) frequency estimation scheme for an AWGN
`channel. But such an NDA structure - which does not make
`we of known symbols - fails in the case of severely frequency
`selective channels or if a high order modulation scheme is
`used.
`As is well known from single carrier transmission sys-
`tems in a frequency selective fading channel environment,
`the frequency synchronization has to be assisted by the
`transmission of known training sequences [a, 41. This ip
`also mandatory for multichannel modulation transmission
`schemes. MOlIer introduces in [5] a special frame format
`
`'(') = -
`
`ej2nJot
`
`l = - q + N Q
`
`an,l eZnJtt g(t - nTsym)
`
`(1)
`
`where N is the total number of subchannels and NG =
`NGuard is the number of the subchannels which are not
`modulated in order to avoid aliasing effects at the receiver
`[l]. Here, g ( t ) is a pulse waveform defined as
`
`where TG is the so called guard period. For the sake of a
`simple transmitter implementation TG should be a multiple of
`Tsub/N. The frequency separation between two subchannels
`is denoted by l/Tsub. The OFDM symbol duration is given
`by Tsym = TG + Tsub. In this case {an,l} is a sequence of
`M-PSK or M-QAM symbols with E { la,,1I2} normalized to one
`and an,l is the symbol carried by the I* subchannel during the
`nm time slot of period Tsym. The total symbol rate is given
`by (A' - 2h.'c)/Taub. The variable fo stands in (1) for the
`unknown carrier frequency offset.
`The transmitted signal is disturbed by additive white gauss-
`ian noise and by a multipath fading channel. In the receiver,
`the received signal is filtered by a lowpass filter (for example
`a root raised cosine filter with rolkdf factor p = 0.1 and a cutoff
`
`0-7803-1927-3/94l$4.00 0 1994 IEEE
`
`1655
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 1
`
`

`

`coarse timing
`estimation
`time domain
`
`~
`
`/ I
`
`r
`
`I
`
`I
`
`A
`
`1 - 1
`
`"
`
`Y
`
`
`
`I
`
`Figure 1: Synchronization path of tbe receiver
`
`frequency at &.
`After deleting the samples which be-
`long to the guardtime period, a block of N samples is applied
`to the demodulation unit of the OFDM system. The demodu-
`lation unit can be very effiiiently implemented by an FFT unit.
`From the FFT output we obtain the Fourier coefficients of the
`signal in the observation period [n Tsym, n Tsym + Tsub]. The
`FFT unit represents the matched filter of an OFDM modulated
`signal. The output zn,l of the lth carrier at time n Tsym can
`be written as
`
`.(e)
`
`is the Fourier coeffiiient of the
`where H p l ) =
`overall channel impulse response of the transmission chan-
`nel including the transmitter filter, the channel and the re-
`ceiver filter. We have assumed that the guardtime is ap-
`propriately chosen which means that this time is larger than
`the significant part of the overall channel impulse response.
`The complex noise process corrupting the lth subchannel
`is represented by nn,l. The noise process has a statis-
`tically independent real and imaginary part each having a
`variance of %*. Therefore Tdym/Tsub reflects the fact
`that the guardtime bads to a theoretical SNR degradation of
`10 log (1 - *)dB
`[l]. The samples nn,l are uncorrelated
`as long as the noise samples corrupting the N input samples
`of the FFT unit are uncorrelated.
`Equation (3) is only valid in the case of perfect synchro-
`nization. In the presence of an uncompensated frequency
`offset, the orthogonality of the subchannels can no longer be
`exploited by the demodulator unit. As a result cross talk be-
`tween each subchannel arises. The impact of this cross talk
`can be described by an additional noise component. Within
`the channel 1 = v the expected value of the power of this
`component can be calculated analogously to [2]
`
`with foTsub < f. Fig. 2 shows the theoretically obtained and
`
`simulated value of PCT.
`
`'CT m
`
`-10.
`
`-20.
`
`-30.
`
`'-1 .
`
`I
`
`.
`
`.
`
`.
`
`
`
`0.4
`0.2
`,
`,
`frequency offset normalized to Tsub
`
`For a small frequency offset fo <
`can be written as
`
`the output z,,~
`
`The exponential term results from the phase drift caused by
`the frequency offset and 6,,1 represents the impact of the
`cross talk. The phase of this complex valued noise process
`iLn,l can be shown to be approximately uniformly distributed
`between [ - x , 4 and the power of this term is given by (4).
`
`3 Carrier Frequency Synchronization
`Generally we distinguish between two operation modes,
`the so called tracking mode and the acquisition mode.
`Whereas during the tracking mode only small frequency fluc-
`tuations have to be dealt with, the frequency offset can take
`on large values (in the range of multiples of the subchannel
`spacing), if the receiver is in the acquisition mode. This is
`the most challenging task to be managed by the synchro-
`nizer structure.
`Below we present a two stage synchmizatbn writ (com-
`pare Fig. 1) which provides a robust acquisition behavior and
`shows an excellent tracklng behavbr. The task of the first
`
`1656
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 2
`
`

`

`stage (unit) is to solve the acquisitii problem by generating
`as fast as possible a coarse frequency estimate. With the
`help of this estimate the second stage (unit) should be able
`to bck and to perform the tracking task. The splitting of the
`synchronization task into two steps allows a large amount of
`freedom in the design of the complete synchronization struc-
`ture because for each stage an algorithm can be tailored to
`the specific task to be performed in this particular stage. This
`means that the first stage - this is the acquisitii unit - can
`be optimized for example with respect to a large acquisitii
`range whereas its tracking performance is of no concem. In
`contrast, the second stage should be designed to exhibit a
`high tracking performance since a large acquisitii range is
`no longer required.
`In sectbn 3.1 we describe the algorithms for the tracking
`mode and in section 3.2 we present the algorithms for the
`acquisition mode. As we will see, a two stage structure does
`not automatically result in doubled implementation cost, or in
`the doubling of the required amount of training symbols.
`
`should be spread uniformly over the whole frequency domain.
`The following generalized estimator can be formulated
`
`, L v - l
`
`I
`
`The function p(j) gives the position of the j"' sync-subchannel,
`which carries one of the LF known training symbol pairs
`(c:,, CO,,). Note that c:,, and CO,, are transmitted over the
`same subchannel and the symbols {CO,,} belong to the n'
`time period respectively {cl,,} to the (n + D)* time period.
`The overall required amount of training symbols equals 2 L F .
`Figure 3 shows how the LF subchannels should be spread
`uniformly over the 11'-2 NG subchannels. D is an integer and
`describes that (D - 1) other symbols can be placed between
`a training symbol pair [a, 91. The effect of this operation is
`explained in section 4.2.
`
`3.1 Tracking Algorithm Structure
`During the tracking mode it is safe to assume that the re-
`maining frequency offset is substantially smaller than &
`and therefore (5) holds. If we consider only one subchan-
`nel, then this frequency synchronization problem is similar to
`that in the case of a single carrier problem. Therefore we can
`make use of the frequency estimation algorithms derived from
`the ML theory in [6, 71. The underlying principle of these fre-
`quency algorithms is that the frequency estimation problem
`can be reduced to a phase estimation problem by consid-
`ering the phase shift between two subsequent subchannel
`samples e.g. zn,t and zntl,t (without the need of generating
`an estimate of the channel Fourier coefficient H(nl)). The
`influence of the modulation is removed in the data aided DA
`case by a multiplication with the conjugate complex value of
`the transmitted symbols. For the DA case we get
`
`The variile (IMq) makes clear that during the tracking p e r i i
`the output of the demodulator unit - zn,l ( jwp) - depends on
`the frequency estimate (denoted by fMq) of the acquisitii
`unit because (fMq) is used to correct the input samples of
`the demodulation unit. The known symbols are represented
`by {c,,,t} and they are taken from a training sequence. To
`simplify the notatbn we have denoted the training symbols
`by the letter "c".
`lt is not necessary and, besides that, not commendable to
`transmit all elements of the training sequence over a single
`subchannel especially in the case of a frequency selective
`transmitted on e.g. LF - so called - sync-subchannels which
`fading channel. Instead of this the training symbols should be
`
`1657
`
`LF synchronization subcarriers
`TYing:
`t) A
`
`N subcarriers (spacing 1&ub)
`
`m
`
`4
`
`Figure 3: Placement of the LF sync-subchannels; A = WQ
`
`The data aided (DA) operation can be replaced by a deci-
`sion directed (DD) operation if the (c:,, CO,,) are substituted
`by the actual decoder decisions. In the case of an M-PSK
`modulated symbol a non data aided operarlov, (NDA) is pos-
`sible, too [6]. But we found that from a point of view of a
`robust tracking performance neither DD nor NDA operation
`can be recommended especially if a high order modulation
`scheme is used.
`Applying the DA operation it can be shown that the fre-
`quency estimator is approximately unbiased for IAf Taut,( <
`0.5 if LF is sufficiently large e.g. LF = 51 (with 11' = 1024
`and 11'~ = 70). But in order to avoid a large decoder per-
`formance degradation due to the cross talk (compare (4)) it
`may be necessary to correct the frequency offset prior to the
`demodulation even during the tracking mode (compare Fig.
`1). But keep in mind that it is theoretically possible to correct
`a small frequency offset Af TSub << 0.5 on the subchannel
`level. In practice this will depend on the maximum magnitude
`of the frequency offset (fo -
`which the second stage
`(the tracking unit) has to cope with. This magnitude is mainly
`determined by the frequency estimate resolution of the first
`stage and the stability of the mixer oscillator.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 3
`
`

`

`3.2 Acquisition Algorithm Structure
`The acquisitii process should be performed fast and
`above all at b w implementation cost. Besides this, a spe-
`cial acquisitii preamble should be avoided to increase the
`transmission efficiency . Therefore our aim was to use the
`same training synchronization symbols as in (7) and to take
`advantage of those operation units which are implemented
`in any case. From section 3.1 we know that the second
`stage can manage frequency offsets up to its pull-in-range
`of IAf TdUbl < 0.5. Therefore, it is sufficient to require that
`the acquisition unit reduces the frequency offset below the
`above mentioned pull-in-range of the tracking unit.
`
`_ I
`- I t -
`
`I
`I
`
`1I-i
`
`10 dB
`
`I
`I
`
`10.
`
`-4.0
`
`-2.0
`
`0:o
`
`2:0
`(ftrial - fO) Tsub
`
`4:O
`
`Figure 4: Plot of expression (8), L F = 51
`The operation involved in acquiring an initial frequency
`offset estimate coincides with the search operation for the
`training symbols transmitted on the LF sync-subchannels
`shown in Fig. 3. Our acquisition rule is based on the fact
`that the magnitude of the expression within the arg function
`of (7) reaches its maximum if fmq coincides with fo, be-
`cause this expression obeys a sa2(2*(f0 - ftrta1)Tsym) law
`for Ifo -
`Tsub < 0.5 (compare (5)). Therefore we con-
`sider the following maximum search procedure
`
`Z:,p(j)(ftrtal)
`
`( c : , ~ @ , I ) )
`
`I)
`
`(8)
`is the
`is the trial frequency and %n,p(,)(ftrsd)
`where (ftrld)
`output of the FFT unit if its N input samples are frequency
`corrected by ftrlal. In practice we found that it is sufficient
`to space the trial parameters 0.1 /Tau,, apart from each other.
`Figure 4 shows a plot of (8) for different SNR values and
`LF = 51 (11' = 1024) drawn over fo - ftrIaI.
`To avoid local maxima occurring for fo - ftrlal
`=
`{ l , . . . , ( L ~ - l ) } ) , the LF
`(with j
`( p ( d - p ( i - 1 ) )
`products (c:,, CO,,) should be elements of a PN sequence.
`The acquisitii performance was found to be independent
`of the particular shape of the PN sequence (binary- or
`
`CAZAC-sequences). Therefore for the sake of simplifying
`the implementation the most simple realization of the frame
`being chosen as CO+,, P eJ
`format results from
`and c;,,
`being taken from an binary PN-sequence as in [lo] of length
`L F .
`A last comment concems the implementation complexity
`and the acquisition time. As shown in Fig. 1 a costly FFT
`unit is needed within the synchronization path. But this does
`not mean that an extra FFT unit is required because the FFT
`of the decoder path, which is implemented in any case, can
`be used during the acquisition period. Note that the output
`of the decoder path FFT is not required since during the
`acquisition process the output is irrelevant. Therefore besides
`the memory unit (for the 2N samples bebnghg to time sbt n
`and n + D) no additbnal expensive hardware is required.
`The acquisitii time is directly proportional to the frequency
`range which has to be scanned. In the case of a substantial
`frequency offset of e.g. +/ - i n subchamel spacings
`the acquisition time may take on a quite large value. But
`in practice this does not represent a strong shortcoming,
`because we are not operating in a burst transmission mode
`and therefore acquisition has to be performed only once at
`the beginning of the transmission.
`
`4 Synchronizer Performance
`4.1 Acquisition Performance
`the above
`Provided there is an unlimited resolution of
`structure produces an unbiased esttmate. Nevertheless, the
`performance of the acquisition unit should not be measured
`in terms of an estimate variance or estimation bias a h .
`A performance measure for a maximum searching algorithm
`is the probability that an estimation error exceeds a given
`threshold. In our application this threshold is the pull-in-range
`of the second stage. We carried out 1O.OOO Independent
`acquisition cycles and we found that for SNR values above
`5dB this threshold was never exceeded for e.g. LF = 51 (with
`11' = 1024, 11'~ = 70 and 7.5Msym/s as total symbol rate).
`Summing up, it may be said that the acquisition behavbr
`is uncriiical for AWGN channels as well as for frequency
`selective fading channels.
`4.2 Tracking Performance
`As mentioned above, NDA and DD operation can not be
`recommended, therefore the theoretical analysis will be re-
`stricted to the DA case. Folbwhg the method outlined in [6]
`we obtain for the AWGN channel the general expression
`
`Fig. 5 show the simulated and analytically obtained MA-
`ances. The curves are parametrized by the number d sync-
`subchannels LF (therefore, the overall reqUlred number d
`training symbols is 2LF). As indicated in (9) in practice it
`
`1658
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 4
`
`

`

`may be advantageous to select E{lcl} # E{lal}, Additiin-
`ally, Fig. 5 makes the effect of factor D clear. But to avoid
`any misunderstanding, the improvement of the performance
`by selecting D > 1 is only possible if the channel can be
`considered as quasi static within a time period Tslm(D + 1).
`
`on frequency selective fading channels. A final comment con-
`cerns the timing information. Up to now timing is assumed to
`be known. Investigations not reported here have shown that
`a slight modiiication of the preamble allows the above fre-
`quency synchronization structure to be efficiently combined
`with a timing synchronization structure.
`
`frequency estimate variance
`
`f reauencv estimate variance
`
`10-4
`
`104
`
`lo-'
`
`lo-'
`
`'
`
`I
`
`lo-'
`
`10-6
`
`lo-'
`
`30
`
`e
`
`.
`
`.
`
`0.
`
`,
`
`
`
`,
`
`I
`
`*
`
`.
`
`
`
`10. SNR=Es/No 'O'
`[dB1
`Figure 5: Var{ AT,,/27r}, AWGN channel, E{ 1.1) = 1.41,
`64QAM modulation and E(I.1) = 1 , S X R = E S / &
`If the channel varies signifiiantly within Tslm the orthog-
`onality of the subchannels can no longer be exploited and
`as a result z , , ~ is disturbed by cross talk effects. These ef-
`fects are proportional e.g. to the amount of the (time se-
`lecttviiy) Doppler delay spread. Figure 7 shows the simula-
`tion results for a frequency and time selective fading channel
`(with N = 1024, NG = 70 and 'T.FiMsym/s as total sym-
`bol rate) whose multipath delay profile is sketched in Fig. 6.
`The strong performance degradation in the case of a Doppler
`
`0.
`
`10.
`20.
`SNR=ES/NO
`Figure 7: Influence of the time selectivity
`E{IcI) = 1.41, 64QAM
`on Var{hT,,},
`modulation and E{lal} = 1 , channel of Fig. 6
`
`90.
`tdB1
`
`Bibliography
`
`Paul G.M. de Bot, Stan Baggen, Antoine Chouly and America
`Brajal. An Example of a MulE-Resolution Digital TV Modem.
`Proceedings ICC' 93, pages 1785-1790, 1993.
`Flavio Daffara and Antoine Chouly. Maximum Likelihood Fre-
`quency Detectors for Orthogonal Multicarrim Systems. Pro-
`ceedings ICC 93. pages 766471,1993.
`Chevillat. P.R., Maiwaki, D., and Ungerboeck, G. Rapid Training
`of a voiceband Data Modem Receiver employing an Equalizer
`with fractional T-spaced Coefficients. I€€€
`Trans. Commun.,
`COM-3!3869-876, Sep. 1987.
`Fechtel. S.A. and Meyr, H. Fast-Frame Synchronization, Fre
`quency Offset Estimation And Channel Aquisition For Sponta-
`neous Transmission Over Unknown Frequency Selctive Radio
`Channels. In Proceedings PlMRC'93 Yokohama, Japan, Sep.
`1993.
`Andreas Muller. Schatzung der Frequenzabweichung von
`OFDM-S~gnalen. ITG Fachbericht Nr. 124 Mobile Kmmunika-
`tion, Neu-Ulm, pages 89-101, Sept. 1993.
`Ferdinand Classen, Heinrich Meyr and Philipp Sehiier. "Max-
`imum Likelihood Open Loop Carrier Synchronizer for Digital
`Radio "_ Proceedings ICC 93, pages 493-497, 1993.
`Steven Kay. A fast and accurate single frequency estimator.
`/€E€ Trans. Aawst., Speech, Signal Processing, ASSP-
`37(12):1987-1990, December 1989.
`Ferdinand Classen, Heinrich hkyr and Philipp Wkr. "An All
`Feedfonvard Synchronization Unit for Digital Radio '. Proceed-
`1993.
`ings VTC 93. pages 738-741
`Jack Wolf and Jay Schwartz. Compariison of Estimators for
`Frequency Offset. /E€€ COM. (1):124-127. Januar 1990.
`(lo] J. Lindner. 'Binary Sequences up to Length 40 with k
`t
` PoS-
`sible Autocotrelation Function'. Ektronics Letter, V d 11507,
`1975.
`
`I
`
`Figure- 6: Multiplath delay profile
`
`spread of X = S S H z results from the impact of the time selec-
`tivity. This impact becomes dominating for high SNR values.
`But since the expected value remains unbiased a further im-
`provement of the estimate can be obtained via a filtering of
`the estimates.
`
`5 Discussion and Conclusion
`The performance of a two stage synchronization structure
`has been studied. The synchronization structure is able to
`cope with large frequency offsets in the range of multiples of
`the spacing between the subchannels. Analysis and simula-
`tions have shown that fast and robust synchronization can be
`established at low implementation cost on AWGN as well as
`
`1659
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 5
`
`