What are the rules of BCD addition.

Binary Coded Decimal Addition

Binary coded decimal addition follows the rules of binary arithmetic, however there are some extra things that
require to be taken care of. The BCD addition of two BCD numbers is performed as per the following steps −
 Step 1 − Perform addition of two BCD numbers by following the rules of binary addition.
 Step 2 − If the result or sum is a 4-bit binary number which is less than or equal to 9, then the sum is a
valid BCD number.
 Step 3 − If the sum is a 4-bit number that is greater than 9 or if a carry is generated, then it is an
invalid sum.
 Step 4 − To obtain the corrected result/sum, add 6 (0110) to the 4-bit invalid sum. If a carry is
generated when 6 is added, then propagate and add this carry to the next 4-bit group. This step is done
to skip the six illegal BCD codes (i.e. 1010, 1011, 1100, 1101, 1110, and 1111).
Rules of Binary Addition
The following are the rules used to perform binary addition of two binary digits −
First Second Result
Bit Bit
0 0 0 + 0 = 0; no
carry
0 1 0 + 1 = 1; no
carry
1 0 1 + 0 = 1; no
carry
1 1 1 + 1 = 0; carry =
1
After getting the knowledge of BCD addition and rules of binary addition, let us now consider some solved
examples to understand the BCD addition in detail.

Explain AND and OR gates with help of a diagram and truth table.
The AND gate is so named because, if 0 is called "false" and 1 is called "true," the gate acts in the same way as
the logical "and" operator. The following illustration and table show the circuit symbol and logic combinations
for an AND gate. (In the symbol, the input terminals are at left and the output terminal is at right.) The output
is "true" when both inputs are "true." Otherwise, the output is "false." In other words, the output is 1 only
when both inputs one AND two are 1.

AND gate
Input Input 2 Output
1
0 0 0
0 1 0
1 0 0
1 1 1
The OR gate gets its name from the fact that it behaves after the fashion of the logical inclusive "or." The
output is "true" if either or both of the inputs are "true." If both inputs are "false," then the output is "false." In
other words, for the output to be 1, at least input one OR two must be 1.

OR gate

Input Input 2 Output

1
0 0 0
0 1 1
1 0 1
 1 1 1

What are universal gates ? Implement all basic logic gates using universal gates.
Universal Gates may implement any Boolean function without using any other gate type. The NAND gate
and NOR gate are called Universal gates because they can perform all the three essential functions of AND,
OR and NOT gates.
A two-input NAND gate is a digital combination logic circuit that performs the logical inverse of an AND
gate. While an AND gate outputs a logical “1” only if both inputs are logical “1,” a NAND gate outputs a
logical “0” for this same combination of inputs. Here, we will explore the Universal gates, NAND Gate &
NOR Gate, along with a few examples of each.
1. Implementation of AND Gate using Universal gates.
a) Using NAND Gates
The AND gate can be implemented by using two NAND gates in the below fashion:

b) Using NOR Gates

Implementation of AND gate using only NOR gates as shown below:

2. Implementation of OR Gate using Universal gates.

a) Using NAND Gates
The OR gate can be implemented using the NAND gate as below:

b) Using NOR Gates

Implementation of OR gate using two NOR gates as shown in the picture below:

3. Implementation of NOT Gate using Universal gates.

a) Using NAND Gates

b) Using NOR Gates

4. Implementation of XOR Gate using Universal gates.

a) Using NAND Gates

b) Using NOR Gates

5. Implementation of XNOR Gate using Universal gates.

a) Using NAND Gate

b) Using NOR Gate

6. Implementation of NOR Gate using NAND Gates

7. Implementation of NAND Gate using NOR Gates

Explain the principle of duality.

