GB2215496A - Multi-stage parallel binary adders and/or subtractors - Google Patents

Abstract

A multi-stage parallel binary adder and/or subtractor has a plurality of stages 0-31 divided into a plurality of groups p1-p16 of consecutive stages. Each group of stages can produce a carry propagate signal and/or carry generate signal respectively for controlling a series-connected MOS transistor and a shunt-connected MOS transistor along a carry path. A carry break signal produced by NAND gates M1, M2 ---, selectively disconnects the carry propagate signal(s) from the series-connected transistor(s) and blocks the conduction of the shunt connected transistor to separate the carry output from one group of stages from the carry path of the next group. The stages may form a single adder/subtractor, or may be divided into independent equal groups of 2, 4, 8, or 16 stages, depending on selection signals J, K1-K4. <IMAGE>

Description

IMPROVEMENTS IN OR RELATING TO MULTI-STAGE PARALLEL BINARY ADDERS AND/OR SUBTRACTORS This invention relates to multi-stage parallel binary adders and/or subtractors and is particularly concerned with such devices that can readily be switched to operate as a plurality of smaller adders and/or subtractors.

An arithmetic logic unit (ALU) in a graphics signal processor is required to perform a number of different functions. Among the arithmetic functions required is that the unit can act as an adder or subtractor for 32-bit long words, say, and also that it can act on small groups, say 2-bits, for processing of picture elements (pixels).

Because a high pixel rate is required to produce a high definition display it is desirable to be able to convert a thirty two-stage adder into sixteen two-stage adders, so that sixteen pixels can be processed at the same time. A method which could be adopted to divide a thirty two-stage adder into sixteen separate two-stage adders is to add gating transistors to the carry path between the two-stage blocks, so that a carry signal from one two-stage block can be stopped from being applied to the next two-stage block. This method suffers from the disadvantage that the fifteen additional transistors impose an undesirable extra delay on a carry signal propagating along the carry path when the adder is operating as a single thirty twostage unit.

The extra carry path delay produced by the gating transistors can be reduced by using only half of the thirty two stages to form eight blocks each of two stages, because then only seven extra gating transistors are required.

This means that half of the potential processing power of the adder is discarded when processing pixels and this can undesirably restrict the definition of the display. In addition the inclusion of seven extra transistors in the carry path may produce an unacceptable delay.

It is an object of the present invention to enable the carry path of a multi-stage adder and/or subtractor to be subdivided without imposing extra delay on the propagation of a carry signal along the path.

According to the present invention there is provided a multi-stage parallel binary adder and/or subtractor having the stages divided into a plurality of groups of consecutive stages, each group of stages having a carry propagate signal output and a carry generate signal output, and a carry path along which a carry signal can be propagated, the carry path including a plurality of series connected gating means respectively responsive to carry propagate signal outputs from the groups of stages, there being connected to the carry path a plurality of carry signal generating circuits respectively responsive to the carry generate signal outputs of the groups of stages to apply carry signals to the carry path, wherein each group of stages includes means responsive to a carry break signal to inhibit the production of the carry propagate and carry generate signals by the group and to provide a separate carry output signal from the group, so that the groups of stages can operate in response to the application of the carry break signal to them variously as independent parallel binary adders and/or subtractors having one or more groups of stages or as a single binary adder and/or subtractor including all the stages.

For the sake of brevity in the following the term "adder" will be used to mean "adder and/or subtractor", except where it is clear from the context that an adder as opposed to a subtractor is being meant.

One example of the adder may have thirty two stages, and each group may have two stages. The adder may be arranged to operate selectively as sixteen separate adders each having two stages, as eight separate adders each having four stages, as four separate adders each having eight stages, as two separate adders each having sixteen stages or as a single adder having thirty two stages. A decoding circuit may be provided to control the separation of the adder into adders of fewer stages.

Means may be provided to apply a carry input to the stage of least significance of each separate adder and to invert one set of input bits to each adder, whereby each adder acts as a subtractor.

