JPH06168101A

JPH06168101A - 加算装置及び加算方法

Info

Publication number: JPH06168101A
Application number: JP31969292A
Authority: JP
Inventors: Kazuo Hashimoto; 和夫橋本; Kazuo Takaragi; 和夫宝木; Masahiro Yamashita; 正弘山下
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1992-11-30
Filing date: 1992-11-30
Publication date: 1994-06-14

Abstract

(57)【要約】【目的】本発明は、桁上げ選択型加算器の設計手法を提
供する。【構成】本発明は、加算器選択回路を３入力のスイッチ
回路とすることにより上記目的を達成する。具体的な構
成は次の通り。（１）前段の加算器１（１０３），２（１０４）からの
桁上げ信号と前段の加算器選択回路１０６の出力のみを
入力とし、前段の加算器選択回路が選択した加算器(１
または、２)からの桁上げ信号を出力とするスイッチ回
路を構成する。（２）上記スイッチ回路をＡＮＤ回路とＯＲ回路とによ
り構成(一般にＡＯＲ回路と呼ばれている)する。【効果】入力データ長によらず同一構造の回路構成が可
能である。特に、暗号で必要とされる５１２ビットデー
タの四則演算に対しては有効である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、桁上げ選択型加算器に
係り、特に、暗号で必要とされる５１２ビットデータの
四則演算のような多倍長演算に用いて有効な加算装置及
び加算方法に関する。

【０００２】

【従来の技術】近年、半導体技術の発達により、高速な
加算回路を構成することは比較的容易である。従来よ
り、リプル桁上げ加算器，桁上げ先見型加算器，桁上げ
選択型加算器等、多くの手法が考案されている。例え
ば、ＨＷＡＮＧ著、堀越彌訳「コンピュータの高速演
算方式」近代科学社昭和５５年９月１日発行の８２
頁〜８５頁に桁上げ選択型加算器が紹介されている。

【０００３】この桁上げ選択型加算器は、長い語長の加
算器を固定長の加算ユニットに分け、各加算ユニットで
の加算を２個の加算器を用いて並列に実施する。ここ
で、一方は前段からの桁上げを仮定し、一方は桁上げな
しと仮定して加算を行う。２つの加算結果は加算器選択
回路を用いて一方を選択し、出力する。この加算器選択
回路は、上段の加算器１，２からの桁上げ信号を全て入
力とするように構成されている。ここで、加算器１とは
前段の桁上げ信号が０と仮定した加算結果Ｘ＋Ｙを出力
する加算器であり、加算器２とは前段の桁上げ信号が１
と仮定した加算結果Ｘ＋Ｙ＋１を出力する加算器であ
る。

【０００４】

【発明が解決しようとする課題】しかるに前記公知例で
は、上段の加算器１，２からの桁上げ信号をすべて入力
として加算器選択回路を構成しているので、加算ユニッ
ト数が増大するにつれて加算器選択回路の構造が急激に
煩雑になるという欠点がある。特に暗号で必要とされる
５１２ビットデータの四則演算に対しては本公知例は適
用出来ない。なぜならば、回路規模が膨大なものになる
からである。

【０００５】そこで、本発明は加算器選択回路を同一構
造のスイッチ回路とすることにより回路構成を簡略化
し、処理速度の高速化を図った桁上げ選択型加算器を提
供することを目的とするものである。

【０００６】

【課題を解決するための手段】本発明は、回路構成の簡
略化および、処理動作の高速化を図るため、加算器選択
回路を次のように構成する。すなわち、ある段の加算器
選択回路は、前段の加算器１，２からの桁上げ信号と前
段の加算器選択回路の出力のみを入力（３入力）とし、
前段の加算器選択回路が選択した加算器(１または、２)
からの桁上げ信号を出力とするスイッチ回路として構成
される。上記スイッチ回路は１対のＡＮＤ回路とＯＲ回
路より構成するのが望ましい。この回路は一般に、ＡＯ
Ｒ回路と呼ばれている。

【０００７】

