Linear Code Ontology

FLOW ALGEBRA
TITLE: Linear Code Ontology
DOMAIN: Discrete Mathematics > Coding Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/coding-theory/linear-code-ontology.html
VERSION: 1.0
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical synthesis; source page not independently verified

1. PURPOSE
Represent linear error-correcting codes as typed finite-field vector subspaces, with explicit encoding, syndrome checking, distance, decoding and verification constraints.

2. TYPED ENTITIES
FiniteField Fq: field of q=p^m elements, p prime, m>=1.
BlockLength n: positive integer.
Dimension k: integer, 0<=k<=n.
MessageSpace M: Fq^k.
AmbientSpace V: Fq^n.
LinearCode C: k-dimensional vector subspace of V.
Message u: vector in M.
Codeword c: vector in C.
ReceivedWord r: vector in V.
ErrorVector e: vector in V.
GeneratorMatrix G: matrix in Fq^(k x n), rank(G)=k.
ParityCheckMatrix H: matrix in Fq^((n-k) x n), rank(H)=n-k.
Syndrome s: vector in Fq^(n-k).
HammingWeight wt(v): number of nonzero coordinates of v.
HammingDistance dH(x,y): wt(x-y).
MinimumDistance d: minimum wt(c) over nonzero c in C, if k>0.
Decoder D: partial or total mapping V -> C, with a stated correction policy.

3. CORE DEFINITIONS
LINEAR_CODE(C,Fq,n,k) iff C subseteq Fq^n and
  (0 in C) and (forall x,y in C: x+y in C) and
  (forall a in Fq, x in C: a*x in C) and dim(C)=k.
ENCODE(u,G) := uG (row-vector convention).
CODE_FROM_G(G) := {uG : u in Fq^k}.
CHECK(c,H) := H*c^T = 0.
CODE_FROM_H(H) := {c in Fq^n : H*c^T=0}.
RECEIVE(c,e) := c+e.
SYNDROME(r,H) := H*r^T.
DISTANCE(C) := min{wt(c): c in C, c!=0}, for nonzero C.

4. STRUCTURAL CONSTRAINTS
0 <= k <= n; G has full row rank k; H has full row rank n-k.
G*H^T = 0 and ker(H)=rowspace(G).
|C| = q^k.
For a nonzero linear code, 1 <= d <= n.
For k=0, C={0}; minimum distance requires an explicit convention (often infinity).

5. ALGEBRAIC LAWS
ENCODE(u+v,G) = ENCODE(u,G)+ENCODE(v,G).
ENCODE(a*u,G) = a*ENCODE(u,G).
SYNDROME(c+e,H) = SYNDROME(e,H), for c in C.
dH(x,y) = wt(x-y).
dH(x,z) <= dH(x,y)+dH(y,z).
C_PERP := {v in Fq^n : v*c^T=0 for all c in C}.
dim(C)+dim(C_PERP)=n; (C_PERP)_PERP=C.
The rows of H generate C_PERP.

6. ERROR DETECTION AND CORRECTION
For minimum distance d, every nonzero error with wt(e)<d is detectable.
Guaranteed unique correction radius t=floor((d-1)/2).
A received word within Hamming distance t of a codeword has that codeword as its unique nearest codeword.
Up to d-1 erasures can be uniquely recovered when erased positions are known.
Outside guaranteed bounds, decoding may fail or return an incorrect codeword; report ambiguity and policy.

7. IMPORTANT BOUNDS
Singleton: d <= n-k+1 for nonzero C.
Hamming sphere packing: q^k * sum(i=0..t, binom(n,i)*(q-1)^i) <= q^n.
Minimum-distance calculation by nonzero codeword weights is valid because C is linear.

8. RELATIONSHIPS
LinearCode IS_A ErrorCorrectingCode.
LinearCode IS_A VectorSubspace.
LinearCode DEFINED_OVER FiniteField.
GeneratorMatrix GENERATES LinearCode.
ParityCheckMatrix DEFINES_KERNEL_OF LinearCode.
Codeword ELEMENT_OF LinearCode.
Syndrome INDICATES ParityConstraintViolation.
MinimumDistance DETERMINES GuaranteedErrorTolerance.
DualCode ORTHOGONAL_COMPLEMENT_OF LinearCode.
HammingCode IS_A LinearCode.
ReedSolomonCode IS_A LinearCode (standard finite-field constructions).

