Uniquely Decodable Codes

In the digital world, all information—from simple commands to complex data streams—must be translated into a language machines can understand, typically a sequence of 0s and 1s. The primary challenge in creating this language is not just assigning unique binary words to concepts, but ensuring that any sequence of these words can be decoded without ambiguity. A simple mix-up, where a string of bits could mean two different things, can lead to system failure. This article addresses the fundamental problem of how to mathematically guarantee that a code is free from such ambiguity.

This exploration will guide you through the principles that govern the construction of reliable codes. In the first chapter, "Principles and Mechanisms," we will journey through a hierarchy of code types, from the barely functional to the elegantly efficient, and uncover the Kraft-McMillan inequality—a simple yet profound mathematical law that acts as a universal gatekeeper for code design. Following this, the chapter on "Applications and Interdisciplinary Connections" will reveal how this theoretical rule becomes a practical engineer's compass, a physicist's lens for viewing physical constraints, and a theorist's key to understanding the ultimate limits of data compression as defined by information theory.

Imagine you're trying to invent a new language, not for speaking, but for machines. Your alphabet is brutally simple: just 0s and 1s. Your task is to create a dictionary that translates a set of concepts—say, A, B, C, and D—into this binary language. How do you choose the 0-and-1 words for your dictionary? You might think the only goal is to use the shortest words possible. But a far more subtle and crucial property must be achieved first: clarity. If your language is to be of any use, it must be free from ambiguity. This quest for clarity takes us on a beautiful journey through a hierarchy of codes, culminating in a wonderfully simple mathematical law that governs them all.

Let's start with the most basic rule you'd want for your new dictionary. If you have two different concepts, say A and B, you should probably give them two different binary words. If A is 01 and B is also 01, your language is useless from the get-go. A code that follows this simple rule—one concept, one unique codeword—is called a ​​non-singular code​​. It’s the absolute minimum requirement for a code to be functional.

But is non-singular enough? Let's consider a slightly more clever, non-singular dictionary:

• s₁ → 10
• s₂ → 0
• s₃ → 1
• s₄ → 100

All the codewords are different, so it's non-singular. Now, imagine your machine receives the message 100. What does it mean? It could be the single codeword for s₄. Or, it could be the codeword for s₃ (1) followed by the codeword for s₂ (0) and then... wait, that doesn't quite work. Let's try another example, this time from:

• x₁ → 10
• x₂ → 00
• x₃ → 1
• x₄ → 001

Again, all codewords are distinct. Now imagine the message 001. Is it x₄? Or is it x₂ (00) followed by x₃ (1)? The receiver has no way of knowing. The message is ambiguous. This code, while non-singular, fails a more stringent test. It is not ​​uniquely decodable​​. A code is uniquely decodable if any sequence of concatenated codewords has only one possible interpretation. This property is non-negotiable for reliable communication.

This reveals a subtle truth: ambiguity can hide not in the individual words, but in the way they stick together. So, how can we guarantee unique decodability? One way is to enforce an even stricter rule. This leads us to the "gold standard" of coding: the ​​prefix code​​ (also called an ​​instantaneous code​​). The rule is simple and elegant: no codeword is allowed to be the prefix (the beginning) of any other codeword.

For example, the code {0, 10, 110, 111} is a prefix code. 0 isn't the start of any other codeword. 10 isn't the start of 110 or 111. It's like a phone system where no one's number is just the beginning of someone else's longer number. The moment you finish dialing a valid number, the call connects. You don't have to wait to see if more digits are coming. This is why it’s called "instantaneous"—decoding can happen in real-time without looking ahead.

All prefix codes are, by their very nature, uniquely decodable. If you're reading a stream of bits, you just read until you match a codeword in your dictionary. Since no codeword is a prefix of another, the first match you find must be the correct one. There's no ambiguity.

This gives us a clear hierarchy of codes, a series of nested sets, each more restrictive and well-behaved than the last:

Are there codes that are uniquely decodable but are not prefix codes? Yes, and they are quite instructive! Consider the code {0, 01, 11}. This is not a prefix code because the codeword 0 is a prefix of 01. So when a decoder sees a 0, it can't immediately decide if the codeword is 0. It has to peek at the next bit. If the next bit is a 1, the codeword must have been 01. If the next symbol is a 0 or another 1, the first codeword must have been just 0. Although not instantaneous, you can always figure it out by looking ahead a bit. The ambiguity is temporary and always resolvable. Such codes are uniquely decodable, but they require more complex decoding logic and memory.

