GroupShu ffl edBP 復号法の新しいグループ分割手法について 平成 27 年度　修士論文

平成 27 年度 修士論文

Group Shuffled BP 復号法の

新しいグループ分割手法について

電気通信大学大学院 情報システム学研究科 情報ネットワークシステム学専攻

学籍番号 : 1452024 吉田 恭平

指導教員 森田 啓義 教授 小川 朋宏 准教授 山口 和彦 准教授

平 成 28 年 1 月 28 日

目 次

第1章 序 論 3

1.1 研 究 背 景 と 目 的 . . . 3

1.2 研 究 の 成 果. . . 4

1.3 本 論 文 の 構 成 . . . 4

第2章 準 備 5 2.1 線 形 符 号 . . . 5

2.1.1 ２ 元 線 形 符 号 . . . 5

2.1.2 LDPC符 号・IRA符 号. . . 6

2.2 グ ラ フ 理 論. . . 6

2.2.1 タ ナ ー グ ラ フ . . . 7

2.2.2 局 所 的 内 径 . . . 8

2.3 通 信 路 . . . 9

2.3.1 通 信 モ デ ル . . . 9

2.3.2 AWGN通 信 路 . . . 10

第3章 検 査 行 列 の 構 成 法 と Belief Propagation復 号 法 12 3.1 LDPC符 号 の 構 成 法 . . . 12

3.1.1 Gallagerの 構 成 法 . . . 12

3.1.2 立 川 の 構 成 法 . . . 13

3.2 LDPC符 号 のBP復 号 法 . . . 19

3.2.1 BP復 号 法 . . . 19

3.2.2 Shuffled BP復 号 法 . . . 21

3.2.3 Group Shuffled BP復 号 法 . . . 22

3.3 グ ル ー プ 分 割 手 法 の 関 連 研 究 . . . 23

3.3.1 次 数 が 降 順 と な る グ ル ー プ 分 割 手 法 . . . 24

3.3.2 隣 接 関 係 を 考 慮 し た グ ル ー プ 分 割 手 法 . . . 24

第4章 局 所 的 内 径 を 考 慮 し た

グ ル ー プ 分 割 手 法 26

4.1 提 案 法 の 考 え . . . 26 4.2 提 案 法 の ア ル ゴ リ ズ ム . . . 27 4.2.1 提 案 法 の 例 . . . 28

第5章 計 算 機 実 験 と 考 察 31

5.1 実 験 環 境 . . . 31 5.2 実 験 結 果 と 考 察 . . . 32 5.2.1 ビット 誤 り 率 と 平 均 反 復 回 数 . . . 32 5.2.2 最 大 反 復 回 数 の 変 化 に 伴 う ビット 誤 り 率 の 変 化 . . . . 46

第6章 ま と め と 今 後 の 課 題 49

6.1 ま と め . . . 49 6.2 今 後 の 課 題. . . 50

謝 辞 51

参 考 文 献 52

第 1 _{章 序論}

1.1 _{研究背景と目的}

近 年 ，誤 り 訂 正 符 号 と し てGallagerに よって1963年 に 提 案 さ れ た 低 密 度 パ リ ティ検 査(LDPC)符 号[1]が 注 目 さ れ て い る ．LDPC符 号 の 検 査 行 列 は ， タ ナ ー グ ラ フ と 呼 ば れ る ２ 部 グ ラ フ で 表 す こ と が 可 能 で あ り，LDPC符 号 の 代 表 的 な 復 号 法 で あ るBelief Propagation(BP)復 号 法[1, 2]（sum-product復 号 法 と も 呼 ば れ る ）で は ，タ ナ ー グ ラ フ の ノ ー ド 間 で 確 率 の 計 算 を メッ セ ー ジ 交 換 の 形 で 行って い る ．LDPC符 号 とBP復 号 法 の 組 み 合 せ に よ り 得 ら れ る 復 号 特 性 は 優 れ て お り，特 に ，長 い 符 号 長 のLDPC符 号 を 用 い た 場 合 に ，Shannon限 界 に 近 い 性 能 を 示 す こ と が 知 ら れ て い る[3]．

BP復 号 法 で は ，各 変 数 ノ ー ド が 並 列 に メッセ ー ジ の 交 換 を 行 う．一 方 で ，Group Shuffled BP(GSBP)復 号 法[9, 10]で は ，変 数 ノ ー ド 集 合 を 複 数 の グ ル ー プ に 分 割 し ，グ ル ー プ 内 で はBP復 号 法 と 同 じ 並 列 処 理 を 行 い ，グ ル ー プ 間 で は 逐 次 的 に ，前 の グ ル ー プ の メッセ ー ジ 交 換 が 終 わ り 次 第 ，次 の グ ル ー プ の メッセ ー ジ 交 換 を 行 う．こ の 順 で 処 理 す る こ と に よ り，前 の グ ル ー プ 内 で 更 新 し た メッセ ー ジ を 以 降 の グ ル ー プ で 利 用 で き る た め ， よ り 信 頼 性 の 高 い メッセ ー ジ を 得 る こ と が で き ，結 果 と し て よ り 少 な い 反 復 回 数 で 正 確 な 復 号 が 可 能 と な る ．

GSBP復 号 法 で は ，受 信 語 の ビット を 受 信 し た 順 に グ ル ー プ に 振 り 分 け て い る ．し か し ，ど の ビット か ら 更 新 を 行 う か で 性 能 に 差 が 生 ま れ る た め ，次 数（ ノ ー ド か ら の 辺 の 数 ）や 誤 り の 伝 播 を 考 慮 し た グ ル ー プ 分 割 手 法[11, 12]が 提 案 さ れ て い る ．本 論 文 で は ，既 存 の グ ル ー プ 分 割 手 法 と は 異 な る 指 標 と し て ，各 変 数 ノ ー ド の 局 所 的 内 径（ そ の 変 数 ノ ー ド を 含 む 最 短 閉 路 の 長 さ ）に 注 目 し て グ ル ー プ 分 割 を 行 う こ と を 提 案 す る ．

BP復 号 法 で は ，タ ナ ー グ ラ フ 上 に 短 い 閉 路 が あ る と ，確 率 計 算 が 正 確 に 行 え ず，性 能 が 悪 化 す る こ と が 知 ら れ て い る[13]．ま たGSBP復 号 法 で は ，誤った 計 算 が 行 わ れ た 場 合 ，そ の 結 果 も 以 降 の グ ル ー プ に 伝 播 し て し

ま う．そ こ で ，局 所 的 内 径 の 大 き い 変 数 ノ ー ド か ら グ ル ー プ に 振 り 分 け て 誤 り の 伝 播 を 防 ぐ こ と で ．ど れ ほ ど の 性 能 向 上 が 見 込 め る か を シ ミュ レ ー ション を 用 い て 評 価 す る ．特 に 本 論 文 で は ，閉 路 の 影 響 が 顕 著 に 出 や す い 符 号 長 が 短 い 符 号 を 用 い て ，局 所 的 内 径 の 効 果 に つ い て 確 か め る ．

1.2 _{研究の成果}

計 算 機 実 験 に よ り，最 大 反 復 回 数5回 で は ，提 案 法 は 既 存 法 に 比 べ 少 な い グ ル ー プ 数 で 優 れ た 訂 正 能 力 を 示 し た ．例 と し て ，SNR= 4.5[dB]の グ ル ー プ 数 が16の 場 合 で は ，提 案 法 に よ り ビット 誤 り 率 が36%改 善 し た ．ま た ，既 存 法 と 提 案 法 の 同 じ グ ル ー プ 数 で の 平 均 反 復 回 数 を 比 較 し た と こ ろ ，提 案 法 に よ り 収 束 速 度 の 向 上 が 見 ら れ た ．一 方 で ，最 大 反 復 回 数10 回 で は ，SNRの 値 が 小 さ い 場 合 は ，提 案 法 に よ る 訂 正 能 力 の 改 善 が 見 ら れ た が ，SNRの 値 が 高 い 場 合 で は ，提 案 法 に 比 べ 既 存 法 の 方 が 優 れ た 訂 正 能 力 を 示 し た ．こ れ は ，提 案 法 で は ，同 じ チェック ノ ー ド と 隣 接 す る 変 数 ノ ー ド が 同 じ グ ル ー プ の 振 り 分 け ら れ や す く な る た め ，更 新 メッセ ー ジ の 利 用 回 数 が 既 存 法 よ り 少 な く な る た め と 考 え ら れ る ．

1.3 _{本論文の構成}

論 文 の 構 成 は 以 下 の 通 り で あ る ．２ 章 で は ，LDPC符 号 や そ の タ ナ ー グ ラ フ に つ い て な ど ，論 文 構 成 の 上 で の 諸 準 備 を 行 う．３ 章 で は ，LDPC 符 号 の 検 査 行 列 の 構 成 法 と ，既 存 の 復 号 法 で あ るBP復 号 法 とGSBP復 号 法 に つ い て 述 べ る ．４ 章 で は ，局 所 的 内 径 を 元 に し た グ ル ー プ 分 割 手 法 を 提 案 し ，５ 章 で そ の 性 能 評 価 を 行 う．６ 章 で は ，本 論 文 の ま と め と 今 後 の 課 題 に つ い て 述 べ る ．

第 2 _{章 準備}

本 章 で は ，本 論 文 で 用 い る 基 礎 的 な 知 識 に つ い て 述 べ る ．ま ず2.1節 で ，２ 元 線 形 符 号 とLDPC符 号 ，IRA符 号 に つ い て 述 べ る ．次 に2.2節 で ， グ ラ フ 理 論 を 説 明 し た 後 ，検 査 行 列 か ら 定 義 さ れ る タ ナ ー グ ラ フ と ，タ ナ ー グ ラ フ に 関 す る パ ラ メ ー タ と し て 局 所 的 内 径 に つ い て 述 べ る ．最 後 に ，2.3節 で ，本 研 究 で 想 定 す る 通 信 モ デ ル とAWGN通 信 路 を 説 明 す る ．

2.1 _線形符号

2.1.1 ２ 元 線 形 符 号

あ る ア ル ファベット（ シ ン ボ ル の 有 限 集 合 ）Qと 正 の 整 数N が 与 え ら れ た と き ，符 号 長 がN の符 号Cと は ，Q^N の 部 分 集 合 で あ る ．ま た ，C の 要 素bを符 号 語と 呼 ぶ ．特 にQ=F2 ={0,1}，か つCがF^N2 の 線 形 部 分 空 間 で あ る と き ，Cを２ 元 線 形 符 号と よ ぶ ．本 論 文 で は ，符 号Cは 常 に 符 号 長 が Nの ２ 元 線 形 符 号 と し ，計 算 は 全 て2を 法 と し て 行 う も の と す る ．

符 号Cの 次 元 をK(≤N)と す る と ，CはK個 の 一 次 独 立 な ベ ク ト ル の 組 (g1,g2, ...,gK) (gi ∈F^N2 , i= 1,2, . . . , K)に よ り 張 ら れ る ．す な わ ち ，Cは

C ={b ∈F^N2 :b =a1g1 +a2g2+· · ·+aKgK, ai ∈F², i= 1,2, . . . , K} (2.1) で 表 現 で き る ．ま た ，次 元 を 符 号 長 で 割った 値R =K/Nを 符 号Cの符 号 化 率と 呼 ぶ ．

上 記giを 第i行 に 持 つK×N 行 列G∈F^K2^×N

G=

⎛

⎜⎜

⎜⎝ g₁ g2

...

gK

⎞

⎟⎟

⎟⎠ (2.2)

をCの生 成 行 列と 呼 ぶ ．符 号Cの 各 符 号 語bは ，生 成 行 列Gと ベ ク ト ル a= (a₁, a₂, . . . , a_K)∈F^K2 を 用 い て ，b=aGと 表 現 す る こ と が で き る ．ま た ，

符号Cの生成行列Gが与えられたとき，GH^T =0を満たすM(= N−K)×N 行 列H をCの検 査 行 列と 呼 ぶ ．こ こ で ，H^T はHの 転 置 行 列 で あ る ．し た がって ，符 号Cは

C ={b∈F^N2 :bH^T =0} (2.3) と も 定 義 で き る ．

2.1.2 LDPC _{符 号・} IRA _{符 号}

行 列 内 の1の 個 数 が 非 常 に 少 な い 行 列 を 疎 行 列 と 呼 ぶ ．２ 元 線 形 符 号 の 検 査 行 列H ∈ F^K2^×N が 疎 行 列 と な る と き ，Hに よ り 表 現 さ れ る 符 号 を ２ 元低 密 度 パ リ ティ検 査（Low Density Parity Check; LDPC）符 号[1]と 呼 ぶ ．

行 列 内 の1の 個 数 を重 みと 呼 ぶ ．行 列 のHの 各 列 の 重 み が 全 て 等 し く，

か つ 各 行 の 重 み が 全 て 等 し い 場 合 ，Hで 表 現 さ れ るLDPC符 号 を正 則 LDPC符 号と い い ，そ れ 以 外 の 場 合 を非 正 則LDPC符 号と い う．

特にM×Nの検査行列Hが，ランダムなM×(N−M)疎行列HuとM×M 階 段 行 列

Hp =

⎛

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎝

1 0 0 0 ... 0 0 1 1 0 0 ... 0 0 0 1 1 0 ... 0 0 ... ... ... ... ... ... ...

0 0 0 0 ... 1 0 0 0 0 0 ... 1 1

⎞

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎠

を 用 い て

H = [Hu|Hp]

と書けるとき，Hで表現されるLDPC符号を（組織）Irregular Repeat Accumulate (IRA) 符 号[4]と 呼 ぶ ．IRA符 号 は ，検 査 行 列Hの み を 用 い て 符 号 化 と 復 号 が 容 易 に で き る と い う 特 徴 が あ る ．IRA符 号 は ，一 般 のLDPC符 号 と 同 等 ，も し く は そ れ 以 上 の 誤 り 訂 正 能 力 を 持 つ こ と が 知 ら れ て い る[4]．

2.2 _{グラフ理論}

グ ラ フG = (V,E)は ，頂 点 集 合Vと 辺 集 合E ⊂V×Vで 構 成 さ れ る ．辺 に 向 き を つ け な い と き（ し た がって(u, v)∈E ⇔(v, u)∈Eが 成 り 立 つ と き ）G

を無 向 グ ラ フと 呼 び ，辺 に 向 き を つ け る と き ，Gを有 向 グ ラ フと よ ぶ ．ま た ，グ ラ フG= (V,E)の 頂 点 集 合Vを

各 i= 1,2に お い て (u, v ∈Vi =⇒(u, v)̸∈E)

を満たすように２つの頂点集合V1，V2に分割できるとき，Gを２部グラフと 呼 びG= (V¹∪V²,E)と 表 す．特 に ，E =V¹×V²と な る と き ，G= (V¹∪V²,E) を完 全 ２ 部 グ ラ フと 呼 ぶ ．

2.2.1 タ ナ ー グ ラ フ

LDPC符 号 の 検 査 行 列Hは ，タ ナ ー グ ラ フと 呼 ば れ る ２ 部 グ ラ フ で 表 現 できる．M×Nの検査行列Hが与えられたとき，Hを表現するタナーグラ フT = (V1∪V2,E)には，Hの列に対応する変数ノードv_i ∈V1(i= 1,2, . . . , N) と ，Hの 行 に 対 応 す る チェック ノ ー ドc_j ∈ V2 (j = 1,2, . . . , M)の 二 種 類 の ノ ー ド が あ り，Hmn = 1 (1≤n ≤ N,1≤m ≤M)と な るvnとcmを 辺 で 結 ぶ こ と で 構 成 さ れ る ．図2.1に 検 査 行 列Hと ，そ れ を 表 現 す る タ ナ ー グ ラ フ の 例 を 示 す．

図 2.1: LDPC符 号 の 検 査 行 列Hと 対 応 す る タ ナ ー グ ラ フ

タ ナ ー グ ラ フ の ノ ー ドvか ら 出 て い る 辺 の 数 を ノ ー ド の次 数と 呼 び ，各 ノ ー ド の 次 数 をd(v) (v ∈V¹∪V²)で 表 す．今 ，dvを 変 数 ノ ー ド の 最 大 次 数 と す る ．こ の と き ，変 数 ノ ー ド の 次 数 分 布 多 項 式λ(x)は ，変 数 ノ ー ド の 次 数 の 総 数 に 対 す る 次 数 がhと な る 変 数 ノ ー ド の 辺 の 総 数 の 割 合 をλh，

つ ま り

λ_h = '

ˆ

n:d(vˆn)=hd(vnˆ) 'N

n=1d(v_n) = h×|{v_nˆ :d(v_nˆ) =h}|

'N

n=1d(v_n) (2.4)

を 用 い て

λ(x) =

dv