The adder may be constructed using any type of logic circuits. It may use MOS dynamic logic. Each of the gating means connected in the carry path may be a single MOS transistor to the gate of which the carry propagate signal from the associated group of stages is controllably applied. A shunt transistor circuit connected from the carry path to a reference potential may constitute the carry signal generating circuit responsive to the carry generate signal from the associated group of stages to apply a carry signal to the carry path. The carry break signal may operate a gate connected to the gate of the single MOS transistor so as to control the application of the carry propagate signal to it.Another transistor may be connected in series with the shunt connected transistor and may be controlled by the carry break signal to control the application of carry signals to the carry path from the carry generate signal.

An example of an adder embodying the invention will now be described with reference to the accompanying drawings, of which: Figure 1 is a block diagrammatic circuit of the adder; Figure 2 shows a block representing two stages of the adder as used in Figure 1; and Figure 3 is a detailed diagram of two stages of the adder constructed using MOS dynamic logic.

The example of an adder embodying the invention shown in Figure 1 has thirty two stages in sixteen pairs represented by the blocks Pl, P2, P3 ..... P16. Only some of the blocks are shown in Figure 1 for the sake of clarity. The connections to each of these blocks are shown in Figure 2. The inputs for the two pairs of bits to be added and the outputs for the sum bits are not shown since these are not affected by the division of the adder into separate smaller adders. Each of the blocks P receives an ARITHMETIC ENABLE signal via a conductor A. The INJECT CARRY signal is applied in inverted form to a conductor B which is connected through an inverter to the block Pl, and through NOR gates N2 to N16 to blocks P2 to P16 respectively. A carry path extends from one block P to the next starting from the first block P1 and ending at the last block P16. Between alternate pairs of adjacent blocks P2 and P3, P4 and P5, P6 and P7, P8 and P9, P10 and Pll, P12 and P13, and P14 and P15 there are provided carry signal regeneration circuits L, each consisting of an inverter driving the gate of an MOS transistor connected from the carry path input of the next block P and ground, with a second MOS transistor connected from the carry path input to the supply voltage VCC and receiving on its gate a pre-charge signal ~P.

Each of the blocks P has an input for a CARRY BREAK signal in inverted form, which serves to disable the normal carry path so that the blocks can be used separately as part of an adder having only some of the sixteen blocks. The way in which the CARRY BREAK signal is used in the particular form of the adder stages shown in Figure 3 will be described in detail with reference to that Figure. Each block has a "CARRY OUT" output connection, on which appears any carry signals produced by the pair of stages in the block; this is an output of carry signals additional to the carry path mentioned above and is of value as an overflow bit output when the particular block contains the two stages of highest significance of a separate small adder when the 32-bit adder is divided up.

The CARRY BREAK signals are produced by four NAND gates, M1, M2, M3 and M4, which are connected to the carry break inputs of the blocks P as follows: the output of the gate M1 is connected to the blocks Pl, P3, P5 P15. The output of the gate M2 is applied to the blocks P2, P6, P10 and P14. The output of the gate M3 is connected to the blocks P4 and P12. The output of the gate M4 is connected to the block P8. The gate M1 is a five input NAND-gate and receives on its five inputs signals K1, K2, K3, K4 and J. The gate M2 is a four input NAND-gate and receives on its inputs the signals K2, K3, K4 and J. The gate M3 is a three input NAND-gate and receives on its inputs the signals K3, K4 and J.The gate M4 is a two input NAND-gate and receives on its inputs the signals K4 and J. The signals K1, K2, K3 and K4 are selection signals and the signal J is a gating signal which is applied to the gates M1, M2, M3 and M4 when CARRY BREAK signals are required.

The CARRY BREAK input to each of the blocks P1 to P15 is also connected to an input of the one of the NORgates N2 to N16 connected to the INJECT CARRY input of the next block P. The purpose of the INJECT CARRY inputs and the NOR-gates N2 to N16 is to permit the adder or adders to be used as subtractors. To enable a binary number to be subtracted from another binary number, what is required is that the individual bits of the number being subtracted are inverted, i.e., 1 changed to 0 and 0 changed to 1.

In addition, a carry input is applied to the first stage of the adder or of each adder when the circuit is operating as several separate adders. It can be shown that these operations enable a multi-bit parallel adder to operate as a multi-bit parallel subtractor.

