JPS5911939B2 - Fugoutukikakezanronrisouchi - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a multiplication logic device for multiplying two serial binary numbers to obtain a serial binary product.

This multiplication and the logic circuit that performs it may hereinafter be referred to as signed. The multiplicand has information representing the size and sign expressed in two's complement notation, the multiplier has information on the size, and the product has information representing the size and sign expressed in two's complement notation. , and all three bit strings appear in series at the same word rate, with the least significant bit appearing first in time. The logic device is comprised of a plurality of generally identical multiplying cells that form partial products that are summed by generally identical summing cells to form the final product.
Each multiplication cell stores multiplier bits and includes one stage of multiplicand shift register and one stage of timing waveform shift register. Under the control of timing waveform,
A means is provided to truncate the multiplicand and round the product. The logic unit is flexible and can form products with either single precision or double precision. The design, which uses two types of roughly identical cells and minimizes communication channels at the cell and periphery of the multiplication logic device, is ideal for large-scale integration using metal-oxide-semiconductor field-effect transistor technology. It's getting old.

In summary, this invention relates to the field of digital computing, and more particularly to the field of digital computing, and more particularly to the field of serial computing, where two series numbers are multiplied to yield a series output, with the product reflecting the sign of the multiplicand. Concerning formal logic devices.

The invention also relates to means for efficiently obtaining products with single precision or double precision. This accuracy will be explained later. The invention utilizes logic functions that are particularly suited to large-scale integration. For the multiplication of two binary numbers of m and n bits, the product is typically (m+n
) bits. Assuming that m and n are equal, the product is 2m (or 2n) bits, which is called double precision. In the normal case, the digits of the operand are available only in the ranges listed above, so the lower half of the bits in the product may not be useful, and in some cases the digits present in the operand may not be useful. (or other) errors. If the operand and the product are serial, create a double-precision product,
Subsequent rounding to a reasonable word length may be practically wasteful in terms of time and equipment. In many computing devices, the series format is particularly attractive, such as when the number of input and output terminals is limited, and this is efficiently implemented in metal oxide semiconductor integrated circuit formats.

Typical signal and data processing requires the ability to handle sign and magnitude information. One of several known formats for signed operations is two's complement notation. In the September 1968 issue of IEEE Transactions on Audio and Electroacoustics, an article entitled "An Approach to the Implementation of Digital Pourders" describes single precision. A multiplication device is described in which the input and output are serial, but the operands must be positive.

Proceedings of the National Electronics Conference 1969 Seifard's paper [Design of Digital Pourdaas]
'Use Inc. Read Only Memories' includes
A series-parallel multiplication device using a read-only storage device is described for adding partial products. The realization of certain logic functions in a form suitable for large-scale integration in MOS technology was developed by Juan Nosland Reinbold in 1972.
It is described in the book ``MOS Integrated Circuits'' edited by William M. P. and Lillian Lo, published by Co., Ltd.

It is an object of this invention to provide an improved serial multiplication device.

Another object of the invention is to provide an improved serial multiplier in which at least one operand is signed.

Another object of the invention is to provide an improved serial multiplier that allows single or double precision products to be obtained without additional time.

A feature of the invention is that when large-scale integration is achieved by using repetitive cells of the same design, communication paths at the periphery of the cells and devices are minimized, and the shape is minimized. An object of the present invention is to provide an improved serial signed multiplication device. Another feature of the invention is the provision of such an apparatus for performing multiplication on real or complex numbers (having real and imaginary parts).

The present invention is realized by a novel signed multiplication logic device designed to multiply two serial binary numbers to obtain a series two product.

The multiplicand has information representing the magnitude and sign expressed in two's complement notation, the multiplier has information representing the magnitude, and the product represents the magnitude and sign expressed in two's complement notation. The bit sequences of the multiplier, multiplicand and product appear serially at the same word rate, with the least significant bit appearing first in time. In the present invention, a multiplication logic device is coupled to a bus supplying a sequence of multiplier bits and stores successive words of the sequence of multiplier bits, each storage element of which is scheduled from each serial multiplier word. a plurality of binary storage elements for selecting a bit of the order of bit and storing the selected bit until a bit of the same order appears in a subsequent word;
A shift register having a plurality of connections at 1-bit intervals to which the multiplicand bit string is supplied, a plurality of multiplication stages, and a shift register coupled to the output of each multiplication stage, which multiplies the bit strings representing partial products. and an adder circuit for combining into a single equal bit string, each multiplier stage being connected to feed a binary bit into a binary storage element and feeding the multiplicand into a junction of a multiplicand shift register. Connected like this, the shift/
The cumulative delay amount of the register increases according to the digit of the multiplier bit sent, and each stage successively selects the most significant bit of the multiplicand word and multiplies it by the multiplier bit to correspond to that digit. It is designed to form partial products in series with time.

In another aspect of the invention, the multiplication stage includes means for feeding less than all the bits of the multiplicand, and truncates the least significant bit in inverse proportion to the order of the multiplier bits fed.

In particular, the means for truncating the multiplicand bits is provided with means for generating a timing waveform having a portion whose duration is equal to the bit time of the multiplier;
and a second shift register having connections at 1-bit intervals. Each multiplier stage is connected to a timing shift register, and a timing signal is provided for controlling the number of high order bits of the multiplicand to be sent so that the number of multiplier bits to be sent corresponds to the place of the multiplier bits to be sent. is required. Multiplication is performed by a three-input gate to which the delayed multiplicand, stored multiplier bits, and timing signals are applied.

The connection time of the timing signal at each stage increases by one bit increments according to the delay added to the timing waveform. 3
An input gate ANDs the three inputs and produces an output.

In another aspect of the invention, each multiplier stage is provided with a bus that generates a timing signal that controls the feeding of the multiplicand bits.

A timing gate has one input coupled to a constant delay timing waveform bus to initiate the timing signal and another input to a timing waveform shift register to terminate the timing signal. Additionally, each multiplier stage has means, responsive to the timing signal, for repeating the sign bit of the multiplicand as many times as necessary to complete the upper portion of the partial product.

