最適化手法に基づく誤り訂正符号の 復号アルゴリズムについて

第

61

1

123–134 2013 c

［総合報告］

最適化手法に基づく誤り訂正符号の 復号アルゴリズムについて

和田山 正

^†

（受付

2012

6

28

8

28

9

5

要 旨

近年，線形計画法などの連続最適化に基づく誤り訂正符号の復号法が登場し，符号理論研究 者の注目を集めている．本稿では，著者の提案する内点法に基づく

LDPC

Parity-Check

符号の復号問題を凸計画問題として定式化し，バリア関数に基づく主パス追跡内点法により近 似的にその凸計画問題を高速に解く，という考え方に基づいて構成されている．本復号アルゴ リズムは，線形ベクトル通信路の範疇に入る定常無記憶通信路，シンボル間干渉通信路，

MIMO

キーワード： 内点法，凸計画問題，低密度パリティ検査符号．

1.

誤り訂正符号の復号法に最適化の考え方が導入されたのは比較的最近（2002年頃）であり，

その先駆的な仕事として

Feldman

Feldman et al., 2005）が挙げられる． Feldman

Vontobel and Koetter

Koetter and Vontobel

著者のグループでは，近年，凸最適化手法に基づく

LDPC

CDMA

2

本稿では，凸最適化問題に基づく

LDPC

Wadayama

†名古屋工業大学：〒466–8555 名古屋市昭和区御器所町

論文

Wadayama

LDPC

内点法の

LDPC

Vontobel

（2008）による内点法の応用 や

Taghavi et al.

実数空間における最適化問題という視座から受信器における受信処理を統一的に眺めること により，連続最適化に基づく推論計算がコンポーネントベースの受信器アルゴリズム設計に代 わる新しい受信器の構成原理を与える可能性が見えてくる．復号問題に対する連続最適化アプ ローチの通信伝送分野における適用範囲は広く，線形ベクトル通信路の範疇に入る定常無記憶 通信路，シンボル間干渉通信路，MIMO通信路，マルチプルアクセス通信路など様々な通信路 に適用が可能であり，幅広い応用が期待されている．

2.

連続最適化に基づく復号法の原理である，緩和推定問題について解説したのち，本稿の以下 の部分で必要とされる記法・定義などを導入する．

2.1

低密度パリティ検査符号，あるいは

LDPC

R. Gallager

sum-product

LDPC

2

LDPC

2

LDPC

sum-product

適切に設計された

LDPC

sum-product

LDPC

2

F

H

= { h

} (i ∈ [1, m], j ∈ [1, n])

C(H)

(2.1) C(H ) =

{x ∈ F

: H x = 0

}

と定義する．なお，この定義の行列ベクトル積

H x

F

F

{ 0,1 }

1 + 1 = 0

[a, b]

整数の集合

{a, a + 1, . . . , b − 1, b}

n

H

LDPC

に対して検査行列中の列に含まれる

1

2.2 2

送信信号を確率変数

X

Y

S

P

(y|x)

n

X = (X

, X

, . . . , X

)

= (Y

, Y

, . . . , Y

)

S

(2.2) P

(y | x) =

P

(y

| x

)

となる．また定常性より，すべての

i ∈ [1, n]

P

(y

| x

)

符号化通信システムは，符号化器と復号器の組から成っている．符号化器は，送信したいメッ セージを

2

C(H )

y

x ˆ

ブロック誤り率

Pr[x = ˆ x]

最尤推定に基づく復号則である最尤復号則は

(2.3) x ˆ = arg max

x∈C(H)

P

(y | x)

と与えられる．ここで，C(H)に含まれる符号語の個数は，符号長

n

その復号アルゴリズムは指数時間アルゴリズムとなる．この計算量の壁を破るためには，符号 または復号法に何らかの工夫が必要である．

2.3

具体的な例を挙げて，本稿で紹介する復号法の考え方について説明する．

検査行列

H

C(H )

x ∈ C(H)

(0,1)・バ

(+1, − 1)

r

(2.4) r = (1 − 2x) + z

と与えられる．ここで，zは白色ガウス雑音ベクトルであり，1はすべての要素が

1

上述の通信系に対する最尤復号則は，

(2.5) x ˆ = arg min

x∈C(H)

|| r − ( 1 − 2x

) ||

と与えられる．ここで，

x ˆ

一般の

2

n

この最尤推定則に基づく最尤復号問題は，一種の組み合わせ最適化問題と見なすことができ る．元問題の実数緩和問題を考えるというアプローチは，計算量的に困難な組み合わせ最適化

問題に対する近似解法として組み合わせ最適化の分野でしばしば利用される

