Error Correction Ontology

FLOW ALGEBRA
TITLE: Error Correction Ontology
DOMAIN: Discrete Mathematics / Coding Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/coding-theory/error-correction-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Formal synthesis from established coding theory; live source page not independently verified.

1. PURPOSE
Model the detection, localisation and correction of symbol errors introduced during transmission or storage using mathematically specified error-correcting codes. Distinguish guaranteed correction within a bounded error model from probabilistic decoding and uncorrectable conditions.

2. TYPED ENTITIES
Alphabet := finite set of symbols, often F_q
Message := element of F_q^k
Codeword := element of code C subset F_q^n
BlockCode := (C, n, k?, q, d_min)
LinearCode := k-dimensional subspace C of F_q^n
GeneratorMatrix := G in F_q^(k x n), rank(G)=k
ParityCheckMatrix := H in F_q^((n-k) x n), rank(H)=n-k
ReceivedWord := r in F_q^n
ErrorVector := e in F_q^n
Syndrome := s in F_q^(n-k)
Decoder := mapping D: F_q^n -> C union {FAIL}
HammingWeight := wt(x) = number of nonzero coordinates of x
HammingDistance := d(x,y) = wt(x-y)
MinimumDistance := d_min(C) = min{d(c1,c2): c1 != c2 in C}
CorrectionRadius := t = floor((d_min-1)/2)
ErasurePattern := subset of coordinates with known unreliable positions
ChannelModel := specified probability law or bounded adversarial error model
DecodingOutcome := CORRECTED | NO_ERROR | DETECTED_UNCORRECTABLE | AMBIGUOUS | FAILURE

3. FORMAL OPERATIONS
ENCODE(m, G) -> c = mG for a linear code (row-vector convention).
TRANSMIT(c, e) -> r = c + e over F_q.
SYNDROME(r, H) -> s = Hr^T; valid codeword iff s=0 for full-rank H defining C.
DISTANCE(x,y) -> wt(x-y).
NEAREST_CODEWORD(r,C) -> argmin_{c in C} d(r,c); may return multiple candidates.
BOUNDED_DISTANCE_DECODE(r,C,t) -> unique c if d(r,c)<=t, otherwise FAIL.
CORRECT(r,e_hat) -> r-e_hat, provided e_hat is validated.
VERIFY(c_hat,H) -> H c_hat^T=0 (membership check, not proof of original message).

4. CORE LAWS AND INVARIANTS
L1: A code with minimum distance d_min guarantees correction of up to t=floor((d_min-1)/2) arbitrary symbol substitutions under bounded-distance decoding.
L2: A code detects every nonzero substitution error of weight less than d_min, provided membership is checked.
L3: A code can uniquely recover from up to d_min-1 erasures (known positions), provided the unerased coordinates determine a unique codeword.
L4: With e errors and s erasures, unique decoding is guaranteed whenever 2e+s < d_min.
L5: For linear codes, syndrome(r)=H e^T because H c^T=0.
L6: Distinct error patterns can share a syndrome; syndrome zero does not rule out undetected nonzero codeword errors.
L7: Hamming bound for q-ary code with M codewords and t-error correction: M * sum_{i=0}^t binomial(n,i)(q-1)^i <= q^n.
L8: Singleton bound: d_min <= n-k+1 for linear [n,k,d_min]_q codes.
L9: A nonzero linear code has d_min=min{wt(c): c in C, c != 0}.
L10: Corrected membership alone cannot certify the decoded message matches the transmitted one beyond the guaranteed radius.

5. RELATIONSHIP GRAPH
ErrorCorrection IS_A CodingTheoryProcess
ErrorCorrection USES ErrorCorrectingCode
ErrorCorrectingCode HAS Codeword
Codeword ENCODED_FROM Message
ReceivedWord DERIVED_FROM Codeword AND ErrorVector
Decoder CONSUMES ReceivedWord
Syndrome COMPUTED_USING ParityCheckMatrix
MinimumDistance DETERMINES CorrectionRadius
ErrorCorrection RELATED_TO ErrorDetection
ErasureDecoding SPECIAL_CASE_OF ErrorCorrection
ReedSolomonCode INSTANCE_OF ErrorCorrectingCode
HammingCode INSTANCE_OF ErrorCorrectingCode
LDPCCode INSTANCE_OF ErrorCorrectingCode

