(57)【特許請求の範囲】
【請求項１】
誤り検出訂正符号における符号語を符号化対象データから生成する符号語生成部と、
前記符号語を反転したデータと前記符号語との一方をライトデータとして前記メモリセルに書き込むライト制御部と、
前記ライトデータを前記メモリセルからリードデータとして読み出して前記リードデータにおける誤りを訂正するリードデータ誤り訂正部と、
前記リードデータを反転した反転データにおける誤りを訂正する反転データ誤り訂正部と、
前記リードデータおよび前記反転データのうち一方のデータのみにおいて前記誤りの数が前記誤り検出訂正符号の訂正能力を超えない場合には前記誤りが訂正された前記一方のデータを選択して訂正データとして出力する訂正データ出力部と
を具備するメモリコントローラ。
【請求項２】
前記リードデータ誤り訂正部は、
前記リードデータおよび所定の検査行列の積をシンドロームとして計算する非反転側シンドローム計算部と、
前記シンドロームから前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正する非反転側誤り位置訂正部と
を備え、
前記反転データ誤り訂正部は、
前記反転データおよび前記所定の検査行列の積と前記シンドロームとの差である補正係数の加算により前記シンドロームを補正する反転補正部と、
前記補正されたシンドロームから前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正する反転側誤り位置訂正部と
前記反転側誤り位置訂正部により前記誤りが訂正された前記リードデータを反転する反転部と
を備える請求項１記載のメモリコントローラ。
【請求項３】
前記リードデータ誤り訂正部は、前記リードデータおよび所定の検査行列の積から前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正し、
前記反転データ誤り訂正部は、前記反転データおよび所定の検査行列の積から前記誤りの位置を検出して前記反転データにおいて前記検出した位置の誤りを訂正する
請求項１記載のメモリコントローラ。
【請求項４】
前記ライト制御部は、前記符号語を反転したデータと前記符号語とのうち前記メモリセルに書き込むときの消費電力の低い方を前記ライトデータとして書き込む
請求項１記載のメモリコントローラ。
【請求項５】
前記ライト制御部は、前記符号語において特定の値のビット数が前記符号語の総ビット数の半数より多い場合には前記符号語を前記ライトデータとして書き込み、前記特定の値のビット数が前記総ビット数の半数を超えない場合には前記符号語を反転したデータを前記ライトデータとして書き込む
請求項４記載のメモリコントローラ。
【請求項６】
前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えない場合には前記誤りが訂正された訂正リードデータと前記誤りが訂正された訂正反転データとのうち前記特定の値のビット数が多い方を前記訂正データとして出力する
請求項５記載のメモリコントローラ。
【請求項７】
前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えない場合には前記誤りが訂正された訂正リードデータと前記誤りが訂正された訂正反転データとのうち前記訂正された誤りが少ない方を前記訂正データとして出力する
請求項５記載のメモリコントローラ。
【請求項８】
前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えず、かつ、前記訂正リードデータおよび前記訂正反転データのそれぞれにおいて訂正された前記誤りの数が同じである場合には前記訂正リードデータおよび前記訂正反転データのうち前記特定の値のビット数が多い方を前記訂正データとして出力する
請求項７記載のメモリコントローラ。
【請求項９】
符号語生成部が、誤り検出訂正符号における符号語を符号化対象データから生成する符号語生成手順と、
ライト処理部が、前記符号語を反転したデータと前記符号語との一方をライトデータとして前記メモリセルに書き込むライト制御手順と、
リードデータ誤り訂正部が、前記ライトデータを前記メモリセルからリードデータとして読み出して前記リードデータにおける誤りを訂正するリードデータ誤り訂正手順と、
反転データ誤り訂正部が、前記リードデータを反転した反転データにおける誤りを訂正する反転データ誤り訂正手順と、
訂正データ出力部が、前記リードデータおよび前記反転データのうち一方のデータのみにおいて前記誤りの数が前記誤り検出訂正符号の訂正能力を超えない場合には前記誤りが訂正された前記一方のデータを選択して訂正データとして出力する訂正データ出力手順と
を具備するメモリコントローラの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、メモリコントローラおよびメモリコントローラの制御方法に関する。詳しくは、誤り訂正を行うメモリコントローラおよびメモリコントローラの制御方法に関する。
【背景技術】
【０００２】
近年の情報処理システムにおいては、補助記憶装置やストレージとして、不揮発性メモリ（ＮＶＭ：Non-Volatile memory）が用いられることがある。この不揮発性メモリは、大きなサイズを単位としたデータアクセスに対応したフラッシュメモリと、小さな単位での高速なランダムアクセスが可能な不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ：Non-Volatile RAM）とに大別される。ここで、フラッシュメモリの代表例としては、ＮＡＮＤ型フラッシュメモリが挙げられる。一方、不揮発性ランダムアクセスメモリの例としては、ＲｅＲＡＭ（Resistance RAM）、ＰＣＲＡＭ（Phase-Change RAM）、ＭＲＡＭ（Magnetoresistive RAM）などが挙げられる。【０００３】
これらの不揮発性メモリの中には、ライト処理において、２値のうちの一方の値のビットの書換えと他方の値の書換えとが順に行われるものがある。このような不揮発性メモリ（例えば、ＲｅＲＡＭ）において、それぞれの書換えにおける消費電力の最大値は、一般に書き換えるビット数が多いほど大きくなる。この最大消費電力を低減するために、反転した反転データと、反転していないデータとのうち、書き換えるビット数の少ない方を選択して不揮発性メモリに書き込む半導体装置が提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２１８４４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の従来の半導体装置は、書込みの際にデータを反転したか否かを示す反転ビットを生成し、反転前のデータまたは反転データとともに反転ビットを不揮発性メモリに書き込む。そして、半導体装置は、データを読み出す際に反転ビットを参照して、書込み時に反転されたのであれば、読み出したデータを反転する。このように、従来の半導体装置では、反転ビットを余分に不揮発性メモリに書き込む必要があるため、その反転ビットの分、不揮発性メモリの使用効率が低下してしまう問題がある。【０００６】
本技術はこのような状況に鑑みて生み出されたものであり、メモリの使用効率を向上させることを目的とする。
【課題を解決するための手段】
【０００７】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、誤り検出訂正符号における符号語を符号化対象データから生成する符号語生成部と、上記符号語を反転したデータと上記符号語との一方をライトデータとして上記メモリセルに書き込むライト制御部と、上記ライトデータを上記メモリセルからリードデータとして読み出して上記リードデータにおける誤りを訂正するリードデータ誤り訂正部と、上記リードデータを反転した反転データにおける誤りを訂正する反転データ誤り訂正部と、上記リードデータおよび上記反転データのうち一方のデータのみにおいて上記誤りの数が上記誤り検出訂正符号の訂正能力を超えない場合には上記誤りが訂正された上記一方のデータを選択して訂正データとして出力する訂正データ出力部とを具備するメモリコントローラ、および、その制御方法である。これにより、リードデータおよび反転データのうち一方のデータのみにおいて誤りの数が誤り訂正符号の訂正能力を超えない場合には誤りが訂正された一方のデータが訂正データとして出力されるという作用をもたらす。【０００８】
また、この第１の側面において、上記リードデータ誤り訂正部は、上記リードデータおよび所定の検査行列の積をシンドロームとして計算する非反転側シンドローム計算部と、上記シンドロームから上記誤りの位置を検出して上記リードデータにおいて上記検出した位置の誤りを訂正する非反転側誤り位置訂正部とを備え、上記反転データ誤り訂正部は、上記反転データおよび上記所定の検査行列の積と上記シンドロームとの差である補正係数の加算により上記シンドロームを補正する反転補正部と、上記補正されたシンドロームから上記誤りの位置を検出して上記リードデータにおいて上記検出した位置の誤りを訂正する反転側誤り位置訂正部と上記反転側誤り位置訂正部により上記誤りが訂正された上記リードデータを反転する反転部とを備えてもよい。これにより、補正係数の加算によりシンドロームが補正されるという作用をもたらす。【０００９】
また、この第１の側面において、上記リードデータ誤り訂正部は、上記リードデータおよび所定の検査行列の積から上記誤りの位置を検出して上記リードデータにおいて上記検出した位置の誤りを訂正し、上記反転データ誤り訂正部は、上記反転データおよび所定の検査行列の積から上記誤りの位置を検出して上記反転データにおいて上記検出した位置の誤りを訂正してもよい。これにより、リードデータおよび所定の検査行列の積から検出された誤りの位置がリードデータにおいて訂正され、反転データおよび所定の検査行列の積から検出された誤りの位置が反転データにおいて訂正されるという作用をもたらす。【００１０】
また、この第１の側面において、上記ライト制御部は、上記符号語を反転したデータと上記符号語とのうち上記メモリセルに書き込むときの消費電力の低い方を上記ライトデータとして書き込んでもよい。これにより、符号語を反転したデータと符号語とのうちメモリセルに書き込むときの消費電力の低い方がメモリセルに書き込まれるという作用をもたらす。【００１１】
また、この第１の側面において、上記ライト制御部は、上記符号語において特定の値のビット数が上記符号語の総ビット数の半数より多い場合には上記符号語を上記ライトデータとして書き込み、上記特定の値のビット数が上記総ビット数の半数を超えない場合には上記符号語を反転したデータを上記ライトデータとして書き込んでもよい。これにより、特定の値のビット数が総ビット数の半数を超えない場合には符号語を反転したデータが書き込まれるという作用をもたらす。【００１２】
また、この第１の側面において、上記リードデータおよび上記反転データの両方において上記誤りの数が上記訂正能力を超えない場合には上記誤りが訂正された訂正リードデータと上記誤りが訂正された訂正反転データとのうち上記特定の値のビット数が多い方を上記訂正データとして出力してもよい。これにより、リードデータおよび反転データの両方において誤りの数が上記訂正能力を超えない場合には訂正リードデータと訂正反転データとのうち特定の値のビット数が多い方が出力されるという作用をもたらす。【００１３】
また、この第１の側面において、上記リードデータおよび上記反転データの両方において上記誤りの数が上記訂正能力を超えない場合には上記誤りが訂正された訂正リードデータと上記誤りが訂正された訂正反転データとのうち上記訂正された誤りが少ない方を上記訂正データとして出力してもよい。これにより、リードデータおよび反転データの両方において誤りの数が訂正能力を超えない場合には訂正リードデータと訂正反転データとのうち訂正された誤りが少ない方が出力されるという作用をもたらす。【００１４】
また、この第１の側面において、上記リードデータおよび上記反転データの両方において上記誤りの数が上記訂正能力を超えず、かつ、上記訂正リードデータおよび上記訂正反転データのそれぞれにおいて訂正された上記誤りの数が同じである場合には上記訂正リードデータおよび上記訂正反転データのうち上記特定の値のビット数が多い方を上記訂正データとして出力してもよい。これにより、リードデータおよび反転データの両方において上記誤りの数が訂正能力を超えず、かつ、訂正リードデータおよび訂正反転データのそれぞれにおいて訂正された誤りの数が同じである場合には上記特定の値のビット数が多い方が出力されるという作用をもたらす。
【発明の効果】
【００１５】
本技術によれば、メモリの使用効率を向上させることができるという優れた効果を奏し得る。なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【図面の簡単な説明】
【００１６】
【図１】第１の実施の形態における情報処理システムの一構成例を示すブロック図である。
【図２】第１の実施の形態におけるメモリコントローラの具体的な構成例を示すブロック図である。
【図３】第１の実施の形態におけるメモリコントローラの機能構成例を示すブロック図である。
【図４】第１の実施の形態におけるライト処理部の一構成例を示すブロック図である。
【図５】第１の実施の形態における符号語およびライト側反転データの一例を示す図である。
【図６】第１の実施の形態におけるリード処理部の一構成例を示すブロック図である。
【図７】第１の実施の形態における訂正データ選択部の動作の一例を示す表である。
【図８】第１の実施の形態におけるリードデータ誤り検出訂正部および反転データ誤り検出訂正部の一構成例を示すブロック図である。
【図９】第１の実施の形態におけるシンドローム計算部の一構成例を示すブロック図である。
【図１０】第１の実施の形態におけるリードデータおよびリード側反転データの一例を示す図である。
【図１１】第１の実施の形態における不揮発性メモリの一構成例を示すブロック図である。
【図１２】第１の実施の形態におけるストレージの動作の一例を示すフローチャートである。
【図１３】第１の実施の形態におけるコントローラ側ライト処理の一例を示すフローチャートである。
【図１４】第１の実施の形態におけるＮＶＲＡＭ側ライト処理の一例を示すフローチャートである。
【図１５】第１の実施の形態におけるコントローラ側リード処理の一例を示すフローチャートである。
【図１６】第１の実施の形態の第１の変形例におけるリード処理部の一構成例を示すブロック図である。
【図１７】第１の実施の形態の第１の変形例におけるコントローラ側リード処理の一例を示すフローチャートである。
【図１８】第１の実施の形態の第２の変形例におけるコントローラ側リード処理の一例を示すフローチャートである。
【図１９】第２の実施の形態におけるリード処理部の一構成例を示すブロック図である。
【図２０】第２の実施の形態におけるリードデータ誤り検出訂正部および反転データ誤り検出訂正部の一構成例を示すブロック図である。
【図２１】第２の実施の形態における反転補正部の一構成例を示すブロック図である。
【発明を実施するための形態】
【００１７】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（リードデータと反転データとのうち訂正に成功した方を出力する例）
２．第２の実施の形態（反転補正後にリードデータと反転データとのうち訂正に成功した方を出力する例）
【００１８】
＜１．第１の実施の形態＞
［情報処理システムの構成例］
図１は、第１の実施の形態における情報処理システムの一構成例を示すブロック図である。この情報処理システムは、ホストコンピュータ１００およびストレージ２００を備える。
【００１９】
ホストコンピュータ１００は、情報処理システム全体を制御するものである。具体的には、ホストコンピュータ１００は、コマンドおよびデータを生成してストレージ２００に信号線１０９を介して供給する。また、ホストコンピュータ１００は、ストレージ２００から、読み出されたデータを受け取る。ここで、コマンドは、ストレージ２００を制御するためのものであり、例えば、データの書込みを指示するライトコマンドや、データの読出しを指示するリードコマンドを含む。
【００２０】
ストレージ２００は、メモリコントローラ３００および不揮発性メモリ４００を備える。このメモリコントローラ３００は、不揮発性メモリ４００を制御するものである。メモリコントローラ３００は、ホストコンピュータ１００からライトコマンドおよびデータを受け取った場合には、そのデータから誤り検出訂正符号（ＥＣＣ：Error detection and Correction Code）を生成する。具体的には、メモリコントローラ３００は、データを、そのデータおよびパリティからなる符号語に変換（すなわち、符号化）する。メモリコントローラ３００は、不揮発性メモリ４００に信号線３０９を介してアクセスして符号化したデータを書き込む。
【００２１】
また、ホストコンピュータ１００からリードコマンドを受け取った場合、メモリコントローラ３００は、不揮発性メモリ４００に信号線３０９を介してアクセスして符号化されたデータを読み出す。そして、メモリコントローラ３００は、符号化されたデータを、符号化前の元のデータに変換（すなわち、復号）する。また、メモリコントローラ３００は、ＥＣＣに基づいてデータにおける誤りの検出および訂正を行う。メモリコントローラ３００は、訂正したデータをホストコンピュータ１００に供給する。
【００２２】
不揮発性メモリ４００は、メモリコントローラ３００の制御に従って、データを記憶するものである。例えば、ＲｅＲＡＭが不揮発性メモリ４００として用いられる。この不揮発性メモリ４００は、複数のメモリセルを備え、これらのメモリセルは、複数のブロックに分けられている。ここで、ブロックは、不揮発性メモリ４００のアクセス単位であり、セクタとも呼ばれる。ブロックのそれぞれにはメモリアドレスが割り当てられている。なお、ＲｅＲＡＭの代わりに、フラッシュメモリ、ＰＣＲＡＭ、および、ＭＲＡＭなどを不揮発性メモリ４００として用いてもよい。
【００２３】
［メモリコントローラの構成例］
図２は、第１の実施の形態におけるメモリコントローラ３００の一構成例を示すブロック図である。このメモリコントローラ３００は、ＲＡＭ（Random Access Memory）３０２、ＣＰＵ（Central Processing Unit）３０３、ＥＣＣ処理部３０４およびＲＯＭ（Read Only Memory）３０５を備える。また、メモリコントローラ３００は、ホストインターフェース３０１、バス３０６およびメモリインターフェース３０７を備える。
【００２４】
ＲＡＭ３０２は、ＣＰＵ３０３が実行する処理において必要となるデータを一時的に保持するものである。ＣＰＵ３０３は、メモリコントローラ３００全体を制御するものである。ＲＯＭ３０５は、ＣＰＵ３０３が実行するプログラム等を記憶するものである。ホストインターフェース３０１は、ホストコンピュータ１００との間でデータやコマンドを相互に交換するものである。バス３０６は、ＲＡＭ３０２、ＣＰＵ３０３、ＥＣＣ処理部３０４、ＲＯＭ３０５、ホストインターフェース３０１およびメモリインターフェース３０７が相互にデータを交換するための共通の経路である。メモリインターフェース３０７は、不揮発性メモリ４００との間でデータやコマンドを相互に交換するものである。
【００２５】
ＥＣＣ処理部３０４は、符号化対象のデータを符号化し、また、符号化されたデータを復号するものである。データの符号化においてＥＣＣ処理部３０４は、符号化対象データにパリティを付加することにより所定の単位で符号化する。所定の単位で符号化された個々のデータを以下、「符号語」と称する。そして、ＥＣＣ処理部３０４は、符号化したデータをライトデータとして不揮発性メモリ４００にバス３０６を介して供給する。
【００２６】
また、ＥＣＣ処理部３０４は、符号化されたリードデータを元のデータに復号する。この復号において、ＥＣＣ処理部３０４は、パリティを使用して符号語の誤りを検出および訂正する。ＥＣＣ処理部３０４は、復号した元のデータをホストコンピュータ１００にバス３０６を介して供給する。
【００２７】
［メモリコントローラの構成例］
図３は、第１の実施の形態におけるメモリコントローラ３００の機能構成例を示すブロック図である。このメモリコントローラ３００は、ライト処理部３１０およびリード処理部３２０を備える。図３におけるライト処理部３１０は、図２におけるＲＡＭ３０２、ＣＰＵ３０３、ＥＣＣ処理部３０４、ＲＯＭ３０５、ホストインターフェース３０１、バス３０６およびメモリインターフェース３０７などにより実現される。リード処理部３２０についても同様である。
【００２８】
ライト処理部３１０は、ライトコマンドに従って、ライトデータを不揮発性メモリ４００に書き込む処理を実行するものである。ライト処理部３１０は、ホストコンピュータ１００からライトコマンドおよび符号化対象データを受け取った場合には、その符号化対象データを符号語に符号化する。符号化において符号化対象データは、例えば、２元のＢＣＨ符号に符号化される。ＢＣＨ符号への符号化においては、例えば、次の式１による生成多項式が用いられる。
【数１】
0006540703.tif 000002
式１において、ＬＣＭ［］は、［］内の各々の多項式の最小公倍多項式を表わす。また、Ｍｉ（ｘ）は、ガロア体ＧＦ（２ｑ）上の原始元をαとしたときのαｉの、最小多項式である。
【００２９】
ライト処理部３１０は、符号化対象データから符号多項式を生成し、その符号多項式を式１に例示した生成多項式により割った剰余を求める。この符号多項式は、符号化対象データの各々のビットの値を係数とする多項式である。ライト処理部３１０は、求めた剰余の係数の各々からなるデータをパリティとして生成し、符号化対象データおよびパリティからなる符号語をライトデータとして不揮発性メモリ４００に出力する。
【００３０】
なお、ライト処理部３１０は、生成多項式を使用した多項式演算でなく、行列演算によって符号化を行ってもよい。また、ライト処理部３１０は、符号化対象データを２元のＢＣＨ符号に符号化しているが、誤り訂正能力を持つ符号であれば、ＢＣＨ符号以外の符号に符号化してもよい。ライト処理部３１０は、例えば、ＲＳ（Reed-Solomon）符号や畳込み符号に符号化してもよい。また、ライト処理部３１０は、２元より高い次元の符号に符号化してもよい。
【００３１】
リード処理部３２０は、リードコマンドに従って、リードデータを不揮発性メモリ４００から読み出す処理を実行するものである。リード処理部３２０は、ホストコンピュータ１００からリードコマンドを受け取ると、そのコマンドにより指定されたメモリアドレスから符号語をリードデータとして読み出す。リード処理部３２０は、リードデータを元のデータに復号する。復号においてリード処理部３２０は、リードデータに含まれるパリティを使用して、リードデータにおける誤りを訂正する。誤り訂正方法の詳細については後述する。リード処理部３２０は、誤りを訂正した訂正データをホストコンピュータ１００へ出力する。また、リード処理部３２０は、誤り訂正の成否に基づいてエラーフラグを生成し、ホストコンピュータ１００へ出力する。
【００３２】
［ライト処理部の構成例］
図４は、第１の実施の形態におけるライト処理部３１０の一構成例を示すブロック図である。このライト処理部３１０は、符号化部３１１、反転判定部３１２、ライト側反転部３１３およびセレクタ３１４を備える。
【００３３】
符号化部３１１は、ライトコマンドに従って、式１の生成多項式を使用して符号化対象データを符号語に符号化するものである。この符号化部３１１は、符号語を反転判定部３１２、ライト側反転部３１３およびセレクタ３１４に供給する。なお、符号化部３１１は、特許請求の範囲に記載の符号語生成部の一例である。
【００３４】
反転判定部３１２は、符号語および反転データのうち、不揮発性メモリ４００に書き込むときの消費電力の低い方はいずれかを判定するものである。この反転判定部３１２は、例えば、符号語において、特定の値（例えば、「１」）のビットが、符号語の総ビット数ｎの半数よりビット数の多い多数ビットであるか否かを判定する。そして、「１」のビットが多数ビットである場合には、反転判定部３１２は、符号語を指定する判定ビットを生成し、そうでない場合には反転データを指定する判定ビットを生成する。
【００３５】
このように「１」のビットが多数ビットでなければ、反転データが書き込まれるため、ライトデータにおいて、「０」のビット数は常に総ビット数ｎの半数以下となる。このため、不揮発性メモリ４００において、「１」を「０」に書き換えるリセット処理と、「０」を「１」に書き換えるセット処理とのそれぞれで変化ビット数が常にｎ／２以下となる。したがって、不揮発性メモリ４００のライト処理において消費電力の最大値が低減する。
【００３６】
ライト側反転部３１３は、符号語を反転するものである。このライト側反転部３１３は、反転した符号語をライト側反転データとしてセレクタ３１４に供給する。
【００３７】
セレクタ３１４は、判定ビットに従って、符号語およびライト側反転データの一方を選択するものである。セレクタ３１４は、選択した方のデータをライトデータとして不揮発性メモリ４００に供給する。なお、セレクタ３１４は、特許請求の範囲に記載のライト制御部の一例である。
【００３８】
なお、ライト処理部３１０は、特定の値のビットが多数ビットであるか否かにより、書き込むデータを選択しているが、この構成に限定されない。例えば、特許文献１に記載のように、ライト処理部３１０は、ライトアドレスからデータを読み出し、符号語およびライト側反転データのそれぞれとビット単位で比較して、書き換えるビット数の少ない方をライトデータとして書き込んでもよい。
【００３９】
図５は、第１の実施の形態における符号語およびライト側反転データの一例を示す図である。同図におけるａは、符号語の一例を示す図である。例えば、（４０、２４）符号においては、２４ビットのライトデータから、１６ビットのパリティが生成され、それらを含む４０ビットの符号語が生成される。この符号語において、「１」のビット数は「１１」個であり、４０／２以下である。このため、「１」は多数ビットでない。同図におけるｂは、同図におけるａの符号語を反転したライト側反転データの一例を示す図である。前述したように符号語において「１」が多数ビットでないため、ライト側反転データの方がライトデータとして不揮発性メモリ４００に書き込まれる。
【００４０】
図６は、第１の実施の形態におけるリード処理部３２０の一構成例を示すブロック図である。このリード処理部３２０は、セレクタ３２１、訂正データ選択部３２２および誤り検出訂正部３３０を備える。また、誤り検出訂正部３３０は、リードデータ誤り検出訂正部３４０、反転データ誤り検出訂正部３６０およびリード側反転部３９０を備える。
【００４１】
リード側反転部３９０は、リードコマンドに従って不揮発性メモリ４００からリードデータを読み出し、そのリードデータを反転するものである。このリード側反転部３９０は、反転したリードデータをリード側反転データとして反転データ誤り検出訂正部３６０に供給する。
【００４２】
リードデータ誤り検出訂正部３４０は、リードコマンドに従って不揮発性メモリ４００からリードデータを読み出し、そのリードデータにおいて誤り検出および誤り訂正を行うものである。このリードデータ誤り検出訂正部３４０は、誤り検出および誤り訂正の結果に基づいて、誤り訂正に成功したか否かを示す訂正成否ビットＢｒを生成する。ここで、誤りが検出されなかった場合は誤り訂正自体が行われないが、この場合は、説明の便宜上、誤り訂正の成功として扱われるものとする。この訂正成否ビットＢｒには、例えば、誤り訂正に成功した場合に「１」の値が設定され、誤り訂正に失敗した場合に「０」の値が設定される。
【００４３】
また、誤り訂正に成功した場合にリードデータ誤り検出訂正部３４０は、誤り訂正後のリードデータから、パリティを除いたデータを訂正リードデータＤｒとしてセレクタ３２１に供給する。また、リードデータ誤り検出訂正部３４０は、誤り訂正に成功したことを通知する訂正成否ビットＢｒを生成して、訂正データ選択部３２２に供給する。
【００４４】
ここで、誤りの数がＥＣＣの訂正能力を超える場合には誤り訂正に失敗するおそれがある。この場合にリードデータ誤り検出訂正部３４０は、誤り訂正に失敗したことを通知する訂正成否ビットＢｒを生成して、訂正データ選択部３２２に供給する。なお、リードデータ誤り検出訂正部３４０は、特許請求の範囲に記載のリードデータ誤り訂正部の一例である。
【００４５】
反転データ誤り検出訂正部３６０は、反転データにおいて誤り検出および誤り訂正を行うものである。この反転データ誤り検出訂正部３６０は、反転データの誤り訂正に成功したか否かを示す訂正成否ビットＢｒ’を生成する。
【００４６】
誤り訂正に成功した場合に反転データ誤り検出訂正部３６０は、誤り訂正後の反転データからパリティを除いたデータを訂正反転データＤｒ’としてセレクタ３２１に供給する。また、反転データ誤り検出訂正部３６０は、誤り訂正に成功したことを通知する訂正成否ビットＢｒ’を生成して訂正データ選択部３２２に供給する。
【００４７】
一方、誤りの訂正に失敗した場合に反転データ誤り検出訂正部３６０は、誤り訂正に失敗したことを通知する訂正成否ビットＢｒ’を生成して、訂正データ選択部３２２に供給する。なお、反転データ誤り検出訂正部３６０は、特許請求の範囲に記載の反転データ誤り訂正部の一例である。
【００４８】
訂正データ選択部３２２は、リードデータおよび反転データの一方のみの誤り訂正に成功した場合には、その成功した方のデータを選択するものである。この訂正データ選択部３２２は、リードデータのみの誤り訂正に成功した場合に訂正リードデータＤｒを選択し、反転データのみの誤り訂正に成功した場合に訂正反転データＤｒ’を選択する。そして、訂正データ選択部３２２は、選択した方を示す選択ビットを生成してセレクタ３２１に供給し、リードエラーが生じなかった旨を通知するエラーフラグを生成してホストコンピュータ１００に出力する。この選択ビットには、例えば、訂正リードデータＤｒが選択された場合に「０」の値が設定され、訂正反転データＤｒ’ が選択された場合に「１」の値が設定される。また、エラーフラグには、リードエラーが生じなかった場合に「０」の値が設定され、そのリードエラーが生じた場合に「１」の値が設定される。
【００４９】
また、リードデータおよび反転データの両方の誤り訂正に失敗した場合、訂正データ選択部３２２は、リードエラーが生じた旨を通知するエラーフラグを生成してホストコンピュータ１００に出力する。
【００５０】
また、リードデータおよび反転データの両方の誤り訂正に成功した場合にも、訂正データ選択部３２２は、リードエラーが生じた旨を通知するエラーフラグを生成してホストコンピュータ１００に出力する。両方の誤り訂正に成功した場合にリードエラーとして扱うのは、リードデータおよび反転データの少なくとも一方において、訂正能力を超える数の誤りが発生したおそれがあり、いずれのデータが正しいのか判断することができないためである。
【００５１】
セレクタ３２１は、選択ビットに従って、訂正データＤｒおよび訂正反転データＤｒ’の一方を訂正データとしてホストコンピュータ１００へ出力するものである。なお、セレクタ３２１は、特許請求の範囲に記載の訂正データ出力部の一例である。
【００５２】
なお、リードエラーの際に、リード処理部３２０はホストコンピュータ１００に訂正前のデータを出力する構成としてもよい。この場合に、リード処理部３２０は、例えば、訂正前のリードデータおよびリード側反転データの少なくとも一方をホストコンピュータ１００に出力する。そして、ホストコンピュータ１００は、例えば、メモリコントローラ３００が用いる復号アルゴリズムよりも誤り訂正能力の高いアルゴリズムにより、そのデータの誤り訂正を行う。訂正能力の低い方の復号アルゴリズムとして、例えば、軟判定復号アルゴリズムにおけるＭｉｎ−Ｓｕｍアルゴリズムが用いられる。また、訂正能力の高い方の復号アルゴリズムとして、例えば、ＢＰ（Brief-Propagation）アルゴリズムが用いられる。
【００５３】
また、リードデータ誤り検出訂正部３４０は、パリティを除いたデータを訂正データＤｒとして出力しているが、パリティを除去しないで、訂正後のリードデータをそのまま出力してもよい。反転データ誤り検出訂正部３６０についても同様である。
【００５４】
図７は、第１の実施の形態における訂正データ選択部３２２の動作の一例を示す表である。訂正成否ビットＢｒおよびＢｒ’の両方が「０」の場合、すなわちリードデータおよびリード側反転データの両方の訂正に失敗した場合には、訂正データ選択部３２２は、リードエラーのあったことを示す「１」のエラーフラグを生成する。この場合、選択ビットは、「０」および「１」のいずれのビットであってもよい。
【００５５】
また、訂正成否ビットＢｒ’のみが「１」の場合、すなわちリード側反転データのみの訂正に成功した場合には、訂正データ選択部３２２は、訂正反転データＤｒ’を示す「１」の選択ビットを生成する。また、訂正データ選択部３２２は、リードエラーの無いことを示す「０」のエラーフラグを生成する。
【００５６】
また、訂正成否ビットＢｒのみが「１」の場合、すなわちリードデータのみの訂正に成功した場合には、訂正データ選択部３２２は、訂正リードデータＤｒを示す「０」の選択ビットを生成する。また、訂正データ選択部３２２は、リードエラーの無いことを示す「０」のエラーフラグを生成する。
【００５７】
また、訂正成否ビットＢｒおよびＢｒ’の両方が「１」の場合、すなわちリードデータおよびリード側反転データの両方の訂正に成功した場合には、訂正データ選択部３２２は、リードエラーのあったことを示す「１」のエラーフラグを生成する。この場合、選択ビットは、「０」および「１」のいずれのビットであってもよい。
【００５８】
図８は、第１の実施の形態におけるリードデータ誤り検出訂正部３４０および反転データ誤り検出訂正部３６０の一構成例を示すブロック図である。リードデータ誤り検出訂正部３４０は、シンドローム計算部３５０、誤り位置計算部３４１および誤り位置訂正部３４２を備える。また、反転データ誤り検出訂正部３６０は、シンドローム計算部３７０、誤り位置計算部３６１および誤り位置訂正部３６２を備える。
【００５９】
シンドローム計算部３５０は、リードデータからシンドロームを計算するものである。このシンドロームは、受信語（すなわち、リードデータ）に検査行列を乗じることにより得られるベクトルであり、誤りの位置を求めるために用いられる。
【００６０】
ここで、短縮化符号における符号語をｃとし、誤りのパターンをｅとし、そのｅを含む受信語をｒとすると、これらは、次の式により表される。
【数２】
0006540703.tif 000003
【数３】
0006540703.tif 000004
【数４】
0006540703.tif 000005
【００６１】
また、シンドロームを求める演算は、例えば、次の式により表わされる。
【数５】
0006540703.tif 000006
上式においてＨは、検査行列であり、Ｓはシンドロームである。また、αは、ＧＦ（２ｑ）の原始元であり、ｔは１以上の整数である。
【００６２】
シンドローム計算部３５０は、式５を使用して算出したシンドロームＳを誤り位置計算部３４１および誤り位置訂正部３４２に供給する。
【００６３】
誤り位置計算部３４１は、誤りの位置を計算するための誤り位置多項式をシンドロームから計算するものである。この誤り位置計算部３４１は、例えば、次の式６のような誤り位置多項式と、次の式７のような誤り評価多項式とを生成する。
【数６】
0006540703.tif 000007
【数７】
0006540703.tif 000008
式６および式７において、ｊ１乃至ｊＬは、誤りの位置である。これらの誤りの位置の個数、すなわち誤りの個数が誤り訂正能力以下であれば、誤り訂正が成功する。
【００６４】
式６の根から、誤りの位置が求められる。また、式７から誤りの位置における値が求められる。
【００６５】
誤り位置計算部３４１は、まずシンドロームから次の式に示す多項式Ｓ（ｘ）を生成する。
【数８】
0006540703.tif 000009
ここで奇数次の係数Ｓ１、Ｓ３、‥、Ｓ２ｔ−１は式５で得られる。また、偶数次の係数Ｓ２、Ｓ４、‥、Ｓ２ｔは次の式のように奇数次の係数から計算できる。
【数９】
0006540703.tif 000010
誤り位置計算部３４１は、次に式１０乃至式１３を満たすσ（ｘ）とω（ｘ）を計算する。これは、ピーターソン法やユークリッド法などにより求められる。この計算が成功した場合、σ（ｘ）とω（ｘ）をそれぞれ誤り位置多項式と誤り評価多項式と呼び、式６および式７を満たしている。
【数１０】
0006540703.tif 000011
上式においてＡ  ｍｏｄ  Ｂは、ＡをＢで割った剰余を意味する。
【００６６】
【数１１】
0006540703.tif 000012
【数１２】
0006540703.tif 000013
【数１３】
0006540703.tif 000014
式１１において、ｄｅｇＡ（ｚ）は、多項式Ａ（ｚ）の最大の次数を示す。
【００６７】
条件を満たす誤り位置多項式および誤り評価多項式が存在しない場合には、誤り訂正能力を越える数の誤りがあるために誤り訂正が失敗したと判断される。その場合には、誤り訂正に失敗した旨が誤り位置訂正部３４２に通知される。
【００６８】
一方、式１１乃至式１３を満たす誤り位置多項式および誤り評価多項式が存在する場合、誤り位置計算部３４１は、それらを誤り位置訂正部３４２に供給する。
【００６９】
誤り位置訂正部３４２は、リードデータ内の誤り位置における誤りを訂正するものである。この誤り位置訂正部３４２は、シンドロームの成分Ｓｉが全て「０」である場合には、誤りが無いと判断し、誤り訂正に成功した旨を示す訂正成否ビットＢｒを生成して訂正データ選択部３２２に出力する。また、誤り位置訂正部３４２は、訂正前のリードデータからパリティを除いたデータを訂正リードデータＤｒとしてセレクタ３２１に出力する。
【００７０】
一方、シンドロームの成分Ｓｉが全て「０」でない場合に誤り位置訂正部３４２は、誤り位置多項式の根を求め、根に対応するｊ１乃至ｊＬを誤りの位置として検出する。
【００７１】
Ｌ個の誤りの位置の検出に成功した場合に誤り位置訂正部３４２は、誤り訂正に成功した旨を示す訂正成否ビットＢｒを生成して訂正データ選択部３２２に出力する。また、誤り位置訂正部３４２は、検出した誤りの位置の各々のビットを反転することによりリードデータの誤りを訂正する。そして、誤り位置訂正部３４２は、訂正後のリードデータからパリティを除いたデータを訂正リードデータＤｒとしてセレクタ３２１に出力する。
【００７２】
式１１等の条件を満たす誤り位置多項式等が存在しない場合、または、Ｌ個の誤りの位置の検出に失敗した場合に誤り位置訂正部３４２は、誤り訂正に失敗した旨を示す訂正成否ビットＢｒを生成して訂正データ選択部３２２に出力する。
【００７３】
なお、２元より高い次元のＢＣＨ符号を使用する場合、誤りの位置に加え、その位置におけるシンボルの値も求める必要がある。この場合、シンボルの値は、例えば、次の式１４および式１５により求められる。
【数１４】
0006540703.tif 000015
【数１５】
0006540703.tif 000016
【００７４】
シンドローム計算部３７０は、反転データからシンドロームＳ’を計算するものである。シンドローム計算部３７０の構成は、シンドローム計算部３５０と同様である。
【００７５】
誤り位置計算部３６１は、誤り位置多項式をシンドロームＳ’から計算するものである。この誤り位置計算部３６１の構成は、誤り位置計算部３４１と同様である。
【００７６】
誤り位置訂正部３６２は、反転データ内の誤り位置における誤りを訂正するものである。誤り位置訂正部３６２の構成は、訂正リードデータＤｒの代わりに訂正反転データＤｒ’を生成し、訂正成否ビットＢｒの代わりに訂正成否ビットＢｒ’を生成する点以外は、誤り位置訂正部３４２と同様である。
【００７７】
［シンドローム計算部の構成例］
図９は、第１の実施の形態におけるシンドローム計算部３５０の一構成例を示すブロック図である。このシンドローム計算部３５０は、ｔ個のシンドローム成分計算部３５１を備える。ｔ個目のシンドローム成分計算部３５１は、式５における成分Ｓｉを生成し、誤り位置計算部３４１等に供給する。
【００７８】
図１０は、第１の実施の形態におけるリードデータおよびリード側反転データの一例を示す図である。同図におけるａは、ライト処理部３１０により反転データが書き込まれた際のリードデータの一例を示す図である。同図におけるｂは、同図におけるａのリードデータを反転したリード側反転データの一例を示す図である。同図におけるｃは、同図におけるｂのリード側反転データを訂正したデータの一例を示す図である。
【００７９】
図１０に例示したように、反転データが書き込まれた際には、リードデータを反転しないと、通常はリード処理部３２０において誤り訂正に成功しない。このため、リード処理部３２０は、リード側反転データのみの誤り訂正に成功する。そして、誤りが訂正されたリード側反転データがホストコンピュータ１００に出力される。
【００８０】
［不揮発性メモリの構成例］
図１１は、第１の実施の形態における不揮発性メモリ４００の一構成例を示すブロック図である。この不揮発性メモリ４００は、データバッファ４１０、メモリセルアレイ４２０、ドライバ４３０、アドレスデコーダ４４０、バス４５０、制御インターフェース４６０、および、メモリ制御部４７０を備える。
【００８１】
データバッファ４１０は、メモリ制御部４７０の制御に従って、ライトデータやリードデータをアクセス単位で保持するものである。メモリセルアレイ４２０は、マトリックス
状に配列された複数のメモリセルを備える。各々のメモリセルとして、不揮発性の記憶素
子が用いられる。具体的には、ＮＡＮＤ型やＮＯＲ型のフラッシュメモリ、ＲｅＲＡＭ、ＰＣＲＡＭ、または、ＭＲＡＭなどが記憶素子として用いられる。
【００８２】
ドライバ４３０は、アドレスデコーダ４４０により選択されたメモリセルに対してデータの書込み、または、データの読出しを行うものである。アドレスデコーダ４４０は、コマンドにより指定されたアドレスを解析して、そのアドレスに対応するメモリセルを選択するものである。バス４５０は、データバッファ４１０、メモリセルアレイ４２０、アドレスデコーダ４４０、メモリ制御部４７０および制御インターフェース４６０が相互にデータを交換するための共通の経路である。制御インターフェース４６０は、メモリコントローラ３００と不揮発性メモリ４００とがデータやコマンドを相互に交換するためのインターフェースである。
【００８３】
メモリ制御部４７０は、ドライバ４３０およびアドレスデコーダ４４０を制御して、データの書込み、または、読出しを行わせるものである。メモリ制御部４７０は、ライトコマンドおよびライトデータを受け取った場合には、そのコマンドの指定するアドレスに書き込まれているデータを既書込みデータとして読み出す。この読出しは、プレリードと呼ばれる。メモリ制御部４７０は、ライトデータと既書込みデータとをビット単位で比較し、ライトデータにおいて「１」であり、かつ、既書込みデータにおいて「０」のビットを書換え対象とする。メモリ制御部４７０は、それらの書換え対象のビットを「１」に書き換える。この処理は、リセット処理と呼ばれる。次に、メモリ制御部４７０は、ライトデータとセット処理後の既書込みデータとをビット単位で比較し、ライトデータにおいて「０」であり、かつ、既書込みデータにおいて「１」のビットを書換え対象とする。メモリ制御部４７０は、それらの書換え対象のビットを「０」に書き換える。この処理は、セット処理と呼ばれる。
【００８４】
また、メモリ制御部４７０は、リードコマンドを受け取ると、アドレスデコーダ４４０およびドライバ４３０を制御してメモリコントローラ３００へリードデータを出力させる。
【００８５】
［ストレージの動作例］
図１２は、第１の実施の形態におけるストレージ２００の動作の一例を示すフローチャートである。この動作は、例えば、ホストコンピュータ１００によりストレージ２００に対して初期化が指示されたときに開始する。
【００８６】
不揮発性メモリ４００は、メモリセルアレイ４２０内の全ビットを特定の値（例えば、「１」）に初期化する（ステップＳ９０１）。メモリコントローラ３００は、ホストコンピュータ１００からのコマンドをデコードする（ステップＳ９０２）。メモリコントローラ３００は、ホストコンピュータ１００からコマンドを受け取った場合に、そのコマンドがライトコマンドであるか否かを判断する（ステップＳ９０３）。ここでは、ホストコンピュータ１００からのコマンドは、ライトコマンドおよびリードコマンドのうちのいずれかであるものとする。なお、不揮発性メモリ４００は、全ビットを「１」の値に初期化しているが、「０」の値に初期化してもよい。この場合、メモリコントローラ３００は、「０」のビットがｎ／２を超えるか否かを判定すればよい。
【００８７】
ライトコマンドである場合には（ステップＳ９０３：Ｙｅｓ）、メモリコントローラ３００は、コントローラ側ライト処理を実行する（ステップＳ９１０）。そして、不揮発性メモリ４００は、ＮＶＲＡＭ側ライト処理を実行する（ステップＳ９２０）。
【００８８】
一方、リードコマンドである場合には（ステップＳ９０３：Ｎｏ）、メモリコントローラ３００は、コントローラ側リード処理を実行する（ステップＳ９５０）。そして、不揮発性メモリ４００は、データを読み出し、メモリコントローラ３００に転送する（ステップＳ９０４）。ステップＳ９２０またはＳ９０４の後、ストレージ２００は、ステップＳ９０２に戻る。
【００８９】
図１３は、第１の実施の形態におけるコントローラ側ライト処理の一例を示すフローチャートである。メモリコントローラ３００は、符号化対象データからｎビットの符号語を生成する（ステップＳ９１１）。メモリコントローラ３００は、符号語内の「１」のビット数がｎ／２より多いか否かを判断する（ステップＳ９１２）。
【００９０】
「１」のビット数がｎ／２より多い場合に（ステップＳ９１２：Ｙｅｓ）、メモリコントローラ３００は、符号語をライトデータとして不揮発性メモリ４００に出力する（ステップＳ９１３）。一方、「１」のビット数がｎ／２以下の場合に（ステップＳ９１２：Ｎｏ）、メモリコントローラ３００は、符号語の反転データをライトデータとして出力する（ステップＳ９１４）。ステップＳ９１２またはＳ９１４の後、メモリコントローラ３００は、コントローラ側ライト処理を終了する。
【００９１】
図１４は、第１の実施の形態におけるＮＶＲＡＭ側ライト処理の一例を示すフローチャートである。不揮発性メモリ４００は、ライトデータを取得する（ステップＳ９２１）。不揮発性メモリ４００は、書込み先のアドレスに書き込まれているデータを既書込みデータとしてプレリードする（ステップＳ９２２）。不揮発性メモリ４００は、ライトデータと、既書込みデータとにおいて対応するビットを比較し、リセットマスクデータを生成する（ステップＳ９２３）。このリセットマスクデータは、ライトデータにおいて「１」であり、かつ、既書込みデータにおいて「０」であるビットについてはリセットする旨を示し、それ以外のビットについてはマスクする旨を示す。
【００９２】
不揮発性メモリ４００は、リセットマスクデータによりリセットする旨が示されたビットのみを「０」から「１」に書き換える処理（リセット処理）を行う（ステップＳ９２４）。不揮発性メモリ４００は、リセット処理後の既書込みデータを読み出し、ベリファイエラーが生じたか否かを判断する（ステップＳ９２５）。
【００９３】
ベリファイエラーが生じなかった場合には（ステップＳ９２５：Ｎｏ）、不揮発性メモリ４００は、ライトデータと、リセット処理後の既書込みデータとにおいて対応するビットを比較し、セットマスクデータを生成する（ステップＳ９２６）。このセットマスクデータは、ライトデータまたは冗長データにおいて「０」であり、かつ、既書込みデータにおいて「１」であるビットについてはセットする旨を示し、それ以外のビットについてはマスクする旨を示す。
【００９４】
不揮発性メモリ４００は、セットマスクデータによりセットする旨が示されたビットのみを「１」から「０」に書き換える処理（セット処理）を行う（ステップＳ９２７）。不揮発性メモリ４００は、セット処理後の既書込みデータを読み出し、ベリファイエラーが生じたか否かを判断する（ステップＳ９２８）。
【００９５】
リセット処理においてエラーが発生した場合（ステップＳ９２５：Ｙｅｓ）、または、セット処理においてエラーが発生した場合（ステップＳ９２８：Ｙｅｓ）、不揮発性メモリ４００は、ライトエラーをホストコンピュータ１００に通知する（ステップＳ９２９）。セット処理においてエラーが発生していない場合（ステップＳ９２８：Ｎｏ）、または、ステップＳ９２９の後、不揮発性メモリ４００は、メモリコントローラ３００にステータスを転送する（ステップＳ９３０）。ステップＳ９３０の後、不揮発性メモリ４００は、ＮＶＲＡＭ側ライト処理を終了する。
【００９６】
図１５は、第１の実施の形態におけるコントローラ側リード処理の一例を示すフローチャートである。メモリコントローラ３００は、リードデータを反転してリード側反転データを生成する（ステップＳ９５１）。そして、メモリコントローラ３００は、リードデータおよびリード側反転データのそれぞれの誤り検出および誤り訂正を行う（ステップＳ９５２）。
【００９７】
メモリコントローラ３００は、リードデータのみ誤り訂正に成功したか否かを判断する（ステップＳ９５３）。リードデータのみ誤り訂正に成功した場合に（ステップＳ９５３：Ｙｅｓ）、メモリコントローラ３００は、訂正リードデータをホストコンピュータ１００へ出力する（ステップＳ９５４）。
【００９８】
リードデータのみ誤り訂正に成功したのではない場合に（ステップＳ９５３：Ｎｏ）、メモリコントローラ３００は、リード側反転データのみ誤り訂正に成功したか否かを判断する（ステップＳ９５５）。リード側反転データのみ誤り訂正に成功した場合に（ステップＳ９５５：Ｙｅｓ）、メモリコントローラ３００は、訂正反転データをホストコンピュータ１００へ出力する（ステップＳ９５６）。
【００９９】
リード側反転データのみ誤り訂正に成功したのではない場合に（ステップＳ９５５：Ｎｏ）、メモリコントローラ３００は、「１」のエラーフラグを生成してホストコンピュータ１００に出力する（ステップＳ９５７）。ステップＳ９５４、Ｓ９５６またはＳ９５７の後、メモリコントローラ３００は、コントローラ側リード処理を終了する。
【０１００】
このように、本技術の第１の実施の形態によれば、メモリコントローラ３００は、リードデータと反転データとの両方を誤り訂正し、訂正に成功した方の訂正データを出力するため、反転したか否かを示すビットをメモリに余分に保持する必要がなくなる。これにより、メモリの使用効率を向上させることができる。
【０１０１】
［第１の変形例］
第１の実施の形態では、メモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功した際にリードエラーと判断していたが、リードエラーと判断せずに一方の訂正データを出力してもよい。例えば、ライト処理部３１０が「１」のビット数がｎ／２より多ければ反転して書き込んでいた場合には、訂正リードデータＤｒおよび訂正反転データＤｒのうち、「１」のビットが多い方が正しいデータである可能性が高い。第１の変形例のメモリコントローラ３００は、訂正リードデータＤｒおよび訂正反転データＤｒの両方の誤り訂正に成功した際にリードエラーと判断せずに特定の値のビット数が多い方を出力する点において第１の実施の形態と異なる。
【０１０２】
図１６は、第１の実施の形態の第１の変形例におけるリード処理部３２０の一構成例を示すブロック図である。第１の変形例のリード処理部３２０は、特定ビット計数部３２３をさらに備える点において第１の実施の形態と異なる。
【０１０３】
特定ビット計数部３２３は、訂正リードデータＤｒおよび訂正反転データＤｒ’のそれぞれにおいて特定の値（例えば、「１」）のビット数を計数するものである。この特定ビット計数部３２３は、訂正リードデータＤｒの方が訂正反転データＤｒ’よりも「１」のビット数が多いか否かを示すビットを生成し、計数結果として訂正データ選択部３２２に供給する。
【０１０４】
第１の変形例の訂正データ選択部３２２は、リードデータおよびリード側反転データの両方の誤り訂正に成功し、訂正リードデータＤｒの方が訂正反転データＤｒ’よりも「１」のビット数が多い場合に、訂正リードデータＤｒを選択する。一方、訂正反転データＤｒ’の方が訂正リードデータＤｒよりも「１」のビット数が多い場合、または、それらのビット数が同じである場合、訂正データ選択部３２２は、訂正反転データＤｒ’を選択する。なお、訂正データ選択部３２２は、リードデータおよびリード側反転データの両方の誤り訂正に成功し、訂正リードデータＤｒおよび訂正リードデータＤｒ’の「１」のビット数が同じである場合にリードエラーと判断してもよい。
【０１０５】
図１７は、第１の実施の形態の第１の変形例におけるコントローラ側リード処理の一例を示すフローチャートである。第１の変形例のコントローラ側リード処理は、ステップＳ９５７を実行せず、ステップＳ９６１乃至Ｓ９６３をさらに実行する点において第１の実施の形態と異なる。
【０１０６】
リード側反転データのみ誤り訂正に成功したのではない場合に（ステップＳ９５５：Ｎｏ）、メモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功したか否かを判断する（ステップＳ９６１）。リードデータおよびリード側反転データの両方の誤り訂正に成功した場合に（ステップＳ９６１：Ｙｅｓ）、メモリコントローラ３００は、ＤｒおよびＤｒ’のうち「１」のビットが多い方をホストコンピュータ１００に出力する。また、「１」のビット数が同じであれば、必要に応じて、「１」のエラーフラグが生成される（ステップＳ９６２）。
【０１０７】
リードデータおよびリード側反転データの両方の誤り訂正に成功していない場合に（ステップＳ９６１：Ｎｏ）、メモリコントローラ３００は、「１」のエラーフラグを生成してホストコンピュータ１００に出力する。また、メモリコントローラ３００は、訂正前のリードデータおよびリード側反転データのうち「１」のビット数の多い方を必要に応じて、ホストコンピュータ１００に出力する（ステップＳ９６３）。ステップＳ９５４、Ｓ９５６、Ｓ９６２またはＳ９６３の後、メモリコントローラ３００は、コントローラ側リード処理を終了する。
【０１０８】
このように第１の変形例によれば、メモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功した際にリードエラーと判断せずに「１」のビットが多い方を出力するため、リードエラーの発生頻度を低減することができる。
【０１０９】
［第２の変形例］
第１の実施の形態では、メモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功した際にリードエラーと判断していたが、リードエラーと判断せずに一方の訂正データを出力してもよい。例えば、訂正したビット数が少ない方が、正しいデータである可能性が高い。第２の変形例のメモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功した際に訂正したビット数の少ない方を出力する点において第１の実施の形態と異なる。
【０１１０】
第２の変形例のリード処理部３２０は、第１の変形例と同様の構成である。ただし、第２の変形例の訂正データ選択部３２２は、リードデータおよびリード側反転データの両方の誤り訂正に成功した場合に、訂正リードデータＤｒおよび訂正反転データＤｒ’のそれぞれの訂正したビット数が同一であるか否かを判断する。訂正リードデータＤｒおよび訂正反転データＤｒ’のそれぞれの訂正したビット数が同一であれば、訂正データ選択部３２２は、それらのうち「１」のビット数が多い方を出力する。
【０１１１】
一方、訂正リードデータＤｒおよび訂正反転データＤｒ’のそれぞれの訂正したビット数が異なれば、訂正データ選択部３２２は、それらの訂正したビット数が少ない方を出力する。
【０１１２】
図１８は、第１の実施の形態の第２の変形例におけるコントローラ側リード処理の一例を示すフローチャートである。第２の変形例のコントローラ側リード処理は、ステップＳ９６２を実行せず、ステップＳ９６４乃至Ｓ９６６をさらに実行する点において第１の変形例と異なる。
【０１１３】
リードデータおよびリード側反転データの両方の誤り訂正に成功した場合に（ステップＳ９６１：Ｙｅｓ）、メモリコントローラ３００は、ＤｒおよびＤｒ’のそれぞれにおいて訂正したビット数が同一であるか否かを判断する（ステップＳ９６４）。訂正したビット数が同一である場合に（ステップＳ９６４：Ｙｅｓ）、メモリコントローラ３００は、ＤｒおよびＤｒ’のうち「１」のビットが多い方をホストコンピュータ１００に出力する（ステップＳ９６５）。一方、訂正したビット数が同一でない場合に（ステップＳ９６４：Ｎｏ）、メモリコントローラ３００は、訂正したビット数が少ない方をホストコンピュータ１００に出力する（ステップＳ９６６）。ステップＳ９５４、Ｓ９５６、Ｓ９６３、Ｓ９６５またはＳ９６６の後、メモリコントローラ３００は、コントローラ側リード処理を終了する。
【０１１４】
このように第２の変形例によれば、メモリコントローラ３００は、リードデータおよびリード側反転データの両方の誤り訂正に成功した際にリードエラーと判断せずに訂正ビット数が少ない方を出力するため、リードエラーの発生頻度を低減することができる。
【０１１５】
＜２．第２の実施の形態＞
第１の実施の形態では、リードデータおよびリード側反転データのそれぞれからシンドロームＳおよびＳ’を計算していたが、シンドロームＳに簡易な演算を行うことによりシンドロームＳ’を計算することができる。これにより、計算量を少なくすることができる。第２の実施の形態のメモリコントローラ３００は、シンドロームＳ’を簡易な演算により求める点において第１の実施の形態と異なる。
【０１１６】
図１９は、第２の実施の形態におけるリード処理部３２０の一構成例を示すブロック図である。第２の実施の形態のリード処理部３２０は、リード側反転部３９０を、反転データ誤り検出訂正部３６０の内部に設けた点において第１の実施の形態と異なる。
【０１１７】
また、第２の実施の形態のリードデータ誤り検出訂正部３４０は、シンドロームＳおよびリードデータを反転データ誤り検出訂正部３６０に供給する。また、第２の実施の形態の反転データ誤り検出訂正部３６０は、シンドロームＳからＳ’を計算し、そのシンドロームＳ’に基づいて反転データにおける誤りを訂正する。
【０１１８】
図２０は、第２の実施の形態におけるリードデータ誤り検出訂正部３４０および反転データ誤り検出訂正部３６０の一構成例を示すブロック図である。第２の実施の形態の反転データ誤り検出訂正部３６０は、シンドローム計算部３７０を備えず、反転補正部３８０およびリード側反転部３９０をさらに備える点において第１の実施の形態と異なる。
【０１１９】
まず、シンドロームＳからＳ’を計算する方法について説明するため、フルレングスのＢＣＨ符号を用いた場合について考える。この場合、符号語ｃ＊、誤りパターンｅ＊、および、受信語ｒ＊は、次の各式により表される。
【数１６】
0006540703.tif 000017
【数１７】
0006540703.tif 000018
【数１８】
0006540703.tif 000019
【０１２０】
式１８の受信語ｒ＊に対するシンドロームＳ＊は、次の式により表される。
【数１９】
0006540703.tif 000020
【０１２１】
ここで、短縮化符号は、フルレングス符号の一部であることと、フルレングス符号では符号語のビット反転がやはり符号語になることとから、次の関係式が導かれる。
【数２０】
0006540703.tif 000021
【数２１】
0006540703.tif 000022
上式において、オーバーバーを付したｃ＊およびｒ＊は、ｃ＊およびｒ＊を反転したベクトルを表す。
【０１２２】
式２０および式２１から、次の式が導かれる。
【数２２】
0006540703.tif 000023
上式において、Ｈとオーバーバー付きのｒとの積は、リード側反転データに対応するシンドロームＳ’に等しい。したがって、式２２から、シンドロームＳ’は、シンドロームＳに次の式で表される補正係数を加算したベクトルに該当することが導かれる。
【数２３】
0006540703.tif 000024
上式において、０番目からｎ−１番目までの「０」の部分は、符号語コーディネートを示し、ｎ番目からＮ−１番目までの「１」の部分は、短縮化されたコーディネートを示す。
【０１２３】
第２の実施の形態のシンドローム計算部３５０は、リードデータから計算したシンドロームＳを反転補正部３８０にさらに供給する。
【０１２４】
反転補正部３８０は、シンドロームＳに式２３の補正係数を加算してシンドロームＳ’を計算するものである。この反転補正部３８０は、計算したシンドロームＳ’を誤り位置計算部３６１および誤り位置訂正部３６２に供給する。
【０１２５】
第２の実施の形態の誤り位置訂正部３６２は、リードデータにおいて、誤りを訂正し、訂正後のリードデータをリード側反転部３９０に供給する。第２の実施の形態のリード側反転部３９０は、誤り位置訂正部３６２からのデータを反転して、訂正反転データＤｒ’として出力する。
【０１２６】
なお、第２の実施の形態の誤り位置訂正部３４２は、特許請求の範囲に記載の非反転側誤り位置訂正部の一例である。また、第２の実施の形態の誤り位置訂正部３６２は、特許請求の範囲に記載の反転側誤り位置訂正部の一例である。
【０１２７】
また、第２の実施の形態における反転補正方法は、任意の有限体の次数、訂正数、短縮化符号長で定義したＢＣＨ符号に適用することができる。
【０１２８】
図２１は、第２の実施の形態における反転補正部３８０の一構成例を示すブロック図である。この反転補正部３８０は、ｔ個の加算器３８１を備える。
【０１２９】
ｔ番目の加算器３８１は、シンドロームの成分Ｓｉに、式２３の補正係数ｕｉを加算して、シンドロームＳ’におけるＳｉ’として出力する。
【０１３０】
このように第２の実施の形態によれば、メモリコントローラ３００は、補正係数の加算という簡易な演算によりシンドロームＳからシンドロームＳ’を算出するため、計算量を少なくすることができる。
【０１３１】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１３２】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disc）、メモリカード、ブルーレイディスク（Blu-ray（登録商標）Disc）等を用いることができる。
【０１３３】
なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【０１３４】
なお、本技術は以下のような構成もとることができる。
（１）誤り検出訂正符号における符号語を符号化対象データから生成する符号語生成部と、
前記符号語を反転したデータと前記符号語との一方をライトデータとして前記メモリセルに書き込むライト制御部と、
前記ライトデータを前記メモリセルからリードデータとして読み出して前記リードデータにおける誤りを訂正するリードデータ誤り訂正部と、
前記リードデータを反転した反転データにおける誤りを訂正する反転データ誤り訂正部と、
前記リードデータおよび前記反転データのうち一方のデータのみにおいて前記誤りの数が前記誤り検出訂正符号の訂正能力を超えない場合には前記誤りが訂正された前記一方のデータを選択して訂正データとして出力する訂正データ出力部と
を具備するメモリコントローラ。
（２）前記リードデータ誤り訂正部は、
前記リードデータおよび所定の検査行列の積をシンドロームとして計算する非反転側シンドローム計算部と、
前記シンドロームから前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正する非反転側誤り位置訂正部と
を備え、
前記反転データ誤り訂正部は、
前記反転データおよび前記所定の検査行列の積と前記シンドロームとの差である補正係数の加算により前記シンドロームを補正する反転補正部と、
前記補正されたシンドロームから前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正する反転側誤り位置訂正部と
前記反転側誤り位置訂正部により前記誤りが訂正された前記リードデータを反転する反転部と
を備える前記（１）記載のメモリコントローラ。
（３）前記リードデータ誤り訂正部は、前記リードデータおよび所定の検査行列の積から前記誤りの位置を検出して前記リードデータにおいて前記検出した位置の誤りを訂正し、
前記反転データ誤り訂正部は、前記反転データおよび所定の検査行列の積から前記誤りの位置を検出して前記反転データにおいて前記検出した位置の誤りを訂正する
前記（１）から（２）のいずれかに記載のメモリコントローラ。
（４）前記ライト制御部は、前記符号語を反転したデータと前記符号語とのうち前記メモリセルに書き込むときの消費電力の低い方を前記ライトデータとして書き込む
前記（１）から（３）のいずれかに記載のメモリコントローラ。
（５）前記ライト制御部は、前記符号語において特定の値のビット数が前記符号語の総ビット数の半数より多い場合には前記符号語を前記ライトデータとして書き込み、前記特定の値のビット数が前記総ビット数の半数を超えない場合には前記符号語を反転したデータを前記ライトデータとして書き込む
前記（４）記載のメモリコントローラ。
（６）前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えない場合には前記誤りが訂正された訂正リードデータと前記誤りが訂正された訂正反転データとのうち前記特定の値のビット数が多い方を前記訂正データとして出力する
前記（５）記載のメモリコントローラ。
（７）前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えない場合には前記誤りが訂正された訂正リードデータと前記誤りが訂正された訂正反転データとのうち前記訂正された誤りが少ない方を前記訂正データとして出力する
前記（５）記載のメモリコントローラ。
（８）前記リードデータおよび前記反転データの両方において前記誤りの数が前記訂正能力を超えず、かつ、前記訂正リードデータおよび前記訂正反転データのそれぞれにおいて訂正された前記誤りの数が同じである場合には前記訂正リードデータおよび前記訂正反転データのうち前記特定の値のビット数が多い方を前記訂正データとして出力する
前記（７）記載のメモリコントローラ。
（９）符号語生成部が、誤り検出訂正符号における符号語を符号化対象データから生成する符号語生成手順と、
ライト処理部が、前記符号語を反転したデータと前記符号語との一方をライトデータとして前記メモリセルに書き込むライト制御手順と、
リードデータ誤り訂正部が、前記ライトデータを前記メモリセルからリードデータとして読み出して前記リードデータにおける誤りを訂正するリードデータ誤り訂正手順と、
反転データ誤り訂正部が、前記リードデータを反転した反転データにおける誤りを訂正する反転データ誤り訂正手順と、
訂正データ出力部が、前記リードデータおよび前記反転データのうち一方のデータのみにおいて前記誤りの数が前記誤り検出訂正符号の訂正能力を超えない場合には前記誤りが訂正された前記一方のデータを選択して訂正データとして出力する訂正データ出力手順と
を具備するメモリコントローラの制御方法。
【符号の説明】
【０１３５】
１００  ホストコンピュータ
２００  ストレージ
３００  メモリコントローラ
３０１  ホストインターフェース
３０２  ＲＡＭ
３０３  ＣＰＵ
３０４  ＥＣＣ処理部
３０５  ＲＯＭ
３０６  バス
３０７  メモリインターフェース
３１０  ライト処理部
３１１  符号化部
３１２  反転判定部
３１３  ライト側反転部
３１４、３２１  セレクタ
３２０  リード処理部
３２２  訂正データ選択部
３２３  特定ビット計数部
３３０  誤り検出訂正部
３４０  リードデータ誤り検出訂正部
３４１、３６１  誤り位置計算部
３４２、３６２  誤り位置訂正部
３５０、３７０  シンドローム計算部
３５１  シンドローム成分計算部
３５２  成分出力制御部
３５３  スイッチ
３６０  反転データ誤り検出訂正部
３８０  反転補正部
３８１  加算器
３９０  リード側反転部
４００  不揮発性メモリ
４１０  データバッファ
４２０  メモリセルアレイ
４３０  ドライバ
４４０  アドレスデコーダ
４５０  バス
４６０  制御インターフェース
４７０  メモリ制御部
【図１】
0006540703.tif 000025
【図２】
0006540703.tif 000026
【図３】
0006540703.tif 000027
【図４】
0006540703.tif 000028
【図５】
0006540703.tif 000029
【図６】
0006540703.tif 000030
【図７】
0006540703.tif 000031
【図８】
0006540703.tif 000032
【図９】
0006540703.tif 000033
【図１０】
0006540703.tif 000034
【図１１】
0006540703.tif 000035
【図１２】
0006540703.tif 000036
【図１３】
0006540703.tif 000037
【図１４】
0006540703.tif 000038
【図１５】
0006540703.tif 000039
【図１６】
0006540703.tif 000040
【図１７】
0006540703.tif 000041
【図１８】
0006540703.tif 000042
【図１９】
0006540703.tif 000043
【図２０】
0006540703.tif 000044
【図２１】
0006540703.tif 000045