Unit2/lecture1

Introduction:

A logic gate is an arrangement of controlled switches used to calculate operations using Boolean logic in digital circuits. They are primarily implemented electronically but can also be constructed using electro- magnetic relays, electronic diodes, fluidics, optical or even mechanical elements.

Logic:

• Formal logic is a branch of mathematics that deals with true and false values instead of numbers.

• In the mid-19th century, George Bool developed many Logic ideas.

• Boolean logic deals with equations where the operators are “AND” or “OR” instead of “add” and “multiply”.

Electric Logic:

• Logical values can easily be expressed by an electrical circuit.

• “True” or “1” can be defined as voltage on a wire while “False” or “0” can be defined as  no voltage. We will use positive logic.

• Analog values can be anything while digital Analog values can be anything while digital only has discrete values,           0 or 1

• Electrical devices called “gates” can implement the logical.

Logic Gates & Symbols:

Note that gates can have more than 2 inputs

AND gate:

• The AND gate is an electronic circuit that gives a gives a true output (1) only if (1) only if all its inputs its inputs are true. A dot (·) is used to show the AND operation i.e. A·B. Note that the dot is sometimes omitted i.e. AB.

Inputs and Outputs:

• The inputs can be considered as logical (true or false) values.

• You can also think of the inputs as voltage (true) or ground (false).

• The output of the gate will also be voltage (true) or ground (false) (true) or ground (false).

OR gate:

• The OR gate is an electronic circuit that  gives a true output (1) if one or more of its inputs are true. A plus (+) is used to show the OR operation.

NOT gate:

• The NOT gate is an electronic circuit that produces an inverted version of the input at its output.

• It is also known as an inverter.

• If the input variable is A, the inverted output is known as NOT A.

• This is also shown as A', or Ā with a bar over the top.

TRUTH TABLE:

NAND gate:

• This is a NOT-AND gate which is equal to an AND gat f ll d b te followed by a NOTGate.

• The outputs of all NAND gates are true if any of the inputs are false.

• The symbol is an AND gate with a small circle on the output. The small circle represents inversion.

Truth Table:

Logical Equivalence:

• A NAND gate gives the same results as an AND gate feeding into a NOT gate.

• Circuits are logically equivalent if they produce the same truth table output.

NAND as a NOT:

• Below are two ways that a NAND gate can b fi d t d be configured to produce a NOTgate. They are logically  equivalent.

• It can also be done using NOR logic gates in the same way.

NOR gate:

• This is a NOT-OR gate which is equal to an OR gate followed by a NOT gate.

• The outputs of all NOR gates are false if any of the inputs are true.

• The symbol is an OR gate with a small circle on the output. The small circle represents inversion.

EXOR gate:

• The 'Exclusive-OR' gate is a circuit which will  give a t true output if either, but not both, of its two inputs are true.

• An encircled plus sign ( ) is used to show the EOR operation.

EXNOR gate:

• The 'Exclusive-NOR' gate circuit does the opposite to the EOR gate.

• It will give a false output if either, but not both, of its two inputs are true.

• The symbol is an EXOR gate with a small circle on the output small circle on the output.

• The small circle represents inversion.

EXNOR gate cont.:

Logic gate symbols:

Truth Table:

• Logic gates representation using the truth table

NOR Inverter:

• Wiring the NOR gate to become an inverter.

Three Input AND Gate:

 • Here is an example of a three input AND gat e.

• Notice that the truth table for the three input gate is similar to the truth table for the two input gate.

• It works on the same principle this It works on the same principle, this time all three inputs need to be true

   (1)to get a true output.

Three Input AND Gate Cont.

Four Input AND Gate:

• Here is an example of a four input AND gate.

• It also works on the same principle, all four inputs need to be true (1) to \get a true output.

• The same principles apply to 5 6 n The same principles apply to 5, 6,..., n  input gates.

Four Input AND Gate cont.

Two, Three, and Four OR gates:

Connecting Gates:

• The output of one logic gate can be used as the input to another logic gate.

• The output of one gate can be used as the inputs to several other gates.

