(57)【要約】【課題】加算比較選択（ＡＣＳ）演算を行う方法及び装置を提供すること。【解決手段】述べられる実施形態では、トレリス復号器は、１組のレジスタを含むメモリと、加算比較選択（ＡＣＳ）モジュールであって、少なくとも２つのＡＣＳレイヤモジュールであって、直列に結合され単一クロックサイクル内のキャリー成分を有する帰還ループを形成するように構成され、複数のビット、及びキャリーセーブ算術を用いて複数の状態メトリックを発生させるように構成された加算器によって表される少なくとも２つのブランチ・メトリック、ならびにキャリー成分としてメモリに記憶されたキャリーセーブ算術における最大状態メトリックの選択を行うように構成された複数のマルチプレクサを含む、少なくとも２つのＡＣＳレイヤモジュールを含む、加算比較選択（ＡＣＳ）モジュールとを含む。高速ＡＣＳ演算を行う方法が開示される。【選択図】図３
2014045480.tif 000002
【特許請求の範囲】
【請求項１】
加算比較選択（ＡＣＳ）演算を反復的に行う方法であって、反復のために、
キャリーセーブ算術を用いて少なくとも２つの状態メトリックを、第１のそれぞれの和成分を有する第１のＡＣＳレイヤモジュールに供給することと、
前記第１のＡＣＳレイヤモジュールによって、単一クロックサイクル内で、少なくとも２つのそれぞれのブランチ・メトリックの第１の組に応答して、キャリーセーブ算術における少なくとも２つの計算状態メトリックの第１の組を生成することと、
少なくとも２つの計算状態メトリックの前記第１の組を、第２のそれぞれの和及びキャリー成分を有する第２のＡＣＳレイヤモジュールに付与することと、
前記第２のＡＣＳレイヤモジュールによって、クロックサイクル内で、少なくとも２つのそれぞれのブランチ・メトリックの第２の組及び少なくとも２つの計算状態メトリックの前記第１の組に応答して、キャリーセーブ算術における少なくとも２つの計算状態メトリックの第２の組を生成することと、
少なくとも他の２つの計算状態メトリックの前記第２の組を、前記第２のＡＣＳレイヤモジュールのキャリー成分として記憶することと、
少なくとも２つの計算状態メトリックの前記第２の組を、次の反復のために前記第１のＡＣＳレイヤモジュールに供給すること
を含む方法。
【請求項２】
前記記憶することのために、前記キャリー成分がレジスタに記憶される、請求項１に記載の方法。
【請求項３】
加算比較選択（ＡＣＳ）演算を行う方法であって、
単一クロックサイクル内でキャリー成分を有する反復ループを形成するように構成された、直列に結合された少なくとも２つのＡＣＳレイヤを含み、
前記ＡＣＳレイヤは、複数のビット、及び（ｉ）キャリーセーブ算術に従って複数の状態メトリックを発生させるように構成された加算器によって表される少なくとも２つのブランチ・メトリック、ならびに（ｉｉ）前記キャリー成分に記憶されたキャリーセーブ算術における最大状態メトリックの選択を行うように構成された複数のマルチプレクサを含む、
方法。
【請求項４】
前記キャリー成分が、対応するレジスタに記憶される、請求項３に記載の方法。
【請求項５】
前記ＡＣＳモジュールが、４個のオペランドのＡＣＳ演算（ＡＣＳ４）を行うように構成された、請求項３に記載の方法。
【請求項６】
前記ＡＣＳモジュールが、８個のオペランドのＡＣＳ演算（ＡＣＳ８）を行うように構成された、請求項３に記載の方法。
【請求項７】
前記ＡＣＳモジュールが、１６個のオペランドのＡＣＳ演算（ＡＣＳ１６）を行うように構成された、請求項３に記載の方法。
【請求項８】
加算比較選択（ＡＣＳ）演算を行うための装置であって、
それぞれが対応する入力及び出力状態ならびに対応する入力及び出力ベクトルを有する、キャリーセーブ算術を用いて状態メトリック計算を行うように構成された、ＡＣＳモジュールの少なくとも２つのレイヤと、
記憶された状態メトリックのキャリー成分とを備え、
前記ＡＣＳモジュールの先行レイヤの前記出力状態は、前記ＡＣＳモジュールの前記先行レイヤの前記入力ベクトルとは異なる入力ベクトルを有する前記ＡＣＳモジュールの後続レイヤに供給され、前記装置は少なくともキャリーセーブ算術における最大状態メトリックを発生させるために、単一クロックサイクル内で計算するＡＣＳレイヤを形成するように構成されている、装置。
【請求項９】
前記キャリー成分が、対応するレジスタに記憶される、請求項８に記載の装置。
【請求項１０】
前記ＡＣＳモジュールが、４個のオペランド、８個のオペランド及び１６個のオペランドのうちの少なくとも１つのＡＣＳ演算（ＡＣＳ４）を行うように構成された、請求項８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は、復号器回路に関し、詳細には、ターボ及び低密度パリティチェック符号（low-density parity-check code：ＬＤＰＣ符号）を復号するための、ビタビ（Viterbi）復号器及び対数最大事後（log-maximum a posteriori：ｌｏｇ−ＭＡＰ）復号器において有用な、高速加算比較選択（high speed add-compare-select：ＡＣＳ）回路に関する。
【背景技術】
【０００２】
ＡＣＳユニットは、ビタビ復号器、ターボ復号器及びｌｏｇ−ＭＡＰ復号器のコア要素である。ＡＣＳユニットがそれら自体の間で接続されるやり方は、特定の符号のトレリス（trellis：格子）図によって規定される。ＡＣＳ演算は、ビタビ及びｌｏｇ−ＭＡＰなどのこのようなトレリスベースの復号アルゴリズムに対する隘路となる算術演算である。これらのアルゴリズムは、畳み込み、ターボ及びＬＤＰＣ符号の復号のために広く用いられる。ビタビアルゴリズム及びｌｏｇ−ＭＡＰアルゴリズムはそれらのアルゴリズムがハードウェアにて実施される場合は、対応するビタビ及び／又はｌｏｇ−ＭＡＰアルゴリズムの実施のクリティカルパス上に各ＡＣＳ演算が現れるように構成される。ＡＣＳ演算は、アルゴリズムの深さ及び対応する復号器の最大動作周波数を決定する。
【０００３】
一般的なトレリスベースの復号アルゴリズムの復号プロセスは、通常は反復プロセス（iteration process）である。各反復は、トレリスの単一のレイヤにおいて処理される。トレリスレイヤの総数は、一般に符号語の長さに等しい。あらゆるトレリスレイヤに対して行われる計算手順は２つのステップすなわち、（ｉ）ブランチ・メトリック計算、及び（ｉｉ）状態メトリック計算を含む。これら２つのステップは、ビタビアルゴリズム又はｌｏｇ−ＭＡＰアルゴリズムの場合に共通である。ブランチ・メトリック計算は、復号器のハードウェア実装部のクリティカルパス上には存在しないので、ブランチ・メトリック計算は諸トレリスレイヤにわたってパイプライン化することができる。これと反対に状態メトリック計算は、内部ループバック構造を含む。次の反復の結果は本質的に、状態メトリック計算に対する前の反復の結果に依存する。したがって状態メトリック計算は復号器のクリティカルパス上に存在し、その結果として復号器の全体の設計の最大可能動作周波数を決定する。
【０００４】
図１は、計算が各レイヤにおいて行われる従来のトレリスベースの復号器の例を示す。図示のように復号器１００は、ブランチ・メトリック計算モジュール１０２、ＡＣＳモジュール１０４、及び現在レイヤ状態メトリックのためのレジスタ１０６を含む。ブランチ・メトリック計算モジュール１０２はブランチ・メトリックを計算する。ＡＣＳモジュール１０４は、帰還ループによって経路メトリックとしてブランチ・メトリックを再帰的に蓄積し、到来する経路メトリックを比較し、トレリスの各状態に対する最尤な状態遷移を選択するように判定を行い、対応する判定ビットを発生させる。レジスタ１０６は判定ビットを記憶し、復号出力を発生させるのを助ける。状態メトリック計算時に行われる主要な算術演算は、ＡＣＳ演算である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−１２４８４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、加算比較選択（ＡＣＳ）演算を反復的に行う方法を提供する。
【課題を解決するための手段】
【０００７】
一実施形態では、本発明は、加算比較選択（ＡＣＳ）演算を反復的に行う方法である。方法は、反復のために、キャリーセーブ算術を用いて少なくとも２つの状態メトリックを、第１のそれぞれの和成分を有する第１のＡＣＳレイヤモジュールに供給し、第１のＡＣＳレイヤモジュールによって、単一クロックサイクル内で、少なくとも２つのそれぞれのブランチ・メトリックの第１の組に応答して、キャリーセーブ算術における少なくとも２つの計算状態メトリックの第１の組を生成し、少なくとも２つの計算状態メトリックの第１の組を、第２のそれぞれの和及びキャリー成分を有する第２のＡＣＳレイヤモジュールに付与し、第２のＡＣＳレイヤモジュールによって、クロックサイクル内で、少なくとも２つのそれぞれのブランチ・メトリックの第２の組及び少なくとも２つの計算状態メトリックの第１の組に応答して、キャリーセーブ算術における少なくとも２つの計算状態メトリックの第２の組を生成し、少なくとも他の２つの計算状態メトリックの第２の組を、第２のＡＣＳレイヤモジュールのキャリー成分として記憶し、少なくとも２つの計算状態メトリックの第２の組を、次の反復のために第１のＡＣＳレイヤモジュールに供給することを含む。
【０００８】
他の実施形態では、本発明は、加算比較選択（ＡＣＳ）演算を行う装置であって、装置は、単一クロックサイクル内でキャリー成分を有する反復ループを形成するように構成された、直列に結合された少なくとも２つのＡＣＳレイヤを含み、ＡＣＳレイヤは、複数のビット、及び（ｉ）キャリーセーブ算術に従って複数の状態メトリックを発生させるように構成された加算器によって表される少なくとも２つのブランチ・メトリックと、（ｉｉ）キャリー成分に記憶されたキャリーセーブ算術における最大状態メトリックの選択を行うように構成された複数のマルチプレクサとを含む。
【０００９】
他の実施形態では、本発明は、加算比較選択（ＡＣＳ）演算を行うための装置であって、装置は、それぞれが対応する入力及び出力状態ならびに対応する入力及び出力ベクトルを有する、キャリーセーブ算術を用いて状態メトリック計算を行うように構成された、ＡＣＳモジュールの少なくとも２つのレイヤと、記憶された状態メトリックのキャリー成分とを備え、ＡＣＳモジュールの先行レイヤの出力状態は、ＡＣＳモジュールの先行レイヤの入力ベクトルとは異なる入力ベクトルを有するＡＣＳモジュールの後続レイヤに供給され、装置は少なくともキャリーセーブ算術における最大状態メトリックを発生させるために、単一クロックサイクル内で計算するＡＣＳレイヤを形成するように構成される。
【００１０】
他の実施形態では、本発明はトレリス復号器であって、トレリス復号器は、１組のレジスタを含むメモリと、加算比較選択（ＡＣＳ）モジュールであって、少なくとも２つのＡＣＳレイヤモジュールであって、直列に結合され単一クロックサイクル内のキャリー成分を有する帰還ループを形成するように構成され、複数のビット、及びキャリーセーブ算術を用いて複数の状態メトリックを発生させるように構成された加算器によって表される少なくとも２つのブランチ・メトリック、ならびにキャリー成分としてメモリに記憶されたキャリーセーブ算術における最大状態メトリックの選択を行うように構成された複数のマルチプレクサを含む、少なくとも２つのＡＣＳレイヤモジュールを含む、加算比較選択（ＡＣＳ）モジュールとを含む。
【００１１】
本発明の他の態様、特徴、及び利点は、以下の詳細な説明、添付の特許請求の範囲、及び同じ参照番号が同様な又は同一の要素を示す添付の図面から、より十分に明らかとなるであろう。
【図面の簡単な説明】
【００１２】
【図１】例示の従来のトレリスベースの復号器を示す図である。
【図２】本発明による単一の標準ＡＣＳレイヤを示すブロック図である。
【図３】本発明によるＡＣＳ倍速化技法の一実施形態を示すブロック図である。
【図４Ａ】本発明による２個のオペランドのＡＣＳ演算のためのモジュールを示すブロック図である。
【図４Ｂ】本発明による２つの４ビットオペランドのＡＣＳモジュールの標準の実装形態を示すブロック図である。
【図５Ａ】本発明による２ビットのリップル・キャリー加算器を示すブロック図である。
【図５Ｂ】本発明による標準のキャリーセーブ加算器を示すブロック図である。
【図６】本発明による２つの４ビットオペランドのキャリーセーブＡＣＳモジュールのビットレベル図の一実施形態を示すブロック図である。
【図７Ａ】本発明によるターボ復号器の例示的実施形態を示すブロック図である。
【図７Ｂ】本発明によるＡＣＳ倍速技法を適用したトレリスベースの復号器の例示的実施形態を示すブロック図である。
【図８】図３及び図６に示される倍速ＡＣＳ技法のための例示の方法を示すフローチャートである。
【発明を実施するための形態】
【００１３】
本発明の述べられる実施形態は、ターボ及びＬＤＰＣ符号を復号するためのビタビ復号器及びｌｏｇ−ＭＡＰ復号器において有用な高速ＡＣＳ回路に関する。１クロックサイクルにおいて２つ以上のトレリスレイヤの場合の、本発明の例示的実施形態によるＡＣＳ演算の高速計算に対する１組の方式について展開する。以下で述べる実施形態は、２トレリスレイヤの例である。しかしこれらの例は、３トレリスレイヤ及びそれより多いものに容易に適合させることができる。詳しく述べられる方式は、ＡＣＳ回路の特定の構造をもたらすことができるキャリーセーブ算術計算を用いることができる。この特徴は、ＡＣＳ回路の設計の手段を理解することを可能にし得る。さらに、詳しく述べられる方式は２つ以上の同一の組合せＡＣＳレイヤ・サブモジュールを含むことができ、これはこれらの設計の概念の理解を助け、さらに計算速度を増加させる。
【００１４】
本明細書で以降では、本発明の実施形態について図面を参照して述べる。
【００１５】
本明細書では、「ＡＣＳ設計」、「ＡＣＳ方式」、「ＡＣＳ回路」、「ＡＣＳモジュール」、「ＡＣＳレイヤ」、「ＡＣＳ技法」、及び「ＡＣＳ演算」という用語は同義的に用い得ることに留意されたい。ＡＣＳ設計は、ＡＣＳ方式、ＡＣＳモジュール、ＡＣＳ回路、及びＡＣＳ演算に対応する又はそれを含むことができ、ＡＣＳ方式、ＡＣＳモジュール、ＡＣＳレイヤ、ＡＣＳ回路、ＡＣＳ技法、及びＡＣＳ演算は、ＡＣＳ設計を指し得ることを理解されたい。
【００１６】
図２を参照すると、ブロック図は反復のための計算を有する単一の標準ＡＣＳモジュール２００を示す。標準ＡＣＳモジュール２００は、１組の組合せゲートを備えることができるＡＣＳレイヤ２０２と、反復のためのループを形成するように結合されたレジスタ２０４とを含む。ＡＣＳレイヤ２０２は、ＡＣＳレイヤの計算の組合せ部分の入力ベクトルｘ（ｔ）及び出力ベクトルｙ（ｔ）を有する。標準ＡＣＳモジュール２００の現在及び次の状態は、ｑ（ｔ）及びｑ（ｔ＋１）と表される。レジスタ２０４は、ＡＣＳレイヤ２０２から計算された状態ｑ（ｔ＋１）を記憶し、計算された状態ｑ（ｔ＋１）を次の反復計算のための次の入力状態としてＡＣＳレイヤ２０２に帰還する。ＡＣＳモジュール２００は、単一クロックサイクルにおいて単一の標準ＡＣＳレイヤ２０２上の１つの計算を行う。
【００１７】
図３は、本発明の例示的実施形態によるＡＣＳ倍速化技法（speed-doubling technique）をもたらす倍速ＡＣＳモジュール３００の例示的実施形態を示すブロック図である。本明細書ではＡＣＳ倍速化技法は、２重又はそれ以上にＡＣＳモジュールの実質的にすべての組合せゲートのクローンを作成し、レジスタ要件は変わらないままとなるように維持される技法とすることができる。図３に示されるように倍速ＡＣＳモジュール３００は、第１のＡＣＳレイヤ３０２、第２のＡＣＳレイヤ３０４、及びレジスタ３０６を含み、これらは反復のためのループを形成するように結合される。第１のＡＣＳレイヤ３０２は、図２に示されるＡＣＳモジュール２００と同じ入力ベクトルｘ（ｔ）を受け取ることができるが、第１のＡＣＳレイヤ３０２の出力ｙ（ｔ）は第２のＡＣＳレイヤ３０４に付与することができ、第２のＡＣＳレイヤ３０４はまた次の入力ベクトルｘ（ｔ＋１）を受け取ることができる。第１のＡＣＳレイヤ３０２からの計算された状態ｑ（ｔ＋１）は、入力状態として第２のＡＣＳレイヤ３０４に供給することができる。第２のＡＣＳレイヤ３０４は、第２の出力ベクトルｙ（ｔ＋１）を出力し、計算された状態ｑ（ｔ＋２）をレジスタ３０６に保存することができる。ＡＣＳアルゴリズムの現在及び次の状態は、ｑ（ｔ）、ｑ（ｔ＋１）及びｑ（ｔ＋２）と表すことができる。レジスタ３０６は、第２のＡＣＳレイヤ３０４からの計算された状態ｑ（ｔ＋２）を記憶し、計算された状態ｑ（ｔ＋２）を、次の計算のための入力状態ｑ（ｔ）として、第１のＡＣＳレイヤ３０２に供給することができる。したがって倍速ＡＣＳモジュール３００は、単一クロックサイクルにおいて２つのＡＣＳレイヤ上の計算を行うことができるのに対し、標準ＡＣＳモジュール２００は、２つのクロックサイクルに対して２つのＡＣＳレイヤにおいて計算を行い得る。その結果、本発明のＡＣＳ倍速化技法は、ＡＣＳレイヤを通じた計算の速度を増加することができる。
【００１８】
さらに、述べられる実施形態ではキャリーセーブ算術（carry-save arithmetic）はＡＣＳレイヤの組合せ部分において使用することができ、これは最大動作周波数の点から倍加された組合せ部分を有するＡＣＳ設計の深い最適化を可能にする。したがって、倍加されたＡＣＳ設計は、標準のＡＣＳ設計の使用周波数の半分より高い周波数で動作することができる。たとえば、標準ＡＣＳレイヤのシミュレーションでは１０００ＭＨｚで閉じることができ、倍速を有するＡＣＳレイヤのシミュレーションでは６５０ＭＨｚで閉じることができる。キャリーセーブ算術を有する倍速ＡＣＳモジュール３００の第１及び第２のレイヤ３０２、３０４については、後に以下で詳述する。
【００１９】
図４Ａは、２個のオペランドのＡＣＳ演算のためのモジュールを表すブロック図を示す。図示のようにモジュール４００は、ブランチ・メトリックＢＭ１、ＢＭ２のための加算器４０２、４０４と、比較選択回路４０６とを含む。ここで、ＢＭはブランチ・メトリック（branch metric）を表し、ＳＭは状態メトリック（state metric）を表す。モジュール４００は、以下の関係式（１）に従って次の反復のために必要な各ＳＭを計算することができる。
ＳＭ＝ｍａｘ（ＢＭ１＋ＳＭ１，ＢＭ２＋ＳＭ２）  （１）
ただし「ｍａｘ］は最大値演算を表す。
【００２０】
ビタビ又はｌｏｇ−ＭＡＰアルゴリズムの一部の変形形態では、たとえば関係式（１）において最大値演算の代わりに、最小値演算を行うことができる。しかしながら、このような変形形態では概して、ＡＣＳの設計の大幅な変更はない。したがって、当業者なら本明細書で述べられる本発明の実施形態の教示を、最小値演算の場合の実施形態に容易に拡張することができ得る。その場合の合計の深さは、加算器（加算器４０２又は４０４）の深さに、対応する数の引数のための加算器の深さで近似することができる比較選択回路４０６の深さを加えたものとすることができる。したがって、所与のＡＣＳ設計の合計の深さは、その引数の数に顕著に依存する。概してＡＣＳ演算の引数の数は、通常はＡＣＳモジュールのトレリスレイヤにおける状態の数に相当する。概して最新のトレリス復号器では、４個のオペランドのＡＣＳ演算（ＡＣＳ４）、８個のオペランドのＡＣＳ演算（ＡＣＳ８）、及び１６個のオペランドのＡＣＳ演算（ＡＣＳ１６）が通常使用される。したがって４個のオペランドのＡＣＳ演算（ＡＣＳ４）、８個のオペランドのＡＣＳ演算（ＡＣＳ８）、及び１６個のオペランドのＡＣＳ演算（ＡＣＳ１６）を、開示された実施形態に適用することができる。
【００２１】
モジュール４００は、図４Ａに示されるように加算器４０２、４０４と、比較選択回路４０６とを含むだけなので、ＡＣＳ演算は比較的簡単である。しかし、簡単なＡＣＳ演算は、ＡＣＳアルゴリズムをより高速にするように変更することが難しくなり得る。しかしレジスタ転送レベル（register-transfer level：ＲＴＬ）合成は、これを効率的に実現し、ビットレベルの実装を用いて加速を可能にする。
【００２２】
図４Ｂは、２つの４ビットオペランドのＡＣＳモジュールの標準の実装形態の場合のブロック図である。図示のようにＡＣＳモジュール５００は、第１及び第２のブランチ・メトリック５１４、５１６（ビット配列として表される）と、マルチプレクサの配列５０５、５０６、５０７、５０８と、状態メトリックビットを記憶するためのレジスタの配列５０９、５１０、５１１、５１２とを含む。第１のブランチ・メトリック５１４は、ブランチ・メトリック・ビット配列５１５と、加算器の配列５０１、５０２、５０３、５０４とを含む。第１のブランチ・メトリック５１４に対するビット及び加算器は図に示されるが、第２のブランチ・メトリック５１６に対するビット及び加算器は簡単にするために図４Ｂでは省かれている。第２のブランチ・メトリック５１６に対するビット及び加算器は、第１のブランチ・メトリック５１４対するものと同じ構造で構成することができる。マルチプレクサ（「Ｍ」と名付けられている）５０５、５０６、５０７、５０８は、上記の関係式（１）（すなわち、ＳＭ＝ｍａｘ（ＢＭ１＋ＳＭ１，ＢＭ２＋ＳＭ２））を用いて計算される最大和を選択し、最大和をレジスタ５０９、５１０、５１１、５１２のそれぞれのものに転送することができる。
【００２３】
図４Ｂに示されるように、ＡＣＳモジュール５００の場合の計算の比較的クリティカルなパスは太線で示される。ＡＣＳモジュール５００のクリティカルパスは、４つの単一ビット加算器５０１、５０２、５０３、５０４、及び４つの単一ビットマルチプレクサ５０５、５０６、５０７、５０８である。したがってＡＣＳモジュール５００の深さは、４つの加算器と４つのマルチプレクサとを含む。
【００２４】
しかし、図２に示された述べられる実施形態のＡＣＳ方式は、ＡＣＳモジュール５００の標準の２つの４ビットのソリューションの深さのほぼ半分の深さを有することができる。これらの特徴は、ＡＣＳモジュールの組合せロジックの二重化の技法と組み合わせてキャリーセーブ算術を用いることによって達成することができる。キャリーセーブ算術については以下で述べる。比較のために初めにリップル・キャリー加算器について述べる。
【００２５】
図５Ａは、２ビットのリップル・キャリー加算器を示すブロック図である。図５Ａに示されるようにリップル・キャリー加算器６００は、一続きの加算器と、２つの全加算器６０２、６０４（またＦＡｉ及びＦＡｉ＋１という名前で示される）とを含む。リップル・キャリー加算器６００は、複数の全加算器を用いてＮビットの数を加算する論理回路とすることができる。図示のように、ａｉ及びｂｉは数Ａ及びＢのビットであり、
【数１】
2014045480.tif 000003
【数２】
2014045480.tif 000004
である。各全加算器、たとえば第１及び第２の全加算器６０２、６０４は、前の加算器のキャリー出力であるキャリーを入力することができ、各キャリービットは次の全加算器に「リップル」（ｒｉｐｐｌｅ）する。より具体的には第１及び第２の全加算器６０２、６０４は、それぞれの先行する全加算器からキャリー入力ｃｉ及びｃｉ＋１と、入力ビットａｉ、ｂｉ、及びａｉ＋１、ｂｉ＋１とを受け取り、２つの出力ビットと、キャリービットｓｉ、ｃｉ＋１及びＳｉ＋１、ｃｉ＋１とを生じることができる。第１の全加算器６０２は、先行する全加算器からキャリー入力ｃｉを受け取ることができる。前の全加算器がない場合は、入力キャリーｃｉはゼロとすることができる。第１の全加算器６０２は、キャリー出力ｃｉ＋１を第２の全加算器６０４に出力することができる。第１の全加算器６０２からのキャリー出力ｃｉ＋１は、第２の全加算器６０４へのキャリー入力ｃｉ＋１とすることができる。同様に第２の全加算器６０４はその第２のキャリー出力ｃｉ＋２を、第３の全加算器（図示せず）へのキャリー入力ｃｉ＋２として供給することができる。同じ全加算器のｃｉ＋２出力を発生させるためには、入力ｃｉは用いなくてもよいことに留意されたい。したがって１つの全加算器から次の全加算器へのキャリーの伝播が生じる。各全加算器６０２、６０４へのそれぞれの入力ビットａｉ、ｂｉ、又はａｉ＋１、ｂｉ＋１は、４つの部分積からの隣接ビットを表すことができる。たとえば、第１の全加算器６０２は、第１、第２、第３、及び第４の部分積のｎ番目のビットを受け取り、第２の全加算器６０４は、それらの同じ部分積のそれぞれのｎ＋１ビットを受け取る。
【００２６】
第１の全加算器６０２（ＦＡｉ）は、加算の結果の出力ビットｓｉと、キャリービットｃｉ＋１とを計算することができる。第１の全加算器６０２から出力されるキャリービットｃｉ＋１は、続く第２の全加算器６０４によって用いることができる。加算の結果の出力ビットｓｉ及びキャリービットｃｉ＋１のビットは、次の関係式を満たすことができる。
【数３】
2014045480.tif 000005
したがって、リップル・キャリー加算器６００の全体の深さは、ビット数ｎに等しくなり得る。ビット数が増加するのに従ってリップル・キャリー加算器６００の深さは増加し、これは計算速度を低下させ得る。
【００２７】
所与の実装形態に対するリップル・キャリー加算器６００の設計は比較的簡単であり、それにより実装のための短い設計時間が可能になり得るが、リップル・キャリー加算器６００は比較的低速であり、各全加算器たとえば第１及び第２の全加算器６０２、６０４は、前の全加算器からキャリービットが計算されるのを待つ。ゲート遅延は、全加算器回路を観察することによって容易に計算することができる。各全加算器たとえば第１及び第２の加算器６０２、６０４は、３つのロジックのレベルを必要とし得る。３２ビットのリップル・キャリー加算器は３２個の全加算器を含み、それによりクリティカルパス（ワーストケース）遅延は、３遅延時間単位（第１の加算器内の入力からキャリーまで）＋３１×２（後の加算器内のキャリー伝播のため）として計算することができ、等価的に６５ゲート遅延を生じる。
【００２８】
キャリーセーブ加算技法を用いることによって、図５Ａに示される加算方式の深さを１遅延時間単位に減少させることができる。図５Ｂは、標準のキャリーセーブ加算器を表すブロック図を示す。キャリーセーブ加算技法は、加算方式を、標準のリップル・キャリー加算器より高い周波数で動作させることができる。キャリーセーブ技法を用いると、キャリービットはもはやすべての全加算器を通って伝播せず、キャリービットは加算演算の結果の一部となる。キャリー入力を後の全加算器に供給する代わりに、オペランドの１つはキャリー入力及びキャリー出力に入力することができ、第２の出力ワードを形成し、これは次いで、２個のオペランドの加算器での通常の出力に加えられて最終的な和となることができる。キャリーセーブ加算器は、３つ以上のバイナリのｎビットの数の和を計算し、同じ次元の２つの数を入力として出力し、その一方は一連の部分和ビットであり、他方は一連のキャリービットである。
【００２９】
図５Ｂに示されるようにキャリーセーブ加算器７００は、３つのオペランドの急速な加算を可能にし、一連の加算器を含む（一連のうちの２つの加算器７０２、７０４のみが示される）。図示のように数ＡとＢの加算は、関係式（２）を満たすことができ、
【数４】
2014045480.tif 000006
したがって、数ＡとＢのキャリーセーブ加算の結果は、キャリーセーブ・ビットｖｉの配列とすることができる。その結果キャリーセーブ加算器の深さは、単一の全加算器の深さに等しくすることができ、すなわち深さは１に等しくすることができる。
【００３０】
キャリーセーブ加算器は加算方式の深さを１に減少させるので、キャリーセーブ算術を適用した述べられる実施形態は計算速度を増加することができる。図６を参照すると、本発明による２つの４ビットオペランドのキャリーセーブＡＣＳモジュールのビットレベル図のブロック図が示される。図３に示される第１及び第２のＡＣＳレイヤ３０２、３０４を、図６に示されるように単一のＡＣＳモジュール８００として形成することができる。ＡＣＳモジュール８００は、ビット配列として表される第１及び第２のブランチ・メトリック８０１、８０２と、第１のブランチ・メトリック８０１のための加算器の配列８０３、８０４、８４５、８０６と、比較選択マルチプレクサ（compare-select multiplexer：ＣＳＭ）の配列８０７、８０８、８０９、８１０と、データを記憶するための複数のレジスタ８１１、８１２、８１３、８１４、８１５、８１６、８１７、８１８とを含む。第２のブランチ・メトリック８０２は、第２のブランチのビット配列と、また加算器８０３、８０４、８０５、８０６の全くのコピーとすることができる全加算器の配列とを含むことができる。レジスタ８１１、８１２、８１３、８１４、８１５、８１６、８１７、８１８は、ブランチ・メトリックの幅に等しいそれぞれの幅を有する標準のレジスタとすることができ、この幅は変わり得る。たとえば一部の場合には、ブランチ・メトリックを表すためには６ビットで十分であるが、一部の復号器設計は８ビットの表示を使用する。第１のブランチ・メトリック８０１に対するビット及び加算器は図６に示されるが、第２のブランチ・メトリック８０２に対するビット及び加算器は簡単にするために図６では省かれている。第２のブランチ・メトリック８０２に対するビット及び加算器は、ブランチ・メトリック８０１に対するものと同じ構造で構成することができる。
【００３１】
ＣＳＭ８０７、８０８、８０９、８１０は、図４Ｂで述べられたような関係式ＳＭ＝ｍａｘ（ＢＭ１＋ＳＭ１，ＢＭ２＋ＳＭ２）を用いて計算される最大和を選択し、最大和をそれぞれのレジスタ８１１、８１２、８１３、８１４に転送することができる。
【００３２】
図６に示されるように、太線で示されるＡＣＳモジュール８００のクリティカルパスは、２つの単一ビット加算器８０４、８０５、及び２つの単一ビットＣＳＭ８０７、８０８を含み、ここにキャリーセーブ算術を適用することができる。上述のように、標準ＡＣＳモジュール５００の深さは４つの加算器及び４つのマルチプレクサを含み、一方、ＡＣＳモジュール８００は２つの単一ビット加算器及び２つの単一ビットＣＳＭを含む。したがって、ＡＣＳモジュール８００のＡＣＳ方式は、標準のソリューションのほぼ半分の深さをもつことができ、それにより述べられる実施形態のＡＣＳ方式は計算速度を増加することができる。これらの特徴は、キャリーセーブ算術、及びモジュールの組合せロジックの二重化の技法を適用することによって達成することができる。
【００３３】
図７Ａを参照するとブロック図は、本発明の例示的実施形態による本明細書で述べられる倍速ＡＣＳ技法を用いた倍速ＡＣＳ復号器１０の一実施形態を示す。復号器は、ビタビ復号器、ターボ復号器、又はｌｏｇ−ＭＡＰ復号器とすることができる。復号器は通常は、デジタルセルラー方式移動電話などの、通信システムに用いるように構成された送受信器の受信器部分における機能処理ブロックとすることができる。復号器は誤り訂正機能を行うことができる。図７Ａに示されるように復号器１０は、プロセッサ１２と、関連するメモリ１４とを含む。上記で詳述したように、復号器の一部を形成する述べられる実施形態のＡＣＳモジュールの機能要素は、図７Ａに示される復号器の実施形態により実施できることを理解されたい。
【００３４】
プロセッサ１２及びメモリ１４は、倍速復号器を実現するために用いられるデジタル信号プロセッサ（ＤＳＰ）の一部であることが好ましい。しかし本明細書で用いられる「プロセッサ」という用語は概して、１つ又は複数の処理デバイス及び／又は他の処理回路（たとえば特定用途向け集積回路すなわちＡＳＩＣ、ＧＡ、ＦＰＧＡ）を含むことが意図されることを理解されたい。本明細書で用いられる「メモリ」という用語は概して、１つ又は複数の処理デバイス及び／又は回路に関連するメモリ、たとえばＲＡＭ、ＲＯＭ、固定及びリムーバブルメモリ装置などを含むことが意図される。また代替実施形態ではＡＣＳモジュールは、全体的なターボ復号器を実現するために用いられるＤＳＰに関連するコプロセッサによって実現することもできる。このような場合はコプロセッサは、ＤＳＰに関連するメモリの使用を共有することができる。
【００３５】
したがって、本明細書で述べられるように本発明の方法論を実行するための命令又はコードを含むソフトウェア構成要素は、ターボ復号器の関連するメモリに記憶し、利用する準備ができたときに一部又は全体をロードし、ターボ復号器の処理デバイス及び／又は回路の１つ又は複数によって実行することができる。
【００３６】
図７Ｂを参照するとブロック図は、本発明によるＡＣＳ倍速技法を適用した、倍速復号器１０のためのトレリスベースの実施形態の例示的実施形態を示す。図示のように復号器２０は、ブランチ・メトリック計算モジュール２２、第１及び第２のＡＣＳモジュール２４、２６、及びレジスタ２８を含む。ブランチ・メトリック計算モジュール２２は、ブランチ・メトリックを計算する。第１及び第２のＡＣＳモジュール２４、２６は、反復ループ２９内でキャリーセーブ加算技法を用いて、経路メトリックとしてブランチ・メトリックを再帰的に蓄積することができる。次いで第１及び第２のＡＣＳモジュール２４、２６は、到来する経路メトリックを比較し、トレリスの各状態に対する最尤な状態遷移を選択するように判定を行い、対応する判定ビットを含むことができる出力状態メトリックを発生させることができる。レジスタ２８は、判定ビットを記憶し、復号出力を発生させるのを助けることができる。状態メトリック計算時に行われる主な算術演算は、クロックサイクル上のＡＣＳ倍速演算とすることができ、これは従来のＡＣＳ演算と比較して少なくとも２倍に計算速度を増加することができる。
【００３７】
図８は、図３及び図６に示される倍速ＡＣＳ技法を用いたモジュール３０に対する例示の方法を示すフローチャートである。図示のようにステップ３１では、キャリーセーブ算術における２つ以上の状態メトリックを、第１のそれぞれの和成分を有する第１のＡＣＳレイヤモジュール３０２に供給することができる。ステップ３２では、第１のＡＣＳレイヤモジュール３０２でのキャリーセーブ算術における２つ以上の計算状態メトリックを、２つ以上のそれぞれのブランチ・メトリックに応答してクロックサイクルにおいて生成することができる。ステップ３３では２つ以上の計算状態メトリックを、第２のそれぞれの和及びキャリー成分を有する第２のＡＣＳレイヤモジュール３０４に供給することができる。ステップ３４では、第２のＡＣＳレイヤモジュール３０４でのキャリーセーブ算術における他の２つ以上の計算状態メトリックを、同じクロックサイクルにおいて他の２つ以上のそれぞれのブランチ・メトリック及び２つ以上の計算状態メトリックに応答して生成することができる。ステップ３５では、他の２つ以上の計算状態メトリックを、第２のＡＣＳレイヤモジュール３０４のキャリー成分に記憶することができる。ステップ３６では、他の２つ以上の計算状態メトリックを、次の反復計算のために第１のＡＣＳレイヤモジュール３０２に供給することができる。
【００３８】
本明細書において「一実施形態」に対する言及は、その実施形態に関連して説明される特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含み得ることを意味する。本明細書内の様々な場所で現れる「一実施形態では」という語句は、必ずしもすべてが同じ実施形態を指すものではなく、必ずしも他の実施形態と互いに排他的な別の又は代替の実施形態を指すものでもない。「実装形態」という用語にも同じことが当てはまる。
【００３９】
本明細書で用いられる「例示」という語句は、例、事例、又は例証として、役立つことを意味する。本明細書で「例示」として述べられるいずれの態様又は設計も、必ずしも他の態様又は設計より好ましい又は有利であると解釈されるべきではない。むしろ例示という語句の使用は、概念を具体的な形で述べることを意図したものである。
【００４０】
さらに「又は（ｏｒ）」という用語は、排他的な「ｏｒ」ではなく、包含的な「ｏｒ」を意味するものである。したがって別段の規定がない又は文脈から明らかでない限り、「ＸはＡ又はＢを使用する」とは、自然な包含的な変形のいずれをも意味するものである。すなわちＸがＡを使用する、ＸがＢを使用する、あるいはＸはＡ及びＢの両方を使用する場合は、「ＸはＡ又はＢを使用する」は上記のいずれの場合においても満足される。さらに本明細書及び添付の特許請求の範囲で用いられる冠詞「ａ」及び「ａｎ」は、別段の規定がない又は文脈から単数形を指すことが明らかでない限り、概して「１つ又は複数の」を意味するものと解釈されるべきである。
【００４１】
本明細書で述べられる主題は、ユーザ対話型構成要素を有する計算用途のための、１つ又は複数の計算用途の機能／動作を処理するための例示の実装形態との関連において説明され得るが、本主題はこれらの特定の実施形態に限定されない。むしろ本明細書で述べられる技法は、任意の適用なタイプのユーザ対話型構成要素実行管理方法、システム、プラットフォーム、及び／又は装置に応用することができる。
【００４２】
本発明は、単一の集積回路（ＡＳＩＣ又はＦＰＧＡなど）、複数チップモジュール、単一カード、又は複数カード回路パックとしての可能な実装形態を含む、回路ベースのプロセスとして実施することができる。当業者には明らかなように、回路要素の様々な機能は、ソフトウェアプログラム内の処理ブロックとして実施することもできる。このようなソフトウェアは、たとえばデジタル信号プロセッサ、マイクロコントローラ、又は汎用コンピュータにて使用することができる。
【００４３】
本発明は、方法及びそれらの方法を実施するための装置の形で具体化することができる。本発明はまた、磁気記録媒体、光記録媒体、固体メモリ、フロッピディスク、ＣＤ−ＲＯＭ、ハードディスク、又はその他の機械可読記憶媒体などの、有形媒体内に具体化されたプログラム・コードの形で具体化することができ、プログラム・コードがコンピュータなどの機械によってロードされ実行されるときは、その機械が本発明を実施する装置となる。本発明はまた、たとえば記憶媒体内に記憶され、機械によってロードされかつ／又は実行され、又は電線又はケーブル上に、又は光ファイバを通して、又は電磁放射を通じてなど、何らかの伝送媒体又はキャリア上を伝送される、プログラム・コードの形で具体化することができ、プログラム・コードがコンピュータなどの機械にロードされ実行されるときは、その機械が本発明を実施する装置となる。汎用プロセッサにおいて実施される場合は、プログラム・コード・セグメントは、プロセッサと組み合わせて、特定の論理回路と同じように動作する特有のデバイスをもたらす。本発明はまた、媒体を通じて電気的又は光学的に伝送され、磁気記録媒体などに磁界変化として記憶され、本発明の方法及び／又は装置によって発生される、ビットストリーム又は他の信号値のシーケンスの形で具体化することができる。
【００４４】
特許請求の範囲における図の番号及び／又は図の参照番号の使用は、特許請求の範囲の理解を容易にするために、請求された主題の１つ又は複数の可能な実施形態を識別するためのものである。このような使用は、必ずしもそれらの特許請求の範囲を、対応する図に示された実施形態に限定するものと解釈されるべきではない。
【００４５】
本明細書に記載された例示の方法のステップは必ずしも説明された順序で実行される必要はないことが理解されるべきであり、そのような方法のステップの順序は単に例示であることが理解されるべきである。同様に、そのような方法に追加のステップを含めることができ、本発明の様々な実施形態に一致する方法では、一部のステップは省略又は組み合わせることができる。
【００４６】
添付の特許請求の範囲に方法の請求項がある場合に、諸要素は対応する名前と共に特定のシーケンスで記載されるが、請求項の記載がそれらの要素の一部又はすべてを実施するための特定のシーケンスを示唆していない限り、それらの要素は必ずしもその特定のシーケンスにて実施されるように限定されるものではない。
【００４７】
本明細書におけるいかなる請求要素も、要素が「する手段(ｍｅａｎｓ  ｆｏｒ)」又は「するステップ(ｓｔｅｐ  ｆｏｒ)」という語句を用いて明示的に記載されない限り、米国特許法第１１２条第６パラグラフに基づいて解釈されないものとする。
【００４８】
さらに当業者には、添付の特許請求の範囲に表された本発明の範囲から逸脱することなく、本発明の本質を説明するために述べられ図示された諸部分の詳細、材料、及び構成において、様々な変更を行うことができることが理解されよう。
【図１】
2014045480.tif 000007
【図２】
2014045480.tif 000008
【図３】
2014045480.tif 000009
【図４Ａ】
2014045480.tif 000010
【図４Ｂ】
2014045480.tif 000011
【図５Ａ】
2014045480.tif 000012
【図５Ｂ】
2014045480.tif 000013
【図６】
2014045480.tif 000014
【図７Ａ】
2014045480.tif 000015
【図７Ｂ】
2014045480.tif 000016
【図８】
2014045480.tif 000017
【外国語明細書】
2014045480.tif 000018
2014045480.tif 000019
2014045480.tif 000020
2014045480.tif 000021
2014045480.tif 000022
2014045480.tif 000023
2014045480.tif 000024
2014045480.tif 000025
2014045480.tif 000026
2014045480.tif 000027
2014045480.tif 000028
2014045480.tif 000029
2014045480.tif 000030
2014045480.tif 000031
2014045480.tif 000032
2014045480.tif 000033
2014045480.tif 000034
2014045480.tif 000035
2014045480.tif 000036
2014045480.tif 000037
2014045480.tif 000038
2014045480.tif 000039
2014045480.tif 000040
2014045480.tif 000041
2014045480.tif 000042
2014045480.tif 000043