(57)【要約】【課題】  インラインワイヤ誤り訂正方式を提供する。【解決手段】  ０からｋのワイヤおよびシンボル０からｎを使用するインライン誤り検出および訂正のための方法において、情報ビットおよびシンボルは、ワイヤ０からｋに沿って送出される。情報ブロックをワイヤ０からｋに沿って送出する前に、チェックビットが、情報ビットから計算される。このチェックビットは、情報の水平パリティと拡張パリティと全体パリティとから構成される。チェックビットは、情報ビットの場合と同じワイヤを使用して、ワイヤ０からｋに沿って送出される。【選択図】図７
2005057741.tif 000002
【特許請求の範囲】
【請求項１】
ワイヤ０からｋ−１およびシンボル０からｎを使用するインライン誤り検出および訂正のための方法であって、
ｎを使用されるシンボル数とし、
【数１】
2005057741.tif 000026
とし、ｋを使用されるワイヤ数として、ｉ＝０からｎ−２について、水平パリティ（ＨＰ［ｉ］）を計算するステップ（７０１）と、
Ｂを原始多項式の次数＋１で、シンドロームのビット数として、拡張パリティ
【数２】
2005057741.tif 000027
を計算するステップ（７０３）と、
ｋ本のワイヤのうちのワイヤ０に沿って、前記水平パリティの内容を送出するステップ（７０５）であって、ＨＰ［０］がシンボル０にあり、ＨＰ［１］がシンボル１にあり、…、ＨＰ［ｎ−２］がシンボルｎ−２にあるステップ（７０５）と、
前記水平パリティと、前記拡張パリティとの排他的論理和である全体パリティ（ＯＰ）を計算するステップ（７０７）と、
前記拡張パリティと、前記水平パリティと、前記全体パリティとを含むチェックビットを、前記ワイヤに沿ってシンボル０で送出するステップ（７０９）と、
シンボル［ｉ］が、ビットｂ［ｋ−１…０］［ｉ］を運ぶシンボル１…ｎ−１で情報ビットを送出するステップと、
チェックビットが、誤りを有するかどうかを判断するステップと、
ＨＰ［ｉ］＝ｂ［ｉ＋１］［０…７］として、シンドローム０が、
【数３】
2005057741.tif 000028
となるようなＢビット量｛ｅＢ−１，…，ｅ２，ｅ１，ｅ０｝であり、シンドローム１が、前記拡張パリティおよび７次多項式の総和である、該シンドローム０を計算し（８０４）、該シンドローム１を計算する（８０６）ステップと、
ワイヤｊのビットｉが誤りを含むかどうかを判断するステップ（８１６）と、
ワイヤｊのビットｉが誤りを含む場合に、該誤りを有するビットを反転すること（８２４）により、該ビット誤りを修正するステップと
を含むインライン誤り検出および訂正のための方法。
【請求項２】
ワイヤ０からｋ−１およびシンボル０からｎを使用し、情報ビットおよびシンボルが、ワイヤ０からｋに沿って送出されるインライン誤り検出および訂正のための方法であって、
情報の水平パリティと拡張パリティと全体パリティとを含むチェックビットを情報ビットから計算するステップ（７０１）と、
ワイヤ０からｋ−１であって、情報が同じワイヤに沿って送出される、ワイヤ０からｋ−１に沿って前記チェックビットを送出するステップ（７０５）と、
前記チェックビットから生成されたシンドロームであって、シンドローム０が、前記情報ビットと前記水平パリティ（ＨＰ）ビットとの排他的ＯＲを求める（ＸＯＲする）ことにより前記ＨＰビットから得られ、シンドローム１が、ｎ−１次多項式を含む、シンドロームを使用して、前記送出された情報に誤りが存在するかどうかを判断するステップ（８１０）と、
前記シンドロームを使用して判断された単一ワイヤの誤りを訂正するステップ（８２４）と
を含むインライン誤り検出および訂正のための方法。
【請求項３】
ｎを使用されるシンボル数とし、ｋを使用されるワイヤ数として、ｉ＝０からｎ−２についての前記水平パリティ（ＨＰ［ｉ］）は、
【数４】
2005057741.tif 000029
であり、Ｂを、原始多項式の次数＋１で、かつ、シンドロームのビット数として、前記拡張ビット（ＥＰ）は、
【数５】
2005057741.tif 000030
である
請求項２に記載のインライン誤り検出および訂正のための方法。
【請求項４】
前記水平パリティの内容は、ｋ本のワイヤのうちのワイヤ０に沿って送出され、ＨＰ［０］は、シンボル０にあり、ＨＰ［１］は、シンボル１にあり、…、ＨＰ［ｎ−２］は、シンボルｎ−２にある
請求項３に記載のインライン誤り検出および訂正のための方法。
【請求項５】
ワイヤ０からｋ−１およびシンボル０からｎを使用するインライン誤り検出および訂正のための装置であって、
情報ビットの水平パリティ（ＨＰ）と、拡張パリティ（ＥＰ）と、全体パリティ（ＯＰ）とを計算する（７０１）エンコーダであって、該水平パリティ（ＨＰ［ｉ］）が、ｎを使用されるシンボル数とし、
【数６】
2005057741.tif 000031
とし、ｋを使用されるワイヤ数として、ｉ＝０からｎ−２についてのものであり、該拡張パリティが、Ｂを原始多項式の次数＋１で、かつ、シンドロームのビット数として、
【数７】
2005057741.tif 000032
であり、該全体パリティ（ＯＰ）が、該ＨＰと該ＥＰとの排他的論理和である、エンコーダと、
ワイヤ０からｋにわたって前記情報ビットおよび前記計算されたパリティビットを送出する（７０５）手段であって、前記拡張パリティと前記水平パリティと前記全体パリティとを含むチェックビットは、これらのワイヤに沿ってシンボル０で送出され、シンボル［ｉ］がビットｂ［ｋ−１…０］［ｉ］を運ぶシンボル１…ｎ−１で情報ビットは送出され、ＨＰ［０］がシンボル０にあり、ＨＰ［１］がシンボル１にあり、…、ＨＰ［ｎ−２］がシンボルｎ−２にある水平パリティ（ＨＰ）は、ワイヤ０に沿って送出される、送出する（７０５）手段と、
チェックビットが誤りを有するかどうかを判断する（８１０）手段であって、シンドローム０およびシンドローム１を計算するデコーダを備え、該シンドローム０が、ＨＰ［ｉ］＝ｂ［ｉ＋１］［０…７］として、
【数８】
2005057741.tif 000033
となるようなＢビット量｛ｅＢ−１，…，ｅ２，ｅ１，ｅ０｝であり、該シンドローム１が、前記拡張パリティおよび７次多項式の総和である、判断する（８１０）手段と、
該判断する手段によって判断されたビット誤りを修正する（８２４）手段と、
を備えるインライン誤り検出および訂正のための装置。
【請求項６】
ワイヤ０からｋ−１およびシンボル０からｎを使用するインライン誤り検出および訂正のための装置であって、
情報の水平パリティ（７０１）と、拡張パリティと、全体パリティ（７０７）とを含むチェックビットを情報ビットから計算するエンコーダと、
ワイヤ０からｋ−１であって、情報が同じワイヤに沿って送出される、ワイヤ０からｋ−１に沿って前記チェックビットを送出する（７０５）送信機と、
前記チェックビットから生成されたシンドロームであって、シンドローム０が、前記情報ビットと前記水平パリティ（ＨＰ）ビットとの排他的ＯＲを求める（ＸＯＲする）ことにより前記ＨＰビットから得られ、シンドローム１が、ｎ−１次多項式を含む、シンドロームを使用して、前記送出された情報に誤りが存在するかどうかを判断する（８１０）手段と、
前記シンドロームを使用して判断された単一ワイヤの誤りを訂正する（８２４）誤り訂正コンポーネントと
を含むインライン誤り検出および訂正のための装置。
【請求項７】
ｎを使用されるシンボル数とし、ｋを使用されるワイヤ数として、ｉ＝０からｎ−２についての前記水平パリティ（ＨＰ［ｉ］）は、
【数９】
2005057741.tif 000034
であり、Ｂを、原始多項式の次数＋１で、かつ、シンドロームのビット数として、前記拡張ビット（ＥＰ）は、
【数１０】
2005057741.tif 000035
である
請求項６に記載のインライン誤り検出および訂正のための装置。
【請求項８】
前記水平パリティの内容は、ｋ本のワイヤのうちのワイヤ０に沿って送出され、ＨＰ［０］は、シンボル０にあり、ＨＰ［１］は、シンボル１にあり、…、ＨＰ［ｎ−２］は、シンボルｎ−２にある
請求項７に記載のインライン誤り検出および訂正のための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、電子データの伝送の誤り訂正方式に関し、詳細には、誤り訂正符号（ＥＣＣ）ビット用の明示的なワイヤが存在しないインライン誤り訂正に関する。
【背景技術】
【０００２】
大量の電子データの通信に伴い、データ誤りの可能性が発生する。
これらの誤りは、雑音のある通信媒体、電子的な干渉、太陽黒点、障害のある通信ライン、断線したワイヤなどのさまざまな現象によって引き起こされる可能性がある。
情報技術産業において改良がなされるにつれて、誤り訂正符号（ＥＣＣ）としても知られているさまざまな誤り訂正方法が開発され、通信誤りを最小にするために使用されてきた。
ノード間の伝送だけでなく、ＣＰＵとメモリとの間のデータ転送速度も、ほぼ指数関数的に増加してきた。
伝送データだけでなく、メモリから取り出されるデータも、信頼性があると考えられること、すなわち誤りがないことが重要である。
【０００３】
ＥＣＣ方式には、通常、誤りの検出および検出した誤りの訂正という２つの部分がある。
時間が重要でないいくつかの用途では、誤りが検出されると、データは、訂正されるのではなく、単に再送される場合がある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この方法は、ほとんどの用途にとってあまりにも遅すぎる。
他の用途では、誤り訂正は、ソフトウェアで行われる。
この方法も、多くの用途にとってあまりにも遅すぎる。
【課題を解決するための手段】
【０００５】
本明細書では、インラインワイヤ誤り訂正方式を使用するシステムが説明される。
０からｋのワイヤおよびシンボル０からｎを使用するインライン誤り検出および訂正のための方法が説明される。
情報ビットおよびシンボルは、ワイヤ０からｋに沿って送出される。
情報ブロックをワイヤ０からｋに沿って送出する前に、チェックビットが、情報ビットから計算される。
このチェックビットは、情報の水平パリティと拡張パリティと全体パリティとから構成される。
チェックビットは、情報ビットの場合と同じワイヤを使用して、ワイヤ０からｋに沿って送出される。
【０００６】
情報ブロック、すなわちフレームが受信されると、その送信された情報に誤りが存在するかどうかを判断する必要がある。
シンドロームが、チェックビットから生成されて、比較される。
シンドローム０は、情報ビットと水平パリティ（ＨＰ）ビットとの排他的ＯＲを求める（ＸＯＲする）ことにより、ＨＰビットから得られる。
シンドローム１は、ｎ−１次多項式を含む。
必要に応じて、単一ワイヤの誤り訂正が実行される。
誤りが存在するワイヤおよびビットは、これらのシンドロームを使用して判断される。
【０００７】
詳細な説明は、図面を参照する。
図面において、同じ符号は、同じ要素を参照する。
【発明を実施するための最良の形態】
【０００８】
本出願の多数の斬新な教示を、特に、現在の好ましい例示の実施の形態について説明することにする。
しかしながら、この種の実施の形態は、本明細書の斬新な教示の多くの有利な使用のうちの数個の例しか提供していないことが理解されるべきである。
一般に、本出願の明細書で行われる陳述は、特許請求の範囲に記載されたさまざまな発明のいずれかの範囲を必ずしも定めるとは限らない。
さらに、陳述の中には、本発明のいくつかの特徴には該当し得るが、他のものには該当し得ないものもある。
【０００９】
既存の方式は、ＥＣＣビットを運ぶのに２本のワイヤを必要とする。
しかしながら、多くのケーブル配線による解決法では、情報専用のワイヤ以外の余分のワイヤが使用できないことがある。
本メカニズムは、ＥＣＣビット用の別個のワイヤを必要とすることなく、ワイヤ誤り訂正を行う能力を提供する。
【００１０】
本メカニズムは、ＥＣＣを拡張して、インラインＥＣＣとして機能するようにする。
本方式は、文献にある既存のものと同じＨ行列を使用する。
本メカニズムは、そのＨ行列を拡張して、側波帯ではなく、インライン誤り訂正符号（ＥＣＣ）として機能させる。
例示のワイヤ誤り訂正符号は、以下に示すように配列される。
ワイヤ番号17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
【００１１】
【数１１】
2005057741.tif 000003
【００１２】
ここで、αは、ｎ次原始多項式の根であり、ｎは、チェックビット数である。
【００１３】
ＥＣＣビットを運ぶ２本のワイヤ（０&１）が存在する。
８つのシンボルは、ブロックまたは「フリット」と呼ばれる論理エンティティを構成する。
ワイヤ０は、パリティを水平に表す（ＨＰ、すなわち水平パリティ（horizontal parity））。
この水平パリティは、ワイヤ２〜１７の全ビットのパリティである。
ワイヤ１は、１２８ビットの情報ビットにわたるガロア体演算である拡張パリティ（ＥＰ（extended parity））を運ぶ。
８次原始多項式が使用される。
ｓ次に下げることができ、ワイヤ１に必要なビットは、ｓビットのみとすることができる。
情報ビットのそれぞれは、原始多項式の根αの累乗を有する。
ワイヤ誤りが発生すると、これらのビットの水平パリティが、誤りのあるビットを特定し、拡張パリティが、障害のあるワイヤを特定する。
【００１４】
［既存の方式］
図１を参照する。
図１には、ＥＣＣ方式のワイヤのＨ行列表現を示す。
ワイヤ番号１０１を第１行の上に示す。
第２行１０３は、Ｈ行列を示している。
例えば、ｎをチェックビット数とすると、αは、ｎ次原始多項式の根である。
図２は、ワイヤ０から１８の１９本のワイヤデータパス２０１を表現したものを示している。
ワイヤ０（２０３）は、最も右のワイヤであり、ワイヤ１８（２０５）は、最も左のワイヤである。
それぞれが（フリットとしても知れられている）１９ビット幅の（８つの）シンボル２０７も示されている。
したがって、８×１７ビットの情報が存在し、２本のワイヤが誤り訂正（ＥＣＣ）用である場合に、この方式は、８×１９＝１５２ビットを提供する。
ワイヤ０は、ワイヤ２から１８のビットの水平パリティを運ぶ。
ワイヤ１の８ビットは、他のワイヤのさまざまな多項式の重みである。
換言すると、ワイヤ１の内容は、次のように表される。
【００１５】
【数１２】
2005057741.tif 000004
【００１６】
例えば、ワイヤｊ（ここで２≦ｊ≦１８）に誤りが発生すると、ワイヤ０から導出される水平パリティは、そのワイヤのどのビットが誤り［ｅ０，ｅ１，…，ｅ７］を有するかを示す。
ワイヤ１は、αｊ［ｅ０＋ｅ１α＋ｅ２α２＋…＋ｅ７α７］を見つけ出すために使用され、ｊを一意に特定する。
【００１７】
ワイヤ０について、本明細書では「ｓｙｎｄ」と呼ぶ２つのシンドロームが計算される。
この解説では、
【００１８】
【数１３】
2005057741.tif 000005
【００１９】
シンボルは、ガロア体（ＧＦ（２））の加算、すなわちビットの排他的論理和（ＸＯＲ）を求めるものを示す。
【００２０】
【数１４】
2005057741.tif 000006
【００２１】
ワイヤ１について、
【００２２】
【数１５】
2005057741.tif 000007
【００２３】
ここで、α＝０〜７のすべての累乗は、ＧＦ（２）の加算、すなわちＸＯＲが施された（排他的ＯＲされた）後に個別に加算される。
【００２４】
誤りが、ワイヤｊ＝１で発生すると、ｓｙｎｄ０は、ゼロであるが、ｓｙｎｄ１は、非ゼロである。
ワイヤ１の回復が所望される場合に、αの非ゼロの累乗を有するビットを反転することができる。
【００２５】
ｊ＝０の場合、ｓｙｎｄ１＝０であるが、ｓｙｎｄ０は、非ゼロである。
【００２６】
この文書では、ワイヤ０の内容は、水平パリティ（ＨＰ）と呼ばれる。
ワイヤ１の内容は、拡張パリティ（ＥＰ）と呼ばれる。
【００２７】
［インライン方法］
ＥＣＣ用に２本の専用ワイヤを有するのではなく、最大１つの追加シンボル、または、所望に応じてより多くの追加シンボルが、代わりに使用される。
図３を参照する。
図３には、ワイヤ０から１６（３０１）およびシンボル０から８（３０３）を示す。
この点で、この符号語は、８×１７ビットの情報（１３６ビット）およびＥＣＣ用の１７ビットとなる。
後述するように、シンボル８がＥＣＣを運ぶ。
１６ビットのＥＣＣビットは、上述したのと同じメカニズムを使用して生成される。
１６ビットのＥＣＣビットの全体パリティとして、余分の１ビットが追加され、その結果、１７ビットのＥＣＣとなる。
【００２８】
シンボル８：
ワイヤ  16  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0
｜EP7 EP6 EP5 EP4 EP3 EP2 EP1 EP0｜HP7 HP6 HP5 HP4 HP3 HP2 HP1 HP0｜OP
【００２９】
ここで、
【００３０】
【数１６】
2005057741.tif 000008
【００３１】
ＥＣＣビットが存在する場合に、各シンボルに対して、１ビットの全体パリティビットが必要とされる。
したがって、代替的な実施の形態では、１８ビットのＥＣＣが存在すると、１６ビットのＥＣＣおよび１ビットのＯＰビットが、シンボル８に使用され、２ビットのＥＣＣおよび１ビットのＯＰビットがシンボル９に使用される。
シンボル９の残りは、すべて０にされる。
このＯＰビットは、ＯＰを含めて、ＥＣＣビットが破損しているかどうかを示す。
ＥＣＣシンボルが、破損していない場合には、情報ビットが影響を受け、ＥＣＣが影響を受けない場合のみが考慮される点を除いて、上述したように、１６ビットのＥＣＣビットによる同じ復号メカニズムを使用することができる。
【００３２】
ＯＰビットが誤りを示している場合には、ワイヤのそれぞれに沿って個別に誤りがあると仮定される。
例えば、ワイヤ１に誤りがあると仮定されると、ＨＰ０を反転して、修正されたＥＣＣビットを得る必要がある。
修正されたＥＣＣビットが得られると、必要に応じて、誤り訂正が実行される。
以下のように、情報ビットとＨＰビットとの排他的ＯＲ（ＸＯＲ）を行うことにより、水平パリティビットから、ｓｙｎｄ０が得られる。
【００３３】
ワイヤ１が誤りを有すると仮定して、
【００３４】
【数１７】
2005057741.tif 000009
【００３５】
同様に、ワイヤｊに誤りがあると仮定すると、真のＥＣＣビットは、ＨＰ０１，ＨＰ１１，…ＨＰ７１，ＥＰ０１，…ＥＰ７１に従って導出することができる。
次に、各行ｎ（ｎ＝０…７）の誤りが、以下のように計算される。
【００３６】
【数１８】
2005057741.tif 000010
【００３７】
すべてのｅｎは、ｓｙｎｄ０を構成する。
ｓｙｎｄ１は、以下の式によって得られる。
【００３８】
【数１９】
2005057741.tif 000011
【００３９】
ここで、
【００４０】
【数２０】
2005057741.tif 000012
【００４１】
ワイヤｊが誤りを有する場合に、ワイヤｊは、ｅｙ値を加えることによってすでに訂正されているので、ｓｙｎｄ１は０に等しくなるべきである。
ｓｙｎｄ１が０でない場合に、誤りは、ワイヤｊには存在せず、ある他のワイヤに存在する。
ＥＣＣが、複数のシンボルにわたって拡散されている場合において、それらのシンボルのＯＰの１つが一致しないときは、ワイヤ誤りがまだ存在すると仮定され、そうでない場合には、ＥＣＣビットは、誤りがないと仮定される。
【００４２】
次に図４を参照する。
図４には、インラインワイヤ方法の一実施の形態のＨ行列を示す。
ワイヤ番号４０１を行列４００の列の上に示す。
従来技術の方法と同様に、最初の２列は、ワイヤではない。
行列４００の最初の２列は、それぞれ、すべてのワイヤに関与するパリティビットおよび全体パリティビットである。
Ｂは、ＨＰまたはＥＰのビット数である。
Ｈ行列４００の行１（４０３）は、水平パリティビットＨＰ［］を与える。
Ｈ行列４００の行２（４０５）は、拡張パリティビットＥＰ［］を与える。
ＨＰ［］およびＥＰ［］のビット数（１３）は同じであり、方程式Ｂ＝本方法の一実施の形態の原始多項式の次数＋１によって与えられる。
本方法は、同じワイヤ誤りが、ＥＣＣビットだけでなくデータにも影響を与えるので、エイリアシングを回避するために、第３列の１ではなくαＢから開始する。
【００４３】
従来技術の方法では、ワイヤ０は、ＨＰビットのすべてを運ぶことができる。
ワイヤ１は、ＥＰビットのすべてを運ぶことができ、ワイヤ２…ｎは、情報ビットのすべてを運ぶことができる。
本方法では、ワイヤ０および１がＥＣＣビットを運ぶ従来技術の方法と異なり、ＥＣＣビットを運ぶ専用ワイヤは、利用可能ではない。
したがって、すべてのＥＰビットおよびＨＰビットは、データと同じワイヤで移動する。
【００４４】
ＨＰビットおよび／またはＥＰビットを運ぶシンボルごとに、全体パリティビット（ＯＰ）が必要となる。
ＯＰビットは、同じシンボルに配置されるべきである。
以下の定義は、図面の説明として理解されるべきである。
【００４５】
ワイヤ数は、ワイヤ０からワイヤ１６の１７本である。
シンボルＢの個数は８である。
ＥＰビットおよびＨＰビットのすべては、ＯＰビットと共に、１つのシンボル内に組み込まれる。
以下に説明するように、２つの代替的な実施の形態について検討する。
【００４６】
ケース（１）：（ＥＰ，ＨＰ，ＯＰ）は、１シンボルよりも少ない量を占める。
この場合、以下に示すように、そのシンボルのビットの残りは、情報ビットを運ぶものと仮定される。
ワイヤ  15 14 13 …                        2 1 0
シンボル  ０：d2 d1 d0 e5 e4 e3 e2 e1 e0 h5 h4 h3 h2 h1 h0 OP
累乗：α１８ α１７ …                      α５ α４ α３
【００４７】
シンボル０が、実際には２つのシンボルであるかのように動作することにより、同じ原理が適用される。
一方の組は、｛０  ０  ０  ｅ５  ｅ４…ｅ０  ｈ５…ｈ０…ＯＰ｝用であり、他方の組は、｛ｄ２  ｄ１  ｄ０  ０  ０  ０…０｝用である。
【００４８】
ケース（２）：ＯＰと組み合わされた｛ＨＰ，ＥＰ｝は、複数のシンボルにまたがる。
この点で、１シンボルあたり１ビットのＯＰビットが必要となる。
各シンボルのＯＰビットは、そのシンボルのみのＨＰ／ＥＰビットをＸＯＲ（排他的ＯＲ）したものである。
本方法は、１つのワイヤ誤りが、０個、１個、または２個以上のＨＰ／ＥＰビットに影響を与え得るということを説明する必要性を記載し、本方法は、これらの場合を説明するために修正される必要がある。
これらのＨＰ／ＥＰビットを有するシンボルの個数に応じて、それらは異なる並べ替えをカバーすることから、本方法は変化することになる。
しかしながら、同じ原理が適用される。
【００４９】
本方法でαＢから開始する理由は、ＥＰビットの誤りが、誤りのない場合にエイリアシングすることができないことにある。
これは、全体パリティが、ＨＰ／ＥＰビットに誤りがあることを示す場合において、すべてのワイヤ位置の誤りを導入するように試みるときに必要とされる。
【００５０】
複数のシンボルが存在する上記ケース（２）では、Ｈ行列を選択している間、ワイヤに沿って配置されたＥＰビットのあらゆる組み合わせがＨ行列のαの妥当な累乗でないということに注意しなければならない。
さらに、ワイヤに沿った複数のＥＰビットは、可能であるならば、回避されるべきである。
【００５１】
情報ビットのみが影響を受け、ＥＣＣビットが影響を受けない場合のみが考慮される点を除いて、上述したような１６ビットによる同じ復号メカニズムが使用される。
ＯＰビットが、誤りを示す場合に、ワイヤのそれぞれに沿って個別に誤りがあると仮定され、次いで、修正されたＥＣＣが得られる。
例えば、ワイヤ１に誤りがあると仮定されると、ＨＰ０ビットが反転されて、修正されたＥＣＣビットが得られる。
【００５２】
修正されたＥＣＣビットが得られると、次に、必要に応じて、誤り訂正が実行される。
水平パリティビットから、情報ビットとＨＰビットとをＸＯＲすることにより、ｓｙｎｄ０が得られる（例えば、
【００５３】
【数２１】
2005057741.tif 000013
【００５４】
ワイヤｊに誤りがあると仮定して、修正されたＥＣＣが得られる。
次に、ｓｙｎｄ１が得られる（例えば、
【００５５】
【数２２】
2005057741.tif 000014
【００５６】
ワイヤｊが誤りを有する場合に、ワイヤｊの内容は、ｅｙ値を加えることによってすでに訂正されているので、ｓｙｎｄ１は０に等しくなるべきである。
ｓｙｎｄ１が０でない場合に、誤りは、ワイヤｊには存在せず、ある他のワイヤに存在する。
ＥＣＣが、複数のシンボルにわたって拡散されている場合において、それらのシンボルのＯＰの１つが一致しないときは、誤りが、ワイヤにまだ存在すると仮定され、そうでない場合には、ＥＣＣビットは、誤りがないと仮定される。
【００５７】
本メカニズムでは、水平パリティビットおよび拡張パリティビットのすべてが使用される。
しかしながら、ワイヤ誤りは、情報ビットかＥＣＣビットかにだけでなく、その双方に影響を与えることがある。
このＥＣＣ方式は、機能しないことがある。
全体パリティビットは、ＥＣＣビットを含む各シンボルで使用される。
全体パリティビットに障害があると仮定すると、同じアルゴリズムを使用して、水平パリティがチェックされて、ワイヤ内の誤りのあるビット（もしあれば）が得られ、拡張パリティビットを使用して、誤りのあるワイヤ（もしあれば）が特定される。
全体パリティが、ＥＣＣビットに誤りがあることを示している場合に、まず、ワイヤ０に独立に誤りがあると仮定して、障害が発生したと仮定されるワイヤに対応するＥＣＣビットの訂正が行われ、水平パリティを適用して、誤りのあるビットが検出される。
誤りのあるビットに基づいて、拡張パリティビットが何であるべきかが検出され、誤りのあるビットが拡張パリティビットと比較される。
拡張パリティビットが、障害のあるワイヤ用に算出されたものと一致すると、その障害のあるワイヤおよびそのワイヤ内の障害のあるビットが特定される。
また、この時に、正しいデータも特定することができる。
全体パリティビットが、障害を示していない場合には、ＨＰビットおよびＥＰビットは正しいと仮定され、元のＥＣＣ方式が適用される。
【００５８】
次に、図５を参照する。
図５には、ＥＣＣビットを符号化するための従来技術の方法５００のフローチャートを示す。
まず、ステップ５０１において、水平パリティＨＰ［ｉ］が、次のようにして計算される。
【００５９】
【数２３】
2005057741.tif 000015
【００６０】
すなわち
【００６１】
【数２４】
2005057741.tif 000016
【００６２】
次いで、ステップ５０３において、拡張パリティ（ＥＰ）が、ＥＰ［７：０］として計算される。
ここで、ＥＰは７次多項式である。
したがって、ＥＰ［０］がα０の係数であり、ＥＰ［１］がα１の係数であり、…、ＥＰ［７］がα７の係数となるように、
【００６３】
【数２５】
2005057741.tif 000017
【００６４】
とする。
次いで、ステップ５０５において、水平パリティ（ＨＰ）の内容が、ワイヤ０に沿って送出される。
この送出は、ＨＰ［０］がシンボル０に、ＨＰ［１］がシンボル１に、…、ＨＰ［７］がシンボル７にある状態で行われる。
次いで、ステップ５０７において、拡張パリティ（ＥＰ）の内容が、ワイヤ１に沿って送出される。
この送出は、ＥＰ［０］がシンボル０に、ＥＰ［１］がシンボル１に、…、ＥＰ［７］がシンボル７にある状態で行われる。
最後に、ステップ５０９において、情報ビットｂ［ｉ］が、ワイヤｉに沿って送出される。
ここで、ｉ＝２〜１８である。
【００６５】
図６Ａおよび図６Ｂは、図５に示すような方法を介して送出されたビットを復号するための従来技術の方法を示している。
まず、図６Ａを参照して、ステップ６０１において、シンドローム０（ｓｙｎｄ０）が、８ビット量として計算される。
ここで、
【００６６】
【数２６】
2005057741.tif 000018
【００６７】
ステップ６０３において、７次多項式であるシンドローム１（ｓｙｎｄ１）が、以下の式として計算される。
【００６８】
【数２７】
2005057741.tif 000019
【００６９】
ステップ６０５において、ｓｙｎｄ０が０であるかどうかについての判断が行われる。
ステップ６０７または６０９において、ｓｙｎｄ１＝０であるかどうかについての判断が行われる。
ｓｙｎｄ０＝０であり、かつ、ｓｙｎｄ１＝０である場合には、ステップ６１１において、誤りは存在せず、ビットｂ［１８：２］［７：０］が使用される。
ｓｙｎｄ０＝０であり、かつ、ｓｙｎｄ１＝１である場合には、ステップ６１３において、ワイヤ１に誤りが存在し、ビットｂ［１８：２］［７：０］が、修正されたデータとして使用される。
ｓｙｎｄ０≠０であり、かつ、ｓｙｎｄ１＝０である場合には、ステップ６１５において、ワイヤ０に誤りが存在し、ビットｂ［１８：２］［７：０］が、修正されたデータとして使用される。
しかしながら、ｓｙｎｄ０≠０であり、かつ、ｓｙｎｄ１≠０である場合には、情報ワイヤの１つに、訂正しなければならない誤りが存在する。
【００７０】
次に、図６Ｂを参照する。
図６Ｂには、従来技術の誤り訂正方法を示す。
ステップ６２１において開始する実行ループが実行され、ステップ６２１において、ｅｒｒ＿ｗｉｒｅ（誤りワイヤ）が２に初期化され、ｅｒｒ＿ｗｉｒｅに誤りが存在するものと仮定される。
まず、ステップ６２３において、ｅｒｒ＿ｗｉｒｅのｓｙｎｄ１が、α（ｅｒｒ＿ｗｉｒｅ）（ｅ７α７＋ｅ６α６＋ｅ５α５＋ｅ４α４＋ｅ３α３＋ｅ２α２＋ｅ１α１＋ｅ０）として計算される。
ステップ６２５で判断されるように、ｅｒｒ＿ｗｉｒｅのｓｙｎｄ１が、ｓｙｎｄ１と等しい場合には、ワイヤｅｒｒ＿ｗｉｒｅに誤りのあるビットが存在する。
ステップ６２７において、ｉ＝０〜７として、ビットｂ［ｅｒｒ＿ｗｉｒｅ］［ｉ］が、ｅ［ｉ］によって反転される。
他のワイヤの他のビットは、修正されることなくデータとして使用される。
しかしながら、ｅｒｒ＿ｗｉｒｅのｓｙｎｄ１が、ｓｙｎｄ１と等しくない場合には、ステップ６２９で判断されるように、ｅｒｒ＿ｗｉｒｅが１８（最後のワイヤ）以下であると、ｅｒｒ＿ｗｉｒｅは、ステップ６３１において１つずつインクリメントされ、ｅｒｒ＿ｗｉｒｅのｓｙｎｄ１は、ステップ６２３において再計算される。
このループは、誤りのあるワイヤおよび関連した誤りのあるビットが決定されて訂正されるまで続けられる。
しかしながら、ｅｒｒ＿ｗｉｒｅが、この時点で１８よりも大きくなると、ステップ６３３に示すように、マルチワイヤ誤り（multi-wire-error）が存在し、データは使用することができない。
【００７１】
図７は、情報ビットのインラインワイヤ誤り訂正符号化方法を示している。
図７を参照して、ステップ７０１において、水平パリティが、以下のように計算される。
【００７２】
【数２８】
2005057741.tif 000020
【００７３】
次いで、ステップ７０３において、拡張パリティＥＰ［７：０］が、以下のように計算される。
【００７４】
【数２９】
2005057741.tif 000021
【００７５】
ここで、ＥＰ［ｉ］は、αｉ＋Ｂの係数である。
次いで、ステップ７０５において、ＨＰの内容が、ワイヤ０に沿って送出される。
この送出は、ＨＰ［０］がシンボル０に、ＨＰ［１］がシンボル１に、…、ＨＰ［７］がシンボル７にある状態で行われる。
次いで、ステップ７０７において、全体パリティ（ＯＰ）が計算される。
ここで、
【００７６】
【数３０】
2005057741.tif 000022
【００７７】
である。
ステップ７０９において、チェックビット（ＥＰ［７：０］、ＨＰ［７：０］、ＯＰ）が、シンボル０で送出される。
この時、ＥＰ［７］はワイヤ１６に、ＨＰ［０］はワイヤ１に、ＨＰ［０］はワイヤ０にある。
残りのビットは、シンボル１から８に配置される。
したがって、シンボルｉは、ビットｂ［１６…０］［ｉ］を運ぶ。
【００７８】
図８Ａ〜図８Ｄは、インライン誤り訂正方法を示している。
図８Ａを参照して、ステップ８０２において、以下の式のように、チェックビットが検査されて、誤りが存在するかどうかが判断される。
【００７９】
【数３１】
2005057741.tif 000023
【００８０】
ここで、ＨＰ［ｉ］＝ｂ［ｉ＋１］［０］であり、ＥＰ［ｉ］＝ｂ［ｉ＋９］である。
ステップ８０３において、チェックビットに誤りが存在するかどうかについての判断が行われる。
チェックビットに誤りが存在しない場合には、ステップ８０４において、ｓｙｎｄ０が、以下のように計算される。
【００８１】
【数３２】
2005057741.tif 000024
【００８２】
ここで、ＨＰ［ｉ］＝ｂ［ｉ＋１］［０７］である。
次いで、ステップ８０６において、ｓｙｎｄ１が、７次多項式として計算される。
ここで、
【００８３】
【数３３】
2005057741.tif 000025
【００８４】
であり、ＥＰ［ｉ］αｉ＝ｂ［ｉ＋９］［０］である。
【００８５】
ステップ８０８において、ｓｙｎｄ０が０であるかどうかについての判断が行われる。
ステップ８１０または８１４において、ｓｙｎｄ１＝０であるかどうかついての判断が行われる。
ｓｙｎｄ０＝０であり、かつ、ｓｙｎｄ１＝０である場合には、ステップ８１２において、誤りは存在せず、ビットｂ［１６：０］［８：１］が使用される。
ｓｙｎｄ０＝０であり、かつ、ｓｙｎｄ１≠０である場合には、チェックビットに誤りが存在しないことを全体パリティの計算が示しているので、マルチワイヤ誤りが存在する。
データビットのどのワイヤ誤りも、双方のシンドロームを破損することになる。
ステップ８１６において、このデータは、使用されるべきでないと判断される。
ｓｙｎｄ０≠０であり、かつ、ｓｙｎｄ１＝０である場合には、ステップ８１６において判断されるように、マルチワイヤ誤りが存在する。
しかしながら、ｓｙｎｄ０≠０であり、かつ、ｓｙｎｄ１≠０である場合には、情報ワイヤの１つに、訂正しなければならない誤りが存在し、実行は、図８Ｂに続く。
【００８６】
次に、図８Ｂを参照して、ステップ８１８において、ｅｒｒ＿ｗｉｒｅが、ワイヤ０に初期化される。
このワイヤには、誤りが存在すると仮定され、シンドロームは、このワイヤに誤りが存在するかのように計算される。
ステップ８２０において、ｓｙｎｄ１が、α（ｅｒｒ＿ｗｉｒｅ＋Ｂ）（ｅ７α７＋ｅ６α６＋ｅ５α５＋ｅ４α４＋ｅ３α３＋ｅ２α２＋ｅ１α１＋ｅ０）として、誤りが存在するかのように計算される。
ステップ８２２において判断されるように、ｓｙｎｄ１が、誤りが存在すると仮定された場合のｓｙｎｄ１と等しい場合には、誤りの存在するビットは、｛ｅ７＋１，ｅ６＋１，…，ｅｉ＋１｝となる。
ステップ８２４において判断されるように、誤りは、ワイヤ＝ｅｒｒ＿ｗｉｒｅに存在する。
ｉ＝１…７について、誤りの存在するビットｂ［ｅｒｒ＿ｗｉｒｅ］［ｉ＋１］は、ｅ［ｉ］によって反転され、次いで、そのデータが使用される。
ｉ＝１…９およびｘ＝０…１６について、ｘ≠ｅｒｒ＿ｗｉｒｅの他のワイヤのビットｂ［ｘ］［ｉ］は、修正なしで使用される。
【００８７】
ステップ８２２において判断されるように、ｓｙｎｄ１が、誤りが存在すると仮定された場合のｓｙｎｄ１と等しくない場合には、ステップ８２６において、ｅｒｒ＿ｗｉｒｅが１６以上であるかどうかについての判断が行われる。
ｅｒｒ＿ｗｉｒｅが１６以上である場合には、ステップ８２８において判断されるように、マルチワイヤ誤りが存在し、そのデータは使用されない。
ｅｒｒ＿ｗｉｒｅが１６以上でない場合には、ステップ８３０において、ｅｒｒ＿ｗｉｒｅが、１つインクリメントされ、プロセスは、ステップ８２０におけるｓｙｎｄ１＿ｉｆ＿ｉｎ＿ｅｒｒｏｒ（誤りが存在する場合のｓｙｎｄ１）の計算に続く。
【００８８】
しかしながら、ステップ８０３で判断されるように、チェックビットに誤りが存在する場合には、ステップ８３２において、ｅｒｒ＿ｗｉｒｅが０に設定される。
次いで、ステップ８３４において、ステップ８０４、８０６、８０８、８１４、８１０、８１２、および８１６が実行される。
しかしながら、処理は、ステップ８１８に続くのではなく、ステップ８３６に続く。
ステップ８３６において、ステップ８２０、８２２、および８２４が実行される。
ステップ８２２において、ｓｙｎｄ１が、誤りが存在すると仮定された場合のｓｙｎｄ１と等しいかどうかがの判断が行われる。
ステップ８３８において、この結果が再びチェックされる。
この時点において、ステップ８２４は、すでに実行されているので、このチェック結果が真であるということは起こり得ない。
したがって、処理は、ステップ８４０に続き、ステップ８４０において、ｅｒｒ＿ｗｉｒｅは１に設定される。
ステップ８４２において、新しい組の水平パリティおよび拡張パリティ（ＨＰ'およびＥＰ'）が計算される。
この点で、ｅｒｒ＿ｗｉｒｅに誤りが存在すると仮定して、ＨＰ'およびＥＰ'は、必要なビットの反転後のＨＰおよびＥＰを反映する。
【００８９】
ステップ８４４において、ｅｒｒ＿ｗｉｒｅが９未満であるかどうかについての判断が行われる。
ｅｒｒ＿ｗｉｒｅが９未満である場合には、ステップ８４５において、ＨＰ'［ｅｒｒ＿ｗｉｒｅ−１］＝ＮＯＴ  ＨＰ'［ｅｒｒ＿ｗｉｒｅ−１］とされる。
そうでない場合には、ステップ８４６において、ＥＰ'［ｅｒｒ＿ｗｉｒｅ］＝ＮＯＴ（反転）  ＥＰ'［ｅｒｒ＿ｗｉｒｅ−９］とされる。
次いで、ステップ８４８において、ｓｙｎｄ０が８ビット量として計算され、ステップ８５０において、ｓｙｎｄ１が７次多項式として計算される。
ステップ８５２において判断されるように、ｓｙｎｄ０が０に等しく、次いで、ステップ８５６で判断されるように、ｓｙｎｄ１も０に等しい場合には、シンボル０でワイヤ番号ｅｒｒ＿ｗｉｒｅに誤りが存在する。
次いで、ステップ８６２において、ビットｂ［１６…０］［８…１］が、入力データとして使用される。
ステップ８５２および８５６において判断されるように、ｓｙｎｄ０＝０  ＡＮＤ（かつ）  ｓｙｎｄ１≠０である場合には、すべてのワイヤが検査されたかどうか、すなわち、ｅｒｒ＿ｗｉｒｅ≧１６であるかどうかについての判断が行われる。
ｅｒｒ＿ｗｉｒｅ≧１６である場合には、ステップ８６４において、マルチワイヤ誤りが存在し、そのデータは使用されない。
ステップ８５２および８５４において判断されるように、ｓｙｎｄ０≠０  ＡＮＤ  ｓｙｎｄ１＝０である場合には、プロセスは、ステップ８６０に続き、最後のワイヤが訂正されているかどうかを判断する。
ｓｙｎｄ０≠０  ＡＮＤ  ｓｙｎｄ１≠０である場合には、ステップ８５８において、ｓｙｎｄ１が、α（ｅｒｒ＿ｗｉｒｅ＋Ｂ）ｓｙｎｄ０に等しいかどうかについての判断が行われる。
等しくない場合には、ステップ８６０において、すべてのワイヤが検査されたかどうかについての判断が行われる。
等しい場合には、シンボル０に加えて、｛ｅ０，ｅ１，…，ｅ７｝が非ゼロであるシンボルにも誤りが存在する。
ｅｉ＝１である場合に、シンボルｅｉ＋１が誤りを有する。
ワイヤ位置は、ｅｒｒ＿ｗｉｒｅである。
次いで、ステップ８６６において、ｉ＝１…７について、ビットｂ［ｅｒｒ＿ｗｉｒｅ］［ｉ＋１］が、ｅ［ｉ］によって反転される。
次いで、ｉ＝１…８、ｘ＝０…１６であり、かつ、ｘ≠ｅｒｒ＿ｗｉｒｅである場合について、他のワイヤの他のビットｂ［ｘ］［ｉ］が、修正なしでデータとして使用される。
処理が、ステップ８６８におけるすべてのワイヤが検査されたかどうかの判断に続き、かつ、すべてのワイヤが検査されていない場合には、処理は、再びステップ８４２に続き、ステップ８４２において、水平パリティおよび拡張パリティが、反転されたビットに基づいて再計算される。
【００９０】
本明細書で使用した用語および説明は、単なる例示として述べたものであり、限定を意味するものではない。
特許請求の範囲およびそれらの均等物で画定される本発明の精神および範囲内において、多くの変形が可能であることが、当業者には理解されよう。
特許請求の範囲において、すべての用語は、特に指定がない限り、それら用語の最も広い意味に理解されるべきである。
【図面の簡単な説明】
【００９１】
【図１】ＥＣＣ方式のワイヤのＨ行列表現である。
【図２】ワイヤ０から１８の１９本のワイヤデータパスを表現したものである。
【図３】ワイヤ０から１６およびシンボル０から８の１７本のワイヤデータパスを表現したものである。
【図４】インラインワイヤ方法の例示の実施の形態のＨ行列である。
【図５】ＥＣＣビットを符号化するための従来技術の方法のフローチャートである。
【図６Ａ】ＥＣＣビットおよび情報ビットを復号するための従来技術の方法のフローチャートである。
【図６Ｂ】ＥＣＣビットおよび情報ビットを復号するための従来技術の方法のフローチャートである。
【図７】水平パリティ、拡張パリティ、および全体パリティを計算することにより、インワイヤＥＣＣのＥＣＣビットおよび情報ビットを符号化するための例示の方法のフローチャートである。
【図８Ａ】ＥＣＣビットおよび情報ビットを、図７に示す方法を使用して符号化されたものとして復号し、インワイヤ方法の単一のワイヤ誤り訂正を実行するための例示の方法のフローチャートである。
【図８Ｂ】ＥＣＣビットおよび情報ビットを、図７に示す方法を使用して符号化されたものとして復号し、インワイヤ方法の単一のワイヤ誤り訂正を実行するための例示の方法のフローチャートである。
【図８Ｃ】ＥＣＣビットおよび情報ビットを、図７に示す方法を使用して符号化されたものとして復号し、インワイヤ方法の単一のワイヤ誤り訂正を実行するための例示の方法のフローチャートである。
【図８Ｄ】ＥＣＣビットおよび情報ビットを、図７に示す方法を使用して符号化されたものとして復号し、インワイヤ方法の単一のワイヤ誤り訂正を実行するための例示の方法のフローチャートである。
【符号の説明】
【００９２】
７００・・・符号化、
８００・・・復号、
【図１】
2005057741.tif 000036
【図２】
2005057741.tif 000037
【図３】
2005057741.tif 000038
【図４】
2005057741.tif 000039
【図５】
2005057741.tif 000040
【図６Ａ】
2005057741.tif 000041
【図６Ｂ】
2005057741.tif 000042
【図７】
2005057741.tif 000043
【図８Ａ】
2005057741.tif 000044
【図８Ｂ】
2005057741.tif 000045
【図８Ｃ】
2005057741.tif 000046
【図８Ｄ】
2005057741.tif 000047