JP2018198358A - 誤り訂正プログラム、及び、誤り訂正装置 - Google Patents

Abstract

【課題】データの誤り訂正において、処理負荷を抑制する。【解決手段】誤り訂正プログラムは、Ｎ個のＡデータ（ｎ）から冗長化データを生成すると共に、冗長化データからＡデータ（ｎ）を生成する。ここで、Ａデータ（ｎ）が示すビット列を、Ａ（ｎ）とし、Ａ（ｎ）の各々に対応する整数をＳ（ｎ）とし、Ａ（ｎ）に対応するビット列をＢ（ｎ）とし、Ｂ（ｎ）は、Ｓ（ｎ）を指数として２を累乗した値と、Ａ（ｎ）が示す値とを乗算した値を示す。また、全てのＡ（ｎ）の排他的論理和を示すデータを、Ｐ１データとし、全てのＢ（ｎ）の排他的論理和を示すデータを、Ｐ２データとする。誤り訂正プログラムは、Ａデータ（ｎ）に基づきＰ１データ及びＰ２データを生成し、これらのデータと、これらのデータの各々について生成された、当該データの誤りを検出するための付加データを、冗長化データとする。【選択図】図３

Description

本開示は、誤り訂正プログラム等に関する。

データの記憶媒体への書き込み及び読み出しを行ったり、データの送受信を行ったりする場合、物理的なノイズや機器の障害等によって、データが破損するリスクが存在する。該リスクに対応するため、書き込みや送信の際にデータを冗長化し、データの一部に破損が生じた場合であっても該破損がある一定の範囲内であればデータを復元できる、種々の技術が開発されている。

特許文献１には、このようなデータを復元できる技術として、データをある一定のサイズに分割してデータブロックを生成し、このデータブロックを用いてガロア体の積演算に基づくパリティを含む２種類のパリティを生成し、データブロックとこれらのパリティとを冗長化されたデータとして用いる、という技術が開示されている。

特許第４９３５３６７号公報

しかしながら、特許文献１に開示されている技術（以下、従来技術）では、ガロア体の積演算に基づいてパリティを生成するため、処理負荷が大きいという問題があった。
本開示は、データの誤り訂正において、処理負荷を抑制することを目的とする。

上記課題に鑑みてなされた本発明の一側面に係る誤り訂正プログラムは、ビット長がｌであるＮ個（Ｎは２以上の整数）のＡデータ（ｎ）（ｎは０〜Ｎ−１の整数）から冗長化データを生成すると共に、冗長化データからＡデータ（ｎ）を生成する装置としてコンピュータを動作させる。誤り訂正プログラムは、生成部、特定部、及び、復元部を備える。

ここで、２進数で表した値における０又は１の値の並びを、ビット列とする。また、Ａデータ（ｎ）が示すビット列を、Ａ（ｎ）とする。また、Ａ（ｎ）の各々に対応する整数であって、各整数は他の整数とは異なる値を有する整数を、Ｓ（ｎ）とし、Ｓ（ｎ）の最大値をＳｍａｘとする。また、Ａ（ｎ）に対応しており、ビット長がＳｍａｘとｌとを加算した値であるビット列を、Ｂ（ｎ）とし、Ｂ（ｎ）は、Ｓ（ｎ）を指数として２を累乗した値と、Ａ（ｎ）が示す値とを乗算した値を示す。また、全てのＡ（ｎ）の排他的論理和を示すビット列であるＰ１を示すデータを、Ｐ１データとし、全てのＢ（ｎ）の排他的論理和を示すビット列であるＰ２を示すデータを、Ｐ２データとする。

生成部は、Ａデータ（ｎ）に基づきＰ１データ及びＰ２データを生成し、Ａデータ（ｎ）、Ｐ１データ、及び、Ｐ２データの各々について、当該データの誤りを検出するための付加データを生成し、Ａデータ（ｎ）、Ｐ１データ、Ｐ２データ、及び、付加データを、冗長化データとする。

また、特定部は、冗長化データに含まれる付加データに基づき、該冗長化データに含まれるＡデータ（ｎ）、Ｐ１データ、及び、Ｐ２データのうちの破損しているデータを特定する。

また、復元部は、冗長化データにおいて、Ａデータ（ｎ）のうちの２つが破損しており、且つ、Ｐ１データ及びＰ２データが破損していない場合に、冗長化データに基づき、破損している２つのＡデータ（ｎ）を復元する。

また、破損している２つのＡデータ（ｎ）のｎの値を、ｆ０、ｆ１（ｆ０、ｆ１は０〜Ｎ−１の整数）とし、破損していないＡデータ（ｎ）のｎの値を、ｔ（ｔは、０〜Ｎ−１の整数であって、ｆ０、ｆ１以外の整数）とする。また、Ａ（ｆ０）とＡ（ｆ１）との排他的論理和を示すビット列を、Ｘ０とし、Ｂ（ｆ０）とＢ（ｆ１）との排他的論理和を示すビット列を、Ｘ１とする。また、Ｂ（ｆ０）において、当該Ｂ（ｆ０）に含まれるＡ（ｆ０）の最下位ビット、最上位ビットに相当するビットの位置を、それぞれ、ｂｌ、ｂｍとし、Ｘ１におけるｂｌからｂｍまでのビット列を、Ｘ１Ａとする。

また、復元部は、全てのＡ（ｔ）とＰ１との排他的論理和を算出することで、Ｘ０を算出し、Ａ（ｔ）に基づき算出された全てのＢ（ｔ）とＰ２との排他的論理和に基づき、Ｘ１Ａを算出する。また、Ｓ（ｆ０）とＳ（ｆ１）との差の絶対値を指数として２を累乗した値を、Ｓとし、Ａ（ｆ１）が示す値をＳで除算した値を示す、ビット長がｌであるビット列、又は、Ａ（ｆ１）が示す値をＳで乗算した値を示すビット列における、最下位ビットから並ぶビット長がｌであるビット列を、Ａ´（ｆ１）とする。復元部は、Ｘ０とＸ１Ａとの排他的論理和を算出することで、Ａ（ｆ１）とＡ´（ｆ１）との排他的論理和であるＸ２を算出し、Ｘ２に基づきＡ（ｆ１）を特定し、特定したＡ（ｆ１）と、Ｐ１又はＰ２とに基づき、Ａ（ｆ０）を特定し、特定したＡ（ｆ０）及びＡ（ｆ１）に基づき、Ａデータ（ｆ０）及びＡデータ（ｆ１）を復元する。

このような構成によれば、ガロア体の積演算を用いること無く、排他的論理和等を用いてデータの誤り訂正が行われるので、データの誤り訂正において処理負荷を抑制することができる。

なお、上記構成において、復元部は、Ａデータ（ｎ）のうちの１つであるＡデータ（ｆ２）（ｆ２は０〜Ｎ−１の整数）が破損しており、且つ、Ｐ１データが破損していない場合に、破損していないＡデータ（ｎ）をＡデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ２以外の整数）とし、全てのＡ（ｔ）とＰ１との排他的論理和をＡ（ｆ２）として算出し、算出したＡ（ｆ２）に基づきＡデータ（ｆ２）を復元しても良い。

このような構成によれば、Ｐ１が破損していない場合に、破損しているデータを特定することができる。
また、上記構成において、復元部は、Ａデータ（ｎ）のうちの１つであるＡデータ（ｆ３）（ｆ３は０〜Ｎ−１の整数）が破損しており、且つ、Ｐ２データが破損していない場合に、破損していないＡデータ（ｎ）をＡデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ３以外の整数）とし、全てのＢ（ｔ）とＰ２との排他的論理和をＢ（ｆ３）として算出し、算出したＢ（ｆ３）に基づきＡデータ（ｆ３）を復元しても良い。

このような構成によれば、Ｐ２が破損していない場合に、破損しているデータを特定することができる。
また、上記構成において、誤り訂正プログラムは、冗長化データを１つのコンピュータファイルとして出力するように構成されてもよい。このような構成によれば、冗長化データを１つのデータとして扱うことができるので、ユーザにとっての利便性が向上する。

なお、上述した誤り訂正プログラムにより動作するコンピュータに相当する、誤り訂正装置を構成してもよい。このような場合であっても、同様の効果を得ることができる。

図１Ａは、本実施形態の誤り訂正装置（ＰＣ）の構成を示すブロック図である。図１Ｂは、冗長化データの構成を示す説明図である。 図２Ａは、Ｐ１の生成を説明する説明図であり、図２Ｂは、Ｐ２の生成を説明する説明図である。 図３は、冗長化処理のフローチャートである。 図４は、復元処理のフローチャートである。 図５は、第１復元処理のフローチャートである。 図６Ａは、Ａ（１）とＡ（２）とが破損している例を示す説明図であり、図６ＢはＸ０の算出を説明する説明図であり、図６ＣはＸ１の算出を説明する説明図であり、図６ＤはＡ´（ｆ１）の説明図である。 図７Ａ、７Ｂは、Ｘ２の算出についての説明図である。 図８は、Ｘ２の算出についての説明図である。 図９Ａ〜９Ｄは、Ａ（２）、Ａ（１）の特定方法についての説明図である。 図１０Ａは、第２復元処理のフローチャートであり、図１０Ｂは、Ａ（１）が破損しておりＰ１が破損していない例を説明する説明図であり、図１０Ｃは、第３復元処理のフローチャートであり、図１０Ｄは、Ａ（１）が破損しておりＰ２が破損していない例を説明する説明図である。

以下、本発明の実施形態について図面を用いて説明する。なお、本発明の実施の形態は、下記の実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の形態を採りうる。

［１．構成の説明］
図１Ａは、本実施形態の誤り訂正装置として作動する周知のＰＣ１の構成を示している。ＰＣ１は、ディスプレイ１０、ＨＤＤ２０、ＣＰＵ３０、ＲＯＭ４０、ＲＡＭ５０、入力装置６０等を備える。

ディスプレイ１０は、映像信号に基づき、ＣＰＵ３０等にて生成された映像を表示する。入力装置６０は、キーボード、マウス等から構成され、ユーザから受け付けた操作に応じた信号をＣＰＵ３０に出力する。ＲＯＭ４０は読み出し専用の不揮発性メモリであり、ＨＤＤ２０は読み出し、書き込み可能な不揮発性メモリである。ＲＯＭ４０、ＨＤＤ２０には、ＣＰＵ３０が読み出して実行するプログラム等が予め記憶されている。ＲＡＭ５０は読み出し、書き込み可能な揮発性メモリであり、ＣＰＵ３０がＲＯＭ４０、ＨＤＤ２０に記憶されたプログラムを実行する際に、そのプログラムを一時的に保存したり、作業用のデータを一時的に保存したりするための記憶領域として用いられる。

ＣＰＵ３０は、ＯＳをＨＤＤ２０から読み出して実行し、ＨＤＤ２０に記憶されている各種プログラムをＯＳ上のプロセスとして実行する。このプロセスにおいて、ＣＰＵ３０は入力装置６０から信号の入力を受け付け、ディスプレイ１０に表示する映像を生成し、ＲＡＭ５０、ＨＤＤ２０に対してデータの読み出し、書き込みの制御を行う。

ＰＣ１には、本実施形態の誤り訂正プログラムがインストールされている。誤り訂正プログラムは、ＨＤＤ２０に保存されていると共に、ＯＳ上のプロセスとして実行されるアプリケーションの１つであり、誤り訂正プログラムを動作させることで、ＰＣ１は誤り訂正装置として稼働する。なお、誤り訂正装置を、ＰＣ１以外の電子装置として構成しても良い。

［２．動作の説明］
（１）概要について
まず、誤り訂正プログラムの概要について説明する。以下の説明では、誤り訂正プログラムが処理を行うといった記載がなされているが、これは、誤り訂正プログラムに従い動作するＰＣ１のＣＰＵ３０が処理を行うということを意味するのは、言うまでも無い。

誤り訂正プログラムは、冗長化の対象となるデータ（以下、オリジナルデータ）から冗長化データを生成する生成部と、冗長化データにおいて破損しているデータを特定する特定部と、破損しているデータを復元する復元部と、を備える。ここでいう冗長化データとは、オリジナルデータが冗長化されたデータのことである。冗長化とは、オリジナルデータに該オリジナルデータ以外の情報を追加することによって耐障害性を向上させること、をいう。

なお、ここでいうオリジナルデータとは、ＰＣ１に搭載されたプログラムを用いて作成された任意のデータをいう。オリジナルデータには、例えば、入力装置６０を介してユーザから受け付けた操作に応じて、ＰＣ１に搭載されたプログラム（一例として、ＣＡＤプログラム）を用いて作成された、ビル、家屋等の建築物を含む各種構造物（以後、建設物）を建設するための三次元の設計図を表すデータが含まれうる。但し、これに限定されるものではなく、オリジナルデータには、ＰＣ１に搭載されたプログラムを用いて作成された、種々の設計図を表すデータが含まれうる。

誤り訂正プログラムにおいて、生成部は、後述する図３に示すように、冗長化データを生成する冗長化処理を実行する。また、誤り訂正プログラムにおいて、特定部及び復元部は、後述する図４、図５、図８に示すように、冗長化データにおいて破損しているデータを特定し、破損しているデータを復元する復元処理を実行する。以下、順に説明する。

（２）冗長化処理について
（２−１）冗長化処理の概要
冗長化処理では、誤り訂正プログラムは、オリジナルデータをある一定のサイズに分割してデータブロックを生成し、このデータブロックを用いて２種類のパリティを生成し、データブロックとこれらのパリティとを含む冗長化データを生成する。ここでいうパリティとは、破損したデータブロックを破損していないデータブロックに基づいて特定するために用いられる情報をいう。

誤り訂正プログラムは、はじめに、冗長化の対象となるデータ（以下、オリジナルデータ）から同一サイズのＮ個のデータであるデータブロック（以後、Ａデータ（ｎ）とも記載）を生成し、Ａデータ（ｎ）から冗長化データを生成する。なお、Ｎは２以上の整数であり、ｎは、０〜Ｎ−１の整数である。また、Ａデータ（ｎ）のサイズをビット長で表すと、ｌビットであり、バイト長で表すと、Ｌバイトとなる。

オリジナルデータのサイズは、Ａデータ（ｎ）のサイズであるＬの整数倍であることが望ましい。なお、オリジナルデータのサイズがＬの整数倍でない場合は、例えば、Ａデータ（０）、Ａデータ（１）、Ａデータ（２）、・・・といった様に順に分割した際に最後となるＡデータ（Ｎ−１）のサイズが、Ｌ未満となることがあり得る。この場合、誤り訂正プログラムは、不足分を０で充填することによって、Ａデータ（ｎ−１）のサイズがＬとなるよう調整してもよい。

誤り訂正プログラムは、Ａデータ（ｎ）に加えて更に、２種類のパリティデータ、及び、付加データｈ（ｎ）を生成する。２種類のパリティデータとは、Ｐ１データ、Ｐ２データである。パリティデータは１つ又は２つのＡデータ（ｎ）が破損した際、破損したＡデータ（ｎ）を復元可能にするためのデータである。

誤り訂正プログラムは、Ａデータ（ｎ）、Ｐ１データ、Ｐ２データ、付加データ、及び、例えば管理データといったその他データを含む冗長化データを生成する。
なお、本実施形態では、管理データがその他データとして含まれているが、これに限定されるものではない。その他データには、例えば、通信において送受信するデータに含まれるヘッダやフッダ等、が含まれうる。誤り訂正プログラムは、少なくともＡデータ（ｎ）、Ｐ１データ、Ｐ２データ、及び、付加データを含むデータ、として構成されうる。

以下では、Ａデータ（ｎ）、Ｐ１データ、及び、Ｐ２データが示すビット列を、それぞれ、Ａ（ｎ）、Ｐ１、及び、Ｐ２と記載する。ビット列とは、２進数で表した値における０又は１の値の並びを意味する。また、理解を容易にするために、本実施形態の具体例を説明する際には、図１Ｂに示すように、Ｎ＝４とし、Ａ（０）、Ａ（１）、Ａ（２）、Ａ（３）をＡ（ｎ）（ｎは０〜３の整数）として説明する。但し、Ｎが４に限定されないことは、言うまでもない。

