NumberDB$^\beta$ Advanced search Tags Tables Help Login
MAP thresholds of regular LDPC codes on the binary erasure channel
edit · history · discussion · files · short url · probability theory
Numbers
$l$
$r$ 
$\epsilon^{\mathrm{MAP}}_{l,r}$
3
4:
0.7460097024723318105717222930682639521990022693543414142035256298101436873938197210754381726436266565
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,4}=0.710102051443$.
3
5:
0.5909893877304922390627798686419034470131201343834866848061621865367552810785186681096609059912254748
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,5}=0.538660236756$.
3
6:
0.4881508841915662005813993380862359845289789242655725776324770240005542044448212499832351786869397408
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,6}=0.432262639059$. Kudekar, Richardson and Urbanke give $\epsilon^{\mathrm{MAP}}_{3,6}\approx 0.488151$ [1].
3
7:
0.4153919452093696880816156016349559318700702368159078901585675407681577451801635719165217595769333864
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,7}=0.360522497742$.
3
8:
0.3613392735023417384345720961714500311939989432103919419729943800999427961810263320712418352378302587
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,8}=0.309045562891$.
3
9:
0.3196531776614661063009286209219973699467026136780479389490049657975370630090305409435548170952711777
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,9}=0.270362770741$.
3
10:
0.2865480792405962018753697162189797174956855868083871762479439627043526359908818268585266497368438219
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,10}=0.240252416794$.
3
11:
0.2596325857883250699107776047580023820915742652296841682846650178573144710956468198603027353275373106
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,11}=0.216158467153$.
3
12:
0.2373249012919082061860774910817991797466587442096769091098595972297049238845462106975723236421737552
comment: The Maxwell root is $x^{\mathrm{MAP}}_{3,12}=0.196446070507$.
4
5:
0.7997287979304097984532428295165019814044802703180572008204120979011408993163464534527784779796021407
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,5}=0.795543687095$.
4
6:
0.6656555954293755092515547325135848203235721228365025564981510531745539300919052596534748901860017402
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,6}=0.656095319557$.
4
7:
0.5697050668943976149114565083226922692913505152755020520561886149032442416439627995790307116198278427
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,7}=0.556860436380$.
4
8:
0.4977408629255408293773349536026464914910229975370068501310633972072636882116106672788720697857116924
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,8}=0.483178816720$. Kudekar, Richardson and Urbanke give $\epsilon^{\mathrm{MAP}}_{4,8}\approx 0.49774$ [1].
4
9:
0.4418185307130570198803964281573184112656496543354989304015860897629250446132496397478941106991829425
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,9}=0.426485533439$.
4
10:
0.3971372668905980989576417122703143322796066297007123717859144438564850851512281344364696532479068644
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,10}=0.381583594771$.
4
11:
0.3606304294535902733841385094967230132271934472770147373025863166932911846981043997401989399555545341
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,11}=0.345172947470$.
4
12:
0.3302500387483348502000207736320442633220580238849270984238780953821267714450063978971659218861382353
comment: The Maxwell root is $x^{\mathrm{MAP}}_{4,12}=0.315068958671$.
5
6:
0.8333153207725165772543195056857145946908837474902968008850771435642115256323876373755351123452972072
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,6}=0.832880895647$.
5
7:
0.7141721918383283561512283182185610628768402934468815094047732934135762311229384662071820913531240078
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,7}=0.712562448869$.
5
8:
0.6247470536455753558790981466066315580917567857657447256337453893371316008733598816449417315508815430
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,8}=0.621995856653$.
5
9:
0.5551627487010864827643626446721561918526145672743458321152468837499920183473091542135749589646701517
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,9}=0.551538520602$.
5
10:
0.4994857962420084167256179096051055324957200725378876907350793273666624504707353502956610509656432922
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,10}=0.495250533476$. Kudekar, Richardson and Urbanke give $\epsilon^{\mathrm{MAP}}_{5,10}\approx 0.499486$ [1].
5
11:
0.4539329231353603301507347725276366229212733477533363066438306275466302804023582083684689381469908312
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,11}=0.449292124101$.
5
12:
0.4159776016157566684380134439769442380796168487566139687853474236906691616173931577797104368511769488
comment: The Maxwell root is $x^{\mathrm{MAP}}_{5,12}=0.411081983915$.
6
7:
0.8571418153601809456906171219487359214672896385117312579804971465927609905707987222784466249711395548
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,7}=0.857105330603$.
6
8:
0.7499885094961486256053781761927936036868682760592865887664605447303931942705442055377713627348012072
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,8}=0.749758104770$.
6
9:
0.6666325297500434033442215738991328114921029516602772827739112634467948595498314610225266088983996578
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,9}=0.666117932910$.
6
10:
0.5999363540617274887800857899364165595387521423576439768632877008299305720137631268803787625543464375
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,10}=0.599134996565$.
6
11:
0.5453597913015883636982318434611953743134493589688805036914334484844496642255506027704034764679820602
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,11}=0.544307746579$.
6
12:
0.4998757187122717730745341857564550241102083741276092195714100161686187547093132325100118149598240242
comment: The Maxwell root is $x^{\mathrm{MAP}}_{6,12}=0.498618989949$. Kudekar, Richardson and Urbanke give $\epsilon^{\mathrm{MAP}}_{6,12}\approx 0.499876$ [1].
7
8:
0.8749999478415831258342204121872530278708067731913175102910245054122575705961396887576784967814307059
comment: The Maxwell root is $x^{\mathrm{MAP}}_{7,8}=0.874997444091$.
7
9:
0.7777767492755224804161058331764985732003637775939068363720759432820736807678554988981610988785331470
comment: The Maxwell root is $x^{\mathrm{MAP}}_{7,9}=0.777748968138$.
7
10:
0.6999958602891425144168092550566638769211806952343470771978648844308457999702393922542931933973500664
comment: The Maxwell root is $x^{\mathrm{MAP}}_{7,10}=0.699912980204$.
7
11:
0.6363542567236949276256245373276635114961328046117438997381037749930145393532281747069834262902414211
comment: The Maxwell root is $x^{\mathrm{MAP}}_{7,11}=0.636199217208$.
7
12:
0.5833172998595457421442184318761976218048947152819386271591390350224267877896769650429860095726578991
comment: The Maxwell root is $x^{\mathrm{MAP}}_{7,12}=0.583085828360$.
8
9:
0.8888888865944974381850832264977823918859724565858196894690399110640576811066249625536683364970325239
comment: The Maxwell root is $x^{\mathrm{MAP}}_{8,9}=0.888888742047$.
8
10:
0.7999999180737916095849631455826924367403459296624240443277398549732436562193311507698610743347555966
comment: The Maxwell root is $x^{\mathrm{MAP}}_{8,10}=0.799997050498$.
8
11:
0.7272722756029631645296815511477607493551135905425344846146117168386962169286128524879255188185029476
comment: The Maxwell root is $x^{\mathrm{MAP}}_{8,11}=0.727260680633$.
8
12:
0.6666654115636381552774144925142736122833839893904568911494241956648676151684376186728605212847223087
comment: The Maxwell root is $x^{\mathrm{MAP}}_{8,12}=0.666639044567$.
9
10:
0.8999999999099999667899782565711310403606528580848388804712069724433116116509644475049384805560946533
comment: The Maxwell root is $x^{\mathrm{MAP}}_{9,10}=0.899999992710$.
9
11:
0.8181818123087669532355610825556942459002043505917906992190749888547028730595787768058954851252999763
comment: The Maxwell root is $x^{\mathrm{MAP}}_{9,11}=0.818181553893$.
9
12:
0.7499999552948856175814949022069076242936718221174733541582409524406829151298497073649124568325865004
comment: The Maxwell root is $x^{\mathrm{MAP}}_{9,12}=0.749998524692$.
10
11:
0.9090909090877227826699501221058767273395914611247647935498909330809282121876748949390680624117868404
comment: The Maxwell root is $x^{\mathrm{MAP}}_{10,11}=0.909090908772$.
10
12:
0.8333333329505049895418917893088910847746013751602109084705699818668289141858753839644561794070988857
comment: The Maxwell root is $x^{\mathrm{MAP}}_{10,12}=0.833333312278$.
11
12:
0.9166666666665638563996879230565495398769552769206779430764932946397675261213323174094145499585124942
comment: The Maxwell root is $x^{\mathrm{MAP}}_{11,12}=0.916666666654$.
Definition
For $3\leq l<r$, $\epsilon^{\mathrm{MAP}}_{l,r}$ is the binary erasure channel [4] threshold below which maximum a posteriori decoding of the regular $(l,r)$ LDPC ensemble [3] succeeds with high probability as the blocklength tends to infinity [2] [1].
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 root $x^{\mathrm{MAP}}_{l,r}$ is the solution in $0<x<1$ of $p^{\mathrm{MAP}}_{l,r}(x)=0$, where $p^{\mathrm{MAP}}_{l,r}(x)=x+\frac1r(1-x)^{r-1} (l+l(r-1)x-rx)-\frac lr$ [1].
(4)
$p^{\mathrm{MAP}}_{l,r}(x)=1-\frac lr-\int_x^1(1-(1-t)^{r-1})^l\,\epsilon'(t)\,dt$.
(5)
For every $x$, $p^{\mathrm{MAP}}_{l,r}(x)=\epsilon(x)(1-(1-x)^{r-1})^l+l x(1-x)^{r-1}-\frac lr(1-(1-x)^r)$.
(6)
The threshold is $\epsilon^{\mathrm{MAP}}_{l,r}=\epsilon(x^{\mathrm{MAP}}_{l,r})$ [1].
Comments
(7)
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{MAP}}_{l,r}<l/r$ for every row. Kudekar, Richardson and Urbanke prove that at fixed design rate the gap to $l/r$ closes exponentially fast in $l$; for example, in this table $11/12-\epsilon^{\mathrm{MAP}}_{11,12}=1.03\times10^{-13}$ [1].
(8)
For $l=2$, the cycle ensembles, the MAP and belief-propagation thresholds coincide [1]; both equal $1/(r-1)$, the limit of $\epsilon(x)$ as $x\to0$.
(9)
At $\epsilon=\epsilon^{\mathrm{MAP}}_{l,r}$ the density-evolution equation has two fixed points in $(0,1)$. The larger one is $x^{\mathrm{MAP}}_{l,r}$, the Maxwell root; it is stable and is the density-evolution message erasure probability at which belief propagation stalls on that channel. Each entry comment gives it to twelve decimal places.
(10)
The equation $p^{\mathrm{MAP}}_{l,r}(x)=0$ is the Maxwell construction: the area under the belief-propagation EXIT curve, taken from $\epsilon(x)$ to $1$, equals the design rate $1-l/r$. Lemma 4 of [1] states this characterization for regular ensembles, following [2].
Programs
(P1)
Python
from mpmath import mp
mp.dps = 50
l, r = 3, 6
def p(x):
    y = 1 - x
    return x + y**(r - 1) * (l + l * (r - 1) * x - r * x) / r - mp.mpf(l) / r
lo, hi = mp.mpf("1e-30"), 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]
C. Méasson, A. Montanari and R. Urbanke, Maxwell construction: the hidden bridge between iterative and maximum a posteriori decoding, IEEE Transactions on Information Theory 54 (2008), no. 12, 5277-5307. (arXiv)
Links
Similar tables
belief-propagation thresholds of regular LDPC codes on the binary erasure channel —   thresholds for iterative decoding of the same regular ensembles
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{MAP}}_{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{MAP}}_{l,r}$ is enclosed by bisection on the sign of $p^{\mathrm{MAP}}_{l,r}(x)$ in the interval $(0,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 bisection, compares the $(3,6)$ row with the printed value $0.488151$ in [1], and checks $\epsilon^{\mathrm{BP}}_{l,r}<\epsilon^{\mathrm{MAP}}_{l,r}<l/r$ against T275.



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