(57)【要約】【課題】データの誤りを正確かつ高速に訂正する。【解決手段】誤り検出訂正装置は、第１符号誤り検出部および第２符号誤り訂正部を備える。第１符号誤り検出部は、複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において第１符号語の各々に誤りがあるか否かを検出する。第２符号誤り訂正部は、第２符号語を複数の部分データからなる符号語として誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて誤りを訂正する。【選択図】図３
2014154899.tif 000002
【特許請求の範囲】
【請求項１】
複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、
前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む前記部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正部と
を具備する誤り検出訂正装置。
【請求項２】
前記複数の部分データは、隣り合う部分データの一部のデータが共通の符号語であり、
前記第２符号誤り訂正部は、前記誤りが検出された第１符号語を含む前記部分データにおいて前記隣接部分データと共通の前記一部のデータに基づいて前記誤りを訂正する
請求項１記載の誤り検出訂正装置。
【請求項３】
前記第２符号誤り訂正部は、前記隣接部分データの誤りを訂正し、前記隣接部分データの誤り訂正が成功した場合には前記第１符号誤り検出部により検出された前記誤りを前記隣接部分データに基づいて訂正する
請求項１記載の誤り検出訂正装置。
【請求項４】
前記第２符号誤り訂正部は、前記隣接部分データの誤り訂正が失敗した場合には前記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データの誤りを訂正して前記新たな隣接部分データの誤り訂正が成功したか否かを判断する
請求項３記載の誤り検出訂正装置。
【請求項５】
前記第２符号誤り訂正部は、前記隣接部分データに含まれる前記第１符号語に誤りが検出されていない場合には前記第１符号誤り検出部により検出された前記誤りを前記隣接部分データに基づいて訂正し、前記隣接部分データに含まれる前記第１符号語に誤りが検出されている場合には前記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データに含まれる前記第１符号語に誤りが検出されているか否かを判断する
請求項３記載の誤り検出訂正装置。
【請求項６】
前記第２符号誤り訂正部は、前記隣接部分データの誤り訂正が失敗した場合には前記第２符号語の誤りを訂正する
請求項３記載の誤り検出訂正装置。
【請求項７】
前記第２符号誤り訂正部は、前記隣接部分データに基づいて行った前記誤りの訂正が成功したか否かを判断し、当該訂正が失敗した場合には各々が前記第１符号語を含む第３符号語に基づいて前記誤りを訂正する
請求項１記載の誤り検出装置。
【請求項８】
前記第２符号語は畳込み符号語であり、
前記第２符号誤り訂正部は、前記隣接部分データにおいて畳込み演算が行われた結果に基づいて前記誤りを訂正する
請求項１記載の誤り検出訂正装置。
【請求項９】
前記第２符号語はターボ符号語である
請求項８記載の誤り検出訂正装置。
【請求項１０】
前記第２符号誤り訂正部は、前記誤りが検出された第１符号語を含む前記部分データと前記隣接部分データとを１つの復号単位として前記誤りを訂正する
請求項１記載の誤り検出訂正装置。
【請求項１１】
前記複数の部分データは、部分データの各々の誤りを訂正するための第２パリティと、当該第２パリティの誤りを訂正するための第１パリティとを含み、
前記第２符号訂正部は、前記第１パリティを使用して前記第２パリティの誤りを訂正し、前記訂正した第２パリティを使用して前記部分データの誤りを訂正する
請求項１記載の誤り検出訂正装置。
【請求項１２】
前記複数の部分データの各々は、複数の前記第１符号語を含む
請求項１記載の誤り検出訂正装置。
【請求項１３】
複数の第１符号語を連鎖的に符号化することにより第２符号語を生成する第２符号化部と、
前記第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、
前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正部と
を具備する情報処理装置。
【請求項１４】
第１符号誤り検出部が、複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出手順と、
第２符号誤り訂正部が、前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正手順と
を具備する誤り検出訂正方法。
【請求項１５】
第１符号誤り検出部が、複数の第１符号語を連鎖的に符号化することにより生成された複数の第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出手順と、
第２符号誤り訂正部が、前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正手順と
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、誤り検出訂正装置、誤り検出訂正方法および情報処理装置ならびに当該誤り検出訂正装置における誤り検出訂正方法をコンピュータに実行させるためのプログラムに関する。詳しくは、複数の種類の符号化方式を使用する誤り検出訂正装置、誤り検出訂正方法および情報処理装置ならびに当該誤り検出訂正装置における誤り検出訂正方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
光磁気記録ディスク、ハードディスク、不揮発性メモリなどのデータ記録再生装置に記録されたデータを再生するときにおいては、その装置の破損や熱雑音などのために記録したデータが破損して正しく読み出せないことがある。このようなデータの破損に対処するために、データ記録装置は、記録する対象のデータを誤り検出訂正符号（ＥＣＣ：Error detection and Correction Code）に符号化して記録することが多い。データ記録装置は、データの再生時に、このＥＣＣを使用してデータにおける誤りの検出および訂正を行うことができる。
【０００３】
符号化においては、誤り訂正能力を向上させるために、複数の符号化方式が使用されることがある。例えば、複数のデータの各々をブロック符号語に符号化し、それらのブロック符号語のそれぞれを畳込み符号語に符号化して記録する不揮発性メモリが提案されている（例えば、特許文献１参照。）。この不揮発性メモリは、ブロック符号語の各々の誤り訂正を行い、いずれかのブロック符号語の誤り訂正に失敗した場合には、その失敗したブロック符号語を含む畳込み符号語を復号することによりデータの誤りを確実に訂正する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２８７３０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の従来技術では、データの誤り訂正に時間がかかるおそれがある。上述の不揮発性メモリでは、複数のブロック符号語をインタリーブした系列を符号化対象として畳込み符号化を行っている。このようにインタリーブした系列に対して畳込み符号化しているため、１つのブロック符号語を復号する前に、全ての畳込み符号語を対象とした復号を行う必要がある。したがって、上述の不揮発性メモリでは、データを確実に訂正するには、１つのブロック符号語の訂正に失敗した場合であっても全ての畳込み符号語を訂正する必要がある。このため、データの誤り訂正に時間がかかり、データの誤りを正確かつ高速に訂正することが困難であるという問題がある。
【０００６】
本技術はこのような状況に鑑みて生み出されたものであり、データの誤りを正確かつ高速に訂正することを目的とする。
【課題を解決するための手段】
【０００７】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において上記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、上記第２符号語を複数の部分データからなる符号語として上記誤りが検出された第１符号語を含む上記部分データに隣接する部分データである隣接部分データに基づいて上記誤りを訂正する第２符号誤り訂正部とを具備する誤り検出訂正装置、および、当該装置における誤り検出訂正方法、ならびに、当該方法を実行させるためのプログラムである。これにより、隣接部分データに基づいて誤りが訂正されるという作用をもたらす。
【０００８】
また、この第１の側面において、上記複数の部分データは、隣り合う部分データの一部のデータが共通の符号語であり、上記第２符号誤り訂正部は、上記誤りが検出された第１符号語を含む上記部分データにおいて上記隣接部分データと共通の上記一部のデータに基づいて上記誤りを訂正してもよい。これにより、隣接部分データと共通の一部のデータに基づいて誤りが訂正されるという作用をもたらす。
【０００９】
また、この第１の側面において、上記第２符号誤り訂正部は、上記隣接部分データの誤りを訂正し、上記隣接部分データの誤り訂正が成功した場合には上記第１符号誤り検出部により検出された上記誤りを上記隣接部分データに基づいて訂正してもよい。これにより、隣接部分データの誤り訂正が成功した場合に誤りが隣接部分データに基づいて訂正されるという作用をもたらす。
【００１０】
また、この第１の側面において、上記第２符号誤り訂正部は、上記隣接部分データの誤り訂正が失敗した場合には上記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データの誤りを訂正して上記新たな隣接部分データの誤り訂正が成功したか否かを判断してもよい。これにより、隣接部分データの誤り訂正が失敗した場合には隣接部分データに隣接する部分データが新たな隣接部分データとされるという作用をもたらす。
【００１１】
また、この第１の側面において、上記第２符号誤り訂正部は、上記隣接部分データに含まれる上記第１符号語に誤りが検出されていない場合には上記第１符号誤り検出部により検出された上記誤りを上記隣接部分データに基づいて訂正し、上記隣接部分データに含まれる上記第１符号語に誤りが検出されている場合には上記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データに含まれる上記第１符号語に誤りが検出されているか否かを判断してもよい。これにより、隣接部分データに含まれる第１符号語に誤りが検出されている場合には隣接部分データに隣接する部分データが新たな上記隣接部分データとされるという作用をもたらす。
【００１２】
また、この第１の側面において、上記第２符号誤り訂正部は、上記隣接部分データの誤り訂正が失敗した場合には上記第２符号語の誤りを訂正してもよい。これにより、隣接部分データの誤り訂正が失敗した場合には第２符号語の誤りが訂正されるという作用をもたらす。
【００１３】
上記第２符号誤り訂正部は、上記隣接部分データに基づいて行った上記誤りの訂正が成功したか否かを判断し、当該訂正が失敗した場合には各々が上記第１符号語を含む第３符号語に基づいて上記誤りを訂正してもよい。これにより、隣接部分データに基づいて行った誤りの訂正が失敗した場合には第１符号語を含む第３符号語に基づいて誤りが訂正されるという作用をもたらす。
【００１４】
また、この第１の側面において、上記第２符号語は畳込み符号語であり、上記第２符号誤り訂正部は、上記隣接部分データにおいて畳込み演算が行われた結果に基づいて上記誤りを訂正してもよい。これにより、隣接部分データにおいて畳込み演算が行われた結果に基づいて誤りが訂正されるという作用をもたらす。
【００１５】
また、この第１の側面において、上記第２符号語はターボ符号語であってもよい。これにより、ターボ符号語において誤りが訂正されるという作用をもたらす。
【００１６】
また、この第１の側面において、上記第２符号誤り訂正部は、上記誤りが検出された第１符号語を含む上記部分データと上記隣接部分データとを１つの復号単位として上記誤りを訂正してもよい。これにより、上記誤りが検出された第１符号語を含む上記部分データと上記隣接部分データとを１つの復号単位として誤りが訂正されるという作用をもたらす。
【００１７】
また、この第１の側面において、上記複数の部分データは、部分データの各々の誤りを訂正するための第２パリティと、当該第２パリティの誤りを訂正するための第１パリティとを含み、上記第２符号訂正部は、上記第１パリティを使用して上記第２パリティの誤りを訂正し、上記訂正した第２パリティを使用して上記部分データの誤りを訂正してもよい。これにより、第１パリティを使用して訂正された第２パリティを使用して部分データの誤りが訂正されるという作用をもたらす。
【００１８】
また、この第１の側面において、上記複数の部分データの各々は、複数の上記第１符号語を含むものであってもよい。これにより、複数のブロック符号語を含む部分データにおいて誤りが訂正されるという作用をもたらす。
【００１９】
また、本技術の第２の側面は、複数の第１符号語を連鎖的に符号化することにより第２符号語を生成する第２符号化部と、上記第２符号語において上記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、上記第２符号語を複数の部分データからなる符号語として上記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて上記誤りを訂正する第２符号誤り訂正部とを具備する情報処理装置である。これにより、隣接部分データに基づいて誤りが訂正されるという作用をもたらす。
【発明の効果】
【００２０】
本技術によれば、誤り検出訂正装置が、データを正確かつ高速に訂正することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２１】
【図１】第１の実施の形態における情報処理システムの一構成例を示すブロック図である。
【図２】第１の実施の形態におけるメモリコントローラの一構成例を示すブロック図である。
【図３】第１の実施の形態におけるＥＣＣ処理部の一構成例を示すブロック図である。
【図４】第１の実施の形態におけるブロック符号化を説明するための図である。
【図５】第１の実施の形態における第２符号化部の一構成例を示すブロック図である。
【図６】第１の実施の形態における正則検査行列の一例を示す図である。
【図７】第１の実施の形態における帯行列の一例である。
【図８】第１の実施の形態における生成行列の使用方法を説明するための図である。
【図９】第１の実施の形態における第２符号内のデータの依存関係の一例を説明するための図である。
【図１０】第１の実施の形態における第２符号のデータ構成の一例を示す図である。
【図１１】第１の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【図１２】第１の実施の形態における第２符号誤り検出訂正器の一構成例を示すブロック図である。
【図１３】第１の実施の形態における変数ノードと検査ノードとの間のメッセージ交換の一例を示す図である。
【図１４】第１の実施の形態における第２符号の訂正方法を説明するための図である。
【図１５】第１の実施の形態におけるメモリコントローラの動作の一例を示すフローチャートである。
【図１６】第１の実施の形態における符号化処理の一例を示すフローチャートである。
【図１７】第１の実施の形態における復号処理の一例を示すフローチャートである。
【図１８】第１の実施の形態における第２符号誤り検出訂正処理の一例を示すフローチャートである。
【図１９】第１の実施の形態の第１の変形例における第２符号のデータ構成の一例を示す図である。
【図２０】第１の実施の形態の第２の変形例における第２符号語のデータ構成の一例を説明するための図である。
【図２１】第１の実施の形態の第３の変形例における第２符号語のデータ構成の例を説明するための図である。
【図２２】第１の実施の形態の第５の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。
【図２３】第１の実施の形態の第５の変形例における第２符号の訂正法を説明するための図である。
【図２４】第２の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【図２５】第２の実施の形態における第２符号誤り検出訂正処理の一例を示すフローチャートである。
【図２６】第２の実施の形態における第２符号の訂正法を説明するための図である。
【図２７】第２の実施の形態の第１の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。
【図２８】第２の実施の形態の第１の変形例における第２符号の訂正方法を説明するための図である。
【図２９】第２の実施の形態の第２の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。
【図３０】第３の実施の形態における第２符号化部の一構成例を示すブロック図である。
【図３１】第３の実施の形態における第２符号化器の状態遷移の一例を示す状態遷移図である。
【図３２】第３の実施の形態における第２符号の生成方法の一例を説明するための図である。
【図３３】第３の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【図３４】第３の実施の形態における第２符号化部の状態遷移の一例を示すトレリス線図の一例である。
【図３５】第４の実施の形態における第２符号化部の一構成例を示すブロック図である。
【図３６】第４の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【図３７】第５の実施の形態における第２符号化部の一構成例を示すブロック図である。
【図３８】第５の実施の形態における第２符号のデータ構成の一例を示す図である。
【図３９】第５の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【図４０】第６の実施の形態における第２符号化部の一構成例を示すブロック図である。
【図４１】第６の実施の形態における検査行列の一例である。
【図４２】第６の実施の形態における第２符号誤り検出訂正部の一構成例を示すブロック図である。
【発明を実施するための形態】
【００２２】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（隣接する部分データに基づいて誤り訂正を行う例）
２．第２の実施の形態（訂正に成功するまで辿った隣接する部分データに基づいて誤り訂正を行う例）
３．第３の実施の形態（畳込み符号語を第２符号語として使用し、隣接する部分データに基づいて誤り訂正を行う例）
４．第４の実施の形態（ターボ符号語を第２符号語として使用し、隣接する部分データに基づいて誤り訂正を行う例）
５．第５の実施の形態（隣接する部分データにおいて訂正したパリティに基づいて誤り訂正を行う例）
６．第６の実施の形態（隣接する部分データに基づいて行った誤り訂正失敗時に第３符号語に基づいて誤り訂正を行う例）
【００２３】
＜１．第１の実施の形態＞
［情報処理システムの構成例］
図１は、第１の実施の形態における情報処理システムの一構成例を示すブロック図である。この情報処理システムは、ホストシステム１００およびストレージシステム２００を備える。
【００２４】
ホストシステム１００は、情報処理システム全体を制御するものである。具体的には、ホストシステム１００は、コマンドおよびデータを生成してストレージシステム２００に信号線１０９を介して供給する。また、ホストシステム１００は、ストレージシステム２００からデータを受け取る。ここで、コマンドは、ストレージシステム２００を制御するためのものであり、例えば、データのライト処理を指示するライトコマンドや、データのリード処理を指示するリードコマンドを含む。
【００２５】
ストレージシステム２００は、メモリコントローラ３００および不揮発性メモリ６００を備える。このメモリコントローラ３００は、不揮発性メモリ６００を制御するものである。メモリコントローラ３００は、ホストシステム１００からライトコマンドおよびライトデータを受け取った場合には、そのライトデータからＥＣＣを生成する。具体的には、メモリコントローラ３００は、ライトデータを、ライトデータおよびパリティからなるＥＣＣに変換（すなわち、符号化）する。メモリコントローラ３００は、不揮発性メモリ６００に信号線３０９を介してアクセスして符号化したデータを書き込む。
【００２６】
また、ホストシステム１００からリードコマンドを受け取った場合、メモリコントローラ３００は、不揮発性メモリ６００に信号線３０９を介してアクセスして符号化されたデータを読み出す。そして、メモリコントローラ３００は、符号化されたデータを、符号化前の元のデータに変換（すなわち、復号）する。この復号において、メモリコントローラ３００は、ＥＣＣに基づいてデータにおけるエラーの検出および訂正を行う。メモリコントローラ３００は、訂正したデータをホストシステム１００に供給する。
【００２７】
不揮発性メモリ６００は、メモリコントローラ３００の制御に従って、データを記憶するものである。
【００２８】
［メモリコントローラの構成例］
図２は、第１の実施の形態におけるメモリコントローラ３００の一構成例を示すブロック図である。このメモリコントローラ３００は、ホストインターフェース３１０、ＲＡＭ（Random Access Memory）３２０、ＣＰＵ（Central Processing Unit）３３０、ＲＯＭ（Read Only Memory）３４０、不揮発性メモリインターフェース３５０およびバス３６０を備える。また、メモリコントローラ３００は、ＥＣＣ処理部４００を備える。
【００２９】
ホストインターフェース３１０は、ホストシステム１００との間でデータやコマンドを相互に交換するものである。ＲＡＭ３２０は、ＣＰＵ３３０が実行する処理において必要となるデータを一時的に保持するものである。ＣＰＵ３３０は、メモリコントローラ３００全体を制御するものである。ＲＯＭ３４０は、ＣＰＵ３３０が実行するプログラム等を記憶するものである。不揮発性メモリインターフェース３５０は、不揮発性メモリ６００との間でデータやコマンドを相互に交換するものである。バス３６０は、ホストインターフェース３１０、ＲＡＭ３２０、ＣＰＵ３３０、ＲＯＭ３４０、不揮発性メモリインターフェース３５０およびＥＣＣ処理部４００が相互にデータを交換するための共通の経路である。
【００３０】
ＥＣＣ処理部４００は、ライトデータを符号化し、また、リードデータを復号するものである。ライトデータの符号化においてＥＣＣ処理部４００は、複数のライトデータの各々をブロック符号化対象データとして、そのブロック符号化対象データにパリティを付加することにより所定の単位でブロック符号に符号化する。所定の単位でブロック符号化された個々のデータを以下、「第１符号語」と称する。そして、ＥＣＣ処理部４００は、第１符号語の各々を所定の単位で連鎖的に符号化する。連鎖的に符号化されたデータを以下、「第２符号語」と称する。なお、ＥＣＣ処理部４００は、特許請求の範囲に記載の誤り訂正検出装置の一例である。
【００３１】
ここで、「連鎖的に符号化する」とは、一定の順序に従って、今回より前のデータより得られた状態と今回のデータとを用いて符号化することにより、複数のデータを順に符号化することをいう。符号化の順序は、データを受信ないし生成した時刻や、データが記録されているアドレスの値などにより決定される。また、第２符号語は、第１符号語と、第２符号語の誤りを検出および訂正するためのパリティとを含む。つまり、ＥＣＣ処理部４００が生成するＥＣＣは、第１符号語および第２符号語を含む。以下、第１符号語を検査するためのパリティを「第１パリティ」と称し、第２符号語を検査するためのパリティを「第２パリティ」と称する。
【００３２】
ＥＣＣ処理部４００は、符号化したライトデータを不揮発性メモリ６００にバス３６０を介して供給する。
【００３３】
符号化されたリードデータが読み出されると、ＥＣＣ処理部４００は、第１パリティを使用して、第１符号語の誤りを検出および訂正する。第１符号語の誤りの訂正に失敗した場合には、ＥＣＣ処理部４００は、第２パリティを使用して第２符号語を訂正することにより、訂正に失敗した第１符号語の誤りを訂正する。ＥＣＣ処理部４００は、訂正した第１符号語を、バス３６０を介してホストシステム１００に供給する。
【００３４】
［ＥＣＣ処理部の構成例］
図３は、第１の実施の形態におけるＥＣＣ処理部４００の一構成例を示すブロック図である。このＥＣＣ処理部４００は、第１符号化部４１０、第２符号化部４２０、符号化データバッファ４６０および符号化データ供給部４７０を備える。また、ＥＣＣ処理部４００は、第１符号誤り検出訂正部５２０、第２符号誤り検出訂正部５３０、復号データバッファ５７０および復号データ供給部５８０を備える。
【００３５】
第１符号化部４１０は、複数のライトデータの各々を第１符号化対象データとして、その符号化対象データを第１符号語に符号化するものである。この第１符号化においては、例えば、２元のＢＣＨ（Bose Chaudhuri Hocquenghem）符号が第１符号として用いられる。第１符号化部４１０は、符号化により生成した第１符号語を第２符号化部４２０に信号線４１９を介して供給する。
【００３６】
なお、第１符号化部４１０は、誤りを検出および訂正することができるＢＣＨ符号を第１符号として使用しているが、第１符号は誤り検出能力をもつ符号であればＢＣＨ符号に限定されない。例えば、第１符号は、誤り訂正能力を持たないパリティビットを含む符号や、ハミング符号またはＲＳ（Reed-Solomon）符号であってもよい。また、第１符号化部４１０は、２元より高い次元の符号を第１符号として用いてもよい。
【００３７】
第２符号化部４２０は、第１符号語を第２符号語に符号化するものである。具体的には、第２符号化部４２０は、空間結合ＬＤＰＣ符号化方式により、複数の第１符号語を第２符号語に符号化する。復号においては、第２符号語の全体または一部の誤りが訂正される。第２符号語を部分的に復号する際の各々の部分を以下、「部分データ」と称する。
【００３８】
符号化データバッファ４６０は、第２符号語に符号化されたデータを保持するものである。符号化データ供給部４７０は、第２符号語を符号化データバッファ４６０から読み出してバス３６０に供給するものである。
【００３９】
第１符号誤り検出訂正部５２０は、第１符号語の誤りを検出および訂正するものである。第１符号誤り検出訂正部５２０は、例えば、第１符号語のシンボルの各々の値を「１」または「０」に一意に決定する硬判定復号法を使用して誤りを訂正する。ここで、シンボルは、符号語を構成する最小単位であり、例えば、１ビットである。第１符号誤り検出訂正部５２０は、第１誤り訂正符号の復号を行い、復号した第１符号語を第２符号誤り検出訂正部５３０に出力するとともに復号データバッファ５７０に保持させる。また、第１符号誤り検出訂正部５２０は、誤りの訂正に失敗し、誤りの検出のみが可能であった第１符号語があれば、その第１符号語を通知する誤り検出通知をＣＰＵ３３０にバス３６０を介して出力する。ＥＣＣ処理部４００が誤り検出通知において、誤りであることを通知すると、ＣＰＵ３３０は第２パリティの一部(復号を試みた第１符号語と共に部分データを構成するための第２パリティ)を読み出して、第２誤り検出訂正部に入力する。
【００４０】
なお、第１符号誤り検出訂正部５２０は、特許請求の範囲に記載の第１符号誤り検出部の一例である。
【００４１】
また、第１符号誤り検出訂正部５２０は、硬判定復号法により第１符号の誤りを訂正しているが、シンボルの各々の値の尤もらしさ（対数尤度比など）を求める軟判定復号法により誤りを訂正してもよい。例えば、「Makiko Kan, et al., Hardware Implementation of Soft-Decision Decoding for Reed-Solomon Code, 2008 5th International Symposium on Turbo Codes and Related Topics」に記載の方法を使用すればよい。この文献において装置は、ＲＳ符号などの第１符号の各々のシンボルの尤もらしさ（対数尤度比など）に基づいて、サムプロダクトアルゴリズムなどの確率伝播法によりデータの誤りを訂正する。この文献では、検査行列の対角化が行われているが、本発明に適用する場合には、対角化は必要ではない。第１符号の誤り訂正にも軟判定復号法を使用することにより、誤り訂正能力が向上する。
【００４２】
第２符号誤り検出訂正部５３０は、第１符号誤り検出訂正部５２０において誤りが検出された訂正対象の部分データに隣接する部分データの少なくとも一方に基づいて、その訂正対象の部分データの誤りを訂正するものである。ここで、部分データＡが部分データＢに「隣接する」とは、符号化の順序において、部分データＡが、部分データＢの直前または直後に生成されたことを意味する。隣接する部分データを、以下、「隣接部分データ」と称する。第２符号誤り検出訂正部５３０は、第２パリティが入力されると、第１符号誤り検出訂正部５２０により復号された第１符号語と、その第２パリティとからなる部分データを生成する。第２符号誤り検出訂正部５３０は、例えば、軟判定復号法を使用して部分データの誤りを訂正する。誤りの訂正方法の詳細については後述する。第２符号誤り検出訂正部５３０は、誤りを訂正した部分データを第１符号語誤り検出訂正部５２０に信号線５３９を介して出力する。第１符号誤り検出訂正部５２０は、その部分データ内の第１符号語を復号データバッファ５７０に保持させる。
【００４３】
なお、第２符号誤り検出訂正部５３０は、特許請求の範囲に記載の第２符号誤り訂正部の一例である。
【００４４】
復号データバッファ５７０は、復号された第１符号語を保持するものである。復号データ供給部５８０は、復号データバッファ５７０から誤りが訂正された第１符号語を読み出して、第１符号化対象データに相当する復号データをバス３６０へ供給するものである。
【００４５】
図４は、第１の実施の形態における第１符号化を説明するための図である。図４に示すように、第１符号化部４１０は、Ｋｆビットの第１符号化対象データの各々をＮｆビットの第１符号語に符号化する。ここで、Ｋｆは整数であり、Ｎｆは、Ｋｆより大きな整数である。それぞれの第１符号語は、Ｋｆビットの第１符号化対象データと、Ｎｆ−Ｋｆビットの第１パリティとを含む。このように、符号語が、符号化対象データをそのまま含み、符号化対象データとパリティとに符号語を容易に分離することができる符号は、組織符号と呼ばれる。なお、第１符号は非組織符号であってもよい。
【００４６】
［第２符号化部の構成例］
図５は、第１の実施の形態における第２符号化部４２０の一構成例を示すブロック図である。この第２符号化部４２０は、第２符号化対象データ生成部４２１および第２符号化器４２３を備える。
【００４７】
第２符号化対象データ生成部４２１は、第１符号化部４１０からの複数の第１符号をまとめて第２符号化対象データとして第２符号化器４２３に供給するものである。
【００４８】
第２符号化器４２２は、第２符号化対象データを第２符号語に符号化するものである。第２符号への符号化においては、例えば、２元の空間結合ＬＤＰＣ（低密度パリティ検査：Low Density Parity Check）符号にデータを符号化する符号化方式が用いられる。空間結合ＬＤＰＣ符号への符号化方法の詳細については、図６乃至図８などを参照して後述する。
【００４９】
ここでは生成行列は第２符号化器４２２が保持しているものとするが、第２符号化器４２２が検査行列から生成行列を生成することもできる。ここで、検査行列は、第２符号に対してパリティ検査を行う処理において用いられる行列であり、生成行列は、符号化対象のデータを符号化するために用いられる行列である。生成行列は、例えば、次の式１により検査行列から求められる。
【数１】
2014154899.tif 000003
式１において、「Ｇ」は、生成行列であり、「ＨＴ」は検査行列Ｈを転置した行列である。
【００５０】
第２符号化器４２３は、式１により得られた生成行列と第２符号化対象データとの積を求める。第２符号化器４２３は、得られた積は第２符号語として符号化データバッファ４６０に信号線４２８を介して出力する。
【００５１】
なお、第２符号は、複数のデータを連鎖的に符号化することにより生成される符号であれば、空間結合ＬＤＰＣ符号に限定されない。例えば、空間結合ＬＤＰＣ符号の代わりに、後述する畳込み符号やターボ符号を使用してよい。また、第２符号化部４２０は、２元より高い次元の符号を第２符号として用いてもよい。後述する第１の実施の形態の各変形例においても同様である。
【００５２】
図６は、第１の実施の形態における正則検査行列Ｈregの一例を示す図である。空間結合ＬＤＰＣ符号化方式においては、第２符号誤り検出訂正部５３０により複数の正則検査行列Ｈregが生成される。これらの正則検査行列Ｈregは、行および列における「１」の個数（以下、「重み」と称する。）が一定の検査行列である。図６におけるａは、正則検査行列Ｈregの重みの一例を示す図である。この例では、列の各々の重みは「３」であり、行の各々の重みは「６」である。
【００５３】
第２符号誤り検出訂正部５３０は、正則検査行列Ｈregを斜めに２分割して上三角行列ＨＵおよび下三角行列ＨＬを生成する。図６におけるｂは、分割された正則検査行列Ｈregの一例を示す図である。以下、三角行列の各々において直角を挟む２辺のうちの一方を底辺とし、他方を隣辺と称する。
【００５４】
空間結合ＬＤＰＣにおいては、帯行列Ｈｂから切り出した部分行列Ｈｐにより部分的な復号を行うことができる。第２符号誤り検出訂正部５３０において部分データのサイズＮｓが設定されると、第２符号誤り検出訂正部５３０は、そのＮｓに応じたサイズの部分行列を帯行列Ｈｂから切り出す。例えば、部分データのサイズＮｓが、三角行列の底辺の２倍の長さであれば、４つの三角行列が連結された部分行列が部分データの復号において検査行列として用いられる。この検査行列Ｈｐは、列数が部分データのサイズＮｓに等しく、行数がＮｓ−Ｋｓの行列である。また、第２符号語全体を復号する場合には、帯行列Ｈｂが検査行列として用いられる。この帯行列Ｈｂの列数Ｎは、第２符号語の符号長である。
【００５５】
ここでＫｓは、部分データから第２パリティを除いたデータのサイズである。すなわち、Ｎｓ−Ｋｓは、部分データ内の第２パリティのサイズである。また、部分データのサイズＮｓは、例えば、不揮発性メモリ６００のアクセス単位の約数に設定される。なお、部分データのサイズＮｓは、不揮発性メモリ６００のアクセス単位の倍数としてもよい。
【００５６】
図８は、第１の実施の形態における生成行列の使用方法を説明するための図である。図８におけるａは、第１の実施の形態における生成行列Ｇの一例を示す図である。図７において例示された帯状の検査行列Ｈｂから式１に基づいて、図８におけるａに例示する生成行列Ｇが生成される。検査行列Ｈｂの列数がＮで行数がＮ−Ｋである場合、その検査行列Ｈｂから、図８におけるａに示すように、列数がＮで行数がＫの生成行列Ｇが生成される。図８におけるｂは、生成行列および第２符号化対象データから第２符号を求める計算式の一例である。図８におけるｂに示すように、生成行列Ｇと、第２符号化対象データとの積により、第２符号語が生成される。この第２符号語は、Ｋビットの第２符号化対象データと、Ｎ−Ｋビットの第２パリティとを含む。このように、第２符号は、符号化対象データをそのまま含む組織符号である。第２符号を組織符号とすることにより、ＥＣＣ処理部４００は、復号において第１符号のみを容易に分離して誤り訂正することができる。
【００５７】
図９は、第１の実施の形態における第２符号内のデータの依存関係の一例を説明するための図である。図９において、矢印は、依存関係を示す。図８に例示した行列演算により、各々の部分データは、隣接する部分データの状態に依存して生成される。ただし、端部の部分データには、隣接する第２パリティが存在しないため、端部の部分データのサイズは、他の部分データのサイズよりも小さくなる。なお、端部の部分データのサイズを他の部分データと同一にする場合には、第２パリティと同じサイズのダミーデータを第２パリティの代わりに加えればよい。
【００５８】
例えば、部分データ＃１は、第１符号語＃１により構成される。２番目の部分データ＃２は、隣接する第２パリティ＃１に依存する。３番目の部分データ＃３は、隣接する第２パリティ＃２に依存する。このように、最初の部分データを除き、部分データのそれぞれは、隣接する部分データの一部（例えば、第２パリティ）に依存するデータである。これらの部分データの集合が１つの第２符号語に該当する。このように、空間結合ＬＤＰＣ符号化方式では、第２符号語は、連鎖的に生成される。なお、依存関係は図９に例示した関係に限定されない。例えば、それぞれの部分データは、隣接する部分データ全体や、他の複数の部分データに依存する構成であってもよい。
【００５９】
図１０は、第１の実施の形態における不揮発性メモリ６００内の第２符号のデータ構成の一例を示すブロック図である。図１０に示すように、第２符号語は、複数の部分データを含む。各々の部分データは、隣接する第２パリティに依存するデータである。このため、隣り合う部分データにおいて一部のデータ（すなわち、第２パリティ）が共通である符号が第２符号として生成される。
【００６０】
［第２符号誤り検出訂正部の構成例］
図１１は、第１の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。この第２符号誤り検出訂正部５３０は、検査行列生成部５３１、部分データ生成部５３２、および、第２符号誤り検出訂正器５４０を備える。
【００６１】
検査行列生成部５３１は、検査行列を生成するものである。検査行列生成部５３１には、部分データのサイズＮｓが設定される。検査行列生成部５３１は、そのＮｓを列数とした検査行列を生成する。検査行列生成部５３１は、生成した検査行列を第２符号誤り検出訂正器５４０に供給する。
【００６２】
部分データ生成部５３２は、最初に、復号に失敗した第１符号を含む部分データに隣接する部分データに含まれる第１符号の復号を行う。ここでは隣接する部分データの読み出し制御はＣＰＵ３３０により行われ、読みだされた部分データに含まれる第１符号の復号は成功するものとする。次に、部分データ生成部５３２は、訂正対象の部分データと隣接する部分データを第２符号誤り検出訂正器５４０に出力する。この際に、復号に成功した第１符号の各ビットを既知ビットとして指定して、その部分データを第２符号誤り検出訂正器５４０に出力する。
【００６３】
ここで、既知ビットとは、誤りが訂正済みであり、訂正後の値が既知であるビットを意味する。前述したように隣り合う部分データは、互いに第２パリティを共有しているため、隣接部分データを誤り訂正することにより、訂正対象の部分データにおける第２パリティの誤りも訂正されることとなる。したがって、部分データ生成部５３２は、その第１符号の各ビットを既知ビットとして指定することができる。既知ビットの指定により、訂正対象の部分データの誤り訂正が容易となる。
【００６４】
また、部分データ生成部５３２は、部分データの生成において、隣接する部分データが第２符号誤り検出訂正器５４０で訂正済みであれば、その部分データを第２符号誤り検出訂正器５４０に再度入力せずに、その部分データの第２パリティを取得する。例えば、部分データ＃１、＃２、＃３、＃４のうち、部分データ＃１および＃３内の第１符号語の誤り訂正に失敗して、隣接する部分データ＃２の誤り訂正が行われた場合を考える。メモリコントローラ３００が部分データ＃２、＃１の順で訂正を行い、いずれも成功した後、部分データ＃３の誤り訂正を行う場合、部分データ＃３に隣接する部分データ＃２および＃４のうち、部分データ＃２は既に訂正済みである。この場合、メモリコントローラ３００は、部分データ＃２の訂正処理は必要ないので再度訂正せずに、部分データ＃４、＃３の順で訂正すればよい。部分データ生成部５３２は、例えば、部分データごとに訂正済みであるか否かを示すフラグを生成して復号データバッファ５７０に保持させておき、そのフラグを参照して訂正済みか否かを判断する。
【００６５】
隣接部分データが既に訂正済であるために隣接部分データに対して訂正処理を行わない場合には、部分データ生成部５３２は、第１符号誤り検出訂正部にて復号に失敗した読み出し第１符号語と、読み出し第２パリティとから部分データを生成し、第２符号誤り検出訂正部に出力する。
【００６６】
第２符号誤り検出訂正器５４０は、検査行列を使用して第２符号語内の部分データの誤りの検出および訂正を行うものである。第２符号誤り検出訂正部５３０は、例えば、サムプロダクトアルゴリズムを使用して部分データの誤りを訂正する。サムプロダクトアルゴリズムを使用する構成において、第２符号誤り検出訂正器５４０は、変数ノード処理部５４１および検査ノード処理部５４３を備える。このサムプロダクトアルゴリズムに分類されるアルゴリズムには、確率領域サムプロダクトアルゴリズム、対数領域サムプロダクトアルゴリズムなどの各種のアルゴリズムがある。変数ノード処理部５４１および検査ノード処理部５４３はこれらのうち、例えば、対数領域サムプロダクトアルゴリズムを使用して第２符号の誤りを訂正する。
【００６７】
なお、変数ノード処理部５４１および検査ノード処理部５４３は、対数領域サムプロダクトアルゴリズム以外のサムプロダクトアルゴリズムを使用してもよい。
【００６８】
また、第２符号誤り検出訂正器５４０は、第２符号語の誤りを検出および訂正することができるのであれば、ビットフリッピングアルゴリズムなど、サムプロダクトアルゴリズム以外のアルゴリズムを使用してもよい。また、サムプロダクトアルゴリズムの一部を簡略化したアルゴリズム（ｍｉｎ−ｓｕｍアルゴリズムなど）を使用してもよい。あるいは、「Shuhei Tanakamaru et.al., Over-10×-Extended-Lifetime 76%-Reduced-Error Solid-State Drives (SSDs) with Error-Prediction LDPC Architecture and Error-Recovery Scheme, ISSCC 2012」に記載の手法を使用してもよい。この文献に記載のＥＰ（Error-Prediction）−ＬＤＰＣ法において装置は、データの書換え回数やデータの保持時間をメモリセルごとに予め測定してテーブルに記録しておく。そして、装置は、これらのテーブルを参照してＢＥＲ（Bit Error Rate）を予測し、そのＢＥＲを使用してＬＤＰＣ符号の誤りを訂正する。
【００６９】
変数ノード処理部５４１は、検査ノード処理部５４３におけるパリティ検査の結果に基づいて第２符号語における誤りの検出および訂正を行うものである。また、検査ノード処理部５４３は、第２符号語に対してパリティ検査を行うものである。変数ノード処理部５４１には、第２符号語における部分データが入力される。なお、後述するように、部分データ生成部５３２は、部分データの訂正に失敗した場合に、第２符号語全体を変数ノード処理部５４１に入力してもよい。
【００７０】
具体的には、変数ノード処理部５４１は、第２符号語を受け取ると、その第２符号語に基づいてメッセージｕ0_iを生成する。このメッセージｕ0_iは、訂正前の第２符号語におけるi番目のシンボル（例えば、ビット）の値の「０」らしさ、または、「１」らしさの度合い（すなわち、尤度）を示す実数の変数である。また、「i」は、０乃至Ｎｓ−１（Ｎｓは第２符号語のサイズ）の整数である。ただし、部分データ生成部５３２によりｉ番目のビットが既知ビットとして指定された場合、メッセージｕ0_iの尤度は、最大値に設定される。変数ノード処理部５４１は、メッセージｕ0_ｊと検査ノード処理部５４３におけるパリティ検査の結果とに基づいてメッセージｖｉを生成して、検査ノード処理部５４３に出力する。このメッセージｖｉは、訂正後の第２符号語におけるｉ番目のビットの値の尤度を示す実数の変数である。対数領域サムプロダクトアルゴリズムにおいては、対数尤度比Λ（ｒｉ）がメッセージｕ0_ｉとして生成される。対数尤度比Λ（ｒｉ）は、符号語のｉ番目のシンボル（例えば、ビット）の値が「０」になる確率と、「１」になる確率との比の対数であり、例えば、次の式２により求められる。
【数２】
2014154899.tif 000004
式２において、ｒは受け取った第２符号語であり、Ｐ（ｒｉ＝１｜ｒ）は、その第２符号語においてｉ番目のビットｒｉの値が「１」である確率であり、Ｐ（ｒｉ＝０｜ｒ）は、その値が「０」である確率である。
【００７１】
なお、メッセージｕ0_ｉは、尤度を示す値であれば、対数尤度比に限定されない。例えば、ｒｉの値が「１」または「０」である確率をメッセージｕ0_ｉとしてもよい。メッセージｖｊやメッセージｕｉについても同様である。
【００７２】
検査ノード処理部５４３は、メッセージｖｉに基づいてパリティ検査を行い、その結果に基づいてメッセージｕｊを生成して変数ノード処理部５４１に出力する。「ｊ」は、０乃至（Ｎｓ−Ｋｓ）−１の整数である。ここで、Ｋｓは部分データから第２パリティを除いたデータのサイズである。対数領域サムプロダクトアルゴリズムにおいては、対数尤度比がメッセージｕｊとして出力される。
【００７３】
変数ノード処理部５４１と検査ノード処理部５４３とは所定の終了条件を満たすまでメッセージを交換する。例えば、一定回数メッセージを交換したときや、対数尤度比の絶対値が閾値を越えたときに終了条件を満たしたと判断される。
【００７４】
終了条件が満たされると、変数ノード処理部５４１は、受け取ったメッセージｕｊに基づいて、誤りを訂正した第２符号語を求める。変数ノード処理部５４１は、その訂正した第２符号語を復号データバッファ５７０に出力する。
【００７５】
［第２符号誤り検出訂正器の構成例］
図１２は、第１の実施の形態における第２符号化誤り検出訂正器５４０の一構成例を示すブロック図である。第２符号化誤り検出訂正器５４０において、変数ノード処理部５４１は、第２符号語のビット数（すなわち、検査行列Ｈｐの列数）と同数の変数ノード５４２を備える。また、検査ノード処理部５４３は、第２符号語内の第２パリティのビット数（すなわち、検査行列Ｈｐの行数）と同数の検査ノード５４４を備える。そして、検査行列Ｈｐの成分の値に基づいて検査ノード５４４および変数ノード５４２が接続される。具体的には、ｊ行ｉ列の成分の値が「１」であれば、ｊ番目の検査ノード５４４とｉ番目の変数ノード５４２とが接続され、「０」であれば、それらのノードは接続されない。
【００７６】
ｉ番目の変数ノード５４２は、検査ノード５４４におけるパリティ検査の結果に基づいて第２符号語におけるｉ番目のシンボル（例えば、ビット）の誤りの検出および訂正を行うものである。ｊ番目の検査ノード５４４は、検査行列Ｈｐのｊ番目の行に対応するパリティ検査を行うものである。
【００７７】
具体的には、ｉ番目の変数ノード５４２は、第２符号語のｉ番目のビットを部分データ生成部５３２から受け取り、そのビットの値に基づいて、メッセージｕ0_iを生成する。メッセージｕ0_iを対数尤度比とする場合、ｉ番目のビットの値が「１」であれば、最大値Ｍａｘ未満の正の所定値がu0_iに設定される。一方、ｉ番目のビットの値が「０」であれば、最小値Ｍｉｎより大きな負の所定値がｕ0_iに設定される。ここで、最大値Ｍａｘおよび最小値Ｍｉｎは、対数尤度比のデータ型およびデータサイズに依存する最大値および最小値である。例えば、符号付きの固定小数点型データを演算に用いる場合、そのデータにより表わすことのできる数値範囲は、実数部および虚数部のそれぞれのビット数に応じた範囲となる。その数値範囲内の最大値および最小値が最小値Ｍａｘおよび最小値Ｍｉｎとして用いられる。なお、第２符号化誤り検出訂正器５４０は、符号付きの浮動少数点型データを演算に用いてもよい。
【００７８】
ただし、ｉ番目のビットが既知ビットとして指定された場合、尤度が最大となる値が設定される。例えば、ｉ番目の既知ビットの値が「１」であれば、最大値Ｍａｘがｕ0_iに設定され、ｉ番目の既知ビットの値が「０」であれば、最小値Ｍｉｎがｕ0_iに設定される。
【００７９】
メッセージｕ0_iを生成した後、変数ノード５４２は、接続された検査ノード５４４の各々からのメッセージｕｊを初期値（例えば、「０」）に設定する。そして、変数ノード５４２は、次の式３を使用して、メッセージｖｉを算出し、接続された検査ノード５４４のいずれかに出力する。
【数３】
2014154899.tif 000005
式３において、ｄｖは、検査行列Ｈｐの列における「１」の値の個数（すなわち、重み）である。
【００８０】
検査ノード５４４は、接続された変数ノード５４２の各々からメッセージｖｉを受け取ると、次の式４を使用してメッセージｕｊを算出し、接続された変数ノード５４２のいずれかに出力する。
【数４】
2014154899.tif 000006
式４において、ｄｃは、検査行列Ｈｐの行における「１」の値の個数（すなわち、重み）である。また、ｔａｎｈ（）は双曲線正接関数であり、Πｘは、ｘの総乗である。
【００８１】
この式４は、式５を使用して、式６に変形することができる。
【数５】
2014154899.tif 000007
【数６】
2014154899.tif 000008
式５および式６において、ｓｉｇｎ（ｘ）は、入力値ｘに対し、ｘ≧０であれば「１」の値を返し、ｘ＜０であれば「−１」の値を返す関数である。
【００８２】
ここで、次の式７に定義した関数を使用して、式４を変形した式６を式８にさらに変形することができる。検査ノード５４４は、式４の代わりに式８を使用してメッセージｕｊを算出してもよい。
【数７】
2014154899.tif 000009
【数８】
2014154899.tif 000010
【００８３】
なお、メッセージｕｊは、式４や式８を使用して求めるほか、それらより簡易な演算によって求めることもできる。例えば、式９に定義する関数Ｒ（ｖ１，ｖ２）の演算結果を、メッセージｖ１およびｖ２の取りうる値ごとに予め計算しておく。そして、その演算結果とメッセージｖ１およびｖ２の組合せとを対応付けたテーブルを予め作成しておき、そのテーブルから読み出した演算結果を、式１０に示すように再帰的に使用することにより、メッセージｕｊを簡易に求めることができる。
【数９】
2014154899.tif 000011
【数１０】
2014154899.tif 000012
【００８４】
変数ノード５４２および検査ノード５４４は、所定の終了条件を満たすまで、式３および式４などを使用してメッセージｖｉおよびｕｊを生成し、それらのメッセージを交換する。
【００８５】
終了条件が満たされた場合には、変数ノード５４２は、次の式１１を使用して、メッセージｖｉ'を生成する。変数ノード５４２は、生成したメッセージｖｉ'に基づいて、第２符号語のｉ番目のビットの値を決定する。変数ノード５４２は、例えば、ｖｉ'≧０であればｉ番目の値を「１」に決定し、ｖｉ'＜０であれば、「０」に決定する。これにより、第２符号語の誤りが訂正される。変数ノード５４２は、第２符号語において訂正した部分データを第１符号誤り検出訂正部５２０に出力する。
【数１１】
2014154899.tif 000013
【００８６】
なお、変数ノード５４２は、式３の演算を、式１１と次の式１２とに分けて実行することもできる。この場合、変数ノード５４２は、終了条件が満たされていない場合には式１２により算出したメッセージｖｉを検査ノード５４４に出力する。そして、終了条件が満たされた場合には変数ノード５４２は、式１１により算出したメッセージｖｉ'に基づいて第２符号語内のビットの値を決定する。
【数１２】
2014154899.tif 000014
式１２において、ｕdvは、変数ノード５４２に接続されたｄｖ個目の検査ノード５４４からのメッセージである。
【００８７】
図１３は、第１の実施の形態における第１の実施の形態における変数ノード５４２と検査ノード５４４との間のメッセージ交換の一例を示す図である。図１３におけるａは、変数ノード５４２がメッセージｖｉを生成するときのメッセージ交換の一例を示す図である。例えば、１番目の変数ノードＶ１と、１、３および５番目の検査ノードＵ１、Ｕ３およびＵ５とが接続されているものとする。この場合、変数ノードＶ１は、メッセージｕ0_1を部分データ生成部５３２から受け取り、検査ノードＵ１およびＵ３からメッセージｕ１およびｕ３を受け取ると、これらのメッセージに基づいてメッセージｖ１を生成し、検査ノードＵ５に出力する。
【００８８】
図１３におけるｂは、検査ノード５４４がメッセージｕｊを生成するときのメッセージ交換の一例を示す図である。例えば、１番目の検査ノードＵ１と、１、３、５、６、７および９番目の変数ノードＶ１、Ｖ３、Ｖ５、Ｖ６、Ｖ７およびＶ９とが接続されているものとする。この場合、検査ノードＵ１は、変数ノードＶ３、Ｖ５、Ｖ６、Ｖ７およびＶ９からメッセージｖ３、ｖ５、ｖ６、ｖ７およびｖ９を受け取ると、これらのメッセージに基づいてメッセージｕ１を生成し、変数ノードＶ１に出力する。
【００８９】
図１４は、第１の実施の形態における第２符号語の訂正方法を説明するための図である。例えば、第１符号語＃１、＃２および＃３を含む第２符号を訂正する場合について考える。これらのうち、第１符号語＃１は、第１符号誤り検出訂正部５２０により訂正可能な数の誤りを含み、第１符号語＃２は訂正不可能な数の誤りを含む。また、これらについて対応して付加されている第２パリティ＃１および＃２も誤りを含むものとする。
【００９０】
第１符号誤り検出訂正部５２０は、第１符号語＃１、＃２および＃３のそれぞれの誤りを訂正する。この訂正において、第１符号誤り検出訂正部５２０は、訂正可能な数の誤りを含む第１符号語＃１の訂正に成功するが、訂正不可能な数の誤りを含む第１符号語＃２の訂正に失敗する。
【００９１】
この場合、第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃２に隣接する部分データ＃１および＃３の誤りを訂正する。これらの部分データの訂正により、部分データ＃１における第２パリティ＃１と、部分データ＃３における第２パリティ＃２の誤りが訂正される。
【００９２】
そして、第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃２を含む部分データ＃２の誤りを訂正する。部分データ＃２において、第２パリティ＃１および＃２の誤りは訂正されているため、第２符号誤り検出訂正部５３０は、これらのビットの値を既知の値として誤りを正確に訂正することができる。
【００９３】
このように、第２符号誤り検出訂正部５３０が誤りを含む訂正対象の部分データに隣接する部分データの誤り訂正を行うことにより、その訂正対象の部分データの第２パリティの誤りが訂正される。したがって、誤りを含む部分データのみを訂正する場合よりも、正確にデータの誤りを訂正することができる。また、第２符号誤り検出訂正部５３０は、第２符号語の全てではなく一部を訂正するため、第２符号語の全てを訂正する場合よりも高速にデータの誤りを訂正することができる。さらに、誤り訂正において第２符号語の全てを作業用メモリに読み出す必要がないため、全ての第２符号を読み出す場合よりも小規模な回路により第２符号誤り検出訂正部５３０を実現することができる。
【００９４】
なお、第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語に隣接する部分データの両方（部分データ＃１および＃３）を訂正しているが、いずれか一方のみを訂正してもよい。いずれか一方を訂正することにより、訂正対象の部分データにおける第２パリティ＃１および＃２の一方の誤りが訂正される。このように隣接する部分データの一方のみを訂正することにより、第２符号誤り検出訂正部５３０は、両方を訂正する場合よりも高速にデータの誤りを訂正することができる。
【００９５】
図１５は、第１の実施の形態におけるメモリコントローラ３００の動作を示すフローチャートである。この動作は、例えば、メモリコントローラ３００に電源が投入されたときに開始する。
【００９６】
メモリコントローラ３００は、ライトコマンドをホストシステム１００から受信したか否かを判断する（ステップＳ９１０）。ライトコマンドを受信したのであれば（ステップＳ９１０：Ｙｅｓ）、メモリコントローラ３００は、ライトデータを符号化するための符号化処理を実行する（ステップＳ９２０）。メモリコントローラ３００は、第２符号語に符号化したライトデータを不揮発性メモリ６００に書き込む（ステップＳ９３０）。ステップＳ９３０の後、メモリコントローラ３００はステップＳ９１０に戻る。
【００９７】
ライトコマンドを受信していなければ（ステップＳ９１０：Ｎｏ）、メモリコントローラ３００は、リードコマンドを受信したか否かを判断する（ステップＳ９４０）。リードコマンドを受信したのであれば（ステップＳ９４０：Ｙｅｓ）、メモリコントローラ３００は、第１符号語に符号化されたリードデータを読み出す（ステップＳ９５０）。そして、メモリコントローラ３００は、符号化されたリードデータを復号するための復号処理を実行する（ステップＳ９６０）。リードコマンドを受信していない場合（ステップＳ９４０：Ｎｏ）、または、ステップＳ９６０の後、メモリコントローラ３００は、ステップＳ９１０に戻る。
【００９８】
図１６は、第１の実施の形態における符号化処理の一例を示すフローチャートである。メモリコントローラ３００は、ライトデータの各々を第１符号化対象データとして、それらの第１符号化対象データを第１符号語に符号化する（ステップＳ９２１）。メモリコントローラ３００は、複数の第１符号語を第２符号語に符号化する（ステップＳ９２２）。ステップＳ９２２の後、メモリコントローラ３００は、符号化処理を終了する。
【００９９】
図１７は、第１の実施の形態における復号処理の一例を示すフローチャートである。メモリコントローラ３００は、第１符号語の各々の誤りを訂正する（ステップＳ９６１）。メモリコントローラ３００は、いずれかの第１符号語の誤り訂正に失敗したか否かを判断する（ステップＳ９６２）。いずれかの第１符号語の誤り訂正に失敗したのであれば（ステップＳ９６２：Ｙｅｓ）、メモリコントローラ３００は、その失敗した第１符号語を含む部分データの誤りを訂正するための第２符号誤り検出訂正処理を実行する（ステップＳ９７０）。全ての第１符号語の誤り訂正に成功した場合（ステップＳ９６２：Ｎｏ）、または、ステップＳ９７０の後、メモリコントローラ３００は、誤りが訂正された第１符号から、第１符号化対象データを取り出して出力する（ステップＳ９６３）。ステップＳ９６３の後、メモリコントローラ３００は、復号処理を終了する。
【０１００】
図１８は、第１の実施の形態における第２符号誤り検出訂正処理の一例を示すフローチャートである。メモリコントローラ３００は、誤りが検出された部分データに隣接する隣接部分データを取得する（ステップＳ９７１）。そして、メモリコントローラ３００は、それらの隣接部分データの誤りを訂正する（ステップＳ９７２）。そして、メモリコントローラ３００は、誤りが検出された第１符号語を含む部分データにおいて、誤り訂正に成功した隣接する第１符号を既知ビットとして、誤りを訂正する（ステップＳ９７３）。
【０１０１】
このように、本技術の第１の実施の形態によれば、メモリコントローラ３００は、符号化対象データの各々を第１符号語に符号化し、第１符号語を連鎖的に符号化することにより第２符号語を生成する。また、メモリコントローラ３００は、第２符号語において誤りが検出された第１符号語を含む部分データの直前または直後に符号化された部分データの少なくとも一方に基づいてデータの誤りを訂正することができる。これにより、メモリコントローラ３００は、第２符号語全体の誤りを訂正する場合よりも、高速に誤りを訂正することができる。また、メモリコントローラ３００は、誤りが検出された第１符号語を含む部分データのみを訂正する場合よりも、正確に誤りを訂正することができる。
【０１０２】
［第１の変形例］
第１の実施の形態では、図１０に例示したように、第１符号語のそれぞれに第２パリティを付加する構成としていたが。第２符号のデータ構造はこの構成に限定されない。第１の変形例のメモリコントローラ３００は、第２パリティを一定個数の第１符号語ごとにまとめて出力する点において、第１の実施の形態と異なる。
【０１０３】
図１９は、第１の実施の形態の第１の変形例における第２符号のデータ構造の一例である。図１９に例示するように、第１の変形例のメモリコントローラ３００は、第２パリティを一定個数の第１符号語ごとにまとめて出力する。ここで、一定個数の第２パリティからなるデータを第２パリティブロックと称する。例えば、第２パリティブロックのサイズが不揮発性メモリ６００のアクセス単位の約数や倍数となるように、第２パリティブロック内の第２パリティの個数が調整される。
【０１０４】
［第２の変形例］
第１の実施の形態では、第１符号化の単位と第２符号化の単位とを一致させて符号化していたが、第１符号化の単位と復号単位とが異なっていてもよい。第２の変形例のメモリコントローラ３００は、第１符号化の単位と異なる単位で第２符号語を復号する点において第１の実施の形態と異なる。
【０１０５】
図２０は、第１の実施の形態の第２の変形例における第２符号語のデータ構成の一例を説明するための図である。例えば、第１符号語＃１乃至＃４を符号化する場合、第３の変形例では、図２０に例示するように、第１符号語＃１および＃２を含む部分を部分データ＃１とする。そして、第１符号語＃３および＃４を含む部分を部分データ＃２とする。これにより、メモリコントローラ３００は、第１符号化の単位と異なる単位で第２符号語を復号することができる。
【０１０６】
［第３の変形例］
第１の実施の形態では、第１符号語全体を符号化していたが、メモリコントローラ３００は、第１符号語の一部を符号化してもよい。第３の変形例のメモリコントローラ３００は、第１符号語の一部を符号化する点において第１の実施の形態と異なる。
【０１０７】
図２１は、第１の実施の形態の第３の変形例における第２符号語のデータ構成の一例を説明するための図である。第３の変形例のメモリコントローラ３００は、図２１に例示するように、第１符号語の一部、例えば、第１パリティを除く第１符号化対象データのみを部分データに符号化する。これにより、第２符号語の符号長を削減することができる。図２１においては、第１パリティの記載を省略している。
【０１０８】
［第４の変形例］
第１の実施の形態では、隣接部分データの誤りを訂正してから、訂正対象の部分データの誤りを訂正していたが、メモリコントローラ３００は、これらをまとめて１つの復号単位として訂正してもよい。第５の変形例のメモリコントローラ３００は、訂正対象の部分データと、隣接部分データとをまとめて訂正する点において第１の実施の形態と異なる。具体的には、検査行列生成部５３１が、訂正対象の部分データの検査行列と、隣接部分データの検査行列とを連結して、訂正対象の部分データおよび隣接部分データからなるデータのサイズに応じた列数の検査行列を生成する。検査行列生成部５３１は、生成した検査行列を第２符号誤り検出訂正器５４０に供給し、第２符号誤り検出訂正器５４０は、その検査行列を使用して、訂正対象の部分データおよび隣接部分データを１つの復号単位としてまとめて訂正する。
【０１０９】
図２２は、第１の実施の形態の第４の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。第４の変形例の第２符号誤り検出処理は、ステップＳ９７２およびＳ９７３の代わりに、ステップＳ９８１およびＳ９８２を実行する点において第１の実施の形態と異なる。第４の変形例においてメモリコントローラ３００は、誤りが検出された第１符号語に隣接する隣接部分データを取得し（ステップＳ９７１）、誤りが検出された第１符号語を含む部分データを取得する（ステップＳ９８１）。そして、メモリコントローラ３００は、取得した部分データのそれぞれを、まとめて誤り訂正を行う（ステップＳ９８２）。
【０１１０】
図２３は、第１の実施の形態の第５の変形例における第２符号の訂正法を説明するための図である。例えば、第１符号語＃１、＃２および＃３を含む第２符号を訂正する場合について考える。これらのうち、第１符号語＃２は訂正不可能な数の誤りを含む。
【０１１１】
第１符号誤り検出訂正部５２０は、第１符号語＃１、＃２および＃３のそれぞれの誤りを訂正する。この訂正において、第１符号誤り検出訂正部５２０は、訂正不可能な数の誤りを含む第１符号語＃２の訂正に失敗する。
【０１１２】
この場合、第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃２と、それに隣接する部分データ＃１および＃３とをまとめて訂正する。これらの部分データの訂正により、第１符号語＃２の誤りが訂正される。隣接部分データ（＃１および＃３）を訂正し、次に訂正対象の部分データ（＃２）を訂正する方法では、隣接部分データの誤り訂正に失敗した場合に、その隣接部分データ内の誤った第２パリティが訂正対象の部分データの訂正に使用されるおそれがある。これに対して第５の変形例によれば、隣接部分データと訂正対象の部分データとをまとめて訂正するため、誤ったパリティを使用して誤り訂正が行われるおそれがなくなり、誤り訂正能力が向上する。
【０１１３】
＜２．第２の実施の形態＞
［第２符号誤り検出訂正部の構成例］
図２４は、第２の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。第１の実施の形態では、第２符号誤り検出訂正部５３０は、隣接部分データの訂正結果にかかわらず、隣接部分データに基づいて訂正対象の部分データの誤りを訂正していた。しかし、隣接部分データの訂正に失敗した場合に、その失敗した隣接部分データに基づいて訂正対象の部分データの誤り訂正を行うと、その訂正にも失敗する可能性が高くなる。このため、隣接部分データの訂正に失敗した場合には、その隣接部分データにさらに隣接する部分データの誤りを訂正して、訂正に成功するまで、隣接する部分データを辿る訂正方法を使用することが望ましい。第２の実施の形態の第２符号誤り検出訂正部５３０は、訂正に成功するまで、隣接する部分データを辿る点において第１の実施の形態と異なる。
【０１１４】
具体的には、第２の実施の形態の第２符号誤り検出訂正器５４０において、変数ノード処理部５４１は、部分データの訂正に失敗したか否かを示す訂正結果を部分データ生成部５３２に出力する。例えば、一定回数メッセージを交換したときにおいて、いずれかのビットについての対数尤度比の絶対値が閾値を越えなかったときに、訂正に失敗したと判断される。部分データ生成部５３２は、その訂正結果に基づいて隣接部分データの訂正に失敗した場合には、その隣接部分データにさらに隣接する部分データを新たな隣接部分データとして取得し、変数ノード処理部５４１に出力する。なお、第２の実施の形態においても第１の実施の形態と同様に、第２符号は空間結合ＬＤＰＣ符号に限定されない。例えば、空間結合ＬＤＰＣ符号の代わりに、後述する畳込み符号やターボ符号を使用してよい。また、第２符号化部４２０は、２元より高い次元の符号を第２符号として用いてもよい。後述する第２の実施の形態の各変形例においても同様である。
【０１１５】
［メモリコントローラの動作例］
図２５は、第２の実施の形態における第２符号誤り検出訂正処理の一例を示すフローチャートである。第２の実施の形態の第２符号誤り検出訂正処理は、ステップＳ９７４、Ｓ９７５およびＳ９７７をさらに実行する点において第１の実施の形態と異なる。
【０１１６】
メモリコントローラ３００は、誤りを検出した第１符号語に隣接する隣接部分データを訂正し（ステップＳ９７２）、その訂正が成功したか否かを判断する（ステップＳ９７４）。訂正に失敗した場合には（ステップＳ９７４：Ｎｏ）、メモリコントローラ３００は、訂正に失敗した隣接部分データに隣接する部分データを新たな隣接部分データとして取得し（ステップＳ９７５）、ステップＳ９７２に戻る。一方、訂正に成功した場合には（ステップＳ９７４：Ｙｅｓ）、メモリコントローラ３００は、辿った順と逆順で部分データを順に訂正して、誤りが検出された訂正対象の部分データを訂正する（ステップＳ９７７）。ステップＳ９７７の後、メモリコントローラ３００は、第２符号誤り検出訂正処理を終了する。
【０１１７】
図２６は、第１の実施の形態における第２符号の訂正方法を説明するための図である。例えば、第１符号語＃１乃至＃４を含む第２符号の誤りを訂正する場合について考える。これらのうち、第１符号語＃２および＃３は、第１符号誤り検出訂正部５２０において訂正不可能な数の誤りを含む。また、各第１符号語について生成された、第２パリティ＃１、＃２および＃３も誤りを含むものとする。
【０１１８】
第１符号誤り検出訂正部５２０は、第１符号語＃１乃至＃４のそれぞれの誤りを訂正する。この訂正において、第１符号誤り検出訂正部５２０は、訂正不可能な数の誤りを含む第１符号語＃２および＃３の訂正に失敗する。
【０１１９】
第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃２に隣接する部分データ＃１および＃３の誤りを訂正する。ここで、第２符号誤り検出訂正部５３０は、誤りのない第１符号語＃１を含む部分データ＃１の訂正には成功したが、誤りのある第１符号語＃３を含む部分データ＃３の訂正には失敗したものとする。この場合、第２符号誤り検出訂正部５３０は、訂正に失敗した部分データ＃３にさらに隣接する部分データ＃４の誤りを訂正する。
【０１２０】
部分データ＃４の訂正に成功すると、第２符号誤り検出訂正部５３０は、訂正に失敗した部分データ＃３の誤りを訂正する。部分データ＃４の訂正により第２パリティ＃３の誤りが訂正されるため、その第２パリティ＃３を含む部分データ＃３を正確に訂正することができる。部分データ＃３の訂正に成功すると、第２符号誤り検出訂正部５３０は、訂正に失敗した部分データ＃２の誤りを訂正する。部分データ＃３の訂正により第２パリティ＃２の誤りが訂正されるため、その第２パリティ＃２を含む部分データ＃２を正確に訂正することができる。
【０１２１】
このように、第２の実施の形態によれば、隣接部分データの訂正に成功するまで、部分データを辿ることにより、訂正に成功した隣接部分データに基づいて、検出された誤りを訂正することができる。これにより、データの誤りをより正確に訂正することができる。
【０１２２】
［第１の変形例］
第２の実施の形態では、メモリコントローラ３００は、第１符号語の復号結果に関らず、訂正に成功するまで隣接部分データを辿っていた。しかし、第１符号語の訂正に失敗した場合には、その第１符号語を含む部分データの訂正も失敗する可能性が高い。このため、部分データを辿る場合には、訂正に失敗した第１符号語を含む部分データをスキップすることが望ましい。第１の変形例のメモリコントローラ３００は、訂正に失敗した第１符号語を含む部分データをスキップして、部分データを辿る点において第２の実施の形態と異なる。
【０１２３】
図２７は、第２の実施の形態の第１の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。第１の変形例の第２符号誤り検出訂正処理は、ステップＳ９７６をさらに実行する点において第２の実施の形態と異なる。
【０１２４】
部分データの誤り訂正に失敗すると（ステップＳ９７４：Ｎｏ）、メモリコントローラ３００は、その失敗した部分データに隣接する部分データを取得する（ステップＳ９７５）。そして、メモリコントローラ３００は、誤り検出ブロック通知に基づいて、その隣接部分データに含まれる第１符号語の訂正に成功したか否かを判断する（ステップＳ９７６）。第１符号語の訂正に失敗していた場合には（ステップＳ９７６：Ｎｏ）、メモリコントローラ３００はステップＳ９７５に戻り、その失敗した第１符号語を含む部分データに隣接する部分データを取得する。一方、第１符号語の訂正に成功していた場合には（ステップＳ９７６：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９７２に戻る。
【０１２５】
図２８は、第２の実施の形態の第１の変形例における第２符号の訂正方法を説明するための図である。例えば、第１符号語＃１乃至＃４を含む第２符号の誤りを訂正する場合について考える。第１符号誤り検出訂正部５２０は、訂正不可能な数の誤りを含む第１符号語＃２および＃３の訂正に失敗したものとする。
【０１２６】
第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃２に隣接する第１符号語＃１および＃３の訂正が成功したか否かを誤り検出ブロック通知に基づいて判断する。第１符号語＃１の訂正は成功しているが、第１符号語＃３の訂正には失敗しているため、第２符号誤り検出訂正部５３０は、訂正に失敗した第１符号語＃３をスキップして、その隣の第１符号語＃４の訂正が成功したか否かを判断する。第１符号語＃４の訂正は成功しているため、第２符号誤り検出訂正部５３０は、その第１符号語＃４を含む部分データ＃４の誤りを訂正する。
【０１２７】
このように、訂正に失敗した第１符号語を含む部分データをスキップして、隣接する部分データを辿ることにより、訂正に成功する可能性の高い部分データに基づいて、検出された誤りを訂正することができる。これにより、より正確にデータの誤りを訂正することができる。
【０１２８】
［第２の変形例］
第２の実施の形態では、メモリコントローラ３００は、隣接部分データの訂正に失敗すると、訂正に成功するまで隣接部分データを辿っていた。しかし、確実にデータを訂正するには、第２符号語を部分的に復号するよりも、第２符号語全体を復号する方が望ましい。第２の変形例は、隣接部分データの訂正に失敗すると、メモリコントローラ３００が第２符号語全体を復号する点において第２の実施の形態と異なる。
【０１２９】
図２９は、第２の実施の形態の第２の変形例における第２符号誤り検出訂正処理の一例を示すフローチャートである。第２の変形例の第２符号誤り検出訂正処理は、ステップＳ９７４、Ｓ９８３およびＳ９８４をさらに実行する点において第２の実施の形態と異なる。
【０１３０】
メモリコントローラ３００は、誤りを検出した第１符号語に隣接する隣接部分データを訂正し（ステップＳ９７２）、その訂正が成功したか否かを判断する（ステップＳ９７４）。訂正に失敗した場合には（ステップＳ９７４：Ｎｏ）、メモリコントローラ３００は、第２符号語全体を読み出し（ステップＳ９８３）、その第２符号語の誤りを訂正する（ステップＳ９８４）。一方、訂正に成功した場合には（ステップＳ９７４：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９７３を実行する。ステップＳ９７３またはＳ９８４の後、メモリコントローラ３００は、第２符号誤り検出訂正処理を終了する。
【０１３１】
＜３．第３の実施の形態＞
［第２符号化部の構成例］
第１の実施の形態では、隣接部分データが一部のデータを共有するＬＤＰＣ符号を第２符号として使用していたが、畳込み符号を第２符号として使用してもよい。第３の実施の形態のメモリコントローラ３００は、第２符号として畳込み符号を使用する点において第１の実施の形態と異なる。図３０は、第３の実施の形態における第２符号化部４２０の一構成例を示すブロック図である。第３の実施の形態の第２符号化部４２０は、第２符号化器４２３の代わりに第２符号化器４３０を備える点において第１の実施の形態と異なる。
【０１３２】
第２符号化器４３０は、畳込み符号化方式を使用して第１符号語を第２符号語に符号化するものである。第２符号化器４３０は、例えば、半加算器４３１および４３４と、レジスタ４３２および４３３とを備える。
【０１３３】
半加算器４３１は、入力値の排他的論理和を出力するものである。半加算器４３１には、第１符号語を構成するビットのいずれかが第２符号化対象ビットｒｍとして入力される。ｍは、０乃至Ｎｆ−１の整数である。Ｎｆは、第１符号語の符号長である。また、半加算器４３１には、レジスタ４３２および４３３から出力されたビットが入力される。半加算器４３１は、これらの排他的論理和をレジスタ４３２および半加算器４３４に出力する。
【０１３４】
レジスタ４３２は、半加算器４３１からの出力値を保持するものである。レジスタ４３２は、所定のクロック信号に従って、保持値をレジスタ４３３および半加算器４３１に出力する。なお、レジスタ４３２が保持する値の初期値は例えば、「０」に設定される。
【０１３５】
レジスタ４３３は、レジスタ４３２からの出力値を保持するものである。レジスタ４３３は、所定のクロック信号に従って、半加算器４３１および４３４に出力する。なお、レジスタ４３３が保持する値の初期値は例えば、「０」に設定される。
【０１３６】
半加算器４３４は、入力値の排他的論理和を出力するものである。半加算器４３４には、半加算器４３１およびレジスタ４３３から出力されたビットが入力される。半加算器４３１は、これらの排他的論理和を第２パリティビットＣｍとして出力する。
【０１３７】
第２符号化器４３０は、第２符号化対象ビットｒｍおよび第２パリティビットＣｍからなる符号語を第２符号語として符号化データバッファ４６０に保持させる。ここで、畳込み符号化により生成された第２符号語のうち部分データのサイズＮｓは、例えば、不揮発性メモリ６００のアクセス単位の約数に設定される。なお、部分データのサイズＮｓは、不揮発性メモリ６００のアクセス単位の倍数としてもよい。
【０１３８】
図３０に例示した構成により、過去の第２符号化対象ビットと、現在の第２符号化対象ビットとに対する畳込み演算の結果が、現在の第２符号検査ビットとして出力される。
【０１３９】
［第２符号化部の状態遷移図］
図３１は、第３の実施の形態における第２符号化器４３０の状態遷移の一例を示す状態遷移図である。第２符号化器４３０の状態は、Ｓ０、Ｓ１、Ｓ２およびＳ３の４つの状態を含む。Ｓ０は、レジスタ４３２および４３３に保持された値が「００」の状態であり、Ｓ１は、それらの値が「１０」の状態である。また、Ｓ２は、レジスタ４３２および４３３に保持された値が「０１」の状態であり、Ｓ４は、それらの値が「１１」の状態である。
【０１４０】
レジスタ４３２および４３３は初期値として例えば「００」を保持するため、第２符号化器４３０の初期状態はＳ０に設定される。なお、初期状態をＳ０以外の状態とすることもできる。
【０１４１】
状態Ｓ０において、「０」の値の第２符号化対象ビットｒｍが入力されると、第２符号化器４３０は、図３０に例示した構成において畳込み演算を行い、第２パリティビットＣｍとして「０」を算出する。この結果、入力された「０」と合わせて「００」の値が出力される。レジスタ４３２および４３３に保持された値は「００」のままであるため、第２符号化器４３０の状態は、状態Ｓ０のままである。一方、状態Ｓ０において、「１」の値が入力されると、第２符号化器４３０は、「１１」の値を出力して、状態Ｓ１に遷移する。
【０１４２】
状態Ｓ１において、「０」の値が入力されると、第２符号化器４３０は、「０１」の値を出力して、状態Ｓ３に遷移する。一方、状態Ｓ１において、「１」の値が入力されると、第２符号化器４３０は、「１０」の値を出力して、状態Ｓ２に遷移する。
【０１４３】
状態Ｓ２において、「０」の値が入力されると、第２符号化器４３０は、「００」の値を出力して、状態Ｓ１に遷移する。一方、状態Ｓ２において、「１」の値が入力されると、第２符号化器４３０は、「１１」の値を出力して、状態Ｓ０に遷移する。
【０１４４】
状態Ｓ３において、「０」の値が入力されると、第２符号化器４３０は、「０１」の値を出力して、状態Ｓ２に遷移する。一方、状態Ｓ３において、「１」の値が入力されると、第２符号化器４３０は、「１０」の値を出力して、状態Ｓ３の状態を維持する。
【０１４５】
このように、第２符号化器４３０は、入力値と現在の状態とに基づいて、一定の規則に従って第２符号を構成するビット列を出力するとともに状態遷移する。このため、第２符号誤り検出訂正部５３０は、第２符号化器４３０の状態の遷移規則に基づいて、第２符号の誤りを訂正することができる。
【０１４６】
図３２は、第３の実施の形態における第２符号の生成方法の一例を説明するための図である。初期値「００」を保持する第２符号化器４３０に最初の第２符号化対象ビットｒ０が入力されると、そのｒ０および「００」に対する演算により生成された最初の第２パリティビットＣ０がｒ０とともに出力される。そして、第２符号化器４３０の前段のレジスタには、ｒ０および「００」に対する演算により生成された「ｒ０'」が保持される。
【０１４７】
次に、２番目の第２符号化対象ビットｒ１が入力されると、そのｒ１、ｒ０'および「０」に対する演算により生成された２番目の第２パリティビットＣ１がｒ１とともに出力される。そして、第２符号化器４３０の後段のレジスタには、前段のｒ０'が保持され、後段のレジスタには、ｒ１等に対する演算により生成された「ｒ１'」が保持される。
【０１４８】
このように、第２符号語におけるデータのそれぞれの値は、それ以前のデータに対する畳込み演算の結果に基づいて決定される。
【０１４９】
［第２符号誤り検出訂正部の構成例］
図３３は、第３の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。第３の実施の形態の第２符号誤り検出訂正部５３０は、検査行列生成部５３１および第２符号誤り検出訂正器５４０の代わりに第２符号誤り検出訂正器５５０を備える点において第１の実施の形態と異なる。
【０１５０】
第２符号誤り検出訂正器５５０は、部分データの誤りを訂正するものであり、例えば、ビタビアルゴリズムを使用して、部分データの誤りを訂正する。
【０１５１】
ここで、ビタビアルゴリズムにおいては、図３１に例示した状態遷移規則に従って、第２符号化器４３０の状態を時系列順に並べ、これらの状態を結ぶトレリス経路のうち、最も尤度の高い経路が求められる。以下、トレリス経路を単に「経路」と称する。具体的には、経路の各々において生成されるデータと、不揮発性メモリ６００から読み出された部分データとのハミング距離とを算出し、最もハミング距離（パスメトリック）の短い経路が選択される。選択された経路において生成されるデータが、誤り訂正されたデータとして出力される。
【０１５２】
第２符号誤り検出訂正器５５０は、時系列順に並べた状態をデータのサイズに応じて区切り、ビタビアルゴリズムを使用して部分データを訂正する。第２符号誤り検出訂正器５５０は、最初に隣接データのビタビアルゴリズムによる復号を実施して、求めた起点または終点の状態を用いて対象部分データを復号する。具体的には、隣接部分データが訂正対象の部分データの後の部分データであれば、その起点の状態を用い、隣接部分データが訂正対象の前の部分データであれば、その終点の状態を用いて対象部分データの復号を行う。このように、経路の探索に先立って、経路（トレリス経路）の起点または終点の状態を決定することを、以下、「トレリスを終端する」と称する。トレリスの終端により、探索対象の経路が絞り込まれるため、データの誤りを、より正確に訂正することができる。
【０１５３】
第２符号誤り検出訂正器５５０は、畳込み符号化されたデータの誤りを訂正することができるのであれば、訂正においてビタビアルゴリズム以外のアルゴリズムを使用してもよい。
【０１５４】
図３４は、第３の実施の形態における第２符号化部の状態遷移の一例を示すトレリス線図の一例である。部分データ＃１乃至＃３が、順に不揮発性メモリ６００から読み出され、部分データ＃２に含まれる第１符号語の訂正に失敗した場合について考える。部分データ＃１および＃３における第１符号語の訂正は成功したものとする。図３３において、横軸は、部分データの読出時刻である。「○」のマークは、第２符号化器４３０の状態を示す。状態間の点線は経路における枝であり、実線は最も尤度の高い経路における枝である。
【０１５５】
図３４におけるａは、部分データ＃２の訂正前のトレリス線図の一例である。メモリコントローラ３００は、ビタビアルゴリズムを使用して、訂正に失敗した部分データ＃２に隣接する部分データ＃１および＃３の訂正を行う。訂正結果に基づいて、メモリコントローラ３００は、部分データ＃１の終点の状態Ｓ３と、部分データ＃３の始点の状態Ｓ０とを求める。
【０１５６】
図３４におけるｂは、部分データ＃２の訂正時のトレリス線図の一例である。メモリコントローラ３００は、部分データ＃２の訂正において、部分データ＃１の訂正で求めた終点Ｓ０を起点とし、部分データ＃３の訂正で求めた起点Ｓ３を終点として、トレリスを終端する。図３４におけるｂに記載の網掛けの「○」のマークは、終端した状態を示すものである。トレリスの終端により、探索する経路が絞り込まれるため、部分データ＃２の誤りを正確に訂正することができる。
【０１５７】
このように、第３の実施の形態によれば、メモリコントローラ３００は、畳込み符号を第２符号として使用して誤り訂正を行うことができる。これにより、畳込み符号化方式を使用するシステムにおいて、データの誤りを正確かつ高速に訂正することができる。
【０１５８】
＜４．第４の実施の形態＞
［第２符号化部の構成例］
第１の実施の形態では、隣接部分データが一部のデータを共有するＬＤＰＣ符号を第２符号として使用していたが、ターボ符号を第２符号として使用してもよい。第４の実施の形態のメモリコントローラ３００は、第２符号としてターボ符号を使用する点において第１の実施の形態と異なる。
【０１５９】
図３５は、第４の実施の形態における第２符号化部４２０の一構成例を示すブロック図である。第４の実施の形態の第２符号化部４２０は、第２符号化対象データ生成部４２１、第２符号化器４２３の代わりに第２符号化器４４０を備える点において第１の実施の形態と異なる。
【０１６０】
第２符号化器４４０は、入替前第２符号化器４４１、遅延バッファ４４２、インタリーバ４４３、入替後第２符号化器４４４、および、スイッチ４４５を備える。
【０１６１】
入替前第２符号化器４４１は、畳込み符号化方式を使用して、第２符号化対象データを第２符号語に符号化するものである。入替前第２符号化器４４１の構成は、第２符号検査ビットのみを生成する点以外は、例えば、第３の実施形態における第２符号化器４３０と同様である。入替前第２符号化器４４１は、生成した第２パリティビットｂＣｍをスイッチ４４５に出力する。ここで、ｍは、０乃至Ｎｆ−１の整数であり、Ｎｆは、第１符号語（すなわち、第２符号化対象データ）の符号長である。
【０１６２】
遅延バッファ４４２は、入替前第２符号化器４４１における符号化が完了するまで、インタリーバ４４３への第２符号化対象データの出力を遅延させるものである。
【０１６３】
インタリーバ４４３は、遅延バッファ４４２を介して第２符号化対象データを取得して、その第２符号化対象データにおいて、データの入れ替えを行うものである。この入れ替えにより、バーストエラーに対する誤り訂正能力が高くなる。インタリーバ４４３は、入れ替えが完了すると、スイッチ４４５を制御して、入替前第２符号化器４４１からの第２符号検査ビットの出力を開始させる。インタリーバ４４３は、入れ替えた第２符号化対象データを入替後第２符号化器４４４に出力する。
【０１６４】
入替後第２符号化器４４４は、畳込み符号化方式を使用して、データが入れ替えられた第２符号化対象データを第２符号語に符号化するものである。入替後第２符号化器４４４は、生成した第２パリティビットａＣｍをスイッチ４４５に出力する。
【０１６５】
スイッチ４４５は、インタリーバ４４３の制御に従って、第２パリティビットｂＣｍまたはａＣｍを出力するものである。スイッチ４４５は、入れ替え前においては、入替前第２符号化器４４１からの第２パリティビットｂＣｍを出力し、入れ替え後においては、入替後第２符号化器４４４からの第２パリティビットａＣｍを出力する。
【０１６６】
第２符号化器４４０は、第２符号化対象ビットｒｍ、第２パリティビットｂＣｍおよびａＣｍからなる符号を第２符号として符号化データバッファ４６０に出力する。データの入れ替え前に生成された第２パリティビットｂＣｍは、第２符号の一部または全体を復号するために用いられる。一方、データの入れ替え後に生成された第２パリティビットａＣｍは、第２符号の部分的な復号が失敗した場合に、第２符号全体を復号するために用いられる。
【０１６７】
［第２符号誤り検出訂正部の構成例］
図３６は、第４の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。第４の実施の形態の第２符号誤り検出訂正部５３０は、検査行列生成部５３１および第２符号誤り検出訂正器５４０の代わりに、第２符号誤り検出訂正器５６０を備える点において第１の実施の形態と異なる。
【０１６８】
第４の実施の形態の部分データ生成部５３２は、復号した第１符号語と第２パリティから部分データを生成して、第２符号誤り検出訂正器５６０に供給する。
【０１６９】
第２符号誤り検出訂正器５６０は、入替前第２符号訂正器５６１、インタリーバ５６２、入替後第２符号訂正器５６３およびデインタリーバ５６４を備える。
【０１７０】
入替前第２符号訂正器５６１は、データが入れ替えられる前の第２符号語の誤りを訂正するものである。入替前第２符号訂正器５６１は、例えば、ＢＣＪＲ（Bahl Cocke Jelinek Raviv）アルゴリズムを使用して、第２符号語の誤りを訂正する。
【０１７１】
ＢＣＪＲアルゴリズムを使用する場合、入替前第２符号訂正器５６１は、部分データ生成部５３２から部分データを受け取り、デインタリーバ５６４から事前情報Ｌｅ（ｕｋ）を受け取る。ここで、事前情報Ｌｅ（ｕｋ）は、入替後第２符号訂正器５６３により求められたｋ番目のシンボル（例えば、ビット）ｕｋの対数尤度比である。ｋは、０乃至Ｎｔ−１の整数であり、Ｎｓは訂正対象のデータのサイズである。なお、初期状態においては、事前情報Ｌｅ（ｕｋ）は求められていないため、事前情報Ｌｅ（ｕｋ）は、所定の初期値（例えば、「０」）に設定される。また、訂正対象のデータは、第２符号語の部分データまたは第２符号語全体である。
【０１７２】
入替前第２符号訂正器５６１は、受け取ったデータから、第２符号化対象ビットｒｍと、入れ替え前に生成された第２パリティビットｂＣｍを取り出す。そして、入替前第２符号訂正器５６１は、次の式１３を使用して、前方状態通過確率αｋ（ｓ）を算出する。ここで、ｓは、入替前第２符号化器４４１の状態である。また、前方状態通過確率αｋ（ｓ）は、０乃至ｋ−１番目までの状態の各々を通過して、ｋ番目の状態がｓとなる確率である。
【数１３】
2014154899.tif 000015
【０１７３】
式１３において、γｋ（ｓ'，ｓ）は、状態ｓ'から状態ｓへ遷移する確率であり、次の式１４により求められる。
【数１４】
2014154899.tif 000016
【０１７４】
式１４において、Ｐ（ｕｋ）は、事前情報Ｌｅ（ｕｋ）を使用して、次の式１５により求められる。また、ｐ（ｒｋ｜ｕｋ）は、符号化データ供給部４７０から第１符号誤り検出訂正部５２０もしくは第２符号誤り検出訂正部５６０までの通信経路に依存する確率であり、次の式１６により求められる。
【数１５】
2014154899.tif 000017
【数１６】
2014154899.tif 000018
式１６において、Ｅｓは、符号化データ供給部４７０から第１符号誤り検出訂正部５２０もしくは第２符号誤り検出訂正部５６０までの通信経路における１ビット当たりの信号のエネルギーであり、単位は、例えばジュール［Ｊ］である。また、Ｎ０は、その通信路の雑音電力密度であり、単位は、例えばワット／ヘルツ［Ｗ／Ｈｚ］である。Ｅｓ／Ｎ０は、例えば、加法性ホワイトガウスノイズ(ＡＷＧＮ：Additive White Gaussian Noise)通信路を想定して算出される。
【０１７５】
ここで、部分データ生成部５３２から起点の状態を受け取っていれば、入替前第２符号訂正器５６１は、その状態に基づいてトレリスを終端する。例えば、式１４において、ｓ'が始点の状態に該当するγ（ｓ'，ｓ）の確率を最大にする。
【０１７６】
また、入替前第２符号訂正器５６１は、次の式１７を使用して、後方状態通過確率βｋ（ｓ）を算出する。ここで、後方状態通過確率βｋ（ｓ）は、末尾のＮｓ−１からｋ＋１番目までの状態の各々を通過して、ｋ番目の状態がｓとなる確率である。
【数１７】
2014154899.tif 000019
【０１７７】
ここで、部分データ生成部５３２から終点の状態を受け取っていれば、入替前第２符号訂正器５６１は、その状態に基づいてトレリスを終端する。例えば、式１７において、ｓが終点の状態に該当するγ（ｓ'，ｓ）の確率を最大にする。
【０１７８】
そして、入替前第２符号訂正器５６１は、次の式１８を使用して、式１３、式１４および式１７の計算結果から、対数尤度比Λ（ｕｋ）を算出する。
【数１８】
2014154899.tif 000020
【０１７９】
そして、入替前第２符号訂正器５６１は、所定の終了条件を満たすか否かを判断し、終了条件を満たすのであれば、算出した対数尤度比Λ（ｕｋ）に基づいて訂正後のデータのビットｕｋの値を決定し、復号データバッファ５７０および部分データ生成部５３２に出力する。例えば、入替前第２符号訂正器５６１および入替後第２符号訂正器５６３の間における情報の受け渡しの繰返し回数が所定数を越えたときや、対数尤度比Λ（ｕｋ）の絶対値が所定の閾値を越えたときに終了条件が満たされたと判断される。ただし、第２符号の部分的な復号を行う場合には、入替前第２符号訂正器５６１および入替後第２符号訂正器５６３の間の情報の受け渡しは行われないため、対数尤度比の絶対値が所定の閾値を超えたときに終了条件が満たされる。訂正後のビットｕｋの値は、例えば、対数尤度比Λ（ｕｋ）が正の値であれば「１」に、負の値であれば「０」に決定される。
【０１８０】
一方、終了条件が満たされなかった場合、入替前第２符号訂正器５６１は、部分データの全てを受け取っているか否かを判断する。部分データの全て（すなわち、第２符号語）を受け取っておらず、第２符号を部分的に復号する場合には、入替前第２符号訂正器５６１は、訂正の失敗を示す訂正結果を生成して部分データ生成部５３２に出力する。一方、部分データの全て（第２符号語）を受け取っている場合、入替前第２符号訂正器５６１は、次の式１９および式２０を使用して、部分データ生成部５３２から受け取った第２符号語と対数尤度比Λ（ｕｋ）とから外部情報Ｌ（ｕｋ）を算出する。入替前第２符号訂正器５６１は、算出した外部情報Ｌ（ｕｋ）を受け取った第２符号語とともにインタリーバ５６２に出力する。
【数１９】
2014154899.tif 000021
【数２０】
2014154899.tif 000022
【０１８１】
インタリーバ５６２は、入替前第２符号訂正器５６１からの第２符号語および外部情報Ｌ（ｕｋ）をランダムに入れ替えるものである。インタリーバ５６２は、入れ替えた外部情報Ｌ（ｕｋ）を入替後第２符号訂正器５６３における事前情報として、入れ替えた第２符号語とともに入替後第２符号訂正器５６３に出力する。
【０１８２】
入替前２符号訂正器５６３において復号に失敗した場合は、入替前２符号訂正器５６３は、第２符号語を全て読み出してから復号処理を行う。第２符号語を全て読み出す場合には、部分的に読み出す場合よりも読み出し時間を要するため、全ての読み出しは、部分的な復号に失敗した場合にのみ行われる。
【０１８３】
入替後第２符号訂正器５６３は、データが入れ替えられた第２符号語の誤りを訂正するものである。入替後第２符号訂正器５６３は、インタリーバ５６２から事前情報および第２符号語を受け取り、その第２符号語から第２符号化対象ビットｕｋおよび第２パリティビットａＣｋを取り出す。入替後第２符号訂正器５６３は、入替前第２符号訂正器５６１と同様の方法を使用して、事前情報および第２符号語に基づいて外部情報を求める。入替後第２符号訂正器５６３は、外部情報および第２符号語をデインタリーバ５６４に出力する。
【０１８４】
デインタリーバ５６４は、入れ替えられた第２符号語および外部情報を、入れ替え前の状態に戻すものである。デインタリーバ５６４は、入れ替え前の外部情報を入替前第２符号訂正器５６１における外部情報として、入れ替え前の第２符号語とともに入替前第２符号訂正器５６１に出力する。
【０１８５】
このように、第４の実施の形態によれば、データを入れ替えて符号化を行うターボ符号を第２符号として使用してデータの誤りを訂正することができる。これにより、バーストエラーに対する誤り訂正能力が向上する。また、第２符号の部分的な復号に失敗した場合に第２符号全体の復号を行うため、部分的な復号のみを行う場合よりも誤り訂正能力が向上する。
【０１８６】
＜５．第５の実施の形態＞
［第２符号化部の構成例］
第１の実施の形態では、メモリコントローラ３００は第２パリティに対するパリティを生成していなかった。しかし、メモリコントローラ３００は第２パリティに対するパリティをさらに生成して第２パリティの誤り訂正を行ってもよい。第５の実施の形態のメモリコントローラ３００は、第２パリティに対するパリティをさらに生成する点において第１の実施の形態と異なる。なお、第２乃至４の実施の形態において、第２パリティに対するパリティをさらに生成してもよい。
【０１８７】
図３７は、第５の実施の形態における第２符号化部４２０の一構成例を示すブロック図である。第５の実施の形態の第２符号化部４２０は、パリティデータバッファ４５１および第１符号化器４５２をさらに備える点において、図３０に例示した第３の実施の形態と異なる。
【０１８８】
パリティデータバッファ４５１は、第２パリティの各々を第２パリティデータとして保持するものである。第１符号化器４５２は、パリティデータバッファ４５１に保持された第２パリティデータを第１符号語に符号化するものである。第１符号化器４５２は、生成した第１符号語を符号化データバッファ４６０に保持させる。
【０１８９】
図３８は、第５の実施の形態における第２符号のデータ構成の一例を示す図である。第２符号は、複数の第１符号語を含む。これらの第１符号語のうち、一部の第１符号語は、第１符号化対象データを符号化したものであり、残りの第１符号語は、第２パリティデータを符号化したものである。例えば、第１符号語＃１乃至＃８は、第１符号化対象データを符号化したものであり、第１符号語＃９は、第２パリティデータを符号化したものである。第１符号語＃９は、第２パリティデータおよび第１パリティ＃９を含む。この第２パリティデータは、例えば、第１符号語＃１乃至＃８の誤りを訂正するための第２パリティ＃１乃至＃９を含む。
【０１９０】
［第２符号誤り検出訂正部の構成例］
図３９は、第５の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。第５の実施の形態の第２符号誤り検出訂正部５３０の構成は、第１符号誤り検出訂正器５３３をさらに備える点において第１の実施の形態と異なる。
【０１９１】
第１符号誤り検出訂正器５３３は、第２パリティの誤りを検出および訂正するものである。具体的には、第１符号誤り検出訂正器５３３は、入力された隣接部分データにおける第２パリティを含む第１符号語の誤りを検出および訂正し、隣接部分データの第２パリティを第１符号語の中から取り出して部分データ生成部５３２に供給する。部分データ生成部５３２は復号した第１符号語と第２パリティとから部分データを生成して、第２符号誤り検出訂正器５５０に供給する。
【０１９２】
このように、第５の実施の形態によれば、メモリコントローラ３００は第２パリティの誤りを訂正することができるため、データの誤りをより正確に訂正することができる。
【０１９３】
＜６．第６の実施の形態＞
［第２符号化部の構成例］
第１の実施の形態では、メモリコントローラ３００はデータを第１符号および第２符号に符号化していたが、第１符号および第２符号以外の符号をさらに生成してもよい。第６の実施の形態のメモリコントローラ３００は、第１符号および第２符号以外の符号をさらに生成する点において第１の実施の形態と異なる。
【０１９４】
図４０は、第６の実施の形態における第２符号化部４２０の一構成例を示すブロック図である。第６の実施の形態の第２符号化部４２０は、第３符号化器４２３をさらに備える点において第１の実施の形態と異なる。第３符号化器４２３は、第２符号化対象データを第３符号に符号化するものである。ここでは生成行列は第２符号化器４２２と第３符号化器４２３が保持しているものとする。
【０１９５】
ここで、第３符号は、第２符号のように部分的に復号することができない符号である。第２符号が空間結合ＬＤＰＣ符号の場合、例えば、第３符号として通常のＬＤＰＣ符号が用いられる。空間結合ＬＤＰＣ符号およびＬＤＰＣ符号を使用することにより、共通の誤り検出訂正器において、これらを復号することができる。この第３符号は、複数の第３符号語を含み、これらの全てを使用して誤りを訂正することにより、第２符号を部分的に訂正するよりも多くの誤りを訂正することができる。このため、第３符号は、第２符号の誤り訂正が失敗したときに用いられる。
【０１９６】
第３符号化器４２３は、第３符号語の各々を符号化データバッファ４６０に保持させる。第６の実施の形態の第２符号化器４２２は、第１の実施の形態と同様に空間結合ＬＤＰＣ符号への符号化を行う。
【０１９７】
図４１は、第６の実施の形態における検査行列の一例を示す図である。第６の実施の形態の検査行列は、検査行列＃１および＃２の２つの部分行列を含む。検査行列＃１は、空間結合ＬＤＰＣ符号の誤りを訂正するために用いられる行列であり、第１の実施の形態と同様の帯行列である。検査行列＃２は、ＬＤＰＣ符号の誤りを訂正するために用いられる行列であり、「１」の値の成分が非常に少ない疎行列である。
【０１９８】
図４２は、第６の実施の形態における第２符号誤り検出訂正部５３０の一構成例を示すブロック図である。第６の実施の形態の第２符号誤り検出訂正部５３０は、部分データ生成部５３２の代わりに、符号語生成部５３４を備える点において第１の実施の形態と異なる。符号語生成部５３４は、隣接部分データと誤りが検出された部分データとを順に生成して第２符号誤り検出訂正器５４０に供給する。符号語生成部５３４は、誤りが検出された部分データにおいて誤り訂正が成功したか否かを示す訂正結果を第２符号誤り検出訂正器５４０から受け取る。第２符合語の誤り訂正が失敗した場合には、符号語生成部５３４は、第３符号語全体を生成して第２符号誤り検出訂正器５４０に供給する。前述したように第３符号語の全てを訂正することにより、第２符号を部分的に訂正するよりも多くの誤りを訂正することができるため、符号全体の誤り訂正能力が向上する。
【０１９９】
このように、第６の実施の形態によれば、メモリコントローラ３００は、部分データの誤り訂正に失敗した場合でも、第３符号語の全ての誤りを訂正することにより、第２符号を部分的に訂正するよりも多くの誤りを訂正することができる。これにより、符号全体の誤り訂正能力が向上する。
【０２００】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２０１】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【０２０２】
なお、本技術は以下のような構成もとることができる。
（１）複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、
前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む前記部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正部と
を具備する誤り検出訂正装置。
（２）前記複数の部分データは、隣り合う部分データの一部のデータが共通の符号語であり、
前記第２符号誤り訂正部は、前記誤りが検出された第１符号語を含む前記部分データにおいて前記隣接部分データと共通の前記一部のデータに基づいて前記誤りを訂正する
前記（１）記載の誤り検出訂正装置。
（３）前記第２符号誤り訂正部は、前記隣接部分データの誤りを訂正し、前記隣接部分データの誤り訂正が成功した場合には前記第１符号誤り検出部により検出された前記誤りを前記隣接部分データに基づいて訂正する
前記（１）または（２）記載の誤り検出訂正装置。
（４）前記第２符号誤り訂正部は、前記隣接部分データの誤り訂正が失敗した場合には前記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データの誤りを訂正して前記新たな隣接部分データの誤り訂正が成功したか否かを判断する
前記（３）記載の誤り検出訂正装置。
（５）前記第２符号誤り訂正部は、前記隣接部分データに含まれる前記第１符号語に誤りが検出されていない場合には前記第１符号誤り検出部により検出された前記誤りを前記隣接部分データに基づいて訂正し、前記隣接部分データに含まれる前記第１符号語に誤りが検出されている場合には前記隣接部分データに隣接する部分データを新たな隣接部分データとして当該新たな隣接部分データに含まれる前記第１符号語に誤りが検出されているか否かを判断する
前記（３）または（４）記載の誤り検出訂正装置。
（６）前記第２符号誤り訂正部は、前記隣接部分データの誤り訂正が失敗した場合には前記第２符号語の誤りを訂正する
前記（３）記載の誤り検出訂正装置。
（７）前記第２符号誤り訂正部は、前記隣接部分データに基づいて行った前記誤りの訂正が成功したか否かを判断し、当該訂正が失敗した場合には各々が前記第１符号語を含む第３符号語に基づいて前記誤りを訂正する
前記（１）乃至（６）記載の誤り検出装置。
（８）前記第２符号語は畳込み符号語であり、
前記第２符号誤り訂正部は、前記隣接部分データにおいて畳込み演算が行われた結果に基づいて前記誤りを訂正する
前記（１）記載の誤り検出訂正装置。
（９）前記第２符号語はターボ符号語である
前記（８）記載の誤り検出訂正装置。
（１０）前記第２符号誤り訂正部は、前記誤りが検出された第１符号語を含む前記部分データと前記隣接部分データとを１つの復号単位として前記誤りを訂正する
前記（１）記載の誤り検出訂正装置。
（１１）前記複数の部分データは、部分データの各々の誤りを訂正するための第２パリティと、当該第２パリティの誤りを訂正するための第１パリティとを含み、
前記第２符号訂正部は、前記第１パリティを使用して前記第２パリティの誤りを訂正し、前記訂正した第２パリティを使用して前記部分データの誤りを訂正する
前記（１）乃至（１０）のいずれかに記載の誤り検出訂正装置。
（１２）前記複数の部分データの各々は、複数の前記第１符号語を含む
前記（１）乃至（１１）のいずれかに記載の誤り検出訂正装置。
（１３）複数の第１符号語を連鎖的に符号化することにより第２符号語を生成する第２符号化部と、
前記第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出部と、
前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正部と
を具備する情報処理装置。
（１４）第１符号誤り検出部が、複数の第１符号語を連鎖的に符号化することにより生成された第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出手順と、
第２符号誤り訂正部が、前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正手順と
を具備する誤り検出訂正方法。
（１５）第１符号誤り検出部が、複数の第１符号語を連鎖的に符号化することにより生成された複数の第２符号語において前記第１符号語の各々に誤りがあるか否かを検出する第１符号誤り検出手順と、
第２符号誤り訂正部が、前記第２符号語を複数の部分データからなる符号語として前記誤りが検出された第１符号語を含む部分データに隣接する部分データである隣接部分データに基づいて前記誤りを訂正する第２符号誤り訂正手順と
をコンピュータに実行させるためのプログラム。
【符号の説明】
【０２０３】
１００  ホストシステム
２００  ストレージシステム
３００  メモリコントローラ
３１０  ホストインターフェース
３２０  ＲＡＭ
３３０  ＣＰＵ
３４０  ＲＯＭ
３５０  不揮発性メモリインターフェース
３６０  バス
４００  ＥＣＣ処理部
４１０  第１符号化部
４２０  第２符号化部
４２１  第２符号化対象データ生成部
４２２、４３０、４４０  第２符号化器
４２３  第３符号化器
４３１、４３４  半加算器
４３２、４３３  レジスタ
４４１  入替前第２符号化器
４４２  遅延バッファ
４４３  インタリーバ
４４４  入替後第２符号化器
４４５  スイッチ
４５１  パリティデータバッファ
４５２  ブロック符号化器
４６０  符号化データバッファ
４７０  符号化データ供給部
５２０  第１符号誤り検出訂正部
５３０  第２符号誤り検出訂正部
５３１  検査行列生成部
５３２  部分データ生成部
５３３  第１符号誤り検出訂正器
５３４  符号語生成部
５４０、５５０、５６０  第２符号誤り検出訂正器
５４１  変数ノード処理部
５４２  変数ノード
５４３  検査ノード処理部
５４４  検査ノード
５６１  入替前第２符号訂正器
５６２  インタリーバ
５６３  入替後第２符号訂正器
５６４  デインタリーバ
５７０  復号データバッファ
５８０  復号データ供給部
６００  不揮発性メモリ
【図１】
2014154899.tif 000023
【図２】
2014154899.tif 000024
【図３】
2014154899.tif 000025
【図４】
2014154899.tif 000026
【図５】
2014154899.tif 000027
【図６】
2014154899.tif 000028
【図７】
2014154899.tif 000029
【図８】
2014154899.tif 000030
【図９】
2014154899.tif 000031
【図１０】
2014154899.tif 000032
【図１１】
2014154899.tif 000033
【図１２】
2014154899.tif 000034
【図１３】
2014154899.tif 000035
【図１４】
2014154899.tif 000036
【図１５】
2014154899.tif 000037
【図１６】
2014154899.tif 000038
【図１７】
2014154899.tif 000039
【図１８】
2014154899.tif 000040
【図１９】
2014154899.tif 000041
【図２０】
2014154899.tif 000042
【図２１】
2014154899.tif 000043
【図２２】
2014154899.tif 000044
【図２３】
2014154899.tif 000045
【図２４】
2014154899.tif 000046
【図２５】
2014154899.tif 000047
【図２６】
2014154899.tif 000048
【図２７】
2014154899.tif 000049
【図２８】
2014154899.tif 000050
【図２９】
2014154899.tif 000051
【図３０】
2014154899.tif 000052
【図３１】
2014154899.tif 000053
【図３２】
2014154899.tif 000054
【図３３】
2014154899.tif 000055
【図３４】
2014154899.tif 000056
【図３５】
2014154899.tif 000057
【図３６】
2014154899.tif 000058
【図３７】
2014154899.tif 000059
【図３８】
2014154899.tif 000060
【図３９】
2014154899.tif 000061
【図４０】
2014154899.tif 000062
【図４１】
2014154899.tif 000063
【図４２】
2014154899.tif 000064