Feleke Combinational Circuits 2018 PDF

Preview

Summary

Dr. Feleke...

Description

Unity University College of Engineering , Technology and Computational Sciences

Department of Computer Science

Course Title: Computer Organization and Architecture

Topic: Combinational circuits Learning Objectives After completing this topic, you will be able to: 

Describe Combinational Logic Circuit



Identify how interconnected gates can be used to implement such functions as :  Performing binary addition ( by using half adder, full adder),  Routing of signals (by using MUX or DEMUX),  Decoding, and ROM making.

 Combining basic gates into circuits 

Combinational Logic Circuit deals with the method of “combining” basic Logic Gates into circuits that carry out a desired application.



Logic gate circuits are divided into two categories based on whether they are with feedback sequential logic circuit or without feedback combinational logic circuit.



Combinational logic (sometimes also referred to as time-independent logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only.

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 1 of 29

Unity University

Block diagram of combinational 

Sequential logic is a type of logic circuit whose output depends not only on the present value of its input signals but on the sequence of past inputs.

Block diagram of sequential

 Difference between Combinational and Sequential logic circuits. Combinational Logic Circuits

Sequential Logic Circuits

Output is a function of the present inputs (Time Output is a function of clock, present inputs Independent Logic). and the previous states of the system. Do not have the ability to store data (state).

Have memory to store the present states that is sent as control input (enable) for the next operation.

It does not require any feedback. It simply outputs the input according to the logic designed.

It involves feedback from output to input that is stored in the memory for the next operation.

Used mainly for Arithmetic and Boolean operations.

Used for storing data (and hence used in RAM).

Logic gates are the elementary building blocks.

Flip flops (binary storage device) are the elementary building unit.

Independent of clock and hence does not require Clocked (Triggered for operation with triggering to operate. electronic pulses). Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 2 of 29

Unity University Example: Counter [Previous O/P +1=Current O/P; Dependency on present input as well as previous state].

Example: Adder [1+0=1; Dependency only on present inputs i.e., 1 and 0].

 Examples (or lists) of Combinational Logic Circuits (see figure below):

a) Binary Adding Circuits (Half adder, full adder) Half adder •

At the digital logic level, Half adder is a combinational logic circuit, which is used to add two bits and generate output as sum ( S ) and carry (addition is performed in binary.) •

Circuit diagram representing a half adder

Two Boolean expressions: sum = A Å B carry = AB Problem: Cannot use it to build larger inputs

•

Sou

•

The result of adding two binary digits could produce a carry value

•

Recall that 1 + 1 = 10 in base two

•

A circuit that computes the sum of two bits and produces the correct carry bit is called a half adder

The truth table

Unity University

Note(Half adder) 

From the truth table (for a half-adder) a closer look reveals that Sum is actually an XOR. The Carry output is equivalent to that of an AND gate. We can combine an XOR gate and an AND gate, resulting in the logic diagram for a half-adder shown above.



The half-adder is a very simple circuit and not really very useful because it can only add two bits together.

Full adder: 

Full adder is a combinational logic circuit used to add three or more bits. The reason for the name full adder is that it can add the carry bit as third bit (Cin ) along with other two inputs A and B.



The figure below illustrates the truth table and corresponding logic diagram for a full-adder. Note that this full-adder is composed of two half-adders and an OR gate.

Legend Sum = S Sourc

Carry out = Cy

Dr.  Eng.)

Page 4 of 29

Unity University

b) Multiplexers 

Multiplexer means “path selector”; it has many inputs, a single output and select input signals.



A multiplexer has n number of select inputs, 2n, inputs, and only one output.



The multiplexer selects which input signal is used as an output signal based on the value represented by a few more input signals, called select signals or select control lines

Figure 4.11 A block diagram of a multiplexer with three select control lines 

The above general block diagram represents a 8-to-1 multiplexer. There are eight input lines labeled D0, D1, D2, . . . , D7.



One of these lines is selected to provide the output signal F. To select one of the eight possible inputs, a 3-bit selection code is needed, and this is implemented as three select lines labeled S0, S1 and S2.



A The truth table

Source: F

y the truth table in Table below.

Page 5 of 29

Unity University

Example 2 

A general block diagram representation is shown in Figure 11.12. This represents a 4-to-1 multiplexer.



There are four input lines, labeled D0, D1, D2, and D3. One of these lines is selected to provide the output signal F.



To select one of the four possible inputs, a 2-bit selection code is needed, and this is implemented as two select lines labeled S1 and S2.



An example 4-to-1 multiplexer is defined by the truth table in Table 11.7. This is a simplified form of a truth table.



Instead of showing all possible combinations of input variables, it shows the output as data from line D0, D1, D2, or D3.

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 6 of 29

Unity University



Figure 11.13 shows an implementation using AND, OR, and NOT gates. S1 and S2 are connected to the AND gates in such a way that, for any combination of S1 and S2, three of the AND gates will output 0.