UNIT II / LECTURE 2

UNIVERSAL GATES

NAND and NOR are universal gates:-

Any function can be implemented using only NAND or only NOR gates. How can we prove this?

(Proof for NAND gates) Any boolean function can be implemented using AND, OR and NOT gates.

So if AND, OR and NOT gates can be implemented using NAND gates only, then we prove our point.

    In practice, this is advantageous since NAND and NOR gates are economical and easier to fabricate and are the basic gates used in all IC digital logic families.

    In fact, an AND gate is typically implemented as a NAND gate followed by an inverter not the other way around!!

    Likewise, an OR gate is typically implemented as a NOR gate followed by an inverter not the other way around.

 1.Implement NOT using NAND:

2. Implementation of AND using NAND

3. Implementation of OR using NAND

Additional properties of XOR:-

A(+) B = 1 only when there are an 0 0 1 1 odd number of 1’s in (A,B). The 0 1 0 1 same is true for A(+) B(+) C  also.

NOR GATE IMPLEMENTATION

NOT GATE USING NOR GATE

This is made by joining the inputs of a NOR gate. As a NOR gate is equivalent to an OR gate leading to NOT gate, this automatically sees to the "OR" part of the NOR gate, eliminating it from consideration and leaving only the NOT part.

OR GATE USING NOR GATE

The OR gate is simply a NOR gate followed by another NOR gate.

AND IMPLEMENTATION USING NOR

An AND gate gives a 1 output when both inputs are 1; a NOR gate gives a 1 output only when both inputs are 0. Therefore, an AND gate is made by inverting the inputs to a NOR gate.

NAND USING NOR GATE

A NAND gate is made using an AND gate in series with a NOT gate:

XOR USING NOR GATE

An XOR gate is made by connecting the output of 3 NOR gates (connected as an AND gate) and the output of a NOR gate to the respective inputs of a NOR gate. This expresses the logical fomula (A AND B) NOR (A NOR B). This construction entails a propagation delay three times that of a single NOR gate.

UNIT-II/LECTURE 3

Half Adder:-

Half adder is a combinational log ic circuit with two inputs and two outputs. The half adder circuits designed to add two sing le 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

K-MAP IMPLEMENTATION

SUM

SUM= AB’ + A’B

CARRY

CARRY = A and B

Full Adder : [ DEC 2014(3)]

 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 Subtractor:

   A half subtractor is an arithmetic circuit that subtracts two bits and produces their

Difference.

The block diagram of half subtractor is shown. The circuit has two inputs minuend

(X) and subtrahend (Y) and two output bits, one is the difference bit (D) and the other

is the borrow bit (B).

It performs the operation X – Y.

It should be noted that the weight of the output borrow bit is -2, while the weight of

the output difference bit is +1

The truth table of the half subtractor is shown. The Boolean functions for the two

outputs can be obtained directly from the truth table as:

UNIT 2/LECTURE 4

Full Subtractor:

A full subtractor is a combinational circuit that performs a subtraction between two bits, taking into account that a 1 may have been borrowed by a lower significant bit.

The block diagram of full subtractor is shown. The circuit has three inputs and two

Outputs.

Input variables are minuend (X), subtrahend (Y), and previous borrow (Z); output

variables are difference (D) and output borrow (B).

It performs the operation X – Y – Z.

It should be noted that the weight of the output borrow bit is -2, while the weight of

the output difference bit is +1.

The truth table of the full subtractor is shown.

The simplified Boolean functions for the two outputs are:

The Full Adder is capable of adding only two single digit binary number along with a carry input. But in practical we need to add binary numbers which are much longer than just one bit. To add two n-bit binary numbers we need to use the n-bit parallel adder. It uses a number of full adders in cascade. The carry output of the previous full adder is connected to carry input of the next full adder.

4 Bit Parallel Adder

In the block diagram, A₀ and B₀ represent the LSB of the four bit words A and B. Hence Full Adder-0 is the lowest stage. Hence its C_in has been permanently made 0. The rest of the connections are exactly same as those of n-bit parallel adder is shown in fig. The four bit parallel adder is a very common logic circuit.

