JP4672016B2 - 低密度パリティ検査行列を用いた符号化及び復号化方法 - Google Patents

Description

本発明は、符号化（ｅｎｃｏｄｉｎｇ）及び復号化（ｄｅｃｏｄｉｎｇ）方法に係り、より具体的には、低密度パリティ検査（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：以下、‘ＬＤＰＣ’という。）コードを用いて符号化する方法の性能（ｐｅｒｆｏｒｍａｎｃｅ）を向上させることができ、かつ、可変データレートを適用する通信システムに效果的に適用できる符号化または復号化方法に関する。

一般に、符号化（ｅｎｃｏｄｉｎｇ）は、データが送信側から通信チャネルを通じて転送される過程で信号の歪、損失などによる誤りが発生する場合にも、受信側で元来のデータを復元できるように送信側でデータ処理を行う過程をいい、復号化（ｄｅｃｏｄｉｎｇ）は、符号化して送信された信号を受信側で元来のデータに復元する過程をいう。

近来、ＬＤＰＣコードを用いた符号化方法が注目を浴びている。ＬＤＰＣコードは、パリティ検査行列（ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）Ηの元素の大部分が‘０’である低密度（ｌｏｗ ｄｅｎｓｉｔｙ）の線形ブロック符号（ｌｉｎｅａｒ ｂｌｏｃｋ ｃｏｄｅ）で、１９６２年ガラガー（Ｇａｌｌａｇｅｒ）によって提案された。ＬＤＰＣ符号は、非常に複雑なため提案当時の技術では具現不可能なものとして認識され、忘れられていたが、１９９５年の再発見によって性能の優秀性が立証されて以来、それに関する研究が活発に進行されている現状にある。（参考文献：非特許文献１、非特許文献２）
ＬＤＰＣコードのパリティ検査行列は、‘０’と‘１’によって構成される２進行列（ｂｉｎａｒｙ ｍａｔｒｉｘ）で、‘１’の個数が少ないため、非常に大きい行列大きさにおいて反復復号を通じて復号化が可能であり、行列大きさが非常に大きくなるとターボコード（ｔｕｒｂｏ ｃｏｄｅ）のようにシャノン（Ｓｈａｎｎｏｎ）のチャネル容量限界に近接する性能を示す。

ＬＤＰＣコードは、（ｎ−ｋ）×ｎ次元のパリティ検査行列Ηによって説明されることができる。該パリティ検査行列Ηに対応する生成行列（ｇｅｎｅｒａｔｏｒ ｍａｔｒｉｘ）Ｇは、次の数学式１によって求められる。
（数学式１）
Η・Ｇ＝０
ＬＤＰＣコードを用いた符号化及び復号化方法においては、送信側で当該パリティ検査行列Ηと数学式１の関係にある生成行列Ｇを用い、次の数学式２によって入力データを符号化する。
（数学式２）
ｃ＝Ｇ・ｕ（ここで、ｃはコードワード（ｃｏｄｅ ｗｏｒｋ）を表し、ｕはデータフレームを表す。）
しかしながら、最近では生成行列Ｇによらず、パリティ検査行列Ηを用いて入力データを符号化する方法が一般的に使われている。したがって、上記のように、ＬＤＰＣコードを用いる符号化及び復号化方法では、パリティ検査行列Ηが最も重要な要素であると言えよう。このパリティ検査行列Ηは、その大きさが非常に大きいため符号化及び復号化過程で多くの演算が要求され、且つ、具現が非常に複雑である他、多くの保存空間を要求する。

一般にパリティ検査行列Ｈへより多くの重み（ｗｅｉｇｈｔ）を付加することは、パリティ検査方程式（ｐａｒｉｔｙ ｃｈｅｃｋ ｅｑｕａｔｉｏｎｓ）へより多くの変数を付加することとなるため、ＬＤＰＣコードによる符号化及び復号化方法においてより良い性能を発揮できる。しかし、一方では、パリティ検査行列Ｈへより多くの重みを付加すると、パリティ検査行列全体に４−サイクルや６−サイクルを形成する場合が多くなり、ＬＤＰＣコードによる符号化及び復号化方法の性能を低下させる危険性につながることもある。

なお、最近の移動通信システムまたは無線インターネットシステムなどでは、チャネル状況または転送するデータ量に応じて可変データレートを適用する場合が多いが、このような可変データレートを適用するシステムには、従来のＬＤＰＣコードを用いた符号化方法を応用し難いという問題点があった。
Ｒｏｂｅｒｔ Ｇ．Ｇａｌｌａｇｅｒ，「ＬＯＷ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ Ｃｏｄｅｓ」，Ｔｈｅ ＭＩＴ Ｐｒｅｓｓ，Ｓｅｐｔｅｍｂｅｒ １５，１９６３． Ｄ．Ｊ．Ｃ．Ｍａｃｋａｙ，Ｇｏｏｄ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｖｅｒｙ ｓｐａｒｓｅ ｍａｔｒｉｃｅｓ，ＩＥＥＥ Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，（１９９９）ＩＴ−４５，ｐｐ．３９９−４３１

本発明は上記の従来技術の問題点を解決するためのもので、その目的は、ＬＤＰＣコードを用いて符号化及び復号化する方法において、符号化及び復号化性能（ｐｅｒｆｏｒｍａｎｃｅ）を向上させることができる方法を提供することにある。

本発明の他の目的は、可変データレート（ｖａｒｉａｂｌｅ ｄａｔａ ｒａｔｅ）を適用する通信システムに效果的に応用できる、ＬＤＰＣコードを用いた符号化及び復号化方法を提供することにある。

