`Second Edition
`
`Edward A. Lee
`University of California at Berkeley
`
`David G. Messerschmitt
`University of California at Berkeley
`
`sa
`StratosAudio Exhibit 2015
`Kluwer Academic Publishers Hyundaiv. StratosAudio
`Boston/Dordrecht/London
`* TPR2021-01267
`
`
`
`Page 1 of 9
`
`StratosAudio Exhibit 2015
`Hyundai v. StratosAudio
`IPR2021-01267
`Page 1 of 9
`
`
`
`
`
`Distributors for North America:
`Kluwer Academic Publishers
`101 Philip Drive
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`
`Distributors for all other countries:
`Kluwer Academic Publishers Group
`Distribution Centre
`Post Office Box 322
`3300 AH Dordrecht, THE NETHERLANDS
`
`2SSSS
`
`Library
`
`of Congress Cataloging-in-Publication Data
`
`Lee, Edward A., 1957-
`Digital communication / Edward A. Lee and David G. Messerschmitt.
`-- 2nd ed.
`p. cm.
`Includesbibliographical references and index.
`ISBN 0-7923-9391-0 (acid-free paper)
`1. Digital communications.
`I. Messerschmitt, David G.
`I. Title.
`TKS5103.7.LA4
`621.382--dc20
`
`1994
`
`93-26197
`CIP
`
`Copyright © 1994 by Kluwer Academic Publishers
`
`All rights reserved. Nopart of this publication may be reproduced,stored in a retrieval
`system ortransmitted in any form or by any means, mechanical, photo-copying, recording,
`or otherwise, without the prior written permission of the publisher, Kluwer Academic
`Publishers, 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061.
`
`Printed on acid-free paper.
`
`Printed in the United States of America
`
`Page 2 of 9
`
`Page 2 of 9
`
`
`
`
`
`770
`
`MULTIPLE ACCESS ALTERNATIVES
`
`The twoapplications differ substantially in the types of problems which must be
`overcome. For the digital subscriber loop, the transmission medium is fairly ideal,
`consisting of wire pairs with a wide bandwidth capability. The biggest complicationis
`the higher bit rate and the presence in some countries of bridged taps — open-
`circuited wire pairs bridged onto the main line. The voiceband data modem, while
`requiring a lower speedof transmission, encounters many more impairments.
`In addi-
`tion to the severe bandlimiting when carrier facilities are used, there are problems
`with noise, nonlinearities, and sometimes even frequency offset. Another difference
`is that the subscriber loop can use baseband transmission, while the voiceband dataset
`always uses passband transmission.
`
`18.2. MULTIPLE ACCESSBY TIME DIVISION
`
`By far the most common method of separating channels or users on a common
`digital communications medium is by ensuring that they transmit at different times.
`This is known as multiple access by time-division. This technique has manyvaria-
`tions, the most common of which are described in this section. In all these variations,
`some method is used to avoid collisions, or two or more users transmitting simultane-
`ously. Collision avoidancein link access is somewhateasier than in the other topolo-
`gies, and therefore wediscusslink access separately.
`
`18.2.1. Point-to-Point Link Access
`It is often desired to divide a high-speed bit stream over a point-to-point com-
`munications link into a set of lower-rate bit streams, each with a fixed and predefined
`bit rate. Wherethis is desired, it is appropriate to use a techniquecalled time-division
`multiplexing (TDM). The bit streams to be multiplexed are called tributary streams.
`Where these tributary bit-streams are provided directly to a user, that is they do not
`themselves consist of tributary streams, then they are called circuits or connections.
`Weinterleave thesetributary streams to obtain a higherrate bit stream. The purpose
`of the multiplex, shown functionally in Figure 18-4,
`is to take advantage of the
`economiesofscale of a high-speed transmission system.
`
`
`SINGLE
`
` LOW-SPEED
`HIGH-SPEED
`
`TIME-DIVISION
`TIME-DIVISION
`LINKS
`
`MULTIPLEX
`DEMULTIPLEX
`
`
`
`Figure 18-4. A time-division multiplex, which interleaves a numberof lower-speed tribu-
`taries ona single higher-speedlink.
`
`SEC. 18.2
`
`Example 18-3.
`A simple multi
`
`Eachtributary
`then these time
`bit stream occu
`
`In practice any
`slot can have a
`time-slot equal
`bits, which is k
`term for eight t
`tems commonly
`tions systems t
`world as bytes.
`tion, meaning «
`defined at
`the
`althoughthis is
`On the hig
`cisely one time
`18-3 one frame
`bit-stream origi
`tion, the bound:
`correspondence
`plexing requires
`tiplex typically
`
`Example 18-4.
`In a time-divis
`a single output
`framingbits. [
`
`The framingbit
`tiplex as distinc
`bits,
`through a
`enablesit to loc
`
`Since a mt
`the minimum b
`sum of the max
`framing and any
`
`Page 3 of 9
`
`Page 3 of 9
`
`
`
`rich mustbe
`fairly ideal,
`nplication is
`OS — open-
`odem, while
`nts.
`In addi-
`ire problems
`ar difference
`yand dataset
`
`n a common
`
`ferent times.
`many varia-
`ie variations,
`g simultane-
`»ther topolo-
`
`)-point com-
`d predefined
`‘ime-division
`ary streams.
`they do not
`connections.
`The purpose
`atage of the
`
`ved tribu-
`
`SEC. 18.2
`
`MULTIPLE ACCESS BYTIME DIVISION
`
`771
`
`Example 18-3.
`A simple multiplexing function for two tributary streams is shown below:
`INPUT TIME-SLOTS
`OUTPUT TIME-SLOTS
`
`
` MULTIPLEX
`
`Eachtributary stream is divided continuously into groupsof bits, known astime-slots, and
`then these time-slots are interleaved to form the output bit stream. Eachslot on the output
`bit stream occupieshalf the time of an inputslot since thebit rate is twice as great. O
`
`In practice any numberof tributary streams can be multiplexed, and a defined time-
`slot can have any numberof bits. However, two cases are particularly common: a
`time-slot equal to one bit, known as bit-interleaving, and a time-slot equal to eight
`bits, which is known as octet-interleaving.
`In multiplexing, an octet is a common
`term for eight bits. Organization around octets is common because voice PCM sys-
`tems commonly use eight bits per sample quantization, and because data communica-
`tions systems typically transfer eight-bit groupings of bits, known in the computer
`world as bytes.
`In both cases it is necessary to maintain octet integrity at the destina-
`tion, meaning that the bit stream is delimited into the same eight-bit boundaries
`defined at the origin. This octet integrity is assured by using octet-interleaving,
`althoughthis is not the only means.
`On the high-speed output bit stream, the collection of bits corresponding to pre-
`cisely one time-slot from each tributary stream is known as a frame.
`In Example
`18-3 one frame correspondsto time-slots a and b. At the demultiplex,all we haveis a
`bit-stream originating at the multiplex.
`In order to realize the demultiplexing func-
`tion, the boundaries of the time-slots must be known. Furthermore, to ensure that the
`correspondence between input and output tributary streams is maintained, demulti-
`plexing requires knowledge of the beginning of the frame. For this purpose, the mul-
`tiplex typically inserts additional bits into the frame knownasframing bits.
`
`Example 18-4.
`In a time-division multiplex, N tributary streams are multiplexed with M -bit time-slots into
`a single outputbit stream. The numberofbits in the output frame is N-M plus any added
`framing bits. O
`
`The framing bits follow a deterministic pattern which can be recognized at the demul-
`tiplex as distinct from the information bits. Once the demultiplex has located these
`bits,
`through a process known as framing recovery,
`it has a reference point that
`enablesit to locate the beginning of the frame.
`Since a multiplex cannot store an unbounded numberofbits, we must ensurethat
`the minimum bit rate of the output high-speed stream is greater than or equal to the
`sum of the maximum bitrates rates of the tributary streams plusthe rate required for
`framing and any other overheadbits.
`
`
`
`Page 4 of 9
`
`Page 4 of 9
`
`
`
`
`8 BITS (3.9 sec)
`
`772
`
`MULTIPLE ACCESS ALTERNATIVES
`
`SEC. 18.2
`
`ONE SUPERFRAME = 16 FRAMES(2 msec)
`
`ONE FRAME = 32 TIME SLOTS (125 Lsec)
`
`
`
`Table 18-1.
`are the sup:
`bit-interleav
`
`frame as defir
`frame superfri
`
`ONE TIME-SLOT=
`
`Figure 18-5. The framestructure for the CCITT G.732 30-channel PCM system.
`
`Example 18-5.
`The CCITT 30-channel system (recommendation G.732 [2]) is widely used in Europe and
`multiplexes 30 tributary streams, each at 64 kb/s, appropriate for a voiceband channel, into
`a single 2048 kb/s bit stream. Note that 30-64 = 1920,so that 128 kb/s is used for overhead
`functions such as framing. The organization of the frame is shown in Figure 18-5. Each
`frameis divided into 32 eight-bit time slots, 30 of them taken from thetributary streams,
`and the remaining two used for overhead. Thus, in this case as in the case of most lower-
`speed multiplexes, ociet-interleaving is used. The time for one frame corresponds to an
`octet on each tributary stream, or 1.25 |1sec. There is also defined a superframe or mul-
`tiframe of 16 frames, whichis used to transmit and frame on-off hook information for each
`of the 30 tributary voiceband channels. This on-off hook information, transmitted in frames
`0 and 16, is used to communicate between switching machines duringcall setup and take-
`down. Time-slot 0 always contains the octet "x0011011" and "x10xxxxx" in alternate
`frames, indicating the beginning of the frame, and time-slot 16 contains "0000x0xx" in
`frame 0 of the superframe indicating the beginning of the superframe ("x" indicates bits not
`assigned, which can be used for other purposes). Time-slot 16 in the remaining frames of
`the superframe contains the aforementioned signaling information. 0
`
`Example 18-6.
`The CCITT 24-channel system used in North America (CCITT G.733 [2]) has a frame con-
`sisting of 193 bits, including 24 eight-bit time-slots for the tributary 64 kb/s channels and
`one framing/superframing bit.
`In a superframe of 12 frames, the framing bit contains the
`patter "101010", the framing pattern, interleaved with the pattern "001110", the super-
`frame pattern. Thebit rate is 193-8 = 1544 kb/s. O
`
`Example 18-7.
`The M12 multiplex used in the North American network multiplexes four tributary bit
`streams at 1544 kb/s (often the G.733 signal of Example 18-6) into a into a 1176-bit super-
`frame shown in Table 18-1 using bit interleaving. Each line ofthe table represents one
`
`Digital Circu
`TDM mu
`bit-rate bit stre
`services such :
`tions through|
`phone networl
`connection.
`In
`the users at an
`function of a
`similar to that
`differs from t
`streams as inf
`plexed lower-:
`corresponding
`correspondstc
`the digital circ
`the switch is
`appearing ont
`
`Example 18-8.
`A simple exa
`
`Each ofthe i
`to each TDN
`output circui
`inputcircuits
`each tributar
`replaces a,
`|
`correspondir.
`
`Page 5 of 9
`
`Page 5 of 9
`
`
`
`SEC. 18.2
`
`MULTIPLE ACCESS BYTIME DIVISION
`
`773
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`34
`
`Table 18-1. Superframestructure of the M12 multiplex. The F bits are the framing bits, M@
`are the superframingbits, and C are stuffing control bits. 481 means 48 informationbits, 12
`bit-interleaved bits from each offour tributary streams.
`
`frame as defined by the FoF’, --- pattern, where Fg =0 and F, = 1. Similarly, the four-
`frame superframeis defined by the M o//,M,M,-°- superframe pattern. O
`
`Digital Circuit Switching
`TDM multiplexing provides a basic capability for the network to provide fixed
`bit-rate bit streams between users. These bit streams, which can be used to provide
`services such as a voiceband channel or video channel, are called circuits or connec-
`tions through the network. This terminology comes from the early days of the tele-
`Se —
`phone network, when voiceband channels were provided by a continuous metallic
`for eveakead
`connection. In order for the network to provide the preciseset of circuits requested by
`, 18-5. Each
`the users at any time, it is necessary to providea set of digital circuit switches. The
`tary streams,
`function of a digital circuit switch, and particularly the transmission interfaces, are
`most lower-
`similar to that of a TDM multiplex, so they will be described briefly here. The switch
`sponds to an
`differs from the multiplex in that it typically has the same number of output bit
`‘ame or mul-
`streams as inputs. Typically each stream is itself composed of time-division multi-
`tion for each
`plexed lower-speed streams, so that it has a defined framing structure with time-slots
`ted in frames
`corresponding to each tributary stream. Further, each of these time-slots typically
`up and take-
`in alternate correspondstoacircuit, or bit stream provided directly to users, since the purpose of
`
`000xOxx" in
`the digital circuit switch is to connect different users together. The specific purpose of
`sales’ EHS DOL
`the switch is to perform an arbitrary permutation of the input circuits (time-slots)
`ng frames of
`appearing on the output.
`
`a frame con-
`channels and
`contains the
`", the super-
`
`tributary bit
`76-bit super-
`presents one
`
`Example 18-8.
`A simple example is shown below:
`
`SWITCH
`
`
`INPUT TIME-SLOTS
`OUTPUT TIME-SLOTS
`
`Each of the input time-slots represents a circuit, where there are twocircuits corresponding
`to each TDM input and output in this example. Thus,in total there are four input and four
`output circuits, and the purpose of the switch is to perform an arbitrary permutation of the
`input circuits as they appearat the output. (If this switch were used for voiceband channels,
`eachtributary would be 64 kb/s).
`In the figure, input circuit a replaces d at the output, c
`replaces a, etc. To perform its function,
`the switch must be able to transfer the bits
`corresponding to one time-slot on one of the input TDM streams to a time-slot on a
`
`
`
`Page 6 of 9
`
`Page 6 of 9
`
`
`
`
`
`774
`
`MULTIPLE ACCESS ALTERNATIVES
`
`SEC. 18.2
`
`different output TDM stream (for example a andcin the figure), which is known as space-
`TDMAre
`division switching. Also, it must be able to transfer the bits from one time-slots ‘to another
`the random ac:
`(for example a andd in the figure), which is known as time-division Switching. O
`the control noc
`Ofcourse, most practical switches are muchlarger than this example.
`bits in TDM, t
`other nodes.
`°
`nodeis assigne
`frame structurt
`reference burs’
`assigned time-
`differences.
`fF
`receives the re
`ted with a cor.
`need for guar
`longer than the
`of traffic burs
`traffic burst is
`ence burst, thé
`allow the rece
`tralized contre
`to the nodes.
`and only as a
`reassignments
`The refe1
`timing sequen
`carrier recovel
`This is follow
`node to estab]
`wordis entire]
`the control ar,
`the nodes.
`It«
`control the ph
`of the guard ti
`
`Example 18-9.
`The No. 4 ESSis a large toll digital switching machine used in the North American net-
`work.
`It has 5120 input bit streams, each of which is the G.733 signal of Example 18-6
`containing 24 tributary voiceband channels, for a total of 122,880 tributary 64 kb/s bit
`streams(the total input and outputbit rate is 7.86 Gb/s, or actually double this because each
`channelis bi-directional). This switch is not capable of providing all possible permutations
`of input-output connections, but reasonable traffic demandscan be served with high proba-
`bility. O
`
`Circuit switching enables the network to provide a connection between twousers
`for the duration of their need. When thecircuit is no longer needed, the switchter-
`minates the connection and uses the associated time-slots on the transmission facility
`to provide another connection.
`In this fashion, we avoid provisioning transmission
`capacity for every possible connection in the network, but rather provide only
`sufficient capacity for those connections likely to be required at any give time.
`In
`Section 18.2.3 we will see an alternative model for providing a connection between
`two users, called packet switching.
`
`18.2.2. Time-Division Multiple Access
`Thus far this section has addressed the use oftime-division techniques for access
`control to a point-to-point link and to a full-duplex channel. Time-division using the
`circuit switching approach can also be applied to other multiple access topologies,
`such as the bus or the ring. The appropriate technique is highly dependent on the
`topology. For example, on the ring topology it is straightforward to define a scheme
`for time-division multiplexing.
`
`~
`
`Exercise 18-1.
`Describe a method for forming a frame and fixed time-slot structure on a ring topology, and
`the way in which a circuit could be formed. This approachis called a slotted ring. O
`
`On the other hand, TDMisdifficult to apply to the bus topology. The reason is sim-
`REFEREN(
`BURST
`ply that TDM requires a fixed frame knownto all nodes of the network, but in a bus,
`particularly a geographically large broadcast network such asasatellite network, the
`|
`propagation delays on the medium will typically be large relative to one bit-time.
`It is
`still common to apply TDM techniquesin this situation, but they must be modified to
`accountfor the significant propagation delays between users. This modification leads
`to an approach knownas time-division multiple access (TDMA). TDMAis applicable
`to any bus or broadcast topology, where there is a set of transmitters and a set of
`receivers, all of which hear each transmission.
`It has been extensively applied to
`satellite networksin particular [3,4].
`
`Figure 18-
`
`Page 7 of 9
`
`Page 7 of 9
`
`
`
`SEC. 18.2
`
`MULTIPLE ACCESS BY TIME DIVISION
`
`775
`
`TDMArequires a centralized control node, a feature that can be avoided using
`the random access techniques discussed in Section 18.2.4. The primary functions of
`the control node are to transmit a periodic reference burst, akin to the added framing
`bits in TDM,that defines a frame and forces a measure of synchronization ofall the
`other nodes. The frame so-defined is divided into time-slots, as in TDM, and each
`node is assigned a unique time-slot in which to transmit its information. Theresulting
`frame structureis illustrated in Figure 18-6, including one frame plus the succeeding
`reference burst. Each node, of which there are N, transmits a traffic burst withinits
`assigned time-slot. Thus far, the approachis similar to TDM,but there are significant
`differences. First, since there are significant delays between nodes, each node
`receives the reference burst with a different phase, and thusits traffic burst is transmit-
`ted with a correspondingly different phase within the time slot. There is therefore a
`need for guard times to take account of this uncertainty. Each time-slot is therefore
`longer than the period needed for the actual traffic burst, thereby avoiding the overlap
`of traffic bursts even in the face of these propagation delays. Second, since each
`traffic burst is transmitted independently with an uncertain phaserelativeto the refer-
`ence burst, there is the need for a preamble at the beginning of each traffic burst to
`allow the receiver to acquire timing and carrier phase. Finally, there must be a cen-
`tralized control mechanism to assign time-slots and communicate those assignments
`to the nodes. Time-slots can be pre-assigned, implying that changes are infrequent
`and only as a result of rearrangements, or demand-assigned, meaning that frequent
`reassignments are made to match the ebb and flow oftraffic demands.
`The reference burst is composed of three parts. A deterministic carrier andbit-
`timing sequence of approximately 30 to 300 symbols enables each nodeto do accurate
`carrier recovery and timing recovery for detection of the subsequent information bits.
`This is followed by a unique word with good autocorrelation properties, enabling each
`node to establish an accurate time-reference within the reference burst. The unique
`word is entirely analogous to the added framing bits ina TDM frame. Finally, there is
`the control and delay channel, which is a set of information bits used for control of
`the nodes.
`It enables the central control to assign time-slots, and can even be used to
`control the phase of a node’s traffic burst within a time-slot, thereby reducing the size
`of the guard time. The traffic burst preamble has a very similar structure. The control
`
`TRAFFIC
`BURSTS
`
`BURST
`
`BURST
`
`REFERENCE oo REFERENCE
`L
`L
`
`yWN aS Space-
`ots ‘to another
`oO
`
`\merican net-
`xample 18-6
`y 64 kb/s bit
`because each
`permutations
`h high proba-
`
`en two users
`3 switch ter-
`ision facility
`transmission
`rovide only
`ve time.
`In
`ion between
`
`3s for access
`on using the
`. topologies,
`ident on the
`ne a scheme
`
`copology, and
`ing. O
`
`ason is sim-
`out in a bus,
`ietwork,the
`it-time.
`It is
`modified to
`cation leads
`Ss applicable
`ind a set of
`7 applied to
`
`
`
`PREAMBLE
`
`INFORMATION
`
`Figure 18-6. The frame structure of a TDMA system.
`
`
`
`Page 8 of 9
`
`Page 8 of 9
`
`
`
`
`
`776
`
`MULTIPLE ACCESS ALTERNATIVES
`
`algorithms can getfairly complicated, and the reader is referred to [3] for a more
`detailed discussion.
`Early satellite systems utilized multiple access by FDM,to be described later,
`but the currenttrend is to use TDMA.
`
`Example 18-10.
`The INTELSAT system uses TDMAfor high-volumeintemational traffic. The basic bit
`rate is 120.832 Mb/s using four-phase PSK so that the baud rate is 60.416 MHz. Thebasic
`frame is 2 msin length, this being 16 times the frame period ofboth ofthe standard primary
`multiplex standards in the world (Example 18-5 and Example 18-6). Each time-slot is
`assigned to one of these primary bit streams. For a G.732 bit stream (Example 18-5), the
`traffic burst will contain 2 ms- 2.048 kb/s = 4096 information bits. At a bit rate of 120.832
`Mb/s, the information portionofthe traffic burst consumes 33.9 jisec. Forgetting the refer-
`ence burst, guard times, andtraffic burst preambles, the frame has room for 59 of these
`G.732bit streams. 0
`i
`
`18.2.3. Packetizing
`The circuit switching approach described in Section 18.1.1 allocated a fixed bit
`rate, corresponding to a reserved time-slot, to each of the multiple users of a given
`transmission system. This approach is simple to implement, but also cannot provide a
`time-varying bandwidth or a bandwidth on demand.
`It is also inflexible in that a fixed
`maximum numberof users can be accommodated on any given transmission system.
`There are many examplesof services that inherently require a time-varying bit rate,
`and in this case usingcircuit switching we mustprovide a circuit commensurate with
`the maximum bit
`rate requirements. Circuit switching is
`therefore somewhat
`inefficient for these services.
`
`Example 18-11.
`In conversational speech, normally only one direction of the conversationis active at any
`given time. During theresulting silence intervals, a smaller or even zero transmission capa-
`city is required. Circuit switching is therefore no better than 50% efficient. O
`
`Example 18-12.
`In video transmission, the image can be reconstructed with high accuracy from past images
`during periods of limited motion. Therefore, for a given fidelity higher bit rates are
`inherently required during periods of high motion than during periods of reduced motion.
`O
`
`Example 18-13.
`In interactive data transmission, transmission capacity from a user typing at a keyboard is
`sporadic, depending on when keys are pressed. Forthis case,circuit switching is grossly
`inefficient. O
`
`SEC. 18.2
`
`‘Example 18-14.
`An alarm syst
`infrequently tc
`O
`
`An additional p
`ferent bit rate r
`administrativels
`Packet sv
`lacking in circt
`vary in bit rate,
`In this subsecti
`multiplexing m
`subsection we ¢
`
`The basic
`a numberof st
`user are divide
`therefore analo
`(hundreds ort]
`fixed number o
`can be variable
`is then to inter!
`unlike in TDM
`users or the siz
`each user.
`
`Example 18-15.
`Enduserssitt
`of characters,
`puter. Thus, i
`this line of ch
`
`Example 18-16.
`Conversation:
`It would be n
`intervals can
`active speech,
`
`In TDM
`corresponding
`the receiver. V
`a somewhat mi
`to each users 1
`bit-rates is ins
`Wewill defer
`the incoming ©
`must be idle-ti
`
`Page 9 of 9
`
`Page 9 of 9
`
`