Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Detailed Evolution of Degree Distributions inResidual Graphs with Joint Degree Distribtuions

Takayuki Nozaki 1 , Kenta Kasai 1 ,Tomoharu Shibuya 2 and Kohi hi Sakaniwa 1
1Tokyo Institute of Te hnology, Tokyo
2Sophia University, Tokyo

July 9th, 2008

1 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Detailedly represented irregular LDPCode ensembles[Kasai, et al. '03℄

2323

: variable node

: he k node

3ements34(i ; j ) : joint degree distribution4

(2; 3) =224

(3; 3) =22r5;1r6;1r10;133t5;1 ; r10;1g3y5y10

34

153,  (2; 4) = 2213,  (3; 4) = 22

2 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Finite-length s aling[Amraoui, et al. '03℄

epla ements
r5;1r6;1r10;1t

minfr5;1 ; r10;1 gy5y10(3,6)-regular, blo k-length 2048

3 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Finite-length optimization

4 / 18[Amraoui, et al. '06℄

Optimized degree distribution pair(x ) = 0:0739196x + 0:657891x + 0:268189x
(x ) = 0:390753x + 0:361589x + 0:247658x
4

hannel erasure probability 0.5
blo klength 5000
target blo k error probability 10 421259

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Our goal

Finite-length s aling with joint degree distributions.

5 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Our goal

Finite-length s aling with joint degree distributions.

As a rst step, we analyze an iterative de oder.

5 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Peeling Algorithm

23233PSfrag repla ements 34r5;1r6;1r10;1343t

minfr5;1 ; r10;1 g 34y5y103436 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Peeling Algorithm

231334143444323PSfrag repla ements 3r5;1r6;1r10;133t

minfr5;1 ; r10;1 g 3y5y10

37 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Peeling Algorithm

23

1334

143444323PSfrag repla ements 3r5;1r6;1r10;133t

minfr5;1 ; r10;1 g 3y5y10

38 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Peeling Algorithm

231334143444323PSfrag repla ements 3r5;1r6;1r10;133t

minfr5;1 ; r10;1 g 3y5y10

39 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Peeling Algorithm

231324043434323PSfrag repla ements 3r5;1r6;1r10;133t

minfr5;1 ; r10;1 g 3y5y10

310 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Distribution of the number ofhe k nodes of residual

degree one [Amraoui, et al. '03℄
Amraoui, et al '03

The ditribution of the number of he k nodes of residual graphtends to a Gaussian.
ementsPSfrag repla ements;1r5;1r5;1r6;1r6;1r10;1r10;1tt

g

minfr5;1 ; r10;1 gy5y5y10y10; r10;1(3,6)-regular ensemble, blo k-length 2048, hannel erasure probability 0.425

11 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Expe ted number of12 / 18

he k nodes of residual degree 1

theorem1For detailedly represented ensembles, r ;1 are written assrs ;1=Xdl (i ; s )(i=2+ 1

Xdr

ijdXl



=2i=2

 (i )

1

Xdr ) #i

 (j )yi

j1ysjsi " (j )yj

1s

1:=2where(the number of he k nodes of residual degree 1 and original degree s )(the total number of the edges in Tannar graph)y := (y2 ; y3 ; : : : ; yd ) is given as a solution of di erential equations

rs ;1:=rDetailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Expe ted number ofhe k nodes of residual degree 1r5;10.012

ag repla ements

13 / 18

r6;10.01

r5;10.008

r6;1r10;1 0.006
t

minfr5;1 ; r10;1 g 0.004
y50.002

y10
00

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

the fraction of the variable nodes in residual graphrs ;1nodes of residual degree 1 and original degree ):= (the number of he k(thetotal number of edges)sDetailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Graphi al interpretation of su

essful de odingtheorem2

A path from the point (1; 1; : : : ; 1) to (0; 0; : : : ; 0) exist in the sets rs ;1 (y) > 0fy j min()gthe de oding is su essful.

14 / 18

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Graphi al interpretation of su

15 / 18

essful de oding

1.00.8ag repla ements

0.6

r5;1y10
r6;1r10;10.4tminfr5;1 ; r10;1 g

0.00
-0.01
-0.02
density evolution

0.2

y5
y10

0.0
0.0

0.2

0.4

0.6

0.8

1.0y5

 = 0:40,  (3; 5) = 0:12;  (3:10) = 0:18;  (4; 5) = 0:28;  (4:10) = 0:42

The de oding is su essful.

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Graphi al interpretation of su

16 / 18

essful de oding

1.0

0.8

ag repla ements
r5;10.6

r6;1y10r10;10.4t

minfr5;1 ; r10;1 g

0.00
-0.01
-0.02
-0.03
density evolution

0.2

y5
y10

0.0

0.0

0.2

0.4

0.6

0.8

1.0y5

 = 0:415,  (3; 5) = 0:12;  (3:10) = 0:18;  (4; 5) = 0:28;  (4:10) = 0:42

The de oding is not su essful.

Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

Con lusion and Future work
Con lusion

We derive the expe ted number of he k nodes of residual
degree 1
We give a graphi al interpretation of su essful de oding
Future work

derive the varian e of the number of he k nodes of residual
degree 1
analyze the waterfall region with joint degree distributions
optimize detailedly represented ensembles

17 / 18Detailed Evolution of Degree Distributions in Residual Graphs with Joint Degree Distribtuions

18 / 18bibliography[1℄ K. Kasai, T. Shibuya and K. Sakaniwa, \Detailedly Represented
Irregular Low-Density Parity-Che k Codes," IEICE Trans. on
Fundamentals, vol.E86-A, no.10, pp.2435-2444, 2003.
[2℄ A. Amraoui \Asymptoti and nite-length optimization ofLDPC odes," Ph.D. Thesis, EPFL, June 2006.
[3℄ M. Luby, M. Mitzenma her, A. Shokrollahi, D. A. Spielman,
and V. Stemann. \Pra ti al Loss-Resilient Codes," inPro eedings of the 29th annual ACM Symposium on Theory of, 1997, pp. 150-159.

Computing