(57)【特許請求の範囲】
【請求項１】
メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、
パリティ・チェック・マトリックスHと与えられたメッセージデータSとを用いて付加情報pを演算する段階を含み、
前記演算段階では列及び行を交換することにより前記パリティ・チェック・マトリックスのn-m+1番目の列からk列を上位3角型領域が0である下位3角型マトリックスに変換し、
前記生成されたパリティ・チェック・マトリックスを付加情報演算に用いることを特徴とする方法。
【請求項２】
前記付加情報は、ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
【数１】
0003810766.tif 000005
により演算されることを特徴とする請求項１に記載の方法。
【請求項３】
前記下位3角型マトリックスの右側上段に0が最大限分布さるべく生成し、前記上位3角型領域が0である下位3角型マトリックスの残り部分に該当するあらゆる1の位置が下位3角型のパリティに該当するマトリックスの対角要素の位置より下に位置することを特徴とする請求項１に記載の方法。
【請求項４】
前記下位3角型マトリックス以外の残りのマトリックスは、ガウス消去法演算方法、又は、次の式、
【数２】
0003810766.tif 000006
で演算されることを特徴とする請求項１に記載の方法。
【請求項５】
メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、
メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを発生する段階と、
列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1列からk列で、上位3角型領域が0である下位3角型マトリックスを生成する段階と、
前記下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する段階と、
前記下位3角型マトリックス生成段階で発生した下位3角型マトリックス領域とメッセージデータSとを用いてバックワード代替演算を行ってｋ列のパリティ値を求める段階と、
前記k列を除いたパリティ値は前記第2マトリックスを用いて求める段階とを含む方法。
【請求項６】
前記下位3角型マトリックス生成段階では、前記上位3角型領域が0である下位3角型マトリックスの残り部分に該当するあらゆる1の位置が下位3角型のパリティに該当するマトリックスの対角要素の位置より下に位置させることを特徴とする請求項５に記載の方法。
【請求項７】
前記下位3角型マトリックス生成段階では下位3角型マトリックスの右側上段に0が最大限分布さるべく生成することを特徴とする請求項５に記載の方法。
【請求項８】
前記付加情報は、ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
次の式、
【数３】
0003810766.tif 000007
で演算されることを特徴とする請求項５に記載の方法。
【請求項９】
前記第2マトリックス生成段階で生成された第2マトリックスは所定のHマトリックスを縮少された形を有することを特徴とする請求項５に記載の方法。
【請求項１０】
前記下位3角型マトリックス以外の残りのマトリックスは、ガウス消去法演算方法、又は、次の式、
【数４】
0003810766.tif 000008
で演算されることを特徴とする請求項９に記載の方法。
【請求項１１】
メッセージワード長mの行及びコードワード長nの列を有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正装置において、
メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを発生するパリティ・チェック・マトリックス発生部と、
列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1列目からk列を上位3角型領域が0である下位3角型マトリックスを生成する第１マトリックス発生部と、
前記第１マトリックス発生部により下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する第2マトリックス発生部と、
前記第１マトリックス発生部で発生した下位3角型マトリックス領域と与えられたメッセージデータとを用いてバックワード代替演算を行ってｋ列のパリティを求めるバックワード代替演算部と、
前記n-m列のパリティ値は、前記第2マトリックスを用いて求める下位パリティ計算部とを含む装置。
【請求項１２】
前記第１マトリックス発生部は、前記k列を上位3角型領域が0である下位3角型マトリックスの残り部分に該当する全ての１の位置が下位3角型のパリティに該当するマトリックスの対角要素の位置より下に位置させることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記第１マトリックス発生部は下位3角型マトリックスの右側上段に0が最大限分布さるべく生成することを特徴とする請求項１１に記載の装置。
【請求項１４】
前記付加情報は、ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
次の式、
【数５】
0003810766.tif 000009
で演算されることを特徴とする請求項１１に記載の装置。
【請求項１５】
前記第2マトリックス発生部で生成された第2マトリックスは既存のHマトリックスを縮少した形を有することを特徴とする請求項１１に記載の装置。
【請求項１６】
前記下位3角型マトリックス以外の残りのマトリックスは、ガウス消去法演算方法、又は、次の式、
【数６】
0003810766.tif 000010
で演算されることを特徴とする請求項１１に記載の装置。
【請求項１７】
パリティ情報を生成する装置において、
各行及び列毎に同じ1の数を有するパリティ・チェック・マトリックスを生成するパリティ・チェック・マトリックス生成器と、
前記パリティ・チェック・マトリックスの所定の第1部分に基づいて下位3角型マトリックスを生成する第1マトリックス生成器と、
メッセージビット及び前記下位3角型マトリックスに基づいて第1パリティ情報を生成するバックワード代替演算器と、
前記パリティ・チェック・マトリックスの所定の第2部分に基づいてCマトリックスを生成する第2マトリックス生成器と、
前記Cマトリックスに基づいて所定の第2パリティ情報を生成する下位パリティ演算器とを含むことを特徴とする装置。
【請求項１８】
前記第1マトリックス生成器は、前記パリティ・チェック・マトリックスの所定部分に基づいて前記行及び列を交換する行及び列置換方法に基づいて前記下位3角型マトリックスを生成する請求項１７に記載の装置。
【請求項１９】
前記バックワード代替演算器は次の式、ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
【数７】
0003810766.tif 000011
に基づいて前記所定の第1パリティ情報を生成することを特徴とする請求項１７に記載の装置。
【請求項２０】
前記Cマトリックスは所定のHマトリックスの縮少された形を有することを特徴とする請求項１７に記載の装置。
【請求項２１】
前記パリティ・チェック・マトリックスの所定の第2部分は前記パリティ・チェック・マトリックスにおいて前記パリティ・チェック・マトリックスの前記第1所定の部分を除いた部分であることを特徴とする請求項２０に記載の装置。
【請求項２２】
前記下位パリティ計算器は次の式、
【数８】
0003810766.tif 000012
に基づいて前記所定の第2パリティ情報を生成することを特徴とする請求項２１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はエラー訂正及び信号検出分野に係り、特にエラー訂正のための付加情報生成方法及びその装置に関する。
【背景技術】
【０００２】
エラー訂正のために使用するコードのうちLDPC(Low  Density  Parity  check  Code)を用いた符号化方法で付加情報を生成するために行及び列に一定数の1を含むパリティ・チェック・コードを生成し、これを用いて付加情報を発生させる。
【０００３】
すなわち、列及び行に一定数の1を含むマトリックスを生成し、これをパリティ・チェック・マトリックスHとに置き、“Hx=0”になるコードワードを発生させる。この時、xは元のデータと付加情報とが連結されている。このような計算を行うためにパリティ・チェック・マトリックスHをガウス消去法(Gaussian  elimination)を用いてジェネレーターマトリックスGに変換するか、あるいは下位3角型の形に変換させて演算を行う。
【０００４】
ジェネレーターマトリックスGは原マトリックスのスパースネス(sparseness)が喪失されて計算量が多くなる短所があり、下位3角型形態も計算過程が複雑になる短所があった。
【０００５】
すなわち、従来のパリティ・チェック・マトリックスHは図1のようであり、“Hx=0”になるコードワードを発生させるための下位3角型形態の計算は次の式（１）の通りであり、その計算過程が複雑であるということが分かる。
【０００６】
【数９】
0003810766.tif 000002
LDPCの基本概念については非特許文献１に開示されており、H  matrixに対する記述は非特許文献２に開示されている。
【非特許文献１】D.J.MacKay,“Good  error-correction  codes  based  on  very  sparse  matrices,”IEEE  Trans.on  Information  Theory,vol.45,no.2,pp.399-431,1999
【非特許文献２】T.Richardson,R.Urbanke,“Efficient  encoding  of  low  density  parity  check  codes,”IEEE  Trans.on  Information  theory,vol.47,  no.2,pp.  638-656,2001
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、本発明の目的は、エラー訂正のための付加情報の生成方法及びその装置を提供するところにある。
【０００８】
本発明の他の目的は、LDPCの符号化時に付加情報を効率よく計算するエラー訂正のための付加情報の生成方法及びその装置を提供するところにある。
【課題を解決するための手段】
【０００９】
本発明によって前記目的は、メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、
パリティ・チェック・マトリックスHと与えられたメッセージデータSとを用いて付加情報pを演算する段階を含み、
前記演算段階では列及び行を交換することにより前記パリティ・チェック・マトリックスのn-m+1番目の列からk列を上位3角型領域が0である下位3角型マトリックスに変換し、
前記生成されたパリティ・チェック・マトリックスを付加情報演算に用いることを特徴とする方法により達成される。
【００１０】
前記付加情報は、ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
【００１１】
【数９】
0003810766.tif 000003
により演算されることが望ましい。
【００１２】
また、前記目的は、メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを発生する段階と、列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1列からk列で、上位3角型領域が0である下位3角型マトリックスを生成する段階と、前記下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する段階と、前記下位3角型マトリックス生成段階で発生した下位3角型マトリックス領域とメッセージデータSとを用いてバックワード代替演算を行ってｋ列のパリティ値を求める段階と、前記k列を除いたパリティ値は前記第2マトリックスを用いて求める段階とを含む方法により達成される。
【００１３】
本発明の他の分野によれば、前記目的は、メッセージワード長mの行及びコードワード長nの列を有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正装置において、メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの要素は全て０であるパリティ・チェック・マトリックスを発生するパリティ・チェック・マトリックス発生部と、列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1列目からk列を上位3角型領域が0である下位3角型マトリックスを生成する第１マトリックス発生部と、前記第１マトリックス発生部により下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する第2マトリックス発生部と、
前記第１マトリックス発生部で発生した下位3角型マトリックス領域と与えられたメッセージデータとを用いてバックワード代替演算を行ってｋ列のパリティを求めるバックワード代替演算部と、前記n-m列のパリティ値は、前記第2マトリックスを用いて求める下位パリティ計算部とを含む装置により達成される。
【発明の効果】
【００１４】
本発明は、LDPCのエンコーダ具現のためのパリティ・チェック・マトリックスを用いて付加情報を発生させる方法であって、演算量のレベルをマトリックスの列長に該当するn個のオーダーに近い値に作れるようになって計算量が減りかつ付加情報を効率よく計算しうる。
【発明を実施するための最良の形態】
【００１５】
以下、添付された図面を参照して本発明の望ましい実施例を説明する。
【００１６】
図2は、本発明によるエラー訂正のための付加情報生成装置の一実施例に係るブロック図であって、パリティ・チェック・マトリックス発生部210、第1マトリックス発生部220、第2マトリックス発生部230、バックワード代替計算部240、下位パリティ計算部250よりなっており、これに対する動作を図3と結び付けて説明する。
【００１７】
図2を参照すれば、パリティ・チェック・マトリックス発生部210はメッセージワード長に該当する行とコードワード長に該当する列とを有するマトリックスに列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを発生させる。第1マトリックス発生部220は図3に示されたTマトリックスに対応する下位三角マトリックスを生成する。このようなTマトリックスは、列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、列と行とを全て交換する列及び行パーミュテーション方法を用いてn-m+1番目の列からk列を上位3角型領域が0となるように列と行とを交換することにより３角型マトリックスが生成される。この際、第1マトリックス発生部220は下位3角型マトリックスの右側上段に0が最大限分布さるべく生成し、n-m個のパリティ数に該当する列のうちk個の下位3角型マトリックスの残り部分のあらゆる1の位置を下位3角型のパリティに該当するマトリックスの対角元素の位置より下に位置させる。
【００１８】
第2マトリックス発生部230は第1マトリックス発生部220により3角型マトリックスが生成されていない部分は第2マトリックスに生成するが、図3に示されたCマトリックスに該当する。第2マトリックス発生部230で発生したCマトリックスは図1に示された既存のHマトリックスの縮少された形態を有する。
【００１９】
バックワード代替演算部240は第1マトリックス発生部220で発生した下位3角型マトリックス領域とメッセージビットSとを用いてバックワード代替演算を行って付加情報pを演算する。この演算は次の式（２）のように表現でき、全体パリティビットのうちk個のパリティビット値が求められる。
【００２０】
ｐlをｌ列の付加情報、Ｈl,jをＨマトリクスのｌ行ｊ列の要素、Ｓjをメッセージデータのjビット目の値を示したとき、
【数１０】
0003810766.tif 000004

