JPH0467211B2 - - Google Patents

Description

【発明の詳細な説明】

［産業上の利用分野］ 半発明は加算回路に関し、特に比較的少ないゲ
ート使用量で桁上げ伝播遅延を大きく低下させた
加算回路に関する。 ［従来技術およびその問題点］ ２つのＮビツトオペランドを加算してＮビツト
の結果を得ること（しばしば桁上げ伝搬加算と呼
ばれる）はデジタル・プロセツサの基本的な演算
である。この演算を実行するために従来より種々
の桁上げ方式が用いられている。 桁上げ伝搬加算を簡単に実行するにはいわゆる
リツプル・アダー（ripple adder）を用いればよ
い。リツプル・アダーはビツト当りのトランジス
タが比較的少なくてすむが、一般的に比較的低速
である。リツプル・アダーはこのように他の加算
器の能力測定の基準としてしばしば用いられる様
な、基本的ではあるが、それだけに低速な加算器
である。 第１図は代表的なリツプル・アダー・セルを示
す図である。第１図において、Ａ(i)及びＢ(i)は加
えられる２つのオペランドのそれぞれのビツトで
あり、Cin(i)は前段のリツプル・アダー・セルか
らの桁上げ入力であり、Cout(i)はこのリツプ
ル・アダー・セルからの桁上げ出力であり、また
Ｄ(i)はこのリツプル・アダー・セルの和である。
ある１つのリツプル・アダー・セルの桁上げ出力
は次段のリツプル・アダー・セルの桁上げ入力と
なる。表１にPASCAL風の言語で書かれた、Ｎ
ビツト・リツプル・アダーの論理動作を説明する
プログラムを示す。なお、表１のプログラムにお
いて「＋」は論理和、「・」は論理積、「XOR」
は排他的論理和を示す。 表 １ For ｉ＝０ toN−１ DO BEGIN Ｋ(i)＝Ａ(i)＋Ｂ(i) Ｇ(i)＝Ａ(i)・Ｂ(i) Ｐ(i)＝Ａ(i)XOR Ｂ(i) Cout(i)＝Ｇ(i)＋〔Ｋ(i)・Cin(i)〕 ＝Cin（ｉ＋１） Ｄ(i)＝Ｐ(i)XOR Cin(i) End リツプル・アダーは桁上げ先見回路を付加する
ことにより高速化することができる。桁上げ先見
加算器を実現するために、リツプル・アダーは、
例えば４つのリツプル・アダー・セルから成るブ
ロツクで構成されている。４つの高速加算器の各
ブロツクは、第２図に示すように、ゲートが付加
されており、このゲートによりＫビツト（すなわ
ち、ORゲートＫ(i)の出力）が全て“１”の時、
前段のブロツクからの桁上げ出力がこのブロツク
を素通りして次段のブロツクに伝搬される。桁上
げ先見加算器は比較的高速であり、MOS回路で
安価に構成できる。 他の方法として、I.R.E.トランザクシヨンズ・
オン・エレクトロニツク・コンピユーターズ（I.
R.E.Transactions on Electronic Computers）
誌1960年６月号、第226頁に、スクランスキー
（Sklansky）氏により「条件付き和による加算論
理」として発表された条件付き和加算器がある。
条件付き和加算は非常に高速で動作するのだが、
上述の比較的低速の加算に比べて非常に多くのロ
ジツクを必要とする。その結果、条件付き和加算
はビツト当りの価格が非常に高いものとなつてし
まう。事実、この方法は広範囲には使用されてい
ない。 上記した様に、従来から桁上げ伝搬加算を実行
するために種々の桁上げ方式が使用されている。
しかし、これら公知の方式は新世代のコンピユー
タにとつてはしばしば遅すぎるものであつたり、
或は期待されるよりもはるかに複雑かつ高価なも
のであつた。 ［発明の目的］ 本発明は上述した従来技術の問題点を解消し、
高速かつ実現容易な加算回路を提供することを目
的とする。 ［発明の概要］ 本発明の一実施例によれば、加算回路は中間桁
上げ信号を発生するセルの直列接続構成となつて
いる。従つてこれら各ビツト対の中間桁上げ信号
は連続する段を独立して次々と伝搬して行くこと
ができる。従つて本発明によれば、公知例と比較
して全加算器の遅延時間を減少させることができ
ると共に、回路の複雑さを比較的低くおさえるこ
とができる。本発明はまた増分器
（incrementor）やプライオリテイ・エンコーダ
にも応用できる。これらの応用例についても以下
で説明する。 本発明の加算回路はセルの種類が比較的少なく
てすむので、任意長の加算器、増分器又はプライ
オリテイ・エンコーダを構成する場合には以下に
図示する様に規則的に容易に結合することができ
る。従つて本発明によれば、絶対速度が速い回路
を実現することが出来ると共にバイポーラ又は
MOS技術のいずれによりLSIを製造した場合で
も、設計上の複雑化を抑えて安価に構成すること
ができる。 ［発明の実施例］ 以下、図面によつて本発明の実施例を詳細に説
明する。 以下では、条件付き桁上げ加算と呼ばれている
桁上げ伝播加算を実行する２つの加算器Ａ，Ｂを
開示している。加算器Ｂが本発明の実施例であ
り、加算器Ａは加算器Ｂと桁上げ方式の一般原理
を共通にする加算器である。これら２つの加算器
Ａ，Ｂの構成は両方とも加算器以外にも増分器や
プライオリテイ・エンコーダにも適用できること
が後述する説明により理解できるだろう。表２に
於て、公知の方式と本発明を用いた条件付き桁上
げ加算器との比較を示した。表２に於て、加算器
の速度は全加算を実行するのに必要なゲート遅延
段数によつて示してある。表２に示したデータは
32ビツト加算器の場合である。 第３Ａ図及び第３Ｂ図は条件付き桁上げ加算器
Ａを示す図であり、表３は条件付き桁上げ加算器
Ａに関連する論理式である。第３Ａ図には３種の
異なるセルが示されている。それらはスタート・
セル、任意の数（０でも良い）の継続セル、及び
エンド・セルである。第３Ｂ図は、９ビツト加算
器の場合のセル構成例を示す図である。この加算
器に於て、各ブロツクは２〜４個の１ビツト・セ
ルを備えている。すなわちブロツク０に２つのセ
ル、ブロツク１に３つのセル、そしてブロツク２
に４つのセルを備えている。例えば、第２ブロツ
ク（ｊ＝１）は３つのセルを備えており、ビツト
番号２はスタート・セル、ビツト番号３は継続
（continue）セル、そしてビツト番号４はエン
ド・セルである。

