JP3210420B2 - 整数上の乗算回路 - Google Patents
整数上の乗算回路Info
- Publication number
- JP3210420B2 JP3210420B2 JP16708392A JP16708392A JP3210420B2 JP 3210420 B2 JP3210420 B2 JP 3210420B2 JP 16708392 A JP16708392 A JP 16708392A JP 16708392 A JP16708392 A JP 16708392A JP 3210420 B2 JP3210420 B2 JP 3210420B2
- Authority
- JP
- Japan
- Prior art keywords
- bit
- bits
- integer
- full adder
- output
- 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.)
- Expired - Fee Related
Links
Description
【０００１】
【産業上の利用分野】本発明は整数上の乗算回路に関
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路に関するものである。本発明は、大きな桁数
の乗算を必要とするＲＳＡ暗号（池野信一，小山謙二：
“現代暗号学”，電子情報通信学会，１９８６，６章）
のような暗号化技術をはじめとして多くの整数演算に利
用することができる。
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路に関するものである。本発明は、大きな桁数
の乗算を必要とするＲＳＡ暗号（池野信一，小山謙二：
“現代暗号学”，電子情報通信学会，１９８６，６章）
のような暗号化技術をはじめとして多くの整数演算に利
用することができる。
【０００２】
【従来の技術】ゲートアレイの設計や基板設計におい
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
【０００３】また、入力値を所定ビツト毎に分割して複
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，岩垂好裕，今井秀樹：
“符号理論”，昭晃堂，１９７３，４章）のような桁上
がりのない演算系では、図２のような回路によつて乗算
が行われることが知られている。図２中、＊Ｂi はＢ i
（ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊ｍビツ
トのガロア体上の乗算器、ＥＸはｍビツトのＥＸＯＲ、
ｒはｍビツトのレジスタである。
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，岩垂好裕，今井秀樹：
“符号理論”，昭晃堂，１９７３，４章）のような桁上
がりのない演算系では、図２のような回路によつて乗算
が行われることが知られている。図２中、＊Ｂi はＢ i
（ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊ｍビツ
トのガロア体上の乗算器、ＥＸはｍビツトのＥＸＯＲ、
ｒはｍビツトのレジスタである。
【０００４】しかし、整数上の乗算では、図２のような
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。
【０００５】
【発明が解決しようとしている課題】本発明は、上述の
欠点を除去し、大きな整数の乗算を、桁上がりを考慮し
ながら小さな桁数の乗算器を用いて、回路規模が小さく
構成の簡単な整数上の乗算回路を提供することを目的と
する。
欠点を除去し、大きな整数の乗算を、桁上がりを考慮し
ながら小さな桁数の乗算器を用いて、回路規模が小さく
構成の簡単な整数上の乗算回路を提供することを目的と
する。
【０００６】
【課題を解決するための手段】この課題を解決するため
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、ｎビツトの整数Ａと（ｈ×ｍ）ビツト
の整数Ｂとの乗算を行う整数上の乗算回路であつて、１
ビツト毎にｎクロツクに分けて上位桁から入力される整
数Ａの各１ビツトに対して、各々が整数Ｂのそれぞれ異
なるｍビツトを並列に乗算するｈ個の１ビツト×ｍビツ
トの乗算器と、ｈ個の２ビツトキヤリー付きｍビツトフ
ルアダーであって、各々が、前記乗算器の１つの出力
と、１つ下位桁の２ビツトキヤリー付きｍビツトフルア
ダーの前回のクロツク時の出力の下位からｍ＋１ビット
目以上の部分を１ビット上位にシフトした値と、自分自
身の前回のクロツク時の出力の下位ｍビツトを１ビット
上位にシフトしたフイードバツク値とを加算する、ｈ個
の２ビツトキヤリー付きｍビツトフルアダーと、各々
が、前記２ビツトキヤリー付きｍビツトフルアダーの１
つのｍ＋２ビツトの出力を格納し、次のクロックで当該
フルアダーに下位ｍビツトをフィードバックし、下位か
らｍ＋１ビット目以上の部分を上位の前記２ビツトキヤ
リー付きｍビツトフルアダーに出力する、ｈ個のｍ＋２
ビツトのレジスタとを備え、最上桁の前記ｍ＋２ビツト
のレジスタから乗算結果Ａ・Ｂを上位桁より順次出力す
ることを特徴とする。
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、ｎビツトの整数Ａと（ｈ×ｍ）ビツト
の整数Ｂとの乗算を行う整数上の乗算回路であつて、１
ビツト毎にｎクロツクに分けて上位桁から入力される整
数Ａの各１ビツトに対して、各々が整数Ｂのそれぞれ異
なるｍビツトを並列に乗算するｈ個の１ビツト×ｍビツ
トの乗算器と、ｈ個の２ビツトキヤリー付きｍビツトフ
ルアダーであって、各々が、前記乗算器の１つの出力
と、１つ下位桁の２ビツトキヤリー付きｍビツトフルア
ダーの前回のクロツク時の出力の下位からｍ＋１ビット
目以上の部分を１ビット上位にシフトした値と、自分自
身の前回のクロツク時の出力の下位ｍビツトを１ビット
上位にシフトしたフイードバツク値とを加算する、ｈ個
の２ビツトキヤリー付きｍビツトフルアダーと、各々
が、前記２ビツトキヤリー付きｍビツトフルアダーの１
つのｍ＋２ビツトの出力を格納し、次のクロックで当該
フルアダーに下位ｍビツトをフィードバックし、下位か
らｍ＋１ビット目以上の部分を上位の前記２ビツトキヤ
リー付きｍビツトフルアダーに出力する、ｈ個のｍ＋２
ビツトのレジスタとを備え、最上桁の前記ｍ＋２ビツト
のレジスタから乗算結果Ａ・Ｂを上位桁より順次出力す
ることを特徴とする。
【０００７】又、ｈ，ｍ，ｎを正の整数とする場合に、
ｎビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算
を行う整数上の乗算回路であつて、１ビツト×ｍビツト
の乗算器と２ビツトキヤリー付きｍビツトフルアダーと
ｍ＋２ビツトのレジスタとを有する演算エレメントを整
数Ｂの所定のｍビツトに対応してｈ個備え、前記乗算器
には整数Ａが１ビツト毎にｎクロツクに分けて上位桁か
ら並列に入力され、該整数Ａの各１ビツトに整数Ｂの所
定のｍビツトが乗算されて、前記ｍビツトフルアダーに
出力され、前記ｍビツトフルアダーでは、前記各乗算器
の出力と、下位桁の前記レジスタからの前回のクロツク
時の下位桁の前記ｍビツトフルアダーの下位からｍ＋１
ビット目以上の部分を１ビット上位にシフトした値と、
同じ演算エレメント内の前記レジスタからの前回のクロ
ツク時の前記ｍビツトフルアダーでの加算結果の下位ｍ
ビツトを１ビット上位にシフトしたフイードバツク値と
を加算し、前記レジスタは、前記ｍビツトフルアダーの
ｍ＋２ビツトの出力を同時に保持し、下位ｍビツトを同
じ演算エレメント内の前記ｍビツトフルアダーにフイー
ドバツクし、下位からｍ＋１ビット目以上の部分を上位
桁の前記ｍビツトフルアダーに提供し、最上桁の前記演
算エレメント内の前記ｍ＋２ビツトのレジスタから乗算
結果Ａ・Ｂを上位桁より順次出力することを特徴とす
る。
ｎビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算
を行う整数上の乗算回路であつて、１ビツト×ｍビツト
の乗算器と２ビツトキヤリー付きｍビツトフルアダーと
ｍ＋２ビツトのレジスタとを有する演算エレメントを整
数Ｂの所定のｍビツトに対応してｈ個備え、前記乗算器
には整数Ａが１ビツト毎にｎクロツクに分けて上位桁か
ら並列に入力され、該整数Ａの各１ビツトに整数Ｂの所
定のｍビツトが乗算されて、前記ｍビツトフルアダーに
出力され、前記ｍビツトフルアダーでは、前記各乗算器
の出力と、下位桁の前記レジスタからの前回のクロツク
時の下位桁の前記ｍビツトフルアダーの下位からｍ＋１
ビット目以上の部分を１ビット上位にシフトした値と、
同じ演算エレメント内の前記レジスタからの前回のクロ
ツク時の前記ｍビツトフルアダーでの加算結果の下位ｍ
ビツトを１ビット上位にシフトしたフイードバツク値と
を加算し、前記レジスタは、前記ｍビツトフルアダーの
ｍ＋２ビツトの出力を同時に保持し、下位ｍビツトを同
じ演算エレメント内の前記ｍビツトフルアダーにフイー
ドバツクし、下位からｍ＋１ビット目以上の部分を上位
桁の前記ｍビツトフルアダーに提供し、最上桁の前記演
算エレメント内の前記ｍ＋２ビツトのレジスタから乗算
結果Ａ・Ｂを上位桁より順次出力することを特徴とす
る。
【０００８】ここで、前記２ビツトキヤリー付きｍビツ
トフルアダーは、複数の２入力フルアダーまたはハーフ
アダーによつて実現される。
トフルアダーは、複数の２入力フルアダーまたはハーフ
アダーによつて実現される。
【０００９】
【００１０】
【実施例】本実施例ではｎビツトの整数Ａとｈ・ｍビツ
トの整数Ｂとの乗算器を想定するが、簡単のためにｈ＝
ｎとして説明する。この限定により一般性が失われるこ
とはない。すなわち、ｎビツトの整数Ａとｎ・ｍビツト
の整数Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
トの整数Ｂとの乗算器を想定するが、簡単のためにｈ＝
ｎとして説明する。この限定により一般性が失われるこ
とはない。すなわち、ｎビツトの整数Ａとｎ・ｍビツト
の整数Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
【００１１】整数Ａを１ビツト毎に、整数Ｂをｍビツト
毎にｎ分割すると、次のように表せる。
毎にｎ分割すると、次のように表せる。
【００１２】 Ａ＝Ａn-1 ・２n-1 ＋Ａn-2 ・２n-2 ＋…＋Ａ1 ・２＋Ａ0 Ｂ＝Ｂn-1 ・Ｘn-1 ＋Ｂn-2 ・Ｘn-2 ＋…＋Ｂ1 ・Ｘ＋Ｂ0 ここで、Ｘ＝２ m とし、Ａ，Ｂについて上位桁からｎ分
割したビツト系列を、各々Ａi ，Ｂi （ｉ＝ｎ−１，
…，０）とする。この場合、整数Ａ，Ｂは多項式とみな
すことができるので、Ａ・Ｂは次のように表すことがで
きる。
割したビツト系列を、各々Ａi ，Ｂi （ｉ＝ｎ−１，
…，０）とする。この場合、整数Ａ，Ｂは多項式とみな
すことができるので、Ａ・Ｂは次のように表すことがで
きる。
【００１３】
【数１】 Ａ・Ｂ＝Ａn-1 ・Ｂ・２n-1 ＋Ａn-2 ・Ｂ・２n-2 ＋… ＋Ａ1 ・Ｂ・２＋Ａ0 ・Ｂ ここでは、一般性が失われることはないので、ｎ＝４の
場合を考える。
場合を考える。
【００１４】 Ａ・Ｂ＝Ａ3 ・（Ｂ3 ・Ｘ3 ＋Ｂ2 ・Ｘ2 ＋Ｂ1 ・Ｘ＋Ｂ0 ）・２3 ＋Ａ2 ・（Ｂ3 ・Ｘ3 ＋Ｂ2 ・Ｘ2 ＋Ｂ1 ・Ｘ＋Ｂ0 ）・２2 ＋Ａ1 ・（Ｂ3 ・Ｘ3 ＋Ｂ2 ・Ｘ2 ＋Ｂ1 ・Ｘ＋Ｂ0 ）・２ ＋Ａ0 ・（Ｂ3 ・Ｘ3 ＋Ｂ2 ・Ｘ2 ＋Ｂ1 ・Ｘ＋Ｂ0 ） これを、図１のような回路の乗算器で構成する。図１は
Ａi （ｉ＝ｎ−１，…，０）が１ビツト単位、Ｂi がｍ
ビツト単位のときの乗算回路である。図１は１×ｍビツ
トの乗算器４個（×Ｂ0 〜×Ｂ3 ）と、２ビツトキヤリ
ー付きｍビツトフルアダー４個（＋0 〜＋3 ）と、ｍ＋
２ビツトのレジスタ４個（Ｒ0 〜Ｒ4 ）から構成され
る。図１において各レジスタの初期状態はオール“０”
とする。
Ａi （ｉ＝ｎ−１，…，０）が１ビツト単位、Ｂi がｍ
ビツト単位のときの乗算回路である。図１は１×ｍビツ
トの乗算器４個（×Ｂ0 〜×Ｂ3 ）と、２ビツトキヤリ
ー付きｍビツトフルアダー４個（＋0 〜＋3 ）と、ｍ＋
２ビツトのレジスタ４個（Ｒ0 〜Ｒ4 ）から構成され
る。図１において各レジスタの初期状態はオール“０”
とする。
【００１５】最初のクロツクでＡ3 が入力されると、
式の各項の係数Ａ3 ・Ｂi （ｉ＝３，…，０）が各乗算
器から出力され、各フルアダーを通して各々のレジスタ
に格納される。
式の各項の係数Ａ3 ・Ｂi （ｉ＝３，…，０）が各乗算
器から出力され、各フルアダーを通して各々のレジスタ
に格納される。
【００１６】次のクロツクでＡ2 が入力されたとき、
式の各項の係数Ａ2 ・Ｂi （ｉ＝３，…，０）が各乗算
器から出力される。式は式に対して２進数で１桁大
きいので、レジスタ内に格納された値は１ビツト上位に
シフトされて、式の係数を表す各乗算器からの出力と
加算される。従つて、各レジスタの下位ｍビツトは１ビ
ツト上位にシフトされた状態で加算器にフイードバツク
入力され、各レジスタのｍ＋１ビツト目以上は１ビツト
上位にシフトされた状態で、右隣の加算器に入力され
る。従つて、加算器では１ビットずれたｍビツト同士の
加算が行われ、桁上がりがあればｍ＋２ビツトの出力が
行われて再びレジスタに格納される。
式の各項の係数Ａ2 ・Ｂi （ｉ＝３，…，０）が各乗算
器から出力される。式は式に対して２進数で１桁大
きいので、レジスタ内に格納された値は１ビツト上位に
シフトされて、式の係数を表す各乗算器からの出力と
加算される。従つて、各レジスタの下位ｍビツトは１ビ
ツト上位にシフトされた状態で加算器にフイードバツク
入力され、各レジスタのｍ＋１ビツト目以上は１ビツト
上位にシフトされた状態で、右隣の加算器に入力され
る。従つて、加算器では１ビットずれたｍビツト同士の
加算が行われ、桁上がりがあればｍ＋２ビツトの出力が
行われて再びレジスタに格納される。
【００１７】次のクロツクでＡ1 が入力されたときも、
Ａ2 が入力されたときと同様の演算が行われる。すなわ
ち、各レジスタのｍ＋１ビツト目の桁上がりビツトがキ
ヤリーとして右隣の加算器の下位から２ビット目に入力
され、各レジスタのｍ＋２ビツト目の桁上がりビツトが
キヤリーとして右隣の加算器の下位から３ビット目に入
力される。すなわち、各レジスタのｍ＋１ビツト目は右
隣のレジスタの最下位ビツトと同じビット位置を表すの
で、加算器においては最下位のキヤリービツトではなく
下位から２ビット目のキヤリービツトとして扱い、各レ
ジスタのｍ＋２ビツト目は右隣のレジスタの下位から２
ビツト目と同じビット位置を表すので、加算器において
は下位から３ビット目のキヤリービツトとして扱う必要
がある。従つて、加算器からはｍ＋２ビツトの出力が行
われ再びレジスタに格納される。これによつて、上の
〜式までの各項の係数の加算が行われたことになる。
Ａ2 が入力されたときと同様の演算が行われる。すなわ
ち、各レジスタのｍ＋１ビツト目の桁上がりビツトがキ
ヤリーとして右隣の加算器の下位から２ビット目に入力
され、各レジスタのｍ＋２ビツト目の桁上がりビツトが
キヤリーとして右隣の加算器の下位から３ビット目に入
力される。すなわち、各レジスタのｍ＋１ビツト目は右
隣のレジスタの最下位ビツトと同じビット位置を表すの
で、加算器においては最下位のキヤリービツトではなく
下位から２ビット目のキヤリービツトとして扱い、各レ
ジスタのｍ＋２ビツト目は右隣のレジスタの下位から２
ビツト目と同じビット位置を表すので、加算器において
は下位から３ビット目のキヤリービツトとして扱う必要
がある。従つて、加算器からはｍ＋２ビツトの出力が行
われ再びレジスタに格納される。これによつて、上の
〜式までの各項の係数の加算が行われたことになる。
【００１８】次のクロツクで最後の入力Ａ0 が入力され
たとき、同様の演算によつて〜式の各項の係数の加
算が行われ、Ａ・Ｂの乗算が行われたことになる。後は
引続きクロツクわ入力し、最上位桁のレジスタの上位ビ
ツトから乗算結果Ａ・Ｂを上位桁から出力しても良い
し、各レジスタの内容を読み出して最終乗算結果Ａ・Ｂ
を作成しても良い。これによつてＡの値が分割入力され
るときＡ・Ｂの演算が効率的に行われる。
たとき、同様の演算によつて〜式の各項の係数の加
算が行われ、Ａ・Ｂの乗算が行われたことになる。後は
引続きクロツクわ入力し、最上位桁のレジスタの上位ビ
ツトから乗算結果Ａ・Ｂを上位桁から出力しても良い
し、各レジスタの内容を読み出して最終乗算結果Ａ・Ｂ
を作成しても良い。これによつてＡの値が分割入力され
るときＡ・Ｂの演算が効率的に行われる。
【００１９】本例では、整数Ａを１ビツトづつ分割し、
ｎ＝４として説明したが、一般性を失うことなく、整数
Ａをｍビツトに分割されたｎ・ｍビツトの数とし、ｎと
ｈとが異なる任意の整数の乗算にまで拡張される。この
場合には、ｍビツト×ｍビツトの乗算器が使用される。
ｎ＝４として説明したが、一般性を失うことなく、整数
Ａをｍビツトに分割されたｎ・ｍビツトの数とし、ｎと
ｈとが異なる任意の整数の乗算にまで拡張される。この
場合には、ｍビツト×ｍビツトの乗算器が使用される。
【００２０】また、図１においてキヤリーを持つフルア
ダーは、複数の２入力フルアダーとハーフアダーの組合
せによつて実現できることも明かである。また、図１に
おいて右端のレジスタを省いたり、更にフルアダーとレ
ジスタを付け加えても同様の乗算器が構成できるのは明
かである。
ダーは、複数の２入力フルアダーとハーフアダーの組合
せによつて実現できることも明かである。また、図１に
おいて右端のレジスタを省いたり、更にフルアダーとレ
ジスタを付け加えても同様の乗算器が構成できるのは明
かである。
【００２１】また、図１のような乗算器（×Ｂj ）とフ
ルアダー（＋j）とレジスタ（Ｒj）とからなる同一の演
算素子（エレメント）の繰り返しによる構成は、ＶＬＳ
Ｉ等の大規模回路を構成しやすいという利点もある。ま
た、複数の領域Ｒj を有するメモリを使用して、ソフト
ウエアにより上記演算素子に対応する演算を順にあるい
は並列に行うことにより、同様の演算結果が得られるこ
とは明らかである。尚、本発明は、複数の機器から構成
されるシステムに適用しても、１つの機器から成る装置
に適用しても良い。また、本発明はシステム或は装置に
プログラムを供給することによつて達成される場合にも
適用できることは言うまでもない。
ルアダー（＋j）とレジスタ（Ｒj）とからなる同一の演
算素子（エレメント）の繰り返しによる構成は、ＶＬＳ
Ｉ等の大規模回路を構成しやすいという利点もある。ま
た、複数の領域Ｒj を有するメモリを使用して、ソフト
ウエアにより上記演算素子に対応する演算を順にあるい
は並列に行うことにより、同様の演算結果が得られるこ
とは明らかである。尚、本発明は、複数の機器から構成
されるシステムに適用しても、１つの機器から成る装置
に適用しても良い。また、本発明はシステム或は装置に
プログラムを供給することによつて達成される場合にも
適用できることは言うまでもない。
【発明の効果】本発明によれば、大きな整数の乗算を、
桁上がりを考慮しながら小さな桁数の乗算器を用いて、
回路規模が小さく構成の簡単な整数上の乗算回路を提供
することができる。
桁上がりを考慮しながら小さな桁数の乗算器を用いて、
回路規模が小さく構成の簡単な整数上の乗算回路を提供
することができる。
【図１】本実施例の整数上の乗算回路を示す図である。
【図２】公知のガロア体上の多項式の乗算回路を示す図
である。
である。
Ｒ…ｍ＋２ビツトレジスタ、＋…２ビツトキヤリー付き
２ｍビツトフルアダー、×Ｂi …Ｂi （ｉ＝０，…，ｎ
−１）を乗数とした１ビツト×ｍビツトの整数上の乗算
器、＊Ｂi …Ｂi （ｉ＝０，…，ｎ−１）を乗数とした
１ビツト＊ｍビツトのガロア体上の乗算器、ＥＸ…ｍビ
ツトのＥＸＯＲ、ｒ…ｍビツトレジスタ
２ｍビツトフルアダー、×Ｂi …Ｂi （ｉ＝０，…，ｎ
−１）を乗数とした１ビツト×ｍビツトの整数上の乗算
器、＊Ｂi …Ｂi （ｉ＝０，…，ｎ−１）を乗数とした
１ビツト＊ｍビツトのガロア体上の乗算器、ＥＸ…ｍビ
ツトのＥＸＯＲ、ｒ…ｍビツトレジスタ
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.7，ＤＢ名) G06F 7/52 310 G06F 7/60 ＷＰＩ（ＤＩＡＬＯＧ)
Claims (3)
- 【請求項１】 ｈ，ｍ，ｎを正の整数とする場合に、ｎ
ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算を
行う整数上の乗算回路であつて、 １ビツト毎にｎクロツクに分けて上位桁から入力される
整数Ａの各１ビツトに対して、各々が整数Ｂのそれぞれ
異なるｍビツトを並列に乗算するｈ個の１ビツト×ｍビ
ツトの乗算器と、 ｈ個の２ビツトキヤリー付きｍビツトフルアダーであっ
て、各々が、前記乗算器の１つの出力と、１つ下位桁の
２ビツトキヤリー付きｍビツトフルアダーの前回のクロ
ツク時の出力の下位からｍ＋１ビット目以上の部分を１
ビット上位にシフトした値と、自分自身の前回のクロツ
ク時の出力の下位ｍビツトを１ビット上位にシフトした
フイードバツク値とを加算する、ｈ個の２ビツトキヤリ
ー付きｍビツトフルアダーと、 各々が、前記２ビツトキヤリー付きｍビツトフルアダー
の１つのｍ＋２ビツトの出力を格納し、次のクロックで
当該フルアダーに下位ｍビツトをフィードバックし、下
位からｍ＋１ビット目以上の部分を上位の前記２ビツト
キヤリー付きｍビツトフルアダーに出力する、ｈ個のｍ
＋２ビツトのレジスタとを備え、 最上桁の前記ｍ＋２ビツトのレジスタから乗算結果Ａ・
Ｂを上位桁より順次出力することを特徴とする整数上の
乗算回路。 - 【請求項２】 ｈ，ｍ，ｎを正の整数とする場合に、ｎ
ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算を
行う整数上の乗算回路であつて、 １ビツト×ｍビツトの乗算器と２ビツトキヤリー付きｍ
ビツトフルアダーとｍ＋２ビツトのレジスタとを有する
演算エレメントを整数Ｂの所定のｍビツトに対応してｈ
個備え、 前記乗算器には整数Ａが１ビツト毎にｎクロツクに分け
て上位桁から並列に入力され、該整数Ａの各１ビツトに
整数Ｂの所定のｍビツトが乗算されて、前記ｍビツトフ
ルアダーに出力され、 前記ｍビツトフルアダーでは、前記各乗算器の出力と、
下位桁の前記レジスタからの前回のクロツク時の下位桁
の前記ｍビツトフルアダーの下位からｍ＋１ビット目以
上の部分を１ビット上位にシフトした値と、同じ演算エ
レメント内の前記レジスタからの前回のクロツク時の前
記ｍビツトフルアダーでの加算結果の下位ｍビツトを１
ビット上位にシフトしたフイードバツク値とを加算し、 前記レジスタは、前記ｍビツトフルアダーのｍ＋２ビツ
トの出力を同時に保持し、下位ｍビツトを同じ演算エレ
メント内の前記ｍビツトフルアダーにフイードバツク
し、下位からｍ＋１ビット目以上の部分を上位桁の前記
ｍビツトフルアダーに提供し、 最上桁の前記演算エレメント内の前記ｍ＋２ビツトのレ
ジスタから乗算結果Ａ・Ｂを上位桁より順次出力するこ
とを特徴とする整数上の乗算回路。 - 【請求項３】 前記２ビツトキヤリー付きｍビツトフル
アダーは、複数の２入力フルアダーまたはハーフアダー
によつて実現されることを特徴とする請求項１または２
記載の整数上の乗算回路。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16708392A JP3210420B2 (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
| DE69329260T DE69329260T2 (de) | 1992-06-25 | 1993-06-23 | Gerät zum Multiplizieren von Ganzzahlen mit vielen Ziffern |
| EP93304879A EP0576262B1 (en) | 1992-06-25 | 1993-06-23 | Apparatus for multiplying integers of many figures |
| US08/512,620 US5524090A (en) | 1992-06-25 | 1995-08-08 | Apparatus for multiplying long integers |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16708392A JP3210420B2 (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0612236A JPH0612236A (ja) | 1994-01-21 |
| JP3210420B2 true JP3210420B2 (ja) | 2001-09-17 |
Family
ID=15843097
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16708392A Expired - Fee Related JP3210420B2 (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3210420B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7806832B2 (en) | 2007-04-30 | 2010-10-05 | The General Electric Company | False positive reduction in SPO2 atrial fibrillation detection using average heart rate and NIBP |
| US12327179B2 (en) | 2021-02-08 | 2025-06-10 | Samsung Electronics Co., Ltd. | Processor, method of operating the processor, and electronic device including the same |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| MX9801571A (es) * | 1995-08-31 | 1998-05-31 | Intel Corp | Aparato para realizar operaciones de multiplica-suma en datos empacados. |
-
1992
- 1992-06-25 JP JP16708392A patent/JP3210420B2/ja not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7806832B2 (en) | 2007-04-30 | 2010-10-05 | The General Electric Company | False positive reduction in SPO2 atrial fibrillation detection using average heart rate and NIBP |
| US12327179B2 (en) | 2021-02-08 | 2025-06-10 | Samsung Electronics Co., Ltd. | Processor, method of operating the processor, and electronic device including the same |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0612236A (ja) | 1994-01-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP1293891B2 (en) | Arithmetic processor accomodating different finite field size | |
| US5764554A (en) | Method for the implementation of modular reduction according to the Montgomery method | |
| US6209016B1 (en) | Co-processor for performing modular multiplication | |
| CA2225899A1 (en) | A method and apparatus for finite field multiplication | |
| JP2744091B2 (ja) | 有限体の乗法的逆数元を計算するデータ処理方法及び装置 | |
| US6009450A (en) | Finite field inverse circuit | |
| US6061706A (en) | Systolic linear-array modular multiplier with pipeline processing elements | |
| US6917956B2 (en) | Apparatus and method for efficient modular exponentiation | |
| JP3213628B2 (ja) | Ｍを法として長い整数を乗算するための算術ユニット及びそのような乗算デバイスを具えるｒ．ｓ．ａ．変換器 | |
| US8244790B2 (en) | Multiplier and cipher circuit | |
| JP3210420B2 (ja) | 整数上の乗算回路 | |
| US20030182343A1 (en) | Fast multiplication circuits | |
| US5912904A (en) | Method for the production of an error correction parameter associated with the implementation of modular operations according to the Montgomery method | |
| EP1504338B1 (en) | "emod" a fast modulus calculation for computer systems | |
| KR100480997B1 (ko) | ＧＦ(ｐ)와 ＧＦ(2^ｍ)의 유한체 곱셈 연산 장치 | |
| JP2000207387A (ja) | 演算装置及び暗号処理装置 | |
| EP1455270A2 (en) | Method and apparatus for basis conversion in finite field and a multiplier | |
| JP3129525B2 (ja) | 整数上の乗算回路 | |
| JPH03661B2 (ja) | ||
| JPH05197525A (ja) | オペランドを否定するための否定方法及び否定回路 | |
| KR100946256B1 (ko) | 다정도 캐리 세이브 가산기를 이용한 듀얼필드상의확장성있는 몽고매리 곱셈기 | |
| JP3129524B2 (ja) | 整数上の乗算回路及び乗算方法 | |
| JP3129526B2 (ja) | 整数上の乗算回路 | |
| EP0281303A3 (en) | Modulo arithmetic processor chip | |
| JPH0612237A (ja) | 整数上の乗算回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20010615 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080713 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080713 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090713 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090713 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100713 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100713 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110713 Year of fee payment: 10 |
|
| LAPS | Cancellation because of no payment of annual fees |