Schrijver

上記の最尤推定則を緩和して得られる緩和推定則

(2.6) x ˆ = arg min

x∈Conv(C(H))

||r − (1 − 2x

)||

を考えよう．ここで，

Conv(C(H))

(0, 1)

(0, 1)

2

2

2.4

2

C(H )

n

基本多面体は

2

C(H)

C(H )

n

いま，Ai

= { j ∈ [1, n] : h

= 1 }，i ∈ [1, m]

(i ∈ [1, m])

A

(2.7) T

=

{ S ⊂ A

: | S | is odd }

x ∈ R

(2.8) ∀ i ∈ [1, m], ∀ S ∈ T

, 1 +

t∈S

(x

− 1) −

t∈Ai\S

x

≤ 0,

と

(2.9) ∀ j ∈ [1, n], 0 ≤ x

≤ 1

はそれぞれパリティ制約式 とボックス制約式と呼ばれる．

パリティ制約式は，検査行列

H

A

S ⊂ T

= (x

, . . . , x

)

x

=

1, i ∈ S 0, i / ∈ S

と定義する．いま，xを

2

F

Hx = 0

x

h

x

=

j∈A_i

x

=

j∈S

x

+

k∈A_i\S

x

= 1

となるからである．なお，この式の和は，2元体上の和である．一方，今度は，xを実ベクト ルと見なして，パリティ制約式の左辺の量を評価すると

1 +

t∈S

(x

− 1) −

t∈A_i\S

x

= 1

となり，このベクトル

x

2

基本多面体

P (H )

(2.10) P (H)

= { x ∈ R

: x satisfies constraints (2.8) and (2.9) }

と定義される多面体である（Koetter and Vontobel, 2003; Feldman et al., 2005）．基本多面体

P(H )

P

(H)

LDPC

2.5 LP

本節では，

Feldman

LP

LP

2

P

(y

| x

)(i ∈ [1, n])

BIOS

Y

X

i

i

λ = (λ

, λ

, . . . , λ

)

(2.11) λ

= ln

P

(y

|0)

P

(y

|1) , i ∈ [1, n]

と与えられる．Feldmanらにより提案された

LP

ˆ

x = arg min

x∈P(H)

λ

x

として定義される．ここで，ˆ

x

2.6

本稿で紹介する内点復号法の主たる対象となる線形干渉通信路を定義する．

送信者は，2元線形符号

C(H )

x

(2.12) r = V x + b + z,

を受け取る．ここで，

V

n × n

n

これらの

V

b

z ∈ R

V

b

MIMO

上記の線形ベクトル通信路における最尤推定問題を緩和することにより，緩和最尤推定則

(2.13) x ˆ = arg min

x∈P(H)

f(V x + b, r)

が得られる．ここで

f( · , · )

ここで，距離関数

d(·, ·)

例えば，雑音ベクトルが加法的白色ガウス雑音である場合には，この距離関数はユークリッド

2

2

(2.14) x ˆ = arg min

x∈P(H)

||r − (V x + b)||

3.

本節では，内点復号法の考え方と概要について述べる．

3.1

通信への連続最適化アルゴリズムの応用を考える場合に重要になるのが計算速度である．例 えば， 多くの通信系応用分野において

1

以下では，前述の緩和最尤推定則により与えられる

2

LDPC

まず準備として，基本多面体に基づいて次のように対数バリア関数を

B(x) =

−

i∈[1,m]

S⊂Ti

ln

−

1 +

t∈S

(x

− 1) −

t∈Ai\S

x

−

j∈[1,n]

ln [ − ( − x

)] −

j∈[1,n]

ln [ − (x

− 1)]

と定義する．

この対数バリア関数の第

1

2，3

∞

緩和推定則における目的関数

f(V x + b,r)

(3.1) ψ

(x) = tf(V x + b, r) + B (x)

と定義する．ここで，tは正実数のパラメータであり，スケールパラメータと呼ぶ．

内点復号法は，主パス追跡型内点法によりメリット関数

ψ

(x)

（1）tの初期値を設定する．探索初期点を基本多面体の中心点

x = (1/2,1/2, . . . , 1/2)

（2）勾配降下法，またはニュートン法を利用して，ψ^(t)

(x)

（3）探索点に対して，min-sum復号法を適用し，一次推定語を作成する．

（4）t

:= αt

（5）ステップ（2）に戻る．

内点復号法の各ステップは，符号長について線形時間で計算が終了するように設計されている．

以下では，内点復号法の各ステップについて説明する．

3.2

内点復号法のステップ（2）では，与えられたパラメータ

