CHIP INTERLEAVING FOR CDMA CELLULAR
`SYSTEMS
`
`Leycheoh Lim
`
`A thesis submitted in conformity mith the requirements
`for the degree of Master of .4pplied Science.
`Graduate Depart ment of Electrical and Computer Engineering. in the
`Cniversity of Toronto. Canada
`
`@ Copyright by Leycheoh Lim 1997
`
`IPR2018-01474
`Apple Inc. EX1019 Page 1
`
`

`

`iJ(il of Canada
`
`National Library
`
`Acquisitions and
`Bibliographie Services
`395 Wellington Street
`Ottawa ON K1A ON4
`Canada
`
`Bibliothèque nationale
`du Canada
`Acquisitions et
`sewices bibliographiques
`395. me Wellington
`OttawaON K1AON4
`Cartada
`
`The author has granted a non-
`exclusive licence allowing the
`National Library of Canada to
`reproduce, loan, distribute or sell
`copies of this thesis in microform,
`paper or electronic formats.
`
`The author retains ownership of the
`copyright in ths thesis. Neither the
`thesis nor substantial extracts fkom it
`may be printed or othenirise
`reproduced without the author's
`permission.
`
`L'auteur a accordé une licence non
`exclusive permettant à la
`Bibliothèque nationale du Canada de
`reproduire, prêter, distribuer CU
`vendre des copies de cette thèse sous
`la forme de microfiche/film, de
`reproduction sur papier ou sur format
`électronique.
`L'auteur conserve la propriété du
`droit d'auteur qui protège cette thèse.
`Ni la thèse ni des extraits substantiels
`de celle-ci ne doivent être imprimés
`ou autrement reproduits sans son
`autorisation.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 2
`
`

`

`Chip Interleaving For CDMA Cellular Systems
`by
`Leycheoh Lim
`Master of AppLied Science
`Department of Electrical and Cornputer Engineering
`University of Toronto
`May, 1997
`
`Abstract
`We consider the forward link of a direct sequence CDMA cellular system oper-
`ating in an environment with time va,rying multi-path fading and introduce a chip
`interleaving scheme. We study the probability of symbol error for various cases of the
`interleaving parameters for the cases of a one-path and a two-path Rayleigh fading
`channel. The chip interleaver output is combined with equd gain combining before
`the detector. Simulation results for the symbol error probability for each chip inter-
`leaving configuration and different interleaving degrees are ob tained. Addi tiondy,
`the effects of hard and soft decision decoding on the performance of the system are
`considered. The chip interleaving simulation results are compared to the syrnbol
`block interleaving used in the 1s-95 CDMA cellular system standard. The results
`show that chip interleaving improves the performance of the CDM.4 link over that
`which is based solely on symbol interleaving.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 3
`
`

`

`Acknowledgment
`1 would like to thank my supervisor, Professor E. Sousa, for giving me ail the
`support, and guidance throughout this reseârch and thesis. In addition, 1 would Like
`to thank my friends especially Qingxin Chen, donathon Sauo Wilson Wong, Qingymg
`Huang, and Richard Lee for their advice and discussions. Most of all 1 would like to
`thank my family for their support and encouragement.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 4
`
`

`

