Subject=Digital Design & Computer Architecture

Topic=Combinational Circuit & Sequential Circuit

Combinational Circuit
Combinational circuit is a circuit in which we combine the different gates in the
circuit, for example encoder, decoder, multiplexer and demultiplexer. Some of the
characteristics of combinational circuits are following −
 The output of combinational circuit at any instant of time, depends only on the
levels present at input terminals.
 The combinational circuit do not use any memory. The previous state of input
does not have any effect on the present state of the circuit.
 A combinational circuit can have an n number of inputs and m number of
outputs.
Block diagram

Half Adder
Half adder is a combinational logic circuit with two inputs and two outputs. The half
adder circuit is designed to add two single bit binary number A and B. It is the basic
building block for addition of two single bit numbers. This circuit has two
outputs carry and sum.
Block diagram

Truth Table
Circuit Diagram

Full Adder
Full adder is developed to overcome the drawback of Half Adder circuit. It can add
two one-bit numbers A and B, and carry c. The full adder is a three input and two
output combinational circuit.
Block diagram

Truth Table
Circuit Diagram

Half Subtractors
Half subtractor is a combination circuit with two inputs and two outputs (difference
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 as Minuend bit and B is called as Subtrahend bit.
Truth Table
Circuit Diagram

Full Subtractors
The disadvantage of a half subtractor is overcome by full subtractor. The full
subtractor is a combinational circuit with three inputs A,B,C and two output D and C'.
A is the 'minuend', B is 'subtrahend', C is the 'borrow' produced by the previous
stage, D is the difference output and C' is the borrow output.
Truth Table

Block Diagram
Multiplexers
Multiplexer is a special type of combinational circuit. There are n-data inputs, one
output and m select inputs with 2m = n. It is a digital circuit which selects one of the n
data inputs and routes it to the output. The selection of one of the n inputs is done by
the selected inputs. Depending on the digital code applied at the selected inputs, one
out of n data sources is selected and transmitted to the single output Y. E is called
the strobe or enable input which is useful for the cascading. It is generally an active
low terminal that means it will perform the required operation when it is low.
Block diagram
Multiplexers come in multiple variations

 2 : 1 multiplexer
 4 : 1 multiplexer
 16 : 1 multiplexer
 32 : 1 multiplexer
Block Diagram

Truth Table

Demultiplexers
A demultiplexer performs the reverse operation of a multiplexer i.e. it receives one
input and distributes it over several outputs. It has only one input, n outputs, m select
input. At a time only one output line is selected by the select lines and the input is
transmitted to the selected output line. A de-multiplexer is equivalent to a single pole
multiple way switch as shown in fig.
Demultiplexers comes in multiple variations.

 1 : 2 demultiplexer
 1 : 4 demultiplexer
 1 : 16 demultiplexer
 1 : 32 demultiplexer
Block diagram
Truth Table

Decoder
A decoder is a combinational circuit. It has n input and to a maximum m = 2n
outputs. Decoder is identical to a demultiplexer without any data input. It performs
operations which are exactly opposite to those of an encoder.
Block diagram

Examples of Decoders are following.

 Code converters
 BCD to seven segment decoders
 Nixie tube decoders
 Relay actuator

Encoder
Encoder is a combinational circuit which is designed to perform the inverse operation
of the decoder. An encoder has n number of input lines and m number of output
lines. An encoder produces an m bit binary code corresponding to the digital input
number. The encoder accepts an n input digital word and converts it into an m bit
another digital word.
Block diagram

Examples of Encoders are following.

 Priority encoders
 Decimal to BCD encoder
 Octal to binary encoder
 Hexadecimal to binary encoder

Sequential Circuit
The combinational circuit does not use any memory. Hence the previous state of
input does not have any effect on the present state of the circuit. But sequential
circuit has memory so output can vary based on input. This type of circuits uses
previous input, output, clock and a memory element.

Types of Sequential Circuits

Asynchronous sequential circuits
The clock signals are not used by the Asynchronous sequential circuits. The
asynchronous circuit is operated through the pulses. So, the changes in the input can
change the state of the circuit. The asynchronous circuits do not use clock pulses.
The internal state is changed when the input variable is changed. The un-clocked
flip-flops or time-delayed are the memory elements of asynchronous sequential
circuits. The asynchronous sequential circuit is similar to the combinational circuits
with feedback.

Synchronous sequential circuits

In synchronous sequential circuits, synchronization of the memory element's state is
done by the clock signal. The output is stored in either flip-flops or latches(memory
devices). The synchronization of the outputs is done with either only negative edges
of the clock signal or only positive edges.

Flip Flop
A flip-flop is a sequential digital electronic circuit having two stable states that can be
used to store one bit of binary data. Flip-flops are the fundamental building blocks of
all memory devices.

Types of Flip–Flops
 R-S flip-flop
 J-K flip-flop
 D flip-flop
 T flip-flop

R-S Flip Flop

The RS Flip Flop is considered as one of the most basic sequential logic
circuits. The Flip Flop is a one-bit memory bi-stable device.
It has two inputs, one is called “SET” which will set the device (output = 1)
and is labelled S and another is known as “RESET” which will reset the
device (output = 0) labelled as R. The RS stands for SET/RESET.
The symbol of the RS Flip-Flop is shown below:
The NAND Gate RS Flip Flop

A pair of cross-coupled 2 unit NAND gates is the simplest way to make any basic
one-bit set/reset RS Flip Flop. It forms Set/Reset bi-stable or an active LOW RS
NAND gate latch. The feedback is fed from each output to one of the other NAND
gate input.

The device consists of two inputs; one is known as SET, (S) and the other is called
as RESET, (R).

The two outputs are Q and Q bar as shown in the figure below:

The Set State

Considering the above circuit. If the input R is at logic level “0” (R = 0) and input S is
at the logic “1” (S = 1), the NAND gate Y has, at least, one of its inputs at a logic “0”.
Therefore, its output Q must be at a logic level “1” (NAND gate principles). The
Output (Q) is fed back to the input “A”. Both the inputs of the NAND gates X are at
logic “1”, and therefore, its output Q must be at the logic level”0”.

The reset input R changes its state, and goes HIGH to logic “1” with S constant at
logic “1”. The NAND gate Y input are now (R = 1) and (B = 0). The output at Q
remains at HIGH or at logic level “1” as one of its inputs is still at logic level “0”.

As a result, there is no change in state. Therefore, the flip-flop circuit is said to be

“LATCHED” or “SET” with Q = 1 and Ǭ = 0.

The Reset State

In this second stable state, Q is at logic level „0” and its inverse output Q is at logic
level “1”. And is given by (R = 1) and (S = 0). As gate X has one of its inputs at a
logic “0” its output Q must equal logic level “1”. (According to the NAND gate
principle). The output Q is fed to input B, so both the inputs to NAND gate Y are at
logic “1”., therefore, Q = 0.

If the set input S now changes the state to logic “1” with the input R remaining at
logic “1”, the output Q still remains LOW at logic level “0”. And there is no change in
the state.

Therefore, the flip-flop circuits “RESET” state has been latched.

The truth table of the Set/Reset is given below:

State S R Q Ǭ Description

SET 1 0 1 0 Set Q >>1

1 1 1 0 No Change

RESET 0 1 0 1 Reset Q >>0

1 1 0 1 No Change

INVALID 0 0 0 1 Memory with Q = 0

0 0 1 0 Memory with Q = 1

From the truth table, it is clear that when both the inputs S = 1 and R =1 the outputs
Q, and Ǭ can be at either logic level „1‟ or “0” depending upon the state of the inputs.

When the input state R = 0 and S = 0 is an invalid condition and must be avoided
because this will give both outputs Q and Ǭ at logic level “1” at the same time and
the necessary condition is that Q to be the inverse of Ǭ.

The flip-flop goes to an unstable state as both the output goes LOW. This unstable
condition arises when the LOW input is switched to HIGH. The flip-flop switches to
one state or the other and any one output of the flip-flop switches faster than the
other. This unstable condition is known as Meta- stable state.
The bistable RS flip flop is activated or set at logic “1” applied to its S input and
deactivated or reset by a logic “1” applied to R. The RS flip-flop is said to be in an
invalid condition if both the set and reset inputs are activated simultaneously.

The NOR Gate RS Flip Flop

The circuit diagram of the NOR gate flip-flop is shown in the figure below:

A simple one bit RS Flip Flops are made by using two cross-coupled NOR gates
connected in the same configuration. The circuit will work similar to the NAND gate
circuit.

The truth table of the NOR gate RS Flip Flop is shown below:

S R Q Ǭ

0 0 No Change No Change

0 1 0 1

1 0 1 0

1 1 0 0
 J-K Flip-flop
 Because of the invalid state corresponding to S=R=1 in the SR flip-flop, there
is a need of another flip-flop. The JK flip-flop operates with only positive or
negative clock transitions. The operation of the JK flip-flop is similar to the SR
flip-flop. When the input J and K are different then the output Q takes the
value of J at the next clock edge. When J and K both are low then NO change
occurs at the output. If both J and K are high, then at the clock edge, the
output will toggle from one state to the other.

 Truth table of JK flip-flop

J K Q State

0 0 0 No Change

0 1 0 Reset

1 0 1 Set

1 1 Toggles Toggle

 Characteristics table of JK flip-flop

J K Q(t) Q(t+1)

0 0 0 0

0 0 1 1
 J K Q(t) Q(t+1)

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

D Flip-flop
 In a D flip-flop, the output can only be changed at positive or negative clock
transitions, and when the inputs changed at other times, the output will remain
unaffected. The D flip-flops are generally used for shift-registers and counters.
The change in output state of D flip-flop depends upon the active transition of
clock. The output (Q) is same as input and changes only at active transition of
clock

 Truth table of D flip-flop

D Q

0 0
 D Q

1 1

T Flip-flop
 A T flip-flop (Toggle Flip-flop) is a simplified version of JK flip-flop. The T flop is
obtained by connecting the J and K inputs together. The flip-flop has one input
terminal and clock input. These flip-flops are said to be T flip-flops because of
their ability to toggle the input state. Toggle flip-flops are mostly used in
counters.

 Truth Table of T flip-flop

T Q(t) Q(t+1)

0 0 0

0 1 1

1 0 1

1 1 0

Master-Slave JK Flip Flop

In "JK Flip Flop", when both the inputs and CLK set to 1 for a long time, then Q
output toggle until the CLK is 1. Thus, the uncertain or unreliable output produces.
This problem is referred to as a race-round condition in JK flip-flop and avoided by
ensuring that the CLK set to 1 only for a very short time.
Explanation
The master-slave flip flop is constructed by combining two JK flip flops. These flip
flops are connected in a series configuration. In these two flip flops, the 1st flip flop
work as "master", called the master flip flop, and the 2nd work as a "slave", called
slave flip flop. The master-slave flip flop is designed in such a way that the output of
the "master" flip flop is passed to both the inputs of the "slave" flip flop. The output
of the "slave" flip flop is passed to inputs of the master flip flop.

In "master-slave flip flop", apart from these two flip flops, an inverter or NOT gate is
also used. For passing the inverted clock pulse to the "slave" flip flop, the inverter is
connected to the clock's pulse. In simple words, when CP set to false for "master",
then CP is set to true for "slave", and when CP set to true for "master", then CP is set
to false for "slave".

Working:

o When the clock pulse is true, the slave flip flop will be in the isolated state, and the
system's state may be affected by the J and K inputs. The "slave" remains isolated
until the CP is 1. When the CP set to 0, the master flip-flop passes the information to
the slave flip flop to obtain the output.
o The master flip flop responds first from the slave because the master flip flop is the
positive level trigger, and the slave flip flop is the negative level trigger.
o The output Q'=1 of the master flip flop is passed to the slave flip flop as an input K
when the input J set to 0 and K set to 1. The clock forces the slave flip flop to work as
reset, and then the slave copies the master flip flop.
o When J=1, and K=0, the output Q=1 is passed to the J input of the slave. The clock's
negative transition sets the slave and copies the master.
 o The master flip flop toggles on the clock's positive transition when the inputs J and K
set to 1. At that time, the slave flip flop toggles on the clock's negative transition.
o The flip flop will be disabled, and Q remains unchanged when both the inputs of the
JK flip flop set to 0.

Timing Diagram of a Master Flip Flop:

o When the clock pulse set to 1, the output of the master flip flop will be one until the
clock input remains 0.
o When the clock pulse becomes high again, then the master's output is 0, which will
be set to 1 when the clock becomes one again.
o The master flip flop is operational when the clock pulse is 1. The slave's output
remains 0 until the clock is not set to 0 because the slave flip flop is not operational.
o The slave flip flop is operational when the clock pulse is 0. The output of the master
remains one until the clock is not set to 0 again.
o Toggling occurs during the entire process because the output changes once in the
cycle.
Subject=Advance Data Structure Using Java
Topic=Trees
Tree Data Structure
A tree is also one of the data structures that represent hierarchical data. Suppose we
want to show the employees and their positions in the hierarchical form then it can
be represented as shown below:

The above tree shows the organization hierarchy of some company. In the above
structure, john is the CEO of the company, and John has two direct reports named
as Steve and Rohan. Steve has three direct reports named Lee, Bob, Ella where Steve is a
manager. Bob has two direct reports named Sal and Emma. Emma has two direct reports
named Tom and Raj. Tom has one direct report named Bill. This particular logical structure
is known as a Tree. Its structure is similar to the real tree, so it is named a Tree. In this
structure, the root is at the top, and its branches are moving in a downward direction.
Therefore, we can say that the Tree data structure is an efficient way of storing the data in a
hierarchical way.
some key points of the Tree data structure.

o A tree data structure is defined as a collection of objects or entities known as

nodes that are linked together to represent or simulate hierarchy.
o A tree data structure is a non-linear data structure because it does not store in
a sequential manner. It is a hierarchical structure as elements in a Tree are
arranged in multiple levels.
o In the Tree data structure, the topmost node is known as a root node. Each
node contains some data, and data can be of any type. In the above tree
structure, the node contains the name of the employee, so the type of data
would be a string.
o Each node contains some data and the link or reference of other nodes that
can be called children.

Some basic terms used in Tree data structure.

Let's consider the tree structure, which is shown below:

In the above structure, each node is labeled with some number. Each arrow shown in
the above figure is known as a link between the two nodes.

o Root: The root node is the topmost node in the tree hierarchy. In other words,
the root node is the one that doesn't have any parent. In the above structure,
node numbered 1 is the root node of the tree. If a node is directly linked to
some other node, it would be called a parent-child relationship.
 o Child node: If the node is a descendant of any node, then the node is known
as a child node.
o Parent: If the node contains any sub-node, then that node is said to be the
parent of that sub-node.
o Sibling: The nodes that have the same parent are known as siblings.
o Leaf Node:- The node of the tree, which doesn't have any child node, is called
a leaf node. A leaf node is the bottom-most node of the tree. There can be
any number of leaf nodes present in a general tree. Leaf nodes can also be
called external nodes.
o Internal nodes: A node has atleast one child node known as an internal
o Ancestor node:- An ancestor of a node is any predecessor node on a path
from the root to that node. The root node doesn't have any ancestors. In the
tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node
10.

What is a Binary Search tree?

A binary search tree follows some order to arrange the elements. In a Binary search
tree, the value of left node must be smaller than the parent node, and the value of
right node must be greater than the parent node. This rule is applied recursively to
the left and right subtrees of the root.

Example

AVL Tree
AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is
named AVL in honour of its inventors.
AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its
right sub-tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1,

otherwise, the tree will be unbalanced and need to be balanced.

An AVL tree is given in the following figure. We can see that, balance factor
associated with each node is in between -1 and +1. therefore, it is an example of AVL
tree.

AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0,
and 1. There are basically four types of rotations which are as follows:

1. L L rotation: Inserted node is in the left subtree of left subtree of A

2. R R rotation : Inserted node is in the right subtree of right subtree of A
3. L R rotation : Inserted node is in the right subtree of left subtree of A
4. R L rotation : Inserted node is in the left subtree of right subtree of A

Where node A is the node whose balance Factor is other than -1, 0, 1.

B Tree
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of
order m can have at most m-1 keys and m children. One of the main reason of using
B tree is its capability to store large number of keys in a single node and large key
values by keeping the height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it

contains the following properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2
children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

A B tree of order 4 is shown in the following image.

What is a Splay Tree?

A splay tree is a self-balancing tree, but AVL and Red-Black trees are also self-
balancing trees then. What makes the splay tree unique two trees. It has one extra
property that makes it unique is splaying.

A splay tree contains the same operations as a Binary search tree, i.e., Insertion,
deletion and searching, but it also contains one more operation, i.e., splaying. So. all
the operations in the splay tree are followed by splaying.

Suppose we want to search 7 element in the tree, which is shown below:

Threaded Binary Tree
In the linked representation of binary trees, more than one half of the link fields
contain NULL values which results in wastage of storage space. If a binary tree
consists of n nodes then n+1 link fields contain NULL values. So in order to
effectively manage the space, a method was devised by Perlis and Thornton in which
the NULL links are replaced with special links known as threads. Such binary trees
with threads are known as threaded binary trees. Each node in a threaded binary
tree either contains a link to its child node or thread to other nodes in the tree.

Types of Threaded Binary Tree

There are two types of threaded binary tree 4:5

o One-way threaded Binary Tree

o Two-way threaded Binary Tree

One-way threaded Binary trees:

Two-way threaded Binary Trees:

Heap Data Structure

A heap is a complete binary tree, and the binary tree is a tree in which the node can have
utmost two children. Before knowing more about the heap data structure, we should know
about the complete binary tree.
In the above figure, we can observe that all the internal nodes are completely filled except the
leaf node; therefore, we can say that the above tree is a complete binary [Link] Video

The above figure shows that all the internal nodes are completely filled except the leaf node,
but the leaf nodes are added at the right part; therefore, the above tree is not a complete
binary tree.

How can we arrange the nodes in the Tree?

There are two types of the heap:

o Min Heap
o Max heap

Min Heap: The value of the parent node should be less than or equal to either of its children.

Or

In other words, the min-heap can be defined as, for every node i, the value of node i is greater
than or equal to its parent value except the root node. Mathematically, it can be defined as:

A[Parent(i)] <= A[i]

Let's understand the min-heap through an example.

In the above figure, 11 is the root node, and the value of the root node is less than the value of
all the other nodes (left child or a right child).

Max Heap: The value of the parent node is greater than or equal to its children.

Or

In other words, the max heap can be defined as for every node i; the value of node i is less
than or equal to its parent value except the root node. Mathematically, it can be defined as:

A[Parent(i)] >= A[i]

The above tree is a max heap tree as it satisfies the property of the max heap. Now,
let's see the array representation of the max heap.

Applications of Heaps:
1) Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
2) Priority Queue: Priority queues can be efficiently implemented using Binary
Heap because it supports insert(), delete() and extractmax(), decreaseKey()
operations in O(logn) time. Binomial Heap and Fibonacci Heap are variations of
Binary Heap. These variations perform union also efficiently.
3) Graph Algorithms: The priority queues are especially used in Graph Algorithms
like Dijkstra‟s Shortest Path and Prim‟s Minimum Spanning Tree.
4) Many problems can be efficiently solved using Heaps. See following for
example.
a) K‟th Largest Element in an array.
b) Sort an almost sorted array/
c) Merge K Sorted Arrays.
Operations on Min Heap:
1) getMini(): It returns the root element of Min Heap. Time Complexity of this
operation is O(1).
2) extractMin(): Removes the minimum element from MinHeap. Time Complexity of
this Operation is O(Logn) as this operation needs to maintain the heap property (by
calling heapify()) after removing root.
3) decreaseKey(): Decreases value of key. The time complexity of this operation is
O(Logn). If the decreases key value of a node is greater than the parent of the
node, then we don‟t need to do anything. Otherwise, we need to traverse up to fix
the violated heap property.
4) insert(): Inserting a new key takes O(Logn) time. We add a new key at the end of
the tree. IF new key is greater than its parent, then we don‟t need to do anything.
Otherwise, we need to traverse up to fix the violated heap property.
5) delete(): Deleting a key also takes O(Logn) time. We replace the key to be
deleted with minum infinite by calling decreaseKey(). After decreaseKey(), the
minus infinite value must reach root, so we call extractMin() to remove the key.