(12)
`
`United States Patent
`Laroia et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,922,388 B1
`Jul. 26, 2005
`
`US006922388B1
`
`(54)
`
`SIGNAL CONSTRUCTION, DETECTION AND
`ESTIMATION FOR UPLINK TIMING
`SYNCHRONIZATION AND ACCESS
`CONTROL IN A MULTI-ACCESS WIRELESS
`COMMUNICATION SYSTEM
`
`(75)
`
`(73)
`
`Inventors: Rajiv Laroia, Basking Ridge, NJ (US);
`Junyi Li, MataWan, NJ (US); Sundeep
`Rangan, Hoboken, NJ (US); Sathyadev
`Venkata Uppala, Scotch Plains, NJ
`(Us)
`Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`(22)
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.: 09/503,041
`Filed:
`Feb. 11, 2000
`
`Int. Cl.7 ............................................... .. H04J 11/00
`370/208; 370/343
`Field of Search ............................... .. 370/370, 371,
`370/372, 373, 374, 375, 343, 208, 209,
`210, 328, 329, 330, 344, 480; 375/133,
`135, 136, 138
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`7/1995 Dent
`5,430,760 A
`5,802,044 A * 9/1998 Baum et al.
`5,867,478 A * 2/1999 Baum et al.
`5,930,308 A * 7/1999 Schmutz
`5,970,047 A * 10/1999 Suzuki
`6,038,450 A
`3/2000 Brink et al.
`6,178,215 B1 * 1/2001 Zhang et al.
`6,266,365 B1 * 7/2001 Wang et al.
`6,317,412 B1 * 11/2001 Natali et al. .............. .. 370/208
`6,330,294 B1 * 12/2001 Ansbro et al.
`6,359,938 B1 * 3/2002 Keevill et al.
`6,449,246 B1 * 9/2002 Barton et al.
`6,456,653 B1 * 9/2002 Sayeed
`
`6,546,055 B1 *
`6,549,561 B2 *
`6,560,209 B1 *
`
`4/2003 Schmidl et al.
`4/2003 Crawford
`5/2003 Alamouti et al. ......... .. 370/330
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`GB
`JP
`
`0 760 564 A2
`2 324 932 A
`11-113049
`
`3/1997
`4/1998
`4/1999
`
`OTHER PUBLICATIONS
`
`S. Gupta, “Phase—Locked Loops,” Proceedings IEEE, vol.
`63, pp. 291—306, Feb. 1975.
`W. Lindsey and C. Chie, “A survey of digital phase—locked
`loops,” Proceedings IEEE, vol. 69, pp. 410—432, 1981.
`L. Franks, “Synchronization subsystems: analysis and
`design,” Digital Communications, Satellite/Earth Station
`Engineering, K. Feher, ed.,, Prentice—Hall, EngleWood
`Cliffs, NJ, pp. 294—325, 1981.
`(Continued)
`Primary Examiner—KWang Bin Yao
`(57)
`ABSTRACT
`
`Signal construction, detection and estimation techniques for
`use in uplink timing synchronization and access control in
`an orthogonal frequency division multiplexed (OFDM)
`Wireless system or other type of Wireless communication
`system. In accordance With an illustrative embodiment of
`the invention, timing and access signals to be transmitted in
`designated timing and access intervals are constructed from
`orthogonal multitone signals. The multitone signals may be
`similar to multitone signals used in OFDM data
`transmission, except that a cyclic pre?x associated With
`reception of the signals in a base station is extended to cover
`the timing errors of mobile stations not yet synchronized.
`The invention also provides design techniques Which opti
`mize the time resolvability and peak-to-average ratio of the
`multitone signals, an ef?cient fast Fourier transform (FFT)
`based technique for maximum likelihood timing estimation,
`and a robust linear ?ltering technique for averaging timing
`estimates from different synchronizations.
`
`39 Claims, 3 Drawing Sheets
`
`TIMING 0R ACCESS SIGNAL FROM MOBILE
`M?
`MULTITONE
`GUARDl SIGNAL GUARDZ
`Tg1
`Ts
`T92
`
`TIMING» __
`ERROR
`A
`
`To “I
`SAMPLE
`WINDOW
`W
`BASE STATION TIMING AND ACCESS INTERVAL
`
`TIME
`
`.
`l
`
`Facebook's Exhibit No. 1052
`Page 1
`
`

