JPH04230124A - マルチレベルエラー訂正システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本願はデータのエラー訂正に関す
るものであり、更に言えばマルチレベルエンコーディン
グ及びデコーディングの改善された技術に関する。

【０００２】

【従来の技術】デジタルコンピュータシステム中のデー
タのエラー訂正コーディングの重要さは、マス記憶メデ
ィア、取り分け磁気ディスク上に記憶されるデータ密度
が増加するにつれ、ますます大きくなっている。より高
いレコード密度を有すると、ディスクの記憶表面のほん
の小さな欠陥が多量のデータをだめにしてしまうことも
ある。データの損失を防ぐため、エラー訂正コード（Ｅ
ＣＣ）はその名が意味するように間違ったデータを訂正
するために使用される。

【０００３】データ記号のストリングがディスクに記憶
される前に、ＥＣＣ即ち冗長、記号を形成するよう、数
学的にエンコードされる。冗長記号はその後、コードワ
ード、データ記号に冗長記号を加えたもの、を形成する
ようデータストリングにアペンドされる。そのストアさ
れたデータがディスクからアクセスされるべき場合には
、データ記号を含有するそれらのコードワードがディス
クから検索され、そして数学的にデコードされる。デコ
ーディングの間に、データ内になんらかのエラーが検出
されると、もし可能ならば、冗長記号の操作を行い訂正
される（デコーディングについてのより詳しい記述は、
Ｐｅｔｅｒｓｏｎ、Ｗｅｌｄｏｎによるエラー訂正コー
ドの第２版、ＭＩＴ出版社、１９７２にある）。

【０００４】ストアされたデジタルコードワードは、マ
ルチエラーを含んでいることもある。マルチエラーの訂
正に使用される最も効果的なＥＣＣタイプの１つは、リ
ードソロモンコードである（リードソロモンコードの詳
細な記述は、Ｐｅｔｅｒｓｏｎ、Ｗｅｌｄｏｎによるエ
ラー訂正コードにある）。リードソロモンＥＣＣのため
のエラー検出及び訂正技術はよく知られている。同前。 このような技術の１つは、コードワードデータをエンコ
ードして新しい冗長記号の組みを発生し、そしてこの冗
長記号の組みを、検索されたコードワード内の冗長記号
、つまりデータの前記憶エンコーディングによって発生
された冗長記号の組みと比較し、検索されたコードワー
ド内のなんらかのエラーを検出するというものである（
このエラー訂正技術についての詳細な記述は、Ｒｉｇｇ
ｌｅとＷｅｎｇに付与された米国特許第４，４１３，３
３９　号にある）。

【０００５】ストアさたデータ内のエラーは、時々マル
チ記号バーストのようなパターンで現れる。このような
エラーは、例えば記憶媒体内の欠陥によって引き起こさ
れるかもしれない。様々なエンコーディング及びデコー
ディングスキームが一般のエラーパターンを訂正するた
めに開発された。バーストのために開発されたスキーム
の１つは、インタリーブである。インタリーブは、ＥＣ
Ｃを使用することによってデータを多数のセクションに
分離し、コードワードを形成するために各セクションを
別個にエンコーディングするものである。各コードワー
ドはこのように、データのセクション及び冗長記号の関
連する組みを含む。全セクションからのインタリーブさ
れたデータ及び冗長記号がその後記憶される。一般に、
インタリーブされたデータ記号は、連続的に記憶され、
その後ろに冗長記号が続く。多数の隣接する（インタリ
ーブされた）データ記号に影響を与えるバーストエラー
は、幾つかのコードワードの各々に小さな多数のエラー
を引き起こす。

【０００６】データ及び冗長記号が後に検索された場合
には、冗長記号の様々な組みがそれに関連するデータセ
クション内のエラーを訂正するために使用される。この
ように、冗長記号の所定の組みがデータの部分を保護し
、且つ何らかのエラーバーストの部分だけを恐らく訂正
する。それ故、「ｘ」個の間違った記号を訂正するよう
設計されているＥＣＣは、それらをセクション毎に訂正
することによってｘ個の記号よりも長いバーストを訂正
することが出来るのである。このようなスキームのため
に選択されたＥＣＣは、バーストエラーを部分部分に分
けることなく訂正しなければならないものよりも、より
パワフルではないものとなり得る。あまりパワフルでは
ないＥＣＣを用いることの利点は、エンコーディング及
びデコーディングハードウエアをより単純なものとし、
（一般に）訂正を早くするということである。（インタ
リーブエンコーディングの詳細な記述は、Ｐｅｔｅｒｓ
ｏｎ、Ｗｅｌｄｏｎによるエラー訂正コードにある）。

【０００７】一般のエラーパターンを訂正するために用
いられる他のスキームは、マルチレベルエンコーディン
グである。マルチレベルエンコーディングには、ＥＣＣ
、及び／または、最も一般的なエラーパターンを訂正す
るように設計された技術を用いることにより一旦データ
をエンコードし、次に、他のＥＣＣ、及び／または、次
に一般的なエラーパターンを訂正するよう設計された技
術を使用してエンコードする等といったことが含まれる
。マルチレベルデコーディングには、第１のレベルのＥ
ＣＣあるいは技術を用いてデータを訂正し、もしエラー
が残っている場合には、第２のレベルのＥＣＣあるいは
技術を用いてそれらを訂正する等といったことが含まれ
る。

【０００８】例えば、エンコーディングの第１レベルは
、比較的弱いＥＣＣを用いてデータをエンコーディング
するといっことからなるであろう。第２レベルのエンコ
ーディングは、よりパワフルなＥＣＣを用いてそのデー
タを再びエンコーディングするといったことからなるで
あろう。このような２レベルのスキームは、Ｐａｔｅｌ
　に付与された米国特許第４，７０６，２５０　号及び
第４，５２５，８３８　号に開示されている。２つの特
許に開示されているＰａｔｅｌ　スキームは、まず初め
にｅａ　個のエラーを訂正するＥＣＣを使用してデータ
をエンコードする。Ｐａｔｅｌ　はデータのブロックを
「ｉ」個のセクション、あるいは、「ｋ」個の記号のサ
ブブロックに分離し、個々別々に、個々のｋ個の記号セ
クションを第１のＥＣＣを用いてエンコードする。エン
コーディングのこのレベルは、各データセクションのた
めに「ｐ」個の冗長記号を発生する、即ち、合計で「ｉ
ｐ」個の冗長記号を発生する。

【０００９】Ｐａｔｅｌ　は次に、各サブブロック内の
対応するデータ記号を足し合わせ（排他ＯＲを実行し）
、その結果生じたｋ個の記号を付加的な「データ」セク
ションとして取り扱う。Ｐａｔｅｌ　はその後、ｅ　ｂ
　個のエラー（ｅ　ｂ　≧ｅａ　）まで訂正することが
出来るよりパワフルなＥＣＣを用いてこれらの記号をエ
ンコードする。この第２エンコーディングは、「ｓ」個
の付加的な冗長記号を発生する。Ｐａｔｅｌ　はこのデ
ータ及び、この２レベルのエンコーディングの間に発生
した冗長記号であるｉｐ及びｓ　個の冗長記号をストア
する。ｋ個の付加的な「データ」記号はストアしない。