`Contents
`
`Abstract
`Acknowledgements
`
`List of Tables
`
`List of Figures
`
`...
`
`111
`
`v
`
`vi
`
`1 Introduction
`1
`1.1 CDMA Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3
`1.1.1 Important Issues and Features in CDMA . . . . . . . .
`4
`IS-95 Standard . . . . . . . . . . . . . . . . . . . . . . . . .
`5
`1.1.2
`1.2 Wireless Channel Characteristics . . . . . . . . . . . . . . . . . .
`6
`Signal Fading Mitigation Techniques . . . . . . . . . . .
`1.2.1
`S
`. . . . . . . . . . . .
`1.2.2 Burst Error Mitigation Techniques
`S
`1.3 Chip Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`9
`1.3.1 Research Objectives . . . . . . . . . . . . . . . . . . . . . . 10
`1.3.2 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . 10
`2 Direct Sequence Spread Spectrum Signals in Multipath Channels
`12
`2.1 Direct Sequence Spread Spectrum Signal . . . . . . . . . . . .
`12
`2.2 Fading Multipath Channel . . . . . . . . . . . . . . . . . . . . . . 15
`2.3 ConvolutionalCoding.. . . . . . . . . . . . . . . . . . . . . . . . 17
`2.3.1 Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 17
`2.3.2 Viterbi Decoding Algorithm . . . . . . . . . . . . . . . . . 18
`. . 20
`2.4 Coding and Ideal Symbol Interieaving for DS/SS Signal
`
`IPR2018-01474
`Apple Inc. EX1019 Page 5
`
`

`

`2.5
`
`Ideal Chip Interleaving Performance . . . . . . . . . . . . . . . 22
`3 Interleaving Scheme
`27
`. . . . . . . . . . . . . . . . . 27
`3.1 Time Diversity and Interleaving
`3.2 Symbol Convolutional Interleaving . . . . . . . . . . . . . . . . 25
`3.2.1 Conventional Symbol Convolutional Interleaver . . . . 25
`3.2.2 Embedded Symbol Convolutional Interleaver . . . . . . 30
`3.3 Symbol Block Interleaving . . . . . . . . . . . . . . . . . . . . . 31
`3.4 Chip Block Interleaving . . . . . . . . . . . . . . . . . . . . . . . 34
`4 Chip Interleaving Scheme Performance
`43
`4.1 System Description . . . . . . . . . . . . . . . . . . . . . . . . . . 43
`4.2 Chip Interleaving and Hard Decision Decoding
`. . . . . . . 44
`4.3 Chip Interleaving and Soft Decision Decoding . . . . . . . . . 52
`4.4 Chip Interleaving and the Rake Receiver . . . . . . . . . . . . . 54
`5 Conclusion
`65
`. . . . . .
`Simulation Results Summary and Research Insights
`65
`1
`. . . . . . . . . . . . . . . . . . . . . 66
`5.2 Topics for Future Research
`A IS-95 Symbol Block Interleaving Algorithm
`B Chip Deinterleaving
`
`73
`
`IPR2018-01474
`Apple Inc. EX1019 Page 6
`
`

`

`List of Tables
`
`2.1 Metric table for an 8 levels quantization . . . . . . . . . . . . . . . . . 20
`Integer Metric table for an 8 levels quantkation . . . . . . . . . . . . . 20
`2.2
`3.1 Five different chip interleaving configurations . . . . . . . . . . . . . . 37
`3.2 Six different interleaving degrees for chip interleaving scheme . . . . . 39
`4.1 Five different chip interleaving configurations . . . . . . . . . . . . . . 45
`4.2 Five interleaving degree for chip interleaving . . . . . . . . . . . . . . . 45
`4.3 Five different chip interleaving configurations and their chip interleav-
`ing degree for the maximum separation chip interleaving scheme . . . . 45
`
`IPR2018-01474
`Apple Inc. EX1019 Page 7
`
`

