線形時間で終端可能なレートロスの少ない 空間結合符号に関する研究 田添 宏治 坂庭・笠井研究室 February 12, 2014 田添 宏治 (坂庭・笠井研究室) 線形時間で終端可能なレートロスの少ない空間結合符号に関する研究 February 12, 2014 1 / 17 . 背景 . . 空間結合符号は Belief Propagation 復号法で通信路容量に迫る性能を持つ . 問題 . . レートロス 符号化の計算量 . 目標 . . BP 復号性能を落とさずにレートロスと符号化の計算量の軽減 . 結果 . レートロスと符号化の計算量を軽減する修正法を提案 BP 復号性能を2つの方法で評価 ▶ . ▶ 密度発展法 計算機シミュレーション 田添 宏治 (坂庭・笠井研究室) 線形時間で終端可能なレートロスの少ない空間結合符号に関する研究 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