【００１０】Ｐａｔｅｌ　スキームは、個々のサブブロ
ック内で第１レベル、即ちレベル−１、ＥＣＣを用いて
ｅａ　個のエラーまで訂正することが出来、そしてレベ
ル−２ＥＣＣを用いていづれか１つのサブブロック内で
ｅ　ｂ　個のエラーまで訂正することが出来る。それ故
Ｐａｔｅｌ　は、まずレベル−１ＥＣＣを用いてデータ
内のなんらかのエラーを訂正しようと試みるのである。 もし、全てのエラーがこのＥＣＣを使用することによっ
て訂正されたならば、かれはエラー訂正デコーディング
動作を中止し、レベル−２ＥＣＣは使用しない。もし１
つのサブブロックを除いて全てが訂正されたならば、そ
のレベル−２コードは、それを訂正するために使用され
る。Ｐａｔｅｌはこのように、エンコーディングの間に
発生されたｋ個の記号の付加的なデータセクションに対
応するｋ個の「データ」記号を形成するため、レベル−
１ＥＣＣを用いて訂正された記号及び、レベル−１コー
ドが訂正しなかった間違った記号を含む各セクション内
の対応するデータ記号に排他ＯＲを実行する。Ｐａｔｅ
ｌ　はその後、これらのｋ個の記号のエラーをレベル−
２コードを用いて訂正しようと試みる。

【００１１】もしｅ　ｂ　個あるいはそれ以下のエラー
が存在する場合には、レベル−２コードはｋ個の記号「
データ」セクション内の間違った記号のロケーションを
判断し、そしてそれに関連するエラー値、即ち、それら
を訂正するために間違った記号を排他ＯＲされなければ
ならない記号を発生する。Ｐａｔｅｌ　はそのエラーロ
ケーションをエラーを含むサブブロックに変換し、そし
てそれらを発生させたエラー値記号を用いて訂正する。

【００１２】もしデータが、サブブロック毎にｅ　ｂ　
個のエラー以上を含んでいた場合、あるいはｅａ　個の
エラー以上を有する１つ以上のサブブロックを含んでい
た場合には、Ｐａｔｅｌ　スキームはそれらのエラーを
訂正することが出来ない。このように、レコード密度が
増加してエラーが発生すればする程、より多くのエラー
を訂正し得るエラー訂正スキームを使用することが望ま
しい。

【００１３】１つの解決法は、よりパワフルなＥＣＣを
各レベルで用いるというものである。これは３つの問題
を作り出す。第１に、よりパワフルなＥＣＣは付加的な
冗長記号を発生するということである。この結果、デー
タに対してより多くの記憶空間をアロケートしなければ
ならなくなり、所定の記憶空間に記憶可能なデータが少
なくなってしまう。第２に、よりパワフルなＥＣＣを必
要とすれば、それはより複雑なものとなり、その結果、
エンコーディング及びデコーディングハードウエア、及
び／または、ソフトウエアが、より高価なものとなって
しまうのである。第３に、より少ない冗長記号を用いる
ＥＣＣよりも、エラーを訂正するためにより多くの時間
を必要とすることである。

【００１４】データ転送技術が発達し、ディスクから検
索されるスピードが増加するのに伴って、より遅いより
複雑なＥＣＣが、データが転送されることが出来る速度
の限界となってしまう。それ故、エラーを素早く訂正す
ることが出来るよりパワフルなエンコーディングスキー
ムが容易に実行され、そして余計な記憶空間量を必要と
しないことということが必要とされるのである。

【００１５】

【発明の概要】本発明は、マルチレベルエンコーディン
グスキームである。このマルチエンコーディングスキー
ムは、より高いエンコーディングレベルで、全てのレベ
ルが共にパワフルでしかも素早いエラー訂正スキームを
形成するようなエンコーディングの第１レベルの間に発
生された冗長記号を使用する。このマルチエンコーディ
ングスキームは、全ての冗長記号を保持する必要はない
。なぜなら、以下に説明するように、これらの記号を規
定数の保持された記号から再発生させることが出来るか
らである。

【００１６】本発明のマルチレベルエンコーディングス
キームは、まず初めにデータを、各々「ｋ」個の記号の
「ｉ」個のセクション、つまりｉ個のサブブロックに分
離し、各サブブロックを（ｎ，ｋ）ＥＣＣを用いてエン
コードする。このデータ記号はインタリーブされている
かもしれないし、されていないかもしれない。このエン
コーディングの第１レベルは個々のｋデータ記号のため
に、「ｎ−ｋ」あるいは「ｒ」冗長記号、あるいは総計
で「ｒｉ」個の冗長記号を含んでいる「ｎ」個の記号コ
ードワードを発生する。

【００１７】このシステムは次に、これらのｒｉ個の冗
長記号を「ｍ」個のマルチ記号セクション、即ち、個々
のｉ個のコードワードからの対応する記号を含むＲ（１
）、Ｒ（２）、・・・Ｒ（ｍ）に分割する。このシステ
ムはその後、これら個々のセクションを同一のＥＣＣ、
あるいはより好ましくは減少した強さのＥＣＣのいずれ
かを用いてエンコードする。このようにしてそれは、例
えばそれは各ｉレベル−１コードワードからの第１の冗
長記号、Ｗｊ＋１　をエンコードし、ｑ２　冗長記号を
発生し、これらのＷｊ＋１　冗長記号とｑ２　はレベル
−２コードワードを形成している冗長を発生する記号を
発生する。次にそれは個々のｉ個のコードワードから第
２冗長記号Ｗｊ＋２　をエンコードし、そして第２レベ
ル−２コードを形成する他のｑ２　冗長記号を発生する
、等である。 様々なセクションＲ（２）・・・Ｒ（ｍ）に対応するレ
ベル−２冗長記号は、それぞれセクションＱ（２）・・
・、Ｑ（ｍ）にある。このシステムはその後、そのデー
タ、セクションＲ（１）冗長記号及びセクションＱ（２
）・・・、Ｑ（ｍ）冗長記号を記憶する。しかしながら
それはセクションＲ（２）・・・Ｒ（ｍ）内の冗長記号
は記憶しない。なぜなら以下に述べるように、記憶され
たＲ（１）及びＱ（２）・・・、Ｑ（ｍ）冗長記号を用
いてこれらの記号を再発生することが出来るからである
。

