MacKay 2003 - Information Theory, Chapter 1

What is information theory? It’s the science of how we transmit and compress information (bits).

I really liked this framing that storing information is also a form of transmission but through time rather than space.

Generally, if you want more reliable transfer over noisy channels (sometimes your bits flip randomly), then there are two approaches. You can either buy more reliable hardware, or you can try to solve this problem through better software and ideas. Information theory is the latter.

As a simple example, let’s that I’m trying to communicate a string of 0s and 1s to someone else. One simple augmentation is that I can repeat each bit I want to send 3 times. 0 becomes 000, 1 becomes 111. Now if a single bit gets flipped randomly in a triplet, a person is able to detect that mistake and correct it.

Obviously while we’re getting a lower error rate, we sacrifice that by also getting lower throughput. Our bandwidth is exactly 1/3 what it used to be! You can also do cleverer things by encoding with Hamming Encodings where rather than trying to get per bit redundancy, you start trying to add redundancy to blocks of bits. For the simplest approach, you can take groups of 4 bits, add 3 parity bits, and suddenly you’re immune to any single bit flip while not even doubling the amount of bits you’re sending.

Not yet certain, but I’m pretty sure that the longer the blocks you’r encoding, the more efficient it becomes.

One of the most stunning results in computer science (math?) is the fact that this trade-off isn’t zero-sum. Intuitively, it seems that if you want to approach 0 error, then you have to keep adding more and more bits to the original thing you want to send. Basically, there is a set trade-off between the rate at which you can send information and the error rate. In reality, there is a non-zero rate where you can send information for an arbitrary error loss. This is insane, and even just from the little teaser of this theorem in the first chapter, I’m excited to dig in more.