Method and Apparatus for Absolute Value Summation and Subtraction

The invention relates to a method and an apparatus for absolute value summation and subtraction and more particularly, to a method and an apparatus for absolute value summation and subtraction in which carry look ahead is utilized.

In a conventional method for absolute value summation and subtraction, subtraction of two operands X and Y is carried out, wherein one of the two operands X and Y, for instance, the operand Y is converted to a two's complement which is then added to the operand X to provide a difference D. In this case, where the operand X is smaller than the operand Y (X<Y), the difference D becomes a two's complement for an absolute value .vertline.X-Y.vertline.. Therefore, a sequence for calculating the two's complement is necessary to indicate the difference D in the expression of an absolute value. In the calculation of a two's complement of the difference D, summation between an inverted difference D, in which each bit of the difference D is inverted, and a number having weight at the least significant bit (LSB) is carried out. In this case, the summation is often realized with a high speed by use of carry look ahead. This is to be explained in more detail later.

However, the conventional method for absolute value summation and subtraction has a disadvantage in that subtraction takes a long time to deteriorate a high speed processing thereof, because a sequence for calculating an absolute value of a subtracting result, which is essentially a summation sequence, is inevitable for the subtraction dependent on a comparison in value of two operands.

Accordingly, it is an object of the invention to provide a method and an apparatus for absolute value summation and subtraction in which summation is realized with a high speed.

According to a first feature of the invention, a method for absolute value summation and subtraction, comprises:

generating a carry generation function G and a carry propagation function P in accordance with two input operands X and Y;

generating a group carry propagation function P* in accordance with said carry propagation function P;

generating a group carry generation function G* in accordance with said carry generation and propagation functions G and P; and

carrying out a summation of said two input operands X and Y by use of said carry generation and propagation functions G and P, and said group carry generation and propagation functions G* and P*.

According to a second feature of the invention, an apparatus for absolute value summation and subtraction, comprises:

a first generator for generating a one's complement, to which a control signal instructing one of summation and subtraction between two input operands X and Y, and said operand Y are supplied, said operand Y being passed therethrough at the time of the summation, and said one's complement of said operand Y being supplied therefrom at the time of the subtraction;

a second generator for generating a carry generation function by receiving said operand X and said one's complement;

a third generator for generating a carry propagation function by receiving said operand X and said one's complement;

a fourth generator for generating a group carry generation function by receiving said carry generation and propagation functions;

a fifth generator for generating a group carry propagation function by receiving said carry propagation function;

a carry look ahead for generating a carry from the most significant bit in the summation of said operand X and a two's complement of said operand Y by receiving said carry generation and propagation functions, and said group carry generation and propagation functions;

a converter, through which said carry generation and propagation functions, and said group carry generation and propagation functions are passed at the time of the summation, and where said carry is "1" at the time of the subtraction, and from which a function obtained by inverting a logic OR of said carry generation and propagation functions, a function obtained by inverting a logic OR of said group carry generation and propagation functions, said carry propagation function and said group carry propagation function are supplied, where said carry is "0" at the time of the subtraction; and

a sum generator for generating one of a sum and a difference between said operands X and Y by receiving outputs of said converter.

The invention will be explained in more detail in conjunction with appended drawings, wherein:

FIG. 1 is a block diagram showing a conventional apparatus for absolute value summation and subtraction in which a conventional method for absolute value summation and subtraction is carried out,

FIG. 2 is a block diagram showing an apparatus for absolute value summation and subtraction in a preferred embodiment according to the invention,

FIG. 3 is a flow chart showing operation in the preferred embodiment and

FIGS. 4A and 4B are explanatory diagrams showing carry generation, carry propagation, and carry absorption in the preferred embodiment.

Before explaining an apparatus for absolute value summation and subtraction in a preferred embodiment according to the invention, the aforementioned method for absolute value summation and subtraction will be explained in FIG. 1, wherein symbols .sym., .LAMBDA., and V indicate an exclusive OR calculation, an AND calculation, and an OR calculation, respectively.

At first, two input operands X and Y of absolute values are supplied to data buses 100 and 101, respectively, and a control signal instructing summation or subtraction is supplied from a control unit 110 to a generator 120 for a one's complement and a generator 126 for a two's complement.

(1) Where summation is carried out

The operand Y is controlled to be passed through the generator 120 for a one's complement, so that the operands X and Y are supplied to a generator 121 for a carry generation function, in which a carry generation function G is generated. The carry generation function G includes a predetermined number of bits, i.sub.th bit Gi of which is expressed by an equation,

where Xi and Yi are i.sub.th bits of the operands X and Y, respectively.