The application of the signals J, K1, K2, K3 and K4 to the gates M1, M2, M3 and M4 and the connections of the outputs of those gates to the blocks P1 to P15 are so arranged that, when the signals K4 and J only are present, the output of the gate M4 goes low, causing a low signal to be applied to the carry break output of the block P8. The effect of this is to break the carry path connection between the blocks P8 and P9 so that the circuit can operate as two separate 16-bit adders instead of a 32-bit adder. The application of the low signal to an input of the NOR-gate N9 connected to the INJECT CARRY input of the block P9 enables the blocks P9 to P16 to operate as a subtractor as well as an adder, if required to do so.

If the signals K3, K4 and J are all present, then both gates M3 and M4 produce low outputs which divides the adder into four separate 8-bit adders. If the signal K2 is present as well as the signals K3, K4 and J, the output of the gate M2 also goes low, dividing an adder into eight 4-bit adders. If all five signals K1, K2, K3, K4 and K5 are present, then outputs of all four gates M1, M2, M3 and M4 go low, so that each of the blocks P, except for P16, which does not require it, receives a CARRY BREAK signal so that the sixteen blocks can act as separate 2-bit adders.

A realisation of one of the blocks P using dynamic MOS logic is shown in Figure 3, the particular block including the stages n and n+l. The modifications to the circuit required to enable its separation from a following block when a plurality of separate adders are required involve the addiition of components bearing the references Q to X and the substitution of a NOR-gate Z for an inverter.

It will be apparent that the modifications would not contribute to the propagation delay of a carry signal along the carry path when all the blocks P are used together as a single 32-bit adder, because none of the components Q to X and Z is connected in series in the carry path.

In Figure 3 the stage numbers increase and the carry propagation takes place from right to left as in Figure 1.

Each adding stage consists of a half-adder consisting of the transistors 39 to 43 (for the stage n) and transmission gates 30 and 31 (for the stage n) which combine the "sum" output bit of the half adder with an incoming carry bit to produce the "sum" output bit (Dn) of the adding stage. A transmission gate consists of an N-channel MOSFET and a P-channel MOSFET connected in parallel with appropriate signals applied to their gates so that they are turned off and on together; such a gate has the advantage that it produces substantially no attenuation of the logic signal levels.

Considering the stage n of the adder, the transistors 39 to 43 together with the associated inverters function as a half-adder in response to inverted input bits An and Bn to produce a carry propagate signal Pn and a carry generate signal Gn. The further inversion of the bit Bn which is required when the adder is to be used as a subtractor may be effected by duplicating the paths including the transistors 39 and 50 and 40 and 49, with the connections to the gates of the duplicates of the transistors 39 and 40 swapped over, and with a "subtract enable" signal applied to the gates of the duplicates of the transistors 49 and 50 in place of the ~E signal.The ARITHMETIC ENABLE signal of Figure 1 is shown as ~E in Figure 3 and the circuit will operate as an adder only when ~E is applied to the gates of transistors 49-52 and to the gate of transistor 38. When required to operate as a substractor the signal ~E is applied to the gates of the duplicates of the transistors 49-52 and to the gate of the transistor 38. The signal Pn is applied to the inputs of the transmission gates 30 and 31, through an inverter in the case of the gate 31, and these gates are controlled by a carry signal Cn-l derived by inverting the signal on a conductor 6.

The output of the transmission gates 30 and 31 forms the sum signal Dn of the stage n.

The stage n+l is of similar construction to the stage n, receiving inverted input bits An+l and Bn+l and producing a carry propagate signal Pn+l and a carry generate signal Gn+l.

An incoming carry signal is applied in inverted form to the conductor 6 which forms the input of the carry propagate path of the adder stages. The conductor 6 is connected to conductor 7 forming the carry path output through a transistor 8. The conductor 7 is connected to a voltage supply VCC through transistor 14 which is rendered conducting by a pre-charge signal ~P.

In the control of the propagation and generation of carries, the stages of the adder are grouped in pairs, stages 0 and 1 together, stages 2 and 3 together, stage 4 with stage 5, and so on as shown in Figure 1. Since the circuits are the same for each pair of stages, only the circuit associated with stages n and n+l will now be described. The incoming carry signal is applied via an inverter 16 to the carry input of stage n. The output of the inverter 16 is applied to the gate of a transistor 35 which is connected in series with a transistor 36 controlled by Pn, the carry propagate signal from stage n.

