JP2008305335A

JP2008305335A - 除算回路

Info

Publication number: JP2008305335A
Application number: JP2007154235A
Authority: JP
Inventors: Iwao Honda; 巌本田
Original assignee: Sanyo Electric Co Ltd; Sanyo Semiconductor Co Ltd
Current assignee: Sanyo Electric Co Ltd; System Solutions Co Ltd
Priority date: 2007-06-11
Filing date: 2007-06-11
Publication date: 2008-12-18
Also published as: US20080307032A1; CN101324836A; CN101324836B

Abstract

【課題】除算処理を高速に実行する。
【解決手段】被除数を除数で除算する除算回路であって、除数の２倍から２^ｍ−１（ｍは２以上の整数）倍までの２^ｍ−２個の除数の倍数である倍除数を生成する倍除数生成回路と、被除数から、除数及び２^ｍ−２個の倍除数の夫々を減じることにより、被除数に対する商を上位からｍビットずつ順に生成する商生成回路と、を備える。
【選択図】図１

Description

本発明は、除算回路に関する。

プロセッサで２進数の除算を行う方法として、加え戻し法や引き放し法が一般的に用いられている。加え戻し法や引き放し法の場合、被除数の上位ビットから順に除数を減じ、その減算結果に基づいて商が１ビットずつ求められていく（例えば、特許文献１）。
特開平１０−１６１８５４号公報

このように、加え戻し法や引き放し法の場合、商が１ビットずつしか得られないため、商として必要なビット数が増加するに連れて、商が求まるまでの処理時間が長くなってしまう。

本発明は上記課題を鑑みてなされたものであり、除算処理を高速に実行可能な除算回路を提供することを目的とする。

上記目的を達成するため、本発明の除算回路は、被除数を除数で除算する除算回路であって、前記除数の２倍から２^ｍ−１（ｍは２以上の整数）倍までの２^ｍ−２個の前記除数の倍数である倍除数を生成する倍除数生成回路と、前記被除数から、前記除数及び２^ｍ−２個の前記倍除数の夫々を減じることにより、前記被除数に対する商を上位からｍビットずつ順に生成する商生成回路と、を備えることとする。

除算処理を高速に実行可能な除算回路を提供することができる。

図１は、本発明の一実施形態である除算回路の構成を示す図である。除算回路は、レジスタ１０〜１２、倍除数生成回路１３、パイプラインレジスタ１４，１５、及び商生成回路１６を含んで構成されている。なお、本実施形態の除算回路は、ＣＰＵ（Central Processing Unit）等のプロセッサの一部として構成されている。

レジスタ１０〜１２は、それぞれ、除算における被除数、除数、商が格納される記憶領域である。これらのレジスタ１０〜１２は、例えば、プロセッサが備えるアキュムレータや汎用レジスタ、特殊レジスタ等である。

倍除数生成回路１３は、レジスタ１１に格納された除数を整数倍した数である倍除数を生成する。除算回路において商をｍ（２以上の整数）ビットずつ求めることとすると、倍除数生成回路１３では、除数の２倍から２^ｍ−１倍までの２^ｍ−２個の倍除数が生成される。図１に示す除算回路では、商を２ビットずつ求めることとしているため、倍除数生成回路１３では、除数の２倍から３倍までの倍除数が生成される。ここで、除数をｔ１とし、２倍，３倍の倍除数をｔ２，ｔ３と表すこととすると、ｔ１を１ビット左シフトすることにより、倍除数ｔ２が生成される。そして、ｔ１にｔ２を加算することにより、倍除数ｔ３が生成される。

パイプラインレジスタ１４，１５には、それぞれ、倍除数生成回路１３で生成された倍除数ｔ２，ｔ３が格納される。本実施形態におけるパイプラインレジスタ１４，１５は、他の処理によって内容が更新される汎用レジスタ等ではなく、除算処理専用のレジスタとして構成されている。

商生成回路１６は、レジスタ１０に格納された被除数ａｘと、パイプラインレジスタ１４，１５に格納された倍除数ｔ２，ｔ３とを用いて、被除数から除数ｔ１及び倍除数ｔ２，ｔ３のそれぞれを減じた結果ｒｅｓ１〜ｒｅｓ３を求める。そして、商生成回路１６では、減算結果ｒｅｓ１〜ｒｅｓ３に基づいて、被除数ａｘを除数ｔ１で除算して得られる商の一部となる２ビットの部分商が求められる。具体的には、減算結果ｒｅｓ３が正（０以上）の場合、部分商ｃは０ｂ１１となる。なお、０ｂは２進表記を示すものである。また、減算結果ｒｅｓ３が負（０未満）で、減算結果ｒｅｓ２が正の場合、部分商ｃは０ｂ１０となる。また、減算結果ｒｅｓ２が負で、減算結果ｒｅｓ１が正の場合、部分商ｃは０ｂ０１となる。また、減算結果ｒｅｓ１が負の場合、部分商ｃは０ｂ００となる。そして、商ｒｓの下位に部分商ｃが付加される。

また、部分商生成回路１６は、減算結果ｒｅｓ１〜ｒｅｓ３に基づいて、被除数ａｘ（被減数）を更新する。具体的には、減算結果ｒｅｓ１〜ｒｅｓ３が全て負の場合、被除数ａｘはそのままとなるが、減算結果ｒｅｓ１〜ｒｅｓ３に正のものがある場合、減算結果ｒｅｓ１〜ｒｅｓ３のうち正で最大のものが被除数ａｘとなる。

なお、本実施形態の除算回路を含むプロセッサは、パイプライン制御されており、実行ステージは、Ｅ１ステージ及びＥ２ステージの２つで構成されていることとする。そして、倍除数生成回路１３による倍除数の生成はＥ１ステージで実行され、商生成回路１６による商の生成はＥ２ステージで実行されることとする。

図２は、図１に示した除算回路による除算処理の一例を示す図である。ここでは、被除数ａｘが０ｂ０００１００１０であり、除数ｔ１が０ｂ０１００００００である。なお、ａｘ及びｔ１は固定小数点数であり、実数で表すと、ａｘ＝０．１４０６２５、ｔ１＝０．５である。

まず、商を２ビットずつ求めるために、被除数ａｘの下位に０ｂ０が付加され、被除数ａｘ（１）＝０ｂ０００１００１００となる。この被除数ａｘ（１）から除数ｔ１及び倍除数ｔ２，ｔ３のそれぞれを減じたｒｅｓ１〜ｒｅｓ３は全て負となる。したがって、部分商ｃ（１）は、０ｂ００となる。続いて、次の２ビットの部分商ｃを求めるため、被除数ａｘ（１）の下位に０ｂ００が付加され、被除数ａｘ（２）＝０ｂ１００１００００となる。この被除数ａｘ（２）に対しては、ｒｅｓ１，ｒｅｓ２が正、ｒｅｓ３が負となる。したがって、部分商ｃ（２）は、ｒｅｓ２に対応する０ｂ１０となる。さらに、次の２ビットの部分商ｃを求めるため、ｒｅｓ２の下位に０ｂ００が付加され、被除数ａｘ（３）＝０ｂ０１００００００００となる。この被除数ａｘ（３）に対しては、ｒｅｓ１が正、ｒｅｓ２，ｒｅｓ３が負となる。したがって、部分商ｃ（３）は、ｒｅｓ１に対応する０ｂ０１となる。これにより、部分商ｃ（１），ｃ（２），ｃ（３）を上位から順に並べた商ｒｓは、０ｂ００１００１（＝０．２８１２５）となる。このように、図１に示した除算回路を用いて商を２ビットずつ求めることにより、６ビットの商を３サイクルで算出することができる。

図３及び図４は、図１に示した除算回路の詳細構成例を示す図である。具体的には、図３は、倍除数生成回路１３の構成例を示す図であり、図１４は、商生成回路１６の構成例を示す図である。

