High-speed digital bus-organized multiplier/divider system

Abstract

Abstract A bus organized 16×16 (or 8×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 INVENTION High 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 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×8 to a 16×16 or a 32×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×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×16 multiplier on a single integrated circuit chip and further to implement a 16×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 INVENTION It 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.

Inventors

• 👤 Robert C. Ghest
• 👤 John M. Birkner
• 👤 Shlomo Waser
• 👤 Hua T. Chua

Bibliographic Details