Information Theory and Coding
Information theory gives a mathematical way to reason about uncertainty and communication. Coding turns those ideas into representations that compress predictable structure or add redundancy against errors. These are different jobs: reducing expected length and improving reliability require different evidence.
Start by identifying the source symbols, their probability model, the channel or storage error model, and what the receiver must reconstruct. Without those assumptions, a claim about bits per symbol or error correction can sound precise while answering the wrong question.
TL;DR
- Measure information relative to a stated probability model.
- Separate source coding for compression from channel coding for reliability.
- Count codebooks, headers, padding, and framing in real storage results.
- Distinguish detection, correction, and authenticity.
- Interpret asymptotic limits with their model and finite-resource assumptions.
Quick Example
This complete Python illustration uses a fictional four-symbol sample with probabilities one-half, one-quarter, one-eighth, and one-eighth. The chosen prefix code matches those probabilities exactly.
The round trip passed with entropy 1.75 bits per symbol and 28 encoded payload bits for 16 symbols. Codebook/framing overhead is excluded. An even-parity example detected one flipped bit and missed the demonstrated two-bit flip. It is not a compressor format, general decoder, error-correcting implementation, cryptographic check, or measured communication link.
Core Concepts
Information and entropy
For an event with probability p, information content is -log2(p). Entropy is the probability-weighted average information content of the modeled source. Its units are bits per source symbol when using base two. MIT information and entropy notes
Source coding
A prefix code lets a receiver identify a codeword without waiting for a later codeword boundary. Huffman coding constructs a useful probability-dependent prefix code; a complete format still needs agreement about the code and framing. MIT source coding notes
Channel coding
Redundancy can support reconstruction under an error model. Detection and correction have different limits, and burst errors can violate an independent-bit model. MIT error-correction notes
Follow every bit in the worked example
The sample has eight As, four Bs, two Cs, and two Ds. The assigned code lengths are one, two, three, and three bits. The payload therefore contains 8×1 + 4×2 + 2×3 + 2×3 = 28 bits. Dividing by 16 gives the same 1.75 bits per symbol as the empirical entropy for this specific distribution.
That equality follows from the chosen probabilities and code. It does not mean every Huffman code reaches entropy exactly, or that a small real file achieves this ratio. A file format must convey or otherwise agree on the codebook and include whatever framing is needed.
The decoder accumulates bits until it sees a complete codeword. The example asserts that the provided payload ends at a codeword boundary and reconstructs the source. It assumes the illustrated alphabet and clean bit string; a general decoder must handle malformed, truncated, or resource-exhausting input.
If the source changes, the estimated symbol frequencies can stop representing future messages. Evaluate the code on the distribution you need to serve, or choose an adaptive format with a clearly defined update protocol. Do not use a training sample’s entropy as a guarantee about an unrelated source.
Correlations also matter. Counting individual symbols can miss predictable sequences. A model with additional context can describe a different information rate, while adding its own representation and computation costs.
Keep compression, reliability, and security distinct
This is a conceptual comparison, not a claim that one primitive covers all five jobs. The parity example has two valid outcomes for different error patterns: one flip changes parity; two selected flips preserve it. A check passing therefore does not establish that the original bits arrived unchanged.
A correction scheme needs a declared error model and decoding rule. Consider a repetition illustration: three copies with majority voting can recover a bit if at most one copy flips, while more errors can produce a wrong majority. The assumptions belong beside the claim, not in an unrelated disclaimer.
Linear block codes represent messages and parity relationships over a finite field. Their code rate relates useful message bits to transmitted codeword bits. The decoder and the supported error patterns determine what can be recovered. MIT block-code and syndrome notes
Do not present a CRC or parity check as protection against an adversary who can deliberately change both data and check value. Accidental-error detection and cryptographic authenticity answer different questions.
Interpret limits through the model
A statement about an average source length depends on the source distribution and allowed code class. A communication limit depends on the channel and acceptable error behavior. Keep those mathematical assumptions attached when translating a theorem into an engineering decision.
Separate an asymptotic existence result from a practical finite-message implementation. A real codec has bounded memory, latency, block length, processing cost, and implementation complexity. The available construction may not reach an ideal limit at the required operating point.
Measure complete files or messages. Include headers, codebooks, padding, framing, checks, and any retransmission cost relevant to the task. Very small messages can expand even when their payload has compressible structure.
For a noisy link, characterize errors with approved measurements rather than assuming independent flips. Bursts, dropped blocks, synchronization loss, and varying conditions can call for different coding and recovery choices. Retain observed conditions and uncertainty in the evaluation record.
Start with a clean round trip and a few deliberate corruptions. Confirm expected rejection or correction before measuring size or throughput. When a corruption is accepted, understand whether that behavior is inside the design’s limits or an implementation defect.
Best Practices
Name the probability model
State the symbols, distribution, context, and whether the values are measured or illustrative. Revisit the model when the source changes.
Count the complete representation
Include format overhead and decoding requirements. Compare exact reconstruction and total size together.
Exercise error patterns
Test supported correction cases and known undetected or uncorrectable cases. Define what the receiver does when confidence is insufficient.
Common Mistakes
Bad: Entropy is the size every file will have after compression.
Correct: Treat it as a modeled quantity and measure actual format overhead and source behavior.
Bad: Parity passing proves the bits are unchanged.
Correct: Document undetected patterns and use the appropriate integrity mechanism for the threat model.
Bad: More redundancy automatically means adequate correction.
Correct: Choose a code, decoder, and error model with verified behavior.
FAQ
Why is the example exactly 28 bits?
Its declared symbol counts and code lengths sum to 28 payload bits. This excludes the codebook and framing.
Can compression and correction be combined?
Yes, as distinct stages with a defined interface and complete overhead calculation. Verify error propagation and recovery across the combined format.
Does the example measure channel capacity?
No. It demonstrates source arithmetic and a parity limitation without a real channel or capacity experiment.
Related Topics
- Binary Data and Character Encoding — Representation, bytes, and character boundaries.
- Probability and Linear Algebra for Computing — Probability models and linear operations.
- Networking — Communication paths and protocol context.