(57)【要約】【課題】誤り訂正を高速に行う。【解決手段】複数のシンボルを含む受信語において所定の条件が満たされない場合には誤り位置検出部が、判定対象のシンボルに誤りがあるか否かを判定する判定処理を行って誤りのあるシンボルの位置である前記誤りの位置を検出する。判定対象変更部が、判定処理が行われるたびに受信語において判定対象のシンボルの位置を変更する。所定の条件が満たされた場合には未検出数検出部が、誤りの位置と受信語から生成された変数との関係に基づいて判定処理が行われていないシンボルにおける誤りの位置を検出する。誤り訂正部が、誤り位置検出部および未検出位置検出部により検出された誤りの位置における誤りを訂正する。【選択図】図７
2015106872.tif 000002
【特許請求の範囲】
【請求項１】
複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルについて誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出部と、
前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更部と、
前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出部と、
前記誤り位置検出部および前記未検出位置検出部により検出された前記誤りの位置における誤りを訂正する誤り訂正部と
を具備する誤り訂正装置。
【請求項２】
前記誤り位置検出部における前記誤りの位置の検出結果に基づいて前記検出数を計数する検出数カウンタをさらに具備し、
前記所定の条件は、前記検出数が一定数を超えることである
請求項１記載の誤り訂正装置。
【請求項３】
前記所定の条件は、前記判定処理が行われていない前記シンボルにおける前記誤りの位置の個数が所定数に満たないことである
請求項１記載の誤り訂正装置。
【請求項４】
前記判定対象変更部は、前記判定処理が行われるたびに前記判定処理が行われていない前記シンボルにおいて前記誤りの位置があるか否かを判断して前記誤りの位置があれば前記判定対象のシンボルの位置を変更する
請求項１記載の誤り訂正装置。
【請求項５】
前記誤り位置検出部における誤りの位置の検出結果に基づいて前記検出数を計数する検出数カウンタをさらに具備し、
前記所定の条件は、前記検出数が一定数を超えることと前記判定対象のシンボルの位置が所定の範囲内であることとの両方が成立することである
請求項４記載の誤り訂正装置。
【請求項６】
前記所定の条件は、前記判定処理が行われていない前記シンボルにおける前記誤りの位置の個数が所定数に満たないことと前記判定対象のシンボルの位置が前記所定の範囲内であることとの両方が成立することである
請求項４記載の誤り訂正装置。
【請求項７】
前記変数は、誤り位置多項式の係数であり、
前記未検出位置検出部は、予め定められた前記係数と前記誤りの位置との関係に基づいて前記誤りの位置を検出する
請求項１記載の誤り訂正装置。
【請求項８】
前記未検出位置検出部は、ＧＦ(２)のｍ次拡大体ＧＦ(２ｍ)の元をＣとして
Ｔｒ（Ｃ）＝Ｃ＾２０＋Ｃ＾２１＋・・・＋Ｃ＾２ｍ−１
においてＴ（Ｃ）＝１となるＣをＤとし、前記誤りの位置を示す前記有限体の元をｘとし、前記誤り位置多項式におけるｘ０の係数をＰ０とし、前記誤り位置多項式におけるｘ１の係数をＰ１とし、前記誤り位置多項式におけるｘ２の係数をＰ２として
ｙ＝ｘ（Ｐ２／Ｐ１）
Ｂ＝（Ｐ０・Ｐ２）／（Ｐ１）２
ｙ１＝（１／Ｔｒ（Ｄ））・｛Ｂ・Ｄ２＋（Ｂ＋Ｂ２）・Ｄ＾（２２）＋・・・
＋（Ｂ＋Ｂ＾２＋・・・Ｂ＾２ｍ−２）・Ｄ＾（２ｍ−１）
ｙ２＝ｙ１＋１
におけるｙ１およびｙ２のそれぞれに対応するｘの示す前記誤りの位置を検出する
請求項７記載の誤り訂正装置。
【請求項９】
前記受信語から生成された前記変数を保持する変数保持部と、
前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記変数を更新する変数更新部とをさらに具備する
請求項１記載の誤り訂正装置。
【請求項１０】
前記変数更新部は、前記判定対象のシンボルの位置が所定の範囲内である場合には前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記変数を更新する
請求項９記載の誤り訂正装置。
【請求項１１】
前記変数更新部は、前記誤りの位置が検出されるたびに前記誤り位置検出部において前記判定処理が行われていない前記シンボルにおける前記誤りの位置の個数が１つであるか否かを判断して前記個数が１つでない場合には前記変数を更新し、
前記未検出位置検出部は、前記個数が１つである場合に前記更新された変数と前記誤りの位置との関係に基づいて前記誤りの位置を検出する
請求項９記載の誤り訂正装置。
【請求項１２】
前記受信語から生成されたベクトルをシンドロームとして保持するシンドローム保持部と、
前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記保持されたシンドロームを更新するシンドローム更新部と、
前記保持されたシンドロームから前記変数を生成して前記未検出位置検出部に供給する変数生成部とをさらに具備する
請求項１記載の誤り訂正装置。
【請求項１３】
前記受信語から第１の誤り位置多項式を生成する第１の誤り位置多項式生成部と、
第２の誤り位置多項式を初期化して前記誤りの位置が検出されるたびに前記誤りの位置を示す一次の多項式を前記第２の誤り位置多項式に乗算する処理により前記第２の誤り位置多項式を更新する乗算部と、
前記所定の条件が満たされた場合には前記第２の誤り位置多項式により前記第１の誤り位置多項式を除算して当該除算により生成した多項式の係数を前記変数として前記未検出位置検出部に供給する除算部と
をさらに具備する請求項１記載の誤り訂正装置。
【請求項１４】
前記誤りの位置と前記受信語から生成された前記変数との関係に基づいて前記誤りの位置を検出して当該検出した誤りの位置の個数である誤り数が所定値を超えるか否かを判定する誤り数判定部をさらに具備し、
前記誤り位置検出部は、前記誤り数が前記所定値を超える場合または前記所定の条件が満たされない場合には前記誤りの位置を検出する
請求項１記載の誤り訂正装置。
【請求項１５】
前記誤り位置検出部は、複数の判定対象のシンボルについて前記判定処理を行い、
前記判定対象変更部は、前記複数の判定対象のシンボルの位置について前記判定処理が行われるたびに前記複数の判定対象のシンボルの位置のそれぞれを変更する
請求項１記載の誤り訂正装置。
【請求項１６】
前記検出された誤りの位置から誤り値を生成する誤り値生成部をさらに具備し、
前記受信語は、ＲＳ（Reed-Solomon）符号、または、ｍを２以上の整数としてｑ（＝２ｍ）元ＢＣＨ符号の符号語に対応する受信語であり、
前記誤り訂正部は、前記誤り位置検出部および前記未検出位置検出部により検出された前記誤りの位置において前記誤り値を使用して前記誤りを訂正する
請求項１記載の誤り訂正装置。
【請求項１７】
前記受信語は、２元ＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号の符号語に対応する受信語であり、
前記誤り訂正部は、前記誤りの位置において前記シンボルの値を反転する
請求項１記載の誤り訂正装置。
【請求項１８】
誤り位置検出部が、複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルに誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出手順と、
判定対象変更部が、前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更手順と、
未検出位置検出部が、前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出手順と、
誤り訂正部が、前記誤り位置検出手順および前記未検出位置検出手順により検出された前記誤りの位置における誤りを訂正する誤り訂正手順と
を具備する誤り訂正方法。
【請求項１９】
誤り位置検出部が、複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルに誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出手順と、
判定対象変更部が、前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更手順と、
未検出位置検出部が、前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出手順と、
誤り訂正部が、前記誤り位置検出手順および前記未検出位置検出手順により検出された前記誤りの位置における誤りを訂正する誤り訂正手順と
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、誤り訂正装置、誤り訂正方法およびプログラムに関する。詳しくは、誤り検出訂正符号を使用する誤り訂正装置、誤り訂正方法およびプログラムに関する。
【背景技術】
【０００２】
従来より、放送システム、通信システムやメモリシステムなどの様々なシステムにおいて、信頼性向上のために、誤り検出訂正符号（ＥＣＣ：Error detection and Correction Code）が用いられている。例えば、メモリシステムにおいては、メモリコントローラ等がデータを、ＥＣＣを用いて符号化してメモリに記録し、そのＥＣＣに基づいて、読み出したデータにおける誤りの検出および訂正を行う。
【０００３】
ここで、誤り訂正の手法は、ＥＣＣとして用いられる符号の種類により異なる。例えば、ＥＣＣとしてＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号を用いるシステムにおいて復号器は、ｎ（ｎは、符号長）個のシンボルからなる受信語から、シンドロームと呼ばれるベクトルを生成する。そして、復号器は、そのシンドロームから誤り位置多項式を生成する。この誤り位置多項式の次数は、復号が可能であれば、受信語に含まれる誤りの個数(以下、「誤り数」と称する。)Ｎｅに等しく、また、誤り位置多項式の根Ａ-ｉの逆元Ａｉにおけるべき指数ｉは、ｎ個のシンボルのうち、誤りのあるシンボルの位置を示す。ただし、ＡはＢＣＨ符号を定義する有限体の原始元であり、ｉは、０乃至ｎ−１の整数である。また、誤りのあるシンボルの位置ｉは誤り位置と呼ばれる。
【０００４】
誤り位置多項式の根の逆元Ａｉと誤り位置ｉとが１対１で対応するため、その根を求めることにより、復号器は、誤り位置を検出することができる。
【０００５】
誤り位置の検出において、誤り数Ｎｅが３以上である場合、誤り位置多項式の次数が３以上になるため、因数分解などの代数的手法による根の算出が困難となる。そこで、３つ以上の誤りの発生が想定される際には、一般に、ｎ個のシンボルの各々に対応する根の候補を順に誤り位置多項式に代入するチェン探索法が用いられる（例えば、特許文献１参照。）。ある候補の代入により、誤り位置多項式の値が零になるのであれば、その候補の逆元のべき指数ｉの示す位置が誤り位置として検出される。言い換えれば、チェン探索法では、ｎ個のシンボルのそれぞれについて順に、その位置が誤り位置であるか否かが判定される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００９−２１２６２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述の従来技術では、誤り訂正にかかる遅延時間が長くなるおそれがある。前述したように、上述のチェン探索法においては、ｎ個のシンボルの各々について順に、その位置が誤り位置であるか否かが判定される。このため、符号長ｎが長くなるほど誤り訂正時間が長くなるおそれがある。
【０００８】
本技術はこのような状況に鑑みて生み出されたものであり、誤り訂正を高速に行うことを目的とする。
【課題を解決するための手段】
【０００９】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルについて誤りがあるか否かを判定する判定処理を行って誤りのある上記シンボルの位置である誤りの位置を検出する誤り位置検出部と、上記判定処理が行われるたびに上記受信語において上記判定対象のシンボルの位置を変更する判定対象変更部と、上記所定の条件が満たされた場合には上記誤りの位置と上記受信語から生成された変数との関係に基づいて上記判定処理が行われていない上記シンボルにおける上記誤りの位置を検出する未検出位置検出部と、上記誤り位置検出部および上記未検出位置検出部により検出された上記誤りの位置における誤りを訂正する誤り訂正部とを具備する誤り訂正装置、および、誤り訂正方法、ならびに、当該方法をコンピュータに実行させるためのプログラムである。これにより、所定の条件が満たされた場合には誤りの位置と受信語から生成された変数との関係に基づいて判定処理が行われていない上記シンボルにおける誤りの位置が検出されるという作用をもたらす。
【００１０】
また、この第１の側面において、上記誤り位置検出部における上記誤りの位置の検出結果に基づいて上記検出数を計数する検出数カウンタをさらに具備し、上記所定の条件は、上記検出数が一定数を超えることであってもよい。これにより、検出数が一定数を超えた場合には、誤りの位置と受信語から生成された変数との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１１】
また、この第１の側面において、上記所定の条件は、上記所定の条件は、上記判定処理が行われていない上記シンボルにおける上記誤りの位置の個数が所定数に満たないことであるであってもよい。これにより、判定処理が行われていない上記シンボルにおける誤りの位置の個数が所定数に満たない場合には、誤りの位置と受信語から生成された変数との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１２】
また、この第１の側面において、上記判定対象変更部は、上記判定対象変更部は、上記判定処理が行われるたびに上記判定処理が行われていない上記シンボルにおいて上記誤りの位置があるか否かを判断して上記誤りの位置があれば上記判定対象のシンボルの位置を変更してもよい。これにより、判定処理が行われていないシンボルにおいて誤りの位置があれば判定対象のシンボルの位置が変更されるという作用をもたらす。
【００１３】
また、この第１の側面において、上記誤り位置検出部における誤りの位置の検出結果に基づいて上記検出数を計数する検出数カウンタをさらに具備し、上記所定の条件は、上記検出数が一定数を超えることと上記判定対象のシンボルの位置が所定の範囲内であることとの両方が成立することであってもよい。これにより、検出数が一定数を超えることと判定対象のシンボルの位置が所定の範囲内であることとの両方が成立する場合には、誤りの位置と受信語から生成された変数との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１４】
また、この第１の側面において、上記所定の条件は、上記判定処理が行われていない上記シンボルにおける上記誤り位置の個数が所定数に満たないことと上記判定対象のシンボルの位置が上記所定の範囲内であることとの両方が成立することであってもよい。これにより、定処理が行われていない上記シンボルにおける上記誤り位置の個数が所定数に満たないことと判定対象のシンボルの位置が所定の範囲内であることとの両方が成立する場合には、誤りの位置と受信語から生成された変数との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１５】
また、この第１の側面において、上記変数は、誤り位置多項式の係数であり、上記未検出位置検出部は、予め定められた上記係数と上記誤りの位置との関係に基づいて上記誤りの位置を検出してもよい。これにより、予め定められた係数と誤りの位置との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１６】
また、この第１の側面において、上記未検出位置検出部は、ＧＦ(２)のｍ次拡大体ＧＦ(２ｍ)の元をＣとして
Ｔｒ（Ｃ）＝Ｃ＾２０＋Ｃ＾２１＋・・・＋Ｃ＾２ｍ−１
においてＴ（Ｃ）＝１となるＣをＤとし、上記誤りの位置を示す上記有限体の元をｘとし、上記誤り位置多項式におけるｘ０の係数をＰ０とし、上記誤り位置多項式におけるｘ１の係数をＰ１とし、上記誤り位置多項式におけるｘ２の係数をＰ２として
ｙ＝ｘ（Ｐ２／Ｐ１）
Ｂ＝（Ｐ０・Ｐ２）／（Ｐ１）２
ｙ１＝（１／Ｔｒ（Ｄ））・｛Ｂ・Ｄ２＋（Ｂ＋Ｂ２）・Ｄ＾（２２）＋・・・
＋（Ｂ＋Ｂ＾２＋・・・Ｂ＾２ｍ−２）・Ｄ＾（２ｍ−１）
ｙ２＝ｙ１＋１
におけるｙ１およびｙ２のそれぞれに対応するｘの示す上記誤りの位置を検出してもよい。これにより、上式におけるｙ１およびｙ２のそれぞれに対応するｘの示す誤りの位置が検出されるという作用をもたらす。
【００１７】
また、この第１の側面において、上記受信語から生成された上記変数を保持する変数保持部と、上記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて上記変数を更新する変数更新部とをさらに具備してもよい。これにより、誤りの位置が検出されるたびに更新された変数と誤りの位置との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００１８】
また、この第１の側面において、上記変数更新部は、上記判定対象のシンボルの位置が所定の範囲内である場合には上記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて上記変数を更新してもよい。これにより、判定対象のシンボルの位置が所定の範囲内である場合には誤りの位置が検出されるたびに変数が更新されるという作用をもたらす。
【００１９】
また、この第１の側面において、上記変数更新部は、上記誤りの位置が検出されるたびに上記誤り位置検出部において上記判定処理が行われていない上記シンボルにおける上記誤りの位置の個数が１つであるか否かを判断して上記個数が１つでない場合には上記変数を更新し、上記未検出位置検出部は、上記個数が１つである場合に上記更新された変数と上記誤りの位置との関係に基づいて上記誤りの位置を検出してもよい。これにより、判定処理が行われていない上記シンボルにおける誤りの位置の個数が１つでない場合には変数が更新され、その個数が１つである場合に変数と誤りの位置との関係に基づいて誤りの位置が検出されるという作用をもたらす。
【００２０】
また、この第１の側面において、上記受信語から生成されたベクトルをシンドロームとして保持するシンドローム保持部と、上記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて上記保持されたシンドロームを更新するシンドローム更新部と、上記保持されたシンドロームから上記変数を生成して上記未検出位置検出部に供給する変数生成部とをさらに具備してもよい。これにより、誤りの位置が検出されるたびに更新されたシンドロームから変数が生成されるという作用をもたらす。
【００２１】
また、この第１の側面において、上記受信語から第１の誤り位置多項式を生成する第１の誤り位置多項式生成部と、第２の誤り位置多項式を初期化して上記誤りの位置が検出されるたびに上記誤りの位置を示す一次の多項式を上記第２の誤り位置多項式に乗算する処理により上記第２の誤り位置多項式を更新する乗算部と、上記所定の条件が満たされた場合には上記第２の誤り位置多項式により上記第１の誤り位置多項式を除算して当該除算により生成した多項式の係数を上記変数として上記未検出位置検出部に供給する除算部とをさらに具備してもよい。これにより、誤りの位置が検出されるたびに誤りの位置を示す一次の多項式を第２の誤り位置多項式に乗算する処理により第２の誤り位置多項式が更新され、所定の条件が満たされた場合には第２の誤り位置多項式により第１の誤り位置多項式が除算されるという作用をもたらす。
【００２２】
また、この第１の側面において、上記誤りの位置と上記受信語から生成された上記変数との関係に基づいて上記誤りの位置を検出して当該検出した誤りの位置の個数である誤り数が所定値を超えるか否かを判定する誤り数判定部をさらに具備し、上記誤り位置検出部は、上記誤り数が上記所定値を超える場合または上記所定の条件が満たされない場合には上記誤りの位置を検出してもよい。これにより、誤り数が所定値を超える場合または所定の条件が満たされない場合に誤り位置検出部により誤りの位置が検出されるという作用をもたらす。
【００２３】
また、この第１の側面において、上記誤り位置検出部は、複数の判定対象のシンボルについて上記判定処理を行い、上記判定対象変更部は、上記複数の判定対象のシンボルの位置について上記判定処理が行われるたびに上記複数の判定対象のシンボルの位置のそれぞれを変更してもよい。これにより、複数の判定対象のシンボルについて判定処理が行われるという作用をもたらす。
【００２４】
また、この第１の側面において、上記誤り位置検出部および上記未検出位置検出部により検出された上記検出された誤りの位置から誤り値を生成する誤り値生成部をさらに具備し、上記受信語は、ＲＳ（Reed-Solomon）符号、または、ｍを２以上の整数としてｑ（＝２ｍ）元ＢＣＨ符号の符号語に対応する受信語であり、上記誤り訂正部は、上記誤りの位置において上記誤り値を使用して上記誤りを訂正してもよい。これにより、誤り値の使用により誤りが訂正されるという作用をもたらす。
【００２５】
また、この第１の側面において、上記受信語は、２元ＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号の符号語に対応する受信語であり、上記誤り訂正部は、上記誤りの位置において上記シンボルの値を反転してもよい。これにより、シンボルの値の判定により誤りが訂正されるという作用をもたらす。
【発明の効果】
【００２６】
本技術によれば、誤り訂正を高速に行うことができるという優れた効果を奏し得る。なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【図面の簡単な説明】
【００２７】
【図１】第１の実施の形態における情報処理システムの一構成例を示すブロック図である。
【図２】第１の実施の形態におけるホストコンピュータの一構成例を示すブロック図である。
【図３】第１の実施の形態におけるメモリコントローラの一構成例を示すブロック図である。
【図４】第１の実施の形態におけるＥＣＣ処理部の一構成例を示すブロック図である。
【図５】第１の実施の形態における符号語および検査行列の一例である。
【図６】第１の実施の形態における復号部の一構成例を示すブロック図である。
【図７】第１の実施の形態における誤り位置検出部の一構成例を示すブロック図である。
【図８】第１の実施の形態における数式処理部の一構成例を示すブロック図である。
【図９】第１の実施の形態におけるメモリコントローラの動作の一例を示すフローチャートである。
【図１０】第１の実施の形態におけるリード処理の一例を示すフローチャートである。
【図１１】第１の実施の形態における誤り位置検出処理の一例を示すフローチャートである。
【図１２】第１の実施の形態における数式処理の一例を示すフローチャートである。
【図１３】第１の変形例における誤り位置検出部の一構成例を示すブロック図である。
【図１４】第１の変形例における数式処理部の一構成例を示すブロック図である。
【図１５】第２の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図１６】第３の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図１７】第４の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図１８】第５の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図１９】第６の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図２０】第７の変形例における誤り位置検出処理の一例を示すフローチャートである。
【図２１】第２の実施形態における誤り位置検出部の一構成例を示すブロック図である。
【図２２】第２の実施の形態における誤り位置検出処理の一例を示すフローチャートである。
【図２３】第３の実施形態における誤り位置検出部の一構成例を示すブロック図である。
【図２４】第３の実施の形態における誤り位置検出処理の一例を示すフローチャートである。
【図２５】第４の実施の形態における復号部の一構成例を示すブロック図である。
【図２６】第４の実施の形態における二重以下誤り判定部の一構成例を示すブロック図である。
【図２７】第４の実施の形態におけるリード処理の一例を示すフローチャートである。
【図２８】第４の実施の形態における二重以下誤り判定処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００２８】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（検出数が一定数を超えると公式により誤り位置を検出する例）
２．第２の実施の形態（シンドロームを更新して検出数が一定数を超えると公式により誤り位置を検出する例）
３．第３の実施の形態（誤り数が所定値以下である場合または検出数が一定数を超える場合に公式により誤り位置を検出する例）
【００２９】
＜１．第１の実施の形態＞
［情報処理システムの構成例］
図１は、実施の形態における情報処理システムの一構成例を示すブロック図である。この情報処理システムは、ホストコンピュータ１００およびストレージ２００を備える。
【００３０】
ホストコンピュータ１００は、情報処理システム全体を制御するものである。具体的には、ホストコンピュータ１００は、コマンドおよびライトデータを生成してストレージ２００に信号線１０９を介して供給する。また、ホストコンピュータ１００は、ストレージ２００からリードデータを受け取る。ここで、コマンドは、ストレージ２００を制御するためのものであり、例えば、ライトデータの書込みを指示するライトコマンドや、リードデータの読出しを指示するリードコマンドを含む。
【００３１】
ストレージ２００は、メモリコントローラ３００および不揮発性メモリ４００を備える。このメモリコントローラ３００は、不揮発性メモリ４００を制御するものである。メモリコントローラ３００は、ホストコンピュータ１００からライトコマンドおよびライトデータを受け取った場合には、そのライトデータから誤り検出訂正符号（ＥＣＣ：Error detection and Correction Code）で符号化する。メモリコントローラ３００は、不揮発性メモリ４００に信号線３０９を介してアクセスして符号化したデータを書き込む。
【００３２】
また、ホストコンピュータ１００からリードコマンドを受け取った場合、メモリコントローラ３００は、不揮発性メモリ４００に信号線３０９を介してアクセスして符号化されたデータを読み出す。そして、メモリコントローラ３００は、符号化されたデータを、符号化前のデータに変換（すなわち、復号）する。復号においてメモリコントローラ３００は、ＥＣＣに基づいてデータにおける誤りの検出および訂正を行う。そして、メモリコントローラ３００は、訂正したデータをホストコンピュータ１００に供給する。なお、メモリコントローラ３００は、特許請求の範囲に記載の誤り訂正装置の一例である。
【００３３】
不揮発性メモリ４００は、メモリコントローラ３００の制御に従って、データを記憶するものである。例えば、フラッシュメモリが不揮発性メモリ４００として用いられる。
【００３４】
なお、フラッシュメモリの代わりに、ＲｅＲＡＭ（resistance random access memory）やＰＣＲＡＭ（Phase change Random Access Memory）を不揮発性メモリ４００として用いてもよい。または、フラッシュメモリの代わりにＭＲＡＭ（Magnetoresistive Random Access Memory）を不揮発性メモリ４００として用いてもよい。また、メモリコントローラ３００は、データを不揮発性メモリ４００に記録しているが、データを記録することができる媒体や装置であれば、不揮発性メモリ４００以外の記録媒体や記憶装置にデータを記録してもよい。そのような記憶装置の一例として、ハードディスクドライブ（ＨＤＤ：Hard Disk Drive）などを想定することができる。
【００３５】
また、記録媒体等にアクセスする際に符号化および復号が行われているが、この構成に限定されない。通信システムや放送システムなどにおいて、送信装置および受信装置が符号化および復号を行ってもよい。
【００３６】
［ホストコンピュータの構成例］
図２は、第１の実施の形態におけるホストコンピュータ１００の一構成例を示すブロック図である。このホストコンピュータ１００は、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３およびＣＰＵ（Central Processing Unit）１０４を備える。また、ホストコンピュータ１００は、ユーザインターフェース１０１、バス１０５およびストレージインターフェース１０６を備える。
【００３７】
ユーザインターフェース１０１は、情報処理システムと、その利用者とが互いに、入力データや出力データをやりとりするためのインターフェースである。ＲＯＭ１０２は、ＣＰＵ１０４が実行するプログラム等を記憶するものである。ＲＡＭ１０３は、ＣＰＵ１０４が実行する処理において必要となるデータを一時的に保持するものである。ＣＰＵ１０４は、ホストコンピュータ１００全体を制御するものである。バス１０５は、ユーザインターフェース１０１、ＲＯＭ１０２、ＲＡＭ１０３、ＣＰＵ１０４およびストレージインターフェース１０６が相互にデータを交換するための共通の経路である。ストレージインターフェース１０６は、ホストコンピュータ１００とストレージ２００とがデータやコマンドを相互に交換するためのインターフェースである。
【００３８】
［メモリコントローラの構成例］
図３は、第１の実施の形態におけるメモリコントローラ３００の一構成例を示すブロック図である。このメモリコントローラ３００は、ホストインターフェース３０１、ＲＯＭ３０２、ＲＡＭ３０３、ＣＰＵ３０４、ＥＣＣ処理部３１０、バス３０５および不揮発性メモリインターフェース３０６を備える。
【００３９】
ホストインターフェース３０１は、メモリコントローラ３００がホストコンピュータ１００との間でデータやコマンドを相互に交換するものである。ＲＡＭ３０３は、ＣＰＵ３０４が実行する処理において必要となるデータを一時的に保持するものである。
【００４０】
ＥＣＣ処理部３１０は、ライトデータを符号化し、また、リードデータを復号するものである。符号化において、ライトデータは所定の単位でＲＳ（Reed-Solomon）符号に符号化される。所定の単位で符号化された個々のデータを以下、「符号語」と称する。それぞれの符号語は、符号化前のデータとパリティとを含む。ＥＣＣ処理部３１０は、符号化したライトデータを不揮発性メモリ４００に不揮発性メモリインターフェース３０６を介して供給する。
【００４１】
なお、ＥＣＣ処理部３１０は、ＲＳ符号にライトデータを符号化しているが、ＢＣＨ符号にライトデータを符号化してもよい。また、ＥＣＣ処理部３１０は、短縮化ＲＳ符号や短縮化ＢＣＨ符号に符号化してもよい。ここで、短縮化ＲＳ符号は、符号長ｎが２ｍ−１（ｍは１以上の整数）未満のＲＳ符号である。短縮化ＢＣＨ符号も同様である。
【００４２】
また、ＥＣＣ処理部３１０は、符号化されたリードデータを元のデータに復号する。復号においてＥＣＣ処理部３１０は、誤り訂正に失敗したか否かを示す訂正不可フラグを生成してホストコンピュータ１００に不揮発性メモリインターフェース３０６を介して供給する。この訂正不可フラグには、例えば、誤り訂正に失敗した場合にはオンが設定され、そうでない場合にはオフが設定される。また、誤りの訂正に成功した場合、ＥＣＣ処理部３１０は、復号した元のデータをホストコンピュータ１００に不揮発性メモリインターフェース３０６を介して供給する。
【００４３】
ＣＰＵ３０４は、メモリコントローラ３００全体を制御するものである。ＲＯＭ３０２は、ＣＰＵ３０４が実行するプログラム等を記憶するものである。バス３０５は、ホストインターフェース３０１、ＲＯＭ３０２、ＲＡＭ３０３、ＣＰＵ３０４、ＥＣＣ処理部３１０および不揮発性メモリインターフェース３０６が相互にデータを交換するための共通の経路である。不揮発性メモリインターフェース３０６は、メモリコントローラ３００が不揮発性メモリ４００との間でデータやコマンドを相互に交換するためのインターフェースである。
【００４４】
［ＥＣＣ処理部の構成例］
図４は、第１の実施の形態におけるＥＣＣ処理部３１０の一構成例を示すブロック図である。このＥＣＣ処理部３１０は、符号化部３１１および復号部３２０を備える。
【００４５】
符号化部３１１は、ライトデータを、ＥＣＣを用いて符号化するものである。復号部３２０は、リードデータを符号語の単位で復号するものである。この復号部３２０は、復号において受信語と所定の検査行列との積を求める。この積により得られるベクトルは、シンドロームと呼ばれる。復号部３２０は、生成したシンドロームから、誤りのあるシンボルの位置を誤り位置として検出し、その誤り位置における誤りを訂正する。復号部３２０は、訂正した受信語からパリティを除いた元のデータを、訂正したデータとして出力する。
【００４６】
図５は、第１の実施の形態における符号語および検査行列の一例を示す図である。図５におけるａは、符号語の一例を示す図である。符号語は、ｎ（ｎは、２以上の整数）個のシンボルを含む。ここで、ｎは、符号長と呼ばれる。また、シンボルは、符号語を構成する一定サイズのデータであり、ＲＳ符号においては、複数のビットからなるデータがシンボルとして用いられる。なお、２元ＢＣＨ符号においては、１ビットのデータがシンボルとして用いられる。
【００４７】
図５におけるｂは、第１の実施の形態における検査行列Ｈの一例である。ここで、検査行列Ｈは、誤り検出および誤り訂正を行う処理において用いられる行列である。検査行列Ｈおよび受信語の積により、シンドロームが生成される。ＲＳ符号においては、同図のｂに例示する検査行列Ｈが用いられる。同図のｂにおいて、ＡはＲＳ符号を定義する有限体の原始元である。また、ｔは整数であり、訂正可能なシンボル数を示す。
【００４８】
図６は、第１の実施の形態における復号部３２０の一構成例を示すブロック図である。この復号部３２０は、誤り検出部３２１、データバッファ３２２、誤り位置検出部３３０、誤り値生成部３２３および誤り訂正部３２４を備える。
【００４９】
誤り検出部３２１は、受信語において誤りの有無を検出するものである。この誤り検出部３２１は、読み出されたリードデータを受信語ｒとして受け取り、その受信語ｒと検査行列Ｈとから次の式を使用してシンドロームｓを生成する。
【００５０】
ｓＴ：＝Ｈ・ｒＴ＝Ｈ（ｃＴ＋ｅＴ）＝Ｈ・ｅＴ                        ・・・式１
上式においてｓＴは、シンドロームｓの転置ベクトルである。ｒＴは、受信語ｒの転置ベクトルである。ｃＴは、符号語の転置ベクトルである。ｅＴは、符号化部３１１から復号部３２０までの経路において生じた誤りの転置ベクトルである。また、「：＝」は、左辺を右辺で定義することを示す。以下の式においても同様である。
【００５１】
具体的には、シンドロームｓの成分ｓｊ（ｊは、０乃至２ｔ−１の整数）は、次の式から求められる。
【数１】
2015106872.tif 000003
【００５２】
誤りベクトルｅｉの誤り位置における成分のそれぞれはゼロ以外の値であり、それ以外の位置における成分は、ゼロの値である。このため、式２より、受信語に１つも誤りがない場合には、誤りベクトルｅｉの成分が全てゼロとなり、シンドロームｓの成分が全てゼロとなる。したがって、誤り検出部３２１は、シンドロームｓの成分が全てゼロであるか否かにより、誤りの有無を検出する。
【００５３】
誤り検出部３２１は、検出結果を示す誤り検出フラグを生成して誤り訂正部３２４に供給する。誤り検出フラグには、例えば、受信語に１つ以上の誤りがあった場合に「１」の値が設定され、そうでない場合に「０」の値が設定される。
【００５４】
また、誤り検出部３２１は、受信語に誤りがあった場合には、シンドロームｓを誤り位置検出部３３０および誤り値生成部３２３に供給する。
【００５５】
誤り位置検出部３３０は、誤り位置を検出するものである。この誤り位置検出部３３０は、例えば、ユークリッドアルゴリズムを使用して誤り位置多項式Ｐ（ｘ）をシンドロームｓから生成する。なお、誤り位置検出部３３０は、ユークリッドアルゴリズムの代わりに、別のアルゴリズム（例えば、ピーターソンアルゴリズム）を使用して、誤り位置多項式Ｐ（ｘ）を求めてもよい。
【００５６】
ユークリッドアルゴリズムは、次の式を満たし、互いに素なｔ次以下の誤り位置多項式Ｐ（ｘ）とｔ−１次以下の誤り評価多項式ｗ（ｘ）とをユークリッドの互除法により求めるアルゴリズムである。ここで、ｘは有限体の元である。
Ｎ（ｘ）ｘ２ｔ＋Ｐ（ｘ）ｓ（ｘ）＝ｗ（ｘ）                       ・・・式３
【００５７】
ユークリッドアルゴリズムにおいて、誤り位置検出部３３０は、まず、次の各式により、Ｂ−１（ｘ）、Ｂ０（ｘ）、Ｒ−１（ｘ）およびＲ０（ｘ）の多項式を定義する。
Ｂ−１（ｘ）＝０                                               ・・・式４
Ｂ０（ｘ）＝１                                                 ・・・式５
Ｒ−１（ｘ）＝ｘ２ｔ                                             ・・・式６
Ｒ０（ｘ）＝ｓ（ｘ）                                           ・・・式７
【００５８】
そして、誤り位置検出部３３０は、変数ｋに１を設定し、Ｒｋ−２（ｘ）をＲｋ−１（ｘ）で割って、その商をＱｋ（ｘ）とし、剰余をＲｋ（ｘ）とする。誤り位置検出部３３０は、これらの結果に基づいて、次の式によりＢｋ（ｘ）を求める。
Ｂｋ（ｘ）＝Ｂｋ−２（ｘ）−Ｑｋ（ｘ）Ｂｋ−１（ｘ）              ・・・式８
【００５９】
誤り位置検出部３３０は、Ｒｋ（ｘ）の次数がｔ（ｔは、訂正可能なシンボル数）未満であるか否かを判断する。Ｒｋ（ｘ）の次数がｔ未満でない場合には、誤り位置検出部３３０は、ｋを「１」増分して、再度Ｒｋ−２（ｘ）をＲｋ−１（ｘ）で割り、Ｂｋ（ｘ）を求め、Ｒｋ（ｘ）の次数がｔ未満であるか否かを再度判断する。
【００６０】
Ｒｋ（ｘ）の次数がｔ未満である場合には、誤り位置検出部３３０は、次の式により、誤り位置多項式Ｐ（ｘ）および誤り評価多項式ｗ（ｘ）を求める。
Ｐ（ｘ）＝Ｂｋ（ｘ）／Ｂｋ（０）                                ・・・式９
ｗ（ｘ）＝Ｒｋ（ｘ）／Ｂｋ（０）                                ・・・式１０
【００６１】
上述のユークリッドアルゴリズムやピーターソンアルゴリズムの詳細は、例えば、「今井秀樹著、『符号理論』、電気情報通信学会出版、１９９０年３月、ｐｐ１６６−１７３」に記載されている。
【００６２】
式９により求められる誤り位置多項式Ｐ（ｘ）は、次の式により表すこともできる。
【数２】
2015106872.tif 000004
【００６３】
上式において、Πは、総乗を示す。また、Ｐａは式１１の右辺を展開したときのｘａの係数である。ただし、この係数Ｐａは固定値でなく、受信語に依存して変化する。また、誤り位置多項式Ｐ（ｘ）の次数（すなわち、最大のａ）は、受信語内の誤り数Ｎｅに等しく、その根の逆元における原始元のべき指数は、誤り位置を示す。誤り数Ｎｅ、すなわち誤り位置多項式Ｐ（ｘ）の次数が３以上であると、因数分解等の代数的手法により誤り位置多項式Ｐ（ｘ）の根を求めることが困難となる。
【００６４】
そこで、誤り数Ｎｅが３以上の場合、誤り位置検出部３３０は、シンボル位置ｉに対応する根の候補Ａ−ｉ（ｉは、０乃至ｎ−１の整数）を順に誤り位置多項式Ｐ（ｘ）に代入し、Ｐ（Ａ−ｉ）がゼロになるか否かを判定する。
【００６５】
Ｐ（Ａ−ｉ）がゼロになるのであれば、誤り位置検出部３３０は、そのときのシンボル位置ｉを誤り位置ｉａとして検出し、保持する。言い換えれば、候補Ａ-ｉの代入により、シンボルごとに、そのシンボルに誤りがあるか否かが順に判定される。このように、根の候補を順に代入して、誤り位置を探索するアルゴリズムは、チェン探索アルゴリズムと呼ばれる。
【００６６】
そして、誤り位置検出部３３０は、誤り位置ｉａを検出するたびに、誤り数Ｎｅと誤り位置の検出数ｂとの差が一定値（例えば、２以下の整数）以下であるか否かを判断する。言い換えれば、誤り位置検出部３３０は、誤り位置の検出数ｂが、一定数（Ｎｅ−２）以上であるか否かを判断する。ここで、誤り数Ｎｅと誤り位置の検出数ｂとの差（Ｎｅ―ｂ）は、未検出の誤りの個数を示す。この（Ｎｅ−ｂ）を以下、「未検出数Ｎｅｈ」と称する。
【００６７】
また、誤り位置検出部３３０は、誤り位置ｉａを検出するたびに、その誤り位置ｉａに基づいて誤り位置多項式Ｐ（ｘ）を更新する。具体的には、誤り位置検出部３３０は、誤り位置多項式Ｐ（ｘ）を｛ｘ−Ａ＾（−ｉａ）｝により割った式により更新する。これにより、誤り位置ｉａが検出されるたびに、誤り位置多項式Ｐ（ｘ）の次数が低減し、その次数は未検出数Ｎｅｈと同じ値となる。
【００６８】
未検出数Ｎｅｈが一定値を超える場合には、誤り位置検出部３３０は、チェン探索アルゴリズムによる誤り位置の検出を継続して行う。
【００６９】
一方、未検出数Ｎｅｈが一定値以下である場合には、誤り位置検出部３３０は、予め定められた、誤り位置多項式における係数と誤り位置との関係を示す公式を使用して誤り位置を検出する。
【００７０】
具体的には、未検出数Ｎｅｈが「１」である場合には、式１１に基づいて、次の式により表される１次の誤り位置多項式Ｐｈ（ｘ）が得られる。
Ｐｈ（ｘ）＝Ｐｈ１ｘ＋Ｐｈ０                                    ・・・式１２
上式において、Ｐｈ１およびＰｈ０は、ｘおよびｘ０の係数である。
【００７１】
式１２の根ｘは、次の式より表される。
ｘ＝−Ｐｈ０／Ｐｈ１                                           ・・・式１３
ただし、Ｐｈ０、Ｐｈ１がＧＦ（２ｍ）の元であれば、根は次の式により表現することができる。
ｘ＝Ｐｈ０／Ｐｈ１                                             ・・・式１４
式１３および式１４の根の逆元における原始元のべき指数が誤り位置を示す。
【００７２】
また、未検出数Ｎｅｈが「２」である場合には、式３に基づいて、次の式により表される２次の誤り位置多項式Ｐｈ（ｘ）が得られる。
Ｐｈ（ｘ）＝Ｐh２ｘ２＋Ｐh１ｘ＋Ｐh０                           ・・・式１５
ただし、上式においてＰh２は、ｘ２の係数であり、ゼロ以外の実数である。
【００７３】
そして、誤り位置検出部３３０は、式１５における係数Ｐ１ｈがゼロであるか否かを判断する。係数Ｐ１ｈがゼロである場合、式１５に例示した誤り位置多項式Ｐｈ（ｘ）は重根をもつこととなり、未検出数Ｎｅｈが「２」であるという前提と矛盾した結果が得られる。このような矛盾は、訂正可能なシンボル数ｔを超える数の誤りが受信語に発生したなどの要因により生じる。
【００７４】
したがって、この場合には、誤り位置検出部３３０は、訂正不可能であると判断し、その判断に基づいて訂正不可フラグを生成して誤り値生成部３２３およびバス３０５に供給する。訂正不可フラグは、受信語を訂正することができる否かを示すフラグであり、例えば、訂正不可能である場合に「１」の値が設定され、そうでない場合に「０」の値が設定される。
【００７５】
式１５の根は、基礎体がＧＦ（２）場合、２次方程式に対する解の公式を利用して求めることができない。そこで、誤り位置検出部３３０は、ヒルベルトの定理における公式を利用して、根を求める。
【００７６】
Ｐh１がゼロでない場合に、誤り位置検出部３３０は、まず、次の式に示すようにＰｈ（ｘ）＝０とおいて変形する。ただし、Ｐｈ（ｘ）は２次多項式であり、ｘ２の係数Ｐｈ２はゼロ以外の値である。
Ｐｈ（ｘ）＝Ｐh２ｘ２＋Ｐh１ｘ＋Ｐh０＝０
ｘ２＋（Ｐh１／Ｐh２）ｘ＋（Ｐh０／Ｐh２）＝０                    ・・・式１６
【００７７】
ここで、次の式に示すようにｙおよびＢを定義する。
ｙ：＝ｘ（Ｐｈ２／Ｐｈ１）
Ｂ：＝（Ｐｈ０・Ｐｈ２）／（Ｐｈ１）２                            ・・・式１７
【００７８】
また、式１６は、式１７において定義したｙおよびＢを用いて、次の式に示すように表すことができる。
ｙ２＋ｙ＋Ｂ＝０                                              ・・・式１８
【００７９】
そして、誤り位置検出部３３０は、式１８において根が存在するか否かを次の式に示すトレースＴｒ（Ｃ）を使用して判断する。
Ｔｒ（Ｃ）＝Ｃ＾２０＋Ｃ＾２１＋・・・＋Ｃ＾２ｍ−１            ・・・式１９
【００８０】
上式において、Ｃは、有限体ＧＦ（２ｍ）における元である。式１７に示したＢをトレースＴｒ（Ｃ）に代入したＴｒ（Ｂ）がゼロになる場合には、式９の根が存在し、そうでない場合には根が存在しない。このため、Ｔｒ（Ｂ）がゼロでない場合には、誤り位置検出部３３０は、訂正不可能であると判断する。
【００８１】
Ｔｒ（Ｂ）がゼロである場合、すなわち根が存在する場合、誤り位置検出部３３０は、有限体ＧＦ（２ｍ）においてＴｒ（Ｄ）が「１」となるＤを求め、次の公式からｙ１およびｙ２を検出する。
ｙ１：＝（１／Ｔｒ（Ｄ））・｛Ｂ・Ｄ２＋（Ｂ＋Ｂ２）・Ｄ＾（２２）＋・・・
＋（Ｂ＋Ｂ＾２＋・・・Ｂ＾２ｍ−２）・Ｄ＾（２ｍ−１）      ・・・式２０
ｙ２：＝ｙ１＋１                                               ・・・式２１
【００８２】
式２０および式２１は、ヒルベルトの定理９０から導出される公式である。ヒルベルトの定理９０における各式の導出方法や証明方法は、例えば、「高山幸秀著、『環・体論II GALOIS理論』、URL:http://www.ritsumei.ac.jp/se/~takayama/galois.pdf」に記載されている。
【００８３】
ｙ１およびｙ２と式１７とにより、次の式を使用して式１６における根ｘ１およびｘ２が求められる。
ｘ１：＝ｙ１・（Ｐh１／Ｐh２）
ｘ２：＝ｙ２・（Ｐh１／Ｐh２）＝ｘ１＋（Ｐh１／Ｐh２）              ・・・式２２
上式における根ｘ１およびｘ２の逆元における原始元のべき指数が、誤り位置ｉ１およびｉ２を示す。
【００８４】
誤り位置検出部３３０は、チェン探索処理または公式（式１３、式１４、または、式１７乃至式２１）により検出した誤り位置と、訂正不可フラグとを誤り値生成部３２３に供給する。
【００８５】
誤り値生成部３２３は、検出された誤り位置のシンボルにおける誤り値を生成するものである。この誤り値生成部３２３は、誤り位置検出部３３０からの訂正不可フラグに基づいて、訂正不可能であるか否かを判断する。
【００８６】
訂正可能である場合、誤り値生成部３２３は、誤り位置検出部３３０により検出された誤り位置においてシンボルの誤りを生成する。生成されたシンボルの値は、誤り値と呼ばれる。誤り値生成部３２３は、例えば、シンドロームを表す式２に、誤り位置を代入して、誤り値に関する連立方程式を解くことにより、誤り値を求める。誤り値生成部３２３は、生成した誤り値を誤り訂正部３２４に供給する。なお、誤り値生成部３２３は、Ｆｏｒｎｅｙアルゴリズムを使用して誤り値を求めてもよい。
【００８７】
誤り訂正部３２４は、受信語の誤りを訂正するものである。この誤り訂正部３２４は、誤り検出部３２１からの誤り検出フラグに基づいて受信語に誤りがあったか否かを判断する。誤りがない場合には、誤り訂正部３２４は、データバッファ３２２から受信語を読み出し、パリティを削除して元のデータとして出力する。なお、誤り訂正部３２４は、訂正不要な受信語からパリティを削除しているが、パリティを削除せずに、訂正不要な受信語をそのまま出力してもよい。
【００８８】
一方、誤りがある場合には、誤り訂正部３２４は、データバッファ３２２から受信語を読み出し、その受信語において誤り位置のシンボルを誤り値により訂正する。誤り訂正部３２４は、訂正後の受信語からパリティを削除して、訂正後の元のデータとして出力する。なお、誤り訂正部３２４は、訂正した受信語からパリティを削除しているが、パリティを削除せずに、訂正した受信語をそのまま出力してもよい。
【００８９】
上述したようにチェン探索処理の途中で、公式（式１３、式１４、または、式１７乃至式２１）を使用した誤り検出に切り替えることにより、誤り位置検出の計算量が低減する。具体的には、ＥＣＣとしてＢＣＨ符号を使用し、有限体ＧＦ（２１３）を用いるものとする。また、符号化前のデータのサイズが４０９６ビットであり、符号語のデータサイズが４２００（＝４０９６＋１３×８）ビットであるものとする。
【００９０】
まず、チェン探索法のみにより誤り位置検出を行う場合を考えると、１クロックサイクルで１つの位置を探索する構成では、符号語のデータサイズが４２００ビットであるため、最大で４２００クロックサイクルが経過してしまう。１クロックサイクルで８つの位置を同時に探索する構成であっても、５２５（＝４２００／８）クロックサイクルが経過してしまう。
【００９１】
これに対して公式を使用した処理では、逆元の計算と、トレースＴｒの計算と、根の計算とのみを行えばよい。逆元計算をテーブル引きにより行うのであれば、逆元、トレースＴｒおよび根の計算のそれぞれは１クロックサイクルで完了する。このため、誤り位置の検出が３クロックサイクルで完了する。ただし、テーブル引きをせずに、逆元を逐次計算する場合には、２８（＝１４×２）クロックサイクルで逆元計算が完了する。この場合には３０クロックサイクルで誤り位置の検出が完了する。まとめると、公式を使用した処理では、３または３０クロックサイクルで誤り位置の検出が完了する。
【００９２】
上述より、誤り数Ｎｅが２以下であると、チェン探索のみを行う構成では最大で５２５または４２００クロックサイクルの遅延が生じるのに対し、誤り数Ｎｅが２以下のときに公式を使用する構成では、３または３０クロックサイクルの遅延しか生じない。
【００９３】
また、誤り数Ｎｅが３以上である場合であっても、メモリコントローラ３００は、残りの誤り位置が２つ以下になったときに、公式を使用する処理に切り替えるため、遅延時間を短くすることができる。例えば、１ビット目と４１９９ビット目と４２００ビット目とに誤りがあった場合、チェン探索のみを行う構成では、５２５または４２００クロックサイクルの遅延時間が生じてしまう。しかし、メモリコントローラ３００は、チェン探索により１ビット目の誤りを検出すると、公式を用いる処理に切り替えて残りの２つの誤り位置を検出するため、４または３１クロックサイクルの遅延時間しか生じない。上述の公式（式１３、式１４、または、式１７乃至式２１）を使用した誤り位置検出の処理を以下、「数式処理」と称する。
【００９４】
なお、メモリコントローラ３００は、未検出数Ｎｅｈが２以下になったときに数式処理に切り替えている。しかし、メモリコントローラ３００は、変形例で後述するように、未検出数Ｎｅｈが２以下になったとき、かつ、シンボル位置ｉが閾値ｉｔｈ未満であるときに数式処理に切り替える構成とすることがより望ましい。ここで、閾値ｉｔｈには、ｉｔｈ以降のシンボルについてチェン探索処理を継続した方が、数式処理に切り替えるよりも誤り位置検出処理が早く終了する値が設定される。後述の図１５以降においては、未検出数Ｎｅｈが２以下になったとき、かつ、シンボル位置ｉが閾値ｉｔｈ未満（言い換えれば、シンボル位置ｉが所定の位置）であるときに数式処理に切り替えられる。この閾値ｉｔｈ未満の範囲は、特許請求の範囲における所定の範囲の一例である。
【００９５】
また、メモリコントローラ３００は、チェン探索において、１クロックで１つの位置について誤り位置の探索を行っているが、第５の変形例において後述するように１クロックで複数のシンボル位置を探索してもよい。
【００９６】
また、メモリコントローラ３００は、誤り値を生成する構成としているが、２元ＢＣＨ符号をＥＣＣとして用いる場合には、誤り値を生成する必要はない。２元ＢＣＨ符号においては、１ビットのデータがシンボルとして用いられるためである。この２元ＢＣＨ符号を用いる場合には、復号部３２０は、誤り値生成部３２３を備えず、誤り訂正部３２４は、検出された誤り位置のシンボル（ビット）を反転することにより誤り訂正を行う。
【００９７】
また、メモリコントローラ３００は、未検出数Ｎｅｈが２以下になったときに、公式を用いる数式処理に切り替えているが、この構成に限定されない。３つ以上の誤り位置と係数との関係を示す公式が存在するのであれば、メモリコントローラ３００は、未検出数Ｎｅｈが３以下になったときに、その公式を用いる数式処理に切り替えてもよい。
【００９８】
［誤り位置検出部の構成例］
図７は、第１の実施の形態における誤り位置検出部３３０の一構成例を示すブロック図である。この誤り位置検出部３３０は、逐次探索処理部３４０および数式処理部３６０を備える。
【００９９】
逐次探索処理部３４０は、チェン探索法を使用して、Ｎ個のシンボルのそれぞれについて順に、その位置が誤り位置であるか否かを探索するものである。逐次探索処理部３４０は、ＯＲゲート３４１、初期化部３４２、誤り位置保持部３４３、誤り位置選択部３４４および切替判定部３４５を備える。また、逐次探索処理部３４０は、訂正不可判定部３４６、検出数カウンタ３４７、誤り位置多項式更新部３４８、逐次誤り位置検出部３４９、誤り位置多項式保持部３５０、シンボル位置カウンタ３５１および誤り位置多項式生成部３５２を備える。
【０１００】
誤り位置多項式生成部３５２は、誤り位置多項式を生成するものである。この誤り位置多項式生成部３５２は、ユークリッドアルゴリズムなどを使用して、式１１に例示した誤り位置多項式Ｐ（ｘ）を生成するとともに、誤り数Ｎｅを求める。誤り位置多項式生成部３５２は、誤り数Ｎｅを、逐次誤り位置検出部３４９、切替判定部３４５および数式処理部３６０に供給する。
【０１０１】
また、誤り位置多項式生成部３５２は、誤り位置多項式Ｐ（ｘ）における各項の係数を誤り位置多項式保持部３５０に供給して保持させる。また、誤り数Ｎｅが３以上である場合には、誤り位置多項式生成部３５２は、チェン探索の開始を指示する開始フラグを生成して、シンボル位置カウンタ３５１、検出数カウンタ３４７および初期化部３４２に供給する。
【０１０２】
誤り位置多項式保持部３５０は、誤り位置多項式Ｐ（ｘ）における各項の係数を保持するものである。なお、誤り位置多項式保持部３５０は、特許請求の範囲に記載の変数保持部の一例である。
【０１０３】
シンボル位置カウンタ３５１は、誤りの有無を判定する対象のシンボル位置を計数するものである。このシンボル位置カウンタ３５１は、例えば、開始フラグが供給されると、シンボル位置ｉを初期値（例えば、「０」）にする。そして、訂正不可フラグの値が「０」である場合には、シンボル位置カウンタ３５１は、所定のクロック信号に同期してシンボル位置ｉを「１」増分する。一方、訂正不可フラグの値が「１」である場合には、シンボル位置カウンタ３５１は、カウント動作を停止する。シンボル位置カウンタ３５１は、訂正不可判定部３４６、誤り位置選択部３４４、切替判定部３４５、誤り位置多項式更新部３４８および逐次誤り位置検出部３４９にシンボル位置ｉを供給する。
【０１０４】
シンボル位置カウンタ３５１がシンボル位置をカウントアップするたびに、誤りがあるか否かの判定における判定対象のシンボルが一定の順序で変更される。シンボル位置カウンタ３５１は、特許請求の範囲に記載の判定対象変更部の一例である。
【０１０５】
逐次誤り位置検出部３４９は、シンボル位置カウンタ３５１から供給されたシンボル位置ｉのシンボルにおける誤りの有無を検出するものである。この逐次誤り位置検出部３４９は、切替フラグを参照する。
【０１０６】
ここで、切替フラグは、チェン探索処理から、数式処理へ切り替えるか否かを示すフラグである。数式処理へ切り替える場合には、例えば、切替フラグに「１」の値が設定され、そうでない場合には「０」の値が設定される。初期状態においては、切替フラグに「０」の値が設定される。
【０１０７】
切替フラグが「０」の値である場合には、逐次誤り位置検出部３４９は、誤り位置多項式保持部３５０から誤り位置多項式Ｐ（ｘ）における各項の係数を取得する。そして、逐次誤り位置検出部３４９は、それらの係数から得られる誤り位置多項式Ｐ（ｘ）に、シンボル位置ｉに対応する根の候補Ａ−ｉを代入して、Ｐ（Ａ−ｉ）がゼロになるか否かを判定する。Ｐ（Ａ−ｉ）がゼロである場合には、シンボル位置ｉは、誤り位置である。
【０１０８】
逐次誤り位置検出部３４９は、シンボル位置ｉが誤り位置であるか否かを示す位置検出フラグを生成して、検出数カウンタ３４７、誤り位置多項式更新部３４８、および、誤り位置選択部３４４に供給する。例えば、シンボル位置ｉが誤り位置である場合には位置検出フラグに「１」の値が設定され、そうでない場合には「０」の値が設定される。なお、逐次誤り位置検出部３４９は、特許請求の範囲に記載の誤り位置検出部の一例である。
【０１０９】
検出数カウンタ３４７は、誤り位置の検出数を計数するものである。この検出数カウンタ３４７は、開始フラグが供給されると、検出数ｂを初期値（例えば、「０」）にする。そして、位置検出フラグが「１」の値である場合には、検出数カウンタ３４７は、所定のクロック信号に同期して検出数を「１」増分する。一方、位置検出フラグが「０」の値である場合には、検出数カウンタ３４７は、カウント動作を停止する。検出数カウンタ３４７は、検出数ｂを切替判定部３４５および訂正不可判定部３４６に供給する。
【０１１０】
誤り位置多項式更新部３４８は、誤り位置多項式Ｐ（ｘ）を更新するものである。この誤り位置多項式更新部３４８は、位置検出フラグが「１」である場合には、誤り位置多項式保持部３５０から誤り位置多項式Ｐ（ｘ）における各項の係数を取得する。そして、誤り位置多項式更新部３４８は、位置検出フラグが「１」のときのシンボル位置ｉを誤り位置ｉａとして、各係数から得られる誤り位置多項式Ｐ（ｘ）を｛ｘ−Ａ＾（−ｉａ）｝により割った式により更新する。誤り位置多項式更新部３４８は、更新後の誤り位置多項式Ｐ（ｘ）の各係数を誤り位置多項式保持部３５０に保持させる。
【０１１１】
なお、誤り位置多項式更新部３４８は、特許請求の範囲に記載の変数更新部の一例である。
【０１１２】
切替判定部３４５は、数式処理へ切り替えるか否かを判定するものである。この切替判定部３４５は、未検出数Ｎｅｈ、すなわち（Ｎｅ−ｂ）が２より大きく、または、シンボル位置ｉが閾値ｉｔｈ以上であるか否かを判断する。未検出数Ｎｅｈが２以下である場合、かつ、シンボル位置ｉが閾値ｉｔｈ未満である場合には、切替判定部３４５は、切替フラグを「１」に設定して切替を指示し、そうでない場合には「０」に設定する。切替判定部３４５は、その切替フラグを逐次誤り位置検出部３４９、誤り位置選択部３４４および数式処理部３６０に供給する。
【０１１３】
訂正不可判定部３４６は、受信語の誤りを訂正することができるか否かを判定するものである。この訂正不可判定部３４６は、次の不等式を使用して、誤りを訂正することができるか否かを判断する。
（ｎ−１）−ｉ＜Ｎｅ−ｂ                                      ・・・式２３
【０１１４】
上式において、右辺は、未検出の誤り位置の個数Ｎｅｈを示す。左辺は、未検出のシンボル数を示す。つまり、上式が成立する場合には、未検出のシンボル数が未検出の誤り位置の個数Ｎｅｈより少ないことを示す。この場合には、仮に、逐次誤り位置検出部３４９が、未検出の全てのシンボルについて誤りの有無を検出しても、誤り位置が全て検出されない。したがって、メモリコントローラ３００は、誤りを訂正することができない。
【０１１５】
このため、未検出のシンボル数が未検出の誤り位置の個数Ｎｅｈより少ない（すなわち、訂正不可である）場合には、訂正不可判定部３４６は、「１」の値を訂正不可フラグに設定し、そうでない場合には「０」の値を設定する。訂正不可判定部３４６は、訂正不可フラグをＯＲゲート３４１およびシンボル位置カウンタ３５１に供給する。
【０１１６】
数式処理部３６０は、上述の公式（式１３、式１４、または、式１７乃至式２１）を使用して、未検出の誤り位置を検出するものである。この数式処理部３６０は、切替フラグの値が「１」である場合には、公式を使用して誤り位置を検出する。そして、数式処理部３６０は、「１」に設定した位置検出フラグと、誤りのあるシンボル位置ｉとを誤り位置選択部３４４へ供給する。また、数式処理部３６０は、公式により誤り位置を検出することができたか否かに基づいて訂正不可フラグを生成してＯＲゲート３４１に供給する。なお、数式処理部３６０は、特許請求の範囲に記載の未検出位置検出部の一例である。
【０１１７】
誤り位置選択部３４４は、逐次誤り位置検出部３４９からの誤り位置と、数式処理部３６０からの誤り位置とのいずれかを選択して供給するものである。この誤り位置選択部３４４は、切替フラグが「０」の値である場合には、逐次誤り位置検出部３４９からの位置検出フラグが「１」のときの、シンボル位置カウンタ３５１からのシンボル位置ｉを誤り位置ｉａとして選択する。一方、切替フラグが「０」の値である場合には、誤り位置選択部３４４は、数式処理部３６０からの位置検出フラグが「１」のときの、数式処理部３６０からのシンボル位置ｉを誤り位置ｉａとして選択する。誤り位置選択部３４４は、選択した誤り位置ｉａを誤り位置保持部３４３に供給して保持させる。また、誤り位置選択部３４４は、シンボル位置ｉが最後の位置（ｎ−１）である場合、または、数式処理部３６０から全ての誤り位置を受け取った場合には、誤り位置検出の終了を示す終了フラグを生成して誤り位置保持部３４３に供給する。
【０１１８】
誤り位置保持部３４３は、誤り位置を保持するものである。誤り位置保持部３４３は、終了フラグが供給されると、保持している誤り位置ｉａのそれぞれを誤り値生成部３２３および誤り訂正部３２４へ供給する。
【０１１９】
初期化部３４２は、誤り位置保持部３４３を初期化するものである。この初期化部３４２は、開始フラグが供給されると、誤り位置保持部３４３に保持された誤り位置ｉａを消去するなどの初期化処理を行う。
【０１２０】
ＯＲゲート３４１は、入力値の論理和を供給するものである。ＯＲゲート３４１には、訂正不可判定部３４６からの訂正不可フラグと、数式処理部３６０からの訂正不可フラグとが入力される。ＯＲゲートは、これらの訂正不可フラグの値の論理和を誤り値生成部３２３へ供給する。
【０１２１】
［数式処理部の構成例］
図８は、第１の実施の形態における数式処理部３６０の一構成例を示すブロック図である。この数式処理部３６０は、誤り位置出力部３６１、二重誤り位置検出部３６２、トレース計算部３６３、および、単一誤り位置検出部３６４を備える。
【０１２２】
単一誤り位置検出部３６４は、誤り数Ｎｅが「１」である場合に誤り位置を検出するものである。この単一誤り位置検出部３６４は、逐次探索処理部３４０から誤り数Ｎｅを取得し、その値が「１」であるか否かを判断する。誤り数Ｎｅが「１」である場合には、単一誤り位置検出部３６４は、誤り位置多項式Ｐ（ｘ）の各項の係数を逐次探索処理部３４０から取得し、式１３または式１４を使用して誤り位置を求める。単一誤り位置検出部３６４は、求めた誤り位置を誤り位置出力部３６１に供給する。
【０１２３】
トレース計算部３６３は、トレースを計算し、誤りを訂正することができるか否かを判定するものである。このトレース計算部３６３は、「１」の切替フラグが供給されると、逐次探索処理部３４０から誤り数Ｎｅが「１」であるか否かを判断する。誤り数Ｎｅが「１」でない場合には、トレース計算部３６３は、式１７からＢを求め、式１９を使用してＴｒ（Ｂ）がゼロであるか否かを判断する。Ｔｒ（Ｂ）がゼロでない場合、すなわち誤り位置多項式Ｐ（ｘ）の根が存在しない場合には、トレース計算部３６３は、訂正不可フラグに「１」を設定し、そうでない場合には「０」を設定する。
【０１２４】
そして、トレース計算部３６３は、訂正不可フラグを二重誤り位置検出部３６２および逐次探索処理部３４０に供給し、ＢおよびＴｒ（Ｂ）を二重誤り位置検出部３６２に供給する。
【０１２５】
二重誤り位置検出部３６２は、ヒルベルトの定理に基づいて、２つの誤り位置を検出するものである。この二重誤り位置検出部３６２は、「０」の訂正不可フラグが供給されると、式２０および式２１を使用して、２つの誤り位置を求めて、誤り位置出力部３６１に供給する。
【０１２６】
誤り位置出力部３６１は、二重誤り位置検出部３６２および単一誤り位置検出部３６４のいずれかにより検出された誤り位置を逐次探索処理部３４０へ出力するものである。この誤り位置出力部３６１は、二重誤り位置検出部３６２および単一誤り位置検出部３６４のいずれかから誤り位置が供給されると、「１」の位置検出フラグを生成して、その誤り位置とともに逐次探索処理部３４０に供給する。
【０１２７】
［メモリコントローラの動作例］
図９は、第１の実施の形態におけるメモリコントローラ３００の動作の一例を示すフローチャートである。この動作は、例えば、メモリコントローラ３００に電源が投入されたときに開始する。
【０１２８】
メモリコントローラ３００は、ホストコンピュータ１００からライトコマンドを受信したか否かを判断する（ステップＳ９０１）。ライトコマンドを受信した場合には（ステップＳ９０１：Ｙｅｓ）、メモリコントローラ３００は、ライトデータの符号化と、符号化したライトデータの不揮発性メモリ４００への書込みとを行う（ステップＳ９０２）。
【０１２９】
ライトコマンドを受信していない場合（ステップＳ９０１：Ｎｏ）、または、ステップＳ９０２の後、メモリコントローラ３００は、ホストコンピュータ１００からリードコマンドを受信したか否かを判断する（ステップＳ９０３）。リードコマンドを受信した場合には（ステップＳ９０３：Ｙｅｓ）、メモリコントローラ３００は、リードデータにおいて誤りの検出および訂正を行うリード処理を実行する（ステップＳ９１０）。リードコマンドを受信していない場合には（ステップＳ９０３：Ｎｏ）、または、ステップＳ９１０の後、メモリコントローラ３００は、ステップＳ９０１に戻る。
【０１３０】
図１０は、第１の実施の形態におけるリード処理の一例を示すフローチャートである。メモリコントローラ３００は、受信語からシンドロームを生成し（ステップＳ９１１）、そのシンドロームに基づいて受信語に誤りがあるか否かを判断する（ステップＳ９１２）。
【０１３１】
受信語に誤りがある場合には（ステップＳ９１２：Ｙｅｓ）、メモリコントローラ３００は、誤り位置を検出するための誤り位置検出処理を実行する（ステップＳ９２０）。そして、メモリコントローラ３００は、訂正不可フラグが「１」の値（オン）であるか否かを判断する（ステップＳ９１３）。
【０１３２】
訂正不可フラグがオフである場合には（ステップＳ９１３：Ｎｏ）、メモリコントローラ３００は、誤り値を生成し（ステップＳ９１４）、誤り値に基づいて、誤り位置における誤りを訂正する（ステップＳ９１６）。
【０１３３】
一方、訂正不可フラグがオンである場合には（ステップＳ９１３：Ｙｅｓ）、メモリコントローラ３００は、ＥＣＣエラーをホストコンピュータ１００に通知する（ステップＳ９１５）。
【０１３４】
受信語に誤りがない場合（ステップＳ９１２：Ｎｏ）、または、ステップＳ９１６の後、メモリコントローラ３００は、受信語からパリティを除いた元データをホストコンピュータ１００に転送する（ステップＳ９１７）。ステップＳ９１５またはステップＳ９１７の後、メモリコントローラ３００はリード処理を終了する。なお、ステップＳ９１７において、メモリコントローラ３００は、パリティを削除せずに、受信語を出力してもよい。
【０１３５】
図１１は、第１の実施の形態における誤り位置検出処理の一例を示すフローチャートである。メモリコントローラ３００は、シンボル位置ｉおよび検出数ｂを初期値「０」に初期化し、誤り位置多項式Ｐ（ｘ）を生成する。また、メモリコントローラ３００は、この誤り位置多項式Ｐ（ｘ）の次数を誤り数Ｎｅとして取得する（ステップＳ９２１）。そして、メモリコントローラ３００は、未検出の誤り位置の個数（Ｎｅ−ｂ）が、２以下であるか否かを判断する（ステップＳ９２２）。
【０１３６】
（Ｎｅ―ｂ）が３以上である場合には（ステップＳ９２２：Ｎｏ）、メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）にＡ-ｉを代入して、ｉ番目のシンボルに誤りがあるか否かを判断する（ステップＳ９２３）。
【０１３７】
ｉ番目のシンボルに誤りがある場合には（ステップＳ９２３：Ｙｅｓ）、メモリコントローラ３００は、そのｉを誤り位置として保持し（ステップＳ９２４）、検出数ｂをインクリメントする（ステップＳ９２５）。また、メモリコントローラ３００は、誤り位置に基づいて誤り位置多項式Ｐ（ｘ）の次数を低減する（ステップＳ９２６）。
【０１３８】
ｉ番目のシンボルに誤りがない場合（ステップＳ９２３：Ｎｏ）、または、ステップＳ９２６の後、メモリコントローラ３００は、式２２が成立するか否かにより、誤りが訂正不可能であるか否かを判断する（ステップＳ９２７）。
【０１３９】
誤りを訂正することができる場合には（ステップＳ９２７：Ｎｏ）、メモリコントローラ３００は、シンボル位置ｉをインクリメントし（ステップＳ９２８）、ステップＳ９２２に戻る。
【０１４０】
訂正不可である場合には（ステップＳ９２７：Ｙｅｓ）、メモリコントローラ３００は、訂正不可フラグをオンにする（ステップＳ９３１）。また、（Ｎｅ−ｂ）が２以下である場合には（ステップＳ９２２：Ｙｅｓ）、メモリコントローラ３００は、未検出の誤り位置を検出する数式処理を実行する（ステップＳ９４０）。
【０１４１】
シンボル位置ｉが符号長ｎである場合には（ステップＳ９２９：Ｙｅｓ）、または、ステップＳ９３１の後、もしくはステップＳ９４０の後、メモリコントローラ３００は、誤り位置検出処理を終了する。
【０１４２】
図１２は、第１の実施の形態における数式処理の一例を示すフローチャートである。メモリコントローラ３００は、単一誤りが発生した（すなわち、Ｎｅ＝１である）か否かを判断する（ステップＳ９４１）。単一誤りが発生していない場合には（ステップＳ９４１：Ｎｏ）、メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）に重根がある（すなわち、訂正不可である）か否かを判断する（ステップＳ９４２）。
【０１４３】
重根がない場合には（ステップＳ９４２：Ｎｏ）、メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）の係数から、式１７を使用してＢを算出する（ステップＳ９４３）。また、メモリコントローラ３００は、トレースＴｒを生成し（ステップＳ９４４）、Ｔｒ（Ｂ）がゼロである（すなわち、訂正可能である）か否かを判断する（ステップＳ９４５）。
【０１４４】
Ｔｒ（Ｂ）がゼロである場合には（ステップＳ９４５：Ｙｅｓ）、メモリコントローラ３００は、式２０および式２１を使用して２つの根から誤り位置を算出する（ステップＳ９４６）。
【０１４５】
単一誤りが発生した場合には（ステップＳ９４１：Ｙｅｓ）、メモリコントローラ３００は、式１３、式１４に例示したように、Ｐ（ｘ）の係数の比から誤り位置を検出する（ステップＳ９４７）。重根がある場合（ステップＳ９４２：Ｙｅｓ）、または、Ｔｒ（Ｂ）がゼロでない場合（ステップＳ９４５：Ｎｏ）、メモリコントローラ３００は、訂正不可フラグをオンにする（ステップＳ９４８）。ステップＳ９４６、Ｓ９４７またはＳ９４８の後、メモリコントローラ３００は、数式処理を終了する。
【０１４６】
このように、本技術の第１の実施の形態によれば、復号部３２０は、チェン探索において所定の条件が満たされた場合には誤り位置と変数との関係を示す公式に基づいて誤り位置を検出するため、公式により高速に誤り位置を検出することができる。これにより、復号部３２０は、誤り訂正を高速に行うことができる。
【０１４７】
［第１の変形例］
第１の実施の形態では、メモリコントローラ３００は、誤り位置を検出するたびに誤り位置多項式Ｐ（ｘ）の次数を低減していたが、この処理を行わない構成とすることもできる。誤り位置多項式の次数を低減しない場合には、メモリコントローラ３００は、数式処理への切り替え後に、次数を低減した誤り位置多項式Ｐ（ｘ）を生成する必要がある。第１の変形例のメモリコントローラ３００は、数式処理への切り替え後に、次数を低減した誤り位置多項式Ｐ（ｘ）を生成する点において第１の実施の形態と異なる。
【０１４８】
［誤り位置検出部の構成例］
図１３は、第１の変形例における誤り位置検出部３３０の一構成例を示すブロック図である。第１の変形例の誤り位置検出部３３０は、誤り位置多項式更新部３４８を備えない点において第１の実施の形態と異なる。
【０１４９】
図１４は、第１の変形例における数式処理部３６０の一構成例を示すブロック図である。第１の変形例の数式処理部３６０は、誤り位置多項式再生成部３６５をさらに備える点において第１の実施の形態と異なる。
【０１５０】
誤り位置多項式再生成部３６５は、数式処理に切り替えられたときに、次数を低減した誤り位置多項式Ｐ（ｘ）を生成するものである。この誤り位置多項式再生成部３６５は、切替フラグが「１」の値である場合には、既に検出された誤り位置ｉａのそれぞれを誤り位置保持部３４３から取得し、誤り位置多項式Ｐ（ｘ）における係数を誤り位置多項式保持部３５０から取得する。また、誤り位置多項式再生成部３６５は、シンドロームｓを誤り検出部３２１から取得する。
【０１５１】
誤り位置ｉａが１つも検出されていない場合には、誤り数Ｎｅは「１」である。この場合、誤り位置多項式再生成部３６５は、シンドロームｓから、次数が「１」の誤り位置多項式を生成する。
【０１５２】
一方、誤り位置ｉａが１つ以上である場合には、誤り数Ｎｅは「２」である。この場合、誤り位置多項式再生成部３６５は、誤り位置ｉａのそれぞれについて、誤り位置多項式Ｐ（ｘ）を｛ｘ−Ａ＾（−ｉａ）｝により割ることにより、次数が「２」の誤り位置多項式Ｐ（ｘ）を生成する。
【０１５３】
誤り位置多項式再生成部３６５は、生成した誤り位置多項式Ｐ（ｘ）の各項の係数をトレース計算部３６３および単一誤り位置検出部３６４に供給する。
【０１５４】
このように、第１の変形例によれば、切り替え後に数式処理部３６０が誤り位置多項式の更新を行うため、切り替え前のチェン探索において逐次探索処理部３４０が誤り位置多項式の更新を行う必要がなくなる。このため、誤り位置多項式の更新を行う回路やプログラムが不要となり、簡易な構成により逐次探索処理部３４０を実現することができる。
【０１５５】
［第２の変形例］
第１の実施の形態では、メモリコントローラ３００は、検出数ｂが誤り数Ｎｅになったか否かを判断していなかったが、その判断を行って検出数ｂが誤り数Ｎｅになったときに誤り位置検出処理を終了してもよい。第２の変形例の誤り位置検出部３３０は、検出数ｂが誤り数Ｎｅになったか否かを判断する点において第１の実施の形態と異なる。
【０１５６】
図１５は、第２の変形例における誤り位置検出処理の一例を示すフローチャートである。第２の変形例の誤り位置検出処理は、ステップＳ９７１およびＳ９７２をさらに実行する点において第１の実施の形態と異なる。
【０１５７】
メモリコントローラ３００は、検出数ｂをインクリメントし（ステップＳ９２５）、検出数ｂが誤り数Ｎｅであるか否かを判断する（ステップＳ９７１）。検出数ｂが誤り数Ｎｅである場合には（ステップＳ９７１：Ｙｅｓ）、メモリコントローラ３００は、誤り位置検出処理を終了する。一方、検出数ｂが誤り数Ｎｅでない場合には（ステップＳ９７１：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２６を実行する。そして、メモリコントローラ３００は、ステップＳ９２８の後、シンボル位置ｉが、閾値ｉｔｈ以上であるか否かを判断する（ステップＳ９７２）。ここで、閾値ｉｔｈには、ｉｔｈ以降のシンボルについてチェン探索処理を継続した方が、数式処理に切り替えるよりも誤り位置検出処理が早く終了する値が設定される。シンボル位置ｉが、閾値ｉｔｈ以上である場合には（ステップＳ９７２：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９２３に戻る。一方、シンボル位置ｉが、閾値ｉｔｈ未満である場合には（ステップＳ９７２：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。
【０１５８】
なお、メモリコントローラ３００がステップＳ９７１を実行しない構成としてもよい。この構成では、メモリコントローラ３００は、シンボル位置ｉが閾値ｉｔｈ以上である場合に（ステップＳ９７２：Ｙｅｓ）、ｉがｎであるか否かを判断するステップを実行すればよい。そして、ｉがｎであれば、メモリコントローラ３００は、誤り位置検出処理を終了し、そうでない場合にはステップＳ９２３に戻る。
【０１５９】
このように、第２の変形例によれば、誤り位置が全て検出されると、誤り位置検出処理を終了するため、誤り位置検出処理に要する時間をさらに短くすることができる。
【０１６０】
［第３の変形例］
第１の実施の形態では、メモリコントローラ３００は、誤り位置を検出するたびに誤り位置多項式の次数を低減していたが、所定の位置以降において誤り位置を検出しても、次数を低減しない構成としてもよい。第３の変形例の誤り位置検出部３３０は、所定の位置以降において誤り位置を検出しても、次数を低減しない点において第１の実施の形態と異なる。
【０１６１】
図１６は、第３の変形例における誤り位置検出処理の一例を示すフローチャートである。第３の変形例の誤り位置検出処理は、ステップＳ９７２乃至Ｓ９７８をさらに実行する点において第１の実施の形態と異なる。
【０１６２】
メモリコントローラ３００は、シンボル位置ｉをインクリメントする処理（ステップＳ９２８）の後、シンボル位置ｉが、閾値ｉｔｈ以上であるか否かを判断する（ステップＳ９７２）。ここで、閾値ｉｔｈには、ｉｔｈ以降のシンボルについてチェン探索処理を継続した方が、数式処理に切り替えるよりも誤り位置検出処理が早く終了する値が設定される。シンボル位置ｉが、閾値ｉｔｈ未満である場合（ステップＳ９７２：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。シンボル位置ｉが、閾値ｉｔｈ以上である場合に（ステップＳ９７２：Ｙｅｓ）、メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）にＡ-ｉを代入して、ｉ番目のシンボルに誤りがあるか否かを判断する（ステップＳ９７３）。ここで、閾値ｉｔｈ未満の範囲は、特許請求の範囲に記載の所定の範囲の一例である。
【０１６３】
ｉ番目のシンボルに誤りがある場合には（ステップＳ９７３：Ｙｅｓ）、メモリコントローラ３００は、そのｉを誤り位置として保持し（ステップＳ９７４）、検出数ｂをインクリメントする（ステップＳ９７５）。ここで、誤り位置多項式の次数の低減は行われない。そして、メモリコントローラ３００は、検出数ｂがＮｅであるか否かを判断する（ステップＳ９７６）。検出数ｂがＮｅである場合（ステップＳ９７６：Ｙｅｓ）、メモリコントローラ３００は、誤り位置検出処理を終了する。ステップＳ９７６を実行することにより、第２の変形例と同様の効果が得られる。
【０１６４】
ｉ番目のシンボルに誤りがない場合（ステップＳ９７３：Ｎｏ）、または、検出数ｂがＮｅでない場合（ステップＳ９７６：Ｎｏ）、メモリコントローラ３００は、式２３が成立するか否かにより、誤りが訂正不可能であるか否かを判断する（ステップＳ９７７）。
【０１６５】
誤りを訂正することができる場合には（ステップＳ９７７：Ｎｏ）、メモリコントローラ３００は、シンボル位置ｉをインクリメントし（ステップＳ９７８）、ステップＳ９７３に戻る。一方、誤りを訂正することができない場合には（ステップＳ９７７：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９３１を実行する。
【０１６６】
なお、メモリコントローラ３００がステップＳ９７６を実行しない構成としてもよい。この構成では、メモリコントローラ３００は、ステップＳ９７８の後に、ｉがｎであるか否かを判断するステップを実行すればよい。そして、ｉがｎであれば、メモリコントローラ３００は、誤り位置検出処理を終了し、そうでない場合にはステップＳ９７３に戻る。
【０１６７】
このように、変形例によれば、シンボル位置ｉが閾値ｉｔｈ以上であるときに、誤り位置を検出しても誤り位置多項式の次数を低減する処理を行わないため、閾値ｉｔｈ以降において、誤り位置の探索を高速に行うことができる。
【０１６８】
［第４の変形例］
第１の実施の形態では、メモリコントローラ３００は、次数を低減した後に未検出の誤り数が１つであるか否かを判断していなかった。しかし、未検出の誤り数が１つのときには、誤り位置多項式は１次式になっており、公式によって高速に誤り位置を求めることができる。第４の変形例のメモリコントローラ３００は、次数を低減した後に未検出の誤り数が１つであれば、公式を使用して誤り位置を求める点において第１の実施の形態と異なる。
【０１６９】
図１７は、第４の変形例における誤り位置検出処理の一例を示すフローチャートである。第４の変形例の誤り位置検出処理は、ステップＳ９７２、Ｓ９７９乃至Ｓ９８１をさらに実行する点において第１の実施の形態と異なる。メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）の次数を低減する処理（ステップＳ９２６）の後に、検出数ｂがＮｅ−１であるか否かを判断する（ステップＳ９７９）。ｂがＮｅ−1であるときは、残りの誤りの個数が１つであり、公式により誤り位置を高速に検出することができる。
【０１７０】
検出数ｂがＮｅ−１でない場合には（ステップＳ９７９：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２７およびＳ９２８の処理を行う。また、メモリコントローラ３００は、ステップＳ９２８の後、シンボル位置ｉが、閾値ｉｔｈ以上であるか否かを判断する（ステップＳ９７２）。ここで、閾値ｉｔｈには、ｉｔｈ以降のシンボルについてチェン探索処理を継続した方が、数式処理に切り替えるよりも誤り位置検出処理が早く終了する値が設定される。シンボル位置ｉが、閾値ｉｔｈ以上である場合（ステップＳ９７２：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９２３に戻る。一方、シンボル位置ｉが、閾値ｉｔｈ未満である場合には（ステップＳ９７２：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。また、検出数ｂがＮｅ−１である場合には（ステップＳ９７９：Ｙｅｓ）、メモリコントローラ３００は、次数を低減後の誤り位置多項式Ｐ（ｘ）から、公式を使用して誤り位置を算出し、その位置を保持する（ステップＳ９８０）。
【０１７１】
メモリコントローラ３００は、最後にステップＳ９８０で求めた誤り位置がｉ＋１乃至ｎ−１の範囲内の位置であるか否かを判断する（ステップＳ９８１）。最後の誤り位置がｉ＋１乃至ｎ−１の範囲内の位置でない場合（ステップＳ９８１：Ｎｏ）、メモリコントローラ３００は、訂正不可フラグをオンにする（ステップＳ９３１）。一方、最後の誤り位置がｉ＋１乃至ｎ−１の範囲内の位置である場合（ステップＳ９８１：Ｙｅｓ）、メモリコントローラ３００は、誤り位置検出処理を終了する。上述のステップＳ９８０、Ｓ９８１およびＳ９３１は、例えば、単一誤り位置検出部３６４により実行される。
【０１７２】
このように、第４の変形例によれば、次数を低減した後に未検出の誤り数が１つであれば、公式を使用して誤り位置を求めるため、高速に誤り位置を検出することができる。
【０１７３】
［第５の変形例］
第１の実施の形態では、メモリコントローラ３００は、チェン探索においてクロックごとに１つの位置について誤り位置の探索を行っているが、クロックごとに複数のシンボル位置を探索してもよい。第５の変形例のメモリコントローラ３００は、クロックごとに複数のシンボル位置を探索する点において第１の実施の形態と異なる。
【０１７４】
図１８は、第５の変形例における誤り位置検出処理の一例を示すフローチャートである。第５の変形例の誤り位置検出処理は、ステップＳ９２１、Ｓ９２３乃至Ｓ９２５、Ｓ９２７、Ｓ９２８の代わりに、ステップＳ９９１乃至Ｓ９９８を実行する点において第１の実施の形態と異なる。
【０１７５】
まず、メモリコントローラ３００は、シンボル位置ｉおよび検出数ｂを初期化し、誤り位置多項式Ｐ（ｘ）を生成し、誤り数Ｎｅを取得する。さらに、メモリコントローラ３００は、並列探索数ｐを設定する（ステップＳ９９１）。ここで、ｐは、１クロックにおいて誤り位置を探索するシンボル位置の個数であり、２以上の整数が設定される。メモリコントローラ３００は、未検出の誤り位置の個数（Ｎｅ−ｂ）が、２以下であるか否かを判断する（ステップＳ９２２）。
【０１７６】
（Ｎｅ―ｂ）が３以上である場合には（ステップＳ９２２：Ｎｏ）、メモリコントローラ３００は、ｉからｐ個目の値（ｉ＋ｐ−１）と、ｉの最大値（ｎ−１）とのうち小さい方をｉ_ｍａｘとする（ステップＳ９９２）。メモリコントローラ３００は、誤り位置多項式Ｐ（ｘ）を使用してｉ乃至ｉ_max番目のシンボルのいずれかに誤りがあるか否かを判断する（ステップＳ９９３）。
【０１７７】
ｉ乃至ｉ_max番目のシンボルのいずれかに誤りがある場合には（ステップＳ９９３：Ｙｅｓ）、メモリコントローラ３００は、その位置を誤り位置として保持し（ステップＳ９９４）、検出数ｂにｐ'を加算する（ステップＳ９９５）。ここで、ｐ'は、ステップＳ９９３において検出された誤りの個数である。そして、メモリコントローラ３００は、検出数ｂがＮｅであるか否かを判断する（ステップＳ９９６）。検出数ｂがＮｅである場合（ステップＳ９９６：Ｙｅｓ）、メモリコントローラ３００は、誤り位置検出処理を終了する。ステップＳ９９６により、１クロックで複数のシンボル位置を探索する場合において、ステップＳ９２２乃至Ｓ９９７のループから抜けられなくなることを回避することができる。一方、検出数ｂがＮｅでない場合（ステップＳ９９６：Ｎｏ）、メモリコントローラ３００は、誤り位置に基づいて誤り位置多項式Ｐ（ｘ）の次数を低減する（ステップＳ９２６）。
【０１７８】
ｉ乃至ｉ_max番目のシンボルに誤りがない場合（ステップＳ９９３：Ｎｏ）、または、ステップＳ９２６の後、メモリコントローラ３００は、ｉをｉ_maxに置き換えた式２３が成立するか否かにより、誤りが訂正不可能であるか否かを判断する（ステップＳ９９７）。
【０１７９】
誤りを訂正することができる場合には（ステップＳ９９７：Ｎｏ）、メモリコントローラ３００は、シンボル位置ｉにｐを加算し（ステップＳ９９８）、ステップＳ９２２に戻る。
【０１８０】
訂正不可である場合には（ステップＳ９９７：Ｙｅｓ）、メモリコントローラ３００は、訂正不可フラグをオンにする（ステップＳ９３１）。
【０１８１】
また、メモリコントローラ３００は、図１７に例示した第４の変形例を第５の変形例にさらに適用してもよい。この場合には、ステップＳ９２６の後に、ステップＳ９７９乃至Ｓ９８１を、ステップＳ９９８の後にステップＳ９７２をそれぞれ挿入すればよい。
【０１８２】
このように第５の変形例によれば、クロックごとに複数のシンボル位置を探索するため、より高速に誤り位置を検出することができる。
【０１８３】
［第６の変形例］
メモリコントローラ３００は、図１５に例示した第２の変形例を図１８に例示した第５の変形例にさらに適用してもよい。第６の変形例は、第５の変形例に第２の変形例をさらに適用したものである。
【０１８４】
図１９は、第６の変形例における誤り位置検出処理の一例を示すフローチャートである。第６の変形例においてメモリコントローラ３００はステップＳ９９８の後に、シンボル位置ｉが閾値ｉｔｈ以上であるか否かを判断するステップＳ９７２をさらに実行する。シンボル位置ｉが閾値ｉｔｈ以上である場合には（ステップＳ９７２：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９９２に戻る。一方、シンボル位置ｉが、閾値ｉｔｈ未満である場合には（ステップＳ９７２：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。ここで、第２の変形例では、ステップＳ９７２を追加したことによりステップＳ９２７の条件がＹｅｓとならずループを脱出できない可能性への対応のためステップＳ９７１の追加を行っていた。しかし、第６の変形例ではステップＳ９９３で複数の誤りが発見された結果、ｂ＝Ｎｅが成立した際にループを脱出するためのステップＳ９９６が既に存在する。このため、第６の変形例では、Ｓ９７１の追加に対応する新たなステップの追加は不要である。
【０１８５】
なお、第６の変形例においてメモリコントローラ３００は、ステップＳ９９６を実行しない構成としてもよい。この構成ではメモリコントローラ３００は、シンボル位置ｉが閾値ｉｔｈ以上である場合に（ステップＳ９７２：Ｙｅｓ）、ｉ≧ｎであるか否かを判断するステップを実行すればよい。そして、ｉ≧ｎであれば、メモリコントローラ３００は、誤り位置検出処理を終了し、そうでない場合にはステップＳ９９２に戻る。条件文がｉ＝ｎでなくｉ≧ｎとなるのは、ステップＳ９９８で並列探索数ｐを加算する処理を行っているためである。
【０１８６】
［第７の変形例］
メモリコントローラ３００は、図１６に例示した第３の変形例を図１８に例示した第５の変形例にさらに適用してもよい。第７の変形例は、第５の変形例に第３の変形例をさらに適用したものである。
【０１８７】
図２０は、第７の変形例における誤り位置検出処理の一例を示すフローチャートである。第７の変形例においてメモリコントローラ３００は、ステップＳ９９８の後に、シンボル位置ｉが閾値ｉｔｈ以上であるか否かを判断するステップＳ９７２をさらに実行する。シンボル位置ｉが閾値ｉｔｈ以上である場合に（ステップＳ９７２：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９９２乃至Ｓ９９８と同様のステップＳ９９２'乃至Ｓ９９８'を行い、ステップＳ９９８'の後、ステップＳ９９２'に戻る。一方、シンボル位置ｉが、閾値ｉｔｈ未満である場合には（ステップＳ９７２：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。
【０１８８】
なお、第７の変形例においてメモリコントローラ３００は、ステップＳ９９６'を実行しない構成としてもよい。この構成ではメモリコントローラ３００は、ステップＳ９９８'のあとにｉ≧ｎであるか否かを判断するステップを実行すればよい。そして、ｉ≧ｎであれば、メモリコントローラ３００は、誤り位置検出処理を終了し、そうでない場合にはステップＳ９９２'に戻る。
【０１８９】
＜２．第２の実施の形態＞
第１の実施の形態では、メモリコントローラ３００は、誤り位置を検出するたびに誤り位置多項式Ｐ（ｘ）を更新していたが、誤り位置を検出するたびにシンドロームｓを更新してもよい。シンドロームｓの更新により、更新した誤り位置多項式Ｐ（ｘ）と同様の多項式が得られるためである。第２の実施の形態のメモリコントローラ３００は、誤り位置を検出するたびにシンドロームｓを更新する点において第１の実施の形態と異なる。
【０１９０】
図２１は、第２の実施形態における誤り位置検出部３３０の一構成例を示すブロック図である。第２の実施の形態の誤り位置検出部３３０は、誤り位置多項式更新部３４８および誤り位置多項式保持部３５０の代わりに、シンドローム更新部３５３およびシンドローム保持部３５４を備える点において第１の実施の形態と異なる。
【０１９１】
シンドローム保持部３５４は、シンドロームｓを保持するものである。保持されたシンドロームｓは、誤り位置多項式の次数を低減させるために、誤り位置が検出されるたびにシンドローム更新部３５３により更新される。
【０１９２】
シンドローム更新部３５３は、誤り位置が検出されるたびにシンドロームｓの成分を削減するものである。ここで、図５のｂに例示した検査行列Ｈの各列のうちｉａ列のみで構成される部分検査行列ＨＮｅは、次の式により表される。
【数３】
2015106872.tif 000005
【０１９３】
この部分検査行列ＨＮｅにおけるｉａ列は、次の式により表される。
【数４】
2015106872.tif 000006
【０１９４】
同様に、ゼロ以外の値の成分のみで構成される部分誤りベクトルｅＮｅは、次の式により表される。
【数５】
2015106872.tif 000007
【０１９５】
式２４および式２６に例示した部分検査行列ＨＮｅおよび部分誤りベクトルｅＮｅを用いて、式２に例示したシンドロームｓは、次の式により表すことができる。
【数６】
2015106872.tif 000008
上式に例示するように、シンドロームｓは、誤り値とｉａ列との積和により表される。このため、誤り位置ｉａが検出されるたびに、シンドローム更新部３５３が誤り値とｉａ列との積をシンドロームｓから減じることにより、誤り位置多項式において次数が低減するシンドロームを生成することができる。
【０１９６】
具体的には、シンドローム更新部３５３は、誤り位置ｉａが検出されると、その位置に基づいて、式２７におけるパリティ検査行列のｉａ列を式２５から求める。また、シンドローム更新部３５３は、Ｆｏｒｎｅｙのアルゴリズムを使用して誤り値ｅｉを求める。そして、シンドローム更新部３５３は、更新対象のシンドロームをＳｕとして、次の式を使用して、シンドローム保持部３５４におけるシンドロームを更新する。
【数７】
2015106872.tif 000009
【０１９７】
上式に例示するように、シンドロームの更新処理は減算により行うことができ、割り算を行う必要のある誤り位置多項式の更新処理と比較して、簡易な処理である。このため、誤り位置検出部３３０を、第１の実施の形態よりも簡易な構成により実現することができる。
【０１９８】
第２の実施の形態の誤り位置多項式生成部３５２は、シンドローム保持部３５４からシンドロームｓを取得して誤り位置多項式Ｐ（ｘ）を生成し、その多項式における係数を逐次誤り位置検出部３４９および数式処理部３６０に供給する。
【０１９９】
未検出数Ｎｅｈが「１」である場合のシンドロームは、式２７の表記法に基づいて、次の式により表される。
【数８】
2015106872.tif 000010
【０２００】
上式に例示するように、誤り位置多項式の次数が「１」であるため、第２の実施の形態の数式処理部３６０は、第１の実施の形態と同様の公式を使用して誤り位置を求めることができる。一方、未検出数Ｎｅｈが「２」である場合には、シンドロームは、次の式により表される。
【数９】
2015106872.tif 000011
【０２０１】
ここで、上式は、次の式に変形することができる。
【数１０】
2015106872.tif 000012
【０２０２】
数式処理部３６０は、ピーターソンアルゴリズムにおいて、ｊが０乃至３のときのｓｕｊを用いることにより、誤り位置多項式Ｐｈ（ｘ）における各係数を求めることができる。具体的には、それらの係数は、次の各式により求められる。
Ｐｈ２＝｛（ｓｕ２）２−ｓｕ１ｓｕ３｝／｛（ｓｕ１）２−ｓｕ０ｓｕ２｝    ・・・式３２
Ｐｈ１＝（ｓｕ０ｓｕ３−ｓｕ１ｓｕ３）／｛（ｓｕ１）２−ｓｕ０ｓｕ２｝    ・・・式３３
Ｐｈ０＝１                                                     ・・・式３４
【０２０３】
図２２は、第２の実施の形態における誤り位置検出処理の一例を示すフローチャートである。第２の実施の形態の誤り位置検出処理は、ステップＳ９２６の代わりにステップＳ９３３を実行する点において第１の実施の形態と異なる。
【０２０４】
メモリコントローラ３００は、検出数ｂをインクリメントすると（ステップＳ９２５）、式２７を使用してシンドロームｓを更新する（ステップＳ９３３）。そして、メモリコントローラ３００は、訂正不可であるか否かを判定する（ステップＳ９２７）。
【０２０５】
なお、図２２に例示した誤り位置検出処理においても、第２乃至第７の変形例を適用することができる。具体的には、図１５乃至図２０に例示したフローチャートにおいて、ステップＳ９２６の代わりにステップＳ９３３を実行すればよい。
【０２０６】
このように、第２の実施の形態によれば、誤り位置を検出するたびにシンドロームを更新するため、簡易な構成により誤り位置を検出することができる。
【０２０７】
＜３．第３の実施の形態＞
第１の実施の形態では、メモリコントローラ３００は、誤り位置を検出するたびに誤り位置多項式Ｐ（ｘ）を更新していた。しかし、誤り位置を検出するたびに検出した誤り位置を根に持つ多項式Ｑ'（ｘ）を更新し、数式処理を行なう直前に一度だけ元の誤り位置多項式Ｐ（ｘ）をＱ'（ｘ）により除算してもよい。この除算により、第１の実施の形態において数式処理部３６０に入力していた誤り位置多項式Ｐ（ｘ）と同様の多項式が得られるためである。第３の実施の形態のメモリコントローラ３００は、誤り位置を検出するたびに検出した誤り位置を根に持つ多項式Ｑ'（ｘ）を更新し、数式処理を行なう直前に一度だけ元の誤り位置多項式Ｐ(ｘ)をＱ'（ｘ）により除算する点において第１の実施の形態と異なる。
【０２０８】
図２３は、第３の実施形態における誤り位置検出部３３０の一構成例を示すブロック図である。第３の実施の形態の誤り位置検出部３３０は、誤り位置多項式更新部３４８の代わりに、検出済み誤り位置多項式生成部３５５および除算部３６６を備える点において第１の実施の形態と異なる。
【０２０９】
検出済み誤り位置多項式生成部３５５は、誤り位置が検出されるたびに次のようにして検出済み誤り位置多項式Ｑ'（ｘ）を生成する。この検出済み誤り位置多項式生成部３５５は、誤り位置多項式Ｐ(ｘ)が生成されるタイミングでＱ'（ｘ）を初期値（例えば、「１」）に初期化し、誤り位置iが検出されるたびにＱ'（ｘ）を次の式を用いて更新する。なお、検出済み誤り位置多項式生成部３５５は、特許請求の範囲に記載の乗算部の一例である。
Ｑ'（ｘ）＝Ｑ'（ｘ）・（ｘ-αｉ)                              ・・・式３５
【０２１０】
除算部３６６は、切替判定部３４５から「１」の切替フラグが供給されると、検出済み誤り位置多項式生成部３５５で生成された検出済み誤り位置多項式Ｑ'（ｘ）を元の誤り位置多項式P(x)により割り切ることにより誤り位置多項式Ｒ'（ｘ）を生成する。具体的には、除算部３６６は、次の式により、Ｐ（ｘ）を割った商をＲ'（ｘ）として求める。
Ｒ'（ｘ）＝Ｐ（ｘ）／Ｑ'（ｘ）                            ・・・式３６
この式により、次数がＰ（ｘ）の次数以下であり、かつ、未検出の誤り位置をすべて根に持つ多項式Ｒ'（ｘ）が得られる。
【０２１１】
除算部３６６は、誤り位置多項式Ｐ（ｘ）の係数の代わりにＲ'（ｘ）の係数を数式処理部３６０に供給する。
【０２１２】
上述したように、検出済み誤り位置多項式Ｑ'（ｘ）の更新は乗算のみでよく、メモリコントローラ３００は、未検出数Ｎｅｈが一定数(例えば、「２」)以下になったときに式３６の除算によりＲ'（ｘ）を生成すればよい。このため、第１の実施の形態よりも除算の回数を減らすことができ、復号処理時間を短縮することができる。
【０２１３】
図２４は、第３の実施の形態における誤り位置検出処理の一例を示すフローチャートである。第３の実施の形態の誤り位置検出処理は、ステップＳ９２１およびＳ９２６の代わりにステップＳ９３４乃至ステップＳ９３６を実行する点において第１の実施の形態と異なる。
【０２１４】
初期化において、メモリコントローラ３００は、シンボル位置ｉなどの初期化の他、検出済誤り位置多項式Ｑ'（ｘ）の初期化をさらに行う（ステップＳ９３４）。また、メモリコントローラ３００は、検出数ｂをインクリメントすると（ステップＳ９２５）、式３５を使用して検出済み誤り位置多項式Ｑ'（ｘ）を更新する（ステップＳ９３５）。そして、メモリコントローラ３００は、訂正不可であるか否かを判定する（ステップＳ９２７）。メモリコントローラ３００は、未検出数Ｎｅｈが２以下になると(ステップＳ９２２：Ｙｅｓ)、式３６を使用してＲ'（ｘ）を求める(ステップＳ９３６)。そして、メモリコントローラ３００は、数式処理を実行する（ステップＳ９４０）。
【０２１５】
なお、図２４に例示した誤り位置検出処理において、第２、第３または第５の変形例をさらに適用することができる。具体的には、図１５、図１６または図１８に例示したフローチャートにおいて、ステップＳ９２１およびＳ９２６の代わりにステップＳ９３４およびＳ９３５を実行すればよい。また、未検出の誤り位置数が２以下となった場合に（ステップＳ９２２：Ｙｅｓ）、ステップＳ９３６を実行してからステップＳ９４０を実行すればよい。
【０２１６】
また、図２４に例示した誤り位置検出処理において、第４の変形例をさらに適用することができる。具体的には、図１７に例示したフローチャートにおいて、ステップＳ９２１およびＳ９２６の代わりにステップＳ９３４およびＳ９３５を実行すればよい。また、未検出の誤り位置数が２以下となった場合に（ステップＳ９２２：Ｙｅｓ）、ステップＳ９３６を実行してからステップＳ９４０を実行する。また、ｂ＝Ｎｅ―１である場合に（ステップＳ９７９：Ｙｅｓ）ステップＳ９３６を実行してからステップＳ９８０を実行すればよい。
【０２１７】
また、検出済み誤り位置多項式の更新を数式処理の直前に行なってもよい。具体的には、未検出の誤り位置数が２以下となった場合に（ステップＳ９２２：Ｙｅｓ）、ステップＳ９３５およびＳ９３６を実行し、Ｓ９４０を実行すればよい。
【０２１８】
また、Ｑ'（ｘ）の次数が一定数以上になったときに除算を実行してもよい。具体的には、ステップＳ９３５の後、メモリコントローラ３００は、Ｑ'（ｘ）の次数を確認し一定数以上であるか否かを判定する。Ｑ'（ｘ）の次数が一定数以上であればステップＳ９３６を実行し、その後に「Ｐ（ｘ）＝Ｒ'（ｘ）」のステップとステップS９２７とを実行する。一方、Ｑ'（ｘ）の次数が一定数未満であればメモリコントローラ３００は、ステップＳ９２７を実行する。
【０２１９】
このように、第３の実施の形態によれば、除算の回数が検出済み誤り位置多項式による除算が１回だけでよいため、復号処理時間を短縮することができる。
【０２２０】
＜４．第４の実施の形態＞
第１の実施の形態では、メモリコントローラ３００は、チェン探索中に、未検出の誤り位置の個数Ｎｅｈが２以下になったときに数式処理を開始していた。しかし、メモリコントローラ３００は、チェン探索を行う前とチェン探索中との両方において数式処理を行ってもよい。第４の実施の形態のメモリコントローラ３００は、チェン探索を行う前とチェン探索中とにおいて数式処理を行う点において第１の実施の形態と異なる。
【０２２１】
図２５は、第４の実施の形態における復号部３２０の一構成例を示すブロック図である。第３の実施形態の復号部３２０は、誤り選択部３２５および二重以下誤り判定部３７０をさらに備える点において第１の実施の形態と異なる。
【０２２２】
二重以下誤り判定部３７０は、二重誤りおよび単一誤りのいずれかが発生した否かを判定するものである。二重以下誤り判定部３７０は、二重誤りまたは単一誤りが生じた（言い換えれば誤り数Ｎｅが２以下である）ことを仮定して、数式処理を実行する。ここで、受信語に生じた実際の誤り数が３以上であると、仮定と矛盾するために、数式処理において二重以下誤り判定部３７０は誤り位置の検出に失敗する。このため、二重以下誤り判定部３７０は、誤り位置検出の成否から、誤り数Ｎｅが２以下であるか否かを判定することができる。
【０２２３】
二重以下誤り判定部３７０は、誤り位置検出の成否に基づいて、誤り数Ｎｅが２以下であるか否かを示す二重以下誤り判定フラグを生成して誤り選択部３２５および誤り位置検出部３３０に供給する。二重以下誤り判定フラグは、例えば、誤り数Ｎｅが２以下である場合に「１」の値に設定され、そうでない場合に「０」の値に設定される。
【０２２４】
また、二重以下誤り判定部３７０は、誤り数Ｎｅが２以下であった場合には、誤り値を生成し、誤り位置および誤り値を誤り選択部３２５へ供給する。なお、二重以下誤り判定部３７０は、特許請求の範囲に記載の誤り数判定部の一例である。
【０２２５】
誤り選択部３２５は、二重以下誤り判定フラグに基づいて、誤り位置および誤り値を選択するものである。この誤り選択部３２５は、二重以下誤り判定フラグが「１」の値（すなわち、誤り数Ｎｅが２以下）である場合には、二重以下誤り判定部３７０からの誤り位置および誤り値を選択する。一方、二重以下誤り判定フラグが「０」の値である場合に誤り選択部３２５は、誤り位置検出部３３０からの誤り位置と誤り値生成部３２３からの誤り値とを選択する。誤り選択部３２５は、選択した誤り位置および誤り値を誤り訂正部３２４へ供給する。
【０２２６】
第４の実施の形態の誤り位置検出部３３０は、第１の実施の形態と同様の構成である。ただし、第４の実施の形態の誤り位置検出部３３０は、二重判定フラグが「０」の値であると、誤り位置の検出を行う。そして誤り位置検出部３３０は、検出した誤り位置を誤り値生成部３２３および誤り選択部３２５へ供給する。第４の実施の形態の誤り値生成部３２３は、生成した誤り値を誤り選択部３２５へ供給する点以外は、第１の実施の形態と同様である。
【０２２７】
なお、復号部３２０は、二重以下誤り判定部３７０と誤り位置検出部３３０とが誤り検出を順に行う構成としているが、これらが並列に誤り検出を行う構成としてもよい。この場合、誤り位置検出部３３０は、検出しておいた誤り位置を二重判定フラグが「０」の値である場合に出力すればよい。
【０２２８】
［二重以下誤り判定部の構成例］
図２６は、第４の実施の形態における二重以下誤り判定部３７０の一構成例を示すブロック図である。この二重以下誤り判定部３７０は、ＯＲゲート３７１、二重以下誤り選択部３７２、単一誤り発生判定部３７３、単一誤り仮定誤り値生成部３７４および単一誤り仮定誤り位置検出部３７５を備える。また、二重以下誤り判定部３７０は、二重誤り発生判定部３７６、二重誤り仮定誤り値生成部３７７、二重誤り仮定誤り位置検出部３７８および二重誤り仮定誤り位置多項式生成部３７９を備える。
【０２２９】
単一誤り仮定誤り位置検出部３７５は、単一誤りが発生したと仮定して誤り位置を検出するものである。単一誤りが発生したときのシンドロームの成分ｓｊは、式２において誤り数Ｎｅを「１」に設定することにより得られる次の式により表される。
【数１１】
2015106872.tif 000013
【０２３０】
上式より、ｊ（ｊは０乃至２ｔ−１の整数）が、ｊ１およびｊ１＋１のそれぞれのときの成分ｓｊに基づいて、単一誤りの誤り位置は、次の式により求められる。
【数１２】
2015106872.tif 000014
上式において、左辺のべき指数ｉ１が誤り位置を示す。
【０２３１】
単一誤り仮定誤り位置検出部３７５は、式３８を使用して誤り位置を検出し、その誤り位置を二重以下誤り選択部３７２、単一誤り仮定誤り値生成部３７４および単一誤り発生判定部３７３に供給する。
【０２３２】
単一誤り仮定誤り値生成部３７４は、単一誤りが発生したと仮定して誤り値を生成するものである。この単一誤り仮定誤り値生成部３７４は、式３７に基づいて、次の式を使用して誤り値を生成する。
【数１３】
2015106872.tif 000015
上式において、左辺が誤り値を示す。
【０２３３】
単一誤り仮定誤り値生成部３７４は、生成した誤り値を単一誤り発生判定部３７３に供給する。
【０２３４】
単一誤り発生判定部３７３は、単一誤りが発生したか否かを判定するものである。この単一誤り発生判定部３７３は、単一誤りを仮定して得られた誤り位置および誤り値とシンドロームとから、０乃至２ｔ−１のｊのそれぞれについて次の式が成立するか否かを判断する。
【数１４】
2015106872.tif 000016
【０２３５】
実際に発生した誤りが１つのみであれば、全てのｊについて上式が成立する。このため、全てのｊについて上式が成立する場合には、単一誤り発生判定部３７３は、単一誤り位置が発生したと判定し、そうでない場合には２つ以上の誤りが発生したと判定する。単一誤り発生判定部３７３は、その判定結果を示す単一誤り発生フラグを生成してＯＲゲート３７１、二重以下誤り選択部３７２および二重誤り仮定誤り位置多項式生成部３７９へ供給する。単一誤り発生フラグには、例えば、単一誤りが発生した場合には「１」の値が設定され、そうでない場合には「０」の値が設定される。
【０２３６】
また、単一誤り発生判定部３７３は、単一誤りが発生した場合には、単一誤り仮定誤り位置検出部３７５および単一誤り仮定誤り値生成部３７４からの誤り位置および誤り値を二重以下誤り選択部３７２に供給する。
【０２３７】
二重誤り仮定誤り位置多項式生成部３７９は、二重誤りが発生したと仮定して誤り位置多項式Ｐ（ｘ）を生成するものである。この二重誤り仮定誤り位置多項式生成部３７９は、単一誤り発生フラグが「０」の値である場合には、式１１などを使用して、次数が「２」の誤り位置多項式Ｐ（ｘ）を生成する。そして、二重誤り仮定誤り位置多項式生成部３７９は、生成した誤り位置多項式Ｐ（ｘ）の各項の係数を二重誤り仮定誤り位置検出部３７８へ供給する。
【０２３８】
二重誤り仮定誤り位置検出部３７８は、二重誤りが発生したと仮定して誤り位置を検出するものである。この二重誤り仮定誤り位置検出部３７８は、二重誤り仮定誤り位置多項式生成部３７９により誤り位置多項式Ｐ（ｘ）が生成されると、公式（式１７乃至式２１）を使用して２つの誤り位置を検出する。また、二重誤り仮定誤り位置検出部３７８は、トレースＴｒ（Ｂ）がゼロになるか否かに基づいて訂正不可フラグを生成する。
【０２３９】
二重誤り仮定誤り位置検出部３７８は、訂正不可フラグと検出した誤り位置とを二重誤り発生判定部３７６および二重誤り仮定誤り値生成部３７７に供給する。
【０２４０】
二重誤り仮定誤り値生成部３７７は、二重誤りが発生したと仮定して誤り値を生成するものである。この二重誤り仮定誤り値生成部３７７は、二重誤り仮定誤り位置検出部３７８から誤り位置が供給されると、ｊ＝０，１のときの式２を用いて、連立方程式を解くなどして、誤り値を生成する。二重誤り仮定誤り値生成部３７７は、生成した誤り値を二重誤り発生判定部３７６に供給する。
【０２４１】
二重誤り発生判定部３７６は、二重誤りが発生したか否かを判定するものである。この二重誤り発生判定部３７６は、訂正不可フラグが「１」の値である場合には、３つ以上の誤りが発生したと判断する。
【０２４２】
一方、訂正不可フラグが「０」の値である場合には、二重誤り発生判定部３７６は、二重誤りを仮定して得られた誤り位置および誤り値に基づいて、次の式により推定シンドロームｓｐを求める。
【数１５】
2015106872.tif 000017
【０２４３】
二重誤り発生判定部３７６は、この推定シンドロームｓｐと、誤り検出部３２１からのシンドロームｓとが一致するか否かを判断する。実際に発生した誤りが２つであれば、これらのシンドロームは一致する。このため、シンドロームが一致するのであれば、二重誤り発生判定部３７６は、二重誤りが発生したと判断し、そうでない場合には二重誤りが発生していないと判断する。
【０２４４】
二重誤り発生判定部３７６は、二重誤りが発生したか否かの判断結果から二重誤り発生フラグを生成してＯＲゲート３７１および二重以下誤り選択部３７２に供給する。二重誤り発生フラグには、例えば、二重誤りが発生した場合には「１」の値が設定され、そうでない場合には「０」の値が設定される。
【０２４５】
二重以下誤り選択部３７２は、単一誤りを仮定して求められた誤り位置および誤り値と二重誤りを仮定して求められた誤り位置および誤り値とのいずれかを選択するものである。二重以下誤り選択部３７２は、単一誤り発生フラグが「１」の値である場合には、単一誤り発生判定部３７３からの誤り位置および誤り値を選択する。
【０２４６】
また、二重誤り発生フラグが「１」の値である場合には、二重以下誤り選択部３７２は、二重誤り発生判定部３７６の誤り位置および誤り値を選択する。二重以下誤り選択部３７２は、選択した誤り位置および誤り値を誤り訂正部３２４に供給する。
【０２４７】
ＯＲゲート３７１は、入力値の論理和を生成するものである。このＯＲゲート３７１には、単一誤り発生フラグおよび二重誤り発生フラグが入力される。ＯＲゲート３７１は、これらのフラグの値の論理和を二重以下誤り判定フラグとして生成する。ＯＲゲート３７１は、生成した二重以下誤り判定フラグを誤り位置検出部３３０および誤り選択部３２５に供給する。
【０２４８】
なお、二重以下誤り判定部３７０は、単一誤りが発生したか否かの判定を行ってから、二重誤りが発生したか否かの判定を行う構成としているが、これらの判定を並列に行ってもよい。
【０２４９】
また、単一誤り仮定誤り位置検出部３７５は、図８に例示した数式処理部３６０における単一誤り位置検出部３６４と回路やプログラムを共用してもよい。同様に、二重誤り仮定誤り位置検出部３７８は、図８に例示した数式処理部３６０におけるトレース計算部３６３および二重誤り位置検出部３６２と回路やプログラムを共用してもよい。
【０２５０】
図２７は、第４の実施の形態におけるリード処理の一例を示すフローチャートである。第３の実施の形態のリード処理は、ステップＳ９５０およびＳ９６０をさらに実行する点において第１の実施の形態と異なる。
【０２５１】
メモリコントローラ３００は、受信語に誤りが含まれる場合には（ステップＳ９１２：Ｙｅｓ）、誤り数Ｎｅが２以下であるか否かを判定する二重以下誤り判定処理を実行する（ステップＳ９５０）。そしてメモリコントローラ３００は、二重以下誤り判定フラグが「１」の値（オン）であるか否かを判断する（ステップＳ９６０）。二重以下誤り判定フラグがオフである場合には（ステップＳ９６０：Ｎｏ）、メモリコントローラ３００は、誤り検出処理（ステップＳ９２０）を実行する。
【０２５２】
一方、二重以下誤り判定フラグがオンである場合には（ステップＳ９６０：Ｙｅｓ）、メモリコントローラ３００は、単一誤りまたは二重誤りを仮定して得られた誤り位置および誤り値を使用して誤りの訂正を行う（ステップＳ９１７）。
【０２５３】
図２８は、第４の実施の形態における二重以下誤り判定処理の一例を示すフローチャートである。メモリコントローラ３００は、二重以下誤り判定フラグをオフにして、単一誤りを仮定した誤り位置の検出を行う（ステップＳ９５１）。そして、メモリコントローラ３００は、単一誤りを仮定した誤り値の生成を行う（ステップＳ９５２）。メモリコントローラ３００は、式３７を使用して、単一誤りが発生したか否かを判断する（ステップＳ９５３）。
【０２５４】
単一誤りが発生してない場合には（ステップＳ９５３：Ｎｏ）、メモリコントローラ３００は、二重誤りを仮定した誤り位置多項式を生成する（ステップＳ９５４）。そして、メモリコントローラ３００は、公式（式１７乃至式２１）を使用して二重誤りを仮定した誤り位置の検出を行う（ステップＳ９５５）。そして、メモリコントローラ３００は、二重誤りを仮定した誤り値の生成を行う（ステップＳ９５６）。
【０２５５】
メモリコントローラ３００は、式３９および訂正不可フラグに基づいて、二重誤りが発生したか否かを判断する（ステップＳ９５７）。単一誤りが発生した場合（ステップＳ９５３：Ｙｅｓ）、または、二重誤りが発生した場合（ステップＳ９５７：Ｙｅｓ）、メモリコントローラ３００は、二重以下誤り判定フラグをオンにする（ステップＳ９５８）。
【０２５６】
一方、二重誤りが発生していない場合（ステップＳ９５７：Ｎｏ）、または、ステップＳ９５８の後、メモリコントローラ３００は、二重以下誤り判定処理を終了する。
【０２５７】
このように、第４の実施の形態によれば、復号部３２０は、公式を使用して誤り位置を検出して誤り数が２以下である場合にチェン探索処理を開始するため、誤り数が２以下である場合に高速に誤り位置を検出することができる。これにより、復号部３２０は、誤り数が２以下である場合に高速に誤り訂正を行うことができる。
【０２５８】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２５９】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disc）、メモリカード、ブルーレイディスク（Blu-ray（登録商標）Disc）等を用いることができる。
【０２６０】
なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【０２６１】
なお、本技術は以下のような構成もとることができる。
（１）複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルについて誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出部と、
前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更部と、
前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出部と、
前記誤り位置検出部および前記未検出位置検出部により検出された前記誤りの位置における誤りを訂正する誤り訂正部と
を具備する誤り訂正装置。
（２）前記誤り位置検出部における前記誤りの位置の検出結果に基づいて前記検出数を計数する検出数カウンタをさらに具備し、
前記所定の条件は、前記検出数が一定数を超えることである
前記（１）記載の誤り訂正装置。
（３）前記所定の条件は、前記判定処理が行われていない前記シンボルにおける前記誤りの位置の個数が所定数に満たないことである
前記（１）記載の誤り訂正装置。
（４）前記判定対象変更部は、前記判定処理が行われるたびに前記判定処理が行われていない前記シンボルにおいて前記誤りの位置があるか否かを判断して前記誤りの位置があれば前記判定対象のシンボルの位置を変更する
前記（１）から（３）のいずれかに記載の誤り訂正装置。
（５）前記誤り位置検出部における誤りの位置の検出結果に基づいて前記検出数を計数する検出数カウンタをさらに具備し、
前記所定の条件は、前記検出数が一定数を超えることと前記判定対象のシンボルの位置が所定の範囲内であることとの両方が成立することである
前記（４）記載の誤り訂正装置。
（６）  前記所定の条件は、前記判定処理が行われていない前記シンボルにおける前記誤り位置の個数が所定数に満たないことと前記判定対象のシンボルの位置が前記所定の範囲内であることとの両方が成立することである
前記（４）記載の誤り訂正装置。
（７）前記変数は、誤り位置多項式の係数であり、
前記未検出位置検出部は、予め定められた前記係数と前記誤りの位置との関係に基づいて前記誤りの位置を検出する
前記（１）から（６）のいずれかに記載の誤り訂正装置。
（８）前記未検出位置検出部は、ＧＦ(２)のｍ次拡大体ＧＦ(２ｍ)の元をＣとして
Ｔｒ（Ｃ）＝Ｃ＾２０＋Ｃ＾２１＋・・・＋Ｃ＾２ｍ−１
においてＴ（Ｃ）＝１となるＣをＤとし、前記誤りの位置を示す前記有限体の元をｘとし、前記誤り位置多項式におけるｘ０の係数をＰ０とし、前記誤り位置多項式におけるｘ１の係数をＰ１とし、前記誤り位置多項式におけるｘ２の係数をＰ２として
ｙ＝ｘ（Ｐ２／Ｐ１）
Ｂ＝（Ｐ０・Ｐ２）／（Ｐ１）２
ｙ１＝（１／Ｔｒ（Ｄ））・｛Ｂ・Ｄ２＋（Ｂ＋Ｂ２）・Ｄ＾（２２）＋・・・
＋（Ｂ＋Ｂ＾２＋・・・Ｂ＾２ｍ−２）・Ｄ＾（２ｍ−１）
ｙ２＝ｙ１＋１
におけるｙ１およびｙ２のそれぞれに対応するｘの示す前記誤りの位置を検出する
前記（７）記載の誤り訂正装置。
（９）前記受信語から生成された前記変数を保持する変数保持部と、
前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記変数を更新する変数更新部とをさらに具備する
前記（１）から（８）のいずれかに記載の誤り訂正装置。
（１０）前記変数更新部は、前記判定対象のシンボルの位置が所定の範囲内である場合には前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記変数を更新する
前記（９）記載の誤り訂正装置。
（１１）前記変数更新部は、前記誤りの位置が検出されるたびに前記誤り位置検出部において前記判定処理が行われていない前記シンボルにおける前記誤りの位置の個数が１つであるか否かを判断して前記個数が１つでない場合には前記変数を更新し、
前記未検出位置検出部は、前記個数が１つである場合に前記更新された変数と前記誤りの位置との関係に基づいて前記誤りの位置を検出する
前記（９）記載の誤り訂正装置。
（１２）前記受信語から生成されたベクトルをシンドロームとして保持するシンドローム保持部と、
前記誤りの位置が検出されるたびに当該検出された誤りの位置に基づいて前記保持されたシンドロームを更新するシンドローム更新部と、
前記保持されたシンドロームから前記変数を生成して前記未検出位置検出部に供給する変数生成部とをさらに具備する
前記（１）から（１１）のいずれかに記載の誤り訂正装置。
（１３）  前記受信語から第１の誤り位置多項式を生成する第１の誤り位置多項式生成部と、
第２の誤り位置多項式を初期化して前記誤りの位置が検出されるたびに前記誤りの位置を示す一次の多項式を前記第２の誤り位置多項式に乗算する処理により前記第２の誤り位置多項式を更新する乗算部と、
前記所定の条件が満たされた場合には前記第２の誤り位置多項式により前記第１の誤り位置多項式を除算して当該除算により生成した多項式の係数を前記変数として前記未検出位置検出部に供給する除算部と
をさらに具備する前記（１）から（１１）のいずれかに記載の誤り訂正装置。
（１４）前記誤りの位置と前記受信語から生成された前記変数との関係に基づいて前記誤りの位置を検出して当該検出した誤りの位置の個数である誤り数が所定値を超えるか否かを判定する誤り数判定部をさらに具備し、
前記誤り位置検出部は、前記誤り数が前記所定値を超える場合または前記所定の条件が満たされない場合には前記誤りの位置を検出する
前記（１）から（１３）のいずれかに記載の誤り訂正装置。
（１５）前記誤り位置検出部は、複数の判定対象のシンボルについて前記判定処理を行い、
前記判定対象変更部は、前記複数の判定対象のシンボルの位置について前記判定処理が行われるたびに前記複数の判定対象のシンボルの位置のそれぞれを変更する
前記（１）から（１３）のいずれかに記載の誤り訂正装置。
（１６）前記検出された誤りの位置から誤り値を生成する誤り値生成部をさらに具備し、
前記受信語は、ＲＳ（Reed-Solomon）符号、または、ｍを２以上の整数としてｑ（＝２ｍ）元ＢＣＨ符号の符号語に対応する受信語であり、
前記誤り訂正部は、前記誤りの位置において前記誤り値を使用して前記誤りを訂正する
前記（１）から（１５）のいずれかに記載の誤り訂正装置。
（１７）前記受信語は、２元ＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号の符号語に対応する受信語であり、
前記誤り訂正部は、前記誤り位置検出部および前記未検出位置検出部により検出された前記誤りの位置において前記シンボルの値を反転する
前記（１）から（１５）のいずれかに記載の誤り訂正装置。
（１８）誤り位置検出部が、複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルに誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出手順と、
判定対象変更部が、前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更手順と、
未検出位置検出部が、前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出手順と、
誤り訂正部が、前記誤り位置検出手順および前記未検出位置検出手順により検出された前記誤りの位置における誤りを訂正する誤り訂正手順と
を具備する誤り訂正方法。
（１９）誤り位置検出部が、複数のシンボルを含む受信語において所定の条件が満たされない場合には判定対象のシンボルに誤りがあるか否かを判定する判定処理を行って誤りのある前記シンボルの位置である誤りの位置を検出する誤り位置検出手順と、
判定対象変更部が、前記判定処理が行われるたびに前記受信語において前記判定対象のシンボルの位置を変更する判定対象変更手順と、
未検出位置検出部が、前記所定の条件が満たされた場合には前記誤りの位置と前記受信語から生成された変数との関係に基づいて前記判定処理が行われていない前記シンボルにおける前記誤りの位置を検出する未検出位置検出手順と、
誤り訂正部が、前記誤り位置検出手順および前記未検出位置検出手順により検出された前記誤りの位置における誤りを訂正する誤り訂正手順と
をコンピュータに実行させるためのプログラム。
【符号の説明】
【０２６２】
１００  ホストコンピュータ
１０１  ユーザインターフェース
１０２、３０２  ＲＯＭ
１０３、３０３  ＲＡＭ
１０４、３０４  ＣＰＵ
１０５、３０５  バス
１０６  ストレージインターフェース
２００  ストレージ
３００  メモリコントローラ
３０１  ホストインターフェース
３０６  不揮発性メモリインターフェース
３１０  ＥＣＣ処理部
３１１  符号化部
３２０  復号部
３２１  誤り検出部
３２２  データバッファ
３２３  誤り値生成部
３２４  誤り訂正部
３２５  誤り選択部
３３０  誤り位置検出部
３４０  逐次探索処理部
３４１、３７１  ＯＲゲート
３４２  初期化部
３４３  誤り位置保持部
３４４  誤り位置選択部
３４５  切替判定部
３４６  訂正不可判定部
３４７  検出数カウンタ
３４８  誤り位置多項式更新部
３４９  逐次誤り位置検出部
３５０  誤り位置多項式保持部
３５１  シンボル位置カウンタ
３５２  誤り位置多項式生成部
３５３  シンドローム更新部
３５４  シンドローム保持部
３５５  検出済み誤り位置多項式生成部
３６０  数式処理部
３６１  誤り位置出力部
３６２  二重誤り位置検出部
３６３  トレース計算部
３６４  単一誤り位置検出部
３６５  誤り位置多項式再生成部
３６６  除算部
３７０  二重以下誤り判定部
３７２  二重以下誤り選択部
３７３  単一誤り発生判定部
３７４  単一誤り仮定誤り値生成部
３７５  単一誤り仮定誤り位置検出部
３７６  二重誤り発生判定部
３７７  二重誤り仮定誤り値生成部
３７８  二重誤り仮定誤り位置検出部
３７９  二重誤り仮定誤り位置多項式生成部
４００  不揮発性メモリ
【図１】
2015106872.tif 000018
【図２】
2015106872.tif 000019
【図３】
2015106872.tif 000020
【図４】
2015106872.tif 000021
【図５】
2015106872.tif 000022
【図６】
2015106872.tif 000023
【図７】
2015106872.tif 000024
【図８】
2015106872.tif 000025
【図９】
2015106872.tif 000026
【図１０】
2015106872.tif 000027
【図１１】
2015106872.tif 000028
【図１２】
2015106872.tif 000029
【図１３】
2015106872.tif 000030
【図１４】
2015106872.tif 000031
【図１５】
2015106872.tif 000032
【図１６】
2015106872.tif 000033
【図１７】
2015106872.tif 000034
【図１８】
2015106872.tif 000035
【図１９】
2015106872.tif 000036
【図２０】
2015106872.tif 000037
【図２１】
2015106872.tif 000038
【図２２】
2015106872.tif 000039
【図２３】
2015106872.tif 000040
【図２４】
2015106872.tif 000041
【図２５】
2015106872.tif 000042
【図２６】
2015106872.tif 000043
【図２７】
2015106872.tif 000044
【図２８】
2015106872.tif 000045