JPH06236255A - 並列桁上げ発生ネットワーク、並列加算器ネットワーク、桁上げ発生モジュール、マルチビット加算器ネットワークおよびモジュラー桁上げ伝ぱんユニット - Google Patents

Abstract

(57)【要約】 【目的】 速度を向上した高度に並列的な構造を有する
Ｎビット２進加算器を提供する。 【構成】 加算器は対応する演算数と桁上げビットの和
を形成する複数の並列モジューロ２加算器で構成する。
桁上げ入力は条件付き伝ぱん発生器とｌｏｇ₂２Ｎ演算
レベルで桁上げビットを生成する無条件桁上げ発生器に
より生成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は算術加算器回路分野に関
し、特に２進加算器ネットワークに関する。

【０００２】

【従来の技術】２進加算器ネットワークはディジタルコ
ンピュータの算術演算の基本である。必要な加算器演算
は膨大となるので、コンピュータの発展の歴史では、よ
り早い構成部分の技術を通してあるいは様々な補助ロジ
ックないし計算ネットワークを用いて基本的な加算器ユ
ニットを増分してネットワーク組織を向上することでよ
り早い加算器ネットワークを常に求めてきた。初期のデ
ィジタルコンピュータはｉ番目の加算器出力ビットを２
ビットを法とする加算により示すことのできる高速桁上
げ加算器を使用した。

【０００３】

【数１】

【０００４】ここでＡiとＢiは入力演算数のｉ番目のビ
ットで、Ｃi-1 は次の最低ビット合計からの桁上げであ
る。桁上げは先行段階の演算数（Ａi-₁，Ｂi-₁）と先行
段階桁上げＣi-2でＣi-1＝Ａi-1 * Ｂi-1＋Ｃi-2（Ａi-
1＋Ｂi-1）として示すことができる。ここで（* 、＋）
はそれぞれブール演算子（ＡＮＤ，ＯＲ）である。高速
桁上げビットのための時間は加算器の速度の制約要因と
なった。それらの欠点を克服するために後続の固定時間
加算器が導入されたが、それらの固定時間加算器は条件
付き合計及びキャリールックアヘッド（ＣＬＡ）加算器
の２つのカテゴリーに分類することができる。

【０００５】条件付き加算器は各々のビット合計Ｓi を
２回計算する。すなわち１つの合計のＳNiは桁上げビッ
トＣi はゼロであるという想定に基づいて行い、第２の
合計のＳEi はＣi＝１という想定の元に行う。図１は４
ビットスライス条件付き合計加算器の論理図である
（「演算入門」ワーサー、フリン、ホルト、ラインアル
ト、ウィンストン 1982年p77ffを参照のこと）。２つの
入力演算数はそれぞれＡ0、Ａ1、Ａ2、Ａ3とＢ0、Ｂ1、
Ｂ2、Ｂ3 の入力ビットで示される。各々の対の演算数
ビット（Ａi、Ｂi）は入力端子 110に加える。Ａ0、Ｂ0
は入力演算数最小ビットに対応し、Ａ3、Ｂ3は最上位ビ
ットに対応する。条件付き合計加算器は２つの基本的な
部分を含んでいる。すなわち出力でＳN0、ＳN1、ＳN2、
ＳN3、ＳN4とＳE0、ＳE1、ＳE2、ＳE3、ＳE4の条件付き
合計と条件付き桁上げの２つの集合を形成する条件付き
合計生成ユニット 130で、後者のグループはその対応す
る個々の条件付き合計発生器 141、143、145、147、149
の各々への非ゼロ繰入れの想定に基づいている。それら
の条件付き信号は出力ビットＳ0、Ｓ1、Ｓ2、Ｓ3と出力
桁上げビットＣ４に対応する個々の出力セレクタ161、1
63、165、167、169 からなる条件付き合計セレクタユニ
ットに加えられる。選択は繰入れビットＣ0 及びＡＮＤ
ゲート113とＯＲゲート115により条件付き合計に動作す
るその補数の／Ｃ0により制御される。図１の条件付き
４ビットスライス加算器の挙動を制御する論理式は次の
ようになる。

【０００６】

【数２】

【０００７】真の４ビット合計とキャリーアウトは次の
ブール式に従ってセレクタ・ユニット 15₀により選択さ
れる。 Ｓ0＝ＳE0Ｃ0＋ＳN0／Ｃ0 Ｓ1＝ＳE1Ｃ0＋ＳN1／Ｃ0 Ｓ2＝ＳE2Ｃ0＋ＳN2／Ｃ0 Ｓ3＝ＳE3Ｃ0＋ＳN3／Ｃ0 Ｓ4＝ＳE4Ｃ0＋ＳN4

【０００８】上記の概念は追加のビットに拡張すること
ができるが、上記の式と図１により示唆されるように複
雑さが付随して増大する。ＣＬＡ加算器はその簡潔性と
モジューラ性から最近では最も普及した集積回路実現法
であった。モジューラ性とは類似の並列装置を用いるこ
とで各々の演算数でビット数を比較的容易に拡張できる
ことを意味している。例えば図２の４ビットスライスＣ
ＬＡを考えてみる。４ビットスライス条件付き加算器の
図１と比較してＣＬＡが比較して簡潔であることが明か
に分かる。ＣＬＡ合計は以下の論理式により次のように
表すことができる。

【０００９】

【数３】