`

`List of Figures
`
`2
`
`1.1 Three basic multiple access schemes . . . . . . . . . . . . . . . . . . .
`Inphase linear shift register for the IS-95 quadrature spreading PX
`1.2
`sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3
`1.3 Spread spectrum communication . . . . . . . . . . . . . . . . . . . . .
`4
`1.4 Direct-sequence spreading of information bits . . . . . . . . . . . . . . 4
`1.5 The forward link of CDMA cellular standardo IS-95 . . . . . . . . . . . 6
`1.6 Chip interleaving at the transrnitter . . . . . . . . . . . . . . . . . . . 10
`2.1 Quadriphase direct-sequence receiver . . . . . . . . . . . . . . . . . . . 14
`2.2 A (2.1. 8) convolutional encoder . . . . . . . . . . . . . . . . . . . . . . 18
`2.3 Simulation results for ideal symbol block interleaving. 1s-95 symbol
`block interleaving. and no interleaving for hard decision decoding under
`one-path Rayleigh fading channel . Maximum Doppler frequency is 60
`Hz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
`2.4 Simulation results of IS-95 symbol block interleaving for hard and soft
`decision deroding . Maximum Doppler frequency is 60 Hz . . . . . . . . 23
`2.5 Simulation results for ideal chip interleaving and ideal symbol block
`interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
`3.1 Conventional s p b o l convolut ional interleaver . . . . . . . . . . . . . . 29
`3.2 Conventional symbol convolutional deinterleaver . . . . . . . . . . . . 30
`3.3 -4 conventional symbol convolutional interleaving ( m=3, D=1 symbol) . 31
`3.4 Embedded symbol convolutional interleaver . . . . . . . . . . . . . . . 31
`3.5 Embedded symbol convolutional deinterleaver . . . . . . . . . . . . . . 32
`3 -6 S ymbol block interleaving scheme . . . . . . . . . . . . . . . . . . . . 32
`
`vii
`
`IPR2018-01474
`Apple Inc. EX1019 Page 8
`
`

`

`36
`
`. . . . . . . . . . . . . . . . . . 33
`A 10 by 6 symbol block interleaving.
`. . . . 34
`CDMA cellular standord 1s-95 forward link block interleaving
`Information bit and symbol DS spreading . . . . . . . . . . . . . . . . 35
`A maximum sepaation distributed 4 16-chip groups/symbol transmit-
`tedsignal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`A maximum sepaation interleaving degree of the 4 16-chip groups/symbol
`chip interleaver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`A maximum separation 4 16-chip groups/symbol chip interleaver. . .
`Four maximum separation chip interleaving configurations shown in
`four speech frames. . . . . . . . . . . . . - . . . . -
`- . . . . . . . . .
`Five maximum separation chip interleavers . . . . - . . . . . . . - . .
`Four 16-chip group interleaving degrees s h o w in time domain. . . . .
`Four 8-chip group chip interleaving degrees shown in time domain. . .
`Three Cchip group chip interleaving degrees show in time domain. .
`Two 2-chip group chip interleaving degrees shown in time domain. . .
`Two 1-chip group chip interleaving degrees shown in time domain. . .
`Five different chip interleaving configurations for maximum separat ion.
`and IS-95 symbol block interleaving. (Hard decision decoding) . . . .
`Four different chip interleaving degrees for 4 16-chip groups/symbol
`configuration. (Hard decision decoding) . - . . . . . . -
`- . . . . . .
`Four different chip interleaving degrees for S 8-chip groups/symbol con-
`figuration. (Hard decision decoding) . . . . - . . - . - . - . . . . - . .
`Three different chip interleaving degrees for 16 Cchip groups/symbol
`configuration. (IIard decision decoding) . . . . . . . . . . . . .
`. . .
`Two different chip interleaving degrees for 32 2-chip groups/s-pbol
`configuration. (Hard decision decoding) . . . . . . . . . . . .
`. . . .
`Two different chip interleaving degrees for 64 1-chip groups/symbol
`. . . . . .
`configuration. (Hard decision decoding) . . . . .
`. . . .
`Four chip interleaving configurations for interleaving degree D. (Hord
`decision decoding) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`IPR2018-01474
`Apple Inc. EX1019 Page 9
`
`

