Weight Distribution for Non-binary Cluster LDPC
Code Ensemble
Takayuki Nozaki1 , Masaki Maehara2 , Kenta Kasai2 ,Kohichi Sakaniwa2
1 Kanagawa University
2 Tokyo Institute of Technology

July 12th, 2013

1 / 25

Introduction (1)Non-binary cluster LDPC codes [SD2011]
One of a class of non-binary LDPC code
A generalization of non-binary LDPC code defined over general lineargroup
Good decoding performance in low rate codes

Contribution of this research
For irregular non-binary cluster LDPC code ensemble,
We derive the symbol and bit weight distributions
We show the growth rate of symbol and bit weight distributions
We give a condition that the relative minimum distance linearly grows
with the code length[SD2011] V.Savin and D.Declercq, ”Linear growing minimum distance of ultra-sparsenon-binary cluster-LDPC codes,” ISIT2011, pp.523–527, July-Aug. 20112 / 25

Introduction (2)Weight distribution for non-binary LDPC code ensembles
Gallager
Kasai et al.
Andriyanova et al.
This research

Gallager code ensemble over Z/qZ
Irregular ensemble over F2m
Regular ensemble over GL(m, F2 )Irregular cluster ensemble

symbol-WD
symbol and bit-WDbit-WD
symbol and bit-WD

Related research for minimum distance of non-binary cluster LDPCcodes[SD2011] shows that there exist (2, dc )-regular expurgated ensemble
whose minimum distance linearly grows with the code length
This research shows a condition that the relative minimum distancelinear grows with the code length for random irregular non-binarycluster LDPC code ensemble.

3 / 25

Outline
1

Introduction

2

Preliminaries

3

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

4Growth Rate for Non-binary Cluster LDPC Code Ensemble
Growth Rate
Analysis of Small Weight Codeword
Numerical Examples

5Conclusion

4 / 25

Non-binary Cluster LDPC Code[Definition] Non-binary cluster LDPC code
Defined by a Tanner graph G
Each edge in Tanner graphs is labeled by cluster, which is p × r
full-rank matrix
A symbol (r-bits) is assigned to each variable node
Xr N
TThj,i xi = 0 ∀j ∈ [1, M ]C(G) := (x1 , . . . , xN ) ∈ (F2 ) |i∈Nc (j)p×rfull-rankmatrix✉r-bitsp-bits
5 / 25

Irregular Non-binary Cluster LDPC Code Ensemble[Definition] Irregular non-binary cluster LDPC code ensemble
G(N, p, r, λ, ρ)N : the number of variable nodes (symbol code length)p, r : size of clusterλ, ρ : degree distribution pair (edge perspective)
Bit code length n := rN
Degree distribution pair (node perspective) (L, R)
R1

R1

Li := λi / i 0 λ(x)dx , Rj := ρj / j 0 ρ(x)dx
R1
Total number of edges E := N/ 0 λ(x)dx
Fraction of check nodes κR1
ρ(x)dx#(check nodes)κ :== R 01#(variable nodes)
λ(x)dx0

Design rate

1 − κp/r

6 / 25

Outline
1Introduction

2Preliminaries

3

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

4Growth Rate for Non-binary Cluster LDPC Code Ensemble
Growth Rate
Analysis of Small Weight Codeword
Numerical Examples

5Conclusion

7 / 25

Weight of Codeword[Definition] Symbol and bit weight of a codeword
Symbol weight of a codeword xw(x) := |{i ∈ [1, N ] | xi 6= 0}|
Bit weight of a codeword xwb (x) := |{(i, j) ∈ [1, N ] × [1, r] | xi,j 6= 0}|[Definition] Average number of codeword of weight ℓ
For an ensemble G = G(N, p, r, λ, ρ),average number of codeword of symbol weight ℓ
PA(ℓ) = |G|−1 G∈G |{x ∈ C(G) | w(x) = ℓ}|average number of codeword of bit weight ℓ
PAb (ℓ) = |G|−1 G∈G |{x ∈ C(G) | wb (x) = ℓ}|

8 / 25

Symbol Weight Distribution[Theorem 1] Symbol weight distribution
For the irregular non-binary cluster LDPC code ensemble G(N, p, r, λ, ρ),
the average number of codewords of symbol weight ℓ isA(ℓ) =EXA(ℓ, k)

k=0EX



(2r − 1)ℓ coef P (s, t)N , sℓ tk coef Q(u)N , uk=,E
pkk (2 − 1)
k=0
LQQ
P (s, t) := i∈L 1 + sti i , Q(u) := j∈R fj (u)κRj ,
fj (u) := 2−p {1 + (2p − 1)u}j + (2p − 1)(1 − u)j ,where coef(g(s, t), si tj ) is the coefficient of the term si tj of a polynomialg(s, t).
9 / 25