【００１０】そしてＣＬＡ桁上げは次のようになる。 Ｃi＋ＡiＢi＋Ｃi（Ａi＋Ｂi）ないし Ｃi＝Ｇi＋ＰiＣi ここで Ｇi＝ＡiＢi および Ｐi＝Ａi＋Ｂi

【００１１】上記のＣＬＡ合計式は２つの演算数（Ａ
i、Ｂi）のＥＯＲを形成することにより桁上げ項（Ｃi-
1）無しに直ちに評価することができる。桁上げ項（Ｃi
-1）は低次指標演算数（Ａi-1，Ｂi-1） と低次桁上げ
Ｃi-2の関数となる。その結果、加算を完了する時間は
一般に各々の合計ビットに対する繰入れビットの入手性
により支配される。Ｃiに付いての上記の式は反復式
で、すなわち現在値Ｃi+1内のものはそれ自身の過去の
値の関数である。これは次のように明示的に述べること
ができる。 Ｃi+1＝Ｇi＋ＰiＧi-1＋ＰiＰi-1Ｇi-2 ＋... ＋ＰiＰi
-1 ... Ｐ0Ｃ0 したがって図２の４ビットの場合は、主要出力けた上げ
のＣ４は次のように表すことができる。 Ｃ4＝Ｇ3＋Ｐ3Ｇ2＋Ｐ3Ｐ2Ｇ1＋Ｐ3Ｐ2Ｐ1Ｇ0＋Ｐ3Ｐ2
Ｐ1Ｐ0Ｃ0 以下を上の式に置換すると Ｇ0'＝Ｇ3＋Ｐ3Ｇ2＋Ｐ3Ｐ2Ｇ1＋Ｐ3Ｐ2Ｐ1Ｇ0 および Ｐ0'＝Ｐ3Ｐ2Ｐ1Ｐ0Ｃ0、 Ｃ4＝Ｇ0'＋Ｐ0'Ｃ0を得ることができる。これは図２の
Ｇ0'とＰ0'の出力端子の論理式を示している。

【００１２】図２に示すタイプの２つのネットワークを
８ビット合計を生成するモジュラーユニットとして使用
するならば、高次の４ビットネットワークに対する繰入
れビットを上記の式にしたがって形成されているであろ
う。高次のユニットＣ８の出力桁上げは、次のように表
すことができる。 Ｃ8＝Ｇ1'＋Ｐ1'Ｇ0'＋Ｐ1'Ｐ0'Ｃ0 ここでＧ1'とＰ1'は、次の高次のＣＬＡモジュラユニッ
トのＣＬＡ出力ペアである。モジューラ性は４つの４ビ
ットスライス加算器に対応し、必要な桁上げ情報、すな
わちＣ4，Ｃ8，Ｃ12とＰ"、Ｇ"を出力で生成する４グル
ープＣＬＡ発生器により拡張して、図２に示すタイプの
４つのモジュレータ加算器ユニットを用いて16ビットｃ
ｌｓ加算器を形成した。図３は４グループＣＬＡ発生器
を示し、４つの入力対（Ｇ'0Ｐ'0）（Ｇ'1Ｐ'1）（Ｇ'2
Ｐ'2）（Ｇ'3Ｐ'3）とＣ4，Ｃ8，Ｃ12と（Ｐ"、Ｇ"）に
対応した桁上げ出力を有する。ここで Ｇ12＝Ｇ'2＋Ｐ'2Ｇ1＋Ｐ'2Ｐ'1Ｇ'0＋Ｐ'2Ｐ'1Ｐ'0Ｃ0 及び Ｇ"＝Ｇ3＋Ｐ'3Ｇ'2＋Ｐ'3Ｐ'2Ｐ'1Ｃ0 Ｐ"＝Ｐ'3Ｐ'2Ｐ'1Ｐ'0 従って最上位繰出しビットのＣ16は論理的に次のように
形成することが出来、 Ｃ16＝Ｇ"＋Ｐ"Ｃ0 更に必要に応じて高次のモジュラーＣＬＡ加算器ユニッ
トにパスすることができる。

【００１３】図４はモジュラーＣＬＡ概念の64ビット加
算への論理的拡張を示したものである。合計16のモジュ
ラー４ビットスライスＳＬＡ加算器 200が並列に配列さ
れており、（Ａ0、Ｂ0）・・・（Ａ3、Ｂ3）、（Ａ4、
Ｂ4）・・・（Ａ7、Ｂ7）、（Ａ60、Ｂ60）・・・（Ａ6
3、Ｂ63）の入力演算数対とそれぞれ（Ｓ0、Ｓ1、Ｓ2、
Ｓ3）・・・（Ｓ60、Ｓ61、Ｓ62、Ｓ63）の４ビット出
力和と桁上げ生成／桁上げ伝ぱん対（Ｐ'0、Ｇ'0）・・
・（Ｐ'15、Ｇ'15） を生成する（Ｃ0，Ｃ16，Ｃ32，Ｃ
48）の繰入れビットを受ける。４つの対応するグループ
のＣＬＡ加算器 200の桁上げ出力情報をそれぞれ受け取
る４モジュラー４グループＣＬＡ発生器 250の第２論理
レベルは、その関連加算器 200のために必要な桁上げ情
報を４対の桁上げ生成／桁上げ伝ぱん対と［（Ｐ"0、
Ｇ"0），（Ｐ"1、Ｇ"1）および（Ｐ'2、Ｇ'2）］の必要
な桁上げ生成／桁上げ伝ぱん対から生成する。これから
は単一のＣＬＡ発生器 250からなる第３論理レベルが第
１、第２レベルに供給される３つの追加繰入れビットの
（Ｃ16，Ｃ32，Ｃ48）を生成する。このようにモジュラ
ー４ビットスライスＣＬＡ加算器を使用して高精度演算
に対応してきた。