【００１８】データが記憶から検索された場合、それは
レベル−１ＥＣＣを用いてコードワード毎にデコードさ
れる。このシステムは、その検索されたセクションＲ（
１）記号を冗長記号として用い、そしてそれらの「失わ
れている」セクションＲ（２）・・・Ｒ（ｍ）記号を消
去エラーとして取り扱う。レベル−１ＥＣＣはこのよう
に、各レベル−１コードのためにセクションＲ（２）・
・・Ｒ（ｍ）内の冗長記号内を満たし、またもし可能な
らば、検索されたデータ及びセクションＲ（１）冗長記
号中のなんらかのエラーを訂正するために用いられる。 もしレベル−１デコーディングが、冗長記号として検索
されたセクションＲ（１）記号だけを用いて全てのエラ
ー及び消去を訂正しなければ、このシステムはセクショ
ンＱ（２）冗長記号及びレベル−２ＥＣＣを用いて、失
われているセクションＲ（２）冗長記号内を満たす。次
に、このシステムは、レベル−１ＥＣＣ及びセクション
Ｒ（１）及びＲ（２）内の検索されそして満たされた冗
長記号を用いて、対応するレベル−１コードワードを訂
正しようとする。もし必要ならば、このシステムは次の
セクション、つまりセクションＲ（３）内のいづれかの
訂正されていない冗長記号内を、セクションＱ（３）及
びレベル−３ＥＣＣを用いて満たす。その後、レベル−
１ＥＣＣ及びセクションＲ（１）、Ｒ（２）及びＲ（３
）内の冗長記号を用いて、データ内のエラーを更に訂正
する。

【００１９】

【実施例】図１を参照すれば、システム（図示されてい
ない）は「ｋｉ」個のデータ記号のストリングを、「ｉ
」個のセクション、あるいは各々が「ｋ」個の記号であ
るサブブロックに分離している。このシステムは初めに
それらｋｉ個のデータ記号をインタリーブしてもよい。 これらのｉ個のセクションは図において列として配列さ
れている。このシステムはまず初めに（ｎ，ｋ）ＥＣＣ
及び従来技術を用いて第１レベル−エンコーディングを
実行し、「ｎ−ｋ」あるいは「ｒ」冗長記号を含むレベ
ル−１コードワードを形成するためにデータの各セクシ
ョンをエンコードする。このコードワードは、図の配列
の、列ｃ１　、ｃ２　、・・・ｃｉ　に対応する。この
システムはこのように、「ｒｉ」個の冗長記号をエンコ
ーディングの第１レベルで発生する。

【００２０】システムは次に、これらの「ｒｉ」個の冗
長記号を、任意のサイズである、実施例ではｍ＝３であ
るが、ｍセクション１２〜１６、Ｒ（１）、Ｒ（２）、
・・・・Ｒ（ｍ）に分離する。個々のセクションは、好
ましくは、１つの間違ったデータ記号を訂正するために
必要とされうる記号の数である少なくとも２つの冗長記
号を含んでいる。このように、各セクション１２〜１６
は、図示された配列の中に少なくとも２つの行を含む。

【００２１】図２を参照すれば、このシステムはＲ（２
）内のそれらの記号を、エンコーディングの第２のレベ
ルを用いてセクションにエンコードしている。それはこ
のように、個々のｉ個のコードワードからの対応する冗
長記号を「情報」記号として、即ち、各行、セクション
Ｒ（２）の「Ｗａ　」を第２ＥＣＣを用いてエンコード
する。このエンコーディングの第２レベルは、セクショ
ンＲ（２）の各行Ｗｊ＋１　、・・・、Ｗｐ　のために
「ｑ２　」個の冗長記号を発生する。ｉ個の情報記号及
びｑ２　個の冗長記号を含んでいる各行は、レベル−２
コードワードを形成する。このシステムはこのように、
エンコーディングのこのレベルに、総計（ｐ−ｊ＋１）
ｑ２　個の冗長記号を発生する。これらの記号は、図で
はセクションＱ（２）として示されている。一般に、セ
クションＱ（２）内の記号の数は、セクションＲ（２）
内の記号の数よりも小さい。

【００２２】このシステムは次に、セクションＲ（３）
内の記号を同様にエンコーディングすることにより、第
３のエンコーディングのレベルを実行する。それはこの
ように、ＥＣＣを用いることにより、個々のｉ個のコー
ドワードからの対応する冗長記号をエンコードする。こ
こでこのＥＣＣは、好ましくは、レベル−２コードより
も力が弱いものである。エンコーディングの第３のレベ
ルは、各行Ｗｐ＋１　、Ｗｐ＋２　、・・・・、Ｗｒ　
のために「ｑ３　」個の冗長記号を発生する。ｉ個の「
情報」記号及びｑ３　個の冗長記号を含む」各行は、レ
ベル−３コードワードを形成する。このシステムはこの
ように、エンコーディングのこのレベルで、総計（ｒ−
ｐ＋１）ｑ３　個の冗長記号を発生する。これらの記号
は、図にセクションＱ（３）として示されている。一般
に、セクションＱ（３）内の記号の数は、セクションＲ
（３）内の記号の数よりも小さい。

【００２３】図３を参照すれば、このシステムは、メモ
リ（図示されていない）内にｋｉ個のデータ記号、セク
ションＲ（１）、Ｑ（２）及びＱ（３）冗長記号をスト
アする。しかしながらシステムは、セクションＲ（２）
及びＲ（３）冗長記号はストアしない。なぜなら、これ
らの記号は、ストアされたセクションＲ（１）、Ｑ（２
）及びＱ（３）冗長記号を用いて再発生させることが可
能だからである。セクションＲ（２）及びＲ（３）記号
はこのように、意識的に「削除」される。削除された個
々の記号はデコーディングの間、削除として、つまり既
知のロケーションを有するエラーとして取り扱われる。

【００２４】このシステムはまた、ストアされたセクシ
ョンＲ（１）、Ｑ（２）・・・Ｑ（ｍ）冗長記号を任意
に、冗長記号ＥＣＫ（１）、ＥＣＫ（２）及びＥＣＫ（
３）を発生する１つ以上のＥＣＣを用いてエンコードす
ることも出来る。これらの記号はその後、データ及びセ
クションＲ（１）、Ｑ（２）及びＱ（３）冗長記号と共
にストアされる。デコーディングの間、これら（任意の
）冗長記号は、それらの冗長記号を削除された記号を再
発生するために用いる前に、ストアされた冗長記号内の
いづれかのエラーを訂正するために使用されることも出
来る。それら任意の記号はこのように、それらのストア
された記号及び削除された記号のために付加された保護
層である。

【００２５】これらのデータ記号は、ｍレベルのエンコ
ーディングによって保護されている。冗長記号のｍレベ
ルのために必要とされる記憶空間は、全てのｒｉレベル
−１冗長記号に必要とされるであろう空間よりも小さい
ものである。それ故、このスキームは、従来のマルチレ
ベルエンコーディングスキームよりもより多くの保護を
提供するが、記憶空間の使用はより少ないのである。

