US005732113A
`5,732,113
`(11) Patent Number:
`United States Patent 9
`Schmid et al.
`[45] Date of Patent:
`Mar. 24, 1998
`
`
`AUEYA
`
`[54] TIMING AND FREQUENCY
`SYNCHRONIZATION OF OFDM SIGNALS
`
`[75]
`
`Inventors: Timothy M. Schmidl; Donald C. Cox,
`
`Primary Examiner—Stephen Chin
`Assistant Examiner—Mohammad Ghayow
`Attorney, Agent, or Firm—Lumen Intellectual Property
`Services
`
`[73] Assignee: Stanford University, Stanford, Calif.
`
`[21] Appl. No.: 666,237
`
`[22] Filed:
`Jun. 20, 1996
`6
`50]
`Tate Ga cccstnrcccrcuscmuacenatemic OGL 700
`[52] US. CL.
`seuscacrecnennanecsucscensesreeretwenereneess 375/355; 375/354
`[58] Field of Searcha .....ccccseccssccsseseneee 375/354, 355;
`370/206, 208
`
`[56]
`
`References Cited
`
`A method and apparatus achieves rapid timing
`synchronization, carrier frequency synchronization, and
`sampling rate synchronization of a receiver to an orthogonal
`frequency division multiplexed (OFDM)signal. The method
`uses two OFDM training symbols to obtain full synchroni-
`zation in less than two data frames. A first OFDM training
`symbol has only even-numbered sub-carriers, and substan-
`tially no odd-numbered sub-carriers. an arrangement that
`results in half-symbol symmetry. A second OFDM training
`symbol has even-numberedsub-carriers differentially modu-
`lated relative to those of the first OFDM training symbol by
`a predetermined sequence. Synchronization is achieved by
`computing metrics which utilize the unique properties of
`these two OFDM training symbols. Timing synchronization
`is determined by computing a timing metric which recog-
`izes
`the half-symbol symmetry of the first OPDM training
` MZES
`:
`ee
`symbol. Carrier frequency offset estimation is performed in
`USing the timing metric as well as a carrier frequency offset
`metric which peaks at the correct value of carrier frequency
`Offset. Sampling rate offset estimation is performed by
`evaluating the slope of the locus of points of phase rotation
`due to sampling rate offset as a function of sub-carrier
`frequency number.
`
`26 Claims, 15 Drawing Sheets
`
`U.S. PATENT DOCUMENTS
`11/1992 Mo0se
`escssseneenensrnsesnsonne 370/32...
`7/1993 teFok eal... 370/20
`_... 370/19‘
`4/1995 Saito et all .........
`ssa 370/19
`8/1995 Leungetal .......
`we 370/19
`11/1995
`4/1996
`daeann 370/19
`5/1996
`. 375/295
`8/1996
`~- 370/19
`9/1996
`2/1997
`
`
`
`.. 370/206
`
`5,166,924
`5.228025
`5,406,551
`5,444,697
`5,471,464
`5,506,836
`5,521,943
`5,550,812
`5,555,268
`5,602,835
`
`
`
`
`
`Computation
`
`Memory/
`Data
`Storage
`Buffer
`
`Microprocessor/
`DSP Firmwarefor
`
`120
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 1
`
`

`

`Ouws«KY
`
`® I
`
`factATS
`
`wzooaouwcnt
`
`pueqeseg
`
`slige1eq
`
`ck
`
`*“"LOLLO™
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 2
`
`US. Patent
`
`Mar. 24, 1998
`
`Sheet 1 of 15
`
`5,732,113
`
`pete eee eee eee ee eeeerer
`
`|
`
`(0)
`(9 +B}
`
`+O
`
`(uy401d)|“SIS
`
`SLQLvk
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 2
`
`

`

`U.S. Patent
`
`5,732,113
`
`Mar. 24, 1998
`
`Sheet 2 of 15
`
`Frequency
`
`FIG.2(PriorArt) Magnitude
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 3
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 3 of 15
`
`5,732,113
`
`pueqeseg
`
`SiigBeg
`
`-“LOLLO'S
`
`vOl
`
`aqawooauc
`
`cOl
`
`OOl
`
`
`
`(iy4Old)°
`
`Vis
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 4
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 4
`
`€
`

`

