JPH0612236A - 整数上の乗算回路及び乗算方法 - Google Patents
整数上の乗算回路及び乗算方法Info
- Publication number
- JPH0612236A JPH0612236A JP4167083A JP16708392A JPH0612236A JP H0612236 A JPH0612236 A JP H0612236A JP 4167083 A JP4167083 A JP 4167083A JP 16708392 A JP16708392 A JP 16708392A JP H0612236 A JPH0612236 A JP H0612236A
- Authority
- JP
- Japan
- Prior art keywords
- bit
- integer
- bits
- full adder
- register
- 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.)
- Granted
Links
Abstract
(57)【要約】 （修正有）
【目的】乗算回路において大きな桁数を分割して演算す
る場合に、小さな桁数の乗算器を用いて桁上がりを考慮
した効率的な回路及び乗算方法を提供する。 【構成】ｈ，ｍ，ｎを正の整数とし、ｎビツトの整数Ａ
と（ｈ×ｍ）ビツトの整数Ｂとの乗算を行う回路におい
て、１×ｍビツトの乗算器とｍビツトフルアダーとｍ＋
２ビツトのレジスタとからなる演算エレメントを整数Ｂ
のｍビツトに対応してｈ個備え、整数Ａの各１ビツトに
整数Ｂのｍビツトが乗算されて、ｍビツトフルアダーに
出力され、フルアダーでは、各乗算器の出力と、下位桁
のレジスタからの前回のクロツク時の下位桁のｍビツト
フルアダーの上位３ビツトと、同じレジスタからの前回
のクロツク時のフルアダーでの加算結果の下位ｍ−１ビ
ツトを１桁上位にシフトしたフイードバツク値とを加算
し、上位３ビツトを上位桁のフルアダーの下位３ビツト
に提供し、ｎクロツク後のｍ＋２ビツトのレジスタの内
容を乗算結果Ａ・Ｂとする。
る場合に、小さな桁数の乗算器を用いて桁上がりを考慮
した効率的な回路及び乗算方法を提供する。 【構成】ｈ，ｍ，ｎを正の整数とし、ｎビツトの整数Ａ
と（ｈ×ｍ）ビツトの整数Ｂとの乗算を行う回路におい
て、１×ｍビツトの乗算器とｍビツトフルアダーとｍ＋
２ビツトのレジスタとからなる演算エレメントを整数Ｂ
のｍビツトに対応してｈ個備え、整数Ａの各１ビツトに
整数Ｂのｍビツトが乗算されて、ｍビツトフルアダーに
出力され、フルアダーでは、各乗算器の出力と、下位桁
のレジスタからの前回のクロツク時の下位桁のｍビツト
フルアダーの上位３ビツトと、同じレジスタからの前回
のクロツク時のフルアダーでの加算結果の下位ｍ−１ビ
ツトを１桁上位にシフトしたフイードバツク値とを加算
し、上位３ビツトを上位桁のフルアダーの下位３ビツト
に提供し、ｎクロツク後のｍ＋２ビツトのレジスタの内
容を乗算結果Ａ・Ｂとする。
Description
【０００１】
【産業上の利用分野】本発明は整数上の乗算回路に関
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路及びその方法に関するものである。本発明
は、大きな桁数の乗算を必要とするＲＳＡ暗号（池野信
一，小山謙二：“現代暗号学”，電子情報通信学会，１
９８６，６章）のような暗号化技術をはじめとして多く
の整数演算に利用することができる。
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路及びその方法に関するものである。本発明
は、大きな桁数の乗算を必要とするＲＳＡ暗号（池野信
一，小山謙二：“現代暗号学”，電子情報通信学会，１
９８６，６章）のような暗号化技術をはじめとして多く
の整数演算に利用することができる。
【０００２】
【従来の技術】ゲートアレイの設計や基板設計におい
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
【０００３】また、入力値を所定ビツト毎に分割して複
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，岩垂好裕，今井秀樹：
“符号理論”，昭晃堂，１９７３，４章）のような桁上
がりのない演算系では、図２のような回路によつて乗算
が行われることが知られている。図２中、＊Ｂi はＢ i
（ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊ｍビツ
トのガロア体上の乗算器、ＥＸはｍビツトのＥＸＯＲ、
ｒはｍビツトのレジスタである。
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，岩垂好裕，今井秀樹：
“符号理論”，昭晃堂，１９７３，４章）のような桁上
がりのない演算系では、図２のような回路によつて乗算
が行われることが知られている。図２中、＊Ｂi はＢ i
（ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊ｍビツ
トのガロア体上の乗算器、ＥＸはｍビツトのＥＸＯＲ、
ｒはｍビツトのレジスタである。
【０００４】しかし、整数上の乗算では、図２のような
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。
【０００５】
【発明が解決しようとしている課題】本発明は、上述の
欠点を除去し、乗算回路において大きな桁数の入力値を
分割して演算する場合に、小さな桁数の乗算器を用いて
桁上がりを考慮した効率的な整数上の乗算回路及び乗算
方法を提供することを目的とする。
欠点を除去し、乗算回路において大きな桁数の入力値を
分割して演算する場合に、小さな桁数の乗算器を用いて
桁上がりを考慮した効率的な整数上の乗算回路及び乗算
方法を提供することを目的とする。
【０００６】
【課題を解決するための手段】この課題を解決するため
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、ｎビツトの整数Ａと（ｈ×ｍ）ビツト
の整数Ｂとの乗算を行う整数上の乗算回路であつて、整
数Ａが１ビツト毎にｎクロツクに分けて上位桁から入力
され、該整数Ａの各１ビツトに整数Ｂの所定のｍビツト
を乗算する前記整数Ａに対して並列につながれる１ビツ
ト×ｍビツトの乗算器と、該乗算器の出力と、前回のク
ロツク時の１つ下位桁の２ビツトキヤリー付きｍビツト
フルアダーのｍ，ｍ＋１及びｍ＋２の上位３ビツトと、
前回のクロツク時の同じ桁の２ビツトキヤリー付きｍビ
ツトフルアダーの下位ｍ−１ビツトを１桁上位にシフト
したフイードバツク値とを加算する前記２ビツトキヤリ
ー付きｍビツトフルアダーと、前記２ビツトキヤリー付
きｍビツトフルアダーのｍ＋２ビツトの出力を同時に入
出力する、２つの前記２ビツトキヤリー付きｍビツトフ
ルアダー間につながれるｍ＋２ビツトのレジスタとを備
え、ｎクロツク後の前記ｍ＋２ビツトのレジスタの内容
を乗算結果Ａ・Ｂとする。
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、ｎビツトの整数Ａと（ｈ×ｍ）ビツト
の整数Ｂとの乗算を行う整数上の乗算回路であつて、整
数Ａが１ビツト毎にｎクロツクに分けて上位桁から入力
され、該整数Ａの各１ビツトに整数Ｂの所定のｍビツト
を乗算する前記整数Ａに対して並列につながれる１ビツ
ト×ｍビツトの乗算器と、該乗算器の出力と、前回のク
ロツク時の１つ下位桁の２ビツトキヤリー付きｍビツト
フルアダーのｍ，ｍ＋１及びｍ＋２の上位３ビツトと、
前回のクロツク時の同じ桁の２ビツトキヤリー付きｍビ
ツトフルアダーの下位ｍ−１ビツトを１桁上位にシフト
したフイードバツク値とを加算する前記２ビツトキヤリ
ー付きｍビツトフルアダーと、前記２ビツトキヤリー付
きｍビツトフルアダーのｍ＋２ビツトの出力を同時に入
出力する、２つの前記２ビツトキヤリー付きｍビツトフ
ルアダー間につながれるｍ＋２ビツトのレジスタとを備
え、ｎクロツク後の前記ｍ＋２ビツトのレジスタの内容
を乗算結果Ａ・Ｂとする。
【０００７】又、ｈ，ｍ，ｎを正の整数とする場合に、
ｎビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算
を行う整数上の乗算回路であつて、１ビツト×ｍビツト
の乗算器と２ビツトキヤリー付きｍビツトフルアダーと
ｍ＋２ビツトのレジスタとからなる演算エレメントを整
数Ｂの所定のｍビツトに対応してｈ個備え、前記乗算器
には整数Ａが１ビツト毎にｎクロツクに分けて上位桁か
ら並列に入力され、該整数Ａの各１ビツトに整数Ｂの所
定のｍビツトが乗算されて、前記ｍビツトフルアダーに
出力され、前記ｍビツトフルアダーでは、前記各乗算器
の出力と、下位桁の前記レジスタからの前回のクロツク
時の下位桁の前記ｍビツトフルアダーのｍ，ｍ＋１及び
ｍ＋２の上位３ビツトと、同じ演算エレメント内の前記
レジスタからの前回のクロツク時の前記ｍビツトフルア
ダーでの加算結果の下位ｍ−１ビツトを１桁上位にシフ
トしたフイードバツク値とを加算し、前記レジスタは、
前記ｍビツトフルアダーのｍ＋２ビツトの出力を同時に
保持し、下位ｍ−１ビツトを同じ演算エレメント内の前
記ｍビツトフルアダーにフイードバツクし、上位３ビツ
トを上位桁の前記ｍビツトフルアダーの下位３ビツトに
提供し、ｎクロツク後の前記ｍ＋２ビツトのレジスタの
内容を乗算結果Ａ・Ｂとする。
ｎビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算
を行う整数上の乗算回路であつて、１ビツト×ｍビツト
の乗算器と２ビツトキヤリー付きｍビツトフルアダーと
ｍ＋２ビツトのレジスタとからなる演算エレメントを整
数Ｂの所定のｍビツトに対応してｈ個備え、前記乗算器
には整数Ａが１ビツト毎にｎクロツクに分けて上位桁か
ら並列に入力され、該整数Ａの各１ビツトに整数Ｂの所
定のｍビツトが乗算されて、前記ｍビツトフルアダーに
出力され、前記ｍビツトフルアダーでは、前記各乗算器
の出力と、下位桁の前記レジスタからの前回のクロツク
時の下位桁の前記ｍビツトフルアダーのｍ，ｍ＋１及び
ｍ＋２の上位３ビツトと、同じ演算エレメント内の前記
レジスタからの前回のクロツク時の前記ｍビツトフルア
ダーでの加算結果の下位ｍ−１ビツトを１桁上位にシフ
トしたフイードバツク値とを加算し、前記レジスタは、
前記ｍビツトフルアダーのｍ＋２ビツトの出力を同時に
保持し、下位ｍ−１ビツトを同じ演算エレメント内の前
記ｍビツトフルアダーにフイードバツクし、上位３ビツ
トを上位桁の前記ｍビツトフルアダーの下位３ビツトに
提供し、ｎクロツク後の前記ｍ＋２ビツトのレジスタの
内容を乗算結果Ａ・Ｂとする。
【０００８】ここで、前記２ビツトキヤリー付きｍビツ
トフルアダーは、複数の２入力フルアダーまたはハーフ
アダーによつて実現される。
トフルアダーは、複数の２入力フルアダーまたはハーフ
アダーによつて実現される。
【０００９】又、本発明の整数上の乗算方法は、ｈ，
ｍ，ｎを正の整数とする場合に、ｎビツトの整数Ａと
（ｈ×ｍ）ビツトの整数Ｂとの乗算を行う整数上の乗算
方法であつて、１ビツト×ｍビツトの乗算器と、２ビツ
トキヤリー付きｍビツトフルアダーと、該フルアダーの
出力を記憶する整数Ｂの桁に対応してアドレス配置され
る複数領域を有する少なくともｍ＋２ビツトのメモリと
を備え、(A) 整数Ａのｎ分割された１ビツト（Ａi ）と
整数Ｂのｈ分割されたｍビツト（Ｂj ）とを前記１ビツ
ト×ｍビツトの乗算器で乗算する行程と、(B) 乗算結果
と前記メモリの所定領域（Ｒj-1 ）の上位３ビツトと所
定領域（Ｒj ）の下位ｍ−１ビツトとを前記フルアダー
で加算する行程と、(C) 加算結果を前記メモリの所定領
域（Ｒj ）に記憶する行程とを備え、前記行程(A) 〜
(C) を各Ａi(ｉ＝ｎ−１，ｎ−２，…，０の順）につい
て、Ｂ j のｊをｎ−１から０まで変化させて繰り返し、
全行程終了後の前記メモリの内容を乗算結果Ａ・Ｂとす
る。
ｍ，ｎを正の整数とする場合に、ｎビツトの整数Ａと
（ｈ×ｍ）ビツトの整数Ｂとの乗算を行う整数上の乗算
方法であつて、１ビツト×ｍビツトの乗算器と、２ビツ
トキヤリー付きｍビツトフルアダーと、該フルアダーの
出力を記憶する整数Ｂの桁に対応してアドレス配置され
る複数領域を有する少なくともｍ＋２ビツトのメモリと
を備え、(A) 整数Ａのｎ分割された１ビツト（Ａi ）と
整数Ｂのｈ分割されたｍビツト（Ｂj ）とを前記１ビツ
ト×ｍビツトの乗算器で乗算する行程と、(B) 乗算結果
と前記メモリの所定領域（Ｒj-1 ）の上位３ビツトと所
定領域（Ｒj ）の下位ｍ−１ビツトとを前記フルアダー
で加算する行程と、(C) 加算結果を前記メモリの所定領
域（Ｒj ）に記憶する行程とを備え、前記行程(A) 〜
(C) を各Ａi(ｉ＝ｎ−１，ｎ−２，…，０の順）につい
て、Ｂ j のｊをｎ−１から０まで変化させて繰り返し、
全行程終了後の前記メモリの内容を乗算結果Ａ・Ｂとす
る。
【００１０】
【実施例】本実施例ではｎビツトの整数Ａとｈ・ｍビツ
トの整数Ｂとの乗算器を想定するが、簡単のためにｈ＝
ｎとして説明する。この限定により一般性が失われるこ
とはない。すなわち、ｎビツトの整数Ａとｎ・ｍビツト
の整数Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
トの整数Ｂとの乗算器を想定するが、簡単のためにｈ＝
ｎとして説明する。この限定により一般性が失われるこ
とはない。すなわち、ｎビツトの整数Ａとｎ・ｍビツト
の整数Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
【００１１】整数Ａを１ビツト毎に、整数Ｂをｍビツト
毎にｎ分割すると、次のように表せる。
毎にｎ分割すると、次のように表せる。
【００１２】Ａ＝Ａn-1 ・２n-1 ＋Ａn-2 ・２n-2 ＋…
＋Ａ1 ・２＋Ａ0 Ｂ＝Ｂn-1 ・Ｘn-1 ＋Ｂn-2 ・Ｘn-2 ＋…＋Ｂ1 ・Ｘ＋
Ｂ0 ここで、Ｘ＝２m-1 とし、Ａ，Ｂについて上位桁からｎ
分割したビツト系列を、各々Ａi ，Ｂi （ｉ＝ｎ−１，
…，０）とする。この場合、整数Ａ，Ｂは多項式とみな
すことができるので、Ａ・Ｂは次のように表すことがで
きる。
＋Ａ1 ・２＋Ａ0 Ｂ＝Ｂn-1 ・Ｘn-1 ＋Ｂn-2 ・Ｘn-2 ＋…＋Ｂ1 ・Ｘ＋
Ｂ0 ここで、Ｘ＝２m-1 とし、Ａ，Ｂについて上位桁からｎ
分割したビツト系列を、各々Ａ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 （ｉ＝０，…，ｎ−１）を乗数とした
１ビツト＊ｍビツトのガロア体上の乗算器、ＥＸ…ｍビ
ツトのＥＸＯＲ、ｒ…ｍビツトレジスタ
Claims (4)
- 【請求項１】 ｈ，ｍ，ｎを正の整数とする場合に、ｎ
ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算を
行う整数上の乗算回路であつて、 整数Ａが１ビツト毎にｎクロツクに分けて上位桁から入
力され、該整数Ａの各１ビツトに整数Ｂの所定のｍビツ
トを乗算する前記整数Ａに対して並列につながれる１ビ
ツト×ｍビツトの乗算器と、 該乗算器の出力と、前回のクロツク時の１つ下位桁の２
ビツトキヤリー付きｍビツトフルアダーのｍ，ｍ＋１及
びｍ＋２の上位３ビツトと、前回のクロツク時の同じ桁
の２ビツトキヤリー付きｍビツトフルアダーの下位ｍ−
１ビツトを１桁上位にシフトしたフイードバツク値とを
加算する前記２ビツトキヤリー付きｍビツトフルアダー
と、 前記２ビツトキヤリー付きｍビツトフルアダーのｍ＋２
ビツトの出力を同時に入出力する、２つの前記２ビツト
キヤリー付きｍビツトフルアダー間につながれるｍ＋２
ビツトのレジスタとを備え、 ｎクロツク後の前記ｍ＋２ビツトのレジスタの内容を乗
算結果Ａ・Ｂとすることを特徴とする整数上の乗算回
路。 - 【請求項２】 ｈ，ｍ，ｎを正の整数とする場合に、ｎ
ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算を
行う整数上の乗算回路であつて、 １ビツト×ｍビツトの乗算器と２ビツトキヤリー付きｍ
ビツトフルアダーとｍ＋２ビツトのレジスタとからなる
演算エレメントを整数Ｂの所定のｍビツトに対応してｈ
個備え、 前記乗算器には整数Ａが１ビツト毎にｎクロツクに分け
て上位桁から並列に入力され、該整数Ａの各１ビツトに
整数Ｂの所定のｍビツトが乗算されて、前記ｍビツトフ
ルアダーに出力され、 前記ｍビツトフルアダーでは、前記各乗算器の出力と、
下位桁の前記レジスタからの前回のクロツク時の下位桁
の前記ｍビツトフルアダーのｍ，ｍ＋１及びｍ＋２の上
位３ビツトと、同じ演算エレメント内の前記レジスタか
らの前回のクロツク時の前記ｍビツトフルアダーでの加
算結果の下位ｍ−１ビツトを１桁上位にシフトしたフイ
ードバツク値とを加算し、 前記レジスタは、前記ｍビツトフルアダーのｍ＋２ビツ
トの出力を同時に保持し、下位ｍ−１ビツトを同じ演算
エレメント内の前記ｍビツトフルアダーにフイードバツ
クし、上位３ビツトを上位桁の前記ｍビツトフルアダー
の下位３ビツトに提供し、 ｎクロツク後の前記ｍ＋２ビツトのレジスタの内容を乗
算結果Ａ・Ｂとすることを特徴とする整数上の乗算回
路。 - 【請求項３】 前記２ビツトキヤリー付きｍビツトフル
アダーは、複数の２入力フルアダーまたはハーフアダー
によつて実現されることを特徴とする請求項１または２
記載の整数上の乗算回路。 - 【請求項４】 ｈ，ｍ，ｎを正の整数とする場合に、ｎ
ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗算を
行う整数上の乗算方法であつて、 １ビツト×ｍビツトの乗算器と、２ビツトキヤリー付き
ｍビツトフルアダーと、該フルアダーの出力を記憶する
整数Ｂの桁に対応してアドレス配置される複数領域を有
する少なくともｍ＋２ビツトのメモリとを備え、 (A) 整数Ａのｎ分割された１ビツト（Ａi ）と整数Ｂの
ｈ分割されたｍビツト（Ｂj ）とを前記１ビツト×ｍビ
ツトの乗算器で乗算する行程と、 (B) 乗算結果と前記メモリの所定領域（Ｒj-1 ）の上位
３ビツトと所定領域（Ｒj ）の下位ｍ−１ビツトとを前
記フルアダーで加算する行程と、 (C) 加算結果を前記メモリの所定領域（Ｒj ）に記憶す
る行程とを備え、 前記行程(A) 〜(C) を各Ａi(ｉ＝ｎ−１，ｎ−２，…，
０の順）について、Ｂ j のｊをｎ−１から０まで変化さ
せて繰り返し、全行程終了後の前記メモリの内容を乗算
結果Ａ・Ｂとすることを特徴とする整数上の乗算方法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16708392A JP3210420B2 (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
| EP93304879A EP0576262B1 (en) | 1992-06-25 | 1993-06-23 | Apparatus for multiplying integers of many figures |
| DE69329260T DE69329260T2 (de) | 1992-06-25 | 1993-06-23 | Gerät zum Multiplizieren von Ganzzahlen mit vielen Ziffern |
| 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 true JPH0612236A (ja) | 1994-01-21 |
| JP3210420B2 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 (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100465874C (zh) * | 1995-08-31 | 2009-03-04 | 英特尔公司 | 根据指令对数据执行运算的方法、处理器和系统 |
Families Citing this family (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 |
| KR102911856B1 (ko) | 2021-02-08 | 2026-01-15 | 삼성전자주식회사 | 프로세서, 프로세서의 동작 방법 및 이를 포함한 전자 장치 |
-
1992
- 1992-06-25 JP JP16708392A patent/JP3210420B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100465874C (zh) * | 1995-08-31 | 2009-03-04 | 英特尔公司 | 根据指令对数据执行运算的方法、处理器和系统 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3210420B2 (ja) | 2001-09-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP1293891B1 (en) | Arithmetic processor accomodating different finite field size | |
| Mohan | Residue number systems: algorithms and architectures | |
| CN110351087B (zh) | 流水线型的蒙哥马利模乘运算方法 | |
| JP5266354B2 (ja) | ガロア拡大体・積算／積算加算・積和演算装置 | |
| US6009450A (en) | Finite field inverse circuit | |
| US6061706A (en) | Systolic linear-array modular multiplier with pipeline processing elements | |
| US3805043A (en) | Serial-parallel binary multiplication using pairwise addition | |
| JP3516503B2 (ja) | 電子乗算および加算装置および方法 | |
| JP3213628B2 (ja) | Ｍを法として長い整数を乗算するための算術ユニット及びそのような乗算デバイスを具えるｒ．ｓ．ａ．変換器 | |
| JPH08101779A (ja) | 有限領域におけるモジュラ計算用の電子回路 | |
| CN1717653B (zh) | 带有查询表的乘法器 | |
| US20030182343A1 (en) | Fast multiplication circuits | |
| US7607165B2 (en) | Method and apparatus for multiplication and/or modular reduction processing | |
| JPH0612236A (ja) | 整数上の乗算回路及び乗算方法 | |
| EP1504338B1 (en) | "emod" a fast modulus calculation for computer systems | |
| JP3129525B2 (ja) | 整数上の乗算回路 | |
| KR100480997B1 (ko) | ＧＦ(ｐ)와 ＧＦ(2^ｍ)의 유한체 곱셈 연산 장치 | |
| JP3129524B2 (ja) | 整数上の乗算回路及び乗算方法 | |
| JP3129526B2 (ja) | 整数上の乗算回路 | |
| JPH0612237A (ja) | 整数上の乗算回路 | |
| JPH0612235A (ja) | 整数上の乗算回路及び乗算方法 | |
| JPH0612232A (ja) | 整数上の乗算回路 | |
| JPH0612231A (ja) | 整数上の乗算回路 | |
| KR100386979B1 (ko) | 갈로아체상에서 비트 직렬 승산기의 병렬화 방법 및 이를이용한 직병렬 승산기 | |
| Meher et al. | An Efficient Look-up Table-based Approach for Multiplication over GF (2 m) Generated by Trinomials |
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 |