Comments
Description
Transcript
博士論文審査結果報告書
早稲田大学大学院情報生産システム研究科 博士論文審査結果報告書 論 Ultra-Low with 文 Power High 題 目 LDPC Decoder Parallelism for Communication System 申 請 者 PENG, Xiao 情報生産システム工学専攻 マルチメディアシステム研究 ２０１１年 ７月 Design Wireless 低密度パリティ検査（LDPC）符号は誤り訂正符号(ECC)の１つで、Gallager によって 1962 年に最初に論文が発表された。当時は、連鎖符号が脚光を帯びており、またハードウ ェア化も十分に実現できなかったため、LDPC に関する論文は 30 年間以上注目されなかっ た。1996 年に Mackay が LDPC 符号はシャノンが示した理論限界に近い優れた誤り訂正能 力があることを発表して以来、誤り訂正符号分野で研究が活発となった。 実用的な応用に LDPC 符号を適用するために、高い誤り訂正能力と部分並列性を備えた Quasi-Cyclic LDPC (QC-LDPC) が考案され、多くの無線通信標準方式、例えば Wireless Metropolitan Area Network（WMAN）や WiMAX、Wireless Local Area Network （WLAN） や WiFi、および Wireless Personal Area Network（WPAN）等の ECC として採用されて きた。現実の無線通信システムは、高いスループットと低消費電力という２つの相反する課 題に取り組む必要がある。高いスループットは無線インターネットや高品質マルチメディア サービスを含む様々な次世代移動通信アプリケーションを実現するのに必要であるし、他方、 低消費電力化も携帯電話や携帯端末機器（例えば iPad、キンドル等）にとっては不可欠な 条件となる。つまり、無線通信システムの LDPC デコーダは高いスループット能力と低消 費電力化を実現しなければならない。この目的のためには、収束性の早い復号化アルゴリズ ムと高並列化アーキテクチャの開発が重要な課題となる。 アルゴリズムレベルにおいては、Turbo-Decoding Message-Passing（TDMP）またはレ イ ヤ ー ド と 呼 ば れ る 復 号 ア ル ゴ リ ズ ム が 提 案 さ れ て お り 、 従 来 の Two-Phase Message-Passing（TPMP）またはフラーディングと呼ばれている復号アルゴリズムと比較 し、QC-LDPC 符号に適用して約 2 倍の収束速度を達成したことが Mansour によって報告 された(TVLSI2003)。 TDMP アルゴリズムのハードウェア化に関しては、Parity Check Matrix(PCM)をブロック毎に処理するアーキテクチャが Yang や Xiang より提案され、並 列性を向上させた(ISCAS2007、 VLSI2010)。しかしこれらの方式はデータ依存性を保有 するために、並列性を更に向上させることはできないという課題があった。 本論文では、アルゴリズムとしては TDMP を用い、並列性を向上させるために、新しい アーキテクチャを提案している。先ず、LDPC デコーダ回路でメモリとプロセッシングユニ ト間をつなぐ順列ネットワーク（Permutation Network）に対して、高並列化実現手法を 提案し、ハードウェアの削減と、クロック周波数の増加をさせることを可能としている。ア ーキテクチャとしては、ビットシリアルスケジューリング方式を採用し、全てのブロックを １レイヤーで処理することで Xiang の手法に比べて約２倍の並列化が可能となった。更な る並列化を図るために、１レイヤーを半分に分割し、並列にビット演算することで 6.5 倍の 並列化を図ることが可能となる方法を提案している。 第 1 章 “Introduction”[序論]は、誤り訂正符号に関する理論と技術動向を紹介している。 そして LDPC 符号、QC-LDPC 符号の特性、および LDPC 復号アルゴリズムの特徴を紹介 している。 第 2 章 “Permutation Network of QC-LDPC Decoder”[QC-LDPC デコーダの順列ネット ワーク]では、QC-LDPC デコーダの重要な要素である順列ネットワークの新しいアーキテ クチャを提案している。QC-LDPC 符号の PCM は、可変ノードとチェックノードの間に相 互接続を指定する巡回シフト部分行列で構成される。無線通信システムでは、様々な環境に 適応させるために複数の符号レートと複数の符号の長さを扱うため、PCM は異なるサイズ と異なる要素値からなる行列を扱わねばならない。その結果、LDPC デコーダを再構成可能 なハードウェア回路で組むことが必要で、順列ネットワークに、複数の入力数（IN）とシ フト数（SN）を持つ巡回シフト機能を持たせることが必要となる。一般的には、対数バレ ルシフタ方式が巡回シフトを実現するために使われるが、複数のメッセージを並列にシフト することや様々な入力数に対応するとハードウェア量が増大するという欠点をもつ。ベネス ネットワークに基づく Daesun の方法(TVLSI2010)は、クロスバースイッチを複数のステ ージで構成するネットワークを採用しており、ステージの数が多くなることと、制御信号が ステージ毎に生成されるため、信号伝達で遅延がかかるという課題がある。 本論文では、この課題の解決のために、 （１）新しいバレルシフタ方式と（２）バンヤン ネットワークに基づいた方式を提案している。（１）は２のベキ乗でない入力数も扱える方 式を考案することでハードウェア量を削減している。（２）は、バンヤンネットワークに基 づきステージの数が少なく、高い並列性を持つ順列ネットワークを提案している。提案して いる順列ネットワークは、様々な PCM に対応できることと、信号の遅延も減少できること に特徴がある。WiMAX 標準に適用したところ、レルシフタに基づく Liu の結果（ISCAS2008） と比較して、1 つのメッセージをシフトする方法で 26%のハードウェア量の削減を、２つの メッセージを並列にシフトする方法では 51%のハードウェア量を削減できている。 また WLAN 標準へも適用したところ、70%のハードウェア量の削減が行え、33.3%の信号遅延 を減少させることができている。革新的な順列ネトワークを考案したことは学術的に新規性 があり、実用的にも有用であり、高く評価できる。 第 3 章“Bit-serial Layered Scheduling based QC-LDPC Decoder Architecture”[ビットシリ アルスケジューリング方式] では TDMP アルゴリズムにビットシリアルスケジューリング 手法を導入したアーキテクチャを提案している。WiMAX で定義されている QC-LDPC 符号 は無線通信規格の中で最も複雑な符号であり、6 種類の符号化率と 19 個の符号長からなる 114 のモードを扱わねばならない。提案するアーキテクチャは WiMAX 規格に対応し、高並 列処理を実現するために TDMP アルゴリズムを従来のブロック単位からレイヤー単位のス ケジューリング方式に変更している。技術の主な特徴として 1）レイヤー単位に処理することで、各レイヤー内ではブロックの処理を完全に並列化する ことができ、１つのレイヤー内のすべてのメッセージの計算と更新を同時に行うことができ る。演算ユニットと順列ネットワークはビットストリームの形式で処理する。各メッセージ は 6 ビットデータで表現されており、各レイヤーのクロックサイクル数は 6 となり、反復 操作でのクロック数は、24 から 72 クロックにすることができている。従来の Xiang の手 法（VLSI2010）では 48 から 54 クロックであり、本提案手法は最良な場合は 50%のクロッ ク数削減を行える。 2）PCM の並べ替え処理を導入することにより、低符号化率符号に対して 2 つのレイヤー を同時に処理が可能となり、クロック数は 24 から 48 クロックまでへ削減できている。 3）SRAM の代わりにレジスタを使用することで、バッファや FIFO を必要としなくなり、 SRAM を使用する場合と比べて、必要なメモリ領域を 22%削減している。レジスタを使用 することで、回路の電力消費量の増加が見込まれたが、クロックゲーティング手法を活用で きる回路構造のために、クロックゲーティングをしない回路と比べて、27%の電力削減が可 能となっている。 これらの方法に基づき、WiMAX システム用の QC-LDPC デコーダ LSI チップを試作し ている。このチップは、SMIC の 65nm 低リーク LVT CMOS 技術を使い、チップ面積は 3.36 平方ミリメートルとなり、電源電圧は 1.2V で動作し、10 回反復動作を行う条件で、 110MHz のクロック周波数で、1056Mbps のスループットに達成している。この時の消費 電力は 115mW であり、電力効率は 10.9pJ/bit/iteration である。この設計結果は従来の最 良の Xiang の結果（VLSI2010）と比べ、消費電力が 42.1％、電力効率（消費電力／スルー プット/反復回数）が 63.6%に削減できており、高く評価できる。 第 4 章“Semi-layer Scheduling Algorithm based QC-LDPC Decoder Architecture”[セミレイ ヤースケジューリングアーキテクチャ] では更なる並列化を図るために、TDMP アルゴリ ズムに、１レイヤーを半分に分割し、並列にビット演算する（セミレイヤー方式）に基づい たアーキテクチャを提案している。このアーキテクチャでは、反復操作で 1 つのレイヤーを 処理するために、最大で 2 クロックサイクルで処理が可能である。第３章のビットシリアル アーキテクチャは１つの繰り返しあたり KqхNlayer クロック数（Kq は通常 5 から 8 まで変化 するメッセージの量子化ビット数である）であるが、このアーキテクチャではクロック数は 2хNlayer であり、並列処理をさらに改善している。WiMAX システム向けに実装したところ、 各繰り返しあたりのクロック数は 8 から 16 であった。従来の Xiang による最良の結果 （VLSI2010）と比べて、1.4 倍のハードウェア量であるが、6.5 倍の高い並列性を実現し、 82.4％の電力削減を達成しており、学術的にも実用的にも高く評価できる。 第 5 章“Conclusion”[結論]では、提案法の概要と結論を述べている。 以上、本論文では高スループットと低電力消費量を目指した LDPC 復号器の設計問題に 取り組み、新しいアーキテクチャと回路構成を提案し、学術な貢献のみならず、実用面でも 有効な研究成果であると評価できる。 よって本論文は博士（工学）の学位論文として価値あるものと認める。 ２０１１年 ６月 ２８日 審査員 主 査 早稲田大学教授 工学博士（早稲田大学） 後藤敏 早稲田大学教授 工学博士（京都大学） 木村晋二 早稲田大学准教授 博士（工学）（早稲田大学） 前原 文明 琉球大学教授 工学博士（大阪大学） 知久 和田