Ulllted States Patent
`
`[19]
`
`[11] Patent Number:
`
`6,018,528
`
`Gitlin et al.
`
`[45] Date of Patent:
`
`*Jan. 25, 2000
`
`US006018528A
`
`6/1993 Wagner .
`11/1993 Schilling ............................... .. 375/203
`12/1993 Faulkner et al.
`.
`3/1994 Gudmundson ........................ .. 375/205
`Eulghum 6‘ ah
`370230
`7;1996 Dzigafififi ““““"
`5’539’730
`370/337
`.
`11/1996 Malkamaki et al.
`5:577:024
`5,581,548 12/1996 Ugland et al.
`........................ .. 370/337
`
`
`
`5,221,983
`5,260,967
`5,272,556
`5,295,153
`
`Primary Examiner—Huy D. V11
`Attorney, Agent, or Firm—Jose R. de la Rosa
`[57]
`ABSTRACT
`
`A system and method for optimizing usage of a communi-
`cations transmission medium. The transmission medium
`may be sliced into time and frequency domains so as to
`create time-frequency slices for assignment to users having
`Varymg 399955 hates and u5ef'aPP11Cat10U req111heTf1emS~
`Through Schedhhhg 0f ‘h? Vahhhs Speed users Whhlh the
`frequency and time domains, the system and method can
`etfficlgnfly allocatedarld mfikehuse of the avallable, Spectrum’
`t ere
`accommo ating ig ‘er rate users. requiring greater
`bandwidths and time slot assignments While still preserving
`cost-efficient access for lower speed users. Depending on the
`signal modulation scheme, the time-frequency slices may be
`allocated on non-contiguous frequency bands. The system
`and method is also applicable to code-division multiple
`access (CDl\/IA) techniques. by slicing the available. code
`space along time-code domains, frequency-code domains or,
`in three dimensions, along time-frequency-code domains.
`US“? may be efficlently .S°l.“’d“1‘°'d lfsfid 0“ °°d‘°’. SP*.“"°'
`requirements so as to optimize use o t e communication
`med1um~
`
`15 Claims, 8 Drawing Sheets
`
`[54]
`
`[75]
`
`SYSTEM AND METHOD FOR OPTIMIZING
`SPECTRAL EFFICIENCY USING TIME-
`FREQUENCY_CODE SLICING
`
`Inventors: Richard D. Gitlin, Little Silver;
`Zygmunt Haas, Holmdel; Mark J.
`Kamh Fair Haw“; Clark W°°dW°”h>
`R1HhS0h> a110f N1
`
`[73] Assignee: AT&T Corp, Middletown, N.J.
`
`[*] Notice:
`
`This patent is subject to a terminal dis-
`claimer.
`
`[21] Appl. No.: 08/234,197
`.
`.
`Apr‘ 28’ 1994
`Ffled‘
`[22]
`Int. Cl.7 ...................................................... .. H04J 4/00
`[51]
`[52] U.s. Cl.
`.......................... 370/436; 370/441; 370/468;
`370/478; 370/479; 375/201
`[58] Field of Search .................................. 370/50, 18, 19,
`370/20’ 330’ 436’ 437’ 478’ 329’ 335’ 336’
`337’ 342’ 343’ 345’ 431’ 441’ 442’ 465’
`479’ 480’ 498’ 535’ 536’ 537’ 546’ 477’
`468. 375/200 201 202 203 204 205
`’
`’
`’
`’
`’
`’ 206’
`
`[56]
`
`References Cited
`
`US. PATENT DOCUMENTS
`9/1989 Suzuki
`...................................... 370/50
`4/1990 Schwendeman et al
`370/50
`7/1991 Cowart . . . . . . . . . . . . . . . . . .
`. . . . .. 375/206
`7/1992 Freeburg et al.
`..
`.... .. 370/330
`5/1993 Schaeffer et al.
`..................... .. 375/203
`
`4,868,811
`4,914,649
`5,029,180
`5,134,615
`5,210,771
`
`42
`
`F6
`
`40/7 F3
`
`F2
`
`F1
`
`F0
`
`FREQUENCE
`
`BANDS
`
`
`
`CONTROL
`
`S0
`
`S1
`
`S3
`S2
`%/
`44
`TIME SLOTS ———»
`12* HIGH—SPEED USERS: A,B,G,L
`50*MEDIUM-SPEED USERS: C,E,F,H,|,J,M,0,0
`* LOW—SPEED USERS: D,K,N,P,R,S,T
`
`S4
`
`S5
`
`S6
`
`SPRINT 1105
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 1 of 8
`
`6,018,528
`
`TIME
`
`TIME
`
`SLOT SLOT
`
`TIME
`
`SLOT
`
`TIME
`
`SLOT
`
`TIME
`
`SLOT
`
`FIG.
`
`1
`
`TIME
`
`SLOT
`
`TIME
`
`SLOT
`
`TIME
`
`SLOT
`
`1 \
`
`RADlO12345678
`
`FREQUENCY
`
`BAND
`
`4
`
`FRAME»/~2
`
`FIG. 2
`
`RE CHANNELS
`
`12
`
`FREQUENCY 1
`
`CONTROL CIRCUIT
`
`
`
`voICE CIRCUIT
`
`
`
`CONTROL CIRCUIT
`
`FREQUENCY 2
`
`FREQUENCY
`DOMAIN
`
`EREQUENCII3
`
`BANDWIDTH or EACH
`
`CHANNEL TYPICALLY
`
`LESS THAN MHZ
`(IN EACH DIRECTION)
`
`14
`
`ALL voICE CIRCUITS ARE
`FULLY TRUNKED, CONTINUOS
`TRANSMISSION CIRCUITS
`ONE CIRCUIT PER
`
`RF CHANNEL
`
`I
`‘O
`
`FREQUENCY 4
`
`°
`
`V0“ “RCU”
`°
`
`FREQUENCY N
`
`VOICE C|RCUlT
`
`
`
`TIME
`
`-->
`
`INDEPENDENT
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 2 of 8
`
`6,018,528
`
`FIG. 3
`
`20\
`
`2E\
`
`22
`
`A1::7,2;:j:________yF5._____:I:;,::fA
`tnu
`
`1
`
`t
`
`24
`\
`ONE TIME SLOT
`
`23
`/’
`‘\
`28
`
`
`
`
`n
`
`n
`
`fl
`
`UNIVERSAL TIME SLOT
`
`FIG. 4
`
`GUARD—
`BAND
`
`LOW—SPEED
`HEADER
`
`|-||G|-|..3p[ED
`DATA
`
`GUARD-
`BAND
`
`SLOT
`
`PACKET
`
`27
`
`‘
`
`28
`
`23
`
`25
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 3 of 8
`
`6,018,528
`
`FIG. 5
`
`
`
`
`
`52
`
`52
`
`100
`
`F7
`
`F6
`
`F5
`
`F4
`
`F3
`
`F2
`
`F1
`
`,0
`
`42
`
`40/
`
`CE
`
`FRE
`
`BA
`
`
`
`44
`TIME SLOTS
`‘HIGH-SPEED USERS: A,B,G,L
`‘MEDIUM-SPEED USERS: C,E,F,H,|,J,M,O,Q
`é
`ERS: D,K,N,P
`LOW-SPEED US
`,R,S,T
`
`fig
`50
`
`

`

