1.2Information theory & encoding

Communication and storage systems must satisfy two opposing requirements at once: making data "as small as possible" and making data "as accurate as possible." Encoding/compression techniques address the first, and error detection/correction techniques address the second. This section covers the theoretical starting point—information content—through to the concrete encoding schemes used in practice.

1.2.1Information content and entropy

• Information content is the "degree of surprise" of an event, computed as log2(1/p) bits from its probability p. A less probable event carries more information.
• Entropy is the weighted average of the information content across every possible event from a source (H = sum of p_i * log2(1/p_i)). It represents the overall uncertainty (average information) of the source, and this value is the theoretical lower bound on the shortest achievable average codeword length.

1.2.2Huffman coding and data compression

• Huffman coding is the representative variable-length coding scheme that minimizes average codeword length by assigning short codes to frequent symbols and long codes to rare ones. Its prefix-free property—no code is a prefix of another—guarantees the decoded boundaries are unambiguous.
• Construction procedure: repeatedly merge the two lowest-frequency nodes to build a binary tree (a Huffman tree); the path from the root (left=0, right=1) becomes each symbol's code. The more skewed the frequency distribution, the higher the compression ratio.

1.2.3Error detection & correction (parity, CRC, Hamming codes)

• A parity bit is a single check bit that makes the count of 1s in the data even (or odd). It can detect a single-bit error, but cannot pinpoint the error location or detect two simultaneous bit errors (an even number of bit errors goes unnoticed).
• CRC (Cyclic Redundancy Check) treats the data as a polynomial and appends the remainder of dividing it by a generator polynomial as a check code. It has much stronger detection of burst errors (multiple consecutive bit errors) than parity, and is widely used in network communication and storage.
• A Hamming code places multiple check bits so that it can not only detect an error but also pinpoint the error location and automatically correct it (single-bit error correction). It is used in settings such as ECC memory where correction, not just detection, is required.

Suppose a communication system sends four symbols A, B, C, D with probabilities A=0.5, B=0.25, C=0.125, D=0.125. First, computing entropy: H = 0.5×log2(2) + 0.25×log2(4) + 0.125×log2(8) + 0.125×log2(8) = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 0.5+0.5+0.375+0.375 = 1.75 bits/symbol, which is the theoretical shortest average codeword length. Applying Huffman coding: first merge the two lowest-frequency symbols C and D (0.125 each) into a node of weight 0.25, then merge that with B (0.25) into a node of weight 0.5, and finally merge with A (0.5) to complete the tree. This tree yields the codes A=0 (1 bit), B=10 (2 bits), C=110 (3 bits), D=111 (3 bits), giving an average codeword length of 0.5×1+0.25×2+0.125×3+0.125×3=1.75 bits—exactly matching the entropy lower bound (this example is a special case where the frequencies are powers of 1/2, so the theoretical value is achieved exactly). Next, consider countermeasures for transmission errors: for file transfers where detection alone suffices, choose CRC (strong against burst errors); for memory systems where correction is mandatory, choose a Hamming code (auto-corrects single-bit errors)—a practical decision driven by whether detection alone is enough, or correction is required.

1.2.4Character encoding

• A character code maps characters to bit patterns. Unicode is the standard that represents every character in the world in a single character set, and UTF-8, one of its encodings, is a widely adopted variable-length encoding that represents ASCII characters in a single byte while still supporting multi-byte characters.

1.2.5Section summary

• Information content = log2(1/p); entropy = the probability-weighted average of information content (theoretical shortest average codeword length)
• Huffman coding assigns shorter codes to more frequent symbols (variable-length, prefix-free) to minimize average codeword length
• Parity = detection only, CRC = strong burst-error detection, Hamming code = detection plus auto-correction—choose based on the requirement