||||||||||||||||||||||||||||||l|||||||||||
`
`USOO7599327B2
`
`(12) United States Patent
`Zhuang
`
`(10) Patent No.:
`
`(45) Date of Patent:
`
`US 7,599,327 B2
`Oct. 6, 2009
`
`(54) NTETI TOD AND APP.-—\R.-—\'l'US FOR ACCESSI .\'G
`A WIRELESS COMMUNICATION SYSTEM
`
`(56)
`
`References Cited
`US. PA'l'lil\l'I‘ I)()(ilJMl'iN'l'S
`
`T75}
`
`Inventor: Xiangyang Zhuang. Hoffman Estates.
`[L (U S}
`
`(73) Assignee: Motorola, Ine.. Schatmiburg. IL (US)
`
`( * ) Notice:
`
`Subject in any disclaimer. the term oflhis
`patent is extended or adjusted under 35
`U.S.C. T54-(b) by 313 days.
`
`(21) App1.N0.:
`
`ll.-’0'?0.06l
`
`(22)
`
`Filed:
`
`Mar. 2, 2005
`
`(65)
`
`Prior Publication Data
`
`US 2005i’(}286465 Al
`
`Dec. 29. 2005
`
`Related US. Application Data
`
`(60) Provisional application No. 60f582.602. filed on Jun.
`24. 2004.
`
`(51)
`
`Int. Cl.
`H0-afW 4./00
`
`(2(}0(1.0l)
`
`370.-’329:370;’203:37'0t'2]0
`(52) U.S.(.‘l.
`(58) Field of(?lassification Search
`370E329.
`370E203. 208. 210, 330. 336. 394
`Sec application tile for complete scarclt ltistory.
`
`7D
`
`
`T.—'l999 Vhnnattact al.
`5.930.299 A
`].-'200I
`Stiztiki el:ll.
`6.l78,l58 Bl ‘E
`].-"200l Freelieh etal.
`6.l'2'8.l9? Bl
`9«'20t}4
`l’I':Ls:td ct al.
`6388.728 Bl
`375-"I49
`9.-"2005 Song
`G.947.4?6 B2 "’
`................ .. 3T0-‘Z03
`6-"2004
`Jung ct al.
`200450114504 Al "‘
`I-"2004 Sandell et al.
`3703210
`2004.-"0|3l0ll Al *
`OTHER PUBLICATIONS
`
`3T0'203
`
`Huy. Vu: The Inlernalitmtll Search Report or the Declaration. ISA.-’
`US. .-\lex.1.n:l.ria Virginia. completed: Nov. IT‘. 2005. m;1i|:.=d: Feb. 22.
`2006.
`
`*‘ cited by examiner
`
`-George ling,
`l’r.='nmr_t‘ .~':I.t'a:r;:iner
`Ass:'.s'."anr E.\'rtmi.eer—Marc0s L Torres
`
`(57)
`
`ABS’l‘RAC'l‘
`
`Access to a wireless colilmunicatioii system (.100) by :1 sub-
`scriber station (101-103) is facilitated by selecting, (705) an
`access sequence from at set oisequcitees that have been idenw
`lifled to have a low average 01‘peak-to-average-power-ratios
`of access signals generated by the set nfseqtleriees and also
`based on a good cross—c0rrelation ofthe access signals: form-
`ing (714) the access waveform by generating an access signal
`using the access sequence and appending in the time domain
`a cyclic prefix to the access signal: and transniitting (715) the
`access waveform. In some impletnentations. the access wave-
`lbrln is cyclically shifiod (820) before the cyclic prclix is
`appended, and in some implenielltalions. the signal is trans-
`mitted (710. 810) in 21 randomly selected sub—band of an
`access interval.
`
`2.] Claims, 6 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`SELECT AN ACCESS SEQUENCE FROH A SET OF NC ACCESS SEDUENCES
`THAT HAVE BEEN IDENTIFIED TO HAVE A LOT! AVERAGE OF PEAlt—TO-
`AVERAGE-POTTER-RATIOS OF ACCESS SIGNALS GENERATED BY THE SET OF
`Ne ACCESS SEDUENCES AND TO HAVE A GOOD CROSS—CDRRELATION OF
`THE ACCESS SIGNALS GENERATED BY THE SET OF Ni: ACCESS
`SEOUENCES, AND NHEREIN THE SET OF N: ACCESS SEOUENCES HAS
`BEEN GEHERATED BY A CORRESPONDING SET OF SEOUENCES OF LENGTH
`K. NHEREIN K [S A OUANTITY OF CARRIERS IDENTIFIED FOR TRANS!-IITTING
`AN ACCESS NAVEFORN
`
`
`
`APPLE 1013
`
`7T0
`
`
`
`SELECT A SUB—BAND
`
`714
`
`
`
`FOR! THE ACCESS TTAVEFDRH BY GENERATING AN ACCESS SIGNAL USING
`THE ACCESS SEQUENCE AND APPENDING IN THE TIME DOHAIN A CYCLIC
`
`PREFIX TO THE ACCESS SIGNAL
`
`N5
`
`
`
`'
`
`TRAHSHIT ms ACCESS wnsrottu
`
`APPLE 1013
`
`1
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet] 0f6
`
`US 7,599,327 B2
`
`‘"4
`
`BANDWIDTH
`REQUEST
`
`FIG. 1
`
`l'!3'_9
`
`2
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet 2 of6
`
`US 7,599,327 B2
`
`wax
`
`
`
`an
`
`:82;E33%
`
`xE#_._3.85Samba
`
`
`
`.........ND
`
`
`
`
`
`
`37,saga.2INAUNBNma)32.;
`
`©aN.\..n_@33..5§__§_gs:____§.=_5,__:_.§_2.2:.323:
`
`
`
`.335%..._§E=:2.53am:33,_.:_._§_
`
`
`23...:E52?,=§_m=:2x..§§)_E,Eramis
`
`
`
`52%ca:8,_:_.§_2.5:_s._:=_
`
`32.2;r:
`
`aux
`
`
`
`52.:__.a-a._.mE._as
`
`smzzmu.NRN
`5.5%.35.22.33saga..53,_3__§_
`.338?;WV._3__.&
`
`3
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet 3 of6
`
`US 7,599,327 B2
`
`23...;
`
`
`uzHuz¢=_=n;,m.om=»m
`-22.2295252:.E55253-292
`
`
`
`
`
`
` :3.5,9*3._a...fi...E23.52.2..,_.:_§_3538:2.2:52:...3..1.332:22#5:meas.55.5%3329:%VVVVA§A§§
`
`
`
`
`
`55.-.....38.;E=_§-_..
`
`
`
`.£__.§_=WmvNr»N:g§_§_s_2:.
`
`wNUNRN
`
`3..
`
`\-§_E:__
`
`éamas
`
`New
`
`(StI3H10{INV ‘IVIIINIJ aumnva
`
`(WILINI-HON) snlarwu
`
`[w111n1-non) anlmwa
`
`AJHJHDJHHJ
`
`4
`
`
`
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet 4 M6
`
`US 7,599,327 B2
`
`502
`
`II
`
`I’
`
`"sh cvcuc SHIFTS FOR EACH
`cons (TIME DOMAIN}
`‘’ "' 5"“
`7 -7 -
`,.’
`,-’
`
`W
`
`“SI 5””
`
`
`
`\
`"n; " costs
`SATIE conis
`ggglgifig TO EACH
`[A nxrrzmr CODE
`mFmAmmmm
`SECTOR)
`
`—
`
`I
`
`,,_—__
`$3
`g
`3
`
`,;-,~«,_
`Q
`5
`
`SUBBANDgnot
`
`II
`
`
`
`,/,/
`‘Q
`
`5-mu-5
`
`
`
`
`
`I 3-rd SHIFT
`
`
`
`
`
`
`
`
`
`
`SELECT AN ACCESS SEQUENCE FROM A SET OF Nc ACCESS SEOUENCES
`
`THAT HAVE BEEN IDENTIFIED TO HAVE A LON AVERAGE OF PEAK—TO-
`AVERAGE—PORER-RATIOS OF ACCESS SIGNALS GENERATED BY THE SET OF
`
`Nc ACCESS SEOUENCES AND TO HAVE A GOOD CROSS—CORRELATION OF
`THE ACCESS SIGNALS GENERATED BY THE SET OF N: ACCESS
`SEOUENCES, AND WHEREIN THE SET OF Nc ACCESS SEOUENCES HAS
`BEEN GENERATED BY A CORRESPONDING SET OF SEQUENCES OF LENGTH
`K. NHEREIN K IS A QUANTITY OF CARRIERS IDENTIFIED FOR TRANSMITTING
`
`AN ACCESS NAVEFORN
`
`
`
`
`
`SELECT A SUB-BAND
`
`FORN THE ACCESS WAVEFORM HT GENERATING AN ACCESS SIGNAL USING
`THE ACCESS SEQUENCE AND APPENDING IN THE TIME DOMAIN A CYCLIC
`PREFIX TO THE ACCESS SIGNAL
`
`75
`
`TRANSMIT THE ACCESS HAVEFORH
`
`01
`
`5
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet 5 M6
`
`US 7,599,327 B2
`
`30
`
`am
`
`8&5
`
`B2:
`
`324
`
`82
`
`SELECTING AN ACCESS SEOUENCE TRON A SET OF Nc ACCESS SEOUENCES
`
`SELECTING A SUB—BAND
`
`GENERATING AN ACCESS SIGNAL USING THE SELECTED ACCESS SEQUENCE
`
`CYCLICALLY TINE SHIFTING THE GENERATED ACCESS SIGNAL BY A SHIFT
`VALUE THAT IS ONE OF A DEFINED SET OF A PLURALITY OF Nsh SHIFT VALUES
`
`FORNING AN ACCESS WAVEFORM BY APPENDING A CYCLIC PREFIX TO THE
`SELECTED ACCESS NAVEFORN
`
`TRANSMITTING THE ACCESS HAVEFORH
`
`FIG. 8
`
`90
`
`
`
`IDENTIFYING IN A TRANSNITTEO CONTROL SIGNAL ONE OR MORE SUB-BANDS
`IN AN ACCESS INTERVAL, EACH OF WHICH CONPRISES K SUB—CARRIERS AND
`FOR WHICH EACH OF THE SUB—BANDS IS AVAILABLE FOR A SUBSCRIBER
`STATION TO USE TO TRANSNIT AN ACCESS SIGNAL
`
`
`
`9M
`
`95
`
`RECEIVING AN ACCESS SIGNAL FROM THE SUBSCRIBER STATION IN ONE OF
`THE ONE OR MORE SUB-BANDS DURING THE ACCESS INTERVAL
`
`DECODING THE ACCESS SIGNAL
`
`FIG. 9
`
`6
`
`

`
`U.S. Patent
`
`Oct. 6, 2009
`
`Sheet 6 M6
`
`US 7,599,327 B2
`
`MW5
`
`RECEIVING AN ACCESS SIGNAL FROM A SUBSCRIBER STATION DURING
`AN ACCESS INTERVAL
`
`I010
`
`
`
` EH5
`
`
`
`ANALYZING THE ACCESS SIGNAL TO IDENTIFY AT LEAST ONE OF A CTCLIC
`SHIFT OF A DEFINED SET OF CYCLIC SHIFTS AND AN ACCESS SEQUENCE OF
`A SET OF ACCESS SEOUENCES
`
`
`
`PROCESSING THE ACCESS SIGNAL T0 EXTRACT SUBSCRIBER STATION
`SYNCHRONIZATION INFORMATION
`
`FIG. 10
`
`7
`
`

`
`1
`METHOD AND APPARATUS FOR ACCESSING
`A Vt/IRELESS COMM U_\'ICA'l'I()N SYSTEM
`
`2
`for an etlicient and flexible air interface mechattistn that
`enables fast and reliable user access to the network.
`
`US ?,599,327 B2
`
`FIELD OF THE INVENTION
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention relates generally to comtrtonicatioti
`systems. and in particular_. to a method and apparatus for
`randomly accessing a wireless communication system by a
`subscriber station in order to obtain or maintain such param-
`eters as uplink timing. power control, channel estimation. and
`frequency alignment of the subscriber station
`
`1U
`
`BACKGROUND OF TI IF. INVIENTION
`
`In a wireless communication system. it is critical to design
`a mechanism for allowing a remote subscriber station (SS) to
`access the network by sending an access signal to a Base
`Station (BS). The access signal fiilfills important functions
`such as requesting resource allocation from the BS. alerting
`the BS of the existence of the SS that is trying to enter the
`network_. and initiating a process that allows the BS to mea-
`sure some parameters of the SS (e.g._. timing offset caused by
`propagation. transmit power. etc.) that must be maintained
`and adjusted constantly in order to ensure a non-interfering
`sharing of the uplink resource. Unlike ordinary data traliic
`that is sent using scheduled resources that are allocated by the
`BS to the SS. such an access signal is often trausntitted in an
`unsolicited manner. Therefore, this process is often referred
`to as a random access. Sometimes the process is also referred
`to as “ranging", as used in the Institute of Electrical and
`Electronic Engineers (IEEE} 302.16 standards. because the
`access signal can help the BS to measure the propagation
`distance from the SS (thus. its range). A parameter known as
`zt timing advance offset is used by the SS to advance its
`transmission relative to the reference timing at the BS so that
`the signals horn all the SS‘s appear synchronized at the BS
`(i.e.. uplink timing synclironiration}. Once uplink timing syn-
`chroniyation is achieved. the SS orthogonality is ensured (i
`each SS occupies its own allocated sub-carriers without inter-
`feringwith other SS). In this speci tication, the terms “access",
`“random access". and “rar1ging" will be used interchangeably
`to describe these processes and also to describe the signal
`transmitted by the SS to initiate the access process.
`The random access or ranging process includes an initial!
`handover ranging function for synchmnizing an SS with a BS
`during the initial network entry or re-entry and during cell
`handoll". a periodic ranging function for maintaining SS syn-
`chroniration. and a bandwidth request function that allows
`each SS to request uplink bandwidth allocation. These uplink
`ranging functions fillfill very important tasks that can signifi-
`cantly influence the user experience. For example. the band-
`width request ranging performance directly impacts the
`access latency perceived by a user. especially during committ-
`nication sessions (e.g.. HTTP) that consist of sporadic packet
`lralfic that requires fast response. in which case high detection
`and low collision probabilities of the access request are very
`desirable. In another example. robust detection of an initial
`ranging signal is essential in order to allow a user to quickly
`enter the network or to be handed over to a new serving sector.
`Reliable extraction of the accurate timing oifsets from the
`initial ranging signals is also critical for achieving uplink
`synchronization that ensures ttser orthogonality (i.e.. to make
`sure that each SS occupies its own allocated sub—carriers
`without interfering with other SS). Other important infon'na—
`tion that the BS needs to extract from ranging includes power
`trteasurcment.
`frequency synclironization.
`and channel
`impulse response estimation. etc. 'l‘herefore_. there is a need
`
`3U
`
`4U
`
`45
`
`50
`
`55
`
`60
`
`65
`
`FIG. 1 is a block diagrain of a conununication system. in
`accordance with some embodiments of the present invention.
`FIG. 2 is a time-domain diagram ofa “basic" dedicated
`basic ranging interval. in accordance with some embodiments
`ofthe present invention.
`FIG. 3 is a time-domain diagram of an extended dedicated
`ranging interval. in accordance with sortie embodiments of
`the present invention.
`FIG. 4 is a freqttency-dortlaitt diagram of a variation of the
`extended dedicated ranging interval. in accordance with sotne
`embodiments ofthe present invention.
`FIG. 5 is a time-domain diagram ofan example design for
`an OFDM system such as the one defined by the IEBE 802.16
`standard.
`
`FIG. 6 is a block diagram of the division ofranging oppor-
`tttnities in frequency. lime. and code domains. in accordance
`with some embodiments of the present invention.
`FIGS. 7 and 8 are flow charts of methods of accessing a
`conununication system. in accordance with some embodi-
`meuts of the present invention.
`FIGS. 9 and 10 are methods used by a base station in a
`wireless communication system for facilitating an access of
`the communication system by a subscriber station, in accor-
`dance with some embodiments of the present invention.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`Before describing in detail the particular communication
`system accessing technology in accordance with the present
`invention. it should be observed that the present invention
`resides primarily in combinations of method steps and appa-
`ratus components related to accessing a communication sys-
`tem by a subscriber station. Accordingly. the apparatus com-
`ponents and method steps have been represented where
`appropriate by conventional symbols in the drawings. show-
`ing only those specific details that are pertinent to understand-
`ing the present invention so as not to obscure the disclosure
`with details that will be readily apparent to those of ordinary
`skill in the art having the benefit ofthe description herein.
`Turning now to the drawings. wherein like numerals des-
`ignate like components. FIG. 1 is a block diagram of com-
`munication system 100. Communication system 100 com-
`prises a plurality ofcells 106 and 107 (only two shown) each
`having a base station (BS) 104, 185. The service area of the
`BS 104 covers a plurality of subscriber stations (SS5) 101-
`103, each at a time may be performing sotne type of ranging
`function. which is also called herein a random access func-
`tion. For example. SS 101 may move out ofthe service area of
`BS 104 and enter into the service area of BS 105, in which
`case a handover occurs that often involves a handover access.
`In other examples, SS 102 makes a bandwidth request andfor
`SS 103 makes an initial entry access when it is first activated
`within the communication system. In one embodiment of the
`present
`invention. communication system 100 utilizes an
`Orthogonal Frequency Division Multiplexed (OFDM) modu-
`latiou or other variants of OFDM such as multi-carrier
`CDMA ( MC-C DMA), multi-carrier direct sequence C DMA
`(MC—DS~CDMA).
`In other embodiments of the present
`invention. the rnulti-channel communication system 100 can
`use any arbitrary technology such as ’fl')MA. FDMA. and
`(DMA.
`
`8
`
`

`
`3
`
`4
`
`US ?,599,327 B2
`
`Definition of Dedicated Ranging Zone
`Referring to FIG. 2. a tittte-domaitt diagram shows a
`“basic" dedicated basic ranging zone 20] defined for an
`OFDM example systent [the term “zone“ is interchangeable
`herein witlt the term “interval" used in the figure). in accor-
`dance witlt some embodiments of tlte present invention. The
`duration ofthe dedicated basic ranging interval 201 consists
`ofan interval ofa special OFDM symbol 202 (denoted as
`“extended-(.”.l"‘ OFDM symbol) and a “dead interval" 204
`that is a tto-transtttissiott interval equal to the maximum tim-
`ing delay to be accommodated in tlte cell. The special OFDM
`symbol 202 has a duratiott equal to the sum of the duration of
`a special Fast Fourier Transfornt {I"l'-"I‘) window 209 and the
`duration ofan extended cyclic prefix (C P] 203 wlterein the C P
`represents the repeat ofa portion ofthe signal as conttnottly
`known itt Oi-‘DM. I-Ience. the special OFDM symbol is also
`referred to as an “extended-CP“ OF[)M symbol in FIG. 2.
`The special Fast Fourier Transform (FFT) window 209 may
`be chosen conveniently to be the same as a “regular" OFDM
`symbol period in an example deployment o f an OFDM sys-
`tem. or other designed value (discussed later). The duration of
`the extended CP 203 equals to the sum of the duration of a
`“regular" C? 205 and the maxintttm timing delay 206 to be
`accommodated. 'l‘lte maximunt timing delay is chosett based
`on the possible timing difierences among all possible sub-
`scriber locations. This value directly relates to the round-trip
`propagation delay and the cell size. Meanwhile. the duration
`ofa “regular" C P 205 withitt the extended CP 203 is tlte same
`as the Cl’ lengtlt defined for regular data transmissions if the
`invention is used for an OFDM system. For other systems. the
`time duration of a regular Cl’ is often chosen based on the
`excessive delay spread of the channels encountered in a
`deployment environment. which is also how the CF’ length is
`determined for OI-"l)M systems. Lastly. as described above.
`the appended “dead" interval is chosen according to the maxi-
`mal tinting delay.
`A ranging signal is allowed to be transmitted only in the
`defined ranging interval. The ranging waveform itself is con-
`structed as art OFDM symbol. i.e.. by appending a CI’ of a
`certain lettgth to a ranging signal. For convenience. we will
`use the term “waveform” to refer to the Cl-’-included signal
`attd the term ‘‘signal’‘ for the CP—excluded portion only. The
`ranging waveform transmission starts frotn what the SS deter-
`mines to be the right titttittg. For initial ranging users. that
`transmission point (i.e.. the transmission stan time) will be
`the beginning of the dedicated ranging interval according to
`the base reference plus the one-way propagation delay. The
`initial ranging SS should send at that point a waveform whose
`CP portion is of the length of an extended CP. For other
`ranging SS’s that have already synchronized with the BS, the
`SS should have known the tinting advance and transmit in
`advance to some reference point so that all the SS signals
`arrive at the BS at roughly the same time. In one embodiment.
`the non-initial ranging SS can either transmit a waveform
`with a regular CI’ at a timing point in advance to the start of
`205 witltin 203 of FIG. 2. or transmit a wavefontt with an
`
`extended C P at a tinting point in advance to the start of203.
`With the above definition of ranging interval, all types of
`ranging signals will not interfere with any transmission that
`precedes attd follows tlte ranging interval, such as Ol"'DlVI
`symbols 207 attd 208 in an OFDM-based example system.
`The maximum tinting delay should be large enough to accom-
`modate the maximum propagation delay for SS5 that have ttot
`adjusted their timing (i.e.. initial ranging users). The maxi-
`mum timing delay is a parameter determined based on the cell
`size. lior the receiver processing at the BS. since the BS
`predefines the maxitttutn tittting delay and thus the cxtettded
`
`1U
`
`3o
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`CP length. the BS should know how to adjust the sampling
`position accordingly in order to extract the special FFT win-
`dow 209. The special F FT window can be any size itt theory.
`A large special F FT wittdow can reduce the proportion ofthe
`extended (‘.13 to the special FFT size (i.e.. reducing the over-
`head) and provide tttore ranging opportunities to reduce col-
`lisiott. Also. the time span of the transmission can also be
`extended so that there will be more signal power arriving at
`the BS for the same average transmit power. I-Iowever, with a
`large special F FT window. the overall overhead of a ranging
`signal as a portion of the lIpli1'l.l.( sub-frame increases attd the
`ranging signal also becomes more susceptible to channel time
`variations (e.g. mobility) that results in inter-carrier interfe -
`ettce caused by Doppler shift. The choice of tlte special F FT
`size should also consider practical
`implementation. For
`example, in an OF DM system. making it an integer multiple
`ofthe regular FFT size may simplify the BS processing.
`The total ranging overhead. which is the ratio of the dura-
`tion oftlte dedicated basic ranging interval to the entire uplink
`sub-frame. depends only on the nplink sub-frame. The longer
`the uplink, the lower is the overhead. If the overhead dtte to
`the “dead interval” 204 delay becomes too excessive. the
`“dead interval" 204 can be omitted at the price of generating
`inevitable interference to the next symbol.
`Referring to FIG. 3. a time-dontain diagram shows an
`“extended" dedicated ranging interval 303 that is built upon
`the “basic" dedicated ranging interval 20.1. in accordance
`with sonte embodiments of the present invention. If more
`ranging opportunities are needed than what a basic ranging
`interval can provide. an extended ranging interval 303 can be
`defined where one or more regular Of-'l')M symbols 301 and
`302 with only a regular C P length may be added in front ofthe
`extended-Cl’ special symbol. Initial ranging transntission is
`allowed only during the extended-(‘P interval. but other rang-
`ing transtnissiotts are allowed everywhere. This design is an
`alternative to the case in which the special FFT size is
`enlarged. as described with reference to FIG. 2.
`Referring to FIG. 4. a frequettcy-domaitt diagram of a
`variation of the extended dedicated ranging interval is shown.
`in accordance with some etttbodiments of the present inven-
`tion. In these embodiments. the ranging signal is allowed to
`occupy only a portion of the system bandwidth instead ofthe
`entire bandwidth as before. For example, for the extended—C P
`sytnbol 401 (that is the same as extended C P symbol 202 in
`FIG. 2). a portion of the bautdwidth 402 is dedicated to rang-
`ing_. and the remaining bandwidth 403 is for data traffic. In
`fact, such a design in which the ranging attd data trailic are
`multiplexed can be done using different datafrangiug ratios
`for eaclt symbol itt the extended ranging interval sttclt as that
`illustrated in FIG. 4, where the additional regular OFDM
`symbols 404 and 405 are used. The gettetic term “frequency-
`time ranging mite” is used for these cases.
`Referring to FIG. 5, a time-domain diagram shows an
`exemplary ranging interval for an OFDM systettt similar to
`OFDM systems described by drafts and the pub] islted version
`of the IEEE 802.16 standard The ranging interval 501 is
`composed of one special OFDMA symbol with an extended
`CP that may be preceded by up to four regular OFDMA
`symbols each having a regular Cl’ for providing more ranging
`opporttutitics if needed. The duration of the extended CP is
`signaled by the base in a control message sent front the BS
`(tag. the UL-MAP message defined in draft and published
`versions of IEEE 802.16 standards) as an integer multiple of
`the regular C P. Similarly.
`the special FFT size of the
`extended—Cl’ symbol. which may also be an integer mttltiple
`ofthe regular [7 1’'1" size. is signaled itt the control ntcssage as
`well. Immediately after the special (JFDMA symbol. there is
`
`9
`
`

`
`5
`
`6
`
`US ?,599,327 B2
`
`a “dead" interval that equals to the largest maximum timing
`difference. But it may be omitted to trade performance deg-
`radation for overhead reduction. The control message may
`indicate whether the dead interval is included. The duration of
`
`the dead interval is implicitly known to the SS and is equal to
`the difference between the extended-(TP symbol duration and
`the regular C P duration.
`
`Division of Ranging Opportunities in Frequency, "lime, and
`Code Domains
`
`Referring to FIG. 6. a block diagram shows the division of
`ranging opportunities in frequency. time. and code domains.
`in accordance with some embodiments of the present inven-
`tion. Each random access signal is generated based on a
`ranging sequence (interchangeable with “access sequence“
`and “ranging code” and “access code") that is randomly cho-
`sen from a code group 601 allocated to the sector (the code
`group size is denoted herein as NC. an integer). The access
`sequences used in a code group and the allocation of code
`groups to different sectors are specified later. The ranging
`sequence may be used to generate an access signal by directly
`modulating the contiguous sub-carriers in a frequency block
`(sub-bamd) that is randomly chosen among Nb] sub-bands
`602, wherein N 1,, is an integer including tl1e value ‘‘I’‘ known
`to both BS and SS. Nb, may be determined based on the
`system bandwidth and be made known to the BS and the SS.
`The timewdoinain access signal is generated by performing an
`IFFT on the ranging sequence after modulating the chosen
`sub-band. Before a CP is inserted in front ofthe access signal
`to form a complete access waveform. the access signal may be
`cyclically (circularly) shifted in time domain, where the shift
`is chosen randomly among Nd, allowed values 603 tl1at are
`known to the BS and SS. wherein N_,,, is an integer. Lastly. a
`CP is added to form the final ranging waveform where the
`length ofthe CP is that of the extended C P for initial ranging
`and for other ranging. either the extended CP or the regular
`CP depending o11 the tratlsrnission point (discussed above].
`The duration of the waveform corresponds to the duration of
`one OFDM symbol
`in the extended ranging interval.
`in
`emboditnents such as those described with reference to FIG.
`3 and FIG. 5 In embodiments such as those described with
`
`reference to FIG. 5, the ranging sequence may be used to
`generate an access waveform by appending data symbols to
`die ranging sequence and directly modulating the contiguous
`sub-carriers in the frequency block (sub-band) that is ran-
`domly chosen. using tenns of the appended ranging
`sequence.
`
`More detail on the division of ranging opportunities in
`frequency. time. and code domains is as follows. Firstly, in the
`frequency domain_. an entire frequency band is divided into
`N51 frequency blocks 602 (NM sub-bands with K sub-carriers
`it1 each sub-band). A ranging signal may occupy only one
`sub-band. The reason for dividing the bandwidth into
`orthogonal blocks is for better flexibility. First. the number of
`ranging opportunities can be made adjustable to the band-
`width: larger bandwidth systems need to provide more oppor-
`tunities than narrower bandwidth systems for a similar colli-
`sion rate. Second, transmitting on a narrow sub—band allows
`power boost on that band to achieve a decent uplink SNR.
`even though narrowband transmission has lowertiining reso-
`lution than wider bandwidth transmission (Nb, channel taps
`will collapse into one channel tap when only lfN,,, of the
`bandwidth is excited). On the other hand. the number of
`sub—carriers in each sub-band. which equals to the length of
`the ranging sequence code, affects the cross-correlation char-
`acteristics. l'-‘or example. halving the number of sub-carriers
`in a sub-band allows a 3 dB transmit power boost on that band_.
`
`5
`
`1U
`
`3U
`
`4U
`
`45
`
`50
`
`55
`
`60
`
`65
`
`but the potential interference from other co-channel ranging
`codes also increases by 3 dB. So the munber of sub-carriers in
`a sub-band involves a tradeofi" between SNR boost and imer-
`
`ference sacrifice. In summary, the parameter N“ is specified
`by the 135 based on the bandwidth (FFT size). upliuk SNR
`requirement.
`timing precision requirement.
`suppression
`capability to potential co—channel interferences. and the num-
`ber of ranging opportunities that needs to be provided. It
`should also be specified jointly with the other two parameters
`NC and N”, described in more detail below.
`Secondly. in each sub-band. a number of ranging codes 601
`(i.e.. Ne sequences) may be allowed. Since these ranging
`codes occupy the same band. they may interfere with each
`other even withotlt any code collision. Sequences with good
`cross—con'elation are much desired for better code detection
`and channel estimation. in addition. a low PAPRi of the
`tirne-domain ranging waveform is also much desirable in
`order to be able to boost the transrnission power to improve
`the uplink SNR. The details of the sequences that have these
`desirable properties will be discussed in the next section.
`Additionally, for cellular deployment. a number of sequence
`groups (each having NC. access sequences) are also required
`for allocating to difierent neighboring sectors. So when those
`codes are generated and grouped, any pair of codes from
`distinct groups needs to have good cross correlation, just like
`any pair of codes in the satue group. In summary. the param-
`eter N‘, is determined by the BS based on the access needs and
`the nlaximally tolerable interference level at which the suc-
`cessful detection rate is still good.
`Thirdly. for each ranging code, NM, cyclic time shifts 683 of
`the time-domain ranging signal (phase rotation in frequency
`domain} can be used to fitrther increase the number ofranging
`opporuuiities. Mathematically.
`the
`frequency
`domain
`sequence, after thej”’ shift is
`
`3,-ttc:=s-tine t'’''’'‘”' ”‘''’”F”.
`
`{I}
`
`where s(k) is the original (or 0”’ shift) sequence. 1. is the C P
`length (regular or extended CP. depending on the type of
`ranging} and NF” is the FFT size. In essence. code separa-
`bility is achieved by the fact that the estimated channel is
`shified in time domain by some multiples of L. If L is large
`enough to cover most ofthe channel length. the access signals
`using distinct cyclic sllills will allow their corresponding
`channels to be separated reasonably well.
`The initial ranging transmission may be used by any SS
`that wants to synchronize to the system chamiel for the first
`time. In one embodiment of the invention, a control message
`from the BS may specify the sub-bands that an initial ranging
`signal can use. All sub—bands or, for example, a specified
`number of the sub-bands starting from the lowest frequency
`offset may be allowed for initial ranging. Maximally, only
`N, = [N511] LCM] shifts are preferred for interference-free code
`separation among different shifts of a ranging signal where
`[it] denotes the flooring function (ie, the maximum integer
`that is not greaterthan x ). LC.” is the length ofan extended CP
`and Nip is the FFT size ofthe special FFT symbol (209 of FIG.
`2) that may be multiples of the regular FFT size N. If sotne
`interference between estimated channels can be tolerated,
`that maximal number may be even increased. In general.
`more shifts can be used at the expense of increased interfer-
`ence. But a good practice is setting the number of shifts to
`NH,‘
`[NSPELCH2]-1 so that a good estimation of the noise and
`interference level can be obtained from the “cliannel—free”
`
`IFFT samples. Since LCM can be significantly larger than the
`regular (7? length (denoted as I..(_.,,) used in an 0l~'l')M system
`(for non-OFIJM that does not define a (_‘P length. the duration
`
`10
`
`10
`
`

`
`7
`
`US ?,599,327 B2
`
`ofa regular CP, or Lap. is cfien chosen based on the excessive
`delay spread of the channels encountered in a deployment, as
`discussed before).
`the allowed N,,, can be significantly
`reduced. To improve the ntunber of shifts available for other
`non-initial ranging functions. the initial ranging can be con-
`lined to a certain number of(say NM ') suh-bands or1 which the
`allowed rturnh-er of shifls is. only for example. N_p,,'=[N_9P/
`LCPG]-l. But on the remaining Nb,-Nb,‘ sub-bands. wltere
`only tton-initial ranging is allowed. the number of shifts can
`be increased to N,,,=|_N_,‘,,fl,c.,sj—l. Often. the total ranging
`opp-orttutities increases. If initial ranging is allowed on only
`Nb ,'(<Nb 1) sub-bands, the number of initial ranging opportu-
`nity is then N,,,'*Nc*N,,,'. If initial ranging is allowed on all
`suh-hands, the total number of all ranging oppor1unities is
`N_,,,'*NL_"‘Nb,. of which a portion may be assigned to initial
`ranging.
`Periodic-ranging transmissions are sent periodically for
`system periodic ranging. Bandwidth-requests transmissions
`are for requesting uplink allocations from the BS. These
`non-initial ranging transmissions may he sent only by SS2:
`that have already synchronized to the system. These trans-
`missions can also use the additional OFDM symbols if these
`symbols are allocated for ranging in a control message from
`the BS.
`
`Ranging Codes
`It is desirable to use ranging sequences that have low‘ l’./\l-’R
`(peak to average power ratio) and good cross-correlation. A
`large PAPR requires more power backoff in order to avoid
`signal distor1ion.A reduced average transmit power resulting
`from using such power backoff causes a decrease of the
`uplinlt SNR. which can be problematic for the BS to detect the
`ranging signals from tnobile devices with limited power. In
`OI"-‘DM. the I-‘APR is usually n1ucl't higher than that it1 the
`traditional “single-carrier" transmission when the Ol"l.)M
`sub-carriers are modulated with random PSKEQAM symbols.
`For example. the PAPR for the access signals described in
`drafts and a published version of the IEEE 802.16 standard
`are in the range of6.5 to 12 dB.
`111 terms of the other important sequence characteristic—
`the cross correlation, since distinct ranging signals can it1ter—
`fere with each other. a good cross correlation among them can
`mitigate the interference. which results in improved detection
`rate and reduced false alarm. The presence of other ranging
`codes on the same set of sub-carriers and at the satne cyclic
`shift may severely distort the estimation of the desired chan-
`nel if the cross correlation property is unsatisfactory. This
`results in low detection rate and high false alarm rate even just
`for the purpose of detecting the presence of a ranging code,
`needless to say the goal of obtaining accurate channel knowl-
`edge. The performance becomes ntore and tnore unaccept-
`able as the channel conditions become worse (for example.
`under larger delay spread) or the number of ranging users
`increases.
`
`In some embodiments of the present invention, the ranging
`signal uses access sequences that have good PAPR and cross
`correlation. In one embodiment of the invention, tl1e set of
`sequences can come from a search of a special
`type of
`sequences such as rand