(57)【要約】【課題】  ディジタルデータの誤り訂正・検出において、１バイトのスポッティバイト誤りを訂正するとともに、２バイトにまたがる２スポッティバイト誤りを検出する機能を有する誤り訂正・検出装置及び誤り訂正・検出方法を提供する。【解決手段】  入力情報データ３０に対して、符号を表現するパリティ検査行列Ｈと入力情報データ３０とを基に生成した検査情報Ｃを付加することにより送信語３１を生成する符号化回路２と、情報伝送路中に誤りを含んだ受信語３２に対して、このパリティ検査行列Ｈを基に生成したシンドロームＳを用いて誤りを訂正する復号回路４を設け、特に前記シンドロームＳを構成する複数のビットを、パリティ検査行列Ｈの構成に対応して複数のグループに分けて、この各グループ毎のビット値を所定のロジックに従って順次判断していくことにより、パリティ検査行列Ｈや復号手順を統一的に扱うことが可能となり、誤りの発生状態に柔軟に対応できるようになる。【選択図】          図１
2005176244.tif 000002
【特許請求の範囲】
【請求項１】
入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備える誤り訂正・検出装置であって、
前記符号化手段は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、
前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、
前記シンドローム生成手段により生成されたシンドロームを構成する複数のビットを、前記パリティ検査行列の構成に対応して複数のグループに分け、前記各グループ毎のビット値を基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることを特徴とする誤り訂正・検出装置。
【請求項２】
前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有することを特徴とする請求項１に記載の誤り訂正・検出装置。
【請求項３】
前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有するとともに、任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有することを特徴とする請求項１に記載の誤り訂正・検出装置。
【請求項４】
前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能、および任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有するとともに、１バイト中のｔビットを超える誤りを検出する機能を有することを特徴とする請求項１に記載の誤り訂正・検出装置。
【請求項５】
前記パリティ検査行列Ｈは、Ｒ行Ｎ列を有する次の行列Ｈであり、
【数１】
2005176244.tif 000018
ただし、ｎ＝２(R-q)/2−１、０≦ｉ≦ｎ−１、０x×yはｘ行ｙ列の零行列、Ｉzはｚ×ｚの単位行列であり、前記Ｈ′は、Ｈ′＝[ｈ0′、ｈ1′、…、ｈb-1′]に示すｑ次の列ベクトルｈj′（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であって３ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ′）≧Ｍｉｎ（３ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが３ｔ＜ｂのときは前記Ｈ′は最小ハミング距離３ｔ＋１を有するパリティ検査行列Ｈに等しくなり、
また、前記Ｈ″は、Ｈ″＝[ｈ0〃、ｈ1〃、…、ｈb-1〃]に示すランクｔ以上のｒ行ｂ列の２元行列であって、前記ｈ0〃、ｈ1〃、…、ｈb-1〃はそれぞれ有限体（ガロア体）GF（２r）上の要素で２元ｒ次の列ベクトルであり、ｔ＝ｂであれば前記Ｈ″はｂ×ｂのランクｂの行列であり、ｔ＜ｂであれば最小ハミング距離ｔ＋１を有する２元（ｂ、ｂ−ｒ）のパリティ検査行列Ｈに等しくなり、また、Ｒ≧ｂ＋２ｒとしγを２を底とする（Ｒ−ｑ）／２次の有限体ＧＦ（２r(R-q)/2）の原始元であって、φを加法のもとでＧＦ（２r）からＧＦ（２(R-q)/2）への準同形写像とするときに、γiＨ″=[γiφ（ｈ0〃）  γiφ（ｈ1〃）  γiφ（ｈ2〃）・・γiφ（ｈb-1〃）]が成立するように構成されることを特徴とする請求項１〜４の何れか１項に記載の誤り訂正・検出装置。
【請求項６】
前記誤り訂正手段は、前記シンドロームを構成する複数のビットを区分した複数のグループのうち第１のグループに含まれるビット値を基に、ｂ（ｂは２以上の整数）ビットを１バイトとした際のバイト単位のバイト誤りパターンを生成するバイト誤りパターン生成手段と、
前記バイト誤りパターン生成手段により生成したバイト誤りパターン、及び前記第１のグループ以外のグループに含まれるビット値を基に、前記受信語の何れのバイトに誤りが含まれているかを検出するバイト誤りポインタと、前記検出されたバイト誤りポインタの示すバイト内で何れのビットが誤っているかを検出するビット誤りポインタとを出力するシンドロームデコード手段とを備えることを特徴とする請求項１〜５の何れか１項に記載の誤り訂正・検出装置。
【請求項７】
前記誤り訂正手段は、前記シンドローム生成手段により生成されたシンドロームと、前記シンドロームデコード手段により出力されたバイト誤りポインタとを基に、前記バイト中に訂正することができないビット誤りを検出する誤り検出手段を備えることを特徴とする請求項６に記載の誤り訂正・検出装置。
【請求項８】
前記誤り検出手段は、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可信号を出力することを特徴とする請求項７に記載の誤り訂正・検出装置。
【請求項９】
前記誤り訂正手段は、前記シンドロームデコード手段により出力されたビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより訂正後の受信語を生成するビット反転手段を備えることを特徴とする請求項６〜８の何れか１項に記載の誤り訂正・検出装置。
【請求項１０】
入力情報データを基に送信語を生成する符号化処理と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理とを備える誤り訂正・検出方法であって、
前記符号化処理は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、
前記復号処理は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理と、
前記シンドローム生成処理により生成されたシンドロームを構成する複数のビットを、前記パリティ検査行列の構成に対応して複数のグループに分け、前記各グループ毎のビット値を基に前記受信語の誤りを訂正または検出する誤り訂正処理とを備えることを特徴とする誤り訂正・検出方法。
【請求項１１】
前記符号化処理は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有する前記パリティ検査行列を生成することを特徴とする請求項１０に記載の誤り訂正・検出方法。
【請求項１２】
前記符号化処理は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有するとともに、任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有する前記パリティ検査行列を生成することを特徴とする請求項１０に記載の誤り訂正・検出方法。
【請求項１３】
前記符号化処理は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能、および任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有するとともに、１バイト中のｔビットを超える誤りを検出する機能を有する前記パリティ検査行列を生成することを特徴とする請求項１０に記載の誤り訂正・検出方法。
【請求項１４】
前記符号化処理により生成されるパリティ検査行列Ｈは、Ｒ行Ｎ列を有する次の行列Ｈであり、
【数２】
2005176244.tif 000019
ただし、ｎ＝２(R-q)/2−１、０≦ｉ≦ｎ−１、０x×yはｘ行ｙ列の零行列、Ｉzはｚ×ｚの単位行列であり、前記Ｈ′は、Ｈ′＝[ｈ0′、ｈ1′、…、ｈb-1′]に示すｑ次の列ベクトルｈj′（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であって３ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ′）≧Ｍｉｎ（３ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが３ｔ＜ｂのときは前記Ｈ′は最小ハミング距離３ｔ＋１を有するパリティ検査行列Ｈに等しくなり、
また、前記Ｈ″は、Ｈ″＝[ｈ0〃、ｈ1〃、…、ｈb-1〃]に示すランクｔ以上のｒ行ｂ列の２元行列であって、前記ｈ0〃、ｈ1〃、…、ｈb-1〃はそれぞれ有限体（ガロア体）GF（２r）上の要素で２元ｒ次の列ベクトルであり、ｔ＝ｂであれば前記Ｈ″はｂ×ｂのランクｂの行列であり、ｔ＜ｂであれば最小ハミング距離ｔ＋１を有する２元（ｂ、ｂ−ｒ）のパリティ検査行列Ｈに等しくなり、また、Ｒ≧ｂ＋２ｒとしγを２を底とする（Ｒ−ｑ）／２次の有限体ＧＦ（２r(R-q)/2）の原始元であって、φを加法のもとでＧＦ（２r）からＧＦ（２(R-q)/2）への準同形写像とするときに、γiＨ″=[γiφ（ｈ0〃）  γiφ（ｈ1〃）  γiφ（ｈ2〃）・・γiφ（ｈb-1〃）]が成立するように構成されることを特徴とする請求項１０〜１３の何れか１項に記載の誤り訂正・検出方法。
【請求項１５】
前記誤り訂正処理は、前記シンドロームを構成する複数のビットを区分した複数のグループのうち第１のグループに含まれるビット値を基に、ｂ（ｂは２以上の整数）ビットを１バイトとした際のバイト単位のバイト誤りパターンを生成するバイト誤りパターン生成処理と、
前記バイト誤りパターン生成処理により生成したバイト誤りパターン、及び前記第１のグループ以外のグループに含まれるビット値を基に前記受信語の何れのバイトに誤りが含まれているかを検出するバイト誤りポインタと、前記検出されたバイト誤りポインタの示すバイト内で何れのビットが誤っているかを検出するビット誤りポインタとを出力するシンドロームデコード処理とを含むことを特徴とする請求項１０〜１４の何れか１項に記載の誤り訂正・検出方法。
【請求項１６】
前記誤り訂正処理は、前記シンドローム生成処理により生成されたシンドロームと、前記シンドロームデコード処理により出力されたバイト誤りポインタとを基に、前記バイト中に訂正することができないビット誤りを検出する誤り検出処理を含むことを特徴とする請求項１５に記載の誤り訂正・検出方法。
【請求項１７】
前記誤り検出処理は、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可信号を出力することを特徴とする請求項１６に記載の誤り訂正・検出方法。
【請求項１８】
前記誤り訂正処理は、前記シンドロームデコード処理により出力されたビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより訂正後の受信語を生成するビット反転を含むことを特徴とする請求項１５〜１７の何れか１項に記載の誤り訂正・検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スポッティバイト誤り訂正・検出方法及び装置に関し、より詳しくは、複数のビットをバイトとし、その複数のバイトから構成される語（ワード）に対して、任意のバイト中にビットの誤りが生じたときにその誤りを検出または訂正するために用いて好適なものである。
【背景技術】
【０００２】
近年、情報化社会の進展や半導体技術の進歩等により、ディジタルデータの信頼性向上がますます重要なものになってきている。ディジタルデータの伝送または記録を正確に行おうとする場合、送信データが情報伝送経路中でノイズ等の影響を受けて誤って伝送されることを防止したり、その誤り箇所を検出・訂正する必要がある。この誤り箇所の検出・訂正を実現するために、符号理論を基礎とした誤り訂正符号技術が従来より様々に開発されてきている。
【０００３】
従来の誤り訂正符号技術として、例えば、ｂビット（ｂは２以上の整数）の塊りをバイトと称し、１バイト中の任意の誤りを訂正する符号（SbEC符号と称する）として優れたHong-Patel符号が発表されている（例えば、非特許文献１参照）。
【０００４】
また、高速半導体メモリシステムにおいて、従来最もよく使用された１ビット誤り訂正・２ビット誤り検出符号を包含する特徴を有した奇数重み列バイト誤り訂正符号が発表されている（例えば、非特許文献２参照）。
さらに、１バイト誤りを訂正し、また２バイト誤りを検出する符号（SbEC-DbED符号と称する）は、リードソロモン符号（Reed-Solomon符号）およびその改良した効率のよい符号として提案されており、多くの計算機システム等の主記憶装置にすでに採用されている（例えば、非特許文献３参照）。
【０００５】
また、バイト誤りを検出する符号としては、１ビット誤りを訂正し、かつ２ビット誤りを検出するとともに、１バイトの誤りをも検出する符号（SEC-DED-SbED符号と称する）が発表され、現在、計算機システムの主記憶装置に多く適用されている（例えば、非特許文献４参照）。なお、これら１９８０年代後半までの相互に関連した多くの符号の研究・開発の具体的な内容は、T.R.N.Rao and Eiji Fujiwara, “Error Control Coding for Computer Systems”, Prentice-Hall, 1989の本で総括的に述べられている。
【０００６】
その後、新しく開発された高速半導体メモリ用の符号としては、１バイトの誤りを訂正し、かつ２ビット誤りを検出する符号（SbEC-DEDと称する）が下記非特許文献５に、また、１バイトの誤りを訂正し、かつ１ビット誤りと１バイト誤りとの同時誤りを検出する符号（SbEC-(S+Sb)ED符号と称する）が下記非特許文献６に提案されている。さらに、１バイトの誤りを訂正するとともに２ビットの誤りがあればこれも訂正する符号（DEC-SbEC符号と称する）が下記非特許文献７に発表されている。
【０００７】
特に、本発明に最も関連する符号として、具体的には、ｂビットからなるバイト内のｔビット(ｔ≦ｂ)までの誤りをｔ／ｂ誤りまたはスポッティバイト誤りと称し、この１スポッティバイト誤りを訂正するSt/bEC符号、および１スポッティバイト誤りを訂正し、かつバイト内ｔビットを越える１バイト誤りを検出するSt/bED-SbED符号に関する発明が既に出願されている（特願２００２−１５９７１４号）。また、特にSt/bEC符号については、下記非特許文献８に発表されている。
【０００８】
【非特許文献１】S.J.Hong and A.M.Patel,”A general Class of Maximal Codes for Computer Applications”, IEEE Transactions on Computers, Vol.C-21, No.12, pp.1322-1331, 1972
【非特許文献２】E.Fujiwara,”Odd-Weight-Column b-Adjacent Error Correcting Codes”, Transactions of the IECE Japan, Vol.E61, No.10, pp.781-787, 1978
【非特許文献３】S.Kaneda and E.Fujiwara,”Single Byte Error Correcting  Double Byte Error Detecting Codes for Memory Systems”, IEEE Transactions on Computers, Vol.C-31, No.7, pp.596-602, July 1982, 及びC.L.Chen and L.E.Grosbach,”Fault-Tolerant Memory Design in the IBM Application System/400TM”, Proceedings of Annual International Symposium on Fault-Tolerant Computing, pp.393-400, June 1991
【非特許文献４】S.Kaneda,”A Class of Odd-Weight-Column SEC-DED-SbED Codes for Memory System Applications”, IEEE Transactions on Computers, Vol.C-33, No.8, pp.737-739, Aug. 1984
【非特許文献５】E.Fujiwara and M.Hamada,”Single b-Bit Byte Error Correcting and Double Bit Error Detecting Codes for Memory Systems”, IEICE Transactions on Fundamentals, Vol.E76-A, No.9, pp.1442-1448, Sept. 1993
【非特許文献６】M.Hamada and E.Fujiwara,”A Class of Error Control Codes for Byte Organized Memory Systems  SbEC-(Sb+S)ED Codes “, IEEE Transactions on Computers, Vol.46, No.1, pp.105-109, Jan. 1997
【非特許文献７】G.Umanesan and E.Fujiwara,”Random Double Bit Error Correcting  Single Byte Error Correcting (DEC-SbEC) Codes for Memory Systems”, IEICE Transactions on Fundamentals, Vol.E85-A, No.1, pp.273-276, Jan. 2002
【非特許文献８】G.Umanesan and E.Fujiwara,”A Class of Codes for Correcting Single Spotty Byte Errors”, IEICE Transactions on Fundamentals, Vol.E86-A, No.3, pp.704-714, March 2003
【発明の開示】
【発明が解決しようとする課題】
【０００９】
１９８０年代半ばまでは、半導体メモリ素子にはデータ１ビットの入出力を有する素子が主に使用されたことから、１素子の誤りを訂正し２素子までの誤りを検出する１ビット誤り訂正・２ビット誤り検出符号（SEC-DED符号と称する）が多く使用されていた。ところが、１９８０年代半ばからはメモリ素子の高集積化ニーズに対応して、データ４ビットの入出力を有する素子が主流となりはじめ、バイト幅ｂ＝４である前述のS4EC-D4ED符号やSEC-DED-S4ED符号が主に使用されるようになってきた。さらに、１９９０年代半ばからはデータ８ビット、１６ビットの入出力を有する半導体メモリ素子が主流になりはじめた。しかし、従来のSbEC-DbED符号のバイト幅ｂにｂ＝８またはｂ＝１６を適用する場合、全体の符号長に対する検査ビット数の占める割合がおよそ３０％から４０％と多大となって符号化率が低下し、実用的に非常に大きな問題となっていた。
【００１０】
ところで、これらの半導体メモリ素子（ＤＲＡＭ素子）を使用したメモリ装置では、ノイズやアルファ粒子等によって一時故障が発生したり、ＤＲＡＭ素子自体が劣化して動作しなくなる固定故障が発生したりする。最近のＤＲＡＭ素子を用いた装置の８０％以上は一時故障であると言われおり、特に、８ビット以上の多ビットデータ入出力を有するＤＲＡＭ素子ではバイト中の１，２，３ビット程度の比較的小さい数のビット誤りが大半であるとされている。
【００１１】
中でも比較的エネルギーレベルの低い電磁ノイズやアルファ粒子による一時誤り、およびメモリセルの固定故障を原因とする１ビット誤りが最も多く、最近では、前記ＤＲＡＭ素子を搭載したモバイル機器が多用されていることから、電磁環境が悪い中での使用も考慮しなければならなくなっている。また、高い高度を飛行する航空機や軍用機で用いられる電子機器中のＤＲＡＭ素子では、宇宙線に起因するエネルギーレベルの高い中性子粒子等の衝突により、２ビット、３ビット程度の誤りを有する一時故障が発生する可能性が高くなっている。さらに、衛星通信や宇宙通信で用いられる宇宙機器に搭載するＤＲＡＭ素子では、エネルギーレベルの高い粒子との衝突によって大きなダメージを受けてしまうことを考慮する必要があり、この場合２ビット以上の誤りになることが知られている。
【００１２】
一方、ＤＲＡＭ素子内のアドレス回路、制御回路、電力回路等に用いられる共通回路で生ずる故障には、発生確率は非常に小さいものの、場合によってはバイト幅全部で誤りを有してしまうことがあることも考慮しておく必要がある。
【００１３】
以上のようなビット誤りの発生状況が多岐にわたっていることを踏まえれば、パラメータｔおよびｂに任意の値を与えて構成できる前記St/bEC-SbED符号は、８ビット以上のＤＲＡＭ素子を使用したメモリ装置に用いる場合に非常に実用的な符号方式である。つまり、前記St/bEC-SbED符号は、バイト幅ｂより小さなｔビット（このｔの値は、誤りの傾向を調査して設計者が任意に決めることが可能である）までの１素子の誤りを訂正することが可能な機能、及び発生確率としては小さいもののｔビットを超える１バイト誤りを検出することが可能な機能を備えた上で、従来のバイト単位で行う符号方式と比較して大幅に少ない数の検査ビットでビット誤りを訂正・検出することを実現することができるようになっている。
【００１４】
しかしながら、前記St/bEC-SbED符号においては、１バイト、即ち１素子内のビット誤りを対象としていて、任意の２素子（隣接した２素子に限らない）にまたがる誤りについては対処できないという問題を有していた。さらに、実用的観点より、１素子のｔ／ｂ誤りを訂正するとともに、２素子のｔ／ｂ誤りも検出する機能を有する符号（St/bEC-Dt/bED符号：Single t-bit within a b-bit byte Error Correcting  Double t-bit within each b-bit byte Error Detecting Codeと称する）の開発が求められてきている。なお、前記“St/bEC-Dt/bED符号”を、簡単に“１スポッティバイト誤り訂正・２スポッティバイト誤り検出符号”とも称することとする。ここで、ｔは１≦ｔ≦ｂを満足する整数である。
【００１５】
本発明はこのような事情に鑑みてなされたものであり、バイトをｂビットの塊りとするとき、バイト内の１ビット以上ｔビットまでのすべての誤りを訂正する１バイト内ｔビット誤り訂正機能(St/bEC)、および任意の２バイトにおける各バイト内ｔビット誤りを検出する各２バイト内ｔビット誤り検出機能（Dt/bED）とを有する機能（St/bEC-Dt/bED）とともに、さらに１バイト内のｔビットを越える誤りを検出する機能(SbED)を有した機能(St/bEC-Dt/bED-SbED符号と称する)を備えたスポッティバイト誤り訂正・検出方法及びその装置を提供することを目的としている。
要するに、本発明は、従来の符号技術では存在しない、ｂビットからなるバイト中の２ビット、３ビット等のｔビット（ｔは１以上ｂ以下の整数）までのビット誤りである１スポッティバイト誤りを訂正するとともに、任意の２バイトにおける２スポッティバイト誤りを検出する符号機能（St/bEC-Dt/bED）を備えることにより、従来よりも検査ビット数を少なくして符号化率を向上させ、またビット誤りの発生状態に柔軟に対応できる符号機能を提供することを目的としている。
【課題を解決するための手段】
【００１６】
本発明の誤り訂正・検出装置は、入力情報データを基に送信語を生成する符号化手段と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号手段とを備える誤り訂正・検出装置であって、前記符号化手段は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、前記復号手段は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成手段と、前記シンドローム生成手段により生成されたシンドロームを構成する複数のビットを、前記パリティ検査行列の構成に対応して複数のグループに分け、前記各グループ毎のビット値を基に前記受信語の誤りを訂正または検出する誤り訂正手段とを備えることを特徴としている。
【００１７】
また、前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有することを特徴としている。
【００１８】
また、前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能を有するとともに、任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有することを特徴としている。
【００１９】
また、前記パリティ検査行列は、ｂ（ｂは２以上の整数）ビットを１バイトとした際、前記入力情報データが複数のバイトから構成される場合に、１バイト中の任意のｔ（ｔは１以上ｂ以下の整数）ビット誤りを訂正する機能、および任意の２バイトにおける各バイト内のｔビット誤りを検出する機能を有するとともに、１バイト中のｔビットを超える誤りを検出する機能を有することを特徴としている。
【００２０】
また、前記パリティ検査行列Ｈは、Ｒ行Ｎ列を有する次の行列Ｈであり、
【数１】
2005176244.tif 000003
ただし、ｎ＝２(R-q)/2−１、０≦ｉ≦ｎ−１、０x×yはｘ行ｙ列の零行列、Ｉzはｚ×ｚの単位行列であり、前記Ｈ′は、Ｈ′＝[ｈ0′、ｈ1′、…、ｈb-1′]に示すｑ次の列ベクトルｈj′（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であって３ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有し、すなわち、Ｒａｎｋ（Ｈ′）≧Ｍｉｎ（３ｔ、ｂ）を満足し、また、ランクがｂに等しいときはランクｂのｂ×ｂ行列であり、ランクが３ｔ＜ｂのときは前記Ｈ′は最小ハミング距離３ｔ＋１を有するパリティ検査行列Ｈに等しくなり、
また、前記Ｈ″は、Ｈ″＝[ｈ0〃、ｈ1〃、…、ｈb-1〃]に示すランクｔ以上のｒ行ｂ列の２元行列であって、前記ｈ0〃、ｈ1〃、…、ｈb-1〃はそれぞれ有限体（ガロア体）GF（２r）上の要素で２元ｒ次の列ベクトルであり、ｔ＝ｂであれば前記Ｈ″はｂ×ｂのランクｂの行列であり、ｔ＜ｂであれば最小ハミング距離ｔ＋１を有する２元（ｂ、ｂ−ｒ）のパリティ検査行列Ｈに等しくなり、また、Ｒ≧ｂ＋２ｒとしγを２を底とする（Ｒ−ｑ）／２次の有限体ＧＦ（２r(R-q)/2）の原始元であって、φを加法のもとでＧＦ（２r）からＧＦ（２(R-q)/2）への準同形写像とするときに、γiＨ″=[γiφ（ｈ0〃）  γiφ（ｈ1〃）  γiφ（ｈ2〃）・・γiφ（ｈb-1〃）]が成立するように構成されることを特徴としている。
【００２１】
また、前記誤り訂正手段は、前記シンドロームを構成する複数のビットを区分した複数のグループのうち第１のグループに含まれるビット値を基に、ｂ（ｂは２以上の整数）ビットを１バイトとした際のバイト単位のバイト誤りパターンを生成するバイト誤りパターン生成手段と、前記バイト誤りパターン生成手段により生成したバイト誤りパターン、及び前記第１のグループ以外のグループに含まれるビット値を基に、前記受信語の何れのバイトに誤りが含まれているかを検出するバイト誤りポインタと、前記検出されたバイト誤りポインタの示すバイト内で何れのビットが誤っているかを検出するビット誤りポインタとを出力するシンドロームデコード手段とを備えることを特徴としている。
【００２２】
また、前記誤り訂正手段は、前記シンドローム生成手段により生成されたシンドロームと、前記シンドロームデコード手段により出力されたバイト誤りポインタとを基に、前記バイト中に訂正することができないビット誤りを検出する誤り検出手段を備えることを特徴としている。
【００２３】
また、前記誤り検出手段は、前記受信語のビット誤りを訂正できないことを検出した場合に、訂正不可信号を出力することを特徴としている。
また、前記誤り訂正手段は、前記シンドロームデコード手段により出力されたビット誤りポインタを基に、誤りビットに該当する前記受信語のビット値を反転させることにより誤り訂正後の受信語を生成するビット反転手段を備えることを特徴としている。
【００２４】
本発明の誤り訂正・検出方法は、入力情報データを基に送信語を生成する符号化処理と、情報伝送路中で誤りが発生した前記送信語を受信語として入力して前記誤りを訂正または検出する復号処理とを備える誤り訂正・検出方法であって、前記符号化処理は、符号を表現するパリティ検査行列と前記入力情報データとを基に生成した検査情報を前記入力情報データに付加することにより前記送信語を生成し、前記復号処理は、前記パリティ検査行列を基に前記受信語のシンドロームを生成するシンドローム生成処理と、前記シンドローム生成処理により生成されたシンドロームを構成する複数のビットを、前記パリティ検査行列の構成に対応して複数のグループに分け、前記各グループ毎のビット値を基に前記受信語の誤りを訂正または検出する誤り訂正処理とを備えることを特徴としている。
【発明の効果】
【００２５】
本発明によれば、符号を表現するパリティ検査行列と入力データとを基に生成した検査情報を前記入力情報データに付加した送信語が、情報伝送路中で発生した誤りを訂正・検出する際に、誤りを有する可能性のある受信語に対し前記パリティ検査行列を基にシンドロームを生成するとともに、このシンドロームを構成する複数のビットを前記パリティ検査行列の構成に対応して複数のグループに分け、この各グループ毎のビット値を基に前記受信語の誤りを訂正または検出するようにしたもので、１バイト中の２ビット、３ビット等のｔビットまでの誤りである１スポッティバイト誤りを訂正する機能（St/bEC）に加え、これまで存在しなかった各２バイトにまたがる２スポッティバイト誤りをも完全に検出する機能（Dt/bED）を有し、さらに１バイト内にｔビットを越えるバイト誤りを検出する機能（SbED）を付加したSt/bEC-Dt/bED-SbEDの符号機能を実現することができた。これにより、誤りを検出または訂正する符号であるパリティ検査行列の構成や復号の処理手順を、誤りパターンの発生状況ごとに対応させる必要がなく統一的に扱うことが可能となり、本発明の符号機能におけるｔ値を任意に設定するだけで誤りの発生状態に柔軟に対応できる符号機能を提供することができる。
また、ｂビットであるバイト長よりも小さな整数ビット長ｔを選ぶことにより、従来のバイト誤り制御符号（ｔ＝ｂに相当）と比較して、検査ビット数を大幅に少なくすることが可能となる。これにより、符号長に対する検査ビット数の占める割合を小さくさせて符号化率を格段に向上することが可能となり、高効率かつ高信頼性のあるデータ伝送を実現することができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の好適な実施形態について図面を参照しながら詳細に説明する。
なお、本実施形態で対象とするディジタルデータとは、０と１との組合せの信号（２進化符号）であり、ビット誤りの発生とは、符号語（バイト）中の任意のビットが、０→１または１→０になることを意味することとする。また、バイト誤りの発生とは、ｂビットからなる符号語中のすべてのビットを含む任意のビットが０→１または１→０になること、さらに、スポッティバイト誤りの発生とは、ｂビットからなる符号語中のｔビット(ｔ≦ｂ)までが０→１または１→０になることを意味することとする。なお、本実施の形態で、「誤り」とある場合、特に明記していない限り、前記「ビット誤り」、「バイト誤り」、「スポッティバイト誤り」のすべてを包含していることとする。
【００２７】
＜スポッティバイト誤り訂正・検出装置１００の全体構成＞
図１は、本発明のスポッティバイト誤り訂正・検出装置１００（以下、スポッティバイト装置１００と略す）の概略構成を示すブロック図である。図１に示すように、スポッティバイト装置１００は、符号化回路２、メモリ３、復号回路４等を備えた構成になっている。
符号化回路２は、対象のディジタルデータ（以下、入力情報データ３０と称する）に対して誤りの訂正・検出を行う検査情報を生成する回路である。なお、検査情報は、任意個の検査ビットより構成されている。
【００２８】
メモリ３は情報伝送路に相当し、本実施形態ではメモリ３を経たデータには誤りが含まれる可能性が存在する構成としている。つまり、符号化回路２より出力されてメモリ３に入力されるデータには誤りが生じていないのに対して、メモリ３から出力されるデータには、誤りが発生している場合を含んでいる。
【００２９】
復号回路４は、シンドローム生成回路１、誤り訂正回路５を備えた構成になっている。復号回路４は、受信語３２に誤りが含まれているか否かを検出したり、その誤り箇所を特定して訂正を行うための回路である。復号回路４の詳細な構成については、後述する復号処理で説明する。
【００３０】
なお、後述する符号化処理及び復号処理では、ガロア理論に基づいた行列演算を行うようにしていることから、符号化回路２、復号回路４、または情報伝送路中における各データを、行列名を英字で付した行列式で表現するようにしている。具体的には例えば、入力情報データＤ、符号（パリティ検査行列）Ｈ、検査情報Ｃ、送信語Ｖ、受信語Ｖ′、シンドロームＳと表している。
【００３１】
＜スポッティバイト装置１００の全体動作＞
ここでは、スポッティバイト装置１００の全体動作について説明する。図２は、全体動作の処理手順を示すフローチャートである。
符号化回路２は、入力情報データ（Ｄ）３０が入力されると、詳細については後述するパリティ検査行列（Ｈ）を用いて検査情報（Ｃ）を生成する（ステップＳ２００）。符号化回路２は、この検査情報（Ｃ）を入力情報データ（Ｄ）３０に付加して、送信語（Ｖ）３１としてメモリ３に送出する（ステップＳ２０１）。メモリ３を経て誤りを含む可能性のある受信語（Ｖ′）３２は、復号回路４に入力される（ステップＳ２０２）。
【００３２】
次に、復号回路４では、まず、符号化回路２で用いたパリティ検査行列（Ｈ）を利用して、入力された受信語（Ｖ′）３２に誤りが発生しているか否かを調べる。具体的には、復号回路４のシンドローム生成回路１が、符号を表現しているパリティ検査行列（Ｈ）を転置させた転置行列（ＨT）を、受信語（Ｖ′）３２に対して乗算することによりシンドローム（Ｓ）３３を生成する（ステップＳ２０３）。シンドローム（Ｓ）３３の値は受信語（Ｖ′）３２に応じて変化するため、受信語（Ｖ′）３２に誤りが含まれているかを判断することが可能となる。
【００３３】
そこで、誤り訂正回路５は、前記シンドローム（Ｓ）の値に基づいて、まず誤りを検出したか否か（ステップＳ２０４）、検出した場合、誤り訂正が可能か否かを判断し（ステップＳ２０５）、前記判断の結果、訂正可能であれば誤りの訂正を行う（ステップ２０６）。そして、誤り訂正回路５は、受信語Ｖ′に対して１スポッティバイト誤りの訂正処理を施した場合、訂正後のＶ′を受信後出力情報データ（Ｖ*）３４として出力する（ステップＳ２０７）。これに対して、ステップ２０５の判断の結果、訂正不可能な２スポッティバイト誤り等が検出された場合には、誤り訂正回路５は、訂正不可能な誤り検出信号としてのＵＣＥ（Uncorrectable Error）信号３５を出力する（ステップＳ２０８）。
【００３４】
次に、前述した符号化回路２及び復号回路４で用いられるパリティ検査行列（Ｈ）の構成について詳細に説明する。本発明のパリティ検査行列Ｈ（Ｈマトリクス、符号マトリクス、または単に検査行列とも称される）は、バイトをｂビットの塊りとするときに、バイト中のｔビットの誤りを訂正する１バイト内ｔビット誤り訂正（St/bEC）、すなわち１スポッティバイト誤り訂正を行うとともに、２バイトにまたがる（隣接したバイトに限らない、以下同じ）２スポッティバイト誤り検出（Dt/bED）も合わせて行うことができる符号（St/bEC-Dt/bED符号）である。
【００３５】
本実施の形態では、任意のｔ（ｔは１以上ｂ以下の整数）およびｂ（２以上の整数）に対して構成できる一般的な符号構成法を提示するとともに、その符号により実際に誤りの訂正・検出ができる方法を示し、またそのための符号化回路および復号回路を提示し、前記符号化回路および復号回路によって誤りが具体的に訂正・検出できることを示す。
【００３６】
なお、ｔ＝１のときに、本発明のパリティ検査行列（Ｈ）は従来の１ビット誤り訂正・２ビット誤り検出（SEC-DED）符号に一致し、ｔ＝ｂのときに、従来の１バイト誤り訂正・２バイト誤り検出（SbEC-DbED）符号に一致する。また、ｔ＝２のとき、パリティ検査行列（Ｈ）はｔ＝２の１スポッティバイト誤りを訂正し、２バイト間にまたがるランダムな２ビット誤りを検出する機能（St/bEC-DED）を包含することは明らかである。
【００３７】
いま、Ｋビットの入力情報データ（Ｄ）３０に対してＲビットの検査情報（Ｃ）を付加し、ある機能を満足するＮ＝Ｋ＋Ｒビットの長さを有する送信語Ｖ（Ｎビットの行ベクトル）を構成することができたときに、この送信語（Ｖ）と、符号を規定するＲ行Ｎ列の２元パリティ検査行列（Ｈ）との間には、Ｖ・ＨT＝０の関係が成立する。ここで、ＨTはパリティ検査行列（Ｈ）の行と列とを入れ替えて生成した転置行列であり、また、右辺の０はＲビットの零行ベクトルを示している。
【００３８】
本実施形態では、１バイト内ｔビットの誤り（１スポッティバイト誤り、またはｔ／ｂ誤り）を訂正し、任意の２バイトにまたがるスポッティバイト誤り（２スポッティバイト誤り、または２ｔ／ｂ誤り）を検出する符号である“St/bEC-Dt/bED符号”に用いるＲ行Ｎ列を有するパリティ検査行列（Ｈ）を、下記の（式１）に示すような構成にしている。
【００３９】
【数２】
2005176244.tif 000004
ここで、ｎ＝２(R-q)/2−１、０≦ｉ≦ｎ−１、０x×yはｘ行ｙ列の零行列、ＩZはｚ×ｚの単位行列である。
前記の（式１）から分かるように、パリティ検査行列Ｈは、情報部のビット列ＨRと、検査部に対応するビット列Ｉとに基本的に分けられ、つまりＨ＝[ＨR Ｉ]という形で構成される。
【００４０】
前記の（式１）を構成する行列Ｈ′は、下記の（式２）に示すｑ次の列ベクトルｈj′（０≦ｊ≦ｂ−１）から構成されるｑ行ｂ列（ｑ≦ｂ）の２元行列であり、３ｔまたはｂのうちいずれか小さい値に等しいか大きいランク（Ｒａｎｋ）を有する。すなわち、Ｒａｎｋ（Ｈ′）≧Ｍｉｎ（３ｔ、ｂ）を満足する。
Ｈ′＝[ｈ0′、ｈ1′、…、ｈb-1′]                        ………  （式２）
【００４１】
また、ランクがｂに等しいときはランクｂのｂ×ｂ行列（例えば、ｂ×ｂの単位行列）であり、ランクが３ｔ＜ｂのときは行列Ｈ′は最小ハミング距離３ｔ＋１を有する符号の検査行列、すなわち、ｔビット誤り訂正・２ｔビット誤り検出の機能を有する（ｂ、ｂ−ｑ）符号のパリティ検査行列（Ｈ）に等しくなる。
【００４２】
また、前記の（式１）を構成する行列Ｈ″は、下記の（式３）に示すランクｔ以上のｒ行ｂ列の２元行列であり、ｈ0〃、ｈ1〃、…、ｈb-1〃はそれぞれ有限体（ガロア体）GF（２r）上の要素で２元ｒ次の列ベクトルである。
Ｈ″＝[ｈ0〃、ｈ1〃、…、ｈb-1〃]                      ………  （式３）
ここで、ｔ＝ｂであれば行列Ｈ″はｂ×ｂのランクｂの行列（例えば、ｂ×ｂの単位行列）であり、ｔ＜ｂであれば最小ハミング距離ｔ＋１を有する２元（ｂ、ｂ−ｒ）符号の検査行列に等しい。すなわち、このときｔビット誤り検出符号のパリティ検査行列Ｈに等しくなる。
【００４３】
次に、Ｒ≧ｂ＋２ｒとし、γを２を底とする（Ｒ−ｑ）／２次の有限体ＧＦ（２(R-q)/2）の原始元とするとき、γiＨ″は下記の（式４）で定義できる。
γiＨ″=[γiφ（ｈ0〃）  γiφ（ｈ1〃）  γiφ（ｈ2〃）・・γiφ（ｈb-1〃）]
………  （式４）
ここで、φは加法のもとでＧＦ（２r）からＧＦ（２(R-q)/2）への準同形写像（homomorphism)である。すなわち、φ：ＧＦ（２r）→ＧＦ（２(R-q)/2）である。また、バイトはｂビットの長さを有するが、最後の２バイトは（Ｒ−ｑ）／２ビットの長さを有する。（Ｒ−ｑ）／２＞ｂでは、ｂビットより大きな値を有するが、例外的にこれも他のバイトと同様にバイトとして扱うこととする。このとき、最大符号長Ｎは、Ｎ＝ｂ（２(R-q)/2−１）＋Ｒ−ｑである。
【００４４】
次に、前記（式１）に示したパリティ検査行列（Ｈ）で表される符号が、前述したSt/bEC-Dt/bEDの機能（SbEDの機能を含む）を有していることを具体的に示す。
（１）１スポッティバイト誤り訂正（St/bEC）の機能を有している証明：
バイト中のｔビットの誤りを訂正する１バイト内ｔビット誤り訂正である１スポッティバイト誤り訂正は、前述したシンドローム生成回路１が生成するシンドローム（Ｓ）３３を用いて行うようにしている。ここで、シンドローム（Ｓ）３３と前記パリティ検査行列（Ｈ）との関係は、Ｓ＝Ｖ′・ＨTで表される。いま、受信語（Ｖ′）３２が元々の送信語（Ｖ）３１に対して誤りパターン（Ｅ）を含み、Ｖ′＝Ｖ＋Ｅで表されるとき、シンドローム（Ｓ）３３は、
Ｓ＝Ｖ′・ＨT＝（Ｖ＋Ｅ）・ＨT＝Ｖ・ＨT＋Ｅ・ＨT
となる。
前述したように、Ｖ・ＨT＝０の関係が成立していることから、結局、シンドロームＳ＝Ｅ・ＨTが成り立つ。つまり、シンドローム（Ｓ）３３は、送信語（Ｖ）３１に影響されずに誤りパターン（Ｅ）のみで決まることから、シンドローム（Ｓ）３３に基づいて１スポッティバイト誤り訂正を行うことが可能か否かは、パリティ検査行列（Ｈ）と誤りパターン（Ｅ）とから計算されるＥ・ＨTの値の結果によって決定できるものである。
【００４５】
そこで、前述したように、行列Ｈ′がｔビット誤り訂正・２ｔビット誤り検出符号のパリティ検査行列に等しいこと、および行列Ｈ″がｔビット誤り検出符号の検査行列に等しいことから、１バイト中のｔビットまでの誤りの集合をＥt/bとするとき、これに含まれる任意の異なる誤りｅ1、ｅ2およびｉ≠ｊに対して、下記の（式５）が明らかに成立することがわかる。
【００４６】
【数３】
2005176244.tif 000005
【００４７】
また、語中の最後のそれぞれ（Ｒ−ｑ）／２ビットを有する２バイトにおけるｔ／ｂ誤りｅ10、ｅ20と、この２バイトを除く他のｂビット幅を有するバイトにおけるｔ／ｂ誤りｅ1に関して、下記の（式６）〜（式８）に表されるシンドロームの関係も明らかに成立する。なお、ｅ10及びｅ20のシンドロームとの値を比較したり（式８）、ｅ10またはｅ20のシンドロームと最後の２バイト以外のバイトのシンドロームとの値を比較したり（式６、式７）しているのは、前記（式１）に示すパリティ検査行列Ｈの最後の２列が単位行列Ｉz及び零行列０x×yより構成されている特殊性を考慮して個別に証明することが必要なためである。
【００４８】
【数４】
2005176244.tif 000006
【００４９】
受信語（Ｖ′）３２が元々の送信語（Ｖ）３１に対して誤りパターン（Ｅ）を含んでいない場合には（すなわち、Ｅ＝０）、シンドローム（Ｓ）３３は明らかにＳ＝０となるので、シンドローム（Ｓ）が非零のときは、受信語（Ｖ′）３２には誤りが含まれていることになる。そして前記証明では、１バイト中のｔ／ｂ誤りの非零シンドロームは、他バイトにおけるｔ／ｂ誤りの非零シンドロームと異なることが示された。これより、本実施形態の（式１）で示すパリティ検査行列（Ｈ）が、誤りを有した互いに異なるバイトにおけるｔ／ｂ誤りを訂正するSt/bECの機能を有していることを証明できたことになる。
【００５０】
（２）２スポッティバイト誤り検出（Dt/bED）の機能を有している証明：
次に、このパリティ検査行列（Ｈ）が、２バイトのｔ／ｂ誤り検出の機能を有していることを示すためには、１バイトにおけるｔ／ｂ誤りのシンドロームが他の任意の２バイトのｔ／ｂ誤りによるシンドロームと一致しないことを証明する必要がある。以下、これを４つの条件に分けて証明する。
【００５１】
（ａ）受信語Ｖ′を構成する最後の３バイト以外のバイト間での成立：
いま、受信語Ｖ′を構成する最後の３バイトを除いた他のバイト（各バイトのバイト幅はｂビット）に対して、異なる３バイト間にｅ1、ｅ2、ｅ3のｔ／ｂ誤りがそれぞれ生じたとき、シンドロームＳとして下記の（式９）の関係が成立したと仮定する。
【００５２】
【数５】
2005176244.tif 000007
【００５３】
前記の（式９）より、ｅ1Ｈ′T＋ｅ2Ｈ′T＝ｅ3Ｈ′Tが成立し、行列Ｈ′がｔビット誤り訂正・２ｔビット誤り検出符号のパリティ検査行列であることから、ｅ1＋ｅ2＝ｅ3が成立する。この両辺に右からＨ″を乗算すれば、ｅ1Ｈ″＋ｅ2Ｈ″＝ｅ3Ｈ″が得られる。
ｅ1Ｈ″、ｅ2Ｈ″、ｅ3Ｈ″をそれぞれｘ、ｙ、ｚと表すと、前記の（式９）より次の（式１０）〜（式１２）の関係がそれぞれ成立することがわかる。
ｘ＋     ｙ ＝    ｚ                            ………  （式１０）
γiｘ＋γjｙ   ＝γk ｚ                            ………  （式１１）
γ2iｘ＋γ2jｙ ＝γ2kｚ                            ………  （式１２）
【００５４】
前記（式１１）の両辺を２乗すると、γ2iｘ2＋γ2jｙ2＝γ2kｚ2となり、（式１２）とから次の（式１３）の関係が導かれる。
γ2iｘ2＋γ2jｙ2＝（γ2kｚ）ｚ＝（γ2iｘ＋γ2jｙ）ｚ        ……  （式１３）
さらに、（式１３）の右辺のｚに対し、前記（式１０）のｚを代入することにより、最終的に次の（式１４）が得られる。
γ2iｘｙ＋γ2jｘｙ＝０                                    ………  （式１４）
【００５５】
前記（式１４）よりｉ＝ｊが導かれるが、これは前述した前提条件（ｉ≠ｊ）と矛盾した結果となってしまう。したがって、ｅ1、ｅ2、ｅ3のｔ／ｂ誤りに対するシンドロームＳに関する前記（式９）に示した仮定が成立しない、つまり、１バイトにおけるｔ／ｂ誤りのシンドロームが他の任意の２バイトのｔ／ｂ誤りによるシンドロームと一致しないこととなる。これから、受信語（Ｖ′）３２の最後の３バイトを除くｂビット幅を有するバイト間において、２バイトのｔ／ｂ誤りを検出することができることになる。
【００５６】
（ｂ）受信語Ｖ′を構成する最後の３バイト中の１バイトと、他の２バイト間の成立：
次に、受信語（Ｖ′）３２の最後の３バイト中の１バイトとこの３バイトを除くその他の２バイト（ｉバイト目及びｊバイト目）間に、前記と同様な３バイトの誤りが生じたとき、そのシンドロームの関係として下記に示す（式１５）〜（式１７）が成立したと仮定する。ここで、ｅ1、ｅ2、ｅ3は、ｂビット幅を有するEt/bに属するｔ／ｂ誤りであり、ｅ10、ｅ20はそれぞれ（Ｒ−ｑ）／２ビット幅を有する受信語（Ｖ′）３２の最後の２バイトに対する誤りである。
【００５７】
【数６】
2005176244.tif 000008
【００５８】
前述した(式９)から（式１４）までの処理と同様に、各項をｘ、ｙ、ｚに置き換えて変形操作を行えば、前記（式１５）〜（式１７）に示した関係式は、前記（式１０）に示した関係ｘ＋ｙ＝ｚとともに、下記の（式１８）及び（式１９）に示す関係が成立する。
【００５９】
γ2iｘ＋γ2jｙ ＝０                                       ………  （式１８）
γ iｘ＋γ jｙ ＝０                                       ………  （式１９）
前記（式１９）の両辺を２乗して変形し、さらに前記（式１８）とから、下記の（式２０）の関係が得られる。
γ2iｘ2＋γ2jｙ2  ＝（γ2iｘ＋γ2jｙ）ｘ＋γ2jｙ2＋γ2jｙｘ
＝γ2jｙ（ｙ＋ｘ）＝０                  ………  （式２０）
【００６０】
前記（ａ）の場合と同様、前記（式２０）からｘ＝ｙが導かれることとなり、前提条件（ｉ≠ｊ）と矛盾した結果となってしまう。したがって、ｅ1、ｅ2、ｅ3およびｅ10、ｅ20のｔ／ｂ誤りに対するシンドロームＳに関する前記（式１５）〜（式１７）に示した仮定が成立しないこととなる。これから受信語Ｖ′の最後の３バイトバイト中の任意の１バイトのｔ／ｂ誤りのシンドロームは、この３バイトを除くその他の任意の２個のバイトにおけるｔ／ｂ誤りによるシンドロームと一致することはなく、このような２バイトのｔ／ｂ誤りを検出することができることになる。
【００６１】
（ｃ）受信語Ｖ′を構成する最後の３バイト中の２バイトと、他の１バイト間の成立：
また、受信語Ｖ′の最後の３バイト中の２バイトのｔ／ｂ誤りによるシンドロームとこの３バイトを除く他の１バイト（ｉバイト目）におけるｔ／ｂ誤りのシンドロームとの関係において、下記の（式２１）〜（式２３）に示す関係が成立したとする。
【００６２】
【数７】
2005176244.tif 000009
【００６３】
前記（式２１）においてｅ3γ2iＨ″T=０、前記（式２２）においてｅ3γiＨ″T=０、前記（式２３）において、ｅ3Ｈ′T=０（以上の０は２元列ベクトル）が成立するが、同様にこれらはいずれも矛盾した結果となっており、前記（式２１）〜（式２３）に示す関係は成立しないこととなる。よって、受信語Ｖ′の最後の３バイトにおける２バイトのｔ／ｂ誤りのシンドロームは、この３バイトを除く他の１バイトにおけるｔ／ｂ誤りのシンドロームと一致することはなく、この間の２バイトのｔ／ｂ誤りを検出することができることになる。
【００６４】
（ｄ）受信語Ｖ′を構成する最後の３バイト間の成立：
最後に、受信語Ｖ′の最後の３バイト間において、下記の（式２４）に示す関係が成立したと仮定する。
【数８】
2005176244.tif 000010
【００６５】
明らかに、この関係は矛盾した結果となっており、成立しないこととなる。よって、受信語Ｖ′の最後の３バイト間における２バイトのｔ／ｂ誤りを検出することができることになる。
したがって、前述した（ａ）〜（ｄ）における証明結果より、前記（式１）に示すパリティ検査行列（Ｈ）が、受信語（Ｖ′）３２に対する任意の２バイト誤りを検出するDt/bEDの機能を有することを証明できた。
【００６６】
（３）１バイト内のｔビットを越える誤りを検出する(SbED)の機能を有している証明：
前記（１）ではSt/bEC機能を、前記（２）ではDt/bEDの機能を有していることを証明したが、行列Ｈ′をｂ行ｂ列の単位行列Ｉbとする場合、前記（式１）に示すパリティ検査行列（Ｈ）は、前述したSt/bEC-Dt/bEDの機能に加えて、単一のｂビットのバイト誤りを検出する機能をも有している。これは、次のようにして証明することができる。
【００６７】
つまり、前記（式１）に示すパリティ検査行列（Ｈ）の第一行についてみれば、受信語（Ｖ′）３２の最後の２バイトに相当する部分を除く要素にはすべて行列Ｈ′が存在しているが、この行列Ｈ′がｂ×ｂの単位行列Ｉbであれば、単一バイト内に生じたいかなる誤りパターン（E）に対しも、シンドロームＳI＝Ｅ・Ｉb＝Ｅ≠０となる。
【００６８】
一方、前述したように、受信語（Ｖ′）３２が誤りパターン（Ｅ）を含んでいない場合には（すなわち、Ｅ＝０のとき）、シンドローム（Ｓ）は明らかにＳ＝０となることから、シンドローム（Ｓ）が非零であれば、誤りが発生していると判断できる。したがって、行列Ｈ′をｂ行ｂ列の単位行列Ｉbとした場合、単一バイト内に生じた誤りパターン（Ｅ）を検出することができるようになる。
特に、ｔより大きい１バイト誤りでは、誤りパターン（Ｅ）の重み（つまり、誤りパターン（Ｅ）に含まれている“１”の数）は明らかにｔよりも大きいことから、ｔ／ｂ誤りにおけるシンドロームＳIとは明らかに異なって１バイト内のｔビットを越える誤りを検出することができることになる。また、最後の２バイトのうち、１バイトにｔビットを越える誤りが生じたときも、同様の考えで明らかなように、１バイト内のｔビットを越える誤りを検出することが可能である。
したがって、前記の（式１）に示すパリティ検査行列（Ｈ）において、Ｈ′＝Ｉbとしたとき、（式１）に示すパリティ検査行列（Ｈ）が、受信語（Ｖ′）３２に対して単一のｂビットのバイト誤りを検出するＳbEDの機能を有していることを証明できたことになる。
【００６９】
以上より、パリティ検査行列（Ｈ）は、Ｈ′＝ＩbのときSt/bEC-Dt/bED-ＳbED機能を有する符号となることを証明することができた。
【実施例】
【００７０】
ここでは、具体的な符号パラメータを与えて、前記（式１）に示すパリティ検査行列（Ｈ）を構成できることを示す。なお、このパリティ検査行列（Ｈ）はあくまでも一例であってこれに限定されないことは言うまでもない。
【００７１】
いま、読み書きデータ幅として８ビットを有するメモリ素子を使用したメモリシステムを対象に、ｔ＝２、ｂ＝８のパラメータを与えてパリティ検査行列（Ｈ）を構成することとする。このとき、Ｍｉｎ（３ｔ，ｂ）＝Ｍｉｎ（６，８）＝６より、行列Ｈ′はランク６を有して符号長８ビットを有する６ビット誤り検出符号の検査行列を構成すればよい。この一例を下記の（式２５）に示す７×８の行列とする。これは７ビット誤り検出の能力を有する符号の検査行列でもある。
【００７２】
【数９】
2005176244.tif 000011
【００７３】
次に、行列Ｈ″はランクｔ＝２以上の行列であり、最小ハミング距離が３の符号として１ビット誤り訂正符号（または２ビット誤り検出符号）の検査行列を使用することとする。その一例を下記の（式２６）に示す４×８の行列とする。これは結果的に最小ハミング距離が４の符号となっている。
【００７４】
【数１０】
2005176244.tif 000012
【００７５】
次に、γを原始多項式ｇ（ｘ）＝ｘ4＋ｘ＋１の根とすると、γは４次の列ベクトルγ＝（０１００）Tと表現できる。つまり、γのべき表示γiとべクトル表示との対応を示せば、次のようになる。
γ0＝（１０００）T、    γ1＝（０１００）T、    γ2＝（００１０）T、
γ3＝（０００１）T、    γ4＝（１１００）T、    γ5＝（０１１０）T、
γ6＝（００１１）T、    γ7＝（１１０１）T、    γ8＝（１０１０）T、
γ9＝（０１０１）T、    γ10＝（１１１０）T、  γ11＝（０１１１）T、
γ12＝（１１１１）T、   γ13＝（１０１１）T、  γ14＝（１００１）T
【００７６】
これより、前記の（式２６）に示す行列H″は、H″＝[γ0γ4γ8γ14γ10γ13γ12γ7]と表すことができる。よって、前記の（式１）に示したパリティ検査行列（Ｈ）は、このＨ′及びH″、γiを使用して、具体的な（１３６、１２１）S2/8EC-D2/8ED符号を構成することができるようになる。これを図３に示す。なお、図３に示すように、パリティ検査行列（Ｈ）のＨ′及びH″に相当するビット箇所を明確化するため、そのビット境の箇所には実線を引いて示している。
【００７７】
いま、パリティ検査行列（Ｈ）の構成要素であるγ2H″が、図３に示す実際のビット値と対応しているかを具体的に確認する。前述したように、H″＝[γ0γ4γ8γ14γ10γ13γ12γ7]より、γ2H″＝γ2[γ0γ4γ8γ14γ10γ13γ12γ7]＝[γ2γ6γ10γ1γ12γ15γ14γ9]となる。このべき表示をベクトル表示（例えば、γ0＝（１０００）T等）に変換すれば図３に示すａ部分に相当し、このａ部分は明らかにパリティ検査行列（Ｈ）のγ2H″部分である。同様にして、パリティ検査行列（Ｈ）における他の構成要素についてもべクトル表示に変換すれば、全体として図３に示すビットの構成となる。
【００７８】
次に、ｂ＝８のもとで、ｔ＝３の場合のパリティ検査行列（Ｈ）を構成する。このとき、Ｍｉｎ（３ｔ、ｂ）＝Ｍｉｎ（９，８）＝８より、Ｈ′はランク８を有する行列として、８×８の単位行列を適用することができる。しかしながら、パリティ検査行列（Ｈ）における全体の検査ビットを削減する観点より、特例として、ランク７を有する前記の（式２４）に示す行列を適用することにする。ここで、ランク７を有する前記の（式２４）に示す行列を適用することが可能であるか否かについては、前述の証明に準じて適用可能であることを示すことができるが、ここではその証明を省略する。
【００７９】
次に、H″はランク３以上の行列であり、最小距離が４の符号として１ビット誤り訂正・２ビット誤り検出符号（または３ビット誤り検出符号）の検査行列を使用すればよい。このとき、前記の（式２６）に示す行列H″は、最小距離が４の符号であることからこれを使用すればよい。以上より、ｂ＝６、ｔ＝３のパリティ検査行列（Ｈ）に対しては、ｂ＝８、ｔ＝２の場合の図３に示したパリティ検査行列Ｈ（１３６、１２１符号）と同一となる。
【００８０】
また、ｔ＝４に対しては、Ｍｉｎ（３ｔ、ｂ）＝８より、行列Ｈ′はランク８を有する８×８の単位行列を使用する。一方、H″はランク４を有する４ビット誤り検出符号の検査行列であり、一例として下記の（式２７）に示す６×８の行列を構成することができる。
【００８１】
【数１１】
2005176244.tif 000013
【００８２】
このとき、行列H″は、ＧＦ（２6）上の原始多項式、例えばｇ（ｘ）＝ｘ6＋ｘ＋１の根をγとして、前述したｇ（ｘ）＝ｘ4＋ｘ＋１のときと同様に構成することができる。
また、ｔ＝５、６、７については、行列H″としてｔビット誤り検出符号を適用すればよい。そして、８列を有する行列を構成することから、これらすべてのｔに対し、結果的に、前記の（式２５）に示した７×８の７ビット誤り検出符号の検査行列をH″として使用すればよい。
【００８３】
なお、以上は最近最も使用されている、バイト幅ｂ＝８ビット入出力を有する半導体メモリ素子を対象としてパリティ検査行列Ｈ（符号）の一例を構成して説明したが、他にも多く使用されている多ビット入出力素子、例えば、ｂ＝１６ビット入出力を有する素子等に対しても、St/bEC-Dt/bED符号を同様に構成することができることは明らかである。
このように、前記ではパリティ検査行列（Ｈ）の構成例を示したが、次に、このパリティ検査行列（Ｈ）を用いて処理する符号化と復号の具体的な方法とその回路構成について示す。
【００８４】
（１）符号化の方法及びこれを実現する回路の構成について
まず、図１に示す符号化回路２が行う符号化方法について説明する。
符号化回路２は、入力情報データＤ（行ベクトル）３０と、パリティ検査行列（Ｈ）の情報部HRとを用いて、検査情報Ｃ（行ベクトル）を生成する。この検査情報（Ｃ）の生成は、下記の（式２８）により求めることができる。
Ｃ＝Ｄ・HRT                                          ………  （式２８）
具体的には、符号化回路２は、入力情報データ（Ｄ）３０の情報ビット長６４ビット、及び検査ビット長１５ビットを基に、図３に示したパリティ検査行列Ｈである（１３６、１２１）S3/8EC-D3/8ED符号を生成した後、さらに、情報部の後半５６ビットに相当する列ベクトル５６列と検査部で重み１を有さない１列とを足し合わせた合計５７列を削除した符号ビット長７９ビット、情報ビット長６４ビットを有する（７９、６４）S3/8EC-D3/8ED符号を生成する。図４は、前記（７９、６４）S3/8EC-D3/8ED符号を示している。
【００８５】
次に、前記の（式２８）を基に、符号化回路２は１５ビットの検査情報（Ｃ）を生成する。前記の（式２８）に示すＣ＝Ｄ・HRTから明らかなように、例えば、検査情報（Ｃ）における検査ビットC0を作成するには、図４に示す（７９、６４）S3/8EC-D3/8ED符号の行列の１行目において、後ろの１５×１５の単位行列を除いた情報部HR部分で“１”が存在する箇所に対応する情報ビットのGF（２）上の和（すなわち、２を法とする和：ｍｏｄ２）をとる演算を行えばよい。
【００８６】
例えば、検査ビットC0を求める場合、情報部HR部分で“１”が存在しているのは、ｄ0、ｄ7、ｄ8、ｄ15、ｄ16、ｄ23、ｄ24、ｄ31、ｄ32、ｄ39、ｄ40、ｄ47、ｄ48、ｄ55、ｄ56、ｄ63であり、これら１６個のビットについて２を法とする和（ｍｏｄ２）をとればよい。これを実現するには、図５に示すように、前記１６ビットを多入力パリティチェック回路２０（０）〜２０（１４）に入力する回路を構成すればよく、この多入力パリティチェック回路２０（０）の出力が検査ビットC0となる。他の検査ビットC1〜C14についても検査ビットC0と同様にして生成することができ、C0〜C14を対象にした全部で１５ビットの検査ビットを並列に生成する符号化回路２の構成を図５に示す。
そして、符号化回路２によって生成した検査情報（Ｃ）を、入力情報データ（Ｄ）３０に付加して生成した情報[Ｄ、Ｃ]が符号語を構成し、これがメモリ３に書き込まれる送信語（Ｖ）３１となる。
【００８７】
（２）復号の方法及びこれを実現する回路の構成について
次に、送信語（Ｖ）３１に誤りが生じたとき（受信語３２に誤りが含まれているとき）、その誤りに対する訂正・検出処理が、図４に示す（７９、６４）S3/8EC-D3/8ED符号を用いて生成されるシンドロームＳの値に基づいて可能なことを示す。
前記（７９、６４）S3/8EC-D3/8ED符号が、前記の（式１）に示した３段構成を有するパリティ検査行列（Ｈ）を基礎にして構成されていることから、上段より得られるｑ＝７ビットのシンドロームをＳI、中段より得られる（Ｒ−ｑ）／２＝４ビットのシンドロームをＳII、下段より得られる（Ｒ−ｑ）／２＝４ビットのシンドロームをＳIIIとする。
【００８８】
これらの情報を用いて、次のように誤りの訂正、検出を行うようにしている。受信語（Ｖ′）３２とパリティ検査行列（Ｈ）とから、シンドローム（Ｓ）３３は下記の（式２９）により求めることができる。
Ｖ′・ＨT＝Ｓ＝[ＳI  ＳII  ＳIII]                          ………  （式２９）
ここで、ＳI  ∈ＧＦ（２q）はｑ次の行ベクトルであり、ＳII、ＳIII∈ＧＦ（２(R-q)/2）はそれぞれ（Ｒ−ｑ）／２次の行ベクトルである。
このとき、ｔ／ｂ誤りパターン（E）とシンドローム（Ｓ）との間には、以下に示す関係が存在し、これによって復号回路４は誤りの訂正および検出ができる。
図６は、復号回路４における誤りの訂正および検出の処理ロジックを示したフローチャートである。
【００８９】
（１）ＳI＝０のとき、
（１−１）SII＝０、ＳIII＝０の場合：受信語Ｖ′は正しいと判定する（ステップＳ６０１）。
（１−２）SII＝０、ＳIII≠０の場合：最後のバイトに誤りが存在し、E＝ＳIIIよりＳIIIを用いて訂正できる（ステップＳ６０２）。
（１−３）SII≠０、ＳIII＝０の場合：最後から２番目のバイトに誤りが存在し、E＝ＳIIよりＳIIを用いて訂正できる（ステップＳ６０３）。
（１−４）SII≠０、ＳIII≠０の場合：訂正できない誤りを検出したと判定する（ステップＳ６０４）。
【００９０】
（２）ＳI≠０のとき、
（２−１）SII≠０、ＳIII＝０、またはSII＝０、ＳIII≠０の場合の場合： 受信語Ｖ′中に訂正できない誤りを検出と判定する（ステップＳ６０６）。
（２−２）SII＝０、ＳIII＝０の場合：最後から３番目のバイトに誤りが存在したと判定する。このとき、Ｅ・Ｈ′T＝ＳIを満足するｔ／ｂ誤りＥを求めることにより、このバイトを訂正できる。また、このような関係を満足しない誤りＥであるとき、訂正できない誤りを検出したと判定する（ステップＳ６０７）。
（２−３）SII≠０、ＳIII≠０の場合：Ｅ・Ｈ′T＝ＳI、Ｅ・（γiH”）T＝SII、かつＥ・（γ2iH”）T＝ＳIIIがすべて成立するとき、ｉバイト目にこれらの関係を満足するｔ／ｂ誤りＥが生じたと判定し、Ｅ・Ｈ′T＝ＳIより誤りEを求めて訂正する。このとき、これらの関係を満足するｉが見つからなかったとき、またはこのような関係を満足するｔ／ｂ誤りＥが求められなかったとき、訂正できない誤りを検出したと判定する（ステップＳ６０５）。
【００９１】
前述した復号方法を実現する復号回路４の概略構成を図７に示す。
図１に示したように、復号回路４は、シンドローム生成回路１および誤り訂正回路５等から構成されている。そして、図７に示すように、誤り訂正回路５は、シンドローム（Ｓ）を基にしてビット誤りポインタ３７及びバイト誤りポインタ３６を生成するシンドロームデコード回路６、前記バイト誤りポインタ３６を基にして誤り訂正の可否を判断する誤り検出回路７、前記ビット誤りポインタ３７を基にして所定のビット値を反転させる反転回路８を含んでいる。
【００９２】
次に、復号回路４で行われる動作手順の概略を説明する。まず、シンドローム生成回路１は、Ｎビットからなる受信語（Ｖ′）３２を入力すると、Ｒビットのシンドローム（Ｓ）３３を生成する。次に、生成されたＲビットのシンドローム（Ｓ）３３は、一方でシンドロームデコード回路６に入力され、他方で誤り検出回路７に入力される。
【００９３】
シンドロームデコード回路６では、詳細は後述するが、入力されたシンドローム（Ｓ）の多段構成Ｓ＝[ＳI  ＳII  ＳIII]を利用し、各Ｓi（ｉ＝Ｉ、ＩＩ、ＩＩＩ）の値およびバイト幅のバイト誤りパターン（Ｅ）を基にして、[[Ｎ／ｂ]]（[[ｘ]]はｘを超える最小の整数）本のバイト誤りポインタ(ＥＢ0、ＥＢ1、……、ＥＢ[[N/b]]-1)３６、および誤りのビットを指摘するＫビットのビット誤りポインタ(ｅ0、ｅ1、……、ｅk-1)３７を生成する。
他方、誤り検出回路７では、詳細は後述するが、シンドロームデコード回路６で生成されたバイト誤りポインタ３６およびシンドローム３３を基にして、図６に示すロジックに従って誤り訂正が可能であるか否かを判別する。前記判別の結果、誤り訂正が不可能とみなされたときは訂正不可能誤り検出信号であるUCE(Uncorrectable Error)３５の値を出力するようにしている。例えば、前記UCE３５の値が“１”であれば、誤り検出回路７は２個のｔ／ｂ誤りを含む訂正不可能な誤りを検出したことを示している。
【００９４】
また、反転回路８は、シンドロームデコード回路６で生成されたＫビットのビット誤りポインタ（ｅ）３７、および受信語（Ｖ′）３２中のＫビットからなる情報ビットを基にして、ビット誤りポインタ（ｅ）３７に対応した受信語（Ｖ′）３２のビットを反転するようにしている。そして、反転回路８は、Ｋビットの誤り訂正された正しい情報語Ｖ*を出力情報データ３４として出力する。
次に、シンドローム生成回路１、シンドロームデコード回路６、誤り検出回路７、および反転回路８の具体的な構成例を、図４に示すS3/8EC-D3/8ED符号を用いて説明する。
【００９５】
（１）シンドローム生成回路１の構成
ここでは、シンドローム生成回路１の構成について詳細に説明する。
まず、シンドローム生成回路１では、Ｎ＝７９（＝６４＋１５）ビットからなる受信語（Ｖ′）３２を、下記の（式３０）に示すように表現したとき、この受信語（Ｖ′）３２を入力して下記の（式３１）に示すようなＳ0、Ｓ1、…Ｓ14からなるＲ＝１５ビットのシンドロームＳを生成する。前述したように、図４に示すS3/8EC-D3/8ED符号のパリティ検査行列が３段構成を有することから、これに対応してシンドロームＳも３つの部分に区分けし、ＳI＝（Ｓ0Ｓ1Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6）、ＳII＝（Ｓ7Ｓ8Ｓ9Ｓ10）、ＳIII＝（Ｓ11Ｓ12Ｓ13Ｓ14）とする。
【００９６】
Ｖ′＝（ｄ0′、ｄ1′、…、ｄ63′、ｃ0′、ｃ1′ …、ｃ14′）    ……（式３０）
Ｓ＝（          ＳI          ｜    ＳII     ｜      ＳIII      ）
＝（Ｓ0Ｓ1Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6｜Ｓ7Ｓ8Ｓ9Ｓ10｜Ｓ11Ｓ12Ｓ13Ｓ14）…（式３１）
【００９７】
前記の（式２９）に示したように、シンドロームＳ＝Ｖ′・ＨTより、転置したパリティ検査行列（ＨT）の各列は入力する情報に対応し、例えば、行列（ＨT）の第０列は入力情報のｄ0′に対応している。また、最後の単位行列は入力情報データ３０の検査情報に対応し、例えば、この部分における最初の列は検査情報のｃ0′に対応している。そこで、シンドローム（Ｓ）の各ビットを生成するには、符号であるパリティ検査行列（ＨT）の各行方向ごとに、“１”を有するビットに対応する受信語（Ｖ′）３２の受信情報をＧＦ（２）上で加算（ｍｏｄ２の計算）すればよい。
【００９８】
図８は、図４に示したS3/8EC-D3/8ED符号のパリティ検査行列を基にして構成したシンドローム生成回路１の一例である。図８に示すように、本実施例では、シンドローム生成回路１は１５個の多入力パリティチェック回路２１（０）、…２１（１４）から構成され、各多入力パリティチェック回路２１（ｘ）、（ｘ＝０，…，１４)には前記S3/8EC-D3/8ED符号のパリティ検査行列の対応する各行のビット“１”を有する受信情報（ｄy′およびｃx′）、（ｙ＝０，…，６３）が入力される。そして、前記入力された受信情報についてｍｏｄ２の計算を行い、その結果をＳxとして出力するようになっている。
【００９９】
なお、このシンドローム生成回路１の構成は、図５に示した検査情報（Ｃ）を生成するための符号化回路２の構成と基本的に同一である。検査情報（Ｃ）の生成とシンドローム（Ｓ）の生成とにおける唯一の違いは、符号化回路２の多入力パリティチェック回路２０（ｘ）が、入力情報データ（Ｄ）より選択された受信情報（つまり、ｄy）についてｍｏｄ２の計算を行うのに対して、シンドローム生成回路１の多入力パリティチェック回路２１（ｘ）は、入力情報データ（Ｄ）の他に検査情報（Ｃ）より選択された受信情報（つまり、ｄy′およびｃx′）についてｍｏｄ２の計算を行うようにしている点にある。
【０１００】
具体的には例えば、シンドロームＳのビットＳ5を作成するには、７９ビットの受信語ｄ0′、…、ｄ63′、ｃ0′、…、ｃ14′のうち、図４に示すパリティ検査行列の上から第６行目において「１」が存在する箇所に相当する１７ビットの受信情報ｄ5′、ｄ7′、ｄ13′、ｄ15′、ｄ21′、ｄ23′、ｄ29′、ｄ31′、ｄ37′、ｄ39′、ｄ45′、ｄ47′、ｄ53′、ｄ55′、ｄ61′、ｄ63′、ｃ5′の値について、２を法とする和（ｍｏｄ２）をとればよい。図８の多入力パリティチェック回路２１（５）は、前記１７ビットの受信情報が入力されて値Ｓ5を出力していることを示している。シンドロームＳの他のビットＳXについても同様である。
【０１０１】
（２）シンドロームデコード回路６の構成
次に、シンドロームデコード回路６について説明する。シンドロームデコード回路６の全体構成を図９に示す。図９に示すように、シンドロームデコード回路６は、誤りパターン生成回路６１、バイト誤りポインタ生成回路６２（０）…６２（７）、６２（Ｐ0）、６２（Ｐ1）、６２（Ｐ2）（以下、代表として６２（ｘ）と称する）、バイト内ビット誤りポインタ生成回路６３（０）…６３（７）（以下、代表として６３（ｘ）と称する）を備えている。
【０１０２】
バイト誤りポインタ生成回路６２（ｘ）は、誤りがどのバイトに生じたかを出力する回路である。バイト誤りポインタ生成回路６２（ｘ）は、検査情報も含めてバイトごとに構成され、バイト誤りポインタ生成回路６２（０）〜６２（７）は、情報バイト０から情報バイト７に対応し、バイト誤りポインタＥＢ0〜ＥＢ7を出力する。また、バイト誤りポインタ生成回路６２（Ｐ0）、６２（Ｐ1）６２（Ｐ2）は、検査バイト０、検査バイト１、検査バイト２に対応し、バイト誤りポインタＥＢP0〜ＥＢP2をそれぞれ出力する。
【０１０３】
また、バイト内ビット誤りポインタ生成回路６３（ｘ）は、各バイト内のどのビットが誤りであるかを出力する回路である。バイト内ビット誤りポインタ生成回路６３（ｘ）は、情報バイト毎に構成され、対応するバイト誤りポインタＥＢ0〜ＥＢ7をそれぞれ入力する。つまり、バイト内ビット誤りポインタ生成回路６３（０）〜６３（７）は、情報バイト０〜情報バイト７にそれぞれ対応し、各バイト内のどのビットが誤りかを指摘する各８ビットのバイト内ビット誤りポインタＥb0〜Ｅb7を出力する。ここで、検査情報部分に生じた誤りについても、符号機能として当然ながら同様に訂正できるが、復号後において検査情報は一般的に使用しないことが多い。このため、本実施例では、検査情報部分に誤り発生している場合であってもあえて訂正せずに、シンドロームデコード回路６は検査情報に対応したビット誤りポインタを出力しないこととしている。このため、図９には、検査ビット誤りポインタが出力される記載になっていない。なお、シンドロームデコード回路６が検査情報に対応したビット誤りポインタを出力するように構成してもよい。
【０１０４】
シンドロームデコード回路６は、複数個のバイト誤りポインタ生成回路６２（ｘ）及び複数個のバイト内ビット誤りポインタ生成回路６３（ｘ）をそれぞれに並列して動作させ、Ｋ＝６４ビットの情報ビット長を有する受信情報に対して、６４ビットのビット誤りポインタを最終的に出力する。
【０１０５】
また、誤りパターン生成回路６１は、シンドロームＳのＳI部分を基にバイト幅の誤りパターンを作成する回路である。誤りパターン生成回路６１からは、バイト幅（この例では８ビット）のバイト誤りパターンＥ３８が出力される。なお、本実施例の場合、シンドロームＳの上位７ビットがＳI、中位４ビットがＳII、下位４ビットがＳIIIに相当している。
【０１０６】
シンドロームデコード回路６の処理をより詳しくみると、図９に示すように、誤りパターン生成回路６１は、Ｒ＝１５ビットのシンドロームＳのうち、論理的処理を施した上位７ビットからなるＳIを入力する。次に、誤りパターン生成回路６１は、バイト誤りパターン（Ｅ）３８を生成して、これをバイト誤りポインタ生成回路６２（ｘ）及びバイト内ビット誤りポインタ生成回路６３（ｘ）へ出力する。
一方、シンドロームＳのうち、残りのＳII、ＳIIIについては、バイト誤りポインタ生成回路６２（ｘ）に入力される。
【０１０７】
バイト誤りポインタ生成回路６２（ｘ）は、入力されたバイト誤りパターン（E）３８とＳII、ＳIIIとから、バイト誤りポインタ（ＥＢ0〜ＥＢp2）３６を生成する。さらに、前記生成されたバイト誤りポインタ３６のうちのＥＢ0〜ＥＢ7とともに、バイト誤りパターン（Ｅ）３８が、バイト内ビット誤りポインタ生成回路６３（ｘ）に入力され、６４ビットのビット誤りポインタ（Ｅb0〜Ｅb7、つまりｅ0〜ｅ63）が生成される。
【０１０８】
次に、バイト誤りパターン生成回路６１の構成例を具体的に示す。図１０は、図４に示すS3/8EC-D3/8ED符号のパリティ検査行列に対し、得られた１５ビットのシンドロームＳのうち７ビットのシンドロームＳI＝（Ｓ0Ｓ1Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6）を用いて、８ビットの誤りパターンＥ＝（Ｅ0Ｅ1Ｅ2Ｅ3Ｅ4Ｅ5Ｅ6Ｅ7）を生成する回路である。
前述したように、この誤りパターン（Ｅ）とシンドローム（ＳI）との関係は、ＳI＝Ｅ・Ｈ′Tが成り立っている。また、前記（式２５）に示す７行８列の行列Ｈ′の構成より、次のことが言える。
【０１０９】
この符号はｔ＝３であることから、ある１バイトに３ビット以下の誤りが存在し、シンドロームＳIの「１」の数（すなわち重み）が１，２または３のとき、８ビットのバイト誤り中最後のビットには誤りがなく（すなわちＥ7＝０）、他の７ビットに誤りが存在してこれはシンドロームＳIと一致する。つまり、Ｅ0＝Ｓ0、Ｅ1＝Ｓ1、Ｅ2＝Ｓ2、Ｅ3＝Ｓ3、Ｅ4＝Ｓ4、Ｅ5＝Ｓ5、Ｅ6＝Ｓ6、Ｅ7＝０となる。
これは、前記の（式２５）に示す行列Ｈ′の構成が、前部に７×７の正方行列、後部にすべて「１」を要素とする１列が存在することによる。つまり、Ｅ7＝０であって他の７ビット中に誤りがあれば、この誤りは７ビットのシンドロームＳI＝（Ｓ0Ｓ1…Ｓ6）のパターンに等しくなる。また、最後のビットに誤りがあって（すなわちＥ7＝１）、他の７ビット中に１ビットまたは２ビットの誤りが存在するとき、他の７ビットの誤りパターンは前記７ビットからなるＳIをそれぞれ反転したパターンに一致する。つまり、Ｅ0＝＜Ｓ0＞、Ｅ1＝＜Ｓ1＞、Ｅ2＝＜Ｓ2＞、Ｅ3＝＜Ｓ3＞、Ｅ4＝＜Ｓ4＞、Ｅ5＝＜Ｓ5＞、Ｅ6＝＜Ｓ6＞、Ｅ7＝１となる。ここで、＜Ｓi＞はＳi（ｉ＝０、１、…、６）を反転したビット情報を表す。すなわち、Ｅ7＝１のときで他に１ビットまたは２ビットの誤りがあるとき、シンドロームＳIの重みは６または５となるはずで、これを反転した＜Ｓi＞の重みは１または２となる。また、この反転した＜Ｓi＞が最後のビット誤りを除く７ビットの誤りパターンとなる。
【０１１０】
以上の関係をハードウェア構成としての具体的な回路によって実現したものが図１０に示す誤りパターン生成回路６１である。図１０に示す７×７ソート回路４０ａ、４０ｂは、入力される７ビットのシンドロームＳI情報中の重み（「１」の数）を数え、その重みの数だけ出力の上位ビットから「１」を連続して表記する回路である。例えば、７ビットの入力情報であるＳIに「１」が３個存在する場合、この回路の出力７ビットのうち上位３ビットはすべて「１」を、残りの４ビットはすべて「０」を出力する回路である。
【０１１１】
７×７ソート回路４０ａ、４０ｂをさらに具体化した回路を図１１に示す。図１１に示すように、ＳIの入力情報であるＳ0からＳ6の７ビットの入力情報がソートされ、２入力ＯＲゲート回路と２入力ＡＮＤゲート回路とが対になって構成された２入力２出力回路をセルとして、ＳIの７入力に対してこのセルを多段に接続して構成している。このソート回路は、一般に、ｎビット入力中に「１」の数がｘ個存在すれば、ｎビット出力のうち上位ｘ個に「１」を出力し、残りの出力はすべて「０」を出力する回路である。なお、この回路の一般的構成は、S.J.Piestrak,”The Minimal Test Set for Multioutput Threshold Circuits Implemented as Sorting Networks” IEEE Transactions on Computers, Vol.42, No.6, pp700-712, June 1993に述べられている。
【０１１２】
図１０に示す７入力７出力の回路である７×７ソート回路４０ａ、４０ｂでは、このセルを１６個（すなわち３２ゲート）使用し、最大６段のセル（６ゲート段）で実現することが可能である。例えば、入力情報ＳIとして（Ｓ0Ｓ1Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6）＝（００１０１１０）のような重み３の情報のとき、出力は（Ｗ0Ｗ1Ｗ2Ｗ3Ｗ4Ｗ5Ｗ6）＝（１１１００００）となる。図１０では、入力情報ＳIに重み１、２または３を有する場合（すなわちＥ7＝０のとき）、および反転ゲート４８でＳIを反転した＜ＳI＞に重み１または２を有する場合（すなわちＥ7＝１のとき）に対して、それぞれ７×７ソート回路４０ａ、４０ｂを適用する。
【０１１３】
特に、図１０の上部に示す７×７ソート回路４０ａは、ＳIを入力する場合のソート回路であり、出力としてＷ0Ｗ1Ｗ2の上位３ビットの論理和を３入力ＯＲゲート回路４１で実行する。ここで、Ｗ0、Ｗ1、Ｗ2の少なくとも何れか１つは「１」であり他のＷiがすべて「０」の場合、７ビットのシンドロームＳIは、２入力ＡＮＤゲート回路４３、さらには２入力ＯＲゲート回路４２を通り、Ｅ0からＥ6の７ビットの誤りパターン（Ｅ）となる。
また、図１０中の下部に示す７×７ソート回路４０ｂは、反転ゲート回路４８から出力されたＳIの反転情報＜ＳI＞の７ビットを入力する場合のソート回路である。反転情報＜ＳI＞に１ビットまたは２ビットの「１」が存在するとき、７×７ソート回路４０ｂの出力Ｗ0、Ｗ1の上位２ビットの論理和を２入力ＯＲゲート回路４２で実行する。ここで、Ｗ0、Ｗ1がの少なくとも何れか１つは「１」であり他のＷiがすべて「０」の場合、＜Ｓ0＞から＜Ｓ6＞のパターンをＡＮＤゲート回路４３、さらにはＯＲゲート回路４２を通ったＥ0からＥ6の７ビットの誤りパターン（Ｅ）を得ることができる。
【０１１４】
また、Ｅ7＝１が出力されるのは、バイト中８ビット目に１ビットの誤りがある場合、またはこの８ビット目とさらに他の１ビットまたは２ビットの誤りがある場合である。よって、前者の場合、ＳIはすべて「１」であり、したがって、７ビットのＳIを入力した７入力ANDゲート回路４４の出力が「１」のときである。また、後者の場合、ＳIの反転情報に重み１または２が存在する場合であり、これは７×７ソート回路４０ｂの上位出力Ｗ0、Ｗ1のＯＲゲート回路４２の出力が「１」で、かつ、他のＷiがすべて「０」であることを示すＮＯＲゲート回路４５の出力が「１」のときである。
したがって、これらのいずれかのとき、ＯＲゲート回路４２を通してＥ7＝１を得ることができる。その他の場合、Ｅ7＝０である。
【０１１５】
一方、前記の（式１）に示すパリティ検査行列（Ｈ）の最上段に、ｂ×ｂの単位行列Ｉbを用いて構成する場合、例えば、S3/8EC-D3/8ED-S8ED符号の検査行列の場合、明らかにＳI＝Ｅとなり、Ｅ0Ｅ1Ｅ2Ｅ3Ｅ4Ｅ5Ｅ6Ｅ7はＳ0Ｓ1Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6にそれぞれ一致することになる。したがって、この場合、図１０に示すような構成を有する誤りパターン生成回路６１を備える必要がなく、バイト幅のバイト誤りパターン（E）３８は、入力情報であるシンドロームＳIをそのまま使用して、バイト誤りポインタ生成回路６２（ｘ）およびバイト内ビット誤りポインタ生成回路６３（ｘ）に入力するようにすればよい。
【０１１６】
次に、バイト誤りポインター生成回路６２（ｘ）の具体的な回路構成の一例を示す。図１２は、図４に示したS3/8EC-D3/8ED符号のパリティ検査行列に対する、バイト誤りポインタ生成回路６２（ｘ）の構成例を示している。ここでは特に、バイト誤りポインター生成回路６２（１）が、バイト誤りポインタＥＢ1を出力する例で説明するが、他のバイト誤りポインター生成回路６２（ｘ）も同様であることは言うまでもない。
【０１１７】
前述したように、バイト誤りポインター生成回路６２（１）は、誤りパターン生成回路６１によりシンドロームＳのＳIから生成されたバイト誤りパターン（Ｅ）３８、およびシンドロームＳII、ＳIIIを入力することにより、バイト誤りポインタ（ＥＢ1）を生成する。ここで、情報バイトｉにおいては、ＳII＝Ｅ・（γiH″）TおよびＳIII＝Ｅ・（γ2iH″）Tが成立することから、この両方の関係が成立するときにのみ、この情報バイトｉに誤りが存在することになる。今、ｉ＝１として、このバイト誤りポインターＥＢiを「１」に設定し、行列H″として前記の（式２６）に示す行列を使用する。また、ＧＦ（２）上の４次の原始多項式ｇ（ｘ）＝ｘ4＋ｘ＋１の根をγとする。このとき、前記の（式２６）に示すH″は、γのべき乗で表すと、前述したように、次の（式３２）のように表される。
【０１１８】
【数１２】
2005176244.tif 000014
【０１１９】
したがって、γH″、γ2H″は、それぞれ次の（式３３）、（式３４）で表すことができる。
【数１３】
2005176244.tif 000015
前記（式３３）、（式３４）で表される行列は、図４に示した検査行列の情報バイト１に相当する２段目（図４に示すＡ部分）、３段目の行列（図４に示すＢ部分）に一致していることを確認することができる。
これから、ＳII＝Ｅ・（γH″）Tは、次の（式３５）に示す関係がすべて成立していなければならない。
【数１４】
2005176244.tif 000016
ここで、前記（式３５）中におけるプラス記号を丸印で囲った記号は、２を法とする和を示している。
【０１２０】
また、ＳIII＝Ｅ・（γ2H″）Tは、次の（式３６）に示す関係がすべて成立していなければならない。
【数１５】
2005176244.tif 000017
【０１２１】
前記（式３５）、（式３６）を満足する回路構成例が図１２に示すようなバイト誤りポインター生成回路６２（１）となる。図１２に示すバイト誤りポインタ（ＥＢ1）は、情報バイト１に対応する誤りポインタであり、５０は８入力ＮＯＲゲート回路である。５１はパリティチェック回路５１である。図のパリティチェック回路５１は、シンドロームＳII、ＳIIIおよびバイト誤りパターン（E）３８を入力した際、前記の（式３５）、（式３６）がすべて成立するときに、情報バイト１誤りポインタ（ＥＢ1）が「1」となるように構成されている。また、他のバイト誤りポインタ（ＥＢx）の生成の場合も同様な回路構成によって実現することができる。
【０１２２】
次に、バイト内ビット誤りポインタ生成回路６３（ｘ）の構成について述べる。このバイト内ビット誤りポインタ生成回路６３（ｘ）は、情報バイト８バイトの各バイトに対して同一の構成からなる回路を備えている。本実施例では、その一例を図１３に示す。図１３のバイト内ビット誤りポインタ生成回路は、情報バイト１に対する回路６３（１）の場合を示している。図１３に示すｅ8からｅ15は、情報バイト１内のビット８からビット１５に対するそれぞれのビット誤りポインタである。図１３に示すように、バイト内ビット誤りポインタ生成回路６３（１）は、図１０に示す誤りパターン生成回路６１により生成されたバイト内の誤りを具体的に示す８ビットのバイト誤りパターン（E）３８と、図１２に示すバイト誤りポインタ生成回路６２（１）により生成されたバイト１誤りポインター（ＥＢ1）とから、ビット誤りポインタｅ8〜ｅ15を出力する。
【０１２３】
すなわち、図１３に示すＥ0からＥ7は、誤りパターン生成回路６１の８ビットの出力バイト誤りパターン（E）から得られるＥ0、…、Ｅ7であり、ＡＮＤ回路７０によりバイト１誤りポインター（ＥＢ1）とのAND論理がそれぞれ施されて、ビット誤りポインタｅ8からｅ15が生成されるようになっている。ここでは、情報バイト１に対する回路６３（１）を例にして説明したが、他の情報バイトのビット誤りポインタについてもまったく同様である。
【０１２４】
（３）誤り検出回路７の構成
次に、誤り検出回路７について述べる。この誤り検出回路７は、受信語（Ｖ′）３２中にｔ／ｂ誤りをそれぞれに有している２バイトの誤り、およびバイト中にｔビットを越える誤り等、訂正することが不可能な誤りを検出する機能を有している。誤り検出回路７が前述したような訂正不可能な誤りを検出したとき、ＵＣＥの信号３５を「１」として出力するようにしている。このための論理は次のように考えればよい。シンドロームＳが非零であり、かつ図９に示すバイト誤りポインタ生成回路６２（ｘ）からのバイト誤りポインタＥＢXがすべて「０」である情報が入力されたとき、誤り検出回路７は、符号として何らかの誤りを検出したにもかかわらず、すべてのバイトにおいて訂正できる誤りが存在していないケースと判断する。つまり、訂正できない誤りが存在してこれを検出した場合であることを表すために、ＵＣＥの信号３５を「１」に設定する。
【０１２５】
前記論理内容を具体的に構成する回路例を図１４に示す。図１４に示す回路は、本実施例における図４に示したS3/8EC-D3/8ED符号のパリティ検査行列に対する誤り検出回路７になっている。図１４に示すように、検出回路７は、１５ビットのシンドロームＳが入力される入力ＯＲゲート回路７５と、情報データの８バイトに対応する８ビットのバイト誤りポインタＥＢ0〜ＥＢ7および検査情報の３バイトに対応する３ビットのバイト誤りポインタＥＢP0〜ＥＢP2の計１１ビットが入力される１１入力NＯＲゲート回路７６と、前記入力ＯＲゲート回路７５および１１入力NＯＲゲート回路７６の出力の論理積を施すＡＮＤゲート回路７７とから構成されている。
【０１２６】
（４）反転回路８の構成
最後に、反転回路８の構成について述べる。例えば、情報バイト１に対して具体的に構成した反転回路８を図１５に示す。図１５に示す反転回路８は、誤りの箇所を具体的に指摘された入力ビットについて、現在のビット値の反転を行って受信語（Ｖ′）３２を訂正する回路である。前述したように、Kビットからなる受信情報に対して、各入力ビットに誤りが存在するか否かを示すビット誤りポインタＥbは、バイト内ビット誤りポインタ生成回路６３（ｘ）によって生成されるので、このビット誤りポインタＥbを用いて反転回路を構成すればよい。具体的には例えば、図１５には、情報バイト１に対する反転回路を示している。
【０１２７】
図１５において、ｄ8′〜ｄ15′は、受信語（Ｖ′）３２′の情報バイト１に相当する８入力ビットであり、ｄ8*〜ｄ15*は、前記情報バイト１に相当する各８ビットに対する訂正後の出力ビットである。反転回路８は、複数の排他的論理和回路８１を有している。排他的論理和回路８１は、前記情報バイト１に相当する入力ビットｄ8′〜ｄ15′のそれぞれのビットに対して、対応するビット誤りポインタｅi（ｉ＝８、…、１５）との排他的論理和をとり、例えば、ビット誤りポインタが「１」のとき、入力ビット値が反転されて訂正されることになる。なお、反転回路８は、各情報バイトにそれぞれ対応するようにするため合計８個の排他的論理和回路８１を備えて構成されるようにしている。したがって、Ｋ＝６４ビットの受信語（Ｖ′）３２の情報に対しては６４個の排他的論理和回路が必要となる。
【０１２８】
前述したように、本発明では、バイト中にｔビットまでの誤りを有する１スポッティバイトの誤りを訂正し、かつ各２バイト中にｔビットまでの誤りを有する２スポッティバイト誤りを検出する符号機能等に対して一般性のある符号構成を与えるとともに、誤りの訂正・検出が実現できる回路である符号化・復号回路構成を示して、検査情報が具体的に生成できること、および誤りが具体的に訂正・検出できることを示した。
また、以上の説明では、主としてメモリ装置に着目して本発明の適用を述べたが、本発明はそれに限定されるものではなく、例えば、このようなバイト単位で物理的に独立した回路、モジュール、装置から構成され、この中で限定した数の誤りが生じる可能性の高い一般の情報システム等に適用可能である。また、光通信回路、バス線回路等の通信または伝送のための回路、装置またはシステムにも適用可能である。
【０１２９】
また、本発明の目的は、本実施の形態のスポッティバイト誤り訂正・検出装置の機能を実現するソフトウェアのプログラムコードを記憶した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読みだして実行することによっても、達成されることは言うまでもない。
【０１３０】
この場合、記憶媒体から読み出されたプログラムコード自体が本実施の形態の機能を実現することとなり、そのプログラムコードを記憶した記憶媒体及び当該プログラムコードは本発明を構成することとなる。プログラムコードを供給するための記憶媒体としては、ＲＯＭ、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード等を用いることができる。
【０１３１】
また、コンピュータが読みだしたプログラムコードを実行することにより、前記本実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ等が実際の処理の一部又は全部を行い、その処理によって本実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１３２】
【図１】本発明の一実施形態であるスポッティバイト誤り訂正・検出装置の概略構成を示すブロック図である。
【図２】スポッティバイト誤り訂正・検出装置における全体動作の処理手順を示すフローチャートである。
【図３】パリティ検査行列の一例であって、符号長Ｎ＝１３６ビット、情報長Ｋ＝１２１ビット、検査長Ｒ＝１５ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する（１３６、１２１）S3/8EC-D3/8ED符号のパリティ検査行列を示す図である。
【図４】図３に示すパリティ検査行列を短縮した符号の一例であって、符号長Ｎ＝７９ビット、情報長Ｋ＝６４ビット、検査長Ｒ＝１５ビット、バイト長ｂ＝８ビット、バイト内訂正ビット長ｔ＝３ビットの符号パラメータを有する短縮（７９、６４）S3/8EC-D3/8ED符号のパリティ検査行列を示す図である。
【図５】図４に示す（７９、６４）S3/8EC-D3/8ED符号をもとに構成した符号化回路の具体例であり、Ｋ＝６４ビットのデータ入力情報からパリティ検査行列により１５ビットの検査情報を生成する回路の構成図である。
【図６】本実施形態の復号回路による誤りの訂正および検出の処理ロジックを示したフローチャートである。
【図７】本発明で開示された機能を有する符号に対する復号回路の概略構成を示すブロック図である。
【図８】図４に示す(79, 64)S3/8EC-D3/8ED符号をもとに具体的に構成したシンドローム生成回路を説明する概念図である。
【図９】図４に示す（７９、６４）S3/8EC-D3/8ED符号に対するシンドロームデコード回路の構成を示すブロック図である。
【図１０】図４に示す（７９、６４）S3/8EC-D3/8ED符号に対する誤りパターン生成回路の一例を示す構成図である。
【図１１】図１０に示す７×７ソーティング回路の一例を示す構成図である。
【図１２】図４に示す（７９、６４）S3/8EC-D3/8ED符号に対する情報バイト１誤りポインター生成回路の一例を示す構成図である。
【図１３】図４に示す（７９、６４）S3/8EC-D3/8ED符号に対する情報バイト１内ビット誤りポインター生成回路の一例を示す構成図である。
【図１４】図４に示す（７９、６４）S3/8EC-D3/8ED符号に対する誤り検出回路の一例を示す構成図である。
【図１５】情報バイト１に対する反転回路の一例を示す構成図である。
【符号の説明】
【０１３３】
１    シンドローム生成回路
２    符号化回路
３    メモリ（または情報伝送路）
４    復号回路
５    誤り訂正回路
６    シンドロームデコード回路
７    誤り検出回路
８    反転回路
２０    多入力パリティチェック回路
２１    多入力パリティチェック回路
３０    入力情報データ
３１    送信語
３２    受信語
３３    シンドローム
３４    出力情報データ
３５    訂正不可能誤り検出信号（ＵＣＥ）
３６    ビット誤りポインタ
３７    バイト誤りポインタ
４０ａ    ７×７ソート回路
４０ｂ    ７×７ソート回路
４１    ３入力論理和（ＯＲゲート）回路
４２    ２入力論理和（ＯＲゲート）回路
４３    ２入力論理積（ＡＮＤゲート）回路
４４    ７入力ＡＮＤ／ＮＡＮＤゲート回路
４５    ５入力ＮＯＲゲート回路
５０    ８入力ＮＯＲゲート回路
５１    ５入力パリティチェック回路
６１    誤りパターン生成回路
６２    バイト誤りポインタ生成回路
６３    バイト内ビット誤りポインタ生成回路
７０    ２入力ＡＮＤゲート回路
７５    １５入力ＯＲゲート回路
７６    １１入力NＯＲゲート回路
７７    ２入力ＡＮＤゲート回路
８１    排他的論理和回路
【図１】
2005176244.tif 000020
【図２】
2005176244.tif 000021
【図３】
2005176244.tif 000022
【図４】
2005176244.tif 000023
【図５】
2005176244.tif 000024
【図６】
2005176244.tif 000025
【図７】
2005176244.tif 000026
【図８】
2005176244.tif 000027
【図９】
2005176244.tif 000028
【図１０】
2005176244.tif 000029
【図１１】
2005176244.tif 000030
【図１２】
2005176244.tif 000031
【図１３】
2005176244.tif 000032
【図１４】
2005176244.tif 000033
【図１５】
2005176244.tif 000034