(57)【特許請求の範囲】
【請求項１】
ｋのデータディスクからのｍビットデータシンボルを符号化してｒの冗長ディスクのためのｍビット冗長シンボルを生成することを、ｋのデータディスク各々からの対応するシンボルを符号化することにより行なう、符号化のためのシステムであって、前記システムは、
（Ａ）  ｋのデータディスクの対応するセクタからデータを受取るための手段と、
（Ｂ）  （ｍ＋１）ビット冗長シンボルを、以下の式すなわち
【数１】
0004190658.tif 000026
として生成するための符号化手段とを含み、式中ｙ＝０、１、…ｒ−１であり、ｉjはｊ番目のデータディスクからのデータであり、αはｍ＋１を素数としたＧＦ（２m）の要素の（ｍ＋１）ビット表現であり、前記手段は各ｃyについて、
（ｉ）  乗算をｙビット循環シフトとして行なうためのシフトレジスタと、
（ii）  シフトレジスタの内容に次のデータディスクからの対応するデータを加算するための加算器とを備え、前記システムはさらに、
（Ｃ）  （ｍ＋１）ビット冗長シンボルをｍビット冗長シンボルに変換するための変換手段と、
（Ｄ）  ｒの冗長ディスクの対応するセクタにｍビット冗長シンボルをストアするための手段とを含む、符号化のためのシステム。
【請求項２】
符号化手段はｍビットセクタを符号化する、請求項１に記載のシステム。
【請求項３】
シフトレジスタは、１つのシフトでｙビット循環シフトの結果を生成するフィードバック経路を含む（ｍ＋１）ビットシフトレジスタである、請求項１に記載のシステム。
【請求項４】
（ｋ＋ｒ）トラックテープのｋのトラックからのｍビットデータシンボルを符号化してｒの冗長トラックのためのｍビット冗長シンボルを生成することを、ｋのデータトラック各々からの対応するシンボルを符号化することにより行なう、符号化のためのシステムであって、
（Ａ）  ｋのデータトラックの対応するブロックからデータを受取るための手段と、
（Ｂ）  （ｍ＋１）ビット冗長シンボルを、以下の式すなわち
【数２】
0004190658.tif 000027
として生成するための符号化手段とを含み、式中ｙ＝０、１、…ｒ−１であり、ｉjはｊ番目のデータトラックからのデータであり、αはｍ＋１を素数としたＧＦ（２m）の要素の（ｍ＋１）ビット表現であり、前記手段は各ｃrについて、
（ｉ）  乗算をｙビット循環シフトとして行なうためのシフトレジスタと、
（ii）  シフトレジスタの内容に次のデータトラックからの対応するデータを加算するための加算器とを備え、前記システムはさらに、
（Ｃ）  （ｍ＋１）ビット冗長シンボルをｍビット冗長シンボルに変換するための変換手段と、
（Ｄ）  ｍビット冗長シンボルをｒの冗長トラックの対応するブロックにストアするための手段とを含む、符号化のためのシステム。
【請求項５】
符号化手段はｍビットブロックを符号化する、請求項４に記載のシステム。
【請求項６】
シフトレジスタは、１つのシフトにおいてｙビット循環シフトの結果を生成するフィードバック経路を含む（ｍ＋１）ビットシフトレジスタである、請求項４に記載のシステム。
【請求項７】
ｒの冗長ディスクの対応するセクタにストアされた冗長シンボルを用いてｋのデータディスクの対応するセクタにおける誤りを訂正するための復号器であって、
（Ａ）  ｋのデータディスクからデータを受取るための手段と、
（Ｂ）  （ｍ＋１）ビット冗長シンボルを、以下の式すなわち
【数３】
0004190658.tif 000028
として生成するための復号化手段とを含み、式中ｙ＝０、１、…ｒ−１であり、ｉjはｊ番目のデータディスクからの誤りのないデータであり、またはｊ番目のディスクのデータに誤りがあればすべて０であり、αはｍ＋１を素数としたＧＦ（２m）の要素の（ｍ＋１）ビット表現であり、前記手段は各ｃrについて、
（ｉ）  乗算をｙビット循環シフトとして行なうためのシフトレジスタと、
（ii）  シフトレジスタの内容に次のデータディスクからのデータを加算するための加算器とを備え、前記復号器はさらに、
（Ｃ）  ｚを誤りのあるデータを含むディスクの数として、シンドロームＳj、Ｓj+1、…Ｓj+z-1を生成するためのシンドローム発生器を含み、前記シンドローム発生器は、
【数４】
0004190658.tif 000029
を生成し、式中ｊ＝０、１、…、ｒ−１であり、ｉ′ezはｚ番目の誤りのあるディスクと関連する誤りパターンであり、Ｓjはｊ番目の冗長ディスクと関連するシンドロームであり、前記復号器はさらに、
（Ｄ）  シンドロームと関連する誤り値を決定するための手段を含み、前記手段は、重み１の（ｍ＋１）ビットシンボル（αj）pの乗法逆元をαm+1-jpとして決定するための手段を含み、前記復号器はさらに、
（Ｅ）  （ｍ＋１）ビット誤り値をｍビット誤り値に変換するための変換手段と、
（Ｆ）  ｍビット誤り値を用いて誤りのあるｍビットシンボルを訂正するための手段とを含む、復号器。
【請求項８】
誤り値を決定するための手段はさらに、Ａ＝αh＋αv、重み２の（ｍ＋１）ビットシンボルの乗法逆元を、Ａ-1＝（αm+1-h）*δv-hとして決定するための手段を含み、式中δはαm-1＋αm-3＋…＋α3＋α1である、請求項７に記載の復号器。
【請求項９】
誤り値を決定するための手段はまた、Ａ＝αa＋αb＋αc、重み３の（ｍ＋１）ビットシンボルの乗法逆元をαc*Ｄb-cとして決定するための手段を含み、式中Ｄはαa"＋α＋１の逆数であり、ａ"＝（ａ−ｃ）／（ｂ−ｃ）である、請求項８に記載の復号器。
【請求項１０】
誤り値を決定するための手段はさらに、…１…００１１の形式の重み３の（ｍ＋１）ビットシンボルの乗法逆元の（ｍ−１）要素テーブルを含み、前記手段はテーブルを投入してシンボルＤを決定する、請求項９に記載の復号器。
【請求項１１】
ｒの冗長トラックの対応するブロックにストアされた冗長シンボルを用いて複数トラックテープシステムのｋのデータトラックの対応するブロックにおける誤りを訂正するための復号器であって、
（Ａ）  ｋのデータトラックからデータを受取るための手段と、
（Ｂ）  （ｍ＋１）ビット冗長シンボルを、以下の式すなわち
【数５】
0004190658.tif 000030
として生成するための復号化手段とを含み、式中、ｙ＝０、１、…ｒ−１であり、ｉjはｊ番目のデータトラックからの誤りのないデータであり、またはｊ番目のトラックのデータに誤りがあればすべて０であり、αはｍ＋１を素数とするＧＦ（２m）の要素の（ｍ＋１）ビット表現であり、前記手段は各ｃrについて、
（ｉ）  乗算をｒビット循環シフトとして行なうためのシフトレジスタと、
（ii）  シフトレジスタの内容に次のデータトラックからのデータを加算するための加算器とを備え、前記復号器はさらに、
（Ｃ）  シンドロームＳj、Ｓj+1、…Ｓj+z-1を生成するためのシンドローム発生器を含み、式中ｚは誤りのあるデータを含むトラックの数であり、シンドローム発生器は、
【数６】
0004190658.tif 000031
を生成し、式中ｊ＝０、１、…、ｒ−１であり、ｉ′ezはｚ番目の誤りのあるトラックに関連する誤りパターンであり、Ｓjはｊ番目の冗長トラックに関連するシンドロームであり、前記復号器はさらに、
（Ｄ）  シンドロームに関連する誤り値を決定するための手段を含み、前記手段は重み１の（ｍ＋１）ビットシンボル（αj）pの乗法逆元をαm+1-jpとして決定するための手段を含み、前記復号器はさらに、
（Ｅ）  （ｍ＋１）ビットエラー値をｍビットエラー値に変換するための変換手段と、
（Ｆ）  ｍビット誤り値を用いて誤りのあるｍビットシンボルを訂正するための手段とを含む、復号器。
【請求項１２】
誤り値を決定するための手段はさらに、Ａ＝αh＋αv、重み２の（ｍ＋１）ビットシンボルの乗法逆元を、Ａ-1＝（αm+1-h）*δv-hとして決定するための手段を含み、式中δはαm-1＋αm-3＋…＋α3＋α1である、請求項１１に記載の復号器。
【請求項１３】
誤り値を決定するための手段はまた、Ａ＝αa＋αb＋αc、重み３の（ｍ＋１）ビットシンボルの乗法逆元をαc*Ｄb-cとして決定するための手段を含み、式中Ｄはαa"＋α＋１の逆数であり、ａ"＝（ａ−ｃ）／（ｂ−ｃ）である、請求項１２に記載の復号器。
【請求項１４】
誤り値を決定するための手段はさらに、…１…００１１の形式の重み３の（ｍ＋１）ビットシンボルの乗法逆元の（ｍ−１）要素テーブルを含み、前記手段はテーブルを投入してシンボルＤを決定する、請求項９に記載の復号器。
【発明の詳細な説明】
【０００１】
【発明の背景】
複数の独立したディスクを備え、冗長データをストアするためにこれらのディスクのうち２つ以上を使用するシステムは一般に、ＲＡＩＤ−６システムと呼ばれており、ＲＡＩＤは、「廉価または独立ディスクの冗長アレイ（redundantarray  ofinexpensive or independentdisks）」の頭字語である。「ｋ」のデータディスクおよび「ｒ」の冗長ディスクを備えるシステムにおいては、ｒの冗長ディスクに記録されたデータは、ｋのデータディスクに記録されたデータを操作することにより生成される。典型的には、ｒの冗長ディスクのデータは、ｋのデータディスクのデータの誤り訂正符号化の結果である。
【０００２】
ｋのデータディスクのデータはデータ符号語の形式を取り、符号語各々がデータシンボルおよび関連する誤り訂正符号（ＥＣＣ）シンボルを含む。ＥＣＣシンボルは、ＥＣＣに従い従来の態様でデータシンボルを符号化することによって生成される。ｒの冗長ディスクのセクタは、冗長符号語を含む。この符号語におけるシンボルは、ｋのデータディスク各々からの対応するシンボルを符号化することによって生成される。この符号化は、ｋの対応するシンボルの「カラム」の符号化と考えることができる。本明細書において混乱を避けるために、ｋのシンボルのカラムを符号化するのに使用されるＥＣＣは、「カラムＥＣＣ」と呼ぶことにする。典型的には、カラムＥＣＣは、ｋのデータディスクに対するデータ符号語を生成するために使用されるＥＣＣと同じではない。
【０００３】
ｒの冗長ディスクにストアされたシンボルは、含まれるＥＣＣシンボルを用いて訂正できないデータ符号語における誤りを訂正するために使用される。システムは、誤りを訂正するために、カラムＥＣＣに従い、誤りのあるデータシンボルを含むカラムを復号化する。
【０００４】
システムは、冗長ディスクのためのデータを生成するために、ｋの対応するセクタにストアされたデータをｍビットシンボルに分割する。このシステムは次に、カラムＥＣＣに従いｋのセクタ各々からの対応するｍビットシンボルを符号化して、ｒの対応するｍビット冗長シンボル生成する。これらのｒのシンボルはそれぞれ、ｒの冗長ディスク各々の対応するセクタにおいて記録される。
【０００５】
システムの設計者は、カラムの符号化および復号化に必要な時間を最短にするために、比較的大きなシンボルサイズ、すなわち「ｍ」についての値を選択しようとするものである。こうすると、１セクタ当りに必要なカラム符号化／復号化動作数が減少する。符号化および復号化動作には、複数のガロア体乗算が必要である。従来のシステムでは、ｍのサイズが増大するほど、ガロア体乗算の複雑度も大幅に増大する。さらに、各復号化動作は、ガロア体ＧＦ（２m）の要素の乗法逆元の決定を含む。ｍが大きい場合、乗法逆元を発見する演算には時間がかかり、かつ／または、大きな、２m−１要素の、ルックアップテーブルを必要とするかもしれない。したがって、ｍの値は、システムの複雑さと符号化／復号化に要する全時間との歩み寄りにおいて選択される。
【０００６】
複数トラックテープシステムのトラックを、ＲＡＩＤ−６システムにおいて複数のディスクを使用するのと同じやり方で使用してもよい。したがって、データ符号語はｋのトラックにストアされ、関連の冗長シンボルは残りのｒのトラックにストアされる。ｋ＋ｒのディスクに対して使用されるのと同じ符号化／復号化技術を、ｋ＋ｒのトラックに対して用いる。このようにして、カラム符号化に際しｍビットシンボルのサイズを選択する上で、同じ歩み寄りを行なう。
【０００７】
【発明の概要】
本発明は、ｍについて選択された値の組のうち１つを使用し、ガロア体乗算を循環シフトおよび排他的ＯＲ演算の組合せとして行なう、ＲＡＩＤ−６または複数トラックテープシステムのための符号化／復号化システムである。このシステムはまた、以下でより詳細に述べるように、ある乗法逆演算を、本質的には体の種々の要素を２の選択された累乗に累乗することによって決定する。このシステムを用いると、ｍの値を、システムが実行する乗算または逆演算の複雑性を増すことなく、任意に大きなものとして選択することができる。
【０００８】
このシステムは、（ｍ＋１）ビットシンボルを用い、乗算および逆演算を行なう。ｍ＋１は素数である。ｍの値は、体ＧＦ（２m）を以下の既約多項式によって生じさせることができるように選択される。
【０００９】
ｇ（ｘ）＝ｘm＋ｘm-1＋...＋ｘ2＋ｘ＋１
ＧＦ（２m）の２つの要素ａ（ｘ）およびｂ（ｘ）の乗算を、循環シフトされた要素ｂ（ｘ）の（ｍ＋１）ビット版の排他的ＯＲを取ることによって行なうことができる。さらに、以下で述べるように、重み１、２または３のＧＦ（２m）の要素ｃ（ｘ）の乗法逆元を、（ｍ＋１）ビット表現を用いて、本質的には体の特定の要素を２の関連の累乗に累乗することによって容易に決定することができる。このように、既知の先行技術のシステムよりも、復号化動作の複雑性は低く、かつ／または要する時間も短い。
【００１０】
このシステムを用いると、ｍの値を、たとえばディスクのセクタまたはテープのブロックの大きさになるように選択できる。このようにして、カラム誤り訂正符号化／復号化を、１セクタまたはブロック当り１回行なうことができる。
【００１１】
本発明についての以下の説明では、添付の図面を参照する。
【００１２】
【実施例の詳細な説明】
本明細書では、ｋのデータディスクおよびｒの冗長ディスクを備えた複数ディスクシステムと関連付けて、本発明について説明を行なう。本発明を、ｋのデータトラックおよびｒの冗長トラックを備える複数トラックテープシステムについて使用することもできる。
【００１３】
従来のＲＡＩＤ−６システムでは、ｋのセクタの各々におけるｉ番目のｍビットシンボル、すなわちｉ番目のカラムと関連するｒの冗長シンボルは、典型的には以下のようにして生成される。
【００１４】
【数７】
0004190658.tif 000002
【００１５】
式中、Ｃ(r-1)iは、ｒ番目の冗長ディスクのｉ番目のカラムに対する冗長シンボルであり、ｉjは、ｊ番目のディスクのｉ番目のカラムにストアされたシンボルであり、「＋」および「＊」は、ガロア体加算および乗算を表わし、「α」はＧＦ（２m）の要素である。このように、各カラムに対し冗長シンボルを生成するために行なわなければならない、複数の、時間の掛かるガロア体乗算がある。
【００１６】
本発明のシステムは、選択された数の体ＧＦ（２m）のうち１つを用い、ガロア体乗算を簡素化している。選択されたｍに対し、ｍ＋１を素数とすると、ガロア体ＧＦ（２m）を、既約多項式、
ｇ（ｘ）＝ｘm＋ｘm-1＋...＋ｘ2＋ｘ＋１
によって生じさせることができ、要素２は、体ＧＦ（ｍ＋１）の原始元である。このような体は、本明細書に引用により援用する、Ｊ．Ｋ．ウルフ（J.K. Wolf）による、Discrete Mathematics 106/107(1992) 497-502頁において発表された、「ｍのある値に対しＧＦ（２m）において乗算するための効率的な回路（Efficient Circuits For Multiplying In GF(2m) For Certain Values of m）」と題された文献において論じられている。以下で述べるように、このシステムはこういった体を利用し、ＧＦ（２m）の原始元が既知であることを必要としない。このことは、より大きな体を用いるときには重要となる。なぜなら、原始元を決定することは困難であり得るからである。ｍ＜３２９８７の場合のｍの値は、図１から３の表に列記されている。
【００１７】
同時係属中の、「ＧＦ（２w+i）のシンボルの（ｗ＋ｉ＋１）ビット表現を用いた修正リードソロモン誤り訂正システム（MODIFIED REED-SOLOMON ERROR CORRECTION SYSTEM USING (w+i+1)-bit REPRESENTATIONS OF SYMBOLS OF GF(2w+i)」と題された米国特許出願第０８／７８６，８９４号において述べられているように、ＧＦ（２m）の要素は、補数である２つの（ｍ＋１）ビットシンボルａ（ｘ）およびｂ（ｘ）によって表現することができる。すなわち、ａ（ｘ）＋ｂ（ｘ）＝０である。たとえば、ＧＦ（２4）の要素を２つの５ビットシンボルのいずれかによって表現することができる。
【００１８】
【表１】
0004190658.tif 000003
【００１９】
ｍビットシンボルの（ｍ＋１）ビット表現は、先行ゼロを追加するかまたは先行１を追加し、残りのｍビットを補足することによって生成される。明らかに、一方の（ｍ＋１）ビット表現は、他方の（ｍ＋１）ビット表現よりも重み、すなわち１の数が少ない。
【００２０】
２つの（ｍ＋１）ビットシンボルの乗算は、一方のシンボルの循環シフトされたコピーと、他方のシンボルの係数またはビットとの排他的ＯＲを取ることによって行なうことができる。例としてＧＦ（２4）の要素を用いると、２つの要素ａ（ｘ）およびｂ（ｘ）の乗算すなわちａ（ｘ）＊ｂ（ｘ）は、ａ（ｘ）＝ａ4ａ3ａ2ａ1ａ0、ｂ（ｘ）＝ｂ4ｂ3ｂ2ｂ1ｂ0の場合以下のようにして行なわれる。
【００２１】
【数８】
0004190658.tif 000004
【００２２】
ｂ（ｘ）の係数がゼロならば、この係数とａ（ｘ）を循環シフトしたものとの積はゼロであり、したがって計算の必要がない。このようにして、乗算を、ｂ（ｘ）についての２つの（ｍ＋１）ビット表現の重みの低い方を選択することによって簡単にすることができる。実際に、この乗算を、２つのシンボルの重みの低い方としてｂ（ｘ）を選択することによってさらに簡単にすることができる。例として、ｂ（ｘ）＝００１０１の場合、乗算は、ａ（ｘ）*ｂ（ｘ）＝（ａ4ａ3ａ2ａ1ａ0）＋（ａ2ａ1ａ0ａ4ａ3）となる。最も簡単な乗算は、１という１つの係数とｍのゼロの値の係数とを有する（ｍ＋１）ビットシンボルｂ（ｘ）を含む。この積はしたがって、ａ（ｘ）の（ｍ＋１）ビット表現を循環シフトさせたものとなる。
【００２３】
この乗算は、ｍのサイズが増大しても複雑にならない。したがって、ｍを少なくともたとえばセクタのビット数の大きさとして選択することができる。このことは、１セクタに付き１つのカラム符号化動作を行なうことを意味している。
【００２４】
（１）  符号化
上記のように、従来のＲＡＩＤ−６システムでは、ｋのセクタの各々におけるｉ番目のｍビットシンボルと関連する、すなわちｉ番目のカラムと関連するｒの冗長シンボルは、典型的には以下のようにして生成される。式中、ｙ＝０、１...、ｒ−１である。
【００２５】
【数９】
0004190658.tif 000005
【００２６】
現システムは、好ましくは、少なくともディスクセクタにおけるビット数の大きさのｍの値を用いる。したがって、１つの符号化動作により、冗長ディスクにおける対応するセクタについてセクタサイズのシンボルが生まれる。要素αは、ｍ−１の先行ゼロを有する０００００…１０として選択される。冗長ディスクの数がｍ＋１以下であれば、冗長シンボルに対し等式の組において必要なαの累乗は以下のようになる。乗算は循環シフトである。
【００２７】
【数１０】
0004190658.tif 000006
【００２８】
次に図４を参照すると、ｃrについての等式におけるｋ番目の積は、回路１００rにおいて、ｋ番目のディスクの対応するセクタからのデータの（ｍ＋１）ビット表現を（ｍ＋１）ビットシフトレジスタ１１０ｒに与え、シンボルを左に「ｊ」ビットだけ循環シフトすることによって計算される。ｊ＝ｒ−１，ｒ−２…１，０である。この積を、次に、加算器１２０ｒにおいて、（ｋ−１）番目のディスクの対応するシンボルからのデータに加算する。再びシフトレジスタはｊビットだけシフトされ、（ｋ−２）番目のディスクの対応するセクタからのデータがシフトレジスタの内容に加算され、以降同様の動作を行ない、ｃrの（ｍ＋１）ビット表現を生成する。
【００２９】
ｃ0＝ｉ0＋（α0*1）ｉ1＋（α0*2）ｉ2＋...＋（α0*(k-1)）ｉk-1を生成する回路１００0については、図５においてより詳細に示している。ｋ番目のディスクのセクタからのデータの（ｍ＋１）ビット表現は、シフトレジスタ１１０0に与えられ、シフトレジスタはｊ＝０ビットシフトされる。（ｋ−１）番目のディスクのセクタ情報の（ｍ＋１）ビット表現は、それぞれのビットを組合せる加算器サブ回路１２１0−１２１mを含む加算器１２０rにおいてシフトレジスタの内容に加算され、シフトレジスタはしたがって、（α0*1）*ｉk-1＋ｉk-2を含む。シフトレジスタを再びｊ＝０ビットシフトし、（ｋ−２）番目のディスクの対応するセクタからのデータの（ｍ＋１）ビット表現を次に、シフトレジスタの内容に加算する。すなわちシフトレジスタは以下を含む。
【００３０】
【数１１】
0004190658.tif 000007
【００３１】
シフトレジスタは再びｊ＝０ビットシフトされ、（ｋ−３）番目のディスクの対応するセクタのデータの（ｍ＋１）ビット表現をシフトレジスタの内容に加算する。すなわちレジスタは以下を含む。
【００３２】
【数１２】
0004190658.tif 000008
【００３３】
同様の動作を、残りのデータディスクの対応するセクタからのデータがシフトレジスタに加算されるまで行なう。結果、レジスタは（ｍ＋１）ビット冗長シンボルｃ0を含む。
【００３４】
冗長シンボルｃ0の（ｍ＋１）ビット表現を次に、変換器１３０においてｍビットシンボルに変換する。変換器１３０は、（ｍ＋１）ビット表現の先頭ビットと残りｍビットの各々との排他的ＯＲを取る。先頭ビットがゼロであれば、残りのｍビットは変化なしであり、この演算では先頭ビットを無視した場合と同じ結果が生まれる。先頭ビットが１であれば、排他的ＯＲ演算は、ｍビットを補足し、先頭ビットは無視される。
【００３５】
セクタデータの（ｍ＋１）ビット表現は、先頭ゼロビットを追加したセクタの内容である。このようにして、セクタから読出したｍビットを直接、ｍビットを（ｍ＋１）ビット表現に変換するという別のステップを行なわずに、シフトレジスタの適切なロケーションに与えることができる。
【００３６】
図６に示すように、ｃ1を生成するための回路１００1も同様にシフトレジスタ１１０1および加算器１２０1を含む。ｋ番目のデータディスクのセクタからのデータをシフトレジスタに与え、レジスタはｊ＝１ビットシフトされ、（ｋ−１）番目のディスクの対応するセクタからのデータがシフトレジスタの内容に加算される。（ｋ−１）番目のシンボルのビット０はｋ番目のシンボルのビットｍと組合され、（ｋ−１）番目のシンボルのビット１はｋ番目のシンボルのビット０と組合され、以降同様に行なって、
αjｉk-1＋ｉk-2
を生成する。次に、シフトレジスタ１１０1の内容をｊ＝１ビットシフトし、（ｋ−２）番目のデータディスクの対応するセクタからのデータをシフトレジスタの内容に加算して以下を生成する。
【００３７】
【数１３】
0004190658.tif 000009
【００３８】
以降同様に行なう。ｋのディスクすべてからのデータをシフトレジスタに加算した後、内容は変換器１３０に与えられる。変換器は（ｍ＋１）ビットシンボルをｍビットシンボルｃ1に変換する。
【００３９】
ｊ＞１に対するシフトレジスタ１１０jは、１つのクロックサイクルにおいてｊビットシフトを行なうように設定されたフィードバック経路を有してもよい。こうして、単一のシフト演算により適切なビット操作を行なってシフトレジスタ内容をαjで乗算する。このようにして、冗長シンボルｃ0…ｃr-1を、同数のクロックサイクルで並行して生成することができる。
【００４０】
次に図７を参照して、ｃ2を生成するための回路は、１クロックサイクルで２ビット循環シフトの結果を生成するようにされたフィードバック経路を備えたシフトレジスタ１１０2を含む。シフトレジスタ１１０2は、ビットｍをロケーション１１２ｍからロケーション１１２1に与え、ロケーション１１２m-1のビットｍ−１をロケーション１１２0に与え、残りのビットｍ−２、…０それぞれをロケーション１１２m-2、…１１２0からロケーション１１２m、…、１１２2に与える。（ｋ−１）番目のディスクの対応するセクタからのビットを次にシフトレジスタの内容に加算し、（ｋ−１）番目のセクタのビット０がｋ番目のセクタのビットｍ−１と組合され、（ｋ−１）番目のセクタのビット１がｋ番目のセクタのビットｍと組合され、（ｋ−１）番目のセクタのビット２がｋ番目のセクタのビット０と組合され、以降同様に行なわれるようにする。したがって、シフトレジスタは
αjｉk-1＋ｉk-2
を含み、ｊ＝２である。次にシフトレジスタの内容を適切にフィードバックして内容をαjで乗算する。これは、（ｍ＋１）ビット内容を左にｊビットだけ循環シフトするのと同じである。（ｋ−２）番目のデータディスクの対応するセクタからのデータもまたレジスタに加算し、すべてのデータディスクの対応するセクタからのデータがレジスタに加算されるまで同様に行なう。次にシフトレジスタの内容を、ｍビット冗長シンボルｃ2を生成する変換器１３０に与える。
【００４１】
好ましくは、ｃ3，ｃ4，…，ｃrに対する回路は、上記のように単一クロックサイクルで適切なｊビットシフトを生じさせるフィードバック経路と同様に構成される。
【００４２】
（２）  復号化
上記のように、このシステムは、検出されたがデータ符号語におけるＥＣＣシンボルを用いて訂正することができない誤りを訂正する。したがって、誤りのロケーションはわかっている。以下で図８を参照してより詳細に述べるように、現システムを用いて１つまたは複数の誤りを訂正することには、一般的に、重み１、２または３の要素の逆数を発見することが含まれる。
【００４３】
重み１のＧＦ（２m）要素、すなわち１つの非ゼロ係数を有する要素は、１つの１およびｍの０、または１つの０およびｍの１を含む（ｍ＋１）ビット表現に相当する。ｉ番目のビットで１つの１である係数を有する要素αi＝０００…０１…００について、乗法逆元α-iは、αiで乗算されたときにα0＝１を生成する要素である。
【００４４】
シンボルα0は（ｍ＋１）ビットシンボルαm+1と同じである。（ｍ＋１）ビット表現を用いると、αiの乗法逆元は、αiのｉ番目の係数を（ｍ＋１）番目の位置に循環シフトする要素である。したがって逆数はαm+1-iである。ｍ＝４の場合、シンボルα2＝００１００は、α5-2＝α3の乗法逆元を有する。したがって、α2*α3＝α5＝α0である。３ビットを左に循環シフトすることによってα2をα3で乗算することができる。
【００４５】
重み２の要素すなわち２つの１の係数およびｍ−１の０の係数を備える要素に対し、乗法逆元は、
００００...００１１＝α1＋α0
の逆数から決定される。このシンボルの乗法逆元は、０１０１...１０１０：００００...００１１*０１０１...１０１０＝０１０１...１０１０＋１０１０...０１００＝１１１１...１１１０または００００...０００１である。したがって逆数は、シンボルαm-1＋αm-3＋αm-5＋...＋α3＋α1であり、このシンボルをδと定めると、
δ*（α1＋α0）＝α0
が得られる。
【００４６】
和α1＋α0を２の累乗に累乗すると以下が生成される。
【００４７】
【数１４】
0004190658.tif 000010
【００４８】
２をＧＦ（ｍ＋１）の原始元とすると、２iｍｏｄ（ｍ＋１）は１とｍとの間の何らかの値となり得る。したがって、いかなる要素αt＋α0も、（α1＋α0）tとして表わすことがことができ、このｔは０≦ｎ≦ｍの何らかの値について２nである。（α1＋α0）tの逆数は以下のようになる。
【００４９】
【数１５】
0004190658.tif 000011
【００５０】
式中、指数はモジュロｍ＋１である。（ｍ＋１）ビットシンボルを用いると、δを２の累乗に累乗することは、（ｍ＋１）ビットシンボルのビットの置換として行なわれる。ｉ番目のビットの係数すなわち累乗ｔ＝２nに累乗したδのｘiは以下のとおりである。
【００５１】
【数１６】
0004190658.tif 000012
【００５２】
何らかの重み２の要素Ａ＝αh＋αv、ｈ＜ｖの逆数を決定するために、このシステムは、αh*σ＝Ａのσ＝α0＋αv-hを用いる。したがってσの逆数は以下のようになる。
【００５３】
【数１７】
0004190658.tif 000013
【００５４】
要素αhは重み１を有するため以下のようになる。
【００５５】
【数１８】
0004190658.tif 000014
【００５６】
量δv-hは置換として計算され、積は置換されたビットを（ｍ＋１−ｈ）ビット左に循環シフトさせたものである。
【００５７】
ｍ＝４、Ａ＝１０１００またはα2＋α4、ｈ＝２、およびｖ＝４の場合の例は以下のようになる。
【００５８】
【数１９】
0004190658.tif 000015
【００５９】
次に挙げるのはこれを検査するための乗法逆元である。
Ａ*Ａ-1＝１０１００*１０００１＝
１０１００＋０１０１０＝１１１１０＝００００１
重み３の要素について、このシステムは０００...０００１１１，０００...００１０１１，０００...０１００１１，（以降同様）の形式の要素の逆数の（ｍ−１）要素ルックアップテーブルを用いる。何らかの重み３の要素Ａの逆数を発見するために（Ａ＝αa＋ａb＋αcかつａ＞ｂ＞ｃ）、このシステムは最初にＡを、α-cすなわちα(m+1-c)で乗算し、以下を形成する。
【００６０】
【数２０】
0004190658.tif 000016
【００６１】
これは以下と同じである。
【００６２】
【数２１】
0004190658.tif 000017
【００６３】
次に、αa"＋α1＋１の逆数をルックアップテープから検索する。この逆数は要素Ｄであり、γの逆数はＤb'である。Ａの逆数はしたがって以下のとおりとなる。
【００６４】
【数２２】
0004190658.tif 000018
【００６５】
式中Ｄb-cは置換として計算され、αcによる乗算は循環シフトである。
（３）  システム
次に図８を参照して、符号器６１０は、ｋのデータディスク６１２からの対応するセクタを符号化して、ｒの冗長ディスク６１４に記録するためにｒの冗長セクタを生成する。この符号器は図４−７を参照して先に述べた回路１００rを用いて、冗長シンボルｃ0，ｃ1，...，ｃr-1を生成する。
【００６６】
復号器６２０および誤り訂正プロセッサ６３０は、ｋのデータディスクにストアされたデータにおける誤りを訂正する。この誤りは、データディスクにストアされたＥＣＣシンボルを用い従来のやり方で検出される。
【００６７】
復号器６２０は、誤りのないｍビットセクタの（ｍ＋１）ビット表現を用い、誤りのあるセクタについてはｍ＋１のゼロを用いてカラムを復号化する。したがって誤りのあるセクタはカラム復号化については読出されない。ｑの誤りのあるセクタがあるならば（ｑは１つ以上の冗長セクタを含み得る）、このシステムはｑの１次方程式の組を解いて誤りのある情報を回復する。
【００６８】
この復号器は回路１００rを用いて冗長シンボルＣrを以下のようにしてｃ’rとして再生する。
【００６９】
【数２３】
0004190658.tif 000019
【００７０】
式中、何らかのｉ＝０、１、…、ｋ−１に対するｉ′iは、ｉ番目のデータディスクから読出した誤りのないデータであり、もしデータが誤りを含んでいればすべて０である。復号器は、シンドローム発生器６２１において従来の態様で、誤りのない冗長ディスクに対応するシンドロームＳj、ｊ＝０、１…ｒ−１を生成する。
【００７１】
１つの誤りを訂正するためのシンドロームは、
Ｓj＝（αj）p*ｉ′ｐ
であり、ｉ′pは、ｐ番目のディスクと関連する誤りパターンである。誤りの値は、
ｉ′p＝Ｓj*（αjp）-1
を解く、誤り値プロセッサ６２２によって回復される。αjの重みは１であるので、上記のように、αjpの重みは１であり（αjp）-1は（αm+1-jp）である。プロセッサはこのようにして容易に、重み１のサブプロセッサ６２４を用いて乗法逆元を決定し、逆数を循環シフトとしてＳjで乗算する。
【００７２】
二重の誤りを訂正するためのシンドロームは以下のとおりである。
【００７３】
【数２４】
0004190658.tif 000020
【００７４】
式中ｉ′qはｑ番目のディスクと関連する誤りパターンである。誤りの値はしたがって以下のようにして決定される。
【００７５】
【数２５】
0004190658.tif 000021
【００７６】
分母は、αの累乗の２つの積の和、すなわちαa＋αbである。この和の重みは、もしａ＝ｂであれば０であり、もしａ≠ｂであれば２である。重み２の分母については、αa＋αbの逆数は上記のように、重み２のサブプロセッサ６２５を用いて容易に決定することができる。
【００７７】
システムは、３つ以上の誤りを訂正するために、連続冗長ディスクに対応するシンドロームを用いる。式の組を解くために、システムは以下の行列式の逆数を決定する。
【００７８】
【数２６】
0004190658.tif 000022
【００７９】
ヴァンデルモンドの行列式の値は、すべてのｅ0≦ａ≦ｅz-1およびｅ1≦ｂ≦ｅzについて以下の項の積に等しい。
【００８０】
【数２７】
0004190658.tif 000023
【００８１】
したがって、行列式Ｄの値は、因子の逆数の積である以下の逆数である。
【００８２】
【数２８】
0004190658.tif 000024
【００８３】
因子Ｊは、重み１のアルファの累乗の連続の積であり、Ｊはしたがって、重み１のアルファの累乗である。Ｊの逆数は、αm+1-jとして容易に決定することができる。ヴァンデルモンドの行列式の因子は各々重み２であり、その逆数は上記のように重み２のサブプロセッサ６２５を用いて容易に決定される。
【００８４】
行列式ＪＶは、Ｄｅｔj／ＪＶによって決定される誤りの値を解くために用いられる分母である。このＤｅｔjは、ｊ番目のカラムを適切なシンドロームで置き換えた行列式Ｄである。したがってＤｅｔjは項
（αa＋αb）*Ｓj
の和に等しく、各積は、Ｓjを循環シフトさせたもの２つの和として計算される。
【００８５】
ｚの連続するシンドロームを生成するのに十分な数の連続した誤りのない冗長ディスクがなければ、分母における行列式はヴァンデルモンドの行列式ではない。生成される因子はしたがって、２よりも大きな重みを有する。重み３の因子については、重み３のサブプロセッサ６２６が上記のように逆数を決定する。３よりも大きな重みを有する項については、重み＞３のサブプロセッサ６２７がユークリッドの互除法を用いて反復的にａ（ｘ）*ｂ（ｘ）＋ｑ（ｘ）*（ｘm＋ｘm+1＋...１＋ｘ＋１）を解く。ｂ（ｘ）は逆数である。
【００８６】
代わりに、このシステムは、カラムＥＣＣについて非原始のリードソロモン符号を用いてもよく、カラム符号器および復号器はしたがって、本明細書に引用により援用する、FettweisおよびHassnerによる、「ハードウェアの複雑性が低い複合リードソロモン符号器およびシンドローム発生器（A Combined Reed-Solomon Encoder and Syndrome Generator With Small Hardware Complexity）」、（Proceeding of the 1992 IEEE International Symposium On Circuits and Systems, San Diego, California, May 10-13 1993, pp.1871-1874）において述べられているように、ハードウェアを共有することができる。たとえば、符号器および復号器は、乗算器、シフトレジスタおよび加算器を共有してもよい。非原始のリードソロモン符号を用いるならば、最大で全ディスクはｍであり、すなわちｋ＋ｒ≦ｍである。
【００８７】
非原始のリードソロモン符号は、ｔ＋１の連続する根を有する生成多項式
ｇ（ｘ）＝（ｘ＋α0）（ｘ＋α1）...（ｘ＋αt）
を有する。非原始のリードソロモン符号については、シンドロームは、単にデータディスクではなくディスクすべてからの検索されたシンボルに基づき決定される。したがってこのシンドロームは、以下のようになる。
【００８８】
【数２９】
0004190658.tif 000025
【００８９】
いかなる数の誤りｚ≦ｒについても、常にｒの連続するシンドロームが利用できる。実際に、最初のｚのシンドロームを使用することができる。誤りの値を解くために逆数が必要とされる行列式はしたがってヴァンデルモンドの行列式である。したがって上記のように、行列式の逆数は容易に、各々が重み２を有する、因子αa＋αbの逆数をともに乗算することによって発見される。誤りの値を決定するための計算は本質的には、いかなる数の誤りについても同じである。こうして、システムは容易にｒの誤りまで、重みが２よりも大きな何らかの要素の逆数を発見せずとも、訂正することができる。
【００９０】
上記のシステムは、ｍビットシンボルのカラムを（ｍ＋１）シンボルとして符号化し、ｍはディスクセクタまたはテープブロックにおけるビット数と同じまたはこれよりも大きなものとして選択することができる。カラム符号化についての既知の先行技術のシステムでは、このような大きなｍビットシンボルの使用は、必要なガロア体乗算器、およびＧＦ（２m）における乗法逆元を発見するための回路が複雑なために本質的に禁じられている。このシステムはこうした演算を簡単にしており、したがって本質的に任意の大きな値のｍを使用することができる。上記のように、ｍの値は、必要に応じてより大きなｍの値を含むように拡張できる、図１から３の表から選択される。
【００９１】
上記の説明は、本発明の特定的な実施例に限定されている。しかしながら、循環シフト演算を行なうシフトレジスタの種々の構成の使用、ソフトウェア、ハードウェアまたはファームウェアにおいて種々の演算を行なうこと、または種々の単一目的のプロセッサを１つ以上の多重目的プロセッサに組合せることなどの変形および修正を本発明に施し、その利点のいくつかまたはすべてを得ることができることが明らかであろう。したがって、前掲の請求項の目的は、本発明の精神および範囲内のこうしたすべての変形および修正を網羅することである。
【図面の簡単な説明】
【図１】ｍの選択された値の表の図である。
【図２】図１に続く表の図である。
【図３】図２に続く表の図である。
【図４】冗長シンボルｃrを生成するための回路の機能ブロック図である。
【図５】冗長シンボルｃ0生成するための回路の機能ブロック図である。
【図６】冗長シンボルｃ1を生成するための回路の機能ブロック図である。
【図７】冗長シンボルｃ2を生成するための好ましい回路の機能ブロック図である。
【図８】図４から７の回路を組込んだ符号化／復号化システムの機能ブロック図である。
【符号の説明】
６１０  符号器
６２０  復号器
６３０  誤り訂正プロセッサ
【図１】
0004190658.tif 000032
【図２】
0004190658.tif 000033
【図３】
0004190658.tif 000034
【図４】
0004190658.tif 000035
【図５】
0004190658.tif 000036
【図６】
0004190658.tif 000037
【図７】
0004190658.tif 000038
【図８】
0004190658.tif 000039