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 levels 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 1sdo not cause a problem. Of course, long runs of 0s still cause aproblem that we must fix. If we were the telephone company, we mightsimply require that the sender not transmit too many 0s. Older digital telephone lines in the U.S., called T1 lines, did in fact require that no more than 15 consecutive 0s be sent for them to work correctly. To fix the problem we can break up runs of 0s by mapping small groups of bits to be transmitted so that groups with successive 0s are mapped to slightly longer patterns that do not have too many consecutive 0s. A well-known code to do this is called 4B/5B. Every 4 bits are mapped into an 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. 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 non-data 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. An alternative approach is to make the data look random, known as scrambling. In this case, there will likely 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. 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.