【００１４】更に図１の基本的条件付き加算器ユニット
をモジュラー加算器として使用して、高次桁上げを定義
する論理式は同一なのでＣＬＡ発生器の概念を使用して
高精度加算に拡張することができる。例えば第２レベル
条件付き同一キャリアは次のように表すことができるこ
とが分かる（前掲ワーサ、フリン）。 Ｃ4 ＝ ＣN4 ＋ＣE4Ｃ0 Ｃ8 ＝ ＣN8 ＋ＣE8ＣN4 ＋ ＣE8ＣE4Ｃ0 Ｃ12 = ＣN12＋ＣE12ＣN8 ＋ＣE12ＣE8ＣN8＋ＣE12ＣE8
ＣE4Ｃ0 上記の式を実施するのに必要な論理は図３、４のＣＬＡ
発生器 250のものと同一なので、16ビット加算器を図５
に示すように実施することができる。加算器は、それぞ
れ４ビット対の演算数を受け取る並列に接続された４つ
の条件付き加算器100を有している。各々の加算器 100
は条件付き和発生器 130とマルチプレクサ150からなっ
ている。モジュラーグループ繰入れ対の［（ＣN4，ＣE
4），（ＣN8，ＣE8），（ＣN12，ＣE12）］は、16ビッ
ト加算を形成するのに必要なモジュラー繰入れビット
（Ｃ4、Ｃ8Ｃ、12）を生成するＣＬＡ発生器 250に供給
される。更に多くのビットに対応するのに必要な拡張
は、先述のＣＬＡ方式で明示した。

【００１５】

【発明が解決しようとする課題】費用効果的な並列高速
加算器が必要とされており、桁上げビット（及び従って
和）を生成するのに必要な処理段階数を比較的低コスト
で各々の演算数内のビット数の対数に比例するようにす
ることが非常に望まれる。また一定した論理入力、論理
出力を可能にし、靜的対固定速度事前チャージ／ディス
チャージ演算を可能にする論理構成が望ましい。本発明
の目的はそれらの目標を達成することである。

【００１６】

【課題を解決するための手段】各々が対応する演算数ビ
ット対と最終和桁上げ入力を受け取って合計する複数の
並列モジューロ２加算器からなる並列Ｎビット２進加算
器ネットワークを説明する。最終和桁上げビットは、入
力演算数ビットの対の論理的ＯＲ化に基づいて条件的桁
上げ伝ぱん項を生成する並列桁上げ伝ぱん論理アレィ
と、入力演算数ビット対のＡＮＤ化に基づく無条件桁上
げ生成論理ネットワークと、条件付き及び無条件桁上げ
項で並列に演算してモジューロ２並列加算器に並列に与
えられる最終和桁上げ項の集合を生成する論理アレィか
らなる桁上げ生成ネットワークにより並列に生成され
る。モジューロ２加算器へのＮ和桁上げ入力の最終集合
を生成するゲート遅延の数は［ｌｏｇ₂２^N］ であり、
加算器のスループットをかなり増大できる。

【００１７】

【実施例】

Ａ＝ＡN-1，ＡN-2，...，Ａ0 Ｂ＝ＢN-1，ＢN-2，...，Ｂ0 の２つのＮビット２進数演算数（Ａ，Ｂ）の和Ｓは、Ｓ
＝Ｓ1，ＳN-2，...，Ｓ0と表すことができる。ここで

【００１８】

【数４】

【００１９】は、次の最下位ビット対（Ａi-1，Ｂi-1）
のモジューロ２和からのｉ番目の演算数ビット値（Ａ
i，Ｂi） 及び繰入れビットＣi-1のモジューロ２和とし
て表されるｉ番目の和ビットの値を示す。従って「ＡＮ
Ｄ」に対してブール論理演算子（*）を使用し、「Ｏ
Ｒ」に対して（+）を使用することで、桁上げビットは
次のように表すことができる。 Ｃ0＝Ａ0*Ｂ0 Ｃ1＝Ａ1*Ｂ1＋（Ａ1＋Ｂ1）*Ｃ0 Ｃ2＝Ａ2*Ｂ2＋（Ａ2＋Ｂ2）*Ｃ1 ： Ｃi＝Ａi*Ｂi＋（Ａi＋Ｂ_i）*Ｃi-1 ： ＣN-1＝ＡN-1*ＢN-1＋（ＡN-1＋ＢN-1）*ＣN-2 ここで便宜のため次のようにすると Ｇi＝Ａi*Ｂi Ｐi＝Ａi＋Ｂi 上記の桁上げビット式は次のようになる。 Ｃ0＝Ｇ0 Ｃ1＝Ｇ1＋Ｐ1Ｃ0 Ｃ2＝Ｇ2＋Ｐ2Ｃ1 ： Ｃi＝Ｇ ： ＣN-1＝ＧN-1＋ＰN+1ＣN-2 （更に便宜のためにＰiＣ＝Ｐi*Ｃi とするために明示
的な「ＡＮＤ」演算子記号は省略していることに留意す
る。）この規約を以下の説明を通して使用する。

