(57)【特許請求の範囲】
【請求項１】
法Ｎと該法Ｎ以下の自然数からなる数Ａ及び羃指数Ｂとを入力し、法Ｎがｄビットに限定される冗長２進演算方法を利用して羃乗剰余演算Ｒ＝ＡＢ  ｍｏｄ  Ｎを行い、少なくとも演算結果の剰余Ｒを出力する羃乗剰余演算方法において、
法Ｎのデータを上位からｍビット毎に入力用前段データ記憶手段に取り込むとともに該法Ｎのデータが何ｍビット入力されたかをデータカウント手段で計測し、
入力用前段データ記憶手段に最初に取り込まれたデータの先頭から何ビット目に最初に“１”が現れたかを検出し、
該検出したビット数をビットシフト量として決定し、
入力用前段データ記憶手段内のデータを入力用後段データ記憶手段に順次転送し、
入力用前段データ記憶手段内のデータを下位ｍビットとし入力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ上位にシフトし、
該シフトした後の２ｍビットのデータの上位ｍビットをｍビットシフトデータ記憶手段に格納し、
法Ｎのデータ入力完了後、データカウント手段の値とｍビットシフトデータ記憶手段の容量／ｍとの差分をシフト量としてシフト量記憶手段に記憶し、
ｍビットシフトデータ記憶手段のデータをシフト量記憶手段の値だけ上位にｍビット単位にシフトして法記憶手段に記憶し、
数Ａのデータを上位からｍビット毎に入力用前段データ記憶手段に取り込むとともに該数Ａのデータが何ｍビット入力されたかをデータカウント手段で計測し、
入力用前段データ記憶手段内のデータを入力用後段データ記憶手段に順次転送し、
入力用前段データ記憶手段内のデータを下位ｍビットとし入力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ上位にシフトし、
該シフトした後の２ｍビットのデータの上位ｍビットをｍビットシフトデータ記憶手段に格納し、
数Ａのデータ入力完了後、ｍビットシフトデータ記憶手段のデータをシフト量記憶手段の値だけ上位にｍビット単位にシフトして数記憶手段に記憶し、
羃指数Ｂのデータを羃指数記憶手段に直接取り込んで記憶するとともに該羃指数Ｂのデータが何ビット入力されたかをデータカウント手段で計測して記憶し、記憶された法Ｎ、数Ａ及び羃指数Ｂのデータを使用して冗長２進演算手段に羃乗剰余演算を行わせ、
演算結果の剰余Ｒを剰余記憶手段に記憶し、
剰余記憶手段より剰余Ｒのデータを上位からｍビット毎に出力用前段データ記憶手段に取り込み、
出力用前段データ記憶手段内のデータを出力用後段データ記憶手段に順次転送し、
出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ下位にシフトして出力する
ことを特徴とする羃乗剰余演算方法。
【請求項２】
法記憶手段より法Ｎのデータを上位からｍビット毎に出力用前段データ記憶手段に取り込み、
出力用前段データ記憶手段内のデータを出力用後段データ記憶手段に順次転送し、
出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットをデータ入力時に決定したビットシフト量だけ下位にシフトして出力する
ことを特徴とする請求項１記載の羃乗剰余演算方法。
【請求項３】
数記憶手段より数Ａのデータを上位からｍビット毎に出力用前段データ記憶手段に取り込み、
出力用前段データ記憶手段内のデータを出力用後段データ記憶手段に順次転送し、
出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを法Ｎのデータ入力時に決定したビットシフト量だけ下位にシフトして出力する
ことを特徴とする請求項１記載の羃乗剰余演算方法。
【請求項４】
羃指数記憶手段より羃指数Ｂのデータを上位からｍビット毎に出力用前段データ記憶手段に取り込み、
出力用前段データ記憶手段内のデータを出力用後段データ記憶手段に順次転送し、
出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとしてそのまま出力する
ことを特徴とする請求項１記載の羃乗剰余演算方法。
【請求項５】
法Ｎと該法Ｎ以下の自然数からなる数Ａ及び羃指数Ｂとを入力し、法Ｎがｄビットに限定される冗長２進演算方法を利用して羃乗剰余演算Ｒ＝ＡＢ  ｍｏｄ  Ｎを行い、少なくとも演算結果の剰余Ｒを出力する羃乗剰余演算装置において、
法Ｎもしくは数Ａのデータを上位からｍビット毎に取り込む入力用前段データ記憶手段と、
法Ｎもしくは数Ａのデータが何ｍビット入力されたか及び羃指数Ｂのデータが何ビット入力されたかを計測するデータカウント手段と、
入力用前段データ記憶手段に最初に取り込まれた法Ｎのデータの先頭から何ビット目に最初に“１”が現れたかを検出する先頭“１”ビット検出手段と、
前記先頭“１”ビット検出手段で検出したビット数をビットシフト量として決定するビットシフト量決定手段と、
入力用前段データ記憶手段のデータを次に受け取る入力用後段データ記憶手段と、
入力用前段データ記憶手段内のデータを下位ｍビットとし入力用後段データ記憶手段内のデータを上位ｍビットとして、ビットシフト量決定手段で決定したシフト量だけ上位にシフトする２ｍビット上位シフト手段と、
法Ｎ、数Ａ及び羃指数Ｂのデータを使用して冗長２進演算方法により羃乗剰余演算を行う冗長２進演算手段と、
２ｍビット上位シフト手段によりシフトした後の２ｍビットのデータ又は冗長２進演算手段より得られる剰余Ｒあるいはこれに加えて法Ｎもしくは数Ａもしくは羃指数Ｂのデータの上位ｍビットを格納するｍビットシフトデータ記憶手段と、
法Ｎのデータ入力完了後、データカウント手段の値とｍビットシフトデータ記憶手段の容量／ｍとの差分をシフト量として記憶するシフト量記憶手段と、
ｍビットデータシフト記憶手段より演算結果の剰余Ｒあるいはこれに加えて法Ｎもしくは数Ａもしくは羃指数Ｂのデータを上位からｍビット毎に取り込む出力用前段データ記憶手段と、
出力用前段データ記憶手段のデータを次に受け取る出力用後段データ記憶手段と、
出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとして、演算結果の剰余Ｒ、法Ｎ及び数Ａのみビットシフト量決定手段で決定したビットシフト量だけ下位にシフトする２ｍビット下位シフト手段とを備えた
ことを特徴とする羃乗剰余演算装置。
【請求項６】
法Ｎを冗長２進表現に変換する法Ｎ−冗長２進変換手段と、
数Ａを冗長２進表現に変換する数Ａ−冗長２進変換手段と、
剰余Ｒを冗長２進表現に変換する数Ａ−冗長２進変換手段と、
演算結果の剰余Ｒを格納する演算結果格納手段と、
演算結果格納手段の内容を“１”に初期化する初期化手段と、
ｋビットの羃指数Ｂのデータが入力された時、ｋ≧ｉ≧１なるｉを用いて
Ｂ＝ｂｋ  ×２ｋ−１  ＋ｂｋ−１  ×２ｋ−２  ＋……＋ｂｉ  ×２ｉ−１  ＋……＋ｂ２  ×２１  ＋ｂ１  ×２０  
とし、ｉ＝ｋとして、演算結果の剰余Ｒ及び法Ｎを冗長２進表現にして法Ｎの格納ビット数と同一ビット数だけ上位ビットからＲ×２ｄ−ｋ  ＝（Ｒ×Ｒ×２ｄ−ｋ  ）ｍｏｄ  （Ｎ×２ｄ−ｋ  ）の演算を行い、また、ｂｉ  ＝１であれば、Ｒ×２ｄ−ｋ  ＝（Ａ×Ｒ×２ｄ−ｋ  ）ｍｏｄ  （Ｎ×２ｄ−ｋ  ）の演算を行い、ｉを１つずつ減じて０になるまで前記演算を繰り返し行うＮ×２ｄ−ｋ  ビット冗長２進羃乗剰余手段と、
冗長２進数を通常の２進数に戻す全加算手段と、
演算結果格納手段の上位ｄ−ｋを求める羃乗剰余演算結果として出力する演算結果出力手段とからなる冗長２進演算手段を備えた
ことを特徴とする請求項５記載の羃乗剰余演算装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、冗長２進演算方法を利用して桁数の多い羃乗剰余演算を高速に行う方法及びその装置に関するものである。
【０００２】
【従来の技術】
羃乗剰余演算は乗算及び剰余算の繰返しにより実行できるが、桁数の多い乗算及び剰余算を高速に行おうとすると、桁上がり・桁借りのキャリーの伝搬遅延の問題が顕著になる。そこで、従来より、キャリーの伝搬を防ぐ工夫をなした演算方法が種々提案されているが、そのうちの一つに冗長２進演算方法がある（例えば、ＩＥＥＥ  ＪＯＵＲＮＡＬ  ＯＦ  ＳＯＬＩＤ−ＳＴＡＴＥ  ＣＩＲＣＵＩＴＳ，  Ｖｏｌ．２５，  Ｎｏ．３，  Ｊｕｎｅ，  １９９０，  Ａ．Ｖａｎｄｅｍｅｕｌｅｂｒｏｅｃｋｅ，  Ｅ．Ｖａｎｚｉｅｌｅｇｈｅｍ，  Ｔ．Ｄｅｎａｙｅｒ  ａｎｄ  Ｐ．Ｇ．Ａ．Ｊｅｓｐｅｒｓ“Ａ  Ｎｅｗ  Ｃａｒｒｙ−Ｆｒｅｅ  Ｄｉｖｉｓｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ａ  Ｓｉｎｇｌｅ−Ｃｈｉｐ  １０２４−ｂ  ＲＳＡ  Ｐｒｏｃｅｓｓｏｒ  ”参照）。
【０００３】
【発明が解決しようとする課題】
ところが、この冗長２進演算方法では、除算や剰余算を行う場合、法の最上位ビットが常に“１”でなければならないという制約があり、その結果、法のビット数が限定されてしまうという問題があった。
【０００４】
本発明の目的は、法の最上位ビットが“１”でなくても冗長２進演算方法による羃乗剰余演算を可能とする方法及びその装置を提供することにある。
【０００５】
【課題を解決するための手段】
本発明では、前記目的を達成するため、法Ｎと該法Ｎ以下の自然数からなる数Ａ及び羃指数Ｂとを入力し、法Ｎがｄビットに限定される冗長２進演算方法を利用して羃乗剰余演算Ｒ＝ＡＢ  ｍｏｄ  Ｎを行い、少なくとも演算結果の剰余Ｒを出力する羃乗剰余演算方法及び装置において、法Ｎのデータを上位からｍビット毎に入力用前段データ記憶手段に取り込むとともに該法Ｎのデータが何ｍビット入力されたかをデータカウント手段で計測し、入力用前段データ記憶手段に最初に取り込まれたデータの先頭から何ビット目に最初に“１”が現れたかを検出し、該検出したビット数をビットシフト量として決定し、入力用前段データ記憶手段内のデータを入力用後段データ記憶手段に順次転送し、入力用前段データ記憶手段内のデータを下位ｍビットとし入力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ上位にシフトし、該シフトした後の２ｍビットのデータの上位ｍビットをｍビットシフトデータ記憶手段に格納し、法Ｎのデータ入力完了後、データカウント手段の値とｍビットシフトデータ記憶手段の容量／ｍとの差分をシフト量としてシフト量記憶手段に記憶し、ｍビットシフトデータ記憶手段のデータをシフト量記憶手段の値だけ上位にｍビット単位にシフトして法記憶手段に記憶し、数Ａのデータを上位からｍビット毎に入力用前段データ記憶手段に取り込むとともに該数Ａのデータが何ｍビット入力されたかをデータカウント手段で計測し、入力用前段データ記憶手段内のデータを入力用後段データ記憶手段に順次転送し、入力用前段データ記憶手段内のデータを下位ｍビットとし入力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ上位にシフトし、該シフトした後の２ｍビットのデータの上位ｍビットをｍビットシフトデータ記憶手段に格納し、数Ａのデータ入力完了後、ｍビットシフトデータ記憶手段のデータをシフト量記憶手段の値だけ上位にｍビット単位にシフトして数記憶手段に記憶し、羃指数Ｂのデータを羃指数記憶手段に直接取り込んで記憶するとともに該羃指数Ｂのデータが何ビット入力されたかをデータカウント手段で計測して記憶し、記憶された法Ｎ、数Ａ及び羃指数Ｂのデータを使用して冗長２進演算手段に羃乗剰余演算を行わせ、演算結果の剰余Ｒを剰余記憶手段に記憶し、剰余記憶手段より剰余Ｒのデータを上位からｍビット毎に出力用前段データ記憶手段に取り込み、出力用前段データ記憶手段内のデータを出力用後段データ記憶手段に順次転送し、出力用前段データ記憶手段内のデータを下位ｍビットとし出力用後段データ記憶手段内のデータを上位ｍビットとして、その２ｍビットを前記ビットシフト量だけ下位にシフトして出力することを特徴とする。
【０００６】
【作用】
従来の冗長２進演算方法を利用した演算器では法の最上位ビットを“１”に制限している。そのため、法のビット数も一意に限定されてしまう。一方、本発明の羃乗剰余演算方法及び装置によれば、法を任意にシフトして入力する手段を有し、これを利用することにより法を格納する時は最上位ビットが必ず“１”になるようにすることができる。従って、法レジスタのビット長以下であればいかなるビット長でも羃乗剰余演算を実行することが可能になり、冗長２進数を利用した羃乗剰余演算を法におけるビット長を限定することなく行うことができるようになる。
【０００７】
【実施例】
従来から多数ビット長で高速処理が必要な四則演算に用いられてきた冗長２進演算器に、本発明のパラメタの入出力補正部を加えることにより、法レジスタ以下のビット長であれば、法のビット長に制限のない羃乗剰余演算を行うことができる。
【０００８】
まず、乗算及び剰余算を組み合わせることにより、法を任意のビット長とした羃乗剰余演算が実行可能であることを示す。
【０００９】
羃乗剰余演算Ｒ＝ＡＢ  ｍｏｄ  Ｎは、ｋビットの羃指数Ｂのデータが入力された時、ｋ≧ｉ≧１なるｉを用いて、
Ｂ＝ｂｋ  ×２ｋ−１  ＋ｂｋ−１  ×２ｋ−２  ＋……＋ｂｉ  ×２ｉ−１  ＋……＋ｂ２  ×２１  ＋ｂ１  ×２０  
とし、
0003555091.tif 000002
で求めることができる。即ち、羃乗剰余演算は乗算及び剰余算の繰り返しにより求めることができる。
【００１０】
この演算処理を冗長２進演算方法により実行するには、法Ｎのビット長が冗長２進演算器のビット長と等しくなければならないことは前述した通りであるが、法Ｎのビット長が冗長２進演算器のビット長より短い時、Ｎ・２ｊ  が冗長２進演算器のビット長と等しくなるようにｊを決定し、
0003555091.tif 000003
を実行すれば、目的のＲ＝ＡＢ  ｍｏｄ  Ｎの演算を実行することができる。
【００１１】
羃乗剰余演算としてＡＢ  ｍｏｄ  Ｎの演算を行い、演算結果の剰余Ｒを出力する例について述べる。この例は以下のフェーズに分けることができる。
（１）演算に必要な３つのパラメタのパラメタレジスタへの入力
（２）冗長２進演算部へ各パラメタを入力するためのパラメタ変換
（３）冗長２進演算部での羃乗剰余演算
（４）演算結果の出力
以下、各フェーズ毎に説明する。
【００１２】
図１は本発明の一実施例を示すもので、図中、１はパラメタ入出力補正部、２はパラメタレジスタ部、３はパラメタ変換部、４は改良型冗長２進演算部、５は状態遷移制御部である。
【００１３】
図２はパラメタ入出力補正部１及びパラメタレジスタ部２の詳細を示すもので、ここではデータの入出力を８ビットのデータバスで行う例を示す。
【００１４】
カウンタ部６は入力される８ビットのデータをカウントアップする。入力用前段バッファ部７は８ビットのデータを蓄積するレジスタである。第１オクテット先頭“１”検出部８は８ビットのデータの先頭から何ビット目に“１”があるかを検出する。ビットシフト量決定部９は第１オクテット先頭“１”検出部８の値からビットシフト量を決定する。入力用後段バッファ部１０は８ビットのデータを蓄積するレジスタである。
【００１５】
入力用ビットシフト部１１は１６ビット入力で上位８ビット出力のバレルレジスタであり、シフト量はビットシフト量決定部９で決まる。バイトシフト部１２は８ビットデータを上位に１バイト単位で任意にシフトさせることができるレジスタである。バイトシフト量記憶部１３は法Ｎ及び数Ａ入力時のバイトシフト量を記憶しておく。
【００１６】
出力用前段バッファ部１４は８ビットのデータを蓄積するレジスタである。出力用後段バッファ部１５は８ビットのデータを蓄積するレジスタである。出力用ビットシフト部１６は１６ビット入力で上位８ビット出力のバレルレジスタであり、シフト量はビットシフト量決定部９で決まる。
【００１７】
法Ｎレジスタ２１は法Ｎを格納しておくレジスタである。数Ａレジスタ２２は数Ａを格納しておくレジスタである。羃指数Ｂレジスタ２３は羃指数Ｂを格納しておくレジスタである。剰余Ｒレジスタ２４は演算結果の剰余Ｒを格納しておくレジスタである。
【００１８】
また、図３はパラメタ変換部３及び改良型冗長２進演算部４の詳細を示すものである。
【００１９】
冗長２進表現の法Ｎレジスタ３１は冗長２進表現の法Ｎを格納しておくレジスタである。冗長２進表現の数Ａレジスタ３２は冗長２進表現の数Ａを格納しておくレジスタである。冗長２進表現の剰余Ｒレジスタ３３は冗長２進表現の剰余Ｒを格納しておくレジスタである。初期化回路３４は剰余Ｒレジスタ２４を初期化する。レジスタ３５は羃指数Ｂのビット長を格納する。レジスタ３６は法Ｎのビット長（ｎ）を格納する。
【００２０】
改良型冗長２進演算部４は従来から用いられている冗長２進演算回路のパラメタ入力を改良したものである。冗長２進数乗算部４１は冗長２進数による乗算を実行する。冗長２進数除算部４２は冗長２進数による除算を実行する。冗長２進数乗算パラメタ入力部４３は冗長２進表現の剰余Ｒもしくは数Ａを乗数として冗長２進数乗算部４１に入力する。被乗数レジスタ４４は冗長２進表現の剰余Ｒを被乗数として冗長２進数乗算部４１に入力する。被除数レジスタ４５は冗長２進表現の法Ｎを被除数として冗長２進数除算部４２に入力する。冗長２進数演算途中結果レジスタ４６は冗長２進表現の演算途中結果を格納する。演算途中結果レジスタ４７は通常の２進数による演算途中結果を格納する。
【００２１】
図４は本実施例の全体的な動作フローチャートを、また、図５は羃乗剰余演算時の詳細な動作フローチャートを示すもので、以下、これらに従って動作を説明する。
【００２２】
（１）演算に必要な３つのパラメタのパラメタレジスタへの入力
まず、演算の前にパラメタの入力を開始する（Ｓ１）。ここで、状態遷移制御部５は入力バイト数を数えるカウンタ部６の初期化を指示する。状態遷移制御部５は入力パラメタが法Ｎあるいは羃指数Ｂの入力か否か（Ｓ２）及び法Ｎか否か（Ｓ３）によって指示内容が異なるが、最初は法Ｎの入力を行うものと仮定する。また、以降、状態遷移制御部５はパラメタの入力が終了するまでカウンタ部６にカウントアップを指示する。
【００２３】
状態遷移制御部５は法Ｎの入力であれば、ビットシフト量決定部９の初期化を指示する（Ｓ４）。なお、数Ａあるいは羃指数Ｂの入力の場合はビットシフト量決定部９はそのままの状態を保つ。
【００２４】
状態遷移制御部５は８ビットのデータバスを介して最初に入力用前段バッファ部７に入力された１バイトデータのみを第１オクテット先頭“１”検出部８に取り込むように指示し、第１オクテット先頭“１”検出部８は取り込んだ８ビットのデータの先頭から何ビット目に最初の“１”があるかを検出する。この際、検出された値（０〜７）はビットシフト量決定部９で用いられ、該ビットシフト量決定部９では第１オクテット先頭“１”検出部８からの値が「０」であればビットシフト量を「０」、「１」であればビットシフト量を「１」、……と決定する（Ｓ５）。
【００２５】
入力用前段バッファ部７に格納された１バイトのデータは次の１バイトのデータが入力される前に入力用後段バッファ部１０に転送される。状態遷移制御部５は転送が終了した後に２バイト目以降のデータの入力を指示する。次のデータがある場合は第２オクテットが入力用前段バッファ部７に入力される。
【００２６】
入力用後段バッファ部１０及び入力用前段バッファ部７の２バイトのデータが揃うと、入力用後段バッファ部１０の８ビットを上位８ビット（第１オクテット）とし、入力用前段バッファ部７の８ビットを下位８ビット（第２オクテット）とした計１６ビットのデータを入力用ビットシフト部１１に転送する。入力用ビットシフト部１１ではビットシフト量決定部９で決めたビットシフト量だけ上位にずらしたデータを出力する。
【００２７】
前記出力はバイトシフト部１２のＬＳＢ側から入力される。そして、入力用ビットシフト部１１の出力の上位８ビットのみがバイトシフト部１２に入力される。これにより、入力された第１オクテットが１０進数で「１〜２５５」のどのような値であってもバイトシフト部１２に入力される値は１０進数で「１２８〜２５５」となり、先頭ビットは必ず“１”になる。
【００２８】
第３オクテット目以降は、第２オクテットの後を追うように、カウンタ部６、入力用前段バッファ部７、入力用後段バッファ部１０、入力用ビットシフト部１１を経てバイトシフト部１２に入力される。以降、全データが入力されるまでこの動作を続け、状態遷移制御部５が最後のデータの入力終了を検出する。
【００２９】
法Ｎのデータ入力の場合、バイトシフト部１２に入力された第１オクテットが最上位に移動するように１バイトづつシフトし、空いたところに“０”を補いながらパラメタの補正シフトが行われる（Ｓ８）。このようにして、パラメタ長が計測され（Ｓ６）、状態遷移制御部５からパラメタ長が格納される（Ｓ７）。このパラメタ長はバイトシフト量記憶部１３に記憶される。
【００３０】
法Ｎのデータ入力時には法Ｎレジスタ２１へ、数Ａのデータ入力時は数Ａレジスタ２２へパラメタの格納が行われる（Ｓ９）。法Ｎ入力時にはその後に数Ａを入力することがあるので、さらに続けて数Ａを入力する場合にはステップＳ２に戻り、そうでない場合は終了する（Ｓ１０）。
【００３１】
法Ｎのパラメタが入力された後に数Ａのパラメタの入力が行われるが、その工程は法Ｎの場合とほぼ同じである。唯一、法Ｎの場合と異なる点は、入力用ビットシフト部１１でのビットシフト量とバイトシフト部１２でのバイトシフト量の決定方法であり、数Ａの場合のビットシフト量は法Ｎの場合に決定した値をそのまま用いる。従って、第１オクテット先頭“１”検出部８は動作しない。数Ａのデータは入力後、入力用ビットシフト部１１でビットシフト量決定部９の値の分、ビットシフトされ（Ｓ１１）、バイトシフト部１２でバイトシフト量記憶部１３の値の分、パラメタの補正シフトが行われる（Ｓ８）。
【００３２】
羃指数Ｂの入力に関しては、法Ｎや数Ａのようにシフトさせて入力する必要はないので、カウンタ部６の出力から直接、羃指数Ｂレジスタ２３にパラメタ格納が行われる（Ｓ９）。
以上のようにして３つのパラメタの入力が完了する。
【００３３】
（２）冗長２進演算部へパラメタを入力するためのパラメタ変換
冗長２進演算は、通常、使用する２進表現とは異なり、２ビットで通常の１ビット分のデータを示す。そこで、通常の２進表現を冗長２進表現に変換する必要がある。法Ｎレジスタ２１及び数Ａレジスタ２２に格納されたパラメタは冗長２進表現に変換されて、冗長２進表現の法Ｎレジスタ３１及び冗長２進表現の数Ａレジスタ３２に格納される。
【００３４】
（３）冗長２進演算部での羃乗剰余演算
冗長２進乗算部４１の被乗数レジスタ４４には常に冗長２進表現の剰余Ｒレジスタ３３のデータが入力される。冗長２進除算部４２の被除数レジスタ４５には常に冗長２進表現の法Ｎレジスタ３１のデータが入力される。また、冗長２進除算部４２の除数として、常に冗長２進乗算部４１での乗算結果が入力される。
【００３５】
演算が開始される（Ｓ１２１）と、まず、初期化回路３４により剰余Ｒレジスタ２４及び冗長２進表現の剰余Ｒレジスタ３３が“１”に初期化される（Ｒ＝１，ｉ＝ｋ）（Ｓ１２２）。
【００３６】
▲１▼冗長２進表現の剰余Ｒレジスタ３３のデータを冗長２進乗算部４１の冗長２進乗算数パラメタ入力部４３に入力する。入力後、冗長２進乗算部４１及び冗長２進除算部４２において乗算及び除算が行われ（Ｓ１２３）、冗長２進演算途中結果レジスタ４６に途中結果が出力される。
【００３７】
この演算（Ｒｉ＋１  ＝｛Ｒｉ  ・（Ｒｉ  ・２ｊ  ）｝ｍｏｄ  （Ｎ・２ｊ  ）：但し、ｊ＝バイトシフト量記憶部１３の値＋ビットシフト量決定部９の値）の結果が冗長２進数演算途中結果レジスタ４６に出力され、通常の２進数表現に戻した結果が演算途中結果レジスタ４７に出力される。この値が次の剰余Ｒレジスタ２４のデータとなる。剰余Ｒレジスタ２４のデータは再び冗長２進表現に変換され、冗長２進表現の剰余Ｒレジスタ３３に格納される。
【００３８】
▲２▼羃指数Ｂレジスタ２３のデータの先頭ビットを見て“１”（ｂｉ  ＝１）でなければ（Ｓ１２４）、この作業は飛ばす。
【００３９】
冗長２進数乗算パラメタ入力部４３に冗長２進表現の数Ａレジスタ３２のデータを入力し、乗算・除算を行い（Ｓ１２５）、その演算（Ｒｉ＋１  ＝｛Ａ・（Ｒｉ  ・２ｊ  ）｝ｍｏｄ  （Ｎ・２ｊ  ））の結果が冗長２進数演算途中結果レジスタ４６に出力され、通常の２進数表現に戻した結果が演算途中結果レジスタ４７に出力される。
【００４０】
▲３▼羃指数Ｂレジスタ２３のデータの先頭ビットの値を破棄し、次のビットを先頭ビットとする。同時に羃指数Ｂビット長レジスタ３５の値が０（ｉ＝０）でなければ１減らし（ｉ＝ｉ−１）、▲１▼に戻る。ｉ＝０になれば、このフェーズを終了する（Ｓ１２６，Ｓ１２７，Ｓ１２８）。
【００４１】
（４）演算結果の出力
剰余Ｒレジスタ２４の値が求める演算結果である。但し、この値は２ｊ  倍されているので、パラメタ出力時に以下のようにして逆補正する。
【００４２】
状態遷移制御部５の指示により、剰余Ｒレジスタ２４内の演算結果の第１オクテットが出力用前段バッファ部１４に取り込まれる。次に、出力用前段バッファ部１４に取り込まれた第１オクテットが出力用後段バッファ部１５に移され、第２オクテットが出力用前段バッファ部１４に取り込まれる。
【００４３】
出力用後段バッファ部１５の８ビットを上位８ビット（第１オクテット）とし、出力用前段バッファ部１４の８ビットを下位８ビット（第２オクテット）とした計１６ビットのデータは、出力用ビットシフト部１６にて、法Ｎの入力時に決定したビットシフト量決定部９からの値により下位にシフトする。そして、出力用ビットシフト部１６の出力の上位８ビットのみが８ビットのデータとして出力される。出力すべきデータのオクテット数は、法Ｎの入力時のカウンタ部６の値を減少させて０になるまで出力する（Ｓ１３〜Ｓ１７）。
【００４４】
なお、演算結果以外の法Ｎ、数Ａのパラメタ出力は剰余Ｒレジスタ２４からの出力の場合と全く同じである。また、羃指数Ｂの出力はビットシフトやバイトシフトは行われていないので、羃指数レジスタ２３から直接出力する。
【００４５】
【発明の効果】
以上説明したように本発明によれば、冗長２進演算方法の長所である多倍長の高速演算性を生かしつつ、短所である羃乗剰余演算の際の法の最上位ビットが“１”に限定される、即ちビット長が一定値に限定されるという制約を解決することができる。
【図面の簡単な説明】
【図１】本発明の一実施例を示す構成図
【図２】パラメタ入出力補正部及びパラメタレジスタ部の詳細を示す構成図
【図３】パラメタ変換部及び改良型冗長２進演算部の詳細を示す構成図
【図４】全体的な動作フローチャート
【図５】羃乗剰余演算時の詳細な動作フローチャート
【符号の説明】
１…パラメタ入出力補正部、２…パラメタレジスタ部、３…パラメタ変換部、４…改良型冗長２進演算部、５…状態遷移制御部。
【図１】
0003555091.tif 000004
【図２】
0003555091.tif 000005
【図３】
0003555091.tif 000006
【図４】
0003555091.tif 000007
【図５】
0003555091.tif 000008