JP3940564B2

JP3940564B2 - Multiplication circuit

Info

Publication number: JP3940564B2
Application number: JP2001093666A
Authority: JP
Inventors: 直佳矢野
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2001-03-28
Filing date: 2001-03-28
Publication date: 2007-07-04
Anticipated expiration: 2021-03-28
Also published as: JP2002287955A

Description

【０００１】
【発明の属する技術分野】
この発明は、ブース（Booth）のアルゴリズムを用いた乗算回路に係り、特に被乗数データから部分積生成に必要な符号データを出力するエンコード回路の配置位置を改良した乗算回路に関する。
【０００２】
【従来の技術】
ＤＳＰ（Digital Signal Processor）やＣＰＵ（Central Processing Unit）などのデジタル半導体集積回路には乗算回路が内蔵されることが多い。
【０００３】
この乗算回路の一手法としてブース（Booth）のアルゴリズムを用いることによって、集積度を高めることが行われている。例えば２次のブースのアルゴリズムを用いることにより、部分積の個数を半分にすることができ、これによって乗算回路の小面積化が可能になる。
【０００４】
いま、被乗数をＸ、乗数をＹとすると、積ＺはＸ＊Ｙと表される。ここで、Ｙを２の補数で表現すると、Ｚは以下の式で表される。
【０００５】
【数１】

