DIGITAL SIGNAL ENCODING FOR LANs

DIGITAL SIGNAL ENCODING FOR LANs

We looked at some of the common techniques for encoding digital data

for transmission, including Manchester and Differential Manchester, which are used in some

of the LAN standards. In this appendix, we examine some additional encoding schemes

referred to in this lesson.

4B/5B-NRZI

This scheme, which is actually a combination of two encoding algorithms, is used both for

100BASE-X and FDDI. To understand the significance of this choice, first consider the simple

alternative of an NRZ (non-return to zero) coding scheme. With NRZ, one signal state

represents binary one, and one signal state represents binary zero. The disadvantage of this

approach is its lack of synchronization. Because transitions on the medium are unpredictable,

there is no way for the receiver to synchronize its clock to the transmitter. A solution to this

problem is to encode the binary data to guarantee the presence of transitions. For example,

the data could first be encoded using Manchester encoding. The disadvantage of this

approach is that the efficiency is only 50%. That is, because there can be as many as two transitions

per bit time, a signaling rate of 200 million signal elements per second (200 Mbaud) is

needed to achieve a data rate of 100 Mbps; this represents an unnecessary cost and technical

burden.

Greater efficiency can be achieved using the 4B15B code. In this scheme, encoding is

done four bits at a time; each four bits of data are encoded into a symbol with five code bits,

such that each code bit contains a single signal element. The block of five code bits is called

a code group. In effect, each set of 4 bits is encoded as 5 bits. The efficiency is thus raised to

80%; 100 Mbps is achieved with 125 Mbaud.

To ensure synchronization, there is a second stage of encoding: each code bit of the

4B15B stream is treated as a binary value and encoded using Nonreturn to Zero Inverted

(NRZI) (see Figure 4.2). In this code, a binary 1 is represented with a transition at the beginning

of the bit interval, and a binary 0 is represented with no transition at the beginning of

the bit interval; there are no other transitions. The advantage of NRZI is that it employs differential

encoding. Recall from Lesson 4 that in differential encoding, the signal is decoded

by comparing the polarity of adjacent signal elements rather than the absolute value of a signal

element. A benefit of this scheme is that it is generally more reliable in detecting a transition

in the presence of noise and distortion than in comparing a value to a threshold.

Now we are in a position to describe the 4B15B code and to understand the selections

that were made. Table 13.8 shows the symbol encoding. Each 5-bit code group pattern is

shown, together with its NRZI realization. Because we are encoding four bits with a 5-bit pattern,

only 16 of the 32 possible patterns are needed for data encoding. The codes selected to

represent the 16 4-bit data blocks are such that a transition is present at least twice for each

5-code group code. No more than three zeros in a row are allowed across one or more code

groups.

The encoding scheme can be summarized as follows:

1. A simple NRZ encoding is rejected because it does not provide synchronization; a

string of 1s or 0s will have no transitions.

2. The data to be transmitted must first be encoded to assure transitions. The 4Bl5B code

is chosen over Manchester because it is more efficient.

3. The 4Bl5B code is further encoded using NRZI so that the resulting differential signal

will improve reception reliability.

4. The specific 5-bit patterns for the encoding of the 16 4-bit data patterns are chosen to

guarantee no more than three zeros in a row, to provide for adequate synchronization.

Those code groups not used to represent data are either declared invalid or are

assigned special meaning as control symbols. These assignments are listed in Table 13.8. The

nondata symbols fall into the following categories:

@ Idle. The idle code group is transmitted between data transmission sequences. It

consists of a constant flow of binary ones, which in NRZI comes out as a continuous

alternation between the two signal levels. This continuous fill pattern establishes and

maintains synchronization and is used in the CSMAICD protocol to indicate that the

shared medium is idle.

@ Start-of-stream delimiter. Used to delineate the starting boundary of a data transmission

sequence; it consists of two different code groups.

a End-of-stream delimiter. Used to terminate normal data transmission sequences; it

consists of two different code groups.

Transmit error. This code group is interpreted as a signaling error. The normal use of

this indicator is for repeaters to propagate received errors.

Although 4BI5B-NRZI is effective over optical fiber, it is not suitable, as is, for use over

twisted pair. The reason is that the signal energy is concentrated in such a way as to produce

