線形時間で終端可能なレートロスの少ない
空間結合符号に関する研究
田添 宏治
坂庭・笠井研究室
February 12, 2014
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
1 / 17
.
背景
.
.
空間結合符号は Belief Propagation 復号法で通信路容量に迫る性能を持つ
.
問題
.
.
レートロス
符号化の計算量
.
目標
.
.
BP 復号性能を落とさずにレートロスと符号化の計算量の軽減
.
結果
.
レートロスと符号化の計算量を軽減する修正法を提案
BP 復号性能を２つの方法で評価
▶
.
▶
密度発展法
計算機シミュレーション
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
2 / 17
(dl , dr , L) 空間結合符号のパリティ検査行列
dk =dr /dl
}|
{
z}|{
z
L + dl − 1
P P
1,5 1,6
P2,3 P2,4 P2,5 P2,6
P
P
P
P
P
P
3,1 3,2 3,3 3,4 3,5 3,6
P4,1 P4,2 P4,3 P4,4 P4,5 P4,6
P
P
P
P
P
P
5,1 5,2 5,3 5,4 5,5 5,6
P
P
P
P
P
P
6,1 6,2 6,3 6,4 6,5 6,6
P7,1 P7,2 P7,3 P7,4 P7,5 P7,6
P
P
P
P
P
P
8,1 8,2 8,3 8,4 8,5 8,6
P9,1 P9,2 P9,3 P9,5 P9,6 P9,7
P
P
P
P
10,1 10,2 10,3 10,4
P11,1 P11,2
|
{z
}
dk L
(dl , dr ) 正則符号のパリティ検査行列を分割して帯状に並べて得られる
z }| {
dr
dl
z
}|
{
P1,1 P1,2 P1,3 P1,4 P1,5 P1,6
P2,1 P2,2 P2,3 P2,4 P2,5 P2,6
P3,1 P3,2 P3,3 P3,4 P3,5 P3,6
Pi, j はサイズ M × M の 2 元置換行列
M は数千∼数万を想定
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
3 / 17
レートロス: (空間結合符号のレート) − (正則符号のレート) =
dk L − (L + dl − 1) dk − 1 dl − 1
=
−
dk L
dk
dk L
dr − dl dk − 1
正則符号のレート:
=
dr
dk
dl − 1
dk L
空間結合符号のレート:
.
問題点Àレートロスが大きい
.
例えば dl = 3, dr = 6, L = 30 の時
dl − 1
= 0.0333...
. dk L
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
4 / 17
逐次処理：計算量 O(M)
P1,5 x1 +P1,6 x2
P2,3 x1 +P2,4 x2 +P2,5 x3 +P2,6 x4
P3,1 x1 +P3,2 x2 +P3,3 x3 +P3,4 x4 +P3,5 x5 +P3,6 x6
P4,1 x3 +P4,2 x4 +P4,3 x5 +P4,4 x6 +P4,5 x7 +P4,6 x8
..
..
..
..
.
.
.
.
=0
=0
=0
=0
終端処理：計算量 O(M 2 )
P8,5 x15 + P8,6 x16
= P8,1 x11 +P8,2 x12 +P8,3 x13 +P8,4 x14
P9,3 x15 + P9,5 x16 + P9,6 x17 + P9,7 x18 =
P9,1 x13 +P9,2 x14
P10,1 x15 +P10,2 x16 +P10,3 x17 +P10,4 x18 =
0
P11,1 x17 +P11,2 x18 =
0
.
問題点Á終端処理の計算量
.
終端処理の線形方程式を解くためには 4M × 4M の行列の掛け算が必要
.M は数千∼数万を想定しているためこの計算は困難
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
5 / 17
修正 (dl , dr , L) 空間結合符号のパリティ検査行列
P P
1,5 1,6
P2,3 P2,4 P2,5 P2,6
P
P
P
P
P
P
3,1 3,2 3,3 3,4 3,5 3,6
P4,1 P4,2 P4,3 P4,4 P4,5 P4,6
P
P
P
P
P
P
5,1 5,2 5,3 5,4 5,5 5,6
P
P
P
P
P
P
6,1 6,2 6,3 6,4 6,5 6,6
P7,1 P7,2 P7,3 P7,4 P7,5 P7,6
P
P
P
P
P
P
8,1 8,2 8,3 8,4 8,5 8,6
P
P
P
P
P
P
9,1 9,2 9,3 9,5 9,6 9,7
P10,1 P10,2 P10,3 P10,4
P11,1 P11,2
.
修正À
.
.空間結合符号の下から (dl
田添 宏治 (坂庭・笠井研究室)
− 2)M 行を削除
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
6 / 17
レートロス: (空間結合符号のレート) − (正則符号のレート) =
dk L − (L + dl − 1) dk − 1
1
=
−
dk L
dk
dk L
dr − dl dk − 1
正則符号のレート:
=
dr
dk
1
dk L
空間結合符号のレート:
.
改善点Àレートロスの軽減
.
例えば dl = 3, dr = 6, L = 30 の時
dl − 1
1
= 0.0333... −→
= 0.0166...
d
L
d
k
kL
.
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
7 / 17
修正によって終端処理で解くべき方程式が小さくなる
P9,6 x17 + P9,7 x18 =P9,3 x15 +P9,5 x16 +P9,1 x13 +P9,2 x14
P10,3 x17 +P10,4 x18 =
P10,1 x15 +P10,2 x16
次数によらず以下の問題に帰着できる
[
P1
P3
][ ] [ ]
P2 x 1
s
= 1
P4 x 2
s2
.
修正Á拡大次数 M が十分大きい時の復号性能を変えない修正
.
[
P1
P3
] [
IM
P2
=
P4
IM
.
田添 宏治 (坂庭・笠井研究室)
′
IM
IM
0
1
]
′
, IM
= 0
0
0
0 0 0 0
0 0 0 0
M×M
.
1 0 . . 0 ∈ F2
0 1 0 0
0 0 1 0
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
8 / 17
.
改善点Á単一のアキュムレータで終端処理を実行可能
.
例えば x1 = (x1 , x2 , x3 ), x2 = (x4 , x5 , x6 ), s1 = (s1 , s2 , s3 ), s2 = (s4 .s5 , s6 ) の時，
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
0 x1 s1
0 x2 s2
0 x3 s3
=
0 x4 s4
0 x5 s5
1 x6
s6
次をのように計算できる
x1 = s1 ,
x2 = x4 + s2 ,
x3 = x5 + s3 ,
.
田添 宏治 (坂庭・笠井研究室)
x4 = x1 + s4
x5 = x2 + s5
x6 = x3 + s6
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
9 / 17
符号長無限大における性能評価
密度発展法によるビット消失確率の追跡 (BEC ϵ = 0.4)
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
p(ℓ)
i
p(ℓ)
i
0
0
2
4
6
8
10
12
14
16
18
2
4
6
8
10
i
12
14
16
18
i
(ℓ)
BP 復号の第 ℓ ラウンドにおける各 xi ∈ F2M の消失確率 pi の変化の様子
空間結合符号 (左)，提案する修正空間結合符号 (右)
BP 閾値を知りたい
ϵ BP = sup{ϵ | lim p(ℓ)
i = 0 for all i }
ϵ
田添 宏治 (坂庭・笠井研究室)
l→∞
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
10 / 17
結合数 L = 3, 5, 9, 17, 33, 65 の変化に伴う BP 閾値と符号化率の変化の様子
0.8
0.7
符号化率 R
0.6
0.5
0.4
0.3
0.2
0.1
Shannon Limit
(3,6,L)
(3,9,L)
(3,12,L)
(3,6,L) modified
(3,9,L) modified
(3,12,L) modified
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
BP 閾値 ϵ BP
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
11 / 17
符号長有限における性能評価
100
修正正 (dl = 3, dr = 9, L = 30, M = 1000) 空間結合符号
10-1
ビット消失確率
10-2
10-3
10-4
10-5
10-6
0.24
0.26
0.28
0.30
0.32
0.34
消失確率
修正空間結合符号はエラーフロアにおける復号性能が悪い
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
12 / 17
P P
1,5 1,6
P2,3 P2,4 P2,5 P2,6
P P P P P P
3,1 3,2 3,3 3,4 3,5 3,6
P4,1 P4,2 P4,3 P4,4 P4,5 P4,6
P5,1 P5,2 P5,3 P5,4 P5,5 P5,6
P6,1 P6,2 P6,3 P6,4 P6,5 P6,6
P7,1 P7,2 P7,3 P7,4 P7,5 P7,6
P8,1 P8,2 P8,3 P8,4 P8,5 P8,6
P
P
P
P
P
P
9,1 9,2 9,3 9,4 9,5 9,6
P10,1 P10,2 P10,3 P10,4
赤く表した部分の復号性能がエラーフロアにおいて支配的
▶
▶
赤く表した部分行列の最小サイクル長を大きくすることでエラーフロアを改善
可能
赤い部分の復号性能が修正空間結合符号のエラーフロアの近似になる
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
13 / 17
ビット消失確率の改善
10-3
改善前
改善後
-4
ビット消失確率
10
10-5
10-6
10-7
10-8
0.27
0.28
0.29
0.30
0.31
0.32
0.33
0.34
消失確率
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
14 / 17
エラーフロアにおいて近似は緊密である
100
修正空間結合符号のエラーフロア
10-1
近似
ビット消失確率
10-2
10-3
10-4
10-5
10-6
0.24
0.26
0.28
0.30
0.32
0.34
消失確率
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
15 / 17
まとめ
.
修正空間結合符号の提案
.
.
レートロスが少ない
終端処理の計算量が少ない
.
修正空間結合符号の復号性能
.
符号長無限大では空間結合符号と等しい性能
符号長有限長ではエラーフロアの性能が劣化
復号誤りの支配的な原因となっている部分を特定
.
▶
エラーフロア性能の改善と近似が可能に
.
今後の課題
.
.
他の通信路での性能評価
エラーフロア性能をどこまで改善できるかの証明
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
16 / 17
関連発表
国内研究会
田添宏治, 笠井健太, 坂庭好一,“空間結合符号に対する効率の良い終端法”, 信学
技報, 信学技報, vol. 112, no. 215, IT2012-32, pp. 7-12, 2012 年 9 月.
田添宏治, 笠井健太, 坂庭好一,“線形時間で終端可能な組織的空間結合符号”, 信
学技報, vol. 112, no. 124, IT2012-24, pp. 91-96, 2012 年 7 月.
国際学会
(Invited Paper) K. Tazoe, K. Kasai, and K. Sakaniwa, “Efficient termination of
spatially-coupled codes,” Proc. 2012 IEEE Information Theory Workshop
(ITW), pp. 30-34, Sept. 2012.
田添 宏治 (坂庭・笠井研究室)
線形時間で終端可能なレートロスの少ない空間結合符号に関する研究
February 12, 2014
17 / 17
© Copyright 2025 ExpyDoc