【０００６】
上記（１）式において、ｙ_2k、ｙ_2k+1、ｙ_2k+2は乗数Ｙのうち隣り合う３ビットのデータであり、この３ビットのデータからエンコード回路を用いて符号データが生成され、この生成された符号データと被乗数Ｘとが部分積生成回路で乗算されて部分積が生成され、全ての部分積が部分積加算回路で加算されることによりＸ＊Ｙの演算が行なわれる。
【０００７】
図６は、２次のブースのアルゴリズムを用いた従来の乗算回路の概略的な構成を示すブロック図である。先に述べたように、ブースのアルゴリズムを用いた乗算回路は、部分積生成回路、エンコード回路及び部分積加算回路で構成されるが、図６では部分積加算回路の図示を省略している。
【０００８】
図示するように、部分積生成回路１１は列状に配列された複数の乗算器セル１３で構成され、それぞれ１つの部分積生成回路１１とエンコード回路１２とが対にされ、部分積生成回路１１に隣接して対をなすエンコード回路１２が配置されて１段の回路が構成され、複数段の回路が縦方向に必要段数分配置される。なお、被乗数Ｘ及び乗数Ｙは複数段の回路の上方からそれぞれ入力されるものとする。
【０００９】
例えば、図中、最上段に配置された回路のエンコード回路１２には３ビットの乗数データとして“０”、ｙ₁ 、ｙ₂ が入力され、この３ビットの乗数データをエンコードして得られる符号データが対応する部分積生成回路１１内の複数の乗算器セル１３に並列に入力されて部分積が生成される。同様に、２段目に配置された回路のエンコード回路１２には３ビットの乗数データとしてｙ₂ 、ｙ₃ 、ｙ₄ が入力され、さらに３段目に配置された回路のエンコード回路１２には３ビットの乗数データとしてｙ₄ 、ｙ₅ 、ｙ₆ が入力され、それぞれこれら３ビットの乗数データをエンコードして得られる符号データが対応する部分積生成回路１１内の複数の乗算器セル１３に並列に入力されて部分積が生成される。
【００１０】
すなわち、２次のブースのアルゴリズムを用いた場合、各段のエンコード回路１２には、縦方向で隣接する２つのエンコード回路で１ビットがオーバーラップした状態で、乗数データが３ビットずつ入力される。
【００１１】
ところで、従来の乗算回路では、図示のように、部分積生成回路１１とエンコード回路１２とからなる各段の回路において、エンコード回路１２は全て部分積生成回路１１の右側に隣接して配置されている。
【００１２】
しかしながら、上記構成でなる従来の乗算回路では、ｎビットの乗数Ｙを各部分積生成回路１１の右側に配置されたエンコード回路１２まで伝達する必要があり、乗数Ｙのビット数が増えれば増えるほど、乗数Ｙの広い配線領域が必要になるという問題がある。
【００１３】
また、図７に示すように、ｎビットの乗数ＹのうちＭＳＢ側の３つのデータｙ_n-2、ｙ_n-1、ｙ_nが入力されるエンコード回路１２を含む回路では、これら３ビットの乗数データが、部分積生成回路１１とエンコード回路１２とからなる回路の外側でエンコード回路１２の位置まで引き回され、さらにそれをエンコードした結果が部分積生成回路１１のＭＳＢ側の乗算器セルまで供給されるという明らかに冗長なデータの移動が起こる。この結果、部分積生成に要する時間の増大を招いてしまうという問題がある。
【００１４】
なお、ここでは、従来例としてブースのエンコード回路１２を部分積生成回路１１の右側に配置した場合について説明したが、逆に左側に配置することも可能であり、この場合には、乗数Ｙを左側に配置されたエンコード回路１２まで引き回す必要が生じ、左右が逆になるだけで、やはり同様の問題が生じる。
【００１５】
【発明が解決しようとする課題】
このように、従来の乗算回路では、部分積生成回路と対をなすエンコード回路を全て部分積生成回路に隣接して配置するようにしているので、乗数データを伝える配線長が長くなって配線領域が増大するという問題が生じる。
【００１６】
この発明は上記のような事情を考慮してなされたものであり、その目的は、乗数データを伝達する配線の配線長を短くして配線領域の削減を図ることができる乗算回路を提供することである。
【００１７】
【課題を解決するための手段】
この発明の乗算回路は、複数ビットのデータからなる乗数データのうちそれぞれ一部のビットのデータが入力されて符号データを出力する複数のエンコード回路と、上記複数のエンコード回路に対応して設けられ、それぞれ列状に配列された複数の乗算器セルからなり、上記乗数データと同一方向もしくは対向する方向から入力される複数ビットのデータからなる被乗数データと上記対応するエンコード回路から出力される符号データとから部分積を生成する複数の部分積生成回路と、上記複数の部分積生成回路で生成された部分積を加算して乗算結果を出力する部分積加算回路とを具備し、上記複数の各エンコード回路は、入力される乗数データのビット位置に適合する位置に配置されていることを特徴とする。
【００１８】
従って、複数のエンコード回路の一部は対応する部分積生成回路に隣接する位置に配置され、他の一部は対応する部分積生成回路内の前記複数の乗算器セルの配列の途中に挿入配置される。
【００１９】
【発明の実施の形態】
以下、図面を参照してこの発明の実施の形態を詳細に説明する。
【００２０】
図１は、この発明の実施の形態による乗算回路の構成を示すブロック図である。なお、本実施の形態では、従来と同様に２次のブースのアルゴリズムを用いた場合について説明するが、３次、４次など、次数の高いブースのアルゴリズムを用いたものにも同様に実施することができる。
【００２１】
この乗算回路は、大きく分けて、部分積生成回路１１及びエンコード回路１２からなり複数の部分積を生成する乗算アレイ１０と、乗算アレイ１０で生成される複数の部分積を加算して乗算結果を出力する部分積加算回路２０とから構成されている。
【００２２】
部分積生成回路１１は列状に配列された複数の乗算器セル１３で構成されており、それぞれ１つの部分積生成回路１１とエンコード回路１２とが対にされて１段の回路が構成され、複数段の回路が縦方向に必要段数分配置される。
【００２３】
ｍビットのデータからなる被乗数Ｘ及びｎビットのデータからなる乗数Ｙは、乗算アレイ１０を構成する複数段の回路の上方からそれぞれ入力される。なお、被乗数Ｘ及び乗数ＹそれぞれのＬＳＢ側のビットのデータを伝達する配線は図中の右側に配置され、逆にＭＳＢ側のビットのデータを伝達する配線は図中の左側に配置されているとする。
【００２４】
ここで、乗算アレイ１０を構成する各段の部分積生成回路１１とエンコード回路１２とからなる回路は、部分積生成回路１１で生成する部分積の重み付けを意識して配置されるが、そのまま配置すると、被乗数Ｘがｍビット、乗数ＹがｎビットでＸ＊Ｙの乗算回路の場合、回路全体のビット幅として（ｍ＋ｎ）ビット分必要になり、全体的に横長の回路になってしまう。
【００２５】
そこで、面積的な制約がある場合には、図１に示すように、部分積生成回路１１とエンコード回路１２とからなる回路をある程度の固まり（本例では４回路）毎にブロック分けし、各ブロック毎に部分積生成回路１１及びエンコード回路１２からなる回路を図中の右方向にシフトして配置する方法が用いられる。
【００２６】
さらに、各ブロックＢ１、Ｂ２、…Ｂｒにおいて、エンコード回路１２は、そのエンコード回路１２に入力される乗数データＹの３ビットの乗数データを伝達する配線に最も近くなるように、それぞれ３ビットの乗数データのビット位置に適合する位置に配置される。例えば、図中、最上部に位置している第１のブロックＢ１では、各エンコード回路１２は対応する部分積生成回路１１の右側に隣接するように配置されている。第１のブロックＢ１の下段に位置する第２のブロックＢ２では、各エンコード回路１２は、対応する部分積生成回路１１内で配列されている複数の乗算器セル１３のうち、右側から数えて６番目と７番目の乗算器セル１３の間に挿入配置されている。以下、同様にして、各ブロックでは、各エンコード回路１２は、それぞれに入力される３ビットの乗数データを伝達する配線に最も近くなるように、対応する部分積生成回路１１内の複数の乗算器セル１３の配列の途中に挿入配置されている。ちなみに、最下部の第ｒのブロックＢｒでは、各エンコード回路１２は、対応する部分積生成回路１１内で配列されている複数の乗算器セル１３のうち、左側から数えて２番目と３番目の乗算器セル１３の間に挿入配置されている。
【００２７】
また、被乗数Ｘの配線はｘ₁ 〜ｘ₇ についてのみ例示している。被乗数Ｘは各部分積生成回路１１内の複数の乗算器セル１３に並列に入力される。
【００２８】
なお、２次のブースのアルゴリズムを用いたエンコード回路１２を設けているので、このエンコード回路１２よりも上位ビット側に位置する部分積生成回路１１内の乗算器セル１３では、図２に示すようにそれぞれの出力を２ビットずつ下位ビット側にシフト（２ 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 と符号データＸとが入力される。上記両ＡＮＤゲート４１、４２の出力はＯＲゲート４３に入力され、さらにこのＯＲゲート４３の出力は符合データＮＥＧと共にイクスクルーシブＯＲゲート４４に入力される。そして、このイクスクルーシブＯＲゲート４４から１ビット分の部分積が出力される。
【００３６】
なお、図３に示したエンコード回路１２のエンコード状態、図４に示したエンコード回路１２の具体的回路構成及び図５に示した乗算器セル１３の具体的回路構成は、それぞれあくまでも一例であり、必ずしもこのようにされている必要はない。
【００３７】
なお、上記実施の形態では、被乗数Ｘ及び乗数Ｙを、乗算アレイ１０を構成する複数段の回路の上方からそれぞれ入力する場合を説明したが、これは例えば被乗数Ｘは上方から入力し、乗数Ｙは下方から入力する如く、被乗数Ｘと乗数Ｙとを対向する方向から入力するように配線を変更してもよい。
【００３８】
さらに上記実施の形態では、図１に示すように、各ブロック内では、部分積生成回路１１に対してエンコード回路１２を全て同じ位置に配置する場合を説明したが、これはブロック内で異なる位置に配置するようにしてもよい。要するに、それぞれに入力される３ビットの乗数データのビット位置に適合する位置にエンコード回路１２を配置すればよい。
【００３９】
【発明の効果】
以上説明したようにこの発明によれば、乗数データを伝達する配線の配線長を短くして配線領域の削減を図ることができる乗算回路を提供することができる。
【図面の簡単な説明】
【図１】この発明の実施の形態による乗算回路の構成を示すブロック図。
【図２】図１の乗算回路において１段分の部分積生成回路及びエンコード回路からなる回路を抜き出して示す回路図。
【図３】図１中のエンコード回路のエンコード状態の一例を示す図。
【図４】図３に示したエンコード状態を実現するエンコード回路の具体的な回路例を示す図。
【図５】図１中の部分積生成回路内の乗算器セル１個分の一構成例を示す回路図。
【図６】従来の乗算回路の構成を示すブロック図。
【図７】図６の従来の乗算回路において１段分の部分積生成回路及びエンコード回路からなる回路を抜き出して示す回路図。
【符号の説明】
１０…乗算アレイ、
１１…部分積生成回路、
１２…エンコード回路、
１３…乗算器セル、
２０…部分積加算回路。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a multiplication circuit using a Booth algorithm, and more particularly to a multiplication circuit in which an arrangement position of an encoding circuit that outputs code data necessary for generating a partial product from multiplicand data is improved.
[0002]
[Prior art]
A digital semiconductor integrated circuit such as a DSP (Digital Signal Processor) or a CPU (Central Processing Unit) often has a built-in multiplication circuit.
[0003]
The integration degree is increased by using a Booth algorithm as one method of the multiplication circuit. For example, by using a secondary Booth algorithm, the number of partial products can be halved, which makes it possible to reduce the area of the multiplication circuit.
[0004]
If the multiplicand is X and the multiplier is Y, the product Z is expressed as X * Y. Here, when Y is expressed in two's complement, Z is expressed by the following equation.
[0005]
[Expression 1]