Bit Weight Distribution[Theorem 2] Bit weight distribution
For the irregular non-binary cluster LDPC code ensemble G(N, p, r, λ, ρ),
the average number of codewords of bit weight ℓ isEXcoef Pb (s, t)n , sℓ tk coef Qb (u)n , uk
Ab (ℓ) =,E pkk (2 − 1)
k=0
QPb (s, t) := i∈L [1 + {(1 + s)r − 1}ti ]Li /r ,QQb (u) := j∈R fj (u)κRj /r ,
fj (u) := 2−p {1 + (2p − 1)u}j + (2p − 1)(1 − u)j .

10 / 25

Outline1Introduction

2Preliminaries

3

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

4Growth Rate for Non-binary Cluster LDPC Code Ensemble
Growth Rate
Analysis of Small Weight Codeword
Numerical Examples

5Conclusion

11 / 25

Growth Rate of Weight Distribution[Definition] Growth rate
Growth rate of symbol weight distribution
γ(ω) := lim N −1 log2r A(ωN ) = lim (rN )−1 log A(ωN )
N →∞

N →∞

Growth rate of bit weight distribution
γb (ωb ) := lim n−1 log Ab (ωb n)n→∞

Properties
The following approximations holdAb (ωb n) ≈ 2γb (ωb )n .

If γ(ω) < 0 for ω ∈ (0, δ∗ ), there areexponentially few codewords of symbol
weight ωN .

growth rate

A(ωN ) ≈ 2γ(ω)rN ,5.0e-05

0.0e+00-5.0e-05
00.0010.002

ωδ∗ 0.003
12 / 25

Growth Rate of Symbol Weight Distribution[Theorem 3] Growth rate of symbol weight distribution
Define ω = ℓ/N and ǫ := E/N .
For G(N, p, r, λ, ρ) with sufficiently large N and for 0 < ω < 1,the growth rate γ(ω) of symbol weight distribution is given by
γ(ω) = supinfr −1 log P (s, t) + log Q(u) − ǫh(β/ǫ)β>0 s>0,t>0,u>0− β log[tu(2p − 1)] − ω log[s/(2r − 1)] ,where h(x) := −x log x − (1 − x) log(1 − x) for 0 < x < 1.
A point (s, t, u) achieving the infimum is a solution of
ω=s ∂P,P ∂s

β=t ∂P,P ∂t

β=u ∂Q.
Q ∂u

The value β giving the supremum needs to satisfy the stationary condition
β = (2p − 1)tu(ǫ − β).
13 / 25Growth Rate of Bit Weight Distribution[Theorem 4] Growth rate of bit weight distribution
Define ωb = ℓ/n and ǫb := E/n.
For G(N, p, r, λ, ρ) with sufficiently large n and for 0 < ωb < 1, thegrowth rate γb (ωb ) of the bit weight distribution is given byγb (ωb ) = supinflog Pb (s, t) + log Qb (u)βb >0 s>0,t>0,u>0− ǫb h(βb /ǫb ) − βb log(tu(2p − 1)) − ωb log s .

A point (s, t, u) achieving the infimum is given in a solution ofωb =s ∂Pb,
Pb ∂sβb =t ∂Pb,
Pb ∂tβb =u ∂Qb.
Qb ∂u

The value βb giving the supremum needs to satisfy the stationary condition
βb = (2p − 1)tu(ǫb − βb ).
14 / 25

Derivations of Growth Rates of Weight Distributions[Lemma 1] Derivation of growth rate of symbol weight distribution
The derivation of growth rate γ(ω) isdγ
1s(ω)(ω) = − log r.
dωr
2 −1

[Lemma 2] Derivation of growth rate of bit weight distribution
The derivation of growth rate γb (ωb ) isdγb(ωb ) = − log s(ωb ).
dωb15 / 25

Outline
1Introduction

2Preliminaries

3

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

4Growth Rate for Non-binary Cluster LDPC Code Ensemble
Growth Rate
Analysis of Small Weight Codeword
Numerical Examples

5Conclusion

16 / 25

Growth Rate for Small Weight (1)5.0e-05

A(ωN ) ≈ 2γ(ω)rN ,Ab (ωb n) ≈ 2γb (ωb )n .

If γ(ω) < 0 for ω ∈ (0, δ∗ ), there areexponentially few codewords of symbol
weight ωN .

growth rate

Properties of growth rate (Written again)
The following approximations hold

0.0e+00-5.0e-05
00.0010.002

ωδ∗ 0.003[Definition] Normalized typical minimum distanceDefineδ∗ := inf{ω > 0 | γ(ω) ≥ 0},δb∗ := inf{ωb > 0 | γb (ωb ) ≥ 0}.