【作用】桁上げ選択型加算器は、各加算ユニットでの加
算を一方は前段からの桁上げを仮定し、一方は桁上げな
しと仮定することにより、各加算ユニットを並列に実行
することができる。これにより、加算に要する時間は各
加算ユニットの語長分となり、高速化が図れる。例え
ば、語長５１２ビットの加算に対し各加算ユニットの語
長を１６ビットとした場合、リプル桁上げ加算器に比
べ、約５１２／１６＝３２倍の高速化が図れる。

【０００８】前段の加算器１，２からの桁上げ信号と前
段の加算器選択回路からの出力のみを入力とし、常に入
力数を一定(３本)にすることにより同一構造の加算器選
択回路を実現できる。これは、加算ユニットを多段化す
るのを容易にする。

【０００９】また、加算器選択回路をＡＯＲ回路で実現
することにより、回路規模の削減及び処理速度の高速化
が図れる。例えば、同回路をＡＮＤ回路２個、ＯＲ回路
１個で実現した場合、回路規模３、論理段数２となる
が、ＡＯＲ回路で実現した場合、回路規模１、論理段数
１.５となり、回路規模の削減および、処理速度の高速化
が期待できる。

【００１０】

【実施例】以下、本発明の実施例を、４ビット長加算ユ
ニット(×４)で構成された１６ビット加算器を例にと
り、図１〜図６を用いて説明する。図１は、本発明の一
実施例である加算装置の構成を示している。本加算装置
は、与えられた２つの入力すなわち１６ビット長数値ａ
（１０１）及びｂ（１０２）に対して、４ビット単位で
計算を行う加算器１ (１０３−１〜４)と加算器２(１０
４−１〜４），加算器１及び２から出力された２つの加
算結果に対して一方を出力するセレクタ１０５，セレク
タを制御する加算器選択回路１０６−１〜４からなり、
加算結果ｃ（１０７）を得る。なお、本文で扱う数値は
すべて２進数とし、最下位ビットを０とし、下位より順
番に１，２，３，…と番号を付けると約束する。加算器
１（１０３）においては０を固定値とし、加算器２
（１０４）においては１を固定値とする。ここで、加算
器１ (１０３）ではＸ＋Ｙが出力され、加算器２ (１０
４)ではＸ＋Ｙ＋１が出力されることに注意する。

【００１１】図２は、加算器１，加算器２の内部構造を
示した図である。加算器１ (１０３)，加算器２ (１０
４)は同一構造であり、同一の１ビット加算器３０２を
４個用いて構成されている。通常、本方式による加算器
をリプル桁上げ加算器と呼ぶ。信号３０１は、前段から
の桁上げ信号が存在するか否かを決定する。

【００１２】３０２は、１ビット加算器であり、Ｘ
(ｉ)，Ｙ(ｉ)，Ｓ(ｉ)を入力とし、内部で入力値の加算
を実行した後、Ｚ(ｉ)，Ｓ(ｉ＋１)を出力する。通常、
Ｓ(ｉ)を下位ビットへの桁上げと呼び、Ｓ(ｉ＋１)を上
位ビットへの桁上げと呼ぶ。

【００１３】３０３は、桁上げ信号である。なお、３０
３は下段の加算器選択回路１０６の入力となり、図１，
８，１１ではＳ₁₁(４)，Ｓ₁₂(４)，…と記述してあるこ
とに注意する。

【００１４】図３は、１ビット加算器３０２の内部構造
を示したものである。１ビット加算器３０２は、Ｘ
(ｉ)，Ｙ(ｉ)，Ｓ(ｉ)を入力とし、上位ビットへの桁上
げＳ(ｉ＋１)を出力する桁上げ回路４０１とＸ(ｉ),Ｙ
(ｉ)，Ｓ(ｉ＋１)を入力とし、加算結果Ｚ(ｉ)を出力す
る２組の排他的論理和回路４０２，４０３より構成され
る。つまり、Ｘ(ｉ)，Ｙ(ｉ)，Ｓ(ｉ＋１)を入力とし、
内部で数１に示す式の処理を実行し、出力する。

【００１５】

【数１】

【００１６】図４は、桁上げ回路４０１の内部構成を示
している。すなわち、排他的論理和回路５０１，ＡＮＤ
回路５０２，５０３及びＯＲ回路５０４によって構成さ
れており、Ｘ(ｉ)，Ｙ(ｉ)，Ｓ(ｉ)を入力とし、内部で
次式の処理を実行し、出力する。Ｓ(ｉ＋１)＝Ｘ(ｉ)・Ｓ(ｉ)＋Ｙ(ｉ)・Ｓ(ｉ)＋Ｘ(ｉ)・
Ｙ(ｉ) 図５は、加算器選択回路１０６の内部構造を示した図で
あり、１対のＡＮＤ回路６０１，６０２と１個のＯＲ回
路を組合わせたＡＯＲ回路からなっている。なお、加算
器選択回路の出力が入力されるＡＮＤ回路６０１の入力
側には極性反転回路６０４が接続されている。加算器選
択回路１０６は、前段の加算器１ (１０３)，加算器２
(１０４)からの桁上げ信号３０３と前段の加算器選択回
路１０６が出力した１ビット情報を入力とし、前段の加
算器選択回路１０６が選んだ加算器１ (１０３)又は、
加算器２ (１０４)からの桁上げ信号３０３を出力す
る。図５では、前段の加算器選択回路１０６の出力が０
の場合、加算器１ (１０３)が選ばれ、１の場合、加算
器２ (１０４)が選ばれる構成となっている。

【００１７】図６は、図１の加算装置の処理動作を示し
た図である。以下、動作を詳細に説明する。（１）１６ビットの入力データａ（０〜１５），ｂ（０
〜１５）を４ビット単位のデータａ(０〜３),ａ(４〜
７),ａ(８〜１１)，ａ(１２〜１５)；ｂ(０〜３)，ｂ
(４〜７)，ｂ(８〜１１)，ｂ(１２〜１５)に分割する。

【００１８】（２）４ビットデータａ(０〜３)，ｂ(０
〜３)を最上段の加算器１，加算器２に入力する。以
下、各４ビットのデータａ(４〜７)，ｂ(４〜７)；ａ
(８〜１１), ｂ(８〜１１)；ａ(１２〜１５)，ｂ(１２
〜１５)についても同様に各段の加算器１，２に各々
並列に入力する。ここで、加算器１とは前段の桁上げ信
号を０と仮定した加算結果Ｘ＋Ｙを出力する加算器であ
り、加算器２とは前段の桁上げ信号を１と仮定した加算
結果Ｘ＋Ｙ＋１を出力する加算器である。

【００１９】（３）各加算ユニットより、２組の４ビッ
ト加算結果Ｚを得る。ここで、各加算ユニットは並列に
加算処理が行われたことに注意する。

【００２０】（４）加算器選択回路は、前段の加算器選
択回路の選択信号と前段の加算器１，２からの桁上げ信
号を入力とし、前段の選択信号で選択された加算器(１
または２)からの桁上げ信号を出力することにより、２
組の４ビット加算結果Ｚの一方を出力する。

【００２１】本実施例では、前段で選択された加算器に
桁上げがない場合、加算器１が選択され、桁上げがある
場合、加算器２が選択される。また、１０６−１のＳと
は加算器１ (１０３−１)もしくは加算器２ (１０４−
１)のいずれかを決定する情報であり、Ｓ＝０の時、加
算器１ (１０３−１)が選ばれ、Ｓ＝１の時、加算器２
(１０４−１)が選ばれる。本発明の加算装置はＳ＝０の
時、ｃ＝ａ＋ｂを計算し、Ｓ＝１の時、ｃ＝ａ＋ｂ＋１
を計算する構造となっている。

【００２２】（５）入力データａ，ｂに対して、加算結
果ｃを上段より漸次に得る。

【００２３】なお、図１〜図６の実施例では、４ビット
長の加算ユニット４つで構成された１６ビット加算装置
を例にとり説明したが、加算ユニットの語長および、加
算ユニット数は任意に設定することができる。

【００２４】［変形例１]ここで、図４の桁上げ回路４
０１に対する変形例を挙げる。一般に、図２で示したリ
プル桁上げ加算器１０３，１０４は、下位ビットの桁上
げ信号を入力とし、次の桁上げ信号を出力する構造とな
っており、回路規模が小さくできるという利点がある
が、その反面処理時間がかかるという欠点がある。そこ
で、変形例として、各加算ユニットの桁上げ回路に桁上
げ先見回路を用いる。図７は、桁上げ先見回路４０２を
用いた加算器の内部構造を示した図である。

【００２５】この桁上げ先見回路は、数２に示すＰ
（ｉ），Ｇ（ｉ）及びＳ（ｏ）を入力とする。

【００２６】

【数２】

【００２７】Ｇ（ｉ）＝Ｘ（ｉ）・Ｙ（ｉ）そして、４ビットの桁上げ信号Ｓ（１）〜Ｓ（４）を同
時に生成する構造となっている。この方式は、処理時間
が短いという利点がある反面、回路規模が大きくなると
いう欠点もある。求められている速度を考慮して採用す
ればよい。

【００２８】［変形例２］本発明の加算器選択回路は同
一構造のスイッチ回路によって構成されるので、１つの
加算ユニットを１個のＩＣチップ上に構成し、複数のＩ
Ｃチップを基板上に直列に接続することにより、一枚の
基板上で本方式の加算装置を構成することができる。図
８は、４ビット長加算ユニット８０を４個用いて構成さ
れた１６ビット加算装置を１枚の基板８２上で実現した
例である。

【００２９】［変形例３］Ｍ＝５１２ビットの多倍長加
算装置を本方式で実現することもできる。本方式は、加
算ユニットの語長ｎを小さくすれば加算器１，加算器２
に要する時間が短くなるが、加算ユニット数（ｍ＝Ｍ／
ｎ）が増加し、加算器選択回路の処理回数が増加する。
これにより加算器選択回路に要する時間が長くなり、加
算装置の性能が低下する場合がある。しかし、次式によ
り、Ｍビットの加算装置における加算ユニットの語長ｎ
及び加算ユニット数ｍの最適数をみつけることができ
る。処理時間Ｔ＝（Ｍ／ｎ)＋ｎなお、上記式は、以下のようにして得られる。本発明の
加算装置の処理時間Ｔは、加算ユニットを構成している
加算器（加算器１，２を指す）の処理時間Ｔ₁と加算器
選択回路の処理時間Ｔ₂の合計で表せる。まず、桁上げ
回路（４０１）の処理時間＝１個の加算器選択回路（１
０６）の処理時間が成立する。ここで、加算器選択回路
の処理時間Ｔ₂＝１と考えると、ｎビット加算器の処理
時間Ｔ₁は約ｎ（桁上げの伝搬回数分）となる。また、
加算器選択回路がｍ段直列に並んだ場合、処理時間Ｔ₂
はｍとなる。以上より、本加算装置の処理時間は次のよ
うに表せる。Ｍ＝５１２ビットの加算装置をｎ＝３２ビットの加算ユ
ニット（加算器１，２を指す）で構成した場合、加算器
の処理時間Ｔ₁＝ｎ＝３２加算器選択回路の処理時間Ｔ₂＝Ｍ／ｎ＝ｍ＝５１２／
３２＝１６よって、本加算装置の処理時間Ｔ＝Ｔ₁＋Ｔ₂＝３２＋１
６＝４８同様に、Ｍビット加算装置をｎビット加算ユニットで構
成した時の処理時間Ｔは、ｎビット加算器の処理時間Ｔ₁＝ｎ加算器選択回路の個数（処理時間）Ｔ₂＝Ｍ／ｎとなる
ので、加算装置の処理時間Ｔ＝（Ｍ／ｎ）＋ｎこの関係をグラフで示したのが図９である。Ｍが５１２
ビットの場合、ｎ＝２２．６のときＴの最小値になる。
実際に加算装置を構成する場合、５１２の約数をとるた
めｎ＝１６、３２となる。すなわち、加算装置をｎ＝１
６または３２ビットの加算ユニットで構成したとき処理
時間Ｔが最小になり、効率の良い加算装置を実現でき
る。