【００２６】従来、当業者によって理解されていたのと
同様、これらのデータ及び冗長記号は、どのようなフォ
ーマットにでもストアし、記憶される。図に示されたブ
ロックフォーマットは、単なる例示に過ぎない。ストア
された情報が後に検索された場合、システムは検索され
たセクションＲ（１）冗長記号を使用して、各コードワ
ードのために、従来のエラー及び削除訂正技術を用いて
「削除」されたセクションＲ（２）、Ｒ（３）レベル−
１冗長記号を再発生する。それはまたセクションＲ（１
）冗長記号を検索されたデータ及び冗長記号内のエラー
を訂正するために使用する。図４は、例えばｃ１　、ｃ
２　といった幾つかの再発生された列を示している。

【００２７】もしシステムが特定のデータのセクション
、つまり特定の列のために有効なコードワードを発生し
なかった場合には、それは関連するセクションＲ（２）
及びＲ（３）記号を、　　えば列ｃｅ１、ｃｅ２、ｃｅ
ｆといった既知のロケーションを有するエラーとして取
り扱う。それはその後、セクションＲ（２）の各行を適
当なセクションＱ（２）冗長記号及びレベル−２ＥＣＣ
を用いてデコードし、そして列ｃｅ１、ｃｅ２・・・ｃ
ｅｗ内の削除されたセクションＲ（２）記号を適切に満
たす。システムは次に、検索されたデータ及びこれらの
列のセクションＲ（１）記号内のいづれかの残りのエラ
ーを、レベル−１ＥＣＣ及び適当なセクションＲ（１）
及びＲ（２）冗長記号を用いて訂正しようと試みる。

【００２８】もしシステムが、レベル−１ＥＣＣ及びセ
クションＲ（１）及びＲ（２）冗長記号を用いても全て
のエラーを訂正し且つ全ての削除された冗長記号を再発
生することが出来ない場合には、セクションＱ（３）冗
長記号及びレベル−３ＥＣＣを用いてなんらかの誤りの
あるセクションＲ（３）記号を満たす。その後、記号内
に満たされたこれらと、レベル−１ＥＣＣを有するセク
ション（１）及びＲ（２）冗長記号を使用して更にエラ
ーを訂正する。もし必要ならば、そしてもしさらにレベ
ルが存在する場合には、システムはそのようなレベルの
各々ために訂正手続きを繰り返す。

【００２９】システムが削除されたセクションＲ（２）
、Ｒ（３）記号を再発生する前に、検索されたセクショ
ンＲ（１）、Ｑ（２）及びＱ（３）冗長記号内の何らか
のエラーを訂正するため、それは任意のＥＣＣ記号を使
用する。次にシステムはレベル−１エラー及び削除訂正
を実行し、削除された冗長記号内を満たし、そしてセク
ションＲ（１）冗長記号内の検索されたデータのエラー
を訂正する。その後、それらのエラーを訂正するために
上で述べた手続きが続く。

【００３０】システムがより高いレベルのデコーディン
グを実行した場合には、それは誤ったデータを発見する
だろう。システムはこのように、そのデータに誤りがあ
るシステムオペレータに信号を送ることも出来、そうし
てそのシステムオペレータはその後に記憶されている媒
体を検査し、回復不可能な程損失してしまう前にストア
されたデータを救助することも出来る。たった２つのデ
コーディングのレベルだけを用いる従来のシステムでは
、誤りのあるデータについてこのように警告されること
はなく、結局は誤った媒体としてデータを喪失してしま
うであろう。

【００３１】図５及び図６は、存在する１レベルエンコ
ーディングシステムと関連して用いられ得る本発明の第
２実施例である。１レベルシステムは、そのｋｉ個のデ
ータ記号を、それらを（任意的に）インタリーブした後
にエンコードする。それは、ｋ記号セクション内のそれ
らをエンコーダ１８内でエンコードし、連続的なルート
ジェネエイタ多項式ｇ１（ｘ）：（ｘ＋αａ　）＊（　
ｘ＋αａ＋１）＊（ｘ＋αａ＋２）＊（ｘ＋αａ＋３）
＊　・・・＊（ｘ＋αａ＋ｓ　）　を有するＥＣＣに従
ってコードワードを形成する。ここで＊は、ガロア域積
であり、αはデータをエンコードするために用いられる
ガロア域ＧＦ（２ｔ　）の根本となる多項式である。

【００３２】このコードワードはｋ個のデータ記号及び
ｓ個の冗長記号を含み、そして図６の列１０として配列
されており、図中でセクションｓ（１）として描かれた
全てのコードワードのためのｓｉ個の冗長記号を有する
。これらのコードワードはエンコーディングの第２のレ
ベルのため、次に第２エンコーダに与えられる。このエ
ンコーディングのレベルは、ジェネレイタ多項式として
、ｇ１（ｘ）を拡張したバージョンであるｇ２（ｘ）：
（ｘ＋αａ−ｄ　）＊（　ｘ＋αａ−ｄ＋１）＊　・・
・＊（ｘ＋αａ　）＊・・・＊（ｘ＋αａ＋ｓ　）＊（
　ｘ＋αａ＋ｓ＋１）＊　・・・＊（ｘ＋αａ＋ｓ＋ｄ
　）　 を有するＥＣＣに関連している。

【００３３】この第２ＥＣＣはよりパワフル、即ちそれ
はｇ１（ｘ）と関連したＥＣＣよりもより多くの所定の
データ量内のエラーを訂正するものである。データ記号
は、セクションｓ（１）冗長記号を作り出すために、１
レベルエンコーダ１８によって既にｇ１（ｘ）に従って
エンコードされている。故に、このコードワードデータ
記号及びｓ（１）冗長記号は情報記号として取り扱われ
、そしてこの第２エンコーダ２０は実際には、ｇ１（ｘ
）の部分ではないｇ２（ｘ）のファクタにしたがってそ
れらの記号をエンコードする。このようなエンコーダ２
０は、それらの記号をｇ２（ｘ）／ｇ１（ｘ）に等しい
多項式ｇ＊２（　ｘ）にしたがってエンコードする。こ
の第２のエンコーディングは、個々のコードワードのた
めに、図６のセクションｓ（２）として示された冗長記
号を発生する。 セクションｓ（２）冗長記号は、データに対して単独で
は適切なエラー保護を与えることはない。なぜなら、そ
れらを発生するために使用されう多項式ｇ＊２（　ｘ）
が、ｇ１（ｘ）を同じ位多くの連続したルートをＧＦ（
２ｔ　）内に持たないからである。しかしながら、セク
ションｓ（２）記号は、対応するセクションｓ（１）記
号と共に、ジェネレイタ多項式ｇ２（ｘ）として保持し
ている比較的パワフルなＥＣＣを用いてそれらのデータ
記号を保護する。

