Reduction of Decoding Iterations for Zigzag
Decodable Fountain Codes
Takayuki Nozaki
Yamaguchi University
This work is partially supported by JSPS KAKENHI Grant Number 16K16007

ISITA2016
Nov. 2nd, 2016

1 / 15Outline
Fountain code
Rateless error correcting code for user diagram protocol (UDP)(Applications) Multicasting, Broadcasting(Examples) LT code, Raptor code, RaptorQ code ...

Previous work [Nozaki2014]
Proposing “Zigzag decodable (ZD) fountain code”(Strength) Small overhead, Low decoding erasure rate(Weakness) Large number of decoding iterations/time

Purpose of this research
Reduction of number of decoding iterations for ZD fountain code(Result) Reducing decoding iterations without loss of decoding
performance2 / 15

Outline
1Fountain code and Raptor code2

Encoding/Decoding for ZD fountain code

3

Investigation of number of iterations for conventional decodingalgorithm

4

Proposed decoding algorithm

5

Simulation results

3 / 15

Fountain code (1: Brief review)[Encoder] generates many output packets from k source packets.
[Decoder] decodes source packets from any k(1 + α) received packets⇒ Suitable for multicasting/broadcastingk-Source packet

s1s2···

sk

Output packet

x1x2·········

Receiver AReceiver B
Receiver Cx2 · · ·x10 · · ·x1234 x1236 · · ····
···
···

xk̃
xk ′xk′′x1x3

·········-k̃ = k(1 + α)
Even if packet losses occur, receiver can recover source packets
4 / 15

Fountain Code (2: Raptor code)
Raptor code (C, Ω(x))
Encoding
12

Generate pre-coding packets from source packets by using precode C
Generate∑output packets from pre-coding packets by using LT codeΩ(x) = i Ωi xi
1 Choose degree d with probability Ωd2 Choose distinct d pre-coding packets (sj1 , sj2 , . . . sjd )∑d3 The output packet is
i=1 sji

Decoding
Generate factor graph from received packets and C
Execute peeling algorithm (PA)Pre-code
Pre-coding packet

Output packets···
5 / 15ZD Fountain Code (1: Toy Example)
Encoding
Using XOR and bit-level shift for source packets
s1,1 s1,2
Source packet s2,1 s2,2······s1,ℓs2,ℓs1,1 s1,2s2,1······s1,ℓs2,ℓ−1 s2,ℓOutput packet x1,1 x1,2···x1,ℓx2,1 x2,2···x2,ℓ x2,ℓ+1

Decoding: Bit-wise peeling algorithm (Zigzag decoding)
Recover source packets in bit-wise
1s1,1 = x2,12s2,1 = x1,1 − s1,13

s1,2 = x2,2 − s2,16 / 15

Zigzag Decodable Fountain Code (2: Encoding)
ZD Fountain Code (C, Ω(x), ∆(x))
1 Generate pre-coding packets (a1 , a2 , . . . , an ) from source packets(s1 , s2 , . . . , sk ) by using precode C
2 Generate an output packet as follows:
Choose degree d of an output packet with probability ΩdChoose d distinct precoded packets. Denote those indexes of packetsby (j1 , j2 , . . . , jd ).
3 Choose d-tuple of shift amount (δ1 , δ2 , . . . , δd ) according to∑D∆(x) = i=0 ∆i xi
4 Send the following output packet∑dδi
i=1 z aji (z),12

Polynomial representation of a packet
aj (z) = aj,1 + aj,2 z + aj,3 z 3 + · · · + aj,ℓ z ℓ−1
a1 (z) + za2 (z) = a1,1 + a1,2 z + a1,3 z 3 + · · · + a1,ℓ z ℓ−1+ a2,1 z + a2,2 z 3 + · · · + a2,ℓ−1 z ℓ−1 + a2,ℓ z ℓ

7 / 15

Zigzag Decodable Fountain Code (3: Decoding)
Conventional Decoding Algorithm
1 Construct factor graph in packet-wise representationfrom precode C and received packets (r 1 , r 2 , . . . , r k′ )2 (Packet-wise PA) Peeling algorithm over the factor graph
3 IF residual graph is empty, decoding succeeds and halts.
Otherwise go to next step.
4 Transform the residual graph into bit-wise representation
5 (Bit-wise PA) Peeling algorithm over the bit-wise factor graph⇒1 z

1 1 1z 1⇒1 z

8 / 15Performance Comparison (Raptor vs ZD Fountain)

Decoding Erasure Rate100

Decoding time [sec] (α = 0.12)
Raptor ZD Fountainℓ = 100
0.170390.43909ℓ = 1000 0.17039
14.0874(0,900)(0,1800)(0,3600)(3,900)(3,1800)(3,3600)

10-1

10-2-3

10

0

0.1

0.2

0.3

0.4

0.5

Overhead

Red: Raptor code,Purple: ZD Fountain code
k = 900, 1800, 3600Strength and Weakness of ZD fountain code
Strength: Small overhead and small decoding erasure rate
Weakness: Large decoding time
9 / 15