【００３０】ここで、本発明と比較するために、従来の
桁上げ選択型加算器を４ビット長加算ユニット(×４)で
構成された１６ビット加算器を例にとりその内容を図１
３、図１４で詳細に説明する。

【００３１】図１３は、桁上げ選択型加算器の構成を示
している。本桁上げ選択型加算器は、与えられた２つの
１６ビット長数値ａ（７０１），ｂ（７０２）に対し
て、４ビット単位で計算を行う加算器１（７０３−１
〜４），加算器２（７０４−１〜４），加算器１，２
から出力された２つの加算結果に対して一方を出力する
セレクタ７０５、セレクタを制御する加算器選択回路
（７０６−１〜４）からなり、入力データａ，ｂの加算
結果ｃ（７０７）を得る。

【００３２】図１４は、処理動作を示した図である。以
下、動作手順を説明する。（１）１６ビットデータａ，ｂを４ビットデータａ(０
〜３),ａ(４〜７),ａ(８〜１１)，ａ(１２〜１５)；ｂ
(０〜３)，ｂ(４〜７)，ｂ(８〜１１)，ｂ(１２〜１５)
に分割する。

【００３３】（２）４ビットデータａ(０〜３)，ｂ(０
〜３)を加算器１ (７０３−１)，加算器２ (７０４−
１)に入力する。以下、ａ(４〜７)，ｂ(４〜７)；ａ(８
〜１１)，ｂ(８〜１１)；ａ(１２〜１５)，ｂ(１２〜１
５)についても同様に加算器１(７０３−２〜４)，加算
器２ (７０４−２〜４)に入力する。