`
`US 6,922,388 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`H. Meyr and G. Ascheid, “Synchronization in Digital Com
`rnunications,” NeW York, NY: Wiley Interscience, pp.
`21—35, 1990.
`J. Proakis, “Digital Communications,” NeW York, NY:
`McGraW—Hill, 3rd ed., pp. 333—371, 1995.
`A]. Viterbi, “CDMA: Principles of Spread—Spectrurn Com
`rnunications,” NeW York, Addison Wesley, Appendix 3A,
`pp. 68—75, 1995.
`A. V. Oppenheirn and R.W. Schafer, Digital Signal Process
`ing, EngleWood Cliffs, NJ, Prentice Hall, pp. 238—269, 1975.
`
`J. L. Brenner, “Application of Chebychev Polynornials to
`Antenna Design,” in Topics in Polynornials of One and
`Several Variables and their Application, T. M. Rassias, H.M.
`Srinivastava and A. Yanashaukas, editors, World Scienti?c
`Publ., pp. 101—108, 1993.
`
`M. Wahlqvist et al., “Tirne SynchroniZation in the Uplink of
`and OFDM Systern,” IEEE, pp. 1569—1573, 1996.
`
`* cited by eXarniner
`
`Facebook's Exhibit No. 1052
`Page 2
`
`

`
`U.S. Patent
`
`Jul. 26,2005
`
`Sheet 1 of3
`
`US 6,922,388 B1
`
`FIG. 1
`
`TIMING 0R ACCESS SIGNAL FROM MOBILE
`
`A
`MULTITONE
`GUARD1 SIGNAL GUARD2
`T91
`Ts
`T92
`
`TIMINGa __
`ERROR
`A
`
`T I, :41’
`SAMPLE
`WINDOW
`
`,TIME
`
`.
`A
`
`BASE STATION TIMING AND ACCESS INTERVAL
`
`F
`
`FIG. 2
`
`TIMING 0R ACCESS SIGNAL FROM MOBILE
`A
`
`/'
`GUARD
`1
`
`GUARD
`2
`
`\
`GUARD
`L+1
`
`MULTTTONE MULTéTONE ' ' ' MULTITONE
`
`%
`
`.
`
`TIMING
`ERROR ‘w A‘-
`
`w
`T
`SAMPLE
`\ 1
`
`_ V
`T
`SAMPLE
`2
`Y
`TTMING AND ACCESS INTERVAL
`
`.
`
`.
`
`.
`
`>TIME
`
`I
`
`1 >
`T
`SAMPLE
`I L j
`
`Facebook's Exhibit No. 1052
`Page 3
`
`

`
`U.S. Patent
`
`Jul. 26,2005
`
`Sheet 2 of3
`
`US 6,922,388 B1
`
`FIG. 3
`
`10%
`
`CONJUGATE IFFTs 0F
`SYNC SIGNAL
`MULTIPATH COMPONENTS
`/_—*'_—\
`A‘vI-AS
`
`‘02
`DATA WITH
`SYNC SIGNAL &
`v [Fl-T
`
`Y(t)
`
`1034
`
`A
`
`Y
`
`103-5
`
`104-1
`S
`FFT
`MAGNITUDE
`.
`;
`
`r
`1
`
`108
`3
`MAX AND
`MAX
`LOCATION
`m
`MAGNHUDE rsme
`3
`104-5
`
`110
`SIGNAL
`L DETECT
`' I
`
`DELAY
`ESTIMATE
`
`200
`\
`
`222
`
`'
`ek
`ESTIMATED CLIPPER
`TIMING ERROR
`(FROM RECEIVER)
`
`FIG. 4
`
`224
`
`9k
`
`' L
`
`20s
`%
`d
`k-1
`
`dk
`TX CLOCK
`DELAY; ADVANCE
`3
`208
`
`Facebook's Exhibit No. 1052
`Page 4
`
`

