(57)【要約】【課題】  より速い乗算演算を有する非同期式符号付き乗算器を提供すること。【解決手段】  Ｎ個の部分積生成器（ＰＰＧ）と、演算モジュールと、先行ゼロビット検出器とを含む非同期式符号付き乗算器を提供する。部分積生成器は、乗数及び被乗数に応じて複数の部分積値を生成する。演算モジュールは（Ｎ−１）番目のＰＰＧから最初のＰＰＧまでの出力に対して合計演算を実行し、Ｎ番目のＰＰＧからの出力は最後に加算される。さらに、先行ゼロビット検出器が乗数及び被乗数において先行ゼロビットを検出すると、「０」のビットに対応する部分積出力は直接ゼロに設定される。【選択図】  図５
2007156620.tif 000002
【特許請求の範囲】
【請求項１】
乗数及び被乗数に対して符号付き乗算演算を実行するための非同期式符号付き乗算器であって、上記乗数及び被乗数は各々Ｎビット及びＭビットを有し、Ｎ及びＭはゼロより大きい正の整数であり、上記乗数及び被乗数は符号の付いた数であり、
上記乗数及び被乗数の各々に応じて部分積結果を生成するために使用されるＮ個の部分積生成器（ＰＰＧ）を備え、上記部分積結果はＤｉで示され、Ｄｉはｉ番目のＰＰＧにおいて、上記被乗数のあらゆるビット数と上記乗数のｉ番目のビット数とのタイミングを合わせることによる部分積結果を表示し、ｉは、Ｎ以下かつ１以上の整数であり、各部分積結果はＭ個の部分積値を含み、
上記ＰＰＧからの出力を受信しかつ下記数１の演算の実行に使用されて第１の演算結果を得る演算モジュールを備え、
【数１】
2007156620.tif 000004
上記第１の演算結果には上記演算モジュールによりＤNが加算されて第２の演算結果が取得され、
上記演算モジュールへ結合される先行ゼロビット検出器を備え、上記先行ゼロビット検出器が上記乗数又は被乗数の何れかにおいて先行ゼロビットを検出すると、上記検出された「０」ビットに対応する全ての部分積値出力はゼロビットに対する演算なしに「０」へ設定される非同期式符号付き乗算器。
【請求項２】
上記第２の演算結果をチェックするために上記演算モジュールへ結合される完了検出器をさらに備える請求項１記載の非同期式符号付き乗算器。
【請求項３】
上記演算モジュールはさらに、
（Ｎ−１）番目のＰＰＧ、（Ｎ−２）番目のＰＰＧから最初のＰＰＧまでの出力を逐次累積するために各々対応する部分積値を受信する複数の第１の加算器と、
各々が第１の入力端、第２の入力端及び出力端を有する複数のマルチプレクサとを備え、各マルチプレクサの上記第１の入力端は各々対応する第１の加算器からの出力を受信し、各マルチプレクサの上記第２の入力端は定数「０」を受信し、上記マルチプレクサは上記先行ゼロビット検出器の出力に従ってその第１の入力端または第２の入力端を選択してその出力端へ結合し、上記マルチプレクサはその第１の入力端または第２の入力端のデータを次の段のＰＰＧによって結合される第１の加算器へ送信し、
各々上記マルチプレクサの一部からの出力を受信する複数の第２の加算器と、
Ｎ番目のＰＰＧ及び第１のＰＰＧからの出力を受信する複数の第３の加算器と、
上記第１のＰＰＧからの出力に関連する演算を処理するマルチプレクサからの出力を受信して第２の演算値を計算するための最終段加算器と、を備える請求項１記載の非同期式符号付き乗算器。
【請求項４】
乗数及び被乗数に対して符号付き乗算演算を実行することに適する非同期式符号付き乗算のためのアルゴリズムであって、上記乗数はＮビットの数であり、Ｎはゼロより大きい正の整数であり、上記乗数及び被乗数の最上位ビットは符号ビットであり、
（Ｎ−１）番目のビット数から最初のビット数へと逐次複数のビット数により上記被乗数のタイミングを合わせて複数の第１の部分積値を取得するためのステップと、
上記第１の部分積値を合計して第１の演算結果を取得するためのステップと、
上記乗数のＮ番目のビット数により上記被乗数のタイミングを合わせて複数の第２の部分積値を取得するためのステップと、
上記第２の部分積値を上記第１の合計値に加えて第２の演算結果を取得するためのステップと、
上記乗数または被乗数において先行ゼロビットが検出されれば、「０」のビットに対して演算を実行することなく「０」のビットに関連する部分積値を直接ゼロに設定するステップとを含むアルゴリズム。
【請求項５】
上記乗数の最上位ビットと上記被乗数の最上位ビットとの間の部分積値を除いて、上記乗数の最上位ビットに関連する、または上記被乗数の最上位ビットに関連する部分積値を位相反転する演算をさらに含む請求項４記載の非同期式符号付き乗算器のためのアルゴリズム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は乗算器とそのアルゴリズムに関し、特に非同期式符号付き乗算器とそのアルゴリズムに関する。
【背景技術】
【０００２】
乗算器は、マイクロプロセッサ、データ信号処理、離散コサイン変換等々といった多くのアプリケーションにおいて重要な役割を果たしている。実際、乗算器は計算チップにおける大部分の演算時間を消費する。従って、乗算器の実行時間はチップの全体効率を決定する。今日まで、同期回路設計における幾つかのアプローチが提供され、非同期回路設計におけるアプローチもある程度提案されている。概して、非同期的方法は同期回路を凌ぐ、低い電力消費、少ない平均計算時間、異なる製造プロセス及び環境への適合可能性、等の幾つかの優位点を有する。特に、これらの優位点は、ある種のＶＬＳＩ（超大規模集積回路）が遭遇する問題点を解決する上で極めて重要である。
【０００３】
今日の乗算器のタイプは、右から左（Ｒ−Ｌ）のアレイ乗算器、左から右（Ｌ−Ｒ）のアレイ乗算器、区分アレイ乗算器及び多重アレイ乗算器に分けることができる。
【０００４】
図１Ａ及び図１Ｂは各々、順次桁上げ式（ｒｉｐｐｌｅ−ｃａｒｒｙ）のアレイ乗算器１００と桁上げ保存式（ｃａｒｒｙ−ｓａｖｅ）のアレイ乗算器１２０とを略示したものであり、これらのアレイ乗算器は双方とも８×８の左から右（Ｌ−Ｒ）のアーキテクチャを有する。図１Ａ及び図１Ｂを参照すると、Ｌ−Ｒ乗算器１００または１２０は主として、部分積生成器（ＰＰＧ）１０２と、Ｌ−Ｒ加算器アレイ１０４と、最終段加算器１０８とを含む。Ｒ−Ｌ乗算器とＬ−Ｒ乗算器との相違は、加算器アレイ１０４及び最終段加算器１０８にある。Ｒ−Ｌ加算器アレイでは、合計演算は最下位ビットの部分積（ＬＳＢＰＰ）で開始され、次に合計及び桁上げが一段ずつ次の上位ビットへ広がって最終的に最終段加算器で最上位ビットの部分積（ＭＳＢＰＰ）が加算される。反対に、Ｌ−Ｒ加算器アレイでは、合計演算は最上位ビットの部分積（ＭＳＢＰＰ）で開始され、結果は一段ずつ次の下位ビットへ広がって最終的に最終段加算器で最下位ビットの部分積（ＬＳＢＰＰ）が加算される。
【０００５】
乗数または被乗数何れかの１ビットは０であることは周知であり、対応する部分積は「０」になるはずである。しかしながら従来型の乗算器の場合、「０」ビットに対しても部分積演算はやはり冗長的に実行され、時間を無駄にしている。加えて演算要素に関しては、その一般的なビットの長さがシステムにおける設計されたビット長さより遙かに短い。即ち、高位ビットの値はしばしば「０」であり、これらの０に対する計算は単に多大な時間の無駄である。
【０００６】
図２は、乗数及び被乗数のヒット数と有効ビット長さとの関係の統計分布を示すグラフである。図２を参照すると、このグラフは６，７４６，８５３個のデータからの統計であり、１つのデータの最大有効ビットは一般に１６ビットである。言い替えれば、１６ビットを超えるビット値はほぼ全て「０」である。従って、この統計結果は、乗算演算を高速化するかなりの余地があることを立証している。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記記述を基礎として、本発明の目的は、より速い乗算演算を有する非同期式符号付き乗算器を提供することにある。
【０００８】
本発明の別の目的は、符号付きデータを計算するための非同期式符号付き乗算のアルゴリズムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明によって提供される非同期式符号付き乗算器は、乗数及び被乗数に対する符号付きの乗算演算に適し、上記乗数及び被乗数は各々Ｎビット及びＭビットを有する。Ｎ及びＭはゼロより大きい正の整数であり、乗数、被乗数及び積は全て２の補数である。本発明の非同期式符号付き乗算器は、乗数及び被乗数による部分積結果を生成するために使用されるＮ個の部分積生成器（ＰＰＧ）を含み、上記部分積はＤｉで示され、Ｄｉはｉ番目のＰＰＧにおける、被乗数のあらゆるビット数と乗数のｉ番目のビット数とのタイミングを合わせることによって得られる部分積を表示する。さらにｉは、Ｎ以下かつ１以上の整数である。各部分積結果はＭ個の部分積を含み、部分積生成器からの全出力は演算モジュールへ送られ、下記［数１］の計算が実行される。
【数１】
2007156620.tif 000003
上記［数１］の計算から、第１の演算結果が得られる。その後、演算モジュールは第２の演算結果を得るために第１の演算結果にＤNを加算する。演算モジュールはさらに先行ゼロビット検出器へ結合され、これは乗数及び被乗数をビット順に、ＭＳＢ（最上位ビット）からＬＳＢ（最下位ビット）へとチェックする。チェックの間、最初の「１」ビットに先行する「０」ビットは何れも空ビットとしてカウントされ、対応する部分積値は「０」で出力される。最初の「１」ビットからＬＳＢまでの全てのビットは、有効ビットと呼ばれる。
【００１０】
本発明の上記実施形態では、非同期式符号付き乗算器はさらに、上述の第２の演算結果を決定するための演算モジュールに結合される完了検出器を含む。
【００１１】
一方で本発明は、乗数及び被乗数に対する符号付き乗算演算に適する非同期式符号付き乗算器のためのアルゴリズムを提供し、この場合の乗数及び被乗数は各々Ｎビット及びＭビットを有する。Ｎ及びＭは、ゼロより大きい正の整数である。乗数または被乗数の最高位ビットは符号ビットである。本発明によれば、複数の第１の部分積値を得るために、被乗数は乗数の各ビット数と逐次ｉ番目のビット数から最初のビット数へタイミングを合わせる。その後、取得した第１の部分積値は合計され、第１の演算結果が得られる。さらに被乗数は、複数の第２の部分積値を得るために乗数のＮ番目のビット数とタイミングを合わされる。次に第１の演算結果は第２の部分積値によって加算され、第２の演算結果が得られる。乗数及び被乗数における任意の「０」ビットに関しては、「０」ビットに関連する演算が免除され、関連する部分積値は直接「０」に設定される。
【発明の効果】
【００１２】
乗数の最上位ビットに関連する部分積値は最終合計の加算を行うための全合計演算の終わりにスケジューリングされることから、本発明は、符号の付いた数に対する演算を実行して計算時間を節約することができる。
【発明を実施するための最良の形態】
【００１３】
図３は、５×５の左から右の符号の付いた数の正規乗算演算を示す図である。Ｍ１及びＭ２が被乗数及び乗数を示す図３を参照すると、乗数Ｍ２の例えばｘ４、ｘ３及びｘ２である上位ビットは「０」であることが想定され、よってこの「０」ビットに関連する部分積値は被乗数Ｍ１の値に関わらず「０」になる。常識的に言って、「０」ビットに関連する演算は時間を節約するために免除され、関連の部分積値は直接「０」に設定される。
【００１４】
しかしながら被乗数Ｍ１及び乗数Ｍ２の符号の付いた数の場合、状況は上述のものとは異なり、被乗数Ｍ１及び乗数Ｍ２の最上位ビットｙ４及びｘ４は符号ビットである。図３からは、符号の付いた数に対する乗算演算の場合、被乗数Ｍ１及び乗数Ｍ２の最上位ビット双方に関連する部分積（ｙ４ｘ４）を除く被乗数Ｍ１／乗数Ｍ２の一方の最上位ビットに関連する残りの部分積は、破線で囲まれた部分に示すように位相を反転される必要のあることが分かる。故に、もとの「０」部分積は、位相反転の後「１」になる。
【００１５】
さらに、通常、有効ビット長さは長くないため、第１の行の部分積値、例えば図３におけるｙ４ｘ４、（ｙ３ｘ４）’、（ｙ２ｘ４）’、（ｙ１ｘ４）’及び（ｙ０ｘ４）’が「１」になる確率は極めて高く、従って後続の部分値に対する加算演算は次の部分値が「０」であるか否かに関わらず連続して実行されることが分かる。これは、多大な時間を不必要に浪費する。
【００１６】
上述の問題点を解決するために、本発明は、例えば図４に示すような５×５のＬ−Ｒ符号付き乗算アルゴリズムを提供する。逆転の発想から、本発明は、図３におけるもとの第１の行の部分積値を最終段に配置替えをして計算する。その結果、図３におけるもとの第２の行の部分積値、即ち（ｙ４ｘ３）’、ｙ３ｘ３、ｙ２ｘ３、ｙ１ｘ３及びｙ０ｘ３は第１の行へ進められて計算される。この新規再配列の下では、被乗数Ｍ１または乗数Ｍ２の上位ビットが「０」として発見されると、関連する部分積値は計算なしにゼロとしてフラグを立てられる可能性がある。位相反転の後に最上位ビットに関連する幾つかの部分積値が「１」になるとしても、反転された部分積値は既に計算の終わりにスケジューリングされているので実際の計算時間は依然として節約される。
【００１７】
図５は、本発明の一実施形態による非同期式符号付き乗算器の略回路図である。図５を参照すると、本実施形態によって提供される乗算器５００は８×８乗算器であり、これは、本乗算器が符号の付いた８ビットの乗数と符号の付いた８ビットの被乗数とに対する乗算演算のために機能し得ることを意味する。但し、本実施形態の８×８乗算器５００は本発明を説明するための単なる例示であり、本発明の範囲を限定するものではない。先に述べたように、本発明が提供する非同期式符号付き乗算器は、Ｎビットの乗数及びＭビットの被乗数に対する乗算演算を処理するように設計される。この場合のＮ及びＭは、０より大きい正の整数である。実際、当業者にとって、本発明の原理を基礎として本発明の精神を逸脱することなく、他の仕様によって所望される乗算器を構築することは容易である。
【００１８】
乗算器５００は、複数の部分積生成器（ＰＰＧ）Ｃ１乃至Ｃ８を含む。本発明においては、ＰＰＧの番号は乗算器のビット数と同じもので指定される。乗算器５００はさらに、演算モジュール５１０と、先行ゼロビット検出器５４０と、完了検出器５５０とを含む。
【００１９】
図５を参照すると、ＰＰＧ  Ｃ１〜Ｃ８は乗数及び被乗数に応じて部分積結果を生成し、ｉ番目のＰＰＧにより生成される部分積結果はＤｉで表示される。下付き文字ｉは、被乗数の全ビット及び乗数のｉ番目のビットに対するｉ番目のＰＰＧ装置の乗算を表す。例えば、Ｄ３は、被乗数の全ビットが乗数の第３のビットで乗じられた、第３のＰＰＧ  Ｃ３からの部分積結果を意味する。各部分積結果は複数の部分積値を有し、ＰＰＧにおける各部分積値はシンボル「・」でマーキングされている。
【００２０】
演算モジュール５１０は、加算器モジュール５１２、５１４、５１６、５１８及び５２０を含む。各加算器モジュールは、複数の第１の加算器と複数のマルチプレクサ、例えば第１の加算器５２８とマルチプレクサ５３０とを含む。この場合、各第１の加算器は対応するＰＰＧからの出力、即ち対応する部分積値を受信する。例えば、第１の加算器５２８はＰＰＧ  Ｃ１から第１の部分積値を受信する。加えて、各マルチプレクサは第１の入力端と第２の入力端とを有する。この場合、マルチプレクサの第１の入力端は対応する加算器からの出力を受信するが、第２の入力端は（図６に示すように）定数「０」を受信する。各マルチプレクサからの出力は、次の段の加算器モジュールへ送られる。例えば、マルチプレクサ５３０の入力端のうちの１つは第１の加算器５２８からの出力を受信するが、その別の入力端は定数「０」を受信し、第１の加算器５２８からの出力は次の段の加算器モジュール５１６における第１の加算器５３２へ送られる。
【００２１】
図６は、図５における演算モジュールの第１の加算器とマルチプレクサとの相互接続を示す部分拡大図である。図６を参照して第１の加算器５２８を例にとれば、本実施形態における第１の加算器５２８は、各々最終段の演算モジュールからの部分積値及び／または出力を受信するための３つの入力端Ａ、Ｂ及びＣを有する。第１の加算器５２８は合計出力端と桁上げ出力端とを有し、上記合計出力端は入力端Ａ、Ｂ及びＣによって受信される値の合計を出力するために使用される。さらに、第１の加算器５２８の桁上げ生成に伴って、桁上げの値が桁上げ出力端から出力される。
【００２２】
マルチプレクサ５３０における入力端の１つ及びマルチプレクサ５３１における入力端の１つは各々、第１の加算器５２８の合計出力端からの出力及び桁上げ出力端からの出力を受信する。マルチプレクサ５３０及び５３１の別の端は、定数「０」を受信する。マルチプレクサ５３０及び５３１は各々、もう１つの端である選択端Ｚを有する。選択端Ｚは、例えば図５における先行ゼロビット検出器５４０へ結合される。このようにして、先行ゼロビット検出器５４０はマルチプレクサ５３１からの出力を制御しかつ切り替えることができる。
【００２３】
再度図５を参照すると、演算モジュール５１０はさらに、第２の加算器モジュール５２２と、第３の加算器モジュール５２４と、最終段の加算器５２６とを含む。この場合、第２の加算器モジュール５２２は、加算器モジュール５１２、５１４、５１６、５１８及び５２０内のマルチプレクサの一部からの出力を受信するための複数の第２の加算器を含む。本発明においては、第２の加算器モジュール５２２及び部分積生成器（ＰＰＧ）Ｃ１乃至Ｃ７は７つの出力、即ちＰＰＧ  Ｃ１乃至ＰＰＧ  Ｃ７からの（Ｎ−１）個の出力に対して前記［数１］の計算を実行し、第１の演算結果を得る。但し、本実施形態の場合、前記［数１］のＮは８である。
【００２４】
加算器モジュール５１２、５１４、５１６、５１８、５２０及び第２の加算器モジュール５２２による公式（１）の計算の実行に伴って、先行ゼロビット検出器５４０が乗数または被乗数の何れかに先行ゼロビットを発見すると、部分積の全ての関連出力は「０」に設定される。本実施形態では、先行ゼロビット検出器５４０が乗数または被乗数の何れかに先行ゼロビットを検出すると、制御信号が生成されてマルチプレクサの選択端Ｚへ送られ、よってマルチプレクサは第１の加算器による演算なしに直接定数「０」を出力する。
【００２５】
第３の加算器モジュール５２４もまた複数の第３の加算器を含み、これらは各々、８番目の、即ちＮ番目のＰＰＧ  Ｃ８によって生成される部分積値を受信する。第３の加算器モジュール５２４及び最終段の加算器５２６はＤ8を第１の演算値へ加算し、即ち第１の演算値をＰＰＧ  Ｃ８によって生成される部分積結果へ加算して第２の演算値を得る。この第２の演算値は、乗数及び被乗数に対する乗算演算による単なる最終積値である。
【００２６】
本実施形態では、最終段の加算器５２６からの出力は完了検出器５５０へ送信され、完了検出器５５０を使用して第２の演算値の検出を完了させる必要がある。
【産業上の利用可能性】
【００２７】
上述の説明から、本発明は、乗数におけるＮ番目のビットの部分積を最終段における計算のために戻すことが分かり、よって本発明は、符号付き乗算の実行に際しても依然として演算時間を節約することができる。
【００２８】
当業者には、本発明の範囲または精神を逸脱することなく本発明の構成に様々な修正及び変更を実行可能であることが明らかであろう。上記内容に鑑みれば、上記明細及び例は単なる例示として考慮されるべきものであり、本発明の真の範囲及び精神は添付の請求の範囲及びこれらに相当するものにより指示されている。
【００２９】
添付の図面は本発明をさらに理解するために包含されるものであり、本明細書の一部に組み込まれかつ上記一部を構成する。諸図面は本発明の実施形態を例示し、明細書本文と共に本発明の原理を説明する働きをする。
【図面の簡単な説明】
【００３０】
【図１Ａ】順次桁上げ式アレイ乗算器を略示するものであり、アレイ乗算器は８×８の左から右（Ｌ−Ｒ）のアーキテクチャを有する。
【図１Ｂ】桁上げ保存式アレイ乗算器を略示するものであり、アレイ乗算器は８×８の左から右（Ｌ−Ｒ）のアーキテクチャを有する。
【図２】乗数及び被乗数のヒット数と有効ビット長さとの関係の統計分布を示すグラフである。
【図３】５×５の左から右の符号の付いた数の正規乗算演算を示す図である。
【図４】本発明の一実施形態による５×５の左から右の符号の付いた数の正規乗算演算を示す図である。
【図５】本発明の一実施形態による非同期式符号付き乗算器の略回路図である。
【図６】図５における演算モジュールの第１の加算器とマルチプレクサとの相互接続を示す部分拡大図である。
【符号の説明】
【００３１】
１００ アレイ乗算器
１０４ Ｌ−Ｒ加算器アレイ
１０８ 最終段加算器
１２０ アレイ乗算器
５００ 乗算器
５１０ 演算モジュール
５１２ 加算器モジュール
５１６ 加算器モジュール
５２２ 加算器モジュール
５２４ 加算器モジュール
５２６ 加算器
５２８ 加算器
５３０ マルチプレクサ
５３１ マルチプレクサ
５３２ 加算器
５４０ 先行ゼロビット検出器
５５０ 完了検出器
【図１Ａ】
2007156620.tif 000005
【図１Ｂ】
2007156620.tif 000006
【図２】
2007156620.tif 000007
【図３】
2007156620.tif 000008
【図４】
2007156620.tif 000009
【図５】
2007156620.tif 000010
【図６】
2007156620.tif 000011