図３に示すように、倍除数生成回路１３は、連接拡張回路２０〜２５、セレクタ２６、連接回路２７，２８、及び加算回路２９を含んで構成されている。また、レジスタ１０＿１，１０＿２は、被除数が格納されるレジスタ１０に対応し、レジスタ１１＿０〜１１＿３は、除数が格納されるレジスタ１１に対応する。なお、図中の［ｘ：ｙ］は、データのビット範囲を示すものである。例えば、［３１：０］は、０ビット目から３１ビット目までの３２ビットのデータを示している。本実施形態では、レジスタ１１＿０〜１１＿３，１０＿１，１０＿２の何れか一つに除数ｔ１が格納される。

連接拡張回路２０は、レジスタ１１＿０に格納された３２ビットのデータｒ０の下位に０ｂ０を付加するとともに、ｒ０［３１］を８ビット分ｒ０の上位に付加し、４１ビットのデータｒ０＿ｓｅを出力する。すなわち、ｒ０＿ｓｅ［４０：０］＝｛ｒ０［３１］，…，ｒ０［３１］，ｒ０［３１：０］，０ｂ０｝となる。連接拡張回路２１〜２５も同様に、レジスタ１１＿１〜１１＿３，１０＿１，１０＿２に格納されたデータｒ１〜ｒ３，ａｘ，ｂｘの下位３２ビットから、４１ビットのデータｒ１＿ｓｅ〜ｒ３＿ｓｅ，ａｘ＿ｒ，ｂｘ＿ｒを生成して出力する。

セレクタ２６は、連接拡張回路２０〜２５から出力される６つのデータと、４１ビット全てがゼロのデータとが入力されており、３ビットの選択信号ｓｅｌ１に応じた１つの４１ビットのデータを出力する。例えば、ｓｅｌ１が０ｂ０００の場合はｒ０＿ｓｅが出力され、ｓｅｌ１が０ｂ００１の場合はｒ１＿ｓｅが出力される。なお、セレクタ２６から出力されるデータＬ＿ｄｉｖ２は、下位１ビットに０ｂ０が付加されているため、除数ｔ１を２倍した倍除数ｔ２となっている。

連接回路２７は、Ｌ＿ｄｉｖ２［４０：１］の上位に１ビットのＬ＿ｄｉｖ２［４０］を付加した４１ビットのデータＬ＿ｄｉｖ１を出力する。すなわち、Ｌ＿ｄｉｖ１は、倍除数ｔ２を１／２倍した除数ｔ１となっている。連接回路２８は、Ｌ＿ｄｉｖ２［４０：０］の上位に１ビットのＬ＿ｄｉｖ２［４０］を付加した４２ビットのデータを、倍除数ｔ２としてパイプラインレジスタ１４に出力する。

加算回路１５は、Ｌ＿ｄｉｖ２にＬ＿ｄｉｖ１を加算して得られる４１ビットのデータを、倍除数ｔ３としてパイプラインレジスタ１５に出力する。

図４に示すように、商生成回路１６は、セレクタ４０〜４６、連接回路４７〜４９、反転回路５０，５１、加算回路５２〜５４、及びデマルチプレクサ５５を含んで構成されている。本実施形態では、レジスタ１０＿１，１０＿２の何れかに被除数が格納される。

セレクタ４０は、レジスタ１０＿１，１０＿２に格納されている２つのデータａｘ，ｂｘのうち、１ビットの選択信号ｓｅｌ２に応じた１つのデータを出力する。本実施形態では、選択信号ｓｅｌ２が０ｂ０の場合にレジスタ１０＿１に格納されているａｘが出力され、選択信号ｓｅｌが０ｂ１の場合にレジスタ１０＿２に格納されているｂｘが出力される。

連接回路４７は、セレクタ４０から出力される４０ビットのデータの下位に０ｂ０を付加し、４１ビットのデータｄｓｔとして出力する。ここで０ｂ０が付加されるのは、商を２ビットずつ生成するためである。そして、ｄｓｔが、減算処理において除数または倍除数を減じる際の被減数となる。

