(57)【要約】  ブロックコヒーレント通信システム上での通信のための方法および装置が記載される。本発明は、符号、例えば、ずっと小さいグラフの多重の同一のコピーで主として構成されるグラフ構造を有するＬＤＰＣ符号によりエンコードされる符号化ビットをインタリーブする方法に関する。
2007525058.tif 000002
【特許請求の範囲】
【請求項１】
複数のＺベクトルを処理する方法であって、各ＺベクトルはＺ要素を含み、各要素はＫビットを含み、ここでＺは１より大きい正の整数であり、Ｋは０より大きい正の整数であり、複数のＺベクトルは１つの２進符号語に対応しており、前記２進符号語のいくつかの部分は、複数の送信単位への直接的マッピング関係を有しており、前記複数のＺベクトルは、Ｄメモリーアレイの組の中に保存されており、ここでＤは０より大きい整数であり、各メモリーアレイはＺ行のメモリー位置を含んでおり、１つの行の各メモリー位置は異なるアレイ列に対応しており、各アレイ列は前記複数のＺベクトルの別の１つに対応し、各Ｚベクトルは前記Ｄメモリーアレイの各々における１つの列を識別し、この方法は、
制御情報の一連の組を生成し、制御情報の各組は、
ｉ）  送信単位識別子と、
ｉｉ）  Ｚベクトル識別子と、
ｉｉｉ）  行識別子とを含み、また
少なくとも１つの生成された制御情報の組について、
前記少なくとも１つの生成された制御情報の組中に含まれるＺベクトル識別子により識別されたＺベクトルにより識別された各列から、Ｄビットで除算されたＫをＰ（Ｐは、０より大きい正の整数）回読み取ることを含む方法。
【請求項２】
前記処理方法は、前記送信単位の送信に先だって送信機器により実行され、
Ｄは１であり、
Ｋは１である請求項１に記載の方法。
【請求項３】
前記少なくとも１つの生成された制御情報の組について、
メモリーから読み取られた前記Ｐビットから、前記少なくとも１つの生成された制御情報の組中に含まれる送信単位識別子により識別された送信単位の一部を生成することをさらに含む請求項２に記載の方法。
【請求項４】
前記複数のＺベクトルは、前記複数のＺベクトルのうちのｎを含み、ｎは１より大きい正の整数であり、
制御情報の一連の組を生成することは、
Ｚベクトル識別子値を、Ｍで除算されたｎだけ増分することをさらに含み、Ｍは、２進符号語の一部への直接的マッピング関係を有する送信単位の部分の数であり、２進符号語の前記部分はＰビットのＭ倍を含む請求項３に記載の方法。
【請求項５】
送信単位の各部分は１つのシンボルであり、
送信単位は１つのドウェルである請求項４に記載の方法。
【請求項６】
制御情報の一連の組を生成することは、
Ｚベクトル識別子値をＭ回増分し、
Ｚベクトル値をＭ回増分した後、
ｉ）  Ｚベクトル識別子値を、前記増分ステップ開始時点に存在するＺベクトル識別子値にリセットし、
ｉｉ）  行識別子値をＰだけ増分することをさらに含む請求項３に記載の方法。
【請求項７】
制御情報の一連の組を生成することは、
Ｐ回で除算された行識別子値Ｚを増分した後（Ｐ回で除算されたＺは整数）、
行識別子値を０に設定し、
Ｚベクトル識別子値を、予め選択された正の整数値だけ増分することとをさらに含む請求項６に記載の方法。
【請求項８】
前記予め選択された正の整数値は１である請求項７に記載の方法。
【請求項９】
前記２進符号語は低密度パリティチェック符号語である請求項２に記載の方法。
【請求項１０】
前記処理方法は受信された送信単位を処理するために用いられ、
Ｋは０より大きい整数であり、前記２進符号語の１ビットに対応するソフト値を表すために用いられるビットの数である請求項１に記載の方法。
【請求項１１】
ＤはＫまたは１に等しい請求項１０の方法。
【請求項１２】
前記少なくとも１つの生成された制御情報の組について、
メモリーから読み取られたＰビットを復調器に供給することをさらに含む請求項１１に記載の方法。
【請求項１３】
前記少なくとも１つの生成された制御情報の組について、
メモリーから読み取られた前記Ｐビットから、前記生成された制御情報中の各組に含まれる送信単位識別子により識別される送信単位の一部を生成することをさらに含む請求項１０に記載の方法。
【請求項１４】
前記複数のＺベクトルは前記Ｚベクトルのうちのｎを含み、ｎは１より大きい正の整数であり、
制御情報の一連の組を生成することは、
Ｚベクトル識別子値を、Ｍで除算されたｎだけ増分することをさらに含み、Ｍは、２進符号語の一部へのマッピング関係を有する送信単位の部分の数であり、２進符号語の前記部分はＰビットのＭ倍を含む請求項１３に記載の方法。
【請求項１５】
制御情報の一連の組を生成することは、
行識別子値を、Ｚベクトル識別子値をＭ回増分するＰだけ増分し、
Ｚベクトル値をＭ回増分した後、
ｉ）  Ｚベクトル識別子値を、前記増分開始時点に存在するＺベクトル識別子値にリセットし、
ｉｉ）  行識別子値をＰだけ増分することをさらに含む請求項１３に記載の方法。
【請求項１６】
制御情報の一連の組を生成することは、
Ｐ回で除算された行識別子値Ｚを増分した後（Ｐ回で除算されたＺは整数）、
行識別子値を０に設定し、
Ｚベクトル識別子値を、予め選択された正の整数値だけ増分することとをさらに含む請求項１５に記載の方法。
【請求項１７】
前記予め選択された正の整数値は１である請求項１６に記載の方法。
【請求項１８】
前記２進符号語は低密度パリティチェック符号語である請求項１０に記載の方法。
【請求項１９】
複数のＺベクトルを処理する装置であって、各ＺベクトルはＺ要素を含み、各要素はＫビットを含み、ここでＺは１より大きい正の整数であり、Ｋは０より大きい正の整数であり、複数のＺベクトルは１つの２進符号語に対応しており、前記２進符号語のいくつかの部分は、複数の送信単位への直接的マッピング関係を有しており、前記装置は、
前記複数のＺベクトルを保存するためのＤメモリーアレイの組を含むメモリーであって、ここでＤは０より大きい整数であり、各メモリーアレイはＺ行のメモリー位置を含んでおり、１つの行の各メモリー位置は異なるアレイ列に対応しており、各アレイ列は前記複数のＺベクトルの別の１つに対応し、各Ｚベクトルは前記Ｄメモリーアレイの各々の中の１つの列を識別するメモリーと、
制御情報の一連の組を生成するためのメモリーアクセス制御モジュールであって、制御情報の各組は、
ｉ）  送信単位識別子と、
ｉｉ）  Ｚベクトル識別子と、
ｉｉｉ）  行識別子とを含むメモリーアクセス制御モジュールと、
Ｚベクトルにより識別された各列から、前記メモリーからのＤビットで除算されたＫをＰ（Ｐは、０より大きい正の整数）回読み取り、このＺベクトルは少なくとも１つの生成された制御情報の組中に含まれるＺベクトル識別子により識別される手段とを含む装置。
【請求項２０】
Ｄは１であり、
Ｋは１である請求項１に記載の方法。
【請求項２１】
前記メモリーアクセス制御モジュールは、
前記Ｚベクトル識別子を生成するための第１のカウンタと、
前記行識別子を生成するための第２のカウンタとを含む請求項１９に記載の方法。
【請求項２２】
複数のＺベクトルを処理するためコンピュータ機器を制御する機械実行可能命令を含む機械可読媒体であって、各ＺベクトルはＺ要素を含み、各要素はＫビットを含み、ここでＺは１より大きい正の整数であり、Ｋは０より大きい正の整数であり、複数のＺベクトルは１つの２進符号語に対応しており、前記２進符号語のいくつかの部分は、複数の送信単位への直接的マッピング関係を有しており、前記機械実行可能命令は、コンピュータ機器を制御するために用いられる命令を含み、
制御情報の一連の組を生成するため、制御情報の各組が、
ｉ）  送信単位識別子と、
ｉｉ）  Ｚベクトル識別子と、
ｉｉｉ）  行識別子とを含むとともに、
少なくとも１つの生成された制御情報の組について、
前記少なくとも１つの生成された制御情報の組中に含まれるＺベクトル識別子により識別されたＺベクトルにより識別された各列から、Ｄビットで除算されたＫをＰ（Ｐは、０より大きい正の整数）回読み取るための機械可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロックコヒーレントなチャネル上でのデータ通信のための方法および装置に関し、より具体的には、パリティチェック符号、例えば、低密度パリティチェック（ＬＤＰＣ）符号により符号化されたデータビットにアクセスおよび／またはこれをインタリーブするための方法および装置に関する。
【背景技術】
【０００２】
瞬間チャネル利得（大きさおよび、特に、位相）について受信機が信頼できる評価を維持することが実行不可能である場合に、通信システムはノンコヒーレント検出を必要とする。ノンコヒーレント通信システムとしては、例えば、限定されたパワーを有する移動体が、信頼し得るチャネル評価を可能にするための高パワーの既知のシンボル（パイロット）を送信するだけの余裕がない無線多重アクセスシステムが含まれる。ノンコヒーレント通信チャネルは、いくつかのコヒーレンス特性を有することがある。すなわち、コヒーレントブロックは、チャネル変動がその間無視できるほど小さい時間間隔である。そのようなチャネル上での通信は、ブロックコヒーレント通信と呼ばれる。
【０００３】
ブロックコヒーレント通信は、高速周波数ホッピング直交周波数分割多重（ＯＦＤＭ）アクセスシステムにおいて自然に生じ得る。そのようなシステムにおいて、情報は、すべてのシンボル時間において、トーンと呼ばれる利用可能な周波数のサブセット上へ変調され得る。スペクトル効率を高め、ダイバーシチ利得を増大するため、利用されるトーンは、場合によっては、Ｌ個のシンボルすべてにおいて利用される周波数帯全体にわたって高速でホップされ、すなわち、Ｌ個の連続するシンボルが１つのトーンにマッピングされ、続いて別のＬ個のシンボルが他のトーンにマッピングされ、以下同様である。Ｌが小さい場合、連続するＬ個のシンボルは、同一のチャネル利得を経ると仮定できる。２つの連続するＬ個のシンボルの利得の大きさが近いことがあり得るが、通常それらの位相は完全に独立している。
【０００４】
より正確には、ブロックコヒーレント通信システムは、以下のように定義し得る。すなわち、離散的時間領域において表されるシステムについて、チャネル利得は、未知の複雑なランダム変数であり、このランダム変数は、Ｌ個の連続するシンボルすべてについて同じままであるが、そうでなければ、何らかの分布に従って独立して変動、例えば、位相は［０，２ＰＩ］にわたって均一に分布され、大きさはレイリー分布される。
【０００５】
ブロックコヒーレント通信については、公称変調方式は、差動Ｍ−アレイ位相シフトキーイング（ＤＭＰＳＫ）である。ＤＭＰＳＫは、コヒーレントブロック上で２つの連続するシンボル間の位相差中で情報を伝える。例として、Ｎ×（Ｌ−１）のＭＰＳＫ情報シンボルｓ（ｉ）を送信するため、ｓ（１），ｓ（２），．．．，ｓ（Ｌ−１）として表されるＬ−１個のシンボルのＮ個の連続する組の各々は、送信されたシンボルｔ（１），ｔ（２），．．．，ｔ（Ｎ）に差動的にエンコードされ、ここでｔ（１）＝１であり、ｊ＝１，．．．，Ｎ−１についてｔ（ｊ＋１）＝ｔ（ｊ）×ｓ（ｊ）である。
【０００６】
ＤＭＰＳＫ以外の変調が可能である。例えば、既知のシンボルをブロックに挿入すると、情報シンボルは、他のシンボル上で差動的でなく直接的に送信し得る。これは擬似パイロット変調と呼ぶことができる。しかしながら、位相不確定性のためにせいぜいＬ−１の情報シンボルが長さＬのドウェル内で送信し得ることが明白である。一般に、各ドウェル内でＭ個の情報シンボルが送信されると仮定し、これは送信単位と見なすことができる。言い換えれば、各送信単位は、Ｌ−Ｍの既知のシンボルを含んでいる。ＭはせいぜいＬ−１である。例えば、言及された両方の方式は、Ｍ＝Ｌ−１を有する。
【０００７】
順方向誤り訂正符号化を用いると、ブロックコヒーレント通信システムは通常、エンコーダ（オリジナルのデータストリーム中に、構造化冗長性を挿入する）、ＤＭＰＳＫ変調器（２進データビットをＭＰＳＫシンボルへマッピングする）、復調器（ソフト情報を差動的に抽出し、それをデコーダに供給する）、およびデコーダ（復調器からのソフト情報に基づいてオリジナルメッセージをデコードする）を含んでいる。
【０００８】
ほとんどの符号化されたシステムにおいて、反復復調および復号−今後はターボ等化と呼ぶ−を適用する受信機は、非反復受信機と比較して大きな性能利得を有する。例えば、ＩＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ２０００において発表された“Ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ  ｆｏｒ  ｃｏｄｅｄ  ｎｏｎｃｏｈｅｒｅｎｔ  ＭＰＳＫ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｖｅｒ  ｐｈａｓｅ−ｎｏｉｓｙ  ＡＷＧＮ  ｃｈａｎｎｅｌ”においてＳｈａｍａｉらにより研究された畳み込みおよび／またはターボ符号化ＤＭＰＳＫシステムは、１．３ｄＢのチャネル容量以内であり従来方式よりも１ｄＢ優れているターボ等化性能を示す。
【０００９】
ターボ等化が最高に効果的になるためには、符号デザインが、反復復調の効果を考慮に入れる必要があることが示されている。符号デザインの必要性およびそれを達成する効果的な方法は、Ｉｎｔｅｒｎａｔｉｏｎａｌ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｙ  Ｊｕｎｅ  ３０  ２００２において発表されたＪｉｎおよびＲｉｃｈａｒｄｓｏｎの論文“Ｄｅｓｉｇｎ  ｏｆ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ  ｉｎ  Ｎｏｎｃｏｈｅｒｅｎｔ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ”に記載されている。そこでのアプローチは、性能をチャネル容量０．７ｄＢ以内まで改善する。
【００１０】
ターボ等化の最適性能のためには、符号化ビットも、送信において十分にインタリーブされるべきである。インタリービングは、２つの目的に役立つ。一方では、インタリービングは、復号目的のためのブロック構造中の小さい距離の符号化ビットと関連したソフトメッセージ間の相関関係を効果的に除去することができる。他方では、インタリービングは、復調のために同じコヒーレントブロックにフィードバックされるメッセージ間の依存性を除去することができる。通常考えられるインタリービング構造は、ランダムインタリービングである。しかしながら、ランダムインタリービングを達成するためには、同じ（ランダムに生成された）並べ替えがアクセス可能、例えば、送信機および受信機双方に保存されていなければならない。これは、大きなブロック符号により符号化された実際のシステムについて大きなメモリー要件を負わせる。
【００１１】
広範囲の機器、例えば、消費者機器における使用について通信システムが実用的であるためにターボ等化の性能が重要である一方で、ターボ等化が妥当なコストで実装され得ることが重要である。従って、ブロックコヒーレント通信システムのために用いられるターボ等化方式を、例えば、ハードウェアコストの点で、効率的に実装する能力が重要になり得る。
【００１２】
ブロックコヒーレント通信における符号化方式としてのＬＤＰＣ符号の使用は、その近容量（ｎｅａｒ  ｃａｐａｃｉｔｙ）符号化利得および豊富なデザイン余地を考えれば、望ましい。
【００１３】
ＬＤＰＣ符号は、タナーグラフと呼ばれる２部構成のグラフにより表されることがよくあり、そこでは、一方のノードの組、すなわち可変ノード、が符号語のビットに対応し、他方のノードの組、すなわち検査ノードと呼ばれることがある制約ノードが、符号を定義するパリティチェック制約の組に対応する。グラフ中のエッジが可変ノードを制約ノードに接続する。可変ノードおよび制約ノードは、もしこれらがグラフ中のエッジにより接続されるのであれば、隣接すると言われる。単純にするため、１対のノードがせいぜい１つのエッジにより接続されると一般に仮定する。
【００１４】
可変ノードと１対１で関連付けられたビットシーケンスは、各制約ノードについて、制約に（可変ノードとのそれらの関連付けを介して）隣接するビットが、０モジュロ２になる、すなわち、それらが偶数のビットを含む場合、かつその場合に限り、符号の符号語である。
【００１５】
ノード、すなわち、可変ノードまたは制約ノードに属するエッジの数は、ノードの次数と呼ばれる。正則グラフまたは符号は、それについてすべての可変ノードが同じ次数、例えばｊを有し、すべての制約ノードが同じ次数、例えばｋを有するものである。この場合、その符号は、（ｊ，ｋ）正則符号であると言う。これらの符号は、もともとＧａｌｌａｇｅｒ（１９６１）により発明された。「正則」符号と対照的に、不規則符号は、次数が異なる制約ノードおよび／または可変ノードを有する。例えば、いくつかの可変ノードは次数４であり、他のものは次数３であり、さらに他のものは次数２であり得る。
【００１６】
不規則符号は表現および／または実装がより複雑であり得る一方で、正則ＬＤＰＣ符号と比較した場合に、不規則ＬＤＰＣ符号はより優れた誤り訂正／検出性能を提供できることが示されている。
【００１７】
長さ１０およびレート２分の１の（３，６）正則ＬＤＰＣ符号を決定する代表的な２部構成のグラフ２００が図２に示してある。長さ１０は、符号語Ｘ１−Ｘ１０の１ビットで各々識別される１０個の可変ノードＶ１−Ｖ１０があることを示し、可変ノードの組Ｖ１−Ｖ１０は、図２において参照番号２０２により一般に識別される。レート２分の１は、可変ノードの半分の検査ノードがあること、すなわち、参照番号２０６により識別される５つの検査ノードＣ１−Ｃ５があることを示す。レート２分の１は、以下で論じられるように、５つの制約が直線的に独立であることをさらに示す。
【００１８】
長さ１０の符号と関連付けられたグラフを図２が例示している一方で、長さ１０００の符号語についてのグラフを表すことが１００倍複雑であろうことが理解され得る。
【００１９】
実装コストを考慮して、ターボ等化により提起された実際的な課題は、ソフトイン・ソフトアウト（ＳＩＳＯ）復調器の複雑さと、送信機および受信機におけるデータインタリービングである。改善されたインタリービング手法および／または実装の必要性が残っている。本発明は、効率的なやり方でインタリーブを実装することに関する。本発明のインタリービング手法は、例えば、低密度パリティチェック（ＬＤＰＣ）符号によりエンコードされたデータビットと共に使用するのに適している。
【発明の開示】
【課題を解決するための手段】
【００２０】
本発明は、ブロックコヒーレントチャネル上でのデータ通信のための方法および装置に関する。単純にするために、１つのコヒーレント間隔中に送信されるシンボルをドウェル（ｄｗｅｌｌ）と呼ぶ。ドウェルの長さはＬである。ドウェルのシンボルは、情報送信単位として働き、これは、Ｍ個の情報シンボルおよび（Ｌ−Ｍ）個の既知シンボルを含む。各情報シンボルは、符号語中のＰビットからマッピングされたシンボルである。
【００２１】
本発明は、送信機において、メモリーを全く使用しないか比較的少ないメモリーを使用して、エンコーダと変調器との間で符号化ビットを代数的にインタリービングするための方法および装置に関する。本発明は、受信機において、メモリーを全く使用しないか比較的少ないメモリーを使用して、デコーダと復調器との間でソフトメッセージを代数的にインタリービングするための方法および装置にも関する。
【００２２】
本発明を説明する目的で、変調型としてＱＰＳＫを仮定する。この仮定では、１つの送信シンボルは、２つの符号化ビット−ダイビットを使用する。しかしながら、本発明において記載される手法は、容易に一般化でき、高次数変調方式、例えば、ＭＰＳＫまたはＱＡＭに適用可能であり、そのような実装は本発明の範囲内であると考えられる。
【００２３】
代数的インタリービングの本発明は、特定の階層構造を有するＬＤＰＣ符号によってエンコードされたデータビットに関し、その階層構造においては、フルＬＤＰＣグラフは、大部分、Ｚ倍小さいグラフの多重コピー、例えばＺ、で構成されるように見える。
【００２４】
Ｚグラフコピーは同一であってもよい。正確に言うと、より小さいグラフを投影グラフと呼ぶ。Ｚ平行エッジをベクトルエッジと呼び、Ｚ平行ノードをベクトルノードと呼ぶ。参照により明確に組み込まれる、２００１年１０月１０日提出の「ＬＤＰＣ符号エンコーディングおよびデコーディングを実行するための方法および装置」と表題を付けられた以前の米国特許出願第０９／９７５，３３１号には、そのような構造がデコーダ実装に与える利点が記載された。重要な観測は、すべての操作がすべてのコピーにわたって並行して行われ得ることである。しかしながら、Ｚコピーはばらばらではなく、これらは組み合わされて、投影グラフよりもＺ倍大きい１つの大きいグラフを形成する。これは、投影グラフのＺコピーを制御されたやり方で相互接続することによって達成される。具体的には、ベクトルエッジ内のＺエッジが例えば、可変ノード側から制約ノード側へ行くときに、それらのＺエッジに、投影グラフのコピー間の並べ替え、または交換を受けさせる。Ｚ平行投影グラフに対応するベクトル化エンコーディングプロセスにおいては、投影可変ノードに対応するベクトル内のＺビットに並べ替えを受けさせる。
【００２５】
符号化および変調の間のインタリービングの目的は、ＬＤＰＣグラフ中の短距離の符号化ビットに対応するソフトメッセージ（値）間の相互関係を緩和することである。さらに、インタリービングが、ターボ等化を支援する構造を作り出し得ることが同様に望ましいことがある。この目的のために、ドウェル中の符号化ビットは、広範囲の次数を有することが好ましい。なぜならば、異なる次数のノードの収束速度が復号プロセスにおいて大きく変化することが知られているからである。初期の位相において首尾よく復号される場合、高次数と関連付けられたビットは、ドウェル中の未知の位相についてより信頼性の高い推定を生成できる。これは一般に、ドウェル中のその隣接シンボルに関して生成されたソフトメッセージを改善し、これが次にデコーダをより効果的に支援する。
【００２６】
データビットが、利用可能な構造を有するベクトルＬＤＰＣ符号によりエンコードされる場合、ノード次数の広範囲の組み合わせを有するドウェルのこの望ましい特性は容易に実装できる。それらのエンコードされたビットを保存しているメモリーが、Ｚ×ｎの行列として構成されていれば、同じ列（物理的に同じアドレス）中のビットは、投影グラフ中の同じノードに対応し、従って同じ次数を有する。
【００２７】
２００３年７月１１日提出の「ＬＤＰＣ符号をエンコーディングするための方法および装置」と表題を付けられた米国特許出願第＿＿＿号に記載されるように、ベクトル化エンコーディングプロセスは、これらの列を、それらの関連付けられた可変ノードの次数が増大する順序になるように配置し得る。そのような配列は、広範囲の次数の可変ノードと関連付けられた符号化ビットでドウェルを形成する代数的インタリービング方法を容易にする。代表的な方法は、行列をＬ−１の連続した部分行列に均一に分割することである。次数が増大するように列が配列される特性は、部分行列が同様の次数の可変ノードを含むことを保証する。すなわち、最初の部分行列は最も低い次数を有し、最後の部分行列は最も高い次数を有する。従って、異なる部分行列から２つのビットを取ることによって形成されたドウェルは所望の特性を有する。
【００２８】
本発明に従って実装される符号化ビットのインタリービングは、以下で論じるように実行し得る。
【００２９】
本発明の代表的なインタリーバ装置は、符号化ビットを保存するためのメモリーおよびインタリービング回路を含む。インタリービング回路は、メモリーからのビットの読取りを制御するために用いられる制御情報の組を生成する。生成された制御情報の各組は、送信単位識別子、Ｚベクトル識別子、および行識別子を含む。制御回路は、代表的な実施形態において、４つの構成要素を含む。すなわち、シンボルＩＤ生成モジュール、ビットＩＤ生成モジュール、列ＩＤ生成モジュールおよび制御情報生成モジュールである。シンボルＩＤ生成モジュールは、０〜Ｍ−１の数ｓを生成する反復カウンタとして実装し得る。反復カウンタは、システムクロックｃｌｋの関数として周期的に増分され、例えば、ｓは、クロックサイクルごとに１回増分され、数ｓは、ドウェル中のシンボルインデックスを決定する。ビットＩＤ生成モジュールも、反復カウンタ、例えば、０〜Ｚ−１の数ｂを生成する反復カウンタとして実装し得る。数ｂは、シンボルインデックス信号ｓが０に達するたびに周期的に増分され、数ｂは、列中で選択されるビットインデックス、例えば、メモリー中に保存されるアレイ中の列の行を決定する。列ＩＤ生成モジュール６０３は、０〜ａ−１の数ｃを生成し、別のカウンタとして実装し得る。数ｃは、ビットインデックスｂが０に達するたびに増分され、数ｃは列インデックスである。ビットインデックスｂ、シンボルインデックスｓ、および列インデックスｃを取ると、制御情報生成モジュールは、送信単位識別子、Ｚベクトル識別子および符号化ビットメモリー中のどの位置がアクセスされるかを制御するために用いられる行識別子を含む制御情報の組を生成する。１つの代表的な実施態様において、Ｚベクトル識別子はｃ＋ａ×ｓであり、行識別子は２×ｂである。送信単位は、値ｂ＋ｃ×Ｚを有する送信単位識別子により識別され、ここでｂおよびｃは上記で定義されたものであり、Ｚは各Ｚベクトル中の要素数であり、×は乗算演算を示す。
【００３０】
受信機側では、データビットと送信単位との間の直接マッピングが復調のために一致させられる。デコーダからのソフト出力が２進符号語構造と同じ配列を有すると仮定される。しかしながら、ソフト値は、符号化ビットに対応するＫビットを含む。ｋビットの各々は、メモリー中のＤアレイのうちの別のアレイ中に保存することができ、Ｄは正の整数である。ほとんどの場合、ｋはＤの整数倍である。１つの代表的なメモリーは、各ビットについて３ビットソフト値を有しており、各々は、同じ符号ビット識別子により識別される。それらの３ビットは、１つのメモリー位置にあってもよく、または、それらの３ビットは、３つの異なるメモリー位置にあってもよい。この構造の場合は、受信機において用いられる同タイプのインタリービング装置も、復調の目的のために送信単位に対応するソフト値にアクセスするために送信機において用い得ることが明らかである。
【００３１】
受信された値も符号語と同じ配列に一致すると仮定すれば、再び同じインタリービング構造が、復調のために受信された値にアクセスするプロセスにおいて適用できる。
【００３２】
本発明の方法および装置の多くの付加的な実施形態、特徴および利点を、以下の詳細な説明において論じる。
【発明を実施するための最良の形態】
【００３３】
図１は、本発明を実装する汎用通信システム１０を例示する。システム１０は、通信チャネル１１０により受信機１２０に結合された送信機１００を含んでいる。送信機１００は、データエンコーディング回路、例えば、エンコーダ１０１、インタリーバ１０２、および変調器１０３を備えている。受信機は、復調器１２１、デインタリーバ１２２、インタリーバ１２３、およびデータデコーダ１２４を備えている。エンコーダ１０１は、入力２進データストリームＡを構造化２進データストリームＸ１へ冗長性と共にマッピングする。インタリーバ１０２は、Ｘ１を別のデータストリームＸ２にインタリーブする。変調器１０３は、２進ストリームＸ２を、実際的な送信に実行可能な物理信号、例えば、ＱＰＳＫ信号に変換する。通信チャネル１１０は、例えば、エアリンクとすることができる。変調信号は、チャネル１１０を介して受信機１２０に送信される。受信機側では、復調器１２１が、雑音のある歪んだ受信Ｙから情報Ｘ２’を抽出する。デインタリーバ１２２は、ソフトメッセージＸ２を、符号構造の本来の配列に対応するＸ１’に配列し直す。そしてデコーダ１２３は、復調により生成された符号化データストリームＸ１’中に存在する冗長性を使用して本来の２進データストリームＡの回復を試みる。デコーダ１２３から復調１２１へのデータパスは、フィードバックループを表している。フィードバックメッセージは、符号における配列を変調における配列に変換するために、インタリーバ１２４によりインタリービングされるべきである。
【００３４】
図３は、グラフ３００の形の単純な不規則ＬＤＰＣ符号を例示する。この符号は、５つの可変ノードＶ１〜Ｖ５３０２により示されるように長さが５である。４つの検査ノードＣ１〜Ｃ４３０６は、合計１２のエッジ３０４によって可変ノード３０２に結合される。
【００３５】
図４は、図３に例示された小さいグラフの３つの平行コピーを作成した結果を例示するグラフ４００である。可変ノード４０２’、４０２’’および４０２’’’は、図３のグラフの３つのコピー作成に起因する第１〜第３のグラフにそれぞれ対応する。さらに、検査ノード４０６’、４０６’’および４０６’’’は、３つのコピー作成に起因する第１〜第３のグラフにそれぞれ対応する。３つのグラフのうちの１つのノードを、３つのグラフの別の１つのノードに接続するエッジが皆無であることに留意されたい。従って、基本グラフを係数３だけ「リフト」するこのコピープロセスは、３つのばらばらな同一のグラフという結果になる。（通常、３つのコピーは、ベクトルエッジを入れ替えることにより相互接続される。）
これから、本発明に従って実装される符号化ビットの代数的インタリービングの説明に進む。
【００３６】
符号化ビットは、Ｚ×ｎとして構成されたメモリー中に保存される。言い換えると、２進符号語をｎＺベクトルと見なし、各ベクトルはＺビットを含む。ベクトルＬＤＰＣ符号中で用いられるＺは、送信されたシンボルに関連付けられたビット数であるＰの倍数である。仮定されたＱＰＳＫ変調（Ｐ＝２）については、Ｚ＝２ｚである。送信単位中の情報送信シンボルの数であるＭの倍数となるように列の数をさらに選ぶ。すなわち、ｎ＝ａＭである。本発明のインタリービング方法は、各送信単位中の各シンボルに関連付けられたＰビットの位置を決定する。明らかに、メモリー位置は、Ｚベクトル識別子およびＺベクトル中のオフセット値に対応している。本発明は、符号化データを以下の通り配列する。すなわち、ｊ番目のドウェル（ｊは、１〜Ｚ×ａ）は、オフセット値２＊（ｊ ｍｏｄ Ｚ／Ｐ）を持つｉ×ｎ／Ｍ＋［ｊ／（Ｚ／Ｐ）］により識別されるＺビットベクトル中の２ビットを含み、ｉは０〜Ｍ−１である。そのような場合、データビットを検索するために用いられるアドレスは、この目的のためのメモリーを使用することなく、代数的に容易に生成し得る。
【００３７】
図５は、Ｌ＝５、Ｍ＝４、およびＰ＝２のコヒーレント間隔についての代表的なインタリービング構造を例示する。アレイ５００は、Ｚ＝４およびｎ＝８を有するベクトル−ＬＤＰＣによりエンコードされた符号化ビットを表す。このアレイは、メモリー位置の対応する構造化アレイ中に保存し得る。符号化ビット５００は、アレイ５００中の各要素が１つのビットを表す４×８配置で保存され、位置（ｉ，ｊ）のビットは、ｃ（ｉ，ｊ）により示される。各ドウェル５０１、５０２、５０３および５０４は、アレイ５００のビットを用いて形成された４つの情報シンボルを含む。提示される手法は、符号化ビットｃ（１，１）、ｃ（２，１）、ｃ（１，３）、ｃ（２，３）、ｃ（１，５）、ｃ（２，５）、ｃ（１，７）、ｃ（２，７）を含む第１のドウェル８０１を作る。説明を容易にするため、用いられる代表的な変調は擬似パイロット変調であり、ダイビット００が各ドウェル（の中央に）挿入されて、ドウェル中の５つのシンボルの１つになる。従って、第１の送信ドウェルは、５０１に示されるように、Ｓ（ｃ（１，１）ｃ（２，１））、Ｓ（ｃ（１，３）ｃ（２，３））、Ｓ（００），Ｓ（ｃ（１，５）ｃ（２，５））、Ｓ（ｃ（１，７）ｃ（２，７））である。同様に、第２のドウェル５０２は、Ｓ（ｃ（３，１）ｃ（４，１））、Ｓ（ｃ（３，３）ｃ（４，３））、Ｓ（００）、Ｓ（ｃ（３，５）ｃ（４，５））、Ｓ（ｃ（３，７）ｃ（４，７））を含む。以下同様である。
【００３８】
提示されるインタリービング手法のための装置、例えば、発明のインタリーバ１０２が図６に示してある。このインタリーバ１０２は、図６に示されるように一緒に結合された、符号化ビットを保存するためのメモリー６１０およびインタリービング回路６００を含んでいる。インタリービング回路６００は、メモリー６１０からのダイビットの読取りを制御するために用いられる制御情報の組を生成する。生成された制御情報の各組は、送信単位識別子、Ｚベクトル識別子、および行識別子を含んでいる。回路６００は４つの構成要素を含んでいる。すなわち、シンボルＩＤ生成モジュール６０１、ビットＩＤ生成モジュール６０２、列ＩＤ生成モジュール６０３および制御情報生成モジュール６０４である。モジュール６０１は、０〜Ｍ−１の数ｓを生成する反復カウンタである。カウンタ６０１は、システムクロックｃｌｋの関数として周期的に増分され、例えば、ｓはクロックサイクルごとに１回増分され、数ｓはドウェル中のシンボルインデックスを決定する。モジュール６０２は、０〜Ｚ−１の数ｂを生成する反復カウンタである。数ｂは、シンボルインデックス信号ｓが０に達するたびに周期的に増分され、数ｂは、列中で選択されるビットインデックス、例えば、メモリー６０５中に保存されるアレイ６００中の列の行を決定する。モジュール６０３はもう一つのカウンタである。モジュール６０３は、０〜ａ−１の数ｃを生成する。数ｃは、ビットインデックスｂが０に達するたびに増分され、数ｃは列インデックスである。ビットインデックスｂ、シンボルインデックスｓ、および列インデックスｃを取ると、制御情報生成モジュール６０４は、送信単位識別子、Ｚベクトル識別子、および符号化ビットメモリー６０５中のどの位置がアクセスされるかを制御するために用いられる行識別子を含む制御情報の組を生成する。Ｚベクトル識別子はｃ＋ａ×ｓであり、行識別子は２×ｂである。送信単位は、値ｂ＋ｃ×Ｚを有する送信単位識別子により識別され、ここでｂおよびｃは上記で定義されたものであり、Ｚは各Ｚベクトル中の要素数であり、ｘは乗算演算を示す。
【００３９】
受信機側では、データビットと送信単位との間の直接マッピングが復調のために一致させられる。デコーダからのソフト出力が、例えば、アレイ６００において示されるような２進符号語構造と同じ配列を有すると仮定する。しかしながら、ソフト値は、符号化ビットに対応するＫビットを含む。ｋビットの各々は、Ｄアレイのうちの別のアレイ中に保存することができ、Ｄは正の整数である。ほとんどの場合、ｋはＤの整数倍である。１つの代表的なメモリー７００は、各ビットについて３ビットソフト値を有しており、各々は、同じ符号ビット識別子により識別される。それらの３ビットは、１つのメモリー位置にあるかもしれず、または、それらの３ビットは、７００において示されるように、３つの異なるメモリー位置７０１、７０２、７０３にある。この構造の場合は、同じインタリービング回路６００が、復調のために送信単位についてのソフト値にアクセスするために用い得ることが明らかである。
【００４０】
受信された値も符号語と同じ配列に一致すると仮定すれば、再び同じインタリービング構造が、復調のために受信された値にアクセスするプロセスにおいて適用できる。
【００４１】
ターボ等化においては、ベクトルデコーダ（モジュール８００）からのソフト出力およびチャネル受信機（モジュール８０８）からのソフト入力が、例えば、アレイ６００に示されるような、符号化ビットと同じ配置を有すると仮定する。しかしながら、上述の配置におけるエントリは、ビットではなくてＫビット整数である。なぜならば、それらはソフトメッセージだからである。インタリービング回路８０２は、図６に示される回路６００と同じとすることができる。インタリービング回路８０２は、デコーダからのソフト出力およびドウェルの配列中のチャネルからのソフト入力双方にアクセスするための正しいアドレスを生成する。同じ生成されたアドレスは、遅延線８１０により導入された遅延に従って、復調後にデコーダ（モジュール８０６）へのソフト入力の書き込みを制御するために用いられる書き込みアドレスを提供する。
【００４２】
上述の方法または方法ステップの多くは、例えば、１つ以上の通信ネットワークノードにおいて上述の方法のすべてまたは一部を実装するため、機械、例えば、付加的ハードウェアを持つまたは持たない汎用コンピュータを制御し、記憶デバイス、例えば、ＲＡＭ、フロッピー（登録商標）ディスク等のような機械可読媒体中に含まれるソフトウェアのような機械実行可能命令を用いて実装し得る。従って、とりわけ、本発明は、機械、例えば、プロセッサおよび関連ハードウェアに、上述の方法の１つ以上のステップを実行させるための機械実行可能な命令を含む機械可読媒体に向けられる。
【００４３】
上述の本発明の方法および装置に関する多くの付加的な変型は、本発明の上記の説明を考慮して当業者にとり明白であろう。そのような変型は、本発明の範囲内にあると見なされるべきである。本発明の方法および装置は、様々な実施形態において、ＣＤＭＡ、直交周波数分割多重（ＯＦＤＭ）、および／またはアクセスノードと移動ノードとの間の無線通信リンクを提供するために用い得る様々な他のタイプの通信手法と共に用いられる。いくつかの実施形態において、アクセスノードは、ＯＦＤＭおよび／またはＣＤＭＡを用いて移動体ノードとの通信リンクを確立する基地局として実装される。様々な実施形態において、移動ノードは、ノートコンピュータ、パーソナルデータアシスタント（ＰＤＡ）、または本発明の方法を実装するために受信機／送信機回路およびロジックおよび／またはルーチンを含むその他の携帯用機器として実装される。
【図面の簡単な説明】
【００４４】
【図１】本発明の方法および装置が用いられるエンコーダ、インタリーバ、変調器、チャネル、復調器、デインタリーバ、およびデコーダを含む代表的な通信システムを例示する。
【図２】長さ１０の代表的な正則ＬＤＰＣ符号の２部構成のグラフ表現を例示する。
【図３】本発明に従う例を提示するためにずっと大きいＬＤＰＣ符号の基礎として用いられる小さいＬＤＰＣ符号のグラフィック表現である。
【図４】図３に示される小さいＬＤＰＣグラフの３つのコピーの作成の効果を図示する。
【図５】本発明に従う代表的な４×８ＬＤＰＣ符号を用いることによる代数的インタリービングの結果を例示する。特に、送信単位の一部への符号化データビットの直接マッピングを例示する。
【図６】図１に示されるシステムの送信機においてインタリーバとして用いるのに適した代表的なインタリーバを例示し、これは本発明に従って代数的インタリービングを実装する。
【図７】ＬＤＰＣデコーダからのソフト値と図５に示される代表的な符号構造を用いる送信単位との間の対応関係を例示する。ソフト値は３ビットを含んでいる。
【図８】図１に示されるシステムの受信機においてインタリーバおよびデインタリーバとして用いるのに適した、反復復調および復号においてインタリービングおよびデインタリービングを適用するための代表的な構造を例示する。
【符号の説明】
【００４５】
１０  汎用通信システム，  １００  送信機，  １２０  受信機，  １１０  通信チャネル，  ６００  インタリービング回路
【図１】
2007525058.tif 000003
【図２】
2007525058.tif 000004
【図３】
2007525058.tif 000005
【図４】
2007525058.tif 000006
【図５】
2007525058.tif 000007
【図６】
2007525058.tif 000008
【図７】
2007525058.tif 000009
【図８】
2007525058.tif 000010
【国際調査報告】
2007525058.tif 000011