`Leung et al.
`
`(56)
`
`73 Assignee:
`
`54 METHOD AND APPARATUS FOR FRAME
`SYNCHRONIZATION IN MOBILE OFDM
`DATA COMMUNICATION
`75 Inventors:
`Cybil S. Leung, Richmond; William
`D. Warner, Maple Ridge, both of
`Canada
`The University of British Columbia,
`Vancouver, Canada
`21 Appl. No.: 104,563
`22 Filed:
`Aug. 11, 1993
`51l Int. Cl. .............................................. H04J 11/00
`52 U.S. Cl. ..................................... 370/19; 370/69.1;
`370/100.1; 375/362
`58 Field of Search .................... 370/69.1, 20, 21, 23,
`370/70, 74, 50, 121, 19, 100.1, 74; 375/98, 111,
`97, 38; 455/59, 71, 54.1
`References Cited
`U.S. PATENT DOCUMENTS
`4,101,738 7/1978 Bellanger et al. ..................... 370/74
`4,438,511 3/1984 Baran ....................
`... 370/19
`4,847,880 7/1989 Karmerman et al. .
`... 375/111.
`4,881,241 11/1989 Pommier et al. .....
`... 375/38
`5,012,491 4/1991 Iwasaki .............
`... 375/97
`5,063,574 11/1991 Moose ................................... 375/27
`5,170,413 12/1992 Hess et al. ............................. 375/38
`5,191,576 3/1993 Prommier et al. .................... 370/18
`5,228,025 7/1993 Le Floch et al. ..................... 370/20
`5,274,629 12/1993 Helard et al. ......................... 375/38
`FOREIGN PATENT DOCUMENTS
`O008521 3/1980 European Pat. Off. .
`0529421A2 3/1993 European Pat. Off. .
`OTHER PUBLICATIONS
`B. Hirosaki, A 19.2 kbps voiceband data modem based
`on orthagonally multiplexed QAM techniques, 1985,
`pp. 21.1.1-21.1.5.
`W. E. Keasler, Reliable Data Communication Over the
`Voice Bandwidth Telephone Channel Using Ortha
`gonal Frequency Division Multiplexing, University of
`Illinois, 1982.
`P. H. Moose, Differential modulation and demodulation
`
`US005444697A
`Patent Number:
`11
`(45). Date of Patent:
`
`5,444,697
`Aug. 22, 1995
`
`of multi-frequency digital communications signals, in
`Milcom 90, pp. 273-277 or 12.4.1-12.4.5, Oct., 1990.
`E. F. Casas and C. Leung, A simple digital fading simu
`lator for mobile radio, IEEE Transactions on Vehicular
`Technology, vol.39, pp.205-212, Aug., 1990.
`P. G. Moore and E. A. C. Shirley, Standard Statistical
`Calculations. New York: John Wiley & Sons, 1972.
`(List continued on next page.)
`Primary Examiner-Melvin Marcelo
`Assistant Examiner-Chau T. Nguyen
`Attorney, Agent, or Firm-Oyen Wiggs Green & Mutala
`57
`ABSTRACT
`A method and apparatus are disclosed for achieving
`symbol (frame) synchronization of digital data in an
`OFDM channel such as an OFDM/FM radio link. The
`method and apparatus are suitable for use in a pure
`ALOHA environment because synchronization is
`achieved on a frame-by-frame basis. The required band
`width overhead is less than 10%. The bit-error-rate
`performance achievable with this technique is within
`1.5 dB of the performance assuming ideal synchroniza
`tion. The method and apparatus provide a three-stage
`synchronization process. First the onset of an ODFM
`frame is detected. Second, coarse synchronization is
`achieved by sampling the received signal, and measur
`ing the correlation between the received signal and a
`reference signal. Coarse synchronization provides syn
`chronization to within -t- sample period. The correla
`tion is preferably carried out in the frequency domain
`after carrying out a Fast Fourier Transform on the
`sampled signal data. Third, synchronization is achieved
`by calculating the time-shift between the coarse syn
`chronization point and the actual synchronization point
`and using the calculated time shift to determine the
`phase correction to apply to each data carrying sub-car
`rier. Finally the transmitted data is recovered by decod
`ing the information obtained about the phase and ampli
`tude of the data-carrying sub-carriers.
`
`16 Claims, 19 Drawing Sheets
`
`
`
`Synchronization
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 1
`
`
`
`5,444,697
`Page 2
`
`OTHER PUBLICATIONS
`D. C. Cox, A Radio System proposal for Widespread
`Low-Power Tetherless Communications, IEEE Trans
`actions on Communication, vol. 39, pp.324-335, Feb.,
`1991.
`L. J. Cimini, Analysis and simulation of a digital mobile
`channel using orthogonal frequency division multiplex
`ing, IEEE Transactions on Communications, vol. CO
`M-33, pp. 665-675, Jul. 1985.
`E. Casas and C. Leung, OFDM for Data Communica
`tion over Mobile Radio FMChannels, Part I: Analysis
`and Experimental Results, IEEE Transactions on Com
`munications, vol.39, pp. 783–793, May 1991.
`B. R. Salzberg, Performance of an efficient parallel data
`transmission system, IEEE Transactions on Communi
`cations Technology, vol. COM-15, pp. 805-811, Dec.
`1967.
`S. B. Weinstein and P. M. Egert, Data Transmission by
`frequency-division multiplexing using the discrete Fou
`
`rier transform, IEEE Transactions on Communications
`Technology, vol. COM-19, pp. 628-634, Oct., 1971.
`J. A. C. Bingham, Multicarrier modulation for data
`transmission: An idea whose time has come, IEEE
`Communications Magazine, pp. 5-14, May, 1990.
`Electronic Industries Association, Minimum standards
`for land mobile communiction FM or PM receivers,
`25-947 MHz, Feb. 1970. EIA Standard RS-152-B.
`Electronic Industries Association, Minimum standards
`for land mobile communication FM or PM receivers,
`25-947 MHz, Jan. 1982. EIA Standard RS-204-C.
`Electronic Industries Association, Minimum standards
`for portable/personal radio transmitters, receivers, and
`transmitter/receiver combination land mobile commu
`nications FM or PM equipment, 25-1000 MHz, May
`1979. EIA Standard RS-316-B.
`Abraham Peled and Antonio Ruiz, Frequency Domain
`Data Transmission using Reduced Computational Com
`plexity Algorithms, ICASSP 80 Proceedings, vol. 3 of 3,
`2 May, 1980964-967.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 2
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 1 of 19
`
`5,444,697
`
`
`
`20-
`
`22 i
`:
`
`3
`2
`
`24
`
`Serial Digital
`Data input
`
`Serial Digital
`Data Output
`
`-- Data Flow -->
`
`Decoding
`
`- 70
`
`Pale
`Serial
`
`7;
`
`De-emphasis
`
`- - - - - - - - (-7- - - - - -
`
`Channel
`
`Equalization
`
`FM
`Transmitte
`
`FM Fading
`Channel
`
`FM
`Receiver
`
`-----------------------------------
`
`-
`: 64
`:
`
`FF
`
`Parallel
`to
`Serial
`
`DSP
`
`Gain
`
`
`
`Parallel
`
`LPF HPF
`
`LPF
`Fifter
`
`DSP
`Gain
`
`DIA
`Conversion
`
`:
`
`53
`
`61
`
`AVD
`Conversion
`
`FIGURE
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 3
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 2 of 19
`
`5,444,697
`
`102
`
`
`
`103
`
`To microphone
`input of
`COM-2AT
`
`S1 - Manual Switch S2- Voltage Controlled Switch
`
`FIGURE 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 4
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 3 of 19
`
`5,444,697
`
`
`
`Carrier with modulation
`
`Carrier without modulation
`
`-25
`
`O
`
`50
`
`75
`
`25
`IF SNR (dB)
`
`FIGURE 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 5
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 4 of 19
`
`5,444,697
`
`
`
`0.5
`
`F SNR = 10dB, fc = 10Hz
`
`FIGURE 4A
`
`s
`o
`c
`
`FIGURE 4B
`
`s
`
`e
`Cs
`Z
`
`O
`
`384
`256
`128
`Sub-Channel Number
`
`512
`
`1.OE-01
`
`IF SNR = 10dB, fc = 10Hz
`
`1.OE-03
`
`100
`
`Sub-Channel Number
`
`1000
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 6
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 5 of 19
`
`5,444,697
`
`FIGURE 5A
`
`vs S
`
`0.5
`
`
`
`0.4
`
`0.3
`
`0.2
`
`0.
`
`O
`O
`
`F SNR = 10dB, fc = 10Hz
`
`384
`256
`28
`Sub-Channel Number
`
`512
`
`1.OE-01
`
`se
`= 10
`F
`F SNR
`dB, fc = 10Hz
`
`FIGURE 5B
`
`5
`S
`i Gd
`2
`
`O
`2
`
`OE-02
`
`W MN W
`
`1.OE-03
`100
`
`Sub-Channel Number
`
`1000
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 7
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 6 of 19
`
`5,444,697
`
`
`
`FIGURE 6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 8
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 7 of 19
`
`5,444,697
`
`0.5
`
`
`
`O
`
`0.5
`
`O
`in-Phase
`
`FIGURE 7
`
`O.5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 9
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 8 of 19
`
`5,444,697
`
`15 sync tones, id=10Hz -e--
`18 sync tones, fc-10Hz -e-
`21 sync tones, fc-10Hz - A -
`21 synctones, fcis-20Hz - - -A ---
`required performance re-r
`
`OE-00
`
`
`
`OE-01
`
`1.OE-02
`
`OE-03
`
`10E-04
`
`OE-05
`OE
`
`10
`
`25
`
`15
`2O
`IF SNR (dB)
`
`FIGURE 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 10
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 9 of 19
`
`5,444,697
`
`Start
`Phase
`
`
`
`Phase
`Coarse
`Synchronization
`
`
`
`Phase
`
`Phase
`Fine
`Synchronization
`
`FIGURE 9
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 11
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 10 of 19
`
`5,444,697
`
`
`
`FIGURE 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 12
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 11 of 19
`
`5,444,697
`
`1.OE-00
`
`
`
`OE-01
`
`1.OE-02
`
`1.OE-03 35
`
`Threshold
`
`FIGURE 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 13
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 12 of 19
`
`5,444,697
`
`1.OE-00
`
`
`
`10E-O1
`
`:
`
`f
`
`OE-02
`
`IF SNR = 25dB, th=0.15 -
`F SNR = 20dB, th=0.18 - - - - - - - - -
`F SNR = 15dB, th=021 - - - - - - -
`IF SNR = 10dB, th=0.25 -------------------
`
`-750
`
`O
`-250
`-500
`Detection Location Prior to Sync (in Sample Periods)
`
`250
`
`FIGURE 12
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 14
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 13 of 19
`
`5,444,697
`
`1.OE-00
`
`
`
`1.OE-0
`
`i
`
`... IN
`II.
`
`IF SNR = 25dB, fc-50Hz -
`IFSNR = 25dB, fod-20Hz - - - - - - - - -
`IF SNR = 10dB, fod-20Hz - - - - - - -
`F SNR = 10dB, fcd=50Hz ...................
`
`1.OE-02
`
`1.OE-04
`-750
`
`w
`O
`-250
`-500
`Detection Location Prior to Sync (in Sample Periods)
`FIGURE 13
`
`250
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 15
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 14 of 19
`
`5,444,697
`
`
`
`Data
`index
`Calculator
`
`interpolating
`Fiter
`
`FIGURE 14
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 16
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 15 of 19
`
`5,444,697
`
`Amplitude -
`Group Delay ------------------
`
`200
`
`
`
`150
`
`100
`
`0.75
`
`O 5
`
`0.25
`
`O
`
`64
`
`128
`
`320
`256
`192
`OFDM Sub-channel index
`
`384
`
`448
`
`512
`
`FIGURE 15
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 17
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 16 of 19
`
`5,444,697
`
`
`
`
`
`Hardware
`Equalizer
`
`Optimal
`Synchronizer
`
`FIGURE 16
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 18
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 17 of 19
`
`5,444,697
`
`OE-00
`
`
`
`1.OE-0
`
`1.OE-02
`
`10E-03
`
`OE-04
`
`Asymptote for fc = 10 Hz -------------------
`fo = 10 Hz -e-
`fod = 20 Hz - - - - - - -
`
`F SNR - 10dB
`
`F SNR = 5dB
`
`- - - - - - X-----------------------------...- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`M
`N- N
`F SNRs 25c B
`
`A
`
`OE-05
`
`O
`
`5
`O
`15
`Number of Synchronization Tones
`
`20
`
`FIGURE 17
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 19
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 18 of 19
`
`5,444,697
`
`
`
`F SNRs 25GB -e-
`F SNR 20GB -A-
`F SNR - 150B --
`F SNR 10GB -e-
`Requirement --------------
`ideal sync -------
`
`O
`
`15
`10
`5
`Number of Synchronization Tones
`
`20
`
`FIGURE 18
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 20
`
`
`
`U.S. Patent
`
`Aug. 22, 1995
`
`Sheet 19 of 19
`
`5,444,697
`
`Signal Flow
`
`------.
`
`Power
`Spliter/Combiner
`Mini-Circuits
`Model ZSC-2-1
`RF Attenuator
`Kay Model 437A
`OO o O Orb-e
`
`COM-2AT
`Receiver
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Baseband Modulating
`Signat
`
`
`
`
`
`
`
`Fading
`Channel
`Control
`
`
`
`Rayleigh Fadin
`Kayleig
`9 :
`: Channel Simulator:
`
`Baseband Demodulated
`Signal
`
`Power Amplifier
`Mini-Circuits
`Model ZHL-2-8
`
`FIGURE 19
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 21
`
`
`
`1.
`
`METHOD AND APPARATUS FOR FRAME
`SYNCHRONIZATION IN MOBILE OFDM DATA
`COMMUNICATION
`
`5,444,697
`2
`gated through water, analog signals being transmitted
`through a wire such as a telephone line, AM, FM, or
`Single Side Band (SSB) radio signals. OFDM/FM is
`particularly attractive because it can be implemented by
`retrofitting existing FM communication systems.
`In OFDM a block of bits is transmitted in parallel
`through a channel comprising a number of sub-carrier
`frequencies. The sub-carrier frequencies are chosen to
`be spaced in frequency from each other by a multiple of
`the symbol rate. That is, if the OFDM symbol duration
`is T seconds, the sub-carrier frequency spacing is 1/T
`Hz. With this frequency spacing, the sub-carriers are
`orthogonal over one symbol interval.
`Data to be transmitted are grouped into blocks of K
`bits. Each block of K bits is encoded, as is further de
`scribed below, and transmitted as a single data frame.
`The block of K bits is generally divided into smaller
`groups, each Smaller group usually containing between
`2 and 5 bits. Each smaller group is assigned to one sub
`carrier frequency. The phase and magnitude of the
`sub-carrier at that frequency are then set to values de
`termined by the data represented by the small group of
`bits. The encoding scheme is chosen to provide at least
`2 discrete signal points differentiated from each other
`in phase and/or magnitude where m is the number of
`bits assigned to the sub-carrier. For example, each of the
`2” possible combinations of the m bits assigned to a
`sub-carrier frequency may be assigned to one of the 2m
`signal points in a 2-QAM (Quadrature Amplitude
`Modulation) constellation. The number of bits mas
`signed to each sub-carrier can vary from one sub-carrier
`to the next. Of course, other encoding schemes besides
`QAM are also possible.
`The transmitted signal is received by a receiver. For
`each sub-carrier, the transmitted information is ex
`tracted by measuring the phase and amplitude of each
`data-carrying sub-carrier and determining which point
`in the 2-QAM constellation is closest to the signal
`point corresponding to the received sub-carrier. This
`signal point then identifies the m-bit data sequence
`transmitted on that sub-carrier. The original Kbit block
`of data can then be reconstructed by combining the bits
`of data recovered from each sub-carrier.
`Because information is encoded in the phase of the
`transmitted signal it is necessary to provide a means for
`synchronizing the received signal with the transmitted
`signal. Furthermore, particularly in a pure ALOHA
`environment, it is necessary to synchronize each
`OFDM frame independently. In a pure ALOHA envi
`ronment the receiver does not know when a data frame
`will be transmitted. A data frame may be transmitted at
`any random time. Therefore, in a pure ALOHA envi
`ronment the receiver cannot rely on information pro
`vided in previously received or subsequently received
`data frames for obtaining synchronization information
`for recovering data from a received data frame. Each
`data frame must carry its own synchronization informa
`tion. Because of this limitation, it is difficult using prior
`art techniques known to the inventors to provide effi
`cient OFDM communications channel in a pure
`ALOHA environment. As the available spectrum is
`limited, any synchronization scheme should have a low
`bandwidth overhead.
`Synchronization schemes devised for parallel
`(OFDM) transmission over telephone channels have
`been disclosed in Hirosaki, A 19.2 kbps voiceband data
`modem based on orthogonally multiplexed QAM tech
`
`FIELD OF THE INVENTION
`This invention relates to a method and apparatus for
`synchronizing data frames being transmitted over an
`Orthogonal Frequency Division Multiplexing (OFDM)
`10
`channel such as an OFDM/FM radio link. The method
`and apparatus have particular application for communi
`cating with mobile data receivers in an asynchronous
`pure ALOHA system in an urban environment where
`signal fading is a problem.
`15
`BACKGROUND OF THE INVENTION
`Digital communication with mobile receivers is be
`coming increasingly significant with the proliferation of
`cellular telephones and mobile data terminals in our
`society. This trend is likely to continue. Some advan
`20
`tages of digital communication over analog communi
`cation are: Improved utilization of the radio spectrum;
`Increased reliability in communicating information
`which is very sensitive to channel errors; Direct access
`to computerized databases; The relative ease of protect
`25
`ing confidentiality and integrity by the use of encryp
`tion techniques; and Integration of voice and data ser
`VCCS.
`In most urban and many suburban areas, a major
`obstacle to achieving efficient and reliable data commu
`30
`nication over a VHF or UHF mobile radio channel is
`multipath propagation. Multipath propagation results in
`severe and rapid fluctuations in the received signal
`strength as the mobile receiver is moved. The duration
`of a fade depends on the velocity of the receiver and is
`typically on the order of a few milliseconds.
`The rate of fluctuation in the strength of the received
`signal is characterized by the Doppler rate f which is
`given by fisfv/c, where f is the carrier frequency, v
`is the vehicle speed, and c is the velocity of light.
`The variation in amplitude of a received fading signal
`is well approximated by a Rayleigh distribution over
`short distances of a few tens of meters. Consequently,
`fading caused by multipath propagation of a signal is
`called Rayleigh fading. Over larger distances, shadow
`45
`ing of the received signal by hills and other large obsta
`cles results in a log-normal variation in the mean of the
`Rayleigh distribution. Rayleigh fading imposes severe
`constraints on digital communication.
`In a conventional serial modulation scheme data bits
`50
`are transmitted over a channel sequentially. If a deep
`fade occurs during the transmission of such a signal then
`the bits which are transmitted during the deep fade may
`not be received. This problem can be reduced by trans
`mitting a data frame containing a block of bits in paral
`55
`lel, each at a low baud rate so that the time taken to
`transmit the frame is long (typically, for example, on the
`order of a fraction of a second) relative to the expected
`duration of a fade. The effect of a fade is then spread out
`over many bits. Rather than a few adjacent bits being
`completely destroyed by a fade, all of the bits in the
`frame are slightly affected by a fade which occurs dur
`ing the time that the frame is being transmitted.
`A good scheme for transmitting a block of bits in
`parallel over a channel is orthogonal frequency division
`65
`multiplexing (OFDM). OFDM may be used in many
`different types of data channel. The data channel may
`comprise, for example, acoustic signals being propa
`
`35
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 22
`
`
`
`5
`
`25
`
`35
`
`5,444,697
`3
`4.
`niques, IEEE International Conference on Communica
`h. applying the time-shift to the second group of
`frequency sub-carriers; and
`tions, 1985, Chicago Ill; Keasler, Reliable data commu
`nication over the voice bandwidth telephone channel
`i. decoding the data.
`using orthogonal frequency division multiplexing, Ph.
`The invention also provides a method for recovering
`D. Thesis, University of Illinois at Urbana-Champaign,
`data from a transmitted OFDM signal, the signal com
`prising a plurality of data sub-carriers, a plurality of
`1982 and Baran, U.S. Pat. No. 4,438,511. However,
`synchronization sub-carriers, and phase-encoded digital
`these schemes rely on several consecutive frames to
`maintain correct timing and do not meet the require
`data associated with the data carrying sub-carriers. The
`ment that synchronization is achieved for each frame
`method comprises the steps of:
`individually.
`a monitoring to detect the start of the signal;
`b, when the signal start is detected, taking samples of
`Moose, Differential modulation and demodulation of
`multi-frequency digital communications signals MIL
`the signal at a frequency of at least twice the fre
`COM 90, pp. 273-277, October 1990 discloses a syn
`quency of any of the sub-carriers for a fixed time
`period;
`chronization technique for use in mobile satellite com
`munications. In this technique, a synchronization frame
`c. storing the samples in a data buffer;
`15
`is used to provide synchronization for a group of fol
`d, taking groups of N consecutive ones of the samples
`lowing data frames.
`and, for each of the groups, calculating the correla
`The performance of a synchronization technique can
`tion between the group and a reference signal;
`be measured by observing the frequency of false alarms,
`e. detecting a one of the groups for which the correla
`mis-detections and bad synchronizations. A false alarm
`tion is greatest;
`occurs if the synchronization algorithm indicates the
`f, deriving the phase and amplitude of each of the
`presence of a data block when none is present. A mis
`data-carrying sub-carriers in the signal by calculat
`detection occurs if the synchronization algorithm does
`ing the fast fourier transform of the one of the
`not detect the presence of a data block when one is
`groups;
`present. A bad synchronization occurs if the synchroni
`g, adding a phase angle coit to each of the data-car
`zation algorithm detects the presence of a data block
`rying sub-carriers where coi is the frequency of the
`when one is present, but does not correctly synchro
`sub-carrier, and T is a time-shift to maximize the
`nize. Bad synchronization occurs when the signal is
`correlation of the synchronization sub-carriers
`distorted enough to prevent proper synchronization,
`with the reference signal; and
`... h. decoding the data from the phases and amplitudes
`but not so distorted as to cause a mis-detection. A cor
`30
`rect synchronization occurs if the synchronization algo
`of the data-carrying sub-carriers.
`rithm detects the presence of a data block when one is
`Another aspect of the invention provides a receiver
`present and correctly synchronizes to the data block.
`for recovering data from a transmitted OFDM signal,
`Preferably a synchronization system should perform
`the signal comprising a plurality of data sub-carriers, a
`sufficiently well that inaccuracy in the synchronization
`plurality of synchronization sub-carriers, and phase
`procedure is not the major factor limiting the achiev
`encoded digital data associated with the data carrying
`sub-carriers, the receiver comprising:
`able bit-error-rate (BER). That is, the BER of the com
`a. a radio frequency receiver having an audio fre
`munication channel should be limited by the OFDM
`modulation technique rather than by the synchroniza
`quency output;
`tion procedure. For example, in designing the synchro
`b. threshold detection means for detecting when a
`nization scheme, the target probability of false alarm,
`radio signal is being received by the receiver;
`mis-detection or bad synchronization may be set equal
`c. analog to digital conversion means for taking digi
`to the BER of the OFDM/FM system given ideal syn
`tal samples of the audio frequency output at a sam
`pling frequency;
`chronization. This ensures that the BER with the syn
`chronization procedure does not exceed twice the BER
`d. data buffer means for storing the digital samples;
`45
`given ideal synchronization.
`e. correlation detection means for providing an out
`put representative of the correlation between
`SUMMARY OF THE INVENTION
`groups of N sequential ones of the stored digital
`The invention provides a method for communicating
`samples and a reference signal;
`from a transmitter to a receiver digital data comprising
`f. peak detection means for monitoring the output of
`a series of data elements. The method comprises the
`the correlation detector means and detecting a
`steps of:
`peak in the output;
`a providing a plurality of orthogonal frequency sub
`g. data index calculating means associated with the
`carriers;
`correlation detection means and the peak detection
`b. reserving a first group of the frequency sub-carri
`means for providing a pointer to the start of a se
`ers for synchronization tones having predeter
`lected one of the groups of N sequential stored
`digital samples corresponding to the peak;
`mined phases and amplitudes;
`c. encoding the data in the phases of a second group
`h, calculation means for:
`of the frequency sub-carriers;
`i. calculating estimated phases and amplitudes of
`d. simultaneously broadcasting the first and second
`the data-carrying sub-carriers by calculating the
`groups of frequency sub-carriers for a predeter
`fourier transform of a group of the stored digital
`mined time period;
`samples identified by the pointer;
`e. receiving the frequency sub-carriers at the re
`ii. calculating a time-shift to maximize the correla
`ceiver;
`tion between the reference signal and the group
`f. measuring the phases of the first group of the fre
`of stored digital samples from the estimated pha
`quency sub-carriers;
`ses;
`g. calculating a time shift from the measured phases
`iii. calculating corrected phases of the data-carry
`of the first group of frequency sub-carriers;
`ing sub-carriers by calculating and adding to the
`
`65
`
`50
`
`55
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 23
`
`
`
`10
`
`15
`
`20
`
`5,444,697
`5
`6
`estimated phases phase-shifts resulting from the
`ing, Ph.D. Thesis, University of Illinois at Urbana
`time-shift;
`Champaign, 1982, Cimini Jr. Analysis and simulation of
`i. decoding means for recovering the phase-encoded
`a digital mobile channel using orthogonal frequency
`digital data from the corrected phases; and
`division multiplexing, IEEE Transactions on Commu
`j. a data output.
`nications, No. 7, July, 1985, p. 665, Weinstein and Ebert,
`Data transmission by frequency-division multiplexing
`BRIEF DESCRIPTION OF THE DRAWINGS
`using the discrete fourier transform, IEEE Transactions
`Preferred embodiments of the invention will now be
`on Communications Technology, vol. COM-19, page
`described with reference to the following drawings in
`628, October, 1971 and Casas and Leung, OFDM for
`which:
`Data Communication over Mobile Radio FM Channels,
`FIG. 1 is a block diagram of an OFDM/FM channel;
`Part I: Analysis and Experimental Results, IEEE Trans
`FIG. 2 is a schematic diagram of a switch for energis
`actions on Communications, vol. 39, page 783, May,
`ing a radio transmitter in a communications channel
`1991 which are incorporated herein by reference.
`according to the invention;
`FIG. 1 is a block diagram which illustrates how data
`FIG. 3 is a graph of audio output power as a function
`flows through an OFDM/FM data communication
`of signal strength for a typical FM receiver;
`channel according to the invention. The digital FM
`FIG. 4A and 4B are graphs of noise power distribu
`channel comprises in sequence a source of serial data 5,
`tion in transmitted and received signals respectively
`transmitter host computer 10, a transmitter digital signal
`where the modulating signal has constant power across
`processor 20, transmitter signal conditioning apparatus
`the spectrum;
`30, a radio channel 40 which is subject to fading, re
`FIGS. 5A and 5B are graphs of noise power distribu
`ceiver signal conditioning apparatus 50, a receiver digi
`tion in transmitted and received signals respectively
`tal signal processor 60, a receiver host computer 70, and
`where the modulating signal has a -10 dB per decade
`a serial digital data output 80.
`pre-emphasis;
`Serial data 5 are first processed in transmitter host
`FIG. 6 is a scatter plot showing the calculated phase
`25
`computer 10 and transmitter data signal processor 20 to
`and amplitude of received data with no equalization;
`generate a digital signal defining the OFDM baseband
`FIG. 7 is a scatter plot of the data of FIG. 6 after
`modulating signal. The transmitter and receiver host
`channel equalization;
`computers 10, 70 may be, for example, IBM PC/AT
`FIG. 8 is a plot showing the probability of failure to
`compatible computers. The digital signal processors 20,
`achieve coarse synchronization as a function of the IF
`30
`60 may be for example model DSP56001 Processor
`SNR level for different numbers of synchronization
`Boards available from Spectrum Signal Processing Inc.
`tones;
`of Burnaby, British Columbia, Canada, residing on the
`FIG. 9 is a block diagram showing the steps involved
`internal buses of the host computers. Digital to analog
`in synchronizing OFDM data flames according to the
`(D/A) and analog to digital (A/D) conversions may be
`invention;
`35
`achieved by means of cards such as Spectrum 4-channel
`FIG. 10 is a block diagram showing the steps in
`Analog I/O boards connected to the digital signal pro
`volved in detecting the presence of an OFDM data
`cessors and mounted on the internal buses of host com
`frame according to the invention;
`puters 10, 70.
`FIG. 11 is a plot of the probability of falsely detecting
`In transmitter host computer 10 serial data 5 are first
`an OFDM data frame as a function of the threshold
`encoded. In the encoding step 11 the stream of data is
`used to determine when a data frame is not present;
`broken up into groups of m bits. Each group of m bits is
`FIGS. 12 and 13 are plots which illustrate the perfor
`encoded as phase and amplitude information for one of
`mance of a test system for detecting the presence of an
`a number of sub-carrier frequencies. For example, if
`OFDM frame according to the invention;
`QAM encoding is used, the m-bit groupings of data are
`FIG. 14 is a block diagram illustrating the method of 45
`first encoded as complex values, a--jb, defining points
`obtaining coarse synchronization of an OFDM data
`in a 2-QAM constellation. There may be, for example,
`frame according to the invention;
`FIG. 15 is a graph showing amplitude and group
`256 frequency sub-channels between 1 kHz and 3 kHz
`used to carry data and synchronization information.
`delay corrections for channel equalization in a test sys
`The output of encoding step 11 is therefore a stream of
`tem according to the invention;
`50
`FIG. 16 is a block diagram illustrating the technique
`complex values which represent the phase and ampli
`for achieving fine synchronization according to the
`tude of the data-carrying sub-carriers in the signal to be
`transmitted.
`invention;
`FIGS. 17 and 18 are plots showing the relationship
`In general, modulation and demodulation can be effi
`ciently done using Inverse Fast Fourier Transform
`between Bit Error Rate and the number of tones used
`55
`for synchronization at various signal levels in a commu
`(IFFT) and Fast Fourier Transform (FFT) algorithms
`respectively. For example, the modulating signal may
`nications channel according to the invention; and
`FIG. 19 is a block diagram of a laboratory system for
`be obtained as follows. The IFFT algorithm operates on
`simulating an FM fading channel which may be used to
`a block of data. Therefore, the complex numbers output
`test apparatus according to the invention.
`from encoding step 11 are grouped. This is indicated by
`serial to parallel conversion step 12.
`DETAILED DESCRIPTION OF THE
`Before the IFFT is performed a software pre-empha
`PREFERRED EMBODIMENT
`sis is preferably carried out to adjust the amplitude of
`1. Generating and decoding an OFDM/FM signal
`complex numbers in the block of data. The amount of
`Apparatus and methods for generating and decoding
`the adjustment is proportional to the frequency of sub
`65
`an OFDM signal are discussed in Keasler, Reliable data
`carrier to which the data element is assigned. Preferably
`communication over the voice bandwidth telephone
`the adjustment is -10 dB per decade. This is discussed
`channel using orthogonal frequency division multiplex
`further below with reference to FIGS. 4 and 5.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1016, p. 24
`
`
`
`5,444,697
`8
`7
`The block of complex values is then input to an N
`attached to the microphone input. When a load is de
`point Inverse Fast Fourier Transform (IFFT) algo
`tected (i.e. when relay 103 is on), the transmitter's Push
`rithm, their location in the IFFT data array correspond
`To Talk (PTT) is enabled. When the load is removed,
`ing to the frequency of their assigned sub-carrier chan
`PTT is disabied.
`nel. Where a sub-carrier is not used, the corresponding
`Of course, there are many variations on this method
`value in the IFFT data array is set to zero. Only the
`for creating an OFDM signal. For example, the segmen
`lower half of the data array is independently specified.
`tation of processing tasks between host computers 10,
`Each value in the upper half of the data array is set
`70 and DSP units 20, 60 is dictated by available technol
`equal to the complex conjugate of the corresponding
`ogy. These tasks could be segmented differently or
`value in the lower half so as to produce a set of N real
`performed by a single integrated device using technol
`10
`modulating signal samples when the IFFT is per
`ogy different from that described above. Furthermore,
`formed.
`the