(57)【要約】【課題】回路規模の小さい除算回路を提供する。【解決手段】本発明の除算回路は、被除数データが格納されたレジスタと、前記レジスタは、偶数のビット幅を有し、前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタのビット幅を、上位側のビット幅と下位側のビット幅が同一となるように分割した場合の上位ビットのデータを算出するシフト除算部とを備える。【選択図】図６
2012141952.tif 000002
【特許請求の範囲】
【請求項１】
被除数データが格納されたレジスタと、前記レジスタは、偶数のビットを有し、
前記被除数データを、前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタの上位ビットのデータを取得するシフト演算部を備え、ここで、前記上位ビットのデータは、前記レジスタのビット列を上位側のビット数と下位側のビット数が同一となるように分割した場合の上位側のビットのデータである
除算回路。
【請求項２】
請求項１に記載の除算回路であって、
前記上位ビットのデータ＋１を前記商として算出する第２シフト演算部と、
前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとり、前記和に基づいて誤差データを決定する誤差決定部とを更に備え、ここで、前記誤差決定部は、前記和が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定し、前記和が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定し、
前記誤差データが０の場合には、前記シフト演算部が算出した前記商を選択し、前期誤差データが１の場合には、前記第２シフト演算部が算出した前記商を選択するセレクタ
を更に備える除算回路。
【請求項３】
請求項２に記載の除算回路であって、
前記上位ビットのデータ＋２を前記商として算出する第３シフト演算部を更に備え、
前記誤差決定部は、更に、前記和が、前記除数データの２倍のデータであれば、前記誤差データを２に決定し、
前記セレクタは、更に、前記誤差データが２の場合には、前記第３シフト演算部が算出した前記商を選択する
除算回路。
【請求項４】
請求項１に記載の除算回路であって、
前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとり、前記和に基づいて誤差データを決定する誤差決定部とを更に備え、ここで、前記誤差決定部は、前記和が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定し、前記和が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定し、前記和が、前記除数データの２倍のデータであれば、前記誤差データを２に決定し、
前記シフト演算部は、前記レジスタの前記上位ビットのデータに前記誤差決定部が決定した前記誤差データを加算する
除算回路。
【請求項５】
被除数データが格納された、ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）に符号ビットを有するレジスタと、前記レジスタは、前記ＭＳＢを除いて偶数のビットを有し、
前記被除数データを、前記ＭＳＢを除いた前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタから、前記ＭＳＢと上位ビットで構成されるビット列を取得するシフト演算部を備え、ここで、前記上位ビットは、前記レジスタの前記符号ビットを除いたビット列を、上位ビットのビット幅と下位ビットのビット幅が同一となるように分割した場合の上位側のビットであり、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋１を前記商として算出する第２シフト演算部と、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋２を前記商として算出する第３シフト演算部と、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）−１を前記商として算出する第４シフト演算部と、
（前記上位ビットのデータ＋前記下位ビットのデータ）−（前記ＭＳＢのデータ）×２で誤差判定条件値を算出し、前記誤差判定条件値に基づいて誤差データを決定する誤差決定部と、ここで、前記誤差決定部は、前記誤差判定条件値が、負数であれば、前記誤差データを−１に決定し、前記誤差判定条件値が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定し、前記誤差判定条件値が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定し、前期誤差判定条件値が、前記除数データの２倍のデータであれば、前記誤差データを２に決定し、
前記誤差データが０の場合には、前記シフト演算部が算出した前記商を選択し、前期誤差データが１の場合には、前記第２シフト演算部が算出した前記商を選択し、前期誤差データが２の場合には、前記第３シフト演算部が算出した前記商を選択し、前期誤差データが−１の場合には、前記第４シフト演算部が算出した前記商を選択するセレクタ
を備える除算回路。
【請求項６】
請求項１に記載の除算回路であって、
前記上位ビットのデータ＋１を前記商として算出する第２シフト演算部と、
前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとる誤差決定部とを更に備え、
前記和が０以上、かつ前記除数データ未満の場合には、前記シフト演算部が算出した前記商を選択し、前期和が前記除数データ以上、かつ前記除数データの２倍のデータ未満の場合には、前記第２シフト演算部が算出した前記商を選択するセレクタ
を更に備える除算回路。
【請求項７】
請求項６に記載の除算回路であって、
前記上位ビットのデータ＋２を前記商として算出する第３シフト演算部を更に備え、
前記セレクタは、更に、前記和が、前記除数データの２倍のデータであれば、前記第３シフト演算部が算出した前記商を選択する
除算回路。
【請求項８】
被除数データが格納された、ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）に符号ビットを有するレジスタと、前記レジスタは、前記ＭＳＢを除いて偶数のビットを有し、
前記被除数データを、前記ＭＳＢを除いた前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタから、前記ＭＳＢと上位ビットで構成されるビット列を取得するシフト演算部を備え、ここで、前記上位ビットは、前記レジスタの前記符号ビットを除いたビット列を、上位ビットのビット幅と下位ビットのビット幅が同一となるように分割した場合の上位側のビットであり、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋１を前記商として算出する第２シフト演算部と、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋２を前記商として算出する第３シフト演算部と、
（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）−１を前記商として算出する第４シフト演算部と、
（前記上位ビットのデータ＋前記下位ビットのデータ）−（前記ＭＳＢのデータ）×２で誤差判定条件値を算出する誤差判定条件値演算部と、
前記誤差判定条件値が、負数であれば、前記第４シフト演算部が算出した前記商を選択し、前記誤差判定条件値が、０以上、かつ前記除数データ未満であれば、前記シフト演算部が算出した前記商を選択し、前記誤差判定条件値が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記第２シフト演算部が算出した前記商を選択し、
前期誤差判定条件値が、前記除数データの２倍のデータであれば、前記第３シフト演算部が算出した前記商を選択するセレクタ
を備える除算回路。
【請求項９】
偶数のビットを有するレジスタに被除数が格納される除算回路において、
シフト演算部が、前記被除数データを、前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタの上位ビットのデータを取得するステップを含み、ここで、前記上位ビットのデータは、前記レジスタのビット列を上位側のビット数と下位側のビット数が同一となるように分割した場合の上位側のビットのデータである
除算方法。
【請求項１０】
請求項９に記載の除算方法であって、
前記第２シフト演算部が、前記上位ビットのデータ＋１を前記商として算出するステッ
プと、
誤差決定部が、前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとるステップと、
前記誤差決定部が、前記和が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定するステップと、
前記誤差決定部が、前記和が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定するステップと、
セレクタが、前記誤差データが０の場合には、前記シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期誤差データが１の場合には、前記第２シフト演算部が算出した前記商を選択するステップと
を更に含む除算方法。
【請求項１１】
請求項１０に記載の除算方法であって、
第３シフト演算部が、前記上位ビットのデータ＋２を前記商として算出するステップと
、
前記誤差決定部が、前記和が、前記除数データの２倍のデータであれば、前記誤差データを２に決定するステップと、
前記セレクタが、前記誤差データが２の場合には、前記第３シフト演算部が算出した前記商を選択するステップと
を更に含む除算方法。
【請求項１２】
請求項９に記載の除算方法であって、
誤差決定部が、前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとるステップと、
前記誤差決定部が、前記和が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定するステップと、
前記誤差決定部が、前記和が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定するステップと、
前記誤差決定部が、前記和が、前記除数データの２倍のデータであれば、前記誤差データを２に決定するステップと、
シフト演算部が、前記レジスタの前記上位ビットのデータに前記誤差決定部が決定した前記誤差データを加算するステップと
を更に含む除算方法。
【請求項１３】
ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）に符号ビットを有し、前記ＭＳＢを除いて偶数のビットを有するレジスタに被除数データが格納される除算回路において、
シフト演算部が、前記被除数データを、前記ＭＳＢを除いた前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタから、前記ＭＳＢと上位ビットで構成されるビット列を取得するステップと、ここで、前記上位ビットは、前記レジスタの前記符号ビットを除いたビット列を、上位ビットのビット幅と下位ビットのビット幅が同一となるように分割した場合の上位側のビットであり、
第２シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋１を前記商として算出するステップと、
第３シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋２を前記商として算出するステップと、
第４シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）−１を前記商として算出するステップと、
誤差決定部が、（前記上位ビットのデータ＋前記下位ビットのデータ）−（前記ＭＳＢのデータ）×２で誤差判定条件値を算出するステップと、
前記誤差決定部が、前記誤差判定条件値に基づいて誤差データを決定するステップと、ここで、前記誤差決定部は、前記誤差判定条件値が、負数であれば、前記誤差データを−１に決定し、前記誤差判定条件値が、０以上、かつ前記除数データ未満であれば、前記誤差データを０に決定し、前記誤差判定条件値が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記誤差データを１に決定し、前期誤差判定条件値が、前記除数データの２倍のデータであれば、前記誤差データを２に決定し、
セレクタが、前記誤差データが０の場合には、前記シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期誤差データが１の場合には、前記第２シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期誤差データが２の場合には、前記第３シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期誤差データが−１の場合には、前記第４シフト演算部が算出した前記商を選択するステップと
を含む除算方法。
【請求項１４】
請求項９に記載の除算方法であって、
第２シフト部が、前記上位ビットのデータ＋１を前記商として算出するステップと、
誤差決定部が、前記レジスタの前記上位ビットのデータと、前記レジスタの下位ビットのデータの和をとるステップと、
セレクタが、前記和が０以上、かつ前記除数データ未満の場合には、前記シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期和が前記除数データ以上、かつ前記除数データの２倍のデータ未満の場合には、前記第２シフト演算部が算出した前記商を選択するステップと
を更に含む除算方法。
【請求項１５】
請求項１４に記載の除算方法であって、
第３シフト演算部が、前記上位ビットのデータ＋２を前記商として算出するステップと、
前記セレクタが、前記和が、前記除数データの２倍のデータであれば、前記第３シフト演算部が算出した前記商を選択するステップと
を更に含む除算方法。
【請求項１６】
ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）に符号ビットを有し、前記ＭＳＢを除いて偶数のビットを有するレジスタに被除数データが格納される除算回路において、
シフト演算部が、前記被除数データを、前記ＭＳＢを除いた前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタから、前記ＭＳＢと上位ビットで構成されるビット列を取得するステップと、ここで、前記上位ビットは、前記レジスタの前記符号ビットを除いたビット列を、上位ビットのビット幅と下位ビットのビット幅が同一となるように分割した場合の上位側のビットであり、
第２シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋１を前記商として算出するステップと、
第３シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）＋２を前記商として算出するステップと、
第４シフト演算部が、（前記ＭＳＢと上位ビットで構成されるビット列で表現されるデータ）−１を前記商として算出するステップと、
誤差判定条件値演算部が、（前記上位ビットのデータ＋前記下位ビットのデータ）−（前記ＭＳＢのデータ）×２で誤差判定条件値を算出するステップと、
セレクタが、前記誤差判定条件値が、負数であれば、前記第４シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前記誤差判定条件値が、０以上、かつ前記除数データ未満であれば、前記シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前記誤差判定条件値が、前記除数データ以上、かつ前記除数データの２倍のデータ未満であれば、前記第２シフト演算部が算出した前記商を選択するステップと、
前記セレクタが、前期誤差判定条件値が、前記除数データの２倍のデータであれば、前記第３シフト演算部が算出した前記商を選択するステップと
を含む除算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、除算回路に関する。
【背景技術】
【０００２】
ハードウェアを用いて除算を実現する除算器は、半導体集積回路を構成する基本部品として用いられている。近年、半導体集積回路のチップサイズは、半導体集積回路の機能増大等により増加しているが、一方では、半導体集積回路の製造コストの削減を図るため、半導体集積回路のチップサイズの縮小が要求されている。
【０００３】
大規模ＳＯＣ（Ｓｙｓｔｅｍ  Ｏｎ  ａ  Ｃｈｉｐ）開発等において、被除数、除数を表現するレジスタのビット幅を増加させても、回路規模を抑えることができる除算器の必要性が高まってきている。
【０００４】
特開平０７−１６０４７９号公報（特許文献１）には、消費電力の低減を図った回復型除算器に係る技術が開示されている。
【０００５】
はじめに、一般的な回復型除算器について説明する。
【０００６】
図１は、回復型除算器の全体構成を示すブロック図である。図１の回復型除算器は、１６ビットのレジスタＸ、１６ビットのレジスタＱ及び部分除算器Ｄ０〜Ｄ１５を備える。また、図１には図示されていないが、除数データを格納する１６ビットのレジスタＹを備える。レジスタＸは、被除数データを格納するレジスタである。レジスタＸに格納された被除数データを、レジスタＹに格納された除数で除算した商データは、部分除算器Ｄ１５から、部分除算器Ｄ０を順次動作させることにより求めることができる。部分除算器Ｄ１５〜Ｄ０による演算結果は、最終的に、レジスタＱのＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）側から、ＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）側に向かって、商データとして格納される。剰余データについては、最後に動作する部分演算器Ｄ０の出力Ｒ０によって求めることができる。
【０００７】
図２は、図１の部分除算器Ｄ１５に使用される部分除算器のブロック図である。部分除算器Ｄ１５は、減算器Ｊ１５及び部分剰余選択回路Ｓ１５を備える。減算器Ｊ１５は、レジスタＸのＭＳＢであるＸ１５から、レジスタＹに格納されている除数データを減算し、減算結果データＡ１５を、部分剰余選択回路Ｓ１５へ出力する。また、減算器Ｊ１５は、レジスタＱのＭＳＢであるＱ１５及び部分剰余選択回路Ｓ１５の入力ＳへデータＢ１５を出力する。データＢ１５は、減算結果データＡ１５が負数であれば０となり、減算結果データＡ１５が０以上であれば１となる。部分剰余選択回路Ｓ１５は、入力Ｓに従って、入力０又は入力１のいずれか一方を、出力Ｓとして出力するセレクタ（マルチプレクサ）である。部分剰余選択回路Ｓ１５は、入力Ｓの値が１であれば、入力１の減算結果データＡ１５を部分剰余データＲ１５として出力し、入力Ｓの値が０であれば、入力０のレジスタＸのＭＳＢであるＸ１５を部分剰余データＲ１５として出力する。
【０００８】
図３は、図１の部分除算器Ｄ１４〜Ｄ０に使用される部分除算器のブロック図である。部分除算器Ｄｎは、レジスタＴｎ、減算器Ｊｎ及び部分剰余選択回路Ｓｎを備える。レジスタＴｎは、Ｒ（ｎ＋１）のＬＳＢ側にＸｎを付加したＷｎを合成する。例えば、Ｒ（ｎ＋１）が、０１０１１０であり、Ｘｎが１であれば、Ｗｎ＝０１０１１０１となる。部分除算器Ｄ１４〜Ｄ０は、Ｗｎを格納するレジスタＴｎを更に備えることと、減算器ＪｎがＸ１５ではなく、Ｗｎを使用して、差Ｗｎ−Ｙをとる点が、図２の部分除算器Ｄ１５とは異なる。
【０００９】
減算器Ｊｎは、レジスタＴｎのＷｎから、レジスタＹに格納されている除数データを減算し、減算結果データＡｎを、部分剰余選択回路Ｓｎへ出力する。また、減算器Ｊｎは、レジスタＱのＱｎ及び部分剰余選択回路Ｓｎの入力ＳへデータＢｎを出力する。データＢｎは、減算結果データＡｎが負数であれば０となり、減算結果データＡｎが０以上であれば１となる。部分剰余選択回路Ｓｎは、入力Ｓに従って、入力０又は入力１のいずれか一方を、出力Ｓとして出力するセレクタ（マルチプレクサ）である。部分剰余選択回路Ｓｎは、入力Ｓの値が１であれば、入力１の減算結果データＡｎを部分剰余データＲｎとして出力し、入力Ｓの値が０であれば、入力０のＷｎを部分剰余データＲｎとして出力する。
【００１０】
上記のような構成をとることにより、レジスタＸに格納されている被除数をレジスタＹに格納されている除数で除算した商が、レジスタＱに格納される。また、レジスタＸに格納されている被除数をレジスタＹに格納されている除数で除算した剰余が、部分除算器Ｄ０の部分剰余選択回路Ｓｎの出力ＵによってＲ０として出力される。
【００１１】
以上が、一般的な回復型除算器についての説明である。
【００１２】
特開平０７−１６０４７９号公報（特許文献１）には、上記で説明した回復型除算器に対して、消費電力の低減を図る技術が開示されている。この技術では、上記で説明した部分除算器Ｄ１５〜Ｄ０に対して、消費電力の低減を図るための改良が加えられている。図４は、引用文献１の部分除算器Ｄ１５に使用される部分除算器のブロック図である。図５は、引用文献１の部分除算器Ｄ１４〜Ｄ０に使用される部分除算器のブロック図である。図４及び図５において、演算結果予測回路Ｆｎを備える点が、一般的な回復型除算器とは異なる。演算結果予測回路Ｆｎが、減算器Ｊｎの演算を行わずに、上記で説明したデータＢｎを予測できる場合には、減算器Ｊｎの演算終了を待たずに、選択制御信号Ｅｎを決定し、部分剰余選択回路Ｓｎの入力Ｓへ出力している。これにより、部分剰余選択回路Ｓｎが、より早くＲｎを選択することで、より早い段階で前記部分剰余選択回路Ｓｎの論理状態を固定し、論理状態変化に伴った消費電力を削減している。
【００１３】
ここで、被除数データを格納するレジスタのビット幅が１６ビットであるときの、引用文献１の除算器の回路規模を概算する。まず、１６ビットのレジスタＸは、１ビットのレジスタを８素子とすれば、１２８素子である。同様に、レジスタＱは、１２８素子である。部分除算器Ｄｎについては、Ｔｎレジスタの大きさが最小となる場合の部分除算器Ｄ１４で、回路規模を見積もると、以下のようになる。部分除算器Ｄ１４は、レジスタＴｎ、減算器Ｊｎ、演算結果予測回路Ｆｎ及びセレクタＳｎを含んでいるため、部分除算器Ｄ１４の回路規模は約７２素子であると考えられる。この７２素子の内訳は、２ビットのレジスタＴｎの１６素子、減算器Ｊｎ（ＮＯＴ回路と全加算器）の３８素子、予想回路Ｆｎ（ＮＯＴ回路３つ、２入力ＮＡＮＤ回路１つ、２入力ＮＯＲ回路）の１４素子、セレクタＳｎ（２ｔｏ１セレクタ）の４素子である。したがって、引用文献１の除算器の回路規模は、レジスタＸ＋レジスタＱ＋部分除算器Ｄｎ×１６＝１２８＋１２８＋１１５２＝１４０８（素子）である。
【００１４】
上記の回復型除算器は、被除数データを格納するレジスタのビット幅を増加させると、ビット幅増加割合の２乗倍で回路規模が増加する。その理由は、図１の回復型除算器の全体構成において、部分除算器はビット幅の増加に伴い個数が増加するが、部分除算器自体もビット幅増加に伴い回路規模が増加するためである。
【００１５】
すなわち、上記のｎビット回復型除算器の回路規模をＳ１とすると、次式が成り立つ。
（数１）
Ｓ１＝（ｎビット除算器の部分除算器の回路規模）×ｎ
【００１６】
被除数データを格納するレジスタのビット幅がｎビットから、ｍビットに増加した場合の回復型除算器の回路規模をＳ２とすると、次式が成り立つ。
（数２）
Ｓ２＝（ｍビット除算器の部分除算器の回路規模）×ｍ
＝（（ｎビット除算器の部分除算器の回路規模）×（ｍ／ｎ））×（ｎ×（ｍ／ｎ））
＝Ｓ１×（ｍ／ｎ）２
【００１７】
例えば、ｎ＝１６（ビット）、ｍ＝３２（ビット）とした場合の回路規模の増加率については、Ｓ２＝１１５２×（３２／１６）２＝４６０８（素子）となる。このように、従来の回復型除算器の回路規模は、被除数データを格納するレジスタのビット幅増加に伴って大幅に増加する。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開平０７−１６０４７９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、除数値が、被除数を格納するレジスタのビット幅の半分で表現可能な最大の数である除算器の回路規模を削減することにある。
【課題を解決するための手段】
【００２０】
本発明の除算回路は、偶数のビットを有する被除数データが格納されたレジスタと、前記被除数データを、前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタのビット列を上位側のビット数と下位側のビット数が同一となるように分割した場合の上位ビットのデータを取得するシフト演算部を備える。
【００２１】
本発明の除算方法は、偶数のビットを有するレジスタに被除数が格納される除算回路において実施される。シフト演算部が、前記被除数データを、前記レジスタの半分のビット数で表現できる最大数の除数データで除算した商として、前記レジスタのビット列を上位側のビット数と下位側のビット数が同一となるように分割した場合の上位ビットのデータを取得するステップを含む。
【発明の効果】
【００２２】
本発明によれば、除数値が、被除数を格納するレジスタのビット幅の半分で表現可能な最大の数である除算器の回路規模を削減することができる。
【図面の簡単な説明】
【００２３】
【図１】図１は、回復型除算器の全体構成を示すブロック図である。
【図２】図２は、図１の部分除算器Ｄ１５に使用される部分除算器のブロック図である。
【図３】図３は、図１の部分除算器Ｄ１４〜Ｄ０に使用される部分除算器のブロック図である。
【図４】図４は、引用文献１の部分除算器Ｄ１５に使用される部分除算器のブロック図である。
【図５】図５は、引用文献１の部分除算器Ｄ１４〜Ｄ０に使用される部分除算器のブロック図である。
【図６】図６は、本発明の第１実施形態における除算回路の構成を示すブロック図である。
【図７】図７は、本発明の第１実施形態の除算回路における除算方法のフローチャートである。
【図８】図８は、本発明の第２実施形態における除算回路の構成を示すブロック図である。
【図９】図９は、本発明の第２実施形態の除算回路における除算方法のフローチャートである。
【図１０】図１０は、本発明の第３実施形態における除算回路の構成を示すブロック図である。
【図１１】図１１は、本発明の第３実施形態の除算回路における除算方法のフローチャートである。
【図１２】図１２は、本発明の第４実施形態における除算回路の構成を示すブロック図である。
【図１３】図１３は、本発明の第５実施形態における除算回路の構成を示すブロック図である。
【図１４】図１４は、本発明の第６実施形態における除算回路の構成を示すブロック図である。
【図１５】図１５は、本発明の第７実施形態における除算回路の構成を示すブロック図である。
【図１６】図１６は、本発明の第８実施形態における除算回路の構成を示すブロック図である。
【図１７】図１７は、本発明の実施形態における誤差決定部４の回路図の例である。
【図１８】図１８は、本発明の実施形態における除数と被除数の関係である。
【図１９】図１９は、本発明の実施形態における除算回路の規模の概算見積もり結果である。
【図２０】図２０は、線形補完処理を説明するための図である。
【図２１】図２１は、（数２８）を利用したアルファブレンド処理回路２０のブロック図である。
【図２２】図２２は、アルファブレンド処理を利用したスプライト方式の画像処理装置３０のブロック図である。
【発明を実施するための形態】
【００２４】
添付図面を参照して、本発明の実施形態による除算回路を以下に説明する。
【００２５】
本発明の実施形態における除算回路は、被除数データを格納するレジスタのビット幅に依存して除数データが決定される。図１８は、本発明の実施形態における除数データと被除数データの関係である。本発明の実施形態における除算回路の産業上の利用可能性については後述する。
【００２６】
（第１実施形態）
［構成の説明］
はじめに、本発明の第１実施形態における除算回路の構成の説明を行う。図６は、本発明の第１実施形態における除算回路の構成を示すブロック図である。本発明の第１実施形態における除算回路は、レジスタ１、シフト演算部２及びレジスタ３を備える。レジスタ１とシフト演算部２は、８ビット分の信号線で接続されている。シフト演算部２とレジスタ３は、９ビット分の信号線で接続されている。図６では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。
【００２７】
レジスタ１は、偶数のビット幅を有し、被除数データが格納される。シフト演算部２は、レジスタ１の被除数データを、レジスタ１のビット幅の半分で表現可能な最大の数の除数データで除算した商を、レジスタ１の上位ビットのデータを取得することで算出する。
上述のレジスタ１の上位ビットとは、レジスタ１を上位ビットのビット幅と下位ビットのビット幅が同一になるように、上位ビット及び下位ビットに分割した場合の上位ビットのデータ（被除数データをレジスタ１の半分のビット数だけ右シフトした演算結果と同一のデータ）である。例えば、レジスタ１が１６ビットであれば、レジスタ１のビット幅の半分で表現可能な最大の数は、８’ｈＦＦとなる。ここで、８’ｈＦＦの８’は、８ビットであることを示し、ｈＦＦは、１６進数で値がＦＦであることを示す。すなわち、１０進数では、除数データは２５５となる。シフト演算部２は、レジスタ１の被除数データを８ビット右シフトした値を、レジスタ１の上位ビットを取得することにより、上述の商を求める。レジスタ３は、シフト演算部２による演算結果が格納される。
【００２８】
［動作方法の説明］
次に、第１実施形態の除算回路における除算方法の説明を行う。
【００２９】
図７は、本発明の第１実施形態の除算回路における除算方法のフローチャートである。説明を容易にするため、被除数データが格納されるレジスタ１のビット幅が１６ビットである場合について説明する。なお、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。以下の説明は、被除数データが格納されるレジスタ１のビット幅が偶数であれば、同様にして成り立つ。
【００３０】
（ステップＳ１）
レジスタ１に１６ビットで表現可能な被除数が格納される。除算回路の処理は、ステップＳ２へ進む。
【００３１】
（ステップＳ２）
まず、レジスタ１の説明に使用する記号について説明する。Ｘ［１５：０］は、レジスタ１の０番目のビット（ＬＳＢ）から、レジスタ１の１５番目のビット（ＭＳＢ）までのビット範囲を示す。同様に、Ｘ［１５：８］は、レジスタ１の８番目のビットから、レジスタ１の１５番目のビットまでのビット範囲を示し、Ｘ［７：０］は、レジスタ１の０番目のビットから、レジスタ１の７番目のビットまでのビット範囲を示す。
【００３２】
シフト演算部２は、Ｘ［１５：８］のデータを８ビットのデータとして、Ｘ［１５：０］のデータから独立して読み込むことで、Ｘ［１５：０］のデータを８ビットシフトした演算結果を求める。この演算結果は、被除数データを２５６で除算した場合の商であるため、誤差が生じる。除算回路の処理は、ステップＳ３へ進む。
【００３３】
（ステップＳ３）
シフト演算部２は、ステップＳ２の演算結果をレジスタ３に格納し、除算回路の処理は終了する。
【００３４】
本発明の第１実施形態によれば、レジスタ１の半分のビット数で表現できる最大数の除数データで除算した商を求める場合に、レジスタ１の上位ビットのデータを取得するシフト演算部２によって商を求めることで、誤差は生じるが回路規模を抑えた除算回路を得ることができる。除算の誤差よりも、とにかく回路規模の縮小が求められる場面において、本発明の第１実施形態は有用である。
【００３５】
（第２実施形態）
［構成の説明］
はじめに、本発明の第２実施形態における除算回路の構成の説明を行う。図８は、本発明の第２実施形態における除算回路の構成を示すブロック図である。本発明の第２実施態における除算回路は、レジスタ１、シフト演算部２、レジスタ３及び誤差決定部４を備える。レジスタ１の上位８ビットと、シフト演算部２及び誤差決定部４は、８ビット分の信号線で接続されている。レジスタ１の下位８ビットと誤差決定部４は、８ビット分の信号線で接続されている。誤差決定部４とシフト演算部２は、２ビット分の信号線で接続されている。シフト演算部２とレジスタ３は、９ビット分の信号線で接続されている。図８では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。
【００３６】
レジスタ１及びレジスタ３については、第１実施形態と同様であるため、説明を省略する。シフト演算部２は、第１実施形態と同様にして、レジスタ１の被除数データを、レジスタ１のビット幅の半分で表現可能な最大の数の除数データで除算した商を、レジスタ１の上位ビットのデータを取得することで算出する。シフト演算部２は、上述の商に対して、誤差決定部４からシフト演算部２へ入力される誤差（０、１、２のいずれか）を加算する。誤差決定部４は、レジスタ１を上位ビットのビット幅と下位ビットのビット幅が同一になるように、上位ビット及び下位ビットに分割した場合の上位ビットのデータ（被除数データをレジスタ１の半分のビット数だけ右シフトした演算結果と同一のデータ）と、被除数データをレジスタ１の半分のビット数で表現できる最大値で除算した商の誤差を、被除数データに基づいて決定する。
【００３７】
［動作方法の説明］
次に、本発明の第２実施形態における除算回路において、除算方法の説明を行う。
【００３８】
図９は、本発明の第２実施形態の除算回路における除算方法のフローチャートである。説明を容易にするため、被除数データが格納されるレジスタ１のビット幅が１６ビットである場合について説明する。なお、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。以下の説明は、被除数データが格納されるレジスタ１のビット幅が偶数であれば、同様に成り立つ。
【００３９】
（ステップＳ２１）
レジスタ１に１６ビットで表現可能な被除数が格納される。除算回路の処理は、ステップＳ２２へ進む。
【００４０】
（ステップＳ２２）
誤差決定部４は、レジスタ１を上位ビットのビット幅と下位ビットのビット幅が同一になるように、上位ビット及び下位ビットに分割する。具体的には、１６ビットのレジスタ１をＸ［１５：０］で示すと、上位ビットは、Ｘ［１５：８］となり、下位ビットはＸ［７：０］となる。
【００４１】
誤差決定部４は、レジスタ１の上位ビットであるＸ［１５：８］のデータ（被除数データをレジスタ１の半分のビット数だけ右シフトした演算結果と同一のデータ）と、被除数データをレジスタ１の半分のビット数で表現できる最大値で除算した商の誤差を、被除数データに基づいて決定する。
【００４２】
ここでは、被除数データを格納するレジスタ１のビット幅を１６ビットとしているため、被除数データをレジスタ１の半分のビット数で表現できる最大値である除数データは、８’ｈＦＦとなる。ここで、８’ｈＦＦの８’は、８ビットであることを示し、ｈＦＦは、１６進数で値がＦＦであることを示す。すなわち、１０進数では、除数データは２５５となる。
【００４３】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、０以上、かつ除数データ（２５５）未満であれば、誤差データを０に決定する。
【００４４】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、除数データ（２５５）以上、かつ除数データの２倍のデータ（５１０）未満であれば、誤差データを１に決定する。
【００４５】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、前記除数データの２倍のデータ（５１０）であれば、誤差データを２に決定する。
【００４６】
誤差決定部４は、決定した誤差データをシフト演算部２に出力する。
【００４７】
上記のように誤差データを決定することができる理由については、後述する。除算回路の処理は、ステップＳ２３へ進む。
【００４８】
（ステップＳ２３）
シフト演算部２は、Ｘ［１５：８］のデータを８ビットのデータとして、Ｘ［１５：０］のデータから独立して読み込むことで、Ｘ［１５：０］のデータを８ビットシフトした演算結果を求める。除算回路の処理は、ステップＳ２４へ進む。
【００４９】
（ステップＳ２４）
シフト演算部２は、ステップＳ３の演算結果に対して、誤差決定部４によって決定された誤差データ（０、１、２のいずれか）を加算する。除算回路の処理は、ステップＳ２５へ進む。
【００５０】
（ステップＳ２５）
シフト演算部２は、ステップＳ２４の演算結果をレジスタ３に格納し、除算回路の処理は終了する。
【００５１】
本発明の第２実施形態は、第１実施形態のシフト演算部１を、除算をシフト演算で代用することによって生じる商の誤差を補正するように改良したものである。本発明の第２実施形態によれば、第１実施形態の除算回路よりも、回路規模は増加するが、除算をシフト演算で代用することによって生じる商の誤差をなくすことができる。
【００５２】
ここで、誤差決定部４が、ステップＳ２２の方法で誤差を算出できる理由について説明する。説明を容易にするため、被除数データが格納されるレジスタ１のビット幅が１６ビットである場合について説明する。以下の説明は、被除数データが格納されるレジスタ１のビット幅が偶数であれば、同様にして成り立つ。
【００５３】
右シフト演算による演算結果と、除算結果の誤差をＴ０１とすると、次式が成り立つ。
【００５４】
（数３）
Ｔ０１＝（Ｘ［１５：０］÷８’ｈＦＦ）−（Ｘ［１５：０］＞＞８）
【００５５】
ここで、Ｘ［１５：０］＞＞８は、レジスタ１の被除数データを８ビット右シフトすることを示す。８’ｈＦＦの８’は、８ビットであることを示し、ｈＦＦは、１６進数のＦＦを示す。
【００５６】
Ｘ［１５：０］は、上位ビットであるＸ［１５：８］のデータと、下位ビットであるＸ［７：０］のデータを用いて、次式で表すことができる。
【００５７】
（数４）
Ｘ［１５：０］＝Ｘ［１５：８］×９’ｈ１００＋Ｘ［７：０］
【００５８】
また、右シフト演算ではあふれビットは切り捨てられるため、Ｘ［１５：０］＞＞８は、次式で表すことができる。
【００５９】
（数５）
Ｘ［１５：０］＞＞８＝Ｘ［１５：８］
【００６０】
（数３）に（数４）と（数５）を代入すると、次式が成り立つ。
【００６１】
（数６）
Ｔ０１＝（（Ｘ［１５：８］×９’ｈ１００＋Ｘ［７：０］）÷８’ｈＦＦ）
−Ｘ［１５：８］
【００６２】
（数６）の両辺に８’ｈＦＦを乗算すると、次式が成り立つ。
【００６３】
（数７）
Ｔ０１×８’ｈＦＦ＝（Ｘ［１５：８］×９’ｈ１００＋Ｘ［７：０］）
−Ｘ［１５：８］×８’ｈＦＦ
【００６４】
更に、（数７）を整理すると、次式が成り立つ。
【００６５】
（数８）
Ｔ０１＝（Ｘ［１５：８］＋Ｘ［７：０］）÷８’ｈＦＦ
【００６６】
ここで、Ｘ［１５：８］＋Ｘ［７：０］に対して、次式が成り立つ。
【００６７】
（数９）
９’ｈ０００＜＝Ｘ［１５：８］＋Ｘ［７：０］＜＝９’ｈ１ＦＥ
【００６８】
したがって、（数８）及び（数９）により、Ｔ０１の値は、Ｘ［１５：８］＋Ｘ［７：０］の範囲に基づいて、以下の３通りに決定できる。すなわち、
【００６９】
（数１０）
９’ｈ０００＜＝Ｘ［１５：８］＋Ｘ［７：０］＜９’ｈ０ＦＦ
【００７０】
であれば、Ｔ０１は、０に決定できる。
【００７１】
（数１１）
９’ｈ０ＦＦ＜＝Ｘ［１５：８］＋Ｘ［７：０］＜９’ｈ１ＦＥ
【００７２】
であれば、Ｔ０１は、１に決定できる。
【００７３】
（数１２）
９’ｈ１ＦＥ＝Ｘ［１５：８］＋Ｘ［７：０］
【００７４】
であれば、Ｔ０１は、２に決定できる。
【００７５】
以上が、ステップＳ２２の方法で誤差を算出できる理由の説明である。図１７は、本発明の実施形態における誤差決定部４の回路図の例である。
【００７６】
（第３実施形態）
［構成の説明］
はじめに、本発明の第３実施形態における除算回路の構成の説明を行う。図１０は、本発明の第３実施形態における除算回路の構成を示すブロック図である。本発明の第３実施形態における除算回路は、レジスタ１、シフト演算部２、レジスタ３、誤差決定部４、シフト演算部５、シフト演算部６及びセレクタ７を備える。レジスタ１の上位８ビットと、シフト演算部２、シフト演算部５、シフト演算部６及び誤差決定部４は、８ビット分の信号線で接続されている。レジスタ１の下位８ビットと誤差決定部４は、８ビット分の信号線で接続されている。シフト演算部２とセレクタ７は、９ビット分の信号線で接続されている。シフト演算部５とセレクタ７は、９ビット分の信号線で接続されている。シフト演算部６とセレクタ７は、９ビット分の信号線で接続されている。誤差決定部４とセレクタ７は、２ビット分の信号線で接続されている。セレクタ７とレジスタ３は、９ビット分の信号線で接続されている。図１０では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。
【００７７】
レジスタ１、レジスタ３及び誤差決定部４については、第２実施形態と同様であるため、説明を省略する。
【００７８】
シフト演算部２は、レジスタ１の上述した上位ビットのデータを商として算出する。シフト演算部５は、レジスタ１の上述した上位ビットのデータ＋１を商として算出する。シフト演算部６は、レジスタ１の上述した上位ビットのデータ＋２を商として算出する。
【００７９】
セレクタ７は、誤差決定部４で決定した誤差データに基づいて、シフト演算部２、シフト演算部５又はシフト演算部６の演算結果から、いずれか１つの演算結果を選択する。
【００８０】
［動作方法の説明］
次に、本発明の実施形態３における除算回路において、除算方法の説明を行う。
【００８１】
図１１は、本発明の第３実施形態の除算回路における除算方法のフローチャートである。説明を容易にするため、被除数データが格納されるレジスタ１のビット幅が１６ビットである場合について説明する。なお、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。以下の説明は、被除数データが格納されるレジスタ１のビット幅が偶数であれば、同様に成り立つ。
【００８２】
（ステップＳ３１）
レジスタ１に１６ビットで表現可能な被除数が格納される。除算回路の処理は、ステップＳ３２へ進む。
【００８３】
（ステップＳ３２）
誤差決定部４は、レジスタ１の上位ビットであるＸ［１５：８］のデータ（被除数データをレジスタ１の半分のビット数だけ右シフトした演算結果と同一のデータ）と、被除数データをレジスタ１の半分のビット数で表現できる最大値で除算した商の誤差を、被除数データに基づいて決定する。
【００８４】
ここでは、被除数データを格納するレジスタ１のビット幅を１６ビットとしているため、被除数データをレジスタ１の半分のビット数で表現できる最大値である除数データは、８’ｈＦＦとなる。ここで、８’ｈＦＦの８’は、８ビットであることを示し、ｈＦＦは、１６進数で値がＦＦであることを示す。すなわち、１０進数では、除数データは２５５となる。
【００８５】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、０以上、かつ除数データ（２５５）未満であれば、誤差データを０に決定する。
【００８６】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、除数データ（２５５）以上、かつ除数データの２倍のデータ（５１０）未満であれば、誤差データを１に決定する。
【００８７】
誤差決定部４は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和が、前記除数データの２倍のデータ（５１０）であれば、誤差データを２に決定する。
【００８８】
上記のように誤差データを決定する理由については、前述した通りである。除算回路の処理は、ステップＳ３３へ進む。
【００８９】
（ステップＳ３３）
シフト演算部２は、Ｘ［１５：８］のデータを８ビットのデータとして、Ｘ［１５：０］のデータから独立して読み込むことで、Ｘ［１５：０］のデータを８ビットシフトした演算結果を求める。
【００９０】
シフト演算部５は、Ｘ［１５：８］のデータを８ビットのデータとして、Ｘ［１５：０］のデータから独立して読み込むことで、Ｘ［１５：０］のデータを８ビットシフトした演算結果を求め、更に、この演算結果に１を加算する。
【００９１】
シフト演算部６は、Ｘ［１５：８］のデータを８ビットのデータとして、Ｘ［１５：０］のデータから独立して読み込むことで、Ｘ［１５：０］のデータを８ビットシフトした演算結果を求め、更に、この演算結果に２を加算する。除算回路の処理は、ステップＳ３４へ進む。
【００９２】
（ステップＳ３４）
セレクタ７は、誤差データが０であるかどうかを確認する。除算回路の処理は、誤差データが０である場合には、ステップＳ３５へ進み、誤差データが０でない場合には、ステップＳ３６へ進む。
【００９３】
（ステップＳ３５）
セレクタ７は、レジスタ１に格納された被除数データを、レジスタ１の半分のビット数で表現できる最大値である除数データで除算した商として、ステップＳ３３でシフト演算部２が算出した演算結果を選択する。除算回路の処理は、ステップＳ３９へ進む。
【００９４】
（ステップＳ３６）
セレクタ７は、誤差データが１であるかどうかを確認する。除算回路の処理は、誤差データが１である場合には、ステップＳ３７へ進み、誤差データが１でない場合には、ステップＳ３８へ進む。
【００９５】
（ステップＳ３７）
セレクタ７は、レジスタ１に格納された被除数データを、レジスタ１の半分のビット数で表現できる最大値である除数データで除算した商として、ステップＳ３３でシフト演算部５が算出した演算結果を選択する。除算回路の処理は、ステップＳ３９へ進む。
【００９６】
（ステップＳ３８）
セレクタ７は、レジスタ１に格納された被除数データを、レジスタ１の半分のビット数で表現できる最大値である除数データで除算した商として、ステップＳ３３でシフト演算部６が算出した演算結果を選択する。除算回路の処理は、ステップＳ３９へ進む。
【００９７】
（ステップＳ３９）
セレクタ７は、ステップＳ３５、ステップＳ３７又はステップＳ３８のいずれか１つのステップで選択した演算結果を、レジスタ３に格納し、除算回路の処理は終了する。
【００９８】
本発明の第３実施形態の特徴は、本発明の第２実施形態のシフト演算部２の誤差補正処理を、シフト演算部２、シフト演算部５、シフト演算部６に分割し、セレクタにより、商を選択させているところである。
【００９９】
（第４実施形態）
［構成の説明］
本発明の第３実施形態の一部を変更した例である第４実施形態について説明する。図１２は、本発明の第４実施形態における除算回路の構成を示すブロック図である。図１２では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。本発明の第３実施形態との違いは、シフト演算部６がないことである。その他の構成と動作方法の説明については、本発明の第３実施形態と同様であるため、詳細な説明は省略する。
【０１００】
被除数データが（数１２）を満たすことがない場合（例えば、レジスタ１が１６ビットである場合、レジスタ１に格納されるデータが‘ｈＦＦＦＦとならない場合）には、誤差が２の場合の演算処理を省略することができるため、第３実施形態ではなく、第４実施形態を適用することができる。
【０１０１】
（第５実施形態）
［構成の説明］
はじめに、本発明の第５実施形態における除算回路の構成の説明を行う。図１３は、本発明の第５実施形態における除算回路の構成を示すブロック図である。本発明の第５実施形態における除算回路は、レジスタ１、シフト演算部２、レジスタ３、誤差決定部４、シフト演算部５、シフト演算部６、セレクタ７及びシフト演算部８を備える。レジスタ１の上位９ビットと、シフト演算部２、シフト演算部５、シフト演算部６、誤差決定部４及びシフト演算部８は、９ビット分の信号線で接続されている。レジスタ１の下位８ビットと誤差決定部４は、８ビット分の信号線で接続されている。シフト演算部２とセレクタ７は、９ビット分の信号線で接続されている。シフト演算部５とセレクタ７は、９ビット分の信号線で接続されている。シフト演算部６とセレクタ７は、９ビット分の信号線で接続されている。シフト演算部８とセレクタ７は、９ビット分の信号線で接続されている。誤差決定部４とセレクタ７は、２ビット分の信号線で接続されている。セレクタ７とレジスタ３は、１０ビット分の信号線で接続されている。図１３では、被除数データが格納されるレジスタ１のビット幅を１７ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、符号ビットを除いて偶数であればよく、１７ビットに限られない。
【０１０２】
レジスタ１には、負数も考慮した被除数データが格納される。レジスタ１のＭＳＢは、符号ビットに使用され、ＭＳＢを除いたレジスタ１のビット数は、偶数である。レジスタ３には、セレクタ７により選択された商が格納される。
【０１０３】
シフト演算部２は、レジスタ１の上位９ビットのデータを商として算出する。シフト演算部５は、レジスタ１の上位９ビットのデータ＋１を商として算出する。シフト演算部６は、レジスタ１の上位９ビットのデータ＋２を商として算出する。シフト演算部８は、レジスタ１の上位９ビットのデータ−１を商として算出する。
【０１０４】
誤差決定部４は、レジスタ１の上位９ビットの値（レジスタ１の被除数データを８ビットだけ右シフトした演算結果と同一のデータ）と、レジスタ１の下位８ビットで表現できる最大値で除算した商の誤差を、被除数データに基づいて決定する。
【０１０５】
セレクタ７は、誤差決定部４で決定した誤差データに基づいて、シフト演算部２、シフト演算部５、シフト演算部６又はシフト演算部８の演算結果から、いずれか１つの演算結果を選択する。
【０１０６】
［動作方法の説明］
本実施形態の動作方法は、被除数データに負数も考慮している点を除いては、第３実施形態と同様である。被除数データに負数も考慮しているため、誤差決定部４における誤差を決定するための条件式が変更されている点と、シフト演算部８が追加されている点が異なる。その他の動作方法については、第３実施形態と同様であるため、詳細な説明については、省略する。
【０１０７】
まず、誤差決定部４で誤差を決定するための条件式について説明する。右シフト演算による演算結果と、除算結果の誤差をＴ０１とすると、次式が成り立つ。
（数１３）
Ｔ０１＝（Ｘ［１６：０］÷８’ｈＦＦ）−（Ｘ［１６：０］＞＞８）
【０１０８】
（数１３）は、（数６）を導いた場合と同様にして、次式で表すことができる。
（数１４）
Ｔ０１＝（（Ｘ［１６］×１７’ｈ１００００＋Ｘ［１５：８］×９’ｈ１００
＋Ｘ［７：０］）÷８’ｈＦＦ）−（Ｘ［１６］×９’ｈ１００＋Ｘ［１５：８］）
【０１０９】
（数１４）の両辺に８’ｈＦＦを乗算すると、次式が成り立つ。
（数１５）
Ｔ０１×８’ｈＦＦ＝（Ｘ［１６］×１７’ｈ１００００
＋Ｘ［１５：８］×９’ｈ１００＋Ｘ［７：０］）
−（Ｘ［１６］×９’ｈ１００＋Ｘ［１５：８］）×８’ｈＦＦ
【０１１０】
ここで、Ｘ［１６］は、０又は１であるため、次式が成り立つ。
（数１６）
Ｘ［１６］×１７’ｈ１００００−（Ｘ［１６］×９’ｈ１００）×８’ｈＦＦ
＝Ｘ［１６］×９‘ｈ１００
【０１１１】
したがって、（数８）を導いた場合と同様にして、次の（数１７）を得る。
（数１７）
Ｔ０１×８’ｈＦＦ＝Ｘ［１６］×９’ｈ１００＋Ｘ［１５：８］＋Ｘ［７：０］
【０１１２】
ここで、Ｘ［１６］×９’ｈ１００が、０又は２５６であること、及びＸ［１５：８］＋Ｘ［７：０］のとりうる範囲を考慮すると、被除数レジスタが正数の場合（Ｘ［１６］＝０）には、（数１０）〜（数１２）の条件式で、誤差Ｔ０１を０〜２に決定することができる。また、被除数レジスタが負数の場合（Ｘ［１６］＝１）には、以下のように場合分けすることで、誤差Ｔ０１を決定することができる。
（数１８）
Ｘ［１５：８］＋Ｘ［７：０］＜＝１０’ｈ００１
であれば、Ｔ０１は、−１に決定できる。
（数１９）
１０’ｈ００１＜Ｘ［１５：８］＋Ｘ［７：０］＜＝１０’ｈ１００
【０１１３】
であれば、Ｔ０１は、０に決定できる。
（数２０）
１０’ｈ１００＜Ｘ［１５：８］＋Ｘ［７：０］＜＝１０’ｈ１ＦＦ
【０１１４】
であれば、Ｔ０１は、１に決定できる。
（数２１）
１０’ｈ１ＦＦ＜Ｘ［１５：８］＋Ｘ［７：０］＜＝１０’ｈ２ＦＥ
【０１１５】
であれば、Ｔ０１は、２に決定できる。
【０１１６】
被除数データが、正数又は負数に関係なく誤差データを決定する条件式にするため、符号ビットＸ［１６］を利用すると、（数１０）〜（数１２）及び（数１８）〜（数２１）を以下の４つの条件式にまとめることができる。
（数２２）
Ｘ［１５：８］＋Ｘ［７：０］−Ｘ［１６］×２＜１０’ｈ０００
【０１１７】
であれば、Ｔ０１は、−１に決定できる。
（数２３）
１０’ｈ０００＜＝Ｘ［１５：８］＋Ｘ［７：０］−Ｘ［１６］×２＜１０’ｈ０ＦＦ
【０１１８】
であれば、Ｔ０１は、０に決定できる。
（数２４）
１０’ｈ０ＦＦ＜＝Ｘ［１５：８］＋Ｘ［７：０］−Ｘ［１６］×２＜１０’ｈ１ＦＥ
【０１１９】
であれば、Ｔ０１は、１に決定できる。
（数２５）
１０’ｈ１ＦＥ＝Ｘ［１５：８］＋Ｘ［７：０］−Ｘ［１６］×２
【０１２０】
であれば、Ｔ０１は、２に決定できる。
【０１２１】
本実施形態の誤差決定部４においては、上記の（数２２）〜（数２５）を利用して、誤差を決定することができる。シフト演算部８は、被除数が正数の場合には、発生しなかった誤差Ｔ０１＝−１の場合についての誤差を補正するための演算部である。
【０１２２】
以上のように、本実施形態によれば、被除数データが負数である場合であっても、正しい除算結果を得ることができる。
【０１２３】
（第６実施形態）
本発明の第３実施形態の一部を変更した例である第６実施形態について説明する。図１４は、本発明の第６実施形態における除算回路の構成を示すブロック図である。図１４では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。本発明の第３実施形態との違いは、誤差決定部４が、誤差判定条件値演算部９に変更されている点と、セレクタ７の演算結果選択処理が異なる。その他の構成と動作方法の説明については、本発明の第３実施形態と同様であるため、詳細な説明は省略する。
【０１２４】
誤差判定条件値演算部９は、Ｘ［１５：８］のデータと、Ｘ［７：０］のデータの和を算出し、セレクタ７に出力する。
【０１２５】
セレクタ７は、誤差判定条件値演算部９で算出されたＸ［１５：８］のデータと、Ｘ［７：０］のデータの和に基づいて、シフト演算部２、シフト演算部５又はシフト演算部６のいずれか１つの演算結果を選択し、レジスタ３へ出力する。
【０１２６】
本発明の第６実施形態とは、誤差判定条件値演算部９で誤差データ（０、１又は２）を算出しない点、セレクタ７では、誤差判定条件値演算部９で算出されたＸ［１５：８］のデータと、Ｘ［７：０］のデータの和を商の選択条件に利用する点が異なる。
【０１２７】
（第７実施形態）
［構成の説明］
本発明の第６実施形態の一部を変更した例である第７実施形態について説明する。図１５は、本発明の第７実施形態における除算回路の構成を示すブロック図である。図１５では、被除数データが格納されるレジスタ１のビット幅を１６ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、偶数であればよく、１６ビットに限られない。本発明の第６実施形態との違いは、シフト演算部６がないことである。その他の構成と動作方法の説明については、本発明の第６実施形態と同様であるため、詳細な説明は省略する。
【０１２８】
被除数データが（数１２）を満たすことがない場合（例えば、レジスタ１が１６ビットである場合、レジスタ１に格納されるデータが‘ｈＦＦＦＦとならない場合）には、誤差が２の場合の演算処理を省略することができるため、第６実施形態ではなく、第７実施形態を適用することができる。
【０１２９】
（第８実施形態）
［構成の説明］
本発明の第５実施形態の一部を変更した例である第８実施形態について説明する。図１６は、本発明の第８実施形態における除算回路の構成を示すブロック図である。図１６では、被除数データが格納されるレジスタ１のビット幅を１７ビットとしているが、被除数データが格納されるレジスタ１のビット幅は、符号ビットを除いて偶数であればよく、１７ビットに限られない。本発明の第５実施形態との違いは、誤差決定部４が、誤差判定条件値演算部９に変更されている点と、セレクタ７の演算結果選択処理が異なる。その他の構成と動作方法の説明については、本発明の第５実施形態と同様であるため、詳細な説明は省略する。
【０１３０】
誤差判定条件値演算部９は、（Ｘ［１５：８］＋Ｘ［７：０］）−（Ｘ［１６］×２）を求め、セレクタ７に出力する。
【０１３１】
セレクタ７は、誤差判定条件値演算部９で算出された（Ｘ［１５：８］＋Ｘ［７：０］）−（Ｘ［１６］×２）に基づいて、シフト演算部２、シフト演算部５、シフト演算部６又はシフト演算部８のいずれか１つの演算結果を選択し、レジスタ３へ出力する。
【０１３２】
本発明の第５実施形態とは、誤差判定条件値演算部９で誤差データ（−１、０、１又は２）を算出しない点、セレクタ７では、誤差判定条件値演算部９で算出された（Ｘ［１５：８］＋Ｘ［７：０］）−（Ｘ［１６］×２）のデータを商の選択条件に利用する点が異なる。
【０１３３】
次に、本実施形態における除算回路の規模について説明する。図１９は、本発明の実施形態における除算回路の規模の概算見積もり結果である。図１９では、回路規模の見積もりを素子数で行っている。
【０１３４】
まず、本発明の第１実施形態における回路規模について説明する。レジスタ１については、１６ビットのビット幅を有するが、１ビットを８素子として、１２８素子とした。シフト演算部２については、レジスタ１の上位８ビットを取得することで実現できるため、０素子とした。レジスタ３については、９ビットのビット幅を有するため、７２素子とした。したがって、第１実施形態における回路規模は、合計で２００素子である。
【０１３５】
次に、本発明の第２実施形態における回路規模について説明する。レジスタ１については、１６ビットのビット幅を有するが、１ビットを８素子として、１２８素子とした。シフト演算部２については、論理回路として、１４０素子とした。レジスタ３については、９ビットのビット幅を有するため、７２素子とした。誤差決定部４については、論理回路として、１０４素子とした。したがって、第２実施形態における回路規模は、合計で４４４素子である。
【０１３６】
次に、本発明の第３実施形態における回路規模について説明する。レジスタ１については、１６ビットのビット幅を有するが、１ビットを８素子として、１２８素子とした。レジスタ１の上位８ビットを取得することで実現できるため、０素子とした。レジスタ３については、９ビットのビット幅を有するため、７２素子とした。誤差決定部４については、論理回路として、１０４素子とした。シフト演算部５、シフト演算部６については、論理回路として、５６素子とした。セレクタ７については、論理回路として、３２０素子とした。したがって、第３実施形態における回路規模は、合計で７３６素子である。
【０１３７】
次に、本発明の第４実施形態における回路規模について説明する。第４実施形態については、第３実施形態のシフト演算部６を省いたものである。したがって、第４実施形態における回路規模は、合計で６８０素子である。
【０１３８】
次に、本発明の第５実施形態における回路規模について説明する。第５実施形態については、第３実施形態にレジスタ１の１ビットとレジスタ３の１ビットとシフト演算部８とを追加したものである。したがって、第５実施形態における回路規模は、合計で８０８素子である。
【０１３９】
次に、本発明の第６実施形態における回路規模について説明する。第６実施形態については、第３実施形態の構成を変更したものである。誤差決定部４が、誤差判定条件値演算部９に変更されている。誤差判定条件値演算部９については、論理回路として、６４素子とした。また、セレクタ７については、上記の変更により、論理回路として、３６０素子としている。したがって、第６実施形態における回路規模は、合計で７３６素子である。
【０１４０】
次に、本発明の第７実施形態における回路規模について説明する。第７実施形態については、第４実施形態の構成を変更したものである。誤差決定部４が、誤差判定条件値演算部９に変更されている。誤差判定条件値演算部９については、論理回路として、６４素子とした。また、セレクタ７については、上記の変更により、論理回路として、３６０素子としている。したがって、第７実施形態における回路規模は、合計で６８０素子である。
【０１４１】
最後に、本発明の第８実施形態における回路規模について説明する。第８実施形態については、第５実施形態の構成を変更したものである。誤差決定部４が、誤差判定条件値演算部９に変更されている。誤差判定条件値演算部９については、論理回路として、６４素子とした。また、セレクタ７については、上記の変更により、論理回路として、３６０素子としている。したがって、第８実施形態における回路規模は、合計で８０８素子である。
【０１４２】
以上のように、本発明の実施形態における除算回路の回路規模は、上記のいずれの実施形態においても、従来の回復型除算器よりも削減されている。これにより、従来の一般的な除算器に比べて、消費電力削減の効果がある。また、回路規模が削減されることにより、被除数データが格納されるレジスタ１の入力から、レジスタ３への商の出力までの論理段数も削減されているため、一般的な除算器に比べて、処理速度も向上している。
【０１４３】
次に、被除数データが格納されるレジスタ１のビット幅を増加させた場合の、除算回路の回路規模の増加率について説明する。本発明の実施形態における除算回路の回路規模の増加率は、被除数データを格納するレジスタ１のビット幅増加に伴い、ビット幅増加割合の１乗倍である。すなわち、レジスタ１のビット幅がｎビットである場合の本発明の実施形態の除算回路の回路規模をＳ３とすると、被除数データを格納するレジスタ１のビット幅を、ｎビットからｍビットへ増加させた場合における本実施形態の除算回路の回路規模Ｓ４は、次式で表すことができる。
【０１４４】
（数２６）
Ｓ４＝Ｓ３×（ｍ／ｎ）
これは（数２）で示した従来の回復型除算器における２乗倍と比較すると格段に改善されていることになる。
【０１４５】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【産業上の利用可能性】
【０１４６】
本発明の除算回路では、除数が被除数を格納するレジスタの半分のビット数で表現できる最大数に固定されている。本発明の除算回路の産業上の利用可能性について説明する。
【０１４７】
画像処理の分野において、線形補完の計算式が利用されている。図２０は、線形補完処理を説明するための図である。線形補完の計算式は以下である。
（数２７）
Ｃ＝（１−α）×Ａ＋α×Ｂ
【０１４８】
この計算式（数２７）は、画像の拡大・縮小処理や、透過率の決定等の画像合成処理に利用されている。特に、画像合成処理では、アルファブレンド処理として知られている。（数２７）のαがとりうる値の範囲は、０〜１であるため、（数２７）の計算をハードウェアを用いて実現する場合に、処理に負担がかかる。そのため、２点間Ａ、Ｂの間を分割して考えることで、αの値を整数値として捉える方法が考えられる。例えば、２点間Ａ、Ｂの間を２５５分割した場合には、αのとりうる値の範囲は、０〜２５５となる。このとき、（数２７）に対応する式は、以下のようになる。
（数２８）
Ｃ＝（（２５５−α）×Ａ＋α×Ｂ）÷２５５
【０１４９】
このように、（数２８）では、Ｃを求めるために、右辺を２のべき乗−１（この場合では、２５５）で除算する必要がある。
【０１５０】
図２１は、（数２８）を利用したアルファブレンド処理回路２０のブロック図である。アルファブレンド処理回路２０は、入力レジスタ２１、２２、出力レジスタ２３、乗算器２４、２５、加算器２６、及び除算器２７を備える。入力レジスタ２１には、乗算器２４を使用して、（２５５−α）と乗算する値Ａが設定される。入力レジスタ２２には、乗算器２５を使用して、αと乗算する値Ｂが設定される。出力レジスタ２３には、（数２８）による演算結果Ｃが設定される。
【０１５１】
従来の除算回路である図１の除算回路を、除算器２７に適用した場合のアルファブレンド処理回路の処理速度と、本発明の実施形態による除算回路を、除算器２７に適用した場合のアルファブレンド処理回路の処理速度を比較する。
【０１５２】
従来の除算回路である図１の除算回路を、除算器２７に適用した場合は、除算器２７の処理速度は、１８サイクルとなる。この１８サイクルの内訳は、被除数をレジスタＸへ格納する処理が１サイクル、部分除算器Ｄ１５〜Ｄ０を順次、動作させる処理が１６サイクル、商をレジスタＱへ格納する処理が１サイクルである。したがって、アルファブレンド処理回路２０の処理速度は、乗算器２４、２５の処理が１サイクル、加算器２６の処理が１サイクル、除算器２７の処理が１８サイクルとなるため、２０サイクルとなる。１サイクルにかかる処理時間を、２（ｎｓ）とすると、アルファブレンド処理回路２０の処理時間は、４０（ｎｓ）となる。
【０１５３】
一方、本発明の第１実施形態による除算回路を、除算器２７に適用した場合は、除算器２７の処理速度は、３サイクルとなる。この３サイクルの内訳は、被除数をレジスタ１へ格納する処理が１サイクル、シフト演算部２の処理が１サイクル、商をレジスタ３へ格納する処理が１サイクルである。したがって、アルファブレンド処理回路２０の処理速度は、乗算器２４、２５の処理が１サイクル、加算器２６の処理が１サイクル、除算器２７の処理が３サイクルとなるため、５サイクルとなる。１サイクルにかかる処理時間を、２（ｎｓ）とすると、アルファブレンド処理回路２０の処理時間は、１０（ｎｓ）となる。
【０１５４】
本発明の第１実施形態による除算回路を、除算器２７に適用した場合のアルファブレンド処理回路の処理速度は、従来の除算回路である図１の除算回路を、除算器２７に適用した場合に比べて、４倍速くなる。
【０１５５】
同様に、本発明の第２実施形態から第８実施形態の除算回路を、除算器２７に適用した場合のアルファブレンド処理回路における処理速度も、従来の除算回路である図１の除算回路を、除算器２７に適用した場合に比べて速くなる。
【０１５６】
次に、アルファブレンド処理を利用したスプライト方式の画像処理装置３０における速度効果について説明する。図２２は、アルファブレンド処理を利用したスプライト方式の画像処理装置３０のブロック図である。画像処理装置３０は、パターンメモリＩ／Ｆ部３１、スプライト処理部３２、スプライトパターン発生部３３、ラインバッファ３４、フレーム制御部３５、及び出力処理部３６を備える。本発明の実施形態の除算回路は、スプライト処理部３２において利用される。各ブロックの動作の詳細については、通常のスプライト方式の画像処理装置３０と同様であるため省略する。
【０１５７】
従来の除算回路である図１の除算回路を、スプライト処理部３２に適用した場合の画像処理装置３０の処理速度と、本発明の実施形態による除算回路を、スプライト処理部３２に適用した場合の画像処理装置３０の処理速度を比較する。
【０１５８】
従来の除算回路である図１の除算回路を、スプライト処理部３２に適用した場合の画像処理装置３０の処理速度は、２２サイクルとなる。この２２サイクルの内訳は、パターンメモリＩ／Ｆ部３１が１サイクル、スプライト処理部３２が１８サイクル、ラインバッファ３４が１サイクル、フレーム制御部３５が１サイクル、出力処理部３６が１サイクルである。
【０１５９】
ここで、クロック周波数を、表示画面に応じて、最小６ＭＨｚから最大４０ＭＨｚの周波数とすると、周期は、最小２５（ｎｓ）から最大１６６（ｎｓ）となる。画像処理装置３０の処理時間は、最小５５０（ｎｓ）から最大３，６５２（ｎｓ）となる。
【０１６０】
本発明の第１実施形態による除算回路を、スプライト処理部３２に適用した場合の画像処理装置３０の処理速度は、７サイクルとなる。この７サイクルの内訳は、パターンメモリＩ／Ｆ部３１が１サイクル、スプライト処理部３２が３サイクル、ラインバッファ３４が１サイクル、フレーム制御部３５が１サイクル、出力処理部３６が１サイクルである。
【０１６１】
ここで、クロック周波数を、表示画面に応じて、最小６ＭＨｚから最大４０ＭＨｚの周波数とすると、周期は、最小２５（ｎｓ）から最大１６６（ｎｓ）となる。画像処理装置３０の処理時間は、最小１７５（ｎｓ）から最大１，１６２（ｎｓ）となる。
【０１６２】
本発明の第１実施形態による除算回路を、スプライト処理部３２に適用した場合の画像処理装置３０の処理速度は、従来の除算回路である図１の除算回路を、除算器２７に適用した場合に比べて、約３倍速くなる。
【０１６３】
本願発明に係る除算回路及び除算方法は、上述の分野において産業上の利用可能性がある。ただし、本願発明の利用分野は、上述の分野に限られるものではなく、上述の例は、本願発明の利用可能性の一例である。
【符号の説明】
【０１６４】
１  レジスタ
２  シフト演算部
３  レジスタ
４  誤差決定部
５  シフト演算部
６  シフト演算部
７  セレクタ
８  シフト演算部
９  誤差判定条件値演算部
１０  加算器
１１  ＡＮＤ回路
１２〜１５  ＮＡＮＤ回路
１６  ＮＯＲ回路
１７  ＯＲ回路
２０  アルファブレンド処理回路
２１，２２  入力レジスタ
２３  出力レジスタ
２４，２５  乗算器
２６  加算器
２７  除算器
３０  画像処理装置
３１  パターンメモリＩ／Ｆ部
３２  スプライト処理部
３３  スプライトパターン発生部
３４  ラインバッファ
３５  フレーム制御部
３６  出力処理部
【図１】
2012141952.tif 000003
【図２】
2012141952.tif 000004
【図３】
2012141952.tif 000005
【図４】
2012141952.tif 000006
【図５】
2012141952.tif 000007
【図６】
2012141952.tif 000008
【図７】
2012141952.tif 000009
【図８】
2012141952.tif 000010
【図９】
2012141952.tif 000011
【図１０】
2012141952.tif 000012
【図１１】
2012141952.tif 000013
【図１２】
2012141952.tif 000014
【図１３】
2012141952.tif 000015
【図１４】
2012141952.tif 000016
【図１５】
2012141952.tif 000017
【図１６】
2012141952.tif 000018
【図１７】
2012141952.tif 000019
【図１８】
2012141952.tif 000020
【図１９】
2012141952.tif 000021
【図２０】
2012141952.tif 000022
【図２１】
2012141952.tif 000023
【図２２】
2012141952.tif 000024