t

Wadayama

勾配法を利用するためには，探索点におけるメリット関数の勾配ベクトルが，ニュートン法 を利用するためには，勾配ベクトルとヘッセ行列の計算が必要となる．

メリット関数の勾配ベクトルは

(3.2) ∇ ψ

(x)

=

∂

∂x

ψ

(x), ∂

∂x

ψ

(x), . . . , ∂

∂x

ψ

(x)

と与えられる．第

k

∂

∂x

ψ

(x) = t ∂

∂x

f(x) + ∂

∂x

B(x)

= t ∂

∂x

f(x) +

i∈[1,m]

S∈T_i

τ

(x) − 1 x

− 1

x

− 1

(3.3) τ

(x)

= I[k ∈ A

\S] − I[k ∈ S]

1 +

(x

− 1) −

x

,

(i ∈ [1, m], S ⊂ [1, n])

I[condition]

I[condition] = 1

パリティ制約に関するバリア関数の偏導関数は

2

m

∇ψ

(x)

w

もし，検査行列の行重みが大きいときには，この部分の計算量が内点復号法全体の計算量を支 配することになる．全体の計算量削減のために，ここでは真の勾配ベクトルを正確に評価する のではなく，その近似値をより少ない計算量で評価するという方策を用いる．

近似勾配ベクトル

g

= (g

, . . . , g

)

(3.4) g

= t ∂

∂x

f(x) +

i∈[1,m]

τ

(x) − 1 x

− 1

x

− 1 , k ∈ [1, n], x ∈ P

(H)

S

(3.5) S

= arg max

S⊂T_i

1 +

l∈S

(x

− 1) −

l∈A_i\S

x

, i ∈ [1, m]

と定義される

T

Wadayama

S

S

w

勾配ベクトルの評価計算量は

O(w

m)

中心点の計算にニュートン法を用いる場合には，勾配ベクトルに加えて，探索点におけるヘッ セ行列の算出が実行時の反復ごとに必要となる．LDPC符号ではヘッセ行列が疎行列になるこ と，近似勾配ベクトルの計算の際に利用した近似計算などを組み合わせることで，近似ヘッセ 行列の高速計算が可能となる．近似ヘッセ行列の詳細は論文

Wadayama

3.3 min-sum

内点復号法の目標は目的関数

f(x)

x ˆ

min-sum

min-sum

な近似更新式に代えて得られる

LDPC

(3.6) α

=

k∈Ai\j

sign(β

)

k∈A

min

| β

|

という形をしている．ここで，c_iは

i

k

c

x

x

c

1

min-sum

B

B

=

{j ∈ [1, m] : h

= 1}, i ∈ [1, n]

と定義される．アルゴリズムの詳細については，例えば，和田山（2010）を参照されたい．

min-sum

いる．min-sum復号法の復号性能は，sum-product復号法の復号性能に若干及ばないが復号中 にメッセージのスケーリングを行うことにより，多くの場合，両者の性能差はほとんど無くな ることが知られている．

緩和推定問題の最小解に十分に収束していない段階でも，min-sum復号法を併用することに より送信符号語を正しく推定できる場合が多くある．そのため，min-sum復号法の利用により 内点復号法の反復処理（ステップ（1）から（4））の回数を大きく減らすことができる．

図

1. min-sum

3.4

内点復号法のステップ（2）において，ニュートン法を利用する場合には，ニュートン方程式

Gd = g

d

d

Wadayama

献

Wadayama

前処理としては，単純なヘッセ行列の対角近似が利用されている．

LDPC

G

4.

本稿では，論文

Wadayama

現在，符号理論の分野では，LDPC符号など疎グラフに基づいて定義される符号を

BP

連続最適化技法に基づく復号手法の考え方は，組み合わせ最適化の緩和解法と共通する部分 が多い．そのため，連続最適化アルゴリズムや組み合わせ最適化などの関連分野の優れた技術 を復号性能向上のために利用できる可能性がある．特に組み合わせ最適化分野で利用されてい る整数計画問題に関する技法は復号性能改善のために重要である．例えば，LP復号法の復号 性能の改善のために，（1）混合整数計画法の利用，（2）制約条件の付加による基本多面体の緊密 化といった工夫が近年提案されてきている．

Draper et al.

LP

BP

LP

整数解（すなわち符号語）が得られる可能性が生じる．2回目の解が再び非整数解の場合，同様 のプロセスを反復する．計算量は通常の

LP

符号語を発見できる可能性が高まることが計算機実験の結果として報告されている．

