WI-LAN Inc. v. Alcatel-Lucent USA Inc. et al

Filing 491

RESPONSE to Motion re 482 MOTION for Judgment as a Matter of Law [RENEWED] OF NO INVALIDITY OR, ALTERNATIVELY, MOTION FOR NEW TRIAL ON INVALIDITY filed by Alcatel-Lucent USA Inc., Ericsson Inc., Exedea INC., HTC America, Inc., HTC Corporation, Sony Mobile Communications (USA) Inc., Sony Mobile Communications AB, Telefonaktiebolaget LM Ericsson. (Attachments: # 1 Exhibit A: Trial Transcript, # 2 Exhibit B: Trial Transcript, # 3 Exhibit C: Trial Transcript, # 4 Exhibit D: Trial Transcript, # 5 Exhibit E: Trial Transcript, # 6 Exhibit F: Trial Transcript, # 7 Exhibit G: Trial Transcript, # 8 Exhibit H: DDX 13-19, # 9 Exhibit I: DDX 13-31, # 10 Exhibit J: DX 124, # 11 Exhibit K: DX 148, # 12 Exhibit L: PX 1, # 13 Text of Proposed Order)(Heinlen, James)

EXHIBIT K

111111

United States Patent

1111111111111111111111111111111111111111111111111111111111111
US006018528A

[19J

Gitlin et al.
[54]

[45]

5,221,983
5,260,967
5,272,556
5,295,153
5,317,593
5,533,013
5,539,730
5,577,024
5,581,548

SYSTEM AND METHOD FOR OPTIMIZING
SPECTRAL EFI<lCIENCY USING TIMEFREQUENCY-CODE SLICING

6,018,528

Patent Number:
Date of Patent:

[11]

6/1993
11/1993
12/1993
3/1994
5/1994
7/1996
7/1996
11/1996
12/1996

*Jan.25,2000

Wagner .
Schilling .................................
Faulkner et a!. .
Gudmundson ..........................
Fulghum et al. .......................
Leppanen ................................
Denl ........................................
Malkamaki eta!. ....................
Ugland et a!. ..........................

[75]

Inventors: Richard D. Gitlin, Little Silver;
Zygmunt Haas. Holmdel; Mark J.
Karol, Fair Haven; Clark Woodworth,
Rumson, all of N.J.

[73]

Assignee: AT&T Corp, Middletown, N.J.
Notice:

[57]

[21]

Appl. No.: 08/234,197

[221

Filed:

375/205
370/342
370/342
370/330
370/337
370/337

Primary Examiner-Huy D. Vu
Attorney, Agent, or Firm-Jose R. de la Rosa

[ *]

375/203

[51]

[52]
[58]

This patent is subject to a terminal disclaimer.

A system and method for optimizing usage of a communications 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
varying access rates and user-application requirements.
Through scheduling of the various speed users within the
frequency and time domains, the system and method can
efficiently allocate and make use of the available spectrum,
thereby accommodating higher 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 (CDMA) techniques by slicing the available code
space along time-code domains, frequency-code domains or,
in three dimensions, along time-frequency-code domains.
Users may be efficiently scheduled based on code space
requirements so as to optimize use of the communication
medium.

Apr. 28, 1994
7

Int. Cl. ........................................................ H04J 4/00
U.S. Cl........................... 370/436; 370/441; 370/468;
370/478; 370/479; 375/201
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
References Cited

[56]

U.S. PATENT DOCUMENTS
4,868,811
4,914,649
5,029,180
5,134,615
5,210,771

9/1989
4/1990
7/1991
7/1992
5/1993

Suzuki .. ................ ...... ...... .... .... 370!50
Schwendeman et a!. ................ 370!50
Cowart .................................... 375/206
Freeburg eta!. ....................... 370/330
Schaeffer eta!. ....................... 375/203

42

ABSTRACT

15 Claims, 8 Drawing Sheets

A

~FJ

F6
F5

s

p

H

B
I

Q ./

M

J

/52

N

F4

40/

l

c

F3

D

F2

F1
FREQUENCE
BANDS
FO

G

E

so

0

K

-

R

J\
T

752
( 100

F
L
S1

S2

S3

S4

~

---4
S5

CONTROL

I

S6

44 TIME SLOTS - - 46'-.,
HIGH-SPEED USERS: A,B,G,L
48
SO'-.... MEDIUI.HPEED USERS: C,E,F,H,I,J,M,O,Q
'-.... LOW-SPEED USERS: D,K,N,P,R,S,T
EJ

T~x. c,~r;,

Akat?i-lurPn( "';a/
N...,. 6.10-L-v-00521-LED

Defendants' Exhibit

DX-148
DEFS0006841

U.S. Patent

FIG.
1

\
RADIO

Jan.25,2000

Sheet 1 of 8

6,018,528

1
TIME TIME TIME TIME TIME TIME TIME TIME
SLOT SLOT SLOT SLOT SLOT SLOT SLOT SLOT
1
2
3
4
5
6
7
8

FRE~UNE~CY ~L--------'----'-1---jfY,__,___l~___~.I_

__,_I_..J...._____.j

v

4/

FRAME--- 2

FIG. 2
RF CHANNELS

12

I

FREQUENCY 1 CONTROL CIRCUIT

I}

BANDWIDTH OF EACH
CHANNEL TYPICALLY
LESS THAN 30KHz
{IN EACH DIRECTION)

FREQUENCY 2 CONTROL CIRCUIT
FREQUENCY
DOMAIN

f
10

14
FREQUENCY 3
FREQUENCY 4

VOICE CIRCUIT
VOICE CIRCUIT
0
0
0

FREQUENCY N

ALL VOICE CIRCUITS ARE
FULLY TRUNKED, CONTINUOS
TRANSMISSION CIRCUITS
ONE CIRCUIT PER
RF CHANNEL

VOICE CIRCUIT
TIME -->
INDEPENDENT

DEFS0006842

U.S. Patent

6,018,528

Sheet 2 of 8

Jan.25,2000

FIG. 3
20

22

\

REAL TIME

22

\

ONE FRAME

24

\

GUARD-

ONE TIME SLOT

VOICE

GUARD-

DATA

BAND
,_______ X ns

BAND

---..-1

VIDEO

UNIVERSAL TIME SLOT
n

n

n

FIG. 4
HIGH-SPEED
DATA

I

)

\

/'

,./

PACKET
SLOT

27

·I '

DEFS0006843

U.S. Patent

Jan.25,2000

6,018,528

Sheet 3 of 8

FIG. 5

A

F7

42~F6

FS

s

p

H

>52

B
I

M

J

N

Q

/

F4
40/

F2

1

c

F3

F1

FREQUENCE
BANDS
FO

G

D

E

R

T

0

K

J\

F

-"

1"'- 52
[7 r100

L
1--

SO

S1

S2

S3

S4

~

44

SS

CONTROL

S6

TIME SLOTS - - - -

46.....__,_
HIGH-SPEED USERS: A,B,G,L
48
SO.....__,_ MEDIUM-SPEED USERS: C,E,F,H,I,J,M,O,Q
"---LOW-SPEED USERS: D,K,N,P,R,S,T

DEFS0006844

U.S. Patent

Jan.25,2000

6,018,528

Sheet 4 of 8

FIG. 6

42~

A

F7

F5
54

s

p

H

F6

v

8

----F4

I

c

G

D

FREQUENC E
BANDS
F1
54
FO

N

/

r--

F3
F2

J

Q

M
R

T

0

K

J\

F

-----...

...

E

t7

52

L
8

SO

S1

~
44

52

S2

S3

S4

SS

S6

TIME SLOTS - - -

46 '--...._
HIGH-SPEED USERS: A,B,G,L
48
.,_____MEDIUM-SPEED USERS: C,E,F,H,I,J,M,O,Q
50
.._____LOW-SPEED USERS: D,K,N,P,R,S,T

DEFS0006845

U.S. Patent

Jan.25,2000

6,018,528

Sheet 5 of 8

FIG. 7

A

C7

43~C6

C5

s

p

H

8
I

M

J

N

52'

Q

C4
40'/

l

CODE
SPACE

c

C3
C2
C1

G

D

E

R

T

0

K

r

J

L

co
so

51

52

53

54

~

55

56

44 TIME SLOTS ----

46'---

48
HIGH-SPEED USERS: A,B,G,L
SO"--- MEDIUM-SPEED USERS: C,E,F,H,I,J,M,O,Q
"--- LOW-SPEED USERS: D,K,N,P,R,S,T

DEFS0006846

U.S. Patent

Jan.25,2000

6,018,528

Sheet 6 of 8

FIG. 8

A

43~::
cs

s

p

H

B
I

J

52'

Q

M

N

C4
40'/

C2

f
CODE
SPACE

c

C3

C1

G

D
E

K

j

R

T

0

F
L

co
FO

F1

F2

F3

F4
F5 F6
~

FREQUENCY BANDS - - -

42

46~

HIGH-SPEED USERS: A,B,G,L
48
SO~ MEDIUM-SPEED USERS: C,E,F,H,I,J,M,O,Q
~ LOW-SPEED USERS: D,K,N,P,R,S,T

DEFS0006847

U.S. Patent

Jan.25,2000

6,018,528

Sheet 7 of 8

FIG. 9

cs

A

120

C8 P C8 S

C8 H
C4 8
C7 I C7 M

Cn is nt h code I\

C3

c

C6 G C3 J C3 N C3 R C3 J

C1 D

1

CODE
SPACE

CO E

SO

C7 Q

C1 0

C1 K

C2 F

S1

co
52

S3

C1 T

L

54

~

SS

S6

44 TIME SLOTS - 46---._
HIGH-SPEED USERS: A,B,GJ
48
SO..._,_ MEDIUM-SPEED USERS: C,E,F,H,I,J,M,O,Q
..._,_ LOW-SPEED USERS: D,K,N,P,R,S,T

DEFS0006848

U.S. Patent

Jan.25,2000

FIG.

Sheet 8 of 8

6,018,528

10
CODE

SP~A

43

co
40"/
F3

42~2
FREQUENCE' Fl
BANDS
E
FO
44

F

G

so

~
TI~E SLO~ S2

J

J

S3
46'-.._
HIGH-SPEED USERS: F,G,J
48
SO'-.,. MEDIUM-SPEED USERS: A,B,C,E
'-.,. LOW-SPEED USERS: D,H,I,K,L,

DEFS0006849

6,018,528
1

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
1. TECHNICAL FIELD
cost of the systems employed by those users. Moreover, as
only a single user can occupy any given frequency, regardThe invention relates to a system and method for maxiless of the time that the user will occupy a frequency(ies) 12,
mizing usage of a communications transmission medium,
the frequency spectrum 10 may not be fully utilized.
and more particularly, to a system and method for maximizAttempts have been made to support users having differing usage of a communications transmission medium while
10 ing communication requirements in various of the aforepreserving optimum access to the medium for users of
mentioned communications systtms. For instance, to supdiffering access speeds and while maximizing spectral use
port users of arbitrary access speeds and to retain low-cost
and bandwidth efficiencies.
access for low-speed users, a "Universal Time Slot"
approach has been proposed by R. A. Thompson, J. 1.
2. PROBLEM
15 HorenKamp, and G. D. Berglund (Phototonic Switching of
Many communication systems today, such as the wireless,
Universal Time,Slots, XIII International Switching Symposatellite, personal communications, and cellular communisium Proceedings, Session C2 Paper 4, Stockholm, May
cations systems, typically exhibit certain common require1990). A depiction of the Universal Time Slot approach is
ments. For example, to maximize their flexibility, these
found in FIG. 3. In the Universal Time Slot approach, each
communications systems typically require a variety of
20 transmission frame 22 in real time 20 is separated into a
access speeds in order to support differing applications. In
plurality of individual time slots 24 of a set duration (for
order to be economically viable, the systems should also
instance, X nanoseconds). The individual time slots 24 can
oJier a generally low-cost access for lower-speed users.
transmit a given number of bits for voice (n bits) or video (m
Lastly, the systems typically strive for a high degree of
bits) transmissions, using different amounts of medium
spectral efficiency in order to maximize usage of the par25 bandwidth. A so-called "data transparency" is created in
ticular communications transmission mtdium.
each of the time slots, in that the signals in each time slot are
As is known, certain data transmission architectures have
typically generated and received asynchronously.
been developed in communications systems to allocate
Another attempt to maximize use of communication syscommunication resources to individual users on their
tems has been proposed by Zygmunt Haas and Richard D.
demand. Typically, these architectures ought to be structured
30 Gitlin using a "Field Coding" technique (Optical Distributo permit various users to utilize the resources in a fully
tion Channel: An Almost-All Optical LAN Based On The
shared communications system. Tims, the various architecField Coding Technique, Journal of High-Speed Networks 1
tures are generically referred to as "multiple access" archi(1992), pp. 193-214). Field coding, typically used for optitectures.
cal transmissions, addresses the costly handicap of requiring
Referring to FIG. 1, one multiple access architecture for 35 an optical switching node to operate at the peak data
maximizing usage of the communications transmission
transmission rate. Field coding separates the switching rate
medium is commonly referred to as time-division multiple
from the transmission rate by employing differing bit rates
access (TDMA). As known to those skilled in the art, in
for the header (26) and data fields (27) of the optical packets
TDMA each carrier frequency 1 is severed into one or more
(see FIG. 4). Guard bands 28 are used to separate individual
time frames 2 having a plurality of individual time slots 4. 40 user transmissions. Because the switching node performs
Each of the time slots 4 is assigned to a user as an
only the switching operation and does not need to process
independent circuit. Information is transmitted by the user in
the data portion of the packet, the switching node can
short bursts during assigned or specified time slots, with
operate at the lower header rate, allowing the faster rate data
users being scheduled for access to the time slots 4 accordfield to pass transparently through the switching node.
ing to their information transmission requirements. As will 45
In both of the proposed approaches, users are allowed to
be appreciated, however, in pure TDMA architecture both
transmit at their own desired rate during their assigned time
higher-speed and lower-speed users share a common comslots. However, while suitable for optical media where
munications bandwidth, typically by assigning more time
bandwidth is abundant, these techniques are in fact specslots per frame to the higher-speed users. The drawback of
trally inefficient. In the cases of the previously mentioned
this architecture is that high-rate access (high speed data so communication systems (for instance, radio), the available
bursts) is required even for lower-speed users, which
communications transmission medium is quite limited and is
increases the cost and complexity of the systems employed
often costly; there is typically only a limited amount of
by those lower-speed users.
bandwidth available for access by users of the various
A second multiple access approach for structuring a
communications systems. Thus, techniques that make efficommunications transmission medium, as known to those 55 cient use of the transmission spectrum are necessary.
skilled in the art, is referred to as frequency-division mul3. SOLUTION
tiple access (FDMA). A depiction of the FDMA approach is
SYSTEM AND METHOD FOR OPTIMIZING
SPECTRAL EFFICIENCY USING TIMEFREQUENCY-CODE SLICING

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 channell2 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

60

65

These and other problems are addressed by a system and
method for maximizing complete usage of the communications 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 overall 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.

DEFS0006850

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
architeclures (e.g. a singk 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 according to the invention, the time-frequency slicing approach can
also be applied to data transmissions with code division
multiple access (COMA) to account for optimum packing of
code space. The COMA 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 oflow-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
FIG. 1 illustrates a TDMA multi-access architecture for
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 assignments 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 (COMA) 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 invention; 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 invention. As illustrated, the overall time-frequency spectrum (or
medium) 40 can be partitioned in both the time and fre-

4
quency domains as a plurality of frequency bands ("slices")
42 (FO, F1, ... FN) extending over a plurality of individual
time slots ("slices") 44 (SO, Sl, ... 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). A-s illustrated in FIG. 5, a plmality of time-frequency
"slices" 52 are gridded into the overall time-frequency
spectrum 40.
10
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
15 the nature of the equipment typically employed by higherspeed 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,
20
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
25 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 " arc necessary
between contiguous frequency bands 42 or time slots 44, or
30 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 frequency band 42 and/or a continuous time allocation 44 can
3s 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
40
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
45 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 determined based on such factors as individual user demand, the
relative numbers of low speed/medium speed;high speed
50 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
55 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
60 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,
65 central control 100 can thus allocate particular timefrequency slices 52 to a given user so as to anticipate
"future" requests which will be made by users 46, 48, 50 so

DEFS0006851

6,018,528

5

6

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

DEFS0006852

6,018,528

7

8

between two different codes is small. Thus, if a signal
temporal occupancy requirements of a given user within the
encoded at one code (C 1) is decoded with a different code
medium. For example, it can be seen that code C3 can be
( C2 ), the result appears to the receiver as noise. The limireused a number of times-here, by users C, J, N,
tation of the scheme (i.e., the maximum number of users that
R-because each of those users do not occupy any common
can utilize the multiple access channel) depends on the total
portion of the overall code space located in the medium 40'
amount of "noise" contributed by "interfering" users to the
at the same time.
detected signal. In other words, the more users simultaIn general, it can be appreciated that the chip rate does not
neously transmitting on the channel, the greater the level of
need to be fixed among users and codes. lbis means that a
interference that will exist within the medium. The Signalsignal can be modulated by a code sequence Ci at some chip
to-Interference ratio (S/I) determines the Bit-Error-Rate
10 rate, Ri. Although the chip rate Ri can be arbitrary, in
(BER) performance of the system.
practice, Ri is often chosen as an integer multiple of some
In the spectral domain, the multiplication of the data by
minimal chip rate, Rmin. This is because the amount of
the fast bit-rate code corresponds to spreading the data
bandwidth occupied by the spreading depends on the chip
spectral components over a broader spectrum. Thus, a larger
rate Ri and Rmin would be selected to fill one frequency
spectrum is required to convey the transmission. However,
15 slice. This implies a frequency-code slicing or timebecause of the multiple-access feature, a number of users
frequency-code slicing system and is similar to high-rate
may co-exist at any time on the channel. The ratio of the
ust:rs mmlulaling lht:ir signal lo occupy mort: than ont:
unspread and the spread signals is called the processing gain,
frequency slice in the time-frequency slicing system. Thus,
GP, and GP=2RjRb where Rc and Rb are the chip and the
a user would have to be assigned enough frequency slices to
data bit-rates, respectively. The larger the processing gain,
20 accommodate the spreading associated with the chip rate,
the less "noise" contribution any user has on the other users'
Ri. Other users may share the same bandwidth at the same
signals.
time using different codes.
The principles underlying the system and method of the
By spreading a signal over a larger bandwidth (i.e, with a
invention will serve to enhance usage of the CDMA
medium. The resource space might be sliced into a "time- 25 faster chip rate), more independent transmissions can be
scheduled in this bandwidth. As previously indicated, schedcodt:" spact:, a "frt:qut:ncy-codt:" spact: or, ifvit:wt:d inthrt:t:
uling of the independent transmissions depends on the
dimensions, into a "time-frequency-code" space. Thus, it
interference level contributed from each transmission, so
will be appreciated that the scheduling approach according
that the BER of the scheduled transmissions is kept below
to the system and method of the invention can also be used
some predetermined threshold.
in the CDMA domain to improve resource usage.
30
It is assumed herein for exemplary purposes only and not
FIG. 7 depicts application of a "time-code" slicing
for purposes of limitation, that the chip rate of the spreading
method as applied to transmissions in the CDMA domain.
code is of constant and fixed rate. A single fixed BER
FIG. 8 depicts a "frequency-code" slicing approach. As
threshold is set for all users. Error rates above this threshold
before, a plurality of different speed users 46, 48, 50 are
contemplated. The overall medium 40' is partitioned into a 35 is considered unacceptable to all users in the system.
plurality of individual, discrete "codes" (43) either over the
In general, it will be appreciated that users with high
time (44) domain (FIG. 7) or frequency band 42 domain
bit-rates will tend to transmit at a higher power level and,
(FIG. 8), accounting for the relative use of the available code
thus, because of the constant spreading sequence chip rate,
space which is contained within the overall medium 40'.
higher speed users will contribute more "noise" or "interThe term "code space" is used to denote the overall set of 40 ference" than user~ with lower bit-rates. Thus, there will be
all possible codes for assignment to user transmission
a tradeoff between a large number of low-bit users and a
employing, for instance, a "family" of codes acceptable for
smaller number of high-speed users. The scheduling process
purposes of cross-correlation. A user requiring a large degree
accounts for granting the various users codes so that the
of code space-for instance, users G, B, M, Q, F---can be
BER caused by the total level of interference from all the
granted code space in at least two ways. For purposes of 45 transmissions remains below the acceptable threshold.
Hence, to minimize code interference, the various users 46,
illustration and not of limitation, examples of possible code
48, 50 can be granted use of the available code space for
space allocations are presented in FIGS. 7, 8 and 9. In FIGS.
7 and 8, ust:rs B ami G, for inslanct:, rt:quirt: a rdalivdy largt:
givm limt: ptriods in lht: lirnt: domain 44. As prt:viously
quantity of code space and as such are granted a plurality of
illustrated with regard to FIG. 9, time multiplexing of
individual codes 43 across time slots (FIG. 7) or frequency 50 CDMA will allow for code "reuse" in differing time periods,
bands (PIG. 8). The plurality of individual codes are colthereby supporting a large user population with a relatively
lectively representative of a larger quantity of code space
small number of codes. Scheduling may thus be used to
contained within the overall medium 40'.
efficiently pack each time slot within overall medium 40,
while maintaining acceptable bit error rates.
An alternative approach is illustrated in FIG. 9. Here, a
user may be allocated codes of differing length 120. The 55
The scheduling as depicted in FIGS. 7, 8 and 9 accounts
relative length of a given code is inversely related to the
for the amount of "code space" a user occupies relative to his
quantity of code space to be occupied by a given user. For
transmission rate and also the amount of noise that he will
instance, in FIG. 9, user A is assigned a longer code C5 than
contribute to the other users. As previously described, in
user G (code C6). As illustrated in FIG. 9, the relative
"code slicing", the term "code space" is used to denote the
"height" of the code space occupied by those users is 60 overall "set" of all possible codes for assignment to user
indicative of the quantity of code space occupied by them;
transmissions, employing, for instance, a ·•family" of codes
here, user A, who has been assigned a longer code (C5) than
acceptable for purposes of cross-correlation. Users 46, 48,
user G (code C6) occupies less code space than user G. In
50 may thus be granted differing portions of the code space
this manner, optimum use of the overall emit: space embodwith, for instance, larger subsets of the code space assigned
ied within the medium 40' can be achieved.
65 to higher bit-rate users, for instance, high speed users B. G
It can be seen in FIG. 9 that the system and method
and L in FIGS. 7 and 8. It can also be seen that, as in a
provide for efficient reuse of the available codes based on the
time-frequency sliced approach, the application of the sys-

DEFS0006853

6,018,528

9

10

tern and method to CDMA will preserve cost-efficient access
a plurality of time slices in said communications transfor all users regardless of their varying access rates.
mission medium;
Furthermore, as previously explained in relation to timemeans for slicing the communications transmission
frequency slicing, the factors underlying optimum schedulmedium into a plurality of time-frequency slices, each
ing and governing its determination can be applied to
of said time-frequency slices occupying a space in said
optimize use of the CDMA medium.
communications transmission medium at least equal to
On certain non-time slotted CDMAsystems, mechanisms
one frequency slice allocation measured over one time
will sometimes be required to limit the maximum number of
slice allocation;
users accessing the system so that a minimum quality can be
means for scheduling at least one of said users in at least
guaranteed for each user. In accordance with the time-code 10
one of said time-frequency slices so as to optimize the
slicing system of the invention, the scheduling and the time
use of said communications transmission medium;
slots provide direct control on the number of users accessing
wherein at least one of said users modulates a respective
a time slot (i.e., exercising an aspect of congestion control),
transmitted signal over two or more frequency slice
thereby guaranteeing a particular quality of service for large
allocations in said communications transmission
user populations.
medium, wherein said at least one of said users occu15
FIG. 10 depicts a similar application of the system and
pies two or more time-frequency slices extending over
method of the invention to a full, three dimensional "timetwo or more frequency slices allocations in said comfrequency-code" sharing scheme. The total space 40" occumunications transmission medium; and
pied by the transmission medium can be visualized in three
wherein said two or more time-frequency slices do not
dimensions as divided into the time (44), frequency (42) and
form continuous allocation.
20
code (43) domains. Here, optimization of the assignment of
2. A system for optimizing spectral use of a communicaavailable code space so as to minimize "noise" or "interfertions transmission medium by a plurality of varying userence" is accomplished by frequency multiplexing as well as
application and access rates, comprising:
time multiplexing. Optimum code reuse in both the frea plurality of frequency slices in said communications
quency and time domains is thus achieved.
transmission medium;
25
I! will be appreciated that the system ami method accorda plurality of time slices in said communications transing to the invention substantially improves usage of the
mission medium;
available communications transmission medium and conmeans for slicing the communications transmiss1on
tributes to greater spectral efficiencies than with current
medium into a plurality of time-frequency slices, each
approaches. As an example, one may consider a time- 30
of said time-frequency slices occupying a space in said
frequency slice system in which there are N time slots per
communications transmission medium equal to at least
(periodic) frame. For simplicity, one may assume that there
one frequency slice allocation measured over one time
are only two classes of users: low-speed users that require
slice allocation;
only one unit time-frequency slice per frame (i.e., a transwherein at least one of said users modulates his respective
mission using one frequency band for one time slot), and 35
signal to cover two or more frequency slice allocations
high-speed users that require X unit slices per frame. We
in said communications transmission medium;
also assume there are a total of F frequency bands.
means for scheduling at least one of said users in at least
With a Universal-Time-Slot system, only one user (either
one of said time-frequency slices so as to optimize the
low-speed or high-speed) transmits per time slot, and any
use of said communications transmission medium;
mix of (at most) N high- and low-speed users can be active. 40
wherein said at least one user modulates his respective
By contrast, in a Time-Frequency-Sliced system according
signal on a multi-tone scheme, wherein each of the
to the invention, one may potentially support up to (FN)
tones modulated by said user is allocated to a separate
low-speed users, or (F/X)N high-speed users, or any mix of
frequency slice; and
high- and low-speed users in which each reduction in the
wherein said frequency slice allocations are not contigunumber of high-speed users increases the number of low- 45
ous.
speed users by X. Thus, achievable capacity improvement
3. A system for optimizing spectral use of a code-divisionfactor is between (F/X) and F. Certain factors such as
multiple-access (CDMA) transmission medium by a pluralrelative traffic demands and performance requirements of
ity of users of varying user-application and access rates,
the high- and low-speed users, and selection of the scheduling algorithm, will contribute to the overall efficiency of 50 comprising:
a plurality of code slice allocations collectively representthe system and method of the invention.
ing a quantity of code space contained in said transThus, the system and method according to the invention
mission medium;
provides optimum access to a communications resource for
a plurality of frequency slices in said transmission
multiple users at a variety of speeds while maintaining both
medium;
low-cost access for low-speed users and a good spectral 55
efficiency.
means for slicing the transmission medium into a plurality
of code-frequency slices;
It will be apparent that other and further forms of the
means for scheduling one or more users in at least one of
invention may be devised without departing from the spirit
said code-frequency slices in said transmission
and scope of the appended claims, it being understood that
medium, wherein said means for scheduling schedules
the invention is not limited to the specific embodiments 60
shown.
a quantity of code space based on a level of interference
We claim:
contributed by each user in said transmission medium,
1. A system for optimizing spectral use of a communicathe scheduling based on a number and type of users for
tions transmission mt:dium by a plurality of ust:rs of varying
tach of said code-frequt:ncy slices;
user-application and access rates, comprising:
65
wherein a signal transmitted by a user in said transmission
a plurality of frequency slices in said communications
medium is assigned a quantity of code space in said
transmission medium;
transmission medium; and

DEFS0006854

6,018,528

11

12

wherein said quantity of code space is inversely related to
a quantity of code space to each of said users of the
transmission medium.
the length of code assigned to a user.
10. The system in accordance with claim 9, wherein said
4. A system for optimizing spectral use of a code-divisionmeans for scheduling schedules users to said code-timemultiple-access (COMA) transmission medium by a pluralfrequency slices based on the user-application and access
ity of users of varying user-application and access rates,
rates of said users.
comprising:
11. A method for optimizing spectral use of a communia plurality of code slice allocations collectively representcations transmi~sion medium by a plurality of users of
ing a quantity of code space contained in said transvarying user-application and access rates, comprising the
mission medium;
steps of:
a plurality of time slices in said transmission medium; 10
dividing the transmission medium into a plurality of
means for slicing the transmission medium into a plurality
frequency slices;
of code-lime slicts;
dividing the transmission medium into a plurality of time
means for scheduling one or more users in at least one of
slices;
said code-time slices in said transmission medium, l5
slicing the transmission medium into a plurality of timewherein said means for scheduling schedules a quantity
frequency slices, each of the time-frequency slices
of code space based on a level of interference contriboccupying space at least equal to one frequency slice
uted by each user in said transmission medium, the
extending over one time slice;
scheduling based on a number and type of users for
scheduling at least one of said users in at least one of said
each of said code-time slices.
20
time-frequency slices so as to optimize the use of the
5. The system in accordance with claim 4, wherein a
space contained within said communications transmissignal transmitted by a user in said transmission medium is
sion medium;
assigned a quantity of code space in said transmission
modulating the signal emitted by a user over two or more
medium.
frequency slices in said communications transmission
6. The system in accordance with claim 5, wherein said 25
medium; and
quantity of code space is inversely related to the length of
wherein said step of scheduling further comprises the step
code assigned to a user.
of scheduling two or more time-frequency slices having
7. Asystcm for optimizing spectral use of a code-divisionnon-contiguous frequency slice allocations.
multiple-access (COMA) transmission medium by a plural12. A method for optimizing spectral use of a COMA
ity of users of varying user-application and access speeds, 30 commuoications transmission medium by a plurality of
comprising:
users of varying user-application and access rates, comprisa plurality of code slice allocations representing a quantity
ing the steps of:
of code space contained in said transmission medium;
slicing the transmission medium into a plurality of code
a plurality of time slices in said transmission medium;
slice allocations collectively representing a quantity of
code space contained within said transmission medium;
means for slicing the transmission medium into a plurality 35
of code-time slices;
slicing the transmission medium into a plurality of timeslice allocations;
a set of individual codes contained within said transmisslicing the transmission medium into a plurality of codesion medium;
time slices, each of the code-time slices occupying
means for assigning an individual code having a length to 40
space at least equal to one code slice allocation extenda user of said transmission medium, the length of said
ing over one time slice allocation; and
individual code inversely related to a quantity of code
scheduling one or more of said users in at least one of said
space to be occupied by said user;
code-time slices in the transmission medium according
means for scheduling one or more users in at least one of
to the amount of code space required by each of said
said code-time slices in said transmission medium, 45
users so as to optimize the occupancy of the code space
wherein said means for scheduling assigns individual
contained within the communications transmission
length codes to said users based on the code space
medium.
requirements of the users in said transmission medium.
13. A method for optimizing spectral use of a COMA
8. The system of claim 7, wherein at least one of said
individual codes is reassigned to a user based on temporal 50 communications transmission medium by a plurality of
users of varying user-application and access rates, comprisoccupancy of said at least one individual code in the
ing the steps of:
transmission medium.
slicing the transmission medium into a plurality of code
9. A system for optimizing spectral use of a code-divisionslice allocations collectively representing a quantity of
multiple-access (COMA) transmission medium by a pluralcode space contained within said transmission medium;
ity of users of varying user-application and access speeds, 55
slicing the transmission medium into a plurality of frecomprising:
quency slice allocations;
a plurality of code slice allocations representing a quantity
slicing the transmission medium into a plurality of codeof code space contained in said transmission medium;
frequency slices, each of the code-frequency slices
a plurality of time slices in said transmission medium;
occupying space at least equal to one code slice allo60
a plurality of frequency slices in said transmission
cation extending over one frequency slice; and
medium;
scheduling one or more of said users in at least one of said
means for slicing the transmission medium into a plurality
code-frequency slices in the transmission medium
of code-time-frequency slices;
according to the amount of code space required by each
of said users so as to optimize the occupancy of the
means for scheduling one or more users in at least one of 65
said code-time-frequency slices in said transmission
code space contained within the communications transmedium, wherein said means for scheduling schedules
mission medium.

DEFS0006855

6,018,528

13

14

14. A method for optimizing spectral use of a CDMA
15. A method for optim1zmg spectral use of a codecommunications transmission medium by a plurality of
division-multiple-access (CDMA) transmission medium by
users of varying user-application and access rates, comprisa plurality of users of varying user-application and access
ing the steps of:
speeds, comprising the steps of:
slicing the transmission medium into a plurality of code
slice allocations collectively representing a quantity of
slicing the transmission medium into a plurality of code
code space contained within said transmission medium;
slice allocations representing a quantity of code space
slicing the transmission medium into a plurality of time
contained in said transmission medium;
slices;
slicing the transmission medium into a plurality of time
slicing the transmission medium into a plurality of code- 10
slices in said transmission medium;
time slices, each of the code-time slices occupying
space at least equal to one code slice allocation extendslicing the transmission medium into a plurality of freing over one time slice allocation;
quency slices in said transmission medium;
assigning an individual user a code from a set of indislicing the transmission medium into a plurality of codevidual codes contained within said transmission
time-frequency slices; and
medium, the length of said individual code inversely 15
related to a quantity of code space to be occupied in the
scheduling one or more users in at least one of said
medium by said user; and
code-time-frequency slices in said transmission
scheduling one or more of said users in at least one of said
medium according to the amount of code space
code-time slices in the transmission medium, wherein
required by each of said users so as to optimize the
the means for scheduling assigns an individual length 20
occupancy of the code space contained within the
code to a user based on code space requirements of a
communications transmission medium.
user so as to optimize the occupancy of the code space
contained within the communications transmission
medium.
* * * * *

DEFS0006856