For all schemes that encode bits into symbols, the receiver must know when
one symbol ends and the next symbol begins to correctly decode the bits. With
NRZ, in which the symbols are simply voltage levels, a long run of 0s or 1s leaves
the signal unchanged. After a while it is hard to tell the bits apart, as 15 zeros
look much like 16 zeros unless you have a very accurate clock
Accurate clocks would help with this problem, but they are an expensive solution for commodity equipment. Remember, we are timing bits on links that run at many megabits/sec, so the clock would have to drift less than a fraction of a microsecond over the longest permitted run. This might be reasonable for slow links or short messages, but it is not a general solution.
One strategy is to send a separate clock signal to the receiver. Another clock line is no big deal for computer buses or short cables in which there are many lines in parallel, but it is wasteful for most network links since if we had another line to send a signal we could use it to send data. A clever trick here is to mix the clock signal with the data signal by XORing them together so that no extra line is needed.
The clock makes a clock transition in every bit time, so it runs at twice the bit rate. When it is XORed with the 0 level it makes a low-to-high transition that is simply the clock. This transition is a logical 0. When it is XORed with the 1 level it is inverted and makes a high-tolow transition. This transition is a logical 1. This scheme is called Manchester encoding and was used for classic Ethernet.
The downside of Manchester encoding is that it requires twice as much bandwidth as NRZ because of the clock, and we have learned that bandwidth often matters. A different strategy is based on the idea that we should code the data to ensure that there are enough transitions in the signal. Consider that NRZ will have clock recovery problems only for long runs of 0s and 1s. If there are frequent transitions, it will be easy for the receiver to stay synchronized with the incoming stream of symbols.
As a step in the right direction, we can simplify the situation by coding a 1 as a transition and a 0 as no transition, or vice versa. This coding is called NRZI (Non-Return-to-Zero Inverted), a twist on NRZ. The popular USB (Universal Serial Bus) standard for connecting computer peripherals uses NRZI. With it, long runs of 1s do not cause a problem.
A well-known code to do this is called 4B/5B. Every 4 bits is mapped into a5-bit pattern with a fixed translation table. The five bit patterns are chosen so that there will never be a run of more than three consecutive 0s. The mapping is shown in Fig. 2-21. This scheme adds 25% overhead, which is better than the 100% overhead of Manchester encoding. Since there are 16 input combinations and 32 output combinations, some of the output combinations are not used. Putting aside the combinations with too many successive 0s, there are still some codes left. As a bonus, we can use these nondata codes to represent physical layer control signals. For example, in some uses ‘‘11111’’ represents an idle line and ‘‘11000’’ represents the start of a frame.
Accurate clocks would help with this problem, but they are an expensive solution for commodity equipment. Remember, we are timing bits on links that run at many megabits/sec, so the clock would have to drift less than a fraction of a microsecond over the longest permitted run. This might be reasonable for slow links or short messages, but it is not a general solution.
One strategy is to send a separate clock signal to the receiver. Another clock line is no big deal for computer buses or short cables in which there are many lines in parallel, but it is wasteful for most network links since if we had another line to send a signal we could use it to send data. A clever trick here is to mix the clock signal with the data signal by XORing them together so that no extra line is needed.
The clock makes a clock transition in every bit time, so it runs at twice the bit rate. When it is XORed with the 0 level it makes a low-to-high transition that is simply the clock. This transition is a logical 0. When it is XORed with the 1 level it is inverted and makes a high-tolow transition. This transition is a logical 1. This scheme is called Manchester encoding and was used for classic Ethernet.
The downside of Manchester encoding is that it requires twice as much bandwidth as NRZ because of the clock, and we have learned that bandwidth often matters. A different strategy is based on the idea that we should code the data to ensure that there are enough transitions in the signal. Consider that NRZ will have clock recovery problems only for long runs of 0s and 1s. If there are frequent transitions, it will be easy for the receiver to stay synchronized with the incoming stream of symbols.
As a step in the right direction, we can simplify the situation by coding a 1 as a transition and a 0 as no transition, or vice versa. This coding is called NRZI (Non-Return-to-Zero Inverted), a twist on NRZ. The popular USB (Universal Serial Bus) standard for connecting computer peripherals uses NRZI. With it, long runs of 1s do not cause a problem.
A well-known code to do this is called 4B/5B. Every 4 bits is mapped into a5-bit pattern with a fixed translation table. The five bit patterns are chosen so that there will never be a run of more than three consecutive 0s. The mapping is shown in Fig. 2-21. This scheme adds 25% overhead, which is better than the 100% overhead of Manchester encoding. Since there are 16 input combinations and 32 output combinations, some of the output combinations are not used. Putting aside the combinations with too many successive 0s, there are still some codes left. As a bonus, we can use these nondata codes to represent physical layer control signals. For example, in some uses ‘‘11111’’ represents an idle line and ‘‘11000’’ represents the start of a frame.
4B/5B mapping
An alternative approach is to make the data look random, known as scrambling.
In this case it is very likely that there will be frequent transitions. A
scrambler works by XORing the data with a pseudorandom sequence before it is
transmitted. This mixing will make the data as random as the pseudorandom sequence
(assuming it is independent of the pseudorandom sequence). The receiver
then XORs the incoming bits with the same pseudorandom sequence to recover
the real data. For this to be practical, the pseudorandom sequence must be easy to
create. It is commonly given as the seed to a simple random number generator.
Scrambling is attractive because it adds no bandwidth or time overhead. In
fact, it often helps to condition the signal so that it does not have its energy in dominant frequency components (caused by repetitive data patterns) that might
radiate electromagnetic interference. Scrambling helps because random signals
tend to be ‘‘white,’’ or have energy spread across the frequency components.
However, scrambling does not guarantee that there will be no long runs. It is
possible to get unlucky occasionally. If the data are the same as the pseudorandom
sequence, they will XOR to all 0s. This outcome does not generally occur with a
long pseudorandom sequence that is difficult to predict. However, with a short or
predictable sequence, it might be possible for malicious users to send bit patterns
that cause long runs of 0s after scrambling and cause links to fail. Early versions
of the standards for sending IP packets over SONET links in the telephone system
had this defect (Malis and Simpson, 1999). It was possible for users to send certain
‘‘killer packets’’ that were guaranteed to cause problems.
No comments:
Post a Comment