(57)【要約】ワイヤレスシステムにおいて、デジタル信号プロセッサ（１１０）は、ターボチャンネル復号およびViterbiチャンネル復号を実行する。デジタル信号プロセッサ（１１０）の演算ブロック（１１２、１１４）は、トレリス演算に関連する命令を実行するためのアクセラレータを伴って提供される。ACS命令は、アルファメトリックおよびベータメトリックのトレリス演算を実行する。複数のバタフライ演算は、単一の命令に応答して実行される。TMAX命令は、トレリスの対数尤度率を計算するために使用される。
2004538704.tif 000002
【特許請求の範囲】
【請求項１】
デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法であって、
選択されるトレリス状態において、ある時間ｔ０でのトレリス状態メトリックの位置、および時間ｔ０から時間ｔ１への遷移メトリックの位置を指定するトレリス命令に応答して、時間ｔ０での第１状態メトリックに遷移メトリックを加算し、第１の値を提供するステップ、時間ｔ０での第２の状態メトリックから遷移メトリックを減算し、第２の値を提供するステップ、；および
それぞれの選択される状態メトリックにおいて、対応する第１の値と第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのトレリス状態メトリックを提供するステップ、を含む前記方法。
【請求項２】
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項１に記載の方法。
【請求項３】
訂正ファクタを加算するステップが、訂正ファクタを含有するルックアップテーブルにアクセスすることを含む、請求項２に記載の方法。
【請求項４】
前記トレリス命令が、αトレリス状態メトリックを計算するための前方トレリス関数を実行する、請求項１に記載の方法。
【請求項５】
前記トレリス命令が、βトレリス状態メトリックを計算するための逆方向トレリス関数を実行する、請求項１に記載の方法。
【請求項６】
前記トレリス命令が、単一の命令、複数のデータアプローチを使用して、αトレリス状態メトリックを計算するための前方トレリス関数、およびβトレリス状態メトリックを計算するための逆方向トレリス関数を同時に実行する、請求項１に記載の方法。
【請求項７】
デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法であって、
ある時間ｔ０でのαメトリックおよびトレリス命令によって指定される時間ｔ０から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのαメトリックを計算するステップ、；および
ある時間ｔ２でのβメトリック、およびトレリス命令によって指定される時間ｔ２から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのβメトリックを計算するステップ、を含む前記方法。
【請求項８】
選択されるトレリス状態におけるαメトリックを計算するステップが、
それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ０での第１のαメトリックに加算して、第１の値を提供するステップ、遷移メトリックを時間ｔ０での第２のαメトリックから減算して、第２の値を提供するステップ、；および
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのαメトリックを提供するステップ、を含む請求項７に記載の方法。
【請求項９】
選択されるトレリス状態におけるαメトリックを計算するステップが、それぞれの選択されるトレリス状態に対して、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項８に記載の方法。
【請求項１０】
選択されるトレリス状態におけるβメトリックを計算するステップが、
それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ２での第１のβメトリックに加算して、第１の値を提供するステップ、遷移メトリックを時間ｔ２での第２のβメトリックから減算して、第２の値を提供するステップ、；および
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのβメトリックを与えるステップ、を含む請求項７に記載の方法。
【請求項１１】
それぞれの選択されるトレリス状態におけるβメトリックを計算するステップが、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
それぞれの選択されるトレリス状態におけるαメトリックを計算するステップが、単一のトレリス命令に応答して、複数のトレリス状態におけるαメトリックを計算するステップを含む、請求項７に記載の方法。
【請求項１３】
それぞれの選択されるトレリス状態におけるβメトリックを計算するステップが、単一のトレリス命令に応答して、複数のトレリス状態におけるβメトリックを計算するステップを含む、請求項７に記載の方法。
【請求項１４】
αメトリックを計算するステップとβメトリックを計算するステップとが、同時に行われる、請求項７に記載の方法。
【請求項１５】
デジタル信号プロセッサにおいて、log MAP関数を計算する方法であって、
第１，第２、第３、および第４のパラメータの位置を指定するlog MAP命令に応答して、第１パラメータと第２パラメータの和もしくは差を計算し、第１の値を提供するステップ、第３パラメータと第４パラメータの和もしくは差を計算して、第２の値を提供するステップ、；および
第１の値と第２の値のうち最大値を選択するステップ、；ならびに
第１の値および第２の値の関数である訂正ファクタを前記最大値に加算して、log MAP結果を提供するステップ、を含む前記方法。
【請求項１６】
訂正ファクタを加算するステップが、訂正ファクタを含有するルックアップテーブルにアクセスすることを含む、請求項１５に記載の方法。
【請求項１７】
単一のlog MAP命令に応答して、２以上のlog MAP結果が計算される、請求項１５に記載の方法。
【請求項１８】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、ある時間ｔ０でのトレリス状態メトリックの位置、および時間ｔ０から時間ｔ１への遷移メトリックの位置を指定するトレリス命令を実行するためのアクセラレータであって、遷移メトリックを時間ｔ０での第１状態メトリックに加算して、第１の値を提供する加算器、および時間ｔ０での第２状態メトリックから遷移メトリックを減算して、第２の値を提供する加算器を含む前記アクセラレータと、それぞれのトレリス状態において対応する第１の値および第２の値のうち、最大値を決定するための比較器と、選択されるトレリス状態において対応する第１の値および第２の値のうち、最大値を選択するためのデータセレクタとを含む前記演算ブロック、とを含むプロセッサ。
【請求項１９】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
第１演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、トレリス命令によって指定される、ある時間ｔ０でのαメトリックおよび時間ｔ０から時間ｔ１への遷移メトリックに応答して、トレリス命令を実行するためのアクセラレータであって、時間ｔ０でのαメトリックおよび遷移メトリックに基づいて、時間ｔ１での選択されるトレリス状態におけるαメトリックを計算するための手段を含む前記アクセラレータ、を含む前記第１演算ブロックと、；
第２演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、命令によって指定される、ある時間ｔ２でのβメトリックおよび時間ｔ２から時間ｔ１への遷移メトリックに応答して、トレリス命令を実行するためのアクセラレータであって、時間ｔ２でのβメトリックおよび時間ｔ２から時間ｔ１への遷移メトリックに基づいて、時間ｔ１での選択されるトレリス状態におけるβメトリックを計算するための手段を含む前記アクセラレータ、を含む前記第２演算ブロック、とを含むプロセッサ。
【請求項２０】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、第１、第２、第３、および第４のパラメータの位置を指定するlog MAP命令を実行するためのアクセラレータであって、第１パラメータと第２パラメータの和もしくは差を計算して、第１の値を提供する第１加算器、ならびに第３パラメータと第４パラメータの和もしくは差を計算して、第２の値を提供する第２加算機を含む前記アクセラレータと、第１の値および第２の値のうち、最大値を選択するためのデータセレクタと、第１の値および第２の値の関数である訂正ファクタを生成するためのルックアップテーブルと、訂正ファクタを前記最大値に加算して、log MAPの結果を提供するための第３加算器、を含む前記演算ブロック、とを含むプロセッサ。
【請求項２１】
デジタル信号プロセッサ演算ブロックに使用されるアクセラレータであって、
アクセラレータへの入力を受信する第１キャリーセーブ加算器と；
前記第１キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第１全加算器と；
前記第１全加算器の出力に応答して、訂正ファクタを生成するルックアップテーブルと；
前記第１全加算器の出力サインに応答して、１または２以上のアクセラレータへの入力を選択するためのマルチプレクサと；
１または２以上のマルチプレクサの出力とルックアップテーブルの出力を加算するための第２キャリーセーブ加算器と；
前記第２キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第２全加算器、
とを含む、前記アクセラレータ。
【請求項２２】
第１キャリーセーブ加算器が４個の入力を有し、マルチプレクサが４個の出力のうち２個を選択し、第２キャリーセーブ加算器が３個の入力を有する、請求項２１に記載のアクセラレータ。
【請求項２３】
前記第２キャリーセーブ加算器のサム出力とキャリー出力とを第１キャリーセーブ加算器の出力に供給するためのデータセレクタをさらに含む、請求項２２に記載のアクセラレータ。
【請求項２４】
前記第１キャリーセーブ加算器および前記第１全加算器が、第１パイプラインステージ、前記ルックアップテーブル、および前記マルチプレクサを含み、前記第２キャリーセーブ加算器が、第２パイプラインステージを含み、前記第２全加算器が第３パイプラインステージを含む、請求項２１に記載のアクセラレータ。
【発明の詳細な説明】
【０００１】
発明の属する分野
本発明は、ワイヤレスモバイルおよび基地局において応用されるデジタル信号プロセッサに関し、さらに具体的には、ワイヤレス基地局において、ターボチャンネル復号およびViterbiチャンネル復号を行うためのデジタル信号プロセッサの使用に関する。
【０００２】
発明の背景
第２世代および第３世代のワイヤレスシステムは、伝送信頼度を高めるために、チャンネル符号およびチャンネル復号アルゴリズム、ならびにスペクトル拡散技術を必要とする。第三世代のワイヤレスシステムにおいて、畳み込み符号スキームが音声伝送のために指定され、および並列連接畳み込み符号（PCCC）がデータ伝送のために指定される。畳み込み符号化されたデータは、Viterbi復号アルゴリズムを使用して復号化され、PCCC符号化されたデータは、ターボ復号アルゴリズムを使用して復号化される。ターボ復号およびViterbi復号スキームは、トレリスに基づくアルゴリズムである。
【０００３】
Viterbi復号器アルゴリズムおよびターボ復号器アルゴリズムは、極度にコンピュータに負担をかける。ワイヤレス基地局における前方誤り訂正（forward error correction）ブロック、つまりチャンネル復号ブロックは、ソフトウェア無線でのシンボルレート処理の８０％に達し得る。割り当てられた制限時間内でこれらのアルゴリズムを実行するために提案される方法は、ASICの使用およびデジタル信号プロセッサにおいて最も基本的なコンポーネントを有する、ハードウェアブロックの使用を含む。
【０００４】
デジタル信号プロセッサは、ソフトウェアのプログラムが可能な能力のために、ASICよりも望ましい解決法である。しかしながら、現在利用可能なデジタル信号プロセッサでは、ソフトウェア無線で必要とされる完全なチップレート処理およびシンボルレート処理を扱うことができない。従ってシステム設計者は、シンボルレート処理を扱うために、デジタル信号プロセッサおよびASICを使用する解決法、もしくはASICのみを使用する解決法について研究を行っている。最低でも、ASICは前方誤り訂正を実行するようになるだろう。
【０００５】
デュアル演算ユニットおよびワイドメモリバスを有し、並列して複数のタスクを扱うための能力を有するデジタル信号プロセッサが、１９９９年４月２０日にGarde（ガード）に対して発行された米国特許第5,896,543号に開示されている。開示されたデジタル信号プロセッサは、非常に高い性能を実現するが、現在構成されているものでは、ワイヤレス基地局の前方誤り訂正を割り当てられた制限時間内に効果的に実行することができない。
【０００６】
従って、ワイヤレスシステムにおいて使用される、ターボチャンネル復号アルゴリズムおよびViterbiチャンネル復号アルゴリズムの改良された実行方法が必要とされている。
【０００７】
発明の概要
本発明の第１の側面に従って、デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法が提供される。トレリス命令によって指定される、ある時間ｔ０でのトレリス状態メトリックおよび時間ｔ０から時間ｔ１への遷移メトリック（transition metric）に応答して、選択されるトレリス状態におけるトレリス関数のメトリックが計算される。それぞれの選択されるトレリス状態における計算は、遷移メトリックを時間ｔ０における第１状態メトリックに加算して、第１の値を提供すること、遷移メトリックを時間ｔ０における第２状態メトリックから減算して、第２の値を提供すること、対応する第１の値および第２の値を比較すること、および対応する第１の値および第２の値のうち最大値を選択して、時間ｔ１におけるトレリス状態メトリックを提供すること、を含む。
【０００８】
前記方法は、それぞれの選択されるトレリス状態において、対応する第１の値および第２の値の関数である訂正ファクタ（correction factor）を前記最大値に加算するというステップをさらに含んでもよい。訂正ファクタを加算するステップは、訂正ファクタを含有するルックアップテーブルにアクセスすることを含んでもよい。
【０００９】
１つの態様において、トレリス命令は、前方トレリス関数（forward trellis function）を実行して、αトレリス状態メトリックを計算する。別の態様において、トレリス命令は、逆方向トレリス関数（reverse trellis function）を実行して、βトレリス状態メトリックを計算する。さらに別の態様において、トレリス命令は、単一の命令、複数のデータアプローチを使用して、αトレリス状態メトリックを計算するための前方トレリス関数、およびβトレリス状態メトリックを計算するための逆方向トレリス関数を同時に実行する。
【００１０】
本発明の別の側面にしたがって、デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法が提供される。ある時間ｔ０でのαメトリックおよびトレリス命令によって指定される時間ｔ０から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのαメトリックが計算される。トレリス命令によって指定される、ある時間ｔ２でのβメトリックおよび時間ｔ２から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのβメトリックが計算される。
【００１１】
選択されるトレリス状態におけるαメトリックを計算するステップは、それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ０での第１のαメトリックに加算して、第１の値を提供すること、遷移メトリックを時間ｔ０での第２のαメトリックから減算して、第２の値を提供すること、それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較すること、それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのαメトリックを提供すること、を含んでもよい。
【００１２】
選択されるトレリス状態におけるβメトリックを計算するためのステップは、それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ２での第１のβメトリックに加算して第１の値を提供すること、遷移メトリックを時間ｔ２での第２のβメトリックから減算して、第２の値を提供すること、それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較すること、それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのβメトリックを提供すること、を含んでもよい。
【００１３】
それぞれの選択されるトレリス状態において、αメトリックを計算するステップおよびβメトリックを計算するステップは、それぞれ対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含んでもよい。αメトリックを計算するステップおよびβメトリックを計算するステップは、同時に行われてもよい。
【００１４】
本発明のさらなる側面にしたがって、デジタル信号プロセッサにおいて、log MAP命令を計算するための方法が提供される。log MAP命令は、第１、第２、第３および第４のパラメータ位置を指定する。第１パラメータと第２パラメータの和もしくは差を計算して、第１の値を提供し、第３パラメータと第４パラメータの和もしくは差を計算して、第２の値を提供する。第１の値と第２の値のうち最大値が選択される。そして、第１の値および第２の値の関数である訂正ファクタを前記最大値に加算して、log MAP結果を提供する。訂正ファクタを加算するステップは、訂正ファクタを含有するルックアップテーブルにアクセスすることを含んでもよい。
【００１５】
デジタル信号プロセッサは、デジタル信号演算のための命令およびオペランドを記憶するメモリと、選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、前記のオペレーションを独立して、もしくはいずれかの組み合わせで実行するためのアクセラレータ、を含む前記演算ブロックを含んでもよい。ある好適な態様において、デジタル信号プロセッサは、複数のオペレーションを並列して実行するための２以上の演算ブロックを含む。
【００１６】
本発明のさらなる側面にしたがって、デジタル信号プロセッサ演算に使用されるアクセラレータが提供される。アクセラレータは、アクセラレータへの入力を受信する第１キャリーセーブ加算器（carry save adder）と、第１キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第１全加算器（full adder）と、第１全加算器の出力に応答して、訂正ファクタを生成するルックアップテーブルと、第１全加算器の出力サインに応答して、１または２以上のアクセラレータへの入力を選択するためのマルチプレクサと、１または２以上のマルチプレクサの出力とルックアップテーブルの出力を加算するための第２キャリーセーブ加算器と、第２キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第２全加算器、を含む。
【００１７】
前記第１キャリーセーブ加算器および前記第１全加算器は、第１パイプラインステージ、前記ルックアップテーブルおよび前記マルチプレクサを含んでもよく、前記第２キャリーセーブ加算器は、第２パイプラインステージを含んでもよく、前記第２全加算器は、第３パイプラインステージを含んでもよい。好適なある態様において、アクセラレータは、第２キャリーセーブ加算器のサム出力およびキャリー出力を第１キャリーセーブ加算器に供給するためのデータセレクタをさらに含んでもよい。
【００１８】
発明の詳細な記述
ワイヤレス基地局信号チェーンの例のブロック線図を図１に示す。信号チェーンは、シンボルレート処理１０およびチップレート処理１２を含む。シンボルレート処理１０は、デジタル信号プロセッサに組み入れられることが望ましい。伝送側において、シンボルレート処理１０は、CRCアタッチメントブロック２０、チャンネル符号ブロック２２、レートマッチングブロック２４およびインターリービングブロック２６を含む。受信側において、シンボルレート処理１０は、デインターリーブブロック３０、レート決定ブロック３２、チャンネル復号ブロック３４，CRCアタッチメントブロック３６を含む。上述した通り、前方誤り訂正（FEC）、つまりチャンネル復号は、シンボルレート処理の８０％に達し得る。
【００１９】
本発明の側面は、デジタル信号プロセッサにおけるチャンネル復号ブロック３４の実行に関する。チャンネル符号ブロック２２は、音声またはローデータレート伝送のための畳み込み符号を利用してもよく、ハイデータレート伝送のためのPCCCスキームを利用してもよい。チャンネル復号ブロック３４は、音声用のViterbi復号アルゴリズムおよびデータ用のターボ復号を利用してもよい。
【００２０】
ターボ複合器の例の単純化されたブロック線図を図２に示す。ターボ複合器は、MAP（最大事後確率）復号器４０および４２、インターリーバ４４およびデインターリーバ４６を含む。ターボ符号は、例えばM. Valenti (Dept. of Elect. Eng., Virginia Polytechnic Inst.) の“An Introduction to Turbo Codes”、W. Ryan (New Mexico State University)の“A Turbo Code Tutorial”に説明されている。シングルMAP復号器は、Viterbi復号器を実行するために使用されてもよい。Viterbiアルゴリズムは、H. Louの“Implementing the Viterbi Algorithm” (IEEE Signal Processing Magazine、１９９５年９月、４２−５２ページ)に説明されている。
【００２１】
ターボチャンネル復号およびViterbiチャンネル復号は、受信されるデータのブロック上で行われる、トレリスに基づくアルゴリズムである。ワイヤレスシステムにおいて典型として使用される８状態トレリスの例を図３に示す。トレリスは、それぞれの複数の時点ｔ＝０、ｔ＝１、…ｔ＝Ｎに関連して状態Ｓ０、Ｓ１、Ｓ２、…Ｓ７を含む。それぞれのトレリス状態に関連するのは、アルファ（α）メトリックで、計算の開始点から現在の状態にある確率に関する。同様にそれぞれのトレリス状態に関連するのは、ベータ（β）メトリックで、現在の状態から正しい状態で終了する確率に関する。したがって、８個のαメトリックおよび８個のβメトリックが、トレリスのそれぞれの時点に関連する。
【００２２】
またトレリスは、ガンマ（γ）遷移メトリックによって特徴づけられ、第１の時点における１つの状態から次の時点における別の状態に移動する可能性に関する。したがって、例えば図３のトレリスにおいて、アルファメトリックα０およびα１は、それぞれ時間ｔ＝１での状態Ｓ０およびＳ１に関連する。遷移メトリックγは、時間ｔ＝０での状態Ｓ０から時間ｔ＝１でのＳ０への遷移に関連し、遷移メトリック−γは、時間ｔ＝０での状態Ｓ１から時間ｔ＝１での状態Ｓ１への遷移に関連する。一般に、アルファメトリックα０、α１、…α７は、それぞれトレリス状態Ｓ０、Ｓ１、…Ｓ７に関連する。同様に、ベータメトリックβ０、β１、…β７は、それぞれトレリス状態Ｓ０、Ｓ１、…Ｓ７に関連する。加えて、遷移メトリックγ０は、状態Ｓ０、Ｓ１、Ｓ２およびＳ３からの遷移に関連し、遷移メトリックγ１は、状態Ｓ４、Ｓ５、Ｓ６およびＳ７からの遷移に関連する。
【００２３】
それぞれのトレリス状態におけるアルファメトリックを計算するための式が図４に示され、ここでｋはトレリス状態を、ｓは時点を表す。図４の式の最後の項は、アルファメトリックの関数である訂正ファクタである。それぞれのトレリス状態におけるベータメトリックを計算するための式を図５に示す。図５の式の最後の項は、ベータメトリックの関数である訂正ファクタである。
【００２４】
図４の式を図３のトレリスに応用したものをここで説明する。状態Ｓ０およびＳ１における時間ｔ＝１でのアルファメトリックα０’およびα１’は、それぞれ以下の式で計算されてよい。
α０’＝MAX［α０＋γ０，α４−γ０］＋Ｃ０’ （１）
α１’＝MAX［α０−γ０，α４＋γ０］＋Ｃ１’ （２）
ここで、Ｃ０’およびＣ１’は、図４に示すようにα０およびα４の値に依存する訂正ファクタである。
【００２５】
したがって、それぞれの状態におけるアルファメトリックは、現在の状態への遷移が可能な２つの以前の状態それぞれにおいて、以前の状態のアルファメトリックと、２つの値を与えるための以前の状態から現在の状態への遷移に対する遷移メトリックとを代数的に合計（サム, sum）することによって計算される。そして、２つの値のうち最大値が選択される。訂正ファクタは、選択された最大値に加算される。以下に記述されるように、訂正ファクタは、ルックアップテーブルから得られてもよい。アルファメトリックは、トレリスのそれぞれの状態において、同類の様式で計算されてもよい。同様に、トレリスのそれぞれの状態におけるベータメトリックを計算するために、図５の式は、同類の様式で応用されてもよい。それぞれ２つの以前の状態のメトリックに基づく２つの状態のメトリックの計算は、通例“バタフライ”計算と呼ばれる。
【００２６】
また対数尤度率は、チャンネル復号と関連して計算される。対数尤度率は、状態１である確率と状態０である確率の比の対数である。対数尤度率を計算する式を図６に示す。以下に、対数尤度率の計算について詳細に議論する。
【００２７】
本発明の特性を実行するに適するデジタル信号プロセッサ（DSP）１１０の例のブロック線図を図７に示す。DSP１１０の主要なコンポーネントは、演算ブロック１１２および１１４、メモリ１１６、制御ブロック１２４、リンクポートバッファ１２６、外部ポート１２８，DRAMコントローラ１３０、命令整列バッファ（instruction alignment buffer）（IAB）１３２およびプライマリ命令復号器（primary instruction decoder）１３４である。演算ブロック１１２および１１４、命令整列バッファ１３２、プライマリ命令復号器１３および制御ブロック１２４は、DSPの主な演算機能およびデータ処理機能を実行するコアプロセッサを成す。外部ポート１２８は、外部アドレスバス１５８および外部データバス１６８を介する外部との伝達を制御する。リンクポートバッファ１２６は、コミュニケーションポート１３６を介する外部との伝達を制御する。DSPは、好ましくは単一のモノリシック集積回路として構成される。
【００２８】
メモリ１１６は、３つの独立した大容量メモリバンク１４０、１４２および１４４を含んでもよい。好適な態様において、メモリバンク１４０、１４２および１４４はそれぞれ、１ワードを３２ビットとして、６４Ｋワードの容量を有する。以下に議論されるように、それぞれのメモリバンク１４０、１４２および１４４は、好ましくは１２８ビットデータバスを有する。３２ビットごとに整列された、最大４つの連続したデータワードが、１クロックサイクルにおいて、それぞれのメモリバンクから転送され得る、もしくはメモリバンクに転送され得る。
【００２９】
DSP１１０の要素は、効率的で高速のオペレーションのために、バスによって相互に接続される。それぞれのバスは、バイナリ情報を並列転送するための複数のラインを含む。第１のアドレスバス１５０（MA０）は、メモリバンク１４０（M０）と制御ブロック１２４とを相互に接続する。第２のアドレスバス１５２（ＭA１）は、メモリバンク１４２（M１）と制御ブロック１２４とを相互に接続する。第３のアドレスバス１５４（ＭA２）は、メモリバンク１４４（M２）と制御ブロック１２４とを相互に接続する。アドレスバス１５０、１５２および１５４は、それぞれ好ましくは１６ビット幅である。外部アドレスバス１５６は、外部ポート１２８を通じて外部アドレスバス１５８に相互に接続される。外部アドレスバス１５６および１５８は、それぞれ好ましくは３２ビット幅である。
【００３０】
第１のデータバス１６０（MD０）は、メモリバンク１４０、演算ブロック１１２および１１４、制御ブロック１２４、リンクポートバッファ１２６、IAB１３２および外部ポート１２８を相互に接続する。第２のデータバス１６２（MD１）は、メモリバンク１４２、演算ブロック１１２および１１４、制御ブロック１２４、リンクポートバッファ１２６、IAB１３２および外部ポート１２８を相互に接続する。第３のデータバス１６４（MD２）は、メモリバンク１４４、演算ブロック１１２および１１４、制御ブロック１２４、リンクポートバッファ１２６、IAB１３２および外部ポート１２８を相互に接続する。データバス１６０、１６２および１６４は、外部ポート１２８を通じて外部データバス１６８に接続される。データバス１６０、１６２および１６４は、それぞれ好ましくは１２８ビット幅であり、外部データバス１６８は、好ましくは６４ビット幅である。
【００３１】
第１のアドレスバス１５０および第１のデータバス１６０は、データをメモリバンク１４０に転送するため、およびデータをメモリバンク１４０から転送するためのバスを含む。第２のアドレスバス１５２および第１のデータバス１６２は、データをメモリバンク１４２に転送するため、およびデータをメモリバンク１４２から転送するための第２のバスを含む。第３のアドレスバス１５４および第１のデータバス１６４は、データをメモリバンク１４４に転送するため、およびデータをメモリバンク１４４から転送するための第３のバスを含む。メモリバンク１４０、１４２および１４４は、それぞれ個々のバスを有するので、メモリバンク１４０、１４２および１４４は、同時にアクセスされてもよい。ここで使用される、“データ”は、バイナリワードを参照し、これは、DSP１１０のオペレーションに関連する命令もしくはオペランドのいずれかを表してもよい。
【００３２】
典型的な動作モードにおいて、プログラム命令は、前記メモリバンクの１つに記憶され、またオペランドは、その他の２つのメモリバンクに記憶される。したがって、１クロックサイクルにおいて、少なくとも１つの命令および２つのオペランドが、演算ブロック１１２および１１４に提供され得る。メモリバンク１４０、１４２および１４４は、１クロックサイクルにおいて、複数のデータワードの読み出しおよび書き込みを可能にするようにそれぞれ構成されてもよい。１クロックサイクルにおいて、それぞれのメモリバンクから同時に複数のデータワードを転送することは、命令キャッシュもしくはデータキャッシュを必要とせずに達成される。
【００３３】
以上に示したように、メモリバンク１４０、１４２および１４４は、それぞれ好ましくは、１ワードを３２ビットとして、６４Ｋワードの容量を有する。それぞれのメモリバンクは、１２８ビット幅であるデータバスに接続されてよい。代替の態様において、データバスは、それぞれ６４ビット幅でよく、そして６４ビットは、クロック位相１およびクロック位相２上で転送される、即ち１２８ビット幅の効果的なバスを提供する。複数のデータワードは、１クロックサイクルにおいて、それぞれのメモリバンク内でアクセスされ得る。特にデータは、各々３２ビットのシングルワード、もしくはデュアルワード、またはクアドワードとしてアクセスされ得る。
【００３４】
クアドワード転送を使用して、それぞれ３２ビットである４つの命令および８つのオペランドが、演算ブロック１１２および１１４に、１回のクロックサイクルで供給され得る。転送されるデータワードの数およびデータワードの転送先となる演算ブロックは、命令中の制御ビットによって選択される。シングルワードもしくはデュアルワードまたはクアドワードは、演算ブロック１１２もしくは演算ブロック１１４、またはこれらの両方に転送され得る。デュアルワードまたはクアドワードは、多くの応用において、いくつかのオペランドを１クロックサイクルで演算ブロック１１２または１１４に転送することを可能にすることによって、DSP１１０の性能を向上させる。各クロックサイクルで複数の命令にアクセスする能力は、複数のオペレーションを各クロックサイクルで実行することを可能にし、即ち性能を向上させる。
【００３５】
演算ブロック１１２および１１４のそれぞれの態様のブロック線図を図８に示す。マルチポートレジスタファイル２００は、オペランドおよび結果の一時的な記憶を提供する。好適な態様において、レジスタファイル２００は、１ワードを３２ビットとして、３２ワードの容量を有し、１列を１２８ビットとして８列で組織される。レジスタファイル２００は、マルチプレクサおよびラッチ（図示なし）を通じて、それぞれのデータバス１６０、１６２および１６４（図７）に接続される。オペランドは、メモリ１１６からフェッチされ、３つのデータバスのうち２つが選択され、選択されたバス上のオペランドが、レジスタファイル２００に供給される。
【００３６】
図８に示される演算ブロックは、乗算／累算器２１０、演算論理ユニット（ALU）２１２、シフタ２１４およびアクセラレータ２１６を含む。乗算／累算器２１０、ALU２１２、シフタ２１４およびアクセラレータ２１６は、十分な命令およびオペランドが演算ブロックに供給され得るまで、命令の同時実行が可能である。オペランドは、オペランドバス２２０上を、レジスタファイル２００から乗算／累算器２１０、ALU２１２、シフタ２１４およびアクセラレータ２１６に供給される。乗算／累算器２１０、ALU２１２、シフタ２１４およびアクセラレータ２１６の結果は、結果バス２２２上を戻る。演算ブロックのコンポーネントは、セカンダリ命令復号器２２４からの、復号化された命令に応答する信号によって制御される。演算ブロックは、性能を向上するために、好ましくはパイプライン構造を有する。
【００３７】
DSPにおける演算ブロック１１２および１１４は、ワイヤレス基地局での性能を高めるために、それぞれアクセラレータ２１６を含む。アクセラレータは、一時的にデータおよび制御値を記憶するためのレジスタ、および指定の命令を実行するためのアクセラレータ回路を含む。以下に、アクセラレータ２１６の機構およびオペレーションを詳細に説明する。
【００３８】
このDSP１１０は、例示の目的のためだけに説明されると理解される。本発明の特性は、異なるデジタル信号プロセッサ構造において実行されてもよい。
【００３９】
ACS命令、つまりトレリス命令に応答して、それぞれのアクセラレータによって実行されるオペレーションのデータフロー線図を図９に示す。レジスタペアTRmdのアルファメトリックもしくはベータメトリックなどのハイデータワードは、減算ユニット２５０および加算ユニット２５２に供給される。レジスタペアTRmdのローデータワードは、減算ユニット２５４および加算ユニット２５６に供給される。レジスタペアTRndのハイデータワードは、加算ユニット２５８および減算ユニット２６０に供給される。レジスタペアTRndのローデータワードは、加算ユニット２６２および減算２６４ユニットに供給される。
【００４０】
レジスタRmのハイデータワードは、ガンマ遷移メトリックであってもよく、減算ユニット２５０、加算ユニット２５２、加算ユニット２５８および減算ユニット２６０に供給される。レジスタRmのローデータワードは、減算ユニット２５４および加算ユニット２５６、加算ユニット２６２および減算ユニット２６４に供給される。減算ユニット２５０および加算ユニット２５８の出力は、MAX/TMAXユニット２７０に供給される。加算ユニット２５２および減算ユニット２６０の出力は、MAX/TMAXユニット２７２に供給される。減算ユニット２５４および加算ユニット２６２の出力は、MAX/TMAXユニット２７４に供給される。加算ユニット２５６および減算ユニット２６４の出力は、MAX/TMAXユニット２７６に供給される。MAX/TMAXユニット２７０、２７２、２７４および２７６の出力は、クアドレジスタTRsqに記憶される。
【００４１】
MAX/TMAXユニット２７０、２７２、２７４および２７６は、それぞれトレリス命令を指定してもよい１または２以上の関数を実行する。MAX関数において、２つの入力の最大値が選択され、クアドレジスタTRsqに記憶される。TMAX関数において、２つの入力の最大値が選択され、訂正値が選択される最大値に加算される。その和がクアドレジスタTRsqに記憶される。訂正ファクタは、MAX/TMAXユニットへの２つの入力の関数である。以下に説明されるように、訂正ファクタは、ルックアップテーブルから決定され得る。MAX/TMAXユニット２７０、２７２、２７４および２７６は、それぞれ出力ビットをビット選択レジスタペアTHRsに提供する。それぞれの出力ビットは、最大値として選択された入力を指し示す。
【００４２】
図９の態様において、アルファメトリックもしくはベータメトリックのようなレジスタペアTRmdおよびTRndのデータ値は、３２ビット値であり、遷移メトリックのようなレジスタRmのデータ値は、１６ビット値である。クアドレジスタTRsqに記憶される出力値は、３２ビット値である。図９の態様において、それぞれのアクセラレータは、単一のトレリス命令に応答して、トレリスの２つの３２ビットバタフライ演算を実行する。
【００４３】
図１０に示されるトレリス命令の別の態様において、それぞれのアクセラレータは、単一のトレリス命令に応答して、４つの１６ビットバタフライ演算を実行する。図１０において、レジスタペアTRmdおよびレジスタぺアTRndは、それぞれアルファメトリックもしくはベータメトリックのような４つの１６ビットデータ値を含有し、レジスタRmは、遷移メトリックのような４つの８ビット値を含有する。データ値は、８つの減算ユニット（２９０他）に、および８つの加算ユニット（２９２他）に供給され、減算ユニットおよび加算ユニットの出力は、８つのMAXユニット（２９４他）に供給される。
【００４４】
例えば、減算ユニット２９０は、データワードＳ３をレジスタペアTRmdから受信し、データワードＢ３をレジスタRmから受信する。加算ユニット２９２は、データワードＳ３をレジスタペアTRndから受信し、データワードＢ３をレジスタRmから受信する。減算ユニット２９０および加算ユニット２９２の出力は、MAXユニット２９４に供給される。MAXユニット２９４は、２つの入力の最大値を選択し、その最大値をクアドレジスタTRsqに記憶する。TMAXオプションは、図１０の態様には含まれていない。また、MAXユニットは、どの入力が選択されたかを指し示すために、出力ビットをレジスタペアTHRsに供給する。図１０中の残りのユニットは、単一のトレリス命令に応答して、トレリスの４つの１６ビットバタフライ演算を提供するために、同様の様式で動作する。
【００４５】
トレリス関数のアルファメトリックおよびベータメトリックを計算するためのソフトウェアコードの例を図１１に示す。図９によって図示され、以上で説明したオペレーションを実行するACS命令を使用して、このコードは実行される。図１１において、それぞれのACS命令は、図９に示されるような２つのトレリスバタフライ演算のための計算を指定する。ACS命令は、４つのバタフライ演算の総計を提供するために、演算ブロック１１２および１１４（図７参照）において実行される。この命令は、図１１に示されるように、与えられた時点での最初の４つのトレリスのステージにおけるアルファメトリックおよびベータメトリックを計算する第１命令と、ならびに与えられた時点での最後の４つのトレリスのステージにおけるアルファメトリックおよびベータメトリックを計算する第２命令とのペアにグループ化される。
【００４６】
したがって、ターボチャンネル復号器のための計算は、トレリスの１時点毎に２つの命令を使用して実行される。図１１のソフトウェアコードは、トレリスの４つの時点におけるメトリックを計算するためのオペレーションを含有するループを説明する。図１１のそれぞれの命令ラインにおけるオペレーションは、デジタル信号プロセッサによって、同時的に実行される。その他の実行において、第１命令は、与えられた時点でのトレリスの８つのステージにおけるアルファメトリックを計算してもよく、第２命令は、与えられた時点でのトレリスの８つのステージにおけるベータメトリックを計算してもよい。
【００４７】
図１１の第１命令ラインにおいて、TR11:8は、図９のクアドレジスタTRsqに対応する。また、第１命令ラインのTR5:4およびTR1:0は、それぞれレジスタペアTRmdおよびレジスタペアTRndに対応する。レジスタsR24は、図９のレジスタRmに対応する。この命令は、単一のACS命令もしくはトレリス命令に応答して、４つのバタフライ演算を実行するために、両方の演算ユニットにおいて、異なるデータ値を伴って実行されてもよいと理解されるであろう。図１１の第１命令ラインはさらに、レジスタTR7:4のデータが、レジスタファイル２００（図８）のレジスタR7:4に移動すること明確にしている。加えて、第１命令ラインは、演算ユニット１１２のレジスタxR3:0および演算ユニット１１４のレジスタyR3:0に対するメモリロードオペレーションを指定する。
【００４８】
図１１のソフトウェアコードにおける最初の２つの命令ラインの実行は、図１２および図１３を参照して説明される。図１２は、DSP１１０の第１サイクルでのトレリス状態Ｓ０〜Ｓ３におけるアルファメトリックおよびベータメトリックの計算を説明し、図１３は、DSP１１０の第２サイクルでのトレリス状態Ｓ４〜Ｓ７におけるアルファメトリックおよびベータメトリックの計算を説明する。図１２に示されるように、演算ブロック１１２のアクセラレータ回路３００は、レジスタペアTR5:4、レジスタペアTR1:0およびレジスタsR24からデータ値を受信し、出力データをクアドレジスタTR11:8に供給する。同様に、演算ブロック１１４のアクセラレータ回路３０２は、レジスタペアTR5:4、レジスタペアTR1:0およびレジスタsR24からデータ値を受信し、出力データをクアドレジスタTR11:8に供給する。図１２に図示されるレジスタは、図１１の最初の命令ラインの中のACS命令によって指定されるレジスタに対応する。
【００４９】
好適な態様において、TRレジスタは、それぞれのアクセラレータ２１６（図８）に配置され、Rレジスタは、それぞれのレジスタファイル２００に配置される。図１２のレジスタペアTR5:4は、図９のレジスタペアTRmdに対応し、レジスタペアTR1:0は、レジスタペアTRndに対応する。同様に、図１２のレジスタsR24は、図９のレジスタRmに対応し、クアドレジスタTR11:8は、図９のクアドレジスタTRsqに対応する。図１２は、SIMDオペレーションを説明し、ここでは単一の命令は、異なるデータを伴って、アクセラレータ回路３００および３０２などの２以上の実行ユニットによって実行される。
【００５０】
図１２に示されるように、図１１の最初の命令ラインは、トレリス状態Ｓ０〜Ｓ３におけるアルファメトリックおよびベータメトリックを計算する。特に、アクセラレータ回路３００は、レジスタペアTR5:4に含有されるα５およびα４の値と、レジスタペアTR1:0に含有されるα１およびα０の値と、レジスタsR24に含有されるγ１およびγ０との値に基づいて、アルファメトリックα０’、α１’、α２’およびα３’を計算する。同様に、アクセラレータ回路３０２は、レジスタペア5:4に含有されるβ５およびβ４の値と、レジスタペアTR1:0に含有されるβ１およびβ０の値と、レジスタsR24に含有されるγ１およびγ０との値に基づいて、ベータメトリックβ０’、β１’、β２ ’およびβ２’を計算する。
【００５１】
ここで、図１３を参照すると、第２のデジタル信号プロセッササイクルの間のトレリス状態Ｓ４〜Ｓ８におけるアルファメトリックおよびベータメトリックの計算が示されている。図１３のオペレーションは、図１１の第２の命令ラインに対応する。アクセラレータ回路３００は、レジスタペアTR7:6に含有されるα７およびα６の値と、レジスタペアTR3:2に含有されるα３およびα２の値と、レジスタsR25に含有されるγ１およびγ０との値に基づいて、アルファメトリックα４’、α５’、α６’およびα７’を計算する。同様に、アクセラレータ回路３０２は、レジスタペアTR7:6に含有されるβ７およびβ６の値と、レジスタペアTR3:2に含有されるβ３およびβ２の値と、レジスタsR25に含有されるγ１およびγ０との値に基づいて、アルファメトリックβ４’、β５’、β６’およびβ７’を計算する。
【００５２】
アクセラレータ３００および３０２は、図１２に示されるように、第１DSPサイクルにおいて４つのバタフライ演算を実行し、また図１３に示されるように、第２のDSPサイクルにおいて４つのバタフライ演算を実行し、それによってデジタル信号プロセッサの２回のサイクルでの８個のトレリス状態における完全なアルファメトリックおよびベータメトリックを計算する。したがって、図１１のソフトウェアコードは、トレリスの４つの時点におけるアルファメトリックおよびベータメトリックを計算する。図１１〜１３の態様において、演算ブロック１１２のアクセラレータレジスタTR0:7は、第１の時点でのトレリス状態Ｓ０〜Ｓ７におけるアルファメトリックを含有し、アクセラレータレジスタTR8:15は、第２の時点でのトレリス状態Ｓ０〜Ｓ７におけるアルファメトリックを含有する。同様に、演算ブロック１１４のアクセラレータレジスタTR0:7は、第１の時点でのトレリス状態Ｓ０〜Ｓ７におけるベータメトリックを含有し、アクセラレータレジスタTR7:15は、第２の時点でのトレリス状態Ｓ０〜Ｓ７におけるベータメトリックを含有する。
【００５３】
第１のタイプのlog MAP命令に応答して、実行されるオペレーションを説明するデータフロー線図が、図１４に図示される。データ値は、レジスタペアTRmdおよびTRndならびにクアドレジスタRmqに保持される。それぞれのデータ値は、図１４の例において、３２ビットである。データ値は、アルファメトリックもしくはベータメトリックまたは遷移メトリックを表してもよい。加算ユニット３３０は、レジスタペアTRmdからハイデータワードを受信し、第１データワードをクアドレジスタRmqから受信する。加算ユニット３３２は、レジスタペアTRmdからローデータワードを受信し、第２データワードをクアドレジスタRmqから受信する。加算ユニット３３４は、レジスタペアTRndからハイデータワードを受信し、第３データワードをクアドレジスタRmqから受信する。加算ユニット３３６は、レジスタペアTRndからローデータワードを受信し、第４データワードをクアドレジスタRmqから受信する。TMAXユニット３４０は、加算ユニット３３０および３３４の出力を受信する。TMAXユニット３４２は、加算ユニット３３２および３３６の出力を受信する。
【００５４】
それぞれTMAXユニット３４０および３４２は、２つの入力の最大値を選択し、訂正ファクタを選択された最大値に加算する。上記の通り、訂正ファクタは、２つの入力値の関数であり、ルックアップテーブルとして実行されてもよい。TMAXユニット３４０および３４２の出力は、クアドレジスタTRsdに記憶される。図１４に説明される命令は、クアドレジスタRmqに含有されるデータ値を、レジスタペアTRmdおよびTRndに含有されるそれぞれのデータ値に加算し、２つの加算ユニットの出力の最大値を選択し、そして選択された最大値に訂正ファクタを加算する。
【００５５】
第２のタイプのlog MAP命令に応答して、実行されるオペレーションを説明するデータフロー線図が、図１５に図示される。図１４および図１５において同等の要素は、同一の参照符号を有する。図１４の加算ユニット３３０、３３２、３３４および３３６が、減算ユニット３５０、３５２、３５４および３５６にそれぞれ置換されていることを除いて、図１５に図示されるオペレーションは、図１４に図示されるものと類似している。したがって、TMAXユニット３４０は、減算ユニット３５０および３５４の出力を受信し、TMAXユニット３４２は、減算ユニット３５２および３５６の出力を受信する。図１５で説明される命令は、クアドレジスタRmqに含有されるデータ値をレジスタペアTRmdおよびTRndに含有されるデータ値から減算し、２つの減算ユニットの出力の最大値を選択し、そして選択された最大値に訂正ファクタを加算する。
【００５６】
トレリス関数の対数尤度率を計算するためのソフトウェアコードの例が、図１６に示される。このコードは、TMAX命令を使用して実行され、これは図１４および図１５で図示され、以上で説明されたオペレーションを実行する。図１６において、TMAX命令は、図１４または図１５に示されるように、それぞれ２つのlog MAP計算のための計算を指定する。TMAX命令は、４つのlog MAP計算の総計を提供するために、演算ブロック１１２および１１４（図７）において実行される。
【００５７】
図１６の第１命令ラインにおいて、TR1:0およびTR3:2は、レジスタペアTRmdおよびレジスタペアTRndにそれぞれ対応する。また、第１命令ラインにおいて、R9:8およびR11:10は、図１４のクアドレジスタRmqに対応する。指定されたレジスタに含有されるデータ値は、図１４もしくは図１５に示されるように、そして以上で説明されたように処理される。この命令は、単一のTMAX命令に応答して、４つのlog MAP計算を実行するために、両方の演算ユニットにおいて、異なるデータ値を伴って実行されてもよいと理解されるであろう。
【００５８】
図１６のソフトウェアコードの第１命令ラインの実行が、図１７を参照して説明される。図１７に示されるように、演算ブロック１１２のアクセラレータ回路３００は、レジスタペアTR1:0、R9:8、TR3:2およびR11:10からデータ値を受信し、出力データ値をレジスタペアTR9:8に供給する。同様に、演算ブロック１１４のアクセラレータ回路３０２は、レジスタペアTR1:0、R9:8、TR3:2およびR11:10からデータ値を受信し、出力データ値をレジスタペアTR9:8に供給する。それぞれアクセラレータ回路３００および３０２は、図１４または図１５に示されるオペレーションを、該命令が指定するように実行する。
【００５９】
それぞれアクセラレータ回路３００および３０２（図１２、図１３、および図１７）の態様が、図１８に示される。アクセラレータ回路は、第１パイプラインステージ４００、第２パイプラインステージ４０２および第３パイプラインステージ４０４を含むパイプライン構造を有する。第１パイプラインステージ４００と第２パイプラインステージ４０２は、ステージレジスタ４１０および４１２を通じて接続され、第２パイプラインステージ４０２と第３パイプラインステージ４０４は、ステージレジスタ４１４を通じて接続される。第１ステージ４００は、EXORゲート（exclusive OR gate）、４入力キャリーセーブ加算器４２４および３２ビット加算器４２６を含む。第２ステージ４０２は、マルチプレクサ４３０、ルックアップテーブル４３２および３入力キャリーセーブ加算器４３４を含む。第３ステージ４０４は、３２ビット加算器４４０を含む。レジスタ４１４のバイパス結果出力は、２つのパイプライン位相を以下に説明されるように実行するために、マルチプレクサ４４２を通じて、入力OP1および入力OP2につながれる。
【００６０】
図１８に示されるアクセラレータ回路は、ACS命令を実行するために使用されてもよい。図９を参照して、ACS命令は、以下のオペレーションを実行する。
MAX（TRmd＋Rm，TRnd−Rm）＋Ｃ （３）
ここで、Ｃは任意の訂正ファクタである。MAXオペレーションは、下記を得るための、係る括弧の２つの値の減算に相当する。
TRmd−TRnd＋２Rm （４）
【００６１】
そして、該回路は、数式（４）の値が正であるか負であるかを決定する。数式（４）の値が正である場合、数式（３）の括弧内の第１項が最大値であり、前記値が負である場合、数式（３）の括弧内の第２項が最大値である。
【００６２】
ACS命令の実行されているとき、レジスタTRmdのデータ値は、入力OP1および入力OP2に供給され、レジスタTRndのデータ値は、入力OP3に供給され、またデータ値2Rmは、入力OP4に供給される。３２ビット加算器４２６の出力は、上記数式の値を表す。この値は、ルックアップテーブル４３２の訂正ファクタにアクセスするために使用される。３２ビット加算器４２６の出力のサインは、マルチプレクサ４３０のための制御信号として使用され、それにより、TRmdとRm、あるいはTRndとRmを選択する。選択される値およびルックアップテーブル４３２の出力は、キャリーセーブ加算器４３４の入力に供給される。３２ビット加算器４４０の出力は、選択される最大値とルックアップテーブル４３２によって提供される訂正ファクタＣとの合計を表す。
【００６３】
２つのパイプラインサイクルへのACS命令の実行時間を減少させるために、キャリーセーブ加算器４３４の出力は、キャリーセーブ加算器４２４の入力OP1および入力OP2に供給されてもよい。以前のACS命令の結果が使用されているとき、加算器４２４のキャリー出力は、マルチプレクサ４４２を通じて、入力OP1に供給されてもよく、加算器４２４のサム（sum）出力は、マルチプレクサ４４２を通じて、入力OP2に供給されてもよい。アクセラレータへの入力は、レジスタから提供され、そしてバイパス関数は利用されず、レジスタ入力は、マルチプレクサ４４２を通じて、入力OP1に供給される。もし訂正ファクタが、ACS命令において利用されないような場合ならば、ルックアップテーブル４３２の出力は、ゼロである。
【００６４】
図１８に示されるアクセラレータ回路は、TMAX命令を実行するために使用されてもよい。図１４を参照して、TMAX命令は、以下のオペレーションを実行する。
MAX（TRmd＋Rm3，TRnd＋Rm1）＋Ｃ （５）
数式（５）のMAXオペレーションは、以下のような２つの値の減算に相当する。
TRmd＋Rm3−TRnd−Rm1 （６）
そして、該回路は、数式（６）の値が正であるか負であるかを決定する。数式（６）の値が正である場合、数式（５）の括弧内の第１項が最大値であり、前記値が負である場合、数式（５）の括弧内の第２項が最大値である。
【００６５】
図１８を参照して、TMAX命令を実行するために、レジスタTRmdの値が入力OP1に供給され、レジスタRm1の値が入力OP2に供給され、またレジスタTRndの値がOP3に供給され、レジスタRm2の値が入力OP4に供給される。ACSに類似の様式で、３２ビット加算器４２６は、ルックアップテーブル４３２にアクセスするために使用され、加算器４２６の出力のサインは、マルチプレクサ４３０を制御するために使用される。マルチプレクサ４３０は、最大値を選択し、最大値をキャリーセーブ加算器４３４に供給する。加算器４３４は、出力結果を提供するために、選択される最大値とルックアップテーブル４３２からの訂正値を加算する。
【００６６】
現時点における本発明の好適な態様として考慮されるものについて、以上に示され、説明されたが、付記の特許請求の範囲に係る発明の範囲を離れない各種の変種および改変は、当業者にとって容易に想到し得るものとみなされるであろう。
【図面の簡単な説明】
【００６７】
【図１】ワイヤレス基地局の信号チェーンのブロック線図である。
【図２】ターボ復号アルゴリズムのブロック線図である。
【図３】８状態トレリスの概要の説明図である。
【図４】トレリスのαメトリックの計算式の説明図である。
【図５】トレリスのβメトリックの計算式の説明図である。
【図６】トレリスの対数尤度率の計算式の説明図である。
【図７】本発明の側面に従うチャンネル復号を実行するために適するデジタル信号プロセッサのブロック線図である。
【図８】図７のデジタル信号プロセッサ中に示されるそれぞれの演算ブロックの態様のブロック線図である。
【図９】トレリス命令に応答して実行され得る演算の第１の態様を説明するデータフロー線図である。
【００６８】
【図１０】トレリス命令に応答して実行され得る演算の第２の態様を説明するデータフロー線図である。
【図１１】本発明の側面にしたがって、ターボチャンネル復号を実行するソフトウェアコードの説明図である。
【図１２】第１デジタル信号プロセッササイクルにおけるトレリス状態Ｓ０―Ｓ３でのαメトリックおよびβメトリックの計算を説明する概要のブロック線図である。
【図１３】第２デジタル信号プロセッササイクルにおけるトレリス状態Ｓ４―Ｓ７でのαメトリックおよびβメトリックの計算を説明する概要のブロック線図である。
【図１４】第１log MAP命令に応答して実行されるオペレーションを説明するデータフロー図である。
【図１５】第２log MAP命令に応答して実行されるオペレーションを説明するデータフロー図である。
【図１６】log MAP命令を使用するトレリスの対数尤度率を計算するためのソフトウェアコードの説明図である。
【図１７】図１６のソフトウェアコードにおける第１命令ラインの実行に使用されるハードウェアのコンポーネントを説明するブロック線図である。
【図１８】図８のアクセラレータの態様を説明するブロック線図である。
【図１】
2004538704.tif 000003
【図２】
2004538704.tif 000004
【図３】
2004538704.tif 000005
【図４】
2004538704.tif 000006
【図５】
2004538704.tif 000007
【図６】
2004538704.tif 000008
【図７】
2004538704.tif 000009
【図８】
2004538704.tif 000010
【図９】
2004538704.tif 000011
【図１０】
2004538704.tif 000012
【図１１】
2004538704.tif 000013
【図１２】
2004538704.tif 000014
【図１３】
2004538704.tif 000015
【図１４】
2004538704.tif 000016
【図１５】
2004538704.tif 000017
【図１６】
2004538704.tif 000018
【図１７】
2004538704.tif 000019
【図１８】
2004538704.tif 000020
【国際公開パンフレット】
2004538704.tif 000021
2004538704.tif 000022
2004538704.tif 000023
2004538704.tif 000024
2004538704.tif 000025
2004538704.tif 000026
2004538704.tif 000027
2004538704.tif 000028
2004538704.tif 000029
2004538704.tif 000030
2004538704.tif 000031
2004538704.tif 000032
2004538704.tif 000033
2004538704.tif 000034
2004538704.tif 000035
2004538704.tif 000036
2004538704.tif 000037
2004538704.tif 000038
2004538704.tif 000039
2004538704.tif 000040
2004538704.tif 000041
2004538704.tif 000042
2004538704.tif 000043
2004538704.tif 000044
2004538704.tif 000045
2004538704.tif 000046
2004538704.tif 000047
2004538704.tif 000048
2004538704.tif 000049
2004538704.tif 000050
2004538704.tif 000051
2004538704.tif 000052
2004538704.tif 000053
2004538704.tif 000054
2004538704.tif 000055
2004538704.tif 000056
2004538704.tif 000057
2004538704.tif 000058
2004538704.tif 000059
2004538704.tif 000060
2004538704.tif 000061
2004538704.tif 000062
【手続補正書】
【提出日】平成15年6月3日(2003.6.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法であって、
プログラム可能なデジタル信号プロセッサを提供するステップ、；
選択されるトレリス状態において、ある時間ｔ０でのトレリス状態メトリックの位置、および時間ｔ０から時間ｔ１への遷移メトリックの位置を指定する単一のトレリス命令に応答して、時間ｔ０での第１状態メトリックに遷移メトリックを加算し、第１の値を提供するステップ、時間ｔ０での第２の状態メトリックから遷移メトリックを減算し、第２の値を提供するステップ、；および
それぞれの選択される状態メトリックにおいて、対応する第１の値と第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのトレリス状態メトリックを提供するステップ、とを含み、
前記加算するステップ、減算するステップ、比較するステップ、および選択するステップが、単一のトレリス命令に応答して、前記プログラム可能なデジタル信号プロセッサによって実行される、前記方法。
【請求項２】
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項１に記載の方法。
【請求項３】
訂正ファクタを加算するステップが、訂正ファクタを含有するルックアップテーブルにアクセスすることを含む、請求項２に記載の方法。
【請求項４】
前記トレリス命令が、αトレリス状態メトリックを計算するための前方トレリス関数を実行する、請求項１に記載の方法。
【請求項５】
前記トレリス命令が、βトレリス状態メトリックを計算するための逆方向トレリス関数を実行する、請求項１に記載の方法。
【請求項６】
前記トレリス命令が、単一の命令、複数のデータアプローチを使用して、αトレリス状態メトリックを計算するための前方トレリス関数、およびβトレリス状態メトリックを計算するための逆方向トレリス関数を同時に実行する、請求項１に記載の方法。
【請求項７】
デジタル信号プロセッサにおいて、トレリス関数のメトリックを計算するための方法であって、
プログラム可能なデジタル信号プロセッサを提供するステップ、；
ある時間ｔ０でのαメトリックおよび単一のトレリス命令によって指定される時間ｔ０から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのαメトリックを計算するステップ、；および
ある時間ｔ２でのβメトリック、および単一のトレリス命令によって指定される時間ｔ２から時間ｔ１への遷移メトリックに応答して、選択されるトレリス状態における時間ｔ１でのβメトリックを計算するステップ、とを含み、
αメトリックを計算するステップとβメトリックを計算するステップが、単一のトレリス命令に応答して、前記プログラム可能なデジタル信号プロセッサによって実行される、前記方法。
【請求項８】
選択されるトレリス状態におけるαメトリックを計算するステップが、
それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ０での第１のαメトリックに加算して、第１の値を提供するステップ、遷移メトリックを時間ｔ０での第２のαメトリックから減算して、第２の値を提供するステップ、；および
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのαメトリックを提供するステップ、を含む請求項７に記載の方法。
【請求項９】
選択されるトレリス状態におけるαメトリックを計算するステップが、それぞれの選択されるトレリス状態に対して、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項８に記載の方法。
【請求項１０】
選択されるトレリス状態におけるβメトリックを計算するステップが、
それぞれの選択されるトレリス状態において、遷移メトリックを時間ｔ２での第１のβメトリックに加算して、第１の値を提供するステップ、遷移メトリックを時間ｔ２での第２のβメトリックから減算して、第２の値を提供するステップ、；および
それぞれの選択されるトレリス状態において、対応する第１の値および第２の値を比較するステップ、；ならびに
それぞれの選択されるトレリス状態において、対応する第１の値と第２の値のうち最大値を選択して、時間ｔ１でのβメトリックを与えるステップ、を含む請求項７に記載の方法。
【請求項１１】
それぞれの選択されるトレリス状態におけるβメトリックを計算するステップが、対応する第１の値および第２の値の関数である訂正ファクタを前記最大値に加算するというステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
それぞれの選択されるトレリス状態におけるαメトリックを計算するステップが、単一のトレリス命令に応答して、複数のトレリス状態におけるαメトリックを計算するステップを含む、請求項７に記載の方法。
【請求項１３】
それぞれの選択されるトレリス状態におけるβメトリックを計算するステップが、単一のトレリス命令に応答して、複数のトレリス状態におけるβメトリックを計算するステップを含む、請求項７に記載の方法。
【請求項１４】
αメトリックを計算するステップとβメトリックを計算するステップとが、同時に行われる、請求項７に記載の方法。
【請求項１５】
デジタル信号プロセッサにおいて、log MAP関数を計算する方法であって、
プログラム可能なデジタル信号プロセッサを提供するステップ、；
第１，第２、第３、および第４のパラメータの位置を指定する単一のlog MAP命令に応答して、第１パラメータと第２パラメータの和もしくは差を計算し、第１の値を提供するステップ、第３パラメータと第４パラメータの和もしくは差を計算して、第２の値を提供するステップ、；および
第１の値と第２の値のうち最大値を選択するステップ、；ならびに
第１の値および第２の値の関数である訂正ファクタを前記最大値に加算して、log MAP結果を提供するステップ、を含み、
前記和もしくは差を計算するステップ、最大値を選択するステップ、および訂正ファクタを加算するステップが、単一のトレリス命令に応答して、前記プログラム可能なデジタル信号プロセッサによって実行される前記方法。
【請求項１６】
訂正ファクタを加算するステップが、訂正ファクタを含有するルックアップテーブルにアクセスすることを含む、請求項１５に記載の方法。
【請求項１７】
単一のlog MAP命令に応答して、２以上のlog MAP結果が計算される、請求項１５に記載の方法。
【請求項１８】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
プログラム可能な演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、ある時間ｔ０でのトレリス状態メトリックの位置、および時間ｔ０から時間ｔ１への遷移メトリックの位置を指定するトレリス命令を実行するためのアクセラレータであって、遷移メトリックを時間ｔ０での第１状態メトリックに加算して、第１の値を提供する加算器、および時間ｔ０での第２状態メトリックから遷移メトリックを減算して、第２の値を提供する加算器を含む、単一のトレリス命令に応答する前記アクセラレータと、単一のトレリス命令に応答し、それぞれのトレリス状態において対応する第１の値および第２の値のうち、最大値を決定するための比較器と、単一のトレリス命令に応答し、選択されるトレリス状態において対応する第１の値および第２の値のうち、最大値を選択するためのデータセレクタとを含む前記演算ブロック、とを含むプロセッサ。
【請求項１９】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
プログラム可能な第１演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、トレリス命令によって指定される、ある時間ｔ０でのαメトリックおよび時間ｔ０から時間ｔ１への遷移メトリックに応答して、トレリス命令を実行するためのアクセラレータであって、時間ｔ０でのαメトリックおよび遷移メトリックに基づいて、時間ｔ１での選択されるトレリス状態におけるαメトリックを計算するための手段を含む、単一のトレリス命令に応答する前記アクセラレータ、を含む前記第１演算ブロックと、；
プログラム可能な第２演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、命令によって指定される、ある時間ｔ２でのβメトリックおよび時間ｔ２から時間ｔ１への遷移メトリックに応答して、トレリス命令を実行するためのアクセラレータであって、単一のトレリス命令に応答し、時間ｔ２でのβメトリックおよび時間ｔ２から時間ｔ１への遷移メトリックに基づいて、時間ｔ１での選択されるトレリス状態におけるβメトリックを計算するための手段を含む前記アクセラレータ、を含む前記第２演算ブロック、とを含むプロセッサ。
【請求項２０】
デジタル信号演算のための命令およびオペランドを記憶するメモリと；
選択される１つの命令を前記メモリからフェッチする命令アドレスを生成するためのプログラムシーケンサと、；
プログラム可能な演算ブロックであって、オペランドおよび結果を一時的に記憶するためのレジスタファイルと、第１、第２、第３、および第４のパラメータの位置を指定するlog MAP命令を実行するためのアクセラレータであって、単一のlog MAP命令に応答し、第１パラメータと第２パラメータの和もしくは差を計算して、第１の値を提供する第１加算器、ならびに単一のlog MAP命令に応答し、第３パラメータと第４パラメータの和もしくは差を計算して、第２の値を提供する第２加算機を含む前記アクセラレータと、単一のlog MAP命令に応答し、第１の値および第２の値のうち、最大値を選択するためのデータセレクタと、単一のlog MAP命令に応答し、第１の値および第２の値の関数である訂正ファクタを生成するためのルックアップテーブルと、単一のlog MAP命令に応答し、訂正ファクタを前記最大値に加算して、log MAPの結果を提供するための第３加算器、を含む前記演算ブロック、とを含むプロセッサ。
【請求項２１】
デジタル信号プロセッサ演算ブロックに使用されるアクセラレータであって、
アクセラレータへの入力を受信する第１キャリーセーブ加算器と；
前記第１キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第１全加算器と；
前記第１全加算器の出力に応答して、訂正ファクタを生成するルックアップテーブルと；
前記第１全加算器の出力サインに応答して、１または２以上のアクセラレータへの入力を選択するためのマルチプレクサと；
１または２以上のマルチプレクサの出力とルックアップテーブルの出力を加算するための第２キャリーセーブ加算器と；
前記第２キャリーセーブ加算器のサム出力とキャリー出力とを組み合わせる第２全加算器、
とを含む、前記アクセラレータ。
【請求項２２】
第１キャリーセーブ加算器が４個の入力を有し、マルチプレクサが４個の出力のうち２個を選択し、第２キャリーセーブ加算器が３個の入力を有する、請求項２１に記載のアクセラレータ。
【請求項２３】
前記第２キャリーセーブ加算器のサム出力とキャリー出力とを第１キャリーセーブ加算器の出力に供給するためのデータセレクタをさらに含む、請求項２２に記載のアクセラレータ。
【請求項２４】
前記第１キャリーセーブ加算器および前記第１全加算器が、第１パイプラインステージ、前記ルックアップテーブル、および前記マルチプレクサを含み、前記第２キャリーセーブ加算器が、第２パイプラインステージを含み、前記第２全加算器が第３パイプラインステージを含む、請求項２１に記載のアクセラレータ。
【国際調査報告】
2004538704.tif 000063
2004538704.tif 000064