公开(公告)号：US4153938A

公开(公告)日：1979-05-08

申请号：US825648

申请日：1977-08-18

Applicant: Robert C. Ghest ,  Hua-Thye Chua ,  John M. Birkner

Inventor： Robert C. Ghest ,  Hua-Thye Chua ,  John M. Birkner

IPC: G06F7/52

CPC classification number: G06F7/5338 ,  G06F7/49963

Abstract: This disclosure relates to a high speed combinatorial 8 by 8 digital multiplier suitable for implementation on a single semiconductor chip including an encoder for implementing the Modified Booth Algorithm to encode the eight multiplier digits. The encoder includes five subsections which generate a plurality of control signals. Each of the plurality of control signals is inputted into a separate one of five multiplexor circuits each of which also receives inputs representative of eight multiplicand bits in accordance with implementation of the Modified Booth Algorithm. Each of the five multiplexer circuits provides a plurality of outputs, each of the pluralities of outputs representing a separate partial product of the multiplier and multiplicand inputs. The partial products are inputted to an array of carry-save adders. The final stage of the adder network includes a carry-look-ahead adder which produces sixteen outputs which represent the product of the multiplier and the multiplicand. The multiplier includes circuitry for permitting encoding of the multiplier inputs in either binary unsigned or in two's compliment form. A multiplier mode control input controls whether the multiplier inputs are operated upon as two's compliment or as unsigned binary numbers. Similarly, a mode control input to circuitry which generates the multiplexer inputs representative of the multiplicand also controls whether the multiplicand inputs are operated upon as two's compliment numbers or as unsigned binary numbers. The mode of the multiplier inputs and multiplicand inputs can be independently controlled, so that mixed signed and unsigned representations of the multiplier and multiplicand, respectively, can be utilized.

Abstract translation: 本公开涉及一种适用于在单个半导体芯片上实施的高速组合8×8数字乘法器，包括用于实现修改的布尔算法来编码八个乘法器数字的编码器。 编码器包括产生多个控制信号的五个子部分。 多个控制信号中的每一个被输入到五个多路复用器电路中的单独一个，每个复用器电路还根据修改的布尔算法的实现接收表示八个被乘数位的输入。 五个多路复用器电路中的每一个提供多个输出，多个输出中的每一个表示乘法器和被乘数输入的单独的部分乘积。 部分产品被输入到一个携带保存加法器阵列。 加法器网络的最后阶段包括进位前瞻加法器，其产生十六个输出，其表示乘法器和被乘数的乘积。 乘法器包括允许以二进制无符号或二进制补码形式对乘法器输入进行编码的电路。 乘法器模式控制输入控制乘法器输入是以二进制补码或无符号二进制数进行操作。 类似地，产生代表被乘数的多路复用器输入的电路的模式控制输入也可以控制被乘数输入是以二进制编号或无符号二进制数进行操作。 可以独立地控制乘法器输入和乘法器输入的模式，从而可以利用乘法器和被乘数的混合有符号和无符号表示。

公开(公告)号：US4238833A

公开(公告)日：1980-12-09

申请号：US24540

申请日：1979-03-28

Applicant: Robert C. Ghest ,  John M. Birkner ,  Shlomo Waser ,  Hua T. Chua

Inventor： Robert C. Ghest ,  John M. Birkner ,  Shlomo Waser ,  Hua T. Chua

IPC: G06F7/52

CPC classification number: G06F7/5338 ,  G06F7/535 ,  G06F2207/5352

