Analysis of Error Floors of Non-binary LDPC Codes
over MBIOS channel
Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa
Dept. Communications and Integrated Systems
Tokyo Institute of Technology

ICC 2011 Kyoto
June 7th, 2011

Outline
1

BackgroundNon-binary low-density parity-check (LDPC) codes
Existing methods for lowering error floors
Channel model2

Lowerling decoding error rates in the error floor over MBIOS channel
Condition for successful decoding
Code design method to lower error floor
Simulation results

3

Analysis of symbol error rates in error floorsLower bound on symbol error rate in error floor
Simulation results

4

Conclusion and related works

Outline
1

BackgroundNon-binary low-density parity-check (LDPC) codes
Existing methods for lowering error floors
Channel model2

Lowerling decoding error rates in the error floor over MBIOS channel
Condition for successful decoding
Code design method to lower error floor
Simulation results

3

Analysis of symbol error rates in error floors
Lower bound on symbol error rate in error floor
Simulation results

4

Conclusion and related works

Non-binary low-density parity-check (LDPC) codes
Non-binary LDPC code
Linear code defined by a sparse parity check matrix H ∈ FM×N2mN
C := {x ∈ F2m | Hx = 0}v1c1c2c3c4

v2

v3v4v5v6

h1,1 h1,2 h1,3 000 h2,1 0 h2,3 00 h2,6  0 h3,2 0 h3,4 h3,5 0 00
0 h4,4 h4,5 h4,6

Non-binary low-density parity-check (LDPC) codes
Non-binary LDPC code
Linear code defined by a sparse parity check matrix H ∈ FM×N2m
N
C := {x ∈ F2m | Hx = 0}v1c1c2c3c4v2v3v4v5v6


h1,1 h1,2 h1,3 000 h2,1 0 h2,3 0
0 h2,6  0 h3,2 0 h3,4 h3,5 0 000 h4,4 h4,5 h4,6

Zigzag cycle
Cycle constructed by the variable nodes ofdegree 2

Zigzag cycles degrade decoding performance
Error floors are mainly caused by codewords of small weight.

Example : Zigzag cycle yields codeword
α : primitive element of F2m

h1,1 h1,2 h1,3 000 h2,1 0 h2,3 00 h2,6 H= 0 h3,2 0
1 α40 000 α6 α10 h4,6
(0 0 0 α4 1 0) ∈ C


1 α4det=0
α6 α10Zigzag cycle yields codeword.
Cycle cancellation [Poulliat 2008]
Existing method : Cycle cancellation [Poulliat 2008]
Design edge labels in zigzag cycle so thatdet H̃ 6= 0.
h1 h2 0
H̃ =  0 h3 h4 h6 0 h5
det H̃ = h1 h3 h5 + h2 h4 h6 6= 0⇐⇒

β = h1−1 h2 h3−1 h4 h5−1 h6 6= 1⇐⇒

β=3Yi =1−1
h2i−1 h2i 6= 1

[Poulliat 2008] C. Poulliat, M. Fossorier and D. Declercq, “Design of regular (2,dc )-LDPC codes over GF(q) using their binary images”, IEEE Trans. Comm. (2008)

