NumberDB$^\beta$ Advanced search Tags Tables Help Login
Belief-propagation thresholds of regular LDPC codes on the binary erasure channel
edit · history · discussion · files · short url · probability theory
Numbers
$l$
$r$ 
$\epsilon^{\mathrm{BP}}_{l,r}$
3
4:
0.6474256494010103699433673115176290794176741107650388581643454178949251946404222573497173063291285627
comment: The double fixed point is $x^{\mathrm{BP}}_{3,4}=0.441742430504$.
3
5:
0.5175701819014950776573150128369529845784690039348490084539515956945751460723288248871259995838820798
comment: The double fixed point is $x^{\mathrm{BP}}_{3,5}=0.328093462089$.
3
6:
0.4294398144194918371556095283314474261570741280102327674982252297778539595778854667886948322839447969
comment: The double fixed point is $x^{\mathrm{BP}}_{3,6}=0.260571072907$. Kudekar, Richardson and Urbanke give $\epsilon^{\mathrm{BP}}_{3,6}\approx 0.42944$ [1].
3
7:
0.3664191795204672190054844740538174783547992084743690982984788018673415506734775838588358227824760715
comment: The double fixed point is $x^{\mathrm{BP}}_{3,7}=0.215987266858$.
3
8:
0.3193121153498562380628066051322261591981582956154777910588018999149484632662304891389124833126536665
comment: The double fixed point is $x^{\mathrm{BP}}_{3,8}=0.184389835313$.
3
9:
0.2828368323849195683202375811045292618215463222739268519494902916046974085811068318243660360321094594
comment: The double fixed point is $x^{\mathrm{BP}}_{3,9}=0.160839303572$.
3
10:
0.2537883708018809667532335500702106657528194685686144015831277786559442100036324469334302337054245866
comment: The double fixed point is $x^{\mathrm{BP}}_{3,10}=0.142614216099$.
3
11:
0.2301218323212584284986642045941442567014493529772342160418634618740971447529743260234083428882897306
comment: The double fixed point is $x^{\mathrm{BP}}_{3,11}=0.128094106724$.
3
12:
0.2104754161202487813349595049899685765930835926308175169312570894619199313305232082470429284422308274
comment: The double fixed point is $x^{\mathrm{BP}}_{3,12}=0.116254634433$.
4
5:
0.6001109521010464656499858617730463383383880806922300388641488073162519666444753774847972952765523524
comment: The double fixed point is $x^{\mathrm{BP}}_{4,5}=0.447178781923$.
4
6:
0.5061323461778445767230851604158820509733169739598299428042821537288047943048420150162027255250528358
comment: The double fixed point is $x^{\mathrm{BP}}_{4,6}=0.363349503139$.
4
7:
0.4365973733885906978937682724018898835252463116049600796868301571402046702405036478068799761190369744
comment: The double fixed point is $x^{\mathrm{BP}}_{4,7}=0.305653674412$.
4
8:
0.3834465723217366076713832595502640761171472547763852706474898686755986714428632574482601247414380972
comment: The double fixed point is $x^{\mathrm{BP}}_{4,8}=0.263641195507$.
4
9:
0.3416363173952012807450502125841236782416334896147780221340235468358284855417700460001922748679668034
comment: The double fixed point is $x^{\mathrm{BP}}_{4,9}=0.231724294029$.
4
10:
0.3079448626463704483076579180073641200025958485449853954989549962238362259343062742300033378054747497
comment: The double fixed point is $x^{\mathrm{BP}}_{4,10}=0.206671364907$.
4
11:
0.2802441556862722274341775835157686654723284080974125100903651232745423059753541253772197996778775523
comment: The double fixed point is $x^{\mathrm{BP}}_{4,11}=0.186490985393$.
4
12:
0.2570810044002002062878130397566264096083022653941202514618306309924457648424711316261757005291041602
comment: The double fixed point is $x^{\mathrm{BP}}_{4,12}=0.169891588461$.
5
6:
0.5510035343592071877001978562847294544651830312216153731364836008490865456653675113073303443443939787
comment: The double fixed point is $x^{\mathrm{BP}}_{5,6}=0.423346634329$.
5
7:
0.4786068038434105556178854556205779846526315167489651889407588241456539569637023146872102815771754087
comment: The double fixed point is $x^{\mathrm{BP}}_{5,7}=0.359329197651$.
5
8:
0.4224462340617003241436373701113741934274632137803969757057708643919887781382348374246104758416248662
comment: The double fixed point is $x^{\mathrm{BP}}_{5,8}=0.311907937730$.
5
9:
0.3778045406996808318680869260973492223193382754316516604426166551081576109585842540316854636870743317
comment: The double fixed point is $x^{\mathrm{BP}}_{5,9}=0.275442493047$.
5
10:
0.3415500230422898616119782202561890673706299233815931950029602324826762254567458430428227687717286480
comment: The double fixed point is $x^{\mathrm{BP}}_{5,10}=0.246559219310$.
5
11:
0.3115613668707418904096704881272331616188026452622918315309667600557217571584471249587444744980884923
comment: The double fixed point is $x^{\mathrm{BP}}_{5,11}=0.223129866466$.
5
12:
0.2863638191408606265061135584132343079208264474259569899868222172425607932593914682836128693536610976
comment: The double fixed point is $x^{\mathrm{BP}}_{5,12}=0.203749968730$.
6
7:
0.5078931849564840370145190056941074999602568618222345012752539048133021753115719794580482496826508765
comment: The double fixed point is $x^{\mathrm{BP}}_{6,7}=0.396594280939$.
6
8:
0.4499266014156229849804014629697984467294823240966564608181002128167669813337428912672943747827178889
comment: The double fixed point is $x^{\mathrm{BP}}_{6,8}=0.345806583477$.
6
9:
0.4034896617599236421382849526538677671220618814348480870333448145428664213849033885129327059944081884
comment: The double fixed point is $x^{\mathrm{BP}}_{6,9}=0.306406485969$.
6
10:
0.3655576802459955413403089064393596127437660343371445050087197292516013105815031632188793463428709615
comment: The double fixed point is $x^{\mathrm{BP}}_{6,10}=0.274992604778$.
6
11:
0.3340399429542679649596109362591965728790962684472775849392287336260061644402960792804585171718729510
comment: The double fixed point is $x^{\mathrm{BP}}_{6,11}=0.249380043956$.
6
12:
0.3074622614781001286506942179484307980678259368037273002773986521277249486856936927537786859057259164
comment: The double fixed point is $x^{\mathrm{BP}}_{6,12}=0.228107723378$.
7
8:
0.4708776764367653180080414660808348676898325435659472266483030186298481905356430975552569713199600387
comment: The double fixed point is $x^{\mathrm{BP}}_{7,8}=0.371562423694$.
7
9:
0.4231886405149950444888261511366039792202241027810258141202052780434646915939602758357528427570365077
comment: The double fixed point is $x^{\mathrm{BP}}_{7,9}=0.330081990786$.
7
10:
0.3840537633660437191600799252554193238295467299887766912931413598652076754977298971537488457673580010
comment: The double fixed point is $x^{\mathrm{BP}}_{7,10}=0.296838488968$.
7
11:
0.3514199823576594701384389639210459891691112996996064104914255344287078345986366999303150923235012510
comment: The double fixed point is $x^{\mathrm{BP}}_{7,11}=0.269625553242$.
7
12:
0.3238224384249304119408323168009798830948027320051705281874757234651074646271270728304934201356450144
comment: The double fixed point is $x^{\mathrm{BP}}_{7,12}=0.246951723225$.
8
9:
0.4390466829307120666245868416212772034594638315329363048099521653002392036138786627616403393689664728
comment: The double fixed point is $x^{\mathrm{BP}}_{8,9}=0.349089111349$.
8
10:
0.3989979708441433017922917527240491279033052446349398242872941710234726016245663464524707218083056878
comment: The double fixed point is $x^{\mathrm{BP}}_{8,10}=0.314444692598$.
8
11:
0.3655029966349869928469911768826772127930431349594401129301536193206165361650335745293344540194136640
comment: The double fixed point is $x^{\mathrm{BP}}_{8,11}=0.285991809376$.
8
12:
0.3371100093630909745047015169932057557397384429361947947573332994696209700137294863850605354782287224
comment: The double fixed point is $x^{\mathrm{BP}}_{8,12}=0.262222656528$.
9
10:
0.4114755018414529615295155139647411173285158295955574993619146649245643652592891436132638216606286903
comment: The double fixed point is $x^{\mathrm{BP}}_{9,10}=0.329112357358$.
9
11:
0.3772899057397068364290390283540364704544118530464464440269904042022080047891731003966468567479474885
comment: The double fixed point is $x^{\mathrm{BP}}_{9,11}=0.299661147716$.
9
12:
0.3482529088467711548182209211858629708317778468850640815717558852251178757800754450291825343685525169
comment: The double fixed point is $x^{\mathrm{BP}}_{9,12}=0.275003404411$.
10
11:
0.3873919295931600570180140714300080706543443814296091657551792094255238532308188318832053099990127742
comment: The double fixed point is $x^{\mathrm{BP}}_{10,11}=0.311355180190$.
10
12:
0.3578190375174394542399300814069318585794094607321170936820173527151865145417347822894569931196571523
comment: The double fixed point is $x^{\mathrm{BP}}_{10,12}=0.285956506693$.
11
12:
0.3661801706661561881089519003920240893017581910073416632009498146646784722630737870566683726752469087
comment: The double fixed point is $x^{\mathrm{BP}}_{11,12}=0.295515258010$.
Definition
For $3\leq l<r$, the regular $(l,r)$ LDPC ensemble [3] has variable and check degrees $l$ and $r$. Its belief-propagation threshold $\epsilon^{\mathrm{BP}}_{l,r}$ is the supremum of BEC [4] erasure probabilities for which density evolution converges to $0$ [2].
Parameters
$l$
—   variable degree ($l\geq3$)
$r$
—   check degree ($r>l$)
Formulas
(1)
The density-evolution fixed point equation on the binary erasure channel is $x=\epsilon(1-(1-x)^{r-1})^{l-1}$ [1].
(2)
For $0<x\leq1$, write $\epsilon(x)=x/(1-(1-x)^{r-1})^{l-1}$.
(3)
The minimizer $x^{\mathrm{BP}}_{l,r}$ is the unique solution in $(0,1)$ of $p^{\mathrm{BP}}_{l,r}(x)=0$, where $p^{\mathrm{BP}}_{l,r}(x)=((l-1)(r-1)-1)(1-x)^{r-2} -\sum_{i=0}^{r-3}(1-x)^i$ [1].
(4)
$\epsilon^{\mathrm{BP}}_{l,r}=\min_{0<x\leq1}\epsilon(x)=\epsilon(x^{\mathrm{BP}}_{l,r})$ [1].
Comments
(5)
With $n$ variable nodes and $m$ check nodes, $m/n=l/r$, and the design rate is $1-l/r$. The actual rate is at least the design rate, with equality when the parity checks are linearly independent. The binary erasure channel has Shannon limit $\epsilon=l/r$ for rate $1-l/r$, and $\epsilon^{\mathrm{BP}}_{l,r}<l/r$ for every row.
(6)
For $l=2$ the threshold is $\epsilon^{\mathrm{BP}}_{2,r}=1/(r-1)$, the limit of $\epsilon(x)$ as $x\to0$, since $\epsilon(x)$ is increasing on $(0,1]$.
(7)
At the threshold, the density-evolution equation has a nonzero double fixed point $x^{\mathrm{BP}}_{l,r}$: it is the point where $\epsilon(x)$ is minimal. Each entry comment gives $x^{\mathrm{BP}}_{l,r}$ to twelve decimal places.
Programs
(P1)
Python
from mpmath import mp
mp.dps = 50
l, r = 3, 6
def p(x):
    y = 1 - x
    return ((l - 1) * (r - 1) - 1) * y**(r - 2) - mp.fsum(y**i for i in range(r - 2))
