Analysis of Stopping Constellation Distribution
for Irregular Non-Binary LDPC Code Ensemble
Takayuki Nozaki, Kenta Kasai, Kohich Sakaniwa
Dept. of Communications and Integrated Systems
Tokyo Institute of Technology

ISIT 2011
July 2th, 2011

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

1 / 19

Backgroundstopping constellation
Stopping constellations are the fixed points of BP decoder for non-binary
LDPC codes
Relative works
Weight distribution
Binary irregular
NB regular
NB irregular

Nozaki et al. (Titech)

Di et al. (2006)
Kasai et al. (2008)
Kasai et al. (2008)

Stoppingsetdist.
Stopping constellation dist.
Orlitsky et al. (2005)
This researchThis research

Analysis of SC-distribution for NB-LDPC

8/2/2011

2 / 19Outline
1

BackgroundNon-binary LDPC code defined over general linear group
Non-binary peeling algorithm
Stopping constellation2

Stopping constellation distributions
Stopping constellation distributions
Asymptotic analysis
Numerical examples

3Conclusion and future work

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

3 / 19Non-binary low-density parity-check (LDPC) code
[Definition] Non-binary LDPC code
PTT
C := (x1 , x2 , . . . , xN ) ∈ FmN| ∀c ∈ C
2i∈N (c) Hi,c xi = 0

C : Set of the check nodes
N (c) : Set of the variable nodes connecting to the node c
Hi,c : Non-singular m × m-matrix (i.e., element of general linear group)H1,1 H1,20
H1,4
 H2,1 H2,2 H2,30 00
H3,3 H3,4

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

4 / 19Non-binary irregular LDPC code ensemble
EGL(N, λ, ρ, m)
N = 6, m = 4, ξ = 20, r = 13416812, λ4 = , ρ4 = , ρ6 =2020
20202422L 2 = , L 4 = , R4 = , R6 =664
4
λ2 =random permutation

λi : Fraction of edges connecting to variable node of degree iρj : Fraction of edges connecting to check node of degree j
Li : Fraction of variable nodes of degree i
Rj : Fraction of check node of degree j
N : Symbol code lengthξ : Total number of edgesr : Design rate
Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

5 / 19Non-binary peeling algorithm [Rathi 2008][Definition] StateEv : Set of candidate symbols for the decoding result for variable node v[Property]: Ev is a linear subspace of Fm
2 if all-zero codewords are sent.
All-zero assumption holds for non-binary LDPC code over the BEC.

Non-binary peeling algorithm
Decoding proceeds as the dimensions of the states decrease[Rathi 2008] V. Rathi, “Conditional entropy of non-binary LDPC codes over the BEC,”
in proc. ISIT2008, July 2008.
Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

6 / 19Peeling decoder

received signals

state?
?

0?

m=2

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

7 / 19Peeling decoder

state

m=2

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

8 / 19Peeling decoder

state

m=2

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

9 / 19

Stopping constellation [Rathi 2008][Definition] Stopping constellation
Stopping constellation {Ev }v∈V X
−1Hc,i Ei
Ev ⊆ Hc,v∀v ∈ V, ∀c ∈ N (v)i∈N (c)\{v}

Ei : State for the i-th variable nodeHc,v : Label in the edges connecting to check node c and variable node v
V : Set of the variable nodes
N (c) : Set of nodes connecting to the check node c

HE := {Hv | v ∈ E}, for invertible matrix H and E ∈ Fm
2 ,mX
X
Ei := {vj | vj ∈ Ej }, ∀Ei ∈ Fm
2 .
i=1

Nozaki et al. (Titech)jAnalysis of SC-distribution for NB-LDPC

8/2/2011

10 / 19

Stopping Constellation Distribution
Weight of stopping constellationℓ := {v ∈ V | dimEv 6= 0}
AG (ℓ) : The number of stopping constellation of weight ℓ for
G ∈ EGL(N, λ, ρ, m)Average stopping constellation distribution
A(ℓ) :=X

G∈EGL(N,λ,ρ,m)Nozaki et al. (Titech)

AG (ℓ)|EGL(N, λ, ρ, m)|Analysis of SC-distribution for NB-LDPC

8/2/2011

11 / 19

Average Stopping Constellation Distribution[Theorem 1] Average Stopping Constellation Distribution
A(ℓ) =b:XPi bi =ξQbi bicoef((Q(s, t)P (u))N , tℓ mi=1 si ui ),Qmm bkξ
k=1b0 ,b1 ,...,bmkQP m j oLj
Q n, P (u) := k {fk (u)}Rk (1−r) ,Q(s, t) := j 1 + t mi=1 i sicoef(g(s, t, u), t[m] :=

Qm bi bibi bi
i=1 si ui ) : coefficient of t
i=1 si ui for polynomial g(s, t, u).

Qm

Qmi
i=1 (2 − 1),

fk (u) =d:

1Tk :=2Xi di =kPˆm˜i:=[m],[i][m − i]m”Ydui i

kd0 , d1 , . . . , dm

