Information Error Correction Codes From Jcost Ecc Family Count

The five families

Error-correcting codes let a message survive noise. When data travels through a channel, some bits get flipped; the receiver needs a way to detect and fix those flips. The five classic families of codes are repetition, Hamming, BCH/Reed-Solomon, LDPC, and polar codes. Each family is a distinct strategy for adding redundancy to a message so that errors can be corrected.

Repetition codes send each bit several times and take a majority vote. Hamming codes add parity bits that let the receiver locate a single flipped bit. BCH and Reed-Solomon codes use polynomial arithmetic to correct bursts of errors. LDPC codes use sparse parity-check matrices and iterative decoding. Polar codes, introduced by Erdal Arıkan in 2009, exploit channel polarization to achieve capacity. These five families dominate practical coding theory, from deep-space communication to Wi-Fi and 5G.

The framework's machine-checked library of formal theorems contains a declaration, eccFamily_count, that proves the number of these families is exactly five. The proof is a direct computation: it checks that the five listed families are all there are. The declaration is part of a larger structure that also proves every family has a positive threshold gap and that these gaps decrease strictly as one moves down the ladder. The threshold gap is the distance between a family's achievable rate and the Shannon capacity limit; smaller gaps mean closer to capacity.

In Recognition Science, the framework models these five families as the complete set of canonical error-correction strategies at a particular structural depth. The framework's cost function, which measures the price of recognition, produces a ladder of thresholds. Each family sits on a rung of this ladder, and the gaps between rungs follow a geometric ratio. The theorem that there are five families is a statement about this modeled structure, not a claim about every possible code ever invented.

What the declaration does not claim is that these are the only codes that exist. Many other codes have been designed, including convolutional codes and turbo codes. The declaration claims only that within the framework's model, five canonical families emerge at this depth. It also does not claim that the threshold gaps are physically measured; they are derived from the framework's definitions. The proof is a formal computation in the library, with zero axioms beyond the standard logical ones.

inductive ECCFamily where
  | repetition
  | hamming
  | bchReedSolomon
  | ldpc
  | polar
  deriving DecidableEq, Repr, BEq, Fintype

theorem eccFamily_count : Fintype.card ECCFamily = 5 := by decide

structure ECCCert where
  five_families : Fintype.card ECCFamily = 5
  threshold_always_pos : ∀ k, 0 < thresholdGap k
  threshold_strictly_decreasing : ∀ k, thresholdGap (k + 1) < thresholdGap k

What this page does not claim

The declaration does not claim these are the only error-correcting codes ever devised. The threshold gaps are derived from definitions, not measured from physical channels. The theorem does not prove any code achieves the Shannon limit exactly.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/ErrorCorrectionCodesFromJCost.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: