博士論文審査結果報告書
論 文 題 目
Research on Low-Complexity Decoding Algorithm and Architecture for Non-Binary LDPC Codes
申 請 者 Yichao LU
情報生産システム工学専攻 マルチメディアシステム研究
2014 年 12 月
現在、高密度大容量ストレージや高速無線通信の急速な発展に伴い、高度な誤り訂正技 術への要求が高まっている。低密度パリティ検査（LDPC: Low-Density Parity-Check）符号 は,誤り訂正符号の１つで、1963 年に Gallager によって発明され、1999 年に Mackay によっ て実用面から再認識された。優れた復号化性能であることと、並列処理が可能な方式である ことから、LDPC 符号は、通信システムに広く使われ始めた。WLAN（IEEE 802.11n）、WiMAX
（IEEE 802.16e）、10GBASE-T（IEEE 802.3an）、WPAN（IEEE 802.15.3c）などの最新の通信 規格に、LDPC 符号は広く採用されている。LDPC 符号は、このように無線通信分野での優位 性が示され、実用化されてきたが、最近ではストレージ製品においても、BCH
(Bose-Chaudhuri-Hocquenghem)、および RS(Reed-Solomon)符号に代わる誤り訂正符号とし て採用され始めた。最新の記憶装置として、マルチレベルセル（MLC: Multi-Level Cell）
型フラッシュメモリがあり、1 つのセルにマルチビットが記録可能でストレージのバイト単 価を大幅に抑えられるが、現時点では書き換えの信頼度または使用寿命が単一レベルセル (SLC: Single Level Cell)型と比較し、大幅に劣っているという問題がある。その理由とし ては、SLC 方式と比較し、MLC は構造的問題から、誤りがより多発するためであり、強力な 誤り訂正符号を採用すれば、構造的欠陥を克服し、ストレージの使用寿命を伸ばすことがで きる。従来のバイナリー（Binary:2 元）LDPC 符号は、通信分野への適用する際に、1 万ビ ット／ブロック以上の長い符号を対象として復号化する場合においては、誤り訂正能力は高 いが、6000 ビット以下の中・短符号に対する訂正能力は低い。最近、中程度の符号長に対 して優れた誤り訂正能力を持つノンバイナリー（Non-Binary：多元）NB-LDPC 符号が注目さ れてきた。Binary LDPC は符号ブロックのシンボルを 0,1 で表現しているが、NB-LDPC は、
シンボルを 0,1,…, 2m -1(GF（2m）)で表現しており、表現に多様性があるために、誤り訂 正能力は向上するが、演算量が増加するという課題がある。
NB-LDPC 符号に対して、2 つのアプローチが取られている。１つは演算量とハードウェ ア実装規模がある程度大きくなるが、あくまでも良い復号性能を目指す方法である。他の 1 つは、復号性能をある程度、犠牲にしても、ハードウェア量を大幅に削減する方法である。
この課題に対して、過去に多くの提案がされてきた。前者の代表的方法として、FFT-QSPA [L.
Barnault, IEEE Information Theory Workshop, 2003]、および Min-Max [V. Savin, ISIT, 2008]アルゴリズムがあるが、復号回路は依然として大きなハードウェア量を必要としてい る。後者の代表的方法として、ワンステップ多数決論理に基づく復号化アルゴリズム（OSMLGD）
[C. Chen, IEEE Trans. on Comm., 2010] があり、有限体と整数演算のみを使用するため、
演算量は大幅に削減されたが、復号化性能が大きく劣化しまうという欠点があった。また、
同論文では OSMLGD の復号化利得を改善するため、多数決論理に基づいて、従来の BP アルゴ リズムより簡単な反復の信頼度伝播を達成できるアルゴリズム（IHRB-MLGD と ISRB-MLGD）
を提案し、OSMLGD と比較し、復号化性能を改良したが、演算量は増加するという結果とな っている。これらのアルゴリズムに基づく NB- LDPC 復号器のアーキテクチャが開発され, ハ ードウェア実装の結果が報告されている（ISRB 復号器[X. Zhang, ASILOMA, 2011], IHRB 復号器[X. Zhang, IEEE Trans. on VLSI, 2011]）。これらは既存の BP アルゴリズムの実装 と比べ、面積削減に優れた結果が得られたが、誤り訂正能力劣化が起こっている。
本論文の目標は、NB-LDPC 復号の強い誤り訂正能力を維持しつつ、復号化の演算量と、
実装ハードウェア量を可能な限り削減することである。そして、具体的な応用として、マル チレベル NAND フラッシュメモリコントローラへ適用し、有効性を示すことである。
本論文では、まずダイナミックチェックメッセージ多数決論理復号化アルゴリズム
（DCM-MLGD）を提案し、演算量が少なく、高い訂正能力を達成している。次に、DCM-MLGD 法に対して、更に演算量の削減を行ったハイブリッド・メッセージパッシング（HMP）アル
ゴリズムを提案し、ハードウェア・アーキテクチャ設計を行い、ハードウェア回路として実 装している。最後に、MLC 型 NAND フラッシュメモリのコントローラを対象として、高速な スループットを達成するために、HMP アルゴリズムに基づく多元準巡回（QCNB-：Quasi Cyclic Non-Binary）LDPC 復号器を提案している。
本論文は、以下の５章で構成されている。
第１章[Introduction（序論）] では、有限代数の基本概念と、NB-LDPC 符号の構成お よび、既存のマルチレベル NAND フラッシュメモリ向け NB-LDPC 復号化手法について紹介し ている。
第2章 [Dynamic Check-Message Majority-Logic Decoding Algorithm for Non-Binary LDPC Codes (NB-LDPC符号に対するダイナミックチェックメッセージ多数決論理復号化アル ゴリズム：DCM-MLGD)]では、NB-LDPC符号に対して新しいアルゴリズム(DCM-MLGD: Dynamic Check-Message Majority-Logic Decoding)を提案している。DCM-MLGDアルゴリズムは、信頼 性に基づく反復多数決論理手法を用いることで、従来のMin-Maxアルゴリズムと比較し、誤 り訂正能力は若干劣るが、大幅に演算量を削減している。パリテイチェック処理において、
提案したアルゴリズムは、チェックノード（検査関数）に信頼度を新規に導入し、チェック ノードとバリアブルノード（受信記号）との間で信頼度を相互に更新する方式を採用してい る。ビット誤り率（BER: Bit Error Rate）の最小化を目的として、多数の数式とパラメー タの中から、最適な数式とパラメータをシミュレーション実験によって求め、チェックノー ドの信頼度の計算方法を提案している。本提案アルゴリズムを、(1) GF（8）上の6000記号 の符号長と2/3の符号化率で、構造が不規則な検査行列を有するNB-LDPC符号と,(2) GF（64）
上の63記号の符号長と1/2の符号化率で、構造が規則的である検査行列を有するNB-LDPC符号 の２種類に対して実験を行った。Min-Maxアルゴリズム[V. Savin, ISIT, 2008]と比べて、
(1)の結果は、BERは0.3dB劣化したが、演算時間で91.9％の削減が行え、(2)の結果は、BER は0.2dBの劣化で、99.6%の演算時間の削減が行えた、一方、ISRB-MLGDアルゴリズム[C. Chen, IEEE Trans. on Comm., 2010]と比べた場合、提案したアルゴリズムは(1)に対して、演算時 間は4.1%増加したが、BERは2.0dB改良した。また(2)に対しては、演算時間は1.0%増加した が、BERは0.3dB改良した。現在までに提案された方法と比べて、演算時間と誤り率の観点か ら、より効率の良い手法を考案したことを高く評価できる。
第 3 章[Hybrid Message Passing Algorithm and an Efficient Decoder Architecture for Decoding Non-Binary LDPC Codes（ハイブリッドメッセージ伝播アルゴリズムと効率 的な NB-LDPC 復号器アーキテクチャ）] では、HMP（Hybrid Message Passing)アルゴリズム とその復号器アーキテクチャを新たに提案している。HMP アルゴリズムは、DCM-MLGD アルゴ リズムをハードウェアに適した計算法に改良することにより、チェックノードの信頼度を更 新する方法を採用している。シミュレーション実験によって求めた最適な減衰係数を利用す ることで、繰り返し操作で累積する信頼度の影響を弱めている。この結果、ISRB アルゴリ ズムで起こる信頼度の飽和問題とクリッピング問題を回避し、誤り訂正能力を向上させ、ハ ードウェア資源を削減できる。GF(64)上の 255 記号の符号長と 2/3 の符号化率を持つ構造が 規則的である巡回 NB-LDPC 符号に対して、シミュレーション実験とアーキテクチャ設計を行 った。シミュレーション結果では、HMP アルゴリズムは第２章で述べた DCM-MLGD と同じ BER を達成し、 ISRB-MLGD アルゴリズムと比べて BER を 0.5dB 改良し、Min-Max アルゴリズムと 比べ、ほぼ同じ BER を達成している。アーキテクチャ設計においては、環状構造をもつバッ
ファを採用し、受信記号のモジュール（VNU：Variable Node Unit）を簡単化することで、
デコーダ回路全体のメモリ量とクリティカルパスを削減している。その結果、提案する復号 器は ISRB 復号器[X. Zhang, ASILOMA, 2011]と比較して、約 24.3％のゲート数と約 12％の メモリ量を削減することができ、Min-Max 復号器[X. Zhang, IEEE Trans. on Circuits and Systems, 2011]と比べて、52%のゲート数と 77.9%のメモリ量を削減しており、従来法を凌 駕するアルゴリズムとアーキテクチャを考案したことは、学術的な面のみならず、実用的な 観点からも高く評価できる。
第 4 章[Non-Binary LDPC Decoder Architecture Designed for MLC NAND Flash Memory
（マルチレベルセル NAND 型フラッシュメモリ向け NB-LDPC 復号器アーキテクチャ）]であ り、MLC 型 NAND フラッシュメモリ向けの NB-LDPC 符号と、小規模化を実現した誤り訂正回 路を提案している。 SLC 型 NAND フラッシュメモリと比べて、MLC 型は多数のビットを格納 できる反面、書き換え操作の信頼性が低下するため、メモリの寿命が短縮される。そのため に、強力な誤り訂正能力もつ NB-LDPC 符号を利用することで、MLC 型フラッシュメモリの信 頼性を向上させ、製品寿命の改善を図ることが期待できる。本提案では、新たな確率モデル を用いて復号器の初期化の精度を向上させることで、シンボル誤り率(SER: Symbol Error Rate)を改良している。そして、１つのセルに 3 ビットを格納する MLC 型フラッシュメモリ に適した GF（8）上の 1240 シンボル記号の符号長と 3/4 の符号化率を持つ NBQC-LDPC 符号 を生成し、HMP アルゴリズムを適用した。Binary LDPC に Min-Sum アルゴリズムを適用した 結果と比較すると、HMP アルゴリズムは SER 値が 2.0×10-3から 1.3×10-4に改良している。
この NBQC-LDPC 符号に対応する回路アーキテクチャを設計したところ、NBQC-LDPC 復号器ア ーキテクチャは、336K ゲート数で、560Mbps のスループットを実現した。ISRB 復号器アー キテクチャ[X. Zhang, IEEE Trans. on VLSI Systems, 2011]と比べて、ゲート数は 64.5％
に削減し、スループットは 69.7％増加することができている。今後、強力な誤り訂正が必 要とされるフラッシュメモリという応用分野を対象として、新アーキテクチャを考案し、回 路設計までを行って従来手法と比べて、良い結果を得ており、非常に高く評価できる。
第 5 章は[Conclusion（結論）]であり、本論文で提案した NB-LDPC 復号化アルゴリズムと アーキテクチャと成果を総括し、今後の課題について述べている。
以上、本論文は NB-LDPC 復号の強い誤り訂正能力を維持しつつ、復号化の演算量を削減 し、実装ハードウェア量を提案し、具体的な応用として、マルチレベル NAND フラッシュメ モリコントローラへ適用し、有効性を示しており、学術的にも実用的も高く評価できる。
よって本論文は博士（工学）の学位論文として価値あるものと認める。
2014 年 11 月 26 日 審査員
主 査 早稲田大学教授 工学博士（早稲田大学） 後藤 敏 早稲田大学教授 博士(工学)（大阪大学） 吉村 猛
早稲田大学教授 工学博士（京都大学） 木村 晋二
早稲田大学教授 博士(工学)（早稲田大学） 前原 文明