`U.S. Patent
`
`Jan. 25, 2000
`
`Sheet 4 of 8
`
`6,018,528
`
`FIG. 6
`
`S0
`
`S1
`
`S2
`
`S3
`
`S4
`
`S5
`
`S6
`
`44
`
`TIME SLOTS
`
`
`
`USERS: A,B,G,L
`46* H|GH—
`ED USERS: C,E,F,H,|,J,M,O,Q
`§g*MEDIu —
`‘Low-SPEED USERS: D,K,N,P,R,S,T
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 5 of 8
`
`6,018,528
`
`30
`
`S1
`
`S2
`
`S3
`
`S4
`
`S5
`
`S6
`
`44 TIME SLOTS ——»
`-SPEED USERS: A,B,G,L
`:2‘
`M-
`USE
`:
`E,F,H,|,J,M,0,Q
`50*
`*Low-sPE
`ERS:
`,P,R,S,T
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 6 of 8
`
`6,018,528
`
`FIG. 8
`
`
`
`('3(3C7C')C3C5C5()3#5304->CJ'IO5\l
`
`
`
`FREQUENCY BANDS —»
`:g\‘H|GH-SPEED USERS: A,B,G,L
`‘MEDIUM-SPEED USERS: C,E,F,H,|,J,M,0,Q
`50* LOW—SPEED us
`ERS: D,K,N,P,R,S,T
`
`42
`
`

`