Goal and Strategy of Research(Goal of Research): reduction of number of decoding iterations without
loss of decoding performance(From simulation result)
Decoding iterations are mainly caused by bit-wise decoding⇒ The source packets are mainly recovered by bit-wise decoding
Strategy of Research: Using a powerful decoding algorithm for packet-wisedecoding.
(Decreasing the iterations of bit-wise decoding)
The number of iterations underpPA+bPA(ℓ = 1000, α = 0.07)

5Iterations of ZD

10104103102
101 010successfailure101
Iterations of PA

102

10 / 15

Decoding Algorithms for LDPC Codes over BEC
Decoding algorithms works upon factor graphs

PA (Peeling Algorithm) [Luby et al. 1997]
Decoding starts from check nodes of degree 1
Low complexity, Low decoding performance

TEP (Tree-structure Expectation Propagation) [Olmos et al. 2010]
Decoding starts from check nodes of degree 1 and 2
Moderate complexity, Moderate decoding performance

G-TEP (Generalized TEP) [Salamanca et al. 2013]
Decoding starts from check nodes of any degree
Equivalent to MAP decoding (i.e, Gaussian elimination)
High complexity, High decoding performance
11 / 15

Proposed Algorithm
Applying TEP decoding algorithm for the packet-wise decoding of ZD
fountain code (packet-wise TEP + bit-wise PA)
1

Initialize the residual graph G by the Tanner graph corresponding to H. Initialize all the memory as si ← 0(i ∈ [1, m]) and the iteration round τ as 1. For j ∈ [1, n] s.t. yj ̸= ∗, update the memory in the check node ci(i ∈ Nv (j)) as si ← si + yj and remove the j-th variable node and its connecting edges from G. Additionally, setF ← {}.

2For i ∈ [1, m], execute the following processes;
1 If the i-th check node is degree 1 in G, execute the following For i ∈ [1, m], if the i-th check node is degree 1in G, then the algorithm executes the following; Let j be the index of the adjacent variable node. The j-thvariable node sets bj (z) ← ℓ−1
i,j si (z) and send bj (z) to all the adjacent check nodes. For k ∈ Nv (j), thecheck node ck updates the memory as sk (z) ← sk (z) + ℓk,j bj (z). Remove the variable node vj and its
connecting edges from G.
2 If the i-th check node is degree 2 in G, execute the followings. Let j, j ′ be the indexes of the adjacent variablenodes. Assume that the degree of the j-th variable node is less than or equal to that of j ′ -th variable node. For
all t ∈ Nv (j) \ {i}, let gt be the greatest common divisor of li.j and lt,j and change the labels andmemory as follows:
mt (z) ← [li,j mt (z) + lt,j mi (z)]/gt ,lt,j ← 0,lt,j̃ ← li,j lt,j̃ /gt∀j̃ ∈ Nc (t) \ {j},lt,j ′ ← lt,j ′ + lt,j li,j ′ /gt .
Moreover, set F ← F ∪ {i}.

3

If there exist some check nodes of degree 1 or 2 in G, set τ ← τ + 1 and go to Step 2. Otherwise, output thedecoding result b1 (z), . . . , bn (z), the residual graph G and memory values s1 (z), . . . , sm′ (z).

12 / 15

Average number of iterations

Simulation Results (1: Average Number of Iteration)
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
00.06

pPA+bPA
pTEP+bPA

0.08

0.1

0.12

0.14

0.16

Overheadℓ = 1000

13 / 15

Simulation Results (2: Decoding Performance)
100

PA
TEP
PA+ZD (D=1)
TEP+ZD (D=1)

Decoding erasure rate-11010-210-3-41010-5
-6

10

0

0.05

0.1

0.15

0.2

Overhead

Decoding performance ( ℓ = 1000)
There are no degradation of decoding performance.
14 / 15

Conclusion and Future Works
Conclusion
We propose a decoding algorithm for ZD fountain code
Small number of iterations
No degradation of decoding performance

Future works
Optimization of degree distribution Ω(x) and shift distribution ∆(x)Comparison of MAP threshold and PA threshold for ZD fountain code

15 / 15

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Cumulative relative frequency

Cumulative relative frequency

Simulation Results (3: Details of Decoding Iterations)

pPA+bPA
pTEP+bPA
020

406080

100

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

pPA+bPA
pTEP+pPA
0

Number of iterations

The number of iterations forpacket-wise decodingℓ = 1000, α = 0.12500

1000

1500

2000

2500

3000

Number of iterations

The number of iterations for
bit-wise decoding

We reduce the total number of decoding iteration
The number of packet-wise decoding is increasing (5 iterations)
The number of bit-wise decoding is decreasing (600 iterations)
15 / 15

Simulation Results (4: Decoding Time)
16

PA
PA+ZD
TEP+ZD

Decoding time [sec]

1412
10
8
6
4
2
0
0.1

0.11

0.12

0.13

0.14

0.15

OverheadTime of decoding ( ℓ = 1000)
We can reduce the latency of decoding

15 / 15