(57)【要約】【課題】ｂビットのバイト中の１からｔビットまでの誤りを訂正するバイト内ｔビット誤り訂正機能と、１バイト中のｔビットまでの誤りを訂正し１バイト中にｔビットより大きい誤りを検出するバイト内ｔビット誤り訂正・１バイト誤り検出機能と、複数バイトからなるＢビットのブロック中の任意のｔビット誤りを訂正しｂビットの１バイト中の任意の誤りを訂正し更に１ブロック中の任意の誤りを検出するブロック内ｔビット誤り訂正・１バイト誤り訂正・１ブロック誤り検出機能とを有するバイト誤り訂正・検出方法及び装置を提供する。【解決手段】符号化回路は入力情報データに基づいて検査ビットを生成しその検査ビットを入力情報データに付加して情報語として通信路に送出し、通信路を経て受信された情報語は受信語として復号回路に入力され、復号回路は受信語に符号を表現するパリティ検査行列の転置行列を乗算してシンドロームをシンドローム生成回路において生成し更にシンドロームのパターンに基づいて誤りの訂正を誤り訂正回路において行うようにする。【選択図】　　図１
2004007217.tif 000002
【特許請求の範囲】
【請求項１】
符号化手段と復号手段とを備えるバイト誤り訂正・検出装置であって、
前記符号化手段は、符号を表現するパリティ検査行列Ｈに基き、入力されたＫビットの入力情報データからＲビットの検査ビットを生成してから、前記検査ビットを前記入力情報データに付加して送信語として、情報伝送路に送出されるように構成され、
前記情報伝送路を経て受信された前記送信語は、受信語Ｖとして前記復号手段に入力され、
前記復号手段は、入力された前記受信語Ｖに前記パリティ検査行列Ｈの転置行列ＨＴを乗算してＲビットのシンドロームＳを生成するシンドローム生成手段と、前記シンドロームＳのパターンに基いて誤りの訂正を行う誤り訂正手段とを有し、
誤りが訂正された情報Ｖ＊は出力情報データとして出力され、また、前記符号により訂正できない誤りを検出した場合には、誤り検出出力としてＵＣＥ信号を出力することを特徴とするバイト誤り訂正・検出装置。
【請求項２】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有する請求項１に記載のバイト誤り訂正・検出装置。
【請求項３】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、更にｔビットを越える１バイトの誤りであれば、これを完全に検出する機能を有する請求項１に記載のバイト誤り訂正・検出装置。
【請求項４】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、複数バイトからなる長さＢ（Ｂはｂの倍数）ビットを有する１ブロック中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、且つ、ｔビットを越える１バイトの誤りを訂正し、更に１バイトを越える１ブロックの誤りであれば、これを完全に検出する機能を有する請求項１に記載のバイト誤り訂正・検出装置。
【請求項５】
前記情報伝送路は、情報通信システムである請求項１乃至４のいずれかに記載のバイト誤り訂正・検出装置。
【請求項６】
前記情報伝送路は、メモリシステムである請求項１乃至４のいずれかに記載のバイト誤り訂正・検出装置。
【請求項７】
前記情報伝送路は、バス線回路である請求項１乃至４のいずれかに記載のバイト誤り訂正・検出装置。
【請求項８】
前記パリティ検査行列Ｈは、次のマトリクスＨ１＊であり、
2004007217.tif 000058
ただし、ＩＲはＲ行Ｒ列の単位行列であり、Ｈ’はランクｔ以上のＲ−ｑ行ｂ列の２元マトリクスであり、Ｈ＃は２ｔおよびｂのうちいずれか小さい方の値に等しいか大きいランクを有するｑ行ｂ列の２元マトリクスであり、すなわちＲａｎｋ（Ｈ＃）≧ ｍｉｎ（２ｔ、ｂ）、また、Ｉｑはｑ行ｑ列の単位行列であり、０ｘ×ｙはｘ行ｙ列の零マトリクスであり、ｍ＝２Ｒ−ｑ−２、検査ビット数Ｒ≧ ｑ＋　ｒとする。ｑ、ｒはそれぞれＨ＃、Ｈ’のランクを満足させる条件から決まるＨ＃、Ｈ’の行数であり、γは２を底とするＲ−ｑ次のガロア体ＧＦ（２Ｒ−ｑ）の原始元であり、また、φは加算のもとでＧＦ（２ｒ）をＧＦ（２Ｒ−ｑ）への準同形写像とするときに、次の式が成立し、
2004007217.tif 000059
ここで、ｉは０≦ｉ≦ ｍの範囲を有する整数であり、また、Ｈ’は、ランクｔ以上のｒ行ｂ列の２元マトリクスであり、次の式に表されるように、ｒ次の列ベクトルｈｊ（０ ≦　ｊ≦　ｂ−１）から構成される
2004007217.tif 000060
ようになっている請求項２に記載のバイト誤り訂正・検出装置。
【請求項９】
前記パリティ検査行列Ｈは、次のマトリクスＨ１＊＊＊であり、
2004007217.tif 000061
ただし、０ｑ×ｑはｑ行ｑ列の零行列であり、ＩＲはＲ行Ｒ列の単位行列であり、ＨＲ−（ｗ−１）ｑは次の式に表され、
2004007217.tif 000062
ここで、Ｈ＃はｍｉｎ（２ｔ、ｂ）以上のランクを有するｑ行ｂ列の２元マトリクスであり、Ｈ’＊はランクｔ以上のＲ−ｗｑ行ｂ列の２元マトリクスであり、ωは２を底とするＲ−ｗｑ次のガロア体ＧＦ（２Ｒ−ｗｑ）の原始元であり、ｍ’’＝２Ｒ−ｗｑ−２となり、ｑ、ｒはそれぞれＨ＃、Ｈ’＊のランクを満足させる条件から決まるＨ＃、Ｈ’＊の行数であり、また、検査ビット数Ｒ≧　ｗｑ＋ｒであり、ｗは１以上の整数であるようになっている請求項２に記載のバイト誤り訂正・検出装置。
【請求項１０】
前記パリティ検査行列Ｈは、次のマトリクスＨ２＊であり、
2004007217.tif 000063
ただし、Ｉｚはｚ行ｚ列の単位行列であり、ＩＲはＲ行Ｒ列の単位行列であり、Ｈ’はランクｔ以上のＲ−ｂ行ｂ列の２元マトリクスであり、また０ｘ×ｙはｘ行ｙ列の零マトリクスであり、ｍ＝２Ｒ−ｂ−２、検査ビット数Ｒ≧　ｂ　＋　ｒとし、ｒはＨ’のランクを満足させる条件から決まるＨ’の行数であり、γはガロア体ＧＦ（２Ｒ−ｂ）の原始元であり、また、φは加算のもとでＧＦ（２ｒ）をＧＦ（２Ｒ−ｂ）への準同形写像とするときに、次の式が成立し、
2004007217.tif 000064
ここで、ｉは０≦ ｉ ≦ ｍの範囲を有する整数であり、また、Ｈ’は、ランクｔ以上のｒ行ｂ列の２元マトリクスであり、次の式に表されるように、ｒ次の列ベクトルｈｊ（０ ≦　ｊ≦　ｂ−１）から構成される
2004007217.tif 000065
ようになっている請求項３に記載のバイト誤り訂正・検出装置。
【請求項１１】
前記パリティ検査行列Ｈは、次のマトリクスＨ２＊＊＊であり、
2004007217.tif 000066
ただし、０ｂ×ｂはｂ行ｂ列の零行列であり、ＩＲはＲ行Ｒ列の単位行列であり、ＨＲ−（ｗ−１）ｂは次の式に表され、
2004007217.tif 000067
ここで、Ｉｂはｂ行ｂ列の単位行列であり、Ｈ’＊はランクｔ以上のＲ−ｗｂ行ｂ列の２元マトリクスであり、ωは２を底とするＲ−ｗｂ次のガロア体ＧＦ（２Ｒ−ｗｂ）の原始元であり、ｍ’’＝２Ｒ−ｗｂ−２となり、また、検査ビット数Ｒ≧　ｗｂ＋　ｒであり、ｒはＨ’＊のランクを満足させる条件から決まるＨ’＊の行数であり、ｗは１以上の整数であるようになっている請求項３に記載のバイト誤り訂正・検出装置。
【請求項１２】
前記パリティ検査行列Ｈは、次のマトリクスＨ２＊であり、
2004007217.tif 000068
ただし、Ｉｚはｚ行ｚ列の単位行列であり、ＩＲはＲ行Ｒ列の単位行列であり、Ｈ’はランクｔ以上のＲ−ｂ行ｂ列の２元マトリクスであり、また０ｘ×ｙはｘ行ｙ列の零マトリクスであり、ｍ＝２Ｒ−ｂ−２、検査ビット数Ｒ≧　ｂ　＋　ｒとし、ｒはＨ’のランクを満足させる条件から決まるＨ’の行数であり、γはガロア体ＧＦ（２Ｒ−ｂ）の原始元であり、また、φは加算のもとでＧＦ（２ｒ）をＧＦ（２Ｒ−ｂ）への準同形写像とするときに、次の式が成立し、
2004007217.tif 000069
ここで、ｉは０ ≦ ｉ ≦ ｍの範囲を有する整数であり、
また、Ｈ’は、次の式に示すように、ランクｔ以上を有するｒ行Ｂ列マトリクスであり、
2004007217.tif 000070
ここで、Ｂ／ｂ個のｈｉはランクｂを有するそれぞれ異なるｒ行ｂ列の２元部分行列とし、また、ｉ＝０、１、２、…、Ｂ／ｂ−１とするようになっている請求項４に記載のバイト誤り訂正・検出装置。
【請求項１３】
前記パリティ検査行列Ｈは、次のマトリクスＨ２＊＊＊であり、
2004007217.tif 000071
ただし、０ｂ×ｂはｂ行ｂ列の零行列であり、ＩＲはＲ行Ｒ列の単位行列であり、ＨＲ−（ｗ−１）ｂは次の式に表され、
2004007217.tif 000072
ここで、Ｉｂはｂ行ｂ列の単位行列であり、Ｈ’＊はランクｔ以上のＲ−ｗｂ行ｂ列の２元マトリクスであり、ωは２を底とするＲ−ｗｂ次のガロア体ＧＦ（２Ｒ−ｗｂ）の原始元であり、ｍ’’＝２Ｒ−ｗｂ−２となり、また、検査ビット数Ｒ≧　ｗｂ＋　ｒであり、ｒはＨ’＊のランクを満足させる条件から決まるＨ’＊の行数であり、ｗは１以上の整数であり、
また、Ｈ’は、次の式に示すように、ランクｔ以上を有するｒ行Ｂ列マトリクスであり、
2004007217.tif 000073
ここで、Ｂ／ｂ個のｈｉはランクｂを有するそれぞれ異なるｒ行ｂ列の２元部分行列とし、また、ｉ＝０、１、２、…、Ｂ／ｂ−１とするようになっている請求項４に記載のバイト誤り訂正・検出装置。
【請求項１４】
前記誤り訂正手段は、シンドロームデコード手段と、誤り検出手段と、反転手段とを有し、
前記シンドローム生成手段にて生成された前記シンドロームＳは、前記シンドロームデコード手段に入力されると共に、前記誤り検出手段にも入力され、
前記シンドロームデコード手段は、入力された前記シンドロームＳに基づいて、具体的に誤りのビットを指摘するＫビットのビット誤りポインターを生成し、
前記誤り検出手段は、入力された前記シンドロームＳに基づいて、誤りが訂正可能であるか否かを判別し、訂正不可能な誤りであれば、検出して前記ＵＣＥ信号を出力し、
前記反転手段は、前記受信語Ｖ中のＫビットからなる情報ビットに対して、前記シンドロームデコード手段から出力されたＫビットの前記ビット誤りポインターを用いて、誤り訂正を行い、誤り訂正された正しい情報Ｖ＊としてＫビットの前記出力情報データを出力するようになっている請求項１に記載のバイト誤り訂正・検出装置。
【請求項１５】
前記誤り検出手段は、Ｒビットの前記シンドロームＳにおいて、少なくともいずれか１ビットが非零であり、且つ、バイト誤りポインターがすべて“０”であるときに、前記受信語Ｖ中にｔビットを越えるバイト誤りを含む訂正不可能な誤りが存在したことを検出し、出力信号である前記ＵＣＥ信号を“１”にするようになっている請求項１４に記載のバイト誤り訂正・検出装置。
【請求項１６】
入力情報データに検査ビットが付加された情報語に対するバイト誤り訂正・検出方法であって、
符号化回路は、入力された入力情報データに基づいて検査ビットを生成し、生成した前記検査ビットを前記入力情報データに付加して前記情報語として通信路に送出し、
前記通信路を経て受信された前記情報語は、受信語Ｖとして復号回路に入力され、
前記復号回路では、前記受信語Ｖに符号を表現するパリティ検査行列Ｈの転置行列ＨＴを乗算してシンドロームＳをシンドローム生成回路において生成し、さらに、前記シンドロームＳのパターンに基づいて誤りの訂正を誤り訂正回路において行い、誤りが訂正された情報Ｖ＊は出力情報データとして出力され、また、前記符号により訂正できない誤りを検出した場合には、誤り検出出力としてＵＣＥ信号を出力することを特徴とするバイト誤り訂正・検出方法。
【請求項１７】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有する請求項１６に記載のバイト誤り訂正・検出方法。
【請求項１８】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、更にｔビットを越える１バイトの誤りであれば、これを完全に検出する機能を有する請求項１６に記載のバイト誤り訂正・検出方法。
【請求項１９】
前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、複数バイトからなる長さＢ（Ｂはｂの倍数）ビットを有する１ブロック中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、且つ、ｔビットを越える１バイトの誤りを訂正し、更に１バイトを越える１ブロックの誤りであれば、これを完全に検出する機能を有する請求項１６に記載のバイト誤り訂正・検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、バイト誤り訂正・検出方法及び装置に関し、詳しくは、ｂ（ｂは２以上の整数）ビットをバイトとし、複数のバイトから構成される語（ワード）に対し、任意の１バイト中にｔ（ｔは１より大きくｂに等しいか小さい整数）ビットの誤りが生じたときにこれを訂正する機能（Ｓｔ／ｂＥＣ）、及び任意の１バイト中にｔビットの誤りが生じたときこれを訂正し、またバイト中にｔビットより大きい誤りが生じたときにこれを検出する機能（Ｓｔ／ｂＥＣ−ＳｂＥＤ）、さらに複数のバイトからなる長さＢビットのブロック中の任意のｔビット誤りが生じたときこれを訂正し、また１バイト中にｔビットより大きいｂビットまでの誤りが生じたときこれを訂正し、さらに１ブロック中に任意の誤りが生じたときこれを検出する機能（Ｓｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ）を有するバイト誤り訂正・検出装置に関する。
【０００２】
【従来の技術】
従来、関連する符号機能を有する既存の装置として、語中の１ビットを訂正し、また語中の１バイトの誤りを検出する１ビット誤り訂正・１バイト誤り検出の符号機能（ＳＥＣ−ＳｂＥＤ）を有する装置は、１９７０年代に提案され、これにさらに語中の任意の２ビット誤りを検出する機能を付加した１ビット誤り訂正・２ビット誤り検出・１バイト誤り検出の符号機能（ＳＥＣ−ＤＥＤ−ＳｂＥＤ）を有する装置は、既に多くの計算機の主記憶装置に採用されている。
【０００３】
また、１バイト中の任意の誤りを訂正する機能を有するハミング（Ｈａｍｍｉｎｇ）符号とＨｏｎｇ−Ｐａｔｅｌ符号は、それぞれ１９６５年、１９７２年に論文で既に明らかにされ、さらに、１バイト誤りを訂正し、２バイト誤りを検出する符号（ＳｂＥＣ−ＤｂＥＤ符号）は、既に多くの主記憶装置に採用されている。さらに、最近の半導体メモリに指向した符号として、１バイトの誤りを訂正し、符号中の２ビット誤りを検出する符号と、１バイトの誤りを訂正し、さらに１バイト誤りと１ビット誤りが同時に生起した場合にこれを検出する符号が、それぞれ１９９３年、１９９７年に論文として提案されている。
【０００４】
なお、関連するこれまでの研究あるいは発表の内容は、Ｔ．Ｒ．Ｎ．Ｒａｏ　ａｎｄ　Ｅ．Ｆｕｊｉｗａｒａ，’’　Ｅｒｒｏｒ　Ｃｏｎｔｒｏｌ　Ｃｏｄｉｎｇ　ｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ’’，　Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，１９８９のＣｈａｐｔｅｒ　５に総括的に述べられている。また、個別には、例えば、ＳＥＣ−ＳｂＥＤ符号に関しては、Ｓ．Ｍ．Ｒｅｄｄｙ，’’Ａ　Ｃｌａｓｓ　ｏｆ　Ｌｉｎｅａｒ　Ｃｏｄｅｓ　ｆｏｒ　Ｂｙｔｅ−ｐｅｒ−Ｃａｒｄ　Ｏｒｇａｎｉｚｅｄ　Ｄｉｇｉｔａｌ　Ｓｙｓｔｅｍｓ’’，　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ，　Ｃ−２７，　Ｎｏ．５，　ｐｐ．４５５−４５９，１９７８およびＣ．Ｌ．Ｃｈｅｎ，‘’Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅｓ　ｗｉｔｈ　Ｂｙｔｅ　Ｅｒｒｏｒ−Ｄｅｔｅｃｔｉｏｎ　Ｃａｐａｂｉｌｉｔｙ’’，　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ，　Ｃ−３２，　Ｎｏ．７，　ｐｐ．６１５−６２１，　１９８３に述べられている。
【０００５】
また、ＳｂＥＣ符号に関しては、Ｓ．Ｊ．Ｈｏｎｇ　ａｎｄ　Ａ．Ｍ．Ｐａｔｅｌ，’’Ａ　Ｇｅｎｅｒａｌ　Ｃｌａｓｓ　ｏｆ　Ｍａｘｉｍａｌ　Ｃｏｄｅｓ　ｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ’’，　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ，　Ｃ−２１，　Ｎｏ．１２，　ｐｐ．１３２２−１３３１，　１９７２およびＥ．Ｆｕｊｉｗａｒａ，’’Ｏｄｄ−Ｗｅｉｇｈｔ−Ｃｏｌｕｍｎ　ｂ−Ａｄｊａｃｅｎｔ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅｓ’’，　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＩＥＣＥ　Ｊａｐａｎ，　Ｅ−６３，　Ｎｏ．１０　，ｐｐ．７８１−７８７，　１９７８に述べられている。
【０００６】
さらに、関連する最近の論文発表として、Ｇ．Ｕｍａｎｅｓａｎ　ａｎｄ　Ｅ．Ｆｕｊｉｗａｒａ，”　Ｒａｎｄｏｍ　Ｄｏｕｂｌｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　−Ｓｉｎｇｌｅ　ｂ−ｂｉｔ　Ｂｙｔｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　（ＤＥＣ−ＳｂＥＣ）　Ｃｏｄｅｓ　ｆｏｒ　Ｍｅｍｏｒｙ　Ｓｙｓｔｅｍｓ”，　ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ，　Ｖｏｌ．Ｅ８５−Ａ，　Ｎｏ．１，　ｐｐ．２７３−２７６，　２００２．，　Ｇ．Ｕｍａｎｅｓａｎ　ａｎｄ　Ｅ．Ｆｕｊｉｗａｒａ，　”　Ａｄｊａｃｅｎｔ　Ｄｏｕｂｌｅ　Ｂｉｔ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅｓ　ｗｉｔｈ　Ｓｉｎｇｌｅ　Ｂｙｔｅ　Ｅｒｒｏｒ　Ｄｅｔｅｃｔｉｎｇ　Ｃａｐａｂｉｌｉｔｙ　ｆｏｒ　Ｍｅｍｏｒｙ　Ｓｙｓｔｅｍｓ”，　ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ，　Ｖｏｌ．Ｅ８５−Ａ，Ｎｏ２．　ｐｐ．４９０−４９６　，　２００２，および　Ｇ．Ｕｍａｎｅｓａｎ　ａｎｄ　Ｅ．Ｆｕｊｉｗａｒａ，“　Ｓｉｎｇｌｅ　Ｂｙｔｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅｓ　ｗｉｔｈ　Ｄｏｕｂｌｅ　Ｂｉｔ　ｗｉｔｈｉｎ　ａ　Ｂｌｏｃｋ　Ｅｒｒｏｒ　ＣｏｒｒｅｃｔｉｎｇＣａｐａｂｉｌｉｔｙ　ｆｏｒ　Ｍｅｍｏｒｙ　Ｓｙｓｔｅｍｓ”，　ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ，　Ｖｏｌ．Ｅ８５−Ａ，　Ｎｏ．２，　ｐｐ．５１３−５１７，　２００２．がある。
【０００７】
【発明が解決しようとする課題】
ところで、最近の高集積半導体メモリ素子（ＤＲＡＭ）には、４ビット、８ビット、１６ビット、３２ビットの読み出し、書き込みデータ幅を有する、いわゆるバイト素子が主流である。ここで、この４ビット、８ビット等のデータの塊がバイトである。このような素子を使用したメモリ装置においては、複数の素子から同時にデータを読み出し、また書き込みを行う。従って、装置全体からの読み出し、書き込みのデータが語（ワード）であり、各素子単位の読み出し、書き込みデータがバイトに相当する。
【０００８】
このような素子を使用したメモリ装置においては、ノイズやアルファ粒子衝突等による一時故障と、素子自身が劣化して動作しなくなる固定故障とが存在する。最近の半導体メモリ素子において、７０％以上の故障は一時故障であるといわれ、この場合バイト中の１、２、３ビット等の比較的小さいビット数の誤りとなる。
【０００９】
一方、固定故障の場合に、１メモリセル故障が生じたときは１ビット誤りとなるが、ワード線故障、アドレス線故障、制御回路故障や電源回路故障等の故障になると、素子の出力ビット全体の誤り、いわゆるバイト誤りとなる。ただし、一般的には、メモリセルに起因する誤りは比較的多いが、上述したような素子全体に影響する故障の発生頻度はきわめて小さい。
【００１０】
上述したような高速半導体メモリ装置においては、特に、周囲の環境による一時故障の影響が大きい。通常、半導体メモリ装置に与える影響としては、ノイズやアルファ粒子等が考えられ、これらの影響は比較的エネルギーレベルの小さい影響であるため、その多くは１ビット誤りとなることが知られている。
【００１１】
しかし、悪い電磁ノイズ環境において使用されるモバイル機器に搭載した半導体メモリ、また、高い高度を飛行する航空機や軍用機における搭載する半導体メモリでは、宇宙線に起因するエネルギーレベルの高い中性子粒子の衝突等によって、２ビット以上の一時的な誤りになる可能性が高い。また、半導体メモリを宇宙機器に搭載した場合に、宇宙空間における極めてエネルギーレベルの高い粒子が衝突することにより、半導体メモリに大きなダメージを与え、２ビット以上の一時的な誤りとなることが知られている。このような場合に、従来の１ビット誤り訂正・１バイト誤り検出の機能（ＳＥＣ−ＳｂＥＤ）では十分ではなく、バイト中の２ビット、３ビット等の１ビットより大きい誤りを訂正する機能が求められる。
【００１２】
本発明は、上述のような事情に鑑みてなされたものであり、本発明の目的は、バイトをｂビットの塊りとするときに、バイト内の１ビット以上ｔビットまでのすべての誤りを訂正する１バイト内ｔビット誤り訂正機能（Ｓｔ／ｂＥＣ）、及びバイト内のｔビットまでのすべての誤りを訂正し、また１バイト中にｔビットより大きい誤りがあればこれを検出するバイト内ｔビット誤り訂正・１バイト誤り検出機能（Ｓｔ／ｂＥＣ−ＳｂＥＤ）と、さらに複数バイトからなるＢビットのブロック中の任意のｔビット誤りを訂正し、ｂビットの１バイト中の任意の誤りを訂正し、更に１ブロック中の任意の誤りを検出するブロック内ｔビット誤り訂正・１バイト誤り訂正・１ブロック誤り検出機能（Ｓｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ）とを有するバイト誤り訂正・検出方法及び装置を提供することにある。
【００１３】
要するに、本発明は、従来技術では存在しない、ｂビットを有するバイト中の２ビット、３ビット等のｔビット（ｔは１以上ｂ以下の整数）までの誤りを訂正する符号機能（Ｓｔ／ｂＥＣ）を与えることにより、従来と比較して、検査ビット数が少なく、また各種要求に柔軟に対応できる符号機能を提供することにある。
【００１４】
【課題を解決するための手段】
本発明は、バイト誤り訂正・検出方法及び装置に関し、本発明の上記目的は、バイト誤り訂正・検出装置については、符号化手段と復号手段とを備えるバイト誤り訂正・検出装置であって、前記符号化手段は、符号を表現するパリティ検査行列Ｈに基き、入力されたＫビットの入力情報データからＲビットの検査ビットを生成してから、前記検査ビットを前記入力情報データに付加して送信語として、情報伝送路に送出されるように構成され、前記情報伝送路を経て受信された前記送信語は、受信語Ｖとして前記復号手段に入力され、前記復号手段は、入力された前記受信語Ｖに前記パリティ検査行列Ｈの転置行列ＨＴを乗算してＲビットのシンドロームＳを生成するシンドローム生成手段と、前記シンドロームＳのパターンに基いて誤りの訂正を行う誤り訂正手段とを有し、誤りが訂正された情報Ｖ＊は出力情報データとして出力され、また、前記符号により訂正できない誤りを検出した場合には、誤り検出出力としてＵＣＥ信号を出力するようにすることにより、あるいは、前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有するようにすることにより、あるいは、前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、更にｔビットを越える１バイトの誤りであれば、これを完全に検出する機能を有するようにすることにより、あるいは、前記パリティ検査行列Ｈは、前記入力情報データが、ｂ（ｂは２以上の整数）ビットを１バイトとし、複数のバイトから構成される語である場合に、複数バイトからなるブロック中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正し、且つ、ｔビットを越える１バイトの誤りを訂正し、更に１バイトを越える１ブロックの誤りであれば、これを完全に検出する機能を有するようにすることにより、あるいは、前記情報伝送路は、情報通信システムであるようにすることにより、あるいは、前記情報伝送路は、メモリシステムであるようにすることにより、あるいは、前記情報伝送路は、バス線回路であるようにすることにより、あるいは、前記誤り訂正手段は、シンドロームデコード手段と、誤り検出手段と、反転手段とを有し、前記シンドローム生成手段にて生成された前記シンドロームＳは、前記シンドロームデコード手段に入力されると共に、前記誤り検出手段にも入力され、前記シンドロームデコード手段は、入力された前記シンドロームＳに基づいて、具体的に誤りのビットを指摘するＫビットのビット誤りポインターを生成し、前記誤り検出手段は、入力された前記シンドロームＳに基づいて、誤りが訂正可能であるか否かを判別し、訂正不可能な誤りであれば、検出して前記ＵＣＥ信号を出力し、前記反転手段は、前記受信語Ｖ中のＫビットからなる情報ビットに対して、前記シンドロームデコード手段から出力されたＫビットの前記ビット誤りポインターを用いて、誤り訂正を行い、誤り訂正された正しい情報Ｖ＊としてＫビットの前記出力情報データを出力するようにすることにより、あるいは、前記誤り検出手段は、Ｒビットの前記シンドロームＳにおいて、少なくともいずれか１ビットが非零であり、且つ、Ｋビットの前記ビット誤りポインターがすべて“０”であるときに、前記受信語Ｖ中にｔビットを越えるバイト誤りを含む訂正不可能な誤りが存在したことを検出し、出力信号である前記ＵＣＥ信号を“１”にするようにすることによって達成される。
【００１５】
また、本発明の上記目的は、バイト誤り訂正・検出方法については、入力情報データに検査ビットが付加された情報語に対するバイト誤り訂正・検出方法であって、符号化回路は、入力された入力情報データに基づいて検査ビットを生成し、生成した前記検査ビットを前記入力情報データに付加して前記情報語として通信路に送出し、前記通信路を経て受信された前記情報語は、受信語Ｖとして復号回路に入力され、前記復号回路では、前記受信語Ｖに符号を表現するパリティ検査行列Ｈの転置行列ＨＴを乗算してシンドロームＳをシンドローム生成回路において生成し、さらに、前記シンドロームＳのパターンに基づいて誤りの訂正を誤り訂正回路において行い、誤りが訂正された情報Ｖ＊は出力情報データとして出力され、また、前記符号により訂正できない誤りを検出した場合には、誤り検出出力としてＵＣＥ信号を出力するようにすることによって達成される。
【００１６】
【発明の実施の形態】
以下、本発明の好適な実施形態について図面を参照しながら詳細に説明する。
【００１７】
図１は、本発明の概略構成を示すブロック図である。図１に示されるように、入力情報データ０１は、符号化回路０２に入力して検査ビットが生成され、この検査ビットは入力情報データ０１に付加される。この入力情報データ０１と検査ビットは送信語として通信路０３に送出される。通信路０３を経て受信された語は受信語Ｖとして復号回路０４に入力する。復号回路０４では、受信語Ｖに符号を表現するパリティ検査行列Ｈの転置行列ＨＴを乗算してシンドロームＳをシンドローム生成回路１において生成し、さらに、このシンドロームＳのパターンに基いて誤りの訂正を誤り訂正回路０５において行う。誤りが訂正された情報Ｖ＊は、出力情報データ０６として出力される。また、符号により訂正できない誤りを検出した場合は、誤り検出出力としてＵＣＥの信号を出力する。
【００１８】
本発明において開示している３種の機能の符号を表現するパリティ検査行列Ｈは、ｂ（ｂは２以上の整数）ビットを１バイトとしたとき、以下のような機能を有する。
【００１９】
［１］１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能。
【００２０】
［２］１バイト中の任意のｔビット誤りを訂正し、さらに、ｔビットを越える１バイトの誤りであれば、これを完全に検出する機能。
【００２１】
［３］複数バイトからなるブロック中の任意のｔビット誤りを訂正し、且つ、ｔビットを越える１バイトの誤りを訂正し、さらに、１バイトを越える１ブロック誤りであれば、これを完全に検出する機能。
【００２２】
要するに、本発明において、バイトをｂビットの塊りとするときに、バイト中のｔビットの誤りを訂正する１バイト内ｔビット誤り訂正（Ｓｔ／ｂＥＣ）符号と、バイト中のｔビット誤りを訂正しｔビットを越える誤りに対してはこれを検出する１バイト内ｔビット誤り訂正・１バイト誤り検出（Ｓｔ／ｂＥＣ−ＳｂＥＤ）符号と、複数バイトからなるＢビットのブロック中の任意のｔビット誤りを訂正し、ｂビットの１バイト中の任意の誤りを訂正し、さらに１ブロック中の任意の誤りを検出するブロック内ｔビット誤り訂正・１バイト誤り訂正・１ブロック誤り検出（Ｓｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ）符号をそれぞれ構成する。
【００２３】
特に、ｔ＝１のときに、本発明のＳｔ／ｂＥＣ符号では、従来の１ビット誤り訂正（ＳＥＣ）符号となり、また、本発明のＳｔ／ｂＥＣ−ＳｂＥＤ符号では、従来の１ビット誤り訂正・１バイト誤り検出（ＳＥＣ−ＳｂＥＤ）符号となる。更に、ｔ＝ｂのときに、双方とも従来の１バイト誤り訂正（ＳｂＥＣ）符号に一致する。
【００２４】
本発明では、任意のｔ（ｔは１以上ｂ以下の整数）およびｂ、Ｂに対して構成できる一般的な符号構成法を提示するとともに、その符号により実際に誤りの訂正・検出ができる方法を示し、またそのための符号化回路および復号回路を提示し誤りが具体的に訂正・検出できることを示す。
【００２５】
一般的に、誤りの訂正・検出を行う符号は、パリティ検査行列Ｈ（Ｈマトリクス、符号マトリクス、または単に検査行列とも言う）により表現される。Ｋビットの情報に対し、Ｒビットの検査ビットを付加してある機能を満足するＮ＝Ｋ＋Ｒビットの長さを有する符号語Ｄ（Ｎビットの行ベクトル）が構成できたときに、符号を規定するＲ行Ｎ列の２元符号マトリクスＨとの間には、Ｄ・ＨＴ＝０の関係が成立する。ここで、ＨＴはマトリクスＨの行と列を入れ替えたマトリクスであり、また、０はＲビットの零列ベクトルである。
【００２６】
（１）符号１
１バイト内ｔビットの誤りを訂正する符号をＳｔ／ｂＥＣ符号（Ｓｉｎｇｌｅ　ｔ−ｂｉｔ　ｗｉｔｈｉｎ　ａ　ｂ−ｂｉｔ　ｂｙｔｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅ）と表記する。ここで、ｔは１≦ｔ≦ｂを満足する整数である。この機能を有する符号のＲ行Ｎ列を有するＨマトリクスＨ１＊を下記の数１により表す。
【００２７】
【数１】
2004007217.tif 000003
ここで、ＩＲはＲ行Ｒ列の単位行列であり、Ｈ’はランクｔ以上のＲ−ｑ行ｂ列の２元マトリクスであり、Ｈ＃は２ｔおよびｂのうちいずれか小さい方の値に等しいか大きいランクを有するｑ行ｂ列の２元マトリクスであり、すなわちＲａｎｋ（Ｈ＃）≧ ｍｉｎ（２ｔ、ｂ）、また、Ｉｑはｑ行ｑ列の単位行列であり、０ｘ×ｙはｘ行ｙ列の零マトリクスであり、ｍ＝２Ｒ−ｑ−２、Ｒ ≧ ｑ＋　ｒとする。γは２を底とするＲ−ｑ次のガロア体ＧＦ（２Ｒ−ｑ）の原始元であり、また、φは加算のもとでＧＦ（２ｒ）をＧＦ（２Ｒ−ｑ）への準同形写像（ｈｏｍｏｍｏｒｐｈｉｓｍ）とするときに、下記の数２が成立する。
【００２８】
【数２】
2004007217.tif 000004
ここで、Ｈ’はランクｔ以上のｒ行ｂ列の２元マトリクスであり、下記の数３に表されるように、ｒ次の列ベクトルｈｊ（０ ≦　ｊ≦　ｂ−１）から構成される。すなわち、Ｈ’は最小距離ｔ＋１を有する（ｂ、ｂ−ｒ）２元線形符号の検査行列であり、ｔビット誤り検出符号のＨマトリクスに等しい。
【００２９】
【数３】
2004007217.tif 000005
また、ｉは０≦ｉ≦ ｍの範囲を有する整数である。ここで、バイトはｂビットの長さを有するが、最後の１バイトはＲ−ｑビットの長さを有する。Ｒ−ｑ　＞ｂでは、ｂビットより大きな値を有するが、例外的にこれも他のバイトと同様に１バイトとして扱うことにする。このとき、最大符号長ＮはＮ　＝ｂ（２Ｒ−ｑ−１）　＋Ｒで表せる。数１に示されたＨマトリクスで表される符号をここでは符号１とする。
次に、数１に示されるこのＨマトリクスで表される符号が具体的に表記の機能（つまり、Ｓｔ／ｂＥＣ符号機能）を有していることを示す。
【００３０】
まず、訂正可能なバイト内ｔビット誤りの集合をＥｔ／ｂとするときに、ｅ１、ｅ２∈Ｅｔ／ｂに対し、下記の数４が成立する。
【００３１】
【数４】
2004007217.tif 000006
ここで、ｅ１およびｅ２はｂビットの２元行ベクトルである。また、ｉ，ｊは互いに異なり、０≦ ｉ、ｊ≦ ｍである。もし、この関係式で等号が成立すると仮定する。このとき、下記の数５及び数６が成立する。
【００３２】
【数５】
2004007217.tif 000007
【数６】
2004007217.tif 000008
まず、数５において、Ｈ＃はＲａｎｋ（Ｈ＃）≧ ｍｉｎ（２ｔ、ｂ）の関係を有することから、ｅ１＝ｅ２ となる。このとき、以下では、ｅ１、ｅ２のうちｅ１を代表して用いることとする。
【００３３】
次に、数６において、Ｒａｎｋ（Ｈ’）≧ ｔより、ｅ１・Ｈ’Ｔ≠０である。これから、下記の数７に表されるようになる。
【００３４】
【数７】
2004007217.tif 000009
従って、数６においてｉ＝ｊが成立することになり、これは矛盾である。よって、上記不等号の関係が成立する。
【００３５】
さらに、検査部の最初のバイト及び２番目のバイトの誤りをそれぞれｅ’∈ ＧＦ（２ｑ）、ｅ” ∈ ＧＦ（２Ｒ−ｑ）とし、それぞれｑビット、Ｒ−ｑビットの２元行ベクトルとするときに、下記の数８、数９及び数１０に表されるような関係が明らかに成立する。
【００３６】
【数８】
2004007217.tif 000010
【数９】
2004007217.tif 000011
【数１０】
2004007217.tif 000012
以上より、数１により表されるＨマトリクスの零空間（ｎｕｌｌ　ｓｐａｃｅ）はＳｔ／ｂＥＣ符号となることが証明された。
【００３７】
（２）符号２
次に、上述したように、検査ビット数Ｒを有する符号１のＨマトリクスＨ１＊に対し、これを使用して構成され、下記の数１１に表されるようなＨマトリクスもやはりＳｔ／ｂＥＣ符号の検査行列となる。
【００３８】
【数１１】
2004007217.tif 000013
ここで、０ｑ×ｑはｑ行ｑ列の零行列であり、またＲ≧　２ｑ＋　ｒであり、ＨＲ−ｑは下記の数１２に表される。
【００３９】
【数１２】
2004007217.tif 000014
ここで、Ｈ＃はｍｉｎ（２ｔ、ｂ）以上のランクを有するｑ行ｂ列の２元マトリクスであり、Ｈ’＃はランクｔ以上のＲ−２ｑ行ｂ列の２元マトリクスであり、δは２を底とするＲ−２ｑ次のガロア体ＧＦ（２Ｒ−２ｑ）の原始元であり、ｍ’＝２Ｒ−２ｑ−２となり、符号の最大長は下記の数１３で表される。
【００４０】
【数１３】
2004007217.tif 000015
数１１に表されるこのマトリクスで表現される符号がＳｔ／ｂＥＣ符号であることは、前述の符号１の構成より容易に証明できる。
【００４１】
まず、前述の符号１から、　［ＨＲ　｜ＩＲ］および　［ＨＲ−ｑ　｜ＩＲ−ｑ］は明らかにＳｔ／ｂＥＣ符号である。ここで、ＩＲ−ｑはＲ−ｑ行Ｒ−ｑ列の単位行列である。前部のＨＲにおける１バイト誤りによるシンドロームとＨＲ−ｑを有する中間部における１バイト誤りによるシンドロームとは、明らかに異なる。これはＨＲの最上部にはｑ行ｑ列の単位行列Ｉｑが存在するのに対し、ＨＲ−ｑを有する部分では最上部にｑ行ｑ列の零行列０ｑ×ｑが存在するためである。また、最後部の検査部における最初のバイトには最上部にｑ行ｑ列の単位行列が存在するが、この部分における１バイト誤りによるシンドロームと、最上部に同様にｂ行ｂ列の単位行列を有する前部ＨＲにおける１バイト誤りによるシンドロームも、前者において残りのＲ−ｑビットのシンドロームがすべて零になることから両者明らかに異なる。数１１に示されるこのＨ１＊＊で表される符号をここでは符号２とする。
【００４２】
（３）符号３
前述の符号２で表されるマトリクス構成のように何回か（ｗ回）階段状に拡張していけば、符号長の優れた符号が得られ、これもＳｔ／ｂＥＣ符号である。ここで、検査長ＲはＲ ≧　ｗｑ＋　ｒであり、ｗは１以上の整数である。下記の数１４に示されたこの符号をここでは符号３とする。
【００４３】
【数１４】
2004007217.tif 000016
ここで、ＨＲ−（ｗ−１）ｑは下記の数１５に表される。
【数１５】
2004007217.tif 000017
ここで、Ｈ＃はｍｉｎ（２ｔ、ｂ）以上のランクを有するｑ行ｂ列の２元マトリクスであり、Ｈ’＊はランクｔ以上のＲ−ｗｑ行ｂ列の２元マトリクスであり、ωは２を底とするＲ−ｗｑ次のガロア体ＧＦ（２Ｒ−ｗｑ）の原始元であり、ｍ’’＝２Ｒ−ｗｑ−２となる。
【００４４】
この構成の符号の最大長はＮ　＝Σｂ（２Ｒ−ｉｑ−１）　＋　Ｒである。ここで、Σはｉ＝　１からｗまでの和である。この符号構成がＳｔ／ｂＥＣ符号の機能を有することは、前述の符号１および符号２の構成から容易に理解できる。
【００４５】
なお、ここで、ｔ　＝　ｂとし、Ｈ’およびＨ＃のランクがともにｂに等しいときに、数１４に示されるマトリクスで表される符号は単一バイト誤り訂正符号、いわゆるＳｂＥＣ符号に一致することに注意する必要がある。しかも、数１４に示されるように、階段状の構成を有するマトリクスで表される符号３においては、従来ＳｂＥＣ符号として最も優れている最大長符号（Ｍａｘｉｍａｌ　Ｃｏｄｅ）に一致する。この最大長符号はＳ．Ｊ．Ｈｏｎｇと　Ａ．Ｍ．Ｐａｔｅｌにより、”Ａ　Ｇｅｎｅｒａｌ　Ｃｌａｓｓ　ｏｆ　Ｍａｘｉｍａｌ　Ｃｏｄｅｓ　ｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ”ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒｓ，　Ｃ−２１，　Ｎｏ．１２，　ｐｐ．１３２２−１３３１，　１９７２に示されている。具体的にランクｂを有するＨ’、Ｈ＃は容易に求められる。すなわち、ｂ行ｂ列の単位行列とすればよい。
【００４６】
（４）符号４
１バイト内ｔビットの誤りを訂正し、ｔビットを超える１バイトの誤りを検出する符号をＳｔ／ｂＥＣ−ＳｂＥＤ符号（Ｓｉｎｇｌｅ　ｔ−ｂｉｔ　ｗｉｔｈｉｎ　ａ　ｂ−ｂｉｔ　ｂｙｔｅ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　ａｎｄ　Ｓｉｎｇｌｅ　ｂ−ｂｉｔ　ｂｙｔｅ　Ｅｒｒｏｒ　Ｄｅｔｅｃｔｉｎｇ　Ｃｏｄｅ）と表記する。この機能を有する符号のＲ行Ｎ列を有するＨマトリクスＨ２＊を下記の数１６により表す。
【００４７】
【数１６】
2004007217.tif 000018
ここで、Ｉｚはｚ行ｚ列の単位行列であり、ＩＲはＲ行Ｒ列の単位行列であり、Ｈ’はランクｔ以上のＲ−ｂ行ｂ列の２元マトリクスであり、また０ｘ×ｙはｘ行ｙ列の零マトリクスであり、ｍ＝２Ｒ−ｂ−２、検査ビット数Ｒ≧　ｂ　＋　ｒとする。γはガロア体ＧＦ（２Ｒ−ｂ）の原始元であり、また、φは加算のもとでＧＦ（２ｒ）をＧＦ（２Ｒ−ｂ）への準同形写像（ｈｏｍｏｍｏｒｐｈｉｓｍ）とするときに、下記の数１７が成立する。
【数１７】
2004007217.tif 000019
ここで、Ｈ’はランクｔ以上のｒ行ｂ列の２元マトリクスであり、前記数３に表されるように、ｒ次の列ベクトルｈｊ（０ ≦　ｊ≦　ｂ−１）から構成される。
【００４８】
また、ｉは０≦ ｉ ≦ ｍの範囲を有する整数である。ここで、バイトはｂビットの長さを有するが、最後の１バイトはＲ−ｂビットの長さを有する。Ｒ＞２ｂではｂビットより大きな値を有するが、例外的にこれも他のバイトと同様に１バイトとして扱うことにする。このとき、最大符号長ＮはＮ　＝ｂ（２Ｒ−ｂ−１）　＋Ｒで表せる。数１６に示されたＨマトリクスで表される符号をここでは符号４とする。
次に、数１６に示されたＨマトリクスで表される符号が具体的に表記の機能を有していることを示す。
【００４９】
まず、訂正可能なバイト内ｔビット誤りの集合をＥｔ／ｂ、およびｔビットを越える１バイト誤りの集合をＥｂとするとき、これらのすべてのいかなる誤りｅ∈｛ Ｅｔ／ｂ ∪ Ｅｂ　｝に対し、ｅＩｂ ≠ ０ｂおよび最後のＲ−ｂビットの検査部の誤りｅＲ−ｂに対しｅＲ−ｂＩＲ−ｂ ≠ ０Ｒ−ｂより、下記の数１８、数１９及び数２０のようになり、これらの誤りに対してシンドロームは、非零となり誤り検出できる。
【００５０】
【数１８】
2004007217.tif 000020
【数１９】
2004007217.tif 000021
【数２０】
2004007217.tif 000022
ここで、ｅはｂビットの２元行ベクトル、ｅＲ−ｂはＲ−ｂビットの２元行ベクトルである。また、０ｂ、０Ｒ−ｂはそれぞれｂ次、Ｒ−ｂ次の２元零行ベクトルである。
【００５１】
次に、訂正可能な誤りである重みｔ以下を有するｂビットの２元行ベクトルｅｔ／ｂ、及びｅ、ｅＲ−ｂに対して、また０≦　ｉ≦ ２Ｒ−ｂ−２に対して、下記の数２１、数２２及び数２３に示された関係は明らかに成立する。
【００５２】
【数２１】
2004007217.tif 000023
【数２２】
2004007217.tif 000024
【数２３】
2004007217.tif 000025
また、０ ≦　ｉ≠　ｊ≦ ２Ｒ−ｂ−２ に対して、下記の数２４が成立する。
【００５３】
【数２４】
2004007217.tif 000026
もし、数２４で等号が成立すると仮定すると、まず 、ｅｔ／ｂ＝ｅが成立しなければならない。また、ｅｔ／ｂはその重みがｔ以下であり、またＨ’のランクはｔ以上であることから、ｅｔ／ｂ・Ｈ’Ｔ ≠ ０となり、よって、下記の数２５が成立する。
【００５４】
【数２５】
2004007217.tif 000027
これから、ｅｔ／ｂ・［γｉＨ’］Ｔ　＝ｅ・［γｊＨ’］Ｔとなり、また、ｅｔ／ｂ　＝　ｅより、これはｉ＝　ｊを意味することになり矛盾である。よって、数２４は成立する。
【００５５】
以上より、数１６に示されたＨマトリクスの零空間（ｎｕｌｌ　ｓｐａｃｅ）はＳｔ／ｂＥＣ−ＳｂＥＤ符号となることが証明された。
【００５６】
（５）符号５
次に、検査ビット数Ｒを有する前記符号４のＨマトリクス中のＨＲを使用して構成した、下記の数２６に示すＨマトリクスもＳｔ／ｂＥＣ−ＳｂＥＤ符号の検査行列となる。
【００５７】
【数２６】
2004007217.tif 000028
ここで、０ｂ×ｂはｂ行ｂ列の零行列であり、またＲ≧ ２ｂ　＋ｒであり、ＨＲ−ｂは下記の数２７により表す。
【００５８】
【数２７】
2004007217.tif 000029
ここで、Ｉｂはｂ行ｂ列の単位行列であり、Ｈ’＃はランクｔ以上のＲ−２ｂ行ｂ列の２元マトリクスであり、δは２を底とするＲ−２ｂ次のガロア体ＧＦ（２Ｒ−２ｂ）の原始元であり、ｍ’＝２Ｒ−２ｂ−２となり、符号の最大長は、下記の数２８で表される。
【００５９】
【数２８】
2004007217.tif 000030
数２６に示されるマトリクスで表現される符号がＳｔ／ｂＥＣ−ＳｂＥＤ符号であることは前記符号４の構成より容易に証明できる。
【００６０】
まず、前述の符号４から［ＨＲ｜ＩＲ］および［ＨＲ−ｂ｜ＩＲ−ｂ］は明らかにＳｔ／ｂＥＣ−ＳｂＥＤ符号である。前部のＨＲにおける１バイト誤りによるシンドロームとＨＲ−ｂを有する中間部における１バイト誤りによるシンドロームとは明らかに異なる。これはＨＲの最上部にはｂ行ｂ列の単位行列Ｉｂが存在するのに対し、ＨＲ−ｂを有する部分では最上部にｂ行ｂ列の零行列０ｂ×ｂが存在するためである。また、最後部の検査部における最初のバイトには最上部にｂ行ｂ列の単位行列が存在するが、この部分における１バイト誤りによるシンドロームと、最上部に同様にｂ行ｂ列の単位行列を有する前部ＨＲにおける１バイト誤りによるシンドロームも、前者において残りのＲ−ｂビットのシンドロームがすべて零になることから両者明らかに異なる。数２６に示されたＨ２＊＊で表される符号をここでは符号５とする。
【００６１】
（６）符号６
前述の符号５で表されるマトリクス構成を前記符号３と同様にｗ回階段状に拡張していけば、下記の数２９に示す符号長の優れた符号が得られ、これもＳｔ／ｂＥＣ−ＳｂＥＤ符号である。ここで、検査長ＲはＲ ≧　ｗｂ＋　ｒであり、ｗは１以上の整数である。この符号をここでは符号６とする。
【００６２】
【数２９】
2004007217.tif 000031
ここで、ＨＲ−（ｗ−１）ｂは下記の数３０に表される。
【数３０】
2004007217.tif 000032
ここで、Ｉｂはｂ行ｂ列の単位行列であり、Ｈ’＊はランクｔ以上のＲ−ｗｂ行ｂ列の２元マトリクスであり、ωは２を底とするＲ−ｗｂ次のガロア体ＧＦ（２Ｒ−ｗｂ）の原始元であり、ｍ’’＝２Ｒ−ｗｂ−２となる。
【００６３】
この構成の符号の最大長はＮ　＝Σｂ（２Ｒ−ｉｂ−１）　＋　Ｒである。ここで、Σはｉ＝　１からｗまでの和である。この符号構成がＳｔ／ｂＥＣ−ＳｂＥＤ符号の機能を有することは、前述した符号４および符号５の構成から容易に理解できる。
【００６４】
なお、ここで、ｔ　＝　ｂとし、Ｈ’のランクがｂに等しいときに、数２９に示すマトリクスで表される符号は、単一バイト誤り訂正符号、いわゆるＳｂＥＣ符号に一致する。しかも、数２９に示すように、階段状の構成を有するマトリクスで表される符号６においては、前記符号３と同様に、従来ＳｂＥＣ符号として最も優れている最大長符号（Ｍａｘｉｍａｌ　Ｃｏｄｅ）に一致する。具体的にランクｂを有するＨ’は容易に求められ、Ｈ’　＝Ｉｂ、すなわちｂ行ｂ列の単位行列とすれば良く、このとき前述のＭａｘｉｍａｌ　Ｃｏｄｅとなる。
【００６５】
（７）符号７
前述の（４）から（６）に示すマトリクス構成を有する符号（符号４、符号５、及び符号６）において、バイト長ｂをさらに大きいブロック長であるＢとみなすとき、すなわち、１ブロックはＢ／ｂ個のバイトから構成されるとき、これらの符号は、ブロック内ｔビットの誤りを訂正し、且つ、ｂビット幅を有する１バイト中の任意の誤りを訂正し、また、Ｂビット幅を有する１ブロック中の任意の誤りを検出する機能を有する符号であるＳｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ符号となる。
【００６６】
このＳｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ符号は、まず、前述した符号４、符号５及び符号６において、ｂをＢに置き換えたＳｔ／ＢＥＣ−ＳＢＥＤ符号にＳｂＥＣの機能を加えた符号に等しい。ここでは、ｔ＜ｂの場合を考える。ｔ≧ｂの場合に、Ｓｔ／ＢＥＣの機能はＳｂＥＣの機能を包含するからである。前述した符号マトリクスの構成において、下記の数３１に示すように、Ｈ’はランクｔ以上を有するｒ行Ｂ列の次に示すマトリクスとする。
【００６７】
【数３１】
2004007217.tif 000033
ここで、Ｂ／ｂ個のｈｉはランクｂを有するそれぞれ異なるｒ行ｂ列の２元部分行列とし、また、ｉ＝０、１、２、…、Ｂ／ｂ−１とする。
【００６８】
このとき、前述した符号４、符号５及び符号６のマトリクス Ｈ２＊、Ｈ２＊＊、Ｈ２＊＊＊ において、数３１で定義したＨ’を与えた符号は、Ｓｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ符号となる。それらの符号を符号７とする。
【００６９】
つまり、符号７がブロック内ｔ（ ＜ ｂ）ビット誤りを訂正し、またブロックが複数個のバイト（ｂビットを有する）で構成されているときに、１バイトの誤りを訂正し、しかも、Ｂビットからなる１ブロック中の任意の誤りを検出する機能を有していることを示す。
【００７０】
ここでは、一例として、符号６で示したマトリクス中Ｈ２＊＊＊中の ＨＲ−ｚｂを対象に証明する。このとき、ｚは０≦ｚ≦　ｗ−１である。今、ブロック中のｔビットの誤りをｅｔ／Ｂとし、一方、ブロック中の任意の誤りをｅＢ、バイト中の任意の誤りをｅｂとするとき、０≦ｉ≠ｊ≦ ２Ｒ−（ｚ＋１）ｂ−２ に対して、下記の数３２及び数３３が成立する。
【００７１】
【数３２】
2004007217.tif 000034
【数３３】
2004007217.tif 000035
ここで、ｅＢ、ｅｔ／ＢはＢビットの２元行ベクトルである。また、０ＢはＢ次の２元零行ベクトルであり、γはＧＦ（２Ｒ−（ｚ＋１）ｂ）における原始元である。
【００７２】
まず、数３２の関係式は自明である。次に、数３３の関係式において、等号が成立したと仮定する。このとき、ｅｔ／ＢＩＢ　＝ｅＢ　ＩＢより、ｅｔ／Ｂ　＝ｅＢとなる。また、ｅｔ／Ｂ・（γｉＨ’）Ｔ　＝ｅＢ・（γｊＨ’）Ｔにおいて、Ｈ’のランクはｔ以上であることからｅｔ／Ｂ・（γｉ Ｈ’）Ｔ≠０となり、よってｉ＝　ｊが成立し、これは矛盾である。よって、数３３の関係式も成立する。数３３の関係式には、ブロック中のｔビット誤りによるシンドロームが他のブロックのブロック誤りによるシンドロームと異なることを意味すると共に、ブロック中のｔビット誤りによるシンドロームが他のブロック中のｔビット誤りによるシンドロームと異なることも意味していることに注意する必要がある。
【００７３】
次に、異なるブロックにそれぞれ生じたバイト誤りとブロック誤りによるシンドロームが互いに異なることを示す必要がある。すなわち、下記の数３４が成立することを示す必要がある。
【００７４】
【数３４】
2004007217.tif 000036
数３４も前述と同様に、等号が成立したと仮定すると、まず、ｅｂ・ＩＢ　＝ｅＢ・ＩＢより、ｅｂ　＝ｅＢが成り立つ。次に、ｅｂ・（γｉ　Ｈ’）Ｔ＝ｅＢ・（γｊ　Ｈ’）Ｔが成立することになるが、Ｈ’を構成するｈｉはそれぞれランクｂを有することから、ｅｂ・（γｉＨ’）Ｔ≠０となり、これからｉ＝ｊが成立し、矛盾となる。よって、数３４の関係も成立することになる。
【００７５】
以上は、符号６で示したマトリクスＨ２＊＊＊中のＨＲ−ｚｂを対象に述べてきたが、他の部分についても、まったく同様に示すことができることは容易に理解できる。以上から、符号７はＳｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ符号となる。
【００７６】
以上のように、符号１から符号７までについて述べてきたが、以下、符号パラメータを与えて具体的に符号が構成できることを示す。
【００７７】
まず、符号１の例として、符号パラメータとしてｔ＝３、ｂ＝８のもとで構成してみよう。この符号は、読み書きデータ幅８ビットを有するメモリ素子を使用したメモリシステムに使用可能である。ここで、検査長ＲをＲ＝１１ビットを与えて構成してみる。これから、Ｈ＃としては、ランク２ｔ　＝　６を有する構成として、最小距離７を有する符号長ｂ　＝　８の符号の検査行列の例として、下記の数３５に示されるようなｑ　＝　７行の行列が構成できる。
【００７８】
【数３５】
2004007217.tif 000037
次に、Ｈ’としては、ｂ　＝８列、Ｒ−ｂ　＝４行を有し、ランクｔ＝３を有する構成として、下記の数３６に示す（８，４）ＳＥＣ−ＤＥＤ（１ビット誤り訂正・２ビット誤り検出）符号の検査行列を使用する。
【００７９】
【数３６】
2004007217.tif 000038
ＳＥＣ−ＤＥＤ符号の構成は多くの符号理論の本、例えば今井秀樹（著）「符号理論」コロナ社（１９９０年刊）に述べられている。ここで、αは３次の２元原始多項式ｐ（ｘ）　＝ｘ３＋　ｘ　＋　１に基づくＧＦ（２３）上の原始元であり、βは４次の２元原始多項式ｐ（ｘ）　＝ｘ４　＋　ｘ　＋　１に基づくＧＦ（２４）上の原始元である。また、符号１における検査行列中のγは４次の２元原始多項式ｐ（ｘ）　＝ｘ４　＋　ｘ　＋　１によるＧＦ（２４）上の原始元であり、βに一致する。このとき、準同形写像φ：ＧＦ（２４）→ＧＦ（２４）は、ＧＦ（２４）上の任意のｘに対しφ（ｘ）　＝ｘにより与えられる。したがって、符号長Ｎ　＝１３１ビット、情報長Ｋ　＝１２０ビットの符号パラメータを有する（１３１，１２０）Ｓ３／８ＥＣ符号のパリティ検査行列は、図２に示すマトリクスにより与えられる。
【００８０】
つまり、図２は、符号１の例として、符号長Ｎ　＝　１３１ビット、情報長Ｋ　＝　１２０ビット、検査長Ｒ　＝　１０ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する（１３１，１２０）Ｓ３／８ＥＣ符号のパリティ検査行列である。
【００８１】
このとき、バイト長として実用的な数値であるｂ＝８のもとで、ｔを２から８まで変化させた場合の符号を示すことにしよう。これには、本符号の構成からわかるように、写像関数φ（ｘ）　＝　ｘを与え、それぞれのｔに対応してｒが決まり、それによるｒ行８列のＨ’を与えておけば、ｒ＝　ｑとしてＨ＃としても使用でき、基本的に任意の符号長を有するＳｔ／８ＥＣ符号が構成できる。
【００８２】
図３には、バイト長ｂ＝８ビットを有するＳｔ／８ＥＣ符号およびＳｔ／８ＥＣ−Ｓ８ＥＤ符号におけるｔ＝　２から８に対する行列Ｈ’を示している。図３に示されるように、ｔ＝　２の場合は、ランク２の行列として１ビット誤り訂正の符号の検査行列を使用すればよいが、このときの符号長８ビットを満足するためには、検査長ｒ＝　４ビットを必要とするため、基本的にｔ＝３の場合の上記Ｈ’と同一の構成となる。また、ｔ＝８では、本符号の機能から単一バイト（バイト＝８ビット）誤り訂正符号であるＳ８ＥＣ符号となる。Ｈ’としてランクｔ＝８を有する８行８列の単位行列を採用すれば、これは従来のＳ８ＥＣ符号の構成に完全に一致する。
【００８３】
次に、このＳｔ／８ＥＣ符号において、これらのＨ’を使用して符号を構成したときに、実用的な情報長Ｋ＝　６４ビットに対して検査長がどのくらい必要かをみてみよう。ｔ＝２およびｔ＝３の場合に、検査長Ｒは１１ビットで、ｔ＝４では１３ビットで、ｔ＝５、６、７では、１４ビットで、ｔ　＝　８ビットでは、１５ビットで実現できる。
【００８４】
ただし、例えば、ｔ＝２またはｔ＝３のときに、検査長が１１ビットでは情報長Ｋの最大は１２０ビットであるため、Ｋ＝１２１ビット以上の場合にはこのＨ’を用いて符号が構成できない。そこで、さらに検査ビットを１ビット増加させ、Ｒ＝１２ビットとして構成することを考えなければならない。このとき、この基本のＨ’の最下位にすべて“０”の１行を加えた、下記の数３７に示す５行８列のＨ’を用いる。
【００８５】
【数３７】
2004007217.tif 000039
このように、すべて“０”の行を追加してＨ’の行数ｒをＲ−ｂに一致させておけば、加算のもとでの準同形写像がφ（ｘ）　＝　ｘとすることができ、γｉＨ’が矛盾なく容易に構成できる。しかし、この修正したＨ’を使用しても、Ｋ＝２４８ビットまでは、符号を構成することが可能であるが、これを越えるＫに対しては構成できない。その場合には、同様にさらに１行すべて“０”の行を加えて新たなＨ’として、これを使用して符号を構成すればよい。このように、Ｈ’にすべて“０”の行を追加して符号の検査行列の行を増やしていけば、すなわち検査長を増加していけば、任意のＫに対して符号が構成できる。これは、他のｔに対してもまったく同様の議論が成立することは明らかである。
【００８６】
一般的には、本発明に開示している符号の構成においては、このように、すべて“０”の行を追加し、ｒ＝Ｒ−ｂとすることにより、容易に符号を拡張できる。これは以下に示すＳｔ／ｂＥＣ−ＳｂＥＤ符号の構成において用いるＨ’にも当然使用できる。
【００８７】
次に、Ｓｔ／ｂＥＣ−ＳｂＥＤ符号に関し、いくつかの符号例を示す。符号４の例として、符号パラメータとしてｔ＝３、ｂ＝８のもとで構成してみよう。ここで、検査長ＲをＲ＝１２ビットを与えて構成してみる。これから、Ｈ’としてはｂ　＝　８列、Ｒ−ｂ　＝４行を有しランクｔ　＝３を有する構成として、数３６に示した（８，４）ＳＥＣ−ＤＥＤ（１ビット誤り訂正・２ビット誤り検出）符号の検査行列を使用する。これは図３におけるｔ＝３の場合のＨ’に等しい。
【００８８】
また、γは４次の２元原始多項式ｐ（ｘ）　＝ｘ４　＋ｘ　＋　１によるＧＦ（２４）上の原始元でありβに一致する。このとき、準同形写像φ：ＧＦ（２４）→ＧＦ（２４）はＧＦ（２４）上の任意のｘに対しφ（ｘ）　＝　ｘにより与えられる。したがって、Ｓ３／８ＥＣ符号の検査行列は、下記の数３８に示すマトリクスにより与えられる。
【００８９】
【数３８】
2004007217.tif 000040
ここで、ｉ＝　０，１，２，・・・，１４に対し、γｉＨ’＝　［βｉ　βｉ＋４　βｉ＋８　βｉ＋１４　βｉ＋１０　βｉ＋１３　βｉ＋１２　βｉ＋７　］である。この符号は、符号長ＮはＮ＝８×（２４−１）＋１２＝１３２ビットであり、情報長ＫはＫ＝１３２−１２＝１２０ビットのパラメータを有する。
【００９０】
図４は、符号４の例として、符号長Ｎ＝７６ビット、情報長Ｋ＝６４ビット、検査長Ｒ＝１２ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する短縮（７６、６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号のパリティ検査行列である。図４には、２元で表したこの符号の検査行列を示している。特に、この符号は、情報ビット数が６４ビットとなるように前記数３８に示す符号の検査行列を２元で表した情報長Ｋ＝１２０ビットを有する行列から情報部の後半５６列を削除したものである。したがって、この行列は８ビット入出力を有するメモリ素子を使用し６４ビットの読み書き幅を有するメモリシステムに応用可能な実用性の高い（７６，６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号の検査行列を表している。
【００９１】
次に、検査行列が階段状の構成を有する符号５（符号６でｗ＝２の構成を有する符号に等しい）の簡単な例として、ｔ　＝　２，　ｂ　＝　３の場合を示そう。Ｒ　＝　８とすると、下記の数３９に示す２段構成の符号となり、Ｈ８と Ｈ５および　Ｉ８（８行８列の単位行列）から構成される。
【００９２】
【数３９】
2004007217.tif 000041
ここで、Ｈ８、Ｈ５は具体的に下記の数４０及び数４１に示すマトリクスである。
【００９３】
【数４０】
2004007217.tif 000042
【数４１】
2004007217.tif 000043
ここで、γはＧＦ（２５）上の原始元であり、５次の２元原始多項式ｐ（ｘ）　＝ｘ５　＋ｘ２　＋　１の根で規定され、また、Ｈ’はランク２である符号長３を有する１ビット誤り訂正符号の検査行列を採用する。すなわち、例えば、下記の数４２に示すように、相異なる２次の２元列ベクトルを３列並べる。
【００９４】
【数４２】
2004007217.tif 000044
ここで、αは原始多項式ｐ（ｘ）　＝ｘ２＋ｘ＋　１の根（原始元）であり、Ｈ’はこのべき乗を列ベクトル表現したものである。このとき、準同形写像関数φ： ＧＦ（２２）→ＧＦ（２５）より、具体的に、φ（α０）　＝γ０ 、φ（α１）＝γ１、φ（α２）＝φ（α＋１）＝φ（α１）＋φ（α０）＝γ０＋γ１＝γ１８、したがって、例えば、γ０Ｈ’は下記の数４３に示すようになる。【数４３】
2004007217.tif 000045
これは、前に述べた方法でも構成できる。すなわち、Ｈ’にすべて“０”の行を３行追加して修正したＨ’とし、これを新たなＨ’とすれば、数４３で求めたγ０Ｈ’に一致する。
【００９５】
次に、δはＧＦ（２２）上の原始元であり、ｐ（ｘ）　＝ｘ２＋ｘ＋　１で規定され、Ｈ＃’は、同様にランク２を有する２行３列の行列として、１ビット誤り訂正符号の検査行列を使用し、下記の数４４を得る。
【００９６】
【数４４】
2004007217.tif 000046
ここで、ρは同様に原始多項式ｐ（ｘ）　＝ｘ２＋ｘ＋　１の根であり、準同形写像φ：ＧＦ（２２）→ＧＦ（２２）より、φ（ｘ）　＝　ｘとし、Ｈ＃’はこの元のべき乗要素を列ベクトル表現したものである。符号は２段階の構成例であり、符号長ＮはＮ＝　３×（２５−１）　＋　３×（２２−１）　＋　８　＝　１１０ビット、情報長ＫはＫ＝　１１０−８　＝　１０２ビット、および検査長ＲはＲ＝　８ビットである。この符号を２元情報で表した（１１０，１０２）Ｓ２／３ＥＣ−Ｓ３ＥＤ符号を図５に示す。
【００９７】
つまり、図５は、符号５または符号６の例として、符号長Ｎ＝１１０ビット、情報長Ｋ＝１０２ビット、検査長Ｒ＝８ビット、バイト長ｂ＝３ビット、バイト内訂正ビット長ｔ＝２ビットの符号パラメータを有するｗ＝２段階構成の（１１０，１０２）Ｓ２／３ＥＣ−Ｓ３ＥＤ符号のパリティ検査行列である。
【００９８】
次に、符号７の例として、ｔ＝３、ｂ＝４、Ｂ＝８の符号パラメータを有するＳ３／８ＥＣ−Ｓ４ＥＣ−Ｓ８ＥＤ符号を示そう。実は、これは前述の符号６の例をそのまま使用すれば実現できる。すなわち、Ｈ’として前述の符号４の例と同じものを使用する。これは、下記の数４５に示すように、それぞれ前半４ビットと後半４ビットの部分行列Ｈ０とＨ１ではそれぞれランクｂ　＝　４を満足しているためである。
【００９９】
【数４５】
2004007217.tif 000047
この性質は、図３で示したｔ　＝　２から８に対して示したそれぞれのＨ’においても、それぞれ前半４ビット、後半４ビットに分けてＨ０、Ｈ１とすれば、成立する。これから、ｂをＢに置き換え、Ｂ＝８ビットとした場合に対して与えた図３のＨ’を使用して構成した符号は、自動的にＳｔ／８ＥＣ−Ｓ４ＥＣ−Ｓ８ＥＤ符号となる。
【０１００】
次に、符号化と復号の具体的方法とその回路を示そう。まず、符号化回路０２は入力情報Ｄと符号マトリクス中の情報部であるＨＲを用いて検査情報Ｃを生成する。検査情報Ｃの生成は、下記の数４６により求めることができる。
【０１０１】
【数４６】
2004007217.tif 000048
本発明に開示している符号のうち、Ｓ３／８ＥＣ−Ｓ８ＥＤ符号である符号４を例に明示することにする。符号４の検査行列は、前述のとおり基本的に、下記の数４７に示す構成を有する。
【０１０２】
【数４７】
2004007217.tif 000049
ここで、ｍ＝２ｒ−２である。符号化回路０２は入力情報データ０１よりｃ０、ｃ１、・・・、ｃＲ−１のＲビットの検査ビットを生成する回路である。
【０１０３】
具体的に、図４に示すＧＦ（２）上で表現した符号化マトリクスを用いて検査情報を求めてみよう。たとえば、検査ビットｃ０を求めるためには、マトリクス中のＨＲの第１行目において“１”の存在する個所に対応する入力情報の排他的論理和（２を法とする和）をとっていけばよい。例えば、検査ビットｃ０はｄ０、ｄ８、ｄ１６、ｄ２４、ｄ３２、ｄ４０、ｄ４８、ｄ５６からなる８ビットの入力情報に対して２を法とする和を求めればよい。
【０１０４】
他の検査ビットも同様にして求めればよく、このための回路を図６に示す。つまり、図６は、図４に示す　（７６，６４）　Ｓ３／８ＥＣ−Ｓ８ＥＤ符号をもとに具体的に構成した符号化回路であり、Ｋ　＝６４ビットの入力情報Ｄから符号マトリクスにより１２ビットの検査情報を生成する回路である。なお、図中の５は多入力パリティ検査回路である。この入力語Ｄに生成した検査情報Ｃを付加して、すなわち、［Ｄ｜Ｃ］が送信語となる。
【０１０５】
次に、誤りが生じたときに、図４に示す符号を用いて具体的に訂正、検出できることを示す。図４において、検査行列の上段より得られるｂビットのシンドロームをＳＩとし、下段より得られるｒビットのシンドロームをＳＩＩとする。Ｎビットから構成される受信語をＶとするときに、シンドロームＳは、下記の数４８により求まる。
【０１０６】
【数４８】
2004007217.tif 000050
ここで、ＳＩ∈ ＧＦ（２ｂ）、ＳＩＩ∈ ＧＦ（２ｒ）であり、ＳＩはｂビットの行ベクトルで、ＳＩＩはｒビットの行ベクトルである。このとき、復号は次のように行われる。
【０１０７】
＜１＞　ＳＩ　＝０、ＳＩＩ　＝０のとき：誤りなしと判定する。
【０１０８】
＜２＞　ＳＩ　＝０、ＳＩＩ　≠０のとき：最後の検査バイトに誤りありと判定する。誤りパターンはＳＩＩにより与えられ、これを用いて訂正する。
【０１０９】
＜３＞　ＳＩ≠０、ＳＩＩ　＝０のとき：最初の検査バイトに誤りありと判定する。誤りパターンはＳＩにより与えられ、これを用いて訂正する。
【０１１０】
＜４＞　ＳＩ≠０、ＳＩＩ≠０のとき：誤りパターンはＳＩにより与えられる。誤りの位置は、ＳＩ・［γｉＨ’］Ｔについて、ｉ＝０、１、 ２、…、２ｒ−２のすべての情報部のバイトに対して独立に並列に計算し、ＳＩ・［γｊＨ’］Ｔ　＝ＳＩＩの関係が成立するｊバイト目に誤りがあると判定し（他のバイトではこの関係は成立しない）、誤りパターンＳＩを用いて訂正する。
【０１１１】
上記の復号方法は、符号４から符号６までに示したＳｔ／ｂＥＣ−ＳｂＥＤ符号において適用できるだけではなく、符号１から符号３までのＳｔ／ｂＥＣ符号においても、また、ｂをＢに置き換えた符号７であるＳｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ符号においても適用できる。すなわち、Ｓｔ／ＢＥＣ−ＳｂＥＤ−ＳＢＥＤ符号において、上記の復号方法では、バイトをブロックとみなし、訂正可能なブロック中のｔビット誤りだけではなく、バイト誤りもブロック中の誤りとみなし、誤りパターンを示すＳＩを用いて（最後の検査バイトではＳＩＩを用いて）訂正すればよい。
【０１１２】
次に、上記復号方法を用いて、受信語中の１バイトに生じた任意のｔビットまでの誤りを訂正し、また１バイト中でｔビットを越える誤りがあればすべて検出する具体的な復号回路０４の構成を示す。この復号回路０４の回路全体のブロック図を図７に示す。
【０１１３】
つまり、図７は、本発明で開示された機能を有する符号の復号回路のブロック回路である。図７において、１はシンドローム生成回路で、２はシンドロームデコード回路で、３は誤り検出回路で、４は反転回路で、Ｖは受信語で、Ｓはシンドロームで、Ｖ＊は訂正後の受信語で、ＵＣＥは訂正不可能誤り検出信号である。
【０１１４】
図７に示されるように、Ｎビットからなる受信語Ｖが入力されると、まず、シンドローム生成回路１にて、ＲビットのシンドロームＳを生成する。このシンドロームＳは、シンドロームデコード回路２に入力し、具体的に誤りのビットを指摘するＫビットのビット誤りポインター（ｅ０〜ｅＫ−１）を生成する。一方、シンドロームＳとシンドロームデコード回路２において作成される┌Ｎ／ｂ┐（┌ｘ┐はｘを越える最小の整数）本のバイト誤りポインタ（Ｅ０、Ｅ１、…、Ｅ┌Ｎ／ｂ┐−１）は、誤り検出回路３に入力し、誤りが訂正可能であるか否かを判別し、訂正不可能な誤りであれば、検出してＵＣＥ（Ｕｎｃｏｒｒｅｃｔａｂｌｅ　Ｅｒｒｏｒ）信号を出力する。このＵＣＥ信号が“１”であれば、訂正不可能な誤りを検出したことを示す。
【０１１５】
また、回路４は誤り反転回路であり、受信語中のＫビットからなる情報ビットに対して、シンドロームデコード回路２から出力したＫビットのビット誤りポインターを用いて、誤り訂正を行う回路である。この誤り反転回路４からは、誤り訂正された正しい情報語Ｖ＊としてＫビットの出力情報データ０６が出力する。ここで、シンドロームデコード回路２、誤り検出回路３、反転回路４からなる回路を誤り訂正回路０５と称する。
【０１１６】
各回路の構成を具体的に図４に示す符号４を用いて説明する。
【０１１７】
まず、シンドローム生成回路１は、Ｎ＝７６ビットからなる受信語Ｖを、下記の数４９に示されるように表したときに、この受信語Ｖを入力して、下記の数５０に示されるようなＳ０、Ｓ１、・・・、Ｓ１１からなるＲ＝１２ビットのシンドロームを生成する。
【０１１８】
【数４９】
2004007217.tif 000051
【数５０】
2004007217.tif 000052
検査行列の各列は入力する情報に対応しており、第０列は入力情報のｄ０に対応し、また、検査行列の最後の単位行列は入力情報の検査部に対応し、この部分における最初の列は検査情報のｃ０に対応する。各シンドロームビットは符号の検査行列において各行方向に“１”を有するビットに対応する受信情報をすべてＧＦ（２）上で加算する。すなわち、対応する受信情報をすべて多入力パリティ検査回路５に入力する。
【０１１９】
このようにして各シンドロームビットを作成する回路を図８に示す。つまり、図８は、図４に示す　（７６，６４）　Ｓ３／８ＥＣ−Ｓ８ＥＤ符号をもとに具体的に構成したシンドローム生成回路１である。図中の５は多入力パリティ検査回路である。このシンドローム生成回路１の構成は、前に示した検査情報を生成した符号化回路０２の構成とほぼ同様である。検査ビットの生成とシンドロームの生成の唯一の違いは、後者において、受信データ情報と受信検査情報から生成するのに対し、前者は入力データ情報のみから生成する点である。
【０１２０】
例えば、シンドロームビット９（Ｓ９）を作成するには、検査行列の第９行目において、“１”の対応する受信情報ｄ１’、ｄ４’、ｄ６’、ｄ７’、ｄ８’、ｄ９’、ｄ１０’、ｄ１２’、ｄ１８’、ｄ１９’、ｄ２０’、ｄ２３’、ｄ２５’、ｄ２６’、ｄ２９’、ｄ３１’、ｄ３２’、ｄ３４’、ｄ３８’、ｄ３９’、ｄ４０’、ｄ４１’、ｄ４３’、ｄ４７’、ｄ４９’、ｄ５１’、ｄ５２’、ｄ５３’、ｄ５６’、ｄ５７’、ｄ６１’、ｄ６２’、ｃ９’からなる３３ビットの入力情報（受信検査ビットｃ９’を含む）に対して、２を法とする和を求めればよく、この３３ビットの入力を多入力パリティ検査回路５に入力して求める。
【０１２１】
次に、シンドロームデコード回路２について説明する。
【０１２２】
このシンドロームデコード回路２は、大きく分けて、誤りがどのバイトに生じたかを示す「バイト誤りポインター生成回路」６（各バイトに対応して、それぞれ６−０、６−１、・・・、６−７、および６−ｐ０、６−ｐ１からなる）と、そのポインターからバイト内のどのビットが誤りかを指摘する「バイト内ビット誤りポインター生成回路」７（情報部のバイトに対応して７−０、７−１、・・・、７−７からなる）とからなる。
【０１２３】
バイト誤りポインター生成回路６は、検査部も含めてそれぞれのバイトごとに用意し、また、バイト内ビット誤りポインター生成回路７も、情報部の各バイトごとに用意する。これらの回路は並列に動作し、最終的にシンドロームデコード回路２において、Ｋ＝６４ビットのビット誤りポインターを出力する。符号として当然検査部の誤りも訂正できるが、一般に検査部の情報は復号回路の後において使用しないことから、ここでは検査部に誤りがあっても訂正せず、復号回路からは検査情報は出力しないこととする。
【０１２４】
図９は、図４に示す符号に対するシンドロームデコード回路２のブロック図である。図９において、６−０から６−７は情報バイト０から情報バイト７に対するバイト誤りポインター生成回路であり、６−ｐ０、６−ｐ１は検査バイト０と検査バイト１に対するそれぞれのバイト誤りポインター生成回路である。また、７−０から７−７は情報バイト０から情報バイト７に対するそれぞれのバイト内ビット誤りポインター生成回路である。ＳＩはシンドロームＳの上位８ビットで、ＳＩＩはシンドロームＳの下位４ビットで、Ｅ０からＥ７はそれぞれのバイトに対するバイト誤りポインターで、Ｅ−ｐ０、Ｅ−ｐ１はそれぞれ検査バイト０、１に対するバイト誤りポインターで、Ｅｂ０からＥｂ７はそれぞれ情報バイト０から情報バイト７に対するバイト内ビット誤りポインターである。
【０１２５】
図９に示されるように、Ｒ＝１２ビットのシンドロームＳは、バイト誤りポインター生成回路６全体に並列に入力し、一方、シンドロームＳの内に８ビットからなるＳＩは、誤りパターンを表示することから、８個のバイト内ビット誤りポインター生成回路７に入力する。このとき、それぞれ相当するバイトのバイト誤りポインター生成回路６からの出力であるバイト誤りポインターもそれぞれのバイト内ビット誤りポインター生成回路７に入力する。
【０１２６】
次に、バイト誤りポインター生成回路６の具体的な回路構成の例を示そう。図１０は、図４に示す符号に対する情報バイト１におけるバイト１誤りポインター生成回路６−１を示す。図中の８はＮＯＲ回路で、Ｅ１はバイト１誤りポインターである。入力のシンドロームＳＩとＳＩＩから、下記の数５１が成立するときに、バイト１誤りポインターＥ１が“１”となる。
【数５１】
2004007217.tif 000053
具体的には、下記の数５２、数５３、数５４及び数５５に示す関係がすべて成立するときに、Ｅ１は“１”となる。
【０１２７】
【数５２】
2004007217.tif 000054
【数５３】
2004007217.tif 000055
【数５４】
2004007217.tif 000056
【数５５】
2004007217.tif 000057
ここで、上記数５２、数５３、数５４及び数５５にある、プラス記号を丸印で囲った記号は、２を法とする和（すなわちＧＦ（２）上の和）を示し、上記左辺の和を多入力パリティ検査回路５に入力し、その出力と上記右辺のシンドロームビットとの２を法とする和をとり、この結果が“０”であれば、上記関係が成立することを示す。回路の構成として、上記関係は左辺と右辺のすべてを多入力パリティ検査回路５に入力することと同一である。さらに、この結果の４出力を回路８のＮＯＲゲートに入力することにより、上記関係がすべて成立するとき“１”の出力を与えるバイト１誤りポインターＥ１となる。他のバイト誤りポインター生成もまったく同一の考えで構成できる。
【０１２８】
次に、バイト内ビット誤りポインター生成回路７の構成について述べる。このバイト内ビット誤りポインター生成回路７は、情報バイト８バイトに対してそれぞれ同一の回路で構成でき、ここでは、例として、バイト１に対する回路７−１を図１１に示す。つまり、図１１は、図４に示す符号に対する情報バイト１のバイト１内ビット誤りポインター生成回路７−１である。なお、図中のｅ８からｅ１５は情報バイト１内のビット８から１５に対するそれぞれのビット誤りポインターである。
【０１２９】
図１１に示されるように、バイト１の誤りを示すバイト１誤りポインターＥ１を用い、さらにバイト中のどのビットが誤りであるかを示す誤りパターンは具体的にシンドロームＳ中の上位のＳＩにより与えられることから、８ビットからなるＳＩの各ビットとＥ１との論理積をとるＡＮＤゲート１０をビット対応に８個設ければよい。このＡＮＤゲート１０の出力が“１”であることは、具体的にバイト１中の当該ビットが誤りであることを示す。バイト１における回路の出力信号は、ｅ８、ｅ９、・・・、ｅ１５である。
【０１３０】
次に、誤り検出回路３について述べる。この誤り検出回路３は、入力情報Ｖ中にｔビットを越えるバイト誤りを含む訂正不可能な誤り（Ｕｎｃｏｒｒｅｃｔａｂｌｅ　Ｅｒｒｏｒ）を検出し、その出力信号であるＵＣＥ信号が“１”のとき、このような訂正不可能な誤りを検出したことを示す。このための論理は次のように考えればよい。
【０１３１】
すなわち、シンドロームが非零（すなわち、符号により訂正可能な誤りを含むなんらかの誤りを検出したことを示す）であり、且つ、回路６−０、６−１、・・・、６−ｐ１からのバイト誤りポインターがすべて“０”である（すなわち、すべてのバイトにおいて訂正できる誤りはないことを示す）ときに、訂正不可能な誤りが存在したとして検出する。
【０１３２】
この論理を構成した回路が図１２である。つまり、図１２は、図４に示す符号に対する誤り検出回路３である。なお、図中の９はＯＲ回路で、１０はＡＮＤ回路である。図１２に示されるように、誤り検出回路３は、１２ビットのシンドロームが入力するＯＲゲート９（シンドロームが非零であるときに“１”を出力）と、情報部の８本のバイト誤りポインターＥ０、Ｅ１、・・・、Ｅ７及び検査部の２本のバイト誤りポインターＥｐ０、Ｅｐ１の計１０個のポインターが入力するＮＯＲゲート８（すべてのポインターが零のときに“１”を出力）と、ゲート回路９とゲート回路８の出力の論理積をとるＡＮＤゲート１０とから構成される。このゲート回路１０からの出力信号がＵＣＥ信号であり、“１”のときに、訂正不可能な誤りを検出したことを示す。
【０１３３】
次に、反転回路４の構成について述べる。この反転回路４は、具体的に誤りがあると指摘された入力ビットについてデータの反転を行い訂正する回路である。Ｋビットからなる情報部に対し各入力ビットに誤りが存在するか否かを示すビット誤りポインターは、バイト内ビット誤りポインター生成回路７において生成され、これを用いて反転回路４を構成すればよい。
【０１３４】
バイト１に対して具体的に構成した回路を図１３に示す。つまり、図１３は情報バイト１に対する反転回路４である。なお、図中の１１は排他的論理和回路で、ｄ’８からｄ’１５は受信語中のバイト１の８入力ビットで、ｄ＊８から　ｄ＊１５はバイト１における各８ビットの訂正出力ビットである。
【０１３５】
すなわち、バイト１の入力ビットｄ８’、ｄ９’、・・・、ｄ１５’のそれぞれに対し、対応するビット誤りポインターとの排他的論理和をとることにより構成できる。つまり、ビット誤りポインターが“１”のときに、入力データビットは反転され訂正される。なお、図１３において、１１は排他的論理和ゲートであり、バイト１に対してはこのゲート８個で構成できるが、すべての情報部入力Ｋ＝６４ビットに対してはＫ個のゲート１１が必要になる。
【０１３６】
上述したように、本発明では、バイト中のｔビットまでの誤りを訂正し、１バイトの誤りを検出する符号機能、等に対して一般性のある符号構成を与え、具体的に誤りの訂正・検出が実現できる回路である復号回路構成を示し、誤りが具体的に訂正・検出できることを示している。
【０１３７】
また、以上は、主としてメモリ装置に着目して本発明の適用を述べたが、本発明は、それに限定されるものではなく、例えば、このようなバイトやブロック等の物理的に独立した回路、モジュール、装置から構成される一般の情報通信システムまたは装置にも適用可能であり、また、バス線回路等の伝送回路や装置にも適用可能である。
【０１３８】
【発明の効果】
本発明に係るバイト誤り訂正・検出方法及び装置によれば、従来技術では存在しない、バイト中の２ビット、３ビット等のｔビットまでの誤り（ｂビットまでの誤りではない）を訂正する符号機能（Ｓｔ／ｂＥＣ）を与えることにより、従来と比較して、検査ビット数の少ないまた各種要求に柔軟に対応できる符号機能を提供できるという優れた効果を奏する。
【０１３９】
また、本発明で開示している符号は、さらに拡張した機能も併せ持っており、最近の高集積半導体メモリ素子を使用したメモリシステムに実用的である。すなわち、メモリ素子内の構成を見ると、通常その中はサブアレーに分割されており、これらは独立に構成され、また、実際の動作も独立である。そのため、ビット幅の大きい、たとえば１６ビット幅のデータ読み書きを行うメモリ素子では、そのチップの中には、４ビットのサブアレーが４個で構成されている場合が多い。従って、このサブアレーからのビット幅を新たにバイト（例えば、４ビット）とし、さらに素子の読み書き幅をブロック（例えば、１６ビット）とすると、本発明で開示しているＳｔ／ｂＥＣ−ＳｂＥＤ機能を有する符号は、バイトをブロックに置き換えることにより、ブロック中の任意のｔビットまでの誤りを訂正し、また１サブアレーの誤りであるｂビットまでの誤りを訂正し、さらに大きなブロックまでの誤りを検出できるＳｔ／ＢＥＣ−ＳｂＥＣ−ＳＢＥＤ機能を有する符号となることができる。
【０１４０】
さらに、本発明によれば、例えば、１バイト中の任意の２ビット（ｔ＝２）誤りを訂正し、さらにバイト中の３ビットより大きい任意の誤り、いわゆる１バイト誤りを検出するバイト内２ビット誤り訂正・１バイト誤り検出の機能（Ｓ２／ｂＥＣ−ＳｂＥＤ）を有する符号は従来存在せず、このような要求に応えることができるという効果を奏する。さらに、ｔをｂより小さい整数とするとき、ｔ＝ｂとする１バイト誤り訂正の機能を有する符号と比較して、より少ない符号検査ビット数で実現できることになり、経済的に誤り訂正・検出装置が実現できるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の概略構成を示すブロック図である。
【図２】符号１の例として、符号長Ｎ　＝１３１ビット、情報長Ｋ　＝１２０ビット、検査長Ｒ　＝１０ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する（１３１，１２０）Ｓ３／８ＥＣ符号のパリティ検査行列を示す図である。
【図３】バイト長ｂ＝８ビットを有するＳｔ／８ＥＣ符号およびＳｔ／８ＥＣ−Ｓ８ＥＤ符号におけるｔ＝２から８に対する行列Ｈ’を示す図である。
【図４】符号４の例として、符号長Ｎ＝７６ビット、情報長Ｋ＝６４ビット、検査長Ｒ＝１２ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する短縮（７６，６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号のパリティ検査行列を示す図である。
【図５】符号５または符号６の例として、符号長Ｎ＝１１０ビット、情報長Ｋ＝１０２ビット、検査長Ｒ＝８ビット、バイト長ｂ＝３ビット、バイト内訂正ビット長ｔ＝２ビットの符号パラメータを有する２段階構成の（１１０，１０２）Ｓ２／３ＥＣ−Ｓ３ＥＤ符号のパリティ検査行列を示す図である。
【図６】図４に示す（７６，６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号をもとに具体的に構成した符号化回路であり、Ｋ　＝　６４ビットの入力情報Ｄから符号マトリクスにより１２ビットの検査情報を生成する回路である。
【図７】本発明で開示された機能を有する符号の復号回路のブロック回路である。
【図８】図４に示す（７６，６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号をもとに具体的に構成したシンドローム生成回路である。
【図９】図４に示す（７６，６４）Ｓ３／８ＥＣ−Ｓ８ＥＤ符号に対するシンドロームデコード回路のブロック図である。
【図１０】図４に示す符号に対する情報バイト１のバイト１誤りポインター生成回路である。
【図１１】図４に示す符号に対する情報バイト１のバイト１内ビット誤りポインター生成回路である。
【図１２】図４に示す符号に対する誤り検出回路である。
【図１３】情報バイト１に対する反転回路である。
【符号の説明】
０１　入力情報データ
０２　符号化回路
０３　通信路
０４　復号回路
０５　誤り訂正回路
０６　出力情報データ
１　　シンドローム生成回路
２　　シンドロームデコード回路
３　　誤り検出回路
４　　反転回路
５　　多入力パリティ検査回路
６　　バイト誤りポインター生成回路
７　　バイト内ビット誤りポインター生成回路
８　　ＮＯＲ回路
９　　ＯＲ回路
１０　ＡＮＤ回路
１１　排他的論理和回路
Ｃ　　検査情報
ｃ０〜ｃ１１　検査情報ビット
Ｄ　　入力情報
Ｓ、ＳＩ、ＳＩＩ　　シンドローム
ＵＣＥ　誤り検出出力
Ｖ　　　受信語
Ｖ＊　　訂正された情報語
【図１】
2004007217.tif 000074
【図２】
2004007217.tif 000075
【図３】
2004007217.tif 000076
【図４】
2004007217.tif 000077
【図５】
2004007217.tif 000078
【図６】
2004007217.tif 000079
【図７】
2004007217.tif 000080
【図８】
2004007217.tif 000081
【図９】
2004007217.tif 000082
【図１０】
2004007217.tif 000083
【図１１】
2004007217.tif 000084
【図１２】
2004007217.tif 000085
【図１３】
2004007217.tif 000086