Pinsketch decoder, stage 1: reading the packed syndrome and materialising its power sums
ProvedLinearSetReconciliation327.Main.pinsketch_decoder_readThis is the contract of the first stage of the Pinsketch decoder: the packed-word reader.
The environment is standard: the word width is and the field-data table is . Starting from the canonical initial state decoderStart (8w) y [] with program counter base, the reader runs the compiled code of inputSavedProcedure and halts within steps. In the resulting boundary state:
- the field elements of
eSeq b yare stored contiguously at addressdecoderSavedBase t; - the syndrome polynomial
syndromePoly (eSeq b y) tis stored at the same base up to the capacitydecoderCapacity t; - every address beyond the saved -element block is zero.
The hypotheses are the ones the stage genuinely needs: the code is installed at base, the word width is a multiple of eight, , (so fits in a word), , and the environment holds the standard table.
Formalization Note The conclusion is a Sem statement with an explicit step bound; FieldArrayStored and PolynomialStored are the memory-layout predicates of the decoder model, and eSeq/syndromePoly are the table-level objects that the key solver will consume.
import Definitions.Def_LinearSetReconciliation327_Main_Basic import Definitions.Def_LinearSetReconciliation327_Main_Pinsketch import Definitions.Def_LinearSetReconciliation327_Main_DecoderModel import Definitions.Def_LinearSetReconciliation327_Main_DecoderTables import Definitions.Def_LinearSetReconciliation327_Main_DecoderProgram import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_syndrome_recovery set_option autoImplicit false open Finset
theorem LinearSetReconciliation327.Main.pinsketch_decoder_read
{F : Type} [Field F] [Algebra (ZMod 2) F]
(E : RAMEnv) (P : Program) (base N t w : ℕ) (y : Fin (t * w) → ZMod 2)
(b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F)
(hAt : At P base (Stmt.compile inputSavedProcedure base))
(hW : E.W = 8 * w) (hw1 : 1 ≤ w) (hNw : N < 2 ^ w) (htN : t ≤ N)
(hdet : E.det = detStd t N b ι) :
Sem P E base (base + 110) { decoderStart (8 * w) y [] with pc := base }
(fun k z => k ≤ 62 * t + 66 ∧ ∃ m', z = boundaryState (base + 110) m' ∧
FieldArrayStored b m' (decoderSavedBase t) (2 * t) (eSeq b y) ∧
PolynomialStored b m' (decoderSavedBase t) (decoderCapacity t) (syndromePoly (eSeq b y) t) ∧
∀ addr, decoderSavedBase t + 2 * t ≤ addr → m' addr = 0) := by sorry