社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
空間結合符号を用いたパケット消失訂正符号
坂田 幸佑†
笠井
健太†
坂庭
好一†
† 東京工業大学 大学院理工学研究科 通信情報工学専攻
E-mail: †{sakata,kenta,sakaniwa}@comm.ce.titech.ac.jp
あらまし
Transmission Control Protocol (TCP) はインターネット上で発生するパケット消失に対して，信頼性の高
い通信を行うために提案されたプロトコルである．しかし複数の受信者が存在する通信（例えばマルチキャスト）で
は，TCP は消失したパケットの再送を要求する Negative ACKnowledgement (NACK) が受信者の数に比例して増加
するためサーバ負荷の要因となる．この問題は，パケットが消失しても再送要求を行わない User Datagram Protocol
(UDP) により解消されるが，逆に UDP は信頼性の高い通信を実現できない．噴水符号は，UDP で信頼性の高い通信
を実現可能なパケット消失訂正符号である．本論文では，噴水符号に空間結合符号を用いることで，提案符号が情報
パケット数に対して線形時間で符号化と復号ができ，通信路容量を達成することを確認している．
キーワード
空間結合符号，LDPC 符号，噴水符号
Packet Erasure Correction Codes via Spatially-Coupled Codes
Kosuke SAKATA† , Kenta KASAI† , and Kohichi SAKANIWA†
† Dept. of Communications and Computer Engineering, Tokyo Institute of Technology
E-mail: †{sakata,kenta,sakaniwa}@comm.ce.titech.ac.jp
Abstract Transmission Control Protocol (TCP) is the reliable transmission protocol against the erased packets on
the Internet. However, for the trainsmission where multiple receivers exist (e.g multicast), Negative ACKnowledgement (NACK) is proportional to the number of receivers on TCP, which causes a load on the server. This problem
is solved by User Datagram Protocol (UDP) that doesn’t retransmit against erased packets, however, UDP can’t
realize reliable transmission. Fountain codes are packet erasure correction codes that can realize reliable transmission on UDP. In this paper, we propose fountain codes via spatially-coupled codes, and proposed codes can encode
and decode in linear time with information packets and achieve the channel capacity.
Key words spatially-coupled codes, LDPC convolutional codes, fountain codes
1. は じ め に
インターネットでのデータ通信では，データをパケットとい
を引き起こす要因となる．この問題は，パケットが消失しても
再送要求を行わない User Datagram Protocol (UDP) により
解消されるが，逆に UDP は信頼性の高い通信を実現できない．
う単位で表す．パケットはデータの情報をもつデータ部と宛先
このためマルチキャスト等で信頼性の高い通信を実現するため
等の情報をもつヘッダ部で構成されており，生成されたパケッ
には，パケットの消失を全て訂正可能な誤り訂正符号が必要と
トはヘッダ部の情報をもとに，ルーターを経由して送信先へと
なる．
送られる．この時，中間ルーターでのオーバーフローやチェッ
誤り訂正符号は，情報パケットに冗長のパケットをもたせた
クサム不一致等の理由により，パケットは破棄されてしまう．
符号パケットを用いることで信頼性の高い通信を実現する．こ
このため，信頼性のある通信を実現するために Transmission
の符号パケットは，複数の情報パケットの線形結合で構成され
Control Protocol (TCP) が提案された．TCP では，破棄され
る．ここで，従来の誤り訂正符号であるブロック符号がマルチ
た（消失した）パケットを復元するために，受信側が消失パケッ
キャストで効率が悪いことを説明する．ブロック符号では，k
トの再送要求である Negative ACKnowledgement (NACK) を
個の情報パケットを n 個の符号パケットに符号化するため，符
送信先に送ることで，信頼性の高い通信を実現している．しか
号化率 R = k/n が一定となる．この場合，複数の状態が異な
し，複数の受信者が存在する通信（例えばマルチキャスト）で
る通信路が存在するマルチキャストでは．符号化率 R が最も状
は NACK が受信者の数に比例して増加するためサーバの障害
態の悪い通信路に設定されるため，状態が良い通信路で結ばれ
—1—
る受信者は遅延やレートロスが発生してしまい通信効率が悪い．
化の計算量は事前符号の LDPC 符号により O(k 2 ) で，BP 復
一方，噴水符号は k 個の情報パケットからそれぞれ独立に計
号の計算量は O(k log(1/α)) となるため，符号化とオーバヘッ
算される無数のパケットを符号パケットとして，消失を訂正す
ド α = 0 を達成するための復号の計算量が大きくなる問題は解
る符号である．受信者は通信路の状態に依らず，任意に受信し
決されていない．
た n = (1 + α)k 個のパケットを消失なく受信することで，k 個
空間結合符号はこれらの問題を解決することができる．空間
の情報パケットを全て復号できる．式内の α はオーバヘッドと
結合符号はベースとなる符号が結合された符号であり，LDPC
呼ばれ，通信路容量との差を表しており，α = 0 で k 個の情報
ブロック符号を結合させた空間結合 LDPC ブロック符号が最初
パケットを復号することが噴水符号の設計目的である．ここで，
に提案された．Kudekar らによって，空間結合 LDPC ブロック
噴水符号が様々な通信に応用可能であることを紹介する．まず，
符号は 2 元消失通信路 (BEC) [3] と 2 元入力無記憶出力対称通
最もシンプルな 1 対 1 の通信について紹介する．1 対 1 の通信
信路 [4] で MAP 閾値を BP 復号で達成することが証明された．
では，TCP により信頼性の高い通信を実現可能である．しか
筆者らは，空間結合 MacKay-Neal (MN) ブロック符号と空間
し，送信者と受信者の距離が大きい場合，それぞれの間を行き
結合 Hsu-Anastasopoulos (HA) ブロック符号を提案し，それ
来する受信確認を表す ACKnowledgement (ACK) が通信の効
らが有界な最大次数で BEC の通信路容量を達成することを数
率性を大きく妨げることになる．この問題に対して，ACK を
値的に示し [5]，さらに BEC において空間結合 MN ブロック符
用いない噴水符号は，送信者と受信者の距離に依らず信頼性の
号と空間結合 HA ブロック符号が通信路容量を達成することを
高い通信を実現できる．1 対多のマルチキャストについては前
証明した [6]. Binary-input Memoryless Symmetric (BMS) 通
述の通り，噴水符号であれば各受信者を結ぶ通信で信頼性の高
信路において，空間結合 MN ブロック符号と空間結合 HA ブ
い通信を実現できる．
ロック符号の BP 閾値がシャノン限界に接近することが観測さ
それでは，代表的な噴水符号の構造を紹介する．LT 符号は
Luby により提案され，オーバヘッド α = 0 を達成する最初の
Fk2
れている [7]．
筆者らは，空間結合 Low-Density Parity-Check (LDPC) 符
噴水符号である [1]．ここで v ∈
を重み d のベクトルとして，
(k )
Ωd / d をベクトル v が選択される確率とし，Ω(x) を Ωd の確
号を外符号（事前符号），空間結合 Low-Density Generator-
率母関数として，以降では Ω(x) を次数分布と呼ぶ．LT 符号は
た [8]．この符号は空間結合 HA 噴水符号とみなすことができ
k 個のパケット (x1 , . . . , xk ) を無数の送信パケット (z 1 , . . . ) に
る．空間結合 HA 噴水符号の次数分布は ΩHA (x) = xdg であ
符号化する．各送信パケット z i は次のように独立に決定され
る．そのため，平均次数と最大次数が共に有界となり復号の計
る．まず，次数分布 Ω(x) からランダムに重み d (1 <
=d<
= k) を
選択する．次に，(x1 , . . . , xk ) の中から d 個のパケットを一様
算量問題を解決できる [9]．また，修正空間結合 LDPC 符号を
ランダムに選択する．そして，選択された d 個のパケットを加
間結合 HA 噴水符号は十分大きな数の情報ビット数を用いれ
算した結果が送信パケット z i となる．以上の符号化を受信側の
ば，復号誤り率を 0 にすると同時に，オーバヘッド閾値 α を 0
Matrix (LDGM) 符号を内符号とする連接噴水符号を提案し
事前符号に採用することで，O(k) で符号化が可能となる．空
復号が完了するまで続ける．よって符号化の計算量は O(k) と
に（通信路容量を達成）できることを密度発展法により確認し
なる．受信者は受信した n 個のパケットから BP 復号等を用い
ている．さらに，密度発展式に関する安定性解析から，復号誤
て k 個の情報パケットを復号する．ここで，LT 符号の次数分
り率を 0 にするオーバヘッド閾値の下界を導出し，オーバヘッ
布 Ω(x) であるソリトン分布の平均次数は Ω′ (1) = O(log(k))
ド閾値を 0 にするための必要条件が導出された [8]．この必要条
となる．よって，BP 復号の計算量は O(k log(k)) となりオー
√
バヘッドは α = O(log2 (k)/ k) となる．つまり，オーバヘッ
件を満たす空間結合 HA 噴水符号は，密度発展法による数値実
験で通信路容量を達成することを多くのパラメータの組で確認
ド α = 0 を達成するために必要な次数平均が不定かつ非有界で
している．また，ポテンシャル関数と双対性 [6] を応用するこ
あるため復号の計算量が大きくなる問題がある．
とで提案符号がオーバヘッド α = 0 を BP 復号で達成すること
Raptor 符号は Shokrollahi により提案され，オーバヘッド
α = 0 を達成するだけでなく、LT 符号に比べて低計算量で復
号が可能な噴水符号である [2]．Raptor 符号の構成を説明する．
が証明された [10]．
2. 準
備
Raptor 符号の符号化は，事前符号化と LT 符号化と 2 段階で
2. 1 通信路モデル
構成され，Raptor 符号の LT 符号化に関する次数分布は，LT
本報告で扱う通信路を定義する．D ビットのデータからなる
符号のソリトン分布を修正した分布 ΩD (x) となる．まず，事
パケット x ∈ {0, 1}D を入力とする．入力 x ∈ {0, 1}D に対し
前符号化では符号化率 R の LDPC 符号により k 個のパケット
て，出力 y は次のように定義される．
{
(x1 , . . . , xk ) は k/R 個のパケット (y 1 , . . . , y k/R ) に符号化され
る．次に，各送信パケット z i は事前符号化された k/R 個のパ
ケット (y 1 , . . . , y k/R ) から，次数分布 ΩD (x) の LT 符号化で決
定される．ここで，Raptor 符号の次数分布 ΩD (x) の平均次数
Ω′D (1)
y=
x
w.p. 1 − ϵ
?
w.p. ϵ
こ こ で ，? は パ ケット が 正 し く 受 信 さ れ ず に 消 失 し た こ
= O(log(1/α)) であるため，オーバヘッド α につい
と を 表 し て い る ．パ ケット x1 = (x1,1 , . . . , x1,D ), x2 =
て一定であり情報パケット数 k に影響されない．しかし，符号
(x2,1 , . . . , x2,D ) ∈ {0, 1}D に対して加算 x1 + x2 を x1 + x2 =
は
—2—
z
|
Section 1
}|
{
{z
}
z
|
Section 2
}|
{
{z
}
z
Section 3
}|
{
|
{z
}
z
|
Section 4
}|
{
{z
}
z
|
Section 5
Section 6
Section 7
Section 8
}|
{ z
}|
{z
}|
{z
}|
{
{z
} |
{z
}|
{z
}|
{z
}
図 1 (dl = 4, dr = 12, dg = 3, L = 5) 空間結合 HA 噴水符号の拡大次数 M = 2 に対するファクターグラフであり，パケットノードを緑
色で，チェックノードを灰色で，チャネルノードを黄色で表す．ここで表記を簡単にするため，全てのランダムな 2 × 2 置換行列を
単位行列としている．ただし，ゼロパケットを含むセクションとの接続を表現していない．
(x1,1 + x2,1 , . . . , x1,D + x2,D ) として定義する．
ンに含まれるパケットは送信され，それ以外のセクションに含
2. 2 空間結合 LDPC 符号
まれるパケットはショートンされるとする．ここでショートン
(dl , dr , L) 空間結合 LDPC 符号を次のようなベース行列によっ
されたパケットとは，パケットの値が 0 := (0, . . . , 0) ∈ {0, 1}D
て定義されるプロトグラフ符号 [11] として定義する．拡大次数
M の (dl , dr , L) 空間結合 LDPC 符号は，ベース行列 B の各成分
で送信されないパケットである．
内符号である空間結合 LDGM 符号による符号化では，各時
の 1 を 2 元 M ×M ランダム置換行列に，0 を M ×M 零行列で置
刻 t (t ∈ [1∞]) で繰り返される下記の処理によって，事前符号
き換えたパリティ検査行列によって定義される．(dl , dr , L) 空間
パケット x1 , . . . , xdk LM をさらに符号化する．この繰り返し処
結合 LDPC 符号に修正を加えた (dl , dr , L) 修正空間結合 LDPC
理は， 以下のアルゴリズムで定義される．
符号は，パリティ検査行列に修正を加えた符号であり，O(k) で
符号化が可能となる [9]．ここで，(dl = 4, dr = 12, L = 9) 空間
結合 LDPC 符号のベース行列 B(4, 12, 9) ∈ {0, 1}
L+dl −1×dk L
は次の様になる．
に選択する．
(t)
(t)
2. j1 , . . . , jdg ∈ [1, dk M ] から dg 個の整数を，重複を
許して一様ランダムに選択する．
111
111111
111111111
111111111111
111111111111
111111111111
B(4, 12, 9) =
111111111111
111111111111
111111111111
111111111
111111
111
ベース行列 B(dl , dr , L) を M 次拡大したパリティ検査行列を
H(dl , dr , L, M ) ∈ {0, 1}
1. i(t) ∈ [1, L + dg − 1] からセクションを一様ランダム
(L+dl −1)M ×(dk L)M
と書く．空間結合
符号の符号語となる dk LM 個の符号パケット x1 , . . . , xdk LM は
次式を満たすパケット列として定義される．
3. dg 個のパケットの和を次式で計算してデータ部を決定
(t)
(t)
し，ヘッダ部に i(t) , j1 , . . . , jdg を埋め込んで送信する．
x(t) =
dg
∑
k=1
(t)
xk =
dg
∑
x((i(t) −k)d
k=1
(t)
k M )+jk
ヘッダ部分の長さは ⌈log2 (L + dg − 1)⌉ + dg ⌈log2 (dk M )⌉ とな
り，データ部分の長さ D を十分大きくすれば，ヘッダの長さは
データの長さに対して無視できるようになる．
3. 1 復 号 法
受信者は送信パケット x(t) (t = 1, . . . , ∞) の中から n 個のパ
ケットを受信しようと試みるがいくつかのパケットは消失し受
信されない．情報パケット数 k に対して k(1 + α) 個のパケッ
H(4, 12, 9, M )(x1 , . . . , xdk LM )T = 0
ここで，符号パケット x1 , . . . , xdk LM を dk M 個毎に L 個のセ
トを消失なく受信しているとしよう．ここで，受信パケットに
関するオーバヘッド α を次式で定義する．
クションに区切る．同様に，(L + dl − 1)M 個のパリティ検査
α=
方程式を M 個毎に L + dl − 1 個のセクションに区切る．
3. 空間結合 HA 噴水符号
本節では，(dl , dr , dg , L) 空間結合 HA 噴水符号を定義す
る．(dl , dr , dg , L) 空間結合 HA 噴水符号は，事前符号化された
n
−1
k
(1)
また，符号化法における各時刻の独立性により，一般性を欠く
ことなく，任意の時刻から n 個のシンボルが受信されたと仮定
している．
復号では，事前符号のパリティ検査行列と消失なく受信した
[t]
[t]
dk M 個のパケットが含まれるセクションを L 個有している．
k(1 + α) 個の受信パケット x[t] のヘッダ i[t] , j1 , . . . , jdg (t =
(dl , dr , dg , L) 空間結合 HA 噴水符号の符号化は，事前符号化と
1, . . . , k(1 + α)) から，事前符号パケット x1 , . . . , xdk LM を変
内符号による符号化の 2 ステップからなる．事前符号化では，
数とするファクターグラフ [12] を構成し，そのファクターグラ
k 個の情報パケットを，(dl , dr , L) 空間結合 LDPC 符号により
フを用いて Sum-Product 復号法 [12] により情報パケットを復
dk M L 個の事前符号パケットに x1 , . . . , xdk LM に符号化する．
号する．受信者によって受信パケットとそのヘッダは異なるた
(dl , dr , dg , L) 空間結合 HA 噴水符号では，i(i ∈ [1, L]) セクショ
め，復号に用いるファクターグラフも受信者によって異なるこ
—3—
0.8
化と復号を実現できなかった．この問題に対して，(dl , dr , dg , L)
α∗ , Rpre
0.7
空間 HA 噴水符号は，O(k) で符号化と復号が可能であり，十
0.6
分大きな数の情報パケット数を用いれば，復号誤り率を 0 にす
0.5
ると同時に，オーバヘッド閾値 α∗ を 0 にできることを密度発
0.50000
Rpre (dl = 2, dr = 4, L)
Rpre (dl = 3, dr = 6, L)
α∗ (dl = 2, dr = 4, dg = 3, L)
α∗ (dl = 3, dr = 6, dg = 3, L)
0.4
0.3
展法により確認した．(dl , dr , dg , L) 空間 HA 噴水符号に修正を
加えた (dl , dr , dg , L, w) 空間 HA 噴水符号については，復号誤
り率を 0 にするオーバヘッド閾値の下界を導出し，オーバヘッ
0.2
ド閾値を 0 にするための必要条件が導出されたこの必要条件を
0.1
満たす空間結合 HA 噴水符号は，密度発展法による数値実験で
通信路容量を達成することを多くのパラメータの組で確認して
0.0
101
102
103
結合数 L
図 2 横軸は結合数 L を表し，縦軸は事前符号の符号化率 Rpre とオー
バヘッド閾値 α∗L の値を表す．
いる．また，ポテンシャル関数と双対性を応用することで空間
HA 噴水符号が通信路容量を達成することを BP 復号で達成す
ることが証明された．
文
とに注意されたい．ファクターグラフは，dk M L 個の事前符
号パケットノード（パケットノード）x(1, 1), . . . , x(L, dk M )，
(1 − Rpre (L))dk M L 個の事前符号のパリティチェックノード
（チェックノード），そして n 個のチャネルノードで構成され
る．引数が真ならば 1 を返し偽ならば 0 を返すインジケータ関
数 1[ · ] を定義すれば，時刻 t = 1, . . . , n に対応する各チャネル
ノードは次式で与えられる．
1[x(i(t) − j1(t) , j1(t) ) + · · · + x(i(t) − jd(t)g , jd(t)g ) = y(t) ] (2)
拡大次数 M = 2 の (dl = 4, dr = 12, L = 5) 空間結合符号を事
前符号とする (dl = 4, dr = 12, dg = 3, L = 5) 空間結合 HA 噴
水符号の復号に用いるファクターグラフを図 1 に示している．
上部の緑色のノードは事前符号パケットを，灰色のノードは事
前符号のパリティチェックを，黄色のノードは逐次符号により
得られる制約である逐次符号パケットファクターを表している．
4. 復号性能解析
本節では，空間結合 HA 噴水符号の復号性能を密度発展法 [13]
により解析した結果を紹介する．パケット消失通信路における
密度発展法は，ノード間で交換される BP 復号のメッセージの
消失確率を解析する手法で，符号の平均的な復号性能を評価す
ることができる．空間結合 HA 噴水符号の内符号の次数分布が
平均 β (β > 0) のポアソン分布 λ(x) = eβ(x−1) となることから，
空間結合 HA 噴水符号の密度発展式が筆者らにより導出され
た [14]．密度発展式から得られる ℓ 回目の BP 復号における復号
(ℓ)
誤り率を Pb とする．このとき，復号誤り率が 0 となるオーバ
}
{
(∞)
∗
ヘッド α をオーバヘッド閾値 αL
:= inf α > 0 | Pb (L) = 0
とする．図 2 は dk = dr /dl = 2 で limL→∞ Rpre = 0.50000 と
∗
なる場合のオーバヘッド閾値 αL
と事前符号化率 Rpre を表し
ており，結合数 L を大きくすることでオーバヘッド閾値 α∗L が
0 に収束することが確認できる．
5. ま と め
噴水符号は，オーバヘッド α = 0（通信路容量）を達成する符
号が提案されていたが，情報パケット数 k に対して O(k) で符号
献
[1] M. Luby, “LT codes,” in Proc. 40th Annual Allerton Conf.
on Commun., Control and Computing, 2002, pp. 271 – 280.
[2] A. Shokrollahi, “Raptor codes,” IEEE Trans. Inf. Theory,
vol. 52, no. 6, pp. 2551–2567, June 2006.
[3] S. Kudekar, T. Richardson, and R. Urbanke, “Threshold
saturation via spatial coupling: Why convolutional LDPC
ensembles perform so well over the BEC,” IEEE Trans. Inf.
Theory, vol. 57, no. 2, pp. 803–834, Feb. 2011.
[4] ——, “Spatially coupled ensembles universally achieve capacity under belief propagation,” IEEE Trans. Inf. Theory,
vol. 59, no. 12, pp. 7761–7813, 2013.
[5] K. Kasai and K. Sakaniwa, “Spatially-coupled MacKayNeal codes and Hsu-Anastasopoulos codes,” IEICE Trans.
Fundamentals, vol. E94-A, no. 11, pp. 2161–2168, Nov.
2011.
[6] N. Obata, Y.-Y. Jian, K. Kasai, and H. D. Pfister, “Spatially-coupled multi-edge type LDPC codes with
bounded degrees that achieve capacity on the BEC under
BP decoding,” in Proc. 2013 IEEE Int. Symp. Inf. Theory
(ISIT), July 2013, pp. 2433–2437.
[7] D. G. M. Mitchell, K. Kasai, M. Lentmaier, and
D. J. Costello, “Asymptotic analysis of spatially coupled
MacKay-Neal and Hsu-Anastasopoulos LDPC codes,” in
2012 International Symposium on Information Theory and
its Applications (ISITA), Oct. 2012, pp. 337–341.
[8] K. Sakata, K. Kasai, and K. Sakaniwa, “Spatially-coupled
precoded rateless codes,” in Proc. 2013 IEEE Int. Symp.
Inf. Theory (ISIT), 2013, pp. 2438–2442.
[9] K. Tazoe, K. Kasai, and K. Sakaniwa, “Efficient termination
of spatially-coupled codes,” in Proc. 2012 IEEE Information Thoery Workshop (ITW), Sept. 2012, pp. 30–34.
[10] K. Sakata, K. Kasai, and K. Sakaniwa, “A proof for achieving the capacity with spatially-coupled Hsu-Anastasopoulos
rateless codes,” IEICE, Technical Report IT2013-50, Mar.
2014.
[11] J. Thorpe, “Low-density parity-check (LDPC) codes constructed from protographs,” IPN Progress Report, pp. 42–
154, Aug. 2003.
[12] F. Kschischang, B. Frey, and H.-A. Loeliger, “Factor graphs
and the sum-product algorithm,” IEEE Trans. Inf. Theory,
vol. 47, no. 2, pp. 498–519, Feb. 2001.
[13] T. Richardson and R. Urbanke, “The capacity of lowdensity parity-check codes under message-passing decoding,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 599–618,
Feb. 2001.
[14] K. Sakata, K. Kasai, and K. Sakaniwa, “Fountain codes via
spatially-coupled Hsu-Anastasopoulos codes,” IEICE, Technical Report IT2012-50, Sept. 2012.
—4—
© Copyright 2024 ExpyDoc