At this time, a partial product having a full length can be obtained by ORing the output of the three-input gate and the output of the code repeating means. Addition of the partial products is performed by an adder divided into a series of digits.

Each adder has two serial data inputs,
A serial data output representing the sum of the two inputs is produced after a one bit delay. The summing devices are arranged in successive stages until the serial data is combined into a single stream. Each adder is also provided with means for resetting an internally stored carry bit as the least significant bit of each word passes through. The reset means comprises one or more reset pulse generators timed by connections to timing waveform registers, each of which generates an internally stored carry bit at the appropriate time. generates an output pulse that resets the The adder in the last place has means for zeroing one or more least significant bits of each word of the series product. A rounding value is introduced to compensate for truncation of the multiplicand as well as the product.

The rounding value means consists of one or more pulse generators and an OR gate for generating the rounded value, each pulse generator having an input coupled to a connection of a timing waveform register and having a predetermined value. It senses that the timing waveform passes at a time corresponding to the first digit bit being fed into the first digit adder and generates an output pulse at this time. The output of the pulse generator is coupled to the OR gate to generate the rounded value and one or more output pulses corresponding to the desired rounded value. Or
The output of the gate is coupled to the input of the adder in the first place and added to the final product. The block diagram shown in FIG. 1 is an example of the signed multiplication logic device of the present invention.

A multiplication logic unit 11 connects two sources 12,1 of serial input data.
3 to produce a single-precision product, also in serial form. Very efficient use of time when performing multiplication of two serial input numbers.

Signed multiplication logic units generate single precision products requiring only one extra bit per word than the multiplicand. If the multiplicand is 12 bits, a 10-bit output product is formed during an output word period of 13 bit times. The length of the multiplier is constant. The multiplicand is variable in length and is typically longer than the multiplier. The signed multiplication logic unit 11 performs a so-called two-quadrant multiplication. The multiplicand (a) from source 12 is expressed in two's complement notation and can be positive or negative. The multiplier 1bI from source 13 is of magnitude only. The output of the signed multiplier 11 is the product a-1bI, expressed in two's complement notation. The operand a is originally expressed in two's complement notation and has both size and sign information, and both are included in the product. However, even if the multiplier 1b1 is introduced as information about the magnitude only, that term represents only the magnitude. this. S. Assuming the product of two real operands to be their signs, this device has 2
It can be characterized as a quadrant device (+a), (+b); (-a), (+b).

Multiplication of 4 quadrants, i.e. (+a)・(+b); (−a)・(+b): (+a)・
(-b): In order to perform (-a) and (-b), if you want to input sign information to multiplier b as well, input the sign of multiplier b from a separate source 14, and add it to the two's complement converter 15. can be controlled.

This complementer is a signed multiplier 1 as shown in FIG.
1 output. In this way, the complementer 15
The output product has size and sign information reflecting both operands, and is expressed in two's complement notation. The signed multiplication logic device of this invention has two
may be used with the two's complementizer 15, or when the sign of the multiplier is always positive, without using the two's complementer, a-1b
You can also find the amount of 1.

This invention can also be used for four-quadrant multiplication of complex numbers, as shown in FIG.

In this figure, the first complex number (a+Jb) is added to the second complex number (
c+Jd). j represents an imaginary number, and i is used for this purpose in some literature. The product of multiplication is the real part (Ac-Bd) and the imaginary part j (Ab+Bc)
It can be expressed as having . Multiplicand a1 added to the inputs of signed multipliers 1 and 3 Signed multiplier 2
, 4 is in two's complement form. The multipliers added to the other inputs of signed multipliers 1 to 4 have magnitudes 1c1, 1d1, 1dI and 1ci, respectively. The outputs of signed multipliers 1 to 4 are a and 1c, respectively.
1, b-1d1, a.:d: and b-1c1. 2
The data inputs of complementizers 5, 6, r, and 8 are connected to the respective outputs of signed multipliers 1 to 4, and the product of the outputs is expressed as
true 4 containing sign and magnitude information of both operands
Convert to quadrant quantity.