Block diagram

In general, an n-bit binary parallel adder can be built out of n full adders connected in cascade. Since a carry of 1 may appear near the least significant bit of the adder and yet  propagate through many full adders to the most significant bit, just as a wave ripples  outward from a pebble dropped in a pond. That is why this parallel adder is also  called as ripple carry adder.The disadvantage of the ripple-carry adder is that it can get very slow when one needs to add many bits.

N-Bit Parallel Subtractor

The subtraction can be carried out by taking the 1's or 2's complement of the number to be subtracted. For example we can perform the subtraction (A-B) by adding either 1's or 2's complement of B to A. That means we can use a binary adder to perform the binary subtraction.

4 Bit Parallel Subtractor

The number to be subtracted (B) is first passed through inverters to obtain its 1's complement. The 4-bit adder then adds A and 2's complement of B to produce the subtraction. S₃ S₂ S₁ S₀ represent the result of binary subtraction (A-B) and carry output C_out represents the polarity of the result. If A > B then Cout =0 and the result of binary form (A-B) then C_out = 1 and the result is in the 2's complement form.

Block diagram

UNIT 2/ LECTURE 5

Multiplexers [ DEC 2014(2)]

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 Demultiplexers 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 come in multiple variations

·         1 : 2 demultiplexer

·         1 : 4 demultiplexer

·         1 : 16 demultiplexer

·         1 : 32 demultiplexer

Block diagram

Truth Table

Q. Implement the function using a minimal network of 4:1 multiplexers. The truth table using a,b as the selection signals:

Q2. Design a full adder with a minimal number of 2:1 multiplexers (no other gates). Draw the schematic diagram.

Sol:- Truth table of full adder

Truth table for s, using a ,b as the selection signals:

Truth table for co , using a ,b as the selection signals:

Fig: Implementation of full adder using 2X1 multiplexer

UNIT2/LECTURE 6

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

2 to 4 Line Decoder

The block diagram of 2 to 4 line decoder is shown in the fig. A and B are the two inputs where D through D are the four outputs. Truth table explains the operations of a decoder. It shows that each output is 1 for only a specific combination of inputs.

Block diagram

Truth Table

Logic Circuit

SO... can use to synthesise all logic functions of n variables!!

E.g. Realise F=ΣX,Y(0,3) using a 2-4 decoder [Dec 2014(7)]

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

Priority Encoder

This is a special type of encoder. Priority is given to the input lines. If two or more input line are 1 at the same time, then the input line with highest priority will be considered. There are four input D₀, D₁, D₂, D₃ and two output Y₀, Y₁. Out of the four input D₃ has the highest priority and D₀ has the lowest priority. That means if D₃ = 1 then Y₁ Y₁ = 11 irrespective of the other inputs. Similarly if D₃ = 0 and D₂ = 1 then Y₁ Y₀ = 10 irrespective of the other inputs.

Block diagram

Truth Table

Logic Circuit

                                                           UNIT 2/LECTURE 8

  BCD Adder[Dec 2014(7)]

• When the sum of two digits is less than or equal to 9 then the ordinary 4-bit adder can be used.

• But if the sum of two digits is greater than 9 then a correction must be added “I.e adding 0110”.

• We need to design a circuit that is capable of doing the correct addition.

 The cases where the sum of two 4-bit numbers is greater than 9 are in the following

table:

• Whenever S4=1 (sums greater than 15)

• Whenever S3=1 and either S2 or S1 or both are

1 (sums 10 to 15)

• The previous table can be expressed as: X = S4 + S3( S2 + S1)

So, whenever X = 1 we should add a correction of 0110 to the sum.

Inputs:[A]=0101, [B]= 0011, Co=0

     Cascading BCD Adders:

• The previous circuit is used for adding two decimal digits only. That is, “ 7 + 6 = 13”.

• For adding numbers with several digits, a separate  BCD adder for each digit position must be used

