# Comma-free codes: a boundary is not a recovered payload

This deterministic mathematical example is not storage-device data or an
error-rate estimate. It connects the existing Huffman, Tunstall and
Varshamov-Tenengolts records without treating their guarantees as interchangeable.

## Four different questions
- A prefix code decodes from a known codeword boundary.
- A comma-free fixed-length code rejects codewords at shifted boundaries in a
  valid concatenation.
- A non-overlapping (cross-bifix-free) code also forbids equality between proper
  prefixes and suffixes, including within one word.
- Error correction must distinguish allowed damaged observations of distinct
  original messages. Boundary recovery alone does not establish that property.

The fixed-length comma-free convention is from Golomb, Gordon and Welch [1].
The stronger prefix/suffix condition is Blackburn's definition [2]. These names
are not used as synonyms here.

## A compact witness
Use C = {001, 011}, mapping one source bit to each three-bit word. Its four
ordered word pairs produce eight shifted three-bit windows; none belongs to C.
A scanner in a valid stream therefore recognizes boundaries without a delimiter.
From an arbitrary start with enough uncorrupted continuation, at most five
observed bits suffice to include a complete word: the next boundary is at most
two bits away. A suffix of only 01 has no complete word.

That synchronization does not establish integrity:
- Substitution: changing the middle bit of 001 produces the valid word 011.
- Deletion: either 001 or 011 can lose one bit and produce 01. Even with the
  original width known, the two source messages cannot be distinguished.
- Stronger condition: suffix 01 of 001 equals prefix 01 of 011. Thus C is
  comma-free but not non-overlapping.
- Rate: this particular mapping carries 1/3 source bit per stored bit before
  headers, length information, checksums or outer correction. It is not a
  compressor or an estimate of a deployed format's overhead.

By contrast, the complete two-bit code {00, 01, 10, 11} is prefix-free yet cannot
find the phase of the infinite alternating stream: aligned pairs are 01 and
shifted pairs are 10 forever. A valid parse is not a synchronization certificate.

The VT record addresses one insertion or deletion with known block parameters.
C does not supply that guarantee. Neither result replaces a file-format
integrity check or a model of errors on actual media.

## Storage contrast: SATA's comma is a special marker
SATA Revision 3.5 uses K28.5 in ALIGN for alignment [3]. This does not make
its entire 8b/10b alphabet a comma-free dictionary. D10.2 is 0101010101;
D21.5 is 1010101010, both with neutral subblock disparity.

Our constructed D10.2 pair has nine shifted ten-bit windows. Even shifts
2, 4, 6 and 8 repeat D10.2; odd shifts give D21.5. None locates the original
boundary. This is a direct counterexample under the definition above, not a
receiver simulation. The pair contains neither seven-bit comma pattern.

There is another limit: during speed negotiation, section 8.4.4.1 recommends
qualifying whole ALIGN primitives because mismatched signaling rates can cause
spurious recognition. Marker detection, protocol acceptance and payload integrity
are different checks. We do not model analog sampling or claim a device failure.

## Exhaustive finite verification
The generator enumerates all 65,808 nonempty binary dictionaries of word widths
1 through 4. Maximum comma-free sizes are 2, 1, 2 and 3, respectively.
An integer-bitmask classifier is compared against a separate concatenated-string
oracle on every dictionary. The classification hash binds each mask to its
accept/reject result; it is an artifact check, not an authentication mechanism.

The JSON retains all eight overlap windows, 24 scan examples, all six single-bit
substitutions of C, and the deletion ambiguity. Scan tests cover every stream of
one through seven words and every starting offset. Input validation, periodic,
cyclic, truncation and changed-result controls are included. Counts are not
samples of hardware behavior and need no statistical confidence interval.
Small-width enumeration does not prove a general maximum-size theorem.

## Reproduce
Download the [model](model.py), [results](results.json) and [tests](test_model.py)
together. Python 3 and its standard library suffice. No random seed,
third-party package or additional data download is needed.
From this directory:

```sh
python3 -B model.py --check
python3 -B -m unittest -v test_model
python3 -B -O -m unittest -v test_model
```

Regenerate with `python3 -B model.py --write`; only results.json is replaced.
Compare the complete file, not just a success message.

## Sources
1. S. W. Golomb, Basil Gordon and L. R. Welch, *Comma-Free Codes*, Canadian
   Journal of Mathematics 10 (1958), 202-209, sections 1-2.
   https://doi.org/10.4153/CJM-1958-023-9
2. Simon R. Blackburn, *Non-overlapping codes*, arXiv:1303.1026v3 (8 July 2015),
   introduction. Journal DOI: 10.1109/TIT.2015.2456634.
   https://arxiv.org/abs/1303.1026v3

3. SATA-IO, *Serial ATA Revision 3.5 Gold*, 1 July 2020,
   sections 4.1.1.11 and 4.1.1.16-17 (pp. 41-42), 8.4.4.1 (p. 462),
   and 9.3.3.5 (pp. 478-479).
   https://sata-io.org/system/files/specifications/SerialATA_Revision_3_5_Gold.pdf

Primary PDFs were inspected on 2026-11-18. Source bytes and hashes are retained
in the private research ledger; no third-party PDF is redistributed.
The small dictionaries are constructed examples; the SATA symbol values come
from the cited specification, with independently calculated shifted windows.
