United States Patent (19)
`Giallorenzi et al.
`
`US006091760A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,091,760
`Jul.18, 2000
`
`54) NON-RECURSIVELY GENERATED
`ORTHOGONAL PN CODES FORWARIABLE
`RATE CDMA
`
`75 Inventors: Thomas R Giallorenzi, Herriman;
`Samuel C Kingston, Salt Lake City;
`Lee A Butterfield, W. Jordan; William
`T Ralston, Riverton; Leon L
`Nieczyporowicz, West Jordan; Alan E
`Lundquist, Salt Lake City, all of Utah
`73 Assignee: L-3 Communications Corporation,
`New York, N.Y.
`
`21 Appl. No.: 09/329,473
`22 Filed:
`Jun. 10, 1999
`Related U.S. Application Data
`63 Continuation-in-part of application No. 09/328,546, Jun. 9,
`1999.
`60 Provisional application No. 60/091,070, Jun. 29, 1998.
`(51) Int. Cl." ..................................................... H04B 71216
`52 U.S. Cl. ........................... 375/140; 370/208; 370/342
`58 Field of Search ..................................... 375/130, 140,
`375/141, 145, 146; 370/203, 208, 320,
`335, 342, 441, 479
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,810,019 5/1974 Miller ...................................... 375/260
`5,151,919 9/1992 Dent .................
`... 375/1
`5,204.876 4/1993 Bruckert et al. .
`... 375/1
`5,329,547 7/1994 Ling .....................
`... 375/1
`5,418,813 5/1995 Schaffner et al.
`375/205
`5,442,625 8/1995 Gitlin et al. .............................. 370/18
`5,515,396 5/1996 Dalekotzin ...
`... 375/206
`5,548,613 8/1996 Kaku et al. ......
`... 375/208
`5,659,573 8/1997 Bruckert et al. .
`... 375/200
`5,729,124 3/1998 Lu ....................
`324/76.24
`5,748,668 5/1998 Tomita et al.
`... 375/200
`5,751,761
`5/1998 Gilhousen ...
`... 375/200
`5,757,767 5/1998 Zehavi .........
`... 370/208
`5,805,567 9/1998 Ramesh ............
`... 370/204
`5,805,584 9/1998 Kingston et al. ....................... 370/342
`
`5,825,835 10/1998 Kingston et al. ....................... 375/367
`5,851,187 12/1998 Thomas, III et al. .................. 600/447
`5,864,548
`1/1999 Liu .......................................... 370/320
`5,926,488 7/1999 Khayrallah ..
`... 371/37.01
`5.936.972 8/1999 Meidan et al...
`... 371/20.1
`5,995,807 11/1999 Magnier et al. ....................... 455/67.6
`
`
`
`OTHER PUBLICATIONS
`
`Multiplexing Of Telephone Signals. By Walsh Functions,
`Davidson, I.A., Applications Of Walsh Functios, 1971 Pro
`ceedings, Apr. 13, 1971, pp. 177-179.
`“Multiplex Systems. Using Sums Of Walsh Functions AS
`Carriers”, Hubner, H., Applications Of Walsh Functions,
`1971 Proceedings, Apr. 13 1971, pp. 180-191.
`“The Use Of Walsh Functions For Multiplexing Signals”,
`Davidson, I.A., Applications Of Walsh Functions, 1970
`Proceedings, pp. 23-25.
`“On The Transmission Of Walsh Modulated Multiplex Sig
`nals”, Hubner H., Applications Of Walsh Functions, 1970
`Proceedings, pp. 41-45.
`“Analog And Digital Multiplexing By Means Of Walsh
`Functions”, Hubner, H., Applications Of Walsh Functions,
`1970 Proceedings, pp. 238–247.
`
`Primary Examiner Young T. Tse
`Attorney, Agent, or Firm-Perman & Green, LLP
`57
`ABSTRACT
`A method and apparatus for constructing a Series of PN code
`Sets that can be used for multirate Synchronous and quasi
`synchronous CDMA systems. The construction technique
`produces PN codes that are balanced, and that furthermore
`do not require any Synchronization of neighboring base
`Stations. The method is a non-recursive method that uses a
`permuted orthogonal matrix to modulate permuted orthogo
`nal matrices to create PN codes that Support multirate
`operation. Furthermore, the codes constructed using the
`method have very good spectral properties (if chosen
`properly) when the code length, n, is reasonably large.
`
`20 Claims, 13 Drawing Sheets
`
`MATRIX
`SEQUENCE
`
`
`
`
`
`
`
`
`
`
`
`
`
`SCAAR X MATRIX
`MULTIPLICATION
`
`:
`{th
`: "MODULATED
`MATRIX
`i
`SEQUENCE
`:
`OUTPUT
`
`CLOCKED ONCE
`EVERY n CHIPS
`(EVERY MATRIX)
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`001
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 1 0f 13
`
`6,091,760
`
`40m2>m
`
`40m
`
`m
`
` Aomz>m
`Ac\om32V3:,$8
`?\omKEV3N;$8
`Ac\om38v3:;$8
`?m\om28vAcmvpa$8
`
`Acqom38v€89$8
`Acm\om88VAcmvm;$8
`?m\om88vAcmvss$8
`ACQQmEEVAcmvcm;$8
`Acqom88vAcmvTcmg$8
`
`Jomzxm
`
`2.0m
`
`Fm<moEm
`
`002
`
`ONE-E-WAY 2007
`
`Apple V. One-E-Way
`IPR2021-00283
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`002
`
`

`

`U.S. Patent
`US. Patent
`
`Jul. 18, 2000
`
`Sheet 2 0f 13
`
`6,091,760
`6,091,760
`
`3>
`(u) ,
`
`E<$035a22....
`
`
`
`
`
`
`
`
`
`¢._om2>mm,40m2>mN4825_485m
`
`gag?
`{oz888_$8._=8
`
`g;:303,9la!
`{omBE6N$8._:8
`{um38ST:$8._=8
`
`
`gggg
`{omBE6F$8.N:8
`{omBE8N$8.N:8
`{um8887:$8.N:8
`
`003
`
`ONE-E-WAY 2007
`
`Apple V One-E-Way
`IPR2021-00283
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`003
`
`
`
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 3 0f 13
`
`6,091,760
`
`
`
`958zit;8502238Eszmm¢<
`
`<
`
`C
`
`\
`
`mzzaooMEEEQCCmesazit;mag2238MEEEQ<
`___unuamns_Dun_n__"$525:2,
`
`_
`
`m
`
`_W
`
`"g
`_______3;:
`A33.F3“
`
`____
`
`__
`
`
`
`A83.{fig3.;HA3;
`
`o¢.o_..._
`
`WIllllllllllllllllllllllllllllllllllllllllllll1..
`
`L X
`
`EEExm5<om
`
`zo_._.<o:n=._..5§
`
`
`823002SHmozoomxogo
`
`mwazwfimwm2%:$93
`xazz8:6:Ema
`
`"uu_
`
`.V"mozwaowm
`
`XEZE
`
`.SQZ
`
`004
`
`ONE-E-WAY 2007
`
`Apple V One-E-Way
`IPR2021-00283
`
`___________.
` mobhaoozm<._<om5.:u_
`
`
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`004
`
`
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 4 0f 13
`
`6,091,760
`
`
`
`5950mozmaomfi
`
`
`
`XEEEQmHEDQOE8—F
`
`
`
`mob/Dame:m5<omHmF
`
`
`5E3).83:825._x22;
`flmozm30mm
`
`
`
`5&8mozwsomm5.Sn_z_
`
`
`
`KOHEDQOEm<._<oma
`
`
`
`x_m._.<§QESDQOE£0
`
`m<._<omo5&8mozmaam5
`
`moHSDQOE
`
`flaw:
`
`m485mmgomzxmv4.825mJomzxmm.2525_gomzrm
`
`
`$va83cm\omBE6mmnoo
`28—:$3:N\omBEE880
`
`VP:$3{om886$68
`
`3“
`
`005
`
`ONE-E-WAY 2007
`
`Apple V One-E-Way
`IPR2021-00283
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`005
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 5 of 13
`
`6,091,760
`
`as as as essa
`
`st St St S
`e gas e a
`s
`K9
`{
`
`as as
`
`era
`
`st St NS
`S. S. S. S.
`g-d
`Cld
`CD
`C
`
`-sa
`
`-
`
`-- - - -
`C
`as 1 as 1 S-1 S-1
`
`era. es -sa ea
`C
`C
`
`S. 1 S 1 S1
`-
`-
`-
`
`S.
`
`arts
`
`as area
`
`-sa
`
`& 1 S 1 S. 1 S1
`Xa
`SN
`SN S
`O - C -
`
`as
`
`as as
`s
`
`-sa
`
`is 1 as 1 as 1 as 1
`
`Ya
`
`sa
`
`sa.
`
`as a
`
`es
`
`r --a --
`
`C
`a- N-1 n-1 se
`eless
`ears.
`as
`es
`2,
`2
`c
`c
`s
`
`2,
`9
`
`-ra
`
`-r-, -a -
`
`& S 1 S 1 S. 1
`Cld
`d
`(s
`
`Xa
`
`assa
`
`Yale
`
`ser
`
`es - - er
`
`s
`c
`
`s
`-
`
`c.
`
`is
`-
`
`era
`
`O ve
`Z
`O
`r
`c
`C
`L
`N-1
`O
`CO
`
`era. as as --a
`C C g
`
`g a
`
`c)
`
`d
`
`s
`
`C
`
`as
`
`era -ra as -sa
`S-1 S-1 S-1 S-1
`s Sk S. Sk
`
`C
`S-1 S-1 S-1 S-1
`s
`ways
`s
`s
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`006
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 6 of 13
`
`6,091,760
`
`
`
`:
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`007
`
`

`

`US. Patent
`
`Jul.18,2000
`
`Sheet 7 0f 13
`
`6,091,760
`
`mAom§>m
`
`mgomzrm
`
`m40m2>m 55%
`
`N40m2>m
`
`FJom§>m
`
`¢40m2>m
`am40m2>m
`aNJomz>m
`F40m2>m
`
`oJomz>m mgomz>m
`
`wgom2>m
`
`m40m2>m
`
`N40m2>m
`
`F40m2>m
`
`
`
`F=8
`
`F=8F=8
`
`vVv
`
`N__8
`
`N=moN2mg
`
`vVJF
`
`{ozBE6
`
`mmvoo
`
`:N\ommFP.Fo
`
`cN\om88Ho
`
`manoo
`
`mouoo
`
`c\om®F9_Fo
`
`mwnoo
`
`:N\om38E
`
`cN\om88B
`
`monoo
`
`mmuoo
`
`008
`
`ONE-E-WAY 2007
`
`Apple V One-E-Way
`IPR2021-00283
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`008
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 8 0f 13
`
`6,091,760
`
`zaomgmmo
`
`mooo
`
`in,
`
`9%.N“.500Fmooo
`
`mm._.<on_:
`
`>mm>m
`
`EIQ
`
`EIE30
`
`2<mmo20m:0:
`
`mtmcmxcmflm“*0mm
`
`“IIImm.
`
`99238EoQz<
`E538:m:6053
`
`>mm>m
`
`n=Iomm
`
`
`
`BEE:V530
`
`mozmpomm1.5881
`
`
`
`
`
`mmmmofiE5238Emsmbgé...zo
`
`Emmasz/‘E
`
`mmEQnS
`
`mn=Ioc>mm>m
`
`fl
`
`QUE
`
`ON/
`
`mtmoxomflm.._o
`
`
`
`2%mo>83..mm:22E.02..az<
`
`2.4m:0:mo30mmoz<§§oo
`
`
`
`8v::82:
`
`mommmooma
`
`820%
`
`E5
`
`
`
`cEmaxnwmwQ
`
`009
`
`ONE-E-WAY 2007
`
`Apple V One-E-Way
`IPR2021-00283
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`009
`
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 9 of 13
`
`6,091,760
`
`7 |
`
`Tl+)
`
`0N?OWBèjdS
`
`QOO ud OS
`
`103130 || ON
`
`NWHOTBOJIS
`
`|
`
`
`
`èJO LOW
`
`BTWOS
`
`3000
`
`caeso,
`
`
`
`
`
`
`
`
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`010
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`
`
`Sheet 10 Of 13
`
`6,091,760
`
`
`||WX [18}}
`·6·3
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`011
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 11 of 13
`
`6,091,760
`
`H 4.
`
`1
`
`-1 - 1
`
`1
`
`FIG. 11 O
`
`RC = 3 1 2 4)
`
`FIG.11b.
`
`16
`
`
`
`
`
`
`
`RANDOM
`NUMBER
`GENERATOR
`
`
`
`REORDER
`PATTERN
`
`16O
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`012
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 12 of 13
`
`6,091,760
`
`Reordering code = 3 5 2 7 1 8 4 6)
`
`Walsh Code= |
`
`1 - 1 - 1
`
`1
`
`1 - 1 - 1
`
`1
`
`1 -1 - 1 - 1
`
`1 - | PFG. 12
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`013
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 13 of 13
`
`6,091,760
`
`
`
`=uo/Su?Au?TM Tepoo Tp3 wap joey
`
`
`
`
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`014
`
`

`

`1
`NON-RECURSIVELY GENERATED
`ORTHOGONAL PN CODES FORWARIABLE
`RATE CDMA
`
`6,091,760
`
`CROSS-REFERENCE TO ARELATED PATENT
`APPLICATION
`This patent application is a continuation-in-part of
`copending and commonly assigned U.S. patent application
`Ser. No. 09/328,546, filed Jun. 9, 1999 as Express Mail No.:
`EL 067 101 377 US, entitled “PN Code Selection for
`Synchronous CDMA', by Leon Nieczyporowicz, Thomas
`Giallorenzi and Steven B. Perkins, which in turn claims
`priority under 35 U.S.C. S 119(e) from Provisional Patent
`Application 60/091,070, filed Jun. 29, 1998, entitled “PN
`Code Selection for Synchronous CDMA', by Leon
`Nieczyporowicz, Thomas Giallorenzi and Steven B. Per
`kins. The disclosure of these two patent applications is
`incorporated by reference herein in their entireties.
`
`5
`
`15
`
`FIELD OF THE INVENTION
`This invention is generally related to telecommunications
`Systems and apparatus that employ spreading codes and, in
`particular, relates to methods and apparatus for generating a
`Set of spreading codes that are optimized for a multi-user,
`multi-rate environment.
`
`25
`
`BACKGROUND OF THE INVENTION
`In the forward direction of a Code Division, Multiple
`Access (CDMA) system, i.e., from a base station or base unit
`to a Subscriber unit, it is relatively easy to Synchronize the
`pseudonoise (PN) codes of the various channels, Since they
`are all created at and transmitted from the same base Station.
`It is furthermore very easy to time-align the chips and
`35
`Symbols of the constituent Signals within the aggregate
`waveform. As a result, the forward channel of most CDMA
`systems utilizes some form of synchronous CDMA. In some
`Systems, Such as a fixed wireleSS local loop telephone System
`known as Primewave 2000TM available from the assignee of
`this patent application, the reverse channel (i.e., Subscriber
`unit to base station) is also quasi-synchronous. In this type
`of System, a timing control loop is utilized to maintain the
`various users in the System time-aligned Such that their
`respective signals all arrive at the base Station within a Small
`fraction of a chip of each other.
`Whenever synchronous or quasi-synchronous CDMA is
`employed, it becomes possible to use PN codes which are
`designed to have the Smallest possible cross-correlation
`when time-aligned with each other. If the number of users in
`the System is less than the number of chips transmitted for
`each channel symbol (which may be referred to as the
`channel Symbol processing gain), then it is possible to
`design PN codes that are truly orthogonal to each other.
`When the number of users exceeds the channel symbol
`processing gain, then it is no longer possible to design codes
`that are orthogonal, Since the dimensionality of the Signaling
`Space has been exceeded. For this reason, it is possible for
`Synchronous and quasi-synchronous CDMA Systems to Sup
`port a number of users equal to the channel Symbol pro
`cessing gain, as long as the links have adequately large
`power and adequately low interference resulting from dis
`tortions Such as clipping, multipath, filtering and timing
`offsets.
`It is often desirable for the system to support users which
`are not all at the same Signaling rate. For example, in a
`System where Some users are using a telephone and the
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`required date rate is on the order of a few thousand bits per
`second (Kbps) to a few tens of Kbps, while other users are
`using the System as a computer network interface and
`require a million bits per Second (Mbps) or more, the
`waveform should to be able to Simultaneously accommodate
`the various non-homogeneous users.
`It is possible to Support a high rate user by allocating to
`him or her a plurality of parallel, lower rate channels, but
`this approach requires that the high rate users have a
`plurality of transmitters and receivers. AS Such, this
`approach is less than desirable in many Systems where cost
`is an important consideration.
`A more cost-effective technique to Support high rate and
`low rate users simultaneously is to employ a common
`chipping rate for all users, but to permit the users in the
`System to vary their channel Symbol processing gains
`depending on their respective data rate. This implies that if
`one desires that all users in either the forward, or the forward
`and reverse channels, to be orthogonal to each other, inde
`pendent of their rates, then a set of PN codes are needed of
`various lengths, and that are mutually orthogonal when
`Synchronized appropriately.
`Walsh functions are a set of binary and orthogonal wave
`forms that can be used for Signal multiplexing purposes, and
`have long been recognized as having application to tele
`phony. Reference in this regard can be had to an article
`entitled “The Multiplexing of Telephone Signals by Walsh
`Functions”, by I. A. Davidson in Applications of Walsh
`Functions, 1971 proceedings, Second Edition, Eds. R. W.
`Zeek and A. E. Showalter, pages 177-179.
`Of the number of possible sets of orthogonal functions
`that can be used as carriers in multiplex transmission, the
`category of the completely orthogonal Hadamard functions
`have also been long recognized as being particularly well
`Suited for technical applications, including telephony appli
`cations. In general, Walsh functions are special Hadamard
`functions, and can be described by Hadamard matrices with
`powers of 2 as ordinary numbers. Further function Systems
`can be derived from Hadamard matrices by permutation of
`columns and rows and by Sign inversion, while preserving
`their orthogonal characteristics.
`One method for creating PN codes which are mutually
`orthogonal is to use a recursive construction technique
`defined by H. Hubner, “Multiplex Systems. Using Sums of
`Walsh Functions as Carriers”, also in Applications of Walsh
`Functions, 1971 proceedings, Second Edition, pages
`180-191.
`Reference in this regard can also be had to U.S. Pat. No.
`5,571,761, entitled “System and Method for Orthogonal
`Spread Spectrum Sequence Generation in Variable Data
`Rate Systems”, by Klein S. Gilhousen.
`These approaches are based upon the Walsh-Hadamard
`construction technique defined as follows:
`
`w(n) w(n)
`w(n) - w(n)
`
`(1)
`
`where w(n) is an n x n matrix of +1 values. If one defines
`w(1)=1, then it follows that,
`
`w(2) =
`
`+ 1 + 1
`+1 - 1
`
`2
`(2)
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`015
`
`

`

`6,091,760
`
`and also that,
`
`+1
`+1
`
`+1
`
`(3)
`
`4
`offset in the receiver of the signal. In other words, if the
`chips are +1 millivolts in the receiver, but there is a 2
`millivolt DC offset in the signal at the input of the
`despreader, then the despreader would have to multiply the
`t1 despreading code with an input signal having values of
`+3 and +1 millivolts. However, if the PN code is balanced
`over a symbol, then the DC offset will not affect the
`despreading process.
`In general, and referring briefly to FIG. 1b, the approach
`used in U.S. Pat. No. 5,751,761 is a recursive approach,
`wherein the value of the nth output of y is created from a
`previous value of y, So long as n>0. In other words, past
`relationships are used to create new, current relationships
`between code elements.
`AS has been made apparent, the use of Such a recursive
`technique to create PN code sets for use in multirate CDMA
`System can result in problems.
`
`OBJECTS AND ADVANTAGES OF THE
`INVENTION
`It is a first object and advantage of this invention to
`provide an improved technique for providing PN codes for
`use in a CDMA communications System having a plurality
`of users Simultaneously operating at different data rates.
`It is a further object and advantage of this invention to
`avoid the problems inherent on the prior art recursive
`techniques that apply a cover code to a code matrix in an
`attempt to make the code Set appear more random.
`It is another object and advantage of this invention to
`provide a non-recursive technique for constructing a Series
`of mutually orthogonal sets of PN codes which support
`multirate signaling, wherein the Series of Sets of PN codes
`have the desirable properties that the constituent codes are
`balanced at all of the desired symbol rates, and that further
`more the constituent codes exhibit good spectral properties.
`It is a still further object and advantage of this invention
`to provide a non-recursive technique for constructing a
`series of balanced PN code sets that can be used to advan
`tage in multirate Synchronous and quasi-synchronous
`CDMA Systems, wherein the technique employs a permuted
`orthogonal matrix to modulate permuted orthogonal matri
`ces to create balanced PN code Sets that Support multirate
`operation.
`
`SUMMARY OF THE INVENTION
`The foregoing and other problems are overcome and the
`objects and advantages of the invention are realized by
`methods and apparatus in accordance with embodiments of
`this invention.
`A method is disclosed for constructing a Series of mutu
`ally orthogonal sets of PN codes which support multirate
`signaling. This series of sets of PN codes has the desirable
`properties that the constituent codes are balanced at all of the
`desired Symbol rates, and also exhibit good spectral prop
`erties (provide a data randomization function). Furthermore,
`this series of sets of PN codes permits efficient multicell
`operation, Since any constituent code of one set appears to
`be approximately random relative to any constituent code of
`any other Set. These improved codes are can be used to
`advantage in the forward channel (point-to-multipoint
`direction) of CDMA systems, but may also be employed in
`the reverse channel if the reverse link employs quasi
`synchronous CDMA.
`A non-recursive technique is disclosed for constructing a
`series of PN code sets that can be used for multirate
`
`This construction technique is recursive since it obeys the
`equation
`(4)
`f(n)=g(f(n)), man
`for Some functions f,g and indexes m,n, where m>n. In other
`words, the m' function, f, is created solely from an
`operation, g, on a previous version of f, namely f(n). A
`15
`function is considered to be recursive if it obeys equation
`(4). By letting f=w, m=2n, one can see that g is defined by
`equation (1).
`This construction technique permits multi-rate orthogonal
`Signaling on a Synchronous CDMA System, Since the Walsh
`Sequences of length n can Support users at a channel Symbol
`rate of Rs=Rc/n (where Rc is the chip rate), while the Walsh
`Sequences of length 2n can Support lower rate users of rate
`RS =Rc/2n. In order to illustrate this point, let w(n) be the
`j" +1 valued chip in the i' row of the code matrix. If only
`one subscript is used, w (n), let that represent the i' row of
`the code matrix, or in other words, the i” PN code in the set
`having n chips in the vector. Clearly both i and are integers
`ranging from 1 to n. When these codes are used for multi
`rate CDMA operation, the users at the various rates are
`either perfectly correlated or are orthogonal, as is illustrated
`by FIG. 1a.
`In FIG. 1a it can be seen that there is a choice of
`Supporting n users at rate Rc/n, 2n users at rate Rc/2n, or a
`number of users between n and 2n at mixed rates. If, for
`example, a user employs code w(n) at rate Rc/n, then codes
`w(2n) and w(2n) at rate Rc/2n may not be used, since they
`are not orthogonal with the user employing code w(n) at
`rate Rc/n. Other users may employ codes w(2n) and W(2n)
`at rate Rc/2n Since they are all mutually orthogonal, even
`though they are at different data rates.
`However, there are Several problems with the approach
`described in U.S. Pat. No. 5,751,761. First of all, if the
`Walsh codes are used directly then the Spectral properties of
`the PN codes would be very poor. This is due to the fact that
`the codes are made up of very regular patterns as is illus
`trated by equation (3). Some codes are completely unspread,
`while others are spread with Square waves whose frequen
`cies are one, two, four, eight, etc. times the Symbol rate.
`These users would have very limited immunity to jammers,
`50
`and would not enjoy the benefits of being spread with a PN
`code of processing gain n or 2n (depending on their rate).
`In U.S. Pat. No. 5,751,761, the approach used to avoid
`this problem is to apply a cover code to the code matrix. This
`amounts to multiplying every code in the Set by a single
`randomizing vector of t1 valued chips whose length is much
`larger than the channel Symbol processing gain. So long as
`every code in the Set is multiplied by the same cover code,
`the orthogonality of the Set is retained, but the resulting Set
`is made to appear more random.
`However, a problem that arises when applying a cover
`code to the matrix is that the resulting randomized Walsh
`codes are not balanced. This means that, over any symbol
`period, the number of +1 valued chips and -1 valued chips
`are not equal to one another in most of the resulting PN
`codes. Balance in the code Set is a very desirable property,
`Since it implies that the codes are orthogonal to any DC
`
`25
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`016
`
`

`

`6,091,760
`
`S
`Synchronous and quasi-synchronous CDMA Systems. The
`construction technique is Superior to conventional tech
`niques in that it produces PN codes that are balanced, and
`that furthermore do not require any Synchronization of
`neighboring base Stations. This approach may be character
`ized as using a permuted orthogonal matrix to modulate
`permuted orthogonal matrices to create PN codes that Sup
`port multirate operation. Furthermore, the codes constructed
`using the method of this invention have very good spectral
`properties (if chosen properly) when the code length, n, is
`reasonably large.
`A non-recursive method is provided for constructing
`balanced PN code sets for use in a CDMA communication
`System. The method includes Steps of (a) applying a con
`Strained permutation to a GXG t1 valued matrix to form a
`modulation matrix M(G); and (b) using the modulation
`matrix M(G) to create a set of available PN codes for a first
`cell by modulating R unique nxn permuted code sets, c'(n)
`to c'(n) by successive scalar elements of M(G). The step of
`using the modulation matrix M(G) comprises a step of
`operating a Scalar times matrix multiplier.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The above set forth and other features of the invention are
`made more apparent in the ensuing Detailed Description of
`the Invention when read in conjunction with the attached
`Drawings, wherein:
`FIG. 1a depicts a conventional timing diagram of various
`Walsh codes used at rates Rc/n and Rc/2n;
`FIG. 1b is a simple block diagram depicting a recursive
`function generator, and which is useful in explaining a prior
`art Walsh code Set generation technique,
`FIG. 2 illustrates a timing diagram of various cell #1 and
`cell #2 Walsh codes used at rate Rc/n, and assuming that
`R=3;
`FIG. 3 is an illustration of permissible permutations of a
`Walsh matrix to obtain M(G), where G=8, and where the
`notation was (8) indicates the jth column of w(8), by
`including the elements of rows 1:8 and column i;
`FIG. 4a depicts the details of a jth scalar modulator
`working on the Sequence of permuted matrices for cell #1;
`FIG. 4b illustrates a procedure for generating the codes
`for cell #1 by modulation the sequence of permuted cell #1
`n X in code sets with the G rows of the modulation matrix
`M(G);
`FIG. 5 is a diagram showing code Sequences for use in cell
`#1 for a case described by a first example (Example 1);
`FIG. 6a depicts an Equation 10 useful in explaining a
`matrix used to modulate a Sequence of permuted matrices
`for cell #1, in accordance with a second example (Example
`2);
`FIG. 6b is a diagram showing code Sequences for use in
`cell #1 for a case described by the second example, where
`the boxes delineate the intended symbol boundaries at
`various data rates,
`FIG. 7 illustrates a timing diagram of various cell #1 and
`cell #2 Walsh codes used at rates Rc/n and Rc/2n, assuming
`that R=3, G=2, and the M(2) matrix employed in the first
`example,
`FIG. 8 is a block diagram of a PN code generation circuit;
`FIG. 9 is a simplified block diagram of a synchronous,
`Spread spectrum CDMA fixed wireleSS communications
`System in accordance with an embodiment of this invention;
`FIG. 10 is an exemplary frequency allocation diagram of
`the system of FIG. 9.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIG. 11a illustrates an exemplary Hadamard (H) matrix,
`FIG.11b illustrates a Reordering Code (RC), and FIG.11c
`illustrates a Reordered Hadamard (RH) code matrix in
`accordance with the invention described in the above
`referenced commonly assigned U.S. patent application Ser.
`No. 09/328,546, filed Jun. 9, 1999, entitled “PN Code
`Selection for Synchronous CDMA', by Leon
`Nieczyporowicz, Thomas Giallorenzi and Steven B. Per
`kins,
`FIG. 12 illustrates an exemplary 8x8 Walsh code matrix,
`an exemplary reordering code, and the resultant reordered
`Walsh code matrix, in accordance with the invention
`described in the above-referenced commonly assigned U.S.
`patent application Ser. No. 09/328,546, filed Jun. 9, 1999,
`entitled “PN Code Selection for Synchronous CDMA";
`FIG. 13 illustrates an exemplary inversion pattern for
`application to the reordered Walsh code matrix of FIG. 12,
`and the resultant inverted, reordered Walsh code matrix, in
`accordance with that invention; and
`FIG. 14 is a simplified block diagram of a reordering
`pattern or code generator and a shift register for reordering
`a PN code.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`Because of the desirability to provide mutually orthogonal
`PN codes that exhibit good spectral properties, and that are
`also balanced, a technique for generating n x n mutually
`orthogonal matrices was described in the above-referenced
`U.S. patent application Ser. No. 09/328,546, filed Jun. 9,
`1999, entitled “PN Code Selection for Synchronous
`CDMA”, by Leon Nieczyporowicz, Thomas Giallorenzi and
`Steven B. Perkins, which is incorporated by reference herein
`in its entirety.
`In this method, described below in greater detail in
`reference to FIGS. 11, 12, 13 and 14, the standard Walsh
`codes are reordered using a pseudo-random reordering pat
`tern. In other words, one starts with a code set w(n) having
`elements wi(n), and then permutes the columns of W(n) in
`a random-like fashion to obtain a new code Set matrix.
`Additional Steps of permuting rows and inverting rows can
`also be employed to provide a code matrix which has the
`additional, appealing properties of having a reasonable
`peak-to-average power ratio when transmitting correlated
`data on each of the CDMA channels.
`In accordance with the teachings of this invention the
`reordered code matrix is referred to as c' (n) to denote the
`k" reordering pattern of w(n), where it is assumed that the
`rows of w(n) were permuted and possibly inverted and the
`columns were permuted to obtain c'(n). The operations
`described do not change the fact that the rows of the matrix
`c' (n) are perfectly balanced. This implies that one of the
`rows will always be made up of all +1 values (or -1 values
`if it is inverted) since reordering the all +1 vector of w(n)
`does not change it. The all ones PN code of the set, c'(n),
`may be discarded, leaving n-1 PN codes which are perfectly
`balanced, mutually orthogonal, and which possess good
`spectral properties, if the k" reordering pattern is a good one.
`Finally, it can readily be shown that in non-degenerate
`cases, the Orthogonal matrix c'(n) is impossible to create
`using the cover code method of randomizing w(n), as
`described in, for example, the above-noted U.S. Pat. No.
`5,751,761.
`An additional benefit of the code generation method
`disclosed in the above-referenced U.S. patent application
`
`ONE-E-WAY 2007
`Apple v. One-E-Way
`IPR2021-00283
`
`017
`
`

`

`7
`Ser. No. 09/328,546, filed Jun. 9, 1999, entitled “PN Code
`Selection for Synchronous CDMA', by Leon
`Nieczyporowicz, Thomas Giallorenzi and Steven B.
`Perkins, is that one can find, if n is large, many distinct
`reordering patterns for use in adjacent cells. For example, in
`an exemplary fixed wireleSS local loop telephone System a
`total of nineteen c' (n) sets can be employed, with n=128,
`So k=1,2,..., 19. Each of the 19 Sets is Selected because
`of good spectral properties, and also because the shifted and
`non-shifted cross-correlation properties are good between
`any pair of codes in different sets, that is, c' (128) and
`c'D.(128) for all ki, where k=1, 2, . . . , 19, and X.y=1,
`2, . . . , 127, and c'es(128) is assumed to be the all +1
`vector of length 128 for all k. Having 19 distinct code sets
`which appear random relative to each other, but which are
`perfectly orthogonal within any one Set, permits one to
`employ a 19-cell code reuse pattern. This 19-cell code reuse
`pattern insures that no two cells are using the Same code Set,
`within two cells of one another, in a cellular grid. In a
`Sectorized deployment one may employ a 19-Sector code
`reuse pattern, or Some other reuse pattern with a Subset of the
`19 sets if desired.
`In contradistinction, in U.S. Pat. No. 5,751,761, the code
`reuse property is obtained by Synchronizing adjacent base
`Stations, and giving every base Station a different phase of
`the cover code. This method not only has the disadvantage
`of unbalanced PN codes, but it also requires that the base
`stations all employ GPS receivers to obtain a common clock
`reference to Synchronize the shifts of the long cover code.
`In contrast, the codes obtained in accordance with the
`teachings of the above-referenced U.S. patent application
`Ser. No. 09/328,546, filed Jun. 9, 1999, entitled “PN Code
`Selection for Synchronous CDMA, by Leon
`Nieczyporowicz, Thomas Giallorenzi and Steven B.
`Perkins, does not require base Station Synchronization to
`insure that adjacent cell interference appears random.
`A discussion is now made of enhancements to and exten
`Sions of the teachings found in the commonly assigned
`patent application U.S. patent application Ser. No. 09/328,
`546, filed Jun. 9, 1999, entitled “PN Code Selection for
`Synchronous CDMA', by Leon Nieczyporowicz, Thomas
`Giallorenzi and Steven B. Perkins, in particular a non
`recursive method for creating variable rate PN codes which
`are appropriate for use in Synchronous and quasi
`synchronous CDMA systems. This novel construction
`method will also be shown to have Several advantages over
`the prior art approaches discussed above.
`Disclosed below is a novel construction technique for
`creating PN codes for multirate Synchronous and quasi
`synchronous CDMA systems which have good spectral
`properties, are balanced, and that permit multicell operation.
`This method is shown to be a non-recursive extension of the
`codes disclosed in the above-referenced commonly assigned
`U.S. patent application Ser. No. 09/328,546, filed Jun. 9,
`1999. In fact, the method of reordering or permuting the
`columns of a Walsh matrix are extended by using a reordered
`matrix to modulate the reordered matrices described in the
`above-referenced commonly assigned U.S. Patent Applica
`tion.
`A notation system was defined above that will be used
`now to explain the novel method for PN code set generation
`in accordance with this invention. As a reminder, c' (n) was
`defined to be the kth code matrix created from w(n) by
`permuting the rows and columns according to the k" per
`mutation patterns, and by inverting Some of the rows of the
`resulting matrix. Also, c(n) was defined to be the j" +1
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,091,760
`
`8
`valued chip in the i' row of the code matrix, c'(n). Assume
`now that there are KuSeable permutation patterns that result
`in reasonable spectral properties and cross-correlation prop
`erties between members of different Sets, So k=1,2,..., K.
`Furthermore, assume that one desires to create Q=K/R
`distinct multirate code Se