21.9. Finding Optimal Encoding

So, when we communicate, we have to transmit information from one place to another place. So, we might be working in some language like English, Hindi or whatever, but if we're using computers for example, to transmit our data, we know that they must send this information in binary strings. So, our typical goal is to take an alphabet, and then encode it over strings of 0 and 1, so that at the other end, we can decode and recover the message.

This chunk introduces the concept of encoding messages for communication, particularly through computers. When we send messages using computers, they do not understand languages directly; instead, they convert our messages into a format of binary strings - sequences comprising of 0s and 1s. This is essential for transmitting data effectively over digital mediums.

Think of sending a text message or email. You type your message in English, but your device converts that message into binary code, which represents the text as a series of 0s and 1s that can be sent over the internet.

So, if you have say the 26 lower case letters a to z, then it is easy to see that we need to; if you want to encode each letter as a fixed sequence of 0’s and 1’s by fixed length, then we will need to use 5 bits for each letter, because if you use only 4 bits, we can only get 16 different combinations, with 5 bits we can get 32 different combinations.

Here, the chunk discusses the limitations of using fixed-length binary encoding. To represent each of the 26 letters in the alphabet in binary, if we want to use a uniform length for each encoding, we need 5 bits because 4 bits only allow for 16 unique combinations. With 5 bits, we gain 32 combinations, enough to represent all letters uniquely.

Imagine a combination lock with 4 dials. Each dial can represent 10 numbers (0-9), which gives us 10,000 possible combinations. If we added another dial, we greatly increase our number of combinations, making it much harder for someone to guess your code.

So, this brings us to the idea of having a variable length encoding, where we use different strings of different length for different letters in the alphabet. So, one of the most famous examples of the variable length encoding is the classical Morse code, which is developed by Samuel Morse from the telegraph.

This chunk introduces the concept of variable length encoding, where different letters use different lengths of binary strings. Morse code is cited as an example, illustrating how this system assigns shorter encodings to more frequently used letters while making encoding more efficient.

Consider how in texting, some people use abbreviations for common words ('u' for 'you', '2' for 'to'). This is similar to variable length encoding: frequently used words are represented with fewer characters, thus saving time and space.

So, in order to make a variable length code an unambiguous decodable, we need what is called a prefix code. When we read through a sequence of 0’s and 1’s, we should be unambiguously clear whether we have read a letter or there is more to read.

This chunk discusses the necessity of prefix codes for ensuring clarity in decoding variable length codes. A prefix code ensures that when a sequence is read, there’s no confusion about when one letter ends and another begins, crucial for effective decoding without ambiguity.

Imagine listening to music and repeating words smoothly. If you slur together words too closely, it can be hard to understand. Likewise, if encoding is ambiguous, the decoder won't know when one letter ends and another starts, leading to confusion.

So, our goal is to find optimal prefix codes. So, we need to talk about what we mean by optimality. So, remember we said that our goal is to assign shorter codes to more frequent letters. So, somehow we have to determine what are more frequent and less frequent letters.

This chunk outlines the goal of finding optimal prefix codes, emphasizing the need to assign shorter codes to more frequently used letters to minimize total encoding length, ultimately leading to more efficient data transmission.

Consider a store selling fruits. If apples are sold much more than oranges, it makes sense to keep apples at the front (shorter time to gather), just like shorter codes for more frequently used letters in encoding to increase efficiency.

So, people have measured the frequency of the occurrence of each letter in different languages. This is a very language-specific thing. So, you take a large body of text in a particular language, and you count the number of a’s, b’s, c’s, d’s, and e’s.

This chunk emphasizes the importance of frequency analysis for determining optimal encodings. By analyzing a large body of text, one can observe how often each letter occurs, which directly informs how to allocate encoding lengths more efficiently.

Think of a website that tracks which articles are read most frequently. By analyzing the data, they can promote popular articles more effectively. Similarly, knowing which letters are used more often helps prioritize encoding efficiency.

So, now we have a message, it consists of some n symbols. So, we have M1, M2 up to Mn. Now, we know that if I take a particular letter x, then fx fraction of these are x, then n * fx gives how many times x appears in the message.

This chunk presents a method for calculating the average number of bits required to encode a message based on the frequency of each letter. By multiplying the frequency of each letter with the length of its encoding, one can sum these values to determine the total encoding length.

Consider a classroom of students taking a test. If a specific question appears more often (like a pop quiz), the teacher knows to give that question more attention when reviewing, just as encoders prioritize letters based on frequency.

Now, a very specific kind of prefix code is the fixed length code, where just by the fact that every code is fixed length, I know exactly where each letter is.

This chunk contrasts fixed length codes and variable length codes. With fixed length encoding, you use the same number of bits for every letter, which simplifies decoding but may not be as efficient as variable length codes that adapt based on letter frequency.

Think of a puzzle with pieces of equal size. If all pieces fit together the same way (fixed), it’s straightforward but can be less interesting compared to uniquely shaped pieces that fit efficiently (variable).

To get to this, it is useful to think of these encodings as binary trees, so in a binary tree, I can interpret directions as 0 and 1, so typically left is 0 and right is 1.

This chunk describes how encoding can be visualized as a binary tree, where each left turn represents a '0' and each right turn represents a '1'. This representation helps in organizing letters based on frequency and lengths so that decoding is readily manageable.

Imagine navigating a maze. Going left at certain junctions leads you to specific destinations. Similarly, in the binary tree, each path leads to a specific letter, which makes decoding systematic and efficient.

In such a tree, if it is optimal, every node will either have no children or will be a leaf or it will have two children. So, this is what we call a Full. Every optimal tree is full.

This chunk explains key properties of optimal encoding trees. Specifically, each node must either have two children or none, ensuring that encoding paths properly terminate without confusion and maintain efficiency in decoding.

Think of a family tree. Each parent has children (two), or they're childless. This symmetry ensures each branch is properly defined, similar to branching in optimal encoding trees, which must be structured for clarity.

--