undesirable radiated emissions from the wire. MLT-3, which is used on both 100BASE-TX

and the twisted pair version of FDDI, is designed to overcome this problem.

The following steps are involved:

1. NRZZ to NRZ conversion: The 4B/5B NRZI signal of the basic 100BASE-X is converted

back to NRZ.

2. Scrambling: The bit stream is scrambled to produce a more uniform spectrum distribution

for the next stage.

3. Encoder: The scrambled bit stream is encoded using a scheme known as MLT-3.

4. Driver: The resulting encoding is transmitted.

The effect of the MLT-3 scheme is to concentrate most of the energy in the transmitted

signal below 30 MHz, which reduces radiated emissions; this, in turn, reduces problems

due to interference.

The MLT-3 encoding produces an output that has a transition for every binary one that

uses three levels: a positive voltage (+V), a negative voltage (-V) and no voltage (0). The

encoding rules are best explained with reference to the encoder state diagram shown in Figure

13.22:

1. If the next input bit is zero, then the next output value is the same as the preceding

value.

2. If the next input bit is one, then the next output value involves a transition:

a. If the preceding output value was either +V or -V, then the next output value is 0.

b. If the preceding output value was 0, then the next output value is nonzero, and that

output is of the opposite sign to the last nonzero output.

Figure 13.23 provides an example. Every time there is an input of 1, there is a transition.

The occurrences of +V and -V alternate.

8B6T

The 8B6T encoding algorithm uses ternary signaling. With this method, each signal element

can take on one of three values (positive voltage, negative voltage, zero voltage). A pure

ternary code is one in which the full information-carrying capacity of the ternary signal is

exploited. However, pure ternary is not attractive for the same reasons that a pure binary

(NRZ) code is rejected: lack of synchronization. However, there are schemes referred to as

block-coding methods that approach the efficiency of ternary and overcome this disadvantage.

A new block coding scheme known as 8B6T is used for 100BASE-T4.

With 8B6T, the data to be transmitted are handled in 8-bit blocks. Each block of 8 bits

is mapped into a code group of six ternary symbols. The stream of code groups is then transmitted

in round-robin fashion across the three output channels (Figure 13.24). Thus, the

ternary transmission rate on each output channel is

Table 13.9 shows a portion of the 8B6T code table; the full table maps all possible 8-

bit patterns into a unique code group of six ternary symbols. The mapping was chosen with

two requirements in mind: synchronization and DC balance. For synchronization, the codes

were chosen so as to maximize the average number of transitions per code group. The second

requirement is to maintain DC balance, so that the average voltage on the line is zero;

for this purpose, all of the selected code groups have either an equal number of positive and

negative symbols or an excess of one positive symbol. To maintain balance, a DC balancing

algorithm is used. In essence, this algorithm monitors the cumulative weight of all code

groups transmitted on a single pair. Each code group has a weight of 0 or 1. To maintain balance,

the algorithm may negate a transmitted code group (change all + symbols to – symbols

 

and all - symbols to + symbols), so that the cumulative weight at the conclusion of each code

group is always either 0 or 1.

5B6B

The 5B6B encoding is used in the 100VG-AnyLAN specification in the following way: A

MAC frame is divided into 5-bit chunks (quintets), and each successive chunk is transmitted

over a different channel in round-robin fashion. Thus, to achieve a data rate of 100 Mbps, a

data rate of only 25 Mbps is needed on each channel.

To ensure adequate transitions on each line for synchronization, an encoding scheme

known as 5B6B is used. The 5B6B scheme is based on the same strategy as the 4B/5B scheme

described earlier. In this case, each group of 5 input bits is mapped into a set of 6 output bits.

Thus, for an effective data rate of 25 Mbps, a signaling rate of 30 Mbaud is required.

With the 5B6B scheme, there are 32 possible 5-bit inputs. Ideally, we would like to

assign to each 5-bit input a 6-bit code that has an equal number of ones and zeros; this would

maintain a dc balance of zero. However, there are only twenty 6-bit code words that have

three ones and zeros. These codes are assigned to 20 of the input patterns. For the remaining

12 input patterns, two code words are assigned, one with four zeros and two ones (mode

2) and one with two zeros and four ones (mode 4). Successive instances of any of these 24