本発明の一様相として、本発明によるＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）コードを用いた符号化または復号化方法は、入力データをパリティ検査行列（ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）Ｈを用いて符号化または復号化する方法において、前記パリティ検査行列Ｈは、Ｈ＝［Ｈ_ｄ｜Ｈ_ｐ］（Ｈ_ｄは（ｎ−ｋ）×ｋ、Ｈ_ｐは（ｎ−ｋ）×（ｎ−ｋ）次元であり、ｋは入力データのビット数、ｎはコードワードのビット数である。）の構成を有し、前記Ｈ_ｄは、列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）がｗ_ｃである部分とｗ_ｃ＋ｗ_ａである部分（前記ｗ_ｃ及びｗ_ａは０でない定数である。）の２部分で構成されることを特徴とする。

本発明の他の様相として、本発明によるＬＤＰＣコードを用いた符号化または復号化方法は、入力データをパリティ検査行列Ｈを用いて符号化または復号化する方法において、前記パリティ検査行列Ｈは、Ｈ＝［Ｈ_ｄ｜Ｈ_ｐ］（Ｈは（ｎ−ｋ）×ｎ次元であり、ｋは入力データのビット数、ｎはコードワードのビット数である。）の構成を有し、前記パリティ検査行列Ｈは、列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）がｗ_ｃである部分とｗ_ｃ＋ｗ_ａである部分（前記ｗ_ｃ及びｗ_ａは０でない定数である。）の２部分で構成されることを特徴とする。

好ましくは、前記パリティ検査行列Ｈまたは前記Ｈ_ｄが（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する複数の第１サブ行列で構成される場合に、前記列重みがｗ_ｃである部分にある前記各第１サブ行列の行重み及び列重みは０または１であり、前記パリティ検査行列Ηまたは前記Ｈ_ｄの任意のいずれの２行（ｒｏｗｓ）も２つ以上の地点に同時に１を有しないことを特徴とする。

本発明に係るＬＤＰＣコードを用いた符号化及び復号化方法は、移動通信システムや携帯インターネットシステムなどのような通信システムに応用可能である。

以下、添付図面に基づいて説明される本発明に係るＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）コードを用いた符号化及び復号化方法の好適な実施例によって、本発明の構成、作用、効果及びその他の特徴がより明確になる。図１は、本発明の好ましい一実施例を説明するための図で、本発明の技術的特徴が無線通信システムに適用された一例である。なお、以下に説明される実施例は、本発明の特徴を説明するための例示に過ぎず、符号化及び復号化を必要とするあらゆる分野に本発明の技術的特徴が適用可能であることは、当業者にとっては自明である。

図１で、送信器１０と受信器３０とが無線チャネル２０を媒介として通信を行う。送信器１０では、データソース１１から出力されたｋビットのソースデータｕが、ＬＤＰＣ符号化モジュール１３でのＬＤＰＣ符号化（ｅｎｃｏｄｉｎｇ）によってｎビットのコードワードｃとなる。コードワードｃは、変調モジュール１５によって無線変調され、アンテナ１７から送信されて無線チャネル２０を通じて受信器３０のアンテナ３１で受信される。この受信器３０では、上記送信器１０で起きた過程の逆過程を経て元来のデータを復元する。すなわち、復調モジュール３３によって復調され、ＬＤＰＣ復号化モジュール３５によって復号されて最終的にソースデータｕが得られる
上述のデータ送受信過程は、本発明の特徴を説明する上で必要な最小限の範囲内で説明されたもので、それ以外にもデータ転送に必要な他の多くの過程があることは、当業者にとっては容易に理解される。

上記数学式１で、第１パリティ検査行列Ηは、Η＝［Ｈ_ｄ｜Ｈ_ｐ］（Ｈ_ｄは（ｎ−ｋ）×ｋ、Ｈ_ｐは（ｎ−ｋ）×（ｎ−ｋ）次元である）で表現されることができる。図２は、Η＝［Ｈ_ｄ｜Ｈ_ｐ］の関係を容易に理解させるように例示したものである。ここで、ｋは、ＬＤＰＣ符号化モジュール１３に入力されるソースデータの長さ（ビット単位）であり、ｎは、符号化したコードワードｃの長さ（ビット単位）を意味する。

数学式１及びΗ＝［Ｈ_ｄ｜Ｈ_ｐ］の関係によってＧ＝［Ｉ｜（Ｈ_ｐ ^−１Ｈ_ｄ）^ｔ］^ｔであることがわかる。したがって、ＬＤＰＣ符号化モジュール１３は、上記数学式２によって入力データｕにＧ＝［Ｉ｜（Ｈ_ｐ−１Ｈ_ｄ）^ｔ］^ｔを乗じることによって符号化する。結局、数学式２は、次の数学式３に取り替えることができる。より具体的には、ｋビットの入力ソースデータｓ_１×ｋは数学式２によって符号化して、ｎビットのコードワードｘ_１×ｋとなる。コードワードｘは、ｘ＝［ｓｐ］＝［ｓ_０，ｓ_１，…，ｓ_ｋ−１，ｐ_０，ｐ_１，…，ｐ_ｍ−１］の構成を有する（ここで、（ｐ_０，ｐ_１，…，ｐ_ｍ−１）はパリティ検査ビット（ｐａｒｉｔｙ ｃｈｅｃｋ ｂｉｔｓ）であり、（ｓ_０，ｓ_１，…，ｓ_ｋ−１）はシステマチックビット（ｓｙｓｔｅｍａｔｉｃ ｂｉｔｓ）である。）。
（数学式３）
ｃ＝［Ｉ｜（Ｈ_ｐ ^−１Ｈ_ｄ）^ｔ］^ｔ・ｕ
しかしながら、生成行列Ｇを用いた符号化方法は非常に複雑である。したがって、このような複雑度を減らすために、生成行列Ｇによらず、パリティ検査行列Ｈを用いて直接入力ソースデータを符号化することが好ましい。すなわち、ｘ＝［ｓｐ］なので、Ｈ・ｘ＝０の特性を用いるとＨ・ｘ＝Ｈ・［ｓｐ］＝０となり、この式からパリティ検査ビットｐが得られ、結果としてコードワードｘ＝［ｓｐ］を求めることができる。