`U.S. Patent
`
`Jan. 25, 2000
`
`Sheet 7 of 8
`
`6,018,528
`
`FIG. 9
`
`
`
`A
`
`
`A
`
`44 TIME SLOTS —»
`
`46*H|(3H-SPEED USERS: A,B,G,L
`48 * MEDIU
`50
`-
`ED US
`: C,E,F,H,|,J,M,O,Q
`* LOW-
`USER :
`,N,P,R,S,T
`
`
`
`c4
`
`B
`
`Cn is n’rh code
`
`c7 I 07 M
`
`c7 0
`
`

`

`U.S. Patent
`
`Jan. 25,2000
`
`Sheet 8 of 8
`
`6,018,528
`
`48
`
`46$H|GH-SPEED USERS: F,G,J
`50 \‘MED|UM—SPEED USERS: A,B,C,E
`\‘ LOW-SPEED USERS: D,H,|,K,L,
`
`

`

`6,018,528
`
`1
`SYSTEM AND METHOD FOR OPTIMIZING
`SPECTRAL EFFICIENCY USING TIME-
`FREQUENCY-CODE SLICING
`
`1. TECHNICAL FIELD
`
`The invention relates to a system and method for maxi-
`mizing usage of a communications transmission medium,
`and more particularly, to a system and method for maximiz-
`ing usage of a communications transmission medium while
`preserving optimum access to the medium for users of
`differing access speeds and while maximizing spectral use
`and bandwidth efficiencies.
`
`2. PROBLEM
`
`Many communication systems today, such as the wireless,
`satellite, personal communications, and cellular communi-
`cations systems, typically exhibit certain common require-
`ments. For example,
`to maximize their flexibility,
`these
`communications systems typically require a variety of
`access speeds in order to support differing applications. In
`order to be economically viable, the systems should also
`offer a generally low-cost access for lower-speed users.
`Lastly,
`the systems typically strive for a high degree of
`spectral efficiency in order to maximize usage of the par-
`ticular communications transmission medium.
`
`As is known, certain data transmission architectures have
`been developed in communications systems to allocate
`communication resources to individual users on their
`
`demand. Typically, these architectures ought to be structured
`to permit various users to utilize the resources in a fully
`shared communications system. Thus, the various architec-
`tures are generically referred to as “multiple access” archi-
`tectures.
`
`Referring to FIG. 1, one multiple access architecture for
`maximizing usage of the communications transmission
`medium is commonly referred to as time-division multiple
`access (TDMA). As known to those skilled in the art, in
`TDMA each carrier frequency 1 is severed into one or more
`time frames 2 having a plurality of individual time slots 4.
`Each of the time slots 4 is assigned to a user as an
`independent circuit. Information is transmitted by the user in
`short bursts during assigned or specified time slots, with
`users being scheduled for access to the time slots 4 accord-
`ing to their information transmission requirements. As will
`be appreciated, however, in pure TDMA architecture both
`higher-speed and lower-speed users share a common com-
`munications bandwidth, typically by assigning more time
`slots per frame to the higher-speed users. The drawback of
`this architecture is that high-rate access (high speed data
`bursts)
`is required even for lower-speed users, which
`increases the cost and complexity of the systems employed
`by those lower-speed users.
`A second multiple access approach for structuring a
`communications transmission medium, as known to those
`skilled in the art, is referred to as frequency-division mul-
`tiple access (FDMA). A depiction of the FDMA approach is
`illustrated in FIG. 2. Unlike TDMA, the FDMA approach is
`independent of time. In FDMA, a number of individualized,
`narrowband channels 12 are used across the frequency
`domain (spectrum) 10. Rather than being partitioned into
`individualized time slots across the channel, in FDMA, one
`circuit 14 is assigned per channel 12 and, typically, users can
`access any one of the frequencies 12 in the frequency
`spectrum 10. A drawback of a pure FDMA architecture is
`that the maximum bandwidth available to an individual user
`
`is oftentimes limited, even if the particular user desires a
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`large peak bandwidth for only a short period of time. In
`order to access greater bandwidth,
`the user often has to
`utilize a plurality of transmitters that allows him to access
`several frequencies at the same time. This may add to the
`cost of the systems employed by those users. Moreover, as
`only a single user can occupy any given frequency, regard-
`less of the time that the user will occupy a frequency(ies) 12,
`the frequency spectrum 10 may not be fully utilized.
`Attempts have been made to support users having differ-
`ing communication requirements in various of the afore-
`mentioned communications systems. For instance, to sup-
`port users of arbitrary access speeds and to retain low-cost
`access for
`low-speed users, a “Universal Time Slot”
`approach has been proposed by R. A. Thompson, J. J.
`HorenKamp, and G. D. Berglund (Phototonic Switching of
`Universal Time-Slots, XIII International Switching Sympo-
`sium Proceedings, Session C2 Paper 4, Stockholm, May
`1990). A depiction of the Universal Time Slot approach is
`found in FIG. 3. In the Universal Time Slot approach, each
`transmission frame 22 in real time 20 is separated into a
`plurality of individual time slots 24 of a set duration (for
`instance, X nanoseconds). The individual time slots 24 can
`transmit a given number of bits for voice (n bits) or video (m
`bits) transmissions, using different amounts of medium
`bandwidth. A so-called “data transparency” is created in
`each of the time slots, in that the signals in each time slot are
`typically generated and received asynchronously.
`Another attempt to maximize use of communication sys-
`tems has been proposed by Zygmunt Haas and Richard D.
`Gitlin using a “Field Coding” technique (Optical Distribu-
`tion Channel: An Almost-All Optical LAN Based On The
`Field Coding Technique, Journal of High-Speed Networks 1
`(1992), pp. 193-214). Field coding, typically used for opti-
`cal transmissions, addresses the costly handicap of requiring
`an optical switching node to operate at
`the peak data
`transmission rate. Field coding separates the switching rate
`from the transmission rate by employing differing bit rates
`for the header (26) and data fields (27) of the optical packets
`(see FIG. 4). Guard bands 28 are used to separate individual
`user transmissions. Because the switching node performs
`only the switching operation and does not need to process
`the data portion of the packet,
`the switching node can
`operate at the lower header rate, allowing the faster rate data
`field to pass transparently through the switching node.
`In both of the proposed approaches, users are allowed to
`transmit at their own desired rate during their assigned time
`slots. However, while suitable for optical media where
`bandwidth is abundant, these techniques are in fact spec-
`trally inefficient. In the cases of the previously mentioned
`communication systems (for instance, radio), the available
`communications transmission medium is quite limited and is
`often costly;
`there is typically only a limited amount of
`bandwidth available for access by users of the various
`communications systems. Thus, techniques that make effi-
`cient use of the transmission spectrum are necessary.
`3. SOLUTION
`
`These and other problems are addressed by a system and
`method for maximizing complete usage of the communica-
`tions transmission medium according to the invention. The
`system and method recognize that the transmission medium
`can be partitioned in frequency, time and code domains, and
`through optimum scheduling, user packing within the over-
`all frequency-time-code domain can be maximized in order
`to optimize spectral efficiency. The system and method also
`preserve a degree of inexpensive access for users with lower
`access speed requirements.
`
`

`

`6,018,528
`
`3
`In one embodiment of the system and method according
`to the invention, the transmission resource, partitioned into
`the “time-frequency” domain, is divided into a plurality of
`time-frequency “slices” that are allocated to users according
`to their various transmission requirements. For higher speed
`users, frequency slots are usually assigned contiguously in
`order to optimize the design of modulation and transmission
`architectures (e.g. a single transmitter for higher rate users).
`In a variant of this embodiment, where frequency adjacency
`requirements can be eased, higher speed users can be
`assigned two or more non-contiguous time-frequency slices
`to further maximize spectral efficiency.
`In a further application of the system and method accord-
`ing to the invention, the time-frequency slicing approach can
`also be applied to data transmissions with code division
`multiple access (CDMA) to account for optimum packing of
`code space. The CDMA transmission spectrum can be
`partitioned into the code-time domains, code-frequency
`domains, or,
`in a three-dimensional approach,
`into the
`code-time-frequency domains so as to optimize use of the
`available code space.
`The system and method provide better spectral use than,
`for example, a Universal-Time-Slot approach, coupled with
`the ability to accommodate a wide range of access rates, the
`provision of low-cost end points for low-speed users, and the
`need for only a single transmitter-receiver pair per user.
`
`4. BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`15
`
`20
`
`25
`
`FIG. 1 illustrates a TDMA multi-access architecture for
`
`30
`
`structuring user access for a given band in the frequency
`spectrum;
`FIG. 2 depicts an FDMA multi-access architecture for
`structuring user access in the frequency spectrum;
`FIG. 3 illustrates a Universal Time Slot approach in
`communications systems;
`FIG. 4 illustrates a Field Coding approach in optical
`transmissions by varying header and data fields;
`FIG. 5 depicts one embodiment of a time-frequency sliced
`system in accordance with the system and method of the
`invention;
`FIG. 6 depicts a second embodiment of a time-frequency
`sliced system for non-contiguous time-frequency assign-
`ments in accordance with the system and method of the
`invention;
`FIG. 7 depicts an embodiment of the system and method
`of the invention for use with time-code slicing in Code
`Division Multiple Access (CDMA) systems;
`FIG. 8 depicts one embodiment of the system and method
`of the invention for use with frequency-code slicing in
`CDMA systems;
`FIG. 9 depicts reuse of code assignments in time-code
`slicing in accordance with the system and method of inven-
`tion; and
`FIG. 10 depicts a further embodiment of the system and
`method of the invention for use with time-frequency-code
`slicing.
`
`5. DETAILED DESCRIPTION OF THE
`INVENTION
`
`Turning now to the drawings, wherein like numerals
`depict like components, FIG. 5 illustrates a time-frequency
`slicing approach according to one embodiment of the inven-
`tion. As illustrated, the overall time-frequency spectrum (or
`medium) 40 can be partitioned in both the time and fre-
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`quency domains as a plurality of frequency bands (“slices”)
`42 (F0, F1, .
`.
`. FN) extending over a plurality of individual
`time slots (“slices”) 44 (S0, S1,
`.
`.
`. SN). For purposes of
`illustration and not of limitation, users of the spectrum can
`be categorized into three general groups: high speed users 46
`(here A, B, G, L); medium speed users 48 (here, C, E, F, H,
`I, J, M, 0, Q); and low speed users 50 (here, D, K, N, P, R,
`S, T). As illustrated in FIG. 5, a plurality of time-frequency
`“slices” 52 are gridded into the overall
`time-frequency
`spectrum 40.
`In accordance with the system and method of the
`invention,
`it
`is assumed that all of the various signals
`transmitted by users 46, 48, 50 will occupy at least one
`frequency band 42. Moreover, it will be realized that due to
`the nature of the equipment typically employed by higher-
`speed users 46, the high-speed users 46 will have the ability
`to modulate their signals so as to cover one or more
`frequency bands 42. Thus, as depicted, the overall medium
`can be sliced so that low-speed users 50 will be permitted to
`fill one or more of the available time slots 44 in a frame,
`while higher-speed users can fill one or more of the available
`frequency bands 42 or time slots 44.
`A further assumption is that one “unit” of “slice”, which
`is taken to be one frequency band allocation for one time slot
`allocation,
`is the minimum amount of communications
`resource which will be available to a user. Unlike other
`
`transmission techniques (such as the Universal Time Slot
`approach of FIG. 3) no guard bands “28 ” are necessary
`between contiguous frequency bands 42 or time slots 44, or
`both, that are allocated to a given user, thus optimizing full
`use of the medium (realizing, of course, that guard bands 28
`may be needed to separate different users). Where a single
`user occupies contiguous allocations, a continuous fre-
`quency band 42 and/or a continuous time allocation 44 can
`be realized because that same user may utilize the space
`which would be normally occupied by guard bands 28.
`Examples of the unit slice are depicted in FIG. 5 by the
`time-frequency slice occupied, for example, by various low
`speed users 50 (i.e., users D, K, N, etc.).
`Thus, through use of their respective transmitters (not
`shown), the various of the users 46, 48, 50 can modulate
`their signals into one or more of the available frequency
`bands 42 on a time slot-by-slot 44 basis in order to effect
`optimum scheduling of the users within the medium 40 to
`efficiently make use of the available time-frequency medium
`40. The actual positioning (scheduling) of the various speed
`users 46, 48, 50 within the overall medium may be deter-
`mined based on such factors as individual user demand, the
`relative numbers of low speed/medium speed/high speed
`users, and the like.
`One way to effect the slicing of the transmission medium
`40 and to implement positioning of the users 46, 48, 50
`within the medium is to provide a central control 100 to
`maintain or otherwise keep a lookup table containing the
`status of the availability of space within the medium 40
`according to frequency band allocations 42 and time slots
`44. The central control 100 may then award particular
`time-frequency slice 52 allocations to the individual users
`46, 48, 50 based on such factors as the amount of the
`medium 40 requested by the users and/or the amount of
`medium 40 already allocated to users. Individual users may
`thus align themselves within their assigned time-frequency
`slices 52 through appropriate signal configuration and/or
`modulation. Based on the availability of the medium 40,
`central control 100 can thus allocate particular time-
`frequency slices 52 to a given user so as to anticipate
`“future” requests which will be made by users 46, 48, 50 so
`
`

`

`6,018,528
`
`5
`as to best optimize full use of the overall medium 40. The
`control 100 can anticipate such requirements, for instance,
`through use of probabalistic studies, historical or projected
`load requirements, and the like, as normally maintained by
`individual service providers. Another way to effect use
`spectrum of the medium 40 is through random assignments
`of users 46, 48, 50 to the available time-frequency slices 52.
`Other ways of effecting slicing and scheduling in accordance
`with the system and method of the invention can be readily
`envisioned or otherwise arrived at by those skilled in the art.
`As will be appreciated,
`through scheduling,
`the time-
`frequency spectrum 40 can be filled in a more efficient
`manner than possible with the Universal-Time-Slot
`approach. Unlike a pure TDMA approach, a common band-
`width is not required, so that the system and method can
`schedule cost-efficient entry points for lower speed users 50.
`That is, unlike TDMA, users are capable of operating at their
`own access rates while still being able to share the overall
`time-frequency domain 40 with users operating at different
`access rates. As shown in FIG. 5, several low-speed users 50
`can be scheduled to transmit on different frequencies 42 in
`the same designated time slot 44. For instance, low speed
`users S, J and T occupy the same time slot S6. During certain
`other time slots 44, then, a smaller number of high-speed
`users 46 may be scheduled to transmit.
`Moreover, unlike a pure FDMA approach, a given band-
`width 42 can be occupied by multiple users (for instance,
`users G, B, H, P, S for band F6). Thus, the system and
`method provide a large degree of flexibility in efficiently
`packing the time-frequency spectrum 40 and making use of
`the entire domains.
`
`Oftentimes, it is advantageous that high-speed users 46 be
`assigned contiguous frequencies 42. Such contiguous
`assignments eliminate the need for guard bands between the
`frequencies assigned to a given user. Depending on the
`modulation scheme, however, certain adjacency require-
`ments may be relaxed. For instance, as will be appreciated,
`users modulating their signals according to a “multi-tone”
`scheme may not require contiguous frequency assignments
`in order to transmit their data. As those skilled in the art will
`
`discern, tones represent multi-bit symbols, with each tone
`toggling at a rate corresponding to the bandwidth of one
`frequency band. Thus, with multi-tone transmission two bits
`can be transmitted as one 4-ary symbol using 2-tone modu-
`lation instead of two symbols on a binary channel.
`FIG. 6 thus depicts a variation of the time-frequency
`slicing method of the invention where noncontiguous fre-
`quency arrangements may be employed. For instance,
`higher-speed users 46 operating on multi-tone modulation
`may benefit from non-contiguous frequency arrangements.
`Here, a particular high speed user B (designated on FIG. 6
`by numeral 54) has been assigned two non-contiguous
`frequency assignments (“slices”) F0 and F5—F6 in the
`bandwidth, rather than the single contiguous assignment
`F4—F6 that the same user B might have employed without
`multi-tone modulation as depicted in FIG. 5. Each of the
`respective tones modulated by the user (here, B) can occupy
`a respective frequency assignment without the necessity for
`contiguous assignments.
`An example of a multi-tone approach includes current
`channelized cellular systems, for instance, cellular telephone
`systems, cellular data systems, or the like, to provide higher
`bandwidth to some users. The higher bandwidth is accom-
`plished by allocating multiple channels to each higher-speed
`user. Since the allocations do not need to be contiguous,
`more users can perhaps be accommodated than with con-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`
`tiguous assignments (FIG. 5). The blocking probability may
`be reduced compared to the contiguous assignments of the
`time-frequency approach as described in FIG. 5.
`Thus, it will be realized that higher data rates will be
`available to higher-speed users 46 by signaling on a com-
`bination of tones, whereas the lower-speed user 50 would
`occupy only a single frequency slice of the bandwidth. The
`transmission speed of a user can thus determine the number
`of tones and, thus, the number of frequencies 42 allocated
`for that user. These tones may be scheduled in possibly
`non-contiguous frequency slots within one or more time
`slots, as, for example, for user B in FIG. 6. In fact, it has
`been found that spreading the frequency allocations of a
`high-speed user may offer some propagation benefits (e.g.,
`a reduction in the degradation from frequency-selective
`multipath fading).
`the single
`that
`It will be understood, of course,
`transmitter-receiver arrangement as utilized in FIG. 5 will
`not be employed by high-speed users in multi-tone trans-
`mission in order to obtain this scheduling advantage. Here,
`higher speed users may need to employ multiple
`transmitters, one for each frequency slice that has been
`assigned to that particular user. However, it will be under-
`stood that as opposed to contiguous transmissions entailing
`the entire frequency spectrum, for non-contiguous multi-
`tone transmissions, the base station receiver itself may be
`simplified, in that only a fixed number (“n”) tones in specific
`frequency bands 42 will need to be received, so that only a
`single, low bit rate transmitter/receiver pairing may need to
`be used. It will also be realized that the m-ary components
`may be modulated by a spectrally efficient scheme or by a
`constant envelope scheme such as constant power PSK.
`Higher-level modulations are also possible in the system and
`method according to the invention.
`Other applications of the scheduling method and system
`according to the invention are also possible. As will be
`appreciated to those skilled in the art, in addition to the
`TDMA and FDMA multiple access architectures, a “Code
`Division Multiple Access” (CDMA) system may also be
`employed in an effort
`to permit multiple access to the
`communications transmission medium. Abrief review of the
`
`principles of CDMA architecture will serve to better appre-
`ciate the applicability of the principles of the system and
`method according to the invention to that architecture.
`In CDMA, individualized transmissions are not strictly
`separated by frequency (as in FDMA) or strictly separated
`by time (as in TDMA). Rather, transmissions in CDMA are
`permitted to controllably interfere with one another by
`sharing the same frequency spectrum at the same time. By
`assigning a special, unique code to each of the separate
`transmissions occupying the CDMA medium, each particu-
`lar transmitter-receiver pair (which operates according to a
`respective code) may decode the appropriate transmission
`occupying the common channel from among the other
`signals occupying that same channel.
`One way to implement CDMA is via “Direct Sequence
`Spread Spectrum”, in which users are assigned codes of
`small cross-correlation. For example, this code set, large but
`finite, may be composed of different phases of a long
`PN-sequence. When users access the channel, they multiply
`their modulated data stream by their assigned code. The
`code rate, which is considerably higher than the data bit-rate,
`is referred to as the chip-rate. At the receiving end, the
`destination multiplies the received signal by a replica of the
`source code to recover the original signal.
`As those skilled in the art will realize, CDMA support for
`multiple access stems from the fact that the cross-correlation
`
`

`

`6,018,528
`
`7
`if a signal
`between two different codes is small. Thus,
`encoded at one code (C1) is decoded with a different code
`(C2), the result appears to the receiver as noise. The limi-
`tation of the scheme (i.e., the maximum number of users that
`can utilize the multiple access channel) depends on the total
`amount of “noise” contributed by “interfering” users to the
`detected signal. In other words,
`the more users simulta-
`neously transmitting on the channel, the greater the level of
`interference that will exist within the medium. The Signal-
`to-Interference ratio (S/I) determines the Bit-Error-Rate
`(BER) performance of the system.
`In the spectral domain, the multiplication of the data by
`the fast bit-rate code corresponds to spreading the data
`spectral components over a broader spectrum. Thus, a larger
`spectrum is required to convey the transmission. However,
`because of the multiple-access feature, a number of users
`may co-exist at any time on the channel. The ratio of the
`unspread and the spread signals is called the processing gain,
`GP, and Gp=2RC/Rb where RC and Rb are the chip and the
`data bit-rates, respectively. The larger the processing gain,
`the less “noise” contribution any user has on the other users’
`signals.
`The principles underlying the system and method of the
`invention will serve to enhance usage of the CDMA
`medium. The resource space might be sliced into a “time-
`code” space, a “frequency-code” space or, if viewed in three
`dimensions, into a “time-frequency-code” space. Thus,
`it
`will be appreciated that the scheduling approach according
`to the system and method of the invention can also be used
`in the CDMA domain to improve resource usage.
`FIG. 7 depicts application of a “time-code” slicing
`method as applied to transmissions in the CDMA domain.
`FIG. 8 depicts a “frequency-code” slicing approach. As
`before, a plurality of different speed users 46, 48, 50 are
`contemplated. The overall medium 40‘ is partitioned into a
`plurality of individual, discrete “codes” (43) either over the
`time (44) domain (FIG. 7) or frequency band 42 domain
`(FIG. 8), accounting for the relative use of the available code
`space which is contained within the overall medium 40‘.
`The term “code space” is used to denote the overall set of
`all possible codes for assignment
`to user transmission
`employing, for instance, a “family” of codes acceptable for
`purposes of cross-correlation. Auser requiring a large degree
`of code space—for instance, users G, B, M, Q, F—can be
`granted code space in at least two ways. For purposes of
`illustration and not of limitation, examples of possible code
`space allocations are presented in FIGS. 7, 8 and 9. In FIGS.
`7 and 8, users B and G, for instance, require a relatively large
`quantity of code space and as such are granted a plurality of
`individual codes 43 across time slots (FIG. 7) or frequency
`bands (FIG. 8). The plurality of individual codes are col-
`lectively representative of a larger quantity of code space
`contained within the overall medium 40‘.
`
`An alternative approach is illustrated in FIG. 9. Here, a
`user may be allocated codes of differing length 120. The
`relative length of a given code is inversely related to the
`quantity of code space to be occupied by a given user. For
`instance, in FIG. 9, user Ais assigned a longer code C5 than
`user G (code C6). As illustrated in FIG. 9,
`the relative
`“height” of the code space occupied by those users is
`indicative of the quantity of code space occupied by them;
`here, user A, who has been assigned a longer code (C5) than
`user G (code C6) occupies less code space than user G. In
`this manner, optimum use of the overall code space embod-
`ied within the medium 40‘ can be achieved.
`
`It can be seen in FIG. 9 that the system and method
`provide for efficient reuse of the available codes based on the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`temporal occupancy requirements of a given user within the
`medium. For example, it can be seen that code C3 can be
`reused a number of times—here, by users C, J, N,
`R—because each of those users do not occupy any common
`portion of the overall code space located in the medium 40‘
`at the same time.
`
`In general, it can be appreciated that the chip rate does not
`need to be fixed among users and codes. This means that a
`signal can be modulated by a code sequence Ci at some chip
`rate, Ri. Although the chip rate Ri can be arbitrary,
`in
`practice, Ri is often chosen as an integer multiple of some
`minimal chip rate, Rmin. This is because the amount of
`bandwidth occupied by the spreading depends on the chip
`rate Ri and Rmin would be selected to fill one frequency
`slice. This implies a frequency-code slicing or
`time-
`frequency-code slicing system and is similar to high-rate
`users modulating their signal
`to occupy more than one
`frequency slice in the time-frequency slicing system. Thus,
`a user would have to be assigned enough frequency slices to
`accommodate the spreading associated with the chip rate,
`Ri. Other users may share the same bandwidth at the same
`time using different codes.
`By spreading a signal over a larger bandwidth (i.e, with a
`faster chip rate), more independent transmissions can be
`scheduled in this bandwidth. As previously indicated, sched-
`uling of the independent
`transmissions depends on the
`interference level contributed from each transmission, so
`that the BER of the scheduled transmissions is kept below
`some predetermined threshold.
`It is assumed herein for exemplary purposes only and not
`for purposes of limitation, that the chip rate of the spreading
`code is of constant and fixed rate. A single fixed BER
`threshold is set for all users. Error rates above this threshold
`
`is considered unacceptable to all users in the system.
`In general,
`it will be appreciated that users