(

h=1

λhx^h−1 (2.5)

で 定 義 さ れ る ．同 様 に ，dcを チェック ノ ー ド の 最 大 次 数 と し ，チェック ノ ー ド の 次 数 の 総 数 に 対 す る 次 数hと な る チェック ノ ー ド の 辺 の 総 数 の 割 合 をρh，つ ま り

ρh = '

ˆ

m:d(c_mˆ)=hd(c_mˆ) 'M

m=1d(cm) = h×|{cmˆ :d(cmˆ) =h}|

'M

m=1d(cm) (2.6)

と す る と ，チェック ノ ー ド の 次 数 分 布 多 項 式ρ(x)は

ρ(x) =

dc

(

h=1

ρhx^h−1 (2.7)

で 定 義 さ れ る ．

タ ナ ー グ ラ フ の 変 数 ノ ー ド に 符 号 語 の ビット を 対 応 さ せ る と ，タ ナ ー グ ラ フ は 符 号 の 制 約 条 件 を 示 し て い る ．つ ま り，ど の チェック ノ ー ドcjに お い て も ，cjに 隣 接 す る 変 数 ノ ー ド に 対 応 す る ビット の 総 和 は0に な る こ と と ，変 数 ノ ー ド に 符 号 語 の ビット が 対 応 し て い る こ と は 同 値 で あ る ． 例 1 図2.1に お い て ，符 号 語b= (b1, b2, b3, b4, b5)を 変 数 ノ ー ドv1, v2, v3, v4, v5

に そ れ ぞ れ 対 応 さ せ る ．こ の と き ，次 の 式 が 成 り 立 つ ． b1+b2 +b4 = 0

b2+b3 +b4 = 0 (2.8)

b3+b4 +b5 = 0

2.2.2 _{局 所 的 内 径}

一 般 の グ ラ フG = (V,E)に お い て ，道π:u0, u1, . . . , ukと は 1. (ui, ui+1)∈E (0≤i≤k−1);か つ

2. (u_i, u_i+1) = (u_i′, u_i′+1)と な る 整 数 組(i, i^′)（ た だ しi̸=i^′）は 存 在 し な い ．

を 満 た す ノ ー ド の 列 で あ り．そ の 長 さ（ 遷 移 回 数k）をℓ(π)で 表 す．特 に u0 =ukと な る と き を閉 路と 呼 ぶ ．

今 ，ノ ー ドuを 含 む 閉 路 の 集 ま り をC(u)と す る と ，uの局 所 的 内 径g(u) と は ，uを 含 む 最 短 閉 路 の 長 さ ，つ ま り

g(u) = min

p∈C(u)ℓ(π) (2.9)

で 定 義 さ れ る ．た だ し ，ど の 閉 路 に も 含 ま れ な い ノ ー ド の 局 所 的 内 径 は 任 意 の 大 き な 値 と す る ．

例 2 図 2.2の タ ナ ー グ ラ フ を 考 え る ．変 数 ノ ー ドv1とv2に お い て は ，閉 路π :v1, c1, v2, c2, v1がv1やv2を 含 む 最 短 閉 路 と な る の で ，g(v1) = g(v2) = 4 で あ る ．同 様 に ，v3とv₄に お い て は ，閉 路µ:v₃, c₃, v₄, c₂, v₁, c₁, v₃がv₃やv₄ を 含 む 最 短 閉 路 と な る の で ，g(v3) = g(v4) = 6で あ る ．一 方 ，v5やv6を 含 む 閉 路 は 存 在 し な い の で ，g(v5)とg(v6)は 任 意 の 大 き な 値（ 例 え ば100な ど ）と す る ．

図 2.2: タ ナ ー グ ラ フ と ノ ー ド の 局 所 的 内 径

2.3 _通信路

2.3.1 _{通 信 モ デ ル}

本 論 文 で は ，図2.3に 示 す 通 信 モ デ ル を 考 え る ．

い ま ，送 信 者 が 情 報a = (a1, a2, . . . , aK) ∈ F^N2 を 送 信 し た い と す る ．ま ず 送 信 者 は ，情 報aを 生 成 行 列Gを 用 い て ，長 さN (N > K)の 符 号 語 b=aG= (b₁, b₂, ..., b_N)∈F^N2 に 変 換 す る ．そ の 後 ，符 号 語bをBPSK変 調 に よ り 電 気 信 号 に 変 換 し ，通 信 路 を 通 し て 受 信 者 に 送 る ．受 信 者 側 で は ，

図 2.3: 通 信 モ デ ル

受 け 取った を 信 号 を 復 調 し 受 信 語y= (y1, y2, . . . , yN)∈R^N を 得 る ．そ の 後 ， 復 号 に よ り，符 号 語 の 推 定 語ˆb = (ˆb1,ˆb2, . . . ,ˆbN)∈F^N2 を 得 る ．

2.3.2 AWGN _{通 信 路}

本論文では，２値入力のAWGN通信路を仮定する．はじめに，式(2.10)を 用 い て 符 号 語b = (b1, b2, ..., bN)∈F2^N をBPSK変 調 に よ りs= (s1, s2, ..., sN)∈ {−1,1}^N に 変 換 す る ．

si =

)1 (bi = 0)

−1 (b_i = 1), (i= 1,2, . . . , N) (2.10) 得られたsがAWGN通信路に入力され，AWGN通信路内で，白色ガウス雑 音z = (z1, z2, ..., zN)∈R^Nが付加 され たも の が受 信語y= (y1, y2, . . . , yN)∈R^N と な る ．す な わ ち ，iビット 目 の 受 信 語 の シ ン ボ ルy_iは ，

yi =si+zi, i= 1,2, . . . , N (2.11) と な る ．こ こ で ，zi は 平 均0，分 散σ²の 正 規 分 布 の 確 率 密 度 関 数

P(zi) = 1

√2πσ²exp

*

−zi2

2σ² +

, i= 1,2, . . . , N (2.12) に 従 う 白 色 ガ ウ ス 雑 音 と す る ．

ま た ，Ebを 情 報1ビット 当 た り の エ ネ ル ギ ー ，N0を 片 側 電 力 エ ネ ル ギ ー と し ，AWGN通 信 路 の 信 号 対 雑 音 比(Signal to Noise ratio : SNR)Eb/N0を

E_b

N0 ! 1

2σ²R (2.13)

と 定 義 す る ．SNRの 単 位 は[dB]と な り，SNR E_b/N₀ =A[dB]の と き ，σ² = 10^−(10A)/2Rと な る ．SNREb/N0は ，通 信 路 を 評 価 す る 際 の 指 標 で あ り，SNR が 低 い ほ ど 雑 音 の 影 響 を 受 け や す く，SNRが 高 い ほ ど 雑 音 の 影 響 を 受 け に く く な る ．

第 3 章 検査行列の構成法と

Belief Propagation _復号法

本 章 で は ，LDPC符 号 の 検 査 行 列Hの 構 成 法 とBelief Propagation(BP)復 号 法[1]に つ い て 述 べ る ．ま ず3.1節 で ，LDPC符 号 の 検 査 行 列Hの 構 成 法 と し て ，Gallagerに よ り 提 案 さ れ た 構 成 法[1]と ，立 川 に よ り 提 案 さ れ た 構 成 法[7]に つ い て 述 べ る ．3.2節 で は ，LDPC符 号 の 復 号 法 で あ るBP復 号 法[1]を 説 明 し た 後 ，そ の 改 良 手 法 で あ るShuffled BP(SBP)復 号 法[9, 10]，

Group Shuffled BP(GSBP)復 号 法[9, 10]に つ い て 述 べ る ．

3.1 LDPC _{符号の構成法}

3.1.1 Gallager _{の 構 成 法}

1963年 ，Gallagerに よ りLDPC符 号 の 検 査 行 列Hの 構 成 法 が 提 案 さ れ た [1]．Gallagerの 構 成 法 で は ，列 の 重 み が1と な る 部 分 行 列 と ，部 分 行 列 に ラ ン ダ ム な 列 置 換 を 行った 行 列 を 結 合 す る こ と で 検 査 行 列 を 構 成 す る ．

い ま ，行 の 重 み がwr，列 の 重 み がwcと な るM ×N の 正 則LDPC符 号 の 検 査 行 列 を 構 成 す る こ と を 考 え る ．

Gallagerに よ る 構 成 法 は 次 の 通 り で あ る ．ま ず，行 の 重 み が 全 てwr，列 の 重 み が 全 て1と な る_w^N_r ×N行 列H₁^′ を 構 成 す る ．次 に ，行 列H₁^′ に ラ ン ダ ム な 列 置 換 を 行 い ，wc −1個 の 行 列H₂^′,H₃^′, . . . ,H_w^′_cを 生 成 す る ．最 後 に ， H₁^′,H₂^′, . . . ,H_w^′_cを 結 合 す る こ と で 行 の 重 み がwr，列 の 重 み がwcのM×N

（ た だ し ，M = _w^N_r ×wc）の 正 則LDPC符 号 の 検 査 行 列 を 得 る ．Gallagerの 構 成 法 で は ，_w^N_r が 整 数 で あ る 場 合 ，か つ 正 則LDPC符 号 の 場 合 に の み 構 成 が 可 能 で あ る ．

例 3 Gallagerの 構 成 法 に よ り 構 成 し た 行 の 重 み が4，列 の 重 み が3と な る

9×12検 査 行 列 の 例 を 次 に 示 す．

⎛

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎜⎝

1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0

⎞

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎟⎠

(3.1)

行 列(3.1)の 黒 線 で 区 切 ら れ た 各 部 分 行 列 は ，行 の 重 み が4，列 の 重 み が1 の3×12行 列 と なって い る ．

3.1.2 立 川 の 構 成 法

Gallagerの 構 成 法 で は ，_w^N_r が 整 数 で あ る 場 合 ，か つ 正 則LDPC符 号 の 場 合 に の み 構 成 が 可 能 と い う 制 約 が あった ．し か し ，実 際 に は ，通 信 環 境 等 の 関 係 で ，任 意 の 重 み の 非 正 則 なLDPC符 号 の 検 査 行 列 が 必 要 と な る 場 合 が あ る ．そ こ で ，立 川 に よ り，最 大 フ ロ ー ア ル ゴ リ ズ ム を 利 用 し た ， 任 意 の 重 み の 検 査 行 列 を 構 成 す る 手 法[7]が 提 案 さ れ て い る ．本 小 節 で は ，最 大 フ ロ ー ア ル ゴ リ ズ ム と ，立 川 の 構 成 法 に つ い て 述 べ る ．

最 大 フ ロ ー ア ル ゴ リ ズ ム

最 大 フ ロ ー ア ル ゴ リ ズ ム（ 詳 細 は 文 献[6]参 照 ）は ，各 辺 に 容 量(capacity) が 設 定 さ れ た ネット ワ ー ク で ，フ ロ ー(flow)と 呼 ば れ る デ ー タ 流 量 の 最 大 値 を 求 め る ア ル ゴ リ ズ ム で あ る ．

入 次 数 が0と な る 始 点 をs，出 次 数 が0と な る 終 点 をtと し ，sとtを 固 定 し た 有 向 グ ラ フG = (V,E)を 考 え る ．ノ ー ドvの 入 辺 集 合 をIn(v) ={e ∈ E|∃u ∈ Vs.t. e = (u, v)}，出 辺 集 合 をOut(v) = {e ∈ E|∃u ∈ Vs.t. e = (v, u)}と し ，辺 集 合E に 対 し て ，容 量cap_G:E →R⁺を 定 義 す る ．ま た ，容 量 が 与 え ら れ た と き ，フ ロ ー を 次 の1), 2)を 満 た す 関 数f low_G :E →R⁺と 定 義 す る ． 1) 各 辺e ∈Eに 対 し て ，f low_G(e)≤cap_G(e)が 成 り 立 つ ．

