データの分散配置におけるパリティより少し高度な冗長符号

更新：
2002年5月12日	公開

はじめに

データを分散配置する際に、冗長性を持たせることで、分散されたデータを全て取得しなくても元のデータを復元可能にできる。例えば、元のデータを2つに分割し、それぞれのデータとパリティを3箇所に分散配置すれば、3箇所のうち2つのデータを取得すれば元のデータが復元できる。しかし、単純なパリティでは、4箇所に分散して任意の2つのデータから復元可能にすることはできない。このページでは、そのような分散を可能にする符号について説明する。

表記・定義

データ列 a の n ビット目を、 a_[n] で表す。添え字は0から始まるものとし、小さい方が下位ビットを表す。排他的論理和を、演算子 ◇ で表す。演算子 ◇ をデータ列に対して使う場合は、それぞれのデータ列の同じ位置のビット同士の排他的論理和をとる。

関数 M を、以下のように定義する。

M(a)_[2n] = a_[2n+1]
M(a)_[2n+1] = a_[2n] ◇ a_[2n+1]

関数 M は、データを2ビット毎に分割し、下記の通り変換するのと等価である。例えば、 a が「01 11 00 10」とすると、 M(a) は、2ビット毎に下記の通り変換し、「10 01 00 11」となる。

00	→	00
01	→	10
10	→	11
11	→	01

M²(a) は M(M(a)) を表す。同様に、M³(a) は M(M(M(a))) を表す。

元のデータを2つに分割する場合は、分割後のデータ列を p, q と表す。分割方法は特に規定しない。1バイトずつ振り分けても、データの前半と後半に分割しても良い。

重要な恒等式

下記の恒等式が成り立つ。証明は省略するが、上記の定義と排他的論理和の基本性質(交換律・結合律・ a ◇ b ◇ b = a )から簡単に証明できる。

M³(a) = a

M(a ◇ b) = M(a) ◇ M(b)

a ◇ M(a) = M²(a)
M(a) ◇ M²(a) = a
M²(a) ◇ a = M(a)

4箇所に分散配置するための符号化

データを p, q に分割し、以下の通りデータ列 a, b, c, d を計算する。

a = p
b = q
c = p ◇ q
d = p ◇ M(q)

データ列 a, b, c, d はそれぞれ、 p, q と同じサイズなので、元のデータの半分のサイズになる。

a, b, c, d のうち、任意の2つのデータから、元のデータが復元できる。 a, b, c のうち2つのデータからは、パリティと同様の方法で復元できる。 a と d からは、以下のように復元できる。

p = a
q = M²(d ◇ p)

b と d からは、以下のように復元できる。

q = b
p = d ◇ M(q)

c と d からは、以下のように復元できる。

q = M(c ◇ d)
p = c ◇ q

5箇所に分散配置するための符号化

上記の a, b, c, d に、下記の e を加えると、5つのうちの任意の2つのデータから復元可能になる。

e = p ◇ M²(q)