マルチレートに動的対応可能な LDPC 符号の復号器に関する研究

(1)

2007 年度修士論文

マルチレートに動的対応可能な LDPC 符号の復号器に関する研究

指導教員戸川望准教授

早稲田大学大学院理工学研究科情報・ネットワーク専攻

3606U011–1

今井優太

(2)

第 1 _章

序論

(5)

第1章序論

1.1 本論文の背景と意義

近年，インターネット通信速度の目覚しい高速化や放送のデジタル化が促進されたことによりパソコンや家庭用テレビなどの固定端末における大容量コンテンツの利用が加速的に増加している．この傾向は，Youtubeの利用者数の著しい増加や，テレビの地上波放送の完全デジタル化[6]が数年後に迫っている点などで我々の生活の中でも実感できるようになっている．更に，この大容量コンテンツの需要は携帯電話を筆頭とした携帯型無線通信機能付小型端末でも着実に伸びている．

無線通信を行うモバイル端末では固定端末向けのコンテンツ配信と比較して通信速度および通信環境が劣化しやすい傾向がある．一方で有料でサービスを提供する事業者はコンテンツ配信の品質を保証する必要がある．無線環境では特に地理的要因の変化などによって通信中の雑音特性が大きく変化する．このような問題を解決して始めてサービスが成り立つことになる．

従来までも通信品質劣化を防ぐための一手法として，雑音によって生じるデジタル誤りを訂正する誤り訂正符号が用いられてきた．しかしながら，無線環境での大容量コンテンツ配信を満足に行えるような復号特性をもつ誤り訂正符号は用いられていない．そのような中，

従来の誤り訂正符号よりも同条件で高い誤り訂正能力をもつ誤り訂正符号としてLDPC(Low Desity Parity Check)符号が注目を浴びている．

LDPC符号は近年，実用化が大きく期待されている誤り訂正符号である．LDPC符号は 1960年代に発見された. 当時はハードウェア化が困難であったことから忘れ去られていたが．

半導体の微細加工技術が進歩し符号化器や復号器のハードウェア化が現実的になったことから近年，再び注目を浴びている．

そのことから，LDPC符号に関する様々な研究が最近10年間で行われてきた．LDPC符号の性能の限界を求める研究や，実用化を目的をしたハードウェア化に関する研究が特に盛んに行われてきている．これらの研究の成果もあり，一部の規格では実用化が決定している．

一方で，採用が決定したものの符号の復号器をどのように実現するかについては具体的に決定していない．また，無線通信環境を取り扱う際に重要である複数の符号化率（マルチレート）に対応した復号器も現段階で存在しない．

このような背景から，時間，地理的要因によって変動する無線環境に動的に対応可能な LDPC符号の復号器を実現することは研究として大きな意義を持つ．本論文では2種類の LDPC符号に対して上記にあげた通り，変動する雑音環境に対して柔軟に対応可能なLDPC

(6)

第1章序論行列に分割できるように構成する．具体的には，大元のパリティチェック行列を3つの符号化率に応じて2分割，3分割，4分割できる構成にする．この構成をとることによって符号化率が変化した時に行処理演算の引数が変化する．この行処理演算の引数の最小公倍数をとりその数を引数とした行処理演算器を提案する．行処理演算では，最小値を求める演算が存在する．この最小値演算方法をトーナメント方式を用いることによって，複数の符号化率の最小値を求める際にハードウェアリソースを共有できるようになる．このことにより，従来の符号化率ごとにハードウェアを設計する場合と比較してより小さい面積で復号器を実現することが可能になる．

次に，IEEE802.11nで提唱されているパリティチェック行列に対応した動的マルチレート対応可能な復号器を提案する．IEEE802.11nで提唱されている12種類のパリティチェック行列の構成に着目し，マルチレートに用意に対応可能な列処理演算器を提案する．提唱されている4つの符号化率のパリティチェック行列の行ブロック数がそれぞれ，4，6，8，12であることから，最小公倍数の24を列処理演算器を入力数と，符号化率ごとに演算の並列度を変化させる．正則パリティチェック行列で提案した復号器と同様に，列処理演算の主要部である加算をハードウェアを共有させることによって，面積オーバヘッドの少ない列処理演算器を実現する．

(7)

第1章序論

1.2 本論文の概要

本論文では変動する無線環境における通信を想定し，雑音環境の変動に応じて変化する LDPC符号の符号化率に動的に対応可能な復号器を提案する．最初に正則なパリティチェック行列を使用する場合における動的にマルチレートに対応可能な復号器を提案する．次に最近の傾向として実際に採用が検討されている非正則なパリティチェック行列に対応した動的マルチレート対応可能復号器を提案する．それぞれの復号器に関して，ソフトウェア復号シミュレーションおよび，HDL記述を行い論理合成を行った結果を示し考察を行う．また，今後の課題を述べる．

本論文は6章で構成される．

第2章「LDPC符号」では，最初にLDPC符号の発見から現在注目されるまでに至った歴史について説明する．次に本論文で取り扱う誤り訂正符号であるLDPC符号の定義およびその特徴について説明する．更に，LDPC符号の復号性能およびハードウェア化の容易さに対して大きく影響を及ぼすパリティチェック行列の構成法を複数示しそれぞれの特徴を説明する．最後に符号の復号法で最も誤り率が高くなる最大事後確率復号法とその近似アルゴリズ

ムであるSum-Product復号法，Min-Sum復号法について説明し，それぞれの特徴を上げ最

終的に本論文で用いる復号法を選定する．

第3章「既存研究」では，現在までに既に行われてきた他研究について説明する．LDPC 符号の特性に関する研究と，復号器のハードウェア化に関する研究とで分けて説明する．復号器のハードウェア化に関する研究では，正則LDPC符号に関するハードウェア，非正則 LDPC符号に関するハードウェア，実規格に則ったハードウェアの3つに分けて説明する．