2) 各 ノ ー ドv ∈ V\{s, t}に 対 し て ，'

e∈In(v)f low_G(e) = '

e∈Out(v)f low_G(e)が 成 り 立 つ ．

有 向 グ ラ フG，容 量 cap_G，始 点s，終 点tか ら 構 成 さ れ る ４ つ 組 を ネット ワ ー クN = (G, s, t, cap_G)と 呼 ぶ ．

最 大 フ ロ ー ア ル ゴ リ ズ ム で は ，以 下 に 定 義 す る残 余 ネット ワ ー クNf を 用 い る ．Gの 逆 向 き の 有 向 辺 集 合 をERと し た と き ，有 向 グ ラ フG^′の 辺 集 合Eψと 容 量 cap_ψを 次 の よ う に 定 義 す る ．

• Eψ ={e∈E|f low_G(e)< cap_G(e)}∪{e_R ∈ER|f low_G(e)>0}

• f low_G(e)< cap_G(e)の と き ， capψ(e) = cap_G(e)−f low_G(e)

• f low_G(e)>0の と き ，capψ(e_R) = f low_G(e)

こ の と き ，有 向 グ ラ フG^′ = (V,Eψ)，始 点s，終 点t，容 量 capψか ら 構 成 さ れ る ４ つ 組 を 残 余 ネット ワ ー クNf = (G^′, s, t, capψ)と 定 義 す る ．

