ニュース

日本IBM 東京基礎研究所 データの誤り訂正を10倍以上高速化
「リード・ソロモン誤り訂正符号」の並列処理アルゴリズムを開発

日本アイ・ビー・エム株式会社（社長・北城恪太郎） は6日、従来より10倍以上高速化可能な「リード・ソロモン(Reed-Solomon)誤り訂正符号*1」の並列処理ハードウエア・アルゴリズムを、同社東京基礎研究所（神奈川県大和市）で開発したことを発表しました。

インターネットの拡大とe-ビジネスの進展にともない、コンピューターの扱うデータ量とスピードは加速度的に増加していますが、システム・レベルの誤りの発生率を現在と同等に保つためには、コンピュータの扱うデータ量に比例して信頼性を向上させる必要があります。この信頼性を向上させる重要な技術に、高度な数学を駆使してさまざまな要因（伝送経路でのノイズなど）による誤りを自動的に訂正する誤り訂正符号と呼ばれるものがあります。その中でも、今日、多く使われている代表的な誤り訂正符号として、ハミング符号とリードソロモン符号があります。

ハミング符号は、基本的にはビット単位の誤り訂正を行ない、訂正能力は低い（例えば、1ビットの誤りを発見した場合は訂正するが、2ビットの誤りは検出するのみ）ですが、誤り訂正処理が簡単なため並列処理を行うことにより、1Gb/s（1秒間に10億ビット）を大きく超える高速処理が可能です。

それに対し、リード・ソロモン符号は、複数個の連続したビット単位（シンボル）の誤りを訂正*2することが可能で高度な訂正能力を持つ反面、処理に複雑な演算を多用するため並列処理が難しく、例えば、8ビットのデータを100MHzでパイプライン処理*3をしたとしても、 800Mb/s (1秒間に8億ビット）の処理速度しか得られませんでした。

したがって、従来のリード・ソロモン符号の復号方式は、通信分野、またはハードディスクやCD-ROM等の二次記憶装置の分野の製品など、現状では主にデータ処理速度の比較的低い分野で応用されており、今後高速性が要求される分野への応用には限界がありました。

このたび日本アイ・ビー・エム東京基礎研究所で新しく開発されたアルゴリズム*4は、これまでの復号処理速度を10倍以上高速化することにより、高度な誤り訂正能力を持つリード・ソロモン符号の誤り訂正処理をハミング符号と同程度の処理速度で行なうことを実現しました。

具体的には、最先端の量子力学*5で使われている対称関数による表現形式を、リード・ソロモン符号の復号処理にも応用することにより、処理速度の向上と並列処理を行うときの演算回路の数の削減を同時に可能にしたものです。

その結果、処理速度の向上に関して、0.35μmの標準的なASIC技術を使って半導体上に試作された独立した4バイト誤り訂正処理回路では、320ビット幅のデータを45ナノ秒（1ナノ秒は10億分の1秒）で並列処理することにより、現在の処理速度の800Mb/sの10倍近い7Gb/s（1秒間に70億ビット）以上の処理速度を実現しています。さらに、最先端の0.25μm以上の集積度のASIC技術を使い、パイプライン処理機能を付加することにより、このアルゴリズムはさらに1桁程度の処理速度の向上が可能です。

また回路サイズは、大規模並列の誤り訂正処理回路に特化した新たな回路最適化アルゴリズム、ならびに回路共有化手法を用いることにより、さらに縮小されました。 この回路サイズは、ハミング符号の並列処理回路と比較してさほど変わらないおよそ3万ゲートを達成しているため、この回路をマクロとして、CPU、メモリー・コントローラーなどの他の回路 と1チップに組み込むことが容易に可能となります。

その上、外部制御回路やレジスターを使わない組合せ回路であるので、高速処理にもかかわらず消費電力も抑えることができます。その結果、この高度な誤り訂正処理回路を、いままで速度の問題から使用されていなかった記憶装置に適用することにより、DRAMのリフレッシュ電力の大幅な削減を実現し、小型情報機器への応用も期待されます。

今後予想されるデータのさらなる大容量化、処理速度の高速化の観点から、高度でかつ高速な誤り訂正符号の必要性はますます大きくなると思われます。日本アイ・ビー・エム 東京基礎研究所では、こうした次世代の各種情報処理機器において、より信頼性の高いシステムを実現させる基礎技術として、今後もこの分野の研究を進めていく考えです。

なお、この研究成果に関して、1999年10月11日から13日に米国テキサス州・オースティンで行われる「ICCD '99（1999 IEEE International Conference on Computer Design）」および1999年11月1日から3日に同ニューメキシコ州アルバカーキーで行われる「DFT '99（1999 IEEE International Symposiμm on Defect and Fault Tolerance in VLSI systems)」にて、学会発表を行なう予定です。

＜補足説明＞

*1 リード・ソロモン誤り訂正符号
Irving S. ReedとGustave Solomonにより1960年に論文として発表された誤り訂正符号。

*2 ビットの単位（シンボル）の誤り訂正
リード・ソロモン符号は、連続したビットの単位（シンボル）で誤り訂正をするため、1シンボルが8ビットで構成されている場合、最高、1シンボル誤り訂正の場合は8ビット、２シンボル誤り訂正の場合には16ビットもしくは2つの8ビットの連続した誤りまで訂正可能。

*3 パイプライン処理
ある処理過程を複数のステージに分割し、流れ作業的に、それぞれのステージを同時に種々の処理段階にあてることにより、全体の処理能力を高速化する手法で、CPUの処理速度の向上手法として一般的に良く用いられているもの。

*4 新しく開発されたアルゴリズム
今回新しく開発されたアルゴリズムでは、順序回路による繰り返しアルゴリズムではなく、組み合わせ回路のみを使って並列にリード・ソロモン符号の復号処理を行うことによって高速化を実現した。
順序回路による繰り返しアルゴリズムとは、演算回路と中間情報を貯えるレジスターを外部制御回路により繰り返し使用して、問題を解くアルゴリズム。
これに対し、組み合わせ回路による並列処理アルゴリズムとは、演算回路のみを処理すべき順序に並べて、一度に並列に処理するアルゴリズム。
一般に同等の処理を行う場合、前者は回路規模は小さくてすむが、処理速度は遅くなる。一方後者は回路規模は大きくなるが、処理速度は速い。

*5 量子力学
電子等のミクロな粒子の振る舞いを記述する基になっている物理学の1分野。今回の成果は、分数量子ホール効果にも使われている理論枠組みを応用。