`-' ;
`. -.. -
`
`I"' -
`ll L~~>
`I,\ ~-
`'}
`d \1
`1
`I:'! .
`..... ______ . ________
`
`'/
`,,
`
`/1
`
`···
`
`_,
`
`:
`
`\
`
`Ji ..
`( ·I
`1,i11
`
`·1
`
`,i I
`
`1\ (1 1
`
`J
`
`· · -. · -··--.. Telecommuni~at-ions ._
`--- . :: _-. : ___ - - ··~.:: ::· ·--Eng· in eer'S · · · ---. _
`·----.1-e·1·e··-ren·• ... c_ ·e 8--o----·ok ··-····-·
`
`···-.
`
`---
`
`-
`
`•
`
`-
`
`_ _ _ . . . . ........... .. __ _ :
`
`·---. · · · · -
`
`.
`
`··
`
`·
`
`,.... -· ····· ··· - ··· - ·· ·-·-····\ ~--
`
`.
`
`-- ..... -
`
`· . ... _
`
`·_
`
`..
`
`--
`
`"-. ,
`
`\
`
`'
`
`·,
`
`/
`
`._
`
`\
`
`· ,
`
`·,
`
`••
`
`,
`
`:
`
`' · - ·-
`
`--
`
`-.. ...
`
`' '·
`
`'
`
`--
`
`I
`
`11
`
`I
`
`I
`I
`I
`
`!
`
`·.
`
`-1-l Ii /
`'i~ I
`1i. ·l
`1H I ·:,
`:tli 1
`1 !: 1, ..
`I t I
`'1< I
`I : I ' , .
`'
`
`'
`
`·
`
`'
`
`,I
`
`· ·" ' .. ,
`
`.
`
`'··
`
`'
`
`·\ .~ '\.: ~\
`
`'
`
`•
`
`·····.,. ~. -
`.. · ···-.......
`'· " ,·..,=-;,_:...
`'· .
`'
`~-
`·
`' ,.
`' ' ... ,~
`' ·
`J
`
`'
`
`,
`
`.....
`
`'•,
`
`'"·
`
`.....
`,.
`·-
`
`,,
`
`~
`
`.
`
`•
`
`. ·~
`
`·-,
`
`..
`
`'•
`-........
`
`' ·
`·, ..
`· .. "
`'\..
`'
`
`-·:· •... ~~ .... ~ :..·":: .... · ..... ~-, , .. - , .. ~...
`.. ... .. -. ...
`tf,'1-..........................
`. ........
`' ... - ..
`~-.....
`!lit-,,
`:.-.:~
`. -\ .
`',,..,
`·.·~
`..............
`.. .. ._~
`{ ..
`\
`·. ,J _.....
`... ,
`. ....... ;;........
`--
`.
`' '
`1119••····-· ..
`~ ~,:
`...
`--
`•; "' i::t \, ', ,. .....
`,. ,
`'. ,
`~ ~ ' ' .
`~ ' ··
`·,\ · . ·•...
`·~ ".~
`..
`....
`\,; .._
`°=
`-l'
`·.
`·:-1 .
`\
`:· ,:i":
`..
`,,
`)
`..... ii.;~r~ ,
`.. ~ ., ... _ .. r ................ ~,.
`~'"'" ... ~...
`. . . .
`.
`~---.
`..........
`-
`.. ,., --
`........... ······ .... _.,,.
`-- ... ---......... .... ··i
`
`'
`
`,.
`
`' ·
`
`I
`
`·- ·-1
`I
`' ',. I
`.
`. . "-... j
`.
`I
`I
`·.
`' · ...
`I
`I
`
`··
`
`\ ,,
`··•...
`
`,
`
`..
`
`•.
`
`_ .. ··
`.
`
`I
`
`i
`
`' -
`
`I
`
`I i
`I .
`' i
`j
`I'
`
`I
`
`. ldit~d by -. · · --. _.
`·· · ·-.fraidooi1 ·Mazda ··
`
`I
`. I
`
`.
`
`I
`.... ·I
`
`)
`
`1
`
`Comcast, Ex. 1226
`
`
`
`Telecommunications
`Engineer's
`Reference Book
`
`Edited by
`Fraidoon Mazda
`MPhil DFH DMS MIMgt CEng FIEE
`
`With specialist contributions
`
`--~ UTTERWORTH
`
`lB.EINEMANN
`
`t
`
`I
`i
`
`2
`
`
`
`HOUSTON PUBLIC LIBRARY
`
`1111111111111111111111111111111111111111111111111111111111111111
`R01025 35658
`
`CSCTRA
`
`Butterworth-Heinemann Ltd
`Linacre House, Jordan Hill, Oxford OX2 8DP
`
`@PART OF REED INTERNATIONAL BOOKS
`
`OXFORD LONDON BOSTON
`MUNICH NEW DELHI SINGAPORE SYDNEY
`TOKYO TORONTO WELLINGTON
`
`First published 1993
`
`© Butterworth-Heinemann Ltd 1993
`
`All rights reserved. No part of this publication
`may be reproduced in any material form (including
`photocopying or storing in any medium by electronic
`means and whether or not transiently or incidentally
`to some other use of this publication) without the
`writteo permission of the copyright holder except in
`accordance with the provisions of the Copyright,
`Designs and Patents Act 1988 or under the terms of a
`licence issued by the Copyright Licensing Agency Ltd,
`90 Tottenham Court Road, London, England, WI P 9HE.
`Applications for the copyright holder's written permission
`to reproduce any part of this publication should be addressed
`to the publishers
`
`British Library Cataloguing in Publication Data
`Mazda, Fraidoon F.
`Telecommunications engineer's reference book
`I. Title
`621.382
`
`ISBN O 7506 1037 9
`
`Library of Congress Cataloguing in Publication
`Mazda, Fraidoon F.
`Telecommunications engineer's reference book/Fraidoon Mazda
`p. cm.
`Includes bibliographical references and index.
`ISBN O 1S06 1037 9
`1. Telecommunications. I. Title
`TK5101.M37 1993
`621.382-dc20
`
`92-27846
`CIP
`
`Printed and bound in Great Britain
`
`3
`
`
`
`Coding
`
`Dr M D Macleod
`MAPhDMIEEE
`University of Cambridge
`
`Contents
`
`14.1 The need for error control coding 14/3
`
`14.2 Principles of ECC 14/3
`
`14.3 Block coding 14/4
`
`14.4
`
`Interleaved and concatenated codes 14/6
`
`14.5 Cyclic codes 14/6
`
`14.6 Convolutional codes 14/9
`
`14.7 Encryption 14/11
`
`14.8 Spread spectrum systems 14/12
`
`14.9 References 14/13
`
`:et Switching in
`:ontrol Procedur
`104, September.
`Packet-switched
`Telecommunicati
`
`ark Magazine,
`MLMA-AC
`Congr. 77, pp. 4
`MAandTDMA
`un., COM-27, M
`'or personal com
`new era IEEE mi
`1 90, (2), Septem
`i Spectrum for
`Magazine, April.
`~iques for Data 11
`'.ms, PhD thesis, U
`ication Networks:
`;on-Wesley.
`ter Communicati
`
`muary.
`191) Analysis of a
`vork with capture
`(2), March.
`unisation and Mui
`iMP, Fall coMPC
`
`4
`
`
`
`e oeed for error control coding
`
`. crete) cornrnunicatio~ system, information is sent as
`dis di its, which are first converted to an analogue
`of gby modulation at the transmitter, and then con(cid:173)
`forrndigits by de-modulation at the receiver. An ideal
`to hannel would transmit information without any
`0
`. c or distortion. Any real channel introduces noise
`(!Oil
`.
`however, and these cause the corruption or loss of
`'the receiver. The system designer can try to reduce
`of digit errors by appropriate design_of the analo~e
`unication system, but 1t may be either 1mposs1ble
`UU:hieve a sufficiently small probability of error in
`~a
`.
`b
`.
`etter solution will often e to use error control coding
`
`coding is the controlled addition of redundancy to the
`t stream in such a way that errors introduced in the
`detected, and in certain circumstances corrected, in
`is therefore a form of channel coding, so called
`ensates for imperfections in the channel; the other
`coding is transmission ( or line coding), which has
`es such as spectrum shaping of the transmitted
`d to lower the probability of error from the input
`e communication system. The added redundancy
`r, that extra digits have to be transmitted over the
`t either the channel transmission rate must be in(cid:173)
`rate of transmission of digits from input to output
`
`d addition of redundancy in ECC contrasts with
`data compression) in which redundancy is removed
`·gnal. For a signal (such as speech) with a high
`ic redundancy it would in principle be possible to
`rror detection and correction at the receiver without
`redundancy. However this is generally too complex
`t on the uncontrolled redundancy of the source
`tive. The functions of error control coding and
`therefore usually separated.
`blocks used for error control coding are a coder
`dulator in the transmitter, and a decoder following
`in the receiver. The decoder may be designed to
`s, or it may be designed to correct them. These
`own as error detection and error correction respec-
`
`ain types of ECC: block coding and convolutional
`coding, the input is divided into blocks of k digit~.
`duces a block of n digits for transmission, and the
`d as 'an (n,k) code'. Each block is coded and
`separately from all other blocks. In convolutional
`input and output are continuous streams of digits.
`n output digits for every k digits input, and the
`as 'a rate k/n code'.
`ts are included unmodified in the coder output the
`as systematic. The additional digits introduced by
`n known as parity or check digits. As well as the
`llveness of systematic codes, they have the advan(cid:173)
`of decoder complexities is made possible. The
`
`The need for error control coding 14/3
`
`simplest decoder can simply extract the unmodified input digits
`from the coded digit stream, ignoring the parity digits. A more
`sophisticated decoder may use the parity digits for error detection,
`and a full decoder for error correction. Unsystematic codes also
`exist, but are less common] y used.
`
`14.2.2 Feedforward and feedback error
`correction
`
`In feedforward error correction (FEC) the decoder applies error
`correction to the received codeword, and it may also detect some
`uncorrectable errors. However, no return path from the receiver to
`the sender is assumed. Either block or convolutional codes may be
`used for feedforward error correction.
`In feedback error correction, for which only block codes can be
`used, the receiver only attempts to detect errors, and sends return
`messages to the sender which cause repeat transmission if any errors
`are detected in a received block. In the OSI model for packet data
`networks, this function is carried out within the data link layer, by
`the return of a positive or negative acknowledgement (ACK or
`NAK) to the sender on receipt of a data block, a system known as
`stop-and-wait ARQ. In go-back-N ARQ, receipt of a NAK by the
`transmitter makes it retransmit the erroneous codeword and the N-1
`following ones, where N is chosen so that the time taken to send N
`codewords is less than the round trip delay from transmitter to
`receiver and back again. This obviates the need for a buffer at the
`receiver. In selective repeat ARQ, only the codewords for which
`NAKs have been returned are re-transmitted. Performance analysis
`(Lin, 1983) shows that this is the most efficient system, although it
`requires an adequate buffer in the receiver.
`
`14.2.3 Arithmetic for ECC
`
`In a digital communication system, each transmitted digit is selected
`from a finite set of M values and is described as an M-ary digit. For
`example, binary digits (bits) have one of two values, which may be
`represented as O and 1. (The actual values of the physical signal used
`to transmit the digits, for example +12V and-12V, are irrelevant
`here). We shall assume that the input message digits use the same
`value of M as the transmitted digits; if not, the message digits can
`simply be converted to M-ary before coding.
`The analytical design of coders and decoders for M-ary digits
`requires the use of Galois field arithmetic, denoted GF(M). If M is
`a prime number (including the important case of binary digits,
`where M = 2), Galois field arithmetic is equivalent to arithmetic
`modulo-M. GF(M) arithmetic also exists when M is equal to a
`power of a prime, so coders using the principles described below
`can be designed for quaternary ( 4-valued) and octal (8-valued) digit
`systems, for example, but in these cases GF(M) arithmetic is not
`equivalent to modulo-M arithmetic.
`In the case of binary systems (M = 2), the addition and multipli(cid:173)
`cation operations in GF(2) (i.e. modulo-2) arithmetic are as follows:
`
`(0 + 0) = (1 + 1) = 0
`(0 + 1) = (1 + 0) = 1
`(() X 0) = (0 X 1) = (1 X 0) = ()
`(lxl)=l.
`
`Clearly, addition in this system is equivalent to the logical exclu(cid:173)
`sive OR (XOR) function, and multiplication is equivalent to the
`logical AND function. For non-binary systems, multiplication and
`addition operations can be implemented using either dedicated logic
`or lookup tables.
`
`5
`
`
`
`14/4 Coding
`
`Note that in modulo-2 arithmetic, addition and subtraction are
`equivalent. Some textbooks only discuss binary coders, and there(cid:173)
`fore treat all subtractions as additions. However for values of M
`other than 2 addition and subtraction are not equivalent, and it is
`essential to implement subtractions correctly.
`
`14.2.4 Types of error
`
`If the physical cause of digit errors is such that any digit is as likely
`to be affected as any other, the errors are described as random. A
`typical cause of random errors is thermal noise in the received
`signal. Other types of interference, however, may make it likely that
`when an error occurs, several symbols in succession will be cor(cid:173)
`rupted; this is known as a burst error. A typical cause of burst errors
`is interference. Although the true behaviour of the channel may be
`more complex than either of these simple models, the random error
`and burst error models are simple, effective, and universally used
`for describing channel characteristics and error control code per(cid:173)
`formance.
`A channel used for transmitting binary digits is known as a binary
`channel, and if the probability of error is the same for Os and ls, the
`channel is called a Binary Symmetric Channel. The probability of
`error in binary digits is known as the bit error rate (BER).
`
`14.2.5 Coding gain
`
`Coding gain is a parameter commonly used for evaluating the
`effectiveness of an error correcting code, and hence for comparing
`codes. It is defined as the saving in energy per source bit of
`information for the coded system, relative to an uncoded system
`delivering the same BER. The effects of both error correction and
`the increase in transmission rate by a factor of n/k must be included
`when calculating the coding gain.
`
`14.2.6 Criteria for choosing a code
`
`The primary objective of error control coding will be to achieve a
`desired end-to-end probability of either uncorrected or undetected
`digit errors. The choice of code will depend on the error charac(cid:173)
`teristics of the channel (particularly the random and burst error
`probabilities). The other important factors are likely to be the value
`of n/k (the increase in transmission rate over the channel), and the
`implementation complexity and cost of the coder and decoder.
`
`errors is even, the single parity code will fail to detect the
`111·
`code is therefore a single error detecting (SEO) code.
`
`14.3.2 Linear block codes
`
`The even parity code is the simplest example of a powerful
`codes called linear block codes. For such codes, the bloc
`message digits is represented as the k-element row vector d
`n digit codeword produced by the coder is represented ~
`n-element vector c. The function of the linear block code y
`scribed by the Equation 14.1 whereG is the(k x n) generato/ I&
`
`C=dG
`
`The multiplications and additions in this equation are carri
`in GF(M) arithmetic (i.e. modulo-2 for binary digits). The
`words generated by the equation are called valid codewords
`there are zk possible datawords, only zk of the zn possible·
`words are valid codewords.
`Systematic linear block codes are produced by a generator
`of th_e form shown in Equation 14.2, where ~ is the (k x k)
`matnx.
`
`When G has this form, the codeword c has the form of
`14.3, in other words the first k digits of the codeword equal
`dataword, and the last n - k digits are parity digits.
`
`C = [dldP]
`
`Let r be the received codeword; in the absence of errors r = c
`decoder performs the operation of Equation 14.4, where H
`k) e
`((n - k) x n) parity check matrix, to produce the (n
`syndromes.
`
`His chosen so that all valid codewords produce a zero syn
`the syndrome then plays a crucial role in error correction. F
`systematic code given above, the optimum form of parity
`matrix is simply as in Equation 14.5.
`
`14.3 Block coding
`
`14.3.1 Single parity checks
`
`The simplest block coder appends a single parity digit to each block
`of k message digits. This produces a systematic (k + 1, k) code
`known as a single parity code. For binary digits, the parity bit may
`be either the modulo-2 sum of the message bits or 1 minus that sum.
`The former case is known as even parity, because the sum of the
`k + 1 bits of the codeword (including the parity bit) is 0, and the
`latter is known as odd parity.
`The decoder forms the sum of the bits of the received codeword.
`For even parity a sum of 1 means that there has been an error, and a
`sum of 0 is assumed to mean that the received codeword is correct.
`(For odd parity 0 indicates an error, and the correct sum is 1). Note
`that when an error is detected there is no way to deduce which bit( s)
`are in error; also, if more than one error occurs, and the number of
`
`For unsystematic codes, construction of the parity check
`more difficult.
`
`14.3.3 Distance and code performance
`
`The Hamming distance between two codewords is simply
`ber of hit positions in which they differ. If the Hamming
`between two codewords c1 and c2 is cl, and c1 is transmitt
`errors would have to occur for codeword c2 to be receiv
`generally, if the minimum Hamming distance between cod
`and any other valid codeword is dM and c1 is transmitted,
`received codeword will not be a valid codeword if betwe
`dM - 1 errors occur. The decoder could therefore detect u
`1 errors.
`Assume that an invalid codeword is received. The dista
`ber of discrepancies) between it and all the valid codewoT<l5
`
`6
`
`
`
`40
`
`Multiplexers
`
`J Hoolan
`Dowty Communications Ltd
`
`Contents
`
`40.1
`
`Introduction 40/3
`
`40.2 Time Division Multiplexi:rs 40/3
`
`40.3 Statistical time division multiplexing 40/6
`
`40.4 High order multiplexing 40/8
`
`40.5 Multiplexing and packi:t switching 40/9
`
`40.6 X.25 and OSI 40/10
`
`40. 7 Physical layer standards 40/13
`
`40.8 Multiplexers in communications networks 40/14
`
`40.9 The future of multiplexing 40/16
`
`7
`
`
`
`40,1
`
`Introduction
`
`The multiplexer is one of the most important components in com(cid:173)
`munications networking. Its central function, from the network
`managers viewpoint, is to concentrate many users (or information
`channels) on to a single transmission channel in order to maximise
`the efficiency of that channel: it is used in almost every aspect of
`networking digital data, voice and video. This section will describe
`the advantages and disadvantages of different data multiplexing
`techniques, why these different techniques evolved to solve particu(cid:173)
`lar network engineering problems and how they fit in to modern
`networks.
`figure 40. 1 shows the basic theoretical model for a multiplexer
`with the composite line speed exactly equal to the aggregate speed
`of the inputs.
`Given a transmission channel, there are two ways the available
`bandwidth can be used: firstly by dividing the available bandwidth
`frequency spectrum into a subset of frequencies, each of which can
`then simultaneously use the transmission channel and allocate each
`frequency band to an input channel that needs to be multiplexed; or
`secondly, allocate all the available bandwidth to each channel for a
`fixed discrete time period. The first of these methods would be
`frequency Division Multiplexing (FDM) and the latter Time Divi(cid:173)
`sion Multiplexing (TOM). FDM is used primarily as an analogue
`solution to multiplexing and, for example, has been used exten(cid:173)
`sively in telephony; indeed many of the FDM standards and tech(cid:173)
`niques such as the multiplexing ratios dictated by the early designs
`of telephone exchange multiplexers (such as 24:1) are still in evi(cid:173)
`dence in some of the latter digital exchanges.
`This chapter is concerned however with the use and applications
`of latter type of multiplexing technique, Time Division Multiplex(cid:173)
`ing which can be used in one of two modes, deterministic or
`non-deterministic. Deterministic TOM (which is the more com(cid:173)
`monly known just as TOM) allocates the available transmission
`channel bandwidth of a fixed regular basis to the input channels,
`whether they have data to send or not. Non-deterministic TOM or
`stalislical TOM (which is more commonly just statistical multiplex(cid:173)
`ing) allocates the available bandwidth to input channels only o n
`demand when data is present.
`
`40.2 Time Division Multiplexers
`
`40.2.l Principles
`
`Time division multiplexing is lhe earliest and simplest form of
`digital multiplexing. It was developed to solve the communications
`A
`
`Introduction 40/3
`
`problem created by the growth in remote computer processing
`during the 1960s. Computer terminals (or consoles) were locally
`attached in early computers but as computers became multi-user, so
`the need grew for more users gaining remote access over a single
`transmission line. Single users could gain access by simply attach(cid:173)
`ing'their terminal to a modem that converted the digital information
`by modulation into a voice frequency that could then be transmitted
`down a telephone to a modem at the receiving end that demodulated
`the signals back into digital form and hence onto the computer.
`However the need for groups of co-located users to gain access to
`computing resource meant that multiplexing techniques had 10 be
`applied to maximise the utilisation of rented PTI lease line circuits
`or costly dial up calls.
`The early forms of multiplexers, which evolved to meet this
`growth in computing power, were designed for use with asyn(cid:173)
`chronous data as this was the most commonly available type of
`terminal and printer. Typically running at speed~ of up to t 200bit/s
`and with code formats of 5 and 7 bits (Baudot and ASCII respec(cid:173)
`tively). As computer manufacturers moved to synchronous data, as
`a more efficient form of communications, so the design of multi(cid:173)
`plexers was adapted for handling this type of traffic. It was in this
`period that many of the design techniques to overcome specific
`engineering and networking problems evolved.
`In common with all multiplexing techniques the primary require(cid:173)
`ment was for the two multiplexers to have some form of synchroni(cid:173)
`sation procedure whereby they could calculate the location of each
`channel. This was done by defining a fixed length composite frame
`format, as in Figure 40.2, that had a unique synchronisation code at
`the start. When the link was first started the multiplexers would
`enter into a 'training' period, with only empty frames plus the
`synchronisation ' header' code being sent to each other to delennine
`the frame boundaries. The composite overhead or bandwidth
`needed could be taken by reducing the available aggregate from the
`input channels.
`Starting with the first commercially avai lahle asynchronous
`multiplexers the initial multiplexing technique was bit interleaved.
`In this method, the incoming data on each channel is sampled bit by
`bit and stored in a transitory central buffer before being assembled
`on lo a composite. This is the simplest technique that can be
`employed as it only requires lhal the multiplexer recognises the bit
`boundaries of the incoming data. Providing that the sequence of data
`bits is then forwarded lo the remote end and demultiplexed without
`losing integrity, then any lype of data formal can be handled.
`However, as this meant sending all data bits for an asynchronous
`character including the slop, start and parity bits, the multiplexing
`technique adopted quickly moved to hyte interleaved. In this
`method the ancillary bits could be stripped off and only the data
`sent. At the receiving end they could be reconstituted. The byte was
`A
`
`Total =
`Nbit/s
`
`B
`
`C
`
`D
`
`Total = Nbit/s
`
`MUX
`
`MUX
`
`Total=
`Nbit/s
`
`B
`
`C
`
`D
`
`Figure 40.1 Basic model for a multiplexer
`
`8
`
`
`
`40/4 Multiplexers
`
`Sync. pattern
`
`I I I
`
`I.
`
`i.
`
`Nbit/s fixed
`
`Frame
`
`I I I
`
`:I
`
`Figure 40.2 The basic operation of framing
`
`8 bits with data requiring 7 bits and the 8th bit in each byte
`indicating whether data or controls were being sent. Although it
`meant that 5 bit data such as Baudot had 2 bits per byte wasted and
`that 8 bit codes could not be sent, as the majority of traffic was based
`on 7 bit code (ASCH), the overall gains made it worthwhile.
`As stated above, the origi nal design was for handling asyn(cid:173)
`chronous traffic and the only rules for configuration would involve
`working out the total aggregate input and formulating the best
`'scanning' method to cater for al l the different speeds, so that they
`could mapped on to the available composite bandwidth. According
`to the design of the multiplexer a small percentage of the bandwidth
`had to be allocated for the synchronisation pattern, or sequence, so
`the general design rule was to limit the overhead to around I % or 2
`bits in a 200 bit frame. In addition, if the status of the V.24 (RS232)
`control lines such as Data Terminal Ready (circuit l08/1 or 2) or
`Request to Send (circuit 105), then this had to be allocated band(cid:173)
`width as if it were data. As an example, if a half duplex circuit is
`being employed, which means that the data and control signals have
`to be kept contiguous, then the control information could require as
`much bandwidth as the data. The result is that the bandwidth
`actually available for data could be less than the theoretical maxi(cid:173)
`mum by up to 50%. The technique developed to overcome this
`problem is to use multi-frames with two types of controls, high and
`low priority. High priority is dealt with as described above. Low
`priority control information is sent every N frames, where N could
`be from 4 to 64 depending on the frame size and speed of the
`composite.
`
`Figure 40.3 shows the ideal model of time division multiplexing
`operation, where all eight channels are being efficiently multiplexed
`onto a composite line. At any one instant in time there is always one
`of the channels using the available bandwidth. Figure 40.4 shows
`the realistic utilisation of the line. Note that only channels I, 2 and
`6 have any data to send. However, time slot~ in the form of band(cid:173)
`width still have to be allocated since the TOM cannot recognise the
`absence of real data; this is the trade-off against data transparency
`and speed.
`To summarise, the technique of sending asynchronous data by
`TOM is to use a frame synchronised, byte interleaved method with
`facilities for control information using a redundant bits.
`The advantage is transparency to data format; any format of
`asynchronous data can be sent, at any speed.
`The disadvantages are:
`
`1. Fixed speeds; it was usually difficult to change any speeds
`without completely re-programming the multiplexers.
`2. Poor efficiency; input channels always have a fixed allocation
`of composite bandwidth, whether they have data to send or not.
`As asynchronous data is by definition 'bursty ' interactive type
`traffic, there wi ll almost certainly be long periods of inactivity
`which still has bandwidth heing allocated to it.
`3. Prone to errors; in the process of being transmitted, any errors
`generated on the composite circuit are passed to the receiving
`end without any indication to the end device (in fact the parity
`recovery method makes this worse as it hides dual bit errors).
`
`Channel 1
`
`Virtual
`channels
`
`Channel 8
`
`Figure 40.3
`
`Ideal model of a TOM
`
`Direction of data
`
`- Bit interleaved data
`
`Channel 1
`
`Virtual
`channels
`
`Channel 8
`
`Figure 40.4
`
`As sy nchrono
`networks wit
`synchronous
`computing re
`For synchro
`as the most s
`chronous mul
`the multiplex
`sation so thal
`generated clo
`as it imposes
`networks and
`Apart from ti
`composite fra
`lation.
`In asynchro
`according to
`therefore devi
`Synchronous
`vary hy 0.1 %,
`important for
`ation from the
`The techniq
`allocating it I
`these constrai
`
`T
`N
`
`Figure 40.5
`
`9
`
`
`
`L
`
`ne division multiplexing
`,g efficiently multiplexed
`, time there is always one
`,idth. Figure 40.4 shows
`at only channels l , 2 and
`lots in the form of band.
`DM cannot recognise the
`,gains! data transparency
`
`1g asynchronous data hy
`inte rleaved method with
`:dundant hits.
`1 format; any format of
`~d.
`
`It to change any speeds
`the multiplexers.
`1s have a fixed allocation
`y have data to send or not.
`1 'bursty' interactive type
`long periods of inactivity
`ated to it.
`1g transmitted, any errors
`·e passed to the receiving
`I device (in fact the parity
`s it hides dual bit errors).
`
`Channel 1
`
`Virtual
`channels
`
`Channels
`
`Time Division Multiplexers 40/5
`
`Virtual
`channels
`
`Channel 1 I\
`j
`
`Channel 8
`
`I Channel 1
`Direction of data flow \
`- Bit interleaved data
`
`Virtual
`channels
`
`Channels
`
`figure 40.4 Line utilisation in a typical TOM
`
`Unless the link synchronisation actually fails the remote end
`has no indication that there is a problem on the line.
`
`40.2.2 Synchronous TOM
`
`As synchronous protocols evolved the need to multiplex them grew;
`networks w ith remote sites that had a mix of asynchronous and
`synchronous terminals needed to connect them to the central site
`computing resource.
`For synchronous TDMs, the bit-interleaved method was adopted
`as the most superior technique. The main difference from asyn(cid:173)
`chronous multiplexing being that as well as keeping data integrity,
`the multiplexers had to keep the associated clock timing synch.roni(cid:173)
`sation so that the demultiplexed recovered data could have a re(cid:173)
`generated clock associated w ith it. This point will be referred to later
`as it imposes major restrictions on the design and operation of
`networks and techniques have heen developed to solve the problem.
`Apart from timing considerations, the synchronisation header in the
`composite frame h.as to be included in the overall bandwidth calcu(cid:173)
`lation.
`In asynchronous data the actual speed of transmission can vary,
`according to the manufacturer's specification, by up to :1:15%,
`therefore devices running overspeed were a particular problem.
`Synchronous data has a much. tighter specification and may only
`vary by 0.1 %, a, recommended by CCITI V.28. This is particularly
`important for synchronous moderns w hich cannot tolerate any devi(cid:173)
`ation from the specified speed.
`The technique of 'robbing' the low speed input c hannels and
`allocating it to the composite was normally only applied within
`lhese con.strainls. Two alternatives were:
`
`1. To designate one of the input channels as a 'vari-speed ' input
`which may be attach.ed to non-critical devices. T his approach,
`for obvious reasons, h.as to be handled w ith caution.
`2. By the preferred technique used by latte r designs to perma(cid:173)
`nently allocate a synchronisation overh.ead.
`
`A mixture of bit and byte interleaving with. a fixed synchronisation
`header was also adopted by some high order multiplexers, where
`multiple voice channels needed to be multiplexed after being digi(cid:173)
`tally encoded; the US Bell DI system for example. The basic
`technique employed is for an analogue sample of th.e voice signal to
`be converted into an 8 bit code word, after being manipulated
`through a compander circuit operating on a logarithmic law to
`reduce the signal to noise level. T he Bell D2 system used bit robbing
`for signalling purposes. The standards which has been adopted for
`this type of high order multiplexing are discussed later in this
`Chapter e.g. the CCITI standa rd G.71I for pulse code modulation.
`
`From t he viewpoint of line efficiency between two point to point
`multiplexers, the advantages and disadvantages of synchronous
`TOM compared to asynchronous TOM are almost identical. The
`main exception is that error detection and correction is not an issue
`with a synchronous data, as it w ill be enveloped in its own protocol
`independent from the multiplexer and therefore wil l have its own
`error recovery mechanisms via retransmission. However, from a
`networking viewpoint, the network timing recovery mechanisms
`and the methods by which the nodes in a network can be syn·
`chronised together, is a ma,jor issue.
`Figure 40.5 s hows a more realistic model of a multiplexer, with
`the overheads taken into account, that results in a composite that
`A
`
`Total=
`NbiVs
`
`A
`
`B
`
`C
`
`D
`
`MUX
`
`Total= MbiVs
`
`MUX
`
`B
`
`C
`
`D
`
`Figure 40.5 Model of a multiplexer with overheads considered
`
`10
`
`
`
`40/6 Multiplexers
`
`must be faster than the input aggregate. The value of M is given by
`Equation 40.5, therefore M > N.
`
`5.
`
`It was being considered as an international standard.
`
`M=A+B+C+C
`+ synchronisation header + control information
`
`(40.1)
`
`In summary it can be stated that time division multiplexing has
`established itself as the most efficient technique for handling syn(cid:173)
`chronous protocols and data at different speeds, even t hough it
`suffered from the fact that bandwidth is always wasted. It is not
`however very effective at handing asynchronous data due to the
`inflexibility and lack of error detection and correction. It is from this
`major disadvantage that the use of statistical multiplexers evolved.
`
`40.3 Statistical time division multiplexing
`
`40.3.1 Principle of Operation
`
`Caught between the exponential growth of computing power and
`the use of asynchronous terminals as a cheap and convenient way
`of accessing computers, the statistical TDM was developed. It was
`first formulated in the early 1970s and in particular on the Arpanet
`network in the USA from which the X.25 packet switch standard
`evolved (Davis, 1973).
`As stated above, the main problems with using mM techniques
`on asynchronous data were lack of error detection and correction,
`and poor efficiency on the composite line, especially since the
`average asynchronous device is only active for 5 to 10% o f the time.
`The solution for a~ynchronous multiplexers was to use a formal
`protocol between the multiplexer nodes which could concentrate
`the data and provide the means of detecting and recovering from
`errors on the line. T he protocol invariably chosen was based on a
`High Level Data Link Control (HDLC) which in turn had been
`derived from the IBM's SDLC protocol. This protocol had several
`design advantages over previous synchronous proto