So we have a wish list for our code. We'd like it to be uniquely decodable, preferably a prefix code. And we'd also like to be clever about assigning lengths—perhaps using short codewords for common symbols and long ones for rare symbols to save space, the very essence of data compression.

This brings us to a fundamental question. Suppose we've decided on a set of desired codeword lengths, say $\{l_1, l_2, l_3, \dots, l_M\}$. How do we know if it's even possible to construct a uniquely decodable code with these lengths? Do we have to go through the painful trial-and-error of trying to build one?

Amazingly, the answer is no. There is a simple, powerful, and profoundly beautiful piece of mathematics that tells us the answer instantly: the ​​Kraft-McMillan inequality​​.

The theorem states that for a set of codeword lengths $\{l_i\}$ to correspond to a uniquely decodable code using a $D$-symbol alphabet (for binary, $D=2$), the following condition is both necessary and sufficient:

This little formula is like a magic ruler. Let's think about what it says. You can imagine you have a total "coding budget" of 1. Each potential codeword of length $l_i$ has a "cost" of $D^{-l_i}$. For a binary code ($D=2$), a codeword of length 1 costs $2^{-1} = 1/2$. A codeword of length 2 costs $2^{-2} = 1/4$. A codeword of length 3 costs $2^{-3} = 1/8$, and so on. Shorter codewords are far more "expensive" because they use up a larger chunk of your budget. The inequality simply says that the total cost of all the codewords in your dictionary cannot exceed your budget of 1.

The power of this inequality is twofold. First, it's a gatekeeper. If you propose a set of lengths and the sum is greater than 1, the theorem says, "Stop. It's impossible." No amount of cleverness will ever allow you to construct a uniquely decodable code with those lengths. You have overspent your budget, and there simply isn't enough "coding space" to fit your words without them tripping over each other and creating ambiguity.

Second, and more wonderfully, if the sum is less than or equal to 1, the theorem guarantees that a prefix code (and thus a uniquely decodable one) with those lengths exists. You are free to go and find it.

Let's see it in action. An engineer proposes a binary code for five signals with lengths $\{2, 3, 3, 4, 4\}$. Is this possible? Let's use our magic ruler.

Since $K = 5/8$, which is less than 1, the inequality is satisfied. We can declare with absolute certainty that a uniquely decodable code with these lengths can be constructed.

The Kraft-McMillan inequality gives us more than just a yes/no answer. The actual value of the sum tells us something about the code itself.

What if the sum is exactly equal to 1? This means you have used your budget perfectly, with nothing to spare. Such a code is called a ​​complete code​​. You have packed the coding space so efficiently that you cannot add even one more codeword of any length without violating the inequality. Complete codes are, in a sense, optimally dense.

What if, as in our example above, the sum is strictly less than 1? For the lengths $\{2, 3, 4, 5, 5\}$, the sum is a mere $1/2$. This tells us the code is ​​not complete​​. There is "money left in the bank." This leftover budget means there is room to improve or expand the code. You could either add new codewords for new symbols, or you might be able to shorten some of the existing codewords, making your code even more efficient.

This framework is so powerful it even works for scenarios that seem impossible at first glance. What if you have a source that can generate a countably infinite number of different symbols? Can you possibly design a uniquely decodable dictionary for an infinite vocabulary? Intuition might scream no. Where would you find the space for an infinite number of binary words?

But mathematics gives a different, more sublime answer. Let's see if we can assign codeword lengths $l_k = k+1$ for symbols $s_k$ where $k=1, 2, 3, \dots$ all the way to infinity. We apply the Kraft-McMillan ruler, but this time it's an infinite sum:

This is a classic geometric series with a first term of $1/4$ and a common ratio of $1/2$. And as students of calculus know, this series converges to a finite value:

The sum is $1/2$. Since $1/2 \le 1$, the inequality holds! The breathtaking conclusion is that, yes, it is entirely possible to construct a uniquely decodable code for a source with an infinite alphabet. This is a testament to the fact that the simple, practical question of building an unambiguous language is deeply connected to the beautiful and profound mathematics of infinite series. The principles that ensure clarity in our digital world are the very same principles that govern the infinite.