（2）の制約条件の付加による基本多面体の緊密化アプローチでは，実行可能領域である多面 体に適切な線形制約条件（超平面）を追加することにより多面体緩和の緊密化を行う．緊密化さ れた実行可能領域で最適化を行うことにより，元の場合と比べて質の良い解が得られる可能性 が高まる．

例えば，切除平面法に基づく

LDPC

スを実行する．一方，我々のグループが開発した切除平面法に基づく検査行列改良手法（Miwa

et al., 2009）は，符号の検査行列の行の線形結合として得られる冗長行の生成する切除超平面

著者のグループでは整数頂点を選好するペナルティ関数を利用した非線形最適化手法の検討を 進めている．

本稿で扱った問題は，「情報通信の文脈において，連続最適化技法に基づき信頼性の高い推 論を実現する」という問題であった．この問題は組み合わせ最適化や連続最適化，推論，符号 理論にまたがる問題であり，学際的色彩の濃いものである．情報通信，信号処理，確率推論の 世界における，特にリアルタイム性が要求される用途での連続最適化技法の応用には今後のさ らなる進展の可能性があると考えられ，分野の枠を超えた研究の推進が求められている．

謝  辞

本研究の一部は，科学研究費 基盤

C No. 22560370

参 考 文 献

Boyd, S. and Vandenberghe, L.

2004

. Convex Optimization, Cambridge University Press, New York.

Burshtein, D.

2008

. Iterative approximate linear programming decoding of LDPC codes with linear complexity, Proceedings of IEEE International Symposium on Information Theory, Toronto.

Draper, S. C., Yedidia, J. S. and Wang, Y.

2007

. ML decoding via mixed-integer adaptive linear programming, Proceedings of IEEE International Symposium on Information Theory, Nice.

Feldman, J.

2003

. Decoding error-correcting codes via linear programming, Ph.D. Thesis, Mas- sachusetts Institute of Technology,

Feldman, J., Wainwright, M. J. and Karger, D. R.

2005

. Using linear programming to decode binary linear codes, IEEE Transactions on Information Theory, 51(3), 954–972.

Gallager, R. G.

1963

. Low Density Parity Check Codes, MIT Press, Cambridge, Massachusetts.

伊藤慎吾，和田山正（

2011

. 2

CDMA

A

J94-A (8), 649–656.

Koetter, R. and Vontobel, P. O.

2003

. Graph covers and iterative decoding of finite-length codes, Proceedings of 3rd International Symposium on Turbo Codes and Related Topics, Brest.

Miwa, M., Wadayama, T. and Takumi, I.

2009

. A cutting-plane method based on redundant rows for improving fractional distance, IEEE Journal on Selected Areas in Communications, 27 (6)

1005–1012.

Schrijver, A.

2003

. Combinatorial Optimization: Polyhedra and Efficiency, Springer, Berlin.

Taghavi, M. H., Shokrollahi, A. and Siegel, P. H.

2008

. Efficient implementation of linear program- ming decoding, Forty-Sixth Annual Allerton Conference, Allerton Park & Retreat Center, University of Illinois Monticello, Illinois.

Tanatmis, A., Ruzika, S., Hamacher, H., Punekar, M., Kienle, F. and Wehn, N.

2009

. Valid inequal- ities for binary linear codes, Proceedings of IEEE International Symposium on Information Theory, Seoul.

Vontobel, P. O.

2008

. Interior-point algorithms for linear-programming decoding, Proceedings of Information Theory and Its Applications Workshop, UC San Diego, La Jolla.

Vontobel P. O. and Koetter R.

2006

. Towards low-complexity linear-programming decoding, Pro-

ceedings of 4th International Conference on Turbo Codes and Related Topics, Munich.

Wadayama, T.

2009

. An LP decoding algorithm based on primal path-following interior point method, Proceedings of IEEE International Symposium on Information Theory, Seoul.

Wadayama, T.

2010

. Interior point decoding for linear vector channels based on convex optimiza- tion, IEEE Transactions on Information Theory, 56 (10), 4905–4921.

和田山正（

2010

.

A Review of Decoding Algorithm for LDPC Codes Based on Numerical Optimization Techniques

Tadashi Wadayama

Nagoya Institute of Technology

This paper reviews a decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization according to the reference Wadayama (2010). The decoding algorithm, called interior point decoding, is designed for linear vector channels. The linear vector channels include many practically important channels such as inter-symbol inter- ference channels and partial response channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem called a relaxed MLD problem. The decoding algorithm is based on the primal path-following interior point method with a barrier function. Approximate variations of the gradient descent and the Newton methods are used to solve the convex optimization problem.

Key words: Interior point method, convex optimization, low-density parity-check codes.