Finite-block iid channel coding bounds
OpenQAlgorithms.Papers.Independent.Intakethird100.P05.finite_block_codingFor a density-output channel with finite input alphabet and finite-dimensional output space, fix any input law and let . Set , , and . For real define
For every integer , every real , every , and every , there is one code of distinct words with positive decoder effects summing to at most identity, satisfying
Here is uniform-message average error on the original memoryless output states. This is a finite-block estimate; no mutual-information threshold or convergence assumption is required.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P05
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P05
open scoped Matrix ComplexConjugate ComplexOrder BigOperators
open Filter Topology QAlgorithms
open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)
open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)
open QAlgorithms.Papers.Independent.Dependency50.P28 (tr pinch typeI accept)
open QAlgorithms.Papers.Independent.Claimed50.P45 (pinchedTest)
open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)
open QAlgorithms.Papers.Independent.Information100.P27 (average)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Dependency50.P35 (directSum)
open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)
attribute [local instance] Classical.propDecidable Classical.decEq
variable {X I : Type} [Fintype X] [DecidableEq X] [Fintype I] [DecidableEq I]
/-- PDF p.5, Theorem 1, (21)–(23), with substitutions (20) on p.4:
for every positive length and gamma, and every lambda > 0, a code satisfies
the two finite-block bounds. No a < I(p) or convergence premise is imposed. -/
theorem finite_block_coding (W : DensityOutputChannel X I) (p : Distribution X)
(n : ℕ) (hn : 1 ≤ n) (a lambda gamma : ℝ)
(hlambda : 0 < lambda) (hgamma : 0 < gamma) :
∃ C : DistinctWordCode (Fin n → X) (Fin n → I),
gamma / (gamma + pinchedLowerTail W p n a) *
min (Real.exp (-(n : ℝ) * lambda))
(1 - pinchedLowerTail W p n a - gamma -
2 * Real.sqrt (Real.exp (-(n : ℝ) * lambda))) ≤
Real.exp (-(n : ℝ) * a) * (C.size : ℝ) ∧
uniformMessageError (wordOutput W.state (n := n)) C ≤ pinchedLowerTail W p n a + gamma +
2 * Real.sqrt (Real.exp (-(n : ℝ) * lambda)) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P05
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For finite index types with decidable equality, let be positive semidefinite complex matrices of trace , and let with . Fix a natural number , arbitrary real , and positive reals . Put , define and , and let , using the spectral projections of at its distinct eigenvalues. Let be the orthogonal projection onto the range of the positive part of , defined by continuous functional calculus, and set
There exists a code with positive integer size , an injective list of words , and positive semidefinite decoding matrices on with , satisfying
No bound relating to an information quantity is assumed, and the stated size lower bound may be nonpositive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.