【００３４】エンコーディングの第３、第４、・・・、
ｍレベルは同一の方法で実行される。エンコーディング
の第３レベルは、例えばジェネレイタ多項式ｇ＊３（　
ｘ）＝ｇ３（ｘ）／ｇ２（ｘ）を使用する。ここで、ｇ
３（ｘ）はｇ２（ｘ）の拡張されたバージョンである。 このように、これらのレベルのエンコーダ、例えばｍレ
ベルエンコーディングのためのエンコーダ２２は、それ
らのデータ記号及び対応するセクションｓ（１）・・・
ｓ（ｍ−１）冗長記号を、多項式ｇ＊　ｍ　（　ｘ）に
従ってエンコードする。このｇ＊　ｍ　（　ｘ）は、ｇ
ｍ−１　（ｘ）の拡張されたバージョンであるｇｍ　（
ｘ）を、前のレベルに関連するジェネレイタ多項式、ｇ
ｍ−１　（ｘ）によって割り算をした商に等しい。レベ
ル−ｍジェネレイタ多項式はこのように、連続するルー
トを含み、また、そのデータをさらにパワフルなＥＣＣ
で保護する。

【００３５】エンコーディングの各レベルに対して発生
された冗長記号が、図６のセクションＳ（１）・・・Ｓ
（ｍ）に示されている。これらの冗長記号セクションは
、図２のセクションＲ（１）・・・Ｒ（ｍ）に対応する
。図６を再び参照すれば、セクションＳ（１）・・・Ｓ
（ｍ）内の冗長記号は、この実施例ではｍ＝３であるが
、その後情報記号としてエンコードされ、図３を参照し
て上で記述したセクションＱ（２）及びＱ（３）内に示
された冗長記号を発生する。

【００３６】データ及びレベル−２及び３冗長記号がエ
ンコードされ、セクションＱ（２）及びＱ（３）内に示
された記号を発生した後、このシステムは更に、セクシ
ョンＱ（２）及びＱ（３）内の冗長記号を１つ以上のＥ
ＣＣを用いエンコードし、そしてＥＣＫ（２）及びＥＣ
Ｋ（３）を発生する。このシステムはその後、これらの
冗長記号、セクションＳ（１）冗長記号及びセクション
Ｑ（２）及びＱ（３）冗長記号をデータ記号と共にスト
アする。しかしながら、セクションＳ（２）及びＳ（３
）冗長記号はストアしない。なぜなら、これらの記号は
ストアされた冗長記号によって再発生されることが可能
だからである。この第２の実施例は、このシステムがセ
クションＱ（２）・・・Ｑ（ｍ）冗長記号をエンコード
することを要求されているという点で、第１の実施例と
は異なる。このシステムは第１の実施例と同様に、（任
意に）セクションＳ（１）記号をエンコードして、セク
ションＥＣＫ（１）記号を形成することも出来る。

【００３７】データ記号１０は、エンコーディングの全
てのｍレベルによって保護されている。第ｍ番目のレベ
ルは、それらをｇｍ　（ｍ）を用いてそれらの保護する
。 このｇｍ　（ｍ）はレベル−１で用いたものよりもかな
りパワフルなＥＣＣであり、多数の冗長記号の記憶を必
要としない。このような保護のために従来のシステムで
は、全てのエンコーディングのレベルからの全ての冗長
記号を記憶することを必要とした。

【００３８】デコーディングは、第１の実施例と関連し
て上で記述されたのと同様に、レベル内でシステムによ
って実行される。このシステムは、レベル−１ＥＣＣで
開始し、必要ならばより高いレベルを使用して、消去さ
れた記号を発生し且つ付加的なエラーを訂正する。各レ
ベルは、前のレベルで使用されていたもの以上に項を有
するジェネレイタ多項式を用いて、さらに非常にパワフ
ルなエラー訂正メカニズムを提供する。また各レベルは
、適当なセクションＱ（２）・・・Ｑ（ｍ）に関連する
コードによって満たされた冗長記号を使用し、こうして
エラーフリー冗長記号を使用する。故に訂正が比較的素
早く実行される。

【００３９】本発明のマルチレベルエンコーディングス
キームは、従来技術のシステムで予期されたように、エ
ンコーダ／デコーダを複雑にしたり、付加的な記号空間
を必要としたり、あるいはエラー訂正のために必要な時
間を猛烈に増加させることなく、パワフルなＥＣＣを用
いて、データ記号を保護する。このスキームは、様々な
より低いエンコーディングレベルからの冗長記号をエン
コードし、そしてそれら消去として取り扱う。こうして
このエンコーディングスキームは、従来技術に必要とさ
れる多数の冗長記号を記憶することなく、データ記号の
パワフルなエラー保護を与えるものである。

【００４０】本発明のシステムは、エラーと消去の両方
を訂正するため、マルチレベルのデコーディングの間に
冗長記号の様々なレベルを使用する。各デコーディング
レベルは、検索された記号中の消去、及び／または、エ
ラーの部分だけを訂正する。故にエラー訂正は、より高
いデコーディングのレベルで、第１の実施例のような複
雑さを減らすＥＣＣ、あるいは第２の実施例のような比
較的少ないエラーを訂正するために必要とされるパワフ
ルなＥＣＣを用いて、比較的素早く実行されるのである
。

【図面の簡単な説明】

【図１】第１レベルのエンコーディングに従って発生さ
れたインタリーブされたコードワードのブロック図を示
す。

【図２】第２及び第３レベルのエンコーディングを用い
てさらにエンコードされた図１のコードワードのブロッ
ク図を示す。

【図３】メモリ内に保持された図２のコードワードの部
分のブロック図を示す。

【図４】再発生された冗長記号を含んでいる検索された
コードワードのブロック図を示す。

【図５】この発明の第２の実施例に従ってコードワード
を形成するためにデータをエンコードするエンコーディ
ングシステムのブロック図を示す。

【図６】図５に示されたエンコーダによって発生された
コードワードのブロック図を示す。

【符号の説明】

１０　　データ記号 １２　　セクション １４　　セクション １６　　セクション

Claims (19)

【特許請求の範囲】
1. 【請求項１】　　「ｋｉ」個のデータ記号をエラーから
   保護する方法において、前記方法は、 Ａ．　　ｋｉ個のデータ記号をｋ個の記号のｉ個のセク
   ションに各々分割し、各々が「ｋ」個のデータ記号と「
   ｒ」個の冗長記号を含んでいるような「ｉ」個のレベル
   −１コードワードを発生するために個々の前記データセ
   クションを第１のエラー訂正コードに従ってエンコード
   し、 Ｂ．　　各レベル−１コードワード内の前記ｒ個の冗長
   記号を「ｍ」個のマルチ記号セクションＲ（１）、Ｒ（
   ２）・・・Ｒ（ｍ）に区画し、 Ｃ．　　前記第１エラー訂正コードと、冗長記号のセク
   ションＱ（２）と関連して発生された「ｑ２　」個の冗
   長記号を用いて発生された「ｉ」個の冗長記号を情報記
   号として各々が含んでいるようなレベル−２コードワー
   ドを発生するために個々の前記レベル−１コードワード
   からエラー訂正コードに従ってセクションＲ（２）内の
   対応する冗長記号をエンコードし、 Ｄ．　　残りの個々のＲ（３）・・・Ｒ（ｍ）冗長記号
   セクションのために、前記エンコードの実行はセクショ
   ンＱ（３）・・・Ｑ（ｍ）冗長記号を発生して、段階Ｃ
   を繰り返し、 Ｅ．　　前記データ記号、前記セクションＲ（１）冗長
   記号、及び前記セクションＱ（２）、Ｑ（３）、・・・
   Ｑ（ｍ）冗長記号を保持する段階を含むことを特徴とす
   る方法。
