(57)【特許請求の範囲】
【請求項１】
それぞれが同一の内部構成を有し、各回次の除算演算において、それぞれが被除数の蓄積手段としての役割、被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割、除数の保持手段としての役割のうち相互に重複しないように割り当てられたいずれか一つの役割を実行する第１、第２及び第３のシフトレジスタ部と、
各回次の除算演算の完了時、現回次の除算演算で被除数の蓄積手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割を実行するよう割り当てを指示し、現回次の除算演算で被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において除数の保持手段としての役割を実行するよう割り当てを指示し、現回次の除算演算で除数の保持手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において被除数の蓄積手段としての役割を実行するよう割り当てを指示することにより、各回次の除算演算毎に、各シフトレジスタ部に割り当てる役割を再設定する制御手段と
を備えることを特徴とするユークリッド互除法実行回路。
【請求項２】
請求項１に記載のユークリッド互除法実行回路と、
上記ユークリッド互除法実行回路における各回次の除算演算結果と、任意の数とを乗算して出力する乗算回路と
を備えることを特徴とする演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ユークリッド互除法を実行する回路に関する。また、当該回路の計算結果を乗算演算に使用する演算回路に関する。
【０００２】
【従来の技術】
ユークリッド互除法とは、与えられた初期値である除数と被除数を用いて除算演算を繰り返し実施する演算操作をいう。このユークリッド互除法では、Ｋ回目の除算と（Ｋ＋１）回目の除算との間に、以下の関係が成り立つ。すなわち、Ｋ回目の除算演算で用いた除数が（Ｋ＋１）回目の除算演算においては被除数となり、Ｋ回目の除算演算で得られた余りが（Ｋ＋１）回目の除算演算においては除数となるという関係が成り立つ。つまり、（Ｋ＋１）回目の除算演算において、（Ｋ回目の除算演算の除数）／（Ｋ回目の除算演算による余り）なる除算演算が実施される関係が成り立つ。
【０００３】
図２に、上述のユークリッド互除法に基づく逐次的計算処理を実行する回路（以下「ユークリッド互除法実行回路」という。）の従来例を示す。当該ユークリッド互除法実行回路は、バッファ回路１と除算回路２からなる。
【０００４】
このうち、バッファ回路１は、複数段のＤフリップフロップ（以下「Ｄ−ＦＦ」という。）で構成されたシフトレジスタＣからなる。このシフトレジスタＣは被除数の蓄積用である。ここで、被除数は、その高次の項がシフトレジスタＣの出力側（図中右側）となるように順番に蓄積されている。
【０００５】
一方、除算回路２は、複数段のＤ−ＦＦと当該段数に応じた個数の加算器及び乗算器で構成されたシフトレジスタＡと、複数段のＤ−ＦＦで構成されたシフトレジスタＢからなる。当該構成は、除算回路に一般的な構成である。
【０００６】
ここで、シフトレジスタＢは除数の保持用である。シフトレジスタＢには、高次の項が出力側（図中右側）になるように除数が蓄積される。一方、シフトレジスタＡは、被除数の入力用である。シフトレジスタＡには、高次の側から順次格納される被除数が全て入力し終わった時（厳密には、１クロック後）、複数段のＤ−ＦＦに当該除算演算による余りが現れる。
【０００７】
ところで、当該回路では、Ｋ回目の除算演算が終了すると即座に（Ｋ＋１）回目の除算演算に移行するのではなく、シフトレジスタＡの値（Ｋ回目の除算演算の余り）を除数を保持するシフトレジスタＢにロードし、同じに、シフトレジスタＢの値（Ｋ回目の除算演算の除数）を被除数を蓄積するシフトレジスタＣにロードしてから（Ｋ＋１）回目の除算演算に移行する動作を採る。かかる動作を行うことにより、Ｋ回目の除算演算の除数が（Ｋ＋１）回目の除算演算の被除数になり、Ｋ回目の除算演算の余りが（Ｋ＋１）回目の除算演算の除数になるという関係が保たれ、ユークリッド互除法に基づく除算演算が実現される。
【０００８】
【発明が解決しようとする課題】
しかしながら、上述した構成の回路では、Ｋ回目の除算演算の後（Ｋ＋１）回目の除算演算に移行する際に、シフトレジスタＡの値（余り）をシフトレジスタＢ（除数）に、またシフトレジスタＢの値（除数）をシフトレジスタＣにロードするという操作が必要となり、ユークリッド互除法を実施するためには、除算演算の他にシフトレジスタ間での値の移動必要となり、ユークリッド互除法に基づく本来の除算演算を連続して実施することができなかった。
【０００９】
本発明は以上の課題を考慮してなされたものであり、連続的な除算演算の可能なユークリッド互除法実行回路の提案を目的とする。
【００１０】
【課題を解決するための手段】
（Ａ）かかる課題を解決するため、本発明においては、ユークリッド互除法実行回路を以下の手段で構成する。すなわち、(1) それぞれが同一の内部構成を有し、各回次の除算演算において、それぞれが被除数の蓄積手段としての役割、被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割、除数の保持手段としての役割のうち相互に重複しないように割り当てられたいずれか一つの役割を実行する第１、第２及び第３のシフトレジスタ部と、(2) 各回次の除算演算の完了時、現回次の除算演算で被除数の蓄積手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割を実行するよう割り当てを指示し、現回次の除算演算で被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において除数の保持手段としての役割を実行するよう割り当てを指示し、現回次の除算演算で除数の保持手段としての役割を割り当てられていたシフトレジスタ部に対しては、次回次の除算演算において被除数の蓄積手段としての役割を実行するよう割り当てを指示することにより、各回次の除算演算毎に、各シフトレジスタ部に割り当てる役割を再設定する制御手段で構成する。
【００１１】
このように本発明では、従来装置のように各役割に応じた専用のシフトレジスタ部を設けるのではなく、同一構成でなるシフトレジスタ部間でその役割を各回次の除算演算のたび変更する。
【００１２】
すなわち、本発明の場合には、現回次の除算演算における「余り」が格納されているシフトレジスタ部が、次回次の除算演算では「除数」を保持するシフトレジスタ部としての役割を果たし、現回次の除算演算における「除数」を保持しているシフトレジスタ部が、次回次の除算演算における「被除数」を蓄積するシフトレジスタ部としての役割を果たすことになる。
【００１３】
このため、本発明の場合には、現回次の「余り」や「除数」を他のシフトレジスタ部に移動させる必要がなく、即座に次回次の除算演算を開始することができる。
【００１４】
なお、現回次の除算演算において「被除数」を蓄積していたシフトレジスタ部は、次回次の除算演算では、非常数を順次入力し、除算終了時に余りを得る手段としての役割を果たすために一旦初期化されるため、値の移動は発生しない。
（Ｂ）かかる課題を解決するため、本発明においては、演算回路を以下の手段で構成する。すなわち、(1) 請求項１に記載のユークリッド互除法実行回路と、(2) ユークリッド互除法実行回路における各回次の除算演算結果と、任意の数とを乗算して出力する乗算回路で構成する。
【００１５】
このように本発明では、乗算回路に除算演算結果を与えるユークリッド互除法実行回路として、請求項１に記載のユークリッド互除法実行回路を適用するため、除算演算の開始と同時に、その演算結果を高次から順番に入力することができる。
【００１６】
このことは、各回次の除算演算が完了し、演算結果の全ての情報が出揃うのを待たなくても良いことを意味するため、乗算結果が得られるまでの時間の短縮を実現できる。
【００１７】
【発明の実施の形態】
（Ａ）ユークリッド互除法実行回路の実施形態
（Ａ−１）装置構成
図１に、装置の全体構成を示す。なお、図１は、当該装置の構成を機能ブロックにより概念的に表したものである。
【００１８】
本実施形態に係る装置の特徴は、当該装置を構成する各シフトレジスタが相互に対等な関係にあり、各回毎に、除算演算上における各々の役割（「被除数の蓄積手段としての役割」、「被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割」、「除数の保持手段としての役割」）を巡回的に持ちまわる点にある。
【００１９】
かかる機能を実現するため、本実施形態に係る装置は、同一構成を有する３つのシフトレジスタ部Ａ、Ｂ、Ｃと、各回ごとに各シフトレジスタ部が果たすべき除算演算上の役割を巡回的に割り当てる制御部（ＣＯＮＴ）と、各回ごとの「除数」と「余り」を選択的に出力する出力部とからなる。
【００２０】
図中、制御部（ＣＯＮＴ）より各レジスタ部に与えられる制御信号ＳCONTが出力部にも与えられているが、これは、いずれのシフトレジスタ部から与えられる出力が、今回の除算演算において「除数」であるか「余り」であるかを出力部において認識可能とするためである。
【００２１】
図３に、かかる動作を可能とするシフトレジスタ部Ａ〜Ｃの構成を示す。図３に示すように、各シフトレジスタ部は、複数段（ｎ＋１段）のＤ−ＦＦ部と、該段数に応じた複数段（ｎ段）の加算器と、同じく該段数に応じた複数段（ｎ段）の乗算器と、１個の除算器からなる。
【００２２】
なお、本実施形態におけるこの構成は、従来装置を構成する除算回路のシフトレジスタＡ（図２）に相当する。換言すると、従来装置の除算回路からシフトレジスタＢ（図２）を除いた構成に相当する。かかる構成が可能なのは、前述したように、本実施形態における各シフトレジスタ部が、いずれも、「除数の保持手段」としても機能し得ることに起因している。
【００２３】
因みに、かかる「除数の保持手段」としての機能を実現するため、本実施形態では、自らの出力を入力側に帰還する経路を備えるＤ−ＦＦ部を使用する。図４に、シフトレジスタ部を構成するＤ−ＦＦ部の構成を示す。なお、図４（Ａ）は、初段（図３に示す各シフトレジスタ部の左端）に位置するＤ−ＦＦ部の構成を表したものであり、図４（Ｂ）は、初段と最後段を除く各段に位置するＤ−ＦＦ部の構成を表したものであり、図４（Ｃ）は、最後段（図３に示す各シフトレジスタ部の右端）に位置するＤ−ＦＦ部の構成を表したものである。
【００２４】
図４に示すように、いずれのＤ−ＦＦ部も、選択手段（ＳＥＬ）とＤ−ＦＦを構成要素に備えて構成されている。因みに、初段のＤ−ＦＦ部は、２入力１出力の選択手段（ＳＥＬ）とＤ−ＦＦを構成要素に有し、中段及び最終段のＤ−ＦＦ部は、３入力１出力の選択手段（ＳＥＬ）とＤ−ＦＦを構成要素に有している。
【００２５】
なお、各Ｄ−ＦＦ部の選択手段（ＳＥＬ）には、各Ｄ−ＦＦ部が属するシフトレジスタ部に共通の制御信号ＳCONTA〜Cが与えられる。かくして、同一のシフトレジスタ部を構成するＤ−ＦＦ部の選択手段（ＳＥＬ）は、いずれも制御信号ＳCONTA〜Cに応じた同一の入力を選択するようになっている。
【００２６】
例えば、各選択手段（ＳＥＬ）は、自らが属するシフトレジスタ部が「除数の保持手段」として機能することを求められている場合、自らが属するＤ−ＦＦ部の出力を帰還した入力を選択する。この選択は、値の保持を実現する。
【００２７】
また、各選択手段（ＳＥＬ）は、自らが属するシフトレジスタ部が「被除数の蓄積手段」として機能することを求められている場合、自らが属するＤ−ＦＦ部の前段からの入力を選択する。この選択は、シフトレジスタとしての動作を実現する。
【００２８】
また、各選択手段（ＳＥＬ）は、自らが属するシフトレジスタ部が「被除数を順次入力すると共に、除算終了時に余りを得る手段」として機能することを求められている場合、自らが属するＤ−ＦＦ部の前段に位置する加算器からの入力（「除数の保持手段」として機能している他のシフトレジスタ部から逐次与えられる被除数と最後段のＤ−ＦＦ部の出力との乗算結果と、自らが属するＤ−ＦＦ部の前段からの入力との加算値）を選択する。この選択は、被除数の全ての値が取り込まれるまでは、シフトレジスタとしての動作を実現し、被除数の全ての値が取り込まれた後の１クロック目は、除算演算による余りを得る動作を実現する。
【００２９】
なお、各シフトレジスタ部を構成する各Ｄ−ＦＦ部の出力は、各シフトレジスタ部が「除数の保持手段」として機能する際に、「被除数を順次入力すると共に、除算終了時に余りを得る手段」として機能する関係にある他のシフトレジスタ部の乗算器へ並列に出力されるようになっている。
【００３０】
図１及び図３の場合、シフトレジスタ部Ａの出力がシフトレジスタ部Ｃの乗算器へ出力され、シフトレジスタ部Ｂの出力がシフトレジスタ部Ａの乗算器へ出力され、シフトレジスタ部Ｃの出力がシフトレジスタ部Ｂの乗算器へ出力されるようになっている。
【００３１】
なお、各乗算器は、前述のようにそれぞれ対応付けられた他のシフトレジスタ部から与えられる出力と、除算器の出力とを乗算し、対応する加算器に出力する。因みに、除算器については、最高次に対応するＤ−ＦＦ部の出力と前述のようにそれぞれ対応付けられた他のシフトレジスタ部から与えられる出力のうち最高次のものとの乗算を行う。
（Ａ−２）演算動作
続いて、以上の構成を有する装置が、具体的にどのように動作し、ユークリッド互除法実行回路としての動作を実現するかを説明する。
（Ａ−２−１）各役割におけるシフトレジスタ部の動作
まず、各シフトレジスタ部Ａ〜Ｃが、除算演算上における各役割（「被除数の蓄積手段としての役割」、「被除数を順次入力すると共に、除算終了時に余りを得る手段としての役割」、「除数の保持手段としての役割」）を果たすとき、どのように動作するかを説明する。
▲１▼「被除数の蓄積手段」としての動作
これは、被除数を蓄積するバッファとして機能するシフトレジスタ部の動作である。このとき、各シフトレジスタ部を構成するＤ−ＦＦ部は、Ｄ−ＦＦに与える入力として、自らの前段に位置するＤ−ＦＦ部の出力を選択する。
【００３２】
これにより、当該シフトレジスタ部は、クロック信号（ＣＬＫ）の入力の度、各Ｄ−ＦＦ部に保持されている値を、図３の右側へシフトさせるよう動作する。この結果、図３の右端に位置するＤ−ＦＦ部からは、被除数の値が高次の項から順に出力される。
▲２▼「被除数を順次入力すると共に、除算終了時に余りを得る手段」としての動作これは、「被除数の蓄積手段」として機能するシフトレジスタ部から被除数の値を順次入力するシフトレジスタ部の動作である。なお、該シフトレジスタ部は、最初に初期化される。次に、該シフトレジスタ部の初段を構成するＤ−ＦＦ部は、その選択手段（ＳＥＬ）において、▲１▼として機能するシフトレジスタ部を構成する最後段のＤ−ＦＦ部に接続された入力を選択する。これにより、被除数が最高次から順番に入力される。
【００３３】
一方、２段目以降最後段に位置する該シフトレジスタ部の他のＤ−ＦＦ部は、その選択手段（ＳＥＬ）において、前段の加算器の出力を選択するよう動作する。なお、被除数が全て入力されるまでは、該シフトレジスタ部の最後段に位置するＤ−ＦＦ部から“０"が出力されるため、各加算器に与えられる乗算器の出力についても“０"となる。このため、該シフトレジスタ部は、クロック信号（ＣＬＫ）の入力の度、各Ｄ−ＦＦ部に保持されている値を、順次、図３の右側のＤ−ＦＦ段へシフトさせるように動作する。
【００３４】
やがて、全ての被除数の値が取り込まれると、該シフトレジスタ部の最後段に位置するＤ−ＦＦ部から“１"が出力され、乗算結果として除数が出力される状態になる。そして、その直後の１クロック目に、被除数と除数とが加算器で加算される。この結果、２段目以降最後段に位置する該シフトレジスタ部のＤ−ＦＦ部に、除算演算結果としての「余り」が現れる。
▲３▼「除数の保持手段」としての動作
これは、除数の値を保持するシフトレジスタ部の動作である。このとき、該シフトレジスタ部を構成する各Ｄ−ＦＦ部は、自らの出力を選択するように動作する。これにより、当該シフトレジスタ部は、クロック信号（ＣＬＫ）の入力に関わらず、値を保持する。
（Ａ−２−２）装置全体としての動作
さて、除算は、前述の▲１▼のシフトレジスタ部から前述の▲２▼のシフトレジスタ部に被除数が１データずつ入力されることで実施される。そして、全ての被除数が入力された時点で各回時における除算演算が終了し、▲２▼のシフトレジスタ部に除算演算の余りが残っていることになる。
【００３５】
ここでは、Ｋ回目、（Ｋ＋１）回目、（Ｋ＋２）回目の除算演算について、シフトレジスタ部Ａ、Ｂ、Ｃがそれぞれどのように役割を分担して動作するかを示す。なお、本実施形態における各シフトレジスタ部が、各除算演算時において、機能をどのように分担するかを図５に模式的に示しておく。ただし、かかる関係は、図１及び図３に示した接続の場合の関係である。
（ａ）Ｋ回目
制御部（ＣＯＮＴ）は、シフトレジスタ部Ａに対し、前述の▲１▼のシフトレジスタ部として動作するように制御信号ＳCONTA を与え、シフトレジスタ部Ｂに対し、前述の▲２▼のシフトレジスタ部として動作するように制御信号ＳCONTB を与え、シフトレジスタ部Ｃに対し、前述の▲３▼のシフトレジスタ部として動作するように制御信号ＳCONTC を与える。
【００３６】
かかる制御信号ＳCONTに応じ、シフトレジスタ部Ａ〜Ｃは、それぞれ割り当てられた役割に応じた動作を実行し、除算演算の完了時に、シフトレジスタ部Ｂに余りを得る。
【００３７】
なお、シフトレジスタ部Ｂを構成する複数段のＤ−ＦＦ部からは「余り」が、また、シフトレジスタ部Ｃを構成する複数段のＤ−ＦＦ部からは「除数」が出力部に並列的に出力される。
【００３８】
ここで、出力部は、制御信号ＳCONTにより、シフトレジスタ部Ｂからの入力が「余り」であり、シフトレジスタ部Ｃからの入力が「除数」であることを認識しているため、これら２つのシフトレジスタ部からの入力を演算結果として出力する。
（ｂ）（Ｋ＋１）回目
（Ｋ＋１）回目の除算演算で使用する被除数は、Ｋ回目の除算演算における除数であり、（Ｋ＋１）回目の除算演算で使用する除数は、Ｋ回目の除算演算における余りである。
【００３９】
そこで、制御部（ＣＯＮＴ）は、シフトレジスタ部Ａに対し、前述の▲２▼のシフトレジスタ部として動作するように制御信号ＳCONTA を与え、シフトレジスタ部Ｂに対し、前述の▲３▼のシフトレジスタ部として動作するように制御信号ＳCONTB を与え、シフトレジスタ部Ｃに対し、前述の▲１▼のシフトレジスタ部として動作するように制御信号ＳCONTC を与える。
【００４０】
かかる制御信号ＳCONTを与えることにより、シフトレジスタ部Ａ〜Ｃは、それぞれの中身を移動することなく、（Ｋ＋１）回目の除算演算を即座に実施できる。なお、除算演算の余りは、シフトレジスタ部Ａに残ることになる。
【００４１】
かくして、この場合は、シフトレジスタ部Ａを構成する複数段のＤ−ＦＦ部からは「余り」が、また、シフトレジスタ部Ｂを構成する複数段のＤ−ＦＦ部からは「除数」が出力部に並列的に出力される。
（ｃ）（Ｋ＋２）回目
（Ｋ＋２）回目の除算演算で使用する被除数は、（Ｋ＋１）回目の除算演算における除数であり、（Ｋ＋２）回目の除算演算で使用する除数は、（Ｋ＋１）回目の除算演算における余りである。
【００４２】
そこで、制御部（ＣＯＮＴ）は、シフトレジスタ部Ａに対し、前述の▲３▼のシフトレジスタ部として動作するように制御信号ＳCONTA を与え、シフトレジスタ部Ｂに対し、前述の▲１▼のシフトレジスタ部として動作するように制御信号ＳCONTB を与え、シフトレジスタ部Ｃに対し、前述の▲２▼のシフトレジスタ部として動作するように制御信号ＳCONTC を与える。
【００４３】
かかる制御信号ＳCONTを与えることにより、シフトレジスタ部Ａ〜Ｃは、それぞれの中身を移動することなく、（Ｋ＋２）回目の除算演算を即座に実施できる。なお、除算演算の余りは、シフトレジスタ部Ｃに残ることになる。
【００４４】
かくして、この場合は、シフトレジスタ部Ｃを構成する複数段のＤ−ＦＦ部からは「余り」が、また、シフトレジスタ部Ａを構成する複数段のＤ−ＦＦ部からは「除数」が出力部に並列的に出力される。
【００４５】
なお、（Ｋ＋３）回目以降の処理は、Ｋ回目、（Ｋ＋１）回目、（Ｋ＋２）貝目の処理の繰り返しとなる。
（Ａ−３）実施形態装置の効果
以上説明したように、本実施形態に係る構成のユークリッド互除法実行回路の場合には、各シフトレジスタ部Ａ、Ｂ、Ｃの動作役割を１回の除算演算が終了するたびに順送りに切り替えるため、従来装置のようなシフトレジスタ間のデータ移動なしにユークリッド互除法に基づく算出処理を実現することが可能になる。
【００４６】
従って、本実施形態に係るユークリッド互除法実行回路は、従来装置では無し得なかった連続的な除算演算を実現できる。
（Ａ−４）他の実施形態
(1) 上述の実施形態においては、ユークリッド互除法実行回路がその出力として、各回次の除算演算で用いた「除数」と「余り」を並列に出力する場合について述べたが、各値を高次の項から順番に出力する（すなわち、図３の図中、該当するシフトレジスタ段の右端から順番に出力する）ようにしても良い。
(2) また、上述の実施形態においては、ユークリッド互除法実行回路がその出力として、各回次の除算演算で用いた「除数」と「余り」を出力する場合について述べたが、出力する演算結果は、これらのうちの一方だけでも良く、また、各回次の除算演算で得られた「商」を出力するようにしても良い。
(3) 上述の実施形態においては、制御部（ＣＯＮＴ）の具体的な構成については言及しなかったが、当該制御部は、当該実行回路専用に設けられた制御部のほか、汎用の制御部を用いても良い。また、当該制御部は、マイクロプロセッサ構成のものに限らず、割り当て順序をテーブル等に記憶したメモリ等であっても良い。
（Ｂ）演算装置の実施形態
続いて、前述のユークリッド互除法実行回路を適用する演算装置の実施形態例を説明する。
（Ｂ−１）装置構成及び演算動作
図６に、演算装置の全体構成を示す。図６に示す演算装置は、前述のユークリッド互除法実行回路からなるユークリッド互除法実行回路と乗算回路を組み合わせたものである。ただし、この演算装置では、ユークリッド互除法実行回路の各除算演算毎に得られる「商」と、任意の数値との乗算演算を実行する。
【００４７】
図７に、本実施形態に係る演算装置のもう一つの構成要素である乗算回路の構成について示す。なお、図７は、多項式の乗算回路として一般的な構成を表したものであり、既存の他の構成のものを用いても良い。乗算回路は、乗数又は被乗数のうち桁数の大きい方に応じた段数（ｎ＋１段）の乗算器と、当該段数に応じた段数（ｎ段）のラッチ回路と、同じく該段数に応じた段数（ｎ段）の加算器とからなる。
【００４８】
このうち乗算器は、右側に位置するものほど乗数及び被乗数の高次の桁に対応する。なお、これら乗算器には、高次の桁に対応する図中右端の乗算器から順番に、Ａn 、Ａn-1 、…Ａ2 、Ａ1 、Ａ0 が被乗数として与えられている。一方、これら乗算器の他の入力端には、ユークリッド互除法実行回路の出力として各除算演算における「商」が乗数として与えられるようになっている。
【００４９】
これら各乗算器における乗算結果のうち初段（図中左端）の出力は、ラッチ回路に入力されて保存され、２段目以降の乗算器からの出力は加算器に与えられる。なお、加算器では、前段のラッチ回路に保存されている値と乗算器の出力との加算が行われ、次段のラッチ回路に出力されるようになっている。因みに、各ラッチ回路は、加算結果（初段については乗算結果）の採り得る最大値に応じたビット幅の記憶部を備えるものとする。
【００５０】
かかる構成により、本実施形態に係る演算装置では、ユークリッド互除法実行回路における各回次の除算演算が終了し、その演算結果として「商」が与えられるたび、当該商（乗数）と任意の数（被乗数である「Ａn Ａn-1 …Ａ2 Ａ1 Ａ0 」）との乗算演算が実行されることになる。
【００５１】
なお、本実施形態に使用するユークリッド互除法実行回路では、除算演算の開始とともに、その演算結果である「商」を高次の項から順番に出力するようになっているので、乗算回路はその値をそのまま次々と入カし、乗算演算を実行するだけで良い。
【００５２】
すなわち、乗算回路は、（除算回路の商）×（任意の数）なる乗算演算を、ユークリッド互除法実行回路における各除算演算の「商」が高次の項から出力されると即座に開始することができ、除算演算が終了し商がすべて出揃うのを待つ必要なく、得られた商の値からそのまま乗算演算に移ることができる。
（Ｂ−２）実施形態装置の効果
このように、本実施形態に係る演算装置の場合には、除算演算から乗算演算への工程に必要な時間を短縮でき、演算処理に要する時間の短縮を実現できる。
（Ｂ−３）他の実施形態
(1) 上述の実施形態においては、演算装置の一般例について説明したが、かかる装置を、リードソロモン符号をユークリッド法を用いて誤り訂正する場合に利用することもできる。リードソロモン符号の誤り訂正は、誤り位置多項式と誤り評価多項式を得ることで実現されている。ユークリッド法は、その誤り位置多項式と誤り評価多項式をユークリッド互除演算と乗算演算の組み合わせで得る方法である。
【００５３】
ユークリッド法は、▲１▼ユークリッド互除法の実行→▲２▼その際の除算演算で得られた「商」と任意の数との乗算演算の実行という操作を繰り返し行うことにより実現される。従って、２番目の実施形態で説明した演算装置（すなわち、ユークリッド互除法実行回路と乗算回路とを組み合わせたもの）を、リードソロモン符号の誤り訂正に用いれば、前記▲１▼→▲２▼の操作を簡単に実施できるので、当該演算装置は、ユークリッド法を用いてのリードソロモン符号の誤りを訂正する場合に適している。
(2) 上述の実施形態においては、演算回路の例として、ユークリッド互除法実行回路と乗算回路とを組み合わせる場合について述べたが、他の演算回路（例えば、加算回路、減算回路等）と組み合わせる場合にも適用し得る。
【００５４】
【発明の効果】
上述のように、請求項１に係る発明においては、第１、第２及び第３の各シフトレジスタ部を同一回路構成とし、それぞれにおいて、除算演算実行時における各役割を分担すると共に、各回次に応じて分担する役割の割り当ても変更するようにしたことにより、現回次で得られた「余り」や「除数」を次回次の除算演算に先立って、他のシフトレジスタ部に移動させる必要をなくすことができる。かくして、ユークリッド互除法に係る演算処理に要する時間のさらなく削減を実現できる。
【００５５】
また上述のように、請求項２に係る発明においては、請求項１に記載のユークリッド互除法実行回路と、該回路における各回次の除算演算結果と任意の数とを乗算して出力する乗算回路により演算回路を構成したことにより、除算演算の開始と同時に、その演算結果を高次から順番に乗算回路に入力することが可能となり、各回次の除算演算が完了して演算結果の全ての情報が出揃うのを待たなければならなかった従来装置に秘して格段に処理時間の短縮を実現できる。
【図面の簡単な説明】
【図１】ユークリッド互除法実行回路の実施形態例を示すブロック図である。
【図２】従来装置の回路構成を示すブロック図である。
【図３】実施形態装置を構成する各シフトレジスタ段の内部構成を示す図である。
【図４】各シフトレジスタ段を構成するＤ−ＦＦ部の内部構成を示す図である。
【図５】各シフトレジスタ段が分担する機能の状態遷移を表した図である。
【図６】演算装置の実施形態例を示すブロック図である。
【図７】実施形態装置を構成する乗算器の内部構成を示す図である。
【符号の説明】
１…バッファ回路、２…除算回路、Ａ、Ｂ、Ｃ…シフトレジスタ部。
【図１】
0003953220.tif 000002
【図２】
0003953220.tif 000003
【図３】
0003953220.tif 000004
【図４】
0003953220.tif 000005
【図５】
0003953220.tif 000006
【図６】
0003953220.tif 000007
【図７】
0003953220.tif 000008