空間結合符号笠井 健太
東京工業大学

平成２６年１１月１８日
IBIS2014 ＠名古屋大学

1 / 21

最近の符号理論の研究で分かったこと
ルーピー BP によって解かれるシステムをいくつか用意して，チェイン状に結合させると大域的な MAP 解をルーピー BP で解くことができる．

システムを L(= 5) 個コピーしてもルーピー BP で訂正できるノイズレベ
ルは個々のシステムのそれと同じだが，隣と結合して大きな結合システムを作ると，ルーピー BP で訂正できる
ノイズレベルは個々のシステムが MAP で訂正できるノイズレベルまで向上する
2 / 21

符号理論が解決しようとしている問題
x = (x1 , . . . , xn ) ∈ C(H) を送信して y = (y1 , . . . , yn ) を受信する．
C(H) : = {x ∈ {0, 1}n |Hx = 0}

送信語は一様分布することを仮定

Pr(X̂ = x̂) : =(H ∈ {0, 1}m×n , n ≃ 105 )[x ∈ C]#C

ノイズの統計的性質 Pr(Y |X) を知っていることを仮定する．
簡単のために独立性も仮定する．
n!
Pr(Y |X) =Pr(Yj |Xj )j=1

符号理論の目的
このとき，H をうまく設計して #C(H) を 2nI(X;Y ) にできるだけ近づけて，エラーレート Pr(xj (Y ) ̸= Xj ) をできるだけ小さくする推定 x̂j (y) をO(n) の計算量で実現したい．
3 / 21

符号理論が解決しようとしている問題の難しさ
エラーレートを最小にする推定は MAP 推定 x̂MAP (y) である．

x̂MAP(y) : = argmax pXj |Y (xj |y)jxj ∈{0,1}= argmax"xj ∈{0,1} ∼xj= argmax"

xj ∈{0,1} ∼xj= argmax"xj ∈{0,1} ∼xj

pX|Y (x|y)∼ xj は xj 以外の x

pY |X (y|x)pX (x)/pY (y)pY |X (y|x) [x ∈ C(H)]/#C(H)[x ∈ C(H)] ̸= 0 な x ∈ C の数は n の指数オーダなので，素朴な
x̂MAP(y) の計算は困難である．
j4 / 21現代符号理論では，解くべき問題の拘束条件を利用者が設計できる
前のスライドの最後の式 MAP 推定 x̂MAP (y) をルーピー BP で解けるよ
うに行列 H を設計し，符号理論の目的を達成することに成功している．

pY |X (y|x) と [x ∈ C(H)] は次のように因子分解できる
pY |X (y|x) =[x ∈ C(H)] =n!
i=1m!
i=1

pYj |Xj (yj |xj )# "j:Hi,j =1

xj = 0$ルーピー BP の信頼性
グラフィカルモデルの局所木性により担保されるルーピー BP の低計算量スパースに因子分解できる (各因子の引数が少ない) ことで担保される
5 / 21列重み ルーピー
dl ，行重みである列数 nHの行列
H
BPdrに適した行列の設計方法

例．dl Low-Density= 2, dr = 4,n = 20 符号
Parity-Check⎛ 1000010000100001⎞

列重み l，行重み r である列数 n の行列 H
0100000000101100
⎜⎟
000
1
1000
10000001
例．
l=2,r=4,n=20⎜⎟⎜ 0 0⎛0 10 01000 10 1000010 00 1100000 00 10⎞⎟TH = ⎜ 1 0 1 0010000 10 0100000 00 1000101 00 00 ⎟ , C = {x ∈ Fn|Hx= 0}2⎜ ⎜ 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 ⎟⎟⎝ 0 0⎜1 0 0 0 0 0 1 0 0 1 0 1 0 0⎟⎠0000101001010000⎟
0 1⎜
H=⎜0 10 00110 00 0110100 00 0000000 10 00⎟ , C = {x ∈ {0, 1}n | Hx = 0}⎟0 0⎜0100000
1001010⎝ 0010000010010100⎠
0100010100000010
0001000001001010

