Low-Density Parity-Check Code Constructions for Hardware Implementation - waxwing_k @ ウィキ

Abstract

• 階層構造のコード構造のLDPCデコーダを実装するためのハードウェアアーキテクチャを提案
• 完全並列化して実現すると輻輳が軽減される
• 0.13umプロセスで1024bit
  • 完全並列LDPCデコーダは12.5mm^2
  • シリアルデコーダは0.15mm^2

I Introduction

• 高いスループットのシステムではハードウェア化されたLDPCデコーダを使わなくてはいけない
• しかしハードウェアは複雑・面積が大きい・消費電力が多い・限られたスループットになるといった問題がある
• 様々な符号化率やブロックサイズに対応した柔軟なハードウェア実装を目指す

• これまでの研究としては・・・
  • 有限配列上に構成できるように，LDPCのエンコードの単純化
  • デコーダを単純化できるようにデコードのスケジューリングを変更
  • 置換行列をベースにしたハード実装

• 良いBERと低いエラーフロアを実現したコード構成法について研究する
• 様々な柔軟性とスループットについてのいくつかのアーキテクチャについて述べる

II LDPC Decoding

• LDPC符号はN×Mのパリティチェック行列Hで構成される
• Nはブロック長，Mはパリティーチェック数を表す
• LDPC符号は二部グラフで表せる
• 正則行列

• sum-productアルゴリズムは復号に用いられる

1. ビットノードで更新情報を計算し，隣接チェックノードへ送信する
2. チェックノードでビットノードから受け取った情報をもとに更新情報を計算し，隣接ビットノードへ送信する

• LDPCデコーダは二部グラフの表現を実現することでハードウェア実装する
• N個のビットノードのPEとM個のチェックノードのPEが接続された状態で構成される
• この実装の問題点はランダムなLDPC符号で小さな構造になることだ
• このような並列デコーダでは平均配線長がとても長くなり，面積利用が非効率である
• しかし，並列デコーダは高いスループットが低電力で実現できる
• 解決法の1つは，デコーダの内部配線が単純になるように規則正しい構造を持つ符号を作ることだ

III Algebraic Constructions

• 規則正しい構造を持つLDPC符号は[9], [10]で研究されている
• これらの幾何構造は良いBERを持つグラフを使っている
• いくつかの性質はsum-productアルゴリズムによって良い符号特性を達成している

1. 符号を表す二部グラフは長い周囲と最小のサイクルを持たなくてはならない
2. グラフは拡張性を持たなくてはならない
3. 符号語間で大きな最小ハミング距離を持つほうが良い

• LDPC符号の構造を制御する1つの方法は，幾何的にパリティーチェック行列を書くことだ

1. その1つの方法はRamanujanグラフだ．Ramanujanグラフはk正則グラフで最適性を持っている

• 非有限のRamanujanグラフの集合は幾何的に構成されることが良く知られている[11]
• これらの二分グラフのいろいろな変形の性能によると，パリティーチェック行列は実行可能なレートに構成される

• これらのグラフは大きい周囲と良い拡張性をもっているけれども，その結果得られる符号は最小ハミング距離を考えることなく作ることが出来る
• 実際にエラーフロアが低いことがわかる[12]
• しかし，エラーを訂正することができない

• RamanujanグラフK_{13,5}を元に構成されるLDPC符号は符号化率50%で2184bitの符号で，非栗エラーフロアで0.001%のブロック誤り率を構成する
• 同様にK_{17,5}では符号化率50%で4896bitでブロック誤り率10^{-7}を構成する

IV Proposed Construction

• 少ない重みの符号語の問題点を克服したいくつかの符号構成法を紹介する
• 先ほど述べた符号の利点は，「短いサイクル長」「拡張性」「構造化された相互接続」
• デコーダの相互接続の構造はパリティーチェック行列に見ることが出来る
• Ramanujanグラフから得られるLDPC符号は構造化されたパリティーチェックを持つ正則(3,6)LDPCである
• 特にその行列は28×14の補行列に分けられ，その行列は78×78の0行列か，置換行列である
• 上位レベルの行列H^*では，どの列も6個の置換行列と22個の0の補行列を持つ
• 逆に，どの行も3個の置換補行列と11個の0行列を持つ
• これらの特徴はデコーダが階層的に作られるための決まりである

• この構造に加え，幾何的に構成されたRamanujanグラフの集合を元に作られたグラフは良い拡張性を持つ
• さらに，小さいkにおいてランダムに構成されたRamanujan kグラフの確率はより高く，N個のノードをもつRamanujanグラフの確率はN倍大きくなる
• k=8, N>1024のとき，Ramanujanグラフの確率は0.8を超える
• この結果から，ランダムで，Ramanujan基準を満たすより確率で構成されたいずれの大きさの正則k二部グラフで，簡単に二つの集合に分けられるものは符号化率が1/2のLDPCを導く
• 順列行列が，より簡単なルーティングの複雑さをもっているような上下関係の他のレベルに加えるための上位のパリティーチェック行列に分けられることは必要条件である
• パリティーチェック行列の結果から，全部でNのノードを持つランダム2d_v正則二部グラフかつ，1つの二部集合と，どのノードも二つのノードにわけられることは同等である
• 元の2d_v正則二部グラフは小さいd_vのRamanujnグラフとなる高い可能性があるので，グラフは最も大きな最小のサイクル長をもつだろう
• その例はFig.3である
  • 24×12のパリティーチェック行列が6×3の上位レベル行列H^*から構成されている
  • 上位レベルパリティーチェック行列はいずれもランダムな置換補行列から構成されている

• 提案手法で生成された符号の性能を完全ランダム生成符号と比較してある．Fig2.
• どちらも102bitのブロックを用いた正則(4,8)LDPC符号で符号化率は1/2である．
• 提案手法では，上位レベル32×16のパリティーチェック行列からなり，それぞれ32×32の要素がある行列である
• この符号はBERの傾斜がブロックエラー率が10^-6まで下がっている時に違いがないことを表している
• このレベルではエラーフロアはまだ下の方に存在している[12]．しかし，以前の構成法ほど上がってはいない．

V Decoder Architectures

• 良い性能に加え，符号の階層構造はハードウェア実装向きのデコーダにもなる．
• この章では，いくつかのデコーダのアーキテクチャについて解析を行い，どの手法が階層構造の符号に適しているか述べる
• 完全並列アーキテクチャは符号化で述べられた相互結合構造によって実現できるを述べた
• 部分的に直列な二つの異なるアーキテクチャについては符号の構造から作ることが出来る
• 最後に，完全に直列なアーキテクチャについては，符号の特徴の利点によって同様に述べる．

A Parallel Decoder

• 完全並列デコーダの設計の問題は，ルーティングの複雑さのレベルを小さくすること
• これは，長い共通相互結合の数を小さくするようなPEの大きなグループの数の分割といえる
• 一般的には，LDPC符号はランダム性と構造化されていない傾向をもつので異なる問題である
• しかし，提案手法ではPEは分割されたパリティーチェック行列H*によって上下関係にそって分割できる
• どの補行列もチェックノードとビットノードの集合を表す
• そのメッセージはPEの集合に同じように分割されルーティングされる
• この基本構造はデコーダの実装のための構造を与える

B Parallel/Serial Implementations

C Serial Implementation

D Comparison of Architectures

VI Conclusions

References