(57)【要約】【課題】  デコーディングによるエンコーディングを可能にするパリティ検査行列、パリティ検査行列の生成方法、エンコーディング方法及びエラー訂正装置を提供する。【解決手段】  Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を定義するステップと、記部分行列Ｈｐとして、あらゆる行ベクトルが線形独立であり、あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、部分集合Ａ１は、集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、部分集合Ａｉ（２≦ｉ≦ｋ）は、部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列を生成するステップとを含む。【選択図】      図６
2007166605.tif 000002
【特許請求の範囲】
【請求項１】
エラー訂正及びデータのデコーディングによるエンコーディングのためのパリティ検査行列において、
前記パリティ検査行列は、Ｍ×Ｎ行列Ｈ＝［Ｈｍ｜Ｈｐ］であり、
前記部分行列Ｈｍは、Ｍ×（Ｎ−Ｍ）行列であり、
前記部分行列Ｈｐは、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは互いに交集合を持たず、空集合ではない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合であるＭ×Ｍ行列であることを特徴とするパリティ検査行列。
【請求項２】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項１に記載のパリティ検査行列。
【請求項３】
前記パリティ検査行列は、Ｍ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数であり、前記Ｈｐは、少なくともＢ個のウエートが１である列ベクトルを含むことを特徴とする請求項１に記載のパリティ検査行列。
【請求項４】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項３に記載のパリティ検査行列。
【請求項５】
エラー訂正及びデータのデコーディングによるエンコーディングのためのパリティ検査行列を生成する方法において、
Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を定義するステップと、
前記部分行列Ｈｐとして、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列を生成するステップとを含むことを特徴とするパリティ検査行列の生成方法。
【請求項６】
前記パリティ検査行列から４サイクルを除去するステップをさらに含むことを特徴とする請求項５に記載のパリティ検査行列の生成方法。
【請求項７】
前記Ｍ×Ｎパリティ検査行列を定義するステップは、前記パリティ検査行列がＭ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数になるように定義するステップを含み、
前記Ｍ×Ｍ部分行列Ｈｐを生成するステップは、前記Ｈｐ内に少なくともＢ個のウエートが１である列ベクトルを生成するステップを含むことを特徴とする請求項５に記載のパリティ検査行列の生成方法。
【請求項８】
前記パリティ検査行列から４サイクルを除去するステップをさらに含むことを特徴とする請求項７に記載のパリティ検査行列の生成方法。
【請求項９】
Ｎ−Ｍ次元のデータメッセージベクトルをエンコーディングする方法において、
Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を定義し、前記部分行列Ｈｐとして、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列を生成することによって、パリティ検査行列を生成するステップと、
前記生成されたパリティ検査行列を利用したデコーディングにより、前記メッセージベクトルにＭ次元のパリティベクトルを付加することで、前記メッセージベクトルをエンコーディングするステップとを含むことを特徴とするエンコーディング方法。
【請求項１０】
前記パリティ検査行列を生成するステップは、
前記生成されたパリティ検査行列から４サイクルを除去するステップを含むことを特徴とする請求項９に記載のエンコーディング方法。
【請求項１１】
前記Ｍ×Ｎパリティ検査行列を生成するステップは、
前記パリティ検査行列がＭ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数になるように定義するステップと、
前記Ｈｐ内に少なくともＢ個のウエートが１である列ベクトルを生成するステップとを含むことを特徴とする請求項９に記載のエンコーディング方法。
【請求項１２】
前記Ｍ×Ｎパリティ検査行列を生成するステップは、前記パリティ検査行列から４サイクルを除去するステップを含むことを特徴とする請求項１１に記載のエンコーディング方法。
【請求項１３】
前記メッセージベクトルをエンコーディングするステップは、前記パリティベクトルにイレイジャー表示を行うステップを含み、
前記エンコーディングは、イレイジャー訂正により行われ、前記デコーディングは、ソフトイタラティブデコーディング方法であることを特徴とする請求項９に記載のエンコーディング方法。
【請求項１４】
前記パリティベクトルにイレイジャー表示を行うステップは、デコーディング時にパリティベクトル全体を０に設定するステップを含むことを特徴とする請求項１３に記載のエンコーディング方法。
【請求項１５】
前記メッセージベクトルをエンコーディングするステップは、
前記メッセージベクトルの０を−１に置換するステップをさらに含むことを特徴とする請求項１３に記載のエンコーディング方法。
【請求項１６】
Ｎ−Ｍ次元のメッセージベクトルをエンコーディングする方法において、
Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を定義し、前記部分行列Ｈｐとして、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列を生成することによって、パリティ検査行列を生成するステップと、
パリティベクトル全体を０に設定し、前記メッセージベクトルの０を−１に置換し、前記生成されたパリティ検査行列を利用したソフトイタラティブデコーディングにより、Ｍ次元の前記パリティベクトルを前記メッセージベクトルに付加することで、前記メッセージベクトルをエンコーディングするステップとを含むことを特徴とするエンコーディング方法。
【請求項１７】
前記Ｍ×Ｎパリティ検査行列を生成するステップは、前記パリティ検査行列から４サイクルを除去するステップを含むことを特徴とする請求項１６に記載のエンコーディング方法。
【請求項１８】
前記Ｍ×Ｎパリティ検査行列を生成するステップは、
前記パリティ検査行列がＭ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数になるように定義するステップと、
前記Ｈｐ内に少なくともＢ個のウエートが１である列ベクトルを生成するステップと、を含むことを特徴とする請求項１６に記載のエンコーディング方法。
【請求項１９】
前記Ｍ×Ｎパリティ検査行列を生成するステップは、前記パリティ検査行列から４サイクルを除去するステップを含むことを特徴とする請求項１８に記載のエンコーディング方法。
【請求項２０】
エラー訂正装置において、
Ｍ×（Ｎ−Ｍ）部分行列Ｈｍと、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合であるＭ×Ｍ部分行列Ｈｐを含む、Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を生成する行列生成部と、
前記生成されたパリティ検査行列を利用したデコーディングにより、Ｎ−Ｍ次元のメッセージベクトルに付加されるＭ次元のパリティベクトルを獲得して前記メッセージベクトルをエンコーディングし、受信されたコードワードベクトルのデコーディングを行うデコーダとを備えることを特徴とするエラー訂正装置。
【請求項２１】
前記メッセージベクトルの０を−１に置換して前記デコーダに出力するデコーダ入力処理部をさらに備え、前記パリティベクトルは全体が０に設定され、
前記デコーダは、ソフトイタラティブデコーダであることを特徴とする請求項２０に記載のエラー訂正装置。
【請求項２２】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項２０に記載のエラー訂正装置。
【請求項２３】
前記パリティ検査行列は、Ｍ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数であり、前記Ｈｐは、少なくともＢ個のウエートが１である列ベクトルを含むことを特徴とする請求項２０に記載のエラー訂正装置。
【請求項２４】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項２３に記載のエラー訂正装置。
【請求項２５】
エラー訂正装置において、
Ｍ×（Ｎ−Ｍ）部分行列Ｈｍと、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合であるＭ×Ｍ部分行列Ｈｐを含む、Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を生成する行列生成部と、
パリティベクトル全体を０に設定し、前記メッセージベクトルの０を−１に置換し、前記生成されたパリティ検査行列を利用したソフトイタラティブデコーディングにより、Ｍ次元の前記パリティベクトルを前記メッセージベクトルに付加することで、前記メッセージベクトルをエンコーディングするデコーダとを備えることを特徴とするエラー訂正装置。
【請求項２６】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項２５に記載のエラー訂正装置。
【請求項２７】
前記パリティ検査行列は、Ｍ＝８＊Ｂであるブロック構造を持ち、前記Ｂは、１以上の整数であり、前記Ｈｐは、少なくともＢ個のウエートが１である列ベクトルを含むことを特徴とする請求項２５に記載のエラー訂正装置。
【請求項２８】
前記パリティ検査行列は、４サイクルを含まないことを特徴とする請求項２７に記載のエラー訂正装置。
【請求項２９】
請求項５に記載の方法を行うプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項３０】
請求項９に記載の方法を行うプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項３１】
請求項１６に記載の方法を行うプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エラー訂正のためのパリティ検査行列、パリティ検査行列の生成方法、エンコーディング方法及びエラー訂正装置に関する。
【背景技術】
【０００２】
情報記録媒体の高密度化、データ伝送の高密度化によって有／無線通信、光通信などを含むデータ伝送のための通信チャンネル上で、単位時間当りデータ再生または伝送量が多くなるにつれて、チャンネルの状況が相対的に悪化して、既存より多くのエラーを含む。例えば、光情報記録媒体の場合、高密度によって物理的な単位長にさらに多くのデータが保存されて、ホコリ、スクラッチ、指紋などによって、さらに多くのエラーを内包する。また、有無線通信の場合、データの高画質化によって単位時間当り伝送されるデータ量が多くなって、同じ時間の通信障害に対して、受信されたデータが持つエラーの量が相対的に多くなっている。これにより、高密度化による通信チャンネル上に高いエラー訂正能力を持つエラー訂正方法またはエラー訂正コードが要求されている。
【０００３】
これによるエラー訂正コード及び方法で、既存のＲＳ（リード−ソロモン）コードのように入力されたビットのハード値（０または１）でエラー訂正を行う方式ではない、ターボコードデコーディング、ＬＤＰＣ（ロー  デンシティ  パリティ  チェック）デコーディングのように入力されたビットのソフト値（０．２、０．９など）を参照して、反復訂正を通じてエラー訂正を行う“ソフトイタラティブデコーディング”方式が注目されている。前記入力されるビットのソフト値というのは、一般的に入力されたハード値の確率として表すことができる。
【０００４】
一般的に、ＲＳコードやＬＤＰＣコードのような線形ブロックコードは、与えられたコードワードベクトルＣに対してＨＣＴ＝０を満足するパリティ検査行列（パリティ  チェック  マトリックス）Ｈが与えられる。また、前記与えられたＨからｍ＊Ｇ＝Ｃを満足する生成行列（ジェネレータ  マトリックス）Ｇが存在する。ここで、ｍは、メッセージベクトル、Ｃはコードワードベクトルである。すなわち、線形ブロックコードでは、生成行列Ｇを利用して、メッセージベクトルをコードワードベクトルにしてエンコーディングを行い、パリティ検査行列Ｈを利用して受信されたコードワードベクトルをデコーディングして、メッセージベクトルを得る。したがって、これを、光情報記録媒体や有／無線通信、コンピュータシステムのような実際システムに適用するためには、一般的にエンコーディングのためのハードウェアとデコーディングのためのハードウェアとを別途に構成せねばならない。
【０００５】
特許文献１は、前記のようなエンコーディング／デコーディングのためのハードウェアの負担を低減するための方法として、一つのＲＳデコーダによりＲＳエンコーディングとＲＳデコーディングとを同時に行える方法を提案した。ここで、ＲＳデコーダだけでエンコーディング可能な理由は、次の通りである。ＲＳデコーダは、パリティ検査行列Ｈを利用して、受信されたコードワードを、代数的方法によりそのエラー位置とその値を探して訂正を行うが、エンコーディング時に、エラーの位置をあらかじめ知っていて訂正を行うイレイジャー（Ｅｒａｓｕｒｅ）訂正方法を利用する。メッセージベクトルに付加情報、すなわち、パリティがついてコードワードベクトルになるが、この時、パリティが添加される部分をあらかじめエラーと見なし、メッセージベクトルを確定してＲＳデコーダに入力すれば、ＲＳデコーダは、受信されたコードワードに対するイレイジャー訂正を行って、メッセージベクトルに対する実際パリティベクトルを生成することによってエンコーディングを行う。しかし、このような方法は、ターボコードやＬＤＰＣコードのように、反復（Ｉｔｅｒａｔｉｏｎ）によるデコーディングを行うシステムに適用できないという問題がある。
【特許文献１】米国特許第５，７７１，２４４号明細書
【特許文献２】日本特許公開第２００５−０５１７５６号公報
【特許文献３】日本特許公開第平８−２７５１７５号公報
【特許文献４】日本特許公開第昭６３−８６９２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、前記のような問題を解決して、デコーダによるエンコーディングを行えるパリティ検査行列、パリティ検査行列の生成方法、エンコーディング方法及びエラー訂正装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記のような課題を解決するための本発明の一特徴は、エラー訂正及びデータのデコーディングによるエンコーディングのためのパリティ検査行列において、前記パリティ検査行列は、Ｍ×Ｎ行列Ｈ＝［Ｈｍ｜Ｈｐ］であり、前記部分行列Ｈｍは、Ｍ×（Ｎ−Ｍ）行列であり、前記部分行列Ｈｐは、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは互いに交集合を持たず、空集合ではない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合であるＭ×Ｍ行列である。
【０００８】
望ましくは、前記パリティ検査行列は、４サイクルを含まない。
【０００９】
本発明の他の特徴は、エラー訂正のためのパリティ検査行列を生成する方法において、Ｍ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］を定義するステップと、前記部分行列Ｈｐとして、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは、互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列を生成するステップと、を含むことである。
【００１０】
本発明のさらに他の特徴は、Ｎ−Ｍ次元のデータメッセージベクトルをエンコーディングする方法において、Ｍ×Ｎパリティ検査行列を生成するステップと、前記生成されたパリティ検査行列を利用したデコーディングにより、前記メッセージベクトルに付加されるＭ次元のパリティベクトルを獲得するステップと、を含むことである。
【００１１】
望ましくは、前記パリティベクトルを獲得するステップは、前記メッセージベクトルと、全体が０に設定されたパリティベクトルとを入力としてソフトイタラティブデコーディングを行うことによって、前記パリティベクトルをエラー訂正するステップを含む。
【００１２】
本発明のさらに他の特徴は、エラー訂正装置において、Ｍ×Ｎパリティ検査行列を生成する行列生成部と、前記生成されたパリティ検査行列を利用したデコーディングにより、Ｎ−Ｍ次元のメッセージベクトルに付加されるＭ次元のパリティベクトルを獲得して前記メッセージベクトルをエンコーディングし、受信されたコードワードベクトルのデコーディングを行うデコーダとを備えることである。
【００１３】
望ましくは、前記エラー訂正装置は、前記エンコーディング実行時、前記メッセージベクトルの０を−１に置換した情報と、全体が０に設定されたパリティベクトルで構成されたコードワードベクトルとを前記デコーダに出力するデコーダ入力処理部をさらに備え、前記デコーダは、ソフトイタラティブデコーダである。
【発明の効果】
【００１４】
本発明の構成によれば、デコーディングによるエンコーディングができるので、システム具現時にパリティ検査行列のためのデコーダだけでデータのエンコーディングとデコーディングとをいずれも行える。
【発明を実施するための最良の形態】
【００１５】
以下、添付された図面を参照して本発明の望ましい実施形態を説明する。
【００１６】
エンコーディングは、システマチックエンコーディングと非システマチックエンコーディングとに大別される。システマチックエンコーディングは、メッセージベクトルを元来の値そのまま維持し、パリティベクトルのみを付加してコードワードを生成するエンコーディング方法をいう。すなわち、システマチックエンコーディング方法によりエンコーディングされたコードワードのメッセージベクトルに該当する部分は、元来メッセージベクトルと同じ値を持つ。一方、非システマチックエンコーディング方法によれば、メッセージベクトルの値がエンコーディングにより他の値に変更される。
【００１７】
本発明によって、デコーディングによるシステマチックエンコーディングを可能にするパリティ検査行列の構造は、次のように定義される。
【００１８】
本発明によるパリティ検査行列は、ＧＦ（２）上のベクトル空間でＭ個の線形独立した行（ｒｏｗ）を持つＭ×Ｎ行列Ｈで定義され、ＨのＭ×Ｍ部分行列（ｓｕｂ−ｍａｔｒｉｘ）Ｈｐは、次のような構造を持つと定義される。
【００１９】
定義１：ＨｐのＭ個の行ベクトルの集合をＡとする。
【００２０】
定義２：与えられたベクトルの各成分のうち、０でない成分の数をウエート（ｗｅｉｇｈｔ）としよう。例えば、ベクトルＶ＝（１，０，０，０，１，０，０）のウエートは２である。
【００２１】
定義３：集合Ａの元素のうち、ウエートが１である元素の集合をＡ１とする。
【００２２】
１．集合Ａの部分集合Ａ１は空集合でない。
【００２３】
２．集合Ａと集合Ａ１との差集合１＝Ａ−Ａ１が空集合でなければ、集合Ｂ１は、次のようなベクトルで構成されたＢ１の部分集合Ａ２を含み、Ａ２は空集合ではない。集合Ｂ１の元素であるベクトルｖに対して、ｖとＡ１のベクトルとの線形結合により、ウエートが１であるベクトルを作ることができるならば、前記ベクトルｖはＡ２の元素である。
【００２４】
３．差集合Ｂ２＝Ａ−（Ａ１∪Ａ２）が空集合でなければ、集合Ｂ２は、次のようなベクトルで構成されたＢ２の部分集合Ａ３を含み、Ａ３は空集合でない。集合Ｂ２の一元素であるベクトルｖに対して、ｖとＡ１∪Ａ２のベクトルとの線形結合によりウエートが１であるベクトルを作ることができるならば、前記ベクトルｖはＡ３の元素である。
【００２５】
４．前記２と３のような方式により、差集合Ｂｋ＝Ａ−（Ａ１∪Ａ２∪…∪Ａｋ）が空集合になる、すなわち、Ａ＝Ａ１∪Ａ２∪…∪Ａｋになるｋが存在し、ｋは、１より大きいか、または同じであり、Ｍより小さいか、または同じである。
【００２６】
５．ＨｐのＭ個の行ベクトルは線形独立である。
【００２７】
要約すれば、本発明によるパリティ検査行列は、あらゆる行ベクトルが線形独立であり、前記あらゆる行ベクトルの集合Ａは互いに交集合を持たず、空集合でない部分集合Ａ１，Ａ２，…，Ａｋ（１≦ｋ≦Ｍ）の合集合であり、前記部分集合Ａ１は、前記集合Ａの元素のうち、ウエートが１である行ベクトルの集合であり、前記部分集合Ａｉ（２≦ｉ≦ｋ）は、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれない行ベクトルのうち、前記部分集合Ａ１，…，Ａｉ−１の合集合に含まれた行ベクトルとの線形結合で、ウエートが１である行ベクトルを派生できる行ベクトルの集合になるＭ×Ｍ行列Ｈｐを含む、Ｍ×Ｎ行列Ｈ＝［Ｈｍ｜Ｈｐ］構造で定義される。また、パリティ検査行列が４サイクルを含まないことが望ましい。４サイクルが含まれれば、パリティ検査行列の性能が顕著に落ちるためである。
【００２８】
図１は、本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第１実施形態を図示したものである。図１を参照するに、Ｍは８であり、ｉ番目行ベクトルをＲｉ（ｉ＝１，２，…，８）とした。この実施形態で、ｋは８であり、それぞれのｉに対して、Ａｉは、一つの行ベクトルのみを持って｛Ｒｉ｝と同一である。
【００２９】
図２は、本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第２実施形態を図示したものである。図２を参照するに、Ｍは８であり、ｉ番目行ベクトルをＲｉ（ｉ＝１，２，…，８）とした。この実施形態で、ｋは４であり、Ａ１＝｛Ｒ１，Ｒ５｝、Ａ２＝｛Ｒ２，Ｒ６｝、Ａ３＝｛Ｒ３，Ｒ７｝、Ａ４＝｛Ｒ４，Ｒ８｝である。
【００３０】
図３Ａは、本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第３実施形態を図示したものである。図３Ｂは、本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第４実施形態を図示したものである。
【００３１】
図３Ａ及び図３Ｂを参照するに、Ｍは８＊Ｂであり、ここで、Ｂは、１以上の整数である。すなわち、図３Ａ及び図３Ｂは、図１及び図２をそれぞれ拡張したものであり、パリティ検査行列Ｈがブロック構造からなる場合において、本発明による定義を満足するＨの部分行列Ｈｐを表す図である。ＢＲｉ（ｉ＝１，２，…，８）は、Ｂ×８＊Ｂ部分行列をいう。例えば、ＢＲ１は、Ｈの最初のＢ個の行ベクトルで構成されたＢ×８＊Ｂ行列（Ｐ
０ ０ ０ ０ ０ ０ ０）である。Ｐ（３０１，３５１）は、Ｂ×Ｂ単位行列Ｉであるか、Ｉを行移動して作ったＩの順列行列（ｐｅｒｍｕｔａｔｉｏｎ  ｍａｔｒｉｘ）である。Ｉの行移動により作られるＰは、全体パリティ検査行列Ｈのガース（ｇｉｒｔｈ、行列Ｈ内で最も短いサイクルの長さ）が６以上になるように決定することが望ましい。すなわち、４サイクルを持たないようにその移動（ｓｈｉｆｔ）値が決定されることが望ましい。また、図３Ａ及び図３Ｂで０は、Ｂ×Ｂゼロ行列をいう。
【００３２】
図１及び図２に図示されたように、本発明によるＨは、少なくとも一つ以上のウエートが１である列ベクトルを持つ。パリティ検査行列の特性上ウエートが１である列（ｃｏｌｕｍｎ）を持つようになれば、パリティ検査行列の性能が多少低下する。図３Ａ及び図３Ｂのように、Ｂ×Ｂ行列で構成されたブロック構造で本発明によるＨＰ構造を設計する場合、ウエートが１である列が少なくともＢ個含まれる。ウエートが１である列の数を最小化することが望ましいので、このために、Ｐａ（３０２，３５２）は、列のウエートが１または２であるＢ×Ｂブロックで構成されることが望ましく、Ｐｂ（３０３，３５３）は、図１または図２のように、本発明による性質を満足するＢ×Ｂ行列で構成されることが望ましい。
【００３３】
ＰｂがＩの順列行列である場合、図３Ａで、ｋ＝８であり、ｉ＝１，２，…，８に対して、Ａｉ＝｛ｖ｜ｖは、ＢＲｉの行ベクトル｝であり、ウエートが１である列ベクトルがＢ個存在する。図３Ｂの場合、ｋ＝４であり、Ａ１＝｛ｖ｜ｖは、ＢＲ１またはＢＲ５の行ベクトル｝、Ａ２＝｛ｖ｜ｖは、ＢＲ２またはＢＲ６の行ベクトル｝、Ａ３＝｛ｖ｜ｖは、ＢＲ３またはＢＲ７の行ベクトル｝、Ａ４＝｛ｖ｜ｖは、ＢＲ４またはＢＲ８の行ベクトル｝であり、ウエートが１である列ベクトルが２＊Ｂ個存在する。
【００３４】
一方、Ｐｂが図１のような構造を持つ場合、図３Ａで、ｋ＝７＋Ｂであり、ｉ＝１，２，…，７に対してＡｉ＝｛ｖ｜ｖは、ＢＲｉの行ベクトル｝であり、ｉ＝１，２，…，Ｂに対してＡｉ＋７＝｛ＢＲ８のｉ番目の行ベクトル｝であり、ウエートが１である列ベクトルが１個存在する。図３Ｂの場合、ｋ＝３＋Ｂであり、Ａ１＝｛ｖ｜ｖは、ＢＲ１またはＢＲ５の行ベクトル｝、Ａ２＝｛ｖ｜ｖは、ＢＲ２またはＢＲ６の行ベクトル｝、Ａ３＝｛ｖ｜ｖは、ＢＲ３またはＢＲ７の行ベクトル｝、ｉ＝１，２，…，Ｂに対して、Ａ３＋ｉ＝｛ＢＲ４またはＢＲ８のｉ番目行ベクトル｝であり、ウエートが１である列ベクトルが２個存在する。
【００３５】
エンコーディング時間はｋに比例し、ウエートが１である列ベクトルの数が大きいほど、パリティ検査行列のエラー訂正能力は落ちる。前記のように、ブロック構造下でｋとウエートが１である列ベクトルの数とを調節することができるので、エンコーディング時間とＨの性能とを考慮して適切な構造を選択することが望ましい。
【００３６】
図４Ａは、図１の部分行列Ｈｐをパリティ検査ノード４０１とビットノード４０２との連結状態を表すグラフに変換したものであり、図４Ｂは、図２の部分行列Ｈｐを、パリティ検査ノード４５１とビットノード４５２との連結状態を表すグラフに変換したものである。
【００３７】
図５は、本発明によるデコーディングによるエンコーディング方法を図示したフローチャートである。図５を参照するに、まず前述した定義を満足するパリティ検査行列を生成する（Ｓ５０２）。その後、生成されたパリティ検査行列を利用したデコーディングにより、メッセージベクトルをコードワードベクトルにエンコーディングする。デコーディング方法としては、ソフトイタラティブデコーディングを使用でき、この場合、パリティ部分全体を０に設定してソフトイタラティブデコーディングを行い、デコーディング実行結果でパリティ部分の値を求めることができるので、デコーディングによるエンコーディングが可能である（Ｓ５０４）。しかし、後述するように、ソフトイタラティブデコーディング以外の方式でもデコーディングによるエンコーディングが可能である。次いで、本発明によるデコーディングによるエンコーディング方法を詳細に説明する。
【００３８】
本発明によって、一つのデコーダでエンコーディングを行うためには、エンコーディングであるかデコーディングであるかを判断できる情報を受信した後、エンコーディングと見なされれば、代数的方法やソフトイタラティブデコーディングによりパリティベクトルＰ（ｘ）を求める。
【００３９】
まず、パリティ検査行列がＨ＝［Ｈｍ｜Ｈｐ］とする。ここで、Ｈｍは、Ｍ×（Ｎ−Ｍ）部分行列である。与えられたＮ−Ｍ次元メッセージベクトルＭ（ｘ）に対するＭ次元パリティベクトルをＰ（ｘ）＝（Ｐ１，Ｐ２，…，ＰＭ）とした時、コードワードベクトルＣ（ｘ）＝（Ｍ（ｘ）、Ｐ（ｘ））は、ＨＣＴ＝ＨｍＭＴ＋ＨｐＰＴ＝０（Ｍ次元のゼロベクトル）を満足せねばならない。すなわち、Ｈのあらゆる行ベクトルとＣＴとの行列積は、ＧＦ（２）上で０でなければならない。結論的に、与えられたＭ（ｘ）に対してＨＣＴ＝０を満足するＭ次元パリティベクトルＰ（ｘ）を探せば、デコーディングによるエンコーディングが可能である。
【００４０】
第１に、代数的方法によるデコーディング過程を説明する。まず、Ｐ０（ｘ）＝（ｘ１，ｘ２，…，ｘＭ）と設定する。この値は、あらかじめ決定された任意の値であればよい。この時、Ｃ０（ｘ）＝（Ｍ（ｘ），Ｐ０（ｘ））である。代数的方法による場合、ｋステップのデコーディングによりＭ（ｘ）をＣ（ｘ）にエンコーディングできる。
【００４１】
段階１：集合Ａ１によるデコーディングを行う。
【００４２】
集合Ａ１にある行ベクトルを含むＨの行ベクトルとＣ０Ｔとの行列積は０でなければならず、前記行ベクトルのウエートは１であるため、前記行ベクトルでその値が１である成分に該当するパリティベクトルＰ０（ｘ）の成分ｘｉ１は、一元一次方程式により唯一の解Ｐｉ１を持つ。その結果Ａ１によりＰ０（ｘ）は、Ｐ１（ｘ）＝（ｘ１，…，Ｐｉ１，…，ｘＭ）にデコーディングされる。Ｃ１（ｘ）＝（Ｍ（ｘ），Ｐ１（ｘ））とする。
【００４３】
段階２：段階１のデコーディング結果を持ってＡ２によるデコーディングを行う。
【００４４】
集合Ａ２にある行ベクトルを含むＨの行ベクトルとＣ１Ｔとの行列積は０でなければならず、前記行ベクトルは、Ａ１にある行ベクトルとの線形結合を通じてウエートが１である行ベクトルを生成できるので、前記行ベクトルでその値が１である成分に該当するパリティベクトルＰ１（ｘ）の成分ｘｉ２は、一元一次方程式により唯一の解Ｐｉ２を持つ。その結果、Ａ２によりＰ１（ｘ）は、Ｐ２（ｘ）＝（ｘ１，…，Ｐｉ１，…，Ｐｉ２，…，ｘＭ）にデコーディングされる。Ｃ２（ｘ）＝（Ｍ（ｘ），Ｐ２（ｘ））とする。
【００４５】
段階ｋ：ステップ（ｋ−１）のデコーディング結果を持ってＡｋによるデコーディングを行う。
【００４６】
集合Ａｋにある行ベクトルを含むＨの行ベクトルとＣｋ−１Ｔとの行列積は０でなければならず、前記行ベクトルは、Ａ１＋Ａ２＋…＋Ａｋ−１にある行ベクトルとの線形結合を通じて、ウエートが１である行ベクトルを生成できるので、前記行ベクトルでその値が１である成分に該当するパリティベクトルＰｋ−１（ｘ）の成分ｘｉｋは、一元一次方程式により唯一の解Ｐｉｋを持つ。その結果、ＡｋによりＰｋ−１（ｘ）は、Ｐ（ｘ）＝（Ｐ１，Ｐ２，…，ＰＭ）にデコーディングされる。Ｃ（ｘ）＝（Ｍ（ｘ）、Ｐ（ｘ））とすれば、Ｃ（ｘ）は、Ｍ（ｘ）のエンコーディングされたコードワードである。
【００４７】
第二に、Ｓｕｍ−ＰｒｏｄｕｃｔやＳｕｍ−Ｐｒｏｄｕｃｔのａｐｐｒｏｘｉｍａｔｉｏｎである“ＭＩＮ”Ａｐｐｒｏｘｉｍａｔｉｏｎのように、ＬＬＲ（Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ）を使用したソフトイタラティブデコーディングによるエンコーディング方法を説明する。
【００４８】
この場合、Ｍ（ｘ）をＭ’（ｘ）＝２＊Ｍ（ｘ）−１に転換し、Ｐ’（ｘ）＝０に設定して、Ｃ’（ｘ）＝（Ｍ’（ｘ），Ｐ’（ｘ））をイタラティブデコーダに入力すれば、多くてもｋ回の反復によりＨＣＴ＝０になるＣ（ｘ）＝（Ｍ（ｘ）、Ｐ（ｘ））をデコーディングできる。この時、Ｐ’（ｘ）はイレイジャー表示のために０に設定されねばならず、これは、イレイジャー訂正を通じてエンコーディングを行うためである。
【００４９】
Ｍ’（ｘ）は、いかなるエラーも含んでおらず、その成分の値が１または−１であり、Ｐ’（ｘ）がいずれも０であるために、ソフトイタラティブデコーディングの特性上、最初の訂正によりＡ１の行ベクトルの成分が１である位置に対応するＰ（ｘ）の成分の値を訂正する。最初の訂正による結果をＣ１（ｘ）とした時、ＨＣ１Ｔ＝０ならば訂正が完了し、そうでなければ、２番目の反復訂正を行う。この時、Ａ２の行ベクトルは、Ａ１の行ベクトルとの線形結合を通じてウエートが１である行ベクトルを派生できるために、前記派生されたウエートが１である行ベクトルの成分が、１の位置に対応するＰ（ｘ）の成分の値を訂正する。２番目の訂正による結果をＣ２（ｘ）とした時、ＨＣ２Ｔ＝０ならば訂正が完了し、そうでなければ、反復訂正を続ける。このような方式で、少なくともｋ番目の訂正によりＰ（ｘ）のあらゆる成分値を訂正し、結果的には、多くてもｋ回のイタラティブデコーディングにより、Ｃ’（ｘ）をＣ（ｘ）＝（Ｍ（ｘ），Ｐ（ｘ））に訂正する。すなわち、メッセージベクトルＭ（ｘ）を、パリティベクトルが追加されたコードワードにエンコーディングする。
【００５０】
図６は、本発明によるエラー訂正装置の構成図である。エラー訂正装置は、本発明によるＭ×Ｎパリティ検査行列Ｈを生成する行列生成部６３０と、前記生成されたパリティ検査行列を利用したデコーディングを行うデコーダ６２０とを備える。デコーダ６２０は、エンコーディング時は、Ｎ−Ｍ次元のメッセージベクトル６０２に付加されるＭ次元のパリティベクトルを獲得して、エンコーディングされたメッセージベクトル６２２を出力し、デコーディング時は、受信されたコードワードベクトル６２４をデコーディングして、デコーディングされたコードワードベクトル６０４を出力する。また、デコーダ６２０としてソフトイタラティブデコーダを使用する場合、エンコーディング実行時、入力されたメッセージベクトル６０２の０を−１に置換した情報と、全体が０に設定された表示されたパリティベクトルとで構成されたコードワードベクトルをデコーダ６２０に出力するデコーダ入力処理部６１０をさらに備えることができる。
【００５１】
図７Ａないし図７Ｄは、本発明によるデコーディングによるエンコーディング過程の例を示す図である。図示された例は、ソフトイタラティブデコーディングによるエンコーディング方法により、ＨＣＴ＝０を満足するＣ（ｘ）を求める過程であり、図２に図示された例によるパリティ検査行列Ｈを利用して、ソフトイタラティブデコーディングを行う過程である。まず、ソフトイタラティブデコーディングのためにＣ’（ｘ）＝（２＊Ｍ（ｘ）−１，０）を入力する。すなわち、メッセージ部分は値が１ならば１、０ならば−１に変換し、パリティ部分は、イレイジャー訂正のために０に設定して、ソフトイタラティブデコーダに入力する。
【００５２】
図７Ａは、入力Ｃ’（ｘ）＝（Ｍ’（ｘ），０，０，０，０，０，０，０，０）である場合、最初の訂正過程を図示したものである。ＬＬＲ（１）（ｑｉ）を硬判定（Ｈａｒｄ  ｄｅｃｉｓｉｏｎ）した結果をＣ１（ｘ）とした時、ＨＣ１Ｔ＝０ならば、デコーディングを終了し、そうでなければ訂正を続ける。図７Ｂは、二番目の訂正過程を図示したものである。ＬＬＲ（２）（ｑｉ）を硬判定した結果をＣ２（ｘ）とした時、ＨＣ２Ｔ＝０ならばデコーディングを終了し、そうでなければ訂正を続ける。図７Ｃは、３番目の訂正過程を図示したものである。ＬＬＲ（３）（ｑｉ）を硬判定した結果をＣ３（ｘ）とした時、ＨＣ３Ｔ＝０ならばデコーディングを終了し、そうでなければ訂正を続ける。図７Ｄは、４番目の訂正過程を図示したものである。ＬＬＲ（４）（ｑｉ）を硬判定した結果をＣ４（ｘ）とした時、Ｃ４（ｘ）＝Ｃ（ｘ）であるしかないので、ＨＣ４Ｔ＝０であり、デコーディングが終了する。Ｃ４（ｘ）＝Ｃ（ｘ）であるしかない理由は、パリティ部分のａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ値が、デコーディングアルゴリズムにより各ステップでの行ベクトル、すなわち、ＡｉとＣｉ（ｘ）との行列積が０になるように設定されるためである。
【００５３】
前述したような、本発明による方法は、コンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現できる。
【００５４】
これまで、本発明についてその望ましい実施形態を中心に説明した。当業者は、本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態に具現できるということを理解できるであろう。したがって、開示された実施形態は限定的な観点でなく説明的な観点で考慮されねばならない。本発明の範囲は、前述した説明でなく特許請求の範囲に現れており、それと同等な範囲内にあるあらゆる差異点は、本発明に含まれていると解釈されねばならない。
【産業上の利用可能性】
【００５５】
本発明は、情報記録媒体に好適に用いられる。
【図面の簡単な説明】
【００５６】
【図１】本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第１実施形態を示す図である。
【図２】本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第２実施形態を示す図である。
【図３Ａ】本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第３実施形態を示す図である。
【図３Ｂ】本発明によるＭ×Ｎパリティ検査行列Ｈ＝［Ｈｍ｜Ｈｐ］の部分行列Ｈｐの第４実施形態を示す図である。
【図４Ａ】図１の部分行列Ｈｐを、パリティ検査ノードとビットノードとの連結状態を表すグラフに変換した図である。
【図４Ｂ】図２の部分行列Ｈｐを、パリティ検査ノードとビットノードとの連結状態を表すグラフに変換した図である。
【図５】本発明によるデコーディングによるエンコーディング方法を示すフローチャートである。
【図６】本発明によるエラー訂正装置の構成図である。
【図７Ａ】本発明によるデコーディングによるエンコーディング過程の例を示す図である。
【図７Ｂ】本発明によるデコーディングによるエンコーディング過程の例を示す図である。
【図７Ｃ】本発明によるデコーディングによるエンコーディング過程の例を示す図である。
【図７Ｄ】本発明によるデコーディングによるエンコーディング過程の例を示す図である。
【符号の説明】
【００５７】
６０２  メッセージベクトル
６０４  コードワードベクトル
６１０  デコーダ入力処理部
６２０  デコーダ
６２２  エンコーディングされたメッセージベクトル
６２４  デコーディングされたコードワードベクトル
６３０  パリティ検査行列生成部
【図１】
2007166605.tif 000003
【図２】
2007166605.tif 000004
【図３Ａ】
2007166605.tif 000005
【図３Ｂ】
2007166605.tif 000006
【図４Ａ】
2007166605.tif 000007
【図４Ｂ】
2007166605.tif 000008
【図５】
2007166605.tif 000009
【図６】
2007166605.tif 000010
【図７Ａ】
2007166605.tif 000011
【図７Ｂ】
2007166605.tif 000012
【図７Ｃ】
2007166605.tif 000013
【図７Ｄ】
2007166605.tif 000014