COMPUTER ARCHITECTURE AND ORGANISATION

UNIT 1 NOTES

What are Logic Gates?

Binary logic deals with binary variables and with operations that assume a logical meaning. It is used to
describe, in algebraic or tabular form, the manipulation and processing of binary information. The manipulation
of binary information is done by logic circuits called gates. Gates are blocks of hardware that produce signals
of binary 1 or 0 when input logic requirements are satisfied.

Truth table:

A truth table is a breakdown of all the possible truth values returned by a logical expression. A truth value is
typically either true or false, or 1 or 0.

A Boolean expression is a logical statement that evaluates a condition and returns a Boolean value,
which is either true or false.

Combinational Circuits:

A combinational circuit is a connected arrangement of logic gates with a set of inputs and outputs. A
combinational circuit transforms binary information from the given input data to the required output data.
Combinational circuits are employed in digital computers for generating binary control decisions and for
providing digital components required for data processing.

A combinational circuit can be described by a truth table showing the binary relationship between the n input
variables and the m output variables. The truth table lists the corresponding output binary values for each of
the 2n input combinations. A combinational circuit can also be specified with m Boolean functions one for
each output variable. Each output function is expressed in terms of the n input variables.

n input Combinational circuit m output

variables variables

Block diagram of a combinational circuit.

Half-Adder
The most basic digital arithmetic circuit is the addition of two binary digits. A combinational circuit
that performs the arithmetic addition of two bits is called a half adder.
The input variables of a half-adder are called the augend and addend bits. The output variables are
the SUM and CARRY. It is necessary to specify two output variables because the sum of 1 + 1 is binary
10, which has two digits. We assign symbols X and Y to the two input variables and S (for sum) and C
(for carry) to the two output variables. The truth table for the half-adder is shown in fig(a) . The C
output is 0 unless both inputs are 1. The S output represents the least significant bit of the sum. The
Boolean functions for the two outputs can be obtained directly from the truth table:

S= X’Y + XY’ = X⊕Y

C = XY

X Y C S X
0 0 0 0 S
Y
0 1 0 1
1 0 0 1
1 1 1 0
C
(a) Truth table
(b) Logic diagram

The logic diagram is shown in fig(b). It consists of an exclusive -OR gate and an AND gate. A half-adder logic
module of an exclusive OR gate and an AND gate can be used to implement universal logic gates NAND and
NOR.1
Full-Adder
A full-adder is a combinational circuit that forms the arithmetic sum of three input bits. It consists of
three inputs and two outputs. Two of the input variables, denoted by X and Y, represent the two
significant bits to be added. The third input Z, represents the carry from the previous lower significant
position. Two outputs are necessary because the arithmetic sum of three binary digits ranges in value
from 0 to 3, and binary 2 or 3 needs two digits. The two outputs are designated by the symbols S (for
sum) and C (for carry). The binary variable S gives the value of the least significant bit of the sum. The
binary variable C gives the output carry.
The truth table of the full-adder is shown below. The eight rows under the input variables
designate all possible combinations that the binary variables may have. The values of the output
variables are determined from the arithmetic sum of the input bits. When all input bits are 0, the
output is 0. The S output is equal to 1 when only one input is equal to 1 or when all three inputs are
equal to 1. The C output has a carry of 1 if two or three inputs are equal to 1.

We obtain the two Boolean expressions for the full-adder as :

S = X ⊕ Y⊕ Z
C = XY + (X ⊕ Y) Z
The logic diagram and block diagram of the full-adder is shown in fig below. The full adder circuit consists of
two half-adders and an OR gate.
Logic diagram of Full Adder

X S

Y Full Adder

Z C

Block diagram of Full Adder

Multiplexers
A multiplexer is a combinational circuit that has many data inputs and a single output, depending
on control or select inputs. For N input lines, log2(N) selection lines are required, or equivalently,
for 2n2n input lines, n selection lines are needed. Multiplexers are also known as “N-to-1 selectors,”
parallel-to-serial converters, many-to-one circuits, and universal logic circuits. They are mainly used
to increase the amount of data that can be sent over a network within a certain amount of time
and bandwidth .

Types of Mux
The Mux can be of different types based on input but in this article we will go through two major
types of mux which are

• 2×1 Mux
• 4×1 Mux
•

2×1 Multiplexer

The 2×1 is a fundamental circuit which is also known 2-to-1 multiplexer that are used to choose
one signal from two inputs and transmits it to the output. The 2×1 mux has two input lines, one
output line, and a single selection line. It has various applications in digital systems such as in
microprocessor it is used to select between two different data sources or between two
different instructions.

Block Diagram of 2:1 Multiplexer with Truth Table

Given Below is the Block Diagram and Truth Table of 2:1 Mux. In this Block Diagram where I0
and I1 are the input lines, Y is the output line and S0 is a single select line.
The output of the 2×1 Mux will depend on the selection line S0,
• When S is 0(low), the I0 is selected
• when S0 is 1(High), I1 is selected

Logical Expression of 2×1 Mux

Using the Truth Table ,the Logical Expression for Mux can be determined as

Y = S0.I0 + S0.I1

Circuit Diagram of 2×1 Multiplexers

Using truth table, the circuit diagram can be given as

4×1 Multiplexer
The 4×1 Multiplexer which is also known as the 4-to-1 multiplexer. It is a multiplexer
that has 4 inputs and a single output. The Output is selected as one of the 4 inputs
which is based on the selection inputs. The number of the Selection lines will depend
on the number of the input which is determined by the equation log2n , In 4×1 Mux the
selection lines can be determined as log4=2, so two selections are needed.

