空間結合(dl,3,3)MacKay

空間結合 (dl , 3, 3)MacKay-Neal 符号が
通信路容量を達成することの証明
岡崎卓弥
坂庭・笠井研究室
February 17, 2014
研究背景と目的
研究背景
Obata らが空間結合 (dl , 2, 2)MacKay-Neal 符号が BEC の通信路容
量を達成することを証明した．
しかし，この符号は次数 2 のビットノードを持つためにエラーフ
ロアが高くなる．
目的
エラーフロアが低い空間結合 (dl , 3, 3)MacKay-Neal 符号が通信路
容量を達成することを証明する．
MacKay-Neal 符号
(dl , dr , dg )MacKay-Neal(MN) 符号
次のタナーグラフを有する符号．但し，dl , dr , dg は
dl ≥ dr ≥ 2, dg ≥ 2 を満たす整数．
▶ dr M
dl
個の次数 dl のパンクチャされたビットノード
▶
M 個の次数 dg のビットノード
▶
M 個の次数 dr + dg のチェックノード
空間結合 MacKay-Neal 符号
(dl , dr , dg , L, w) 空間結合 MacKay-Neal(MN) 符号
(dl , dr , dg ) MN 符号のタナーグラフを L セクション分重ねて，w
離れたセクションまで互いのノードが結合しているタナーグラフ
を有する符号．
空間結合 MN 符号のレート RMN は
∑
i dr +dg
1+w−2 w
)
dr
dr
i=0 (1 − ( w )
MN
R
=
+
=
dl
L
dl
(L → ∞)
復号性能の解析方法
MN 符号の密度発展式
消失確率が ϵ ∈ [0, 1] である BEC における MN 符号の密度発展式
は次のようになる．
x(t+1) = f (g(x(t) ); ϵ)
d −1
f (x; ϵ) = (x1dl −1 , ϵx2g
)
dr −1
g(x) = (1 − (1 − x1 )
(1 − x2 )dg , 1 − (1 − x1 )dr (1 − x2 )dg −1 )
空間結合 MN 符号の密度発展式
MN 符号の密度発展式の f , g を用いて次のようになる．
( w−1
)
w−1
∑
∑
1
1
(t)
(t+1)
f
g(xi+j−k ); ϵi−k ,
xi
=
w
w
k=0
{
ただし，ϵi =
j=0
ϵ, i ∈ {0, . . . , L − 1}
0, i ∈
/ {0, . . . , L − 1}
である．
ポテンシャル関数
ポテンシャル関数
BEC における MN 符号のポテンシャル関数は次式になる．
dr
U (x1 , x2 ; ϵ) =1 − (1 − (1 − x1 )dr −1 (1 − x2 )dg )dl
dl
− ϵ(1 − (1 − x1 )dr (1 − x2 )dg −1 )dg
dg x 2
dr x 1
+ (1 − x1 )dr (1 − x2 )dg (1 +
+
)
1 − x1 1 − x2
閾値飽和定理
ポテンシャル閾値
F(ϵ) ≜ {x ∈ [0, 1]2 ]\{0}|x = f (g(x); ϵ)} を ϵ ∈ [0, 1] に対して非
ゼロの不動点の集合とする. ポテンシャル閾値を次のように定義
する
ϵ∗ ≜ sup{ϵ ∈ [0, 1]| min U (x; ϵ) > 0}
x∈F (ϵ)
閾値飽和定理
(dl , dr , dg )MN 符号のポテンシャル閾値未満の ϵ と十分大きい結合
幅 w に対して，空間結合 (dl , dr , dg )MN 符号の密度発展式に対す
る不動点は 0 ただ一つである．
密度発展式の不動点
密度発展式の不動点
MN 符号の不動点 (x1 , x2 , ϵ) は 2 種類存在する．
▶
自明な不動点:(1, ϵ, ϵ)
▶
非自明な不動点:x1 ∈ (0, 1) に対して (x1 , x2 (x1 ), ϵ(x1 ))
1/(dl −1)
x2 (x1 ) = 1 − ((1 − x1
ϵ(x1 )
)/(1 − x1 )dr −1 )1/dg
= x2 /(1 − (1 − x1 )dr (1 − x2 )dg −1 )dg −1
不動点におけるポテンシャル関数
ポテンシャル閾値
ϵ∗ ≜ sup{ϵ ∈ [0, 1]| min U (x; ϵ) > 0}
x∈F (ϵ)
0.6
dl=3
dl=4
dl=5
dl=6
U (x1 , x2 , ϵ)
0.5
0.4
破線:非自明な不動点における
ポテンシャル関数
0.3
実線:自明な不動点における
0.2
ポテンシャル関数
0.1
0.0
0
0.25
0.4
0.5
-0.1
-0.2
0.0
0.2
0.4
0.6
ϵ
0.8
1.0
証明
非自明な不動点におけるポテンシャル関数を U (x1 , x2 (x1 ); ϵ(x1 ))
とする．
複雑な形をした不等式
U (x1 , x2 (x1 ); ϵ(x1 )) > 0
f or x1 ∈ (0, 1)
⇐⇒
多項式の不等式
I(z) < 0
f or z ∈ (0, 1)
dl −2
I(z) = −d3l + 27
∑
[z 3dl −2+i (1 − z dl −1 )] − 27d2l z −2+2dl (1 − 4z dl −1 )(1 − z dl −1 )2
i=0
{
}
− 9dl z −4+dl (1 − z dl −1 )2 (−3 + z)z 2 + 16(−1 + z)z 2dl − 8(−1 + z)z 1+dl
− d3l (1 − z)z −9+dl (8z 6dl − 56z 1+5dl + 2z 6 (3 + 7z) + 8z 2+4dl (13 + 8z)
− 8z 3+3dl (13 + 22z) + 4z 4+2dl (21 + 43z) − z 5+dl (41 + 73z))
I(z) < 0 の証明
I(dl )
3 ≤ dl ≤ 164 に対してスツルムの定理から区間 z ∈ (0, 1] におけ
る I(z) の解の個数は 0．I(0) = I(1) = −d3l より I(z) < 0
I(z) ≤ −d3l +
0
6775346d2l
41325
+
444dl
5
164.5
0
30
60
90
dl
120
150
√
11627977054429
≃ −0.53984, +164.49
I(dl ) = 0 の解は 0, 3387673± 41325
よって dl ≥ 165 に対して I(z) < I(dl ) < 0．
dl ≥ 3 に対して非自明な不動点に関するポテンシャル関数は
U (x1 , x2 (x1 ); ϵ(x1 )) > 0 を満たす．
= I(dl )
自明な不動点におけるポテンシャル関数
非自明な不動点におけるポテンシャル関数が常に正であるから，
ポテンシャル閾値は自明な不動点 (1, ϵ, ϵ) に関するポテンシャル
関数が正になる最大の ϵ で与えられる.
U (1, ϵ, ϵ) = 1 −
ϵ∗ = 1 −
dr
−ϵ
dl
dr
= 1 − RM N = ϵsha
dl
閾値飽和定理から ϵ∗ = ϵsha 未満の ϵ に対して空間結合
(dl , 3, 3)MN 符号の密度発展式の不動点は 0 になる
つまり，空間結合 (dl , 3, 3)MN 符号は BEC の通信路容量を達成
する
結論と課題
結論
十分大きい結合幅 w と結合数 L に対して空間結合
(dl ≥ 3, 3, 3)MN 符号は BP 復号で BEC の通信路容量を達成する
ことを証明した
課題
▶
双対定理を使い空間結合 HA 符号についても調べる
▶
空間結合 MN 符号のエラーフロアを調べる
▶
他のパラメーターの空間結合 MN 符号についても調べる

Download Report