Therefore, code information corresponding to the absolute value of the multiplier is coupled to the code input of the two's complement converter. Sign input Sd and Sd
are the sign of d and the inverted sign of d, respectively, and the same is true for SO. That is, the sign of the multiplier C is added to the two's complementer 5, the sign of d is added to the two's complementer 6, and (factor J2
The sign of the multiplier d is added to the two's complementer 7 and the sign of the multiplier c is added to the two's complementer 8. At the outputs of the four two's complement converters 5 to 8, complete four-quadrant multiplication of the operands is performed, and the product is expressed in two's complement notation. The complex product is obtained by combining the outputs of the four two's complementers 5-8.

The real part of the output is Ac-Bd, and the two's complement converter 5,
6 is formed by combining the outputs of 6 in an adder 9. Similarly, the imaginary part of the output is J(Ad+Bc) and is formed by combining the outputs of two's complementers 7 and 8 in addition device 10. In FIG. 1, the element 15 and the second
A preferred example of a series two's complementer, shown as elements 5 to 8, is shown in detail in FIG.

However, two's complementizers are well known and any suitable conventional equipment may be used. A 2's complement converter converts a serial binary number into 2
It is expressed in the notation of the complement of , and is designed to change the algebraic sign when desired.

The two's complementizer converts the quantity a·1bI(2
(expressed in complement notation), thus reflecting the influence of the sign of the quantity Ibl.

The product of the outputs at 16 is a-b (expressed in two's complement notation) and reflects the signs of both inputs.

The logical design of a two's complementizer is illustrated in FIG.

This selectively uses a Nando machine. This design allows metal oxide semiconductor field effect transistors (MOS
When integrated on a large scale using FETs, the minimum form factor is achieved. As shown in the dashed line box in Figure 3, two
The complementer consists of two main blocks: a binary storage element and an exclusive NOR. In principle, the circuit senses the first 611 in the bit string and then, after a one bit delay, inverts the following bit. The binary storage element consists of an inverter 20, two NAND gates 21, 22 and a 1-bit dynamic delay device 23.

The bit stream from signed multiplication logic unit 11 is coupled via inverter 20 to NAND gate 21 and then via a one bit delay unit 23 to NAND gate 22. The other two inputs of NAND gate 22 are control and reset input connections. The output of NAND gate 22 is coupled to the second input of NAND gate 21;
It is designed to have a reproducing effect as a binary storage element. Exclusive Noah Gate Two Nando Gates 24
, 25 and an or gate 26.

Nand gate 24 and or gate 26 are both 1
Two inputs are connected to the complement output of the binary storage element.
Other inputs of NAND gate 24 and OR gate 26 are connected to receive the bit string from signed multiplication logic unit 11. Nando Gate 24 and Or Gate 26
the outputs of are connected to separate inputs of the NAND gate 25,
At the output of NAND gate 25 appears the product a-b. In this two's complementer, the binary storage element is designed to respond to the first "1" in the incoming bit string and change its output after a one bit delay.

An exclusive NOR with one input coupled to the bit stream from the signed multiplication logic unit 11 and another input coupled to the complement output of the binary storage element causes the (complement) output of the binary storage element to be zero. It is designed to reverse the incoming bit row when entering the state.

The output of exclusive Noah is the number of negations. The operation of the signed multiplication logic device is best explained with reference to the block diagram of FIG. 4 and the table of FIG. 5.

In the following discussion, it is assumed that the serial multiplier has seven information bits representing the magnitude, which are applied to a signed multiplier with the least significant bit being first in time. Multipliers usually also have a separate sign bit. The serial multiplicand is 12 bits, expressed in two's complement notation, with the least significant bit appearing first and the sign bit appearing last. Multipliers and multiplicands are applied at a word rate corresponding to a period of 13 bit times per word. Under these assumptions, the 13 bits are rounded to 10 bits, resulting in a single precision product after a 9 bit transport delay, appearing at a period of 13 bit times per word. The components of the multiplication logic unit, their interconnections, their operations, and the order in which the operations are performed will now be described. FIG. 4 shows the novel signed multiplication logic device 1 of FIG.
1 is shown in a simple block diagram. These blocks do not support writing logic, but are each a cell,
In the preferred integrated circuit embodiment, these cells are formed repeatedly in generally the same manner throughout the logic device. The multiplication logic unit consists of a series of seven interconnected multiplication input gates 34-40 (these are cells of the first type) and serial adders 41-47 (these are cells of the second type). It can be seen that it is composed of a pyramid-shaped adder including a The multiplier cells, among other functions, form partial products that are added by the adder cells to form the final product. The input, internal and output data paths of the multiplication logic unit cells are as follows. Bus line 31
A stream of serial multiplier (1b1) input data obtained from is applied directly to the Bj data input of each multiplier cell 34-40. The serial multiplicand (a) input data stream obtained from line 32 is applied directly to the A, data input of only the first multiplier cell 34, and is applied directly to the A data input of only the first multiplier cell 34, and
are indirectly fed via internal one-bit delays to each of the Ai data inputs.

Each multiplier cell has internal connections (not shown in FIG. 4) for feeding the flow of multiplicand data into that cell to generate the partial products associated with that cell. Starting with the last cell, each cell has a path containing a 1-bit delay for transferring the multiplicand to the next cell. For this reason, line 3
The multiplicand data stream directly obtained from multiplication cell 34 is transferred with a one bit delay to the A, data input of multiplication cell 35. Similarly, the flow of multiplicand data is from multiplication cell 35 to multiplication cell 36, 53. 6 to 37
to, 37 to 38, 38 to 39 and finally 3
9 to the multiplication cell 40, but the multiplication cell 40 does not use a delay device. When transferring the multiplicand from the input of the first multiplication cell to the input of the last multiplication cell, a total of 6
Bit delay occurs. These delay devices form each stage of a multiplicand shift register with seven connections spaced one bit apart. The partial products in the form of a serial data stream formed by the multiplier cells 34-40 are applied to the first digit adder cells 41-44.

Specifically, the partial product outputs of multiplier cells 34 and 35 are applied to two inputs of series adder cell 41;
The partial product outputs of 3r and 3r are applied to the two summing cells 42, and the similar outputs of multiplication cells 38 and 39 are applied to summing cells 4.
applied to the two inputs of 3 and finally the last multiplication cell 40
The partial product output of is applied along with the rounded value (the source of which will be explained later) to the two inputs of the last summing cell 44 in the first place. The partial products are combined in adder cells 41-47 to form the final product. The adders 41-47 are arranged in three places in a pyramid configuration and require a period of three bit times to combine the separate streams into a single data stream. The first adders 41-44 each produce a single data stream after a one bit delay time.

Its value is the sum of the two input data. The output data streams of summing cells 41 and 42 in the first digit are applied to separate inputs of summing cell 45 in the second digit.

The output data streams of summing cells 43 and 44 in the first digit are applied to another input of summing cell 46 in the second digit.

The outputs of adder cells 45 and 46 in the second place, also appearing after a one bit delay, are applied to separate inputs of adder cell 41 in the third place.

At the output of the serial adder 47 appears the aggregated data stream after a further delay of one bit. The final product a-1b1 of the signed multiplication logic unit appears on the output line 33.

Since the multiplicand requires 6 bits of delay to reach the last multiplication cell and 3 bits of delay to add, the total delay required for transport is 9 bits. Fifth
A discussion of the sequence table in the figure will provide a more detailed understanding of how the product is formed. The order table of FIG. 5 shows the order of the flow of multiplicand data, the flow of multiplier data, and the flow of product data.

In each multiplication cell 34-40, the multiplicand a is multiplied by the multiplier bit Bj to form a respective partial product PP1-PP7. The partial products are then transferred to pyramid-shaped adders 41 to 47.
are added to form the single precision final product a-1bI. This table shows the truncation of the multiplicand, the truncation of the final product,
It shows rounding of the product to compensate for truncation of the multiplicand and subsequent products to obtain a single precision output, as well as extension of the sign bit to form a partial product with a valid sign. Multiplicand and multiplier positions are shown for any bit time at a word rate of 13 bit time for all three data streams.

This ordering table shows that the 12-bit multiplicand a is the current 13-bit product word and the 7-bit (B, to B7) multiplier Ib
It is assumed that the project is planned between 1 and 1. The arbitrary bit times of the current word of a.1b1 are shown at the top of the table. Time T, corresponds to the start of addition of partial products using addition devices 41 to 47 in FIG. Time moves from right to left, so numbers can be written in their natural order, with the least significant bit on the right. Therefore, words before the current word appear on the right side of the table, and words after the current word appear on the left side of the table. The same multiplicand word with the 11 least significant bits and the sign bit, represented in two's complement notation, is shown in the table of FIG. It is mentioned.

In the serial data format used for the operations used here, the least significant bit appears first in time, and the last bit is the sign bit. In the top row of multiplicands, bit numbers 5 through 1 of the multiplicand and the sign bit appear at bit times T, through T6 of the current word. In the second row, the multiplicand is shifted to the left by one bit (later in time), and bits 6 through 1 representing the magnitude of the multiplicand and the sign bit appear at times T, through T7 of the current word.

Each subsequent row shifts the multiplicand to the left by one bit. In the seventh and final row, bits 11 to 1 and the sign bit appear at bit times T, to T, of the current word. These staggered rows illustrate the passage of the multiplicand word through successive stages of the shift register, each stage of which is separated by a 1-bit delay in each multiplier cell. is configured and utilized by each multiplication cell for a predetermined series of bit times. The multiplier word is built into columns one bit at a time, with each bit aligned with a successively offset row of the current multiplicand word.

The least significant bit of the multiplier, B, is at the top of the column and the most significant bit, B7, is at the bottom of the column. The multiplier word is fed one bit at a time, least significant bit first, during the previous word time, times T7 to T,3, as shown by bits B, to B, circled in the table. . The injected bits are latched into the multiplier cell while a portion or all of the multiplicand word is read from a stage of the shift register and passed through that portion of the cell to form the partial product. As can be seen from the order table, the final product a-1bI is formed by taking the multiplicand word a one word or less at a time and successively multiplying it by the multiplier word taken one bit at a time. be done.

When calculating double-precision products, the entire multiplier word is used in forming each partial product.

However, given the precision of the multiplicand and multiplier, when determining a single-precision product, it is desirable to truncate the multiplicand before forming the product and then round the product. I will explain in detail later,
This truncation saves significant time and allows the input and output data streams to be processed completely serially. 1
When forming a double-precision product, the multiplicand is truncated so that all bits that contribute less than a predetermined value to the final product are removed.

In FIG. 5, the value of the bit in the multiplicand increases as it progresses from T, to T, . Furthermore, in the top row, the multiplicand is multiplied by the least significant bit of the multiplier, so
It only contributes to the smaller bits in the final product.
In the lower row, the multiplicand is multiplied by the more significant bits of the multiplier, so that the final product value contributes to both the small and large bits. In short, the multiplicand row is
The individual bits of the multiplicand are successively shifted in FIG. 5 so that they have values that contribute to the final product, depending directly on their position along the bit time coordinate. Therefore, to obtain a given precision in the final product, bits in the multiplicand row that occur before any bit time (e.g., T1) must be truncated to form the individual partial products. Do it regardless.

Therefore, the first partial product PPl is the last (and therefore most significant) six bits of the multiplicand a multiplied by the least significant bit of the multiplier. By multiplying the following bits of the multiplicand by the following multiplier bits, seven partial products PP1 to PP7 are successively formed in multiplication cells 34 to 40. Partial product P
Forming the final product from P1 to PP7 is performed by the pyramidal adder of FIG. 4, using the rounding value of 6 mentioned earlier.

This compensates for the statistical average of the numbers truncated in the multiplicand as well as the numbers truncated (or zeroed) in the product. The last 44 of the serial adders with the rounded value in the first digit.
inserted into. As will be explained later, the duration of the word marker (shown in FIG. 9) or timing waveform controls the triangular shape of the multiplicand truncation as well as the final product zeroing. Increasing the duration of the word marker reduces the truncation triangle to zero, eliminates zeroing the product, and thus yields a double precision product without sacrificing any precision. Most. The final product a-1b (is transmitted from the last serial adder 47 at 13 bit times per word, and the first three bits at times T, to T3 are zeroed. The one product a-1b! is 10 bits expressed in two's complement form and is generated at 13 bit times per word.In summary, the ordinal table of FIG. The feeding of the multiplicand a and forming the single precision final product a-1bI is illustrated.

Next considered are multiplier and multiplicand operations on partial products of variable word length, two types of truncation, one of which involves rounding, and two's complement sign extension. The individual cells that make up the multiplication logic device and the timing of multiplication will now be described. A simple block diagram of the multiplication cell is shown in FIG.

In Figure 6, when an inversion such as occurs for a delayed word marker, a half-bit delay occurring at the multiplication gate is added to the first half-bit delay shown, one bit of the word at the multiplication gate is delay, or 2.
Details of the clocking operations performed on phases ψ and ψ2 have been omitted. These details are shown in the logic diagram of FIG. 7 and will be discussed below in connection with that diagram. In FIG. 6, each multiplier cell has a multiplicand gate 61, which plays the main role in forming one partial product (PPl to PP7) and inputting selected bits from the multiplier and the variable of the multiplicand. The most significant bit of the number (as described above) is used.

Each multiplier cell has a first one-bit delay device 68 formed by two half-bit delay devices. Although not shown in FIG. 6, the two phases are inverted with a half-bit delay. Since the connections of the multiplier input gates are made only at one bit intervals, the taps at the boundaries of the multiplier input gates pick up only the non-inverted waves. When all the multiplier cells are interconnected, the first one-bit delay device 68 collectively forms the multiplicand shift register described above. Each multiplier cell has a second one-bit delay formed by two half-bit delays (58, 59) and two inverters (not shown in FIG. 6). When all multiplier cells are interconnected, these second delay devices collectively form a second shift register to which a word marker or timing waveform is applied to set the word length of the multiplicand. Then, the timing for selecting the multiplier bit is determined, and the timing for subsequent addition is determined. The last element in the multiplication cell is a means to recover the sign bit necessary to maintain two's complement notation in the partial product represented by the shifted multiplicand. The partial product (P
Pl to PP7) are formed by blocks 61 called multiplicand gates of predetermined multiplication cells 34 to 40.

The multiplicand gate 61 has three inputs and one output,
When all three inputs are 17, a ``1'' output is generated.What I would like to say here is that the term ``1'' or ``0'' does not mean ``true'' or ``false''. Or the signal “
It is synonymous with ``presence'' or ``absence.'' We will also ignore inversions that may occur in actual equipment. Fourth
The bit sequence of multiplicand a from line 32 in the diagram is applied to the first input of multiplicand gate 61, partially after a delay by the multiplicand shift register, and the selected bit (Bi) of multiplicand b is applied to the first input of multiplicand gate 61. Multiplier bit latch 6 taken out from busbar 31
2 is applied to the second input of gate 61. A timing control signal is applied from timing gate 57 through inverter 65 to a third input of multiplicand gate 61 . The multiplicand in a given multiplicand gate 61 is delayed by one bit from the position of the multiplication cell in the sequence of FIG.

In the first multiplication cell in the sequence of FIG. 4, the multiplicand (a1) from input 32 is directly connected to the first input of multiplicand gate 61. It is also connected to the input of a first 1-bit delay device (corresponding to 68). In the subsequent reference cell, the 1-bit delay device (corresponding to 68) is connected to the 1-bit delay device (corresponding to 68) in the previous cell, so the 1-bit delay device (corresponding to 68) is the multiplicand line 3
2 are connected in series and together they form a multiplicand shift register. Since the multiplicand gate 61 of a given loss calculation cell is connected to the input side of the 1-bit delay device 68 of that cell, the last loss calculation cell (40 in FIG. 4)
does not require a delay device for the multiplicand. The successive delays of the multiplicands in the 0 multiplicand gate are
4 (input a1) is O bit, the second 35 (input A2) is 1 bit, and the third 36 (input A3) is O bit.
), it is 2 bits, the fourth 37 (input A4) is 3 bits, the fifth 38 (input A,) is 4 bits, the sixth 39 (input A6) is 5 bits, In the seventh and final cell 40 (input A7) there are 6 bits. Due to the delay of the multiplicand bit string mentioned above, the fifth
Successive shifts in the multiplicands in each row of the diagram occur. To this end, a stream of serial multiplicand data passes through each multiplier cell 34-40, and the multiplicand (or some portion thereof) is multiplied by the multiplier bit applied to that cell. The delay causes the lower multiplicand bits to come in on each successive row and within the time limits of the current output word. For this reason,
By gating the multiplicands in all multiplication cells at selected bit times (relative to the flow of product data),
When forming partial products, the multiplicand can be truncated. The multiplier bits selected to form partial products in a given multiplication cell correspond to the sequential positions of the cells in FIG.

In other words, multiplier bits 1 through 7 are selected in multiplication cells 34 through 40, respectively. Selection of the multiplier bit in a given multiplication cell is accomplished by using a multiplier bit latch 62, a multiplier strobe 66, and two half-bit delays 58, 59 (as well as two inverters not shown in FIG. 6). and these are coupled to the path to the word marker input 49 of FIG. At input 49, the word marker (W1) serving as the bit selection means is at O'2 for a duration of 7 bits (T6-Tl3), starting from the nominal bit time T6 (FIG. 9); Duration of 6 pits (T, 3-T6
) is 8-bit. This sequence is repeated at a cycle of 13 pit times per word. Since word marker delays 58, 59 are connected in series for each cell, the word marker arrives one bit late in each subsequent multiplication cell. Collectively, the delay devices form a word marker shift register. Therefore, the stroke connection made to the word marker register in each cell lags the previous cell by one bit. As will be explained later, the connections within the cell to the word marker register allow bit times T7 to T of the previous word.
Multiplier bits can be sent during l3. First, consider the multiplier bit latch 62, which selects one bit from the multiplier bit sequence and selects one bit from the multiplier bit sequence for a duration of one word (1
3 bit times) and couples it to the second input of multiplicand gate 61, ie, the multiplier input.

The data input to multiplier bit latch 62 is coupled to multiplier bus 31 which has a multiplier bit string. The control input of latch 62 selects a particular bit from the bit string.
Coupled to the output of the multiplier bit strobe 66 After this, the selected bits from the multiplier bit string become the multiplier bits.
appears at the output of the latch and is coupled to multiplicand gate 61. Multiplier bit latch 62 receives the strobe signal from 66.
Corresponding to the state of the multiplier bus 31 when the pulse occurs,
6F' or 60" at the output and latches it. The latch holds this 811 or 60" state until the next strobe pulse occurs one word later.

On the next pulse, the latched value is continued or replaced. Multiplier bit strobe 66
Its internal connection to the mah- register
In response to the presence of the marker, the time (T1+6)
(ie, T7 in multiplication cell 34).

As shown in FIG. 6, the multiplier bit strobe 66 is
It has two inputs respectively coupled to the input and output of half-pit delay device 59. This connection senses the passing of a word marker and produces an output signal to latch 62 after a nominal one bit delay after the end of the word marker reaches a cell boundary. As I mentioned before,
The block diagram of FIG. 6 is simplified in that it does not feature the inversion or transmission gates of ψ1 and ψ2, which cause the strop to be at the middle edge of the word marker's word (i.e., 1 Therefore, in the first multiplication cell 34, the nominal bit time T7) can be sensed for the first multiplication cell 34.
A pulse is generated by strobe 66. Assuming that the multiplier bit string, which also has a duration of 7 bits, is properly synchronized with the word marker, the first pit latches into the first loss cell at nominal bit time T7, as shown in FIG. The second multiplier bit is then latched into the second multiplier cell 35 at time T8, and the third multiplier bit is latched into the third cell 36 at time T.
such that all seven multiplier bits are stored by bit time Tl3 of the previous word. Timing control of multiplication in forming each partial product is performed by a timing gate (57 in FIG. 6, 95 in FIG. 7).

Timing gate 57 has one input coupled to word marker bus 48 and another input coupled to the word marker register. The first input connection provides the word markers for all cells simultaneously, and the second input connection provides the word markers with a delay of one bit one after the other, following the order from cells 34 to 40. is obtained.

The timing gate is responsive to the time period defined by the undelayed word marker as well as the delayed word marker and produces an enable output during that time period, which is applied to the third input of multiplicand gate 61. is combined with In further detailing the connections described above, bus 48, to which one input of gate 57 is connected, provides an inverted word marker W2.

The horizontal line at the beginning indicates that the word marker is inverted, and the subscript indicates that the delay is (n-1) bits. The waveforms described above are shown in FIG.
The other input of is connected to the output of half-bit delay device 58. Taking into account the inversion not shown and the half-bit delay at the input of the gate, the second input waveform at the input of gate 57 can also be represented by VV2. The output of gate 57 is the AND of the two inputs, which is inverted by inverter 65. Therefore, in the first cell 34, the two logically ANDed waveforms are anti-coincident, and a "1" output is generated during the period T1 to T6. The operation of gate 57 and inverter 65 can be tabulated as follows: Since the output of the multiplicand gate is related to the AND of the three inputs, the multiplicand gate in each multiplier cell has the timing described above. Generates output only during the period.

As shown in FIG. 5, this period is limited to between the vertical dashed line 52 (on the right) and the diagonal dashed line 53 (on the left). The portion fed into is discarded and is not used in forming the partial products. At the output of each multiplication cell, in order to fully represent the partial products in two's complement notation, and to be able to properly add partial products of Machihen word length, the sign bit must be equal to the remainder of the current word. must be continuous throughout the section. As shown in FIG. 5, the continuation of the sign bits continues to the left of diagonal dashed line 53 to the end of the current word. The continuation of the sign bit is passed through a block 6, which includes a 1-bit delay 64 through an inverter gate 57, a code recovery block 67, and an or gate 63.
This is done by a regeneration path back to the second input of T. The sign bit is 67 in each multiplication cell at the following bit time:
It is reproduced by a loop consisting of 63 and 64.

The output of multiplicand gate 61 as well as the output of sign recovery gate 67 are applied to separate inputs of OR gate 63 to produce the complete partial product.

The partial product of each multiplication cell can be expressed by the following Boolean formula. PPl=A,・b1・(T1-T6) ten reproduction code・(T7-Tl3)PP2-A2・B2・(T,-T
7) Ten reproduction code・(T8−Tl3)PP3=A,・B3
・(T-T8) ten reproduction code ・(T,-Tl3)PP4=
A4・B4・(T-T,) ten reproduction code・(TlO-Tl
3) PP5-A5・B5・(T, −TlO) ten reproduction code・(T,, −T],)PP6=A6・B6・(T−Tl
l) Ten reproduction code・(Tl2-Tl3)PP7=A7・B
7・(T, −Tl2) ten reproduction code・(Tl3−T, 3)
Here, a1 to A7 are the multiplicands appearing at the inputs of gates 34 to 40, respectively, b1 to B7 are the bits stored in gates 34 to 40, and time T is the bit time relative to the output word (FIG. 5). . The multiplication cells shown in the block diagram of FIG. 6 are shown in more detail in the logic diagram of FIG. The logic circuit of FIG. 7 is implemented using MOSFETs, in which case the NAND gate format is most desirable in terms of minimizing substrate area. The circuits of the individual gates are not shown because they are well known. The program of FIG. 6 has its counterpart shown in FIG. Multiplicand gate 61 in FIG. 6 corresponds to NAND gate 71 in FIG.

