トップページ･ Imonyとは

PAR2の計算方法

分かりやすくプログラムを書いているところがないので資料程度に書いておきます。

はじめに

PAR2はn個のデータとm個のチェックサムを作り、それらのn+m個のブロックの内n個見つかったとすれば、復元できるという画期的な方法をさします。ここではプログラムに組み込むための資料ですので、証明は省かせていただきます。

この資料について

James S. Plankによる"A Tutorial on Reed-Solomon Coding for Fault-Torelance in RAID-like Systems"を参考に作成しました。また一部日本語訳も大いに参考になりましたのでこの場をかりて礼をさせていただきます。PAR2内部での計算方法を知るために有限体という項目を作りました。有限体をわかった上でPAR2の計算方法の項目へ進むことをオススメします。

有限体

有限体とは

代数学において、有限体（ゆうげんたい）とは、有限個の元からなる体、すなわち四則演算が定義され閉じている有限集合のことをさします。主に計算機関連の分野においては、ガロア体 (Galois field) とも呼びます。有限体の位数はある素数ρのべきであり、このときその標数はρとなります。四則演算が閉じていることにより、割り算の結果が分数になることや、掛け算の結果がとても大きな数値になること、はありません。プログラミングでは利便性の高い2のべきを使います。このことをGF(2^w)と書くこともあります。wに関しては1Byteが8Bitであるのでその約数・倍数である4、8、16が使われます。32に関しては大きくなりすぎているために現状ではほとんど使われていません。
参考: フリー百科事典『ウィキペディア（Wikipedia）』

有限体の計算

有限体の初期化

まずは定数の設定から始めます。PRIME_POLYは初期化のためによく考えられた数値と思ってください。



// 8Bitの場合
#define PAR2_BIT 8
#define PAR2_PRIME_POLY 285
#define PAR2_COUNT (1 << PAR2_BIT)
#define PAR2_MAX (PAR2_COUNT - 1)

// 4Bitの場合
#define PAR2_BIT 4
#define PAR2_PRIME_POLY 19
#define PAR2_COUNT (1 << PAR2_BIT)
#define PAR2_MAX (PAR2_COUNT - 1)

// 16Bitの場合
#define PAR2_BIT 16
#define PAR2_PRIME_POLY 69643
#define PAR2_COUNT (1 << PAR2_BIT)
#define PAR2_MAX (PAR2_COUNT - 1)

以上を定義し、計算用の配列を作成します



int gf[PAR2_COUNT], gfi[PAR2_COUNT];

for (i = 0, j = 1; i < PAR2_MAX; i++) {
    gf[j] = i; gfi[i] = j;
    if (PAR2_MAX < (j <<= 1)) j ^= PAR2_PRIME_POLY;
}

有限体の足し算引き算

どちらもプログラミング用語で言われている排他的論理和を使用します。BASIC系の言語であれば"XOR"で、C系の言語であれば"^"で計算することができます。



int par2_add(int a, int b) {
    return a ^ b;
}

有限体の割り算掛け算

一旦、両方の対応する数を表より算出し、割り算は数を減らし、掛け算は足します。理屈がわからなくてもプログラムできますのであまり深く考えない方が良いかもしれません。



// PAR2用掛け算
int par2_mult(int a, int b) {
    int c;
    if (a == 0 || b == 0) return 0;
    if ((c = gf[a] + gf[b]) < PAR2_MAX) return gfi[c];
    return gfi[c - PAR2_MAX];
}

// PAR2用割り算(b=0は本来あってはならない)
int par2_div(int a, int b) {
    int c;
    if (a == 0) return 0; if (b == 0) return -1;
    if (0 <= (c = gf[a] - gf[b])) return gfi[c];
    return gfi[c + PAR2_MAX];
}

PAR2プログラミング

ここではImonyで使う8BITのPAR2で説明します。分かりやすくするために元データが4つにし、パリティを4つ生成します。元データは(D1 => 10, D2 => 200, D3 => 55, D4 => 11)とします。

パリティの生成

