Logic Design And circuit diagram of Half and Full Adder
Table of Contents
Combinational Logic Design And circuit diagram of Half adder and Full Adder
COMBINATIONAL LOGIC DESIGN
Introduction
The term ‘combinational’ comes to us from mathematics. In mathematics a combination is an unordered set, . Which is a formal way to say that nobody cares which order the items came in. Most games work this way, if you rolled dice one at a time . And get a 2 followed by a 3 it is the same as if you had rolled a 3 followed by a 2. With combinational logic, the circuit produces the same output regardless of the order the inputs are changed.
There are circuits which depend on the when the inputs change, these circuits are called sequential logic. Even though you will not find the term ‖sequential logic‖ in the chapter titles, the next several chapters will discuss sequential logic. Practical circuits will have a mix of combinational and sequential logic, with sequential logic making sure everything happens in order and combinational logic performing functions like arithmetic, logic, or conversion.
Design Using Gates
A combinational circuit is one where the output at any time depends only on the present combination of inputs at that point of time with total disregard to the past state of the inputs. The logic gate is the most basic building block of combinational logic. The logical function performed by a combinational circuit is fully defined by a set of Boolean expressions. The other category of logic circuits, called sequential logic circuits, comprises both logic gates and memory elements such as flip-flops. Owing to the presence of memory elements, . The output in a sequential circuit depends upon not only the present but also the past state of inputs.
The Fig shows the block schematic representation of a generalized combinational circuit having n input variables and m output variables or simply outputs. Since the number of input variables is
Generalized Combinational Circuit
n, there are 2n possible combinations of bits at the input. Each output can be expressed in terms of input variables by a Boolean expression, . With the result that the generalized system of above fig can be expressed by m Boolean expressions. As an illustration, Boolean expressions describing the function of a four-input OR/NOR gate are given as
BCD Arithmetic Circuits
Addition and subtraction are the two most commonly used arithmetic operations, as the other two, namely multiplication and division, are respectively the processes of repeated addition and repeated subtraction, as was outlined in Chapter 2 dealing with binary arithmetic. We will begin with the basic building blocks that form the basis of all hardware used to perform the aforesaid arithmetic operations on binary numbers. These include half-adder, full adder, half-subtractor, full subtractor and controlled inverter.
circuit diagram of Half and Full Adder
Binary Adder
Half Adder
A half adder is an arithmetic circuit block that can be used to add two bits. Such a circuit thus has two inputs that represent the two bits to be added and two outputs, with one producing the SUM output and the other producing the CARRY. Figure 3.2 shows the truth table of a half-adder, showing all possible input combinations and the corresponding outputs.
The Boolean expressions for the SUM and CARRY outputs are given by the equations below
Half adder truth table
An examination of the two expressions tells that there is no scope for further simplification. While the first one representing the SUM output is that of an EX-OR gate . The second one representing the CARRY output is that of an AND gate. However, these two expressions can certainly be represented in different forms using various laws and theorems of Boolean algebra to illustrate the flexibility that the designer has in hardware-implementing as simple a combinational function as that of a half adder. (half adder circuit, half adder circuit diagram)
Logic Implementation of Half Adder
Although the simplest way to hardware-implement a half-adder would be to use a two-input EX-OR gate for the SUM output and a two-input AND gate for the CARRY output, as shown in Fig. 3.3, it could also be implemented by using an appropriate arrangement of either NAND or NOR gates.
Full Adder
A full adder circuit is an arithmetic circuit block that can be used to add three bits to produce a SUM and a CARRY output. Such a building block becomes a necessity when it comes to adding binary numbers with a large number of bits. The full adder circuit overcomes the limitation of the half-adder, which can be used to add two bits only. Let us recall the procedure for adding larger binary numbers. We begin with the addition of LSBs of the two numbers.
We record the sum under the LSB column and take the carry, if any, forward to the next higher column bits. As a result, when we add the next adjacent higher column bits, we would be required to add three bits if there were a carry from the previous addition. We have a similar situation for the other higher column bits. Also until we reach the MSB. A full adder is therefore essential for the hardware implementation of an adder circuit capable of adding larger binary numbers. A half-adder can be used for addition of LSBs only.
full adder truth table
Figure shows the truth table of a full adder circuit showing all possible input combinations and corresponding outputs. In order to arrive at the logic circuit for hardware implementation of a full adder, we will firstly write the Boolean expressions for the two output variables, that is, the SUM and CARRY outputs, in terms of input variables. These expressions are then simplified by using any of the simplification techniques described in the previous chapter. The Boolean expressions for the two output variables are given in Equation below for the SUM output (S) and in above Equation for the CARRY output (Cout):
The next step is to simplify the two expressions. We will do so with the help of the Karnaugh mapping technique. Karnaugh maps for the two expressions are given in Fig. 3.5(a) for the SUM output and Fig. 3.5(b) for the CARRY output. As is clear from the two maps, the expression for the SUM (S) output cannot be simplified any further, whereas the simplified Boolean expression for Cout is given by the equation
Figure shows the logic circuit diagram of the full adder. A full adder can also be seen to comprise two half-adders and an OR gate. The expressions for SUM and CARRY outputs can be rewritten as follows:
Similarly, the expression for CARRY output can be rewritten as follows:
Karnaugh Map for the sum and carry out of a full adder
full adder circuit diagram (full adder circuit)
Boolean expression above can be implemented with a two-input EX-OR gate provided that one of the inputs is Cin and the other input is the output of another two-input EX-OR gate with A and B as its inputs. Similarly, Boolean expression above can be implemented by ORing two minterms. One of them is the AND output of A and B. The other is also the output of an AND gate whose inputs are Cin and the output of an EX-OR operation on A and B.
The whole idea of writing the Boolean expressions in this modified form was to demonstrate the use of a half-adder circuit in building a full adder. Figure 3.7(a) shows logic implementation of Equations above. Figure 3.7(b) is nothing but Fig. 3.7(a) redrawn with the portion of the circuit representing a half-adder replaced with a block. The full adder of the type described above forms the basic building block of binary adders. However, a single full adder circuit can be used to add one-bit binary numbers only.
A cascade arrangement of these adders can be used to construct adders capable of adding binary numbers with a larger number of bits. For example, a four-bit binary adder would require four full adders of the type shown in Fig. 3.7 to be connected in cascade. Figure 3.8 shows such an arrangement. (A3A2A1A0) and (B3B2B1B0) are the two binary numbers to be added, with A0 and B0 representing LSBs and A3 and B3 representing MSBs of the two numbers.
Logic Implementation of a half adder and full adder
Four Bit Binary Adder
Half Subtractor
We will study the use of adder circuits for subtraction operations in the following pages. Before we do that, we will briefly look at the counterparts of half adder and full adder circuits in the half subtractor and full subtractor for direct implementation of subtraction operations using logic gates.
A half subtractor is a combinational circuit that can be used to subtract one binary digit from another to produce a DIFFERENCE output and a BORROW output. The BORROW output here specifies whether a ‘1‘ has been borrowed to perform the subtraction. The truth table of a half-subtractor, as shown in Fig. 3.9, explains this further. The Boolean expressions for the two outputs are given by the equations ( half subtractor truth table )
Half subtractor circuit
It is obvious that there is no further scope for any simplification of the Boolean expressions given by above equations. While the expression for the DIFFERENCE (D) output is that of an EX-OR gate, the expression for the BORROW output (Bo) is that of an AND gate with input A complemented before it is fed to the gate. Figure 3.10 shows the logic implementation of a half-subtractor. Comparing a half-subtractor with a half-adder, we find that the expressions for the SUM and DIFFERENCE outputs are just the same. The expression for BORROW in the case of the half-subtractor is also similar to what we have for CARRY in the case of the half-adder. If the input A, that is, the minuend, is complemented, an AND gate can be used to implement the BORROW output. Note the similarities between the logic diagrams of Fig. 3.3 (half-adder) and Fig. 3.10 (half-subtractor).
Full Subtractor
A full subtractor performs subtraction operation on two bits, a minuend and a subtrahend, and also takes into consideration whether a ‘1‘ has already been borrowed by the previous adjacent lower minuend bit or not. As a result, there are three bits to be handled at the input of a full subtractor, namely the two bits to be subtracted and a borrow bit designated as Bin . There are two outputs, namely the DIFFERENCE output D and the BORROW output Bo.
The BORROW output bit tells whether the minuend bit needs to borrow a ‘1‘ from the next possible higher minuend bit. Figure 3.11 shows the full subtractor truth table
The Boolean expressions for the two output variables are given by the equations (full subtractor circuit)
The Karnaugh maps for the two expressions are given in Fig. 3.12(a) for DIFFERENCE output D and in Fig. 3.12(b) for BORROW output Bo. As is clear from the two Karnaugh maps, no simplification is possible for the difference output D. The simplified expression for Bo is given by the equation
If we compare these expressions with those derived earlier in the case of a full adder, we find that the expression for DIFFERENCE output D is the same as that for the SUM output. Also, the expression for BORROW output Bo is similar to the expression for CARRY-OUT Co. In the case of a half-subtractor, the A input is complemented. By a similar analysis it can be shown that a full subtractor can be implemented with half-subtractors in the same way as a full adder was constructed using half-adders. Relevant logic diagrams are shown in Figs 3.7(a) and (b) corresponding to Figs 3.7(a) and (b) respectively for a full adder. Again, more than one full subtractor can be connected in cascade to perform subtraction on two larger binary numbers. As an illustration, Fig. 3.13 shows a four-bit subtractor.
Four Bit Subtractor
Multipliers
Multiplication of binary numbers is usually implemented in microprocessors and microcomputers by using repeated addition and shift operations. Since the binary adders are designed to add only two binary numbers at a time, instead of adding all the partial products at the end, they are added two at a time and their sum is accumulated in a register called the accumulator register. Also, when the multiplier bit is ‘0‘, that very partial product is ignored, as an all ‘0‘ line does not affect the final result. The basic hardware arrangement of such a binary multiplier would comprise shift registers for the multiplicand and multiplier bits, an accumulator register for storing partial products, a binary parallel adder and a clock pulse generator to time various operations.
Binary multipliers are also available in IC form. Some of the popular type numbers in the TTL family include 74261 which is a 2 × 4 bit multiplier (a four-bit multiplicand designated as B0,B1,B2,B3 and B4, and a two-bit multiplier designated as M0, M1 and M2.
The MSBs B4 and M2 are used to represent signs. 74284 and 74285 are 4 × 4 bit multipliers. They can be used together to perform high-speed multiplication of two four-bit numbers. Figure 3.14 shows the arrangement. The result of multiplication is often required to be stored in a register. The size of this register (accumulator) depends upon the number of bits in the result, which at the most can be equal to the sum of the number of bits in the multiplier and multiplicand. Some multipliers ICs have an in-built register.
Many microprocessors do not have in their ALU the hardware that can perform multiplication or other complex arithmetic operations such as division, determining the square root, trigonometric functions, etc. These operations in these microprocessors are executed through software. For example, a multiplication operation may be accomplished by using a software program that does multiplication through repeated execution of addition and shift instructions. Other complex operations mentioned above can also be executed with similar programs. Although the use of software reduces the hardware needed in the microprocessor, the computation time in general is higher in the case of software-executed operations when compared with the use of hardware to perform those operations.
Design Using MSI devices
When designing logic circuits, the “discrete logic gates”; i.e., individual AND, OR, NOT etc. gates, are often neither the simplest nor the most economical devices we could use. There are many standard MSI(medium scale integrated) and LSI(Large scle integrated) circuits, or functions available, which can do many of the things commonly required in logic circuits. Often these MSI and LSI circuits do not fit our requirements exactly, and it is often necessary to use discrete logic to adapt these circuits for our application.
However, the number and type o these LSI and VLSI (very large scale integrated) circuits is steadily increasing, and it is difficult to always be aware of the best possible circuits available for a given problem. Also, systematic design methods are difficult to devise when the types of logic device available keeps increasing. In general the “best” design procedure is to attempt to find a LSI device which can perform the required function, or which can be modified using other devices to perform the required function. If nothing is available, then the function should be implemented with several MSI devices. Only as a last option should the entire function be implemented with discrete logic gates. In fact, with present technology, it is becoming increasingly cost-effective to implement a design as one or more dedicated VLSI devices.
When designing all but the simplest logic devices, a “top-down” approch should be adopted. The device should be specified in block form, and attempt to implement each block with a small number of LSI or MSI functions. Each block which cannot be implemented directly can be then broken into smaller blocks, and process repeated, until each block is fully implemented.
Of course, a good knowledge of what LSI and MSI functions are available in the appropriate technology makes this process simpler.
MULTIPLEXERS
Many tasks in communications, control, and computer systems can be performed by combinational logic circuits. When a circuit has been designed to perform some task in one application, it often finds use in a different application as well. In this way, it acquires different names from its various uses. In this and the following sections, we will describe a number of such circuits and their uses. We will discuss their principles of operation, specifying their MSI or LSI implementations. One common task is illustrated in Figure 12. Data generated in one location is to be used in another location; A method is needed to transmit it from one location to another through some communications channel.
The data is available, in parallel, on many different lines but must be transmitted over a single communications link. A mechanism is needed to select which of the many data lines to activate sequentially at any one time so that the data this line carries can be transmitted at that time. This process is called multiplexing. An example is the multiplexing of conversations on the telephone system. A number of telephone conversations are alternately switched onto the telephone line many times per second. Because of the nature of the human auditory system, listeners cannot detect that what they are hearing is chopped up and that other people‘s conversations are interspersed with their own in the transmission process.
Needed at the other end of the communications link is a device that will undo the multiplexing: a demultiplexer. Such a device must accept the incoming serial data and direct it in parallel to one of many output lines. The interspersed snatches of telephone conversations, for example, must be sent to the correct listeners.
A digital multiplexer is a circuit with 2n data input lines and one output line. It must also have a way of determining the specific data input line to be selected at any one time. This is done with n other input lines, called the select or selector inputs . Whose function is to select one of the 2n data inputs for connection to the output. A circuit for n = 3 is shown in Figure 13. The n selector lines have 2n = 8 combinations of values that constitute binary select numbers
Multiplexers as General Purpose Logic Circuits
It is clear from Figures 13 and 14 . That the structure of a multiplexer is that of a two-level AND-OR logic circuit. With each AND gate having n + 1 inputs, where n is the number of select inputs. It appears that the multiplexer would constitute a canonic sum-of-products implementation of a switching function . If all the data lines together represent just one switching variable (or its complement) . And each of the select inputs represents a switching variable.
Let‘s work backward from a specified function of m switching variables for which we have written a canonic sum-of-products expression. The size of multiplexer needed (number of select inputs) is not evident. Suppose we choose a multiplexer that has m − 1 select inputs . Leaving only one other variable to accommodate all the data inputs. We write an output function of these select inputs and the 2m–1 data inputs Di. Now we plan to assign m −1 of these variables to the select inputs; . But how to make the assignment?4 There are really no restrictions, so it can be done arbitrarily. The next step is to write the multiplexer output . After replacing the select inputs with m − 1 of the variables of the given function. By comparing the two expressions term by term, the Di inputs can be determined in terms of the remaining variable.
Demultiplexers
The demultiplexer shown there is a single-input, multiple-output circuit. However, in addition to the data input, . There must be other inputs to control the transmission of the data to the appropriate data output line at any given time. Such a demultiplexer circuit having eight output lines is shown in Figure 16a. It is instructive to compare this demultiplexer circuit with the multiplexer circuit in Figure 13. For the same number of control (select) inputs, there are the same number of AND gates. But now each AND gate output is a circuit output. Rather than each gate having its own separate data input . The single data line now forms one of the inputs to each AND gate . The other AND inputs being control inputs.