Analytical Solution of Covariance Evolution
for Regular LDPC Codes
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Tokyo Institute of Technology

July 3th 2009

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

1 / 27

Finite-length scaling[Amraoui, et al. ’03]

block error probability

10.1

0.01

0.001
0.36

0.38

0.4

0.42

0.44

0.46

channel erasure probability

0.48

0.5

ǫ

(3,6)-regular, block-length 1024
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

2 / 27

Finite-length scaling[Amraoui, et al. ’03]

block error probability

10.1

0.01

0.001
0.36

0.38

0.4

0.42

0.44

0.46

channel erasure probability

0.48

0.5

ǫ

(3,6)-regular, block-length 1024
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

3 / 27

Regular LDPC code ensemble(2,3)-regular LDPC
code ensemble

Random Permitation: variable node : check node

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

4 / 27

Binary Erasure Channel : BEC

01

1−ǫ

0ǫ
ǫ?

1−ǫ

1

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

5 / 27

Peeling Algorithm [Luby ’97]

4Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

6 / 27

Peeling Algorithm [Luby ’97]

122

3

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

7 / 27

Peeling Algorithm [Luby ’97]

122

3

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

8 / 27

Peeling Algorithm [Luby ’97]

02

22

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJuly
Codes
3th 2009

9 / 27

The number of check nodes of residual degree 1
number of check nodes of residual degree 1
1801601401201008060402000100

200300400500

600

700

800

900

number of variable nodes in the residual graph(3,6)-regular, block-length 2048, channel erasure probability 0.425
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

10 / 27

The number of check nodes of residual degree 1
number of check nodes of residual degree 11801601401201008060402000100200300400500600700800900

number of variable nodes in the residual graph(3,6)-regular, block-length 2048, channel erasure probability 0.425
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

11 / 27

The number of check nodes of residual degree 1
number of check nodes of residual degree 1180160

1401201008060402000100200300

400500600700800900

number of variable nodes in the residual graph(3,6)-regular, block-length 2048, channel erasure probability 0.425
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

12 / 27

Distribution of the number of check nodes of residual
degree 1 [Amraoui, et al. ’03]
Amraoui, et al ’03
The distribution of the number of check nodes of residual degree 1
converge weakly to normal distribution.
number of check nodes of residual degree 11800.016

1600.014

1400.012

1200.01
1000.008
800.006
600.004
400.0022000100

200

300

400

500

600

700

number of variable nodes in the residual graph

800

900

0050

100150200

number of check nodes of residual degree 1(3,6)-regular ensemble, block-length 2048, channel erasure probability 0.425
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

13 / 27

The variance of the number of check node of residual
degree 1 [Amraoui, et al. ’03]
numerical computations for covariance evolution
the variance of the number of erased message

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

14 / 27

Definition of the covariances
Definition of the covarianceCov(lb (y ), lb (y ))# (edges in original graph)Cov(lb (y ), rj (y ))δ(lb ,rj ) (y ) :=# (edges in original graph)Cov(rj (y ), rk (y ))δ(rj ,rk ) (y ) :=# (edges in original graph)δ(lb ,lb ) (y ) :=lb (y ) := # (edges connecting to variable node of residual degree b)rj (y ) := # (edges connecting to check node of residual degree j)(j ∈ {1, 2, . . . , d − 1})
y := (parameter determined from the iteration number of PA)
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

15 / 27

ResultTheorem 1
For (b,d)-regular LDPC code ensemble,
δ(lb ,lb ) (y ) = bǫǫ̃,δ(lb ,rj ) (y ) = −Gj {ǫǫ̃(b − 1)y −1 + ǫ̃x} + I{j=1} bǫǫ̃,b−1
Gk Gj {ǫǫ̃(b − 1)y −2 − (ǫ − ǫ̃)xy −1 + x 2 }δ(rk ,rj ) (y ) =b
d − 1 d − 1 j+k 2d−k−j
d −1−dx x̃
+ I{k=j}kx k x̃ d−kk −1j −1
k −1+ I{k=1,j=1} (bǫǫ̃ − x x̃) − (I{k=1} Gj + I{j=1} Gk ){ǫǫ̃(b − 1)y −1 − ǫx + x 2 }ǫ : channel erasure probability
x := ǫy b−1, ǫ̃ := 1 − ǫ, x̃ := 1 − x,
j−1 x̃ d−j−1 (dx − j) + I
Gj := d−1{j=1}j−1 xTakayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

16 / 27

Resultδ(r1 ,r1 ) (y ) =b−1 2G1 {ǫǫ̃(b − 1)y −2 − (ǫ − ǫ̃)xy −1 + x 2 }b− dx 2 x̃ 2d−2 + x x̃ d−1+ (bǫǫ̃ − x x̃) − 2G1 {ǫǫ̃(b − 1)y −1 − ǫx + x 2 },where G1 := x̃ d−j−1 (dx − 1) + 1

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

17 / 27

Resultcorollary 1ǫ∗ : threshold of the ensemble under BP decodingfor ǫ = ǫ∗δ(r1 ,r1 ) (y ∗ ) =x ∗y ∗ ∗(y − x ∗ )b−1

The same result as in [Amraoui ’06] for regular LDPC code ensemble.
y ∗ : critical point,x ∗ := ǫ∗ (y ∗ )b−1

r1ǫ∗ ≈ ǫ

0.12

0.1

0.08

0.06

δ(r1 ,r1 ) (y ∗ )

0.04

0.02

000.2

0.4

0.6

y∗1yTakayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

18 / 27

Outline of proof
Solve the system of differential equation (covariance evolution) [Amraoui’06])dδ= F (y )δ(y ) + b(y )dyTakayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

