Coding Theory Ontology

FLOW ALGEBRA
TITLE: Coding Theory Ontology
DOMAIN: Discrete Mathematics / Coding Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/coding-theory/coding-theory-ontology.html
VERSION: 1.0
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Formal mathematical synthesis; live source page not independently verified.

1. ONTOLOGY
CodingTheory := study of encoding, transmitting, storing and recovering information under noise and errors.
Alphabet := finite set Σ with cardinality q >= 2.
Word(n,Σ) := ordered n-tuple over Σ.
Code := C ⊆ Σ^n, with nonempty C.
Codeword := c ∈ C.
BlockLength(C) := n.
CodeSize(C) := |C|.
Rate(C) := log_q(|C|)/n.
HammingDistance(x,y) := |{i ∈ {1,...,n} : x_i ≠ y_i}|.
MinimumDistance(C) := min{d_H(x,y) : x,y ∈ C, x ≠ y}, for |C| >= 2.

2. TYPED ENTITIES
Alphabet: FiniteSet[Symbol]
Symbol: Element[Alphabet]
MessageSpace: Set[Message]
Encoder: Function[MessageSpace, Code]
Decoder: Function[ReceivedWord, Message | Failure]
Channel: StochasticMap[TransmittedWord, ReceivedWord]
Code: Subset[Word(n,Alphabet)]
Codeword: Word(n,Alphabet)
ErrorPattern: Word(n,Alphabet)
HammingMetric: Metric[Word(n,Alphabet)]
LinearCode: VectorSubspace[GF(q)^n] (q a prime power)
GeneratorMatrix: Matrix[GF(q), k, n]
ParityCheckMatrix: Matrix[GF(q), n-k, n]
Syndrome: Vector[GF(q), n-k]

3. CORE RELATIONSHIPS
Code HAS_ALPHABET Alphabet
Code HAS_BLOCK_LENGTH n
Code CONTAINS Codeword
Encoder MAPS Message TO Codeword
Channel MAPS Codeword TO ReceivedWord
Decoder MAPS ReceivedWord TO MessageOrFailure
HammingDistance MEASURES SymbolDisagreements
MinimumDistance DETERMINES GuaranteedErrorCapability
LinearCode IS_SUBSPACE_OF GF(q)^n
GeneratorMatrix GENERATES LinearCode
ParityCheckMatrix DEFINES LinearCodeKernel

4. FLOW OPERATIONS
ENCODE(m) := E(m), requiring E(m) ∈ C.
TRANSMIT(c, channel) := r sampled from channel(. | c).
DECODE(r) := D(r), potentially returning Failure.
DISTANCE(x,y) := Σ_{i=1}^n 1[x_i ≠ y_i].
NEAREST_CODEWORD(r) := argmin_{c∈C} d_H(r,c), with tie policy explicit.
SYNDROME(r) := H r^T, for a linear code over GF(q).
LINEAR_ENCODE(m) := mG, for m ∈ GF(q)^k.
VALID_CODEWORD(c) := (H c^T = 0), for the code C = ker(H).

5. ALGEBRAIC LAWS AND THEOREMS
DistanceNonnegative: d_H(x,y) >= 0.
DistanceIdentity: d_H(x,y) = 0 iff x = y.
DistanceSymmetry: d_H(x,y) = d_H(y,x).
TriangleInequality: d_H(x,z) <= d_H(x,y) + d_H(y,z).
DetectionBound: minimum distance d guarantees detection of up to d-1 symbol errors.
CorrectionBound: minimum distance d guarantees unique correction of up to floor((d-1)/2) symbol errors.
SingletonBound: for a q-ary (n,M,d) code, M <= q^(n-d+1).
HammingBound: for a q-ary (n,M,d) code, M * Σ_{i=0}^{t} binom(n,i)(q-1)^i <= q^n, t=floor((d-1)/2).
LinearDimension: for an [n,k] linear code over GF(q), |C|=q^k and Rate=k/n.
ParityCheck: for a full-rank H of size (n-k)×n, C=ker(H) has dimension k.

6. INFERENCE RULES
IF C is a linear code AND c1,c2∈C THEN c1+c2∈C.
IF C is linear AND a∈GF(q) AND c∈C THEN a*c∈C.
IF d_min(C)>=2t+1 THEN unique decoding of every received word within distance t of a transmitted codeword is possible.
IF H*r^T ≠ 0 THEN r is not a codeword of C=ker(H).
IF H*r^T = 0 THEN r is a codeword of C=ker(H); this alone does not prove no transmission error occurred.
IF G has row rank k THEN m↦mG is injective on GF(q)^k.

7. SEMANTIC_EQUIVALENCE
Codeword ≡ EncodedWord (within a block-code context).
HammingWeight(x) ≡ d_H(x,0^n), for vectors over an alphabet with designated zero.
ErrorCorrectionCapability ≡ GuaranteedUniqueCorrectionRadius, when defined as floor((d_min-1)/2).
CodeRate ≡ InformationSymbolsPerTransmittedSymbol, for an [n,k] linear code with q-ary symbols.
NOT_EQUIVALENT: ErrorDetection ≠ ErrorCorrection.
NOT_EQUIVALENT: CodeRate ≠ ChannelCapacity.
NOT_EQUIVALENT: SyndromeZero ≠ ErrorFreeTransmission.

8. VALIDATION
ASSERT q>=2 AND n>=1.
ASSERT C⊆Σ^n AND |C|>=1.
ASSERT 0<=Rate(C)<=1.
ASSERT 0<=d_H(x,y)<=n for x,y∈Σ^n.
ASSERT all codewords have length n.
ASSERT generator and parity-check matrix dimensions are compatible.
ASSERT G*H^T=0 for a consistent linear-code pair.
ASSERT claimed correction radius t satisfies 2t<d_min(C).
ASSERT distance-based theorems use |C|>=2 when minimum distance is defined via distinct pairs.

9. EXAMPLE
Σ={0,1}; C={000,111}; n=3; |C|=2; d_min=3; Rate=1/3.
The code detects up to 2 bit errors and uniquely corrects up to 1 bit error.
Received word 101 has distance 1 from 111 and distance 2 from 000, so nearest-codeword decoding returns 111.

10. CONFIDENCE
MathematicalDefinitions: 1.00 (standard definitions, subject to stated assumptions).
Theorems: 1.00 (within specified finite block-code model).
SourcePageAlignment: UNVERIFIED.
InferenceConfidence: depends on validated inputs and modelling assumptions; not an empirical channel success probability.

11. FLOW_HASH
Algorithm: SHA-256
Canonicalisation: UTF-8; LF line endings; normalise field ordering before hashing.
Value: COMPUTE_ON_DEPLOYMENT (not precomputed).

12. UPDATE_MODEL
Trigger: definition change | theorem correction | source page revision | new code family | validation change.
Process: revise typed entities -> revalidate equations -> update semantic relationships -> recompute FLOW_HASH -> increment VERSION -> record provenance.

13. AI_CONSUMPTION
Parse entities and types; check preconditions before applying theorems.
Keep code parameters (q,n,M,d) explicit and distinguish linear [n,k,d] codes.
Do not conflate guaranteed correction radius with observed decoder performance.
Return proofs or counterexamples for inferred properties when possible.
Preserve source provenance, confidence and version metadata.

END FLOW ALGEBRA