2. 【請求項２】　　請求項１記載の方法において、前記ｒ
   個の冗長記号の個々の前記Ｒ（２）、・・・Ｒ（ｍ）セ
   クションは、同じエラー訂正コードを用いてエンコード
   される方法。
3. 【請求項３】　　請求項１記載のエラー保護方法におい
   て、前記冗長記号セクションの各々は異なるエラー訂正
   コードを用いてエンコードされるものであり、冗長セク
   ションＲ（３）、・・・Ｒ（ｍ）をエンコードするため
   に用いられる前記エラー訂正コードは、その前のセクシ
   ョンＲ（２）、・・・Ｒ（ｍ−１）をエンコードするた
   めに使用されたコードよりもより少ないエラーを訂正す
   るように設計されている方法。
4. 【請求項４】　　請求項１記載のエラー保護方法におい
   て、前記方法は更に、ｋｉ個のデータ記号をインタリー
   ブする段階を含む方法。
5. 【請求項５】　　請求項１記載のエラー保護方法におい
   て、前記方法は更に、 Ｆ．　　段階Ｅで保持されていない前記セクションＲ（
   ２）、Ｒ（３）、・・・Ｒ（ｍ）記号を消去として取扱
   い、 Ｇ．　　前記エラー訂正コードを用いて、個々のレベル
   −１コードワード内を出来る限り多くの前記消去で満た
   し、そして前記コードワード内のエラーを出来る限り多
   く訂正し、 Ｈ．　　もし、前記レベル−１コードワード内の全ての
   前記冗長記号コードワードが満たされている場合には、
   エラーフリーとして前記データ記号を取扱い、Ｉ．　　
   前記セクションＲ（２）記号が満たされていない各レベ
   ル−１コードワード内で、前記セクションＱ（２）冗長
   記号と前記セクションＲ（２）記号をエンコードするた
   めに用いられた前記エラー訂正コードを使用することに
   より、セクションＲ（２）内の前記消去を満たし、 Ｊ．　　前記第１のエラー訂正コードと前記セクション
   Ｒ（１）及びＲ（２）冗長記号を用いて、前記セクショ
   ンＲ（２）記号が段階Ｉによって満たされた前記レベル
   −１コードワード内のどんなエラーも訂正し、Ｋ．　　
   もし前記レベル−１コードワード内のいくらかの冗長記
   号が満たされなかった場合には、（１）　．　　前記セ
   クションＲ（３）をエンコードするため、前記セクショ
   ンＲ（３）消去を前記セクションＱ（３）冗長記号と前
   記セクションＲ（３）をエンコードするために用いられ
   る前記エラー訂正コードを用いて満たし、 （２）　．　　前記第１エラー訂正コードと前記セクシ
   ョンＲ（１）、Ｒ（２）及びＲ（３）記号を用いて、前
   記セクションＲ（３）記号がこの段階Ｊによって満たさ
   れた前記レベル−１コードワード内のどんなエラーも訂
   正し、Ｌ．　　前記ｒ個の冗長記号の残りの各セクショ
   ンのために段階ｊを繰り返す。
6. 【請求項６】　　請求項５記載のエラー保護方法におい
   て、前記ｒ個の冗長記号の個々の前記Ｒ（２）、・・・
   、Ｒ（ｍ）セクションは同一のエラー訂正コードを用い
   てエンコードされる。
7. 【請求項７】　　請求項５記載のエラー保護方法におい
   て、前記冗長記号セクションの各々は、異なるエラー訂
   正コードを用いてエンコードされるものであり、冗長セ
   クションＲ（３）、・・・Ｒ（ｍ）記号をエンコードす
   るために用いられる前記エラー訂正コードは、データ、
   及びセクションＲ（２）、・・・、Ｒ（ｍ）をそれぞれ
   をエンコードするために使用されるコードよりもより少
   数のエラーを訂正するよう設計されている方法。
8. 【請求項８】　　「ｋｉ」個のデータ記号をエンコード
   して前記データ記号をエラーから保護するためのエラー
   訂正システムにおいて、前記システムは、Ａ．　　デー
   タを各々「ｋ」個の記号の「ｉ」個のセクションに分離
   し且つそれらのセクションを第１のエラー訂正コードに
   従ってエンコードし、各々が「ｋ」個のデータ記号と「
   ｒ」個の冗長記号を含んでいる「ｉ」個のレベル−１コ
   ードワードを発生するための第１のエンコーダ手段と、 Ｂ．　　各レベル−１コードワード内の前記ｒ個の冗長
   記号を「ｍ」個のマルチ記号セクションＲ（１）、Ｒ（
   ２）・・・Ｒ（ｍ）に区画するための手段と、Ｃ．　　
   前記第１のエラー訂正コードと、冗長記号のセクション
   Ｑ（２）と関連して発生された「ｑ２　」個の冗長記号
   を用いて発生された「ｉ」個の冗長記号を情報記号とし
   て各々が含んでいるようなレベル−２コードワードを発
   生するために個々の前記レベル−１コードワードからエ
   ラー訂正コードに従ってセクションＲ（２）内の対応す
   る冗長記号をエンコードするための第２のエンコーダ手
   段であって、残りの冗長記号セクションを各々にエンコ
   ーディングして冗長記号のセクションＱ（３）、・・・
   Ｑ（ｍ）をそれぞれに発生するような第２のエンコーダ
   手段と、 Ｄ．　　前記データ記号、前記セクションＲ（１）冗長
   記号、及び前記セクションＱ（２）、Ｑ（３）、・・・
   Ｑ（ｍ）冗長記号を保持するための手段を含むことを特
   徴とするシステム。
9. 【請求項９】　　請求項８記載のエラー訂正システムに
   おいて、前記第２のエンコーダ手段は、前記ｒ個の冗長
   記号の個々の前記Ｒ（２）・・・Ｒ（ｍ）セクションを
   同一のエラー訂正コードを用いてエンコードするシステ
   ム。