Timing gate 57 and inverter 65 in FIG. 6 correspond to NAND gate 95 and its interconnection with NAND gates 70 and 71 in FIG. This performs the above-mentioned logical AND and inversion. Multiplier bit latch 62 connects to transmission gate 73 and inverter 74
, Or Gate 75, 76, Nando Gate JMo V, 78
The bit string corresponding to transmission gate 79 is transmission gate 7.
3 to the input of an OR gate 75 and, after being inverted at 74, to the input of another OR gate 76. The strobe input is a NAND gate 81 (this corresponds to the multiplier bit strobe 66 in FIG. 6).
is applied to other inputs of OR gates 75 and 76. The strobe input from 81 is a short pulse of approximately 1 bit in duration.

The outputs of OR gates 75 and 76 are NAND gates JMoV,
78, each of which is supplied to a first input. To achieve a latching effect, the output of NAND gate JMOV,78 is cross-coupled to the other input. The output of the multiplier bit latch is taken from the output of NAND gate 78 and sent to the second input of NAND gate 71 via transfer gate 79. The OR gate 63 in FIG. 6 corresponds to the NAND gate 72 in FIG.

NAND gate 72 has one input as NAND gate 71
and another input is coupled to the output of NAND gate 70. Code recovery block 67 in FIG. 6 corresponds to NAND gate 70. 1-bit delay device 64 in FIG. 6 is composed of transmission gates 82 and 84 and inverters 83 and 85. nand gate 7
The output of 2 is transmitted to delay elements 82, 83, 84 for code regeneration.
, 85, the partial product output of the 0 cell is coupled to the input of NAND gate 70.
The 1-bit multiplicand delay device 68 in FIG.

