21.8. Fixed Length Codes

In the fixed length encoding, all symbols are represented using the same number of bits. For example, if there are 26 letters from a-z, we would need 5 bits to represent them because 2^5 = 32, which covers all combinations needed for 26 letters.

Fixed length codes use a uniform number of bits to represent each symbol or character without variation. For example, with 5 bits, we can uniquely represent 32 different symbols, which is more than sufficient for the 26 letters of the English alphabet. This consistency simplifies encoding and decoding since every character occupies the same amount of space.

Imagine a classroom where every student has a labeled desk. If each desk is the same size and shape, you can easily see how many desks you have and where each student sits (like using 5 bits for encoding). However, if some desks were smaller or larger, it would be harder to keep track of how many students you can fit in the room (like variable-length codes).

While fixed length codes simplify encoding and decoding, they can be inefficient. For example, if a few letters are much more common than others, allocating the same number of bits to less common letters wastes space.

Fixed length codes can lead to inefficiencies, particularly when there are significant differences in the frequency of symbol use. For instance, if the letter 'e' appears much more frequently than 'x', both using the same number of bits means that 'e' is not being transmitted as efficiently as possible. This inefficiency can lead to more data bits being sent than necessary, which is not ideal in data transmission.

Think of packing a suitcase with both large and small items. If you only use large containers (fixed length), you may waste a lot of space with smaller items that don’t need such big containers. It would be more efficient to use various container sizes based on the item size (variable length) to optimize packing.

Optimizing data transmission often involves using variable length encoding instead of fixed length encoding. Variable length encoding assigns shorter codes to more frequently used characters, thereby reducing the overall amount of data transmitted.

Variable length encoding allows for a flexible approach where frequently used symbols are encoded with fewer bits, while less frequent symbols can utilize more bits. This results in a more efficient use of bandwidth, as common symbols take up less space, and rare symbols take up more, thereby achieving a balance based on usage frequency.

Picture an online shopping website where bestsellers (like popular clothing items) are in high demand – you might want to put them on special sale (short encoding). Less popular items may be given plain prices. This approach ensures the majority of your sales (common items) are quickly accessible, while other items can still be offered at a higher complexity and length (longer encoding).

To ensure that variable length codes are uniquely decodable, they must adhere to the prefix property. This means no code can be the prefix of another, allowing for immediate identification of the end of a code.

The prefix property is a crucial aspect of variable length coding. It prevents ambiguity during decoding by ensuring that once a code fragment is read, it indicates a complete symbol without overlapping with the beginning of another symbol. This property ensures that each encoded symbol can be distinctly recognized and makes decoding straightforward.

Consider the difference between stopping at a street with a 'STOP' sign (prefix) versus one that has multiple 'STOP' signs at different distances. If all are treated the same, drivers could get confused about which one they need to stop at, just as code interpretations could get confused without the prefix property.

Encoding symbols can be visualized using binary trees, where each path from the root to a leaf corresponds to a unique binary code. This visualization helps in understanding how variable length encodings work.

Binary trees work as an effective tool to represent the encoding process. Each left turn might signify a '0' and each right turn signifies a '1', leading to a unique path for each symbol. The tree can help maintain the prefix property by ensuring that once you reach a leaf node, you have a complete and distinct encoded symbol.

Imagine a library where each aisle represents a different genre (like paths in a tree). When you pick a book from a specific aisle, you know you've reached your destination. Similarly, as you navigate through the binary tree, reaching a leaf node means you've arrived at a specific encoded symbol.

--