Binary erasure channel (BEC) case [ISIT 2010]
Existing method: Modified cycle cancellation [ISIT 2010]
Design edge labels in zigzag cycle so thaton 2m −1[β 6∈
αi 2r −1 | i = 0, 1, . . . , 2r − 2r >0:r |m,r 6=m

Symbol erasure rate10010-110-210-3

10-4

10-510-610-7

0.1

Symbol code length : 315
Order of Galois field : 16Cycle cancellation
ProposedLower bound
0.2

0.3

0.4

0.5

0.6

0.7

0.8

Channel erasure probability[ISIT 2010] T. Nozaki, K. Kasai and K. Sakaniwa, “Error floors of non-binary LDPC
codes,” ISIT 2010

Channel Model
Memoryless binary-input output-symmetric (MBIOS) channel
Memoryless
pY |X (y | x) =symmetricYtpYt |Xt (yt | xt )pYt |Xt (yt | 0) = pYt |Xt (−yt | 1)

Example : Member of MBIOS channel
Binary erasure channel (BEC)
Binary symmetric channel (BSC)
Additive white Gaussian noise (AWGN) channel

Outline
1

BackgroundNon-binary low-density parity-check (LDPC) codes
Existing methods for lowering error floors
Channel model2

Lowerling decoding error rates in the error floor over MBIOS channel
Condition for successful decoding
Code design method to lower error floor
Simulation results

3

Analysis of symbol error rates in error floors
Lower bound on symbol error rate in error floor
Simulation results

4Conclusion and related works

Condition for successful decoding
Definition : zigzag cycle code

symbol code length 3

Q−1
β = si=1 h2i−1 h2i−1
γi = h2i −1 h2i
s : symbol code length
σ : the order of βCk (γ) : γ-th entry of the initial message ofk-th variable node

Lemma 1 : Condition for successful decoding
BP decoding succeeds for zigzag cycle code of length sm⇐⇒ for all x ∈ Aβ := {αj | j = 0, 1, . . . , 2 σ−1 − 1}
sYk=1(Ck (0))σ >s
σ−1YY

t=0 k=1

k−1Y γs .
Ck β t x
s=1

Condition for the lowest decoding error rate
Theorem 1
The zigzag cycles with cycle parameter β 6∈ Hm have good decoding
performance, wheren 2m −1o[Hm :=αi r | i = 0, . . . , r − 1 .
0<r <2m −1:r |2m −1

Simulation result
block error rate

10-1

additive white Gaussian noise(AWGN) channel
σ2 = 1
Zigzag cycle code
Symbol code length : 3
Order of Galois field : 16

10-2
10-3
10-4

α0 α2 α4 α6 α8 α10 α12 α14β

Construction of code
Proposition 1: Design method to lower error floor for MBIOS channel
Design edge labels in zigzag cycle so thatn 2m −1o[β 6∈ Hm =αi r | i = 0, . . . , r − 1 .
0<r <2m −1:r |2m −1

Note : BEC case
Design edge labels in zigzag cycle so thaton 2m −1[β 6∈
αi 2r −1 | i = 0, . . . , r − 1 .
r >0:r |m,r 6=mField
F24

The elements of Hm
1, α3 , α5 , α6 , α9 , α10 , α12F261, α3 , α6 , α7 , α9 , α12 , α14 , α15 , α18 , α21 , α24 , α25 , α27 , α28 , α30 ,α33 , α35 , α36 , α39 , α42 , α45 , α48 , α49 , α51 , α54 , α56 , α57 , α60

Simulation result (AWGN channel)
100Symbol error rate

10-1
10-2
10-3
10-410-5Cycle cancellation
Proposed

10-6
10-7-4-2

024Eb/N0 [dB](2,3)-regular LDPC code ensemble
Symbol code length : 315 symbols
Order of Galois field : 16

68

Simulation result (BSC)100

Symbol error rate

10-1

Cycle cancellation
Proposed-2

1010-3
10-4
10-5
10-6
10-7
10-8
0.01

0.1

Crossover probability(2,3)-regular LDPC code ensemble
Symbol code length : 315 symbols
Order of Galois field : 16

Outline
1

BackgroundNon-binary low-density parity-check (LDPC) codes
Existing methods for lowering error floors
Channel model2

Lowerling decoding error rates in the error floor over MBIOS channel
Condition for successful decoding
Code design method to lower error floor
Simulation results

3

Analysis of symbol error rates in error floors
Lower bound on symbol error rate in error floor
Simulation results

4Conclusion and related works

Condition for successful decoding for zigzag cycle codes
Definition : Log-likelihood ratio
Yv ,i : i -th channel output in v -th variable node
Zv ,i := log

Pr(Yv ,i | Xv ,i = 0).
Pr(Yv ,i | Xv ,i = 1)

All zero assumption
The decoding error rate does not depend on the codeword.

Lemma2 : Condition for successful decoding
For zigzag cycle codes with cycle parameter β 6∈PHm under BP decoding
All the symbols are successfully decoded ⇐⇒ Pv ,i Zv ,i > 0.
All the errors are not recoverable⇐⇒
v ,i Zv ,i ≤ 0.

The decoding error
P probablities of all the zigzag cycle codes are lower
bounded by Pr( v ,i Zv ,i ≥ 0)

Analysis of error floors
Theorem 2 : Error floor for NB-LDPC codes
N : symbol
lengthP codePi−1λ(x) = i λi x , ρ(x) := i ρi x i −1 : degree distribution pair
µ := λ′ (0)ρ′ (1)sg : expurgation
parameter (no cycle of weight in {1, 2, . . . , sg − 1})
Ps P(sm)
Z:= v =1 m
i =1 Zv ,iLet Ps (E) be the symbol error rate of the code ensemble designed byproposed method over the MBIOS channel charactrized by its L-density aunder BP decoding.
R
1For a(x) exp[−x/2]dx < µ− m and the sufficiently large N, we have ∞
11 X s(sm)Ps (E) ≥.
µ Pr(Z≤ 0) + o2N s=sNg

Analysis of error floors
Corollary1 : AWGN channel caseFor AWGN channel with channel variance σ 2( √∞∞
1 X s  sm 
1Ps (E) ≥µQ+o, for σ 2 <m2N s=sσ
N2 log µg

where Q(y ) = √12π

R∞
yfor µ ≤ 1,for µ > 12

exp[− x2 ]dx.

Corollary2 : BSC case
For BSC with crossover probability ǫ <1−√

1−max{µ−2/m ,1},2  ∞
1
1 X s X ms
ms−i iµ(1 − ǫ)ǫ +oPs (E) ≥.
i2N s=sNci ≤ms/2

Simulation result : Lower bound (AWGN channel)
100Symbol error rate

10-1
10-2
10-3
10-4
10-5

Cycle cancellation
Proposed
Lower bound

10-6
10-7-4-2

0246Eb/N0 [dB](2,3)-regular LDPC code ensemble
Symbol code length : 315
Order of Galois field : 16sg = 1

8

Simulation result : Lower bound (BSC)100

Symbol error rate

10-1
10-2

Cycle Cancellation
Proposed
Lower bound

10-3
10-4
10-5
10-6
10-7
10-8
0.01

0.1

Crossover probability(2,3)-regular LDPC code ensemble
Symbol code length : 1200
Order of Galois field : 16sg = 2

Conclusion and related works
Conclusion
We derive a necessary and sufficient condition for successful decoding
for zigzag cycle codes over the MBIOS channel under BP decoding.
We propose a design method lowering error floor.
We give a lower bound for the decoding error rates in the error floors
for the expurgated ensembles constructed by proposed method.

Related works
Analysis of error floors of non-binary LDPC codes over q-ary
symmetric channel
Analysis of error floors of non-binary LDPC codes defined overgeneral linear groups