19 / 27

Outline of proof
Solve the system of differential equation (covariance evolution) [Amraoui’06])dδ(lb ,lb )(y ) = 0,dyd−1i
h ∂ fˆ(rd−1 )X ∂ fˆ(rd−1 )dδ(lb ,rd−1 )δ(lb ,lb ) +δ(lb ,rs ) ,(y ) = −xdy∂r̄s∂ l̄bs=1h ∂ fˆ(rk )dδ(lb ,rk )∂ fˆ(rk ) (lb ,rk+1 ) ∂ fˆ(rk ) (lb ,rk ) i(y ) = −x
δ(lb ,lb ) +δ+δ.
dy∂r̄k+1∂r̄k∂ l̄b

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 200920 / 27

Outline of proof
Solve the system of differential equation (covariance evolution) [Amraoui’06])
δ(lb ,lb ) (y ) = bǫǫ̃,d−1h ∂ fˆ(rd−1 )iX ∂ fˆ(rd−1 )dδ(lb ,rd−1 )(y ) = −xbǫǫ̃+δ(lb ,rs ) ,dy
∂r̄s
∂ l̄b
s=1h ∂ fˆ(rk )dδ(lb ,rk )∂ fˆ(rk ) (lb ,rk+1 ) ∂ fˆ(rk ) (lb ,rk ) i.
bǫǫ̃ +δ+δ(y ) = −xdy∂r̄k+1∂r̄k∂ l̄b

Takayuki Nozaki, Kenta Kasai and Koichi SakaniwaAnalytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

21 / 27

Outline of proof
Solve the system of differential equation (covariance evolution) [Amraoui’06])
δ(lb ,lb ) (y ) = bǫǫ̃,d−1h ∂ fˆ(rd−1 )iX ∂ fˆ(rd−1 )dδ(lb ,rd−1 )(y ) = −xbǫǫ̃+δ(lb ,rs ) ,dy∂r̄s∂ l̄bs=1h ∂ fˆ(rk )dδ(lb ,rk )∂ fˆ(rk ) (lb ,rk+1 ) ∂ fˆ(rk ) (lb ,rk ) i.
bǫǫ̃ +δ+δ(y ) = −xdy∂r̄k+1∂r̄k∂ l̄blb , r1

lb , r2

lb , rd −2

lb , rd −1

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

21 / 27

Outline of proofA(y ) :=

Pd−1

s=1 δ(lb ,rs )Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

22 / 27

Outline of proofA(y ) :=

Pd−1

s=1 δ(lb ,rs )dA(y ) = d(b − 1)y −1 A + d(b − 1)(x d−1 y −2 − y −1 )bǫǫ̃,dyh ∂ fˆ(rd−1 )∂ fˆ(rd−1 )∂ fˆ(rd−1 ) (lb ,rd−1 ) idδ(lb ,rd−1 )(y ) = −xbǫǫ̃+,A+δ
dy
∂r̄1
∂r̄1
∂ l̄bh ∂ fˆ(rk )dδ(lb ,rk )∂ fˆ(rk ) (lb ,rk+1 ) ∂ fˆ(rk ) (lb ,rk ) i.
δ+δ(y ) = −xbǫǫ̃ +dy∂r̄k+1∂r̄k∂ l̄blb , r1

lb , r2

lb , rd −2lb , rd −1

ATakayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

22 / 27

Outline of proof
B (rj ,Σ) :=Pd−1 (r ,rs ) (Σ,Σ)
P
Pd−1 (r ,rs )jj,B:= d−1
s=1 δ
j=1
s=1 δ

replacements

B (r1 ,Σ)B (r2 ,Σ)(r,Σ)
B d −1B (Σ,Σ)rd −1 , r1

rd −1 , r2

rd −1 , rd −1(r,Σ)
B d −1

r2 , r1

r2 , r2

r2 , rd −1

B (r2 ,Σ)r1 , r1

r1 , r2

r1 , rd −1

B (r1 ,Σ)Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

23 / 27

numerically computationnδ(r1 ,r1 )
40000
analyticalexperiment

35000

30000

25000

20000

15000

10000

5000

001000

2000

3000

4000

5000

6000

7000

8000

9000

t

(3,6)-regular LDPC code ensemble,block length 16384, channel erasure probability 0.400
Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

24 / 27

Relationship between stability condition
corollary 2(1,if I{b=2} (d − 1)ǫ ≤ 1
ρlb ,r1 (ǫ) =−1, if I{b=2} (d − 1)ǫ > 1.
I{b=2} (d − 1)ǫ < 1 : stability condition
where,
ρlb ,r1 (ǫ) := lim py →0δ(lb ,r1 ) (ǫ, y )δ(lb ,lb ) (ǫ, y )δ(r1 ,r1 ) (ǫ, y ),Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

25 / 27

Conclusion and Future WorkConclusion
We show the analytical solution of the covariance evolution forregular LDPC code ensembles
We have derived the relation ship between stability condition

Future WorkShow the analytical solution of the covariance evolution for irregular
LDPC code ensembles

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolution
Instituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

26 / 27

Bibliography
A. Amraoui “Asymptotic and finite-length optimization of LDPC
codes,” Ph.D. Thesis, EPFL, June 2006.
M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman, and V.
Stemann. “Practical Loss-Resilient Codes,” in Proceedings of the 29th
annual ACM Symposium on Theory of Computing, 1997, pp. 150-159.
T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge
University Press, 2008.

Takayuki Nozaki, Kenta Kasai and Koichi Sakaniwa
Analytical( TokyoSolutionInstituteof Covarianceof TechnologyEvolution)
for Regular LDPCJulyCodes
3th 2009

27 / 27