最 大 フ ロ ー ア ル ゴ リ ズ ム の 入 力 は ネット ワ ー クN で あ り，出 力 は max(

f low_G(ˆe) （ 最 大 フ ロ ー ） (3.2)

で あ る ．こ こ で ，出 力 の 式 の'は ，始 点sか ら の 出 辺ˆeの フ ロ ー の 和 を 意 味 す る ．

以 下 に 最 大 フ ロ ー ア ル ゴ リ ズ ム を 示 す．

最 大 フ ロ ー ア ル ゴ リ ズ ム

初 期 設 定 全 て の 辺e∈Eに つ い てf low_G(e) = 0と す る ．

ス テップ １ ネット ワ ー クN の 残 余 ネット ワ ー クNf = (G^′, s, t, capψ)を 構 成 す る ．

ス テップ ２ N^fの 始 点sか ら 終 点tま で の 道πを 幅 優 先 探 索 で 見 つ け る ．道 πが 存 在 し な い 場 合 ，ス テップ ４ へ 進 む ．

ス テップ ３ 道π =u1, u2, . . . , uj−1, ujが 存 在 す る と き ，∆(π)を 道πに 含 ま れ る 辺 の 容 量 の 最 小 値 ，つ ま り

∆(π) = min

1≤i≤j−1(capψ((ui, ui+1))) (3.3)

と し ，(ui, ui+ 1)の フ ロ ー を 次 の よ う に 更 新 す る ．

• (u_i, u_i+ 1)∈E の 場 合：f low_G((u_i, u_i+ 1)) :=f low_G((u_i, u_i+ 1)) +∆(π)

• (ui, ui+ 1) ∈ERの場合：f low_G((ui, ui+ 1)) :=f low_G((ui, ui+ 1))−∆(π) フ ロ ー を 更 新 し た 後 ，ス テップ １ へ 戻 り 残 余 ネット ワ ー ク を 更 新 し ， ス テップ ２ へ 進 む ．

ス テップ ４ 始 点sか ら 出 て い る 辺eˆの フ ロ ー の 総 和 を 最 大 フ ロ ー と し て 出 力 し 終 了 ．

立 川 の 構 成 法 の ア ル ゴ リ ズ ム

検 査 行 列 は タ ナ ー グ ラ フ に よ り 定 義 す る こ と が 可 能 で あ る た め ，検 査 行 列 を 構 成 す る 場 合 は タ ナ ー グ ラ フ を 求 め れ ば 良 い ．つ ま り，所 望 の M×Nの 検 査 行 列 を 構 成 す る こ と は ，濃 度 が|V1|=N，|V2|=Mと な る 完 全 ２ 部 グ ラ フW = (V1∪V2,V1×V2)を 考 え ，行 重 み ，列 重 み に 対 応 す る 次 数 の 条 件 を 満 た すW の 部 分 グ ラ フ を タ ナ ー グ ラ フ と し て 求 め る こ と と 同 義 で あ る ．立 川 の 構 成 法 で は ，有 向 完 全 ２ 部 グ ラ フBに ，始 点sと 終 点 t，お よ び そ れ ら に 付 随 す る 有 向 辺 を 加 え た グ ラ フGを 用 意 し ，Gの 各 辺 に 容 量 を 定 義 し た ネット ワ ー クN = (G, s, t, cap_G)の 最 大 フ ロ ー を 求 め る こ と で 所 望 の タ ナ ー グ ラ フ を 生 成 し て い る ．

いま，所望するタナーグラフT = (V¹∪V²,E)のV¹の変数ノードv1, v2, . . . , vN

の 次 数 を そ れ ぞ れφ^′₁,φ^′₂, . . . ,φ_N^′ と ，V2の チェック ノ ー ドc1, c2, . . . , cM の 次 数 を そ れ ぞ れω^′₁,ω^′₂, . . . ,ω_M^′ と す る ．以 下 に ，立 川 の 構 成 法 の ア ル ゴ リ ズ ム を 示 す．

入 力

• 変 数 ノ ー ド の 個 数N

• チェック ノ ー ド の 個 数M

• 各 変 数 ノ ー ド の 次 数φ^′₁,φ^′₂, . . . ,φ^′_N

• 各 チェック ノ ー ド の 次 数ω^′₁,ω^′₂, . . . ,ω_M^′ 出 力

• 変 数 ノ ー ド の 個 数N，チェック ノ ー ド の 個 数M，各 変 数 ノ ー ド の 次 数 がφ^′₁,φ^′₂, . . . ,φ^′_N，各 チェック ノ ー ド の 次 数 がω^′₁,ω₂^′, . . . ,ω^′_M と な る タ ナ ー グ ラ フ

立 川 の 構 成 法 の ア ル ゴ リ ズ ム

ス テップ １ |V1|=N，|V2|=M，か つ ，V1か らV2へ の 有 向 辺 を 持 つ 有 向 完 全 ２ 部 グ ラ フB = (V1∪V2,E)を 構 成 す る ．

ス テップ ２ 始 点sと 終 点t追 加 し ，sか らV1の 各 ノ ー ド に 有 向 辺 を ひ き ， V²の 各 ノ ー ド か らtへ 有 向 辺 を ひ く．Bにsとtお よ び そ れ ら に 付 随 す る 有 向 辺 を 追 加 し た グ ラ フ をGと す る ．ま た ，各vn∈V¹に 対 し て ， 容 量 cap_G((s, vn))を

cap_G((s, vn)) =φ^′_n (3.4) と す る ．同 様 に ，各cm ∈V2に 対 し て ，容 量 cap_G((cm, t))を

cap_G((cm, t)) = ω^′_m (3.5)

と す る ．ま た ，も と も とBに 含 ま れ て い た 辺eに つ い て は

cap_G(e) = 1 (3.6)

と す る ．そ し て ，グ ラ フG，始 点s，終 点t，容 量cap_Gの ４ つ 組 か ら な る ネット ワ ー クN = (G, s, t, cap_G)を 構 成 す る ．

ス テップ ３ ネット ワ ー クN = (G, s, t, cap_G)に 対 し て 最 大 フ ロ ー ア ル ゴ リ ズ ム を 適 用 す る ．た だ し ，幅 優 先 探 索 時 に ノ ー ド のindexを ラ ン ダ ム に 探 索 す る も の と す る ．つ ま り，す べ て の 道 を 探 す 場 合 で ，indexを 入 れ 替 え る ．道 が 見 つ か ら な い 場 合 は ，ア ル ゴ リ ズ ム を 終 了 す る ． ス テップ ４ 最 大 フ ロ ー ア ル ゴ リ ズ ム で 出 力 さ れ た 最 大 フ ロ ー が'N

n=1φ^′_n と 一 致 す る か 確 認 す る ．も し ，一 致 し な い 場 合 ，タ ナ ー グ ラ フ は 存 在 し な い と 返 す．一 致 す る 場 合 は ，フ ロ ー が0と な る 全 て の 辺 お よ び 始 点sとsに 繋 が る 辺 ，終 点tとtに 繋 が る 辺 を 削 除 し ，残った グ ラ フ の ベ ー ス グ ラ フ（ 有 向 辺 を 無 向 辺 と し て 得 ら れ る 無 向 グ ラ フ ）を 所 望 タ ナ ー グ ラ フ と し て 出 力 す る ．

例 4 立 川 の 構 成 法 を 用 い て ，変 数 ノ ー ド の 個 数N = 5，チェック ノ ー ド の 個 数M = 3，各 変 数 ノ ー ド の 次 数 がφ^′₁ =φ^′₂ = 2,φ^′₃ =φ^′₄ =φ^′₅ = 1，各 チェッ ク ノ ー ド の 次 数 がω₁^′ =ω^′₂ = 2,ω₃^′ = 3と な る タ ナ ー グ ラ フ を 構 成 す る こ と を 考 え る ．

ま ず，ス テップ １ ，ス テップ ２ に よ り 図3.1に 示 す ネット ワ ー クN を 構 成 す る ．こ こ で ，図 中 の 赤 字 は 辺 の 容 量 を 表 す．

次 に ，ス テップ ３ に お い て ，ネット ワ ー クN に 対 し て 最 大 フ ロ ー ア ル ゴ リ ズ ム を 適 用 し て ，最 大 フ ロ ー を 達 成 す る 道 を 表 す 図3.2と 最 大 フ ロ ー を 得 る ．こ こ で ，図 中 の 黒 い 辺 は フ ロ ー が0の 辺 ，赤 い 辺 が フ ロ ー が 非0 の 辺 で 赤 い 数 字 が フ ロ ー の 値 を 表 す．

最 後 に ，ス テップ4で は ，最 大 フ ロ ー と 変 数 ノ ー ド の 次 数 の 和 が 一 致 す る の で ，フ ロ ー が0と な る 全 て の 辺 お よ び 始 点sとsに 繋 が る 辺 ，終 点tと tに 繋 が る 辺 を 削 除 し ，残った グ ラ フ の 有 向 辺 を 無 向 辺 と し た グ ラ フ を タ ナ ー グ ラ フ と し て 出 力 す る ．

立 川 の 構 成 法 を 用 い る こ と で ，任 意 の 次 数 分 布 のLDPC符 号 の 検 査 行 列Hお よ びIRA符 号 の 検 査 行 列 の 部 分 行 列Huを 構 成 で き る ．本 論 文 で 使 用 す る 符 号 は ，立 川 の 構 成 法 に よ り 構 成 さ れ る 検 査 行 列 を 用 い る ．

Figure 5.3: resulting network N = (G, s, t, cap_G)

Figure 5.4: the graph after applying Max-Flow algorithm

Therefore, we delete s, t, edges from s to variable nodes and those from check nodes tot, and all edges whose flows are0. We obtain a desired Tanner graph as shown in Figure 5.5.

30

図 3.1: N = 5，M = 3の ネット ワ ー クN の 例（ 文 献[7] p.30よ り 引 用 ）

Figure 5.3: resulting network N = (G, s, t, capG)

Figure 5.4: the graph after applying Max-Flow algorithm

Therefore, we delete s, t, edges from s to variable nodes and those from check nodes tot, and all edges whose flows are0. We obtain a desired Tanner graph as shown in Figure 5.5.

図3.2: 最 大 フ ロ ー ア ル ゴ リ ズ ム を 適 用 し た グ ラ フ の 例（ 文 献[7] p.30 よ り 引 用 ）

18

3.2 LDPC _符号の BP _復号法

本 節 で は ，LDPC符 号 の 代 表 的 な 復 号 法 で あ るBelief Propagation（BP）

復 号 法[1]と ，そ の 改 良 手 法 で あ るShuffled BP（SBP）復 号 法[9, 10]，Group Shuffled BP（GSBP）復 号 法[9, 10]に つ い て 説 明 す る ．

チェックノードcmと隣接する変数ノードの添字集合をN(m) ={n :Hmn = 1}， 変数ノードvnと隣接するチェックノードの添字集合をM(n) = {m:Hmn = 1} と す る ．ま た ，符 号 語 をx= (x1, x2, . . . , xN)，受 信 語 をy= (y1, y2, . . . , yN)と し ，通 信 路 はBPSK変 調 を 伴 うAWGN通 信 路 を 仮 定 す る ．

い ま ，送 信 し た 符 号 語 のnビット 目(n = 1,2, . . . , N)の シ ン ボ ル がx_n = 0 で あ る と き に ，受 信 シ ン ボ ル がyn ∈ {0,1}(n = 1,2, . . . , N)で あ る 確 率 を P(yn|xn = 0)，xn = 1であるときに，受信シンボルがyn ∈{0,1}(n= 1,2, . . . , N) である確率をP(yn|xn= 1)と表すことにする．受信シンボルyn(n= 1,2, . . . , N) に 対 す る 対 数 尤 度 比 を

Ln= lnP(yn|xn= 0)

P(yn|xn= 1) (3.7)

と 定 義 す る ．ま た ，各 変 数 ノ ー ド は 受 信 語 の 各 ビット と 対 応 し て お り，受 信 ビット の 添 字 と 変 数 ノ ー ド の 添 字 は 一 致 す る ．

3.2.1 BP _{復 号 法}

BP復 号 法[1]は ，ファク タ ー グ ラ フ と 呼 ば れ る グ ラ フ を 元 に ，受 信 語y に 基 づ き 事 後 確 率 が 最 大 と な る 推 定 語x，つ ま りˆ

ˆ

x= arg max

x∈C

P(x|y) (3.8)

を 出 力 す る 復 号 法 で あ る ．BP復 号 法 で は ，各 ビット の 事 後 確 率 の 周 辺 化 計 算 を ，タ ナ ー グ ラ フ 上 で の メッセ ー ジ 交 換 の 形 式 で ，効 率 よ く 計 算 す る ．各 変 数 ノ ー ド が 同 時 に 変 数 ノ ー ド 処 理 を ，各 チェック ノ ー ド が 同 時 に チェック ノ ー ド 処 理 を 行 い ，そ の 結 果 を メッセ ー ジ の 形 で 交 換 す る こ と を 繰 り 返 し て 復 号 す る ．反 復l回 目 の チェック ノ ー ドcmか ら 変 数 ノ ー ドvn(n ∈N(m))へ の メッセ ー ジ をα^(l)mn，変 数 ノ ー ドvnか ら チェック ノ ー ド cm(m∈M(n))へ の メッセ ー ジ をβmn^(l) と す る ．以 下 にBP復 号 法 の ア ル ゴ リ ズ ム を 示 す（ 詳 細 は 文 献[8]な ど を 参 照 ）．

BP復 号 法 の ア ル ゴ リ ズ ム

ス テップ １（ 初 期 化 ）Hmn= 1を 満 た す 組(m, n)に 対 し てβmn⁽⁰⁾ =Lnと す る ． ま た ，反 復 回 数 を 表 す 変 数lの 初 期 値 を1と し ，最 大 反 復 回 数 をlmax

と す る ．

ス テップ ２（ メッセ ー ジ 更 新 ）n = 1,2, . . . , Nに つ い て 以 下 の 二 つ の 処 理 を 行 う．

行 処 理 ）m ∈M(n)に お い て ，α^(l)mnを 次 の よ う に 計 算 す る ．

α^(l)_mn = 2 tanh⁻¹

⎛

⎝ ,

n^′∈N(m)\{n}

tanh

-β_mn^(l−1)_′ 2

.⎞

⎠ (3.9)

こ こ で ，D\{d}は 集 合Dか ら 要 素dを 除 い た 集 合 を 表 し ，以 降 ， 簡 単 化 の た めD\dと 表 す．

列 処 理 ）m ∈M(n)に お い て ，βmn^(l) を 次 の よ う に 計 算 す る ． β_mn^(l) =Ln+ (

m^′∈M(n)\m

α^(l)_m′n (3.10)

ス テップ ３（ 一 時 推 定 ビット の 決 定 ）n = 1,2, . . . , N に お い て 推 定 ビット の 決 定 に 用 い る 値γn^(l)を 次 式 で 求 め る ．

γ_n^(l) =Ln+ (

m^′∈M(n)

α^(l)_m′n (3.11)

反復l回目の推定ビットxˆ^(l) = (ˆx^(l)₁ ,xˆ^(l)₂ , . . . ,xˆ^(l)_N)を次式によって決定する．

ˆ x^(l)_n =

)0 γn^(l) ≥0

1 γn^(l) <0, n= 0,1, . . . , N (3.12) ス テップ ４（ 終 了 判 定 ）xˆ^(l)H^T =0の 場 合 ，ま た は ，反 復 回 数lがlmaxの 場 合 は ，xˆ^(l) = (ˆx^(l)₁ ,xˆ^(l)₂ , . . . ,xˆ^(l)_N)を 推 定 語 と し て 出 力 し て 終 了 す る ．そ う で な れ ば ，l :=l+ 1と し て ス テップ ２ へ 戻 る ．

ス テップ ２ で の 行 処 理・列 処 理 の 図 を 図3.3に 示 す．ま た ，行 処 理・列 処 理 の 反 復 の 図 を 図3.4に 示 す．

図 3.3: BP復 号 法 の 行 処 理・列 処 理

図 3.4: BP復 号 法 の 行 処 理・列 処 理 の 反 復

3.2.2 Shuffled BP _{復 号 法}

BP復 号 法 で は ，1回 の 反 復 の 処 理 で ，全 て の チェック ノ ー ド で メッセ ー ジ を 同 時 に 更 新 し ，全 て の 変 数 ノ ー ド で メッセ ー ジ を 同 時 に 更 新 し て い る ．そ の た め ，各αmn^(l) （ 反 復l回 目 のc_mか らv_nへ の メッセ ー ジ ）は ，反 復l−1回 のv_n以 外 のc_mの 隣 接 ノ ー ド か らc_mに 送 ら れ て く る メッセ ー ジ β_mn^(l−1)′ (n^′ ∈M(m)\n）す べ て を 用 い て 更 新 し て い る ．ま た ，反 復l回 目 の 変 数 ノ ー ド か ら チェック ノ ー ド へ の メッセ ー ジβmn^(l) は ，α^(l)_m′n(m^′ ∈N(m)\m)を 用 い て 更 新 し て い る ．し か し ，メッセ ー ジ は 更 新 す る た び 信 頼 度 が 上 が る た め ，反 復l回 目 の メッセ ー ジα^(l)mnを 更 新 す る 際 に は ，反 復l−1回 目 の メッセ ー ジβ_mn^(l−1)′ よ り も 反 復l回 の メッセ ー ジβ_mn^(l)′を 用 い て 更 新 し た 方 が ， よ り 信 頼 度 の 高 いα^(l)mnを 得 る こ と が で き る ．

そ こ で ，Shuffled BP（SBP）復 号 法[9, 10]で は ，並 列 に 行 わ れ て い た 処 理

を ，各 ノ ー ド で 逐 次 的 に 処 理 す る こ と で ，可 能 な 限 り 反 復l回 の メッセ ー ジβ_mn^(l)′ を 用 い て 更 新 す る ．こ れ に よ り，よ り 少 な い 反 復 回 数 で 正 確 に 計 算 す る こ と が 期 待 で き る ．SBP復 号 法 で は ，BP復 号 法 の ス テップ ２ を 以 下 の よ う に 変 更 す る ．

SBP復 号 法 の 行 処 理 ，列 処 理

ス テップ ２（ メッセ ー ジ 更 新 ） n= 1,2, . . . , N に 対 し て

行 処 理 ）m ∈M(n)に 対 し てα^(l)mnを 次 の よ う に 計 算 す る ．

α^(l)_mn = 2 tanh⁻¹

⎛

⎜⎜

⎝ ,

n^′∈N(m)\n, n^′<n

tanh

-β_mn^(l)′

2 .

× ,

n^′∈N(m)\n, n^′>n

tanh

-β_mn^(l−′¹⁾

2 .⎞

⎟⎟

⎠

(3.13) 列 処 理 ）m ∈M(n)に 対 し てβmn^(l) を 次 の よ う に 計 算 す る ．

β_mn^(l) =L_n+ (

m^′∈M(n)\m

α^(l)_m′n (3.14)

3.2.3 Group Shuffled BP _{復 号 法}

SBP復 号 法 で は ，各 ノ ー ド で 逐 次 処 理 す る こ と で ，収 束 速 度 を 向 上 さ せ て い た ．し か し ，逐 次 的 な 処 理 で は ，処 理 を 並 列 に 行 うBP復 号 法 に 比 べ ， 復 号 の 際 に 遅 延 が 発 生 し て し ま う 問 題 点 が あ る ．そ こ で ，Group Shuffled BP(GSBP)復 号 法[9, 10]で は ，ノ ー ド を 複 数 の グ ル ー プ に 分 割 し ，グ ル ー プ 内 で は 並 列 に ，グ ル ー プ 間 で は 逐 次 的 に 実 行 す る こ と で ，遅 延 の 減 少 を 図って い る（ 図3.5参 照 ）．つ ま り，グ ル ー プ 数 が1のGSBP復 号 法 はBP 復 号 法 ，グ ル ー プ 数 がN（ 符 号 長 ）のGSBP復 号 法 はSBP復 号 法 と な る ．

こ こ で は ，文 献[9]を 参 考 に ，受 信 語 の 各 添 字 集 合Gkの 濃 度 が（ 均 等 に ） NGと な る よ う に

Gi = /

n ∈{1,2, . . . , N} 00 00i=

1 n NG

23

(3.15) と し て ，変 数 ノ ー ド の 添 字 集 合{1,2, . . . , N}をr(= N/NG)個 の 集 合（ グ ル ー プ ）G1, G₂, . . . , G_rに 分 割 す る ．GSBP復 号 法 の ア ル ゴ リ ズ ム は ，BP復 号 法 の ア ル ゴ リ ズ ム の ス テップ ２ を 以 下 の よ う に 変 更 す る ．

図 3.5: GSBP復 号 法

GSBP復 号 法 の 行 処 理 ，列 処 理

ス テップ ２（ メッセ ー ジ 更 新 ）k = 1,2, . . . , rの 順 で ，以 下 の ２ つ の 処 理 を 行 う  

行 処 理 ）n = (k−1)NG+ 1,(k−1)NG+ 2, . . . , kNGに お い てm∈M(n)に 対 し てα^(l)mnを 次 の よ う に 計 算 す る ．

α^(l)_mn = 2 tanh⁻¹

⎛

⎜⎜

⎝

,

n^′∈N(m)\n, n^′∈G_k′(k^′<k)

tanh

-β_mn^(l)′

2 .

× ,

n^′∈N(m)\n, n^′∈G_k′(k^′≥k)

tanh

-β_mn^(l−1)′

2 .⎞

⎟⎟

⎠

(3.16) 列 処 理 ）n = (k−1)N_G+ 1,(k−1)N_G+ 2, . . . , kN_Gに お い てm∈M(n)に

対 し てβmn^(l) を 次 の よ う に 計 算 す る ． β_mn^(l) =Ln+ (

m^′∈M(n)\m

α^(l)_m′n (3.17)

3.3 グループ分割手法の関連研究

GSBP復 号 法 の グ ル ー プ 分 け で は ，受 信 語 の ビット を 受 信 し た 順 に ，対 応 す る 変 数 ノ ー ド の 添 字 を グ ル ー プ に 振 り 分 け て い る ．し か し ，SBP復 号 法 ，GSBP復 号 法 で は ，先 に 更 新 す る メッセ ー ジ の 信 頼 性 を 向 上 さ せ る こ と で ，後 に 更 新 す る メッセ ー ジ の 信 頼 性 能 が 向 上 す る ．そ の た め ，変 数

ノ ー ド の 添 字 を 適 切 な グ ル ー プ に 振 り 分 け る こ と に よ り，更 新 す る メッ セ ー ジ の 信 頼 性 を 向 上 さ せ ，復 号 性 能 の 改 善 を 図 る こ と が 可 能 で あ る ． 本 節 で は ，グ ル ー プ 分 割 手 法 の 関 連 研 究 に つ い て 述 べ る ．

3.3.1 次 数 が 降 順 と な る グ ル ー プ 分 割 手 法

SBP復 号 法 ，GSBP復 号 法 で は ，次 数 が 大 き い 変 数 ノ ー ド は ，次 数 の 小 さ い 変 数 ノ ー ド に 比 べ て ，一 度 の 処 理 で 交 換 で き る メッセ ー ジ が 多 い た め ，メッセ ー ジ の 信 頼 性 も 高 く な る ．そ こ で ，SBP復 号 法 に お い て ，変 数 ノ ー ド の 次 数 が 降 順 と な る 順 に 更 新 処 理 を す る 手 法 が 内 川 ら に よ り 提 案 さ れ て お り[11]，ま た ，GSBP復 号 法 に お い て も 内 川 ら の 手 法 が 有 効 で あ る こ と が 佐 藤 ら に よ り 示 さ れ て い る[12]．

内 川 ら の 手 法 を 用 い た グ ル ー プ 分 け で は ，グ ル ー プ に 振 り 分 け ら れ て い な い 変 数 ノ ー ド の 添 字 の 中 で ，最 大 次 数 を 持 つ 変 数 ノ ー ド の 添 字 を 選 択 し グ ル ー プ に 振 り 分 け る ．こ れ に よ り，次 数 が 降 順 と な る よ う 変 数 ノ ー ド を 処 理 し ，従 来 のGSBP復 号 法 に 比 べ て ，信 頼 性 の 高 い メッセ ー ジ 更 新 を 行 う こ と が 可 能 で あ る ．

3.3.2 隣 接 関 係 を 考 慮 し た グ ル ー プ 分 割 手 法

GSBP復 号 法 で は ，反 復l回 目 の メッセ ー ジα^(l)mnを 更 新 す る を 更 新 す る 際 ，出 来 る だ け 反 復l回 の メッセ ー ジβ_mn^(l)_′を 利 用 す る こ と で 信 頼 性 の 高 い メッセ ー ジ 更 新 を 行って い た ．い ま ，グ ル ー プ 分 け の と き ，同 じ チェック ノ ー ドc1に 隣 接 し て い る 変 数 ノ ー ドv1, v2を 同 じ グ ル ー プ に 含 ま れ る よ う に グ ル ー プ 分 割 す る 場 合 を 考 え る ．こ の と き ，同 じ グ ル ー プ 内 で は 並 列 に メッセ ー ジ 更 新 を 行 う の で ，反 復l回 目 のc1か らv2へ の メッセ ー ジα^(l)₁₂ に ，反 復l回 目 のv1か らc1へ の メッセ ー ジβ₁₁^(l)を 用 い る こ と が 出 来 な い ．そ こ で ，佐 藤 ら は ，同 じ チェック ノ ー ド に 隣 接 す る 変 数 ノ ー ド が ，で き る だ け 同 じ グ ル ー プ に 含 ま れ な い よ う に グ ル ー プ 分 割 す る 手 法 を 提 案 し て い る[12]．

い ま ，変 数 ノ ー ド の 添 字n = 1,2, . . . , Nをr個 の グ ル ー プG₁, G₂, . . . , G_rに 分 割 す る こ と を 考 え る ．こ こ で ，タ ナ ー グ ラ フ の 辺 の 総 数 をD_max，各 グ ル ー プ に 含 ま れ る 変 数 ノ ー ド の 辺 の 合 計 をDk (k = 1,2, . . . , r)と し ，各 変

数 ノ ー ドvn(n= 1,2, . . . , N)の 次 数 をd(vn)と す る ．佐 藤 ら の ア ル ゴ リ ズ ム を 次 に 示 す．

ス テップ １ G1 =G2 =. . .=Gr ={}（{}は 空 集 合 ）と す る ．k := 1と す る ． ス テップ ２ 次 数 が 降 順 と な る 順 に 変 数 ノ ー ド の 添 字 を 一 つ ラ ン ダ ム に 選

択 し ，次 式 を 満 た す 限 りGkに 振 り 分 け る ．

k−1

(

i=1

|Di|+|Dk|≤kDmax

r (3.18)

式(3.18)を 満 た さ な い と き ，k :=k+ 1と し て ，ス テップ ２ を 繰 り 返 す．

で な け れ ば ，n := 1と し て ス テップ ３ へ 進 む ．

ス テップ ３ n ∈Gkと し ，次 式 を 満 た す 変 数 ノ ー ド の 添 字qを ラ ン ダ ム に 一 つ 選 択 す る ．

q= arg min

n^′∈G_k′

k̸=k^′, d(v_n^′)=d(vn)

⎧⎨

⎩ 00 00 00

7

i∈Gk′

M(n)∩M(i) 00 00 00+

00 00 0

7

j∈Gk

M(n^′)∩M(j) 00 00 0

⎫⎬

⎭ (3.19)

ス テップ4 ス テップ3で 選 ん だqに 対 し て ，次 式 か らη,η^′を 求 め る ．

η = 00 00 0

7

i∈G_k

M(n)∩M(i) 00 00 0+

00 00 00

7

j∈G_k′

M(q)∩M(j) 00 00

00 (3.20)

η^′ = 00 00 00

7

j∈G_k′

M(n)∩M(j) 00 00 00+

00 00 0

7

i∈Gk

M(q)∩M(i) 00 00

0 (3.21) も し ，η>η^′な ら ば ，グ ル ー プ のnとqを 入 れ 替 え る ．η ≤η^′な ら ば ， 入 れ 替 え な い

ス テップ5 も し ，n=Nな ら ば 終 了 ．そ う で な け れ ば ，n:=n+ 1と し て ス テップ3へ 戻 る ．

第 4 章 局所的内径を考慮した グループ分割手法

4.1 _{提案法の考え}

GSBP復 号 法 で は ，グ ル ー プ 間 で 逐 次 的 に 処 理 を 行 う た め ，先 に 処 理 し た グ ル ー プ で 更 新 し た メッセ ー ジ を 次 の グ ル ー プ 以 降 で 利 用 し ，収 束 速 度 を 向 上 さ せ て い た ．し か し ，先 に 処 理 す る グ ル ー プ で 誤 り を 含 む メッセ ー ジ 更 新 を 行った 場 合 ，従 来 のBP復 号 法 に 比 べ て ，誤 り を 含 む メッセ ー ジ を 早 く 伝 播 さ せ て し ま う た め ，解 へ の 収 束 が 遅 れ て し ま う 問 題 が あ る ． GSBP復 号 法[9]で は ，受 信 し た ビット の 添 字 を 昇 順 に グ ル ー プ に 振 り 分 け て お り，誤 り の 伝 播 に つ い て は 考 慮 し て い な い ．そ の た め ，誤 り を 含 む メッセ ー ジ の 伝 播 を 防 ぐ こ と で ，収 束 速 度 の 向 上 が 期 待 で き る ．

変 数 ノ ー ド が 送 る メッセ ー ジ の 信 頼 度 の 指 標 と し て ，２ 章 で 述 べ た 局 所 的 内 径 が あ る ．タ ナ ー グ ラ フ が 局 所 的 内 径 の 小 さ い 変 数 ノ ー ド を 持 つ 場 合 ，BP復 号 法 の 性 能 が 悪 化 す る こ と が 知 ら れ て い る[13]．実 際 ，あ る 変 数 ノ ー ド を 始 点 と 終 点 と す る よ う な 閉 路 が あ る 場 合 ，変 数 ノ ー ド か ら の メッセ ー ジ が 閉 路 を 通 し て 変 数 ノ ー ド 自 身 に 返って く る た め 事 後 確 率 が 収 束 し な い 状 況 に 陥 る 場 合 が あ り，特 に 局 所 的 内 径 の 値 が 小 さ い と き ， そ の 影 響 が 顕 著 に 表 れ る ．

そ こ で ，変 数 ノ ー ド の 局 所 的 内 径 が 降 順 と な る よ う 先 に 処 理 す る よ う グ ル ー プ 分 け す る こ と で ，誤 り の 伝 播 を 防 ぐ こ と が で き る の で は な い か と 考 え ら れ る ．ま た 非 正 則LDPC符 号 の 場 合 に は ，変 数 ノ ー ド の 次 数 が 降 順 と な る よ う グ ル ー プ 分 け を す る こ と で こ と で 収 束 速 度 が 向 上 す る こ と が 知 ら れ て い る[3]．本 研 究 で は ，次 数 と 局 所 的 内 径 を 考 慮 し た グ ル ー プ 分 割 手 法 を 提 案 す る ．

4.2 _{提案法のアルゴリズム}

今 ，符 号 長Nの 符 号 語 の ビット の 添 字 を ，サ イ ズ が 均 等 で あ る（ つ ま り, 各 グ ル ー プ の サ イ ズ がNG =N/rと な る ）r個 の グ ル ー プG1, G2, . . . , Grに 分 割 す る こ と を 考 え る ．ま た ，各 変 数 ノ ー ド の 次 数 をd(vn) (n = 1,2, . . . , N)，

局 所 的 内 径 をg(vn) (n = 1,2, . . . , N)と す る ．た だ し ，ど の 閉 路 に も 含 ま れ な い 変 数 ノ ー ド の 局 所 的 内 径 は 任 意 に 大 き な 値 と す る ．以 下 に 提 案 法 の ア ル ゴ リ ズ ム を 示 す．

提 案 法 の ア ル ゴ リ ズ ム

ス テップ １ G1 =G2 =. . .=Gr ={}と す る ．k := 1と す る ス テップ ２ |Gk|=NGと な る ま で ，次 の 操 作 を 繰 り 返 す．

n = 1,2, . . . , N に つ い て ，次 の 式(4.1)を 求 め る ． A=

) n /∈

7k i=1

Gi

00 00

0d(vn) = max

j /∈!_k

j=1Gj

d(vj)

;

(4.1) 求 め たAに つ い て ，次 式(4.2)を 求 め る ．

B={n∈A |g(vn) = max

h∈A g(vh)} (4.2) n^∗ = minBをGkに 追 加 す る ．

ス テップ ３ k =rな ら ば 終 了 ．そ う で な れ ば ，k :=k+ 1と し て ，ス テップ ２ へ 戻 る ．

提 案 法 の ス テップ １ は ，各 グ ル ー プG1, G2, . . . , Grを 空 集 合 と し ，G1か ら 添 字 を 振 り 分 け て い く こ と を 意 味 す る ．ス テップ ２ で は ，グ ル ー プGkの 要 素 数 が 最 大|NG|に な る ま で ，次 の1)と2)の 操 作 を 繰 り 返 す．

1) ま だ グ ル ー プ に 振 り 分 け ら れ て い な い 変 数 ノ ー ド の 添 字 の 中 か ら ，次 数 が 最 大 と な る 添 字 を 全 て 列 挙 し ，そ れ ら の 集 ま り を 集 合Aと お く

（ 式(4.1））．

2) Aに 含 ま れ る 要 素 を 添 字 と し て 持 つ 変 数 ノ ー ド を 考 え る ．そ の な か で ，最 大 の 局 所 的 内 径 を 持 つ 変 数 ノ ー ド の 添 字 集 合 をBと す る（ 式 (4.2)）．Bの 中 で 最 も 小 さ い 添 字n^∗をG_kに 追 加 す る ．

ス テップ ３ は 終 了 条 件 で ，全 て の 変 数 ノ ー ド の グ ル ー プ 分 け が 終 了 し て い る な ら ば ア ル ゴ リ ズ ム を 終 了 し ，ま だ グ ル ー プ 分 け さ れ て い な い 変 数 ノ ー ド が 残って い る な ら ば ，次 の グ ル ー プGk+1に 添 字 を 振 り 分 け て い く．

提 案 法 を 用 い る こ と で ，次 数 は 降 順 に ，同 じ 次 数 同 士 で あ れ ば 局 所 的 内 径 が 大 き い 変 数 ノ ー ド の 添 字 か ら 先 に 処 理 で き る ．こ れ に よ り，信 頼 度 が 低 く，誤 る 可 能 性 が 高 い 変 数 ノ ー ド の メッセ ー ジ の 伝 播 を 防 ぐ こ と が で き る ．

4.2.1 _{提 案 法 の 例}

図 4.1: 提 案 法 の グ ル ー プ 分 け の 例 の タ ナ ー グ ラ フ

図4.1のタナーグラフを用いて提案法の例を示す．今，変数ノードv1, . . . , v6

の 添 字 を3つ の グ ル ー プG1, G2, G3に 分 け る と す る（ よって ，各 グ ル ー プ に 入 る 要 素 数 はN_G = 6/3 = 2と な る ）．ど の 閉 路 に も 含 ま れ な い 変 数 ノ ー ド の 局 所 的 内 径 の 値 は100（ 任 意 の 大 き な 値 ）と す る ．図4.1の 例 で は ，各 変 数 ノ ー ド の 次 数 はd(v1) =d(v2) =d(v3) =d(v4) = 2, d(v5) = d(v6) = 1, ま た ， 局 所 的 内 径 はg(v1) = 4, g(v2) = 4, g(v3) = 6, g(v4) = 6, g(v5) = 100, g(v6) = 100 で あ る ．

提 案 法 の 例 を 次 に 示 す．最 初 に ，ス テップ １ で 各 グ ル ー プ をG1 =G2 = G3 ={}と す る ．次 に ，ス テップ ２ で|G1|= 2と な る ま で ，変 数 ノ ー ド の 添 字 を 振 り 分 け る ．ま ず，式(4.1)に よ り，最 大 次 数 の 変 数 ノ ー ド 集 合Aを 求 め る ．次 数 が 最 大 と な る の は ，次 数 が2で あ るv₁, v₂, v₃, v₄と な る の で ，添 字 集 合A={1,2,3,4}を 得 る ．次 に ，Aの 中 で ，局 所 的 内 径 が 最 大 の 変 数

ノ ー ド の 添 字 集 合Bを 求 め る と ，B ={3,4}と な る ．そ し て ，Bの 要 素 の 中 で 添 字 の 値 が 最 小 に な る3がG1に 追 加 さ れ る（ 図4.2）．同 様 に ，も う 一 度 ス テップ ２ を 行 う．ま だ グ ル ー プ に 振 り 分 け ら れ て い な い 変 数 ノ ー ド の 中 で 最 大 次 数 と な る 変 数 ノ ー ド の 添 字 集 合Aを 求 め る と ，A ={1,2,4} を 得 る ．A={1,2,4}の 中 で 最 大 の 局 所 的 内 径 を 持 つ 変 数 ノ ー ド の 添 字 は 4な の で ，4をG1に 追 加 し ，G1 ={3,4}を 得 る（ 図4.3）．|G1|= 2と な る の で ス テップ ３ へ 移 る ．ス テップ ３ で は ，グ ル ー プ 分 け が 終 了 し て い な い の で ，k := k+ 1と し ，G2へ 添 字 を 振 り 分 け る た め に ス テップ ２ へ 戻 る ． 今 度 はG2 に 対 し て ス テップ ２ を 行 い ，G2 = {1,2}を 得 る ．ス テップ ３ で k :=k+ 1と し ス テップ ２ へ 戻 る ．最 後 に ，ス テップ ２ でG3に 対 し て 振 り 分 け を 行 いG3 ={5,6}と な る ．こ れ で ，す べ て の 変 数 ノ ー ド の 添 字 が グ ル ー プ に 振 り 分 け ら れ た（ 図4.4）．

図 4.2: 提 案 法 の グ ル ー プ 分 け の 例 １

図 4.3: 提 案 法 の グ ル ー プ 分 け の 例 ２

図 4.4: 提 案 法 の グ ル ー プ 分 け の 例 ３