JPS6238938A - ROM type multiplier - Google Patents

Abstract

PURPOSE:To greatly reduce the capacity of a ROM by finding a partial product by using ROMs as many as combinations of plural decomposed numerals and adding the plural partial products together, and thus obtaining the composite product. CONSTITUTION:At least one numeral between a multiplicand X and a multiplier Y is divided into plural partial numerals, and partial products based upon all combinations of respective partial numerals of X and partial numerals of Y are calculated in ROMs and summed up to find the product P=X.Y. Thus, a practical ROM type multiplier in which the capacity of the ROMs is reduced greatly is obtained.

Description

[Detailed Description of the Invention] [Industrial Application Field] This invention provides an RO that implements a multiplier using ROM'i.
This is a ROM type multiplication type container with a significantly reduced amount of ROMg among M type multiplication types.

[Conventional technology]

FIG. 4 is a diagram of the simplest ROM type multiplicative container. In the figure, the multiplicand X and multiplier Y of the double code are ROM (
'1oo), and the product P corresponding to the address value is obtained from the output terminal after a predetermined access time. In other words, the product result of p=x-y is stored in ROM
(11oo) as data, and the multiplicand X and multiplier Y are configured to be input as ROM address signals.

For example, X=233=ゝゝ11101001'' and Y=1
91:=010111111”, Y
A composite address = ``1110100110111111'' where is the lower address and x all upper addresses is input to the address terminals (16) of the ROM. At this time, the ROM
If all the multiplication results of p=x-y are stored in 16 bits in advance, the product P=X-Y='ゝ10101
10111010111'' can be obtained.

This is an outline of the operation of a ROM type multiplicative container.

By the way, the wave &X and the multiplier Y are 8 bits (0≦X≦2
55. When O≦Y≦255), the output data is 16 bits and the number of addresses is 211 × 28 == 2t.
It becomes 6. Therefore, the total ROM capacity T, is T, = 1
6X2'6=10485'76 bits. This is 1M bits, which is a large value for a ROM capacity. Next, if we calculate from the ROM capacity when X and Y are 16 bits, Tb - 32 bits X2 X2 = 2
becomes. This number is not achievable.

[Problem that the invention seeks to solve]

Since the conventional ROM type multiplier is configured as described above, it is an intuitive and easy-to-use circuit, but its RO
Since the M capacity is enormous, there is a problem that it cannot be realized, or even if it can be realized, it is not practical.

This invention was made to solve the above problems, and it is a practical ROM with significantly reduced ROM capacity.
The purpose is to obtain a shaped multiplier.

[Means for solving problems]

In the ROM type multiplier according to the present invention, at least one of the multiplicands X and the multiplier Y is divided into a plurality of partial values, and partial products of all combinations of each partial value of X and each partial value of Y are Each of these partial products is obtained using a ROM, and these partial products are combined and added using an adder to obtain the product P=X-Yi.

[Effect]

In this invention, the numerical values of the multiplicand X and the multiplier Y are each divided into partial numerical values, and these are used to calculate the partial products in the ROM, so that the bit capacity required for the ROM is significantly reduced.

〔Example〕

FIG. 1 is a block diagram showing an embodiment of the present invention.
When the multiplicand X and the multiplier Y are both 8 bits,
+X 4 ・2' +Xs ・2””) [2・22
")CI'" +X6=(x 712"+xa ・2
"+x6 ・2+X4) ・2'"(xa ・23+X
2 ・2”+x 1・2+XQ)=X −2'+X
Similarly, it is expressed in the form Q L Y-YU"' +YL-c.

And the product p=x-y is P=X-Y=XU4.・28+XtI+YL-2'+X
Q14 partial products X[
1''[1,

In FIG. 1, a first ROM (hereinafter referred to as ROM IJ) (101) to a fourth ROM (ROM4) (1
04) are the partial products X, ・Ywa, XII-YL, and X, respectively.
This is a ROM that stores data of L-YU, x, ・YL, and each ROM address terminal has a 4-bit XLI
, xL, YU, and YL are connected as a composite address as shown in the figure. Number of addresses per ROM is 2-25
6, and each partial product output data is 8 bits. These partial products output bootara x. -YU's data is 8
Execute a bit carry, X, YL and XL-YU execute a 4-bit carry, and add xL'YL and the full adder (li'UI, L ADDER) (105). The product P is obtained.

In this case, due to the ROM capacity, the total of 4 pieces is 'I' =
2'X2'X (8 bits) x 4C) = 8192 pits. This is a value of 1/(12B) compared to the conventional one, and a significant reduction in ROM capacity can be achieved.

Next, verify with actual numbers.

X=233. Assuming multiplication of Y-191, XU=
8 (1) + 4 (1) + 2 (1) + 1 (0)
= 14XL=8(1)+4(0)+2(0)+4(1
)=9yO=8(1)+4(o)+2(1)+
Ut) = 11YL = 8(1) +4(1)+2(
1) + 1 (1) 215 times, (1)=ゝゝH''=ゝゝ3-1/(o)=111// becomes It□ l/, XU-YU=14X11=154, XU −
YL=14X15=2.10, X-Y=9X1
1=99, XL-YL=9X15=135
・U can be obtained as 8-bit ROM output data.

and tL et al. 0 binary code 'ili' UL, L ADDER (
If you calculate lI19te, /Jl, you will get the product P. This process is shown below.

XtI-YO= 10011010←8 bit shift-X-Y: 11010010←2
2. −X L−YtI =
01100 01 1+-, XL-YL=+)
10000111P =
1010110111010111 The double code of the product P is P = 2” (1) + 2”@+ 213 (1)
+ 212 (0) + 2 ” (1) + 2” (1) +
2' (0) + 28 (1) + 27 (1) + 26 (
1) + 25(o)+ 2'(1)-1-z3(o)+
2"(1) + 2'(1) + 2°(1). This is expressed as P=44503 in decimal notation, P=X-Y=2
Matches 33X191=44503. Therefore, the algorithm of the present invention is valid. The circuit of FIG.
The configuration is to use four OM'i in parallel, but the RO
Using only one M'i, execute 4 access fs and sequentially xU-yU, x,, yL, xL-yff, xL
-x.

