(57)【特許請求の範囲】
【請求項１】
ｑ（Ｎ−Ｊ）個（ｑ，Ｊ，Ｎは自然数であって、Ｎ＞Ｊ）のシンボルを備えるデータシンボル列を入力し、ｑＪ個のシンボルを備えるパリティシンボル列を前記データシンボル列に付加してｑＮ個のシンボルを備える符号語を生成する符号化装置において、
前記符号語は、ｑＪ行×ｑＮ列のパリティ検査行列を用いたパリティ検査を満足し、
前記パリティ検査行列において前記パリティシンボル列に対応するｑＪ行×ｑＪ列の第１の部分行列は、ｑＬ行×ｑＬ列（Ｌは自然数であって、Ｊ＞Ｌ）の第１の単位行列とｑ（Ｊ−Ｌ）行×ｑＬ列の第１の非零行列とを備えるｑＪ行×ｑＬ列の第２の部分行列を含む、
符号化装置。
【請求項２】
前記前記第１の部分行列は、ｑＬ行×ｑ（Ｊ−Ｌ）列の第２の非零行列とｑ（Ｊ−Ｌ）行×ｑ（Ｊ−Ｌ）列の第２の単位行列とを備えるｑＪ行×ｑ（Ｊ−Ｌ）列の第３の部分行列を更に含み、
前記第１の非零行列及び前記第２の非零行列の行列積は零行列である、
請求項１の符号化装置。
【請求項３】
前記パリティシンボル列は、ｑ（Ｊ−Ｌ）個のシンボルを備える第１の部分パリティシンボル列と、ｑＬ個のシンボルを備える第２の部分パリティシンボル列とを備え、
前記第１の部分パリティシンボル列は、前記データシンボル列に基づいて生成され、
前記第２の部分パリティシンボル列は、前記第１の部分パリティシンボル列及び前記データシンボル列に基づいて生成される、
請求項１または２の符号化装置。
【請求項４】
前記パリティ検査行列は、Ｊ×Ｎ個のｑ行×ｑ列のブロック行列を配列することによって形成され、
前記ブロック行列の各々は、非零行列及び零行列のいずれか一方である、
請求項１乃至３のいずれか１項に記載の符号化装置。
【請求項５】
前記ブロック行列の各々は、巡回シフト行列及び零行列のいずれか一方である、
請求項４の符号化装置。
【請求項６】
前記ブロック行列の各々は、各行に１つだけ非零要素を含む非零行列及び零行列のいずれか一方である、
請求項４の符号化装置。
【請求項７】
Ｌ＝Ｊ−２であり、
前記第１の非零行列は、２×（Ｊ−２）個のｑ行×ｑ列のブロック行列を配列することによって形成され、
前記ブロック行列の各々は、非零行列である、
請求項１または２の符号化装置。
【請求項８】
請求項１または２の符号化装置と、
前記符号語を記憶する半導体メモリと
を具備する半導体メモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
実施形態は、誤り訂正符号化技術に関する。
【背景技術】
【０００２】
強力な誤り訂正能力を持つ誤り訂正符号の１つとして、ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号が知られている。ＬＤＰＣ符号語は、例えばメッセージパッシングアルゴリズムに基づいて復号できる。係る復号処理の計算複雑度は、符号語長（＝ｎシンボル）に対してオーダО（ｎ）（即ち、線形オーダ）と評価できる。他方、ＬＤＰＣ符号語を生成するための符号化処理は、一般的には、データシンボル列（データベクトル）に生成行列を乗算することによって実現される。係る符号化処理の計算複雑度は、符号長（＝ｎシンボル）に対してオーダＯ（ｎ２）と評価できる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】T．Ｒｉｃｈａｒｄｓｏｎ，  ｅｔ．ａｌ．，“Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ”  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍ．，  Ｖｏｌ．４７，  Ｎｏ．２，  ２００１．
【非特許文献２】Ｍａｎａｂｕ  Ｈａｇｉｗａｒａ，  ｅｔ．ａｌ．，  “Ｑｕａｎｔｕｍ  Ｑｕａｓｉ−Ｃｙｃｌｉｃ  ＬＤＰＣ  Ｃｏｄｅｓ，”  Ｐｒｏｃ．  ｉｎ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  （ＩＳＩＴ２００７），  ｐｐ．８０６−８１０，  ２００７．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
実施形態は、符号化処理の計算複雑度を低減させると共に符号化処理を高速化することとを目的とする。
【課題を解決するための手段】
【０００５】
実施形態によれば、符号化装置は、ｑ（Ｎ−Ｊ）個（ｑ，Ｊ，Ｎは自然数であって、Ｎ＞Ｊ）のシンボルを備えるデータシンボル列を入力し、ｑＪ個のシンボルを備えるパリティシンボル列をデータシンボル列に付加してｑＮ個のシンボルを備える符号語を生成する。符号語は、ｑＪ行×ｑＮ列のパリティ検査行列を用いたパリティ検査を満足する。パリティ検査行列においてパリティシンボル列に対応するｑＪ行×ｑＪ列の第１の部分行列は、ｑＬ行×ｑＬ列（Ｌは自然数であって、Ｊ＞Ｌ）の第１の単位行列とｑ（Ｊ−Ｌ）行×ｑＬ列の第１の非零行列とを備えるｑＪ行×ｑＬ列の第２の部分行列を含む。
【図面の簡単な説明】
【０００６】
【図１】第１の実施形態に係る符号化装置を例示するブロック図。
【図２】第２の実施形態に係る符号化装置を例示するブロック図。
【図３】比較例に相当する符号化装置を例示するブロック図。
【図４】準巡回シフト行列及び基本行列の関係の説明図。
【図５】第３の実施形態に係る半導体メモリシステムを例示するブロック図。
【図６】第１の実施形態に係る符号化装置に対応するパリティ検査行列を例示する図。
【図７】第２の実施形態に係る符号化装置に対応するパリティ検査行列を例示する図。
【図８】第２の実施形態に係る符号化装置に対応するパリティ検査行列の基本行列を例示する図。
【発明を実施するための形態】
【０００７】
以下、図面を参照しながら実施形態の説明が述べられる。尚、以降、説明済みの要素と同一または類似の要素には同一または類似の符号が付され、重複する説明は基本的に省略される。
【０００８】
以降の説明において、各実施形態は、ＬＤＰＣ符号方式に適用されることが想定されている。但し、各実施形態は、他の符号方式に適用されてもよい。  
パリティ検査行列の性質は、当該パリティ検査行列に行基本変形及び列基本変形が施されても変化しない。従って、以降の説明において、第１のパリティ検査行列に対して行基本変形及び列基本変形の少なくとも一方を任意に施すことによって導出可能な第２のパリティ検査行列は、第１のパリティ検査行列と同一とみなされる。
【０００９】
また、以降の説明において、簡単化のために、各実施形態はバイナリシンボル（「１」または「０」のシンボル値を取る）に適用されるものとする。従って、シンボル同士の演算において、符号の正負は交換できる。但し、各実施形態が多元シンボルに適用される場合には、シンボル同士の演算において、符号の正負は交換できない。
【００１０】
（第１の実施形態）  
符号化とは、長さｆ＝ｑ（Ｎ−Ｊ）のデータシンボル列ｍに対して、下記数式（１）を満足させる長さｒ＝ｑＪのパリティシンボル列（パリティベクトル）ｐを生成する処理と定義される。尚、以降の説明において、「Ｔ」は、行列またはベクトルの転置を表す記号である。
【数１】
0005665725.tif 000002
【００１１】
数式（１）において、Ｈはパリティ検査行列を表す。一般的なＬＤＰＣ符号化処理は、このパリティ検査行列Ｈに対応する生成行列をデータシンボル列ｍに乗算することによって実現される。この計算複雑度がオーダＯ（ｎ２）であることは前述の通りである。ここで、パリティ検査行列Ｈを利用してパリティシンボル列ｐを生成すれば、計算複雑度を低減させることができる。
【００１２】
具体的には、下記数式（２）に示されるように、パリティ検査行列Ｈを６つの（部分）行列Ａ，Ｂ，Ｔ，Ｃ，Ｄ，Ｅによって構成されるとする。尚、行列Ｔは、下三角行列である。他の行列Ａ，Ｂ，Ｃ，Ｄ，Ｅは、下三角行列である必要はないものの、計算複雑度を低減させる観点から疎行列であることが好ましい。
【数２】
0005665725.tif 000003
【００１３】
行列Ａ，Ｃはデータシンボル列ｍに対応する（即ち、データシンボル列ｍに乗算される）。行列Ｂ，Ｔ，Ｄ，Ｅはパリティシンボル列ｐに対応する（即ち、パリティシンボル列ｐに乗算される）。より詳細には、パリティシンボル列ｐ＝（ｐ１，ｐ２）のように分割すると、行列Ｂ，Ｄは第１の（部分）パリティシンボル列ｐ１（第１の（部分）パリティベクトル）に対応し、行列Ｔ，Ｅは第２の（部分）パリティシンボル列ｐ２（第２の（部分）パリティベクトル）に対応する。第１のパリティシンボル列ｐ１の長さをｒ１＝ｑ（Ｊ−Ｌ）とし、第２のパリティシンボル列ｐ２の長さをｒ２＝ｑＬとすると、ｒ＝ｒ１＋ｒ２が成立する。数式（２）のパリティ検査行列Ｈに、行列Ｅを零行列に置き換えるための行基本変形を施すと、下記数式（３）に示されるパリティ検査行列Ｈ’が導出される。尚、以降の説明において、「−１」は逆行列を表す記号である。
【数３】
0005665725.tif 000004
【００１４】
尚、行列Ｔは下三角行列であるから、逆行列Ｔ−１は存在する。行基本変形を施したとしてもパリティ検査行列Ｈの性質は変化しないから、Ｈ’（ｍ，ｐ）Ｔ＝０が成立する。即ち、下記数式（４），（５）が成立する。
【数４】
0005665725.tif 000005
【００１５】
【数５】
0005665725.tif 000006
【００１６】
数式（５）から、第１のパリティシンボル列ｐ１は、下記数式（６）に示されるように生成できる。  
【数６】
0005665725.tif 000007
【００１７】
また、上記数式（４）から、第２のパリティシンボル列ｐ２は、下記数式（７）に示されるように生成できる。  
【数７】
0005665725.tif 000008
【００１８】
数式（７）において、行列Ａ，Ｂが疎行列であるならば、行列積ＡｍＴ及びＢｐ１Ｔの計算複雑度は低い。更に、Ｔは下三角行列であるから、第２のパリティシンボル列ｐ２の各要素を逐次的に計算すれば、計算複雑度を低減させることができる。従って、パリティシンボル列ｐをこのように生成すれば、符号化処理の一部の計算複雑度を低減させることができる。
【００１９】
他方、係る生成技法は、逐次的な計算を含むので、並列処理が困難である。即ち、係る生成技法は、高速化が困難である。更に、数式（６）における行列φ−１は、概して疎行列でない。故に、係る生成技法によると、第１のパリティシンボル列を生成するための計算複雑度は必ずしも低くない。
【００２０】
行列Ｔを同じサイズの単位行列Ｉに置き換えると、上記数式（６），（７）を下記数式（８），（９）に置き換えることができる。尚、前述の通り、２値シンボルに関して、符号の正負は交換できるので、例えば右辺の「−」符号が「＋」符号に交換されてよい。
【数８】
0005665725.tif 000009
【００２１】
【数９】
0005665725.tif 000010
【００２２】
数式（９）によれば、ベクトルＡｍＴ及びＢｐ１Ｔの加算によって第２のパリティシンボル列ｐ２を生成できるので逐次的な計算が不要である。故に、第２のパリティシンボル列ｐ２をこのように生成すれば、符号化処理を並列処理によって実現すること（即ち、符号化処理を高速化すること）が容易である。
【００２３】
第１の実施形態に係る符号化装置は、上記数式（８）及び数式（９）に従って、第１のパリティシンボル列ｐ１及び第２のパリティシンボル列ｐ２を生成する。この符号化装置は、図６及び下記数式（１０）に示されるパリティ検査行列Ｈに対応する。
【数１０】
0005665725.tif 000011
【００２４】
行列Ａは、ｑＬ行×ｑ（Ｎ−Ｊ）列の行列である。行列Ｂは、ｑＬ行×ｑ（Ｊ−Ｌ）列の行列である。行列Ｃは、ｑ（Ｊ−Ｌ）行×ｑ（Ｎ−Ｊ）列の行列である。行列Ｄは、ｑ（Ｊ−Ｌ）行×ｑ（Ｊ−Ｌ）列の行列である。行列Ｅは、ｑ（Ｊ−Ｌ）行×ｑＬ列の行列である。尚、行列Ａ，Ｂ，Ｃ，Ｄ，Ｅは、計算複雑度を低減させる観点から、疎行列であることが好ましい。
【００２５】
また、行列Ａ，Ｂ，Ｃ，Ｄ，Ｅは、典型的には、（行数×列数）個のブロック行列（ｑ行×ｑ列の行列）を配列することによって形成される。以降の説明において、行列Ａ，Ｂ，Ｃ，Ｄ，Ｅは、（行数×列数）個のブロック行列を配列することによって形成されるものとする。具体的には、行列Ａは、Ｌ×（Ｎ−Ｊ）個のブロック行列を配列することによって形成される。行列Ｂは、Ｌ×（Ｊ−Ｌ）個のブロック行列を配列することによって形成される。行列Ｃは、（Ｊ−Ｌ）×（Ｎ−Ｊ）個のブロック行列を配列することによって形成される。行列Ｄは、（Ｊ−Ｌ）×（Ｊ−Ｌ）個のブロック行列を配列することによって形成される。行列Ｅは、（Ｊ−Ｌ）×Ｌ個のブロック行列を配列することによって形成される。
【００２６】
各ブロック行列は、非零行列（疎行列であることが好ましい）であってもよいし、零行列であってもよい。また、各ブロック行列としての非零行列は、ハードウェア構成の簡素化などの観点から、巡回シフト行列であってもよい。ここで、巡回シフト行列は、各行に１つだけ非零要素が含まれるものが最も疎である。以降の説明において、各ブロック行列は、各行に１つだけ非零要素を含むｑ行×ｑ列の巡回シフト行列またはｑ行×ｑ列の零行列であるとする。即ち、パリティ検査行列Ｈは、Ｊ×Ｎ個のブロック行列を配列することによって形成される準巡回シフト行列であるとする。
【００２７】
準巡回シフト行列は、基本行列を用いて表現することができる。ｑ行×ｑ列の単位行列に相当するブロック行列は、基本行列における「０」の要素に対応する。また、ｑ行×ｑ列の単位行列の各行の非零要素がｉ（＝１，２，・・・，ｑ−１）列だけ右側に巡回シフトした行列に相当するブロック行列は、基本行列における「ｉ」の要素に対応する。更に、ｑ行×ｑ列の零行列に相当するブロック行列は、基本行列における「∞」の要素に対応する。図４は、パリティ検査行列Ｈと、その基本行列ΩＨを例示する。図４の例では、ｑ＝３，Ｊ＝５，Ｎ＝６，Ｌ＝３である。
【００２８】
本実施形態に係る符号化装置１００が、図１に例示されている。符号化装置１００は、行列計算部１０１，１０２，１０３，１０４と、ベクトル加算部１０５とを含む。  
行列計算部１０１，１０２は、上記数式（８）に従って、第１のパリティシンボル列ｐ１を生成する。行列計算部１０３，１０４及びベクトル加算部１０５は、上記数式（９）に従って、第２のパリティシンボル列ｐ２を生成する。
【００２９】
行列計算部１０１は、外部からデータシンボル列ｍを入力する。行列計算部１０１は、データシンボル列ｍＴの左側から行列（−ＥＡ＋Ｃ）を乗算する。即ち、行列計算部１０１は、下記数式（１０）に従って、ベクトル（行列積）ｖ１Ｔを計算する。行列計算部１０１は、ベクトルｖ１Ｔを行列計算部１０２へと出力する。
【数１１】
0005665725.tif 000012
【００３０】
行列計算部１０２は、行列計算部１０１からベクトルｖ１Ｔを入力する。行列計算部１０２は、ベクトルｖ１Ｔの左側から行列Ψ−１を乗算する。即ち、行列計算部１０２は、下記数式（１２）に従って、第１のパリティシンボル列ｐ１Ｔを計算する。行列計算部１０２は、第１のパリティシンボル列ｐ１を外部へと出力すると共に行列計算部１０４へと出力する。
【数１２】
0005665725.tif 000013
【００３１】
行列計算部１０３は、外部からデータシンボル列ｍを入力する。行列計算部１０３は、データシンボル列ｍの左側から行列Ａを乗算する。即ち、行列計算部１０３は、下記数式（１３）に従って、ベクトル（行列積）ｖ２Ｔを計算する。行列計算部１０３は、ベクトルｖ２Ｔをベクトル加算部１０５へと出力する。尚、行列計算部１０３は、行列計算部１０１，１０２，１０４と並行して動作してもよいし、これらよりも前に或いは後に動作してもよい。
【数１３】
0005665725.tif 000014
【００３２】
行列計算部１０４は、行列計算部１０２から第１のパリティシンボル列ｐ１を入力する。行列計算部１０４は、第１のパリティシンボル列ｐ１Ｔの左側から行列Ｂを乗算する。即ち、行列計算部１０４は、下記数式（１４）に従って、ベクトル（行列積）ｖ３Ｔを計算する。行列計算部１０４は、ベクトルｖ３Ｔをベクトル加算部１０５へと出力する。
【数１４】
0005665725.tif 000015
【００３３】
ベクトル加算部１０５は、行列計算部１０３からベクトルｖ２Ｔを入力し、行列計算部１０４からベクトルｖ３Ｔを入力する。ベクトル加算部１０５は、ベクトルｖ２Ｔ及びベクトルｖ３Ｔを加算する。即ち、ベクトル加算部１０５は、下記数式（１５）に従って、第２のパリティシンボル列ｐ２を計算する。ベクトル加算部１０５は、第２のパリティシンボル列ｐ２を外部へと出力する。
【数１５】
0005665725.tif 000016
【００３４】
尚、上記数式（１２）に関して、Ψ−１は、ｑ（Ｊ−Ｌ）行×ｑ（Ｊ−Ｌ）列の行列である。Ψ−１は、概して疎行列でないので、数式（１２）の計算複雑度は必ずしも低くない。従って、ＬＤＰＣ符号の特性を考慮しつつＬが大きくなるように設定することによって、ＬＤＰＣ符号の特性を維持しつつ数式（１２）の計算複雑度を低減させることが好ましい。
【００３５】
Ｌの設定可能な最大値は、以下の技法により導出できる。例えば、基本行列ΩＨのうちパリティシンボル列ｐに対応する部分において、「∞」でない要素（即ち、「０」，「１」，・・・，「ｑ−１」の要素）を多くともＷ（＝Ｊ，Ｊ−１，・・・，１）個持つ列の総数が少なくとも（Ｊ−Ｗ＋１）個であるという条件を満足させるＷが少なくとも１つ存在する。係るＷに関して、Ｌ＝Ｊ−Ｗ＋１に設定できる。即ち、Ｗの最小値をＷｍｉｎとし、Ｌの最大値をＬｍａｘとすれば、Ｌｍａｘ＝Ｊ−Ｗｍｉｎ＋１である。図４の例では、Ｗ＝５，４，３の場合に上記条件が満足する。従って、Ｌｍａｘ＝３（＝５−３＋１）に設定できる。
【００３６】
尚、Ｌを単純に最大化するとＬＤＰＣ符号の特性が劣化するおそれがあるので、前述の通り、ＬＤＰＣ符号の特性を考慮しつつＬが大きくなるように設定することが望ましい。例えば、復号誤り率が低い領域において良好な特性を示すＬＤＰＣ符号を定義するパリティ検査行列は、その各列が持つ非零のブロック行列の最小数が３以上であることが経験的に知られている。従って、例えばストレージシステムに適用されるＬＤＰＣ符号について、Ｗ＝３を採用してＬを設定することが好ましい。即ち、パリティ検査行列Ｈのうちパリティシンボル列に対応するｑＪ行×ｑＪ列の第１の部分行列が、ｑ（Ｊ−２）行×ｑ（Ｊ−２）列の単位行列と、２×（Ｊ−２）個の巡回シフト行列を配列した非零行列とを備えるｑＪ行×ｑ（Ｊ−２）列の第２の部分行列を含むように設計することが好ましい。
【００３７】
符号化装置１００の比較例に相当する符号化装置３００が図３に示されている。符号化装置３００は、行列計算部３０１，３０２，１０３，１０４，３０６と、ベクトル加算部３０５とを含む。
【００３８】
行列計算部３０１，３０２は、上記数式（６）に従って、第１のパリティシンボル列ｐ１を生成する。行列計算部１０３，１０４，３０６及びベクトル加算部３０５は、上記数式（７）に従って、第２のパリティシンボル列ｐ２を生成する。
【００３９】
行列計算部３０１は、外部からデータシンボル列ｍを入力する。行列計算部３０１は、データシンボル列ｍＴの左側から行列（−ＥＴ−１Ａ＋Ｃ）を乗算する。即ち、行列計算部３０１は、下記数式（１６）に従って、ベクトル（行列積）ｖ４Ｔを計算する。行列計算部３０１は、ベクトルｖ４Ｔを行列計算部３０２へと出力する。
【数１６】
0005665725.tif 000017
【００４０】
行列計算部３０２は、行列計算部３０１からベクトルｖ４Ｔを入力する。行列計算部３０２は、ベクトルｖ４Ｔの左側から行列φ−１を乗算する。即ち、行列計算部３０２は、下記数式（１７）に従って、第１のパリティシンボル列ｐ１Ｔを計算する。行列計算部３０２は、第１のパリティシンボル列ｐ１を外部へと出力すると共に行列計算部１０４へと出力する。
【数１７】
0005665725.tif 000018
【００４１】
ベクトル加算部３０５は、行列計算部１０３からベクトルｖ２Ｔを入力し、行列計算部１０４からベクトルｖ３Ｔを入力する。ベクトル加算部３０５は、ベクトルｖ２Ｔ及びベクトルｖ３Ｔを加算する。即ち、ベクトル加算部３０５は、下記数式（１８）に従って、ベクトルｖ５Ｔを計算する。ベクトル加算部３０５は、ベクトルｖ５Ｔを行列計算部３０６へと出力する。
【数１８】
0005665725.tif 000019
【００４２】
行列計算部３０６は、ベクトル加算部３０５からベクトルｖ５Ｔを入力する。行列計算部３０６は、下記数式（１９）に従って、第２のパリティシンボル列ｐ２Ｔを計算する。行列Ｔ−１は下三角行列であるため、逐次的に計算することによって計算複雑度を抑えることができる。行列計算部３０６は、第２のパリティシンボル列ｐ２を外部へと出力する。
【数１９】
0005665725.tif 000020
【００４３】
符号化装置１００及び符号化装置３００を比較すると、符号化装置１００は行列計算部３０６のように逐次的な計算を行う必要がない。従って、符号化装置１００によれば、符号化装置３００に比べて、符号化処理を並列処理によって実現すること（即ち、符号化処理を高速化すること）が容易である。
【００４４】
以上説明したように、第１の実施形態に係る符号化装置は、パリティシンボル列に対応する部分行列にｑＬ行×ｑＬ列の単位行列を含むように設計されたパリティ検査行列を利用して符号語を生成する。従って、この符号化装置によれば、符号化処理の計算複雑度を低減させると共に符号化処理を高速化できる。
【００４５】
（第２の実施形態）  
第２の実施形態に係る符号化装置は、パリティ検査行列の一部において第１の実施形態に係る符号化装置と異なる。具体的には、本実施形態に係る符号化装置は、図７及び下記数式（２０）に示されるパリティ検査行列Ｈに対応する。
【数２０】
0005665725.tif 000021
【００４６】
数式（２０）に示されるパリティ検査行列Ｈは、上記数式（１０）に示されるパリティ検査行列Ｈにおいて部分行列Ｄが単位行列Ｉである場合に相当する。更に、数式（２０）のパリティ検査行列Ｈは、下記数式（２１）を満足する。
【数２１】
0005665725.tif 000022
【００４７】
従って、上記数式（８）は下記数式（２２）に置き換えることができる。  
【数２２】
0005665725.tif 000023
【００４８】
本実施形態に係る符号化装置２００が、図２に例示されている。符号化装置２００は、行列計算部２０１，１０３，１０４と、ベクトル加算部１０５とを含む。
【００４９】
行列計算部２０１は、上記数式（２２）に従って、第１のパリティシンボル列ｐ１を生成する。行列計算部１０３，１０４及びベクトル加算部１０５は、上記数式（９）に従って、第２のパリティシンボル列ｐ２を生成する。
【００５０】
行列計算部２０１は、外部からデータシンボル列ｍを入力する。行列計算部２０１は、データシンボル列ｍＴの左側から行列（−ＥＡ＋Ｃ）を乗算する。即ち、行列計算部２０１は、上記数式（２２）に従って、第１のパリティシンボル列ｐ１を計算する。行列計算部２０１は、第１のパリティシンボル列ｐ１を外部へと出力すると共に行列計算部１０４へと出力する。
【００５１】
行列計算部１０３は、前述のものと同一または類似である。但し、行列計算部１０３は、行列計算部２０１，１０４と並行して動作してもよいし、これらよりも前に或いは後に動作してもよい。
【００５２】
上記数式（２０），（２１）を満足するパリティ検査行列Ｈによれば、Ψ−１＝（−ＥＢ＋Ｄ）−１＝Ｉである。従って、符号化装置２００は、上記数式（１２）に示されるような、行列Ψ−１を用いた行列計算が不要である。行列Ψ−１は、前述の通り、概して疎行列でないから、当該行列Ψ−１を含む行列積の計算複雑度は必ずしも低くない。故に、符号化装置２００は、数式（１２）の計算を省略できるから、符号化処理の計算複雑度を効果的に低減できる。
【００５３】
以下、上記数式（２１）を満足する行列Ｅ，Ｂを設計するための技法を例示する。尚、下記技法に限られず、種々の技法を利用することによって上記数式（２１）を満足する行列Ｅ，Ｂを設計してもよい。例えば、非特許文献２の知見を利用することによって上記数式（２１）を満足する行列Ｅ，Ｂを設計してもよい。
【００５４】
本技法において、ｑＭ行×ｑＭ列の巡回シフト行列Ｓと、ｑＭ行×ｑＭ列の巡回シフト行列Ｑとが用いられる。巡回シフト行列Ｓ，Ｑは、夫々、ｑ行×ｑ列のブロック行列をＭ×Ｍ個配列することによって形成される。ブロック行列の各々は、巡回シフト行列または零行列である。従って、巡回シフト行列Ｓ，Ｑの基本行列ΩＳ，ΩＱは、夫々、下記の数式（２３）によって表される。
【数２３】
0005665725.tif 000024
【００５５】
数式（２３）において、要素ｓ０，ｓ１，・・・，ｓＭ−１，ｕ０，ｕ１，・・・，ｕＭ−１は、「０」，「１」，・・・，「ｑ−１」，「∞」のいずれかである。「∞」の要素は、ｑ行×ｑ列の零行列に対応する。「０」，「１」，・・・，「ｑ−１」の要素は、ｑ行×ｑ列の巡回シフト行列に対応する。要素の値は、対応するｑ行×ｑ列の巡回シフト行列のシフト値を表す。
【００５６】
行列Ｅ，Ｂは、これら巡回シフト行列Ｓ，Ｕを用いて表すことができる。具体的には、行列Ｅ，Ｂの基本行列ΩＥ，ΩＢは、下記数式（２４）によって表すことができる。
【数２４】
0005665725.tif 000025
【００５７】
本技法によれば、行列ＥのサイズはｑＭ行×２ｑＭ列となり、行列Ｂのサイズは２ｑＭ行×ｑＭ列となる。尚、本技法によって設計された行列Ｅ，Ｂが数式（２１）を満足することは、容易に確認できる。また、行列Ｅの各行（または行列Ｂの各列は）独立なので、任意の行（または列）を除去することによって行列ＥまたはＢの行列サイズを任意に変更できる。つまり、行列Ｅのサイズを（ｑＭ―Ｐ）行×２ｑＭ列、行列Ｂのサイズを２ｑＭ行×（ｑＭ―Ｐ）列に変更することができる。ここで、Ｐは０〜ｑＭ−１の整数となるが、行列ＥまたはＢを巡回シフト行列によって構成することを鑑みるとＰはｑの整数倍であることが望ましい。
【００５８】
ｑ＝７，Ｍ＝３の場合に、本技法によって設計される基本行列ΩＥ，ΩＢＴが、下記数式（２５），（２６）に例示される。
【数２５】
0005665725.tif 000026
【００５９】
【数２６】
0005665725.tif 000027
【００６０】
以上説明したように、第２の実施形態に係る符号化装置は、第１の実施形態に係る符号化装置において第１のパリティシンボル列を生成するために必要とされた行列計算の一部を省略できるように設計されたパリティ検査行列を利用する。行列計算の省略部分は、概して疎行列でない行列を含む行列積計算に相当するから、その計算複雑度は必ずしも低くない。従って、この符号化装置によれば、第１の実施形態に係る符号化装置に比べて、符号化処理の計算複雑度を効果的に低減できる。
【００６１】
図８は、第２の実施形態に係る符号化装置に対応するパリティ検査行列の基本行列を例示する。この基本行列は、符号化率２分の１のＬＤＰＣ符号を定義するパリティ検査行列に対応し、このパリティ検査行列に関してｑ＝４９３である。この基本行列によって定義されるＬＤＰＣ符号において、パリティシンボル（パリティビット）１つあたりの生成に要する平均加算回数は６．２回となることから、符号化の計算複雑度が非常に小さく抑えられていることを確認できる。
【００６２】
（第３の実施形態）  
第１乃至第２の実施形態に係る符号化装置は、例えば記憶システム、通信システムなどに組み込まれる。第３の実施形態に係る半導体メモリシステムは、第１乃至第２の実施形態に係る符号化装置を組み込む。尚、詳細な説明は省略されるが、第１乃至第２の実施形態に係る符号化装置は、通信システム、光記録システム、磁気記録システムなど、誤り訂正符号を利用可能なあらゆるシステムに組み込まれてよい。
【００６３】
図５に示されるように、第３の実施形態に係る半導体メモリシステム５００は、ＬＤＰＣ符号化部５０１と、不揮発性半導体メモリ５０２と、ＬＤＰＣ復号部５０３とを含む。尚、半導体メモリシステム５００は、ＬＤＰＣ符号以外の誤り訂正符号を用いてもよい。また、簡単化のために、図５において不揮発性半導体メモリ５０２へのデータの読み書きを行う機能部が省略されている。しかしながら、半導体メモリシステム５００は、係る機能部を必要に応じて備えることができる。
【００６４】
ＬＤＰＣ符号化部５０１は、第１乃至第２の実施形態に係る符号化装置に対応する。ＬＤＰＣ符号化部５０１は、前段の処理部（図示しない）からデータを入力し、当該データを構成するデータシンボル列の各々にＬＤＰＣ符号化処理を行う。即ち、ＬＤＰＣ符号化部５０１は、データシンボル列にパリティシンボル列を付加してＬＤＰＣ符号フレーム（即ち、ＬＤＰＣ符号語）を生成する。ＬＤＰＣ符号化部５０１は、１以上のＬＤＰＣ符号フレームを束ねてページデータを形成する。ＬＤＰＣ符号化部５０１は、ページデータを不揮発性半導体メモリ５０２へと出力する。
【００６５】
前述の通り、ＬＤＰＣ符号化部５０１は、第１乃至第２の実施形態に係る符号化装置に対応する。故に、ＬＤＰＣ符号化部５０１は、上記数式（１０）または数式（２０）に示されるパリティ検査行列Ｈ（或いは、このパリティ検査行列Ｈに行基本変形及び列基本変形の少なくとも一方を任意に施すことによって導出可能な行列）を利用して符号化処理を行う。即ち、ＬＤＰＣ符号化部５０１は、データシンボル列に基づいて第１のパリティシンボル列を生成し、当該第１のパリティシンボル列及びデータシンボル列に基づいて第２のパリティシンボル列を生成する。
【００６６】
不揮発性半導体メモリ５０２への書き込み処理及び不揮発性半導体メモリ５０２からの読み出し処理は、いずれもページデータ単位で行われる。ページデータは、前述の通り、１以上のＬＤＰＣ符号フレームが束ねられたものである。ページデータのサイズは、不揮発性半導体メモリ５０２の構成に依存するが、概ね数ＫＢ程度である。不揮発性半導体メモリ５０２は、複数のメモリセルを備える。具体的には、不揮発性半導体メモリ５０２は、例えば複数のメモリセルがＮＡＮＤ型に接続されたアレイ構造を備えるフラッシュメモリによって実現される。
【００６７】
各メモリセルは、２個以上の閾値電圧が割り当てられ、１ビット以上のデータを記憶できる。各メモリセルが記憶可能なデータ量は、各メモリセルに割り当てられる閾値電圧の総数によって決まる。例えば、１セルあたり２ビットを記憶するフラッシュメモリに関して、各セルには２ビット値のパターン：「００」，「０１」，「１０」，「１１」に応じた４個の閾値が割り当てられる。メモリセルの閾値電圧は、隣接セルとの容量結合などの理由によって、揺らぐことがある。そして、この閾値電圧の揺らぎは、読み出しデータの誤りを引き起こす一因となる。
【００６８】
不揮発性半導体メモリ５０２は、ＬＤＰＣ符号化部５０１によって生成されたページデータを入力する。不揮発性半導体メモリ５０２は、ページデータをメモリセルに記憶する（書き込む）。また、不揮発性半導体メモリ５０２は、メモリセルに記憶されたページデータを読み出し、これを出力する。尚、前述の通り、閾値電圧の揺らぎなどの要因によって、ページデータは誤りを含んで読み出される可能性がある。
【００６９】
ＬＤＰＣ復号部５０３は、不揮発性半導体メモリ５０２によって読み出されたページデータを入力する。ＬＤＰＣ復号部５０３は、ページデータに含まれる１以上のＬＤＰＣ符号フレームの各々にＬＤＰＣ復号処理を行う。ＬＤＰＣ復号処理は、パリティ検査行列を用いた繰り返し復号アルゴリズムによって実現される。繰り返し復号アルゴリズムは、例えば、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム、ｍｉｎ−ｓｕｍアルゴリズムなどである。
【００７０】
ＬＤＰＣ復号部５０３は、パリティ検査において誤りなしと判定した場合（即ち、復号成功の場合）に、一時推定語からパリティシンボル列を除去してデータシンボル列を生成し、これを後段の信号処理部（図示しない）へと出力する。また、ＬＤＰＣ復号部５０３は、復号処理の試行回数が最大繰り返し回数に達した場合（即ち、復号失敗の場合）に、データシンボル列を後段の信号処理部（図示しない）へと出力してもよいし、復号の失敗を後段の信号処理部（図示しない）に通知してもよい。
【００７１】
尚、ＬＤＰＣ復号部５０３は、上記数式（１０）または数式（２０）に示されるパリティ検査行列Ｈ（或いは、このパリティ検査行列Ｈに行基本変形及び列基本変形の少なくとも一方を任意に施すことによって導出可能な行列）を用いる。
【００７２】
以上説明したように、第３の実施形態に係る半導体メモリシステムは、第１乃至第２の実施形態に係る符号化装置を組み込む。従って、この半導体メモリシステムによれば、書き込み処理の一部である符号化処理を高速化できる。
【００７３】
上記各実施形態の処理は、汎用のコンピュータを基本ハードウェアとして用いることで実現可能である。上記各実施形態の処理を実現するプログラムは、コンピュータで読み取り可能な記憶媒体に格納して提供されてもよい。プログラムは、インストール可能な形式のファイルまたは実行可能な形式のファイルとして記憶媒体に記憶される。記憶媒体としては、磁気ディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリなどである。記憶媒体は、プログラムを記憶でき、かつ、コンピュータが読み取り可能であれば、何れであってもよい。また、上記各実施形態の処理を実現するプログラムを、インターネットなどのネットワークに接続されたコンピュータ（サーバ）上に格納し、ネットワーク経由でコンピュータ（クライアント）にダウンロードさせてもよい。
【００７４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７５】
１００，２００，３００・・・符号化装置
１０１，１０２，１０３，１０４，２０１，３０１，３０２，３０６・・・行列計算部
１０５，３０５・・・ベクトル加算部
５００・・・半導体メモリシステム
５０１・・・ＬＤＰＣ符号化部
５０２・・・不揮発性半導体メモリ
５０３・・・ＬＤＰＣ復号部
【図１】
0005665725.tif 000028
【図２】
0005665725.tif 000029
【図３】
0005665725.tif 000030
【図４】
0005665725.tif 000031
【図５】
0005665725.tif 000032
【図６】
0005665725.tif 000033
【図７】
0005665725.tif 000034
【図８】
0005665725.tif 000035