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