Ｈ_ｐは、（ｎ−ｋ）×（ｎ−ｋ）次元の二重対角行列（ｄｕａｌ ｄｉａｇｏｎａｌ ｍａｔｒｉｘ）とすることが好ましい。二重対角行列は、主対角（ｍａｉｎ ｄｉａｇｏｎａｌ）とこの主対角の真下の対角が１であり、残りがいずれも０の行列を意味するものである。この二重対角行列の理解を助ける一例を、図３に示す。

図４は、数学式３で表現されるパリティ検査行列Ｈを用いた符号化過程を実際に具現するエンコーダ（ｅｎｃｏｄｅｒ）のブロック構成図である。入力データｕは、Ｈ_ｄ部分とＨ_ｐ ^−１部分によって符号化され、符号化したコードワードｃとなる。図４で、Ｈ_ｐ ^−１部分は、Ｈ_ｐとして二重対角行列（ｄｕａｌ ｄｉａｇｏｎａｌ ｍａｔｒｉｘ）を使用した時、Ｈ_ｐ ^−１を実際に具現した構成例である。

本発明の特徴は、［Ｈ_ｄ｜Ｈ_ｐ］の構造を持つパリティ検査行列Ｈ、または該パリティ検査行列Ｈを構成するＨ_ｄのデータ構造にある。以下ではＨ_ｄの本発明に係る特徴を中心にして説明するものとする。以下に説明される本発明に係るＨ_ｄの特徴は、パリティ検査行列Ｈ全体に対しても同一に適用されることができる。

このＨ_ｄは、列（ｃｏｌｕｍｎ）と行（ｒｏｗ）の重み（ｗｅｉｇｈｔ）において一定の規則性を持つことを特徴とする。この規則性は、Ｈ_ｄを（ｎ−ｋ）×（ｎ−ｋ）次元を有するｒ／（１−ｒ）（ここで、ｒ＝ｋ／ｎ）個の行列Ｈ^（ｉ） _ｄ（ここで、ｉ＝１，２，…，ｒ／（１−ｒ））に分割し、任意のＨ^（ｉ） _ｄは（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有するｍ×ｍ個の第１サブ行列に分割する場合に、Ｈ_ｄを構成する任意の第１サブ行列の行重み（ｒｏｗ ｗｅｉｇｈｔ）及び列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）は１とすることによって達成できる。また、当該パリティ検査行列Ηの任意のいずれの２行（ｒｏｗｓ）も２つ以上の地点に同時に１を有しないようにＨ_ｄを構成し、該パリティ検査行列Ηに含まれた任意の１を含めて形成される６−サイクル（６−ｃｙｃｌｅ）の個数を、既に設定された臨界値（Ｃ_ｍａｘ）以下とすることが好ましい。

より具体的に説明すると、Ｈ_ｄは、コードレート（ｒ＝ｋ／ｎ）に応じて１つ以上のＨ^（ｉ） _ｄ（ここで、ｉ＝１，２，…，ｒ／（１−ｒ））で構成されることができる。コードレートｒは、入力データの長さｋと符号化したデータの長さｎとの比で、一般にｒ＝１／２、２／３、３／４、４／５などが使われる。Ｈ^（ｉ）ｄは、（ｎ−ｋ）×（ｎ−ｋ）次元を有する行列で、Ｈ_ｄ＝［Ｈ^（１） _ｄ｜Ｈ^（２） _ｄ｜…｜Ｈ^{（ｒ／（１−ｒ））} _ｄ］の関係を持つ。各Ｈ^（ｉ） _ｄが、（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有するｍ×ｍ個の第１サブ行列で構成されるとするとき、Ｈ_ｄを構成する任意の第１サブ行列の行重み（ｒｏｗ ｗｅｉｇｈｔ）及び列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）を１とすることによって当該Ｈ_ｄ全体に対して列重み及び行重みに一定の規則性を与えることができる。ｍは、正の整数で、Ｈ_ｄのレゾリューションファクター（ｒｅｓｏｌｕｔｉｏｎ ｆａｃｔｏｒ）である。このｍは、２〜１２のうち、最も良い性能を発揮するものを選択して使用することが好ましい。

図５は、パリティ検査行列Ｈの構造を説明するための図である。図５の例では、パリティ検査行列Ｈは、［Ｈ_ｄ｜Ｈ_ｐ］の構造を有し、Ｈ_ｄは、Ｈ_ｄ＝［Ｈ^（１） _ｄ｜Ｈ^（２） _ｄ｜Ｈ^（３） _ｄ｜Ｈ^（４） _ｄ］の構造を有する。図５の例では、ｍ＝５で、各Ｈ^（ｉ） _ｄは、５×５＝２５個の第１サブ行列で構成される。各第１サブ行列の行重み及び列重みが１であるというのは、各第１サブ行列の任意の行及び列には１が１つのみあり、残りはいずれも０であるという意味である。ｍは、４〜１２のうち、最も良い性能を発揮するものを選択して使用することが好ましい。