[0006]
In the above equation (1), y _2k , y _{2k + 1} , y _{2k + 2} are adjacent 3-bit data in the multiplier Y, and code data is generated from the 3-bit data using an encoding circuit, The generated code data and the multiplicand X are multiplied by the partial product generation circuit to generate a partial product, and all partial products are added by the partial product addition circuit, whereby an X * Y operation is performed.
[0007]
FIG. 6 is a block diagram showing a schematic configuration of a conventional multiplication circuit using a second-order Booth algorithm. As described above, the multiplication circuit using the Booth algorithm is composed of a partial product generation circuit, an encoding circuit, and a partial product addition circuit, but the partial product addition circuit is not shown in FIG.
[0008]
As shown in the figure, the partial product generation circuit 11 is composed of a plurality of multiplier cells 13 arranged in a column, and each of the partial product generation circuit 11 and the encoding circuit 12 is paired. A pair of encoding circuits 12 are arranged adjacent to each other to form a single-stage circuit, and a plurality of stages of circuits are arranged in the vertical direction by the required number of stages. It is assumed that the multiplicand X and the multiplier Y are respectively input from above the plurality of stages of circuits.
[0009]
For example, “0”, y ₁ , y ₂ are input as 3-bit multiplier data to the encoding circuit 12 of the circuit arranged at the top in the figure, and the code obtained by encoding the 3-bit multiplier data Data is input in parallel to a plurality of multiplier cells 13 in the corresponding partial product generation circuit 11 to generate a partial product. Similarly, y ₂ , y ₃ , and y ₄ are input as 3-bit multiplier data to the encoding circuit 12 of the circuit arranged at the second stage, and further, the encoding circuit 12 of the circuit arranged at the third stage is input to the encoding circuit 12 of the circuit arranged at the third stage. Y ₄ , y ₅ , and y ₆ are input as 3-bit multiplier data, and code data obtained by encoding these 3-bit multiplier data are respectively input to a plurality of multiplier cells 13 in the corresponding partial product generation circuit 11. Partial products are generated by parallel input.
[0010]
That is, when the secondary Booth algorithm is used, the multiplier data is input to the encoding circuit 12 at each stage in a state where 1 bit overlaps between two encoding circuits adjacent in the vertical direction. .
[0011]
By the way, in the conventional multiplication circuit, as shown in the figure, in each stage circuit composed of the partial product generation circuit 11 and the encoding circuit 12, all the encoding circuits 12 are arranged adjacent to the right side of the partial product generation circuit 11. Yes.
[0012]
However, in the conventional multiplication circuit having the above-described configuration, it is necessary to transmit the n-bit multiplier Y to the encoding circuit 12 arranged on the right side of each partial product generation circuit 11, and as the number of bits of the multiplier Y increases, the number increases. There is a problem that a wiring region having a wide multiplier Y is required.
[0013]
Further, as shown in FIG. 7, in a circuit including an encoding circuit 12 to which three data y _n-2 , y _n-1 , y _n on the MSB side of the n-bit multiplier Y are input, The multiplier data is routed to the position of the encoding circuit 12 outside the circuit composed of the partial product generation circuit 11 and the encoding circuit 12, and the result of encoding the data is the multiplier cell on the MSB side of the partial product generation circuit 11. Clearly redundant data movement occurs that is provided. As a result, there is a problem that the time required for partial product generation is increased.
[0014]
Here, the case where the Booth encoding circuit 12 is arranged on the right side of the partial product generation circuit 11 has been described as a conventional example, but conversely, it is also possible to arrange the encoding circuit 12 on the left side. It is necessary to route to the encoding circuit 12 arranged on the left side, and the same problem occurs after the left and right are reversed.
[0015]
[Problems to be solved by the invention]
In this way, in the conventional multiplication circuit, all the encoding circuits paired with the partial product generation circuit are arranged adjacent to the partial product generation circuit, so that the wiring length for transmitting the multiplier data becomes long and the wiring area The problem of increasing is caused.
[0016]
The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a multiplication circuit capable of reducing the wiring area by shortening the wiring length of the wiring for transmitting the multiplier data. It is.
[0017]
[Means for Solving the Problems]
A multiplication circuit according to the present invention is provided corresponding to a plurality of encoding circuits that receive a part of bit data of multiplier data composed of a plurality of bits of data and output code data, and the plurality of encoding circuits. , Multiplicand data composed of a plurality of multiplier cells arranged in a row, multi-bit data input from the same direction as or opposite to the multiplier data, and code data output from the corresponding encoding circuit A plurality of partial product generation circuits that generate partial products from the above, and a partial product addition circuit that adds the partial products generated by the plurality of partial product generation circuits and outputs a multiplication result. The encoding circuit is characterized in that it is arranged at a position that matches the bit position of the input multiplier data.
[0018]
Accordingly, a part of the plurality of encoding circuits is arranged at a position adjacent to the corresponding partial product generation circuit, and the other part is inserted in the middle of the arrangement of the plurality of multiplier cells in the corresponding partial product generation circuit. Is done.
[0019]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0020]
FIG. 1 is a block diagram showing a configuration of a multiplication circuit according to an embodiment of the present invention. In the present embodiment, a case where a secondary booth algorithm is used as in the conventional case will be described, but the same applies to a case where a higher order booth algorithm such as a third order or a fourth order is used. be able to.
[0021]
This multiplication circuit is broadly divided into a multiplication array 10 that includes a partial product generation circuit 11 and an encoding circuit 12 and generates a plurality of partial products, and adds a plurality of partial products generated by the multiplication array 10 to obtain a multiplication result. And a partial product adding circuit 20 for outputting.
[0022]
The partial product generation circuit 11 is composed of a plurality of multiplier cells 13 arranged in a line, and each of the partial product generation circuit 11 and the encoding circuit 12 is paired to form a one-stage circuit. A plurality of stages of circuits are arranged in the vertical direction by the required number of stages.
[0023]
A multiplicand X consisting of m-bit data and a multiplier Y consisting of n-bit data are respectively input from above a plurality of stages of circuits constituting the multiplication array 10. Note that the wiring for transmitting the LSB side bit data of each of the multiplicand X and the multiplier Y is arranged on the right side in the figure, and conversely, the wiring for transmitting the MSB side bit data is arranged on the left side in the figure. And
[0024]
Here, the circuit comprising the partial product generation circuit 11 and the encoding circuit 12 of each stage constituting the multiplication array 10 is arranged in consideration of the weighting of the partial products generated by the partial product generation circuit 11, but is arranged as it is. Then, in the case of an X * Y multiplication circuit with a multiplicand X of m bits and a multiplier Y of n bits, (m + n) bits are required as the bit width of the entire circuit, resulting in a horizontally long circuit as a whole.
[0025]
Therefore, when there is an area limitation, as shown in FIG. 1, the circuit composed of the partial product generation circuit 11 and the encoding circuit 12 is divided into blocks for a certain amount of blocks (four circuits in this example). A method is used in which a circuit composed of the partial product generation circuit 11 and the encoding circuit 12 is shifted and arranged in the right direction in the drawing for each block.
[0026]
Furthermore, in each of the blocks B1, B2,... Br, the encoding circuit 12 is a 3-bit multiplier so as to be closest to the wiring for transmitting the 3-bit multiplier data of the multiplier data Y input to the encoding circuit 12. It is placed at a position that matches the bit position of the data. For example, in the first block B1 located at the top in the drawing, each encoding circuit 12 is arranged adjacent to the right side of the corresponding partial product generation circuit 11. In the second block B2 located in the lower stage of the first block B1, each encoding circuit 12 counts 6 from the right side among the plurality of multiplier cells 13 arranged in the corresponding partial product generation circuit 11. The seventh and seventh multiplier cells 13 are inserted. Similarly, in each block, each encoding circuit 12 has a plurality of multipliers in the corresponding partial product generation circuit 11 so as to be closest to the wiring for transmitting the 3-bit multiplier data input thereto. It is inserted and arranged in the middle of the array of cells 13. Incidentally, in the r-th block Br at the bottom, each encoding circuit 12 has the second and third counting from the left side among the plurality of multiplier cells 13 arranged in the corresponding partial product generation circuit 11. Insertion is arranged between the multiplier cells 13.
[0027]
The wiring of the multiplicand X exemplifies only x ₁ ~x _7. The multiplicand X is input in parallel to a plurality of multiplier cells 13 in each partial product generation circuit 11.
[0028]
Since the encoding circuit 12 using the secondary Booth algorithm is provided, the multiplier cell 13 in the partial product generation circuit 11 located on the higher bit side than the encoding circuit 12 is as shown in FIG. Each output is shifted by 2 bits to the lower bit side (2 bit shift).
[0029]
In the multiplication circuit configured as described above, the partial product output from the partial product generation circuit 11 at each stage is shifted by the amount of insertion of the secondary Booth encoding circuit 12 in the partial product generation circuit 11. Thereafter, the desired multiplication result can be obtained by adding the partial products using the partial product adding circuit 20 as in the conventional multiplication circuit.
[0030]
In the multiplication circuit of the above embodiment, each encoding circuit 12 is arranged at a position that matches the bit position of the input multiplier data so as to be closest to the wiring that transmits the 3-bit multiplier data input thereto. Has been.
[0031]
For this reason, it is not necessary to route the wiring of the multiplier data long and input it to each encoding circuit 12 as in the prior art. As a result, even if the number of bits of the multiplier Y is increased, a wide wiring area is not necessary for the wiring of the multiplier Y, and the wiring area of the multiplier Y can be reduced as compared with the related art.
[0032]
Further, since it is not necessary to route the multiplier data wiring for a long time as in the prior art, redundant data movement can be eliminated, and an increase in time required for partial product generation can be prevented.
[0033]
FIG. 3 is a diagram illustrating an example of an encoding state of the encoding circuit 12 in FIG. “Multiple” in FIG. 3 indicates a numerical value for multiplying the multiplicand X based on 3-bit multiplier data (y _2k , y _{2k + 1} , y _{2k + 2} ). 3 is represented by 3-bit code data X, 2X, NEG. For example, when y _2k = y _{2k + 1} = “0” and y _{2k + 2} = “1” in the second stage in FIG. 3, the multiple is −2, and this multiple sets the code data 2X to “1”. By double, the code data NEG is set to “1” to indicate that the multiple is a negative value.
[0034]
FIG. 4 shows a specific circuit example of the encoding circuit 12 that realizes the encoding state shown in FIG. Multiplier data y _2k and y _{2k + 1} are input to an exclusive OR gate 31, and code data X is output from the exclusive OR gate 31. Further, multiplier data y _{_2k,} y _2k _{+ 1} is directly and multiplier data y _{2k + 2} in the inverted data are input to the AND gate 32, further multiplier data y _{_2k,} y _2k _{+ 1} each inverted data and multiplier data y _{2k +2} is input to the AND gate 33, the outputs of the AND