パリティ行列Pは行列F*データ行列Dによって求められます。行列Fはチェックサム行列が互いに素であるように作られる必要があり、また受け取り元でも同一の行列を生成できる必要があるので、生成方法はJames S. Plankが指定している方法に固定します。

行列F =

1⁰	2⁰	3⁰	4⁰
1¹	2¹	3¹	4¹
1²	2²	3²	4²
1³	2³	3³	4³

1	1	1	1
1	2	3	4
1	4	5	16
1	8	15	64

ここで3の二乗が5になっているのは計算が有機体で行われているからです。これよりパリティ行列Pは行列F*データ行列Dによって

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1
1	1	1	1
1	2	3	4
1	4	5	16
1	8	15	64

で求まるので代入して

P =

1	1	1	1
1	2	3	4
1	4	5	16
1	8	15	64

200

254

242

222

と計算され(P1 => 254, P2 => 242, P3 => 86, P4 => 222)とパリティが求まります。

復元

この時、D1,D3,D4,P1を取得できなかった―(D2 => 200, P2 => 242, P3 => 86, P4 => 222)の4つが見つかったとします。つまりこれは行列で言うと、

0	1	0	0
1	2	3	4
1	4	5	16
1	8	15	64

これの逆行列をガウスの消去法で求めます。この時、データを別の所に置くと0で割ることになり機械的に計算することができなくなるので、データはもとの番号に置くことに注意してください。つまり

1	2	3	4
0	1	0	0
1	4	5	16
1	8	15	64

ということになります。この時の左の行列を変換行列Aと名づけます。変換行列Aは最初に正則行列になるように生成しているので必ず逆行列が存在します。ここで変換行列Aの逆行列を逆変換行列Xとします。ここではガウスの消去法と呼ばれる方法を使います。まず(A|E)を生成します。

1	2	3	4	1	0	0	0
0	1	0	0	0	1	0	0
1	4	5	16	0	0	1	0
1	8	15	64	0	0	0	1

ここからL3,L4の一番左を消去する(0にする)ためにL1をそれぞれに足します。

1	2	3	4	1	0	0	0
0	1	0	0	0	1	0	0
0	6	6	20	1	0	1	0
0	10	12	68	1	0	0	1

L3 + L1

L4 + L1

ここからL1,L3,L4の左から2番目を消去する(0にする)ためにL2を適度にかけてそれぞれに足します。

1	0	3	4	1	2	0	0
0	1	0	0	0	1	0	0
0	0	6	20	1	6	1	0
0	0	12	68	1	10	0	1

L1 + 2 * L2

L3 + 6 * L2

L4 + 10 * L2

L3の左から3番目が1になっていないので6で割ります。

1	0	3	4	1	2	0	0
0	1	0	0	0	1	0	0
0	0	1	6	122	1	122	0
0	0	12	68	1	10	0	1

L3 / 6

ここからL1,L4の左から3番目を消去する(0にする)ためにL3を適度にかけてそれぞれに足します。

1	0	0	14	143	1	142	0
0	1	0	0	0	1	0	0
0	0	1	6	122	1	122	0
0	0	0	108	3	6	2	1

L1 + 3 * L3

L4 + 12 * L3

L4の左から4番目が1になっていないので108で割ります。

1	0	0	14	143	1	142	0
0	1	0	0	0	1	0	0
0	0	1	6	122	1	122	0
0	0	0	1	96	192	64	32

L4 / 108

ここからL1,L3の左から4番目を消去する(0にする)ためにL4を適度にかけてそれぞれに足します。

1	0	0	0	245	245	41	221
0	1	0	0	0	1	0	0
0	0	1	0	39	187	231	192
0	0	0	1	96	192	64	32

L1 + 14 * L4

L3 + 6 * L4

これで(E|逆行列X)の生成が完了です。よって元のデータを求めるにはこの逆行列に集めたD2,P2,P3,P4をかけます。

D =

245	245	41	221
0	1	0	0
39	187	231	192
96	192	64	32

242

200

222

200

こうして元の行列を得る事ができました。

コンテンツ

トップページ
Imonyについて
Imonyアンテナ
更新履歴

リンク集

≫P2P today
≫俺が新しいP2P作ろっか？
　　…P2P製作本スレ
≫Download板