# Information theory

Make code structure and exact expected length visible. Prefix validity and optimality are different questions.

## Definitions

- **Prefix-free code**: No symbol’s codeword is a prefix of another symbol’s codeword.
- **Expected length**: The probability-weighted sum of codeword lengths.
- **Instantaneous decoding**: A prefix-free stream can identify a codeword without waiting for the next symbol.

## Acceptance procedure

1. Require one binary codeword for every declared symbol.
2. Check every ordered pair for the prefix relation.
3. Verify symbol probabilities form an exact rational distribution.
4. Compute the average code length using rational arithmetic.

## Complexity

With n symbols and maximum code length L, naive pairwise prefix checking is O(n²L).

## Common failure

Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length.

## Extensions

Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

## Instances

- KL-FCS-055: A probability-shaped prefix code — Prefix free: yes; Expected bits per symbol: 7/4
- KL-FCS-056: A fixed-length four-symbol code — Prefix free: yes; Expected bits per symbol: 2
- KL-FCS-057: A prefix collision as negative evidence — Prefix free: no; Expected bits per symbol: 3/2

## References

- https://ocw.mit.edu/courses/6-441-information-theory-spring-2010/