【表】

【表】 基本的に、各ブロツクに於て（例えばｊ＝０〜
２に於て）２つのリツプル桁上げ出力Cout0(i)及
びCout1(i)が発生される。各ブロツクのスター
ト・セルに於て桁上げ入力Cin0及びCin1はそれ
ぞれ“０”及び“１”と定義されていることに注
意されたい。この２つの桁上げ出力Coutは現在
のブロツクに入力された桁上げ入力Cinブロツク
(j)と結合することにより現在のブロツクの桁上げ
出力Coutブロツク(j)を発生する。ｊ＝０〜２の
全てのブロツクでそれらの２つの桁上げの連鎖
（Cout0−Cin0及びCout1−Cin1）が同時に次々と
伝搬される。ブロツク０は最初にその桁上げ出力
を発生し、そしてブロツク１に伝搬する。その
後、桁上げが各ブロツクを「飛び越す」ためには
ゲート１段分の遅延しか必要ない。よつて、条件
付き桁上げ加算器Ａにおいては、桁上げ伝搬遅延
時間を最小にした場合、ブロツクの大きさ、すな
わちビツト長は、ブロツク番号ｊの増加につれて
等差数列的（すなわち２，３，４，……等）に増
加するから、全遅延時間はオペランドのビツト長
の平方根にほぼ比例して増加する。 従つて条件付き桁上げ加算器Ａは桁上げ先見加
算器と比較して、表２からわかる様にビツト当り
の素子を17％増加するのみで25％の性能の向上を
得ることができる。同様に、条件付き桁上げ加算
器Ａは１ビツト・セルによつて構成されており、
他の高速化技術の様な複数ビツトにまたがつてい
るセルを使用してはいない。このことにより、実
現が容易でかつチツプ面積の使用効率が良好であ
る規則なレイアウトを持つ集積回路を作ることが
できる。 本発明の実施例である、条件付き桁上げ加算器
Ｂを第４図に示し、またその動作を示す
PASCAL風の言語で書かれたプログラムを表４
に示す。表４のプログラムはオペランド長がＮビ
ツトの場合について示しており、またここで“２
〓〓ｊ”は2^jを表わす。 この実施例の構成は条件付き桁上げ加算器Ａ
（第３Ａ図及び第３Ｂ図）と類似しており、また
同様にして入力はCin0＝１及びCin1＝１と見な
され、桁上げ出力がそれに従つて演算される。

