United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,732,113
`
`
`Schmidl et a].
`[45] Date of Patent:
`Mar. 24, 1998
`
`U8005732113A
`
`[S4] TIMING AND FREQUENCY
`SYNCERONIZATION 0F OFDM SIGNALS
`
`[‘75]
`
`Inventors: Timothy M. Schmidl; Donald C. Cox.
`
`Primary Emnfinerfigtephen Chin
`Assistant Wiser—Mohammad Ghayow
`Attorney Agent. or Finn—Lumen Intellectual Property
`Services
`
`[73] Assignee: Stanford Univetdty. Stanford. Calif.
`
`[2]] Appl- No: 666,237
`
`[22] Filed:
`
`Jun. 20, 1996
`
`5
`Int. Cl. ....... HML 7N0
`[51]
`[52] U18: Clo on“............u.uuuunnuuuuo-u 375555; 375854
`[58] Fleld of Search .......... 375.654. 355;
`3701206. 208
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`1111992 Moose .................................. 37052.1
`7,1993 Le Finch at al
`______ 370,20
`
`441995 Saito a 311......“
`m... 370119
`3,119.95
`..... 370119
`
`lltl995
`370r19
`.
`
`41'1996
`....... 370119
`5r1996
`. 3751295
`8’1996
`.u 370319
`911996
`3753206
`211997
`.. 370x206
`
`
`
`5,166,924
`5,223,025
`5,406,551
`5,444,69?
`5.471.464
`5,506,336
`5,521,943
`5,5”,812
`5,555,268
`5,612,335
`
`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-
`nation in less than two data frames. A first OFDM training
`symbol has only even-numbered sub-mien, and substan-
`tially no qulummcd sub_cm-flu5. an mangcmcnt that
`results in half-symbol symmetry. A second OFDM training
`symbol has even-ntnnbered sub-carriers difierentially 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-
`“in“ '1“ hm‘symm We"? °f “w fir“ CPD“ "mg
`symbol. Carrier frequency ofiset estimation is perfumed in
`“Sing “19 timing Emit: as “'6“ as a “flier W395“? 0533*
`metric which peaks at the correct value of earner frequency
`ofisel. 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
`
`Memory!
`Data
`
`Storage
`Buffer
`
`Computation
`
`Microprocessor/
`DSP Firmware for
`
`120
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 1
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 1 of 15
`
`5,732,113
`
`'I
`
`IIIIIIIIII|IIIIIIIIIII
`
`I
`
`O
`1'-
`
`ran-um.—-————————————u-———————___——__—..._.__________————___
`
`®8m..............V................mom33N1ma20mAE8EQ3E.mMmm3m9Em
`:79MEPIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIPI
`
`nu
`
`QEHmmom20
`
`vI
`
`IlIlIIIIiIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIlIIIIIII|I|II
`
`c2BE:F.9".
`
`CD,_
`
`<01.
`
`«u-,_
`
`n...————.-————_—_——_—————— ——————__————————————-—————_.|
`
`E
`
`ucmnmmmm.
`
`J5::5...
`
`gmman.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 2
`
`

`

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

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 3 of 15
`
`5,732,113
`
`ucmnwmmm
`
`BEEun—
`
`\i5..5.:
`
`#9.
`
`Nov
`
`oo_.
`
`OE
`
`:232...:n.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 4
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 4
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 4 of 15
`
`5,732,113
`
`05:.
`
` ENrrATEVNZ.CNFFONE.DNZ.
`
`
`“mm—L,M.272m69.566956...:632:6...m6956m_onE>mF.853u
`
`lllllllllllllllllllllllll\‘I‘.‘~"I’-IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`c23:5e.9".
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 5
`
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 5 of 15
`
`_
`
`5,732,113
`
`ED Computation
`
`I...
`
`~22
`89
`a)!!!
`83
`9E
`
`Q-LL
`90.
`.90)
`
`FIG.5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 6
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 6 of 15
`
`5,732,113
`
`
`99%2n.3mm21deniozemm.
`
`DEEEFmEEmfi.mag_ooE>m
`
`80me.59;52-qu
`
`59:5262:5
`
`N(
`
`‘0
`,—
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 7
`
`
`
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 7
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 7 of 15
`
`5,732,113
`
`FIG.7
`
`Amplitude
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 8
`
`

`

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

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 9 of 15
`
`5,732,113
`
`Imaginary
`
`Real
`
`FIG. QB
`
`Imaginary
`
`A Real
`
`FIG. 9A
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 10
`
`

`

`US. Patent
`
`Mar. 24, 1998
`
`Sheet 10 of 15
`
`5,732,113
`
`.0.0.0J"-O’)03
`
`MetricM(d)
`Timing
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 11
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 11 of 15
`
`5,732,113
`
`.09s:45-0')CO
`
`
`
`TimingMetricM(d)
`
`—1
`
`~05
`
`0
`
`0.5
`
`1
`
`Timing Offset (symbols)
`
`FIG. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 12
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 12
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 12 of 15
`
`5,732,113
`
`
`
`:3".._o=<
`
`5.6250
`
`5-359
`
`ESE_TEE
`
`_:93
`
`Emma
`
`gazesmzcoo
`
`25:9....22
`5:53:50
`
`3:262“.
`
`5.39.30
`
`3.38
`
`€98_738
`
`Esme
`
`.E98
`
`H-350
`
`:58
`
`.298
`
`£98
`
`£98
`
`NF.0."—
`
`H-350
`
`fl£98
`
`SEE
`
`598
`
`RES
`
`Sun
`
`Sun
`
`0026qu
`
`uoEEwcat.
`
`cozfizmtcoo
`:2559200
`
`35:32“.
`
`.3532
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 13
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 13 of 15
`
`5,732,113
`
`OffsetMetricB(g)
`Carrier
`
`Incorrect
`
`SNR (dB)
`
`FIG. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 14
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 14
`
`

`

`US. Patent
`
`Mar. 24, 1993
`
`Sheet 14 of 15
`
`5,732,113
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`
`
`CarrierOffsetMetric3(9)
`
`-10
`
`I
`
`-5
`
`o
`
`5
`
`10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 15
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 15
`
`

`

`US. 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. 1006, p. 16
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 16
`
`

`

`1
`
`2
`
`5,732,113
`
`TIMING AND FREQUENCY
`SYNCHRONIZA'I'ION 0F 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 OPDM
`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
`
`1. General Description of Transmission Using OFDM
`Orthogonal frequency division multiplexing (OFDM) is a
`robust technique for efliciently 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~
`ing (FDM). which waste large portions of the channel
`bandwidth in order to separate and isolate the sub-carrier
`frequency spectra and thereby avoid inter-carrier interfer.
`ence (ICI). By connast. although the frequency spectra of
`OFDM sub-carriers overlap significantly within the OFDM
`channel bandwidth. OFDM nonetheless allows resolution
`and recovery of the information that has been modulated
`onto each sub-carrier. Additionally. OFDM is much less
`susceptible to data loss due to multipath fading than other
`conventional approaches for data transmission because
`inter-symbol interference is prevented through the use of
`OFDM symbols that are long in comparison to the length of
`the channel impulse response. Also. the coding of data onto
`the OFDM sub-carriers can take advantage of frequency
`diversity to mitigate loss due to frequency-selective fading.
`The general principles of OFDM signal transmission can
`be described with reference to FIG. 1 which is a block.
`
`diagram of a typical OFDM transmitter according to the
`prior art. An OFDM nansmitter 10 receives a sham of
`baseband data bits 12 as its input. These input data bits 12
`are immediately fed into an encoder 14. which takes these
`data bits 12 in segments of B bits every T8+T, seconds,
`where T, is an OFDM symbol interval and T8 is a cyclic
`prefix or guard interval. Encoder l4 typically uses a block
`andfor convolutional coding scheme to introduce error-
`correcting audio: error-detecting redundancy into the seg-
`ment of B bits and then sub-divides the coded bits into 2N
`sub-segments of m bits. The integer m typically ranges from
`2 to 6.
`
`In a typical OFDM transmission system. there are 2N+l
`OFDM sub-carriers, including the zero frequency DC sub-
`carrier which is not generally used to n-ansmit data since it
`has no frequency and therefore no phase. Accordingly,
`encoder 14 then typically performs 2"'-ary quadrature ampli-
`tude modulation (QAM) encoding of the 2N sub-segments
`of to bits in order to map the sub-segments of in bits to
`predetermined corresponding complex-valued points in a
`“-ary constellation. Each complex-valued point in the
`constellation represents discrete values of phase and ampli-
`tude. In this way, encoder l4 assigns to each of the 2N
`sub-segments of in bits 9. corresponding complex-valued
`2"'-ary QAM sub-symbol ct=ak+jbp where —N§k§N. in
`meter to acute a sequence of frequency-domain sub-symbols
`that encodes the B data bits. Also,
`the zero-frequency
`
`sub-comer is typically assigned c0=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 (lDFl‘) or. preferably. an inverse fast Fourier trans-
`former (IFFI‘) 16.
`
`Upon receiving the sequence of OFDM frequency-
`domain sub-symbols from encoder 14. IFFI‘ 16 performs an
`inverse fast Fom'ier transform on the sequence of sub-
`symbols. In other words. it uses each of the complex-valued
`sub-symbols. ck. 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 cam. and
`therefore. have baseband frequencies of ffikfl‘, where k is
`the frequency number and is an integer in the range
`—N§k§N. [EFT 16 thereby produces a digital time-domain
`OFDM symbol of duration T, given by:
`N
`u[t)= r:- c “Pi-2W)
`N i
`cant:
`
`(1)
`
`As a result of this discrete-valued modulation of the
`OFDM sub-carries by frequency-domain sub-symbols over
`symbol intervals of T, seconds. the OFDM sub-carriers each
`display a sine x=(si.n nix spectrum in the frequency domain.
`By spacing each of the 2N+l sub-carriers lfl', apart in the
`frequency domain. the primary peak of each sub-carrier’s
`sine x spectrum coincides with a null of the spech of
`every other sub-carrier. In this way. although the specn-a of
`the sub-carriers overlap. they remain orthogonal to one
`another. FIG. 2 illustrates the arrangement of the OFDM
`sub-carriers as well as the envelope of their modulated
`spectra within an OFDM channel bandwidth. BW. centered
`around a carrier frequency. fa. Note that the modulated
`sub-carriers fill the channel bandwidth very efiiciently.
`Returning to FIG. 1.
`the digital time-domain OFDM
`symbols produced by [FFT 16 are then passed to a digital
`signal processor (DSP) 18. DSP 18 performs additional
`specn'al shaping on the digital time-domain DFDM symbols
`and also adds a cyclic prefix or guard interval of length Ts
`to each symbol. The cyclic prefix is generally just a repeti-
`tion of part of the symbol. This cyclic prefix is typically
`longer than the OFDM channel
`impulse response and.
`tltca'cfca’e. acts to prevent inter-symbol interference (151)
`between consecutive symbols.
`The real.and imaginary-valued digital components that
`make up the cyclically extended. spectrally-shaped digital
`time-domain OFDM symbols are then passed to digital-to-
`analog converters (DACs) 20 and 2.2. respectively. DACs 20
`and 22 convert the real and imaginary-valued digital com-
`ponents of the time-domain OFDM symbols into in-phase
`and quadrature OFDM analog signals. respectively. at a
`conversion or sampling rate fa,“ as determined by a clock
`circuit 24. The in-phase and quadrature OFDM signals are
`then passed to mixers 26 and 3, respectively.
`in mixers 26 and 28, the int-phase and quadranrre OFDM
`signals from DACs 20 and 22 are used to modulate an
`in-phase intermediate frequency (1F) signal and a 90° phase-
`shifted (quadrature) IF signal. respectively, in order to
`produce an in—phase IF OFDM signal and a quadrannc IF
`DFDM signal, respectively. The in-phase IF signal that is fed
`to mixer 26 is produced directly by a local oscillator 30.
`while the 90" phase-shifted IF signal that is fed to mixer 28
`is produced by passing the “in-phase IF signal produced by
`local oscillator 30 through a 90° phase-shine: 32 before
`
`S
`
`10
`
`15
`
`35
`
`45
`
`55
`
`65
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 17
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 17
`
`

`

`3
`
`5,732,113
`
`4
`
`feeding it to mixer 28. These two in-phase and quadramre IF
`OFDM signals are then combined in combiner 34 to form a
`composite IF OFDM signal. In some prior art transmitters,
`the ]F 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 OFDM signal is then passed into radio
`frequency (RF) transmitter 40. Many variations of RF trans-
`mitter 48 exist and are well known in the art. but typically.
`RF transmitter 40 includes an IF bandpass filter 42. an RF
`mixer 44. an RF carrier frequency local oscillator 46. an RF
`bandpass filter 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 can'ier of
`frequency fa, 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
`must fit within this channel bandwidth. the channel band-
`width must be at least (III‘,)-(2N+l) 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 calrier
`is then transmitted from antenna 52 through a channel. to an
`OFDM receiver in a remote location. In alternative embodi-
`ments of RF transmitter 40. the OFDM signal is used to
`modulate the transmit carrier using fi'equency modulation
`(FE). single-sideband modulation (588), or other modula-
`tion techniques. Therefore.
`the resulting RP OFDM-
`modulated carrier may not necessarily have the exact shape
`of the RP OFDM-modulated carrier illustrated in FIG. 2 (he.
`the RF OFDM-modulated carrier might not be centered
`around the transmit carrier. but instead may lie 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 OFDM receiver according to
`the prior art.
`The first element of a typical OFDM receiver 60 is an RF
`receiver 70. Like RF transrnittu' 40. many variations of RF
`receiver 10 exist andare well known in the art. but typically.
`RF receiver 70 includes an antenna '72. a low noise amplifier
`(LNA) 74. an RF bandpass filter 76. an automatic gain
`control (AGC) circuit 77. an RF mixer 1'8, an RF carrier
`frequent.)r local oscillator 80. and an IF bandpass filter 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
`fa, generated by RF local oscillator 80. RF receiver 78
`downoonverts the RF OFDM-modulated carrier to obtain a
`received IF OFDM signal. The frequency diiference
`between the receive carrier and the transmit carrier contrib-
`utes to the carrier frequency ofiset. Afr
`This received IF OFDM signal then feeds into both mixer
`81 and nfixer86tobemlxedwithan in-phaseIFsignaland
`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
`produced by 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
`
`4s
`
`55
`
`The in-pbase and quadrature OFDM signals then pass into
`analog-to-digital converters {ADCs} 92 and 93. respectively,
`where they are digitized at a sampling rate fa,” 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 difi'erenee between the
`sampling rates of the receiver and that of the n'ansmitter is
`the sampling rate ofiset. Affl=fdJ— :Lt‘
`The unfiltered in-phase and quadrature discrete-time
`OFDM signals from ADCs 92 and 93 then pass through
`digital low-pass filters 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 convuted
`into in-phase (qj) and quadrature (p9 samples that represent
`the real and imaginary-valued components. respectively. of
`the complex-valued OFDM signal. r,=qi+jp.-. These in-phase
`and quadrature (real-valued and imaginary-valued) samples
`of the received OFDM signal are then delivered to DSP 100.
`Note that in some prior 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 180 performs a variety of operations on the in-phase
`and quadrature samples of the received OFDM signal. These
`operations may include: a}.synchronizing receiver 68 to the
`timing of the symbols and data frames within the received
`OFDM signal. b) estimating and correcting for the carrier
`frequency ofi‘set dig. of the received OFDM signal. c)
`removing the cyclic prefixes from the received OFDM
`signal. :1) computing the discrete Fourier transits-m (DFI') or
`preferably the fast Fourier transform [FFI'J 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 symbol intervaL and e)
`performing any required channel equalization on the sub-
`catriers. In some implementations. DSP 109 also estimates
`and corrects the sampling rate ofiset. Aid. Finally. DSP 100
`computes a sequence of frequency-domain sub—symbols. y»
`from each symbol of the OFDM signal by demodulating the
`sub~carriers of the OFDM signal by means of the FFI‘
`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 andlor Reed-Solomon decoding. for example. to
`recover the data from the block and-‘or convolutionally
`encoded sub-symbols.
`In a typical OFDM data n-ansrnission 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. 1121;.
`.
`.
`.
`. 112M. each of
`which includes a guard interval. Tr as well as the OFDM
`symbol interval. '1‘, 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
`broadcast of digital TV. or data frames can be transmitted at
`random times in bursts. such as in the implementation of a
`WIAN.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 18
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, 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) Tolaance to multipath delay spread. This tolerance is
`due to 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 (131).
`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
`recova‘ed 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 efl‘iciently fill a channel.
`d) Simplified sub-channel equalization. OFDM shifts
`channel equalization ii'om 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.
`
`e) 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
`OFDM sub-carriers near the channel bandwidth edges.
`Although OFDM exhibits these advantages, prior art
`implementations of OFDM also exhibit several dificulties
`and practical limitations. The most important dificulty wilh
`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
`deter-mine 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 acairately recovered.
`Equally important but perhaps more difficult than achiev-
`ing proper symbol timing is the issue of determining and
`correcting for carrier frequency ofl'sct. 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
`rnis-matdt contributes to a non-zero canierfrequency cfl'set,
`rife. in the received OFDM signaL OFDM signals are very
`susceptible to such carrier frequency otfset which causes a
`loss of orthogonality between the OFDM sub-carriers and
`results in inter-carrier interference (1(1) and a severe
`increase in the bit error rate (BER) of the recovered data at
`the receiver.
`
`The third synchronization issue of concern when imple-
`menting an OFDM communication system is that of syn-
`chronizing the u'ansnnuer’s sample rate to the receiver‘s
`sample rate to eliminate sampling rate oifset. Any mis-match
`between these mo 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
`
`25
`
`30
`
`35
`
`45
`
`55
`
`6
`of a problem than that of determining symbol tiruing and
`correcting denier frequency offset, uncorrected sampling
`frequency ofiset can contribute to increased BER.
`
`DESCRIPTION OF THE PRIOR ARI‘
`
`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.691 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-caniers used for encoding and
`transmitting data. Furthennore. Leung does not suggest a
`technique for correcting the carrier frequency offset or
`sampling rate ofiset. 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 FFI' 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 tray 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 range is limited to half
`a sub-channel bandwidth. This very limited range for carrier
`offset correction is insufiicient for applications such as
`digital television where carrier frequency ofi’sets are likely to
`be as much as several tens of sub-carrim' bandwidths.
`Finally, the disclosure does not teach a method for correcting
`for sampling rate cfiset
`1n U.S. Pat. No. 5.3 13.169. Fouche et al. suggest a method
`for estimating and correcting for the carrier frequency offset
`and s sampling rate ofi'set 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. Faiche et aL
`do not suggest a reliable method for detamining symbol
`Liming. 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 [instance of
`can'ier frequency offset. Also, because their synchronization
`loop includes a computationally complex FFI‘. synchroni-
`zation takes a long time. Additionally. because the method
`does not correct for carrier frequency oifset before taking the
`FFI's. 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 olfset estimation.
`In “A Technique for Orthogonal Frequency Division
`Multiplexing Frequency Ofiset Correction." JEEE Transac-
`tions on Conmunicaticns, 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. 1006, p. 19
`
`Petitioner Sirius XM Radio Inc. - Ex. 1006, p. 19
`
`

`

`7
`
`8
`
`5,732,113
`
`Fachragung 130. Munich. Oct. 26—28. 1994. pp. 105—113.
`Moose and Classen. respectively. discuss two techniques for
`OFDM synchronization. Both methods involve the repeti-
`tion of at least one symbol within an OFDM data free.
`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 eta-reeling
`for the phase shift introduced by the carrier frequency offset.
`This technique requires the re-computation of a correction
`fador for every new set of samples and is.
`therefore.
`tremendously computationally complex. Furthermore. nei-
`ther author suggests an reflective 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 suggest a trial-and-enror method for estimating
`carrier frequency ofl‘sets 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.
`
`5
`
`10
`
`15
`
`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 OPDM signal
`which provides fast and accurate estimates of symbol
`timing. carrier frequency offset. and sampling rate oflset
`typitnrlly within the time duration of one data frame. It is a
`further object of the invention to provide a method that
`operates efiectively 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.
`
`25
`
`30
`
`35
`
`to provide a method for carrier
`is another object
`It
`frequency offset estimation that is not limited to a finite
`range and that can determine ofi'sets of many sub-channel
`bandwidths. Also. it is an object to provide such a method
`that avoids the use of an PET 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 hacking 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
`apparatus for the rapid acquisition and synchronization of an
`OFDM signal at an OFDM receiver. 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;
`
`45
`
`SD
`
`55
`
`b) to provide a method for rapidly estimating and cor-
`recting for the carrier frequency ofiset of an OFDM
`receiva: 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 ctr-respond-
`ing increase in BER:
`
`65
`
`c) to provide a method for rapidly estimating and cor-
`recting for the sampling rate offset of an OFDM
`receiver. thereby allowing reception and demodulation
`oftheOFDMsymbolsinaburstframewithminimized
`BER;
`
`d) to provide a method for continuously tracking the
`symbol and frame timing of an OFDM signal consist-
`ing of continuously nausmitted data frames;
`e) to provide a method for continuously tracking and
`correcting for the carrier frequency ofl’set of an OFDM
`receiver thereby allowing continuous reception of an
`OFDM signal 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 lo