# A fixed-length four-symbol code

KL-FCS-056 · Information theory · version 1.0.0

## Problem

Check binary prefix-freeness and compute exact mean codeword length.

## Context

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.

## Checked result

Prefix free: yes; Expected bits per symbol: 2.

The pairwise check reveals every possible prefix collision. Expected length is an exact fraction, avoiding rounding in the acceptance artifact.

## Checker reasoning

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.

## Dataset construction

{
  "family": "information-theory",
  "task": "Check binary prefix-freeness and compute exact mean codeword length.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete codeword-pair check + exact rational average",
  "acceptance": [
    "Require one binary codeword for every declared symbol.",
    "Check every ordered pair for the prefix relation.",
    "Verify symbol probabilities form an exact rational distribution.",
    "Compute the average code length using rational arithmetic."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "probabilities": {
      "A": "1/4",
      "B": "1/4",
      "C": "1/4",
      "D": "1/4"
    }
  },
  "claim": {
    "prefix_free": true,
    "expected_bits": "2"
  },
  "witness": {
    "codes": {
      "A": "00",
      "B": "01",
      "C": "10",
      "D": "11"
    }
  }
}
```

## Complexity

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

## Limits

No entropy estimate or code optimality claim is made. A rejected prefix code is retained as an instructive checked negative result.

## Common error and further work

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

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

## Verification

Complete codeword-pair check + exact rational average. 12 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://ocw.mit.edu/courses/6-441-information-theory-spring-2010/)