【００２０】上記の反復式は次のように表すことができ
る。 Ｃ0＝Ｇ0 Ｃ1＝Ｇ1＋Ｐ1Ｇ0 Ｃ2＝Ｇ2＋Ｐ2Ｇ1＋Ｐ2Ｐ1Ｇ0 Ｃ3＝Ｇ3＋Ｐ3Ｇ2＋Ｐ3Ｐ2Ｇ1＋Ｐ3Ｐ2Ｐ1Ｇ0 Ｃ4＝Ｇ4＋Ｐ4Ｇ3＋Ｐ4Ｐ3Ｇ2＋Ｐ4Ｐ3Ｐ2Ｇ1＋Ｐ4Ｐ3Ｐ2Ｐ1Ｇ0 ： Ｃ＝Ｇi＋ＰiＧi-1＋ＰiＰi-1Ｇi-2＋ＰiＰi-1Ｐi-2Ｇi-3 ＋．．．＋ＰiＰi-1Ｐi-2．．．ＰiＧ0 : この式の集合は一方で次のような行列で表すことができ
る。

【００２１】

【数５】

【００２２】あるいは単に ｃ＝Ｐ（Ｎ）ｇ ここでｃは桁上り桁ベクタ、ｇは桁上り発生器桁ベク
タ、Ｐ（Ｎ）は低次三角ＮＸＮ伝ぱん行列である。従っ
てｇ＝［Ｇ0Ｇ1Ｇ2・・ＧN-1］T＝［Ａ0Ｂ0Ａ1Ｂ1Ａ2Ｂ
2...ＡN-1ＢN-1］Tは、高いときは繰出しを生成する演
算数ビット対の「ＡＮＤ」化を示す。要素が伝ぱん制御
変数を示す行列Ｐは、繰出しを高次ビットに対して伝ぱ
んする手段を記述するものである。Ｐ行列は疎低三角行
列の積に因数分解することができる。例えば

【００２３】

【数６】

【００２４】

【数７】

【００２５】従って各々の２進増分で２^k≦ｒ≦２^k+1、
Ｐ(r) は示した形式の（ｋ＋１）低次三角行列に因数分
解することができる。これらの因数分解式は図６、７、
８の流れ図で示すことができる。図６はＰ(4) の因数分
解により示される４ビット桁上げ伝ぱん過程に対応して
いる。この過程への入力は、下部に示す［Ｇ0 Ｇ1 Ｇ2
Ｇ3］Tの桁上げ発生器ベクタからなっている。矢印を有
する対角線は、対応するラベルづけされた式で原点のノ
ードのデータ上の複数（「ＡＮＤ」）演算に対応する。
ノード間のラベルなしの垂直線は伝送経路を示し、ｄｔ
の修正は低次ノードから高次ノードに伝送されない。全
てのノードは総和（「ＯＲ」）分岐点である。例えばＣ
1＝Ｇ1＋Ｐ1Ｇ0 およびＣ3＝Ｐ3Ｐ2（Ｇ1＋Ｐ1Ｇ0）＋
（Ｇ3＋Ｐ3Ｇ2）＝Ｐ3Ｐ2Ｐ1Ｇ0＋Ｐ3Ｐ2Ｇ¹＋Ｐ3Ｇ2＋
Ｇ3である。繰出しベクタ［Ｃ0 Ｃ1 Ｃ2 Ｃ3］^Tは上部
出力ノードにある値により示される。

【００２６】図７、８はそれぞれ８および¹6ビット桁上
げ生成過程を示すＰ(8)とＰ(16) の流れ図を示したもの
で、明かに大きなビット数の流れ図は詳述した原理を拡
張することで同様に生成することができる。各々の２進
増分２^k≦ｒ≦２^k+1−１あるいは演算数で使用するビッ
ト数のそれぞれ２倍について、１つの追加疎低次三角行
列がＰ(r) 行列の因数分解形式を示すために必要とな
る。従って２^k≦ｒ≦３、Ｐ^(r)要素に付いては２行列、
４≦ｒ≦７、Ｐ(r)要素に付いては３行列、２^k≦ｒ≦２
^k+1−１、Ｐ^(r)要素に付いては（ｋ＋１）行列が必要で
ある。

【００２７】各々の因数分解行列演算は図６、７、８に
示すノードの行に対応する。最低（ゼロ）レベルノード
は入力桁上げ生成ベクタ値ｇに対応する。ノードの次の
レベルの値は上記の例の右端の因数分解行列が入力生成
ベクタｇ上で演算するならば得られる列ベクタに対応す
る。同様にノードの第２レベルは、第２の右端が、その
右側の積から生じるベクタ上で演算される行列を因数分
解するならば得られる値に対応した値を有している。後
続のレベルでも同様である。一般にｋ＋１因数分解行列
（段階）が各々の演算数の２^k+1 に対して必要で、すな
わちＮビット演算数について［ｌｏｇ₂Ｎ］が必要とな
る。図６、７、８の流れ図は、図９〜11に示す論理ネッ
トワーク構造をも示している。

