Hamming Code Ontology

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

1. PURPOSE
Represent binary Hamming codes as typed algebraic objects with checkable encoding, syndrome detection, and single-error correction operations.

2. TYPED ENTITIES
Bit := {0,1}
F2 := finite field with addition XOR and multiplication AND
Vector(n) := F2^n
Matrix(r,n) := F2^(r x n)
Codeword := Vector(n) satisfying H*c^T = 0
Message := Vector(k)
ReceivedWord := Vector(n)
ErrorVector := Vector(n)
Syndrome := Vector(r)
ParityCheckMatrix H := Matrix(r,n)
GeneratorMatrix G := Matrix(k,n)
HammingCode(r) := binary linear [n,k,d] code with n=2^r-1, k=n-r, d=3, r>=2
ExtendedHammingCode(r) := binary linear [2^r, 2^r-r-1, 4] code formed by adding overall parity

3. RELATIONSHIPS
HammingCode IS_A LinearBlockCode
LinearBlockCode IS_A ErrorCorrectingCode
GeneratorMatrix GENERATES Codeword
ParityCheckMatrix VALIDATES Codeword
ReceivedWord HAS_SYNDROME Syndrome
Syndrome IDENTIFIES SingleBitErrorPosition when error weight = 1
HammingCode CORRECTS up to 1 arbitrary bit error
HammingCode DETECTS up to 2 bit errors (not necessarily corrects)
ExtendedHammingCode SUPPORTS single-error correction and double-error detection (SECDED)

4. CORE CONSTRAINTS
r: integer >= 2
n = 2^r - 1
k = n - r
rank(H) = r
H columns are every distinct nonzero r-bit vector exactly once, in an explicitly declared column order
H*G^T = 0 over F2
C = {c in F2^n | H*c^T = 0}
|C| = 2^k
minimum_distance(C) = 3
CorrectionRadius = floor((d-1)/2) = 1
DetectionBound = d-1 = 2

5. FLOW OPERATIONS
flow CONSTRUCT_HAMMING(r):
  require integer(r) and r>=2
  n := 2^r - 1
  H := matrix whose columns enumerate all nonzero vectors of F2^r
  G := basis of nullspace(H) over F2, arranged as k x n
  assert rank(H)=r and H*G^T=0
  return (n, n-r, H, G)

flow ENCODE(message, G):
  require length(message)=rows(G)
  return (message*G) mod 2

flow SYNDROME(received, H):
  require length(received)=columns(H)
  return (H*received^T) mod 2

flow DECODE_SINGLE_ERROR(received, H):
  s := SYNDROME(received,H)
  if s=zero_vector: return (received, "no detected error", not_guaranteed_error_free)
  j := unique index such that column(H,j)=s
  corrected := received XOR unit_vector(j)
  assert SYNDROME(corrected,H)=zero_vector
  return (corrected, "single-error candidate", guaranteed_only_if_at_most_one_error)

flow EXTEND_WITH_PARITY(c):
  parity := sum(c_i) mod 2
  return concatenate(c,parity)

6. ALGEBRAIC LAWS
Linearity: ENCODE(a XOR b,G) = ENCODE(a,G) XOR ENCODE(b,G)
CodewordClosure: c1,c2 in C => c1 XOR c2 in C
ZeroCodeword: zero_vector(n) in C
SyndromeLinearity: SYNDROME(x XOR y,H) = SYNDROME(x,H) XOR SYNDROME(y,H)
SyndromeError: if received=c XOR e and c in C, then SYNDROME(received,H)=H*e^T
SingleError: if e=unit_vector(j), then SYNDROME(received,H)=column(H,j)
HammingBoundEquality: 2^k*(1+n)=2^n for binary Hamming codes

7. INFERENCE RULES
IF rank(H)=r AND H contains each nonzero r-bit column once THEN code has parameters [2^r-1,2^r-r-1,3].
IF syndrome is nonzero AND at most one bit was corrupted THEN the syndrome identifies the corrupted position.
IF syndrome is zero THEN received is a codeword; do not infer that no transmission error occurred.
IF two bits are corrupted in a standard Hamming code THEN syndrome is nonzero, but naive single-error correction can miscorrect.
IF overall parity and Hamming syndrome indicate double error in an extended Hamming code THEN report detected uncorrectable error rather than flip a bit.

8. WORKED EXAMPLE
r=3 => n=7, k=4, d=3
Choose H columns in order: 001,010,011,100,101,110,111 (bit strings represent column vectors).
For any valid codeword c, H*c^T=000.
If bit 5 is flipped, syndrome = 101, which identifies column 5.
Flipping bit 5 again restores the transmitted codeword, assuming at most one error.

9. VALIDATION
V01 r is integer and >=2.
V02 H dimensions are r x (2^r-1).
V03 Every H column is nonzero and no two columns repeat.
V04 rank(H)=r.
V05 G dimensions are (n-r) x n and rank(G)=n-r.
V06 H*G^T=0 mod 2.
V07 All encoded messages have zero syndrome.
V08 Each one-bit corruption yields the corresponding H column as syndrome.
V09 For each codeword, every one-bit corruption decodes back to it.
V10 Never claim general double-error correction for ordinary Hamming codes.
V11 Extended Hamming code SECDED decoder must distinguish parity/syndrome cases.

10. SEMANTIC_EQUIVALENCE
"Hamming code" ~= "binary single-error-correcting perfect linear code" ONLY when referring to standard binary Hamming family.
"Parity-check matrix" ~= "syndrome matrix" as context-dependent descriptions, not universally identical terminology.
"SECDED" != "ordinary Hamming code"; extended parity is required.
"Error detection" != "error correction".

11. CONFIDENCE
mathematical_definitions: 1.00
algebraic_laws: 1.00
worked_example: 1.00
live_page_alignment: unverified
confidence_policy: Formal guarantees depend on declared field, dimensions, code construction, and error assumptions.

12. FLOW_HASH
algorithm: SHA-256
scope: canonical UTF-8 content of this file excluding the FLOW_HASH value field itself
value: compute_on_ingestion

13. UPDATE_MODEL
trigger: source_revision | formal_correction | new_example | ontology_alignment_change
method: revalidate constraints; update version; recompute content hash; preserve provenance
compatibility: maintain stable entity and operation names or document migration

14. AI_CONSUMPTION
parse_mode: typed_declarative_flow
reasoning_mode: deterministic_mod2_linear_algebra
preferred_tasks: encoding, syndrome computation, correction-under-assumptions, theorem checking, ontology linking
required_checks: V01-V11
prohibited_inference: syndrome_zero_implies_no_error
output_contract: include code parameters, matrix column ordering, syndrome, decoding status, and assumptions

END FLOW ALGEBRA