Digital System Design Using Verilog�(21EC32)

Lesson Plan

2

Combinational Circuits

• Combinational circuit is a feed forward circuit that consists of combination of gates.

​

To Design a combinational circuit the following steps are followed

1. State the given problem completely and exactly
2. Interpret the problem, and determine the available input variables and required output variables.
3. Assign a letter symbol to each input and output variables.
4. Design the truth table, which defines the required relations between inputs and outputs.
5. Obtain the simplified Boolean expression for each output using k-maps.
6. Draw the logic circuit diagram to implement the Boolean expression.

​

3

Combinational Circuits

• Design a combinational circuit which has 3-bit input number and a single output (F). The

output signal F is specified as follows:

• F = 1 when the input number is less than (3)

• F = 0 otherwise.

• Implement F using only NAND gates

4

Combinational Circuits

• Let the three inputs be called X, Y, and Z.
• X is the most significant variable and Z is the least significant variable. The output F goes high, that is, the output produces logic 1 value if the input is less than 011, equivalent to a decimal value of three. This means that the output will be logic one for input combinations 000, 001, and 010.
• For other input combinations, which are 011 upto 111, the output is logic zero.

​

5

Binary Adder

• Basic building blocks of all arithmetic circuits are ADDERS.
• It adds two binary numbers and gives out sum and carry-out as outputs.
• Divided into two categories 1.Half adder 2.Full-adder

6

Half Adder

• Adding two single-bit binary values, X, Y produces a sum S bit and a carry out C-out bit.
• This operation is called half addition and the circuit to realize it is called a half adder.

​

7

S(X,Y) = Σ (1,2)

S = X’Y + XY’

S = X ⊕ Y

​

C-out(x, y, C-in) = Σ (3)

C-out = XY

X

Y

Sum S

C-out

Full Adder

• Adding two single-bit binary values, X, Y with a carry input bit C-in produces a sum bit S and a carry out C-out bit.

8

Full Adder Truth Table

S(X,Y, C-in) = Σ (1,2,4,7)

C-out(x, y, C-in) = Σ (3,5,6,7)

Inputs

Outputs

S = X’Y’(C-in) + XY’(C-in)’ + XY’(C-in)’ + XY(C-in)

S = X ⊕ Y ⊕ (C-in)

C-out = XY + X(C-in) + Y(C-in)

Full Adder Circuit Using AND-OR

9

Full Adder Circuit Using XOR

10

Binary parallel Adder

11

Adds two 4-bit numbers:

X = X3 X2 X1 X0

Y = Y3 Y2 Y1 Y0

producing the sum S = S3 S2 S1 S0 ,

C-out = C4 from the most significant

position j=3

Look-Ahead Carry Binary Adders

• Main disadvantage of four bit adder is that higher order bit operation can be performed only if carry out from lower order bit occurs.Hence it takes n-time’s propagation delay of full adder to complete n-bit addition.This delay can be overcome by look-ahead carry adder.
• Carry look-ahead adders use a different method to create the needed carry bits for each full adder with a lower constant delay equal to three gate delays.
• The carry out C-out from the full adder at position i or C_j+1 is given by:

C-out = C _i+1 = X_i . Y_i + (X_i + Y_i) . C_i

• By defining:
• G_i = X_i . Y_i as the carry generate function for position i (one gate delay) (If G_i =1 C _i+1 will be generated regardless of the value C_i)
• P_i = X_i + Y_i as the carry propagate function for position i (one gate delay) (If P_i = 1 C_i will be propagated to C _i+1)
• By using the carry generate function G_i and carry propagate function P_i , then C _i+1 can be written as:

C-out = C _i+1 = G_i + P_i . C_i

• To eliminate carry ripple the term C_i is recursively expanded and by multiplying out, we obtain a 2-level AND-OR expression for each C _i+1

12

Carry Look-Ahead Adders

• For a 4-bit carry look-ahead adder the expanded expressions for all carry bits are given by:

C₁ = G₀ + P₀.C₀

​

C₂ = G₁ + P₁.C₁ = G₁ + P1.G₀ + P₁.P₀.C₀

​

C₃ = G₂ + P₂.G₁ + P₂.P₁.G₀ + P₂.P₁.P₀.C₀

​

C₄ = G₃ + P₃.G₂ + P₃.P₂.G₁ + P₃ . P₂.P₁.G₀ + P₃.P₂.P₁.P₀.C₀

​

where G_i = X_i . Y_i P_i = X_i + Y_i

​

• The additional circuits needed to realize the expressions are usually referred to as the carry look-ahead logic.
• Using carry-ahead logic all carry bits are available after three gate delays regardless of the size of the adder.

​

13

Carry Look-Ahead Circuit

14

C_i = G_i-1 + P_i-1. G_i-2 + …. + P_i-1.P _i-2. …P₁ . G₀ + P _i-1.P _i-2. …P₀ . C₀

Binary Arithmetic Operation: Subtraction

• Two binary numbers are subtracted by subtracting each pair of bits together with borrowing, where needed.
• Subtraction Example:

​

