(57)【要約】【課題】  多重のバイト内複数スポッティバイト誤りを制御することができる機能を備えたバイト内複数スポッティバイト誤り訂正・検出装置を提供する。【解決手段】  入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるバイト内複数スポッティバイト誤り訂正・検出装置であって、前記符号化手段は、スポッティバイト誤り制御符号を表現するパリティ検査行列と、前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備える。【選択図】  図１
2006101429.tif 000002
【特許請求の範囲】
【請求項１】
入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるバイト内複数スポッティバイト誤り訂正・検出装置であって、
前記符号化手段は、スポッティバイト誤り制御符号を表現するパリティ検査行列と、前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、
前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることを特徴とするバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２】
前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、１バイト内に複数の前記スポッティバイト誤りが生じる誤りをバイト内複数スポッティバイト誤りと称することを前提とし、
前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、距離ｄに対し、
2006101429.tif 000218
を有する請求項１に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項３】
前記ｔ値、ｂ値、ｄ値を任意に設定する請求項２に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項４】
前記情報伝送路は、情報通信システムである請求項１乃至請求項３のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項５】
前記情報伝送路は、メモリシステムである請求項１乃至請求項３のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項６】
前記情報伝送路は、バス線回路である請求項１乃至請求項３のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項７】
前記パリティ検査行列は、前記距離ｄを有するバイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000219
ただし、Ｒ＝ｑ＋（ｄ−２）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000220
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000221
を満足し、ここで、
2006101429.tif 000222
はｘを超えない最小の整数を表し、また、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000223
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000224
を有する符号の検査行列、すなわち、
2006101429.tif 000225
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ”＝［γｉｈ０”、γｉｈ１”、…、γｉｈｂ−１”］が成立するように構成される請求項２乃至請求項６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項８】
前記パリティ検査行列は、前記距離ｄを有する伸長バイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000226
ただし、Ｒ≧ｑ＋（ｄ−２）ｒ、かつ（Ｒ−ｑ）は（ｄ−２）の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／（ｄ−２）、０≦ｉ≦ｎ−１、（Ｒ−ｑ）は（ｄ−２）の倍数とし、ｎ＝２（Ｒ−ｑ）／（ｄ−２）−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000227
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000228
を満足し、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000229
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000230
を有する符号の検査行列、すなわち、
2006101429.tif 000231
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、Ｒ≧ｑ＋（ｄ−２）ｒ、かつＲ−ｑはｄ−２の倍数とし、γは２を底とする（Ｒ−ｑ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｑ）／（ｄ−２））の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”
）、γｉΦ（ｈ１” ）、・・・、γｉΦ（ｈｂ−１”
）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｑ）→ＧＦ（２（Ｒ−ｑ）／（ｄ−２））である請求項２乃至請求項６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項９】
前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビットまでの誤りをｔ／ｂ誤りと称し、バイト内のｔ’ビットまでの誤りをｔ’／ｂ誤りと称することを前提とし、ただし、１≦ｔ、ｔ’≦ｂ、且つ、ｔ≠ｔ’であり、
前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、１バイト内に生じた大きさの異なる２種類のスポッティバイト誤り（つまり、前記ｔ／ｂ誤り及び前記ｔ’／ｂ誤り）を制御する機能を備えた請求項１に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１０】
前記情報伝送路は、情報通信システムである請求項９に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１１】
前記情報伝送路は、メモリシステムである請求項９に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１２】
前記情報伝送路は、バス線回路である請求項９に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１３】
前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、（ｔ／ｂ＋ｔ’／ｂ）誤り（つまり、ｔ／ｂ誤りとｔ’／ｂ誤りの複合誤り）を検出する機能を有するＳｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号であり、
前記Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000232
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項９乃至請求項１２のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１４】
前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、２個のｔ’／ｂ誤りを検出する機能を有するＳｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号であり、
前記Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000233
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔまたはｔ＋２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ＋２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項９乃至請求項１２のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１５】
前記スポッティバイト誤り制御符号は、（ｔ／ｂ＋ｔ’／ｂ）誤りを訂正する機能を有する（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号であり、
前記（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000234
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋２ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋２ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（ｔ＋ｔ’、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項９乃至請求項１２のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１６】
前記スポッティバイト誤り制御符号は、２個のｔ／ｂ誤りを訂正し、且つ、１個のｔ’／ｂ誤り（ｔ＜ｔ’）を訂正する機能を有するＤｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号であり、
前記Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000235
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、４ｔまたは２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（４ｔ、２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ’）、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項９乃至請求項１２のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１７】
前記誤り訂正手段は、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力する請求項１乃至請求項１６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１８】
前記誤り訂正手段は、Ｈ’復号手段と、Ｈ”乗算手段と、ＧＦ（２ｒ）上の並列復号手段と、ＧＦ（２ｂ）上の誤り生成手段と、反転手段とから構成される請求項７、請求項８、請求項１３、請求項１４、請求項１５又は請求項１６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項１９】
前記Ｈ’復号手段は、前記シンドローム生成手段で生成された前記シンドロームの上位ｑビットを基にして、バイトごとの誤りの和（ｅＡ）を生成し、
前記Ｈ”乗算手段は、前記Ｈ’復号手段で生成された前記バイトごとの誤りの和（ｅＡ）を基にして、前記シンドロームの上位ｑビットとＨ”の転置行列の積を生成し、
前記ＧＦ（２ｒ）上の並列復号手段は、前記Ｈ”乗算手段で生成された前記シンドロームの上位ｑビットとＨ”の転置行列の積、及び前記シンドローム生成手段で生成された前記シンドロームの上位ｑビットを除く残りの下位ビットを基にして、ＧＦ（２ｒ）上のビット誤りポインタ、及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号を生成し、
前記ＧＦ（２ｂ）上の誤り生成手段は、前記Ｈ’復号手段で生成された前記バイトごとの誤りの和（ｅＡ）、及び、前記ＧＦ（２ｒ）上の並列復号手段で生成された前記ＧＦ（２ｒ）上のビット誤りポインタを基にして、ＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ、及び誤り訂正が不可能とみなされたときに出力される第２の訂正不可能誤り検出信号を生成し、
前記反転手段は、前記ＧＦ（２ｂ）上の誤り生成手段で生成された前記ＧＦ（２ｂ）上のビット誤りポインタを基にして、前記ＧＦ（２ｂ）上のビット誤りポインタに対応した前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正する請求項１８に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２０】
前記誤り訂正手段では、前記ＧＦ（２ｒ）上の並列復号手段で生成された前記第１の訂正不可能誤り検出信号と、前記ＧＦ（２ｂ）上の誤り生成手段で生成された前記第２の訂正不可能誤り検出信号の論理和をとることにより、訂正能力を超えた誤りを検出したことを示す第３の訂正不可能誤り検出信号を出力する請求項１９に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２１】
前記ＧＦ（２ｂ）上の誤り生成手段は、
シンドロームが非零であることを検出する誤りバイト検出手段と、
前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトから前記ＧＦ（２ｂ）上のビット誤りポインタの１バイトを出力するｔビット誤り訂正復号手段と、
入力信号の選択を制御信号に従って行うビットごと選択手段と、
入力された信号のハミング重み１を検出するためのハミング重み検出手段とを備えた請求項１９又は請求項２０に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２２】
前記ＧＦ（２ｂ）上の誤り生成手段は、誤りバイト検出手段と、ｔビット誤り訂正復号手段と、ビットごと選択手段と、ハミング重み検出手段とを備えており、
前記誤りバイト検出手段は、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトを入力とし、１ビットのシンドローム検出信号を出力し、
前記ｔビット誤り訂正復号手段は、前記ＧＦ（２ｒ）上のビット誤りポインタの所定の１バイトを入力とし、前記ＧＦ（２ｂ）上のビット誤りポインタの前記所定の１バイトに対応する１バイトを出力すると共に、訂正能力をこえた誤りを検出する検出信号をも出力し、
前記ビットごと選択手段は、２つの入力信号の各ビットどうしを制御信号に従って選択し、
前記ハミング重み検出手段は、前記誤りバイト検出手段から出力された前記シンドローム検出信号を入力とし、入力された前記シンドローム検出信号のハミング重みを計算し、前記ハミング重みが１の場合に１を出力し、そうでない場合に０を出力するように構成される請求項１９又は請求項２０に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２３】
前記ｔビット誤り訂正復号手段では、訂正能力をこえた前記誤りが、前記ＧＦ（２ｒ）上の誤りｅ’Iから写像されることのない前記ＧＦ（２ｂ）上の誤りｅIである請求項２２に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２４】
前記ＧＦ（２ｂ）上の誤り生成手段では、前記ｔビット誤り訂正復号手段から出力された前記検出信号を多入力ＯＲゲート回路に入力し、前記多入力ＯＲゲート回路は、入力された前記検出信号に基づいて、前記第２の訂正不可能誤り検出信号を出力し、
また、前記ＧＦ（２ｂ）上の誤り生成手段では、前記ハミング重み検出手段から出力された信号と、前記誤りバイト検出手段から出力された前記シンドローム検出信号とをそれぞれ２入力ＡＮＤゲート回路に入力し、前記２入力ＡＮＤゲート回路から出力された信号を前記ビットごと選択手段の前記制御信号とし、
前記ビットごと選択手段では、前記ｔビット誤り訂正復号手段から出力された信号、及び、前記バイトごとの誤りの和（ｅＡ）の選択を前記制御信号に従って行い、選択された信号を集め、前記ＧＦ（２ｂ）上のビット誤りポインタを出力する請求項２３に記載のバイト内複数スポッティバイト誤り訂正・検出装置。
【請求項２５】
入力情報データを基に送信語を生成する符号化処理ステップと、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理ステップとを有するバイト内複数スポッティバイト誤り訂正・検出方法であって、
前記符号化処理ステップは、スポッティバイト誤り制御符号を表現するパリティ検査行列と、前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、
前記復号処理ステップは、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理ステップと、前記シンドローム生成処理ステップにより生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正処理ステップとを有することを特徴とするバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項２６】
前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、１バイト内に複数の前記スポッティバイト誤りが生じる誤りをバイト内複数スポッティバイト誤りと称することを前提とし、
前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、距離ｄに対し、
2006101429.tif 000236
を有する請求項２５に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項２７】
前記ｔ値、ｂ値、ｄ値を任意に設定する請求項２６に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項２８】
前記情報伝送路は、情報通信システムである請求項２５乃至請求項２７のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項２９】
前記情報伝送路は、メモリシステムである請求項２５乃至請求項２７のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３０】
前記情報伝送路は、バス線回路である請求項２５乃至請求項２７のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３１】
前記パリティ検査行列は、前記距離ｄを有するバイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000237
ただし、Ｒ＝ｑ＋（ｄ−２）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000238
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000239
を満足し、ここで、
2006101429.tif 000240
はｘを超えない最小の整数を表し、また、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000241
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000242
を有する符号の検査行列、すなわち、
2006101429.tif 000243
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ”＝［γｉｈ０”、γｉｈ１”、…、γｉｈｂ−１”］が成立するように構成される請求項２６乃至請求項３０のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３２】
前記パリティ検査行列は、前記距離ｄを有する伸長バイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000244
ただし、Ｒ≧ｑ＋（ｄ−２）ｒ、かつ（Ｒ−ｑ）は（ｄ−２）の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／（ｄ−２）、０≦ｉ≦ｎ−１、（Ｒ−ｑ）は（ｄ−２）の倍数とし、ｎ＝２（Ｒ−ｑ）／（ｄ−２）−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000245
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000246
を満足し、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000247
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000248
を有する符号の検査行列、すなわち、
2006101429.tif 000249
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、Ｒ≧ｑ＋（ｄ−２）ｒ、かつＲ−ｑはｄ−２の倍数とし、γは２を底とする（Ｒ−ｑ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｑ）／（ｄ−２））の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”
）、γｉΦ（ｈ１” ）、・・・、γｉΦ（ｈｂ−１”
）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｑ）→ＧＦ（２（Ｒ−ｑ）／（ｄ−２））である請求項２６乃至請求項３０のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３３】
前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビットまでの誤りをｔ／ｂ誤りと称し、バイト内のｔ’ビットまでの誤りをｔ’／ｂ誤りと称することを前提とし、ただし、１≦ｔ、ｔ’≦ｂ、且つ、ｔ≠ｔ’であり、
前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、１バイト内に生じた大きさの異なる２種類のスポッティバイト誤り（つまり、前記ｔ／ｂ誤り及び前記ｔ’／ｂ誤り）を制御する機能を備えた請求項２５に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３４】
前記情報伝送路は、情報通信システムである請求項３３に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３５】
前記情報伝送路は、メモリシステムである請求項３３に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３６】
前記情報伝送路は、バス線回路である請求項３３に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３７】
前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、（ｔ／ｂ＋ｔ’／ｂ）誤り（つまり、ｔ／ｂ誤りとｔ’／ｂ誤りの複合誤り）を検出する機能を有するＳｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号であり、
前記Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000250
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項３３乃至請求項３６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３８】
前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、２個のｔ’／ｂ誤りを検出する機能を有するＳｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号であり、
前記Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000251
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔまたはｔ＋２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ＋２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項３３乃至請求項３６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項３９】
前記スポッティバイト誤り制御符号は、（ｔ／ｂ＋ｔ’／ｂ）誤りを訂正する機能を有する（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号であり、
前記（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000252
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋２ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋２ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（ｔ＋ｔ’、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項３３乃至請求項３６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４０】
前記スポッティバイト誤り制御符号は、２個のｔ／ｂ誤りを訂正し、且つ、１個のｔ’／ｂ誤り（ｔ＜ｔ’）を訂正する機能を有するＤｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号であり、
前記Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000253
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、４ｔまたは２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（４ｔ、２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ’）、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である請求項３３乃至請求項３６のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４１】
前記誤り訂正処理ステップは、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力する請求項２５乃至請求項４０のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４２】
前記誤り訂正処理ステップは、Ｈ’復号処理ステップと、Ｈ”乗算処理ステップと、ＧＦ（２ｒ）上の並列復号処理ステップと、ＧＦ（２ｂ）上の誤り生成処理ステップと、反転処理ステップとを有する請求項３１、請求項３２、請求項３７、請求項３８、請求項３９又は請求項４０のいずれかに記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４３】
前記Ｈ’復号処理ステップは、前記シンドローム生成処理ステップで生成された前記シンドロームの上位ｑビットを基にして、バイトごとの誤りの和（ｅＡ）を生成し、
前記Ｈ”乗算処理ステップは、前記Ｈ’復号処理ステップで生成された前記バイトごとの誤りの和（ｅＡ）を基にして、前記シンドロームの上位ｑビットとＨ”の転置行列の積を生成し、
前記ＧＦ（２ｒ）上の並列復号処理ステップは、前記Ｈ”乗算処理ステップで生成された前記シンドロームの上位ｑビットとＨ”の転置行列の積、及び前記シンドローム生成処理ステップで生成された前記シンドロームの上位ｑビットを除く残りの下位ビットを基にして、ＧＦ（２ｒ）上のビット誤りポインタ、及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号を生成し、
前記ＧＦ（２ｂ）上の誤り生成処理ステップは、前記Ｈ’復号処理ステップで生成された前記バイトごとの誤りの和（ｅＡ）、及び、前記ＧＦ（２ｒ）上の並列復号処理ステップで生成された前記ＧＦ（２ｒ）上のビット誤りポインタを基にして、ＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ、及び誤り訂正が不可能とみなされたときに出力される第２の訂正不可能誤り検出信号を生成し、
前記反転処理ステップは、前記ＧＦ（２ｂ）上の誤り生成処理ステップで生成された前記ＧＦ（２ｂ）上のビット誤りポインタを基にして、前記ＧＦ（２ｂ）上のビット誤りポインタに対応した前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正する請求項４２に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４４】
前記誤り訂正処理ステップでは、前記ＧＦ（２ｒ）上の並列復号処理ステップで生成された前記第１の訂正不可能誤り検出信号と、前記ＧＦ（２ｂ）上の誤り生成処理ステップで生成された前記第２の訂正不可能誤り検出信号の論理和をとることにより、訂正能力を超えた誤りを検出したことを示す第３の訂正不可能誤り検出信号を出力する請求項４３に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４５】
前記ＧＦ（２ｂ）上の誤り生成処理ステップは、
シンドロームが非零であることを検出する誤りバイト検出処理ステップと、
前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトから前記ＧＦ（２ｂ）上のビット誤りポインタの１バイトを出力するｔビット誤り訂正復号処理ステップと、
入力信号の選択を制御信号に従って行うビットごと選択処理ステップと、
入力された信号のハミング重み１を検出するためのハミング重み検出処理ステップとを有する請求項４３又は請求項４４に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４６】
前記ＧＦ（２ｂ）上の誤り生成処理ステップは、誤りバイト検出処理ステップと、ｔビット誤り訂正復号処理ステップと、ビットごと選択処理ステップと、ハミング重み検出処理ステップとを有し、
前記誤りバイト検出処理ステップは、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトを入力とし、１ビットのシンドローム検出信号を出力し、
前記ｔビット誤り訂正復号処理ステップは、前記ＧＦ（２ｒ）上のビット誤りポインタの所定の１バイトを入力とし、前記ＧＦ（２ｂ）上のビット誤りポインタの前記所定の１バイトに対応する１バイトを出力すると共に、訂正能力をこえた誤りを検出する検出信号をも出力し、
前記ビットごと選択処理ステップは、２つの入力信号の各ビットどうしを制御信号に従って選択し、
前記ハミング重み検出処理ステップは、前記誤りバイト検出処理ステップから出力された前記シンドローム検出信号を入力とし、入力された前記シンドローム検出信号のハミング重みを計算し、前記ハミング重みが１の場合に１を出力し、そうでない場合に０を出力する請求項４３又は請求項４４に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４７】
前記ｔビット誤り訂正復号処理ステップでは、訂正能力をこえた前記誤りが、前記ＧＦ（２ｒ）上の誤りｅ’Iから写像されることのない前記ＧＦ（２ｂ）上の誤りｅIである請求項４６に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【請求項４８】
前記ＧＦ（２ｂ）上の誤り生成処理ステップでは、前記ｔビット誤り訂正復号処理ステップから出力された前記検出信号を多入力ＯＲゲート回路に入力し、前記多入力ＯＲゲート回路は、入力された前記検出信号に基づいて、前記第２の訂正不可能誤り検出信号を出力し、
また、前記ＧＦ（２ｂ）上の誤り生成処理ステップでは、前記ハミング重み検出処理ステップから出力された信号と、前記誤りバイト検出処理ステップから出力された前記シンドローム検出信号とをそれぞれ２入力ＡＮＤゲート回路に入力し、前記２入力ＡＮＤゲート回路から出力された信号を前記ビットごと選択処理ステップに用いる前記制御信号とし、
前記ビットごと選択処理ステップでは、前記ｔビット誤り訂正復号処理ステップから出力された信号、及び、前記バイトごとの誤りの和（ｅＡ）の選択を前記制御信号に従って行い、選択された信号を集め、前記ＧＦ（２ｂ）上のビット誤りポインタを出力する請求項４７に記載のバイト内複数スポッティバイト誤り訂正・検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スポッティバイト誤り訂正・検出方法及び装置に関し、より詳しくは、複数のビットをバイトとし、その複数のバイトから構成される語（ワード）に対して、任意の１バイト中に複数のスポッティバイト誤りが生じたときに、その誤りを検出または訂正するために用いて好適なバイト内複数スポッティバイト誤り訂正・検出方法及び装置に関する。
【背景技術】
【０００２】
近年、情報化社会の進展や半導体技術の進歩等により、ディジタルデータの信頼性向上がますます重要なものになってきている。ディジタルデータの伝送または記録を正確に行おうとする場合、送信データが伝送経路中でノイズ等の影響を受けて誤って伝送されたり、素子の故障、あるいは記録媒体等の欠陥等により生じた誤りを検出・訂正する必要がある。この誤りの検出・訂正を実現するために、符号理論を基礎とした誤り訂正・検出符号が従来より種々に開発されてきている。
【０００３】
従来の誤り訂正符号として、例えば、ｂビット（ｂは２以上の整数）の塊りをバイトと称し、１バイト中の任意の誤りを訂正する符号（ＳｂＥＣ符号と称する）として優れた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 ByteError Correcting 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年
【非特許文献１２】エス.ジェイ.ピーストラク(S.J.Piestrak),『ザ  ミニマル  テスト  セット  フォー  マルチアウトプット  スレッショウルド  サーキットズ  インプレメンテド  アズ  ソーティング  ネットワークス  “The minimal Test Setfor Multioutput Threshold Circuits Implemented as Sorting Networks”』,ＩＥＥＥ  トランスアクションズ  オン  コンピュータズ(IEEETransactions on Computers),第42巻,第6号,p.700-712,1993年6月
【発明の開示】
【発明が解決しようとする課題】
【００１２】
１９８０年代半ばまでは、半導体メモリ素子にはデータ１ビットの入出力を有する素子が主に使用されたことから、１素子の誤りを訂正し２素子までの誤りを検出する１ビット誤り訂正・２ビット誤り検出符号（ＳＥＣ−ＤＥＤ符号と称する）が多く使用されていた。ところが、１９８０年代半ばからメモリ素子の高集積化ニーズに対応して、データ４ビットの入出力を有する素子が主流となりはじめ、バイト幅ｂ＝４ビットである前述のＳ４ＥＣ−Ｄ４ＥＤ符号やＳＥＣ−ＤＥＤ−Ｓ４ＥＤ符号が主に使用されるようになってきた。さらに、１９９０年代半ばからはデータ８ビット、１６ビットの入出力を有する半導体メモリ素子が主流になりはじめた。
【００１３】
しかしながら、従来のＳｂＥＣ−ＤｂＥＤ符号のバイト幅ｂにｂ＝８またはｂ＝１６を適用する場合、全体の符号長に対する検査ビット数の占める割合がおよそ３０％から４０％と多大となって、符号化率が低下し、実用的に非常に大きな問題となっていた。
【００１４】
ところで、これらの半導体メモリ素子（ＤＲＡＭ素子）を使用したメモリ装置では、ノイズやアルファ粒子等によって一時故障が発生したり、ＤＲＡＭ素子自体が劣化して動作しなくなる固定故障が発生したりする。最近のＤＲＡＭ素子を用いた装置の８０％以上は一時故障であると言われており、特に、８ビット以上の多ビットデータ入出力を有するＤＲＡＭ素子ではバイト中の１、２、３ビット程度の比較的小さい数のビット誤りが大半であるとされている。
【００１５】
中でも比較的エネルギーレベルの低い電磁ノイズやアルファ粒子による一時誤り、及びメモリセルの固定故障を原因とする１ビット誤りが最も多く、最近では、前記ＤＲＡＭ素子を搭載したモバイル機器が多用されていることから、電磁環境が悪い中での使用も考慮しなければならなくなっている。また、高い高度を飛行する航空機や軍用機で用いられる電子機器中のＤＲＡＭ素子では、宇宙線に起因するエネルギーレベルの高い中性子粒子等の衝突により、２ビット、３ビット程度の誤りを有する一時故障が発生する可能性が高くなっている。さらに、衛星通信や宇宙通信で用いられる宇宙機器に搭載するＤＲＡＭ素子では、エネルギーレベルの高い粒子との衝突によって大きなダメージを受けてしまうことを考慮する必要があり、この場合２ビット以上の誤りを考慮しなければならないことが知られている。
【００１６】
以上のようなビット誤りの発生状況が多岐にわたっていることを踏まえれば、パラメータｔ及びｂに任意の値を与えて構成できる前記Ｓｔ／ｂＥＣ−ＳｂＥＤ符号は、８ビット以上のＤＲＡＭ素子を使用したメモリ装置に用いる場合に、非常に実用的な符号方式である。つまり、前記Ｓｔ／ｂＥＣ−ＳｂＥＤ符号は、バイト幅ｂより小さなｔビット（このｔの値は、誤りの傾向を調査して設計者が任意に決めることが可能である）までの１素子の誤り（スポッティバイト誤り）を訂正することが可能な機能、及び発生確率としては小さいもののｔビットを超える１バイト誤りを検出することが可能な機能を備えることにより、従来のバイト単位で行うReed-Solomon符号等の誤り制御符号と比較して大幅に少ない数の検査ビットで誤りを訂正・検出することができる。
【００１７】
また、任意の２素子（隣接した２素子に限らない）にまたがる誤りに対して、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号は、８ビット以上のＤＲＡＭ素子を使用したメモリ装置に用いる場合に非常に実用的な符号化方式である。つまり、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ−ＳｂＥＤ符号は、バイト幅ｂより小さなｔビットまでの１素子の誤りを訂正することが可能な機能（１スポッティバイト誤り訂正、Ｓｔ／ｂＥＣ）、２素子にまたがるスポッティバイト誤りを検出することが可能な機能（２スポッティバイト誤り検出、Ｄｔ／ｂＥＤ）、及び発生確率としては小さいもののｔビットを超える１バイト誤りを検出することが可能な機能（１バイト誤り検出、ＳｂＥＤ）を備えた符号であり、従来のバイト単位で行う符号方式と比較して大幅に少ない数の検査ビットでビット誤りを訂正・検出することができる。
【００１８】
さらに、２素子以上にまたがる誤りに対しては、理論上、一般にＧＦ（２ｂ）上で距離ｄを有するスポッティバイト誤り制御符号を構成することにより誤りを訂正・検出することができるようになっている。
【００１９】
しかしながら、前記ＧＦ（２ｂ）上で距離ｄを有するスポッティバイト誤り制御符号においては、１バイトにおけるｔビットを超える誤りを訂正・検出（ＳｂＥＤ機能など）することができないという問題を有していた。そのため、１バイト内にｔビットを超える誤り、すなわち、複数のスポッティバイト誤りが生じた場合においても訂正・検出する機能を有する符号の開発が求められてきている。
【００２０】
また、前記Ｓｔ／ｂＥＣ−Ｄｔ／ｂＥＤ符号等では訂正、検出ともにｔの値は等しく、訂正、検出に異なるｔの値を与えることができないという問題を有していた。
【００２１】
ここで、前記ＧＦ（２ｂ）上で距離ｄを有するスポッティバイト誤り制御符号のように、１バイト内に１スポッティバイト誤りのみが生じる誤りを『バイト内単一スポッティバイト誤り』と称するのに対し、１バイト内に複数のスポッティバイト誤り（つまり、２以上のスポッティバイト誤り）が生じる誤りを『バイト内複数スポッティバイト誤り』と称する。
【００２２】
本発明は、上述のような事情に鑑みてなされたものであり、本発明の目的は、多重のバイト内複数スポッティバイト誤りを制御することができる機能を備えたバイト内複数スポッティバイト誤り訂正・検出方法及び装置を提供することにある。
【００２３】
また、本発明のもう一つの目的は、１バイト内に生じた大きさの異なる２種類のスポッティバイト誤りを制御することができる機能を備えたバイト内複数スポッティバイト誤り訂正・検出方法及び装置を提供することにある。
【課題を解決するための手段】
【００２４】
本発明は、入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備えるバイト内複数スポッティバイト誤り訂正・検出装置に関し、本発明の上述目的は、  前記符号化手段は、スポッティバイト誤り制御符号を表現するパリティ検査行列と、前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることにより、或いは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビット（１≦ｔ≦ｂ）までの誤りをスポッティバイト誤りと称し、１バイト内に複数の前記スポッティバイト誤りが生じる誤りをバイト内複数スポッティバイト誤りと称することを前提とし、前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、距離ｄに対し、
2006101429.tif 000003
を有することにより、或いは、前記ｔ値、ｂ値、ｄ値を任意に設定することにより、或いは、前記情報伝送路は、情報通信システムであることにより、或いは、前記情報伝送路は、メモリシステムであることにより、或いは、前記情報伝送路は、バス線回路であることによって効果的に達成される。
【００２５】
また、本発明の上述目的は、前記パリティ検査行列は、前記距離ｄを有するバイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000004
ただし、Ｒ＝ｑ＋（ｄ−２）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000005
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000006
を満足し、ここで、
2006101429.tif 000007
はｘを超えない最小の整数を表し、また、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000008
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000009
を有する符号の検査行列、すなわち、
2006101429.tif 000010
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、γは２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元であって、γｉＨ”＝［γｉｈ０”、γｉｈ１”、…、γｉｈｂ−１”］が成立するように構成されることによって効果的に達成される。
【００２６】
また、本発明の上述目的は、前記パリティ検査行列は、前記距離ｄを有する伸長バイト内複数スポッティバイト誤り制御符号に用いる、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000011
ただし、Ｒ≧ｑ＋（ｄ−２）ｒ、かつ（Ｒ−ｑ）は（ｄ−２）の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／（ｄ−２）、０≦ｉ≦ｎ−１、（Ｒ−ｑ）は（ｄ−２）の倍数とし、ｎ＝２（Ｒ−ｑ）／（ｄ−２）−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足し、前記行列Ｈ’のランクがｂに等しいとき、前記行列Ｈ’はランクｂのｂ×ｂ行列であり、前記行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、前記行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しくなり、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000012
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、
2006101429.tif 000013
を満足し、前記行列Ｈ”のランクがｂに等しいとき、前記行列Ｈ”はランクｂのｂ×ｂ行列であり、前記行列Ｈ”のランクが
2006101429.tif 000014
のとき、前記行列Ｈ”は最小ハミング距離
2006101429.tif 000015
を有する符号の検査行列、すなわち、
2006101429.tif 000016
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しくなり、Ｒ≧ｑ＋（ｄ−２）ｒ、かつＲ−ｑはｄ−２の倍数とし、γは２を底とする（Ｒ−ｑ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｑ）／（ｄ−２））の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”
）、γｉΦ（ｈ１” ）、・・・、γｉΦ（ｈｂ−１”
）］が成立するように構成され、ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／（ｄ−２））への準同型写像（homomorphism）であり、すなわち、Φ：ＧＦ（２ｑ）→ＧＦ（２（Ｒ−ｑ）／（ｄ−２））であることによって効果的に達成される。
【００２７】
また、本発明の上述目的は、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される場合に、ここで、バイト内のｔビットまでの誤りをｔ／ｂ誤りと称し、バイト内のｔ’ビットまでの誤りをｔ’／ｂ誤りと称することを前提とし、ただし、１≦ｔ、ｔ’≦ｂ、且つ、ｔ≠ｔ’であり、前記パリティ検査行列で表現される前記スポッティバイト誤り制御符号は、１バイト内に生じた大きさの異なる２種類のスポッティバイト誤り（つまり、前記ｔ／ｂ誤り及び前記ｔ’／ｂ誤り）を制御する機能を備えることにより、或いは、前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、（ｔ／ｂ＋ｔ’／ｂ）誤り（つまり、ｔ／ｂ誤りとｔ’／ｂ誤りの複合誤り）を検出する機能を有するＳｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号であり、前記Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000017
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）であることにより、或いは、前記スポッティバイト誤り制御符号は、１個のｔ／ｂ誤りを訂正し、且つ、２個のｔ’／ｂ誤りを検出する機能を有するＳｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号であり、前記Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000018
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔまたはｔ＋２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ＋２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足し、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γは２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）であることにより、或いは、前記スポッティバイト誤り制御符号は、（ｔ／ｂ＋ｔ’／ｂ）誤りを訂正する機能を有する（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号であり、前記（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000019
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋２ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋２ｔ’、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（ｔ＋ｔ’、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）であることにより、或いは、前記スポッティバイト誤り制御符号は、２個のｔ／ｂ誤りを訂正し、且つ、１個のｔ’／ｂ誤り（ｔ＜ｔ’）を訂正する機能を有するＤｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号であり、前記Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号に用いる前記パリティ検査行列は、Ｒ行Ｎ列を有する次の行列Ｈであり、
2006101429.tif 000020
ただし、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、また、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１であり、行列Ｈ’は、Ｈ’＝［ｈ０’、ｈ１’、・・・、ｈｂ−１’］に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、４ｔまたは２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（４ｔ、２ｔ’）、ｂ）を満足し、また、行列Ｈ”は、Ｈ”＝［ｈ０”、ｈ１”、・・・、ｈｂ−１”］に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ’）、ｂ）を満足し、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γは２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元であって、γｉＨ”＝［γｉΦ（ｈ０”）、γｉΦ（ｈ１”）、・・・、γｉΦ（ｈｂ−１”）］が成立するように構成され、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）であることによって効果的に達成される。
【００２８】
また、本発明の上述目的は、前記誤り訂正手段は、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力することにより、或いは、前記誤り訂正手段は、Ｈ’復号手段と、Ｈ”乗算手段と、ＧＦ（２ｒ）上の並列復号手段と、ＧＦ（２ｂ）上の誤り生成手段と、反転手段とから構成されることにより、或いは、前記Ｈ’復号手段は、前記シンドローム生成手段で生成された前記シンドロームの上位ｑビットを基にして、バイトごとの誤りの和（ｅＡ）を生成し、前記Ｈ”乗算手段は、前記Ｈ’復号手段で生成された前記バイトごとの誤りの和（ｅＡ）を基にして、前記シンドロームの上位ｑビットとＨ”の転置行列の積を生成し、前記ＧＦ（２ｒ）上の並列復号手段は、前記Ｈ”乗算手段で生成された前記シンドロームの上位ｑビットとＨ”の転置行列の積、及び前記シンドローム生成手段で生成された前記シンドロームの上位ｑビットを除く残りの下位ビットを基にして、ＧＦ（２ｒ）上のビット誤りポインタ、及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号を生成し、前記ＧＦ（２ｂ）上の誤り生成手段は、前記Ｈ’復号手段で生成された前記バイトごとの誤りの和（ｅＡ）、及び、前記ＧＦ（２ｒ）上の並列復号手段で生成された前記ＧＦ（２ｒ）上のビット誤りポインタを基にして、ＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ、及び誤り訂正が不可能とみなされたときに出力される第２の訂正不可能誤り検出信号を生成し、前記反転手段は、前記ＧＦ（２ｂ）上の誤り生成手段で生成された前記ＧＦ（２ｂ）上のビット誤りポインタを基にして、前記ＧＦ（２ｂ）上のビット誤りポインタに対応した前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正することにより、或いは、前記誤り訂正手段では、前記ＧＦ（２ｒ）上の並列復号手段で生成された前記第１の訂正不可能誤り検出信号と、前記ＧＦ（２ｂ）上の誤り生成手段で生成された前記第２の訂正不可能誤り検出信号の論理和をとることにより、訂正能力を超えた誤りを検出したことを示す第３の訂正不可能誤り検出信号を出力することにより、或いは、前記ＧＦ（２ｂ）上の誤り生成手段は、シンドロームが非零であることを検出する誤りバイト検出手段と、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトから前記ＧＦ（２ｂ）上のビット誤りポインタの１バイトを出力するｔビット誤り訂正復号手段と、入力信号の選択を制御信号に従って行うビットごと選択手段と、入力された信号のハミング重み１を検出するためのハミング重み検出手段とを備えることにより、或いは、前記ＧＦ（２ｂ）上の誤り生成手段は、誤りバイト検出手段と、ｔビット誤り訂正復号手段と、ビットごと選択手段と、ハミング重み検出手段とを備えており、前記誤りバイト検出手段は、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトを入力とし、１ビットのシンドローム検出信号を出力し、前記ｔビット誤り訂正復号手段は、前記ＧＦ（２ｒ）上のビット誤りポインタの所定の１バイトを入力とし、前記ＧＦ（２ｂ）上のビット誤りポインタの前記所定の１バイトに対応する１バイトを出力すると共に、訂正能力をこえた誤りを検出する検出信号をも出力し、前記ビットごと選択手段は、２つの入力信号の各ビットどうしを制御信号に従って選択し、前記ハミング重み検出手段は、前記誤りバイト検出手段から出力された前記シンドローム検出信号を入力とし、入力された前記シンドローム検出信号のハミング重みを計算し、前記ハミング重みが１の場合に１を出力し、そうでない場合に０を出力するように構成されることにより、或いは、前記ｔビット誤り訂正復号手段では、訂正能力をこえた前記誤りが、前記ＧＦ（２ｒ）上の誤りｅ’Iから写像されることのない前記ＧＦ（２ｂ）上の誤りｅIであることにより、或いは、前記ＧＦ（２ｂ）上の誤り生成手段では、前記ｔビット誤り訂正復号手段から出力された前記検出信号を多入力ＯＲゲート回路に入力し、前記多入力ＯＲゲート回路は、入力された前記検出信号に基づいて、前記第２の訂正不可能誤り検出信号を出力し、また、前記ＧＦ（２ｂ）上の誤り生成手段では、前記ハミング重み検出手段から出力された信号と、前記誤りバイト検出手段から出力された前記シンドローム検出信号とをそれぞれ２入力ＡＮＤゲート回路に入力し、前記２入力ＡＮＤゲート回路から出力された信号を前記ビットごと選択手段の前記制御信号とし、前記ビットごと選択手段では、前記ｔビット誤り訂正復号手段から出力された信号、及び、前記バイトごとの誤りの和（ｅＡ）の選択を前記制御信号に従って行い、選択された信号を集め、前記ＧＦ（２ｂ）上のビット誤りポインタを出力することによって効果的に達成される。
【００２９】
更に、本発明は、入力情報データを基に送信語を生成する符号化処理ステップと、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理ステップとを有するバイト内複数スポッティバイト誤り訂正・検出方法に関し、本発明の上述目的は、前記符号化処理ステップは、スポッティバイト誤り制御符号を表現するパリティ検査行列と、前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより、前記送信語を生成し、前記復号処理ステップは、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理ステップと、前記シンドローム生成処理ステップにより生成されたシンドロームを基に前記受信語の誤りを訂正または検出する誤り訂正処理ステップとを有することにより、或いは、前記誤り訂正処理ステップは、前記シンドロームを基に前記受信語の何れのビットが誤っているかを検出するビット誤りポインタを生成し、生成された前記ビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正し、また、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可能誤り検出信号を出力することにより、或いは、前記誤り訂正処理ステップは、Ｈ’復号処理ステップと、Ｈ”乗算処理ステップと、ＧＦ（２ｒ）上の並列復号処理ステップと、ＧＦ（２ｂ）上の誤り生成処理ステップと、反転処理ステップとを有することにより、或いは、前記Ｈ’復号処理ステップは、前記シンドローム生成処理ステップで生成された前記シンドロームの上位ｑビットを基にして、バイトごとの誤りの和（ｅＡ）を生成し、前記Ｈ”乗算処理ステップは、前記Ｈ’復号処理ステップで生成された前記バイトごとの誤りの和（ｅＡ）を基にして、前記シンドロームの上位ｑビットとＨ”の転置行列の積を生成し、前記ＧＦ（２ｒ）上の並列復号処理ステップは、前記Ｈ”乗算処理ステップで生成された前記シンドロームの上位ｑビットとＨ”の転置行列の積、及び前記シンドローム生成処理ステップで生成された前記シンドロームの上位ｑビットを除く残りの下位ビットを基にして、ＧＦ（２ｒ）上のビット誤りポインタ、及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力される第１の訂正不可能誤り検出信号を生成し、前記ＧＦ（２ｂ）上の誤り生成処理ステップは、前記Ｈ’復号処理ステップで生成された前記バイトごとの誤りの和（ｅＡ）、及び、前記ＧＦ（２ｒ）上の並列復号処理ステップで生成された前記ＧＦ（２ｒ）上のビット誤りポインタを基にして、ＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ、及び誤り訂正が不可能とみなされたときに出力される第２の訂正不可能誤り検出信号を生成し、前記反転処理ステップは、前記ＧＦ（２ｂ）上の誤り生成処理ステップで生成された前記ＧＦ（２ｂ）上のビット誤りポインタを基にして、前記ＧＦ（２ｂ）上のビット誤りポインタに対応した前記受信語のビット値を反転させることにより、前記受信語の誤りを訂正することにより、或いは、前記誤り訂正処理ステップでは、前記ＧＦ（２ｒ）上の並列復号処理ステップで生成された前記第１の訂正不可能誤り検出信号と、前記ＧＦ（２ｂ）上の誤り生成処理ステップで生成された前記第２の訂正不可能誤り検出信号の論理和をとることにより、訂正能力を超えた誤りを検出したことを示す第３の訂正不可能誤り検出信号を出力することによって効果的に達成される。
【００３０】
また、本発明の上述目的は、前記ＧＦ（２ｂ）上の誤り生成処理ステップは、シンドロームが非零であることを検出する誤りバイト検出処理ステップと、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトから前記ＧＦ（２ｂ）上のビット誤りポインタの１バイトを出力するｔビット誤り訂正復号処理ステップと、入力信号の選択を制御信号に従って行うビットごと選択処理ステップと、入力された信号のハミング重み１を検出するためのハミング重み検出処理ステップとを有することにより、或いは、前記ＧＦ（２ｂ）上の誤り生成処理ステップは、誤りバイト検出処理ステップと、ｔビット誤り訂正復号処理ステップと、ビットごと選択処理ステップと、ハミング重み検出処理ステップとを有し、前記誤りバイト検出処理ステップは、前記ＧＦ（２ｒ）上のビット誤りポインタの１バイトを入力とし、１ビットのシンドローム検出信号を出力し、前記ｔビット誤り訂正復号処理ステップは、前記ＧＦ（２ｒ）上のビット誤りポインタの所定の１バイトを入力とし、前記ＧＦ（２ｂ）上のビット誤りポインタの前記所定の１バイトに対応する１バイトを出力すると共に、訂正能力をこえた誤りを検出する検出信号をも出力し、前記ビットごと選択処理ステップは、２つの入力信号の各ビットどうしを制御信号に従って選択し、前記ハミング重み検出処理ステップは、前記誤りバイト検出処理ステップから出力された前記シンドローム検出信号を入力とし、入力された前記シンドローム検出信号のハミング重みを計算し、前記ハミング重みが１の場合に１を出力し、そうでない場合に０を出力することにより、或いは、前記ｔビット誤り訂正復号処理ステップでは、訂正能力をこえた前記誤りが、前記ＧＦ（２ｒ）上の誤りｅ’Iから写像されることのない前記ＧＦ（２ｂ）上の誤りｅIであることにより、或いは、前記ＧＦ（２ｂ）上の誤り生成処理ステップでは、前記ｔビット誤り訂正復号処理ステップから出力された前記検出信号を多入力ＯＲゲート回路に入力し、前記多入力ＯＲゲート回路は、入力された前記検出信号に基づいて、前記第２の訂正不可能誤り検出信号を出力し、また、前記ＧＦ（２ｂ）上の誤り生成処理ステップでは、前記ハミング重み検出処理ステップから出力された信号と、前記誤りバイト検出処理ステップから出力された前記シンドローム検出信号とをそれぞれ２入力ＡＮＤゲート回路に入力し、前記２入力ＡＮＤゲート回路から出力された信号を前記ビットごと選択処理ステップに用いる前記制御信号とし、前記ビットごと選択処理ステップでは、前記ｔビット誤り訂正復号処理ステップから出力された信号、及び、前記バイトごとの誤りの和（ｅＡ）の選択を前記制御信号に従って行い、選択された信号を集め、前記ＧＦ（２ｂ）上のビット誤りポインタを出力することによって効果的に達成される。
【発明の効果】
【００３１】
本発明に係るバイト内複数スポッティバイト誤り訂正・検出方法及び装置によれば、符号を表現するパリティ検査行列と入力情報データとを基に生成した検査情報を前記入力情報データに付加した送信語が、情報伝送路中で発生した誤りを有する可能性のある受信語に対し、前記パリティ検査行列を基にシンドロームを生成するとともに、このシンドロームを基に前記受信語の誤りを訂正または検出するようにしているので、１バイト中の２ビット、３ビット等のｔビットまでの誤りであるスポッティバイト誤りに対し、任意の数のバイト内複数スポッティバイト誤り（誤りの傾向を調査して設計者が任意に決めることができる）を訂正・検出する機能を有するバイト内複数スポッティバイト誤り制御符号を実現することができた。
【００３２】
これにより、誤りを検出または訂正する符号であるパリティ検査行列の構成や復号の処理手順を、誤りの発生状況ごとに対応させる必要がなく統一的に扱うことが可能となり、本発明の符号機能におけるｔ値、ｂ値、ｄ値を任意に設定するだけで、パリティ検査行列Ｈや復号手順を統一的に扱うことが可能となり、誤りの発生状態に柔軟に対応できる符号機能を提供することができる。また、本発明による大きさの異なる２種類のスポッティバイト誤りを制御する符号により、誤りの発生状態にさらに柔軟に対応できる符号機能を提供することができる。
【００３３】
さらに、ｂビットであるバイト長よりも小さな整数ビット長ｔを選ぶことにより、従来のバイト誤り制御符号（ｔ＝ｂに相当）と比較して、検査ビット数を大幅に減少することが可能となる。これにより、符号長に対する検査ビット数の占める割合を小さくさせて、符号化率を格段に向上することが可能となり、高効率且つ高信頼性のあるデータ転送を実現することができる。
【００３４】
要するに、従来の符号技術では存在しない、『多重のバイト内複数スポッティバイト誤りを制御できる』といった優れた機能を備える本発明のバイト内複数スポッティバイト誤り訂正・検出方法及び装置によれば、従来のリードソロモン符号（Reed-Solomon符号）による多重バイト誤り制御符号と比較して、検査ビット数を少なくして符号化率を向上させることができ、また、ビット誤りの発生状態に柔軟に対応できる符号機能を提供することができるといった顕著な効果を奏する。
【００３５】
また、『１バイト内に生じた大きさの異なる２種類のスポッティバイト誤りを制御することができる』といった機能を備える本発明のバイト内複数スポッティバイト誤り訂正・検出方法及び装置によれば、従来の大きさが一定であるスポッティバイト誤り制御符号、及びリードソロモン符号（Reed-Solomon符号）と比較して、検査ビット数を少なくして符号化率を向上させ、また、ビット誤りの発生状態に柔軟に対応できる符号機能を提供することができるといった顕著な効果を奏する。
【発明を実施するための最良の形態】
【００３６】
以下、本発明を実施するための最良の形態について、図面を参照しながら詳細に説明する。
【００３７】
本発明を説明するための用語を次のように定義する。まず、本発明の実施形態において、対象とするディジタルデータとは、０と１との組合せの信号（２進化符号）であり、ビット誤りの発生とは、符号語中の任意のビットが、０→１または１→０になることを意味することとする。また、スポッティバイト誤りの発生とは、ｂビットからなるバイト中のｔビット（ｔ≦ｂ）までが０→１または１→０になることを意味することとする。なお、本実施の形態で、「誤り」とある場合、特に明記していない限り、前記「ビット誤り」、「スポッティバイト誤り」のすべてを包含していることとする。また、１バイト内に複数のスポッティバイト誤り（つまり、２以上のスポッティバイト誤り）が生じる誤りを『バイト内複数スポッティバイト誤り』と称する。
【００３８】
まず、本発明に係るバイト内複数スポッティバイト誤り訂正・検出装置１００の全体構成について説明する。図１は、本発明のバイト内複数スポッティバイト誤り訂正・検出装置１００（以下、スポッティバイト装置１００と略す）の概略構成を示すブロック図である。図１に示すように、スポッティバイト装置１００は、符号化回路２、回路３、復号回路４等を備えた構成になっている。
【００３９】
符号化回路２は、対象のディジタルデータ（以下、入力情報データ３０と称する）に対して、誤りの訂正・検出を行う検査情報を生成する回路である。なお、検査情報は、任意個の検査ビットより構成されている。
【００４０】
回路３は、メモリ等の通信路に相当し、本実施形態では、回路３を経たデータには誤りが含まれる可能性が存在する構成としている。つまり、符号化回路２より出力されて回路３に入力されるデータには誤りが生じていないのに対して、回路３から出力されるデータには、誤りが発生している場合を含んでいる。
【００４１】
復号回路４は、シンドローム生成回路１と誤り訂正回路５とを備えた構成になっている。復号回路４は、受信語３２に誤りが含まれているか否かを検出し、その誤り箇所を特定して訂正を行うための回路である。復号回路４の詳細な構成については、後述する復号処理で説明する。
【００４２】
なお、後述する符号化処理及び復号処理では、ガロア体理論に基づいた行列演算を行うことから、符号化回路２、復号回路４、または通信路中における各データを、英字で付した行列、またはベクトルで表現する。具体的には、例えば、入力情報データＤ、符号（パリティ検査行列）Ｈ、検査情報Ｃ、送信語Ｖ、受信語Ｖ’、シンドロームＳと表している。
【００４３】
次に、本発明のスポッティバイト装置１００の全体動作について説明する。図２は、図１に示された本発明のスポッティバイト装置１００の全体動作の処理手順を示すフローチャートである。
【００４４】
図２に示されるように、まず、符号化回路２では、入力情報データ（Ｄ）３０が入力されると、詳細については後述するパリティ検査行列（Ｈ）を用いて検査情報（Ｃ）を生成する（ステップＳ２００）。次に、符号化回路２では、この検査情報（Ｃ）を入力情報データ（Ｄ）３０に付加して、送信語（Ｖ）３１としてメモリ等の通信路である回路３に送出する（ステップＳ２０１）。そして、回路３を経て誤りを含む可能性のある受信語（Ｖ’）３２は、復号回路４に入力される（ステップＳ２０２）。
【００４５】
次に、復号回路４では、まず、符号化回路２で用いたパリティ検査行列（Ｈ）を利用して、入力された受信語（Ｖ’）３２に誤りが発生しているか否かを調べる。具体的には、復号回路４のシンドローム生成回路１が、符号を表現しているパリティ検査行列（Ｈ）を転置させた転置行列（ＨＴ）を、受信語（Ｖ’）３２に対して乗算することによりシンドローム（Ｓ）を生成する（ステップＳ２０３）。シンドローム（Ｓ）３３の値は受信語（Ｖ’）３２に応じて変化するため、受信語（Ｖ’）３２に誤りが含まれているかを判断することが可能となる。
【００４６】
そこで、復号回路４の誤り訂正回路５は、前記シンドローム（Ｓ）３３の値に基づいて、まず誤りを検出したか否か（ステップＳ２０４）、検出した場合に、誤り訂正が可能か否かを判断し（ステップＳ２０５）、前記判断の結果、訂正可能であれば誤りの訂正を行う（ステップＳ２０６）。そして、誤り訂正回路５は、受信語Ｖ’に対してスポッティバイト誤りの訂正処理を施した場合、訂正後のＶ’を受信語出力情報データ（Ｖ＊）３４として出力する（ステップＳ２０７）。これに対して、ステップＳ２０５の判断の結果、訂正不可能なスポッティバイト誤り等が検出された場合には、誤り訂正回路５は、訂正不可能な誤り検出信号としてのＵＣＥ（Uncorrectable  Error）信号３５を出力する（ステップＳ２０８）。
【００４７】
次に、前述した符号化回路２及び復号回路４で用いられるパリティ検査行列（Ｈ）の構成について、詳細に説明する。本発明のパリティ検査行列Ｈ（Ｈマトリクス、符号マトリクス、または単に検査行列とも称される）は、複数のスポッティバイト誤りを訂正・検出する機能を有する符号である。
【００４８】
本実施の形態では、任意のｄ（ｄは３以上の整数）、ｔ（ｔは１以上ｂ以下の整数）、及びｂ（２以上の整数）に対して構成できる一般的な符号構成法を提示するとともに、その符号により実際に誤りの訂正・検出ができる方法を示し、またそのための符号化回路および復号回路を提示し、前記符号化回路及び復号回路によって誤りが具体的に訂正・検出できることを示す。
【００４９】
なお、距離ｄに対し、
2006101429.tif 000021
を有していることを具体的に示す。例えば、距離ｄ＝５の２重バイト内複数スポッティバイト誤り訂正符号の場合、
2006101429.tif 000022
となる。
【００５０】
また、本符号構成法において、ｔ＝ｂのとき、正確には後述するように、
2006101429.tif 000023
のとき、従来のバイト誤り制御符号であるリード・ソロモン符号（ＲＳ符号）に一致する。
【００５１】
いま、Ｋビットの入力情報データ（Ｄ）３０に対してＲビットの検査情報（Ｃ）を付加し、ある機能を満足するＮ＝Ｋ＋Ｒビットの長さを有する送信語Ｖ（Ｎビットの行ベクトル）を構成することができたときに、この送信語（Ｖ）と、符号を規定するＲ行Ｎ列の２元パリティ検査行列（Ｈ）との間には、Ｖ・ＨＴ＝０の関係が成立する。ここで、ＨＴはパリティ検査行列（Ｈ）の行と列を入れ替えて生成した置換行列であり、また、右辺の０はＲビットの零行ベクトルを示している。
【００５２】
本実施形態では、距離ｄを有するバイト内複数スポッティバイト誤り制御符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数１に示すような構成としている。
【００５３】
【数１】
2006101429.tif 000024
ただし、Ｒ＝ｑ＋（ｄ−２）ｒ、Ｎ＝ｂｎ、０≦ｉ≦ｎ−１、ｎ＝２ｒ−１である。
【００５４】
上記数１を構成する行列Ｈ’は、下記数２に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足する。
【００５５】
【数２】
2006101429.tif 000025
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【００５６】
また、上記数１を構成する行列Ｈ”は、下記数３に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000026
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、
2006101429.tif 000027
を満足する。ここで、
2006101429.tif 000028
はｘを超えない最小の整数を表す。
【００５７】
【数３】
2006101429.tif 000029
ここで、行列Ｈ”のランクがｂに等しいとき、行列Ｈ”はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ”のランクが
2006101429.tif 000030
のとき、行列Ｈ”は最小ハミング距離
2006101429.tif 000031
を有する符号の検査行列、すなわち、
2006101429.tif 000032
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しい。
【００５８】
次に、γを２を底とするｒ次の拡大体ＧＦ（２ｒ）の原始元とするときに、γｉＨ”は下記数４で定義することができる。
【００５９】
【数４】
2006101429.tif 000033
このとき、最大符号長Ｎは、Ｎ＝ｂ（２ｒ―１）である。
【００６０】
上記数１に示したパリティ検査行列（Ｈ）は、パラメータ
2006101429.tif 000034
とした場合に、Ｈ’及びＨ”はランクｂを有することから、従来のＲＳ符号のパリティ検査行列と一致する。
【００６１】
また、本実施形態では、伸長符号を定義することができる。距離ｄを有する伸長バイト内複数スポッティバイト誤り制御符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）は、下記数５に示すような構成とすることができる。
【００６２】
【数５】
2006101429.tif 000035
ただし、Ｒ≧ｑ＋（ｄ−２）ｒ、かつ（Ｒ−ｑ）は（ｄ−２）の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／（ｄ−２）、０≦ｉ≦ｎ−１、（Ｒ−ｑ）は（ｄ−２）の倍数とし、ｎ＝２（Ｒ−ｑ）／（ｄ−２）−１である。
【００６３】
上記数５を構成する行列Ｈ’は、下記数６に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、（ｄ−１）ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（（ｄ−１）ｔ、ｂ）を満足する。
【００６４】
【数６】
2006101429.tif 000036
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが（ｄ−１）ｔ＜ｂのとき、行列Ｈ’は最小ハミング距離（ｄ−１）ｔ＋１を有する符号の検査行列、すなわち、（ｄ−１）ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【００６５】
また、上記数１を構成する行列Ｈ”は、下記数７に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、
2006101429.tif 000037
またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、
2006101429.tif 000038
を満足する。
【００６６】
【数７】
2006101429.tif 000039
ここで、行列Ｈ”のランクがｂに等しいとき、行列Ｈ”はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ”のランクが
2006101429.tif 000040
のとき、行列Ｈ”は最小ハミング距離
2006101429.tif 000041
を有する符号の検査行列、すなわち、
2006101429.tif 000042
ビット誤り検出機能を有する（ｂ、ｂ−ｒ）符号のパリティ検査行列に等しい。
【００６７】
次に、Ｒ≧ｑ＋（ｄ−２）ｒかつＲ−ｑはｄ−２の倍数とし、γを２を底とする（Ｒ−ｑ）／（ｄ−２）次の拡大体ＧＦ（２（Ｒ−ｑ）／（ｄ−２））の原始元とするときに、γｉＨ”は下記数８で定義することができる。
【００６８】
【数８】
2006101429.tif 000043
ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／（ｄ−２））への準同型写像（homomorphism）である。すなわち、Φ：ＧＦ（２ｑ）→ＧＦ（２（Ｒ−ｑ）／（ｄ−２））である。このとき、最大符号長Ｎは、Ｎ＝ｂ・２（Ｒ−ｑ）／（ｄ−２）＋（Ｒ−ｑ）／（ｄ−２）である。また、Ｒ≧ｑ＋（ｄ−２）ｒであることから、数５のＨの２行目から下の行に用いるＨ”の行数ｒ’はｒより大きい値をとることができ、数５で表される符号は、（ｄ−２）ビットずつ検査ビット数を増大させることにより、任意の符号長に対して構成できる符号であることに注意する必要がある。
【００６９】
上記数５に示したパリティ検査行列（Ｈ）は、パラメータ
2006101429.tif 000044
とした場合に、Ｈ’及びＨ”はランクｂを有することから、従来の２次伸長ＲＳ符号のパリティ検査行列と一致する。
【００７０】
次に、上記数１に示したパリティ検査行列（Ｈ）で表される符号が、距離ｄに対し、
2006101429.tif 000045
を有していることを具体的に示す。一般に、
2006101429.tif 000046
において、パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、・・・、Ｈｎ−１］が、以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【００７１】
【数９】
2006101429.tif 000047
【００７２】
【数１０】
2006101429.tif 000048
【００７３】
【数１１】
2006101429.tif 000049
ここで、１バイト中のｔビットまでの誤りの集合をＥｔ／ｂとし、ｅｉは誤りの集合Ｅｔ／ｂに含まれる任意の誤りとする。また、ｉ１、ｉ２、・・・、ｉｋ・・・、ｉｄ−１（０≦ｉ１、ｉ２、・・・、ｉｋ、・・・、ｉｄ−１≦ｎ−１）はすべて異なるものとする。
【００７４】
スポッティバイト誤り訂正は、前述したシンドローム生成回路１が生成するシンドローム（Ｓ）３３を用いて実行する。ここで、シンドローム（Ｓ）３３と前記パリティ検査行列（Ｈ）との関係は、Ｓ＝Ｖ’・ＨＴで表される。いま、受信語（Ｖ’）３２が元々の送信語（Ｖ）３１に対して誤り（Ｅ）を含み、Ｖ’＝Ｖ＋Ｅで表されるとき、シンドローム（Ｓ）３３は、Ｓ＝Ｖ’・ＨＴ＝（Ｖ＋Ｅ）・ＨＴ＝Ｖ・ＨＴ＋Ｅ・ＨＴとなる。
【００７５】
前述したように、Ｖ・ＨＴ＝０の関係が成立していることから、結局、シンドロームＳ＝Ｅ・ＨＴが成り立つ。つまり、シンドローム（Ｓ）３３は、送信語（Ｖ）３１に影響されずに誤り（Ｅ）のみで決まることから、シンドローム（Ｓ）３３に基づいてスポッティバイト誤り訂正を行うことが可能か否かは、パリティ検査行列（Ｈ）と誤り（Ｅ）とから計算されるＥ・ＨＴの値の結果によって決定できるものである。
【００７６】
上記数９、数１０、数１１に示した必要十分条件は、距離ｄに対し、訂正・検出可能なすべてのバイト内複数スポッティバイト誤りのシンドロームと訂正可能な他のすべてのバイト内複数スポッティバイト誤りのシンドロームが異なることを示している。すなわち、ｍ個以下のバイト内複数スポッティバイト誤りのシンドロームと他の
2006101429.tif 000050
個以下のバイト内複数スポッティバイト誤りのシンドロームが異なればよい。よって、
2006101429.tif 000051
個のバイト内複数スポッティバイト誤りのシンドローム和が０とならなければよい。
【００７７】
数９は、ｍ個のバイト内複数スポッティバイト誤りと
2006101429.tif 000052
個のバイト内複数スポッティバイト誤りが、すべて同じバイトに生じた場合であり、それぞれのシンドロームが異なることを示している。
【００７８】
また、数１０は、ｍ個のバイト内複数スポッティバイト誤りと
2006101429.tif 000053
個のバイト内複数スポッティバイト誤りが生じ、うち２からｄ−２バイトにおいて、バイト内複数スポッティバイト誤りが同じバイトに生じている場合であり、これらのシンドロームが異なることを示している。
【００７９】
さらに、数１１は、ｍ個のバイト内複数スポッティバイト誤りと
2006101429.tif 000054
個のバイト内複数スポッティバイト誤りが、すべて異なるバイトに生じている場合であり、それぞれのシンドロームが異なることを示している。
【００８０】
ここで、（ｅｉ＋・・・＋ｅｉ＋ｊ）は、ｊ個以下のバイト内複数スポッティバイト誤りを包含するため、（ｄ−１）個のバイト内複数スポッティバイト誤りのシンドローム和が０とならないことを示すことにより、（ｄ−１）個未満のバイト内複数スポッティバイト誤りのシンドロームが異なることを示すことができる。
【００８１】
よって、数１に示すパリティ検査行列で表現される符号が、上記数９、数１０、数１１に示した必要十分条件を満たすことを示すことにより、距離ｄに対し、
2006101429.tif 000055
を有していることを以下に示す。
＜１＞必要十分条件（数９）を満たしていることの証明
シンドロームＳとして、下記数１２の関係が成立していると仮定する。
【００８２】
【数１２】
2006101429.tif 000056
数１２において、Ｈ’はランクがＭｉｎ（（ｄ−１）ｔ、ｂ）、かつｅ１＋ｅ２＋・・・＋ｅｄ−１≠０より（ｅ１＋ｅ２＋・・・＋ｅｄ−１）・Ｈ’Ｔ≠０。よって、数１で表される符号は、必要十分条件（数９）を満たしている。
＜２＞必要十分条件（数１０）を満たしていることの証明
シンドロームＳとして、下記数１３の関係が成立したと仮定する。
【００８３】
【数１３】
2006101429.tif 000057
数１３の（ｅ１＋ｅ２＋・・・＋ｅｄ−１）・Ｈ’Ｔ＝０において、Ｈ’はランクがＭｉｎ（（ｄ−１）ｔ、ｂ）より、下記数１４が得られる。
【００８４】
【数１４】
2006101429.tif 000058
数１４において、右からＨ”Ｔをかけると、下記数１５が得られる。
【００８５】
【数１５】
2006101429.tif 000059
数１３、数１５において、
2006101429.tif 000060
をそれぞれｘ１、ｘ２、・・・、ｘρ、ρ＞１、とおくと、下記数１６が得られる。ここで、
2006101429.tif 000061
より、
2006101429.tif 000062
となるｉは、高々１個のみ存在する。Ｈ”はランク
2006101429.tif 000063
より、ｘ２≠０、ｘ３≠０、・・・、ｘρ≠０（ｘ１は０となることもある）、ρ＞１、となる。
【００８６】
【数１６】
2006101429.tif 000064
数１６において、上からρ（＜ｄ−１）個の式を行列の形で表すと、下記数１７が得られる。
【００８７】
【数１７】
2006101429.tif 000065
数１７中のρ行ρ列の行列は、ヴァンデルモンドの行列の形をしているため、正則行列である。よって、数１７の両辺に左からこの行列の逆行列を乗算すると、下記数１８が得られる。
【００８８】
【数１８】
2006101429.tif 000066
数１８は、ｘ１＝０、ｘ２＝０、・・・、ｘρ＝０、ρ＞１、となり、前提であるｘ２≠０、ｘ３≠０、・・・、ｘρ≠０に矛盾する。よって、数１で表される符号は、必要十分条件（数１０）を満たしている。
＜３＞必要十分条件（数１１）を満たしていることの証明
シンドロームＳとして、下記数１９の関係が成立したと仮定する。
【００８９】
【数１９】
2006101429.tif 000067
数１９の（ｅ１＋ｅ２＋・・・＋ｅｄ−１）・Ｈ’Ｔ＝０において、Ｈ’はランクがＭｉｎ（（ｄ−１）ｔ、ｂ）より、下記数２０が得られる。
【００９０】
【数２０】
2006101429.tif 000068
数２０において、右からＨ”Ｔをかけると、下記数２１が得られる。
【００９１】
【数２１】
2006101429.tif 000069
数１９、数２１において、ｅ１・Ｈ”Ｔ、ｅ２・Ｈ”Ｔ、・・・、ｅｄ−１・Ｈ”Ｔをそれぞれｘ１、ｘ２、・・・、ｘｄ−１
2006101429.tif 000070
より、ｘ１≠０、ｘ２≠０、・・・、ｘｄ−１≠０）と表すと、下記数２２が得られる。
【００９２】
【数２２】
2006101429.tif 000071
数２２を行列の形で表すと、下記数２３が得られる。
【００９３】
【数２３】
2006101429.tif 000072
数２３中の（ｄ−１）行（ｄ−１）列の行列は、ヴァンデルモンドの行列の形をしているため、正則行列である。よって、上記数２３の両辺に左から逆行列をかけると、下記数２４が得られる。
【００９４】
【数２４】
2006101429.tif 000073
数２４は、ｘ１＝０、ｘ２＝０、・・・、ｘｄ−１＝０となり、前提であるｘ１≠０、ｘ２≠０、・・・、ｘｄ−１≠０に矛盾する。よって、数１で表される符号は、必要十分条件（数１１）を満たしている。
【００９５】
したがって、前述した＜１＞〜＜３＞における証明結果より、上記数１に示すパリティ検査行列（Ｈ）は、距離ｄに対し、受信語（Ｖ’）３２に含まれる
2006101429.tif 000074
個以下のバイト内複数スポッティバイト誤りを訂正し、ｍ個以下のバイト内複数スポッティバイト誤りを検出する機能を有していることを証明することができた。
【００９６】
また、上記数５に示したパリティ検査行列（Ｈ）で表される伸長符号も、同様に上記数９、数１０、数１１に示した必要十分条件を満たすことを示すことにより、距離ｄに対し、
2006101429.tif 000075
を有していることを示すことができる。
【００９７】
ここでは、具体的な符号パラメータを与えて、上記数１に示すパリティ検査行列（Ｈ）を構成できることを示す。なお、このパリティ検査行列（Ｈ）は、あくまで一例であって、本発明がこれに限定されないことは言うまでもない。
【００９８】
いま、読み書きデータ幅として、８ビットを有するメモリ素子を使用したメモリシステムを対象に、ｄ＝５、ｔ＝２、ｂ＝８のパラメータを与え、バイト内２ビット以下の誤りをスポッティバイト誤りとして、２個のバイト内複数スポッティバイト誤りを訂正するＤ２／８ＥＣ符号のパリティ検査行列（Ｈ）を構成することとする。このとき、Ｍｉｎ（（ｄ−１）ｔ、ｂ）＝Ｍｉｎ（８、８）＝８より、行列Ｈ’として、ランク８を有する行列を構成すればよい。この一例として、下記数２５に示す８×８（８行８列を意味する）単位行列を構成すればよい。
【００９９】
【数２５】
2006101429.tif 000076
また、
2006101429.tif 000077
より、行列Ｈ”として、ランク４を有する４ビット誤り検出符号の検査行列を構成すればよい。この一例として、下記数２６に示す６×８行列を示す。
【０１００】
【数２６】
2006101429.tif 000078
次に、γをＧＦ（２）上の６次の原始多項式ｇ（ｘ）＝ｘ６＋ｘ＋１の根とすると、γは、６次の列ベクトルγ＝（０１００００）Ｔと表現することができる。
【０１０１】
つまり、γのべき表示γｉとベクトル表示との対応を示すと、次のようになる。
γ０＝（１０００００）Ｔ、 γ１＝（０１００００）Ｔ、 γ２＝（００１０００）Ｔ、
γ３＝（０００１００）Ｔ、 γ４＝（００００１０）Ｔ、 γ５＝（０００００１）Ｔ、
γ６＝（１１００００）Ｔ、 γ７＝（０１１０００）Ｔ、 γ８＝（００１１００）Ｔ、
γ９＝（０００１１０）Ｔ、 γ１０＝（００００１１）Ｔ、γ１１＝（１１０００１）Ｔ、
γ１２＝（１０１０００）Ｔ、γ１３＝（０１０１００）Ｔ、γ１４＝（００１０１０）Ｔ、
γ１５＝（０００１０１）Ｔ、γ１６＝（１１００１０）Ｔ、γ１７＝（０１１００１）Ｔ、
γ１８＝（１１１１００）Ｔ、γ１９＝（０１１１１０）Ｔ、γ２０＝（００１１１１）Ｔ、
γ２１＝（１１０１１１）Ｔ、γ２２＝（１０１０１１）Ｔ、γ２３＝（１００１０１）Ｔ、
γ２４＝（１０００１０）Ｔ、γ２５＝（０１０００１）Ｔ、γ２６＝（１１１０００）Ｔ、
γ２７＝（０１１１００）Ｔ、γ２８＝（００１１１０）Ｔ、γ２９＝（０００１１１）Ｔ、
γ３０＝（１１００１１）Ｔ、γ３１＝（１０１００１）Ｔ、γ３２＝（１００１００）Ｔ、
γ３３＝（０１００１０）Ｔ、γ３４＝（００１００１）Ｔ、γ３５＝（１１０１００）Ｔ、
γ３６＝（０１１０１０）Ｔ、γ３７＝（００１１０１）Ｔ、γ３８＝（１１０１１０）Ｔ、
γ３９＝（０１１０１１）Ｔ、γ４０＝（１１１１０１）Ｔ、γ４１＝（１０１１１０）Ｔ、
γ４２＝（０１０１１１）Ｔ、γ４３＝（１１１０１１）Ｔ、γ４４＝（１０１１０１）Ｔ、
γ４５＝（１００１１０）Ｔ、γ４６＝（０１００１１）Ｔ、γ４７＝（１１１００１）Ｔ、
γ４８＝（１０１１００）Ｔ、γ４９＝（０１０１１０）Ｔ、γ５０＝（００１０１１）Ｔ、
γ５１＝（１１０１０１）Ｔ、γ５２＝（１０１０１０）Ｔ、γ５３＝（０１０１０１）Ｔ、
γ５４＝（１１１０１０）Ｔ、γ５５＝（０１１１０１）Ｔ、γ５６＝（１１１１１０）Ｔ、
γ５７＝（０１１１１１）Ｔ、γ５８＝（１１１１１１）Ｔ、γ５９＝（１０１１１１）Ｔ、
γ６０＝（１００１１１）Ｔ、γ６１＝（１０００１１）Ｔ、γ６２＝（１００００１）Ｔ
これより、上記数２６に示す行列Ｈ”は、Ｈ”＝［γ０γ１γ２γ３γ４γ５γ１８γ２０］と表すことができる。よって、上記数１に示したパリティ検査行列（Ｈ）は、Ｈ’及びＨ”を用いて、具体的な（５０４、４７８）Ｄ２／８ＥＣ符号を構成することができる。この符号の最後から４１４列削除することによって得られた（９０、６４）Ｄ２／８ＥＣ符号の検査行列を図３に示す。
【０１０２】
なお、図３に示すように、パリティ検査行列（Ｈ）のＨ’及びＨ”に相当する行単位の箇所を明確化するため、その境界に実線を引いて示している。
【０１０３】
いま、パリティ検査行列（Ｈ）の構成要素であるγ３Ｈ”が、図３に示す実際のビット値と対応しているかを具体的に確認する。前述したように、Ｈ”＝［γ０γ１γ２γ３γ４γ５γ１８γ２０］より、γ３Ｈ”＝γ３［γ０γ１γ２γ３γ４γ５γ１８γ２０］＝［γ３γ４γ５γ６γ７γ８γ２１γ２３］となる。このべき表示をベクトル表示（例えば、γ０＝（１０００００）Ｔ等）に変換すれば、図３に示すａ部分に相当し、このａ部分は明らかにパリティ検査行列（Ｈ）のγ３Ｈ”部分である。同様にして、パリティ検査行列（Ｈ）における他の構成要素についても、ベクトル表示に変換すれば、全体として図３に示すビット表現の２６行９０列の構成となる。
【０１０４】
ここで、ｔ＝３に対しては、Ｍｉｎ（（ｄ−１）ｔ、ｂ）＝８より、行列Ｈ’として、上記数２５に示したランク８を有する８×８（８行８列を意味する）単位行列を構成すればよい。また、
2006101429.tif 000079
より、行列Ｈ”として、ランク６を有し、また、符号長８ビットを有する６ビット誤り検出符号の検査行列を構成すればよい。この一例として、下記数２７に示す７×８行列を構成することができる。
【０１０５】
【数２７】
2006101429.tif 000080
一方、ｔ＝４、５、６、７については、Ｈ’及びＨ”は８×８の単位行列に等しくなり、パリティ検査行列（Ｈ）は、ＲＳ符号のパリティ検査行列と一致する。
【０１０６】
なお、以上は最近最も使用されている、バイト幅ｂ＝８ビット入出力を有する半導体メモリ素子を対象として、パリティ検査行列Ｈ（符号）の一例を構成して説明したが、他にも多く使用されている多ビット入出力素子、例えば、ｂ＝１６ビット入出力を有する素子等に対しても、また２以上の任意の整数値を有するｂに対して、Ｄｔ／ｂＥＣ符号を構成できることは明らかである。
【０１０７】
また、以上は距離ｄ＝５として、パリティ検査行列Ｈの一例を構成して説明したが、任意の距離ｄに対して、符号すなわちパリティ検査行列が構成できることも明らかである。
【０１０８】
このように、前記では、バイト内複数スポッティバイト誤り制御符号のパリティ検査行列（Ｈ）の構成法の一例を示したが、このパリティ検査行列（Ｈ）中のＨ’及びＨ”のランクを変化させることにより、大きさの異なる２種のバイト内複数スポッティバイト誤りを制御する符号を構成することができる。
【０１０９】
ここで、大きさの異なる２種のスポッティバイト誤り（ｔ／ｂ誤り及びｔ’／ｂ誤り、１≦ｔ、ｔ’≦ｂ）を考慮した４種のバイト内複数スポッティバイト誤り制御符号について説明する。
【０１１０】
具体的には、この４種のバイト内複数スポッティバイト誤り制御符号は、次のようになっている。
＜Ｉ＞Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号
つまり、１個のｔ／ｂ誤りを訂正し、且つ、（ｔ／ｂ＋ｔ’／ｂ）誤り（ｔ／ｂ誤りとｔ’／ｂ誤りの複合誤り）を検出する符号である。
＜II＞Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号
つまり、１個のｔ／ｂ誤りを訂正し、且つ、２個のｔ’／ｂ誤りを検出する符号である。
＜III＞（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号
つまり、（ｔ／ｂ＋ｔ’／ｂ）誤りを訂正する符号である。
＜IV＞Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号
つまり、２個のｔ／ｂ誤りを訂正し、且つ、１個のｔ’／ｂ誤り（ｔ＜ｔ’）を訂正する符号である。
ここで、大きさの異なる２種のスポッティバイト誤り（ｔ／ｂ誤り及びｔ’／ｂ誤り、１≦ｔ、ｔ’≦ｂ）を考慮した上記４種のバイト内複数スポッティバイト誤り制御符号を以下のように詳細に述べる。
＜Ｉ＞Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号
Ｓｔ／ｂＥＣ−（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数２８に示すような構成としている。
【０１１１】
【数２８】
2006101429.tif 000081
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１である。
【０１１２】
上記数２８を構成する行列Ｈ’は、下記数２９に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋ｔ’、ｂ）を満足する。
【０１１３】
【数２９】
2006101429.tif 000082
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが２ｔ＋ｔ’＜ｂのとき、行列Ｈ’は最小ハミング距離２ｔ＋ｔ’＋１を有する符号の検査行列、すなわち、２ｔ＋ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１１４】
また、上記数２８を構成する行列Ｈ”は、下記数３０に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足する。
【０１１５】
【数３０】
2006101429.tif 000083
ここで、行列Ｈ”のランクがｔ＞ｔ’のとき、行列Ｈ”は最小ハミング距離ｔ＋１を有する符号の検査行列、すなわち、ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。また、行列Ｈ”のランクがｔ＜ｔ’のとき、行列Ｈ”は最小ハミング距離ｔ’＋１を有する符号の検査行列、すなわち、ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１１６】
次に、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γを２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元とするときに、γｉＨ”は下記数３１で定義することができる。
【０１１７】
【数３１】
2006101429.tif 000084
ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である。
【０１１８】
次に、上記数２８に示したパリティ検査行列（Ｈ）で表される符号が、１個のｔ／ｂ誤りを訂正し、且つ、（ｔ／ｂ＋ｔ’／ｂ）誤り（つまり、ｔ／ｂ誤りとｔ’／ｂ誤りの複合誤り）を検出する機能を有していることを具体的に示す。パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、・・・、Ｈｎ−１］が以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【０１１９】
【数３２】
2006101429.tif 000085
【０１２０】
【数３３】
2006101429.tif 000086
【０１２１】
【数３４】
2006101429.tif 000087
【０１２２】
【数３５】
2006101429.tif 000088
ここで、Ｅｔ／ｂを１バイト中のｔビットまでの誤りの集合とし、Ｅｔ’／ｂを１バイト中のｔ’ビットまでの誤りの集合とする。また、ｉ、ｊ、ｋ（０≦ｉ、ｊ、ｋ≦ｎ−１）は、すべて異なるものとする。
【０１２３】
上記数９、数１０、数１１に示した必要十分条件と同様に、数３２から数３５までに示した条件を満たしていることを示すことができる。
＜II＞Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号
Ｓｔ／ｂＥＣ−Ｄｔ’／ｂＥＤ符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数３６に示すような構成としている。
【０１２４】
【数３６】
2006101429.tif 000089
ただし、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、Ｎ＝ｂ（ｎ＋１）＋Ｒ−ｑ、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／２−１である。
【０１２５】
上記数３６を構成する行列Ｈ’は、下記数３７に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔまたはｔ＋２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ＋２ｔ’）、ｂ）を満足する。
【０１２６】
【数３７】
2006101429.tif 000090
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが２ｔのとき、行列Ｈ’は最小ハミング距離２ｔ＋１を有する符号の検査行列、すなわち、２ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。また、行列Ｈ’のランクがｔ＋２ｔ’のとき、行列Ｈ’は最小ハミング距離ｔ＋２ｔ’＋１を有する符号の検査行列、すなわち、ｔ＋２ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１２７】
また、上記数３６を構成する行列Ｈ”は、下記数３８に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔまたはｔ’のうちいずれか大きい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足する。
【０１２８】
【数３８】
2006101429.tif 000091
ここで、行列Ｈ”のランクがｔ＞ｔ’のとき、行列Ｈ”は最小ハミング距離ｔ＋１を有する符号の検査行列、すなわち、ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。また、行列Ｈ”のランクがｔ＜ｔ’のとき、行列Ｈ”は最小ハミング距離ｔ’＋１を有する符号の検査行列、すなわち、ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１２９】
次に、Ｒ≧ｑ＋２ｒ、かつ（Ｒ−ｑ）は２の倍数であり、γを２を底とする（Ｒ−ｑ）／２次の拡大体ＧＦ（２（Ｒ−ｑ）／２）の原始元とするときに、γｉＨ”は下記数３９で定義することができる。
【０１３０】
【数３９】
2006101429.tif 000092
ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／２）への準同型写像（homomorphism）である。
【０１３１】
次に、上記数３６に示したパリティ検査行列（Ｈ）で表される符号が、１個のｔ／ｂ誤りを訂正し、且つ、２個のｔ’／ｂ誤りを検出する機能を有していることを具体的に示す。パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、・・・、Ｈｎ−１］が以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【０１３２】
【数４０】
2006101429.tif 000093
【０１３３】
【数４１】
2006101429.tif 000094
【０１３４】
【数４２】
2006101429.tif 000095
【０１３５】
【数４３】
2006101429.tif 000096
【０１３６】
【数４４】
2006101429.tif 000097
【０１３７】
【数４５】
2006101429.tif 000098
ここで、Ｅｔ／ｂを１バイト中のｔビットまでの誤りの集合とし、Ｅｔ’／ｂを１バイト中のｔ’ビットまでの誤りの集合とする。また、ｉ、ｊ、ｋ（０≦ｉ、ｊ、ｋ≦ｎ−１）は、すべて異なるものとする。
【０１３８】
上記数９、数１０、数１１に示した必要十分条件と同様に、数４０から数４５までに示した条件を満たしていることを示すことができる。
＜III＞（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号
（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＣ符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数４６に示すような構成としている。ここで、一般性を失うことなく、ｔ＞ｔ’とする。
【０１３９】
【数４６】
2006101429.tif 000099
ただし、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１である。
【０１４０】
上記数４６を構成する行列Ｈ’は、下記数４７に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、２ｔ＋２ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋２ｔ’、ｂ）を満足する。
【０１４１】
【数４７】
2006101429.tif 000100
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが２ｔ＋２ｔ’＜ｂのとき、行列Ｈ’は最小ハミング距離２ｔ＋２ｔ’＋１を有する符号の検査行列、すなわち、２ｔ＋２ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１４２】
また、上記数４６を構成する行列Ｈ”は、下記数４８に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、ｔ＋ｔ’またはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（ｔ＋ｔ’、ｂ）を満足する。
【０１４３】
【数４８】
2006101429.tif 000101
ここで、行列Ｈ”のランクがｂに等しいとき、行列Ｈ”はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ”のランクがｔ＋ｔ’＜ｂのとき、行列Ｈ”は最小ハミング距離ｔ＋ｔ’＋１を有する符号の検査行列、すなわち、ｔ＋ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１４４】
次に、Ｒ≧ｑ＋３ｒ、且つ、（Ｒ−ｑ）は３の倍数であり、γを２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元とするときに、γｉＨ”は下記数４９で定義することができる。
【０１４５】
【数４９】
2006101429.tif 000102
ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／３）への準同型写像（homomorphism）である。
【０１４６】
次に、上記数４６に示したパリティ検査行列（Ｈ）で表される符号が、（ｔ／ｂ＋ｔ’／ｂ）誤りを訂正する機能を有していることを具体的に示す。パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、・・・、Ｈｎ−１］が、以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【０１４７】
【数５０】
2006101429.tif 000103
【０１４８】
【数５１】
2006101429.tif 000104
【０１４９】
【数５２】
2006101429.tif 000105
【０１５０】
【数５３】
2006101429.tif 000106
【０１５１】
【数５４】
2006101429.tif 000107
【０１５２】
【数５５】
2006101429.tif 000108
【０１５３】
【数５６】
2006101429.tif 000109
【０１５４】
【数５７】
2006101429.tif 000110
【０１５５】
【数５８】
2006101429.tif 000111
ここで、Ｅｔ／ｂを１バイト中のｔビットまでの誤りの集合とし、Ｅｔ’／ｂを１バイト中のｔ’ビットまでの誤りの集合とする。また、
2006101429.tif 000112
はすべて異なるものとする。
【０１５６】
上記数９、数１０、数１１に示した必要十分条件と同様に、数５０から数５８までに示した条件を満たしていることを示すことができる。
＜IV＞Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号
Ｄｔ／ｂＥＣ−Ｓｔ’／ｂＥＣ符号に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記数５９に示すような構成としている。ここで、Ｄｔ／ｂＥＣ符号は、１バイト内に生じた２ｔビットまでの誤りを訂正する機能を有するため、ｔ’＞２ｔとする。
【０１５７】
【数５９】
2006101429.tif 000113
ただし、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、Ｎ＝ｂ（ｎ＋１）＋（Ｒ−ｑ）／３、０≦ｉ≦ｎ−１、ｎ＝２（Ｒ−ｑ）／３−１である。
【０１５８】
上記数５９を構成する行列Ｈ’は、下記数６０に示すｑ次の列ベクトルｈｊ’（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、４ｔまたは２ｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ’）≧Ｍｉｎ（Ｍａｘ（４ｔ、２ｔ’）、ｂ）を満足する。
【０１５９】
【数６０】
2006101429.tif 000114
ここで、行列Ｈ’のランクがｂに等しいとき、行列Ｈ’はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ’のランクが４ｔのとき、行列Ｈ’は最小ハミング距離４ｔ＋１を有する符号の検査行列、すなわち、４ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。また、行列Ｈ’のランクが２ｔ’のとき、行列Ｈ’は最小ハミング距離２ｔ’＋１を有する符号の検査行列、すなわち、２ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１６０】
また、上記数５９を構成する行列Ｈ”は、下記数６１に示すｒ次の列ベクトルｈｊ”（０≦ｊ≦ｂ−１）から構成されるｒ行ｂ列（ｒ≦ｂ）の２元行列であり、２ｔまたはｔ’のうちいずれか大きい値、及びｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ”）≧Ｍｉｎ（Ｍａｘ（２ｔ、ｔ’）、ｂ）を満足する。
【０１６１】
【数６１】
2006101429.tif 000115
ここで、行列Ｈ”のランクがｂに等しいとき、行列Ｈ”はランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、行列Ｈ”のランクが２ｔのとき、行列Ｈ”は最小ハミング距離２ｔ＋１を有する符号の検査行列、すなわち、２ｔビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。また、行列Ｈ”のランクがｔ’のとき、行列Ｈ”は最小ハミング距離ｔ’＋１を有する符号の検査行列、すなわち、ｔ’ビット誤り検出機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列に等しい。
【０１６２】
次に、Ｒ≧ｑ＋３ｒ、かつ（Ｒ−ｑ）は３の倍数であり、γを２を底とする（Ｒ−ｑ）／３次の拡大体ＧＦ（２（Ｒ−ｑ）／３）の原始元とするときに、γｉＨ”は下記数６２で定義することができる。
【０１６３】
【数６２】
2006101429.tif 000116
ここで、Φは加法のもとでＧＦ（２ｑ）からＧＦ（２（Ｒ−ｑ）／３）への準同型写像（homomorphism）である。
【０１６４】
次に、上記数５９に示したパリティ検査行列（Ｈ）で表される符号が、２個のｔ／ｂ誤りを訂正し、かつ１個のｔ’／ｂ誤り（ｔ＜ｔ’）を訂正する機能を有していることを具体的に示す。パリティ検査行列Ｈ＝［Ｈ０、Ｈ１、・・・、Ｈｎ−１］が、以下に示す必要十分条件を満たしていることを示せばよい。ただし、ＨｉはＲ×ｂの小行列である。
【０１６５】
【数６３】
2006101429.tif 000117
【０１６６】
【数６４】
2006101429.tif 000118
【０１６７】
【数６５】
2006101429.tif 000119
【０１６８】
【数６６】
2006101429.tif 000120
【０１６９】
【数６７】
2006101429.tif 000121
ここで、Ｅｔ／ｂを１バイト中のｔビットまでの誤りの集合とし、Ｅｔ’／ｂを１バイト中のｔ’ビットまでの誤りの集合とする。また、
2006101429.tif 000122
はすべて異なるものとする。
【０１７０】
上記数９、数１０、数１１に示した必要十分条件と同様に、数６３から数６７までに示した条件を満たしていることを示すことができる。
【０１７１】
このように、上記では、バイト内複数スポッティバイト誤り制御符号のパリティ検査行列（Ｈ）の構成法の幾つかの例を示したが、次に、このパリティ検査行列（Ｈ）を用いて、処理する符号化と復号の具体的な方法とそれぞれの回路構成について、数１に示したバイト内複数スポッティバイト誤り制御符号を例に取って説明する。
＜Ａ＞符号化の方法及びこれを実現する回路の構成について
まず、図１に示す符号化回路２が行う符号化方法について説明する。
【０１７２】
符号化回路２は、入力情報データＤ（行ベクトル）３０と、図３に示すパリティ検査行列（Ｈ）を基本行変形して得られるパリティ検査行列（Ｈ）の情報部ＨＲを用いて、検査情報Ｃ（行ベクトル）を生成する。この検査情報（Ｃ）の生成は、下記数６８により求めることができる。
【０１７３】
【数６８】
2006101429.tif 000123
具体的には、符号化回路２は、入力情報データ（Ｄ）３０の情報ビット長６４ビット及び検査ビット長２６ビットを基に、パリティ検査行列Ｈである（５０４、４７８）Ｄ２／８ＥＣ符号を構成した後に、後半４１４ビットに相当する列ベクトル４１４列を削除することにより、符号ビット長９０ビット、情報長６４ビットを有する図３に示す（９０、６４）Ｄ２／８ＥＣ符号が構成することができる。この符号のパリティ検査行列Ｈを基本行変形すると、組織符号としてのパリティ検査行列Ｈを構成することができる。図４は、（９０、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列を示している。
【０１７４】
図４に示す（９０、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列において、ｄ０〜ｄ６３が情報ビットに相当し、ｃ０〜ｃ２５が検査ビットに相当する。ここで、図４に示す（９０、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列において、情報ビットに相当するｄ０〜ｄ６３の列ベクトルを集めた行列が、パリティ検査行列の情報部ＨＲとなる。
【０１７５】
ここで、符号化では図４に示すパリティ検査行列を使用し、復号では図３に示すパリティ検査行列を使用する。基本行変形して得られた行列は、もとの行列と等価であり、図４に示すパリティ検査行列で表される符号は、図３に示すパリティ検査行列で表される符号と、その性質は全く変化しない。これより、符号化においては、図４に示すパリティ検査行列を使用することとする。
【０１７６】
次に、符号化回路２は、上記数６８を基に、２６ビットの検査情報（Ｃ）を生成する。上記数６８に示すＣ＝Ｄ・ＨＲＴから明らかなように、例えば、検査情報（Ｃ）における検査ビットｃ０を生成するには、図４に示す符号化用（９０、６４）Ｄ２／８ＥＣ符号の行列の１行目において、ｃ０に対応するビットを除いて“１”が存在する箇所に対応するビットのＧＦ（２）上の和（すなわち、２を法とする和：ｍｏｄ２）をとる演算を行えばよい。
【０１７７】
例えば、検査ビットｃ０を求める場合に、ｃ０に対応するビットを除いて“１”が存在しているのは、ｄ１、ｄ４、ｄ５、ｄ６、ｄ８、ｄ１１、ｄ１２、ｄ２０、ｄ２１、ｄ２４、ｄ２６、ｄ３１、ｄ３３、ｄ３７、ｄ３８、ｄ３９、ｄ４０、ｄ４１、ｄ４２、ｄ４３、ｄ４４、ｄ４７、ｄ４８、ｄ５２、ｄ５４、ｄ５５、ｄ５６、ｄ５７、ｄ５８であり、これら２９個のビットについて、２を法とする和（ｍｏｄ２）をとればよい。
【０１７８】
これを実現するには、図５に示すように、前記２９ビットを多入力パリティチェック回路２０（０）を構成すればよく、この多入力パリティチェック回路２０（０）の出力が検査ビットｃ０となる。他の検査ビットｃ１〜ｃ２５についても、検査ビットｃ０と同様にして生成することができる。２６ビットの検査ビットｃ０〜ｃ２５を並列に生成する符号化回路２（多入力パリティチェック回路２０（０）〜２０（２５）からなる）の上位１４ビットの構成を図５に、下位１２ビットの構成を図６にそれぞれ示す。
【０１７９】
次に、符号化回路２によって生成した検査情報（Ｃ）を、入力情報データ（Ｄ）３０に付加した符号語を下記数６９に示す。これが回路３に送られる送信語（Ｖ）（９０ビットのベクトル）となる。
【０１８０】
【数６９】
2006101429.tif 000124
＜Ｂ＞復号の方法及びこれを実現する回路の構成について
次に、送信語（Ｖ）３１に誤りが生じたとき（すなわち受信語３２に誤りが含まれているとき）に、その誤りに対する訂正・検出処理が、図３に示す（９０、６４）Ｄ２／８ＥＣ符号を用いて生成されるシンドローム（Ｓ）３３の値に基づいて可能なことを示す。
【０１８１】
図３に示す（９０、６４）Ｄ２／８ＥＣ符号の検査行列は、距離ｄ＝５を有することから、上記数１に示すように、パリティ検査行列Ｈ’による４段構成を有する。これより、１段目より得られるｑ＝８ビットのシンドロームをＳI、２段目より得られるｒ＝６ビットのシンドロームをＳII、３段目より得られるｒ＝６ビットのシンドロームをＳIII、４段目より得られるｒ＝６ビットのシンドロームをＳIVとする。
【０１８２】
これらの情報を用いて、次のように誤りの訂正・検出を行う。受信語（Ｖ’）３２とパリティ検査行列（Ｈ）とから、シンドローム（Ｓ）３３は、下記数７０により求めることができる。
【０１８３】
【数７０】
2006101429.tif 000125
ここで、ＳI∈ＧＦ（２ｑ）は、ｑ次の行ベクトルである。また、ＳII、ＳIII、ＳIV∈ＧＦ（２ｒ）は、それぞれｒ次の行ベクトルである。
【０１８４】
上記数５に示す伸長符号の場合に、ＳI∈ＧＦ（２ｑ）は、ｑ次の行ベクトルである。また、ＳII、ＳIII、ＳIV∈ＧＦ（２（Ｒ−ｑ）／３）は、それぞれ（Ｒ−ｑ）／３次の行ベクトルである。
【０１８５】
なお、シンドローム（Ｓ）３３は、例えば、ｉI番目のバイトにｅIの誤り、ｉII番目のバイトにｅIIの誤りが生じているときに、下記数７１となる。
【０１８６】
【数７１】
2006101429.tif 000126
ＳIに注目すると、下記数７２が成り立つ。数７２において、Ｈ’はランクＭｉｎ（（ｄ−１）ｔ、ｂ）を有しているため、ｅI＋ｅII（＝ｅＡとする）を求めることができる。図３に示す（９０、６４）Ｄ２／８ＥＣ符号の場合に、Ｈ’は単位行列であるため、ｅＡ＝ｅI＋ｅII＝ＳIとなる。
【０１８７】
【数７２】
2006101429.tif 000127
次に、ｅI＋ｅIIにＨ”Ｔを右から乗算し、乗算した結果をＳ’I∈ＧＦ（２ｒ）とする。つまり、下記数７３の関係が成立する。
【０１８８】
【数７３】
2006101429.tif 000128
ここで、ｅI・Ｈ”Ｔ、ｅII・Ｈ”Ｔ（∈ＧＦ（２ｒ））をＧＦ（２ｒ）上の誤りｅ’I、ｅ’IIとし、Ｓ’＝［Ｓ’IＳIIＳIIIＳIV］とすると、下記数７４の関係が成り立つ。
【０１８９】
【数７４】
2006101429.tif 000129
数７４に示すＳ’は、誤りｅ’I、ｅ’IIを有する距離ｄ＝５のＲＳ符号におけるシンドロームの式と一致する。よって、距離ｄ＝５を有するＧＦ（２ｒ）上のＲＳ符号の復号法を用いることで、誤り位置ｉI、ｉII及びＧＦ（２ｒ）上の誤りｅ’I、ｅ’IIを求めることができる。また、誤り位置が求まらない場合に、誤りの訂正が不可能として誤りを検出する。
【０１９０】
次に、ＧＦ（２ｒ）上の誤りｅ’I、ｅ’IIから、ＧＦ（２ｂ）上の誤りｅI、ｅIIを求める。前記ＲＳ符号の復号により得られたＧＦ（２ｒ）上の誤りｅ’において、誤りｅ’I、ｅ’IIが、２バイトに生じている場合と１バイトに生じている場合で場合分けする。
【０１９１】
ｅ’I、ｅ’IIが２バイトに生じている場合に、各バイトに１個ずつのスポッティバイト誤りが生じている。このとき、ｅI・Ｈ”Ｔ＝ｅ’I、ｅII・Ｈ”Ｔ＝ｅ’IIにおいて、Ｈ”は、ランクがＭｉｎ（２ｔ、ｂ）＝（４、８）＝４より、ｅI→ｅ’I、ｅII→ｅ’IIは単射の関係となっているため、ＧＦ（２ｂ）上の誤りｅI、ｅIIを求めることができる。
【０１９２】
また、ｅ’I、ｅ’IIが１バイトに生じている場合に、１バイトに１または２個のスポッティバイト誤りが生じている。このとき、上記数７３から求めたｅＡ＝ｅI＋ｅIIが誤りとなるため、誤りも求めることができる。
【０１９３】
なお、一般的な距離ｄ、つまり、任意所定の距離ｄに対しても、前記距離ｄ＝５の場合と同様に、前記ＲＳ符号の復号により得られたＧＦ（２ｒ）上の誤りｅ’において、誤りが生じているバイト数による場合分けを行うことにより、ＧＦ（２ｂ）上の誤りを求めることができる。
【０１９４】
ＲＳ符号に対する復号は、距離ｄが小さい符号に対しては、並列復号法を用いて実現することができる。この並列復号法の一般的構成は、「バースト誤り生成方法及びバーストおよびバイト誤り検出・訂正装置」（特許文献４参照）に開示されている。
【０１９５】
しかしながら、特許文献４に開示された並列復号法は、高速な復号が可能であるが、符号の距離ｄが大きくなると、回路量が大きくなるという問題が生じる。距離ｄが大きい符号に対しては、例えば、バーレカンプ・マッシィ法などの逐次復号法を用いることができるが、逐次復号法による復号は、逐次（シリアル）に行われるため、復号が遅いといった問題が生じる。なお、バーレカンプ・マッシィ法を用いたＲＳ符号の復号回路の構成は、非特許文献１１に開示されている。
【０１９６】
特許文献４に開示された並列復号法によれば、例えば、ｄ＝５の符号に対しては、次のような手順により復号する。
【０１９７】
まず、ＲＳ符号のパリティ検査行列
2006101429.tif 000130
に対し、Ｒ×２ｒの行列
2006101429.tif 000131
を構成する。ただし、
2006101429.tif 000132
はＲ×ｒの小行列である。
【０１９８】
次に、この行列
2006101429.tif 000133
にＲ×（Ｒ−２ｒ）の行列Ｂ（ｉ，ｊ）を付加し、Ｒ×Ｒの正則行列
2006101429.tif 000134
を構成する。
【０１９９】
そして、Ａ（ｉ，ｊ）の逆行列
2006101429.tif 000135
を求めると、下記数７５の関係が成り立つ。
【０２００】
【数７５】
2006101429.tif 000136
ここで、
2006101429.tif 000137
はｒ×Ｒの行列であり、
2006101429.tif 000138
となる。ただし、
2006101429.tif 000139
はｒ×ｒの単位行列である。また、
2006101429.tif 000140
はｒ×Ｒの行列であり、
2006101429.tif 000141
となる。また、
2006101429.tif 000142
は２ｒ×Ｒの行列であり、
2006101429.tif 000143
となる。ただし、
2006101429.tif 000144
は２ｒ×２ｒの単位行列である。また、
2006101429.tif 000145
は２ｒ×Ｒの行列であり、
2006101429.tif 000146
となる。
【０２０１】
前記
2006101429.tif 000147
に対し、
2006101429.tif 000148
となるバイト位置ｉ，ｊが誤りの位置ｉI、ｉIIとなり、
2006101429.tif 000149
が誤りの大きさｅ’I、ｅ’IIとなる。これから、２バイトの誤りを訂正することができる。また、
2006101429.tif 000150
となるバイト位置ｉ，ｊが存在しない場合に、誤りの訂正が不可能として誤りを検出する。
【０２０２】
次に、本発明において、前述したｄ＝５の符号に対する並列復号方法を実現する復号回路４の概略構成を図７に示す。
【０２０３】
図１に示したように、復号回路４は、シンドローム生成回路１と誤り訂正回路５とから構成されている。
【０２０４】
また、図７に示すように、誤り訂正回路５は、Ｈ’復号回路６と、Ｈ”乗算回路７と、ＧＦ（２ｒ）上の並列復号回路８と、ＧＦ（２ｂ）上の誤り生成回路９と、反転回路１０とから構成されている。
【０２０５】
ここで、Ｈ’復号回路６は、シンドローム（Ｓ）３３の上位ｑビットＳI３６を基にして、バイトごとの誤りの和（ｅＡ）３８を生成する。
【０２０６】
また、Ｈ”乗算回路７は、バイトごとの誤りの和（ｅＡ）３８を基にして、シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９を生成する。
【０２０７】
次に、ＧＦ（２ｒ）上の並列復号回路８は、シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９、及びシンドローム（Ｓ）３３の下位３ｒビットＳIIＳIIIＳIV３７を基にして、ＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）４０、及びＧＦ（２ｒ）上の並列復号において誤り訂正が不可能とみなされたときに出力されるＤＳ（０）（Detection  Signal）４１を生成する。
【０２０８】
そして、ＧＦ（２ｂ）上の誤り生成回路９は、バイトごとの誤りの和（ｅＡ）３８、及びＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）４０を基にして、ＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換して、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）４２、及び誤り訂正が不可能とみなされたときに出力されるＤＳ（１）（Detection  Signal）４３を出力する。
【０２０９】
最後に、反転回路１０は、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）４２を基にして、誤りビットに該当する受信語（Ｖ’）３２のビット値を反転させることにより、受信語（Ｖ’）３２の誤りを訂正する。
【０２１０】
次に、図７に示される復号回路４で行われる動作手順の概略を説明する。
【０２１１】
まず、シンドローム生成回路１では、Ｎビットからなる受信語（Ｖ’）３２が入力されると、Ｒビットのシンドローム（Ｓ）３３を生成する。
【０２１２】
次に、生成されたＲビットのシンドローム（Ｓ）３３は、上位ｑビットＳI３６と、下位３ｒビットＳIIＳIIIＳIV３７とに分けられる。シンドローム（Ｓ）３３の上位ｑビットＳI３６は、Ｈ’復号回路６に入力される。また、シンドローム（Ｓ）３３の下位３ｒビットＳIIＳIIIＳIV３７は、ＧＦ（２ｒ）上の並列復号回路８に入力される。
【０２１３】
そして、Ｈ’復号回路６では、詳細は後述するが、シンドローム生成回路１で生成されたシンドローム（Ｓ）３３の上位ｑビットＳI３６を基にして、ｂビットのバイトごとの誤りの和（ｅＡ）３８を出力する。
【０２１４】
そして、Ｈ”乗算回路７では、詳細は後述するが、Ｈ’復号回路６で生成されたバイトごとの誤りの和（ｅＡ）３８を基にして、シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９を出力する。
【０２１５】
また、ＧＦ（２ｒ）上の並列復号回路８では、詳細は後述するが、Ｈ”乗算回路７で生成されたシンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９、及びシンドローム生成回路１で生成されたシンドローム（Ｓ）３３の下位３ｒビットＳIIＳIIIＳIV３７を基にして、ＧＦ（２ｒ）上の誤りを指摘する
2006101429.tif 000151
ビットのＧＦ（２ｒ）上のビット誤りポインタ
2006101429.tif 000152
を生成する。ここで、
2006101429.tif 000153
はｙを超える最小の整数を示す。また、ＧＦ（２ｒ）上の並列復号回路８では、ＧＦ（２ｒ）上の並列復号において、誤り訂正が不可能とみなされたときに、訂正不可能誤り検出信号（ＤＳ（０））４１を出力する。
【０２１６】
そして、ＧＦ（２ｂ）上の誤り生成回路９では、詳細は後述するが、Ｈ’復号回路６で生成されたバイトごとの誤りの和（ｅＡ）３８、及びＧＦ（２ｒ）上の並列復号回路８で生成されたＧＦ（２ｒ）上のビット誤りポインタ（ｅ’）４０を基にして、ＧＦ（２ｂ）上の誤りを指摘するＮビットのＧＦ（２ｂ）上のビット誤りポインタｅ＝（ｅ０、ｅ１、・・・、ｅＮ−１）４２を生成する。また、ＧＦ（２ｂ）上の誤り生成回路９では、誤り訂正が不可能とみなされたときに、訂正不可能誤り検出信号（ＤＳ（１））４３を出力する。
【０２１７】
次に、反転回路１０では、ＧＦ（２ｂ）上の誤り生成回路９で生成されたＮビットのＧＦ（２ｂ）上のビット誤りポインタ（ｅ）４２、及び受信語（Ｖ’）３２を基にして、ＧＦ（２ｂ）上のビット誤りポインタ（ｅ）４２に対応した受信語（Ｖ’）３２のビットを反転する。
【０２１８】
最後に、反転回路１０では、Ｎビットの誤り訂正された受信語Ｖ＊から、Ｋビットの情報語Ｄ＊を取り出し、出力情報データ３４として出力する。
【０２１９】
また、ＧＦ（２ｒ）上の並列復号回路８で生成された訂正不可能誤り検出信号（ＤＳ（０））４１と、ＧＦ（２ｂ）上の誤り生成回路９で生成された訂正不可能誤り検出信号（ＤＳ（１））４３の論理和をとることにより、訂正不可能誤り検出信号ＵＣＥ（Uncorrectable  Error）３５の値を出力する。例えば、この訂正不可能誤り検出信号ＵＣＥ３５の値が“１”であれば、訂正能力を超えた誤りを検出したことを示している。
【０２２０】
なお、数５に示す伸長符号、及び数２８、数３６、数４６、数５９に示す大きさの異なる２種類のバイト内複数スポッティバイト誤りを制御する符号でも、それらの復号方法及び回路構成は、上述したことと基本的に同一である。
【０２２１】
次に、シンドローム生成回路１、Ｈ’復号回路６、Ｈ”乗算回路７、ＧＦ（２ｒ）上の並列復号回路８、ＧＦ（２ｂ）上の誤り生成回路９、及び反転回路１０のそれぞれの具体的な構成例を、図３に示す（９０、６４）Ｄ２／８ＥＣ符号を用いて説明する。
＜ａ＞シンドローム生成回路１の構成
ここでは、シンドローム生成回路１の構成について詳細に説明する。
【０２２２】
まず、シンドローム生成回路では、Ｎ＝９０（＝６４＋２６）ビットからなる受信語（Ｖ’）３２を、下記数７６に示すように表現したとき、この受信語（Ｖ’）３２を入力して、下記数７７に示すＳ０、Ｓ１、・・・、Ｓ２５からなるＲ＝２６ビットのシンドローム（Ｓ）３３を生成する。
【０２２３】
前述したように、図３に示すＤ２／８ＥＣ符号のパリティ検査行列が４段構成を有することから、これに対応してシンドローム（Ｓ）３３も４個の部分に区分けし、ＳI＝（Ｓ０Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７）、ＳII＝（Ｓ８Ｓ９Ｓ１０Ｓ１１Ｓ１２Ｓ１３）、ＳIII＝（Ｓ１４Ｓ１５Ｓ１６Ｓ１７Ｓ１８Ｓ１９）、ＳIV＝（Ｓ２０Ｓ２１Ｓ２２Ｓ２３Ｓ２４Ｓ２５）とする。
【０２２４】
【数７６】
2006101429.tif 000154
【０２２５】
【数７７】
2006101429.tif 000155
上記数６８に示したように、シンドロームＳ＝Ｖ’・ＨＴより、転置したパリティ検査行列（ＨＴ）の各行は、入力する情報に対応し、例えば、行列（ＨＴ）の第０行は、入力情報のｖ０’に対応している。そこで、シンドローム（Ｓ）３３の各ビットを生成するには、符号であるパリティ検査行列（ＨＴ）の各列方向に、“１”を有するビットに対応する受信語（Ｖ’）３２の受信情報をＧＦ（２）上で加算（ｍｏｄ２の計算）すればよい。
【０２２６】
図８及び図９は、図３に示した（９０、６４）Ｄ２／８ＥＣ符号のパリティ検査行列を基に構成したシンドローム生成回路１を示す図である。図８では、Ｓ０、Ｓ１、・・・、Ｓ１３といったシンドローム（Ｓ）３３の上位１４ビット、また、図９では、Ｓ１４、Ｓ１３、・・・、Ｓ２５といったシンドローム（Ｓ）３３の下位１２ビットをそれぞれ生成している。
【０２２７】
図８及び図９に示すように、本実施例では、シンドローム生成回路１において、まず、２６個の多入力パリティチェック回路２１（ｐ）、（ｐ＝０、１、・・・、２５）に、図３に示した（９０、６４）Ｄ２／８ＥＣ符号のパリティ検査行列の対応する各行のビット“１”を有する受信情報（ｖｑ’）、（ｑ＝０、１、・・・、８９）が入力する。
【０２２８】
次に、各多入力パリティチェック回路２１（ｐ）、（ｐ＝０、１、・・・、２５）において、前記入力された受信情報（ｖｑ’）に対して、２を法とする和（ｍｏｄ２）の計算を行い、その結果がＳｐである。
【０２２９】
具体的に、例えば、シンドローム（Ｓ）３３のビットＳ０を生成するには、９０ビットの受信語ｖ０’、ｖ１’、・・・、ｖ８９’のうち、図３に示すパリティ検査行列の第０行目において、“１”が存在する箇所に相当するｖ０’、ｖ８’、ｖ１６’、ｖ２４’、ｖ３２’、ｖ４０’、ｖ４８’、ｖ５６’、ｖ６４’、ｖ７２’、ｖ８０’、ｖ８８’の１２ビットについて、２を法とする和（ｍｏｄ２）をとればよい。図８の多入力パリティチェック回路２１（０）は、前記１２ビットの受信情報を入力として、値Ｓ０を出力するようになっている。シンドローム（Ｓ）３３の他のビットＳｐ、（ｐ＝１、・・・、２５）についても同様である。
＜ｂ＞Ｈ’復号回路６の構成
次に、Ｈ’復号回路６について説明する。
【０２３０】
Ｈ’復号回路６を図１０に示す。数７２に示した（ｅI＋ｅII）・Ｈ’Ｔ＝ＳIにおいて、Ｈ’はランクＭｉｎ（（ｄ−１）ｔ、ｂ）を有しているため、ｅI＋ｅII（＝ｅＡとする）を求めることができる。よって、ｅI＋ｅII→ＳIが単射の関係となっていることを利用し、論理合成を行うことにより、組み合わせ回路で実現することができる。
【０２３１】
図３に示す（９０、６４）Ｄ２／８ＥＣ符号の場合に、Ｈ’は単位行列であるため、ｅＡ＝ｅI＋ｅII＝ＳIとなる。すなわち、
2006101429.tif 000156
ＳI＝（Ｓ０Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７）に対し、図１０に示すように、
2006101429.tif 000157
となる。
【０２３２】
一方、Ｈ’が単位行列でない場合に、＜ｅ＞において後述する方法を用いる。
＜ｃ＞Ｈ”乗算回路７の構成
次に、Ｈ”乗算回路７について説明する。
【０２３３】
Ｈ”乗算回路７を図１１に示す。数７３に示したＳ’I＝（ｅI＋ｅII）・Ｈ”Ｔ＝ｅＡ・Ｈ”Ｔを計算する。下記数７８に示すＨ”の対応する各行のビット“１”を有するｅＡの情報がＨ”乗算回路７に入力される。そして、Ｈ”乗算回路７では、前記入力されたｅＡの情報に対し、ｍｏｄ２の計算を行い、その結果をＳ’ｐ（ｐ＝０、１、・・・、５）として出力する。
【０２３４】
【数７８】
2006101429.tif 000158
具体的に、例えば、シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９のビットＳ’０を生成するには、８ビットの
2006101429.tif 000159
のうち、数７８に示すパリティ検査行列Ｈ”の第０行目において、“１”が存在する箇所に相当する２ビット
2006101429.tif 000160
の値に対して、２を法とする和（ｍｏｄ２）をとればよい。
【０２３５】
図１１において、排他的論理和回路２２では、前記２ビットのｅＡの情報（つまり、２ビット
2006101429.tif 000161
の値）が入力されて、値Ｓ’０を出力していることを示している。
【０２３６】
シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９のほかのビットＳ’ｐについても、同様に、排他的論理和回路２２及び３入力パリティチェック回路２３を用いて、構成することができる。
【０２３７】
ここで、Ｓ’は下記数７９に示す構成とする。
【０２３８】
【数７９】
2006101429.tif 000162
＜ｄ＞ＧＦ（２６）上の並列復号回路８の構成
次に、ＧＦ（２６）上の並列復号回路８について説明する。
【０２３９】
ＧＦ（２６）上のビット誤りポインタ４０を求めるために、並列復号法を用いる。ＧＦ（２６）上の並列復号回路８の全体構成を図１２に示す。
【０２４０】
図１２に示されるように、ＧＦ（２６）上の並列復号回路８は、１２バイト中任意の２バイトの組
2006101429.tif 000163
個を選び、ｉ、ｊ番目の２バイト（以下、（ｉ、ｊ）と表現することとする）に関する各々の誤りを生成する回路である（ｉ、ｊ）に対する誤り生成回路５０（０）・・・５０（６５）、（以下、代表として５０（ｍ）、０≦ｍ≦６５、と称する）と、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を出力するＧＦ（２６）上の誤り算出回路５１とから構成されている。
【０２４１】
まず、（ｉ、ｊ）に対する誤り生成回路５０（ｍ）は、バイト位置ｉ、ｊに対して、上述した
2006101429.tif 000164
を計算する回路である。要するに、（ｉ、ｊ）に対する誤り生成回路５０（０）〜５０（６５）は、符号語の１２バイト中のｉ、ｊ（０≦ｉ＜ｊ≦１１）番目のバイトに対する前述した
2006101429.tif 000165
を計算し、Ｅ’ｍ、ｉ、Ｅ’ｍ、ｊになる誤り５２（ｍ）、０≦ｍ≦６５、０≦ｉ＜ｊ≦１１（それぞれｒビットのベクトル）、及び訂正可能信号５３（ｍ）、０≦ｍ≦６５、を出力する。
【０２４２】
また、ＧＦ（２６）上の誤り算出回路５１は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を出力する回路である。要するに、ＧＦ（２６）上の誤り算出回路５１は、誤り生成回路５０（ｍ）の出力である誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊを入力とし、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を出力する。
【０２４３】
ここで、ＧＦ（２６）上の並列復号回路８の処理をより詳しく説明すると、図１２に示すように、まず、Ｒ＝２４ビットのＳ’（シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９、及びシンドローム（Ｓ）３３の下位３ｒビットＳIIＳIIIＳIV３７）を（ｉ、ｊ）に対する誤り生成回路５０（ｍ）に入力する。
【０２４４】
次に、（ｉ、ｊ）に対する誤り生成回路５０（ｍ）は、誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊを生成し、そして、生成した誤りＥ’ｍ、ｉ、Ｅ’ｍ、ｊをＧＦ（２６）上の誤り算出回路５１に入力する。次に、ＧＦ（２６）上の誤り算出回路５１は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を出力する。
【０２４５】
また、Ｒ＝２４ビットのＳ’（シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）３９、及びシシンドローム（Ｓ）３３の下位３ｒビットＳIIＳIIIＳIV３７）を２４ビット入力ＯＲゲート回路５４に入力する。
【０２４６】
一方、（ｉ、ｊ）に対する誤り生成回路５０（ｍ）によって生成される訂正可能信号５３（ｍ）を、６６入力ＮＯＲゲート回路５５に入力する。
【０２４７】
２４ビット入力ＯＲゲート回路５４及び６６入力ＮＯＲゲート回路５５からそれぞれ出力された２本の信号を２入力ＡＮＤゲート回路５６に入力する。２入力ＡＮＤゲート回路５６は、訂正不可能誤り検出信号（ＤＳ（０））４１を出力する。これらの回路により、シンドロームが非零且つ訂正可能信号がすべて０の場合に、誤りを検出する。
【０２４８】
次に、（ｉ、ｊ）に対する誤り生成回路５０（ｍ）の構成例を具体的に示す。例として、（０、１）に対する誤り生成回路５０（０）を図１３に示す。図１３に示されるように、（ｉ、ｊ）に対する誤り生成回路５０（ｍ）は、
2006101429.tif 000166
計算回路６０と、
2006101429.tif 000167
計算回路６１と、
2006101429.tif 000168
計算回路６２とを備える。
【０２４９】
ここで、
2006101429.tif 000169
は下記数８０に示すＧＦ（２６）上のＲＳ符号の検査行列であり、符号長７２ビットと検査ビット長２４ビットとを有する。ただし、γはＧＦ（２６）の元であり、下記数８１に示すように、生成多項式ｇ（ｘ）＝ｘ６＋ｘ＋１で定義される２元の６×６随伴行列（companion  matrix）で表現される。
【０２５０】
【数８０】
2006101429.tif 000170
【０２５１】
【数８１】
2006101429.tif 000171
例えば、（０、１）に対する誤り生成回路５０（０）では、
2006101429.tif 000172
は、数８０の第１列、第２列に相当し、それぞれ下記数８２に示す２４×６行列となる。
【０２５２】
【数８２】
2006101429.tif 000173
次に、
2006101429.tif 000174
から２４×１２の行列
2006101429.tif 000175
を構成し、
2006101429.tif 000176
に２４×１２の行列Ｂ（０，１）を付加することにより、下記数８３に示す２４×２４の正則行列
2006101429.tif 000177
を構成する。ここで、Ｂ（０，１）はＡ（０，１）が正則行列となるように求めた２４×１２の行列であり、一例である。
【０２５３】
【数８３】
2006101429.tif 000178
次に、Ａ（０，１）の逆行列
2006101429.tif 000179
を求めると、下記数８４の関係が成り立つ。
2006101429.tif 000180
はそれぞれ下記数８５、数８６、数８７に示す行列となる。
【０２５４】
【数８４】
2006101429.tif 000181
【０２５５】
【数８５】
2006101429.tif 000182
【０２５６】
【数８６】
2006101429.tif 000183
【０２５７】
【数８７】
2006101429.tif 000184
2006101429.tif 000185
計算回路６０では、
2006101429.tif 000186
の各列が入力する情報に対応し、例えば、
2006101429.tif 000187
の第０行が入力情報のＳ’０に対応している。そこで、
2006101429.tif 000188
の各ビットを生成するには、
2006101429.tif 000189
の各行方向に、“１”を有するビットに対応するシンドロームＳ’の情報をＧＦ（２）上で加算（ｍｏｄ２の計算）すればよい。
【０２５８】
要するに、
2006101429.tif 000190
計算回路６０は、まず、前記
2006101429.tif 000191
の対応する各行のビット“１”を有するシンドローム情報（Ｓ’ｐ）、（ｐ＝０、１、・・・、２３）をそれぞれ６個の多入力パリティチェック回路６３（ｕ）、（ｕ＝０、１、・・・、５）に入力する。次に、これらのシンドローム情報についてｍｏｄ２の計算を行い、その結果をとしてＥ’０、０、Ｅ’０、１を出力する。
【０２５９】
具体的に、例えば、Ｅ’０、０の０ビット目を生成するには、２４ビットのシンドロームＳ’＝Ｓ’０、Ｓ’１、・・・、Ｓ’２３のうち、上記数８５に示すパリティ検査行列の第０行目において“１”が存在する箇所に相当する５ビットＳ’０、Ｓ’５、Ｓ’９、Ｓ’２１、Ｓ’２３の値について、２を法とする和（ｍｏｄ２）をとればよい。図１３の多入力パリティチェック回路６３（０）は、この５ビットＳ’０、Ｓ’５、Ｓ’９、Ｓ’２１、Ｓ’２３のシンドロームが入力される。また、多入力パリティチェック回路６３（０）は、５２（０）であるＥ’０、０の０ビット目を出力する。なお、Ｅ’０、０の他のビットについても同様である。
【０２６０】
また、図１３に示されるように、
2006101429.tif 000192
計算回路６１は、６個の多入力パリティチェック回路６４（ｗ）、（ｗ＝０、１、・・・、５）で構成され、そして、
2006101429.tif 000193
計算回路６２は、１２個の多入力パリティチェック回路６５（ｚ）、（ｚ＝０、１、・・・、１１）で構成される。これらの計算回路は、
2006101429.tif 000194
計算回路６０と同様の方法で構成することができる。
【０２６１】
ここで、（０、１）に対する誤り生成回路５０（０）の処理をより詳しく説明すると、図１３に示すように、２４ビットのシンドロームＳ’を多入力パリティチェック回路６３（ｕ）、（ｕ＝０、１、・・・、５）に入力することにより、Ｅ’０、０を生成する。また、２４ビットのシンドロームＳ’を多入力パリティチェック回路６４（ｗ）、（ｗ＝０、１、・・・、５）に入力することにより、Ｅ’０、１を生成する。
【０２６２】
また、２４ビットのシンドロームＳ’を多入力パリティチェック回路６５（ｚ）、（ｚ＝０、１、・・・、１１）に入力する。多入力パリティチェック回路６５（ｚ）、（ｚ＝０、１、・・・、１１）から出力される１２ビットの信号を１２入力ＮＯＲゲート回路６５に入力し、（０、１）に対する訂正可能信号５３（０）を出力する。これらの回路は、
2006101429.tif 000195
となるバイトの組（ｉ、ｊ）が誤りのバイトの組であるため、
2006101429.tif 000196
であることを検出し、バイトの組（ｉ、ｊ）で訂正可能であることを意味する。
【０２６３】
また、（０、１）に対する訂正可能信号５３（０）と多入力パリティチェック回路６３、多入力パリティチェック回路６４からの出力信号を２入力ＡＮＤゲート回路６７に入力し、Ｅ’０、０及びＥ’０、１を出力する。これらの回路は、誤りが生じているバイトの組である場合に、誤りを出力し、そうでない場合に、０のパターンを出力するようにしている。
【０２６４】
以上より、（０、１）に対する誤り生成回路５０（０）は、誤りＥ’０、０、Ｅ’０、１５２（０）、及び（０、１）に対する訂正可能信号５３（０）を最終的に出力する。ここでは、（０、１）に対する誤り生成回路５０（０）を例にして説明したが、他のバイト（ｉ、ｊ）に対しても同様である。
【０２６５】
次に、ＧＦ（２６）上の誤り算出回路５１の構成例を具体的に示す。ＧＦ（２６）上の誤り算出回路５１を図１４に示す。
【０２６６】
図１４に示されるように、ＧＦ（２６）上の誤り算出回路５１は、ｉ番目のバイトに対応するすべての誤りＥ’ｍ、ｉをビットごとＯＲ演算回路６８に入力し、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を最終的に出力する。これらの回路は、ｉ番目に対応するバイトの組（ｉ、ｊ）からの誤りＥ’ｍ、ｉを統合し、ｉ番目の誤りｅｉ’を出力するようにしている。
【０２６７】
具体的に、例えば、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０のｅ’６を出力するには、（０、１）に対する誤り生成回路５０（０）、（１、２）に対する誤り生成回路５０（１１）、・・・、及び（１、１１）に対する誤り生成回路５０（２０）から出力されるＥ’０、１、Ｅ’１１、１、・・・、Ｅ’２０、１の０ビット目をビットごとのＯＲ演算回路６８に入力することにより得られる。ビットごとのＯＲ演算回路６８では、６ビットを有するＥ’０、１、Ｅ’１１、１、・・・、Ｅ’２０、１の０ビット目をそれぞれ１１入力ＯＲ回路６９に入力することにより、Ｅ’０、１、Ｅ’１１、１、・・・、Ｅ’１９、１の０ビット目を統合し、ｅ６’を出力している。
【０２６８】
以上では、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０のｅ’６を例にして説明したが、他のビット値ｅ’０、・・・、ｅ’６５についても、まったく同様である。
＜ｅ＞ＧＦ（２８）上の誤り生成回路９の構成
次に、ＧＦ（２８）上の誤り生成回路９について説明する。ＧＦ（２８）上の誤り生成回路９の全体構成を図１５に示す。
【０２６９】
図１５に示すように、ＧＦ（２８）上の誤り生成回路９は、シンドロームが非零であることを検出する誤りバイト検出回路７０と、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０の１バイトからＧＦ（２８）上のビット誤りポインタ（ｅ）４２の１バイトを出力するｔビット誤り訂正復号回路７２と、入力信号の選択を行うビットごと選択回路７５とをそれぞれ１２個ずつ備えている。また、ハミング重み（１の数）が１の信号の場合、１を出力するハミング重み１を検出する回路７１をも備えている。
【０２７０】
ここで、誤りバイト検出回路７０は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０の１バイト（６ビット）を入力とし、１ビットのシンドローム検出信号を出力する。すなわち、６ビットの入力がすべて０である場合に、０が出力され、そうでない場合に、１が出力される。
【０２７１】
また、ｔビット誤り訂正復号回路（本例では、２ビット誤り訂正復号回路）７２は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を入力とし、１バイトからＧＦ（２８）上のビット誤りポインタ（ｅ）４２の１バイトを出力する。また、ｔビット誤り訂正復号回路７２では、訂正能力をこえた誤りを検出する信号をも出力する。
【０２７２】
そして、ビットごと選択回路７５は、それぞれ８ビットを有する２つの信号の各ビットどうしを制御信号に従って選択する。
【０２７３】
最後に、ハミング重み１を検出する回路７１は、入力された信号のハミング重みを計算し、ハミング重みが１の場合に、１を出力し、そうでない場合に、０を出力する。
【０２７４】
ここで、ＧＦ（２８）上の誤り生成回路９の処理をより詳しく説明すると、図１５に示すように、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０を６ビットずつに分け、誤りバイト検出回路７０、及び２ビット誤り訂正復号回路７２にそれぞれ入力する。
【０２７５】
次に、誤りバイト検出回路７０から出力された検出信号を、ハミング重み１を検出する回路７１に入力する。ハミング重み１を検出する回路７１から出力された信号と、誤りバイト検出回路７０から出力された検出信号とをそれぞれ２入力ＡＮＤゲート回路７３に入力する。
【０２７６】
そして、２入力ＡＮＤゲート回路７３から出力された信号をビットごと選択回路７５の制御信号とし、ビットごと選択回路７５では、２ビット誤り訂正復号回路７２から出力された信号、及びバイトごとの誤りの和（ｅＡ）３８の選択をこの制御信号に従って行う。選択された信号を集め、９０ビットのＧＦ（２ｂ）上のビット誤りポインタ４２を出力する。
【０２７７】
また、２ビット誤り訂正復号回路７２から出力された検出信号は、１２入力ＯＲゲート回路７４に入力される。１２入力ＯＲゲート回路７４は、入力された検出信号に基づいて、訂正不可能誤り検出信号（ＤＳ（１））４３を出力する。
【０２７８】
次に、誤りバイト検出回路７０の構成例を具体的に示す。例として、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０の２バイト目に対する誤りバイト検出回路７０を図１６に示す。
【０２７９】
図１６に示すように、誤りバイト検出回路７０では、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０の２バイト目の信号ｅ’６、ｅ’７、ｅ’８、ｅ’９、ｅ’１０、ｅ’１１を６入力ＯＲゲート回路８０に入力することにより、シンドローム検出信号を出力する。
【０２８０】
次に、ハミング重み１を検出する回路７１の構成例を図１７に示す。
【０２８１】
図１７に示すように、ハミング重み１を検出する回路７１は、１２入力ソート回路８１を備えている。１２入力ソート回路８１は、入力される１２ビットの情報中の重み（１の数）を数え、その重みの数だけ出力の上位ビットから１を連続して表記する回路である。例えば、１２ビットの入力情報中に１が６個存在する場合、この回路の出力１２ビットのうち上位６ビットはすべて１を、残りの６ビットはすべて０を出力する回路である。
【０２８２】
ここで、ハミング重み１を検出する回路７１の処理をより詳しく説明すると、図１７に示すように、１２ビットの信号を１２入力ソート回路８１に入力する。１２入力ソート回路８１から出力される信号のうち、上位１ビットを除く１１ビットをＮＯＴゲート回路８２に入力する。次に、１２入力ソート回路８１から出力される上位１ビットの信号と、ＮＯＴゲート回路８２から出力される１１ビットの信号とを１２入力ＡＮＤゲート回路８３に入力することにより、ハミング重み１の検出信号を出力する。
【０２８３】
次に、１２入力ソート回路８１の構成例を図１８に示す。図１８に示すように、１２ビットの入力情報がソートされ、２入力ＯＲゲート回路８４、及び２入力ＡＮＤゲート回路８５が対になって構成された２入力２出力回路をセルとして、１２入力に対してこのセルを多段に接続して構成している。このソート回路は、一般に、ｎビット入力中に１の数がｘ個存在すれば、ｎビットの上位ｘ個に１を出力し、残りの出力はすべて０を出力する回路である。なお、この回路の一般的な構成は、非特許文献１２に述べられている。
【０２８４】
図１８に示すように、１２入力１２出力の回路である１２入力ソート回路８１では、このセルを３９個（すなわち、７８ゲート）使用し、最大１２段のセル（１２ゲート段）で実現することが可能である。例えば、１２ビットの入力情報として（００１０１１００１０１１）のような重み６の情報のとき、出力は（１１１１１１００００００）となる。
【０２８５】
次に、２ビット誤り訂正復号回路７２の構成例を具体的に示す。
【０２８６】
例として、２バイト目に対する２ビット誤り訂正復号回路７２の上位４ビットを出力する回路を図１９に、２バイト目に対する２ビット誤り訂正復号回路７２の下位４ビットを出力する回路を図２０に、また訂正能力をこえた誤りのときに“１”を出力する検出信号を出力する回路を図２１にそれぞれ示す。
【０２８７】
２ビット誤り訂正復号回路７２は、ＧＦ（２６）上のビット誤りポインタ（ｅ’）４０の２バイト目を入力とし、ＧＦ（２８）上のビット誤りポインタ（ｅ）４２の２バイト目と、検出信号とを出力する回路である。
【０２８８】
２ビット誤り訂正復号回路７２は、ＧＦ（２８）上の誤りｅI、ＧＦ（２６）上の誤りｅ’Iにおいて、ｅI→ｅ’Iは単射の関係となっている。よって、論理合成を行うことにより、組み合わせ回路で実現することができる。
【０２８９】
具体的に、例えば、図１９において、情報２バイト目では、ｅI・Ｈ’Ｔ＝ｅI’であり、Ｈ’は、数２６に示すランク４を有する２ビット誤り訂正符号の検査行列であるため、重みが２以下のＧＦ（２８）上の誤りｅI、及びＧＦ（２６）上の誤りｅI’は一意に定まる。よって、重みが２以下のＧＦ（２８）上の誤りｅI＝（ｅ８ｅ９ｅ１０ｅ１１ｅ１２ｅ１３ｅ１４ｅ１５）、及びＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）は、下記表１に示す関係を有する。
【０２９０】
【表１】
2006101429.tif 000197
ここで、ＧＦ（２６）上の誤りｅI’は３７パターンあるが、残りの２６−３７＝２７パターンに対するｅIは、訂正能力外誤りとして検出し、ｅIの出力はドントケア＊とする。
【０２９１】
例えば、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係から、情報２バイト目の１ビット目の値ｅ８は、ｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ ｅ１０’ｅ１１’）＝（１０００００）、（１１００００）、（１０１０００）、（１００１００）、（０１１１００）、（１０００１０）、（１０１１１１）、（１００００１）のときに、１となる。
【０２９２】
また、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係において、残った２７パターンのＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）＝（１００１１０）、（１１０１１０）、（０１０１１０）、（０１１１１０）、（１０１１１０）、（１１００１０）、（０１１０１０）、（１１１０１０）、（１０１０１０）、（１０００１１）、（０１００１１）、（０１１０１１）、（１１１０１１）、（１０１０１１）、（１００１１１）、（１１０１１１）、（０１０１１１）、（１１１１１１）、（１００１０１）、（１１０１０１）、（０１０１０１）、（０１１１０１）、（１０１１０１）、（１１０００１）、（０１１００１）、（１１１００１）、（１０１００１）に対する情報２バイト目の１ビット目の値ｅ８は、ドントケア＊とする。
【０２９３】
これらの論理関数を簡単化すると、情報２バイト目の１ビット目の値ｅ８は、下記数８８に示す論理式で表される。
【０２９４】
【数８８】
2006101429.tif 000198
ただし、
2006101429.tif 000199
は
2006101429.tif 000200
の否定で、
2006101429.tif 000201
は
2006101429.tif 000202
であり、また、
2006101429.tif 000203
は論理和を、
2006101429.tif 000204
は論理積を表す。
【０２９５】
よって、図１９に示されるように、まず、ＧＦ（２６）上のビット誤りポインタ４０ｅ’６、ｅ’７、ｅ’８、ｅ’９、ｅ’１０、ｅ’１１をＮＯＴゲート回路９０に入力し、
2006101429.tif 000205
を生成する。そして、
2006101429.tif 000206
を３入力ＡＮＤゲート回路９１に、
2006101429.tif 000207
を４入力ＡＮＤゲート回路９２に、
2006101429.tif 000208
を５入力ＡＮＤゲート回路９３に、
2006101429.tif 000209
を４入力ＡＮＤゲート回路９２に、
2006101429.tif 000210
を４入力ＡＮＤゲート回路９２にそれぞれ入力する。それぞれのＡＮＤゲート回路から出力された信号を５入力ＯＲゲート回路９４に入力することにより、情報２バイト目の１ビット目の値ｅ８が得られる。
【０２９６】
図１９及び図２０に示されるように、他のビットの値ｅ９、・・・、ｅ１５も、ＮＯＴゲート回路９０、３入力ＡＮＤゲート回路９１、４入力ＡＮＤゲート回路９２、５入力ＡＮＤゲート回路９３、５入力ＯＲゲート回路９４、６入力ＯＲゲート回路９５により、同様にして得られる。
【０２９７】
また、ｔビット誤り訂正復号回路（本例では、２ビット誤り訂正復号回路）７２の検出信号出力部も同様にして、構成することができる。検出信号出力部は、ＧＦ（２６）上の誤りｅ’Iから写像されることのないＧＦ（２８）上の誤りｅIを訂正不可能な誤りとして検出する。例えば、２バイト目に対する検出信号出力部を図２１に示す。
【０２９８】
具体的に、例えば、情報２バイト目において、上記表１に示されたＧＦ（２８）上の誤りｅIとＧＦ（２６）上の誤りｅI’の対応関係において、残った２７パターンのＧＦ（２６）上の誤りｅI’＝（ｅ６’ｅ７’ｅ８’ｅ９’ｅ１０’ｅ１１’）＝（１００１１０）、（１１０１１０）、（０１０１１０）、（０１１１１０）、（１０１１１０）、（１１００１０）、（０１１０１０）、（１１１０１０）、（１０１０１０）、（１０００１１）、（０１００１１）、（０１１０１１）、（１１１０１１）、（１０１０１１）、（１００１１１）、（１１０１１１）、（０１０１１１）、（１１１１１１）、（１００１０１）、（１１０１０１）、（０１０１０１）、（０１１１０１）、（１０１１０１）、（１１０００１）、（０１１００１）、（１１１００１）、（１０１００１）に対する検出信号の値を１にし、誤りを検出する。
【０２９９】
よって、これらの論理関数を簡単化すると、検出信号の値は、下記数８９に示す論理式で表される。
【０３００】
【数８９】
2006101429.tif 000211
よって、図２１に示されるように、まず、ＧＦ（２６）上のビット誤りポインタ４０ｅ’６、ｅ’７、ｅ’８、ｅ’９、ｅ’１０、ｅ’１１をＮＯＴゲート回路９０に入力し、
2006101429.tif 000212
を生成する。
【０３０１】
そして、
2006101429.tif 000213
を合計１４個の４入力ＡＮＤゲート９２及び５入力ＡＮＤゲート９３にそれぞれ入力する。
【０３０２】
最後に、それぞれのＡＮＤゲート回路から出力された信号を、１４入力ＯＲ回路９６に入力することにより、検出信号を出力する。
【０３０３】
なお、以上では、２バイト目におけるｔビット誤り訂正復号回路７２を例として詳細に説明したが、他のバイトについてもまったく同様である。
【０３０４】
最後に、ビットごと選択回路７５の構成例を具体的に示す。
【０３０５】
図２２に示すように、ビットごと選択回路７５は、それぞれ８ビットを有する２つの信号の各ビットどうしを制御信号に従って選択する回路である。
【０３０６】
ここで、ビットごと選択回路７５の処理をより詳しく説明すると、図２２に示すように、８ビットの信号の中で０ビット目どうしを２入力マルチプレクサ８６に入力する。２入力マルチプレクサ８６では、制御信号が０の場合に、上の信号を出力し、制御信号が１の場合に、下の信号を出力する。０ビット目以外の信号に関しても同様に、制御信号により選択を行う。２入力マルチプレクサ８６から出力された各信号をまとめて、最終的に８ビットの信号として出力する。
【０３０７】
以上では、距離ｄ＝５を有する符号を例として説明したが、ｄ＝５以外の距離を有する符号についても、バイトごとの誤りの和（ｅＡ）とＧＦ（２ｒ）上のビット誤りポインタとを用いて、ＧＦ（２ｂ）上の誤り生成回路中のビットごと選択回路７５を用いて場合分けを行うことにより、同様に回路を構成することができる。
（ｆ）反転回路１０の構成
最後に、反転回路１０の構成について説明する。
【０３０８】
例えば、２バイト目に対して、具体的に構成した反転回路１０を図２３に示す。図２３に示す反転回路１０は、誤りの箇所を具体的に指摘されたビット位置に対して、受信したビット値の反転を行って受信語（Ｖ’）３２を訂正する回路である。図２３において、ｖ８’〜ｖ１５’は、受信語（Ｖ’）３２の２バイト目に相当する８ビットであり、ｖ８＊〜ｖ１５＊は訂正後の出力ビットである。
【０３０９】
反転回路１０は、複数の排他的論理和回路を有している。図２３に示された２バイト目における反転回路１０において、合計８個の排他的論理和回路９７は、８入力ビットｖ８’〜ｖ１５’に対して、対応するビット誤りポインタｅｉ（ｉ＝８、９、・・・、１５）との排他的論理和をとり、例えば、ビット誤りポインタが“１”のとき、入力ビット値が反転されて訂正されることになる。
【０３１０】
なお、反転回路１０は、各バイトにそれぞれ対応するようにするため、Ｎ＝９０ビットの受信語（Ｖ’）に対しては、９０個の排他的論理和回路が必要となる。反転回路１０は、最後に、Ｎ＝９０ビットの受信語（Ｖ’）から、下記数９０に示す６４ビットの訂正語Ｄ＊を得る。
【０３１１】
【数９０】
2006101429.tif 000214
以上では、図３に示す距離ｄ＝５を有する（９０、６４）Ｄ２／８ＥＣ符号を例にとり、距離ｄを有するバイト内複数スポッティバイト誤り制御符号における符号化・復号回路構成を詳細に説明した。ここで、ＧＦ（２ｒ）上の並列復号回路８において、前記バーレカンプ・マッシィ法を用いた逐次復号を行う場合に、誤り位置多項式および誤り評価多項式から、誤り位置および誤りを求める既存の手法を用いればよい。この手法の実現手段は、ハードウェアでもソフトウェアでもよい。
【０３１２】
また、ｄ＝５以外の距離ｄを有するバイト内複数スポッティバイト誤り制御符号に対しては、次のような考えで構成することができる。
【０３１３】
まず、符号化回路は、２元で表現したパリティ検査行列により、Ｒビットの検査情報を生成すればよく、全く同様に構成することができる。
【０３１４】
また、復号は、前述したように、前記ＲＳ符号の復号により得られたＧＦ（２ｒ）上の誤りｅ’において、誤りが生じているバイト数による場合分けを行うことにより、ＧＦ（２ｂ）上の誤りを求めることができる。
【０３１５】
例えば、距離ｄ＝７の場合、行列Ｈ”がＲａｎｋ（Ｈ”）≧Ｍｉｎ（３ｔ、ｂ）を満足する行列であることから、距離ｄ＝５の例における前記ＧＦ（２ｂ）上の誤り生成回路９において、ｔビット誤り訂正復号回路７２の構成をｔビット誤り訂正・２ｔビット誤り検出の訂正能力を有する符号の復号回路へ変更する。
【０３１６】
また、ＧＦ（２ｒ）上の誤りｅ’において、誤りが生じているバイトが１、２、３バイトの場合を、それぞれビットごと選択回路７５を用いて場合分けを行う回路を構成することにより、同様に復号回路を構成することができる。従って、距離ｄ＝５、７以外の場合も、距離ｄを有するバイト内複数スポッティバイト誤り制御符号の復号回路を同様に構成できることは明らかである。
【０３１７】
さらに、上記数５に示された伸長バイト内複数スポッティバイト誤り制御符号に対しては、次のような考えで構成することができる。
【０３１８】
まず、符号化回路は、２元で表現したパリティ検査行列により、Ｒビットの検査情報を生成すればよく、全く同様に構成することができる。
【０３１９】
また、復号は、前記並列復号法やバーレカンプ・マッシィ法を用いた逐次復号法により、ＧＦ（２（Ｒ−ｒ）／（ｄ−２））上のＲＳ符号の復号をすることにより、また、ＧＦ（２（Ｒ−ｒ）／（ｄ−２））上の誤りをＧＦ（２ｂ）上の誤りに距離ｄ＝５の例と同様に変換することにより、同様に復号することができる。
【０３２０】
よって、復号回路も距離ｄ＝５の例における前記ＧＦ（２ｒ）上の並列復号回路８をＧＦ（２（Ｒ−ｒ）／（ｄ−２））上で並列復号を行う回路に変更することにより、また、距離ｄ＝５の例における前記ＧＦ（２ｂ）上の誤り生成回路９において、ｒビットを（Ｒ−ｒ）／（ｄ−２）ビットに変更することにより、復号回路を同様に構成できることは明らかである。
【０３２１】
また、上記数２８、数３６、数４６、数５９に示された大きさの異なる２種類のバイト内複数スポッティバイト誤り制御符号に対しては、次のような考えで構成することができる。
【０３２２】
まず、符号化回路は、２元で表現したパリティ検査行列により、Ｒビットの検査情報を生成すればよく、全く同様に構成することができる。
【０３２３】
また、復号は、例えば、数２８に示されたＳｔ／ｂＥＣ―（Ｓｔ／ｂ＋Ｓｔ’／ｂ）ＥＤ符号では、ＧＦ（２ｒ）上の誤りｅ’において、誤りが生じている個所が１バイトである場合に、Ｈ”がＲａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足する行列であるため、ｂビットを有するバイト中のｔビット以内の誤りであるｅIに対し、ｅI・Ｈ’Ｔ＝ｅI’の関係式から誤りｅIを求めることができる。また、ＧＦ（２ｒ）上の誤りｅ’において、誤りが生じている個所が２バイトである場合に、前記並列復号の際に検出することができる。
【０３２４】
よって、距離ｄ＝５の例における前記Ｈ’復号回路６、Ｈ”乗算回路７、及びｔビット誤り訂正復号回路７２を、それぞれＲａｎｋ（Ｈ’）≧Ｍｉｎ（２ｔ＋ｔ’、ｂ）を満足する行列Ｈ’、Ｒａｎｋ（Ｈ”）≧Ｍａｘ（ｔ、ｔ’）を満足する行列Ｈ”に対応させることにより、距離ｄ＝４のバイト内複数スポッティバイト誤り制御符号の復号回路と同様に復号回路を構成することが可能である。
【０３２５】
同様に、数３６に示された大きさの異なる２種類のバイト内複数スポッティバイト誤り制御符号は、距離ｄ＝４のバイト内複数スポッティバイト誤り制御符号の復号回路と同様に構成できることは明らかである。
【０３２６】
また、数４６、数５９に示された大きさの異なる２種類のバイト内複数スポッティバイト誤り制御符号は、距離ｄ＝５のバイト内複数スポッティバイト誤り制御符号の復号回路と同様に構成可能できることは明らかである。
【０３２７】
前述したように、本発明では、バイト中にｔビットまでの誤りを有するスポッティバイト誤りに対し、任意所定の距離ｄを有するバイト内複数スポッティバイト誤り制御符号の一般性のある符号構成、及び大きさの異なる２種類のバイト内複数スポッティバイト誤りを制御する符号の符号構成を与えるとともに、誤りの訂正・検出が実現できる回路である符号化・復号回路構成を示して、検査情報が具体的に生成できること、及び誤りが具体的に訂正・検出できることを示した。
【０３２８】
以上の説明では、主としてメモリ装置に注目して本発明の適用を述べたが、本発明は、それに限定されるものではなく、例えば、このようなバイト単位で物理的に独立した回路と、モジュールと、装置とから構成され、この中で限定した数の誤りが生じる可能性の高い一般の情報システム等に適用可能である。また、光通信回路やバス線回路等の通信または伝送のための回路、装置またはシステムにも適用可能である。
【０３２９】
また、本発明の目的は、本実施の形態のバイト内複数スポッティバイト誤り訂正・検出装置の機能を実現するソフトウェアのプログラムコードを記述した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出して実行することによっても、達成されることは言うまでもない。
【０３３０】
この場合、記憶媒体から読み出されたプログラムコード自体が本実施の形態の機能を実現することとなり、そのプログラムコードを記憶した記憶媒体及び当該プログラムコードは本発明を構成することとなる。プログラムコードを供給するための記憶媒体としては、ＲＯＭ、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード等を用いることができる。
【０３３１】
また、コンピュータが読み出したプログラムコードを実行することにより、前記本実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ等が実際の処理の一部又は全部を行い、その処理によって本実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０３３２】
【図１】本発明の一実施形態であるバイト内複数スポッティバイト誤り訂正・検出装置の概略構成を示すブロック図である。
【図２】図１に示された本発明のバイト内複数スポッティバイト誤り訂正・検出装置における全体動作の処理手順を示すフローチャートである。
【図３】本発明によるパリティ検査行列の一例であって、符号長Ｎ＝９０ビット、情報長Ｋ＝６４ビット、検査長Ｒ＝２６ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長２ビットの符号パラメータを有する短縮（９０、６４）Ｄ２／８ＥＣ符号のパリティ検査行列を示す図である。
【図４】図３に示すパリティ検査行列を基本行変形して得られる符号化用（９０、６４）Ｄ２／８ＥＣ組織符号のパリティ検査行列を示す図である。
【図５】図４に示す符号化用（９０、６４）Ｄ２／８ＥＣ組織符号をもとに構成した符号化回路（上位１４ビット）の具体例であり、Ｋ＝６４ビットの入力情報データからパリティ検査行列により２６ビットの検査情報を生成する回路の概念図である。
【図６】図４に示す符号化用（９０、６４）Ｄ２／８ＥＣ組織符号をもとに構成した符号化回路（下位１２ビット）の具体例であり、Ｋ＝６４ビットの入力情報データからパリティ検査行列により２６ビットの検査情報を生成する回路の概念図である。
【図７】本発明で開示された機能を有する符号に対する復号回路の概略構成を示すブロック図である。
【図８】図３に示す（９０、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したシンドローム生成回路（上位１４ビット）を説明するための概念図である。
【図９】図３に示す（９０、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したシンドローム生成回路（下位１２ビット）を説明するための概念図である。
【図１０】図３に示す（９０、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したＨ’復号回路の構成図である。
【図１１】図３に示す（９０、６４）Ｄ２／８ＥＣ符号をもとに具体的に構成したＨ”乗算回路の構成図である。
【図１２】図３に示す（９０、６４）Ｄ２／８ＥＣ符号に対するＧＦ（２ｒ）上の並列復号回路の概略構成を示すブロック図である。
【図１３】図１２に示すＧＦ（２ｒ）上の並列復号回路における（ｉ、ｊ）に対する誤り生成回路の一例の回路構成図である。
【図１４】図１２に示すＧＦ（２ｒ）上の並列復号回路におけるＧＦ（２ｒ）上の誤り算出回路の構成図である。
【図１５】図３に示す（９０、６４）Ｄ２／８ＥＣ符号に対するＧＦ（２ｂ）上の誤り生成回路の概略構成を示すブロック図である。
【図１６】図１５に示すＧＦ（２ｂ）上の誤り生成回路における誤りバイト検出回路の構成図である。
【図１７】図１５に示すＧＦ（２ｂ）上の誤り生成回路におけるハミング重み１を検出する回路の構成図である。
【図１８】図１６に示すハミング重み１を検出する回路における１２入力ソート回路の構成図である。
【図１９】図１５に示すＧＦ（２ｂ）上の誤り生成回路におけるｔビット誤り訂正復号回路の例であり、１バイトに対してＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換する回路（上位４ビット）の構成図である。
【図２０】図１５に示すＧＦ（２ｂ）上の誤り生成回路におけるｔビット誤り訂正復号回路の例であり、１バイトに対してＧＦ（２ｒ）上の誤りをＧＦ（２ｂ）上の誤りに変換する回路（下位４ビット）の構成図である。
【図２１】図１５に示すＧＦ（２ｂ）上の誤り生成回路におけるｔビット誤り訂正復号回路の例であり、１バイトに対して誤りを検出する回路の構成図である。
【図２２】図１５に示すＧＦ（２ｂ）上の誤り生成回路におけるビットごと選択回路の構成図である。
【図２３】図３に示す（９０、６４）Ｄ２／８ＥＣ符号に対する反転回路の一例であり、１バイトに対する反転回路の構成図である。
【符号の説明】
【０３３３】
１    シンドローム生成回路
２    符号化回路
３    回路（メモリ等の通信路）
４    復号回路
５    誤り訂正回路
６    Ｈ’復号回路
７    Ｈ”乗算回路
８    ＧＦ（２ｒ）上の並列復号回路
９    ＧＦ（２ｂ）上の誤り生成回路
１０    反転回路
２０    多入力パリティチェック回路
２１    多入力パリティチェック回路
２２    ２入力排他的論理和回路
２３    ３入力パリティチェック回路
３０    入力情報データ
３１    送信語
３２    受信語
３３    シンドローム（Ｓ）
３４    出力情報データ
３５    訂正不可能誤り検出信号（ＵＣＥ）
３６    シンドローム（Ｓ）３３の上位ｑビット（ＳI）
３７    シンドローム（Ｓ）３３の下位３ｒビット（ＳIIＳIIIＳIV）
３８    バイトごとの誤りの和（ｅＡ）
３９    シンドローム（Ｓ）３３の上位ｑビットＳI３６とＨ”の転置（Ｈ”Ｔ）の積（Ｓ’I）
４０    ＧＦ（２ｒ）上のビット誤りポインタ
４１    訂正不可能誤り検出信号（ＤＳ（０））
４２    ＧＦ（２ｂ）上のビット誤りポインタ
４３    訂正不可能誤り検出信号（ＤＳ（１））
４４    ２入力ＡＮＤゲート回路
５０    （ｉ、ｊ）に対する誤り生成回路
５１    ＧＦ（２ｒ）上の誤り算出回路
５２    （ｉ、ｊ）に対する誤り
５３    （ｉ、ｊ）に対する訂正可能信号
５４    ２４入力ＯＲゲート回路
５５    ６６入力ＮＯＲゲート回路
５６    ２入力ＡＮＤゲート回路
６０
2006101429.tif 000215
６１
2006101429.tif 000216
６２
2006101429.tif 000217
６３    多入力パリティチェック回路
６４    多入力パリティチェック回路
６５    多入力パリティチェック回路
６６    １２入力ＮＯＲゲート回路
６７    ２入力ＡＮＤゲート回路
６８    ビットごとＯＲ演算回路
６９    １１入力ＯＲゲート回路
７０    誤りバイト検出回路
７１    ハミング重み１を検出する回路
７２    ｔビット誤り訂正復号回路
７３    ２入力ＡＮＤゲート回路
７４    １２入力ＯＲゲート回路
７５    ビットごと選択回路
８０    ６入力ＯＲゲート回路
８１    １２入力ソート回路
８２    ＮＯＴゲート回路
８３    １２入力ＡＮＤゲート回路
８４    ２入力ＯＲゲート回路
８５    ２入力ＡＮＤゲート回路
８６    ２入力マルチプレクサ回路
９０    ＮＯＴゲート回路
９１    ３入力ＡＮＤゲート回路
９２    ４入力ＡＮＤゲート回路
９３    ５入力ＡＮＤゲート回路
９４    ５入力ＯＲゲート回路
９５    ６入力ＯＲゲート回路
９６    １５入力ＯＲゲート回路
９７    排他的論理和回路
１００    バイト内複数スポッティバイト誤り訂正・検出装置
【図１】
2006101429.tif 000254
【図２】
2006101429.tif 000255
【図３】
2006101429.tif 000256
【図４】
2006101429.tif 000257
【図５】
2006101429.tif 000258
【図６】
2006101429.tif 000259
【図７】
2006101429.tif 000260
【図８】
2006101429.tif 000261
【図９】
2006101429.tif 000262
【図１０】
2006101429.tif 000263
【図１１】
2006101429.tif 000264
【図１２】
2006101429.tif 000265
【図１３】
2006101429.tif 000266
【図１４】
2006101429.tif 000267
【図１５】
2006101429.tif 000268
【図１６】
2006101429.tif 000269
【図１７】
2006101429.tif 000270
【図１８】
2006101429.tif 000271
【図１９】
2006101429.tif 000272
【図２０】
2006101429.tif 000273
【図２１】
2006101429.tif 000274
【図２２】
2006101429.tif 000275
【図２３】
2006101429.tif 000276