Analysis of Error Floors of Generalized Non-binary
LDPC Codes over q-ary Memoryless SymmetricChannels
Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa
Tokyo Institute of Technology

July 5, 2012

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 2012

1 / 22

Outline
1Introduction
Purposes of ResearchNon-binary LDPC Matrices over General Linear Groupq-ary Memoryless Symmetric Channel

2

Lowering Decoding Error Rates in Error Floors
Error Floors and Zigzag Cycles
A Method to lower Error Floors

3Analysis of Decoding Error Rates in Error Floors
Log-Likelihood Ratio
L-Density and Bhattacharyya Functional
Decoding Error Rate of Zigzag Cycle
Lower Bound of Error Floor
Simulation Results
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 20122 / 22

Purposes of Research
Purposes of research
For non-binary low-density parity-check (LDPC) matrices over generallinear (GL) groups over the q-ary memoryless symmetric (q-MS) channels
under belief propagation (BP) decoding,we propose a method to lower the error floors,
we analyze the decoding error rates in the error floors.
Contribution of the research
LDPC matrices over GF
LDPC matrices over GL group

MBIOS channel[NKS2011]
This researchq-MS channel
This researchThis research

GF : Galois field
MBIOS channel : Memoryless binary-input output-symmetric channel[NKS2011] T. Nozaki, K. Kasai, and K. Sakaniwa, “Analysis of Error Floors ofNon-binary LDPC Codes over MBIOS Channel,” IEICE Trans. Fundamentals,
vol. E94-A, no. 11, pp.2144–2152, Nov. 2011.
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC codeJuly 5, 20123 / 22

Non-binary LDPC Codes
GL group GL(m3 , F2m4 ) is the set of m3 × m3 invertible matrices over F2m4 .

Non-binary LDPC matrices over general linear groupN(x1 , x2 , . . . , xN ) ∈ (Fm2 ) |PT
Ti∈Nc (j) Hj,i xi = 0 ∀j ∈ {1, . . . , M }Let Nc (j) be the set of variable nodes
connecting to the j-th check node.
Hi,j ∈ F2mmatrices over GF
Decoding
complexity
Performanceon waterfall
Performanceon error floor
Nozaki et al. (Titech)

Hi,j ∈ GL(m3 , F2m4 ) Hi,j ∈ GL(m, F2 )matrices over GL grouplowmiddle

highlow

unknownhighunknown

unknown

unknown

Analysis of EF for non-binary LDPC code

July 5, 2012

4 / 22

Channel Modelq-MS channel [HSS2008]
X : input alphabet
Y : output alphabet
q-ary memoryless channel is symmetric if there exists T : Y × X → Y s.t.
∀x ∈ X , T (·, x) : Y → Y is bijection∀x ∈ X , Jacobian of T (·, x) : Y → Y is 1 (if Y is continuous)∀x1 , x2 ∈ X , ∀y ∈ Y, p(y | x1 ) = p(T (y, x2 − x1 ) | x2 )[Lemma 1] All-zero codeword assumption
The decoding error rate of the LDPC code over GL(m3 , F2m4 ) throughthe 2m1 -MS channel under BP decoding is independent of the sending
codeword.
[HSS2008] E. Hof, I. Sason, and S. Shamai, “Performance bounds for non-binary linear
block codes over memoryless symmetric channels,” IEEE trans. on IT, Mar. 2008

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 2012

5 / 22

Examples of q-MS channelsExamples of q-MS channels
memoryless binary input output symmetric (MBIOS) channels
binary erasure channel (BEC)
binary symmetric channel (BSC)
binary additive white Gaussian noise (BAWGN) channel