Duality Principle in Boolean Algebra states that if we have true Boolean postulates or equations then the dual
of this statement equation is also true.
The principle says that for any identity in Boolean algebra expressed in terms of ANDs, ORs, and NOTs, there
exists a dual identity that can be obtained by exchanging ANDs and ORs.
Thus, a dual of a boolean statement is obtained by replacing the statement’s symbols with their counterparts.
This means that “0” becomes a “1”, “1” becomes a “0”, “+” and in a similar way "+" becomes a “.” and “.”
becomes a “+”.
Let's understand it through an example.
Suppose we have the following true Boolean statements:
(1). 1 • 0 = 1
The dual of this statement comes out to be:
(2). 0 + 1 = 0
As you can see, the dual of the true Boolean statement (1) is (2). We found statement (2) by replacing each
symbol from (1) with its Boolean counterpart as described above. Thus, (2) is also a true Boolean statement.
The fundamental takeaway from this principle is there is nothing intrinsically special about our denotation of
“0” and “1”.
Duality Principles Examples
Expression Dual
1=0 0=1
0=1 1=0
1.0 = 0 0+1=1
0.1 = 0 1+0=1
1+0=1 0.1 = 0
0+1=1 1.0 = 0
A.0 = 0 A+1=1
0.A = 0 1+A=1
A.1 = 0 A+0=1
1.A = 0 1+A=1
A.A = 0 A+A=1
A.B = B.A A+B=B+A
A.(B.C) = (A.B).C A + (B + C) = (A + B) + C
A.(A + B) = A A + A.B = A
AB + C + BCA = 0 (A + B).C.(B + C + A) = 1

State and prove de morgan’s law

De Morgan's Theorem:-
There are two theorems -
De Morgan's First Theorem:-
Statement - The complement of a logical sum equals the logical product of the complements.
Logic equation - A+B¯=A¯.B¯
Proof –

NOR gate is equivalent to bubbled AND gate.

De Morgan's Second Theorem:-
Statement - The complement of a logical product equals the logical sum of the complements.Logic equation -
A.B¯=A¯+B¯
Proof -

NAND gate is equivalent to bubbled OR gate.

Truth Table to prove De Morgan's Theorem:-

Explain how sum of minterms of F can be converted to product of Maxterms of F.

Sum of Products (SOP)
A boolean expression consisting purely of Minterms (product terms) is said to be in canonical sum of products
form.
Example
lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and
lets say, output of F is true i.e., F = 1 when any one of the input is true or 1. Now we draw the truth table for F.
A B F
0 0 0
0 1 1
1 0 1
1 1 1
Now we will create a column for the minterm using the variables A and B. If input is 0 we take the
complement of the variable and if input is 1 we take the variable as is.
A B F Minterm
0 0 0 A'B'
0 1 1 A'B
1 0 1 AB'
1 1 1 AB
To get the desired canonical SOP expression we will add the minterms (product terms) for which the output is
1.
F = A’B + AB’ + AB
Converting Sum of Products (SOP) to shorthand notation
From the previous example we have
F = A’B + AB’ + AB
Now, lets say we want to express the SOP using shorthand notation.
we have F = A’B + AB’ + AB
First we need to denote the minterms in shorthand notation.

A’B = (01)2 = m1
AB’ = (10)2 = m2
AB = (11)2 = m3

We saw the conversion of SOP to shorthand notation. Lets check the conversion of shorthand notation to SOP.
Converting shorthand notation to Sum of Products (SOP)
Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and
lets say, the minterms are expressed as shorthand notation given below.
F = ∑(1, 2, 3)our task is to get the SOP.
F has two input variables A and B and output of F = 1 for m1, m2 and m3 i.e., 2nd, 3rd and 4th combination.
we have, F = ∑(1, 2, 3)
= m1 + m2 + m3
= 01 + 10 + 11

To convert from shorthand notation to SOP we follow the given rules. If the variable is 1 then it is taken "as
is" and if the variable is 0 then we take its "complement".

F = ∑(1, 2, 3)
= A’B + AB’ + AB

And we have the required SOP

Product of Sums (POS)

A boolean expression consisting purely of Maxterms (sum terms) is said to be in canonical product of sums
form.

Example
Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and
lets say, output of F is true i.e., F = 1 when only one of the input is true or 1.

now we draw the truth table for F

A B F
0 0 0
0 1 1
1 0 1
1 1 0
Now we will create a column for the maxterm using the variables A and B. If input is 1 we take the
complement of the variable and if input is 0 we take the variable as is.

A B F Maxterm
0 0 0 A+B
0 1 1 A + B'
1 0 1 A' + B
1 1 0 A' + B'
To get the desired canonical POS expression we will multiply the maxterms (sum terms) for which the output
is 0.