グラフィカルモデル [x ∈ C(H)] =グラフィカルモデル'mi=1()

j:Hi,j =1 xj = 0*[x ∈ C(H)]m # "$!
=xj = 0i=1j:Hi,j =16 / 216

消失通信モデルでルーピー BP の性能を測ろう
消失確率 ϵ の消失通信路 BEC(ϵ)+?
with probability ϵYj =Xj with probability 1 − ϵ1１次元のパラメータで表されるシンプルな方程式を解くことで，消失通信路における復号誤り率を評価できる．

2

消失通信路の評価に用いた１次元のパラメータを確率分布に拡張することで，容易に他の通信路における復号誤り率を評価することができる．

3

消失通信路でシャノン限界に達成する符号の構成法を開発すれば，一般の無記憶通信路でも同様な構成法でシャノン限界に接近する符号を構成できる．
7 / 21

ルーピー BP の動作のもよう
x5 + x7 + x10 + x12 = 0 (∗)❄

x5x7x10x12

ルーピー BP の途中で x5 =?, x7 = 1, x10 = 1, x12 = 0 とすると，式 (∗)
から，x5 = 1 であることが分かる．
？がなくなるか，決定できる？がなくなるまで繰り返し更新する辺の数に比例する計算量 O(n) で，訂正を完了できる．
8 / 21(l, r) 符号の BEC(ϵ) におけるルーピー BP の訂正性能
次数 r である拘束条件ノードのメッセージ消失確率

q (t) = 1 − (1 − p(t−1) )r−1
次数 l であるビットノードのメッセージ消失確率p(t) = ϵ(q (t) )l−1
まとめると，p(t) = ϵ(1 − (1 − p(t−1) )r−1 )l−1
= f (g(p(t−1) ); ϵ)BP 閾値：(l, r) 符号の性能を測る指標
ϵBP (l, r) = sup{ϵ | lim p(t) = 0}t→∞

ルーピー BP で訂正可能な最大ノイズレベルを表している．
9 / 21非空間結合システム (l, r) 符号の性能解析 (つづき)(l, r)
(2,4)
(3,6)
(4,8)
(5,10)(6,12)(7,14)ϵBP (l, r)
0.33330.42940.38340.34160.30750.2797ϵMAP (l, r)
0.33333
0.488150.49774
0.499490.49988
0.49997

非結合システム (l, r) 符号の MAP 閾値 ϵMAP (l, r),n"1ϵMAP (l, r) = sup ϵ |Pr(Xi ̸= x̂MAP(Y (ϵ))) = 0i
ni=1x = (x1 , . . . , xn ) : (l, r) 符号の符号語

10 / 21

非空間結合システム (l, r) 符号の性能解析(t)(t−1)

p1 = f (g(p1); ϵ)(t)············(t−1)

p5 = f (g(p5); ϵ)

空間結合システム (l, r, L, w) 符号の性能解析/
1 " .1 "(t+1)(t)
pi=fg(pi+j−k ); ϵi−kw
w
w−1

w−1

k=0

j=0

i = 1, 2, . . . , Lw は結合幅: w 離れたシステムまで結合する (例．w = 2)
11 / 21

空間結合符号システムの訂正過程デモのページ
reg36_eps048_animation.gif を開く

l = 3, r = 6, L = 51, w = 2, ϵ = 0.48
なぜ端から訂正されていくのかを説明する
なぜ中から訂正されていかないのかを説明する
スライディング復号法を説明する

12 / 21結合システムの訂正性能はどこまで向上しているのか？
結合システム (l, r, L, w) 符号の BP 閾値 ϵBP (l, r, L, w),(t)ϵBP (l, r, L, w) = sup ϵ | lim pi = 0, i = 1, . . . , Lt→∞結合システムの BP 閾値は非結合システムの MAP 閾値と一致する[2010 Kudekar et al., 2011 Takeuchi et al., 2012 Yedla et al. ]lim lim ϵBP (l, r, L, w) = ϵMAP (l, r)