他の実施例として、Ｈ_ｄを構成する任意の第１サブ行列の行重み（ｒｏｗ ｗｅｉｇｈｔ）及び列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）は、０または１でありうる。すなわち、任意のＨ^（ｉ） _ｄに対して、Ｈ^（ｉ） _ｄを構成する第１サブ行列の内には、行重み及び列重みが０であるものも、１であるものもある。この場合、任意のＨ^（ｉ） _ｄに対して、行重み（ｒｏｗ ｗｅｉｇｈｔ）及び列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）が０のサブ行列は、Ｈ^（ｉ） _ｄの行及び列方向に同じ数で存在することが好ましい。

また、Ｈ_ｐは、（ｎ−ｋ）×（ｎ−ｋ）次元の二重対角行列（ｄｕａｌ ｄｉａｇｏｎａｌ ｍａｔｒｉｘ）とすることが好ましい。二重対角行列は、主対角（ｍａｉｎ ｄｉａｇｏｎａｌ）と該主対角の真下の対角が１であり、残りがいずれも０の行列を意味する。

以上ではＨ_ｄを構成する行及び列重みが０または１であるという特徴について説明したが、パリティ検査行列Ｈ全体が（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する複数の第１サブ行列で構成される場合に、Ｈを構成する任意の第１サブ行列の行重み及び列重みを０または１とすることも可能である。すなわち、パリティ検査行列Ｈの一部構成であるＨ_ｄに対してのみ、該Ｈ_ｄを構成する第１サブ行列の行及び列重みが０または１であっても良く、パリティ検査行列Ｈの全体に対して、パリティ検査行列Ｈ全体を構成する第１サブ行列の行及び列重みが０または１であっても良い。

本発明の好ましい他の実施例として、Ｈ_ｄは全体として列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）がｗ_ｃである部分と、ｗ_ｃ＋ｗ_ａ（ｗ_ｃ及びｗ_ａは０でない定数である。）である部分の２部分で構成されることができる。すなわち、Ｈ_ｄの一部にｗ_ａだけの列重みをさらに付加する。ｗ_ａの付加されなかった部分は、前述したような規則性が続けて維持されることができる。好ましくは、Ｈ_ｄの大部分はその列の重みがｗ_ｃであり、一部分がｗ_ｃよりも大きいｗ_ｃ＋ｗ_ａである。好ましくは、ｗ_ａはｗ_ｃの１０〜１１０％の範囲内で選択されると良い。

一方、Ｈ_ｄが（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する複数の第２サブ行列に分割される場合に、列重みがｗ_ｃ＋ｗ_ａである部分は、複数の第２サブ行列のうち、１つまたは２つ以上の第２サブ行列に含まれても良く、複数の第２サブ行列のそれぞれの一部分であっても良い。

図６は、列重みがｗ_ｃ＋ｗ_ａである部分が、複数の第２サブ行列のうちの１つに含まれた場合を説明するための図である。図６で、Ｈ_ｄは、８個の（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する第２サブ行列で構成され、各第２サブ行列は、４個の（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する第１サブ行列で構成される。上記のように、各第１サブ行列の列重みが１といずれも同一であるため、各第２サブ行列の列重みもｗ_ｃ＝４といずれも同一である。ただし、図６で、ハッチされた１番目の第２サブ行列に対しては列重みをｗ_ａだけさらに付加して、他の第２サブ行列よりも列重みを大きくした。図６では、１番目の第２サブ行列の列重みを他の第２サブ行列のそれに比べて大きくしたが、１番目の第２サブ行列だけでなく、他の第２サブ行列にｗ_ａを付加しても良い。また、１つの第２サブ行列の全体に対してｗ_ａを付加することも可能であるが、１つの第２サブ行列の一部に対してｗ_ａを付加することも可能である。さらには、列重みがｗ_ｃ＋ｗ_ａである部分が、複数の第２サブ行列のうちの２つ以上に含まれても良い。例えば、図６で、１番目の第２サブ行列の全部と２番目の第２サブ行列の一部にのみ、列重みをｗ_ａだけ追加することも可能である。

ＬＤＰＣコードによる復号方法は、パリティ検査行列Ηを構成する行間にチャネル状況によって判断される確率的情報の反復的交換によってなされるが、図６に示すように、パリティ検査行列Ηの一部分の列重みを他の部分に比べて大きくすると、復号過程における収斂速度が速くなり、復号性能を高めることができる。

図７は、列重みがｗ_ｃ＋ｗ_ａである部分は、複数の第２サブ行列のそれぞれの一部分である場合を説明するための図である。図７では、全ての第２サブ行列のそれぞれの一部に対して（ハッチ部分）ｗ_ａを付加して、他の部分に比べて列重みを大きくした。この場合にも、追加される列重みｗ_ａをｗ_ｃと同一にして、ｗ_ａの付加されなかった部分に比べて列重みを２倍とすることが好ましい。Ｈ_ｄを図７のように構成すると、可変データレート（ｖａｒｉａｂｌｅ ｄａｔａ ｒａｔｅ）を適用するシステムに容易に応用することが可能になる。

また、上記のような特徴を持つＨ_ｄを含むパリティ検査行列Ηに含まれた任意の１を含めて形成される６−サイクルの個数が、既に設定された臨界値（Ｃ_ｍａｘ）以下であり、パリティ検査行列Ηの任意のいずれの２行（ｒｏｗｓ）も、２つ以上の列に同時に１を有しないことが好ましい。臨界値（Ｃ_ｍａｘ）は、パリティ検査行列Ｈに６−サイクルが存在しても、パリティ検査行列Ｈを用いた符号化及び復号化の性能低下が起きない範囲で決定されることが好ましい。より具体的には、パリティ検査行列Ｈに存在する６−サイクルの減少による性能改善効果と６−サイクルを減らすのに必要な計算量とを比較して、合理的範囲内で決定されることが好ましい。シミュレーション結果、臨界値（Ｃ_ｍａｘ）が略１０〜５００個の範囲で満足できるような性能が導き出されたし、１〜１００個の範囲でより良い性能を発揮した。ただし、この範囲に臨界値が制限されるわけではない。

