(57)【要約】【課題】  エラー訂正のための付加情報生成方法及びその装置を提供する。【解決手段】  メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、パリティ・チェック・マトリックスHと与えられたメッセージデータSとを用いて付加情報pを演算する段階を含み、前記演算段階では列及び行パーミュテーション方法を用いて前記パリティ・チェック・マトリックスのn-m+1番目の元素からk個の列を上位3角型領域が0である下位3角型マトリックス形態を生成して前記生成されたパリティ・チェック・マトリックスを付加情報演算に用いることによって、LDPCを用いた符号化時に付加情報を効率よく計算しうる。【選択図】      図２
2004208307.tif 000002
【特許請求の範囲】
【請求項１】
メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、
パリティ・チェック・マトリックスHと与えられたメッセージデータSとを用いて付加情報pを演算する段階を含み、
前記演算段階では列及び行パーミュテーション方法を用いて前記パリティ・チェック・マトリックスのn-m+1番目の元素からk個の列を上位3角型領域が0である下位3角型マトリックス形態を生成して前記生成されたパリティ・チェック・マトリックスを付加情報演算に用いることを特徴とする方法。
【請求項２】
前記付加情報を発生させる時、p個のパリティのうちk個のパリティは次の式、
【数１】
2004208307.tif 000006
で表示されるバックワード代替を用いて求める請求項１に記載の方法。
【請求項３】
下位3角型マトリックスの右側上段に0が最大限分布さるべく生成し、n-m個のパリティ数に該当する列のうちから所定数kの列を上位3角型領域が0である下位3角型マトリックスの残り部分に該当するあらゆる1の位置が下位3角型のパリティに該当するマトリックスの対角元素の位置より下に位置することを特徴とする請求項１に記載の方法。
【請求項４】
前記付加情報を発生させる時、p個のパリティのうちp-k個のパリティは下位3角型マトリックス以外の残りのマトリックスを用いてガウス消去法演算方法または次の式、
【数２】
2004208307.tif 000007
で表示された一般的な方法により求めることを特徴とする請求項１に記載の方法。
【請求項５】
メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、
メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを発生する段階と、
列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1番目のマトリックスからk個の列を上位3角型領域が0である下位3角型マトリックスを生成する段階と、
前記下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する段階と、
前記下位3角型マトリックス生成段階で発生した下位3角型マトリックス領域とメッセージデータSを用いてバックワード代替演算を行ってk個のパリティ値を求める段階と、
前記パリティビットn-m個のうち前記バックワード代替演算により求めたk個を除いたパリティ値は前記第2マトリックスを用いて求める段階とを含む方法。
【請求項６】
前記下位3角型マトリックス生成段階ではn-m個のパリティ数に該当する列のうちk個の列を上位3角型領域が0である下位3角型マトリックスの残り部分に該当するあらゆる1の位置が下位3角型のパリティに該当するマトリックスの対角元素の位置より下に位置させることを特徴とする請求項５に記載の方法。
【請求項７】
前記下位3角型マトリックス生成段階では下位3角型マトリックスの右側上段に0が最大限分布さるべく生成することを特徴とする請求項５に記載の方法。
【請求項８】
前記k個のパリティ演算段階で付加情報を発生させる時、p個のパリティのうちk個のパリティは次の式、
【数３】
2004208307.tif 000008
で表示されるバックワード代替を用いて求めることを特徴とする請求項５に記載の方法。
【請求項９】
前記第2マトリックス生成段階で生成された第2マトリックスは所定のHマトリックス形態の縮少された形を有することを特徴とする請求項５に記載の方法。
【請求項１０】
前記k個を除いたパリティ演算段階で付加情報を発生させる時、p個のパリティのうちp-k個のパリティは前記第2マトリックスを用いてガウス消去演算方法または次の式、
【数４】
2004208307.tif 000009
で表示された一般的な方法により求めることを特徴とする請求項９に記載の方法。
【請求項１１】
メッセージワード長mの行及びコードワード長nの列を有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正装置において、
メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを発生するパリティ・チェック・マトリックス発生部と、
列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1番目のマトリックスからk個の列を上位3角型領域が0である下位3角型マトリックスを生成する第1マトリックス発生部と、
前記第1マトリックス発生部により下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する第2マトリックス発生部と、
前記第1マトリックス発生部で発生した下位3角型マトリックス領域と与えられたメッセージデータとを用いてバックワード代替演算を行ってk個のパリティを求めるバックワード代替演算部と、
前記パリティビットn-m個のうち前記バックワード代替演算部で求めたk個を除いたパリティ値は前記第2マトリックスを用いて求める下位パリティ計算部とを含む装置。
【請求項１２】
前記第1マトリックス発生部はn-m個のパリティ数に該当する列のうちk個の列を上位3角型領域が0である下位3角型マトリックスの残り部分に該当するあらゆる1の位置が下位3角型のパリティに該当するマトリックスの対角元素の位置より下に位置させることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記第1マトリックス発生部は下位3角型マトリックスの右側上段に0が最大限分布さるべく生成することを特徴とする請求項１１に記載の装置。
【請求項１４】
前記バックワード代替演算部は前記付加情報を発生させる時、p個のパリティのうちk個のパリティは次の式、
【数５】
2004208307.tif 000010
で表示されるバックワード代替を用いて求めることを特徴とする請求項１１に記載の装置。
【請求項１５】
前記第2マトリックス発生部で生成された第2マトリックスは既存のHマトリックスの縮少された形を有することを特徴とする請求項１１に記載の装置。
【請求項１６】
前記下位パリティ計算部は前記付加情報を発生させる時、p個のパリティのうちp-k個のパリティは前記第2マトリックスを用いてガウス消去演算方法または次の式、
【数６】
2004208307.tif 000011
で表示された一般的な方法により求めることを特徴とする請求項１１に記載の装置。
【請求項１７】
パリティ情報を生成する装置において、
各行及び列毎に同じ1の数を有するパリティ・チェック・マトリックスを生成するパリティ・チェック・マトリックス生成器と、
前記パリティ・チェック・マトリックスの所定の第1部分に基づいて下位3角型マトリックスを生成する第1マトリックス生成器と、
メッセージビット及び前記下位3角型マトリックスに基づいて第1パリティ情報を生成するバックワード代替演算器と、
前記パリティ・チェック・マトリックスの所定の第2部分に基づいてCマトリックスを生成する第2マトリックス生成器と、
前記Cマトリックスに基づいて所定の第2パリティ情報を生成する下位パリティ演算器とを含むことを特徴とする装置。
【請求項１８】
前記第1マトリックス生成器は、前記パリティ・チェック・マトリックスの所定部分に基づいて前記行及び列を交換する行及び列置換方法に基づいて前記下位3角型マトリックスを生成する請求項１７に記載の装置。
【請求項１９】
前記バックワード代替演算器は次の式、
【数７】
2004208307.tif 000012
に基づいて前記所定の第1パリティ情報を生成することを特徴とする請求項１７に記載の装置。
【請求項２０】
前記Cマトリックスは所定のHマトリックスの縮少された形を有することを特徴とする請求項１７に記載の装置。
【請求項２１】
前記パリティ・チェック・マトリックスの所定の第2部分は前記パリティ・チェック・マトリックスにおいて前記パリティ・チェック・マトリックスの前記第1所定の部分を除いた部分であることを特徴とする請求項２０に記載の装置。
【請求項２２】
前記下位パリティ計算器は次の式、
【数８】
2004208307.tif 000013
に基づいて前記所定の第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角型形態の計算は次の式（１）の通りであり、その計算過程が複雑であるということが分かる。
【０００６】
【数９】
2004208307.tif 000003
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角型マトリックス形態を生成して前記生成されたパリティ・チェック・マトリックスを付加情報演算に用いることを特徴とするエラー訂正のための付加情報の生成方法により達成される。
【００１０】
前記付加情報を発生させる時、p個のパリティのうちk個のパリティは
【００１１】
【数１０】
2004208307.tif 000004
のような式で表示されるバックワード代替を用いて求めることが望ましい。
【００１２】
また、前記目的は、メッセージワード長mの行とコードワード長nの列とを有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正方法において、メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを発生する段階と、列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1番目のマトリックスからk個の列を上位3角型領域が0である下位3角型マトリックスを生成する段階と、前記下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する段階と、前記下位3角型マトリックス生成段階で発生した下位3角型マトリックス領域とメッセージデータSを用いてバックワード代替演算を行ってk個のパリティ値を求める段階と、前記パリティビットn-m個のうち前記バックワード代替演算により求めたk個を除いたパリティ値は前記第2マトリックスを用いて求める段階とを含むエラー訂正のための付加情報の生成方法により達成される。
【００１３】
本発明の他の分野によれば、前記目的は、メッセージワード長mの行及びコードワード長nの列を有するマトリックスにおいて列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを用いて付加情報を生成するエラー訂正装置において、メッセージワード長に該当する行及びコードワード長に該当する列を有するマトリックスに列及び行に入る1の数が一定しており、残りの元素は全て０であるパリティ・チェック・マトリックスを発生するパリティ・チェック・マトリックス発生部と、列長n、行長mを有するパリティ・チェック・マトリックスを使用する時、n-m+1番目のマトリックスからk個の列を上位3角型領域が0である下位3角型マトリックスを生成する第1マトリックス発生部と、前記第1マトリックス発生部により下位3角型マトリックスが生成されていない部分は第2マトリックスとして生成する第2マトリックス発生部と、前記第1マトリックス発生部で発生した下位3角型マトリックス領域と与えられたメッセージデータとを用いてバックワード代替演算を行ってk個のパリティを求めるバックワード代替演算部と、前記パリティビットn-m個のうち前記バックワード代替演算部で求めたk個を除いたパリティ値は前記第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である3角型マトリックスに生成される。この際、第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個のパリティビット値が求められる。
【００２０】
【数１１】
2004208307.tif 000005
下位パリティ計算部250はパリティビットn-m個のうちバックワード代替演算部240で求めたk個を除いたパリティ値は第2マトリックス発生部230で生成された第2マトリックスを用いて計算する。すなわち、第2マトリックスに該当するCマトリックスは既存のHマトリックスの縮少された形であるので、ガウス消去演算方法または式（１）で表示された既存の方法により残りのパリティビットの値を計算する。
【００２１】
したがって、本発明は迅速なエンコーディングを必要とする応用分野に効率よく適用されうる。
【産業上の利用可能性】
【００２２】
本発明は光ディスク装置のエラー訂正及び信号検出分野に係り、特にエラー訂正のための付加情報生成方法及びその装置に関し、例えば、迅速なエンコーディングを必要とする応用分野に効率よく適用されうる。
【図面の簡単な説明】
【００２３】
【図１】従来のエラー訂正のための付加情報を生成するためのHマトリックス構造図である。
【図２】本発明によるエラー訂正のための付加情報生成装置の一実施例に係るブロック図である。
【図３】本発明に係るエラー訂正のための付加情報を生成するためのHマトリックス構造図である。
【符号の説明】
【００２４】
２１０  パリティ・チェック・マトリックス発生部
２２０  第1マトリックス発生部
２３０  第2マトリックス発生部
２４０  バックワード代替計算部
２５０  下位パリティ計算部
【図１】
2004208307.tif 000014
【図２】
2004208307.tif 000015
【図３】
2004208307.tif 000016