【００３４】（３）各加算ユニットより、２組の４ビッ
ト加算結果Ｚを得る。ここで、各加算ユニットは並列に
加算処理が行われたことに注意する。

【００３５】（４）上段の加算器１，２からの桁上げ信
号Ｓ₁₁，Ｓ₁₂，Ｓ₂₁，…より、４つの加算器選択回路を
並列に作動させ、４ビット加算結果のうち一方を出力す
る。

【００３６】詳しくは、次の等式を満たすように加算器
選択回路を構成する。＝Ｓ＝Ｓ・Ｓ₁₂＋Ｓ₁₁ ＝Ｓ・Ｓ₁₂・Ｓ₂₂＋Ｓ₁₁・Ｓ₂₂＋Ｓ₂₁ ＝Ｓ・Ｓ₁₂・Ｓ₂₂・Ｓ₃₂＋Ｓ₁₁・Ｓ₂₂・Ｓ₃₂＋Ｓ₂₁・Ｓ₃₂＋
Ｓ₃₁ （＋：ビット毎の論理和・：ビット毎の論理積）ここで、本従来例ではＳ＝０の時、ｃ＝ａ＋ｂを計算
し、Ｓ＝１の時、ｃ＝ａ＋ｂ＋１を計算する構造となっ
ていることに注意する。（５）各加算ユニットより４ビット長加算結果を同時に
得、入力ａ，ｂに対する加算結果ｃを得る。

