.~
`
`r
`,
`
`~'
`
`E
`
`I
`
`~ 'f'
`
`F 1
`t
`
`i
`
`t ~
`
`~
`
`-
`
`--
`
`—
`
`~~c ommunications ~~
`
`——-
`
`Pr i nci Ales
`
`P r a c t i c e
`
`;,
`~ ~
`~
`~ ;~
`~
`
`'
`
`'
`
`~~
`
`~
`
`~
`
`~..~
`
`PRENTICE HALL COMMUNICATIONS ENGIlVEERIQ~9G A~lD
`EMERGING TECHNOLOGIES S~RdES
`THEODORE S. RAPPAPORT, SER9ES EDITOR
`
`~i
`~
`. :.
`~
`~ : , .
`~ ,
`~
`I — I
`. ~
`~:
`
`►
`
`~J
`
`1 i
`►
`
`~o
`
`-
`
`~
`
`;
`
`~~~
`'~ .
`
`i '
`
`Petitioner's Exhibit 1015
`Page 001
`
`

`

`y
`
`~.M u 2«~1.
`
`A~~ 2 «~~ .
`
`Petitioner's Exhibit 1015
`Page 002
`
`

`

`,..
`
`1:
`
`~~
`
`:Y
`
`~t
`
`..'fir s~.
`
`is
`
`~~}~
`
`~
`
`M
`
`~;
`
`~ 4
`
`. -~ ~.~
`
`For book and bookstore information
`
`• • ~ a '. "'~~iF^v':~~ ri.•:•rmxv~ ~ rr ~. r x x
`r. xxr~x~n~x~~r. r~rwui.
`w.. fdr~i rr~r r~rr~~a~~~~xrrr~x~rr~.
`
`ht4p://v~vw.pren ha Il.coen
`
`I-'rentice Mall P~'I~
`Upper Saddle River, New .Tersey 0745
`
`Petitioner's Exhibit 1015
`Page 003
`
`

`

`Prentice Hal] Communications Engineering and Emerging Technologies Series
`
`Theodore S. Rappaport, Series Editor
`
`RAPPAPORT Wireless Communication: Principles &Practice
`
`1~AZA~II
`
`RF Microelectronics
`
`FORTHCOMING
`
`~.IBERTI ~ I~APPf~POR'f
`
`Smart Antennas for CDMA Wireless Systems: Applications
`to IS-95 and Wideband CDMA
`
`~'RAN'~°EZZ, K05BAgt, RAPPAPORT & SHANM~JGAN
`
`simulation of Modern Communication
`Systems with Wireless Applications
`
`CiAIZG ~ VVILI~ES Principles and Applications of GSM
`
`Petitioner's Exhibit 1015
`Page 004
`
`

`

`Editorial/production manager: Camille Trentacoste
`Cover design director: je~ry Votfa
`Cover designer: Anthony Gemtneltaro
`Manufacturing manager: Alexis R. Heydt
`Acquisitions editor: Karen Gettman
`Editorial assistant: Barbara Alfieri
`
`OO 1996 by Prentice Hall, PTR
`Prentice Hall, Inc.
`Upper Saddle River, NJ 07458
`
`The publishQr offers discounts on this book when ordered in bulk
`quantities. For more information, contact Corporate Sales Department,
`Prentice Hail PTR, One Lake Street, Upper Saddle River, NJ 07458.
`Phone: 8~-382-3419; FAX: 201- 236-7141.
`E-mail: corpsales@prenhall.com
`
`All rights reserved. No part of this book maybe reproduced,
`in any form or by any means,
`without permission in writing from the publisher.
`All product names mentioned herein are the trademarks of their' respective owners.
`Printed in the United States of l~merica
`20 19 18 17 16 75 14 13 12
`
`ISBN 0-13-375536-3
`Reprinted with corrections July, 1999
`Prentice-Hall International (UK) Limited, Lo~idon
`Prentice-Hall o.f Australia Pty. Limited, Syclf~ey
`Prentice-Hall of Canada, Inc., Toronto
`Prentice-Hall Hispanoamericana, S. A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Prentice-Hall Asia Pte. Ltd., Singapore
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`Petitioner's Exhibit 1015
`Page 005
`
`

`

`1
`
`Preface
`1 Introduction to Wireless Cvmm~~aica~ion 5yste
`1.1 Evolution of Mobile Radio Communications
`1.2 Mobile Radiotelephone in the U.S.
`1.3 Mobile Radio Systems Around the World
`1.4 Examples of Mobile Radio Systems
`1.4.1 Paging Systems
`1.4.2 Cordless Telephone Systems
`1.4.3 Cellular Telephone Systems
`1.4.4 Comparison of Common Mobile Radio Systems
`1.5 'rends ~ Cellular Radio and Personal Cominunicatsons
`1.6 Problems
`2 1'he Cell~l~ Concept — 5~stem Design Fundamentals
`2.1 Introduction
`2.2 Frequency Reuse
`2.3 Channel Assignment Strategies
`2.4 Handoff Strategies
`2.4.1 Prioritizing Handoffs
`2.4.2 Practical Handoff Considerations
`2.5 Interference and System Capacity
`2.5.1 Co-channel Interference and System Capacity
`2.5.2 Adjacent Channel Interference
`2.5.3 Power Control for Reducing Interference
`2.6 Trunking and Grade of Service
`
`v
`
`xi
`1
`1
`4
`6
`9
`11
`13
`14
`17
`20
`22
`25
`25
`26
`30
`31
`34
`34
`37
`37
`41
`43
`44
`
`Petitioner's Exhibit 1015
`Page 006
`
`

