JPH0612231A - 整数上の乗算回路 - Google Patents
整数上の乗算回路Info
- Publication number
- JPH0612231A JPH0612231A JP4167081A JP16708192A JPH0612231A JP H0612231 A JPH0612231 A JP H0612231A JP 4167081 A JP4167081 A JP 4167081A JP 16708192 A JP16708192 A JP 16708192A JP H0612231 A JPH0612231 A JP H0612231A
- Authority
- JP
- Japan
- Prior art keywords
- integer
- output
- bits
- multiplication
- input
- 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.)
- Withdrawn
Links
Abstract
(57)【要約】
【目的】本発明の目的は、乗算回路において大きな桁数
の入力値を分割して演算する場合に、小さな桁数の乗算
器を用いて桁上がりを考慮した効率的で高速の且つ拡張
性のある整数上の乗算回路を提供することにある。 【構成】 ｈ，ｍ，ｎを正の整数とする場合に、（ｎ×
ｍ）ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗
算を行う整数上の乗算回路であつて、ｈ行×ｎ列の２次
元状に並べられる同一の演算素子ＰＥ(0,0) 〜ＰＥ(n-
1,h-1) を備え、前記各列のＰＥ(i,0) 〜ＰＥ(i,h-1)
に整数Ａをｍビツト毎に分けたＡi （ｉ＝０，…，ｎ−
１）と整数Ｂをｍビツト毎に分けたＢj （ｊ＝０，…，
ｈ−１）とを同時に入力し、各ＰＥ(i,j) においてＳj
←Ａi ・Ｂj ＋Ｓj （ｊ＝０，…，ｈ−１）を計算して
ＰＥ(i+1,j-1) に出力し、ＰＥ(i,0) とＰＥ(n-1,j) と
からの出力をＡ・Ｂの乗算値とすることを特徴とする。
の入力値を分割して演算する場合に、小さな桁数の乗算
器を用いて桁上がりを考慮した効率的で高速の且つ拡張
性のある整数上の乗算回路を提供することにある。 【構成】 ｈ，ｍ，ｎを正の整数とする場合に、（ｎ×
ｍ）ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂとの乗
算を行う整数上の乗算回路であつて、ｈ行×ｎ列の２次
元状に並べられる同一の演算素子ＰＥ(0,0) 〜ＰＥ(n-
1,h-1) を備え、前記各列のＰＥ(i,0) 〜ＰＥ(i,h-1)
に整数Ａをｍビツト毎に分けたＡi （ｉ＝０，…，ｎ−
１）と整数Ｂをｍビツト毎に分けたＢj （ｊ＝０，…，
ｈ−１）とを同時に入力し、各ＰＥ(i,j) においてＳj
←Ａi ・Ｂj ＋Ｓj （ｊ＝０，…，ｈ−１）を計算して
ＰＥ(i+1,j-1) に出力し、ＰＥ(i,0) とＰＥ(n-1,j) と
からの出力をＡ・Ｂの乗算値とすることを特徴とする。
Description
【０００１】
【産業上の利用分野】本発明は整数上の乗算回路に関
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路に関するものである。本発明は、大きな桁数
の乗算を必要とするＲＳＡ暗号（池野信一，小山謙二：
“現代暗号学”，電子情報通信学会，１９８６，６章）
のような暗号化技術をはじめとして多くの整数演算に利
用することができる。
し、特に小さな桁数の乗算器を用いて大きな桁数の乗算
を行う回路に関するものである。本発明は、大きな桁数
の乗算を必要とするＲＳＡ暗号（池野信一，小山謙二：
“現代暗号学”，電子情報通信学会，１９８６，６章）
のような暗号化技術をはじめとして多くの整数演算に利
用することができる。
【０００２】
【従来の技術】ゲートアレイの設計や基板設計におい
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
て、小さな桁数の整数上の乗算器は、セルライブラリや
ＴＴＬ等が用意されているため手軽に構成することがで
きる。しかし、大きな桁数の乗算回路を実現しようとし
た場合には、セルライブラリ等がないので自分で設計し
なければならない。ところが、大きな桁数の乗算器を自
分で設計する場合、小さな桁数の乗算器の回路構成をそ
のまま拡張したのでは、回路構成が非常に複雑になり実
現が難しい。
【０００３】また、入力値を所定ビツト毎に分割して複
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，原島博，今井秀樹：
“情報と符号の理論”，岩波講座，１９８２，６章）の
ような桁上がりのない演算系では、図５のような回路に
よつて乗算が行われることが知られている。図５中、＊
Ｂi はＢi （ｉ＝０，…，ｎ−１）を乗数としたｍビツ
ト＊ｍビツトのガロア体上の乗算器、ＥＸはｍビツトの
ＥＸＯＲ、ｒはｍビツトのレジスタである。
数クロツクで乗算を行おうとする場合、入力値を多項式
と見なすと、ガロア体（宮川洋，原島博，今井秀樹：
“情報と符号の理論”，岩波講座，１９８２，６章）の
ような桁上がりのない演算系では、図５のような回路に
よつて乗算が行われることが知られている。図５中、＊
Ｂi はＢi （ｉ＝０，…，ｎ−１）を乗数としたｍビツ
ト＊ｍビツトのガロア体上の乗算器、ＥＸはｍビツトの
ＥＸＯＲ、ｒはｍビツトのレジスタである。
【０００４】しかし、整数上の乗算では、図５のような
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。また、
図５のような乗算回路は、分割した入力値Ａi （ｉ＝ｎ
−１，…，１）をシリアルに１クロツクづつ入力する必
要があり、Ａi を同時に入力して高速演算することはで
きない。
分割演算を行うと分割演算した桁毎に桁上がりが生じる
ため、効率的な乗算器を実現することは難しい。また、
図５のような乗算回路は、分割した入力値Ａi （ｉ＝ｎ
−１，…，１）をシリアルに１クロツクづつ入力する必
要があり、Ａi を同時に入力して高速演算することはで
きない。
【０００５】本発明は、上述の欠点を除去し、乗算回路
において大きな桁数の入力値を分割して演算する場合
に、小さな桁数の乗算器を用いて桁上がりを考慮した効
率的で高速の且つ拡張性のある整数上の乗算回路を提供
することを目的とする。
において大きな桁数の入力値を分割して演算する場合
に、小さな桁数の乗算器を用いて桁上がりを考慮した効
率的で高速の且つ拡張性のある整数上の乗算回路を提供
することを目的とする。
【０００６】
【課題を解決するための手段】この課題を解決するため
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、（ｎ×ｍ）ビツトの整数Ａと（ｈ×
ｍ）ビツトの整数Ｂとの乗算を行う整数上の乗算回路で
あつて、ｈ行×ｎ列の２次元状に並べられる同一の演算
素子ＰＥ(0,0) 〜ＰＥ(n-1,h-1) を備え、前記各列のＰ
Ｅ(i,0) 〜ＰＥ(i,h-1) に整数Ａをｍビツト毎に分けた
Ａi （ｉ＝０，…，ｎ−１）と整数Ｂをｍビツト毎に分
けたＢj （ｊ＝０，…，ｈ−１）とを同時に入力し、各
ＰＥ(i,j) においてＳj ←Ａi ・Ｂj ＋Ｓj （ｊ＝０，
…，ｈ−１）を計算してＰＥ(i+1,j-1) に出力し、ＰＥ
(i,0) とＰＥ(n-1,j) とからの出力をＡ・Ｂの乗算値と
する。更に、前記Ａi として零が入力されるｈ行のＰＥ
を最終列後に更に２列備え、最終キヤリーを含むＡ・Ｂ
の乗算値を出力する。
に、本発明の整数上の乗算回路は、ｈ，ｍ，ｎを正の整
数とする場合に、（ｎ×ｍ）ビツトの整数Ａと（ｈ×
ｍ）ビツトの整数Ｂとの乗算を行う整数上の乗算回路で
あつて、ｈ行×ｎ列の２次元状に並べられる同一の演算
素子ＰＥ(0,0) 〜ＰＥ(n-1,h-1) を備え、前記各列のＰ
Ｅ(i,0) 〜ＰＥ(i,h-1) に整数Ａをｍビツト毎に分けた
Ａi （ｉ＝０，…，ｎ−１）と整数Ｂをｍビツト毎に分
けたＢj （ｊ＝０，…，ｈ−１）とを同時に入力し、各
ＰＥ(i,j) においてＳj ←Ａi ・Ｂj ＋Ｓj （ｊ＝０，
…，ｈ−１）を計算してＰＥ(i+1,j-1) に出力し、ＰＥ
(i,0) とＰＥ(n-1,j) とからの出力をＡ・Ｂの乗算値と
する。更に、前記Ａi として零が入力されるｈ行のＰＥ
を最終列後に更に２列備え、最終キヤリーを含むＡ・Ｂ
の乗算値を出力する。
【０００７】ここで、前記ＰＥは、ｍビツト×ｍビツト
の乗算を実行する乗算器と、前記乗算器の出力と前段の
ＰＥの計算結果とを加算する２入力の２ｍビツト加算器
と、該加算器の出力を記憶する２ｍビツトのレジスタ
と、該加算器のキヤリー出力をラツチし、２列後の同じ
行のＰＥのキヤリー入力に出力するフリツプフロツプ
と、前記Ｂi を１クロツク遅延する遅延回路とから構成
される。
の乗算を実行する乗算器と、前記乗算器の出力と前段の
ＰＥの計算結果とを加算する２入力の２ｍビツト加算器
と、該加算器の出力を記憶する２ｍビツトのレジスタ
と、該加算器のキヤリー出力をラツチし、２列後の同じ
行のＰＥのキヤリー入力に出力するフリツプフロツプ
と、前記Ｂi を１クロツク遅延する遅延回路とから構成
される。
【０００８】
【実施例】本実施例ではｎ・ｍビツトの整数Ａとｈ・ｍ
ビツトの整数Ｂとの乗算器を想定するが、簡単のために
ｈ＝ｎとして説明する。この限定により一般性が失われ
ることはない。すなわち、ｎ・ｍビツトの２つの整数を
Ａ，Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
ビツトの整数Ｂとの乗算器を想定するが、簡単のために
ｈ＝ｎとして説明する。この限定により一般性が失われ
ることはない。すなわち、ｎ・ｍビツトの２つの整数を
Ａ，Ｂとし、Ａ・Ｂ＝Ｃの演算を実行することを考え
る。ここで、ｍビツトの２つの整数ａ，ｂの乗算ａ・ｂ
＝ｃを実行する乗算器は公知の構成、例えばセルライブ
ラリやＴＴＬ等によつて簡単に実現できる。
【０００９】整数Ａ，Ｂを各々ｍビツト毎にｎ分割する
と、次のように表せる。
と、次のように表せる。
【００１０】Ａ＝Ａ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 （ｉ
＝ｎ−１，…，０）とする。この場合、整数Ａ，Ｂは多
項式とみなすことができるので、Ａ・Ｂは次のように表
すことができる。
【００１１】
【数１】 従つて、図１のような回路で乗算器を構成できる。図１
はプロセツシング・エレメント（ＰＥ）と呼ばれる小さ
な同一の演算ブロツクによるパイプライン処理によつて
実行される。図１の縦方向のＰＥ(i,0) 〜ＰＥ(i,n-1)
には同じＡi （ｉ＝０，…，ｎ−１）が予めセツトされ
る。図１の配列においては、各ＰＥは、図２に示すよう
に、Ｂj （ｊ＝０，…，ｎ−１）を１クロツク遅れで右
方向にあるＰＥへ出力する。更に、Ｓj を左斜め上方の
ＰＥから入力すると、Ｓj ←Ａi・Ｂj ＋Ｓj を演算し
て、右斜め下方のＰＥへ演算結果Ｓj を出力し、この演
算で出力されたキヤリーｃｒを右方向の１つおきのＰＥ
へ出力する。尚、ＰＥの配列方法に対応して各ＰＥのデ
ータの入出力は異なるが、ＰＥの役割は等価である。
はプロセツシング・エレメント（ＰＥ）と呼ばれる小さ
な同一の演算ブロツクによるパイプライン処理によつて
実行される。図１の縦方向のＰＥ(i,0) 〜ＰＥ(i,n-1)
には同じＡi （ｉ＝０，…，ｎ−１）が予めセツトされ
る。図１の配列においては、各ＰＥは、図２に示すよう
に、Ｂj （ｊ＝０，…，ｎ−１）を１クロツク遅れで右
方向にあるＰＥへ出力する。更に、Ｓj を左斜め上方の
ＰＥから入力すると、Ｓj ←Ａi・Ｂj ＋Ｓj を演算し
て、右斜め下方のＰＥへ演算結果Ｓj を出力し、この演
算で出力されたキヤリーｃｒを右方向の１つおきのＰＥ
へ出力する。尚、ＰＥの配列方法に対応して各ＰＥのデ
ータの入出力は異なるが、ＰＥの役割は等価である。
【００１２】図２のＰＥは図３のように構成される。図
３はｍビツト×ｍビツトの乗算ａ・ｂ＝ｃ（本例ではＡ
i・Ｂj ）を実行する乗算器と、２つの２ｍビツトのレジ
スタＲ1 ，Ｒ2 と、２入力の２ｍビツト加算器と、該加
算器からのキヤリーｃｒをラツチするフリツプフロツプ
ＦＦとから構成される。
３はｍビツト×ｍビツトの乗算ａ・ｂ＝ｃ（本例ではＡ
i・Ｂj ）を実行する乗算器と、２つの２ｍビツトのレジ
スタＲ1 ，Ｒ2 と、２入力の２ｍビツト加算器と、該加
算器からのキヤリーｃｒをラツチするフリツプフロツプ
ＦＦとから構成される。
【００１３】図１において、Ｂ0 からＢn-1 の値は同時
に左端（列）のｎ個のＰＥ(0,0) 〜ＰＥ(0,n-1) の対応
するそれぞれに入力される。左端（列）のＰＥ及び上端
（行）のＰＥのＳj 入力に当たる左斜め上からはオール
“０”が入力される。
に左端（列）のｎ個のＰＥ(0,0) 〜ＰＥ(0,n-1) の対応
するそれぞれに入力される。左端（列）のＰＥ及び上端
（行）のＰＥのＳj 入力に当たる左斜め上からはオール
“０”が入力される。
【００１４】左端（列）のｎ個のＰＥ(0,0) 〜ＰＥ(0,n
-1) においては、Ｂj （ｊ＝０，…，ｎ−１）の入力に
応じて、乗算器で２ｍビツトのＡ0 ・Ｂ0 ，Ａ0 ・Ｂ
1 ，…Ａ0 ・Ｂn-1 が演算される。これをＳj ＝Ａ0 ・
Ｂj として右斜め下のＰＥに出力し、それに同期してＢ
j を右方向のＰＥに出力する。このとき、左端（列）の
下端のＰＥ(0,0) からは最下位桁であるＣ0 （＝Ａ0 ・
Ｂ0 ）が出力される。
-1) においては、Ｂj （ｊ＝０，…，ｎ−１）の入力に
応じて、乗算器で２ｍビツトのＡ0 ・Ｂ0 ，Ａ0 ・Ｂ
1 ，…Ａ0 ・Ｂn-1 が演算される。これをＳj ＝Ａ0 ・
Ｂj として右斜め下のＰＥに出力し、それに同期してＢ
j を右方向のＰＥに出力する。このとき、左端（列）の
下端のＰＥ(0,0) からは最下位桁であるＣ0 （＝Ａ0 ・
Ｂ0 ）が出力される。
【００１５】次に、図１の左から２番目（２列目）のｎ
個のＰＥ(1,0) 〜ＰＥ(1,n-1) においては、左端（列）
の１つ上（左斜め上）の行のＰＥからの出力Ｓj によつ
てＡ 0 ・Ｂj ＋Ａ1 ・Ｂj-1 が演算され、新たにＳj と
して３番目（３列目）の１つ下（右斜め下）へ出力さ
れ、加算器によつて出力されるキヤリーｃｒはフリツプ
フロツプＦＦによつてラツチされ、同じ行の左から４番
目（４列目）のＰＥへ出力される。
個のＰＥ(1,0) 〜ＰＥ(1,n-1) においては、左端（列）
の１つ上（左斜め上）の行のＰＥからの出力Ｓj によつ
てＡ 0 ・Ｂj ＋Ａ1 ・Ｂj-1 が演算され、新たにＳj と
して３番目（３列目）の１つ下（右斜め下）へ出力さ
れ、加算器によつて出力されるキヤリーｃｒはフリツプ
フロツプＦＦによつてラツチされ、同じ行の左から４番
目（４列目）のＰＥへ出力される。
【００１６】このとき、左から２番目の下端のＰＥ(1,
0) からは次の桁の出力であるＣ1 （＝Ａ0 ・Ｂ1 ＋Ａ1
・Ｂ0 ）が出力される。ＰＥ内での乗算結果Ａi ・Ｂj
はｍビツトのＡi ，Ｂj に対して２ｍビツトであるの
で、Ｘ2 分の桁数である。しかし、ＰＥ毎に行われる演
算の桁のずれはＸであるので、出力されたキヤリーは１
つおきのＰＥに対する桁上がり信号となる。
0) からは次の桁の出力であるＣ1 （＝Ａ0 ・Ｂ1 ＋Ａ1
・Ｂ0 ）が出力される。ＰＥ内での乗算結果Ａi ・Ｂj
はｍビツトのＡi ，Ｂj に対して２ｍビツトであるの
で、Ｘ2 分の桁数である。しかし、ＰＥ毎に行われる演
算の桁のずれはＸであるので、出力されたキヤリーは１
つおきのＰＥに対する桁上がり信号となる。
【００１７】以下同様の処理を図１の右端（列）のｎ個
のＰＥ(n-1,0) 〜ＰＥ(n-1,n-1) まで繰り返すことによ
つて、下端のＰＥ(0,0) 〜ＰＥ(n-1,0) からはＸn-1 桁
までの値Ａ・Ｂの乗算結果が出力され、右端（列）のＰ
Ｅ(n-1,0) 〜ＰＥ(n-1,n-1)からはＸn-1 桁以上のＡ・
Ｂの乗算結果とキヤリーが出力されることが判る。
のＰＥ(n-1,0) 〜ＰＥ(n-1,n-1) まで繰り返すことによ
つて、下端のＰＥ(0,0) 〜ＰＥ(n-1,0) からはＸn-1 桁
までの値Ａ・Ｂの乗算結果が出力され、右端（列）のＰ
Ｅ(n-1,0) 〜ＰＥ(n-1,n-1)からはＸn-1 桁以上のＡ・
Ｂの乗算結果とキヤリーが出力されることが判る。
【００１８】キヤリーによる加算も行った乗算結果を得
るには、図４のように右端（列）に更に２列ｎ個のＰＥ
(n,0) 〜ＰＥ(n,n-1) とＰＥ(n+1,0) 〜ＰＥ(n+1,n-1)
とを追加するか、キヤリーの加算演算のみを行う加算器
をｎ個追加すればよい。
るには、図４のように右端（列）に更に２列ｎ個のＰＥ
(n,0) 〜ＰＥ(n,n-1) とＰＥ(n+1,0) 〜ＰＥ(n+1,n-1)
とを追加するか、キヤリーの加算演算のみを行う加算器
をｎ個追加すればよい。
【００１９】以上によつて、入力値がｍビツト毎にｎ分
割されて入力されるとき、ｍビツトの乗算器を用いてｎ
・ｍビツトの乗算回路がパイプライン処理によつて高速
に実現できることが示せた。ｈ≠ｎの場合にも同様の回
路で乗算が実行できることは明らかである。これによつ
て、整数Ａの値が分割入力されるときＡ・Ｂの演算が効
率的に行われる。
割されて入力されるとき、ｍビツトの乗算器を用いてｎ
・ｍビツトの乗算回路がパイプライン処理によつて高速
に実現できることが示せた。ｈ≠ｎの場合にも同様の回
路で乗算が実行できることは明らかである。これによつ
て、整数Ａの値が分割入力されるときＡ・Ｂの演算が効
率的に行われる。
【００２０】この回路はＰＥの数が多いが、簡単な同一
ＰＥの規則的な構成によつて実現されるので、ＶＬＳＩ
等を構成しやすい。また、制御も各ＰＥについて同一で
済み、データも同一クロツクによつて同期して動作する
ので非常に簡単に実現できる。更に、Ａ，Ｂの桁数がど
んなに大きくなつてもＰＥを継ぎ足して行くだけでよく
拡張性に富んでいる。また、この方式は桁上がりが１つ
おきのＰＥ毎にクロツクに同期して行われるので、整数
上の乗算において問題になる桁上がりに関する遅延等の
問題がない。
ＰＥの規則的な構成によつて実現されるので、ＶＬＳＩ
等を構成しやすい。また、制御も各ＰＥについて同一で
済み、データも同一クロツクによつて同期して動作する
ので非常に簡単に実現できる。更に、Ａ，Ｂの桁数がど
んなに大きくなつてもＰＥを継ぎ足して行くだけでよく
拡張性に富んでいる。また、この方式は桁上がりが１つ
おきのＰＥ毎にクロツクに同期して行われるので、整数
上の乗算において問題になる桁上がりに関する遅延等の
問題がない。
【００２１】尚、本発明は、複数の機器から構成される
システムに適用しても、１つの機器から成る装置に適用
しても良い。また、本発明はシステム或は装置にプログ
ラムを供給することによつて達成される場合にも適用で
きることは言うまでもない。
システムに適用しても、１つの機器から成る装置に適用
しても良い。また、本発明はシステム或は装置にプログ
ラムを供給することによつて達成される場合にも適用で
きることは言うまでもない。
【００２２】
【発明の効果】本発明により、乗算回路において大きな
桁数の入力値を分割して演算する場合に、小さな桁数の
乗算器を用いて桁上がりを考慮した効率的で高速の且つ
拡張性のある整数上の乗算回路を提供できる。
桁数の入力値を分割して演算する場合に、小さな桁数の
乗算器を用いて桁上がりを考慮した効率的で高速の且つ
拡張性のある整数上の乗算回路を提供できる。
【図１】本実施例の整数上の乗算回路の基本構成を示す
図である。
図である。
【図２】図１に示された本実施例のＰＥの入出力関係を
示す図である。
示す図である。
【図３】図１に示された本実施例のＰＥの内部構成を示
す図である。
す図である。
【図４】本実施例の整数上の乗算回路の最終キヤリーの
演算も含む構成を示す図である。
演算も含む構成を示す図である。
【図５】公知のガロア体上の多項式の乗算回路を示す図
である。
である。
ＰＥ…プロセツシング・エレメント、Ｒ…２ｍビツトの
レジスタ、ＦＦ…１ビツトのフリツプフロツプ、＊Ｂi
…Ｂi （ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊
ｍビツトのガロア体上の乗算器、ＥＸ…ｍビツトのＥＸ
ＯＲ，ｒ…ｍビツトのレジスタ
レジスタ、ＦＦ…１ビツトのフリツプフロツプ、＊Ｂi
…Ｂi （ｉ＝０，…，ｎ−１）を乗数としたｍビツト＊
ｍビツトのガロア体上の乗算器、ＥＸ…ｍビツトのＥＸ
ＯＲ，ｒ…ｍビツトのレジスタ
Claims (3)
- 【請求項１】 ｈ，ｍ，ｎを正の整数とする場合に、
（ｎ×ｍ）ビツトの整数Ａと（ｈ×ｍ）ビツトの整数Ｂ
との乗算を行う整数上の乗算回路であつて、 ｈ行×ｎ列の２次元状に並べられる同一の演算素子ＰＥ
(0,0) 〜ＰＥ(n-1,h-1) を備え、 前記各列のＰＥ(i,0) 〜ＰＥ(i,h-1) に整数Ａをｍビツ
ト毎に分けたＡi （ｉ＝０，…，ｎ−１）と整数Ｂをｍ
ビツト毎に分けたＢj （ｊ＝０，…，ｈ−１）とを同時
に入力し、各ＰＥ(i,j) においてＳj ←Ａi ・Ｂj ＋Ｓ
j （ｊ＝０，…，ｈ−１）を計算してＰＥ(i+1,j-1) に
出力し、ＰＥ(i,0) とＰＥ(n-1,j) とからの出力をＡ・
Ｂの乗算値とすることを特徴とする整数上の乗算回路。 - 【請求項２】 前記Ａi として零が入力されるｈ行のＰ
Ｅを最終列後に更に２列備え、最終キヤリーを含むＡ・
Ｂの乗算値を出力することを特徴とする請求項１記載の
整数上の乗算回路。 - 【請求項３】 前記ＰＥは、ｍビツト×ｍビツトの乗算
を実行する乗算器と、前記乗算器の出力と前段のＰＥの
計算結果とを加算する２入力の２ｍビツト加算器と、該
加算器の出力を記憶する２ｍビツトのレジスタと、該加
算器のキヤリー出力をラツチし、２列後の同じ行のＰＥ
のキヤリー入力に出力するフリツプフロツプと、前記Ｂ
i を１クロツク遅延する遅延回路とから構成されること
を特徴とする請求項１又は２記載の整数上の乗算回路。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4167081A JPH0612231A (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 |
|---|---|---|---|
| JP4167081A JPH0612231A (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0612231A true JPH0612231A (ja) | 1994-01-21 |
Family
ID=15843055
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4167081A Withdrawn JPH0612231A (ja) | 1992-06-25 | 1992-06-25 | 整数上の乗算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0612231A (ja) |
-
1992
- 1992-06-25 JP JP4167081A patent/JPH0612231A/ja not_active Withdrawn
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110351087B (zh) | 流水线型的蒙哥马利模乘运算方法 | |
| US5524090A (en) | Apparatus for multiplying long integers | |
| Kinniment | An evaluation of asynchronous addition | |
| Imana | LFSR-Based Bit-Serial $ GF (2^ m) $ G F (2 m) Multipliers Using Irreducible Trinomials | |
| US3805043A (en) | Serial-parallel binary multiplication using pairwise addition | |
| Langhammer et al. | Efficient FPGA modular multiplication implementation | |
| US3878985A (en) | Serial-parallel multiplier using booth{3 s algorithm with combined carry-borrow feature | |
| Kong et al. | FPGA implementation of modular multiplier in residue number system | |
| Lee et al. | Efficient $ M $-ary exponentiation over $ GF (2^{m}) $ using subquadratic KA-based three-operand Montgomery multiplier | |
| CN108008934B (zh) | 一种基于查找表的复合有限域求逆装置 | |
| US7693925B2 (en) | Multiplicand shifting in a linear systolic array modular multiplier | |
| JPH0612231A (ja) | 整数上の乗算回路 | |
| JP3210420B2 (ja) | 整数上の乗算回路 | |
| JP3129525B2 (ja) | 整数上の乗算回路 | |
| CN117149131A (zh) | 一种快速右移移位累加器、分布式算法处理器和滤波器 | |
| JP3129526B2 (ja) | 整数上の乗算回路 | |
| Namin et al. | A High-Speed Word Level Finite Field Multiplier in ${\BBF} _ {2^ m} $ Using Redundant Representation | |
| WO2003096182A1 (en) | “emod” a fast modulus calculation for computer systems | |
| Salarifard et al. | High-throughput low-complexity unified multipliers over $ GF (2^{m}) $ in dual and triangular bases | |
| KR100946256B1 (ko) | 다정도 캐리 세이브 가산기를 이용한 듀얼필드상의확장성있는 몽고매리 곱셈기 | |
| JP3129524B2 (ja) | 整数上の乗算回路及び乗算方法 | |
| Nadjia et al. | High throughput parallel montgomery modular exponentiation on FPGA | |
| RU2838847C1 (ru) | Конвейерный умножитель по модулям | |
| JPH0612235A (ja) | 整数上の乗算回路及び乗算方法 | |
| RU2485574C1 (ru) | Способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19990831 |