(57)【要約】【課題】無線通信のためのターボ復号方法および装置。【解決手段】通信システム１０において、方法および装置が、ターボ符号化されたデータシンボルのシーケンスを復号化することを与える。チャネルノードＲｘ、Ｒｙ、およびＲｚは、受信されたチャネル出力に基づいて更新され、そしてシンボルノード（７０１、７０７、７０８）からの出発メッセージが初期化される。シンボルノード（７０１、７０７、７０８）は、チャネルノードＲｘ、Ｒｙ、およびＲｚと通信している。異なった時刻段階における計算上のノードＣ（７０４）およびＤ（７０６）の更新は、トリガリング計画に従って実行される。
2005528811.tif 000002
【特許請求の範囲】
【請求項１】
通信システムにおいて、チャネル上に送信されたターボ符号化されたデータシンボルのシーケンスを復号するための方法であって、
受信されたチャネル出力に基づいてチャネルノードＲｘ、Ｒｙ、およびＲｚを更新し、
シンボルノードＸｉ、Ｙｉ、およびＺｋから出発メッセージを初期化し、ここでシンボルノードＸｉ、Ｙｉ、およびＺｋは、チャネルノードＲｘ、Ｒｙ、およびＲｚと通信しており、そして
トリガリング計画に従って異なった時刻の段階と組み合わせられた計算上のノードＣおよびＤの更新をトリガすることを含む、ここで計算上のノードＣｉはシンボルノードＸｉおよびＹｉと通信しており、そして計算上のノードＤｋはシンボルノードＸｉおよびＺｋと通信している方法。
【請求項２】
ここで、計算上のノードＣｉは第１の要素符号と組み合わせられた状態ノードＳｉおよびＳｉ−１と通信しており、そして計算上のノードＤｋは第２の要素符号と組み合わせられた状態ノードσｋおよびσｋ−１と通信している、ここで第１および第２の要素符号は、符号化されたデータシンボルのシーケンスを符号化するために使用される通信システム内のターボ符号と組み合わせられている、請求項１に記載された方法。
【請求項３】
さらに、計算上のノードＣおよびＤの更新をトリガすることの少なくとも１度の反復の後に、シンボルノードＸｉにおいて、シンボルＸｉの復号された値としてシンボルＸｉの値を受け入れることを含む、請求項１に記載された方法。
【請求項４】
ここで、トリガリング計画は、異なった時刻段階における計算上のノードＣおよびＤを、本質的に同時にトリガすることを含む、請求項１に記載された方法。
【請求項５】
ここで、トリガリング計画は、異なった時刻段階における計算上のノードＣおよびＤを、Ｃ０、Ｃ１、Ｃ２、…、ＣＮ、ＣＮ−１、ＣＮ−２、ＣＮ−３、…、Ｃ２、Ｃ１、Ｃ０、Ｄ０ 、Ｄ１、Ｄ２、…、ＤＮ，ＤＮ−１、ＤＮ−２、ＤＮ−３、…、Ｄ２、Ｄ１、Ｄ０の順序でトリガすることを含む、請求項１に記載された方法。
【請求項６】
さらに、時刻段階Ｃ０、Ｃ１、Ｃ２、…、ＣＮにおける計算上のノードＣを、少なくとも２個のサブセットに分割することを含む、ここでトリガリング計画は、各サブセット内で異なった時刻段階において順々に計算上のノードＣの更新をトリガすることを含む、請求項１に記載された方法。
【請求項７】
さらに、更新をトリガするために、各サブセット内で異なった時刻段階における順序を決定することを含む、請求項６に記載された方法。
【請求項８】
ここで、少なくとも２個のサブセット内の異なった時刻段階における計算上のノードＣに関するトリガリングは同時に生じる、請求項６に記載された方法。
【請求項９】
ここで、異なった時刻段階Ｃ０、Ｃ１、Ｃ２、…、ＣＮにおける計算上のノードＣに関する少なくとも２個のサブセットは、少なくとも１個の共通した計算上のノード時刻段階を有する、請求項６に記載された方法。
【請求項１０】
さらに、異なった時刻段階Ｄ０、Ｄ１、Ｄ２、…、ＤＮにおける計算上のノードＤを少なくとも２個のサブセットに分割することを含む、ここでトリガリング計画は計算上のノードＤを、異なった時刻段階において各サブセット内で順々にトリガすることを含む、請求項１に記載された方法。
【請求項１１】
さらに、更新をトリガするために、各サブセット内で異なった時刻段階における順序を決定することを含む、請求項１０に記載された方法。
【請求項１２】
ここで、少なくとも２個のサブセット内の異なった時刻段階における計算上のノードＤに関するトリガリングは同時に生じる、請求項１０に記載された方法。
【請求項１３】
ここで、時刻段階Ｄ０、Ｄ１、Ｄ２、…、ＤＮにおける計算上のノードＤに関するサブセットは、少なくとも１個の共通した計算上のノード時刻段階を有する、請求項１０に記載された方法。
【請求項１４】
ここで、更新は、出力メッセージを生成するために到来メッセージを合計し、そして更新のために出力メッセージを出力する、請求項１に記載された方法。
【請求項１５】
ここで、受信されたチャネル出力に基づいてチャネルノードＲｘ、Ｒｙ、およびＲｚを更新することは、
チャネルノードＲｘにおいてシンボルＸｉと組み合わせられたチャネル出力を受信し、
チャネルノードＲｙにおいてシンボルＹｉと組み合わせられたチャネル出力を受信し、
チャネルノードＲｚにおいてシンボルＹｋと組み合わせられたチャネル出力を受信し、
受信されたチャネル出力に基づいてシンボルＸｉの確度をチャネルノードＲｘからシンボルノードＸｉに送り、
受信されたチャネル出力に基づいてシンボルＹｉの確度をチャネルノードＲｙからシンボルノードＹｉに送り、そして
受信されたチャネル出力に基づいてシンボルＺｋの確度をチャネルノードＲｚからシンボルノードＺｋに送る、
ことを含む、請求項１に記載された方法。
【請求項１６】
ここで、シンボルノードＸｉ、Ｙｉ、およびＺｋからの出発メッセージを初期化することは、
シンボルノードＸｉからのメッセージを、計算上のノードＣに関する計算上のノードＣｉに送り、ここでメッセージはシンボルノードＸｉにおける到来メッセージの総和に基づいており、
シンボルノードＸｉからのメッセージを、計算上のノードＤに関する計算上のノードＤｋに送り、ここでメッセージはシンボルノードＸｉにおける到来メッセージの総和に基づいており、
シンボルノードＹｉからのメッセージを、計算上のノードＣｉに送り、ここでメッセージはデータシンボルＹｉの確度に基づいており、そして
シンボルノードＺｋからのメッセージを計算上のノードＤｋに送ることを含む、ここでメッセージはデータシンボルＺｋの確度に基づいている、請求項１に記載された方法。
【請求項１７】
ここで、データのシーケンスはシンボルの“Ｎ”個の数を含み、ここでシーケンス内の各シンボルは添字“ｉ”あるいは“ｋ”の何れかによって識別され、そしてここで添字“ｉ”および“ｋ”は、復号処理における時刻段階に対する参照である、請求項１に記載された方法。
【請求項１８】
チャネル上に通信されたターボ符号化されたデータシンボルのシーケンスを復号するための装置であって、
チャネル出力を受信するためのチャネルノードＲｘ、Ｒｙ、およびＲｚと、
チャネルノードＲｘ、Ｒｙ、およびＲｚと通信しているシンボルノードＸｉ、Ｙｉ、およびＺｋと、
ターボ符号内の第１の要素符号と組み合わせられた状態ノードＳｉおよびＳｉ−１と、
ターボ符号内の第２の要素符号と組み合わせられた状態ノードσｋおよびσｋ−１と、
シンボルノードＸｉおよびＹｉと通信している計算上のノードＣｉと、そして
シンボルノードＸｉおよびＺｋと通信している計算上のノードＤｋと、ここで計算上のノードＣｉは状態ノードＳｉおよびＳｉ−１と通信しており、そして計算上のノードＤｋは状態ノードσｋおよびσｋ−１と通信しており、
状態ノードＳｉと通信している計算上のノードＣｉ＋１と、
状態ノードＳｉ−１と通信している計算上のノードＣｉ−１と、
状態ノードσｋと通信している計算上のノードＤｋ＋１と、そして
状態ノードσｋ＋１と通信している計算上のノードＤｋ−１とを含む、ここで異なった時刻段階における計算上のノードＣおよびＤは、更新トリガリング計画に従った更新のために配列されている装置。
【請求項１９】
ここで、更新トリガリング計画は、計算上のノードＣおよびＤの更新を、Ｃ０、Ｃ１、Ｃ２、…、ＣＮ、ＣＮ−１、ＣＮ−２、ＣＮ−３、…、Ｃ２、Ｃ１、Ｃ０、Ｄ０、Ｄ１、Ｄ２、…、ＤＮ、ＤＮ−１、ＤＮ−２、ＤＮ−３、…、Ｄ２、Ｄ１、Ｄ０の順序でトリガすることを含む、請求項１８に記載された装置。
【請求項２０】
ここで、更新トリガリング計画は、少なくとも２個のサブセットに分割された計算上のノードＣ０、Ｃ１、Ｃ２、…、ＣＮの中で、そして少なくとも２個のサブセットに分割された計算上のノードＤ０、Ｄ１、Ｄ２、…、ＤＮの中で順々に更新をトリガすることを含む、請求項１８に記載された装置。
【請求項２１】
ここで、データのシーケンスはシンボルの“Ｎ”個の数を含み、ここで、シーケンス内の各シンボルは状態ノードおよび計算上のノードに対して使用される添字に対応する添字“ｉ”あるいは“ｋ”の何れかによって識別される、請求項１８に記載された装置。
【請求項２２】
チャネル上の通信のためのターボ符号化されたデータシンボルのシーケンスを復号するために配列された処理装置であって、
チャネル出力を受信するためのチャネルノードＲｘ、Ｒｙ、およびＲｚと、
チャネルノードＲｘ、Ｒｙ、およびＲｚと通信しているシンボルノードＸｉ、Ｙｉ、およびＺｋと、
ターボ符号内の第１の要素符号と組み合わせられた状態ノードＳｉおよびＳｉ−１と、
ターボ符号内の第２の要素符号と組み合わせられた状態ノードσｋおよびσｋ−１と、
シンボルノードＸｉ、およびＹｉと通信している計算上のノードＣｉと、そして
シンボルノードＸｉ、およびＺｋと通信している計算上のノードＤｋと、ここで計算上のノードＣｉは状態ノードＳｉおよびＳｉ−１と通信しており、そして計算上のノードＤｋは状態ノードσｋおよびσｋ−１と通信しており、
状態ノードＳｉと通信している計算上のノードＣｉ＋１と、
状態ノードＳｉ−１と通信している計算上のノードＣｉ−１と、
状態ノードσｋと通信している計算上のノードＤｋ＋１と、そして
状態ノードσｋ＋１と通信している計算上のノードＤｋ−１とを含む、ここで異なった時刻段階における計算上のノードＣおよびＤは、更新トリガリング計画に従った更新のために配列されている処理装置。
【請求項２３】
ここで、更新トリガリング計画は、計算上のノードＣおよびＤの更新を、Ｃ０、Ｃ１、Ｃ２、…、ＣＮ、ＣＮ−１、ＣＮ−２、ＣＮ−３、…、Ｃ２、Ｃ１、Ｃ０、Ｄ０、Ｄ１、Ｄ２、…、ＤＮ、ＤＮ−１、ＤＮ−２、ＤＮ−３、…、Ｄ２、Ｄ１、Ｄ０の順序でトリガすることを含む、請求項２２に記載された処理装置。
【請求項２４】
ここで、データのシーケンスはシンボルの“Ｎ”個の数を含み、ここで、シーケンス内の各シンボルは状態ノードおよび計算上のノードに対して使用される添字に対応する添字“ｉ”あるいは“ｋ”の何れかによって識別される、請求項２２に記載された処理装置。
【請求項２５】
チャネル上の通信のためのターボ符号化されたデータシンボルのシーケンスを復号するための装置であって、
チャネル出力を受信するためのチャネルノードＲｘ、Ｒｙ、およびＲｚに対する手段と、
チャネルノードＲｘ、Ｒｙ、およびＲｚと通信しているシンボルノードＸｉ、Ｙｉ、およびＺｋに対する手段と、
ターボ符号内の第１の要素符号と組み合わせられた状態ノードＳｉおよびＳｉ−１に対する手段と、
ターボ符号内の第２の要素符号と組み合わせられた状態ノードσｋおよびσｋ−１に対する手段と、
シンボルノードＸｉおよびＹｉと通信している計算上のノードＣｉに対する手段と、
シンボルノードＸｉおよびＺｋと通信している計算上のノードＤｋに対する手段と、ここで、計算上のノードＣｉは状態ノードＳｉおよびＳｉ−１と通信しており、なお、計算上のノードＤｋは状態ノードσｋおよびσｋ−１と通信しており、
状態ノードＳｉと通信している計算上のノードＣｉ＋１に対する手段と、
状態ノードＳｉ−１と通信している計算上のノードＣｉ−１に対する手段と、
状態ノードσｋと通信している計算上のノードＤｋ＋１に対する手段と、そして
状態ノードσｋ＋１と通信している計算上のノードＤｋ−１に対する手段とを含む、ここで異なった時刻段階における計算上のノードＣおよびＤは、更新トリガリング計画に従った更新のために配列されている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信分野そしてとくに無線通信に関する。
【背景技術】
【０００２】
誤り制御符号はデータシンボルのシーケンスの通信に冗長性を与え、そしてそれは雑音および干渉の存在の下でデータシンボルのもとのシーケンスを再生するために受信端において利用される。ビタビ(Viterbi)復号器を用いた畳み込み符号は、ＣＤＭＡ無線通信システムにおいて、電力を制限されたチャネルおよび干渉を制限されたチャネル上で、信頼できる通信を達成するために広く使用されてきている。ターボ符号と称される誤り訂正符号の新しい種類はさらに、古い符号に勝って特性の向上を与えている。受信機におけるターボ符号に対する復号処理は反復アルゴリズムを含み、そしてそれは受信機にとっては複雑であり計算的に徹底している。
【０００３】
その結果、当業界においては、ターボ符号が使用される通信システムにおける改善された復号器に対するニーズが存在する。
【発明の開示】
【課題を解決するための手段】
【０００４】
通信システムにおいて、方法および装置がターボ符号化されたデータシンボル（turbo encoded data symbol）のシーケンスを復号することを与える。本発明に関する種々の観点が、種々のノードおよび接続ブランチを含む図によって示される。ノードは、チャネルノード（channel node）、シンボルノード（symbol node）、ステートノード（state node）、および計算上のノード（computational node）を含む種々の形式のものである。ノードを接続しているブランチは、１個のノードから他へのメッセージの流れを可能にする。ノードおよびブランチは、ソフトウエア、ハードウエア、あるいは両者の組み合わせによって実現することが可能である。ノードは、到来メッセージの値に基づいた値を有する出発メッセージ（outgoing message）の送出によって更新されることが可能である。一つの実施例においては、チャネルノードＲｘ、Ｒｙ、およびＲｚは、受信されたチャネル出力に基づいて更新され、そしてシンボルノードからの出発メッセージは初期化される。シンボルノードはチャネルノードＲｘ、Ｒｙ、およびＲｚと通信している。計算上のノードＣおよびＤに関する更新は、トリガリング計画（triggering schedule）に従って実行される。一つの実施例においては、計算上のノードＣおよびＤに関する更新は、すべての可能性のある時刻段階（time instance）に対して同時にトリガされる。トリガリング計画は、復号処理に関する１個あるいはそれ以上の反復を得るために繰り返されることが可能である。１個あるいはそれ以上の反復の後に、シンボルノードは、復号されたシンボルに対する値を保持する。結果として、復号処理は効率的に、正確に、そして迅速に実行される。
【発明を実施するための最良の形態】
【０００５】
本発明の特徴、目的、および利点が、図面と関連させた場合に、以下に記述する詳細な説明からより明白になろう。図面において同様の参照符号は、全体を通して同一のものと認定する。
本発明の種々の実施例は、米国通信工業会（ＴＩＡ）、第３世代パートナーシッププロジェクト（３ＧＰＰ）、および第３世代パートナーシッププロジェクト２（３ＧＰＰ２）によって刊行された種々の標準の中に開示され、そして記述されてきている、符号分割多元接続（ＣＤＭＡ）技術に従って動作する無線通信システム内に組み入れられることが可能である。これらの標準は、ＴＩＡ／ＥＩＡ‐９５標準、ＴＩＡ／ＥＩＡ‐ＩＳ‐８５６標準、ＩＭＴ‐２０００標準（ｃｄｍａ２０００標準およびＷＣＤＭＡ標準を含む）、ここに参照によって組み込まれたすべてのものを含む。標準の写しは、ｈｔｔｐ：／／ｗｗｗ．３ｇｐｐ２．ｏｒｇなるアドレスのワールドワイドウエブにアクセスすることによって、あるいは、アメリカ合衆国、ＶＡ２２２０１、Ａｒｌｉｎｇｔｏｎ、２５００Ｗｉｌｓｏｎ  Ｂｏｕｌｅｖａｒｄ、米国通信工業会標準および技術部あてに手紙を書くことによって入手が可能である。一般的にＷＣＤＭＡ標準として識別され、この中に参照によって組み込まれている標準は、３ＧＰＰサポートオフィス、６５０Ｒｏｕｔｅ  ｄｅｓ  Ｌｕｃｉｏｌｅｓ‐Ｓｏｐｈｉａ  Ａｎｔｉｐｏｌｉｓ、Ｖａｌｂｏｎｎｅ‐Ｆｒａｎｃｅとコンタクトすることによって、入手することが可能である。
【０００６】
一般的に述べられた、新しいそして改善された方法およびこれに伴う装置は、通信システムにおける符号化されたデータシンボルのシーケンスに関する効率的な復号を与える。ここに記述された１個あるいはそれ以上の典型的な実施例は、ディジタル無線データ通信システムにおいて示されている。この範囲内における使用においては有利である一方、本発明の異なった実施例は、異なった環境あるいは配置と組み合わせられることが可能である。一般的に、ここに記述される種々のシステムは、ソフトウエアで制御される処理装置、集積回路、あるいはディスクリート論理を用いて形成することが可能である。応用を通じて参照されるかも知れないデータ、命令、指令、情報、信号、シンボル、およびチップは、電圧、電流、電磁波、磁場あるいは粒子、光学場あるいは粒子、あるいはこれらの組み合わせによって好都合に示される。さらに、各ブロック線図内に示されるブロックは、ハードウエアあるいは方法ステップを示すかも知れない。
【０００７】
図１は、チャネル上での動作のための送信機および受信機を含む通信システム１０に関するブロック線図である。送信端においては、システム１０は、符号化動作のための入力データシーケンスを受信するための符号器１２を含む。符号器１２は、変調器１４に符号化されたデータシーケンスを出力する。変調器１４は、符号化されたデータシーケンスを搬送波信号上に変調する。変調器１４は、結果となる信号を送信機１６に与える。送信機１６は、加法性白色ガウス雑音（ＡＷＧＮ）チャネル１７上に信号を送信するために必要な、電力増幅器およびアンテナを含むかも知れない。受信機１８は信号を受信する。受信された信号は復調器１９によって復調されそして復号器２０に進められる。復号器２０は入力データシーケンスの推定値を出力する。変調器１４、送信機１６、受信機１８、および復調器１９の動作は、関連業界において既知の技術に従うことが可能である。
【０００８】
符号器１２は、入力データビットの数（ｋ）に対して生成された符号語内の符号化されたシンボルの数（ｎ）に対応する符号化率（ｋ／ｎ）において符号化するための、畳み込み符号器を含むことが可能である。拘束長（Ｋ）がまた、データの畳み込み符号化に使用されるシフトレジスタの長さとして定義される。畳み込み符号器はバイナリ係数および長さＫ−１を有する有限インパルス応答濾波器として動作するかも知れない。符号器は、２から（Ｋ−１）乗までの可能な状態を有することが可能である。
【０００９】
図２を参照して、一つの実施例に従ったシステム１０における使用のための畳み込み符号器１００に関するブロック線図が示される。符号器１００は、データシンボルＸｉを入力し、そして符号化されたシンボルＸｉおよびＹｉを含む符号語を出力する。その結果、符号化は符号化率１／２におけるものである。添字“ｉ”は、時刻のある段階を表しているインデックスである。符号器１１０は、データシンボルＹｉを生成するために、多項式に従って入力データシンボルＸｉを符号化する。多項式は、畳み込み符号に従うことが可能である。このような多項式の実行は、バイナリフリップフロップ１１１および１１２を含むかも知れない。バイナリフリップフロップ１１１および１１２は、それぞれ状態“Ｄ０”および“Ｄ１”にあることが可能である。状態Ｄ０およびＤ１は、時刻の任意段階において状態“０”あるいは“１”の何れかであることが可能である。システム１０においては、符号化されたデータシンボルＸｉおよびＹｉは、ＡＷＧＮチャネル１７上で受信機１８に送信される。
【００１０】
それは必要ではないが、符号特性あるいは最適復号器の特性の何れかを理解するときに、符号をトレリス線図（trellis diagram）上に表すことが有効である。トレリス線図は、符号器のための状態線図に関する無限の写しである。トレリス中の一つのレベルにおけるノード（状態）は、前のレベルのノード（状態）から、状態線図によって決定されるように１個の入力ビットに対応する１個のブランチを経ての移行によって達成される。状態メトリック、パスメトリック、およびブランチメトリック等のいくつかのメトリックの形式が復号処理に使用されることが可能である。最も可能性のある経路が、確実性の高い程度をもって選定されることが可能である。選定された経路の各ブランチに関するシンボルに対応する符号語は、送信された符号語の最も可能性のある組み合わせである。
【００１１】
図３を参照して、トレリス（trellis）２００は、受信された符号化されたデータシンボルＸｉおよびＹｉを復号器２０において復号するために示される。トレリス２００は、時刻段階“ｉ−１”、“ｉ”および“ｉ＋１”におけるフリップフロップ１１１および１１２のそれぞれの状態に対する状態空間（state space）２０１、２０２、および２０３を示す。４個の可能性のある状態２１１、２１２、２１３、および２１４は、典型的実施例に示されるように各状態空間と組み合わせられる。たとえば、状態２１１、２１２、２１３、および２１４は、可能性のある状態“００”、“１０”、“０１”、および“１１”におけるそれぞれ、フリップフロップ１１１および１１２の状態を示す。一つの状態空間における一つの状態から、他の状態空間における他の状態への移行は、異なった可能性のある符号語ブランチによって示される。各ブランチは、符号化されたシンボルＸｉおよびＹｉに対する特定の選択を示す。たとえば、符号語ブランチ“０１”は、データシンボルＸｉに対する“０”の値、およびデータシンボルＹｉに対する“１”の値を示す。符号語ブランチ“０１”は、フリップフロップ１１１および１１２の、ある時刻の段階における状態空間の状態２１３から次の時刻の段階における他の状態空間の状態２１１への、そしてある時刻の段階における状態空間の状態２１４から次の時刻の段階における他の状態空間の状態２１４への移行を示すことが可能である。レート１／２に対しては、各状態空間における各状態は、少なくとも２個の可能性のある符号語ブランチによって到達されることが可能である。
【００１２】
種々の実施例に従って、復調器１９内の相関器は、各受信された符号化されたデータシンボルに関する確率を、チャネル出力に基づいて決定することが可能である。各受信された符号化されたデータシンボルと組み合わせられた確率は、記憶エレメント内に保存されるかも知れない。各データシンボルＸｉおよびＹｉに対する決定された確率は、ブランチメトリック（チャネルメトリック）を決定するために使用される。
【００１３】
ＭＡＰアルゴリズムとして一般に知られるアルゴリズムは、復号処理に使用されることが可能である。トレリス２００における復号処理は、状態メトリックおよびパスメトリックを初期の状態空間および最終の状態空間から、順方向および逆方向法で(in a forward and backward fashion)、同時に決定することを含むかも知れない。軟判定（soft decision）は、符号化されたデータシンボルＸｉおよびＹｉの値を、トレリス内の状態空間に対応する時刻段階におけるブランチによって表されるとして決定する。符号化されたデータシンボルＸｉおよびＹｉの値に対する軟判定を行うために、各ブランチに関するデュアルメトリック（ＤＭ）が決定される。ブランチのＤＭは順方向状態メトリック(forward state metric)（ＦＳＭ）、逆方向状態メトリック(backward state metric)（ＢＳＭ）、およびブランチメトリック（ＢＭ）に基づいている。ＤＭは、ＦＳＭ、ＢＳＭ、およびＢＭの合計であるかも知れない。ブランチのＢＭは、チャネル出力に基づいて決定されるかも知れない。
【００１４】
状態のＦＳＭは順方向パスメトリック（ＦＰＭ）に基づいているかも知れない。ブランチの一端におけるＦＰＭは、ブランチの開始点における状態のＦＳＭおよびブランチのＢＭの合計に等しいかも知れない。トレリスの初期の状態空間における状態のＦＳＭは、既知であり、あるいはあらかじめ設定されているかも知れない。トレリスの初期の状態空間における状態以外の状態のＦＳＭは、初期の状態空間から出発しそして状態において終了する経路のＦＰＭの汎用最小値(generalized minimum)に等しいかも知れない。状態のＢＳＭは、逆方向パスメトリック（ＢＰＭ）に基づくかも知れない。ブランチの一端におけるＢＰＭは、ブランチの開始点における状態のＢＳＭおよびブランチのＢＭに等しいかも知れない。トレリスの最終の状態空間における状態のＢＳＭは、既知であり、あるいはあらかじめ設定されているかも知れない。トレリスの最終の状態空間における状態以外の状態のＢＳＭは、その状態から出発し、そして最終の状態空間に関する状態において終了する経路のＢＰＭの汎用最小値に等しいかも知れない。このように、初期の状態および最終の状態からの状態空間のＦＳＭ、ＢＳＭ、およびＢＭは、両方向からの経路がブランチすべてに対するＤＭを決定するために反対の終端に到達するまで、連続した方法で決定されるかも知れない。ブランチのＤＭは、順方向からのブランチの一端における状態のＦＳＭ、逆方向からのブランチの一端における状態のＢＳＭ、およびブランチのＢＭに基づくかも知れない。
【００１５】
２個の連続した状態空間の間のブランチのＤＭは、二つのグループに分類することが可能である。第１のグループは“０”に等しいＸｉシンボルを有する符号語をもったブランチを含んでいる。第２のグループは“１”に等しいＸｉシンボルを有する符号語をもったブランチを含んでいる。第１のグループ（ＧＭＢ０）に関する汎用最小値、および第２のグループ（ＧＭＢ１）に関する汎用最小値が決定される。 Ｘｉシンボルに対する軟判定は、ＧＭＢ０およびＧＭＢ１間の差に等しいかも知れない。符号語の他のデータシンボルに対する軟判定は、同様にしてブランチを二つのグループに分類することによって決定されるかも知れない。第１のグループは“０”に等しいデータシンボルを有することかも知れず、そして第２のグループは“１”に等しい（データシンボルを有することかも知れない）。データシンボルに対する軟判定はＧＭＢ０およびＧＭＢ１間の差に等しいかも知れない。
【００１６】
トレリスの各ブランチは、いくつかのデータシンボルを含む符号語を示している。たとえば、符号化率１／２に対しては、トレリス２００内に示される各ブランチ内の符号語は、データシンボルＸｉおよびＹｉに対する値を示している。もしも送信機内の符号器が符号化率１／３で符号化されたデータシンボルを送信する場合は、各入力データシンボルに対して３個のデータシンボルが生成されることが可能である。このような例においては、各ブランチ内の符号語は３個のデータシンボルを示す。
【００１７】
図４を参照して、従来のレート１／３ターボ符号器（turbo encoder）４００に関する一般的ブロック線図が示されている。一般的に言えば、レート１／３ターボ符号器は、少なくとも２個の並列符号器を含む。ターボ符号器４００は、第１の要素符号（constituent code）４０１および第２の要素符号４０２、および符号インターリーバ４０３を含む。データシンボルＸｉは、入力４１０においてターボ符号器４００に入力する。第１の要素符号４０１は、データシンボルＸｉを符号化されたデータシンボルＹｉを生成するために入力する。符号インターリーバ４０３は、データシンボルＸｋを生成するためにデータシンボルＸｉをインタリーブするためにデータシンボルＸｉを受信する。データシンボルＸｋは、再配列されたデータシンボルＸｉを含むかも知れない。第２の要素符号４０２は、データシンボルＸｋを符号化し、そしてデータシンボルＺｋを出力する。第１および第２の要素符号４０１および４０２内のデータシンボルを符号化するために用いられた多項式は、同じであるかあるいは異なるかも知れない。第１および第２の要素符号４０１および４０２における符号化は、図２に示される畳み込み符号１１０に従うかも知れない。
【００１８】
データシンボルＸｉ、Ｙｉ、およびＺｋは、伝送のためのデータシンボルを選定するためにパンクチャリングブロック（図示せず）に通されるかも知れない。選定は、パンクチャリングパターンに従うかも知れない。選定されたデータシンボルは、専らデータシンボルＸｉ、Ｙｉ、およびＺｋのみである。システム１０においては、選定されたデータシンボルは変調および受信機１８への伝送のために変調器１４に通される。復号器２０は、データシンボルＸｉ、Ｙｉ、およびＺｋの雑音を含んだ形態を受信する。
【００１９】
図５を参照して、データシンボルＸｉの推定値を生成するためにデータシンボルＸｉ、Ｙｉ、およびＺｋの、雑音を含んだ形態を復号するための復号器５００に関するブロック線図が示される。復号器５００は、システム１０における復号器２０内で用いられるかも知れない。符号化されたデータシンボルＸｉ、Ｙｉ、およびＺｋの雑音を含んだ形態は、入力５４２における復号ブロック５０１へのルーチングのために、データシンボルＸｉおよびＹｉの雑音を含んだ形態を選定するために動作する、データシンボル選択器ブロック５２０を通過するかも知れない。データシンボルＸｉの雑音を含んだ形態は、局部的にデータシンボルＸｋの雑音を含んだ形態を再生成するためにインターリーバ５９９を内部的に通過する。局部的に生成されたデータシンボルＸｋおよびＺｋの雑音を含んだ形態は、入力５４０において復号器ブロック５０２に通される。復号器５０１は、説明されそして示されたようにＭＡＰ等の復号処理に従って、データシンボルＸｉおよびＹｉの雑音を含んだ形態を復号することが可能である。復号器５０１は、出力５５０においてデータシンボルＸｉの推定値を生成する。復号器５０２は、説明されそして示されたようにＭＡＰ等の復号処理に従って、データシンボルＺｋおよびＸｋの雑音を含んだ形態を復号する。復号器５０２は、出力５６０においてデータシンボルＸｋの推定値を生成する。復号器５０１および５０２内の復号処理は連続的に実行されるかも知れない。情報は、各反復の終了後に復号器５０１から復号器５０２に通されるかも知れない。当業界において通常に熟練した人は、記述されそして示されたような種々の実施例における復号器は、符号化されたデータシンボルの雑音を含んだ形態上で動作することを正しく評価するであろう。
【００２０】
真の値を保持するために、データシンボルＸｉの推定値に対する信頼性を増加するために、出力５５０においてデータシンボルＸｉの推定値は、復号器５０２の入力５３２においてデータシンボルＸｋの推定値を生成するためにインターリーバ５３０を通過するかも知れない。復号器５０２は、出力５６０においてデータシンボルＸｋの新しい推定値を生成するために、入力５４０におけるデータシンボルの推定値と共に、入力５３２におけるデータシンボルＸｋの推定値を使用する。出力５６０におけるデータシンボルＸｋの推定値は、ターボ符号４００内のインターリーバ４３０のインターリービング機能の処理を反転するために、そして入力５４１においてデータシンボルＸｉの推定値を生成するためにデインターリーバ５３１を通過する。入力５４１におけるデータシンボルＸｉの推定値は、出力５５０においてデータシンボルＸｉの新しい推定値を生成するために入力５４２におけるデータシンボルの推定値と共に用いられる。処理はデータシンボルＸｉの推定値に対する信頼度が満足できるレベルに達するまで繰り返されるかも知れない。このように、データシンボルＸｉの復号のための処理は時間を消費するものであり、そして通信システム１０における応用に対して間に合うような方法で、データシンボルＸｉの正確な推定値を生成しないかも知れない。
【００２１】
図６を参照して、図表６００は、通信システム１０内で使用されることが可能な本発明の種々の実施例に従った復号器内の信号および情報の流れを示す。図表６００に述べられた復号動作はターボ符号に従って送信機において符号化されているデータシンボルのシーケンスを復号するのに適している。図４に示されたターボ符号器４００は、ターボ符号に従ったデータシンボルのシーケンスの符号化に対する典型的な実施例である。復号器２０のような本発明の実施例と組み合わせられた復号器は、本発明の種々の観点から非常に有益である。本発明の一つの実施例は、高い信頼度をもってデータシンボルＸｉの正確な推定値を決定するための高速復号動作を与える。本発明の種々の実施例に従った図表６００における信号および情報に関する流れの種々の観点をフォローするために、いくつかの表示が定義されるかも知れない。データシンボルＸｉによって形成されたデータシンボルのシーケンスは長さＮのバイナリシンボルであることが可能である。Ｎに対する値は、任意の有限の数値であることが可能である。第１の要素符号４０１に対する時刻インデックスは、１およびＮの間の数値を有する“ｉ”に対する“Ｉ”であることが可能である。データシンボルＹｉおよびＺｋもまた長さＮのバイナリシンボルであることが可能である。第２の要素符号４０２に対する時刻インデックスは、１およびＮの間の数値を有する“ｋ”に対する“ｋ”であることが可能である。“ｋ”に対する値は、符号インターリーバ４０３におけるインターリービング後の時刻インデックス“ｉ”のイメージである。
【００２２】
図６を参照して、シンボルＸｉノード６０１は、時刻“ｉ”における第１の要素符号４０１の入力におけるデータシンボルと組み合わせられたシンボルノードであるかも知れない。シンボルＹｉノード６０２は、時刻“ｉ”における第１の要素符号４０１の出力におけるデータシンボルと組み合わせられたシンボルノードであるかも知れない。シンボルＺｋノード６０３は、時刻“ｋ”における第２の要素符号の出力におけるデータシンボルと組み合わせられたシンボルノードであるかも知れない。時刻“ｉ−１”および“ｉ”における第１の要素符号４０１と組み合わせられたトレリスの状態ノード（state node）は、それぞれ状態Ｓｉ−１ノード６０４および状態Ｓｉノード６０５によって表されることが可能である。時刻“ｋ−１”および“ｋ”における第２の要素符号４０２と組み合わせられたトレリスの状態ノードは、それぞれ状態σｋ−１ノード６０６および状態σｋノード６０７とによって表されることが可能である。時刻“ｉ−１”、“ｉ”、および“ｉ＋１”における第１の要素符号４０１と組み合わせられた計算上のノードは、それぞれＣｉ−１ノード６０８、Ｃｉノード６０９、およびＣｉ＋１ノード６１０によって表されることが可能である。時刻“ｋ−１”、“ｋ”、および“ｋ＋１”における第２の要素符号４０２と組み合わせられた計算上のノードは、それぞれＤｋ−１ノード６１１、 Ｄｋノード６１２、Ｄｋ＋１ノード６１３によって表されることが可能である。チャネルＲｘノード６１４は、受信されたデータシンボルＸｉと組み合わせられる。チャネルＲｙノード６１５は、受信されたデータシンボルＹｉと組み合わせられる。チャネルＲｚノード６１６は、受信されたデータシンボルＺｋと組み合わせられる。
【００２３】
図表６００において、ブランチは２個のノードを接続することが可能である。一つのブランチは、ソースノードから宛先ノードへのメッセージを搬送することが可能である。一般的に、もしもαおよびβが任意の２個のノードである場合は、表示Ｍ（α，β）はノードαからノードβへのメッセージを表す。たとえば、ブランチ６５１は、Ｘｉノード６０１等のシンボルノードを、Ｃｉノード６０９等の計算上のノードに接続することが可能である。ブランチ６５１は、ソースノード、Ｘｉ６０１から宛先ノード、 Ｃｉノード６０９へメッセージを搬送することが可能である。その結果、ブランチ６５１によって搬送されたメッセージは、Ｍ（ Ｘｉ ， Ｃｉ ）として表される。シンボルノード６０１、シンボルノード６０２、およびシンボルノード６０３に接続されたブランチは、１個の数字を含むメッセージを搬送する。シンボルノードに接続されたブランチは、ハードウエア、ファームウエアあるいはソフトウエア、あるいはこれらの組み合わせの中に、レジスタあるいは変数、あるいはこれらの組み合わせとして実現することが可能である。レジスタあるいは変数によって保持される値は、ブランチによって搬送されたメッセージを示すことが可能である。
【００２４】
状態Ｓｉノード６０５、状態Ｓｉ−１ノード６０４、状態σｋ−１ノード６０６、および状態σｋ６０７ノードに接続されたブランチは、数字の配列を含むメッセージを搬送する。数字の配列は接続する状態ノードと組み合わせられたトレリス内の状態の数に等しい長さを有することが可能である。対応する要素符号と組み合わせられた符号器は状態の数を確立することが可能である。たとえば、要素符号４０１は、各時刻の段階における各状態空間に４個の状態を有している。その結果、数の配列は４個の数を含み、ここで、一つの数は状態空間における各状態に対する。状態ノードに接続されたブランチは、ハードウエア、ファームウエアあるいはソフトウエア、あるいはこれらの組み合わせの中に、レジスタあるいは変数、あるいはこれらの組み合わせとして実現することが可能である。レジスタあるいは変数によって保持された値は、ブランチによって搬送されたメッセージを示すことが可能である。
【００２５】
一般的に、ノードはいくつかの入力および出力をもった論理回路の形で、ハードウエア内に実現することが可能である。ノードはまた、機能あるいはサブルーチンの形で、ソフトウエア／ファームウエア内に実現されることが可能である。ノードはいつでも、いかなる情報も記憶しあるいは保存する必要はないかも知れない。ノードは到来メッセージによって“更新される”かも知れない。ノードが“更新される”場合、ノードはその到来ブランチにおけるメッセージの現在の値に基づいてその出発ブランチのすべてに、メッセージを出力する。ノードの出発ブランチ上のメッセージの形式は、またノードの形式によって異なる。
【００２６】
チャネルノード６１４‐６１６は、対応するデータシンボルと組み合わせられたチャネル出力を受信することによって更新される。復調器１９内の相関器は、各データシンボルに対するチャネル出力を出力するかも知れない。たとえば、データシンボルＸｉ、Ｙｉ、およびＺｋと組み合わせられたチャネル出力は、それぞれチャネルノード６１４、６１５、および６１６を更新する。チャネルノードが更新される場合、メッセージがチャネルノードから組み合わせられたシンボルノードへ通される。たとえば、データシンボルＸｉの場合、データシンボルＸｉと組み合わせられたチャネルノード６１４において、 Ｘｉチャネル出力を受信した後、チャネルノード６１４は、チャネルノード６１４からシンボルノード６０１へメッセージを通すことによって更新される。チャネルノード６１４からシンボルノード６０１へ通されたメッセージは、シンボルＸｉチャネル出力の対数‐尤度比(log-likelihood ratio)、
【００２７】
【数１】
2005528811.tif 000003
に等しいことが可能である。たとえば、もしもシンボルＸｉが、１は正の電圧として送信され、そして０は負の電圧として送信されるようにＢＰＳＫ変調され、そして実数ｒｉによって示される電圧としてＡＷＧＮチャネル上で受信される場合は、そこでメッセージは
【００２８】
【数２】
2005528811.tif 000004
に等しいことが可能である。ここで、Ｅｓ／Ｎ０はチャネルのシンボルＳＮＲを表す。ある時刻の段階におけるデータシンボルに対してチャネルノードは一度だけ更新されることを必要とする。チャネルノードはチャネル出力を受信することによって更新されることが可能である。
【００２９】
シンボルノードは、接続ブランチ上のメッセージを受信することによって更新されるかも知れない。シンボルノードはいくつかのノードに接続されるかも知れない。たとえば、シンボルノードＸｉ６０１は、チャネルノード６１４、Ｃｉノード６０９、およびＤｋノード６１２に接続される。シンボルノードが更新される場合、出発メッセージは到来メッセージの和によって決定される。次の表示が有用であるかも知れない。シンボルノードαが更新される場合、シンボルノードαからの出発メッセージは次のように推定される。
【００３０】
【数３】
2005528811.tif 000005
総和はノードαと接続されている他のノード（β′）からの到来メッセージのすべてについてである。ノードαの更新をトリガしたノードβからの到来メッセージＭ（β，α）は、ノードαからノードβへの出発メッセージＭ（α，β）の決定には用いられない。シンボルノードＸｉ６０１の場合、ノードはメッセージが到来ブランチ６５０、６５３、および６５９上で受信される場合に更新される。ブランチ６５０は、 Ｃｉノード６０９からのメッセージＭ（Ｃｉ，Ｘｉ）を搬送する。ブランチ６５３は、Ｄｋノード６１２からのメッセージＭ（Ｄｋ，Ｘｉ）を搬送する。ブランチ６５９は、チャネルノード６１４からのメッセージＭ（Ｒ， Ｘｉ）を搬送する。 Ｃｉノード６０９への出発メッセージは、ブランチ６５１上で搬送される。 Ｄｋノード６１２への出発メッセージは、ブランチ６５２上で搬送される。もしも更新がブランチ６５０上でのメッセージＭ（Ｃｉ，Ｘｉ）の受信による場合は、出発メッセージＭ（Ｘｉ，Ｃｉ）はブランチ６５１上には送出されず、その結果ブランチ６５２上への出発メッセージＭ（Ｘｉ，Ｄｋ）のみが送出される。シンボルノードからチャネルノードへの出発メッセージは存在しない。もしも更新がブランチ６５９上でのメッセージＭ（Ｒ，Ｘｉ）の受信に起因する場合は、ブランチ６５２上でＤｋノード６１２に送出されたメッセージは、チャネルノードＲｘ６１４からのメッセージＭ（Ｒ，Ｘｉ）およびＣｉノード６０９からのメッセージＭ（Ｃｉ，Ｘｉ）からの寄与を有しているであろう。同様にもしも更新がブランチ６５９上でのメッセージＭ（Ｒ，Ｘｉ）の受信に起因する場合は、ブランチ６５１上でＣｉノード６０９に送出されたメッセージは、チャネルノードＲｘ６１４からのメッセージＭ（Ｒ，Ｘｉ）およびＤｋノード６１２からのメッセージＭ（ Ｄｋ，Ｘｉ）からの寄与を有しているであろう。
【００３１】
一つの実施例においては、共通の時刻の段階と組み合わせられた到来メッセージは、ノードに本質的には同時に到着される。その結果、出発メッセージは共通の時刻の段階と組み合わせられたすべての到来メッセージを有することによってトリガされる。時刻の段階と組み合わせられた到来メッセージは、メッセージが本質的に同時に各ノードに到着されない場合は、他の時刻の段階と組み合わせられた出発メッセージをトリガしない。
【００３２】
状態ノードもまた接続されたブランチ上でメッセージを受信することによって更新されるかも知れない。状態ノードを更新するために、状態ノードは受信されたメッセージを、到来ブランチ上の接続された計算上のノードから、出発ブランチ上の他の接続された計算上のノードに通す。状態ノードは計算上のノードのみに接続される。状態ノードは基本的には計算上のノードからの到来メッセージを、他の計算上のノードに通す。状態Ｓｉノード６０５は、計算上のＣｉノード６０９およびＣｉ＋１ノード６１０に接続される。状態Ｓｉ−１ノード６０４は、Ｃｉ−１ノード６０８およびＣｉノード６０９に接続される。状態Ｓｉノード６０５がＣｉノード６０９からの到来ブランチ６６５上でメッセージＭ（Ｃｉ，Ｓｉ）を受信することによって更新される場合は、メッセージＭ（Ｃｉ，Ｓｉ）は、Ｃｉ＋１ノード６１０への出発ブランチ６６７上のメッセージＭ（Ｓｉ，Ｃｉ＋１）として通される。状態Ｓｉノード６０５が、到来ブランチ６６８上でメッセージＭ（Ｃｉ＋１，Ｓｉ）を受信することによって更新される場合は、メッセージＭ（Ｃｉ＋１，Ｓｉ）は、Ｃｉノード６０９への出発ブランチ上のメッセージＭ（Ｓｉ，Ｃｉ）として通される。同様な動作が、状態Ｓｉ−１ノード６０４、状態σｋノード６０７、および状態σｋ−１ノード６０６を更新する場合に実行される。
【００３３】
計算ノードにおける出発メッセージの推定値を記述するために、要素符号と組み合わせられたトレリスに関する若干の表示が述べられる。トレリスの各ブランチは状態ｓを状態ｔに接続し、そして第１および第２の要素符号４０１および４０２の場合２個のバイナリシンボルで名づけられる。状態のある対のみがトレリス内に接続される。第１の要素符号４０１と組み合わせられたトレリス内の各ブランチは、（ｆ〔ｓ，ｔ〕，ｇ〔ｓ，ｔ〕）として表示される。同様に、第２の要素符号４０２と組み合わせられたトレリスの各ブランチは、状態ｓを状態ｔに接続しており、（ｆ′〔ｓ，ｔ〕，ｇ′〔ｓ，ｔ〕）として表示される。 ｆ〔ｓ，ｔ〕は第１の要素符号４０１と組み合わせられた体系的なシンボル（すなわちＸｉ）を示し、そしてｇ〔ｓ，ｔ〕はパリティシンボル（すなわちＹｉおよびＺｋ）を示す。 ｆ′〔ｓ，ｔ〕は第２の要素符号４０２と組み合わせられた体系的なシンボル（すなわちＸｉ ）を示し、そしてｇ′〔ｓ，ｔ〕はパリティシンボル（すなわちＹｉおよびＺｋ）を示す。当業界において通常に熟練した人は、データシンボルＸｉは体系的シンボルであり、そしてＹｉおよびＺｋはターボ符号と組み合わせられたパリティシンボルであることを正しく評価するであろう。
【００３４】
計算ノードから状態ノードへの出発メッセージは、数字の配列の形態である。説明したように、状態ノードはメッセージを一つの計算ノードから他へと通す。その結果、状態ノードからの出発メッセージはまた、数字の配列の形態である。配列の長さは、トレリスの各状態空間内の状態の数に等しい。たとえば、計算上のノードＣｉ６０９から状態Ｓｉノード６０５へのメッセージＭ（Ｃｉ，Ｓｉ）の場合、 Ｍ（Ｃｉ，Ｓｉ）〔ｓ〕は、メッセージＭ（Ｃｉ，Ｓｉ）における数字の配列のｓ番目の成分を示す。同様に、Ｍ（Ｓｉ，Ｃｉ）〔ｓ〕は、状態ノードから計算ノードへのメッセージＭ（Ｓｉ，Ｃｉ）のｓ番目の成分を示す。計算Ｃｉノード６０９からの出発メッセージは、次のように推定される。
【００３５】
【数４】
2005528811.tif 000006
ここで総和は、状態ｓおよびｔに対して、トレリス内に状態ｓから状態ｔへのブランチがあるように制約される。計算上のＣｉノード６０９からシンボルノードＹｉ６０２への出発メッセージは、ブランチ６５７が（破線で）たとえ示されていても存在しないかも知れない。シンボルノードＹｉ６０２はメッセージをＣｉノード６０９のみに送出するために、ノードＹｉ６０２はＣｉノード６０９からはメッセージを受信しない。同様に、計算ノードＤｋ６１２からのメッセージは、次のように推定される。
【００３６】
【数５】
2005528811.tif 000007
計算上のノードＤｋ６０９からシンボルノードＺｋへの出発メッセージは、ブランチ６５４が（破線で）たとえ示されていても存在しないかも知れない。シンボルノードＺｋ６０３はメッセージをＤｋノード６０３のみに送出するために、ノードＺｋ６０３はＤｋノード６０３からはメッセージを受信しない。
【００３７】
上記の計算は、通常
【００３８】
【数６】
2005528811.tif 000008
によって定義される基本的数学的演算を用いる。
上記のｎ配列演算はバイナリ演算
【００３９】
【数７】
2005528811.tif 000009
の連結として実現可能であることは容易に知られるであろう。
さらにバイナリ演算は
【００４０】
【数８】
2005528811.tif 000010
として実現が可能である。
実用上、関数ψ（｜ｕ１−ｕ２｜）は、小さいルックアップテーブルを用いて近似される。計算ノードが“トリガされた”場合は、次のステップが順に起きることが可能である。（１）計算ノードに接続されたすべての状態ノードおよびシンボルノードが更新され、そして（２）計算ノードそれ自身が更新される。
【００４１】
種々の実施例に従ったメッセージ通過復号アルゴリズム(message passing decoding algorithm)は、すべてのチャネルノードを一度更新し、そしてそこでトリガリング計画に従って計算ノードをトリガすることを含む。典型的には、計算ノードは、復号処理の期間中、計画に従って数回トリガされる。計算ノードからの出発メッセージは初期化され、そして更新トリガが計画される。
【００４２】
初期化処理の間、すべての計算ノードからシンボルノードへのメッセージは０に初期化される。すべての計算ノードから状態ノードへの出発メッセージの各成分は、−ｌｏｇ（Ｍ）に初期化される。ここでＭはトレリスの各状態空間内の状態の数である。もしも要素符号器が符号化に先立って０の状態にあることが知られる場合は、そこで処理は、時刻“０”において、トレリスセクション内のすべての０でない状態ｓに対して、Ｍ（Ｃ０，Ｓ０）［０］＝Ｍ（Ｄ０，σ０）［０］＝０、およびＭ（Ｃ０，Ｓ０）［ｓ］＝ Ｍ（Ｄ０，σ０）［ｓ］＝−∞、と初期化する。同様に、もしも要素符号器が符号化の終期において０の状態にあることが知られる場合は、処理はすべての０でない状態ｓに対して、Ｍ（ＣＮ＋１，ＳＮ）［０］＝Ｍ（ＤＮ＋１，σＮ）［０］＝０、およびＭ（ＣＮ＋１，ＳＮ）［ｓ］＝Ｍ（ＤＮ＋１，σＮ ）［ｓ］＝−∞と、初期化する。
【００４３】
図７を参照して、図表７００は、本発明の種々の実施例に従った異なった時刻の段階に対応する異なったノード間のメッセージの流れを示す。符号化されたデータシンボルＸｉ、Ｙｉ、およびＺｋと組み合わせられたチャネル出力は、復調器１９内の記憶エレメント内に保存されることが可能である。このように、異なった時刻段階に対する符号化されたデータシンボルＸｉ、Ｙｉ、およびＺｋと組み合わせられたチャネル出力は、復号処理に対してすべて同時に利用可能となることが可能である。時刻段階“ｉ−１”、“ｉ”、および“ｉ＋１”に対応するデータシンボルＸｉ−１、Ｘｉ、およびＸｉ＋１と組み合わせられたチャネル出力は、シンボルノード７０１に通過する。状態Ｓｉ−２、Ｓｉ−１、Ｓｉ、およびＳｉ＋１ノード７０２はまた、計算上のＣｉ−２、Ｃｉ−１、Ｃｉ、Ｃｉ＋１、およびＣｉ＋２ノード７０４と接続するために形成されるかも知れない。状態σｋ−２、σｋ−１、σｋおよび、σｋ＋１ノード７０５もまた、計算上のＤｋ−２、Ｄｋ−１、 Ｄｋ、Ｄｋ＋１、およびＤｋ＋２ノード７０６と接続するために形成されるかも知れない。時刻段階“ｉ−１”、“ｉ”、および“ｉ＋１”に対応する、データシンボルＹｉ−１、Ｙｉ、およびＹｉ＋１と組み合わせられたチャネル出力は、シンボルノード７０７に通過する。時刻段階“ｋ−１”、“ｋ”、および“ｋ＋１”に対応する、データシンボルＺｋ−１、Ｚｋ、およびＺｋ＋１と組み合わせられたチャネル出力は、シンボルノード７０８に通過する。図表７００は３個の時刻段階に対応するメッセージ通過流れを示しているが、当業界において通常に熟練した人は、図表７００は１からＮに対するすべての時刻段階を含むように拡張が可能であることを正しく認識するであろう。一つの実施例に従って、すべての計算ノード７０４および７０６は本質的に同時にトリガされることが可能である。このように、一つのステップ内ですべての計算上のノードは一度更新される。各時刻にすべての計算上のノードは更新され、復号処理は復号化の反復上で完了していることが可能である。計算上のノード７０４および７０６に関する同時のトリガは、復号処理の１個あるいはそれ以上の反復を達成するために繰り返されることが可能である。
【００４４】
他の実施例においては、計算上のノードは、フルＭＡＰ復号化を用いて従来のターボ復号アルゴリズムの単一の反復を得るために、Ｃ０、Ｃ１、Ｃ２、…、ＣＮ、ＣＮ−１、ＣＮ−２、ＣＮ−３、…、Ｃ２、Ｃ１、Ｃ０、Ｄ０、Ｄ１、Ｄ２、…、ＤＮ，ＤＮ−１、ＤＮ−２、ＤＮ−３、…、Ｄ２、Ｄ１、Ｄ０の順序でトリガされることが可能である。計算ノードＣ０、Ｃ１、Ｃ２、…、ＣＮのシーケンスはいくつかの部分的に重畳するサブブロックに分割されることが可能であり、そしてノードは各サブブロック内で順々に、しかしすべてのサブブロックに亙っては同時にトリガされる。第１の要素符号に関するスライディングブロックＭＡＰ復号化に対する精密な近似を得ることが可能である。ノードＤ０、Ｄ１、Ｄ２、…、ＤＮは、スライディングブロックＭＡＰ復号化を用いて標準のターボ復号アルゴリズムに関する近似を得るのと同じ方法でトリガされるかも知れない。
【００４５】
一般的に計算ノードの（重畳している）サブセットの任意の集合が定義されるかも知れず、そしてサブセットがトリガされる順序もまた定義されるかも知れない。各サブセットの中で、ノードは任意の順序で、あるいは同時にトリガされるかも知れない。あるいは、順序は、サブセット内の各計算ノードに関するトリガと一致するように規定されるかも知れない。異なったサブセットが任意の順序で、あるいは同時にトリガされるかも知れない。すべての計算上のノードが一度トリガされる場合に、復号反復が起きると定義される。完全な復号処理はいくつかの反復を含むかも知れない。第１の要素符号に関する計算ノードのトリガリングのいくつかの反復の後に、第２の要素符号に関する計算ノードが同様にトリガされるかも知れない。処理はまた、実施例に従ってあらかじめ定義された反復数の後に完了されるかも知れない。処理はまた、実施例に従って動的な形態におけるいくつかの反復の後に完了されるかも知れない。処理は体系的なデータシンボル（Ｘｉ）の満足できる組が満足できる品質レベルで生成される場合に完了される。シンボルノードＸｉ６０１におけるデータシンボルＸｉの値は、各反復の後に巡回冗長検査（ＣＲＣ）を通るかも知れない。もしもＣＲＣを通過する場合は、復号動作は完了することが可能であり、そして付加的な反復は必要とされないことが可能である。
【００４６】
当業界において熟練した人々は、ここに開示された実施例に関連して記述された、種々の例証となる論理ブロック、モジュール、回路、およびアルゴリズムステップは、電子的ハードウエア、計算機ソフトウエア、あるいは両者の組み合わせとして実現可能であることを正しく評価するであろう。ハードウエア、およびソフトウエアに関するこの互換性を明らかに示すために、種々の例証となるコンポーネント、ブロック、モジュール、回路、およびステップが以上に一般的に、それらの機能の形で記述されてきている。これらの機能がハードウエアあるいはソフトウエアで実現されるか否かは、システム全体に課せられた特定の応用、および設計制約によって異なる。熟練した技術者は、記述された機能を各特定の応用に対して異なった方法で実現するかも知れない。しかしこのような実現の決定は本発明の範囲から逸脱する原因として解釈されるべきではない。
【００４７】
ここに開示された実施例に関連して記述された種々の例証となる論理ブロック、モジュールおよび回路は、汎用処理装置、ディジタル信号処理装置（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＧＰＡ）あるいは他のプログラマブル論理デバイス、ディスクリートゲートあるいはトランジスタ論理、ディスクリートハードウエアコンポーネント、あるいはここに記述された機能を実行するように設計された、任意のこれらの組み合わせで実現されあるいは実行されることが可能である。汎用処理装置はマイクロ処理装置であるかも知れず、しかし代わりに処理装置は任意の従来の処理装置、制御器、マイクロ制御器、あるいはステートマシンであるかも知れない。処理装置はまた、計算デバイスの組み合わせ、たとえば、ＤＳＰおよびマイクロ処理装置の組み合わせ、複数のマイクロ処理装置、ＤＳＰコアを伴った１個あるいはそれ以上のマイクロ処理装置、あるいは任意の他のこのような配列として実現されるかも知れない。
【００４８】
ここに開示された実施例に関連して記述された方法あるいはアルゴリズムのステップは、直接にハードウエア内で、処理装置によって実行されるソフトウエアモジュールの中で、あるいは組み合わせの中で具体化されるかも知れない。ソフトウエアモジュールはＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、抵抗器、ハードディスク、リムーバブルディスク、ＣＤ‐ＲＯＭ、あるいは当業界において知られた記憶媒体の任意の他の形態の中に置かれるかも知れない。典型的な記憶媒体は処理装置が記憶媒体からの情報を読み、そして（記憶媒体に）情報を書き込むことが可能なように処理装置に結合される。代わりに、記憶媒体は処理装置と一体化されるかも知れない。処理装置および記憶媒体はＡＳＩＣ内に置かれるかも知れない。ＡＳＩＣはユーザ端末内に置かれるかも知れない。代わりに処理装置および記憶媒体はユーザ端末内にディスクリートコンポーネントとして置かれるかも知れない。
【００４９】
望ましい実施例に関する以上の記述は、当業界において熟練したいかなる人に対しても本発明を作成しあるいは使用することを可能とする。これらの実施例に対する種々の修正は当業界において熟練した人々に対しては容易に明白であろうし、そしてここに定義された一般的原理は創造的能力を使用することなしに他の実施例に適用が可能である。従って、本発明はここに示された実施例に限定されることを意図したものではなく、しかしここに開示された原理および新しい特徴に一致する最も広い範囲に一致されるべきものである。
【図面の簡単な説明】
【００５０】
【図１】本発明の種々の実施例に従って動作することが可能な通信システムを示す。
【図２】エンコーダに関するブロック線図を示す。
【図３】トレリス線図を示す。
【図４】ターボエンコーダに関するブロック線図を示す。
【図５】復号器に関するブロック線図を示す。
【図６】本発明の種々の実施例に従って符号化されたデータシンボルのシーケンスを復号するための種々の形式のノード間の情報の流れに対する図表を示す。
【図７】本発明の種々の実施例に従って符号化されたデータシンボルのシーケンスを復号するための種々の形式のノード間の情報の流れに対する一般化された図表を示す。
【符号の説明】
【００５１】
１０…通信システム、  １２…符号器、  １４…変調器、  １６…送信機、  １７…加法性白色ガウス雑音（ＡＷＧＮ）チャネル、  １８…受信機、  １９…復調器、  ２０…復号器、  １００…符号器、  １１０…符号器、  １１１…フリップフロップ、  ２００…トレリス、  ２０１…状態空間、  ２０２…状態空間、  ２１１…状態、  ２１２…状態、  ２１３…状態、  ２１４…状態、  ４００…ターボ符号器、  ４０３…符号インターリーバ、  ４１０…入力、  ４３０…インターリーバ、  ５００…復号器、  ５０１…復号器（復号ブロック）、  ５０２…復号器（復号ブロック）、  ５２０…データシンボル選択器ブロック、  ５３０…インターリーバ、  ５３１…デインターリーバ、  ５３２…入力、  ５４０…入力、  ５４１…入力、  ５４２…入力、  ５５０…出力、  ５６０…出力、  ５９９…インターリーバ、  ６０１…シンボルノード、  ６０２…シンボルノード、  ６０３…シンボルノード、  ６０４…ノード、  ６０５…ノード、  ６０６…ノード、  ６０７…ノード、  ６０８…ノード、  ６０９…ノード、  ６１０…ノード、  ６１１…ノード、  ６１２…ノード、  ６１３…ノード、  ６１４…チャネルノード、  ６１５…チャネルノード、  ６１５…ノード、  ６１６…ノード、  ６５０…ブランチ、  ６５１…ブランチ、  ６５２…ブランチ、  ６５３…ブランチ、  ６５４…ブランチ、  ６５７…ブランチ、  ６５９…ブランチ、  ６６５…到来ブランチ、  ６６７…出発ブランチ、  ６６８…到来ブランチ、  ７０１…シンボルノード、  ７０２…ノード、  ７０４…ノード、  ７０５…ノード、  ７０６…ノード、  ７０７…シンボルノード、  ７０８…シンボルノード
【図１】
2005528811.tif 000011
【図２】
2005528811.tif 000012
【図３】
2005528811.tif 000013
【図４】
2005528811.tif 000014
【図５】
2005528811.tif 000015
【図６】
2005528811.tif 000016
【図７】
2005528811.tif 000017
【国際調査報告】
2005528811.tif 000018
2005528811.tif 000019
2005528811.tif 000020