Reed–Solomon Code Ontology

FLOW ALGEBRA
TITLE: Reed–Solomon Code Ontology
DOMAIN: Discrete Mathematics / Coding Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/coding-theory/reed-solomon-code-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Represent Reed–Solomon (RS) codes as finite-field, polynomial-evaluation error-correcting codes with explicit encoding, decoding, validation and semantic reasoning rules.

2. TYPED ENTITIES
FiniteField(q): field GF(q), where q is a prime power.
FieldElement: element of GF(q).
EvaluationPoint: distinct alpha_i in GF(q).
MessagePolynomial: f(x) in GF(q)[x] with deg(f) < k.
Message: k field symbols, identified with coefficients of f.
Codeword: n field symbols (f(alpha_1), ..., f(alpha_n)).
ReceivedWord: n field symbols possibly corrupted or erased.
ErrorPosition: index where received symbol differs from transmitted symbol.
ErasurePosition: known location of missing or unreliable symbol.
GeneratorPolynomial: cyclic RS construction polynomial, where applicable.
Syndrome: parity-check evaluation of a received word.
Decoder: procedure producing a codeword or declaring failure.

3. PARAMETERS AND CONSTRAINTS
q = p^m, p prime, m >= 1.
1 <= k <= n <= q for the standard evaluation construction.
Evaluation points alpha_1,...,alpha_n are pairwise distinct.
Code C = { (f(alpha_1),...,f(alpha_n)) : f in GF(q)[x], deg(f) < k }.
C is a linear [n,k,d] code over GF(q), with d = n-k+1.
For extended or cyclic RS variants, specify evaluation conventions and allowable lengths separately.

4. OPERATIONS
ENCODE(message, evaluation_points) -> codeword.
EVALUATE(f, alpha_i) -> field_element.
ADD_CODEWORDS(c1,c2) -> c1+c2 in C.
SCALE_CODEWORD(a,c) -> a*c in C.
HAMMING_DISTANCE(u,v) -> number of differing coordinates.
CALCULATE_SYNDROME(received_word, parity_check) -> syndrome.
LOCATE_ERRORS(received_word, parameters) -> candidate positions.
CORRECT(received_word, positions, magnitudes) -> candidate codeword.
VERIFY_CODEWORD(candidate) -> Boolean.
DECODE(received_word, erasures?) -> codeword | failure.

5. FORMAL LAWS
LINEARITY: for f,g of degree < k and a,b in GF(q), ENCODE(a*f+b*g)=a*ENCODE(f)+b*ENCODE(g).
MINIMUM_DISTANCE: d(C)=n-k+1 for distinct evaluation points.
MDS_PROPERTY: d=n-k+1 meets the Singleton bound.
ERROR_CORRECTION: any pattern of t unknown symbol errors is uniquely correctable when 2t < d.
ERASURE_CORRECTION: any e known erasures are uniquely correctable when e < d.
MIXED_CORRECTION: 2t+e < d guarantees unique recovery.
EQUIVALENT_BOUND: 2t+e <= n-k.
UNIQUE_INTERPOLATION: k distinct correct evaluation pairs determine a unique polynomial of degree < k.

6. INFERENCE RULES
IF field_is_valid AND evaluation_points_distinct AND 1<=k<=n<=q THEN construction_is_valid.
IF construction_is_valid THEN code_is_linear AND minimum_distance=n-k+1.
IF error_count=t AND erasure_count=e AND 2*t+e<=n-k THEN unique_decoding_guaranteed.
IF syndrome_is_zero THEN received_word_is_codeword (for a valid parity-check matrix).
IF received_word_is_codeword THEN syndrome_is_zero.
IF error_bound_exceeded THEN guaranteed_unique_decoding=false; do not infer certain failure or success.
IF decoder_returns_candidate THEN require membership_check AND distance_or_erasure_consistency_check.

7. SEMANTIC RELATIONSHIPS
ReedSolomonCode IS_A LinearBlockCode.
ReedSolomonCode IS_A MaximumDistanceSeparableCode.
ReedSolomonCode USES FiniteField.
ReedSolomonCode ENCODES MessagePolynomial.
ReedSolomonCode PRODUCES Codeword.
ReedSolomonCode HAS_PARAMETER CodeLength.
ReedSolomonCode HAS_PARAMETER MessageLength.
ReedSolomonCode HAS_PROPERTY MinimumDistance.
Syndrome SUPPORTS ErrorDetection.
Decoder PERFORMS ErrorCorrection.
ErasurePosition HAS_KNOWN_LOCATION true.

8. SEMANTIC_EQUIVALENCE
'Reed–Solomon code' ~= 'RS code' [terminological alias].
'code length' ~= 'n' [parameter notation, in context].
'message dimension' ~= 'k' [parameter notation, in context].
'minimum Hamming distance' ~= 'd_min' [parameter notation].
'parity symbols' ~= 'n-k redundant symbols' [systematic encoding context].
Do not equate Reed–Solomon codes with binary Hamming codes, nor erasures with unknown-position errors.

9. VALIDATION
CHECK finite_field_order_is_prime_power.
CHECK 1<=k<=n<=q for standard evaluation RS.
CHECK all_evaluation_points_distinct.
CHECK every_symbol_belongs_to_GF(q).
CHECK encoded_word_length=n.
CHECK message_polynomial_degree<k.
CHECK codeword_membership_via_parity_check_or_interpolation.
CHECK decoding_guarantee_using_2*t+e<=n-k.
CHECK field arithmetic rather than ordinary integer arithmetic.
CHECK alternative cyclic/extended conventions before applying length restrictions.

10. WORKED EXAMPLE
Take GF(7), n=5, k=3 and evaluation points (0,1,2,3,4).
Message polynomial f(x)=1+2x+3x^2 (mod 7).
Evaluations: f(0)=1, f(1)=6, f(2)=3, f(3)=6, f(4)=1.
Codeword: (1,6,3,6,1).
Minimum distance d=5-3+1=3.
Guaranteed correction: 1 unknown symbol error OR 2 known erasures.

11. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard coding-theory results).
PAGE_SPECIFIC_ALIGNMENT: unverified.
DECODED_RESULT_CONFIDENCE: only assert certainty after valid assumptions and checks.

12. FLOW_HASH
HASH_METHOD: SHA-256 of canonical UTF-8 flow text, computed at ingestion.
HASH_VALUE: pending computation at ingestion; never fabricate a digest.

13. UPDATE_MODEL
ON field_parameter_change -> revalidate code parameters and arithmetic.
ON evaluation_point_change -> verify uniqueness and regenerate encoding structure.
ON decoding_algorithm_change -> rerun correctness and failure tests.
ON source_revision -> compare definitions, update provenance and recompute FLOW_HASH.

14. AI_CONSUMPTION
INPUT: code parameters, field specification, message/received symbols, known erasures.
PROCESS: validate -> construct/evaluate -> detect -> decode -> verify.
OUTPUT: encoded codeword, candidate decoded message, correction status, constraints, provenance.
FAIL_CLOSED: reject invalid field/parameters; flag undecidable or unverified decoding outcomes.
INTEROPERABILITY: finite-field ontology, polynomial ontology, linear-code ontology, error-correction ontology.

END FLOW ALGEBRA