Abstract: A bus organized 16.times.16 (or 8.times.8) high-speed digital bus-organized multiplier/divider for high-speed, low-power operation is implemented on a single semiconductor chip. Four working registers each of 16 (or 8) bits are used in the system. These registers are a multiplier register, a multiplicand and divisor register, a first accumulator register for storing the least significant half of a double length product after a multiplication of the remainder after a division operation, and a second accumulator register which stores the most significant half of the product after a multiplication or the quotient after a division operation. A decoder is connected to the multiplicand and multiplier registers to implement the Modified Booth Algorithm and to encode the 16 (or 8) multiplier digits. The system operates to shift the multiplier number through the multiplier register to a position where the Modified Booth Algorithm encoding takes place. The Modified Booth encoder then controls the operation of multiplexer circuits to which the outputs of the multiplicand register are applied to produce successive partial products. A carry/save arithmetic logic unit operates in conjunction with the registers to cause accumulation and storage of multiplication products and division quotient/remainders in the double length accumulator registers which provide a 32 bit output number. BACKGROUND OF THE INVENTIONHigh speed digital multipliers and digital dividers have a wide number of applications in digital signal processing. Multiplication or division of binary numbers can be performed in a relatively simply manner. For multiplication, a classic approach is to provide an accumulate register which has twice the length n of the operands, because the product can approach twice the size of the operands. The multiplier is conveniently stored in the less significant half of the accumulator register. The most significant half and the contents of a multiplicand register are applied to an adder. The output of the adder is effectively the sum of the accumulated partial products and the potential partial product consisting of one times the multiplicand. A series of n cycles is set up. For each cycle, the least significant bit of the accumulator is examined; and the output of the adder is stored in the more significant half of the accumulator or not, in accordance with that bit being a binary "1" or a "0", respectively. The accumulator then is shifted to the right one bit, and the cycle is repeated until the entire multiplier has been examined. As a consequence, the multiplicand has been multiplied by 2.sup.n, for every "1" bit in the multiplier; and these partial products have been accumulated with the proper alignment due to the cyclic shifts which divide the result by 2 in each cycle. Various techniques exist in the art for handling different sign combinations of the operands, for the different types of number representations, that is, sign and magnitude, 1's complement and 2's complement.A problem which exists with a digital multiplier of the type just described is that for 16 bit operands, the process calls for 16 cycles to obtain each of the 16 different partial products. These partial products then are added together in an additional 16 adder circuits to obtain the final resultant product, and all of the gates and other circuitry results in dissipation of a substantial amount of power. In addition, as the size of the multiplier increases (for example from an 8.times.8 to a 16.times.16 or a 32.times.32 multiplier), the length of time for accomplishing the multiplication increases in direct proportion.Because of the large number of circuit components which are necessary with such a prior art approach, implementation of large multipliers on a single LSI chip has not proved practical. As a result such circuitry is usually implemented in several chips which must be interconnected together externally to form the complete circuit.Another disadvantage with the standard prior art approaches is the dissipation of relatively large amounts of power, so that it is necessary to employ forced air cooling or other types of cooling during the operation of the system. The resultant machine is correspondingly increased in complexity and cost as a result of the relatively high power dissipation.A solution to some of the problems inherent in the prior art is disclosed in U.S. Pat. No. 4,153,938 issued May 8, 1979 filed on Aug. 18, 1977 and assigned to the same assignee as the present application. In this copending application, a high speed 8.times.8 digital multiplier is implemented in a single LSI chip using circuitry for implementing a Modified Booth Algorithm to examine the binary multiplier 3 bits at a time and shifted 2 bits at a time in sequence for performing the multiplication function. In the copending application, this examination is effected through the use of several Modified Booth encoder gating circuits, each responsive to a different group of 3 bits of the multiplier input register, for controlling the shifting of the outputs of the multiplicand register applied to the input of an array of carry/save adder circuits to effect the desired multiplication. The result is a reduction in the number of cycles required to complete the multiplication operation and a reduction in the circuitry necessary to carry it out, along with reduced power dissipation.It is desirable to implement a 16.times.16 multiplier on a single integrated circuit chip and further to implement a 16.times.16 multiplier/divider system on a single IC chip for high speed operation with minimal power consumption. Other features which are desirable in such multiplier/divider circuits, and which are particularly desirable in circuits implemented in a single integrated circuit chip, are the ability to multiply and accumulate in a single cycle of operation, to perform the entry of new data from the input busses simultaneously with the processing of previous entries, and the multiplication or division of new entries or accumulated entries by a constant.SUMMARY OF THE INVENTIONIt is an object of this invention to provide an improved high-speed digital multiplier.It is another object of this invention to provide an improved high-speed digital multiplier/divider.It is an additional object of this invention to provide a high-speed digital multiplier of at least 16 bits by 16 bits on a single semiconductor chip.It is still another object of the invention to provide a high-speed digital multiplier/divider on a single semiconductor chip having reduced power dissipation.It is still a further object of this invention to provide a bus organized multiplier/divider having a variety of different multiply and divide options controlled by external instruction signals.Yet another object of this invention is to implement a high-speed, low-power dissipation digital multiplier/divider system utilizing circuitry which generates a reduced number of partial products.In accordance with the preferred embodiment of this invention, a digital multiplier circuit includes registers for receiving the multiplier inputs and the multiplicand inputs. A partial product generator coupled to the registers includes an encoder which encodes the multiplier inputs according to the Modified Booth Algorithm to produce control signals which are applied to a plurality of multiplexer circuits interconnecting the multiplicand register with the partial product generating circuitry to produce the resultant number. The information in the multiplier register is shifted on a step-by-step basis through the register to present the contents of the register to the encoder circuitry; so that only a single Modified Booth Algorithm encoder circuit is required, irrespective of the length of the multiplier in the multiplier register.In more specific embodiments of the invention, accumulator registers are provided and the system includes operating mode control circuitry for permitting operation of the system either as a multiplier or as a divider. In addition, a state counter is used in conjunction with external mode control signals applied to the circuit to permit a variety of multiplication and accumulation functions as well as a variety of divider functions to be accomplished by the system. These functions include positive and negative multiplication, positive and negative accumulation, multiplication by a constant, and both single and double length addition in conjunction with mmultiplication, along with divide options including single or double length division, division of a previous generated number, division by a constant, and continual division of a remainder or quotient.

Abstract translation: 在单个半导体芯片上实现了一个总线，用于高速，低功耗操作的16x16（或8x8）高速数字总线组合乘法器/分频器。 系统中使用16个（或8）位中的每个工作寄存器。 这些寄存器是乘法器寄存器，被乘数和除数寄存器，第一累加器寄存器，用于在除法运算之后的余数相乘之后存储双倍长度乘积的最小有效半，以及存储最高有效半 乘法后的乘积或除法运算后的商。 解码器连接到被乘数和乘法器寄存器以实现修改的布尔算法并对16（或8）个乘法器数字进行编码。 该系统操作以将乘数通过乘数寄存器移动到发生修改展位算法编码的位置。 修改后的编码器然后控制多路复用器电路的操作，多路复用器电路被应用寄存器的输出以产生连续的部分乘积。 进位/保存算术逻辑单元与寄存器一起运行，以使倍增乘积的积累和存储以及提供32位输出数的双倍长度累加器寄存器中的除法/余数。