Half bit word marker delay device 58 corresponds to transfer gate 90 and inverter 91. A half pit word marker delay device 59 corresponds to a transmission gate 92 and an inverter 93.
9 is used to reset the carry stored inside the adder.

This corresponds to the NAND gate 96 in FIG. 7. As previously explained with reference to FIG.
Combining the seven bit strings from 0 into a single bit string representing the sum of the individual bit strings.0 This combining requires a delay time of one bit per digit.

Adder Power The adder in the 01st position operates synchronously with the quasi-1 arithmetic gate and is set as the least significant bit of each word passes, if there is a carry stored internally. The carry stored within 41-44 is set by the signal at nominal bit time T1 obtained from the NAND gate corresponding to NAND gate 96 of the second multiplier cell 35. The adders 45, 46 in the second place are reset by a signal at nominal bit time T2 obtained from the NAND gate corresponding to NAND gate 96 of the third multiplier cell 36.

The last adder 47 is reset by a signal at nominal bit time T3 obtained from the NAND gate corresponding to NAND gate 96 of the fourth multiplier cell 37. All adders are similar except for the last adder 47;
The final adder replaces the inverter with an output NOR gate, zeroing out the last three digits of the product. This is why the adder is used repeatedly in the design of the loss adder.
It is a cell of the form . A logic diagram of the adder is shown in FIG. 8 and will now be described. The summing cell of FIG. 8 is of conventional design and can be seen as being formed by three main blocks, indicated by dashed boxes, and several associated delay devices.

