Message Passing Algorithm with MAP Decoding onZigzag Cycles for Non-binary LDPC Codes
Takayuki Nozaki1 , Kenta Kasai2 , Kohichi Sakaniwa2
1 Kanagawa University
2 Tokyo Institute of Technology

July 12th, 20131 / 19

Introduction
We propose a new decoding algorithm for non-binary low-density
parity-check (LDPC) codes over binary erasure channel (BEC).
Strongth of the proposed algorithm
In the error floor region, decoding erasure rate of proposed algorithm
is lower than that of BP decoder
Message passing algorithm
Weakness of the proposed algorithmDecoding complexity is higher than the BP decoder
Main idea
Reduce the decoding erasures in the zigzag cycles
Three phase decoding algorithm[Phase 1] BP decoding[Phase 2] Detection of the zigzag cycles with erasures[Phase 3] MAP decoding on the zigzag cycles
2 / 19Outline
1

Introduction2

Non-binary LDPC Codes and Zigzag Cycles

3

Message Passing Algorithm with MAP Decoding on Zigzag Cycles
Zigzag Cycle Detection
MAP Decoding on Zigzag Cycles
Simulation Result

4Conclusion

3 / 19Non-binary LDPC CodeNon-binary LDPC Code×NA linear code defined by sparse parity check matrix H ∈ FM2mTTC := x ∈ FN2m | Hx = 0

It is known that the optimized irregular non-binary LDPC codes containvariable nodes of degree 2.

v1
c1
c2
c3
c4v2v3v4v5v6


h1,1 h1,2 h1,3000
 00 h2,3 h2,4 h2,50  0 h3,20 h3,40 h3,6 h4,1000 h4,5 h4,64 / 19

Error Floors of Non-binary LDPC Codes
Decoding erasures with small weight cause error floors.

[Definition] Zigzag Cycle
A zigzag cycle (Vzc ∪ Czc , Ezc ) is a simple cycle such that the degrees ofvariable nodes in Vzc are two in the Tanner graph. All the check nodes inCzc connect to the variable nodes Vzc exactly twice.
The set of the variable nodes in Vzc forms stopping sets.
Zigzag cycles cause decoding erasures with small weight.

[Example] Zigzag Cycle(Left) A zigzag cycle(Right) A connected graphwhich is not zigzag cycle

5 / 19Outline
1

Introduction2

Non-binary LDPC Codes and Zigzag Cycles

3

Message Passing Algorithm with MAP Decoding on Zigzag Cycles
Zigzag Cycle Detection
MAP Decoding on Zigzag Cycles
Simulation Result

4Conclusion

6 / 19Abstract of Proposed Decoding Algorithm
Key Concept of Decoding Algorithm
The BP decoder can not recover zigzag cycles in which all the bits areerased, but MAP decoder can recover those.
Combine “BP decoder” with “MAP decoding on the zigzag cycles”
BPDecoderZigzag Cycle
Detector

MAP onZigzag Cycle

Y mN ∈ {0, 1, ?}mN : channel outputs.
Ei ⊆ F2m : BP decoding result for the i-th variable node (VN).
P∈ F2m : syndrome of the j-th check node (CN).
sj := i∈{k||Ek |=1} hj,i x̂BPi
Z ∈ [1, N ] : the set of VNs in zigzag cycles with BP decoding erasures.
x̂i ∈ F2m ∪ {?} : the decoding result of the i-th VN.
7 / 19

Zigzag Cycle Detection (1:Example)
If the i-th BP decoding result Ei is not unique, then the i-th VN has BP
decoding erasure.

(1)(1) The blue VNs are correctly decoded by BP decoder

8 / 19

Zigzag Cycle Detection (2:Algorithm)[Algorithm 1] Zigzag Cycle Detection
1(Construction of residual graph)
Set G as the Tanner graph. For i ∈ [1, N ], if |Ei | = 1, i-th VN and adjacentedges are removed from G and x̂i = γ where γ is the unique element of Ei .

2

(Removing CNs of residual degrees more than 2)
For j ∈ [1, M ], if the j-th CN is of degree more than 2 in G, x̂i =? andremove the VNs connecting to the j-th CN and edges adjacent to those VNsfrom G.

3(Removing CNs whose residual degrees decrease)
For j ∈ [1, M ], if the residual degrees of the j-th CN decreases, x̂i =? andremove the VNs connecting to the j-th CN and edges adjacent to those VNs
from G.

4(Decision)
If the residual degrees of all the CNs do not decrease in Step 3, let Z be theset of variable nodes in G and algorithm stops. Otherwise, go to Step 3.
9 / 19

MAP Decoding on Zigzag Cycles (1:Inverse Matrix)
To simplify the notations, we consider thezigzag cycle of weight 3.
Let si be syndrome ofQ
the i-th check node.
3,β:=ζi := hi−1,i h−1i,ii=1 ζi .
Assume that the submatrix corresponding tozigzag cycle is non-singular, i.e., β 6= 1.

 
s1
h1,1 h1,2
0x1
 s2  =  0 h2,2 h2,3   x2 s3h3,1
0 h3,3x3 −1−1−1hh1,1 ζ2 h1,1 ζ2 ζ3
s1x1
1  −11,1
  s 2  =  x2  .
h2,2 ζ3 ζ1
h−1
h−1⇐⇒2,22,2 ζ31+β−1−1−1s3x3h3,3 ζ1 h3,3 ζ1 ζ2h3,310 / 19