6. INFERENCE RULES
R1: IF d_min >= 2t+1 AND wt(e)<=t AND decoder is correct bounded-distance decoder THEN recovered_codeword=transmitted_codeword.
R2: IF H r^T != 0 THEN received_word is not a codeword of C.
R3: IF H r^T = 0 THEN received_word belongs to C; do not infer transmission was error-free.
R4: IF two distinct codewords minimise distance to r THEN nearest-neighbour result is AMBIGUOUS.
R5: IF 2e+s < d_min AND erasure locations known THEN unique error-and-erasure correction is possible in principle.
R6: IF observed corruption exceeds certified capability THEN report guarantee as unavailable; do not claim reliable correction.

7. EXAMPLE
Binary repetition code C={000,111}; n=3, k=1, d_min=3, t=1.
Message 1 encodes to 111. A one-bit error yields received 101.
Distances: d(101,111)=1; d(101,000)=2.
Bounded-distance decoding returns 111 and recovers message 1.
Two-bit errors can produce an incorrect nearest-codeword decision; no two-error guarantee exists.

8. VALIDATION
V1: Confirm finite-field alphabet and compatible matrix dimensions.
V2: Check rank(G)=k, rank(H)=n-k, and G H^T=0.
V3: Confirm C={mG:m in F_q^k}={x:H x^T=0}.
V4: Confirm stated d_min by proof, exhaustive search for small codes, or trusted construction.
V5: Confirm t=floor((d_min-1)/2), with correct error/erasure assumptions.
V6: Test zero-error, boundary-radius, beyond-radius, tie, and erasure cases.
V7: Separate detection, correction, and decoding confidence.
V8: Record channel model, decoder algorithm, complexity, and failure mode.

9. SEMANTIC_EQUIVALENCE
error-correcting code ~= forward error correction code [context: redundant coding]
minimum Hamming distance ~= code minimum distance [context: Hamming-metric block codes]
syndrome decoding ~= parity-check-based decoding [context: linear codes]
error detection != error correction
error correction != retransmission (ARQ)
error-free syndrome != proof of no corruption

10. CONFIDENCE
FORMAL_THEOREM: 1.00 when assumptions and proof obligations verified.
BOUNDED_DECODING_GUARANTEE: 1.00 only within specified minimum-distance radius and validated decoder.
EMPIRICAL_DECODING_CONFIDENCE: derived from measured channel and decoder performance; not assigned a universal constant.
UNCERTAIN_INPUT: return explicit uncertainty or failure rather than fabricated assurance.

11. FLOW_HASH
METHOD: SHA-256 over canonical UTF-8 representation of ontology content.
CANONICALISATION: normalise line endings to LF, preserve mathematical symbols, exclude FLOW_HASH computed value itself.
VALUE: COMPUTE_ON_PUBLICATION (not precomputed).

12. UPDATE_MODEL
TRIGGER: mathematical correction, code-family extension, new decoding method, source-page revision.
PROCESS: validate -> version increment -> recompute FLOW_HASH -> publish provenance and change log.
COMPATIBILITY: preserve stable entity names or provide explicit migration mapping.

13. AI_CONSUMPTION
INPUTS: code specification, channel assumptions, received word, known erasures, required reliability.
OUTPUTS: typed decoded codeword or failure, detected syndrome, guaranteed correction radius, validation trace, confidence qualifier.
REQUIREMENTS: preserve finite-field arithmetic, distinguish guarantees from estimates, expose ambiguity and out-of-radius results, never claim certainty unsupported by the error model.

END FLOW ALGEBRA