反転回路５０は、レジスタ１４に格納されている４２ビットの倍除数ｔ２の全ビットを反転させて出力する。したがって、反転回路５０から出力される４２ビットのデータの上位４１ビットであるｄｉｖ１は、除数ｔ１の１の補数となっており、下位４１ビットであるｄｉｖ２は、倍除数ｔ２の１の補数となっている。反転回路５１は、レジスタ１５に格納されている４１ビットの倍除数ｔ３の全ビットを反転させて出力する。したがって、反転回路５１から出力される４１ビットのデータであるｄｉｖ３は、倍除数ｔ３の１の補数となっている。

加算回路５２は、ｄｓｔ、ｄｉｖ１、及び０ｂ１を加算して出力する。すなわち、加算回路５２から出力される４１ビットのデータｔ＿ｒｅｓｕｌｔ１は、被減数であるｄｓｔから除数ｔ１を減じた結果となる。同様に、加算回路５３，５４は、ｄｓｔから倍除数ｔ２，ｔ３を減じた結果ｔ＿ｒｅｓｕｌｔ２，ｔ＿ｒｅｓｕｌｔ３を出力する。

セレクタ４１には、部分商の候補となる０ｂ０１，０ｂ００が入力されており、加算回路５２から出力される減算結果ｔ＿ｒｅｓｕｌｔ１の最上位ビットに応じて、何れか一方がｒｓ＿ｌｓ１として出力される。本実施形態では、ｔ＿ｒｅｓｕｌｔ１［４０］が０の場合（減算結果が正の場合）、０ｂ０１がｒｓ＿ｌｓ１として出力され、ｔ＿ｒｅｓｕｌｔ１［４０］が１の場合（減算結果が負の場合）、０ｂ００がｒｓ＿ｌｓ１として出力される。セレクタ４２には、部分商の候補となる０ｂ１０と、セレクタ４１の出力ｒｓ＿ｌｓ１とが入力されており、減算結果ｔ＿ｒｅｓｕｌｔ２が正の場合には０ｂ１０がｒｓ＿ｌｓ２として出力され、減算結果ｔ＿ｒｅｓｕｌｔ２が負の場合にはｒｓ＿ｌｓ１がｒｓ＿ｌｓ２として出力される。セレクタ４３には、部分商の候補となる０ｂ１１と、セレクタ４２の出力ｒｓ＿ｌｓ２とが入力されており、減算結果ｔ＿ｒｅｓｕｌｔ３が正の場合には０ｂ１１が２ビットの部分商であるｒｓ＿ｌｓとして出力され、減算結果ｔ＿ｒｅｓｕｌｔ３が負の場合にはｒｓ＿ｌｓ２がｒｓ＿ｌｓとして出力される。すなわち、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３が全て負の場合は、０ｂ００が部分商ｒｓ＿ｌｓとして出力され、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３に正のものがある場合は、減算結果が最大となる除数ｔ１または倍除数ｔ２，ｔ３の除数ｔ１に対する倍数を示す２ビットのデータが部分商ｒｓ＿ｌｓとして出力される。例えば、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３が全て正の場合、除数ｔ１及び倍除数ｔ２，ｔ３のうち最大である倍除数ｔ３は除数ｔ１の３倍であるため、３を示す２ビットの０ｂ１１が部分商ｒｓ＿ｌｓとして出力される。

連接回路４８は、レジスタ１２に格納されている３２ビットの商ｒｓの下位３０ビットに、セレクタ４３から出力される２ビットの部分商ｒｓ＿ｌｓを付加したデータを、３２ビットの商ｒｓとしてレジスタ１２に格納する。

