What is prefix code?

A prefix code is a type of variable-length code used in data compression where no codeword is a prefix of another. This ensures unambiguous decoding: when reading a sequence of bits, the decoder can uniquely identify the end of each codeword without needing separators.

Key properties:

• Uniqueness: No codeword is a prefix of another (e.g., 01 and 010 cannot coexist).
• Efficiency: Shorter codewords are assigned to more frequent symbols (e.g., Huffman coding).
• Applications: Used in Huffman coding, run-length encoding, and network protocols (e.g., Elias gamma coding).

Example: In a binary prefix code, 0 and 10 are valid, but 1 and 10 are invalid because 1 is a prefix of 10. This property guarantees lossless reconstruction of original data.