0 0 1 1 1 1 1 0 0 Borrow

X 229 1 1 1 0 0 1 0 1

Y - 46 - 0 0 1 0 1 1 1 0

183 1 0 1 1 0 1 1 1

15

Half Subtractor

• Subtracting a single-bit binary value Y from anther X (I.e. X -Y ) produces a difference bit D and a borrow out bit B-out.
• This operation is called half subtraction and the circuit to realize it is called a half subtractor.

​

16

D(X,Y) = Σ (1,2)

D = X’Y + XY’

D = X ⊕ Y

​

B-out(x, y, C-in) = Σ (1)

B-out = X’Y

X

Y

Difference D

B-out

Full Subtractor

• Subtracting two single-bit binary values, Y, B-in from a single-bit value X produces a difference bit D and a borrow out B-out bit. This is called full subtraction.

17

Full Subtractor Truth Table

S(X,Y, C-in) = Σ (1,2,4,7)

C-out(x, y, C-in) = Σ (1,2,3,7)

Inputs

Outputs

1

1

1

1

Borrow B-out

S = X’Y’(B-in) + XY’(B-in)’ + XY’(B-in)’ + XY(B-in)

S = X ⊕ Y ⊕ (C-in)

B-out = X’Y + X’(B-in) + Y(B-in)

Full Subtractor Circuit Using AND-OR

18

Full Subtractor Circuit Using XOR

19

Difference D

n-bit Subtractors

An n-bit subtracor used to subtract an n-bit number Y from another

n-bit number X (i.e X-Y) can be built in one of two ways:

​

• By using n full subtractors and connecting them in series, creating a borrow ripple subtractor:
• Each borrow out B-out from a full subtractor at position j is connected to the borrow in B-in of the full subtracor at the higher position j+1.

​

• By using an n-bit adder and n inverters:
• Find two’s complement of Y by:
• Inverting all the bits of Y using the n inverters.
• Adding 1 by setting the carry in of the least significant position to 1
• The original subtraction (X - Y) now becomes an addition of X to two’s complement of Y using the n-bit adder.

​

20

4-bit Borrow Subtractor

21

Subtracts two 4-bit numbers:

Y = Y3 Y2 Y1 Y0 from

X = X3 X2 X1 X0

Y = Y3 Y2 Y1 Y0

producing the difference D = D3 D2 D1 D0 ,

B-out = B4 from the most significant

position j=3

4-bit Subtractor Using 4-bit Adder

22

4-bit

Adder

X3 X2 X1 X0

D3 D2 D1 D0

C-in

C-out

C4

Y3 Y2 Y1 Y0

C0 = 1

Inputs to be subtracted

Difference Output

S3 S2 S1 S0

Comparator-one bit

23

Decoders

• A decoder is a multiple-input, multiple-output logic circuit that converts coded inputs into coded outputs, where the input and output codes are different. e.g. n-to-2ⁿ, BCD decoders.

​

• Enable inputs must be on for the decoder to function, otherwise its outputs assume a single “disabled” output code word.

24

Binary n-to-2ⁿ Decoders

• A binary decoder has n inputs and 2ⁿ outputs.
• Only the output corresponding to the input value is equal to 1.

25

2-to-4 Binary Decoder

• From truth table, circuit for 2x4 decoder is:
• Note: Each output is a 2-variable minterm (X'Y', X'Y, XY' or XY)

26

Truth Table:

2-to-4

Decoder

X

Y

F0

​

F1

​

F2

​

F3

3:8 Decoder

27

A

B

C

O₀

O₁

O₂

O₃

O₄

O₅

O₆

O₇

0

0

0

1

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

0

1

1

0

0

0

0

0

0

0

1

0

1

1

1

0

0

0

0

0

0

0

1

3:8 Decoder

28

3-to-8 Binary Decoder

29

Truth Table:

3-to-8

Decoder

X

Y

F0

​

F1

​

F2

​

F3

​

F4

​

F5

​

F6

​

F7

Z

Encoders

• If the a decoder's output code has fewer bits than the input code, the device is usually called an encoder.

e.g. 2ⁿ-to-n, priority encoders.

​

• The simplest encoder is a 2ⁿ-to-n binary encoder, where it has only one of 2ⁿ inputs = 1 and the output is the n-bit binary number corresponding to the active input.

​

• For an 8-to-3 binay encoder with inputs I0-I7 the logic expressions of the outputs Y0-Y2 are:

​

Y0 = I1 + I3 + I5 + I7

Y1= I2 + I3 + I6 + I7

Y2 = I4 + I5 + I6 +I7

30

8-to-3 Binary Encoder

31

​

​

At any one time, only

one input line has a value of 1.

0

0

0

0

0

0

0

1

0

0

1

0

1

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

0

0

1

1

1

1

Multiplexers

• A multiplexer (MUX) is a digital switches which connects data from one of n sources to the output.
• A number of select inputs determine which data source is connected to the output.

32

2:1 Multiplexer and 4:1 Multiplexer

Truth table for a 4-to-1 multiplexer and 2:1 Multiplexer