9. INFERENCE RULES
IF rank(G)=k AND C=rowspace(G) THEN dim(C)=k.
IF rank(H)=n-k AND C=ker(H) THEN dim(C)=k.
IF G*H^T=0 AND rank(G)=k AND rank(H)=n-k THEN rowspace(G)=ker(H).
IF SYNDROME(r,H)!=0 THEN r NOT_IN C.
IF SYNDROME(r,H)=0 THEN r IN C (not proof of error-free transmission).
IF d>=2t+1 THEN every error of weight <=t is uniquely correctable.
IF d>=s+1 THEN every erasure pattern of size <=s is uniquely recoverable.

10. VALIDATION
CHECK_FIELD: verify q is a prime power and arithmetic is performed in Fq.
CHECK_SHAPES: verify G and H dimensions.
CHECK_RANK: rank(G)=k; rank(H)=n-k.
CHECK_ORTHOGONALITY: G*H^T=0.
CHECK_CARDINALITY: |rowspace(G)|=q^k.
CHECK_CODEWORD: H*c^T=0 for sampled/generated codewords.
CHECK_DISTANCE: calculate nonzero codeword weights for tractable instances.
CHECK_DECODER: compare outputs against stated correction radius and test ambiguous cases.
CHECK_ZERO_CODE: apply an explicit minimum-distance convention for k=0.

11. EXAMPLE
Binary [3,2,2] even-parity code over F2:
G = [[1,0,1],[0,1,1]]
H = [[1,1,1]]
C = {000,101,011,110}; d=2.
Message 10 encodes to 101.
Received 100 has syndrome 1, so an error is detected.
This code guarantees detection of one error, but not correction of one unknown error.

12. SEMANTIC_EQUIVALENCE
"linear block code" ~= "linear code" when fixed-length block context is explicit.
"parity-check matrix" ~= "syndrome-check matrix" in this coding-theory context.
"code dimension" = vector-space dimension k, not block length n.
"code rate" = k/n (symbols per transmitted symbol), for n>0.
Distinguish codeword Hamming weight from pairwise Hamming distance.
Distinguish error detection from unique error correction.

13. CONFIDENCE
MATHEMATICAL_DEFINITIONS: high (standard finite-field linear coding theory).
SOURCE_PAGE_ALIGNMENT: unverified (live page not independently inspected).
DERIVED_RESULTS: require validation of assumptions and code parameters.
Do not convert semantic confidence into a numeric probability without calibration.

14. FLOW_HASH
HASH_INPUT: canonical UTF-8 serialisation of ontology title, version, source URL, entity definitions, constraints, inference rules and validation rules.
HASH_ALGORITHM: SHA-256.
HASH_VALUE: compute upon publication; do not fabricate a digest.

15. UPDATE_MODEL
ON_SOURCE_CHANGE: review definitions and relationships; increment version; recompute FLOW_HASH.
ON_FIELD_CHANGE: update finite-field constraints and example calculations.
ON_RULE_CHANGE: rerun algebraic and decoder validation tests.
MAINTAIN: provenance, change history and backwards-compatible identifiers where feasible.

16. AI_CONSUMPTION
INPUT: {q,n,k,G?,H?,message?,received?,decoder_policy?}.
PRECONDITIONS: valid finite field, consistent dimensions, rank and orthogonality.
PROCESS: construct code -> verify matrices -> encode/check -> compute syndrome -> decode only under explicit policy -> report guarantees.
OUTPUT: {code_parameters, codeword?, syndrome?, detected_error?, corrected_codeword?, guarantee, validation, provenance, confidence}.
FAIL_CLOSED: reject inconsistent matrices, invalid field arithmetic or unsupported decoding guarantees.

END FLOW ALGEBRA