（２−１−１）Ｐ１の生成
誤り訂正プログラムは、全てのＡ（ｎ）の排他的論理和を、Ｐ１として算出する。なお、Ｐ１のサイズは、ｌビット（換言すれば、Ｌバイト）となる。図２Ａは、本実施形態において、Ｎ＝４としたときに、Ａ（０）〜Ａ（３）の排他的論理和としてＰ１が生成される様子を示す。以下では、排他的論理和を「＾」の記号で表す。つまり、Ｐ１は（１）式のように表される。

Ｐ１＝Ａ（０）＾Ａ（１）＾Ａ（２）＾Ａ（３） （１）
（２−１−２）Ｐ２の生成
ここで、Ａ（ｎ）の各々に対応するＮ個の整数であって、各整数は、他の整数とは異なる値を有する整数を、Ｓ（ｎ）とする。なお、Ｓ（ｎ）は０以上の整数であっても良い。また、Ｓ（ｎ）の最大値を、Ｓｍａｘとする。また、Ａ（ｎ）に対応するビット列を、Ｂ（ｎ）とする。Ｂ（ｎ）のサイズは、バイト長がＭであり、ビット長がｍである。また、Ｂ（ｎ）のサイズをビット長で表すと、Ｓｍａｘとｌとを加算した値となる。Ｂ（ｎ）は、Ａ（ｎ）が示す値と、Ｓ（ｎ）を指数として２を累乗した値とを乗算した値を示す。換言すれば、Ｂ（ｎ）は、Ａ（ｎ）をＳ（ｎ）ビット上位側にシフトした値を示す。そして、Ｐ２は、全てのＢ（ｎ）の排他的論理和を示す。

なお、シフトとは、所定のメモリ領域に記憶されているデータが示すビット列を上位側又は下位側に移動させることで、該ビット列を編集することを意味する。ここで、予め定められた正の整数を、Ｄとする。ビット列をＤビット上位側にシフトした場合には、シフト後の該メモリ領域における最下位ビットから上位側に並ぶＤビットには、０が設定された状態となる。また、ビット列をＤビット下位側にシフトした場合には、シフト後の該ビット列における最上位ビットから下位側に並ぶＤビットには、０が設定された状態となる。そして、シフト後の該メモリ領域に記憶されているデータが示すビット列が、シフトの結果として得られる。

誤り訂正プログラムは、Ａ（ｎ）に基づきＰ２を算出する。具体的には、例えば、乗算、除算、加算、減算、又は、データのシフト等や、Ａデータ（ｎ）をメモリの所定のアドレスに保存したりすることで、Ａ（ｎ）からＢ（ｎ）が算出される。そして、全てのＢ（ｎ）の排他的論理和を算出することで、Ｐ２が算出される。Ｐ２のサイズは、Ｍバイト（換言すれば、Ｓｍａｘ＋ｌビット）となる。

図２Ｂは、本実施形態において、Ｎ＝４としたときに、Ｂ（０）〜Ｂ（３）の排他的論理和としてＰ２が生成される様子を示す。この場合、ＳｍａｘはＳ（３）となる。
ここで、Ｓ（ｎ）は、一例として、ｎｋ（ｋは１以上の整数）として表されるものとする。また、一例として、ｋは８の倍数とする。すなわち、ｋ＝８ｘ（ｘは１以上の整数）、つまり、Ｓ（ｎ）＝８ｎｘとなる。また、この場合、Ｐ２のバイト長であるＭは、Ｌ＋（Ｎ−１）ｘバイトとなる。

また、ここでは、Ｓ（ｎ）をｎｋとする例を示したが、これに限定されるものではない。Ｓ（ｎ）は、ｎの増加と無関係に、ランダムに設定されうる。
なお、ｋは、任意の値に設定されうる。但し、本実施形態のように、ｋは、８、１６、３２、・・・等といったバイト単位、すなわち８の倍数であることが望ましい。更に述べると、ｋは、コンピュータのバス幅に等しい値とすることが望ましい。例えば、６４ビットアーキテクチャのコンピュータで６４ビットバスが用いられる場合であれば、ｋ＝６４とすることが望ましい。

本実施形態においては、一例として、Ｂ（ｎ）及びＰ２の算出は、Ａデータ（ｎ）のメモリ転送と、Ａ（ｎ）と、該メモリ転送先に記憶されているデータが示すビット列との排他的論理和と、によって、一括して実現される。すなわち、メモリには、予めＰ２データが記憶される領域（Ｐ２領域）として、Ｍバイトの領域が設定されている。Ｐ２の算出を開始する直前は、Ｐ２領域に０が設定される。また、Ｐ２領域には、Ａ（ｎ）の記憶領域であるＲ（ｎ）が定められている。Ｒ（ｎ）の先頭アドレスは、０が設定されたＰ２領域におけるＲ（ｎ）にＡデータ（ｎ）をメモリ転送することで、Ｐ２領域に保存されたデータがＢ（ｎ）を示すよう調整されている。一例として、Ｒ（ｎ）の先頭アドレスは、Ｐ２領域の先頭アドレスから、Ｐ２領域の末尾側に、ｘ（Ｎ−１−ｎ）バイトオフセットされたアドレスとなる。なお、Ａデータ（ｎ）の記憶領域Ｒ（ｎ）は、他のＡデータ（ｎ）の記憶領域と一部重複する。

そして、Ｒ（ｎ）にＡデータ（ｎ）が転送される際、Ｒ（ｎ）に記憶されているデータが示すビット列とＡ（ｎ）との排他的論理和が算出される。そして、算出された値が、Ｒ（ｎ）に記憶される。このため、Ａデータ（ｎ）が全てＰ２領域に転送されると、Ｐ２領域にてＰ２データが生成される。これにより、乗除算等を用いること無く、メモリ転送によりＰ２を生成できるため、処理負荷を抑制できる。

但し、Ｐ２の生成方法は、これに限定されるものではない。例えば、Ａ（ｎ）に基づいてＢ（ｎ）を示すデータを生成し、これらのデータからＰ２データを生成してＰ２領域に記憶しても良い。

ここで、Ｐ２は、（２）式のように表される。
Ｐ２＝Ｂ（０）＾Ｂ（１）＾Ｂ（２）＾Ｂ（３） （２）
（２−１−３）付加データの生成
誤り訂正プログラムは、Ａデータ（ｎ）、Ｐ１データ、及び、Ｐ２データの各々について、当該データの誤りを検出するためのデータである付加データを生成する。ここでは、Ａデータ（ｎ）、Ｐ１データ、及び、Ｐ２データの各々から算出したハッシュ値を示すデータが、付加データとして用いられる。ハッシュ値とは、元になるデータに対して予め定められた演算処理（以下、ハッシュ関数）を行うことによって求められる値をいう。以下では、Ａデータ（ｎ）、Ｐ１データ、及び、Ｐ２データの各々から算出したハッシュ値を示すデータを、それぞれ、ｈ（ｎ）、ｈ（Ｐ１）、ｈ（Ｐ２）とする。ここでは、各データについて、同じハッシュ関数を用いてハッシュ値を算出するものとする。ｈ（ｎ）、ｈ（Ｐ１）、ｈ（Ｐ２）は、予め定められたデータサイズ（以下、ハッシュサイズ）となる。

（２−１−４）管理データ
管理データは、誤り訂正プログラムにおいて、予めその値が定められている種々のデータをいう。管理データは、例えば、Ａ（ｎ）の数であるＮ、Ａ（ｎ）のサイズであるＬ、ハッシュサイズ、及び、Ｂ（ｎ）及びＰ２のサイズであるＭ等を示す。また、管理データには、例えば、上述のｋやｘ等といった、ｎとＳ（ｎ）とを対応づけるためのデータが含まれうる。これらのデータ等は、予めＨＤＤ２０に記憶されており、誤り訂正プログラムを実行する際に、ＲＡＭ５０に記憶される。

（２−２）冗長化処理
次に、冗長化処理について、図３を用いて説明する。誤り訂正プログラムは、例えば、ＨＤＤ２０に対して、ＰＣ１上のプログラムによって生成されたオリジナルデータの書き込みを行う際に、本冗長化処理を実行する。本冗長化処理によって生成された冗長化データは、ＨＤＤ２０に対して、１つのコンピュータファイルとして記憶されるものとする。１つのコンピュータファイルとは、ＰＣ１におけるファイルシステム上で、１つのファイルとして扱われるデータであること、を意味する。

なお、以下の説明において主語が省略されている場合は、誤り訂正プログラムを主語とする。また、オリジナルデータは、ＨＤＤ２０において、予め定められた領域に記憶されているものとする。

はじめに、Ｓ１１０では、ＲＡＭ５０から管理データを取得する。
Ｓ１１５では、ＨＤＤ２０において、Ｐ１データが記憶されるサイズがＬバイトの領域（以下、Ｐ１領域）、及び、Ｐ２領域を設定する。また、本ステップでは、Ｐ１領域及びＰ２領域は、０に初期化される。また、ｎは０に初期化される。

Ｓ１２０〜Ｓ１５０では、オリジナルデータからＬバイトのＡデータ（ｎ）を生成する処理が繰り返し実行される。また、Ｓ１２０〜Ｓ１５０が繰り返し実行されることによって、Ｐ１データ及びＰ２データが生成される。

具体的には、Ｓ１２０では、オリジナルデータにおいて、Ｓ１２０〜Ｓ１５０の処理対象となっていないデータ（以下、未処理データ）のサイズが、Ｌ以上か否かを判断する。未処理データがＬ以上の場合、処理をＳ１３０へ移行させ、Ｌ未満の場合、処理をＳ１２５へ移行させる。

Ｓ１２５では、未処理データに、所定のサイズの０を示すデータを加えたものを、Ｌバイトのデータとする。なお、未処理データに対しどのように０を示すデータを加えるかについては、適宜定められる。

Ｓ１３０では、オリジナルデータからＬバイトのデータをＡデータ（ｎ）として取得し、Ａデータ（ｎ）をＨＤＤ２０に記憶する。
Ｓ１３５では、Ｓ１３０にて取得したＡデータ（ｎ）が示すＡ（ｎ）と、Ｐ１領域に記憶されたデータが示すビット列との排他的論理和を算出し、算出結果をＰ１領域に記憶する。

Ｓ１４０では、Ｓ１３０にて取得したＡデータ（ｎ）を、上述のように、Ｐ２領域内にメモリ転送し、且つ、排他的論理和を算出する。
Ｓ１４５では、Ａデータ（ｎ）についてのハッシュ値であるｈ（ｎ）を算出し、ｈ（ｎ）をＨＤＤ２０に記憶する。また、本ステップでは、ｎ＋１を新たなｎとして記憶し直す。

Ｓ１５０では、オリジナルデータのうち、未処理データがあるか否かを判断する。未処理データがある場合は、処理をＳ１２０へ移行させ、Ｓ１２０〜Ｓ１５０の処理を繰り返す。未処理データがない場合は、処理をＳ１５５へ移行させる。これにより、Ｓ１５５へ処理が移行されるまでに、Ａデータ（ｎ）及びｈ（ｎ）（ｎは０〜Ｎ−１）、Ｐ１データ、Ｐ２データがそれぞれ生成され、ＨＤＤ２０に記憶される。

Ｓ１５５では、Ｐ１データについてのハッシュ値を示すｈ（Ｐ１）を生成し、ｈ（Ｐ１）をＨＤＤ２０に記憶する。
Ｓ１６０では、Ｐ２データについてのハッシュ値を示すｈ（Ｐ２）を生成し、ｈ（Ｐ２）をＨＤＤ２０に記憶する。そして、本冗長化処理は終了となる。

このようにして、Ａデータ（ｎ）、ｈ（ｎ）、Ｐ１データ、ｈ（Ｐ１）、Ｐ２データ、ｈ（Ｐ２）、及び、管理データが、冗長化データとして、ＨＤＤ２０に記憶される。
（３）復元処理について
（３−１）復元処理の概要
復元処理では、誤り訂正プログラムは、特定部が、冗長化データにおいて破損しているデータを特定する。続いて、誤り訂正プログラムは、復元部が、冗長化データにおいて破損しているデータの数が２以下であり、且つＡデータ（ｎ）のうち破損しているものが２つ以下である場合に、破損しているＡデータ（ｎ）を特定し、復元する。なお、Ｐ１データ及びＰ２データの両方が破損している場合、及び、破損しているデータの数が３以上である場合、誤り訂正プログラムは、破損しているＡデータ（ｎ）を復元できない。

（３−２）復元処理
続いて、誤り訂正プログラムにおける特定部及び復元部が実行する復元処理について、図４を用いて説明する。誤り訂正プログラムは、例えば、ＨＤＤ２０から、冗長化データの読み出しを行う際に、本復元処理を実行する。

はじめに、Ｓ２１０では、破損しているデータを特定する。具体的には、冗長化データに含まれるｈ（ｎ）、ｈ（Ｐ１）及びｈ（Ｐ２）を用いて、冗長化データに含まれるＡデータ（ｎ）、Ｐ１データ、及び、Ｐ２データのうちの破損しているデータを特定する。

つまり、本ステップでは、冗長化データに含まれるＡデータ（ｎ）、Ｐ１データ、及び、Ｐ２データから、冗長化データの生成時と同じハッシュ関数を用いてハッシュ値が算出される。そして、算出されたハッシュ値と冗長化データに含まれるｈ（ｎ）、ｈ（Ｐ１）、及び、ｈ（Ｐ２）とが一致していない場合に、一致していないデータを破損しているデータとして特定する。このようなハッシュ値に基づいて破損しているデータを特定する技術は、公知の技術であるため、詳細な説明を割愛する。

Ｓ２１５では、少なくとも１つのＡデータ（ｎ）が破損しているか否かを判断する。少なくとも１つのＡデータ（ｎ）が破損している場合は、処理をＳ２２０へ移行させ、破損していない場合は、本復元処理を終了させる。

Ｓ２２０では、Ａデータ（ｎ）とＰ１データとＰ２データとのうち、破損しているデータの数が２よりも大きいか否かを判断する。破損しているデータの数が２よりも大きい場合は処理をＳ２５５へ移行させ、該数が２以下である場合は処理をＳ２２５へ移行させる。

Ｓ２２５では、破損しているＡデータ（ｎ）の数が２であるか否かを判断する。ここで、破損しているＡデータ（ｎ）の数が２である場合は、処理をＳ２３０へ移行させて第１復元処理を実行する。第１復元処理では、破損している２つのＡ（ｎ）を復元して、本復元処理を終了させる。破損しているＡデータ（ｎ）の数が２でない場合、つまり１である場合は、処理をＳ２３５へ移行させる。

Ｓ２３５では、Ｐ１データが破損しているか否かを判断する。ここで、Ｐ１データが破損していない場合は、処理をＳ２４０へ移行させて第２復元処理を実行する。第２復元処理では、破損している１つのＡデータ（ｎ）を復元して、本復元処理を終了させる。Ｐ１データが破損している場合は、処理をＳ２４５へ移行させる。

Ｓ２４５では、Ｐ２データが破損しているか否かを判断する。ここで、Ｐ２データが破損していない場合は、処理をＳ２５０へ移行させて第３復元処理を実行する。第３復元処理では、破損している１つのＡデータ（ｎ）を復元して、本復元処理を終了させる。Ｐ２データが破損している場合は、処理をＳ２５５へ移行させる。

Ｐ１データ及びＰ２データの両方が破損している場合、及び、破損しているデータの数が３以上である場合に移行するＳ２５５では、一例として、復元処理が異常終了されたことを表す異常フラグをセットし、本復元処理を終了させる。