`aul
`
`U.S. Patent
`
`Uclt
`
`Mar. 24, 1998
`
`Sheet 4 of 15
`
`5,732,113
`
`
` OLLaIWZLIA.UZLLO11azehh|1WWL-N
`
` soquids|joquiAseeezloquids||joquis||atan1Ioeeaenngnnneneeeeeer1 jujoqués|ee|¢joqwdAs]
`
`
`(W)ZEE
`
`(MY10d)p“SIs
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 5
`
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 5 of 15
`
`5,732,113
`
`= ©Computation
`
`ho
`
`~ &
`S ©
`oO
`oOo =
`OE=LL
`
`Oo
`= ©
`Soy
`
`FIG.5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 6
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 6 of 15
`
`5,732,113
`
`Burures|
`
`Z‘besNd
`|‘besNd
`
`‘bas4“ON-UeAg
`
`
`
`‘bes4“ON-PPO
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 7
`
`Buiules|
`
`
`
`adA|joqwAs
`
`
`
`JequinyjoqwAs
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 7
`
`
`

`

`U.S. Patent
`
`5,732,113
`
`Sheet 7 of 15
`
`Mar. 24, 1998
`
`FIG.7 Amplitude
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 8
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 8 of 15
`
`5,732,113
`
`Number, k
`
`
`
` Frequency
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 9
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 9
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 9 of 15
`
`5,732,113
`
`Imaginary
`
`Real
`
`FIG. 9B
`
`Imaginary
`
`Ow
`
`Real
`
`FIG. 9A
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 10
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 10 of 15
`
`§,732,113
`
`°°°bfon)oo—
`
`
`
`TimingMetricM(d)
`
`Outside first symbol
`
`SNR (dB)
`
`FIG. 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 11
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 11 of 15
`
`5,732,113
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`
`
`TimingMetricM(d)
`
`-1
`
`-0.5
`
`0
`
`0.5
`
`1
`
`Timing Offset (symbols)
`
`FIG. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 12
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 12
`
`

`