F = (A+B) . (A’+B’)

Converting Product of Sums (POS) to shorthand notation

From the previous example we have
F = (A+B) . (A’+B’)
Now, lets say we want to express the POS using shorthand notation.

we have F = (A+B) . (A’+B’)

First we need to denote the maxterms in shorthand notation.

 A+B = (00)2 = M0
A’+B’ = (11)2 = M3

Now we express F using shorthand notation.

F = M0 . M3

This can also be written as F = ∏(0, 3)

We saw the conversion of POS to shorthand notation. Lets check the conversion of shorthand notation to POS.

Converting shorthand notation to Product of Sums (POS)

Lets say, we have a boolean function F defined on two variables A and B so, A and B are the inputs for F and
lets say, the maxterm are expressed as shorthand notation given below.

F = ∏(1, 2, 3)

Our task is to get the POS.

F has two input variables A and B and output of F = 0 for M1, M2 and M3 i.e., 2nd, 3rd and 4th combination.

we have, F = ∏(1, 2, 3)
= M1 . M2 . M3
= 01 . 10 . 11

To convert from shorthand notation to POS we follow the given rules. If the variable is 0 then it is taken as is
and if the variable is 1 then we take its complement.

we have, F = ∏(1, 2, 3)
= (A+B’) . (A’+B) . (A’+B’)

And we have the required POS.

Explain the Quine McCluskey Method.

Boolean function simplification is one of the basics of Digital Electronics. The quine-McCluskey method
also called the tabulation method is a very useful and convenient method for simplification of the Boolean
functions for a large number of variables (greater than 4). This method is useful over K-map when the
number of variables is larger for which K-map formation is difficult. This method uses prime implicants for
simplification.
In this method, we construct multiple tables according to the question and at the last, we make a prime
implicant table which is used to obtain essential prime implicants which are present in the simplified boolean
expression. This method requires prior knowledge of decimal to binary representation and the basics of
boolean algebra. It is a suitable method for a large number of input variables which can be easily solved by
this method but the computation complexity is high. Majorly, this method includes the use of minterms, and
prime implicants and obtains essential prime implicants which are further used in the simplified boolean
functions.
Quine McCluskey Method (QMC):
 Quine McCluskey method also known as the tabulation method is used to minimize the Boolean functions.
 It simplifies boolean expression into the simplified form using prime implicants.
 This method is convenient to simplify boolean expressions with more than 4 input variables.
 It uses an automatic simplification routine.
Terminologies:
Implicant: Implicant is defined as a group of 1’s(for minterm).
Prime implicant: It is the largest possible group of 1’s(for minterm).
Essential Prime implicant: Essential prime implicants are groups that cover at least one minterm which
cannot be covered by other applicants.
Note: This method uses decimal to binary representation.
Steps for Quine McCluskey Method:
1. Arrange the given minterms according to the number of ones present in their binary representation in
ascending order.
2. Take the minterms from the continuous group if there is only a one-bit change to make their pair.
 3. Place the ‘-‘ symbol where there is a bit change accordingly and keep the remaining bits the same.
4. Repeat steps 2 to 3 until we get all prime implicants (when all the bits present in the table are different).
5. Make a prime implicant table that consists of the prime implicants (obtained minterms) as rows and the
given minterms (given in problem) as columns.
6. Place ‘1’ in the minterms (cell) which are covered by each prime implicant.
7. Observe the table, if the minterm is covered by only one prime implicant then it is an essential to prime
implicant.
8. Add the essential prime implicants to the simplified boolean function.
Example: Simplify using tabulation method : F(A,B,C,D) =∑ m(0,1,2,4,6,8,9,11,13,15)
Solution: Convert the given minterms into their binary representation and arrange them according to the
number of ones present in the binary representation.
TABLE 1
Grou Minter
p m A B C D

0 0 0 0 0
0

0
1 0 0 1
2 0 0 1 0
1
4 0 0 0
8 1 1 0 0

6 0 1 1 0
2
9 1 0 1
0

11 1 0 1 1
3
13 1 0 1
1

4 15 1 1 1
1

Explain analysis and design procedure for combinational logic circuit.

