Notice:
Please change your zoom name to
20/ENG/XXX
1
CO2202 - Computer Organization
Dr. Lakshitha Wijesinghe
Acknowledgement - Notes from Dr. Randima Dinalankara
2
Last week on CO2202,
• Digital logic
• Main logic gates
• Truth tables
• Boolean algebra
• Logic circuit design
3
Digital logic: K-maps (Karnaugh map)
4
K-maps
• The Karnaugh map is a method of simplifying Boolean algebra expressions. Introduced by
Maurice Karnaugh introduced in 1953.
• Karnaugh Map is a method that used to graphically represent the logic output of the
combination circuit.
• Karnaugh Map indicates the output is 0 or 1 for each and every input combination.
• If a system has mover than an output, then K-Maps needed to be develop for each output.
5
K-maps
• Consider the inputs are A, B, C, and D.
• For two input system with one input, the K-Map is given below
• The decimal values written inside each cell represent the decimal value of the binary bit
pattern created by the inputs.
6
K-maps
• For three variable map
7
K-maps
• For four variable map
8
K-maps
• The designer is required to provided with the information that indicates the input binary
patterns corresponding decimal value which turn the output of the circuit is logic 1 as follows.
• The K-Maps are very useful in simplifying the solution.
• The main purpose of having K-Maps is to derive a simple form of logic formula instead of using
Boolean Algebra.
9
K-maps
• In the K-Map, the adjacent cells with logic 1 can be combined to form either a square or a
rectangle.
• Even this can be done on borders or corners.
• The adjacent columns or rows have an unchanged logic value of the input. Therefore, terms
can be merged and simplified logic formula can be formed.
10
K-maps: example 1
• Derive the logic function using the truth table
Input
Output (Y)
A B
0 0 0
0 1 1
1 0 0
1 1 1
• K-Map
11
K-maps: example 2
• Derive the logic function for,
• F(A,B,C) = sum (1,3,5,7)
12
K-maps: example 3
• Derive the logic function for,
• F(A,B,C,D) = sum(1,3, 10, 11, 14, 15)
13
K-maps: example 4
• Derive the logic function for,
• F(A,B,C,D) = sum(0,2,8,11)
14
Types of digital circuits
• Digital Circuits are divided into two categories.
1. Combinational Circuits : There is no feedback path from output to the input, and there is
no memory (most of the circuits we have seen in the course so far).
2. Sequential Circuits : Have a feedback path from output to the input, and they have
memory.
15
Designing a Digital Circuit
Designing a Digital Circuit has several steps.
• Has to identify the problem
• Assign letters to the inputs
• Build a truth table
• Derive the logic function for each output
• Draw the logic diagram
16
Digital logic: Combinational Circuits
17
Half and Full Adder
• Half Adder is the basic digital circuit which adds two binary bits. Consider that the inputs of
the Half Adder are logic A and B.
• The logic outputs are C and S, which represent the carrier-bit and summation-bit.
• There are four situations in the Half adder:
• 0 2 + 02 = 0 2
• 0 2 + 12 = 1 2
• 1 2 + 02 = 1 2
• 12 + 12 = 102
• The truth table on the four situations of the Half Adder is given below
18
Half Adder
• The logic function of S and C are,
• Fs = A’.B + A.B’ (XOR of A and B)
• Fc = A.B
• The schematic of the Half adder using the basic digital logic gates
19
Full Adder
• A half adder is capable to add two binary bits.
• Look at following example where a carrier bit is passed to left hand side.
1 0 12
+ 1 12
• The carrier passed from right to left in the above calculation. Three bits need to be added in
this situation.
• Therefore, an adder with summing capability of three bits need to be developed, which is
known as Full Adder.
20
Full Adder
• Develop a Full Adder. A full adder can add three bits in a single operation cycle.
• Consider the carrier bit as Cin while the direct inputs are A and B
• The truth table,
21
Full Adder
• Logic functions
• Fsum = A’.B’.Cin + A’.B.Cin’ + A.B’.Cin’ + A.B.Cin
• Fsum = A’.(B’.Cin + B.Cin’) + A.(B’.Cin’ + B.Cin)
• Fsum = A’.XOR(B,Cin) + A.XOR(B,Cin)’
• Fsum = XOR(A,B,Cin)
• Fc = A’.B.Cin + A.B’.Cin + A.B.Cin’ + A.B.Cin
• Fc = A.(B’.Cin + B.Cin’) + B.Cin
• Fc = A.XOR(B,Cin) + B.Cin
• Logic circuit
22
Decoder
• One of the output wire will be logic-high according to the binary pattern entered through the
input wires.
• Consider a decoder with one input wire. Only two logic status can be exist in the input wire :
logic high or logic low.
• Therefore, there can be only two output wires and only one of the output wire will be logic
high according to the input logic.
• If input logic is A, and outputs are O0 and O1, the truth table is,
• Logic equations are,
• O0 = A’
• O1 = A
23
Decoder
• Consider a decoder with two input wires,
• When there are two inputs, four different logic patterns can be set on the inputs.
• So there are four output wires. The input wires are labelled as A0 and A1, while the outputs
are O0, O1, O2, and O3 .
• The truth table,
• The logic functions for the outputs
• O0 = A0 ‘. A1’
• O1 = A0‘ . A1
• O2 = A0 . A1’
• O3 = A0 . A1
• This is also called a 2-to-4 decoder
24
Encoder
• Encoder output the binary number pattern according to the logic high input wire number. It
is the inverse operation of Decoder.
• This can be constructed with OR logic gates. The input line is connected to corresponding OR
gates which output the binary pattern which represent the input line number in binary
format.
• Example: A 4-by-2 Encoder.
• There are four input lines and two output lines. The inputs and outputs of the truth table
developed for the Decoder can be reversed and used in here.
25
Encoder
• The logic functions
• O0 = A2 + A3
• O1 = A1 + A3
• The combinational logic circuit,
26
Multiplexers
• Multiplexers is a digital circuitry that output one of the inputs that user selected. User can
select the input by setting the selection logic pattern on the selection pins.
• Let’s consider there are four inputs A0, A1, A2, and A3, while there are two selection pins S0
and S1.
• Exercise:
• Write down the truth table.
• Write the logic equations for the output (Y)
• Draw the logic circuit
27
Demultiplexers
• This is the component which does the inverse of the Multiplexer.
• The demultiplexer send the input to one of the outputs according to the users selection input
value.
• Other outputs are logic low while the selected output indicates the input logic.
• Exercise: Draw a logic circuit for a 1-to-4 demultiplexer intuitively without using the truth
table.
28
In the next lecture,
Today we studied combinational logic circuits in details, next week, we will look at sequential
logic circuits.
29