第4章「正則LDPC符号列分割形動的マルチレート対応復号器の提案」では，動的にマルチレート対応可能なLDPC符号の列分割形パリティチェック行列を提案し，そのパリティチェック行列に対応する復号器を提案する．符号化率ごとに分割の仕方を変更できるパリティチェック行列を提案し，その分割法に対応可能な行処理演算器を提案する．符号化率が変化すると行処理演算の並列度が変わる．一方で，符号長は符号化率が小さくなると符号長も小さくなるようになっており，単位時間に復号されるビット数はどの符号化率の場合でも一定となる．本文中ではより詳しいマルチレート対応手法について説明する．

また提案するLDPC符号をC言語を用いて復号シミュレーションした結果とVHDLで記述し論理合成を行った結果を示す．この2つの結果を用い，既存の符号化率固定復号器とスループットの比較を行い，符号化率の可変性の有効性を示す．第5章「非正則LDPC符号行

(8)

第1章序論た小面積マルチレート対応列処理演算器を提案する．行ブロック数の最小公倍数をとり列処理演算器の入力数とする．加算演算器を共有することにより，面積オーバヘッドを抑える事を可能にする．また，符号化率が高くなるにつれて列処理演算の並列度が高くなる構造にし，

高復号スループットを実現する．

また提案するLDPC符号をC言語を用いて復号シミュレーションした結果とVHDLで記述し論理合成を行った結果を示す．この2つの結果を用い，既存の復号器との単位面積当たりの復号スループットの評価を行う．その上で，提案復号器の優位性を示す．

第6章「結論」では，本論文全体の内容を総括し，今後の課題と展望を述べる．

(9)

第 2 _章

LDPC _符号

(10)

第2章 LDPC符号

2.1 本章の概要

本章では，本論文でハードウェアを設計する対象アプリケーションとなるLDPC符号について説明する．最初にLDPC符号の定義について説明し，様々な符号の構成法について説明する．次にハードウェア化において重要となる復号法について説明する．

2.2 LDPC 符号の歴史

LDPC符号は1960年代にGallagerによって発案された線形誤り訂正符号の一種である[9]．

発案当時の半導体加工技術ではハードウェア実装が不可能であったことから注目を浴びることなくおよそ30年程もの間忘れさられていた．1990年代後半になり，MacKayやNealらによって再発見され優れた性能を持つと認められると同時に半導体加工技術も伴って実用化が検討されるようになった[13, 14, 15]．

LDPC符号が他の線形符号と異なるのは，繰り返し復号が可能であるという点である．この繰り返し復号を可能にしている理由は，LDPC符号の復号がビット値を推定する際に確率計算を行っているからである．この確率計算を繰り返し行うことによってより推定ビット値信頼度を高めることができる．条件を整えれば，シャノン限界に非常に近いビット誤り率を実現することも証明されている．このことから近年では，無線LANの新規格である IEEE802.11n[10]や欧州のデジタル衛星放送の規格であるDVB-S2[7]などで具体的に採用が決定している．今後，通信技術以外でも次世代ディスク記録媒体などの誤り訂正など幅広い分野での応用も期待されている．

2.3 LDPC 符号の定義

パリティチェック行列

LDPC符号はパリティチェック行列と呼ばれる疎な2元行列によって定義される．Low Density という名が示す通り，パリティチェック行列中の要素’1’の数が要素’0’の数に比べて非常に少ない．このパリティチェック行列をH とし，符号語をC とするとパリティチェック行列と符号語の間には次式が成り立つ．

(11)

第2章 LDPC符号列とは要素’1’の数が行，列により異なるパリティチェック行列のことを指す．レギュラー符号と同様に，非正則行列で定義されるLDPC符号をイレギュラー符号は呼ばれる．本論文では3章で提案する復号器ではレギュラーLDPC符号を取り扱い，4章で提案する復号器は IEEE802.11n内で提唱されている非正則LDPC符号を取り扱う．式(2.1)のパリティチェック行列と符号の関係は，行列が正則，非正則であることに関わらず図2.1に示したようなタナーグラフとよばれる2部グラフで表現することができる．2部グラフの一方のノード群は変数ノードとよばれ他方はチェックノードと呼ばれる．変数ノードは符号中の書くビットに対応しており，チェックノードはパリティチェックビットに対応している．チェックノード群ではパリティチェック行列の各行における行処理演算を行い，変数ノード群では各列における列処理演算を行う．このノード間で尤度情報を演算し交互に値を転送することから，メッセージパッシング型符号としても知られている．

符号化率

符号化率とは1符号語の内の情報ビットが占める割合を表している．符号長をn，パリティ チェックビット数をmとすると，符号化率Rは式(2.2)で表される．

R = (n−m)/n (2.2)

レギュラーLDPC符号に関してはパリティチェック行列中，1行当りの要素’1’の数である行重みをr，1列当りの要素’1’の数である列重みをcと表現すると符号化率は式(2.3)でも求められる．

R = (r−c)/r (2.3)

一般的な誤り訂正符号と同様Rの値が小さくなる程，誤り訂正能力が高くなる．一方で一定の伝送ビットレートにおいては，伝送することが出来る有効ビット数は減少する．

マルチレート

復号器の実現法として，固定復号器とマルチレート対応復号器が存在する．固定復号器とはある特定の符号化率に特化して設計されて復号器のことを指す．一方でマルチレート復号器とは，複数の符号化率の符号を切り替えて復号できる復号器のことを指す．マルチレートに対応する復号器はスイッチング動作などが必用になり，マルチプレプレクサやパーミュータ，

メモリ構造などが固定復号器と比較して複雑な構造になる．

(12)

第2章 LDPC符号

C

1

C

₃

C

4

C

₅

C

2

C

₆

0 1

0 1 0 1 0

0 1 0 1 0 1

1 0 0 0 1 1

6 5 4 3 2 1

=

 







 







•  







 







=

C C C C C C

HC

^T

列処理列処理列処理

列処理演算を行うノード演算を行うノード演算を行うノード演算を行うノード群

群群

群（（（（HHHHののの列数と等価）の列数と等価）列数と等価）列数と等価）

行処理行処理行処理

行処理演算を行うノード演算を行うノード演算を行うノード演算を行うノード群

群群