A ROM type multiplier can also be realized using the method of determining . FIG. 2 shows another embodiment of the invention based on this system. In the figure, (106) is xII・YUj x[1”LI
Selector (107) that generates the composite address of L”ITIXL-xL is D that temporarily stores ROM output data.
FE', (108) is the selector (106) and DF
This is a control circuit that synchronizes with F (107) and sequentially executes four ROM accesses. The operation is first
The YL composite address signal is selected as the output of the selector (1Oa), and data corresponding to this address value is output from the ROM l (lol) after a predetermined access time, and this output data is used as D F F (10'7). D]
i'li'l memorize it.

Similarly, the value of xL"U is set to '1DFF2, xU 'Y
The value of L is stored in DF1i'3, and finally the values of xU and YU are obtained. These data are FULL ADDER (1
05) and add them according to the composition formula, a multiplier can be realized with a capacity of 〇 that can obtain the desired value. At this time,
Since the same ROM is accessed 14 times, the time required to obtain the product P'ilH is approximately four times that in FIG. 1.

Until now, we have explained about the 8x8 bit multiplier, but
Next, a description will be given of the theoretical ROM capacity when nXn bits are divided into N and M to generate partial products, and product P is obtained by combining and adding the partial products. Figure 3 shows the division. Wave multiplier '#, divide X into N, multiplier Y'f: M
Assume that it is divided. At this time, the divided address space consists of 21×2M addresses, and the number of data bits per address is (-+-). Since the total space is HM times M of one divided address space, the required ROM capacity T, is T, = (
2irxaM)x(-+-)X(N-M)M. In this equation, n=8. Substituting N=M=2f,
T, =(2X2)X(4+4)X(4)=2=
8192 bits, which corresponds to the numerical value in the description of the embodiment of FIG.

Here, n=46. Under the condition N=M=4, T,=(2
X2)X(4+4)X16=32768 bits. Therefore, 32. 1 with a ROM capacity of 768 kilobits
A 6×16 bit ROM type multiplier can be realized. Of course, if the circuit configuration shown in FIG. 27112 is expanded to support 16 bits, it can be realized with a ROM capacity of 2 kbits, but this has the disadvantage of slow multiplication speed.

As explained above, the nXn bit multiplier is
Although it can be implemented with a ROM, increasing the ROM capacity can reduce random logic circuits and provide high multiplication speeds. On the other hand, if the ROM capacity is reduced, the number of random logic circuits will increase and the multiplication speed will become slower. Therefore, depending on the purpose of use, ROM
Capacity needs to be determined.

In the above embodiment, the number of addresses is divided into units of 4 pits, but it may be divided arbitrarily in consideration of the purpose, characteristics of the device used, circuit scale, multiplication speed, etc.

Also, as a modification of Fig. 2, DI"F (10'7) and FU
LL(9) ,,1ADDE
R(105) may be replaced with an accumulative adder.

Finally, not limited to nXn bit multipliers, but general α×β
A bit multiplier can also be similarly implemented using the gist of the present invention.

〔Effect of the invention〕

As described above, according to the present invention, the multiplicand X and the multiplier Y
decompose at least one of them into the sum of multiple numbers, use ROM to find partial products as many times as there are combinations of the decomposed multiple numbers, and finally perform synthetic addition of the multiple partial products to obtain the product p=x
-y, it is possible to achieve a significant reduction in ROM capacity, which has the effect of making it a practical ROMM multiplier.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a ROM type multiplier according to an embodiment of the invention, FIG. 2 is a block diagram showing another embodiment of the invention, and FIG. FIG. 4, which shows one form of division, is a block diagram showing a conventional ROM multiplier. In the figure, (101) to (105) are ROM, (1
05) is an adder. Note that the same reference numerals in the figures indicate the same or corresponding parts.

Claims (1)

[Claims] (1) Decompose the value of at least one of the multiplicand and the multiplier into the sum of multiple partial values, and send data obtained from all combinations of each partial value of the multiplicand and each partial value of the multiplier to an address signal. is input into the ROM as the address input signal, and the product of the partial numerical values of the address input signal stored in advance corresponding to each address data is used as the partial product to obtain the corresponding R.
A ROM-type multiplier characterized in that the product of the multiplicand and the multiplier is obtained by obtaining the output data of an OM and combining and adding these partial products.