q-ary symmetric channel (q-SC)(1 − ǫ,p(y | x) =ǫ/(q − 1),

Nozaki et al. (Titech)

if y = x,
if y 6= x.

Analysis of EF for non-binary LDPC code

July 5, 2012

6 / 22

Channel Outputs to a Variable Node
We parameterize the number of channel outputs assigned to a variablenode.
In the case for m = 626 -MS channel

23 -MS channel

22 -MS channel

2-MS channel
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 20127 / 22Outline
1Introduction
Purposes of ResearchNon-binary LDPC Matrices over General Linear Groupq-ary Memoryless Symmetric Channel

2Lowering Decoding Error Rates in Error Floors
Error Floors and Zigzag Cycles
A Method to lower Error Floors

3

Analysis of Decoding Error Rates in Error Floors
Log-Likelihood Ratio
L-Density and Bhattacharyya Functional
Decoding Error Rate of Zigzag Cycle
Lower Bound of Error Floor
Simulation Results
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 20128 / 22

Error Floors and Zigzag Cycles
Error floors are mainly caused by small weight errors.

[Definition] Zigzag cycle
Zigzag cycles are circuit in the Tanner graph such that all the variablenodes are of degree two.
Property: Zigzag cycles cause small weight errors.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 20129 / 22

Methods to Lower Error Floors
To lower the error floors, we need to optimize the zigzag cycle.

Optimization of zigzag cycles
Optimize the structure of Tanner graph→ (e.g.) Progressive edge growth [HEA2005] removes the zigzag
cycles of small weight from Tanner graph.
Optimize the labels in the zigzag cycles→ This research optimizes the labels in the zigzag cycles to lower thedecoding error rates in the zigzag cycles.
[HEA2005] X.Y. Hu, E. Eleftherious, and D. Arnold, “Regular and irregular progressiveedge-growth Tanner graphs,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386–396,Jan. 2005

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201210 / 22

Optimization of Labels to Lower Error Floors
For zigzag cycle with labels H1,1 , H1,2 , H2,2 , . . . , Hw,w , Hw,1 ,−1−1−1 Hdefine χ := H1,1H1,2 H2,2· · · Hw,ww,1 .
The order σ of χ is the smallest integer s.t. χσ is identify matrix.

Label selection to lower the error floors
Optimize labels in the zigzag cycles satisfying σ = 2m3 m4 − 1 to lower theerror floors for non-binary LDPC code over GL(m3 , F2m4 ).
Outline of proof
1[Theorem 1] shows the condition for thesuccessful decoding of the zigzag cycles.

2[Corollary 1] gives the zigzag cycles whichhave the best decoding performance.

3[Lemma 2] gives the relation between
condition in [Corollary 1] and order of χ.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201211 / 22

Outline of Proof (1)[Definition] Orbit
Let hχi be the cyclic subgroup generated by χ ∈ GL(m3 , F2m4 ), i.e.,hχi := {χj | j = 0, 1, . . . }.
3
Define the orbit of x ∈ Fm
2m4 under hχi as hχix := {gx | g ∈ hχi}.
m3
3The set of orbits of x ∈ Fm
2m4 \ {0} under hχi forms partition of F2m4 \ {0}.
m3
A set of class representatives Sχ is a subset of F2m4 \ {0} which contains
exactly one elements from each orbit.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201212 / 22

Outline of Proof (2)Let Ci (x) be the initial message from i-th variable node in the BP decoder
3for x ∈ Fm2m4 .

[Theorem 1] Condition for successful decoding−1−1 HConsider the zigzag cycle of weight w with χ = H1,1H1,2 · · · Hw,w
w,1 .
All the symbols in the zigzag cycles are successful decoded iff|hχix|−1 w
Y Y
t=0

Cs (0) >s=1|hχix|−1 w
Y Y
t=0Cs

s=1Qwtxχ∀x ∈ Sχ .
ιj=s jNo symbols in the zigzag cycles are successful decoded iff|hχix|−1 w
Y Yt=0Cs (0) ≤s=1

Nozaki et al. (Titech)|hχix|−1 w
Y Y
t=0

s=1

CsQw

j=s ιjAnalysis of EF for non-binary LDPC codeχt x∃x ∈ Sχ .

July 5, 201213 / 22

Outline of Proof (3)[Corollary 1] Zigzag cycles having best performance
The zigzag cycles with χ s.t. |Sχ | = 1 have the best decoding performancein the zigzag cycles for a fixed weight.

[Lemma 2] Relation between orbit and order
The order of χ ∈ GL(m3 , F2m4 ) is 2m3 m4 − 1 iff |Sχ | = 1.

The zigzag cycles with χ of order 2m3 m4 − 1 have the best decoding
performance in the zigzag cycles for a fixed weight.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201214 / 22

Outline
1Introduction
Purposes of ResearchNon-binary LDPC Matrices over General Linear Groupq-ary Memoryless Symmetric Channel

2Lowering Decoding Error Rates in Error Floors
Error Floors and Zigzag Cycles
A Method to lower Error Floors

3

Analysis of Decoding Error Rates in Error Floors
Log-Likelihood Ratio
L-Density and Bhattacharyya Functional
Decoding Error Rate of Zigzag CycleLower Bound of Error Floor
Simulation Results
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201215 / 22

Condition for Decoding Failure[Definition] Log-likelihood ratio (LLR)
Assume the 2m1 -MS channel.
1For γ ∈ X = Fm
2 , the LLR Zv,i (yv,i , γ) corresponding to the i-th channel
output yv,i in the v-th variable node is defined as
Zv,i (yv,i , γ) = log

p(yv,i | 0).
p(yv,i | γ)[Corollary 2] Condition for decoding failure for zigzag cycles
We consider the zigzag cycle of weight w with the matrix χ of order
2m3 m4 − 1.
No symbols in the zigzag cycle are successfully decoded iffm2w X
XX

Zv,i (yv,i , γ) ≤ 0.

v=1 i=1 γ∈Fm1 \{0}Nozaki et al. (Titech)2

Analysis of EF for non-binary LDPC code

July 5, 201216 / 22

L-Density and Bhattacharyya Functional[Definition] L-density for 2m1 -MS channels
Define the random variable
L(Y ) :=Xmγ∈F2 1 \{0}logp(Y | 0).
p(Y | γ)Let a(x) be the density function of L(Y ). We refer a(x) as L-density.
The 2m1 -MS channels are characterized by L-density.

[Definition] Bhattacharyya functional
For a L-density a(x), the Bhattacharyya functional B(a) is defined as
Z ∞a(x) exp[−x/2]dx.
B(a) =−∞

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201217 / 22

Decoding Error Rate of Zigzag Cycle[Corollary 3] Decoding error rate of zigzag cycle
Let m = m1 m2 = m3 m4 .
Let Pzc (w, m1 , m2 , a) be the symbol error rate for the zigzag cycle ofweight w with χ of order 2m − 1 over the 2m1 -MS channel with L-densitya(x) under BPPdecoding.
Define Z (k) = ki=1 Zi , where Z1 , Z2 , . . . , Zk denote i.i.d. random variablewith L-density a(x). ThenPzc (w, m1 , m2 , a) = Pr(Z (wm2 ) ≤ 0) ≤ B(a)wm2 .
Note: For a fixed m = m3 m4 , the decoding error rate of zigzag cycles are
independent from m3 and m4 .

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201218 / 22

Lower Bound of Error Floor
Consider the LDPC codes designed by proposed method.

[Theorem 2] Lower bound of error floors for non-binary LDPC codes
Let wg be the minimum weight of the zigzag cycle in the LDPC code
ensemble.
Define µ := λ′ (0)ρ′ (1), where (λ, ρ) is a pair of degree distribution.
For sufficiently large N and B(a) < µ−1/m2 , the symbol error rate of theLDPC code ensemble is lower bounded by
1 X wµ Pr(Z (wm2 ) ≤ 0).
2N w=wg

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201219 / 22

Simulation Result (1)
100

10-1
Symbol error rate

10-1
Symbol error rate100

GL(4, F2 ) RandomGL(4, F2 ) Proposed
Lower bound

10-2
10-3-4

10-5

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

10

10-6

GL(4, F2) RandomGL(4, F2) Proposed
Lower bound-1012
3
4
Eb/N0 [dB]56

BAWGN channel case (wg = 1)

710-60.02

0.04 0.06
0.10.2Channel error probability

0.4

24 -SC case (wg = 2)(2,3)-regular LDPC code over GL(4, F2 ) code length 1260 bit.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201220 / 22

Simulation Result (2)
100

10-1
Symbol error rate

10-1
Symbol error rate

100

F24 Proposed
GL(4, F2 ) Proposed
Lower bound

10-2
10-3-4

10-5

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

1010-6

F24 Proposed
GL(4, F2) Proposed
Lower bound-10123
4
Eb/N0 [dB]56

BAWGN channel case (wg = 1)710-6
0.02

0.04 0.06
0.1
0.2
Channel error probability

0.4

24 -SC case (wg = 2)(2,3)-regular LDPC code over F24 and GL(4, F2 ) code length 1260 bit.

Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201221 / 22

Conclusion
Conclusion
For non-binary LDPC codes over GL(m3 , F2m4 ) over the 2m1 -MS channels
under BP decoding,we proposed a method to lower the error floors,
we analyzed the decoding error rates in the error floors.
Hi,j ∈ F2mcodes over GF
Decoding
complexity
Performanceon waterfall
Performanceon error floor

Hi,j ∈ GL(m3 , F2m4 ) Hi,j ∈ GL(m, F2 )codes over GL grouplowmiddle

highlow

unknownhighsame

Future works
Improve the decoding error rates in the waterfall regions.
Nozaki et al. (Titech)

Analysis of EF for non-binary LDPC code

July 5, 201222 / 22