• For example:

                                                                     Example

      • Determine the inputs and the outputs when the above circuit is used to add 538 to 247.

        Assume a CARRY IN = 0

     • Solution:

                       – Represent the decimal numbers in BCD

                                247 = 0010 0100 0111

                                538 = 0101 0011 1000

                         Put these numbers in registers [A] and [B]

                                [A] = 0010 0100 0111

                                [B] = 0101 0011 1000

UNIT 2/LECTURE 9

Look-ahead carry generator:-

  In ripple carry adders, the carry propagation time is the major speed limiting factor

Most other arithmetic operations, e.g. multiplication and division are implemented using

Several add/subtract steps. Thus, improving the speed of addition will improve the speed

of all other arithmetic operations.

Accordingly, reducing the carry propagation delay of adders is of great importance.

Different logic design approaches have been employed to overcome the carry

Propagation problem.

One widely used approach employs the principle of carry look-ahead solves this problem

by calculating the carry signals in advance, based on the input signals.

This type of adder circuit is called as carry look-ahead adder (CLA adder). It is based on

the fact that a carry signal will be generated in two cases:

The Figure shows the full adder circuit used to add the operand bits in the ith column;

namely Ai & Bi and the carry bit coming from the previous column (Ci ).

In this circuit, the 2 internal signals Pi and Gi are given by:

Pi = Ai ⊕Bi ……………………..(1)

Gi = AiBi ……………….……(2)

The output sum and carry can be defined as :

i Pi Ci S = ⊕ ……………………(3)

Ci +1 = Gi + PiCi …………(4)

Gi is known as the carry Generate signal since a carry (Ci+1) is generated whenever Gi

=1, regardless of the input carry (Ci).

Pi is known as the carry propagate signal since whenever Pi =1, the input carry is

propagated to the output carry, i.e., Ci+1. = Ci (note that whenever Pi =1, Gi =0).

Computing the values of Pi and Gi only depend on the input operand bits (Ai & Bi) as

clear from the Figure and equations.

Thus, these signals settle to their steady-state value after the propagation through their

respective gates.

Computed values of all the Pi’s are valid one XOR-gate delay after the operands A and B

are made valid.

Computed values of all the Gi’s are valid one AND-gate delay after the operands A and B

The Boolean expression of the carry outputs of various stages can be written as follows:

C1 = G0 + P0C0

C2 = G1 + P1C1 = G1 + P1 (G0 + P0C0)

 = G1 + P1G0 + P1P0C0

C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0

C4 = G3 + P3C3

 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0

In general, the ith. carry output is expressed in the form Ci = Fi(P’s, G’s , C0).

In other words, each carry signal is expressed as a direct SOP function of C0 rather than

its preceding carry signal.

Since the Boolean expression for each output carry is expressed in SOP form, it can be

implemented in two-level circuits.

The 2-level implementation of the carry signals has a propagation delay of 2 gates, i.e.,

2τ.

The 4-bit carry look-ahead (CLA) adder consists of 3 levels of logic:

First level: Generates all the P & G signals. Four sets of P & G logic (each consists of an

XOR gate and an AND gate). Output signals of this level (P’s & G’s) will be valid after

1τ.

Second level: The Carry Look-Ahead (CLA) logic block which consists of four 2-level

implementation logic circuits. It generates the carry signals (C1, C2, C3, and C4) as

defined by the above expressions. Output signals of this level (C1, C2, C3, and C4) will be

valid after 3τ.

Third level: Four XOR gates which generate the sum signals (Si) (Si = Pi ⊕ Ci). Output

signals of this level (S0, S1, S2, and S3) will be valid after 4τ.

Thus, the 4 Sum signals (S0, S1, S2 & S3) will all be valid after a total delay of 4τ compared to a delay of (2n+1)τ for Ripple Carry adders.

For a 4-bit adder (n = 4), the Ripple Carry adder delay is 9τ.

The disadvantage of the CLA adders is that the carry expressions (and hence logic)

become quite complex for more than 4 bits.

Thus, CLA adders are usually implemented as 4-bit modules that are used to build larger

size adders.

BCD- to-Gray Code Converter