(57)【要約】【課題】遅延時間を短縮したブース乗算器を提供する。【解決手段】乗算方法あるいは乗算装置が提供される。この方法あるいは装置は、基数２の乗数を、基数４の符号化されたビットの組に変換する。符号化されたビットの組は、−２、−１、−０、１、２のいずれかを表現したものであり、第１のビットは、表現する数が２のときに真値（すなわち１）となり、第２のビットは、表現する数が−２のときに真値となり、第３のビットは、表現する数が負または０のとき真値となり、第４のビットは、表現する数の絶対値が１のとき真値となる。【選択図】図３
2007234004.tif 000002
【特許請求の範囲】
【請求項１】
乗数に含まれるビットの組を受け、基数２から基数４に変換して、−２、−１、０、１、２のいずれかの数を表現する符号化されたビットの組を生成する複数の論理ゲートを含む符号化回路を備え、
前記符号化されたビットの組は、
表現する数が２のときに真値となる第１のビットと、
表現する数が−２のときに真値となる第２のビットと、
表現する数が負または０のとき真値となる第３のビットと、
表現する数の絶対値が１のとき真値となる第４のビットと、
を含むことを特徴とする装置。
【請求項２】
前記符号化回路は、
前記乗数に含まれる３ビットＹｉ、Ｙｊ、Ｙｋを受け、前記符号化されたビットの組の前記第１のビットＢ１を生成する第１回路と、
前記乗数の前記ビットＹｉ、Ｙｊ、Ｙｋを受け、前記符号化されたビットの組の前記第２のビットＢ２を生成する第２回路と、
前記乗数の前記ビットＹｉを受け、前記符号化されたビットの組の前記第３のビットＢ３を生成する第３回路と、
前記乗数の前記ビットＹｊ、Ｙｋを受け、前記符号化されたビットの組の前記第４のビットＢ４を生成する第４回路と、
を含むことを特徴とする請求項１に記載の装置。
【請求項３】
前記第１回路は、以下の真理値表に従った論理演算を実行する論理ゲートを含むことを特徴とする請求項２に記載の装置。
【表１】
2007234004.tif 000004
【請求項４】
前記第２回路は、以下の真理値表に従った論理演算を実行する論理ゲートを含むことを特徴とする請求項２または３に記載の装置。
【表２】
2007234004.tif 000005
【請求項５】
前記第３回路は、以下の真理値表に従った論理演算を実行する論理ゲートを含むことを特徴とする請求項２から４のいずれかに記載の装置。
【表３】
2007234004.tif 000006
【請求項６】
前記第４回路は、以下の真理値表に従った論理演算を実行する論理ゲートを含むことを特徴とする請求項２から５のいずれかに記載の装置。
【表４】
2007234004.tif 000007
【請求項７】
前記乗数のビット数をＮ（Ｎは自然数）とするとき、Ｎ／２個の符号化回路を備え、
各符号化回路は、最後の符号化回路を除いて、前記乗数の３ビットの組であって互いに異なる組を受け、前記最後の符号化回路は２ビットの組と、ヌルビットを受けることを特徴とする請求項２から６のいずれかに記載の装置。
【請求項８】
前記乗数は、ビットＹ０、Ｙ１、Ｙ２、Ｙ３…ＹＮ−１を含み、
第ｐ番目（ｐは、１≦ｐ≦Ｎ−１を満たす整数）の符号化回路は、ビットＹ（ｐ−１）×２、Ｙ（ｐ−１）×２＋１、Ｙ（ｐ−１）×２＋２を受け（、第Ｎ番目の符号化回路はビットＹ（ｐ−１）×２、Ｙ（ｐ−１）×２＋１およびヌルビットを受け）ることを特徴とする請求項７に記載の装置。
【請求項９】
複数のセレクタ回路をさらに備え、各セレクタ回路は、
前記符号化回路からの前記符号化されたビットと、被乗数に含まれるビットの組とを受け、部分積の各ビットを生成することを特徴とする請求項１に記載の装置。
【請求項１０】
各セレクタ回路は、前記被乗数に含まれる２ビットの組Ａｉ、Ａｊを受け、部分積の各ビットを生成し、
各セレクタ回路は、符号化されたビットの第１、第２、第３、第４のビットをＢ１、Ｂ２、Ｂ３、Ｂ４とするとき、論理式
Ｓｉ＝（Ｂ１  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ２  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ４  ＮＡＮＤ  （Ｂ３  ＸＯＲ  Ａｉ））
に従って各ビットＳｉを生成する複数の論理ゲートを含むことを特徴とする請求項９に記載の装置。
【請求項１１】
乗数を符号化したビットの組と被乗数に含まれるビットの組とを受け、部分積の各ビットを生成するセレクタ回路を備え、
前記乗数を符号化したビットは、基数２から基数４へ変換されており、基数４の数は、−２、−１、０、１、２のいずれかの数を表現しており、
前記乗数を符号化したビットの組は、
表現する数が２のときに真値となる第１のビットと、
表現する数が−２のときに真値となる第２のビットと、
表現する数が負または０のとき真値となる第３のビットと、
表現する数の絶対値が１のとき真値となる第４のビットと、
を含むことを特徴とする装置。
【請求項１２】
各セレクタ回路は、前記被乗数に含まれる２ビットの組Ａｉ、Ａｊを受け、部分積の各ビットＳｉを生成し、
前記乗数を符号化した第１から第４のビットをＢ１、Ｂ２、Ｂ３、Ｂ４とするとき、各セレクタ回路は、論理式
Ｓｉ＝（Ｂ１  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ２  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ４  ＮＡＮＤ  （Ｂ３  ＸＯＲ  Ａｉ））
に従って各ビットＳｉを生成する複数の論理ゲートを含むことを特徴とする請求項１１に記載の装置。
【請求項１３】
前記被乗数のビット数をＭ（Ｍは自然数）とするとき、Ｍ個のセレクタ回路を備え、
各符号化回路は、最後のセレクタ回路を除いて、それぞれ異なる前記被乗数に含まれる２ビットの組を受け、前記最後のセレクタ回路は前記被乗数の１ビットおよびヌルビットを受けることを特徴とする請求項１１に記載の装置。
【請求項１４】
前記被乗数は、ビットＡ０、Ａ１、Ａ２、Ａ３、…ＡＭ−１（Ｍは整数）を含み、
第ｐ番目（ｐは、１≦ｐ≦Ｍ−１を満たす整数）の前記セレクタ回路はビットＡｐ−１、Ａｐを受け（、第Ｍ番目の前記セレクタ回路は、ビットＡＭ−１およびヌルビットを受け）ることを特徴とする請求項１３に記載の装置。
【請求項１５】
ある符号化されたビットの組に対する出力ビットＳｉの集合は、前記乗数と前記被乗数の部分積となり、
前記部分積の合計は、前記乗数および前記被乗数の積となることを特徴とする請求項１４に記載の装置。
【請求項１６】
基数２の乗数を、−２、−１、０、１、２のいずれかの数を表現する符号化されたビットの組に変換するステップを備え、
前記符号化されたビットの組は、
表現する数が２のときに真値となる第１のビットと、
表現する数が−２のときに真値となる第２のビットと、
表現する数が負または０のとき真値となる第３のビットと、
表現する数の絶対値が１のとき真値となる第４のビットと、
を含むことを特徴とする方法。
【請求項１７】
前記第１、第２、第３、第４の符号化されたビットＢ１、Ｂ２、Ｂ３、Ｂ４を、以下の真理値表に従って生成することを特徴とする請求項１６に記載の方法。
【表５】
2007234004.tif 000008
【請求項１８】
前記乗数に含まれる３ビットの組それぞれを、符号化されたビットに変換するステップをさらに備え、
前記乗数は、ビットＹ０、Ｙ１、Ｙ２、Ｙ３…ＹＮ−１を含み、
第ｐ番目（ｐは、１≦ｐ≦Ｎ−１を満たす整数）の前記３ビットの組はビットＹ（ｐ−１）×２、Ｙ（ｐ−１）×２＋１、Ｙ（ｐ−１）×２＋２を含（み、第Ｎ番目の組は、Ｙ（ｐ−１）×２、Ｙ（ｐ−１）×２＋１およびヌルビットを含）むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記符号化されたビットの組と、前記乗数に含まれるビットの組とを受けるステップと、
部分積の各ビットを生成するステップと、
をさらに備えることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記被乗数に含まれる２ビットの組Ａｉ、Ａｊと、符号化された第１から第４のビットＢ１、Ｂ２、Ｂ３、Ｂ４とを受けるステップと、
部分積の各ビットＳｉを、論理式
Ｓｉ＝（Ｂ１  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ２  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ４  ＮＡＮＤ  （Ｂ３  ＸＯＲ  Ａｉ））
に従って生成するステップと、
をさらに備えることを特徴とする請求項１６に記載の方法。
【請求項２１】
前記被乗数は、ビットＡ０、Ａ１、Ａ２、Ａ３、…ＡＭ−１を含み、
前記被乗数に含まれる第ｐ番目（ｐは、１≦ｐ≦Ｍ−１を満たす整数）のビットの組は、ビットＡｐ−１、Ａｐを含み、（第Ｍ番目の組は、ビットＡＭ−１、ヌルビットを含む）ことを特徴とする請求項２０に記載の方法。
【請求項２２】
それぞれの符号化されたビットの組に対するビットＳｉの集合を生成し、前記乗数と前記被乗数の部分積を生成するステップをさらに備えることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記乗数と前記被乗数の積を生成するために、前記部分積を加算するステップをさらに備えることを特徴とする請求項２２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２進数をブース乗算器を利用して乗算する装置および方法に関する。
【背景技術】
【０００２】
情報処理システム等によって実行される多くの処理は、２進数の乗算を必要とする。乗算関数では、被乗数（multiplicand）と乗数（multiplier）が存在する。よく知られるように、２進数の乗算は、まず、被乗数が乗数の第１ビットと掛け合わされる。つづいて、被乗数が乗数の第２ビットと掛け合わされ、その結果得られた値が、１桁シフトされて、積同士が加算される。このプロセスが、乗数のすべてのビットが被乗数と掛け合わせられるまで繰り返される。
【０００３】
被乗数と、乗数のある１ビットとを掛け合わせて得られる積は、部分積と呼ばれる。最終的な積は、もっとも右の桁から左の桁へと桁上げしながら、部分積を積算することにより生成される。このプロセスは、部分積積算（partial product accumulation）と呼ばれる。このプロセスは、意図した目的を達成するためによく機能するが、ハードウェアを利用してこの処理を実装する場合、非常に多くの論理ゲートおよびその他の回路が必要とされるという深刻な欠点が存在する。結果として、ハードウェアを用いてこのプロセスを実装する場合、非常に多くの費用がかかり、とくに多くのビット数を演算する場合には、処理速度が遅くなってしまう。
【０００４】
２進数の乗数と、２進数の被乗数を掛け合わせて生成される部分積の個数を減らすことにより、処理速度の高速化を図るために、乗算器にブース符号化アルゴリズムあるいはブース符号化方法を利用する手法が知られている。部分積の個数を減らすために、ブース符号化アルゴリズムは、基数２の乗数Ｙを、符号化されたデジタル値の集合｛−２、−１、−０、１、２｝のいずれかの数を表現する基数４の乗数Ｚに再コード化し、その結果として、部分積の個数を１／２とする。ブース乗算は、一般的にいくつかの符号化器とセレクタで構成される。符号化器は、基数２の乗数に含まれるビットの組を、基数４の符号化されたビットの組に変換する。セレクタは、乗算器として機能し、各セレクタは基数２の被乗数をビットの組ごとに受け、基数２の乗数に含まれるビットの組は、セレクタビットとして利用される。基数２の乗数に含まれるあるビットの組に対して、各セレクタからの出力の集合は、部分積となる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このアルゴリズムは、冗長な記数法を利用することにより、部分積の個数を減少させることができる一方、従来のブース乗算回路の符号化器およびセレクタは、それぞれの機能を実現するために多くの論理ゲートを必要とする（従来のブース符号化器およびセレクタの例については後述する）。結果として、乗算器を通過する際に、信号の伝搬遅延が発生するという問題がある。
【０００６】
本発明は、かかる課題に鑑みてなされたものであり、その目的のひとつは、遅延時間を短縮したブース乗算器の提供にある。
【課題を解決するための手段】
【０００７】
本発明のある態様によれば、乗算方法あるいは乗算装置が提供される。この方法あるいは装置は、基数２の乗数（基数を２とする表現）を、基数４（基数を４とする表現）の符号化されたビットの組に変換する。符号化されたビットの組は、−２、−１、−０、１、２のいずれかを表現したものであり、第１のビットは、表現する数が２のときに真値（すなわち１）となり、第２のビットは、表現する数が−２のときに真値となり、第３のビットは、表現する数が負または０のとき真値となり、第４のビットは、表現する数の絶対値が１のとき真値となる。
【０００８】
ある態様の方法もしくは装置は、符号化されたビットの組の第１から第４のビットを、以下の真理値表にもとづいて生成してもよい。なお、本明細書において、ｊ＝ｉ＋１、ｋ＝ｉ＋２である。
【０００９】
【表１】
2007234004.tif 000003
【００１０】
ある態様の方法もしくは装置は、乗数に含まれるビットの組それぞれを、符号化されたビットの組に変換してもよい。ビットの組は、最後のものを除き、３ビットを含み、最後のビットの組は、２ビットとヌルビットを含んでもよい。乗数は、ビットＹ０、Ｙ１、Ｙ２、Ｙ３…ＹＮ−１を含み、第１の３ビットの組は、Ｙ０、Ｙ１、Ｙ２を含み、第２の３ビットの組はＹ２、Ｙ３、Ｙ４を含み、以下、各組は同様に構成されていてもよい。すなわち、第ｐ番目（ｐは、１≦ｐ≦Ｎ−１を満たす整数）の３ビットの組は、ビットＹ（ｐ−１）×２、Ｙ（ｐ−１）×２＋１、Ｙ（ｐ−１）×２＋２を含み、第Ｎ番目の符号化回路はビットＹ（Ｎ−１）×２、Ｙ（Ｎ−１）×２＋１およびヌルビットを含んでもよい。
【００１１】
ある態様の方法もしくは装置は、符号化されたビットの組と、乗数に含まれるビットの組とを受け、部分積の各ビットを生成してもよい。
【００１２】
ある態様の方法もしくは装置は、被乗数に含まれる２ビットの組Ａｉ、Ａｊと、符号化された第１から第４のビットＢ１、Ｂ２、Ｂ３、Ｂ４とを受け、部分積の各ビットＳｉを、論理式
Ｓｉ＝（Ｂ１  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ２  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ４  ＮＡＮＤ  （Ｂ３  ＸＯＲ  Ａｉ））
に従って生成してもよい。
たとえば、被乗数が、ビットＡ０、Ａ１、Ａ２、Ａ３、…ＡＭ−１を含むとき、第１番目の２ビットの組はＡ０、Ａ１を含み、第２番目の２ビットの組はＡ１、Ａ２を含み、第３番目の２ビットの組はＡ２、Ａ３を含み、以下、各組は同様に構成されてもよい。すなわち、被乗数に含まれる第ｐ番目（ｐは、１≦ｐ≦Ｍ−１を満たす整数）のビットの組は、ビットＡｐ−１、Ａｐを含み、第Ｍ番目の組は、ビットＡＭ−１、ヌルビットを含んでもよい。
なお、本明細書において、ＮＡＮＤ（！ＡＮＤ）は、否定論理積を、ＸＯＲは、排他的論理和を表すものとする。
【００１３】
ある態様の方法もしくは装置は、それぞれの符号化されたビットの組に対するビットＳｉの集合を生成し、乗数と被乗数の部分積を生成してもよい。さらに、乗数と被乗数の積を生成するために、部分積を加算してもよい。
【００１４】
なお、以上の構成要素の任意の組合せや、本発明の構成要素や表現を、方法、装置、システムなどの間で相互に置換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１５】
本発明によれば、ブース乗算器の遅延時間を短縮することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明を好適な実施の形態をもとに図面を参照しながら説明する。各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付するものとし、適宜重複した説明は省略する。また、実施の形態は、発明を限定するものではなく例示であって、実施の形態に記述されるすべての特徴やその組み合わせは、必ずしも発明の本質的なものであるとは限らない。
【００１７】
図１は、２進数の積に関連する部分積を生成する実施の形態に係る乗算回路１００の構成を示すブロック図である。乗算回路１００は、少なくともひとつの符号化回路１０２（説明のため４つの符号化回路が図示される）と、複数のセレクタ回路１０４（説明のために８つのセレクタ回路が図示される）を備える。
【００１８】
符号化回路１０２は、それぞれ、２進数に含まれるビットＹｉで構成されるビットの組１０６を、各ビットの組ごとに基数４の符号化されたビットＢｉに変換し、信号線１０８に出力する。具体的には、信号線１０８Ａ〜１０８Ｄ上の符号化されたそれぞれのビットは、｛−２、−１、−０、１、２｝からなる集合のいずれかの数を表現する。好ましい実施の形態では、各符号化回路１０２は、２進数の乗数に含まれる３ビットづつの組を受け、基数が４である４つの符号化されたビットを信号線１０８上に生成する。符号化回路１０２の入力および出力に関する詳細は、後述する。
【００１９】
セレクタ回路１０４は、それぞれ、信号線１０８上の符号化されたビットの組を受けるとともに、被乗数および乗数の部分積の各ビットを生成するために、被乗数に含まれるビットの組１１０を受ける。好ましい実施の形態において、各セレクタ回路１０４は、対応する符号化回路１０２から信号線１０８を介して符号化されたビットの組を受け、それを利用して被乗数に含まれるビットの組１１０に処理を施し、部分積の１ビットＳｉを生成する。図１に示されるように、４つの符号化されたビットの組それぞれは、複数のセレクタ回路１０４にそれぞれ入力され、各セレクタ回路１０４は、４つの部分積のあるビットＳｉを生成する。部分積の和は、乗数および被乗数の積となる。
【００２０】
好ましい実施の形態において、乗算回路１００は、Ｎ／２個の符号化回路１０２を含む。ここで、Ｎは、乗数のビット数である。したがって、たとえば、８ビットの乗数（Ｙ０、Ｙ１、Ｙ２、Ｙ３、Ｙ４、Ｙ５、Ｙ６、Ｙ７）に対しては、４つの符号化回路１０２Ａ〜１０２Ｄが利用される。さらに、それぞれの符号化回路１０２は、乗数に含まれる３ビットの組（Ｙｉ、Ｙｊ、Ｙｋ）であってそれぞれ異なる組を受ける。たとえば、符号化回路１０２は、乗数のビットＹ０、Ｙ１、Ｙ２を受ける。符号化回路１０２Ｂは、乗数のビットＹ２、Ｙ３、Ｙ４を受ける。符号化回路１０２Ｃは、乗数のビットＹ４、Ｙ５、Ｙ６を受ける。符号化回路１０２Ｄは、乗数のビットＹ６、Ｙ７および０であるヌルビットを受ける。
【００２１】
好ましい実施の形態において、乗算回路１００は、Ｍ個のセレクタ回路１０４を備える。ここでＭは、被乗数のビット数である。本実施の形態では、被乗数は８ビット（Ａ０、Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６、Ａ７）であるとする。各セレクタ回路１０４は、最後のセレクタ回路１０４Ｈを除き、被乗数に含まれる２ビットの組１１０であって互いに異なる組を受ける。最後のセレクタ回路１０４Ｈは、被乗数に含まれる１ビットと、ヌルビットを受ける。たとえば、第１セレクタ回路１０４Ａは、被乗数のビットＡ０、Ａ１を受ける。第２セレクタ回路１０４Ｂは、被乗数のビットＡ１、Ａ２を受ける。第３セレクタ回路１０４Ｃは、被乗数のビットＡ２、Ａ３を受ける。さらに他のセレクタ回路１０４も、最後のセレクタ回路１０４Ｈを除き、同様のパターンにて、被乗数のビットを受ける。最後のセレクタ回路１０４ＨはビットＡ７とヌルビット０を受けることになる。
【００２２】
当業者であれば、本明細書の説明にもとづいて、乗算回路１００の設計指針に応じて、別の個数の符号化回路１０２、あるいは別の個数のセレクタ回路１０４が利用できることを理解できよう。たとえば、ひとつの符号化回路１０２を用い、乗数に含まれるビットの組１０６を順次受け、符号化されたビットの組を信号線１０８に順次出力してもよい。この場合、複数のセレクタ回路１０４が、順次、符号化されたビットの組を受け、それぞれに対して部分積を生成してもよい。同様に、ひとつのセレクタ回路１０４を用い、被乗数のビットの組１１０を順次受け、部分積の各ビットＳｉを順次生成してもよい。以上の説明によって、当業者であれば、異なる個数の符号化回路１０２や、異なる個数のセレクタ回路１０４を利用した乗算回路１００のさまざまな実施の形態を考えることができ、上述したあるいは後述する部分積を生成することができよう。
【００２３】
図２は、図１の符号化回路１０２の構成例を示す回路図である。図３は、符号化回路１０２の真理値表を示す。符号化回路１０２は乗数に含まれる３ビットの組（Ｙｉ、Ｙｊ、Ｙｋ）を、符号化されたビットの組（ｐｏｓ＿２、ｎｅｇ＿２、ｎｅｇ＿ｏｒ＿ｚｅｒｏ、ａｂｓ＿１）に変換する複数の論理ゲートを備える。好ましい実施の形態において、符号化回路１０２は、第１回路２０２Ａ、第２回路２０２Ｂ、第３回路２０２Ｃ、第４回路２０２Ｄを含む。第１回路２０２Ａは、乗数のビットＹｉ、Ｙｊ、Ｙｋを受け、符号化されたビットのうち、第１のビットｐｏｓ＿２を生成する。第２回路２０２Ｂは、乗数のビットＹｉ、Ｙｊ、Ｙｋを受け、符号化されたビットのうち、第２のビットｎｅｇ＿２を生成する。第３回路２０２Ｃは、乗数のビットＹｉを受け、符号化されたビットのうち、第３のビットｎｅｇ＿ｏｒ＿ｚｅｒｏを生成する。第４回路２０２Ｄは、乗数のビットＹｊ、Ｙｋを受け、符号化されたビットのうち、第４のビットａｂｓ＿１を生成する。
【００２４】
符号化回路１０２は、図３に示す真理値表に示される符号化されたビットを生成するように接続された適切な論理ゲートを含む。具体的には、第１の符号化されたビットｐｏｓ＿２は、乗数に含まれる３ビットの組の基数４の表現が＋２の場合に真（１）となる。第２ビットｎｅｇ＿２は、乗数に含まれる３ビットの組の基数４の表現が−２の場合に真（１）となる。第３ビットｎｅｇ＿ｏｒ＿ｚｅｒｏは、乗数に含まれる３ビットの組の基数４の表現が、負もしくは０である場合に真（１）となる。第４ビットａｂｓ＿１は、乗数に含まれる３ビットの組の基数４の表現の絶対値が１のときに真（１）となる。
【００２５】
図２に示される符号化回路１０２の具体的な回路構成は、説明のための例示であり、当業者であれば、ここの論理ゲートやそれらの相互接続に、本発明の範囲内において、さまざまな変形例があり得ることが理解できよう。
【００２６】
図４は、図１のセレクタ回路１０４の構成例を示す回路図である。セレクタ回路１０４は、符号化回路１０２からの符号化されたビットを利用して、被乗数に含まれるビットの組１１０であるＡｉ、Ａｊを操作し、乗数および被乗数の部分積の各ビットＳｉを生成するための複数の論理ゲートを含む。好ましい実施の形態において、論理ゲートは以下のブール表現に従って、出力ビットＳｉを生成する。
Ｓｉ＝（Ｂ１  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ２  ＮＡＮＤ  Ａｊ）  ＮＡＮＤ  （Ｂ４  ＮＡＮＤ  （Ｂ３  ＸＯＲ  Ａｉ））
ここで、Ｂｉは、符号化されたビットの組の第１、第２、第３、第４のビットである。
【００２７】
図４のセレクタ回路１０４は、説明のための例示であり、当業者であれば、ここの論理ゲートやそれらの相互接続に、本発明の範囲内において、さまざまな変形例があり得ることが理解できよう。
【００２８】
図５から図８は、図１から図４に示した実施の形態に係る乗算回路と、従来の乗算回路の伝搬遅延を比較して示す図である。
図５は、従来のブース符号化回路３０２およびセレクタ回路３０４を示す図であり、図示された真理値表は、ブース符号化回路３０２の動作を示す。ブース符号化回路３０２およびセレクタ回路３０４の最長の伝搬遅延は、複数の論理ゲートごとの単位遅延を考えることによって評価できる。説明のため、ＸＯＲゲートは、多くのファンアウト負荷を有した状態で１．５の伝搬遅延を有し、ＡＮＤゲートは、１．０の伝搬遅延を有し、インバータゲートは、１．０の伝搬遅延を有するものとする。図５の回路の最長の伝搬遅延は、１．５＋１．０＋１．０＋１．０＋１．０＋１．５＝７．０となる。
【００２９】
図６は、別の従来のブース符号化回路４０２およびセレクタ回路４０４を示す図であり、図示された真理値表は、ブース符号化回路４０２の動作を示す。ブース符号化回路４０２およびセレクタ回路４０４による最長の伝搬遅延は、１．５＋１．０＋１．０＋１．０＋１．０＝５．５となる。
【００３０】
図７は、さらに別の従来のブース符号化回路５０２およびセレクタ回路５０４を示す図であり、図示された真理値表は、ブース符号化回路５０２の動作を示す。ブース符号化回路５０２およびセレクタ回路５０４による最長の伝搬遅延は、１．５＋１．０＋１．０＋１．０＋１．０＝５．５となる。
【００３１】
図８は、本実施の形態に係る符号化回路１０２およびセレクタ回路１０４を示す図である。いくつかのパスについて検討する。第１の符号化されたビットｐｏｓ＿２の第１の経路では、伝搬遅延は、１．５＋１．０＋１．０＋１．０＝４．５となる。第２の符号化されたビットｎｅｇ＿２の伝搬遅延は、１．５＋１．０＋１．０＋１．０＝４．５となる。第３の符号化されたビットｎｅｇ＿ｏｒ＿ｚｅｒｏの伝搬遅延は、１．５＋１．０＋１．０＋１．０＝４．５となる。ここでの１．５という伝搬遅延は、符号化回路１０２におけるインバータに対するものであり、その出力が複数のセレクタ回路に対して展開されているため１．５としている。反対に、セレクタ回路１０４のＸＯＲ論理ゲートに対する１．０という伝搬遅延は、ＸＯＲゲートが負荷としてひとつの論理ゲートのみを有していることによるものである。第４の符号化されたビットａｂｓ＿１の伝搬遅延は、１．５＋１．０＋１．０＋１．０＝４．５となる。図８の乗算回路１００における信号の伝搬遅延を、従来の図５から図７の伝搬遅延と比較すると、本実施の形態における伝搬遅延が全体として著しく短くなっている。さらに、乗算回路１００のそれぞれのパスの伝搬遅延は、先行技術におけるそれぞれと比べて、バランスがとれたものとなっている。これにより、より早い処理速度と、より高い同期動作が実現できる。
【００３２】
本明細書において説明した方法あるいは装置はたとえば、現在において利用可能であり、あるいは将来において開発される標準的なデジタル回路、アナログ回路、マイクロプロセッサ、デジタル信号処理回路、ソフトウェアやファームウェアを実行可能なプロセッサ、プログラム可能なデジタル機器やシステム、プログラム可能なアレイ論理デバイス、あるいはこれらの組み合わせなどの公知の技術を利用することにより実現される。
【００３３】
実施の形態にもとづき、本発明を説明したが、実施の形態は、本発明の原理、応用を示しているにすぎず、実施の形態には、請求の範囲に規定された本発明の思想を離脱しない範囲において、多くの変形例や配置の変更が可能である。
【図面の簡単な説明】
【００３４】
【図１】２進数の積に関連する部分積を生成する実施の形態に係る乗算回路の構成を示すブロック図である。
【図２】図１の符号化回路の構成例を示す回路図である。
【図３】図２の符号化回路の真理値表を示す。
【図４】図１のセレクタ回路の構成例を示す回路図である。
【図５】従来のブース符号化回路およびセレクタ回路の遅延およびブース符号化回路の動作を示す真理値表を示す図である。
【図６】従来の別のブース符号化回路およびセレクタ回路の遅延およびブース符号化回路の動作を示す真理値表を示す図である。
【図７】従来のさらに別のブース符号化回路およびセレクタ回路の遅延およびブース符号化回路の動作を示す真理値表を示す図である。
【図８】実施の形態に係る符号化回路およびセレクタ回路を示す図である。
【符号の説明】
【００３５】
１００  乗算回路、  １０２  符号化回路、  １０４  セレクタ回路、  １０８  信号線、  ２０２Ａ  第１回路、  ２０２Ｂ  第２回路、  ２０２Ｃ  第３回路、  ２０２Ｄ  第４回路。
【図１】
2007234004.tif 000009
【図２】
2007234004.tif 000010
【図３】
2007234004.tif 000011
【図４】
2007234004.tif 000012
【図５】
2007234004.tif 000013
【図６】
2007234004.tif 000014
【図７】
2007234004.tif 000015
【図８】
2007234004.tif 000016