次に、第１復元処理、第２復元処理、第３復元処理をそれぞれ説明する。
（３−２−１）第１復元処理
次に、第１復元処理について、図５を用いて説明する。第１復元処理では、Ａデータ（ｎ）のうちの２つが破損しており、且つ、Ｐ１データ及びＰ２データが破損していない場合に、破損している２つのＡデータ（ｎ）が復元される。ここで、破損しているＡデータ（ｎ）のｎの値を、ｆ０、ｆ１（ｆ０、ｆ１は０〜Ｎ−１の整数）とし、破損していないＡデータ（ｎ）のｎの値を、ｔ（ｔは、０〜Ｎ−１の整数であって、ｆ０、ｆ１以外の整数）とする。

図６Ａは、本実施形態において、Ｎ＝４としたときに、Ａデータ（１）とＡデータ（２）とが破損しており、且つ、Ａデータ（０）とＡデータ（３）とＰ１とＰ２とが破損していない様子を示す。

Ｓ３１０では、全てのＡ（ｔ）とＰ１との排他的論理和を算出することで、Ａ（ｆ０）とＡ（ｆ１）との排他的論理和を示すビット列であるＸ０を算出する。すなわち、本実施形態においては、図６Ｂに示すように、Ａ（０）とＡ（３）とＰ１との排他的論理和を、Ｘ０として算出する。Ｐ１は（１）式で表されることから、Ｘ０は、以下の（３）式で表されるように、Ａ（１）とＡ（２）との排他的論理和に相当する。

Ｐ１＝Ａ（０）＾Ａ（１）＾Ａ（２）＾Ａ（３）
Ａ（０）＾Ｐ１＝Ａ（０）＾Ａ（０）＾Ａ（１）＾Ａ（２）＾Ａ（３）
Ａ（０）＾Ｐ１＝Ａ（１）＾Ａ（２）＾Ａ（３）
Ａ（３）＾Ａ（０）＾Ｐ１＝Ａ（３）＾Ａ（１）＾Ａ（２）＾Ａ（３）
Ａ（３）＾Ａ（０）＾Ｐ１＝Ａ（１）＾Ａ（２）＝Ｘ０ （３）
Ｓ３２０では、Ａ（ｔ）に基づきＢ（ｔ）を算出する。すなわち、本実施形態においては、破損していないＡ（０）とＡ（３）とに基づき、Ｂ（０）とＢ（３）とを算出する。

Ｓ３３０では、全てのＢ（ｔ）とＰ２との排他的論理和を算出することで、Ｂ（ｆ０）とＢ（ｆ１）との排他的論理和を示すビット列であるＸ１を算出する。すなわち、本実施形態においては、図６Ｃに示すように、Ｂ（０）とＢ（３）とＰ２との排他的論理和を、Ｘ１として算出する。Ｐ２は（２）式で表されることから、Ｘ１は、以下の（４）式で表されるように、Ｂ（１）とＢ（２）との排他的論理和に相当する。

Ｐ２＝Ｂ（０）＾Ｂ（１）＾Ｂ（２）＾Ｂ（３）
Ｂ（０）＾Ｂ（３）＾Ｐ２＝Ｂ（１）＾Ｂ（２）＝Ｘ１ （４）
そして、Ｓ３４０〜Ｓ３６０では、次のようにしてＡ（ｆ０）、Ａ（ｆ１）が復元される。

まず、Ｂ（ｆ０）において、Ａ（ｆ０）の最下位ビット、最上位ビットに相当するビットの位置を、それぞれ、ｂｌ、ｂｍとする。つまり、Ｂ（ｆ０）におけるＡ（ｆ０）が占めるビット列の最下位ビットの位置を、ｂｌとし、該ビット列の最上位ビットの位置を、ｂｍとする。そして、Ｘ１におけるｂｌからｂｍまでのビット列を、Ｘ１Ａとする。

本実施形態では、一例として、Ａデータ（１）とＡデータ（２）とが破損している。Ｘ１におけるＸ１Ａを、Ｂ（１）に含まれるＡ（１）に揃えるか（ｆ０＜ｆ１、つまり、ｆ０＝１、ｆ１＝２とするか）、又は、Ｂ（２）におけるＡ（２）に揃えるか（ｆ０＞ｆ１、つまり、ｆ０＝２、ｆ１＝１とするか）によって、計算方法は異なるものとなる。

すなわち、ｆ０＜ｆ１（換言すれば、ｆ０＝１、ｆ１＝２）の場合、図６Ｃに示すように、Ｂ（１）におけるＡ（１）が占める部分の最下位のビット、最上位のビットが、それぞれ、ｂｌ、ｂｍとなる。そして、Ｘ１Ａは、Ａ（１）と、Ｂ（２）におけるｂｌからｂｍかけてのビット列との排他的論理和を示す。一方、ｆ０＞ｆ１（換言すれば、ｆ０＝２、ｆ１＝１）の場合、Ｂ（２）におけるＡ（２）が占める部分の最下位のビット、最上位のビットが、それぞれ、ｂｌ、ｂｍとなる。そして、Ｘ１Ａは、Ａ（２）と、Ｂ（１）におけるｂｌからｂｍかけてのビット列との排他的論理和を示す。

また、図６Ｄに示すように、ｆ０＜ｆ１の場合には、Ａ（ｆ１）を、Ｓ（ｆ０）とＳ（ｆ１）との差分の絶対値である｜Ｓ（ｆ０）−Ｓ（ｆ１）｜ビット上位側にシフトさせたデータ列を、Ａ´（ｆ１）とする。なお、本実施形態では、｜Ｓ（ｆ０）−Ｓ（ｆ１）｜＝ｋとなる。ここで、｜Ｓ（ｆ０）−Ｓ（ｆ１）｜を指数として２を累乗した値を、Ｓとする。換言すれば、Ａ´（ｆ１）は、Ａ（ｆ１）が示す値をＳで乗算した値のビット列における、最下位ビットから並ぶデータ長がｌであるビット列となる。一方、ｆ０＞ｆ１の場合には、Ａ（ｆ１）を、｜Ｓ（ｆ０）−Ｓ（ｆ１）｜ビット下位側にシフトさせたデータ列を、Ａ´（ｆ１）とする。換言すれば、Ａ´（ｆ１）は、Ａ（ｆ１）が示す値をＳで除算した値を示す、ビット長がｌであるビット列となる。

そして、図７Ａに示すように、Ｘ０とＸ１Ａとの排他的論理和であるＸ２を算出する。Ｘ２は、Ａ（ｆ１）とＡ´（ｆ１）との排他的論理和に相当する。さらに、Ｘ２に基づきＡ（ｆ１）を特定し、特定したＡ（ｆ１）と、Ｐ１又はＰ２とに基づき、Ａ（ｆ０）を特定する。

本実施形態では、一例として、Ｘ１を下位側にシフトした上でＸ２を算出する。
まず、ｆ０＜ｆ１とした場合について説明する。Ｓ３４０では、Ｘ１をＳ（１）ビット（換言すれば、ｋビット）下位側にシフトさせたＸ１´を算出する。図７Ｂに示すように、Ｘ１´は、Ａ（１）と同じ値を示すビット長がｍのビット列と、Ａ（２）をＳ（２）−Ｓ（１）ビット上位側にシフトした値と同じ値を示す、ビット長がｍのビット列との排他的論理和を示す。そして、Ｘ１´における最下位ビットから並ぶビット長がｌのビット列を、Ｘ１Ａとして特定する。

Ｓ３５０では、Ｘ１ＡとＸ０との排他的論理和であるＸ２を算出する。図７Ｂに示すように、Ｘ２は、Ａ（２）と、Ａ（２）をＳ（２）−Ｓ（１）ビット（換言すれば、ｋビット）上位側にシフトしたビット列との排他的論理和に相当する。

一方、ｆ０＞ｆ１とした場合、以下のようにしてＸ２が算出される。すなわち、Ｓ３４０では、Ｘ１をＳ（２）ビット下位側にシフトさせたＸ１´を算出する。図８に示すように、Ｘ１´は、Ａ（１）をＳ（１）ビット下位側にシフトさせたビット列と同じ値を示す、ビット長がｍのビット列と、Ａ（２）と同じ値を示すビット長がｍのビット列との排他的論理和を示す。そして、Ｘ１´における最下位ビットから並ぶビット長がｌのビット列を、Ｘ１Ａとして特定する。

Ｓ３５０では、Ｘ１ＡとＸ０との排他的論理和であるＸ２を算出する。図８に示すように、Ｘ２は、Ａ（１）と、Ａ（１）をＳ（２）−Ｓ（１）ビット（換言すれば、ｋビット）下位側にシフトしたビット列との排他的論理和に相当する。

なお、この他にも、一例として、Ｘ０と同じ値を示すビット長がｍのビット列を、Ｓ（１）ビット、又は、Ｓ（２）ビット上位側にシフトしたＸ０´を算出しても良い。そして、Ｘ０´とＸ１との排他的論理和であるＹを算出しても良い。Ｙにおけるｂｌからｂｍまでのビット列は、Ｘ２となる。シフト等により、ＹからＸ２を算出しても良い。

続いて、Ｓ３６０では、Ｘ２に基づきＡ（ｆ１）が特定され、その後、Ａ（ｆ０）が特定される。
まず、ｆ０＜ｆ１の場合、つまり、ｆ１＝２の場合、Ｘ２は、Ａ（ｆ１）と、Ａ（ｆ１）を、｜Ｓ（ｆ０）−Ｓ（ｆ１）｜ビット上位側にシフトしたビット列であるＡ´（ｆ１）との排他的論理和となる。このため、本実施形態では、Ｘ２は、図７Ｂに示すように、Ａ（２）と、Ａ（２）をＳ（２）−Ｓ（１）ビット（換言すれば、ｋビット）上位側にシフトしたビット列との排他的論理和に相当する。まず、Ｘ２に基づき、Ａ（ｆ１）が特定される。以下では、Ａ（ｆ１）の特定方法について説明する。

Ｘ２及びＡ（２）において、最下位ビットから並ぶビット長がＳ（２）−Ｓ（１）のビット列を、（ア）とする。また、Ａ´（２）において、最下位ビットから並ぶビット長がＳ（２）−Ｓ（１）のビット列は、全て０となる。このため、図９Ａに示すように、Ｘ２及びＡ（２）の（ア）は一致する。したがって、Ｘ２の（ア）を、Ａ（２）における（ア）として特定できる。

次に、Ａ（２）、Ｘ２において、（ア）の上位側に隣接するビットから上位側に並ぶビット長がｋのビット列を、それぞれ、（イ）、（ウ）とする。図９Ｂに示すように、（ウ）は、（ア）と（イ）との排他的論理和に相当する。このため、Ａ（２）の（ア）とＸ２の（ウ）との排他的論理和を算出することで、Ａ（２）の（イ）を特定できる。

そして、図９Ｃに示すように、同様にして、Ａ（２）における（イ）の上位側に隣接するビットから上位側に並ぶビットを、ビット長がｋのビット列単位で繰り返し特定することで、Ａ（２）を特定する。

一方、ｆ０＞ｆ１の場合、つまり、ｆ１＝１の場合、Ｘ２は、Ａ（ｆ１）と、Ａ（ｆ１）を、｜Ｓ（ｆ０）−Ｓ（ｆ１）｜ビット下位側にシフトしたビット列であるＡ´（ｆ１）との排他的論理和となる。このため、本実施形態では、Ｘ２は、図８に示すように、Ａ（１）と、Ａ（１）をＳ（２）−Ｓ（１）ビット（換言すれば、ｋビット）下位側にシフトしたビット列との排他的論理和に相当する。そして、同様にして、まず、Ｘ２に基づき、Ａ（ｆ１）が特定される。

Ｘ２及びＡ（１）において、最上位ビットから並ぶビット長がＳ（２）−Ｓ（１）のビット列を、（ア）とする。また、Ａ´（１）において、最上位ビットから並ぶビット長がＳ（２）−Ｓ（１）のビット列は、全て０となる。このため、図９Ｄに示すように、Ｘ２及びＡ（１）の（ア）は一致する。したがって、Ｘ２の（ア）を、Ａ（１）における（ア）として特定できる。

次に、Ａ（１）、Ｘ２において、（ア）の下位側に隣接するビットから下位側に並ぶビット長がｋのビット列を、それぞれ、（イ）、（ウ）とする。図９Ｄに示すように、（ウ）は、（ア）と（イ）との排他的論理和に相当する。このため、Ａ（１）の（ア）とＸ２の（ウ）との排他的論理和を算出することで、Ａ（１）の（イ）を特定できる。

そして、同様にして、Ａ（１）における（イ）の下位側に隣接するビットから下位側に並ぶビットを、ビット長がｋのビット列単位で繰り返し特定することで、Ａ（１）を特定する。

次に、Ａ（ｆ１）と、Ｐ１又はＰ２とに基づき、Ａ（ｆ０）を特定する。具体的には、Ｐ１とＡ（ｔ）と排他的論理和により算出されたＸ０とＡ（ｆ１）との排他的論理和を、Ａ（ｆ０）として算出しても良い。この他にも、Ａ（ｆ１）に基づきＢ（ｆ１）を算出しても良い。そして、Ｘ１とＢ（ｆ１）との排他的論理和を、Ｂ（ｆ０）として算出し、Ｂ（ｆ０）に基づきＡ（ｆ０）を算出しても良い。

誤り訂正プログラムは、特定したＡ（ｆ０）、Ａ（ｆ１）を、冗長化データにおけるＡデータ（ｆ０）、Ａデータ（ｆ１）に設定することで、これらのデータを復元する。そして、第１復元処理を終了する。

（３−２−２）第２復元処理
次に、第２復元処理について、図１０Ａを用いて説明する。誤り訂正プログラムは、第２復元処理では、Ａデータ（ｎ）のうちの１つであるＡデータ（ｆ２）（ｆ２は０〜Ｎ−１の整数）が破損しており、且つ、Ｐ１データが破損していない場合に、Ａ（ｆ２）を特定することが可能である。ここで、破損していないＡデータ（ｎ）をＡデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ２以外の整数）と記載する。

図１０Ｂは、一例として、Ａデータ（０）〜Ａデータ（３）のうちＡデータ（１）が破損しており、且つ、Ｐ２データが破損しＰ１データが破損していない様子を示す。この場合、ｆ２＝１であり、ｔは０、２、３である。

Ｓ４１０では、全てのＡ（ｔ）とＰ１との各々が示す値の排他的論理和を、Ａ（ｆ２）として算出する。なお、算出したＡ（ｆ２）を、冗長化データにおけるＡデータ（ｆ２）に設定することで、Ａデータ（ｆ２）が復元されても良い。そして、第２復元処理を終了する。

（３−２−３）第３復元処理
次に、第３復元処理について、図１０Ｃを用いて説明する。誤り訂正プログラムは、第３復元処理では、Ａデータ（ｎ）のうちの１つであるＡデータ（ｆ３）（ｆ３は０〜Ｎ−１の整数）が破損しており、且つ、Ｐ２データが破損していない場合に、Ａ（ｆ３）を特定することが可能である。ここで、破損していないＡデータ（ｎ）をＡデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ３以外の整数）と記載する。

図１０Ｄは、一例として、Ａデータ（０）〜Ａデータ（３）のうちＡデータ（１）が破損しており、且つ、Ｐ１データが破損しＰ２データが破損していない様子を示す。この場合、ｆ３＝１であり、ｔは０、２、３である。

Ｓ５１０では、Ａ（ｔ）に基づき、Ｂ（ｔ）を算出する。すなわち、本実施形態おいては、Ａ（０）とＡ（２）とＡ（３）とに基づき、Ｂ（０）とＢ（２）とＢ（３）とを算出する。

Ｓ５２０では、全てのＢ（ｔ）とＰ２との排他的論理和を示すビット列であるＸ３を算出する。
ここで、Ｘ３をＳ（ｆ３）ビット下位側にシフトした値を、Ｘ３´とする。Ｓ５３０では、Ｘ３に基づきＸ３´を算出する。なお、Ｘ３´は、例えば、除算やシフト等により算出される。そして、Ｘ３´の最下位ビットから並ぶｌビットのビット列を、Ａ（ｆ３）として特定する。なお、特定したＡ（ｆ３）を、冗長化データにおけるＡデータ（ｆ３）に設定することで、Ａデータ（ｆ３）が復元されても良い。そして、第３復元処理を終了する。