The main block is a first exclusive NOR consisting of elements 100, 101, and 102, and elements 103, 104, and 105.
a second exclusive NOR consisting of elements 108 and 109;
, 110, 111, 112 and a delay device. Symbols A, B, and C written in FIG. 8 represent an addend, an augend, and a carry, respectively. This should not be confused with the symbols A, b, and c used in connection with multiplication in other figures. The carry logic and delay devices create a one bit delay time in transfer gate 110, NAND gate 111 and transfer gate 112. The input of the first exclusive NOR gate is provided with a half-bit delay by transmission gates 98 and 99 acting in conjunction with gates 100 and 102. Transfer gate 06 working in conjunction with inverter 107 adds a half-bit delay to the output. The addition cell works as follows.

The A and B bit streams are applied to the first exclusive NOR via a half-bit delay. The exclusive NOR consists of two NAND gates 100, 101 and an OR gate 102. Inputs 100 and 102 are connected in parallel to the A and B bit strings.

The outputs of NAND gate 100 and OR gate 102 are coupled to two inputs of NAND gate 101. 1st
The output of exclusive NOR (A(+)B) is NAND gate 1
Appears in the output of 01. Another output (A-B) is Nando's
? taken from the output of gate 100 and applied to one input of the carry logic and delay device? It will be done. The second exclusive NOR of the adder cell is comprised of a NAND gate 103, an OR gate 105 and a NAND gate 104.