Block Diagram of 4×1 Multiplexer

In the Given Block Diagram I0, I1, I2, and I3 are the 4 inputs and Y is the Single
output which is based on Select lines S0 and S1.
The output of the multiplexer is determined by the binary value of the selection lines
• When S1S0=00, the input I0 is selected.
• When S1S0=01, the input I1 is selected.
• When S1S0=10, the input I2 is selected.
• When S1S0=11, the input I3 is selected.
•
Truth Table of 4×1 Multiplexer
Given Below is the Truth Table of 4×1 Multiplexer

Circuit Diagram of 4×1 Multiplexers

Using truth table the circuit diagram can be given as
Multiplexer can act as universal combinational circuit. All the standard logic
gates can be implemented with multiplexers.

De-Multiplexer
DEMUX or De-Multiplexer is a data distributor combinational circuit. It works in a
reverse way of the Multiplexer. The DEMUX has 1 input port and 2^n output lines.
Here n signifies the selection line for a DEMUX. As per the selection line value, the
DEMUX input lines will be connected to receive the output. Demultiplexer receives
digital information from a single source and converts it into several sources.

General Block Diagram Of A DEMUX

Here is the basic block diagram of a DEMUX as mentioned below.
Half Subtractor

A half subtractor is a digital logic circuit that performs binary subtraction of two single-bit
binary numbers. It has two inputs, A and B, and two outputs, DIFFERENCE and BORROW. The
DIFFERENCE output is the difference between the two input bits, while the BORROW output
indicates whether borrowing was necessary during the subtraction.

The half subtractor can be implemented using basic gates such as XOR and NOT gates. The
DIFFERENCE output is the XOR of the two inputs A and B, while the BORROW output is the
NOT of input A and the AND of inputs A and B.

Half subtractor is a combination circuit with two inputs and two outputs that
are different and borrow. It produces the difference between the two binary bits at the
input and also produces an output (Borrow) to indicate if a 1 has been borrowed. In the
subtraction (A-B), A is called a Minuend bit and B is called a Subtrahend bit.

Truth Table

The SOP form of the Diff and Borrow is as follows:

Diff= A'B+AB'
Borrow = A'B
Circuit Diagram

Full Subtractor

A full-subtractor is a combinational circuit that has three inputs A, B, bin and two
outputs d and b. Where, A is the minuend, B is subtrahend, bin is borrow produced
by the previous stage, d is the difference output and b is the borrow output.

As we know that the half-subtractor can only be used for subtraction of LSB (least
significant bit) of binary numbers. If there is any borrow during the subtraction
of the LSBs of two binary numbers, then it will affect the subtraction of next
stages. Therefore, the subtraction with borrow are performed by a full subtractor.

The block diagram and circuit diagram of a full-subtractor is shown in Figure-1.

Therefore, we can realize the full-subtractor using two XOR gates, two NOT
gates, two AND gates, and one OR gate.
Operation of Full Subtractor
Now, let us understand the operation of the full subtractor. Full subtractor performs
its operation to find the difference of two binary numbers according to the rules of
binary subtraction, which are as follows −

In the case of full subtractor, the 1s and 0s for the output variables (difference and
borrow) are determined from the subtraction of A – B – bin.

From the logic circuit diagram of the full subtractor, it is clear that the difference bit
(d) is obtained by the XOR operation of the two inputs A, B, and bin, and the output
borrow bit (b) is obtained by NOT, AND, and OR operations of variable A, B, and bin.

Truth Table of Full-Subtractor

The truth table is one that gives relationship between input and output of a logic
circuit. The following is the truth table of the full-subtractor −

Encoders
Encoders convert 2N lines of input into a code of N bits and Decoders decode the N
bits into 2N lines.

An encoder is a combinational circuit that converts binary information in the form of a

2N input lines into N output lines, which represent N bit code for the input. For simple
encoders, it is assumed that only one input line is active at a time. As an example, let’s
consider Octal to Binary encoder. As shown in the following figure, an octal-to-binary
encoder takes 8 input lines and generates 3 output lines.
Truth Table –
D7 D6 D5 D4 D3 D2 D1 D0 X Y Z

0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0 0 1

0 0 0 0 0 1 0 0 0 1 0

0 0 0 0 1 0 0 0 0 1 1

0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0 1 0 1

0 1 0 0 0 0 0 0 1 1 0

1 0 0 0 0 0 0 0 1 1 1
Binary Decoder
A binary decoder is a digital circuit that converts a binary code into a set of outputs. The binary
code represents the position of the desired output and is used to select the specific output that is
active. Binary decoders are the inverse of encoders and are commonly used in digital systems to
convert a serial code into a parallel set of outputs.

1. The basic principle of a binary decoder is to assign a unique output to each possible
binary code. For example, a binary decoder with 4 inputs and 2^4 = 16 outputs can
assign a unique output to each of the 16 possible 4-bit binary codes.
2. The inputs of a binary decoder are usually active low, meaning that only one input is
active (low) at any given time, and the remaining inputs are inactive (high). The
active low input is used to select the specific output that is active.
3. There are different types of binary decoders, including priority decoders, which
assign a priority to each output, and error-detecting decoders, which can detect errors
in the binary code and generate an error signal.

In summary, a binary decoder is a digital circuit that converts a binary code into a set of outputs.
Binary decoders are the inverse of encoders and are widely used in digital systems to convert
serial codes into parallel outputs.

4 bit register with parallel load

Refer Text book