セレクタ４４には、減算結果ｔ＿ｒｅｓｕｌｔ１と、被減数ｄｓｔとが入力されており、加算回路５２から出力される減算結果ｔ＿ｒｅｓｕｌｔ１の最上位ビットに応じて、何れか一方がｒｅｓｕｌｔ１として出力される。本実施形態では、ｔ＿ｒｅｓｕｌｔ１［４０］が０の場合（減算結果が正の場合）、ｔ＿ｒｅｓｕｌｔ１がｒｅｓｕｌｔ１として出力され、ｔ＿ｒｅｓｕｌｔ１［４０］が１の場合（減算結果が負の場合）、ｄｓｔがｒｅｓｕｌｔ１として出力される。セレクタ４５には、減算結果ｔ＿ｒｅｓｕｌｔ２と、セレクタ４４から出力されるｒｅｓｕｌｔ１とが入力されており、減算結果ｔ＿ｒｅｓｕｌｔ２が正の場合にはｔ＿ｒｅｓｕｌｔ２がｒｅｓｕｌｔ２として出力され、減算結果ｔ＿ｒｅｓｕｌｔ２が負の場合にはｒｅｓｕｌｔ１がｒｅｓｕｌｔ２として出力される。セレクタ４６には、減算結果ｔ＿ｒｅｓｕｌｔ３と、セレクタ４５から出力されるｒｅｓｕｌｔ２とが入力されており、減算結果ｔ＿ｒｅｓｕｌｔ３が正の場合にはｔ＿ｒｅｓｕｌｔ３がｔ＿ｒｅｓｕｌｔとして出力され、減算結果ｔ＿ｒｅｓｕｌｔ３が負の場合にはｒｅｓｕｌｔ２がｔ＿ｒｅｓｕｌｔとして出力される。すなわち、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３が全て負の場合にはｄｓｔがｔ＿ｒｅｓｕｌｔとして出力され、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３に正のものがある場合は、正のうち最小の減算結果がｔ＿ｒｅｓｕｌｔとして出力される。

連接回路４９は、セレクタ４６から出力されるｔ＿ｒｅｓｕｌｔの下位３９ビットに０ｂ０を付加して得られる４０ビットのデータをｒｅｓｕｌｔとして出力する。

デマルチプレクサ５５は、入力されるｒｅｓｕｌｔを、セレクタ４０の場合と同じ選択信号ｓｅｌ２に応じて、レジスタ１０＿１，１０＿２の何れか一方に出力する。本実施形態では、選択信号ｓｅｌ２が０ｂ０の場合にｒｅｓｕｌｔがレジスタ１０＿１に出力され、選択信号ｓｅｌ２が０ｂ１の場合にｒｅｓｕｌｔがレジスタ１０＿２に出力される。すなわち、デマルチプレクサ５５からの出力により、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３に応じて被除数が更新されることとなる。そして、被除数が更新されると、連接回路４７から出力される被減数ｄｓｔも更新されることとなる。

なお、反転回路５０，５１及び加算回路５２〜５４により構成される回路が、本発明の減算回路に相当する。また、セレクタ４１〜４３により構成される回路が、本発明の部分商生成回路及び部分商選択回路に相当する。また、セレクタ４４〜４６及び連接回路４７，４９により構成される回路が、本発明の被減数更新回路に相当する。そして、セレクタ４４〜４６により構成される回路が、本発明の減算結果選択回路に相当し、連接回路４７，４９により構成される回路が、本発明の被減数生成回路に相当する。

図５は、図４に示した除算回路の動作の一例を示すタイミングチャートである。図５において、ＣＬＫは除算回路の動作クロックを示している。また、図５の例では、被除数はレジスタ１０＿１に格納されたａｘであり、除数はレジスタ１１＿０に格納されたｒ０であることとする。なお、図５に示す数は１６進表記であり、“＿”は下位から１６ビットごとの区切りを表している。例えば、被除数ａｘ［３９：０］の初期値１２３４＿５６７８は、ａｘ［３９：０］の下位３２ビットが、０ｘ１２３４５６７８であることを示している。また、除数ｒ０［３１：０］の４０００＿００００は、ｒ０［３１：０］が０ｘ４０００００００であることを示している。なお、０ｘは１６進表記を示すものである。そして、被除数ａｘ及び除数ｔ１は固定小数点数であり、実数で表すと、ａｘ＝０．１４２２２２２２１９４０７５５８４４１１６２１０９３７５、ｔ１＝０．５となる。