The output of the transistor 35 is the carry signal Cn and is connected to the carry input of stage n+l. The signal Pn is applied together with a signal Pn+l from stage n+l to the inputs of NAND-gate 19, the output of which controls the transistor 8 through a NOR-gate Z. Since the signals Pn and Pn+l represent the carry propagate signals from the stages n and n+l, it will be apparent that when combined by the NAND-gate 19 they serve to convey an inverted carry input signal through the transistor 8 to the conductor 7. The carry generate signal Gn from the stage n after inversion by a transistor 34 forms a second carry input to stage n+l. The signal Gn is also applied to a NAND-gate 22 together with the carry propagate signal Pn+l from stage n+l and the output of the gate 22 is applied to a NAND-gate 24.The NANDgate 24 also receives the carry generate signal Gn+l from the stage n+l after inversion and produces an output used to control a transistor 26 connected in a series path from the conductor 7 to ground. The inverted CARRY BREAK signal is applied to the gate of a transistor 53 connected in series with the transistor 26 and also to a second input of the NOR-gate Z.

The circuitry just described performs the logical operations to combine the carry propagate and carry generate signals from the stages n and n+l so that a signal representing the inverted carry from the stage n+l is correctly produced with the only delay imposed on the propagation of a carry input applied in inverted form to the conductor 6 is that due to the transistor 8. The form of logic used in the carry path shown is the same as that used in the rest of the circuit and is known as dynamic MOS logic; it operates by the pre-charging of the conductors 6, 7 to the voltage VCC by the pre-charge signal ~P and their selective discharge depending on the data bit carried.A carry is represented by the discharge of the appropriate conductor to ground, the conductor 6 being discharged to represent an incoming carry signal by means in the preceding stage, not shown, although a NOR-gate W connected to the gate of a transistor X is shown for the purpose of carry injection on to the conductor 6 for enabling the adder to be used as a subtractor. The transistor 26 serves to discharge the conductor 7 if the transistor 8 does not conduct, this being the situation if the stages n and n+l produce a carry output although they may not necessarily propagate a carry from the conductor 6.If both stages n and n+l produce a carry propagate signal, that is to say both Pn and Pn+l are present, then the NAND gate 19 will respond and cause the NOR gate Z to apply a signal to the transistor 8 to cause it to conduct so that any inverted carry input signals will discharge the conductor 7.

Stages n and n+l together will produce a carry output regardless of the carry input if either the stage n+l produces a carry generate signal or stage n produces a carry generate signal Gn and stage n+l produces a carry propagate signal Pn+l. In the latter case, the NAND-gate 22 reacts and applies the signal to the NAND-gate 24 and in the former case the signal Gn+l is applied directly to the NAND-gate 24. When either of these is present, the gate 24 switches on the transistor 26 to discharge the conductor 7, provided that the CARRY BREAK signal is not being applied to the transistor 53 to disable the discharge path. The CARRY BREAK signal is also applied through the inverter Q to disable the NOR-gate Z and prevent a carry being applied to the oonductor 7 through the transistor 8.

Incoming carries to stage n can be derived from the conductor 6 only and are fed to the stage n through the inverter 16. Incoming carries to stage n+l can be derived from the conductor 6 if stage n is producing a carry propagate signal Pn when the transistor 36 conducts.

In addition, the stage n can produce a carry generate signal Gn and this is applied through the transistor 34 to the stage n+l.

The pre-charge clock signal ~P is used in Figure 3 to enable the functioning of the logical circuitry of the adding stages. The ARITHMETIC ENABLE signal is employed in Figure 3 to enable the selective discharge of the conductors precharged by the pre-charge clock in response to the logical combination of signals applied to the transistors of the circuits involved. The pre-charge clock ~P and the ARITHMETIC ENABLE signal are applied alternately to their respective connections.

From a consideration of the circuit described above with reference to Figure 3, it will be apparent that the carry chain includes only a single series connected transistor for every two stages of the adder so that the propagation delay of the carry signal along the carry chain is not affected by the addition of components 0 to X and the replacement of an inverter by the NOR-gate Z to enable the division of the single adder having thirty two stages into two adders having sixteen stages each, or sixteen adders having two stages each, for example.