群（（（H（HHのHののの行数と等価）行数と等価）行数と等価）行数と等価）

図 2.1: パリティチェック行列とタナーグラフの関係

(13)

第2章 LDPC符号

2.4 LDPC 符号のパリティチェック行列構成法

前節で記述した通り，式(2.1)を満たす限りパリティチェック行列はいかなる構成をとっても問題がない．そのため，様々なパリティチェック行列が考案されている．その中でもLDPC 符号の特性を考える上で基本となる復号性能が最も高くなる構成法と，ハードウェア化を意識した構成法を紹介する．

2.4.1 ランダム構成法

LDPC符号を生成する手法には大きく分けて2つ存在する．その内の一方である「ランダム構成法」は文字通りランダム関数を用いる事によってビット誤り率を極力低下させることを目的としたLDCPC符号のパリティチェック行列の構成法である．ランダム構成にもいくつかの異なる手法が存在する．そのランダム構成法の1つを提唱した内の１人がLDPC符号の発見者でもあるGallagerであり，構成法はその名前をとって「ガラガー構成法」とも呼ばれている[9]．この手法では，パリティチェック行列の列重み，行重みを任意で決定し入力パラメータとする．その上でまずパリティチェック行列をいくつかのサブブロックに分割する．図2.2にガラガー構成法の例を示す．この図のように，列重みが3であれば，3つのサブブロックにパリティチェック行列を分割する．次に第1サブブロックを行重み1，列重み6 の行列とし，各行の‘1’は長さが行重み分の一塊のものとする．このことにより，規則的に 1を並べる．

残りのサブブロックに関しては第1サブブロックの列をランダムに交換する事によって決める．第1サブブロックのどの列をとっても含まれる要素‘1’は1つなので列を交換したとしても，最初に決定した行列の列重み，行重みの値が変わってしまう恐れはない．

以上の方法で生成されたLDPC符号は，符号長が長い（数万以上）時に優れた性能を示す．このランダムに列を並び代える手法は，シャノンが通信路符号化定理の証明の中で利用した「ランダム符号化」のアイディアを具現化したものと考えることができる．

2.4.2 Quasi-Cyclic _生成法