unbalanced code words must alternate between mode 2 and mode 4 output to maintain balance.

If, during reception, a station or repeater receives two of the same type of unbalanced

words in a row (with any number of intervening balanced words), the receiver knows that a

transmission error has occurred and will ask for a retransmission of the data.

Table 13.10 shows the complete 5B6B encoding scheme. There is a unique output code

word for 20 of the input patterns; for the rest, the transmitter keeps track of whether the last

unbalanced transmitted word was mode 2 or mode 4 and transmits the appropriate output

code word to maintain balance.

The encoding scheme used for Fibre Channel is 8B/10B, in which each 8 bits of data is converted

into 10 bits for transmission. This scheme has a similar philosophy to the 4Bl5B

scheme used for FDDI, as discussed earlier. The 8B110B scheme was developed and patented

by IBM for use in its 200-megabaud ESCON interconnect system [WIDM83]. The 8Bl10B

scheme is more powerful than 4Bl5B in terms of transmission characteristics and error detection

capability.

The developers of this code list the following advantages:

It can be implemented with relatively simple and reliable transceivers at low cost.

* It is well-balanced, with minimal deviation from the occurrence of an equal number of

1 and 0 bits across any sequence.

e It provides good transition density for easier clock recovery.

e It provides useful error-detection capability.

The 8Bl10B code is an example of the more general mBnB code, in which m binary

source bits are mapped into n binary bits for transmission. Redundancy is built into the code

to provide the desired transmission features by making n > rn.

Figure 13.25 illustrates the operation of this code. The code actually combines two

other codes, a 5Bl6B code and a 3Bl4B code. The use of these two codes is simply an artifact

that simplifies the definition of the mapping and the implementation; the mapping could

have been defined directly as an 8Bl10B code. In any case, a mapping is defined that maps

each of the possible &bit source blocks into a 10-bit code block. There is also a function

called disparity control. In essence, this function keeps track of the excess of zeros over ones

or ones over zeros. An excess in either direction is referred to as a disparity. If there is a disparity,

and if the current code block would add to that disparity, then the disparity control

block complements the 10-bit code block. This has the effect of either eliminating the disparity

or at least moving it in the opposite direction of the current disparity.

The encoding mechanism also includes a control line input, K, which indicates whether

the lines A through H are data or control bits. In the latter case, a special nondata 10-bit

block is generated. A total of 12 of these nondata blocks is defined as valid in the standard;

these are used for synchronization and for other control purposes.

PERFORMANCE ISSUE
THE CHOICE OF a LAN or MAN architecture is based on many factors, but one of the

most important is performance. Of particular concern is the behavior (throughput, response

time) of the network under heavy load. Here, we provide an introduction to this topic. A

more detailed discussion can be found in [STAL97].

The Effect of Propagation Delay and Transmission Rate

In Lesson 6, we introduced the parameter a, defined as

In that context, we were concerned with a point-to-point link, with a given propagation time

between the two endpoints and a transmission time for either a fixed or an average frame

size. It was shown that a could be expressed as

This parameter is also important in the context of LANs and MANS, and, in fact, determines

an upper bound on utilization. Consider a perfectly efficient access mechanism that

allows only one transmission at a time. As soon as one transmission is over, another station

begins transmitting. Furthermore, the transmission is pure data; there are no overhead bits.

What is the maximum possible utilization of the network? It can be expressed as the ratio of

total throughput of the network to its capacity:

Now define,

R = data rate of the channel

d = maximum distance between any two stations

V = velocity of signal propagation

L = average or fixed frame length

The throughput is just the number of bits transmitted per unit time. A frame contains L bits,

and the amount of time devoted to that frame is the actual transmission time (L/R) plus the

propagation delay (d/V). Thus,

 

But by our definition of a, above

Substituting (13.2) and (13.3) into (13.1)

Note that the above differs from Equation (6.2), because the latter assumed a half-duplex

protocol (no piggybacked acknowledgments).

So, utilization varies with a; this can be grasped intuitively by studying Figure 13.26,

which shows a baseband bus with two stations as far apart as possible (worst case) that take

turns sending frames. If we normalize time such that frame transmission time = 1, then the

propagation time = a. For a < 1, the sequence of events is as follows:

1. A station begins transmitting at to.

2. Reception begins at to + a.