【００３７】次に、図１０に、本発明の加算装置と図１
３、図１４で説明した従来技術との性能の比較を示す。
まず、図１０の（Ａ）は、Ｍビット長の加算装置におけ
る処理時間Ｔの比較を示す。図１３、図１４に示す従来
技術の方式では、ビット長Ｍの小さいときは構成が簡単
なため高速処理が可能である。しかし、ビット長が大き
くなるにつれて本発明による方式の処理時間に近づき、
５１２ビットではほとんど同じになる。

【００３８】次に図１０の（Ｂ）はＭビット長の加算装
置を構成するのに必要なハードウェアの量を比較したも
のである。元々入力数が多いため、従来技術方式のほう
がハードウェア量は多いが、入力数の増加につれて、ハ
ードウェア量が指数関数的に増え、５１２ビット加算器
を作るのは不可能に近い。これに対して本発明の方式で
は、常に一定の割合でハードウェア量が増えるため、５
１２ビット長の加算器を作るのも十分可能である。この
ように、処理時間とハードウェア量の両観点から考えた
とき、本発明の方式は多倍長演算用の加算装置に適して
いることから明らかである。例えば２５６ビット長の加
算器でも十分な効果が得られる。

【００３９】〔応用例〕すでに述べたように、本発明の
加算装置は多倍長演算に有効である。一例として、５１
２ビットの数値を使用する暗号アルゴリズムＲＳＡ暗号
の演算に使用することができる。ここで、ＲＳＡ暗号と
は、数３をアルゴリズムとする暗号方式であり、通常、
Ｍ，ｎ，ｅとして５１２ビットの数値を使用する。

