A Tutorial on Reed-Solomon Coding for Fault-Torelance in RAID-like System
James S. Plank
Department of Computer Science University of Tennessee, Feb 19, 1999

の部分訳

琉球大学情報工学科　和田　知久

アブストラクト

RAID（Redundant Array of Inexpensive Disks）での複数エラーに対するエラーコレクションにリードソロモン符号が使えることは知られているが、符号化技術はあまり知られていない。符号関係のプロにとっては、リードソロモン符号の符号化は基本的な符号化の方法を拡張したものであるが、符号理論をしらないシステムプログラマにとってはミステリである。
このペーパーはシステムプログラマ向けであり、[私にとってはLSI設計者向きではあるが。(^^;)] 符号化の完全なアルゴリズムとその実装方法を示す。また、このペーパーは読者として、数学や符号理論を知らない人を仮定している。このペーパの目的は、システムプログラマが他の文献の手助けなしに、RAIDのようなシステムに対してリードソロモン符号を実現できるようにするためである。

問題の定義

RS-Raidアルゴリズム

リードソロモン-RAIDアルゴリズムに３つの技術要素がある。１つはVandermonde行列による計算とチェックサムの生成、２つ目はGaussian Eliminationによる不良からのリカバリー、そして３つ目はガロワ体をでの算術計算である。

以下にそれぞれに対して説明をする。

チェックサムの計算

各チェックサムの生成関数を以下のような線形式で定義する。

データ、チェックサムをそれぞれベクトルD、Cと示し、Fiを行列Fであらわすと、

FD=C

なる計算式でチェックサムCが求まる。FとしてVandermonde行列を用いると以下のように変形される。

ここで、任意のひとつのデータ dj が d'j に書き換えられると、チェックサムも同様に書き換えを行う必要がある。これを式で示すと以下のようになる。

不良発生時のデータの再生性

行列AとベクトルEを以下のように定義する。

そうすると、AD=E　が成立し以下の式が得られる。この式の各行はそれぞれ対応する記憶デバイスに対応する式になっている。不良が発生した場合、それに対応する行を消去した式に変形し( A' D = E' )、それより、Dすなわちd1, ..., dnを再計算することができる。ｍ個の不良が発生しても、そのｍ行を消去すると A' はnxn行列となる。FはVandermonde行列であるので、行列Aのｎ行からなるサブセット行列の各行は非従属であり、逆行列が存在するからである。

例

例として、３つのデータデバイスと３つのチェックサムデバイスを考える。したがって、n=3, m=3 である。wとして４を選ぶ。2のw乗 > n+m が成立する。掛算に対してはTable1のlogarithm tableを用いる。

３ｘ３のVandermonde行列Fは以下のようになる。カロア体での乗算で、右下の要素が９でなく５になることに注意が必要である。

FD=C にしたがって、チェックサムを計算する。ここでは例として、D1=3, D2=13, D3=9 を仮定している。実際に計算を行うと以下のようになる。[ガロア体の乗算は設計仕様書のセクション３を参照]

ここで、D2を１３から１に変更すると、D2は（１−１３）すなわち、

１２をチェックサムデバイスに送ることになる。再計算を行うと以下のようになる。

これまでの D, C を用いて、AD=E　を書き直すと、

が得られる。ここで、D2, D3, C3のデバイスが故障したとすると、対応する行を消去すると、以下の式がえられる。

ガウスの消去法で逆行列を計算すると、以下の式が得られる。[ここでもガロア体で、簡単ではない！]

これよりd1, d2, d3 を以下のように再生成することができる。