w→∞ L→∞(l, r)
(2,4)
(3,6)
(4,8)
(5,10)(6,12)(7,14)ϵBP (l, r)
0.33330.42940.38340.34160.30750.2797ϵMAP (l, r)
0.33333
0.488150.49774
0.499490.49988
0.49997
13 / 21

空間結合符号の定義 (範囲)

このように，BP 復号の連鎖反応が端から起こり結合前よりも強いレベルの誤りを訂正することができる事を空間結合効果と呼び，空間結合効果が起こることを狙って設計された符号を空間結合符号と呼ぶ．

14 / 21

Felström-Zigangirov の空間結合符号の構成法

H=
1. 行列 H を斜めに切る

15 / 21

Felström-Zigangirov の空間結合符号の構成法 (続き)

′
H =
2.

を L 個コピーする

3. 対角状にコピー行列を並べる.
4. 疎な帯行列であるパリティ検査行列 H ′ が得られる

16 / 21

空間結合符号の万能性
空間結合符号より前に開発されていた誤り訂正符号は通信路に依存した設計が必要であった
空間結合符号は，任意の無記憶通信路だけでなく有記憶通信路に対してもその理論限界の訂正性能を達成することが知られている"yj =ai xj−i + ξji≥0

さらに，任意の通信路容量を有する任意の通信路に対して，レートレス符号器と復号器の単一のペアを用いてその理論限界性能を達成することが実験から予想されている(x1 , x2 , . . . , x105 )(x1 , x2 , . . . , x105 , . . . , x2×105 )(x1 , x2 , . . . , x105 , . . . , x2×105 , . . . , x3×105 )どこで通信をやめてもその系列の符号化率でシャノン限界を達成することができる．
17 / 21

バースト誤りに対する弱さ
空間結合符号の訂正過程はドミノ倒しのような連鎖反応である
一時的にノイズレベルが高くなり訂正の連鎖反応を止めてしまうことがある
インターリーバを使うとスライディング窓法が使えなくなってしまう

連鎖反応の迂回路を作って連鎖反応が止まらないようにすれば良い

18 / 21バースト誤り訂正のデモ

なぜ中心から復号が始まるのかを説明する

19 / 21

有限計算量でシャノン限界達成へ
シャノン限界を達成するために，MAP 閾値が良いものを探したいBP 閾値＜ MAP 閾値であるから，BP 閾値がよい符号を空間結合すればいいんじゃないか？
(l, r) 符号の MAP 閾値をシャノン限界まで到達させるためには
l → ∞, r → ∞ が必要だが，l, r は訂正に必要な情報ビットあたりの計算量に比例するので大きくしたくない
MacKay-Neal 符号は２つの疎行列 H と G を用いて定義される符号

CMN (H, G) = {y ∈ {0, 1}n |Gx = Hy, x ∈ {0, 1}k }である．MacKay-Neal 符号はルーピー BP 復号では，反復復号の初期状態でアルゴリズムの不動点にいるので，結合しないと全く役に立たない．情報をドーピングして符号化率を落とすことで，動作するように修正して使っていた．
MacKay-Neal 符号の MAP 閾値はシャノン限界と一致していて空間結合 MacKay-Neal 符号はルーピー BP により情報ビットあたり有限の計算量でシャノン限界を達成する事ができる．
20 / 21まとめ

空間結合符号の定義，性能評価，万能性，レートレス符号への応用を紹介した．
ルーピー BP がうまく動かないシステムに対する適用法を紹介した．
紹介しなかった応用例として，圧縮センシング，k-SAT，CDMA マ
ルチユーザ検出，量子通信，ニューラル連想記憶などへの応用がな
されている

21 / 21