(57)【特許請求の範囲】
【請求項１】
冗長２進数の演算を行う演算精度ｎ桁の並列型の除算器であって、
ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器を、１桁づつシフトして接続して、ｎ段に構成してなる除算回路と、
前記除算回路を構成するｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々に対応して設けられたｎ個の単位比較器からなる演算判断回路であって、当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余と除数との減算結果であって冗長２進数である２ビットで表現された減算結果に基づいて、前記２ビットを比較することにより、当該ｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々における減算結果を判断し、当該減算結果が正又は０である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該減算結果が負である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる減算判断回路とを有する
ことを特徴とする並列型の除算器。
【請求項２】
冗長２進数の演算を行う演算精度ｎ桁の並列型の除算器であって、
ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器を、１桁づつシフトするように、ｎ段に構成してなる除算回路と、
前記除算回路を構成するｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々に対応して設けられたｎ個の単位比較器からなる演算判断回路であって、当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余と除数との減算結果であって冗長２進数である２ビットで表現された減算結果に基づいて、前記２ビットを比較することにより、当該ｎ桁の並列型の減算器に入力される被減数と減数の大小を判断し、当該被減数が減数より大きいか又は減数と等しい場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該被減数が減数より小さい場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる減算判断回路とを有する
ことを特徴とする並列型の除算器。
【請求項３】
前記減算判断回路が比較器からなり、
前記比較器が、当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に対応して設けられたｎ個の単位比較器を、カスケード接続してなる
ことを特徴とする請求項１又は請求項２に記載の並列型の除算器。
【請求項４】
冗長２進数の演算を行う演算精度ｎ桁の順序回路型の除算器であって、
ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器からなる除算回路と、
前記除算回路に対応して設けられ、当該ｎ桁の並列型の減算器における減算結果を判断し、当該減算結果が正又は０である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該減算結果が負である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる減算判断回路と、
前記除算回路を構成するｎ桁の並列型の減算器を構成するｎ個の単位減算器毎に設けられたｎ個の保持回路であって、前記減算判断回路によって定められる当該対応する単位減算器の真の部分剰余を入力され、所定のクロックに同期して当該入力を１桁シフトさせて当該対応する単位減算器に隣接する単位減算器に入力するｎ個の保持回路とを有する
ことを特徴とする順序回路型の除算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、除算器に関し、特に、丸め誤差なしで正確な剰余を算出でき高速演算が可能な冗長２進数の演算を行う除算器に関する。
【０００２】
【従来の技術】
公開鍵暗号演算用の専用ハードウェアなどに用いられる除算器は、例えば１０２４桁以上の高精度な減算器によって構成されている。しかし、この減算器として、通常の２進数の演算を行う（２進表現による）減算器を用いると、各桁（各ビット）の単位減算器の間において桁上がり又は桁借りの伝搬が生じることが避けられない。このため、演算精度を向上させるために除算器の演算桁数（ビット数）を増加させた場合、この桁上がり又は桁借りの伝搬に起因して、遅延時間が演算桁数に比例して増加する。また、キャリールックアヘッド方式も高速化に向いてはいるが、多精度演算やチップスライス化による精度の拡張には不向きである。
【０００３】
そこで、遅延を演算桁数にかかわらず一定にすることのできる冗長２進数（冗長２進表現）を利用することが考えられる。通常、冗長２進数の演算（冗長２進表現による演算）では、２進数を冗長２進表現に変換し、冗長２進表現された値の間での演算を行い、結果を通常の２進数に逆変換する。しかし、ＲＳＡ公開鍵暗号演算で使用される「べき乗剰余演算」では乗算と除算を繰り返し演算するので、一度の乗算と除算の演算が終了した後に変換するのではなく、冗長２進表現で繰り返し減算を行い、最後の一度だけの変換で済む。従って、ＲＳＡ公開鍵暗号演算は、変換による処理時間は考慮しなくてもよい範囲にある。
【０００４】
冗長２進表現における減算は、減数の符号を反転させることにより加算器で実現できる（例えば、斎藤等“１桁２ビット／３ビット混合表現を用いた高速冗長２進加減算器の構成法”、信学技報、CAS99-41, VLD99-41, DSP99-57, pp.83-90(1999-06) 、文献▲１▼と言う）。具体的には、減数のそれぞれのビットを入れ替えるだけでよい。また、冗長２進表現による除算回路についても、既に提案されている（高木等“冗長２進表現を利用したＶＬＳＩ向き高速除算器”、電子通信学会論文誌、Vol.J67-D 、No.4、pp.450-457(1984-04) 、文献▲２▼と言う）。
【０００５】
【発明が解決しようとする課題】
しかし、上記の冗長２進数の演算を行う除算器は、本来、ＲＳＡ公開鍵暗号演算用の除算器として提案されたものでない。このため、上記の冗長２進数の演算を行う除算器を公開鍵暗号演算用の除算器として用いることは、実質的にはできない。
【０００６】
即ち、上記の除算器は固定演算であり、丸めによる商の誤差を含み、また、剰余を考慮していない。換言すれば、丸め誤差なしで正確な剰余を算出すると言う、ＲＳＡ公開鍵暗号演算用のような高精度の演算のために必須である演算ができない。従って、上記の冗長２進数の演算を行う除算器を、そのまま公開鍵暗号演算用の専用ハードウェア等における除算器として用いても、当該除算器に求められる１０２４桁以上の高精度な演算を行うことができない。また、上記の冗長２進数の演算を行う除算器は、固定演算であるので、演算桁数を１桁でも越えてしまうと演算不能になる。このため、上記の冗長２進数の演算を行う除算器のチップスライス化は不可能である。
【０００７】
本発明は、丸め誤差なしで正確な剰余を算出できる除算器を提供することを目的とする。
また、本発明は、公開鍵暗号演算等に適した除算器を提供することを目的とする。
また、本発明は、任意精度に拡張可能である除算器を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明による除算器は、冗長２進数の演算を行う演算精度ｎ（ｎは正の整数、この明細書において同じ）桁の並列型の除算器であって、除算回路と減算判断回路とを有する。除算回路は、ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器を、１桁づつシフトして接続して、ｎ段に構成してなる。減算判断回路は、除算回路を構成するｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々に対応して設けられたｎ個の単位比較器からなる演算判断回路であって、当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余と除数との減算結果であって冗長２進数である２ビットで表現された減算結果に基づいて、前記２ビットを比較することにより、当該ｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々における減算結果を判断し、当該減算結果が正又は０である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該減算結果が負である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる。
【０００９】
本発明の除算器によれば、ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器を用いて除算回路が構成されると共にこれに減算判断回路が付加される。これにより、並列型の減算器における全ての桁の演算結果を参照して減算結果の正負を判断することができる。即ち、冗長２進表現を利用した減算においては、桁上がり又は桁借りが高々１桁しか伝搬しないため、最大で全ての桁における演算結果を参照して減算結果の正負を判断する必要があるが、減算判断回路により正しくこれを判断することができる。従って、並列型の減算器を用いて冗長２進数の演算による除算を高速で行うことができるので、丸め誤差なしで正確な剰余を算出する演算を高速で行うことができる。この結果、本発明の除算器を、ＲＳＡ公開鍵暗号演算用のように、例えば１０２４桁以上の高精度の演算を行う除算器として用いることができる。また、並列に接続する単位減算器の個数ｎを増加させて演算精度を向上できるので、除算器をチップスライス化（モジュール化）することができる。
【００１０】
また、本発明による他の除算器は、冗長２進数の演算を行う演算精度ｎ桁の並列型の除算器であって、除算回路と減算判断回路とを有する。除算回路は、ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器を、１桁づつシフトするように、ｎ段に構成してなる。減算判断回路は、除算回路を構成するｎ桁の並列型の減算器を構成する前記ｎ個の単位減算器の各々に対応して設けられたｎ個の単位比較器からなる演算判断回路であって、当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余と除数との減算結果であって冗長２進数である２ビットで表現された減算結果に基づいて、前記２ビットを比較することにより、当該ｎ桁の並列型の減算器に入力される被減数と減数の大小を判断し、当該被減数が減数より大きいか又は減数と等しい場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該被減数が減数より小さい場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる。
【００１１】
本発明の他の除算器によれば、前述と同様の理由で、減算判断回路により並列型の減算器における全ての桁の演算結果を参照して減算結果の正負を判断することができるので、並列型の減算器を用いた冗長２進数の演算を可能とし、丸め誤差なしで正確な剰余を算出する演算を高速で行うことができる。この結果、本発明の除算器を高精度の演算を行う除算器として用いることができ、また、除算器をチップスライス化することができる。
【００１２】
また、本発明による更に他の除算器は、冗長２進数の演算を行う演算精度ｎ桁の並列型の除算器であって、除算回路と減算判断回路とｎ個の保持回路とを有する。除算回路は、ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器からなる。減算判断回路は、除算回路に対応して設けられ、当該ｎ桁の並列型の減算器における減算結果を判断し、当該減算結果が正又は０である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々において求まる部分剰余を当該真の部分剰余として次段に出力させ、当該減算結果が負である場合に当該ｎ桁の並列型の減算器を構成するｎ個の単位減算器の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる。ｎ個の保持回路は、除算回路を構成するｎ桁の並列型の減算器を構成するｎ個の単位減算器毎に設けられたｎ個の保持回路であって、減算判断回路によって定められる当該対応する単位減算器の真の部分剰余を入力され、所定のクロックに同期して当該入力を１桁シフトさせて当該対応する単位減算器に隣接する単位減算器に入力する。
【００１３】
本発明の更に他の除算器によれば、前述と同様の理由で、減算判断回路により並列型の減算器における全ての桁の演算結果を参照して減算結果の正負を判断することができるので、並列型の減算器を用いた冗長２進数の演算を可能とし、丸め誤差なしで正確な剰余を算出する演算を高速で行うことができる。この結果、本発明の除算器を高精度の演算を行う除算器として用いることができる。また、保持回路を設けることにより、除算回路を簡単な構成として小さな回路規模で除算器を実現することができる。更に、除算器をチップスライス化することができると共に、そのモジュール自体を小さくでき、かつ、少ないモジュールの数で任意精度に拡張することができる。
【００１４】
【発明の実施の形態】
〔第１の実施態様〕
本発明の除算器は、冗長２進数の演算を行う演算精度ｎ桁（ｎビット）の並列型の除算器であって、図１に示すように、除算回路と減算判断回路２とを有する。除算回路は、ｎ個の単位減算器（減算器セル）１０を並列に接続してなるｎ桁の並列型の減算器１を、１桁づつシフトして接続して、ｎ段に構成してなる。減算判断回路２は、図１及び図２（Ａ）に示すように、除算回路を構成するｎ桁の並列型の減算器１毎に設けられ、当該ｎ桁の並列型の減算器１における減算結果を判断する。単位減算器１０は、図２（Ｂ）に示すように、周知の減算器（ＳＵＢ．）１１からなる。
【００１５】
なお、図１において、図示の簡単のために、ｎ＝４としている。また、減算判断回路２は、ｎ桁の並列型の減算器１毎に設けられるが、図示の簡単のために、１段についてのみ示す。更に、単位減算器１０の各々に、Ｃ33乃至Ｃ00の符号を付して表している。
【００１６】
減算判断回路２は、当該ｎ桁の並列型の減算器１における当該減算結果が正又は０である場合に、当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々において求まる部分剰余を、当該真の部分剰余として次段に出力させる。また、減算判断回路２は、当該減算結果が負である場合に、当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々に入力された前段の部分剰余を、当該真の部分剰余として次段に出力させる。
【００１７】
減算判断回路２は、例えば比較器からなる。比較器は、図２（Ｃ）に示すように、当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々に対応して設けられたｎ個の単位比較器２０を、カスケード接続してなる。
【００１８】
単位減算器１０における周知の減算器（ＳＵＢ）１１は、例えば図３に示すように、複数のＮＡＮＤゲート回路及びＮＯＲゲート回路により構成される。例えば、Ｘ−端子及びＸ＋端子には、各々、冗長２進数の採る値｛−１，０，１｝の内の−１及び＋１が入力される。Ｘ−端子に−１が入力される場合、Ｘ＋端子には０が入力される。Ｘ＋端子に＋１が入力される場合、Ｘ−端子には０が入力される。冗長２進数の０を入力する場合、Ｘ−端子及びＸ＋端子に共に０が入力される。なお、Ｘ−１及びＹ−１は下位桁からの入力であり、Ｃｉ−及びＣｉ＋は下位桁からの桁上がり又は桁借りであり、Ｃ−及びＣ＋は上位桁への桁上がり又は桁借りであり、ＯＵＴ−及びＯＵＴ＋は当該出力である。
【００１９】
本発明の除算器は、図１及び図２から判るように、冗長２進表現による減算を利用すると共に、減算器１段ごとにそれぞれ減算判断回路２を付加したものである。減算判断回路２を付加する理由は、減算結果の正負を判断する際に、最大すべての桁をもって判断する必要があるためである。本発明の除算器は、丸め誤差なしで正確な剰余を得ることができ、公開鍵暗号演算等にも不可欠な演算特性を得ることができる。また、本発明の除算器は、後述するように、これを１個の除算器モジユールとし、これを複数個用いることによって、通常の２進数で行われてきた任意精度に同じように、その演算精度を任意精度に拡張可能である。これにより、本発明者らが先に提案した任意精度に拡張可能な公開鍵暗号演算用の専用ハードウェア（中村等”ＲＳＡ公開鍵暗号システム実装におけるビットスライス化の一方式”、電学論(C)、Vol.118-C,  No.7/8, pp.1073-1081(1997-7/8)）にそのまま適用できる。
【００２０】
以下、本発明の除算器について、詳細に説明する。最初に、冗長２進表現及びその計算規則について簡単に説明し、次に、本発明の除算器における減算器の構成を説明し、更に、本発明の第１の実施態様である並列型除算器について説明する。
（冗長２進表現及びその計算規則）
整数部ｎ桁の２進数は、
（ａn-1 ａn-2 ・・・ａ0 ）2 ・・・・式（１）
と表すことができる。これは、
（Σａi ・２i ）10  ・・・・式（２）
を意味する（ここで、Σは、ｉ＝０からｎ−１までである）。通常の２進数は、各桁の要素ａi が、｛０，１｝の値をとるが、冗長２進表現は、基数２のＳＤ（Ｓｉｇｎｅｄ  Ｄｉｇｉｔ）表現の一種であり、各要素ａi が｛−１，０，１｝の値をとる（文献▲１▼、文献▲２▼、富田等”計算機システム工学”昭晃堂1988年、参照）。従って、この要素を表現するには最低２ビット必要である。
【００２１】
この方法により、加算時の桁上げや減算時の桁借りの伝搬を防止することで、高速に演算を行うことができる。この方法は、演算の桁数が多くなるほど効果が現れる。また、冗長２進表現による加算は、通常の２進数の加算と同じように演算ビット幅の直列に接続した全加算器を用いて構成できる。そのため論理回路設計上、演算ビットの拡張は全加算器の単純拡張で容易に実現可能である。冗長２進表現による演算では、２進数を冗長２進表現に変換し、冗長２進表現間での演算を行い、結果を通常の２進数に逆変換する。
【００２２】
冗長２進表現による加算においては、その過程を以下の２つのステップで行う。即ち、
１．桁ｉ、桁ｉ−１で中間和と桁上げを求める、
２．中間和と桁上げを加算する。
【００２３】
各桁の要素ａi が｛−１，０，１｝である冗長２進表現では、桁ｉで桁ｉ−１からの桁上げに基づいた桁ｉ＋１への桁上げを阻止でき、加算を定数時間で行うことができる。冗長２進による加算規則を図４（Ａ）に示す。入力は、それぞれ２ビットの被加数ｘi 、加数ｙi に加え、桁上げの伝搬を阻止するため１つ下位桁の入力ｘi-1 、ｙi-1 も調べる。
【００２４】
冗長２進表現による減算の場合、符号の反転は各桁それぞれの符号を反転させることによって実現できるので、加算と同様に扱うことができる（文献▲１▼参照）。演算（Ａ−Ｂ）を実現するためには、加算器に、Ａと、各桁それぞれの符号を反転させたＢとを入力する。これにより、加算器をそのまま減算器として使用することができる。従って、減算の場合も同じように桁借り伝搬を高々１桁に抑えることができる。冗長２進減算の計算規則を図４（Ｂ）に示す。
（除算器及びこれを構成する減算器）
除算器は、減算器によって構成することができる。そこで、まず、減算器の構成を説明し、次に、これを本発明の並列型除算器に適用する。
【００２５】
除算の実現方法は以下の４種類がある。即ち、
１．変数ｙと１／ｙの関係を示す変換表をＲＯＭ（読み出し専用メモリ）内に用意しておき、ｘ／ｙをｘ＊（１／ｙ）の乗算に置き換えて実行する逆数ＲＯＭ方式、
２．ｘ／ｙを実行する代わりに、対数ＲＯＭによりｌｏｇｘ及びｌｏｇｙを求め、それからｚ＝ｌｏｇｘ−ｌｏｇｙの減算を行い、最後に指数ＲＯＭによりｅz を求める対数計算方式、
３．被除数に対して減算を試行錯誤的に繰り返す減算シフト方式、及び
４．乗算を繰り遅し実行しながら結果を求める商に収束させる収束型除算方式、である。
【００２６】
この中では、逆数ＲＯＭ方式が高速であるが、対数計算方式と同様に高精度になると、ＲＯＭの容量が指数的に大きくなる欠点がある。収束型除算方式は、モジュール化を考えた場合近似による誤差が増大する。この点、減算シフト方式はこのような問題はなく、モジュール化に適している。通常の２進数による演算については、本発明者らは先に減算シフト方式を利用したモジュール化された除算器を実現している（中村等”任意の精度に拡張可能な除算器の提案”、電学論、Vol.111-C, No.3, pp.123-128(1991-03)）。そこで、本発明の除算器は、減算シフト方式を採用する。即ち、この除算アルゴリズムは、被除数に対してシフトと減算を試行錯誤的に繰り返す「減算シフト方式」に基づいた方式であり、一般的な基本式は以下の式（３）で表される。即ち、
Ｒ(0) ／Ｄ＝Σ２-jｑj ＋２-nＲ(n) ／Ｄ・・・・式（３）
である  （ここで、Σは、ｊ＝１からｎまでである）。式（３）において、除数Ｄ及び被除数Ｒ(0) に対して、Σ２-jｑj （Σはｊ＝１からｎまで）が求める商Ｑであり、最終剰余Ｒは２-nＲ(n) である。各段における商の１桁ｑj+1 は２ＲとＤとの大小関係で以下の式（４）のように求まる。即ち、
0004300332.tif 000002
である。つまり、まず仮の部分剰余Ｒ(j+1) （＝２Ｒ(j) −Ｄ）を求め、正又は０ならば、ｑj+1 ＝１が求まり、真の部分剰余とする。もし負ならば、ｑj+1 ＝０で仮の部分剰余の減算を取り消す。
【００２７】
以上の操作は、Ｒ(n) をｎ桁右にシフトすることから求まることを意味する。しかし、以上のことは、ｎ桁の商に対してのものであり、除算データを各モジュールに分散した場合、各モジュールの被除数と除数はそれぞれ連絡した状態で減算とシフトが行われなければならない。
【００２８】
一般に、除数に対して被除数の桁数が多いため、分散した除数を連結して被除数との減算を行うことは、除数の連結とそれに伴う減算やラッチ回路の連絡などにより容易に実現できない。そこで、アルゴリズムを変更し、分散した除数と減算器は各モジュール内で固定し、被除数を連結してシフトと減算を行う方式としてモジュールの分散化を可能にした。
【００２９】
減算シフト方式によるｎビット除算の処理手順を、図５に示す。ここで、Ｘは被除敦、Ｙは除数、Ｒは部分剰余、Ｒ’は仮の部分剰余、Ｑは商である。部分剰余と除数の減算から商の１桁を求める過程がｎ回繰り返される。本除算操作では、除数は固定で、部分剰余、被除数のみがシフトする。
【００３０】
減算シフト方式による４ビットの演算例を図６に示す。この例では、被除数Ｘ＝１１０１、除数Ｙ＝０１０１としている。４回の減算と３回のシフトにより、商Ｑ＝００１０、及び剰余Ｒ＝００１１が求められる。なお、図６において、表示の便宜上、−１を１の上部にバーを付加して表している。
（並列型除算器）
演算精度ｎ桁の並列型除算器は、ｎ桁の並列減算器１を１桁シフトしてｎ段構成とすることにより実現できる。
【００３１】
図５でＲ’≧０の判断機構は通常の２進数による演算の場合とは異なる。通常の２進数による演算の場合、減算結果が正（０を含む）もしくは負を判断する際には最上位の桁借りのみを見ればよい。なぜなら、Ｒ’≧０の場合、減算器の最上位桁の桁借りが必ず”０”になり、Ｒ’＜０の場合、減算器の最上位桁の桁借りが必ず”１”になるためである。しかし、冗長２進表現による演算の場合には、桁借りが高々１桁しか伝搬せず、減算結果が負の場合でも最上位桁に桁借りが生じるとは限らない。従って、各桁の減算結果が正であるかもしくは負であるかを判断する際には、減算結果そのものをもって判断する必要がある。つまり、減算結果の正負が決定できるまで、当該正負を上位ビットから順に判断しなければならず、最大ですべての減算結果を調べなければならない。そこで、本発明では、ｎ桁の並列型の減算器１に減算結果を判断する減算判断回路２を付加する。
【００３２】
この減算判断回路２は、前述の図１及び図２に示すように、ｎ桁の並列型の減算器１毎に付加され、減算結果が正もしくは負かを判断するために、比較器（コンパレータ）で構成される。まず、部分剰余（ｘ）と除数（ｙ）との減算を行い、結果（ｄ）を減算判断回路２に入力する。結果（ｄ）は、冗長２進表現ゆえ、２ビット（ＯＵＴ−及びＯＵＴ＋）で表される。この２ビットを比較して、減算結果が正又は０である（ＯＵＴ＋が大きいか又は０（この時、ＯＵＴ−も０である））場合、減算判断回路２の出力ｅを”１”とし、これにより単位減算器１０における仮の部分剰余を真の部分剰余とし（図２（Ｂ）のスイッチが図の左側に倒れ、ｄ’←ｄとされる）、Ｑi ＝１となる。一方、減算結果が負である（ＯＵＴ−が大きい）場合、減算判断回路２の出力ｅを”０”とし、仮の部分剰余の減算を破棄し（図２（Ｂ）のスイッチが図の右側に倒れ、ｄ’←ｘとされる）、Ｑi ＝０となる。
【００３３】
以上の構成によれば、通常の２進数でのアルゴリズム（前述の４種類の除算の実現方法）がそのまま使用できる。また、これらの減算判断回路２の機能は、減算結果が正（０を含む）もしくは負の２通りを判断し、その結果によって２種類のうちどちらかの値を出力するので、商は通常の２進数で得られる。また、剰余は冗長２進表現のままで出力される。また、以上の構成によれば、減算を行ってから比較をするため多少時間がかかるが、減算判断回路２をマグニチュードコンパレータで構成できるので拡張が容易である。また、後述する第２の実施態様と比較すると、減算判断回路２の回路規模が小さく、接続が容易である。
【００３４】
以上のように、演算精度ｎ桁の並列型除算器は、図１に示すように、ｎ桁の並列型の減算器１を１桁シフトしてｎ段構成とすることにより実現できる。１段の並列型の減算器１で部分剰余と除数との減算を行い、その結果によって、次段の並列型の減算器１に入力される部分剰会の値が決められる。１段ごとに並列型の減算器１を１桁シフトさせての減算になるので、次段に入力される部分剰余は１桁シフトした状態となり、減算をｎ段分行うことによって、結果が求められる（中村等”任意精度の演算が可能な並列除算器のアーキテクチャ”、信学論、Vol.J75-C-II, No.5, pp.185-192(1992-05) ）。減算器がｎ段になるので、本方式では、減算判断回路２がｎ個必要である。
（モジュール化）
演算精度がｎビットの並列型除算器（図１の除算器をｎビットに拡張したもの）を１個のモジュールとしたときの、演算精度ｎと冗長２進表現を用いた並列型除算器の端子数との関係式を図７に示す。この端子数は、チップスライス化を考慮に入れたものである。従って、演算精度が増加し、２モジュール以上に拡張した場合のモジュール間の接続を考慮して算出した。電源端子を除いて、１モジュールの演算精度ｎが４ビットで端子数が８０本、８ビットで１６４本、１６ビットで３３２本になる。
【００３５】
１モジュールのビット数としては、４ビットや８ビットより１６ビットの方が実用的である。そこで、端子数を減少させるために、本発明ではバス形式を採用する。具体的には、端子数の大部分を占める被除数、除数、商及び剰余などの入出力をバス形式にする。即ち、これらの入力データは、分割したある決まった桁の分だけ、下位桁から順に所定のクロックに同期して順次入力する。入力したデータは、内部の保持回路に記憶しておく。演算終了後、同様に、剰余などのデータを下位桁からクロックに同期して数回に分割して出力する。これにより、入出力端子の数を大幅に減少させることができる。
【００３６】
並列型除算器の演算精度をｋ倍に拡張する場合、商を得るのに、減算器をｋ倍必要とする。さらに、減算回数もｋ倍の段数行わなければならない。従って、拡張は同一モジュールを２次元状に配列することによって、任意精度に拡張可能であるが、モジュール数はｋ2 個必要となる。演算精度を２倍（倍精度）に拡張するようにモジュール１００を拡張する時の接続図を図８に示す。図８（Ａ）及び図８（Ｂ）に示すように、モジュール＃１とモジュール＃２を接合することによって、並列減算器を２倍に拡張し、それに加え、モジュール＃３とモジュール＃４を接合することによって、減算器の段数を２倍にしている。なお、図８において、点線で区切って示す領域が１個のモジュール１００である。
〔第２の実施態様〕
図９は、本発明の第２の実施態様による除算器の構成を示し、図２（Ｂ）に対応する図である。この除算器は、基本的には、図１乃至図３に示す第１の実施態様の除算器と同一の構成を有するが、その減算判断回路２Ａのみが異なる構成とされる。
【００３７】
即ち、減算判断回路２Ａは、除算回路を構成するｎ桁の並列型の減算器１毎に設けられ、図９に示すように、当該ｎ桁の並列型の減算器１に入力される被減数と減数の大小を判断する。そして、減算判断回路２Ａは、当該被減数が減数より大きいか又は減数と等しい場合に当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々において求まる部分剰余を当該真の部分剰余として次段に出力させる。また、減算判断回路２Ａは、当該被減数が減数より小さい場合に当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる。なお、減算判断回路２Ａは比較器からなり、第１の実施態様の除算器と同一とされる。
【００３８】
この構成は、図９に示すように、減算判断回路２に代えて、当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々における、被減数と減数を比較するための減算判断回路２Ａを設ける構成である。単位減算器１０の構成は第１の実施態様と同じである。この構成では、減算と判断を同時に行う。減算判断回路２Ａに入力される値は、部分剰余（ｘ）と、除数（ｙ）である。部分剰余が除数より大きいか又は除数と等しい場合、減算結果が正になるので、減算判断回路２Ａの出力を”１”とし、仮の部分剰余を真の部分剰余とし（図２（Ｂ）のスイツチが左側に倒れ、ｄ’←ｄとされる）、Ｑi ＝１となる。部分剰余より除数の方が大きい場合、減算結果は負になるので、減算判断回路２Ａの出力を”０”とし、仮の部分剰余の減算を破棄し（図２（Ｂ）のスイッチが右側に倒れ、ｄ’←ｘとされる）、Ｑi ＝０となる。
【００３９】
この構成によっても、通常の２進数でのアルゴリズム（前述の４種類の実現方法）がそのまま使用できる。また、これらの減算判断回路２の機能は、減算結果が正もしくは負の２通りを判断し、その結果によって２種類のうちどちらかの値を出力するので、商は通常の２進数で得られる。また、剰余は冗長２進表現のままで出力される。また、この構成によれば、減算と判断を同時に行うので、高速な判断が可能であれば、多数桁になっても遅延の増加を防ぐことができる。
〔第３の実施態様〕
図１０は、本発明の第３の実施態様による除算器の構成を示し、図１及び図２（Ｂ）に対応する図である。この除算器は、ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の構成及び減算判断回路２については、図１乃至図３に示す第１の実施態様の除算器と同一の構成とされるが、その除算回路が異なる構成とされ、また、ｎ（この例ではｎ＝４）個の保持回路３１乃至３４を有する構成とされる。
【００４０】
即ち、除算回路は、ｎ個の単位減算器１０を並列に接続してなるｎ桁の並列型の減算器１からなる。減算判断回路２は、除算回路に対応して設けられ、当該ｎ桁の並列型の減算器１における減算結果を判断する。減算判断回路２は、当該減算結果が正又は０である場合に当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々において求まる部分剰余を当該真の部分剰余として次段に出力させる。また、減算判断回路２は、当該減算結果が負である場合に当該ｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０の各々に入力された前段の部分剰余を当該真の部分剰余として次段に出力させる。ｎ個の保持回路３１乃至３４は、除算回路を構成するｎ桁の並列型の減算器１を構成するｎ個の単位減算器１０毎に設けられる。ｎ個の保持回路３１乃至３４は、減算判断回路２によって定められる当該対応する単位減算器１０の真の部分剰余を入力され、所定のクロックに同期して当該入力を１桁シフトさせて、当該対応する単位減算器１０に隣接する単位減算器１０に入力する。ｎ個の保持回路３１乃至３４は、例えばフリップフロップＦＦ（又はシフトレジスタ）からなる。この例は順序回路型の除算器である。
【００４１】
順序回路型の除算器はクロックの１周期ごとにｑi を１桁ずつ上位桁から求めていく。並列型の除算器では、減算器１段ごとにｎ個の減算器１を１桁シフトさせて配置した構成になるが、順序回路型の除算器では、減算器は１段のみで構成し、シフトはｎ個の保持回路３１乃至３４へのクロックに同期して行われる。順序回路型の除算器の演算部分の構成図を図１０に示す。
【００４２】
まず、被除数ｘi を最下位桁の単位減算器１０の被減数に入力する。次に、減算判断回路２が減算と減算結果の判定を行う。最後に、仮の部分剰余の値によって、保持回路３１乃至３４に入力される真の部分剰余の値が決められる。クロックが与えられると、保持回路３１乃至３４に入力された値が部分剰余として出力されると同時に、各々の対応する単位減算器１０から１桁だけ左シフトされた単位減算器１０の被減数に入力される。これを演算桁数ｎと同じだけのクロック数を用いて繰り返すと、最終的に除算結果を求めることができる。
【００４３】
図９の順序回路型の除算器について、図１の並列型の除算器と比較をするために、入出力にレジスタを設け、バス形式を用いず全入力データを並列に入力（ラッチ）し、全出力データを並列に出力する場合を考える。このときの入出力端子の関係式を図１１に示す。図９の順序回路型の除算器は、減算器が１段しかないので、その分の端子が減少していることが判る。図１１の値は、図９の順序回路型の除算器において、図１の並列型の除算器と同じように、演算精度ｎが増加し、２個以上のモジュールに拡張した場合のモジュール間の接続を考慮して算出した。電源端子を除いて、１モジュールの演算精度ｎが４ビットで端子数が４９本、８ビットで７７本、１６ビットで１３３本になる。
【００４４】
減算シフト型の場合には、ｋ倍精度に拡張する場合、商を得るのに、減算器がｋ倍必要であるのは並列型と変わらないが、クロックに同期して同じ減算器を再利用してゆくので除算器は１段でよい。従って、同一モジュールをカスケード接続することによって拡張可能である。ｋ倍精度に拡張する場合、ｋ個の除算器モジユールのカスケード接続になる。
【００４５】
例えば、除算機の構成を３個のモジュール（３倍精度）に拡張する時の接続図を図１２に示す。ここで、ｇi 、ｇo は、減算判断回路２のカスケード接続用の端子である。最上位モジュールの減算判断回路２の出力が、全モジユールの減算セルヘのスイッチ制御入力となる。
【００４６】
冗長２進表現を利用した場合、減算器の回路規模は通常の２進数の除算器のそれより約３倍になる（文献▲１▼参照）。また、１桁を２ビットで表現しているので、保持回路３１乃至３４などの規模は２倍になる。しかし、最近の集積回路の大規模化により、この程度の増加では問題となる値ではないと考える。また、図１等の並列型の除算器は、クロツクを必要とせず高速に演算を行うことができるが、拡張性を考えた場合、モジュールを２次元状に配置しなければならないので、精度が大きくなるとモジュール数が多くなり、端子数も比較的多くなり、減算判断回路２もｋ  個必要となる。従って、精度が大きい場合、順序回路型の除算器が有効である。
【００４７】
以上、本発明を実施の態様により説明したが、本発明はその主旨の範囲内において種々の変形が可能である。
【００４８】
例えば、本発明の冗長２進表現を用いた除算器には減算判断回路２を付加する必要があるが、この減算判断回路２は、前述した以外にも種々の構成のものが考えられ、本発明の除算器の周辺回路との関係で最適な減算判断回路２の構成を選択することができる。また、本発明の冗長２進表現を用いた除算器において、その除算回路として、準並列型除算器（例えば、中村等”任意精度対応準並列型除算機構とそのＶＳＩへの応用”、信学技報、CAS99-40, VLD99-40, DSP99-66, pp.75-82(1999-06) ）を採用してもよい。一方、本発明の冗長２進表現を用いた除算器は、ＲＳＡ公開鍵暗号演算用に限られず、例えば画像処理等における高速演算用除算器として用いることができる。この場合、テレビ電話やインターネット上での動画像の表示において、高速で高精度の除算が可能となるので、画像を高速で滑らかに動かすことができる。
【００４９】
【発明の効果】
以上説明したように、本発明によれば、演算精度ｎ桁の除算器において、ｎ個の単位減算器を並列に接続してなるｎ桁の並列型の減算器１を用いて除算回路を構成すると共にこれに減算判断回路を付加することにより、冗長２進数の演算による除算を行うことができるので、丸め誤差なしで正確な剰余を算出する演算を高速で行うことができ、この結果、ＲＳＡ公開鍵暗号演算用のような例えば１０２４桁以上の高精度の演算を行う除算器として用いることができ、また、並列に接続する単位減算器の個数ｎを増加させて演算精度を向上できるので、除算器をチップスライス化することができる。
【００５０】
本発明の冗長２進数による除算器は、通常の２進数で使用するアルゴリズムがそのまま利用でき、しかも丸め誤差なしで商と剰余が得られ、正確な剰余が必要な公開鍵暗号方式にも応用できる。本発明の除算器のモジュールは、チップスライス化を考慮したアーキテクチャとなっているので、任意精度に容易に拡張可能であり、鍵の長さの拡張や可変長鍵に対しても対処可能な公開鍵暗号演算用の専用ハードウェアにそのまま適用できる。
【図面の簡単な説明】
【図１】並列型除算器説明図である。
【図２】並列型除算器説明図である。
【図３】並列型除算器説明図である。
【図４】並列型除算器説明図である。
【図５】並列型除算器説明図である。
【図６】並列型除算器説明図である。
【図７】並列型除算器説明図である。
【図８】並列型除算器説明図である。
【図９】並列型除算器説明図である。
【図１０】並列型除算器説明図である。
【図１１】並列型除算器説明図である。
【図１２】並列型除算器説明図である。
【符号の説明】
１    減算器
２、２Ａ    減算判断回路
１０    単位減算器
２０    単位比較器
【図１】
0004300332.tif 000003
【図２】
0004300332.tif 000004
【図３】
0004300332.tif 000005
【図４】
0004300332.tif 000006
【図５】
0004300332.tif 000007
【図６】
0004300332.tif 000008
【図７】
0004300332.tif 000009
【図８】
0004300332.tif 000010
【図９】
0004300332.tif 000011
【図１０】
0004300332.tif 000012
【図１１】
0004300332.tif 000013
【図１２】
0004300332.tif 000014