`

`Vo
`
`2.7 Improving Capacity in Cellular Systems
`2.7.1 Cell Splitting
`2.?.2 Sectoring
`2.7.3 A I~ovel 1Vlicrocell Zone Concept
`2.~ Summary
`2.9 Problems
`3 Mobile Radio Propagat~one I,ar~e~Scale Path Loss
`3.1 Introduction to Radio Wave Propagation
`3.2 Free'Space Propagation Model
`3.3 Relating Power to Electric Field
`3.4 The Three Basic Propagation Mechanisms
`3.5 Reflection
`3.5.1 Reflection from I3ielectrics
`3.5.2 Brewster Angle
`3.5.3 Reflection from Perfect Conductors
`3.6 Ground Reflection (2-ray) Model
`3.7 Diffraction
`3.7.1 Fresnel Zone Geometry
`3.7.2 Knife-edge Diffraction Model
`3.7.3 Multiple Knife-edge Diffraction
`3.8 S cattering
`3.8.1 Radar Cross Section Model
`3.9 Practical Link Budget Design using Path Loss I~todels
`3.9.1 Log-distance Path Loss Model
`3.9.2 Log-normal Shadowing
`3.9.3 Determination of Percentage of Coverage Area
`3.10 Outdoor Propagation Models
`3.10.1 Longley-Rice Model
`3.10.2 Durkin'sModel — A Case Study
`3.10.3 Okumura Model
`3.10.4 Hata Model
`3.10. S PCS Extension to Hata Model
`3.10.6 Walfisch and Bertoni Model
`3.10.7 Wideband PCS IO~icrocell Model
`3.11 Indoor Propagation Models
`3.11.1 Partition Losses (same floor)
`3.11.2 Partition Losses between Floors
`3.11.3 Log-distance Path Loss Model
`3.11.4 Ericsson Multiple Breakpoint Model
`3.11.5 Attenuation Factor Model
`3.12 Signal Penetration into Buildings
`3.13 Ray Tracing and Site Specific Modeling
`3.14 Problems
`
`Contents
`54
`54
`57
`61
`63
`63
`69
`69
`70
`74
`78
`78
`79
`84
`SS
`~5
`90
`91
`94
`99
`100
`101
`102
`102
`104
`106
`110
`110
`111
`116
`119
`120
`120
`121
`123
`123
`126
`126
`12~
`128
`131
`132
`133
`
`Petitioner's Exhibit 1015
`Page 007
`
`

`

`vii
`
`Contents
`4 Niob~le Radio Propa~ationo S al9a5cale Fad~n~ and ul~path 139
`4.1 Small-Scale Multipath Propagation
`139
`4.1.1 Factors Influencing Small-Scale Fading
`140
`4.1.2 Doppler Shift
`747
`4.2 Impulse Response Model of a Multipatb. Channel
`143
`4.2.1 Relationship Between bandwidth and Reeeived Power
`147
`4.3 Small-Scale Multipath Measurements
`153
`4.3.1 IDirect RF Pulse System
`154
`43.2 Spread Spectrum Sliding Co~elator Channel Sounding
`155
`4.3.3 Frequency Domain Chaianel Sounding
`1$g
`4.4 Parameters of Mobile MuItipath Channels
`159
`4.4.1 Time Dispersion Parameters
`160
`4.4.2 Coherence Bandwidth
`163
`4.4.3 Doppler Spread and Coherence Time
`165
`4.5 Types of Small-Scale Fading
`167
`4.5.1 Fading Effects Due to Multipath Time Delay Spread
`168
`4.5.2 Fading Effects Due to Doppler Spread
`170
`4.6 Rayleigh and Ricean Distributions
`172
`4.6.1 Rayleigh Fading Distribution
`1'72
`4.6.2 Ricean Fading Distribution
`174
`4.7 Statistical Models for Multipath Fading Channels
`176
`4.7.1 Clarke's Model for Flat Fading
`177
`4.7.2 Simulation of Clarke and Gans Fading 1b1odel
`181
`4.7.3 Level Crossing and Fading Statistics
`185
`4.7.4 Two-ray Rayleigh Fading Model
`18g
`4.7.5 Sa1eh and Valenzuela Indoor Statistical Model
`188
`4.7.6 SIRCIM and SMI~CIM Indoor and Outdoor Statistical Models
`189
`4.8 Problems
`192
`5 Modula~on Techniques for 1Vlobifle l~ad~o
`197
`5.1 Frequency Modulation vs: Amplitude IVlodulation
`198
`5.2 Amplitude Modulation
`199
`5.2.1 Single Sideband AM
`2p2
`5.2.2 Pilot Tone SSB
`203
`5.2.3 Demodulation of AM signals
`206
`5.3 Angle lO~Iodulation
`206
`5.3.1 Spectra and Bandwidth of FM Signals
`208
`5.3.2 FNI Modulation McY,hods
`2p9
`5.3.3 FM Detection Techniques
`211
`5.3.4 Tradeoff Between SNR ar►d bandwidth in an FM Signal
`219
`5.4 Digital Modulation — an Overview
`22p
`5.4.1 Factors That Influence the Choice of Digital lOilodulation
`2.21
`5.4.2 Bandwidth and Power Specri~al Density of Digital Signals
`224
`So4.3 Line Coding
`225
`5.5 Pulse Shaping Tecbniques
`22~
`5.5.1 I~yquist Criterion for ISI Cancellation
`227
`
`Petitioner's Exhibit 1015
`Page 008
`
`

