(57)【要約】【課題】誤り値を求める方法を提供する。【解決手段】誤り値を求める方法は、データシンボルを表わす行を有する誤り訂正符号（ＥＣＣ）エンティティをロードするステップと、第１の行に対して誤り位置を求めるステップと、第１の行に対して誤りシンドロームを生成するステップと、誤り位置から消失定数を求めるステップと、残りの行の各々に対して誤り位置を求めるステップと、残りの行の各々に対して誤りシンドロームを生成するステップと、対応の誤り位置、対応の誤りシンドロームおよび定数から、行の各々について誤り値を求めるステップとを含む。【選択図】図２
2009295273.tif 000002
【特許請求の範囲】
【請求項１】
誤り訂正符号（ＥＣＣ）エンティティのための消失訂正のコンピュータ実現化方法であって、
消失位置を受けるステップと、
第１のシンドローム多項式を生成するステップと、
消失定数配列を計算するステップと、
前記第１のシンドローム多項式および前記消失定数配列のみを用いて第１の行ＥＣＣデータ値を訂正するステップと、
第２のシンドローム多項式を生成するステップと、
前記第２のシンドローム多項式および消失定数配列のみを用いて、第２の行ＥＣＣデータ値を訂正するステップとを含み、
前記第１および前記第２の行ＥＣＣデータ値の訂正において、前記消失定数配列として同じ値が用いられる、方法。
【請求項２】
前記消失定数配列を計算するステップは、
第２の消失位置を受けるステップと、
第２のシンドローム多項式および前記消失定数配列から前記第２の消失位置を訂正するステップとを含む、請求項１に記載のコンピュータ実現化方法。
【請求項３】
ＥＣＣエンティティのための行誤り訂正符号（ＥＣＣ）データ値を訂正するためのコンピュータ実現化方法であって、
消失位置を受けるステップと、
前記行ＥＣＣデータ値が訂正される行に対する誤りシンドロームおよび消失定数配列のみを用いて、以下のアルゴリズムによって前記行ＥＣＣデータ値を訂正するステップとを含み、
【数１】
2009295273.tif 000010
式中、Ｙjは行ｊに対する誤り値であり、ρは消失数であり、Ｕjkは消失定数配列であり
、Ｓkは行ｊ誤りシンドロームであって、
異なる行の訂正において、前記消失定数配列として同じ値が用いられる、方法。
【請求項４】
誤り定数Ｕjkは、
位置の値を入力するステップと、
誤り位置多項式の係数を入力するステップと、
ｊ＝０を初期化するステップと、
【数２】
2009295273.tif 000011
を計算するステップとを含む、請求項３に記載のコンピュータ実現化方法。
【請求項５】
Ｕjkは、
【数３】
2009295273.tif 000012
を含む、請求項３に記載のコンピュータ実現化方法。
【請求項６】
誤り値を求める方法であって、
データシンボルを表わす行を有する誤り訂正符号（ＥＣＣ）エンティティをロードするステップと、
第１の行に対して誤り位置を求めるステップと、
第１の行に対して誤りシンドロームを生成するステップと、
誤り位置から消失定数配列を求めるステップと、
残りの行の各々に対して誤りシンドロームを生成するステップと、
対応の誤り位置から、行に対応する誤りシンドロームと前記消失定数配列とのみを用いて、行の各々に対して誤り値を訂正するステップとを含み、
前記各行に対する前記誤り値を求めるために、前記消失定数配列として同じ値が用いられる、方法。
【請求項７】
誤り訂正方法であって、
デジタル線形テープから誤り訂正エンティティをロードするステップと、
消失定数配列を生成するステップと、
誤り値が訂正される行に対する誤りシンドロームおよび前記消失定数配列のみを用いて前記誤り訂正エンティティの複数の行に対して誤り値を訂正するステップとを含み、
前記誤り訂正エンティティの複数の行に対する前記誤り値を求めるために、前記消失定数配列として同じ値が用いられる、方法。
【請求項８】
誤り訂正エンティティは、データシンボルを表わす行を含む、請求項７に記載の方法。
【請求項９】
前記消失定数配列を生成するステップは、
前記誤り訂正エンティティ内の第１の行に対して誤り位置を求めるステップと、
前記第１の行に対して誤りシンドロームを生成するステップとを含む、請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は一般的に、記憶されたデータの誤り検出および訂正に関し、より特定的には、消失訂正としても知られる長いバースト誤りまたは失われたデータの訂正に関する。
【背景技術】
【０００２】
デジタルコンピュータシステムにおいてより高密度な記憶媒体を用いることは、欠陥に関連するデータ誤りの可能性を高めた。そのようなデータ破損の結果としてのデータ損失を減じるために、誤ったデータを訂正するために誤り訂正符号が用いられる。
【０００３】
データシンボルのストリングが磁気テープに記録される前に、これは数学的に符号化されて冗長シンボルを形成する。冗長シンボルは次いでデータストリングに付与されて、冗長シンボルを備えたデータシンボルである符号語を形成する。符号語は次いで磁気テープに記憶される。記憶されたデータが磁気テープからアクセスされる場合、データシンボルを含む符号語はテープから検索されて数学的に復号化される。復号化の間に、データ内のいかなる誤りも検出され、かつ可能であれば、冗長シンボルの操作を介して訂正される。
【０００４】
記憶されたデジタルデータは、多数の独立した誤りを含み得る。多数の誤りを訂正するために用いられる誤り訂正符号の１つのタイプは、リード・ソロモン（ＲＳ）符号である。多数の誤りをデータシンボルのストリングとして訂正するために、ＲＳ符号はガロア体として知られるシンボルの組のさまざまな数学的性質を用いるが、これはＧＦ（Ｐ＊＊Ｑ）で表わされ、ここで「Ｐ」は素数であり、「Ｑ」は体の中の要素またはシンボルごとの桁の数であり、Ｐを底とする。「Ｐ」はデジタルコンピュータアプリケーションにおいて通常２の値を有し、「Ｑ」はシンボルごとのビットの数を表わす。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
データは典型的には、磁気テープにシンボルの長いシーケンスとして記憶される。磁気テープに記憶されたデータにおける誤りはしばしば長いバーストで現われるが、これはシーケンスにおける多くの誤ったシンボルである。これらの長いバースト誤りを扱うために、典型的には特別な誤り検出および／または訂正技術が用いられる。
【０００６】
一旦長いバースト誤りが検出されると、可能であればこれに関する誤ったシンボルは訂正される。誤りが早く訂正されるほど、ユーザがデータを利用可能になる。よって、誤り検出の速度が上昇するにつれ、実効データ転送速度が上昇する。
【課題を解決するための手段】
【０００７】
発明の一局面においては、誤り訂正符号（ＥＣＣ）エンティティのための消失訂正の方法を特徴とし、これは消失位置を受けるステップと、シンドローム多項式を生成するステップと、消失定数配列を計算するステップと、シンドローム多項式と消失定数配列とから第１の行ＥＣＣデータ値を訂正するステップとを含む。
【０００８】
この発明の実施例は、以下の利点の１つ以上を有し得る。
この発明は、データが２回符号化される、すなわち１回は垂直次元（列）で、１回は水平次元（行）で符号化される、ＥＣＣ符号の類に関する。
【０００９】
データは一般的に、磁気テープのような媒体にブロックで書込まれる。ブロックは、典型的には４０００（４ｋ）バイトを含む線形アドレス空間である。よって、ブロックの各
々は最大４０００の英数字、すなわち１バイトごとに１英数字を含み得る。ブロックの各々が、データチェッカおよび／または訂正として用いられる付加的な冗長バイトで終了する。これらの冗長バイトは列冗長バイトと呼ばれる。たとえば、ブロックの最後の８バイトの内容は、ブロック内に先行して書込まれたすべてのデータの線形シフトフィードバック機構において生成されることができる。これは、ブロックに書込まれたすべてのデータに対するチェックサムまたは巡回冗長チェック（ＣＲＣ）符号をもたらす。
【００１０】
１６ブロックのデータごとに、行誤り訂正符号（ＥＣＣ）エンティティが生成され、列冗長符号によって識別された誤りを訂正するために用いられる。ＥＣＣエンティティは典型的には４つのブロックを含み、ブロックの各々は４ｋバイトを含む。ＥＣＣエンティティ内のブロックの各々は列と呼ばれる。列の各々は４ｋバイトを含み、バイトの各々は行符号内のシンボルを表わす。ＥＣＣエンティティ内の行の各々は符号語（またはＥＣＣデータシンボル）を表わし、これは先行する１６ブロックのデータのうちの１つに含まれるデータの数学的表現である。ＥＣＣエンティティの行の各々は、ＥＣＣ行冗長符号として知られる誤り訂正符号で終了する。ＥＣＣ行冗長符号は、ＥＣＣエンティティの行内に含まれるデータシンボル誤りの復元の方法を提供する。
【００１１】
読出動作の間に、データは１６のデータブロックから、ＥＣＣエンティティ内に含まれる、付随する行ＥＣＣデータシンボルとともに読出される。ＥＣＣエンティティ内のデータシンボルの列（ブロック）全体が、システムが列内に訂正不可能な誤りがあると判断した場合に消失する。誤りは行符号に対してわかっている位置で発生している。消失を訂正するために、誤り位置多項式が生成され、シンドローム多項式が生成され、これらの多項式は誤り値（すなわち訂正データ）を求めるために、ＥＣＣエンティティ内の４０００行のシンボルの各々に対してシードをセットされる。
【００１２】
消失位置はＥＣＣエンティティ内のすべての行において同一であるという事実を用いて、定数配列を予め計算する。この定数配列は、消失位置にのみ依存するので、ＥＣＣエンティティにおけるすべての行によって定数配列を共有することができ、かつ一度だけ計算すればよい。行ごとにシンドローム多項式が生成される。このシンドローム多項式を予め計算された定数配列と組合せて用いると、ＥＣＣエンティティにおける行ごとに誤り位置多項式およびシンドローム多項式から同じ定数配列を生成する必要なく、行誤り値を生成する。
【００１３】
この発明の１つ以上の実施例の詳細は、添付の図面および以下の説明に示される。この発明の他の特徴、目的および利点は、説明および図面と特許請求の範囲とから明らかとなるであろう。
【００１４】
この発明の上述の特徴と他の局面とは、添付の図面により詳細に説明される。
異なる図面の同様の参照符号は同様の要素を示す。
【図面の簡単な説明】
【００１５】
【図１】関連のＥＣＣエンティティを備えた１６のデータブロックのブロック図である。
【図２】図１のブロックと併せて用いられる消失訂正プロセスのフロー図である。
【図３】ＥＣＣエンティティのブロック図である。
【図４】ＥＣＣ消失定数を計算するために用いられるプロセスのフロー図である。
【発明を実施するための形態】
【００１６】
図１を参照すると、データは磁気テープなどの媒体１０に以下のように書込まれる。データはＮ個のデータブロック１２ａ−１２ｐのうちの１つに置かれる。ブロックの各々、
たとえばブロック１２ａは、４０００（４ｋ）バイトのデータ１４とそれに続くいくつかのＥＣＣ冗長バイト１６とを含む。データバイト１４およびＥＣＣ冗長バイト１６は、ブロック１２ａ−１２ｐごとのいくつもの誤ったデータバイトを検出し訂正することができるＥＣＣ符号語を形成する。ブロックごとの誤り検出および訂正の量は、選択されるＥＣＣ符号のタイプの関数である。ＥＣＣエンティティ１８は、６４データブロックを含み、ブロックの各々がＥＣＣエンティティ１８におけるデータシンボル列２０として表わされる。ＥＣＣエンティティ１８はまた、６４データブロックを含み、ブロックの各々がＥＣＣエンティティ１８におけるデータシンボル列２０として表わされる。ＥＣＣエンティティはまた、１６ブロックの行ＥＣＣシンボル２２を含む。ＥＣＣエンティティ１８の行の各々は、６４のデータシンボルとＥＣＣ冗長の１６のシンボルとを備えたＥＣＣ符号語である。１６の行ＥＣＣブロック２２もまた媒体１０に書込まれる。行ＥＣＣブロック２２の各々は媒体１０に書込まれた場合、その後に列次元にＥＣＣ冗長バイトが続き、データブロック１２ａ−１２ｐと同様である。
【００１７】
ＥＣＣ行冗長シンボル２２は符号化器を用いて生成されるが、これは入力であるＥＣＣデータシンボル２０を以下のように用いる。ＥＣＣエンティティ１８の行１、列１に位置するＥＣＣデータシンボル２６は、行ＥＣＣ符号語の第１のＥＣＣデータシンボルを表わし、符号化器に入力される。ＥＣＣエンティティ１８の行１、列２に位置するＥＣＣデータシンボル２８は、行ＥＣＣ符号語の第２のＥＣＣデータシンボルを表わし、符号化器に入力される。残りのＥＣＣデータシンボル２０の各々もまた同様の態様で符号化され、たとえばＥＣＣエンティティ１８の行１、列３に位置するＥＣＣデータシンボル３０は符号化器に入力される第３のＥＣＣデータシンボルを表わす。この符号化プロセスは、６４のデータブロックの第１の行から、６４のデータシンボルのすべてが行ＥＣＣ符号化器に入力されるまで行なわれる。行ＥＣＣ符号化器は、１６のＥＣＣ行冗長シンボル２２を生成し、冗長シンボルの各々がＥＣＣブロックまたは列を定義する。このプロセスは、ＥＣＣエンティティ１８の全体がＥＣＣデータシンボル２０および行冗長シンボル２２によって埋まるまですべての行に対して繰返される。一旦ＥＣＣエンティティ１８が生成されると、データブロックは媒体１０に書込まれ、データブロックの各々はＥＣＣエンティティ１８内の列に対応する。列の各々が媒体１０に書込まれると、ＥＣＣ列冗長２４が列データに付与されて、列次元における誤り検出および訂正を可能にする。
【００１８】
読出動作の間に、もしシステムが１つ以上のデータブロック１２ａ−１２ｐで誤りを判断すると、それぞれのデータブロックの列ＥＣＣ符号２４が誤りを訂正するために最初に用いられる。もしシステムが誤りの訂正に失敗すると、ブロックは「消失」したと宣言される。消失は位置がわかっている誤りである。
【００１９】
もしブロックが列ＥＣＣ符号２４によって訂正不可能であると宣言されると、同じＥＣＣエンティティ１８の一部であるすべてのブロックを用いて、行ＥＣＣ符号２２を用いることにより誤ったブロックを訂正する。行ＥＣＣ符号２２は、ＥＣＣ冗長シンボルの数までの、たとえば１６個の、消失したシンボルを訂正することが可能である。訂正は、ガロア体をわたる線形方程式の性質に基づいて、消失訂正プロセス（以下に説明する）を用いて達成される。
【００２０】
図２を参照すると、消失訂正プロセス５０は、誤った列を識別し（５２）、よって行符号のどのシンボルが訂正が必要であるかを判断することを含む。訂正が必要である行符号語に対して、プロセス５０は、誤り位置多項式を求め（５４）、消失定数配列を生成する（５６）。誤り位置多項式と消失定数配列とを用いて、プロセス５０は誤ったシンボルごとに誤り値を計算し（５８）、最初に媒体から検索したデータシンボルで誤り値のＸＯＲ（排他的ＯＲ）をとることにより誤ったシンボルを訂正する（６０）。プロセス５０は、ＥＣＣエンティティ内に処理されるべき行が残っているかどうか判断する（６２）。ＥＣ
Ｃエンティティ内の残りの行ごとに、プロセス５０は消失定数配列を用いて消失シンボルごとに計算し（５８）、誤り値を生成する（６０）。プロセス５０は８０において終了する。
【００２１】
消失定数配列の生成を、ＥＣＣエンティティと併せて説明する。
図３を参照すると、訂正符号（ＥＣＣ）エンティティ１００は、Ｎ本の列（１０２）の長さＬのｍビットのシンボルを含む。列ごとに、２ｔ＋ｅのＥＣＣ列冗長符号１０４が存在する。復号化器は、列ごとに最大ｔの誤りを訂正する。行訂正に対しては、ρのＥＣＣ行冗長シンボル１０６とＮ−ρのＥＣＣデータシンボル１０８が存在する。ρのＥＣＣ行冗長シンボル１０６は、行ごとに最大ρの消失を訂正するよう設計される。
【００２２】
一実施例においては、（Ｌ，Ｌ−２ｔ−ｅ）ｍビットのシンボルＲＳ符号が列に対して用いられ、（Ｎ，Ｎ−ρ）ｍビットのシンボルＲＳ符号が行に対して用いられる。列のうちの１つが訂正に失敗し、誤りを有すると宣言されると、この列は消失する、すなわちすべて誤りを有すると考慮される。こうして、ＥＣＣエンティティ１００内のすべての行は同じ消失位置を共用する。（図２の）誤り訂正プロセス５０は、この性質を用いてＥＣＣエンティティ１００全体の消失を訂正する。
【００２３】
ＥＣＣエンティティ１００に対して、Ｌの行消失訂正が存在する。すべての行において、符号は次式の生成多項式
【００２４】
【数１】
2009295273.tif 000003
【００２５】
と、次式で表わされるシンドローム多項式
【００２６】
【数２】
2009295273.tif 000004
【００２７】
とを備えたｍビット（Ｎ，Ｎ−ρ）ＲＳ符号である。
所与のＮ個のシンボルデータｒ0、ｒ1、・・・、ｒN-1に対して、シンドロームは次式である。
【００２８】
【数３】
2009295273.tif 000005
【００２９】
（ｒ0、ｒ1、・・・、ｒN-1）＝（ｃ0、・・・、ｃN-1）＋（ｅ0、・・・、ｅN-1）であり（ｃ0、・・・、ｃN-1）が符号語の行で（ｅ0、・・・、ｅN-1）が誤りベクトルである場合、シンドロームはまた次式でも与えられる。
【００３０】
【数４】
2009295273.tif 000006
【００３１】
一実施例においては、ρ個のシンドロームのすべてが計算されたと想定する。
【００３２】
【数５】
2009295273.tif 000007
【００３３】
行ごとの値Ｕjkは行シンドローム値Ｓkに（または行誤り値に）依存しないので、そのような値は一度だけ計算すればよく、同じ値Ｕjkがすべての行に対して用いられる。よって、Ｘj、[（ｘ）、[jiおよびＵjkに対する計算は一度だけ求めればよい。
【００３４】
列訂正の後に、消失位置ｉが消失復号化器に与えられる。しかしながら、誤り値を検出するためには、Ｘj、ｊ＝０、・・・、ρ−１に対応するαijを知る必要がある。このために、２つの実施例を用い得る。
【００３５】
１つの実施例は、ｉをαiにマッピングするルックアップテーブルを用いる。テーブルの大きさはＮ×ｍビットである。
【００３６】
【数６】
2009295273.tif 000008
【００３７】
【数７】
2009295273.tif 000009
【００３８】
この発明は詳細な説明とともに記載されたが、上述の説明は例示のみであり、この発明を限定するものではなく、この発明は前掲の特許請求の範囲によって定義されることを理解されたい。他の局面、利点および変形は前掲の特許請求の範囲に含まれる。
【符号の説明】
【００３９】
２０  ＥＣＣデータシンボル、２２  ＥＣＣ行冗長、２４  ＥＣＣ列冗長。
【図１】
2009295273.tif 000013
【図２】
2009295273.tif 000014
【図３】
2009295273.tif 000015
【図４】
2009295273.tif 000016