除数ｒ０が４０００＿００００であるため、時刻Ｔ０に、ｄｉｖ１，ｄｉｖ２，ｄｉｖ３が１ｆｆ＿ｂｆｆｆ＿ｆｆｆｆ，１ｆｆ＿７ｆｆｆ＿ｆｆｆｆ，１ｆｆ＿３ｆｆｆ＿ｆｆｆｆとなる。また、ａｘが１２３４＿５６７８であるため、時刻Ｔ０に、ｄｓｔが２４６８＿ａｃｆ０となる。このとき、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３は全て負となるため、部分商ｒｓ＿ｌｓは０（０ｂ００）となる。したがって、時刻Ｔ２に、商ｒｓは０（ｒｓ［１：０］＝０ｂ００）となる。また、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３が全て負であるため、時刻Ｔ０において、ｔ＿ｒｅｓｕｌｔは２４６８＿ａｃｆ０（ｄｓｔ）となり、ｒｅｓｕｌｔは４８ｄ１＿５９ｅ０となる。したがって、時刻Ｔ１に、ａｘが４８ｄ１＿５９ｅ０となり、ｄｓｔが９１ａ２＿ｂ３ｃ０となる。

時刻Ｔ１にｄｓｔが９１ａ２＿ｂ３ｃ０になると、減算結果ｔ＿ｒｅｓｕｌｔ１〜ｔ＿ｒｅｓｕｌｔ３は、順に、５１ａ２＿ｂ３ｃ０，１１ａ２＿ｂ３ｃ０，１ｆｆ＿ｄ１ａ２＿ｂ３ｃ０となる。つまり、減算結果ｔ＿ｒｅｓｕｌｔ１，ｔ＿ｒｅｓｕｌｔ２が正、減算結果ｔ＿ｒｅｓｕｌｔ３が負となっている。したがって、部分商ｒｓ＿ｌｓは、正で最小の減算結果ｔ＿ｒｅｓｕｌｔ２に対応する２（０ｂ１０）となる。したがって、時刻Ｔ２に、商ｒｓは２（ｒｓ［３：０］＝０ｂ００１０）となる。また、正で最小の減算結果ｔ＿ｒｅｓｕｌｔ２である１１ａ２＿ｂ３ｃ０がｔ＿ｒｅｓｕｌｔとなり、ｒｅｓｕｌｔは２３４５＿６７８０となる。したがって、時刻Ｔ２に、ａｘが２３４５＿６７８０となり、ｄｓｔが４６８ａ＿ｃｆ００となる。

そして、２ビットずつ商を求めて行く処理が繰り返されることにより、時刻Ｔ１６に、３２ビットの商ｒｓとなる２４６８＿ａｃｆ０が得られる。実数で表すと、ｒｓ＝０．２８４４４４４３８８１５１１６８８２３２４２となる。

このように、除数の２倍から２^ｍ−１（ｍは２以上の整数：本実施形態ではｍ＝２）倍までの２^ｍ−２個の倍除数を生成し、被除数から除数及び倍除数のそれぞれを減じることにより、商をｍビットずつ順に生成していくことができる。したがって、商を１ビットずつ順に生成していく場合と比較して、除算処理を高速に実行することが可能となる。

そして、図４に示したように、被除数の高次からｎビット（ｎは２以上の整数：本実施形態ではｎ＝４１）を被減数ｄｓｔとし、被減数から除数及び倍除数のそれぞれを減じた２^ｍ−１個の減算結果に基づいてｍビットの部分商を求め、次のｍビットの部分商が求められるように被減数ｄｓｔを更新する構成とすることができる。