The bit Gi becomes true, when a carry is generated at the i.sub.th bit in the summation of the operands X and Y. The operands X and Y are also supplied to a generator 122 for a carry propagation function, in which a carry propagation function P is generated. The carry propagation function P includes a predetermined number of bits, i.sub.th bit Pi of which is expressed by an equation,

and the i.sub.th bit Pi indicates whether or not a carry is propagated at the i.sub.th bit in the summation of the operands X and Y.

Thus, a calculation of a carry is realized at each bit in the summation of the operands X and Y by use of the carry generation and propagation functions G and P. For this purpose, a number of logic circuits are required to be provided, wherein each logic circuit is necessary to have many input terminals. This results in a difficulty of realizing the apparatus for absolute value summation and subtraction. In practical, therefore, bits of two operands are divided into a predetermined number of groups, in which and among which a carry is first calculated. For instance, the bits are divided to provide plural groups by each three bits. Here, a group carry generation function G* is defined by an equation,

where i is an integer selected from 0, 3, 6 - - - .

The bit Gi* becomes true, when a carry is generated from a group to an upper bit ((i+3).sub.th bit) in the assumption that the group includes i.sub.th, (i+1).sub.th, and (i+2).sub.th bits.

Further, a group carry propagation propagation function P is defined by an equation,

The bit Pi* becomes true, when a carry which is propagated to the LSB (i.sub.th bit) of the group is propagated through each bit of the group to an upper (i+3).sub.th bit. Even if the number of bits is not three the group generation and propagation functions G* and P* are generated in generators 123 and 124 by modifying the equations Gi* and Pi*.

Then, a sum of the operands X and Y is obtained in a generator 125 by receiving the carry generation and propagation functions G and P, and the group carry generation and propagation functions G* and P*. For this purpose, a carry is first calculated at each bit in the summation of the operands X and Y by use of carry look ahead.

Here, where it is assumed, for instance, that the bits are divided into a predetermined number of groups by each three bits, a carry C.sub.7 is expressed at the seventh bit by an equation,

In the above equation, each term indicates following states.

(a) the first term

a carry is generated at the seventh bit.

(b) the second term

a carry which is generated at the sixth bit is propagated through the seventh bit.

(c) the third term

a carry which is generated in a group of the third to fifth bits is propagated through the sixth and seventh bits.

(d) the fourth term

a carry which is generated in a group of the zero to second bits is propagated through a group of the third to fifth bits and through the sixth and seventh bits.

A carry is calculated at an arbitrary bit in the same manner as the above.

In the generator 125, a carry is calculated as explained above, and an output W.sub.1, of the sum of the operands X and Y is supplied from the generator 125 in accordance with the carry, and the carry propagation function P.

The output W.sub.1 is passed through a generator 126 for a two's complement which does not operate at the time of the summation to be provided on a data bus 102.

(2) Where subtraction is carried out

The operand Y is supplied through the data bus 101 to the generator 120 for a complement of "1", in which a one's complement Y (each bit of the operand Y is inverted) is generated. The subtraction is realized in the summation by use of a two's complement, that is, by adding the two's complement (Y+1) to the operand X. The "1" is processed as a carry C.sub.-1 which is carried to the zero bit (the LSB). In the generators 121 and 122, the carry generation function G and the carry propagation function P are generated, respectively, in accordance with each bit of the operand X and the complement Y. Then, the group carry generation and propagation functions G* and P* are generated in the generators 123 and 124, respectively, in the same manner as the aforementioned summation. Thereafter, a carry is calculated in the summation of the operand X and the two's complement in accordance with the functions G, P, G* and P*. In this case, a carry C.sub.-1 (=1) which is carried to the zero bit (the LSB) must be considered as explained before.

Here, where it is assumed, for instance, that the bits are divided into a predetermined number of groups, a carry C.sub.7 of the seventh bit is obtained by an equation,

In the above equation, although the definition of the first to fourth terms is the same as that of a corresponding equation in the summation, the fifth term indicating a state where the seventh bit C.sub.7 is propagated through a group of the zero to second bits and a group of the third to fifth bits, and through the sixth and seventh bits additionally. A carry of an arbitrary bit is calculated in the same manner as the above.