`
`U.S. Patent
`
`Jul. 26,2005
`
`Sheet 3 of3
`
`US 6,922,388 B1
`
`FIG. 5
`
`TIMING 0R ACCESS SIGNAL FROM MOBILE
`: STSYm
`T92
`MULTITONE 1
`‘ Ts: 2T
`7%
`
`‘
`
`T91
`
`ll
`
`7
`
`T93
`
`MULTITONE 2
`Ts: 2L}:
`
`l
`TIMING ERROR» <— I
`A
`I
`ll
`
`T
`
`l
`SAMPLE
`INTERVAL T
`
`I
`'
`
`T
`
`SAMPLE
`INTERVAL 2
`
`l
`'
`
`' 'l
`
`A
`
`BS TIMING AND ACCESS INTERVAL (STSYm)
`
`'
`
`' TIME
`
`Facebook's Exhibit No. 1052
`Page 5
`
`

`
`US 6,922,388 B1
`
`1
`SIGNAL CONSTRUCTION, DETECTION AND
`ESTIMATION FOR UPLINK TIMING
`SYNCHRONIZATION AND ACCESS
`CONTROL IN A MULTI-ACCESS WIRELESS
`COMMUNICATION SYSTEM
`
`RELATED APPLICATION
`
`The present invention is related to the invention described
`in US. patent application Ser. No. 09/503,040, ?led con
`currently hereWith in the name of inventors R. Laroia et al.
`and entitled “Uplink Timing Synchronization and Access
`Control for a Multi-Access Wireless Communication
`System,” Which is incorporated by reference herein.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to Wireless com
`munication systems and more particularly to techniques for
`constructing, detecting and estimating signals for use in
`uplink timing synchroniZation and access control in a multi
`access Wireless communication system.
`
`BACKGROUND OF THE INVENTION
`Orthogonal frequency division multiplexing (OFDM) has
`been recently proposed as a multi-access scheme for use in
`the next generation of cellular Wireless systems. A critical
`issue in the design of these systems is the requirement of
`strict timing synchroniZation and access control. In order to
`maintain orthogonality in the uplink, it is necessary that all
`signal paths from all mobile stations (“mobiles”) arrive
`Within a so-called receive cyclic pre?x of the particular base
`station that they are attempting to communicate With.
`Moreover, neW mobiles that have not yet synchroniZed must
`be able to access the base station Without disrupting the
`uplink data from mobiles already in communication and
`synchroniZed With the base station.
`A need exists for techniques for construction, detection
`and estimation of the timing and access signals to be used in
`OFDM uplink synchroniZation and access systems. The
`construction, detection and estimation of timing and access
`signals is a classic problem, and-involves, in general, a
`number of standard criteria including timing resolvability,
`signal bandWidth, the poWer requirement on the mobile to
`transmit the signals, and estimation optimality. See, e.g., J.
`G. Proakis, “Digital Communications,” 3rd ed., NeW York,
`McGraW Hill, 1995, Which is incorporated by reference
`herein. HoWever, the design and estimation of signals for
`certain OFDM multi-access Wireless synchroniZation sys
`tems presents a number of unique challenges.
`First, the multi-access channel may result in interference
`betWeen signals. It is desirable to reduce the co-signal
`interference to improve the signal detection and estimation,
`and eliminate the need for the computationally dif?cult
`procedures such as interference cancellation or multi-user
`detection and estimation. Also, in Wireless systems, signals
`from different mobiles may be received With Widely differ
`ent poWers, and suppression of the co-signal interference is
`necessary to avoid strong signals from overWhelming
`Weaker ones. This need to suppress co-signal interference is
`particularly important during access, When neW mobiles
`may not yet be poWer controlled. Also, When co-signal
`interference is reduced, mobiles Which have failed access
`can more rapidly increase their transmission poWer in sub
`sequent access attempts, since the effect of co-signal inter
`ference from a high-poWer mobile is reduced. This potential
`for faster poWer increases Would reduce the access delay.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Second, in a Wireless channel, signal detection and timing
`estimation should be robust against channel fading, multi
`path delay spread and any interference appearing in the same
`band. Moreover, in OFDM systems, the objective of timing
`estimation is not to resolve all the signal path arrival times.
`Instead, it is only necessary to determine some timing offset
`such that all signal paths arrive Within the base station cyclic
`pre?x.
`Conventional techniques have been unable to address
`adequately the above-identi?ed concerns relating to the
`construction, estimation and detection of timing and access
`signals for synchroniZation and access control in OFDM
`systems.
`
`SUMMARY OF THE INVENTION
`The present invention provides improved techniques for
`construction, detection and estimation of timing and access
`signals in an OFDM system or other type of Wireless
`communication system.
`In accordance With one aspect of the invention, a set of
`timing and access signals are made orthogonal by construct
`ing them from multitone signals. Amultitone signal may be,
`e.g., a linear combination of discrete complex tones, Whose
`baseband tone frequencies are integer multiples of l/T,
`Where Tis the base station sample WindoW siZe. Each timing
`and access signal may contain one such multitone signal,
`With multitone signals in different timing and access signals
`using non-overlapping tone frequencies.
`Advantageously, such multitone timing and access signals
`are guaranteed to be received orthogonally over the base
`station receiver sample WindoW, since the distinct tones
`contained in the signals are orthogonal over any period of
`length T. Also, since linear channels do not change the tone
`frequencies, the multitone timing and access signals Will be
`received orthogonally, even When different signals arrive
`asynchronously through different multipath channels. The
`orthogonality eliminates the co-signal interference described
`above, and thereby improves the signal-to-noise ratio, elimi
`nates the need for multi-user detection and estimation, and
`permits a greater range of receive poWer levels.
`Orthogonality can be maintained under variable arrival
`times and multipath channels by transmitting each multitone
`signal for a time, T5, Which is larger than the base station
`sample WindoW siZe, T. This extra length, TS—T, provides a
`timing slack, such that even under variable arrival times and
`multipath dispersion, the base station sample alWays cap
`tures exactly one T-period of the sinusoidal steady-state
`response to the multitone signal.
`Timing errors of mobiles not yet synchroniZed can be
`covered by selecting the excess length, TS—T, of the timing
`and access signals to be larger than that used in OFDM data
`signals. In addition, guard periods in Which there is no
`transmission can be added at both ends of a given timing and
`access signal, to prevent the timing and access signals from
`interfering With data reception outside the timing and access
`interval.
`In one illustrative embodiment of the invention, each
`timing and access signal contains one multitone signal and
`the base station captures one T-period of the signal. In
`another illustrative embodiment, each timing and access
`signal comprises a sequence of L multitone signals trans
`mitted one after another, and the base station captures one
`T-period from each of the L multitone signals. The multiple
`sample format can be used to reduce the peak number of
`tones transmitted by the mobile at one time, thereby reduc
`ing the peak transmit poWer requirement.
`
`Facebook's Exhibit No. 1052
`Page 6
`
`

`
`US 6,922,388 B1
`
`3
`Another aspect of the invention provides techniques for
`optimizing the tone frequencies and coef?cients of the
`multitone timing and access signals. In accordance With
`these techniques, tone frequencies and the magnitudes of the
`complex multitone coefficients can be determined using the
`criterion of time resolvability, While the phases of the
`complex coefficients are determined using the criterion of
`peak-to-average ratio. More particularly, to combat channel
`fading, the tones of each multitone signal are selected to
`span a large frequency range for frequency diversity. This
`diversity may be achieved by constructing each multitone
`signal of groups of contiguous tones, With the groups
`separated beyond the channel coherence bandWidth. Finite
`impulse response (FIR) ?lter design techniques, such as
`Chebychev polynomials, may be used to determine coef?
`cient magnitudes of the tones in each contiguous group. The
`coef?cient phases of tones in each multitone signal are then
`selected to minimize the resultant peak-to-average ratio
`Without affecting the optimized property of time resolvabil
`ity.
`A further aspect of the invention provides a maximum
`likelihood (ML) estimator for the base station to estimate the
`arrival time of the received multitone timing and access
`signal. In a multipath channel, the ML estimate is the delay
`that maximizes the sum of the cross-correlation energies of
`the received signal With certain multipath component of the
`transmitted signal. The ML estimator can be implemented
`With standard Inverse Fast Fourier Transform (IFFT) tech
`niques. Also, the received signal poWer can be estimated by
`the maximum of the total cross-correlation energy. The
`presence of a transmitted access signal can be detected When
`the estimated received signal poWer surpasses a pre
`determined energy threshold constant. The ML estimate for
`the timing and poWer can be used in the access
`acknowledgment, if the access can be granted.
`In accordance With another aspect of the invention, if
`timing re-synchronizations are suf?ciently frequent, then
`timing estimates at different synchronizations are combined
`to improve the estimation accuracy. The combining can be
`performed by linearly loW-pass ?ltering the timing estimates
`from the base station. A clipping technique may be used to
`screen out large and spurious timing errors. Such timing
`errors can occur due to fading of the timing signal resulting
`in a poor estimate at the base station, or fading of the
`feedback channel resulting in a corruption of the feedback
`timing correction.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shoWs a single sample timing and access signal in
`accordance With the invention;
`FIG. 2 shoWs a multiple sample timing and access signal
`in accordance With the invention;
`FIG. 3 shoWs an illustrative embodiment of a base station
`multipath detection and timing estimation system in accor
`dance With the invention;
`FIG. 4 shoWs an illustrative embodiment of a mobile
`station clock offset adjustment system With ?ltering in
`accordance With the invention; and
`FIG. 5 shoWs a timing and access signal for an example
`design in accordance With the invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The present invention Will be illustrated beloW in con
`junction With an exemplary multiple access Wireless com
`
`10
`
`15
`
`25
`
`35
`
`40
`
`45
`
`55
`
`65
`
`4
`munication system based on orthogonal frequency division
`multiplexing (OFDM). It should be understood, hoWever,
`that the invention is not limited to use With any particular
`type of Wireless communication system.
`The above-cited US. patent application Ser. No. 09/503,
`040 discloses systems for OFDM synchronization and
`access control in Which mobiles transmit certain timing and
`access signals in dedicated timing and access intervals. In an
`illustrative embodiment of such a system, the timing and
`access intervals occur periodically in the uplink stream, and
`all regular uplink data transmission is suspended during the
`intervals. For access, neW mobiles transmit one of a pre
`speci?ed set of access signals during the interval, and the
`base station searches each interval for the presence of the
`access signals to detect the access requests. If an access
`request is detected and granted, the base station can send an
`access acknoWledgment in the doWnlink containing uplink
`and doWnlink channel assignments along With initial timing
`and poWer corrections. Similarly, for re-synchronization,
`mobiles can transmit pre-speci?ed synchronization signals
`in the timing and access intervals. The base station can
`measure the arrival times of the signals, and transmits
`appropriate timing corrections back to the mobiles in the
`doWnlink.
`Since this illustrative uplink synchronization and access
`system uses designated intervals completely separate from
`the uplink data, considerable ?exibility is available in signal
`design, detection and estimation. In particular, timing and
`access signals can be designed completely differently than
`regular OFDM data signals.
`The present invention provides techniques for
`construction, detection and estimation of timing and access
`signals. These techniques are particularly Well suited for use
`in synchronization and access control systems such as those
`described in the above-cited US. Patent Application, but are
`also applicable to other types of systems.
`
`Multitone Signals
`In an illustrative embodiment of the present invention,
`timing and access signals are constructed from multitone
`signals. A multitone signal is a linear combination of com
`plex exponentials of the form (in baseband),
`
`Where M is the number of tones, otm are complex scalars, mm
`are the tone frequencies and T is the base station sample
`WindoW size. The indices nm are each integers from 0 to N-l
`Where N is the total number of tones available. To utilize the
`same processing as the data reception, the timing and access
`WindoW size, T, Will be the same as the WindoW size for the
`OFDM data symbols. The time T5 is the length of the
`multitone signal and Will be greater than T but less than the
`total length of the timing and access signal. Any signal u(t)
`of the form (1) is periodic With period T.
`A multitone signal can be computed by the mobile using
`an inverse fast Fourier transform (IFFT) processor Which is
`also used for OFDM data transmission. Alternatively, the
`signal can be pre-computed and stored in a memory of the
`mobile.
`An important property of the multitone signals in this
`embodiment is that tWo multitone signals With non
`overlapping sets of tone frequencies are orthogonal over any
`period of length T. Moreover, the tWo multitone signals Will
`
`Facebook's Exhibit No. 1052
`Page 7
`
`