【表】 第４図に於て、各ステージは各ビツトから発生
される桁上げ出力Cout0（ｊ，ｉ）及びCout1（ｊ，
ｉ）を、そのビツトへの桁上げ入力がそれぞれ
“０”及び“１”であると仮定して発生する。但
し、“ｊ”はステージ番号であり“ｉ”はビツト
番号であるとする。この目的は、ビツトのブロツ
ク全体に対して下位から与えられる桁上げ入力が
それぞれ“０”及び“１”であるとして各ビツト
に対する桁上げ入力を発生するためである。連続
する各ステージはこの機能を実行するとともに、
またこのブロツク用の桁上げ出力Cout1及び
Cout0を発生する。 第４図のステージ４に示される様に、各ビツト
に対しての最終的な桁上げ入力（表４のCout0
（ｋ，ｉ）及びCout1（ｋ，ｉ））が発生された段
階で、加算器に対しての桁上げ入力Cinが各ビツ
トに対する正しい桁上げ入力（表４のCin（ｉ＋
１））を選択する。そしてこの選択された桁上げ
入力は適切なＰビツトＰ（０）〜Ｐ(7)と排他的論
理和がとられ最終的な和Ｄ（０）〜Ｄ(7)が発生さ
れることを示している。 第４図から理解できるように、条件付き桁上げ
加算器Ｂと条件付き桁上げ加算器Ａとの主要な違
いは次の様である。条件付き桁上げ加算器Ｂに於
ては、ブロツクの大きさは２の累乗で増加する、
すなわち等比数列的に増加するものであるが、条
件付き桁上げ加算器Ａのブロツクの大きさは上記
した様に等差数列的に増加する。従つて条件付き
桁上げ加算器Ｂの全遅延時間は加算されるビツト
数の２を底とした対数に比例する。 条件付き桁上げ加算器Ａ，Ｂの桁上げは増分器
やプライオリテイ・エンコーダのいずれを構成す
る場合でも適用することができる。増分器はＮビ
ツトで表される数に１を加える回路であり、プラ
イオリテイ・エンコーダはＮビツト入力中の最優
先（最上位）ビツトをコード化した出力を発生す
る（例えば８ビツト−３ビツト・エンコーダ又は
10ビツト−４ビツト・エンコーダ）ものである。 第５図に条件付き桁上げ加算器Ｂにおける桁上
げを用いた増分器を示した増分器においては加算
における第２の入力Ｂ（０）〜Ｂ(7)を使用しない
ので、これらをゼロにセツトすることができる。
このとき第４図のステージ０で発生されるＫ，
Ｇ，Ｐは以下の様になる。 Ｋ＝Ａ・Ｂ＝０ Ｇ＝Ａ＋Ｂ＝Ａ Ｐ＝A_XOR＝Ａ 同様に、増分器を常にイネーブル状態にしたおく
場合には、Cin信号を“１”にセツトすることが
できる。この様にして、第４図に示した条件付き
桁上げ加算器Ｂから増分器としては論理的に冗長
なゲーウを全て除去することにより、第５図に示
した増分器を構成することができる。これと同様
の冗長ゲートの除去方法を用いて、第３Ａ図の条
件付き桁上げ加算器Ａを基に構成したものが第６
図に示した増分器である。第３Ａ図及び第３Ｂ図
に示した加算器と同様に、第６図の継続セルは各
ブロツクに於て必要なだけ何回でも使用すること
ができる。 第７図は条件付き桁上げ加算器Ｂの高速桁上げ
方式を用いた８ビツト−３ビツト・プライオリテ
イ・エンコーダを示す図である。上記した増分器
と同様に、Ｂ（０）〜Ｂ(7)入力は“０”にセツト
されており、桁上げ信号は“１”にセツトされて
いる。このプライオリテイエンコーダに於ては、
桁上げ入力は「イネーブル」として示されてお
り、本プライオリテイエンコーダをイネーブル状
態にしておく都合上反転されている。（つまりイ
ネーブル端子は実際にはアースされて“０”が与
えられているのである）。各出力セルは３状態バ
ツフア３０を備えており、対応するゲート４０に
よりイネーブルとされる。最初の４行に論理素子
により、８ビツト入力Ａ(7)〜Ａ(10)のうち、“１”
となつている最上位ビツトに対応するバツフア３
０のみがイネーブルされることが保証されてい
る。各出力セルの各３状態バツフア３０への入力
は各演算子入力のビツト番号に対応する適切に２
進重み付けされた信号を結線されている。この様
に、各３状態がバツフア３０は並列接続された３
個のバツフアで構成されており、３ビツト出力の
３本のエンコード出力線を形成している。各３状
態バツフア３０のイネーブル時の出力の設定は、
Ａ（０）桁は０，０，０に、Ａ(1)桁は０，０，１
に、等々、Ａ(7)桁の１，１，１に至る迄セツトさ
れている。そして各３状態バツフアへの３ビツト
入力のうち最下位の入力に対応する８個のバツフ
ア（各桁から１つずつ）の出力は共通接続されエ
ンコード（０）出力を形成し、中間重み付けされ
た（すなわち重み２）入力に対応する８個のバツ
フア（各桁から１つずつ）は共通接続されエンコ
ーダ(1)出力を形成し、そして最上位入力に対応す
る８個のバツフア（各桁から１つずつ）は共通接
続されエンコード(2)出力を形成している。そして
これら３本のエンコード・ラインは８ビツト−３
ビツト・エンコーダ機能を実行するための適切に
重み付けされた出力を供給し、適切にイネーブル
された３状態バツフア３０は入力語中にある
“１”のうち最上位にあるもののビツト位置に対
応する所望の優先順位を示す数を供給する。上記
した増分器と同様にして、各ビツトに対して適切
な数の３状態バツフアを追加することに加えて、
冗長ゲート除去の技法により、第３Ａ図に示した
条件付き桁上げ加算器Ａを基に第８図に示したプ
ライオリテイ・エンコーダを構成することができ
る。この場合にも、第８図に示した継続セルは各
ブロツクに於て必要に応じて何回も使用できる。 ［発明の効果］ 以上詳細に説明したように、本発明によれば、
比較的少ないゲート量で高速の加算回路を実現す
ることができる。