The fourth AND gate will output the value of the selected line, which is either 0 or 1. Thus, three of the inputs to the OR gate are always 0, and the output of the OR gate will equal the value of the selected input gate.



Using this regular organization, it is easy to construct multiplexers of size 8-to-1, 16-to-1, and so on.



Multiplexers are used in digital circuits to control signal and data routing. An example is the loading of the program counter (PC). The value to be loaded into the program counter may come from one of several different sources:

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 7 of 29

Unity University

c) Encoder 

An encoder is a combinational logic circuit which converts non-digital data to digital data.



An encoder has 2n input lines and n output lines. The output lines generate a binary code corresponding to the input value.



For example a single bit 4-to-2 encoder takes in 4 bits and outputs 2 bits. An encoder combinational circuit that performs the inverse operation of a decoder. The truth table of an encoder is shown in Table 13-16

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 8 of 29

Unity University

 8-to-3 Encoder:

 Circuit Diagram of an 8-to-3 Encoder:

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 9 of 29

Unity University

d) Decoders 

Decoder is combinational logic circuit multiple-input, multiple-output logic circuit which converts digital data to non-digital data.



n

In general, a decoder has n inputs and 2 outputs. Figure 11.15 shows a decoder with three inputs and eight outputs.



A 3-to-8 decoder is implemented using three inverters and eight 3-input AND gates, as shown in Figure 11.15. The three inputs A, B, C are decoded into eight outputs. Each one of the AND gates produce one min-terms of the input variables.



Decoders find many uses in digital computers. One example is address decoding.

 Circuit Diagram of A 3-to-8 decoder:

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 10 of 29

Unity University

 Circuit Diagram of A 3-to-8 decoder:

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 11 of 29

Unity University  Truth table of A 3-to-8 decoder:

 Applications of the decoder: 

A ROM can be implemented with a decoder and a set of OR gates.



Combinational circuits are often referred to as “memoryless” circuits, because their output depends only on their current input and no history of prior inputs is retained.



However, there is one sort of memory that is implemented with combinational circuits, namely read-only memory (ROM).



Recall that a ROM is a memory unit that performs only the read operation. This implies that the binary information stored in a ROM is permanent and was created during the fabrication process. Thus, a given input to the ROM (address lines) always produces the same output (data lines).

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 12 of 29

Unity University 

Because the outputs are a function only of the present inputs , the ROM is in fact a combinational circuit.



A ROM can be implemented with a decoder and a set of OR gates. As an example, consider Table 11.8. This can be viewed as a truth table with four inputs and four outputs.



For each of the 16 possible input values, the corresponding set of values of the outputs is shown. It can also be viewed as defining the contents of a 64-bit ROM consisting of 16 words of 4 bits each. The four inputs specify an address, and the four outputs specify the contents of the location specified by the address.

 Figure 11.18 shows how this memory could be implemented using a 4-to-16 decoder and four OR gates.

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 13 of 29

Unity University

Review questions with answers Part I: Descriptive questions with answers 1. What is combinational circuit in digital electronics? In digital circuit theory, combinational logic (sometimes also referred to as time-independent logic ) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. 2. Write two characteristics of combinational circuits. The two characteristics of combinational circuits are:  In combinational circuits, the output exists as long as the input exists.  A combinational circuit will always respond in the same fashion to the input function, when we apply signal to the input terminal of the combinational logic circuit. 3. Applications of XOR gate The XOR logic gate can be used as a one-bit adder that adds any two bits together to output one bit. For example, if we add 1 plus 1 in binary, we expect a two-bit answer, 10 (i.e. 2 in decimal). Since the trailing sum bit in this output is achieved with XOR,

Source: Feleke M. HaileMariam (Dr.  Eng.)

Example half adder circuit diagram

Unity University the preceding carry bit is calculated with an AND gate. This is the main principle in Half Adders. A slightly larger Full Adder circuit may be chained together in order to add ever longer binary numbers.

4. What is the half adder? The half adder is an example of a simple, functional digital circuit built from two logic gates. The half adder adds two one-bit binary numbers (AB). The output is the sum of the two bits (S) and the carry (C). 5. What do you mean by full adder? The full-adder circuit adds three one-bit binary numbers (C A B) and outputs two one-bit binary numbers, a sum (S) and a carry (C1). The full-adder is usually a component in a cascade of adders, which add 8, 16, 32, etc. binary numbers.

The carry input for the full-adder circuit is from the carry output from the circuit "above" itself in the cascade. The carry output from the full adder is fed to another full adder "below" itself in the cascade. Note: The full adder is simply two half adders joined by an OR. 6. What is the difference between a half adder and a full adder? The main difference between the Full Adder and the previous Half Adder is that afull adder has three inputs. The same two single bit data inputs A and B as before plus an additional Carry-in (C-in) input to receive the carry from a previous stage as shown below. 7. What is full adder in digital electronics? A full adder is a logical circuit that performs an addition operation on three one-bit binary numbers. The full adder produces a sum of the two inputs and carry value. It can be combined with other full adders (see below) or work on its own. 8. What are encoders and decoders? The purpose of encoder is standardization, speed, secrecy, security, or saving space by shrinking size. Encoders are combinational logic circuits and they are exactly opposite of decoders. They accept one or more inputs and generate a multibit output code. Encoders perform exactly reverse operation than decoder. 9. What is a decoder in digital electronics?

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 15 of 29