図８は、パリティ検査行列Ηの任意の３行の中から選択されたあらゆる組み合わせ可能な２行が、同じ地点に１を持つ場合の例を示す図である。すなわち、ｉ、ｊ及びｋ行の３つの行から選択されたあらゆる組み合わせ可能な２行、すなわち、ｉ番目行とｊ番目行、ｊ番目行とｋ番目行、及びｋ番目行とｉ番目行が、同じ地点に１を持つ場合であり、図８で円で囲まれた６個の地点をつなぐとサイクルを形成するが、これを６−サイクルという。図９は、上記パリティ検査行列Ηの他の表現方法である二部グラフ（ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ）で、６行９列のパリティ検査行列を意味する。図９で、太線で表示された部分が６−サイクルを形成する部分である。このパリティ検査行列Ηに含まれた任意の１を含めて形成される６−サイクルの個数が、既に設定された臨界値（Ｃ_ｍａｘ）以下であるというのは、該パリティ検査行列Ηに含まれた任意の１を基準に該任意の１を含めて形成される６−サイクルが当該臨界値（Ｃ_ｍａｘ）よりも小さい、または、等しいということを意味する。

図１０は、パリティ検査行列Ηの２つの行が、２つの列に同時に１を持つ場合を例示する図である。すなわち、図１０で、ｉ番目行の円で囲まれた２つの地点とｊ番目行の円で囲まれた２つの地点がいずれも１である場合で、図１０のような場合がパリティ検査行列Ηに存在するとＬＤＰＣコードによる符号化及び復号化方法は良好な性能を発揮することができない。図１０に示すように、パリティ検査行列Ηの２つの行が２つの地点に同時に１を持つ場合を４−サイクル（４−ｃｙｃｌｅ）という。上記のパリティ検査行列Ηの任意のいずれの２行（ｒｏｗｓ）も２つ以上の地点に同時に１を有しないということは、パリティ検査行列Ηの全体に対して４−サイクルを形成する場合がないということを意味する。

前述したように、ＬＤＰＣコードによる符号化方法は、パリティ検査行列Ηを構成する行間にチャネル状況によって判断される確率的情報の反復的交換によってなされる。４−サイクル及び６−サイクルに関する２条件を満たさないパリティ検査行列Ηでは、各行の確率的情報が他の行に伝達されて充分な反復無しに戻ってくるので、良好な性能を発揮できない。

本発明の技術的特徴を有するパリティ検査行列Ηを符号化及び復号化に用いると、チャネル状況などによってコードレート（ｃｏｄｅ ｒａｔｅ）が可変する場合、第１サブ行列を除去または追加することによってパリティ検査行列Ηの大きさを可変させてもその特徴がそのまま維持されるため、可変コードレートを適用するシステムに容易に適応可能である。

パリティビット（ｐａｒｉｔｙ ｂｉｔｓ）を減らす場合には、図１１に示すように、Ｈ_ｐを構成する第１サブ行列から、第１サブ行列単位に任意の第１サブ行列を列（ｃｏｌｕｍｎ）方向に除去（ｒｅｄｕｃｉｎｇ）し、Ｈ_ｄとＨ_ｐを構成する第１サブ行列から、第１サブ行列単位に任意の第１サブ行列を行（ｒｏｗ）方向に除去する。図１１で、ハッチ部分が、除去される部分である。

図１２は、基本的に８個の第１サブ行列で構成されたパリティ検査行列Ηに対して、パリティビットを減らすために（１，４）、（２，１）、（２，２）、（２，３）及び（２，４）第１サブ行列を除去し、（１，１）、（１，２）及び（１，３）第１サブ行列のみでパリティ検査行列Ηを構成する例を示す図である。図１２では、（１，１）及び（１，２）第１サブ行列がＨ_ｄを構成し、（１，３）第１サブ行列がＨ_ｐを構成して、コードレートｒ＝２／３となる。図１１で、（１，３）、（２，１）、（２，２）、（２，３）及び（２，４）第１サブ行列を除去することによっても、パリティビットを減らすことができる。Ｈ_ｄを構成する各第１サブ行列のそれぞれの行重み（ｒｏｗ ｗｅｉｇｈｔ）及び列重み（ｃｏｌｕｍｎ ｗｅｉｇｈｔ）は０または１であるため、このＨ_ｄに対してはいくつかの第１サブ行列が除去されても、除去されて残った行列において任意の行と列の重み（ｗｅｉｇｈｔ）が０または１であるという基本特徴が維持される。

表１は、パリティビット（Ｎ_{ｐａｒｉｔｙ}）を変更することによってコードレート（Ｒ）を可変させる例を説明するためのものである。すなわち、図１１及び図１２に示すように、パリティ検査行列Ｈの一部第１サブ行列を除去するとパリティビット（Ｎ_{ｐａｒｉｔｙ}）が減り、結果としてコードレート（Ｒ）が高まる。

システマチックビット（ｓｙｓｔｅｍａｔｉｃ ｂｉｔｓ）を減らす場合には、図１３に示すように、Ｈ_ｄを構成する第１サブ行列から、第１サブ行列単位に任意の第１サブ行列を列（ｃｏｌｕｍｎ）方向に除去する。図１３で、ハッチ部分が、除去される部分となる。

図１４は、基本的に８個の第１サブ行列で構成されたパリティ検査行列Ηに対して、システマチックビットを減らすために（１，１）及び（２，１）第１サブ行列を除去した場合を示す図である。図１４で、（１，１）及び（２，１）第１サブ行列の代わりに、（１，２）及び（２，２）第１サブ行列を除去することによってシステマチックビットを減らすことができる。

