(12) United States Patent
`Jones, IV et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,657,949 B1
`Dec. 2, 2003
`
`US006657949B1
`
`(54) EFFICIENT REQUEST ACCESS FOR OFDM
`SYSTEMS
`
`(75) Inventors: Vincent K. Jones, IV, Redwood
`Shores, CA (US); James M. Gardner,
`San Jose, CA (US)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(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) Appl. No.: 09/348,718
`(22) Filed:
`Jul. 6, 1999
`
`(51) Int. Cl.7 ................................................ .. H04L 5/04
`(52) US. Cl. ...................................... .. 370/205; 370/439
`(58) Field of Search ............................... .. 370/204, 205,
`370/208, 210, 230, 230.1, 278, 280, 281,
`329, 330, 437, 438, 439
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1994 Fattouche et al.
`5,282,222 A
`5,909,436 A * 6/1999 Engstrom et al. ......... .. 370/343
`5,963,557 A * 10/1999 Eng ............... ..
`370/432
`6,031,827 A * 2/2000 Rikkinen et al.
`370/330
`6,052,594 A * 4/2000 Chuang et al.
`455/450
`6,175,550 B1 * 1/2001 Van Nee ......... ..
`370/206
`6,192,026 B1 * 2/2001 Pollack et al.
`370/203
`6,327,314 B1 * 12/2001 Cimini, Jr. et al.
`375/340
`6,333,937 B1 * 12/2001 Ryan .............. ..
`370/468
`6,370,153 B1 * 4/2002 Eng ........ ..
`370/438
`6,515,960 B1 * 2/2003 Usui et al. ................ .. 370/203
`
`OTHER PUBLICATIONS
`
`Speth, M. et al “Minimum Overhead Burst Synchronization
`for OFDM Based Broadband Transmission” Global Tele
`communications, vol. 5, Nov. 8—12, 1998, pp. 2777—2782.*
`Morelli, M. “An Improved Frequency Offset Estimator for
`OFDM Applications” IEEE Communications Letters, vol. 3,
`Issue 3, Mar. 1990, pp. 75—77.*
`
`Ayanoglu, E. “Adaptive ARQ/FEC for Multitone Transmis
`sion in Wireless Networks” Global Telecommunications,
`vol. 3, Nov. 13—17, 1995, pp. 2278—2283.*
`Kumagai, T. et al “A Maximal Ratio Combining Frequency
`Diversity ARQ Scheme for OFDM Signals” Personal,
`Indoor and Mobile Radio, vol. 2, Sep. 8—11, 1998, pp.
`528—532.*
`Pollack et al., “Medium access control protocol for OFDM
`Wireless networks”, 1998, US. patent application No.
`09/019,938.
`Jones et al., “Differential OFDM using multiple receiver
`antennas”, 1999, US. patent application No. 09/282,589.
`Jones et al., “Improved system for interference cancella
`tion”, 1999, US. patent application No. 09/234,629.
`
`* cited by examiner
`
`Primary Examiner—Hassan KiZou
`Assistant Examiner—Anh Vu Ly
`(74) Attorney, Agent, or Firm—Ritter, Lang & Kaplan LLP
`(57)
`ABSTRACT
`
`Systems and methods for efficient multiplexing of multiple
`access requests from disparate sources Within a single
`OFDM burst. Each of multiple subscriber units employ
`non-overlapping groups of OFDM frequency domain sym
`bols Within a single burst for upstream transmission of their
`access requests. In one embodiment, the OFDM frequency
`domain symbols are differentially encoded to eliminate the
`need for transmission of upstream training information. In
`an alternative embodiment, the group of frequency domain
`symbols Within the burst employed by any particular sub
`scriber unit are contiguous to one another. Channel training
`for a give subscriber unit need only be performed over the
`subband occupied by its group of frequency domain sym
`bols. This greatly reduces the number of training symbols
`required for reception. The reduction or elimination of
`training symbols increases the number of access requests
`that may be accommodated Within a single burst and/or
`alloWs for greater redundancy in transmission of access
`request data.
`
`32 Claims, 10 Drawing Sheets
`
`Page 1 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 1 0f 10
`
`US 6,657,949 B1
`
`1 00 —\
`
`Y /— I04
`Subscriber
`
`1 04
`
`Y /
`Subscriber
`
`Y [104
`Subscriber
`
`Y [102
`
`Head End
`
`Y?'”
`
`Subscriber
`
`Y [104
`
`Subscriber
`
`FIG. 1
`
`Page 2 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 2 0f 10
`
`US 6,657,949 B1
`
`Page 3 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 3 0f 10
`
`US 6,657,949 B1
`
`(See Fig- 28)
`
`RAZ _ &\\\\\\\\\\\\\\\\\\\\\\\\\\\\\v
`End Zeros
`W Zeros
`
`d1__N
`%
`d1 N-I
`
`/—200
`
`d1_3
`dl_2
`
`d1 1 5mm Middle
`FIG. 2A
`
`Zeros
`
`dl_ N
`
`d1 N-l
`
`55'
`VIN
`£\\\\\\\\\\\\\\\\\\\\‘
`
`Page 4 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 4 0f 10
`
`US 6,657,949 B1
`
`(See Fig. 2C)
`
`End Zeros
`
`Zeros
`
`(12
`§\\\\\\\\\\\\\\\\\\‘
`d2 N-l
`
`(123
`d2: 1
`
`Middle
`Zeros
`
`FIG. 2B
`
`RA2
`
`N
`mm
`
`\
`200
`
`RAli
`
`(See Fig. 2A)
`
`Page 5 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 5 0f 10
`
`US 6,657,949 B1
`
`l | I | l | l
`
`Zeros
`End Zeros
`
`Zeros
`
`% 2
`
`%...FE ‘z I “J
`
`dN_3
`dN_2
`dN__ l
`
`FIG.2C
`
`Zeros
`
`dN__ N
`\§
`dN N-l
`
`dN_3
`dN_2
`dN_ 1
`E\\\\\\\\\\\\\\\\\\\
`Zeros
`
`_
`
`.
`
`N (See Fig. 2B)
`
`200\
`
`RA2|
`
`Page 6 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 6 0f 10
`
`US 6,657,949 B1
`
`mohoN
`
`dlN
`dlN-l
`dlN-2
`
`d1
`
`1
`
`86M
`
`m UFN
`
`dlN
`dlN-l
`d1N-2
`
`l
`
`mobN
`
`Page 7 of 19
`
`

`
`U.S. Patent
`
`3m
`
`hS
`
`07
`
`US 6,657,949 B1
`
`
`
` 2,2»M.“u8.2u:uUm.B§z
`
`
`
`TBm:Z..o
`
`Eouamm
`
`8»/:8»
`
`w2:3»me.
`
`ma:flonfimmmoas0gm2%.as:H8.8mB30
`
`E»
`
`.8=_Em§fi.
`
`Sufism
`
`Hm”:
`
`V.U~n~
`
`Page 8 of 19
`
`Page 8 of 19
`
`
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 8 0f 10
`
`US 6,657,949 B1
`
`m2
`
`s5
`
`
`
`Al! koqwwnswom
`
`4m
`
`880
`35:50
`
`dououhoO
`
`.
`
`
`
`a5 ._ 5a “a?
`
`z m » wk. . . P 285%
`
`
`< u \l 28 Sam A] HHHE Al. 6230
`3m E28 /l 8“ \\
`
`. _
`
`_
`
`“ KN: m m u
`
`+
`
`m 8“
`
`M
`
`m2 889$
`
`5308M
`
`
`
` ( Hlhow?zio 2m @555
`
`
`< r (NR. 35.?
`
`
`
`0802: W03
`
`
`0225 @5529 8m
`
`3:25am 1/!
`
`mobN was $952
`$5 (3
`
`Page 9 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 9 0f 10
`
`US 6,657,949 B1
`
`
`
`man @%|\ week
`
`w .bhm
`will 0 38+ 953mm _ w .
`
`
`
`
`
`
`
`AN ~mn- , .3“
`
`man
`
`8 E80
`
`
`
`QR\\\\ S m 5028M 112K
`
`698:2
`
`“88260
`
`m .m?k
`
`cm“ 839$ 5| “5560M ‘In 33 5WD All 8mg;
`
`
`
`m: a /I won KNE
`
`
`SEEmSEH Sc Eon m o o .
`
`/| on oh “FE w w 0
`
`£55m w?wov
`
`8.8 g
`
`Page 10 of 19
`
`

`
`U.S. Patent
`
`Dec. 2, 2003
`
`Sheet 10 0f 10
`
`US 6,657,949 B1
`
`Sum § @260
`
`
`
`llllllallllu aorm?n?ou
`
`365%:
`
`(‘may
`
`83E
`mESEEQmQQ Al
`/| 8%
`
`_ .Em
`
`M 839mm 1 523mm
`RHNQQ
`
`% .bwm
`
`m m
`
`Hangman 82E .
`
`
`
`/l new
`
`
`
`
`w?wooo? Al. mEEEEQMQQ “2 .FE Al mmioowumm
`K5,,
`
`2 2 m E m.»
`
`/& gm
`k
`
`Page 11 of 19
`
`

`
`US 6,657,949 B1
`
`1
`EFFICIENT REQUEST ACCESS FOR OFDM
`SYSTEMS
`
`STATEMENT OF RELATED APPLICATIONS
`
`The present application is related to the subject matter of
`the following previously ?led US. Patent Applications.
`US. patent application Ser. No. 09/019,938, entitled
`MEDIUM ACCESS CONTROL PROTOCOL FOR OFDM
`WIRELESS NETWORKS, ?led on Feb. 6, 1998. US.
`patent application Ser. No. 09/282,589, entitled DIFFER
`ENTIAL OFDM USING MULTIPLE RECEIVER
`ANTENNAS, ?led on Mar. 31, 1999.
`US. patent application Ser. No. 09/234,629, entitled
`SYSTEM FOR INTERFERENCE CANCELLATION, ?led
`on Jan. 21, 1999.
`The co-?led, co-assigned US. Patent Application entitled
`OPTIMAL USE OF REQUEST ACCESS TDMA SLOTS
`FOR AUTOMATIC LEVEL CONTROL is also related to
`the subject matter of the present application.
`All of the related patent applications are herein incorpo
`rated by reference.
`
`10
`
`15
`
`20
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates to digital communication
`systems and more particularly to digital communication
`systems employing orthogonal frequency division multi
`plexing (OFDM).
`A point to multipoint Wireless communication system
`represents a potentially effective solution to the problem of
`providing broadband netWork connectivity to a large number
`of geographically distributed points. Unlike optical ?ber,
`DSL, and cable modems, there is no need to either construct
`a neW Wired infrastructure or substantially modify a Wired
`infrastructure that has been constructed for a different pur
`pose.
`In order to conserve scarce spectrum, the data communi
`cation devices of a point to multipoint Wireless communi
`cation system may all share access to a common frequency.
`In a typical scenario one or more frequency channels are
`allocated to doWnstream broadcast communication from a
`central access point to a plurality of subscriber units and one
`or more separate frequency channels are allocated to
`upstream communication from the subscriber units to the
`central access point. For upstream communication there is a
`medium access control (MAC) protocol that determines
`Which subscriber unit is permitted to transmit at Which time
`so as not to interfere With transmission from other subscriber
`units. For a given upstream frequency, the time domain is
`divided into frames Which are typically of equal duration
`Where each frame represents an individually allocable unit in
`the time domain. For frames transmitting upstream data, one
`subscriber unit transmits in each frame. Certain other frames
`are, hoWever, reserved for access requests by subscriber
`units. The access request frames are not reserved for any
`particular subscriber unit in advance. Any subscriber unit
`Wishing to transmit data upstream may transmit its access
`request in the access request frame. If multiple subscriber
`units transmit simultaneously in an access request frame
`there is a collision. The colliding subscriber units Will detect
`the collision and attempt to retransmit their access request
`after a Wait period that is de?ned pseudo-randomly at each
`subscriber unit so as to reduce the probability of further
`collisions.
`Orthogonal frequency division multiplexing (OFDM)
`systems offer signi?cant advantages in many real World
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`communication systems, particularly in environments Where
`multipath effects impair performance. OFDM divides the
`available spectrum Within a channel into narroW subchan
`nels. In a given so-called “burst,” each subchannel transmits
`one data symbol. Each subchannel, therefore, operates at a
`very loW data rate compared to the channel as a Whole. To
`achieve transmission in orthogonal subchannels, a burst of
`frequency domain symbols are converted from the time
`domain by an inverse Fast Fourier Transform (IFFT) pro
`cedure. To assure that orthogonality is maintained in dis
`persive channels, a cyclic pre?x is added to the resulting
`time domain sequence. The cyclic pre?x is a duplicate of the
`last portion of the time domain sequence that is appended to
`its beginning. To assure orthogonality, the cyclic pre?x
`should be as long as the duration of the impulse response of
`the channel. It is desirable to use OFDM in point to
`multipoint netWorks Where multipath effects are a concern.
`Upstream access requests typically contain very little
`data. Using an entire frame for an access request from a
`single subscriber unit is therefore very inef?cient. One
`solution is to multiplex multiple access requests from mul
`tiple subscriber units Within the same frame in a Way that
`avoids collisions. In an OFDM system one Way to accom
`plish this is to allocate different frequency domain subchan
`nels to different subscriber units so that multiple subscriber
`units effectively share an OFDM burst and may each trans
`mit their oWn access request Within their oWn grouping of
`subchannels. Such a technique is disclosed in US. patent
`application Ser. No. 09/019,938.
`To assure maximum performance, an OFDM burst car
`rying data from a subscriber unit should contain v frequency
`domain training symbols having predetermined values to
`assist the receiver in estimating the channel response Where
`vis greater than or equal to the number of symbol periods in
`a duration of the impulse response from the subscriber unit
`to the central access point. Symbols used for training are
`then unavailable for transmission of data. Loss of ef?ciency
`due to the inclusion of training symbols is compounded
`Where multiple subscriber units share a single OFDM burst.
`In the system described in US. patent application Ser. No.
`09/019,938, each subscriber unit must transmit v training
`symbols as part of its oWn grouping Within the access
`request OFDM burst. Thus Within a single OFDM burst,
`there are R*v symbols devoted to training Where R is the
`number of subscriber units sharing the burst. What is needed
`are systems and methods for more ef?ciently multiplexing
`transmissions of multiple subscriber units Within the same
`OFDM burst.
`
`SUMMARY OF THE INVENTION
`Systems and methods for efficient multiplexing of mul
`tiple access requests from disparate sources Within a single
`OFDM burst are provided by virtue of the present invention.
`Each of multiple subscriber units employ non-overlapping
`groups of OFDM frequency domain symbols Within a single
`burst for upstream transmission of their access requests. In
`one embodiment, the OFDM frequency domain symbols are
`differentially encoded to eliminate the need for upstream
`transmission of training information. In an alternative
`embodiment, the group of frequency domain symbols Within
`the burst employed by any particular subscriber unit are
`contiguous to one another. Channel training for a given
`subscriber unit need only be performed over the subband
`occupied by its group of frequency domain symbols. This
`greatly reduces the number of training symbols required for
`reception. The reduction or elimination of training symbols
`increases the number of access requests that may be accom
`
`Page 12 of 19
`
`

`
`US 6,657,949 B1
`
`3
`modated Within a single burst and/or allows for greater
`redundancy in transmission of access request data.
`One aspect of the present invention provides apparatus for
`operating a selected data communication device to request
`access to a shared medium employed by a digital commu
`nication system. The apparatus includes a burst forming
`system that forms frequency domain symbols of an OFDM
`burst. A?rst group of frequency domain symbols Within the
`burst includes differentially encoded data and a second
`group of frequency domain symbols in the burst includes
`Zero values to alloW for data transmitted by other data
`communication devices. The apparatus further includes a
`converter that transforms frequency domain symbols of the
`OFDM burst into time domain symbols, and a transmitter
`system that transmits the time domain symbols as a request
`for access to the shared medium.
`Further understanding of the nature and advantages of the
`invention herein may be realiZed by reference to the remain
`ing portions of the speci?cation and the attached draWings.
`
`10
`
`15
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 depicts a point to multipoint communication
`netWork suitable for implementing one embodiment of the
`present invention.
`25
`FIGS. 2A—2C depict the internal structure of an OFDM
`request access burst incorporating reduced training informa
`tion according to one embodiment of the present invention.
`FIG. 3 depicts internal structure of an OFDM request
`access burst incorporating differential coding according to
`one embodiment of the present invention.
`FIG. 4 depicts apparatus for transmitting the request
`access burst of FIG. 2 according to one embodiment of the
`present invention.
`FIG. 5 depicts apparatus for receiving the request access
`burst of FIG. 2 according to one embodiment of the present
`invention.
`FIG. 6 depicts apparatus for performing channel training
`on a subband of the request access burst of FIG. 2 according
`to one embodiment of the present invention.
`FIG. 7 depicts apparatus for transmitting the request
`access burst of FIG. 3 according to one embodiment of the
`present invention.
`FIG. 8 depicts apparatus for receiving the request access
`burst of FIG. 3 according to one embodiment of the present
`invention.
`
`35
`
`45
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`FIG. 1 depicts a point to multipoint Wireless communi
`cation netWork 100 suitable for implementing one embodi
`ment of the present invention. NetWork 100 includes a
`central access point or headend 102 and multiple subscriber
`units 104. All communication is typically either to or from
`central access point 102. Communication from central
`access point 102 to one or more subscriber units 104 is
`herein referred to as doWnstream communication. Commu
`nication from any one of subscriber units 104 to central
`access point 102 is herein referred to as upstream commu
`nication. In one embodiment, different frequencies are allo
`cated to upstream and doWnstream communication. In some
`alternative embodiments, subscriber units 104 may commu
`nicate With one another directly.
`Each of one or more upstream frequencies is common to
`multiple subscriber units. To prevent collisions betWeen
`subscriber units When accessing the shared medium to
`
`55
`
`65
`
`4
`transmit data upstream, a medium access control (MAC)
`protocol is provided. For each upstream frequency, the time
`domain is divided into frames or slots. An individual frame
`may be allocated for upstream data transmission by a
`particular subscriber unit. The schedule of Which subscriber
`units are permitted to transmit in Which frames is distributed
`in a scheduling message sent doWnstream by central access
`point 102. In a typical system, When a particular subscriber
`unit Wishes to transmit data upstream, it sends a special
`transmission knoWn as an access request upstream to central
`access point 102 to request access to the shared medium.
`Particular frames or slots are reserved for transmission of the
`access request. According to the present invention, multiple
`subscriber units may transmit access requests upstream
`Within the same access frame Without causing a collision.
`NetWork 100 may employ OFDM. The abbreviation
`“OFDM” refers to Orthogonal Frequency Division Multi
`plexing. In OFDM, the available bandWidth is effectively
`divided into a plurality of subchannels that are orthogonal in
`the frequency domain. During a given symbol period, the
`transmitter transmits a symbol in each subchannel. To create
`the transmitted time domain signal corresponding to all of
`the subschannels, an FFT is applied to a series of frequency
`domain symbols. The resulting time domain burst is aug
`mented With a cyclic pre?x prior to transmission. The cyclic
`pre?x addition process can be characteriZed by the expres
`s1on:
`
`On the receive end, the cyclic pre?x is removed from the
`received time domain symbols. An IFFT is then applied to
`recover the simultaneously transmitted frequency domains
`symbols. The cyclic pre?x has length v Where v is greater
`than or equal to a duration of the impulse response of the
`channel. The cyclic pre?x assures orthogonality of the
`frequency domain subchannels.
`There are other Ways of creating transmitted bursts of
`symbols in orthogonal subchannels or substantially orthogo
`nal subchannels including, e. g., use of the Hilbert transform,
`use of the Wavelet transform, using a batch of frequency
`upconverters in combination With a ?lter bank, etc. Wher
`ever the term OFDM is used, it Will be understood that this
`term includes all alternative methods of simultaneously
`communicating a burst of symbols in orthogonal or substan
`tially orthogonal subchannels de?ned by procedures per
`formed on a time domain sequence. The term frequency
`domain should be understood to refer to any domain that is
`divided into such orthogonal or substantially orthogonal
`subchannels.
`FIGS. 2A—2C depict the contents of a request access
`OFDM burst according to one embodiment of the present
`invention Wherein each of multiple subscriber units are
`allocated contiguous subgroups of OFDM frequency
`domain symbols. In the discussion that folloWs, the fre
`quency domain symbols are also referred to as “tones.” An
`OFDM request access (RA) burst includes data tones, chan
`nel training tones and Zero tones. FIGS. 2A—2C shoW the
`tone positions as they Would appear at the receiver end. At
`either end of the burst, there are Nedge Zero tones Where
`Nedge equals betWeen (N—v)/ 10 and (N—v)/20 Where N is the
`IFFT siZe and v is the number of training symbols to be
`included Within the burst.
`Besides the edge tones, the remaining tones are evenly
`divided into Nuser RA tone sets of siZe Nm. Each subscriber
`unit transmits using only one of the RA tone sets and sets the
`remaining tone sets to have Zero value. When requesting
`access, each subscriber unit pseudo-randomly determines
`
`Page 13 of 19
`
`

`
`US 6,657,949 B1
`
`5
`the tone set that it Will use. Each RA tone set contains N"
`training tones that in the depicted example occupy every
`fourth tone starting With the ?rst tone in the tone set. The
`training tones Will have one of four values:
`
`6
`The phase scrambling pattern consists of a series of values
`ranging from 0 to 3. Aphase scrambling storage block 410
`generates the values of the pattern in succession. Acomplex
`exponential block 412 represents the translation of the
`values ranging from 0 through 3 into four possible phase
`rotation values: 0, 31/2, at, 375/2. Aphase rotator 414 applies
`the phase scrambling phase shifts to the Zero-?lled and
`repetition coded RA symbols. Atraining tone selection block
`416 generates training tones at the appropriate positions
`depending on the RA tone sets selected by random number
`generator 406. A multiplexer 418 selects betWeen the Zero
`?lled redundant sets of RA data symbols and the training
`tones depending on the position Within the burst. The output
`of multiplexer 418 is the complete set of frequency domain
`symbols for the burst as transmitted by a particular sub
`scriber unit 104.
`IFFT block 420 converts the frequency domain symbol
`burst into a time domain symbol burst and af?xes the cyclic
`pre?x to the beginning of the time domain symbol burst. A
`transmitter system 422 performs all additional digital and
`analog signal processing necessary to generate an RF signal
`for transmission over the airWaves Where the RF signal has
`been modulated using the baseband time domain symbols
`output by IFFT block 420. Transmitter system 422 transmits
`the RF signal upstream via an antenna 424.
`FIG. 5 depicts a system 500 for receiving and processing
`the OFDM RA burst of FIGS. 2A—2C. System 500 Would
`typically be implemented at central access point 102. Sys
`tem 500 takes advantage of signals received via MR antennas
`502. HoWever, the present invention may also be applied in
`the context of receivers only employing a single antenna.
`For each antenna 502, there is a receiver system 504.
`Receiver system 504 performs all of the analog and digital
`signal processing operations necessary to recover baseband
`time domain symbols from the modulated RF signal
`received via the antennas 502. A series of FFT blocks 506
`remove the cyclic pre?x from successive time domain
`OFDM bursts and convert the time domain OFDM bursts to
`the frequency domain using the FFT. A group of selection
`blocks 508 then separate the tones from each RA tone set
`depicted in FIGS. 2A—2C. The selection blocks 508 are
`aWare of a number of users 510 for Which RA OFDM burst
`200 has been con?gured. Each selection block 508 outputs
`data tone values and Zero tone values for all subscriber units
`as received via a particular antenna. Each selection block
`508 also outputs training values for each user as received by
`a particular one of antennas 502.
`Channel estimations are performed separately for each
`subscriber unit based on the training tones Within the sub
`scriber unit’s RA tone set. According to the present
`invention, each RA tone set in burst 200 includes a number
`of training tones suf?cient to establish channel response
`Within the tone set but not over the burst as a Whole. An
`interpolation technique is used to establish the channel
`response over all the tones of the tone set based on the
`training tone values as received. Each of a series of inter
`polation ?lters 512 obtains the channel response for a single
`combination of antenna and RA tone set. The predetermined
`training tone values as transmitted are obtained from an
`inverse phase sequence/training tone block 514.
`Each of interpolation ?lters 512 operates as folloWs. Let
`the vector Zr be the ideal N" training tones in an RA tone set,
`and the vector XU- be the received values from antenna i for
`the training tones. An estimate of the channel at the training
`tone positions is formed by a quotient block 602 taking the
`quotient of these tWo values:
`
`Where the amplitude A Will depend on Which constellation
`type (e.g., 4-QAM, 16-QAM) is being used for data. This
`choice of training tone values removes the need for any
`division or multiplication of these values in the channel
`estimation processing. The number of training tones in each
`RA tone set may be less than the impulse response duration
`in symbol periods.
`Each tone set includes Nm tones. The remaining N’“—Nn
`tones are used to transmit the subscriber unit’s access
`request data and some Zero tones. To increase the probability
`of accurate reception of the access request data even under
`dif?cult channel conditions, the access request data is dupli
`cated Nred times to implement repetition coding. For each
`repetition of the data there are Nzm Zero tones. Furthermore,
`at the beginning of the RA tone set there are NZS Zeros and
`at the end of the RA tone set there are Nze Zero tones. Each
`repetition of the data includes Ndam data tones so that each
`RA tone set includes Nd=NdamNred data tones. Zero tones
`are positioned to ensure that the data tones are centered
`Within the training tones, that the training tones are spaced
`evenly across RA tone sets as seen by the receiver, and that
`there is equal spacing betWeen all redundant data tones
`Within a tone set.
`FIG. 4 depicts a system for generating and transmitting a
`single RA tone set Within request access burst 200 as Will be
`generated by a single subscriber unit. Binary request access
`data is input into a symbol mapper 402. The request access
`data is has preferably been coded employing error correction
`coding techniques such as convolutional coding, block
`coding, Reed-Solomon coding, etc. A random number gen
`erator 406 selects for each access request the particular RA
`tone set that Will be used by the subscriber unit. A redundant
`symbol formation block 404 positions the RA data symbols
`Within the burst and creates the redundant data sets as shoWn
`in FIGS. 2A—2C. A Zero-?lling block 408 positions the Zero
`tones Within the burst including the Zero values correspond
`ing to the non-selected RA tone sets.
`The phases of the frequency domain symbols Within the
`RA burst are scrambled prior to transmission. The phases are
`scrambled according to a scrambling pattern or scrambling
`code that assigns a scrambling phase value to each tone
`position Within the burst. Each RA tone set therefore has its
`oWn unique section of the phase scrambling pattern. The
`reason for the phase scrambling is that certain combinations
`of request access data symbols Will result in an excessive
`peak to mean poWer ratio (PMPR) for the burst as received.
`If the phase scrambled symbol values generated for a
`particular request access burst result in excessive PMPR, the
`receiver FFT Will saturate resulting in a failed access
`request. In response to the lack of acknowledgement, the
`access request Will be retransmitted. NoW, hoWever, random
`number generator 406 Will likely select a different RA tone
`set for use in requesting access. The request access tones Will
`be shifted to a different portion of the burst and subject to
`phase scrambling by a different section of the phase scram
`bling pattern giving rise to a different PMPR value.
`Repeated transmissions using different RA tone sets Will
`quickly result in a successful transmission that does not
`saturate the receiver FFT. It is highly probable that the
`second transmission Will be successful if the ?rst transmis
`sion results in saturation.
`
`1O
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`Page 14 of 19
`
`

`
`US 6,657,949 B1
`
`7
`Where the symbol + represents element-by-element division.
`Since Z, is de?ned as given earlier, this operation does not
`require any multiplies or divides.
`An estimate of the channel at the data tones is formed by
`interpolating II”. This is done by ?rst extending IAIN, Zero
`stuf?ng the resultant extended vector With rim-1 Zeros, and
`convolving the Zero-stuffed vector With an interpolation
`?lter, G, of length 2L+1. Therefore:
`1. Let IAIU- be a vector of values IAIU- an extrapolation block
`604 forms
`Hm,’Fmwm??highm],
`Where
`
`Hlow,,(n)=Hm(1)-n(Hm(2)-Hm(1)),n=1 .
`
`. .L
`
`Hhightyl-(n)=Hm-(Nn)—n HM-(NTT—1)—HM-(N7T)),n=1 .
`
`. .L
`
`2. An upsampler 606 Zero-stuffs according to:
`
`Hextt’i=[HextM-(1)OO .
`
`.
`
`. OHextM-(DO .
`
`.
`
`. ]
`
`3. A ?lter block 608 then ?lters according to:
`
`10
`
`15
`
`8
`
`Where RW(n)=E[W(n)W*(n)] is the (siZe MR X MR) spatial
`covariance matrix of the interference and noise at tone n, II]
`is an MR-length vector of the estimated channel values from
`user j at tone n, and X(n) is an MR-length vector of received
`symbols at tone n. Details of computing the spatial covari
`ance matrix are described in Us. patent application Ser. No.
`09/234,629. The Weighted-Euclidean cost function is com
`puted as folloWs:
`1. Antenna Combining and Channel Correction:
`
`MR
`2 19,-, Ara/vi grim-(n)
`
`[:l
`
`2. Channel Con?dence:
`
`25
`
`Mr
`
`The number of complex operations required to form IAIl-(n)
`for each data tone in an RA slot, neglecting multiplications
`involving Zero, is (2L+1)N,edNdam. This channel estimation
`technique provides an adequate estimate over a particular
`subband even When the number of training tones is less than
`the number of symbol periods in the channel impulse
`response from the subscriber unit to the central access point.
`Inverse phase sequence/training tone block 514 outputs an
`inverse phase scrambling pattern that is an inverse of the
`phase scrambling pattern applied at the subscriber units 104.
`A set of phase rotators 516 for each antenna 502 applies the
`phase rotation to undo the effects of phase scrambling. A
`channel correction and antenna combining block 518 cor
`rects the access request data as received based on the
`measured channel response, optimally combines the request
`access data as received via the multiple antennas 502, and
`furthermore optimally combines the multiple repetitions of
`data Within each RA tone set. The output of block 518 is a
`series of cost metric or soft decision values for each bit
`Which can then be used by a Viterbi decoder or trellis
`decoder to remove the effects of convolution encoding. A
`later stage or stages can then remove the effects of other
`error correcting codes applied at the transmit end. The
`operation of block 518 Will ?rst be explained With reference
`to an embodiment Wherein there is no repetition of data
`Within an RA tone set.
`After conversion to the frequency domain, the receive
`value for each symbol is:
`
`35
`
`45
`
`55
`
`Constellation bit mapping (CBM) is used to determine the
`cost metrics of each bit in the symbol at tone n. Details of
`CBM are described in Us. patent application Ser. No.
`09/234,629. The interference energy, ozij-(n) is calculated as
`
`Where Zij-(n) is the nearest ideal QAM value to 2m, and 2M
`is the single antenna corrected symbol value:
`
`The expectation ozij-(n) is performed across all the data
`tones in an RA. Thus, there Will be one poWer estimate for
`each RA slot and each antenna.
`The above technique can be modi?ed With bursts that
`employ redundancy as in FIGS. 2A—2C. The data should be
`coherently combined across redundant subsets Within each
`tone set. In the antenna combining and channel correction
`step each redundant set of data is treated as originating With
`a separate antenna.
`Interference energy estimates are, hoWever, averaged over
`redundant subsets, so that there is only one value of 02,-]- for
`each user and each antenna. The Weighted-Euclidean cost
`function is then obtained by:
`
`where X- and Wi are the frequency domain received symbol
`and noise/interference values at tone position n.
`The term Hij-(n) is the channel response at tone n from user
`j to antenna i. The term
`is the transmitted symbol by
`user j in tone n. The use of both j and n is redundant since
`for any tone value n, there is just one user j. HoWever, this
`notation Will be used in order to emphasiZe certain aspects
`of the processing.
`The maximum likelihood solution for decoding the
`received symbols When there is no redundancy in an RA tone
`set is
`
`65
`
`melred [:1
`
`Where Jred is the set of tones n that have redundant data.
`
`Page 15 of 19
`
`

`
`US 6,657,949 B1
`
`Then,
`
`Mr
`
`melred [:1
`
`Constellation bit mapping is performed for each com
`bined symbol Z(n) as described earlier.
`FIG