(57)【要約】【課題】  ”２”を法としない通常の加減乗除命令を用いて、データ値を符号化し、誤り検出および誤り訂正を実行する。【解決手段】  データと補正値との積を、べき乗剰余環における”２”を原始根とする素数である除数で除して第１の剰余を生成する処理を、除算命令を用いてコンピュータにより実行する。補正値は、誤りのない符号が除数で割りきれるように設定され、べき乗剰余環は、除数を法とする。そして、データに第１の剰余を付加して符号を生成する処理をコンピュータにより実行する。【選択図】    図１
2014072852.tif 000002
【特許請求の範囲】
【請求項１】
データと補正値との積を、べき乗剰余環における”２”を原始根とする素数である除数で除して第１の剰余を生成する処理を、除算命令を用いてコンピュータにより実行し、
前記データに前記第１の剰余を付加して符号を生成する処理をコンピュータにより実行し、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする符号化方法。
【請求項２】
前記第１の剰余に定数を付加して第２の剰余を生成し、
前記データの下位ビット側に、前記第１の剰余の代わりに前記第２の剰余を付加して前記符号を生成し、
前記第２の剰余は、”０”を除き、かつ前記除数の倍数を除く付加値を前記符号に付加した値が前記除数で割りきれるように設定されること
を特徴とする請求項１に記載の符号化方法。
【請求項３】
前記第２の剰余は、２進数で表される前記付加値のビット数を”ｊ”とする場合に、”２”を底とし、指数を”−ｊ”とするべき乗と前記付加値との積を、前記第１の剰余から減じて得られる値を、前記除数で除して得られる剰余であること
を特徴とする請求項２に記載の符号化方法。
【請求項４】
前記符号は、前記データを、前記第１の剰余の上位ビット側に付加して生成され、
前記補正値は、２進数で表される前記除数のビット数を”ｍ”とする場合に、”２”を底とし、指数を”ｍ”とするべき乗と”−１”との積を前記除数で除して得られる剰余であること
を特徴とする請求項１に記載の符号化方法。
【請求項５】
前記符号は、前記第１の剰余を、前記データの上位ビット側に付加して生成され、
前記補正値は、２進数で表される前記データのビット数を”ｄ”とする場合に、”２”を底とし、指数を”−ｄ”とするべき乗と”−１”との積を前記除数で除して得られる剰余であること
を特徴とする請求項１に記載の符号化方法。
【請求項６】
前記符号は、前記データを第１のシフト量だけシフトした値に、前記第１の剰余を第２のシフト量だけシフトした値を付加し、かつシフトしたデータとシフトした第１の剰余とが互いに重複しないように生成され、
前記補正値は、”２”を底とし、前記第１のシフト量と前記第２のシフト量との差を指数とするべき乗と”−１”との積を前記除数で除して得られる剰余であること
を特徴とする請求項１に記載の符号化方法。
【請求項７】
データと補正値との積を、べき乗剰余環における”２”を原始根とする除数で除して生成される第１の剰余が、前記データに付加されて生成された符号を、前記除数で除して第２の剰余を生成する処理を、除算命令を用いてコンピュータにより実行し、
前記第２の剰余が”０”のときに、前記符号に誤りがないことを検出し、前記第２の剰余が”０”でないときに、前記符号に誤りがあることを検出する処理をコンピュータにより実行し、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする誤り検出方法。
【請求項８】
前記第２の剰余が”０”でないときに、前記符号において、前記第２の剰余に一意に対応する、誤りが発生したビット位置と誤り値とを求め、
求めた前記ビット位置に前記誤り値と逆の論理を書き込むことで誤りを訂正すること
を特徴とする請求項７に記載の誤り検出方法。
【請求項９】
前記第２の剰余が”０”でないときに、前記第２の剰余と同じ値が剰余となる”２”を底とするべき乗の指数を求め、
前記指数が、前記除数から１を引いた値の２分の１未満の場合に、２進数で表される前記符号において、前記指数をビット番号とするビット値が論理０から論理１に誤っていることを検出し、
前記指数が、前記除数から”１”を引いた値の２分の１以上の場合に、２進数で表される前記符号において、前記除数から”１”を引いた値の２分の１を前記指数から引いた値をビット番号とするビット値が論理１から論理０に誤っていることを検出すること
を特徴とする請求項８に記載の誤り検出方法。
【請求項１０】
前記除数は、複数の素数の積から”１”を減じた値になるように設定され、
前記第２の剰余を底とし、前記除数から”１”を減じた値を前記複数の素数でそれぞれ除して得られる整数を指数とするべき乗を、前記除数で除して、前記整数毎に複数の第３の剰余を求め、
”２”を底とし、前記整数を指数とするべき乗をそれぞれ定数値とする場合に、前記定数値を底とするべき乗を前記除数で除して得られる剰余が、前記第３の剰余になる指数値を、前記整数毎に求め、
誤りが発生したビット番号を前記各整数で除した剰余が、前記整数に対応する前記指数値になる関係を用いて、中国剰余定理より誤りが発生したビット番号を求めること
を特徴とする請求項８に記載の誤り検出方法。
【請求項１１】
除算命令に基づいて動作し、データと補正値との積を、べき乗剰余環における”２”を原始根とする素数である除数で除して第１の剰余を生成する第１演算部と、
前記データに前記第１の剰余を付加して符号を生成する第２演算部と
を備え、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする符号化装置。
【請求項１２】
除算命令に基づいて動作し、データと補正値との積を、べき乗剰余環における”２”を原始根とする除数で除して生成される第１の剰余が、前記データに付加されて生成された符号を、前記除数で除して第２の剰余を生成する第１演算部と、
前記第２の剰余が”０”のときに、前記符号に誤りがないことを検出し、前記第２の剰余が”０”でないときに、前記符号に誤りがあることを検出する第２演算部とを備え、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする誤り検出装置。
【請求項１３】
データと補正値との積を、べき乗剰余環における”２”を原始根とする素数である除数で除して第１の剰余を生成する処理を、除算命令を用いてコンピュータに実行させ、
前記データに前記第１の剰余を付加して符号を生成する処理をコンピュータに実行させ、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする符号化プログラム。
【請求項１４】
データと補正値との積を、べき乗剰余環における”２”を原始根とする除数で除して生成される第１の剰余が、前記データに付加されて生成された符号を、前記除数で除して第２の剰余を生成する処理を、除算命令を用いてコンピュータに実行させ、
前記第２の剰余が”０”のときに、前記符号に誤りがないことを検出し、前記第２の剰余が”０”でないときに、前記符号に誤りがあることを検出する処理をコンピュータに実行させ、
前記補正値は、誤りのない符号が前記除数で割りきれるように設定され、前記べき乗剰余環は、前記除数を法とすること
を特徴とする誤り検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置、誤り検出装置、符号化方法、誤り検出方法、符号化プログラムおよび誤り検出プログラムに関する。
【背景技術】
【０００２】
デジタル機器で扱われるデータ値は、ノイズ等により論理値が変化することで誤りが発生する。例えば、データ値の誤りは、データ値と誤り検出符号値とを用いてシンドローム値を計算することで検出される。また、シンドローム値から誤ったデータ値のビット位置を求めることで、データの誤りが訂正される（例えば、特許文献１、２参照）。例えば、誤り訂正符号値は中国人剰余定理を利用して求められる（例えば、特許文献３参照）。また、離散対数値の演算にＰｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムを用いることで、演算の負荷は軽くなる（例えば、特許文献４、５参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−２２４０４９号公報
【特許文献２】特開２０００−１３２４１２号公報
【特許文献３】特開平６−２１９１６号公報
【特許文献４】特開２００９−１１６９１２号公報
【特許文献５】特開２００７−１２８００１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の誤り検出および誤り訂正は、”２”を法とする（２進数を用いた）排他的加算を用いている。一般に、ＣＰＵ（Central Processing Unit）は、四則演算回路により演算を実行するため、ＣＰＵに排他的加算を実行させる場合、効率が悪い。このため、一般的には、”２”を法とする排他的加算による誤り検出および誤り訂正は、ＣＰＵとは異なる専用のハードウエアを用いて実行される。
【０００５】
１つの側面では、本発明の目的は、”２”を法としない通常の加減乗除命令を用いて、データ値を符号化し、誤り検出および誤り訂正を実行することである。
【課題を解決するための手段】
【０００６】
本発明の一形態における符号化方法では、コンピュータの除算命令を用いて、データと補正値との積を、べき乗剰余環における”２”を原始根とする素数である除数で除して第１の剰余を生成し、データに第１の剰余を付加して符号を生成し、補正値は、誤りのない符号が除数で割りきれるように設定され、べき乗剰余環は、除数を法とする。
【０００７】
本発明の別の一形態における誤り検出方法では、データと補正値との積を、べき乗剰余環における”２”を原始根とする除数で除して生成される第１の剰余が、データに付加されて生成された符号を、コンピュータの除算命令を用いて、除数で除して第２の剰余を生成し、補正値は、誤りのない符号が除数で割りきれるように設定され、べき乗剰余環は、除数を法としており、第２の剰余が”０”のときに、符号に誤りがないことを検出し、第２の剰余が”０”でないときに、符号に誤りがあることを検出する。
【発明の効果】
【０００８】
２を法としない加減乗除命令を用いて、データ値を符号化でき、誤り検出および誤り訂正を実行できる。
【図面の簡単な説明】
【０００９】
【図１】一実施形態における符号化方法の例を示している。
【図２】一実施形態における誤り検出方法の例を示している。
【図３】除数値を”１３”にする場合の指数値、ビット情報、剰余値の関係の例を示している。
【図４】除数値が”１３”の場合において、シンドローム値、ビット情報、誤りが発生したビット位置および訂正値との関係の例を示している。
【図５】別の実施形態における符号化方法の例を示している。
【図６】符号値内での誤り検出符号値の配置の例を示している。
【図７】別の実施形態における符号化方法の例を示している。
【図８】図７で生成される符号値に付加値を付加した符号値の例を示している。
【図９】別の実施形態における符号化方法の例を示している。
【図１０】図９で生成される符号値の例を示している。
【図１１】別の実施形態における符号化方法の例を示している。
【図１２】図１１で生成される符号値の例および符号値に付加される付加値の例を示している。
【図１３】別の実施形態における誤り検出方法の例を示している。
【図１４】図１から図１３に示した符号化方法および誤り検出方法を実現するデータ処理装置の例を示している。
【図１５】図１から図１３に示した符号化方法および誤り検出方法を実現するデータ処理装置の別の例を示している。
【発明を実施するための形態】
【００１０】
以下、図面を用いて実施形態を説明する。
図１は、一実施形態における符号化方法の例を示している。例えば、図１に示す符号化方法は、図１４および図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図１に示す各処理は、ＣＰＵ等のプロセッサにより実行される。
【００１１】
図１において、符号Ｄは、符号化する元のデータ値である。符号Ｍは、誤り検出の演算および誤り訂正の演算で使用する法値（除数値）であり、Ｍを法とする”べき乗剰余環”において”２”を原始根とする素数である。図３等に示す”１３”は、この条件を満たす除数Ｍの例である。符号Ｃは、データＤに付加する誤り検出符号値であり、符号Ｅは、データＤと誤り検出符号Ｃとを組み合わせた符号値である。符号Ｋは、誤り検出符号Ｃを算出する際に、除数Ｍの剰余値を補正する補正値である。後述するように、補正値Ｋは、除数Ｍから一意に決定できる。除数Ｍおよび補正値Ｋは、図１の処理が実行される前に予め求められている。符号ＭＬＥＮは、除数Ｍを２進数で表した場合のビット長値である。符号”＜＜”は、データＤ等の数値をシフトすることを示している。
【００１２】
補正値Ｋは、データＤに誤り検出符号Ｃを付加して符号Ｅを生成する場合に、除数Ｍで割り切れる符号Ｅを生成するためのものであり、式（１）により算出される。符号”≡”は、剰余演算において、合同値の正の最小値または左辺に”０”を代入することを示す。
Ｋ≡−２ＭＬＥＮ  （ｍｏｄ  Ｍ）  ‥‥（１）
【００１３】
例えば、除数Ｍが”１３”のとき、”１３”は２進数で”１１０１”のため、除数Ｍのビット長値ＭＬＥＮは”４”である。式（１）より、補正値Ｋは、”...、−１６、−３、１０、２３、３６、...”をとり得る。このうち、除数Ｍ以下で正の値（すなわち、１０）が、補正値Ｋとして予め選択される。
【００１４】
まず、ステップＳ１００において、プロセッサは、データＤと補正値Ｋの積を除数Ｍで除して剰余を算出し、算出した剰余を誤り検出符号Ｃとする。例えば、データＤと補正値Ｋの積は、乗算命令を用いて実行され、剰余の算出は、除算命令を用いて実行される。ビット長を短くするために、検出符号値Ｃは、除数Ｍ以下で正の値の剰余を選択することが好ましい。例えば、データＤは、プロセッサの外部から供給される。
【００１５】
なお、ステップＳ１００は、”ｔｅｍｐ≡Ｄ  （ｍｏｄ  Ｍ）”と、”Ｃ≡ｔｅｍｐ×Ｋ  （ｍｏｄ  Ｍ）”の２つのステップに分けられてもよい。符号ｔｅｍｐは、演算で一時的に使用する変数である。２つのステップに分けて除算命令を実行することで、除算命令で使用する数値のビット数を少なくでき、計算の負荷を軽減できる。
【００１６】
ステップＳ１１０において、プロセッサは、例えば、乗算命令あるいはシフト命令を用いて、データＤをビット長値ＭＬＥＮだけ上位ビット側にシフトし、シフトしたデータ値に誤り検出符号Ｃを付加する。すなわち、データＤの下位ビット側に誤り検出符号Ｃが付加され、符号Ｅが生成される。符号Ｅを２進数で表す場合のビット長は、ビット長値ＤＬＥＮとビット長値ＭＬＥＮの和になる。ここで、ビット長値ＤＬＥＮは、データＤを２進数で表す場合のビット長を示す。例えば、生成した符号Ｅは、レジスタやメモリ等の記憶領域に格納される。
【００１７】
式（１）で示した補正値Ｋを用いて、符号Ｅを算出する場合、式（２）、（３）、（４）が成立するため、符号Ｅは、除数Ｍで割り切れる。
Ｃ≡Ｄ・Ｋ≡−（Ｄ・２ＭＬＥＮ））  （ｍｏｄ  Ｍ）  ‥‥（２）
Ｅ≡（Ｄ＜＜ＭＬＥＮ）＋Ｃ≡（Ｄ・２ＭＬＥＮ）＋Ｃ  (ｍｏｄ  Ｍ）  ‥‥（３）
Ｅ≡０（ｍｏｄ  Ｍ）  ‥‥（４）
【００１８】
式（３）において、”Ｄ＜＜ＭＬＥＮ”および”Ｄ・２ＭＬＥＮ”は、データＤを除数Ｍのビット長値ＭＬＥＮだけ左シフトすることを示している。なお、符号”＜＜ａ”は、”ａ”が正の場合に左シフトを示し、”ａ”が負の場合に右シフトを示す。誤り検出符号Ｃは、除数Ｍによる除算によって得られる剰余値であるため、誤り検出符号Ｃのビット長値は”ＭＬＥＮ”以下である。このため、式（３）では、誤り検出符号Ｃのビット長値は”ＭＬＥＮ”としている。
【００１９】
図１に示した符号化方法では、排他的演算を用いずに四則演算（すなわち、加減乗除算）を用いて符号Ｅが生成される。したがって、専用のコントローラを用いることなく、ＣＰＵ等のプロセッサを用いて、符号Ｅを生成できる。
【００２０】
図２は、一実施形態における誤り検出方法の例を示している。例えば、図２に示す誤り検出方法は、図１の処理により生成された符号Ｅの１ビット誤りを検出する場合に実行され、図１４および図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図２の各処理は、ＣＰＵ等のプロセッサにより実行される。なお、図１の処理を実行するプロセッサと、図２の処理を実行するプロセッサとは、同じでもよく、互いに相違してもよい。
【００２１】
図２において、符号Ｓは、符号Ｅにおいて誤りが発生したビットの位置を検出するときに使用するシンドローム値である。符号Ｆ（Ｓ，Ｍ）は、シンドロームＳから、誤りが発生したビットの位置を求める関数である。符号ｂｉｔは、誤りが発生したビットの位置を示すビット情報であり、関数Ｆ（Ｓ，Ｍ）により特定される。符号Ｅ［値］の[値]は、符号Ｅ内のビット番号を示しており、符号Ｅ［値］は、[値]で示されるビット番号のビット値である。符号（ｂ）は、その直前の数値が２進数であることを示す。例えば、符号Ｅ＝１０１１（ｂ）の場合、最上位ビットから順に、Ｅ［３］＝１（ｂ）、Ｅ［２］＝０（ｂ）、Ｅ［１］＝１（ｂ）、Ｅ［０］＝１（ｂ）となる。図１と同じ符号についての説明は省略する。
【００２２】
ステップＳ２００において、プロセッサは、例えば、除算命令を用いて、符号Ｅを除数Ｍで除して剰余を算出し、算出した剰余をシンドロームＳとする。すなわち、シンドロームＳは、式（５）から算出される。ここで、誤り検出方法で用いる除数Ｍは、符号化方法で用いる除数Ｍと同じ値である。
Ｓ≡Ｅ  （ｍｏｄ  Ｍ）  ‥‥（５）
【００２３】
ステップＳ２１０において、プロセッサは、シンドロームＳが０の場合、処理を終了し、シンドロームＳが”０”以外の場合、処理をステップＳ２２０に移行する。プロセッサは、シンドロームＳが”０”の場合、符号Ｅに誤りがないと判断し、シンドロームＳが”０”以外の場合、符号Ｅに１ビット誤りがあると判断する。そして、ステップＳ２３０、Ｓ２４０、Ｓ２５０では、符号Ｅにおける１ビット誤りが発生したビット位置が検出され、誤りが訂正される。
【００２４】
まず、ステップＳ２２０において、プロセッサは、関数Ｆ（Ｓ，Ｍ）を用いて、シンドロームＳから誤りが発生したビットの位置を示すビット情報ｂｉｔを求める。すなわち、ビット情報ｂｉｔは、式（６）から算出される。なお、関数Ｆ（Ｓ，Ｍ）は、プロセッサにより演算を実行することで算出されてもよく、プロセッサによりテーブルを参照することで求められてもよい。
ｂｉｔ＝Ｆ（Ｓ，Ｍ）‥‥（６）
【００２５】
ステップＳ２３０において、プロセッサは、ビット情報ｂｉｔの値が（Ｍ−１）／２より小さいか否かを判定する。ビット情報ｂｉｔの値が（Ｍ−１）／２より小さい場合、プロセッサは、論理０から論理１への１ビット誤りが発生したことを検出し、処理をステップＳ２４０に移行する。ビット情報ｂｉｔの値が（Ｍ−１）／２以上の場合、プロセッサは、論理１から論理０への１ビット誤りが発生したことを検出し、処理をステップＳ２５０に移行する。
【００２６】
ステップＳ２４０において、プロセッサは、符号ＥにおけるＥ［ｂｉｔ］の値を論理０に変更することで、ビット情報ｂｉｔの値が示すビット番号の論理１誤りを訂正する。すなわち、プロセッサは、誤りが発生したビットの検出および誤りの訂正を、式（７）に基づいて実行する。そして、処理は終了する。
Ｅ［ｂｉｔ］＝０（ｂ）‥‥（７）
【００２７】
ステップＳ２５０において、プロセッサは、符号ＥにおけるＥ［ｂｉｔ−（Ｍ−１）／２］の値を論理１に変更することで、”ｂｉｔ−（Ｍ−１）／２”の値が示すビット番号の論理０誤りを訂正する。すなわち、プロセッサは、誤りが発生したビットの検出および誤りの訂正を、式（８）に基づいて実行する。そして、処理は終了する。
Ｅ［ｂｉｔ−（Ｍ−１）／２］＝１（ｂ）‥‥（８）
【００２８】
図３は、除数Ｍを”１３”とする場合の”２”を底とする指数値Ｐ、ビット情報ｂｉｔ、剰余値Ｒの関係の例を示している。図３に示すように、指数値Ｐが１２増える毎に、１から１２までの剰余値Ｒが１回ずつ出現する。すなわち、Ｍ＝１３は、２を原始根とする素数であり、図１および図２に示したアルゴリズムに適用可能であることが分かる。但し、後述するように、ＤＬＥＮ＋ＭＬＥＮ≦（Ｍ−１）／２の関係を満たす必要があるので、Ｍ＝３およびＭ＝５は、通常使用されない。
【００２９】
符号Ｅの任意のビットＥ［ＢＩＴ］に、論理０から論理１への１ビットの誤りが生じている場合、誤った符号Ｅ’は、式（９）で表される。一方、符号Ｅの任意のビットＥ［ＢＩＴ］に、論理１から論理０へのビット誤りが生じている場合、誤った符号Ｅ’は、式（１０）で表される。ここで、”ＢＩＴ”は、ビット誤りが生じたビット番号（ビット位置）を示しており、例えば、最下位ビットを示す”ＢＩＴ”は０である。
Ｅ’＝Ｅ＋２ＢＩＴ  ‥‥（９）
Ｅ’＝Ｅ−２ＢＩＴ  ‥‥（１０）
【００３０】
除数Ｍは、２を原始根とする素数であるため、”２ＢＩＴ”は、図３に示したように、除数Ｍで割り切れず、除数Ｍの倍数にはならない。このため、符号Ｅが誤った符号値をＥ’に変化している場合、図３に示すシンドロームＳ（すなわち、剰余値Ｒ）は、±２Ｐ（ｍｏｄ  Ｍ）（すなわち、図３に示した剰余値Ｒ）になる。逆に、１ビット誤りが生じていない場合は、符号Ｅは除数Ｍの倍数であるため、シンドロームＳは”０”になる。したがって、シンドロームＳが”０”でない場合、１ビット誤りがあると判定でき、シンドロームＳが”０”の場合、１ビット誤りがないと判定できる。
【００３１】
図３に示したように、ビット情報ｂｉｔは、剰余値Ｒ（”０”から”Ｍ−１”の範囲）から一意に決定できる。このため、剰余値ＲをシンドロームＳ、誤りが発生したビット番号を示す情報をビット情報ｂｉｔとして、式（１１）の逆関数である式（６）を定義すると、誤りが発生したビット番号に一意に対応するビット情報ｂｉｔをシンドロームＳから算出できる。
Ｓ≡２ｂｉｔ  （ｍｏｄ  Ｍ）  ‥‥（１１）
【００３２】
ここで、指数値Ｐが（Ｍ−１）／２の場合、除数Ｍは、素数であり、２を原始根とすることから、式（１２）が成り立つ。
２（Ｍ−１）／２  （ｍｏｄ  Ｍ）＝Ｍ−１  ‥‥（１２）
【００３３】
図３の逆関数” ｂｉｔ＝Ｆ（Ｓ，Ｍ）”および剰余値Ｒの欄に示した括弧内の値は、”（Ｍ−１）／２”（この例では”６”）より小さいビット情報ｂｉｔと、”（Ｍ−１）／２”以上のビット情報ｂｉｔとが、対応関係を有することを示している。すなわち、”０≦Ｐ＜（Ｍ−１）／２”の範囲の剰余値Ｒに、それぞれＭ−１を乗じた値の剰余値が、（Ｍ−１）／２≦Ｐ＜Ｍ−１の範囲の剰余値Ｒとなる。
【００３４】
例えば、図３において、指数値Ｐ＝６の剰余値Ｒは、指数値Ｐ＝０の剰余値Ｒ＝１に１２（または−１）を乗じた値の剰余値である１２（または−１）になる。図３において、指数値Ｐ＝７の剰余値Ｒは、指数値Ｐ＝１の剰余値Ｒ＝２に１２（または−１）を乗じた値の剰余値である１１（または−２）になる。図３において、指数値Ｐ＝１１の剰余値Ｒは、指数値Ｐ＝５の剰余値Ｒ＝６に１２（または−１）を乗じた値の剰余値である７（または−６）になる。
【００３５】
図３に示した（Ｍ−１）／２≦Ｐ＜Ｍ−１の範囲（６から１１）では、剰余値Ｒに括弧で示した数値（剰余値Ｒの除数Ｍに対する相対値）で示す様に、−２Ｐ  （ｍｏｄ  Ｍ）のデータ誤りが生じていると判断できる。この場合のシンドロームＳは、”Ｓ≡−（２Ｐ−((Ｍ−１）／２)）  （ｍｏｄ  Ｍ）”で示される。
【００３６】
図４は、除数Ｍが”１３”の場合において、シンドロームＳ、ビット情報ｂｉｔ、誤りが発生したビット位置および訂正値との関係の例を示している。シンドロームＳから求められたビット情報ｂｉｔが、０≦ｂｉｔ＜（Ｍ−１）／２の場合、上記式（９）に該当し、符号Ｅのビット位置Ｅ［ＢＩＴ］（０≦ＢＩＴ＜（Ｍ−１）／２）の”ＢＩＴ”は”ｂｉｔ”と同じ値である。この場合、ビット位置Ｅ［ｂｉｔ］に論理０から論理１へのデータ誤りが生じていることが判り、ビット位置Ｅ［ｂｉｔ］の値が論理０に訂正される。
【００３７】
シンドロームＳから求められたビット番号ｂｉｔが、（Ｍ−１）／２≦ｂｉｔ＜Ｍ−１の場合、上記式（１０）に該当し、符号Ｅのビット位置Ｅ［ＢＩＴ］の”ＢＩＴ”は”ｂｉｔ−（Ｍ−１）／２”である。この場合、符号Ｅ［ｂｉｔ−（Ｍ−１）／２］に論理１から論理０へのデータ誤りが生じていることが判り、ビット位置Ｅ［ｂｉｔ−（Ｍ−１）／２］の値が論理１に訂正される。
【００３８】
図４に示したように、誤りを検出するプロセッサは、シンドロームＳから求められるビット情報ｂｉｔに基づいて、誤りが発生したビット番号と、そのビット番号の値が論理０または論理１のいずれに誤っているかが判る。”０”以外の複数個のシンドロームＳの半分が論理０から論理１への誤り検出に使用され、”０”以外の複数個のシンドロームＳの残りの半分が論理１から論理０への誤り検出に使用される。このため、誤り訂正可能な符号Ｅのビット長は、（Ｍ−１）／２である。符号Ｅのビット長は、データＤのビット長ＤＬＥＮと検出符号値Ｃのビット長値ＭＬＥＮとの和である。したがって、データＤのデータ長ＤＬＥＮが”（Ｍ−１）／２−ＭＬＥＮ”以下であれば、符号Ｅの誤りが訂正可能になる。データ長ＤＬＥＮ、ＭＬＥＮの関係を式（１３）に示す。
ＤＬＥＮ＋ＭＬＥＮ≦（Ｍ−１）／２  ‥‥（１３）
【００３９】
例えば、除数Ｍが”１３”の場合、検出符号値Ｃのビット長ＭＬＥＮは”４”であるから、誤りを訂正可能なデータＤのビット長ＤＬＥＮは”２”である。すなわち、符号Ｅのビット長を６ビットにすることで、ビット長ＤＬＥＮが２ビットのデータＤの１ビットの誤り検出訂正が可能である。
【００４０】
除数Ｍのビット長ＭＬＥＮが”８”に設定される場合、例えば、Ｍ＝２２７を用いて、１１３ビットの符号Ｅ（データＤは１０５ビット）の１ビット誤りが検出可能であり、誤りが訂正可能である。除数Ｍのビット長ＭＬＥＮが”１６”に設定される場合、例えば、Ｍ＝６５３７１を用いて、３２６８５ビットの符号Ｅ（データＤは３２６６９ビット）の１ビットの誤り検出と１ビットの誤り訂正とが可能である。このように、この実施形態では、除数Ｍは、データＤのビット長ＤＬＥＮに合わせて選択可能であり、選択した除数Ｍに基づいて符号Ｅを生成できる。
【００４１】
図２に示した誤り検出方法では、排他的演算を用いずに四則演算（すなわち、加減乗除算）を用いて誤り検出と誤り訂正が実行される。したがって、専用のコントローラを用いることなく、ＣＰＵ等のプロセッサを用いてプログラムを実行することで、誤り検出と誤り訂正を実行できる。
【００４２】
以下、実際の数値を用いて、図１に示した符号化方法および図２に示した誤り検出方法の例を説明する。以下の説明において、符号（ｈ）は、その直前の数値が１６進数であることを示す。この例では、プロセッサは、Ｍ＝２２７＝Ｅ３（ｈ）、ビット長値ＭＬＥＮ＝８を使用して、１ビット誤りの検出および訂正を実行する。
【００４３】
補正値Ｋは、式（１）より１９８＝Ｃ６（ｈ）である。データＤのビット長値ＤＬＥＮの最大値は、式（１３）を変形した”（Ｍ−１）／２−ＭＬＥＮ”により求められ、”１０５”である。このため、除数Ｍが”２２７”に設定される場合、２進数で１０５ビットまでのデータＤが符号化可能である。
【００４４】
まず、符号化方法について説明する。例えば、データＤ＝”１２３４ ５６７８ ９ＡＢＣ ＤＥＦ０ １２３４ ５６７８（ｈ）”とする。このデータＤのビット長ＤＬＥＮは”９６”であり、符号化が可能であり、１ビット誤りの検出と訂正が可能である。プロセッサは、図２に示したステップＳ１００において、式（２）に基づいて誤り検出符号Ｃ＝１４（ｈ）を算出する。
【００４５】
プロセッサは、図２に示したステップＳ１１０において、式（３）に基づいて符号Ｅ＝１２ ３４５６ ７８９Ａ ＢＣＤＥ Ｆ０１２ ３４５６ ７８１４（ｈ）を算出する。符号Ｅのビット長は１０４（＝９６＋８）である。
【００４６】
次に、誤り検出方法について説明する。なお、符号Ｅは除数Ｍで割り切れるため、符号Ｅに誤りがない状態では、シンドロームＳは”０”である。例えば、符号Ｅの９９番目のビットＥ［９９］に、論理０から論理１への１ビット誤りが生じた場合、誤りを含む符号Ｅ'は”１Ａ ３４５６ ７８９Ａ ＢＣＤＥ Ｆ０１２ ３４５６ ７８１４（ｈ）”である。符号Ｅ’は、元の符号Ｅに比べて、上位の８ビットが”１２（ｈ）”から”１Ａ（ｈ）”に変わっている。
【００４７】
プロセッサは、図３に示したステップＳ２００において、式（５）に基づいて符号Ｅ’のシンドロームＳを算出する。この例では、シンドロームＳは”１７”であり、”０”でないことから、プロセッサは、図３に示したステップ２５０において、誤りが発生していることを検出する。
【００４８】
プロセッサは、図３に示したステップＳ２２０において、式（１１）に基づいて、離散対数演算を実行し、”１７＝２ｂｉｔ  （ｍｏｄ  ２２７）”を満たすビット情報ｂｉｔ＝９９を算出する。なお、プロセッサは、離散対数演算をする代わりに、図４と同様なテーブルを参照して、ビット情報ｂｉｔを求めてもよい。
【００４９】
次に、プロセッサは、図３に示したステップＳ２３０において、ビット情報ｂｉｔが１１３未満（（Ｍ−１）／２未満）であると判定する。そして、プロセッサは、図３に示したステップＳ２４０において、ビット情報ｂｉｔ（＝９９）から１ビット誤りが発生しているビット番号（＝９９）を求め、求めたビット番号の値を論理０から論理１に誤り訂正する。
【００５０】
一方、例えば、符号Ｅの４番目のビットＥ［４］に、論理１から論理０への１ビット誤りが生じた場合、誤りを含む符号Ｅ'は”１２ ３４５６ ７８９ａ ｂｃｄｅ ｆ０１２ ３４５６ ７８０４（ｈ）”である。符号Ｅ’は、元の符号Ｅに比べて、上位の８ビットが”１４（ｈ）”から”０４（ｈ）”に変わっている。
【００５１】
プロセッサは、上述と同様に、符号Ｅ’のシンドロームＳ（＝２１１）を算出し、誤りが発生していることを検出する。次に、プロセッサは、”２１１＝２ｂｉｔ  （ｍｏｄ  ２２７）”を満たすビット情報ｂｉｔ＝１１７を算出する。ビット情報ｂｉｔは、式（１１）に基づいて離散対数演算により算出してもよく、図４と同様なテーブルを参照して求めてもよい。
【００５２】
次に、プロセッサは、図３に示したステップＳ２３０において、ビット情報ｂｉｔが１１３以上（（Ｍ−１）／２以上）であると判定する。そして、プロセッサは、図３に示したステップＳ２５０において、ビット情報ｂｉｔ（＝１１７）から１１３を減じて、１ビット誤りが発生しているビット番号（＝４）を求め、求めたビット番号の値を論理１から論理０に誤り訂正する。
【００５３】
以上、この実施形態では、Ｍを法とする”べき乗剰余環”において２を原始根とする素数を除数値として用いて、符号Ｅが生成され、生成された符号Ｅの誤り検出および誤り訂正が実行される。これにより、２を法とする排他的演算を用いずに、２を法としない四則演算（すなわち、加減乗除算）を用いて符号Ｅを生成でき、誤り検出および誤り訂正を実行できる。換言すれば、専用のコントローラを用いることなく、ＣＰＵ等のプロセッサを用いてプログラムを実行することで、符号Ｅを生成でき、誤り検出および誤り訂正を実行できる。
【００５４】
図５は、別の実施形態における符号化方法の例を示している。図１から図４に示した実施形態で説明した要素と同様または同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。例えば、図５に示す符号化方法は、図１４および図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図５に示す各処理は、ＣＰＵ等のプロセッサにより実行される。
【００５５】
この実施形態では、符号Ｅは、誤り検出符号ＣをデータＤの上位ビット側に付加することで生成される。この場合、誤り検出符号Ｃは、上述した式（２）の代わりに式（１４）により求められる補正値Ｋ’を用いて算出される。
Ｋ’≡−（２−ＤＬＥＮ）  （ｍｏｄ  Ｍ）  ‥‥（１４）
【００５６】
まず、ステップＳ１００Ａにおいて、プロセッサは、データＤと補正値Ｋ’の積を除数Ｍで除して剰余を算出し、算出した剰余を誤り検出符号Ｃとする。例えば、データＤと補正値Ｋ’の積は、乗算命令を用いて実行され、剰余の算出は、除算命令を用いて実行される。ビット長を短くするために、検出符号値Ｃは、除数Ｍ以下で正の値の剰余を選択することが好ましい。例えば、データＤは、プロセッサの外部から供給される。
【００５７】
なお、ステップＳ１００Ａは、図１に示したステップＳ１００と同様に、”ｔｅｍｐ≡Ｄ  （ｍｏｄ  Ｍ）”と、”Ｃ≡ｔｅｍｐ×Ｋ’  （ｍｏｄ  Ｍ）”の２つのステップに分けられてもよい。この場合、剰余演算に使用する数値のビット数を少なくでき、計算の負荷を軽減できる。
【００５８】
ステップＳ１１０Ａにおいて、プロセッサは、例えば、乗算命令あるいはシフト命令を用いて、誤り検出符号ＣをデータＤのビット長値ＤＬＥＮだけ上位ビット側にシフトし、シフトした誤り検出符号ＣにデータＤを付加する。すなわち、データＤの上位ビット側に誤り検出符号Ｃが付加され、符号Ｅが生成される。式（１４）で示した補正値Ｋ’を用いて、符号Ｅを算出する場合、式（１５）、（１６）、（１７）が成立するため、符号Ｅは、除数Ｍで割り切れる。
Ｃ≡Ｄ・Ｋ’≡−（Ｄ・（１／２）ＭＬＥＮ））  （ｍｏｄ  Ｍ）  ‥‥（１５）
Ｅ≡（Ｃ＜＜ＤＬＥＮ）＋Ｄ≡（Ｃ・２ＤＬＥＮ）＋Ｄ  (ｍｏｄ  Ｍ）  ‥‥（１６）
Ｅ≡０（ｍｏｄ  Ｍ）  ‥‥（１７）
【００５９】
式（１４）において、”２−ＤＬＥＮ”は、除数Ｍを法とする”２ＤＬＥＮ”の乗算逆元を示している。ここで、除数Ｍは、２を原始根とする素数（奇数）であるため、２の乗算逆元は存在する。
【００６０】
２の乗算逆元が存在するため、データＤと誤り検出符号Ｃの配置を交換可能であり、誤り検出符号ＣをデータＤの上位ビット側に配置可能である。すなわち、式（１４）に示す補正値Ｋ’を用いて算出された誤り検出符号Ｃを用いることで、誤り検出符号ＣがデータＤの上位ビット側に付加される場合にも、除数Ｍで割り切れる符号Ｅを生成できる。したがって、符号Ｅの１ビット誤りを検出でき、検出した１ビット誤りを訂正できる。
【００６１】
図６は、符号Ｅ内での誤り検出符号Ｃの配置の例を示している。図６において符号Ｗは、ＣＰＵ等のプロセッサにより一度にアクセスされるデータのビット幅（データバス幅）を示している。データバスは、プロセッサが実行するプログラムのフェッチや、データＤ、誤り検出符号Ｃ等の情報の入出力に使用される。そして、プロセッサがプログラムを実行することにより、誤り検出符号Ｃおよび符号Ｅが生成され、符号Ｅの誤り検出および誤り訂正が行われる。データＤは、ビット幅Ｗに合わせてｎ＋１個（Ｄ（０）、Ｄ（１）、Ｄ（２）、...、Ｄ（ｎ−１）、Ｄ（ｎ））に区画される。
【００６２】
図６（Ａ）では、式（１４）に示す補正値Ｋ’を用いて算出された誤り検出符号Ｃは、データＤのビット長ＤＬＥＮだけ上位ビット側にシフトされ（左シフト）、データＤの上位ビット側に付加される。例えば、誤り検出符号Ｃのビット長ＭＬＥＮは、データのビット幅Ｗより小さい。
【００６３】
この場合、データＤの配列を変えることなく、符号Ｅを生成できる。また、符号Ｅは、誤り検出符号ＣをデータＤのビット長ＤＬＥＮだけ左シフトすることにより生成される。上述したように、誤り検出符号Ｃのビット長ＭＬＥＮが８ビットや１６ビットの場合、ビット長ＭＬＥＮは、データＤのビット長ＤＬＥＮに比べて小さい。このため、図６（Ａ）では、データＤをシフトして誤り検出符号ＣをデータＤの下位ビット側に付加する場合に比べて演算回数を少なくできる。
【００６４】
図６（Ｂ）は、誤り検出符号Ｃのビット長ＭＬＥＮがデータのビット幅Ｗと等しい場合に、データＤがビット長ＭＬＥＮだけ上位ビット側にシフトされ、データＤの下位ビット側に誤り検出符号Ｃが付加される例を示している。例えば、図６（Ｂ）の符号Ｅは、図１から図４に示した実施形態で使用される。
【００６５】
図６（Ｃ）は、誤り検出符号Ｃのビット長ＭＬＥＮがデータのビット幅Ｗより小さい場合に、データＤがビット長ＭＬＥＮだけ上位ビット側にシフトされ、データＤの下位ビット側に誤り検出符号Ｃが付加される例を示している。下位ビット側に配置されるビット長ＭＬＥＮがビット幅Ｗより小さいため、データＤは、ビット幅Ｗの境界を跨いで配置される。
【００６６】
例えば、データＤの本来の配列構成からデータＥを作成する際に、図６（Ｃ）の配列構成を作成するためには、データＤの移動を行う必要があり、演算の実行効率は低下する。換言すれば、誤り検出符号Ｃのビット長ＭＬＥＮがデータのビット幅Ｗより小さい場合、図６（Ａ）に示したように、補正値Ｋ’を用いて、データＤの上位ビット側に誤り検出符号Ｃを付加することが好ましい。
【００６７】
補正値Ｋ’は、データＤの上位ビット側に誤り検出符号Ｃを付加して符号Ｅを生成する場合に、除数Ｍで割り切れる符号Ｅを生成するためのものである。符号Ｅを除数Ｍで除した剰余であるシンドロームＳは、符号Ｅに１ビット誤りがない場合に”０”であり、符号Ｅに１ビット誤りがある場合に”０”以外である。また、符号Ｅに１ビット誤りがある場合、誤りが発生したビット番号と誤った論理とは、シンドロームＳに基づいて一意に決定可能である。したがって、補正値Ｋ’を用いて生成された符号Ｅは、図２に示したフローを実行することにより、１ビット誤りを検出、訂正できる。
【００６８】
図６（Ａ）から図６（Ｃ）に示した誤り検出符号Ｃは、式（１８）により求められる補正値Ｋを用いることでも算出可能であり、算出された誤り検出符号Ｃが付加された符号Ｅは、除数Ｍで割り切れる。式（１８）のＤｓｈｉｆｔは、データＤを符号Ｅ内に配置するためのシフト量を示し、Ｃｓｈｉｆｔは、誤り検出符号Ｃを符号Ｅ内に配置するためのシフト量を示している。
Ｋ≡−２Ｄｓｈｉｆｔ−Ｃｓｈｉｆｔ  （ｍｏｄ  Ｍ）  ‥‥（１８）
【００６９】
シフト量Ｄｓｈｉｆｔが正の場合、データＤは、上位ビット側にシフト（左シフト）される。シフト量Ｄｓｈｉｆｔが負の場合、データＤは、下位ビット側にシフト（右シフト）される。シフト量Ｃｓｈｉｆｔが正の場合、誤り検出符号Ｃは、上位ビット側にシフト（左シフト）される。シフト量Ｃｓｈｉｆｔが負の場合、誤り検出符号Ｃは、下位ビット側にシフト（右シフト）される。式（１８）で求められる補正値Ｋを使用し、データＤと誤り検出符号Ｃとが互いに重複しないように配置することで、データＤおよび誤り検出符号Ｃを符号Ｅ内の任意の位置に配置できる。
【００７０】
以上、この実施形態においても、図１に示した実施形態と同様に、排他的演算を用いずに四則演算を用いて符号Ｅを生成できる。さらに、誤り検出符号ＣをデータＤに対して任意の位置に配置できる。例えば、図６（Ｃ）に示す配置を避け、図６（Ａ）に示す配置にすることで、演算効率を向上できる。
【００７１】
図７は、別の実施形態における符号化方法の例を示している。図１から図４に示した実施形態で説明した要素と同様または同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。例えば、図７に示す符号化方法は、図１４および図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図７に示す各処理は、ＣＰＵ等のプロセッサにより実行される。この実施形態では、図１に示したステップＳ１１０の代わりにステップＳ１１０Ｂが実行され、ステップＳ１００とＳ１１０Ｂとの間に、ステップＳ１０５Ｂが挿入される。
【００７２】
例えば、図１から図４に示した実施形態では、データＤがオール０の場合、誤り検出符号値Ｃはオール０になり、符号Ｅはオール０になる。初期状態で論理０を記憶するメモリセルを有する半導体メモリに、符号Ｅが格納される場合、半導体メモリから読み出されるオール０は、誤りのない有効な符号Ｅであるのか初期状態の論理であるのかの判別が困難である。あるいは、通信システムにおいて、通信データ長が規定されていない場合、受信回路が、下位ビット側に論理０が付加された誤った符号値を受信するかもしれない。受信回路は、オール０の符号値を受信すると、誤りを検出できない。あるいは、下位ビット側に論理０が付加された誤った符号値は、元の符号Ｅの倍数であるため、誤りを検出できない場合がある。
【００７３】
この実施形態では、データＤがオール０の場合に誤り検出符号Ｃが”０”以外になるようにし、かつ、誤りがないときの符号Ｅが除数Ｍで割り切れないようにすることで、上記問題が解決可能になる。なお、この実施形態は、データＤのビット長ＤＬＥＮが決まっている場合に適用可能である。
【００７４】
まず、ステップＳ１００において、図１と同様に、除算命令を用いて誤り検出符号Ｃが算出される。次に、ステップＳ１０５Ｂにおいて、プロセッサは、誤り検出符号Ｃと符号Ｅの後（下位ビット側）に付けられる付加値Ｊとを用いて、誤り検出符号Ｃを付加値Ｊで補正し、誤り検出符号Ｃ’を算出する。例えば、誤り検出符号Ｃ’は、除算命令を用いて式（１９）により算出される。付加値Ｊは、”０”を除き、かつ除数Ｍの倍数を除く定数値である。このため、誤り検出符号Ｃ’は、誤り検出符号Ｃに定数を加算し、剰余を求めることで算出すればよいことがわかる。符号ＪＬＥＮは、付加値Ｊのビット長である。式（１４）と同様に、”２−ＪＬＥＮ”は、除数Ｍを法とする”２ＪＬＥＮ”の乗算逆元を示している。
Ｃ’≡Ｃ−Ｊ×２−ＪＬＥＮ  （ｍｏｄ  Ｍ）  ‥‥（１９）
【００７５】
プロセッサは、式（１９）で求めた誤り検出符号Ｃ’のうち、除数Ｍ以下の正の値を、実際の誤り検出符号Ｃ’として選択する。誤り検出符号Ｃ’を用いることで、符号Ｅに付加値Ｊを加えて生成される符号ＡＬＬは、除数Ｍで割り切れる。一方、符号ＡＬＬが除数Ｍで割り切れるように算出されるため、符号Ｅに誤りがない場合、誤り検出符号Ｃ’は”０”以外の値になる。
【００７６】
次に、ステップＳ１１０Ｂにおいて、図１のステップＳ１１０と同様に、プロセッサは、乗算命令あるいはシフト命令を用いて、データＤをビット長値ＭＬＥＮだけ上位ビット側にシフトし、シフトしたデータ値に誤り検出符号Ｃ’を付加する。すなわち、データＤの下位ビット側に誤り検出符号Ｃ’が付加され、符号Ｅが生成される。
【００７７】
生成された符号Ｅ（誤りがない符号Ｅ）は、除数Ｍで割り切れない。一方、誤り検出符号Ｃ’は、付加値Ｊを考慮して算出されているため、符号Ｅの後（下位ビット側）に付けられる付加値Ｊを含む符号ＡＬＬ（図８）は、除数Ｍで割り切れる。
【００７８】
図８は、図７で生成される符号Ｅに付加値Ｊを付加した符号ＡＬＬの例を示している。符号ＡＬＬは、符号Ｅの後（下位ビット側）に付加値Ｊを付けることで生成される。付加値Ｊのビット長をＪＬＥＮとすると、符号ＡＬＬは、式（２０）により表される。
ＡＬＬ＝（Ｄ＜＜（ＭＬＥＮ＋ＪＬＥＮ））＋（Ｃ’＜＜ＪＬＥＮ）＋Ｊ  ‥‥（２０）
【００７９】
付加値Ｊは、データＤや誤り検出符号Ｃ’に依存しない固定の値である。このため、付加値Ｊは、符号Ｅを生成するときに誤り検出符号Ｃ’を求めるために使用されればよく、符号Ｅの誤りを検出するときに、符号ＡＬＬを生成するために使用されればよい。したがって、付加値Ｊは、符号Ｅを生成する符号化部と、符号Ｅの誤りを検出する誤り検出部とが予め認識していればよい。
【００８０】
すなわち、符号化部は、付加値Ｊを含まない符号Ｅを出力すればよく、誤り検出部は、付加値Ｊを含まない符号Ｅを受ければよい。例えば、メモリシステムでは、符号化部は、符号ＡＬＬではなく符号Ｅを半導体メモリに格納し、誤り検出部は、半導体メモリから読み出した符号Ｅに付加値Ｊを付加した符号ＡＬＬを生成し、符号ＡＬＬを用いて誤りを検出する。通信システムでは、符号ＡＬＬではなく符号Ｅが、送信回路の符号化部から受信回路に出力され、受信回路の誤り検出部は、受信した符号Ｅに付加値Ｊを付加して符号ＡＬＬを生成し、符号ＡＬＬを用いて誤りを検出する。
【００８１】
誤り検出部は、符号ＡＬＬを除数Ｍで除した剰余が０のときにデータＤに誤りがないと判定し、符号ＡＬＬを除数Ｍで除した剰余が”０”以外のときにデータＤに誤りがあると判定する。付加値Ｊを符号Ｅに付加することで、誤り検出符号Ｃ’は、データＤが０の場合にも”０”以外の値になる。また、符号ＡＬＬは除数Ｍの倍数であるが、符号Ｅは除数Ｍの倍数でない。
【００８２】
これにより、例えば、メモリシステムでは、半導体メモリのメモリセルが初期状態で論理０の場合にも、半導体メモリから読み出されるオール０が、誤りのない有効な符号Ｅであるのか初期状態の論理であるのかを判別可能になる。また、通信システムでは、受信回路が、下位ビット側に論理０が付加された誤った符号Ｅを受信する場合、符号Ｅの誤りが検出可能になる。
【００８３】
図９は、別の実施形態における符号化方法の例を示している。図１から図５、図７、図８に示した実施形態で説明した要素と同様または同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。例えば、図９に示す符号化方法は、図１４および図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図９に示す各処理は、ＣＰＵ等のプロセッサにより実行される。この実施形態では、図１に示したステップＳ１１０の代わりに図７に示したステップＳ１１０Ｂが実行され、ステップＳ１００とＳ１１０Ｂとの間に、ステップＳ１０５Ｃが挿入される。
【００８４】
まず、ステップＳ１００において、図１と同様に、誤り検出符号Ｃが算出される。次に、ステップＳ１０５Ｃにおいて、プロセッサは、例えば、加算命令を用いて、誤り検出符号Ｃに定数Ｃ１を付加して誤り検出符号Ｃ’を算出する。定数Ｃ１は、”０”を除き、かつ、除数Ｍの倍数を除く定数値である。そして、ステップＳ１１０Ｂにおいて、データＤがビット長値ＭＬＥＮだけ上位ビット側にシフトされ、シフトされたデータ値に誤り検出符号Ｃ’が付加されて、符号Ｅが生成される。
【００８５】
図１０は、図９で生成される符号Ｅの例を示している。この実施形態では、上記の式（２）により求められる誤り検出符号Ｃに定数Ｃ１を付加した値が、データＤに付加され、符号Ｅが生成される。誤り検出符号Ｃに定数Ｃ１を付加した値のビット長が、除数Ｍのビット長ＭＬＥＮ以下になるように、定数Ｃ１は、１からＭ−１のいずれかの値であることが好ましい。
【００８６】
定数Ｃ１が付加された符号Ｅに誤りがない場合、符号Ｅを除数Ｍで除した剰余（すなわち、シンドロームＳ）は定数Ｃ１になる。一方、定数Ｃ１が付加された符号Ｅに誤りがある場合、符号Ｅを除数Ｍで除した剰余は、定数Ｃ１以外の値になる。これにより、符号Ｅに誤りがあるか否かを判断できる。
【００８７】
これにより、図７に示した実施形態と同様に、メモリシステムでは、半導体メモリのメモリセルが初期状態で論理０の場合にも、半導体メモリから読み出されるオール０が、誤りのない有効な符号Ｅであるのか初期状態の論理であるのかを判別可能になる。また、通信システムでは、受信回路が、下位ビット側に論理０が付加された誤った符号Ｅを受信する場合、符号Ｅの誤りが検出可能になる。
【００８８】
図１１は、別の実施形態における符号化方法および誤り検出方法で扱われるデータの構造の例を示している。図１から図５、図７から図１０に示した実施形態で説明した要素と同様または同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。例えば、図１１に示す符号化方法は、図１４または図１５に示すＣＰＵ等のプロセッサがプログラムを実行することにより実現される。すなわち、図１１に示す各処理は、ＣＰＵ等のプロセッサにより実行される。この実施形態では、図７に示したステップＳ１００の代わりにステップＳ１００Ｄが実行される。ステップＳ１０５Ｂ、Ｓ１１０Ｂは、図７のステップＳ１０５Ｂ、Ｓ１１０Ｂと同様である。
【００８９】
この実施形態は、データＤのビット長ＤＬＥＮが可変の場合に適用され、図１２に示すように、符号Ｅの前（上位ビット側）に付けられる付加値Ｉと、符号Ｅの後（下位ビット側）に付けられる付加値Ｊとを含む符号ＡＬＬが定義される。付加値Ｉのビット長をＩＬＥＮ、付加値Ｊのビット長をＪＬＥＮとすると、符号ＡＬＬは、式（２１）により表される。
ＡＬＬ＝Ｉ＜＜（ＤＬＥＮ＋ＭＥＬＮ＋ＪＬＥＮ）＋Ｄ＜＜（ＭＬＥＮ＋ＪＬＥＮ）＋Ｃ＜＜ＪＬＥＮ＋Ｊ  ‥‥（２１）
【００９０】
ここで、付加値Ｉ、Ｊの各々は、”０”を除き、かつ、除数Ｍの倍数を除く定数である。まず、付加値ＩがデータＤの上位ビット側に付加された値（（Ｉ＜＜ＤＬＥＮ）＋Ｄ）と式（１）に示した補正値Ｋを用いて、式（２２）から誤り検出符号Ｃが求められる。
Ｃ≡（（Ｉ＜＜ＤＬＥＮ）＋Ｄ）×Ｋ  （ｍｏｄ  Ｍ）  ‥‥（２２）
【００９１】
なお、演算するビット数を減らすために、付加値Ｉを除数Ｍで除した剰余を求め（Ｉ  （ｍｏｄ  Ｍ））、求めた剰余にデータＤの一部と乗じて、剰余を順次に求めてもよい。付加値Ｉは定数であるため、付加値Ｉを除数Ｍで除した剰余も定数である。そして、最終的に求められた剰余に補正値Ｋを乗じた値を除数Ｍで除した剰余が誤り検出符号Ｃになる。
【００９２】
次に、上記の式（１９）に基づいて、検出符号値Ｃと付加値Ｊとを用いて検出符号値Ｃ’が求められ、符号Ｅが生成される。図８で説明したように、メモリシステムおよび通信システムにおいて、符号化部は、付加値Ｊを含まない符号Ｅを出力すればよく、誤り検出部は、付加値Ｊを含まない符号Ｅを受ければよい。そして、誤り検出部は、符号ＡＬＬを除数Ｍで除した剰余が０のときにデータＤに誤りがないと判定し、符号ＡＬＬを除数Ｍで除した剰余が”０”以外のときにデータＤに誤りがあると判定する。なお、図９と同様に、付加値Ｊを付加せずに、誤り検出符号Ｃ’に定数Ｃ１を付加した値が、データＤに付加され、符号Ｅが生成されてもよい。
【００９３】
図１２は、図１１で生成される符号Ｅの例および符号Ｅに付加される付加値Ｉ、Ｊの例を示している。符号ＡＬＬは、式（２１）に示したように、符号Ｅの前（上位ビット側）に付加値Ｉを付け、符号Ｅの後（下位ビット側）に付加値Ｊを付けることで生成される。
【００９４】
通信システムにおいて、送信装置側と受信装置側で、通信データ長が予め規定されていない場合、送信されるデータＤに先立って０データが余分に受信される場合がある。しかし、この実施形態では、符号ＡＬＬは、データＤの前に付加される付加値Ｉ（０でない）を含むため、受信装置は、データ値の前に０データが付加されているか否かを判断できる。すなわち、受信装置は、誤ったデータの受信を検出できる。
【００９５】
以下、実際の数値を用いて、図１１に示した符号化方法および図１１の処理により生成された符号Ｅの誤り検出方法の例を説明する。この例では、プロセッサは、Ｍ＝２２７＝Ｅ３（ｈ）、ビット長値ＭＬＥＮ＝８を使用して、１ビット誤りの検出を実行する。補正値Ｋは、式（１）より１９８＝Ｃ６（ｈ）である。付加値ＩはＦＦ（ｈ）、付加値Ｉのビット長ＩＬＥＮは”８”、付加値Ｊは２９（ｈ）、付加値Ｊのビット長ＪＬＥＮは”８”に設定されている。
【００９６】
データＤのビット長値ＤＬＥＮの最大値は、式（１３）を変形した”（Ｍ・１）／２−ＭＬＥＮ”により求められ、”１０５”である。この例では、可変長のデータＤの１つとして、”１２３４ ５６７８ ９ＡＢＣ ＤＥＦ０ １２３４ ５６７８（ｈ）”が符号化される。データＤのビット長ＤＬＥＮは”９６”である。
【００９７】
プロセッサは、図１１に示したステップＳ１００Ｄにおいて、例えば、乗算命令、加算命令、除算命令を用いて、式（２２）に基づいて、誤り検出符号Ｃを算出する。例えば、プロセッサは、最初に”（Ｉ＜＜ＤＬＥＮ）＋Ｄ  （ｍｏｄ  Ｍ）”を算出する。”Ｉ＜＜ＤＬＥＮ）＋Ｄ”は、”ＦＦ １２３４ ５６７８ ９ＡＢＣ ＤＥＦ０ １２３４ ５６７８（ｈ）”であるため、”８Ｄ（ｈ）”が得られる。プロセッサは、得られた値”８Ｄ（ｈ）”に補正値Ｋ＝”Ｃ６（ｈ）”を乗じた値を除数Ｍで除した剰余を求め、求めた値”Ｅ０（ｈ）”を誤り検出符号Ｃとする。
【００９８】
次に、プロセッサは、図１１に示したステップＳ１０５Ｂにおいて、式（１９）に基づいて、誤り検出符号Ｃ’を算出する。”−（Ｊ×２−ＪＬＥＮ）”が”Ｅ２（ｈ）”であるため、プロセッサは、誤り検出符号Ｃ’＝”ＤＦ（ｈ）”を得る。
【００９９】
次に、プロセッサは、図１１に示したステップＳ１１０Ｂにおいて、データＤをビット長値ＭＬＥＮだけ上位ビット側にシフトし、シフトしたデータ値に誤り検出符号Ｃ’を付加し、符号Ｅ＝”１２ ３４５６ ７８９Ａ ＢＣＤＥ Ｆ０１２ ３４５６ ７８ＤＦ（ｈ）”を得る。そして、得られた符号Ｅは、半導体メモリに書き込まれ、あるいは、受信装置に向けて送信される。
【０１００】
符号Ｅの誤りを検出する場合、プロセッサは、符号Ｅに付加値Ｉ、Ｊを加えて符号ＡＬＬを生成する。符号Ｅに誤りがない場合、符号ＡＬＬは”ＦＦ １２３４ ５６７８ ９ＡＢＣ ＤＥＦ０ １２３４ ５６７８ ＤＦ１Ｄ（ｈ）”になる。プロセッサは、”ＡＬＬ  （ｍｏｄ  Ｍ）”を算出して”０”を得ることで、符号Ｅに誤りがないことを検出する。
【０１０１】
プロセッサが、符号Ｅの上位ビット側に”０”が１ビット付加された誤った符号Ｅ’を受信する場合、符号Ｅ’は、”０１２ ３４５６ ７８９Ａ ＢＣＤＥ Ｆ０１２ ３４５６ ７８ＤＦ（ｈ）”になる。プロセッサは、符号Ｅ’に付加値Ｉ、Ｊを付加した符号ＡＬＬ＝”１ＦＥ １２３４ ５６７８ ９ＡＢＣ ＤＥＦ０ １２３４ ５６７８ ＤＦ１Ｄ”を用いて、”ＡＬＬ  （ｍｏｄ  Ｍ）”＝”Ｄ５（ｈ）”を算出する。プロセッサは、算出した剰余が０でないことに基づいて、受信した符号Ｅ’に誤りがあることを検出する。
【０１０２】
一方、プロセッサが、符号Ｅの下位ビット側に”０”が１ビット付加された誤った符号Ｅ’を受信する場合、符号Ｅ’は、”０２４ ６８ＡＣ Ｆ１３５ ７９ＢＤ Ｅ０２４ ６８ＡＣ Ｆ１ＢＥ（ｈ）”になる。プロセッサは、符号Ｅ’に付加値Ｉ、Ｊを付加した符号ＡＬＬ＝”１ＦＥ ２４６８ ＡＣＦ１ ３５７９ ＢＤＥ０ ２４６８ ＡＣＦ１ ＢＥ１Ｄ”を用いて、”ＡＬＬ  （ｍｏｄ  Ｍ）”＝”Ｃ６（ｈ）”を算出する。プロセッサは、算出した剰余が０でないことに基づいて、受信した符号Ｅ’に誤りがあることを検出する。
【０１０３】
これに対して、図１に示したアルゴリズムにより符号化された符号Ｅの誤りが、図２に示したアルゴリズムにより検出される場合、プロセッサは、符号Ｅの下位ビット側に”０”が１ビット付加された誤った符号Ｅ’の誤りを検出しない。例えば、符号Ｅが”１２ ３４５６ ７８９Ａ ＢＣＤＥ Ｆ０１２ ３４５６ ７８ＤＦ（ｈ）”の場合、下位ビット側に”０”が１ビット付加された誤った符号Ｅ’は”０２４ ６８ＡＣ Ｆ１３５ ７９ＢＤ Ｅ０２４ ６８ＡＣ Ｆ０２８（ｈ）”になる。式（５）を用いて求められる符号Ｅ’のシンドロームＳは、”０”になり、符号Ｅ’の誤りを検出できない。同様に、図１に示したアルゴリズムにより符号化された符号Ｅの誤りが、図２に示したアルゴリズムにより検出される場合、プロセッサは、符号Ｅの上位ビット側に”０”が１ビット付加された誤った符号Ｅ’の誤りを検出できない。
【０１０４】
図１３は、別の実施形態における誤り検出方法の例を示している。図１から図１２に示した実施形態で説明した要素と同様または同一の要素については、同一の符号を付し、これ等については、詳細な説明を省略する。
【０１０５】
図５に示したように、ビット誤りの位置を判定する逆関数ｂｉｔ＝Ｆ（Ｓ，Ｍ）は、離散対数値を演算する関数である。このため、この実施形態では、プロセッサが、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムにより離散対数演算を実行することで、演算負荷を軽減する。除数Ｍを選択し、式（２３）を満たすように定数Ｍ０、Ｍ１、...、Ｍｎ（互いに異なる素数）、Ｐ０、Ｐ１、...、Ｐｎ（整数）を決定する。各変数の添字ｎ(整数)は、Ｍ−１を素因数分解した際の素因数の数＋１を示しており、各素因数に対し同様の演算を定義する。なお、説明を判りやすくするために、以降は、Ｐ０、Ｐ１、...、Ｐｎは、全て”１”とする。各Ｍ０、Ｍ１、...、Ｍｎから、式（２４）により、定数Ｎ０、Ｎ１、...、Ｎｎを定義する。Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムの原理に基づき、Ｓ≡２ＢＩＴ（ｍｏｄ  Ｍ）を満たすＢＩＴに対して、式（２５）により、Ｂ０、Ｂ１、...、Ｂｎが定義される。
Ｍ−１＝Ｍ０Ｐ０×Ｍ１Ｐ１×...×ＭｎＰｎ  ‥‥（２３）
Ｎｎ＝（Ｍ−１）／Ｍｎ  ‥‥（２４）
Ｂｎ≡ＢＩＴ  （ｍｏｄ  Ｍｎ）  ‥‥（２５）
【０１０６】
まず、ステップＳ３００において、プロセッサは、除算命令を用いて、符号Ｅを除数Ｍで除して剰余を算出し、算出した剰余をシンドロームＳとする。ステップＳ３１０において、プロセッサは、シンドロームＳが０の場合、符号Ｅに誤りがないと判断し、処理を終了する。プロセッサは、シンドロームＳが”０”以外の場合、符号Ｅに１ビット誤りがあると判断し、処理をステップＳ３２０に移行する。
【０１０７】
次に、ステップＳ３２０において、プロセッサは、カウンタ値ｎを”０”に初期化する。ステップＳ３３０において、プロセッサは、乗算命令および除算命令により、シンドロームＳを用いて、最初の定数Ｎ０について式（２６）からシンドロームＳ０を算出する。
Ｓｎ≡ＳＮｎ  （ｍｏｄ  Ｍ）  （ｎは０以上の整数）  ‥‥（２６）
【０１０８】
ステップＳ３４０において、プロセッサは、カウンタ値ｎが最大値ｍａｘ（以下に示す実際の例では、”３”）のときに処理をステップＳ３５０に移行し、カウンタ値ｎが最大値ｍａｘより小さいときに、処理をステップＳ３４５に移行する。ステップＳ３４５では、カウンタ値ｎが１だけ増加される。
【０１０９】
そして、プロセッサは、ステップＳ３３０を”ｎ＋１”回実行し、定数Ｍ１、...、Ｍｎについて、式（２６）からシンドロームＳ１、...、Ｓｎを算出する。なお、プロセッサは、カウンタ値ｎを用いることなく、ｎ＋１個のシンドロームＳ０−Ｓｎを順に算出してもよい。
【０１１０】
次に、ステップＳ３５０において、プロセッサは、カウンタ値ｎを”０”に初期化する。ステップＳ３６０において、プロセッサは、次に、式（２６）で求められたシンドロームＳ０、Ｓ１、...、Ｓｎを用いて、式（２７）の条件を満たす値Ｂｎ（Ｂ０、Ｂ１、...、Ｂｎ）を求める。ここで、式（２６）で求められるシンドロームＳ０、Ｓ１、...、Ｓｎの各々は、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムの原理に基づき、Ｍｎ個の種類に限定される。このため、プロセッサは、式（２７）の条件を満たす値Ｂｎを、少ないクロックサイクル数で求めることができる。式（２７）において符号**は、べき乗演算を示している。
Ｓｎ≡（２Ｎｎ）**Ｂｎ  （ｍｏｄ  Ｍｎ）  ‥‥（２７）
【０１１１】
ステップＳ３７０において、プロセッサは、カウンタ値ｎが最大値ｍａｘ（以下に示す実際の例では、”３”のとき）に処理をステップＳ３８０に移行し、カウンタ値ｎが最大値ｍａｘより小さいときに、処理をステップＳ３７５に移行する。ステップＳ３７５では、カウンタ値ｎが１だけ増加される。
【０１１２】
そして、プロセッサは、ステップＳ３６０を”ｎ＋１”回実行し、式（２７）の条件を満たす”ｎ＋１”個の値Ｂｎを求める。なお、プロセッサは、カウンタ値ｎを用いることなく、ｎ＋１個の値Ｂｎを順に求めてもよい。
【０１１３】
次に、ステップＳ３８０において、プロセッサは、ｎ＋１個の値Ｂｎを用いて、中国剰余定理により、符号Ｅ内で誤りが発生したビット位置を求める。ステップＳ３６０で求められた値Ｂ０、Ｂ１、...、Ｂｎは、式（２５）の関係を満たしているため、中国剰余定理を利用することができる。
【０１１４】
この実施形態では、２を原始根とする素数である除数Ｍのうち、積が”Ｍ−１”となる値Ｍ０Ｐ０、Ｍ１Ｐ１、...、ＭｎＰｎを選択することで、符号Ｅ内で誤りが発生したビット位置を求めるアルゴリズムを効率的に適用できる。この結果、演算に必要なメモリ容量を小さくでき、演算に必要な処理時間を短縮できる。なお、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムの原理に基づき、定数Ｍ０、Ｍ１、...、Ｍｎは、小さい方が演算の負荷を軽くできる。これにより、符号Ｅのビット長を大きくし、除数Ｍが大きくなる場合にも、データＤの誤りを検出する処理の演算負荷が小さくできる。例えば、除数Ｍとして、”２１１＝２×３×５×７＋１”、あるいは”１６３＝２×３４＋１”が選択できる。
【０１１５】
以下、実際の数値を用いて、図１３に示した誤り検出方法の例を説明する。なお、符号Ｅは、例えば、プロセッサにより図１に示した符号化方法を実行することで生成される。この例では、Ｍ＝２１１、カウンタ値ｎ＝３、Ｍ０＝２、Ｍ１＝３、Ｍ２＝５、Ｍ３＝７、Ｐ０＝１、Ｐ１＝１、Ｐ２＝１、Ｐ３＝１が予め設定されている。
【０１１６】
例えば、ステップＳ３００において、シンドロームＳ＝１６２が得られたとする。プロセッサは、ステップＳ３３０により以下に示すシンドロームＳ０−Ｓ３を算出する。
Ｓ０≡ＳＮ０≡（１６２１０５）≡２１０  （ｍｏｄ  ２１１）
Ｓ１≡ＳＮ１≡（１６２７０）≡１４  （ｍｏｄ  ２１１）
Ｓ２≡ＳＮ２≡（１６２４２）≡１８８  （ｍｏｄ  ２１１）
Ｓ３≡ＳＮ３≡（１６２３０）≡１９９  （ｍｏｄ  ２１１）
【０１１７】
次に、プロセッサは、ステップＳ３６０（式（２５））により、値Ｂ０、Ｂ１、Ｂ２、Ｂ３を求める。
【０１１８】
値Ｂ０に関して、”２Ｎ０≡２１０５≡２１０  （ｍｏｄ  ２１１）”であり、Ｓ０は、”１”、”２１０”のいずれかの値に限定される（１≡２１００  （ｍｏｄ  ２１１）、２１０≡２１０１  （ｍｏｄ  ２１１））。上で求めたシンドロームＳ０は”２１０”であるため、プロセッサは、”Ｂ０≡１  （ｍｏｄ  ２）”を得る。
【０１１９】
値Ｂ１に関して、”２Ｎ１≡２７０≡１９６  （ｍｏｄ  ２１１）”であり、Ｓ１は、”１”、”１９６”、”１４”のいずれかの値に限定される（１≡１９６０  （ｍｏｄ  ２１１）、１９６≡１９６１  （ｍｏｄ  ２１１）、１４≡１９６２  （ｍｏｄ  ２１１））。上で求めたシンドロームＳ１は”１４”であるため、プロセッサは、”Ｂ１≡２  （ｍｏｄ  ３）”を得る。
【０１２０】
値Ｂ２に関して、”２Ｎ２≡２４２≡１０７  （ｍｏｄ  ２１１）”であり、Ｓ２は、”１”、”１０７”、”５５”、”１８８”、”７１”のいずれかの値に限定される（１≡１０７０  （ｍｏｄ  ２１１）、１０７≡１０７１  （ｍｏｄ  ２１１）、５５≡１０７２  （ｍｏｄ  ２１１）、１８８≡１０７３  （ｍｏｄ  ２１１）、７１≡１０７４  （ｍｏｄ  ２１１））。上で求めたシンドロームＳ２は”１８８”であるため、プロセッサは、”Ｂ２≡３  （ｍｏｄ  ５）”を得る。
【０１２１】
値Ｂ３に関して、”２Ｎ３≡２３０≡１７１  （ｍｏｄ  ２１１）”であり、Ｓ３は、”１”、”１７１”、”１２３”、”１４４”、”１４８”、”１９９”、”５８”のいずれかの値に限定される（１≡１７１０  （ｍｏｄ  ２１１）、１７１≡１７１１  （ｍｏｄ  ２１１）、１２３≡１７１２  （ｍｏｄ  ２１１）、１４４≡１７１３  （ｍｏｄ  ２１１）、１４８≡１７１４  （ｍｏｄ  ２１１）、１９９≡１７１５  （ｍｏｄ  ２１１）、５８≡１７１６  （ｍｏｄ  ２１１））。上で求めたシンドロームＳ３は”１９９”であるため、プロセッサは、”Ｂ３≡５  （ｍｏｄ  ７）”を得る。
【０１２２】
求められた値Ｂ０、Ｂ１、Ｂ２、Ｂ３より、プロセッサは、中国剰余定理を用いて、１６２≡２ＢＩＴ（ｍｏｄ  ２１１）を満たすＢＩＴ＝１７３を算出する。
【０１２３】
以上、この実施形態では、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎアルゴリズムおよび中国剰余定理を利用することで、誤り検出の演算負荷を軽減できる。
【０１２４】
図１４は、図１から図１３に示した符号化方法および誤り検出方法を実現するデータ処理装置の例を示している。例えば、データ処理装置は、メモリシステムＭＳＹＳである。
【０１２５】
メモリシステムＭＳＹＳは、ＣＰＵおよび半導体メモリＭＥＭを含んでいる。例えば、ＣＰＵは、内蔵するＲＯＭ（Read Only Memory）に格納された符号化プログラムを実行することにより、誤り検出符号Ｃを生成し、生成した誤り検出符号ＣをデータＤに付加して符号Ｅを生成するコンピュータの一例である。そして、ＣＰＵは、生成した符号Ｅを半導体メモリＭＥＭに書き込む。例えば、半導体メモリＭＥＭは、ＤＲＡＭ（Dynamic Random Access Memory）、フラッシュメモリまたはＳＲＡＭ（Random Access Memory）等である。
【０１２６】
また、ＣＰＵは、内蔵するＲＯＭに格納された誤り検出プログラムを実行することにより、半導体メモリＭＥＭから読み出した符号Ｅに含まれるビット誤りを検出するコンピュータの一例である。ＣＰＵは、訂正可能なビット誤りを検出した場合、誤りを訂正してもよい。なお、ＣＰＵは、外部のＲＯＭに格納された符号化プログラムおよび誤り検出プログラムを実行してもよい。また、ＣＰＵは、外部から内蔵するＲＡＭに転送される符号化プログラムおよび誤り検出プログラムを実行してもよい。
【０１２７】
ＣＰＵは、内蔵する四則演算回路を用いて符号化方法および誤り検出方法を実行する。すなわち、符号化方法を実行する四則演算回路は、符号化部として機能し、誤り検出方法を実行する四則演算回路は、誤り検出部として機能する。また、符号化方法を実行するＣＰＵは、符号化装置として機能し、誤り検出方法を実行するＣＰＵは、誤り検出装置として機能する。
【０１２８】
例えば、符号化部は、データＤと補正値Ｋの積を除数Ｍで除して誤り検出符号Ｃを生成する第１演算部と、データＤに誤り検出符号Ｃを付加して符号Ｅを生成する第２演算部とを有している。第１演算部および第２演算部の演算回路は、互いに重複していてもよい。
【０１２９】
例えば、誤り検出部は、第３演算部および第４演算部を有している。第３演算部は、符号Ｅを除数Ｍで除してシンドロームＳを生成する。第４演算部は、シンドロームＳがゼロのときに符号Ｅに誤りがないことを検出し、シンドロームＳがゼロでないときに符号Ｅに誤りがあることを検出する。第３演算部および第４演算部の演算回路は、互いに重複していてもよい。
【０１３０】
図１５は、図１から図１３に示した符号化方法および誤り検出方法を実現するデータ処理装置の別の例を示している。例えば、データ処理装置は、通信システムＣＳＹＳである。
【０１３１】
通信システムＣＳＹＳは、ＣＰＵをそれぞれ内蔵する送信装置および受信装置を含んでいる。送信装置のＣＰＵは、内蔵するＲＯＭに格納された符号化プログラムを実行することにより、誤り検出符号Ｃを生成し、生成した誤り検出符号ＣをデータＤに付加して符号Ｅを生成するコンピュータの一例である。そして、送信装置は、生成した符号Ｅを受信装置に送信する。
【０１３２】
送信装置のＣＰＵは、内蔵する四則演算回路を用いて符号化方法を実行する。すなわち、符号化方法を実行する四則演算回路は、符号化部として機能する。また、符号化方法を実行するＣＰＵは、符号化装置として機能する。例えば、符号化部は、データＤと補正値Ｋの積を除数Ｍで除して誤り検出符号Ｃを生成する第１演算部と、データＤに誤り検出符号Ｃを付加して符号Ｅを生成する第２演算部とを有している。第１演算部および第２演算部の演算回路は、互いに重複していてもよい。
【０１３３】
受信装置のＣＰＵは、内蔵するＲＯＭに格納された誤り検出プログラムを実行することにより、送信装置から受信した符号Ｅに含まれるビット誤りを検出するコンピュータの一例である。受信装置のＣＰＵは、訂正可能なビット誤りを検出した場合、誤りを訂正してもよい。なお、送信装置および受信装置のＣＰＵは、外部のＲＯＭに格納された符号化プログラムおよび誤り検出プログラムを実行してもよい。また、ＣＰＵは、外部から内蔵するＲＡＭに転送される符号化プログラムおよび誤り検出プログラムを実行してもよい。
【０１３４】
受信装置のＣＰＵは、内蔵する四則演算回路を用いて誤り検出方法を実行する。すなわち、誤り検出方法を実行する四則演算回路は、誤り検出部として機能する。また、誤り検出方法を実行するＣＰＵは、誤り検出装置として機能する。例えば、誤り検出部は、第３演算部および第４演算部を有している。第３演算部は、符号Ｅを除数Ｍで除してシンドロームＳを生成する。第４演算部は、シンドロームＳがゼロのときに符号Ｅに誤りがないことを検出し、シンドロームＳがゼロでないときに符号Ｅに誤りがあることを検出する。第３演算部および第４演算部の演算回路は、互いに重複していてもよい。
【０１３５】
以上の詳細な説明により、実施形態の特徴点および利点は明らかになるであろう。これは、特許請求の範囲がその精神および権利範囲を逸脱しない範囲で前述のような実施形態の特徴点および利点にまで及ぶことを意図するものである。また、当該技術分野において通常の知識を有する者であれば、あらゆる改良および変更に容易に想到できるはずであり、発明性を有する実施形態の範囲を前述したものに限定する意図はなく、実施形態に開示された範囲に含まれる適当な改良物および均等物に拠ることも可能である。
【符号の説明】
【０１３６】
ＡＬＬ‥符号；ｂｉｔ‥ビット情報；ＢＩＴ‥ビット番号；Ｃ、Ｃ’‥誤り検出符号；ＣＳＹＳ‥通信システム；Ｄ‥データ；Ｅ‥符号；Ｊ‥付加値；Ｋ‥補正値；Ｍ‥除数；ＭＥＭ‥半導体メモリ；ＭＳＹＳ‥メモリシステム；Ｓ‥シンドローム
【図１】
2014072852.tif 000003
【図２】
2014072852.tif 000004
【図３】
2014072852.tif 000005
【図４】
2014072852.tif 000006
【図５】
2014072852.tif 000007
【図６】
2014072852.tif 000008
【図７】
2014072852.tif 000009
【図８】
2014072852.tif 000010
【図９】
2014072852.tif 000011
【図１０】
2014072852.tif 000012
【図１１】
2014072852.tif 000013
【図１２】
2014072852.tif 000014
【図１３】
2014072852.tif 000015
【図１４】
2014072852.tif 000016
【図１５】
2014072852.tif 000017