I. Introduction
Arithmetic circuits are the ones which perform arithmetic operations like addition, subtraction, multiplication, division, parity calculation. Most of the time, designing these circuits is the same as designing muxers, encoders and decoders.
II. Content
1. Combinational Arithmetic Circuits Part-I
2. Combinational Arithmetic Circuits Part-II
3. Combinational Arithmetic Circuits Part-III
4. Combinational Arithmetic Circuits Part-IV
In the next few pages we will see few of these circuits in detail.
Adders
Adders are the basic building blocks of all arithmetic circuits; adders add two binary numbers and give out sum and carry as output. Basically we have two types of adders.
- Half Adder.
- Full Adder.
Half Adder
Adding two single-bit binary values X, Y produces a sum S bit and a carry out C-out bit. This operation is called half addition and the circuit to realize it is called a half adder.
Truth Table
X | Y | SUM | CARRY |
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
Symbol
S (X,Y) = (1,2) |
S = X'Y + XY' |
S = X Y |
CARRY = XY |
Circuit
Full Adder
Full adder takes a three-bits input. Adding two single-bit binary values X, Y with a carry input bit C-in produces a sum bit S and a carry out C-out bit.
Truth Table
X | Y | Z | SUM | CARRY |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
SUM (X,Y,Z) = (1,2,4,7)
CARRY (X,Y,Z) = (3,5,6,7)
Kmap-SUM
SUM = X'Y'Z + XY'Z' + X'YZ'
SUM = X Y Z
Kmap-CARRY
CARRY = XY + XZ + YZ
Full Adder using AND-OR
The below implementation shows implementing the full adder with AND-OR gates, instead of using XOR gates. The basis of the circuit below is from the above Kmap.
Full Adder using AND-OR
Circuit-SUM
Circuit-CARRY
n-bit Carry Ripple Adder
An n-bit adder used to add two n-bit binary numbers can be built by connecting n full adders in series. Each full adder represents a bit position j (from 0 to n-1).
Each carry out C-out from a full adder at position j is connected to the carry in C-in of the full adder at higher position j+1. The output of a full adder at position j is given by: Sj= Xj Yj Cj
Cj+1 = Xj . Yj + Xj . Cj + Y . Cj
In the expression of the sum Cj must be generated by the full adder at lower position j. The propagation delay in each full adder to produce the carry is equal to two gate delays = 2 D Since the generation of the sum requires the propagation of the carry from the lowest position to the highest position , the total propagation delay of the adder is approximately:
Total Propagation delay = 2 nD
4-bit Carry Ripple Adder
Adds two 4-bit numbers:
X = X3 X2 X1 X0
Y = Y3 Y2 Y1 Y0
producing the sum S = S3 S2 S1 S0 , C-out = C4 from the most significant position j=3
Total Propagation delay = 2 nD = 8D or 8 gate delays
Larger Adder
Example: 16-bit adder using 4 4-bit adders. Adds two 16-bit inputs X (bits X0 to X15), Y (bits Y0 to Y15) producing a 16-bit Sum S (bits S0 to S15) and a carry out C16 from the most significant position.
Propagation delay for 16-bit adder = 4 x propagation delay of 4-bit adder
= 4 x 2 nD = 4 x 8D = 32 D
or 32 gate delays
Carry Look-Ahead Adder
The delay generated by an N-bit adder is proportional to the length N of the two numbers X and Y that are added because the carry signals have to propagate from one full-adder to the next. For large values of N, the delay becomes unacceptably large so that a special solution needs to be adopted to accelerate the calculation of the carry bits. This solution involves a "look-ahead carry generator" which is a block that simultaneously calculates all the carry bits involved. Once these bits are available to the rest of the circuit, each individual three-bit addition (X_{i}+Y_{i}+carry-in_{i}) is implemented by a simple 3-input XOR gate. The design of the look-ahead carry generator involves two Boolean functions named Generate and Propagate. For each input bits pair these functions are defined as:
Gi = Xi . Yi
Pi = Xi + Yi
The carry bit c-out(i) generated when adding two bits Xi and Yi is '1' if the corresponding function Gi is '1' or if the c-out(i-1)='1' and the function Pi = '1' simultaneously. In the first case, the carry bit is activated by the local conditions (the values of Xi and Yi). In the second, the carry bit is received from the less significant elementary addition and is propagated further to the more significant elementary addition. Therefore, the carry_out bit corresponding to a pair of bits Xi and Yi is calculated according to the equation:
carry_out(i) = Gi + Pi.carry_in(i-1)
For a four-bit adder the carry-outs are calculated as follows
carry_out0 = G0 + P0 . carry_in0
carry_out1 = G1 + P1 . carry_out0 = G1 + P1G0 + P1P0 . carry_in0
carry_out2 = G2 + P2G1 + P2P1G0 + P2P1P0 . carry_in0
carry_out3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1 . carry_in0
The set of equations above are implemented by the circuit below and a complete adder with a look-ahead carry generator is next. The input signals need to propagate through a maximum of 4 logic gate in such an adder as opposed to 8 and 12 logic gates in its counterparts illustrated earlier.
Sums can be calculated from the following equations, where carry_out is taken from the carry calculated in the above circuit.
sum_out0 = X 0 Y0 carry_out0
sum_out1 = X 1 Y1 carry_out1
sum_out2 = X 2 Y2 carry_out2
carry_out1 = G1 + P1 . carry_out0 = G1 + P1G0 + P1P0 . carry_in0
carry_out2 = G2 + P2G1 + P2P1G0 + P2P1P0 . carry_in0
carry_out3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1 . carry_in0
BCD Adder
BCD addition is the same as binary addition with a bit of variation: whenever a sum is greater than 1001, it is not a valid BCD number, so we add 0110 to it, to do the correction. This will produce a carry, which is added to the next BCD position.
- Add the two 4-bit BCD code inputs.
Determine if the sum of this addition is greater than 1001; if yes, then add 0110 to this sum and generate a carry to the next decimal position.
Subtracter
Subtracter circuits take two binary numbers as input and subtract one binary number input from the other binary number input. Similar to adders, it gives out two outputs, difference and borrow (carry-in the case of Adder).
There are two types of subtracters.
- Half Subtracter.
- Full Subtracter.
Half Subtracter
The half-subtracter is a combinational circuit which is used to perform subtraction of two bits. It has two inputs, X (minuend) and Y (subtrahend) and two outputs D (difference) and B (borrow). The logic symbol and truth table are shown below.
Symbol
Truth Table
X | Y | D | B |
0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
From the equation we can draw the half-subtracter as shown in the figure below.
Full Subtracter
A full subtracter is a combinational circuit that performs subtraction involving three bits, namely minuend, subtrahend, and borrow-in. The logic symbol and truth table are shown below.
Symbol
Truth Table
X | Y | Bin | D | Bout |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 |
From above table we can draw the Kmap as shown below for "difference" and "borrow". The boolean expression for difference and borrow can be written.
D = X'Y'Bin + X'YBin' + XY'Bin' + XYBin
= (X'Y' + XY)Bin + (X'Y + XY')Bin'
= (X Y)'Bin + (X Y)Bin'
= X Y Bin
Bout = X'.Y + X'.Bin + Y.Bin
From the equation we can draw the half-subtracter as shown in figure below.
From the above expression, we can draw the circuit below. If you look carefully, you will see that a full-subtracter circuit is more or less same as a full-adder with slight modification.
Parallel Binary Subtracter
Parallel binary subtracter can be implemented by cascading several full-subtracters. Implementation and associated problems are those of a parallel binary adder, seen before in parallel binary adder section.
Below is the block level representation of a 4-bit parallel binary subtracter, which subtracts 4-bit Y3Y2Y1Y0 from 4-bit X3X2X1X0. It has 4-bit difference output D3D2D1D0 with borrow output Bout.
Serial Binary Subtracter
A serial subtracter can be obtained by converting the serial adder using the 2's complement system. The subtrahend is stored in the Y register and must be 2's complemented before it is added to the minuend stored in the X register.
The circuit for a 4-bit serial subtracter using full-adder is shown in the figure below.
Comparators
Comparators can compare either a variable number X (xn xn-1 ... x3 x2 x1) with a predefined constant C (cn cn-1 ... c3 c2 c1) or two variable numbers X and Y. In the first case the implementation reduces to a series of cascaded AND and OR logic gates. If the comparator answers the question 'X>C?' then its hardware implementation is designed according to the following rules:
- The number X has two types of binary figures: bits corresponding to '1' in the predefined constant and bits corresponding to '0' in the predefined constant.
- The bits of the number X corresponding to '1' are supplied to AND gates
- The bits corresponding to '0' are supplied to OR logic gates
- If the least significant bits of the predefined constant are '10' then bit X0 is supplied to the same AND gate as bit X1.
If the least significant bits of the constant are all '1' then the corresponding bits of the number X are not included in the hardware implementation. All other relations between X and C can be transformed in equivalent ones that use the operator '>' and the NOT logic operator as shown in the table below
Initial relationship to be tested | Equivalent relationship to be implemented |
X | NOT (X>C-1) |
X<= C | NOT (X>C) |
X >= C | X>C-1 |
If the most significant bits are Xn='1' and Yn='0' then number X is larger than Y.
If Xn='0' and Yn='1' then number X is smaller than Y.
If Xn=Yn then no decision can be taken about X and Y based only on these two bits.
If the most significant bits are equal then the result of the comparison is determined by the less significant bits Xn-1 and Yn-1. If these bits are equal as well, the process continues with the next pair of bits. If all bits are equal then the two numbers are equal
Multipliers
Multiplication is achieved by adding a list of shifted multiplicands according to the digits of the multiplier. An n-bit X n-bit multiplier can be realized in combinational circuitry by using an array of n-1 n-bit adders where each adder is shifted by one position.
For each adder one input is the shifted multiplicand multiplied by 0 or 1 (using AND gates) depending on the multiplier bit, the other input is n partial product bits.
Dividers
The binary divisions are performed in a very similar manner to the decimal divisions, as shown in the below figure examples. Thus, the second number is repeatedly subtracted from the figures of the first number after being multiplied either with '1' or with '0'. The multiplication bit ('1' or '0') is selected for each subtraction step in such a manner that the subtraction result is not negative. The division result is composed from all the successive multiplication bits while the remainder is the result of the last subtraction step.
This algorithm can be implemented by a series of subtracters composed of modified elementary cells. Each subtracter calculates the difference between two input numbers, but if the result is negative the operation is canceled and replaced with a subtraction by zero. Thus, each divider cell has the normal inputs of a subtracter unit as in the figure below but a supplementary input ('div_bit') is also present. This input is connected to the b_req_out signal generated by the most significant cell of the subtracter. If this signal is '1', the initial subtraction result is negative and it has to be replaced with a subtraction by zero. Inside each divider cell the div_bit signal controls an equivalent 2:1 multiplexer that selects between bit 'x' and the bit included in the subtraction result X-Y. The complete division can therefore by implemented by a matrix of divider cells connected on rows and columns as shown in figure below. Each row performs one multiplication-and-subtraction cycle where the multiplication bit is supplied by the NOT logic gate at the end of each row. Therefor the NOT logic gates generate the bits of the division result.
Bạn Có Đam Mê Với Vi Mạch hay Nhúng - Bạn Muốn Trau Dồi Thêm Kĩ Năng
Mong Muốn Có Thêm Cơ Hội Trong Công Việc
Và Trở Thành Một Người Có Giá Trị Hơn
Mong Muốn Có Thêm Cơ Hội Trong Công Việc
Và Trở Thành Một Người Có Giá Trị Hơn