`

`r~iio
`
`Contents
`
`5.5.2 Raised Cosine Rolloff Filter
`5.5.3 Gaussian Pulse-shaping Filter
`5.6 Geometric Representation of Modulation Signals
`5.7 Linear Modulation Techniques
`5.7.1 binary Phase Shift Keying (BPSK)
`5.7.2 Differential Phase Shift Keying (DPSK)
`5.7.3 Quadrature Phase Shift I~eying (QPSK)
`5.7.4 QPSK Transmission and Detection Techniques
`Se7.5 Offset QPSK
`5.7.6 ~/4 QPSK
`S.Z.7 ~/4 QPSK Tratas~russion Techniques
`5.7.E ~l4 QPSK Detection Techniques
`~
`5.8 Constant Envelope Modulation
`5.8.1 Binary Frequency Shift Keying
`.5.8.2 Minimum Shift Keying (MSK)
`5.x.3 Gaussian Minimum Shift Keying (GMSK)
`5.9 Combined Linear and Constant Envelope Modulation Techniques
`5.9.1. M-ary Phase Shift Keying (MPSK)
`5.9.2 M-ary Quadrature Amplitude Modulation (QAM)
`5.9.3 M-ary Frequency Shift Keying (MFSK)
`5.10 Spread Spectrum Modulation Techniques
`5.10.1 Pseudo-noise (i'I~ Sequences
`5.10.2 Direct Sequence Spread Spectrum (DS-SS)
`5.10.3 Frequency Hopped Spread Spectrum (FH-SS)
`5.10.4 Performance of Direct Sequence Spread Spectrum
`5.10.5 Performance of Frequency Hopping Spread Spectrum
`5.11 Modulation Perforniax~ce in Fading and Multipath Channels
`5.11.1 Perforniance of Digital Modulation in Slow, Flat Fading Channels
`5.11.2 Digital Modulation in Frequency Selective Mobile Channels
`5.11.3 Performance of ~/4 DQPSK in Fading and Interference
`5.12 Problems
`6 Equalization, Diversity, and Channel Coding
`6.1 Introduction
`6.2 Fundamentals of Equalization
`6.3 A Generic Adaptive Equalizer
`6.4 Equalizers in a Communications Receiver
`6.5 Survey of Equalization Techniques
`6.6 Linear Equalizers
`6.7 Nonlinear Equalization
`6.7.1 Decision Feedback Equalization (DFE)
`6.7.2 Maximum Likelihoad S equence Estimation (MLSE) Equalizer
`6.8 Algorithms for Adaptive Equalization
`6.8.1 Zero Forcing Algorithm
`6.8.2 Least Dean Square Algorithm
`6.8.3 Recursive Least Squares .~ilgorithm
`6.8.4 summary of Algorithms
`
`229
`233
`234
`238
`238
`242
`2A~3
`246
`247
`249
`249
`252
`254
`256
`259
`261
`267
`267
`270
`272
`274
`275
`276
`278
`280
`283
`284
`285
`289
`290
`294
`299
`299
`300
`303
`307
`30~
`310
`312
`313
`315
`316
`31 ~
`319
`321
`323
`
`Petitioner's Exhibit 1015
`Page 009
`
`

`

`Contents
`6.9 Fractionally Spaced Equalizers
`6.10 Diversity Techniques
`6.10.1 Derivation of Selection Diversity Improvement
`6.10.2 Derivation of Ma3cimal Ratio Combining Improvement
`6.10.3 Practical Space Diversity Considerations
`6.10.4 Polarization Diversity
`6.10.,5 Frequency Diversity
`6.10.6 Time Diversity
`6.11 RAKE Receiver
`6.12 Interleaving
`6.13 Fundamentals of Channel Coding
`6.14 Block Codes
`6.14.1 Examples of Block Codes
`6.14.2 Case Study of Reed~Solomon Codes
`6.15 Convolutional Codes
`6.15.1 Decoding of Convolutional Codes
`6.16 Coding Gain
`6.17 Trellis Coded Modulation
`6.18 Problems
`7 Speeel' Coding
`7.1 Introduction
`7.2 Characteristics of Speech Signals
`7.3 Quantization Techniques
`7.3.1 Uniform Quantization
`7.3.2 Nonuniform Quantization
`7.3.3 Adaptive Quantization
`7.3.4 Vector Quantization
`7.4 Adaptive Differential Pulse Code Modulation
`7.5 Frequency Domain Coding of Speech
`7.5.1 Sub-band Coding
`7.5.2 Adaptive Transform Coding
`7.6 Vocoders
`7.6.1 Channel Vocoders
`7.6.2 Formant Vocoders
`7.6.3 Cepstrum Vocaders
`7.6.4 Voice-Excited Vocoder
`7.7 Linear Predictive Coders
`7.7.1 LPC Vocoders
`7.7.2 Multi-pulse Excited LPC
`7.7.3 Code-Excited. LPC
`7.7.4 Residual Excited LPC
`7.8 Choosing Speech Codecs for Mobile Communications
`7.9 The GSM Codec
`7.10 The USDC Codec
`7.11 Performance Evaluation of Speech Coders
`7.12 Pa~oblems
`
`ix
`
`323
`325
`326
`328
`330
`332
`335
`335
`336
`338
`339
`340
`344
`346
`352
`354
`356
`356
`357
`361
`361
`363
`365
`365
`365
`368
`368
`369
`371
`3~2
`375
`376
`376
`377
`377
`378
`378
`378
`381
`382
`383
`384
`387
`389
`3~9
`392
`
`Petitioner's Exhibit 1015
`Page 010
`
`

`

`a
`
`X
`~ 10~ultipie Access Techniques for Wireless Comrrr~rei~.t~o~
`~.1 Int~oduct~on
`8.1.1 Introduction to 1Vlultiple Access
`8.2 Frequency Division Multiple access (FDMA)
`8.3 Tune Division Multiple Access (TDMA)
`~.4 Spread Spectrum 11~ultiple Access
`8.4.1 Frequency Hopped Multiple Access (FHN~A)
`8.4.2 Code Division Multiple Access (CDIVIA)
`8.4.3 Hybrid Spread Spectrum Techniques
`8.5 Space Division Iviu~tiple Access (SOMA)
`8.6 Packet Radio
`8.6.1 Packet Radio Protocols
`8.6.2 Carrier Sense Multiple Access (CSMA) Protocols
`8.6.3 Reservation Protocols
`8.6.4 Capture Effect in Packet Radio
`~.7 Capacity of Cellular Systems
`x.7.1 Capacity of Cellular COMA
`8.7.2 Capacity of CDIVIA with D/Iultlpl~ Cells
`8.7.3 Capacity of Space Dieision Multiple Access
`~.~ Problems
`9 wireless l~detvvork~ng
`9.1 Introduction to Wireless I~Tetworks
`9.2 Differences Between ~Ni~eless and Fixed Telephone Networks
`9.2.1 The Public Switched Telephone Network (PSTI~
`9.2.2 Lunitations in Wireless Networking
`9.2.3 Merging Wireless Networks and the PSTN
`9.3 Development of Wireless Networks
`9.3.1 First Generation Wireless Networks
`9.3.2 Second.Generation Wireless Networks
`9.3.3 Third Generation Wireless I~Tetworks
`9,4 Fixed Network Transmission Hierarchy
`9.5 Traffic Routing in Ve~ireless Networks
`9.5.1 Circuit Switching
`9.5.2 Packet twitching
`9.5.3 The X.25 Protocol
`9.6 Wireless Data. Services
`9.6.1 Cellular Digital Packet Data. (CDPD)
`9.6.2 Advanced Radio Data. Information Systems (ARDIS)
`9.6.3 RAM Mobile Data. (1ZIVV~)
`9.7 Common Ci~annel Signaling (CC5)
`9.7.1 The Distributed Central Switching Office for CCS
`9.~ Ir►tegrated Services I~i~itai Network (ISDl~d)
`9.x.1 broadband ISDIV and ATNI
`9.9 Signalinb System I~To. 7 (SS7)
`9.9.1 Network Services Part (IVSP) of SS7
`
`Contents
`395
`395
`396
`397
`400
`404
`404
`405
`407
`409
`410
`411
`415
`416
`416
`417
`422
`425
`431
`437
`439
`439
`441
`441
`443
`444
`445
`445
`448
`449
`449
`450
`452
`452
`454.
`455
`455
`457
`457
`45~
`459
`461
`463
`463
`465
`
`Petitioner's Exhibit 1015
`Page 011
`
`

`

`Contents
`9.9.2 The S S7 User Part
`9.9.3 Signaling Traffic in SS7
`9,9.4 SS7 Services
`9.9.5 Performance of SS7
`9.10 An example of SS7 —Global Cellular Network Interoperability
`9.11 Personal Communication Services/Networks (1'CS/PCI~
`9.11.1 Packet vs. Circuit switching for PCN
`9.11.2 Cellular Packet-Switched Architecture
`9.12 Protocols for Network Access
`9.12.1 Packet Reservation Multiple Access (PRMA)
`9.13 Network Databases
`9.13.1 Distributed Database for Mobility Management
`9..14 Universal Mobile Telecommunication System (UMTS)
`9.15 Summary
`10 wireless Systems and. Standards
`10.1 AMPS and ETAC~
`10.1.1 AMPS and ETACS System Overview
`10.1.2 Call Handling in AMPS and ETACS
`10.1.3 AMPS and ETACS Air Interface
`10.1.4 N-AMPS
`10.2 United States Digital Cellular (IS-54)
`10.2.1 USDC Radio Interface
`10.2.2 United States Digital Cellular Derivatives (IS-94 and IS-136)
`10.3 Global System for Mobile (GSM)
`10.3.1 GSM Services and Features
`10.3.2 GSM System Architecture
`10.3.3 GSM Radio Subsystem
`10.3.4 GSM Channel Types
`10.3.5 Example of a GSM Call
`10.3.6 Frame Structure for GSM
`10.3.7 Signal Processing in GSM
`10.4 CDMA Digital Cellular Standard (I~-95)
`10.4.1 Frequency and Channel Specifications
`10.4.2 Forward CDMA Channel
`10.4.3 Reverse CDMA Channel
`10.4.4 IS-95 with 14.4 kbps Speech Coder [AI~S95]
`10.5 CT2 Standard ~'or Cordless Telephones
`10.5.1 CT2 Services and Features
`10.5.2 The C'I2. standard
`10.6 Digital European Cordless Telephone (DECT)
`10.6.1 Features and Characteristics
`10.6.2 DECT Architecture
`10.6.3 DECT Functional Concept
`10.6.4 DECT Radio Link
`
`X~
`
`466
`467
`468
`469
`469
`472
`472
`473
`477
`47~
`479
`479
`480
`481
`4~3
`483
`484
`485
`487
`491
`491
`493
`500
`500
`501
`502
`505
`507
`512
`513
`515
`519
`520
`521
`527
`533
`533
`533
`534
`535
`535
`536
`537
`538
`
`Petitioner's Exhibit 1015
`Page 012
`
`

`

`xii
`
`10.7 PACE —Personal Access Communication Systems
`10.7.1 PALS System Architecture
`10.7.2 PACE Radio Interface
`10.8 Pacific Digital Cellular (PDC)
`10.9 Personal Handyphone System (PSIS)
`10.10 U.S. PCS and ISM Bands
`10,11 i7.S, Wireless Cable Television
`10.18 Summary of Standards Throughout tl~e World
`10.13 Problems
`
`Contents
`539
`540
`541
`543
`544
`544
`547
`548
`551
`
`D ~1`•I~;
`555
`A 7'r~anking Theory
`556
`A.1 Erlang B
`556
`A.1.1 Derivation of Erlang B
`561
`A.2 Erlang C
`561
`A.2.1 Derivation of Erlang C
`565
`~ Eloise Figure Calculations for Link budgets
`569.
`C Gaussian Appro~mations for Spread Spectr~uun CD1V~
`577
`C.1 The Gaussian Approximation
`582.
`C.2 The Improved Gaussian Appro~mation (IGA)
`C.3 A Simplified Expression for the Improved Gaussian Approxunation (SEIGA) 585
`593
`I) Q, erff erfc F~et~ons
`593
`D.1 The Q-Function
`595
`D.2 The erf and erfc functions
`599
`E 1Vlathexr►atieal Tables
`607
`~ Abbre~ia~ions and. Acronyms
`617
`G References
`635
`Index
`
`Petitioner's Exhibit 1015
`Page 013
`
`

`

`340
`
`Ch. 6 •Equalization, Diversity, and Channel Coding
`
`= log2(1 + No Bb I
`J
`
`(6.83)
`
`where C/B denotes bandwidth efficiency.
`The basic purpose of error detection and error correction techniques is to
`introduce redundancies in the data to improve wireless link performance. The
`introduction of redundant bits increases the raw data rate used in the link,
`hence increases the bandwidth requirement for a fixed source data rate. This
`reduces the bandwidth efficiency of the link in high ~NR conditions, but provides
`excellent BER performance at low SNR values.
`It is well known that the use of orthogonal signaling allows the probability
`of error to become arbitrarily small by expanding the signal set, i.e., by making
`the number of waveforms 1~1 ~ oo , provided that the SNR per bit exceeds the
`Shannon limit of SNRb _> —1.6 dB [Vit79]. In the limit, Shannon's result indicates
`that extremely wideband signals could be used to achieve error free communica-
`tions, as long a~ sufficient SNR exists. Error control coding waveforms, on the
`other hand, have bandwidth ex~aansion factory that grow only linearly with the
`code block length. Error correction coding thus offers advantages in bandwidth
`limited applications, and also provides link protection in power limited applica-
`tions.
`A channel coder operates on digital message (or source) data by encoding
`the source information into a code sequence for transmission through the chan-
`nel. There are two basic types of error correction and detection codes: block codes
`and convolutional codes.
`
`6e14 ~lo~k Codes
`Block codes are forward error correction (FEC) codes that enable a limited
`number of errors to be detected and corrected without retransmission. Block
`codes can be used to improve the performance of a communications system when
`other means of improvement (such as increasing transmitter power or using a
`more sophisticated demodulator) are impractical.
`In block codes, parity bits are added to blocks of message bits to make code-
`words or code blocks. In a block encoder, k information bits are encoded into n
`code bits. A total of n — k redundant bits are added to the k information bits for
`the purpose of detecting and correcting errors [Lin83]. The block code is referred
`to as an (n, k) code, and the rate of the code is defined as R~ = k/n and is
`equal to the gate of information divided by the raw channel rate.
`The ability of a block code to correct errors is a function of the code distance.
`Many families of codes exist that provide varying degrees of error protection
`[Cou93], [Hay94], [Lin83], [Sk193], and [Vit79].
`
`Petitioner's Exhibit 1015
`Page 014
`
`

`

`D
`
`Block Codes
`
`341
`
`Exax~aple F.5
`Interleavers and block codes are typically combined for wireless speech trans-
`mission. Consider an interleaves with m rows and n-bit words. Assume each
`word of the interleaves is actually made up of k source bits and (n-k) bits from
`a block code. The resulting interleaves/coder combination will break up a burst
`of channel errors of length l = mb into m bursts of length b.
`Thus an (n, k) code that can handle burst errors of length b < (n —k) /2. can
`be combined with an interleaves of degree m to create an interleaved (mn,mk)
`block code that can handle bursts of length mb. As long as mb or fewer bits are
`corrupted during the transmission of the coded speech signal from the inter-
`leaver, the received data will be error free.
`Besides the code rate, other important parameters are the distance and the
`weight of a code. These are defined below.
`Distance of a Code —The distance of a codeword is the number of ele-
`ments in which two codewords Ci and C~ differ
`N
`d (Ci, C~) _ ~ Ci l O+ C~ l (modulo —q)
`a =1
`where d is the distance of the codeword and q is the number of possible values
`of Ci and C~ . If the code used is binary, the distance is known as the ~Iamming
`distance. The minimum distance dmin is the smallest distance for the given set
`and is given as
`
`(6.84)
`
`(6.85)
`dmin =Min {d (Cl, C~) }
`Weag~at of a Code —The weight of a codeword is given by the number of
`nonzero elements in the codeword. For a binary code, the weight is basically the
`number of 1's in the codeword and is given as
`
`u' (Ci) _
`
`~L a
`l=1
`
`(6.86)
`
`P~opertie~ of Mock Codes
`Linearity —Suppose Ci and C~ are .two code words in an (n, k) block
`code. Let al and a2 be any two elements selected from the alphabet. Then the
`code is said to be linear if and only if a1C1 + a2CZ is also a code word. A linear
`code must contain the all-zero code word. Consequently, aconstant-weight code
`is nonlinear.
`~ystemcatic — A systematic code is one in which the parity bits are
`appended to the end of the information bits. For an (n, k) code, the first k bits
`are identical to the information bits, and the remaining n — k bits of each code
`word are linear combinations of the k information bits.
`
`Petitioner's Exhibit 1015
`Page 015
`
`

`

`342
`
`Ch. 6 •Equalization, Diversity, and Channel Coding
`~'~clac —Cyclic codes are a subset of the class of linear codes which satisfy
`the following cyclic shift property: If C = [Cn _ I ~ Cn _ y .....~ co] is a code word of a
`cyclic code, then [ cn _ 2, Cn _ 3, .... ~, c o, cn -1 ] ,obtained by a cyclic shift of the ele-
`ments of C, is also a code word. That is, all cyclic shifts of C are code words. As a
`consequence of the cyclic property, the codes possess a considerable amount of
`structure which can be exploited in the encoding and decoding operation.
`Encoding and decoding techniques make use of the mathematical con-
`structs know as finite fcelds. Finite fields are algebraic systems which contain a
`finite set of elements. Addition, subtraction, multiplication, and division of finite
`field elements is accomplished without leaving the set (i.e., the sum/product of
`two field elements is a field element). Addition and multiplication must satisfy
`the commutative, associative, and distributive laws, A formal .definition of a
`finite field is given below:
`Let F be a finite set of elements on which two binary operations —addition
`and multiplication are defined. The set 1~' together with the two binary oper-
`ations is a field if the following conditions are satisfied:
`F is a commutative group under addition. The identity element with respect
`to addition is called the zero element and is denoted by 0.
`The yet of nonzero elements in F is a commutative group under znultiplica-
`tion. "I"he identity element with respect to multiplication is called the unit
`element and is denoted by 1.
`• Multiplication is distributive over addition; that is, for any three elements a,
`b, and c in F.
`
`The additive inverse of a field element a, denoted by -a, is the field element
`which produces the sum 0 when added to a [a + (-a) = 0 ]. The multiplicative
`inverse of a ,denoted by a i , is the field element which produces the product 1
`when multiplied by a [a • a 1 = 1 ].
`Four basic properties of fields can be derived from the definition of a field.
`They are as follows:
`Property I: a• 0= 0= 0• a
`Property II: For nonzero field elements a and b , a • b ~ 0
`Property III: a• b= 0 and a~ 0 imply b= 0
`Property IV: -(a • b) _ (-a) • b = a • (-b)
`For any prime number p ,there .exists a finite field which contains p ele-
`ments. This prime field is denoted as GF (p) because finite fields are also called
`Galois fields, in honor of their discoverer [Lin83]. It is also possible to extend the
`prime field G~' (p) to a field of p"` elements which is called an extension fceld of
`• GF (p) and is denoted by GI' (p"~) , where m is a positive integer. Codes with
`symbols from the binary field G~(2) or its extension field GF(2"~) are most
`commonly used in digital data transmission and storage systems, since informa-
`tion in these systems i~ always encoded in binary form in practice.
`
`Petitioner's Exhibit 1015
`Page 016
`
`

`

`Block Codes
`343
`In binary arithmetic, modulo-2 addition and multiplication are used. This
`arithmetic is actually equivalent *o ordinary arithmetic except that 2 is consid-
`ered equal to 0 { 1 + 1 = 2 = 0) .Note that since 1+1 = 0, 1= -1, and hence for the
`arithmetic used to generate error control codes, addition is equivalent to subtrac-
`tion.
`
`Reed-Solomon codes make use of nonbinary field GF (2m) .These fields
`have more .than 2 elements and are extensions., of the binary field
`GF (2) _ { 0, 1 } .The additional elements in the extension field GF (2m) can-
`not be 0 or 1 since all of the elements are unique, so a new symbol a is used to
`represent the other elements in the field. Each nonzero element can be repre-
`sented by a power of a .
`"for the extension field must be defined so
`The multiplication operation "
`that the. remaining elements of the field can be represented as sequence of pow-
`ers of a . The multiplication operation can be used to produce the infcnite set of
`elements F shown below
`
`F = { 0, 1, a, a2, ....., a~, ..... } _ { 0, a°, a I, a2, ....., a~, ..... }
`To obtain the finite set of elements of GF (2"Z) from F, a condition mint be
`imposed on F so that it may contain only 2m elements and is a closed set under
`multiplication (i.e., multiplication, of two field elements is performed without;
`leaving the set). The condition which closes the set of field elements under multi-
`plication is known as the irreducible polynomial, and it typically takes the fol-
`lowing form [Rhe89]:
`
`(6.87) ~
`
`a ~2m 1 ~ + 1 = 0 or equivalently a ~2m-1 ~ = 1 = a~
`(6.8~)
`Using the irreducible polynomial, any element which has a power greater
`than 2m — 2 can be reduced to an element with a power less than 2m — 2 as fol-
`lows:
`
`aka"`+n> _ a~2m-i~ an+i = an+i
`(6.89)
`The sequence of elements F thus becomes the following sequence F* , whose
`nonzero terms are closed under multiplication:
`
`m rrz
`,a
`F* _ {O, 1, a,aZ, .....,a
`o i l z"`-z
`
`o
`
`m
`,a ,.....}
`a
`
`(6.90)
`
`Take the first 2"Z terms of ~'* and you have the elements of the finite field
`GF (2m) in their power representation
`
`j tsF~Zm~ = {O, 1~ CGS 0(2~ .....~
`
`a2nc_21
`~ f O~ C(~~ OLD CC2~ .....~ CG2m-Z }
`I t
`
`~G.✓1.~
`
`Petitioner's Exhibit 1015
`Page 017
`
`

`

`r
`
`344
`
`Ch. 6 •Equalization, Diversity, and Channel Coding
`It can be shown that each of the 2"` elements of the finite field can be repre-
`sented as a distinct polynomial of degree m - 1 or less (the element 0 is repre-
`sented by the zero polynomial, a polynomial with no nonzero terms) [Rhe89].
`Each of the nonzero elements of GF(2"Z) , can be denoted as a polynomial ai(x) ,
`where at least one of the m coefficients is nonzero.
`m-1
`(6.92)
`a
`i
`a = ai(x) = al a + al, lx + a~, Zx + ..... + ai, m -1x
`Addition of two elements of the finite field is then defined as the modulo-2
`addition of each of the polynomial coefficients of like powers, as shown below
`m-1
`(6.93)
`at +a~ _ (a~,o+a~,o)+(ai,l+a~,1)x+.....+(al,m_z+a~ m-l~x
`Thus GF(2"`) may be constructed, and using equations .(6.92) and (6.93) the
`polynomial representation for the 2"~ elements of the field may be obtained.
`
`6.14.1 Examples of Block Codes
`Haanming Codes
`Hamming codes were among the first of the nontrivial error correction
`codes [Ham50]. These codes and their variations have been used for error control
`in digital communication systems. There are -both binary and nonbinary Ham-
`ming codes. A binary Hamming code has the property that
`(6.94)
`(f2,IZ) _ (2"2 -1, 2"'-1-m)
`where k is the number of information bits used to form a n bit codeword, and m
`is any positive integer. The number of parity symbols are n - k = m.
`Hadamard Codes.
`Hadamard codes are obtained by selecting as codewords the rows of a Had-
`amard matrix. A Hadamard matrix A is a N x N matrix of is and Os such that
`each row differs from any other row in exactly 1V/2 locations. One row contains
`all zeros with the remainder containing N/2 zeros and N/2 ones. The mini-
`mum distance for these codes is N/2.
`For N =; 2 ,the Hadamard matrix A is
`
`A = 0 0
`O 1
`In addition to the special case considered above when N = 2"Z (m being a
`positive integer), Hadamarc~ codes of other block lengths are possible, but the
`codes are not linear.
`Golay Codes
`Golay codes are linear binary (23,12) codes with a minimum distance of 7
`and a error correction capability of 3 bits [Go149]. This is a special, one of a kind
`code in that this is the only nontrivial example of a perfect code. (Hamming codes
`
`(6.95)
`
`Petitioner's Exhibit 1015
`Page 018
`
`

`

`i
`
`345
`Block Codes
`and some repetition codes are also perfect.) Every codeword lies within distance
`3 of any codeword, thus making maximum likelihood decoding possible.
`Cyclic Codes
`Cyclic codes are a subset of the class of linear codes which satisfy the cyclic
`property as discussed before. As a result of this property, these codes possess a
`considerable amount of structure which can be exploited.
`A cyclic code can be generated by using a generator polynomial g (p) of
`degree (n - k). The generator polynomial of an (n, k) cyclic code is a factor of
`pn + 1 and has the general form
`g'~P) = pn yi+g'n-k-IPA-k-1 -i- ..... -f-g'Ip -f- Z
`A message polynomial x(p) can also be defined as
`
`6.96)
`
`x~p) = xk-iPk-1+ ..... +xlp+xa X6.97)
`where (xk _ 1, ...., xo) represents the k information bits. The resultant codeword
`c (p) can be written as
`
`(6.98)
`
`~(p) = x(P)g(P)
`where c(p) is a polynomial of degree less than n.
`Encoding for a cyclic code is usually performed by a linear feedback shift
`register based on either the generator or parity polynomial.
`BCH Codes
`BCH cyclic codes are among the most important block codes since they exist
`for a wide range of rates, achieve significant coding gains, and can be imple-
`mented even at high speeds [Bos60]. The block length of the codes is n = 2"` -1
`for m >_ 3 , and the number of errors that they can correct is bounded by
`t < (2"Z - 1)/2 . The binary BCH codes can be generalized to create classes of
`nonbinary codes which use m bits per code symbol. The most important and
`common class of nonbinary BCH codes is the family of codes known as Reed-
`Solomon codes. The (63,47) Reed-Solomon code in U.S. Cellular Digital Packet
`Data (CDPD) uses m = 6 bits per code symbol.
`Reed-Solomon Codes
`Reed-Solomon (RS) are nonbinary codes which are capable of correcting
`errors which appear in bursts and are commonly used in. concatenated coding
`systems [Ree60]. The block length of these codes is n = 2"` - 1. These can be
`extended to 2"` or 2"` + l . The number of parity symbols that must be used to
`correct e errors is n - k = 2e . The minimum distance dmin = 2e + 1 . RS codes
`achieve the largest possible d1zLn of any linear code.
`
`Petitioner's Exhibit 1015
`Page 019
`
`

`

`346
`
`Ch. 6 ~ Equalization, Diversity, and Channel Coding
`
`Por the purpose of explanation, the field choice will be GF (64) ,since this
`is the same field used in CDPD systems. In this case, m = 6 , so each of the 64
`field elements is represented by a 6 bit symbol.
`A finite field entity p (~ is introduced in order to map the 64 distinct 6-bit
`symbols to the elements of the field: An irreducible polynomial p (~ of degree
`m is said to be primitive if the smallest integer n for which p (~ divides X'Z + 1
`is n = 2"` —1 . This primitive polynomial p (~ is typical of the form
`
`(6.99)
`p (h~ = 1 +X +X"'
`In the case of the Reed-Solomon code used for CDPD, this is indeed the
`form of p(X). Regardless, these polynomials have been tabulated fog a wide range
`of field sizes, sop (X} should be considered a known quantity. CDPD's primitive
`polynomial is
`
`pcDPD (~ = 1 +X+X6 (6.100)
`In order to map symbols to field elements, set the primitive polynomial
`p (a) = 0 . This yields the following result, which closes the set of field elements:
`
`cc6 +a+ 1 = 0
`(6.101)
`Table 6.2 shows the proper mapping of 6 bit symbols to field elements.
`These elerrients were generated by starting with the element 1 (a°) and multi-
`plying by a to obtain the next field element. Any element which contains an as
`term will yield an a6 term in the next element, but a6 is not in GF(64) .The
`primitive polynomial rule is used to convert a6 to a + 1 . Also note that
`a62 • a = a63 = a° = 1. This simple result is critical when implementing finite
`field multiplication in software. Multiplication can be accomplished quickly and
`efficiently by using modulo 2'y` —1 addition of -the powers of the elemental oper-
`ands. For the 63, 47 Reed-Solomon code used in CDPD systems, multiplication.of
`two field elements corresponds to adding the powers of the two operands modulo-
`63 to arrive at the power of the product.
`Addition in GF (2"`) corresponds to modulo-2 adding the coefficients of the
`polynomial representation of the elements. Since the coefficients are either 1's or
`0's (because the field is an extension of the binary field GF (2) ), this can simply
`be implemented with the bit-wise exclusive-OR of the 6 bit symbol representa-
`tion of the elemental operands. Some examples of finite- field`addition in GF (64)
`are' shown below.
`
`a27 + as = (001110) 2XOR (100000) 2 = (101110) 2 =ass (6.102.a)
`
`a 19 + a62 = (011110) ZXOl~ (100001) 2 = (111111) 2 = a58 (6.