JPH10161853A - デジタル乗算ユニットおよびデジタル乗算方法 - Google Patents
デジタル乗算ユニットおよびデジタル乗算方法Info
- Publication number
- JPH10161853A JPH10161853A JP9326549A JP32654997A JPH10161853A JP H10161853 A JPH10161853 A JP H10161853A JP 9326549 A JP9326549 A JP 9326549A JP 32654997 A JP32654997 A JP 32654997A JP H10161853 A JPH10161853 A JP H10161853A
- Authority
- JP
- Japan
- Prior art keywords
- add
- component
- multiplicand
- unit
- multiplier
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/523—Multiplying only
- G06F7/527—Multiplying only in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/523—Multiplying only
- G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel
- G06F7/5324—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
- G06F2207/3804—Details
- G06F2207/386—Special constructional features
- G06F2207/388—Skewing
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【課題】 デジタル乗算ユニットの部品の利用率を高め
ること 【解決手段】 被乗数のディジットにより部分積をグル
ープ分けし、ディジットの順によって決定される遅延部
品を通して、関連する加算部品の第１ターミナルに各デ
ィジットを印加する。各加算部品からの出力信号が複数
の遅延部品を通過するようにし、同じ加算部品の第２入
力ターミナルに印加する。このようにして部分積ＡP ＊
Ｂq をアセンブルし、単一周期で合計ユニットへ部分積
（Ａ0 ＋....ＡM ）＊Ｂq ＝Ａ＊Ｂq を印加できる。
ること 【解決手段】 被乗数のディジットにより部分積をグル
ープ分けし、ディジットの順によって決定される遅延部
品を通して、関連する加算部品の第１ターミナルに各デ
ィジットを印加する。各加算部品からの出力信号が複数
の遅延部品を通過するようにし、同じ加算部品の第２入
力ターミナルに印加する。このようにして部分積ＡP ＊
Ｂq をアセンブルし、単一周期で合計ユニットへ部分積
（Ａ0 ＋....ＡM ）＊Ｂq ＝Ａ＊Ｂq を印加できる。
Description
【０００１】
【発明の属する技術分野】本発明はデータ処理システム
の部品に関し、より詳細にはデータ処理システムの乗算
部品に関する。このデータ処理システムの乗算部品はデ
ータビットによって示される被乗数にデータビットで示
される乗数をかけるようになっている。
の部品に関し、より詳細にはデータ処理システムの乗算
部品に関する。このデータ処理システムの乗算部品はデ
ータビットによって示される被乗数にデータビットで示
される乗数をかけるようになっている。
【０００２】
【従来技術】従来技術では、乗算ユニット、例えばブー
ス乗算ユニットまたは並列乗算ユニットは一般に部品の
利用率が低い。データが乗算ユニットを通過する際にリ
ップル動作する時間がある結果、このように利用率が低
くなっている。上記乗算器の構造のいずれのタイプも、
このリップル時間は乗算ユニットの加算ステージでデー
タを処理するのに時間がかかることから生じるものであ
る。過去においてこのリップル時間を短縮するためにキ
ャリールックアヘッド（桁上げ先見）回路が設けられ
た。しかしながらこのようなキャリールックアヘッド回
路を設けることにより乗算ユニットに必要な部品の複雑
性およびその数がかなり増すこととなった。
ス乗算ユニットまたは並列乗算ユニットは一般に部品の
利用率が低い。データが乗算ユニットを通過する際にリ
ップル動作する時間がある結果、このように利用率が低
くなっている。上記乗算器の構造のいずれのタイプも、
このリップル時間は乗算ユニットの加算ステージでデー
タを処理するのに時間がかかることから生じるものであ
る。過去においてこのリップル時間を短縮するためにキ
ャリールックアヘッド（桁上げ先見）回路が設けられ
た。しかしながらこのようなキャリールックアヘッド回
路を設けることにより乗算ユニットに必要な部品の複雑
性およびその数がかなり増すこととなった。
【０００３】図１を参照すると、二進の被乗数Ａに二進
の乗数Ｂをかけるための乗算ユニットは一般に３つのス
テージに分割できる。この第１ステージでは乗算方法の
実施に使用される装置を簡略化するためレジスタ１０に
記憶された被乗数Ａをプリプロセッサステージ１１によ
って予め処理するようになっている。次にディジット生
成部品１３はレジスタ２０に記憶された乗数Ｂのｉ番目
のディジットを生成する。第２ステージすなわち乗算ス
テージ１２では積Ａ＊Ｂi が生成される。第３ステージ
すなわち加算ステージ１４ではＡ＊Ｂi の合計が生成さ
れ、この部分積はＳi 、すなわち乗算レジスタ２０内の
乗数ビットＢi の位置だけシフトされる。Ｂ＝ＳＵＭ
（ｉ）｛Ｂi ２Si｝であるので、これら３つのステージ
の演算により所望の結果が生成される。例えば簡単なシ
フトおよび加算乗算ユニットではプリプロセッサステー
ジ１１は作動しない。乗算ステージ１２はＡを１または
０のいずれかで乗算する。この二進ビットはＢのｉ番目
のディジットである。加算ステージ１４は積をＳi だけ
シフトし、すべての結果を加算する。
の乗数Ｂをかけるための乗算ユニットは一般に３つのス
テージに分割できる。この第１ステージでは乗算方法の
実施に使用される装置を簡略化するためレジスタ１０に
記憶された被乗数Ａをプリプロセッサステージ１１によ
って予め処理するようになっている。次にディジット生
成部品１３はレジスタ２０に記憶された乗数Ｂのｉ番目
のディジットを生成する。第２ステージすなわち乗算ス
テージ１２では積Ａ＊Ｂi が生成される。第３ステージ
すなわち加算ステージ１４ではＡ＊Ｂi の合計が生成さ
れ、この部分積はＳi 、すなわち乗算レジスタ２０内の
乗数ビットＢi の位置だけシフトされる。Ｂ＝ＳＵＭ
（ｉ）｛Ｂi ２Si｝であるので、これら３つのステージ
の演算により所望の結果が生成される。例えば簡単なシ
フトおよび加算乗算ユニットではプリプロセッサステー
ジ１１は作動しない。乗算ステージ１２はＡを１または
０のいずれかで乗算する。この二進ビットはＢのｉ番目
のディジットである。加算ステージ１４は積をＳi だけ
シフトし、すべての結果を加算する。
【０００４】
【発明が解決しようとする課題】この例ではほとんどの
複雑性は第３ステージすなわち合計ステージから生じる
ものである。乗算器のディジットは１または０のいずれ
かであるので、第２ステージすなわち乗算ステージは比
較的簡単となっている。第３ステージすなわち合計ステ
ージ１４では順次加算が行われ、加算値は１つのランニ
ング合計値に加算されるので、加算器の部品の利用率は
低くなっている。しかしながら多くの乗算ユニットの場
合、乗算演算を実行するのに部品をほとんど必要としな
い時は、乗算機能を実行するためにより長い時間が許容
される。
複雑性は第３ステージすなわち合計ステージから生じる
ものである。乗算器のディジットは１または０のいずれ
かであるので、第２ステージすなわち乗算ステージは比
較的簡単となっている。第３ステージすなわち合計ステ
ージ１４では順次加算が行われ、加算値は１つのランニ
ング合計値に加算されるので、加算器の部品の利用率は
低くなっている。しかしながら多くの乗算ユニットの場
合、乗算演算を実行するのに部品をほとんど必要としな
い時は、乗算機能を実行するためにより長い時間が許容
される。
【０００５】従って、乗算ユニットの部品の利用率を高
めるように講じた装置および関連する方法がこれまで望
まれていた。部品の利用率をより高くする結果、乗算方
法を実行するための処理サイクルをより多くできる。更
に第２ステージすなわち乗算ステージで部分積の加算の
多くを実行することにより、第３ステージすなわち合計
ステージでのキャリーリップル（桁上げ伝搬）の活動を
比較的少なくすることが望ましい。
めるように講じた装置および関連する方法がこれまで望
まれていた。部品の利用率をより高くする結果、乗算方
法を実行するための処理サイクルをより多くできる。更
に第２ステージすなわち乗算ステージで部分積の加算の
多くを実行することにより、第３ステージすなわち合計
ステージでのキャリーリップル（桁上げ伝搬）の活動を
比較的少なくすることが望ましい。
【０００６】
【課題を解決するための手段】代表的な構造と、プリプ
ロセッサステージと、乗算ステージと、合計ステージと
を有する、本発明に係わる乗算ユニットにより上記およ
びそれ以外の特徴が得られる。しかしながら本発明で
は、被乗数を記憶するためのレジスタはシフトレジスタ
となっている。乗算ステージはゲート部品を含み、この
ゲート部品はゲート部品の制御ターミナルに印加される
乗数の論理信号のサブディジットに応答して、適当にシ
フトされた被乗数を制御自在に通過させる。乗算ステー
ジは複数の加算部品も含み、各加算部品は被乗数のディ
ジット（一般に多数の論理信号となっている）（被乗数
のディジットは第１加算ユニットサイクル後はサイクル
に応じてシフトされる）に関連している。各加算ユニッ
トの第１入力ターミナルは直列に結合された遅延部品を
有し、遅延部品の数は関連する被乗数のディジットの位
置および乗数のディジット数に応じて決まる。各加算ユ
ニットの出力ターミナルは一連のＫ個（Ｋは乗数を区分
したディジット数であり、Ｐは被乗数を区分したディジ
ット数である）の遅延部品に印加され、Ｋ個の遅延部品
の出力は同じ加算部品の第２の入力ターミナルに結合さ
れる。このように部分積ＡP ＊ＢK を生成できる。ここ
でＡP およびＢK はそれぞれ被乗数のディジットおよび
乗数のディジットである。遅延部品に記憶される信号を
適当に選択することにより、連続するサイクルで乗算ユ
ニットの合計ステージへ部分積Ａ＊Ｂ0 からＡ＊ＢK-1
を印加できる。乗数の論理信号の数が被乗数を含む論理
信号の整数倍であるとき、乗算ユニットの実現は特に容
易となる。
ロセッサステージと、乗算ステージと、合計ステージと
を有する、本発明に係わる乗算ユニットにより上記およ
びそれ以外の特徴が得られる。しかしながら本発明で
は、被乗数を記憶するためのレジスタはシフトレジスタ
となっている。乗算ステージはゲート部品を含み、この
ゲート部品はゲート部品の制御ターミナルに印加される
乗数の論理信号のサブディジットに応答して、適当にシ
フトされた被乗数を制御自在に通過させる。乗算ステー
ジは複数の加算部品も含み、各加算部品は被乗数のディ
ジット（一般に多数の論理信号となっている）（被乗数
のディジットは第１加算ユニットサイクル後はサイクル
に応じてシフトされる）に関連している。各加算ユニッ
トの第１入力ターミナルは直列に結合された遅延部品を
有し、遅延部品の数は関連する被乗数のディジットの位
置および乗数のディジット数に応じて決まる。各加算ユ
ニットの出力ターミナルは一連のＫ個（Ｋは乗数を区分
したディジット数であり、Ｐは被乗数を区分したディジ
ット数である）の遅延部品に印加され、Ｋ個の遅延部品
の出力は同じ加算部品の第２の入力ターミナルに結合さ
れる。このように部分積ＡP ＊ＢK を生成できる。ここ
でＡP およびＢK はそれぞれ被乗数のディジットおよび
乗数のディジットである。遅延部品に記憶される信号を
適当に選択することにより、連続するサイクルで乗算ユ
ニットの合計ステージへ部分積Ａ＊Ｂ0 からＡ＊ＢK-1
を印加できる。乗数の論理信号の数が被乗数を含む論理
信号の整数倍であるとき、乗算ユニットの実現は特に容
易となる。
【０００７】添付図面と共に次の詳細な説明を読めば、
本発明の上記およびそれ以外の特徴について理解できよ
う。
本発明の上記およびそれ以外の特徴について理解できよ
う。
【０００８】
【発明の実施の形態】図１については従来技術に関連し
て説明した。
て説明した。
【０００９】図２を参照すると、ここには本発明に係わ
る乗算ユニットの第２ステージ、すなわち乗算ステージ
１２が示されている。被乗数ＡはＭ個の論理信号を有
し、Ｐ個のディジットすなわち論理信号のグループに区
分されている。これらディジットはＡ0 〜ＡP-1 と表示
されている。図１に示されるレジスタ１０には被乗数Ａ
が記憶される。レジスタ１０は付加部分２９を有するこ
とに留意されたい。乗算器の作動中に被乗数Ａはシフト
され、このシフトを可能にするためにより大きいレジス
タが必要である。被乗数Ａはゲート部品２１に印加され
る。被乗数Ａのゲート部品２１の通過はゲート部品２１
の制御ターミナルに乗数Ｂのどの論理ビットが加えられ
るかによって決定される。ゲート部品が被乗数Ａのビッ
トを通過させるか、または被乗数Ａのビットの反対の論
理ビットを通過させるかは、ゲート部品２１の制御ター
ミナルに加えられるビットの論理ステートに応じて決ま
る。乗数ＢはＫ個のディジット、すなわち論理信号のグ
ループ、例えばＢ0 〜ＢK-1に区分されている。ゲート
２１からの通過した信号は一連のＰ個の加算ユニット２
２に加えられる。ゲート部品２１によって通過される際
の被乗数Ａの最下位のディジットＡ0 は直接第１の（す
なわち最小位の）加算部品２２へ印加される。被乗数Ａ
の第２番目の最下位のディジットＡ1 はゲート部品２１
を通過する際に単一遅延部品２３を通って、第２の（す
なわち次に大きい位の）加算部品２２へ加えられる。ゲ
ート部品２１を通過するＡの別の各ディジットは別の遅
延部品２３を通って関連する（次第に位が増す）加算部
品２２へ加えられる。ゲート部品２１を通過する最上位
のディジットＡP-1 はＫ−１の遅延部品２３を通って関
連する加算ユニット２２へ印加される。加算ユニット２
２の出力信号の各々は直列に結合されたＫ個の遅延部品
２４へ加えられる。最終遅延部品２４の出力端は関連す
る加算部品２２の第２の入力ターミナルに結合されてい
る。被乗数Ａの最下位ディジットＡ0 に関連する加算ユ
ニット２２に結合されたＫ個の遅延部品のうちの最終部
品の入力ターミナルから最下位のディジットの出力信号
が取り出される。被乗数Ａの最下位の次の位のディジッ
トＡ1 を受ける加算部品２２に関連した最終の次の遅延
部品２４の入力端から、最下位の次の位のディジットが
得られる。こうして被乗数から最上位のビットＡP-1 を
受ける加算部品２２からは最上位の出力信号が得られ
る。加算部品２２から次に高い被乗数のディジットに関
連した加算部品のキャリーインターミナルへキャリーア
ウト（桁上げ）ビットが加えられる。乗数は長さがＮ個
のビットとなっている。被乗数がＭ個のビットを有し、
レジスタ１０（このレジスタ１０は長さがＭ＋Ｌビット
となっている）のＭ個の位の小さいビットに記憶される
場合、Ｍ＋Ｌ個のビットは（Ｍ＋Ｌ）／Ｐ個の論理ビッ
トによりＰ個のディジットに区分される。乗数は長さが
Ｎ個のビットであるので、このＮ個のビットはＮ／Ｋ＝
Ｌ個の論理ビットによりＫ個のディジットに区分され
る。乗算ステージにおける加算部品は長さがＭ＋Ｌ個の
ビットであり、各乗算ステージの加算部品２２は長さが
（Ｍ＋Ｌ）／Ｐ個の論理ビットである。各加算部品２２
は先の加算部品２２がその入力信号を受けた１サイク
ル、すなわち１クロック後でその入力信号を受ける。部
分積をスキューイング利用することから加算機部品２２
の長さが短くなっているので、クリティカルパスも短縮
されている。
る乗算ユニットの第２ステージ、すなわち乗算ステージ
１２が示されている。被乗数ＡはＭ個の論理信号を有
し、Ｐ個のディジットすなわち論理信号のグループに区
分されている。これらディジットはＡ0 〜ＡP-1 と表示
されている。図１に示されるレジスタ１０には被乗数Ａ
が記憶される。レジスタ１０は付加部分２９を有するこ
とに留意されたい。乗算器の作動中に被乗数Ａはシフト
され、このシフトを可能にするためにより大きいレジス
タが必要である。被乗数Ａはゲート部品２１に印加され
る。被乗数Ａのゲート部品２１の通過はゲート部品２１
の制御ターミナルに乗数Ｂのどの論理ビットが加えられ
るかによって決定される。ゲート部品が被乗数Ａのビッ
トを通過させるか、または被乗数Ａのビットの反対の論
理ビットを通過させるかは、ゲート部品２１の制御ター
ミナルに加えられるビットの論理ステートに応じて決ま
る。乗数ＢはＫ個のディジット、すなわち論理信号のグ
ループ、例えばＢ0 〜ＢK-1に区分されている。ゲート
２１からの通過した信号は一連のＰ個の加算ユニット２
２に加えられる。ゲート部品２１によって通過される際
の被乗数Ａの最下位のディジットＡ0 は直接第１の（す
なわち最小位の）加算部品２２へ印加される。被乗数Ａ
の第２番目の最下位のディジットＡ1 はゲート部品２１
を通過する際に単一遅延部品２３を通って、第２の（す
なわち次に大きい位の）加算部品２２へ加えられる。ゲ
ート部品２１を通過するＡの別の各ディジットは別の遅
延部品２３を通って関連する（次第に位が増す）加算部
品２２へ加えられる。ゲート部品２１を通過する最上位
のディジットＡP-1 はＫ−１の遅延部品２３を通って関
連する加算ユニット２２へ印加される。加算ユニット２
２の出力信号の各々は直列に結合されたＫ個の遅延部品
２４へ加えられる。最終遅延部品２４の出力端は関連す
る加算部品２２の第２の入力ターミナルに結合されてい
る。被乗数Ａの最下位ディジットＡ0 に関連する加算ユ
ニット２２に結合されたＫ個の遅延部品のうちの最終部
品の入力ターミナルから最下位のディジットの出力信号
が取り出される。被乗数Ａの最下位の次の位のディジッ
トＡ1 を受ける加算部品２２に関連した最終の次の遅延
部品２４の入力端から、最下位の次の位のディジットが
得られる。こうして被乗数から最上位のビットＡP-1 を
受ける加算部品２２からは最上位の出力信号が得られ
る。加算部品２２から次に高い被乗数のディジットに関
連した加算部品のキャリーインターミナルへキャリーア
ウト（桁上げ）ビットが加えられる。乗数は長さがＮ個
のビットとなっている。被乗数がＭ個のビットを有し、
レジスタ１０（このレジスタ１０は長さがＭ＋Ｌビット
となっている）のＭ個の位の小さいビットに記憶される
場合、Ｍ＋Ｌ個のビットは（Ｍ＋Ｌ）／Ｐ個の論理ビッ
トによりＰ個のディジットに区分される。乗数は長さが
Ｎ個のビットであるので、このＮ個のビットはＮ／Ｋ＝
Ｌ個の論理ビットによりＫ個のディジットに区分され
る。乗算ステージにおける加算部品は長さがＭ＋Ｌ個の
ビットであり、各乗算ステージの加算部品２２は長さが
（Ｍ＋Ｌ）／Ｐ個の論理ビットである。各加算部品２２
は先の加算部品２２がその入力信号を受けた１サイク
ル、すなわち１クロック後でその入力信号を受ける。部
分積をスキューイング利用することから加算機部品２２
の長さが短くなっているので、クリティカルパスも短縮
されている。
【００１０】図３Ａを参照する。ここには図２の乗算ユ
ニットの演算の１周期Ｔの後に、被乗数からの最下位デ
ィジットを受ける加算部品２２に関連した遅延部品２
３、２４の内容および被乗数からの最下位の次の位のデ
ィジットを受ける加算ユニットに関連した遅延部品２３
および２４の内容が示されている。図３Ｂには１周期Ｔ
の５倍の時間の後に同じ遅延部品２３および２４の内容
が示されており、被乗数は４つのディジットに区分され
ている。
ニットの演算の１周期Ｔの後に、被乗数からの最下位デ
ィジットを受ける加算部品２２に関連した遅延部品２
３、２４の内容および被乗数からの最下位の次の位のデ
ィジットを受ける加算ユニットに関連した遅延部品２３
および２４の内容が示されている。図３Ｂには１周期Ｔ
の５倍の時間の後に同じ遅延部品２３および２４の内容
が示されており、被乗数は４つのディジットに区分され
ている。
【００１１】図４を参照すると、ここには本発明により
加算ステージ１４に印加される信号が示されている。Ｑ
＝（Ｎ＋Ｋ−１）のサイクルまたは周期の後で乗算ユニ
ット１２の出力はＡ＊Ｂ0 となる。次の周期で、すなわ
ち（Ｎ＋Ｋ）サイクルで、乗算ユニットの出力はＡ＊Ｂ
1 となる。次の２周期の間で乗算ユニットの出力はＡ＊
Ｂ2 となり、Ａ＊Ｂ3 が得られる。これら部分積は合計
ステージ１４で順に加算される。
加算ステージ１４に印加される信号が示されている。Ｑ
＝（Ｎ＋Ｋ−１）のサイクルまたは周期の後で乗算ユニ
ット１２の出力はＡ＊Ｂ0 となる。次の周期で、すなわ
ち（Ｎ＋Ｋ）サイクルで、乗算ユニットの出力はＡ＊Ｂ
1 となる。次の２周期の間で乗算ユニットの出力はＡ＊
Ｂ2 となり、Ａ＊Ｂ3 が得られる。これら部分積は合計
ステージ１４で順に加算される。
【００１２】図５を参照すると、ここには乗算ステージ
１２からの部分積に対する出力論理信号が示されてい
る。Ｍは乗数の各ディジットの論理信号の数であるが、
他方Ｌは被乗数のディジットに対する論理信号の数であ
る。加算ステージ１４へ印加すべき乗数ステージ１２か
らの部分積は幅がＬ＋Ｍ個のビットとなっている。乗算
ユニットは遅延部品２３から得られるスキューイングに
より、連続するクロックサイクルでＫ個の部分積の各々
が利用できるように構成されている。Ｋ個の部分積の各
々は乗算ステージ１２からの先の部分積に対し、Ｌ個の
ビット位置だけシフトされる。
１２からの部分積に対する出力論理信号が示されてい
る。Ｍは乗数の各ディジットの論理信号の数であるが、
他方Ｌは被乗数のディジットに対する論理信号の数であ
る。加算ステージ１４へ印加すべき乗数ステージ１２か
らの部分積は幅がＬ＋Ｍ個のビットとなっている。乗算
ユニットは遅延部品２３から得られるスキューイングに
より、連続するクロックサイクルでＫ個の部分積の各々
が利用できるように構成されている。Ｋ個の部分積の各
々は乗算ステージ１２からの先の部分積に対し、Ｌ個の
ビット位置だけシフトされる。
【００１３】図６を参照すると、ここには乗数Ｂが被乗
数Ａの倍数Ｒ（例えば４）となっている場合に、本発明
を実施した例が示されている。この構造は、図２の構造
と類似している。しかしながら最終遅延部品２４の１つ
前の入力端から乗算ステージからの最下位ディジットに
対する出力を得ている。次の２つのディジットの双方は
最終遅延ライン２４の前のラインに先行する遅延ライン
２４への入力端から受信される。最上位ディジットは加
算ユニット２２の出力端、すなわち被乗数の最上位ディ
ジットに関連する加算ユニット２２から得られる。一般
に乗算ステージ１２の出力信号の最上位の半分は信号の
最下位の半分と比較して１周期だけ遅延される。
数Ａの倍数Ｒ（例えば４）となっている場合に、本発明
を実施した例が示されている。この構造は、図２の構造
と類似している。しかしながら最終遅延部品２４の１つ
前の入力端から乗算ステージからの最下位ディジットに
対する出力を得ている。次の２つのディジットの双方は
最終遅延ライン２４の前のラインに先行する遅延ライン
２４への入力端から受信される。最上位ディジットは加
算ユニット２２の出力端、すなわち被乗数の最上位ディ
ジットに関連する加算ユニット２２から得られる。一般
に乗算ステージ１２の出力信号の最上位の半分は信号の
最下位の半分と比較して１周期だけ遅延される。
【００１４】２．好ましい実施例の動作 本発明は次のように理解できる。図２を参照すると、Ｂ
00（すなわち乗数の第１のディジットの第１ビット）と
被乗数Ａの部分積が加算ユニット（加算ユニットは加算
器と遅延部品を含む）に入力され、記憶される。Ｂ
10（乗数の第２のディジットの第１ビット）の部分積が
加算ユニットに入力され、記憶される。被乗数Ａと乗数
のディジットの第１のビットのすべてとの部分積のすべ
てが記憶されるまで（すなわち｛Ａ＊（Ｂ00＋....＋Ｂ
(K-1)0）｝）このプロセスが続けられる。次にレジスタ
１０において、被乗数Ａが１ビット位置だけシフトさ
れ、同じ乗数のディジットの位置の部分積を組み合わせ
る例外を除き、上記プロセスが繰り返される。このプロ
セスは乗数のディジットの各ビット位置に対して繰り返
される。図２を参照すると、遅延部品２３から生じたス
キューイングの結果として、遅延部品２４はＡP ＊ＢK
の部分積を累積する。遅延部品２４から出力信号が抽出
される態様、すなわち加算器の位が増すごとに別の遅延
ラインから部分積が得られる態様から、部分積Ａ＊ＢK
は連続する周期の間で加算ユニット１４へ加えられる。
乗算ステージ１２からのＫ個の部分積はＫｉのインクリ
メント量だけシフトされ、Ｋ個の部分積を別々に処理す
るか、または組み合わせできる。二進表示ではディジッ
トは重複しないので、加算すべき結果はＭすなわち被乗
数Ａの大きさだけ重複するに過ぎない。従って、これら
部分積は加算ステージ１４において長さＭの加算器を使
って加算できる。図５にはこれら部分積の重複が示され
ている。また図５は、長さＬ−Ｍのキャリーリップルも
示している。Ｌ≧Ｍの場合、加算ステージにおける加算
は長さＭの加算器および長さＬ−Ｍのキャリー伝搬ユニ
ットを使って実行できる。従って加算ステージは長さＬ
の高速シフトおよびＭビットの加算ユニットを使って実
現できる。
00（すなわち乗数の第１のディジットの第１ビット）と
被乗数Ａの部分積が加算ユニット（加算ユニットは加算
器と遅延部品を含む）に入力され、記憶される。Ｂ
10（乗数の第２のディジットの第１ビット）の部分積が
加算ユニットに入力され、記憶される。被乗数Ａと乗数
のディジットの第１のビットのすべてとの部分積のすべ
てが記憶されるまで（すなわち｛Ａ＊（Ｂ00＋....＋Ｂ
(K-1)0）｝）このプロセスが続けられる。次にレジスタ
１０において、被乗数Ａが１ビット位置だけシフトさ
れ、同じ乗数のディジットの位置の部分積を組み合わせ
る例外を除き、上記プロセスが繰り返される。このプロ
セスは乗数のディジットの各ビット位置に対して繰り返
される。図２を参照すると、遅延部品２３から生じたス
キューイングの結果として、遅延部品２４はＡP ＊ＢK
の部分積を累積する。遅延部品２４から出力信号が抽出
される態様、すなわち加算器の位が増すごとに別の遅延
ラインから部分積が得られる態様から、部分積Ａ＊ＢK
は連続する周期の間で加算ユニット１４へ加えられる。
乗算ステージ１２からのＫ個の部分積はＫｉのインクリ
メント量だけシフトされ、Ｋ個の部分積を別々に処理す
るか、または組み合わせできる。二進表示ではディジッ
トは重複しないので、加算すべき結果はＭすなわち被乗
数Ａの大きさだけ重複するに過ぎない。従って、これら
部分積は加算ステージ１４において長さＭの加算器を使
って加算できる。図５にはこれら部分積の重複が示され
ている。また図５は、長さＬ−Ｍのキャリーリップルも
示している。Ｌ≧Ｍの場合、加算ステージにおける加算
は長さＭの加算器および長さＬ−Ｍのキャリー伝搬ユニ
ットを使って実行できる。従って加算ステージは長さＬ
の高速シフトおよびＭビットの加算ユニットを使って実
現できる。
【００１５】Ｌ＝Ｍの場合、本発明の加算器は図５に示
されるように実現できる。周期Ｔにおける乗算ステージ
の最上位の半分をＴ＋１の時間における最下位の半分に
加算する。この結果生じるキャリーは次の加算演算で実
施する。部分積は乗数をＭ個のスライスのままにする。
（最初の出力が最下位の半分である場合を除き）所望の
結果が得られるように最上位部分と最下位部分を直接加
算することが可能である。一般的な構成に含まれるゲー
トおよびシフト部品はプリプロセッサステージ１１のシ
フト演算に含めることができる。
されるように実現できる。周期Ｔにおける乗算ステージ
の最上位の半分をＴ＋１の時間における最下位の半分に
加算する。この結果生じるキャリーは次の加算演算で実
施する。部分積は乗数をＭ個のスライスのままにする。
（最初の出力が最下位の半分である場合を除き）所望の
結果が得られるように最上位部分と最下位部分を直接加
算することが可能である。一般的な構成に含まれるゲー
トおよびシフト部品はプリプロセッサステージ１１のシ
フト演算に含めることができる。
【００１６】本発明の結果、レイテンシーを増しながら
部品の利用率が高まる。加算ユニット２２は部分積ＡP
＊Ｂk の累積中に何回も使用される。
部品の利用率が高まる。加算ユニット２２は部分積ＡP
＊Ｂk の累積中に何回も使用される。
【００１７】再度、図６を参照する。合計ステージは加
算演算のキャリーアウトと別の加算のキャリーインとを
結ぶ長さＬ−Ｍビットのリップルキャリーを含む。Ｌ≧
Ｍの時は長さＭビット位置の加算器と長さＬ−Ｍビット
位置のキャリー伝搬ユニットを用いて加算を行うことが
できるので、加算が簡略化される。Ｌ−Ｍ＝０の場合、
合計ステージを構成するにはキャリー装置を備えた長さ
Ｌの、Ｍビットの加算ユニットをルーティングするだけ
でよい。
算演算のキャリーアウトと別の加算のキャリーインとを
結ぶ長さＬ−Ｍビットのリップルキャリーを含む。Ｌ≧
Ｍの時は長さＭビット位置の加算器と長さＬ−Ｍビット
位置のキャリー伝搬ユニットを用いて加算を行うことが
できるので、加算が簡略化される。Ｌ−Ｍ＝０の場合、
合計ステージを構成するにはキャリー装置を備えた長さ
Ｌの、Ｍビットの加算ユニットをルーティングするだけ
でよい。
【００１８】本発明は乗算演算を実行するのにより多数
のサイクルを必用としながら、装置をあまり使用しない
ようにすることを意図したものである。部分積Ａ0 ＊Ｂ
0 のレイテンシーはＮサイクルであるが、部分積Ａ＊Ｂ
0 のレイテンシーはＮ＋Ｋ−１サイクルである。しかし
ながら装置の数を増やすことによって、このレイテンシ
ーを小さくできる。例えばゲート部品２１の装置の複雑
性を適当に高めることにより、乗算器Ｂからの２ビット
（またはそれ以上のビット）をゲート部品２１に加え、
これらを乗算ステージの他の部品に印加する前にこれら
ビットを被乗数Ａでコード化できる。従って、装置の数
を増すことを犠牲に、レイテンシーを改善できる。更に
ゲート部品の複雑性を高めることにより、すなわち被乗
数Ａの一部を適当にシフト（またはルーティング）する
ことにより加算部品の入力ターミナルの結合された遅延
部品を省略できる。
のサイクルを必用としながら、装置をあまり使用しない
ようにすることを意図したものである。部分積Ａ0 ＊Ｂ
0 のレイテンシーはＮサイクルであるが、部分積Ａ＊Ｂ
0 のレイテンシーはＮ＋Ｋ−１サイクルである。しかし
ながら装置の数を増やすことによって、このレイテンシ
ーを小さくできる。例えばゲート部品２１の装置の複雑
性を適当に高めることにより、乗算器Ｂからの２ビット
（またはそれ以上のビット）をゲート部品２１に加え、
これらを乗算ステージの他の部品に印加する前にこれら
ビットを被乗数Ａでコード化できる。従って、装置の数
を増すことを犠牲に、レイテンシーを改善できる。更に
ゲート部品の複雑性を高めることにより、すなわち被乗
数Ａの一部を適当にシフト（またはルーティング）する
ことにより加算部品の入力ターミナルの結合された遅延
部品を省略できる。
【００１９】以上で特に好ましい実施例を参照して、本
発明について説明したが、当業者であれば本発明から逸
脱することなく、種々の変更を行ったり、好ましい実施
例の部品を均等物に置換することも理解できよう。更に
本発明の要旨から逸脱することなく、本発明の要旨に特
定の状況および材料を適合するように多数のへんこうを
行うことができる。
発明について説明したが、当業者であれば本発明から逸
脱することなく、種々の変更を行ったり、好ましい実施
例の部品を均等物に置換することも理解できよう。更に
本発明の要旨から逸脱することなく、本発明の要旨に特
定の状況および材料を適合するように多数のへんこうを
行うことができる。
【００２０】上記説明から明らかなように、本発明の所
定の特徴は、図示した実施例の特定の細部に限定される
ものでなく、よって当業者には他の変形および用途を思
いつくことができよう。従って、特許請求の範囲は本発
明の精神および範囲から逸脱しないすべての変形例およ
び用途をカバーするものである。
定の特徴は、図示した実施例の特定の細部に限定される
ものでなく、よって当業者には他の変形および用途を思
いつくことができよう。従って、特許請求の範囲は本発
明の精神および範囲から逸脱しないすべての変形例およ
び用途をカバーするものである。
【００２１】以上の説明に関して更に以下の項を開示す
る。 （１）被乗数Ａを記憶するためのシフトレジスタと、被
乗数Ａを第１の複数のＰ個のディジットＡ0 〜ＡP-1 に
区分し、乗数Ａを第２の複数のＫ個のディジットＢ0 〜
ＢK-1 に区分し、ゲート部品の制御ターミナルに乗数Ｂ
のビット信号を印加し、前記被乗数Ａをいつゲートユニ
ットに通過させ、前記乗数のどの論理ステートを前記ゲ
ートユニットによって送るかを判断するゲート部品と、
Ａ0 〜ＡP-1 の部分積を受信するための加算部品ＡＤＤ
0 〜ＡＤＤP-1 とを備え、各加算部品が加算部品ＡＤＤ
P-1 の第１入力ターミナルと前記ゲート部品との間に結
合されたＰ−１個の入力遅延部品を有し、各加算ユニッ
トが加算部品ＡＤＤP の出力ターミナルと前記加算部品
ＡＤＤP の第２入力ターミナルとの間に結合されたＫ個
の順次出力遅延部品を有し、各加算ユニットＡＤＤP が
加算部品ＡＤＤP+1 にキャリー信号を印加するようにな
っている乗算ステージおよび；加算部品ＡＤＤP-1 の
（Ｋ−ｐ）番目の出力遅延部品の出力ターミナルに印加
される信号グループを受けるための合計ステージを備え
たデジタル乗算ユニット。 （２）あるシーケンスの部分積Ａ＊ＢK （ここでＫは０
〜Ｋ−１である）が前記合計ステージに印加される、項
（１）記載の乗算ユニット。 （３）乗数の論理信号の数が被乗数の論理信号の数の倍
数である、項（１）記載の乗算ユニット。 （４）前記ゲート部品の機能を含むプリプロセッサステ
ージを更に含む、項（３）記載の乗算ユニット。 （５）前記合計ユニットがキャリーユニットを備えたＭ
×Ｎの加算部品（ここでＭは被乗数のビット数である）
である、項（３）記載の乗算ユニット。 （６）前記合計ユニットに位の高いＡ＊ＢK の部分積を
印加し、その後、次に位の低いＡ＊ＢK の部分積を印加
する、項（３）記載の乗算ユニット。 （７）Ｋ＝Ｐである、項（１）記載の乗算ユニット。 （８）前記合計ユニットがＬ＋Ｍビット幅の加算部品
（ここでＬは乗数Ｂの各ディジットにおけるビット数で
あり、Ｍは被乗数Ａのディジット数である）を有する、
項（７）記載の乗算ユニット。
る。 （１）被乗数Ａを記憶するためのシフトレジスタと、被
乗数Ａを第１の複数のＰ個のディジットＡ0 〜ＡP-1 に
区分し、乗数Ａを第２の複数のＫ個のディジットＢ0 〜
ＢK-1 に区分し、ゲート部品の制御ターミナルに乗数Ｂ
のビット信号を印加し、前記被乗数Ａをいつゲートユニ
ットに通過させ、前記乗数のどの論理ステートを前記ゲ
ートユニットによって送るかを判断するゲート部品と、
Ａ0 〜ＡP-1 の部分積を受信するための加算部品ＡＤＤ
0 〜ＡＤＤP-1 とを備え、各加算部品が加算部品ＡＤＤ
P-1 の第１入力ターミナルと前記ゲート部品との間に結
合されたＰ−１個の入力遅延部品を有し、各加算ユニッ
トが加算部品ＡＤＤP の出力ターミナルと前記加算部品
ＡＤＤP の第２入力ターミナルとの間に結合されたＫ個
の順次出力遅延部品を有し、各加算ユニットＡＤＤP が
加算部品ＡＤＤP+1 にキャリー信号を印加するようにな
っている乗算ステージおよび；加算部品ＡＤＤP-1 の
（Ｋ−ｐ）番目の出力遅延部品の出力ターミナルに印加
される信号グループを受けるための合計ステージを備え
たデジタル乗算ユニット。 （２）あるシーケンスの部分積Ａ＊ＢK （ここでＫは０
〜Ｋ−１である）が前記合計ステージに印加される、項
（１）記載の乗算ユニット。 （３）乗数の論理信号の数が被乗数の論理信号の数の倍
数である、項（１）記載の乗算ユニット。 （４）前記ゲート部品の機能を含むプリプロセッサステ
ージを更に含む、項（３）記載の乗算ユニット。 （５）前記合計ユニットがキャリーユニットを備えたＭ
×Ｎの加算部品（ここでＭは被乗数のビット数である）
である、項（３）記載の乗算ユニット。 （６）前記合計ユニットに位の高いＡ＊ＢK の部分積を
印加し、その後、次に位の低いＡ＊ＢK の部分積を印加
する、項（３）記載の乗算ユニット。 （７）Ｋ＝Ｐである、項（１）記載の乗算ユニット。 （８）前記合計ユニットがＬ＋Ｍビット幅の加算部品
（ここでＬは乗数Ｂの各ディジットにおけるビット数で
あり、Ｍは被乗数Ａのディジット数である）を有する、
項（７）記載の乗算ユニット。
【００２２】（９）被乗数Ａと乗数Ｂとをデジタル乗算
する方法であって、 ａ）各ディジットがあるシーケンスのＬ個の論理ビット
ＢK1から成る、あるシーケンスのＫ個のディジットＢK
となるようにＢを区分する工程と、 ｂ）ＡをあるシーケンスのＰ個のディジットＡP に区分
する工程と、 ｃ）最下位の乗数のディジットの最下位ビットから開始
し、連続する時間中に逐次部分積（Ａ0 〜ＡP-1 ）＊ｂ
K1を形成する工程と、 ｄ）Ｋ時間の遅延後、関連する加算部品ＡＤＤP の入力
ターミナルに各ＡP ＊ｂK1を印加する工程と、 ｅ）加算ユニットＡＤＤP からの出力信号をＫ時間遅延
した後に加算部品ＡＤＤP の第２入力ターミナルに印加
する工程と、 ｆ）ｌ≦Ｌ−１のときに、前記乗数のディジットの、最
下位の次の位のビットに対し、工程ｃ）〜ｅ）を繰り返
す工程と、 ｇ）ｌ＝Ｌのときに、連続する時間中に部分積Ａ＊Ｂ0
〜Ａ＊ＢK-1 を合計ユニットに印加する工程とを備えた
デジタル乗算方法。 （１０）連続する時間中に部分積Ａ＊ＢK から成る出力
信号を生成する工程を更に含む、項（９）記載の方法。 （１１）Ｌ＋Ｍビット幅の加算部品（ここでＭは被乗数
のビット数である）を有する合計ステージで前記部分積
Ａ＊ＢK を加算する工程を更に含む、項（１０）記載の
方法。 （１２）Ｌ＝Ｍの場合に、より位の高いほうの部分積Ａ
＊ＢK を位の低い部分積Ａ＊ＢK1よりも先に前記合計ユ
ニットに与える、項（１１）記載の方法。
する方法であって、 ａ）各ディジットがあるシーケンスのＬ個の論理ビット
ＢK1から成る、あるシーケンスのＫ個のディジットＢK
となるようにＢを区分する工程と、 ｂ）ＡをあるシーケンスのＰ個のディジットＡP に区分
する工程と、 ｃ）最下位の乗数のディジットの最下位ビットから開始
し、連続する時間中に逐次部分積（Ａ0 〜ＡP-1 ）＊ｂ
K1を形成する工程と、 ｄ）Ｋ時間の遅延後、関連する加算部品ＡＤＤP の入力
ターミナルに各ＡP ＊ｂK1を印加する工程と、 ｅ）加算ユニットＡＤＤP からの出力信号をＫ時間遅延
した後に加算部品ＡＤＤP の第２入力ターミナルに印加
する工程と、 ｆ）ｌ≦Ｌ−１のときに、前記乗数のディジットの、最
下位の次の位のビットに対し、工程ｃ）〜ｅ）を繰り返
す工程と、 ｇ）ｌ＝Ｌのときに、連続する時間中に部分積Ａ＊Ｂ0
〜Ａ＊ＢK-1 を合計ユニットに印加する工程とを備えた
デジタル乗算方法。 （１０）連続する時間中に部分積Ａ＊ＢK から成る出力
信号を生成する工程を更に含む、項（９）記載の方法。 （１１）Ｌ＋Ｍビット幅の加算部品（ここでＭは被乗数
のビット数である）を有する合計ステージで前記部分積
Ａ＊ＢK を加算する工程を更に含む、項（１０）記載の
方法。 （１２）Ｌ＝Ｍの場合に、より位の高いほうの部分積Ａ
＊ＢK を位の低い部分積Ａ＊ＢK1よりも先に前記合計ユ
ニットに与える、項（１１）記載の方法。
【００２３】（１３）被乗数Ａを記憶するためのシフト
レジスタと、乗数Ｂからの印加論理信号に応答自在であ
り、この印加された論理信号によって決定される被乗数
Ａの各ビットに対する論理ステートで前記被乗数Ａを通
過させるための、前記被乗数Ａが印加されるゲート部品
と、前記ゲート部品に結合された第１の複数の累積ユニ
ットとを備え、各累積ユニットが、複数の記憶設備を含
み、前記記憶設備の各々が予め選択された被乗数のディ
ジットと前記乗数の選択されたディジットの論理信号と
の部分積を記憶する累積ユニットから成り、累積ユニッ
トの前記記憶設備の各々が前記各記憶設備の内容に新た
に形成された部分積を加算するための装置を含み、前記
複数の累積ユニットが前記被乗数と乗数のディジットの
部分積の部分出力信号を生成するデジタル乗算ユニッ
ト。 （１４）前記出力信号が連続する時間中に前記被乗数Ａ
と、位が増す前記乗数ＢK のディジットとの部分積を含
む、項（１３）記載の乗算ユニット。 （１５）前記乗数が前記被乗数の整数倍である、項（１
４）記載の乗算ユニット。 （１６）前記部分積を合計するための合計ユニットがＭ
×Ｍビット幅（ここでＭは乗数のディジット数である）
である、項（１５）記載の乗算ユニット。
レジスタと、乗数Ｂからの印加論理信号に応答自在であ
り、この印加された論理信号によって決定される被乗数
Ａの各ビットに対する論理ステートで前記被乗数Ａを通
過させるための、前記被乗数Ａが印加されるゲート部品
と、前記ゲート部品に結合された第１の複数の累積ユニ
ットとを備え、各累積ユニットが、複数の記憶設備を含
み、前記記憶設備の各々が予め選択された被乗数のディ
ジットと前記乗数の選択されたディジットの論理信号と
の部分積を記憶する累積ユニットから成り、累積ユニッ
トの前記記憶設備の各々が前記各記憶設備の内容に新た
に形成された部分積を加算するための装置を含み、前記
複数の累積ユニットが前記被乗数と乗数のディジットの
部分積の部分出力信号を生成するデジタル乗算ユニッ
ト。 （１４）前記出力信号が連続する時間中に前記被乗数Ａ
と、位が増す前記乗数ＢK のディジットとの部分積を含
む、項（１３）記載の乗算ユニット。 （１５）前記乗数が前記被乗数の整数倍である、項（１
４）記載の乗算ユニット。 （１６）前記部分積を合計するための合計ユニットがＭ
×Ｍビット幅（ここでＭは乗数のディジット数である）
である、項（１５）記載の乗算ユニット。
【００２４】（１７）被乗数Ａを記憶するためのシフト
レジスタと、被乗数Ａを第１の複数のＰ個のディジット
Ａ0 〜ＡP-1 に区分し、乗数Ａを第２の複数のＫ個のデ
ィジットＢ0 〜ＢK-1 に区分し、ゲート部品の制御ター
ミナルに乗数Ｂのビット信号を印加し、前記被乗数Ａを
いつゲートユニットに通過させるか、更に通過させる被
乗数の論理信号の論理状態を決定するゲート部品と、乗
数Ｂのディジットの論理信号と被乗数のディジットＡ0
〜ＡP-1 の部分積を受信するための加算部品ＡＤＤ0 〜
ＡＤＤP-1 とを備え、各加算部品が加算部品ＡＤＤP-1
の第１入力ターミナルと前記ゲートおよびシフト部品と
の間に結合されたＰ−１個のシーケンシャルな入力遅延
部品を有し、各加算ユニットが加算部品ＡＤＤP の出力
ターミナルと前記加算部品ＡＤＤP+1 の第２入力ターミ
ナルとの間に結合されたＫ個の順次出力遅延部品を有
し、各加算ユニットＡＤＤP が加算部品ＡＤＤP+1 にキ
ャリー信号を印加するようになっている乗算ステージ
と、加算部品ＡＤＤP-1 の（Ｋ−ｐ）番目の出力遅延部
品の出力ターミナルに印加される信号グループを受ける
ための合計ステージとを備えたデジタル乗算ユニット。
レジスタと、被乗数Ａを第１の複数のＰ個のディジット
Ａ0 〜ＡP-1 に区分し、乗数Ａを第２の複数のＫ個のデ
ィジットＢ0 〜ＢK-1 に区分し、ゲート部品の制御ター
ミナルに乗数Ｂのビット信号を印加し、前記被乗数Ａを
いつゲートユニットに通過させるか、更に通過させる被
乗数の論理信号の論理状態を決定するゲート部品と、乗
数Ｂのディジットの論理信号と被乗数のディジットＡ0
〜ＡP-1 の部分積を受信するための加算部品ＡＤＤ0 〜
ＡＤＤP-1 とを備え、各加算部品が加算部品ＡＤＤP-1
の第１入力ターミナルと前記ゲートおよびシフト部品と
の間に結合されたＰ−１個のシーケンシャルな入力遅延
部品を有し、各加算ユニットが加算部品ＡＤＤP の出力
ターミナルと前記加算部品ＡＤＤP+1 の第２入力ターミ
ナルとの間に結合されたＫ個の順次出力遅延部品を有
し、各加算ユニットＡＤＤP が加算部品ＡＤＤP+1 にキ
ャリー信号を印加するようになっている乗算ステージ
と、加算部品ＡＤＤP-1 の（Ｋ−ｐ）番目の出力遅延部
品の出力ターミナルに印加される信号グループを受ける
ための合計ステージとを備えたデジタル乗算ユニット。
【００２５】（１８）プリプロセッサステージと、乗算
ステージと、合計ステージとを有する乗算ユニットにお
いて、乗算ステージがシフトレジスタと、ゲート部品制
御ターミナルに印加される乗数Ｂのビット信号によって
決定される態様で被乗数Ａを制御しながら通過させるた
めのゲート部品とを含む。被乗数のディジットにより部
分積をグループ分けし、ディジットの順によって決定さ
れる遅延部品を通して、関連する加算部品の第１ターミ
ナルに各ディジットを印加する。各加算部品からの出力
信号が複数の遅延部品を通過するようにし、同じ加算部
品の第２入力ターミナルに印加する。このようにして部
分積ＡP ＊Ｂq をアセンブルし、単一周期で合計ユニッ
トへ部分積（Ａ0 ＋....ＡM ）＊Ｂq ＝Ａ＊Ｂq を印加
できる。乗数が被乗数の整数倍である時は、実施は特に
容易である。
ステージと、合計ステージとを有する乗算ユニットにお
いて、乗算ステージがシフトレジスタと、ゲート部品制
御ターミナルに印加される乗数Ｂのビット信号によって
決定される態様で被乗数Ａを制御しながら通過させるた
めのゲート部品とを含む。被乗数のディジットにより部
分積をグループ分けし、ディジットの順によって決定さ
れる遅延部品を通して、関連する加算部品の第１ターミ
ナルに各ディジットを印加する。各加算部品からの出力
信号が複数の遅延部品を通過するようにし、同じ加算部
品の第２入力ターミナルに印加する。このようにして部
分積ＡP ＊Ｂq をアセンブルし、単一周期で合計ユニッ
トへ部分積（Ａ0 ＋....ＡM ）＊Ｂq ＝Ａ＊Ｂq を印加
できる。乗数が被乗数の整数倍である時は、実施は特に
容易である。
【図１】３ステージの乗算ユニットの一般的アーキテク
チャを示すブロック図である。
チャを示すブロック図である。
【図２】本発明に係わる３ステージアーキテクチャの第
２すなわち乗算ステージのブロック図である。
２すなわち乗算ステージのブロック図である。
【図３】図２の装置の最下位デジタルパス内および次の
位のデジタルデータパス内の遅延部品の内容を示し、そ
のうちの図３Ａは最初の乗算サイクルの後の遅延部品の
内容を示し、図３Ｂは５つの乗算サイクル後の遅延部品
の内容を示す。
位のデジタルデータパス内の遅延部品の内容を示し、そ
のうちの図３Ａは最初の乗算サイクルの後の遅延部品の
内容を示し、図３Ｂは５つの乗算サイクル後の遅延部品
の内容を示す。
【図４】本発明に係わる乗算ユニットの乗算ステージか
ら合計ステージへの部分積の印加を示すブロック図であ
る。
ら合計ステージへの部分積の印加を示すブロック図であ
る。
【図５】乗算ステージによって得られた部分積の、図２
の乗算ユニットの合計ステージへの重複を示す拡大図で
ある。
の乗算ユニットの合計ステージへの重複を示す拡大図で
ある。
【図６】本発明の特殊なケースを示すブロック図であ
る。
る。
１０ レジスタ １２ 乗算ステージ １４ 合計ステージ ２１ ゲート部品 ２２ 加算ユニット ２３、２４ 遅延部品
Claims (2)
- 【請求項１】 被乗数Ａを記憶するためのシフトレジス
タと、 被乗数Ａを第１の複数のＰ個のディジットＡ0 〜ＡP-1
に区分し、乗数Ａを第２の複数のＫ個のディジットＢ0
〜ＢK-1 に区分し、ゲート部品の制御ターミナルに乗数
Ｂのビット信号を印加し、前記被乗数Ａをいつゲートユ
ニットに通過させ、前記乗数のどの論理ステートを前記
ゲートユニットによって送るかを判断するゲート部品
と、 Ａ0 〜ＡP-1 の部分積を受信するための加算部品ＡＤＤ
0 〜ＡＤＤP-1 とを備え、各加算部品が加算部品ＡＤＤ
P-1 の第１入力ターミナルと前記ゲート部品との間に結
合されたＰ−１個の入力遅延部品を有し、各加算ユニッ
トが加算部品ＡＤＤP の出力ターミナルと前記加算部品
ＡＤＤP の第２入力ターミナルとの間に結合されたＫ個
の順次出力遅延部品を有し、各加算ユニットＡＤＤP が
加算部品ＡＤＤP+1 にキャリー信号を印加するようにな
っている乗算ステージおよび；加算部品ＡＤＤP-1 の
（Ｋ−ｐ）番目の出力遅延部品の出力ターミナルに印加
される信号グループを受けるための合計ステージを備え
たデジタル乗算ユニット。 - 【請求項２】 被乗数Ａと乗数Ｂとをデジタル乗算する
方法であって、 ａ）各ディジットが所定のシーケンスのＬ個の論理ビッ
トＢK1から成る所定のシーケンスのＫ個のディジットＢ
K となるようにＢを区分し、 ｂ）ＡをあるシーケンスのＰ個のディジットＡP に区分
し、 ｃ）最下位の乗数のディジットの最小位ビットから開始
し、連続する時間中に逐次部分積（Ａ0 〜ＡP-1 ）＊ｂ
K1を形成し、 ｄ）Ｋ時間の遅延後、関連する加算部品ＡＤＤP の入力
ターミナルに各ＡP ＊ｂK1を印加し、 ｅ）加算ユニットＡＤＤP からの出力信号をＫ時間遅延
した後に加算部品ＡＤＤP の第２入力ターミナルに印加
し、 ｆ）ｌ≦Ｌ−１のときに、前記乗数のディジットの、最
下位の次の位のビットに対し、前記工程ｃ）〜ｅ）を繰
り返し、 ｇ）ｌ＝Ｌのときに、連続する時間中に部分積Ａ＊Ｂ0
〜Ａ＊ＢK-1 を合計ユニットに印加する、ことを備えた
デジタル乗算方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US3250296P | 1996-11-27 | 1996-11-27 | |
| US032502 | 1996-11-27 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10161853A true JPH10161853A (ja) | 1998-06-19 |
| JP3848764B2 JP3848764B2 (ja) | 2006-11-22 |
Family
ID=21865268
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP32654997A Expired - Fee Related JP3848764B2 (ja) | 1996-11-27 | 1997-11-27 | デジタル乗算ユニットおよびデジタル乗算方法 |
Country Status (4)
| Country | Link |
|---|---|
| EP (1) | EP0845740B1 (ja) |
| JP (1) | JP3848764B2 (ja) |
| DE (1) | DE69715570T2 (ja) |
| TW (1) | TW381232B (ja) |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6284335A (ja) * | 1985-10-09 | 1987-04-17 | Hitachi Ltd | 乗算回路 |
| JPH05197741A (ja) * | 1991-06-06 | 1993-08-06 | Lsi Logic Corp | インターリーブド乗算器累算器 |
-
1997
- 1997-11-26 DE DE1997615570 patent/DE69715570T2/de not_active Expired - Lifetime
- 1997-11-26 EP EP19970120773 patent/EP0845740B1/en not_active Expired - Lifetime
- 1997-11-27 TW TW86117817A patent/TW381232B/zh not_active IP Right Cessation
- 1997-11-27 JP JP32654997A patent/JP3848764B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| TW381232B (en) | 2000-02-01 |
| EP0845740A1 (en) | 1998-06-03 |
| JP3848764B2 (ja) | 2006-11-22 |
| DE69715570T2 (de) | 2003-08-07 |
| EP0845740B1 (en) | 2002-09-18 |
| DE69715570D1 (de) | 2002-10-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4839847A (en) | N-clock, n-bit-serial multiplier | |
| US6049815A (en) | Method and apparatus for finite field multiplication | |
| US5524090A (en) | Apparatus for multiplying long integers | |
| JPS62286307A (ja) | 多重ステージデジタル信号乗算加算装置 | |
| US4965762A (en) | Mixed size radix recoded multiplier | |
| US5297069A (en) | Finite impulse response filter | |
| US4142242A (en) | Multiplier accumulator | |
| JPH08221256A (ja) | 乗算器及び積和演算装置 | |
| US7607165B2 (en) | Method and apparatus for multiplication and/or modular reduction processing | |
| JP3848764B2 (ja) | デジタル乗算ユニットおよびデジタル乗算方法 | |
| JPS5981761A (ja) | シストリツク計算配列 | |
| US5262975A (en) | Serial input multiplier apparatus | |
| JP3660075B2 (ja) | 除算装置 | |
| US5311193A (en) | Digital chirp generator | |
| US5258945A (en) | Method and apparatus for generating multiples of BCD number | |
| US5031137A (en) | Two input bit-serial multiplier | |
| US5691930A (en) | Booth encoder in a binary multiplier | |
| US5889691A (en) | Apparatus and method for a multiplier unit with high component utilization | |
| US5684731A (en) | Booth multiplier using data path width adder for efficient carry save addition | |
| JPH0773022A (ja) | ディジタル信号処理方法及びその装置 | |
| JP2864597B2 (ja) | ディジタル演算回路 | |
| JP3695561B2 (ja) | 積和器 | |
| KR100386979B1 (ko) | 갈로아체상에서 비트 직렬 승산기의 병렬화 방법 및 이를이용한 직병렬 승산기 | |
| JP3155026B2 (ja) | 累算器 | |
| US5644518A (en) | Computing device for nth degree functions |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20041126 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060801 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060804 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060828 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090901 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100901 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110901 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110901 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120901 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130901 Year of fee payment: 7 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |