Error Detection Ontology

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

1. ONTOLOGY
ontology ErrorDetectionOntology {
  extends CodingTheoryOntology
  purpose: Identify whether received information violates constraints imposed by an encoding scheme.
  distinction: Detection identifies possible corruption; correction additionally reconstructs a candidate original message.
}

2. TYPED ENTITIES
entity Message : SymbolSequence
entity Alphabet : FiniteSet[Symbol]
entity Code : Set[Codeword]
entity Codeword : SymbolSequence
entity Encoder : Function[Message,Codeword]
entity Channel : Transformation[Codeword,ReceivedWord]
entity ReceivedWord : SymbolSequence
entity ErrorPattern : SymbolSequence
entity Detector : Function[ReceivedWord,DetectionResult]
entity DetectionResult : Enum[ACCEPT,DETECTED_ERROR]
entity ParityBit : Bit
entity Checksum : FiniteValue
entity Syndrome : Vector[FiniteFieldElement]
entity GeneratorMatrix : Matrix[FiniteFieldElement]
entity ParityCheckMatrix : Matrix[FiniteFieldElement]
entity HammingDistance : NonNegativeInteger
entity MinimumDistance : NonNegativeInteger
entity UndetectedError : Event
entity DetectionGuarantee : Constraint

3. RELATIONSHIPS
Encoder maps Message -> Codeword
Channel maps Codeword -> ReceivedWord
ErrorPattern transforms Codeword -> ReceivedWord
Detector evaluates ReceivedWord -> DetectionResult
ParityCheckMatrix computes ReceivedWord -> Syndrome
MinimumDistance constrains DetectableErrorWeight
Checksum summarises MessageOrCodeword -> CheckValue
UndetectedError occurs_when ReceivedWord != TransmittedCodeword AND Detector(ReceivedWord) == ACCEPT

4. FORMAL MODEL
Let Sigma be a finite alphabet and C subseteq Sigma^n be a block code.
Encoding: E : M -> C.
Transmission: c = E(m), received r.
For binary additive noise: r = c XOR e, where e in {0,1}^n.
Hamming distance: d_H(x,y) = |{i : x_i != y_i}|.
Minimum distance: d_min(C) = min{d_H(x,y) : x,y in C, x != y}, for |C| >= 2.
Membership detector: D(r) = ACCEPT if r in C; DETECTED_ERROR otherwise.
An undetected substitution occurs when r in C and r != c.

5. DETECTION LAWS
For a code with minimum distance d >= 2, every substitution error pattern of Hamming weight at most d-1 is detected by exact codeword membership testing.
For a code with d >= 2t+1, unique correction of up to t substitution errors is possible.
A parity bit detects any odd number of flipped bits but cannot detect an even number of flipped bits.
For a binary linear code with parity-check matrix H, syndrome s = H*r^T over GF(2).
For transmitted c in C, H*c^T = 0; therefore s = H*e^T.
A nonzero syndrome proves r is not a codeword. A zero syndrome does not prove that no transmission error occurred.
For a systematic linear code, parity constraints must be applied consistently to the entire encoded word.

6. OPERATIONS
operation ENCODE(message, encoder) -> Codeword
operation TRANSMIT(codeword, channel) -> ReceivedWord
operation HAMMING_DISTANCE(wordA, wordB) -> NonNegativeInteger
operation COMPUTE_PARITY(word) -> Bit
operation COMPUTE_SYNDROME(received, H) -> Syndrome
operation VERIFY_CHECKSUM(received, expected) -> Boolean
operation DETECT_ERROR(received, code) -> DetectionResult
operation ESTIMATE_UNDETECTED_ERROR_RATE(channelModel, code) -> Probability

7. INFERENCE RULES
RULE R1: r notin C => DETECTED_ERROR.
RULE R2: r in C => ACCEPT; do not infer r equals transmitted c.
RULE R3: H*r^T != 0 => DETECTED_ERROR for the specified linear code.
RULE R4: H*r^T = 0 => r satisfies parity checks; transmission integrity is not guaranteed.
RULE R5: d_min(C) > t AND 0 < d_H(c,r) <= t => r notin C.
RULE R6: parity(received) != expectedParity => DETECTED_ERROR.
RULE R7: checksum mismatch => DETECTED_ERROR under the specified checksum procedure.

8. EXAMPLES
EXAMPLE A: Even parity: transmitted 10110 has three ones, so append parity bit 1 to form 101101. A single-bit flip changes parity and is detected.
EXAMPLE B: Repetition code C={000,111} has d_min=3 and detects any one- or two-bit substitution error. Three flips can transform 000 into 111 without detection.
EXAMPLE C: For any linear code, a received word with nonzero syndrome is invalid; a zero syndrome can still correspond to an undetected codeword-to-codeword error.

9. VALIDATION
CHECK alphabet finite and symbols valid.
CHECK encoded length n and parity-check matrix dimensions consistent.
CHECK H*c^T = 0 for all tested valid codewords.
CHECK claimed detection bound <= d_min - 1.
CHECK detection guarantee specifies error model (substitution, erasure, burst, insertion or deletion).
CHECK checksum collision possibility is not mistaken for absolute integrity.
CHECK probability estimates specify channel assumptions.
CHECK zero syndrome is never described as proof of error-free transmission.

10. SEMANTIC_EQUIVALENCE
Error detection ~= corruption detection, under a specified error model.
Parity checking is_a error detection technique.
Checksum verification is_a error detection technique.
Syndrome testing is_a error detection technique for linear codes.
Error detection != error correction.
Detected error != identified error location.
Accepted codeword != guaranteed original codeword.

11. CONFIDENCE
Formal mathematical definitions and distance bounds: HIGH, conditional on their stated assumptions.
Claims about actual channel reliability: CONDITIONAL on measured channel model and implementation.
Detection results: DETERMINISTIC for a fixed received word and specified code; not proof of transmission integrity on ACCEPT.

12. FLOW_HASH
canonical_fields: [ontology,version,source_url,typed_entities,relationships,formal_model,operations,inference_rules,validation]
method: SHA-256 over UTF-8 canonical serialisation of canonical_fields
value: COMPUTE_AT_INGESTION
note: No digest is asserted until canonicalisation and hashing are executed.

13. UPDATE_MODEL
on_change: [definition,algorithm,error_model,validation_rule,source_revision]
process: validate -> version -> recompute_flow_hash -> publish -> retain_provenance
compatibility: Preserve definitions of error model and guarantee when migrating.

14. AI_CONSUMPTION
read_mode: typed_semantic_flow
required_context: [alphabet,code,channel_error_model,detector]
output: [detection_result,syndrome_if_applicable,guarantee_scope,confidence,provenance]
reasoning_policy: Do not claim no errors occurred solely because parity/checksum/syndrome checks passed.
interoperability: [CodingTheoryOntology,CodewordOntology,HammingDistanceOntology,LinearCodeOntology,ErrorCorrectionOntology]

END FLOW ALGEBRA