MAP Decoding on Zigzag Cycles (2:Decoding Result)Hence, the MAP decoding results are−1x̂1 = (1 + β)−1 h−1
1,1 (s1 + ζ2 s2 + ζ2 ζ3 s3 ) =: (1 + β) A1 ,−1x̂2 = (1 + β)−1 h−12,2 (ζ3 ζ1 s1 + s2 + ζ3 s3 ) =: (1 + β) A2 ,−1x̂3 = (1 + β)−1 h−13,3 (ζ1 s1 + ζ1 ζ2 s2 + s3 ) =: (1 + β) A3 .

Define Bi := β −1 Ai . β = Ai /Bi β 6= 1 ⇐⇒ Ai 6= Bi .
Then, we getx̂i =AiAi Bi
Ai==.
1+β1 + Ai /Bi
Ai + Bi

Hence, we obtain the MAP decoding result if we get Ai and Bi .
A message passing algorithm is able to calculate Ai and Bi .

11 / 19

MAP Decoding on Zigzag Cycle (3:Example)

s+
ζs
A1 = h−1s+ζ
3 3
12 21,1 −1−1= h−1s+hh(s+h0s+hh)
.
22,3
3
3,1
1
1,2
0
1,1
3,32,21 2

12 / 19

MAP Decoding on Zigzag Cycle (4:Example)−1−1B1 = h−1s+ζs+ζs3213,132 −1−1)= h−1s+hh(s+h0s+hh.
22,2
1
1,1
3
3,3
0
3,1
1,22,3
1 213 / 19

MAP Decoding on Zigzag Cycle (5:Algorithm)
BPDecoderZigzag CycleDetector

MAP onZigzag Cycle

sj ∈ F2m : syndrome of the j-th check node (CN).
Z ∈ [1, N ] : the set of VNs in zigzag cycles with BP decoding erasures.
x̂i ∈ F2m ∪ {?} : the decoding result of the i-th VN.
(ℓ)

(ℓ)

(ℓ)

(ℓ)

(ψi→j , pi→j ) ∈ F2m × [1, w] : the message from the i-th VN to the j-th CN
at the ℓ-th iteration.
(φj→i , qj→i ) ∈ F2m × [1, w] : the message from the j-th CN to the i-th VN
at the ℓ-th iteration.
Nv (i) : the set of indices of CNs which are neighbors of the i-th VN.
Nc (j) : the set of indices of VNs which are neighbors of the j-th CN.
Nv (Z) : the set of indices of CNs which are neighbors of the VNs in Z.
14 / 19

MAP Decoding on Zigzag Cycle (6:Algorithm)[Algorithm 2] MAP Decoding on Zigzag Cycle
1

Set ℓ = 0. For i ∈ Z and j ∈ Nv (i), the i-th VN sends
(0)

(0)

(ψi→j , pi→j ) = (0, i).
2

For j ∈ Nv (Z) and i ∈ Nc (j) ∩ Z, the j-th CN sends
(ℓ+1)

(ℓ)

(ℓ+1)

(ℓ)

−1
(sj + hj,i′ ψi′ →j ), pi′ →j ),(φj→i , qj→i ) = (hj,iwhere i′ is the unique element of (Nc (j) ∩ Z) \ {i}.
(ℓ+1)

(ℓ+1)

4For i ∈ Z, if i = qj→i = qj ′ →i where {j, j ′ } = Nv (i), then Z ← Z \ {i}((ℓ+1)
(ℓ+1)
(ℓ+1)
(ℓ+1)
(ℓ+1) (ℓ+1)φj→i φj ′ →i /(φj→i + φj ′ →i ), if φj→i 6= φj ′ →i ,x̂i =(ℓ+1)(ℓ+1)?,
if φj→i = φj ′ →i .
If Z = ∅, the algorithm stops.

5Set ℓ ← ℓ + 1. For i ∈ Z and j ∈ Nv (i), the i-th VN sends

3(ℓ)

(ℓ)

(ψi→j , pi→j ) = (φj ′ →i , qj ′ →i ),′where j is the unique element of Nv (i) \ {j}. Go to Step 2.
15 / 19

Decoding Complexity (Worst case)E : the number of variable node with decoding erasureZigzag cycle detection(The number of iteration) ≤ E/2(The number of edges conveying messages per iteration) ≤ 2E
⇒ Complexity O(E 2 )MAP decoding on zigzag cycle(The number of iteration) ≤ E(The number of calculations per iteration) ≤ O(E)⇒ Complexity O(E 2 )16 / 19

Simulation Result (1)010-1BP-2

Proposed

Symbol erasure rate

1010-310-4

10(2,3)-regular LDPC codes
constructed by [NKS12]F24Symbol code length 315-510-6

10-7100.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7
Channel erasure probability[NKS12] T. Nozaki, K. Kasai, and K. Sakaniwa, “Analysis of Error Floors of Non-binary LDPC
Codes over BEC,” IEICE Trans. Fundamentals. vol. E95-A, no. 1, pp. 381–390, Jan. 201217 / 19

Simulation Result (2)0Symbol erasure rate

10-1BP-2

Proposed

10Irregular LDPC codes
constructed [NKS12]
F24
Symbol code length 252

10-310-4

10-510-6100.2

0.25
0.3
0.35
0.40.45
Channel erasure probability

0.5

Λ(x) =195x2 + 26x3 + 29x4 + 2x5
P (x) = 36x4 + 90x5

[NKS12] T. Nozaki, K. Kasai, and K. Sakaniwa, “Analysis of Error Floors of Non-binary LDPC
Codes over BEC,” IEICE Trans. Fundamentals. vol. E95-A, no. 1, pp. 381–390, Jan. 201218 / 19

Conclusion
Conclusions
We have proposed a message passing decoding algorithm with MAP
decoding on the zigzag cycles.

RemarkThe proposed algorithm is extended to the memoryless binary-input
output-symmetric channels (IEICE transactions).

19 / 19