表２は、システマチックビット（Ｎ_ｉｎｆｏ）を変更することによってコードレート（Ｒ）を可変させる例を説明するための図である。すなわち、図１３及び図１４に示すように、パリティ検査行列Ｈの一部第１サブ行列を除去するとシステマチックビット（Ｎ_ｉｎｆｏ）が高まり、結果としてコードレート（Ｒ）が高まる。

パリティビット及びシステマチックビットを同時に減らす場合には、図１５に示すように、Ｈ_ｐ及びＨ_ｄを構成する第１サブ行列から、第１サブ行列単位に任意の第１サブ行列を列（ｃｏｌｕｍｎ）及び行（ｒｏｗ）方向に除去する。図１５で、ハッチ部分が、除去される部分となる。

図１６Ａ及び図１６Ｂは、上記のような特徴を有するパリティ検査行列Ｈを生成する一過程を説明するための処理流れ図である。以下に説明される方法は一例に過ぎず、上記のような特徴を有するＨは、様々な方法によって得られることが可能である。

図１６Ａ及び図１６Ｂで、ｉはパリティ検査行列Ｈの任意の行（ｒｏｗ）のインデックス、ｊは任意の列（ｃｏｌｕｍｎ）のインデックス、ｋはｗ_ａを付加する列のインデックス、Ｃ_ｗは任意の列ｊまたはｋの現在重み（ｗｅｉｇｈｔ）数を意味する。まず、重みのない（Ｃ_ｗ＝０）の１番目の列（ｊ＝１）に対して重みを付加し始める［Ｓ１７，Ｓ１８］。ここで、重みを付加するというのは、任意の列の任意の行に該当する元素を１とするということを意味する。

１番目の列の任意のｉ番目の候補行（ｃａｎｄｉｄａｔｅ ｒｏｗ）に暫定的に重みを付加する［Ｓ１９］。暫定的に重みを付加するということは、その行に対する重み付けが最終的なものではなく、後の手続きによって変更可能なものであるという意味である。その後、パリティ検査行列Ｈが（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する複数の第１サブ行列で構成される場合に、当該ｊ番目列のｉ番目行が属したサブ行列の行と列に、重みが２以上である行または列が存在するかを検査する［Ｓ２０］。このｊ番目列のｉ番目行が属したサブ行列の行と列のうち、重み２以上の行または列が存在すると、当該ｉ番目行に対して重みを付加せずに他の行に重みを付加して［Ｓ１９］、その次の手続きを再び進行し、ｊ番目列のｉ番目行が属したサブ行列の行と列のうち、重み２以上の行または列が存在しないと、パリティ検査行列Ｈの全体に対して４−サイクルが存在するか判断する［Ｓ２１］。

４−サイクル（４−ｃｙｃｌｅ）とは、パリティ検査行列Ηの任意の２つの行が２つの地点に同時に１を持つ場合のことをいう。すなわち、パリティ検査行列Ηの全体に対して４−サイクルを形成する場合がないというのは、該パリティ検査行列Ηの任意のいずれの２行も２つ以上の地点に同時に１を有しないということを意味する。

パリティ検査行列Ｈの全体に対して４−サイクルが存在するか判断し［Ｓ２１］、４−サイクルが存在すると、ｉ番目行に対して重みを付加せずに他の行に重みを付加して［Ｓ１９］、その次の手続きを再び進行し、４−サイクルが存在しないと、ｉ番目行の１を含めて形成される６−サイクルが存在するか判断する［Ｓ２２］。

このｉ番目行の１を含めて形成される６−サイクルが存在するか判断した結果、６−サイクルが存在しないと、ｉ番目行に最終的に重みを付加する。６−サイクルが存在すると、ｉ番目行の１を含めて形成される６−サイクルの個数が、既に設定された臨界値（Ｃ_ｍａｘ）以下か判断し［Ｓ２３］、以下であると、同様にｉ番目行に最終的に重みを付加し［Ｓ２４］、以下でないとｉ番目行に重みを付加せずに他の行に重みを付加して［Ｓ１９］、その次の手続きを再び進行する。

ｉ番目行に重みを最終的に付加すると［Ｓ２４］、ｊ番目列の現在重み数（Ｃ_ｗ）を１増加させ［Ｓ２５］、ｊ番目列の現在重み数がｗ_ｃと同一か判断する［Ｓ２８］。ｊ番目列の現在重み数がｗ_ｃと同一であると、ｊ番目列に対する重み付けは終了し、ｊがコードワード長と同一か判断する［Ｓ２７］。一方、ｊ番目列の現在重み数がｗ_ｃと同一でないと、ステップＳ１９に戻り、ｊ番目列の他の行に暫定的に重みを付加し、その後続手続きを続けて行う。

ｊがコードワード長と同一であると、列重みｗ_ａをさらに付加する手続きが始まる。ｗ_ａを付加しようとする１番目の列の任意のｉ番目候補行（ｃａｎｄｉｄａｔｅ ｒｏｗ）に暫定的に重みを付加し［Ｓ３０］、パリティ検査行列Ｈの全体に対して４−サイクルが存在するか判断する［Ｓ３１］。

パリティ検査行列Ｈの全体に対して４−サイクルが存在するか判断した結果、４−サイクルが存在すると、ｉ番目行に対して重みを付加せずに他の行に重みを付加して［Ｓ３０］、その次の手続きを再び進行し、４−サイクルが存在しないと、ｉ番目行に最終的に重みを付加する［Ｓ３２］。