3. Transmission is completed at to + 1.

4. Reception ends at to + 1 + a.

5. The other station begins transmitting.

For a > 1, events 2 and 3 are interchanged. In both cases, the total time for one "turn"

is 1 + a, but the transmission time is only 1 for a utilization of 1/(1 + a).

The same effect as above can be seen to apply to a ring network in Figure 13.27. Here

we assume that one station transmits and then waits to receive its own transmission before

any other station transmits. The identical sequence of events outlined above applies.

Typical values of a range from about 0.01 to 0.1 for LANs and 0.1 to well over 1.0 for

MANS. Table 13.11 gives some representative values for a bus topology. As can be seen, for

larger and/or higher-speed networks, utilization suffers. For this reason, the restriction of

only one frame at a time is lifted for LANs such as FDDI.

 

Finally, the analysis above assumes a "perfect" protocol, for which a new frame can be

transmitted as soon as an old frame is received. In practice, the MAC protocol adds overhead

that makes utilization worse. This is demonstrated in the next sublesson for token-passing

and for CSMAICD.

Simple Performance Models of Token Passing and CSMA/CD

The purpose of this lesson is to give the reader some insight into the relative performance

of the most important LAN protocols-CSMAICD, token bus, and token ring-by developing

two simple performance models. It is hoped that this exercise will aid in delineating the

results of more rigorous analyses.

For these models, we assume a local network with N active stations, and a maximum

normalized propagation delay of a. To simplify the analysis, we assume that each station is

always prepared to transmit a frame; this allows us to develop an expression for maximum

achievable utilization (U). Although this should not be construed to be the sole figure of

merit for a local network, it is the single most analyzed figure of merit, and does permit useful

performance comparisons.

First, let us consider token ring. Time on the ring will alternate between data frame

transmission and token passing. Refer to a single instance of a data frame followed by a token

as a cycle and define the following:

C = average time for one cycle

TI = average time to transmit a data frame

T2 = average time to pass a token

It should be clear that the average cycle rate is just 1/C = l/(Tl + T2). Intuitively,

That is, the throughput, normalized to system capacity, is just the fraction of time that is spent

transmitting data.

The reasoning above applies equally well to token bus, where we assume that the logical

ordering is the same as the physical ordering and that token-passing time is, therefore, a/N.

For CSMA/CD, consider time on the medium to be organized into slots whose length

is twice the end-to-end propagation delay. This is a convenient way to view the activity on

the medium; the slot time is the maximum time, from the start of transmission, required to

detect a collision. Again, assume that there are N active stations. Clearly, if each station

always has a frame to transmit, and does so, there will be nothing but collisions on the line.

As a result, we assume that each station restrains itself to transmitting during an available slot

with probability P.

Time on the medium consists of two types of intervals: first is a transmission interval,

which lasts 1/2a slots; second is a contention interval, which is a sequence of slots with either

a collision or no transmission in each slot. The throughput is just the amount of time spent in

transmission intervals (similar to the reasoning for Equation (13.5)).

To determine the average length of a contention interval, we begin by computing A,

the probability that exactly one station attempts a transmission in a slot and, therefore,

acquires the medium. This is just the binomial probability that any one station attempts to

transmit and the others do not:

We are interested in the maximum because we want to calculate the maximum throughput

of the medium; it should be clear that maximum throughput will be achieved if we maximize

the probability of successful seizure of the medium. Therefore, the following rule should be

enforced: During periods of heavy usage, a station should restrain its offered load to 1/N.

(This assumes that each station knows the value of N. In order to derive an expression for

maximum possible throughput, we live with this assumption.) On the other hand, during periods

of light usage, maximum utilization cannot be achieved because the load is too low; this

region is not of interest here.

Now we can estimate the mean length of a contention interval, w, in slots:

Figure 13.28 shows normalized throughput as a function of various values of N and for

both token passing and CSMAICD. For both protocols, throughput declines as a increases;

this is to be expected. The dramatic difference, though, between the two protocols is seen in

Figure 13.29, which shows throughput as a function of N. Token-passing performance actually

improves as a function of N, because less time is spent in token passing. Conversely, the

performance of CSMAICD decreases because of the increased likelihood of collision or no

transmission.

It is interesting to note the asymptotic value of U as N increases. For token passing,