Construction of Combinational Circuits



A Combinational Circuit consist of logic gates whose outputs at any instant of time are determined directly
from the present combination of inputs without regard to previous input. Examples of combinational circuits:
Adder, Subtractor, Converter, and Encoder/Decoder.
Here we are going to learn how to construct and analyze any type of combinational circuit using four general
steps. I am going to explain this trick with the help of the one combinational circuit and you can apply the
same for implementing other combinational circuits.
Following are the four steps to construct and analyze any combinational circuit.
 Step-1: Identify the number of inputs and outputs of the circuit.
First of all, we have to think about the inputs and outputs of the circuit by considering which type of logical
operation we want to perform with the circuit.
For example, we have to create a circuit that can add two bits. For this, we require two inputs (one for the
first bit (A) another for the second bit (B)) and two outputs one for sum (S) of two bits and another for carry
(C).
In total, we require 2 inputs and 2 outputs. So here our first step is completed.
 Step-2: Creating the Truth Table.
In this step we have to create truth table for our circuit so for this first we will create input columns and list
 all the possible combinations of inputs. In our case 2 bits can have maximum 4 combinations (00 01 10 11).
Now in output, we have two columns (Sum and Carry) as discussed earlier. Now we have to fill output
columns in such a way that for which logical operation we are constructing circuit.
In our circuit, we want addition so we will add those input bits and write the sum of those bits in (Sum)
column and if carry is generated we will write 1 else write.
0 in (Carry) column.

 Step-3: Simplify the Boolean function for each output.

In this step, we have to just create a simplified Boolean function according to inputs and outputs of the truth
table obtained in the previous step.
For Sum,
Sum = A'B + AB' = A XOR B
For Carry,
Carry = AB = A AND B
 Step-4: Constructing circuit using Boolean function obtained from third step.
For sum, we have obtained (A XOR B) so we will connect A and B to the inputs of XOR gate and take its
output as a sum. For carry, we have obtained (A AND B) so we will connect A and B to the inputs of AND
gate and take its output as a carry.

Now in this circuit, if you provide input at A and B ends. You will get the output on sum and carry ends
according to truth table we have created above. So here we have completed our four steps for creating the
combinational circuit.

Explain the half adder with help of truth table, k-map and block diagram.
A half adder is a digital logic circuit that performs binary addition of two single-bit binary numbers. It has
two inputs, A and B, and two outputs, SUM and CARRY. The SUM output is the least significant bit (LSB)
of the result, while the CARRY output is the most significant bit (MSB) of the result, indicating whether
there was a carry-over from the addition of the two inputs. The half adder can be implemented using basic
gates such as XOR and AND gates.
Sure, here’s a more in-depth explanation of the half adder circuit:
The half adder is a basic building block for more complex adder circuits such as full adders and multiple-bit
adders. It performs binary addition of two single-bit inputs, A and B, and provides two outputs, SUM and
CARRY.
The SUM output is the least significant bit (LSB) of the result, which is the XOR of the two inputs A and B.
The XOR gate implements the addition operation for binary digits, where a “1” is generated in the SUM
output only when one of the inputs is “1”.
The CARRY output is the most significant bit (MSB) of the result, indicating whether there was a carry-over
from the addition of the two inputs. The CARRY output is the AND of the two inputs A and B. The AND
gate generates a “1” in the CARRY output only when both inputs are “1”.
Half Adder (HA):
Half adder is the simplest of all adder circuits. Half adder is a combinational arithmetic circuit that adds two
numbers and produces a sum bit (s) and carry bit (c) both as output. The addition of 2 bits is done using a
combination circuit called a Half adder. The input variables are augend and addend bits and output variables
are sum & carry bits. A and B are the two input bits.
let us consider two input bits A and B, then sum bit (s) is the X-OR of A and B. it is evident from the
function of a half adder that it requires one X-OR gate and one AND gate for its construction.
Truth Table:
 Here we perform two operations Sum and Carry, thus we need two K-maps one for each to derive the
expression.
Logical Expression:
For Sum:

Sum = A XOR B
For Carry:

Carry = A AND B
Implementation:

Explain concept of binary parallel adder with help of diagram.