lo, hi = mp.mpf("0"), mp.mpf("1")
for _ in range(200):
    mid = (lo + hi) / 2
    if p(mid) > 0:
        lo = mid
    else:
        hi = mid
x = (lo + hi) / 2
print(x / (1 - (1 - x)**(r - 1))**(l - 1))
References
[1]
S. Kudekar, T. Richardson and R. Urbanke, Threshold saturation via spatial coupling: why convolutional LDPC ensembles perform so well over the BEC, IEEE Transactions on Information Theory 57 (2011), 803-834. (arXiv) (doi)
[2]
T. J. Richardson and R. L. Urbanke, The capacity of low-density parity-check codes under message-passing decoding, IEEE Transactions on Information Theory 47 (2001), 599-618. (doi)
Links
Data properties
Entries are of type: real number
How well the digits are known: proven
Sources of data: [1], [2]
Table is complete: no (it holds $\epsilon^{\mathrm{BP}}_{l,r}$ for every pair with $3\leq l<r\leq12$)
How they were obtained:

Each entry is computed in ball arithmetic with 64 guard bits beyond the 100 digits written. The root $x^{\mathrm{BP}}_{l,r}$ is enclosed by bisection on the sign of $p^{\mathrm{BP}}_{l,r}(x)$ between $0$ and $1$, down to a bracket of half-width $10^{-106}$ whose ends are checked to give opposite signs; the value of $x/(1-(1-x)^{r-1})^{l-1}$ on that bracket is the stored ball.

more

The generator also compares every row with an mpmath minimisation of $\epsilon(x)$ on $(0,1]$, and compares the $(3,6)$ row with the printed value $0.42944$ in [1].



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.