このようにｉ番目行に重みを最終的に付加すると［Ｓ３２］、ｋ番目列の現在重み数（Ｃ_ｗ）を１増加させ［Ｓ３３］、該ｋ番目列の現在重み数が（ｗ_ｃ＋ｗ_ａ）と同一か判断する［Ｓ３４］。ｋ番目列の現在重み数が（ｗ_ｃ＋ｗ_ａ）と同一であると、ｋ番目列に対する重み付けは終了し、このｋが、列重みｗ_ａをさらに付加しようとする列の最終個数Ｋと同一か判断する［Ｓ３５］。一方、ｋ番目列の現在重み数が（ｗ_ｃ＋ｗ_ａ）と同一でないとステップＳ３０に戻り、ｋ番目列の他の行に暫定的に重みを付加して、その後続手続きを続けて行う。

ｋが列重みｗ_ａをさらに付加しようとする列の最終個数Ｋと同一であると、パリティ検査行列Ｈの全体に対して重み付けが終了したことであるので、この時点までの重み付け結果に基づいて最終的にパリティ検査行列Ｈを生成することができる［Ｓ３７］。一方、ｋが列重みｗ_ａをさらに付加しようとする列の個数Ｋと同一でないと、まだ重みｗ_ａを付加しなかった列が存在するという意味であるので、ｋに１を追加して［Ｓ３６］、次の列に対してステップＳ３０から上記と同一の方法で重みを付加する。

列重みがｗ_ｃ＋ｗ_ａである部分を、複数の第２サブ行列のそれぞれの一部分とするためには、ステップＳ３６でｋが１ずつ増加する場合もあり、第２サブ行列の列の個数である（ｎ−ｋ）／ｍ個ずつ増加する場合もありうる。すなわち、この場合には、Ｋが、各第２サブ行列に含まれる列重みｗ_ｃ＋ｗ_ａの部分の列数の合計となる。

行重み及び列重みが０のサブ行列を含むパリティ検査行列Ｈを生成するためには、図１６Ａ及び図１６Ｂに示す手続きによって生成されたパリティ検査行列Ｈにおいていくつかのサブ行列の行重み及び列重みを０とすれば良い（図示せず）。

上記のように、パリティ検査行列Ｈ全体を上記のような手続きによって生成しても良いが、上記の如く、［Ｈ_ｄ｜Ｈ_ｐ］の構造を持つパリティ検査行列ＨにおいてＨ_ｄを上記の手続きによって生成し、Ｈ_ｐを定形化した形態としても良い。

図１で、受信器３０が、上記のような方法で符号化したデータを受信して復号する際には、下記の数学式４を利用する。
（数学式４）
Η・ｃ＝０
すなわち、符号化したデータｃとパリティ検査行列（ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）Ηを乗じて０になると、転送エラーがないということを意味し、０にならないと転送エラーが存在するということを意味するので、これによってソースデータを分離することができる。

本発明の技術的思想は、上記特徴を持つパリティ検査行列ΗまたはＨ_ｄのようなデータ構造が記録された、ＣＤ−ＲＯＭ、フロッピー（登録商標）ディスク、コンピュータメモリまたは移動通信用端末機のメモリなどのようなＣＰＵによって読取り可能な記録媒体にも及ぶことができる。

本発明に係るＬＤＰＣコードを用いた符号化方法及び符号化のためにコンピュータで読取り可能な記録媒体によれば、ＬＤＰＣコードによる符号化及び復号化方法の性能を向上させることができ、可変データレートを使用する通信システムにおいても容易に適応できる効果が得られる。

本発明は、本発明の精神及び必須特徴を逸脱しない範囲で他の特定の形態に具体化できることは当業者にとっては自明である。したがって、上記の詳細な説明はあらゆる面において制約的に解釈されてはいけなく、例示的なものとして考慮されるべきである。本発明の範囲は、添付の特許請求の範囲の合理的解釈によって定められなければならず、よって、本発明の等価的な範囲内でのあらゆる変更は、本発明の範囲に含まれる。

本発明の好適な一実施例を説明するための通信システム構成図である。 Η＝［Ｈ_ｄ｜Ｈ_ｐ］の関係を説明するための例示図である。 二重対角行列であるＨ_ｐの構成図である。 パリティ検査行列Ｈを用いた符号化過程を実際に具現したエンコーダ（ｅｎｃｏｄｅｒ）のブロック構成図である。 本発明によるパリティ検査行列Ｈの構造を説明するための図である。 本発明の好ましい一実施例によって列重みｗ_ｃ＋ｗ_ａの部分が複数の第２サブ行列のうちの一つの第２サブ行列に含まれた場合を説明するための図である。 本発明の好ましい一実施例によって列重みｗ_ｃ＋ｗ_ａの部分が複数の第２サブ行列のそれぞれの一部分である場合を説明するための図である。 パリティ検査行列Ηの任意の３行の中から選択されたあらゆる組み合わせ可能な２行が、同じ地点に１を持つ場合の例を示す図である。 パリティ検査行列Ηの他の表現方法である二部グラフ（ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ）である。 パリティ検査行列Ηの２つの行が２つの地点に同時に１を持つ場合を例示する図である。 本発明の好ましい一実施例においてパリティビットを除去する構造を説明するための図である。 本発明の好ましい一実施例においてパリティビットを除去する構造を説明するための図である。 本発明の好ましい一実施例においてシステマチックビットを減らす場合を説明するための図である。 本発明の好ましい一実施例においてシステマチックビットを減らす場合を説明するための図である。 本発明の好ましい一実施例においてパリティビット及びシステマチックビットを減らす場合を説明するための図である。 パリティ検査行列Ｈを生成する一過程を説明するための処理流れ図である。 パリティ検査行列Ｈを生成する一過程を説明するための処理流れ図である。

Claims (21)