Parallel Adder –
A single full adder performs the addition of two one bit numbers and an input carry. But a Parallel Adder is
a digital circuit capable of finding the arithmetic sum of two binary numbers that is greater than one bit in
length by operating on corresponding pairs of bits in parallel. It consists of full adders connected in a
chain where the output carry from each full adder is connected to the carry input of the next higher order full
adder in the chain. A n bit parallel adder requires n full adders to perform the operation. So for the two-
bit number, two adders are needed while for four bit number, four adders are needed and so on. Parallel
adders normally incorporate carry lookahead logic to ensure that carry propagation between subsequent
stages of addition does not limit addition speed.

Working of parallel Adder –

1. As shown in the figure, firstly the full adder FA1 adds A1 and B1 along with the carry C1 to generate the
sum S1 (the first bit of the output sum) and the carry C2 which is connected to the next adder in chain.
2. Next, the full adder FA2 uses this carry bit C2 to add with the input bits A2 and B2 to generate the sum
S2(the second bit of the output sum) and the carry C3 which is again further connected to the next adder in
chain and so on.
3. The process continues till the last full adder FAn uses the carry bit Cn to add with its input An and Bn to
generate the last bit of the output along last carry bit Cout.

Explain 1:2 demux with truth table, block diagram and k-map
There are various types of De-multiplexer which are as follows:
1×2 De-multiplexer:
In the 1 to 2 De-multiplexer, there are only two outputs, i.e., Y 0, and Y1, 1 selection lines, i.e., S 0, and single
input, i.e., A. On the basis of the selection value, the input will be connected to one of the outputs. The block
diagram and the truth table of the 1×2 multiplexer are given below.
Block Diagram:

Truth Table:

The logical expression of the term Y is as follows:

Y0=S0'.A
Y1=S0.A
Logical circuit of the above expressions is given below:

Explain octal to binary encoder with help of truth table.

An encoder has 2n or fewer input lines, only one of which is in the “1” state at a particular time and an n-bit
code is generated on “n” output lines depending upon which of the input is excited. In other words, an encoder
is a circuit in which output lines generate the binary code corresponding to the input value.

Octal To Binary Encoder Octal to binary encoder has 23 = 8 input lines D0 to D7 and 3 output lines Y0 to Y2.
Below is the truth table for octal to the binary encoder.
 From the truth table, the outputs can be expressed by following Boolean Function.
Y0 = D 1 + D 3 + D 5 + D 7
Y1 = D 2 + D 3 + D 6 + D 7
Y2 = D 4 + D 5 + D 6 + D 7
Note: Above boolean functions are formed by OR ing all the input lines for which output is 1. For instance
Y0 is 1 for D1, D3, D5, D7 input lines. The encoder can, therefore, be implemented with OR gates whose inputs
are determined directly from the truth table as shown in the image below:

Explain the concept of flipflop.

Flip-flop is a circuit that maintains a state until directed by input to change the state. A basic flip-flop can be
constructed using four-NAND or four-NOR gates. Flip flop is popularly known as the basic digital memory
circuit. It has its two states as logic 1(High) and logic 0(low) states. A flip flop is a sequential circuit which
consist of single binary state of information or data. The digital circuit is a flip flop which has two outputs
and are of opposite states. It is also known as a Bistable Multivibrator.
Types of flip-flops:
1. SR Flip Flop
2. JK Flip Flop
3. D Flip Flop
4. T Flip Flop
Logic diagrams and truth tables of the different types of flip-flops are as follows:
S-R Flip Flop :
In the flip flop, with the help of preset and clear when the power is switched ON, the states of the circuit
keeps on changing, that is it is uncertain. It may come to set(Q=1) or reset(Q’=0) state. In many applications,
it is desired to initially set or reset the flip flop that is the initial state of the flip flop that needs to be assigned.
This thing is accomplished by the preset(PR) and the clear(CLR).

Convert JK flipflop to SR flipflop.

 S-R Flip Flop
