Proposition 2.1's decoder at an arbitrary payload base
ProvedLinearSetReconciliation327.Main.pinsketch_decoding_atdecoderlinear-set-reconciliationpinsketchword-ram
If the payload of a syndrome is staged at word base in an otherwise zero memory, then Proposition 2.1's decoder — run through the copy-in/run/copy-out layer — halts within steps and outputs the decoding of the sparse vector from the pinning syndromes : a base-relative form of Proposition 2.1's decoding conjunct, in which the payload sits at an arbitrary word address rather than at word .
Preamble
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 Definitions.Def_LinearSetReconciliation327_Main_P21RunStmt
Formal statement
namespace LinearSetReconciliation327.Main
variable {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F] {N t w : ℕ}
theorem pinsketch_decoding_at (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F)
(y : Fin (t * w) → ZMod 2) (β : ℕ) (s : RAMState)
(hN : 1 ≤ N) (ht : 1 ≤ t) (htN : t ≤ N) (h0 : ∀ i < N, ι i ≠ 0)
(hinj : Set.InjOn ι (Set.Iio N)) (hpc : s.pc = 0)
(hpayload : ∀ j < wordsOf (8 * w) (t * w), s.mem (β + j) = packMem (8 * w) y j)
(hpayloadWord : ∀ j < wordsOf (8 * w) (t * w), s.mem (β + j) < 2 ^ (8 * w))
(hzero : ∀ a, (a < β ∨ β + wordsOf (8 * w) (t * w) ≤ a) → s.mem a = 0)
(hβL : wordsOf (8 * w) (t * w) ≤ β)
(hβfit : β + 2 * wordsOf (8 * w) (t * w) < 2 ^ (8 * w)) :
∃ s', HaltsWithin (programOfStatement (pinsketchRunStmt t w β))
(detEnv (8 * w) (detStd t N b ι))
(((positiveDecoderBudget t w + (24 * wordsOf (8 * w) (t * w) + 40) : ℕ) : ℝ)) s s' ∧
decoderPost (N := N) b ι y s' := by sorry
end LinearSetReconciliation327.MainSource
arXiv:2611.11409 (Liu, Xu, Yang, Zhou, *Linear Set Reconciliation with O(d) Additive Redundancy*), §2.2 (pinsketch syndromes and the decoder) and §2.1 (word-RAM model), Proposition 2.1 (decoding conjunct); extracted from the verified development `Solutions/Sol_p21_copyrun.lean`.