"生成多項式を用いた除算によってパリティ検査を実施可能な線形符号方式をサポートし、入力データに前記生成多項式を適用して線形符号化データを得る線形符号化部と、LDPC符号のパリティ検査行列に対応する生成行列を前記線形符号化データに適用し、出力データを得るLDPC符号化部とを具備し、前記パリティ検査行列は、数式:を満たす、誤り訂正符号化装置。LDPC符号のパリティ検査行列を用いて入力データを復号し、LDPC復号データを得るLDPC復号部と、生成多項式を用いた除算によってパリティ検査を実施可能な線形符号方式をサポートし、前記LDPC復号データに前記生成多項式を適用して誤りを検査し、出力データを得る誤り検査部とを具備し、前記パリティ検査行列は、数式:を満たす、誤り訂正復号装置。生成多項式を用いた除算によってパリティ検査を実施可能な線形符号方式をサポートし、第1のデータに前記生成多項式を適用して第2のデータを得る線形符号化部と、LDPC符号のパリティ検査行列に対応する生成行列を前記第2のデータに適用し、第3のデータを得るLDPC符号化部と、前記第3のデータが記憶される不揮発性半導体メモリと、前記パリティ検査行列を用いて、前記不揮発性半導体メモリから前記第3のデータを読み出すことによって得られた第4のデータを復号し、第5のデータを得るLDPC復号部と、前記線形符号方式をサポートし、前記第5のデータに前記生成多項式を適用して誤りを検査し、第6のデータを得る検査部とを具備し、前記パリティ検査行列は、数式:を満たす、不揮発性半導体記憶システム。第1の誤り訂正符号方式に基づいて入力データを符号化して前記第1のデータを得る第1の誤り訂正符号化部と、前記第1の誤り訂正符号方式に基づいて前記第6のデータを復号して出力データを得る第1の誤り訂正復号部とを更に具備する、請求項3の不揮発性半導体記憶システム。前記パリティ検査行列は、設計時において前記数式を満足することが確認されている、請求項3の不揮発性半導体記憶システム。生成多項式を用いた除算によってパリティ検査を実施可能な線形符号方式と組み合わせて利用されるLDPC符号のパリティ検査行列の候補を作成することと、前記パリティ検査行列の候補が、数式:を満足するか否かを判定することと、前記パリティ検査行列の候補が前記数式を満足するならば、当該パリティ検査行列の候補をパリティ検査行列と決定することとを具備し、前記パリティ検査行列の候補が前記数式を満足するまで、前記パリティ検査行列の候補を作成することと、前記パリティ検査行列の候補が前記数式を満足するか否かを判定することとが繰り返される、パリティ検査行列生成方法。実施形態は、誤り検出率の向上を目的とする。実施形態によれば、誤り訂正符号化装置は、線形符号化部と、LDPC符号化部とを含む。線形符号化部は、生成多項式を用いた除算によってパリティ検査を実施可能な線形符号方式をサポートし、入力データに生成多項式を適用して線形符号化データを得る。LDPC符号化部は、LDPC符号のパリティ検査行列に対応する生成行列を線形符号化データに適用し、出力データを得る。パリティ検査行列は、明細書中の数式1を満たす。以下、図面を参照しながら実施形態の説明が述べられる。尚、以降の説明において、復号及び訂正という用語がしばしば使用されるが、両者は概ね同じ意味である。具体的には、いずれも、正しい符号フレーム符号データを推定すること、即ち、誤り訂正と概ね同じ意味である。第1の実施形態第1の実施形態に係る誤り訂正符号化装置及び誤り訂正復号装置は、例えば記憶システム、通信システムなどに組み込まれる。以降の説明は、簡単化のために、本実施形態に係る誤り訂正符号化装置及び誤り訂正復号装置が、不揮発性半導体記憶システムに組み込まれることを前提に述べられる。但し、本実施形態に係る誤り訂正符号化装置及び誤り訂正復号装置は、通信システム、光記録システム、磁気記録システムなど、誤り訂正符号を利用可能なあらゆるシステムに適用されてよい。本実施形態に係る誤り訂正符号化装置及び誤り訂正復号装置は、例えば図1に示される不揮発性半導体記憶システム100に組み込まれる。図1の不揮発性半導体記憶システム100は、第1の誤り訂正符号化部101と、CRCCyclicRedundancyCheck符号化部102と、LDPC符号化部103と、不揮発性半導体メモリ104と、LDPC復号部105と、CRC検査部106と、制御部107と、バッファメモリ108と、第1の誤り訂正復号部109とを含む。ここで、本実施形態に係る誤り訂正符号化装置は、例えば、第1の誤り訂正符号化部101と、CRC符号化部102と、LDPC符号化部103とを含む。また、本実施形態に係る誤り訂正復号装置は、LDPC復号部105と、CRC検査部106と、制御部107と、バッファメモリ108と、第1の誤り訂正復号部109とを含む。第1の誤り訂正符号化部101は、図2に示されるように、不揮発性半導体記憶システム100の入力データに第1の誤り訂正符号に基づくパリティデータを付加し、第1のデータを得る。第1の誤り訂正符号化部101は、第1のデータをCRC符号化部102へと出力する。尚、第1の誤り訂正符号は、任意の方式の誤り訂正符号であってよい。第1の誤り訂正符号は、後述されるLDPC復号部105の復号失敗時例えばエラーフロア発生時、或いは、CRC検査部106による誤り検出時に、正しいデータを復号するために利用される。但し、第1の誤り訂正符号は必須でなく、必要に応じて第1の誤り訂正符号化部101及び第1の誤り訂正復号部109が除去されてよい。CRC符号化部102は、図2に示されるように、第1のデータを分割し、M組の第1のサブデータ1,,Mを得る。尚、図2はM=2である場合を示しているが、分割は必須でない。即ち、M=1も許容されるので、M≧1である。また、図2において、第1のデータのうちデータ部及びパリティデータ部の両方が等分割されているが、これらの一方または両方が不等分割されてもよい。或いは、データ部及びパリティデータ部を区別することなく、第1のデータが先頭から順番に等分割または不等分割されてもよい。以降の説明は、簡単化のために、図2の分割方式を前提とする。係る分割方式は、一般的な不揮発性半導体システムにおける分割方式に合致している。更に、CRC符号化部102は、図2に示されるように、M組の第1のサブデータ1,,MにM組のCRCパリティデータ1,,Mを夫々付加し、M組の第2のデータ1,,Mを得る。CRC符号化部102は、典型的には、第1のサブデータを生成多項式によって除算し、その剰余をパリティデータとして付加する。CRC符号化部102は、M組の第2のデータ1,,MをLDPC符号化部103へと出力する。尚、CRC符号化部102は、生成多項式を用いた除算によってパリティ検査を実施可能な任意の線形符号方式をサポートする線形符号化部に置き換えられてよい。この線形符号方式は、少なくとも誤り検出能力を持つが、更に誤り訂正能力を持ってもよい。具体的には、この線形符号方式は、ハミング符号、BCH符号、Reed-Solomon符号などであってよい。LDPC符号化部103は、図2に示されるように、M組の第2のデータ1,,MにM組のLDPC符号のパリティデータ1,,Mを夫々付加し、M組の第3のデータ1,,Mを得る。LDPC符号化部103は、典型的には、後述されるパリティ検査行列に対応するLDPC生成行列を第2のデータに乗算し、第3のデータを得る。パリティ検査行列の詳細は後述される。LDPC符号化部103は、M組の第3のデータ1,,Mを不揮発性半導体メモリ104へと出力する。不揮発性半導体メモリ104は、例えば複数のメモリセルがNAND型に接続されたアレイ構造を有するフラッシュメモリによって実現される。不揮発性半導体メモリ104は、メモリセルにM組の第3のデータ1,,Mを記録する。具体的には、不揮発性半導体メモリ104は、ページデータ単位でデータを読み書きできる。ページデータの容量は、フラッシュメモリの構成に依存するものの、概ね数KB程度である。1単位のページデータは、図2に示されるように、M組の第3のデータ1,,Mの少なくとも全てを包含する。尚、図1において不揮発性半導体記憶システム100の構成が簡略化されて描かれているが、不揮発性半導体記憶システム100はフラッシュメモリへのデータの書き込み、読み込みに必要な種々の機能部図示されないを当然に備える。各メモリセルには少なくとも2以上の閾値電圧が設定されており、この書き込み閾値電圧の数に応じて1ビット以上のデータを記憶することができる。例えば、1つのメモリセルに2ビットが記憶される場合には、2ビット値:11,10,01,00が4つの閾値電圧に夫々マッピングされる。尚、メモリセルの閾値電圧は、隣接セルとの容量結合などの理由により、揺らぐことがある。そして、この閾値電圧の揺らぎは、読み出しデータの誤りを引き起こす一因となる。以上、データの書き込みに関する構成要素とその動作が説明された。以下、データの読み出しに関する構成要素とその動作が説明される。不揮発性半導体メモリ104からM組の第4のデータ1,,Mが読み出され、LDPC復号部105へと出力される。前述の通り、M組の第4のデータ1,,Mは誤りを含み得る。即ち、M組の第4のデータ1,,Mは、M組の第3のデータ1,,Mと必ずしも一致しない。LDPC復号部105は、M組の第4のデータ1,,Mに対してLDPC復号処理を実施する。具体的には、LDPC復号部105は、後述されるパリティ検査行列を用いた繰り返し復号アルゴリズムを実施する。繰り返し復号アルゴリズムは、例えば、sum-productアルゴリズム、min-sumアルゴリズムなどである。LDPC復号部105は、繰り返し復号の各試行において、第4のデータの一時推定語にパリティ検査行列を乗算してパリティ検査を実施する。繰り返し復号の過程においてLDPC符号語が得られた場合即ち、復号が成功した場合に、当該LDPC符号語からLDPC符号のパリティデータを除去したM組の第5のデータ1,,MをCRC検査部106へと出力する。M組の第5のデータ1,,Mは、LDPC符号語のデータ部に相当するが、当該LDPC符号語は正しく訂正されたLDPC符号語であるかもしれないし、誤訂正されたLDPC符号語であるかもしれない。一方、LDPC復号部105は、繰り返し復号の試行回数が最大値に達してもLDPC符号語を得られない即ち、復号に失敗することもある。係る場合の扱いは、特に制限されないが、例えばCRC検査を省略して第1の誤り訂正符号に基づく復号を実施することが想定できる。CRC検査部106は、M組の第5のデータ1,,MのCRC検査を行う。具体的には、CRC検査部106は、第5のデータを生成多項式で除算し、剰余が零であるか否かを検査する。剰余が零であれば第5のデータから誤りが検出されず、剰余が非零であれば第5のデータから誤りが検出される。CRC検査部106は、M組の第5のデータ1,,Mの各々の検査結果即ち、誤りが検出されたか否か1,,Mを制御部107に通知する。また、CRC検査部106は、M組の第5のデータ1,,MからCRCパリティデータを除去し、M組の第6のデータ1,,Mを得る。CRC検査部106は、M組の第6のデータ1,,Mをバッファメモリ108に保存する。更に、CRC検査部106は、誤りが検出されなかった第6のデータについて、第1の誤り訂正符号のパリティサブデータを除去して直接外部に出力してもよい。係る措置によれば、誤りのない第6のデータについて、第1の誤り訂正復号部109による復号処理を省略できるので、データ出力のスループットが向上する。制御部107は、CRC検査部106からの検査結果1,,Mを参照し、少なくとも1つの第6のデータについて誤りが検出されたか否かを確認する。少なくとも1つの第6のデータについて誤りが検出されているならば、制御部107はバッファメモリ108にM組の第6のデータ1,,Mの出力指示を与えると共に、第1の誤り訂正復号部109に復号処理の実施指示を与える。更に、制御部107は、CRC検査部106からの検査結果1,,Mを第1の誤り訂正復号部109に通知してもよい。係る措置によれば、第1の誤り訂正復号部109は誤りが含まれない第6のデータを識別できるので、不必要な復号処理を省略できる。即ち、第6のデータ1,,Mの全体を対象とする場合に比べて、第1の誤り訂正復号部109による復号処理を高速化できる。バッファメモリ108は、CRC検査部106からのM組の第6のデータ1,,Mを保存する。バッファメモリ108は、制御部107から出力指示を与えられると、これらM組の第6のデータ1,,Mを結合した第7のデータを第1の誤り訂正復号部109へと出力する。第1の誤り訂正復号部109は、制御部107から復号処理の実施指示を受けると、バッファメモリからの第7のデータに第1の誤り訂正符号に基づく復号処理を行う。尚、前述の通り、第1の誤り訂正復号部109は、制御部107から通知されるCRC検査結果1,,Mを利用して効率的な復号処理を行ってよい。第1の誤り訂正復号部109は、第7のデータの復号処理において符号語を得る即ち、誤りが訂正されると、当該符号語から第1の誤り訂正符号のパリティデータを除去し、それから外部に出力する。他方、復号処理の結果、符号語が得られなかった誤りが訂正されなかった場合の扱いは特に制限されない。例えば、誤りを含むデータが外部に出力されてもよいし、されなくてもよい。いずれにせよ、誤りが訂正されなったことを確認可能な情報が外部に出力されることが望ましい。以上説明されたように、不揮発性半導体記憶システム100において、LDPC復号部105及びCRC検査部106によって2重の誤り検出が実施される。即ち、誤訂正されたLDPC符号語を検出するために、LDPC符号にCRC符号或いはその他の外符号であってもよいが組み合わせられている。CRC符号を利用すれば、誤訂正されたLDPC復号データに含まれる誤りを検出できる可能性がある。しかしながら、LDPC符号の設計次第では、誤訂正に基づくLDPC復号データが偶然にもCRC符号語に一致するおそれがある。この場合に、外符号が機能せず、誤りは検出されない。即ち、CRC符号をLDPC符号と単純に組み合わせたとしても、システム例えば、LDPC符号を利用する記憶システム、通信システムなど全体の誤り検出率を向上させることは容易でない。例えば、LDPC復号部105によって誤訂正された符号語に基づく第5のデータがCRC符号語に一致していれば、CRC検査部106は機能しないので当該第5のデータに含まれる誤りを検出できない。そこで、本実施形態に係る誤り訂正復号装置は、後述される数式1を満たすLDPC符号のパリティ検査行列を使用する。また、本実施形態に係る誤り訂正符号化装置は、このパリティ検査行列に対応するLDPC符号生成行列を使用する。一般に、正しいLDPC符号語便宜的に、第1のLDPC符号語と称されると誤訂正されたLDPC符号語便宜的に、第2のLDPC符号語と称されるとの間のハミング距離は小さくなり易い傾向にある。また、LDPC符号は線形符号であるから、符号語間の距離もまたLDPC符号語便宜的に、第3のLDPC符号語と称されるの1つである。符号語間の距離が小さいほど誤訂正は生じ易いといえるので、第3のLDPC符号語が少数の1及び多数の0によって構成される低重み語になり易い傾向にあることは明らかである。ここで、第1のLDPC符号語が0のみで構成されると仮定すると、第2のLDPC符号語及び第3のLDPC符号語は一致する。即ち、係る仮定の下では第2のLDPC符号語は低重み語になり易い傾向にある。この低重み語からLDPC符号のパリティデータを除去して得られる第5のデータこれは、低重みの符号系列であるといえるがCRC符号語と一致しないCRC検査を満たさないようにLDPC符号を設計しておけば、CRC検査部106は0のみで構成されるLDPC符号語の誤訂正に基づく第5のデータの誤りを検出できる。更に、CRC符号もまた線形符号である。即ち、任意の2つのCRC符号語間の距離もまたCRC符号語の1つに一致する。故に、係る低重みの符号系列がCRC符号語と一致しないようにすることは、任意のCRC符号語第1のLDPC符号語からLDPCのパリティデータを除去して得られる符号系列からの距離が当該低重みの符号系列に等しい符号系列第2の符号語からLDPCのパリティデータを除去して得られる符号系列がCRC符号語と一致しないようにすることを意味する。従って、低重みのLDPC符号語からLDPC符号のパリティデータを除去して得られる第5のデータをCRC符号語と一致しないようにLDPC符号を設計しておけば、CRC検査部106はLDPC復号部105の誤訂正を高精度に検出可能である。そして、係る条件を満足するためには、LDPC符号のパリティ検査行列は下記数式1を満足する必要がある。上記数式1は、LDPC符号のパリティ検査行列=Hに基づいて定義される低重みLDPC符号語のうちのデータ部=dxがCRC検査部106においてCRCエラーとなる条件を表している。即ち、LDPC符号のパリティ検査行列=Hが上記数式1を満たすならば、誤訂正されたLDPC符号語に含まれる誤りはCRC検査部106によって高確率に検出される。パリティ検査行列=Hは、より詳細には、複数のq行q列のブロックを組み合わせて形成される。各ブロックは、q行q列の巡回シフト行列単位行列を巡回シフトすることによって得られる行列またはq行q列の零行列である。係るパリティ検査行列=Hに基づくLDPC符号は、準巡回LDPC符号と呼ばれる。各ブロックは、バイナリ表現に限られず、q-1次の多項式で表現することも可能である。例えば、各ブロックの第1行第1列の要素をx0=1の係数とし、第q行第1列の要素をxq-1の係数とすれば多項式表現が可能である。従って、パリティ検査行列=Hは、下記の数式2に示されるように、q-1次多項式を要素として持つJ行K列の行列として表現できる。更に、符号語=cも同様に、q列単位でq-1次の多項式で表現できる。具体的には、q列ごとに列インデックスの小さい要素から順にx0,,xq-1の係数に割り当てることによって多項式表現は可能である。従って、符号語=cは、下記の数式3に示されるように、K個のq-1次多項式を要素として持つ行ベクトルとして表現できる。一例として、q=3、J=2、K=3の場合における符号語=c及びパリティ検査行列=Hの多項式表現及びバイナリ表現が図3に示されている。尚、符号語の多項式表現は、図3の例に限られず、例えば多項式の順序を反転させてd’x=xndx-1とすることも可能である。更に、下記の数式4に示されるように、LDPC符号のパリティ検査を多項式で表現することもできる。下記の数式4は、第j行のパリティ検査を示す。多項式ベクトル=cは、パリティ検査行列=Hによって定義される符号語であるので、sjxは全てj=1,,J零となる。即ち、上記数式4においてcixとして一時推定語の各要素の多項式表現を与えた場合に全てのjについてsjx=0であれば、当該一時推定語はLDPC符号語と判定される。一方、少なくとも1つのjについてsjx=0でなければ、当該一時推定語はLDPC符号語でないと判定される。低重みの符号系列は、下記数式5によって定義できる。尚、下記数式5によって低重み語を定義できることは、非特許文献1を参照すれば理解可能であるので、その詳細は省略される。この低重み符号系列は、以下に証明されるように、LDPC復号部105におけるパリティ検査を満たす低重みLDPC符号である。上記数式4及び数式5に基づいて、この低重み符号系列のパリティ検査は下記数式6によって表現できる。ここで、関数permは、前述の通り行列式の計算を意味するので、上記数式6は、下記の行列の余因子展開とみなすことができる。上記行列は、その第1行と第j1行とが必ず一致するので、明らかにフルランクでない。即ち、行列式は必ず零となり、全てのjについてsjx=0である。従って、上記数式5に示される低重み符号系列は、LDPC復号部105におけるパリティ検査を満たす低重みLDPC符号語である。そして、前述の通り、この低重みLDPC符号語のうちのデータ部から、CRC検査部106は誤りを検出できる。以下、図4を用いて数式1を満足するLDPC符号のパリティ検査行列の生成方法が説明される。誤り符号化装置及び誤り復号装置の設計時に係るアルゴリズムを適用することによって、LDPC符号のパリティ検査行列が数式1を満足することを保証できる。尚、図4のアルゴリズムにおいて、簡単化のために、列インデックスが小さいほど列次数が大きい換言すれば、列インデックスが大きいほど列次数が小さいパリティ検査行列=Hが生成対象とされる。まず、種々のパラメータが入力される。具体的には、パリティ検査行列=Hの行数=J及び列数=Kと、第k列に含まれる非零ブロックの総数を表す非零ブロック分布=Dkとが入力される。更に、初期化処理として変数iにKが代入される。更に、変数eに1が代入される。初期化処理の後に、処理はステップS201に進む。ステップS201において、iが正値であるか否かが判定される。iが正値であれば処理はステップS202に進み、そうでなければ処理はステップS205に進む。ステップS205において、数式1を満たすことが確認済みのパリティ検査行列Hが生成されているので、これが出力され、処理は終了する。ステップS202において、eがDi未満であるか否かが判定される。eがDi未満であれば処理はステップS203に進み、そうでなければ処理はステップS204に進む。ステップS203において、PEGProgressiveEdgeGrowthなどのアルゴリズムを用いて多項式hj,ixが決定される。PEGの詳細は非特許文献2に記載されているので、その詳細は省略される。更に、eが1だけインクリメントe=e1され、処理はステップS202に戻る。ステップS204において、パリティ検査行列の第i列から第K列までの候補であるH{i,,K}が数式1を満足するか否かが判定される。H{i,,K}が数式1を満足すれば処理はステップS206に進み、そうでなければ処理はステップS207に進む。ステップS206において、iが1だけデクリメントi=i-1され、処理はステップS201に戻る。ステップS207において、eに1が代入され、処理はステップS203に戻る。図4のアルゴリズムによれば、パリティ検査行列=Hの第K列から第1列まで順番に、対象列第i列の多項式要素の候補が作成され、当該候補に基づくパリティ検査行列が数式1を満足するか否かが確認され、数式1が満足される場合には対象列第i列の多項式要素が確定し、そうでない場合には対象列の多項式要素の候補が改めて作成される。尚、パリティ検査行列=Hの生成方法は、図4の例に限られず、生成されるパリティ検査行列=Hが数式1を満足することを確認できるものであればよい。以上説明したように、第1の実施形態に係る誤り訂正符号化装置及び誤り訂正復号装置は、CRC符号と組み合わせて、数式1を満足するLDPC符号のパリティ検査行列に基づいてLDPC符号化及びLDPC復号を実施する。従って、この誤り訂正符号化装置及び誤り訂正復号装置によれば、低重みLDPC符号語のデータ部がCRC符号語に一致しないので、LDPC復号において誤訂正が生じたとしてもCRC検査によって高確率に誤り検出できる。上記各実施形態の処理は、汎用のコンピュータを基本ハードウェアとして用いることで実現可能である。上記各実施形態の処理を実現するプログラムは、コンピュータで読み取り可能な記憶媒体に格納して提供されてもよい。プログラムは、インストール可能な形式のファイルまたは実行可能な形式のファイルとして記憶媒体に記憶される。記憶媒体としては、磁気ディスク、光ディスクCD-ROM、CD-R、DVD等、光磁気ディスクMO等、半導体メモリなどである。記憶媒体は、プログラムを記憶でき、かつ、コンピュータが読み取り可能であれば、何れであってもよい。また、上記各実施形態の処理を実現するプログラムを、インターネットなどのネットワークに接続されたコンピュータサーバ上に格納し、ネットワーク経由でコンピュータクライアントにダウンロードさせてもよい。本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。"