1. 入力データをパリティ検査行列Ｈを用いて符号化または復号化する方法において、
   前記パリティ検査行列Ｈは、Ｈ＝［Ｈ_ｄ｜Ｈ_ｐ］（Ｈ_ｄは（ｎ−ｋ）×ｋ次元であり、Ｈ_ｐは（ｎ−ｋ）×（ｎ−ｋ）次元であり、ｋは入力データのビット数であり、ｎはコードワードのビット数である）の構成を有し、
   前記Ｈ_ｄは、ｗ _ｃ の列重みを有する第１部分とｗ_ｃ＋ｗ_ａ の列重みを有する第２部分とを含み、前記ｗ_ｃ及びｗ_ａは０ではなく、前記パリティ検査行列Ｈが（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する複数の第１サブ行列を含む場合に、前記ｗ _ｃ の列重みを有する第１部分にある前記複数の第１サブ行列の各々の行重み及び列重みは、一定の規則性を有することを特徴とする、低密度パリティ検査（ＬＤＰＣ）コードを用いた符号化または復号化方法。
2. 前記Ｈ_ｄが（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する複数の第２サブ行列を含む場合に、前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のうちの少なくとも１つの第２サブ行列に含まれる、請求項１に記載の方法。
3. 前記Ｈ_ｄが（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する複数の第２サブ行列を含む場合に、前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のそれぞれの一部分を構成する、請求項１に記載の方法。
4. 前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のうちの前記少なくとも１つの第２サブ行列の１つの列に対応するか、前記複数の第２サブ行列のうちの前記少なくとも１つの第２サブ行列の全体列に対応する、請求項２に記載の方法。
5. 前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のそれぞれの規定された１つの列に対応する、請求項３に記載の方法。
6. 前記ｗ _ｃ の列重みを有する第１部分にある前記複数の第１サブ行列の各々の行重み及び列重みは、０または１である、請求項１に記載の方法。
7. 前記Ｈ_ｄ全体の任意のいずれの２行も、少なくとも２つの列に同時に１を有しない、請求項１乃至６のいずれか１項に記載の方法。
8. 前記Ｈ_ｄ全体の任意の３行の中から選択されたあらゆる組み合わせ可能な２行が同じ列に１を有する場合が、既に設定された臨界値（Ｃ_ｍａｘ）以下である、請求項７に記載の方法。
9. 前記パリティ検査行列Ｈ全体の任意のいずれの２行も、少なくとも２つの行に同時に１を有しない、請求項１乃至６のいずれか１項に記載の方法。
10. 前記パリティ検査行列Ηの任意の３行の中から選択されたあらゆる組み合わせ可能な２行が同じ列に１を有する場合が、既に設定された臨界値（Ｃ_ｍａｘ）以下である、請求項９に記載の方法。
11. 前記Ｈ_ｐは、二重対角行列である、請求項１に記載の方法。
12. 入力データをパリティ検査行列Ｈを用いて符号化または復号化する方法において、
    前記パリティ検査行列Ｈは、Ｈ＝［Ｈ_ｄ｜Ｈ_ｐ］（Ｈは（ｎ−ｋ）×ｎ次元であり、ｋは入力データのビット数であり、ｎはコードワードのビット数である）の構成を有し、
    前記パリティ検査行列Ｈは、ｗ _ｃ の列重みを有する第１部分とｗ_ｃ＋ｗ_ａ の列重みを有する第２部分とを含み、前記ｗ_ｃ及びｗ_ａは０でなく、前記パリティ検査行列Ｈが（ｎ−ｋ）／ｍ×（ｎ−ｋ）／ｍ次元を有する複数の第１サブ行列を含む場合に、前記ｗ _ｃ の列重みを有する第１部分にある前記複数の第１サブ行列の各々の行重み及び列重みは、一定の規則性を有することを特徴とする、低密度パリティ検査（ＬＤＰＣ）コードを用いた符号化または復号化方法。
13. 前記パリティ検査行列Ｈが（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する複数の第２サブ行列を含む場合に、前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のうちの少なくとも１つの第２サブ行列に含まれる、請求項１２に記載の方法。
14. 前記パリティ検査行列Ｈが（ｎ−ｋ）×（ｎ−ｋ）／ｍ次元を有する複数の第２サブ行列を含む場合に、前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のそれぞれの一部分を構成する、請求項１２に記載の方法。
15. 前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のうちの前記少なくとも１つの第２サブ行列の規定された１つの列に対応するか、前記複数の第２サブ行列のうちの前記少なくとも１つの第２サブ行列の全体列に対応する、請求項１３に記載の方法。
16. 前記ｗ _ｃ＋ｗ_ａ の列重みを有する第２部分は、前記複数の第２サブ行列のそれぞれの規定された１つの列に対応する、請求項１４に記載の方法。
17. 前記ｗ _ｃ の列重みを有する第１部分にある前記複数の第１サブ行列の各々の行重み及び列重みは、０または１である、請求項１２に記載の方法。
18. 前記Ｈ_ｄ全体の任意のいずれの２行も、少なくとも２つの列に同時に１を有しない、請求項１２乃至１７のいずれか１項に記載の方法。
19. 前記Ｈ_ｄ全体の任意の３行の中から選択されたあらゆる組み合わせ可能な２行が同じ列に１を有する場合が、既に設定された臨界値（Ｃ_ｍａｘ）以下である、請求項１８に記載の方法。
20. 前記パリティ検査行列Ｈ全体の任意のいずれの２行も、少なくとも２つの行に同時に１を有しない、請求項１２乃至１７のいずれか１項に記載の方法。
21. 前記パリティ検査行列Ηの任意の３行の中から選択されたあらゆる組み合わせ可能な２行が同じ列に１を有する場合が、既に設定された臨界値（Ｃ_ｍａｘ）以下である、請求項２０に記載の方法。

Images