シフト演算を利用した噴水符号
Zigzag Decodable Fountain Codes
野崎隆之
山口大学

2017/1/19

1 / 32

概要
噴水符号パケット通信向けの誤り訂正符号 (特にマルチキャスト)
発表の構成
1

噴水符号 (目的，既存の構成法・復号法)

2

シフトを利用した噴水符号 (構成法・復号法・性能解析)

詳しい情報
萩原学 編著 “進化する符号理論,” 数学評論社

A. Shokrollahi, M. Luby, “Raptor Codes,” Foundations and Trends in
Communications and Information Theory, vol. 6, nos. 3–4,
pp. 213–322, 2011
T. Nozaki, “Zigzag decodable fountain codes,” arXiv preprint
arXiv:1605.09125, 2016.
2 / 32

マルチキャストとその問題点
マルチキャスト
複数のユーザにデータを送る通信方式
問題点
送信者は受信者の再送要求に応じることができない
受信者によって通信路の状況が異なるs1s2s3s4s5s6- 受信者 As1s3s4s4s5s5s6
s6- 受信者 C××

s2s2×××

送信者- 受信者 B××
s33 / 32

噴水符号 [Byers 2002][送信者] k 個の情報パケットを符号化し，十分大きな数の送信パケットを作成[受信者] 任意の k(1 + α) 個の送信パケットを受信し，復号⇒ 受信パケットに関するオーバヘッド α を小さくしたいk-

情報パケットs1s2···sk

送信パケットx1x2···

···

···

受信者 A
受信者 B
受信者 C

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

xk̃
xk ′xk′′

x1x3



···

···

···

-k̃ = k(1 + α)
4 / 32

LT 符号 [Luby 2002] (1:概要と符号化)
噴水符号のコンセプトを初めて実現した符号

Peeling 復号法によって効率的に復号される (計算量 O(k))

LT 符号の符号化
パラメタ：次数分布 Ω(x) =∑( i Ωi = 1)

∑dmi=1 Ωi xi

1

整数 d を確率 Ωd で選ぶ

2

相異なる d 個のパケットを選び出す(sj1 , sj2 , . . . , sjd )3

選んだパケットを足し合わせる
xt = sj1 + sj2 + · · · + sjd

5 / 32

LT 符号 [Luby 2002] (2:符号化の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s56 / 32

LT 符号 [Luby 2002] (2:符号化の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s57 / 32

LT 符号 [Luby 2002] (2:符号化の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s58 / 32

LT 符号 [Luby 2002] (2:符号化の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s59 / 32

LT 符号 [Luby 2002] (2:符号化の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s510 / 32

LT 符号 [Luby 2002] (3:復号の例)s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s511 / 32

LT 符号 [Luby 2002] (3:復号の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s512 / 32

LT 符号 [Luby 2002] (3:復号の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s513 / 32

LT 符号 [Luby 2002] (3:復号の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s514 / 32

LT 符号 [Luby 2002] (3:復号の例)

s1s2s3s4s5s1s3s4s5s1s2s4s2s2s4s3s5

15 / 32

Raptor 符号 [Shokrollahi 2006]
Raptor 符号 (C, Ω(x))
符号化
12

事前符号 C を用いて，情報パケットから事前符号化パケットを作成
事前符号化パケットを LT 符号 (Ω(x)) で符号化し，送信復号
受信パケットと事前符号のタナーグラフをもとにファクターグラフを作成し，ピーリング復号

事前符号
事前符号化パケット

送信パケット···16 / 32

ピーリング復号の停止条件
次数 1 の検査ノードがなくなったときに復号停止⇒ Stopping set にはまった時

研究のアイディア
Stopping set にはまっても復号できるような仕掛けを作る

17 / 32

ZD 噴水符号 (1: Zigzag decodable code [Sung 2013])
符号化
情報パケットに対して排他的論理和とシフト演算を用いる

情報パケットs1,1 s1,2s2,1 s2,2······

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

s1,ℓs2,ℓ−1 s2,ℓ

送信パケットx1,1 x1,2···x1,ℓx2,1 x2,2···x2,ℓ x2,ℓ+1

復号法 (Zigzag 復号法)[Gollakota 2008]
符号化パケットの先頭から順に復号する．
ビット毎のピーリング復号法とみなせる
1s1,1 = x2,12s2,1 = x1,1 − s1,13s1,2 = x2,2 − s2,118 / 32

ZD 噴水符号 (2: 符号化法)
パケットの表現法aj= (aj,1 , aj,2 , aj,3 ,. . . , aj,ℓ )aj (z) = aj,1 + aj,2 z + aj,3 z 2 + · · · + aj,ℓ z ℓ−1
ZD 噴水符号 (C, Ω(x), ∆(x))
事前符号 C を用いて，情報パケット (s1 , s2 , . . . , sk ) から事前符号化
パケット (a1 , a2 , . . . , an ) を作成
2 (送信パケットの作成)
1

次数分布 Ω(x) に従って送信パケットの次数 d を選ぶ
相異なる d 個の事前符号化パケットを一様に選び，そのインデックスを (j1 , . . . , jd ) と書く∑
smi
3 シフト分布 ∆(x) :=i=0 ∆i x に基づき d 個のシフト量 δ1 , . . . , δd を独立に選ぶ．
4 以下を送信パケットとして送信
12d∑

z δi aji (z),i=119 / 32

ZD 噴水符号 (3: 復号法)
受信者毎に，事前符号と受信パケットからファクターグラフを作成

事前符号
事前符号化パケット

送信パケット

1z

1

1 z z

1

復号法
1

パケット毎に PA 復号 (次数 1 の検査ノードから復号)

2

ビット毎に ZD 復号20 / 32

ZD 噴水符号 (4: 復号法の例)⇒1z21 / 32

性能評価 (1:オーバヘッド 1)
受信パケットに関するオーバヘッド α
情報パケット数に対して余分に受け取った受信パケットの割合
受信パケット数 k(1 + α)
受信ビットに関するオーバヘッド β
情報ビット数に対して余分に受け取った受信ビット数の割合
受信ビット数 kℓ(1 + β)

Raptor 符号の場合：α = β
提案符号の場合：α ≤ β
β =α+k(1+α)
1 ∑ℓi .
kℓi=1

但し，i 番目の受信パケットのビット数は ℓ + ℓi

22 / 32

性能評価 (2:オーバヘッド 2)[補題 1] 受信パケットのビット長の期待値
L : 受信パケットのビット長を表す確率変数∑Ω(x) = i Ωi xi : 次数分布∑m∆(x) = si=0
∆i xi : シフト分布
E[L] = ℓ + sm −但し，∆[i,j] :=∑s∑m −1Ω(∆[0,i] ) −i=0sm∑Ω(∆[i,sm ] )i=1k∈[i,j] ∆k

β の期待値はβ̄ = (1 + α)

E[L]−1ℓ

23 / 32

性能評価 (3:復号誤り率の比較)[定理 1] 復号誤り率の比較
PB (α, C, Ω, ∆) : オーバヘッド α のときの ZD 噴水符号 (C, Ω(x), ∆(x)) の復号誤り率
任意の α, C, Ω(x), ∆(x) に対して，PB (α, C, Ω, 1) ≥ PB (α, C, Ω, ∆)定理の意味
Raptor 符号より ZD 噴水符号の方が復号誤り率が低い

24 / 32

性能評価 (4:復号計算量)

空間計算量
Raptor 符号 ℓ(2n + βk)
ZD 噴水符号 ℓ(2n + βk)⇒ オーバヘッド β に依存
最大反復回数 (最悪時間計算量)
Raptor 符号 βk + n
ZD 噴水符号 ℓ(βk + n)

⇒ ZD 噴水符号は復号時間が大きい

25 / 32

数値実験 (0:パラメタ設定)
設定パラメタパケット
パケット長：100
事前符号(3,30)-正則 LDPC 符号
情報パケット数 k ： 900,1800,3600
事前符号化パケット数 n：1000,2000,4000
送信パケット符号化
次数分布：Ω(x) =0.007969x + 0.493570x2 + 0.166220x3 + 0.072646x4 + 0.032558x5 +919 + 0.025023x65 + 0.003135x66
0.056058x8 + 0.037229x∑s+m0.055590x1i
シフト分布： ∆(x) = i=0 1+sm x

26 / 32

数値実験 (1:復号誤り率)
100
Decoding Erasure Rate

Decoding Erasure Rate

100

10-1
sm=0
sm=1
sm=2
sm=3
sm=4
sm=5
sm=6-2

10

10-3

00.05

0.1

0.15

0.2

10-1

10-3
0.25

sm=0
sm=1
sm=2
sm=3
sm=4
sm=5
sm=6

10-2

0.3

00.05

Overheadα
復号性能の比較 (赤：Raptor 符号, その他：提案法)
sm = 0, 1, 2, . . . , 6, k = 900, n = 1000

0.1

0.15

0.2

0.25

0.3

OverheadβZD 噴水符号の方が復号誤り率が低い
ZD 噴水符号の方が空間計算量が低い
27 / 32

数値実験 (2:復号誤り率)

Decoding Erasure Rate

10010-110-210-3(0,900)(0,1800)(0,3600)(3,900)(3,1800)(3,3600)

00.1

0.2

0.3

0.40.5Overheadβ
復号性能の比較 (赤：Raptor 符号, その他：提案法)
sm = 3, (k, n) = (900, 1000), (1800, 2000), (3600, 4000)
しきい値 α∗ , β ∗ が存在
28 / 32

数値実験 (3:復号反復回数)
Average number of iterations

300

sm=0
sm=1
sm=2
sm=3
sm=4
sm=5

250
200
150
100
50
00.1

0.12

0.14

0.16

0.18

0.2Overheadα
反復回数の比較 (灰色：Raptor 符号，その他：提案符号)ℓ = 100, (k, n) = (3600, 4000), sm = 0, 1, . . . , 5
欠点： 復号反復回数が大きい
29 / 32

漸近性能解析α∗ , β ∗ : 復号しきい値 (k → ∞ のときの性能指標)

密度発展法による解析{}(τ )α∗ = min α | ∃τ ∀i ∈ [1, ℓ] Qi = 0 .
β ∗ = (1 + α∗ )(0)x2,i = 1

(τ )

(τ )

(τ )

(τ )

(τ )

x1,i = 1,(0)x1,i = λ(y1,i )I(y2,i ),E[L]−1ℓ∀i ∈ {1, . . . , ℓ}
(τ )

(τ )

(τ )

x2,i = Λ(y1,i )ι(y2,i )∑(τ )(τ −1)(τ )(τ −1)
y1,i = 1 − ρ(1 − x1,i ), y2,i = 1 − s ∆s ω(1 − x̂2,i+s ),
∑sm
(τ )
(τ )
x̂2,i := s=0∆s x2,i−s(τ )Qi= Λ(y1,i )I(y2,i ),30 / 32

漸近性能解析の数値例 (1)Table: Overhead α∗ for k → ∞sm
1
0.0561
0.05630.05630.05630.056320.0338
0.03650.03650.03650.03650.16

30.0171
0.02650.02690.02690.02694-0.0011
0.02050.02190.02200.02205-0.0244
0.01560.01890.01900.0190

sm=0
sm=1
sm=2
sm=3sm=4sm=50.14
0.12
Overhead βℓ163264128
25600.1282
0.12820.12820.12820.1282

0.1
0.08
0.06
0.04
0.02
101001000

Length of source packets

31 / 32

まとめと今後の課題

まとめ
噴水符号の既存研究 (LT 符号・Raptor 符号) を紹介した

Zigzag decodable 噴水符号を紹介した

今後の課題
次数分布・シフト分布の最適化(次数分布の最適化：3 月の全国大会で発表予定)
復号法の反復回数の削減・効率化(ISITA2016 で提案したが，改善の余地あり)

32 / 32