また、２^ｍ−１個の減算結果に基づいて、減算結果が全て負の場合はｍビットのゼロを部分商として出力し、減算結果に正が含まれる場合は、減算結果が正のうち、最大の除数又は倍除数の除数に対する倍数を示すｍビットの数を部分商として出力する構成とすることができる。例えば、図１において、減算結果ｒｅｓ１〜ｒｅｓ３が全て負の場合は０ｂ００が部分商として出力され、減算結果ｒｅｓ１，ｒｅｓ２が正、減算結果ｒｅｓ３が負の場合は、減算結果が正のうち最大の倍除数であるｔ２が除数ｔ１の２倍であるため、０ｂ１０が部分商として出力される。

また、被減数ｄｓｔを更新する回路は、減算結果に基づいて被減数または減算結果の何れかを出力し、出力される被減数または減算結果の下位ｎ−ｍビットにｍビットを付加したｎビットの数を被減数として出力する構成とすることができる。

なお、上記実施例は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更、改良され得ると共に、本発明にはその等価物も含まれる。

例えば、本実施形態では、ｍ＝２として商を２ビットずつ求めることとしたが、商を求める単位は２ビットに限られない。例えば、図６に示すように、除数ｔ１の２倍から１５倍の倍除数ｔ２〜ｔ１５を生成し、被除数から序数ｔ１及び倍除数ｔ２〜ｔ１５を減じた結果ｒｅｓ１〜１５に基づいて、商を４ビットずつ求めることとしてもよい。

本発明の一実施形態である除算回路の構成を示す図である。除算回路による除算処理の一例を示す図である。倍除数生成回路の構成例を示す図である。商生成回路の構成例を示す図である。除算回路の動作の一例を示すタイミングチャートである。商を４ビットずつ求める場合の除算回路の構成例を示す図である。

符号の説明

１０〜１２レジスタ
１３倍除数生成回路
１４，１５パイプラインレジスタ
１６商生成回路

Claims

被除数を除数で除算する除算回路であって、
前記除数の２倍から２^ｍ−１（ｍは２以上の整数）倍までの２^ｍ−２個の前記除数の倍数である倍除数を生成する倍除数生成回路と、
前記被除数から、前記除数及び２^ｍ−２個の前記倍除数の夫々を減じることにより、前記被除数に対する商を上位からｍビットずつ順に生成する商生成回路と、
を備えることを特徴とする除算回路。
請求項１に記載の除算回路であって、
前記除数及び前記倍除数はｎ（ｎは２以上の整数）ビットであり、
前記商生成回路は、
前記被除数の高次からｎビットを被減数とし、前記除数及び２^ｍ−２個の前記倍除数の夫々を減数として、２^ｍ−１個の減算結果を出力する減算回路と、
２^ｍ−１個の前記減算結果に基づいて、前記被除数に対する商の一部であるｍビットの部分商を生成する部分商生成回路と、
前記被除数及び２^ｍ−１個の前記減算結果に基づいて、前記被除数に対する次のｍビットの部分商を生成すべく、前記減算回路における前記被減数を更新する被減数更新回路と、
を含んで構成されることを特徴とする除算回路。
請求項２に記載の除算回路であって、
前記部分商生成回路は、
２^ｍ−１個の前記減算結果に基づいて、前記減算結果が全て負の場合はｍビットのゼロを前記部分商として出力し、前記減算結果に正が含まれる場合は前記減算結果が正のうち最大の前記除数又は前記倍除数の前記除数に対する倍数を示すｍビットの数を前記部分商として出力する部分商選択回路を含んで構成されることを特徴とする除算回路。
請求項２又は３に記載の除算回路であって、
前記被減数更新回路は、
前記減算結果が全て負の場合は、前記被減数を出力し、前記減算結果に正が含まれる場合は前記減算結果のうち正の最小の減算結果を出力する減算結果選択回路と、
前記減算結果選択回路から出力されるｎビットの前記被減数又は前記減算結果の下位ｎ−ｍビットに、前記被除数の前記ｎビットに続くｍビットを付加したｎビットの数を前記被減数として出力する被減数生成回路と、
を含んで構成されることを特徴とする除算回路。