gates

32 and 33 are input to the OR gate 34, and the code data 2X is output from the OR gate 34. The multiplier data y _{2k + 2} is output as it is as code data NEG.
[0035]
FIG. 5 is a circuit diagram showing a configuration example of one multiplier cell 13 in the partial product generation circuit 11 in FIG. The multiplier cell 13 is composed of two AND

gates

41 and 42, and one OR gate 43 and an exclusive OR gate 44. The AND gate 41 receives multiplicand data xj-1 and code data 2X. The AND gate 42 receives the multiplicand data xj and the code data X. The outputs of the AND

gates

41 and 42 are input to an OR gate 43, and the output of the OR gate 43 is input to an exclusive OR gate 44 together with code data NEG. Then, a partial product for one bit is output from the exclusive OR gate 44.
[0036]
Note that the encoding state of the encoding circuit 12 shown in FIG. 3, the specific circuit configuration of the encoding circuit 12 shown in FIG. 4, and the specific circuit configuration of the multiplier cell 13 shown in FIG. 5 are merely examples. It does not necessarily have to be this way.
[0037]
In the above-described embodiment, the case where the multiplicand X and the multiplier Y are input from above the circuits of the plurality of stages constituting the multiplication array 10 has been described. For example, the multiplicand X is input from above and the multiplier Y is input. As is inputted from below, the wiring may be changed so that the multiplicand X and the multiplier Y are inputted from opposite directions.
[0038]
Further, in the above-described embodiment, as shown in FIG. 1, the case where the encoding circuits 12 are all arranged at the same position with respect to the partial product generation circuit 11 in each block has been described. You may make it arrange | position to. In short, the encoding circuit 12 may be arranged at a position that matches the bit position of the 3-bit multiplier data that is input to each.
[0039]
【The invention's effect】
As described above, according to the present invention, it is possible to provide a multiplication circuit capable of reducing the wiring area by shortening the wiring length of the wiring for transmitting multiplier data.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a multiplication circuit according to an embodiment of the present invention.
2 is a circuit diagram showing an extracted circuit composed of a partial product generation circuit and an encoding circuit for one stage in the multiplication circuit of FIG. 1;
FIG. 3 is a view showing an example of an encoding state of the encoding circuit in FIG. 1;
4 is a diagram showing a specific circuit example of an encoding circuit that realizes the encoding state shown in FIG. 3; FIG.
5 is a circuit diagram showing a configuration example for one multiplier cell in the partial product generation circuit in FIG. 1; FIG.
FIG. 6 is a block diagram showing a configuration of a conventional multiplication circuit.
7 is a circuit diagram showing an extracted circuit composed of a partial product generation circuit and an encoding circuit for one stage in the conventional multiplication circuit of FIG. 6;
[Explanation of symbols]
10 ... multiplication array,
11 ... Partial product generation circuit,
12 ... Encoding circuit,
13 ... multiplier cell,
20: Partial product addition circuit.

Claims

A plurality of encoding circuits for outputting code data by inputting a part of bit data among multiplier data composed of a plurality of bits;
Multiplicand data composed of a plurality of multiplier cells provided corresponding to the plurality of encoding circuits and arranged in rows, respectively, and composed of a plurality of bits of data input from the same direction as or opposite to the multiplier data; A plurality of partial product generation circuits for generating partial products from code data output from the corresponding encoding circuit;
A partial product addition circuit for adding the partial products generated by the plurality of partial product generation circuits and outputting a multiplication result,
Each of the plurality of encoding circuits is arranged at a position suitable for a bit position of input multiplier data.

Among the plurality of encoding circuits, a part is arranged at a position adjacent to the corresponding partial product generation circuit, and a part is inserted in the middle of the arrangement of the plurality of multiplier cells of the corresponding partial product generation circuit The multiplication circuit according to claim 1, wherein:

3. The multiplication circuit according to claim 1, wherein each of the plurality of encoding circuits is a Booth encoding circuit.