Multi-Bit Arithmetic Logic Units Having Fast Parallel Carry Systems

The present invention relates to multibit arithmetic logic units (ALU's), more specifically, multibit adders-subtractors (A/S), having fast carry-look-ahead (CLA) systems, and particularly to a CLA system designed to speed-up the execution of arithmetical operations.

As known, most of the time required by ALU's to execute arithmetical operations is due to the carry propagation delay via the CLA system. Many systems involving various CLA techniques have been devised to reduce this delay. These known techniques, however, require the introduction of additional circuitries whose complexity increases inordinately after a certain number of bits. These additional bits contribute additional propagation delay (PD) per each additional CLA level, which is a primary limitation in speeding-up the operation of extended-length ALU's.

A general object of the present invention is to provide an ALU incorporating an improved CLA system which permits a significant increase in the number of bits within existing CLA levels while reducing the worst case propagation delay (PD) path through the ALU, thereby permitting a significant increase to be made in speeding up arithmetic operations of an extended-length ALU with a minimum penalty of additional circuitry to be included.

More particularly, one object of the invention is to provide a system of combining logical circuits that enables the assembling of an extended-length ALU while reducing extreme output loads and improving execution time, as compared to known ALU circuits, such as the 74181, AM 2901, or the circuit described in Note 1 at the end of this specification. Another object of the invention is to provide a new system for implementing the concept of splitting a large-scale, hard-wired ALU into multiple, small-scale ALU groups or sections, e.g., by programming with software of firmware, by option block wiring or fixed wiring, or by other known techniques.

A further object of the invention is to provide an ALU which permits the simultaneous processing and execution of arithmetic functions of different data and operand lengths.

A still further object of the invention is to provide an ALU having means for selecting desired accuracy of calculated functions, such as multiplication, division, while maintaining maximum efficiency of the ALU.

Additional objects will be apparent from the description below.

The present invention is directed to ALU's including a carry-look-ahead (CLA) system having a plurality of CLA levels, each level including; (1) logical preparation (LLP) circuitry in which are produced intermediate combined signals, the generated carries (G.sub.N) and the propagated carries (P.sub.N) of the respective bit position (A.sub.N, B.sub.N) and G.sub.0, P.sub.0, for the respective group or section position; and (2) logical combination (LLC) circuitry in which are produced the propagated combined carry signals, i.e. the final combined propagated carry (C.sub.N), for the first CLA level, or the intermediate combined propagated carry signals (C.sub.P) for other than the first CLA level.

According to one feature of the invention, the LLP circuitry of the first CLA level interconnects several bit positions so as to output from the first-level LLP circuitry intermediate combination signals which are a function of a plurality of bit positions (P.sub.N, G.sub.N), rather than of a single bit position. Such an arrangement, as will be described more particularly below, enables a significant increase to be made in the number of bits per group, the number of groups per section, etc., while relatively reducing both extreme logic circuitry and total propagation delay of the complete ALU.

According to another feature of the present invention, the carry-in signal (C.sub.IN) into the least-significant-bit (LSB) of the respective group is separated from the intermediate combined propagated carry signal (C.sub.P) between groups, and is introduced into the input at the first-level LLP circuitry combined with the LSB signals, preferably also with a binary "split" signal (SP) whose state determines whether the adder is splitted and the C.sub.IN is to be inputted or not; whereas the C.sub.P signal is introduced into the LLC circuitry input of the respective CLA level, and the split signal determines whether the C.sub.p is disabled or not.

Including the S.sub.P ("split") signal provides a number of advantages within the CLA system, as will be described more fully below; however, it further enables executing various concepts of up-coming new ideas in multi-processing and flexible use of the ALU, including varying the number of data groups to be executed, varying the desired accuracy of execution, executing multiple data simultaneously, and executing multiplication, division and other repetitive algorithms. In addition, the manner in which the SP signal is used does not introduce additional propagation delay, and it saves at least one unit of time delay.

According to a still further feature of the invention, a CLA integrated circuit (IC) device incorporates both the LLP and the LLC of the respective CLA level, as distinguished from existing IC's, such as the 74182, wherein the circuitries for the LLP and LLC logical levels for the same CLA level are divided between different IC;s.

This latter feature permits the ALU to be better divided into IC chips based on either negative or positive CLA logic. Besides decreasing the output loading, the new IC chip design is applicable for: (1) negative inputs to positive outputs for the LLP logical level, and positive inputs to negative outputs for the LLC logical levels; or (2) positive inputs to negative outputs for the LLP logical levels, and negative inputs to positive outputs for the LLC logical levels.

Such an arrangement permits the IC chips to be used for alternate CLA logical levels which, by using wide gates, provides improved results and a minimum of propagation delay. Thus, this technique reduces the propagation delay as compared to existing ALU arrays using devices such as the 74182, in that one inverter delay is saved for the second CLA level, and two inverter delays are saved for each succeeding CLA level.

According to a still further feature of the invention, the circuitry incorporating the functions selector arithmetic-logic ("ADD", "AND", "OR", "XOR") are included within the Sum Part level, thus enabling further reduction to be made of propagation delay while switching from arithmetical functions to logical functions.

Further features and advantages of the invention will be apparent from the description below.

The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:

FIG. 1 illustrates a known single-level, four-bit CLA system, and FIGS. 1a-1c illustrate known modifications to such a system, all of which will be helpful in explaining the present invention;

FIG. 2 illustrates the LLP logical level only of the known CLA system of FIG. 1, except that FIG. 2 illustrates a six-bit CLA system, rather than the four-bit system of FIG. 1;

FIG. 3 is a diagram illustrating the circuit connections in the known plural-level CLA system which diagram will aid in better understanding the propagation delays involved in the operation of such a system;

FIGS. 4a and 4b are diagrams, corresponding to that of FIG. 2, but illustrating certain concepts involved in the present invention;

FIGS. 5, 5a, 5b, 5c are further diagrams which will be helpful in better understanding certain advantages involved in the present invention, particularly when breaking an ALU into groups, FIGS. 5, 5a and 5b illustrating the prior art, and FIG. 5c illustrating certain advantages when the present invention is used;

FIGS. 6 and 6a diagrammatically illustrates the architecture of a known ALU including three and two levels, respectively, of the CLA;

FIG. 7 illustrates the architecture of an ALU corresponding to that of FIG. 6 but incorporating certain features of the present invention, while FIG. 7a illustrates the novel ALU architecture when only two CLA levels are provided;

FIG. 8 is a diagram illustrating one circuit that may be used for the novel CLA component "Z" in FIG. 7;

FIG. 9 is a diagram illustrating a 4-bit CLA system corresponding to the known circuit of FIG. 1 but incorporating certain features of the present invention; FIGS. 9a and 9b being modifications in the circuit of FIG. 9;

FIG. 10 is a diagram illustrating a complete 6-bit ALU, this constituting one "Y" component in FIGS. 7 and 7a constructed in accordance with the present invention;

FIG. 11 is a diagram illustrating an 8-bit CLA system constructed in accordance with the invention; and

FIGS. 12 and 13 illustrate how standard printed circuit cards may be designed to assemble, into different combinations, components constructed in accordance with the invention.

Before describing the specific implementations of the invention as illustrated in FIGS. 10-13, it is believed desirable, as an aid in understanding them, to first describe some novel concepts incorporated in these specific implementations.

As known, the arithmetic portion of an ALU is divided into two parts, namely, the Sum Part and the Carry-Look-Ahead (CLA)Part. The CLA part includes several CLA levels in order to reduce propagation delay, which thereby speeds up the execution of arithmetic functions. The total number of bits per ALU (N.sub.F) executing 2's complement operations is equal to the total number (N) of bits per group, group per sections, sections per division, etc. raised to the power of the number of participating CLA levels (L); thus: N.sub.F =N.sup.L.

Normally, an ALU executes at least one arithmetic operation, namely addition (substraction being executed by 2's complement addition), which dictates the propagation delay, and therefore the maximum clock rate. ALso, an ALU executes at least the logic functions "AND", "OR", "XOR", etc.

Although the CLA equations are known to those familiar with this subject, let us set forth some basic definitions.

Thus, A.sub.N, A.sub.N, B.sub.N and B.sub.N designate the input into the Adder/Subtractor at the N'th position of two multi-bit numbers. "A" and "B" added together form the output result "F", the least significant bit (LSB) position is designated as 1; C.sub.N designates the carry input into the N'th position.

The generated carry is defined as G.sub.N =A.sub.N.B.sub.N =A.sub.N +B.sub.N.

The propagated carry is defined as P.sub.N =A.sub.N +B.sub.N =A.sub.N.B.sub.N

The initial carry input signal into a least-significant bit of an adder is defined as C.sub.IN, which has no propagating delay.

The inter-group carry signal is defined as C.sub.P which is propagated and therefore has a propagation delay.

As also known, the bits of the ALU are divided into groups, sections, divisions, etc., with the first level (CLA) being applicable to the bits within a group, the second level CLA being applicable to the groups within a section, the third level CLA being applicable to the sections within a division, etc.

Each of the foregoing CLA levels may be considered as further divided into two logical levels, each having a one-unit time delay. This, each CLA level includes: (1) a logical preparation level (LLP) in which are prepared the intermediate combined signals (P, G), the generated carry (G.sub.N) and the propagated carry signals (P.sub.N) for the respective bit positions (A.sub.N, B.sub.N), and G.sub.0, P.sub.0 for the respective group, section, etc. portions; and (2) a logical combination level (LLC) in which are combined the final combined propagated carry signals (C.sub.N) for the first CLA level, or the intermediate combined propagated carry signal (C.sub.P) for the other CLA levels.

The foregoing is illustrated in FIG. 1 showing a single-level, four-bit CLA system, wherein it will be seen that the upper logical circuitry receiving the input data bits (A.sub.1, B.sub.1, . . . A.sub.4, B.sub.4, negative input logic being used) constitutes the LLP.sub.1 logical level preparing the intermediate combined signals G.sub.1, P.sub.1 . . . G.sub.4, P.sub.4 for generating the generated carry and the propagated carry; whereas the lower logical circuitry constitutes the LLC.sub.1 logical level receiving the foregoing intermediate combined signals and combines them to prepare the final combined propagated carry signal C.sub.1 . . . C.sub.4 for the respective group.

It will be noted that the prior art arrangement illustrated in FIG. 1, produces a propagated carry output signal (P), and a generated carry output signal (G), but not a carry-output signal (C.sub.OUT); this is the case, e.g. in the TI 745381. Sometimes A C.sub.OUT signal is desired, for example in temporary carry storage, (e.g. Fairchild 9340); in that case, the modification illustrated in FIG. 1a, requiring additional circuitry, could be used, whereupon there would be produced C.sub.OUT, but not G. If G together with C.sub.OUT is desired, the modification illustrated in FIG. 1b could be used, this involving further additional circuitry with additional delay in C.sub.OUT (e.g. TI 74181 or Fairchild 9341); and if it is desired to product P, G and C.sub.OUT without additional delay, the modification illustrated in FIG. 1c could be used, this requiring still further additional circuitry.

The logical preparing level LLP.sub.1 of the system illustrated in FIG. 1 is also shown in FIG. 2, except that FIG. 2 shows a six-bit group rather than the four-bit group of FIG. 1. A six-bit group as appearing in the illustration of FIG. 2 would be impractical in a prior art system such as illustrated in FIG. 1, but nevertheless it is shown in FIG. 2 in order to provide a better basis for comparison with respect to the present invention as embodied in the diagrams of FIGS. 4a and 4b, and as will be described more particularly below.

The prior art circuit of FIG. 1 illustrates only the first level CLA including the LLP of the second level. As indicated above, ALU's conventionally include multiple-level CLA systems respectively applicable to the bits, groups, sections, etc. of the ALU, with each CLA level being further constituted of two logical levels, namely the LLP and the LLC logical levels.

FIG. 3 diagrammatically illustrates such a known multiple-level ALU. Thus, in an ALU having one CLA level, the preparation logical level (LLP) outputs are wired to the combination logical level (LLC) inputs, whereas the outputs of the LLC are wired to the Sum Part of the ALU. Since each of the two logical levels LLP and LLC involves one unit time delay, it will be seen that such a single-level ALU involves two units of time delay for the CLA.

As also shown in FIG. 3, in ALU's having two CLA levels, the LLP.sub.1 outputs are wired to the LLC.sub.1 inputs and also to the LLP.sub.2 inputs; the LLP.sub.2 outputs are wired to the LLC.sub.2 inputs; the LLC.sub.2 outputs are wired to the LLC.sub.1 inputs; and the LLC.sub.1 outputs are wired to the Sum Part. Thus, in a two-level CLA system, there would be four units of time delay for the CLA.

In general, the LLP outputs of the N'th CLA level are wired to the LLC inputs of the n'th CLA level and also to the the (N+1)'th CLA level; and the LLC outputs of the (N+1)'th CLA level are wired to the LLC inputs of the n'th CLA level.

The "P" and "G" signals are output signals of the first CLA level; they are basic intermediate combination signals of A.sub.N, B.sub.N input signals. Thus, P.sub.N =f(A.sub.N, B.sub.N); and G.sub.N =f(A.sub.N, B.sub.N), wherein "N" is the bit position in the adder. P.sub.0 and G.sub.0 are output signals of other than the first CLA level, (i.e., groups within a section, sections within a division, etc.), higher intermediate combination signals of P.sub.N, G.sub.N input signals. Thus, P.sub.0 =f(P.sub.N).sub.K.gtoreq.N.gtoreq.1 ; G.sub.0 =f[(P.sub.N).sub.K.gtoreq.N.gtoreq.2 (G.sub.N).sub.K.gtoreq.N.gtoreq.1 ] wherein "K" is the number of bits per groups (it may also be used for higher order CLA's, as the number of groups per section, etc.); "0" indicates output signals; and "N" indicates input signals also for higher CLA levels.

FIGS. 4a and 4b illustrate one of the novel innovations of the present invention, wherein the logical preparation level (LLP) of the first CLA level (i.e., bits within a group) includes circuitry interconnecting several bit positions so as to output from the LLP.sub.1 logical level higher intermediate combination signals which are a function of a plurality of bit positions, rather than of a single bit position as in the prior art showings of FIGS. 1 and 2. Thus, some of the P.sub.N and G.sub.N output signals at the LLP.sub.1 logical level are no longer a function of a single bit position, but rather are functions of several bit positions, as follows: P.sub.(N) =f(A.sub.N, B.sub.N).sub.K.gtoreq.N.gtoreq.1 ; G.sub.(N) =f(A.sub.N, B.sub.N).sub.K.gtoreq.N.gtoreq.0* wherein "(N)" is a function of several bit positions; and "0*" indicates that additional inputs are included in producing G.sub.(N).

Thus, as shown in the six-bit system of FIG. 4a, which is to be compared with the prior art six-bit system of FIG. 2, it will be seen that the LLP.sub.1 logical level outputs the following intermediate combined signals: G.sub.6, P.sub.6, G.sub.54, P.sub.54, G.sub.5, P.sub.4, G.sub.32, P.sub.32, P.sub.3, G.sub.2, P.sub.2, G*.sub.10 and P*.sub.1. Of these, it will be seen that P.sub.54 and G.sub.54 are higher combination functions of A.sub.5, B.sub.5, A.sub.4, B.sub.4 ; P.sub.32, G.sub.32 are higher combination functions of A.sub.3, B.sub.3, A.sub.2, B.sub.2 ; G*.sub.10 is a function of A.sub.1, B.sub.1, C.sub.IN, S.sub.P (the latter being a "split signal" to be described more particularly below, without S.sub.P, the signal is G.sub.10, which is a function of A.sub.1, B.sub.1, C.sub.IN); and P*.sub.1 is a function of A.sub.1, B.sub.1, S.sub.P (without S.sub.P the signal is P.sub.1).

As will also be described more particularly below, providing the higher intermediate combination signals P.sub.54, G.sub.54, P.sub.32, G.sub.32 produces a number of important advantages: Thus, it increases the number of bits per group, while reducing extreme output loads and extreme inputs into the "AND" gates and "OR" gates within the same time-unit delay. In addition, providing the G.sub.10 output signal permits more groups per section, more sections per division, etc., to be connected without producing extreme output loads, or extreme inputs into "AND" or "OR" gates. Also, the additional propagation delay of the overflow (OVR) signal is eliminated, thereby permitting shorter clock cycles and faster ALU operation.

FIG. 4b illustrates a six-bit system wherein the LLP.sub.1 logical level outputs even higher intermediate combination signals, these being a function of three-bit positions, rather than a single bit position as in the prior art of FIG. 2, or two-bit positions as in the arrangement illustrated in FIG. 4A. Tables 1, 2 and 3, at the end of this specification, show the output signals in the three arrangements of FIGS. 2, 4a and 4b, respectively:

It will be noted that in the circuits of FIGS. 4a and 4b constructed in accordance with the present invention, the inputs into the LLP, of the group includes not only the A.sub.N and B.sub.N signals but also the two additional signals identified as C.sub.IN and SP, which signals were absent from the inputs in the corresponding prior art circuits of FIGS. 1 and 2. Instead of introducing these two signals into the logical preparation level LLP.sub.1 of the respective CLA level, the prior art systems, as shown by the circuit of FIG. 1, introduces the signals C.sub.IN and S.sub.P, via the input signal C.sub.P, into the logical combination level LLC.sub.1 of the respective CLA level as in FIG. 5b.

Another feature of the present invention resides in separating the carry-in signal C.sub.IN into the LSB of the respective group, from the combined propagated carry signals C.sub.P between the groups, and introducing the C.sub.IN signal into the LLP.sub.1 logical level to be combined with the LSB's, and with the S.sub.P signal, as mentioned earlier, the S.sub.P signal is a binary "split" signal whose state determines whether or not the C.sub.IN signal will be operative. In this connection, it is to be pointed out that C.sub.IN is not an input for propagated carries, since C.sub.IN is combined at the LLP.sub.1 logical level, and therefore C.sub.IN will be used for not-propagated carries, e.g., initial carry C.sub.INIT, temporary carry storage, and other uses. Thus, as distinguished from the known circuitry (FIG. 1 and also in the 74S381), wherein the C.sub.IN signal is combined at the LLC logical level of the CLA system and is used also for combined least-significant-group carries, one of the features of the present invention is that the C.sub.IN signal is separated from the C.sub.P signal and is introduced into the LLP.sub.1 logical level of the CLA group for carries which are not propagated, whereas the C.sub.P signal is inputted into the LLC logical level of the respective group for propagated carries.

The following discussion explains the advantages in this feature of the invention:

Thus, by distinguishing between and separating these two carry input signals C.sub.IN and C.sub.P, and by adding the additional signal SP ("split-signal"), the carry-input signal becomes (C.sub.IN .multidot.SP+SP.multidot.C.sub.P), and the carry equations become:

Let us route the (C.sub.IN .multidot.SP) signal, to be assimilated in the CLA system, in a difference path. This is done by specifically combining (G.sub.1 +P.sub.1 .multidot.C.sub.IN .multidot.SP) to produce G*.sub.10 ; then G*.sub.10 =(G.sub.1 +P.sub.1 .multidot.C.sub.IN .multidot.SP). This may be done since C.sub.IN is not propagated and is therefore not delaying the completion of an arithmetical operation.

Let us also specifically combine P.sub.1 .multidot.SP to produce P*.sub.1 ; then P*.sub.1 =P.sub.1 .multidot.SP, and the specific carry equations become:

These specific CLA equations have the built-in feature of splitting an adder. Thus:

If (SP)="0", i.e., not split, then G*.sub.10 =G.sub.10 and P*.sub.1 =P.sub.1 ; therefore:

If (SP)="1", i.e. split, then P*.sub.1 .multidot.C.sub.P =0; therefore;

as we can see, P*.sub.1 performs two tasks; thus:

1 if (SP)="0", then P.sub.1 propagates C.sub.P

2 if (SP)="1", then P.sub.1 splits the adder.

G*.sub.1 also performs two tasks; thus:

1 if (SP)="0", then G*.sub.10 is as conventional G.sub.1

2 if (SP)="1", then G*.sub.10 acts to assimilate C.sub.IN into the adder and makes the G*.sub.O signal (discussed later) to act as C.sub.OUT.

The "Split" signal SP may also be used to split the ALU, as will be discussed more fully below particularly with respect to FIGS. 5 and 5a-5c.

Additional technical advantages of the foregoing arrangement, as compared to other known adders, are:

(a) extreme output loading within a group are reduced;

(b) extreme fan-in into "and" gates are reduced;

(c) extreme fan-in into "or" gates are reduced;

In addition, the C.sub.OUT output signal in conventional circuits is redundant. The C.sub.OUT signal may nevertheless be obtained since: if (SP)="1", then G*.sub.0 =C.sub.OUT, which leads to the possibility of connecting an additional least-significant group over a conventional 2-level CLA system (shown at position MO in FIG. 12, described below).

FIG. 1 illustrates a 4-bit "CLA" group.

The foregoing will be better understood by the specific implementations described below particularly with respect to FIGS. 9-11. However, at this point it may also be mentioned that the SP "split" signal potentially provides additional advantages, from the architectural standpoint, over and above the advantages discussed above. For example, the SP signal can also be used to split the ALU into separate units. This exploitation of the SP "split" signal will be better understood by reference to FIG. 5 and the accompanying FIGS. 5a-5c.

Thus, FIG. 5 diagramically illustrates a complete ALU having DATA-IN and SUM-OUT, and also C.sub.IN, C.sub.OUT, and OVR (overflow), for four groups of bits N.sub.1 -N.sub.4. The four-group ALU of FIG. 5 is equivalent to the four separate groups N.sub.1 -N.sub.4 illustrated in FIG. 5a, wherein it will be seen that each such group also has a C.sub.IN, C.sub.OUT and OVR. The propagation delay is a function of the time of addition, but since the OVR demands extra propagation delay, then as a practical matter there is a minimum propagation delay of one additional time unit.

FIG. 5a, which is equivalent to FIG. 5, shows that if the ALU is broken down into groups (e.g., for temporary carry storage use or for operation as four separate ALU's), each group must have a C.sub.IN and OVR for independent ALU operation, and also an additional C.sub.OUT if operated as a temporary carry storage system.

FIG. 5b illustrates a known arrangement to enable the foregoing system to be operated either together as a single group as shown in FIG. 5, or as individual groups N.sub.1 -N.sub.4 as shown in FIG. 5a. For such a capability, the system is equipped, between each group, with a logic unit receiving a "split" (SP) binary signal which, in one state, causes the ALU to operate as a single group as in FIG. 5, and in another state causes it to operate as individual groups as shown in FIG. 5a. In such known systems, however, the additional logic unit provided between each group introduces an additional propagation delay per addition.

FIG. 5c, however, illustrates how the "split" signal SP, in an ALU constructed in accordance with the present invention, permits the ALU to be operated either as one complete ALU, or as separate smaller ALU's, without any additional propagation delay. Not only does such a system, constructed in accordance with the invention, avoid the additional propagation delay, but it also improves the usual propagation delay in a normal ALU. Thus, as shown in FIG. 5c, the system includes an SP "split" signal, inputted with C.sub.IN into each group (actually into the LLP.sub.1 logical level) which, in one binary state ("0") of SP, causes the system to operate as one complete ALU, and in the other binary state ("1"), causes the system to operate as four separate ALU's, e.g. for temporary carry storage purposes or for other purposes. This aspect of the invention will also be better understood by the description below of several specific implementations, particularly as shown in FIGS. 9-11.

A further feature of the present invention enables a substantial improvement to be made in the overall architecture of the ALU. This feature will be best understood by reference to FIG. 6 which illustrates an ALU array according to the prior art, and FIGS. 7 and 7a which illustrate ALU arrays according to the present invention, FIG. 7 illustrating a 3-level CLA and FIG. 7a illustrating a 2-level CLA.

Thus, as shown in FIG. 6, the construction of the prior art ALU arrays, is based on two kinds of integrated circuits, these being shown in FIG. 6 as the ALU device 74181, and the CLA device 74182. Unfortunately, these known devices are logically not best divided into integrated-circuit groups. Thus, the existing ALU devices, such as the 74181, include the LLP (preparation) logical level of the second-level CLA system, and exclude the LLC (combination) logical level of the same-level CLA system. The existing CLA devices, such as the 74182, include the LLC logical level (having three combined carry outputs C.sub.N+X, C.sub.N+Y, C.sub.N+Z), of the second-level CLA system and the LLP logical level of the third-level CLA system (output P or X, G or Y). That is to say, generally speaking the existing CLA devices include the LLC (combination) logical levels of the N'th-level CLA system, and the LLP (preparation) logical levels of the (N+1)'th-level CLA system. Accordingly, when such devices as the 74181 and 74182 are wired together to form ALU arrays, long and circuitous wiring is required, as shown in FIG. 6.

The present invention, among its other advantages as discussed above, provides a better design, from a logic standpoint, for division into groups, thereby permitting a much simpler organization of an ALU array with substantially simpler and shorter wiring between the devices. Thus, the present invention permits both the LLP and LLC logical levels to be included in the same CLA device, e.g. in the same integrated circuit chip or chips, wherein the LLC logical level has only one combined carry output C.sub.P for the respective CLA level.

Such a new CLA design would also require the ALU device to be redesigned, either by excluding the LLP logical level of the second-level CLA system, or by including the LLC logical level of the second-level CLA system. However, such a redesign of the ALU device has also been suggested because of other in-group innovations; for example, the Fairchild 9340 is designed with both LLP.sub.2 and LLC.sub.2 logical levels of the second-level CLA system within the device.

According to this feature of the invention, the CLA device includes circuitry for implementing the following typical equations for the LLP and LLC logical levels:

This design would have the disadvantage of requiring a comparatively high number of pins (19) per device. However, it would have the extremely important advantage of permitting a much simpler organization of the ALU array, with substantially shorter and simpler wiring in between the devices. Further, one additional Head Group (i.e., the most signficant group, per most significant section), and one additional Head Section (i.e., the most significant section per most significant division), etc. may be connected without increasing extreme loads per output, and without increasing extreme inputs into "AND" and "OR" gates.

More particularly, both the LLP and LLC of the same second CLA level may be incorporated in one integrated circuit (IC) device or chip with either positive or negative logic inputs/outputs such as to permit a plurality of such IC chips to be connected together either alone to form a 2-level CLA system, or with additional IC chips to form a 3-level CLA system. Such a 2-level system is illustrated in FIG. 7a, wherein each ALU chip is identified as "Y"; and such a 3-level CLA system is illustrated in FIG. 7, wherein each ALU chip is also identified as "Y" and the additional CLA chip is identified as "Z". For example the "Y" chip in both FIGS. 7 and 7a may have a CLA circuit as illustrated in FIGS. 9-11, whereas the "Z" chip of FIG. 7 may have the circuit illustrated in FIG. 8.

Thus, each Y-chip may be constructed according to FIGS. 9, 10 or 11 (described more particularly below) to include, in one Y-chip, LLP circuitry having input logic of one sense and output logic of the opposite sense driving the LLC of the respective level and the LLP of the succeeding level. Assuming that the LLP input logic is "negative", and the output logic is "positive", the chip for the respective level would include LLC circuitry having positive input logic driven by the LLP circuitry of that level and the LLC circuitry of the succeeding level, and negative output logic driving the Sum Part of the respective group. Examples of circuitry that may be used for the Y-chip are illustrated in FIGS. 9-11, described more particularly below together with typical equations to be implemented by such circuitry as set forth in the tables appearing at the end of this application.

Such Y-chips can be connected together in the manner illustrated in FIG. 7a to form a 2-level CLA system, without any additional circuitry. However, by the addition of the Z-chip, illustrated in FIG. 8, such Y-chips can be connected together in the manner illustrated in FIG. 7 to produce a 3-level or higher-level CLA system.

As shown in FIG. 8, the Z-chip (of FIG. 7) includes first circuitry (i.e., the upper half of FIG. 8) having input logic of one sense (i.e., "positive"), and output logic of the opposite sense (i.e., "negative"); and second circuitry (i.e., the lower half of FIG. 8) of reverse-sense logic, i.e. negative input logic and positive output logic. Either circuitry can be used as the LLP or LLC for the third or higher-level CLA, depending on the logic of the previous CLA level. Thus, if the Y-chips include (as the case in FIGS. 9-11, to be described more particularly below) negative-to-positive logic in the LLP, and positive-to-negative logic in the LLC, then the upper circuitry in the Z-chip of FIG. 8 would be used as LLP, and the lower circuitry would be used as LLC. In such a case, the seven inputs in the upper (LLP) circuitry of FIG. 8 would be connected to the LLP output of the second-level CLA, and the two-outputs would serve as the LLP output for the third-level CLA; whereas the seven inputs in the lower (LLC) circuitry would be connected to the LLP of the third-level CLA, and one output would serve as the C.sub.P third-level CLA output. On the other hand, if the Z-chip of FIG. 8 is used with Y-chips in which the input and output logics are reversed, then the lower circuitry in FIG. 8 would be used as the LLP, and the upper circuitry in FIG. 8 would be used as the LLC.

Thus, whereas conventional CLA IC devices incorporate three LLC outputs and one pair of LLP outputs of the next CLA level, the Z-chip illustrated in FIG. 8 incorporates one pair of LLP outputs and one LLC output of the same CLA level, and is so designed to be useful with either positive or negative CLA logic. This permits a plurality of alternate reverse-logic CLA devices to be connected together to form a CLA system with minimum progagation delay, one inverter delay being saved for a two-level CLA system (FIG. 7a), and two inverter delays being saved with each additional CLA level (e.g. FIG. 7), when compared to existing devices such as the 74182.

The Z-device, which as noted above is used together with the Y-devices to provide a CLA system of more than 2 CLA levels, should implement the following typical logical equation: ##EQU1##

Such a Z-device would require 20 pins, would be useful for both sets of equations, and would provide the following advantages:

(a) no more than 6 loads per output (connected to 2 or 3 devices);

(b) no more than 4 inputs per "AND" gate;

(c) no more than 4 inputs per "OR" gate.

By adding P.sub.0-4 and G.sub.0-5 to G.sub.02 and P.sub.02 equations, we gain additional groups, sections, etc., while still keeping within the restriction of 6 loads per output; but in this case will be 5 inputs per "AND" gate, 5 inputs per "OR" gate, and 22 pins per device.

According to a still further feature of the present invention, the "Y" IC's including the LLP and LLC circuitry for 2 CLA levels may also include circuitry defining the Sum Part of the respective group, and further circuitry defining arithmetic-logic selectors and logic function selectors. This is more particularly described below with respect to the implementation illustrated in FIG. 10.

FIGS. 9-13 illustrate a number of preferred implementations of the foregoing concepts of the present invention.

It will be seen that the implementation illustrated in FIG. 9 is patterned after the prior art CLA system illustrated in FIG. 1, except that it includes the above-described "split" feature of separating the carry-in signal (C.sub.IN) inputted into the LLP, of the respective group, from the intermediate combined propagated carry signal (C.sub.P) between groups, and introducing the C.sub.IN signal into the input of the LLP.sub.1 logical level combined with the LSB signals and with the "split" signal (SP), the binary state of the latter signal determining whether the C.sub.IN is to be effective or not.

Thus, the FIG. 9 system, which may be incorporated in a single IC chip, includes only the circuitry defining a 4-bit CLA system, in which the logical circuitry shown at the upper portion (namely gates 4, 16 etc. outputting P*.sub.1, G*.sub.10, P.sub.2, G.sub.2, P.sub.3, G.sub.3 and P.sub.4, G.sub.4) define the LLP logical level, and the lower circuitry (namely gates 7, 8, 9, 10 outputting C.sub.1, C.sub.2, C.sub.3, C.sub.4) define the LLC logical level. The C.sub.IN signal is separated from the C.sub.P signal and is inputted, via gate 1 with the "split" signal SP, into gate 4, the latter constituting a "wide gate". The C.sub.IN signal is also applied, via lead 2, an inverter, and lead 6, into gate 7 of the LLC logical level, together with the C.sub.P signal from the succeeding LLC logical level via the logic circuitry including the wide gate 3. The C.sub.P signal is also outputted via lead 19 as the C.sub.OUT of the least significant groups of the ALU.

The propagated carry output P*.sub.0 and the generated carry output G*.sub.0 from the LLP logical level are applied, via logical circuitry 18 and 11, respectively, to the subsequent groups of the CLA system.

It will also be seen that the circuitry at the upper part of FIG. 9, defining the LLP logical level, is based on negative-to-positive logic, receiving negative inputs and producing positive outputs to the logic circuitry 7, 8, 9, and 10, defining the LLC logic of that respective CLA level, and also to the logic circuitry 11 and 18 defining the inputs to the next LLP logical level. It will also be seen that the LLC logical circuitry (elements 7-10) receives positive-logic inputs from the LLP circuitry of the respective CLA level, and also from the LLC circuitry 3 of the succeeding CLA level, and produces negative-logic outputs C.sub.1, C.sub.2, C.sub.3, C.sub.4.

Thus, the circuit illustrated in FIG. 9, which may be incorporated in a single IC as a part of the ALU to constitute a "Y" device (FIGS. 7, 7a) uses the pre-produced signals P.sub.2, P.sub.3, P.sub.4, G.sub.2, G.sub.3, G.sub.4, and the specific signals P*.sub.1 and G*.sub.10.

The C.sub.P signal is also used; it is a composition of several input signals according to the following equation: ##EQU2## The internal carry equations are as follows:

The generated carry output equation is as follows:

IF(SP)="0", then G*.sub.0 =G.sub.0

IF(SP)="1", then G*.sub.0 =C.sub.5 =C.sub.OUT

The carry propagating output equation is as follows:

IF(SP)="0", then P*.sub.o =P.sub.0, the CLA is not split and P*.sub.0 serves as conventional external CLA propagation.

IF(SP)="1", then P*.sub.0 =SPLIT, the CLA is split, and P*.sub.0 serves to disable external CLA propagation.

At gate 1 the signal C.sub.IN .multidot.SP is combined into the inverted signal C.sub.IN .multidot.SP 2 after having been separated from signal C.sub.P 3. Signal 2 then drives gate 4 to product the G*.sub.10 signal 5, which equals;

Signal 2 is inverted-back to produce (C.sub.IN .multidot.SP) 6 to drive gate 7 for producing C.sub.1. The signal 5 drives gates 8, 9, 10 and 11, as in a conventional CLA function.

Although gate 1 is in series with gate 4, it does not effect practical delays since the C.sub.IN signal is earlier produced, (see FIG. 10, input B, 26).

FIG. 9a illustrates a modification providing an alternative signal G.sub.10 *. Signals C.sub.IN (13) and SP(14) are directly combined via wide gate 12 to produce

The signal SP 15 drives gate 16 to produce P*.sub.1 17, which drives gates 8, 9, 10 and 18 as in a conventional CLA function.

Gate 11 combines the generated carry output G*.sub.0, and gate 18 combines the carry propagating output P*.sub.0. The C.sub.P signal 3 is also outputted at 19 to constitute the C.sub.OUT of the least significant groups of its ALU. This signal C.sub.P may also be outputted through an inverter to form C.sub.P.

If several such groups as described above are connected together for assembling a multibit ALU (see FIGS. 12, 13), then such an ALU may be split into parts, e.g. by programming, by firmware, by option block wiring, or by fixed wiring the SP signal at a desired inter-group position to be logical "1".

FIG. 9b illustrates a circuit similar to that of FIG. 9, except without the "split" signal SP, but otherwise including the same logical circuitry as described above with respect to FIG. 9.

See Table 4 appearing at the end of this specification, for a listing of the advantages available when using the implementation of both FIGS. 9 and 9b in an ALU constructed to include either a 3-level CLA as in FIG. 7 or a 2-level CLA as in FIG. 7a, as compared to the conventional ALU as in FIG. 6.

FIG. 10, with the set of equations appearing in Tables 2,5 at the end of this specification, illustrates an embodiment of a 6-bit ALU group.

This extended-length ALU group implements additional combined logic and includes complete basic ALU functions (see Note 2 at the end of the specification) as follows:

The functions included in the ALU are: Logical functions: "and", "or", "xor", "zero", "compare"; and Arithmetic functions: add, carry-in, overflow, zero, and C.sub.P output 19 (see Note 6).

The ALU logical components are as follows: An accumulator register RA 20, OVR 21 overflow output, zero 22 output, the logical functions "and", "or" and "xor" 23, formed in negative logic to reduce execution time of the logical functions, arith/.sub.LOGIC 24 "switch-over" input, and the input gate 25 which forms the signal C.sub.P 3. This gate 25 enables a direct connection of up to five groups (Note 3), with negative logic equations at inter-group CLA level, without any additional external logic (see FIG. 11). The inter-group, negative logic, carry equations, are as follows: ##EQU3##

If (SP)="1" then: C.sub.IN is the initial carry input, G*.sub.0 =C.sub.OUT =C.sub.7 and P*.sub.0 ="0", disables exterial propagation of C.sub.P that arrives from less significant groups.

If (SP)="0" then: C.sub.P is the carry input, G*.sub.0 =G.sub.0 =generated carry and P*.sub.0 =P.sub.0 =carry propagating signal.

The target of 6-bits per group is achieved by specifically combining "pair signals into one". The signals which are combined in these specific illustrations are:

(see equations of Table 5)

The functional advantage that has been achieved is maximum propagation delay (see Note 4) for 6 bit+C.sub.IN +C.sub.OUT +OVR arithmetic operation--3 wide gates+inverter (see Note 5).

The technical improvements that have been achieved are:

maximum fan-in into "and" gate -4 inputs

maximum fan-in into "or" gate -5 inputs (6 inputs for zero signal; 4 inputs without "split" function, 4-bit groups Such a six-bits group may be integrated to form one IC chip or a part of an ALU array.

By assembling five such ALU group components (see Note 3 and FIG. 11) in two-level CLA systems with negative logic at inter-group connections, --a complete 30-bit ALU plus carry-in plus over-flow, is achieved.

The maximum propagation delay is 5 wide gates+inverter (Notes 4, 5, 7).

If an ALU is assembled in three levels with negative-logic at inter-group connections and positive-logic at intersection connections (see Note 3 and FIG. 12), then up to 138 bits may be assembled in the ALU with maximum propagation delay of 7 wide gates+inverter (Notes 4, 5, 7).

It is also possible to assemble up to 498 bit per ALU with maximum propagation delay of 9 wide gates+inverter (Notes 3, 4, 5, 7).

Obviously such a long ALU seems to be over-practical, but since such an ALU can be split by programming into multiple ALU subunits by the splitting method, then multi-simultaneously-operations and the concept of variable length multiplication, division and other mathematical functions, together with a selected desired accuracy, can easily be implemented and executed.

Although the ALU may be physically hardwired in a three or four level CLA system, if split by programming within a section, then propagation delay of an individual ALU does not exceed one section delay; and if split into individual groups, then the maximum propagation delay is as for a one group delay.

FIG. 11, with the set of equations in Table 6 at the end of the specification illustrates an embodiment of an 8-bit CLA group within the restriction of eight loads per output. This compares very favorably with IBM's 5-bit group of Note 1 below wherein the fan-out exceeds 11 loads per output). This target is achieved by specifically combining "pair" and "quad" signals into "one" signal. The signals which are specifically combined in this specific illustration are, G.sub.32 =G.sub.3 +P.sub.3 .multidot.P.sub.2, G.sub.54 =G.sub.5 +P.sub.5 .multidot.G.sub.4, G.sub.76 =G.sub.7 +P.sub.7 .multidot.G.sub.6, P.sub.76 =P.sub.7 .multidot.P.sub.6 and P.sub.5432 =P.sub.5 .multidot.P.sub.4 .multidot.P.sub.3 .multidot.P.sub.2.

The main functional improvement that is achieved per 8-bit full adder+C.sub.IN +C.sub.out is maximum propagation delay of 3 wide gates+inverter (Notes 4,5).

The technical improvements are:

Maximum fan-in into "and" gate is 5

Maximum fan-in into "or" gate is 5

The eight-bit group permits a 40-bit ALU in two levels with maximum propagation delay of 5 wide gates+inv, while intergroup loads are restricted (see Notes 3,4,7), or to a 184-bit ALU in three levels with maximum propagation delay of 7 wide gate+inv (Notes 3, 4, 7).

If output loads have to be restricted and not to exceed 4 loads per output, then by grouping 3 bits in a group:

in a two-level CLA 5 wide+inv. we gain 12 bits;

in three-level CLA 7 wide+inv. we gain 30 bits;

in four-level CLA 9 wide+inv. we gain 66 bits.

Additional technical improvements are:

Maximum fan-in into "and" gate 3;

Maximum fan-in into "or" gate 3:

By connecting A.sub.0 to C.sub.IN, B.sub.0 to SP and C.sub.P inputs to +Vcc, then the eight-bits CLA system of FIG. 10 can be used to constitute a ten-bit adder where G.sub.0 * is the carry to the tenth bit, and without initial carry input. The maximum propagation delay is 3 wide gates+INV (see Note 4).

The following additional features apply to any group described herein:

The ALU may include four-levels, using an alternate positive-negative-logic technique, which would have less propagation delay than a 3-level CLA system with positive logic or negative logic at interconnections.

The ALU may also be split into 2 bits per group, and within the restriction of 4 loads per output, it is still possible to assemble 60 bits with 9 wide gate+inv. delay.

If 6 loads are permitted, then up to 166 bits may be assembled in 4 levels, or 46 bits in 3 levels.

Two bits per group with temporary carry storage fits multiplication processing wherein 2 bits are decoded per step.

FIG. 12 illustrates how a standard printed circuit card may be designed to assemble components in different combinations. Let us first refer to the following groups as:

Groups M.sub.1, M.sub.2, M.sub.3 together as a section;

Group M.sub.0, the least significant group, as the tail group; and

Group M.sub.4, the most significant group, as the head group.

The standard printed circuit card may be assembled either with:

(a) 5 groups--M.sub.0, M.sub.1, M.sub.2, M.sub.3, M.sub.4 --to become a two level array of a 30-bit ALU (if 6 bits per group); or

(b) higher CLA levels as:

(1) a section including M.sub.1, M.sub.2, M.sub.3 assembled with additional appropriate input and output signals logic; or

(2) as a tail-section including M.sub.0, M.sub.1, M.sub.2, M.sub.3, assembled with the additional appropriate output signals logic; or

(3) as a head-section including M.sub.1, M.sub.2, M.sub.3, M.sub.4, assembled with the additional appropriate input signals logic.

It will thus be seen that the standard printed circuit card can be assembled with 5 groups (M.sub.0, M.sub.1, M.sub.2, M.sub.3, M.sub.4) to form a 2-level CLA system without any additional logic circuitry, in which case all the "E" bridges would be disconnected. Alternately, the card may be assembled as a section including group M.sub.1, M.sub.2, M.sub.3, with additional appropriate input gates, as shown on the right side of FIG. 12, and output gate R.sub.N, T.sub.N, and T.sub.(N-1). This latter combination is illustrated in FIG. 13, including printed circuit boards PC.sub.1 -PC.sub.5. All "P" points have to be bridged, besides E.sub.8, and the left side of E.sub.8 has to be connected to +V.sub.CC.

A further alternative is to connect the cards as a Tail Section including groups M.sub.0, M.sub.1, M.sub.2 and M.sub.3, with the additional appropriate output gates. In this case only R.sub.N is used, the latter also being used as PC.sub.0 in FIG. 13; all "E" points have to be bridged besides E.sub.1.

A further alternative is to connect the card as a Head Section including groups M.sub.1, M.sub.2, M.sub.3, M.sub.4, assembled with additional appropriate input gates, on the right side of FIG. 12. This arrangement is used as PC.sub.6 in FIG. 13; only E.sub.1 has to be bridged.

FIG. 13 illustrates an array of 5 sections plus one head-section, plus one tail-section, to make 23 groups in three levels, this being gained by combining specific signals, "three into one signal" 27 and "six into one signal 28.

Maximum fan-in into "and" gate-4-inter-section level.

Maximum fan-in into "or" gate-6 at inter-section level.

While the invention has been described with respect to a number of preferred embodiments, it will be appreciated that these are illustrated for purposes of example only, and that many other variations, modifications and applications of the invention may be made.

1. Report "high speed arithmetic in binary circuits" published by O. L. MacSorley in Proc. of the IRE Jan. 1961.

2. This practical 6 bits ALU group circuit, was selected to show the withstanding in the restriction imposed (Note 3).

3. Restrictions were made not to exceed six loads per output.

4. If the output wide gates 29 are combined as a bit input to a register then Maximum propagation delay is reduced by one wide gate.

5. Maximum logical functions delay--2 wide gates (Note 4).

6. This signal C.sub.P, demands additional output load. The use of this signal to produce a temporary carry storage (carry save) must be considered due to the fast addition.

7. Due to distances at inter-groups or inter sections connections additional delay must be taken into account.