Error Floors of Non-binary LDPC Codes
Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa
Tokyo Institute of Technology

2010/6/14

Outline
BackgroundNon-binary low-density parity-check (LDPC) codes
Existing works

Lowering the error floor
Condition for successful decoding under BP decoding
Modified cycle cancellation
Simulation results

Analysis of the error floors
Closed-form expression for error floor
Monotonicity of error floors

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}
It is empirically known that (2,k)-regular LDPC codes exhibit good
decoding performance.

v1c1c2c3c4

v2v3v4v5v6

h1,1 h1,2 h1,3 000 h2,1 0 h2,3 00 h2,6  0 h3,2 0 h3,4 h3,5 0 
000 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
NC := {x ∈ F2m | Hx = 0}
It is empirically known that (2,k)-regular LDPC codes exhibit good
decoding performance.

v1c1c2c3c4

v2v3v4v5v6

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 
00
0 h4,4 h4,5 h4,6

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

Example : Zigzag cycle yields codewordh1,1 h1,2 h1,3 000 h2,1 0 h2,3 0
0 h2,6 H= 0 h3,2 0
1 α40 000 α6 α10 h4,6


(0 0 0 α4 1 0) ∈ C

1 α4=0det
α6 α10Zigzag cycle yields codeword.
Cycle cancellation [Poulliat 2008]
Existing work : Cycle cancellation [Poulliat 2008]
Design edge labels in zigzag cycle so that the corresponding sub-matrices
H̃ are nonsingular, i.e.,det H̃ 6= 0.


h1 h2 0H̃ =  0 h3 h4 h6 0 h5
det H̃ = h1 h3 h5 + h2 h4 h6 6= 0⇐⇒

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

β=3Y−16= 1
h2i −1 h2ii =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)

Motivation
Some zigzag cycles designed by cycle cancellation can cause decoding
failure under BP decoding over the BEC.

Example : Decoding failure under BP decoding
Zigzag cycle N = 2, F24
E1 = {0, α0 , α5 , α10 }E2 = {0, α2 , α7 , α12 }Note that for the BEC
All the nonzero entries in a message are equal
Messages are represented by the set of indexes of nonzero entries

Condition for successful decoding for zigzag cycle codes
Theorem 1
A necessary condition for successful decoding under BP decoding for
zigzag cycle code over the BEC is that1

not all bits are erased

2

cycle parameter β is not in the proper subfield of F2m , i.e.,[2m −1β 6∈ Hm :={αi 2r −1 | i = 0, 1, . . . , 2r − 2}
r >0:r |m,r 6=m

α : primitive element of F2m
cycleQparameter−1β = ni=1 h2i −1 h2i

Modified cycle cancellation
Modified cycle cancellation
Design the edge labels in zigzag cycle such thatβ 6∈ Hm .
Field
F24
F25
F26
F27
F28
F29

The elements of Hm
1, α5 , α10
1
1, α9 , α18 , α21 , α27 , α36 , α42 , α45 , α54
1
1, α17 , α34 , α51 , α68 , α85 , α102 , α119 ,α136 , α153 , α170 , α187 , α204 , α221 , α238
1, α73 , α146 , α219 , α292 , α365 , α438

Simulation result : Zigzag cycle codes (1)block erasure rate

100
10-1
10-2
10-3β=1β = α21β = α9β = α1theoretical

10-4
10-5
0.4

0.5

0.6

0.70.80.9

channel erasure probability

1ǫZigzag cycle code, N = 3 (18 bits), F26
H6 = {1, α9 , α18 , α21 , α27 , α36 , α42 , α45 , α54 }The theoretical block erasure rate is given by ǫ18 .

Simulation result : Zigzag cycle codes (2)block erasure rate

100

simulation
theoretical

10-1

10-2-310010203040
cycle parameter

5060

Zigzag cycle code N = 3 (18 bits), F26 , ǫ = 0.7
H6 = {1, α9 , α18 , α21 , α27 , α36 , α42 , α45 , α54 }The theoretical block erasure rate is given by 0.718 ≈ 1.63 × 10−3.

Simulation result : LDPC codes
100
symbol erasure rate

10-1
10-2
10-3
10-4
10-5
10-6
10-7
10-8

cycle cancellation
proposed

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
channel erasure probability(2,3)-regular LDPC codes
Symbol code length : 315 symbols (315 × 4 = 1260 bits)
Order of Galois field : 16 = 24

Closed-form expression of error floors
Definition : LDPC code ensemble
Let LDPC(N, m, λ, ρ) denote the set of LDPC codes of symbol code
length N over F2m defined by Tanner graphs with a degree distribution
pair (λ, ρ).

Definition : Expurgate ensemble
Let E(N, m, sc , H, λ, ρ) be the set of codes in LDPC(N, m, λ, ρ) whichcontains no zigzag cycles of size at most sc with cycle parameter β ∈ H.

Conjecture 1 : Error floor for NB-LDPC codes
Let Ps (N, sc , ǫ) be the symbol erasure rate of E(N, m, sc , Hm , λ, ρ) overBEC(ǫ). Then,limlim NPs (N, sc , ǫ) =sc →∞ N→∞1 λ′ (0)ρ′ (1)ǫm
2 1 − λ′ (0)ρ′ (1)ǫm

Simulation result : Error floor
100symbol erasure rate

10-1
10-2
10-3
10-4
10-5
10-6
10-7

ConjectureE(315, 4, 7, H4, x, x 2 )10-8
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
channel erasure probability(2,3)-regular LDPC code ensemble designed by our proposed method
Symbol code length : 315 symbols (315 × 4 = 1260 bits)
Order of Galois filed : 16 = 24

Monotonicity of error floor
Conjecture 2 : Monotonicity of error floor
Let n := mN denote bit code length.
Let Pb (n, m, sc , ǫ) be the bit erasure rate of E(N, m, sc , Hm , λ, ρ) overBEC(ǫ).
f (m, ǫ) := lim lim nPb (n, m, sc , ǫ)
sc →∞ n→∞m λ′ (0)ρ′ (1)ǫm
=2 1 − λ′ (0)ρ′ (1)ǫm

(From Conjecture 1)

1For 0 < ǫ < (λ′ (0)ρ′ (1))− m and λ′ (0)ρ′ (1) > 1,f (m, ǫ) > f (m + 1, ǫ).

Monotonicity of error floor
101100f (m, ǫ)

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

m=1
m=2
m=3
m=4
m=5
m=6
m=7
m=8
m=910-5
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
channel erasure probability(2,3)-regular LDPC codes ensemble constructed by our proposed method

Conclusion and future work
Conclusion
We derive a necessary condition for successful decoding for zigzag
cycle codes over the BEC under BP decoding.
We propose a design method lowering error floor.
We analyze the error floors for the expurgated ensembles constructedby proposed method.
We show that error floors decrease as the size of Galois field increases.

Future work
Clarify the condition for successful decoding for 3 imbricate cycles.

Simulation result : LDPC codes over AWGNC
100Cycle cancellation
Proposed

symbol error rate

10-1
10-2
10-3
10-4
10-5
10-6
10-7
-4

-2

0SNR

24(2,3)-regular LDPC codes ensemble over AWGNC
symbol code length : 315 symbols
Order of Galois field : 246