In the generator 125, a carry is calculated as described above, and the sum of the operand X and the two's complement for the operand Y is obtained in accordance with the carry, and the carry propagation function P. Then, an output of the generator 125 is passed through the generator 126 for a two's complement, where the operand Y is equal to or less than the operand X (Y.ltoreq.X), while a two's complement for the output of the generator 125 is generated in the generator 126 to be provided on the data bus 102, where the operand X is less than the operand Y (X<Y). That is, an absolute value of the difference in the subtraction is obtained. In deciding which of the operands X and Y is larger, the operand Y is found equal to or less than the operand X, where a carry is generated at the most significant bit (MSB) in the summation of the operand X and the two's complement for the operand Y, while the operand X is found less than the operand Y, where the carry is not generated at the MSB in the summation of the operand X and the two's complement for the operand Y. On the other hand, a complement of the difference D in the subtraction is obtained by adding S, each bit of which is obtained by inverting each bit of the outputs of the generator 125. However, the method and the apparatus for absolute value summation and subtraction has a disadvantage which is described before.

Accordingly, a method and an apparatus for absolute value summation and subtraction according to the invention are provided as explained in detail hereinafter.

FIG. 2 shows an apparatus for absolute value summation and subtraction in the preferred embodiment according to the invention. In the apparatus for absolute value summation and subtraction, a generator 214 for a one's complement and a generator 215 for a carry generation function are connected to data buses 201 and 200, respectively, and a generator 216 for a carry propagation function is connected to the data bus 200 and the generator 214 for a one's complement which is also connected to the generator 215 for a carry generation function. The generator 216 for a carry propagation function is connected at its output to a generator 217 for a group carry generation function, a generator 218 for a group carry propagation function 218, a MSB carry look ahead 219, and a converter 220, and the generator 215 for a carry generation function is connected at its output to the generator 217 for a group carry generation function, the MSB carry look ahead 219, and the converter 220. Further, the generator 218 for a group carry propagation function and the generator 217 for a group carry generation function are connected at their outputs to the MSB carry look ahead 21 9 and the converter 220, respectively, and the MSB carry look ahead 219 is connected at its output to the converter 220 which is connected at its output to a generator 221 of a sum having an output data bus 202. A control unit 213 is connected to the generator 214 for a one's complement and the converter 220.

In operation of summation, two input operands X and Y are supplied to the data buses 200 and 201, and a control signal instructing summation is supplied from the control unit 213 to the generator 214 for a one's complement, the MSB carry look ahead 219, and the converter 220 (301 in FIG. 3). Consequently, the generator 214 for a one's complement does not operate, so that the operand Y is merely passed therethough. As a result, a carry generation function G and a carry propagation function P are generated in the generators 215 and 216, respectively (302 in FIG. 3). Then, a group carry generation function G* and a group carry propagation function P* are generated in the generators 217 and 218 in accordance with the carry generation and propagation functions G and P, respectively (303 in FIG. 3). On the other hand, the MSB carry look ahead 219 does not operate in the summation. The carry generation function G, the carry propagation function P, the group carry generation function G*, and the group carry propagation function P* are passed through the converter 220 by the control signal instructing summation supplied from the control unit 213. In a generator 221 of a sum, finally, a carry is calculated in the summation of the operands X and Y based on the functions G, P, G* and P* by use of carry look ahead, so that bits of a sum is generated (304 in FIG. 3). The calculation of the functions G, P, G* and P*, a carry of each bit, and the bits of the sum is carried out in the same manner as described in the conventional method. In operation of subtraction, the control signal instructing subtraction is supplied from the control unit 213 to the generator 214 for a complement, the MSB carry look ahead 219, and the converter 220 (305 in FIG. 3). The, a complement Y which is a one's complement for the operand Y is generated in the generator 214 (306 in FIG. 3), and a carry generation function g is generated in the generator 215 by receiving the operand X and the complement Y (307 in FIG. 3). At the same time, a carry propagation function p is generated in the generator 216 also by receiving the operand X and the complement Y (307 in FIG. 3). Then, a group carry generation function g* is generated in the generator 217 by receiving the functions g and p (308 in FIG. 3), and a group carry propagation function p* is generated in the generator 218 by receiving the function p(308 in FIG. 3). Thereafter, a carry C.sub.M of the MSB is calculated in the MSB carry look ahead 219 in the summation of the operand X and a two's complement for the operand Y by receiving the functions g, p, g* and p* (309 in FIG. 3). Where the carry C.sub.M is 1 (310 in FIG. 3), the operand Y is equal to or less than the operand X, so that the functions g, p, g* and p* are passed through the converter 220 to be supplied to the generator 221 of a sum, in which a carry is calculated at each bit in accordance with the functions g, p, g* and p* by use of carry look ahead, so that bits of a difference are obtained in the subtraction between the operands x and Y to be provided on the data bus 202 (304 in FIG. 3). Where the carry C.sub.M is zero (311 in FIG. 3), the operand X is less than the operand Y, so that group carry generation functions g' and g'* are generated in the converter 220 (312 in FIG. 3).

