(57)【特許請求の範囲】
【請求項１】
不揮発性メモリを制御するメモリコントローラであって、
ユーザデータに誤り訂正符号化処理を行うことにより第１乃至第ｎパリティを生成し、前記第１乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第１乃至第ｎ外部パリティを生成する符号化部と、
前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティの前記不揮発性メモリへの書込み、及び前記不揮発性メモリからの読み出しを制御するメモリインタフェース部と、
前記不揮発性メモリから読み出される前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行う復号部と、
を備え、
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とするメモリコントローラ。
【請求項２】
前記復号部は、前記第１乃至第ｋ外部パリティ（ｋは１以上ｎ以下の整数）を用いて前記第１乃至第ｋパリティの誤り訂正復号処理を行った後に、前記第１乃至第ｋパリティを用いて前記ユーザデータの誤り訂正復号処理を行うことを特徴とする請求項１に記載のメモリコントローラ。
【請求項３】
不揮発性メモリを制御するメモリコントローラであって、
ユーザデータに誤り訂正符号化処理を行うことにより第１パリティを生成し、前記ユーザデータと前記第１パリティに誤り訂正符号化処理を行うことにより第２パリティを生成し、前記ユーザデータと前記第１パリティに誤り訂正符号化処理を行うことにより第ｎパリティを生成し、さらに、前記第２乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第２乃至第ｎ外部パリティを生成する符号化部と、
前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第２乃至第ｎ外部パリティの前記不揮発性メモリへの書込み、及び前記不揮発性メモリからの読み出しを制御するメモリインタフェース部と、
前記不揮発性メモリから読み出される前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第２乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行う復号部と、
を備え、
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とするメモリコントローラ。
【請求項４】
前記復号部は、前記第１パリティの誤り訂正能力では前記ユーザデータの誤り訂正復号できない場合に、前記第２乃至第ｋ外部パリティ（ｋは２以上ｎ以下の整数）を用いて前記第２乃至第ｋパリティの誤り訂正復号処理を行った後に、前記第２乃至第ｋパリティを用いて前記ユーザデータ及び前記第１パリティの誤り訂正を行うことを特徴とする請求項３に記載のメモリコントローラ。
【請求項５】
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式Ｇi（ｘ）は、ｒi、ｔiを整数とした場合に、
ｒ1，ｒ2，…，ｒnは、以下の関係を満たし、
ｒ2≦ｒ1、ｒ1＋２ｔ1−１≦ｒ2＋２ｔ2−１
ｒ3≦ｒ2、ｒ2＋２ｔ2−１≦ｒ3＋２ｔ3−１
…
ｒn≦ｒn-1、n-1＋２ｔn-1−１≦ｒn＋２ｔn−１
Ｇ1（ｘ）×Ｇ2（ｘ）×…×Ｇi（ｘ）＝０が、αri，αri+1，αri+2，…，α2ti+ri-2，α2ti+ri-1の２×ｔi個の根を有するよう選択されることを特徴とする請求項１乃至４いずれか１項に記載のメモリコントローラ。
【請求項６】
前記第１乃至第ｎパリティの生成する誤り訂正符号処理には、同一の誤り訂正符号が用いられることを特徴とする請求項１乃至５いずれか１項に記載のメモリコントローラ。
【請求項７】
前記誤り訂正符号は、ＢＣＨ符号であることを特徴とする請求項６に記載のメモリコントローラ。
【請求項８】
前記パリティ及び前記外部パリティの少なくとも一部は、前記ユーザデータとは異なる、パリティを格納する専用のパリティ専用ページに格納されることを特徴とする請求項１乃至７いずれか１項に記載のメモリコントローラ。
【請求項９】
前記パリティ及び前記外部パリティの少なくとも一部は、パリティの保護対象であるユーザデータまたはパリティとは異なるユーザデータページに格納されることを特徴とする請求項１乃至７いずれか１項に記載のメモリコントローラ。
【請求項１０】
不揮発性メモリを制御するメモリコントローラであって、
第１ユーザデータに誤り訂正符号化処理を行うことにより、第１パリティを生成し、前記第１ユーザデータと前記第１パリティに誤り訂正符号処理を行うことにより第２パリティを生成し、第２ユーザデータと前記第２パリティを含む複数のパリティに誤り訂正符号処理を行うことにより第３パリティを生成する符号化部と、
前記第１ユーザデータと前記第１パリティの第１ページへの書込み、及び前記第２ユーザデータ及び前記第２のパリティを含む複数のパリティ、第３パリティの第２ページへの書込みを制御するメモリインタフェース部と、
前記不揮発性メモリから読み出される前記第１、第２ユーザデータ及び前記第１乃至第３パリティに基づき、誤り訂正復号処理を行う復号部と、
を備え、
前記第２パリティを生成するために用いられる生成多項式は、第１パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とするメモリコントローラ。
【請求項１１】
前記第１パリティのサイズは、前記第２パリティのサイズと前記第３のパリティのサイズの和以上であることを特徴とする請求項１０に記載のメモリコントローラ。
【請求項１２】
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式Ｇi（ｘ）は、ｒ1、ｔ1、ｒ2、ｔ2、ｒ3、ｔ3を整数とした場合に、
ｒ1、ｔ1、ｒ1，ｒ2、ｒ3、ｔ3は、以下の関係を満たし、
ｒ2≦ｒ1、ｒ1＋２ｔ1−１≦ｒ2＋２ｔ2−１
ｒ3≦ｒ2、ｒ2＋２ｔ2−１≦ｒ3＋２ｔ3−１
Ｇ1（ｘ）×Ｇ2（ｘ）×…×Ｇi（ｘ）＝０が、αri，αri+1，αri+2，…，α2ti+ri-2，α2ti+ri-1の２×ｔi個の根を有するよう選択されることを特徴とする請求項１０又は１１に記載のメモリコントローラ。
【請求項１３】
不揮発性メモリと、
ユーザデータに誤り訂正符号化処理を行うことにより第１乃至第ｎパリティを生成し、前記第１乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第１乃至第ｎ外部パリティを生成する符号化部と、
前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティの前記不揮発メモリへの書込み、及び前記不揮発性メモリからの読み出しを制御するメモリインタフェース部と、
前記不揮発性メモリから読み出される前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第1乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行う復号部と、
を備え、
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とする記憶装置。
【請求項１４】
ユーザデータに誤り訂正符号化処理を行うことにより第１乃至第ｎパリティを生成し、前記第１乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第１乃至第ｎ外部パリティを生成する符号化部と、
受信した前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行う復号部と、
を備え、
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とする誤り訂正装置。
【請求項１５】
不揮発性メモリを制御するメモリコントローラにおける誤り訂正方法であって、
ユーザデータに誤り訂正符号化処理を行うことにより第１乃至第ｎパリティを生成するステップと、
前記第１乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第１乃至第ｎ外部パリティを生成するステップと、
前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティの前記不揮発メモリへの書込むステップと、
前記不揮発性メモリから前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティの読み出しを行うステップと、
前記不揮発性メモリから読み出される前記ユーザデータ、前記第１乃至第ｎパリティ、及び前記第１乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行うステップと、
を備え、
前記第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択されることを特徴とする誤り訂正方法。
【請求項１６】
前記復号部は、
第１乃至第ｎパリティの全てを用いた場合の訂正能力をｔnビットとするとき、ｔnビット以上の演算に対応可能なシンドローム計算部、を備え、
前記シンドローム計算部は、第１乃至第ｎパリティを生成するために用いられる生成多項式の各根に対応するシンドロームを計算するｔn個以上のシンドローム計算回路、を有し、
第ｉパリティを生成するために用いられる生成多項式をＧiとするとき、Ｇ1乃至Ｇn-1に含まれる根に対応する前記シンドローム計算回路は、ユーザデータ、またはユーザデータおよび第１乃至第（ｎ−１）パリティのうちの少なくとも１つと、０と、のうちいずれか一方を選択する選択回路と、
を備え、
前記第１乃至第ｉパリティを用いた前記ユーザデータの誤り訂正処理と第ｉ誤り訂正処理とするとき、第１乃至第ｎ誤り訂正処理を前記シンドローム計算部により実施することを特徴とする請求項１に記載のメモリコントローラ。
【請求項１７】
第ｉ誤り訂正処理では、Ｇiに含まれる根に対応する前記シンドローム計算回路以外の前記シンドローム計算回路の動作を停止させる、ことを特徴とする請求項１６に記載のメモリコントローラ。
【請求項１８】
前記シンドローム計算回路がＰ（Ｐは２以上の整数）ビット並列演算を行う場合に、
前記符号化部は、前記第１乃至第ｎパリティのうちビット数がＰの倍数でないパリティがある場合、当該パリティのビット数がＰの倍数となるようゼロ挿入処理を実施する、ことを特徴とする請求項１６または１７に記載のメモリコントローラ。
【請求項１９】
前記ゼロ挿入処理を、前記第１乃至第ｎパリティのうちビット数がＰの倍数でないパリティの生成処理において、当該パリティのビット数がＰの倍数となるよう前記生成処理へゼロを入力する処理とすることを特徴とする請求項１８に記載のメモリコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、メモリコントローラ、記憶装置、誤り訂正装置および誤り訂正方法に関する。
【背景技術】
【０００２】
メモリに格納されたユーザデータをメモリから読み出した場合に、本来の値と異なった値に変化したり、送信装置が送信したデータが受信装置に受信されると受信されたデータが本来の値と異なった値に変化したり、等の現象が生じることがある。
【０００３】
この問題に対応するために、ユーザデータを誤り訂正符号化してパリティデータを生成し、ユーザデータとパリティデータを組にして管理するという方法が一般的に取られる。誤り訂正符号としては、例えば、ＢＣＨ符号やＲＳ（リードソロモン）符号が存在する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第７４１８６４４号明細書
【特許文献２】特開２００５−５６３９７号公報
【特許文献３】特開２００９−２１１２０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、ユーザデータに対して、誤りの規模に応じて処理量を変更する適応的な誤り訂正を行うことができない。
【課題を解決するための手段】
【０００６】
本実施形態によれば、ユーザデータに誤り訂正符号化処理を行うことにより第１乃至第ｎパリティを生成し、第１乃至第ｎパリティ各々に誤り訂正符号化処理を行うことにより第１乃至第ｎ外部パリティを生成する符号化部と、ユーザデータ、第１乃至第ｎパリティ、及び第１乃至第ｎ外部パリティを用いて、誤り訂正復号処理を行う復号部と、を備え、第ｉパリティ（ｉは１以上ｎ以下の整数）を生成するために用いられる生成多項式は、第１乃至第（ｉ−１）パリティを生成するために用いられる生成多項式に基づいて選択される。
【図面の簡単な説明】
【０００７】
【図１】図１は、第１の実施の形態にかかるメモリシステムの構成例を示すブロック図である。
【図２】図２は、第１の実施の形態のパリティの格納概念の一例を示す図である。
【図３】図３は、第１の実施の形態の符号演算の概念を示す図である。
【図４】図４は、第１の実施の形態の復号演算の概念を示す図である。
【図５】図５は、第１の実施の形態の符号演算手順の一例を示すフローチャートである。
【図６】図６は、第１の実施の形態の復号演算手順の一例を示すフローチャートである。
【図７】図７は、ユーザデータとパリティの格納形式の例を示す図である。
【図８】図８は、ユーザデータとパリティの格納形式の例を示す図である（パリティ数がユーザデータにより異なる例）。
【図９】図９は、ユーザデータとパリティの格納形式の例を示す図である（複数の記憶装置に格納する例）。
【図１０】図１０は、第２の実施の形態にかかるメモリシステムの構成例を示すブロック図である。
【図１１】図１１は、第２の実施の形態の符号演算の概念を示す図である。
【図１２】図１２は、第３の実施の形態にかかるメモリシステムの構成例を示すブロック図である。
【図１３】図１３は、パリティ保護表の一例を示す図である。
【図１４】図１４は、第３の実施の形態の符号演算の概念を示す図である。
【図１５】図１５は、第３の実施の形態の復号演算の概念とユーザデータおよびパリティの格納例を示す図である。
【図１６】図１６は、ユーザデータ１個とパリティ複数個とから外部パリティを計算する場合のユーザデータおよびパリティの格納例を示す図である。
【図１７】図１７は、ユーザデータとパリティの格納形式の例を示す図である（パリティ専用ページにパリティを格納する例）。
【図１８】図１８は、ユーザデータとパリティの格納形式の例を示す図である（パリティ専用ページにパ８ティを格納し、ページによりパリティ量が異なる例）。
【図１９】図１９は、ユーザデータとパリティの格納形式の例を示す図である（パリティ専用ページにパリティを格納し、他のページにもパリティを格納する例）。
【図２０】図２０は、第４の実施の形態にかかる誤り訂正装置を備える通信装置の構成例を示すブロック図である。
【図２１】図２１は、第５の実施の形態にかかる半導体記憶装置における復号部の構成例を示すブロック図である。
【図２２】図２２は、第５の実施の復号処理手順の一例を示すフローチャートである。
【図２３】図２３は、シンドローム計算部の構成例を示す図である。
【図２４】図２４は、１段階目の誤り訂正処理における回路使用状態を示す図である。
【図２５】図２５は、第５の実施の形態のシンドローム計算の処理手順の一例を示すフローチャートである。
【図２６】図２６は、外部パリティを用いた復号も行う場合の復号部の構成例を示す図である。
【図２７】図２７は、第６の実施の形態にかかる半導体記憶装置におけるシンドローム計算部のシンドロームＳi計算回路の構成例を示すブロック図である。
【図２８】図２８は、第６の実施の形態のデータフォーマットの一例を示す図である。
【図２９】図２９は、ｄ1ビットのゼロパディングの位置をパリティ＃１の最後の部分とした場合のデータフォーマットの一例を示す図である。
【図３０】図３０は、３段階の誤り訂正方式を採用する場合のデータフォーマットの一例を示す図である。
【図３１】図３１は、復号時のＰビット並列処理に対応したパリティ＃ｎを生成するための符号化部の構成例を示す図である。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態にかかるメモリコントローラ、記憶装置、誤り訂正装置および誤り訂正方法を詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００９】
（第１の実施の形態）
図１は、第１の実施の形態にかかるメモリシステムの構成例を示すブロック図である。本実施の形態の半導体記憶装置（記憶装置）１は、メモリコントローラ２と半導体メモリ部（不揮発性メモリ）３を備える。記憶装置１は、ホスト４と接続可能であり、図１ではホスト４と接続された状態を示している。ホスト４は、例えば、パーソナルコンピュータ、携帯端末などの電子機器である。
【００１０】
半導体メモリ部３は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤメモリである。なお、ここでは、半導体メモリ部３としてＮＡＮＤメモリを用いる例を説明するが、半導体メモリ部３としてＮＡＮＤメモリ以外の記憶手段を用いてもよい。ＮＡＮＤメモリでは、一般にページと言われる書込み単位（最小書込み）が存在し、ページ単位で書込みが行われる。
【００１１】
メモリコントローラ２は、ホスト４からの書込みコマンド（要求）に従って半導体メモリ部３への書込みを制御し、またホスト４からの読み出しコマンド（要求）に従ってＮＡＮＤメモリ３からの読み出しを制御する。メモリコントローラ２は、ＨｏｓｔＩ／Ｆ２１、メモリＩ／Ｆ２２、制御部２３、符号化／復号部２４を備える。符号化／復号部２４は、符号化部２５と復号部２６を備える。ＨｏｓｔＩ／Ｆ２１、メモリＩ／Ｆ２２、制御部２３、符号化部２５および復号部２６は、内部バス２０で接続されている。
【００１２】
ＨｏｓｔＩ／Ｆ２１は、ホスト４との間のインタフェース規格に従った処理を実施し、ホスト４から受信した命令、ユーザデータなどを内部バス２０に出力する。また、ＨｏｓｔＩ／Ｆ２１は、半導体メモリ部３から読み出されたユーザデータ、制御部２３からの応答などをホスト４へ送信する。
【００１３】
メモリＩ／Ｆ２２は、制御部２３の指示に基づいて、書込みデータを半導体メモリ部３へ書込む処理および半導体メモリ部３からの読み出し処理を制御する。
【００１４】
制御部２３は、半導体記憶装置１の各構成要素を統括的に制御する制御部である。制御部２３は、ホスト４からＨｏｓｔＩ／Ｆ２１経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部２３は、ホスト４からの命令に従って、半導体メモリ部３へのユーザデータおよびパリティの書き込み、半導体メモリ部３からのユーザデータの読み出しなどを、メモリＩ／Ｆ２２へ指示する。
【００１５】
符号化部２５は、内部バス２０に転送されたデータに基づいて、誤り訂正符号化処理を実施しパリティを生成する。誤り訂正符号としてはどのような符号を用いてもよいが、例えば、ＢＣＨ符号やＲＳ（Reed−Solomon）符号等を用いることができる。以下の説明では、ＢＣＨ符号を用いる例について説明するが、誤り訂正符号の種類はこれに限定されないが、符号化後に情報データとパリティとに分離できる符号が好ましい。
【００１６】
復号部２６は、半導体メモリ部３からの読み出されたユーザデータおよびパリティに基づいて復号処理を実施する。ユーザデータに誤りの無い場合、半導体メモリ部３からの読み出されたユーザデータをそのまま内部バス２０へ出力し、ユーザデータに誤りのある場合、パリティを用いて誤り訂正を行った後にユーザデータを内部バス２０へ出力する。
【００１７】
ＮＡＮＤメモリでは、ページ単位で書込みが行われるが、信頼性の異なる（誤りの発生する確率が異なる）ページが存在することがある。例えば、ＮＡＮＤメモリのメモリセルとして多値セルを用いる場合、一般に、１つのメモリセルに格納される各ｂｉｔには異なるページが割当てられる。例えば、１つのメモリセルに格納されるビットを３ビットとすると、３ビットにはそれぞれ異なるページが割当てられる。このような場合、ページにより信頼性が異なることがある。
【００１８】
信頼性の低いページでは、誤り訂正能力の高いパリティを生成しておくことが望ましい。誤り訂正能力の高いパリティを実現するためにはパリティのサイズを大きくすることになるが、ＮＡＮＤメモリの各ページのサイズは同一である。このため、信頼性の低いページに対応した誤り訂正能力のパリティを生成するためには、例えば、信頼性の低いページのパリティを２つに分割して、信頼性の高いページに分割したうちの１つのパリティを格納する方法が考えられる。しかし、この方法では、信頼性の低いページのユーザデータを読み出す際に、分割したパリティを格納した別のページも読み出す必要があり、読み出し速度が低下する。また、信頼性の低いページでも、実際にはほとんどのページでは、誤りは無いまたは誤り数が最大の想定数より少ない場合が多く、信頼性の高いページに対応した誤り訂正能力で十分対応可能である。
【００１９】
本実施の形態では、誤り訂正符号として、誤り訂正能力を高めた分のパリティを追加することにより段階的に誤り訂正能力の高い符号化を行うことが可能な符号を用いる。図２は、本実施の形態のパリティの格納概念の一例を示す図である。図２の上側には、比較例として、信頼性の低いページのユーザデータ＃１に対して誤り訂正能力の高いパリティ＃１を生成し、信頼性の高いページのユーザデータ＃２に対して誤り訂正能力の低いパリティ＃２を生成して格納した例を示している。このように信頼性の高さに応じて誤り訂正能力を変えてパリティを生成してユーザデータと同一のページに格納するとページごとにパリティのサイズが異なることになってしまう。
【００２０】
これに対して、図２の下側に示した本実施の形態では、１段階で誤り訂正能力の高いパリティ＃１を生成するのではなく、１段階目としてユーザデータ＃１に基づいて所定の誤り訂正能力を有するパリティ＃１−１を生成し、２段階目としてユーザデータ＃１とパリティ＃１−１を用いてパリティ＃１−２を生成し、３段階目としてユーザデータ＃１とパリティ＃１−１とパリティ＃１−２を用いてパリティ＃１−３を生成し、…というように段階的にパリティを生成する。そして、復号時には、まず、パリティ＃１−１を用いて復号を行い誤り訂正不可であった場合に、パリティ＃１−２を読み出し、パリティ＃１−１およびパリティ＃１−２を用いて復号を行い誤り訂正不可であった場合にパリティ＃１−３を読み出し、…というように段階的に復号を行う。このような符号化および復号化を行うと、例えば、図２に示すように、信頼性の低い（平均誤りビット数の多い）ページ＃１にユーザデータ＃１を格納する場合、ユーザデータ＃１に基づいて生成したパリティ＃１−１を当該パリティに対応するユーザデータ＃１が格納されるページに格納し、パリティ＃１−２を信頼性の高いページ＃２に格納することができる。復号時には通常は、まずユーザデータ＃１およびパリティ＃１−１を読み出す。このように構成しておくと、パリティ＃１−１を用いた復号で誤り訂正が可能であった場合には、ページ＃１以外のページ（図２の例ではページ＃２）を読み出さなくてよい。なお、図２では、図の簡略化のため、２段階のパリティを例に説明しているが、本実施の形態のパリティの生成は２段階に限らず、後述するように何段階で生成してもよい。
【００２１】
一方、パリティを多段階に分けて生成する方法として、独立した符号化処理を段階的に行う方法も考えられる。例えば、１段階目としてユーザデータに対して所定の誤り能力を有するパリティＡを生成する。そして、２段階目としてユーザデータに基づいて別の符号化処理により所定の誤り能力より高い誤り能力を有するパリティＢを生成し、図２と同様に、ユーザデータと同一ページにパリティＡを格納し、同一でないページにパリティＢを格納するということも考えられる。しかし、この場合、パリティＢはパリティＡとはまったく独立に生成されているため、パリティＢを用いた復号の際にパリティＡを用いることができない。一方、上述した誤り訂正能力を高めた分のパリティを追加する符号を用いれば、パリティ＃１−２を用いた復号の際にパリティ＃１−１も用いることができる。したがって、合計のパリティサイズが同じであれば、誤り訂正能力を高めた分のパリティを追加する符号の方が独立した多段階の符号化に比べ高い誤り訂正能力を有し、また、同じ誤り訂正能力であれば、誤り訂正能力を高めた分のパリティを追加する符号の方がパリティのサイズが少なくてすむ。
【００２２】
このため、本実施の形態では、ｉ（ｉは２以上ｎ以下の整数）段階目のパリティのサイズは、１乃至ｉ段階目の全てのパリティを用いて誤り訂正を行う場合と同等の誤り訂正能力を有するよう単独で生成されるパリティのサイズより小さくなるようにｎ段階でパリティを生成する。例えば、上記の例では、本実施の形態の２段階目のパリティであるパリティ＃１−２のサイズは、パリティＡと独立に生成した２段階目のパリティであるパリティＢのサイズより小さい。
【００２３】
以下、本実施の形態の誤り訂正符号化処理（以下、符号演算と略す）および復号演算について説明する。図３は、本実施の形態の符号演算の概念を示す図である。図３に示すように、本実施の形態の符号化部２５は、符号演算として次のようにｎ段階でパリティを計算する。
（１）ユーザデータを用いてＧ1（ｘ）によりパリティ＃１を計算。
（２）ユーザデータ＋パリティ＃１を用いてＧ2（ｘ）によりパリティ＃２を計算。
（３）ユーザデータ＋パリティ＃１＋パリティ＃２を用いてＧ3（ｘ）によりパリティ＃３を計算。
…
（ｎ）ユーザデータ＋パリティ＃１＋パリティ＃２＋…＋パリティ＃（ｎ−１）を用いてＧn（ｘ）によりパリティ＃ｎ（ｎは１以上の整数）を計算。
なお、Ｇi（ｘ）（ｉ＝１，２,…，ｎ）は生成多項式であり、Ｇi（ｘ）については後述する。
【００２４】
図４は、本実施の形態の復号演算の概念を示す図である。図４に示すように、本実施の形態の復号部２６は、復号演算として、次のようにｎ段階で誤り訂正を実施する。
（１）パリティ＃１を用いてユーザデータ＋パリティ＃１の誤り訂正を実施する。
（２）（１）の誤り訂正に失敗した場合、パリティ＃１〜パリティ＃２を用いてユーザデータ＋パリティ＃１＋パリティ＃２の誤り訂正を実施する。
（３）（２）の誤り訂正に失敗した場合、パリティ＃１〜パリティ＃３を用いてユーザデータ＋パリティ＃１＋パリティ＃２＋パリティ＃３の誤り訂正を実施する。
…
（ｎ）（ｎ−１）の誤り訂正に失敗した場合、パリティ＃１〜パリティ＃ｎを用いてユーザデータ＋パリティ＃１＋パリティ＃２＋パリティ＃３＋…＋パリティ＃ｎの誤り訂正を実施する。
【００２５】
なお、各段階で、誤り訂正に失敗した場合に次の段階へ進み、各段階で誤り訂正に成功した場合は次の段階へは進まず復号演算を終了する。ｎ段階目の誤り訂正処理で誤り訂正に失敗した場合は、復号部２６は、誤り訂正に失敗したことを制御部２３へ通知する。制御部２３は、誤り訂正に失敗した場合の所定の手順（例えば、ホスト４へ読み出したユーザデータに誤りがあることを通知する等）を実施する。
【００２６】
また、パリティ＃１を用いてユーザデータ＋パリティ＃１の復号処理を実施した際に、ユーザデータに誤りが無かった場合は、ユーザデータに対して誤り訂正は実施せず、読み出したユーザデータをそのまま出力する。なお、ユーザデータに誤り検出符号を付加しておいて、誤り検出符号を用いてユーザデータの誤りの有無を判定するようにしてもよい。
【００２７】
以上の演算を実施する場合に、パリティ＃１からパリティ＃ｉまでを用いて誤り訂正を行うよりも、パリティ＃１からパリティ＃（ｉ＋１）までを用いて誤り訂正を行う方がより強力な誤り訂正能力を有するようにするために、本実施の形態では、例えば、以下のような符号演算を実施する。
【００２８】
なお、以下の説明では、ＢＣＨ符号を用いる場合の符号演算方法および復号演算方法について説明するが、ＢＣＨ符号に限定されるものではない。
【００２９】
まず、ＢＣＨ符号に関する一般的な説明を行う。ユーザデータ、パリティ、符号語などは０または１の値の列であり、これらを表現するためには様々な方法が存在するが、ここでは、多項式表現を用いて説明する。例えば、ユーザデータ１０１０１は、多項式表現によりユーザデータ多項式ｘ4＋ｘ2＋１と表現することができる。
【００３０】
符号演算に際しては、ユーザデータ多項式に生成多項式と呼ばれる多項式を用いた四則演算を施して、パリティの多項式表現であるパリティ多項式を計算する。そして、ユーザデータ多項式とパリティ多項式を組み合わせることで符号多項式を計算する。
【００３１】
上記四則演算は、
・ガロア体ＧＦ（２）
・ガロア拡大体ＧＦ（２m）
・原始多項式
・最小多項式
に基づいて行われるが、これらに関しては、詳細は省略する。
【００３２】
ガロア拡大体ＧＦ（２m）は２m種類の元があり、それらは、０，１，α，α2，α3，…，αM-1，αM（Ｍ＝２m−２）と表現される。
【００３３】
生成多項式を用いて計算される符号多項式に誤りが加わった結果（時間の経過とともに様々なストレスを受けた結果）得られる多項式を受信多項式とするとき、受信多項式に基づいて誤り多項式を計算し、誤り多項式を用いて符号多項式が計算可能であるためには、生成多項式を適切に選択する必要がある。
【００３４】
具体的には、ｔビットの誤りが計算可能であるためには、生成多項式＝０が、ｒを任意の整数とし、αr，αr+1，αr+2，…，α2t+r-2，α2t+r-1の２ｔ個の根を持っていればよい（ＢＣＨ限界)。
【００３５】
次に、以上行ったＢＣＨ符号の説明に基づき、本実施の形態における生成多項式の選択方法の説明を行う。図３に示したｎ段階の誤り訂正符号では、Ｇ1（ｘ），Ｇ2（ｘ），…，Ｇn（ｘ）のｎ個の生成多項式を用いて符号化を行う。なお、以下、添え字付の文字（ｒ1、ｂｂ1等）を、上付文字（指数の肩）や添え字（下付文字）のなかで用いる場合、上付または下付ではない表記（ｒ1、ｂｂ1等）で記載するが、両者は同じものを示している。
【００３６】
このとき、
（１）ｒ1を整数とし、Ｇ1（ｘ）＝０がαr1，αr1+1，αr1+2，…，α2t1+r1-2，α2t1+r1-1の２ｔ1（＝２×ｔ1）個の根を持っており、
（２）ｒ2を整数とし、Ｇ1（ｘ）＊Ｇ2（ｘ）＝０が、αr2，αr2+1，αr2+2，…，α2t2+r2-2，α2t2+r2-1の２ｔ2個の根を持っており、
…
（ｎ）ｒnを整数とし、Ｇ1（ｘ）＊Ｇ2（ｘ）…＊Ｇn（ｘ）＝０が、αrn，αrn+1，αrn+2，…，α2tn+rn-2，α2tn+rn-1の２ｔn個の根を持っている、
というｎ種の条件を満たすようにｎ個の生成多項式Ｇ1（ｘ），Ｇ2（ｘ），…，Ｇn（ｘ）を選択する。なお、ｒ1，ｒ2，…，ｒnは、以下の関係を満たす。
・ｒ2≦ｒ1、ｒ1＋２ｔ1−１≦ｒ2＋２ｔ2−１
・ｒ3≦ｒ2、ｒ2＋２ｔ2−１≦ｒ3＋２ｔ3−１
…
・ｒn≦ｒn-1、
ｒn-1＋２ｔn-1−１≦ｒn＋２ｔn−１
これにより、ｔn＞ｔn-1＞…＞ｔ2＞ｔ1となる。
【００３７】
上記の生成多項式選択を行うと、
ｔ0＝０、ｂi＝ｔi−ｔi-1（１≦ｉ≦ｎ）とするとき、
Ｇi（ｘ）によって計算されるパリティ＃ｉは、ｂiビットの訂正能力を持つ。
【００３８】
また、上記の生成多項式選択を行うと、パリティ＃１からパリティ＃ｉを用いると、ユーザデータ＋パリティ＃１＋パリティ＃２＋…＋パリティ＃ｉ内にｔiビットまでの誤りがある場合に、ユーザデータ内の誤りを訂正し、ユーザデータが本来取るべき値を得ることが可能である。
【００３９】
したがって、上記の生成多項式選択を行うと、パリティ＃１からパリティ＃ｎを用いると、ユーザデータ＋パリティ＃１＋パリティ＃２＋…＋パリティ＃ｎ内にｔnビットまでの誤りがある場合にユーザデータ内の誤りを訂正し、ユーザデータが本来取るべき値を得ることが可能である。
【００４０】
上記のｎ−１種の条件を満たすよう選択した生成多項式の一例として、ｒ1＝ｒ2＝…＝ｒn＝１とした例を説明する。αiを根とするＧＦ（２）上の最小多項式をＭi（ｘ）と置く。０＜ｂｂ1＜ｂｂ2＜ｂｂ3＜…＜ｂｂnを満たす任意の整数ｂｂ1、ｂｂ2、ｂｂ3、…、ｂｂnに関して以下の式（１）のようにＧＧi（ｘ）を置く。
ＧＧi（ｘ）＝Ｍ1（ｘ）＊Ｍ3（ｘ）＊Ｍ5（ｘ）＊
…＊Ｍ2bbi-1（ｘ）  （１≦ｉ≦ｎ）    …（１）
【００４１】
このとき、ＧＧi（ｘ）を生成多項式とするＢＣＨ符号はｂｂiビットまでの誤り訂正が可能である。
【００４２】
以下の式（２）のように、Ｇi（ｘ）を置くと、
Ｇ0（ｘ）＝１、
Ｇi（ｘ）＝ＧＧi（ｘ）／ＧＧi-1（ｘ）
＝Ｍ2bb(i-1)+1（ｘ）＊Ｍ2bb(i-1)+3（ｘ）＊
…＊Ｍ2bbi-1  （１≦ｉ≦ｎ）      …（２）
なお、ｂｂ（ｉ−１）＝ｂｂi-1とする。
【００４３】
式（２）で示した生成多項式は、上記のｎ−１種の条件を満たすよう選択した生成多項式の一例となり、上記のｎ−１種の条件において、ｂi＝ｂｂi−ｂｂi-1とし、ｔi＝ｂｂiとした例に相当する。
【００４４】
図５は、本実施の形態の符号演算手順の一例を示すフローチャートである。図５の手順は、上記で説明した生成多項式を選択してｎ段階の符号化を行う場合の符号演算手順を示している。まず、ｉ＝１とし、符号語＃０をユーザデータ（符号語＃０＝ユーザデータ）とする（ステップＳ１）。次に、符号語＃ｉを符号語＃（ｉ−１）×ｘK（Ｋは生成多項式Ｇi（ｘ）の次数）とする（符号語＃ｉ＝符号語＃（ｉ−１）×ｘK）（ステップＳ２）。パリティ＃ｉを、符号語＃ｉの生成多項式Ｇi（ｘ）による剰余として求める（ステップＳ３）。
【００４５】
そして、符号語＃ｉにパリティ＃ｉを加えて符号語＃ｉを更新（符号語＃ｉ＝符号語＃ｉ＋パリティ＃ｉ）する（ステップＳ４）。その後、ｉ＝ｉ＋１とし（ステップＳ５）、ｎ＜ｉであるか否かを判断する（ステップＳ６）。ｎ＜ｉである場合（ステップＳ６  Ｙｅｓ）、処理を終了し、ｎ＜ｉでない場合（ステップＳ６  Ｎｏ）、ステップＳ２に戻る。
【００４６】
図６は、本実施の形態の復号演算手順の一例を示すフローチャートである。図６の手順は、図５で説明した符号演算を行った符号語が、半導体メモリ部３に格納された後に、読み出された場合の復号部２６における復号手順を示している。まず、ｉ＝１とし、ユーザデータとパリティ＃１を受信する（ステップＳ１２）。具体的には、制御部２３の指示に基づいてメモリＩ／Ｆ２２が半導体メモリ部３から読み出したユーザデータと当該ユーザデータに対応するパリティ＃１を内部バス２０経由で受信する。
【００４７】
ユーザデータとパリティ＃１からパリティ＃ｉまでのパリティに基づいて誤り訂正を試みる（ステップＳ１３）。そして、誤り訂正に成功したか否かを判断し（ステップＳ１４）、誤り訂正に成功した場合（ステップＳ１４  Ｙｅｓ）、処理を終了する。
【００４８】
誤り訂正に成功しなかった場合（ステップＳ１４  Ｎｏ）、ｉ＝ｉ＋１とし（ステップＳ１５）、ｎ＜ｉであるか否かを判断する（ステップＳ１６）。ｎ＜ｉである場合（ステップＳ１６  Ｙｅｓ）、処理を終了する。ｎ＜ｉでない場合（ステップＳ１６  Ｎｏ）、パリティ＃ｉを受信し（ステップＳ１７）、ステップＳ１３へ戻る。パリティ＃ｉの受信は、具体的には、復号部２６が誤り訂正の失敗を制御部２３へ通知し、制御部２３が当該通知に基づいてメモリＩ／Ｆ２２に対して、パリティ＃ｉの読出しを指示する。そして、メモリＩ／Ｆ２２により半導体メモリ部３から読み出されたパリティ＃ｉを内部バス２０経由で受信する。
【００４９】
次に、ユーザデータとパリティの半導体メモリ部３への格納方法の例について説明する。図７〜図８は、ユーザデータとパリティの半導体メモリ部３への格納形式の例を示す図である。
【００５０】
図７の例では、すべてのユーザデータのサイズが同一（ユーザデータ＃１，ユーザデータ＃２，…，ユーザデータ＃Ｕのサイズが同一）とした例を示しており、全てのユーザデータに対して同一サイズのパリティを生成して半導体メモリ部３へ格納している。この例では、ユーザデータ＃ｉ（ｉ＝１，２，…，Ｕ）に対して、上述の１段階目のパリティ＃１に相当するパリティ＃ｉ−１，上述の２段階目のパリティ＃２に相当するパリティ＃ｉ−２，上述の３段階目のパリティ＃３に相当するパリティ＃ｉ−３，…，上述のｎ段階目のパリティ＃２に相当するパリティ＃ｉ−ｎを生成して格納している。例えば、半導体メモリ部３がＮＡＮＤメモリである場合、図７の一行を１ページとしてもよい。
【００５１】
なお、図７では、すべてのユーザデータのサイズを同一としているが、ユーザデータのうち一部またはすべてのサイズが異なっていても同様にユーザデータ＃ｉに対してパリティ＃ｉ−１〜＃ｉ−ｎを生成して格納することができる。
【００５２】
また、図７の例では、１≦ｉ≦Ｕの全てのｉについて、パリティ＃ｉ−１のサイズを同一とし、パリティ＃ｉ−２のサイズを同一とし、パリティ＃ｉ−３のサイズを同一とし、…、パリティ＃ｉ−ｎのサイズを同一としているが、これらパリティのうち一部またはすべてのサイズが異なっていてもよい。
【００５３】
また、図７の例では、すべてのユーザデータのパリティの数（ｎ）が同一であるが、ユーザデータのうちの一部または全てについてパリティの数が異なっていてもよい。
【００５４】
また、図７の例では、パリティ＃ｉ−１，パリティ＃ｉ−２，パリティ＃ｉ−３，…，パリティ＃ｉ−ｎが連続する領域に記憶されているが、これらパリティのうち一部またはすべてが非連続な領域に記憶されてもよい。
【００５５】
図８の例では、ユーザデータ＃２とユーザデータ＃１およびユーザデータ＃３とで、パリティの数（ｎ）が異なり、また、パリティ＃ｉ−１，パリティ＃ｉ−２，パリティ＃ｉ−３，…，パリティ＃ｉ−ｎを非連続な領域に格納した例を示している。ユーザデータ＃２ではｎ＝３とし、ユーザデータ＃１およびユーザデータ＃３では、ｎ＝１としている。そして、ユーザデータ＃２に連続する領域にパリティ＃２−１を格納し、パリティ＃２−２はユーザデータ＃１に連続する領域に格納し、パリティ＃２−３はユーザデータ＃３に連続する領域に格納している。各ユーザデータに対応するパリティの数、各パリティの配置位置は図８の例に限定されない。例えば、半導体メモリ部３がＮＡＮＤメモリである場合、図８の一行を１ページとしてもよい。
【００５６】
図６、図７、図８の例では、半導体メモリ部３が１つの記憶装置である例を示したが、図９は、半導体メモリ３がメモリ部３−１〜３−（ｎ＋１）の複数の記憶装置で構成される例を示している。メモリ部３−１〜３−（ｎ＋１）は、例えばそれぞれ異なるメモリチップであってもよいし、それぞれ異なる形式（例えば、ＮＡＮＤメモリと磁気記憶装置等）の記憶装置であってもよい。図９の例では、メモリ部３−１にユーザデータ＃１〜＃Ｕを格納し、パリティ＃ｉ−１をメモリ部３−２に格納し、パリティ＃ｉ−２をメモリ部３−３に格納し、パリティ＃ｉ−３をメモリ部３−４に格納し、…、パリティ＃ｉ−ｎをメモリ部３−（ｎ＋１）に格納している。図９は、各メモリ部へユーザデータおよび各パリティを分散して格納する場合の一例を示しており、具体的な分散方法は、図９の例に限定されない。また、図９の例では、半導体メモリ部３内の異なる記憶装置にユーザデータおよび各パリティを分散して格納する例を示したが、ユーザデータおよび各パリティの一部を半導体メモリ部３外の別の記憶装置に格納してもよい。
【００５７】
以上のように、本実施の形態では、パリティを多段階で生成する。そして、復号時に、１段階目と２段階目のパリティを２段階目の誤り訂正で用い、１段階目、２段階目および３段階目のパリティを３段目の誤り訂正で用い、…というように、他の段階のパリティを復号において用いることにより誤り訂正能力を向上させることができる符号を、符号演算において生成するようにした。このため、平均的な読み出し速度を低下させずに、誤りの規模に応じて誤り訂正に用いるパリティ数を適応的に変化させることができ、また、独立して多段階のパリティを生成する場合に比べ、パリティ量が同一であれば誤り訂正能力を高めることができる。
【００５８】
（第２の実施の形態）
図１０は、第２の実施の形態にかかるメモリシステムの構成例を示すブロック図である。本実施の形態の半導体記憶装置１ａは、メモリコントローラ２ａと半導体メモリ部３を備える。半導体メモリ部３は第１の実施の形態の半導体メモリ部３と同様である。記憶装置１ａは、第１の実施の形態の記憶装置１と同様にホスト４と接続可能である。第１の実施の形態と同様の機能を有する構成要素は、第１の実施の形態と同一の符号を付して重複する説明を省略する。
【００５９】
メモリコントローラ２ａは、符号化／復号部２４を符号化／復号部２４ａに替える以外は、第１の実施の形態のメモリコントローラ２と同様である。符号／復号部２４ａは、符号化部２５ａと復号部２６ａで構成される。本実施の形態の動作は、半導体メモリ部３への書込み時の符号演算および半導体メモリ部３からの読み出し時の復号演算を除き、第１の実施の形態と同様である。
【００６０】
本実施の形態の符号化部２５ａにおける符号演算について説明する。図１１は、本実施の形態の符号演算の概念を示す図である。図１１に示したＧ1（ｘ）〜Ｇn（ｘ）は、第１の実施の形態で述べた生成多項式Ｇ1（ｘ）〜Ｇn（ｘ）と同様である。
【００６１】
図１１に示すように、本実施の形態の符号化部２５ａは、符号演算として次のようにｎ段階でパリティを計算する。
（１）ユーザデータを用いてＧ1（ｘ）によりパリティ＃１を計算し、パリティ＃１のパリティである外部パリティ＃１を計算する。
（２）ユーザデータを用いてＧ2（ｘ）によりパリティ＃２を計算し、パリティ＃２のパリティである外部パリティ＃２を計算する。
（３）ユーザデータを用いてＧ3（ｘ）によりパリティ＃３を計算し、パリティ＃３のパリティである外部パリティ＃３を計算する。
…
（ｎ）ユーザデータを用いてＧn（ｘ）によりパリティ＃ｎ（ｎは１以上の整数）を計算し、パリティ＃ｎのパリティである外部パリティ＃ｎを計算する。
【００６２】
次に、本実施の形態の復号部２６ａにおける復号演算について説明する。本実施の形態の復号部２６ａは、復号演算として次のようにｎ段階で誤り訂正を実施する。
（１）外部パリティ＃１を用いてパリティ＃１の誤り訂正を行う。パリティ＃１の誤り訂正に成功した場合、誤り訂正後のパリティ＃１（誤りの無かった場合には元のパリティ＃１）とユーザデータを用いて、ユーザデータの誤り訂正を実施する。
（２）（１）でユーザデータの誤り訂正に失敗した場合、外部パリティ＃２を用いてパリティ＃２の誤り訂正を行う。パリティ＃２の誤り訂正に成功した場合、誤り訂正後のパリティ＃１と誤り訂正後のパリティ＃２とユーザデータとを用いて、ユーザデータの誤り訂正を実施する。
（３）（２）でユーザデータの誤り訂正に失敗した場合、外部パリティ＃３を用いてパリティ＃３の誤り訂正を行う。パリティ＃３の誤り訂正に成功した場合、誤り訂正後のパリティ＃１と誤り訂正後のパリティ＃２と誤り訂正後のパリティ＃３とユーザデータとを用いて、ユーザデータの誤り訂正を実施する。
…
（ｎ）（ｎ−１）でユーザデータの誤り訂正に失敗した場合、外部パリティ＃ｎを用いてパリティ＃ｎの誤り訂正を行う。パリティ＃ｎの誤り訂正に成功した場合、誤り訂正後のパリティ＃１と誤り訂正後のパリティ＃２と誤り訂正後のパリティ＃３と…誤り訂正後のパリティ＃ｎとユーザデータとを用いて、ユーザデータの誤り訂正を実施する。
【００６３】
なお、外部パリティ＃ｉ（ｉ＝１，２，…，ｎ）を用いたパリティ＃ｉの誤り訂正に失敗した場合、ユーザデータの誤り訂正ができないため、復号部２６ａは制御部２３へ当該ユーザデータの誤り訂正の失敗を通知する。
【００６４】
なお、ユーザデータ、パリティ＃ｉ、外部パリティ＃ｉの半導体メモリ部３への格納方法に制約はなく、ユーザデータ、パリティ＃ｉ、外部パリティ＃ｉを連続した領域に格納してもよいし、分散させて格納してもよい。また、第１の実施の形態で述べたように、複数の記憶装置に分散させて格納してもよい。例えば、半導体メモリ部３がＮＡＮＤメモリである場合、パリティ＃１〜＃ｎをユーザデータと同一ページ内に格納し、外部パリティ＃１〜＃ｎを半導体メモリ部３外の別の記憶装置に格納してもよい。また、パリティ＃１をユーザデータと同一ページ内に格納し、パリティ＃２〜＃ｎと外部パリティ＃１〜＃ｎを別のページに格納してもよい。
【００６５】
以上のように、本実施の形態では、ユーザデータに基づいて第１の実施の形態と同様の生成多項式を用いて各段階のパリティを生成し、各段階のパリティのパリティである外部パリティを生成するようにした。このため、ユーザデータの誤り訂正を行う演算において、パリティに誤りは含まれないとして演算することができ、第１の実施の形態に比べ、演算を高速化することができる。
【００６６】
（第３の実施の形態）
図１２は、第３の実施の形態にかかるメモリシステムの構成例を示すブロック図である。本実施の形態の半導体記憶装置１ｂは、メモリコントローラ２ｂと半導体メモリ部３を備える。半導体メモリ部３は第１の実施の形態の半導体メモリ部３と同様である。記憶装置１ｂは、第１の実施の形態の記憶装置１と同様にホスト４と接続可能である。第１の実施の形態と同様の機能を有する構成要素は、第１の実施の形態と同一の符号を付して重複する説明を省略する。
【００６７】
メモリコントローラ２ｂは、符号／復号部２４を符号／復号部２４ｂに替える以外は、第１の実施の形態のメモリコントローラ２と同様である。符号／復号部２４ｂは、符号化部２５ｂと復号部２６ｂとパリティ保護表記憶部２７と構成される。本実施の形態の動作は、半導体メモリ部３への書込み時の符号演算および半導体メモリ部３からの読み出し時の復号演算を除き、第１の実施の形態と同様である。
【００６８】
第１の実施の形態では、ｎ段階目の誤り訂正手続きの主要部において、パリティ＃１、パリティ＃２、…、パリティ＃ｎの誤り訂正対象が、ユーザデータ＋パリティ＃１＋パリティ＃２＋…＋パリティ＃ｎであり、すべてのパリティが誤り訂正の対象となっている。すなわち、パリティ＃１、パリティ＃２、…、パリティ＃ｎに誤りが含まれているかもしれないという前提で誤り訂正を行う。
【００６９】
これに対し、第２の実施の形態では、パリティ＃１、パリティ＃２、…、パリティ＃ｎの誤り訂正対象が、ユーザデータのみであり、パリティ＃１、パリティ＃２、…、パリティ＃ｎ自身はパリティ＃１、パリティ＃２、…、パリティ＃ｎの誤り訂正の対象外である。パリティ＃１、パリティ＃２、…、パリティ＃ｎは、パリティ＃１、パリティ＃２、…、パリティ＃ｎとは異なる別のパリティである外部パリティ＃１、外部パリティ＃２、…、外部パリティ＃ｎの誤り訂正対象である。
【００７０】
すなわち、パリティ＃ｉ（１≦ｉ≦ｎ）に誤りが存在する場合には、第１の実施の形態では、パリティ＃ｉ自身とパリティｊ（ｉ＜ｊ）を用いてパリティ＃ｉを訂正し、第２の実施の形態では、外部パリティ＃ｉを用いてパリティ＃ｉを訂正する。
【００７１】
本実施の形態では、パリティ＃ｉの誤りを、第１の実施の形態の方法で訂正するか、第２の実施の形態の方法で訂正するか、をパリティ＃ｉごとに設定可能とし、パリティ＃ｉの誤りを、どのパリティで誤り訂正するかを示すパリティ保護情報をパリティ保護表として保持する。そして、符号演算、復号演算を行う際に、パリティ保護表に従って演算を実施する。パリティ保護表を任意に設定可能とすることで、パリティ＃ｉの誤りをどのパリティを用いて誤り訂正するかを任意に設定することができる。パリティ保護表は、パリティ保護表記憶部２７に記憶される。
【００７２】
図１３は、パリティ保護表の一例を示す図である。図１３の表の縦方向は、誤り訂正対象となるパリティを示し、横方向は誤り訂正対象をする際に用いることができるパリティを示している。図１３の表では、丸印は誤り訂正に用いることが可能なことを示し、バツ印はパリティを用いることができないことを示す。また、図１３の表では、パリティ＃ｉを誤り訂正対象とする場合のパリティ＃１〜＃ｉは、設定により変更されることはないため「−」として示している。例えば、１行目のパリティ＃１は、用いることが自明なパリティ＃１と、丸印となっているパリティ＃２、パリティ＃３、…、パリティ＃ｎを用いて誤り訂正することができる。パリティ＃２は、用いることが自明なパリティ＃２と、外部パリティを用いて誤り訂正を行うことができる。パリティ＃３は、用いることが自明なパリティ＃３と、外部パリティを用いて誤り訂正を行うことができる。なお、図１３は一例であり、パリティ保護表の具体的内容はこの例に限定されない。
【００７３】
図１４は、本実施の形態の符号演算の概念を示す図である。図１４は、図１３に示したパリティ保護表に対応する符号演算の例を示している。
【００７４】
図１４の例では、符号化部２５ｂは、符号演算として次のようにｎ段階でパリティを計算する。
（１）ユーザデータを用いてＧ1（ｘ）によりパリティ＃１を計算する。
（２）ユーザデータとパリティ＃１を用いてＧ2（ｘ）によりパリティ＃２を計算し、パリティ＃２のパリティである外部パリティ＃２を計算する。
（３）ユーザデータとパリティ＃１を用いてＧ3（ｘ）によりパリティ＃３を計算し、パリティ＃３のパリティである外部パリティ＃３を計算する。
…
（ｎ）ユーザデータとパリティ＃１を用いてＧn（ｘ）によりパリティ＃ｎ（ｎは１以上の整数）を計算し、パリティ＃ｎのパリティである外部パリティ＃ｎを計算する。
【００７５】
符号化部２５ｂは、パリティ保護表に基づいてパリティの生成方法を選択して、対応するパリティを生成する。例えば、図１３の例の場合、パリティ＃１については、外部パリティが用いられないため、第１の実施の形態と同様にユーザデータに基づいてパリティ＃１を生成し、パリティ＃１に対する外部パリティは生成しない。一方、パリティ＃２については、外部パリティが用いるため、ユーザデータに基づいてパリティ＃２を生成し、さらにパリティ＃２に対する外部パリティを生成する。
【００７６】
なお、パリティ＃１からパリティ＃（ｉ−１）までの全てが外部パリティにより保護されている場合は、ユーザデータのみに基づいてパリティ＃ｉを生成すればよいが、パリティ＃１からパリティ＃（ｉ−１）の中に外部パリティによって保護されないパリティが存在する場合には、ユーザデータ＋外部パリティによって保護されないパリティすべてを用いてパリティ＃ｉを生成する。
【００７７】
復号部２６ｂは、パリティ保護表に基づいてパリティの復号方法を選択して、対応する誤り訂正処理を実施する。例えば、図１３の例の場合、パリティ＃１を用いた１段階目の誤り訂正処理では、外部パリティが生成されていないため、第１の実施の形態と同様にパリティ＃１とユーザデータとに基づいてユーザデータの誤り訂正を行う。一方、パリティ＃２については外部パリティが生成されているため、パリティ＃２の外部パリティを用いてパリティ＃２の誤り訂正を行った後に、パリティ＃１、パリティ＃２およびユーザデータに基づいてユーザデータの誤り訂正を実施する。
【００７８】
図１５は、本実施の形態の復号演算の概念とユーザデータおよびパリティの格納例を示す図である。図１５は、半導体メモリ部３への格納例として、ユーザデータ＃１、ユーザデータ＃２、ユーザデータ＃３について、ユーザデータ＃２にはユーザデータ＃１、＃３より多くのパリティを割り当てる例を示している。図１５のユーザデータ＃２に関しては、３段階の符号演算が実施され、ユーザデータ＃１、ユーザデータ＃３については、１段階の符号化が実施されている。ここでは、半導体メモリ部３をＮＡＮＤメモリとし、ユーザデータ＃１、ユーザデータ＃２、ユーザデータ＃３をそれぞれ異なるページに格納されるとする。
【００７９】
具体的には、ユーザデータ＃２に関しては、１段階目のパリティとしてパリティ＃２−１が生成され（パリティ＃２−１に対する外部パリティは無し）、２段階目のパリティとしてパリティ＃２−２が生成されるとともにパリティ＃２−２の外部パリティ（図１５のパリティ＃１−１が外部パリティに相当する）が生成され、３段階目のパリティとしてパリティ＃２−３が生成されるとともにパリティ＃２−３の外部パリティ（図１５のパリティ＃３−１が外部パリティに相当する）が生成される。また、ユーザデータ＃１に関しては、ユーザデータ＃１とパリティ＃２−２を通常のユーザデータと同様とみなしてパリティ＃１−１を生成する。同様に、ユーザデータ＃３に関しては、ユーザデータ＃３とパリティ＃２−３を通常のユーザデータと同様とみなしてパリティ＃３−１を生成する。このように、パリティ＃１−１はユーザデータ＃１のパリティであるが、パリティ＃２−２の外部パリティでもある。また、パリティ＃３−１はユーザデータ＃３のパリティであるが、パリティ＃２−３の外部パリティでもある。
【００８０】
図１５の例では、多段階の符号化を行うユーザデータ＃２の外部パリティを他のページに格納し、他のページのパリティ（パリティ＃１−１，＃３−１）の誤り訂正対象としてユーザデータだけでなく当該ページに格納されたユーザデータ＃２のパリティを含めるように構成しているが、外部パリティの生成方法はこの方法に限定されない。他のページ（ユーザデータ＃１、ユーザデータ＃３）のユーザデータのパリティとは別にユーザページ＃２のパリティの外部パリティを生成して、半導体メモリ３上または他の記憶装置に格納するようにしてもよい。
【００８１】
図１５の例のユーザデータ＃２の復号演算の手順を説明する。
（１）ユーザデータ＃２およびパリティ＃２−１を用いてユーザデータの誤り訂正を実施する。
（２）（１）でユーザデータの誤り訂正に失敗した場合、外部パリティであるパリティ＃１−１とユーザデータ＃１とパリティ＃２−２を用いて、パリティ＃２−２の誤り訂正を行う。パリティ＃２−２の誤り訂正に成功した場合、パリティ＃２−１と誤り訂正後のパリティ＃２−２とユーザデータ＃２とを用いて、ユーザデータ＃２の誤り訂正を実施する。
（３）（２）でユーザデータの誤り訂正に失敗した場合、外部パリティであるパリティ＃３−１とユーザデータ＃３とパリティ＃２−３を用いて、パリティ＃２−３の誤り訂正を行う。パリティ＃２−３の誤り訂正に成功した場合、パリティ＃２−１と誤り訂正後のパリティ＃２−２と誤り訂正後のパリティ＃２−３とユーザデータ＃２とを用いて、ユーザデータ＃２の誤り訂正を実施する。
【００８２】
図１６は、ユーザデータ１個とパリティ複数個とから外部パリティを計算する場合のユーザデータおよびパリティの格納例を示す図である。図１６の例では、ユーザデータ＃２、＃３に関しては、３段階のパリティ生成が行われ、ユーザデータ＃１については１段階のパリティ生成が行われる。ユーザデータ＃２、＃３に関しては、それぞれ１段階目のパリティとして生成多項式Ｇ1（ｘ）に基づいてパリティ＃２−１、＃３−１が生成され、２段階目のパリティとして生成多項式Ｇ2（ｘ）に基づいてパリティ＃２−２、＃３−２が生成される。そして、ユーザデータ＃１、パリティ＃２−２および＃３−２に生成多項式Ｇ3（ｘ）を用いてパリティ＃１−１が生成される。パリティ＃１−１は、パリティ＃２−２および＃３−２の外部パリティとなっている。
【００８３】
図１７〜図１９は、半導体メモリ部３をＮＡＮＤメモリとした場合の本実施の形態のユーザデータおよび各パリティの格納方法の例を示している。ここでは、１つのメモリセルに３ｂｉｔのデータを格納するとし、この３ｂｉｔにそれぞれ異なるページが割当てられるとし、１ワードラインに格納されるページをlower（Ｌ）ページ、middle（Ｍ）ページ、upper（Ｕ）ページとそれぞれ呼ぶこととするが、半導体メモリ部３を構成するＮＡＮＤメモリは、このようなタイプのメモリに限定されるものではない。図１７〜図１８では、パリティ専用ページ以外については、lowerページ、middleページ、upperページをそれぞれ異なるハッチングをして示している。例えば、図１７〜図１９において、１行目がlowerページ、２行目がmiddleページ、３行目がupperページ、４行目がlowerページ、…とする。パリティ専用ページについては、lowerページ用のパリティ、middle用ページのパリティ、upperページ用のパリティをそれぞれlowerページ、middleページ、upperページと同一のハッチングで示している。パリティ専用ページは、lowerページ、middleページ、upperページのいずれであってもよいが、図１７〜図１９では、パリティ専用ページは、middleページ（下から２段目）とupperページ（最下段）の例を示している。
【００８４】
図１７〜図１８の例では、パリティの一部を、（ユーザデータが格納されない）パリティ専用ページに格納している。図１７の例では、lowerページ、middleページ、upperページの全てに同一サイズのパリティを割当てている。そして、１段階目で生成したパリティ（１２２Ｂ）をそれぞれ対応するユーザデータ（５１２Ｂ×２）と同一ページに格納し、２段階目のパリティ（７Ｂ）を、下から２行に示した２ページのパリティ専用ページに格納している。また、最下段のパリティ専用ページでは、２段階目のパリティをユーザデータと同等に扱って外部パリティ（１２９Ｂ）を生成し、各ページ（パリティ専用ページ）内に格納している。
【００８５】
図１７の例では、lowerページ、middleページ、upperページの全てについて、それぞれページ内に格納された１段階目のパリティ（１２２Ｂ）を用いて６９ビットまで訂正可能であり、さらにパリティ専用ページに格納された２段階目のパリティ（７Ｂ）を用いると７３ビットまで訂正可能である。
【００８６】
また、図１８の例では、lowerページ、middleページ、upperページの全てに、１段階目のパリティについては同一サイズのパリティを割当てている。そして、１段階目で生成したパリティ（１２２Ｂ）をそれぞれ対応するユーザデータ（５１２Ｂ×２）と同一ページに格納している。２段階目のパリティ（２３Ｂ）については、middleページに対して生成して下から２行に示した２ページのパリティ専用ページに格納している。また、最下段のパリティ専用ページでは、２段階目のパリティをユーザデータと同等に扱って外部パリティ（１４５Ｂ）を生成し、各ページ（パリティ専用ページ）内に格納している。
【００８７】
図１８の例では、lowerページ、middleページ、upperページの全てについて、それぞれページ内に格納された１段階目のパリティ（１２２Ｂ）を用いて６９ビットまで訂正可能であり、さらにパリティ専用ページに格納された２段階目のパリティ（２３Ｂ）を用いるとmiddleページについて８２ビットまで訂正可能である。
【００８８】
また、図１９の例では、middleページの１段階目のパリティのサイズをlowerページおよびupperページの１段階目のパリティのサイズより大きくしている。middleページの１段階目のパリティは６９ビットまで訂正可能な１２２Ｂであり、lowerページおよびupperページの１段階目のパリティは、６７ビットまで訂正可能な１１８Ｂである。また、２段階目のパリティ（２３Ｂ）については、middleページに対して生成して下から２行に示した２ページのパリティ専用ページに格納する。さらに３段階目および４段階目のパリティ（各４Ｂ）をmiddleページに対して生成して、lowerページおよびupperページに格納している。また、最下段のパリティ専用ページでは、２段階目のパリティをユーザデータと同等に扱って外部パリティ（１５３Ｂ）を生成し、各ページ（パリティ専用ページ）内に格納している。
【００８９】
図１９の例では、lowerページおよびupperページについては、６７ビットまで訂正可能であり、middleページについては、ユーザデータと同一ページ内の１段階目のパリティを用いると６９ビットまで訂正可能であり、パリティ専用ページの２段階目のパリティを用いると８２ビットまで訂正可能であり、４段階目までの全てのパリティを用いると８７ビットまで訂正可能である。
【００９０】
図１８、図１９の例のように、ページごとにパリティのサイズを変えるようにしておくと、例えば、信頼性の低いページに大きなサイズのパリティを割当てることが可能となる。また、実際の誤り数が少ない場合は、ページ内のパリティの読出しだけですむ。さらに、上述したように各段階のパリティを追加して誤り訂正を行うような符号化を行っているため、独立して多段階のパリティを生成する場合に比べ、パリティ量が同一であれば誤り訂正能力を高めることができる。
【００９１】
なお、図１８、図１９の例では、３ページのうち１ページにサイズの大きなパリティを割り当て、残りの２ページには同一サイズのパリティを割り当てたが、３ページすべてに異なるサイズのパリティを割り当ててもよい。
【００９２】
以上のように、本実施の形態では、パリティ保護表を用いて、パリティ＃ｉを保護するパリティを設定可能とすることにより、第１の実施の形態の符号演算および復号演算と、第２の実施の形態の符号演算および復号演算と、を組み合わせて実施することができる。このため、想定される誤り数や演算速度への要求等に応じて適切な符号演算および復号演算を行うことができる。
【００９３】
（第４の実施の形態）
図２０は、第４の実施の形態にかかる誤り訂正装置を備える通信装置の構成例を示すブロック図である。図２０では、誤り訂正処理にかかる構成要素を示しており、例えば通信装置が無線通信装置である場合のアンテナ等、通信装置が通常備える機能は図示を省略している。
【００９４】
通信装置３０−１，３０−２は、それぞれ送信機能および受信機能を有し、通信装置３０−１から送信されたユーザデータは通信装置３０−２で受信され、通信装置３０−２から送信されたユーザデータは通信装置３０−１で受信される。通信装置３０−１と通信装置３０−２の間の通信路において、誤りが発生することがある。
【００９５】
このような通信路における誤りに対する誤り訂正にも第１の実施の形態で述べた多段階の符号化を適用することができる。
【００９６】
通信装置３０−１，３０−２は同様の構成を有する。図２０に示すように、通信装置３０−１，３０−２は、符号化部４０と復号部５０を備える。符号化部４０は、ユーザデータ生成部４１、符号演算部４２、符号記憶部４３、送信部４４および符号送信要求受信部４５を備える。復号部５０は、受信部５１、復号演算部５２および符号送信要求送信部５３を備える。符号化部４０および復号部５０は、本実施の形態の誤り訂正装置を構成する。
【００９７】
まず、ユーザデータの送信動作について説明する。例えば、通信装置３０−１から通信装置３０−２へユーザデータを送信する場合、通信装置３０−１のユーザデータ生成部４１は、ユーザデータを生成して符号演算部４２へ入力する。符号演算部４２は、第１の実施の形態（または第２の実施の形態、第３の実施の形態のいずれかでもよい）と同様の多段階の符号演算によりパリティを生成し、符号記憶部４３へパリティを格納する。例えば、パリティ＃１〜パリティ＃ｎが格納されるとする。送信部４４は、ユーザデータと所定の段階までのパリティ（例えば、パリティ＃１）とを通信装置３０−２へ送信する。なお、第３の実施の形態の符号化を行う場合には、通信装置３０−１および通信装置３０−２はパリティ保護表を保持する。
【００９８】
通信装置３０−２では、受信部５１が、ユーザデータおよびパリティ（例えば、パリティ＃１）を受信し、復号演算部５２へ入力する。復号演算部５２は、第１の実施の形態（または第２の実施の形態、第３の実施の形態のいずれかでもよい）と同様に受信したパリティに応じた処理を実施する。例えば、第１の実施の形態の符号演算が実施されて、パリティ＃１を受信した場合、パリティ＃１とユーザデータに基づいてユーザデータの誤り訂正を行う。復号演算部５２は、この誤り訂正が成功した場合は、当該ユーザデータの受信処理を終了する。一方、この誤り訂正に失敗した場合は、復号演算部５２は、誤り訂正の失敗を符号送信要求送信部５３へ通知する。符号送信要求送信部５３は、この通知を受けると、当該ユーザデータに対する次の段階のパリティ（例えば、パリティ＃２）の送信要求を通信装置３０−１へ送信する。なお、復号演算部５２は、誤り訂正に失敗した場合、受信済みのパリティとユーザデータとを保持しておく。
【００９９】
通信装置３０−１の符号送信要求受信部４５は、通信装置３０−２からの送信要求を受信すると、対応するパリティを符号記憶部４３から送信部４４へ出力するよう制御し、送信部４４は入力されたパリティを通信装置３０−１へ送信する。通信装置３０−１の受信部５１は、このパリティを復号演算部５２へ渡し、復号演算部５２は、保持しているパリティとユーザデータと新たに受信したパリティとを用いて復号演算を実施する。以降、復号演算において誤り訂正が失敗した場合には、同様に、次の段階のパリティの送信を要求し、当該パリティを受信した場合に、受信したパリティと保持しているパリティおよびユーザデータとを用いて復号演算を行うことを繰り返す。
【０１００】
例えば、まず、通信装置３０−１は、ユーザデータとともに第１の実施の形態のパリティ＃１を送信しておき、パリティの送信要求を受信した場合（すなわち、パリティ＃１による誤り訂正が失敗であった場合）に、パリティ＃２を送信し、さらにパリティの送信要求を受信した場合（すなわち、パリティ＃２までによる誤り訂正が失敗であった場合）に、パリティ＃２を送信する、…というように段階的にパリティを送信することができる。これにより、誤りの規模に応じて誤り訂正に用いるパリティ数を適応的に変化させることができ、パリティによる通信帯域の浪費を防ぎつつ誤り数が多い場合にも誤り訂正を実施することができる。
【０１０１】
なお、ここでは、通信装置３０−１，３０−２がユーザデータを生成するようにしたが、通信装置３０−１，３０−２がユーザ端末等と接続し、ユーザデータをユーザ端末等から受信し、受信したユーザデータに対して符号演算を行うようにしてもよい。
【０１０２】
（第５の実施の形態）
図２１は、第５の実施の形態にかかる半導体記憶装置における復号部の構成例を示すブロック図である。本実施の形態では、第３の実施の形態で述べた多段階誤り訂正方式を実現するための復号部２６ｂの構成と動作の一例を説明する。
【０１０３】
図２１に示すように、本実施の形態の復号部２６ｂは、シンドローム計算部２６１、誤り位置多項式演算部２６２、チエンサーチ部２６３および復号制御部２６４を備える。
【０１０４】
図２２は、本実施の形態の復号処理手順の一例を示すフローチャートである。図２１、２２を用いて、本実施の形態の復号処理の全体動作を説明する。制御部２３は、ＨｏｓｔＩ／Ｆ２１経由でホスト４からデータの読み出し要求を受け取ると、読み出し対象のデータを読み出すようメモリＩ／Ｆ２２へ指示し、メモリＩ／Ｆ２２は読み出し対象のデータを対応するパリティとともに読み出し、復号部２６へ渡す。復号部２６では、メモリＩ／Ｆ２２から読み出し対象のデータおよびパリティを受け取ると復号処理を開始する。
【０１０５】
本実施の形態では、第３の実施の形態と同様に多段階誤り訂正方式により符号化演算が実施される。以下の説明では、符号化演算において２段階のパリティが生成され、また２段階目のパリティに外部パリティが生成される例について説明するが、多段階誤り訂正方式の段階数や外部パリティの付与方法はこれに限定されず、外部パリティを用いなくてもよい。外部パリティを用いない多段階誤り訂正方式を採用する場合も、本実施の形態の復号処理は適用可能であり、この場合は、例えば、各段階のパリティに誤りが無いと仮定して復号処理を実施する。
【０１０６】
図２２の手順は、多段階の復号演算のうちの１段階分の処理を示している。第１の実施の形態〜第３の実施の形態で述べたように、１段階目のパリティを用いた図２２に示す手順により復号処理を実施し、誤り訂正に失敗した場合、２段階目のパリティを用いた復号処理が実施される。この際、２段階目のパリティに外部パリティが付与されている場合は、外部パリティを用いた復号処理を図２２と同様の手順で実施し、復号後（誤り訂正後）の２段階目のパリティを用いて２段階目の復号処理を実施する。
【０１０７】
まず、復号制御部２６４は、復号処理を開始すると、シンドローム計算部２６１に対してシンドローム計算の実施を指示し、シンドローム計算部２６１がシンドローム計算を実施する（ステップＳ２１）。その後、復号制御部２６４は、誤り位置多項式演算部２６２に対して、計算済みのシンドローム計算結果を用いて誤り多項式演算を行うよう指示し、誤り位置多項式演算部２６２が誤り位置多項式演算を実施する（ステップＳ２２）。
【０１０８】
次に、復号制御部２６４は、チエンサーチ部２６３に対して、誤り位置多項式演算の結果を用いてチエンサーチを行うよう指示し、チエンサーチ部２６３は誤り位置多項式演算の結果である誤り位置多項式の係数を用いてチエンサーチを実施し（ステップＳ２３）、誤り位置を特定し、処理を終了する。復号制御部２６４は、チエンサーチにより、誤りがあると判定されたビットを反転させることにより誤り訂正を実施する。
【０１０９】
１段階目のパリティを用いた復号処理では、シンドローム計算部２６１に入力されるのは、ユーザデータ（読み出しデータ）と１段階目のパリティである。１段階目のパリティを用いた復号処理において誤り訂正不可であると判定された場合、本実施の形態では、２段階目のパリティに外部パリティが付与されるため、外部パリティと２段階目のパリティとを用いた復号処理が行われる。そして、ユーザデータと１段階目のパリティと誤り訂正後の２段階目のパリティとをシンドローム計算部２６１に入力し、２段階目の復号処理が実施される。なお、外部パリティと２段階目のパリティとを用いた復号処理については、図２１に示したシンドローム計算部２６１、誤り位置多項式演算部２６２、チエンサーチ部２６３および復号制御部２６４を用いて実施してもよいし、これらとは別に復号処理演算の回路を設けて、この回路により実施してもよい。
【０１１０】
以下、本実施の形態では、第１の実施の形態で述べた生成多項式Ｇ1（ｘ）に基づいて１段階目のパリティとしてパリティ＃１が生成され、生成多項式Ｇ2（ｘ）に基づいて２段階目のパリティとしてパリティ＃２が生成され、パリティ＃２の外部パリティが生成されているとする。
【０１１１】
パリティ＃１がｔ1の誤り訂正能力を有し（ｔ1ビットの誤り訂正が可能）、パリティ＃１とパリティ＃２の両方を用いた場合の誤り訂正能力をｔ2とする（ｔ2ビットの誤り訂正が可能）。このとき、ｔ1の誤り訂正能力に対応した復号処理回路とｔ2の誤り訂正能力に対応した復号処理回路を個別に備え、段階ごとに使い分けるように構成することも可能であるが、個別に備えるとハードウェア規模が大きくなるため、復号処理回路を共用することが望ましい。本実施の形態では、各段階の復号処理を単一の復号処理回路で実施する場合の構成および動作を説明する。
【０１１２】
まず、本実施の形態のシンドローム計算部２６１について説明する。一般に、シンドローム計算部２６１は、αi倍の乗算を行うための乗算器を含む最小単位の計算回路（αi倍の乗算器、ＸＯＲ回路、レジスタ等を含む）を誤り訂正可能なビット数個備える。αiの添字ｉは、Ｇ1（ｘ）×Ｇ2（ｘ）の根（αをガロア拡大体ＧＦ（２m）の原始元としたときの根α1，α2，α3，α4，α5，α6，…，α2t2-1）の指数部に対応する。ここでは、この最小単位の計算回路（シンドロームＳiを算出する回路）をシンドロームＳi計算回路とよぶ。１段階目の誤り訂正処理（復号処理）と、２段階目の誤り訂正処理とで回路を共用するためには、少なくとも、ｉ＝１，３，５，・・・，２ｔ2−１にそれぞれ対応する合計ｔ2個のシンドロームＳi計算回路を備えることになる。
【０１１３】
図２３は、シンドローム計算部２６１の構成例を示す図である。図２３では、一例としてパリティ＃１、パリティ＃２がそれぞれ２ビットの訂正能力を有する例を示しているが、パリティ＃１、パリティ＃２の訂正能力はそれぞれこれらに限定されない。ここでは、２段階目のパリティ＃１およびパリティ＃２を用いた誤り訂正処理を実施可能な復号化回路を共有するため、訂正能力の高い２段階目の誤り訂正能力ｔ2（図２３の例ではｔ2＝２）個の回路を備える構成としている。
【０１１４】
シンドロームＳi計算回路は、αiを乗算するmビットのガロア拡大体乗算回路６２−ｊ（ｊ＝（ｉ＋１）／２）と、シンドロームＳiの計算途中結果を保持するｍビットのレジスタ（ＦＦ（FlipFlop））６４−ｊと、ｍビットのＸＯＲ回路６２−ｊとを備える。以上は、一般的なシンドローム計算回路と同様である。本実施の形態では、αiがＧ1（ｘ）の根であるシンドロームＳi計算回路がグループ＃１を構成し、αiがＧ2（ｘ）の根であるシンドロームＳi計算回路がグループ＃２を構成とする。本実施の形態では、グループ＃１に属するシンドロームＳi計算回路については、シンドロームのレジスタ更新に用いる値を、入力データ（ＩＤＡＴＡ）とするか０とするかを切り替えるセレクタ回路（選択回路）６１−ｊを備え、セレクタ回路６１−ｊを制御する制御回路６５をグループ＃１内に少なくとも１つ備える。入力データとは、ユーザデータおよびパリティである。図２３の例では、制御回路６５をグループ＃１内に１つとしているが、例えば、セレクタ回路ごとに制御回路を備えてもよい。
【０１１５】
図２４は、１段階目の誤り訂正処理における回路使用状態を示す図である。図２４では、図２３に示したシンドローム計算部２６１により、１段階目のパリティ＃１を用いて（１段階目のパリティ＃１とユーザデータとを入力として）誤り訂正を行い場合の回路使用状態を示している。１段階目の誤り訂正では、図２４に示すように、グループ＃１に属するシンドロームＳi計算回路を用い、グループ＃２に属するシンドロームＳi計算回路は停止されておいてよい。１段階目の誤り訂正では、制御回路６５は、セレクタ回路６１−ｊが入力データ（ユーザデータおよびパリティ＃１）を選択するよう制御する。なお、図２３，２４では、ユーザデータ、パリティ＃１、パリティ＃２を、それぞれＤａｔａ、Ｐ１、Ｐ２と略して記載している。
【０１１６】
図２４に示すように、１段階目の誤り訂正では、パリティ＃２は入力されず、パリティ＃１の最終ビット位置を０番目と定義して通常のシンドローム計算が実施される。一般に、誤り訂正処理では、多項式表示で高次の項から順にデータがシンドローム計算回路に入力され、最終入力ビットを０番目のビットとしてチエンサーチ処理において誤り位置の特定が実施される。ここでは、ユーザデータ、パリティの順に入力されるとし、パリティの最終ビット（最後に入力されるビット）を０番目とする。１段階目の誤り訂正処理におけるシンドローム計算は、通常の誤り訂正処理と同様である。１段階目の誤り訂正処理におけるシンドローム計算以外の処理も、通常の誤り訂正処理と同様である。
【０１１７】
次に、本実施の形態のシンドローム計算処理について説明する。図２５は、本実施の形態のシンドローム計算の処理手順の一例を示すフローチャートである。前述のように、２段階目の誤り訂正処理は、１段階目の誤り訂正処理に失敗した場合に実施されるが、２段階目の誤り訂正処理を実施する際、パリティ＃２に外部パリティが付与されている場合は、パリティ＃２は外部パリティを用いた誤り訂正が実施済であるとする。
【０１１８】
まず、グループ＃１およびグループ＃２のシンドロームＳi計算回路にユーザデータとパリティ＃１を高次の項から１ビット入力する（ステップＳ３１）。具体的には、図２３の例では、制御回路６５が、入力データ（ユーザデータとパリティ）を選択するようセレクタ回路６１−１，６１−２を制御する。これにより、セレクタ回路６１−１〜６１−４の全てに入力データの１ビットが入力される。
【０１１９】
次に、制御回路６５は、パリティ＃１の最終ビットを入力したか否かを判断し（ステップＳ３２）、入力していない場合（ステップＳ３２  Ｎｏ）、ステップＳ３１へ戻り、次の次数の項の入力データを１ビット入力する。パリティ＃１の最終ビットを入力したか否かは、例えば、入力済みのビット数とユーザデータ＋パリティ＃１のビット数との比較により判定することができる。
【０１２０】
パリティ＃１の最終ビットを入力した場合（ステップＳ３２  Ｙｅｓ）、パリティ＃２を入力する（すなわち、２段階目の誤り訂正処理である）か否かを判断する（ステップＳ３３）。パリティ＃２を入力しない場合（ステップＳ３３  Ｎｏ）、処理を終了する。
【０１２１】
パリティ＃２を入力する場合（ステップＳ３３  Ｙｅｓ）、グループ＃１のシンドロームＳi計算回路には０を１ビット入力し、グループ＃２のシンドロームＳi計算回路にはパリティ＃２を高次の項から１ビット入力する（ステップＳ３４）。具体的には、図２３の例では、制御回路６５が、０を選択するようセレクタ回路６１−１，６１−２を制御する。
【０１２２】
次に、制御回路６５は、パリティ＃２の最終ビットを入力したか否かを判断し（ステップＳ３５）、入力していない場合（ステップＳ３５  Ｎｏ）、ステップＳ３４へ戻り次の次数のパリティ＃２を１ビット入力する。パリティ＃２の最終ビットを入力した場合（ステップＳ３５  Ｙｅｓ）、処理を終了する。
【０１２３】
以上のようにシンドローム計算を実施することで、２段階目の誤り訂正処理では、パリティ＃２を入力し終えたときには、グループ＃１のシンドロームを保持するレジスタ６４−１，６４−２については、「データとパリティ＃１」をパリティ＃２の次数分ケタ上げした（ビット位置を高次側にシフトさせた）多項式にαiを代入した結果が格納され、グループ＃１のシンドロームを保持するレジスタ６４−３，６４−４については、「データとパリティ#１とパリティ＃２」を並べて表示した多項式にαiを代入した結果が格納される。
【０１２４】
このようにすると、グループ＃１に入力した多項式と、グループ＃２に入力した多項式とは次数が揃うため、「データとパリティ＃１とパリティ＃２」のパリティ＃２の最低次数の位置を、「データとパリティ＃１とパリティ＃２」の０番目のビットとして扱うことができる。このため、この後は、通常のｔ2重（ｔ2ビットまでの誤り訂正処理が可能な）の誤り位置多項式の計算回路と、誤り位置の計算回路（チエンサーチ回路）とがあれば、２段階目の誤り訂正処理が可能である。
【０１２５】
また、本実施の形態では、２段階の誤り訂正方式を採用しているが、ｎ段階（ｎは３以上の整数）の誤り訂正方式を採用する場合は、グループ＃１〜グループ＃ｎを設け、それぞれが、生成多項式Ｇ1（ｘ）の根〜生成多項式Ｇn（ｘ）の根に対応するシンドロームＳi計算回路を備えるようにすればよい。また、グループ＃２〜グループ＃ｎは、それぞれセレクタ回路および制御回路を備え、ユーザデータと自グループに対応する根に対応するパリティが入力される間はセレクタ回路が入力データを選択し、自グループに対応する根に対応しないパリティが入力される間は、セレクタ回路が０を選択するようにすればよい。
【０１２６】
次に、誤り位置多項式演算部２６２およびチエンサーチ部２６３について述べる。誤り位置多項式演算部２６２は、シンドローム計算部２６１により計算されたシンドロームに基づいて誤り位置多項式を計算する。多段階の誤り訂正方式に対応するためには、誤り位置多項式演算部２６２は、ｔ2重の誤りにまで対応できる構成を備えていればよい。また誤り位置多項式計算のアルゴリズムの１つである、バーレカンプ・マッシィのアルゴリズムは、符号の最大訂正ビット数に対応したループ回数の処理を行う。このアルゴリズムを用い、「データとパリティ＃１」だけを入力として計算したシンドロームを入力とする１段階目の誤り訂正処理では、ｔ1重の誤りに対応するループ回数で処理を止めれば、処理を早く終わらせることができる。
【０１２７】
チエンサーチ部２６３は、誤り位置多項式に基づいて、誤り位置を計算する回路である。チエンサーチ部２６３については、ｔ2重の誤りにまで対応できる構成を備えた上で、下記に示す２通りの制御方式が考えられる。
【０１２８】
チエンサーチ部２６３では、誤り位置多項式演算部２６２により求められた誤り位置多項式に、誤りロケータを代入した値を順次計算することで、誤りロケータが誤り位置多項式の根となる位置を求める。ここで、データとパリティを合わせた符号語を多項式で表現したものを符号多項式と呼ぶ。符号多項式の最高次数の項がデータの先頭ビットに対応し、最低次数の項がパリティの最終ビットに対応する。符号多項式の最高次数の側の誤りロケータから代入する場合と、最低次数の側の誤りロケータから代入する場合とで、制御の仕方が異なる。
【０１２９】
符号多項式の最高次数の側の誤りロケータから代入する場合は、パリティ＃２を含めるとき（２段階目の誤り訂正処理）と含めないとき（１段階目の誤り訂正処理）とで符号多項式の最高次数が異なるため、チエンサーチ回路に最初に代入するロケータの値が異なる。すなわち、復号対象にパリティ＃２を含めるかどうか（２段階目の誤り訂正処理か１段階目の誤り訂正処理か）で、チエンサーチ部２６３に最初に代入する値を切り替える処理が必要になる。
【０１３０】
符号多項式の最低次数の側の誤りロケータから代入する場合は、パリティ＃２を含めるとき（２段階目の誤り訂正処理）と含めないとき（１段階目の誤り訂正処理）とで符号多項式の最低次数の位置を表す誤りロケータは同じであるため、上記のようなチエンサーチ部２６３に最初に代入する値の切り替えは必要ない。
【０１３１】
符号多項式の最高次数の側の誤りロケータから代入しても、最低次数の側の誤りロケータから代入しても、代入した誤りロケータの位置を順にずらしていく方向が、前者であれば次数が下がる方向、後者であれば次数が上がる方向というように異なるだけで、代入した誤りロケータの位置をずらして、誤り位置多項式の根になっているかチェックする、という処理自体は同じである。
【０１３２】
仮に、グループ＃１に属するシンドロームＳi計算回路に、入力データ切り替えの機構（セレクタ回路６１−１，６１−２，制御回路６５）が無かったとする。そうすると、グループ＃１に属するシンドロームＳi計算回路にもパリティ＃２が入力される。パリティ＃１の生成多項式Ｇ1（ｘ）はグループ＃１に対応する根（図２３の例では、α1，α3）を持つが、生成多項式Ｇ2（ｘ）の根は持たない。したがって、グループ＃１のシンドロームＳi計算回路に、パリティ＃２が入力されると、シンドロームにおいて符号語の寄与を排除できず、誤り位置多項式を求めるのが非常に困難になる（シンドロームが誤りパターンにのみ依存して決まることが誤り位置多項式を効率的に求めるために必要である）。そのため、通常の誤り位置多項式計算回路と、チエンサーチ回路とでは誤り訂正ができない。
【０１３３】
また、グループ＃１に属するシンドロームＳi計算回路への入力データを「データとパリティ#１」を入力した時点で打ち切ってしまうと、グループ＃１とグループ＃２とで入力した多項式の次数が異なるため、誤り位置を示す値が定められず、誤りロケータを定義できない。そのため、誤り位置多項式そのものが定義できず、通常の誤り位置多項式計算回路と、チエンサーチ回路とでは誤り訂正ができないことになる。
【０１３４】
また、復号の各段階において、復号に使用しないパリティの生成に用いた生成多項式の根に対応するシンドローム計算を行う部分は、動作を停止するような制御を行うことで、各段階での誤り訂正処理でシンドローム計算部２６１を共用しても、消費電力を、各段階での誤り訂正に必要な最低限の回路構成とした場合と同程度に抑えることができる。
【０１３５】
また、パリティ＃２を保護する外部パリティを用いたパリティの誤り訂正処理では、パリティ＃１、パリティ＃２を用いた誤り訂正処理とは別の復号回路を備えてもよいが、復号回路を共用することもできる。
【０１３６】
具体的には、パリティ＃２を保護する外部パリティの訂正能力をｔ2ビット以下に設定し、ｔ2重の誤り訂正を行うための回路を備えていれば、外部パリティを用いた誤り訂正処理についても回路を共用できる。特に外部パリティの生成多項式に、生成多項式Ｇ1（ｘ）を用い、かつ符号長も１段階目の符号語（ユーザデータ＋パリティ＃１）と同じになるように揃えた場合、１段階目のパリティ＃１を用いたユーザデータの誤り訂正処理と全く同じ処理で復号を行うことができ、制御を簡単化できる。
【０１３７】
図２６は、外部パリティを用いた復号も行う場合の復号部２６ｂの構成例を示す図である。図２６のdecoder１００は、図２１のシンドローム計算部２６１、誤り位置多項式演算部２６２、チエンサーチ部２６３および復号制御部２６４により構成される。図２６に示すように、外部パリティを用いた復号と共用する場合、訂正済み拡張パリティ一時保存領域１０１およびセレクタ回路１０２をさらに備える。
【０１３８】
セレクタ回路１０２は、制御部２３または復号制御部２６４の制御により、パリティ＃１を用いた１段階目の誤り訂正処理では、入力データを選択してdecoder１００へ入力する。１段階目の誤り訂正処理に失敗した場合、セレクタ回路１０２は、制御部２３または復号制御部２６４の制御により、入力データを選択してdecoder１００へ入力する。この際、入力データとしては、パリティ＃２と外部パリティが入力される。外部パリティを用いたパリティ＃２の誤り訂正処理を行った後、誤り訂正処理後のパリティ＃２は、一時的に訂正済み拡張パリティ一時保存領域１０１に格納される。
【０１３９】
そして、ユーザデータに対する２段階目の誤り訂正処理を行う際に、セレクタ回路１０２は、制御部２３または復号制御部２６４の制御により、はじめは入力データ（ユーザデータとパリティ＃１）を選択し、ユーザデータとパリティ＃１の入力が終わると、訂正済み拡張パリティ一時保存領域１０１に格納されたデータ（誤り訂正済みのパリティ＃２）を選択してdecoder１００へ入力する。
【０１４０】
以上のように、本実施の形態では、２段階で誤り訂正符号化を実施する場合に、パリティ＃１とパリティの両方を用いた場合の訂正能力に対応する復号部２６ｂを有し、シンドロームＳi計算回路を、同一段階の生成多項式の根に対応するシンドロームを計算するシンドロームＳi計算回路を同一グループとして段階ごとにグループ分けする。そして、２段階目の誤り訂正処理では、１段階目に対応するグループに属するシンドロームＳi計算回路には、パリティ＃２の代わりに０を入力するようにした。このため、１段階目と２段階目の誤り訂正処理で回路を共有でき、かつ誤り位置を正しく定義することができる。
【０１４１】
（第６の実施の形態）
図２７は、第６の実施の形態にかかる半導体記憶装置におけるシンドローム計算部２６１ａのシンドロームＳi計算回路の構成例を示すブロック図である。本実施の形態の半導体記憶装置の構成は、第５の実施の形態のシンドーム計算部２６１を本実施の形態のシンドローム計算部２６１ａに替える以外は、第５の実施の形態の半導体記憶装置と同様である。以下、第５の実施の形態と異なる部分を説明する。
【０１４２】
第１の実施の形態では、シンドローム計算部２６１に、１ビットずつデータを入力する例を示したが、本実施の形態では、シンドローム計算部２６１ａにおいてＰ（Ｐは２以上の整数）ビットの並列処理を行う例について説明する。本実施の形態の符号化演算は、第５の実施の形態と同様に２段階の誤り訂正方式で実施されているとする。図２７では、Ｐ＝２の場合のグループ＃１のシンドロームＳi計算回路の構成例を示している。グループ＃１のシンドロームＳi計算回路は、セレクタ回路７１−１，７１−２と、ＸＯＲ回路７２−１，７２−２と、αiの乗算を行う乗算器７３−１，７３−２と、レジスタ７４と、制御回路７５と、を備える。なお、Ｐが３以上の場合も、同様に、各シンドロームＳi計算回路が乗算器およびＸＯＲ回路をＰ個備え、グループ＃１のシンドロームＳi計算回路が、Ｐ個のセレクタ回路と制御回路７５とを備えるようにすればよい。
【０１４３】
本実施の形態のシンドローム計算部２６１ａは、第５の実施の形態と同様に、グループ＃２のシンドロームＳi計算回路も備えるが、グループ＃２のシンドロームＳi計算回路については、従来のＰビット並列処理を行うシンドロームＳi計算回路と同様である。すなわち、図２７のシンドロームＳi計算回路からセレクタ回路７１−１，７１−２および制御回路７５を削除したものであるため図示を省略する。
【０１４４】
グループ＃１のシンドロームＳi計算回路のセレクタ回路７１−１，７１−２は、制御回路７５からの制御により、入力データ（ユーザデータ、パリティ）と０のうちいずれか一方を選択してそれぞれＸＯＲ回路７２−１，７２−２へ入力する。具体的には、制御回路７５は、ユーザデータとパリティ＃１が入力される間は入力データを選択し、パリティ＃２が入力される間は０を選択するようセレクタ回路７１−１，７１−２を制御する。制御回路７５は、第５の実施の形態の制御回路６５と同様に複数のシンドロームＳi計算回路で共用してもよい。
【０１４５】
並列処理を行う場合、シンドロームＳi計算回路には、１サイクルでＰビットずつ入力データが入力される。図２７では、Ｐ＝２であり、一例として、入力データの０番目のビットと１番目のビット（図２７のＩＤＡＴＡ［０］、ＩＤＡＴＡ［１］）が同時に入力される例を示している。セレクタ回路７１−１，７１−２による入力データと０との切り替え動作以外は、通常の並列処理の動作と同様である。すなわち、Ｐビット並列処理を行う場合の１サイクルでのレジスタ７４の更新値ＲＥＧ＿ｕｐｄａｔｅは、ＣＵＲを更新前のレジスタ７４の値とするとき、以下の式（３）で表すことができる。
ＲＥＧ＿ｕｐｄａｔｅ＝
ＣＵＲ×（αi）P 
＋  ＩＤＡＴＡ［０］×（αi）P-1
＋  ＩＤＡＴＡ［１］×（αi）P-2
…
＋  ＩＤＡＴＡ［Ｐ−２］×（αi）1
＋  ＩＤＡＴＡ［Ｐ−１］×（αi）0                          …（３）
【０１４６】
本実施の形態のシンドローム計算手順は、図２５に示した処理手順のステップＳ３１およびステップＳ３４において、１ビット入力の代わりにＰビット入力とする以外は第５の実施の形態の手順と同様である。
【０１４７】
以上のようにシンドローム計算において並列処理を行う場合、パリティ＃１、パリティ＃２のビット数が並列ビット数Ｐの倍数でない場合、入力データがＰビット未満となるサイクルが生じる。なお、ユーザデータはＰビットの倍数であるとする（Ｐビットの倍数でない場合も０等のデータが付加することによりことにより、最終的にＰビットの倍数であるとする）。一方、パリティ＃１、パリティ＃２については、それぞれ生成多項式Ｇ1（ｘ）、Ｇ2（ｘ）の最大次数により決定される数値であり、Ｐとは無関係に生成される。
【０１４８】
入力データがＰビット未満となるサイクルを含む場合、当該サイクルの処理は、他のＰビット並列処理と異なることになり、別のハードウェアを用意する等の対応が必要となる。そこで、本実施の形態では、符号化演算の際に、別のハードウェアを用意する等の対応を実施しなくてよいように、パリティ＃１、パリティ＃２のビット数をそれぞれＰの倍数となるようゼロパディング（ゼロ挿入処理）を実施する。
【０１４９】
図２８は、本実施の形態のデータフォーマットの一例を示す図である。ここでは、パリティ＃１のビット数（生成多項式Ｇ1（ｘ）の最大次数になる）がＰビットの整数倍になっていないとする。本実施の形態では、roundup（パリティ＃１のビット数／Ｐ）×Ｐ−パリティ＃１のビット数＝ｄ1としたとき、図２８に示す位置８１に、ｄ1ビットのゼロパディングを行う。このｄ1ビットのゼロは、符号化部２５におけるパリティ＃１を計算する演算で、情報多項式の下位ｄ1ビットとして入力する。
【０１５０】
パリティ＃２についても、同様に、roundup（パリティ＃２のビット数／Ｐ）×Ｐ−パリティ＃２のビット数＝ｄ2としたとき、図２８に示す位置８２に、ｄ2ビットのゼロパディングを行う。また、ｄ2ビットのゼロについては、符号化部２５におけるパリティ生成演算に入力せず、パリティ＃２の生成後にゼロを付加する。
【０１５１】
このようにすることで、図２８に示すように、パリティ＃１、パリティ＃２のビット数がＰの倍数となり、シンドローム計算において入力データがＰビット未満となるサイクルの発生を防ぐことができる。このため、入力データがＰビット未満となるサイクルに対応する場合に比べ、余分な処理を行う必要がないため、回路規模を抑えることができる。
【０１５２】
また、パリティ＃１のビット数がＰの倍数でない場合、２段階目の誤り訂正処理では、パリティ＃１とパリティ＃２の間に無効なデータが含まれることになり、毎サイクル毎にＰ箇所の位置が誤りかどうかチェックするＰ並列チエンサーチ回路を使うときに、無効なデータ部分を飛ばした誤りロケータの割り当てを行うことになり、Ｐビットにアラインしたフォーマットに合わせて誤り位置を出力するためにはその部分をずらして誤り位置を出す処理が必要になる。図２８に示すように、ｄ1ビットのゼロパディングを行うことにより、このような処理は不要になり、回路規模を抑えることができる。
【０１５３】
また、ｄ1ビットのゼロを符号化部２５におけるパリティ＃１の生成処理に入力せずに、パリティ＃１を生成した後にゼロを付加してもよい。この場合、ｄ1ビットのゼロの位置８１をパリティ＃１の最後とする。図２９は、ｄ1ビットのゼロパディングの位置８１をパリティ＃１の最後の部分とした場合のデータフォーマットの一例を示す図である。位置８１は、パリティ＃１の始めではなく最後としている。同様に、ｄ2ビットのゼロを符号化部２５におけるパリティ＃２の生成処理に入力せずに、パリティ＃２を生成した後にｄ2ビットのゼロを付加するようにしてもよい。ｄ2ビットのパディングの位置８２もパリティ＃２内の最後とする。
【０１５４】
なお、本実施の形態では、符号化部２５ｂにおけるパリティ演算にゼロを挿入してパリティのビット数をＰの倍数とする処理と、符号化部２５ｂにおいてパリティ（ビット数はＰの倍数でない）を生成した後、パリティのビット数をＰの倍数となるようゼロを挿入する処理と、の両方をゼロパディングと呼ぶこととする。
【０１５５】
図３０は、３段階の誤り訂正方式を採用する場合のデータフォーマットの一例を示す図である。パリティ＃１の始めの部分の位置８１にｄ1ビットのゼロをパディングし、パリティ＃２の始めの部分の位置８２にｄ2ビットのゼロをパディングする。具体的には、図３０の例では、図２８の例と同様に、ｄ1ビットのゼロをパリティ＃１の生成時に情報多項式の下位ビットとして入力する。また、ｄ2ビットのゼロをパリティ＃２の生成時に情報多項式の下位ビット（パリティ＃１の下位ビット）として入力する。なお、ここではパリティ＃３のビット数はＰの倍数であるとしてゼロパディングを行っていないが、パリティ＃３のビット数がＰの倍数でない場合は、パリティ＃３の生成後にroundup（パリティ＃３のビット数／Ｐ）×Ｐ−パリティ＃３のビット数＝ｄ3ビットをパリティ＃３の始めまたは最後に付加する。また、ｄ1ビットのゼロ、ｄ2ビットのゼロについても、パリティ＃１、パリティ＃２のそれぞれの生成時に入力とせず、パリティ＃１、パリティ＃２の生成後にゼロを付加するようにしてもよい。この場合、位置８１、位置８２はパリティ＃１、パリティ＃２の最後の部分とする。
【０１５６】
図３１は、ｎ段階の誤り訂正方式において復号時のＰビット並列処理に対応したパリティ＃ｎを生成するための符号化部２５ｂの構成例を示す図である。ここでは、パリティ＃ｎの生成時に、ｄnビット（ｄn＝roundup（パリティ＃ｎのビット数／Ｐ）×Ｐ−パリティ＃ｎのビット数を情報多項式の下位ビットとして入力する場合に構成例を示している。図３１に示す符号化部２５は、入力データに対して生成多項式Ｇn（ｘ）を用いた剰余計算を行うＰ並列剰余計算回路９１と、パリティ＃ｎの計算途中結果を保持するレジスタ（ＦＦ）９３と、レジスタ９３への入力を切り替えるセレクタ回路９５と、セレクタ回路９５の切り替えを制御するセレクタ回路制御回路９２と、ｄnビットのゼロに対して生成多項式Ｇn（ｘ）を用いた剰余計算を行うｄnビットパディング処理部９４と、を備える。
【０１５７】
Ｐ並列剰余計算回路９１に対する（すなわち、符号化部２５に対する）入力データ（情報ビット）は、ユーザデータ＋パリティ＃１＋・・・＋パリティ＃（ｎ−１）となる（ただし、パリティ＃１を計算する際は、入力データはユーザデータのみである）。符号化部２５へ入力データが入力されている間は、セレクタ回路制御回路９２は、Ｇn（ｘ）によるＰ並列剰余計算回路９１の出力をレジスタ９３へ入力するようセレクタ回路９５を制御する。入力が完了すると、セレクタ回路制御回路９２は、ｄnビットパディング処理部９４回路の出力をレジスタ９３へ入力するようセレクタ回路９５を制御する。
【０１５８】
ｄnビットパディング処理部９４回路は、例えば、ｄn’（ｄn’はｄnの約数）並列のＧn（ｘ）による剰余回路構成でされ、入力をゼロに固定し、ｄn÷ｄn’サイクル分、この回路の出力でレジスタ９３を更新すると、符号化処理は完了し、パリティ＃ｎを出力することができる。
【０１５９】
なお、以上では、外部パリティを用いる場合について説明を省略したが、外部パリティを用いたパリティ＃ｉ（ｉ＝１，２，…，ｎ）の復号処理に、別の回路を用いる場合は外部パリティを用いたパリティ＃ｉの復号処理は通常の復号処理と同様である。第１の実施の形態で述べたように、外部パリティを用いたパリティ＃ｉと、パリティ＃１等を用いたユーザデータの復号処理とで回路を共有する場合は、外部パリティを用いたパリティ＃ｉの復号処理においてもＰ並列演算が実施される。このため、外部パリティについてもビット数がＰの倍数でない場合は、Ｐの倍数となるようゼロパディングを行うことが望ましい。
【０１６０】
以上のように、本実施の形態では、復号演算においてＰビット並列処理を実施する場合に、符号化演算において各段階のパリティのビット数がＰの倍数でない場合、各段階のパリティがＰの倍数となるようゼロパディングを行うようにした。このため、復号時に、パリティがＰの倍数でないことにより生じる「余分な処理を行う必要がないため、回路規模を抑えることができる。
【０１６１】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６２】
１  半導体記憶装置、２  メモリコントローラ、３  半導体メモリ部、２２  メモリＩ／Ｆ、２３  制御部、２４，２４ａ，２４ｂ  符号／復号部、２５，２５ａ，２５ｂ，４０  符号化部、２６，２６ａ，２６ｂ，５０  復号部、６１−１，６１−２，７１−１，７１−２  セレクタ回路、６５，７５  制御回路、２６１  シンドローム計算部、２６２  誤り位置多項式演算部、２６３  チエンサーチ部、２６４  復号制御部。
【図１】
0005768022.tif 000002
【図２】
0005768022.tif 000003
【図３】
0005768022.tif 000004
【図４】
0005768022.tif 000005
【図５】
0005768022.tif 000006
【図６】
0005768022.tif 000007
【図７】
0005768022.tif 000008
【図８】
0005768022.tif 000009
【図９】
0005768022.tif 000010
【図１０】
0005768022.tif 000011
【図１１】
0005768022.tif 000012
【図１２】
0005768022.tif 000013
【図１３】
0005768022.tif 000014
【図１４】
0005768022.tif 000015
【図１５】
0005768022.tif 000016
【図１６】
0005768022.tif 000017
【図１７】
0005768022.tif 000018
【図１８】
0005768022.tif 000019
【図１９】
0005768022.tif 000020
【図２０】
0005768022.tif 000021
【図２１】
0005768022.tif 000022
【図２２】
0005768022.tif 000023
【図２３】
0005768022.tif 000024
【図２４】
0005768022.tif 000025
【図２５】
0005768022.tif 000026
【図２６】
0005768022.tif 000027
【図２７】
0005768022.tif 000028
【図２８】
0005768022.tif 000029
【図２９】
0005768022.tif 000030
【図３０】
0005768022.tif 000031
【図３１】
0005768022.tif 000032