(57)【要約】【課題】ＬＤＰＣコードを用いて符号化または復号化するにおいて必要なパリティ検査行列を保存するためのメモリを節約することができ、符号化または復号化性能を高められるＬＤＰＣコードを用いた符号化または復号化方法及びその装置を提供する。【解決手段】少なくとも一つ以上の基本パーミュテーション行列の行と列のうち少なくとも何れか一つの順序の変更、または、前記少なくとも一つ以上の基本パーミュテーション行列の回転によって形成されたパーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成する段階と、前記パリティ検査行列を用いて入力データを符号化または復号化する段階と、を含んでＬＤＰＣコードを用いた符号化または復号化方法を構成する。【選択図】図１Ａ
2008514102.tif 000002
【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）コードを用いて入力データを符号化または復号化する方法において、
少なくとも一つ以上の基本パーミュテーション行列の行と列のうち少なくとも何れか一つの順序の変更、または、前記少なくとも一つ以上の基本パーミュテーション行列の回転によって形成されたパーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成する段階と、
前記パリティ検査行列を用いて入力データを符号化または復号化する段階と、を含むＬＤＰＣコードを用いた符号化または復号化方法。
【請求項２】
前記基本行列は、前記少なくとも一つ以上の基本パーミュテーション行列及び０行列を定義するパーミュテーションタイプをさらに含むことを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項３】
前記基本行列の各パーミュテーションタイプを、前記各パーミュテーションタイプが定義する行列に取り替えることで、前記パリティ検査行列に拡張することを特徴とする請求項２に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項４】
前記少なくとも一つ以上の基本パーミュテーション行列及び前記少なくとも一つ以上の基本パーミュテーション行列から前記パーミュテーション行列を形成する方法は、前記パリティ検査行列Ｈ全体に対して４―サイクルが形成されないように選択されることを特徴とする請求項２に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項５】
前記少なくとも一つ以上の基本パーミュテーション行列及び前記少なくとも一つ以上の基本パーミュテーション行列から前記パーミュテーション行列を形成する方法は、前記パリティ検査行列全体に対して６―サイクルが既に設定された臨界値（Ｃｍａｘ）以下になるように選択されることを特徴とする請求項４に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項６】
前記パリティ検査行列ＨがＨｐ及びＨｄの二つの部分によって構成されるとき（Ｈｐ及びＨｄは、パリティ検査行列Ｈの一部分であり、Ｈ＝［Ｈｄ｜Ｈｐ］（Ｈｄは、（ｎ―ｋ）×ｋで、Ｈｐは、（ｎ―ｋ）×（ｎ―ｋ）次元である）の構造である）、前記Ｈｐ部分は、ブロック二重対角行列であることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項７】
前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列の各行または列を所定方向に任意の間隔だけシフトさせることで形成されることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項８】
前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列の特定の行を任意の他の行と交換することで形成されることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項９】
前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列の特定の列を任意の他の列と交換することで形成されることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項１０】
前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させることで形成されることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項１１】
前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列の各行または列を所定方向に任意の間隔だけシフトさせるか（第１クラス）、特定の行を任意の他の行と交換するか（第２クラス）、特定の列を任意の他の列と交換するか（第３クラス）、前記少なくとも一つ以上の基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させて（第４クラス）形成されることを特徴とする請求項１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項１２】
前記パーミュテーション行列は、前記第１クラス〜第４クラスの二つ以上の組み合わせによって形成されることを特徴とする請求項１１に記載のＬＤＰＣコードを用いた符号化または復号化方法。
【請求項１３】
（ｎ−ｋ）×ｎ次元のＨ行列によって定義されるＬＤＰＣコードを生成する方法において、
ｚ×ｚ次元（ｚは、１以上の整数である）の少なくとも一つ以上の基本パーミュテーション行列またはｚ×ｚ次元の０行列を決定する段階と、
各元素として前記基本パーミュテーション行列を所定の規則によって変形させるか、前記０行列を示す情報を含む（ｎ−ｋ）／ｚ×ｎ／ｚ次元（ここで、ｎは、コードワードの長さで、ｋは、情報ブロックの長さである）の基本行列Ｈｂを決定する段階と、
前記情報によって前記基本パーミュテーション行列または前記０行列に取り替えることで、前記行列Ｈを生成するように前記基本行列を拡張する段階と、を含んで構成されることを特徴とするＬＤＰＣコード生成方法。
【請求項１４】
前記変形に関する情報は、前記基本パーミュテーション行列の行の交換、列の交換、回転、行のシフトに関する情報のうち少なくとも一つを含むことを特徴とする請求項１３に記載のＬＤＰＣコード生成方法
【請求項１５】
ＬＤＰＣコードを用いて入力データを符号化する符号化装置において、
少なくとも一つ以上の基本パーミュテーション行列の行及び列のうち少なくとも何れか一つの順序の変更、または、前記少なくとも一つ以上の基本パーミュテーション行列の回転によって形成されたパーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュールと、
前記パリティ検査行列生成モジュールによって生成されたパリティ検査行列を用いて入力データを符号化する符号化モジュールと、を含む符号化装置。
【請求項１６】
前記基本行列は、前記少なくとも一つ以上の基本パーミュテーション行列または０行列を定義するパーミュテーションタイプをさらに含むことを特徴とする請求項１５に記載の符号化装置。
【請求項１７】
前記パリティ検査行列モジュールは、前記基本行列の各パーミュテーションタイプを前記各パーミュテーションタイプが定義する行列に取り替えることで、前記基本行列を前記パリティ検査行列に拡張することを特徴とする請求項１６に記載の符号化装置。
【請求項１８】
前記所定の規則は、前記少なくとも一つ以上の基本パーミュテーション行列の各行または列を所定方向に任意の間隔だけシフトさせる第１クラスであるか、特定の行を任意の他の行と交換する第２クラスであるか、特定の列を任意の他の列と交換する第３クラスであるか、前記少なくとも一つ以上の基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させる第４クラスであることを特徴とする請求項１５に記載の符号化装置。
【請求項１９】
前記パーミュテーション行列は、前記第１クラス〜第４クラスの二つ以上の組み合わせによって形成されることを特徴とする請求項１８に記載の符号化装置。
【請求項２０】
前記少なくとも一つ以上の基本パーミュテーション行列及び前記基本行列を保存するメモリモジュールをさらに含むことを特徴とする請求項１７に記載の符号化装置。
【請求項２１】
ＬＤＰＣコードを用いて入力データを符号化する復号化装置において、
少なくとも一つ以上の基本パーミュテーション行列の行及び列のうち少なくとも何れか一つの順序の変更、または、前記少なくとも一つ以上の基本パーミュテーション行列の回転によって形成されたパーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュールと、
前記パリティ検査行列生成モジュールによって生成されたパリティ検査行列を用いて入力データを符号化する符号化モジュールと、を含む復号化装置。
【請求項２２】
前記基本行列は、前記少なくとも一つ以上の基本パーミュテーション行列または０行列を定義するパーミュテーションタイプをさらに含むことを特徴とする請求項２１に記載の復号化装置。
【請求項２３】
前記パリティ検査行列モジュールは、前記基本行列の各パーミュテーションタイプを前記各パーミュテーションタイプが定義する行列に取り替えることで、前記基本行列を前記パリティ検査行列に拡張することを特徴とする請求項２２に記載の復号化装置。
【請求項２４】
前記所定の規則は、前記少なくとも一つ以上の基本パーミュテーション行列の各行または列を所定方向に任意の間隔だけシフトさせる第１クラスであるか、特定の行を任意の他の行と交換する第２クラスであるか、特定の列を任意の他の列と交換する第３クラスであるか、前記少なくとも一つ以上の基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させる第４クラスであることを特徴とする請求項２１に記載の復号化装置。
【請求項２５】
前記パーミュテーション行列は、前記第１クラス〜第４クラスの二つ以上の組み合わせによって形成されることを特徴とする請求項２４に記載の復号化装置。
【請求項２６】
前記少なくとも一つ以上の基本パーミュテーション行列及び前記基本行列を保存するメモリモジュールをさらに含むことを特徴とする請求項２１に記載の復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化及び復号化方法に関するものである。より具体的には、低密度パリティ検査（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ：ＬＤＰＣ）コードを用いて符号化または復号化する方法において必要なパリティ検査行列を保存するためのメモリを節約することができ、符号化または復号化性能を向上させることができるＬＤＰＣコードを用いた符号化または復号化方法、符号化または復号化のためのＬＤＰＣコード生成方法及び符号化または復号化装置に関するものである。
【背景技術】
【０００２】
一般的に、符号化（ｅｎｃｏｄｉｎｇ）は、送信側から送信されたデータが通信チャネルを通して伝送される過程で発生する信号の歪み、損失などによるエラー発生にもかかわらず、受信側で元のデータを復元できるように送信側でデータを処理する過程を意味する。また、復号化（ｄｅｃｏｄｉｎｇ）は、符号化されて送信された信号を、受信側で元のデータに復元する過程である。
【０００３】
最近、ＬＤＰＣコードを用いた符号化方法が注目を浴びているが、ＬＤＰＣコードは、パリティ検査行列Ｈのほとんどの元素が‘０’である低密度の線形ブロック符号であり、１９６２年にＧａｌｌａｇｅｒによって提案された。ＬＤＰＣ符号は、非常に複雑であり、提案当時の技術では具現不可能であったが、１９９５年に再び発見され、その性能が非常に優秀であることが立証されて以来、それに対する研究が最近まで活発に行われている。（参考文献：［１］非特許文献１［２］非特許文献２）
【０００４】
ＬＤＰＣコードのパリティ検査行列は、‘１’の個数が非常に少ないので、ブロック大きさが非常に大きい場合も、反復復号を通して復号が可能であり、ブロック大きさが非常に大きくなると、ターボコードのように、シャノン（Ｓｈａｎｎｏｎ）のチャネル容量限界に近接する性能を示す。
【０００５】
ＬＤＰＣコードは、（ｎ−ｋ）×ｎパリティ検査行列Ｈによって説明される。前記パリティ検査行列Ｈに対応する生成行列Ｇは、次の数学式１によって求められる。
【０００６】
［数学式１］
Ｈ・Ｇ＝０
【０００７】
ＬＤＰＣコードを用いた符号化及び復号化方法において、送信側では、前記パリティ検査行列Ｈと数学式１の関係にある前記生成行列Ｇを用いて、次の数学式２によって入力データを符号化する。
【０００８】
［数学式２］
ｃ＝Ｇ・ｕ（ここで、ｃは、コードワードであり、ｕは、データフレームである。）
【０００９】
最近は、前記生成行列Ｇによらず、前記パリティ検査行列Ｈを用いて入力データを符号化する方法が一般的に用いられている。したがって、上述したように、ＬＤＰＣコードを用いた符号化方法では、前記パリティ検査行列Ｈが最も重要な要素といえる。前記パリティ検査行列Ｈは、約１０００×２０００以上の大きさを有するので、符号化及び復号化過程で多くの演算が要求され、その具現が非常に複雑であり、多くの保存空間が要求されるという問題点があった。
【非特許文献１】Ｒｏｂｅｒｔ  Ｇ．Ｇａｌｌａｇｅｒ、"Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ"、Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ、Ｓｅｐｔｅｍｂｅｒ  １５、１９６３．
【非特許文献２】Ｄ．Ｊ．Ｃ．Ｍａｃｋａｙ、Ｇｏｏｄ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、ＩＴ−４５、ｐｐ．３９９−４３１（１９９９）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、上記のような従来技術の問題点を解決するためになされたもので、その目的は、ＬＤＰＣコードを用いて符号化または復号化するにおいて必要なパリティ検査行列を保存するためのメモリを節約することができ、符号化または復号化性能を高められるＬＤＰＣコードを用いた符号化または復号化方法及びその装置を提供することにある。
【００１１】
本発明の他の目的は、ＬＤＰＣコードを用いた符号化または復号化方法において必要なパリティ検査行列を保存するためのメモリを節約できるＬＤＰＣコード生成方法を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の一様相として、本発明に係るＬＤＰＣコードを用いた符号化または復号化方法は、パーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成する段階を含む。また、本発明は、前記パリティ検査行列を用いて入力データを符号化または復号化する段階を含む。
【００１３】
本発明の他の様相として、本発明に係る符号化または復号化のためのＬＤＰＣコード生成方法は、（ｎ−ｋ）×ｎ次元のＨ行列によって定義されるＬＤＰＣコードを生成する方法において、ｚ×ｚ次元（ｚは、１以上の整数である）の少なくとも一つ以上の基本パーミュテーション行列またはｚ×ｚ次元の０行列を決定する段階と、各元素として前記基本パーミュテーション行列を所定の規則によって変形させるか、前記０行列を示す情報を含む（ｎ−ｋ）／ｚ×ｎ／ｚ次元（ここで、ｎは、コードワードの長さで、ｋは、情報ブロックの長さである）の基本行列Ｈｂを決定する段階と、前記情報によって前記基本パーミュテーション行列または前記０行列を取り替えることで、前記行列Ｈを生成するように前記基本行列を拡張する段階と、を含んで構成されることを特徴とする。
【００１４】
本発明の更に他の様相として、本発明に係るＬＤＰＣコードを用いた符号化装置は、パーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュールを含む。また、本発明に係る符号化装置は、前記パリティ検査行列生成モジュールによって生成されたパリティ検査行列を用いて入力データを符号化する符号化モジュールを含む。
【００１５】
本発明の更に他の様相として、本発明に係るＬＤＰＣコードを用いた復号化装置は、パーミュテーション行列を定義するパーミュテーションタイプを少なくとも一つ以上の元素として含む基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュールと、前記パリティ検査行列生成モジュールによって生成されたパリティ検査行列を用いて入力データを復号化する復号化モジュールと、を含んで構成されることを特徴とする。
【００１６】
前記パーミュテーションタイプによって定義されるパーミュテーション行列は、少なくとも一つ以上の基本パーミュテーション行列であるか、前記少なくとも一つ以上の基本パーミュテーション行列の行及び列のうち少なくとも何れか一つの順序の変更、または、前記少なくとも一つ以上の基本パーミュテーション行列の回転によって形成された多数のパーミュテーション行列または０行列であることが好ましい。
【００１７】
前記基本行列の各パーミュテーションタイプを前記各パーミュテーションタイプが定義するパーミュテーション行列に取り替えることで、前記パリティ検査行列が拡張され、その結果、前記パリティ検査行列が生成されることが好ましい。
【００１８】
前記パーミュテーション行列を形成する方法は、前記少なくとも一つ以上の基本パーミュテーション行列の各行または列を所定方向に任意の間隔だけシフトさせる第１クラスであるか、特定の行を任意の他の行と交換する第２クラスであるか、特定の列を任意の他の列と交換する第３クラスであるか、前記少なくとも一つ以上の基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させる第４クラスであることが好ましい。
【産業上の利用可能性】
【００１９】
本発明は、移動通信システムや広帯域無線接続システムなどの無線通信システムのみならず、符号化または復号化が必要な全ての分野に適用可能である。
【発明を実施するための最良の形態】
【００２０】
以下、本発明に係るＬＤＰＣコードを用いた符号化または復号化方法及びその装置の好適な実施例について、添付の図面に基づいて詳細に説明する。図１Ａは、本発明の好適な一実施例を説明するための図で、本発明の技術的特徴が無線通信システムに適用された一例を説明している。以下で説明する実施例は、本発明の特徴を説明するための例示に過ぎないもので、本発明の技術的特徴は、符号化または復号化が必要な全ての分野に適用可能である。
【００２１】
図１Ａに示すように、送信機１０及び受信機３０は、無線チャネル２０を介して通信を行う。前記送信機１０では、データソース１１から出力されたｋビットのソースデータｕが、ＬＤＰＣ符号化器１３でのＬＤＰＣ符号化によってｎビットのコードワードｃになる。コードワードｃは、変調器１５によって無線変調されてアンテナ１７を通して送信され、無線チャネル２０を通して前記受信機３０のアンテナ３１に受信される。前記受信機３０では、前記送信機１０で行った過程と逆の過程を経る。すなわち、受信されたデータが復調器３３によって復調され、ＬＤＰＣ復号化器３５によって復号されることで、最終的にソースデータｕを得られる。上述したようなデータ送受信過程は、本発明の特徴を説明するために必要な最小限の範囲内で説明したもので、その他にも、データ伝送のために必要な多くの過程があり得る。
【００２２】
図１Ｂ及び図１Ｃは、図１ＡのＬＰＤＣ復号化器１３及びＬＰＤＣ復号化器３５の詳細構成図で、以下、その詳細な内容を説明する。
【００２３】
前記ＬＤＰＣ符号化器１３で入力ソースデータを符号化するために用いられる前記パリティ検査行列Ｈは、（ｎ−ｋ）×ｎ次元を有する。前記ｋは、前記ＬＤＰＣ符号化器１３に入力されるソースデータの長さ（ビット単位）で、前記ｎは、符号化されたコードワードｃの長さ（ビット単位）を意味する。前記パリティ検査行列Ｈは、図２に示すように、ｚ×ｚ次元の多数のパーミュテーション行列または０行列によって構成される。すなわち、図２において、Ｐｉ，ｊは、ｚ×ｚ次元のパーミュテーション行列または０行列を意味する。
【００２４】
前記多数のパーミュテーション行列は、少なくとも一つ以上の基本パーミュテーション行列を所定の規則によって変形させて形成することができる。前記一つ以上の基本パーミュテーション行列を含む前記多数のパーミュテーション行列は、行と列の重みが１であることが好ましい。すなわち、前記多数のパーミュテーション行列の全ての行及び全ての列の元素のうち一つの元素のみが１で、残りの元素は０であることが好ましい。前記少なくとも一つ以上の基本パーミュテーション行列を変形して前記多数のパーミュテーション行列を形成する所定の規則として、以下の四つの方法（クラス）が挙げられる。
【００２５】
第一のクラスは、前記基本パーミュテーション行列の全ての行（または列）を特定の方向に所定間隔だけシフトさせる方法である。図３は、その一例を説明するための図である。すなわち、図３において、図３（ａ）の基本パーミュテーション行列の全ての行を下方向に５行だけ（ｎｓ＝５）（または、全ての列を右側に３列だけ）シフトさせて図３（ｂ）のパーミュテーション行列を形成した。前記第一のクラスによると、ｚ×ｚ次元の基本パーミュテーション行列に対してシフトされる行（または列）の間隔によって（ｚ−１）個のパーミュテーション行列を形成することができる（したがって、基本パーミュテーション行列を含むと、ｚ個のパーミュテーション行列が形成される）。前記基本パーミュテーション行列が与えられると、前記基本パーミュテーション行列を含む前記ｚ個のパーミュテーション行列は、それぞれ一つの整数によって表現される。例えば、基本パーミュテーション行列を‘０’で表現し、前記基本パーミュテーション行列の全ての行を特定の方向に１行だけシフトさせたパーミュテーション行列を‘１’で表現し、前記基本パーミュテーション行列の全ての行を２行だけシフトさせたパーミュテーション行列を‘２’で表現するなどの方法によって全てのパーミュテーション行列を一つの整数によって表現する。
【００２６】
第二のクラスは、前記基本パーミュテーション行列の特定の行を任意の他の行と交換する方法である。図４は、その一例を説明するための図である。すなわち、図４では、図４（ａ）の基本パーミュテーション行列の１番目行と６番目行を交換して図４（ｂ）のパーミュテーション行列を形成した。第二のクラスによると、ｚ×ｚ次元の基本パーミュテーション行列に対して１番目行と交換される行が何番目の行であるかによって（ｚ−１）個のパーミュテーション行列を形成することができる（したがって、基本パーミュテーション行列を含むと、ｚ個のパーミュテーション行列が形成される）。前記基本パーミュテーション行列が与えられると、前記基本パーミュテーション行列を含む前記ｚ個のパーミュテーション行列は、それぞれ一つの整数によって表現される。例えば、基本パーミュテーション行列を‘０’で表現し、前記基本パーミュテーション行列の１番目行と２番目行を交換して形成されたパーミュテーション行列を‘１’で表現し、前記基本パーミュテーション行列の１番目行と３番目行を交換して形成されたパーミュテーション行列を‘２’で表現するなどの方法によって全てのパーミュテーション行列を一つの整数で表現することができる。図４では、１番目行を基準にして任意の他の行と交換してパーミュテーション行列を形成したが、基準になる行を他の任意の行にした場合にも同一の結果を得られる。
【００２７】
第三のクラスは、前記基本パーミュテーション行列の特定の列を任意の他の列と交換する方法である。図５は、第三のクラスの一例を説明するための図である。すなわち、図５において、図５（ａ）の基本パーミュテーション行列の１番目列と６番目列を交換して図５（ｂ）のパーミュテーション行列を形成した。前記第三のクラスによると、ｚ×ｚ次元の基本パーミュテーション行列に対して１番目列と交換される列が何番目の列であるかによって、（ｚ-１）個のパーミュテーション行列を形成することができる（したがって、基本パーミュテーション行列を含むと、ｚ個のパーミュテーション行列が形成される）。前記基本パーミュテーション行列が与えられると、前記基本パーミュテーション行列を含む前記ｚ個のパーミュテーション行列は、それぞれ一つの整数によって表現される。例えば、基本パーミュテーション行列を‘０’で表現し、前記基本パーミュテーション行列の１番目列と２番目列を交換して形成されたパーミュテーション行列を‘１’で表現し、前記基本パーミュテーション行列の１番目列と３番目列を交換して形成されたパーミュテーション行列を‘２’で表現するなどの方法によって全てのパーミュテーション行列を一つの整数で表現することができる。図５では、１番目列を基準にして任意の他の列と交換してパーミュテーション行列を形成したが、基準になる列を他の任意の列にした場合にも同一の結果を得られる。
【００２８】
第四のクラスは、前記基本パーミュテーション行列を９０゜、１８０゜または２７０゜ずつ回転させることでパーミュテーション行列を形成する方法である。図６は、その一例を説明するための図である。すなわち、図６において、図６（ａ）の基本パーミュテーション行列を９０゜回転させ、図６（ｂ）のパーミュテーション行列を形成した。第四のクラスによると、ｚ×ｚ次元の基本パーミュテーション行列に対する回転角度によって３個のパーミュテーション行列を形成することができる（したがって、基本パーミュテーション行列を含むと、４個のパーミュテーション行列が形成される）。前記基本パーミュテーション行列が与えられると、前記基本パーミュテーション行列を含む前記４個のパーミュテーション行列は、それぞれ一つの整数によって表現される。例えば、基本パーミュテーション行列を‘０’で表現し、前記基本パーミュテーション行列を９０゜回転させて形成したパーミュテーション行列を‘１’で表現し、前記基本パーミュテーション行列の全ての行を１８０゜回転させて形成したパーミュテーション行列を‘２’で表現するなどの方法によって全てのパーミュテーション行列を一つの整数で表現する。
【００２９】
上記の四つのクラスによって基本パーミュテーション行列から形成された多数のパーミュテーション行列のタイプは、一つの整数によって単純に表現することができる。ｚ×ｚ次元のパーミュテーション行列を定義する整数などを、本明細書ではパーミュテーションタイプと称する。このパーミュテーションタイプを整数で表現することは、一つの例に過ぎないもので、パーミュテーションタイプは、その他にも多様に前記パーミュテーションタイプを表現できることは明らかである。
【００３０】
本発明は、パリティ検査行列Ｈを用いて符号化または復号化するにおいて、パリティ検査行列Ｈ自体を保存するのではなく、ｚ×ｚ次元のパーミュテーション行列を定義するパーミュテーションタイプを各元素として含む基本行列Ｈｂを保存した状態で、符号化または復号化時に前記基本行列Ｈｂの各元素をそのパーミュテーションタイプが定義するパーミュテーション行列に取り替えて拡張することでパリティ検査行列Ｈを生成し、前記生成されたパリティ検査行列を用いて符号化または復号化を行うことを特徴とする。これによって、符号化または復号化性能を高めることができ、パリティ検査行列自体を保存する必要がないのでメモリを節約することができる。
【００３１】
上述したように、図１Ｂ及び図１Ｃは、図１ＡのＬＤＰＣ符号化器１３及びＬＤＰＣ復号化器３５をそれぞれ示す詳細構成図である。図１Ｂ及び図１Ｃを参照すると、前記ＬＤＰＣ符号化器１３は、少なくとも一つ以上の基本パーミュテーション行列及び基本行列Ｈｂを保存するメモリモジュール１３１と、前記基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュール１３３と、前記パリティ検査行列生成モジュール１３３によって生成されたパリティ検査行列を用いて入力データを符号化する符号化モジュール１３５と、を含んで構成される。また、前記ＬＤＰＣ復号化器３５は、少なくとも一つ以上の基本パーミュテーション行列及び基本行列Ｈｂを保存するメモリモジュール３５１と、前記基本行列を拡張してパリティ検査行列を生成するパリティ検査行列生成モジュール３５３と、前記パリティ検査行列生成モジュール３５３によって生成されたパリティ検査行列を用いて入力データを符号化する符号化モジュール３５５と、を含んで構成される。
【００３２】
前記基本パーミュテーション行列として単位行列などの典型的な行列を用いる場合、前記ＬＤＰＣ符号化器１３または復号化器３５のメモリモジュール１３１，３５１は、前記基本行列Ｈｂのみを保存することができる。前記パリティ検査行列生成モジュール１３３，３５３は、前記基本行列Ｈｂの各元素をそのパーミュテーションタイプが定義するパーミュテーション行列に取り替えて拡張することで、パリティ検査行列Ｈを生成する。前記パーミュテーション行列は、前記少なくとも一つ以上の基本パーミュテーション行列と、前記少なくとも一つ以上の基本パーミュテーション行列を上述した第１クラス〜第４クラスまたはこれらの結合によって変形させて形成される多数のパーミュテーション行列と、０行列のうち何れか一つである。上述したような機能を行う前記パリティ検査行列生成モジュール１３３，３５３は、ソフトウェア的またはハードウェア的に具現可能である。
【００３３】
前記符号化モジュール１３５は、前記パリティ検査行列生成モジュール１３３によって生成されたパリティ検査行列を用いて入力データを符号化する。パリティ検査行列を用いて入力データを符号化する方法としては、多様な方法が用いられる。例えば、次のような方法があり得るが、これに限定されることはない。
【００３４】
前記数学式１及びＨ＝［Ｈｄ｜Ｈｐ］の関係によって、Ｇ＝［I｜（Ｈｐ−１Ｈｄ）ｔ］ｔであることが分かる。したがって、前記符号化モジュール１３５は、前記数学式２によって入力データｕに前記Ｇ＝［I｜（Ｈｐ−１Ｈｄ）ｔ］ｔを掛け算することで符号化する。結局、数学式２は、次の数学式３に取り替えられる。より具体的には、ｋビットの入力ソースデータｓ１×ｋは、数学式２によって符号化されてｎビットのコードワードｘ１×ｋになる。コードワードｘは、ｘ＝［ｓｐ］＝［ｓ０，ｓ１，・・・，ｓｋ−１、ｐ０，ｐ１，・・・，ｐｍ−１］の構成を有する（ここで、（ｐ０，ｐ１，・・・，ｐｍ−１）は、パリティ検査ビットで、（ｓ０，ｓ１，・・・，ｓｋ−１）は、システムビットである）。
【００３５】
［数学式３］
ｃ＝［I｜（Ｈｐ−１Ｈｄ）ｔ］ｔ・ｕ
【００３６】
しかし、前記生成行列Ｇを用いた符号化方法は非常に複雑である。したがって、このような複雑度を減少させるために、前記生成行列Ｇによらず、パリティ検査行列Ｈを用いて直接入力ソースデータを符号化することが好ましい。すなわち、ｘ＝［ｓｐ］であるので、Ｈ・ｘ＝０である特性を用いると、Ｈ・ｘ＝Ｈ・［ｓｐ］＝０になり、この式からパリティ検査ビットｐを得ることができ、結果的にコードワードｘ＝［ｓｐ］を求めることができる。
【００３７】
前記復号化器３５の復号化モジュール３５５が上述した方法で符号化されたデータを受信して復号するにおいて、次の数学式４を用いる。
【００３８】
［数学式４］
Ｈ・ｃ＝０
【００３９】
すなわち、符号化されたデータｃと前記パリティ検査行列Ｈとを掛け算して０になる場合、伝送エラーがないことを意味し、０にならない場合、伝送エラーが存在することを意味するので、これによってソースデータを分離することができる。
【００４０】
前記基本行列ＨｂをＨｄ及びＨｐの二つの部分に分割すると仮定したとき、一般的に、前記Ｈｐ部分には、ブロック二重対角行列を用いることができる。ブロック二重対角行列は、主対角及び前記主対角の真下側または上側の対角が全て単位行列で、残りが全て０行列であることを意味する。
【００４１】
前記基本パーミュテーション行列と、前記基本パーミュテーション行列から多数の他のパーミュテーション行列を形成する方法を選択するとき、前記パリティ検査行列Ｈ全体において４―サイクルや６―サイクルなどの短いサイクルの生成を最小化することが好ましい。特に、前記パリティ検査行列は、４―サイクルを持たないことが好ましい。また、前記パリティ検査行列Ｈは、既に設定された臨界値Ｃｍａｘ以下の６―サイクルを有することが好ましい。４―サイクルは、パリティ検査行列Ｈの任意の二つの行が二つの地点で同時に１を有する場合を意味する。また、６―サイクルは、前記パリティ検査行列Ｈの任意の三つの行から選択された組み合わせ可能な二つの行が同一の地点で１を有する場合を意味する。
【００４２】
図７Ａ乃至図７Ｃは、送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された一つの基本パーミュテーション行列と、前記基本パーミュテーション行列を上述した四つのクラスの組み合わせによって変形させて形成されたパーミュテーション行列のパーミュテーションタイプを元素として有する基本行列Ｈｂを用いて、パリティ検査行列Ｈを生成する方法を説明するための図である。
【００４３】
図７Ａは、ｚ＝５で、全ての行と列の重みが１である基本パーミュテーション行列を示している。図７Ｂは、前記基本パーミュテーション行列を上述した四つのクラスの組み合わせによって変形させて形成されたパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを示している。図７Ｂにおいて、基本行列Ｈｂが含むパーミュテーション行列のタイプは、（ｎｓ，ｎｒ，ｎｃ，ｎｔ）のような形式で表示された。（ｎｓ，ｎｒ，ｎｃ，ｎｔ）のような形式は、図７Ａに示した基本パーミュテーション行列の全ての行（または列）をｎｓだけシフトさせ、特定の行（例えば、１番目行）をｎｒ番目の行と交換し、特定の列（例えば、１番目列）をｎｃ番目の列と交換し、ｎｔに該当する角度だけ回転させたパーミュテーション行列を意味する。例えば、パーミュテーション行列のタイプ（２，０，１，０）は、図７Ａに示した基本パーミュテーション行列を基準にして全ての行（または列）を２行ずつシフトさせた後、１番目の列と２番目の列を交換して形成された新しいパーミュテーション行列を意味する。図７Ｂにおいて、（−１）は、５×５次元の０行列を意味する。したがって、図７Ａに示した基本パーミュテーション行列と、図７Ｂに示したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂが与えられると、既に決定された規則によってパリティ検査行列Ｈを容易に生成することができる。図７Ｃは、図７Ａに示した基本パーミュテーション行列と、図７Ｂに示したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂによって生成されたパリティ検査行列Ｈを示している。
【００４４】
図７Ａ乃至図７Ｃによって説明される実施例では、前記基本パーミュテーション行列から上述した四つのクラスの組み合わせによって多数のパーミュテーション行列を生成する方法を説明したが、前記多数のパーミュテーション行列は、前記四つのクラスのうち何れか一つのクラスによっても生成され、四つのクラスのうち何れか二つまたは三つのクラスの組み合わせによっても生成される。前記多数のパーミュテーション行列を前記四つのクラスのうち何れか一つのクラスによって生成する場合、前記パーミュテーション行列のタイプは一つの整数によって表現可能であり、二つのクラスによって生成する場合、前記パーミュテーション行列のタイプは二つの整数によって表現可能であり、三つのクラスの組み合わせによって生成する場合、前記パーミュテーション行列のタイプは三つの整数によって表現可能である。
【００４５】
例えば、前記第一のクラスの前記基本パーミュテーション行列の全ての行（または列）を所定間隔だけシフトさせる方法と、前記第二のクラスで前記基本パーミュテーション行列を所定角度だけ回転させる方法とを組み合わせると、前記基本行列Ｈｂが含む前記パーミュテーション行列のタイプは、（ｎｓ，ｎｒ，ｎｃ，ｎｔ）から（ｎｓ,ｎｒ）に単純化される。さらに、前記所定角度を９０゜にすると、前記パーミュテーション行列のタイプは、一つの整数ｓで表現可能になる。ここで、ｓは、０、１、・・・、（ｚ−１）、ｚ、（ｚ＋１）、・・・、（２×ｚ−１）のうち一つの数を有する整数である。すなわち、ｚ×ｚ次元の前記基本パーミュテーション行列を所定間隔だけシフトさせて生成されるｚ個の行列と、前記ｚ個の行列をそれぞれ所定方向に９０゜回転させて生成される他のｚ個の行列を、前記一つの整数ｓによって表現可能である。前記基本パーミュテーション行列として、ｚ×ｚ次元の単位行列を用いることができる。上記の例によると、前記基本行列Ｈｂに含まれる前記パーミュテーションタイプを簡単化できるのみならず、この簡単な情報を用いてＬＤＰＣコードを表現することで、ＬＤＰＣコード保存のためのメモリを節約しながら最適の性能を導き出すことができる。
【００４６】
図８Ａ乃至図８Ｃは、送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された二つの基本パーミュテーション行列と、前記二つの基本パーミュテーション行列を上述した四つのクラスの組み合わせによって変形させて形成されたパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【００４７】
図８Ａ乃至図８Ｃによって説明される実施例と、図７Ａ乃至図７Ｃによって説明される実施例との相異点は、二つの基本パーミュテーション行列から多数の他のパーミュテーション行列を生成する点にあり、その結果として、図８Ｂに示すように、基本行列Ｈｂが含むパーミュテーション行列のタイプが（ｎ０,ｎｓ,ｎｒ,ｎｃ,ｎｔ）などの方法によって表現される。ｎｓ、ｎｒ、ｎｃ及びｎｔが意味することは、上述した通りである。ｎ０は、二つの基本パーミュテーション行列のうち何れに基づいて多数の他のパーミュテーション行列を生成するかに関する情報である。
【００４８】
図８Ｂにおいて、（−１）は、５×５次元の０行列を意味する。図８Ｃは、図８Ａに示した二つの基本パーミュテーション行列と、図８Ｂに示したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂによって生成されたパリティ検査行列Ｈを示している。
【００４９】
二つの基本パーミュテーション行列に基づいて多数の他のパーミュテーション行列を形成する場合も、前記四つのクラスのうち何れか一つのクラスのみを用いるか、四つのクラスのうち何れか二つのクラスまたは三つのクラスの組み合わせを用いる。また、前記基本パーミュテーション行列の個数は、三つ以上であることが明らかである。
【００５０】
本発明に係るＬＤＰＣコードを用いた符号化及び復号化方法によると、入力データを符号化または復号化するにおいて、大容量のメモリを占めるパリティ検査行列を保存する必要がないため、メモリを節約できるのみならず、符号化または復号化性能を向上できるという効果がある。
【００５１】
本発明は、本発明の精神及び必須的な特徴を逸脱しない範囲で、他の特定の形態で具体化されることが当業者にとって自明である。したがって、上記の詳細な説明は、全ての面で制限的に解析されてはならなく、例示的なものとして考慮されるべきである。本発明の範囲は、添付の特許請求の範囲の合理的な解析によって決定されるべきで、本発明の等価的範囲内での全ての変更は本発明の範囲に含まれる。
【図面の簡単な説明】
【００５２】
【図１Ａ】本発明の好適な一実施例を説明するための通信システム構成図である。
【図１Ｂ】図１ＡのＬＤＰＣ符号化器を示す詳細構成図である。
【図１Ｃ】図１ＡのＬＤＰＣ復号化器を示す詳細構成図である。
【図２】ｚ×ｚ次元の多数のパーミュテーション行列または０行列を含むパリティ検査行列Ｈの構成図である。
【図３】本発明の好適な一実施例において、基本パーミュテーション行列の全ての行を所定間隔だけシフトさせて多数のパーミュテーション行列を形成する方法を説明するための図である。
【図４】本発明の好適な一実施例において、基本パーミュテーション行列の特定の行を任意の他の行と交換することで多数のパーミュテーション行列を形成する方法を説明するための図である。
【図５】本発明の好適な一実施例において、基本パーミュテーション行列の特定の列を任意の他の列と交換することで多数のパーミュテーション行列を形成する方法を説明するための図である。
【図６】本発明の好適な一実施例において、基本パーミュテーション行列を特定の角度だけ回転させて多数のパーミュテーション行列を形成する方法を説明するための図である。
【図７Ａ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された一つの基本パーミュテーション行列と、前記基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【図７Ｂ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された一つの基本パーミュテーション行列と、前記基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【図７Ｃ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された一つの基本パーミュテーション行列と、前記基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【図８Ａ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された二つの基本パーミュテーション行列と、前記二つの基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【図８Ｂ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された二つの基本パーミュテーション行列と、前記二つの基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【図８Ｃ】送信側または受信側でデータを符号化または復号化する過程で、メモリに保存された二つの基本パーミュテーション行列と、前記二つの基本パーミュテーション行列を上記した四つの方法の組み合わせによって変形させて形成したパーミュテーション行列のタイプに関する情報を含む基本行列Ｈｂを用いてパリティ検査行列Ｈを生成する方法を説明するための図である。
【符号の説明】
【００５３】
１０  送信機
１１  データソース
１３  ＬＤＰＣ符号化器
１５  変調器
１７  アンテナ
２０  無線チャネル
３０  受信機
３１  アンテナ
３３  復調器
３５  ＬＤＰＣ復号化器
【図１Ａ】
2008514102.tif 000003
【図１Ｂ】
2008514102.tif 000004
【図１Ｃ】
2008514102.tif 000005
【図２】
2008514102.tif 000006
【図３】
2008514102.tif 000007
【図４】
2008514102.tif 000008
【図５】
2008514102.tif 000009
【図６】
2008514102.tif 000010
【図７Ａ】
2008514102.tif 000011
【図７Ｂ】
2008514102.tif 000012
【図７Ｃ】
2008514102.tif 000013
【図８Ａ】
2008514102.tif 000014
【図８Ｂ】
2008514102.tif 000015
【図８Ｃ】
2008514102.tif 000016
【国際調査報告】
2008514102.tif 000017
2008514102.tif 000018