“Xi=1”
ξξ!
:=,b0 , b1 , . . . , bm
b0 !b1 ! · · · bm !
X[m]Q
2Tk ,[a(S)]kS⊂[1,k]a ∈D“kkak (S1 )ak (S2 ).

S1 ,S2 ⊂[1,k]:S1 6⊂S2 ,S1 6⊃S2Ppj
di ,Let pj be the smallest integer s.t. j ≤ i=0PP
Dk := {ak | S⊂[1,k] ak (S) = m, ak (S) = 0 for |S| = k − 1, S:j∈S ak (S) = m − pj }.
Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

12 / 19

Sketch of Proof for Theorem 1ℓ : weight of stopping constellationbi : the number of edges connecting to variable nodes with dimension i
12

For a given ℓ, b, the number of constellations of linear subspaces
satisfying constraints
Q forbivariable nodes iscoef(Q(s, t)N , tℓ mi=1 si )For a given b, the number of linear subspaces
P of constellations−1satisfying Ev ⊆ Hc,vi∈N (c)\{v} Hc,i Ei for all the check nodes
coef(P (u)N , ubi i )34

Forof edges satisfying constraints is
Qm a given b, the numberbii=0 bi !([m − i][i])The number of elements in EGL(N, λ, ρ, m) isξ![m]ξ

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

13 / 19

Asymptotic Analysis 1 : Growth Rate
Define the normalized weight as ω := ℓ/N , βi := bi /N .

[Definition] Growth rate
1log A(ωN )N →∞ Nγ(ω) := lim[Theorem 2] Growth rate of average number of stopping constellation
γ(ω) = supinf

log Q(s, t) + log P (u) − ω log tβ>0 s>0,t>0,u>0−= supinf

β>0 s>0,t>0,u>0Pm

i=1 βi logγ̂(ω, s, t, u).

m Pm
i=0 βi log βi − log ǫi si ui +A point which achieves the minimum of γ̂(ω, s, t, u) is the solution ofsi ∂Qui ∂Pt ∂Qβi =, βi =, ω=Q ∂si
Q ∂t
P ∂ui
Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

14 / 19

Sketch of proof for Theorem 2[Burshtein 2004] Theorem 3
1log coef(p(x1 , . . . , xm ), (xα1 1 · · · xαmm )N )N →∞ Np(x1 , . . . , xm )= inf log α1
x1 ,...,xm
x1 · · · xαmmlim

1 ,...,xm )A point x which achieves the minimum of log p(xis the solution ofα
x 1 ···xαm∀k ∈ {1, 2, . . . , m}1m∂p(x1 , . . . , xm )xk
= αkp(x1 , . . . , xm )∂xk
From this theorem and Theorem 1, we have Theorem 2.
[Burshtein 2004] D. Burshtein, and G. Miller, “Asymptotic enumeration method foranalyzing LDPC codes,” IEEE Trans. on Inform. Theory, Jun. 2004
Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

15 / 19

Asymptotic Analysis 2 : Differential of growth rate
[Lemma 1] Differential of growth ratedγ(ω)= − log t(ω).
dω[Note]: the paramters t, β, u, s depend only on ω

[Theorem 3] Small weight Stopping Constellations
For N → ∞, ω → 0 and EGL(N, λ, ρ, m) s.t. λ2 > 0,γ(ω) = log[λ′ (0)ρ′ (1)]ω + o(ω).

[Discussion] For small ω
If λ′ (0)ρ′ (1) > 1, then γ(ω) > 0
If λ′ (0)ρ′ (1) < 1, then γ(ω) < 0

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

16 / 19

Numerical example (1)51.6e-06
1.4e-06
growth rate

4growth rate

1.8e-06

m=1
m=2
m=3
m=4

3
2

1.2e-06

m=1
m=2
m=3
m=4log(3)1.0e-06
8.0e-076.0e-071

4.0e-0700.0

0.0e+00
0.0e+00 2.0e-07 4.0e-07 6.0e-07 8.0e-07 1.0e-06

2.0e-070.20.4

ω

0.6

0.8

1.0

ω

Growth rate for the (2,4)-regular non-binary LDPC ensembles

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

17 / 19

4.5
4
3.5
3
2.5
2
1.5
10.02

m=1
m=2
m=3
m=40.015
growth rate

growth rate

Numerical example (2)

0.5
0-0.5
0.0

m=1
m=2
m=3
m=40.010.005
0-0.005

0.2

0.4

ω

0.60.8

1.0-0.01
0.000

0.005

0.010

ω

0.015

0.020

Growth rate for the (3,6)-regular non-binary LDPC ensembles

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

18 / 19

Conclusion and future work
Conclusion
For irregular non-binary LDPC codes defined over general linear group,
we give the stopping constellation distributions
we derive the growth rate for the average of stopping constellation
distributions

Future work
To derive the stopping constellation distribution for irregular
non-binary LDPC codes defined over finite field.

Nozaki et al. (Titech)

Analysis of SC-distribution for NB-LDPC

8/2/2011

19 / 19