下位パリティ計算部250はk列を除いたパリティ値は第2マトリックス発生部230で生成された第2マトリックスを用いて計算する。すなわち、第2マトリックスに該当するCマトリックスは既存のHマトリックスの縮少された形であるので、ガウス消去演算方法または式（１）で表示された既存の方法により残りのパリティビットの値を計算する。
【００２１】
したがって、本発明は迅速なエンコーディングを必要とする応用分野に効率よく適用されうる。
【産業上の利用可能性】
【００２２】
本発明は光ディスク装置のエラー訂正及び信号検出分野に係り、特にエラー訂正のための付加情報生成方法及びその装置に関し、例えば、迅速なエンコーディングを必要とする応用分野に効率よく適用されうる。
【図面の簡単な説明】
【００２３】
【図１】従来のエラー訂正のための付加情報を生成するためのHマトリックス構造図である。
【図２】本発明によるエラー訂正のための付加情報生成装置の一実施例に係るブロック図である。
【図３】本発明に係るエラー訂正のための付加情報を生成するためのHマトリックス構造図である。
【符号の説明】
【００２４】
２１０  パリティ・チェック・マトリックス発生部
２２０  第1マトリックス発生部
２３０  第2マトリックス発生部
２４０  バックワード代替計算部
２５０  下位パリティ計算部
【図１】
0003810766.tif 000013
【図２】
0003810766.tif 000014
【図３】
0003810766.tif 000015