Having understood the principles that govern uniquely decodable codes, we might be tempted to file them away as a neat piece of mathematics. But to do so would be to miss the point entirely! The Kraft-McMillan inequality is not merely a theorem; it is a fundamental law of information. Like a conservation law in physics, it tells us what is possible and what is impossible in the world of data. It is a powerful lens through which we can view problems not only in computer science and engineering but also in more abstract domains. It provides a universal budget for brevity, a strict accounting of how efficiently we can represent information. Let's embark on a journey to see this principle at work, to discover its surprising reach and inherent beauty.

Imagine you are an engineer designing a communication protocol. Whether for a simple autonomous rover, an industrial control system, or a sophisticated satellite, your goal is to transmit instructions and data reliably and efficiently. Efficiency often means using short codes for common messages and longer codes for rare ones. But how short can you make them? Can you assign a 1-bit code to every command? Your intuition says no—you'd run out of symbols immediately. The Kraft-McMillan inequality formalizes this intuition and turns it into a rigorous design tool.

Think of the inequality, $\sum_{i} D^{-l_i} \le 1$, as a "coding budget." The number 1 on the right side represents your total available budget. Each codeword you create has a "cost," which is $D^{-l_i}$. Notice something interesting: shorter codewords (small $l_i$) are far more "expensive" than longer ones. For a binary code ($D=2$), a codeword of length 1 costs $2^{-1} = 0.5$, half your entire budget! A codeword of length 2 costs $2^{-2} = 0.25$, and one of length 10 costs a minuscule $2^{-10} \approx 0.001$.

With this analogy, designing a code becomes an exercise in budget management. Suppose a robotics team wants to use a binary code for five different rover commands, proposing lengths of $\\{2, 2, 3, 3, 3\\}$. Do they have enough budget? We can simply add up the costs: two length-2 words cost $2 \times 2^{-2} = 0.5$, and three length-3 words cost $3 \times 2^{-3} = 0.375$. The total cost is $0.5 + 0.375 = 0.875$, which is less than 1. The budget holds! This tells the engineers, with mathematical certainty, that a uniquely decodable code with these lengths can be constructed, even before they've figured out what the actual 0s and 1s will be.

Conversely, what if a different team, designing a special keyboard, gets too ambitious? They want to encode seven key presses with lengths $\\{2, 2, 3, 3, 3, 3, 3\\}$. Let's check their budget. The two length-2 words cost $2 \times 2^{-2} = 0.5$. The five length-3 words cost $5 \times 2^{-3} = 0.625$. The total cost is $0.5 + 0.625 = 1.125$. They have overspent their budget! The inequality is violated, and so we know, without any further effort, that their design is impossible. No amount of cleverness can create a uniquely decodable code with those lengths. In fact, if you have two separate, complete codes—codes that use up their entire budget precisely ($\sum 2^{-l_i} = 1$)—you cannot simply merge their codewords into one larger set. The new "budget" sum would be $1+1=2$, a flagrant violation of the law. Such a combined code is guaranteed to be ambiguous.

This budget concept also helps us make design choices. Imagine a data compression scheme that needs to add a special End-of-File (EOF) marker. The existing codewords already consume a portion of the budget, say $\frac{15}{16}$ of it. This means we have $1 - \frac{15}{16} = \frac{1}{16}$ of our budget remaining. What is the shortest, "cheapest" codeword we can add for our EOF marker? Its cost, $2^{-L}$, must be no more than the remaining budget: $2^{-L} \le \frac{1}{16}$. This immediately tells us that $L$ must be at least 4. The shortest possible length is 4. The law not only tells us what is possible, but it guides us toward the most efficient solution.

The "alphabet size" $D$ is just as important. If you insist on using three commands, all of length 1, a binary alphabet ($D=2$) won't work. The cost would be $3 \times 2^{-1} = 1.5$, which is over budget. To afford such short codes, you need a "cheaper" currency. The inequality $3 \times D^{-1} \le 1$ tells us we need an alphabet of at least size $D=3$. Using a ternary alphabet (symbols 0, 1, 2) gives us a larger budget, allowing for more short codewords than a binary alphabet would permit. In fact, if you have a binary code that is "complete" (uses its budget fully, $\sum 2^{-l_i} = 1$), and you switch to a larger alphabet like $D=3$ while keeping the same lengths, the cost of every codeword drops. The total sum $\sum 3^{-l_i}$ will now be strictly less than 1, meaning your once-full code now has room to spare; it is no longer complete.

Here is where the story gets truly interesting. A physicist, upon seeing the Kraft-McMillan inequality, might ask: "Why should length be the only 'cost'?" What if transmitting a '0' and a '1' takes a different amount of time, or energy? This happens in real physical systems. Imagine a channel where sending a '0' takes 1 microsecond, but sending a '1' takes 2 microseconds.

