(57)【特許請求の範囲】
【請求項１】
複数ビットのデータからなる乗数データのうちそれぞれ一部のビットのデータが入力されて符号データを出力する複数のエンコード回路と、
上記複数のエンコード回路に対応して設けられ、それぞれ列状に配列された複数の乗算器セルからなり、上記乗数データと同一方向もしくは対向する方向から入力される複数ビットのデータからなる被乗数データと上記対応するエンコード回路から出力される符号データとから部分積を生成する複数の部分積生成回路と、
上記複数の部分積生成回路で生成された部分積を加算して乗算結果を出力する部分積加算回路とを具備し、
上記複数の各エンコード回路は、入力される乗数データのビット位置に適合する位置に配置されていることを特徴とする乗算回路。
【請求項２】
前記複数のエンコード回路のうち、一部は対応する前記部分積生成回路に隣接する位置に配置され、一部は対応する前記部分積生成回路の前記複数の乗算器セルの配列の途中に挿入配置されていることを特徴する請求項１記載の乗算回路。
【請求項３】
前記複数の各エンコード回路がブース（Booth）のエンコード回路であることを特徴する請求項１または２記載の乗算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ブース（Booth）のアルゴリズムを用いた乗算回路に係り、特に被乗数データから部分積生成に必要な符号データを出力するエンコード回路の配置位置を改良した乗算回路に関する。
【０００２】
【従来の技術】
ＤＳＰ（Digital Signal Processor）やＣＰＵ（Central Processing Unit）などのデジタル半導体集積回路には乗算回路が内蔵されることが多い。
【０００３】
この乗算回路の一手法としてブース（Booth）のアルゴリズムを用いることによって、集積度を高めることが行われている。例えば２次のブースのアルゴリズムを用いることにより、部分積の個数を半分にすることができ、これによって乗算回路の小面積化が可能になる。
【０００４】
いま、被乗数をＸ、乗数をＹとすると、積ＺはＸ＊Ｙと表される。ここで、Ｙを２の補数で表現すると、Ｚは以下の式で表される。
【０００５】
【数１】
0003940564.tif 000002
【０００６】
上記（１）式において、ｙ2k、ｙ2k+1、ｙ2k+2は乗数Ｙのうち隣り合う３ビットのデータであり、この３ビットのデータからエンコード回路を用いて符号データが生成され、この生成された符号データと被乗数Ｘとが部分積生成回路で乗算されて部分積が生成され、全ての部分積が部分積加算回路で加算されることによりＸ＊Ｙの演算が行なわれる。
【０００７】
図６は、２次のブースのアルゴリズムを用いた従来の乗算回路の概略的な構成を示すブロック図である。先に述べたように、ブースのアルゴリズムを用いた乗算回路は、部分積生成回路、エンコード回路及び部分積加算回路で構成されるが、図６では部分積加算回路の図示を省略している。
【０００８】
図示するように、部分積生成回路１１は列状に配列された複数の乗算器セル１３で構成され、それぞれ１つの部分積生成回路１１とエンコード回路１２とが対にされ、部分積生成回路１１に隣接して対をなすエンコード回路１２が配置されて１段の回路が構成され、複数段の回路が縦方向に必要段数分配置される。なお、被乗数Ｘ及び乗数Ｙは複数段の回路の上方からそれぞれ入力されるものとする。
【０００９】
例えば、図中、最上段に配置された回路のエンコード回路１２には３ビットの乗数データとして“０”、ｙ1 、ｙ2 が入力され、この３ビットの乗数データをエンコードして得られる符号データが対応する部分積生成回路１１内の複数の乗算器セル１３に並列に入力されて部分積が生成される。同様に、２段目に配置された回路のエンコード回路１２には３ビットの乗数データとしてｙ2 、ｙ3 、ｙ4 が入力され、さらに３段目に配置された回路のエンコード回路１２には３ビットの乗数データとしてｙ4 、ｙ5 、ｙ6 が入力され、それぞれこれら３ビットの乗数データをエンコードして得られる符号データが対応する部分積生成回路１１内の複数の乗算器セル１３に並列に入力されて部分積が生成される。
【００１０】
すなわち、２次のブースのアルゴリズムを用いた場合、各段のエンコード回路１２には、縦方向で隣接する２つのエンコード回路で１ビットがオーバーラップした状態で、乗数データが３ビットずつ入力される。
【００１１】
ところで、従来の乗算回路では、図示のように、部分積生成回路１１とエンコード回路１２とからなる各段の回路において、エンコード回路１２は全て部分積生成回路１１の右側に隣接して配置されている。
【００１２】
しかしながら、上記構成でなる従来の乗算回路では、ｎビットの乗数Ｙを各部分積生成回路１１の右側に配置されたエンコード回路１２まで伝達する必要があり、乗数Ｙのビット数が増えれば増えるほど、乗数Ｙの広い配線領域が必要になるという問題がある。
【００１３】
また、図７に示すように、ｎビットの乗数ＹのうちＭＳＢ側の３つのデータｙn-2、ｙn-1、ｙn が入力されるエンコード回路１２を含む回路では、これら３ビットの乗数データが、部分積生成回路１１とエンコード回路１２とからなる回路の外側でエンコード回路１２の位置まで引き回され、さらにそれをエンコードした結果が部分積生成回路１１のＭＳＢ側の乗算器セルまで供給されるという明らかに冗長なデータの移動が起こる。この結果、部分積生成に要する時間の増大を招いてしまうという問題がある。
【００１４】
なお、ここでは、従来例としてブースのエンコード回路１２を部分積生成回路１１の右側に配置した場合について説明したが、逆に左側に配置することも可能であり、この場合には、乗数Ｙを左側に配置されたエンコード回路１２まで引き回す必要が生じ、左右が逆になるだけで、やはり同様の問題が生じる。
【００１５】
【発明が解決しようとする課題】
このように、従来の乗算回路では、部分積生成回路と対をなすエンコード回路を全て部分積生成回路に隣接して配置するようにしているので、乗数データを伝える配線長が長くなって配線領域が増大するという問題が生じる。
【００１６】
この発明は上記のような事情を考慮してなされたものであり、その目的は、乗数データを伝達する配線の配線長を短くして配線領域の削減を図ることができる乗算回路を提供することである。
【００１７】
【課題を解決するための手段】
この発明の乗算回路は、複数ビットのデータからなる乗数データのうちそれぞれ一部のビットのデータが入力されて符号データを出力する複数のエンコード回路と、上記複数のエンコード回路に対応して設けられ、それぞれ列状に配列された複数の乗算器セルからなり、上記乗数データと同一方向もしくは対向する方向から入力される複数ビットのデータからなる被乗数データと上記対応するエンコード回路から出力される符号データとから部分積を生成する複数の部分積生成回路と、上記複数の部分積生成回路で生成された部分積を加算して乗算結果を出力する部分積加算回路とを具備し、上記複数の各エンコード回路は、入力される乗数データのビット位置に適合する位置に配置されていることを特徴とする。
【００１８】
従って、複数のエンコード回路の一部は対応する部分積生成回路に隣接する位置に配置され、他の一部は対応する部分積生成回路内の前記複数の乗算器セルの配列の途中に挿入配置される。
【００１９】
【発明の実施の形態】
以下、図面を参照してこの発明の実施の形態を詳細に説明する。
【００２０】
図１は、この発明の実施の形態による乗算回路の構成を示すブロック図である。なお、本実施の形態では、従来と同様に２次のブースのアルゴリズムを用いた場合について説明するが、３次、４次など、次数の高いブースのアルゴリズムを用いたものにも同様に実施することができる。
【００２１】
この乗算回路は、大きく分けて、部分積生成回路１１及びエンコード回路１２からなり複数の部分積を生成する乗算アレイ１０と、乗算アレイ１０で生成される複数の部分積を加算して乗算結果を出力する部分積加算回路２０とから構成されている。
【００２２】
部分積生成回路１１は列状に配列された複数の乗算器セル１３で構成されており、それぞれ１つの部分積生成回路１１とエンコード回路１２とが対にされて１段の回路が構成され、複数段の回路が縦方向に必要段数分配置される。
【００２３】
ｍビットのデータからなる被乗数Ｘ及びｎビットのデータからなる乗数Ｙは、乗算アレイ１０を構成する複数段の回路の上方からそれぞれ入力される。なお、被乗数Ｘ及び乗数ＹそれぞれのＬＳＢ側のビットのデータを伝達する配線は図中の右側に配置され、逆にＭＳＢ側のビットのデータを伝達する配線は図中の左側に配置されているとする。
【００２４】
ここで、乗算アレイ１０を構成する各段の部分積生成回路１１とエンコード回路１２とからなる回路は、部分積生成回路１１で生成する部分積の重み付けを意識して配置されるが、そのまま配置すると、被乗数Ｘがｍビット、乗数ＹがｎビットでＸ＊Ｙの乗算回路の場合、回路全体のビット幅として（ｍ＋ｎ）ビット分必要になり、全体的に横長の回路になってしまう。
【００２５】
そこで、面積的な制約がある場合には、図１に示すように、部分積生成回路１１とエンコード回路１２とからなる回路をある程度の固まり（本例では４回路）毎にブロック分けし、各ブロック毎に部分積生成回路１１及びエンコード回路１２からなる回路を図中の右方向にシフトして配置する方法が用いられる。
【００２６】
さらに、各ブロックＢ１、Ｂ２、…Ｂｒにおいて、エンコード回路１２は、そのエンコード回路１２に入力される乗数データＹの３ビットの乗数データを伝達する配線に最も近くなるように、それぞれ３ビットの乗数データのビット位置に適合する位置に配置される。例えば、図中、最上部に位置している第１のブロックＢ１では、各エンコード回路１２は対応する部分積生成回路１１の右側に隣接するように配置されている。第１のブロックＢ１の下段に位置する第２のブロックＢ２では、各エンコード回路１２は、対応する部分積生成回路１１内で配列されている複数の乗算器セル１３のうち、右側から数えて６番目と７番目の乗算器セル１３の間に挿入配置されている。以下、同様にして、各ブロックでは、各エンコード回路１２は、それぞれに入力される３ビットの乗数データを伝達する配線に最も近くなるように、対応する部分積生成回路１１内の複数の乗算器セル１３の配列の途中に挿入配置されている。ちなみに、最下部の第ｒのブロックＢｒでは、各エンコード回路１２は、対応する部分積生成回路１１内で配列されている複数の乗算器セル１３のうち、左側から数えて２番目と３番目の乗算器セル１３の間に挿入配置されている。
【００２７】
また、被乗数Ｘの配線はｘ1 〜ｘ7 についてのみ例示している。被乗数Ｘは各部分積生成回路１１内の複数の乗算器セル１３に並列に入力される。
【００２８】
なお、２次のブースのアルゴリズムを用いたエンコード回路１２を設けているので、このエンコード回路１２よりも上位ビット側に位置する部分積生成回路１１内の乗算器セル１３では、図２に示すようにそれぞれの出力を２ビットずつ下位ビット側にシフト（２ bit shift）している。
【００２９】
このように構成された乗算回路において、各段の部分積生成回路１１から出力される部分積は、２次のブースのエンコード回路１２を部分積生成回路１１の途中に挿入した分のシフトを行なった後は、従来の乗算回路と同様に部分積加算回路２０を用いて部分積の加算を行なうことによって、所望の乗算結果を得ることができる。
【００３０】
上記実施の形態の乗算回路では、各エンコード回路１２は、それぞれに入力される３ビットの乗数データを伝達する配線に最も近くなるように、入力される乗数データのビット位置に適合する位置に配置されている。
【００３１】
このため、従来のように乗数データの配線を長く引き回して各エンコード回路１２に入力する必要がない。この結果、乗数Ｙのビット数が増えても、乗数Ｙの配線として広い配線領域は不要であり、乗数Ｙの配線領域を従来よりも削減することができる。
【００３２】
また、従来のように乗数データの配線を長く引き回す必要がなくなるので、冗長なデータの移動をなくすことができ、部分積生成にかかる時間の増大も防止することができる。
【００３３】
図３は、図１中のエンコード回路１２のエンコード状態の一例を示す図である。図３中の「倍数」とは、３ビットの乗数データ（ｙ2k、ｙ2k+1、ｙ2k+2）に基づいて被乗数Ｘに対して乗算を行なう数値を示しており、この数値は図３中の３ビットの符号データＸ、２Ｘ、ＮＥＧによって表される。例えば、図３中の２段目のｙ2k＝ｙ2k+1＝“０”、ｙ2k+2＝“１”の場合、倍数は−２であり、この倍数は符号データ２Ｘを“１”にすることで２倍を表し、さらに符号データＮＥＧを“１”にすることでその倍数が負の値であることを表している。
【００３４】
図４は、上記図３に示したエンコード状態を実現するエンコード回路１２の具体的な回路例を示している。乗数データｙ2k及びｙ2k+1がイクスクルーシブ（exclusive）ＯＲゲート３１に入力され、このイクスクルーシブＯＲゲート３１から符号データＸが出力される。また、乗数データｙ2k、ｙ2k+1がそのまま及び乗数データｙ2k+2の反転データがＡＮＤゲート３２に入力され、さらに乗数データｙ2k、ｙ2k+1それぞれの反転データ及び乗数データｙ2k+2がＡＮＤゲート３３に入力され、両ＡＮＤゲート３２、３３の出力がＯＲゲート３４に入力され、このＯＲゲート３４から符号データ２Ｘが出力される。乗数データｙ2k+2はそのまま符合データＮＥＧとして出力される。
【００３５】
図５は、図１中の部分積生成回路１１内の乗算器セル１３の１個分の一構成例を示す回路図である。この乗算器セル１３は、２個のＡＮＤゲート４１、４２と、それそれ１個のＯＲゲート４３及びイクスクルーシブＯＲゲート４４とから構成されている。ＡＮＤゲート４１には被乗数データｘj-1と符号データ２Ｘとが入力される。また、ＡＮＤゲート４２には被乗数データｘj と符号データＸとが入力される。上記両ＡＮＤゲート４１、４２の出力はＯＲゲート４３に入力され、さらにこのＯＲゲート４３の出力は符合データＮＥＧと共にイクスクルーシブＯＲゲート４４に入力される。そして、このイクスクルーシブＯＲゲート４４から１ビット分の部分積が出力される。
【００３６】
なお、図３に示したエンコード回路１２のエンコード状態、図４に示したエンコード回路１２の具体的回路構成及び図５に示した乗算器セル１３の具体的回路構成は、それぞれあくまでも一例であり、必ずしもこのようにされている必要はない。
【００３７】
なお、上記実施の形態では、被乗数Ｘ及び乗数Ｙを、乗算アレイ１０を構成する複数段の回路の上方からそれぞれ入力する場合を説明したが、これは例えば被乗数Ｘは上方から入力し、乗数Ｙは下方から入力する如く、被乗数Ｘと乗数Ｙとを対向する方向から入力するように配線を変更してもよい。
【００３８】
さらに上記実施の形態では、図１に示すように、各ブロック内では、部分積生成回路１１に対してエンコード回路１２を全て同じ位置に配置する場合を説明したが、これはブロック内で異なる位置に配置するようにしてもよい。要するに、それぞれに入力される３ビットの乗数データのビット位置に適合する位置にエンコード回路１２を配置すればよい。
【００３９】
【発明の効果】
以上説明したようにこの発明によれば、乗数データを伝達する配線の配線長を短くして配線領域の削減を図ることができる乗算回路を提供することができる。
【図面の簡単な説明】
【図１】この発明の実施の形態による乗算回路の構成を示すブロック図。
【図２】図１の乗算回路において１段分の部分積生成回路及びエンコード回路からなる回路を抜き出して示す回路図。
【図３】図１中のエンコード回路のエンコード状態の一例を示す図。
【図４】図３に示したエンコード状態を実現するエンコード回路の具体的な回路例を示す図。
【図５】図１中の部分積生成回路内の乗算器セル１個分の一構成例を示す回路図。
【図６】従来の乗算回路の構成を示すブロック図。
【図７】図６の従来の乗算回路において１段分の部分積生成回路及びエンコード回路からなる回路を抜き出して示す回路図。
【符号の説明】
１０…乗算アレイ、
１１…部分積生成回路、
１２…エンコード回路、
１３…乗算器セル、
２０…部分積加算回路。
【図１】
0003940564.tif 000003
【図２】
0003940564.tif 000004
【図３】
0003940564.tif 000005
【図４】
0003940564.tif 000006
【図５】
0003940564.tif 000007
【図６】
0003940564.tif 000008
【図７】
0003940564.tif 000009