ブース乗算方法及びシステムのための電力効率の良い符号拡張
【課題】ディジタル信号プロセッサが通信（例えば、ＣＤＭＡ）システムにおける伝送処理をブース乗算方法を用いて電力効率の良い符号拡張を提供する。
【解決手段】符号ビットは、ブース乗算処理が符号拡張ステップを実行することを可能にする。これは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張することをさらに含む。この符号拡張ビットは、キャリー−アウト列中に置かれて、ブース乗算処理の積を拡張する。次に、方法及びシステムは、ブース乗算ツリーの事前に決められた列に置かれた符号ビットにキャリー−アウト値を加算することによってブース乗算ツリーから最終積を形成する。この結果は、符号を有する最終積のサム成分を効率的に拡張しそして最終積のキャリー成分をゼロ−拡張することである。
【解決手段】符号ビットは、ブース乗算処理が符号拡張ステップを実行することを可能にする。これは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張することをさらに含む。この符号拡張ビットは、キャリー−アウト列中に置かれて、ブース乗算処理の積を拡張する。次に、方法及びシステムは、ブース乗算ツリーの事前に決められた列に置かれた符号ビットにキャリー−アウト値を加算することによってブース乗算ツリーから最終積を形成する。この結果は、符号を有する最終積のサム成分を効率的に拡張しそして最終積のキャリー成分をゼロ−拡張することである。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル信号プロセッサにおける数学プロセッサの分野に係わり、そしてより詳しくは、数値の高速乗算を実行するための数学プロセッサにおいて使用されるブース乗算に関する。より具体的には、本発明は、ブース乗算方法及びシステムにおける使用のために符号付きの及び符号のないバイナリ値に対する電力効率の良い符号拡張に関する。
【背景技術】
【０００２】
ますます、電子装置及びサポート・ソフトウェア・アプリケーションは、ディジタル信号処理を必要とする。ホーム・シアター、コンピュータ・グラフィックス、医療画像技術及び電気通信技術は、全てディジタル信号処理技術を頼りにしている。ディジタル信号処理は、複雑であるが繰返しアルゴリズムの高速の数学演算を必要とする。多くのアプリケーションは、リアル−タイムの計算を必要とする、すなわち、信号は、時間の連続関数であり、それは数値処理のためにサンプリングされ、そしてディジタルに変換される必要がある。プロセッサは、サンプルが到着するとそのサンプルに個別の演算を実行するアルゴリズムを実行する必要がある。ディジタル信号プロセッサ、すなわちＤＳＰ（ＤＳＰ：digital signal processor）、のアーキテクチャは、そのようなアルゴリズムを取り扱うために最適化される。良い信号処理エンジンの特性は、高速で柔軟な算術計算ユニット、その計算ユニットへのそしてそれからの非拘束データ・フロー、計算ユニットの精度及びダイナミック・レンジの拡張、デュアル・アドレス発生器、効率的なプログラム・シーケンシング、及びプログラミングの容易さ、を含む。
【０００３】
ＤＳＰ技術の１つの将来有望なアプリケーションは、衛星回線又は地上回線を介して複数のユーザ間の音声及びデータ通信をサポートする符号分割多元接続（ＣＤＭＡ：code division multiple access）システムのような通信システムを含む。多元接続通信システムにおけるＣＤＭＡプロセスの使用は、米国特許番号第４，９０１，３０７号、名称“衛星リピータ又は地上リピータを使用するスペクトル拡散多元接続通信システム”、及び米国特許番号第５，１０３，４５９号、名称“ＣＤＭＡセルラ電話ハンドセット・システムにおいて波形を生成するためのシステム及び方法”に開示されており、両者とも特許請求された主題の譲受け人に譲渡されている。
【０００４】
ＣＤＭＡシステムは、１又はそれより多くの電気通信規格、そして現在流れているビデオ規格に準拠するように一般的に設計されている。１つのそのような第１世代規格は、“ＴＩＡ／ＥＩＡ／ＩＳ−９５ デュアル・モード広帯域スペクトル拡散セルラ・システムのための端末−基地局互換性規格”であり、以降ＩＳ−９５規格と呼ばれる。ＩＳ−９５ ＣＤＭＡシステムは、音声データとパケット・データとを送信することが可能である。パケット・データをもっと効率的に送信することが可能なより新しい世代の規格は、“第３世代パートナーシップ・プロジェクト”（３ＧＰＰ）という名前のコンソーシアムにより提案され、そしてドキュメント番号３Ｇ ＴＳ ２５．２１１、３Ｇ ＴＳ ２５．２１２、３Ｇ ＴＳ ２５．２１３、及び３Ｇ ＴＳ ２５．２１４を含むドキュメントのセットに組み込まれており、それは公に容易に利用可能である。３ＧＰＰ規格は、以降Ｗ−ＣＤＭＡ規格として呼ばれる。同様に、ビデオ圧縮規格があり、例えば、ＭＰＥＧ−１，ＭＰＥＧ−２，ＭＰＥＧ−４，Ｈ．２６３，及びＷＭＶ（ウィンドウズ（登録商標）メディア・ビデオ）、同様に、そのような無線ハンドセットがますます利用するであろう多くの他の規格がある。
【０００５】
高速で柔軟な算術計算ユニットを実現するために、高速乗算演算を実行する必要性がある。そのような演算を実行するための１つのプロセスは、ブース乗算として知られている。ブース乗算は、乗算される数値を記録することにより、より小さく、より早い乗算回路を可能にするプロセスである。ブース・プロセスを使用する乗算は、典型的に部分積を生成することにより実行される。部分積は、次に加算されて最終結果を求める。ブース乗算処理を用いると、部分積の個数は、乗数行列中の行の個数に等しい。用語“部分積”は、乗算ツリー中の行を呼ぶ。
【０００６】
元々のブースのアルゴリズムへの数多くの変形があるが、基本的な原理は、ブース・エンコーディング・プロセスを使用してより少ない部分積を生成することである。基数−４ブース・レコーディングのプロセスを使用することによりほぼ半分に部分積の個数を減少させることが可能である。基数−４ブース・レコーディングは、０と１のバイナリ値で元々は表わされる乗数Ｂのビットを、−２，−１，０，１又は２の値を取ることが可能な乗算因子の集合へとマッピングする。この方法は、そうでなければ生じるはずの部分積の個数をほぼ半分にする利点を提供する。これは、回路の動作中の伝搬遅延に関係し、そしてその実施の複雑性と電力消費に関係するので、回路設計において重要である。０，１又は２で、そしてある乗数又はその等価なものだけで、乗算する際にほんのわずかしか複雑性の不利がない。
【０００７】
ブース・エンコーディングのプロセスを使用して部分積が一旦生成されてしまうと、それらは削減技術を利用することにより一緒に加算される。削減のプロセスは、半加算器、全加算器、及びマルチ−オペランド（multi-operand）加算器を使用して並列処理で部分積ビットの複数の行を合計することを含む。この削減は、冗長フォーマットであると言われるビットの２行を結果としてもたらし、キャリー伝搬加算器を使用して分解するときに、その総和は最終積を表す。これらの行のうちの１つは、サム（Sum）Ｓと呼ばれ、そして他の行は、キャリー（Carry）Ｃと呼ばれる。乗算−累積（ＭＡＣ：multiply-accumulate）演算において、［Ｚ＋（ＡｘＢ）］中のＺ項は、一般的に、最終ＣＡＰの前に削減ツリー中に含まれる。この処理は、冗長フォーマットでの乗算積の分解に対して及び引き続く累積に対しての両者でＣＰＡを利用することを省略する。
【０００８】
ある複数の部分積が負であり得るので、２の補集合を作るために必要なハードウェアは、ブース乗算器の１つの態様である。そのようなハードウェアを用いて、乗算積を生成することが可能なブース乗算器を提供する必要性がある。現在、ＤＳＰアプリケーションのために効率的に−（ＡｘＢ）を生成することができる公知の方法又はシステムは、何も存在しない。したがって、ＤＳＰアプリケーションにおいて積の加算の逆、−（ＡｘＢ）、を生成するためにブース乗算処理を使用することができる方法とシステムに対する必要性が存在する。
【０００９】
しかしながら、一旦、そのような積が生成されると、“Ｚ”から乗算の積“ＡｘＢ”まで累積されようとしている値が積ＡｘＢよりも大きなビット幅の場合には、冗長積の“サム”と“キャリー”成分の両者は、適正に符号拡張される必要がある。
【００１０】
時々、ビットの広い範囲にわたり符号拡張を実行することが、必要であり得る。したがって、ＤＳＰ中でブース乗算処理の間に適正な符号拡張のプロセスに対する必要性がある。一般的に、乗算の両方の中間冗長積が、符号拡張されるであろう。
【００１１】
冗長積のサム成分だけが符号拡張される必要がある状況に関して電力効率の良いプロセスに対するさらなる必要性がある。
【００１２】
ブース乗算処理から最終積を生成する際にサム成分とキャリー成分の両方の符号拡張することを避ける必要性がある。
【００１３】
ブース乗算処理の間に中間３２−ビット積の部分積を符号拡張することから生じる電力消費を削減するためのさらなる必要性がある。
【００１４】
ブース乗算の符号拡張のフェーズの間に動作している乗算回路の数を減少させることがさらに必要である。
【発明の概要】
【００１５】
ブース乗算方法及びシステムのために電力効率の良い符号拡張を提供するための技術が開示され、そのプロセスは、パーソナル・コンピュータ、個人ディジタル補助装置、無線ハンドセット、及び類似の電子デバイスのますますエラーに強いソフトウェア・アプリケーションを処理するため、同様にますます増加している関係するディジタル信号プロセッサ速度及びサービス品質のための、ディジタル信号プロセッサの動作とディジタル信号プロセッサ命令の効率的な使用の両方を改善する。
【００１６】
１つの態様によれば、開示された方法及びシステムは、ブース乗算処理のための電力効率の良い符号拡張方法及びシステムを含む。開示された主題は、複数の部分積行を備えるブース乗算ツリーに符号ビットを導入する。その符号ビットは、符号拡張ステップを必要とする該ブース乗算処理の事象において有用である。ここに開示された方法及びシステムは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張する（すなわち、その符号が“１”であるときに符号拡張する）能力を含む。符号ビットの信号値を分解する（resolve）ことは、ブース乗算ツリー中に符号拡張ビットを生成することを必然的に伴う。この符号拡張ビットは、キャリー−アウト列中に置かれることができ、ブース乗算処理の積を拡張する。次に、本発明は、ブース乗算ツリーの少なくとも事前に決められた列への符号ビットにキャリー−アウト値を加えることによってブース乗算ツリーから最終積を形成する。これは、符号を有する最終積のサム成分を拡張しそして最終積のキャリー成分をゼロ−拡張する効果を有する。
【００１７】
開示された主題のこれらの利点及び他の利点、同様にさらなる新規な特徴は、本明細書中に提供される説明から明白であろう。このサマリーの意図するものは、権利を主張する主題の包括的な説明ではなく、むしろ主題の機能のうちのあるものの短い概要を提供することである。ここに提供される別のシステム、方法、特徴、及び利点は、次に続く図面及び詳細な説明を考察することで当業者に明らかになるであろう。全てのそのようなさらなるシステム、方法、特徴、及び利点が、本明細書の範囲内に含まれ、添付された特許請求の範囲内であることが、意図されている。
【図面の簡単な説明】
【００１８】
【図１】本実施形態を実行することが可能である通信システムの単純化したブロック図である。
【図２】本実施形態の教示を実行するためのＤＳＰアーキテクチャを図示する。
【図３】開示された主題の技術的な利点を提供するディジタル信号プロセッサの１つの実施形態のアーキテクチャ・ブロック図を与える。
【図４】開示された主題の様々な実行のためのデータ・パス図を表す。
【図５】開示された主題に適用可能な変形された１６×１６基数−４ブース・乗算ツリーを表す。
【図６】開示された主題のためのブース・レコーダを実装するための論理セルを与える。
【図７】開示された主題を用いる図７の論理セルに対するビット・グループ化の説明を与える。
【図８】−（ＡｘＢ）積のためのブース・レコーディング論理回路を実装するための論理セルを表す。
【図９】開示された主題がブース乗算において引き算をどのようにして取り扱うかの表である。
【図１０】開示された主題のさらなる教示にしたがった１６×１６ブース乗算削減ツリーを示す。
【発明の詳細な説明】
【００１９】
開示された主題の特徴、本質、及び利点は、図面を使用して以下に述べる詳細な説明から、さらに明確になるであろう。図面では、同じ参照符号は一貫して対応するものを特定する。
【００２０】
ここに示されるブース乗算方法及びシステムに対する電力効率の良い符号拡張のための開示された主題は、マルチ・スレッド処理を伴うアプリケーションを含む、非常に広範囲の様々なディジタル信号処理アプリケーションの使用を有する。１つのそのようなアプリケーションは、電気通信において見られ、そして特に、１又はそれより多くのディジタル信号処理回路を利用する無線ハンドセットにおいて見られる。その結果、下記の図１から図３は、電気通信ＤＳＰを説明し、その中では本教示は、有用であり得る。図４は、乗算処理のためのデータ・パスを述べ、その中では拡張ブース乗算演算の本開示が機能することができる。しかしながら、開示された主題が適用されることができるアプリケーションの実質的に無限の集合のうちの１つだけを、ここに説明されるインプリメンテーションが提供することを、忘れずにおくことである。
【００２１】
そのような無線ハンドセットがどのように使用されることができるかを説明する目的のために、図１は、開示される中断処理方法及びシステムの本実施形態を実行することが可能である通信システム１０の単純化したブロック図を与える。送信機ユニット１２において、データは、データ・ソース１４から送信（ＴＸ）データ・プロセッサ１６に、一般的にブロックで送られ、その送信データ・プロセッサ１６はデータをフォーマット化し、コード化し、そして処理して、１又はそれより多くのアナログ信号を生成する。アナログ信号は、次に送信機（ＴＭＴＲ）１８に与えられ、それはベースバンド信号を変調し、フィルタし、増幅し、そしてアップコンバートして、変調された信号を生成する。変調された信号は、次に１又はそれより多くの受信機ユニットにアンテナ２０を介して送信される。
【００２２】
受信機ユニット２２において、送信された信号は、アンテナ２４により受信され、そして受信機（ＲＣＶＲ）２６に与えられる。受信機２６内で、受信された信号は、増幅され、フィルタされ、ダウンコンバートされ、復調され、そしてディジタル化されて、インフェーズ（Ｉ）と（Ｑ）サンプルを生成する。サンプルは、次に受信（ＲＸ）データ・プロセッサ２８によりデコードされそして処理されて、送信されたデータを再生する。受信機ユニット２２におけるエンコーディングと処理は、送信機ユニット１２において実行されたコーディングと処理に相補的な方法で実行される。再生されたデータは、次にデータ・シンク３０に与えられる。
【００２３】
上に記述された信号処理は、音声、ビデオ、パケット・データ、メッセージ送信、及び１方向の他のタイプの通信をサポートする。双方向通信システムは、２方向のデータ送信をサポートする。しかしながら、他の方向に対する信号処理は、単純化のために図１には示されない。通信システム１０は、符号分割多元接続（ＣＤＭＡ：code division multiple access）システム、時分割多元接続（ＴＤＭＡ：time division multiple access）通信システム（例えば、ＧＳＭ（登録商標）システム）、周波数分割多元接続（ＦＤＭＡ：frequency division multiple access）通信システム、又は地上回線を経由して複数のユーザ間の音声とデータ通信をサポートする他の多元接続通信システムであり得る。ある特定の実施形態では、通信システム１０は、Ｗ−ＣＤＭＡ規格に準拠するＣＤＭＡシステムである。
【００２４】
図２は、図１の送信データ・プロセッサ１６と受信データ・プロセッサ２８として機能することができるＤＳＰ４０アーキテクチャを図示する。もう一度、ＤＳＰ４０がここに示された教示及び概念を効果的に使用することができる非常に多くの可能性のあるディジタル信号プロセッサ実施形態のうちの１つの実施形態を表すだけであることを、強調する。ＤＳＰ４０において、それゆえ、スレッドＴ０：Ｔ５（参照番号４２から５２）は、別のスレッドからの命令の集合を含む。回路５４は、命令アクセス・メカニズムを表し、そしてスレッドＴ０：Ｔ５に対する命令を取り出す（fetch）ために使用される。回路５４のための命令は、命令キュー５６へとキューされる。命令キュー５６中の命令は、プロセッサ・パイプライン６６（下記を参照）へと発せられるように準備されている。命令キュー５６から、１つのスレッド、例えば、スレッドＴ０、は、発行論理回路５８によって選択されることができる。選択されたスレッドのレジスタ・ファイル６０が、読み出され、そして読み出されたデータは、スロット０からスロット３に対する実行データ・パス６２へ送られる。スロット０からスロット３は、この例では、本実施形態において用いられるパケット・グループ化組み合わせを規定する。
【００２５】
実行データ・パス６２からの出力は、ＤＳＰ４０の動作からの結果を戻すために、レジスタ・ファイル書込み回路６４に行き、しかもその回路は個々のスレッドＴ０：Ｔ５を適応させるように構成される。そのように、回路５４からのデータ・パス及び様々なスレッドに応じて分けられるレジスタ・ファイル書込み回路６４の前のデータ・パスは、処理パイプライン６６を形成する。
【００２６】
本実施形態は、６個までのスレッド、Ｔ０：Ｔ５、を有する１つのマイクロプロセッサを使用するヘテロジーニアス素子プロセッサ（ＨＥＰ：heterogeneous element processor）の混成タイプを使用することができる。プロセッサ・パイプライン６６は、６つのステージを有し、回路５４からレジスタ６０と６４へのデータ項目を取り出すために必要なプロセッサ・サイクルの最小数を組み合わせる。ＤＳＰ４０は、プロセッサ・パイプライン６６内の異なるスレッドＴ０：Ｔ５の命令を同時に実行する。すなわち、ＤＳＰ４０は、６個の独立したプログラム・カウンタ、プロセッサ・パイプライン６６内のスレッドＴ０：Ｔ５の命令を識別する内部タッギング・メカニズム、及びスレッド・スイッチをトリガするメカニズム、を与える。スレッド・スイッチ・オーバーヘッドは、ゼロからほんの数サイクルまで変化する。
【００２７】
ＤＳＰ４０は、それゆえ、広範囲の様々な信号、画像、及びビデオ処理アプリケーションにわたり高性能かつ低電力の目的で設計される汎用ディジタル信号プロセッサを提供する。図３は、ＤＳＰ４０アーキテクチャの簡単な全体像を与え、開示された主題の１つの表現のために関係する命令セット・アーキテクチャのある複数の態様を含む。ＤＳＰ４０アーキテクチャのインプリメンテーションは、インターリーブされたマルチスレッディング（ＩＭＴ：interleaved multithreading）をサポートする。この実行モデルでは、ハードウェアは、パイプライン中の異なるスレッドからの命令をインターリーブすることにより複数のハードウェア・スレッドＴ０：Ｔ５の同時の実行をサポートする。この特徴は、ＤＳＰ４０が高いコア及びメモリ利用を維持したままで、アグレッシブなクロック周波数を含むことを可能にする。ＩＭＴは、費用のかかる補償機構、例えば、適切でない実行、大規模な転送ネットワーク、及びその他、を必要とせずに高スループットを提供する。
【００２８】
図３は、より一層具体的に、開示された主題の教示を利用することができる１つのスレッドに対するプログラミング・モデルの１つの実施形態のアーキテクチャ・ブロック図を与える。ブロック図７０は、ＡＸＩバス７４からの命令を受け取る非公開命令キャッシュ７２を図示し、その命令はスレッドＴ０：Ｔ５のシーケンサ７６、ユーザ制御レジスタ７８、及び管理制御レジスタ８０への混合の１６−ビットと３２−ビット命令を含む。シーケンサ７６は、Ｓ−パイプ・ユニット８２、Ｍ−パイプ・ユニット８４、Ｌｄ−パイプ８６、及びＬｄ／Ｓｔ−パイプ・ユニット８８への混成タイプの２−方向スーパースカラ命令と４−方向ＶＬＩＷ命令を与える。ＡＸＩバス７４は、スレッドＴ０：Ｔ５へのＬＤ／ＳＴ命令を共有データ・キャッシュ９０と同様に通信する。外部ＤＭＡマスタ９６を用いて、共有データＴＣＭ９８は、ＬＤ／ＳＴ命令を通信し、そのＬＤ／ＳＴ命令は、スレッドＴ０：Ｔ５へとさらに流れる。ＡＨＢ周辺バス１００から、ＭＳＭ特定コントローラ１０２は、Ｔ０：Ｔ５を有する中断ピンを通信し、それは中断コントローラ命令、デバッグ命令、及びタイミング命令を含む。グローバル制御レジスタ１０４は、スレッドＴ０：Ｔ５と制御レジスタ命令を通信する。
【００２９】
図３のＭ−パイプ８４において述べたように単一スレッド処理のアーキテクチャ内では、高速数学処理が生じる。電力効率は、ＤＳＰ４０の動作に決定的であり、そしてＭ−パイプ８４は、自身の動作においてこの考慮を含む必要がある。そのような乗算処理において生じるものは、乗算の結果が冗長形式で利用可能になることであり、そしてこれらの冗長な結果は、乗算−累積演算において使用される。そのような冗長な結果で、符号拡張が、両方の冗長積について生じる必要があり得る。開示された主題は、各乗算の２つの冗長積のうちの１つにだけ適用される符号拡張を提供する。これは、中間冗長積が大きなビット範囲にわたり符号拡張される必要があるケースでは顕著な省電力をもたらす。
【００３０】
同様な電力効率の考えは、開示された主題が適用されることができるいずれのアプリケーションにおいてもおそらく存在する。したがって、ブース乗算処理が行われる速度は、個々に開示された題材の特徴的な新規な態様を提供する。
【００３１】
開示された主題は、乗算のためのブース・エンコーディング・プロセスを提供し、それは部分積の最後の行が‘１要素’拡張される部分積生成の方法を利用する。乗数の削減ツリーの最下位列の削減を適切に操作することによって、‘サム’冗長積だけが符号拡張される必要があるが、‘キャリー’冗長積はゼロ拡張されることが可能であることを、開示されるプロセスは確実にする。‘サム’だけが符号拡張されるので、開示されるプロセス及び関係する構造は、乗算の冗長積を符号拡張することに含まれる電力コストを削減する。開示された主題がこれらの省電力と関連する効率をどのようにして実現するかの理解を得るために、特定の実施形態のさらなる実例による説明がここに与えられる。
【００３２】
図４は、それゆえ、開示された主題の様々な実施のためのデータ・パス図１８０を表し、そして本ブース乗算処理がそこで行われることができるデータ・フローを設定する。特に、乗算ブロック１１８は、ＲｓとＲｔ入力を受け取る。乗算ブロック１１８の内部にあるものは、乗算ユニットＭ０：Ｍ３である。特に、Ｍ０乗算器ユニット１８２、Ｍ１乗算器ユニット１８４、Ｍ２乗算器ユニット１８６、及びＭ３乗算器ユニット１８８は、ＲｓとＲｔ入力を別々に受け取って、シフト／符号拡張ユニット１４８への、それぞれ、Ｓ０Ｃ０（すなわち、サム０とキャリー０）、Ｓ１Ｃ１、Ｓ２Ｃ２、及びＳ３Ｃ３出力を生成する。シフト／符号拡張ユニット１４８は、これらの中間冗長積の論理シフトと符号拡張を実行する責任がある。
【００３３】
乗算器ブロック１１８は、Ｍ−パイプ８４に対する命令に関連する乗算を実行する。これらの命令は、１６×１６乗算処理を基底として使用する複合命令として取り扱われることができる。乗算器ブロックは、４個の１６×１６乗算器ユニットＭ０：Ｍ３から構成される。各乗算器ユニットＭ０：Ｍ３は、複数のモードで機能することが可能であり、多種多様なＭ−タイプ命令をサポートする。符号付きモードと符号なしモードとがサポートされる。乗算器は、減算がその積に実行される必要があるケースでは、それらの積の２の補数を同様に生成することが可能である。
【００３４】
開示された主題を用いて、Ｍ０：Ｍ３乗算器１８２から１８８は、基数−４ブース・エンコーディングを使用する。符号なしモードでは、それらは、符号ビットとして機能する追加の１７番目のビットを有する１７×１７乗算に似ている。倍精度乗算（すなわち、３２×３２乗算）を除いて、全ての他の乗算命令は、“符号付き×符号付き”又は“符号なし×符号なし”である。倍精度３２×３２乗算及び複数の１６×１６乗数を使用する３２×１６乗算は、同様に“符号付き×符号なし”乗算と“符号なし×符号付き”乗算とを必要とする。これらのモードの全ては、Ｍ０：Ｍ３乗算器１８２から１８８の被乗数と乗数オペランド（operand）の符号ビットを制御することによりサポートされる。
【００３５】
シフト／符号拡張ユニット１４８からの出力は、マルチ−オペランド加算器１５０に行き、そしてＲ０：Ｒ３入力へと分解される。マルチ−オペランド加算器１５０は、これらのＲ０：Ｒ３入力を受け取り、そして圧縮と累積ステージのセットの後で、最終的にＲｄｄ出力１７０を与える。
【００３６】
データ・パス１８０は、４つのフェーズへと分割可能であるように理解されることができる。まず第１に、データ配送フェーズでは、ＲｓとＲｔソース・レジスタからのデータは、乗算ブロック１１８に供給される。乗算ブロック１１８の中では、ソース・オペランドからの１６−ビット・ハーフ・ワードは、命令に基づいて４個のＭ０：Ｍ３乗算器１８２から１８８に配送される。次に、部分積生成及び削減（reduction）ベクトル加算又は減算が行われる、そこでは、Ｍ０：Ｍ３乗算器１８２から１８８は、基数−４ブース・エンコーディングを使用して部分積を生成し、そして出力の冗長対へ削減を使用してそれらを削減する。
【００３７】
マルチ−オペランド削減フェーズの間、乗算ブロック１１８からの冗長出力は、マルチ−オペランド加算器１５０へ入力され、その加算器はこれらの入力とオプションの累算値／丸めた値を２組の冗長出力へと削減する。最後に、加算／サチュレーション（saturation）フェーズでは、冗長出力は、キャリー増殖（propagate）加算を使用して解かれ、そしてサチュレーションは、適用可能であるときに実行される。
【００３８】
開示された主題は、したがって、そのような値の変形されたブース乗算を規定する。そのような複素値を用いて、入力は、下位ハーフワードの実数１６−ビット値と上位ハーフワードの虚数１６−ビット値とを有する。乗算結果は、オプションとして０−１ビットだけスケーリングされる。丸め定数がそれぞれの実数和と虚数和に加算される。実数部と虚数部は、３２ビットに個別にサチュレートされる。３２−ビット結果のそれぞれの上位１６−ビットは、３２−ビット行先レジスタにパック（pack）される。
【００３９】
この例では、Ｓ０：Ｓ３とＣ０：Ｃ３は、３３−ビット幅である。１６×１６乗算の出力が３２−ビットで表わされることが可能であるとしても、ある複数の命令は、符号なしモードで実行し、そして追加ビットが符号拡張を容易にするために符号ビットとしてこのケースでは使用される。Ｓ０：Ｓ３とＣ０：Ｃ３は、シフト／符号拡張ユニット１４８を経由して渡される。Ｓ０：Ｓ１とＣ０：Ｃ１は、パッキングの前に、最終結果の低次の３２−ビットを与える。これは、結果の実数部を形成する。これらの４つの数は、命令で指定される場合には、１−ビットの左シフトによりオプションとしてスケーリングされる。
【００４０】
これらの数のシフトされたバージョンは、Ｒ０：Ｒ３と名付けられる。Ｒ０：Ｒ３は、マルチ−オペランド加算器１５０を経由して渡される。マルチ−オペランド加算器１５０からの出力は、サチュレーション／加算ユニット１７０に流れる。
【００４１】
ここで、開示された主題は、様々なブース乗算処理において実行されることができる。しかしながら、開示された主題の具体的な使用を理解することは、そのようなアプリケーションが起きることがある特定のブース乗算処理の表現を通して最も良く達成されることができる。したがって、図５は、開示された主題に適用可能な変形された１６×１６基数−４ブース・乗算ツリーを提示することにより、開示された主題のブース乗算処理を理解することを容易にする。図５のドット図２００は、開示された主題の１６×１６乗数についての基数−４ブース・エンコーディングを概念的に図示し、それは９個の部分積２０２，２０４，２０６，２０８，２１０，２１２，２１４，２１６，と２１８とを結果としてもたらす。９個の部分積は、２個の３３−ビット冗長出力に削減され、それらは２レベルの３：２削減と引き続く１レベルの４：２圧縮からなる削減ツリーを使用するＳ０：Ｓ３及びＣ０：Ｃ３である。３２−ビットの精度は１６×１６乗算のために十分であるが、３３番目のビットは、符号なし乗算のケースにおける符号ビットとして機能するように同様に保存される。３３番目の列からの追加のキャリー−アウト・ビットは、同様に、符号拡張を支援するための乗算器からの出力である。
【００４２】
さらに図５を参照して、各部分積行２２０から２３６は、横方向に示される被乗数ビット２３８の倍数である。列番号は、図５の上部に示されている。乗数ビット２４０は、縦方向に示され、そしてこれらのビットは、部分積行２２０から２３６を形成するための乗算係数を生成するために記録される。図５に示される信号ｎ０からｎ７は、スティッキー（sticky）“１”を示し、それは負の加重を受ける部分積行２２０から２３６に付加される。これらは、積の最終反転を必要としない乗算を扱うために十分である。乗数における−（ＡｘＢ）陰関数表示のケースを取り扱うために、追加の信号ｎ８が与えられる。
【００４３】
乗算演算の積が乗数ツリー内で非明示的に減算されるときに、信号ｓ０からｓ７は、符号拡張を取り扱う。ＡとＢとが、それぞれ被乗数と乗数であると仮定される場合に、基数−４ブース・エンコーディングは、乗数オペランドＢの３個のビットのグループをエンコーディングすることにより、そして集合｛−２Ａ，−Ａ，０，Ａ，２Ａ｝から部分積を選択するためにこのエンコーディングを使用することにより、進められる。ここで、最終積（ＡｘＢ）が減算される必要がある場合には、それはＡｘ−（Ｂ）を加算することに等しく、それは順に、積（（−Ａ）ｘＢ）を加算することに等しい。乗数は、ここでＢから（−Ｂ）に変更される。
【００４４】
開示された主題がそこにおいてアプリケーションを見出すことができるブース乗算処理の一部として、図６は、開示された主題を実行するためのブース・レコーダ回路２５０を提供する。ブース・レコーダ・セル２５０は、ＸＯＲ２５６でのＬＳＢ入力２５４からインバータＸＯＲ２６０でのＭＳＢ入力２５８までの範囲の乗数グループ入力２５２を含む。ＭＳＢ入力２５８は、ブース・レコーダ回路２５０からの“ｎｅｇ”出力を同様に与える。ＸＯＲ２５６からの出力は、ブース・レコーダ２５０からのＡｘ１信号、Ａを表し、インバータＸＯＲ２６４への入力を同様に与える。インバータＸＯＲ２６０からの出力は、インバータＸＯＲ２６４への入力を同様に与えて、ブース・レコーダ回路２５０からのＡｘ２信号、２Ａを生成する。ＸＯＲ２６４は、ブース・レコーダ回路２５０からの否定 “ｎｅｇ”を指示するための出力を与える。そのように、ブース・レコーダ回路２５０は、乗数Ｂの３−ビットを検査し、そして信号“Ａ”，“２Ａ”と“ｎｅｇ”へとそれらを記録する。減算が実行される必要があるとき、“ｎｅｇ”信号は、部分積を生成するために反転され、それは積、ＡｘＢ、の２の補数を生成する。
【００４５】
図７は、開示された主題を用いる図６の論理セルに対するビット・グループ化の説明を与える。特に、基数−４ブース・レコーディングは、１６−ビット乗数Ｂから９個の乗算係数を生成し、それはＡの倍数として使用され、９個の部分積を生成する。０から８までの範囲の“ｎ”に対して、図７の表は、ビット・グループＢ［２ｎ＋１：２ｎ−１］に対するブース乗算係数を決定する。本実施形態のレコーディング方式に関して、Ｂ［−１］は、ゼロであると仮定される。Ｂ［１６］とＢ［１７］は、Ｂが符号なしの数である場合にゼロであり、そしてＢが符号付きの数である場合にＢの符号拡張である、すなわち、Ｂ［１７］＝Ｂ［１６］＝Ｂ［１５］。乗算係数は、３つの信号へと記録される：それはＸＯＲ２５６からのＡ、インバータＸＯＲ２６４からの２Ａ及びＭＢＳ入力２６２からの“ｎｅｇ”である。そのように、Ａに対する乗算係数が−２であるとき、信号２Ａとｎｅｇは、ハイである。同様に＋１に対して、Ａだけがハイであり、そして＋／−０に対して全ての３つの信号は、ローである。しかも、積ＡｘＢを生成することに関して、最上位ビット・グループに対する乗算係数、Ｂ［１７：１５］は、常に正であることに、注意する。ここで、Ｂ［１７：１５］に対する可能なビット・グループは、Ｂが符号なしの場合には［０００］又は［００１］であり、そしてＢが符号付きの場合には［０００］又は［１１１］であるだけである。図７から、これらの全てのグループは、正の乗算係数に導く。本明細書中に記述されるブース乗算マルチプレクサは、それゆえ、部分積を生成するためにセット｛０，Ａ，２Ａ｝から選択することができる。
【００４６】
図８は、−（ＡｘＢ）積のためのブース・レコーディング論理回路を実装するためのブース・レコーダ回路２７０を提供する。ブース・レコーダ・セルは、ＸＯＲ２７６でのＬＳＢ入力２７４からインバータＸＯＲ２８０でのＭＳＢ入力２７８までの範囲にわたる乗数グループ入力２７２を含む。“減算”入力２８２とＭＳＢ入力２７８は、ＸＯＲ２８４へ流れる。ＸＯＲ２７６からの出力は、ブース・レコーダ２７０からの被乗数Ａ信号を表し、それに加えてインバータＸＯＲ２８６への入力を与える。インバータＸＯＲ２８０からの出力は、ブース・レコーダ回路２７０からの２Ａ信号を生成するためにインバータＸＯＲ２８６への入力を同様に与える。ＸＯＲ２８４は、ブース・レコーダ回路２７０からの“ｎｅｇ”出力を与える。
【００４７】
本主題がそれに対する使用を見出すことができるブース乗算処理の開示されたアプリケーションでは、図８は、それゆえ、被乗数Ａと乗数Ｂの積の負の値が、ＡとＢの負の値との積を計算することによって得られるという特性を利用する。これは、それゆえ、最初にＡｘＢの積を計算し、そして次に−（ＡｘＢ）を得るために積の２の補数を計算する公知の２ステップ・プロセスを回避する。ブース・レコーダ回路２７０は、乗算のステージと並行して否定を実行する。
【００４８】
積の２の補集合を作ることは、−（ＡｘＢ）がＡｘ（−Ｂ）に等価であるという事実を利用する。この例では、オペランド（−Ｂ）は、乗数として扱われる。乗数として（−Ｂ）を使用して生成されたブース乗算係数は、乗数オペランドとしてＢを使用して生成された乗算係数に対応する付加的な逆である。積ＡｘＢを計算するために使用するブース乗算ハードウェア構成は、ブース乗算係数のそれぞれの符号を反転することによりＡｘ（−Ｂ）を計算するために再使用されることが可能である。この符号は、ブース・レコーダ回路２７０の“ｎｅｇ”信号によって決定され、それは積を否定する際に“−ｎｅｇ”信号を生成するためにレコーディング・ハードウェアに対する変更である。
【００４９】
ブース・レコーダ回路２７０において、ＸＯＲゲート２８４は、非クリティカル・パス上にあり、そしてクリティカル・パスに寄与しない。その代りに、クリティカル・パスは、信号Ａと２Ａを生成するための乗数ビットを含む。部分積のための乗算係数の符号を反転させるこのプロセスは、最終積行の符号が負であり得るケースを導入する。これゆえ、信号“ｎ８”は、上記の図５に見られるように、乗算ツリーに追加されることができる。行を追加することは、追加の行を適応させるために削減ステージを変更することにより削減されることができる。これは、しかしながら、追加の遅延と関係するハードウェアを意味することがある。
【００５０】
ここに示されたプロセスは、削減ステージにおいて追加の行を含まないが、その代わりに乗算ツリーへの論理的な変更を行うことにより部分積の既存の９行中へとｎ８信号を吸収することに焦点を合わせている。乗算ツリーに追加される遅延は、最小である。
【００５１】
形式ＰＰｒｏｗ＿ｃｏｌｕｍｎの各“ドット”を参照する表記は、開示された主題のこの態様を理解することを求める際に役立つ。図９を参照して、乗算ツリー中の各バイナリ・ビット（ドット）は、その固有の加重と行列中の位置とを有する。同じ列の全てのビットは、同じ加重を有し、そしてその加重が維持される限り任意の順番で削減されることができる。行は、０で始まり上から下に番号を付けられ、そして列は、０で始まり右から左に番号を付けられる。この表記を使用して、ｎ８は、ＰＰ１０＿１６に等価である。ＰＰ０＿１６，ＰＰ０＿１７，ＰＰ０＿１８とＰＰ０＿１９は、基数−４ブース・エンコーディングにより公知のスケーリングと符号拡張プロセスとを使用して生成される。そのようなアプローチを用いて、ｎ８を乗算ツリーの中へと吸収することが可能である。そのように、符号付き乗算モードと符号なし乗算モードの両方においてＰＰ０＿１６，ＰＰ０＿１７，ＰＰ０＿１８とＰＰ０＿１９に対する全ての可能性のあるビット値を解析することによって、ｎ８がその中に挿入されることができる位置は、全ての可能性のあるブース乗算係数に対して決定することが可能である。
【００５２】
図９は、部分積行０の４つの最上位ビットに対する値の範囲、そして信号ｎ８をこの４−ビット・フィールドに追加する効果を列挙する。ＭＵＸ構成は、ｎ８がハイであるときに、４−ビット・フィールドの変更された値を選択することを認める。言い換えると、開示されたプロセスは、信号ｎ８が列１６のところに追加される、すなわち、ＰＰ０＿１６である場合に、部分積行０の４つの最上位ビットの値を事前に計算し、そしてこの変更された４−ビット・フィールドを削減ステージにおいて使用する。ＭＵＸ構成は、一旦ＰＰ０＿１６（表中に“ａ”として示される）が標準ブース多重送信回路系を使用して計算されるように最適化される。ｎ８に基づく変更された４−ビット・フィールドは、この後で最小遅延で解かれる。乗算処理の残りは、積ＡｘＢを生成するための通常の乗算フローと同じである。
【００５３】
図１０は、開示された主題のさらなる態様に対して利用可能な変更された１６×１６基数−４ブース乗算ツリーを示す。図１０から、本開示の重要な符号拡張と定数丸め機能とを理解することが可能である。１６×１６乗数の削減ステージへの変更は、９個の部分積行を通るクリティカル・パスを最小にし、そしてその積が冗長サム−キャリー・フォーマットで利用可能であるときに、符号拡張を効率的に与える。図１０は、１６×１６基数−４ブース乗数のための変更された削減ツリー３０４を示す。変更された削減ツリー３０４は、符号付きオペランドと符号なしオペランドを適応させ、そして積を否定する可能性を有する。
【００５４】
削減の第１ステージは、全加算器の３行を使用して９行を６行に削減する。削減の第２ステージは、全加算器の２行を使用して６行を４行に削減する。削減の第３ステージと最終ステージは、４：２マルチ−オペランド加算器のある行を利用して、４行を最終の冗長サムとキャリー行へと削減する。サムとキャリーの３２ビットが１６×１６積を表示するために十分であるけれども、追加ビットは、符号拡張が符号なし乗算に対して正しく取り扱われることを確実にする。
【００５５】
図１０は、積を形成する下位の３２ビットよりもすぐ上位である列３０６をさらに示す。本明細書は、最終部分積行３０８のための符号ビットｓ８を導入するために列＃３２から上方のブース乗算ツリーを変更する。この符号ビットｓ８は、積が符号拡張を必要としない場合には、必要とされない。ここで、部分積行８の正しい符号を保存するために、プロセスは、１ビットだけ部分積行３０８を拡張することを含む。＃３２よりも大きい列は、削減の最終ステージまで影響されない。そのような点において、信号〜ｓ８は、列＃３１からのキャリー−アウトにより分解し、そして“ｃ―”として示されるキャリー−アウト３１０を生成する。
【００５６】
最終積は、上方への行＃３３から１要素拡張にキャリー−アウト“ｃ―”３１０を加算することにより形成される。その効果は、符号としてｃ―を有する最終積のサム成分を符号拡張するためであり、一方で最終積のキャリー成分はゼロ−拡張である。これらのステップは、サム成分とキャリー成分の両方を符号拡張する必要性を排除する。例えば、１６×１６乗算が３２−ビット積への６４−ビット値の累算を必要とするＭＡＣ演算の一部である場合には、６４−ビット値に３２−ビット積を加算する前に、３２−ビット積を６４−ビットに符号拡張することが、必要とされるはずである。中間３２−ビット積が冗長形式で残され、そしてここに提示された符号拡張プロセスが適用される場合に、３１−ビットにわたりキャリー成分を符号拡張するために使用する複数のＭＵＸを排除することの可能性のために、相当量の電力節約が生じ得る。
【００５７】
再び図１０を参照して、本明細書は、乗数、Ｂに丸め定数を加算する能力をさらに提供する。ＤＳＰ演算において１６×１６乗算に対する一般的丸め定数は、０×８０００である。１６×１６乗算の積を丸めることは、一般的な演算であり、それは２ステップ演算として典型的に実行される、ここで、乗数が積を生成するために最初に使用され、そして次に丸め定数がその積に加算される。
【００５８】
上に記述された表記を使用すると、図１０ではＰＰ８＿１５が０であることに注意する。乗算行列中のこのビット位置に“１”を挿入することにより、最初に積を生成しそして次にその積に値０×８０００を加算することにより求められるはずの結果と同じ結果を生成することが可能である。このプロセスは、しかもクリティカル・パスにいかなる待ち時間も追加しない。
【００５９】
乗算ブロック１１８中のハードウェアが乗算の積に１つの累算−オペランドを加算することが可能であるだけの能力に制限される場合には、乗算の積が丸められる必要があるときに累算−オペランドを有する丸め定数をＭＵＸすることが、一般的である。これは、乗算の積についての丸め演算と累算演算との両方を単一ステップで実行することを困難にさせる。しかし、ここに開示されたプロセスを使用することは、そのような制限を排除する。
【００６０】
要約すると、開示された主題は、設計のためのプロセス及びディジタル信号プロセッサの使用を提供し、通信（例えば、ＣＤＭＡ）システムにおける送信を処理することを含む。開示された方法及びシステムは、ブース乗算処理のための電力効率の良い符号拡張方法及びシステムを含む。開示された主題は、複数の部分積行を備えるブース乗算ツリーに符号ビットを導入する。符号ビットは、符号拡張ステップを必要とするブース乗算処理の事象（event）において有用である。ここに開示された方法及びシステムは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張する。符号ビットの信号値を分解することは、ブース乗算ツリーにおいて符号拡張ビットを生成することを必然的に伴う。符号拡張ビットは、キャリー−アウト列中に配置されることができて、ブース乗算処理の積を拡張する。次に本発明は、ブース乗算ツリーの少なくとも事前に決められた列に対する符号ビットにキャリー・アウト値を加算することによってブース乗算ツリーから最終積を形成する。これは、符号ビットを有する最終積のサム成分を拡張する効果を、そして最終積のキャリー成分をゼロ拡張する効果を有する。
【００６１】
本発明は、変形されたブース乗数の技術的な利点をさらに提供し、それは形式［Ｚ＋−（ＡｘＢ）＋丸め定数］のＭＡＣ演算において使用されることが可能である。この乗数は、（ａ）ブース乗算係数を否定してそして余分なスティッキー・ビットを削減ツリー中へと吸収することにより、（ｂ）丸め定数を削減ツリーへと詰め込む場所を見つけることにより、そして（ｃ）冗長サムの符号拡張を必要とするだけの符号拡張プロセスを使用することにより、遅延、電力、及びハードウェアを最小にする。
【００６２】
その上、本明細書中に記述された処理の特徴及び機能は、様々な方式で実施されることができる。例えば、ＤＳＰ４０が上記の演算を実行することがあるだけでなく、本実施形態は、用途特定集積回路（ＡＳＩＣ：application specific integrated circuit）、マイクロコントローラ、マイクロプロセッサ、又は本明細書中に記述された機能を実行するために設計された他の電子回路、で実施されることができる。好ましい実施形態のこれまでの説明は、それゆえ、権利を主張する主題を当業者が制作すること又は使用することを可能にするために提供される。これらの実施形態への様々な変形は、当業者には容易に明らかにされるであろう、そして本明細書中で規定される一般的な原理は、革新的な能力を使用することなく他の実施形態に適用されることができる。そのように、権利を主張する主題は、本明細書に示された実施形態に限定するように意図されるのではなく、本明細書中に開示された原理と新奇な特徴に整合する最も広い範囲に一致する。
【技術分野】
【０００１】
本発明は、ディジタル信号プロセッサにおける数学プロセッサの分野に係わり、そしてより詳しくは、数値の高速乗算を実行するための数学プロセッサにおいて使用されるブース乗算に関する。より具体的には、本発明は、ブース乗算方法及びシステムにおける使用のために符号付きの及び符号のないバイナリ値に対する電力効率の良い符号拡張に関する。
【背景技術】
【０００２】
ますます、電子装置及びサポート・ソフトウェア・アプリケーションは、ディジタル信号処理を必要とする。ホーム・シアター、コンピュータ・グラフィックス、医療画像技術及び電気通信技術は、全てディジタル信号処理技術を頼りにしている。ディジタル信号処理は、複雑であるが繰返しアルゴリズムの高速の数学演算を必要とする。多くのアプリケーションは、リアル−タイムの計算を必要とする、すなわち、信号は、時間の連続関数であり、それは数値処理のためにサンプリングされ、そしてディジタルに変換される必要がある。プロセッサは、サンプルが到着するとそのサンプルに個別の演算を実行するアルゴリズムを実行する必要がある。ディジタル信号プロセッサ、すなわちＤＳＰ（ＤＳＰ：digital signal processor）、のアーキテクチャは、そのようなアルゴリズムを取り扱うために最適化される。良い信号処理エンジンの特性は、高速で柔軟な算術計算ユニット、その計算ユニットへのそしてそれからの非拘束データ・フロー、計算ユニットの精度及びダイナミック・レンジの拡張、デュアル・アドレス発生器、効率的なプログラム・シーケンシング、及びプログラミングの容易さ、を含む。
【０００３】
ＤＳＰ技術の１つの将来有望なアプリケーションは、衛星回線又は地上回線を介して複数のユーザ間の音声及びデータ通信をサポートする符号分割多元接続（ＣＤＭＡ：code division multiple access）システムのような通信システムを含む。多元接続通信システムにおけるＣＤＭＡプロセスの使用は、米国特許番号第４，９０１，３０７号、名称“衛星リピータ又は地上リピータを使用するスペクトル拡散多元接続通信システム”、及び米国特許番号第５，１０３，４５９号、名称“ＣＤＭＡセルラ電話ハンドセット・システムにおいて波形を生成するためのシステム及び方法”に開示されており、両者とも特許請求された主題の譲受け人に譲渡されている。
【０００４】
ＣＤＭＡシステムは、１又はそれより多くの電気通信規格、そして現在流れているビデオ規格に準拠するように一般的に設計されている。１つのそのような第１世代規格は、“ＴＩＡ／ＥＩＡ／ＩＳ−９５ デュアル・モード広帯域スペクトル拡散セルラ・システムのための端末−基地局互換性規格”であり、以降ＩＳ−９５規格と呼ばれる。ＩＳ−９５ ＣＤＭＡシステムは、音声データとパケット・データとを送信することが可能である。パケット・データをもっと効率的に送信することが可能なより新しい世代の規格は、“第３世代パートナーシップ・プロジェクト”（３ＧＰＰ）という名前のコンソーシアムにより提案され、そしてドキュメント番号３Ｇ ＴＳ ２５．２１１、３Ｇ ＴＳ ２５．２１２、３Ｇ ＴＳ ２５．２１３、及び３Ｇ ＴＳ ２５．２１４を含むドキュメントのセットに組み込まれており、それは公に容易に利用可能である。３ＧＰＰ規格は、以降Ｗ−ＣＤＭＡ規格として呼ばれる。同様に、ビデオ圧縮規格があり、例えば、ＭＰＥＧ−１，ＭＰＥＧ−２，ＭＰＥＧ−４，Ｈ．２６３，及びＷＭＶ（ウィンドウズ（登録商標）メディア・ビデオ）、同様に、そのような無線ハンドセットがますます利用するであろう多くの他の規格がある。
【０００５】
高速で柔軟な算術計算ユニットを実現するために、高速乗算演算を実行する必要性がある。そのような演算を実行するための１つのプロセスは、ブース乗算として知られている。ブース乗算は、乗算される数値を記録することにより、より小さく、より早い乗算回路を可能にするプロセスである。ブース・プロセスを使用する乗算は、典型的に部分積を生成することにより実行される。部分積は、次に加算されて最終結果を求める。ブース乗算処理を用いると、部分積の個数は、乗数行列中の行の個数に等しい。用語“部分積”は、乗算ツリー中の行を呼ぶ。
【０００６】
元々のブースのアルゴリズムへの数多くの変形があるが、基本的な原理は、ブース・エンコーディング・プロセスを使用してより少ない部分積を生成することである。基数−４ブース・レコーディングのプロセスを使用することによりほぼ半分に部分積の個数を減少させることが可能である。基数−４ブース・レコーディングは、０と１のバイナリ値で元々は表わされる乗数Ｂのビットを、−２，−１，０，１又は２の値を取ることが可能な乗算因子の集合へとマッピングする。この方法は、そうでなければ生じるはずの部分積の個数をほぼ半分にする利点を提供する。これは、回路の動作中の伝搬遅延に関係し、そしてその実施の複雑性と電力消費に関係するので、回路設計において重要である。０，１又は２で、そしてある乗数又はその等価なものだけで、乗算する際にほんのわずかしか複雑性の不利がない。
【０００７】
ブース・エンコーディングのプロセスを使用して部分積が一旦生成されてしまうと、それらは削減技術を利用することにより一緒に加算される。削減のプロセスは、半加算器、全加算器、及びマルチ−オペランド（multi-operand）加算器を使用して並列処理で部分積ビットの複数の行を合計することを含む。この削減は、冗長フォーマットであると言われるビットの２行を結果としてもたらし、キャリー伝搬加算器を使用して分解するときに、その総和は最終積を表す。これらの行のうちの１つは、サム（Sum）Ｓと呼ばれ、そして他の行は、キャリー（Carry）Ｃと呼ばれる。乗算−累積（ＭＡＣ：multiply-accumulate）演算において、［Ｚ＋（ＡｘＢ）］中のＺ項は、一般的に、最終ＣＡＰの前に削減ツリー中に含まれる。この処理は、冗長フォーマットでの乗算積の分解に対して及び引き続く累積に対しての両者でＣＰＡを利用することを省略する。
【０００８】
ある複数の部分積が負であり得るので、２の補集合を作るために必要なハードウェアは、ブース乗算器の１つの態様である。そのようなハードウェアを用いて、乗算積を生成することが可能なブース乗算器を提供する必要性がある。現在、ＤＳＰアプリケーションのために効率的に−（ＡｘＢ）を生成することができる公知の方法又はシステムは、何も存在しない。したがって、ＤＳＰアプリケーションにおいて積の加算の逆、−（ＡｘＢ）、を生成するためにブース乗算処理を使用することができる方法とシステムに対する必要性が存在する。
【０００９】
しかしながら、一旦、そのような積が生成されると、“Ｚ”から乗算の積“ＡｘＢ”まで累積されようとしている値が積ＡｘＢよりも大きなビット幅の場合には、冗長積の“サム”と“キャリー”成分の両者は、適正に符号拡張される必要がある。
【００１０】
時々、ビットの広い範囲にわたり符号拡張を実行することが、必要であり得る。したがって、ＤＳＰ中でブース乗算処理の間に適正な符号拡張のプロセスに対する必要性がある。一般的に、乗算の両方の中間冗長積が、符号拡張されるであろう。
【００１１】
冗長積のサム成分だけが符号拡張される必要がある状況に関して電力効率の良いプロセスに対するさらなる必要性がある。
【００１２】
ブース乗算処理から最終積を生成する際にサム成分とキャリー成分の両方の符号拡張することを避ける必要性がある。
【００１３】
ブース乗算処理の間に中間３２−ビット積の部分積を符号拡張することから生じる電力消費を削減するためのさらなる必要性がある。
【００１４】
ブース乗算の符号拡張のフェーズの間に動作している乗算回路の数を減少させることがさらに必要である。
【発明の概要】
【００１５】
ブース乗算方法及びシステムのために電力効率の良い符号拡張を提供するための技術が開示され、そのプロセスは、パーソナル・コンピュータ、個人ディジタル補助装置、無線ハンドセット、及び類似の電子デバイスのますますエラーに強いソフトウェア・アプリケーションを処理するため、同様にますます増加している関係するディジタル信号プロセッサ速度及びサービス品質のための、ディジタル信号プロセッサの動作とディジタル信号プロセッサ命令の効率的な使用の両方を改善する。
【００１６】
１つの態様によれば、開示された方法及びシステムは、ブース乗算処理のための電力効率の良い符号拡張方法及びシステムを含む。開示された主題は、複数の部分積行を備えるブース乗算ツリーに符号ビットを導入する。その符号ビットは、符号拡張ステップを必要とする該ブース乗算処理の事象において有用である。ここに開示された方法及びシステムは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張する（すなわち、その符号が“１”であるときに符号拡張する）能力を含む。符号ビットの信号値を分解する（resolve）ことは、ブース乗算ツリー中に符号拡張ビットを生成することを必然的に伴う。この符号拡張ビットは、キャリー−アウト列中に置かれることができ、ブース乗算処理の積を拡張する。次に、本発明は、ブース乗算ツリーの少なくとも事前に決められた列への符号ビットにキャリー−アウト値を加えることによってブース乗算ツリーから最終積を形成する。これは、符号を有する最終積のサム成分を拡張しそして最終積のキャリー成分をゼロ−拡張する効果を有する。
【００１７】
開示された主題のこれらの利点及び他の利点、同様にさらなる新規な特徴は、本明細書中に提供される説明から明白であろう。このサマリーの意図するものは、権利を主張する主題の包括的な説明ではなく、むしろ主題の機能のうちのあるものの短い概要を提供することである。ここに提供される別のシステム、方法、特徴、及び利点は、次に続く図面及び詳細な説明を考察することで当業者に明らかになるであろう。全てのそのようなさらなるシステム、方法、特徴、及び利点が、本明細書の範囲内に含まれ、添付された特許請求の範囲内であることが、意図されている。
【図面の簡単な説明】
【００１８】
【図１】本実施形態を実行することが可能である通信システムの単純化したブロック図である。
【図２】本実施形態の教示を実行するためのＤＳＰアーキテクチャを図示する。
【図３】開示された主題の技術的な利点を提供するディジタル信号プロセッサの１つの実施形態のアーキテクチャ・ブロック図を与える。
【図４】開示された主題の様々な実行のためのデータ・パス図を表す。
【図５】開示された主題に適用可能な変形された１６×１６基数−４ブース・乗算ツリーを表す。
【図６】開示された主題のためのブース・レコーダを実装するための論理セルを与える。
【図７】開示された主題を用いる図７の論理セルに対するビット・グループ化の説明を与える。
【図８】−（ＡｘＢ）積のためのブース・レコーディング論理回路を実装するための論理セルを表す。
【図９】開示された主題がブース乗算において引き算をどのようにして取り扱うかの表である。
【図１０】開示された主題のさらなる教示にしたがった１６×１６ブース乗算削減ツリーを示す。
【発明の詳細な説明】
【００１９】
開示された主題の特徴、本質、及び利点は、図面を使用して以下に述べる詳細な説明から、さらに明確になるであろう。図面では、同じ参照符号は一貫して対応するものを特定する。
【００２０】
ここに示されるブース乗算方法及びシステムに対する電力効率の良い符号拡張のための開示された主題は、マルチ・スレッド処理を伴うアプリケーションを含む、非常に広範囲の様々なディジタル信号処理アプリケーションの使用を有する。１つのそのようなアプリケーションは、電気通信において見られ、そして特に、１又はそれより多くのディジタル信号処理回路を利用する無線ハンドセットにおいて見られる。その結果、下記の図１から図３は、電気通信ＤＳＰを説明し、その中では本教示は、有用であり得る。図４は、乗算処理のためのデータ・パスを述べ、その中では拡張ブース乗算演算の本開示が機能することができる。しかしながら、開示された主題が適用されることができるアプリケーションの実質的に無限の集合のうちの１つだけを、ここに説明されるインプリメンテーションが提供することを、忘れずにおくことである。
【００２１】
そのような無線ハンドセットがどのように使用されることができるかを説明する目的のために、図１は、開示される中断処理方法及びシステムの本実施形態を実行することが可能である通信システム１０の単純化したブロック図を与える。送信機ユニット１２において、データは、データ・ソース１４から送信（ＴＸ）データ・プロセッサ１６に、一般的にブロックで送られ、その送信データ・プロセッサ１６はデータをフォーマット化し、コード化し、そして処理して、１又はそれより多くのアナログ信号を生成する。アナログ信号は、次に送信機（ＴＭＴＲ）１８に与えられ、それはベースバンド信号を変調し、フィルタし、増幅し、そしてアップコンバートして、変調された信号を生成する。変調された信号は、次に１又はそれより多くの受信機ユニットにアンテナ２０を介して送信される。
【００２２】
受信機ユニット２２において、送信された信号は、アンテナ２４により受信され、そして受信機（ＲＣＶＲ）２６に与えられる。受信機２６内で、受信された信号は、増幅され、フィルタされ、ダウンコンバートされ、復調され、そしてディジタル化されて、インフェーズ（Ｉ）と（Ｑ）サンプルを生成する。サンプルは、次に受信（ＲＸ）データ・プロセッサ２８によりデコードされそして処理されて、送信されたデータを再生する。受信機ユニット２２におけるエンコーディングと処理は、送信機ユニット１２において実行されたコーディングと処理に相補的な方法で実行される。再生されたデータは、次にデータ・シンク３０に与えられる。
【００２３】
上に記述された信号処理は、音声、ビデオ、パケット・データ、メッセージ送信、及び１方向の他のタイプの通信をサポートする。双方向通信システムは、２方向のデータ送信をサポートする。しかしながら、他の方向に対する信号処理は、単純化のために図１には示されない。通信システム１０は、符号分割多元接続（ＣＤＭＡ：code division multiple access）システム、時分割多元接続（ＴＤＭＡ：time division multiple access）通信システム（例えば、ＧＳＭ（登録商標）システム）、周波数分割多元接続（ＦＤＭＡ：frequency division multiple access）通信システム、又は地上回線を経由して複数のユーザ間の音声とデータ通信をサポートする他の多元接続通信システムであり得る。ある特定の実施形態では、通信システム１０は、Ｗ−ＣＤＭＡ規格に準拠するＣＤＭＡシステムである。
【００２４】
図２は、図１の送信データ・プロセッサ１６と受信データ・プロセッサ２８として機能することができるＤＳＰ４０アーキテクチャを図示する。もう一度、ＤＳＰ４０がここに示された教示及び概念を効果的に使用することができる非常に多くの可能性のあるディジタル信号プロセッサ実施形態のうちの１つの実施形態を表すだけであることを、強調する。ＤＳＰ４０において、それゆえ、スレッドＴ０：Ｔ５（参照番号４２から５２）は、別のスレッドからの命令の集合を含む。回路５４は、命令アクセス・メカニズムを表し、そしてスレッドＴ０：Ｔ５に対する命令を取り出す（fetch）ために使用される。回路５４のための命令は、命令キュー５６へとキューされる。命令キュー５６中の命令は、プロセッサ・パイプライン６６（下記を参照）へと発せられるように準備されている。命令キュー５６から、１つのスレッド、例えば、スレッドＴ０、は、発行論理回路５８によって選択されることができる。選択されたスレッドのレジスタ・ファイル６０が、読み出され、そして読み出されたデータは、スロット０からスロット３に対する実行データ・パス６２へ送られる。スロット０からスロット３は、この例では、本実施形態において用いられるパケット・グループ化組み合わせを規定する。
【００２５】
実行データ・パス６２からの出力は、ＤＳＰ４０の動作からの結果を戻すために、レジスタ・ファイル書込み回路６４に行き、しかもその回路は個々のスレッドＴ０：Ｔ５を適応させるように構成される。そのように、回路５４からのデータ・パス及び様々なスレッドに応じて分けられるレジスタ・ファイル書込み回路６４の前のデータ・パスは、処理パイプライン６６を形成する。
【００２６】
本実施形態は、６個までのスレッド、Ｔ０：Ｔ５、を有する１つのマイクロプロセッサを使用するヘテロジーニアス素子プロセッサ（ＨＥＰ：heterogeneous element processor）の混成タイプを使用することができる。プロセッサ・パイプライン６６は、６つのステージを有し、回路５４からレジスタ６０と６４へのデータ項目を取り出すために必要なプロセッサ・サイクルの最小数を組み合わせる。ＤＳＰ４０は、プロセッサ・パイプライン６６内の異なるスレッドＴ０：Ｔ５の命令を同時に実行する。すなわち、ＤＳＰ４０は、６個の独立したプログラム・カウンタ、プロセッサ・パイプライン６６内のスレッドＴ０：Ｔ５の命令を識別する内部タッギング・メカニズム、及びスレッド・スイッチをトリガするメカニズム、を与える。スレッド・スイッチ・オーバーヘッドは、ゼロからほんの数サイクルまで変化する。
【００２７】
ＤＳＰ４０は、それゆえ、広範囲の様々な信号、画像、及びビデオ処理アプリケーションにわたり高性能かつ低電力の目的で設計される汎用ディジタル信号プロセッサを提供する。図３は、ＤＳＰ４０アーキテクチャの簡単な全体像を与え、開示された主題の１つの表現のために関係する命令セット・アーキテクチャのある複数の態様を含む。ＤＳＰ４０アーキテクチャのインプリメンテーションは、インターリーブされたマルチスレッディング（ＩＭＴ：interleaved multithreading）をサポートする。この実行モデルでは、ハードウェアは、パイプライン中の異なるスレッドからの命令をインターリーブすることにより複数のハードウェア・スレッドＴ０：Ｔ５の同時の実行をサポートする。この特徴は、ＤＳＰ４０が高いコア及びメモリ利用を維持したままで、アグレッシブなクロック周波数を含むことを可能にする。ＩＭＴは、費用のかかる補償機構、例えば、適切でない実行、大規模な転送ネットワーク、及びその他、を必要とせずに高スループットを提供する。
【００２８】
図３は、より一層具体的に、開示された主題の教示を利用することができる１つのスレッドに対するプログラミング・モデルの１つの実施形態のアーキテクチャ・ブロック図を与える。ブロック図７０は、ＡＸＩバス７４からの命令を受け取る非公開命令キャッシュ７２を図示し、その命令はスレッドＴ０：Ｔ５のシーケンサ７６、ユーザ制御レジスタ７８、及び管理制御レジスタ８０への混合の１６−ビットと３２−ビット命令を含む。シーケンサ７６は、Ｓ−パイプ・ユニット８２、Ｍ−パイプ・ユニット８４、Ｌｄ−パイプ８６、及びＬｄ／Ｓｔ−パイプ・ユニット８８への混成タイプの２−方向スーパースカラ命令と４−方向ＶＬＩＷ命令を与える。ＡＸＩバス７４は、スレッドＴ０：Ｔ５へのＬＤ／ＳＴ命令を共有データ・キャッシュ９０と同様に通信する。外部ＤＭＡマスタ９６を用いて、共有データＴＣＭ９８は、ＬＤ／ＳＴ命令を通信し、そのＬＤ／ＳＴ命令は、スレッドＴ０：Ｔ５へとさらに流れる。ＡＨＢ周辺バス１００から、ＭＳＭ特定コントローラ１０２は、Ｔ０：Ｔ５を有する中断ピンを通信し、それは中断コントローラ命令、デバッグ命令、及びタイミング命令を含む。グローバル制御レジスタ１０４は、スレッドＴ０：Ｔ５と制御レジスタ命令を通信する。
【００２９】
図３のＭ−パイプ８４において述べたように単一スレッド処理のアーキテクチャ内では、高速数学処理が生じる。電力効率は、ＤＳＰ４０の動作に決定的であり、そしてＭ−パイプ８４は、自身の動作においてこの考慮を含む必要がある。そのような乗算処理において生じるものは、乗算の結果が冗長形式で利用可能になることであり、そしてこれらの冗長な結果は、乗算−累積演算において使用される。そのような冗長な結果で、符号拡張が、両方の冗長積について生じる必要があり得る。開示された主題は、各乗算の２つの冗長積のうちの１つにだけ適用される符号拡張を提供する。これは、中間冗長積が大きなビット範囲にわたり符号拡張される必要があるケースでは顕著な省電力をもたらす。
【００３０】
同様な電力効率の考えは、開示された主題が適用されることができるいずれのアプリケーションにおいてもおそらく存在する。したがって、ブース乗算処理が行われる速度は、個々に開示された題材の特徴的な新規な態様を提供する。
【００３１】
開示された主題は、乗算のためのブース・エンコーディング・プロセスを提供し、それは部分積の最後の行が‘１要素’拡張される部分積生成の方法を利用する。乗数の削減ツリーの最下位列の削減を適切に操作することによって、‘サム’冗長積だけが符号拡張される必要があるが、‘キャリー’冗長積はゼロ拡張されることが可能であることを、開示されるプロセスは確実にする。‘サム’だけが符号拡張されるので、開示されるプロセス及び関係する構造は、乗算の冗長積を符号拡張することに含まれる電力コストを削減する。開示された主題がこれらの省電力と関連する効率をどのようにして実現するかの理解を得るために、特定の実施形態のさらなる実例による説明がここに与えられる。
【００３２】
図４は、それゆえ、開示された主題の様々な実施のためのデータ・パス図１８０を表し、そして本ブース乗算処理がそこで行われることができるデータ・フローを設定する。特に、乗算ブロック１１８は、ＲｓとＲｔ入力を受け取る。乗算ブロック１１８の内部にあるものは、乗算ユニットＭ０：Ｍ３である。特に、Ｍ０乗算器ユニット１８２、Ｍ１乗算器ユニット１８４、Ｍ２乗算器ユニット１８６、及びＭ３乗算器ユニット１８８は、ＲｓとＲｔ入力を別々に受け取って、シフト／符号拡張ユニット１４８への、それぞれ、Ｓ０Ｃ０（すなわち、サム０とキャリー０）、Ｓ１Ｃ１、Ｓ２Ｃ２、及びＳ３Ｃ３出力を生成する。シフト／符号拡張ユニット１４８は、これらの中間冗長積の論理シフトと符号拡張を実行する責任がある。
【００３３】
乗算器ブロック１１８は、Ｍ−パイプ８４に対する命令に関連する乗算を実行する。これらの命令は、１６×１６乗算処理を基底として使用する複合命令として取り扱われることができる。乗算器ブロックは、４個の１６×１６乗算器ユニットＭ０：Ｍ３から構成される。各乗算器ユニットＭ０：Ｍ３は、複数のモードで機能することが可能であり、多種多様なＭ−タイプ命令をサポートする。符号付きモードと符号なしモードとがサポートされる。乗算器は、減算がその積に実行される必要があるケースでは、それらの積の２の補数を同様に生成することが可能である。
【００３４】
開示された主題を用いて、Ｍ０：Ｍ３乗算器１８２から１８８は、基数−４ブース・エンコーディングを使用する。符号なしモードでは、それらは、符号ビットとして機能する追加の１７番目のビットを有する１７×１７乗算に似ている。倍精度乗算（すなわち、３２×３２乗算）を除いて、全ての他の乗算命令は、“符号付き×符号付き”又は“符号なし×符号なし”である。倍精度３２×３２乗算及び複数の１６×１６乗数を使用する３２×１６乗算は、同様に“符号付き×符号なし”乗算と“符号なし×符号付き”乗算とを必要とする。これらのモードの全ては、Ｍ０：Ｍ３乗算器１８２から１８８の被乗数と乗数オペランド（operand）の符号ビットを制御することによりサポートされる。
【００３５】
シフト／符号拡張ユニット１４８からの出力は、マルチ−オペランド加算器１５０に行き、そしてＲ０：Ｒ３入力へと分解される。マルチ−オペランド加算器１５０は、これらのＲ０：Ｒ３入力を受け取り、そして圧縮と累積ステージのセットの後で、最終的にＲｄｄ出力１７０を与える。
【００３６】
データ・パス１８０は、４つのフェーズへと分割可能であるように理解されることができる。まず第１に、データ配送フェーズでは、ＲｓとＲｔソース・レジスタからのデータは、乗算ブロック１１８に供給される。乗算ブロック１１８の中では、ソース・オペランドからの１６−ビット・ハーフ・ワードは、命令に基づいて４個のＭ０：Ｍ３乗算器１８２から１８８に配送される。次に、部分積生成及び削減（reduction）ベクトル加算又は減算が行われる、そこでは、Ｍ０：Ｍ３乗算器１８２から１８８は、基数−４ブース・エンコーディングを使用して部分積を生成し、そして出力の冗長対へ削減を使用してそれらを削減する。
【００３７】
マルチ−オペランド削減フェーズの間、乗算ブロック１１８からの冗長出力は、マルチ−オペランド加算器１５０へ入力され、その加算器はこれらの入力とオプションの累算値／丸めた値を２組の冗長出力へと削減する。最後に、加算／サチュレーション（saturation）フェーズでは、冗長出力は、キャリー増殖（propagate）加算を使用して解かれ、そしてサチュレーションは、適用可能であるときに実行される。
【００３８】
開示された主題は、したがって、そのような値の変形されたブース乗算を規定する。そのような複素値を用いて、入力は、下位ハーフワードの実数１６−ビット値と上位ハーフワードの虚数１６−ビット値とを有する。乗算結果は、オプションとして０−１ビットだけスケーリングされる。丸め定数がそれぞれの実数和と虚数和に加算される。実数部と虚数部は、３２ビットに個別にサチュレートされる。３２−ビット結果のそれぞれの上位１６−ビットは、３２−ビット行先レジスタにパック（pack）される。
【００３９】
この例では、Ｓ０：Ｓ３とＣ０：Ｃ３は、３３−ビット幅である。１６×１６乗算の出力が３２−ビットで表わされることが可能であるとしても、ある複数の命令は、符号なしモードで実行し、そして追加ビットが符号拡張を容易にするために符号ビットとしてこのケースでは使用される。Ｓ０：Ｓ３とＣ０：Ｃ３は、シフト／符号拡張ユニット１４８を経由して渡される。Ｓ０：Ｓ１とＣ０：Ｃ１は、パッキングの前に、最終結果の低次の３２−ビットを与える。これは、結果の実数部を形成する。これらの４つの数は、命令で指定される場合には、１−ビットの左シフトによりオプションとしてスケーリングされる。
【００４０】
これらの数のシフトされたバージョンは、Ｒ０：Ｒ３と名付けられる。Ｒ０：Ｒ３は、マルチ−オペランド加算器１５０を経由して渡される。マルチ−オペランド加算器１５０からの出力は、サチュレーション／加算ユニット１７０に流れる。
【００４１】
ここで、開示された主題は、様々なブース乗算処理において実行されることができる。しかしながら、開示された主題の具体的な使用を理解することは、そのようなアプリケーションが起きることがある特定のブース乗算処理の表現を通して最も良く達成されることができる。したがって、図５は、開示された主題に適用可能な変形された１６×１６基数−４ブース・乗算ツリーを提示することにより、開示された主題のブース乗算処理を理解することを容易にする。図５のドット図２００は、開示された主題の１６×１６乗数についての基数−４ブース・エンコーディングを概念的に図示し、それは９個の部分積２０２，２０４，２０６，２０８，２１０，２１２，２１４，２１６，と２１８とを結果としてもたらす。９個の部分積は、２個の３３−ビット冗長出力に削減され、それらは２レベルの３：２削減と引き続く１レベルの４：２圧縮からなる削減ツリーを使用するＳ０：Ｓ３及びＣ０：Ｃ３である。３２−ビットの精度は１６×１６乗算のために十分であるが、３３番目のビットは、符号なし乗算のケースにおける符号ビットとして機能するように同様に保存される。３３番目の列からの追加のキャリー−アウト・ビットは、同様に、符号拡張を支援するための乗算器からの出力である。
【００４２】
さらに図５を参照して、各部分積行２２０から２３６は、横方向に示される被乗数ビット２３８の倍数である。列番号は、図５の上部に示されている。乗数ビット２４０は、縦方向に示され、そしてこれらのビットは、部分積行２２０から２３６を形成するための乗算係数を生成するために記録される。図５に示される信号ｎ０からｎ７は、スティッキー（sticky）“１”を示し、それは負の加重を受ける部分積行２２０から２３６に付加される。これらは、積の最終反転を必要としない乗算を扱うために十分である。乗数における−（ＡｘＢ）陰関数表示のケースを取り扱うために、追加の信号ｎ８が与えられる。
【００４３】
乗算演算の積が乗数ツリー内で非明示的に減算されるときに、信号ｓ０からｓ７は、符号拡張を取り扱う。ＡとＢとが、それぞれ被乗数と乗数であると仮定される場合に、基数−４ブース・エンコーディングは、乗数オペランドＢの３個のビットのグループをエンコーディングすることにより、そして集合｛−２Ａ，−Ａ，０，Ａ，２Ａ｝から部分積を選択するためにこのエンコーディングを使用することにより、進められる。ここで、最終積（ＡｘＢ）が減算される必要がある場合には、それはＡｘ−（Ｂ）を加算することに等しく、それは順に、積（（−Ａ）ｘＢ）を加算することに等しい。乗数は、ここでＢから（−Ｂ）に変更される。
【００４４】
開示された主題がそこにおいてアプリケーションを見出すことができるブース乗算処理の一部として、図６は、開示された主題を実行するためのブース・レコーダ回路２５０を提供する。ブース・レコーダ・セル２５０は、ＸＯＲ２５６でのＬＳＢ入力２５４からインバータＸＯＲ２６０でのＭＳＢ入力２５８までの範囲の乗数グループ入力２５２を含む。ＭＳＢ入力２５８は、ブース・レコーダ回路２５０からの“ｎｅｇ”出力を同様に与える。ＸＯＲ２５６からの出力は、ブース・レコーダ２５０からのＡｘ１信号、Ａを表し、インバータＸＯＲ２６４への入力を同様に与える。インバータＸＯＲ２６０からの出力は、インバータＸＯＲ２６４への入力を同様に与えて、ブース・レコーダ回路２５０からのＡｘ２信号、２Ａを生成する。ＸＯＲ２６４は、ブース・レコーダ回路２５０からの否定 “ｎｅｇ”を指示するための出力を与える。そのように、ブース・レコーダ回路２５０は、乗数Ｂの３−ビットを検査し、そして信号“Ａ”，“２Ａ”と“ｎｅｇ”へとそれらを記録する。減算が実行される必要があるとき、“ｎｅｇ”信号は、部分積を生成するために反転され、それは積、ＡｘＢ、の２の補数を生成する。
【００４５】
図７は、開示された主題を用いる図６の論理セルに対するビット・グループ化の説明を与える。特に、基数−４ブース・レコーディングは、１６−ビット乗数Ｂから９個の乗算係数を生成し、それはＡの倍数として使用され、９個の部分積を生成する。０から８までの範囲の“ｎ”に対して、図７の表は、ビット・グループＢ［２ｎ＋１：２ｎ−１］に対するブース乗算係数を決定する。本実施形態のレコーディング方式に関して、Ｂ［−１］は、ゼロであると仮定される。Ｂ［１６］とＢ［１７］は、Ｂが符号なしの数である場合にゼロであり、そしてＢが符号付きの数である場合にＢの符号拡張である、すなわち、Ｂ［１７］＝Ｂ［１６］＝Ｂ［１５］。乗算係数は、３つの信号へと記録される：それはＸＯＲ２５６からのＡ、インバータＸＯＲ２６４からの２Ａ及びＭＢＳ入力２６２からの“ｎｅｇ”である。そのように、Ａに対する乗算係数が−２であるとき、信号２Ａとｎｅｇは、ハイである。同様に＋１に対して、Ａだけがハイであり、そして＋／−０に対して全ての３つの信号は、ローである。しかも、積ＡｘＢを生成することに関して、最上位ビット・グループに対する乗算係数、Ｂ［１７：１５］は、常に正であることに、注意する。ここで、Ｂ［１７：１５］に対する可能なビット・グループは、Ｂが符号なしの場合には［０００］又は［００１］であり、そしてＢが符号付きの場合には［０００］又は［１１１］であるだけである。図７から、これらの全てのグループは、正の乗算係数に導く。本明細書中に記述されるブース乗算マルチプレクサは、それゆえ、部分積を生成するためにセット｛０，Ａ，２Ａ｝から選択することができる。
【００４６】
図８は、−（ＡｘＢ）積のためのブース・レコーディング論理回路を実装するためのブース・レコーダ回路２７０を提供する。ブース・レコーダ・セルは、ＸＯＲ２７６でのＬＳＢ入力２７４からインバータＸＯＲ２８０でのＭＳＢ入力２７８までの範囲にわたる乗数グループ入力２７２を含む。“減算”入力２８２とＭＳＢ入力２７８は、ＸＯＲ２８４へ流れる。ＸＯＲ２７６からの出力は、ブース・レコーダ２７０からの被乗数Ａ信号を表し、それに加えてインバータＸＯＲ２８６への入力を与える。インバータＸＯＲ２８０からの出力は、ブース・レコーダ回路２７０からの２Ａ信号を生成するためにインバータＸＯＲ２８６への入力を同様に与える。ＸＯＲ２８４は、ブース・レコーダ回路２７０からの“ｎｅｇ”出力を与える。
【００４７】
本主題がそれに対する使用を見出すことができるブース乗算処理の開示されたアプリケーションでは、図８は、それゆえ、被乗数Ａと乗数Ｂの積の負の値が、ＡとＢの負の値との積を計算することによって得られるという特性を利用する。これは、それゆえ、最初にＡｘＢの積を計算し、そして次に−（ＡｘＢ）を得るために積の２の補数を計算する公知の２ステップ・プロセスを回避する。ブース・レコーダ回路２７０は、乗算のステージと並行して否定を実行する。
【００４８】
積の２の補集合を作ることは、−（ＡｘＢ）がＡｘ（−Ｂ）に等価であるという事実を利用する。この例では、オペランド（−Ｂ）は、乗数として扱われる。乗数として（−Ｂ）を使用して生成されたブース乗算係数は、乗数オペランドとしてＢを使用して生成された乗算係数に対応する付加的な逆である。積ＡｘＢを計算するために使用するブース乗算ハードウェア構成は、ブース乗算係数のそれぞれの符号を反転することによりＡｘ（−Ｂ）を計算するために再使用されることが可能である。この符号は、ブース・レコーダ回路２７０の“ｎｅｇ”信号によって決定され、それは積を否定する際に“−ｎｅｇ”信号を生成するためにレコーディング・ハードウェアに対する変更である。
【００４９】
ブース・レコーダ回路２７０において、ＸＯＲゲート２８４は、非クリティカル・パス上にあり、そしてクリティカル・パスに寄与しない。その代りに、クリティカル・パスは、信号Ａと２Ａを生成するための乗数ビットを含む。部分積のための乗算係数の符号を反転させるこのプロセスは、最終積行の符号が負であり得るケースを導入する。これゆえ、信号“ｎ８”は、上記の図５に見られるように、乗算ツリーに追加されることができる。行を追加することは、追加の行を適応させるために削減ステージを変更することにより削減されることができる。これは、しかしながら、追加の遅延と関係するハードウェアを意味することがある。
【００５０】
ここに示されたプロセスは、削減ステージにおいて追加の行を含まないが、その代わりに乗算ツリーへの論理的な変更を行うことにより部分積の既存の９行中へとｎ８信号を吸収することに焦点を合わせている。乗算ツリーに追加される遅延は、最小である。
【００５１】
形式ＰＰｒｏｗ＿ｃｏｌｕｍｎの各“ドット”を参照する表記は、開示された主題のこの態様を理解することを求める際に役立つ。図９を参照して、乗算ツリー中の各バイナリ・ビット（ドット）は、その固有の加重と行列中の位置とを有する。同じ列の全てのビットは、同じ加重を有し、そしてその加重が維持される限り任意の順番で削減されることができる。行は、０で始まり上から下に番号を付けられ、そして列は、０で始まり右から左に番号を付けられる。この表記を使用して、ｎ８は、ＰＰ１０＿１６に等価である。ＰＰ０＿１６，ＰＰ０＿１７，ＰＰ０＿１８とＰＰ０＿１９は、基数−４ブース・エンコーディングにより公知のスケーリングと符号拡張プロセスとを使用して生成される。そのようなアプローチを用いて、ｎ８を乗算ツリーの中へと吸収することが可能である。そのように、符号付き乗算モードと符号なし乗算モードの両方においてＰＰ０＿１６，ＰＰ０＿１７，ＰＰ０＿１８とＰＰ０＿１９に対する全ての可能性のあるビット値を解析することによって、ｎ８がその中に挿入されることができる位置は、全ての可能性のあるブース乗算係数に対して決定することが可能である。
【００５２】
図９は、部分積行０の４つの最上位ビットに対する値の範囲、そして信号ｎ８をこの４−ビット・フィールドに追加する効果を列挙する。ＭＵＸ構成は、ｎ８がハイであるときに、４−ビット・フィールドの変更された値を選択することを認める。言い換えると、開示されたプロセスは、信号ｎ８が列１６のところに追加される、すなわち、ＰＰ０＿１６である場合に、部分積行０の４つの最上位ビットの値を事前に計算し、そしてこの変更された４−ビット・フィールドを削減ステージにおいて使用する。ＭＵＸ構成は、一旦ＰＰ０＿１６（表中に“ａ”として示される）が標準ブース多重送信回路系を使用して計算されるように最適化される。ｎ８に基づく変更された４−ビット・フィールドは、この後で最小遅延で解かれる。乗算処理の残りは、積ＡｘＢを生成するための通常の乗算フローと同じである。
【００５３】
図１０は、開示された主題のさらなる態様に対して利用可能な変更された１６×１６基数−４ブース乗算ツリーを示す。図１０から、本開示の重要な符号拡張と定数丸め機能とを理解することが可能である。１６×１６乗数の削減ステージへの変更は、９個の部分積行を通るクリティカル・パスを最小にし、そしてその積が冗長サム−キャリー・フォーマットで利用可能であるときに、符号拡張を効率的に与える。図１０は、１６×１６基数−４ブース乗数のための変更された削減ツリー３０４を示す。変更された削減ツリー３０４は、符号付きオペランドと符号なしオペランドを適応させ、そして積を否定する可能性を有する。
【００５４】
削減の第１ステージは、全加算器の３行を使用して９行を６行に削減する。削減の第２ステージは、全加算器の２行を使用して６行を４行に削減する。削減の第３ステージと最終ステージは、４：２マルチ−オペランド加算器のある行を利用して、４行を最終の冗長サムとキャリー行へと削減する。サムとキャリーの３２ビットが１６×１６積を表示するために十分であるけれども、追加ビットは、符号拡張が符号なし乗算に対して正しく取り扱われることを確実にする。
【００５５】
図１０は、積を形成する下位の３２ビットよりもすぐ上位である列３０６をさらに示す。本明細書は、最終部分積行３０８のための符号ビットｓ８を導入するために列＃３２から上方のブース乗算ツリーを変更する。この符号ビットｓ８は、積が符号拡張を必要としない場合には、必要とされない。ここで、部分積行８の正しい符号を保存するために、プロセスは、１ビットだけ部分積行３０８を拡張することを含む。＃３２よりも大きい列は、削減の最終ステージまで影響されない。そのような点において、信号〜ｓ８は、列＃３１からのキャリー−アウトにより分解し、そして“ｃ―”として示されるキャリー−アウト３１０を生成する。
【００５６】
最終積は、上方への行＃３３から１要素拡張にキャリー−アウト“ｃ―”３１０を加算することにより形成される。その効果は、符号としてｃ―を有する最終積のサム成分を符号拡張するためであり、一方で最終積のキャリー成分はゼロ−拡張である。これらのステップは、サム成分とキャリー成分の両方を符号拡張する必要性を排除する。例えば、１６×１６乗算が３２−ビット積への６４−ビット値の累算を必要とするＭＡＣ演算の一部である場合には、６４−ビット値に３２−ビット積を加算する前に、３２−ビット積を６４−ビットに符号拡張することが、必要とされるはずである。中間３２−ビット積が冗長形式で残され、そしてここに提示された符号拡張プロセスが適用される場合に、３１−ビットにわたりキャリー成分を符号拡張するために使用する複数のＭＵＸを排除することの可能性のために、相当量の電力節約が生じ得る。
【００５７】
再び図１０を参照して、本明細書は、乗数、Ｂに丸め定数を加算する能力をさらに提供する。ＤＳＰ演算において１６×１６乗算に対する一般的丸め定数は、０×８０００である。１６×１６乗算の積を丸めることは、一般的な演算であり、それは２ステップ演算として典型的に実行される、ここで、乗数が積を生成するために最初に使用され、そして次に丸め定数がその積に加算される。
【００５８】
上に記述された表記を使用すると、図１０ではＰＰ８＿１５が０であることに注意する。乗算行列中のこのビット位置に“１”を挿入することにより、最初に積を生成しそして次にその積に値０×８０００を加算することにより求められるはずの結果と同じ結果を生成することが可能である。このプロセスは、しかもクリティカル・パスにいかなる待ち時間も追加しない。
【００５９】
乗算ブロック１１８中のハードウェアが乗算の積に１つの累算−オペランドを加算することが可能であるだけの能力に制限される場合には、乗算の積が丸められる必要があるときに累算−オペランドを有する丸め定数をＭＵＸすることが、一般的である。これは、乗算の積についての丸め演算と累算演算との両方を単一ステップで実行することを困難にさせる。しかし、ここに開示されたプロセスを使用することは、そのような制限を排除する。
【００６０】
要約すると、開示された主題は、設計のためのプロセス及びディジタル信号プロセッサの使用を提供し、通信（例えば、ＣＤＭＡ）システムにおける送信を処理することを含む。開示された方法及びシステムは、ブース乗算処理のための電力効率の良い符号拡張方法及びシステムを含む。開示された主題は、複数の部分積行を備えるブース乗算ツリーに符号ビットを導入する。符号ビットは、符号拡張ステップを必要とするブース乗算処理の事象（event）において有用である。ここに開示された方法及びシステムは、事前に決められた部分積行の正しい符号を保存するために符号ビットを使用してブース乗算ツリーの事前に決められた部分積行を１要素拡張する。符号ビットの信号値を分解することは、ブース乗算ツリーにおいて符号拡張ビットを生成することを必然的に伴う。符号拡張ビットは、キャリー−アウト列中に配置されることができて、ブース乗算処理の積を拡張する。次に本発明は、ブース乗算ツリーの少なくとも事前に決められた列に対する符号ビットにキャリー・アウト値を加算することによってブース乗算ツリーから最終積を形成する。これは、符号ビットを有する最終積のサム成分を拡張する効果を、そして最終積のキャリー成分をゼロ拡張する効果を有する。
【００６１】
本発明は、変形されたブース乗数の技術的な利点をさらに提供し、それは形式［Ｚ＋−（ＡｘＢ）＋丸め定数］のＭＡＣ演算において使用されることが可能である。この乗数は、（ａ）ブース乗算係数を否定してそして余分なスティッキー・ビットを削減ツリー中へと吸収することにより、（ｂ）丸め定数を削減ツリーへと詰め込む場所を見つけることにより、そして（ｃ）冗長サムの符号拡張を必要とするだけの符号拡張プロセスを使用することにより、遅延、電力、及びハードウェアを最小にする。
【００６２】
その上、本明細書中に記述された処理の特徴及び機能は、様々な方式で実施されることができる。例えば、ＤＳＰ４０が上記の演算を実行することがあるだけでなく、本実施形態は、用途特定集積回路（ＡＳＩＣ：application specific integrated circuit）、マイクロコントローラ、マイクロプロセッサ、又は本明細書中に記述された機能を実行するために設計された他の電子回路、で実施されることができる。好ましい実施形態のこれまでの説明は、それゆえ、権利を主張する主題を当業者が制作すること又は使用することを可能にするために提供される。これらの実施形態への様々な変形は、当業者には容易に明らかにされるであろう、そして本明細書中で規定される一般的な原理は、革新的な能力を使用することなく他の実施形態に適用されることができる。そのように、権利を主張する主題は、本明細書に示された実施形態に限定するように意図されるのではなく、本明細書中に開示された原理と新奇な特徴に整合する最も広い範囲に一致する。
【特許請求の範囲】
【請求項１】
ブース乗算処理を容易にするための電力効率の良い符号拡張方法であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用すること、ここで、それぞれの前記部分積行はブース乗算処理の部分積を備え、前記ブース乗算処理の事象（event）における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張すること；
前記ブース乗算ツリーにおいて符号拡張ビットを生成することによって前記符号ビットの信号値を分解する（resolve）こと、ここで、前記符号拡張ビットは前記ブース乗算処理の前記積を拡張する場所に置かれる；及び
前記符号を有する最終積のサム（sum）成分を効果的に拡張しそして前記最終積のキャリー（carry）成分をゼロ−拡張するために前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成すること、
のステップを具備する方法。
【請求項２】
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減すること；
第２の複数の加算器回路を使用して前記６部分積行を４部分積行に削減すること；
圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減すること；及び
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列への符号ビットを変更すること、
によって前記複数の部分積を削減するステップをさらに具備する、請求項１の方法。
【請求項３】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを含めるステップをさらに具備する、請求項１の方法。
【請求項４】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するステップをさらに具備する、請求項１の方法。
【請求項５】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目以上の列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するステップをさらに具備する、請求項１の方法。
【請求項６】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するステップをさらに具備する、請求項１の方法。
【請求項７】
ブース乗算処理を実行するためのディジタル信号処理に関係する電力効率の良い符号拡張回路であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するための符号適用回路系、ここで、それぞれの前記部分積行はブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するための乗算回路系； 前記ブース乗算ツリーに符号拡張ビットを生成することによって前記符号ビットの信号値を分解するための符号値解析回路系、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記乗算回路系は、さらに前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために、前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットに前記キャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するためである、
を具備する、符号拡張回路。
【請求項８】
９部分積行を６部分積行に削減するための第１の複数の加算器回路；
前記６部分積行を４部分積行に削減するための第２の複数の加算器回路行；
前記４部分積行を、使用するサム行とキャリー行に削減するための圧縮器回路；及び 符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列に符号ビットを加えるためのエンコーディング回路系、
をさらに具備する、請求項７のシステム。
【請求項９】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるためのエンコーディング回路系をさらに具備する、請求項７のシステム。
【請求項１０】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ前記３２番目の列よりも大きい列を変更するためのエンコーディング回路系をさらに具備する、請求項７のシステム。
【請求項１１】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの前記３２番目とそれより大きい列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するための削減回路系をさらに具備する、請求項７のシステム。
【請求項１２】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するための乗算回路系をさらに具備する、請求項７のシステム。
【請求項１３】
個人向け電子デバイスをサポートする演算のためのディジタル信号プロセッサであって、ディジタル信号処理はブース乗算処理のために電力効率の良い符号拡張を実行するための手段を具備し、前記処理は：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するための手段、ここで、前記部分積行のそれぞれはブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するための手段；
前記ブース乗算ツリーにおいて符号拡張ビットを生成することによって前記符号ビットの信号値を分解するための手段、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために、前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するための手段、
を具備する処理である、ディジタル信号プロセッサ。
【請求項１４】
前記複数の部分積を削減するための手段をさらに具備し、前記部分積を削減する手段は：
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減するための手段； 第２の複数の加算器行を使用して前記６部分積行を４部分積行に削減するための手段； 圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減するための手段；そしてさらに
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列に符号ビットを加えるための手段、
を具備する前記手段である、請求項１３のディジタル信号プロセッサ。
【請求項１５】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１６】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１７】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目及びそれより大きい列から１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１８】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するためのステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１９】
ブース乗算処理のための電力効率の良い符号拡張方法を実行するためにその中に組み込まれたコンピュータ読取り可能なプログラム・コード手段を有するコンピュータ使用可能な媒体であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するためのコンピュータ読取り可能なプログラム・コード手段、ここで、前記部分積行のそれぞれはブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のために前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するためのコンピュータ読取り可能なプログラム・コード手段；
前記ブース乗算ツリーに符号拡張ビットを生成することによって前記符号ビットの信号値を分解するためのコンピュータ読取り可能なプログラム・コード手段、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するためのコンピュータ読取り可能なプログラム・コード手段、
を具備するコンピュータ使用可能な媒体。
【請求項２０】
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減するためのコンピュータ読取り可能なプログラム・コード手段；
第２の複数の加算器行を使用して前記６部分積行を４部分積行に削減するためのコンピュータ読取り可能なプログラム・コード手段；
圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減するためのコンピュータ読取り可能なプログラム・コード手段；及び
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列へ符号ビットを加えるためのコンピュータ読取り可能なプログラム・コード手段、
をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２１】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２２】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２３】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目及びそれより大きい列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２４】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項１】
ブース乗算処理を容易にするための電力効率の良い符号拡張方法であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用すること、ここで、それぞれの前記部分積行はブース乗算処理の部分積を備え、前記ブース乗算処理の事象（event）における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張すること；
前記ブース乗算ツリーにおいて符号拡張ビットを生成することによって前記符号ビットの信号値を分解する（resolve）こと、ここで、前記符号拡張ビットは前記ブース乗算処理の前記積を拡張する場所に置かれる；及び
前記符号を有する最終積のサム（sum）成分を効果的に拡張しそして前記最終積のキャリー（carry）成分をゼロ−拡張するために前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成すること、
のステップを具備する方法。
【請求項２】
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減すること；
第２の複数の加算器回路を使用して前記６部分積行を４部分積行に削減すること；
圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減すること；及び
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列への符号ビットを変更すること、
によって前記複数の部分積を削減するステップをさらに具備する、請求項１の方法。
【請求項３】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを含めるステップをさらに具備する、請求項１の方法。
【請求項４】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するステップをさらに具備する、請求項１の方法。
【請求項５】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目以上の列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するステップをさらに具備する、請求項１の方法。
【請求項６】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するステップをさらに具備する、請求項１の方法。
【請求項７】
ブース乗算処理を実行するためのディジタル信号処理に関係する電力効率の良い符号拡張回路であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するための符号適用回路系、ここで、それぞれの前記部分積行はブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するための乗算回路系； 前記ブース乗算ツリーに符号拡張ビットを生成することによって前記符号ビットの信号値を分解するための符号値解析回路系、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記乗算回路系は、さらに前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために、前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットに前記キャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するためである、
を具備する、符号拡張回路。
【請求項８】
９部分積行を６部分積行に削減するための第１の複数の加算器回路；
前記６部分積行を４部分積行に削減するための第２の複数の加算器回路行；
前記４部分積行を、使用するサム行とキャリー行に削減するための圧縮器回路；及び 符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列に符号ビットを加えるためのエンコーディング回路系、
をさらに具備する、請求項７のシステム。
【請求項９】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるためのエンコーディング回路系をさらに具備する、請求項７のシステム。
【請求項１０】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ前記３２番目の列よりも大きい列を変更するためのエンコーディング回路系をさらに具備する、請求項７のシステム。
【請求項１１】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの前記３２番目とそれより大きい列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するための削減回路系をさらに具備する、請求項７のシステム。
【請求項１２】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するための乗算回路系をさらに具備する、請求項７のシステム。
【請求項１３】
個人向け電子デバイスをサポートする演算のためのディジタル信号プロセッサであって、ディジタル信号処理はブース乗算処理のために電力効率の良い符号拡張を実行するための手段を具備し、前記処理は：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するための手段、ここで、前記部分積行のそれぞれはブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のための前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するための手段；
前記ブース乗算ツリーにおいて符号拡張ビットを生成することによって前記符号ビットの信号値を分解するための手段、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために、前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するための手段、
を具備する処理である、ディジタル信号プロセッサ。
【請求項１４】
前記複数の部分積を削減するための手段をさらに具備し、前記部分積を削減する手段は：
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減するための手段； 第２の複数の加算器行を使用して前記６部分積行を４部分積行に削減するための手段； 圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減するための手段；そしてさらに
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列に符号ビットを加えるための手段、
を具備する前記手段である、請求項１３のディジタル信号プロセッサ。
【請求項１５】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１６】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１７】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目及びそれより大きい列から１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１８】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するためのステップをさらに具備する、請求項１３のディジタル信号プロセッサ。
【請求項１９】
ブース乗算処理のための電力効率の良い符号拡張方法を実行するためにその中に組み込まれたコンピュータ読取り可能なプログラム・コード手段を有するコンピュータ使用可能な媒体であって：
複数の部分積行を備えるブース乗算ツリーに符号ビットを適用するためのコンピュータ読取り可能なプログラム・コード手段、ここで、前記部分積行のそれぞれはブース乗算処理の部分積を備え、前記ブース乗算処理の事象における使用のために前記符号ビットは符号拡張ステップを必要とする；
事前に決められた部分積行の正しい符号を保存するために符号ビットを使用して前記ブース乗算ツリーの前記事前に決められた部分積行を１要素拡張するためのコンピュータ読取り可能なプログラム・コード手段；
前記ブース乗算ツリーに符号拡張ビットを生成することによって前記符号ビットの信号値を分解するためのコンピュータ読取り可能なプログラム・コード手段、ここで、前記符号拡張ビットはキャリー−アウト列中に置かれて前記ブース乗算処理の前記積を拡張する；及び
前記符号を有する最終積のサム成分を効果的に拡張しそして前記最終積のキャリー成分をゼロ−拡張するために前記ブース乗算ツリーの少なくとも事前に決められた列への前記符号ビットにキャリー−アウト値を加えることによって前記ブース乗算ツリーから前記最終積を形成するためのコンピュータ読取り可能なプログラム・コード手段、
を具備するコンピュータ使用可能な媒体。
【請求項２０】
第１の複数の加算器回路を使用して９部分積行を６部分積行に削減するためのコンピュータ読取り可能なプログラム・コード手段；
第２の複数の加算器行を使用して前記６部分積行を４部分積行に削減するためのコンピュータ読取り可能なプログラム・コード手段；
圧縮器回路を使用して前記４部分積行をサム行とキャリー行に削減するためのコンピュータ読取り可能なプログラム・コード手段；及び
符号なし乗算のための符号拡張を実行するために１６×１６前記ブース乗算ツリーの３２番目の列へ符号ビットを加えるためのコンピュータ読取り可能なプログラム・コード手段、
をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２１】
前記ブース乗算ツリーの最終部分積行中にビット、ｓ８、として前記符号ビットを加えるためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２２】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記複数の部分積の削減の最終ステージにおいてのみ又はその後でのみ３２番目の列よりも大きい列を変更するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２３】
前記ブース乗算ツリーは、１６×１６基数−４ブース乗算ツリーを備え、そして前記１６×１６基数−４ブース乗算ツリーの３２番目及びそれより大きい列からの１要素拡張にキャリー−アウト値を加えることによって前記ブース乗算ツリーから最終積を形成するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【請求項２４】
ＭＡＣ演算のあいだに６４−ビット値累算の一部として前記ブース乗算処理を実行するためのコンピュータ読取り可能なプログラム・コード手段をさらに具備する、請求項１９のコンピュータ使用可能な媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−２２２０２４（Ｐ２０１１−２２２０２４Ａ）
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−９２１６１（Ｐ２０１１−９２１６１）
【出願日】平成２３年４月１８日（２０１１．４．１８）
【分割の表示】特願２００８−５５５４９５（Ｐ２００８−５５５４９５）の分割
【原出願日】平成１９年２月１５日（２００７．２．１５）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【出願番号】特願２０１１−９２１６１（Ｐ２０１１−９２１６１）
【出願日】平成２３年４月１８日（２０１１．４．１８）
【分割の表示】特願２００８−５５５４９５（Ｐ２００８−５５５４９５）の分割
【原出願日】平成１９年２月１５日（２００７．２．１５）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
[ Back to top ]