一方で確定的構成法では，パリティチェック行列をあるp×p(pは任意の定数）の正方ブロックに分割する手法をとる[17]．各ブロックは単位行列をある値imodpだけ右シフトさせたものとなる．シフト値の集合をSとすると，Sは式(2.4)のように表される．

(14)

第2章 LDPC符号

1 1 1 1 1 1

……

1

1 １

1

1 1

1 １

1 １ 1 １

1 1

1

1 1

……

1 1

1

1 1

1 １ 1 １

1 １

11 1 1

列重み3 行重み6

サブブロック１

サブブロック2

サブブロック3

サブブロック1の列の位置を乱数を使ってランダムに

並べ換える

図 2.2: パリティチェック行列のランダム生成法

るパリティチェック行列の例を示す．図2.3の各部分ブロック中に見られる斜線はパリティチェック行列の要素‘1’を表しており，その他の部分は要素‘0’である．各ブロックの右シフ

ト値i mod pはそれぞれ異なった値となり次の手法で決定される．

• q^c ≡1mod pとなるqを仮定する(cは行重み）．

• ある整数にq mod pを掛ける演算は集合Sをコセットに分割する．

• 整数sを含むコセットは{s，sq，sq²，…，sq^m^s⁻¹}となる．（但し，m_sはsq^m^s ≡s(mod p) となる最小の整数）

この方法を用いると，例えばp=31，c=5の時q=2となり，コセットはC0 ={0}，C1 ={1

，2，4，8，16}，C3 ={3，6，12，24，17}，…，{15，30，29，27，23}のようになる．この内シフト

(15)

第2章 LDPC符号れ1のブロックに分割しそれぞれにメモリを割り当てる事によってメモリへの書き込みや読み込みを支障なく行うことができる．

文献[17]では上記したようなモジュロ演算を用いて右シフト値を決定しているが，一般的には右シフト値はどのような値をとっても良い．ランダムに右シフト値を決定することによってより良い復号性能が得られる可能性もある．本研究でも，この部分ブロックに分割する方法を採用する．

(16)

第2章 LDPC符号

図 2.3: Quasi-Cyclic生成法によるパリティチェック行列

(17)

第2章 LDPC符号

2.5 LDPC 符号の復号法

本節では，LDPC符号の復号法について説明する．最初に誤り訂正符号全般において最も誤り訂正能力が高くなる最大事後確率復号法について説明する．次に最大事後確率復号法の近似アルゴリズムである．Sum-Product復号法とMin-Sum復号法について説明する．これらの復号法は異なった特徴を持ち本論文で提案する復号器にどの復号法が適しているかについても議論する．

2.5.1 最大事後確率（ MAP) 復号法

一般的にどのような通信路符号化の符号であっても最も高い復号性能（低いビット誤り率）

を示すのは，最大事後確率（MAP）復号法と呼ばれる手法である．この手法は，受信信号から最もたしからしいメッセージ・ビット系列を推定する方法である．具体的には，受信語Y から符号語Xに関する事後確率P(X|Y)を計算し，事後確率を最大にする0または1のシンボルをその推定値とする．符号語をx(x₁, x₂,˙˙˙,x_N) と表し，受信語をy,符号語をCと表現すると，符号語のi番目のシンボルが‘0’である確率および‘1’である確率は式(2.5), 式(2.6)で求められる．この確率を式(2.7)のように比較し，より値の大きいシンボルが推定語となる．

P(X_i = 0|Y =y) = ∑

x∈C,xi=0

P(X =x)P(Y =y|X =x)

P(Y =y) (2.5)

P(X_i = 1|Y =y) = ∑

x∈C,xi=1

P(X =x)P(Y =y|X =x)

P(Y =y) (2.6)

ˆ x_i =

{0, P(X_i = 0|Y =y)≥P(X_i = 1|Y =y)

1, P(X_i = 1|Y =y)< P(X_i = 0|Y =y) (2.7) この手法は前に述べた通り，最も高い復号性能を示す復号法である．しかしながら問題となるのが復号を行う際の計算複雑度である．式(2.7)では全ての符号語に関する和を求める部分が存在する．符号長を‘N’とすると，計算複雑度は，2^Nのオーダーとなる．つまり，‘N’

が大きくなると復号時間が膨大になってしまい復号アーキテクチャを実装することを考えるとこの復号法の適用は現実的ではない．それは例えばNに100という数字を代入してみると 2¹⁰⁰という天文学的な時間になることからも明らかである．

そこで，実際にアーキテクチャを実装する際には，計算量がMAP復号法よりも少なく実用的な復号アルゴリズムが用いられる．この場合のより実用的が意味することは，式(2.7)

(18)

第2章 LDPC符号

2.5.2 Sum-Product 復号法

Sum-Product復号法はMAP復号法の近似アルゴリズムである．MAP復号法では，前節

でも記載した通り，受信語yの観測によって得られる事後確率分布の周辺化を行って推定語を求める．この周辺化を行う際の演算が符号長’N’に対して指数関数的に復号時間を増大させる原因となっている．そこで周辺分布を求める際の演算回数を分配則を用いて軽減する．

具体的には，事後確率演算を結合分布を用いた表現で取り扱う．例えば，ある変数Cの観測値cを得たとする．この時の変数Cの観測後の確率変数Aの事後確率分布は式(2.8)で求められる．

P(A|C =c) = P(A, C =c)

P(C=c) (2.8)

この演算結果は，結合分布に含まれる変数以外の変数を結合分布から周辺化によって除外することによって求められる．この演算を直接計算せずに分配則を用いて計算する．除外する変数ごとに演算を分けて行いその積をとる形にすることが可能である．ただしこれは，結合分布が因子分解できる構造である必要がある．

この構造はベイジアンネットワーク上でのメッセージパッシングアルゴリズムの形としてとらえることもできある．各ノードは，隣接するノードから局所積和（因子分解した際のそのノードに対応する積和演算結果）を受け取り，送り先ノード以外の変数を局所化した局所積和を求めて隣接する送り先ノードにメッセージとして送信する．

この考えを更に一般化し，多変数関数の周辺化問題を取り扱う．この多変数関数は，グローバル関数に因子分解することができる．この因子分解を行うのをファクターグラフと呼ばれるノードに各関数ごとにわりあてる．ファクターグラフは関数ノードと変数ノードと呼ばれる2種類のノードを持つ2部グラフで表現される，それぞれのノードでは先に述べた局所積和をそれぞれ，積と和とで分割して行い，メッセージを伝達して演算を行うことによって最終的に各シンボルごとに符号語が求められる．

各ノードで行われる演算が積と和で分けられることから，Sum-Productアルゴリズムと呼ばれる．LDPC符号に対してこのSum-Productアルゴリズムを適用した復号法がSum- Product復号法である．Sum-Product復号法には，確率領域Sum-Product復号法と呼ばれるものと，対数領域Sum-Product復号法の2種類が存在する．この内，ハードウェア化により

(19)

第2章 LDPC符号

Step1[初期化]

H_mn = 1を満たす全ての組(m,n)に対して対数事前比β_mn = 0とする．また反復回数ℓを1 とし，最大繰り返し回数ℓ_maxを設定する．

Step2[行処理]

m = 1,2, ..., M の順にHmn = 1満たす全ての組(m,n)に対して式(2.9)を利用して対数外部値比α_mnを求める．

α_mn =

( ∏

m∈A(m)\n

sign(β_mn′) )

·f

( ∑

n^′∈A(m)\n

f

(|β_mn′|))

(2.9)

sign(x) = 1 if x >0 sign(x) =−1 if x <0

f(x) = lnexp(x) + 1

exp(x)−1 (2.10)

Step3[列処理]

n = 1,2, ...Nの順にH_mn = 1を満たす全ての組(m,n)に対して式(2.11)を用いてbeta_mnを求める．

β_mn= ∑

m^′∈B(n)\m

α_m′n+λ_n (2.11)

λ_n= 2y_n/σ²

Step4[一時推定語の計算]

n ∈[1, N]について ˆ

c_n= 0, if sign(∑

m^′∈B(n)α_m′n+λ_n )

= 1 ˆ

c_n= 1, if sign(∑

m^′∈B(n)α_m′n+λ_n )

=−1 Step5[パリティチェック]

一時推定語が正しく復号されたかどうかのチェックをする．

一時推定語( ˆc₁, ...cˆ_N)が ( ˆc₁, ...cˆ_N)H^T =0，

を満たすとき推定語として出力しアルゴリズムを終了する．

Step6[繰り返し復号回数のカウント]

ℓ < ℓ_maxならばℓをインクリメントしてステップ2以降を繰り返す．

ℓ =ℓ_maxならば一時推定語を推定語として出力しアルゴリズムを終了する．

図 2.4: Sum-Product復号アルゴリズム[25]

(20)

第2章 LDPC符号

2.5.3 Min-Sum 復号法

対数領域Sum-Product復号法は主に実数の加算および関数f(x)の評価で演算が行われる．

f(x)は計算コストが高いため復号アルゴリズムをより実用的にするためにはこのf(x)に変わる別な計算コストの低い関数または，近似法が必要である．

f

( ∑

n^′∈A(m)\n

f

(|β_mn′|))

(2.12)

f

( ∑

n^′∈A(m)\n

f

(|β_mn′|)) wf

(

f(min_n′∈A(m)\n|β_mn′|) )

=min_n′∈A(m)\n|β_mn′|

(2.13)

そこで，関数f(x)(式2.12)の挙動を観測する．f(x)はxの値が小さいものが支配的となる.つまり，従来であれば，全てのxに対してのf(x)の和を求めるところを，最も小さいx の値に近似しても差し支えがほとんど生じないことになる．また，f =f⁻¹であることから，

式(2.13)のような近似が行える．この近似を取り入れた復号法がMin-Sum復号法である. こ

のMin-Sum法はSum-Product法を適用した場合と比べてもビット誤り率はさほど劣化しな

いことが他の研究によって証明されている[11]．Sum-Product法との精度格差を削減するために，xに補正値をかけ，式(2.2)中のf(x)の和に近づける方法がある.この補正値をかけることを「スケーリング」または「ノーマライゼーション」と呼び，Min-Sum復号法の復号精度の向上に一役買っている.

また，ビット誤り率が多少劣化するという犠牲を払ったとしても，計算量を大幅に削減できる事の方が復号アーキテクチャを実装する上では大きなメリットとなる．Min-Sum復号法は加算，最小，正負判定，正負符号の乗算という4種類の簡単な演算のみで実効されていることから，計算コストの大幅削減を実現している．本論文でも最終的にはアーキテクチャ実装を目標としていることから，Min-Sumアルゴリズムを適用することを前提として議論を進める．

Min-Sum復号法のその他の部分を含めた全体アルゴリズムを図2.5に示す．

(21)

第2章 LDPC符号

Step1[初期化]

Hmn = 1を満たす全ての組(m,n)に対して対数事前比βmn = 0とする．また反復回数ℓを1 とし，最大繰り返し回数ℓ_maxを設定する．

Step2[行処理]

m = 1,2, ..., M の順にH_mn = 1満たす全ての組(m,n)に対して式(2.14)を利用して対数外部値比αmnを求める．

α_mn=

( ∏

m∈A(m)\n

sign(β_mn′) )

·min_n′∈A(m)\n|β_mn′| (2.14)

sign(x) = 1 if x >0 sign(x) =−1 if x <0 Step3[列処理]

n = 1,2, ...Nの順にH_mn= 1を満たす全ての組(m,n)に対して式( 2.15)を用いてβ_mnを求める．

β_mn= ∑

m^′∈B(n)\m

α_m′n+λ_n (2.15)

λ_n= 2y_n/σ²

Step4[一時推定語の計算]

n ∈[1, N]について ˆ

c_n= 0, if sign(∑

m^′∈B(n)α_m′n+λ_n )

= 1 ˆ

cn= 1, if sign(∑

m^′∈B(n)αm^′n+λn

)

=−1 Step5[パリティチェック]

一時推定語が正しく復号されたかどうかのチェックをする．

一時推定語( ˆc₁, ...cˆ_N)が ( ˆc₁, ...cˆ_N)H^T =0，

を満たすとき推定語として出力しアルゴリズムを終了する．

Step6[繰り返し復号回数のカウント]

ℓ < ℓmaxならばℓをインクリメントしてステップ2以降を繰り返す．

ℓ =ℓ_maxならば一時推定語を推定語として出力しアルゴリズムを終了する．

図 2.5: Min-Sum復号アルゴリズム[25]

(22)

第2章 LDPC符号

2.6 本章のまとめ

本章では，本論文でハードウェアを設計する対象アプリケーションとなるLDPC符号について説明した．最初にLDPC符号の定義について説明し，復号性能を追究した符号構成法およびハードウェア化を意識した符号構成法について説明した．次に符号の復号において最小の誤り率を実現できる最大事後確率復号法を紹介し，そこから派生したより実用的な復号法

であるSum-Product復号法，Min-Sum復号法について詳しく説明した．その上で，簡素な

ハードウェア化を目標としていることからMin-Sum復号法を本論文では採用することを示した．

(23)

第 3 _章

既存研究

(24)

第3章既存研究

3.1 本章の概要

本章では本論文で提案するLDPC符号の復号器に先だって行われてきたLDPC符号に関する研究のうち本論文が参考にした研究および本論文の提案復号器と比較を行う際に取り上げる研究を取り上げる．

始めにLDPC符号の発見当初から行われてきたLDPC符号の誤り訂正符号としての性能を追究する研究を取り上げる．次にLDPC符号の実用化，特にハードウェア化を研究対象としている研究を取り上げる．ハードウェアの中でも特に復号器を取り扱う研究を取り上げ，

著者らが任意で作成したパリティチェック行列に対応した復号器と，近年の本格的な実用化の傾向を受けた規格の草案で定義されているパリティチェックに対応した復号器を取り上げる．その上で，それらの研究において未だに実現されていない研究課題を見出す．

(25)

第3章既存研究

3.2 符号性能に関する研究

LDPC符号が脚光を再び浴びるようになった当初は，LDPC符号の誤り訂正符号としての特性をより高める研究，もしくは純粋にLDPC符号の限界の調査が研究分野の中心であった．MacKayらは文献[13, 14, 15]においてLDPC符号の様々な特徴について研究を行っている．文献[13]では，LDPC符号がシャノン限界に近い誤り訂正能力を有し，同条件において他の誤り訂正符号よりも高い復号性能を示すことを実験的に証明している．具体的には，

リード・ソロモン符号と呼ばれる畳み込み符号とLDPC符号をガウス雑音環境下でそれぞれ比較しビット誤り率を比較している．その結果，LDPC符号はリード・ソロモン符号よりも高い誤り訂正能力を持つことが実験的に証明されている．その誤り訂正能力はターボ符号とほぼ同等であるが，復号演算の複雑度はLDPC符号の方が低いことからLDPC符号が優れた符号であると結論付けている．文献[14, 15]ではそれぞれパリティチェック行列の構成法についての研究が行われている．文献[14]は複数のイレギュラーLDPC符号のパリティチェック行列を提示し，それぞれの誤り訂正能力を比較している．文献[15]は線形時間内で復号可能で復号性能も高いという意味において「良い」符号を定義でぎるパリティチェック行列を提案している．また，文献[21]においても，誤り訂正能力が高くなるようなパリティチェック行列の構成法が提案されている．

これらの研究は，将来的にハードウェア化を意識したものもあれば，純粋に数学的見解から誤り訂正能力を追求するものまで様々なものが見受けられる．その内のいくつかの手法は，

現在実際にLDPC符号の採用が決定している規格中で提唱されているLDPC符号を構成する際の礎となっている．

(26)

第3章既存研究

3.3 LDPC 符号の復号器に関する研究

本節ではLDPC符号の復号器に関する研究を，レギュラーLDPC符号の復号器，イレギュラーLDPC符号の復号器，そしてイレギュラーの中でもIEEE802.11nに対応した復号器の 3つに分けてそれぞれ取り上げる．

3.3.1 レギュラー LDPC 符号の復号器に関する研究

レギュラーLDPC符号を取り扱う研究としては，文献[1, 11, 17, 22, 23, 27]が見られる．

文献[17]では，正則LDPC符号の復号器の低消費電力化をテーマとしている．LDPC符号の復号器はメモリをはじめとしたハードウェアコストが大きくなる傾向にある．一方でLDPC 符号の復号器は，携帯電話などの電池稼動携帯小型機器への搭載が期待されている．そこで，

消費電力を小さく抑えるようなハードウェアアーキテクチャが提案されている．文献[23]では，効率的な復号アルゴリズムを導入した復号器を実現している．LDPC符号の復号アルゴリズムでは行処理をパリティチェック中の全ての行について行い，その後列処理を開始する．

文献[23]は，行処理演算のメッセージ更新がおこなれると同時にその更新位置に対応した列処理を行うように工夫をすることによって復号の効率化を図っている．

Karkootiらが[11]で実装した復号器は静的に再構成可能なアーキテクチャとなっている．

この回路はFPGAで実装しており，そのことにより再構成が可能になっている．

符号長をNとすると，N = 6×2^θの範囲で再構成が可能となっている．Nの上限値は実装するFPGAの仕様によって決まることになる．符号長は可変であるが，符号化率は0.5と固定されている．この研究では，符号長が長い方がより低いビット誤り率を実現できることも証明している．つまり，復号を行うアプリケーションに応じて符号長は変化するが，極力大きな符号長を選べば良い復号性能が引き出せる．

しかしこの研究で問題となるのが，再構成時間である．再構成は静的に行われる為，再構成回路情報は外部メモリなどからロードする必要が生じる．その為再構成には最短でもµs オーダの時間がかかる．また，再構成時には一度電源を落とす必要があるため，再構成を行う場合は，現在復号を行っているアプリケーションが完全に動作を終了してから行う必要がある．つまり，環境変動が頻繁に起きる状況での再構成には向いていない．この，静的再構

(27)

第3章既存研究する際のアイディアを応用する．

3.3.2 _{イレギュラー} LDPC 符号の復号器に関する研究

イレギュラーLDPC符号に関する研究は文献[2, 3, 26]などが見られる．文献[2]は，ステップ幅が一定ではない量子化を施すことにより2種類の著者が提案する符号において，復号器の誤り訂正能力が2倍精度浮動小数点演算を行った場合と比較しても0.1dBの劣化で抑えられるように設計されている．文献[3] 文献[26]では著者らが構成した3種類の符号化率に対応した復号器が提案されている．その内の1つは符号化率1/2のイレギュラーLDPC符号であり，残りの2つはそれぞれ符号化率が5/8, 7/8のレギュラーLDPC符号である．チェックノードユニット（行処理演算器に相当する演算器）を工夫することにより，マルチレート対応可能なアーキテクチャが可能になると記載されている．しかしながら，チェックノードユニットの構造は明記されているがどのように演算を行うかについては明記されていない．また，変数ノードユニットとメモリブロックの間にマルチレートに対応するためのルータを挟むと記載されているがどのようなルータの仕様が記載されていない．

3.3.3 IEEE802.11n を意識した LDPC 符号の復号器に関する研究

さらにより最近では，次世代の無線通信の規格であるIEEE802.11n[10]にLDPC符号が採用されることが決まったことから，規格に準拠するような形で復号器を設計する研究も行われるようになっている．文献[8, 12]ではそれぞれ，異なるアプローチでIEEE802.11nに規格に準拠したLDPC符号の復号器を提案している．

文献[8]では，異なる符号化率を実現する際にパリティチェック行列の行を足し合わせることによって実現している．最小値探索や，符号演算はシリアル処理を行っている．行処理演算器において，ベースとなる符号化率に対してあらかじめ最小値探索回路と符号演算回路を用意し，異なる符号化率においては行の足し合わせに対処するための付加回路を設け演算結果を元の演算回路に反映させることによってマルチレートに対応している．また，列処理演算器では，列重みの変化に対応するために可変長バッファを用意し，異なる符号化率における列処理演算のシリアルに行うことを可能にしている．

文献[12]では，サブブロックに対して全並列で演算を行うIEEE802.11nに対応したLDPC 符号の復号器を設計している．異なる符号長に対応するために，事後確率比値をメモリに書き込む際にパーミュータを介するように設計している．これは，符号化率の変化によって生

(28)

第3章既存研究

3.4 本章のまとめ

本章では，LDPC符号に関する研究を符号理論的見地，ハードウェア化の見地に分類して紹介した．

ハードウェア化に関する研究は更に正則LDPC符号に関する研究，非正則LDPC符号に関する研究，実用規格で提唱されたLDPC符号に関する研究の3つに分けて紹介した．

正則LDPC符号に関する研究では，符号化率固定の復号器が数多く提案されている．一方で，本論文が着目する雑音変動が発生しやすい無線通信環境を想定した研究は存在しない．

環境変動が頻繁に発生しても高速無線通信を実現するためには，高い復号スループットと同時に高い誤り訂正能力も満たさなければならない．このことから，環境変動に応じて，最適な符号化率を選択できるようなLDPC符号の復号器が必要である．本論文の4章では動的にマルチレートに対応可能なLDPC符号の復号器を提案する．

一方でIEEE802.11nに代表されるように，LDPC符号は研究の段階から実用の段階へと

移行しつつある．IEEE802.11nで提唱されるLDPC符号を意識した研究も紹介した．実際に

IEEE802.11nが導入される時に想定されている実製品としては，iPodなどに代表されるよう

な小型デジタル機器が想定される．このような機器に導入するには，復号器の高い復号スループット，誤り訂正能力に付け加えて，小面積化ということも求めらる．しかし残念ながら，現在までにそのような研究はなされてきていない．そこで本論文の第5章では(1)IEEE802.11n に定められたイレギュラーパリティチェック行列を用い，(2)無線環境の変動に対して符号化率を変更することができ，(3)携帯電話や音楽プレーヤなどの小型携帯無線機器にも搭載可能で小面積である，動的マルチレート対応可能な復号器を提案する．

(29)

第 4 _章

正則 LDPC _{符号列分割形}

動的マルチレート対応復号器の提案

(30)

第4章正則LDPC符号列分割形動的マルチレート対応復号器の提案

4.1 本章の概要

本章では，正則LDPC符号を対象とした，動的マルチレート対応可能な復号器の提案を行う．最初に，マルチレート対応可能を実現するパリティチェック行列の構成を提案する．次に提案したパリティチェック行列に対応する行処理演算器の構成を提案し，マルチレートにどのように対応するかを詳しく説明する．最後に提案行処理演算器を含んだ復号器全体の構成および仕様を説明する．

(31)

4.2 提案正則パリティチェック行列

ブロック分割型パリティチェック行列

LDPC符号の復号をハードウェアで実装する場合に有効なパリティチェック行列の構造としては2.4.2項でも取り上げたQuasi-Cyclic構成法が存在する．この手法は文献[11, 17, 23]でも用いられている．パリティチェック行列は正則行列を対象としており，wr×wc個の部分ブロックに分割される．このブロックは任意の整数kを一辺とする正方行列である．この時正方行列は単位行列，または単位行列の要素を任意整数値rだけ右シフトした行列である．この手法を用いると各部分ブロックで同時に行われる演算数は1回となる．そのことから，この部分ブロックにつき一つのメモリバンクを割り当てれば復号時の演算結果を効率的に読み書きすることが可能になる．

このようなパリティチェック行列の生成手法を採用すると，符号の符号化率は部分ブロック数によって決まることになる．例えば，パリティチェック行列をw_r個の列ブロックで構成されていると見ると，列ブロック数を変化させればそのパリティチェック行列によって定義される符号の符号化率が変化することになる．この特徴を活かして提案手法では，図4.1に示すようなパリティチェック行列を生成し用いる．このパリティチェック行列は3行×24列の部分ブロックで一つの大きなパリティチェック行列を構成している．

この大きなパリティチェック行列を符号化率に応じて図4.1に表した通り等分割する．本論文では，符号化率は0.5, 0.625, 0.75を用いそれぞれの場合で大きなパリティチェック行列を4分割，3分割，2分割している．例えば，符号化率が0.5の時は，列ブロック数が6のパリティチェック行列が4つ独立して存在することになる．つまり，復号を行う際には4つの符号を並列的に復号が可能である．同様にして，符号化率が0.625の時は，3つの異なるパリティチェック行列としてみなすことができ，0.75の時は2つの異なるパリティチェック行列とみなすことができる．それぞれの符号化率において分割を行う大元のパリティチェック行列は不変であるため，分割が行われたとしても要素’1’の位置は固定である．そのためハードウェアで復号を行う際にはどこで分割を行うかという事だけを意識すれば良い．

この分割を行う意味は，前章でも述べた通り変動する雑音環境に対して符号化率を柔軟に変化させる事によって対応させる為である．通信環境のS/N比が劣悪な時は符号化率の低いパリティチェック行列の構成をとり，逆にS/N比が良好な場合には符号化率を高めることによって復号スループットを高めることが可能になるという考えに基づいた提案である．

(32)

R=0.75

R=0.5 R=0.625

図 4.1: 提案するパリティチェック行列の分割法

(33)

4.3 列分割形動的マルチレート対応可能な復号器

本節では，マルチレートに対応するための手法および，その手法を具体的にハードウェアで実現する際の構成法を提案する．

4.3.1 復号器の構成

提案する復号器の特有の特徴を説明する前に，復号器の全体仕様を説明する．主な仕様を表したものを表4.1に示す．

また以上の仕様を踏まえた上での復号器の復号ステップを図4.4に示す．復号器は，図4.4 に示された状態を一つのモジュールとし，それぞれにコントローラを加えたもので構成した．

具体的に列挙すると次のようになる．

• 復号器全体制御モジュール

• 入力制御モジュール

• 出力制御モジュール

• 行処理演算および制御モジュール

• 列処理演算および制御モジュール

• パリティ検査および制御モジュール

これらのモジュールによって構成される復号器の全体構造を図4.2に示す．行処理演算器および，列処理演算器は並列度および行ブロック数・列ブロック数に応じて複数用意しそれぞれ演算器群を構成する．またメモリも同様にして群を構成し，列処理演算・行処理演算時に各演算器群へメッセージを供給し，演算結果を保存する．復号器全体モジュールは復号が正しく行われるように各制御モジュールに信号を伝達する．以降，各モジュールについてより詳しく機能を説明する．

復号器全体制御および各演算器制御モジュール

復号器全体制御モジュールは入出力・および行処理・列処理・パリティチェック演算器の制御モジュールに図4.4に基づいて，演算の開始および終了を伝達する役割を果たす．演算開始信号を制御モジュールに伝達し，そのモジュールから終了信号がかえってくるのを待つ．その間，現在のステート以外に相当する制御モジュールには待機信号を送信しておく．現ステートに該当する制御モジュールから終了信号を受けると，次ステートに相当する制御モジュールに対して演算開始信号を送信し，それまでの制御モジュールには待機信号を送信する．各

(34)

LDPC DECODER TOP

CONTROLER Ctrl. Sig.

Data Sig.

Parity Check Operational

Unit

Parity Check Operational

Unit

CTRL Column Operational

Unit

Column Operational

Unit

Column Operational Column Unit

Operational Unit

Column Operational

Unit

Column Operational

Unit Column

Operational Unit

Column Operational

Unit

Column Operational

Unit

Memory Bank Memory

Bank Memory

Bank

Memory Bank

Memory Bank Memory

Bank Memory

Bank

Memory Bank

Memory Bank Memory

Bank Memory

Bank

Memory Bank CTRL

Row Operational

Unit

Row Operational

Unit

Row Operational Row Unit

Operational Unit

Row Operational

Unit

Row Operational

Unit CTRL

Row Operational

Unit

Row Operational

Unit

Row Operational

Unit

Input CTRL Output CTRL

図 4.2: 提案復号器の全体構造

して，演算終了信号を発行する．また，全体制御信号から待機信号を受けている間は，演算器やメモリ対する信号をすべて無効にする．

行処理演算器

行処理演算器については，前節に提案している．復号器全体が１ブロックあたり並列度4になるよう設計している．提案するパリティチェック行列は，行ブロック数が3である．このことから，12個の行処理演算器によって演算器群を構成する．

列処理演算器

列処理演算器は，ある列に着目した時に各行ブロックの要素’1’に対応したメッセージおよ

(35)

+

j

q

λ

) ( i

₁

j

_q

α β ( i

1

j

q

)

) ( i

2

j

q

β

) ( i

₃

j

_q

β

+

) +

( i

₃

j

_q

α

+ +

) ( i

₂

j

_q

α

j

q

x ˆ

図 4.3: 列処理演算器パリティチェック演算器

パリティチェック演算器は，仮復号語が正しく復号されたかどうかを判定する回路である．

符号化率に応じて仮復号語を6値，8値または12値のグループに分け，パリティチェック行列の各行中の要素‘1’に対応する仮復号値の排他的論理和をとる．すべての行に対して，演算を施しどの結果も0になった時，符号が正しく復号されたとみなしその符号の復号が終了信号をパリティチェック演算制御器に返す．排他的論理和が途中のいずれかの行にて‘1’を返す時には，復号継続信号を制御器に返す．

これらのモジュールの復号アルゴリズムに合わせた復号過程を表す状態遷移図を図4.4に示す．提案復号器では各行ブロックおよび列ブロックあたりの演算器並列度を‘4’と定めた．

そのため行処理演算および列処理演算は1回の繰り返し復号回においてそれぞれ256/4 = 64 回演算が行われることになる．図4.4から6144ビット分の復号を行うのにかかるクロックサイクル数は3712サイクルとなる．

(36)

Inp Inp Inp Inputututut

RR RRowowowow Operation OperationOperation Operation

Column Column Column Column Operation Operation Operation Operation P

P P

Parity Checkarity Checkarity Checkarity Check OutpOutp

OutpOutputututut

No. of No. of No. of

No. of Iterations of Iterations of Iterations of Iterations of ddd

decoding ＜8ecoding ＜8ecoding ＜8ecoding ＜8

＆＆

＆＆ No. o No. o No. o

No. of iterations off iterations off iterations off iterations of Column ColumnColumn Column O

OO

Operation=64peration=64peration=64peration=64 S S S

Signal telling the beginningignal telling the beginningignal telling the beginningignal telling the beginning of Row

of Row of Row

of Row operation= 1 operation= 1 operation= 1 operation= 1 Mov

Mov Mov

Move on to nexte on to nexte on to nexte on to next input code input codeinput code input code

Row Row Row

Row Operation Operation Operation Operation IteIteIte

Iterations No.=64rations No.=64rations No.=64rations No.=64 Row

RowRow

Row Operation Operation Operation Operation Ite

IteIte

Iterations No.＜64rations No.＜64rations No.＜64rations No.＜64 Wa

Wa Wa

Waiting for inputiting for inputiting for inputiting for input d

dd

data to comeata to comeata to comeata to come

No. of No. of No. of

No. of Iterations of Iterations of Iterations of Iterations of dd

ddecoding＝8ecoding＝8ecoding＝8ecoding＝8

＆＆

＆＆ Col Col Col

Col umn Operationumn Operationumn Operationumn Operation Ite

IteIte

Iterations No.=64rations No.=64rations No.=64rations No.=64 No. o

No. o No. o

No. of iterations off iterations off iterations off iterations of Pa

Pa Pa

Parity Check ＜64rity Check ＜64rity Check ＜64rity Check ＜64 No. o

No. o No. o

No. of iterations off iterations off iterations off iterations of PaPa

PaParity Check =64rity Check =64rity Check =64rity Check =64

ColCol

ColCol umn Operationumn Operationumn Operationumn Operation IteIte

IteIterations No.<64rations No.<64rations No.<64rations No.<64

図 4.4: 提案復号器の復号状態遷移図

表 4.1: 提案復号器の仕様

項目名具体名・数

復号アルゴリズム Min-Sum法復号繰り返し回数 8回固定 1シンボル当たりの量子化ビット数 6ビット

部分ブロック一辺k 256

(37)

絶対値演算

1stMin 2ndMin 演算正負符号演算

符号最小値マージ部

1 1 1

6

符号化率信号線

6

CFU

1 j in

βm

2 j in

βm

j3 in

βm

R

j1 in

αm

2 j in

αm

j3 in

αm

図 4.5: 設計したCFU(模式図)

4.3.2 _{行処理演算器の構成}

前節で説明したパリティチェック行列の構造を採用し，符号化率を変動させることによって影響を受ける箇所は以下の通りである．

• 行処理演算時の演算対象引数

• パリティチェック時の推定語と検査行列の掛け合わせ方法行処理演算ユニット

行処理ユニットまたはCFU（Check Functional Unit)は式(2.14)の演算を行う．提案する復

号器のCFUは式(2.14)の正負符号演算部分と最小値探索部分をそれぞれ異なるエンティティ

で設計し双方の演算結果を掛け合わせることによって式中のα_mnを求めることとした．設計したCFU回路の模式図を図4.5に示す．図では見易さを重視するため入力数および出力数が3値となっているが実際には大元のパリティチェック行列の列ブロック数に相当する24値が入出力数である．

正負符号演算部

提案する復号器では，符号化率の変動応じて正負符号演算および，最小値探索演算の行いかたが変化する．正負符号演算では符号化率に応じて掛けあわせる符号の数を変化させる．

例えば，符号化率が0.5の時は24値を6つずつ4組に分けそれぞれの組で，式(2.14)中のプ

マルチレートに動的対応可能な LDPC 符号の復号器に関する研究

2007 年度 修士論文