Thus, a carry is calculated at each bit by use of carry look ahead, so that bits of a difference are obtained in subtraction between the operands X and Y to be provided on the data bus 202 (304 in FIG. 3).

Next, it will be explained that the functions g' and g'* are group carry generation functions, where the operand X is less than the operand Y.

A calculation of (X-Y) is realized by adding the operand X, a complement Y which is a one's complement for the operand Y, and "1" added to the LSB of the complement Y to each other. That is,

On the other hand, a calculation of (Y-X) is realized by adding a complement X which is a one's complement for the operand X, the operand Y, and "1" added to the LSB of the operand Y to each other. That is,

FIGS. 4A and 4B show two examples in which the operand X is assumed to be (11000101).sub.2, and the operand Y is assumed to be (010101001).sub.2. In the above two equations, the term of "+1" is processed as a carry which is carried to the LSB. Therefore, this term is not considered in the two examples.

FIG. 4A shows the first example in which (X+Y) is calculated, wherein a carry is generated at the LSB (the zero bit) having a combination of "1" and "1", and the carry is propagated through the first to third bits having a combination of "1" and "0", and absorbed at the fourth bit having a combination of "0" and "0". Further, a carry is generated at the seventh bit in the first example.

FIG. 4B shows the second example in which (X+Y) is calculated, wherein a carry is generated at the fourth bit, and propagated through the fifth and sixth bits to be absorbed at the seventh bit.

As understood from the above first and second examples, the generation and the absorption of a carry is reverse between (X+Y) and (X+Y). Here, if it is assumed that a carry generation function is g in the calculation of (X+Y), and a carry propagation function is p in the same calculation, Boolean algebra equation of g'.LAMBDA.p' becomes true, when both of the i.sub.th bits of the operand X and the complement Y are zero, because the Boolean algebra equation indicates that a carry is not generated at the i.sub.th bit, and a carry of a lower bit is not propagated at the i.sub.th bit. That is, the g .LAMBDA.p becomes true, when a carry carried from a lower bit is absorbed at the i.sub.th bit thereof. As described before, a combination of "0" and "0" at which a carry is absorbed in the calculation of (X+Y) is converted to a combination of "1" and "1" at which a carry is generated in the calculation of (X+Y). According to the theorem of DeMorgan, gi.LAMBDA.pi is equal to giVpi(gi.LAMBDA.pi=giVpi). Therefore, g'i(=giVpi) is a carry generation function in the calculation of (X+Y).

As to carry propagation function p, bits having a combination of "0" and "1" in the calculation of (X+Y) is not necessary to be converted to bits having the other combination, because the bits has also a combination of "1" and "0" in the calculation of (X"Y).

Based on this concept, it is understood that g'.sub.i * (=gi*Vpi*) is regarded as a group carry function in the calculation of (X+Y).

Accordingly, it is understood that the calculation of .vertline.X-Y.vertline. is realized in accordance with the functions supplied from the converter 220.

As explained above, a carry generation function g, a carry propagation function p, a group carry generation function g*, and a group carry propagation function p*, which are necessary to conduct carry look ahead in the summation of the operand X and the two's complement of the operand Y, are first generated in an absolute value subtraction of .vertline.X-Y.vertline.. Next, a carry of the MSB is calculated in the summation of the operand X and the two's complement of the operand Y by use of the functions g and p, and the functions g* and p*. Where the carry is generated, the operand Y is equal to or less than the operand X, so that the above summation remaines continued by use of the functions g and p, and the function g* and p*. On the other hand, where the carry is not generated, the operand X is less than the operand Y, so that the calculation continues by use of the carry generation function g and the group carry propagation function p* which are given from g'.sub.i (=giVpi) and g'.sub.i * (=gi*Vpi*). The g' and g'* are the carry generation function and the group carry generation function in the summation of the operand Y and the two's complement of the operand X. Therefore, the summation of the operand Y and the two's complement of the operand X is realized by use of the functions g' and g'*, and the functions p and p*.

As understood from the above, it is first decided which of the operands X and Y is larger by use of the carry generation and group carry generation functions and the carry propagation and group carry propagation functions. In accordance with the above decision, the carry generation function and the group carry generation function are converted to continue the calculation of subtracting a smaller operand from a larger operand. A processing amount of the above decision and the above conversion is very small. Therefore, a high speed calculation is realized as compared to the conventional method in which an absolute value processing which essentially requires a summation processing is finally carried out.

Although the invention has been described with respect to specific embodiment for complete and clear disclosure, the appended claims are not to be thus limited but are to be construed as embodying all modification and alternative construction that may occur to one skilled in the art which fairly fall within the basic teaching herein set forth.