The inputs of 103 and 105 are connected in parallel and coupled to the output of the first exclusive NOR (A4B) and the carry output (C, -1) of the carry logic and delay device, respectively.

The outputs of NAND gate 103 & OR gate 105 are applied to two inputs of NAND gate 104, respectively.
Second exclusive NOR output (A(1)B)(1)Ci-1
appears at the output of NAND gate 104 and transfer gate 1
06 and an inverter 107. An inverter adds a second half-bit delay to the bit stream. A summation output A(+)B+)C appears at the output of inverter 107. The carry logic and delay device is an or gate 108;
NAND gates 109, 111 and transmission gates 110,
It consists of 112.

One input of gate 108 is the output C of the first exclusive NOR.
A4B) and its output is connected to NAND gate 109
is coupled to one input of The other input of NAND gate 109 is connected to the AB output of NAND gate 100. The output of NAND gate 109 is transferred to transmission gate 110.
0 NAND gate 111 which is coupled to NAND gate 111 via
The output of contains a carry (at i-1), which is delayed by half a bit in transmission gate 112 and coupled to the other input of OR gate 108 via a feedback path. The logic function of the adder cell can be represented in the following table.

qfu vyo 1 tier 1L 5 mouth J/ '1st Buddha/＼ 1~
The rounded value and zero adjustment shown in Figure 5 can be understood by looking at Figures 4 and 8a. Obtained by using OR Gate 49.

These include an adder 41 in which the bit string is in the first place;
It is timed to generate 110 when passing through 42, 43, and 44. The addition is performed on the inputs of a serial adder 44. Zero adjustment of the last 3 bits of the product word is done by T3, T4, and T5 of Katsura 1 arithmetic cells 37, 38, and 39.
This is done by an OR gate 50 with its input coupled to its output. As previously stated, these correspond to the outputs from a NAND gate similar to NAND gate 96 shown in FIG. The output of the OR gate 50 is the 1-bit delay device 5.
1 to the gate provided in the last serial adder 47. The gate to the serial adder 4r is shown in FIG. 8a, in which case a NOR gate 113 is used instead of the inverter 107. Thus, a rounding value is introduced when the first three least significant bits are passing through the serial adder in the first place, and the truncation during rounding is applied to the three least significant bits coming out of the serial adder 47. The signed multiplication logic unit described in 〇〇＼, which is performed by zeroing out , is arranged to minimize the number of communication paths at the logic unit and cell boundaries.

Data flow to and from the logic device as well as between cells requires only a single connection since the data is in serial form. As for the logic device boundary, it feeds in a serial data stream of multipliers, injects a serial stream of multiplicands, and takes out a serial data stream of final products. At the cell boundaries, the multiplier stream is injected, the multiplicand data stream is in and out, and the partial product serial data stream is out. Since the data flow is serial, the requirements for the adder cells are the same (two in, one out). There are somewhat more communication paths allocated to the 0 timing function, but the timing waveform or word - Minimized by using markers.