【００２８】図９は例えばＧl,k をその出力で生成する
図８のノードｌ，ｋにある一般的な節点プロセッサ10を
示したものである。プロセッサ10は入力としてＧ_{l-1 ,}
ｋ−２^l-1，Ｇ_l-1,kおよびＰ_kＰ_k-1・・・Ｐ_k-2 ^l-1をそ
れぞれその入力端子11、12、13で受け取る。「ＡＮＤ」
ゲート16及び「ＯＲ」はそれらの入力を演算して出力14
で次のブール関数をもたらす。 Ｇ_l,k ＝Ｇ_l-1,k＋Ｐ_kＰ_k-1・・・Ｐ_k-2 ^l-1Ｇ_l-1,_k-2
^l-1

【００２９】図10は４つの行（０−３）と８つの列（０
−７）を有する８ビット桁上げ発生器の実施例である。
行１−３はそれぞれ７、６、４節点プロセッサ10からな
り、各々のタイプは図９に示す通りである。行０はＧ0,
k＝Ａk、Ｂk を形成しライン11のプロセッサ10に供給す
る｛Ａk、Ｂk｝の対応する演算数ビット対を入力端子30
1で受け取るように配置された８つのＡＮＤゲート20か
らなる。行１のプロセッサ10はまた入力ライン 305のＰ
7 を通して７つの伝ぱん変数Ｐを受け取る。伝ぱん変数
Ｐk は行１、ライン13の列ｋにあるプロセッサ10にライ
ン12により供給されるＧ0,k-1 と共に入力として与えら
れる。１、ｋにあるプロセッサ10の出力は次の通りであ
る。

【００３０】Ｇ1,k＝Ｇ0,k＋ＰkＧ0,k-1 同様に行２のプロセッサ10には行１の出力が入力ライン
30₇からＰ76を通した伝ぱん変数Ｐ21と共に加えられ
る。２、ｋにあるプロセッサ10の出力は次の通りであ
る。

【００３１】Ｇ2,k＝Ｇ1,k＋ＰkＰk-1Ｇ1,k-2 同様に３、ｋのプロセッサ10は低レベル・プロセッサと
入力ライン 309に供給されるＰ4Ｐ3Ｐ2Ｐ1からＰ7Ｐ6Ｐ
5Ｐ4の伝ぱん変数により与えられる入力から次の出力を
生成する。 Ｇ3,k＝Ｇ2,k＋ＰkＰk-1Ｐk-2Ｐk-3Ｇ2,k-4 桁上げ出力Ｃ0 はライン 303の位置０、０のＡＮＤゲー
ト20から直接得ることが出来、Ｃ1 は位置１、１のプロ
セッサ10の出力ライン14から、Ｃ2とＣ3はそれぞれ一
２、２及び２、３のプロセッサ10から、そしてＣ4化ら
Ｃ₇は行３のプロセッサ10の出力から得ることができ
る。

【００３２】図６、７、８の流れ図及び図10の桁上げ発
生器 300に関して、８ビット桁上げ発生器 300のアーキ
テクチャと構成は各々の演算数のビット数が倍増される
度に追加の行を無限に追加することで拡張することがで
きることが明かである。各々の行で必要な並列プロセッ
サ数を表１にまとめる。

【００３３】

【表１】

【００３４】図11は図10の８ビット桁上げ発生器に伝ぱ
ん変数を供給するのに適した８ビット伝ぱん発生器を実
現する論理回路である。伝ぱん発生器 400は入力演算数
ビット対｛Ａk、Ｂk｝から次のように伝ぱん変数Ｐ1、
Ｐ2、・・・Ｐ7を形成するのに使用する７ＯＲゲート40
を行０に含んでいる。Ｐk＝Ａk＋Ｂk 集合｛Ｐk｝は出力ライン307上で得ることができる。次
の行はＡＮＤゲート50からなっている。行１のｋ番目の
ＡＮＤゲートは行０のｋ番目及びｋ−１番目の出力を受
け取り、その出力 307でＰkＰk-1を形成する。同様に行
２のｋ番目のプロセッサは行１のｋ番目とｋ−２番目の
出力を受け取って出力 309にもたらされる｛ＰkＰk-1Ｐ
k-2Ｐk-3｝の伝ぱん変数の集合を形成する。

【００３５】プロセッサ 400の構成とアーキテクチャは
図11の構造を左に拡張し、入力演算数ビット数が倍増さ
れる度にＡＮＤゲート50の追加行を追加することにより
拡張して更に多くの演算数ビットに対応することができ
る。行毎に必要なゲート数を表２に示す。

【００３６】

【表２】

【００３７】図12は２つの演算数ビットの完全ビット和
（Ａk、Ｂk）及び排他的ＯＲ（ＥＯＲ）ネットワーク6
1、62からなる繰入れビットＣｋを形成する論理ネット
ワーク60を示す。ＥＯＲネットワーク61はモジューロ２
は

【００３８】

【数８】

【００３９】を形成し、ネットワーク62はその出力に以
下をもたらす。

【００４０】

【数９】