10. 【請求項１０】　　請求項８記載のエラー訂正システム
    において、前記第２のエンコーダ手段は、各セクション
    のために前のセクション記号をエンコードするために用
    いられたコードよりもより少ないエラーを訂正するよう
    に設計されたエラー訂正コードを用いて、前記ｒ個の冗
    長記号の個々の前記Ｒ（２）・・・Ｒ（ｍ）セクション
    をエンコードするシステム。
11. 【請求項１１】　　請求項８記載のエラー訂正システム
    において、前記第１のエンコーダ手段はそれらｋｉ個の
    データ記号をそれらを前記ｉ個のセクションに分離する
    前にインタリーブするシステム。
12. 【請求項１２】　　請求項８記載のエラー訂正システム
    において、前記システムは更に、 Ｅ．　　（１）　．前記レベル−１エラー訂正コードを
    用いて前記セクションＲ（２）・・・Ｒ（ｍ）冗長記号
    を消去として訂正し且つ間違いを持つどんなデータ及び
    セクションＲ（１）記号をも訂正し、 （２）　．もし前記レベル−１コードワード内の全ての
    前記冗長記号が満たされていれば、前記データ記号をエ
    ラーフリーとして取扱う第１の訂正手段と、Ｆ．　　（
    １）　．前記第１の訂正手段によって満たされていない
    前記セクションＲ（２）・・・Ｒ（ｍ）を、前記セクシ
    ョンＱ（２）・・・Ｑ（ｍ）冗長記号と、前記セクショ
    ンＲ（２）・・・Ｒ（ｍ）をそれぞれにエンコードする
    ために用いられる前記エラー訂正コードを使用して満た
    し、（２）　．個々の前記セクションＲ（２）・・・Ｒ
    （ｍ）が満たされた後、更にエラー訂正をするため、前
    記第１の訂正手段を前記レベル−１コードワードに適用
    する第２の訂正手段とを更に含むシステム。
13. 【請求項１３】　　「ｋｉ」個のデータ記号に対応する
    エラー訂正冗長記号を発生する方法において、前記方法
    は、 Ａ．　　それらのｋｉ個のデータ記号をｉ個のセクショ
    ンに区分し、そして各々が「ｋ」個のデータ記号と「ｓ
    」個の冗長記号を含んでいる「ｉ」個のレベル−１コー
    ドワードを発生するために、ＧＦ（２ｔ　）中に連続的
    なルートを有するジェネレイタ多項式ｇ１　（ｘ）：（
    ｘ＋αａ　）＊（　ｘ＋αａ＋１）＊（ｘ＋αａ＋２）
    ＊（ｘ＋αａ＋３）＊　・・・＊（ｘ＋αａ＋ｓ　）　
    、ここで　＊　　はガロア域積であって、αはガロア域
    ＧＦ（２ｔ　）の根本となる多項式であり、前記冗長記
    号は冗長記号のセクションＳ（１）と関連しているもの
    であるが、このジェネレイタ多項式ｇ１　（ｘ）を有し
    ている第１のエラー訂正コードを使用して、ガロア域Ｇ
    Ｆ（２ｔ　）上でそれらのセクションをエンコードし、 Ｂ．セクションＳ（２）と関連する冗長記号の第２のセ
    ットを発生するために、前記ｉレベル−１コードワード
    内の前記データ記号とセクションＳ（１）内の対応する
    記号を、前記ジェネレイタ多項式ｇ１　（ｘ）によって
    割り算された、ｇ１　（ｘ）の拡張であるジェネレイタ
    多項式ｇ２　（ｘ）、ｇ２　（ｘ）＝（ｘ＋αａ−ｄ　
    ）＊（　ｘ＋αａ−ｄ＋１）＊　・・・＊（ｘ＋αａ　
    ）＊・・・＊（ｘ＋αａ＋ｓ　）＊（　ｘ＋αａ＋ｓ＋
    １）＊　・・・＊（ｘ＋αａ＋ｓ＋ｄ　）　の商に等し
    いジェネレイタ多項式ｇ＊２（ｘ）を有する第２のエラ
    ー訂正コードを用いてエンコードし、 Ｃ．　　段階Ｂを所定回数繰り返し且つ冗長記号のセク
    ションＳ（３）・・・Ｓ（ｍ）を発生し、Ｄ．　　冗長
    記号Ｑ（２）・・・Ｑ（ｍ）の関連するセクションを発
    生するために、前記セクションＳ（２）・・・Ｓ（ｍ）
    冗長記号を更にエンコーディングし、Ｅ．　　セクショ
    ンＥＣＫ（２）・・・ＥＣＫ（ｍ）冗長記号を発生する
    ために、冗長記号の個々の前記セクションＱ（２）・・
    ・Ｑ（ｍ）をエンコーディングし、Ｆ．　　前記データ
    記号、前記セクションＳ（１）冗長記号、前記セクショ
    ンＱ（２）・・・Ｑ（ｍ）冗長記号、及び前記ＥＣＫ（
    ２）・・・ＥＣＫ（ｍ）冗長記号を保持する段階を含む
    ことを特徴とする方法。
14. 【請求項１４】　　請求項１３記載の方法において、前
    記方法は更に、それらのｋｉ個のデータ記号をインタリ
    ーブすることを含む方法。
15. 【請求項１５】　　請求項１３記載の方法において、前
    記方法は更に、 Ｆ．　　前記データ記号を、前記セクションＳ（１）冗
    長記号及び、前記第１のエラー訂正コードを用いて訂正
    し、 Ｇ．　　もし前記データ記号内にエラーが残っている場
    合には、前記セクションＱ（２）冗長記号と前記セクシ
    ョンＱ（２）冗長記号を発生するために使用された前記
    エラー訂正コードを用いて、個々のコードワード、前記
    セクションＳ（２）冗長記号を満たし、 Ｈ．　　前記間違いのあるデータ記号を、前記満たされ
    たセクションＳ（２）冗長記号と、前記ジェネレイタ多
    項式ｇ＊２（ｘ）を有する前記第２のエラー訂正コード
    を用いて訂正し、 Ｉ．　　もしエラーが前記データ記号内に残っている場
    合には、前記対応するセクションＱ（３）・・・Ｑ（ｍ
    ）冗長記号と前記レベルに関連するエラー訂正コードを
    用いて個々のコードワード、次の前記冗長記号のセクシ
    ョン、Ｓ（３）・・・Ｓ（ｍ）を満たし、Ｊ．　　エン
    コーディングのそのレベルに関連するエラー訂正コード
    を用いてどんなエラーも訂正する段階を含む方法。