`U.S. Patent
`
`uoneinbyuog
`
`
`
`uoneinbyuoyNeedPeAlsseypeywisuel)1800
`
`
`
`U0NI21105veaonoes,uolelJOQUINNuoyesnbyuodnByuog
`
`
`
`
`IngsayyeMenomlsBedeedAouanbai
`
`
`
`
`
`Mar. 24, 1998
`
`Sheet 12 of 15
`
`5,732,113
`
`
`
`
`
`[g-]eyeq[oJeveq[z-leieqZ-
`
`[oJeveq
`
`
`
`
`
`[L-Jeyeq[Lleyeq[L-leveq[-
`
`[pleyeq
`
`
`
`
`
`[oleyeq"[z]eyeq[olereq0[zjeveq
`
`
`
`[Llereq[Lereq|
`
`
`
`[zleieq[zjeeqz
`
`cL“Sid
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 13
`
`[z-]eyeq
`
`[g-Jeveqp-
`
`[L-leveq
`
`[.-Jeyeq¢-
`
`c-
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 13
`
`€
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 13 of 15
`
`5,732,113
`
`Correct
`
`OffsetMetricB(g)
`Carrier
`
`Incorrect
`
`SNR (dB)
`
`FIG. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 14
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 14
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 14 of 15
`
`5,732,113
`
`
`
`CarrierOffsetMetricB(g)
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`10 a:
`
`0
`
`g
`
`FIG. 14
`
`5
`
`10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 15
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 15
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 15 of 15
`
`5,732,113
`
`Accumulated
`
`Phase
`
`Rotation in Time
`Ts+Tg Due to
`
`Sampling Rate Offset
`
`FIG. 15
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 16
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 16
`
`

`

`5,732,113
`
`1
`TIMING AND FREQUENCY
`SYNCHRONIZATION OF OFDM SIGNALS
`
`FIELD OF THE INVENTION
`
`The present invention relates to a method and apparatus
`for the reception of orthogonal frequency division multi-
`plexed (OFDM) signals. More particularly, the invention
`concerns timing and frequency synchronization of an
`OFDM receiver to an OFDM signal to enable the OFDM
`receiver to accurately demodulate, decode, and recover data
`transmitted across an OFDM channel on the OFDM sub-
`carriers of the OFDM signal.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`2
`sub-carrier is typically assigned c,=0. Encoder 14 then
`passes the sequence of sub-symbols, along with any addi-
`tional zeroes that may be required for interpolation to
`simplify filtering, onto an inverse discrete Fourier trans-
`former (IDFT)or, preferably, an inverse fast Fourier trans-
`former (IFFT) 16.
`Upon receiving the sequence of OFDM frequency-
`domain sub-symbols from encoder 14, IFFT 16 performs an
`inverse fast Fourier transform on the sequence of sub-
`symbols. In other words, it uses each of the complex-valued
`sub-symbols, c,, to modulate the phase and amplitude of a
`corresponding one of 2N+1 sub-carrier frequencies over a
`symbol interval T,. The sub-carriers are given by e~?"*, and
`therefore, have baseband frequenciesof f,=k/T,, where k is
`the frequency number and is an integer in the range
`—-NSkSN.IFFT 16 thereby produces a digital time-domain
`OFDM symbol of duration T, given by:
`
`ceexp(-2nift
`= 2
`a) = pen exp(
`)
`
`OStST,
`
`°
`
`1. General Description of Transmission Using OFDM
`Orthogonal frequency division multiplexing (OFDM)is a
`robust technique for efficiently transmitting data over a
`channel. The technique uses a plurality of sub-carrier fre-
`quencies (sub-carriers) within a channel bandwidth to trans-
`mit the data. These sub-carriers are arranged for optimal
`bandwidth efficiency compared to more conventional trans-
`mission approaches, such as frequency division multiplex-
`As a result of this discrete-valued modulation of the
`ing (FDM). which waste large portions of the channel
`OFDMsub-carriers by frequency-domain sub-symbols over
`bandwidth in order to separate and isolate the sub-carrier
`symbolintervals of T, seconds, the OFDM sub-carriers each
`frequency spectra and thereby avoid inter-carrier interfer-
`display a sinc x=(sin x)/x spectrum in the frequency domain.
`ence (ICI). By contrast, although the frequency spectra of
`By spacing each of the 2N+1 sub-carriers 1/T, apart in the
`OFDM sub-carriers overlap significantly within the OFDM
`frequency domain, the primary peak of each sub-carrier’s
`channel bandwidth, OFDM nonetheless allows resolution
`sinc x spectrum coincides with a null of the spectrum of
`and recovery of the information that has been modulated
`every other sub-carrier. In this way, although the spectra of
`onto each sub-carrier. Additionally, OFDM is much less
`the sub-carriers overlap, they remain orthogonal to one
`susceptible to data loss due to multipath fading than other
`another. FIG. 2 illustrates the arrangement of the OFDM
`conventional approaches for data transmission because
`sub-carriers as well as the envelope of their modulated
`inter-symbol interference is prevented through the use of
`spectra within an OFDM channel bandwidth, BW,centered
`OFDM symbols that are long in comparison to the length of
`around a carrier frequency, f., Note that the modulated
`the channel impulse response. Also, the coding of data onto
`sub-carriersfill the channel bandwidth very efficiently.
`the OFDM sub-carriers can take advantage of frequency
`Returning to FIG. 1,
`the digital time-domain OFDM
`diversity to mitigate loss due to frequency-selective fading.
`symbols produced by IFFT 16 are then passed to a digital
`The general principles of OFDMsignal transmission can
`be described with reference to FIG. 1 which is a block
`signal processor (DSP) 18. DSP 18 performs additional
`spectral shaping on the digital time-domain OFDM symbols
`diagram of a typical OFDM transmitter according to the
`and also adds a cyclic prefix or guard interval of length T,
`prior art. An OFDM transmitter 10 receives a stream of
`to each symbol. The cyclic prefix is generally just a repeti-
`baseband data bits 12 as its input. These input data bits 12
`tion of part of the symbol. This cyclic prefix is typically
`are immediately fed into an encoder 14, which takes these
`longer than the OFDM channel
`impulse response and,
`data bits 12 in segments of B bits every T,+T, seconds,
`therefore, acts to prevent inter-symbol interference (ISI)
`where T, is an OFDM symbolinterval and T, is a cyclic
`between consecutive symbols,
`prefix or guard interval. Encoder 14 typically uses a block
`and/or convolutional coding scheme to introduce error-
`The real. and imaginary-valued digital components that
`make up the cyclically extended, spectrally-shaped digital
`correcting and/or error-detecting redundancy into the seg-
`ment of B bits and then sub-divides the coded bits into 2N
`time-domain OFDM symbols are then passed to digital-to-
`analog converters (DACs) 20 and 22, respectively. DACs 20
`sub-segments ofmbits. The integer m typically ranges from
`2 to 6.
`and 22 convert the real and imaginary-valued digital com-
`ponents of the time-domain OFDM symbols into in-phase
`In a typical OFDMtransmission system, there are 2N+1
`and quadrature OFDM analog signals, respectively, at a
`OFDM sub-carriers, including the zero frequency DC sub-
`conversion or samplingrate f.,,as determined by a clock
`carrier which is not generally used to transmit data since it
`circuit 24. The in-phase and quadrature OFDM signals are
`has no frequency and therefore no phase. Accordingly,
`then passed to mixers 26 and 28, respectively.
`encoder 14 then typically performs 2”-ary quadrature ampli-
`In mixers 26 and 28, the in-phase and quadrature OFDM
`tude modulation (QAM) encoding of the 2N sub-segments
`of m bits in order to map the sub-segments of m bits to
`signals from DACs 20 and 22 are used to modulate an
`predetermined corresponding complex-valued points in a
`in-phase intermediate frequency (IF) signal and a 90° phase-
`™-ary constellation. Each complex-valued point in the
`shifted (quadrature) IF signal, respectively, in order to
`constellation represents discrete values of phase and ampli-
`produce an in-phase IF OFDMsignal and a quadrature IF
`tude. In this way, encoder 14 assigns to each of the 2N
`OFDMsignal, respectively. The in-phase IF signal that is fed
`to mixer 26 is produced directly by a local oscillator 30,
`sub-segments of m bits a corresponding complex-valued
`2”-ary QAM sub-symbol c,=a,+jb,, where -NSkSN,in
`while the 90° phase-shifted IF signal that is fed to mixer 28
`order to create a sequence of frequency-domain sub-symbols
`is produced by passing the in-phase IF signal produced by
`that encodes the B data bits. Also,
`the zero-frequency
`local oscillator 30 through a 90° phase-shifter 32 before
`
`35
`
`45
`
`55
`
`65
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 17
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 17
`
`

`

`5,732,113
`
`3
`feeding it to mixer 28. These two in-phase and quadrature IF
`OFDM signals are then combined in combiner 34 to form a
`composite IF OFDMsignal. In some prior art transmitters,
`the IF mixing is performed in the digital domain using a
`digital synthesizer and digital mixers before the digital-to-
`analog conversion is performed.
`This composite IF OFDMsignal is then passed into radio
`frequency (RF) transmitter 40. Many variations of RF trans-
`mitter 40 exist and are well knownin theart. but typically,
`RF transmitter 40 includes an IF bandpassfilter 42, an RF
`mixer 44, an RF carrier frequency local oscillator 46, an RF
`bandpassfilter 48, an RF power amplifier 50, and an antenna
`52. RF transmitter 40 takes the IF OFDM signal from
`combiner 34 and uses it to modulate a transmit carrier of
`frequency f.,. generated by RF local oscillator 46, in order
`to produce an RP OFDM-modulated carrier that occupies a
`channel bandwidth, BM. Because the entire OFDM signal
`mustfit within this channel bandwidth, the channel band-
`width mustbe at least (1/T,)-(2N+1) Hz wide to accommo-
`date all the modulated OFDM sub-carriers. The frequency-
`domain characteristics of this RF OFDM-modulated carrier
`are illustrated in FIG. 2. This RF OFDM-modulated carrier
`is then transmitted from antenna 52 through a channel, to an
`OPDMreceiver in a remote location. In alternative embodi-
`ments of RF transmitter 40. the OFDM signal is used to
`modulate the transmit carrier using frequency modulation
`(FH). single-sideband modulation (SSB), or other modula-
`tion techniques. Therefore,
`the resulting RP OFDM-
`modulated carrier may not necessarily have the exact shape
`of the RP OPDM-modulatedcarrier illustrated in FIG.2 (i.e.
`the RF OPDM-modulated carrier might not be centered
`around the transmit carrier, but instead maylie to either side
`of it).
`In order to receive the OFDM signal and to recover the
`baseband data bits that have been encoded into the OFDH
`sub-carriers at a remote location, an OFDM receiver must
`perform essentially the inverse of all the operations per-
`formed by the OFDM transmitter described above. These
`operations can be described with reference to FIG. 3 which
`is a block diagram of a typical OPDM receiver according to
`the prior art.
`Thefirst element of a typical OFDM receiver 60 is an RF
`receiver 70. Like RF transmitter 40, many variations of RF
`receiver 70 exist and are well knownin theart, but typically,
`RF receiver 70 includes an antenna 72,a low noise amplifier
`(LNA) 74, an RF bandpassfilter 76, an automatic gain
`control (AGC)circuit 77, an RF mixer 78, an RF carrier
`frequency local oscillator 80, and an IF bandpassfilter 82.
`Through antenna 72, RF receiver 70 couples in the RF
`OFDM-modulated carrier after it passes through the chan-
`nel. Then, by mixing it with a receive carrier of frequency
`f,, generated by RF local oscillator 80, RF receiver 70
`downconverts the RF OFDM-modulated carrier to obtain a
`received IF OFDM signal. The frequency difference
`between the receive carrier and the transmit carrier contrib-
`utes to the carrier frequency offset, Af...
`This received IF OFDM signal then feeds into both mixer
`84 and mixer 86 to be mixed with an in-phase IF signal and
`a 90° phase-shifted (quadrature) IF signal, respectively, to
`produce in-phase and quadrature OFDM signals, respec-
`tively. The in-phase IF signal that feeds into mixer 84 is
`producedby an IF local oscillator 88. The 90° phase-shifted
`IF signal
`that feeds into mixer 86 is derived from the
`in-phase IF signal of IF local oscillator 88 by passing the
`in-phase IF signal through a 90° phase shifter 90 before
`feeding it to mixer 86.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`45
`
`55
`
`4
`The in-phase and quadrature OFDMsignals then pass into
`analog-to-digital converters (ADCs) 92 and 93, respectively,
`where they are digitized at a sampling rate f,_, as deter-
`mined by a clock circuit 94. ADCs 92 and 93 produce digital
`samples that form an in-phase and a quadrature discrete-time
`OFDM signal, respectively. The difference between the
`sampling rates of the receiver and that of the transmitter is
`the sampling rate offset, Af,=f.—fu_+
`The unfiltered in-phase and quadrature discrete-time
`OFDM signals from ADCs 92 and 93 then pass through
`digital low-passfilters 96 and 98, respectively. The output of
`lowpass digital filters 96 and 98 are filtered in-phase and
`quadrature samples, respectively. of the received OFDM
`signal. In this way, the received OFDM signal is converted
`into in-phase (q,) and quadrature (p,) samples that represent
`the real and imaginary-valued components, respectively, of
`the complex-valued OFDMsignal, r=q,+jp;. These in-phase
`and quadrature (real-valued and imaginary-valued) samples
`of the received OFDMsignal are then delivered to DSP 100.
`Note that in someprior art implementations of receiver 60,
`the analog-to-digital conversion is done before the IF mixing
`process. In such an implementation, the mixing process
`involves the use of digital mixers and a digital frequency
`synthesizer. Also note that in many prior art implementa-
`tions of receiver 60,
`the digital-to-analog conversion is
`performed after the filtering.
`DSP 100 performs a variety of operations on the in-phase
`and quadrature samplesof the received OFDM signal. These
`operations mayinclude: a).synchronizing receiver 60 to the
`timing of the symbols and data frames within the received
`OFDMsignal, b) estimating and correcting for the carrier
`frequency offset Af, of the received OFDM signal, c)
`removing the cyclic prefixes from the received OFDM
`signal, d) computing the discrete Fourier transform (DFT) or
`preferably the fast Fourier transform (FFT) of the received
`OFDM signal
`in order to recover the sequences of
`frequency-domain sub-symbols that were used to modulate
`the sub-carriers during each OFDM symbolinterval, and ¢)
`performing any required channel equalization on the sub-
`carriers. In some implementations, DSP 100 also estimates
`and corrects the sampling rate offset, Af_,. Finally, DSP 100
`computes a sequenceof frequency-domain sub-symbols.y,,
`from each symbol of the OFDMsignal by demodulating the
`sub-carriers of the OFDM signal by means of the FFT
`calculation. DSP 100 then delivers these sequences of sub-
`symbols to a decoder 102.
`Decoder 102 recovers the transmitted data bits from the
`sequences of frequency-domain sub-symbols that are deliv-
`ered to it from DSP 100. This recovery is performed by
`decoding the frequency-domain sub-symbols to obtain a
`stream of data bits 104 which should ideally match the
`stream of data bits 12 that were fed into the OFDM trans-
`mitter 10. This decoding process can include soft Viterbi
`decoding and/or Reed-Solomon decoding, for example, to
`recover the data from the block and/or convolutionally
`encoded sub-symbols.
`In a typical OFDMdata transmission system such as one
`for implementing digital television or a wireless local area
`network (WLAN), data is transmitted in the OFDM signal in
`groups of symbols known as data frames. This prior art
`concept is shown in FIG. 4 where a data frame 100 includes
`M consecutive symbols 112a, 1124, .
`.
`.
`, 112M, each of
`which includes a guard interval, T,, as well as the OFDM
`symbol interval, T,. Therefore, each symbol has a total
`duration of T,+T, seconds. Depending on the application,
`data frames can be transmitted continuously, such as in the
`broadcastof digital TV, or data frames can be transmitted at
`random times in bursts, such as in the implementation of a
`WLAN.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 18
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 18
`
`

`

`5,732,113
`
`5
`The transmission of data through a channel via an OFDM
`signals provides several advantages over more conventional
`transmission techniques. These advantages include:
`a) Tolerance to multipath delay spread. This tolerance is
`dueto the relatively long symbol interval T, compared
`to the typical time duration of the channel impulse
`response. These long symbol intervals prevent inter-
`symbol interference (ISI).
`b) Tolerance to frequency selective fading. By including
`redundancy in the OFDM signal, data encoded onto
`fading sub-carriers can be reconstructed from the data
`recovered from the other sub-carriers.
`
`c) Efficient spectrum usage. Since OFDM sub-carriers are
`placed in very close proximity to one another without
`the need to leave unused frequency space between
`them, OFDM can efficiently fill a channel.
`d) Simplified sub-channel equalization. OFDM shifts
`channel equalization from the time domain (as in single
`carrier transmission systems) to the frequency domain
`where a bank of simple one-tap equalizers can indi-
`vidually adjust for the phase and amplitude distortion
`of each sub-channel.
`
`¢) Good interference properties. It is possible to modify
`the OFDM spectrum to account for the distribution of
`power of an interfering signal. Also, it is possible to
`reduce out-of-band interference by avoiding the use of
`OFDMsub-carriers near the channel bandwidth edges.
`Although OFDM exhibits these advantages, prior art
`implementations of OFDM also exhibit several difficulties
`and practical limitations. The most importantdifficulty with
`implementing OFDM transmission systems is that of
`achieving timing and frequency synchronization between
`the transmitter and the receiver. There are three aspects of
`synchronization that require careful attention for the proper
`reception of OFDM signals.
`First, in order to properly receive an OFDM signal that
`has been transmitted across a channel and demodulate the
`symbols from the received signal, an OFDM receiver must
`determine the exact timing of the beginning of each symbol
`within a data frame. If correct timing is not known, the
`receiver will not be able to reliably remove the cyclic
`prefixes and correctly isolate individual symbols before
`computing the FFT of their samples. In this case, sequences
`of sub-symbols demodulated from the OFDM signal will
`generally be incorrect, and the transmitted data bits will not
`be accurately recovered.
`Equally important but perhaps more difficult than achiev-
`ing proper symbol timing is the issue of determining and
`correcting for carrier frequency offset, the second major
`aspect of OFDM synchronization. Ideally, the receive carrier
`frequency, f,,, should exactly match the transmit carrier
`frequency, f_,. If this condition is not met, however, the
`mis-match contributes to a non-zerocarrier frequency offset,
`Af, in the received OFDM signal. OFDM signals are very
`susceptible to such carrier frequency offset which causes a
`loss of orthogonality between the OFDM sub-carriers and
`results in inter-carrier interference (ICI) and a severe
`increase in the bit error rate (BER) of the recovered data at
`the receiver.
`Thethird synchronization issue of concern when imple-
`menting an OFDM communication system is that of syn-
`chronizing the transmitter’s sample rate to the receiver’s
`sample rate to eliminate samplingrate offset. Any mis-match
`between these two sampling rates results in a rotation of the
`2™-ary sub-symbol constellation from symbol to symbol in
`a frame. Although correcting for sampling rate offset is less
`
`10
`
`15
`
`30
`
`35
`
`45
`
`55
`
`6
`of a problem than that of determining symbol timing and
`correcting carrier frequency offset, uncorrected sampling
`frequency offset can contribute to increased BER.
`
`DESCRIPTION OF THE PRIOR ART
`
`In order to solve the above-mentioned synchronization
`problems associated with the proper reception OFDM
`signals, several synchronization and correction techniques
`have been previously suggested and developed.
`In U.S. Pat. No. 5.444.697, Leung et al. suggest a tech-
`nique for achieving timing synchronization of a receiver to
`an OFDM signal on a frame-by-frame basis. The method,
`however, requires that a plurality of the OFDM sub-carriers
`be reserved exclusively for data synchronization, thus reduc-
`ing the number of sub-carriers used for encoding and
`transmitting data. Furthermore, Leung does not suggest a
`technique for correcting the carrier frequency offset or
`sampling rate offset. Finally, Leung’s technique requires a
`loop-back to determine the phase and amplitude of each
`sub-channel, thereby rendering the technique unsuitable for
`broadcast applications such as digital TV.
`In U.S. Pat. No. 5,345,440, Gledhill et al. present a
`method for improved demodulation of OFDM signals in
`which the sub-carriers are modulated with values from a
`quadrature phase shift keying (QPSK) constellation.
`However, the disclosure does not teach a reliable way to
`estimate the symbol timing. Instead, assuming approximate
`timing is already known, it suggests taking an FFT of the
`OFDM signal samples and measuring the spread of the
`resulting data points to suggest the degree of timing syn-
`chronization. This technique, however, requires a very long
`time to synchronize to the OFDM signal since there is an
`FFT in the timing synchronization loop. Also, their method
`for correcting for carrier frequency offset assumes that
`timing synchronization is already known. Furthermore, the
`achievable carrier offset acquisition rangeis limited to half
`a sub-channel bandwidth. This very limited range for carrier
`offset correction is insufficient for applications such as
`digital television where carrier frequency offsets are likely to
`be as much as several tens of sub-carrier bandwidths.
`Finally, the disclosure does not teach a method for correcting
`for sampling rate offset.
`In U.S.Pat. No. 5,313,169, Foucheet al. suggest a method
`for estimating and correcting for the carrier frequency offset
`and s samplingrate offset of a receiver receiving an OFDM
`signal. The method requires the inclusion of two additional
`pilot frequencies within the channel bandwidth. The success
`of this method is limited because these pilot carriers are
`susceptible to multipath fading. Furthermore, Foucheet al.
`do not suggest a reliable method for determining symbol
`timing. They discuss subtracting the cyclic prefix from each
`symbol and then trying to find where there is a cancellation,
`but such a cancellation will not occur in the presence of
`carrier frequency offset. Also, because their synchronization
`loop includes a computationally complex FFT, synchroni-
`zation takes a long time. Additionally, because the method
`does not correct for carrier frequency offset before taking the
`FFTs, the method will suffer from inter-carrier interference
`between the sub-carriers,
`thus limiting its performance.
`Finally, the method also has a limited acquisition range for
`the carrier frequency offset estimation.
`In “A Technique for Orthogonal Frequency Division
`Multiplexing Frequency Offset Correction,” JEEE Transac-
`tions on Communications, Vol. 42, No. 10, October 1994,
`pp. 2908-14, and in “Synchronization Algorithms for an
`OFDM System for Mobile Communications.” /TG-
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 19
`
`Petitioner Sirius XM Radio Inc. - Ex. 1008, p. 19
`
`

`

`5,732,113
`
`7
`Fachtagung 130, Munich, Oct. 26-28, 1994, pp. 105-113,
`Mooseand Classen, respectively, discuss two techniques for
`OFDM synchronization. Both methods involve the repeti-
`tion of at least one symbol within an OFDM datafree.
`Moose’s method does not suggest a way to determine
`symbol timing while Classen’s method requires searching
`for a cancellation of two identical symbols after correcting
`for the phase shift introduced bythe carrier frequency offset.
`This technique requires the re-computation of a correction
`factor for every new set of samples and is,
`therefore,
`tremendously computationally complex. Furthermore. nei-
`ther author suggests an effective technique for estimating
`carrier frequency offset greater than one half of a sub-
`channel bandwidth. Consequently, the methods would not be
`suitable to the reception of OFDM digital TV signals.
`Classen does suggesta trial-and-error method for estimating
`carrier frequency offsets greater than one half of a sub-
`channel bandwidth by searching in increments of 0.1 sub-
`channel bandwidths. Such a method, however, is very slow
`and computationally complex, especially for offsets of sev-
`eral sub-carrier bandwidths.
`
`OBJECTS AND ADVANTAGES
`It is an object of the present invention to overcome many
`of the short-comings of the above-mentioned prior art syn-
`chronization techniques. In particular, it is an object of the
`invention to provide a robust and computationally simple
`method for synchronizing a receiver to an OFDMsignal
`which provides fast and accurate estimates of symbol
`timing, carrier frequency offset, and sampling rate offset,
`typically within the time duration of one data frame.It is a
`further object of the invention to provide a method that
`operates effectively with minimal overhead to the OFDM
`signal and does not require the use of additional hardware
`for generating and transmitting additional synchronization
`carrier frequencies, as is required by some of the prior art
`methods.
`to provide a method for carrier
`It
`is another object
`frequency offset estimation that is not limited to a finite
`range and that can determine offsets of many sub-channel
`bandwidths. Also, it is an object to provide such a method
`that avoids the use of an PFT in the timing synchronization
`estimate, thereby allowing very quick determination of the,
`correct timing point. It is a further object of the present
`invention to require only two FFTs during carrier frequency
`synchronization while still avoiding ICI. Finally, it is an
`object of the present invention to provide a low-complexity
`technique for tracking successive data frames in order to
`maintain synchronization indefinitely following the initial
`acquisition procedure.
`Accordingly, it is an object of the present invention to
`provide a robust, low-overhead, low-complexity method and
`apparatusfor the rapid acquisition and synchronization of an
`OFDMsignal at an OFDMreceiver. Specifically, several
`other objects of the present invention include:
`a) to provide a method for rapidly acquiring the symbol
`and frame timing of an OFDM signal, preferably within
`less than the time interval of two data frames, thereby
`allowing reception of the OFDM symbols transmitted
`in either continuous or burst data frames;
`b) to provide a method for rapidly estimating and cor-
`recting for the carrier frequency offset of an OFDM
`receiver, preferably within less than the time interval of
`two data frames,
`thereby allowing reception and
`demodulation of the OFDM symbols in a burst data
`frame without loss of orthogonality and a correspond-
`ing increase in BER;
`
`10
`
`15
`
`25
`
`30
`
`35
`
`45
`
`50
`
`35
`
`8
`¢) to provide a method for rapidly estimating and cor-
`recting for the sampling rate offset of an OFDM
`receiver, thereby allowing reception and demodulation
`of the OFDM symbols in a burst frame with minimized
`BER;
`d) to provide a method for continuously tracking the
`symbol and frame timing of an OFDM signal consist-
`ing of continuously transmitted data frames;
`e) to provide a method for continuously tracking and
`correcting for the carrier frequency offset of an OFDM
`receiver thereby allowing continuous reception of an
`OFDMsignal without loss of orthogonality between
`the sub-carriers and an corresponding increase in BER;
`f) to provide a method for continuously tracking and
`correcting the sampling rate offset of an OFDM
`receiver;
`g) to provide a low-complexity method and apparatus for
`all the above that requiresrelatively little computation;
`h) to provide a robust met