【００４１】さきに説明した加算ネットワーク60、桁上
げ発生器 300及び伝ぱん発生器 400に基づいて完全並列
２進加算器を次のように２つのＮビット演算数を受け取
るように構成した図13に示すように定義することができ
る。 Ａ＝Ａ0Ａ1Ａ2・・・ＡN-1 Ｂ＝Ｂ0Ｂ1Ｂ2・・・ＢN-1 演算数ＡとＢは伝ぱん発生器 400、桁上げ発生器 300及
び加算ユニット 500の入力に加えられる。伝ぱん発生器
400と桁上げ発生器 300は先の説明にしたがって構成す
る。加算ユニット 500はＮ１ビットプラスに繰入れビッ
トＥＯＲネットワーク60をそれぞれ図12で説明したよう
に含んでいる。各々のＥＯＲネットワーク60への繰入れ
は桁上げ発生器 300の適切な出力端子により提供され
る。伝ぱん変数は２つの入力演算数Ａ、Ｂにより決定さ
れるように伝ぱん発生器 400により桁上げ発生器 300に
与えられる。加算ユニット 500の出力は次の通りであ
る。Ｓ＝Ｓ0Ｓ1・・・ＳN-1

【００４２】

【数１０】

【００４３】桁上げＣN-1 は出力で、演算数Ａ、Ｂのビ
ット数を拡張する際に使用するあふれビットとして得る
ことができる。桁上げ発生器 300の実施例ではモジュラ
ー中間規模集積回路技術を使用する。例えば図８の流れ
グラフを点線で示すように７つの小部分に適切に小区分
することで、回路実現へのモジュラー構築ブロック方法
のベースを形作る４ビットワイドで２レベル深さのモジ
ュールを定義することができる。４ビットワイドの区分
は任意的なもので、説明するモジュラー性の原理の説明
を可能にする最低レベルのモジュラー化を示すもので、
主に説明のために選んだものである。

【００４４】図14は図９に示したタイプの２層のｍ節点
プロセッサ10からなるｍビットワイド、２レベルモジュ
ール ₅₀₀のブロック図である。５組のｍ入力ラインが収
納されており、入力 501は対応するｌレベルの出力の
｛Ｇl,k｝を受取り、入力503は２l-1 で置き換えた｛Ｇ
_l,k-2 ^l-1｝のｌレベル出力を受取り、入力505、507はそ
れぞれ次の条件付き桁上げ項を受取る。

【００４５】

【数１１】

【００４６】入力509は（ｌ＋１）番目の内層出力項の
（２^lで置換した）｛Ｇ_l+1,k-2 ^l｝を受け取る。出力ラ
インは２組あり、出力 511は第１の層の出力項｛Ｇl+1,
k｝ に対応し、出力 513は第２層（ないしモジュール）
の出力の｛Ｇl+2,k｝に対応する。図15は４ビットワイ
ド（ｍ＝４）２層モジュール 500を使用した桁上げ発生
器300の相互接続図である。各々の論理装置 520は｛Ｇ
k｝ を形成するのに使用する１組の４ユニット20ＡＮＤ
ゲートを示す。

【００４７】図15は、ゼロレベル（ｌ＝０）入力の｛Ｇ
0,k｝ から第２レベル（ｌ＝２）出力｛Ｇ2,k｝に関し
た行列式を示す図16及び第２レベル出力から第４レベル
出力の｛Ｇ4,k｝ に関した行列式を示す図17を見ると理
解できる。図16では２つの16× 16行列（Ｐ₁ ⁽¹⁶⁾、Ｐ₂
⁽¹⁶⁾）がそれぞれ、16の４ × ４小行列に区分されてい
る。各々の非ゼロ値小行列は、 500モジュール内で行わ
れる単層４ビットワイド演算に対応する。右側の行列の
小行列は第１層の演算に対応し、左側のものは先述した
第２層の演算に対応する。同様に図17の右側の集合の小
行列は第３レベル（ｌ＝３）演算に対応し、左側の集合
は第４レベル（ｌ＝４）演算に対応する。それらの式は
個々のモジュール 500の入力をその出力に関連付けるこ
とで相互接続情報をもたらす。

【００４８】例えば座標（１、３）で識別される図15の
第１の行のモジュール 500の入出力関係を考える。 Ｇ2,8-11 = Ｐ2.32*Ｐ1.21Ｇ0.0-3+Ｐ2.32*Ｐ1.22Ｇ0,4
-7+Ｐ2,33Ｐ1.32Ｇ0,4-7+ Ｐ2,33Ｇ0,8-11 Ｐ2.32*Ｐ1.21=0なので

【００４９】

【数１２】

【００５０】なぜならば

【００５１】

【数１３】

【００５２】後者の式はモジュール 500(1,3) への必要
な入力を表す。右側の最初の式は２つだけの非ゼロ積の

【００５３】

【数１４】

【００５４】を示し、従って

【００５５】

【数１５】

【００５６】が入力として必要となる。第２の式は

【００５７】

【数１６】

【００５８】を必要とし、第３の式は入力４重項［Ｇ0,
8 Ｇ0,9 Ｇ0,10 Ｇ0,11］Tおよび３重項

【００５９】

【数１７】

【００６０】を必要とする。要約すると図15に示すよう
に必要入力はＧ0,8-11，Ｇ1,6-7，Ｇ0,7および

【００６１】

【数１８】

【００６２】となる（図15に関して出力キャリアの｛Ｃ
k｝は｛Ｇ4,k｝ と等しいことに留意する）。モジュー
ル 500(2,4)に対する同様の解析から次の式が生じる。

【００６３】

【数１９】