When it is required to disconnect the carry output of the stage n+l from the conductor 7, the CARRY BREAK signal is applied to the two conductors so marked in Figure 3. The CARRY BREAk signal performs three functions: a) It turns off the transistor 53, thereby preventing carry signals from being applied to the conductor 7 from the transistor 26.

b) It closes the gate Z, thereby preventing incoming carries to the stage n on the conductor 6 being propagated through the transistor 8.

c) It enables the gate W of stage n+2 (not shown) to pass a CARRY INJECT signal so that the next group of stages can operate as a subtractor as described above.

It may be required to provide a carry output from the stage n+l when the connection to the carry path conductor 7 is disabled. This carry output is provided by the components R, S, T, U and V. A NAND-gate R performs an equivalent function to that of the transistor 8, logically combining the inverted carry signal from the conductor 6 with the inverted output of the NAND-gate 19.

A NAND-gate T operates as an OR-gate to pass the inverted output of the NAND-gate 24 or the output of the NAND-gate R, or both, through an inverter V to the carry output.

Although the invention has been described with reference to a specific embodiment, it is not limited to the embodiment described. For example, the adder may be constructed from any kind of digital logic circuitry, and may, if desired, include different kinds of such circuitry. The adder may include as many or as few stages as are required for a particular application and may be capable of being subdivided in different ways from those described. It would be possible for the subdivision to produce a plurality of separate adders of different numbers of stages. The adders may be constructed to operate as adders only, without the capability of being operated as subtractors.

Claims (7)

CLAIMS:

1. A multi-stage parallel binary adder and/or subtractor having the stages divided into a plurality of groups of consecutive stages, each group of stages having a carry propagate signal output and a carry generate signal output, and a carry path along which a carry signal can be propagated, the carry path including a plurality of seriesconnected gating means respectively responsive to carry propagate signal outputs from the groups of stages, there being connected to the carry path a plurality of carry signal generating circuits respectively responsive to the carry generate signal outputs of the groups of stages to apply carry signals to the carry path, wherein each group of stages includes means responsive to a carry break signal to inhibit the production of the carry propagate and carry generate signals by the group to provide a separate carry output signal from the group, so that the groups of stages can operate in response to the application of the carry break signal to them variously as independent parallel binary adders and/or subtractors having one or more groups of stages or as a single binary adder and/or subtractor including all the stages.

2. A multi-stage parallel binary adder and/or subtractor according to claim 1 further including decoding means responsive to a plurality of control signals to produce a selected one of a plurality of carry break signals, each being connected to separate the stages into a plurality of groups of stages of the same size, the different carry break signals separating the stages into groups of different sizes.

3. A multi-stage parallel binary adder and/or subtractor according to claim 2 having 32 stages wherein the decoding means produces carry break signals connected to divide the stages into groups in at least some of the following ways: 2 groups of 16 stages; 4 groups of 8 stages; 8 groups of 4 stages; 16 groups of 2 stages.

4. A multi-stage parallel binary adder and/or subtractor according to any preceding claim wherein each stage is constructed as an adder and means is provided for applying a carry input to the stage of least significance of a group comprising all the stages or of each group of stages if the stages are divided into smaller groups and for inverting the logical state of one set of input bits to the or each group of stages, whereby the or each group can operate as a subtractor.

5. A multi-stage parallel binary adder and/or subtractor according to any preceding claim wherein the stages are constructed using dynamic MOS logic, each series-connected gating means in the carry path includes a single MOS transistor, having its channel connected in the carry path and to the gate of which a carry propagate signal is applied, and the carry signal generating circuit includes an MOS transistor connected in a shunt path from the carry path to a reference potential to the gate of which a carry generate signal is applied.

6. A multi-stage parallel binary adder and/or subtractor according to claim 5 including for each of the seriesconnected gating means in the carry path a further gating means in the connection for applying the carry propagate signal to the gate of the single MOS transistor, and in each carry signal generating circuit an additional MOS transistor is connected in series with the MOS transistor in the shunt path, the further gating means and the additional MOS transistors being controlled by the carry break signal or one of the carry break signals.

7. A multi-stage parallel binary adder and/or subtractor substantially as described herein and as illustrated by the accompanying drawings.