`

`4.8 Five chip interleaving configurations for int erleaving degree E. (Hard
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .
`decision decoding)
`4.9 Five different chip interleaving configurations for maximum separation
`. . . . .
`and 1s-95 symbol block interleaving. (Soft decision decoding)
`4.10 Comparison between hard decision decoding and soft decision decoding
`for 4 16-chip groups/symbol configuration wit h maximum separation.
`4.11 Compaxison between hard decision decoding and soft decision decoding
`for 8 8-chip groups/symbol configuration with maximum separation. .
`4.12 Comparison between hard decision decoding and soft decision decoding
`for 16 Pchip groups/symbol configuration wi t h maximum separation.
`4.13 Comparison between hard decision decoding and soft decision decoding
`for 32 2-chip groups/symbol configuration with maximum separation.
`4.14 Comparison between hard decision decoding and soft decision decoding
`for 64 1-chip groups/symbol configuration wit h maximum separat ion.
`4.15 Tw-path model: Five different chip interleaving configurations for
`maximum separation. (Hard decision decoding) . . . . . . . . . . . .
`4.16 Even distributed separation for 4 16-chip groups/symbol chip inter-
`leaving configuration. (Hard decision decoding ) . . . . . . . . . . . . .
`4.17 Even distributed separation for 8 8-chip groups/symbol chip interleav-
`ing configuration.(Hard decision decoding) . . . . . . . . . . . . . . .
`4.18 Even distributed separation for 16 Pchip groups/s-ymbol chip inter-
`leaving configuration. (Hard decision decoding) . . . . . . . . . . . . .
`4.19 Even distributed separation for 32 2-chip groups /symbol chip inter-
`leaving configuration.(Haxd decision decoding ) . . . . . . . . . . . . .
`4.20 Even distributed separation for 64 1-chip groups/symbol chip inter-
`leaving co&wation.(Hard decision decoding) . . . . . . . . . . . . .
`5.1 One-path model: Comparison between the best hard decision decoding
`chip interleaving and the soft decision decoding symbol block interleav-
`. . . . . . . . . . . . . . . . .
`ing. Maximum Doppler shift of 60 Hz.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 10
`
`

`

`5.2 Cornparison between the 16 Cchip groups/symbol chip interleaving,
`symbol block interleaving, and the ideal symbol block interleaving.
`. . . . . 69
`Maximum Doppler shift of 60 Hz. (Hard decision decoding)
`CDMA Cellular Standard IS-95 Forward Link Block Interleaver . . . 70
`1
`B. 1 -4 maximum separation for 4 16-chip group interleaving in the time scale. 73
`B.2 A maximum separation for 4 16-chip groups chip interleaver. . . . . . 74
`B.3 A chip deinterleaving for 4 16-chip groups at the receiver. . . . . . . . 74
`B.4 Long code generation for the 4 16-chip groups maximum separation
`configuration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`74
`
`IPR2018-01474
`Apple Inc. EX1019 Page 11
`
`

`

`Chapter 1
`Introduction
`
`Wireless communications is one of the fastest growing industries. The subscrip tions
`to wireless communications services are doubling every 20 months. and the number
`of subscribers has reached 50 million in less than 20 years. This growth rate is due to
`the development of inexpensive. rapidly deployable wireless s ystems and mobile uni ts.
`The viability of wireless communications to provide telephony services is a result of
`the development of the cellular concept and the associated concept of frequency re-
`use. The cellular concept constitutes the partitionhg of a large area into a number of
`cells and the allocation of a portion of the total radio spectrum to each of the cells.
`This frequency allocation results in a pattern of repetition of frequency allocation
`according to a basic set of cells known as the frequency re-use cluster size. Within
`each c d . the transmission link from the base station (BS) to the mobile station (11s )
`is called the fonvard link, whereas the transmission link from the LIS to the BS is
`called the reverse link. The BS performs functions such as c d setup. radio ckannel
`assignment. message scheduling on broadcast channels. and power control. The base
`stations from different cells are comected to a switch know as the mobile telephone
`snitching office (MTSO). The MTSO is the interface between the BS and the wire-
`.A
`full duplex channel is composed of the forward and reverse links
`line network.
`which are separated by a large frequency so as to allow simultaneous transmission.
`The North America cellular system channel structure contains a 45 MHz bandwidth
`separation between these two radio Links (11.
`The three basic multiple access schemes are Frequency Division Multiple Access
`
`IPR2018-01474
`Apple Inc. EX1019 Page 12
`
`

`

`(FDMA), Time Division Multiple Access (TDMA), and Code Division Multiple Ac-
`cess (CDMA). They are illustrated in Fig. 1.1. With FDMA the total channel band-
`
`Figure 1.1: Three basic multiple access schemes.
`width is divided into a number of smaller fiequency bands. Each of these frequency
`bands is called a radio channel. Each channel is assigned to a specific user. which
`uses it throughout the c d . With TDMA each user transmits a wideband signal oc-
`cupying the whole system spectrum for a portion of the time [2]. CDMA utilizes
`the total channel bandwidth for signal transmission. Users are different iated by t heir
`unique code assignment [3]. Several cellular communication standards based on t hese
`multiple access schemes have been established. The analog system standard which
`is knonm as Adwced Mobile Phone Service (AMPS) is based on FDM-4. ivhich is
`also hown as the first generation wireless system. Current digital cellular standards.
`IS-54 and GSM use a hybrid of FDMA and TDMA. On the other hand. the cellular
`standard IS-95. was adopted in 1993 [4]. is based on CDMA [SI.
`Follorving the development of digi ta1 cellular standards in 1981. we have wi tnessed
`a gradud switch from the analog to the digital systems. One of the major system
`performance degradations is that due to multipath propagation. The multipath prop-
`agation causes the signal to undergo constnict ive and destructive interference which
`results in a fading process. Much research has been conducted in devising techniques
`to mitigate the fading. These techniques include the use of equalizers. diversity
`schemes. and in particular the rake receiver. In order to combat the fading prob-
`lem in the CDMA systems. we introduce new techniques based on chip interleaving.
`These techniques are relatively simple CO irnplement and result in an improvement
`over the standard technique of symbol interleaving.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 13
`
`

`

`1.1 CDMA Systems
`The two common spread spectrum techniques are direct sequence spreading (DS)
`[6][7][8] and frequency hopping (FH). In frequency hopping, the carrier frequency of
`the transrnitted signal is pseud~tandomly changed according to a pseuderandom
`m-ary sequence. On the other hand. in a DS spread spectrum system. the phase of
`the carrier is varied according to a binary pseudo-noise (PX) sequence or P N code. In
`this thesis we consider a DS-SS communication system. The PX codes are generated
`by linear feedback shift registers. In the IS-95 system the forward channe1 utilizes a
`QPSK spreading scherne. Two DS signals are generated. one modulates an in-phase
`carrier and the other modulates a quadrature carrier. Fig. 1.2 shows the inphase
`quadrature PN spreading code used in IS-95.
`
`Figure 1.2: Inphase linear shift register for the 1s-95 quadrature spreading PX se-
`quence.
`
`In CDHA cellular communications. the different base stations utilize pilot signals
`which are generated as difTerent phase shifts of a fked PS code of period equal to
`215. These are referred to as different offsets of the pilot signal. The pilot signal
`is unmodulated and is transmitted at a higher energy level than the traffic carrying
`signals. Orthogonal PX codes are used in the fonvard link in order to reduce multiple
`access interference. On the other hand. the reverse link uses non-orthogonal codes.
`because it is difficult to align the transmissions of all the signals in the reverse l i d .
`[9]. This thesis concentrates on the forward link of a cellular system. Fig. 1.3 shows
`the block diagram of a typical direct sequence spread spectrum system.
`In the DS scheme the data signal is multiplied by a PX sequence as shown in
`Fig. 1.3. Each symbol in the PN sequence is c d e d a chip. Fig. 1.4 shows an example
`
`IPR2018-01474
`Apple Inc. EX1019 Page 14
`
`

`

`Figure 1.3: Spread spectriim communication.
`
`of a spread data bit by a PN code. The receiver multiplies the received signal with ao
`
`Figure 1.4: Direct-sequence spreading of information bits.
`
`exact copy of the PX sequence with the appropriate phase (in the sequence period)
`and the result is low-pass filtered. Some of the important issues and features in the
`CDMA systems are presented in the next subsection.
`
`1.1.1 Important Issues and Features in CDMA
`Some of the important features in a CDMA cellular system are the pilot signal, the
`use of soft hand off, power control, and the Rake receiver. The pilot signal provides
`many functions to the CDMA systems. Besides using the pilot signal to identi6
`different base stations as mentioned in the last section, it is used to generate a local
`PN code and carrier phase for coherent demodulation. The use of a pilot signal also
`facilitates the implement ation of soft hand-off. The mobile searches over the different
`codes phases of the pilot signal, instructs the base station to transmit the signal over
`
`IPR2018-01474
`Apple Inc. EX1019 Page 15
`
`

`

`the base stations that give the strongest signal. This type of hand off is sometimes
`referred to as "make before break" hand off.
`The user capacity in the CDMA cellular systems is lirnited by the multiple access
`interference. and power control is employed to reduce this interference. The goal is
`to transmit the smdest possible power level so as to achieve an acceptable signal
`to noise ratio at the receiver. Reverse link power control atternpts to achieve equal
`power signals which are received from different MS at the BS [IO]. The BS sends a
`command to the MS so that the MS can constantly adjust its transmit power level.
`This is known as the closed loop power control. Forward link power control is based
`on the received frame error rate at the MS and the BS adjusts its transmit power to
`the MS so that the MS receives a signal with suaicient SNR [Il].
`The Rake receiver also plays an important role in CDMA cellular communica-
`tions [12]. When the received signal contains multipath components which have a
`relative delay of at least one chip, the received signal components are resolvable at
`the receiver. The Rake receiver collects signal energy from the resolvable multipat h
`components. The signal energy can be combined by three different schemes; maximal
`ratio combining, equal gain combining, and selective combining. The Rake receiver
`is used both in the forward and reverse links of the 1s-95 CDMA cellular systems.
`
`1.1.2 IS-95 Standard
`IS-95 is an interim digital cellular standard which adopts the CDMA technology.
`There are two major areas in this standard: the reverse link and the forward iink.
`The forward link is an important area for system performance improvement since
`the mobile receiver has a limitation on hardware implementation: we want a smdl
`and less power-consuming mobile receiver. Our research focuses on improving the
`system performance for the forward link of CDMA cellular systems. We use 1s-95 as
`a guideline for our research and simulation parameters. This standard specifies the
`modulation technique, long PN code generation, orthogonal code, forward link power
`control, interleaving scheme, and forward error correc ting code (FEC ). Fig. 1.5 shows
`the 1s-95 forward link transmission block diagram.
`The orthogonal code used in the forward link is based on the 64 x 64 Hadamard
`matrices. The fomard link has up to seven paging channels, one synchronization
`
`IPR2018-01474
`Apple Inc. EX1019 Page 16
`
`

`

`Figure 1.5: The forward link of CDMA cellular standard, IS-95.
`
`channel, one pilot chasnel, and 54 trafic channels. The dl zero sequence in the
`Hadamard matrix is used for the pilot channel, and the other 63 orthogonal codes
`are used for the other channels. Only the receiver which has the right orthogonal
`code can retrieve its information from the received signal [13]. The forward link uses
`a rate 112 convolutional channel encoding. One bit of information is encoded into
`two symbols. Each speech frame contains 384 symbols which are read into a block
`interleaving table. The symbols are interleaved for transmission. This has the effect
`of making the system robust against rapid fading.
`.4t the receiver, the received signal is despread by the same PN code as that
`used at the transmitter. After coherent demodulation and detection, the decision is
`read into the deinterleaver so that the received information sequence is rearranged
`to its original speech sequence. The ability of the deinterleaving process to break
`up any length of burst error depends on its interleaving degree. The bit error rate
`perîormance from the chip interleaving scheme is compared to the above symbol block
`interleaving. A wireless channel has time varying chuacteristic. The type of signal
`distortion caused by the time varying effect is called fading. Before ive discuss the
`objective of chip interleaving, section 1.2 discusses the characteristic of fading channel
`and burst errors.
`
`1.2 Wireless Channel Characteristics
`When a signal is transmitted in a wireless environment, the transrnitted signal is
`subjected to reflection and refraction. Because of this multi-path environment, the
`received signal's ampli tude const itutes a s u m of multiple signal components, which
`s u m constructively or destmctively at the receiver. This amplitude variation in the
`received signal is known as signal fading. In addition, the signal is also subject to the
`
`IPR2018-01474
`Apple Inc. EX1019 Page 17
`
`

`

`Doppler shift effect due to the movement of the receiver (141. When the receiver is
`moving directly towards the transmitter, the received signal will be shifted higher in
`frequency, whereas if the receiver is moving directly away from the transmitter, the
`received signal will be shifted lower in frequency. We can express the Doppler shift
`of the i t h received signal as in ( 1.1 ) ,
`
`where w, is the maximum Doppler shift and 0; is the mival angle of it h signal path
`to the direction of motion of the receiver. The maximum Doppler shift is related to
`the signal carrier frequency f, and the velocity of the receiver v. as in (1.2).
`
`where c is the speed of light. The Doppler shift effect produces the spaced-time
`correlation function for the received signal, from which we can find the coherence
`time of the channel. The coherence time is essentially a measure of the rate of
`channel variation in time. For example a fast changing channel has a small coherence
`time compared to the data duration. When there are a large number of received
`signal paths, the received signal can be modeled as a complex-value Gaussian random
`process. Therefore the characteristic of the received signal's envelope can be modeled
`as the Rayleigh distribution or Ricean distribution, depending on whet her there is
`a strong specular path [15]. In other cases, the received signal's envelope can be
`modeled as Nagakami-m distribution. We mode1 our simulation channel as a Rayleigh
`distributed channel.
`The above fading process is known as fast fading. Besides fast fading, the received
`signal is also subject to a shadowing effect. This is also known as slow fading. Slow
`fading is caused by the signal blockage between the receiver and trammitter. The
`most common experience is when a user is under a bridge. One way of solving this
`problem is to transmit a larger power signal to the receiver. Besides shadowing, path
`loss also causes signal distortion. Path loss is proportional to the distance between the
`receiver and transmitter. As the distance between the receiver and the transmitter
`increases, the transmit ted signal strengt h becomes weaker.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 18
`
`

`

`Because of the signal fading effect, a wireless channel is characterized as a bursty
`error channel. The errors in a bursty error channel tend to occur in clusters. A
`common error control strategy is using random error correcting codes along with
`interleavers (161. Diversity schemes are usually employed to mitigate fading. The
`following two sections discuss these dis tortion mitigation techniques.
`
`1.2.1 Signal Fading Mit igat ion Techniques
`Diversity schemes can effectively combat fading. There are three basic diversity
`schemes: antema diversity, time diversity, and frequency diversity. Their use is ap-
`propriately selected depending on the application. Antenna diversity is achieved by
`receiving signals from multiple antennas at the receiver. These antennas are sepa-
`rated a few wavelengths apart so that the received signals are uncorrelated at different
`antennas. Usually the separation is required to be at least tens of wavelengths apart
`to achieve an independent fading path at the receiver antenna. Therefore a n t e ~ a
`diversity is not feasible for the forward li&
`communication. since the mobile receiver
`is too smail to provide enough spacing for the antennas.
`With time diversity the same information is transmitted in digerent time dots
`such that the probability that all the signals encounter a simultaneous deep fade
`is very srnall. When the separation of the time slot is bigger than the coherence
`time of the channel the errors in the different dots are uncorrelated. Wi th frequency
`diversity the same information is transmitted in different frequency bands [17]. If the
`separation between the carriers is greater than the coherence BW of the channel. then
`we obtain uncorrelated errors in the bits transmitted on the two carriers. Both of
`t hese diversity schemes, t ime and frequency, require additional bandwidt h for signal
`transmission.
`
`1.2.2 Burst Error Mitigation Techniques
`A burst-error channel can be modeled with two states; a "good state" and a "bad
`state" [18]. When the channel is in the good state, the probability that transmission
`errors occur is very s m d . When the channel is in the good state it is less likely to shift
`to the bad state; however once the channel is in a bad state, it is more likely to shift
`
`IPR2018-01474
`Apple Inc. EX1019 Page 19
`
`

`

`from the bad state to the good state. The channel shifts to the bad state whenever
`the transmission medium encounters bad changes, for example a "deep faden. Once
`the channel is in the bad state, transmission errors are more likely to happen. This
`type of error is fiequently caused by fading efEect in the wireless channel. This occurs
`when the duration of fade is longer than a few symbol times.
`The burst of errors is specified by the length of the error cluster and the guard
`space between these clusters. The guard space is many times longer than the burst
`length. In order to break up the burst of errors at the receiver, an interleaver is in-
`corporated with the random error correcting code at the transmit ter. The interleaver
`can transform a memory chonnel into a mernoryless channel. Other burst error cor-
`recting techniques include the burst-error-correc ting code [18]. However interleaving
`is preferable to the burst-error-correcting code because an interleaver is simple and
`interleaver is suitable for s m d and power limited
`easy to impiement. Moreover an
`receivers.
`The purpose of interleaving is
`to spread the errors throughout the speech frame.
`The interleaving process scrarnbles the transmit data bit sequence at the transmit ter
`before modulation. After demodulat ion at the receiver. the deint erleaver arranges
`the received bit sequence back to the original sequence before decoding. Therefore
`any length of burst errors from the channel is broken up before the decoding process.
`Interleaving can combine with the FEC to mitigate the effect of burst error. There are
`two types of interleaving schemes: block interleaving and convolutional interleaving
`[19]. These different interleaving schemes axe discussed in Chapter 3. Chip interleav-
`ing is a combination of block interleaving and time diversity The main purpose is to
`prevent a whole data syrnbol to undergo deep fade.
`
`1.3 Chip Interleaving
`As mentioned previously, in a spread spectrum communication7 each data symbol is
`spread by the PN sequence. Therefore a data symbol contains a nurnber of chips.
`Chip interleaving can be introduced in the CDMA cellular systems to improve the
`bit error rate (BER) performance under a fast fading channel. In next two sections,
`we discuss the research objectives and the oventiew of the thesis.
`
`IPR2018-01474
`Apple Inc. EX1019 Page 20
`
`

`

`1.3.1 Research Objectives
`The main purpose of introducing chip interleaving is to prevent the whole data s ~ b o l
`from encoutering a deep fade. Chip interleaving can be thought as a combination
`of interleaving and time diversity. It is uinterleaving" because the successive symbols
`from the speech frame are transmitted far apart from each other through the channel.
`It is a &tirne diversity" because the same symbol is divided into many smdler parts
`and transmitted at different time dots through the channel. If 113 of the data symbol
`parts encounters a deep fade we can recover the signal from the other 213 parts of
`the data symbol.
`Chip interleaving does not cause any additional bandwidth expansion in CDMA
`systems. At the same time we can achieve additional 2-3 dB SNR improvement at
`10-3 BER. Because of the low complexity in implementation. chip interleaving is
`preferable to using any high complexity powelful code to gain a ferv dBs in SNR. The
`simulation results have shown t hat chip interleaving improves the SNR significantly
`over the syrnbol interleaving performance when