［３．効果］
本実施形態の誤り訂正プログラムによれば、ガロア体の積演算を用いること無く、排他的論理和等を用いてデータの誤り訂正が行われるので、データの誤り訂正において処理負荷を抑制することができる。また、冗長化データを生成する際には、Ａ（ｎ）をＰ２領域にメモリ転送しながら排他的論理和を行うことで、Ｐ２データが生成される。このため、冗長化データを生成する際の処理負荷を抑制できる。

［４．他の実施形態］
以上、本開示の実施形態について説明したが、本開示は上述の実施形態に限定されることなく、種々変形して実施することができる。

（４ａ）上記実施形態では、Ｓ（ｎ）は、８の倍数に設定されていたが、これに限定されるものではない。Ｓ（ｎ）は、例えば、Ｓ（０）＝２、Ｓ（１）＝８、Ｓ（２）＝０、Ｓ（３）＝４、といったように、８の倍数といったような所定の数の倍数でなく、任意に設定されうる。なお、上記実施形態及びこの例においては、いずれも、ｎとＳ（ｎ）との対応を表すデータが管理データとして含まれる。また、Ｓ（ｎ）にｎの値そのものを用いてもよい。この場合、ｎとＳ（ｎ）との対応を表すデータが管理データとして不要になる。これにより、管理データのための記憶領域を別の用途に活用することができる。

（４ｂ）上述した誤り訂正プログラムにより動作するコンピュータに相当する、誤り訂正装置を構成してもよい。このような場合であっても、誤り訂正プログラムにより得られる効果と同様の効果を得ることができる。

（４ｃ）上記実施形態では、オリジナルデータから生成された冗長化データは、ＨＤＤ２０に対して、１つのコンピュータファイルとして記憶されていたが、これに限定されるものではない。冗長化データは、異なる複数のＨＤＤに対して、ＨＤＤ毎に分割して記憶されうる。また、冗長化データは、パケット単位に分割されて、送受信されうる。

ＨＤＤでは、セクタ単位でデータの書き込みが行われる。データの破損は、これらセクタ単位、パケット単位で発生する可能性が高い。Ａデータ（ｎ）と該Ａデータ（ｎ）から生成されたｈ（ｎ）とを含むデータを、分割ブロックというものとする。分割ブロックの大きさは、セクタ又はパケットの整数倍となるように設定されることが望ましい。つまり、分割ブロックの大きさがセクタ又はパケットの整数倍となるように、Ａデータ（ｎ）のサイズであるＬが設定されることが望ましい。

また、これによれば、分割ブロックの境界と、セクタ又はパケットによる境界とを一致させることができるので、セクタ又はブロックにおけるデータの破損が複数の分割ブロックに渡って影響を与えること、を抑制することができる。

（４ｄ）上記実施形態では、ハッシュ値を付加データとして用いたが、これに限定されるものではない。付加データは、例えば、周知のパリティ符号といったように、Ａデータ（ｎ）、Ｐ１データ、Ｐ２データが破損しているか否かを特定できる情報であればよい。

（４ｅ）上記実施形態では、オリジナルデータを分割して複数のＡデータ（ｎ）を生成し、Ａデータ（ｎ）に基づいてＰ１データ及びＰ２データを生成し、少なくともこれらを含む冗長化データを生成したが、これに限定されるものではない。冗長化プログラムは、例えば、Ａデータ（ｎ）の各々を更に小分割サイズＫ（Ｋ＜Ｌ）に分割するように構成されてもよい。そして、冗長化プログラムは、該小分割サイズＫのデータをＡデータ（ｎ）と見なして、同様に、Ｐ１データ及びＰ２データを生成して記憶するように構成されてもよい。つまり、オリジナルデータに全体に対してＰ１データ及びＰ２データといった２つのパリティが１組だけ生成されるのではなく、オリジナルデータに全体に対してＰ１データ及びＰ２データが複数組生成されてもよい。これによれば、より耐障害性を向上させることができる。

（４ｆ）上記実施形態における１つの構成要素が有する複数の機能を、複数の構成要素によって実現したり、１つの構成要素が有する１つの機能を、複数の構成要素によって実現したりしてもよい。また、複数の構成要素が有する複数の機能を、１つの構成要素によって実現したり、複数の構成要素によって実現される１つの機能を、１つの構成要素によって実現したりしてもよい。また、上記実施形態の構成の一部を省略してもよい。また、上記実施形態の構成の少なくとも一部を、他の上記実施形態の構成に対して付加又は置換してもよい。なお、特許請求の範囲に記載した文言から特定される技術思想に含まれるあらゆる態様が本開示の実施形態である。

［５．特許請求の範囲との対応］
上記実施形態の説明で用いた用語と、特許請求の範囲の記載に用いた用語との対応を示す。冗長化処理（Ｓ１１０〜Ｓ１６０）が生成部に相当し、Ｓ２１０が特定部に相当し、Ｓ２１５〜Ｓ２５０が復元部に相当する。

１…ＰＣ、１０…ディスプレイ、２０…ＨＤＤ、３０…ＣＰＵ、４０…ＲＯＭ、５０…ＲＡＭ、６０…入力装置。

Claims (5)

1. ビット長がｌであるＮ個（Ｎは２以上の整数）のＡデータ（ｎ）（ｎは０〜Ｎ−１の整数）から冗長化データを生成すると共に、前記冗長化データから前記Ａデータ（ｎ）を生成する装置としてコンピュータを動作させる誤り訂正プログラムであって、
   ２進数で表した値における０又は１の値の並びを、ビット列とし、
   前記Ａデータ（ｎ）が示す前記ビット列を、Ａ（ｎ）とし、
   前記Ａ（ｎ）の各々に対応する整数であって、各整数は他の整数とは異なる値を有する整数を、Ｓ（ｎ）とし、前記Ｓ（ｎ）の最大値をＳｍａｘとし、
   前記Ａ（ｎ）に対応しており、ビット長が前記Ｓｍａｘと前記ｌとを加算した値である前記ビット列を、Ｂ（ｎ）とし、前記Ｂ（ｎ）は、前記Ｓ（ｎ）を指数として２を累乗した値と、前記Ａ（ｎ）が示す値とを乗算した値を示し、
   全ての前記Ａ（ｎ）の排他的論理和を示す前記ビット列であるＰ１を示すデータを、Ｐ１データとし、全ての前記Ｂ（ｎ）の排他的論理和を示す前記ビット列であるＰ２を示すデータを、Ｐ２データとし、
   前記Ａデータ（ｎ）に基づき前記Ｐ１データ及び前記Ｐ２データを生成し、前記Ａデータ（ｎ）、前記Ｐ１データ、及び、前記Ｐ２データの各々について、当該データの誤りを検出するための付加データを生成し、前記Ａデータ（ｎ）、前記Ｐ１データ、前記Ｐ２データ、及び、前記付加データを、前記冗長化データとする生成部と、
   前記冗長化データに含まれる前記付加データに基づき、該冗長化データに含まれる前記Ａデータ（ｎ）、前記Ｐ１データ、及び、前記Ｐ２データのうちの破損しているデータを特定する特定部と、
   前記冗長化データにおいて、前記Ａデータ（ｎ）のうちの２つが破損しており、且つ、前記Ｐ１データ及び前記Ｐ２データが破損していない場合に、前記冗長化データに基づき、破損している２つの前記Ａデータ（ｎ）を復元する復元部として、コンピュータを動作させ、
   破損している２つの前記Ａデータ（ｎ）のｎの値を、ｆ０、ｆ１（ｆ０、ｆ１は０〜Ｎ−１の整数）とし、破損していない前記Ａデータ（ｎ）のｎの値を、ｔ（ｔは、０〜Ｎ−１の整数であって、ｆ０、ｆ１以外の整数）とし、
   前記Ａ（ｆ０）と前記Ａ（ｆ１）との排他的論理和を示す前記ビット列を、Ｘ０とし、
   前記Ｂ（ｆ０）と前記Ｂ（ｆ１）との排他的論理和を示す前記ビット列を、Ｘ１とし、
   前記Ｂ（ｆ０）において、当該Ｂ（ｆ０）に含まれる前記Ａ（ｆ０）の最下位ビット、最上位ビットに相当するビットの位置を、それぞれ、ｂｌ、ｂｍとし、前記Ｘ１における前記ｂｌから前記ｂｍまでの前記ビット列を、Ｘ１Ａとし、
   前記復元部は、
   全ての前記Ａ（ｔ）と前記Ｐ１との排他的論理和を算出することで、前記Ｘ０を算出し、
   前記Ａ（ｔ）に基づき算出された全ての前記Ｂ（ｔ）と前記Ｐ２との排他的論理和に基づき、前記Ｘ１Ａを算出し、
   前記Ｓ（ｆ０）と前記Ｓ（ｆ１）との差の絶対値を指数として２を累乗した値を、Ｓとし、
   前記Ａ（ｆ１）が示す値を前記Ｓで除算した値を示す、ビット長が前記ｌである前記ビット列、又は、前記Ａ（ｆ１）が示す値を前記Ｓで乗算した値を示す前記ビット列における、最下位ビットから並ぶビット長が前記ｌである前記ビット列を、Ａ´（ｆ１）とし、
   前記Ｘ０と前記Ｘ１Ａとの排他的論理和を算出することで、前記Ａ（ｆ１）と前記Ａ´（ｆ１）との排他的論理和であるＸ２を算出し、
   前記Ｘ２に基づき前記Ａ（ｆ１）を特定し、特定した前記Ａ（ｆ１）と、前記Ｐ１又は前記Ｐ２とに基づき、前記Ａ（ｆ０）を特定し、特定した前記Ａ（ｆ０）及び前記Ａ（ｆ１）に基づき、前記Ａデータ（ｆ０）及び前記Ａデータ（ｆ１）を復元する
   誤り訂正プログラム。
