JPH07248901A - 演算器 - Google Patents
演算器Info
- Publication number
- JPH07248901A JPH07248901A JP4216594A JP4216594A JPH07248901A JP H07248901 A JPH07248901 A JP H07248901A JP 4216594 A JP4216594 A JP 4216594A JP 4216594 A JP4216594 A JP 4216594A JP H07248901 A JPH07248901 A JP H07248901A
- Authority
- JP
- Japan
- Prior art keywords
- carry
- bits
- notci
- adder
- addition
- 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.)
- Pending
Links
Abstract
(57)【要約】
【目的】少伝播段数及び小規模で実現できる高速な加算
方式及びこの方式に従う加算器の構成を提供し、従来に
提案されているパストランジスタに基づいた加算器より
高速な加算器を構成する。 【構成】４ビット毎のグループに分けた２つのｎビット
の入力Ｘ(０..ｎ−１)及びＹ(０..ｎ−１)が、それぞれ
のグループの最下位のキャリアが「１」及び「０」の前
提で、ＳＧ(Sum Generator）で仮定的に加算され、前記
の各グループの最下位のキャリアが「１」及び「０」の
前提で、各々のグループの桁上げ及び４ビットの加算に
対する実キャリアがＣＧ(Carry Generator）で生成さ
れ、これらの実キャリアで、前記のＳＧの出力がＳＳ
（Sum Selector）ブロックで選択される。
方式及びこの方式に従う加算器の構成を提供し、従来に
提案されているパストランジスタに基づいた加算器より
高速な加算器を構成する。 【構成】４ビット毎のグループに分けた２つのｎビット
の入力Ｘ(０..ｎ−１)及びＹ(０..ｎ−１)が、それぞれ
のグループの最下位のキャリアが「１」及び「０」の前
提で、ＳＧ(Sum Generator）で仮定的に加算され、前記
の各グループの最下位のキャリアが「１」及び「０」の
前提で、各々のグループの桁上げ及び４ビットの加算に
対する実キャリアがＣＧ(Carry Generator）で生成さ
れ、これらの実キャリアで、前記のＳＧの出力がＳＳ
（Sum Selector）ブロックで選択される。
Description
【０００１】
【産業上の利用分野】本発明は、大型計算機，マイクロ
プロセッサ等のシステムの演算部の中心である加算器の
構成に関する。
プロセッサ等のシステムの演算部の中心である加算器の
構成に関する。
【０００２】
【従来の技術】加算器に関する研究が古くから行われて
いる。加算を高速に行うために色々な計算方式が提案さ
れてきている。理論的には、技術論文「ジェイ スクラ
ンスキー，“コンディショナル−サム アディション
ロジック”アイアールイー トランザクションズ オン
エレクトロニック コンピューターズ １９６０年６
月（J. Sklansky，“Conditional-Sum Addition Logi
c，”IRE Trans. on Electronic Computers, June 196
0)，pp.226-231」に示す計算方式が一番高速であると見
なされている。しかし、その実現に必要な面積が大き
い。このため、技術論文「オージェー ベドリ，“キャ
リー セレクト アダーズ”アイアールイー トランザ
クションズ オン エレクトロニック コンピューター
ズＥＣ１１巻３号，１９６２年６月(O.J. Bedrij，“Ca
rry-Select Adders，”IRE Trans．on Electronic Comp
uters，Vol.EC-11，No.3，June 1962）pp.340-346.」の
計算方式が普及してきた。しかし、技術論文「エイロザ
ーメル他、“リアライゼーション オブ トランスミッ
ション ゲート コンディショナル ザム アダーズウ
ィズ ロー レイテェンシー タイム”アイイーイーイ
ー ジャーナル オブソリツド ステート サーキッツ
２４巻３号（A.Rothermel, et.al. “Realizati
on of Transmission-Gate Conditional-Sum (TGCS) Add
ers with Low Latency Time，”IEEE Journal of Soli
d-State Circuits，Vol.24，No.3）pp.558-561 June 19
89」及び「エム ミッタル他，“ディーピーティーエル
４−ｂ キャリー ルックアヘッド アダー”アイイ
ーイーイー ジャーナル オブ ソリツド ステート
サーキッツ ２７巻１１号（M. Mittal ea al.“DPTL4-
b Carry Lookahead Adder,”IEEE Journal of Solid-St
ate Circuits, Vol.27，No.11）pp.1644-1647，Novembe
r 1992」には、パストランジスタの回路を用いることに
よって高速で小規模の加算器回路を構成することができ
ると述べられている。しかし、ビット数が大きくなるに
つれ回路が大きくなり、必要となるバッファ回路は面積
が大きくなるため、前記の両方の論文の技術は、多いビ
ット数の加算器への適用が困難である。
いる。加算を高速に行うために色々な計算方式が提案さ
れてきている。理論的には、技術論文「ジェイ スクラ
ンスキー，“コンディショナル−サム アディション
ロジック”アイアールイー トランザクションズ オン
エレクトロニック コンピューターズ １９６０年６
月（J. Sklansky，“Conditional-Sum Addition Logi
c，”IRE Trans. on Electronic Computers, June 196
0)，pp.226-231」に示す計算方式が一番高速であると見
なされている。しかし、その実現に必要な面積が大き
い。このため、技術論文「オージェー ベドリ，“キャ
リー セレクト アダーズ”アイアールイー トランザ
クションズ オン エレクトロニック コンピューター
ズＥＣ１１巻３号，１９６２年６月(O.J. Bedrij，“Ca
rry-Select Adders，”IRE Trans．on Electronic Comp
uters，Vol.EC-11，No.3，June 1962）pp.340-346.」の
計算方式が普及してきた。しかし、技術論文「エイロザ
ーメル他、“リアライゼーション オブ トランスミッ
ション ゲート コンディショナル ザム アダーズウ
ィズ ロー レイテェンシー タイム”アイイーイーイ
ー ジャーナル オブソリツド ステート サーキッツ
２４巻３号（A.Rothermel, et.al. “Realizati
on of Transmission-Gate Conditional-Sum (TGCS) Add
ers with Low Latency Time，”IEEE Journal of Soli
d-State Circuits，Vol.24，No.3）pp.558-561 June 19
89」及び「エム ミッタル他，“ディーピーティーエル
４−ｂ キャリー ルックアヘッド アダー”アイイ
ーイーイー ジャーナル オブ ソリツド ステート
サーキッツ ２７巻１１号（M. Mittal ea al.“DPTL4-
b Carry Lookahead Adder,”IEEE Journal of Solid-St
ate Circuits, Vol.27，No.11）pp.1644-1647，Novembe
r 1992」には、パストランジスタの回路を用いることに
よって高速で小規模の加算器回路を構成することができ
ると述べられている。しかし、ビット数が大きくなるに
つれ回路が大きくなり、必要となるバッファ回路は面積
が大きくなるため、前記の両方の論文の技術は、多いビ
ット数の加算器への適用が困難である。
【０００３】最近、技術論文「スズキ他“ア １.５ｎ
ｓ ３２ｂ シーモス エイエルユー イン ダブル
パストランジスタ ロジック”ダイジェスト オブ テ
クニカル ペーパーズ アイイーイーイー インタナシ
ョナル ソリッド ステートサーキッツ カンファレン
ス ペーパー M. Susuki，et al，(“A 1.5ns 32bCMOS
ALU in Double Pass-Transistor Logic，”Digest of
Technical Papers,IEEE International Solid-State Ci
rcuits Conference, paper）TA.5.4，pp.90-91，Feb. 1
993」に前記の問題を緩和するアプロ−チが示されてい
る。この論文の加算器はキャリー セレクト アダー
（Carry-Select Adder）型であり、３２ビットの場合は
一番大きなバッファは４個のマルチプレクサしか起動し
ない。
ｓ ３２ｂ シーモス エイエルユー イン ダブル
パストランジスタ ロジック”ダイジェスト オブ テ
クニカル ペーパーズ アイイーイーイー インタナシ
ョナル ソリッド ステートサーキッツ カンファレン
ス ペーパー M. Susuki，et al，(“A 1.5ns 32bCMOS
ALU in Double Pass-Transistor Logic，”Digest of
Technical Papers,IEEE International Solid-State Ci
rcuits Conference, paper）TA.5.4，pp.90-91，Feb. 1
993」に前記の問題を緩和するアプロ−チが示されてい
る。この論文の加算器はキャリー セレクト アダー
（Carry-Select Adder）型であり、３２ビットの場合は
一番大きなバッファは４個のマルチプレクサしか起動し
ない。
【０００４】図１１乃至図１５に、従来技術による演算
器のブロック図もしくは回路図を例示する。
器のブロック図もしくは回路図を例示する。
【０００５】
【発明が解決しようとする課題】上記の技術論文「M. S
usuki, N. Ohkubo, T. Yamanaka, A. Shimizu and K.Sa
saki,“A 1.5ns 32b CMOS ALU in Double Pass-Transis
tor Logic，”Digestof Technical Papers, IEEE Inter
national Solid-State Circuits Conference,paper TA.
5.4,pp.90-91，Feb. 1993」に示す加算器の構成方式
で、技術論文「A.Rothermel, B.J. Hosticka, G. Trost
er and J. Arndt，“Realization of Transmission-
Gate Conditional-Sum (TGCS) Adders with Low Latenc
y Time,”IEEE Journal of Solid-State Circuits,Vol.
24,No.3，pp.558-561 June 1989」の加算器のトランジ
スタの直連結及びバッファの大きさに関する問題がある
程度解決されるが、その代り、入力から出力までの遅延
時間が大きくなる。バッファのトランジスタを除いて、
Rothermel らの回路で、入力から出力まで一番長いパス
の信号は６個のパストランジスタを通過する。一方Susu
kiらの回路では、同様な信号は４個のパストランジスタ
しか通過しない。しかし、前記のRothermel の回路で、
入力から出力までの遅延時間が信号の伝播段数で数える
と６段であるのに対して前記のSusukiの回路では、１１
段である。
usuki, N. Ohkubo, T. Yamanaka, A. Shimizu and K.Sa
saki,“A 1.5ns 32b CMOS ALU in Double Pass-Transis
tor Logic，”Digestof Technical Papers, IEEE Inter
national Solid-State Circuits Conference,paper TA.
5.4,pp.90-91，Feb. 1993」に示す加算器の構成方式
で、技術論文「A.Rothermel, B.J. Hosticka, G. Trost
er and J. Arndt，“Realization of Transmission-
Gate Conditional-Sum (TGCS) Adders with Low Latenc
y Time,”IEEE Journal of Solid-State Circuits,Vol.
24,No.3，pp.558-561 June 1989」の加算器のトランジ
スタの直連結及びバッファの大きさに関する問題がある
程度解決されるが、その代り、入力から出力までの遅延
時間が大きくなる。バッファのトランジスタを除いて、
Rothermel らの回路で、入力から出力まで一番長いパス
の信号は６個のパストランジスタを通過する。一方Susu
kiらの回路では、同様な信号は４個のパストランジスタ
しか通過しない。しかし、前記のRothermel の回路で、
入力から出力までの遅延時間が信号の伝播段数で数える
と６段であるのに対して前記のSusukiの回路では、１１
段である。
【０００６】本発明の目的は、前記のRothermel らの計
算機の少伝播段数及びSusukiの小さい面積及び小さいバ
ッファで実現できる高速な加算方式及びこの方式に従う
加算器の構成を提供することである。
算機の少伝播段数及びSusukiの小さい面積及び小さいバ
ッファで実現できる高速な加算方式及びこの方式に従う
加算器の構成を提供することである。
【０００７】
【課題を解決するための手段】本発明の演算器は、上記
目的を達成するために、上記の技術論文「O.J. Bedrij,
“Carry-Select Adders，”IRE Trans．on Electronic
Computers，Vol.EC-11,No.3, June 1962，pp.340-34
6．」の計算方式を基にする。しかし、桁上げの計算の
流れは、バイナリ木を成す。
目的を達成するために、上記の技術論文「O.J. Bedrij,
“Carry-Select Adders，”IRE Trans．on Electronic
Computers，Vol.EC-11,No.3, June 1962，pp.340-34
6．」の計算方式を基にする。しかし、桁上げの計算の
流れは、バイナリ木を成す。
【０００８】バイナリ木を成す演算方式は、技術論文
「ラドナ他，“パラレル プリフィクス コンピューテ
ーション”，ジャーナル オブ ジ エイシーエム（R.
E.Ladner and M.J. Fischer，”Parallel Prefix Compu
tation," Journal of theACM)，Vol.27，pp.831-838,Oc
tober 1980」に提案され、技術論文「ブレント他,“ア
レギュラー レイアウト フォー パラレル アダー
ズ”アイイーイーイートランザクションズ オン コン
ピューターズ（R.P. Brent and H.T. Kung，“A Regula
r Layout for Parallel Adders，”IEEE Trans. on Com
puters Vol.C-31，No.3，pp.260-264,March 1982」及び
「ケリハー他，“ＥＬＭ−Ａ ファースト アディッシ
ョン アルゴリズム ディスカバード バイ ア プロ
グラム”アイイーイーイー トランザクションズ オン
コンピューターズ（T.P.Kelliher, R.M. Owens, M.J.
Irwin and T.-T. Hwang,“ELM-A Fast AdditionAlgori
thm Discovered by a Program,”IEEE Trans. on Compu
ters，）Vol.41，No.9，pp.1181-1184，September 199
2」において加算器の設計に用いられた。
「ラドナ他，“パラレル プリフィクス コンピューテ
ーション”，ジャーナル オブ ジ エイシーエム（R.
E.Ladner and M.J. Fischer，”Parallel Prefix Compu
tation," Journal of theACM)，Vol.27，pp.831-838,Oc
tober 1980」に提案され、技術論文「ブレント他,“ア
レギュラー レイアウト フォー パラレル アダー
ズ”アイイーイーイートランザクションズ オン コン
ピューターズ（R.P. Brent and H.T. Kung，“A Regula
r Layout for Parallel Adders，”IEEE Trans. on Com
puters Vol.C-31，No.3，pp.260-264,March 1982」及び
「ケリハー他，“ＥＬＭ−Ａ ファースト アディッシ
ョン アルゴリズム ディスカバード バイ ア プロ
グラム”アイイーイーイー トランザクションズ オン
コンピューターズ（T.P.Kelliher, R.M. Owens, M.J.
Irwin and T.-T. Hwang,“ELM-A Fast AdditionAlgori
thm Discovered by a Program,”IEEE Trans. on Compu
ters，）Vol.41，No.9，pp.1181-1184，September 199
2」において加算器の設計に用いられた。
【０００９】桁上げの計算は流れがバイナリ木を成す
と、ｎビットの加算は、その桁上げの計算時間がＯ（lo
gn）の時間で行えると知られている。つまり、３２ビッ
トの場合は、Carry Select Adderの最初のキャリアの生
成段階と結果の選択の段階を入れると、入力から出力ま
での遅延時間が信号の伝播段数で表すと７段となる。桁
上げの計算を実現する回路は構成がバイナリ木に従うと
計算の各段に起動されるブロック数が限られるため、そ
れらを起動するバッファの大きさが小さくなる。なお、
高速化及び小規模のために、パストランジスタを用い
る。また、パストランジスタの直列接続に起因するドレ
インとソース間電圧の低下問題を避けるために、回路の
実現にマルチプレクサを用いる。
と、ｎビットの加算は、その桁上げの計算時間がＯ（lo
gn）の時間で行えると知られている。つまり、３２ビッ
トの場合は、Carry Select Adderの最初のキャリアの生
成段階と結果の選択の段階を入れると、入力から出力ま
での遅延時間が信号の伝播段数で表すと７段となる。桁
上げの計算を実現する回路は構成がバイナリ木に従うと
計算の各段に起動されるブロック数が限られるため、そ
れらを起動するバッファの大きさが小さくなる。なお、
高速化及び小規模のために、パストランジスタを用い
る。また、パストランジスタの直列接続に起因するドレ
インとソース間電圧の低下問題を避けるために、回路の
実現にマルチプレクサを用いる。
【００１０】
【作用】文献「ワン，“コンピュータ アリスメティッ
ク：プリンシプルズ，アーキテクチュア アンド デザ
イン”(K. Hwang，“Computer Arithmetic:Principles,
Architecture and Design”，pp.81-84：New York：Wil
ey，1978」に示されるように、通常のCarry Select Add
erは、ｎビットの入力Ｘ及びＹを固定のビットサイズ
（４か８ビット）毎のグループに分割し、グループの最
下位のキャリアが「０」及び「１」の前提でグループ毎
の加算及び桁上げの計算を同時に行い、各グループの実
キャリアをそのグループ及びその前のグループの仮定的
なキャリアで計算し、計算した実キャリアで各グループ
の実加算出力を選択する。
ク：プリンシプルズ，アーキテクチュア アンド デザ
イン”(K. Hwang，“Computer Arithmetic:Principles,
Architecture and Design”，pp.81-84：New York：Wil
ey，1978」に示されるように、通常のCarry Select Add
erは、ｎビットの入力Ｘ及びＹを固定のビットサイズ
（４か８ビット）毎のグループに分割し、グループの最
下位のキャリアが「０」及び「１」の前提でグループ毎
の加算及び桁上げの計算を同時に行い、各グループの実
キャリアをそのグループ及びその前のグループの仮定的
なキャリアで計算し、計算した実キャリアで各グループ
の実加算出力を選択する。
【００１１】本発明の加算器は、基本的にはこの計算方
式とほぼ同じであるが、桁上げの計算の流れがバイナリ
木を成す。本発明の桁上げの計算方式と従来の桁上げの
計算方式との違いを述べるために、一つのグループは４
ビットで構成されていると仮定し考える。以下、グルー
プ内及びグループの出力のキャリアはグループへの入力
キャリアが「０」のとき、Ｃ(０)で表し、入力キャリア
が「１」のとき、Ｃ(１)で表す。２つの４ビットの入力
（Ｘｉ，Ｘｉ＋１，Ｘｉ＋２，Ｘｉ＋３）と（Ｙｉ，Ｙ
ｉ＋１，Ｙｉ＋２，Ｙｉ＋３）の従来の桁上げの計算を
式で表すと、次の数１，数２のようになる。
式とほぼ同じであるが、桁上げの計算の流れがバイナリ
木を成す。本発明の桁上げの計算方式と従来の桁上げの
計算方式との違いを述べるために、一つのグループは４
ビットで構成されていると仮定し考える。以下、グルー
プ内及びグループの出力のキャリアはグループへの入力
キャリアが「０」のとき、Ｃ(０)で表し、入力キャリア
が「１」のとき、Ｃ(１)で表す。２つの４ビットの入力
（Ｘｉ，Ｘｉ＋１，Ｘｉ＋２，Ｘｉ＋３）と（Ｙｉ，Ｙ
ｉ＋１，Ｙｉ＋２，Ｙｉ＋３）の従来の桁上げの計算を
式で表すと、次の数１，数２のようになる。
【００１２】
【数１】 Ｃｉ−１＝０の前提で： Ｃｉ(０)＝Ｘｉ．Ｙｉ Ｃｉ＋１(０)＝(Ｘｉ＋１．Ｙｉ＋１)．notＣｉ(０)＋(Ｘｉ＋１＋Ｙｉ ＋１）．Ｃｉ(０) Ｃｉ＋２(０)＝(Ｘｉ＋２．Ｙｉ＋２)．notＣｉ＋１(０)＋(Ｘｉ＋２＋Ｙｉ ＋２）．Ｃｉ＋１(０) Ｃｉ＋３(０)＝(Ｘｉ＋３．Ｙｉ＋３)．notＣｉ＋２(０)＋(Ｘｉ＋３＋Ｙｉ ＋３）．Ｃｉ＋２(０) …（数１）
【００１３】
【数２】 Ｃｉ−１＝１の前提で： Ｃｉ(１)＝Ｘｉ＋Ｙｉ Ｃｉ＋１(１)＝(Ｘｉ＋１．Ｙｉ＋１)．notＣｉ(１)＋(Ｘｉ＋１＋Ｙｉ ＋１）．Ｃｉ(１) Ｃｉ＋２(１)＝(Ｘｉ＋２．Ｙｉ＋２)．notＣｉ＋１(１)＋(Ｘｉ＋２＋Ｙｉ ＋２）．Ｃｉ＋１(１) Ｃｉ＋３(１)＝(Ｘｉ＋３．Ｙｉ＋３)．notＣｉ＋２(１)＋(Ｘｉ＋３＋Ｙｉ ＋３）．Ｃｉ＋２(１) …（数２） 但し、notＸ はＸの否定値を表す。上記の式を簡単にす
るために、以下では、Ｘｉ．ＹｉをＡｉで、Ｘｉ＋Ｙｉ
をＯｉで表す。
るために、以下では、Ｘｉ．ＹｉをＡｉで、Ｘｉ＋Ｙｉ
をＯｉで表す。
【００１４】本発明の桁上げの計算方式で、２つのビッ
ト間で、下位のビットの桁上げが計算され、上位のビッ
トの桁上げと組んでそれらのビットに対する桁上げが生
成され、次の上位の２つのビットの桁上げと組んで４つ
のビットの桁下が生成され、この４つのビットを上位の
４つのビットと組んで８つのビットの桁上げが生成さ
れ、これを繰返して上位のビットの桁上げが順次に生成
される。
ト間で、下位のビットの桁上げが計算され、上位のビッ
トの桁上げと組んでそれらのビットに対する桁上げが生
成され、次の上位の２つのビットの桁上げと組んで４つ
のビットの桁下が生成され、この４つのビットを上位の
４つのビットと組んで８つのビットの桁上げが生成さ
れ、これを繰返して上位のビットの桁上げが順次に生成
される。
【００１５】本発明での４ビットの桁上げの計算を式で
表すと、次の数３および数４のようになる。
表すと、次の数３および数４のようになる。
【００１６】
【数３】 Ｃｉ−１＝０の前提で： Ｃｉ(０)＝Ａｉ Ｃｉ＋１(０)＝Ａｉ＋１．notＣｉ(０)＋Ｏｉ＋１．Ｃｉ(０) Ｃｉ＋２(０)＝Ａｉ＋２．notＣｉ＋１(０)＋Ｏｉ＋２．Ｃｉ＋１(０) Ｃ′ｉ＋３(０)＝Ａｉ＋３．notＡｉ＋２＋Ｏｉ＋３．Ａｉ＋２ Ｃ″ｉ＋３(０)＝Ａｉ＋３．notＯｉ＋２＋Ｏｉ＋３．Ｏｉ＋２ Ｃｉ＋３(０)＝Ｃ′ｉ＋３．notＣｉ＋１(０)＋Ｃ″ｉ＋３．Ｃｉ＋１(０) …（数３）
【００１７】
【数４】 Ｃｉ−１＝１の前提で： Ｃｉ(１)＝Ｏｉ Ｃｉ＋１(１)＝Ａｉ＋１．notＣｉ(１)＋Ｏｉ＋１．Ｃｉ(１) Ｃｉ＋２(１)＝Ａｉ＋２．notＣｉ＋１(１)＋Ｏｉ＋２．Ｃｉ＋１(１) Ｃ′ｉ＋３(１)＝Ａｉ＋３．notＡｉ＋２＋Ｏｉ＋３．Ａｉ＋２ Ｃ″ｉ＋３(１)＝Ａｉ＋３．notＯｉ＋２＋Ｏｉ＋３．Ｏｉ＋２ Ｃｉ＋３(１)＝Ｃ′ｉ＋３．notＣｉ＋１(１)＋Ｃ″ｉ＋３．Ｃｉ＋１(１) …（数４） これらの方式から解かる様に、Ｃｉ＋２及びＣｉ＋３の
キャリアが同時に生成され、遅延時間が一段小さくな
る。上記の４ビットの桁上げの計算の流れをグラフで表
せば、バイナリ木の様なものができあがる。
キャリアが同時に生成され、遅延時間が一段小さくな
る。上記の４ビットの桁上げの計算の流れをグラフで表
せば、バイナリ木の様なものができあがる。
【００１８】ここで、従来の技術の式、数５は本発明で
の式、数６と等価であることを証明する必要がある。
の式、数６と等価であることを証明する必要がある。
【００１９】
【数５】 Ｃｉ＋３＝Ａｉ＋３．notＣｉ＋２＋Ｏｉ＋３．Ｃｉ＋２ …（数５）
【００２０】
【数６】 Ｃｉ＋３＝Ｃ′ｉ＋３．notＣｉ＋１＋Ｃ″ｉ＋３．Ｃｉ＋１ …（数６） 一般性を失うことがないため、数５及び数６から(１)及
び(０)を省いた。
び(０)を省いた。
【００２１】数６にＣ′ｉ＋３及びＣ″ｉ＋３の式を代
入すると、数７となる。
入すると、数７となる。
【００２２】
【数７】 Ｃｉ＋３＝(Ａｉ＋３．notＡｉ＋２＋Ｏｉ＋３．Ａｉ＋２)．notＣｉ＋１ ＋(Ａｉ＋３．notＯｉ＋２＋Ｏｉ＋３．Ｏｉ＋２)．Ｃｉ＋１ ＝Ａｉ＋３.(notＡｉ＋２．notＣｉ＋１＋notＯｉ＋２．Ｃｉ＋１) ＋Ｏｉ＋３.(Ａｉ＋２．notＣｉ＋１＋Ｏｉ＋２．Ｃｉ＋１) …（数７） この式のＯｉ＋３の(Ａｉ＋２．notＣｉ＋１＋Ｏｉ＋
２．Ｃｉ＋１)はＣｉ＋２であるため、数７の最初の項
の（notＡｉ＋２．notＣｉ＋１＋notＯｉ＋２．Ｃｉ＋
１）はnotＣｉ＋２に等しいことだけを証明すれば良
い。
２．Ｃｉ＋１)はＣｉ＋２であるため、数７の最初の項
の（notＡｉ＋２．notＣｉ＋１＋notＯｉ＋２．Ｃｉ＋
１）はnotＣｉ＋２に等しいことだけを証明すれば良
い。
【００２３】
【数８】 notＣｉ＋２＝not(Ａｉ＋２.notＣｉ＋１＋Ｏｉ＋２.Ｃｉ＋１) …（数８) であるため、数９となる。
【００２４】
【数９】 notＣｉ＋２＝(notＡｉ＋２＋Ｃｉ＋１)．(notＯｉ＋２＋notＣｉ＋１） ＝notＡｉ＋２．(notＯｉ＋２＋notＣｉ＋１)＋Ｃｉ ＋１．(notＯｉ＋２＋notＣｉ＋１） ＝notＡｉ＋２．notＯｉ＋２＋notＡｉ＋２．notＣｉ＋１ ＋Ｃｉ＋１．notＯｉ＋２＋Ｃｉ＋１．notＣｉ＋１ ＝notＡｉ＋２．notＯｉ＋２＋notＡｉ＋２．notＣｉ＋１ ＋Ｃｉ＋１．notＯｉ＋２ ＝notＡｉ＋２．notＯｉ＋２．(notＣｉ＋１＋Ｃｉ＋１) ＋notＡｉ＋２．notＣｉ＋１＋Ｃｉ＋１．notＯｉ＋２ ＝notＡｉ＋２．notＯｉ＋２．notＣｉ＋１＋notＡｉ ＋２．notＯｉ＋２．Ｃｉ＋１ ＋notＡｉ＋２．notＣｉ＋１＋Ｃｉ＋１．notＯｉ＋２ ＝notＡｉ＋２．notＣｉ＋１．(notＯｉ＋２＋１)＋Ｃｉ ＋１．notＯｉ＋２．(notＡｉ＋２＋１） ＝notＡｉ＋２．notＣｉ＋１＋Ｃｉ＋１．notＯｉ＋２ …（数９） 故に、本発明での桁上げの計算方式でキャリアの正しい
値が得られることを証明した。この方式を拡張するため
に、上記の式に対応する演算を数１０のように定義す
る。
値が得られることを証明した。この方式を拡張するため
に、上記の式に対応する演算を数１０のように定義す
る。
【００２５】
【数１０】 Ｃｉ＝Ａｉ Ｃｉ＋１＝Ａｉ＋１．notＣｉ＋Ｏｉ＋１．Ｃｉ ＝(Ａｉ＋１，Ｏｉ＋１)＊Ｃｉ Ｃｉ＋２＝Ａｉ＋２．notＣｉ＋１＋Ｏｉ＋２．Ｃｉ＋１ ＝(Ａｉ＋２，Ｏｉ＋２)＊Ｃｉ＋１ Ｃ′ｉ＋３(０)＝Ａｉ＋３．notＡｉ＋２＋Ｏｉ＋３．Ａｉ＋２ ＝(Ａｉ＋３，Ｏｉ＋３)＊Ａｉ＋２ Ｃ″ｉ＋３(０)＝Ａｉ＋３．notＯｉ＋２＋Ｏｉ＋３．Ｏｉ＋２ ＝(Ａｉ＋３，Ｏｉ＋３)＊Ｏｉ＋２ Ｃｉ＋３＝Ｃ′ｉ＋３．notＣｉ＋１＋Ｃ″ｉ＋３．Ｃｉ＋１ ＝(Ｃ′ｉ＋３，Ｃ″ｉ＋３)＊Ｃｉ＋１ …（数１０） 上記の証明で、数１１となる。
【００２６】
【数１１】 Ｃｉ＋３＝(Ｃ′ｉ＋３，Ｃ″ｉ＋３)＊Ｃｉ＋１＝((Ａｉ＋３，Ｏｉ ＋３)＊Ａｉ＋２，(Ａｉ＋３，Ｏｉ＋３)＊Ｏｉ＋２)＊Ｃｉ＋１ …（数１１） この演算を４ビット以上、３２ビットまで拡張すると、
上記のｉ＝１のとき数１２となる。
上記のｉ＝１のとき数１２となる。
【００２７】
【数１２】 Ｃ４＝(Ｃ′４，Ｃ″４)＊Ｃ２ Ｃ８＝(Ｃ８(０)，Ｃ８(１))＊Ｃ４ Ｃ１２＝(Ｃ１２(０)，Ｃ１２(１))＊Ｃ８ Ｃ１６＝((Ｃ１６(０)，Ｃ１６(１))＊Ｃ１２(０)，(Ｃ１６(０)， Ｃ１６(１))＊Ｃ１２(１))＊Ｃ８ Ｃ２０＝(Ｃ２０(０)，Ｃ２０(１))＊Ｃ１６ Ｃ２４＝((Ｃ２４(０)，Ｃ２４(１))＊Ｃ２０(０)，(Ｃ２４(０)， Ｃ２４(１))＊Ｃ２０(１))＊Ｃ１６ ＝(Ｃ２４′(０)，Ｃ２４′(１))＊Ｃ１６ Ｃ２８＝((Ｃ２８(０)，Ｃ２８(１))＊Ｃ２４′(０)，(Ｃ２８(０)， Ｃ２８(１))＊Ｃ２４′(１))＊Ｃ１６ ＝(Ｃ２８″(０)，Ｃ２８″(１))＊Ｃ１６ Ｃ３２＝(((Ｃ３２(０)，Ｃ３２(１))＊Ｃ２８(０)，(Ｃ３２(０)， Ｃ３２(１))＊Ｃ２８(１))＊Ｃ２４′(０)，((Ｃ３２(０)， Ｃ３２(１))＊Ｃ２８(０)，(Ｃ３２(０)，Ｃ３２(１)) ＊Ｃ２８(１))＊Ｃ２４′(１))＊Ｃ１６ …（数１２）
【００２８】
【実施例】図１は本発明の一実施例の演算器の基本構成
を示す。すなわち図１の演算器は、二つのｎビットの入
力Ｘ（０..ｎ−１）及びＹ（０..ｎ−１）を４ビット毎
のグループに分け、それぞれのグループの最下位のキャ
リアが「１」及び「０」の前提で仮定的にｎビットの加
算するＳＧ(Sum Generator）と、前記の入力Ｘ(０..ｎ
−１）及びＹ(０..ｎ−１）を４ビット毎のグループに
分け、それぞれのグループの最下位のキャリアが「１」
及び「０」の前提で仮定的に前記各４ビットのグループ
の加算に対応する桁上げを生成するＣＧ(Carry Generat
or）、及び、前記のＳＧ及びＣＧの出力を入力し、前記
ＣＧからの入力で前記のＳＧの出力を選択して前記のｎ
ビットの入力Ｘ（０..ｎ−１）とＹ（０..ｎ−１）の加
算に対応する結果を出力するＳＳ（Sum Selector）ブロ
ックからなる。
を示す。すなわち図１の演算器は、二つのｎビットの入
力Ｘ（０..ｎ−１）及びＹ（０..ｎ−１）を４ビット毎
のグループに分け、それぞれのグループの最下位のキャ
リアが「１」及び「０」の前提で仮定的にｎビットの加
算するＳＧ(Sum Generator）と、前記の入力Ｘ(０..ｎ
−１）及びＹ(０..ｎ−１）を４ビット毎のグループに
分け、それぞれのグループの最下位のキャリアが「１」
及び「０」の前提で仮定的に前記各４ビットのグループ
の加算に対応する桁上げを生成するＣＧ(Carry Generat
or）、及び、前記のＳＧ及びＣＧの出力を入力し、前記
ＣＧからの入力で前記のＳＧの出力を選択して前記のｎ
ビットの入力Ｘ（０..ｎ−１）とＹ（０..ｎ−１）の加
算に対応する結果を出力するＳＳ（Sum Selector）ブロ
ックからなる。
【００２９】図２は本発明の一般の構成を示す図１に対
する３２ビットの場合の一つの実施例を示す。図３は６
４ビットの計算を構成するための実施例のブロック図を
示す。図２及び図３に示すＣＧ１が４ビットの桁上げの
回路であり、上記に示した式に従い、その一つの実現例
を図４及び図５に示す。図５の回路のゲートレベルの実
現例を図６に示す。図２及び図３のΣのブロック図を図
７に示す。図７の半加算器ＨＡの詳細を図８に示す。図
２及び図３内のＭＸ，ＭＸ１，ＭＸ２及びMX3とＭＸ４
を図９及び図１０に示す。
する３２ビットの場合の一つの実施例を示す。図３は６
４ビットの計算を構成するための実施例のブロック図を
示す。図２及び図３に示すＣＧ１が４ビットの桁上げの
回路であり、上記に示した式に従い、その一つの実現例
を図４及び図５に示す。図５の回路のゲートレベルの実
現例を図６に示す。図２及び図３のΣのブロック図を図
７に示す。図７の半加算器ＨＡの詳細を図８に示す。図
２及び図３内のＭＸ，ＭＸ１，ＭＸ２及びMX3とＭＸ４
を図９及び図１０に示す。
【００３０】図２及び図３の加算器の動作は基本的には
同一のものであるため、以下では図２の回路動作をもと
に実施例を説明する。また、ゲートレベルの実現に前記
文献のようなダブル パス トランジスタ ロジック
（ＤＰＬ）の回路を用いるため、ここではその動作の説
明を省略する。
同一のものであるため、以下では図２の回路動作をもと
に実施例を説明する。また、ゲートレベルの実現に前記
文献のようなダブル パス トランジスタ ロジック
（ＤＰＬ）の回路を用いるため、ここではその動作の説
明を省略する。
【００３１】図２の加算及び桁上げの演算は、まず３２
ビットの入力Ｘ及びＹを４ビット毎ブロックに分け、各
ブロックの桁上げの計算はＣＧ１により行い、ブロック
の仮定的な加算はΣにより行う。前記作用の項で記した
ように、各ブロックへの実キャリアがＭＸ，ＭＸ１及び
ＭＸ２で生成され、これらのキャリアで各ブロックの実
加算出力が選択される。上記に示したように、このＡＬ
Ｕの特徴として、ＣＧ１内のキャリアの計算及び上位の
ビットの計算の流れがバイナリ木を成す。これで、ＣＧ
１内の信号の伝播段数が４段，ＣＧ１の出力から加算器
の出力まで４段、合計８段となる。
ビットの入力Ｘ及びＹを４ビット毎ブロックに分け、各
ブロックの桁上げの計算はＣＧ１により行い、ブロック
の仮定的な加算はΣにより行う。前記作用の項で記した
ように、各ブロックへの実キャリアがＭＸ，ＭＸ１及び
ＭＸ２で生成され、これらのキャリアで各ブロックの実
加算出力が選択される。上記に示したように、このＡＬ
Ｕの特徴として、ＣＧ１内のキャリアの計算及び上位の
ビットの計算の流れがバイナリ木を成す。これで、ＣＧ
１内の信号の伝播段数が４段，ＣＧ１の出力から加算器
の出力まで４段、合計８段となる。
【００３２】これに対して、図１１から図１５までに示
す前記の技術論文の回路では、CLA1内の信号の伝播段数
が５段，ＣＬＡ１の出力から加算器の出力まで６段、合
計１１段である。本発明で５０％に近い伝播段数の節約
ができる。
す前記の技術論文の回路では、CLA1内の信号の伝播段数
が５段，ＣＬＡ１の出力から加算器の出力まで６段、合
計１１段である。本発明で５０％に近い伝播段数の節約
ができる。
【００３３】回路量の視点から、本発明の加算器は前記
の回路に比べると、６％程度大きい。６４のビットの場
合は、これが４％程度となる。比較には図２，図３及び
図１１，図１２を用いた。
の回路に比べると、６％程度大きい。６４のビットの場
合は、これが４％程度となる。比較には図２，図３及び
図１１，図１２を用いた。
【００３４】
【発明の効果】本発明の桁上げの計算方式及び計算機を
用いることにより、従来技術の加算器より高速なものを
構成することができる。また、加算を中心とする他の演
算ユニットも高速化できる。
用いることにより、従来技術の加算器より高速なものを
構成することができる。また、加算を中心とする他の演
算ユニットも高速化できる。
【図１】本発明の基本構成を示す演算器のブロック図。
【図２】本発明の加算器を３２ビットとしたときの一実
施例のブロック図。
施例のブロック図。
【図３】本発明の加算器を６４ビットとしたときの一実
施例(上位の３２ビットの回路)のブロック図。
施例(上位の３２ビットの回路)のブロック図。
【図４】図３のＣＧ１のブロック図。
【図５】図４の各ブロックのゲートレベルの構成図。
【図６】図５のＣＧ０のトランジスタレベルの一実施例
を示す回路図。
を示す回路図。
【図７】図２のΣの一実施例の説明図。
【図８】図７のΣのＨＡのトランジスタレベルの一実施
例を示す回路図。
例を示す回路図。
【図９】図２及び図３のＭＸ１及びＭＸ２の一実施例の
ブロック図。
ブロック図。
【図１０】図３のＭＸ３及びＭＸ４の一実施例のブロッ
ク図。
ク図。
【図１１】従来の技術の３２ビットの加算器の一実施例
のブロック図。
のブロック図。
【図１２】図１１の技術の６４ビットの加算器の一実施
例（上位の３２ビットの回路）のブロック図。
例（上位の３２ビットの回路）のブロック図。
【図１３】図１１のＣＬＡ１及びＣＬＡ２のブロック
図。
図。
【図１４】図１３のＣＬＡ１のＣＬＡ０のトランジスタ
レベルの実現例を示す回路図。
レベルの実現例を示す回路図。
【図１５】図１１及び図１２のＣＬＡ２Ｈの実現例のブ
ロック図。
ロック図。
Ｘ(０..ｎ−１)…ｎビットの入力、Ｙ(０..ｎ−１)Ｄ…
ｎビットの入力、ＳＧ（Sum Generator）…仮定的に加
算を行うブロック、ＣＧ（Carry Generator）…仮定的
に加算に対応するキャリアを生成するブロック、ＳＳ
（Sum Selector）…ＳＳブロックの出力でＳＧの出力か
ら加算出力を選択するブロック、Ｘｉ，Ｙｉ…１ビット
の入力、Ｃｉ…キャリア、Ｃｉ＋３(０)…Ｃｉ−１が
「０」の時のＸｉ＋３とＹｉ＋３の加算に対応するキャ
リア、Ｃｉ＋３(１)…Ｃｉ−１が「１」の時のＸｉ＋３と
Ｙｉ＋３の加算に対応するキャリア、ＨＡ…半加算器、
ＶＤＤ…電源、ＧＮＤ…グランド、ＡＮＤ／ＮＡＮＤ，
ＸＯＲ／ＸＮＯＲ…論理素子、ＭＸ…マルチプレクサ、
ＣＬＡ０，ＣＬＡ１，ＣＬＡ２，ＣＬＡ２Ｈ，ＭＸ１〜
ＭＸ４…マルチプレクサで構成される構成要素。
ｎビットの入力、ＳＧ（Sum Generator）…仮定的に加
算を行うブロック、ＣＧ（Carry Generator）…仮定的
に加算に対応するキャリアを生成するブロック、ＳＳ
（Sum Selector）…ＳＳブロックの出力でＳＧの出力か
ら加算出力を選択するブロック、Ｘｉ，Ｙｉ…１ビット
の入力、Ｃｉ…キャリア、Ｃｉ＋３(０)…Ｃｉ−１が
「０」の時のＸｉ＋３とＹｉ＋３の加算に対応するキャ
リア、Ｃｉ＋３(１)…Ｃｉ−１が「１」の時のＸｉ＋３と
Ｙｉ＋３の加算に対応するキャリア、ＨＡ…半加算器、
ＶＤＤ…電源、ＧＮＤ…グランド、ＡＮＤ／ＮＡＮＤ，
ＸＯＲ／ＸＮＯＲ…論理素子、ＭＸ…マルチプレクサ、
ＣＬＡ０，ＣＬＡ１，ＣＬＡ２，ＣＬＡ２Ｈ，ＭＸ１〜
ＭＸ４…マルチプレクサで構成される構成要素。
Claims (3)
- 【請求項１】二つのｎビットの入力Ｘ（０..ｎ−１）及
びＹ（０..ｎ−１）を４ビット毎のグループに分け、そ
れぞれのグループの最下位のキャリアが「１」及び
「０」の前提で仮定的にｎビットの加算するＳＧ(Sum G
enerator）と、前記の入力Ｘ（０..ｎ−１）及びＹ
（０..ｎ−１）を４ビット毎のグループに分け、それぞ
れのグループの最下位のキャリアが「１」及び「０」の
前提で仮定的に前記各４ビットのグループの加算に対応
する桁上げを生成するＣＧ(Carry Generator）、及び、
前記のＳＧ及びＣＧの出力を入力し、前記ＣＧからの入
力で前記のＳＧの出力を選択して前記のｎビットの入力
Ｘ（０..ｎ−１）とＹ（０..ｎ−１）の加算に対応する
結果を出力するＳＳ（Sum Selector）ブロック、前記の
三つのブロックで構成されることを特徴とする加算器。 - 【請求項２】請求項第１項に記載の桁上げを生成するＣ
Ｇ(Carry Generator）は桁上げの計算の流れがバイナリ
木(binary tree）を構成することを特徴とする加算器。 - 【請求項３】請求項第１項に記載の全てのブロックがパ
ストランジスタを用いることを特徴とする加算器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4216594A JPH07248901A (ja) | 1994-03-14 | 1994-03-14 | 演算器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4216594A JPH07248901A (ja) | 1994-03-14 | 1994-03-14 | 演算器 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07248901A true JPH07248901A (ja) | 1995-09-26 |
Family
ID=12628358
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4216594A Pending JPH07248901A (ja) | 1994-03-14 | 1994-03-14 | 演算器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07248901A (ja) |
-
1994
- 1994-03-14 JP JP4216594A patent/JPH07248901A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5278783A (en) | Fast area-efficient multi-bit binary adder with low fan-out signals | |
| US6301600B1 (en) | Method and apparatus for dynamic partitionable saturating adder/subtractor | |
| JPS6055438A (ja) | ２入力加算器 | |
| US20010016865A1 (en) | Multiplier circuit for reducing the number of necessary elements without sacrificing high speed capability | |
| US4556948A (en) | Multiplier speed improvement by skipping carry save adders | |
| US4858168A (en) | Carry look-ahead technique having a reduced number of logic levels | |
| US6012079A (en) | Conditional sum adder using pass-transistor logic and integrated circuit having the same | |
| JP2000235479A (ja) | 和・比較演算を実行するための方法および装置 | |
| US5500813A (en) | Circuit for adding multiple-bit binary numbers | |
| US20030120694A1 (en) | Method and apparatus for use in booth-encoded multiplication | |
| US6003059A (en) | Carry select adder using two level selectors | |
| EP0147836A2 (en) | Precharge-type carry chained adder circuit | |
| JP2992588B2 (ja) | 加算回路 | |
| CN117971157A (zh) | 进位逻辑电路 | |
| KR920004108B1 (ko) | 자리올림 선택가산회로를 갖는 논리회로 | |
| Govindarajulu et al. | Design of Energy-Efficient and High-Performance VLSI Adders | |
| Ganguly et al. | A reconfigurable parallel prefix ling adder with modified enhanced flagged binary logic | |
| Chetana et al. | An Efficient Selection Gate Logic Based Ripple Carry Adder for Deep Learning Networks | |
| Grad et al. | A hybrid Ling carry-select adder | |
| Priya et al. | A Design of low power Adders | |
| US6301597B1 (en) | Method and apparatus for saturation in an N-NARY adder/subtractor | |
| JPH09185493A (ja) | 加算器用集積回路 | |
| US6272514B1 (en) | Method and apparatus for interruption of carry propagation on partition boundaries | |
| Boateng | Design and Implementation of a 16 Bit Carry-Lookahead Adder | |
| Kamble et al. | Design of Area-Power-Delay Efficient Square Root Carry Select Adder |