Zigzag decodable 噴水符号の復号反復回数の削減
野崎 隆之
山口大学

情報理論研究会
2016/1/18

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

1 / 18

概要噴水符号マルチキャスト向けの消失訂正符号(応用例) ネットワークでの (動画) 放送(既存研究) LT 符号，Raptor 符号

これまでの研究 [Nozaki2014]
Zigzag decodable (ZD) 噴水符号の提案
利点 Raptor 符号よりも，オーバヘッド・復号消失率・空間計算量が小さい
欠点 復号反復回数が大きい (復号時間が大きい)

本研究の目的と結果
ZD 噴水符号の復号反復回数の削減(結果) 復号性能を保ったまま復号反復回数の削減に成功

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

2 / 18

Outline
1噴水符号

2Raptor 符号

3

ZD 噴水符号・復号法

4

従来復号法の問題点と改善法

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

3 / 18

噴水符号 (1: マルチキャストとその問題点)
マルチキャスト
特定の複数のユーザにデータを送信する
問題点
送信者は受信者の再送要求に応じることができない
受信者によって通信路の状況が異なる
送信者- 受信者 A
- 受信者 B
- 受信者 C

野崎 隆之 (山口大学)

s1s2

s3

s4

s5

s6

s1

s2
s2

s3

s4
s4

s5
s5

s6
s6×××××××s3

ZD 噴水符号の復号反復回数の削減

2016/1/18

4 / 18

噴水符号 (2: 概要)[送信者] k 個の情報パケットを符号化し，十分大きな数の送信パケットを作成[受信者] 任意の k(1 + α) 個の送信パケットを受信し，復号⇒ オーバヘッド α・復号消失率を小さくしたいk-

情報パケットs1s2···sk送信パケット

x1x2······

···

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

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

xk̃xk′xk′′

x1x3



·········-k̃ = k(1 + α)
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

5 / 18

噴水符号 (3: 既存研究，Raptor 符号)
Raptor 符号 (C, Ω(x))
符号化
12

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

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

送信パケット
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

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

情報パケット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 復号法)
符号化パケットの先頭から順に復号する．
ビット毎のピーリング復号法とみなせる
1

s1,1 = x2,12s2,1 = x1,1 − s1,13s1,2 = x2,2 − s2,1
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/187 / 18

ZD 噴水符号 (2: 符号化法)
提案噴水符号 (C, Ω(x), ∆(x))
12

事前符号 C を用いて，情報パケット (s1 , s2 , . . . , sk ) から事前符号化
パケット (a1 , a2 , . . . , an ) を作成
次数分布 Ω(x) に従って送信パケットの次数 d を選ぶ

相異なる d 個の事前符号化パケットを一様に選び，そのインデック
スを (j1 , . . . , jd ) と書く∑Di4 シフト分布 ∆(x) :=i=0 ∆i x に基づき d 個のシフト量 δ1 , . . . , δdを独立に選ぶ．
35以下を送信パケットとして送信d∑z δi aji (z),i=1パケットの多項式表現 aj (z) = aj,1 + aj,2 z + aj,3 z 3 + · · · + aj,ℓ z ℓ−1

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

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

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

送信パケット

1z11復号法
1

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

2

ビット毎に ZD 復号

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

9 / 18数値実験による性能比較
0

Decoding Erasure Rate

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

10-1

Table: 復号時間 [sec] の比較 (α = 0.12)ℓ = 100ℓ = 1000

10-2

10-300.1

0.2

0.30.4

Raptor0.170390.17039ZD 噴水
0.43909
14.0874

0.5Overhead

Figure: 復号性能の比較 (赤：Ratpor 符号, 紫：提案法) k = 900, 1800, 3600

提案法の利点・欠点
利点：オーバーヘッドと復号誤り率が低い
欠点：復号時間が大きい
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

10 / 18

復号法の改良
目標： 復号誤り率を保ったまま復号反復回数を削減
原因と解決策：
パケット毎の復号法による情報の復元が少ない⇒ パケット毎の復号法を強力なものに変更する
104

反復回数
パケット毎の PA : 50 回程度
ビット毎の ZD：1000 回程度

Iterations of ZD

310102

方針
101

ビット毎の復号の反復回数を削減

010100101102Iterations of PA103

反復回数の散布図(ℓ = 1000, α = 0.12)
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

11 / 18

LDPC 符号の復号法
PA (Peeling Algorithm) [Luby et al. 1997]
LDPC 符号に対するファクターグラフ上の復号アルゴリズム
次数 1 の検査ノードを利用
後退代入のみを利用した線形方程式の解法

TEP (Tree-structure Expectation Propagation) [Olmos et al. 2010]
LDPC 符号に対するファクターグラフ上の復号アルゴリズム
次数 1 と 2 の検査ノードを利用
後退代入 + 部分的に前方消去 を利用した線形方程式の解法

G-TEP (Generalized TEP) [Salamanca et al. 2013]
LDPC 符号に対するファクターグラフ上の復号アルゴリズム
全ての検査ノードを利用
ガウスの消去法を利用した解法
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

12 / 18

研究のアイディア
復号法の比較
復号法
PATEP
G-TEP

復号処理
後退代入のみ一部前進消去ガウスの消去法

利用するノード
次数 1
次数 1,2任意性能
小中大計算量小中
大グラフの密度減少
非増加増加

研究のアイディアTEP 復号法を ZD 噴水符号のパケット毎の復号へ拡張
復号誤り率は劣化しない (PA より復号性能が高いので)ZD 復号の反復回数を減らせる(パケット毎の復号で多く復元できるので)(欠点) 復号アルゴリズムがやや煩雑

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

13 / 18

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Cumurative ratio

Cumurative ratio

数値実験 (1: 反復回数)

PA+ZD(PA)TEP+ZD(TEP)
020

4060

80

100

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

PA+ZD(ZD)TEP+ZD(ZD)
0Number of iterations

5001000

1500

2000

2500

3000

Number of iterations

パケット毎の復号の反復回数ℓ = 1000, α = 0.12

ビット毎の復号の反復回数

復号の反復回数の削減に成功
パケット毎の復号は 5 回程度増加
ビット毎の復号は 600 回程度減少
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

14 / 18数値実験 (2: 復号性能)

Decoding erasure rate

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

-1

10-2
10-3

10-4
10-5
10-6
0

0.05

0.1

0.15

0.2

Overhead

復号性能 ( ℓ = 1000)
復号性能に劣化がない
野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

15 / 18数値実験 (3: 復号時間)
16

PA
PA+ZD
TEP+ZDDecoding time [sec]141210864
200.1

0.11

0.12

0.13

0.14

0.15

Overhead

復号時間 ( ℓ = 1000)
復号時間の削減に成功

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

16 / 18

まとめと今後の課題
まとめ
ZD 噴水符号に対して，復号時間の削減に成功した
TEP 復号法を ZD 噴水符号へ拡張

今後の課題
ZD 噴水符号に関する研究
復号性能解析 (密度発展法)
次数分布 Ω(x) の最適化
シフト分布 ∆(x) の最適化
復号法の更なる改良 (ZD 復号を変更)

野崎 隆之 (山口大学)

ZD 噴水符号の復号反復回数の削減

2016/1/18

17 / 18