Programmers are forever coming up with clever ways to represent data more compactly. Like storing the entire English dictionary using a trie; or compressing fax transmissions 10x using run-length encoding; or storing thousands of values in a few kilobytes using probabilistic data structures. I might not come up with one of these schemes myself but when I read how they’re implemented I’m usually able to come away with an understanding of how they work, even if they feel a bit magical when you first hear about them.
I was on a random Wikipedia walk when I stumbled on 8 bit/10 bit encoding. My first reaction was complete bafflement. In what world can you represent 10 bits with just 8 bits? Are you tapping into some hidden quantum realm or something? But actually it’s the opposite: the encoding uses 10 bits to represent 8 bits of data. If anything that’s more interesting. Of course you can do it–no one wonders how you can fit 8 numbers into 10 slots–but why?
The answer is a reminder that I don’t really know much about the physical world of computers. It largely boils down to the fact that it’s problematic to transmit lots of 1s or 0s in a row. But sometimes we’re going to do that! If someone writes an email that has a bunch of consecutive @ signs (ASCII 64, 01000000), then we’re going to send tons of zeros over the wire. The issue with lots of 1s and 0s is that it causes problems with the voltage in the line, and problems with clock synchronization.
The voltage drift is called DC bias. Even after reading the article on it, I was a little lost.
The clock problem is easier for me to understand. When you’re receiving a message, you use a clock to decide when to sample the voltage to see if it’s high (1) or low (0). I imagine it like a metronome and on each tick you read a bit. But, of course, clocks are hard! It’s easy for them to drift and get out of sync. So you use transitions between 0 and 1 to re-synchronize (see “Clock Recovery”). If one of those transitions happens before your metronome ticks, you know that you’re running a little behind and can adjust. If you don’t have those transitions (because lots of 0s are being transmitted), then your clock can drift. When that happens the data is going to be wrong because you’re reading the voltage at the wrong time.
One solution to the problem of too many 1s or 0s is 8b/10b encoding. Because you have extra bits, you can use them to create multiple representations of the underlying bytes. Some of them are already balanced enough and you can send them as-is. For others you create different representations then you alternate between them to achieve balance between the number of 1s and 0s transmitted. In fact, 8b/10b makes that guarantee: if you send at least 20 bits, you will have practically the same number of 1s and 0s.
8b/10b encoding is used for some forms of Gigabit ethernet, USB 3.0, DisplayPort, and a variety of other protocols. Other systems use related line codes for similar reasons: Fast Ethernet (100BaseT) uses 4B5B; 10 Gbps Ethernet uses 64b/66b.
I enjoy living in software land where I don’t spend a lot of time thinking about these problems but it was fascinating to learn about.