21.6. Encoding Messages

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 are 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 encoded it over strings of 0 and 1, so that at the other end, we can decoded and recover the message.

When we communicate, especially using computers, the information must be transmitted using binary code, which consists of 0s and 1s. This means that any language we speak (like English or Hindi) has to be translated into a code that computers understand, and this coding allows for accurate transmission and recovery of messages at the receiving end.

Think of it like sending a letter with a secret code. You write your message in English, but before sending it, you convert each letter into a number (for example, 'A' = 1, 'B' = 2, etc.), so when your friend receives it, they can decode the numbers back into letters and read your message. This is similar to how computers encode messages using binary.

So, this brings us to the idea 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.

Variable length encoding means that different letters in the alphabet can have codes of different lengths. In Morse code, for instance, common letters like 'E' are represented by a single dot and less common letters have longer sequences. This optimizes communication because more frequently used letters are represented with shorter codes, allowing for quicker transmission.

Imagine a game where you can shout a single letter for your most common words like 'E' (a quick 'dot' sound) or a longer call for the rare ones. This makes your communication more efficient, akin to how Morse code works, where everyday communication is encoded succinctly.

Now, the problem with Morse’s encoding is that it is ambiguous, when you come to decoding. For instance, if we look at the word, the sequence 0 1, then we do not know whether we should interpret each of these as one letter code and get e t e t, all for instance we should think of this as 2 two letter of codes and get a a and so on.

Ambiguity in decoding means that the same sequence of encoded bits can potentially be interpreted in multiple ways. For example, a simple message in Morse code might confuse us as it could read as different letters depending on how we interpret the pauses in signals.

Consider a situation where you hear someone whistle a tune; if they pause at different times, you might think of it as different songs. This is similar to how Morse code might be interpreted differently based on pauses—too much ambiguity can lead to confusion.

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

To eliminate ambiguity in decoding variable-length messages, we use a prefix code. This means that no code should be a prefix of any other code. With a prefix code, once we see a complete encoding for one letter, we know we can't continue to form another letter with that sequence, making decoding clear and straightforward.

Think of a unique set of house numbers in a neighborhood where no house number is a beginning part of another. If you see '20', you immediately know that it's not the start of '200' but a separate house. This is how prefix codes help to distinguish between different encoded letters.

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.

Optimal prefix codes aim to assign shorter codes to letters that appear more frequently in a language. This is important because if we have letters that are often used taking more bits, we end up increasing the amount of data transferred unnecessarily. Finding an optimal encoding thus reduces the overall length of the transmitted message.

Imagine packing for a trip where heavier items take up more space. You should pack lighter items more efficiently so that you can maximize the number of items you can carry without overloading your bag. Similarly, using shorter codes for common letters ensures message efficiency.

So, our goal is to find an assignment capital E which minimizes this quantity. So, in our coding the average efficient is possible.

To minimize the total bits used for encoding a message, we calculate the expected length of the encoding based on letter frequencies. By doing this, we can determine the average number of bits each letter will require, which helps inform how to assign codes optimally.

Think of budgeting your expenses. If you know your most costly items, you would want to find ways to reduce those costs first. Similarly, knowing letter frequencies helps identify how to save the most bits in encoding messages.

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

Using binary trees to represent codes allows us to visualize the encoding process. Each letter corresponds to a position (or leaf) in the tree, where the path taken is defined by moving left (0) or right (1). This structure not only aids in encoding but also ensures the prefix property is maintained, making decoding direct and efficient.

Picture a family tree where each branch represents decisions and leads to different family members. If you follow the branches to find a relative, you clearly know who you’re talking about based on the path you took. This is how binary trees help find encoded letters based on the paths taken.

--