Unity University In digital electronics, a binary decoder is a combinational logic circuit that converts a binary integer value to an associated pattern of output bits. They are used in a wide variety of applications,

including

data

demultiplexing,

seven

segment

displays,

and

memory

address decoding.

Part II: Multiple Choice questions with answers 1. How many 1-of-16 decoders are required for decoding a 7-bit binary number? a) 5

b) 6

c) 7

d) 8

2. Which gate is best used as a basic comparator? a) NOR b) OR c) Exclusive-OR

d) AND

3. The carry propagation can be expressed as ________ a) Cp = AB b) Cp = A + B c) d) 4. A decoder can be used as a demultiplexer by ________. a) tying all enable pins LOW b) tying all data-select lines LOW c) tying all data-select lines HIGH d) using the input lines for data selection and an enable line for data input

5. How many 4-bit parallel adders would be required to add two binary numbers each representing decimal numbers up through 30010? a) 1 b) 2 c) 3 d) 4

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 16 of 29

Unity University 6. For the device shown here, let all D inputs be LOW, both S inputs be HIGH, and the be LOW. What is the status of the Y output?

input

a) LOW b) HIGH c) Don't Care d) Cannot be determined 7. For the device shown here, assume the D input is LOW, both S inputs are HIGH, and the input is HIGH. What is the status of the

outputs?

a) All are HIGH. b) All are LOW. c) All but

are LOW.

d) All but

are HIGH.

Part III: Digital Circuits Questions and Answers – Introduction of Arithmetic Operation 1.

The basic building blocks of the arithmetic unit in a digital computers are a) Subtractors b) Adders c) Multiplexer d) None of the Mentioned

Answer: b Explanation: The basic building blocks of the arithmetic unit in a digital computers are adders.

Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 17 of 29

Unity University Since, a parallel adder is constructed with a number of full-adder circuits connected in cascade. By controlling the data inputs to the parallel adder, it is possible to obtain different types of arithmetic operations. 2.

A digital system consists of _____ types of circuits. a) 2 b) 3 c) 4 d) 5 Answer: a Explanation: A digital system consists of two types of circuits and these are combinational and sequential logic circuit.

3.

In a combinational circuit, the output at any time depends only on the _______ at that time. a) Voltage b) Intermediate values c) Input values d) None of the Mentioned

Answer: c Explanation: In a combinational circuit, the output at any time depends only on the input values at that time.

Part IV: Digital Circuits Questions and Answers – Half Adder & Full Adder 1. Total number of inputs in a half adder is a) 2

b) 3

c) 4

d) 1

Answer: a Explanation: Total number of inputs in a half adder is two. Since, an EXOR gates has 2 inputs and carry is connected with the input of EXOR gates. 2. In which operation carry is obtained? a) Subtraction b) Addition c) Multiplication d) Both addition and subtraction Answer: b Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 18 of 29

Unity University Explanation: In addition, carry is obtained. For example: 1 0 1 + 1 1 1 = 1 0 0; in this example carry is obtained after 1st addition (i.e. 1 + 1 = 1 0). 3.

If A and B are the inputs of a half adder, the sum is given by a) A AND B b) A OR B c) A XOR B d) A EXOR B

Answer: c Explanation: If A and B are the inputs of a half adder, the sum is given by A XOR B. 4. If A and B are the inputs of a half adder, the carry is given by a) A AND B b) A OR B c) A XOR B d) A EXOR B Answer: a Explanation: If A and B are the inputs of a half adder, the carry is given by: A(AND)B. 5. Half-adders have a major limitation in that they cannot a) Accept a carry bit from a present stage b) Accept a carry bit from a next stage c) Accept a carry bit from a previous stage d) None of the Mentioned Answer: c Explanation: Half-adders have a major limitation in that they cannot accept a carry bit from a previous stage, meaning that they cannot be chained together to add multi-bit numbers. However, the two output bits of a half-adder can also represent the result A+B=3 as sum and carry both being high. 6. The difference between half adder and full adder is a) Half adder has two inputs while full adder has four inputs b) Half adder has one output while full adder has two outputs c) Half adder has two inputs while full adder has three inputs d) All of the Mentioned Source: Feleke M. HaileMariam (Dr.  Eng.)

Page 19 of 29

Unity University Answer: c Explanation: Half adder has two inputs while full adder has three outputs; this is the difference between them. 7.

If A, B and C are the inputs of a full adder then the sum is given by a) A AND B AND C b) A OR B AND C c) A OR B OR C d) A XOR B XOR C

Answer: c Explanation: If A, B and C are the inputs of a full adder then the sum is given by A OR B OR C. 8.

If A, B and C are the inputs of a full adder then the carry is given by a) A AND...