Warning: copy(.htaccess): failed to open stream: Permission denied in /home/jp321/public_html/header.php on line 8
除算装置および除算方法 - 松下電器産業株式会社
米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 除算装置および除算方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−36669
公開日 平成7年(1995)2月7日
出願番号 特願平5−180336
出願日 平成5年(1993)7月21日
代理人 【弁理士】
【氏名又は名称】中島 司朗
発明者 鈴木 正人
要約 目的
除算装置の回路規模の低減、および除算速度の高速化を図る。

構成
制御回路8が、除数レジスタ1と同じビット幅の演算回路2の最上位ビットからの桁上げ(ACRY)、シフトあふれ保持レジスタ7の値(SCRY)、および第二レジスタ6の最下位ビットの値(1つ前の部分商Q(n-1) )に基づいて、演算回路2の演算の種類(OPR)、第一シフタ3のシフト数(SFT1)、および第二シフタ5のシフト数(SFT2)を指示するとともに、第二シフタ5の1ビットシフト時の最下位ビットへの挿入値(部分商Q(n) )を生成するように構成されている。
特許請求の範囲
【請求項1】 符号なし2進数の除算を行う除算装置であって、除数と同じビット幅を有し、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算手段と、加減算結果を1ビット上位ビット側にシフトするシフト手段と、上記演算手段からの桁上げの値、シフト手段からのシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商を求める部分商算出手段とを備えたことを特徴とする除算装置。
【請求項2】 上記部分商算出手段が、演算手段からの桁上げの値、シフト手段からのシフトあふれの値、および直前の部分商の値に基づいて、除数のビット幅より1ビット上位のビットからさらに上位のビットへの桁上がりの値を求める桁上がり検出手段と、上記桁上がりの値に応じて、新たな部分商を決定する部分商決定手段とを有していることを特徴とする請求項1の除算装置。
【請求項3】 上記桁上がり検出決定手段は、演算手段からの桁上げの値、シフト手段からのシフトあふれの値、および直前の部分商の値のうちの、少なくとも2つの値が1である場合に、桁上がりの値を1とする一方、その他の場合には0とするように構成され、部分商決定手段は、上記桁上がりの値を新たな部分商として決定するように構成されていることを特徴とする請求項2の除算装置。
【請求項4】 符号なし2進数の除算を行う除算方法であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて除数と同じビット幅で加減算する演算ステップと、加減算結果を1ビット上位ビット側にシフトするシフトステップと、上記演算ステップの演算による桁上げの値、シフトステップによるシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商を求める部分商算出ステップとを有することを特徴とする除算方法。
【請求項5】 上記部分商算出ステップが、演算ステップによる桁上げの値、シフトステップによるシフトあふれの値、および直前の部分商の値に基づいて、除数のビット幅より1ビット上位のビットからさらに上位のビットへの桁上がりの値を求める桁上がり検出ステップと、上記桁上がりの値に応じて、新たな部分商を決定する部分商決定ステップとを有することを特徴とする請求項4の除算方法。
【請求項6】 上記桁上がり検出決定ステップは、演算ステップによる桁上げの値、シフトステップによるシフトあふれの値、および直前の部分商の値のうちの、少なくとも2つの値が1である場合に、桁上がりの値を1とする一方、その他の場合には0とするステップであり、部分商決定ステップは、上記桁上がりの値を新たな部分商として決定するステップであることを特徴とする請求項5の除算装置。
【請求項7】 符号なし数の除数を保持する除数保持手段と、第1と第2の2つの入力に対して加算を行いその結果を出力するかもしくは第1の入力から第2の入力の減算を行いその結果を出力するかもしくは第1の入力をそのまま転送して出力する演算手段と、前記演算手段の出力を上位ビット方向に1ビットシフトするかもしくはそのまま転送する第一シフト手段と、除算処理の開始時には、符号なし数の被除数の前記除数保持手段の語長に等しい語長の上位部分を保持し、処理の実行中には、前記第一シフト手段の出力を保持し、処理の終了時には、剰余を保持する第一データ保持手段と、処理の開始時には、前記被除数の残りの下位部分を保持し、処理の実行中には、上位ビット方向にシフトされた前記被除数の下位部分と商の一部とを保持し、処理の終了時には、商を保持する第二データ保持手段と、前記第二データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくはそのまま転送して結果を再び前記第二データ保持手段に格納する第二シフト手段と、前記第一シフト手段における最上位ビットからのシフトあふれを保持する第三データ保持手段と、内部に計数手段を持ち、前記演算手段に対しては、前記計数手段が処理の開始を示すときには減算を指示し、前記計数手段が処理の開始から終了までの間であることを示すときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば減算を指示し、前記計数手段が処理の終了を示すときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば第1入力の転送を指示し、前記第一シフト手段に対しては、前記計数手段が処理の終了または直前の処理でないことを示すときには、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了またはその直前の処理であることを示すときには転送を指示し、前記第二シフト手段に対しては、前記計数手段が処理の開始を示すときには前記演算手段における桁上げを最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の開始から終了までの間であることを示すときには、前記演算手段における桁上げと前記第二データ保持手段の最下位ビットの値と前記第三データ保持手段に保持された値とによって定まる値を最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示する制御手段とを備え、前記第一データ保持手段に保持された値および前記除数保持手段に保持された値をそれぞれ前記演算手段の第1および第2の入力とし、前記第一シフト手段の最下位ビットに挿入する値を前記第二シフト手段における最上位ビットからのシフトあふれとし、前記演算手段における演算と前記第一シフト手段および前記第二シフト手段におけるシフトとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して商および剰余を求めるように構成されていることを特徴とする除算装置。
【請求項8】 除算処理の開始時に、符号なし数の被除数を符号なし数の除数の語長に等しい語長の上位部分と残りの下位部分とに分け、それぞれを第一の値または第二の値として保持する初期設定ステップと、繰り返し処理の処理回数を数える計数ステップと、前記計数ステップにより処理の開始が示されるときには、前記第一の値から前記除数を減じ、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、前記第二の値の最下位ビットが0ならば前記第一の値と前記除数とを加える一方、1ならば前記第一の値から前記除数を減じ、前記計数ステップにより処理の終了が示されるときには、前記第二の値の最下位ビットが0である場合に第一の値と前記除数とを加える演算ステップと、前記計数ステップにより処理の終了または終了直前の処理でないことが示されるときに、第二のシフトステップにおける最上位ビットからのシフトあふれを最下位ビットへ挿入するとともに前記演算ステップで得られる値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第一の値とする第一のシフトステップと、前記第一のシフトステップにおける最上位ビットからのシフトあふれを第三の値として保持するシフト桁上げ格納ステップと、前記計数ステップにより処理の開始が示されるときには、前記演算ステップにおける桁上げを最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とし、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、前記演算ステップにおける桁上げ、前記第二の値の最下位ビット、および現ステップの直前のステップにおける前記第三の値に基づいて定まる値を最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とする第二のシフトステップとを有し、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算ステップと前記第一のシフトステップと前記シフト桁上げ格納ステップと前記第二のシフトステップとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して得られる第一の値および第二の値をそれぞれ剰余および商とすることを特徴とする除算方法。
【請求項9】 符号付き2進数の除算を行う除算装置であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算手段と、加減算結果を1ビット上位ビット側にシフトするシフト手段と、上記演算手段からの桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商を求める部分商算出手段とを備えたことを特徴とする除算装置。
【請求項10】 符号付き2進数の除算を行う除算方法であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算ステップと、加減算結果を1ビット上位ビット側にシフトするシフトステップと、上記演算ステップによる桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商を求める部分商算出ステップとを有することを特徴とする除算方法。
【請求項11】 処理の開始時に、符号付き数の被除数を符号付き数の除数の語長に等しい語長の上位部分と残りの下位部分とに分け、それぞれを第一の値または第二の値として保持する初期設定ステップと、繰り返しの処理回数を数える計数ステップと、前記計数ステップにより処理の開始が示されるときには、前記被除数と前記除数とが同符号ならば前記第一の値から前記除数を減じる一方異符号ならば前記第一の値と前記除数とを加え、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、前記第二の値の最下位ビットが0ならば前記第一の値と前記除数とを加える一方1ならば前記第一の値から前記除数を減じ、前記計数ステップにより処理の終了が示されるときには、前記第二の値の最下位ビットが0ならば第一の値と前記除数とを加える演算ステップと、前記計数ステップにより処理の終了または終了直前の処理でないことが示されるときに、第二のシフトステップにおける最上位ビットからのシフトあふれを最下位ビットへ挿入するとともに前記演算ステップで得られる値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第一の値とする第一のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、前記演算ステップにおける桁上げまたはその反転値を最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とする第二のシフトステップとを有し、前記第二のシフトステップにおいて最下位ビットへ挿入する値を、前記除数の符号が負でかつ現在または1つ前の処理における前記第一の値のいずれかのビットまたは前記第二の値のうち直前のステップまでに最下位ビットに挿入されたものを除く部分のいずれかのビットが1のときには、前記演算ステップにおける桁上げの反転とし、それ以外のときには前記演算ステップにおける桁上げとし、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算ステップと前記第一のシフトステップと前記第二のシフトステップとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して得られる第一の値および第二の値をそれぞれ剰余および商とすることを特徴とする除算方法。
【請求項12】 処理の開始時に、符号付き数の被除数を符号付き数の除数の語長に等しい語長の上位部分と残りの下位部分とに分け、それぞれを第一の値または第二の値として保持する初期設定ステップと、繰り返しの処理回数を数える計数ステップと、前記計数ステップにより処理の開始が示されるときには、前記被除数と前記除数とが同符号ならば前記第一の値から前記除数を減じる一方異符号ならば前記第一の値と前記除数とを加え、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、第三の値の最下位ビットが0ならば前記第一の値と前記除数とを加える一方1ならば前記第一の値から前記除数を減じ、前記計数ステップにより処理の終了が示されるときには、前記第三の値の最下位ビットが0ならば第一の値と前記除数とを加える演算ステップと、前記計数ステップにより処理の終了またはその直前の処理でないことが示されるときには、第二のシフトステップにおける最上位ビットからのシフトあふれを最下位ビットへ挿入するとともに前記演算ステップで得られる値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第一の値とする第一のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、0を最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とする第二のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、前記演算ステップにおける桁上げまたはその反転値を最下位ビットへ挿入するとともに前記第三の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第三の値とする第三のシフトステップとを有し、前記第三のシフトステップにおいて最下位ビットへ挿入する値を、前記除数の符号が負でかつ現在または1つ前の処理における前記第一の値のいずれかのビットまたは前記第二の値のいずれかのビットが1のときには、前記演算ステップにおける桁上げの反転とし、それ以外のときには、前記演算ステップにおける桁上げとし、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算ステップと前記第一のシフトステップと前記第二のシフトステップと前記第三のシフトステップとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して得られる第一の値および第三の値をそれぞれ剰余および商とすることを特徴とする除算方法。
【請求項13】 符号付き数の除数を保持する除数保持手段と、第1と第2の2つの入力に対して加算を行いその結果を出力するかもしくは第1の入力から第2の入力の減算を行いその結果を出力するかもしくは第1の入力をそのまま転送して出力する演算手段と、前記演算手段の出力を上位ビット方向に1ビットシフトするかもしくはそのまま転送する第一シフト手段と、除算処理の開始時には、符号付き数の被除数の前記除数保持手段の語長に等しい語長の上位部分を保持し、処理の実行中には、前記第一シフト手段の出力を保持し、処理の終了時には、剰余を保持する第一データ保持手段と、処理の開始時には、前記被除数の残りの下位部分を保持し、処理の実行中には、上位ビット方向にシフトされた前記被除数の下位部分と商の一部とを保持し、処理の終了時には、商を保持する第二データ保持手段と、前記第二データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくはそのまま転送して結果を再び前記第二データ保持手段に格納する第二シフト手段と、内部に計数手段を持ち、前記演算手段に対しては、前記計数手段が処理の開始を示すときには、前記被除数と前記除数とが同符号ならば減算を指示する一方異符号ならば加算を指示し、前記計数手段が処理の開始から終了までの間であることを示すときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば減算を指示し、前記計数手段が処理の終了を示すときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば第1入力の転送を指示し、前記第一シフト手段に対しては、前記計数手段が処理の終了または直前の処理でないことを示すときには、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了またはその直前の処理を示すときには転送を指示し、前記第二シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、前記演算手段における桁上げまたはその反転値を最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示する制御手段とを備え、前記第一データ保持手段に保持された値および前記除数保持手段に保持された値をそれぞれ前記演算手段の第1および第2の入力とし、前記第一シフト手段の最下位ビットに挿入する値を前記第二シフト手段における最上位ビットからのシフトあふれとし、さらに前記制御手段における前記第二シフト手段へ挿入するビットに関する指示を、前記除数の符号が負でかつ現在または1つ前の処理における前記第一データ保持手段のいずれかのビットまたは前記第二データ保持手段のうち既に前記第二シフト手段によって最下位ビットに挿入されている値のすべてを除く部分のいずれかのビットが1のときには前記演算手段における桁上げの反転とし、それ以外のときには前記演算手段における桁上げとし、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算手段における演算と前記第一シフト手段および前記第二シフト手段におけるシフトとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して商および剰余を求めることを特徴とする除算装置。
【請求項14】 符号付き数の除数を保持する除数保持手段と、第1と第2の2つの入力に対して加算を行いその結果を出力するかもしくは第1の入力から第2の入力の減算を行いその結果を出力するかもしくは第1の入力をそのまま転送して出力する演算手段と、前記演算手段の出力を上位ビット方向に1ビットシフトするかもしくはそのまま転送する第一シフト手段と、除算処理の開始時には、符号付き数の被除数の前記除数保持手段の語長に等しい語長の上位部分を保持し、処理の実行中には、前記第一シフト手段の出力を保持し、処理の終了時には、剰余を保持する第一データ保持手段と、処理の開始時には、前記被除数の残りの下位部分を保持し、処理の実行中には、上位ビット方向にシフトされた前記被除数の下位部分を保持し、処理の終了時には0を保持する第二データ保持手段と、処理の実行中には商の一部を保持して、処理の終了時には商を保持する第三データ保持手段と、0を最下位ビットに挿入して前記第二データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくは前記第二データ保持手段に保持された値をそのまま転送して結果を再び前記第二データ保持手段に格納する第二シフト手段と、前記第三データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくはそのまま転送して結果を再び前記第三データ保持手段に格納する第三シフト手段と、内部に計数手段を持ち、前記演算手段に対しては、前記計数手段が処理の開始を示すときには、前記被除数と前記除数とが同符号ならば減算を指示する一方異符号ならば加算を指示し、前記計数手段が処理の開始から終了までの間であることを示すときには、前記第三データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば減算を指示し、前記計数手段が処理の終了を示すときには、前記第三データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば第1入力の転送を指示し、前記第一シフト手段に対しては、前記計数手段が処理の終了または直前の処理でないことを示すときには、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了またはその直前の処理を示すときには転送を指示し、前記第二シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示し、前記第三シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、前記演算手段における桁上げまたはその反転値を最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示する制御手段とを備え、前記第一データ保持手段に保持された値および前記除数保持手段に保持された値をそれぞれ前記演算手段の第1および第2の入力とし、前記第一シフト手段の最下位ビットに挿入する値を前記第二シフト手段における最上位ビットからのシフトあふれとし、さらに前記制御手段における前記第三シフト手段へ挿入するビットに関する指示を、前記除数の符号が負でかつ現在または1つ前の処理における前記第一データ保持手段のいずれかのビットまたは前記第二データ保持手段のいずれかのビットが1のときには、前記演算手段における桁上げの反転とし、それ以外のときには、前記演算手段における桁上げとし、前記計数手段による計数に基づいて、処理の開始から終了までの間に、前記演算手段における演算と前記第一シフト手段および前記第二シフト手段および前記第三シフト手段におけるシフトとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返して商および剰余を求めるように構成されていることを特徴とする除算装置。
【請求項15】 処理の開始時に、符号付き数の被除数を符号付き数の除数の語長に等しい語長の上位部分と残りの下位部分とに分け、それぞれを第一の値または第二の値として格納する初期設定ステップと、繰り返しの処理回数を数える計数ステップと、前記計数ステップにより処理の開始が示されるときには、前記被除数と前記除数とが同符号ならば前記第一の値から前記除数を減じる一方異符号ならば前記第一の値と前記除数とを加え、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、前記第二の値の最下位ビットが0ならば前記第一の値と前記除数とを加える一方1ならば前記第一の値から前記除数を減じ、前記計数ステップにより処理の終了が示されかつ前記被除数と前記除数とが同符号の時は前記第二の値の最下位ビットが0ならば第一の値と前記除数とを加え、前記計数ステップにより処理の終了が示されかつ前記被除数と前記除数とが異符号の時は前記第二の値の最下位ビットが1ならば第一の値から前記除数を減ずる演算ステップと、前記計数ステップにより処理の終了または終了直前の処理でないことが示されるときに、第二のシフトステップにおける最上位ビットからのシフトあふれを最下位ビットへ挿入するとともに前記演算ステップで得られる値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第一の値とする第一のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、前記演算ステップにおける桁上げまたはその反転値を最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とする第二のシフトステップと、前記第二の値に1を加える商補正ステップとを有し、前記第二のシフトステップにおいて最下位ビットへ挿入する値を、前記計数ステップにより処理の開始が示されるときには、前記除数の符号が負ならば前記演算ステップにおける桁上げの反転とする一方正ならば前記演算ステップにおける桁上げとし、前記計数ステップにより処理の開始でないことが示されるときには、前記被除数が正かつ前記除数が負の場合または前記被除数が負かつ前記除数が正でかつ現在または1つ前の処理における前記第一の値の全部のビットおよび前記第二の値のうち直前のステップまでに最下位ビットに挿入されたものを除く部分のビットがいずれも0の場合または前記被除数が負かつ前記除数が負でかつ現在および1つ前の処理における前記第一の値のいずれかのビットまたは前記第二の値のうち直前のステップまでに最下位ビットに挿入されたものを除く部分のいずれかのビットが1の場合は前記演算ステップにおける桁上げの反転とし、それ以外の場合は前記演算ステップにおける桁上げとし、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算ステップと前記第一のシフトステップと前記第二のシフトステップとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返し、得られる第一の値を剰余とし、前記被除数と前記除数とが異符号の時は前記商補正ステップを行い、同符号の時は前記商補正ステップを行わずに得られる第二の値を商とすることを特徴とする除算方法。
【請求項16】 処理の開始時に、符号付き数の被除数を符号付き数の除数の語長に等しい語長の上位部分と残りの下位部分とに分け、それぞれを第一の値または第二の値として保持する初期設定ステップと、繰り返しの処理回数を数える計数ステップと、前記計数ステップにより処理の開始が示されるときには、前記被除数と前記除数とが同符号ならば前記第一の値から前記除数を減じる一方異符号ならば前記第一の値と前記除数とを加え、前記計数ステップにより処理の開始から終了までの間であることが示されるときには、第三の値の最下位ビットが0ならば前記第一の値と前記除数とを加える一方1ならば前記第一の値から前記除数を減じ、前記計数ステップにより処理の終了が示されかつ前記被除数と前記除数とが同符号のときには前記第二の値の最下位ビットが0ならば第一の値と前記除数とを加え、前記計数ステップにより処理の終了が示されかつ前記被除数と前記除数とが異符号の時は前記第二の値の最下位ビットが1ならば第一の値から前記除数を減ずる演算ステップと、前記計数ステップにより処理の終了またはその直前の処理でないことが示されるときには、第二のシフトステップにおける最上位ビットからのシフトあふれを最下位ビットへ挿入するとともに前記演算ステップで得られる値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第一の値とする第一のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、0を最下位ビットへ挿入するとともに前記第二の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第二の値とする第二のシフトステップと、前記計数ステップにより処理の終了でないことが示されるときには、前記演算ステップにおける桁上げまたはその反転値を最下位ビットへ挿入するとともに前記第三の値を上位ビット方向へ1ビットシフトしてそのシフト結果を新たな第三の値とする第三のシフトステップと、前記第三の値に1を加える商補正ステップとを有し、前記第三のシフトステップにおいて最下位ビットへ挿入する値を、前記計数ステップにより処理の開始が示されるときには、前記除数の符号が負ならば前記演算ステップにおける桁上げの反転とする一方正ならば前記演算ステップにおける桁上げとし、前記計数ステップにより処理の開始でないことが示されるときには、前記被除数が正かつ前記除数が負の場合または前記被除数が負かつ前記除数が正でかつ現在または1つ前の処理における前記第一の値の全部のビットおよび前記第二の値の全部のビットがいずれも0の場合または前記被除数が負かつ前記除数が負でかつ現在および1つ前の処理における前記第一の値のいずれかのビットまたは前記第二の値のいずれかのビットが1の場合は前記演算ステップにおける桁上げの反転とし、それ以外の場合は前記演算ステップにおける桁上げとし、前記計数ステップによる計数に基づいて、処理の開始から終了までの間に、前記演算ステップと前記第一のシフトステップと前記第二のシフトステップと前記第三のシフトステップとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返し、得られる第一の値を剰余とし、前記被除数と前記除数とが異符号の時は前記商補正ステップを行い、同符号の時は前記商補正ステップを行わずに得られる第三の値を商とすることを特徴とする除算方法。
【請求項17】 符号付き数の除数を保持する除数保持手段と、第1と第2の2つの入力に対して加算を行いその結果を出力するかもしくは第1の入力から第2の入力の減算を行いその結果を出力するかもしくは第1の入力をそのまま転送して出力する演算手段と、前記演算手段の出力を上位ビット方向に1ビットシフトするかもしくはそのまま転送する第一シフト手段と、除算処理の開始時には、符号付き数の被除数の前記除数保持手段の語長に等しい語長の上位部分を保持し、処理の実行中には、前記第一シフト手段の出力を保持し、処理の終了時には、剰余を保持する第一データ保持手段と、処理の開始時には、前記被除数の残りの下位部分を保持し、処理の実行中には、上位ビット方向にシフトされた前記被除数の下位部分と商の一部とを保持し、処理の終了時には、商を保持する第二データ保持手段と、前記第二データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくはそのまま転送して結果を再び前記第二データ保持手段に格納する第二シフト手段と、内部に計数手段を持ち、前記演算手段に対しては、前記計数手段が処理の開始を示すときには、前記被除数と前記除数とが同符号ならば減算を指示する一方異符号ならば加算を指示し、前記計数手段が処理の開始から終了までの間であることを示すときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば減算を指示し、前記計数手段が処理の終了を示しかつ前記被除数と前記除数とが同符号のときには、前記第二データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば第1入力の転送を指示し、前記計数手段が処理の終了を示しかつ前記被除数と前記除数とが異符号のときには、前記第二データ保持手段の最下位ビットの値が0ならば第1入力の転送を指示する一方1ならば減算を指示して、前記第一シフト手段に対しては、前記計数手段により処理の終了または終了直前の処理でないことが示されるときに、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了またはその直前の処理であることを示すときには、転送を指示し、前記第二シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、前記演算手段における桁上げまたはその反転値を最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示する制御手段と、前記第二データ保持手段に保持された値に1を加える商補正手段とを備え、前記第一データ保持手段に保持された値および前記除数保持手段に保持された値をそれぞれ前記演算手段の第1および第2の入力とし、前記第一シフト手段の最下位ビットに挿入する値を前記第二シフト手段における最上位ビットからのシフトあふれとし、さらに前記制御手段における前記第二シフト手段へ挿入するビットに関する指示を、前記計数手段が処理の開始を示すときは前記除数の符号が負ならば前記演算手段における桁上げの反転とする一方正ならば前記演算手段における桁上げとし、前記計数手段が処理の開始でないことを示すときには、前記被除数が正かつ前記除数が負の場合または前記被除数が負かつ前記除数が正でかつ現在または1つ前の処理における前記第一データ保持手段の全部のビットおよび前記第二データ保持手段のうち既に前記第二シフト手段によって最下位ビットに挿入されている値のすべてを除く部分のビットがいずれも0の場合または前記被除数が負かつ前記除数が負でかつ現在および1つ前の処理における前記第一データ保持手段のいずれかのビットまたは前記第二データ保持手段のうち既に前記第二シフト手段によって最下位ビットに挿入されている値のすべてを除く部分のいずれかのビットが1の場合は前記演算手段における桁上げの反転とし、それ以外の場合は前記演算手段における桁上げとし、前記計数手段による計数に基づいて、処理の開始から終了までの間に、前記演算手段における演算と前記第一シフト手段および前記第二シフト手段におけるシフトとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返し、前記第一データ保持手段に保持されている値を剰余とし、前記被除数と前記除数とが異符号のときには前記商補正手段により前記第二データ保持手段に保持している値に1を加える一方同符号のときには何も行わずに前記第二データ保持手段に保持されている値を商とするように構成されていることを特徴とする除算装置。
【請求項18】 符号付き数の除数を保持する除数保持手段と、第1と第2の2つの入力に対して加算を行いその結果を出力するかもしくは第1の入力から第2の入力の減算を行いその結果を出力するかもしくは第1の入力をそのまま転送して出力する演算手段と、前記演算手段の出力を上位ビット方向に1ビットシフトするかもしくはそのまま転送する第一シフト手段と、除算処理の開始時には、符号付き数の被除数の前記除数保持手段の語長に等しい語長の上位部分を保持し、処理の実行中には、前記第一シフト手段の出力を保持し、処理の終了時には、剰余を保持する第一データ保持手段と、処理の開始時には、前記被除数の残りの下位部分を保持し、処理の実行中には、上位ビット方向にシフトされた前記被除数の下位部分を保持し、処理の終了時には0を保持する第二データ保持手段と、処理の実行中には商の一部を保持して、処理の終了時には商を保持する第三データ保持手段と、0を最下位ビットに挿入して前記第二データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくは前記第二データ保持手段に保持された値をそのまま転送して結果を再び前記第二データ保持手段に格納する第二シフト手段と、前記第三データ保持手段に保持された値を上位ビット方向に1ビットシフトするかもしくはそのまま転送して結果を再び前記第三データ保持手段に格納する第三シフト手段と、内部に計数手段を持ち、前記演算手段に対しては、前記計数手段が処理の開始を示すときには、前記被除数と前記除数とが同符号ならば減算を指示する一方異符号ならば加算を指示し、前記計数手段が処理の開始から周力までの間であることを示すときには、前記第三データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば減算を指示し、前記計数手段が処理の終了を示しかつ前記被除数と前記除数とが同符号のときには、前記第三データ保持手段の最下位ビットの値が0ならば加算を指示する一方1ならば第1入力の転送を指示し、前記計数手段が処理の終了を示しかつ前記被除数と前記除数とが異符号のときには、前記第三データ保持手段の最下位ビットの値が0ならば第1入力の転送を指示する一方1ならば減算を指示して、前記第一シフト手段に対しては、前記計数手段により処理の終了またはその直前の処理でないことが示されるときに、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了またはその直前の処理であることを示すときには、転送を指示し、前記第二シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示す時は転送を指示し、前記第三シフト手段に対しては、前記計数手段が処理の終了でないことを示すときには、前記演算手段における桁上げまたはその反転値を最下位ビットに挿入する上位ビット方向の1ビットシフトを指示し、前記計数手段が処理の終了を示すときには転送を指示する制御手段と、前記第三データ保持手段に保持された値に1を加える商補正手段とを備え、前記第一データ保持手段に保持された値および前記除数保持手段に保持された値をそれぞれ前記演算手段の第1および第2の入力とし、前記第一シフト手段の最下位ビットに挿入する値を前記第二シフト手段における最上位ビットからのシフトあふれとし、さらに前記制御手段における前記第三シフト手段へ挿入するビットに関する指示を、前記計数手段が処理の開始を示すときは前記除数の符号が負ならば前記演算手段における桁上げの反転とする一方正ならば前記演算手段における桁上げとし、前記計数手段が処理の開始でないことを示すときには、前記被除数が正かつ前記除数が負の場合または前記被除数が負かつ前記除数が正でかつ現在または1つ前の処理における前記第一データ保持手段の全部のビットおよび前記第二データ保持手段の全部のビットがいずれも0の場合または前記被除数が負かつ前記除数が負でかつ現在および1つ前の処理における前記第一データ保持手段のいずれかのビットまたは前記第二データ保持手段のいずれかのビットが1の場合は前記演算手段における桁上げの反転とし、それ以外の場合は前記演算手段における桁上げとし、前記除数の符号が負でかつ前記第一データ保持手段のいずれかのビットまたは前記第二データ保持手段のいずれかのビットが1のときには前記演算手段における桁上げの反転とし、それ以外の時は前記演算手段における桁上げとし、前記計数手段による計数に基づいて、処理の開始から終了までの間に、前記演算手段における演算と前記第一シフト手段および前記第二シフト手段および前記第三シフト手段におけるシフトとを前記被除数のビット数と前記除数のビット数との差に等しい回数だけ繰り返し、前記第一データ保持手段に保持されている値を剰余とし、前記被除数と前記除数とが異符号の時は前記商補正手段により前記第三データ保持手段に保持している値に1を加える一方同符号の時は何も行わずに前記第三データ保持手段に保持されている値を商とするように構成されていることを特徴とする除算装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明はディジタル計算機の中央処理装置等に用いられ、符号なし数または符号付き数の2進数の除算を行う除算装置に関するものである。
【0002】
【従来の技術】従来の除算装置における除算アルゴリズムとしては、例えば、Kai Hwang 著、堀越彌監訳「コンピュータの高速演算方式」(昭和55年9月1日、近代科学社)PP.222〜224 、7.5 節(2進非回復型除算)に示されているものがある。この除算アルゴリズムでは、以下のようにして商および剰余を求めるようになっている。
【0003】まず、除算の最初においては、被除数から除数を減算して部分剰余を求め、この部分剰余が正ならば部分商を1とし、負ならば0とするとともに、上記部分剰余を2倍(上位ビット方向に1ビットシフト)する。その後は、前回の演算によって得られた部分剰余が正ならば部分剰余の2倍数から除数を減算し、負ならば部分剰余の2倍数に除数を加算して新たな部分剰余を得、この新たな部分剰余が正ならば部分商を1とし、負ならば0とするとともに、上記新たな部分剰余を2倍する。この処理を被除数のビット数と除数のビット数との差の分だけ繰り返す。
【0004】すなわち、部分剰余の2倍数と除数との大小関係に係らず、部分剰余が正であれば除数の減算を行う一方、負であれば除数の加算を行うとともに、加減算結果が正の場合には部分商を1にし、負の場合には部分商を0にすることにより、アルゴリズムを簡素化して、除算速度の高速化や回路規模の低減を図り得るようになっている。
【0005】ところで、上記部分剰余の正負の判定は、前回の演算によって得られた部分剰余の2倍数と除数との加減算における、符号ビットを除く最上位ビットからのキャリの有無によって行われる。すなわち、上記加減算は、実質的には常に正数と負数との加算になり、最上位ビットからのキャリがあれば符号ビットは必ず0になるので加減算結果は正数と判定できる一方、最上位ビットからのキャリがなければ符号ビットは必ず1になるので加減算結果は負数と判定できる。
【0006】また、上記除算アルゴリズムは、被除数および除数が共に非負の場合にのみ適用可能であるため、符号付き数どうしの除算を行い得る従来の除算装置は、あらかじめ被除数および除数の絶対値を求めて非負の数を得る絶対値生成手段と、非負の被除数と除数との商(商の絶対値)を求める絶対値除算手段と、被除数と除数とが異符号の場合には商の符号を負と決定し、被除数と除数とが同符号の場合には商の符号を正と決定する符号決定手段と、商の絶対値を符号付き数に変換する符号付き数変換手段とを有していた。
【0007】
【発明が解決しようとする課題】しかしながら、上記従来の除算アルゴリズムでは、部分剰余の正負の判定を、前回の演算によって得られた部分剰余の2倍数と除数との加減算における、符号ビットを除く最上位ビットからのキャリの有無によって行うために、上記加減算は除数のビット幅より少なくとも1ビット多いビット幅で行う必要がある。なぜならば、前回の演算によって得られる部分剰余は除数と同じビット幅を有し、この2倍数(上位ビット方向に1ビットシフトした数)における最上位ビットから最下位ビットまでのビット幅は、除数のビット幅よりも1ビット多いビット幅になるからである。なお、厳密には、上記最上位ビットを無視して除数のビット幅で加減算を行った場合でも、最上位ビットの値と符号ビットの値とが同値(共に0または1)の場合には、加減算結果の正負は正しく判定されるが、同値でない(0と1、または1と0)場合に、いわゆるシフトオーバフローによる符号の逆転が生じるので、正しい正負の判定が行えない。
【0008】したがって、従来の除算装置は、加減算回路のビット幅を短くして回路規模を低減することができないという問題点を有していた。また、符号付き数どうしの除算を行い得るようにするためには、絶対値除算手段に加えて、絶対値生成手段と、符号決定手段と、符号付き数変換手段と、およびこれらの手段による処理ステップを必要とするため、やはり回路規模の低減が困難であるうえ、除算速度の高速化も困難であるという問題点を有していた。
【0009】本発明は上記の点に鑑み、回路規模の低減、および除算速度の高速化を図り得る除算装置および除算方法の提供を目的としている。
【0010】
【課題を解決するための手段】上記目的を達成するため、本発明は、符号なし2進数の除算を行う除算装置であって、除数と同じビット幅を有し、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算手段と、加減算結果を1ビット上位ビット側にシフトするシフト手段と、上記演算手段からの桁上げの値、シフト手段からのシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商を求める部分商算出手段とを備えたことを特徴としている。
【0011】また、符号なし2進数の除算を行う除算方法であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて除数と同じビット幅で加減算する演算ステップと、加減算結果を1ビット上位ビット側にシフトするシフトステップと、上記演算ステップの演算による桁上げの値、シフトステップによるシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商を求める部分商算出ステップとを有することを特徴としている。
【0012】また、符号付き2進数の除算を行う除算装置であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算手段と、加減算結果を1ビット上位ビット側にシフトするシフト手段と、上記演算手段からの桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商を求める部分商算出手段とを備えたことを特徴としている。
【0013】また、符号付き2進数の除算を行う除算方法であって、被除数、または部分剰余の2倍数と、除数とを部分商の値に応じて加減算する演算ステップと、加減算結果を1ビット上位ビット側にシフトするシフトステップと、上記演算ステップによる桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商を求める部分商算出ステップとを有することを特徴としている。
【0014】
【作用】上記の構成により、符号なし2進数の除算を行う除算装置または除算方法においては、被除数、または部分剰余の2倍数と、除数との、部分商の値に応じた加減算による桁上げの値、加減算結果の1ビット上位ビット側へのシフトによるシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商が求められる。
【0015】また、符号付き2進数の除算を行う除算装置または除算方法においては、被除数、または部分剰余の2倍数と、除数との、部分商の値に応じた加減算による桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商が求められる。
【0016】
【実施例】
(第1実施例)図1は本発明の第1実施例における符号なし数どうしの除算を行う除算装置のブロック図である。図1において、1は除数を保持する除数レジスタである。
【0017】2はA入力(被除数または部分剰余の上位ビット)とB入力(除数)とが入力され、上記A入力とB入力とを加算してその結果を出力するか、またはA入力からB入力を減算してその結果を出力するか、またはA入力をそのまま転送して出力する演算回路である。上記加減算は、除数レジスタ1と同じビット幅で行われ、その最上位ビットからの桁上げ(ACRY)が出力されるようになっている。
【0018】3は演算回路2の出力(部分剰余)を上位ビット方向に1ビットシフトするか、またはそのまま転送して出力する第一シフタである。この第一シフタ3のシフト時には、後述する第二シフタ5のシフトあふれの値が最下位ビットに挿入される。4は被除数の上位ビット、または第一シフタ3の出力(部分剰余の2倍数の上位ビット)を一旦保持し、その値をレジスタR2を介して演算回路2のA入力として出力する第一レジスタである。
【0019】5は入力された値を上位ビット方向に1ビットシフトするか、またはそのまま転送して出力する第二シフタである。この第二シフタ5のシフト時には、後述する制御回路8から与えられる部分商Q(n) が順次最下位ビットに挿入される。6は被除数の下位ビット、または第二シフタ5の出力(部分剰余の2倍数の下位ビット)を一旦保持し、その値をレジスタR2を介して再び第二シフタ5に入力する第二レジスタである。この第二レジスタ6は、また、商を保持するレジスタも兼ねている。
【0020】7は第一シフタ3からのシフトあふれ(SCRY)を保持し、レジスタR2を介して出力するシフトあふれ保持レジスタである。8は内部に処理ステップ数(n)を計数する図示しないカウンタを持ち、上記処理ステップ数(n)、演算回路2の最上位ビットからの桁上げ(ACRY)、シフトあふれ保持レジスタ7の値(SCRY)、および第二レジスタ6の最下位ビットの値(1つ前の部分商Q(n-1) )に基づいて、演算回路2の演算の種類(OPR)、第一シフタ3のシフト数(SFT1)、および第二シフタ5のシフト数(SFT2)を指示するとともに、第二シフタ5の1ビットシフト時の最下位ビットへの挿入値(部分商Q(n) )を生成する制御回路である。
【0021】より詳しくは、制御回路8は、処理ステップごとに、図2に示すような制御を行う。すなわち、制御回路8は、同図におけるOPRの欄が”A”ならばA入力の転送を、”A+B”ならばA入力とB入力の加算を、”A−B”ならばA入力からB入力の減算を演算回路2に指示する。また、SFT1またはSFT2の欄が”L1”ならば上位ビット方向に1ビットのシフトを、”0”ならば0ビットシフトすなわち転送を、第一シフタ3または第二シフタ5に指示する。さらに、Q(n) の欄が”ACRY”ならば演算回路2の最上位ビットからの桁上げを、”Z”ならば下記(1)式で決まる値を第二シフタ5の最下位ビットに部分商Q(n) として挿入する。ここで、(1)式において、「・」はビット論理積を、「+」はビット論理和を表す。
【0022】
Z=ACRY・(Q(n-1) +SCRY)+Q(n-1) ・SCRY ……(1)
上記Zは、Q(n-1) と、SCRYと、ACRYとのうちの少なくとも何れか2つの値が1である場合に1となり、部分剰余が正であることを示す。すなわち、図2に示すように、n=1〜2の場合において、Q(n-1) =0(前の処理ステップの部分剰余が負)のときには除数(B)の加算が行われる一方、Q(n-1) =1(前の処理ステップの部分剰余が正)のときには除数の減算が行われるので、上記減算を除数の2の補数(−B)の加算と考えると、加数(Bまたは−B)における除数のビット幅より1ビット上位のビットの値は、Q(n-1) =0のときに0、Q(n-1) =1のときに1となる。また、SCRYは、被加数(A)における除数のビット幅より1ビット上位のビットの値であり、ACRYは、除数のビット幅の加算における除数のビット幅より1ビット上位のビットへの桁上げである。
【0023】そこで、演算回路2による加算は除数のビット幅だけで行われるが、除数のビット幅よりも1ビット多いビット幅の加算を行う場合における除数のビット幅より1ビット上位のビットからの桁上がりの有無(部分剰余の正負)は、Q(n-1)、SCRY、ACRYのうちの少なくとも何れか2つの値が1であるかどうか(Z=1であるかどうか)によって判別できる。
【0024】したがって、上記Zの値によって部分剰余の正負が正確に判定でき、このZを部分商Q(n) とすることにより、部分剰余の正負に応じた正しい部分商Q(n) が得られる。上記除数レジスタ1、演算回路2、第一シフタ3、第一レジスタ4、第二シフタ5、第二レジスタ6およびこれら相互間の接続線は、多くの場合はいずれも16ビットや32ビットなど2のべき乗のデータ幅に構成されるが、ここでは説明の簡単のために3ビットのデータ幅を持つとして説明する。なお、原理的にはどのようなデータ幅であってもよい。
【0025】また、第一レジスタ4、第二レジスタ6、およびシフトあふれ保持レジスタ7は、それぞれ入力されたデータをクロック信号φ1に同期して保持し、除数レジスタ1、および各レジスタR2は、それぞれ入力されたデータをクロック信号φ2に同期して保持する。なお、実際には上記の他にも商のオーバフローを検出する手段や除数を正規化する手段等が設けられるが、本発明の主眼ではないので説明を省略する。
【0026】以上のように構成された本実施例の除算装置について、制御回路8の制御に基づく動作を説明する。
(1)処理ステップ開始前(初期化処理)
まず、制御回路8の内部のカウンタの値(n)を0にクリアするとともに、3ビットの符号なし数の除数を除数レジスタ1に格納する。また、被除数が6ビットの符号なし数の場合には、その上位3ビットを第一レジスタ4に、下位3ビットを第二レジスタ6にそれぞれ格納する一方、被除数が3ビットの符号なし数の場合には、第一レジスタ4を0にクリアするとともに、被除数を第二レジスタ6に格納する。
(2)第1処理ステップ(n=0)
まず、第一レジスタ4に保持されている値と除数レジスタ1に保持されている除数とをそれぞれ演算回路2のA入力とB入力とに入力して演算を行う。この時の演算は、図2のOPRの欄に示すように、A入力からB入力の減算となる。
【0027】次に、上記演算の演算結果および第二レジスタ6の値を、それぞれ第一シフタ3または第二シフタ5で上位ビット方向に1ビットシフトし、シフト結果をそれぞれ第一レジスタ4または第二レジスタ6に格納する。その際、シフトあふれ保持レジスタ7には、第一シフタ3の最上位ビットからのシフトあふれ(SCRY)が格納され、第一シフタ3の最下位ビットには、第二シフタ5の最上位ビットからのシフトあふれが挿入され、第二シフタ5の最下位ビットには、図2のQ(n) の欄に示すように、演算回路2の桁上げ(ACRY)が制御回路8から与えられて挿入される。
【0028】また、制御回路8の内部のカウンタの値(n)を1増分する。
(3)第2〜第3処理ステップ(n=1〜2)
まず、第一レジスタ4に保持されている値と除数レジスタ1に保持されている除数とをそれぞれ演算回路2のA入力とB入力とに入力して演算を行う。この時の演算は、図2のOPRの欄に示すように、第二レジスタ6の最下位ビットの値(1つ前の部分商Q(n-1) )が0ならばA入力とB入力の加算、1ならばA入力からB入力の減算となる。
【0029】次に、前記第1処理ステップと同様に、演算結果および第二レジスタ6の値を、それぞれ第一シフタ3または第二シフタ5で上位ビット方向に1ビットシフトし、シフト結果を第一レジスタ4または第二レジスタ6に格納する。その際、やはり第1処理ステップと同様に、シフトあふれ保持レジスタ7には、第一シフタ3の最上位ビットからのシフトあふれ(SCRY)が格納され、第一シフタ3の最下位ビットには、第二シフタ5の最上位ビットからのシフトあふれが挿入されるが、第二シフタ5の最下位ビットには、図2のQ(n) の欄に示すように、演算回路2の桁上げ(ACRY)と第二レジスタ6の最下位ビットの値(Q(n-1) )とシフトあふれ保持レジスタ7の値(SCRY)とから前記(1)式によって求められるZの値が制御回路8から与えられて挿入される。
【0030】また、制御回路8の内部のカウンタの値(n)を1増分し、その値が3になるまで上記処理を繰り返す。
(4)第4処理ステップ(n=3)
まず、第2〜第3処理ステップと同様に、第一レジスタ4に保持されている値と除数レジスタ1に保持されている除数とをそれぞれ演算回路2のA入力とB入力とに入力し、第二レジスタ6の最下位ビットの値(Q(n-1) )に応じて加算または減算を行う。
【0031】次に、演算結果は、そのまま第一シフタ3を経由して第一レジスタ4に格納する一方、第二レジスタ6の値は第二シフタ5で上位ビット方向に1ビットシフトし、シフト結果を第二レジスタ6に格納する。この場合、第二シフタ5の最上位ビットからのシフトあふれは、第一シフタ3の最下位ビットに挿入されることなく捨てられるが、第二シフタ5の最下位ビットには、第2〜第3処理ステップと同様に、演算回路2の桁上げ(ACRY)と第二レジスタ6の最下位ビットの値とシフトあふれ保持レジスタ7の値(SCRY)とから(1)式によって求められるZの値が制御回路8から与えられて挿入される。すなわち、部分商Q(n) は、第2〜第3処理ステップと同様に求められて第二シフタ5に格納されるが、演算回路2から出力される演算結果は最終剰余なので、2倍されることなく第一レジスタ4に格納される。
【0032】また、制御回路8の内部のカウンタの値(n)を1増分する。
(5)第5処理ステップ(n=4)
第一レジスタ4に保持されている値と除数レジスタ1に保持されている除数とをそれぞれ演算回路2のA入力とB入力に入力して演算を行う。この時の演算は、図2のOPRの欄に示すように第二レジスタ6の最下位ビットの値(Q(n-1))が0ならばA入力とB入力の加算、1ならばA入力の転送となる。すなわち、最終剰余が負である場合に、除数を加算して最終剰余を補正する。
【0033】また、演算結果および第二レジスタ6の値を、それぞれ第一シフタ3または第二シフタ5をそのまま経由して、第一レジスタ4または第二レジスタ6に格納する。以上の処理が行われた後、第一レジスタ4に格納されている値が求める剰余で、第二レジスタ6に格納されている値が求める商である。
【0034】上記のような処理によって行われる具体的な計算の過程を筆算の書式で図3に示す。ここで、同図における「X」、「C」は、それぞれ演算回路2の加算における除数のビット幅より1ビット上位のビットへの桁上げ(ACRY)を示し、アンダーラインは、第一シフタ3の最上位ビットからのシフトあふれ(SCRY)を示している。
【0035】なお、上記の例では、第二レジスタ6を被除数または部分剰余の格納と、商の格納とに兼用する例を示したが、商を格納するレジスタを独立して設けてもよい。この場合には、第一シフタ3と第二シフタ5との分割が不要になるとともに、商のビット数を任意に設定することも容易になる。
(第2実施例)図4は本発明の第2実施例における符号付き数どうしの除算を行う除算装置のブロック図である。この除算装置は、商を負方向に丸め、剰余の符号を除数の符号と同じにするようになっている。具体的には、例えば被除数が−10、除数が3の場合には、商は−4、剰余は2となる。なお、本第2実施例において、前記第1実施例と同様の機能を有する構成要素は、対応する番号を付して説明を省略する。
【0036】図4において、15、19は入力された値を上位ビット方向に1ビットシフトするか、またはそのまま転送して出力する第二シフタおよび第三シフタ、16は被除数の下位ビット、または第二シフタ15の出力(部分剰余の2倍数の下位ビット)を一旦保持し、その値を再び第二シフタ15に入力する第二レジスタ、20は商を保持するレジスタである。すなわち、第1実施例と異なり、被除数等をシフトまたは保持する手段と、商をシフトまたは保持する手段とが独立して設けられている。なお、第二シフタ15のシフト時には、値”0”が最下位ビットに挿入され、第三シフタ19のシフト時には、後述する制御回路18から与えられる部分商Q(n) が順次最下位ビットに挿入される。
【0037】21は被除数の符号(S1)、すなわち被除数の最上位ビットの値を保持する被除数符号レジスタである。22は第一レジスタ14の全てのビットに保持されている値が0であるときに、値(Z1)として1を出力する第一零検出回路である。23は第二レジスタ16の全てのビットに保持されている値が0であるときに、値(Z2)として1を出力する第二零検出回路である。
【0038】24は第一零検出回路22の検出結果を保持する第一零検出保持レジスタである。25は第二零検出回路23の検出結果を保持する第二零検出保持レジスタである。18は内部に処理ステップ数(n)を計数する図示しないカウンタを持ち、上記処理ステップ数(n)、被除数符号レジスタ21の値(S1)、除数の符号である除数レジスタ11の最上位ビットの値(S2)、演算回路12の最上位ビットからの桁上げ(ACRY)、第三レジスタ20の最下位ビットの値(1つ前の部分商Q(n-1) )、および第一零検出回路22と、第二零検出回路23と、第一零検出保持レジスタ24と、第二零検出保持レジスタ25との検出結果または保持内容(Z1、Z2、PZ1、PZ2)に基づいて、演算回路12の演算の種類(OPR)、第一シフタ13のシフト数(SFT1)、第二シフタ15のシフト数(SFT2)、および第三シフタ19のシフト数(SFT3)を指示するとともに、第三シフタ19の1ビットシフト時の最下位ビットへの挿入値(部分商Q(n) )を生成する制御回路である。
【0039】図5は、第1実施例の図2と同様に、制御回路18の処理ステップごとの具体的な制御内容を示す説明図である。同図のQ(n) の欄における”ACRY”および上線付きの”ACRY”は、演算回路12の最上位ビットからの桁上げ、またはそのビット反転値を第三シフタ19の最下位ビットに部分商Q(n-1) として挿入することを示す。
【0040】また、除数レジスタ11、演算回路12、第一シフタ13、第一レジスタ14、第二シフタ15、第二レジスタ16、第三シフタ19、第三レジスタ20、第一零検出回路22、第二零検出回路23、およびこれら相互間の接続線はいずれも3ビットのデータ幅を持つ。以上のように構成された本実施例の除算装置について、制御回路18の制御に基づく動作を説明する。
(1)処理ステップ開始前(初期化処理)
まず、制御回路18の内部のカウンタの値(n)、第一零検出保持レジスタ24、および第二零検出保持レジスタ25の値(PZ1、PZ2)を0にクリアするとともに、3ビットの符号付き数の除数を除数レジスタ11に格納する。また、被除数が6ビットの符号付き数の場合には、その上位3ビットを第一レジスタ14に、下位3ビットを第二レジスタ16にそれぞれ格納する一方、被除数が3ビットの符号付き数の場合には、第一レジスタ14の全ビットに被除数の符号ビットの値をコピーするとともに、被除数を第二レジスタ16に格納する。
(2)第1処理ステップ(n=0)
まず、第一レジスタ14に保持されている値と除数レジスタ11に保持されている除数とをそれぞれ演算回路12のA入力とB入力とに入力して演算を行う。この時の演算は、図5のOPRの欄に示すように、被除数符号レジスタ21の値(S1)と除数レジスタ11の最上位ビットの値(S2)とが同じ値ならば、A入力からB入力の減算、異なる値ならばA入力とB入力の加算となる。
【0041】次に、上記演算の演算結果、第二レジスタ16の値、および第三レジスタ20の値を、それぞれ第一シフタ13、第二シフタ15、または第三シフタ19で上位ビット方向に1ビットシフトし、シフト結果をそれぞれ第一レジスタ14、第二レジスタ16、または第三レジスタ20に格納する。その際、第一シフタ13の最下位ビットには、第二シフタ15の最上位ビットからのシフトあふれが挿入され、第二シフタ15の最下位ビットには、値”0”が挿入され、第三シフタ19の最下位ビットには、図5のQ(n) の欄に示すように、演算回路12の桁上げ(ACRY)、またはそのビット反転値が制御回路18から与えられて挿入される。
【0042】より詳しくは、除数レジスタ11の最上位ビットの値(S2)が1で、かつ第一零検出回路22および第二零検出回路23の検出結果(Z1、Z2)の少なくとも一方が0で、さらに第一零検出保持レジスタ24および第二零検出保持レジスタ25の保持内容(PZ1、PZ2)の少なくとも一方が0である場合には、演算回路12の桁上げ(ACRY)のビット反転値が挿入され、その他の場合には、演算回路12の桁上げ(ACRY)がそのまま挿入される。
【0043】また、制御回路18の内部のカウンタの値(n)を1増分する。
(3)第2〜第3処理ステップ(n=1〜2)
まず、第一レジスタ14に保持されている値と除数レジスタ1に保持されている除数とをそれぞれ演算回路12のA入力とB入力とに入力して演算を行う。この時の演算は、図5のOPRの欄に示すように、第三レジスタ20の最下位ビットの値(1つ前の部分商Q(n-1) )が0ならばA入力とB入力の加算、1ならばA入力からB入力の減算となる。
【0044】次に、前記第1処理ステップと同様に、演算結果、第二レジスタ16および第三レジスタ20の値を、それぞれ第一シフタ13、第二シフタ15、または第三シフタ19で上位ビット方向に1ビットシフトし、シフト結果を第一レジスタ14、第二レジスタ16、または第三レジスタ20に格納する。その際、やはり第1処理ステップと同様に、第一シフタ13の最下位ビットには、第二シフタ15の最上位ビットからのシフトあふれが挿入され、第二シフタ15の最下位ビットには、値”0”が挿入され、第三シフタ19の最下位ビットには、図5のQ(n) の欄に示すように、演算回路12の桁上げ(ACRY)、またはそのビット反転値が制御回路18から与えられて挿入される。
【0045】また、制御回路18の内部のカウンタの値(n)を1増分し、その値が3になるまで上記処理を繰り返す。
(4)第4処理ステップ(n=3)
まず、第2〜第3処理ステップと同様に、第一レジスタ14に保持されている値と除数レジスタ11に保持されている除数とをそれぞれ演算回路12のA入力とB入力とに入力し、第三レジスタ20の最下位ビットの値(Q(n-1) )に応じて加算または減算を行う。
【0046】次に、演算結果は、そのまま第一シフタ13を経由して第一レジスタ14に格納する一方、第二レジスタ16および第三レジスタ20の値は第二シフタ15または第三シフタ19で上位ビット方向に1ビットシフトし、シフト結果を第二レジスタ16または第三レジスタ20に格納する。この場合、第二シフタ15の最上位ビットからのシフトあふれは、第一シフタ13の最下位ビットに挿入されることなく捨てられるが、第二シフタ15の最下位ビットには、第2〜第3処理ステップと同様に値”0”が挿入され、第三シフタ19の最下位ビットには、やはり第2〜第3処理ステップと同様に、除数レジスタ11の最上位ビットの値(S2)、および第一零検出回路22と、第二零検出回路23と、第一零検出保持レジスタ24と、第二零検出保持レジスタ25との検出結果または保持内容(Z1、Z2、PZ1、PZ2)に応じて、演算回路12の桁上げ(ACRY)、またはそのビット反転値が制御回路18から与えられて挿入される。すなわち、部分商Q(n) は、第2〜第3処理ステップと同様に求められて第二シフタ15に格納されるが、演算回路12から出力される演算結果は最終剰余なので、2倍されることなく第一レジスタ14に格納される。
【0047】また、制御回路18の内部のカウンタの値(n)を1増分する。
(5)第5処理ステップ(n=4)
第一レジスタ14に保持されている値と除数レジスタ11に保持されている除数とをそれぞれ演算回路12のA入力とB入力に入力して演算を行う。この時の演算は、図5のOPRの欄に示すように第三レジスタ20の最下位ビットの値(Q(n-1) )が0ならばA入力とB入力の加算、1ならばA入力の転送となる。すなわち、最終剰余が負である場合に、除数を加算して最終剰余を補正する。
【0048】また、演算結果、第二レジスタ16、および第三レジスタ20の値を、それぞれ第一シフタ13または第二シフタ15、または第三シフタ19をそのまま経由して、第一レジスタ14、第二レジスタ16、または第三レジスタ20に格納する。以上の処理が行われた後、第一レジスタ14に格納されている値が求める剰余で、第三レジスタ20に格納されている値が求める商である。
【0049】上記のような処理によって行われる具体的な計算の過程を筆算の書式で図6に示す。ここで、第1実施例と同様に、同図における「X」、「C」は、それぞれ演算回路2の加算における除数のビット幅より1ビット上位のビットへの桁上げ(ACRY)を示し、アンダーラインは、第一シフタ3の最上位ビットからのシフトあふれ(SCRY)を示している。
【0050】なお、本第2実施例においては、第三シフタ19と第三レジスタ20とを設け、制御回路18の生成する部分商Q(n) を第三シフタ19の最下位ビットに挿入して第三レジスタ20に蓄積しているが、第三シフタ19と第三レジスタ20とを設けずに制御回路18の生成する部分商Q(n) を第二シフタ15の最下位ビットに挿入して第二レジスタ16に蓄積するようにするとともに、第二零検出回路23が、第二レジスタ16に入力される値のうち、第二シフタ15によって挿入され蓄積された部分商を除く部分の全てのビットが0であるときに値(Z2)として1を出力するようにすればよい。この場合、商は、第5処理ステップが終了した時に第二レジスタ16に格納される。
(第3実施例)上記第2実施例の変形例として、商を0方向に丸め、剰余の符号は被除数の符号と同じになる除算装置を説明する。すなわち、例えば、被除数が−10、除数が3の場合、商は−3、剰余は−1となる。
【0051】この除算装置は、制御回路18の制御内容が、第2実施例の除算装置と異なる。すなわち、図7に示すように、第1処理ステップ(n=0)においては、第三シフタ19の最下位ビットに挿入する値(Q(n-1) )として、第一零検出回路22の出力(Z1)および第二零検出回路23の出力(Z2)の値に係らず、除数レジスタ11の最上位ビット(S2)が1ならば演算回路2の桁上げの反転値が、0ならば演算回路2の桁上げが制御回路18から与えられる。
【0052】また、第2〜第3処理ステップ(n=1〜2)、および第4処理ステップ(n=3)においては、第三シフタ19の最下位ビットに挿入する値(Q(n-1) )として、被除数符号レジスタ21の値(S1)が0でかつ除数レジスタ11の最上位ビット(S2)が1の場合、被除数符号レジスタ21の値(S1)が1でかつ除数レジスタ11の最上位ビットが0でさらにZ1・Z2+PZ1・PZ2が1の場合、および被除数符号レジスタ21の値(S1)が1でかつ除数レジスタ11の最上位ビットが1でさらにZ1・Z2+PZ1・PZ2が0の場合は、演算回路12の桁上げの反転値が、制御回路18から与えられる一方、それ以外の場合は、演算回路12の桁上げが制御回路18から与えられる。
【0053】また、第5処理ステップ(n=4)では、第一レジスタ14に保持されている値と除数レジスタ11に保持されている除数との演算回路12による演算として、被除数符号レジスタ21の値(S1)と除数レジスタ11の最上位ビット(S2)とが同じ値の場合には、さらに第三レジスタ20の最下位ビット(Q(n-1))が0ならばA入力とB入力の加算、1ならばA入力の転送となる一方、異なる値の場合には、さらに第三レジスタ20の最下位ビットが0ならばA入力の転送、1ならばA入力からB入力の減算となる。
【0054】また、求める商は、被除数と除数が同符号の場合には、第三レジスタ20に格納されている値であるが、異符合の場合には、第三レジスタ20に格納されている値に1が加算され、結果を再び第三レジスタ20に格納された値が求める商である。すなわち、符号なし数の除算を行う場合と同じかもしくは1だけ多い処理ステップ数で、しかも大幅なハードウェアの増大を伴うことなく符号付き数の商および剰余を求めることができる。なお、上記1の加算は、第三シフタ19にシフトおよび転送の機能に加えて1だけ加算(インクリメント)する機能を持たせて行うようにしてもよいし、演算回路12を用いるようにしてもよいし、また、図示しない別の加算器を用いて行うようにしてもよい。
【0055】上記のような処理によって行われる具体的な計算の過程を筆算の書式で図8に示す。なお、上記第2実施例および第3実施例では、商が2の補数表現数として得られるように構成した例を示したが、冗長2進表現数として得られるように構成してもよい。
【0056】また、各実施例ではハードウェアにより除算装置を構成する例を示したが、これに限らず、例えば上記各ブロックに対応する基本的な回路と、これらの回路の動作を制御する基本的な命令列により構成することなどもできる。
【0057】
【発明の効果】以上説明したように、本発明によれば、符号なし2進数の除算を行う除算装置または除算方法においては、被除数、または部分剰余の2倍数と、除数との、部分商の値に応じた加減算による桁上げの値、加減算結果の1ビット上位ビット側へのシフトによるシフトあふれの値、および直前の部分商の値に基づいて、新たな部分商が求められるので、除数と同じビット幅の加減算によって正確な商を得ることができ、したがって、回路規模の低減や除算速度の高速化を図ることができるという効果を奏する。
【0058】また、符号付き2進数の除算を行う除算装置または除算方法においては、被除数、または部分剰余の2倍数と、除数との、部分商の値に応じた加減算による桁上げの値、除数と被除数との符号、直前の部分商の値、および最新の加減算結果または直前の加減算結果のうちの少なくとも何れか一方が0であるかどうかに基づいて、新たな部分商が求められるので、被除数および除数の絶対値を求めたり商の絶対値を符号付き数に変換したりすることなく、符号付きの商を得ることができ、やはり、回路規模の低減や除算速度の高速化を図ることができるという効果を奏する。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013