【図面の簡単な説明】

第１図は従来技術に係るリツプル・アダーの１
ビツト分を示す図、第２図は従来技術に係る桁上
げ先見加算器を示す図、第３Ａ図および第３Ｂ図
は高速桁上げを行なう加算回路を示す図、第４図
は本発明の実施例を示す図、第５図ないし第８図
は第３Ａ図、第３Ｂ図および第４図の加算回路を
応用した増分器およびプライオリテイ・エンコー
ダを示す図である。 Ａ，Ｂ……オペランド、Ｄ……和、Cin……桁
上げ入力、Cout……桁上げ出力。

Claims (1)

1. 【特許請求の範囲】 １ ２つのＮ桁のオペランドを加算する加算回路
   において、 下記の(A)ないし(C)： (A) 複数の第１のセル手段を有する１つの入力
   行：前記第１のセル手段の各々は前記２つのオ
   ペランドからの桁の第１の対を受け入れて、複
   数の第１の論理出力信号を後続の行中の隣接す
   るセル手段に与える； (B) 複数の第２、第３、第４のセル手段を有する
   複数の中間行： （Ｂ−１） 前記第２のセル手段は直前の行中
   の隣接するセル手段からの論理出力信号の内
   の選択されたものを自行中の隣接するセル手
   段へ渡し、前記直前の行中の前記隣接するセ
   ル手段からの論理出力信号の内の選択された
   ものを後続の行中の隣接するセル手段へ渡
   す； （Ｂ−２） 前記第３のセル手段は直前の行中
   の隣接するセル手段からの論理出力信号の内
   の選択されたものを後続の行中の隣接するセ
   ル手段へ渡し、前記直前の行中の前記隣接す
   るセル手段からの論理出力信号の内の選択さ
   れたものと自行中の隣接するセル手段からの
   前記論理出力信号の内の選択されたものを組
   み合わせて、第１の桁上げの出力信号の対を
   後続の行中の隣接するセル手段に与える； （Ｂ−３） 前記第４のセル手段は直前の行中
   の隣接するセルからの論理出力信号の内の選
   択されたものを後続の行中の隣接するセル手
   段へ渡す； (C) 複数の第５のセル手段を有する１つの出力
   行：前記第５のセル手段は先行する行中の隣接
   するセル手段からの選択された論理出力信号と
   第２の桁上げの入力信号とを組み合わせて最終
   的な合計された桁出力を生成する； を設け、 前記複数の中間行は前記入力行と前記出力行と
   の間に結合され、 １番目の中間行においては、前記第２、第３、
   及び第４のセル手段の内の選択されたものがＲポ
   ジシヨン毎に繰り返されるように配置されてお
   り、 前記１番目の中間行に結合された２番目の中間
   行においては、前記第２、第３、及び第４のセル
   手段の内の選択されたものがＳポジシヨン毎に繰
   り返されるように配置されており、 前記２番目の中間行に結合された３番目の中間
   行においては、前記第２、第３、及び第４のセル
   手段の内の選択されたものがＴポジシヨン毎に繰
   り返されるように配置されており、 前記繰り返しの長さ（Ｒ，Ｓ，Ｔ）は中間行の
   番号が１つ大きくなる毎に２倍になる幾何数列を
   形成する ことを特徴とする加算回路。