Fountain Codes Based on Zigzag Decodable Coding
Takayuki Nozaki
Kanagawa University

28th Oct. 2014

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

1 / 19

Overview
Purpose of this study
Constructing fountain codes which have good performance when thenumber of source packets is finite.
Strength of the proposed system (overhead, space complexity of decoding)
The proposed system outperforms the Raptor coding system in termof the overhead and space complexity of decoding for the fixed
decoding erasure rate.
Drawback of the proposed system (time complexity of decoding)
The time decoding complexity of proposed system is larger than the
Raptor coding system.
Main Idea(Raptor code) + (Zigzag decodable code) ⇒ Proposed fountain code

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

2 / 19Outline
1

Fountain Codes
Fountain Codes
LT CodesRaptor Codes

2

Zigzag Decodable Codes

3

Fountain Codes Based on Zigzag Decodable Coding
Encoding
Decoding

4

Performance Evaluation
Overhead
Decoding Erasure Probability
Decoding Complexity
Simulation Results

Takayuki Nozaki(Kanagawa University)Fountain Codes Based on ZD Coding

28th Oct. 2014

3 / 19

Fountain Code [Byers et al. 2002].
Erasure decoding code.

Solving the retransmission problem on the multicast

Sender encodes k source packets and produces infinite output packets.
Receivers decodes the original message from arbitrary k(1 + α) output
packets.
⇒ Goal: Achieving small overhead α of received packets.
kSource Packets

s1s2···

sk

Output Packets

x1x2·········

Receiver A
Receiver B
Receiver C

x2 · · ·x10 · · ·x1234 x1236 · · ··········

xk̃xk′xk′′

x1x3



·········-k̃ = k(1 + α)
Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

4 / 19

LT Codes (Ω(x)) [Luby 2002].
Firstcode realizing the concepts of the fountain code.
.
Encoding
1
2
3

Randomly∑choose a degree d according to the degree distributionΩ(x) = i Ωi xi
Randomly choose d distinct source packets
Output bit-wise XOR of the d distinct source packets as an outputpacket

Decoding
12.

Construct the factor graph from the received packets
Recover the source packets by using packet-wise peeling algorithm (PA)

Source Packets

Output packets···

x1 = s 3 + s 5.

Takayuki Nozaki= (s3,1 + s5,1 , s3,2 + s5,2 , . . . , s3,ℓ + s5,ℓ )(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

5 / 19Raptor Codes [Shokrollahi 2006]
Raptor code (C, Ω(x))
Encoding
12

Generate the precoded packets from the source packets by using
precode C
Generate the output packets from the precoded packets by using LTcode (Ω(x))

Decoding
12

Construct the factor graph from the received packets and Tanner graphof C
Recover the source packets by using packet-wise PA.
PrecodePrecoded packets···. Output packets
Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

6 / 19

Zigzag Decodable Codes (1) [Gollakota & Katabi 2008].
Originally proposed in the wireless communication to combat thehidden terminal problem.

Applied to the distributed storage system and network coding.
Encoding.
Generate the encoded packets from the source packets by using shift and.bit-wise XOR.
s1,1 s1,2s2,1 s2,2······

s1,ℓs2,ℓs1,1 s1,2s2,1······

s1,ℓs2,ℓ−1 s2,ℓ.Encoded Packet x1,1 x1,2···x1,ℓx2,1 x2,2···x2,ℓ x2,ℓ+1

Source Packet

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

7 / 19

Zigzag Decodable Codes (2).

(Original) Zigzag Decoding.

The decoding starts only left of the encoded packets
Solving linear equations with one unknown variable (like as PA).

.
.

Source Packet

s1,1 s1,2s2,1 s2,2······

s1,ℓs2,ℓs1,1 s1,2s2,1······

s1,ℓs2,ℓ−1 s2,ℓEncoded Packet

x1,1 x1,2···x1,ℓx2,1 x2,2···x2,ℓ x2,ℓ+1

1s1,1 = x2,12s2,1 = x1,1 − s1,1. 3 s1,2 = x2,2 − s2,1.

Modified Zigzag Decoding (bit-wise PA).
If the decoding starts left and right of the encoded packets, the decoding
performanceis improved.
.
Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 20148 / 19Representation for the Zigzag Decodable Codes
Polynomial representation of the packet si = (si,1 , si,2 , . . . , si,ℓ )si (z) = si,1 + si,2 z + si,3 z 2 + · · · + si,ℓ z ℓ−1
Polynomial representation for the encoded packets∑xi (z) = kj=1 gi,j (z)sj (z)(gi,j (z) ∈ {0, 1, z, z 2 , . . . })Matrix representation for the Zigzag decodable codex(z) = G(z)s(z)s1

Factor graph representation for the Zigzag decodable code
s2
1 1
1 z

c1

c2
1x1
Takayuki Nozaki(1G(z) =x2(Kanagawa University)

Fountain Codes Based on ZD Coding

1 11 z28th Oct. 2014)

9 / 19

Fountain Codes Based on Zigzag Decodable Coding(Encoding)
Proposed fountain code F(C, Ω(x), ∆(x))(Precoding) Generate the precoded packets a from the source packets sby using precode C.
1
2

3

Choose a degree d according to the degree distribution Ω(x).
Choose d-tuple of shift amount (δ̃1 , . . . , δ̃d ) ∈ [0, sm ]d in independentof each other according to shift distribution ∆(x).
Define δi := δ̃i − δ̃min for ∀i, where δ̃min := mini {δ̃1 , . . . , δ̃d }.

4

Choose d distinct precoded packets uniformly. Let (j1 , j2 , . . . , jd )denote the d-tuple of indexes of the chosen precoded packets.

5

Generate an output packet from the d distinct precoded packets asfollows:∑d δi
i=1 z aji (z).

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 2014

10 / 19

Fountain Codes Based on Zigzag Decodable Coding(Decoding)Generate the factor graph from the received packets and precode.
2 Execute bit-wise peeling algorithm
1Precode
Precoded Packet
1

Received Packet.
µ2@@
R@z µ̃2@@R@1 µ̃1

Takayuki Nozaki

z

1

1

µ1 , µ2 , ν ∈ {0, 1, ?}ℓ ,- z2 -ν̃oνo(Kanagawa University)? + ∗ =?

1µ̃1 (z) = µ1 (z),2ν̃o (z) = µ̃1 (z) + µ̃2 (z) + x(z)3(νo,1 , . . . , νo,ℓ ) = (ν̃o,3 , . . . , ν̃o,k+2 )Fountain Codes Based on ZD Codingµ̃2 (z) = zµ2 (z)28th Oct. 201411 / 19Performance Evaluation (1: Overhead).
Overhead α of received packets.
#of received packetsk̃
α=−1= −1#of source packetsk.
.
Overhead β of received bits.
∑k̃(ℓ + ℓi )#of received bits
β=− 1 = i=1−1#of source bitskℓℓ : the length of the source packets.
ℓ. + ℓi : the length of the i-th received packet.

β =α+k(1+α)
1 ∑ℓi .
kℓi=1

For the Raptor codes: α = βFor the proposed codes: α ≤ βTakayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201412 / 19Performance Evaluation (2: Overhead).

[Proposition 1] Expectation of the length of the received packets.

L : Random variable representing a length of a received packet∑Ω(x) = i Ωi xi : Degree distribution∑m∆(x) = si=0
∆i xi : Shift distribution
E[L] = ℓ + sm −where ∆[i,j] :=.

∑s∑m −1Ω(∆[0,i] ) −i=0sm∑Ω(∆[i,sm ] ),i=1

k∈[i,j] ∆k .

.
For a fixed α, the expectation of β is(1 + α)

E[L]−1ℓ.Since E[L] ≤ ℓ + sm , β → α as ℓ → ∞.
Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201413 / 19Performance Evaluation (3: Decoding Erasure Probability).

[Theorem 1] Comparison of decoding erasure probability with Raptor
code.
PB (α, C, Ω, ∆) : decoding erasure probability for the proposed fountaincode F(C, Ω(x), ∆(x)) at the overhead α
For arbitrary α, C, Ω(x), ∆(x), the following holds
PB (α, C, Ω, 1) ≥ PB (α, C, Ω, ∆).

Note: The fountain code F(C, Ω(x), 1) is equivalent to the Raptor code(C, Ω(x)).

[Corollary 1].
If Raptor code (C, Ω(x)) achieves α = 0, then the proposed fountain code
F(C,Ω(x), ∆(x)) also achieves α = 0 for arbitrary ∆(x).
.

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201414 / 19Performance Evaluation (4: Decoding Complexity).
Space Complexity.
Space complexity is determined from the total number of factor nodes.
For. both the proposed code and Raptor code, kℓ(2 + β) + nℓ.
.

Time Complexity (Upper bound).
Time complexity is determined from the number of iteration in peelingalgorithm.
For the Raptor code, αk + n. (Since packet-wise PA).For the proposed code, ℓ(βk + n). (Since bit-wise PA)⇒ (main drawback)The time complexity of the proposed code is larger than Raptor code.

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201415 / 19Performance Evaluation (5: Simulation Results)
Settings
PacketLength of packet ℓ : 100 (bits)
Precode(3,30)-regular LDPC code
The number of source packets: k = 900, 1800, 3600
The number of precoded packets: n = 1000, 2000, 4000
Degree distributionsΩ(x) =0.007969x + 0.493570x2 + 0.166220x3 + 0.072646x4 + 0.032558x5 +8 0.037229x9 + 0.055590x19 + 0.025023x65 + 0.003135x66
0.056058x∑s+1mi∆(x) = i=01+sm x

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201416 / 19Performance Evaluation (6: Simulation Results)

100

sm=0sm=1
sm=2
sm=3
sm=4
sm=510-1

Decoding Erasure Rate

Decoding Erasure Rate

10010-2

10-3

00.05

0.1

0.15

0.2

0.25

0.3

sm=0
sm=1
sm=2
sm=3
sm=4
sm=510-1

10-2

10-30αNumber of source packets k = 900 (n = 1000)
Maximum shift amount sm = 0, 1, 2, 3, 4, 5.
Raptor code : sm = 0.Proposed code : sm = 1, 2, 3, 4, 5Overhead

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

0.05

0.1

0.15

0.2Overhead

β0.25

28th Oct. 20140.3

17 / 19Performance Evaluation (7: Simulation Results)

100(0,900)(0,1800)(0,3600)(3,900)(3,1800)(3,3600)

10-1

Decoding Erasure Rate

Decoding Erasure Rate

100

10-2

10-3

0

0.1

0.2

0.3

0.4

0.5

(0,900)(0,1800)(0,3600)(3,900)(3,1800)(3,3600)

10-1

10-2

10-3

00.1

α
Number of source packets k = 900, 1800, 3600
Maximum shift amount sm = 0, 3.
Overhead0.2

0.3

Overhead0.4

0.5

β(Remark).
The
space complexity of decoding is kℓ(2 + β) + nℓ.
.
Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201418 / 19

Conclusion and Future Works.
Conclusion.
Proposing a fountain coding system based on zigzag decodable code.

The proposed fountain code outperforms the Raptor code in term of
the overheads and space complexity of decoding.
Future Works.
Propose an eﬃcient decoding algorithm.

Analyze the decoding threshold

Takayuki Nozaki(Kanagawa University)

Fountain Codes Based on ZD Coding

28th Oct. 201419 / 19