Half Adder

10 Key excerpts on "Half Adder"

• 

  eBook - PDF

  Engineering Digital Design

  Revised Second Edition

  • Richard F. Tinder(Author)
  • 2000(Publication Date)
  • Academic Press

    (Publisher)

  There are ripple-carry adders, carry-save, carry select, and carry-look-ahead adders, 335 336 CHAPTER 8 / ARITHMETIC DEVICES AND ARITHMETIC LOGIC UNITS (ALUs) the last three being classified as “high-speed” adders. This list of four does not nearly cover the scope of adder design, nor does it establish the general character of these arithmetic devices. It does introduce the concept of computational speed as it relates to the addition process, however that is characterized. 8.2.1 The Half Adder The Half Adder (HA) is the simplest of all the arithmetic circuits and may be regarded as the smallest building block for modular design of arithmetic circuits. The HA consists of two inputs, A and B , and two outputs, sum S and carry C , as indicated by the logic circuit symbol in Fig. 8.1a. The operation format and truth table for the HA are given in Fig. 8.1b and 8.1c. Here, A plus B yields the result CS , where carry is the MSB and sum is the LSB. When mapped as in Fig. 8.1d, the results for sum and carry are read directly as S = A ⊕ B C = A · B . (8.1) The logic circuit for the HA is implemented by using Eqs. (8.1) and is given in Fig. 8.1e. Here, the choice is made to use the XOR gate in the implementation of the HA. However, use could have been made of the two-or three-level XOR realizations given in Fig. 3.28, or the transmission gate approach by using AOI or OAI gates as in Fig. 7.21 and 7.22. The XOR gate, given in Fig. 3.26, is the simplest CMOS design possible. FIGURE 8.1 Design of the Half Adder (HA). (a) Block diagram for the HA. (b) Operation format. (c) Truth table for A plus B , showing carry C , and sum S . (d) K-maps for sum and carry. (e) Logic circuit for the HA. 8.2 BINARY ADDERS 337 FIGURE 8.2 Design of the full adder (FA). (a) Block diagram for the FA. (b) Operation format for the FA. (c) Truth table for A plus B plus C in , showing carry-out C out , and sum S .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Electronics 2

  Sequential and Arithmetic Logic Circuits

  • Tertulien Ndjountche(Author)
  • 2016(Publication Date)
  • Wiley-ISTE

    (Publisher)

  4 Arithmetic and Logic Circuits

  4.1. Introduction

  Arithmetic circuits are essential in the implementation of microprocessors and circuits for digital signal processing.

  As the complexity of the direct approach (construct a truth table and then derive and simplify the output logic equations) increases with an increase in the size of data, the modular approach is often chosen to implement arithmetic circuits. A given digital circuit is thus implemented by assembling modules that are designed for numbers with small word lengths.

  Despite the increasing number of arithmetic operations that are becoming routine, most microprocessors only contain circuits for basic operations, such as an adder (or summer), comparator, multiplier and divider. In addition to arithmetic circuits, there is also a need for circuits that can perform bitwise logic and shift operations. One of the main components of a microprocessor, therefore, is the arithmetic and logic unit (ALU), which encases all the circuits required for carrying out operations on digital data.

  4.2. Adder

  Adders are used to perform a large number of digital operations. In spite of the apparent simplicity of an addition operation, there are several approaches to designing adders.

  4.2.1. Half Adder

  A Half Adder (HA) is a circuit that generates the sum, S, and the carry, C, resulting from the addition of two 1-bit numbers, A and B.

  An example of a simple addition, A + B, is given in Figure 4.1 . The truth table shown in Table 4.1 is constructed by considering bits C and S to be the MSB and LSB in the 2-bit representation of the addition result. The logic equations for the two outputs are given by:

  [4.1]

  [4.2]

  Figure 4.1. Example of a simple addition. For a color version of the figure, see www.iste.co.uk/ndjountche/electronics2.zip

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Algorithms and Data Structures in C++

  • Alan Parker(Author)
  • 2018(Publication Date)
  • Routledge

    (Publisher)

  Code List 4.1

  C++ Output

  a=−6 b=6 sum = 0 overflow= 0 carry= 1 a= 19 b= −33 sum = −14 overflow= 0 carry= 0 a= −60 b= −90 sum = 106 overflow= 1 carry= 1 a= −1 b= −2 sum = −3 overflow= 0 carry= 1 a= −128 b= −128 sum = 0 overflow= 1 carry= 1

  The programs do not check for overflow but simply simulate the additon as performed by hardware. 4.1.1    Full and Half Adder

  In order to develop some fast algorithms for multiplication and addition it is necessary to analyze the process of addition and multiplication at the bit level. Full and Half Adders are bit-level building blocks that are used to perform addition.

  A Half Adder is a module which inputs two signals, a

  i

  and b

  i

  , and generates a sum, s

  i

  , and a carry-out c

  i

  . A Half Adder does not support a carry-in. The outputs are as in Table 4.1 .

  TABLE 4.1 Half Adder Truth Table

  A full adder has a carry-in input, c

  i

  A full adder is shown in Table 4.2 .

  TABLE 4.2 Full Adder Truth Table

  The full adder and Half Adder modules are shown in Figure 4.1 . The boolean equation for the output of the full adder is

  s i = a ¯ i b ¯ i c i − 1 + a ¯ i b i c i − 1 ¯ + a i b ¯ i c i − 1 ¯ + a i b i c i − 1

  (4.1)

  c i = a ¯ i b i c i − 1 + a i b i c i − 1 ¯ + a i b i c i − 1

  (4.2)

  The boolean equation for the output of the Half Adder is

  s i = a i b ¯ i + a ¯ i b i = a i ⊕ b i

  (4.3)

  where ⊕ denotes the exclusive-or operation.

  c i = a i b i

  (4.4)

  The output delay of each module can be expressed in terms of the gate delay, Δ, of the technology used to implement the boolean expression. The sum, s

  i

  , for the full adder can be implemented as in Eq. 4.1 using four 3-input NAND gates in parallel followed by a 4-input NAND gate. The gate delay of a k-input NAND gate is Δ so the sum is calculated in 2Δ. This is illustrated in Figure 4.2 . For the half-adder the sum is calculated within 1Δ and the carry is generated within 1Δ. The Output Delay for the Half Adder is shown in Figure 4.2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Verilog HDL Design Examples

  • Joseph Cavanagh(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  2 .

  Table 4.1 Truth Table for a Full Adder for Binary Addition

  The radix complement of binary numbers (2s complement ) is obtained by complementing each bit of the corresponding positive binary number and adding 1 to the low–order bit position. For example, let A = 0001 11002 = +2810 and A’ = 1110 0011 = 1110 0100 = –28. To obtain the value of a negative number count the weight of the 0s and add 1. Examples of addition operations are shown in Table 4.2 , which add two 8-bit positive and negative operands.

  Table 4.2 Examples of Addition for Two Eight-Bit Signed Operands

  4.12.1 Full Adder

  A full adder can be designed from two Half Adders. A Half Adder adds two operand bits a and b, and produces two outputs sum and carry-out . The truth table for a Half Adder is shown in Table 4.3 and the equations for a Half Adder are shown in Equation 4.2 . From Table 4.1 , the equations for the sum and carry-out of a full adder are shown in Equation 4.3 . The logic diagram for a full adder is shown in Figure 4.1 .

  (4.2)

  s u m =

  a ′

  b + a b = a ⊕ b c o u t = a b

  (4.3)

  c o u n t =

  a ′

  b c i n + a

  b ′

  c i n + a b c i

  n ′

  + a b c i n

  = a b + ( a ⊕ b ) c i n

  Table 4.3 Truth Table for a Half Adder

  Augend (a )	Addend (b )	Carry-out (cout )	Sum
  0	0	0	0
  0	1	0	1
  1	0	0	1
  1	1	1	0

  Figure 4.1 Logic diagram for a full adder using two Half Adders.

  The structural design module is shown in Figure 4.2 using built-in primitives. The test bench module and the outputs are shown in Figures 4.3 and 4.4

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Foundation of Digital Electronics and Logic Design

  • Subir Kumar Sarkar, Asish Kumar De, Souvik Sarkar(Authors)
  • 2014(Publication Date)
  • Jenny Stanford Publishing

    (Publisher)

  That is 0 1 1 0 1 1 0 (Since there is a carry, 3 bit addition have to be done which is not possible with Half Adder. 1.25 Full Adder and Full Subtractor It adds three binary bits at a time. The two binary bits are called augend bit and addend bit and the other bit is called the carry bit from the previous stage (Fig. 1.75). here A = augend bit and B = addend bit Figure 1.74 Logic circuit realization of the functions f 1 = ( M, A, B ) and f 2 = ( M, A, B ) using NAND gate. Figure 1.75 Block diagram of a full adder. 70 Combinational Circuits C i –1 = the carry bit generated from the previous stage that is just previous to present stage. So full adder circuit has multiple output and this is a multiple output function. The corresponding function of the full adder can be verified using the data given in Table 1.21 Table 1.21 Truth table of a full adder Decimal Three inputs Two outputs A B C i –1 S C i 0 0 0 0 0 0 1 0 0 1 1 0 2 0 1 0 1 0 3 0 1 1 0 1 4 1 0 0 1 0 5 1 0 1 0 1 6 1 1 0 0 1 7 1 1 1 1 1 First add B with C i –1 and then add it with A to get the final sum and carry indicated by the logical expressions S and C , respectively. S = ∑ m (1, 2, 4, 7) C = ∑ m (3, 5, 6, 7) The sum satisfies XOR logic (odd number of 1s as I/P) S = 1 and even number of 1s S = 0. S = A ⊕ B ⊕ C i –1. Now verify the result with the K map. But none of the cells can be included in group and hence, S = 001 + 010 + 100 + 111 = A – B – C i –1 + A – BC – i –1 + AB – C – i –1 + ABC i –1 (1.30) If we expand Eq. (1), we get Eq. (2). Expanding Eq. (1), we have: S = A ⊕ B ⊕ C i –1 Let u = A ⊕ B Full Adder and Full Subtractor 71 S = u ⊕ C i –1 = u – C i –1 + — uC i –1 (1.31) and u = ( AB ― + ― AB ) (1.32) u A B A B A A A B A B A B ( ) ( ) A + . A + By Demorgan’s theorem we get = + + + AA AB AB BB So, u ― = ― AB – + AB (1.33) Using Eqs.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Digital Computer Structure and Design

  • R. Townsend(Author)
  • 2014(Publication Date)
  • Butterworth-Heinemann

    (Publisher)

  A somewhat different approach to the problem of fast binary addition has been adopted by the Manchester University Computer Group, and others. With this point of view the adder and the accumulator register are considered as a single combined device in which the objective is to place the result in the register in the shortest time. In the adder for the Atlas computer 11 a special purpose circuit is designed which derives its speed from the fast propagation of the carry signal from the collector to the emitter of a saturated symmetrical transistor. However this technique is no longer suitable for modern integrated circuit technology. The need for high speed binary adders becomes most important on very large and fast computers having word lengths of 50 to 100 bits, in which the carry propagation time with a conventional ripple carry 106 Addition and Subtraction adder has a serious effect on the performance. With the availability of small lookahead adders complete on integrated circuits, it is now worth while to incorporate these in minicomputers. In any case, the speed of integrated circuit logic gates is continually rising, which makes for a very high performance with conventional methods. The lookahead adder seems to be the preferred method for improving speed on modern large machines. Binary Coded Decimal Adders Most modern processors operate with pure binary numbers, but decimal arithmetic units are still of interest in electronic calculators and special purpose devices, such as point of sale cash registers. The decimal numbers are usually represented as a binary code, the commonest being the straightforward BCD or 1248 weighted code. The 'excess 3' code has been widely used in the past, and is still popular in some applications. The rules of binary coded decimal arithmetic with the BCD and 'excess 3' codes have been described in Chapter 4.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Logic Design

  • Wai-Kai Chen(Author)
  • 2003(Publication Date)
  • CRC Press

    (Publisher)

  16.3 Serial Adder A serial adder operates similarly to manual addition. The serial adder, at each step, calculates the sum and carry at one bit position. It starts at the least significant bit position (i.e., i = 0) and each successive next step it sequentially moves to the next more significant bit position where it calculates the sum and carry. At the n -th step, it calculates the sum and carry at the most significant bit position (i.e., i = n – 1). In other words, the serial adder serially adds augend X and addend Y by adding x i , y i , and c i at the i -th bit position from i = 0 to n – 1. From the truth table shown in Table 16.1, we have sum bit s i = x i ≈ y i ≈ c i and carry to the next higher bit position c i +1 = x i · y i ⁄ c i ·( x i ⁄ y i ) (also c i +1 = x i · y i ⁄ c i · ( x i ≈ y i )), where “·” is AND, “ ⁄ ” is OR, and “ ≈ ” is XOR, and henceforth, “·” will be omitted. This serial addition can be realized by the logic network, called a serial adder , or bit-serial adder , shown in Fig. 16.2, where its operation is synchronized by a clock. The addition of each i -th bit is done at a rate of one bit per cycle of clock, producing sum bits, s i ’s, at the same rate, from the least significant bit to the most significant one. In each cycle, s i and c i + 1 , are calculated from x i , y i , and the carry from the previous cycle, c i . The core logic network, shown in the rectangle in Fig. 16.2, for this one-bit addition for the i -th bit position is called a full adder (abbreviated as FA ). We obtain a logic network for an FA shown in Fig. 16.3 using AND, OR, and XOR gates. A D-type flip-flop may be used as a delay element which stores the carry for FIGURE 16.1 Examples of addition of numbers in two’s complement representation. 16-4 Logic Design a cycle. Full adders realized in ECL (emitter-coupled logic) are described in Chapter 13. FAs with a minimum number of logic gates are known for different types of logic gates.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Arithmetic and Logic in Computer Systems

  • Mi Lu(Author)
  • 2005(Publication Date)
  • Wiley-Interscience

    (Publisher)

  The same hardware unit designed for addition can be applied to perform the subtraction. Consider moving the pointer of a clock. Clockwise move is analogous to addition and counter-clockwise move is analogous to subtraction. For example, suppose a pointer is pointing to 12 o’clock at the beginning. Moving it counter-clockwise for 3 hours will result in 9, that is, 12 - 3 = 9. On the other hand, moving it clockwise for 9 hours will make it stop at the same place because (12+9) mod 12 =9. (See Figure 2.8.) Here 3 and 9 are the complement numbers of each other, the 12’s complement numbers. So, 12 - 3 can be completed by 12 + (-3), while (-3) is represented in the complement form, that is, 9. The same idea applies in computer systems except that the 1’s or 2’s complement system is adopted rather than the 12’s complement system. Given a number B, the negation function and the hardware designed for it can find (-B) as described in Section 2.2. By combining an adder and a complementor, a unit capable of both addition and subtraction can be designed. In Figure 2.9 a single-bit full-adder has its output which is actually the same logic shown in Equation (2.2). Where bi used to be at the input of the full-adder, bi @ M is utilized now. Here M is the control signal. When M = 0, bi is input to the adder unchanged and ai + bi is performed. When M = 1, input to the adder is 6i which is the 1’s complement number of bi, and ai + (- bi) = ai - bi is performed. Hence, Equations (2.1) and (2.7) become ~i = ai @ (bi @ M ) @ ci 42 ADDITION AND SUBTRACTION I Si Fig. 2.9: One-Bit AdderKubtractor and respectively. To add two n-bit numbers or subtract one from the other, n such units as in Figure 2.9 can be connected in cascade to form an n-bit adderhbtractor. Note that M is the same signal to all the units. Depending on whether M equals to 0 or 1, the negation function is disabled or enabled and an addition or subtraction is to be performed.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Logic Techniques

  • John Stonham(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  If bit b i, of the multiplier is 0 2 then the multiplication A × b i must be zero for all possible values of A. If b i is 1 2 then the multiplication A × b i is equal to A. Therefore no extra logical operation or calculation is required in this step of the algorithm. Binary multiplication is therefore only a series of shift-and-add operations and like the subtractor operation, this too can be implemented based on an adder circuit, enhanced with three data stores and a control unit. A block diagram of a binary multiplier is shown in Fig. 7.7. Fig. 7.7 A binary shift-and-add multiplier. For example, parallel or look-ahead-carry adder. The binary adder is the main processor in a multiplier. It can be a ripple-through-carry type or one of the faster adders previously described. The adder resolution needs to be 2 n bits as the data in register A (the multiplicand) and register B (the multiplier) are n bits. Owing to the increased complexity of the system, a controller unit is necessary to schedule the flow of information. The controller receives the least significant bit b 0 from register B via its input K. If b 0 is 0, register A is shifted 1 bit left initiated by control signal C 2 and register B is shifted 1 bit right through C 3. If, however, b 0 is 1 then the contents of register A and the accumulator are input to the adder via controls C 1 and C 4 and the resulting addition stored in the accumulator before the shift controls are applied to registers A and B

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Digital Arithmetic

  • Miloš D. Ercegovac, Tomás Lang, Miloš D. Ercegovac(Authors)
  • 2003(Publication Date)
  • Morgan Kaufmann

    (Publisher)

  On the other hand, with VLSI technology, in which a whole adder fits in a chip, the constraints are different, and simplicity of cells and regularity of connections become the most critical. Because of this, groups of size two are quite popular. Prefix Adder The prefix adder is a structure that is based on considering the carry computation as a prefix computation. In general, a prefix combinational network of n inputs xo, x2, ..., Xn-1 uses the associative (arbitrary) operator o to produce the vector of outputs described by Zi m Xi 0 Xi_ 1 0 ... 0 X 1 0 X 0 2.55 As indicated in Section 2.1, for the carry computation we have zi = (g{i,0), a(i,0)), xi = (gi, ai) 2.56 and the operator (implemented by a cell) has as input two pairs of bits (gL, g R) and (a/., a R) and as output one pair (gout, aout). It is described by the switching expressions gout = g I. + a Lg R 2.57 El out ~ a L a R where as before, g anda -- k' correspond to generate and to alive signals, respec- tively. With this cell, a variety of networks are used to produce the carries. They are all based on the fact that the carry c i corresponds to the generate signal spanning the bit positions (-1) to i - 1. We call this generate signal g(i-1,-1) so that Ci = g(i--1,-1) 2.58 where (g-I, a_l) - (co, co). 80 C H APT E R 2 Two-Operand Addition le~2 riiht2 (e~l iightl gL aL gg aR . . . . . . . . . . . . . i ' ' ' I , a(leftvlefq ) g (rig htvri ght l) i a(right2,righq) ~ : 2 , ', f ' g(left2,righq ) 2 a(leftvrighq ) gout a out (a) (b) FIGURE 2.t7 Composition of spans in computing (g, a) signals. A prefix adder is then an interconnection of the above-mentioned cells to produce g(i-1,-1) for all i. These carries are then used to obtain the sum bits as S i = Pi ~]~ Ci 2.59 To obtain the carries the cells are connected in a recursive manner to produce the g signals that span an increasing number of bits.

  Sign up to read

  Learn more about book