(57)【要約】【課題】ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成方法であり、特に、優れた復号特性を安定して得ることのできる符号語を設定するためのパリティチェック行列生成方法を提供する。【解決手段】パリティチェック行列内に含まれるサイクルに対応する部分行列についてその行列式が０とならないようなノンバイナリの非零成分を選択する。これによって、大きな重みの符号語を得ることのできるノンバイナリ・パリティチェック行列を生成する。【選択図】図１
2009531885.tif 000002
【特許請求の範囲】
【請求項１】
ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成方法であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定ステップと、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出ステップと、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択ステップと、を有し、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を構成するパリティチェック行列生成方法。
【請求項２】
前記行列設定ステップにおいて、前記バイナリ・パリティチェック行列は、既知のアルゴリズムにより生成された複数のバイナリ・パリティチェック行列の中から選択して設定する請求項１に記載のパリティチェック行列生成方法。
【請求項３】
前記検出ステップにおいて、成分０および成分１から構成される前記バイナリ・パリティチェック行列内の複数の成分１を行方向および列方向に沿って順次結んで一巡させてなるループを前記サイクルとして検出する請求項１に記載のパリティチェック行列生成方法。
【請求項４】
前記検出ステップにおいて、検出するループの長さを、予め定めた上限長以下に制限する請求項３に記載のパリティチェック行列生成方法。
【請求項５】
前記上限長は、
Ｌmin＋２[(Ｌmin−２)/４]
であり、ここに、
Ｌminは、前記バイナリ・パリティチェック行列内に含まれる前記サイクルのうち最短のサイクルの長さを表し、
［ ］は、Ｘについて［Ｘ］と表したときこの［Ｘ］は、Ｘを超えない整数であることを示す、
請求項４に記載のパリティチェック行列生成方法。
【請求項６】
成分０および成分１から構成される前記バイナリ・パリティチェック行列内において前記サイクルをなす成分のうち各該成分１に対し、前記ノンバイナリ成分である多値のうちの１つを割り当てるように、前記選択ステップでの選択を行う請求項１に記載のパリティチェック行列生成方法。
【請求項７】
各前記成分１について順次、前記多値のうちの１つを割り当てて前記の選択を実行し、未選択となって最後に残った１つの該成分１についてその多値のうちの１つを割り当てる際にのみ、当該サイクルに対応する前記部分行列についての行列式が０にならないようにその多値のうちの１つを選択する請求項６に記載のパリティチェック行列生成方法。
【請求項８】
前記の最後に未選択となって残った１つの成分１に至るまでの各成分１については、前記の多値のうちの１つをランダムに割り当てる請求項７に記載のパリティチェック行列生成方法。
【請求項９】
前記バイナリ・パリティチェック行列および前記ノンバイナリ・パリティチェック行列が共に、列重み２の行列である請求項１に記載のパリティチェック行列生成方法。
【請求項１０】
ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成装置であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０にならないように、該部分行列内のノンバイナリ成分を選択する選択部と、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置。
【請求項１１】
符号化して送信すべき情報ビットを入力し、これをノンバイナリＬＤＰＣ符号により符号化するＬＤＰＣ符号化器と、
前記の符号化を行うに際して使用するノンバイナリ・パリティチェック行列を保持する符号化側パリティチェック行列保持部と、
前記ＬＤＰＣ符号化器からの符号化後の前記情報ビットを変調して受信側に送信する変調器と、を含んでなる送信機であって、
前記符号化側パリティチェック行列保持部は、パリティチェック行列生成装置により生成されたノンバイナリ・パリティチェック行列を保持し、ここに、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、送信機。
【請求項１２】
バイナリビットである前記情報ビットをノンバイナリである多値シンボルに変換するために、前記ＬＤＰＣ符号化器の入力側に設けられる入力側変換部と、
前記ＬＤＰＣ符号化器により符号化された、ノンバイナリの多値シンボルからなる前記情報ビットを、前記バイナリビットに変換するために、前記ＬＤＰＣ符号化器の出力側に設けられる出力側変換部と、を備える請求項11に記載の送信機。
【請求項１３】
ノンバイナリＬＤＰＣ符号により符号化され変調して送信側より送信された情報ビットを受信し、これを復調する復調器と、
前記復調器からの対数尤度で表された復調ビットに対し、ノンバイナリＬＤＰＣ符号により復号を行うＬＤＰＣ復号器と、
前記の復号を行うに際して使用するノンバイナリ・パリティチェック行列を保持する復号側パリティチェック行列保持部と、を含んでなる受信機であって、
前記復号側パリティチェック行列保持部は、パリティチェック行列生成装置により生成されたノンバイナリ・パリティチェック行列を保持し、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、受信機。
【請求項１４】
前記復調器からの尤度で表されたバイナリの復調ビットを、ノンバイナリの多値シンボルに変換するために、前記ＬＤＰＣ復号器の入力側に設けられる入力側変換部と、
前記ＬＤＰＣ復号器により復号された、ノンバイナリの多値シンボルからなる前記情報ビットを、前記バイナリビットに変換するために、前記ＬＤＰＣ復号器の出力側に設けられる出力側変換部と、を備える請求項13に記載の受信機。
【請求項１５】
符号化して送信すべき送信情報が、コード長の長い第１送信情報と、該第１送信情報よりも短いコード長であるが該第１情報よりも高品質が要求される第２情報とを含むような送信機であって、
前記第１送信情報を入力し、これをバイナリＬＤＰＣ符号により符号化するバイナリＬＤＰＣ符号化器と、
前記第２送信情報を入力し、これをノンバイナリＬＤＰＣ符号により符号化するノンバイナリＬＤＰＣ符号化器と、
前記バイナリＬＤＰＣ符号化器からの符号化出力を変調する第１変調器と、
前記ノンバイナリＬＤＰＣ符号化器からの符号化出力を変調する第２変調器と、
該第１および第２変調器からの各変調出力を合成して受信側に送信する送信手段と、
を備えると共に、前記ノンバイナリＬＤＰＣ符号化器は、パリティチェック行列生成装置によって生成されたノンバイナリ・パリティチェック行列により前記の符号化を行い、ここに、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、送信機。
【請求項１６】
前記バイナリＬＤＰＣ符号化器は、前記第１送信情報として無線通信における情報ビットを入力し、
前記ノンバイナリＬＤＰＣ符号化器は、前記第２送信情報として無線通信における制御情報を入力する請求項15に記載の送信機。
【請求項１７】
前記バイナリＬＤＰＣ符号化器は、前記第１送信情報として無線通信における情報ビットを入力し、
前記ノンバイナリＬＤＰＣ符号化器は、前記第２送信情報として無線通信における報知情報を入力する請求項15に記載の送信機。
【請求項１８】
バイナリビットである前記第１送信情報をノンバイナリである多値シンボルに変換するために、前記ＬＤＰＣ符号化器の入力側に設けられる入力側変換部と、
前記ＬＤＰＣ符号化器により符号化された、ノンバイナリの多値シンボルからなる前記第２送信情報を、前記バイナリビットに変換するために、前記ＬＤＰＣ符号化器の出力側に設けられる出力側変換部と、を備える請求項15に記載の送信機。
【請求項１９】
請求項15に記載の送信機より送信された前記第１送信情報および前記第２送信情報を受信して、それぞれ個別に再生する受信機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列を生成する方法に関し、さらには、そのパリティチェック行列の生成装置、ならびに、そのノンバイナリ・パリティチェック行列を利用した送信機と受信機に関する。
【背景技術】
【０００２】
近年、従前のターボ符号と同様にシャノン限界に近い優れた特性を有する誤り訂正符号として、ＬＤＰＣ（Low Density Parity Check）符号が注目され始めている。
【０００３】
特に、このＬＤＰＣ符号の復号特性は上記ターボ符号と同等か、もしくは、その符号長が長い場合にはターボ符号よりも優れた特性を示すことが知られている。例えば、その符号長が数万ビット以上になると、第３世代携帯電話システムにおいて現在採用されている上記ターボ符号の復号特性を上回る場合がある。
【０００４】
かかるＬＤＰＣ符号として現在、バイナリ型のＬＤＰＣ符号と、ノンバイナリ型のＬＤＰＣ符号とが知られているが、後者のノンバイナリＬＤＰＣ符号を用いると、前者のバイナリＬＤＰＣ符号を用いる場合に比べて処理量が増加するという欠点がある。しかしこのような欠点があるものの、このノンバイナリＬＤＰＣ符号を用いると、上記符号長が短くなった場合であっても、バイナリＬＤＰＣ符号を用いたときよりも、復号特性の向上が見込まれる。
【０００５】
したがって、上記の欠点が今後の技術開発で改善されれば、ＬＤＰＣ符号におけるノンバイナリ型の適用範囲が広がるであろうことが想定される。そこで、かかるノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成する方法について考察すると、次のような問題がある。
【０００６】
バイナリ符号を定義するバイナリ・パリティチェック行列を生成する場合、成分０および成分１から構成される該行列内の成分１、すなわち非零成分を、その行列内のどの位置（何行何列）に配置するか、ということを決定するだけで十分である。
【０００７】
ところがノンバイナリ符号を定義するノンバイナリ・パリティチェック行列を生成する場合には、上記非零成分の位置を決定するだけでは十分でなく、そのノンバイナリである多値（１，２，３，４…）の各値までも決定する必要がある。
【０００８】
そこでその多値の各値を決定する決定の仕方について検討すると、従来においてはその決定の仕方について明確な基準あるいは規則はなく、実際には、その多値の各値をランダムに選択する（ランダム選択法）というのが一般的であった。このため、その選択のパターンに応じて、上記の特性がばらついてしまい、安定した良好な特性が得られない、という問題があった。
【０００９】
【非特許文献１】X.Y.Hu, E. Eleftheriou and D.M. Arnold,“Regular and Irregular Progressive Edge-Growth Tanner Graphs,”IEEE Trans. Inform. Theory, vol.51, pp.386-398, Jan. 2005.
【発明の開示】
【課題を解決するための手段】
【００１０】
したがって本発明は、上記問題点に鑑み、上記の特性にばらつきがなく安定しており、しかも、上記従来のランダム選択による場合に比べて、一層良好な特性が得られるように構成された、ノンバイナリ・パリティチェック行列を生成するためのアルゴリズム、すなわちノンバイナリ・パリティチェック行列の生成方法を提供することを目的とするものである。
【００１１】
さらには、上記ノンバイナリ・パリティチェック行列の生成装置を提供すること、さらにまた、上記ノンバイナリ・パリティチェック行列を利用した送信機および受信機を提供することを目的とするものである。
【００１２】
上記目的を達成するために、本発明は、
（１）バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定し、
（２）そのバイナリ・パリティチェック行列内に含まれるサイクルを検出し、
（３）その検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択し、
その選択されたノンバイナリ成分によってノンバイナリ・パリティチェック行列内の非零成分を構成することを特徴とするものである。
【発明の効果】
【００１３】
ノンバイナリ型ＬＤＰＣ符号における処理量の増加という欠点を克服し、ＬＤＰＣ符号本来の良好な復号特性が得られる。このためノンバイナリ型ＬＤＰＣ符号の適用範囲は一層広がる。
【発明を実施するための最良の形態】
【００１４】
図１は、本発明に係るパリティチェック行列生成方法の基本ステップを示すフローチャートである。
【００１５】
本図において、
Ｓ11：行列設定ステップ
Ｓ12：検出ステップ
Ｓ13：選択ステップ
であり、
ステップＳ11では、ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定し、
ステップＳ12では、その設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出し、
ステップＳ13では、上記のノンバイナリ・パリティチェック行列内において上記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択するものであり、
ここに上記の選択されたノンバイナリ成分によってノンバイナリ・パリティチェック行列内の非零成分を構成する。
【００１６】
このように選択されたノンバイナリ成分によってノンバイナリ・パリティチェック行列内の非零成分を構成する。このことは、すなわち、対応する部分行列の行列式＝が０となるサイクルに関して、なるべく小さいサイクルがノンバイナリ・パリティチェック行列内に含まれないようにすることを意味する。つまりなるべく重みの小さい（非零成分の少ない）符号語が存在しないように、ノンバイナリ・パリティチェック行列内の非零成分を選択する。これは、良く知られているように、パリティチェック行列が重みの小さい符号語、すなわち非零成分の少ない符号語を少なく持つ程、良好な復号特性が得られるからである。
【００１７】
なお、Ｍ行Ｎ列のパリティチェック行列において、Ｎ＞Ｍであるから、上記のフローチャートで行列式≠０を追求していったとしても、必ず行列式＝０となる部分行列が２N-M個存在し、この部分行列に対応する符号語は必ず存在する。なぜならＮ＞Ｍに設定してあるので、変数の数がＮ個、方程式の数がＭ個である方程式を解くことになり、（Ｎ−Ｍ）の自由度をもってその解が存在するからである。
【００１８】
ここで本発明の理解のために、本発明に係る技術の背景を予め説明しておく。
【００１９】
符号化率Ｒ、符号長ＮのＬＤＰＣ符号は、線形ブロック符号としてＭ行Ｎ列のパリティチェック行列Ｈによって定義される。このＬＤＰＣ符号は、そのパリティチェック行列Ｈがノンバイナリのガロア体の要素から構成されている場合に、ノンバイナリＬＤＰＣ符号と呼ばれる。
【００２０】
ここで、要素の個数がｑ個のガロア体（Galois Field）をＧＦ（ｑ）と表し、ノンバイナリの場合はｑ＞２となる。特にｑが２のべき乗の場合が一般的に用いられる。区別のためにｑ＝２の場合のＬＤＰＣ符号をバイナリＬＤＰＣ符号と呼ぶ。このパリティチェック行列Ｈを用いてＬＤＰＣ符号はＨｃ＝０と定義される。ここで、ｃはＮ行１列の符号語ベクトルである。つまり、あるパリティチェック行列Ｈに対して、上式Ｈｃ＝０を満たすようなベクトルｃの全体が、ＬＤＰＣ符号の符号語として定義される。このＬＤＰＣ符号のパリティチェック行列はその非零成分の密度が小さいことが特徴である。
【００２１】
なおＬＤＰＣ符号の復号は、パリティチェック行列Ｈに対応したタナーグラフ（後述する図11参照）上で行われる。このタナーグラフは、Ｎ個のビットノードとＭ個のチェックノードおよび、ＷｃＮ＝ＷｒＭ個のエッジから構成され、それぞれ、パリティチェック行列における列、行および非零成分に対応する。ただし、Ｗｃは列重み（１列中に存在する非零成分の個数）、Ｗｒは行重み（１行中に存在する非零成分の個数）を表す。なお、ここでは簡単のため、列重みおよび行重みがそれぞれ一定の場合（レギュラーＬＤＰＣ符号）を考える。
【００２２】
復号には該タナーグラフ上におけるＢＰ（Belief Propagation）アルゴリズムが用いられる。これは、繰り返し復号の一種で、ビットノードとチェックノードで情報（メッセージ）を交換することにより、各ビットの尤度を最適値に収束させるものである。ＬＤＰＣ符号の受信特性は、このタナーグラフ、すなわちパリティチェック行列Ｈに大きく依存するため、良好なパリティチェック行列を構成するための多くの方式が考案されてきた。具体的には、パリティチェック内の小さいサイクルを除去することが大きな特性の向上をもたらすことが知られており、ほとんどのパリティチェック行列構成方式は長さが短いサイクルを除去することに焦点が置かれている。なお後述する図11のタナーグラフ中に、長さ６のサイクルＣＬ６の一例を実線で示す。
【００２３】
本発明は、上記のように、パリティチェック内の小さいサイクルを除去することを狙いとするのではなく、ある一定のアルゴリズム（上記の図１）に従って各非零成分の値を選択することにより、小さいサイクルに対応する重みの小さい符号語を除去することによって良好な復号特性を得るパリティチェック行列を作成することを目的とする。この本発明に固有のアルゴリズムによると、前述した従来の「ランダム選択法」に比べて優れた復号特性が安定して得られる（後述する図４参照）。
【００２４】
以下、本発明の実施態様について説明する。本発明では、列重み２のパリティチェック行列を用いるノンバイナリＬＤＰＣ符号に注目する。一般的にレギュラーバイナリＬＤＰＣ符号では、列重み３のパリティチェック行列による復号特性が良好であることが報告されている。しかしレギュラーノンバイナリＬＤＰＣ符号においてそのガロア体の次元が大きくなるに従い、通常ｑ＝８程度で列重み２のパリティチェック行列の復号特性が列重み３のそれを上回る。このため、本発明の実施態様を列重み２のパリティチェック行列に限定しても、余り問題とはならない。なお、イレギュラーＬＤＰＣ符号を含めて、最適な行列重みの分布を考慮した場合にも、ｑが大きくなるに従って、最適な行列重み分布が一定重み２に近づくことが示されている（前述した下記の文献参照）。
【００２５】
〔文献〕
X.Y.Hu, E. Eleftheriou and D.M. Arnold,“Regular and Irregular Progressive Edge-Growth Tanner Graphs,”IEEE Trans. Inform. Theory, vol.51, pp.386-398, Jan. 2005.
【００２６】
次に図２を参照する。図２は、本発明の理解を早めるための、サイクルと符号語の関係を示す図である。本図において、両矢印の左側は、前述したＨｃ＝０の関係を示す。Ｈｃの一方“Ｈ”はパリティチェック行列であり、Ｍ行Ｎ列からなる行列である。この行列内の非零成分（Ａ，Ｂ，Ｃ…）をどのように決定するかが、本発明の課題である。
【００２７】
上記Ｈｃの他方“ｃ”は、符号語である。すなわち、送信側より符号化して送信すべき多種の「情報ビット」の１つ１つに１対１で対応させるべき符号を表す符号語である。この図２に示すように、Ｈｃ＝０が成立するとき、符号語が存在する。そしてこの場合、サイクルＣＬ（図では長さ＝６のサイクルを一例として示す）に対応して、符号語の非零成分ａ，ｂおよびｃが一意に定まる。つまり、
Ａａ＋Ｃｂ＝０
Ｂｂ＋Ｅｃ＝０
Ｄｂ＋Ｆｃ＝０
から、符号語ｃの非零成分をなすａ，ｂおよびｃが定まる（注：符号語ｃのｃはcodeを意味し、非零成分ｃとは異なる）。
【００２８】
かくして、Ｈｃ＝０が成立したとき符号語ｃが存在する。この場合、サイクルＣＬに相当する部分行列の行列式（determinant）、すなわちdet｜      ｜が０のときに限り、そのＨｃ＝０が成立する。この両者の関係を表したのが図２の両矢印である。
【００２９】
ところで図２において、行列の非零成分をＡ，Ｂ，Ｃ…のようにノンバイナリで表したが、これは本発明がノンバイナリ・パリティチェック行列を対象としているからであり、バイナリ・パリティチェック行列の場合は、上記Ａ，Ｂ，Ｃ…は１である。
【００３０】
ここで注意すべきことは、成分０および成分１からなるバイナリの場合、その行列式、すなわち図２の右側のdet｜      ｜は必ず０になることである。そうすると、図１のステップＳ13において述べた「行列式が０とならない」ような成分は存在しないことになる。
【００３１】
しかしノンバイナリの場合は、図３に示すように、det｜      ｜≠０を満足させるノンバイナリの非零成分（Ａ，Ｂ，Ｃ…）を選択することが可能となる。この着眼が本発明のポイントになる。
【００３２】
要するに、本発明におけるパリティチェック行列構成のアルゴリズムにおいては、列重み２のパリティチェック行列Ｈにおいて、サイクルＣＬで構成される行列Ｈが符号語ｃに対応すること、またその行列の行列式が０である場合のみに対応する符号語が存在することに注目し、パリティチェック行列内のサイクルを見つけ、その行列式が０にならないようにノンバイナリの非零成分を選択するようにしたものである。これにより、符号語ｃの最小の符号重みを大きくし、既述の復号特性（受信特性）の向上を図ることが可能になる。
【００３３】
図４は、本発明と従来例との間の復号特性の比較結果を示す図である。すなわち、本発明による優れた効果を明らかにするためのシミュレーション結果の一例を示す図である。
【００３４】
図４のグラフにおいて、縦軸は「ブロック誤り率」（ＢＬＥＲ）、横軸は「ビット当たりの信号電力対雑音電力密度比」（Eb／No）〔dB〕をそれぞれ示す。また本グラフの右上には、本比較結果を得たときのシミュレーションの条件を示す。すなわち、Additive White Gaussian Noise（ＡＷＧＮ）と、ＢＰＳＫ変調と、ＧＦ（16）すなわちノンバイナリ成分として１〜15と、を用いたシミュレーションである。
【００３５】
ここに、既述の従来例（ランダム選択法）に比較して、本発明によるとブロック誤り率（ＢＬＥＲ）がマイナス５乗の点において、0.1〜1.0dB程度の受信特性の向上が図れていることが分かる。さらに加えて、従来例を用いて生成されたノンバイナリ・パリティチェック行列を採用した場合、その受信特性がばらついている。しかし本発明によって生成されたノンバイナリ・パリティチェック行列を採用した場合には、その受信特性、すなわち復号特性にばらつきがなく、きわめて安定していることが分かる。
【００３６】
なお図４の中に示すＫ（＝Ｎ−Ｍ）は、符号化して送信すべき情報ビット（情報系列）のビット数、Ｎはその符号化後のシンボル数、Ｒは符号化率を示す。
【００３７】
次に本発明の実施態様に基づくパリティチェック行列の生成方法を具体的に説明する。図５は、本発明に基づくパリティチェック行列の生成方法を表すフローチャート（その１）であり、図６は同フローチャート（その２）である。また、図７は図５および図６の説明に用いるバイナリ・パリティチェック行列の一例を示す図であり、図８は図５および図６の説明に用いる本発明により完成したノンバイナリ・パリティチェック行列の一例を示す図である。
【００３８】
図５および図６を参照すると、そのフローチャートの全体のステップは、基本的に、図１に示す３つの「行列設定ステップ」Ｓ11、「検出ステップ」Ｓ12および「選択ステップ」Ｓ13の基本３ステップよりなるが、具体的にはさらに種々のステップからなる。次のとおりである。
【００３９】
ステップＳ21（図５）においては、列重み（各列の中に含まれる非零成分（バイナリの場合は１）の数）が２のバイナリ・パリティチェック行列を設定する。その一例を示すのが図７である。この行列設定ステップ（Ｓ11，Ｓ21）においては、上記バイナリ・パリティチェック行列は、既知のアルゴリズムにより生成された複数の公知のバイナリ・パリティチェック行列の中から選択して設定することができる。例えば、前記の文献に記載の行列等である。
【００４０】
ステップＳ22においては、図７の行列におけるＮの中のｉ番目の列に注目する。まず始めにｉ＝１すなわち第１列に注目する。
【００４１】
ステップＳ23においては、図７における第１列の１番目の行（ｉ＝１）の非零成分“１”について、その値をＧＦ（ｑ）の成分の中からランダムに、つまり任意に選択する。任意に選択したのは、後述するサイクルがまだ検出されていないからである。図８の例では、ｑ＝８であってＧＦ（８）であるから、１〜７の中の１つを全く勝手に選択する。図８の例によれば、そのｉ＝１、ｊ＝１の成分として“３”が選択されている。その後、ステップＳ23→Ｓ29→Ｓ23を、何回か繰り返したものとして、
ステップＳ24では、１列目からｉ列目までの間に作られる部分行列、つまり注目するｉ番目の列より左側に作られる部分行列について、その部分行列の中に含まれる長さＬ0（後述）以下のサイクルを全て検出する（ｉ列目より右側におけるサイクルには全く注目しない）。
【００４２】
このサイクルの検出については、例えば前述の図２を参照すると、前記検出ステップにおいて、成分Ａ，Ｂ，Ｃ…から構成されるノンバイナリ・パリティチェック行列内の複数の非零成分を行方向および列方向に沿って順次結んで一巡させてなるループをサイクルとして検出しているが、このステップＳ24では、図７のバイナリ・パリティチェック行列内におけるサイクルの検出を行うのでこの場合は、成分０および成分１から構成されるバイナリ・パリティチェック行列内の複数の成分１を行方向および列方向に沿って順次結んで一巡させてなるループをサイクルとして検出することになる。
【００４３】
このようなサイクルを形成するループが検出されるのは１つの行列内に１つとは限らず、複数検出されるのが普通である。このサイクルの長さとは、例えば図２を参照すると、ここに示すサイクルＣＬの長さは、６である。つまり、サイクルＣＬをなす線分ＡＢ、ＢＥ、ＥＦ、ＦＤ、ＤＣおよびＣＡの総和が、６である。
【００４４】
このようにして検出した各サイクルについてそれぞれ行列式＝０とならないように、非零成分の値を選択していくことになるが、検出した全てのサイクルについて、その行列式が０にならないようにすることができない場合が存在する。このような場合は、上記の長さを、予め定めた上限長以下に制限してしまう。ある程度、大きな符号語が得られれば十分だからである。なお、最初から上限長以下のサイクルのみを検出することによって手順の効率化を図ることもできる。
【００４５】
さらに定量的に表現すれば、サイクルの長さＬ0をその上限値とする。そしてこの上限長は、
Ｌmin＋２[(Ｌmin−２)/４]
により定める。ここに、Ｌminは、バイナリ・パリティチェック行列内に含まれるサイクルのうち最短のサイクルの長さを表し、［ ］は、Ｘについて［Ｘ］と表したときこの［Ｘ］は、Ｘを超えない整数であることを示す。なお、この上限値の式を導出した根拠については、本明細書の末尾に図13〜図16を参照して詳しく説明する。
【００４６】
以上、サイクルの検出について詳しく述べたが、
ステップＳ25（図６）においては、上記のサイクルが実際に検出されたか否か判定する。
【００４７】
ステップＳ26：ステップ25において、サイクルは検出されないと判定されたときは（No）、ｉ列目の列重み２に対応する２番目（図７のｉ＝１を例にとれば、ｉ＝１、ｊ＝４に位置する成分１）の非零成分についてその値をＧＦ（ｑ）（図８の行列を対象としているので、ｑ＝８）の成分（１〜７）の中からランダムに選択する。ランダムであるから全く勝手に選択すればよい。
【００４８】
このように、１つのサイクルの途中の全ての成分について全くランダムに選択してもよいのは、後述するステップＳ28において、未選択の最後の１つ成分のみを適切に選択しさえすれば、当該サイクルに相当する部分行列の行列式を０にすることができるからである。
【００４９】
要するに上記ステップＳ26においては、成分０および成分１から構成される図７のバイナリ・パリティチェック行列内において前述したサイクルをなす成分のうちの各成分１に対し、ノンバイナリ成分である多値（１〜７）のうちの１つを割り当てるように、選択ステップＳ13（図１）での選択を行うようにする。この場合、最後に未選択となって残った１つの成分１に至るまでの各成分１については、前記の多値のうちの１つをランダムに割り当てるようにする。
【００５０】
上記ステップＳ25に戻ると、ここで、サイクルが検出されたとすると（YES）、ステップＳ28に移行する。
【００５１】
ステップＳ28においては、ｉ列目の２番目の非零成分について、その値を全てのサイクルに対応する行列の行列式が０とならないようにＧＦ（ｑ）の成分（１〜７）の中から選択する。
【００５２】
要するに、図７の行列内の各成分１について順次、上記の多値（１〜７）のうちの１つを割り当てて前述した選択（Ｓ13）を実行し、未選択となって残った最後の１つの成分１についてその多値（１〜７）のうちの１つを割り当てる際にのみ、当該サイクルＣＬに対応する部分行列についての行列式det｜      ｜が０にならないように、その多値のうちの１つを選択するようにする。なお、全ての行列の行列式を０とすることができない場合には、小さいサイクルに対応する小さい行列を優先することとする。
【００５３】
この選択後ステップＳ27に移る。上記ステップＳ26の終了後も同じくステップ27に移る。
【００５４】
ステップＳ27：ステップＳ26またはＳ28において、図７のｉ列目における成分１に関し、図８に示すノンバイナリ非零成分を決定したならば、次の（ｉ＋１）列目に注目し、
ステップＳ29において、ｉ＞Ｎ（図７ではＮ＝16）とならない限り、上記ステップＳ23に戻って同じ動作を繰り返す。
【００５５】
以上の動作説明は、バイナリ・パリティチェック行列（図７）およびノンバイナリ・パリティチェック行列（図８）が共に、列重み２の行列である場合を好適例として、行ったが、列重みの全てが２でない（一部のみが列重み２）場合においても、列重みが２の列のみを対象にして本発明を適用することにより、列重み２でない列の割合が小さい場合には、一定の効果を期待することができる。
【００５６】
以上、本発明に基づくパリティチェック行列の生成方法について詳述したが、本発明の思想はパリティチェック行列生成装置としても実現することができる。その一例を以下に示す。
【００５７】
図９は、本発明に係るパリティチェック行列生成装置を示す図である。本図に表すとおり、パリティチェック行列生成装置10は、行列設定部11と、検出部12と、選択部13と、パリティチェック行列出力部14と、から構成される。上記各部（11〜13）の機能は、図１ならびに図５および図６において説明したとおりである。
【００５８】
このパリティチェック行列生成装置10は、ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成装置である。
【００５９】
ここに、行列設定部11は、ノンバイナリ・パリティチェック行列（図８）と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列（図７）を設定するものであり、検出部12は、上記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルＣＬを検出するものであり、選択部13は、上記のノンバイナリ・パリティチェック行列内において上記の検出されたサイクルＣＬに対応する部分行列についての行列式det｜      ｜が０にならないように、該部分行列内のノンバイナリ成分を選択するものである。
【００６０】
そしてパリティチェック行列出力部14において、上記の選択されたノンバイナリ成分によってノンバイナリ・パリティチェック行列内の非零成分（１〜７）を決定し、ノンバイナリ・パリティチェック行列を出力する。
【００６１】
以上説明した本発明に係るパリティチェック行列生成方法（図１）またはパリティチェック行列生成装置（図９）は、送信装置と受信装置との間で行われる情報通信に効果的に利用することができる。最も好適には、無線送信機と無線受信機とからなる無線通信システムにおける情報通信に利用することができる。そこで、これら無線の送信機および受信機について以下に説明する。
【００６２】
図10は、本発明に係るパリティチェック行列を利用した無線通信システムを示す図であり、上段は送信機20、下段は受信機40であり、両者（20，40）は無線チャネル30を介して接続される。
【００６３】
まず送信機20について見てみると、この送信機20は、符号化して送信すべき情報ビットIbを入力し、これをノンバイナリＬＤＰＣ符号により符号化するＬＤＰＣ符号化器22と、この符号化を行うに際して使用するノンバイナリ・パリティチェック行列を保持する符号化側パリティチェック行列保持部23と、そのＬＤＰＣ符号化器22からの符号化後の情報ビットIbを変調して受信側に送信する変調器25と、を含んでなる送信機である。
【００６４】
ここで注目すべき点は、符号化側パリティチェック行列保持部23が、本発明に基づくパリティチェック行列生成装置10（図９）により生成されたノンバイナリ・パリティチェック行列を保持することである。すなわち、既述したとおり、このパリティチェック行列生成装置10は、
（ｉ）ノンバイナリ・パリティチェック行列（図８）と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列（図７）を設定する行列設定部11と、
（ii）その設定されたバイナリ・パリティチェック行列（図７）内に含まれるサイクルＣＬを検出する検出部12と、
（iii）ノンバイナリ・パリティチェック行列（図８）内において前述の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部13と、
（iv）その選択されたノンバイナリ成分によってそのノンバイナリ・パリティチェック行列内の非零成分を決定し、ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部14と、からなる。
【００６５】
この送信機20は、さらに、バイナリビットである情報ビットIbをノンバイナリである多値シンボルに変換するために、ＬＤＰＣ符号化器22の入力側に設けられる入力側変換部21と、ＬＤＰＣ符号化器22により符号化された、ノンバイナリの多値シンボルからなる情報ビットを、バイナリビットに変換するために、ＬＤＰＣ符号化器22の出力側に設けられる出力側変換部24と、を備える。
【００６６】
上記入力側変換部21は、多値で動作するＬＤＰＣ符号化器22に、バイナリの情報ビットIbを整合させるために、ＧＦ（４）の場合を例にとると、
00→０
01→１
10→２
11→３
といった多値化変換をし（ＧＦ（２）→ＧＦ（４））、一方
上記出力側変換部24は、ＬＤＰＣ符号化器22からの多値の出力を、バイナリで動作させるために、同様に、ＧＦ（４）の場合を例にとると、
０→00
１→01
２→10
３→11
といった２値化変換をする（ＧＦ（４）→ＧＦ（２））。
【００６７】
図10の下段に示す受信機40について見てみると、これは、ノンバイナリＬＤＰＣ符号により符号化（22）され変調（25）して送信側（20）より送信された信号を受信し、これを復調する復調器41と、この復調器41からの尤度で表された復調ビットに対し、ノンバイナリＬＤＰＣ符号により復号を行うＬＤＰＣ復号器43と、この復号を行うに際して使用するノンバイナリ・パリティチェック行列を保持する復号側パリティチェック行列保持部44と、を含んでなる受信機である。
【００６８】
ここで注目すべき点は、復号側パリティチェック行列保持部43が、本発明に基づくパリティチェック行列生成装置10（図９）により生成されたノンバイナリ・パリティチェック行列を保持することである。すなわち、既述と同様、このパリティチェック行列生成装置10は、（ｉ）行列設定部11と、（ii）検出部12と、（iii）選択部13と、（iv）パリティチェック行列出力部14と、からなる。
【００６９】
この受信機40は、さらに、復調器41からの尤度で表されたバイナリの復調ビットを、ノンバイナリの多値シンボルに変換するために、ＬＤＰＣ復号器43の入力側に設けられる入力側変換部42と、ＬＤＰＣ復号器43により復号された、ノンバイナリの多値シンボルからなる情報ビットIbを、バイナリビットに変換するために、ＬＤＰＣ復号器43の出力側に設けられる出力側変換部45と、を備える。すなわちこの出力側変換部45は、
０→00
１→01
２→10
３→11
といった変換を行う（ＧＦ（４）→ＧＦ（２））。
【００７０】
一方、上記入力側変換部42は、その機能からして尤度変換部と称するのが適切である。これは、復調器41によって得られたバイナリ尤度をｑビット毎にひとまとめにして、それぞれ１シンボルのノンバイナリ尤度に変換するものである。例としてＧＦ（２）→ＧＦ（４）の変換は、
Ｑ0＝Ｐ00Ｐ10
Ｑ1＝Ｐ00Ｐ11
Ｑ2＝Ｐ01Ｐ10
Ｑ3＝Ｐ01Ｐ11
となる。ここで、Ｐ10は変換前の１ビット目が０である確率、Ｑ0は変換後のシンボルが０である確率などを表すものとする。このようにして得られたシンボル尤度を復号器43に入力するという構成とする。
【００７１】
この復号器43では、既述したタナーグラフにより、ＬＤＰＣ符号の復号が行われる。図11は公知のタナーグラフを図２のパリティチェック行列に対応させて示す図である。本図において、Ｖ0，Ｖ1，…Ｖ5は、いわゆるビットノードであり、Ｃ0，Ｃ1…Ｃ3はいわゆるチェックノードである。そのビットノードの各々に入力されるＦ0，Ｆ1…Ｆ5は、図10の復調器41から前述の尤度変換部（42）を経た復調結果である。図中の太線のＣＬ６は、図２に示したサイクルＣＬに対応している。その長さは６である。
【００７２】
次に図10に示す送信機20の変形態様について説明する。この変形態様は、ノンバイナリＬＤＰＣ符号の長所とバイナリＬＤＰＣ符号の長所とを上手に利用したものである。すなわち、情報ビットIbのようにコード長が比較的長くなり、このためにノンバイナリＬＤＰＣ符号を用いた場合とバイナリＬＤＰＣ符号を用いた場合とを比較してノンバイナリＬＤＰＣ符号を用いることによる受信特性の改善度合が低い場合には、あえてノンバイナリＬＤＰＣ符号を用いることなく、バイナリＬＤＰＣ符号による符号化を行う。
【００７３】
一方、セルラー網における制御情報や報知情報のように、コード長が短いが高品質（Ｑ0Ｓ）な通信が要求される情報については、専らノンバイナリＬＤＰＣ符号を用いる。上述の思想を図に表すと図12のようになる。
【００７４】
図12は、本発明に係るパリティチェック行列を利用した無線送信機20′を示す図である。なお、図10に示す構成要素と同様のものには、同一の参照番号または記号を付して示す。
【００７５】
総括的に表現すればこの送信機20′は、符号化して送信すべき送信情報が、コード長の長い第１送信情報（例えばIb）と、この第１送信情報よりも短いコード長であるがこの第１情報よりも高品質が要求される第２情報（例えば、IctやIbr）とを含むような送信機である。この送信機20′は、第１送信情報（Ib）を入力し、これをバイナリＬＤＰＣ符号により符号化するバイナリＬＤＰＣ符号化器26ｂと、第２送信情報（Ict，Ibr）を入力し、これをノンバイナリＬＤＰＣ符号により符号化するノンバイナリＬＤＰＣ符号化器（22ct，22br）と、バイナリＬＤＰＣ符号化器26ｂからの符号化出力を変調する第１変調器25ｂと、ノンバイナリＬＤＰＣ符号化器（22ct，22br）からの符号化出力を変調する第２変調器（25ct，25br）と、これら第１および第２変調器からの各変調出力を合成して受信側に送信する送信手段（28，29）と、を備える。
【００７６】
ここにノンバイナリＬＤＰＣ符号化器（22ct，22br）は、パリティチェック行列生成装置10（図９）によって生成されたノンバイナリ・パリティチェック行列により上記の符号化を行い、またそのパリティチェック行列生成装置は、既述のとおり、（ｉ）行列設定部11と、（ii）検出部12と、（iii）選択部13と、（iv）パリティチェック行列出力部14と、からなる。
【００７７】
具体的には、バイナリＬＤＰＣ符号化器26ｂは、上記の第１送信情報として無線通信における情報ビットIbを入力し、ノンバイナリＬＤＰＣ符号化器22ctは、上記の第２送信情報として無線通信における制御情報Ictを入力する。
【００７８】
またバイナリＬＤＰＣ符号化器26ｂは、上記の第１送信情報として無線通信における情報ビットIbを入力し、ノンバイナリＬＤＰＣ符号化器22brは、上記の第２送信情報として無線通信における報知情報Ibrを入力する。
【００７９】
さらにまた、バイナリビットである第２送信情報（Ict，Ibr）をノンバイナリである多値シンボルに変換するために、ＬＤＰＣ符号化器（22ct，22br）の入力側に設けられる入力側変換部（21ct，21br）と、ＬＤＰＣ符号化器（22ct，22br）により符号化された、ノンバイナリの多値シンボルからなる第２送信情報（Ict，Ibr）を、バイナリビットに変換するために、ＬＤＰＣ符号化器（22ct，22br）の出力側に設けられる出力側変換部（24ct，24br）と、を備える。
【００８０】
前述した送信手段（28，29）は、時間スイッチ28および送信アンテナ29からなり、この送信アンテナ29から送信された符号化情報は受信機（図10の40に相当）に送信され、この受信機において上記の第１送信情報（Ib）と第２送信情報（Ict，Ibr）が受信され、時間スイッチで分離されたこれらの情報は、対応する復号器（図10の43に相当）にてそれぞれ個別に再生される。
【００８１】
最後に、前述した上限長が、
Ｌmin＋２[(Ｌmin−２)/４]
で導出される根拠について、詳しく説明する。
【００８２】
図13は、上限長の算出式の根拠を説明するための図（その１）、
図14は同図（その２）、
図15は同図（その３）、
図16は同図（その４）であり、
これらの図を参照しながら説明する。
【００８３】
列重みが２のレギュラーＬＤＰＣ符号について考える。前述したとおり、対応する部分行列の行列式が０であるようなサイクルは対応する符号語を持つ。しかし、全ての符号語がサイクルに対応するわけではなく、符号語はサイクルに対応する符号語（サイクル符号語）とサイクルに対応しない符号語（非サイクル符号語）の２種類に分類される。例えば、図13のような（部分）パリティチェック行列Ｈは対応する（非サイクル）符号語を持つ。つまり、Ｈｃ＝０となるようなベクトルｃが存在する。一般的には、あるパリティチェック行列の全ての行の重みが２以上で、かつＮ＞Ｍであれば必ず対応する符号語が存在する。このようなパリティチェック行列は必ずその内部にサイクルを含む。図13においては、内部に含まれているサイクルＣＬが図示されている。
【００８４】
本発明は、長さの短いサイクルに対応する重みが小さい符号語が存在しないように、ノンバイナリＬＤＰＣ符号のパリティチェック行列の成分を選択するアルゴリズムを提供するものであることについて前述したが、ある長さ以上のサイクルに対してこのアルゴリズムを適用したとしても、それ以下の重みの非サイクル符号語が存在する場合には、これを適用するメリットがなくなる。
【００８５】
そこで、本発明のアルゴリズムを適用することにより回避されるサイクル符号語の最大重みは、非サイクル符号語の最小重みより１つ小さいものとすれば十分であることが分かる。この非サイクル符号語の最小重みを求めるために、列重みが２のレギュラーＬＤＰＣ符号において、符号語に対応する部分パリティチェック行列は必ずサイクルを内部に含むという事実を利用する。また、問題を考えやすくするために、図14および図15のようなチャートを利用する。図14および図15において、丸はビットノードを表し、四角はチェックノードを表す。
【００８６】
まず、最小長さ（Ｌmin＝２ｋ）のサイクルに対応するチャートを作成する（図14および図15のそれぞれの上半分に対応）。その後、これらの図に示されているように、サイクルの一番下に位置するチェックノードから、ビットノード→チェックノードの順にチャートを広げていくことによって、より大きいチャートを作成する。このようなチャートにおいて、サイクルの最小長さより小さいサイクルができないように、かつ全てのビットノードおよびチェックノードに接続しているエッジの数が２以上になるように作成した最も小さいチャートが、最小の非サイクル符号語に対応する部分パリティチェック行列に対応したチャートとなる。例えば、図13のパリティチェック行列Ｈに対応するチャートは図16のようになり、このチャート中に含まれているビットノードの数（＝パリティチェック行列の列数）は５となる。つまり、最小の非サイクル符号語の重みは５となることが分かる。
【００８７】
したがって、この場合、本発明のアルゴリズムは、重み５の符号語に対応するサイクル（長さ10）よりも短いサイクルに適用されるべきである。すなわち、考慮するサイクルの最大長さは８となる。これを一般化すると、図16に示されているように、Ｌmin＝２ｋとして、ｋが偶数の場合と奇数の場合で分けて考えることにより、偶数の場合のビットノードの個数は３ｋ／２個、奇数の場合は（３ｋ＋１）／２個となり、考慮しなければならないサイクルの上限長はそれぞれ、３ｋ−１および３ｋとなることが分かる。ここで、Ｌmin＝２ｋを代入して、ｋが奇数の場合と偶数の場合とをまとめて考えると、問題としている上限長は、
Ｌ0＝Ｌmin＋２[(Ｌmin−２)/４]
として導出される。
【００８８】
以上詳述した本発明の実施態様は以上のとおりである。
【図面の簡単な説明】
【００８９】
【図１】図１は、本発明に係るパリティチェック行列生成方法の基本ステップを示すフローチャート。
【図２】図２は、本発明の理解を早めるための、サイクルと符号語の関係を表す図。
【図３】図３は、本発明における、サイクルと符号語の関係を表す図。
【図４】図４は、本発明と従来例との間の復号特性の比較結果を示す図。
【図５】図５は、本発明に基づくパリティチェック行列生成方法の具体例を示すフローチャート（その１）。
【図６】図６は、本発明に基づくパリティチェック行列生成方法の具体例を示すフローチャート（その２）。
【図７】図７は、図５および図６の説明に用いるバイナリ・パリティチェック行列の一例を示す図。
【図８】図８は、図５および図６の説明に用いる本発明により完成したノンバイナリ・パリティチェック行列の一例を示す図。
【図９】図９は、本発明に係るパリティチェック行列生成装置を示す図。
【図１０】図10は、本発明に係るパリティチェック行列を利用した無線通信システムを示す図。
【図１１】図11は、公知のタナーグラフを図２のパリティチェック行列に対応させて示す図。
【図１２】図12は、本発明に係るパリティチェック行列を利用した送信機を示す図。
【図１３】図13は、上限長の算出式の根拠を説明するための図（その１）。
【図１４】図14は、上限長の算出式の根拠を説明するための図（その２）。
【図１５】図15は、上限長の算出式の根拠を説明するための図（その３）。
【図１６】図16は、上限長の算出式の根拠を説明するための図（その４）である。
【図１】
2009531885.tif 000003
【図２】
2009531885.tif 000004
【図３】
2009531885.tif 000005
【図４】
2009531885.tif 000006
【図５】
2009531885.tif 000007
【図６】
2009531885.tif 000008
【図７】
2009531885.tif 000009
【図８】
2009531885.tif 000010
【図９】
2009531885.tif 000011
【図１０】
2009531885.tif 000012
【図１１】
2009531885.tif 000013
【図１２】
2009531885.tif 000014
【図１３】
2009531885.tif 000015
【図１４】
2009531885.tif 000016
【図１５】
2009531885.tif 000017
【図１６】
2009531885.tif 000018
【手続補正書】
【提出日】平成20年10月1日(2008.10.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成方法であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定ステップと、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出ステップと、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択ステップと、を有し、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を構成するパリティチェック行列生成方法。
【請求項２】
前記行列設定ステップにおいて、前記バイナリ・パリティチェック行列は、既知のアルゴリズムにより生成された複数のバイナリ・パリティチェック行列の中から選択して設定する請求項１に記載のパリティチェック行列生成方法。
【請求項３】
前記検出ステップにおいて、成分０および成分１から構成される前記バイナリ・パリティチェック行列内の複数の成分１を行方向および列方向に沿って順次結んで一巡させてなるループを前記サイクルとして検出する請求項１に記載のパリティチェック行列生成方法。
【請求項４】
前記検出ステップにおいて、検出するループの長さを、予め定めた上限長以下に制限する請求項３に記載のパリティチェック行列生成方法。
【請求項５】
成分０および成分１から構成される前記バイナリ・パリティチェック行列内において前記サイクルをなす成分のうち各該成分１に対し、前記ノンバイナリ成分である多値のうちの１つを割り当てるように、前記選択ステップでの選択を行う請求項１に記載のパリティチェック行列生成方法。
【請求項６】
各前記成分１について順次、前記多値のうちの１つを割り当てて前記の選択を実行し、未選択となって最後に残った１つの該成分１についてその多値のうちの１つを割り当てる際にのみ、当該サイクルに対応する前記部分行列についての行列式が０にならないようにその多値のうちの１つを選択する請求項５に記載のパリティチェック行列生成方法。
【請求項７】
前記バイナリ・パリティチェック行列および前記ノンバイナリ・パリティチェック行列が共に、列重み２の行列である請求項１に記載のパリティチェック行列生成方法。
【請求項８】
ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成装置であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０にならないように、該部分行列内のノンバイナリ成分を選択する選択部と、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置。
【請求項９】
符号化して送信すべき情報ビットを入力し、これをノンバイナリＬＤＰＣ符号により符号化するＬＤＰＣ符号化器と、
前記の符号化を行うに際して使用するノンバイナリ・パリティチェック行列を保持する符号化側パリティチェック行列保持部と、
前記ＬＤＰＣ符号化器からの符号化後の前記情報ビットを変調して受信側に送信する変調器と、を含んでなる送信機であって、
前記符号化側パリティチェック行列保持部は、パリティチェック行列生成装置により生成されたノンバイナリ・パリティチェック行列を保持し、ここに、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii ）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、送信機。
【請求項１０】
ノンバイナリＬＤＰＣ符号により符号化され変調して送信側より送信された情報ビットを受信し、これを復調する復調器と、
前記復調器からの対数尤度で表された復調ビットに対し、ノンバイナリＬＤＰＣ符号により復号を行うＬＤＰＣ復号器と、
前記の復号を行うに際して使用するノンバイナリ・パリティチェック行列を保持する復号側パリティチェック行列保持部と、を含んでなる受信機であって、
前記復号側パリティチェック行列保持部は、パリティチェック行列生成装置により生成されたノンバイナリ・パリティチェック行列を保持し、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii ）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、受信機。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
以上詳述した本発明の実施態様は以下のとおりである。
（付記１）ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成方法であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定ステップと、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出ステップと、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択ステップと、を有し、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を構成するパリティチェック行列生成方法。
（付記２）前記行列設定ステップにおいて、前記バイナリ・パリティチェック行列は、既知のアルゴリズムにより生成された複数のバイナリ・パリティチェック行列の中から選択して設定する付記１に記載のパリティチェック行列生成方法。
（付記３）前記検出ステップにおいて、成分０および成分１から構成される前記バイナリ・パリティチェック行列内の複数の成分１を行方向および列方向に沿って順次結んで一巡させてなるループを前記サイクルとして検出する付記１に記載のパリティチェック行列生成方法。
（付記４）前記検出ステップにおいて、検出するループの長さを、予め定めた上限長以下に制限する付記３に記載のパリティチェック行列生成方法。
（付記５）前記上限長は、
Ｌmin＋２[(Ｌmin−２)/４]
であり、ここに、
Ｌminは、前記バイナリ・パリティチェック行列内に含まれる前記サイクルのうち最短のサイクルの長さを表し、
［ ］は、Ｘについて［Ｘ］と表したときこの［Ｘ］は、Ｘを超えない整数であることを示す、
付記４に記載のパリティチェック行列生成方法。
（付記６）成分０および成分１から構成される前記バイナリ・パリティチェック行列内において前記サイクルをなす成分のうち各該成分１に対し、前記ノンバイナリ成分である多値のうちの１つを割り当てるように、前記選択ステップでの選択を行う付記１に記載のパリティチェック行列生成方法。
（付記７）各前成分１について順次、前記多値のうちの１つを割り当てて前記の選択を実行し、未選択となって最後に残った１つの該成分１についてその多値のうちの１つを割り当てる際にのみ、当該サイクルに対応する前記部分行列についての行列式が０にならないようにその多値のうちの１つを選択する付記６に記載のパリティチェック行列生成方法。
（付記８）前記の最後に未選択となって残った１つの成分１に至るまでの各成分１については、前記の多値のうちの１つをランダムに割り当てる付記７に記載のパリティチェック行列生成方法。
（付記９）前記バイナリ・パリティチェック行列および前記ノンバイナリ・パリティチェック行列が共に、列重み２の行列である付記１に記載のパリティチェック行列生成方法。
（付記10）ノンバイナリＬＤＰＣ符号を定義するノンバイナリ・パリティチェック行列を生成するためのパリティチェック行列生成装置であって、
前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、
前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、
前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０にならないように、該部分行列内のノンバイナリ成分を選択する選択部と、
前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置。
（付記11）符号化して送信すべき情報ビットを入力し、これをノンバイナリＬＤＰＣ符号により符号化するＬＤＰＣ符号化器と、
前記の符号化を行うに際して使用するノンバイナリ・パリティチェック行列を保持する符号化側パリティチェック行列保持部と、
前記ＬＤＰＣ符号化器からの符号化後の前記情報ビットを変調して受信側に送信する変調器と、を含んでなる送信機であって、
前記符号化側パリティチェック行列保持部は、パリティチェック行列生成装置により生成されたノンバイナリ・パリティチェック行列を保持し、ここに、
該パリティチェック行列生成装置は、（ｉ）前記ノンバイナリ・パリティチェック行列と同一構成を有する、バイナリＬＤＰＣ符号のバイナリ・パリティチェック行列を設定する行列設定部と、（ii）前記の設定されたバイナリ・パリティチェック行列内に含まれるサイクルを検出する検出部と、（iii ）前記ノンバイナリ・パリティチェック行列内において前記の検出されたサイクルに対応する部分行列についての行列式が０とならないように、該部分行列内のノンバイナリ成分を選択する選択部と、（iv）前記の選択されたノンバイナリ成分によって前記ノンバイナリ・パリティチェック行列内の非零成分を決定し、前記ノンバイナリ・パリティチェック行列を出力するパリティチェック行列出力部と、からなるパリティチェック行列生成装置である、送信機。
（付記12）バイナリビットである前記情報ビットをノンバイナリである多値シンボルに変換するために、前記ＬＤＰＣ符号化器の入力側に設けられる入力側変換部と、
前記ＬＤＰＣ符号化器により符号化された、ノンバイナリの多値シンボルからなる前記情報ビットを、前記バイナリビットに変換するために、前記ＬＤＰＣ符号化器の出力側に設けられる出力側変換部と、を備える付記11に記載の送信機。
【国際調査報告】
2009531885.tif 000019
2009531885.tif 000020