33

4-to-1 MUX Circuit

34

Larger Multiplexers

• Larger multiplexers can be constructed from smaller ones.
• An 8-to-1 multiplexer can be constructed from smaller multiplexers as shown:

35

Demultiplexers

• Digital switches to connect data from one input source to one of n outputs.
• Usually implemented by using n-to-2ⁿ binary decoders where the decoder’s enable line is used for data input of the demultiplexer.

36

1-bit 4-output demultiplexer using

a 2x4 binary decoder.

1-to-4 Demultiplexer

37

38

PLDs (Programmable Logic Devices)

General Structure of PLD

• Inputs to the PLD are applied to a set of buffer/inverters. These devices have both the true value of the input as well as the complemented value of the input as its outputs.
• Outputs from these devices are the inputs to an array of and-gates. The AND array generates a set of p product terms.
• The product terms are inputs to an array of or-gates to realize a set of m sum-of-product expressions.

39

General Structure of PLD

40

General Structure of PLD

• One or both of the gate arrays are programmable.
• The logic designer can specify the connections within an array.
• PLDs serve as general circuits for the realization of a set of Boolean functions.

​

​

​

​

​

41

Programming a PLD

42

Programming a PLD

• Erasable PLD—connections can be reset to their original conditions and then reprogrammed.
• Can be achieved by exposing the PLD to ultraviolet light or using electrical signals
• PLDs programmed by a user are called field programmable.
• User can also specify the desired connections and supply the information to the manufacturer. Manufacturer prepares an overlay that is used to complete the connections as the last step in the fabrication process.
• Such PLDs are called mask programmable.

43

PLD Notation

• Simplified notation. Each gate has only a single input line.
• Inputs are indicated by lines at right angles to the single gate lines.
• A cross at the intersection denotes a fusible link is intact.

44

PLD Notation

• Lack of cross indicates the fuse is blown or no connection exists.

​

45

PLD Notation

• The occurrence of a hard-wired connection that is not fusible is indicated by a junction dot.

​

​

​

​

​

• For the special case when all the input fuses to a gate are kept intact, a cross is placed inside the gate symbol.

46

Programmable Read-Only Memory (PROM)

47

PROM Structure

48

Logic Diagram

PROM Structure

49

PLD Notation

Example

50

Why is it called PROM?

51

Programmable Logic Array

52

Programmable Logic Array

53

Programmable Logic Array

54

PROM vs PLA

• PROM: realization of a set of Boolean functions is based on minterm canonical expressions.
• No minimization necessary.
• PLA: the AND gates are capable of generating product terms that are not necessarily minterms.
• Realization using PLA is based on sum-of-product expression that may not be canonical.
• Logic designer is bounded by the number of product terms that are realizable by the AND-array.
• Simplifications is necessary.

55

Logic Design Example

56

Logic Design Example

57

Logic Design Example

58

Additional Features

• For greater flexibility, PLAs make provision for either a true output or a complemented output.

59

Example of Use of Complemented Functions

60

Example of Use of Complemented Functions

61

PLA Table

• A common way of specifying the connections in a PLA.
• 3 sections: input section, output section, T/C section.
• Each product term is assigned a row in the table.
• Input section indicates connections between inputs to AND-array.
• Output section indicates connections between outputs of AND-array and inputs to the OR-array.
• T/C section indicates how the exclusive or gates are programmed.
• T—true output is used.
• C—output should be complemented.

​

​

​

​

​

62

Programmable Array Logic (PAL) Devices

• OR-array is fixed by the manufacturer of the device.
• PAL device is easier to program and less expensive than the PLA.
• Less flexible.

​

​

​

​

​

​

​

​

​

​

​

63

Example of Logic Design with PAL

64

Example of Logic Design with PAL

65

University Questions

• Define priority encoder with three inputs with middle bit at highest priority encoding to 10 most significant bit at next priority encoding to 11 and least significant at least priority encoding 01. 10M
• Define multiplexer and demultiplexer and draw block diagram. 04M
• Design 4:1 Multiplexer draw the circuit using gates. 06M
• Explain how will you implement the following function using implementation table,

F(A,B,C,D)=Σm(0,1,3,4,7,10,12,14) with A,B,C select lines. 10M

• Design Magnitude comparator .Design a two bit binary comparator and implement with suitable logic gates. 08M
• Design a binary full adder using only two input NAND gates. Write its truth table. 06M
• Implement the following boolean function using 4:1 multiplexer Y=f(A,B,C,D)=Σm(0,1,2,4,6,9,12,14) 06M

66

Assignment Questions

• Design a combinational circuit so that output is generated when majority of four inputs is false.
• Draw Half adder using only Nand gates and only Nor gates.
• Design full subtractor by cascading Half-Subtractors.
• Implement the following function by means of the decoder and fundamental gates F=πM(0,1,4,5)
• Implement full adder circuit using decoder and OR gates.
• Construct 1:16 demultiplexer using 1:4 demultiplexer and 2:4 line decoder.
• Implement Σm(2,4,5,7,9,14) Using Mux.

67