【００６４】図15に示すモジュール 500（２、４）に対
する相互接続が生じる。図18は３層の８ビットワイド２
層モジュールを用いた64ビット桁上げ発生器の簡潔な相
互接続図である。４ビットワイド２層の例で示した同一
方法で桁上げ発生器 300行列を区分することで相互接続
の詳細を得ることができる。しかし64ビットの場合は、
図18の３つの層に対応する３組の式を使用する必要があ
る。わずかに異なるモジュラー製を使用した別の実施例
を図19に示す。説明のため、24ビット加算器ネットワー
クを示しており、各々が図１で説明したように［（Ａ0-
7，Ｂ0-7）（Ａ8-15，Ｂ8-15），（Ａ16-23，Ｂ16-2
3）］の２つの８ビット演算数を受け取り、各々が２つ
の条件付き８ビット和（ＳE，ＳN）を出力する３つの８
ビット条件付き加算器ネットワークと、２状態桁上げ信
号により制御される各々の条件付き加算器ユニットのＳ
EないしＳNを選択するマルチプレクサ・ユニット 160
と、各々が２つの８ビット演算数を受け取り、その出力
で最高桁上げを例えばその関連２：１ＭＵＸ160を制御
する（Ｃ0、Ｃ1、・・・Ｃ7）の可能な集合から生成す
る桁上げ発生器 400からなる桁上げ及び伝ぱん生成ユニ
ット 600からなる。最低次（右端）ＭＵＸ 160はモジュ
ラー製の考察から各々の８ビット条件付き加算器 141は
関連ＭＵＸ 160でパッケージする必要があることがあ
り、その場合その制御は入力桁上げの欠如によりＳN 出
力は常に有効となるので低く設定されることを示すため
に点線で示していることに留意する。事実上、ユニット
141、160、600 の３つの垂直グループ化の各々は、モジ
ュラー加算器と繰出し発生器 700を構成しており、演算
数ビットと繰入れビットの２つのその関連フィールドを
必要とする。それらのユニットのタンデムな集合により
完全な加算器ができる。出力和は25ビット和Ｓ0-7，Ｓ8
-15，Ｓ16-23，Ｓ24荷より示される。

【００６５】繰入れビット（Ｃ−１，Ｃ７，Ｃ15）をユ
ニット 600に収納するため、基本行列と流れ図に若干の
変更を加える必要がある。図19の右端に示したユニット
600を考えると、必要な行列は次の形式を持つ。

【００６６】

【数２０】

【００６７】Ｃ-1の繰入れがゼロ（存在しない）なら
ば、第１の行と列はゼロとなることに留意する。またＰ
0＝Ｃ-1であるので、Ｃ-1＝０ ならばＰ０とその全ての
積項は消去する。従ってＣ-1＝０の場合、ネットワーク
300、400は先のように定義される。行列の形式の場合Ｃ
-1＝１ならば、桁上げ発生器ネットワーク 300と伝ぱん
発生器 400は先述のように同一論理構造を持つ。例えば
図20は、図19で８ビット条件付き加算器ユニット 141に
付いて示したように４ビット条件付き加算器ユニットを
連結するのに適した入力桁上げビットＣ-1を有する４ビ
ット桁上げ発生器 300に対応する流れ図を示している。
出力桁上げＣ3 を生成するのに必要なステップは実線で
示し、点線はさきに示した他の可能なしかし必要としな
い処理ステップを示している。これは処理モジュール10
を用いた図21に示す繰出し発生器構造300'を示すもので
ある。

【００６８】図22、23はそれぞれ図19の加算器ネットワ
ークで使用した８ビットユニットの簡略化した繰出し発
生器構造 300の対応する流れ図である。図24は図19の８
ビット加算器モジュール 700で使用するのに適した伝ぱ
ん発生器400'の簡潔なブロック図である。４ビット繰出
し発生器300'で必要とされる伝ぱん項の小集合の（Ｐ3
Ｐ2Ｐ1Ｐ0、Ｐ3Ｐ2、Ｐ3、Ｐ1）もこのユニットから得
ることができる。図19の全ての連結ユニット 600には同
一流れ図と論理ネットワークを適用することができる。
しかし図19の右端の最下位ユニット 600の場合は、先の
段階からの繰入れは存在しないのでＣ-1＝０である。他
の段階に付いては、先の節の繰出しを繰入れとして使用
することができる。図19に例を示すように拡張演算数精
度を増すためにモジュラー桁上げ伝ぱんの概念は、ユニ
ット 600、160、141を所望の語長に実施することにより
４、８、16などのどの様な大きさのモジュラービットの
使用にも適用することができる。また所定の 700セクシ
ョンの関連ユニット 600、160、141は同一語長であるが
それとタンデムに接続した他の 700ユニットでは必ずし
も同一語長ではない混合システムを構成することもでき
る。当業者には以上あるいは同様の変形が明かとなろ
う。

【図面の簡単な説明】

【図１】従来の４ビットスライス条件付き総和加算器の
論理図である。

【図２】従来の４ビットスライス・キャリールックアヘ
ッド（ＣＬＡ）加算器の論理図である。

【図３】従来の４グループＣＬＡ発生器の論理図であ
る。

【図４】フル・ＣＬＡを使用した従来の64ビット加算器
のブロック図である。

【図５】４グループＣＬＡ発生器を使用した従来の16ビ
ット条件付き総和加算器のブロック図である。

【図６】４ビット桁上げ過程の流れ図である。

【図７】８ビット桁上げ過程の流れ図である。

【図８】16ビット桁上げ過程の流れ図である。

【図９】一般的な桁上げ発生器ノード実施の論理図であ
る。

【図10】８ビット桁上げ発生器のブロック図である。

【図11】８ビット伝ぱん発生器の論理図である。