`
`US 6,922,388 B1
`
`5
`remain orthogonal even if transmitted over different multi
`path channels, since the received signals Will also be mul
`titone signals With the same tones as the transmitted signals.
`Consequently, orthogonally received timing and access sig
`nals can be easily constructed by using multitone signals
`With disjoints sets of tones.
`By Way of example, tWo illustrative multitone timing and
`access signal formats Will be described beloW: single sample
`timing and access signals, and multiple sample timing and
`access signals.
`
`Single Sample Timing and Access Signals
`FIG. 1 shoWs an example of a single sample timing and
`access signal in accordance With the invention. The timing
`and access interval refers to the interval in Which the timing
`and access signals are received. Although the ?gure only
`shoWs one timing and access signal, it should be understood
`that a number of timing and access signals from different
`mobiles could be received in the same timing and access
`interval.
`The base station takes one sample WindoW of the total
`timing and access interval. The sample WindoW has length T,
`and begins at a time T0 from the beginning of the interval.
`The total length of the timing and access interval is denoted
`Ti. The single sample timing and access signal itself com
`prises one multitone signal of length TS along With guard
`periods (described beloW) of length Tg1 and Tg2 on both
`ends. The multitone signal is of the form (1) above. For
`orthogonality, different timing and access signals use non
`overlapping sets of tone frequencies 00,, .
`.
`.
`, 00M. The
`selection of the tone frequencies mm and coef?cients otm Will
`be described beloW. The timing and access signal has the
`same length as the timing and access interval.
`The timing and access signal is shoWn to arrive With an
`error, denotedArelative to the base station timing and access
`interval. In general, A can be positive or negative. For the
`proposed signal construction and timing estimation, it is
`assumed that there are some a priori bounds on the maxi
`mum timing error. Before transmitting a timing or access
`signal, it is assumed that mobiles attain some level of
`synchroniZation Which is guaranteed to bring the timing
`error Within these bounds. These timing error bounds could
`be larger than the ?nal desired timing errors, and could be
`achieved by a knoWn technique, such as open-loop synchro
`niZation.
`The guard periods of length Tg1 and Tg2 as shoWn in FIG.
`1 are periods in Which there is no transmission. The guard
`periods insure that the multitone signal Will not corrupt data
`reception outside the timing and access interval. The lengths
`Tg1 and Tg2 should be sufficiently large to cover the possible
`range of the timing errors A.
`The starting point of the sample WindoW, To, should be
`selected such that the sample WindoW lies entirely in the
`TS-length multitone signal for all possible values of A. Also,
`in a channel With maximum delay spread 6W, the sample
`WindoW should start at least 6W from the beginning of the
`multitone signal to insure that the channel comes to the
`steady-state sinusoidal response before the T-sample Win
`doW. With this alignment, the base station samples exactly
`one T-period of the steady-state sinusoidal response of the
`TS-length multitone signal. Also, TO can be adjusted, if
`desired, such that the timing and access sample WindoW is
`synchroniZed With the sample WindoWs of the OFDM data
`symbols.
`It can be seen that the mobile must transmit the multitone
`signal for a time T5 greater than one period T, to cover the
`
`6
`unknoWn timing error A and channel delay spread am. This
`is similar to the cyclic pre?x used in traditional OFDM.
`HoWever, this excess length, TS—T, Will in general be larger
`than the cyclic pre?x in the OFDM data symbols, since the
`excess length must cover the timing errors from mobiles not
`yet synchroniZed.
`Multiple Sample Timing and Access Signals
`In certain circumstances, the mobile may have insuf?cient
`poWer to transmit a large number of tones at the same time.
`To reduce the peak number of tones transmitted, a multiple
`sample timing and access signal format may be used, in
`Which a number of multitone signals are transmitted sequen
`tially over time.
`FIG. 2 shoWs an example of a multiple sample timing and
`access signal in accordance With the invention. The timing
`and access signal comprises a sequence of L multitone
`signals transmitted one after the other. The base station takes
`a T-length sample from each of the L multitone signals. As
`in the single sample case, each of the L multitone signals is
`of length TS and of the form
`In each of the L sample
`WindoWs, different timing and access signals should use
`non-overlapping sets of tone frequencies.
`As in the single sample signal of FIG. 1, guard periods can
`be added at the beginning and end of the sequence of
`multitone signals to protect adjacent data reception. For
`alignment purposes, guard periods can also be added in
`betWeen the multitone signals. Also, the L sample WindoWs
`should be aligned such that they capture one T-period of the
`steady-state response of each of the L multitone signals.
`Single Time Resolvability Optimization
`Designing orthogonal multitone synchroniZation signals
`of the form (1) involves selecting the number, M, of tones
`per signal, and, for each signal, selecting the tone frequen
`cies mm and the coef?cients, otm. For purposes of illustration,
`example signal designs Will be described herein using time
`resolvability and peak-to-average ratio as design criteria. It
`should be noted, hoWever, that a precise evaluation of a
`timing signal generally requires a detailed simulation With a
`speci?c channel model. This section Will consider the ?rst of
`the tWo above-noted design criteria, namely, time resolv
`ability.
`A timing signal generally must be designed such that the
`delay of the signal’s arrival can be estimated easily by the
`base station. Time resolvability refers to hoW easy this
`estimation is in the presence of channel fading and noise.
`For simplicity, We ?rst consider the design of multitone
`signals assuming a single-path channel model. We Will then
`extend the description to the case of multipath channels. In
`a single-path channel, a mobile transmits a timing signal u(t)
`and the base station receives a delayed version of the signal,
`u(t-I). The base station must estimate the delay '5 from the
`received signal.
`For periodic signals u(t) of the form (1), the cyclic
`sampled autocorrelation of the signal can be used as one
`simple measure of its time resolvability, i.e.,
`
`10
`
`15
`
`35
`
`40
`
`45
`
`55
`
`Nil
`
`(Z)
`
`65
`
`The cyclic autocorrelation Ru ('5) represents the degree of
`correlation betWeen the signals u(t) and u(t-I). If the auto
`correlation magnitude |Ru("c) I is high, it can be expected that
`it Would be dif?cult to resolve tWo delays separated by "c.
`
`Facebook's Exhibit No. 1052
`Page 8
`
`

`
`US 6,922,388 B1
`
`7
`This fact can be justi?ed more rigorously by an analysis
`similar to that described in Appendix 3 of A. J. Viterbi,
`“CDMA: Principles of Spread-Spectrum Communication,”
`N.Y. Addison Wesley, 1995, Which is incorporated by ref
`erence herein. Following this analysis, one can compute the
`minimum probability of error in distinguishing betWeen tWo
`delays, "c='c1 and 'c="c2 on the basis of noisy, faded measure
`ments of the delayed timing signal u(t-I). It can be shoWn
`that this minimum error probability increases With the
`autocorrelation magnitude |Ru("c1—'c2)| and decreases With
`the signal poWer |Ru(0)|.
`Consequently, for good time resolvability, it is desirable
`to have |Ru('c)| small for all delay differences '5 to be
`resolved, and have the signal poWer, Ru(0); be as large as
`permitted. That is, it is desirable to have signals With
`“peaky,” or “White-noise like” autocorrelations.
`For a given number of tones M, the general problem of
`selecting the tone frequencies mm and the coef?cients otm to
`achieve a good autocorrelation Ru("c) is difficult. HoWever,
`the problem is signi?cantly simpli?ed if each timing signal
`is composed of contiguous tones. That is, one timing signal
`is constructed from tones 0 to M—1, the second from M to
`2M-1, and so on. With contiguous tones, the autocorrelation
`Ru("c) in (2) can be regarded as a frequency response of an
`M-tap ?nite impulse response (FIR) ?lter With positive
`coef?cients |otm|2. Thus, to create a “peaky” autocorrelation,
`one can use any standard FIR loW-pass ?lter With positive
`coef?cients.
`Suitable FIR ?lter design techniques are described in, e.g.,
`A. V. Oppenheim and R. W. Schafer, Digital Signal Proc
`cssing EngleWood Cliffs, N.J., Prentice Hall, 1975, Which is
`incorporated by reference herein. One such FIR design
`technique Well suited for multitone signals is based on
`Chebychev polynomials. The technique is to select the
`coef?cients otm based on the folloWing min-max optimiZa
`tion: ?x a 6>0, and ?nd the coef?cients otm in (1), to
`minimiZe,
`
`10
`
`15
`
`25
`
`35
`
`mqxé] |Ru('r)|, subject to Ru(O) : Emax
`min
`al,...,aM re[6, *
`
`(3)
`
`40
`
`Where Emax is the maximum alloWed signal poWer. This
`formulation uniformly minimiZes the autocorrelation |Ru('c)|
`over all 'CE[6, T-b], and consequently maximiZes the resolv
`ability of all relative delays greater than 6. The variable 6
`determines the minimum resolvable delay separation and
`can be adjusted as a design parameter. With M contiguous
`tones, the solution to (3) is standard and given by a Che
`bychev ?lter. The exact equations can be found in, e.g., J. L.
`Brenner, “Application of Chebychev Polynomials to
`Antenna Design,” in Topics in Polynomials of One and
`Several Variables and their Application, T. M. Srinivastava
`and A. Yanashaukas, editors, World Scienti?c Publ., 1993,
`Which solves a similar problem for multi-antenna design.
`The above analysis assumes a single-path channel model.
`In a multipath channel, it is necessary that the signal arrival
`time can be estimated in the presence of channel fading. One
`heuristic technique for combating channel fading is to
`incorporate some frequency diversity in the tone selection.
`That is, the tones of each multitone signal should span a
`large frequency range. In this Way, frequency selective
`fading Will only affect a subset of tones in the multitone
`signal, thus reducing the adverse impact on estimating the
`signal arrival time.
`Unfortunately, While contiguous tone selection alloWs for
`easy coef?cient design, contiguous tones offer little fre
`quency diversity since the tones are all located close
`
`45
`
`55
`
`65
`
`8
`together. A simple Way to add frequency diversity is for the
`multitone signal to be composed of groups of contiguous
`tones, With the groups separated beyond the channel coher
`ence bandWidth. The coef?cients of the tones in each con
`tiguous group can be designed by the FIR and Chebychev
`techniques described above. In a multiple sample timing and
`access signal, the different contiguous groups could appear
`in different sample WindoWs.
`
`Single Peak-to-average Ratio OptimiZation
`In most radio frequency (RF) ampli?ers, the poWer
`required to transmit a signal is generally determined by the
`signal’s peak value, not its mean square. For a T-periodic
`signal u(t), We de?ne the peak-to-average ratio (PAR) as
`
`Where
`
`For all signals, PARZl. Signals With a large PAR require a
`greater peak poWer to transmit and therefore necessitate a
`greater dynamic range in the RF ampli?er. Consequently, it
`is desirable to have the PAR as small (close to one) as
`possible.
`As shoWn above, the autocorrelation function |Ru('c)| in
`(2) depends only on the coef?cient magnitudes |otm|. Thus, it
`is possible to select the phases of the coefficients otm to
`minimiZe the PAR Without affecting the autocorrelation.
`To describe the PAR minimiZation more precisely, Write
`the complex coef?cients otm=hmexp(jq)m) Where hmZO is the
`magnitude and q)", is the phase. Assume the magnitudes hm
`are determined by the time-resolvability optimiZation
`described above. The PAR is minimiZed by adjusting the
`phases (pm. The values of hm ?x the norm HuH2 in (4), and
`therefore minimiZing the PAR over the phases 4)", is equiva
`lent to minimiZing the peak norm
`Thus, the PAR
`minimiZation can be reWritten as
`
`j
`mm
`
`(5)
`
`For moderate siZe M, the problem can be approximately
`solved by Well-knoWn numerical optimiZation techniques.
`
`Multipath Timing Estimation and Access Detection
`
`In slotted timing and access systems, it is generally the
`responsibility of the base station to search each timing and
`access interval for the presence of the timing and access
`signals. For each signal detected, the base station must
`measure the arrival time of the signal rela