Our simple formula seems to break down. But the underlying principle does not. We can generalize it. The fundamental idea is that there is a "cost" associated with each symbol in our coding alphabet. Instead of summing powers of $D^{-1}$, we find a new base, $\rho$, that captures the physics of the channel. This $\rho$ is the unique positive number that satisfies the equation $\rho^{\text{cost of '0'}} + \rho^{\text{cost of '1'}} = 1$. In our example, this would be $\rho^{1} + \rho^{2} = 1$.

Once we have this magic number $\rho$ (which turns out to be the golden ratio conjugate, $\frac{\sqrt{5}-1}{2}$), it takes the place of $\frac{1}{D}$ in our inequality. A uniquely decodable code is possible if and only if the sum of the costs of its codewords, measured with this new base, is less than or equal to 1. That is, $\sum_{i} \rho^{T_i} \le 1$, where $T_i$ is the total transmission time for the $i$-th codeword.

This is a breathtaking generalization. It shows that the structure of possibility is not tied to the abstract notion of "bits" but to the concrete, physical "cost" of transmission. Whether the cost is length, time, or energy, the same beautiful mathematical constraint holds. It unifies the abstract world of information with the physical world of implementation.

Having established the boundaries of what is possible, the theorist asks a deeper question: What is optimal? Among all possible uniquely decodable codes for a given information source, which one is the best? "Best," in this context, usually means having the minimum possible average codeword length.

This brings us to the famous Huffman codes. The Huffman algorithm is a beautifully simple, greedy procedure for constructing a prefix code that is provably optimal. But what makes a Huffman code special? The Kraft-McMillan inequality tells us that for an optimal binary code, the budget should be fully spent: $\sum 2^{-l_i} = 1$. But this is not enough. Consider the code $\\{0, 01, 11\\}$. The sum of costs is $2^{-1} + 2^{-2} + 2^{-2} = 1$, so it spends its budget perfectly. It is also uniquely decodable. Yet, it can never be a Huffman code, for any set of probabilities. Why? Because the Huffman algorithm has a specific structural signature: the two longest codewords (which correspond to the two least probable symbols) must always be "siblings" in the code tree. They must share the same prefix and differ only in their final bit, like 1010 and 1011. The codewords 01 and 11 in our example are not siblings; they have different parents. This subtle structural flaw, invisible to the Kraft-McMillan inequality alone, disqualifies it from being a Huffman code.

This leads us to the grandest connection of all. Claude Shannon, the father of information theory, proved that for any information source, there is a fundamental limit to compression. This limit is called the ​​entropy​​ of the source, denoted by $H$. It measures the inherent "surprise" or uncertainty in the information. Shannon's source coding theorem states that the average length $G$ of any uniquely decodable code is bounded by the entropy: $G \ge H$.

The entropy $H$ is the ultimate bedrock. No code, no matter how clever, can on average represent the source using fewer bits than its entropy. This connects our practical engineering problem to a concept that feels almost thermodynamic in nature. Now, the final question: can we ever reach this limit? Can we have $G = H$? The theorem says yes, in the ideal case where the symbol probabilities are exact negative powers of two, e.g., $p_i = 2^{-l_i}$. For such a source, a Huffman code with lengths $l_i$ will achieve the entropy bound.

But what about our non-prefix, yet uniquely decodable, code from before: $\\{0, 01, 11\\}$? Its lengths are $\\{1, 2, 2\\}$. If we imagine a source with probabilities perfectly matched to these lengths—$p_1=2^{-1}=0.5$, $p_2=2^{-2}=0.25$, $p_3=2^{-2}=0.25$—we can calculate both its entropy and its average length. Miraculously, they turn out to be exactly the same. Even though it is not an optimal prefix code (a Huffman code for this source would be $\\{0, 10, 11\\}$), it still manages to achieve the absolute Shannon limit for this specific, tailored probability distribution.

So we see the full picture. The Kraft-McMillan inequality is the gatekeeper, separating the possible from the impossible. The structure of optimal algorithms like Huffman's shows us how to build the best prefix codes within those possibilities. And Shannon's entropy provides the ultimate, unbreakable speed limit for all codes. The journey from a simple design check to the fundamental laws of information reveals a deep and beautiful unity, a testament to the power of a single, elegant mathematical idea.