【００４０】

【数３】

【００４１】数３の演算方法を図１１に示す。図１１の
ステップ２の剰余乗算アルゴリズム、すなわちＭ₁・Ｍ₂
ｍｏｄｎの計算方法は図１２に示すとおりである。図
１２のステップ２のＸ＋Ｒ、Ｒ−Ｎ及びＲ＋Ｎの計算、
ステップ３のＲ＋Ｎの計算に、本発明の加算装置を使用
し、５１２ビット加算を実行することにより、高速処理
を図ることができる。

【００４２】以上述べたように、本発明の各実施例によ
り、次のような効果を得ることができる。

【００４３】（１）前段の加算器１，２からの桁上げ信
号と前段の加算器選択回路の出力のみを入力とし、前段
の加算器選択回路が選択した加算器(１または、２)から
の桁上げ信号を出力するスイッチ回路を構成することに
より、加算ユニットの数に関係なく同一の加算器選択回
路が構成できる。これにより、加算ユニットの追加が容
易である。

【００４４】（２）加算器選択回路は、ＡＯＲ回路１個
と極性反転回路１個で実現できる。これにより、従来の
加算器選択回路に比べて回路規模の削減が図れる。

【００４５】（３）加算器選択回路は、前段の加算器選
択回路の出力をもとに出力値を決定する為、前段の加算
器選択回路の出力値が決定するまでの遅れが生じる。し
かし、本加算器選択回路はＡＯＲ回路で実現できるた
め、ＡＮＤ回路及びＯＲ回路に比べて約１.３倍の高速
化が図れる(作用で述べた論理段数２：１.５より試
算)。これにより、従来の加算器選択回路に比べて同等
の速度が得られる。

【００４６】

【発明の効果】本発明によれば、回路構成が簡単で、か
つ処理速度の速い桁上げ選択型加算器を提供することが
できる。

【図面の簡単な説明】

【図１】本発明の一実施例になる加算装置の構成を示し
た図である。

【図２】図１における加算器１,２の概略図である。

【図３】図２における加算器１,２の詳細図である。

【図４】図３における桁上げ回路の詳細図である。

【図５】図１における加算器選択回路の詳細図である。

【図６】図１の加算装置の処理動作を示した図である。

【図７】図３で示した桁上げ回路の変形例を示す図であ
る。

【図８】本発明の一実施例になる桁上げ選択型加算器を
基板上で構成した図である。

【図９】本発明の加算装置におけるビット数と処理時間
の関係を示す図である。

【図１０】本発明と従来技術の性能を比較した図であ
る。

【図１１】本発明を応用したＲＳＡ暗号の演算手順を示
す図である。

【図１２】図１１の演算手順の過程の詳細を示す図であ
る。

【図１３】桁上げ選択型加算器の従来例を示した図であ
る。

【図１４】図１３で示した従来方式の処理動作を示した
図である。

【符号の説明】

１０３…加算器１、１０４…加算器２、１０５…セレク
タ、１０６…加算器選択回路、３０２…１ビット加算
器、４０１…桁上げ回路

Claims

【特許請求の範囲】