【図12】桁上げ入力を有する１ビット加算器の論理図で
ある。

【図13】完全並列加算器のブロック図である。

【図14】ｍビット２レベル桁上げ発生器モジュールを示
す図である。

【図15】４ビット２レベル・モジュールを使用する16ビ
ット桁上げ発生器の相互接続を示す図である。

【図16】４ビット２レベル・モジュールで使用する16ビ
ット第１、第２レベル桁上げ生成行列の区分を示す図で
ある。

【図17】４ビット２レベル・モジュールで使用する₁₆ビ
ット第３、第４レベル桁上げ生成行列の区分を示す図で
ある。

【図18】８ビット２レベル・モジュールを使用する₆₄ビ
ット桁上げ発生器の相互接続を示す図である。

【図19】他の実施例のブロック図である。

【図20】４ビット桁上げ発生器に対応する流れ図であ
る。

【図21】繰り出し発生器の構造を示す図である。

【図22】８ビットユニットの簡略化下繰り出し発生器の
対応する流れ図である。

【図23】８ビットユニットの簡略化下繰り出し発生器の
対応する流れ図である。

【図24】伝ぱん発生器の簡潔なブロック図である。

【符号の説明】

150:マルチプレクサ 300:桁上げ発生器 400:伝ぱん発生器 500:加算ユニット

Claims (5)

【特許請求の範囲】
1. 【請求項１】 (a) 第１と第２のＮビット２進演算数を
   受け取る手段と、(b) 前記第１と第２の演算数の対応す
   るビットの対に対する並列論理演算により条件つき桁上
   げ伝ぱん項を生成する桁上げ生成論理ネットワークアレ
   ィと、(c) i) 前記第１と第２の演算数の対応するビッ
   トの前記対に対する並列演算により無条件桁上げ項を生
   成する論理ネットワークと、ii) 前記無条件桁上げ項を
   受け取って演算し、最終和桁上げ項の並列集合を生成す
   る論理ネットワークアレィとからなる最終和桁上げビッ
   トを生成する桁上げ発生器論理アレィとからなり、マル
   チビット２進加算器で使用する並列桁上げ発生ネットワ
   ーク。
2. 【請求項２】 (a) 第１と第２と第３の入力集合を有
   し、前記第１と第２の入力集合は第１と第２の入力演算
   数を受け取り、前記第３の入力集合は並列桁上げ生成ネ
   ットワークの出力に接続されて並列桁上げビットを受け
   取り入力演算数の和を生成する並列加算装置と、(b) 第
   １と第２の演算数を有し、その出力端子で桁上げビット
   の並列集合を生成する並列桁上げ生成ネットワークとか
   らなる並列加算器ネットワーク。
3. 【請求項３】 (a) それぞれ第１と第２と第３の入力を
   有し、前記第１と第２入力は対応する次の低レベルの出
   力から別個の部分桁上げ項に接続され、前記第２の入力
   は次の低次層出力から関連置換部分桁上げ項に接続さ
   れ、前記第３の入力は次の低次の層の出力から関連条件
   つき桁上げ項に接続され、各々の出力で次のレベルの部
   分桁上げ項を生成する同等の数の第１と第２レベル桁上
   げ発生器プロセッサと、(b) 前記第１レベルの桁上げ発
   生器プロセッサの各々の前記出力を対応する前記第２レ
   ベルプロセッサの第１の入力に接続する手段と、(c) 前
   記第１と第２レベルプロセッサ出力を外部端子の第１の
   集合に接続する手段と、(d) 前記第１と第２レベルプロ
   セッサの第２と第３の入力を外部端子の第２の集合に接
   続する手段と、(e) 前記ネットワークとユニット化構造
   としてサポートする手段とからなる桁上げ発生モジュー
   ル。
4. 【請求項４】 (a) ２フィールドの演算数ビットと入力
   桁上げビットを受け取って和と出力桁上げを生成すると
   ともに、条件つき総和加算器と、入力桁上げにより制御
   される条件つき総和選択手段と、前記出力桁上げを前記
   演算数ビットと入力桁上げビットから生成する並列桁上
   げ発生器装置とを備えたモジュラー加算器と繰り出し発
   生ユニットと、(b) 先行するモジュラー加算器と繰出し
   発生器の繰出しが表明されたときに選択される繰入れに
   基づいて前記条件つき和の制御入力に前記繰出しが接続
   され、さもなくば他の条件つき和を選択し、前記選択和
   と最終繰出しは所望の加算器出力を示すようにタンデム
   に接続された複数の前記モジュラー加算器と繰出し発生
   器ユニットとからなるマルチビット加算器ネットワー
   ク。
5. 【請求項５】 (a) 前記桁上げビットを生成するのに必
   要な最小のプロセッサ要素集合を備えた演算数ビットと
   繰入れビットの２つの集合から出力桁上げビットを生成
   し、関連した伝ぱん変数の最小集合により制御される簡
   略化桁上げ発生器と、(b) 前記簡略化桁上げ発生器を制
   御するのに必要な最小の伝ぱん変数の集合を生成するの
   に必要な最小の論理要素集合を備えた演算数ビットと繰
   入れビットの２つの集合から伝ぱん制御変数を生成する
   簡略化伝ぱん発生器とからなるモジュラーマルチビット
   加算器ネットワークで使用するモジュラー桁上げ伝ぱん
   ユニット。