Cyclic Code Ontology

FLOW ALGEBRA
TITLE: Cyclic Code Ontology
DOMAIN: Discrete Mathematics / Coding Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/coding-theory/cyclic-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. ONTOLOGY
ENTITY CyclicCode <: LinearCode
ENTITY FiniteField GF(q)
ENTITY Codeword = Vector(GF(q), n)
ENTITY GeneratorPolynomial g(x)
ENTITY ParityCheckPolynomial h(x)
ENTITY MessagePolynomial m(x)
ENTITY ReceivedPolynomial r(x)
ENTITY SyndromePolynomial s(x)
ENTITY ErrorPolynomial e(x)
ENTITY CodeParameters (n,k,d_min,q)

2. TYPE AND DOMAIN CONSTRAINTS
q = p^m where p is prime and m >= 1.
n >= 1; 0 <= k <= n.
C subseteq GF(q)^n is a linear subspace of dimension k.
Represent vectors (c_0,...,c_(n-1)) as c(x) = sum_{i=0}^{n-1} c_i x^i.
Work in quotient ring R = GF(q)[x]/(x^n - 1).
All polynomial congruences below are modulo x^n - 1 unless stated otherwise.

3. DEFINITIONS
CYCLIC(C) iff for every (c_0,...,c_(n-1)) in C,
  (c_(n-1),c_0,...,c_(n-2)) in C.
EQUIVALENT: x*c(x) mod (x^n - 1) belongs to C whenever c(x) belongs to C.
C is a cyclic linear code iff its polynomial representation is an ideal of R.
Since GF(q)[x] is a principal ideal domain, each cyclic code has a unique monic generator polynomial g(x) dividing x^n - 1.
C = {m(x)*g(x) mod (x^n - 1) : deg(m) < k}.
k = n - deg(g).
h(x) = (x^n - 1)/g(x); deg(h) = k.
MEMBERSHIP(c): g(x) divides c(x) in GF(q)[x] for representatives of degree < n.

4. OPERATIONS
ENCODE(m): return m(x)*g(x) for deg(m) < k (degree < n).
SHIFT(c): return x*c(x) mod (x^n - 1).
ADD(c1,c2): componentwise addition over GF(q).
SCALAR(a,c): componentwise multiplication by a in GF(q).
SYNDROME(r): return r(x) mod g(x).
DETECT(r): return SYNDROME(r) != 0.
CORRECT(r): identify an error e consistent with the syndrome and a declared decoding radius; return r-e only when unique correction is certified.

5. INVARIANTS AND ALGEBRAIC LAWS
SHIFT(C) = C.
SHIFT^n(c) = c.
C is closed under vector addition and scalar multiplication.
g(x) | (x^n - 1).
g(x)*h(x) = x^n - 1.
SYNDROME(c) = 0 for every c in C.
SYNDROME(c+e) = SYNDROME(e).
Minimum distance d_min = min{wt(c): c in C, c != 0}, for nonzero codes.
Guaranteed correction of t errors if 2*t < d_min.
Guaranteed detection of up to d_min - 1 symbol errors.
Note: A zero-dimensional code has no nonzero codeword; handle d_min by an explicit convention.

6. INFERENCE RULES
IF C is linear AND closed under cyclic shift THEN C is a cyclic code.
IF g is monic AND g divides x^n - 1 THEN <g> defines a cyclic code of length n.
IF deg(g) = n-k THEN dim(C) = k.
IF r mod g != 0 THEN r is not a codeword.
IF r mod g = 0 THEN r is a codeword; undetected transmission errors remain possible.
IF wt(e) <= floor((d_min-1)/2) AND decoding is nearest-codeword THEN correction is unique.
IF gcd(n,q) = 1 THEN x^n - 1 has no repeated roots over GF(q); do not assume this without checking.

7. SEMANTIC RELATIONSHIPS
CyclicCode IS_A LinearCode.
CyclicCode USES FiniteField.
CyclicCode REPRESENTED_BY PolynomialIdeal.
CyclicCode GENERATED_BY GeneratorPolynomial.
GeneratorPolynomial DIVIDES (x^n - 1).
ParityCheckPolynomial COMPLEMENTS GeneratorPolynomial IN factorisation of (x^n - 1).
Codeword SUBJECT_TO CyclicShift.
SyndromePolynomial SUPPORTS ErrorDetection.
MinimumDistance BOUNDS ErrorCorrectionCapacity.
BCHCode IS_A CyclicCode (standard narrow-sense constructions).
CRCCode USES CyclicPolynomialCodePrinciples (implementation details vary).

8. VALIDATION
CHECK field arithmetic is valid for GF(q).
CHECK n,k are integers and 0 <= k <= n.
CHECK g is monic and divides x^n - 1.
CHECK deg(g) = n-k.
CHECK every encoded codeword has degree < n and zero remainder modulo g.
CHECK cyclic shifts of generated basis vectors remain in code.
CHECK any claimed d_min against codeword weights or a proved distance bound.
CHECK decoder's declared radius and failure/ambiguity handling.
CHECK polynomial coefficient ordering and shift convention.

9. EXAMPLE (BINARY)
FIELD: GF(2); n = 7; g(x) = x^3 + x + 1.
FACT: g(x) divides x^7 + 1 in GF(2)[x].
k = 7-3 = 4.
MESSAGE: m(x) = x+1.
ENCODE: c(x) = (x+1)(x^3+x+1) = x^4+x^3+x^2+1.
SYNDROME(c) = 0.
SHIFT: x*c(x) mod (x^7+1) is also a codeword.
This is a binary [7,4,3] cyclic Hamming code.

10. SEMANTIC_EQUIVALENCE
"cyclic linear code" == "linear code invariant under cyclic coordinate shift".
"generator polynomial" == "unique monic generator of the associated ideal".
"syndrome" == "remainder upon division by generator polynomial" (for this cyclic-code convention).
Do not equate cyclic codes with arbitrary linear codes or convolutional codes.

11. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard theory)
SOURCE_PAGE_ALIGNMENT: unverified
EXAMPLE_CONFIDENCE: 1.00 (algebraically checkable)
Do not interpret confidence values as empirical probabilities.

12. FLOW_HASH
ALGORITHM: SHA-256
INPUT: canonical UTF-8 bytes of this document excluding the FLOW_HASH value itself.
VALUE: COMPUTE_ON_INGEST

13. UPDATE_MODEL
TRIGGER: revised source page, correction to algebra, new code construction, or changed field/length assumptions.
ACTION: revalidate divisibility, dimension, distance claims, example, and semantic links; increment version and recompute FLOW_HASH.
PROVENANCE: distinguish standard mathematical facts from claims verified against source page.

14. AI_CONSUMPTION
PARSE: entities -> constraints -> definitions -> operations -> invariants -> inference -> validation.
REASONING_POLICY: preserve finite-field arithmetic and quotient-ring semantics; verify divisibility before inferring cyclic-code properties.
OUTPUT: typed graph of concepts, machine-checkable predicates, algebraic transformations, and provenance-aware confidence.
FAIL_CLOSED: reject invalid field sizes, non-dividing generator polynomials, unsupported distance claims, and ambiguous decoding.