Operations:
Case 1:
PR=CLR=1 The asynchronous inputs are inactive and the flip flop responds freely to the S,R and the CLK
inputs in the normal way.
Case 2:
PR=0 and CLR=1 This is used when the Q is set to 1.
Case 3:
PR=1 and CLR=0 This is used when the Q’ is set to 1.
Case 4:
PR=CLR=0 This is an invalid state.
Characteristics Equation for SR Flip Flop: QN+1 = QNR’ + SR’

Explain the concept of MOD-N counter.

Design Mod – N synchronous Counter
The value of N can be different from power of 2. Also, the counting sequence may be random for example
some cyclic code (8421, 2423 etc). The following method is applied for designing for mod N and any counting
sequence.
Design for Mod-N counter :
The steps for the design are –
Step 1 : Decision for number of flip-flops –
Example : If we are designing mod N counter and n number of flip-flops are required then n can be found out
by this equation.
N <= 2n
Here we are designing Mod-10 counter Therefore, N= 10 and number of Flip flops(n) required is
For n =3, 10<=8, which is false.
For n= 4,10<=16, which is true.
Therefore number of FF required is 4 for Mod-10 counter.
Step 2 : Write excitation table of Flip flops –
Here T FF is used

Excitation table of T FF.

Step 3 : Draw state diagram and circuit excitation table –

 Counting Sequence of Decade counter

A decade counter is called as mod -10 or divide by 10 counter. It counts from 0 to 9 and again reset to 0. It
counts in natural binary sequence. Here 4 T Flip flops are used. It resets after Q 3 Q2 Q1 Q0 = 1001.
Circuit excitation table –
Here Q3 Q2 Q1 Q0 are present states of four flip-flops and Q*3 Q*2 Q*1 Q*0 are next counting state of 4 Flip
flops. If there is a transition in current state i.e if Q3 value changes from 0 to 1 or 1 to 0 then there’s
corresponding T(toggle) bit is written as 1 otherwise 0.

Circuit excitation table

Step 4 : Create Karnaugh map for each FF input in terms of flip-flop outputs as the input variable –
Simplify the K map –

K map for finding minimal expressions.

Step 5 : Create circuit diagram –

Here negative edge triggered clock is used for toggling purpose.
 The clock is provided to every Flip flop at same instant of time.
 The toggle(T) input is provided to every Flip flop according to the simplified equation of K map.
 Circuit diagram

Explain the D flipflop with help of truth table and block diagram.
D Flip Flop
D flip flop is an electronic devices that is known as “delay flip flop” or “data flip flop” which is used to store
single bit of data.D flip flops are synchronous or asynchronous. The clock single required for the
synchronous version of D flip flops but not for the asynchronous one.The D flip flop has two inputs, data
and clock input which controls the flip flop. when clock input is high, the data is transferred to the output of
the flip flop and when the clock input is low, the output of the flip flop is held in its previous state.

Working of D Flip Flop

D flip flop consist of a single input D and two outputs (Q and Q’). The basic working of D Flip Flop is as
follows:
 When the clock signal is low, the flip flop holds its current state and ignores the D input.
 When the clock signal is high, the flip flop samples and stores D input.
 The value that was previously fed into the D input is reflected at the flip flop’s Q output.
 If D = 0 then Q will be 0.
 If D = 1 then Q will be 1.
 The Q’ output of the flip flop is complemented by the Q output.
 If Q = 0 then Q’ will be 1.
 If Q = 1 then Q’ will be 0.

Truth Table of D Flip Flop

Characteristic Table of D Flip Flop
The characteristic table of the D flip flop displays the behavior of the flip flop for each combination of input
and current state. The characteristic table for a D flip flop is as follows.

Characteristics table of D Flip Flop

 D is the input, and Q is current state, Qn + 1 is the next state outputs.
 Qn+1 will always be zero when D is 0, irrespective of current state of flip flop.
 When the input of the flip flop is 1, next state of flip flop will always be 1, regardless of the current state
of flip flop.

Explain with help of a flowchart booth’s algorithm.

Booth’s Algorithm Flowchart –
We name the register as A, B and Q, AC, BR and QR respectively. Qn designates the least significant bit of
multiplier in the register QR. An extra flip-flop Qn+1is appended to QR to facilitate a double inspection of
the multiplier.The flowchart for the booth algorithm is shown below.

Flow chart of Booth’s Algorithm.