Properties
For G(N, p, r, λ, ρ), if the normalized typical minimum distance is strictly
positive, then the typical minimum distance linearly grows with code
length.
17 / 25

Growth Rate for Small Weight (2)[Theorem 5] Growth rate for small symbol weight
For G(N, p, r, λ, ρ) with λ2 > 0, the growth rate γ(ω) for small ω isω
2p − 1γ(ω) = − log+ o(ω),
r(2r − 1)λ′ (0)ρ′ (1)(x)= 0 and
where f (x) = o(g(x)) means limxց0 fg(x)P′′
λ (0)ρ (1) = λ2 j∈R (j − 1)ρj .

[Theorem 6] Growth rate for small bit weight
For G(N, p, r, λ, ρ) with λ2 > 0, the growth rate γb (ωb ) for small ωb isγb (ωb ) = −ωb log


1/r
2p − 1− 1 + o(ωb ).
+1λ′ (0)ρ′ (1)18 / 25

Growth Rate for Small Weight (3)[Corollary] Condition that typical minimum distance linearly grows
with code length
For G(N, p, r, λ, ρ) with sufficiently large N , the normalized typicalminimum distances δ∗ and δb∗ are strictly positive if
λ′ (0)ρ′ (1) <2p − 1.
2r − 1[Remark] Comparison with other non-binary LDPC codes
Case for non-binary LDPC code over Galois fieldλ′ (0)ρ′ (1) < 1.
Case for non-binary LDPC code defined by general linear groupλ′ (0)ρ′ (1) < 1.
Hence, for (2,dc )-regular non-binary LDPC code, δ∗ = 0 and δb∗ = 0.
19 / 25

Growth Rate for (2,dc)-Regular LDPC Code Ensembleλ′ (0)ρ′ (1) <2p − 1.
2r − 1[Example] For (2,8)-regular LDPC code ensemble with rate 1/2
λ′ (0)ρ′ (1) = 7, p/r = 2.
2p − 1= 3.
If (p, r) = (2, 1), r
2 −1
2p − 1If (p, r) = (4, 2), r
= 5.
2 −1
2p − 1= 9.
If (p, r) = (6, 3), r
2 −1

Hence, δ∗ = 0 and δb∗ = 0
Hence, δ∗ = 0 and δb∗ = 0Hence, δ∗ > 0 and δb∗ > 020 / 25

Outline
1Introduction

2Preliminaries

3Weight Distribution for Non-binary Cluster LDPC Code Ensemble

4Growth Rate for Non-binary Cluster LDPC Code Ensemble
Growth Rate
Analysis of Small Weight Codeword
Numerical Examples

5Conclusion

21 / 25

Numerical Example (1 : Symbol Weight)
5.0e-04

p=2,r=1
p=4,r=2
p=6,r=3
p=8,r=4
p=10,r=5
p=12,r=6
p=14,r=7
p=16,r=8
p=18,r=90-0.5
0.0

Growth rate

Growth rate

0.50.20.40.6

ω0.80.0e+00
p=2,r=1
p=4,r=2
p=6,r=3
p=8,r=4
p=10,r=5
p=12,r=6
p=14,r=7
p=16,r=8
p=18,r=9-5.0e-04

1.0-1.0e-03
0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035

ω(2,8)-regular non-binary cluster LDPC code ensemble

22 / 25

Numerical Example (2 : Bit Weight)
0.5

0.00020.0-0.50.0

Growth rate

Growth rate

0.0000p=2,r=1
p=4,r=2
p=6,r=3
p=8,r=4
p=10,r=5
p=12,r=6
p=14,r=7
p=16,r=8
p=18,r=9
random code0.2-0.0002
p=2,r=1
p=4,r=2
p=6,r=3
p=8,r=4
p=10,r=5
p=12,r=6
p=14,r=7
p=16,r=8
p=18,r=9-0.0004-0.0006-0.0008

0.4

0.6

ωb0.8

1.0-0.0010
0.000

0.005

0.010

0.015

ωb

(2,8)-regular non-binary cluster LDPC code ensemble

23 / 25

Numerical Example (3 : Normalized Typical MinimumDistance)

0.02

0.010

δb∗

0.015

δ∗0.03

0.01

0.005

0(2,1) (4,2) (6,3) (8,4) (10,5) (12,6) (14,7) (16,8) (18,9)(p, r)

Symbol case0.000(2,1) (4,2) (6,3) (8,4) (10,5) (12,6) (14,7) (16,8) (18,9)(p, r)

Bit case(2,8)-regular non-binary cluster LDPC code ensemble

24 / 25

Conclusion
Summary
We derive the symbol and bit weight distributions
We show the growth rate of symbol and bit weight distributions
We give a condition that the relative minimum distance linearly grows
with the code lengthλ′ (0)ρ′ (1) <2p − 1.
2r − 125 / 25