Refined scaling conjecture for unconditionally stable LDPC ensembles

About 22 years old · traced to

Consider transmission over the binary erasure channel with erasure probability ϵ\epsilon using random elements from an ensemble LDPC⁡(n,λ,ρ)\operatorname{LDPC}(n,\lambda,\rho) having a single critical point and being unconditionally stable. Let ϵ∗=ϵ∗(λ,ρ)\epsilon^*=\epsilon^*(\lambda,\rho) be the threshold, let ν∗\nu^* be the fractional size of the residual graph at the threshold, and let γ∈(0,1)\gamma\in(0,1). Write P⁡b(n,λ,ρ,ϵ)\operatorname{P}_{\rm b}(n,\lambda,\rho,\epsilon) for the expected bit-erasure probability and P⁡B,γ(n,λ,ρ,ϵ)\operatorname{P}_{\rm B,\gamma}(n,\lambda,\rho,\epsilon) for the expected block-erasure probability due to errors of size at least γν∗\gamma\nu^*. Set

z:=n(ϵ∗−βn−2/3−ϵ).z:=\sqrt{n}\left(\epsilon^*-\beta n^{-2/3}-\epsilon\right).

Refined scaling conjecture. As nn tends to infinity,

P⁡B,γ(n,λ,ρ,ϵ)=Q(zα)(1+O(n−1/3)),\operatorname{P}_{\rm B,\gamma}(n,\lambda,\rho,\epsilon)=Q\left(\frac{z}{\alpha}\right)\left(1+O(n^{-1/3})\right),

and

P⁡b(n,λ,ρ,ϵ)=ν∗Q(zα)(1+O(n−1/3)),\operatorname{P}_{\rm b}(n,\lambda,\rho,\epsilon)=\nu^*Q\left(\frac{z}{\alpha}\right)\left(1+O(n^{-1/3})\right),

where α=α(λ,ρ)\alpha=\alpha(\lambda,\rho) and β=β(λ,ρ)\beta=\beta(\lambda,\rho) are constants depending on the ensemble. The preceding scaling lemma gives the leading Gaussian behavior, but the finite-length shift and its O(n−1/3)O(n^{-1/3}) refinement were not rigorously established in the source; the authors describe the remaining difficulty as technical rather than conceptual.

References

Primary source

Abdelaziz Amraoui, Andrea Montanari, Tom Richardson and Rudiger Urbanke, “Finite-Length Scaling and Finite-Length Shift for Low-Density Parity-Check Codes”, arXiv:cs/0410019 (2004).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.