AC and the appended bit Qn+1 are initially cleared to 0 and the sequence SC is set to a number n equal to
the number of bits in the multiplier. The two bits of the multiplier in Qn and Qn+1are inspected. If the two
bits are equal to 10, it means that the first 1 in a string has been encountered.

This requires subtraction of the multiplicand from the partial product in AC. If the 2 bits are equal to 01, it
means that the first 0 in a string of 0’s has been encountered. This requires the addition of the multiplicand to
the partial product in AC. When the two bits are equal, the partial product does not change.

An overflow cannot occur because the addition and subtraction of the multiplicand follow each other. As a
consequence, the 2 numbers that are added always have a opposite signs, a condition that excludes an
overflow. The next step is to shift right the partial product and the multiplier (including Qn+1). This is an
arithmetic shift right (ashr) operation which AC and QR to the right and leaves the sign bit in AC unchanged.
The sequence counter is decremented and the computational loop is repeated n times. Product of negative
numbers is important, while multiplying negative numbers we need to find 2’s complement of the number to
change its sign, because it’s easier to add instead of performing binary subtraction. product of two negative
number is demonstrated below along with 2’s complement.

Example – A numerical example of booth’s algorithm is shown below for n = 4. It shows the step by step
multiplication of -5 and -7.
BR = -5 = 1011,
BR' = 0100, <-- 1's Complement (change the values 0 to 1 and 1 to 0)
BR'+1 = 0101 <-- 2's Complement (add 1 to the Binary value obtained after 1's complement)
QR = -7 = 1001 <-- 2's Complement of 0111 (7 = 0111 in Binary)
The explanation of first step is as follows: Qn+1
AC = 0000, QR = 1001, Qn+1 = 0, SC = 4
Qn Qn+1 = 10
So, we do AC + (BR)'+1, which gives AC = 0101
On right shifting AC and QR, we get
AC = 0010, QR = 1100 and Qn+1 = 1
 OPERATION AC QR Qn+1 SC
0000 1001 0 4
AC + BR’ + 1 0101 1001 0
ASHR 0010 1100 1 3
AC + BR 1101 1100 1
ASHR 1110 1110 0 2
ASHR 1111 0111 0 1
AC + BR’ + 1 0100 0111 0
ASHR 0010 0011 1 0

Explain concept of carry look ahead adder.

Carry Look-Ahead Adder
The adder produce carry propagation delay while performing other arithmetic operations like multiplication
and divisions as it uses several additions or subtraction steps. This is a major problem for the adder and hence
improving the speed of addition will improve the speed of all other arithmetic operations. Hence reducing the
carry propagation delay of adders is of great importance. There are different logic design approaches that have
been employed to overcome the carry propagation problem. One widely used approach is to employ a carry
look-ahead which solves this problem by calculating the carry signals in advance, based on the input signals.
This type of adder circuit is called a carry look-ahead adder.
Here a carry signal will be generated in two cases:
1. Input bits A and B are 1
2. When one of the two bits is 1 and the carry-in is 1.
In ripple carry adders, for each adder block, the two bits that are to be added are available instantly. However,
each adder block waits for the carry to arrive from its previous block. So, it is not possible to generate the sum
and carry of any block until the input carry is known. The block waits for the block to produce its carry. So
there will be a considerable time delay which is carry propagation delay.

Consider the above 4-bit ripple carry adder. The sum is produced by the corresponding full adder as soon as
the input signals are applied to it. But the carry input is not available on its final steady-state value until
carry is available at its steady-state value. Similarly depends on and on . Therefore, though the carry must
propagate to all the stages in order that output and carry settle their final steady-state value.
The propagation time is equal to the propagation delay of each adder block, multiplied by the number of adder
blocks in the circuit. For example, if each full adder stage has a propagation delay of 20 nanoseconds,
then will reach its final correct value after 60 (20 × 3) nanoseconds. The situation gets worse, if we extend the
number of stages for adding more number of bits.
Carry Look-ahead Adder :
A carry look-ahead adder reduces the propagation delay by introducing more complex hardware. In this
design, the ripple carry design is suitably transformed such that the carry logic over fixed groups of bits of the
adder is reduced to two-level logic. Let us discuss the design in detail.