The timing conditions are for logical devices,
Two-phase clocking to and from the individual cells is required. At the boundary of the logic device, the inverted timing waveform W2 delayed by one bit is applied by the bus 48,
The non-inverted timing waveform W1 is sent to the first stage of the timing waveform register. Inverted at cell boundaries. One connection is required for the waveform, and two connections are required to send in and take out the non-inverted timing waveform. Inside the cell, a timing signal is generated whose termination is controlled by the shift register timing waveform and whose start is controlled by the busbar inverted timing waveform. The term timing signal refers to the output of NAND gate 95 (FIG. 7), which is responsive to both timing waveforms;
refers to the combination of equivalent signals at the input of gate 95,
This is effectively the word time minus the output of NAND gate 95. Two connections in the timing waveform to a cell provide the control necessary to internally adjust the word length of the multiplicand, as well as to strobe the multiplier bits needed to form the partial product associated with that cell. The required timing information can be obtained internally. The timing waveform register also provides the timing signals necessary to reset the adder, zero the last adder, and introduce the rounded value. For this last function, only one connection path is required from each individual multiplier cell to the subsequent adder cell. The reduction in the number of connections between cells as described above can be explained by the fact that, in the case of a loss-making cell, various functions are most efficiently grouped together in a cell.

The core function of a multiplication cell is to create a logical product, which is essential for a loss cell, and thereby forms a partial product. Around it are a multiplier bit latch that stores one multiplier bit at a time, eliminating the need for parallel input connections, and two shift register stages each. One of these registers is required to properly delay the multiplicand according to the selected multiplier bit order, and the other register is required for the timing waveform and, as mentioned above, is required to properly delay the multiplicand according to the selected multiplier bit order. Provides the necessary strobe pulses inside the cell for selection and multiplicand truncation. The advantage of having a minimum number of communication paths at the boundaries of logic devices and a minimum number of connection paths between cells is unique to integrated circuit fabrication, but it is also possible to planar circuits. This is especially important when configuring in shapes. When produced in this way, connection lines requiring metallization are particularly expensive, since they require large areas of the semiconductor piece or cut through polycrystalline silicon channels. The choice of serial clocks and serial data flow provides great flexibility in terms of capacity, but also minimizes communication paths.
This fulfills the basic conditions that make the individual cells useful in other device applications. When building a new device with a larger or smaller capacity, this cell configuration can be used as is. This significantly reduces the cost of re-designing the device. In summary, the multiplying input gate described so far requires only two bus connections and two series connections as inputs, and provides timing data as outputs. As well as producing partial products, a series connection to neighboring cells is obtained.

Additionally, the word marker waveform is specifically chosen such that one portion reflects the multiplier word length determined by the number of carrier input gates actually used in a particular design; The total length determines the word length of the multiplicand,
This may vary in any given case. The ability to electrically vary the multiplicand with word markers provides design flexibility for data and signal processing issues where data precision varies depending on the application. Note that the word length of the multiplicand can only vary upwards from a certain minimum word length.
Below this word length, the multiplier input gate internal timings begin to overlap in an undesirable manner. If a complete double-precision product is desired and the extra time required to obtain the product is acceptable, the signed subtraction logic unit can do this as follows.

If there are b bits in the multiplier, then (b-1) bits are truncated from the multiplicand in the top row of FIG.
There are 3 rounded numbers. Therefore, in the lower part of the multiplicand (b
-1) +3 O's are added and the word marker is set to a period longer by (b-1) +3 pit times than in the case of single precision. The result is a complete double precision product.

[Brief explanation of drawings]

FIG. 1 shows a system of the present invention connected to multiply a multiplicand expressed in two's complement notation by a multiplier representing sign and magnitude to generate a rainbow product expressed in two's complement notation. A block diagram of a signed loss calculation logic device. FIG. 2 is a block diagram showing a case where a plurality of signed loss calculation logic devices are used to perform multiplication of complex numbers. FIG. 3 is a block diagram of a signed loss calculation logic device. 4 is a block diagram of a signed multiplication logic device; FIG. 5 shows the handling of multiplicands and multipliers, the formation of partial products, and their A sequence table showing the procedure for obtaining products by combining, FIG. 6 is a simplified block diagram of a multiplication input gate used repeatedly in FIG. 4, and FIG.
Figure 8 is a logic diagram of the serial adder used repeatedly in the block diagram of Figure 4. FIG. 9 is a graph illustrating the control waveforms generated within the signed counting logic device of FIG. 4 and used to time its operations.

Claims (1)

[Scope of Claims] 1. The multiplicand has information representing the magnitude and sign expressed in two's complement description, the multiplier has information representing the magnitude, and the product is expressed in multiple notations of two. Two serial binary numbers are stored in such a way that the bit strings of the multiplier, multiplicand, and product appear serially at the same word rate, and the major and low-order bits appear temporally first. In a signed multiplication logic device for multiplying to obtain a series binary product, a bus supplying the multiplier bit string as a word of n bits; and a bus coupled to the bus for storing successive words of the multiplier bit string; Each such storage element selects a predetermined bit from each word of the multiplier bit string until a bit of the same order appears in a subsequent word.
n binary storage elements adapted to store selected bits, a shift register with n connections to which the multiplicand bit sequence is supplied at one-bit intervals, and n multiplication stages; an adder circuit coupled to the output of each multiplier stage to combine the bit strings representing the partial products into a single bit string equal to the product, each multiplier stage feeding the multiplier bits into a binary storage element; The multiplicand is connected to feed into a multiplicand shift register connection such that the cumulative delay of the shift register increases in accordance with the order of the multiplicand bits fed into the multiplicand. A signed multiplication logic device adapted to successively select the most significant bits of a word and multiply them by a multiplier bit to form a serial partial product at the times corresponding to the digits. 2. In the signed multiplication logic device as claimed in claim 1, each multiplication stage has means for feeding a number of bits less than all of the multiplicand, the number being inversely proportional to the order of the multiplier bits fed. the least significant bit is truncated, the means for truncating the multiplicand bits includes means for generating a timing waveform having a portion whose connection time is equal to the bit time of the multiplier word; a second shift register, the second shift register has connections at one-bit intervals, each multiplication stage is connected to the second shift register, and the second shift register has connections at one-bit intervals; , a signed multiplication logic device which determines a timing signal for controlling the number of upper bits to be sent to correspond to the order of multiplier bits to be sent.