16. 【請求項１６】　　「ｋｉ」個のデータ記号に対応する
    エラー訂正冗長記号を発生するためのシステムにおいて
    、前記システムは、 Ａ．　　前記ｋｉ個のデータ記号をｉ個のセクションに
    分離し、そして各々が「ｋ」個のデータ記号と「ｓ」個
    の冗長記号を含んでいる「ｉ」個のレベル−１コードワ
    ードを発生するために、ＧＦ（２ｔ　）中に連続的なル
    ートを有するジェネレイタ多項式ｇ１　（ｘ）：（ｘ＋
    αａ　）＊（　ｘ＋αａ＋１）＊（ｘ＋αａ＋２）＊（
    ｘ＋αａ＋３）＊　・・・＊（ｘ＋αａ＋ｓ　）　、こ
    こで　＊　　はガロア域積であって、αはガロア域ＧＦ
    （２ｔ　）の根本となる多項式であり、前記冗長記号は
    冗長記号のセクションＳ（１）と関連しているものであ
    るが、このジェネレイタ多項式ｇ１　（ｘ）を有してい
    る第１のエラー訂正コードを使用して、ガロア域ＧＦ（
    ２ｔ　）上でそれらの「ｉ」個のセクションをエンコー
    ドするための第１のエンコーディング手段と、Ｂ．　　
    冗長記号Ｓ（２）を発生するために、個々の前記ｉ個の
    レベル−１コードワード内の前記データ記号及び前記セ
    クションＳ（１）冗長記号を、ｇ１　（ｘ）によって割
    り算された、ｇ１　（ｘ）の拡張であるｇ２　（ｘ）、
    ｇ２　（ｘ）＝（ｘ＋αａ−ｄ　）＊（　ｘ＋αａ−ｄ
    ＋１）＊　・・・＊（ｘ＋αａ　）＊・・・＊（ｘ＋α
    ａ＋ｓ　）＊（　ｘ＋αａ＋ｓ＋１）＊　・・・＊（ｘ
    ＋αａ＋ｓ＋ｄ　）　の商に等しいジェネレイタ多項式
    ｇ＊２（ｘ）を有する第２のエラー訂正コードを用いて
    エンコードするためのエンコーディング手段と、Ｃ．　
    　冗長記号のセクションＱ（２）を発生するために、前
    記セクションＳ（２）冗長記号をエンコーディングする
    ためのエンコーディング手段と、Ｄ．　　セクションＥ
    ＣＫ（２）冗長記号を発生するために前記セクションＱ
    （２）冗長記号をエンコーディングするためのエンコー
    ディング手段と、 Ｅ．　　前記データ記号、前記セクションＳ（１）冗長
    記号、前記セクションＱ（２）及び、セクションＥＣＫ
    （２）冗長記号を保持するための手段とを有することを
    特徴とするシステム。
17. 【請求項１７】　　請求項１６記載のシステムにおいて
    、前記システムは更に、 Ｆ．　　レベル内で、前記データ記号と、エンコーディ
    ングの前のレベルで冗長記号の次のセクションＳ（ｉ＋
    １）を発生するために、前のレベルに関連するジェネレ
    イタ多項式ｇｉ　（ｘ）の拡張であって、このジェネレ
    イタ多項式によって割り算されたジェネレイタ多項式ｇ
    ｉ＋１　（ｘ）の商であるジェネレイタ多項式ｇ＊　ｉ
    ＋１　（ｘ）を有するエラー訂正コードを用いて発生さ
    れた冗長記号Ｓ（ｉ）の前記セクションをエンコーディ
    ングするためのエンコーディング手段と、Ｇ．　　冗長
    記号Ｑ（ｉ）の他のセクションを発生するために、冗長
    記号の個々の前記セクションＳ（ｉ）をエンコーディン
    グするためのエンコーディング手段と、Ｈ．　　冗長記
    号のＥＣＫ（ｉ）セクションを発生するために、冗長記
    号の個々の前記Ｑ（ｉ）セクションをエンコーディング
    するためのエンコーディング手段と、Ｉ．　　前記デー
    タ記号、前記セクションＳ（１）冗長記号、冗長記号の
    前記セクションＱ（２）・・・Ｑ（ｉ）、及び冗長記号
    の前記セクションＥＣＫ（２）・・・ＥＣＫ（ｉ）の組
    みを保持するための手段とを更に備えるシステム。
18. 【請求項１８】　　請求項１６記載のシステムにおいて
    、前記システムは更に、 Ｆ．　　前記セクションＳ（１）冗長記号と前記第１の
    エラー訂正コードを用いて前記データ記号を訂正するた
    めの手段と、Ｇ．　　前記データ記号内にエラーが残っ
    ている場合に、前記セクションＱ（２）冗長記号、及び
    前記セクションＱ（２）冗長記号を発生するために使用
    された前記エラー訂正コードを用いて個々のコードワー
    ド内で前記セクションＳ（２）冗長記号を満たすための
    手段と、 Ｈ．　　前記間違ったデータ記号を、前記満たされたセ
    クションＳ（２）冗長記号と、前記レベル−１ジェネレ
    イタｇ１　（ｘ）によって割り算された、前記レベル−
    １ジェネレイタ多項式の拡張であるジェネレイタ多項式
    ｇ２（ｘ）の商に等しいジェネレイタ多項式ｇ＊２（ｘ
    ）を有する前記第２のエラー訂正コードとを用いて訂正
    することを更に含むシステム。
19. 【請求項１９】　　請求項１７記載のシステムにおいて
    、前記システムは更に、 Ｊ．　　前記セクションＳ（１）冗長記号と前記第１の
    エラー訂正コードを用いて前記データ記号を訂正するた
    めの手段と、 Ｋ．　　前記データ記号内にエラーが残っている場合に
    、前記セクションＱ（２）冗長記号、及び前記セクショ
    ンＱ（２）冗長記号を発生するために使用された前記エ
    ラー訂正コードを用いて個々のコードワード内で前記セ
    クションＳ（２）冗長記号を満たすための手段と、Ｌ．
    　　前記間違ったデータ記号を、前記満たされたセクシ
    ョンＳ（２）冗長記号と、前記レベル−１ジェネレイタ
    ｇ１　（ｘ）によって割り算された、前記レベル−１ジ
    ェネレイタ多項式の拡張であるジェネレイタ多項式ｇ２
    （ｘ）の商に等しいジェネレイタ多項式ｇ＊２（ｘ）を
    有する前記第２のエラー訂正コードとを用いて訂正し、
    Ｍ．　　前記データ記号内にエラーが残っている場合に
    、前記対応するセクションＱ（ｉ）冗長記号と前記対応
    するエラー訂正コードを用いて個々のコードワード内で
    前記次のエンコーディング段階によって発生された前記
    セクションＳ（２）冗長記号を満たすための手段と、Ｎ
    ．　　前記間違ったデータ記号を、前記満たされたセク
    ションＳ（ｉ）冗長記号と、前記前のレベルジェネレイ
    タによって割り算された、前のレベルジェネレイタ多項
    式の拡張である、前記ジェネレイタ多項式ｇｉ　（ｘ）
    の商に等しいジェネレイタ多項式　　ｇ＊　ｉ　（ｘ）
    を有する前記対応するエラー訂正コードとを用いて訂正
    することを更に含むシステム。