【請求項１】２つの加算器と１つの加算器選択回路およ
び１つのセレクタから構成されるｎビットの加算を行う
加算ユニットをｍ段直列に接続し、(ｎ×ｍ)ビットの加
算結果を出力するようにした加算装置において、各段の前記加算ユニットが、入力データを加算する第１
の加算器と、入力データの加算結果より１大きい値を出
力する第２の加算器と、前段の前記第１の加算器からの第１の桁上げ信号、前段
の前記第２の加算器からの第２の桁上げ信号および前段
の加算器選択回路からの出力に応じて前記第１の桁上げ
信号もしくは前記第２の桁上げ信号のいずれかを選択信
号として出力する加算器選択回路と、前記加算器選択回路からの選択信号に応じて、前記第１
の加算器もしくは前記第２の加算器のいずれかの出力を
前記加算ユニットの出力として選択するセレクタとを備
え、前記各加算ユニットが上段より漸次加算結果を出力する
ようにしたことを特徴とする加算装置。
【請求項２】請求項１記載の加算装置において、前記各
加算ユニットをＩＣチップとして形成し、該ＩＣチップ
を基板上にｍ段直列に接続することにより、(ｎ×ｍ)ビ
ットの加算結果を出力するように構成したことを特徴と
する加算装置。
【請求項３】各段毎に１対の加算器１，２と１個の加算
器選択回路及びセレクタを備えた加算ユニットを多段直
列に接続した加算装置において、前記加算器選択回路を、前段の加算器１，２からの桁上
げ信号と前段の加算器選択回路の出力のみを入力とし、
前段の加算器選択回路が選択した前記加算器１または２
からの桁上げ信号を出力とするスイッチ回路として構成
したことを特徴とする加算装置。
【請求項４】請求項３記載の加算装置において、前記ス
イッチ回路を１対のＡＮＤ回路とＯＲ回路とを含むＡＯ
Ｒ回路により構成し、前記ＡＮＤ回路の１つに極性反転
回路を介して前記加算器選択回路の出力を入力するよう
にしたことを特徴とする加算装置。
【請求項５】各段毎に１対の加算器と１個の加算器選択
回路及びセレクタを備えた加算ユニットを多段直列に接
続した加算装置において、前記各段の加算器選択回路への入力が前段の１対の加算
器からの桁上げ信号と前段の加算器選択回路の出力信号
の３つであり、該入力数が上位区分、下位区分にかかわ
らず常に一定であることを特徴とする加算装置。
【請求項６】各段毎に１対の加算器と１個の加算器選択
回路及びセレクタを備えｎビットの加算を行う加算ユニ
ットをｍ段直列に接続した加算装置において、前記各段の加算器が桁上げ先見回路を備え、ｎビットの
桁上げ信号を同時に生成するように構成されていること
を特徴とする加算装置。
【請求項７】各段毎に１対の加算器と１個の加算器選択
回路とセレクタとを備えた加算ユニットを多段直列に接
続した加算装置を用いて、多倍長データを一括して加算
する計算方法であって、前記各加算ユニットにおいて、各区分の加算を下位区分
からの桁上げありと仮定した加算器と桁上げなしと仮定
した加算器を用いて各区分の加算を並列に実行し、下位区分が選択した加算器の上位区分への桁上げ信号を
出力する加算器選択回路により得られた前記２つの加算
結果の一方を選択し、下位区分より順次加算結果を得ることを特徴とした多倍
長データの加算方法。
【請求項８】前段の桁上げ信号を０と仮定した加算結果
Ｘ＋Ｙを出力する加算器と、前段の桁上げ信号を１と仮
定した加算結果Ｘ＋Ｙ＋１を出力する加算器及び１個の
加算器選択回路とを備えた加算ユニットを多段直列に接
続した加算装置を用いた加算方法であって、各段の加算ユニットにより並列にデータの加算処理を行
なって、２組の加算結果を得るステップと、前記加算器選択回路において、前段の加算器選択回路の
出力信号と前段の１対の加算器からの桁上げ信号を入力
とし、前段で選択された前記１対の加算器のいずれか一
方からの桁上げ信号を出力することにより、前記２組の
加算結果のうち一方を出力するステップを含む加算方
法。
【請求項９】前記データが、５１２ビットの数値からな
るＲＳＡ暗号であることを特徴とする請求項８記載の加
算方法。