2. 請求項１に記載の誤り訂正プログラムであって、
   前記復元部は、
   前記Ａデータ（ｎ）のうちの１つである前記Ａデータ（ｆ２）（ｆ２は０〜Ｎ−１の整数）が破損しており、且つ、前記Ｐ１データが破損していない場合に、
   破損していない前記Ａデータ（ｎ）を前記Ａデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ２以外の整数）とし、
   全ての前記Ａ（ｔ）と前記Ｐ１との排他的論理和を前記Ａ（ｆ２）として算出し、算出した前記Ａ（ｆ２）に基づき前記Ａデータ（ｆ２）を復元する
   誤り訂正プログラム。
3. 請求項１又は請求項２に記載の誤り訂正プログラムであって、
   前記復元部は、
   前記Ａデータ（ｎ）のうちの１つである前記Ａデータ（ｆ３）（ｆ３は０〜Ｎ−１の整数）が破損しており、且つ、前記Ｐ２データが破損していない場合に、
   破損していない前記Ａデータ（ｎ）を前記Ａデータ（ｔ）（ｔは、０〜Ｎ−１の整数であって、ｆ３以外の整数）とし、
   全ての前記Ｂ（ｔ）と前記Ｐ２との排他的論理和を前記Ｂ（ｆ３）として算出し、算出した前記Ｂ（ｆ３）に基づき前記Ａデータ（ｆ３）を復元する
   誤り訂正プログラム。
4. 請求項１から請求項３のいずれか１項に記載の誤り訂正プログラムであって、
   前記冗長化データを１つのコンピュータファイルとして出力する
   誤り訂正プログラム。
5. ビット長がｌであるＮ個（Ｎは２以上の整数）のＡデータ（ｎ）（ｎは０〜Ｎ−１の整数）から冗長化データを生成すると共に、前記冗長化データから前記Ａデータ（ｎ）を生成する装置としてコンピュータを動作させる誤り訂正装置であって、
   ２進数で表した値における０又は１の値の並びを、ビット列とし、
   前記Ａデータ（ｎ）が示す前記ビット列を、Ａ（ｎ）とし、
   前記Ａ（ｎ）の各々に対応する整数であって、各整数は他の整数とは異なる値を有する整数を、Ｓ（ｎ）とし、前記Ｓ（ｎ）の最大値をＳｍａｘとし、
   前記Ａ（ｎ）に対応しており、ビット長が前記Ｓｍａｘと前記ｌとを加算した値である前記ビット列を、Ｂ（ｎ）とし、前記Ｂ（ｎ）は、前記Ｓ（ｎ）を指数として２を累乗した値と、前記Ａ（ｎ）が示す値とを乗算した値を示し、
   全ての前記Ａ（ｎ）の排他的論理和を示す前記ビット列であるＰ１を示すデータを、Ｐ１データとし、全ての前記Ｂ（ｎ）の排他的論理和を示す前記ビット列であるＰ２を示すデータを、Ｐ２データとし、
   前記Ａデータ（ｎ）に基づき前記Ｐ１データ及び前記Ｐ２データを生成し、前記Ａデータ（ｎ）、前記Ｐ１データ、及び、前記Ｐ２データの各々について、当該データの誤りを検出するための付加データを生成し、前記Ａデータ（ｎ）、前記Ｐ１データ、前記Ｐ２データ、及び、前記付加データを、前記冗長化データとする生成部と、
   前記冗長化データに含まれる前記付加データに基づき、該冗長化データに含まれる前記Ａデータ（ｎ）、前記Ｐ１データ、及び、前記Ｐ２データのうちの破損しているデータを特定する特定部と、
   前記冗長化データにおいて、前記Ａデータ（ｎ）のうちの２つが破損しており、且つ、前記Ｐ１データ及び前記Ｐ２データが破損していない場合に、前記冗長化データに基づき、破損している２つの前記Ａデータ（ｎ）を復元する復元部と、を備え、
   破損している２つの前記Ａデータ（ｎ）のｎの値を、ｆ０、ｆ１（ｆ０、ｆ１は０〜Ｎ−１の整数）とし、破損していない前記Ａデータ（ｎ）のｎの値を、ｔ（ｔは、０〜Ｎ−１の整数であって、ｆ０、ｆ１以外の整数）とし、
   前記Ａ（ｆ０）と前記Ａ（ｆ１）との排他的論理和を示す前記ビット列を、Ｘ０とし、
   前記Ｂ（ｆ０）と前記Ｂ（ｆ１）との排他的論理和を示す前記ビット列を、Ｘ１とし、
   前記Ｂ（ｆ０）において、当該Ｂ（ｆ０）に含まれる前記Ａ（ｆ０）の最下位ビット、最上位ビットに相当するビットの位置を、それぞれ、ｂｌ、ｂｍとし、前記Ｘ１における前記ｂｌから前記ｂｍまでの前記ビット列を、Ｘ１Ａとし、
   前記復元部は、
   全ての前記Ａ（ｔ）と前記Ｐ１との排他的論理和を算出することで、前記Ｘ０を算出し、
   前記Ａ（ｔ）に基づき算出された全ての前記Ｂ（ｔ）と前記Ｐ２との排他的論理和に基づき、前記Ｘ１Ａを算出し、
   前記Ｓ（ｆ０）と前記Ｓ（ｆ１）との差の絶対値を指数として２を累乗した値を、Ｓとし、
   前記Ａ（ｆ１）が示す値を前記Ｓで除算した値を示す、ビット長が前記ｌである前記ビット列、又は、前記Ａ（ｆ１）が示す値を前記Ｓで乗算した値を示す前記ビット列における、最下位ビットから並ぶビット長が前記ｌである前記ビット列を、Ａ´（ｆ１）とし、
   前記Ｘ０と前記Ｘ１Ａとの排他的論理和を算出することで、前記Ａ（ｆ１）と前記Ａ´（ｆ１）との排他的論理和であるＸ２を算出し、
   前記Ｘ２に基づき前記Ａ（ｆ１）を特定し、特定した前記Ａ（ｆ１）と、前記Ｐ１又は前記Ｐ２とに基づき、前記Ａ（ｆ０）を特定し、特定した前記Ａ（ｆ０）及び前記Ａ（ｆ１）に基づき、前記Ａデータ（ｆ０）及び前記Ａデータ（ｆ１）を復元する
   誤り訂正装置。

Images