(57)【要約】チャネルのビットストリームを効率的にデコーディングするシステム及び方法が、トレリスベースの演算を実行する。このシステムは、バタフライコプロセッサとデジタル信号プロセッサとを含む。トレリスベースのエンコーダに対して、このシステムは、デジタル信号プロセッサの指示によりバタフライコプロセッサ内で演算を並列で実行することによって、チャネルのビットストリームをデコードする。ＭＡＰアルゴリズムとビタビのアルゴリズムと他のソフト出力又はハード出力のデコーディングアルゴリズムとの実行中に、これらの演算が使用される。ＤＳＰは、バタフライコプロセッサの代わりに、メモリ管理とアルゴリズムのスケジューリングとを実行する。バタフライコプロセッサは、スループットを増加するために並列のバタフライ演算を実行する。システムは、多数の可能なデコーディング環境の中で使用するためにフレキシビリティを維持する。
2004511162.tif 000002
【特許請求の範囲】
【請求項１】
メモリに接続可能なバスを含むデジタル信号プロセッサと、
該デジタル信号プロセッサによってスケジュール化された動作を実行する、前記バスに接続されたバタフライコプロセッサと
を含んでなるシステム。
【請求項２】
前記デジタル信号プロセッサが、要求装置の代わりに前記メモリにアドレスする、前記バスに接続されたデータアドレス発生器をさらに含む請求項１に記載のシステム。
【請求項３】
前記デジタル信号プロセッサが、前記デジタル信号プロセッサの中で算術演算を実行する算術演算装置をさらに含む請求項２に記載のシステム。
【請求項４】
前記算術演算装置が、ブランチメトリック計算を実行するブランチメトリックユニットをさらに含む請求項３に記載のシステム。
【請求項５】
前記算術演算装置が、前記ブランチメトリックユニットが１つ以上の結果を記憶することができる１つ以上のレジスタをさらに含む請求項４に記載のシステム。
【請求項６】
前記データアドレスレジスタが前記算術演算装置内の１つ以上のレジスタにアドレスすることができるものである請求項５に記載のシステム。
【請求項７】
前記バタフライコプロセッサがバタフライ演算を実行する複数のバタフライユニットをさらに含む請求項１に記載のシステム。
【請求項８】
前記バタフライ演算が並列演算である請求項７に記載のシステム。
【請求項９】
前記バタフライコプロセッサ内の前記複数のバタフライユニットが、前記デジタル信号プロセッサの指示で加算−比較−選択の動作をさらに実行するものである請求項８に記載のシステム。
【請求項１０】
前記バタフライコプロセッサ内の前記複数のバタフライユニットが、前記デジタル信号プロセッサの指示で対数加算指数演算の近似をさらに実行する請求項８に記載のシステム。
【請求項１１】
経路メトリック用メモリから読み出された経路メトリックが前記デジタル信号プロセッサの前記データアドレス発生器によってアクセスされる請求項８に記載のシステム。
【請求項１２】
前記デジタル信号プロセッサの前記データアドレス発生器が前記ブランチメトリックユニットからブランチメトリックをさらに読み出す請求項１１に記載のシステム。
【請求項１３】
トレリス図の段階を識別するステップと、
該段階の各ノードに対してブランチメトリックを計算するステップと、
該ブランチメトリックに基づいて前記段階に対する２つ以上の経路メトリックを同時に計算するステップと
を含んでなる方法。
【請求項１４】
前記経路メトリックをメモリに記憶するステップをさらに含む請求項１３の方法。
【請求項１５】
前記段階の各ノードに対してブランチメトリックを計算するステップが、
前記段階内のノード数を識別するステップと、
前記各ノードから伸びるブランチ数を識別するステップと、
前記各ブランチに対してブランチメトリックを計算するステップと
をさらに含む請求項１３に記載の方法。
【請求項１６】
前記ブランチメトリックに基づいて前記段階に対する２つ以上の経路メトリックを同時に計算するステップが、
前記段階のノードを識別するステップと、
前記メモリから、前記ノードに導く前の経路メトリックを読み出すステップと、
前記段階内の前記ノードから伸びるブランチ数を識別するステップと、
前記ノードから伸びる各ブランチに対して、前記前の経路メトリックと前記ブランチメトリックとから新しい経路メトリックを計算するバタフライユニットを割り当てるステップと
をさらに含む請求項１４に記載の方法。
【請求項１７】
トレリス図を用いて記述されるエンコーダによってコード化されたビットストリームをデコードする要求を受け取るステップと、
該トレリス図の段階を識別するステップと、
該段階の全てのノードに対してブランチメトリックを計算するステップと、
メモリから前記トレリス図の異なる段階に対する経路メトリックを読み出すステップと、
前記段階の各ノードに対して新しい経路メトリックを同時に計算するステップと
を含んでなる方法。
【請求項１８】
前記メモリ内の前記段階の各ノードに対する新しい経路メトリックを記憶するステップと、
前記トレリス図の新しい段階を識別するステップと
をさらに含む請求項１７に記載の方法。
【請求項１９】
実行時にプロセッサベースのシステムに対して、
トレリス図の段階を識別させることと、
前記段階の各ノードに対してブランチメトリックを計算させることと、
前記ブランチメトリックに基づいて前記段階に対して２つ以上の経路メトリックを同時に計算させることと
を含むソフトウェアプログラムを記憶している媒体から構成される製品。
【請求項２０】
プロセッサベースのシステムに対して、実行時にメモリ内に前記経路メトリックを記憶させるソフトウェアプログラムをさらに記憶する請求項１９に記載の製品。
【請求項２１】
メモリに接続可能なバスと、
データアドレス発生器と、
算術演算装置と
を含むデジタル信号プロセッサと、
前記バスに接続された、前記デジタル信号プロセッサによってスケジュール化された演算を実行するバタフライコプロセッサと
から構成されるシステム。
【請求項２２】
前記デジタル信号プロセッサが、実行時に、
トレリス図の段階を識別し、
前記段階の中のノード数を識別し、
前記各ノードから伸びるブランチ数を識別する、
ソフトウェアプログラムをさらに含む請求項２１に記載のシステム。
【請求項２３】
前記バタフライコプロセッサが複数のバタフライユニットをさらに含む請求項２２に記載のシステム。
【請求項２４】
前記バタフライユニットの数が前記段階の中の前記ノード数に等しいものである請求項２３に記載のシステム。
【請求項２５】
前記バタフライコプロセッサによって実行された演算が前記段階に対する経路メトリックを計算する動作を含む請求項２４に記載のシステム。
【請求項２６】
前記バタフライユニットが前記段階の各ノードに対して経路メトリックを同時に計算することを特徴とする請求項２５に記載のシステム。
【発明の詳細な説明】
【０００１】
［背景］
本発明は、チャネルコード化データに対して行われるデコーディング動作に関し、より詳細には、トレリス図（ｔｒｅｌｌｉｓ ｄｉａｇｒａｍ）上で動作するデコーダに関する。
【０００２】
システム間の通信は、共通チャネルがシステムに接続するときはいつでも可能である。ネットワークケーブル、電話線、又はインターネットプロトコルのソケットによる場合を問わず、エンティティー間を通信するデータはチャネル媒体を通過する。
【０００３】
残念なことに、チャネル媒体の中の「雑音（ｎｏｉｓｅ）」及び「干渉（ｉｎｔｅｒｆｅｒｅｎｃｅ）」が、送信する間のデータを劣化させることがある。チャネル媒体の長さや、送信されるデータ量や、チャネル内の擬似信号の存在や、他の環境条件等の要因が、雑音及び干渉の量と、これによる受信データの品質とに影響を与えることがある。
【０００４】
チャネル内の雑音及び干渉の現象により、データは送信される前にほとんど常にコード化されると予想される。データエンコーダは、一般に、フリップフロップ及びＮＡＮＤゲート等の個別の論理回路から構成される。このデータエンコーダは、情報ビットとして周知のデータのビットストリームを受信する。これらの情報ビットはチャネル媒体を通って送信され、情報ビット自身に基づいてパリティビットとしてよく知られた付加的なビットを生成する。情報ビットとパリティビットとは共に、コード化されたビットストリームを構成する。
【０００５】
この注意深く設計された冗長的な情報は、前進型誤信号訂正（ｆｏｒｗａｒｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ：以下、「ＦＥＣ」と呼ぶ）又はチャネルコーディング（ｃｈａｎｎｅｌ ｃｏｄｉｎｇ）としてよく知られている。コード化されたビットストリームは、一旦構築されると、チャネルを通って送信される。場合によっては、コード化されたビットストリームを送信する前に変調することができる。
【０００６】
いくつかの「１」ビット（又はその変調された表示）は、チャネル上で送信され続いてレシーバで復調されるとき、「０」ビットを受信したように悪影響を受けることがある。同様に、いくつかの「０」ビットは、「１」ビットとして受信されることがある。近代的なデジタル式無線レシーバでは、復調器はビット単位の「信頼性メトリック（ｒｅｌｉａｂｉｌｉｔｙ ｍｅｔｒｉｃ）」を報告することもできる。明瞭に受信された１及び０は信頼性が高いメトリック（ｍｅｔｒｉｃ）を作り、一方、不明瞭に受信されたデータは信頼性が低いメトリックを産む。コード化されたビットストリームの情報ビット若しくはパリティビット、又はその両方は、送信される間に悪影響を受けることがある。
【０００７】
復調器に加えて、受信エンティティーは、復調器の出力及びエンコーダの構造の知識を用いて、情報ビットが送信された可能性が最も高いと決定することを目的とするデコーダを含む。前述したビット信頼性メトリックは、デコーダの能力を著しく高めることができる。予想されるように、デコーダはエンコーダよりもかなり複雑である。
【０００８】
シャノンの有名なチャネルコーディング定理（ｃｈａｎｎｅｌ ｃｏｄｉｎｇ ｔｈｅｏｒｅｍ、またはチャネル符号化定理）は、ますます複雑になるコード化されたデジタル通信システムに向かって推進するための示唆となる。シャノンの定理は、（毎秒の送信された情報ビット等の）情報速度がチャネル容量を超えない限り、デコーディングエラーの確率を任意に小さくしてＦＥＣコーディングシステムを設計することが可能であると述べている。
【０００９】
しかしながら、シャノンの定理は、漸近的な結果（ａｓｙｍｐｔｏｔｉｃ ｒｅｓｕｌｔ）である。その定理は、（情報ビットの数等の）コーディングのブロック長とコードの複雑性とが無限に向かう傾向があるため、完全なコーディングに近付くことができるということを除いて、実際的なコーディングシステムをどのように設計するかについては、我々には実際にほとんど知られていない。極めて強力な、そのため複雑なコードは、作成が容易であることが分かる。
【００１０】
そして、困難な作業は、これらの複雑なコードに対する効果的なデコーディング（ｄｅｃｏｄｉｎｇ）のアルゴリズムを見つけることである。このため、ＦＥＣコード設計の実際の仕事は、実際に実現する場合に複雑になるデコーダを得るために利用することができる特定の構造を有する強力な（このため、複雑な）コードのファミリーを見つけることである。もちろん、デジタル技術が進歩するにつれて、ますます複雑なデコーダが可能になる。
【００１１】
いくつかのデコーディングアルゴリズムは、トレリス図（ｔｒｅｌｌｉｓ ｄｉａｇｒａｍ）としてよく知られた専用の状態図で動作して、デコードされた出力を発生する。トレリス図は、エンコーダの時間に対する可能な状態遷移を示す状態機械を記述する。トレリス図は、時を違えず各点におけるエンコーダの全ての可能な状態を説明する。多くのデコーディングのアルゴリズムは、チャネルのビットストリームと共にトレリス図を使用して、正しい情報ビットに到達する。
【００１２】
しかしながら、トレリス形（ｔｒｅｌｌｉｓ−ｔｙｐｅ）のデコーディングに関係する計算量は膨大になる。このため、デコーダは、バタフライ演算のような専用のトレリス演算を極めて効率的に実行する特定用途向け集積回路（以下、「ＡＳＩＣ」とよぶ）を用いて実現される。各種のデコーダのアルゴリズムは複雑なため、そのようなＡＳＩＣは、一般に、１つのアルゴリズムに対して設計される。
【００１３】
他のデコーダは、汎用のデジタル信号プロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ：以下、「ＤＳＰ」と呼ぶ）を含む。このデジタル信号プロセッサは、トレリス演算を実行する特殊命令を含んでも含まなくても良い。これらのデコーダは、必要な場合には、種々のデコーディングのアルゴリズムを実行することができるように、プログラム可能でありうる。そのようなデコーダはよりフレキシビリティに富むが、チャネルデータをデコードする速度は、ＡＳＩＣベースのデコーダよりも遅い。
【００１４】
このため、トレリスベースのデコーディング演算（ｔｒｅｌｌｉｓ−ｂａｓｅｄ ｄｅｃｏｄｉｎｇ ｏｐｅｒａｔｉｏｎ）を実行する汎用のデジタル信号プロセッサと共に使用することができる、プログラム可能なプロセッサに対する継続的な必要性が存在する。
【００１５】
［詳細な説明］
本願で説明されるいくつかの実施形態に基づいて、ある種のチャネルのビットストリームをデコーディングするときに使用される専用の演算を効率よく実行するシステム及び方法が開示される。専用の演算は、バタフライ演算としてよく知られている。ビタビ（Ｖｉｔｅｒｂｉ）のデコーディングアルゴリズムとＭＡＰのデコーディングアルゴリズムとが詳細に説明されるが、このシステム及び方法は、トレリス図上で動作する他のデコーディングアルゴリズムを用いて実行することもできる。
【００１６】
本願で説明する動作は、いくつかのトレリスベースのアルゴリズムを実現することに関する。このアルゴリズムのクラスは、通信及び信号処理における多数のアプリケーションの中で使用され、実際には、畳込み及びターボコードのコーディング及びデコーディングと、チャネル等化と、音声のコーディングとを（これらに限定はされないが）含む。本願ではＦＥＣのデコーディングアプリケーションが例証の目的で説明されるが、決して本発明の範囲を限定するものではない。
【００１７】
図１において、１つの実施形態によれば、システム１００は、デジタル信号プロセッサ１０とバタフライコプロセッサ２８とを含む。デジタル信号プロセッサすなわちＤＳＰは、デジタル信号の処理用に調整されたアーキテクチャを有する専用のマイクロプロセッサである。ＤＳＰは、一般に、高速の算術演算と、外部装置への及びそれらからのデータ転送と、メモリへの多重アクセスとを実行することができる回路であることに特徴がある。例えば、ＤＳＰは、平行に伸びた１６ビット又は３２ビットのバスと、メモリにアクセスするための特定のデータアドレス発生器と、乗加算（ＭＡＣ）算術演算装置とを含む。
【００１８】
図１では、ＤＳＰ１０は、２つのバス、すなわち、メモリ記憶バス２２とメモリロードバス２４とを含む。このメモリ記憶バス２２とメモリロードバス２４とは、メモリ３０に接続するためにＤＳＰ１０を超えて伸びる。第２の実施形態では、メモリ記憶バスとメモリロードバス２２及び２４とは、１つのバスとして結合される。
【００１９】
算術演算装置２０は、メモリ記憶バス２２とメモリロードバス２４とに接続される。算術演算装置２０は、１つ以上の乗加算ユニットと、レジスタと、算術演算を実行する他の回路とを含む。データアドレス発生器２６は、メモリ記憶バス２２とメモリロードバス２４にも接続される。データアドレス発生器２６は、ロード又は記憶のどちらかが行われるメモリ３０内の特定の位置を識別する。データアドレス発生器２６は、算術演算装置２０等のＤＳＰ１０の他の回路に代わってこの動作を行う。
【００２０】
１つの実施形態では、システム１００は、バタフライコプロセッサ２８をさらに含む。このバタフライコプロセッサ２８は、ＤＳＰ１０の一部ではないが、メモリ記憶バスとメモリロードバス２２及び２４とによってＤＳＰ１０に接続される。算術演算装置２０と同様に、バタフライコプロセッサ２８はこれらのバスを使用してメモリ３０にアクセスする。本願においてさらに説明するように、システム１００をデコーダの中で使用して、コード化されたチャネルのビットストリームのトレリス図のデコーディングを行うことができる。
【００２１】
特定のＤＳＰ１０は単なる例証である。図１の回路の構成は、システム１００を実現するいくつかの可能な１つを図解するために提供される。図１には示されていないが、ＤＳＰは、一般に、レジスタや制御ブロックや直接メモリアクセス（ＤＭＡ）を行う回路や他の回路等の構成要素をさらに含む。ＤＳＰは、１以上のメモリバスを用いて実行され、周辺装置へのアクセス用などの付加的なバスを特徴とする。
【００２２】
１つの実施形態では、ＤＳＰ１０は、バタフライコプロセッサ２８の代わりに、高速で並列のバタフライ演算を行うメモリ管理を実行する。しかしながら、システム１００を詳細に説明する前に、コーディング技術とデコーディング技術とを紹介すると、本発明を理解する基礎が提供されるであろう。
【００２３】
情報のデータストリームをチャネル媒体を通って送信する場合には、エラーを補正するいくつかの可能な方法がある。例えば、エラー率が極めて高い場合には、送信機の電力がエラー率を減らすために高められる。携帯電話等のいくつかの用途では、利用可能な電池の電力の容量が限られているため、この解決策は役に立たない。
【００２４】
別の解決策は、同じ情報のデータストリームを２回同じチャネル媒体を通って送信すること、又はデータストリームを２つの別のチャネルを通って送信することのいずれかによって、送信を二重にすることである。そして、二重のデータストリームは、レシーバで互いに比較される。しかしながら、冗長性によりシステムに費用が加わることになり、その上、情報のデータストリームを処理する時間が増加する。
【００２５】
第３の可能性は、レシーバが自動再送要求（ａｕｔｏｍａｔｉｃ ｒｅｐｅａｔ ｒｅｑｕｅｓｔ：ＡＲＱ）機構を利用することである。レシーバは、エラーが送信中に発生したと判断すると、データストリームの送信を要求する。しかしながら、これはコード化方式ではないため、雑音が多いチャネルに対する優れた解決策ではない。
【００２６】
前進形誤信号訂正は、情報のデータストリームが送信される前に、付加的なビットがそのデータストリームに加えられる技術である。送信されると、レシーバは、送信の間に発生したどのようなエラーも補正するデコーダを含みうる。
【００２７】
畳込みコードは、２進畳込みコードすなわちＢＣＣと呼ばれることもあり、到来するデータの連続ストリームから生成される。これに対して、ブロックコードは、エンコーダが到来するデータストリームをコード化する前にそれらを固定した長さのブロックへと分割するときに結果として生じる。畳込みコードとブロックコードとの両方は、フォワード・エラー・コレクション（ｆｏｒｗａｒｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ）のコードの種類である。
【００２８】
その上、ブロックコード及び畳込みコードの両方をデコーディングする多くのデコーダが知られている。例えば、畳込みコードをデコーディングするビタビのデコーディングアルゴリズムが良く知られている。ビタビのアルゴリズムは、実際の情報ビットがアルゴリズムの連続的な実行から結果として生ずることを意味する、「ハードな（ｈａｒｄ）」出力アルゴリズムである。あるいはまた、最大事後確率（ｍａｘｉｍｕｍ ａ ｐｏｓｔｅｒｉｏｒｉ ｐｒｏｂａｂｉｌｉｔｙ：ＭＡＰ）アルゴリズムは、チャネルビットの値についての尤度又は「品質（ｑｕａｌｉｔｙ）」情報を発生する「ソフトな（ｓｏｆｔ）」出力アルゴリズムである。
【００２９】
つい最近では、ターボデコーダは、チャネルコード化データに対してより優れた結果をもたらしている。ターボデコーダは、正確な結果を発生する複数のＭＡＰデコーダ等の複数のデコーダを含む。ターボデコーダの１つの実施例は、以下の図１６で説明される。
【００３０】
図２において、エンコーダ５０は、単純で帰納的なシステム化された畳込み（ｒｅｃｕｒｓｉｖｅ ｓｙｓｔｅｍａｔｉｃ ｃｏｎｖｏｌｕｔｉｏｎａｌ：以下、「ＲＳＣ」とよぶ）エンコーダである。システマティックコード（ｓｙｓｔｅｍａｔｉｃ ｃｏｄｅ）は、パリティビットＰｋ＋１が情報ビットＵｋ＋１に連続グループとして加えられるコードである。図２のエンコーダ５０は、システマティックコードを発生する。エンコーダ５０は、出力値Ｐｋ＋１が後で処理するために入力値Ｕｋにフィードバックされるため帰納的である。
【００３１】
ＲＳＣエンコーダ５０では、情報ビットＵｋは排他的ＯＲすなわちＸＯＲのゲート５６に送られる。そして、結果がシフトレジスタ５２へと送られる。シフトレジスタ５２の前の値、すなわち、「１」又は「０」のいずれかは、第２のシフトレジスタ５４に送られる。コードワードビットＵｋ＋１及びＰｋ＋１は、シフトレジスタ５２及び５４の中に記憶されるときの現在の状態及び入力値Ｕｋの関数として生成される。図２のエンコーダ５０では、コードワードビットＵｋ＋１は、入力値Ｕｋとたまたま同じである。しかしながら、パリティビットＰｋ＋１は、状態（シフトレジスタ５２及び５４）と入力値Ｕｋとの両方から結果として発生する。Ｕｋ＋１及びＰｋ＋１は、共に、時間ｋ＋１に対するコードワードビットである。
【００３２】
畳込みコードでは、各コードビットの対（Ｕｋ＋１，Ｐｋ＋１）は、このように、入力値に依存する。この入力値Ｕｋは、シフトレジスタ５２及び５４の値であるだけでなく、複数の情報ビットの１つである。シフトレジスタ５２及び５４は、入力値Ｕｋの過去の値についての情報を記憶する。情報のデータストリームの長さまでのｎ＝１に対する連続的なビット（Ｕｋ＋ｎ，Ｐｋ＋ｎ）は、このため、過去のビットとは無関係ではない。
【００３３】
図３において、状態遷移表６０は、各入力Ｕｋ（列１）に対して、エンコーダ５０の状態としてもよく知られる、シフトレジスタ５２及び５４の中に記憶された値を特徴にしている。この状態遷移表６０は、入力値Ｕｋ（列２）から結果として生ずる、図２のＲＳＣエンコーダ５０が発生したビット（Ｕｋ＋１，Ｐｋ＋１）をさらに特徴とする。状態遷移表６０は、時間ｋ（列１）と時間ｋ＋１（列３）との両方におけるエンコーダ５０の状態を示す。状態遷移表６０は、このように、シフトレジスタ５２及び５４の中に記憶された状態の情報を提供するだけでなく、所定の入力値Ｕｋに対するエンコーダ５０の出力値Ｕｋ＋１，Ｐｋ＋１の完全な表示を行う。
【００３４】
状態遷移表６０から、図４に示すように、トレリス７０を生成することができる。トレリスは、２つの状態間のエンコーダの可能な遷移を示す状態機械である。図４のトレリス７０は、００と、０１と、１０と、１１とラベルが付けられた、段階ｋにおける４つのノード７２ｋから成る。（表示７２ｓｔａｇｅは、特定の段階における全てのノード７２を説明するために使用される。）
【００３５】
トレリス７０は、段階ｋ＋１において、同様に００と、０１と、１０と、１１とラベルが付けられた４つのノード７２ｋ＋１をさらに含む。段階００と段階０１と段階１０と段階１１とは、エンコーダ５０のシフトレジスタ５２及び５４内の値に対応する。ノード７２ｋ及び７２ｋ＋１は、図３の状態遷移表６０の、それぞれ列１及び列３に示すように、ｋ及びｋ＋１におけるエンコーダ５０の状態をそれぞれ示す。
【００３６】
ノード７２ｋをノード７２ｋ＋１に接続する線はブランチ７４である。２つのブランチ７４は、Ｕｋに対して２つの可能な値０又は１があることを示し、全ての４つの可能な状態００と０１と１０と１１から伸びている。
【００３７】
トレリス７０の各ブランチ７４上に、入力値Ｕｋと、出力ビットＵｋ＋１，Ｐｋ＋１とを形式（Ｕｋ，Ｕｋ＋１Ｐｋ＋１）で示す。各ブランチ７４は、ブランチ７４の左側の状態（段階ｋ）からブランチ７４の右側の状態（段階ｋ＋１）への、入力値Ｕｋに対するエンコーダ５０の遷移を関連付ける。
【００３８】
トレリスと同様に、トレリス図はエンコーダの動作を説明するために使用される状態機械である。しかしながら、トレリス図は、エンコーダの時間に対する可能な状態遷移を説明する。図５では、トレリス図８０は、図２のＲＳＣエンコーダ５０に対する可能な状態遷移を含む。トレリス図８０は、図４のトレリス７０の単なる直列の連結である。
【００３９】
４つの状態７２がトレリス図８０の中でも可能である、すなわち、００，０１，１０及び１１（状態７２はエンコーダ５０のシフトレジスタ５２及び５４に対応することを思い出してほしい）。変数ｋは、トレリス図８０の段階を示す。各段階は時間における別個の点である。トレリス図の開始の時間０ではｋ＝０、その後の時間の点ではｋ＝１、以下同様である。トレリス図８０は、エンコーダ５０に送られた情報ビットＵｋの数に対応する、数百さらには数千もの段階を含むことがある。図５では、トレリス図８０の始めの１０段階が示されている。
【００４０】
図４のトレリス７０と同様に、トレリス図８０は、各段階ｋにおいて４つのノード７２を含む。状態００，０１，１０及び１１が、トレリス図８０の左側の列に順次列挙されている。段階ｋにおける４つのノード７２のそれぞれは、状態００，０１，１０及び１１の１つを示す。さらに、各ノード７２から伸びる線はブランチ７４であり、ノード７２ｋからノード７２ｋ＋１への各遷移を示す。
【００４１】
０番目の状態では、２つのブランチ７４だけが、状態００を示すノード７２から伸びている。１つの実施形態では、エンコーダ５０が、シフトレジスタ５２内の０の値とシフトレジスタ５４内の０の値とを用いてコード化を開始するものと仮定される。このため、０番目の段階の残りの状態０１と１０と１１とは「不可能」であり、これらの状態からはブランチが伸びることはない。
【００４２】
次の段階（ｋ＝１）では、ブランチ７４は状態００及び状態１０を示すノード７２から伸びる。その理由は、これらのノードは、入力値がそれぞれ０及び１の場合には、０番目の段階からの遷移が可能であるためである。状態１０から、ブランチ７４は他の２つの可能な状態０１及び状態１１に伸びる。このため、ｋ＝２になると、段階ｋからｋ＋１の各々は、同一であり、図４のトレリス７０で示したものと正確に同じになる。
【００４３】
トレリス図８０は、エンコーダ５０の完全な表示、すなわち、入力値と状態と出力値との表示を行う。図６のように、各段階ｋにおいてブランチ７４を結合することによって、経路８２は、２進の入力値８４、１１１１００００１に対して、ｋ＝９においてコード化された２進の出力コードワード８６、１０１１１０１００１０１０００１１１を示す。しかしながら、経路８２は、トレリス図８０を通る多くの可能な経路の１つだけを示す。
【００４４】
図２のエンコーダ５０が、図６に示すように、値が１１１１００００１の９ビットの情報データストリーム８４を受信し、値が１０１１１０１００１０１０００１１１の１８ビットの２進畳込みコードワード８６を発生すると仮定する。そして、図７に示すように、コードワード８６は、チャネル媒体９０を通ってデコーダ９６を含むレシーバ９４に送信される。デコーダ９６はチャネルのビットストリーム９２を受信するが、このチャネルのビットストリーム９２は畳込みコードワード８６と同じビットストリームであっても異なっていても良い。
【００４５】
デコーダ９６は、チャネルのビットストリーム９２から情報のデータストリーム９８を発生する。この情報のデータストリーム９８が情報のデータストリーム８４と同一であれば、デコーダ９６はチャネルのビットストリーム９２を首尾良くデコードしたことになる。
【００４６】
チャネル媒体９０内の雑音又は他の現象のために、チャネルのビットストリーム９２は、チャネル９０を通って送られたコードワード８６とは異なることが多い。しかしながら、畳込みワード８６は、情報ビット（Ｕｋ）だけでなく、当初の情報ビットに基づいたパリティビット（Ｐｋ）も含んでいる。いくつかのビットが異なる可能性があるが、チャネルのビットストリーム９２は同様に情報ビットとパリティビットとの両方を含んでいる。デコーダ９６は、正しい情報のデータストリーム９８を抽出するために、エンコーダの「青写真（ｂｌｕｅｐｒｉｎｔ）」を提供するトレリス図だけでなく、この情報も使用する。
【００４７】
トレリス図を使用するデコーディングの基本的な考え方は、コード化の順序は図６のトレリス図８０内の経路８２等の経路と等価であるということである。このため、この経路は、エンコーダ５０に対する入力順序Ｕｋと、ブランチ７４上で指定されるように、エンコーダ５０からの出力順序Ｕｋ＋１，Ｐｋ＋１との両方を提供する。トレリス図８０のどこかで、デコーダ９６が正しい経路８２を取り出すことができる。
【００４８】
従って、エンコーダをトレリス図を用いて説明する場合には、その関連するデコーディングのアルゴリズムは、一般に、入力順序Ｕｋを再構成するトレリス図８０に基づく。デコーダ９６は、トレリス図８０のどの経路８２が所定のチャネルのビットストリーム９２に対して最も有望な経路であるかを決定する。
【００４９】
デコーダ９６がトレリス図８０上でどのように動作するかを理解するために、図８の図形を考えてみる。図５の４つの状態のトレリス図８０で、０〜５とラベル付けられた６つの段階ｋが示されている。ハード出力のデコーディングのアルゴリズムでは、デコーダ９６は各段階ｋにおいて、コード化されたビットが「１」ビットであるか又は「０」ビットであるかを判断する。対照的に、デコーダ９６がソフト入力／ソフト出力（ｓｏｆｔ−ｉｎｐｕｔ／ｓｏｆｔ−ｏｕｔｐｕｔ：以下、「ＳＩＳＯ」とよぶ）のアルゴリズムを使用する場合には、トレリス図８０の所定の経路８２の品質が評価される。このように、デコーダ９６は、「１」ビット又は「０」ビットであるかどうかではなく、確率データを提供する。このため、ソフト出力のアルゴリズムでは、経路８２はメトリックとしてよく知られた数字を用いて定義される。このメトリックは、チャネルのビットストリーム９２がデコーダ９６によって受信されると、経路がトレリス図８０の中で作られる可能性があることを示す。
【００５０】
図２のＲＳＣエンコーダ５０については、Ｕｋの２つの可能な入力値０又は１は、各ノード７２から伸びる２つの可能なブランチ７４に相当する。このため、図８では、段階１において、２つのブランチ７４が「１０」状態のノード７２から伸びる。同様に、各ブランチ７４は、尤度（ｌｉｋｅｌｉｈｏｏｄ）又はブランチメトリック１０６と関連付けられる。図８では、ブランチメトリック１０６は、ブランチ１０４とラベル付けられた数である。上側のブランチ７４ａは、．２のブランチメトリック１０６を有する。下側のブランチ７４ｂは、．３のブランチメトリック１０６を有する。
【００５１】
ブランチメトリック１０６は、「ソフトな（ｓｏｆｔ）」情報であり、一般に、チャネルのビットストリーム９２がデコーダ９６により受信される場合には、次のノード７２に到達する尤度を示す対数の確率である。デコーダ９６は、ブランチメトリック１０６を計算する。
【００５２】
ビタビのアルゴリズムでは、デコーダ９６の目的は、トレリス図８０から最良の経路８２を得ることである。ＭＡＰアルゴリズム等のソフトな出力アルゴリズムでは、デコーダ９６はその代わりにトレリスの各段階ｋにおいて、情報ビットＵｋが０又は１である尤度を決定する。このように、デコーダ９６は、一度に１つの段階ずつ繰り返しトレリス図８０を横切って、受信したビットストリームとトレリス図８０とに基づいて尤度の情報を計算する。
【００５３】
デコーダ９６は、本質的に、トレリス図８０の全ての可能な経路８２を考慮する。考慮された各経路８２に対して、デコーダ９６は、経路８２に対するブランチメトリック１０６を計算して、結果として経路メトリック１０８を発生する。そして、デコーダ９６は、最大の経路メトリック１０８を有する経路８２を選択する。この最大の経路メトリック１０８を有する経路８２は、最大尤度の経路である。選択された経路８２は、残存経路（ｓｕｒｖｉｖｏｒ ｐａｔｈ）としても知られている。そして、経路８２から情報ビットＵｋを決定する。
【００５４】
このように、デコーダ９６は、トレリス図８０を通って「移動（ｔｒａｖｅｌ）」し、経路に沿ってブランチメトリック１０６と経路メトリック１０８とを計算する。いくつかのアルゴリズムでは、トレリス図８０は１回だけ通過される。しかしながら、他のアルゴリズムでは、トレリス図８０は、前方向と逆方向との両方に通過される。それにもかかわらず、ビタビのアルゴリズムとＭＡＰのアルゴリズムとトレリス図８０上で動作する他のアルゴリズムとは、所望の結果に到着する前に、膨大な数の計算を実行する。
【００５５】
トレリス図８０の可能な経路８２の数は、例えば、２ｔｒｅｌｌｉｓ ｌｅｎｇｔｈである。そのため、エンコーダ５０が１００個の情報ビットをコード化する場合には、デコーダ９６は、２１００個の可能な経路（約１０３０経路）８２を計算することになる。この計算は、ブランチメトリック１０６の各々がメモリ内に記憶されない場合はさらに複雑になる。
【００５６】
図９では、図５のトレリス図８０の一部が、段階ｋと段階ｋ＋１と段階ｋ＋２とを含んでいる。スライディングウィンドウ（ｓｌｉｄｉｎｇ ｗｉｎｄｏｗ）１１０が段階ｋと段階ｋ＋１とを囲んでいる。デコーダ９６は、スライディングウィンドウ１１０を使用して、トレリス８０に沿ってブランチメトリック１０６を任意に計算することができる。
【００５７】
例えば、段階ｋにおいて、状態００に対応するノード７２ｋから、ブランチ７４ｃ及びブランチ７４ｄが（段階ｋ＋１の）ノード７２ｋ＋１に伸びる。同様に、状態０１に対応するノード７２ｋから、２つのブランチ７４ｅ及び７４ｆが伸びる。ノード７２ｋ（状態１０）からブランチ７４ｇ及び７４ｈが、ノード７２ｋ（状態１１）からブランチ７４ｉ及び７４ｊが、ノード７２ｋ＋１（段階ｋ＋１）に伸びる。ブランチ７４ｃと７４ｅと７４ｇと７４ｉとは、エンコーダ５０に対して「０」の入力値に相当し、一方、ブランチ７４ｄと７４ｆと７４ｈと７４ｊとは、「１」の入力値に相当する。
【００５８】
スライディングウィンドウ１１０が図９の位置にある間に、デコーダ９６は、ブランチ７４ｃ〜７４ｊの各々に対して、合計８つのブランチメトリック１０６を計算する。ｋ＝０の場合を除いて、１つ以上の経路８２は前の段階からノード７２ｋに伸びる。経路８２の１つが残存経路である。このため、残存経路の経路メトリック１０８を用いて、新しい経路メトリック１０８を計算することができる。そして、第１のブランチメトリック１０６を経路メトリック１０８に加算し、第２のブランチメトリック１０６を経路メトリック１０８に加える。この２つの結果を比較することができる。長い方の経路メトリック１０８を有する経路８２が、段階ｋに対する新しい残存経路である。この計算グループは、バタフライ演算としてよく知られている。
【００５９】
バタフライ演算が段階ｋに対して完了すると、スライディングウィンドウ１１０をアルゴリズムに従って前後に移動させて、次のバタフライ演算を実行する。
【００６０】
図９のスライディングウィンドウ１１０では、各ノード７２ｋに対して１つずつ、最大４つのバタフライ演算を実行することができる。各ブランチ７４のブランチメトリック１０６を、経路メトリック１０８に加算する（加算演算）。そして、結果として生じた経路メトリック１０８のそれぞれを他の経路メトリック１０８と比較して、どちらの結果が大きいかを判断する（比較演算）。結果として生じた経路メトリック１０８すなわち残存経路を選択する（選択動作）。このため、バタフライ演算は、加算と比較と選択（ａｄｄ−ｃｏｍｐａｒｅ−ｓｅｌｅｃｔ：以下、「ＡＣＳ」とよぶ）、すなわちＡＣＳ演算としてしばしば知られている。最後に、残存経路はメモリ等に記憶される。
【００６１】
図１０では、１つの実施形態に基づいて、システム２００を前述したようなバタフライ演算を実行するために使用することができる。このシステム２００は、１つ以上のバタフライユニット２０２と、ブランチメトリックユニット２０４と、経路メトリック用メモリ２０６とを含む。システム２００の回路は、ＡＣＳ又は対数ＭＡＰのバタフライ演算を実行することもできる。
【００６２】
１つの実施形態では、ブランチメトリックユニット２０４は、上記の図８で説明したブランチメトリック１０６に対する計算を実行する。ブランチメトリック１０６は、チャネルデータ９２とエンコーダ５０とが発生する４つの可能な出力値Ｕｋ＋１，Ｐｋ＋１を分析することによって計算される。ブランチメトリック１０６は、各ノード７２ｋに対して計算される。ブランチメトリックユニット２０４は、前の段階からの経路メトリック１０８がブランチメトリック１０６の計算では考慮されていないため、経路メトリック用メモリ２０６には接続されていないことに注意されたい。
【００６３】
図１０の実施形態では、各バタフライユニット２０２は、ブランチメトリック１０６をブランチメトリックユニット２０４から受け取る。各段階ｋには４つのノード７２があるため、４つのバタフライユニット２０２を設ける。従って、１つの実施形態によれば、各バタフライユニット２０２が互いに平行して計算を行うことができるため、状態００と状態０１と状態１０と状態１１とのそれぞれに対する新しい経路メトリック同時に計算することができる。
【００６４】
さらに、各バタフライユニット２０２は、経路メトリック１０８を経路メトリック用メモリ２０６から受け取る。この情報を用いて、それぞれのバタフライユニット２０２は、トレリス図８０の所定のノード７２ｋに対してＡＳＣ演算を実行することができる。
【００６５】
各バタフライユニット２０２の出力経路は、経路メトリック用メモリ２０６にも接続される。このように、新しいバタフライ演算の組が段階ｋ＋１で実行されるまで記憶するために、各バタフライユニット２０２は、結果として生じた経路メトリックを経路メトリック用メモリ２０６に送る。
【００６６】
図１１において、システム２００の第２の実施形態が、本願で説明するＭＡＰアルゴリズムを実行する。デコーダ９６は、システム２００を使用して、トレリス図８０上の前方と後方との両方向に向かってトレリス演算を実行することができる。ＭＡＰアルゴリズムは、トレリス図に対して前方と後方との両方向に向かってトレリス演算を実行する２経路式のアルゴリズムである。前方経路と後方経路との両方で、トレリスのノードメトリックが計算される。
【００６７】
前方経路の間に、ノードメトリックを経路メトリック用メモリ２０６の中に記憶することができる。そして、後方経路の間に、スライディングウィンドウのメトリックが、計算されて、経路メトリック用メモリ２０６内に記憶された前方経路メトリックと結合される。別の方法では、所望する場合には、前方経路の前に後方経路を置くことができる。
【００６８】
トレリスは各段階でＮ個の状態を有する。図１１のシステム２００は、前方と後方との両方向で、全てのＮ個の状態に対するメトリックを単一のビット信頼性メトリックに減少させる。これは、ＭＡＰアルゴリズムの最終的なソフト出力である。
【００６９】
図１１に示すようなバタフライユニット２０２の構成を用いて、前方経路メトリックと後方経路メトリックとの両方をこのように計算することができる。上側の３つのバタフライユニット２０２は「１」のブランチ１０４に対して使用され、一方、下側の３つのバタフライユニット２０２は「０」のブランチ１０４に対して使用される。
【００７０】
図１１では、１つの実施形態に基づいて、ブランチメトリックユニット（ｂｒａｎｃｈ ｍｅｔｒｉｃｓ ｕｎｉｔ：以下、「ＢＭＵ」とよぶ）２０４が、段階ｋに対する現在のブランチメトリック７４を計算する。そして、バタフライユニット２０２は、前方の（又は後方の）経路メトリック１０８を経路メトリック用メモリ２０６からまたブランチメトリック７４をブランチメトリックユニット２０４から読み出す。そして、各バタフライユニット２０２は、一度に２つずつ結果を結合し差分を減算して、事後確率値（ａ ｐｏｓｔｅｒｉｏｒｉ ｐｒｏｂａｂｉｌｉｔｙ）を発生する。
【００７１】
図１２において、図１０のシステム２００が、１つの実施形態に基づいて、システム１００（図１）の中で実現される。予想されるように、経路メトリック用メモリ２０６は、より大きな利用可能なメモリ３０の一部である。経路メトリック用メモリ２０６は、メモリ記憶バス２２とメモリロードバス２４とによって、他の回路にアクセスすることができる。
【００７２】
図１２では、ブランチメトリックユニット２０４は、算術演算装置２０の一部である。このブランチメトリックユニット２０４は、その計算を実行する場合には、経路メトリック用メモリ２０６にアクセスする必要はない。その代わり、ブランチメトリックユニット２０４は、バタフライユニット２０２に情報を提供する。
【００７３】
このため、１つの実施形態では、算術演算装置２０は、データアドレス発生器２６がアクセス可能なレジスタ２１０を含む。演算が完了すると、ＢＭＵ２０４は、レジスタ２１０の中に結果を記憶する。そして、バタフライユニット２０２は、データアドレス発生器２６を用いてレジスタ２１０にアクセスすることによって、メモリ３０にアクセスされたように、ＢＭＵ２０４の演算結果を得る。
【００７４】
１つの実施形態では、バタフライコプロセッサ２８が４つのバタフライユニット２０２を含む。バタフライ計算を行うために、バタフライユニット２０２は、データアドレス発生器２６とメモリロードバス２４とを用いて経路メトリック用メモリ２０６とレジスタ２１０とにアクセスする。そして、バタフライユニット２０２は、ＡＳＣ演算を実行して、スライディングウィンドウ１１０内の現在の段階におけるノード７２に対する経路メトリック１０８を計算する。バタフライ演算を完了すると、バタフライユニット２０２は、メモリ記憶バス２２上に結果を置くことによって、経路メトリック用メモリ２０６内に結果を記憶する。
【００７５】
図１２の実施形態では、ＤＳＰ１０がバタフライコプロセッサ２８の代わりにメモリの管理を行う。しかしながら、加えて、その算術演算装置２０の中にブランチメトリックユニット２０４の動作を含むことによって、ＤＳＰはバタフライ演算の一部も実行する。これにより、バタフライコプロセッサ２８は、バタフライユニット２０２による各種のノード演算を平行して行うことに全てのアテンション（ａｔｔｅｎｔｉｏｎ）を専念させることができる。
【００７６】
他の実施形態は、図１０のシステム２００を実行することができる。例えば、図１２では、ブランチメトリックユニット２０４がブランチメトリック１０６を計算すると、ブランチメトリックユニット２０４は結果を算術演算装置２０の中に配置されたレジスタ２１０に記憶する。そして、データアドレス発生器２６は、バタフライコプロセッサ２８の要求によりレジスタ２１０にアクセスする。
【００７７】
別の方法では、バタフライコプロセッサ２８自身の中にブランチメトリック２０４を配置することができる。この別の方法の構成では、ブランチメトリックユニット２０４をバタフライユニット２０２に直接に接続することができるため、レジスタ２１０に対する必要性を未然に防ぐ。バタフライコプロセッサ２８は、ブランチメトリックユニット２０４の動作とＡＳＣ動作との両方を実行する。
【００７８】
さらに、いくつかの実施形態では、システム１００がプログラム可能でありうる。例えば、レジスタはブランチメトリックユニット２０４とＤＳＰ１０との間の接続性を定義する。単にメモリの管理を行う場合又はバタフライ演算の一部を行う場合であっても、ＤＳＰ１０は、段階ごとのベースでデコーディングするトレリスの中で必要とされる。１つの実施形態では、ＤＳＰ１０はバタフライコプロセッサ２８用のメモリインターフェースを提供する。いくつかの実施形態では、ＤＳＰ１０は、バタフライコプロセッサ２８の代わりに、アルゴリズムのスケジューリングを付加的に実行する。
【００７９】
このように、バタフライコプロセッサ２８は、複数のバタフライユニットを用いて、並列のバタフライ演算を実行する。１つの実施形態では、システム１００は、チャネルのビットストリームのデコーディングに含まれる極めて複雑な演算を実行するスループットを増加する。
【００８０】
１つの実施形態では、システム１００は、メモリ３０の中に記憶されて示されるソフトウェアプログラム５００を含む。このソフトウェアプログラム５００を用いて、システム１００を多数のデコーディング方式に対して柔軟に実行することができる。さらに、新しいデコーディング技術が開発されるたびに、新しいソフトウェアプログラムをシステム１００にロードすることができる。
【００８１】
図１３において、ソフトウェアプログラム５００は、（ブロック５０２で）デコーディング要求を受信することによって、１つの実施形態に基づいて、デコーディング動作を管理する。図１２の実施形態では、経路メトリック１０８は、経路メトリック用メモリ２０６の中に記憶される。このため、ソフトウェアプログラム５００は、データアドレス発生器２６を用いてメモリ３０をアドレスして、（ブロック５０４で）経路メトリックメモリ２０６から経路メトリック１０８を読み出す。そして、経路メトリック１０８はバタフライコプロセッサ２８に送られる。
【００８２】
図１０に戻る。経路メトリック１０８を受信することに加えて、バタフライユニット２０２は、ブランチメトリック１０６も入力値として受け取る。このため、図１３では、サービスプロバイダ５００は、（ブロック５０６で）ブランチメトリックユニット２０４に対してそのブランチメトリックの計算を実行させる。バタフライコプロセッサ２８に送るために、結果が、レジスタ２１０の中に記憶されるか、メモリ３０内に記憶されるか、又はメモリ記憶バス２２上に直接に置かれる。
【００８３】
このように、ソフトウェアプログラム５００は、（ブロック５０８で）システム１００に対して経路メトリック１０８とブランチメトリック１０６とをバタフライコプロセッサ２８に送らせる。そして、バタフライコプロセッサは、（ブロック５１０で）並列のバタフライ演算を実行する。従って、１つの段階に対するトレリスの計算がシステム１００によって実行される。ソフトウェア５００の動作が、１つの実施形態に基づいて完了される。
【００８４】
多数の方法で、バタフライユニット２０２を実行することができる。図１０及び図１１では、それぞれのバタフライユニット２０２は、２つの入力値、すなわち、１つは経路メトリック用メモリ２０６から、他はブランチメトリックユニット２０４から受け取る。そして、バタフライユニット２０２は、経路メトリック用メモリ２０６に送られる１つの出力値を発生する。
【００８５】
図１４ａでは、１つの実施形態に基づいて、バタフライユニット２０２は、アルゴリズミック加算指数演算（ａｌｇｏｒｉｔｈｍｉｃ ｓｕｍ ｅｘｐｏｎｅｎｔｉａｌ ｏｐｅｒａｔｉｏｎ）を用いて実行される。経路メトリック用メモリ２０６とブランチメトリックユニット２０４からの値を受信することに加えて、バタフライユニット２０２は付加的にパラメータｃを受け取る。このパラメータｃは、バタフライユニット２０２に配線で接続されたもの、又は、希望する場合には、プログラム可能とすることができる。以下の数式が、バタフライユニット２０２の中で個別の論理として実行される。
ｚ ＝ ｃ ｌｏｇ （ｅｘ／ｃ ＋ ｅｙ／ｃ）
＝ ｍａｘ（ｘ，ｙ） ＋ ｃ ｌｏｇ （１ ＋ ｅｄｉｆｆ／ｃ）
【００８６】
図１４ｂでは、バタフライユニット２０２は最大演算（ｍａｘ ｏｐｅｒａｔｉｏｎ）を実行する。バタフライユニット２０２は、入力値ｘ及びｙの最大値と差分との両方を計算する最大ユニット（ｍａｘ ｕｎｉｔ）２２０を含む。最大の出力値は加算器２２４に送られる。差分値はルックアップテーブル２２２に送られ、ルックアップテーブルの結果が加算器２２４に送られる。ＡＳＣ演算を実行する他のアルゴリズムは、よく知られており、バタフライユニット２０２の中で実行することができる。
【００８７】
特に複雑なコード化方式を有するシステム１００を使用することにより、相当の利点があることが認識される。例えば、ターボコードは、ＦＥＣチャネルコーディングにおいて最近開発された方式である。ターボコードは、広帯域規格と携帯電話で使用されている第三世代（３Ｇ）の符号分割多重アクセス（ＣＤＭＡ）規格との両方で使用することが検討されている。
【００８８】
図１５において、ターボエンコーダ３００は、３ＧのＣＤＭＡセルラー技術で使用される１つのよく知られた実施形態である。エンコーダ３００は、長さが３２０から５，１２０ビットの範囲のデータブロックで動作する。ブロックは、２構成畳込みコード、又はＲＳＣエンコーダ３０２及び３０４によって並列にコード化される。ＲＳＣエンコーダ３０４によりコード化する前に、入力のデータブロック３１０は、インターリーバ３０６によりビットインターリーブされる。
【００８９】
データブロック３１０をＲＳＣエンコーダ３０４に送る前にインターリーブすることによって、ターボエンコーダ３００は１つの時間でコード化するよりもはるかに強力になる。ＲＳＣエンコーダ３０２及び３０４を通過した後に、コード化されたブロック３１２及び３１４は、別個にチャネル９０（図５）を通ってそれぞれ送られるか、必要に応じてそれぞれ結合される。
【００９０】
従来の畳込みコード化動作と比較すると、ターボエンコーダで使用される構成コードははるかに複雑ではない。第三世代のシステムは、３２ｋｂｐｓ以下の速度でチャネルと音声とデータリンクとを制御するために、例えば、ｋ９畳込みコードを使用する。このｋ９コードは２５６の状態を有する。対照的に、ターボ構成コードは、例えば、僅か８つの状態しか有していない。
【００９１】
図１６において、ターボデコーダ４００は、２つのソフト入力／ソフト出力（ＳＩＳＯ）デコーダ４０６及び４０８を含む。デコーダ４０６及び４０８のそれぞれは、チャネルのビットストリーム４０２及び４０４をそれぞれ受け取る。チャネルのビットストリーム４０２は、図１５のコード化されたブロック３１２に相当する。チャネルのビットストリーム４０４は、図１５のコード化されたブロック３１４に相当する。
【００９２】
ターボエンコーダ３００と同様に、図１６のターボデコーダはよく知られている。ＳＩＳＯデコーダ４０６は、チャネルのビットストリーム４０２を受け取る。デコーディングの後に、出力値はインターリーバ４１０を通過して、第２のＳＩＳＯデコーダ４０８によって受信される。この第２のＳＩＳＯデコーダ４０８は、第２のチャネルビットストリーム４０４をさらに受け取る。デコーディング動作の後に、ＳＩＳＯデコーダ４０８は、出力値をデ・インターリーバ（ｄｅ−ｉｎｔｅｒｌｅａｖｅｒ）４１２に送り、そして、デ・インターリーブされたデータ（ｄｅ−ｉｎｔｅｒｌｅａｖｅｄ ｄａｔａ）がＳＩＳＯデコーダ４０６に送られる。
【００９３】
この処理は、最終出力がハード決定ブロック４１４に送られるまで数回繰り返される。このハード決定ブロック４１４は、ハード出力値としてデータを定量化する。ＳＩＳＯデコーダ４０６及び４０８がソフト入力及びソフト出力であるために、ターボデコーダ４００が部分的にはうまく働く。このため、ソフト情報を所望の回数だけそれらの間を通すことができる。本質的に、アービトレーション方式は、最終的な出力値に関して採用される。
【００９４】
１つの実施形態では、ＳＩＳＯデコーダ４０６は、ＭＡＰアルゴリズム（最大事後確率）を用いて実行される。前述したように、ＭＡＰはソフト入力／ソフト出力のアルゴリズムである。ＭＡＰ出力は、「ハードな（ｈａｒｄ）」ビット決定出力を発生するのではなく、各データビット値の尤度を示す事後確率（ａ ｐｏｓｔｅｒｉｏｒｉ ｐｒｏｂａｂｉｌｉｔｙ：ＡＰＰ）である。相対的に、ビタビのアルゴリズムは、ソフト入力／ハード出力のデコーダである。
【００９５】
ＭＡＰのアルゴリズムの複雑性は、状態当たりの複雑性ではビタビのアルゴリズムの約４倍である。さらに、ＭＡＰのアルゴリズムは、ビタビのアルゴリズムよりもはるかにメモリ集約的である。しかしながら、ターボコードを実行する場合には、ｋ９畳込みコードでは２５６個の状態を考慮することに比べると、わずか８つの状態を考えるだけである。
【００９６】
図１６では、ターボデコーダ４００は、両方のＳＩＳＯデコーダ４０６及び４０８内に組み込まれたＭＡＰアルゴリズムを繰り返す。各デコーダ４０６及び４０８はシステム１００（図１２）を使用して、ＭＡＰアルゴリズムを実行する。ターボデコーダ４００がそれぞれＭＡＰアルゴリズムを使用する２つのデコーダを含むため、システム１００の並列演算により、従来技術の装置よりも実質的に早い性能が結果として生ずる。
【００９７】
このため、いくつかの実施形態によれば、システム１００をデコーダの中で使用して、トレリス図に関連する演算を実行することができる。ＭＡＰアルゴリズムと、ビタビのアルゴリズムと、他のアルゴリズムとは、そのような演算を実行する。さらに、システム１００は、ソフト出力のアルゴリズム又はハード出力のアルゴリズムのいずれかを実行することができる。ＤＳＰ及びバタフライコプロセッサは、これらの演算を行う上で一緒に動作する。
【００９８】
ＤＳＰ及びバタフライコプロセッサ間の仕事の分担は、様々な方法により行うことができる。１つの実施形態では、ＤＳＰは、バタフライコプロセッサに代わって、メモリの管理とアルゴリズムのスケジューリングとを行う。バタフライコプロセッサは、デコーディングの間のスループットを増加するために、並列バタフライ演算を実行する。さらに、システム１００は、多数の可能なデコーディング環境の中で使用するためのフレキシビリティを維持する。
【００９９】
本発明を限られた数の実施形態に関して説明してきたが、当業者はこれらの実施形態からの多くの修正例及び変更例を理解されよう。全てのそのような修正例や変更例を本発明の真の精神及び範囲の中に入るよう、特許請求の範囲に包含することを意図している。
【図面の簡単な説明】
【図１】
本発明の１つの実施形態によるシステムのブロック図である。
【図２】
本発明の１つの実施形態による、帰納的なシステム化された畳込みエンコーダの図である。
【図３】
本発明の１つの実施形態による、図２のエンコーダ用の状態遷移表である。
【図４】
本発明の１つの実施形態による、図２のエンコーダに対するトレリスである。
【図５】
本発明の１つの実施形態による、図２のエンコーダに対するトレリス図である。
【図６】
本発明の１つの実施形態に基づいて、図２のエンコーダを使用する可能な経路を図解する、図５のトレリス図である。
【図７】
本発明の１つの実施形態に基づいて、情報のデータストリームが取ることができる経路のブロック図である。
【図８】
本発明の１つの実施形態に基づいて、トレリス図のブランチ及び経路のメトリックの両方を示す図である。
【図９】
本発明の１つの実施形態に基づいて、バタフライ演算を図解するために使用されるトレリス図である。
【図１０】
本発明の１つの実施形態によるバタフライ演算子のブロック図である。
【図１１】
本発明の第２の実施形態によるバタフライ演算子の第２のブロック図である。
【図１２】
本発明の１つの実施形態に基づいて、図１のシステムの中で使用される図１０のバタフライ演算子のブロック図である。
【図１３】
本発明の１つの実施形態に基づいて、図１２のシステムによって使用されるソフトウェアプログラムのフローチャートである。
【図１４】
ａ及びｂは、本発明の１つの実施形態に基づいて、バタフライユニットの可能な動作を示す図である。
【図１５】
本発明の１つの実施形態によるターボエンコーダのブロック図である。
【図１６】
本発明の１つの実施形態によるターボデコーダのブロック図である。
【図１】
2004511162.tif 000003
【図２】
2004511162.tif 000004
【図３】
2004511162.tif 000005
【図４】
2004511162.tif 000006
【図５】
2004511162.tif 000007
【図６】
2004511162.tif 000008
【図７】
2004511162.tif 000009
【図８】
2004511162.tif 000010
【図９】
2004511162.tif 000011
【図１０】
2004511162.tif 000012
【図１１】
2004511162.tif 000013
【図１２】
2004511162.tif 000014
【図１３】
2004511162.tif 000015
【図１４】
2004511162.tif 000016
【図１５】
2004511162.tif 000017
【図１６】
2004511162.tif 000018
【国際公開パンフレット】
2004511162.tif 000019
2004511162.tif 000020
2004511162.tif 000021
2004511162.tif 000022
2004511162.tif 000023
2004511162.tif 000024
2004511162.tif 000025
2004511162.tif 000026
2004511162.tif 000027
2004511162.tif 000028
2004511162.tif 000029
2004511162.tif 000030
2004511162.tif 000031
2004511162.tif 000032
2004511162.tif 000033
2004511162.tif 000034
2004511162.tif 000035
2004511162.tif 000036
2004511162.tif 000037
2004511162.tif 000038
2004511162.tif 000039
2004511162.tif 000040
2004511162.tif 000041
2004511162.tif 000042
2004511162.tif 000043
2004511162.tif 000044
2004511162.tif 000045
2004511162.tif 000046
2004511162.tif 000047
2004511162.tif 000048
2004511162.tif 000049
2004511162.tif 000050
2004511162.tif 000051
2004511162.tif 000052
2004511162.tif 000053
2004511162.tif 000054
2004511162.tif 000055
2004511162.tif 000056
2004511162.tif 000057
2004511162.tif 000058
2004511162.tif 000059
2004511162.tif 000060
2004511162.tif 000061
【国際公開パンフレット（コレクトバージョン）】
2004511162.tif 000062
2004511162.tif 000063
【国際調査報告】
2004511162.tif 000064
2004511162.tif 000065