(57)【要約】【課題】  ２スポッティバイト誤り以上の多重スポッティバイト誤りを制御することができる機能を備えたスポッティバイト誤り訂正・検出装置を提供する。【解決手段】  入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるスポッティバイト誤り訂正・検出装置であって、前記符号化手段は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備える。【選択図】  図１
2006060465.tif 000002
【特許請求の範囲】
【請求項１】
入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるスポッティバイト誤り訂正・検出装置であって、
前記符号化手段は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、
前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることを特徴とするスポッティバイト誤り訂正・検出装置。
【請求項２】
前記パリティ検査行列は、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、ＧＦ（２ｂ）上で距離ｄ（ｄは３以上の整数）を有する複数のスポッティバイト誤りを訂正・検出する機能を有する請求項１に記載のスポッティバイト誤り訂正・検出装置。
【請求項３】
前記パリティ検査行列は、前記距離ｄに対し、
2006060465.tif 000137
個のスポッティバイト誤りを訂正すると共に、ｍ個のスポッティバイト誤りを検出し、かつ、
2006060465.tif 000138
を満たす請求項２に記載のスポッティバイト誤り訂正・検出装置。
【請求項４】
前記ｔ値、ｂ値、ｄ値を任意に設定する請求項３に記載のスポッティバイト誤り訂正・検出装置。
【請求項５】
前記情報伝送路は、情報通信システムである請求項１乃至請求項４のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項６】
前記情報伝送路は、メモリシステムである請求項１乃至請求項４のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項７】
前記情報伝送路は、バス線回路である請求項１乃至請求項４のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項８】
前記パリティ検査行列は、前記距離ｄを有するスポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000139
ただし、Ｒ＝（ｄ−１）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、
前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、
γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ’＝［γｉｈ０’、γｉｈ１’、…、γｉｈｂ−１’］が成立するように構成される請求項２乃至請求項７のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項９】
前記パリティ検査行列は、前記距離ｄを有する伸長スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000140
ただし、Ｒ≧（ｄ−１）ｒ、かつ、（Ｒ−ｒ）は（ｄ−２）の倍数であり、
また、Ｎ＝ｂ（ｎ＋２）、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｒ）／（ｄ−２）−１であり、
前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、
Ｒ≧（ｄ−１）ｒとし、γは２を底とする（Ｒ−ｒ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｒ）／（ｄ−２））の原始元であって、γｉＨ’＝［γｉΦ（ｈ０’）、γｉΦ（ｈ１’）、…、γｉΦ（ｈｂ−１’）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｒ）からＧＦ（２（Ｒ−ｒ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｒ）→ＧＦ（２（Ｒ−ｒ）／（ｄ−２））である請求項２乃至請求項７のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項１０】
前記誤り訂正手段は、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力する請求項１乃至請求項９のいずれかに記載のスポッティバイト誤り訂正・検出装置。
【請求項１１】
前記誤り訂正手段は、並列復号手段と、誤り生成手段と、誤り検出手段と、反転手段とを備え、
前記並列復号手段は、前記シンドロームを基にしてＧＦ（２ｒ）上の誤りを生成し、
前記誤り生成手段は、前記並列復号手段で生成された前記ＧＦ（２ｒ）上の誤りを変換し、前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、
前記誤り検出手段は、前記並列復号手段により訂正できない誤りを検出し、
前記反転手段は、前記誤り生成手段から入力される前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、訂正後の受信語を生成する請求項８又は請求項９に記載のスポッティバイト誤り訂正・検出装置。
【請求項１２】
Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する行列Ｈ’に成立するｅ・Ｈ’Ｔ＝ｅ’（ここで、Ｈ’ＴはＨ’の行と列を入れ替えた置換行列）の関係式から、ＧＦ（２ｒ）上の誤りｅ’よりＧＦ（２ｂ）上の誤りｅを決定する請求項１１に記載のスポッティバイト誤り訂正・検出装置。
【請求項１３】
前記誤り訂正手段は、並列復号手段と、誤り生成手段と、誤り検出手段と、反転手段とを備え、
前記並列復号手段は、前記シンドロームを基にして、ＧＦ（２ｒ）上の誤りを指摘する第１のビット誤りポインタと、ＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号とを生成し、
前記誤り生成手段は、前記並列復号手段から入力される前記第１のビット誤りポインタに基づいて、第２のビット誤りポインタを生成し、
前記誤り検出手段は、前記並列復号手段で生成された前記第１のビット誤りポインタと前記第１の訂正不可能誤り検出信号とに基づいて、前記受信語の誤り訂正の可否を判断し、前記受信語のビット誤りを訂正できないことを検出した場合に、第２の訂正不可能誤り検出信号を出力し、
前記反転手段は、前記誤り生成手段で生成された前記第２のビット誤りポインタ及び前記受信語を基にして、前記第２のビット誤りポインタに対応した前記受信語のビットを反転させることにより、前記受信語の誤りを訂正する請求項８又は請求項９に記載のスポッティバイト誤り訂正・検出装置。
【請求項１４】
入力情報データを基に送信語を生成する符号化処理ステップと、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理ステップとを有するスポッティバイト誤り訂正・検出方法であって、
前記符号化処理ステップは、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、
前記復号処理ステップは、
前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理ステップと、
前記シンドローム生成処理ステップにより生成されたシンドロームを基に、前記受信語の誤りを訂正または検出する誤り訂正処理ステップと、
を有することを特徴とするスポッティバイト誤り訂正・検出方法。
【請求項１５】
前記パリティ検査行列は、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、ＧＦ（２ｂ）上で距離ｄ（ｄは３以上の整数）を有する複数のスポッティバイト誤りを訂正・検出する機能を有する請求項１４に記載のスポッティバイト誤り訂正・検出方法。
【請求項１６】
前記パリティ検査行列は、前記距離ｄに対し、
2006060465.tif 000141
個のスポッティバイト誤りを訂正すると共に、ｍ個のスポッティバイト誤りを検出し、かつ、
2006060465.tif 000142
を満たす請求項１５に記載のスポッティバイト誤り訂正・検出方法。
【請求項１７】
前記ｔ値、ｂ値、ｄ値を任意に設定する請求項１６に記載のスポッティバイト誤り訂正・検出方法。
【請求項１８】
前記情報伝送路は、情報通信システムである請求項１４乃至請求項１７のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項１９】
前記情報伝送路は、メモリシステムである請求項１４乃至請求項１７のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項２０】
前記情報伝送路は、バス線回路である請求項１４乃至請求項１７のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項２１】
前記パリティ検査行列は、前記距離ｄを有するスポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000143
ただし、Ｒ＝（ｄ−１）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、
前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、
γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ’＝［γｉｈ０’、γｉｈ１’、…、γｉｈｂ−１’］が成立するように構成される請求項１５乃至請求項２０のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項２２】
前記パリティ検査行列は、前記距離ｄを有する伸長スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000144
ただし、Ｒ≧（ｄ−１）ｒ、かつ、（Ｒ−ｒ）は（ｄ−２）の倍数であり、
また、Ｎ＝ｂ（ｎ＋２）、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｒ）／（ｄ−２）−１であり、
前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、
Ｒ≧（ｄ−１）ｒとし、γは２を底とする（Ｒ−ｒ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｒ）／（ｄ−２））の原始元であって、γｉＨ’＝［γｉΦ（ｈ０’）、γｉΦ（ｈ１’）、…、γｉΦ（ｈｂ−１’）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｒ）からＧＦ（２（Ｒ−ｒ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｒ）→ＧＦ（２（Ｒ−ｒ）／（ｄ−２））である請求項１５乃至請求項２０のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項２３】
前記誤り訂正処理ステップは、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力する請求項１４乃至請求項２２のいずれかに記載のスポッティバイト誤り訂正・検出方法。
【請求項２４】
前記誤り訂正処理ステップは、並列復号処理ステップと、誤り生成処理ステップと、誤り検出処理ステップと、反転処理ステップとを有し、
前記並列復号処理ステップは、前記シンドロームを基にしてＧＦ（２ｒ）上の誤りを生成し、
前記誤り生成処理ステップは、前記並列復号処理ステップで生成された前記ＧＦ（２ｒ）上の誤りを変換し、前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、
前記誤り検出処理ステップは、前記並列復号処理ステップで訂正できない誤りを検出し、
前記反転処理ステップは、前記誤り生成処理ステップで生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、訂正後の受信語を生成する請求項２１又は請求項２２に記載のスポッティバイト誤り訂正・検出方法。
【請求項２５】
Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する行列Ｈ’に成立するｅ・Ｈ’Ｔ＝ｅ’の関係式から、ＧＦ（２ｒ）上の誤りｅ’よりＧＦ（２ｂ）上の誤りｅを決定する請求項２４に記載のスポッティバイト誤り訂正・検出方法。
【請求項２６】
前記誤り訂正処理ステップは、並列復号処理ステップと、誤り生成処理ステップと、誤り検出処理ステップと、反転処理ステップとを有し、
前記並列復号処理ステップは、前記シンドロームを基にして、ＧＦ（２ｒ）上の誤りを指摘する第１のビット誤りポインタと、ＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号とを生成し、
前記誤り生成処理ステップは、前記並列復号処理ステップで生成された前記第１のビット誤りポインタに基づいて、第２のビット誤りポインタを生成し、
前記誤り検出処理ステップは、前記並列復号処理ステップで生成された前記第１のビット誤りポインタと前記第１の訂正不可能誤り検出信号とに基づいて、前記受信語の誤り訂正の可否を判断し、前記受信語のビット誤りを訂正できないことを検出した場合に、第２の訂正不可能誤り検出信号を出力し、
前記反転処理ステップは、前記誤り生成処理ステップで生成された前記第２のビット誤りポインタ及び前記受信語を基にして、前記第２のビット誤りポインタに対応した前記受信語のビットを反転させることにより、前記受信語の誤りを訂正する請求項２１又は請求項２２に記載のスポッティバイト誤り訂正・検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スポッティバイト誤り訂正・検出方法及び装置に関し、より詳しくは、複数のビットをバイトとし、その複数のバイトから構成される語（ワード）に対して、任意のバイト中にビット誤りが生じたときにその誤りを検出または訂正するために用いて好適なスポッティバイト誤り訂正・検出方法及び装置に関する。
【背景技術】
【０００２】
近年、情報化社会の進展や半導体技術の進歩等により、ディジタルデータの信頼性向上がますます重要なものになってきている。ディジタルデータの伝送または記録を正確に行おうとする場合に、送信データが伝送経路中でノイズ等の影響を受けて誤って伝送されたり、素子の故障あるいは記録媒体等の欠陥等により生じた誤りを検出・訂正する必要がある。この誤りの検出・訂正を実現するために、符号理論を基礎とした誤り訂正・検出符号が従来より種々開発されてきている。
【０００３】
従来の誤り訂正符号として、例えば、ｂビット（ｂは２以上の整数）の塊りをバイトと称し、１バイト中の任意の誤りを訂正する符号（ＳｂＥＣ符号と称する）として、優れたHong-Patel符号が発表されている（例えば、非特許文献１参照）。
【０００４】
また、高速半導体メモリシステムにおいて、従来最もよく使用された１ビット誤り訂正・２ビット誤り検出符号を包含する特徴を有した奇数重み列バイト誤り訂正符号が開示されている（例えば、非特許文献２参照）。
【０００５】
さらに、１バイト誤りを訂正し、また２バイト誤りを検出する符号（ＳｂＥＣ−ＤｂＥＤ符号と称する）は、リードソロモン符号（Reed-Solomon符号）及びその改良した効率のよい符号として提案されており、多くの計算機システム等の主記憶装置にすでに採用されている（例えば、非特許文献３や非特許文献４を参照）。
【０００６】
また、バイト誤りを検出する符号としては、１ビット誤りを訂正し、かつ２ビット誤りを検出するとともに、１バイトの誤りをも検出する符号（ＳＥＣ−ＤＥＤ−ＳｂＥＤ符号と称する）が発表され、現在、計算機システムの主記憶装置に多く適用されている（例えば、非特許文献５参照）。
【０００７】
なお、これら１９８０年代後半までの相互に関連した多くの符号研究・開発に関する具体的な内容は、非特許文献６において総括的に述べられている。
【０００８】
その後、新しく開発された高速半導体メモリ用の符号としては、１バイトの誤りを訂正し、かつ２ビット誤りを検出する符号（ＳｂＥＣ−ＤＥＤ符号と称する）が非特許文献７に、また、１バイトの誤りを訂正し、かつ１ビット誤りと１バイト誤りとの同時誤りを検出する符号（ＳｂＥＣ−（Ｓ＋Ｓｂ）ＥＣ符号と称する）が非特許文献８に開示されている。さらに、１バイトの誤りを訂正するとともに２ビットの誤りがあれば、これも訂正する符号（ＳｂＥＣ−ＤＥＣ符号と称する）が非特許文献９に開示されている。
【０００９】
特に、本発明に最も関連する符号として、具体的には、ｂビットからなるバイト内のｔビット（ｔ≦ｂ）までの誤りをｔ／ｂ誤りまたはスポッティバイト誤りと称し、この１スポッティバイト誤りを訂正するＳｔ／ｂＥＣ符号、及び１スポッティバイト誤りを訂正し、かつバイト内ｔビットを越える１バイト誤りを検出するＳｔ／ｂＥＣ−ＳｂＥＤ符号に関する発明が既に開示されている（特許文献１参照）。また、特にＳｔ／ｂＥＣ符号については、非特許文献１０に開示されている。
【００１０】
また、１スポッティバイト誤りを訂正し、かつ２スポッティバイト誤りを検出するＳｔ／ｂＥＣ−Ｄｔ／ｂＥＤ符号、及び１スポッティバイト誤りを訂正し、かつ２スポッティバイト誤りを検出し、かつバイト内ｔビットを越える１バイト誤りを検出するＳｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号に関する発明が既に出願されている（特許文献２参照）。
【特許文献１】特開２００４−７２１７号公報
【特許文献２】特願２００３−４１６９７８号明細書
【特許文献３】特開２００２−３７４１７５号公報
【非特許文献１】エス.ジェイ.ホン（S.J.Hong）・エイ.エム.パテル（A.M.Patel）共著,『ア  ゼネラル  クラス  オフ  マックシマル  コードズ  フォー  コンピュータ  アプリケーションズ  “A general Class ofMaximal Codes for Computer Applications”』,ＩＥＥＥ  トランスアクションズ  オン  コンピュータズ（IEEETransactions on Computers）,第C-21巻,第12号, p.1322-1331,1972年
【非特許文献２】イー.フジワラ（E.Fujiwara）,『オッドーウエイトーコラム  ｂーアジェイスント  エラー  コレクティング  コードズ  “Odd-Weight-Columnb-Adjacent Error Correcting Codes”』,トランスアクションズ  オフ  ザ  ＩＥＣＥ  ジャパン（Transactions of the IECE Japan）,第E61巻,第10号,p.781-787,1978年
【非特許文献３】エス.カネダ（S.Kaneda）・イー.フジワラ（E.Fujiwara）共著,『シングル  バイト  エラー  コレクティングーダブル  バイト  エラー  ディテクティング  コードズ  フォー  メモリ  システムズ  “Single Byte ErrorCorrecting-Double Byte Error Detecting Codes for Memory Systems”』,ＩＥＥＥ  トランスアクションズ  オン  コンピュータズ（IEEETransactions on Computers）,第C-31巻,第7号,p.596-602,1982年７月
【非特許文献４】シー.エル.チェン（C.L.Chen）・エル.イー.グロバシュ（L.E.Grosbach）共著,『フォールトートレラント  メモリ  デザイン  イン  ザ  ＩＢＭ  アプリケーション  システム／４００ＴＭ  “Fault-Tolerant MemoryDesign in the IBM Application System/400TM”』,プロシーディングズ  オフ  アニュアル  インターナショナル  シンポジウム  オン  フォールトートレラント  コンピューティング（Proceedingsof Annual International Symposium on Fault-Tolerant Computing）,p.393-400,1991年6月
【非特許文献５】エス.カネダ（S.Kaneda）,『ア  クラス  オフ  オッドーウエイトーコラム  ＳＥＣ−ＤＥＤ−ＳｂＥＤ  コードズ  フォー  メモリ  システム  アプリケーションズ  “A class ofOdd-Weight-Column SEC-DED-SbED Codes for Memory System Applications”』,ＩＥＥＥ  トランスアクションズ  オン  コンピュータズ（IEEETransactions on Computers）,第C-33巻,第8号,p.737-739,1984年8月
【非特許文献６】ティ.アール.エヌ.ラオ（T.R.N.Rao）・エイジ  フジワラ（Eiji Fujiwara）共著,『エラー  コントロール  コーディング  フォー  コンピュータ  システムズ  “Error Control Codingfor Computer Systems”』,プレンティスーホール（Prentice-Hall）,1989年
【非特許文献７】イー.フジワラ（E.Fujiwara）・エム.ハマダ（M.Hamada）共著,『シングル  ｂービット  バイト  エラー  コレクティング  アンド  ダブル  ビット  エラー  ディテクティング  コードズ  フォー  メモリ  システムズ  “Single b-Bit Byte ErrorCorrecting and Double Bit Error Detecting Codes for Memory Systems”』,ＩＥＩＣＥ  トランスアクションズ  オン  ファンダメンタルズ（IEICETransactions on Fundamentals）,第E76-A巻,第9号,p.1442-1448,1993年9月
【非特許文献８】エム.ハマダ（M.Hamada）・イー.フジワラ（E.Fujiwara）共著,『ア  クラス  オフ  エラー  コントロール  コードズ  フォー  バイト  オーガナイゼド  メモリ  システムズ―ＳｂＥＣ−(Ｓｂ＋Ｓ)ＥＤ  コードズ―  “A Class of ErrorControl Codes for Byte Organized Memory Systems − SbEC−(Sb+S)ED Codes −”』,ＩＥＥＥ  トランスアクションズ  オン  コンピュータズ（IEEETransactions on Computers）,第46巻,第1号,p.105−109,1997年1月
【非特許文献９】ジー.ウマネサン（G.Umanesan）・イー.フジワラ（E.Fujiwara）共著,『ランダム  ダブル  ビット  エラー  コレクティングーシングル  バイト  エラー  コレクティング（ＤＥＣ−ＳｂＥＣ）  コードズ  フォー  メモリ  システムズ  “Random Double BitError Correcting − Single Byte Error Correcting (DEC−SbEC) Codes for MemorySystems”』,ＩＥＩＣＥ  トランスアクションズ  オン  ファンダメンタルズ（IEICETransactions on Fundamentals）,第E85−A巻,第1号,p.273−276,2002年1月
【非特許文献１０】ジー.ウマネサン（G.Umanesan）・イー.フジワラ（E.Fujiwara）共著,『ア  クラス  オフ  コードズ  フォー  コレクティング  シングル  スポッティ  バイト  エラーズ  “A Class of Codes forCorrecting Single Spotty Byte Errors”』,ＩＥＩＣＥ  トランスアクションズ  オン  ファンダメンタルズ（IEICE Transactions on Fundamentals）,第E86−A巻,第3号,p.704−714,2003年3月
【非特許文献１１】エス.ビィー.ウィッカー（S.B.Wicker）・ヴィ.ケイ.バールガバ（V.K.Bhargava）共著,『リードソロモン  コードズ  アンド  ゼア  アプリケーションズ  “Reed−Solomon Codes andTheir Applications”』,ＩＥＥＥ  プレス（IEEEPress）,1994年
【発明の開示】
【発明が解決しようとする課題】
【００１１】
１９８０年代半ばまでは、半導体メモリ素子には、データ１ビットの入出力を有する素子が主に使用されたことから、１素子の誤りを訂正し２素子までの誤りを検出する１ビット誤り訂正・２ビット誤り検出符号（ＳＥＣ−ＤＥＤ符号と称する）が多く使用されていた。ところが、１９８０年代半ばからメモリ素子の高集積化ニーズに対応して、データ４ビットの入出力を有する素子が主流となりはじめ、バイト幅ｂ＝４ビットである前述のＳ４ＥＣ−Ｄ４ＥＤ符号やＳＥＣ−ＤＥＤ−Ｓ４ＥＤ符号が主に使用されるようになってきた。さらに、１９９０年代半ばからは、データ８ビット又はデータ１６ビットの入出力を有する半導体メモリ素子が主流になりつつある。
【００１２】
しかしながら、従来のＳｂＥＣ−ＤｂＥＤ符号のバイト幅ｂに、ｂ＝８またはｂ＝１６を適用する場合に、全体の符号長に対する検査ビット数の占める割合がおよそ３０％から４０％と多大となって、符号化率が低下し、実用的に非常に大きな問題となっていた。
【００１３】
ところで、これらの半導体メモリ素子（ＤＲＡＭ素子）を使用したメモリ装置では、ノイズやアルファ粒子等によって一時故障が発生したり、ＤＲＡＭ素子自体が劣化して動作しなくなる固定故障が発生したりする。最近のＤＲＡＭ素子を用いた装置の８０％以上は一時故障であると言われており、特に、８ビット以上の多ビットデータ入出力を有するＤＲＡＭ素子では、バイト中の１、２、３ビット程度の比較的小さい数のビット誤りが大半であるとされている。
【００１４】
中でも比較的エネルギーレベルの低い電磁ノイズやアルファ粒子による一時誤り、及びメモリセルの固定故障を原因とする１ビット誤りが最も多く、最近では、前記ＤＲＡＭ素子を搭載したモバイル機器が多用されていることから、電磁環境が悪い中での使用も考慮しなければならなくなっている。また、高い高度を飛行する航空機や軍用機で用いられる電子機器中のＤＲＡＭ素子では、宇宙線に起因するエネルギーレベルの高い中性子粒子等の衝突により、２ビット、３ビット程度の誤りを有する一時故障が発生する可能性が高くなっている。さらに、衛星通信や宇宙通信で用いられる宇宙機器に搭載するＤＲＡＭ素子では、エネルギーレベルの高い粒子との衝突によって、大きなダメージを受けてしまうことを考慮する必要があり、この場合に２ビット以上の誤りを考慮しなければならないことが知られている。
【００１５】
以上のようなビット誤りの発生状況が多岐にわたっていることを踏まえれば、パラメータｔ及びｂに任意の値を与えて構成できる前記Ｓｔ／ｂＥＣ−ＳｂＥＤ符号は、８ビット以上のＤＲＡＭ素子を使用したメモリ装置に用いる場合に、非常に実用的な符号方式である。つまり、前記Ｓｔ／ｂＥＣ−ＳｂＥＤ符号は、バイト幅ｂより小さなｔビット（このｔの値は、誤りの傾向を調査して設計者が任意に決めることが可能である）までの１素子の誤り（スポッティバイト誤り）を訂正することが可能な機能、及び発生確率としては小さいもののｔビットを超える１バイト誤りを検出することが可能な機能を備えることにより、従来のバイト単位で行うリードソロモン符号（Reed−Solomon符号）等の誤り制御符号と比較して、大幅に少ない数の検査ビットで誤りを訂正・検出することができる。
【００１６】
また、任意の２素子（隣接した２素子に限らない）にまたがる誤りに対して、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号は、８ビット以上のＤＲＡＭ素子を使用したメモリ装置に用いる場合に、非常に実用的な符号化方式である。つまり、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号は、バイト幅ｂより小さなｔビットまでの１素子の誤りを訂正することが可能な機能（１スポッティバイト誤り訂正、Ｓｔ／ｂＥＣ）と、２素子にまたがるスポッティバイト誤りを検出することが可能な機能（２スポッティバイト誤り検出、Ｄｔ／ｂＥＤ）と、発生確率としては小さいもののｔビットを超える１バイト誤りを検出することが可能な機能（１バイト誤り検出、ＳｂＥＤ）とを備えた符号であり、従来のバイト単位で行う符号方式と比較して、大幅に少ない数の検査ビットで誤りを訂正・検出することができる。
【００１７】
しかしながら、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号においては、２素子にまたがる誤りを訂正することができないという問題を有していた。そのため、２素子のｔ／ｂ誤り（２スポッティバイト誤り）を訂正する機能を有する符号（Ｄｔ／ｂＥＣ符号：Double t−bit  within a b−bit byte Error Correcting Codeと称する）の開発が求められてきている。また、２スポッティバイト誤り以上の誤りを制御する符号、すなわち、理論上、一般にＧＦ（２ｂ）上で距離ｄを有するスポッティバイト誤り訂正符号の構成が求められている。なお、前記“Ｄｔ／ｂＥＣ符号”を、簡単にＧＦ（２ｂ）上でｄ＝５を有する“２スポッティバイト誤り訂正符号”とも称することとする。ここで、ｔは１≦ｔ≦ｂを満足する整数である。
【００１８】
本発明は、上述のような事情に鑑みてなされたものであり、本発明の目的は、２スポッティバイト誤り以上の多重スポッティバイト誤りを制御することができる機能を備えたスポッティバイト誤り訂正・検出方法及び装置を提供することにある。
【課題を解決するための手段】
【００１９】
本発明は、スポッティバイト誤り訂正・検出装置に関し、本発明の上述目的は、入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるスポッティバイト誤り訂正・検出装置であって、前記符号化手段は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることにより、或いは、前記パリティ検査行列は、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、ＧＦ（２ｂ）上で距離ｄ（ｄは３以上の整数）を有する複数のスポッティバイト誤りを訂正・検出する機能を有することにより、或いは、前記パリティ検査行列は、前記距離ｄに対し、
2006060465.tif 000003
個のスポッティバイト誤りを訂正すると共に、ｍ個のスポッティバイト誤りを検出し、かつ、
2006060465.tif 000004
を満たすことにより、或いは、前記ｔ値、ｂ値、ｄ値を任意に設定することにより、或いは、前記情報伝送路は、情報通信システムであることにより、或いは、前記情報伝送路は、メモリシステムであることにより、或いは、前記情報伝送路は、バス線回路であることにより、或いは、前記パリティ検査行列は、前記距離ｄを有するスポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000005
ただし、Ｒ＝（ｄ−１）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ’＝［γｉｈ０’、γｉｈ１’、…、γｉｈｂ−１’］が成立するように構成されることにより、或いは、前記パリティ検査行列は、前記距離ｄを有する伸長スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000006
ただし、Ｒ≧（ｄ−１）ｒ、かつ、（Ｒ−ｒ）は（ｄ−２）の倍数であり、また、Ｎ＝ｂ（ｎ＋２）、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｒ）／（ｄ−２）−１であり、前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、Ｒ≧（ｄ−１）ｒとし、γは２を底とする（Ｒ−ｒ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｒ）／（ｄ−２））の原始元であって、γｉＨ’＝［γｉΦ（ｈ０’）、γｉΦ（ｈ１’）、…、γｉΦ（ｈｂ−１’）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｒ）からＧＦ（２（Ｒ−ｒ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｒ）→ＧＦ（２（Ｒ−ｒ）／（ｄ−２））であることにより、或いは、前記誤り訂正手段は、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力することにより、或いは、前記誤り訂正手段は、並列復号手段と、誤り生成手段と、誤り検出手段と、反転手段とを備え、前記並列復号手段は、前記シンドロームを基にしてＧＦ（２ｒ）上の誤りを生成し、前記誤り生成手段は、前記並列復号手段で生成された前記ＧＦ（２ｒ）上の誤りを変換し、前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、前記誤り検出手段は、前記並列復号手段により訂正できない誤りを検出し、前記反転手段は、前記誤り生成手段から入力される前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、訂正後の受信語を生成することにより、或いは、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する行列Ｈ’に成立するｅ・Ｈ’Ｔ＝ｅ’（ここで、H’ＴはＨ’の行と列を入れ替えた置換行列）の関係式から、ＧＦ（２ｒ）上の誤りｅ’よりＧＦ（２ｂ）上の誤りｅを決定することにより、或いは、前記誤り訂正手段は、並列復号手段と、誤り生成手段と、誤り検出手段と、反転手段とを備え、前記並列復号手段は、前記シンドロームを基にして、ＧＦ（２ｒ）上の誤りを指摘する第１のビット誤りポインタと、ＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号とを生成し、前記誤り生成手段は、前記並列復号手段から入力される前記第１のビット誤りポインタに基づいて、第２のビット誤りポインタを生成し、前記誤り検出手段は、前記並列復号手段で生成された前記第１のビット誤りポインタと前記第１の訂正不可能誤り検出信号とに基づいて、前記受信語の誤り訂正の可���を判断し、前記受信語のビット誤りを訂正できないことを検出した場合に、第２の訂正不可能誤り検出信号を出力し、前記反転手段は、前記誤り生成手段で生成された前記第２のビット誤りポインタ及び前記受信語を基にして、前記第２のビット誤りポインタに対応した前記受信語のビットを反転させることにより、前記受信語の誤りを訂正することによって効果的に達成される。
【００２０】
また、本発明は、スポッティバイト誤り訂正・検出方法に関し、本発明の上述目的は、入力情報データを基に送信語を生成する符号化処理ステップと、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理ステップとを有するスポッティバイト誤り訂正・検出方法であって、前記符号化処理ステップは、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、前記復号処理ステップは、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理ステップと、前記シンドローム生成処理ステップにより生成されたシンドロームを基に、前記受信語の誤りを訂正または検出する誤り訂正処理ステップとを有することにより、或いは、前記パリティ検査行列は、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、ＧＦ（２ｂ）上で距離ｄ（ｄは３以上の整数）を有する複数のスポッティバイト誤りを訂正・検出する機能を有することにより、或いは、前記パリティ検査行列は、前記距離ｄに対し、
2006060465.tif 000007
個のスポッティバイト誤りを訂正すると共に、ｍ個のスポッティバイト誤りを検出し、かつ、
2006060465.tif 000008
を満たすことにより、或いは、前記ｔ値、ｂ値、ｄ値を任意に設定することにより、或いは、前記情報伝送路は、情報通信システムであることにより、或いは、前記情報伝送路は、メモリシステムであることにより、或いは、前記情報伝送路は、バス線回路であることにより、或いは、前記パリティ検査行列は、前記距離ｄを有するスポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000009
ただし、Ｒ＝（ｄ−１）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ’＝［γｉｈ０’、γｉｈ１’、…、γｉｈｂ−１’］が成立するように構成されることにより、或いは、前記パリティ検査行列は、前記距離ｄを有する伸長スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006060465.tif 000010
ただし、Ｒ≧（ｄ−１）ｒ、かつ、（Ｒ−ｒ）は（ｄ−２）の倍数であり、また、Ｎ＝ｂ（ｎ＋２）、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｒ）／（ｄ−２）−１であり、前記Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、…、ｈｂ−１’］に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であって、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが２ｔ＜ｂのときは前記Ｈ’は最小ハミング距離２ｔ＋１を有するパリティ検査行列に等しくなり、Ｒ≧（ｄ−１）ｒとし、γは２を底とする（Ｒ−ｒ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｒ）／（ｄ−２））の原始元であって、γｉＨ’＝［γｉΦ（ｈ０’）、γｉΦ（ｈ１’）、…、γｉΦ（ｈｂ−１’）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｒ）からＧＦ（２（Ｒ−ｒ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｒ）→ＧＦ（２（Ｒ−ｒ）／（ｄ−２））であることにより、或いは、前記誤り訂正処理ステップは、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力することにより、或いは、前記誤り訂正処理ステップは、並列復号処理ステップと、誤り生成処理ステップと、誤り検出処理ステップと、反転処理ステップとを有し、前記並列復号処理ステップは、前記シンドロームを基にしてＧＦ（２ｒ）上の誤りを生成し、前記誤り生成処理ステップは、前記並列復号処理ステップで生成された前記ＧＦ（２ｒ）上の誤りを変換し、前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、前記誤り検出処理ステップは、前記並列復号処理ステップで訂正できない誤りを検出し、前記反転処理ステップは、前記誤り生成処理ステップで生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、訂正後の受信語を生成することにより、或いは、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する行列Ｈ’に成立するｅ・Ｈ’Ｔ＝ｅ’の関係式から、ＧＦ（２ｒ）上の誤りｅ’よりＧＦ（２ｂ）上の誤りｅを決定することにより、或いは、前記誤り訂正処理ステップは、並列復号処理ステップと、誤り生成処理ステップと、誤り検出処理ステップと、反転処理ステップとを有し、前記並列復号処理ステップは、前記シンドロームを基にして、ＧＦ（２ｒ）上の誤りを指摘する第１のビット誤りポインタと、ＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号とを生成し、前記誤り生成処理ステップは、前記並列復号処理ステップで生成された前記第１のビット誤りポインタに基づいて、第２のビット誤りポインタを生成し、前記誤り検出処理ステップは、前記並列復��処理ステップで生成された前記第１のビット誤りポインタと前記第１の訂正不可能誤り検出信号とに基づいて、前記受信語の誤り訂正の可否を判断し、前記受信語のビット誤りを訂正できないことを検出した場合に、第２の訂正不可能誤り検出信号を出力し、前記反転処理ステップは、前記誤り生成処理ステップで生成された前記第２のビット誤りポインタ及び前記受信語を基にして、前記第２のビット誤りポインタに対応した前記受信語のビットを反転させることにより、前記受信語の誤りを訂正することによって効果的に達成される。
【発明の効果】
【００２１】
本発明に係るスポッティバイト誤り訂正・検出方法及び装置によれば、符号を表現するパリティ検査行列と入力情報データとを基に生成した検査情報を前記入力情報データに付加した送信語が、情報伝送路中で発生した誤りを有する可能性のある受信語に対し、前記パリティ検査行列を基にシンドロームを生成するとともに、このシンドロームを基に前記受信語の誤りを訂正または検出するようにしているので、１バイト中の２ビット、３ビット等のｔビットまでの誤りであるスポッティバイト誤りに対し、任意の数のスポッティ誤り（誤りの傾向を調査して設計者が任意に決めることができる）を訂正・検出する機能を有するスポッティバイト誤り制御符号を実現することができた。
【００２２】
これにより、誤りを検出または訂正する符号であるパリティ検査行列の構成や復号の処理手順を、誤りの発生状況ごとに対応させる必要がなく統一的に扱うことが可能となり、本発明の符号機能におけるｔ値、ｂ値、ｄ値を任意に設定するだけで、パリティ検査行列Ｈや復号手順を統一的に扱うことが可能となり、誤りの発生状態に柔軟に対応できる符号機能を提供することができる。
【００２３】
また、ｂビットであるバイト長よりも小さな整数ビット長ｔを選ぶことにより、従来のバイト誤り制御符号（ｔ＝ｂに相当）と比較して、検査ビット数を大幅に少なくすることが可能となる。これにより、符号長に対する検査ビット数の占める割合を小さくさせて符号化率を格段に向上することが可能となり、高効率かつ高信頼性のあるデータ転送を実現することができる。
【００２４】
要するに、従来の符号技術では存在しない、『多重スポッティバイト誤りを制御できる』といった優れた機能を備える本発明のスポッティバイト誤り訂正・検出方法及び装置によれば、従来のリードソロモン符号（Reed−Solomon符号）による多重バイト誤り制御符号と比較して、検査ビット数を少なくして符号化率を向上させることができ、また、ビット誤りの発生状態に柔軟に対応できる符号機能を提供できるといった顕著な効果を奏する。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を実施するための最良の形態について、図面を参照しながら詳細に説明する。
【００２６】
本発明を説明するための用語を次のように定義する。まず、本発明の実施形態において、対象とするディジタルデータとは、０と１との組合せの信号（２進化符号）であり、ビット誤りの発生とは、符号語中の任意のビットが、０→１または１→０になることを意味することとする。また、スポッティバイト誤りの発生とは、ｂビットからなるバイト中のｔビット（ｔ≦ｂ）までが０→１または１→０になることを意味することとする。なお、本発明の実施形態において、「誤り」とある場合は、特に明記していない限り、前記「ビット誤り」、「スポッティバイト誤り」のすべてを包含していることとする。
【００２７】
まず、本発明に係るスポッティバイト誤り訂正・検出装置１００の全体構成について説明する。図１は、本発明のスポッティバイト誤り訂正・検出装置１００（以下、スポッティバイト装置１００と略す）の概略構成を示すブロック図である。図１に示すように、スポッティバイト装置１００は、符号化回路２、回路３、復号回路４等を備えた構成になっている。
【００２８】
符号化回路２は、対象のディジタルデータ（以下、入力情報データ３０と称する）に対して、誤りの訂正・検出を行う検査情報を生成する回路である。なお、検査情報は、任意個の検査ビットより構成されている。
【００２９】
回路３は、メモリ等の通信路に相当し、本実施形態では、回路３を経たデータには誤りが含まれる可能性が存在する構成としている。つまり、符号化回路２より出力されて回路３に入力されるデータには誤りが生じていないのに対して、回路３から出力されるデータには、誤りが発生している場合を含んでいる。
【００３０】
復号回路４は、シンドローム生成回路１と誤り訂正回路５とを備えた構成になっている。復号回路４は、受信語３２に誤りが含まれているか否かを検出し、その誤り箇所を特定して訂正を行うための回路である。復号回路４の詳細な構成については、後述する復号処理で説明する。
【００３１】
なお、後述する符号化処理及び復号処理では、ガロア体理論に基づいた行列演算を行うことから、符号化回路２、復号回路４、または通信路中における各データを、英字で付した行列、またはベクトルで表現する。具体的には、例えば、入力情報データＤ、符号（パリティ検査行列）Ｈ、検査情報Ｃ、送信語Ｖ、受信語Ｖ’、シンドロームＳと表している。
【００３２】
次に、本発明のスポッティバイト装置１００の全体動作について説明する。図２は、図１に示された本発明のスポッティバイト装置１００の全体動作の処理手順を示すフローチャートである。
【００３３】
図２に示されるように、まず、符号化回路２では、入力情報データ（Ｄ）３０が入力されると、詳細については後述するパリティ検査行列（Ｈ）を用いて検査情報（Ｃ）を生成する（ステップＳ２００）。次に、符号化回路２では、この検査情報（Ｃ）を入力情報データ（Ｄ）３０に付加して送信語（Ｖ）３１として、メモリ等の通信路である回路３に送出する（ステップＳ２０１）。そして、回路３を経て誤りを含む可能性のある受信語（Ｖ’）３２は、復号回路４に入力される（ステップＳ２０２）。
【００３４】
次に、復号回路４では、まず、符号化回路２で用いたパリティ検査行列（Ｈ）を利用して、入力された受信語（Ｖ’）３２に誤りが発生しているか否かを調べる。具体的には、復号回路４のシンドローム生成回路１が、符号を表現しているパリティ検査行列（Ｈ）を転置させた転置行列（ＨＴ）を、受信語（Ｖ’）３２に対して乗算することによりシンドローム（Ｓ）を生成する（ステップＳ２０３）。シンドローム（Ｓ）３３の値は、受信語（Ｖ’）３２に応じて変化するため、受信語（Ｖ’）３２に誤りが含まれているかを判断することが可能となる。
【００３５】
そこで、復号回路４の誤り訂正回路５は、前記シンドローム（Ｓ）３３の値に基づいて、まず誤りを検出したか否か（ステップＳ２０４）、検出した場合に、誤り訂正が可能か否かを判断し（ステップＳ２０５）、前記判断の結果、訂正可能であれば誤りの訂正を行う（ステップＳ２０６）。そして、誤り訂正回路５は、受信語Ｖ’に対してスポッティバイト誤りの訂正処理を施した場合、訂正後のＶ’を受信語出力情報データ（Ｖ*）３４として出力する（ステップＳ２０７）。これに対して、ステップＳ２０５の判断の結果、訂正不可能なスポッティバイト誤り等が検出された場合には、誤り訂正回路５は、訂正不可能な誤り検出信号としてのＵＣＥ（Uncorrectable  Error）信号３５を出力する（ステップＳ２０８）。
【００３６】
次に、前述した符号化回路２及び復号回路４で用いられるパリティ検査行列（Ｈ）の構成について、詳細に説明する。本発明のパリティ検査行列Ｈ（Ｈマトリクス、符号マトリクス、または単に検査行列とも称される）は、複数のスポッティバイト誤りを訂正・検出する機能を有する符号である。
【００３７】
本実施の形態では、任意のｄ（ｄは３以上の整数）、ｔ（ｔは１以上ｂ以下の整数）、及びｂ（２以上の整数）に対して構成できる一般的な符号構成法を提示するとともに、その符号により実際に誤りの訂正・検出ができる方法を示し、またそのための符号化回路および復号回路を提示し、前記符号化回路及び復号回路によって誤りが具体的に訂正・検出できることを示す。
【００３８】
なお、本符号構成法において、ｔ＝ｂのとき、正確には後述するようにｔ≧ｂ／２のとき、従来のバイト誤り制御符号であるリード・ソロモン符号（ＲＳ符号）に一致する。
【００３９】
いま、Ｋビットの入力情報データ（Ｄ）３０に対してＲビットの検査情報（Ｃ）を付加し、ある機能を満足するＮ＝Ｋ＋Ｒビットの長さを有する送信語Ｖ（Ｎビットの行ベクトル）を構成することができたときに、この送信語（Ｖ）と、符号を規定するＲ行Ｎ列の２元パリティ検査行列（Ｈ）との間には、Ｖ・ＨＴ＝０の関係が成立する。ここで、ＨＴはパリティ検査行列（Ｈ）の行と列を入れ替えて生成した置換行列であり、また、右辺の０はＲビットの零行ベクトルを示している。
【００４０】
本実施形態では、距離ｄを有するスポッティバイト誤り制御符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数１に示すような構成としている。
【００４１】
【数１】
2006060465.tif 000011
ただし、Ｒ＝（ｄ−１）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、上記数１を構成する行列Ｈ’は、下記数２に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する。
【００４２】
【数２】
2006060465.tif 000012
また、ランクがｂに等しいときはランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、ランクが２ｔ＜ｂのとき行列Ｈ’は最小ハミング距離２ｔ＋１を有する符号の検査行列、すなわち、ｔビット誤り訂正機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しい。
【００４３】
次に、γを２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元とするときに、γｉＨ’は下記数３で定義することができる。
【００４４】
【数３】
2006060465.tif 000013
このとき、最大符号長Ｎは、Ｎ＝ｂ（２ｒ―１）である。
【００４５】
上記数１に示したパリティ検査行列（Ｈ）は、パラメータｔ≧ｂ／２とした場合Ｈ’はランクｂを有することから、従来のＲＳ符号のパリティ検査行列と一致する。
【００４６】
また、本実施形態では、伸長符号を定義することができる。距離ｄを有する伸長スポッティバイト誤り制御符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）は、下記数４に示すような構成とすることができる。
【００４７】
【数４】
2006060465.tif 000014
ただし、Ｒ≧（ｄ−１）ｒ、かつ（Ｒ−ｒ）は（ｄ−２）の倍数であり、Ｎ＝ｂ（ｎ＋２）、０≦ｉ≦ｎ−１、（Ｒ−ｒ）は（ｄ−２）の倍数とし、ｎ＝２（Ｒ−ｒ）／（ｄ−２）−１である。上記数４を構成する行列Ｈ’は、下記数５に示すｒ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ、ｂ）を満足する。
【００４８】
【数５】
2006060465.tif 000015
また、ランクがｂに等しいときはランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、ランクが２ｔ＜ｂのとき行列Ｈ’は最小ハミング距離２ｔ＋１を有する符号の検査行列、すなわち、ｔビット誤り訂正機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなる。
【００４９】
次に、Ｒ≧（ｄ−１）ｒかつＲ−ｒはｄ−２の倍数とし、γを２を底とする（Ｒ−ｒ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｒ）／（ｄ−２））の原始元とするときに、γｉＨ’は下記数６で定義することができる。
【００５０】
【数６】
2006060465.tif 000016
ここで、Φは加法のもとでＧＦ（２ｒ）からＧＦ（２（Ｒ−ｒ）／（ｄ−２））への準同型写像（homomorphism）である。すなわち、Φ：ＧＦ（２ｒ）→ＧＦ（２（Ｒ−ｒ）／（ｄ−２））である。このとき、最大符号長Ｎは、Ｎ＝ｂ（２（Ｒ−ｒ）／（ｄ−２）＋１）である。また、Ｒ≧（ｄ−１）ｒであることから、数４のＨの２行目から下の行に用いるＨ’の行数ｒ’は、ｒより大きい値をとることができ、数４で表される符号は、（ｄ−２）ビットずつ検査ビット数を増大させることにより、任意の符号長に対して構成できる符号であることに注意する必要がある。
【００５１】
上記数４に示したパリティ検査行列（Ｈ）は、パラメータｔ≧ｂ／２とした場合に、Ｈ’がランクｂを有することから、従来の２次伸長ＲＳ符号のパリティ検査行列と一致する。
【００５２】
次に、上記数１に示したパリティ検査行列（Ｈ）で表される符号が、距離ｄに対し、
2006060465.tif 000017
を満たす訂正数
2006060465.tif 000018
、検出数
2006060465.tif 000019
を有していることを具体的に示す。例えば、距離ｄ＝５の２重スポッティバイト誤り訂正符号の場合に、
2006060465.tif 000020
となる。一般に、
2006060465.tif 000021
において、パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、…、Ｈｎ−１］が、以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【００５３】
【数７】
2006060465.tif 000022
【００５４】
【数８】
2006060465.tif 000023
【００５５】
【数９】
2006060465.tif 000024
ここで、１バイト中のｔビットまでの誤りの集合をＥｔ／ｂとし、ｅｉは誤りの集合Ｅｔ／ｂに含まれる任意の誤りとする。また、ｉ１、ｉ２、…、ｉｋ、…、ｉｄ−１（０≦ｉ１、ｉ２、…、ｉｋ、…、ｉｄ−１≦ｎ−１）はすべて異なるものとする。
【００５６】
スポッティバイト誤り訂正は、前述したシンドローム生成回路１が生成するシンドローム（Ｓ）３３を用いて実行する。ここで、シンドローム（Ｓ）３３と前記パリティ検査行列（Ｈ）との関係は、Ｓ＝Ｖ’・ＨＴで表される。いま、受信語（Ｖ’）３２が元々の送信語（Ｖ）３１に対して誤り（Ｅ）を含み、Ｖ’＝Ｖ＋Ｅで表されるとき、シンドローム（Ｓ）３３は、Ｓ＝Ｖ’・ＨＴ＝（Ｖ＋Ｅ）・ＨＴ＝Ｖ・ＨＴ＋Ｅ・ＨＴとなる。
【００５７】
前述したように、Ｖ・ＨＴ＝０の関係が成立していることから、結局、シンドロームＳ＝Ｅ・ＨＴが成り立つ。つまり、シンドローム（Ｓ）３３は、送信語（Ｖ）３１に影響されずに誤り（Ｅ）のみで決まることから、シンドローム（Ｓ）３３に基づいてスポッティバイト誤り訂正を行うことが可能か否かは、パリティ検査行列（Ｈ）と誤り（Ｅ）とから計算されるＥ・ＨＴの値の結果によって決定できるものである。
【００５８】
上記数７、数８、数９に示した必要十分条件は、距離ｄに対し、訂正・検出可能なすべてのスポッティバイト誤りのシンドロームと訂正可能な他のすべてのスポッティバイト誤りのシンドロームが異なることを示している。すなわち、ｍ個以下のスポッティバイト誤りのシンドロームと他の
2006060465.tif 000025
個以下のスポッティバイト誤りのシンドロームが異なればよい。よって、
2006060465.tif 000026
個のスポッティバイト誤りのシンドローム和が０とならなければよい。
【００５９】
数７は、ｋ個のスポッティバイト誤りのシンドロームが同じバイトに生じた他のｋ（２ｋ≦ｄ−１）個のスポッティバイト誤りのシンドロームと異なることを示している。また、数８は、ｍ個のスポッティバイト誤りと
2006060465.tif 000027
個のスポッティバイト誤りが生じ、うち
2006060465.tif 000028
バイトにおいて異なる２個のスポッティバイト誤りが同じバイトに生じ、他のｊバイトにおいてそれぞれ１個のスポッティバイト誤りが生じている場合であり、これらのシンドロームが異なることを示している。さらに、数９は、ｍ個のスポッティバイト誤りと
2006060465.tif 000029
個のスポッティバイト誤りがすべて異なるバイトに生じている場合であり、それぞれのシンドロームが異なることを示している。
【００６０】
ここで、（ｅｉ＋ｅｉ＋１）は、１個のスポッティバイト誤りを包含するため、（ｄ−１）個のスポッティバイト誤りのシンドローム和が０とならないことを示すことにより、（ｄ−１）個未満のスポッティバイト誤りのシンドロームが異なることを示すことができる。
【００６１】
よって、数１に示すパリティ検査行列で表現される符号が、上記数７、数８、数９に示した必要十分条件を満たすことを示すことにより、距離ｄに対し
2006060465.tif 000030
を満足する訂正数
2006060465.tif 000031
、検出数
2006060465.tif 000032
を有していることを以下に示す。
＜１＞必要十分条件（数７）を満たしていることの証明
シンドロームＳとして、下記数１０の関係が成立していると仮定する。
【００６２】
【数１０】
2006060465.tif 000033
数１０において、（ｅ１＋ｅ２）・Ｈ’Ｔ、（ｅ３＋ｅ４）・Ｈ’Ｔ、…、（ｅ２ｋ−１＋ｅ２ｋ）・Ｈ’Ｔをそれぞれｘ１、ｘ２、…、ｘｋ（ここで、Ｈ’はランクがＭｉｎ（２ｔ、ｂ）より、ｘ１≠０、ｘ２≠０、…、ｘｋ≠０）と表すと、下記数１１が得られる。
【００６３】
【数１１】
2006060465.tif 000034
数１１において、上からｋ（＜ｄ−１）個の式を行列の形で表すと、下記数１２が得られる。
【００６４】
【数１２】
2006060465.tif 000035
数１２におけるｋ行ｋ列の行列は、ヴァンデルモンドの行列の形をしているため、正則行列である。よって、数１２の両辺に左からこの行列の逆行列を乗算すると、下記数１３が得られる。
【００６５】
【数１３】
2006060465.tif 000036
数１３は、ｘ１＝０、ｘ２＝０、…、ｘｋ＝０を意味しており、これは前提であるｘ１≠０、ｘ２≠０、…、ｘｋ≠０に矛盾する。よって、数１で表される符号は、必要十分条件（数７）を満たしている。
＜２＞必要十分条件（数８）を満たしていることの証明
シンドロームＳとして、下記数１４の関係が成立したと仮定する。
【００６６】
【数１４】
2006060465.tif 000037
数１４において、（ｅ１＋ｅ２）・Ｈ’Ｔ、…、（ｅ２ｋ−１＋ｅ２ｋ）・Ｈ’Ｔ、ｅ２ｋ＋１・Ｈ’Ｔ、…、ｅ２ｋ＋ｊ・Ｈ’Ｔをそれぞれｘ１、…、ｘｋ、ｘｋ＋１、…、ｘｋ＋ｊ（ここで、Ｈ’はランクがＭｉｎ（２ｔ、ｂ）より、ｘ１≠０、…、ｘｋ≠０、ｘｋ＋１≠０、…、ｘｋ＋ｊ≠０）と表すと、下記数１５が得られる。
【００６７】
【数１５】
2006060465.tif 000038
数１５において、上からｋ＋ｊ（＜ｄ−１）個の式を行列の形で表すと、下記数１６が得られる。
【００６８】
【数１６】
2006060465.tif 000039
数１６における（ｋ＋ｊ）行（ｋ＋ｊ）列の行列は、ヴァンデルモンドの行列の形をしているため、正則行列である。よって、数１６の両辺に左からこの行列の逆行列を乗算すると、下記数１７が得られる。
【００６９】
【数１７】
2006060465.tif 000040
数１７は、ｘ１＝０、ｘ２＝０、…、ｘｋ＋ｊ＝０となり、前提であるｘ１≠０、ｘ２≠０、…、ｘｋ＋ｊ≠０に矛盾する。よって、数１で表される符号は、必要十分条件（数８）を満たしている。
＜３＞必要十分条件（数９）を満たしていることの証明
シンドロームＳとして、下記数１８の関係が成立したと仮定する。
【００７０】
【数１８】
2006060465.tif 000041
数１８において、ｅ１・Ｈ’Ｔ、ｅ２・Ｈ’Ｔ、…、ｅｄ−１・Ｈ’Ｔをそれぞれｘ１、ｘ２、…、ｘｄ−１（ここで、Ｈ’はランクがＭｉｎ（２ｔ、ｂ）より、ｘ１≠０、ｘ２≠０、…、ｘｄ−１≠０）と表すと、下記数１９が得られる。
【００７１】
【数１９】
2006060465.tif 000042
数１９を行列の形で表すと、下記数２０が得られる。
【００７２】
【数２０】
2006060465.tif 000043
数２０における（ｄ−１）行（ｄ−１）列の行列は、ヴァンデルモンドの行列の形をしているため、正則行列である。よって、上記数２０の両辺に左から逆行列をかけると、下記数２１が得られる。
【００７３】
【数２１】
2006060465.tif 000044
数２１は、ｘ１＝０、ｘ２＝０、…、ｘｄ−１＝０となり、前提であるｘ１≠０、ｘ２≠０、…、ｘｄ−１≠０に矛盾する。よって、数１で表される符号は、必要十分条件（数９）を満たしている。
【００７４】
したがって、前述した＜１＞〜＜３＞における証明結果より、上記数１に示すパリティ検査行列（Ｈ）は、距離ｄに対し、受信語（Ｖ’）３２に含まれる
2006060465.tif 000045
個以下のスポッティバイト誤りを訂正し、ｍ個以下のスポッティバイト誤りを検出する機能を有していることが証明できた。
【００７５】
また、上記数４に示したパリティ検査行列（Ｈ）で表される伸長符号も、同様に上記数７、数８、数９に示した必要十分条件を満たすことを示すことにより、距離ｄに対し、
2006060465.tif 000046
を満たす訂正数
2006060465.tif 000047
、検出数
2006060465.tif 000048
を有していることを示すことができる。
【００７６】
ここでは、具体的な符号パラメータを与えて、上記数１に示すパリティ検査行列（Ｈ）を構成できることを示す。なお、このパリティ検査行列（Ｈ）は、あくまで一例であって、これに限定されないことは言うまでもない。
【００７７】
いま、読み書きデータ幅として、８ビットを有するメモリ素子を使用したメモリシステムを対象に、ｄ＝５、ｔ＝２、ｂ＝８のパラメータを与え、バイト内２ビット以下の誤りをスポッティバイト誤りとして、２スポッティバイト誤りを訂正するＤ２／８ＥＣ符号のパリティ検査行列（Ｈ）を構成することとする。このとき、Ｍｉｎ（２ｔ、ｂ）＝Ｍｉｎ（４、８）＝４より、行列Ｈ’としてランク４を有する４ビット誤り検出符号の検査行列を構成すればよい。この一例として、下記数２２に示す６×８（６行８列を意味する）行列を示す。
【００７８】
【数２２】
2006060465.tif 000049
次に、γをＧＦ（２）上の６次の原始多項式ｇ（ｘ）＝ｘ６＋ｘ＋１の根とすると、γは、６次の列ベクトルγ＝（０１００００）Ｔと表現することができる。
【００７９】
つまり、γのべき表示γｉとベクトル表示との対応を示すと、次のようになる。
γ０＝（１０００００）Ｔ、 γ１＝（０１００００）Ｔ、 γ２＝（００１０００）Ｔ、
γ３＝（０００１００）Ｔ、 γ４＝（００００１０）Ｔ、 γ５＝（０００００１）Ｔ、
γ６＝（１１００００）Ｔ、 γ７＝（０１１０００）Ｔ、 γ８＝（００１１００）Ｔ、
γ９＝（０００１１０）Ｔ、 γ１０＝（００００１１）Ｔ、γ１１＝（１１０００１）Ｔ、
γ１２＝（１０１０００）Ｔ、γ１３＝（０１０１００）Ｔ、γ１４＝（００１０１０）Ｔ、
γ１５＝（０００１０１）Ｔ、γ１６＝（１１００１０）Ｔ、γ１７＝（０１１００１）Ｔ、
γ１８＝（１１１１００）Ｔ、γ１９＝（０１１１１０）Ｔ、γ２０＝（００１１１１）Ｔ、
γ２１＝（１１０１１１）Ｔ、γ２２＝（１０１０１１）Ｔ、γ２３＝（１００１０１）Ｔ、
γ２４＝（１０００１０）Ｔ、γ２５＝（０１０００１）Ｔ、γ２６＝（１１１０００）Ｔ、
γ２７＝（０１１１００）Ｔ、γ２８＝（００１１１０）Ｔ、γ２９＝（０００１１１）Ｔ、
γ３０＝（１１００１１）Ｔ、γ３１＝（１０１００１）Ｔ、γ３２＝（１００１００）Ｔ、
γ３３＝（０１００１０）Ｔ、γ３４＝（００１００１）Ｔ、γ３５＝（１１０１００）Ｔ、
γ３６＝（０１１０１０）Ｔ、γ３７＝（００１１０１）Ｔ、γ３８＝（１１０１１０）Ｔ、
γ３９＝（０１１０１１）Ｔ、γ４０＝（１１１１０１）Ｔ、γ４１＝（１０１１１０）Ｔ、
γ４２＝（０１０１１１）Ｔ、γ４３＝（１１１０１１）Ｔ、γ４４＝（１０１１０１）Ｔ、
γ４５＝（１００１１０）Ｔ、γ４６＝（０１００１１）Ｔ、γ４７＝（１１１００１）Ｔ、
γ４８＝（１０１１００）Ｔ、γ４９＝（０１０１１０）Ｔ、γ５０＝（００１０１１）Ｔ、
γ５１＝（１１０１０１）Ｔ、γ５２＝（１０１０１０）Ｔ、γ５３＝（０１０１０１）Ｔ、
γ５４＝（１１１０１０）Ｔ、γ５５＝（０１１１０１）Ｔ、γ５６＝（１１１１１０）Ｔ、
γ５７＝（０１１１１１）Ｔ、γ５８＝（１１１１１１）Ｔ、γ５９＝（１０１１１１）Ｔ、
γ６０＝（１００１１１）Ｔ、γ６１＝（１０００１１）Ｔ、γ６２＝（１００００１）Ｔ
これより、上記数２２に示す行列Ｈ’は、Ｈ’＝［γ０γ１γ２γ３γ４γ５γ１８γ２０］と表すことができる。よって、上記数１に示したパリティ検査行列（Ｈ）は、このＨ’を用いて、具体的な（５０４、４８０）Ｄ２／８ＥＣ符号を構成することができる。この符号の最後から４１６列削除することによって得られた（８８、６４）Ｄ２／８ＥＣ符号の検査行列を図３に示す。
【００８０】
なお、図３に示すように、パリティ検査行列（Ｈ）のＨ’に相当する行単位の箇所を明確化するため、その境界に実線を引いて示している。
【００８１】
いま、パリティ検査行列（Ｈ）の構成要素であるγ３Ｈ’が、図３に示す実際のビット値と対応しているかを具体的に確認する。前述したように、Ｈ’＝［γ０γ１γ２γ３γ４γ５γ１８γ２０］より、γ３Ｈ’＝γ３［γ０γ１γ２γ３γ４γ５γ１８γ２０］＝［γ３γ４γ５γ６γ７γ８γ２１γ２３］となる。このべき表示をベクトル表示（例えば、γ０＝（１０００００）Ｔ等）に変換すれば、図３に示すａ部分に相当し、このａ部分は明らかにパリティ検査行列（Ｈ）のγ３Ｈ’部分である。同様にして、パリティ検査行列（Ｈ）における他の構成要素についても、ベクトル表示に変換すれば、全体として図３に示すビット表現の２４行８８列の構成となる。
【００８２】
また、ｔ＝３に対しては、Ｍｉｎ（２ｔ、ｂ）＝６より、行列Ｈ’はランク６を有し、また、符号長８ビットを有する６ビット誤り検出符号の検査行列であり、一例として下記数２３に示す７×８の行列を構成することができる。
【００８３】
【数２３】
2006060465.tif 000050
ｔ＝４、５、６、７については、Ｈ’は８×８の単位行列に等しくなり、パリティ検査行列（Ｈ）は、ＲＳ符号のパリティ検査行列と一致する。
【００８４】
なお、以上は最近最も使用されている、バイト幅ｂ＝８ビット入出力を有する半導体メモリ素子を対象として、パリティ検査行列Ｈ（符号）の一例を構成して説明したが、他にも多く使用されている多ビット入出力素子、例えば、ｂ＝１６ビット入出力を有する素子等に対しても、また、２以上の任意の整数値を有するｂに対して、Ｄｔ／ｂＥＣ符号を構成できることは明らかである。
【００８５】
また、以上は距離ｄ＝５として、パリティ検査行列Ｈの一例を構成して説明したが、任意の距離ｄに対して、符号すなわちパリティ検査行列が構成できることも明らかである。
【００８６】
このように、前記ではパリティ検査行列（Ｈ）の構成例を示したが、次に、このパリティ検査行列（Ｈ）を用いて処理する符号化と復号の具体的な方法及びそれぞれの回路構成を示す。
＜Ａ＞符号化の方法及びこれを実現する回路の構成について
まず、図１に示す符号化回路２が行う符号化方法について説明する。
【００８７】
符号化回路２では、入力情報データＤ（行ベクトル）３０と、図３に示すパリティ検査行列（Ｈ）を基本行変形して得られるパリティ検査行列（Ｈ）の情報部ＨＲを用いて、検査情報Ｃ（行ベクトル）を生成する。この検査情報（Ｃ）の生成は、下記数２４により求めることができる。
【００８８】
【数２４】
2006060465.tif 000051
具体的には、符号化回路２は、入力情報データ（Ｄ）３０の情報ビット長６４ビット及び検査ビット長２４ビットを基に、パリティ検査行列Ｈである（５０４、４８０）Ｄ２／８ＥＣ符号を構成した後に、後半４１６ビットに相当する列ベクトル４１６列を削除することにより、符号ビット長８８ビット及び情報長６４ビットを有する図３に示す（８８、６４）Ｄ２／８ＥＣ符号を構成することができる。この符号のパリティ検査行列Ｈを基本行変形すると、組織符号としてのパリティ検査行列Ｈを構成することができる。図４は、（８８、６４）Ｄ２／８ＥＣ組織符号の検査行列を示している。
【００８９】
図４に示す（８８、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列において、ｄ０〜ｄ６３が情報ビットに相当し、ｃ０〜ｃ２３が検査ビットに相当する。ここで、図４に示す符号化用（８８、６４）Ｄ２／８ＥＣ符号のパリティ検査行列において、情報ビットに相当するｄ０〜ｄ６３の列ベクトルを集めた行列が、パリティ検査行列の情報部ＨＲとなる。
【００９０】
ここで、符号化では図４に示す検査行列を使用し、復号では図３に示す検査行列を使用する。基本行変形して得られた行列は、もとの行列と等価であり、図４に示す検査行列の符号は、図３に示す検査行列の符号とその性質は全く変化しない。これより、符号化においては、図４に示す検査行列を使用することとする。
【００９１】
次に、符号化回路２は、上記数２４を基に、２４ビットの検査情報（Ｃ）を生成する。上記数２４に示すＣ＝Ｄ・ＨＲＴから明らかなように、例えば、検査情報（Ｃ）における検査ビットｃ０を生成するには、図４に示す符号化用（８８、６４）Ｄ２／８ＥＣ符号の行列の１行目において、ｃ０に対応するビットを除いて“１”が存在する箇所に対応するビットのＧＦ（２）上の和（すなわち、２を法とする和：ｍｏｄ２）をとる演算を行えばよい。
【００９２】
例えば、検査ビットｃ０を求める場合に、ｃ０に対応するビットを除いて“１”が存在しているのは、ｄ２、ｄ３、ｄ４、ｄ５、ｄ９、ｄ１０、ｄ１２、ｄ１８、ｄ１９、ｄ２４、ｄ２８、ｄ２９、ｄ３０、ｄ３５、ｄ３６、ｄ３７、ｄ３８、ｄ３９、ｄ４０、ｄ４１、ｄ４２、ｄ４６、ｄ４７、ｄ５０、ｄ５２、ｄ５４、ｄ５６であり、これら２７個のビットについて２を法とする和（ｍｏｄ２）をとればよい。これを実現するには、図５に示すように、前記２７ビットを多入力パリティチェック回路２０（０）を構成すればよく、この多入力パリティチェック回路２０（０）の出力が検査ビットｃ０となる。他の検査ビットｃ１〜ｃ２３についても、検査ビットｃ０と同様にして生成することができる。２４ビットの検査ビットｃ０〜ｃ２３を並列に生成する符号化回路２（多入力パリティチェック回路２０（０）〜２０（２３）からなる）の構成を図５に示す。
【００９３】
次に、符号化回路２によって生成した検査情報（Ｃ）を、入力情報データ（Ｄ）３０に付加した符号語を下記数２５に示す。これが回路３に送られる送信語（Ｖ）（８８ビットのベクトル）となる。
【００９４】
【数２５】
2006060465.tif 000052
＜Ｂ＞復号の方法及びこれを実現する回路の構成について
次に、送信語（Ｖ）３１に誤りが生じたとき（すなわち、受信語３２に誤りが含まれているとき）に、その誤りに対する訂正・検出処理が、図３に示す（８８、６４）Ｄ２／８ＥＣ符号を用いて生成されるシンドローム（Ｓ）３３の値に基づいて可能なことを示す。
【００９５】
図３に示す（８８、６４）Ｄ２／８ＥＣ符号の検査行列は、距離ｄ＝５を有することから、上記数１に示すように、パリティ検査行列Ｈ’による４段構成を有する。これより、１段目より得られるｒ＝６ビットのシンドロームをＳI、２段目より得られるｒ＝６ビットのシンドロームをＳII、３段目より得られるｒ＝６ビットのシンドロームをＳIII、４段目より得られるｒ＝６ビットのシンドロームをＳIVとする。
【００９６】
これらの情報を用いて、次のように誤りの訂正、検出を行う。受信語（Ｖ’）３２とパリティ検査行列（Ｈ）とから、シンドローム（Ｓ）３３は、下記数２６により求めることができる。
【００９７】
【数２６】
2006060465.tif 000053
ここで、ＳI、ＳII、ＳIII、ＳIV∈ＧＦ（２ｒ）は、ｒ次の行ベクトルである。上記数４に示す伸長符号の場合に、ＳI∈ＧＦ（２ｒ）は、ｒ次の行ベクトルであり、また、ＳII、ＳIII、ＳIV∈ＧＦ（２（Ｒ−ｒ）／３）は、それぞれ（Ｒ−ｒ）／３次の行ベクトルである。
【００９８】
なお、シンドローム（Ｓ）３３は、例えば、ｉI番目のバイトにｅIの誤り、ｉII番目のバイトにｅIIの誤りが生じているときに、下記数２７となる。
【００９９】
【数２７】
2006060465.tif 000054
ここで、ｅI・Ｈ’Ｔ、ｅII・Ｈ’Ｔ（∈ＧＦ（２ｒ））をＧＦ（２ｒ）上の誤りｅI’、ｅII’とすると、前記シンドローム（Ｓ）３３は、下記数２８となる。
【０１００】
【数２８】
2006060465.tif 000055
数２８に示すシンドロームは、誤りｅI’、ｅII’を有する距離ｄ＝５のＲＳ符号におけるシンドロームの式と一致する。よって、距離ｄ＝５を有するＧＦ（２ｒ）上のＲＳ符号の復号法を用いることで、誤り位置ｉI、ｉII及びＧＦ（２ｒ）上の誤りｅI’、ｅII’を求めることができる。また、誤り位置が求まらない場合に、誤りの訂正が不可能として誤りを検出する。
【０１０１】
次に、ＧＦ（２ｒ）上の誤りｅI’、ｅII’からＧＦ（２ｂ）上の誤りｅI、ｅIIを求める。ｅI・Ｈ’Ｔ＝ｅI’、ｅII・Ｈ’Ｔ＝ｅII’において、Ｈ’はランクがＭｉｎ（２ｔ、ｂ）＝（４、８）＝４より、ｅI→ｅI’、ｅII→ｅII’は単射の関係となっている。よって、ＧＦ（２ｂ）上の誤りｅI、ｅIIを求めることができる。
【０１０２】
ＲＳ符号に対する復号は、距離ｄが小さい符号に対して、並列復号法を用いて実現することができる。この並列復号法の一般的構成は、「バースト誤りパターン生成方法及びバーストおよびバイト誤り検出・訂正装置」（特許文献３参照）に開示されている。
【０１０３】
特許文献３に開示された並列復号法によれば、例えば、ｄ＝５の符号に対しては、次のような手順により復号する。
【０１０４】
まず、ＲＳ符号のパリティ検査行列
2006060465.tif 000056
に対し、Ｒ×２ｒの行列
2006060465.tif 000057
を構成する。ただし、
2006060465.tif 000058
はＲ×ｒの小行列である。次に、この行列
2006060465.tif 000059
にＲ×（Ｒ−２ｒ）の行列Ｂ（ｉ，ｊ）を付加し、Ｒ×Ｒの正則行列
2006060465.tif 000060
を構成する。そして、Ａ（ｉ，ｊ）の逆行列
2006060465.tif 000061
を求めると、下記数２９の関係が成り立つ。
【０１０５】
【数２９】
2006060465.tif 000062
ここで、
2006060465.tif 000063
はｒ×Ｒの行列であり、
2006060465.tif 000064
となる。ただし、Ｉｒはｒ×ｒの単位行列である。また、
2006060465.tif 000065
はｒ×Ｒの行列であり、
2006060465.tif 000066
となる。また、
2006060465.tif 000067
は２ｒ×Ｒの行列であり、
2006060465.tif 000068
となる。ただし、Ｉ２ｒは２ｒ×２ｒの単位行列である。また、
2006060465.tif 000069
は２ｒ×Ｒの行列であり、
2006060465.tif 000070
となる。
【０１０６】
前記
2006060465.tif 000071
に対し、
2006060465.tif 000072
となるバイト位置ｉ，ｊが、誤りの位置ｉI、ｉIIとなり、
2006060465.tif 000073
が誤りの大きさｅI’、ｅII’となる。これから、２バイトの誤りを訂正することができる。また、
2006060465.tif 000074
となるバイト位置ｉ，ｊが、存在しない場合に、誤りの訂正が不可能として誤りを検出する。
【０１０７】
しかし、特許文献３に開示された並列復号法は、高速な復号が可能であるが、符号の距離ｄが大きくなると、回路量が大きくなるという問題が生じる。この場合、例えば、バーレカンプ・マッシィ法などの逐次復号法を用いることができるが、逐次復号法による復号はシリアルに行われるため、復号が遅いといった問題が生じる。なお、バーレカンプ・マッシィ法を用いたＲＳ符号の復号回路の構成は、非特許文献１１に開示されている。
【０１０８】
一方、本発明において、前述したｄ＝５の符号に対する並列復号方法を実現する復号回路４の概略構成を図６に示す。
【０１０９】
図１に示したように、復号回路４は、シンドローム生成回路１と誤り訂正回路５とから構成されている。
【０１１０】
また、図６に示すように、誤り訂正回路５は、ＧＦ（２ｒ）上の並列復号回路６と、ＧＦ（２ｂ）上の誤り生成回路７と、誤り検出回路８と、反転回路９とから構成されている。
【０１１１】
ここで、ＧＦ（２ｒ）上の並列復号回路６は、シンドローム（Ｓ）３３を基にして、ＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される訂正不可能誤り検出信号ＤＳ（Detection  Signal）３６を生成する。
【０１１２】
また、ＧＦ（２ｂ）上の誤り生成回路７は、ＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７に指摘されたＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）３８を出力する。
【０１１３】
そして、誤り検出回路８は、並列復号回路６で訂正できない誤りを検出し、つまり、ＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７及び訂正不可能誤り検出信号（ＤＳ）３６を基にして、誤り訂正の可否を判断する。
【０１１４】
最後に、反転回路９は、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）３８を基にして、誤りビットに該当する受信語（Ｖ’）３２のビット値を反転させることにより、受信語（Ｖ’）３２の誤りを訂正する。
【０１１５】
次に、図６に示される復号回路４で行われる動作手順の概略を説明する。
【０１１６】
まず、シンドローム生成回路１では、Ｎビットからなる受信語（Ｖ’）３２が入力されると、Ｒビットのシンドローム（Ｓ）３３を生成する。
【０１１７】
次に、生成されたＲビットのシンドローム（Ｓ）３３は、ＧＦ（２ｒ）上の並列復号回路６に入力される。
【０１１８】
そして、ＧＦ（２ｒ）上の並列復号回路６では、詳細は後述するが、シンドローム（Ｓ）３３を基にして、ＧＦ（２ｒ）上の誤りを指摘する
2006060465.tif 000075
ビットのＧＦ（２ｒ）上のビット誤りポインタ
2006060465.tif 000076
を生成する。ここで、
2006060465.tif 000077
はｙを越える最小の整数を示す。また、ＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに、訂正不可能誤り検出信号（ＤＳ）３６を出力する。
【０１１９】
また、ＧＦ（２ｂ）上の誤り生成回路７では、詳細は後述するが、ｅI→ｅI’、ｅII→ｅII’が単射の関係になっていることに基づき、ＧＦ（２ｒ）上の並列復号回路６で生成されたＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７からＮビットのビット誤りポインタｅ＝（ｅ０、ｅ１、…、ｅＮ−１）３８を出力する。
【０１２０】
次に、誤り検出回路８では、詳細は後述するが、ＧＦ（２ｒ）上の並列復号回路６で生成された訂正不可能誤り検出信号（ＤＳ）３６及びＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７を基にして、受信語の誤り訂正の可否を判断し、受信語のビット誤りを訂正できないことを検出した場合に、最終的に、訂正不可能誤り検出信号ＵＣＥ（Uncorrectable  Error）３５を出力する。例えば、訂正不可能誤り検出信号ＵＣＥ３５の値が“１”であれば、誤り検出回路８は、訂正能力を超えた誤りを検出したことを示している。
【０１２１】
そして、反転回路９では、ＧＦ（２ｂ）上の誤り生成回路７で生成されたＮビットのＧＦ（２ｂ）上のビット誤りポインタ（ｅ）３８及び受信語（Ｖ’）３２を基にして、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）に対応した受信語（Ｖ’）３２のビットを反転する。
【０１２２】
最後に、反転回路９は、Ｎビットの誤り訂正された受信語Ｖ＊からＫビットの情報語Ｄ*を取り出し、出力情報データ３４として出力する。
【０１２３】
なお、数４に示す伸長符号でも、その復号方法及び回路構成は、上述したことと基本的に同一である。
【０１２４】
次に、シンドローム生成回路１、ＧＦ（２ｒ）上の並列復号回路６、ＧＦ（２ｂ）上の誤り生成回路７、誤り検出回路８、及び反転回路９のそれぞれの具体的な構成例を、図３に示す（８８、６４）Ｄ２／８ＥＣ符号を用いて説明する。
＜ａ＞シンドローム生成回路１の構成
ここでは、シンドローム生成回路１の構成について詳細に説明する。
【０１２５】
まず、シンドローム生成回路では、Ｎ＝８８（＝６４＋２４）ビットからなる受信語（Ｖ’）３２を、下記数３０に示すように表現したとき、この受信語（Ｖ’）３２を入力して、下記数３１に示すＳ０、Ｓ１、…、Ｓ２３からなるＲ＝２４ビットのシンドローム（Ｓ）３３を生成する。前述したように、図３に示すＤ２／８ＥＣ符号のパリティ検査行列が４段構成を有することから、これに対応してシンドローム（Ｓ）３３も４個の部分に区分けし、ＳI＝（Ｓ０Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５）、ＳII＝（Ｓ６Ｓ７Ｓ８Ｓ９Ｓ１０Ｓ１１）、ＳIII＝（Ｓ１２Ｓ１３Ｓ１４Ｓ１５Ｓ１６Ｓ１７）、ＳIV＝（Ｓ１８Ｓ１９Ｓ２０Ｓ２１Ｓ２２Ｓ２３）とする。
【０１２６】
【数３０】
2006060465.tif 000078
【０１２７】
【数３１】
2006060465.tif 000079
上記数２６に示したように、シンドロームＳ＝Ｖ’・ＨＴより、転置したパリティ検査行列（ＨＴ）の各行は、入力する情報に対応し、例えば、行列（ＨＴ）の第０行は、入力情報のｖ０’に対応している。そこで、シンドローム（Ｓ）３３の各ビットを生成するには、符号であるパリティ検査行列（ＨＴ）の各列方向ごとに、“１”を有するビットに対応する受信語（Ｖ’）３２の受信情報をＧＦ（２）上で加算（ｍｏｄ２の計算）すればよい。
【０１２８】
図７及び図８は、図３に示したＤ２／８ＥＣ符号のパリティ検査行列を基に構成したシンドローム生成回路１を示す図である。図７では、Ｓ０、Ｓ１、…、Ｓ１１といったシンドローム（Ｓ）３３の上位１２ビットを、また、図８では、Ｓ１２、Ｓ１３、…、Ｓ２３といったシンドローム（Ｓ）３３の下位１２ビットをそれぞれ生成している。
【０１２９】
図７及び図８に示すように、本実施例では、シンドローム生成回路１において、まず、２４個の多入力パリティチェック回路２１（ｐ）、（ｐ＝０、１、…、２３）に、図３に示したＤ２／８ＥＣ符号のパリティ検査行列の対応する各行のビット“１”を有する受信情報（ｖｑ’）、（ｑ＝０、１、…、８７）が入力される。
【０１３０】
次に、各多入力パリティチェック回路２１（ｐ）、（ｐ＝０、１、…、２３）において、前記入力された受信情報（ｖｑ’）に対して、２を法とする和（ｍｏｄ２）の計算を行い、その結果がＳｐである。
【０１３１】
具体的に、例えば、シンドローム（Ｓ）３３のビットＳ０を生成するには、８８ビットの受信語ｖ０’、ｖ１’、…、ｖ８７’のうち、図３に示すパリティ検査行列の第０行目において、“１”が存在する箇所に相当するｖ０’、ｖ６’、ｖ８’、ｖ１４’、ｖ１６’、ｖ２２’、ｖ２４’、ｖ３０’、ｖ３２’、ｖ３８’、ｖ４０’、ｖ４６’、ｖ４８’、ｖ５４’、ｖ５６’、ｖ６２’、ｖ６４’、ｖ７０’、ｖ７２’、ｖ７８’、ｖ８０’、ｖ８６’の２２ビットに対して、２を法とする和（ｍｏｄ２）をとればよい。図７の多入力パリティチェック回路２１（０）では、前記２２ビットの受信情報を入力として、値Ｓ０を出力するようになっている。シンドローム（Ｓ）３３の他のビットＳｐ、（ｐ＝１、…、２３）についても同様である。
＜ｂ＞ＧＦ（２６）上の並列復号回路６の構成
次に、ＧＦ（２６）上の並列復号回路６について説明する。
【０１３２】
ＧＦ（２６）上のビット誤りポインタ３７を求めるために、並列復号法を用いる。ＧＦ（２６）上の並列復号回路６の全体構成を図９に示す。
【０１３３】
図９に示されるように、ＧＦ（２６）上の並列復号回路６は、１１バイト中任意の２バイトの組
2006060465.tif 000080
個を選び、ｉ、ｊ番目の２バイト（以下、（ｉ、ｊ）と表現することとする）に関する各々の誤りを生成する回路である誤り生成回路４０（０）…４０（５４）、（以下、代表として４０（ｍ）、０≦ｍ≦５４、と称する）と、ＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）３７を出力するＧＦ（２ｒ）上の誤り算出回路４１とから構成されている。
【０１３４】
まず、（ｉ、ｊ）に対する誤り生成回路４０（ｍ）は、バイト位置ｉ、ｊに対して、上述した
2006060465.tif 000081
を計算する回路である。要するに、（ｉ、ｊ）に対する誤り生成回路４０（０）〜４０（５４）は、符号語の１１バイト中のｉ、ｊ（０≦ｉ＜ｊ≦１０）番目のバイトに対する前述した
2006060465.tif 000082
を計算し、Ｅ’ｍ、ｉ、Ｅ’ｍ、ｊになる誤り４２（ｍ）、０≦ｍ≦５４、０≦ｉ＜ｊ≦１０（それぞれｒビットのベクトル）、及び訂正可能信号４３（ｍ）、０≦ｍ≦５４、を出力する。
【０１３５】
また、ＧＦ（２６）上の誤り算出回路４１は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７を出力する回路である。要するに、ＧＦ（２６）上の誤り算出回路４１は、誤り生成回路４０（ｍ）の出力である誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊを入力とし、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７を出力する。
【０１３６】
ここで、ＧＦ（２６）上の並列復号回路６の処理をより詳しくみると、図９に示すように、まず、Ｒ＝２４ビットのシンドローム（Ｓ）３３を（ｉ、ｊ）に対する誤り生成回路４０（ｍ）に入力する。次に、（ｉ、ｊ）に対する誤り生成回路４０（ｍ）は、誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊを生成し、そして、生成した誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊをＧＦ（２６）上の誤り算出回路４１に入力する。ＧＦ（２６）上の誤り算出回路４１は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７を出力する。
【０１３７】
また、Ｒ＝２４ビットのシンドローム（Ｓ）３３を２４ビット入力ＯＲゲート回路４４にも入力し、一方、（ｉ、ｊ）に対する誤り生成回路４０（ｍ）によって生成される訂正可能信号４３（ｍ）を５５入力ＮＯＲゲート回路４５に入力する。
【０１３８】
２４ビット入力ＯＲゲート回路４４及び５５入力ＮＯＲゲート回路４５からそれぞれ出力された２本の信号を２入力ＡＮＤゲート回路４６に入力する。２入力ＡＮＤゲート回路４６は、訂正不可能誤り検出信号（ＤＳ）３６を出力する。これらの回路により、シンドローム（Ｓ）３３が非零、かつ訂正可能信号がすべて０の場合に、誤りを検出する。
【０１３９】
次に、（ｉ、ｊ）に対する誤り生成回路４０（ｍ）の構成例を具体的に示す。例として、（０、１）に対する誤り生成回路４０（０）を図１０に示す。図１０に示されるように、（ｉ、ｊ）に対する誤り生成回路４０（ｍ）は、
2006060465.tif 000083
計算回路５０と、
2006060465.tif 000084
計算回路５１と、
2006060465.tif 000085
計算回路５２とを備える。
【０１４０】
ここで、
2006060465.tif 000086
は下記数３２に示すＧＦ（２６）上のＲＳ符号の検査行列であり、符号長６６ビットと検査ビット長２４ビットとを有する。ただし、γはＧＦ（２６）の元であり、下記数３３に示すように、生成多項式ｇ（ｘ）＝ｘ６＋ｘ＋１で定義される２元の６×６随伴行列（companion  matrix）で表現される。
【０１４１】
【数３２】
2006060465.tif 000087
【０１４２】
【数３３】
2006060465.tif 000088
例えば、（０、１）に対する誤り生成回路４０（０）では、
2006060465.tif 000089
は、数３２の第１列、第２列に相当し、それぞれ下記数３４に示す２４×６行列となる。
【０１４３】
【数３４】
2006060465.tif 000090
次に、
2006060465.tif 000091
から２４×１２の行列
2006060465.tif 000092
を構成し、
2006060465.tif 000093
に２４×１２の行列Ｂ（０，１）を付加することにより、下記数３５に示す２４×２４の正則行列
2006060465.tif 000094
を構成する。ここで、Ｂ（０，１）はＡ（０，１）が正則行列となるように求めた２４×１２の行列であり、一例である。
【０１４４】
【数３５】
2006060465.tif 000095
次に、Ａ（０，１）の逆行列
2006060465.tif 000096
を求めると、下記数３６の関係が成り立ち、
2006060465.tif 000097
は、それぞれ下記数３７、数３８、数３９に示す行列となる。
【０１４５】
【数３６】
2006060465.tif 000098
【０１４６】
【数３７】
2006060465.tif 000099
【０１４７】
【数３８】
2006060465.tif 000100
【０１４８】
【数３９】
2006060465.tif 000101
2006060465.tif 000102
計算回路５０では、
2006060465.tif 000103
の各列が入力する情報に対応し、例えば、
2006060465.tif 000104
の第０行が入力情報のＳ０に対応している。そこで、
2006060465.tif 000105
の各ビットを生成するには、
2006060465.tif 000106
の各行方向に、“１”を有するビットに対応するシンドローム（Ｓ）３３の情報をＧＦ（２）上で加算（ｍｏｄ２の計算）すればよい。
【０１４９】
要するに、
2006060465.tif 000107
計算回路５０は、まず、前記
2006060465.tif 000108
の対応する各行のビット“１”を有するシンドローム情報（Ｓｐ）、（ｐ＝０、１、…、２３）をそれぞれ６個の多入力パリティチェック回路５３（ｕ）、（ｕ＝０、１、…、５）に入力する。次に、これらのシンドローム情報に対してｍｏｄ２の計算を行い、その結果としてＥ’０、０、Ｅ’０、１を出力する。
【０１５０】
具体的に、例えば、Ｅ’０、０の０ビット目を生成するには、２４ビットのシンドロームＳ０、Ｓ１、…、Ｓ２３のうち、上記数３７に示すパリティ検査行列の第０行目において、“１”が存在する箇所に相当する５ビットｓ０、ｓ５、ｓ９、ｓ２１、ｓ２３の値について、２を法とする和（ｍｏｄ２）をとればよい。
【０１５１】
図１０の多入力パリティチェック回路５３（０）には、この５ビットｓ０、ｓ５、ｓ９、ｓ２１、ｓ２３のシンドロームが入力される。また、多入力パリティチェック回路５３（０）は、４２（０）であるＥ’０、０の０ビット目を出力する。なお、Ｅ’０、０の他のビットについても同様である。
【０１５２】
また、図１０に示されるように、
2006060465.tif 000109
計算回路５１は、６個の多入力パリティチェック回路５４（ｗ）、（ｗ＝０、１、…、５）で構成され、
2006060465.tif 000110
計算回路５２は、１２個の多入力パリティチェック回路５５（ｚ）、（ｚ＝０、１、…、１１）で構成されている。これらの計算回路は、
2006060465.tif 000111
計算回路５０と同様の方法で構成することができる。
【０１５３】
ここで、（０、１）に対する誤り生成回路４０（０）の処理をより詳しくみると、図１０に示すように、Ｒ＝２４ビットのシンドローム（Ｓ）３３を多入力パリティチェック回路５３（ｕ）、（ｕ＝０、１、…、５）に入力することにより、Ｅ’０、０を生成する。また、Ｒ＝２４ビットのシンドローム（Ｓ）３３を多入力パリティチェック回路５４（ｗ）、（ｗ＝０、１、…、５）に入力することにより、Ｅ’０、１を生成する。
【０１５４】
また、Ｒ＝２４ビットのシンドローム（Ｓ）３３を多入力パリティチェック回路５５（ｚ）、（ｚ＝０、１、…、１１）に入力する。多入力パリティチェック回路５５（ｚ）、（ｚ＝０、１、…、１１）から出力される１２ビットの信号を１２入力ＮＯＲゲート回路５６に入力し、（０、１）に対する訂正可能信号４３（０）を出力する。これらの回路は、
2006060465.tif 000112
となるバイトの組（ｉ、ｊ）が誤りのバイトの組であるため、
2006060465.tif 000113
であることを検出し、バイトの組（ｉ、ｊ）で訂正可能であることを意味する。
【０１５５】
また、（０、１）に対する訂正可能信号４３（０）と多入力パリティチェック回路５３、多入力パリティチェック回路５４からの出力信号を２入力ＡＮＤゲート回路５７に入力し、Ｅ’０、０、及びＥ’０、１を出力する。これらの回路は、誤りが生じているバイトの組である場合に、誤りを出力し、そうでない場合に、０のパターンを出力するようにしている。
【０１５６】
以上より、（０、１）に対する誤り生成回路４０（０）は、誤りＥ’０、０、Ｅ’０、１４２（０）、及び（０、１）に対する訂正可能信号４３（０）を最終的に出力する。ここでは、（０、１）に対する誤り生成回路４０（０）を例として説明したが、他のバイト（ｉ、ｊ）に対しても同様である。
【０１５７】
次に、ＧＦ（２６）上の誤り算出回路４１の構成例を具体的に示す。ＧＦ（２６）上の誤り算出回路４１を図１１に示す。
【０１５８】
図１１に示されるように、ＧＦ（２６）上の誤り算出回路４１は、ｉ番目のバイトに対応するすべての誤りＥ’ｍ、ｉをビットごとＯＲ演算回路６０に入力し、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７を最終的に出力する。これらの回路は、ｉ番目に対応するバイトの組（ｉ、ｊ）からの誤りＥ’ｍ、ｉを統合し、ｉ番目の誤りｅｉ’を出力するようにしている。
【０１５９】
具体的に、例えば、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７のｅ６’を出力するには、（０、１）に対する誤り生成回路４０（０）、及び（１、２）に対する誤り生成回路４０（１０）、…、及び（１、１０）に対する誤り生成回路４０（１８）から出力されるＥ’０、１、Ｅ’１０、１、…、Ｅ’１８、１の０ビット目をビットごとＯＲ演算回路６０に入力することにより得られる。ビットごとＯＲ演算回路６０では、６ビットを有するＥ’０、１、Ｅ’１０、１、…、Ｅ’１８、１の０ビット目をそれぞれ１０入力ＯＲ回路６１に入力することにより、Ｅ’０、１、Ｅ’１０、１、…、Ｅ’１８、１の０ビット目を統合し、ｅ６’を出力している。
【０１６０】
以上では、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７のｅ６’を例として説明したが、他のビット値ｅ０’、…、ｅ６５’についてもまったく同様である。
＜ｃ＞ＧＦ（２８）上の誤り生成回路７の構成
次に、ＧＦ（２８）上の誤り生成回路７について述べる。ＧＦ（２８）上の誤り生成回路７は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７を入力とし、ＧＦ（２８）上のビット誤りポインタ（ｅ）３８を出力する回路である。
【０１６１】
例として、２バイト目に対するＧＦ（２８）上の誤り生成回路７（上位４ビット）を図１２に、また、２バイト目に対するＧＦ（２８）上の誤り生成回路７（下位４ビット）を図１３にそれぞれ示す。
【０１６２】
ＧＦ（２８）上の誤りｅI、ＧＦ（２６）上の誤りｅI’において、ｅI→ｅI’は、単射の関係となっている。よって、論理合成を行うことにより、組み合わせ回路で実現することができる。
【０１６３】
具体的に、例えば、図１２において、情報２バイト目では、ｅI・Ｈ’Ｔ＝ｅI’であり、Ｈ’は、数２２に示すランク４を有する２ビット誤り訂正符号の検査行列であるため、重みが２以下のＧＦ（２８）上の誤りｅI、及びＧＦ（２６）上の誤りｅI’は一意に定まる。よって、重みが２以下のＧＦ（２８）上の誤りｅI＝（ｅ８ｅ９ｅ１０ｅ１１ｅ１２ｅ１３ｅ１４ｅ１５）、及びＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）は、下記表１に示す関係を有する。
【０１６４】
【表１】
2006060465.tif 000114
ここで、ＧＦ（２６）上の誤りｅI’は３７パターンあるが、残りの２６−３７＝２７パターンに対するｅIは、ドントケア＊とする。
【０１６５】
例えば、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係から、情報２バイト目の１ビット目の値ｅ８は、ｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）＝（１０００００）、（１１００００）、（１０１０００）、（１００１００）、（０１１１００）、（１０００１０）、（１０１１１１）、（１００００１）のときに、１となる。
【０１６６】
また、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係において、残った２７パターンのＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）＝（１００１１０）、（１１０１１０）、（０１０１１０）、（０１１１１０）、（１０１１１０）、（１１００１０）、（０１１０１０）、（１１１０１０）、（１０１０１０）、（１０００１１）、（０１００１１）、（０１１０１１）、（１１１０１１）、（１０１０１１）、（１００１１１）、（１１０１１１）、（０１０１１１）、（１１１１１１）、（１００１０１）、（１１０１０１）、（０１０１０１）、（０１１１０１）、（１０１１０１）、（１１０００１）、（０１１００１）、（１１１００１）、（１０１００１）に対する情報２バイト目の１ビット目の値ｅ８は、ドントケア＊とする。
【０１６７】
これらの論理関数を簡単化すると、情報２バイト目の１ビット目の値ｅ８は、下記数４０に示す論理式で表される。
【０１６８】
【数４０】
2006060465.tif 000115
ただし、
2006060465.tif 000116
は
2006060465.tif 000117
の否定で、
2006060465.tif 000118
は
2006060465.tif 000119
であり、また、
2006060465.tif 000120
は論理和を、
2006060465.tif 000121
は論理積を表す。
【０１６９】
よって、図１２に示されるように、まず、ＧＦ（２６）上のビット誤りポインタ３７ｅ６’、ｅ７’、ｅ８’、ｅ９’、ｅ１０’、ｅ１１’をＮＯＴゲート回路７０に入力し、
2006060465.tif 000122
を生成する。そして、
2006060465.tif 000123
を３入力ＡＮＤゲート回路７１に、
2006060465.tif 000124
を４入力ＡＮＤゲート回路７２に、
2006060465.tif 000125
を５入力ＡＮＤゲート回路７３に、
2006060465.tif 000126
を４入力ＡＮＤゲート回路７２に、
2006060465.tif 000127
を４入力ＡＮＤゲート回路７２にそれぞれ入力する。それぞれのＡＮＤゲート回路から出力された信号を５入力ＯＲゲート回路７４に入力することにより、情報２バイト目の１ビット目の値ｅ８が得られる。
【０１７０】
図１２及び図１３に示されるように、他のビットの値ｅ９、…、ｅ１５も、ＮＯＴゲート回路７０、３入力ＡＮＤゲート回路７１、４入力ＡＮＤゲート回路７２、５入力ＡＮＤゲート回路７３、５入力ＯＲゲート回路７４、６入力ＯＲゲート回路７５により、同様にして得られる。
【０１７１】
なお、以上では、２バイト目におけるＧＦ（２８）上の誤り生成回路７を例として詳細に説明したが、他のバイトについてもまったく同様である。
＜ｄ＞誤り検出回路８の構成
次に、誤り検出回路８について説明する。
【０１７２】
誤り検出回路８は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）３７及び訂正不可能誤り検出信号（ＤＳ）３６を入力とし、訂正不可能誤り検出信号（ＵＣＥ）３５を出力する回路である。つまり、誤り検出回路８では、ＧＦ（２６）上の誤りｅI’から写像されることのないＧＦ（２８）上の誤りｅIを訂正不可能な誤りとして検出するようにしている。
【０１７３】
例えば、２バイト目に対する誤り検出回路８を図１４に示す。
【０１７４】
具体的に、例えば、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係において、残った２７パターンのＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）＝（１００１１０）、（１１０１１０）、（０１０１１０）、（０１１１１０）、（１０１１１０）、（１１００１０）、（０１１０１０）、（１１１０１０）、（１０１０１０）、（１０００１１）、（０１００１１）、（０１１０１１）、（１１１０１１）、（１０１０１１）、（１００１１１）、（１１０１１１）、（０１０１１１）、（１１１１１１）、（１００１０１）、（１１０１０１）、（０１０１０１）、（０１１１０１）、（１０１１０１）、（１１０００１）、（０１１００１）、（１１１００１）、（１０１００１）に対する訂正不可能誤り検出信号（ＵＣＥ）３５の値を１にし、誤りを検出する。また、訂正不可能誤り検出信号（ＤＳ）３６の値が１のときに、誤りを検出する。
【０１７５】
よって、これらの論理関数を簡単化すると、訂正不可能誤り検出信号（ＵＣＥ）３５の値は、下記数４１に示す論理式で表される。
【０１７６】
【数４１】
2006060465.tif 000128
従って、図１４に示されるように、まず、ＧＦ（２６）上のビット誤りポインタ３７ｅ６’、ｅ７’、ｅ８’、ｅ９’、ｅ１０’、ｅ１１’をＮＯＴゲート回路７０に入力し、
2006060465.tif 000129
を生成する。そして、
2006060465.tif 000130
2006060465.tif 000131
2006060465.tif 000132
を合計１４個の４入力ＡＮＤゲート回路７２及び５入力ＡＮＤゲート回路７３にそれぞれ入力する。
【０１７７】
次に、これら合計１４個のＡＮＤゲート回路からそれぞれ出力された信号と、訂正不可能誤り検出信号（ＤＳ）３６とを１５入力ＯＲ回路７６に入力することにより、訂正不可能誤り検出信号（ＵＣＥ）３５を出力する。
【０１７８】
以上では、図１４に示された２バイト目における誤り検出回路８を誤り検出回路８の一例として説明したが、他のバイトについてもまったく同様である。
＜ｅ＞反転回路９の構成
最後に、反転回路９の構成について説明する。
【０１７９】
例えば、２バイト目に対して、具体的に構成した反転回路９を図１５に示す。図１５に示す反転回路９は、誤りの箇所を具体的に指摘されたビット位置に対して、受信したビット値の反転を行って受信語（Ｖ’）３２を訂正する回路である。図１５において、ｖ８’〜ｖ１５’は、受信語（Ｖ’）３２の２バイト目に相当する８ビットであり、また、ｖ８*〜ｖ１５*は訂正後の出力ビットである。
【０１８０】
反転回路９は、複数の排他的論理和回路を有している。図１５に示された２バイト目における反転回路９において、合計８個の排他的論理和回路８０は、８入力ビットｖ８’〜ｖ１５’に対して、対応するビット誤りポインタｅｉ（ｉ＝８、９、…、１５）との排他的論理和をそれぞれとり、例えば、ビット誤りポインタが“１”のときに、入力ビット値が反転されて訂正されるようにする。
【０１８１】
なお、反転回路９は、各バイトにそれぞれ対応するようにするため、例えば、Ｎ＝８８ビットの受信語（Ｖ’）に対しては、８８個の排他的論理和回路８０が必要となる。反転回路９は、最後に、Ｎ＝８８ビットの受信語（Ｖ’）から、下記数４２に示す訂正語Ｄ*６４ビットを得る。
【０１８２】
【数４２】
2006060465.tif 000133
前述したように、本発明では、バイト中にｔビットまでの誤りを有するスポッティバイト誤りに対し、距離ｄを有するスポッティバイト誤り訂正符号の一般性のある符号構成を与えるとともに、誤りの訂正・検出が実現できる回路である符号化・復号回路構成を示して、検査情報が具体的に生成できること、及び誤りが具体的に訂正・検出できることを示した。
【０１８３】
また、以上の説明では、主としてメモリ装置に注目して本発明の適用を述べたが、本発明は、それに限定されるものではなく、例えば、このようなバイト単位で物理的に独立した回路とモジュールと装置とから構成され、この中で限定した数の誤りが生じる可能性の高い一般の情報システム等に適用可能である。また、光通信回路やバス線回路等の通信または伝送のための回路、装置またはシステムにも適用可能である。
【０１８４】
また、本発明の目的は、本実施の形態のスポッティバイト誤り訂正・検出装置の機能を実現するソフトウェアのプログラムコードを記述した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出して実行することによっても、達成されることは言うまでもない。
【０１８５】
この場合、記憶媒体から読み出されたプログラムコード自体が本実施の形態の機能を実現することとなり、そのプログラムコードを記憶した記憶媒体及び当該プログラムコードは本発明を構成することとなる。プログラムコードを供給するための記憶媒体としては、ＲＯＭ、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード等を用いることができる。
【０１８６】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した本実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ等が実際の処理の一部又は全部を行い、その処理によって本実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１８７】
【図１】本発明の一実施形態であるスポッティバイト誤り訂正・検出装置の概略構成を示すブロック図である。
【図２】図１に示された本発明のスポッティバイト誤り訂正・検出装置における全体動作の処理手順を示すフローチャートである。
【図３】パリティ検査行列の一例であって、符号長Ｎ＝８８ビット、情報長Ｋ＝６４ビット、検査長Ｒ＝２４ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長２ビットの符号パラメータを有する短縮（８８、６４）Ｄ２／８ＥＣ符号のパリティ検査行列を示す図である。
【図４】図３に示すパリティ検査行列を基本行変形して得られる符号化用（８８、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列を示す図である。
【図５】図４に示す符号化用（８８、６４）Ｄ２／８ＥＣ組織符号をもとに構成した符号化回路の具体例であり、Ｋ＝６４ビットのデータ入力情報からパリティ検査行列により２４ビットの検査情報を生成する回路の構成図である。
【図６】本発明で開示された機能を有する符号に対する復号回路の概略構成を示すブロック図である。
【図７】図３に示す（８８、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したシンドローム生成回路（上位１２ビット）を説明するための概念図である。
【図８】図３に示す（８８、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したシンドローム生成回路（下位１２ビット）を説明するための概念図である。
【図９】図３に示す（８８、６４）Ｄ２／８ＥＣ符号に対するＧＦ（２ｒ）上の並列復号回路の概略構成を示すブロック図である。
【図１０】図９に示すＧＦ（２ｒ）上の並列復号回路における（ｉ、ｊ）に対する誤り生成回路の一例の回路構成図である。
【図１１】図９に示すＧＦ（２ｒ）上の並列復号回路におけるＧＦ（２ｒ）上の誤り算出回路の構成図である。
【図１２】図３に示す（８８、６４）Ｄ２／８ＥＣ符号に対するＧＦ（２ｂ）上の誤り生成回路の一例であり、１バイトに対してＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換する回路（上位４ビット）の構成図である。
【図１３】図３に示す（８８、６４）Ｄ２／８ＥＣ符号に対するＧＦ（２ｂ）上の誤り生成回路の一例であり、１バイトに対してＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換する回路（下位４ビット）の構成図である。
【図１４】図３に示す（８８、６４）Ｄ２／８ＥＣ符号に対する誤り検出回路の一例であり、１バイトに対して誤りを検出する回路の構成図である。
【図１５】図３に示す（８８、６４）Ｄ２／８ＥＣ符号に対する反転回路の一例であり、１バイトに対する反転回路の構成図である。
【符号の説明】
【０１８８】
１  シンドローム生成回路
２  符号化回路
３  回路（メモリ等の通信路）
４  復号回路
５  誤り訂正回路
６  ＧＦ（２ｒ）上の並列復号回路
７  ＧＦ（２ｂ）上の誤り生成回路
８  誤り検出回路
９  反転回路
２０  多入力パリティチェック回路
２１  多入力パリティチェック回路
３０  入力情報データ
３１  送信語
３２  受信語
３３  シンドローム
３４  出力情報データ
３５  訂正不可能誤り検出信号（ＵＣＥ）
３６  訂正不可能誤り検出信号（ＤＳ）
３７  ＧＦ（２ｒ）上のビット誤りポインタ
３８  ＧＦ（２ｂ）上のビット誤りポインタ
４０  （ｉ、ｊ）に対する誤り生成回路
４１  ＧＦ（２ｒ）上の誤り算出回路
４２  （ｉ、ｊ）に対する誤り
４３  （ｉ、ｊ）に対する訂正可能信号
４４  ２４入力ＯＲゲート回路
４５  ５５入力ＮＯＲゲート回路
４６  ２入力ＡＮＤゲート回路
５０  
2006060465.tif 000134
計算回路
５１  
2006060465.tif 000135
計算回路
５２  
2006060465.tif 000136
計算回路
５３  多入力パリティチェック回路
５４  多入力パリティチェック回路
５５  多入力パリティチェック回路
５６  １２入力ＮＯＲゲート回路
５７  ２入力ＡＮＤゲート回路
６０  ビットごとＯＲ演算回路
６１  １０入力ＡＮＤゲート回路
７０  ＮＯＴゲート回路
７１  ３入力ＡＮＤゲート回路
７２  ４入力ＡＮＤゲート回路
７３  ５入力ＡＮＤゲート回路
７４  ５入力ＯＲゲート回路
７５  ６入力ＯＲゲート回路
７６  １５入力ＯＲゲート回路
８０  排他的論理和回路
１００  スポッティバイト誤り訂正・校正検出装置
【図１】
2006060465.tif 000145
【図２】
2006060465.tif 000146
【図３】
2006060465.tif 000147
【図４】
2006060465.tif 000148
【図５】
2006060465.tif 000149
【図６】
2006060465.tif 000150
【図７】
2006060465.tif 000151
【図８】
2006060465.tif 000152
【図９】
2006060465.tif 000153
【図１０】
2006060465.tif 000154
【図１１】
2006060465.tif 000155
【図１２】
2006060465.tif 000156
【図１３】
2006060465.tif 000157
【図１４】
2006060465.tif 000158
【図１５】
2006060465.tif 000159