Digital Principles and System Design

NH – 67, Karur – Trichy Highways, Puliyur C.F, 639 114 Karur District

DEPARTMENT OF INFORMATION TECHNOLOGY

CS 2202 DIGITAL PRINCIPLES AND SYSTEM DESIGN

*The NPTEL material on digital circuits for the IT branch-3rd Semester is available here.

UNIT 1

BOOLEAN ALGEBRA AND LOGIC GATES

Review of binary number systems – Binary arithmetic – Binary codes – Boolean algebra and theorems – Boolean functions – Simplification of Boolean functions using Karnaugh map and tabulation methods – Logic gates

INTRODUCTION

The world of electronics is divided into two areas: analog and digital. Analog circuits consist mainly of amplifiers for voltage or current variations that are smooth and continuous.

Digital circuits provide electronic switching of voltage pulses. A pulse has abrupt changes between two extreme amplitude levels (i.e.: 5 volt = high level and 0 volt = low level).

Since the digital signal has only two significant levels, either high or low, it is useful to represent the pulses in a binary number system with the digits 1 and 0.

Digital electronics are electronics systems that use digital signals. Digital electronics are used in computers, mobile phones, and other consumer products.

Digital electronics or any digital circuits are usually made from large assemblies of logic gates, simple electronic representations of Boolean logic functions.

Advantages of digital system

1. Digital systems interface well with computers and are easy to control with software. New features can often be added to a digital system without changing hardware. Often this can be done outside of the factory by updating the product's software. So, the product's design errors can be corrected after the product is in a customer's hands.

2. Information storage can be easier in digital systems than in analog ones. The noise-immunity of digital systems permits data to be stored and retrieved without degradation. In an analog system, noise from aging and wear degrade the information stored. In a digital system, as long as the total noise is below a certain level, the information can be recovered perfectly.

1.1 NUMBER SYSTEM

There are four important number systems which you should become familiar with. These are decimal, binary, octal and hexadecimal. The decimal system, which is the one you are most familiar with, utilizes ten symbols to represent each digit. These are 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. This system is referred to as base 10, or radix 10 system. Similarly, the binary system is base 2, octal is base 8, and hexadecimal is base 16 as shown in the following Table

Number System / Radix / Symbols
Binary / 2 / 0 1
Octal / 8 / 0 1 2 3 4 5 6 7
Decimal / 10 / 0 1 2 3 4 5 6 7 8 9
Hexadecimal / 16 / 0 1 2 3 4 5 6 7 8 9 A B C D E F

Table below shows an example of counting from 0 to 18 in each of the four number systems.

Decimal / Binary / Octal / Hexadecimal
0 / 0000 / 0 / 0
1 / 0001 / 1 / 1
2 / 0010 / 2 / 2
3 / 0011 / 3 / 3
4 / 0100 / 4 / 4
5 / 0101 / 5 / 5
6 / 0110 / 6 / 6
7 / 0111 / 7 / 7
8 / 1000 / 10 / 8
9 / 1001 / 11 / 9
10 / 1010 / 12 / A
11 / 1011 / 13 / B
12 / 1100 / 14 / C
13 / 1101 / 15 / D
14 / 1110 / 16 / E
15 / 1111 / 17 / F
16 / 10000 / 20 / 10
17 / 10001 / 21 / 11
18 / 10010 / 22 / 12

Number Conversion

Working in binary can become very cumbersome and prone to errors. It is important to learn how to convert from one system to another. Let us take the binary pattern 1011101 as an example. If we are working predominantly in the octal system, we would break this into groups of three bits, starting from the right

1011101 = 1 011 101 = 1358

The subscript 8 is used to indicate that it is the octal representation. After converting to octal, the conversion to base 10 is simplified.

Mathematically, the decimal value can be computed as (1 × 82) + (3 × 81) + (5 × 80) = 93. However, in a computer program it would be more efficient to use an iterative algorithm. Thus the result is computed as:

((1 × 8) + 3) × 8 + 5 = 93.

Conversion to Binary

Converting an octal or hexadecimal number to its binary representation is straight forward. For example:

3618 = 011 110 0012

1A416 = 0001 1010 01002

Converting a decimal number to its binary representation is slightly more complex. It is simplified if you convert the decimal number to its octal or hexadecimal equivalent first. For example, let us find the binary representation of 144910. First, we shall convert it to its octal representation.

1.2 Binary number system

The native language of digital computers is inherently binary. Thus, numbers are naturally represented as binary integers by the computer. The range of numbers which can be represented is dependent on the number of bits used. A common unit of storage is a byte which is a group of eight bits. Eight bits can represent 28 unique states, i.e. 256 possible combinations. This fact can be used to our advantage to represent many different things on the computer. For example, a byte can be used to represent 256 colours, 256 shades of grey, 256 shapes, 256 symbols, 256 names, or even 256 different numbers. More typically, we can use a byte to represent 256 sequential numbers such as the numbers from 1 to 256, or the numbers from 0 to 255. Remember that 0 is not "nothing" and has equal significance as any other number.

Signed Integers

One of the eight bit is reserved to indicate the sign of the number. Following usual convention, the left-most bit (called the most significant bit or MSB) is dedicated as the sign bit. For the numbers from -128 to 127, there are 256 unique numbers in this range. With this scheme, we can now have 128 positive and 128 negative numbers, typically the numbers from 0 to 127. This scheme has the anomaly that there are two unique representations for positive and negative zero. A more serious problem is that the rules of binary arithmetic breakdown when we decrement by 1 from positive to negative numbers.

To overcome the discontinuity at zero, a scheme of complementary binary is used whereby negative numbers are represented by the binary complement of the positive representation. This system is called one's complement binary. This system also has two unique representations for positive and negative zero. The two's complement binary system overcomes both problems mentioned above. In this notation, the negative number is represented by forming the binary complement of the positive number and adding one.

To summarize, integers are commonly represented by the unsigned binary and the 2's complement binary representations. The range of integer numbers can be extended by utilizing more bits. For example, 16 bits will allow us to represent 216 unique items, i.e. 65536 possible states. These can be the numbers from 0 to 65535 for unsigned integers or -32768 to 32767 for 2's complement signed integers

00011001 ------ +25

10011001 ------ -25 SIGN- MAGNITUDE form

11100110 ------ -25 1s compliment form

11100111 ------ -25 2s compliment form

1.3 Binary Arithmetic

It shows the way in which the manipulation of bits inside the logic units or devices being carried out.

Binary Addition

The rules for binary integer arithmetic follow the same rules as for decimal numbers.

1+0 = 1

1+1 = 10 Sum = 0 ; Carry = 1

1+1+1 = 11 Sum = 1 ; Carry = 1

Binary Subtraction

0-0= 0

1-1 = 0

1-0 = 1

0-1 = 1 Borrowing 1 makes 0 to 10.

(Ex)

Binary Multiplication

Usually, two other logic functions, left shift and right shift, are provided since these are also easy to implement in hardware. When a number is shifted by one digit to the left, for example, 123 left shifted becomes 1230, this is equivalent to multiplying the number by the radix, whatever it may be. Similarly, 123 shifted to the right is 12.3 and this is the same as dividing by the radix. In binary, shifting left by one bit is equivalent to multiplying by 2. Shifting right by one bit is the same as dividing by 2.

To find 2941 x 318, the first number is called the multiplicand and the second is the multiplier, there are two ways depending on which end of the multiplier we begin with. The following should look familiar:

2941
× 318
2941 × 8 = / 23528
29410 × 1 = / 29410
294100 × 3 = / 882300
935238

A less familiar method is the following where we start with the left digit of the multiplier:

2941 × 3 = / 8823 / × 100 = / 882300
2941 × 1 = / 2491 / ×10 = / 24910
2941 × 8 = / 23528 / × 1 = / 23528
935238

In both cases, the product can be formally stated as the sum of partial products as follows:

2941 × 318 = (2941 × 3 × 102 ) + (2941 × 1 × 101 ) + (2941 × 8 × 100 )

Multiplication in binary (or any other radix) can be performed using the same technique as for decimal. Both methods shown are easily implemented in binary on a digital computer. In the examples shown above, the partial products are first formed and the summation is done at the end. In a computer algorithm this is not the usual case since it is more efficient to sum the partial products as they are formed. In special processors optimized for speed, such as digital signal processors (DSP), dedicated hardware to do this is called a multiply and accumulate register (MAC).

Multiplying in binary follows the same rules.

111 x 101. This can be formulated as follows:

(111 × 1 × 22 ) + (111 × 0 × 21 ) + (111 × 1 × 20 )

With binary arithmetic, the task of multiplying by 2 is simply a shift of one bit to the left. Similarly, dividing by 2 is a shift of one bit to the right.

Binary Division

Division in binary follows the same concept as for long division in decimal

(Ex)

1.4 Boolean Algebra

George Boole (1854) invented a new kind of algebra that could be used to analyse and design digital and computer circuits.

1.4.1 Boolean laws and theorems

Certain rules and theorems are defined to facilitate the simplification of Boolean expressions inturn making the simpler logic circuits with reduced number of gates.

Basic laws
Commutative law:

A+B =B+A

AB = BA

Associative law:

A + (B+C) = (A+B) + C

A(BC) = (AB)C

Distributive law:

A (B+C) = AB + AC

Boolean relations about OR operations

A+0=A

A+A=A

A+1=1

Boolean relations about AND operations

A ' 1 = A
A ' A = A
A ' 0 = 0

1.4.2 Postulates

1. Identity

Identity elements exist for each operation that leaves the result unchanged.

A+0 = A

A.0 = 0

A+1 = 1

A.1 = A

An operation between two identical variables will yield a result that is unchanged

A+A = A

A.A = A

2. Inverse

For every element, there is an inverse or complementwith the following properties

A.A’= 0

A+A ‘= 1

3. The complement of a complement gives back the original quantity

(A’)’ = A

1.4.3 Application:

It provides the systematic mathematical approach to study, design and analyze the logic circuits.

Boolean expressions enables the design and simplification of logic circuits.

1.5 Logic Gates

1.5.1NOT operation

Fig. 2-1: Inverter symbol and Boolean notation

Ex: If A is 0 (low) ' X = NOT 0 = 1

In Boolean algebra the overbar stands for NOT operation.

1.5.2OR operation

Fig. 2-2: OR symbol and Boolean notation

Ex: If A = 0, B = 1 ' X = A or B = 0 or 1 = l

In Boolean algebra the + sign stans for the OR operation:

X=A+B

Ex: If A = 1, B = 0 ' X = A + B = 1 + 0 = 1

1.5.3AND operation

Fig. 2-3: AND symbol and Boolean notation

In Boolean algebra the multiplication sign stands for the AND operation

X = AB

Ex: If A = 1, B = 0 ' X = A B = 1 ' 0 = 0

1.5.4 NOR gate

Based on the three fundamental logic operations it is possible to design additionel logic devices.

Fig. 2-6: NOR gate, symbol and truth table

1.5.5NAND gate

Fig. 2-7: NAND grate, symbol and truth table

1.5.6 XOR gate

Events which are true only if and only if one of the motivating events are true

Truth Table

A B F

0 0 0

0 1 1

1 0 1

1 1 0

1.6 DE MORGAN’S THEOREMS

1.

This states that the inverse (i.e.)of a product [and] is equal to the sum [or] of the complements

2.

This states that the inverse (complement) of a sum [or] is equal to the product [and] of the complements

These theorems can be extended to cover several variables:

1.7 Canonical and Standard forms

Consider two binary variables x and y combined by an AND operation

X’. Y’ 0 0 m0

X’. Y 0 1 m1

X . Y’ 1 0 m2 Where X’ – Primed representing binary ‘0’

X . Y 1 1 m3 And X – Unprimed representing binary ‘1’

mx – Minterm or standard product

For n variables, there are in total 2n Minterms.

For OR operation,

X + Y 0 0 M0

X + Y’ 0 1 M1

X’+ Y 1 0 M2

X’ + Y’ 1 1 M3 Mx – Maxterm or standard sum

Each Maxterm is the complement of corresponding Minterm.

Boolean expression can be expressed in terms of Minterms and Maxterms as follows

X Y Z f1

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

1.7.1 Sum of minterms:

Boolean expression for the function f1 from the given truth table is,

f1= X’Y’Z + XY’Z’ + XYZ = m1 + m4 + m7

ie) OR ing the minterms which gives ‘1’ in the function f1

1.7.2 Product of maxterms:

Similarly,

f1= (X+Y+Z) (X+Y’+Z) (X+Y’+Z’) (X’+Y+Z’) (X’+Y’+Z) = M0 . M2 .M3.M5. M6

ie) AND ing the maxterms which gives ‘0’ in the function f1

1.8 Karnaugh Map

It is a systematic method to simplify Boolean expression using a map. Map is a diagram made up of cells where each cell gives the output value for the corresponding input combination. Totally there are 2n cells for ‘n’ input variables. The map presents a visual diagram of all possible ways a function may be expressed in a standard form.

1.8.1 Two- and Three- variable maps

A Two-variable map is shown below.

There are 4 cells for 2 variables. Each cell for a minterm. Figure (a) shows the minterms and (b) the relationship between the cells and variables.

Example:

F1 = XY is represented by this mapping method as,

Since XY is equal to m3, a ‘1’ is placed inside the cell that belongs to m3.

Similarly, F2 = X + Y as,

A Three-variable map is shown below.

Here 8 cells are not arranged in a binary sequence, but in a sequence similar to Gray code. The characteristic of this sequence is that only 1 bit changes from 0 to 1 or 1 to 0 in the listing sequence. ie) the minterms in the adjacent cells are differing by a single bit. This is the basic principle behind K-Map and can be clarified by taking a function having m5 and m7 as,

m5 + m7 = XY’Z + XYZ = XZ(Y’+Y) = XZ.

Two minterms of 3 literals is solved into a single minterm of 2 literals.

The two cells are considered to be adjacent even though they do not touch each other like m0 and m2.

Example:

#1) Simplify the Boolean function F(X, Y, Z) = ∑ (2, 3, 4, 5)

Mark 1 in each minterm that represents the function.

Find the adjacent cells (shown in two rectangles)

Upper rectangle area is enclosed by the variables X’ and Y

Similarly lower rectangle by variables X and Y’

So the resultant function is F(X, Y, Z) = ∑ (2, 3, 4, 5) = X’Y + XY’

1.8.2 Four- variable map

A Four-variable map is shown below.

The minterm corresponding to each cell can be obtained by the concatenation of the respective row and column. For instance, third row (11) and second column (01) gives 1101, the binary equivalent of decimal 13 representing m13.

The map minimization is the similar procedure as that of the three variable type.

No other combination of squares can simplify the function.

1.8.3 Five- variable map

Maps for more than 4 variables are not as simple to use. It needs 32 cells. A Five-variable map is shown below

It consists of 2 four-variable maps, where A distinguishes between two maps. Minterms 0 throgh 15 belong with A = 0 and Minterms 16 throgh 31 belong with A = 1. Each map retains adjacency when taken separately. Each cell in the A = 0 map is adjacent to the corresponding cell in the A = 1 map like 4 and 20, 15 and 31.

Simply, for 2k adjacent squares, for k = 0,1,2..n, in an n-variable map will represent an area that gives a term of n-k literals. When n=k, the entire areas of the is combined to give the identity function.

1.8.4 Product of Sum simplification

With minor modification, POS form is obtained as the result of simplification from the map. Simplified expression for the complement of the function,F’, is obtained if the cells with 0’s are combined into valid squares. The complement of F’ inturn gives us F in POS form.(By Demorgan’s Theorem)

Ex:

#1) Simplify the given Boolean expression in SOP and POS form.

F(A,B,C,D) = ∑(0,1,2,5,8,9,10)

Combining cells with 1’s gives the SOP form,

F = B’D’ + B’C’ + A’C’D

Combining cells with 0’s gives the form,

F = AB + CD + BD’

Applyind Demorgan’s theorem, we get the simplified POS form

F = (A’+B’) (C’+D’) (B’+D)

Gate implementation of the function

F = B’D’ + B’C’ + A’C’D F = (A’ + B’) (C’+ D’) (B’ + D)

1.8.4 NAND and NOR Implementation

NAND and NOR gates are easier to fabricate and are the basic gates used in all IC digital logic families. So Boolean functions interms of NAND and NOR is necessory.

The invert OR symbol is followed from the Demorgan’s thoerem.

Similarly for NOR gate,

A one-input NAND or NOR behaves like an inverter

1.8.4.1 NAND implementation

Boolean expression in sum of product form is needed for NAND implementation.

Consider for example, F = AB+CD+E is implemented in three ways as shown below.

Figure (a) and (c) looks similar but NAND implementation needs one more NAND gate for complementing E. By Demorgan’s theorem,

F = [ (AB)’ . (CD)’ . E’ ]’ = AB + CD + E.

Thus the two level implementation is possible with the NAND gates for the given Boolean expression.

1.8.4.2 NOR implementation

NOR function is the dual of the NAND function. So all the procedures and rules for NOR logic are the dual of the NAND logic.Boolean expression in product of sum form is needed for NOR implementation.

For the same example given above, F = (A+B) . (C+D) . E

To obtain product of sum from a map, it is necessary to combine cells with 0’s and then complement the function.

1.8.4.3 Don’t-Care conditions

The logical sun of minterms associated with the Boolean function specifies the condition under which the function is equal to 1. The function is equal to 0 for the rest of the minterms. Ie) all the combinations of variables are valid. In some practical applications the function is not specified for certain combinations of variables. For example four bit codes for BCD greater than 9 has six invalid combinations. These unspecified minterms are known as don’t care conditions and used for further simplification. To distinguish don’t care condition from 0 and 1, it is marked with X. Don’t care cell is assumed to be 1 or 0 when choosing adjacent squares.

Ex. #1) Simplify F(w,x,y,z) = ∑ (1,3,7,11,15)

That has the don’t care conditions

d(w,x,y,z) = ∑ (0,2,5)

All the five 1’s should be included to form the sum of products. But X may or may not be included.

By including 0 and 2 don’t care items, F = yz+w’x’

By including 5 don’t care item, F = yz+w’z

Expression in POS form is by grouping 0’s and include minterms 0 and 2 to get it in the simplified version.

F’ = z’ + wy’

Complementing F’ yields

F(w,x,y,z) = z(w’+y) = yz+w’z

For this case minterms 0 and 2 are included with 0’s and minterm 5 with the 1’s.

1.9 TABULATION METHOD

If the number of variables exceeds five or six, excessive number of cells make the grouping difficult whereby the tabulation method is a step-by-step procedure.This method was first tabulated by Quine and later improved by Mccluskey. Hence it is known as Quine-Mccluskey method.

It consists of two parts. First is to find the Prime implicants. Second to choose among the prime implicants those that give an expression with least number of literals.

Example 1) Find minimal SOP for f = ∑ (1,2,3,4,5,7,8,9,10,11,14,15)

Solution:

i)write the given minterms in binary form

minterms / A / B / C / D
1 / 0 / 0 / 0 / 1
2 / 0 / 0 / 1 / 0
3 / 0 / 0 / 1 / 1
4 / 0 / 1 / 0 / 0
5 / 0 / 1 / 0 / 1
7 / 0 / 1 / 1 / 1
8 / 1 / 0 / 0 / 0
9 / 1 / 0 / 0 / 1
10 / 1 / 0 / 1 / 0
11 / 1 / 0 / 1 / 1
14 / 1 / 1 / 1 / 0
15 / 1 / 1 / 1 / 1

ii)Arrange the numbers in increasing number of 1’s

No. Of 1’s / minterms / A / B / C / D
1 / 1 ^ / 0 / 0 / 0 / 1
4 ^ / 0 / 1 / 0 / 0
8 ^ / 1 / 0 / 0 / 0
2 / 3 ^ / 0 / 0 / 1 / 1
5 ^ / 0 / 1 / 0 / 1
9 ^ / 1 / 0 / 0 / 1
10 ^ / 1 / 0 / 1 / 0
3 / 7 ^ / 0 / 1 / 1 / 1
11 ^ / 1 / 0 / 1 / 1
14 ^ / 1 / 1 / 1 / 0
4 / 15 ^ / 1 / 1 / 1 / 1

iii)Compare adjacent groups to find numbers which differ by 1 variable.

^denotes the numbers undergone the comparision

Combination / A / B / C / D
(1,3) ^ / 0 / 0 / _ / 1
(1,9)^ / _ / 0 / 0 / 1
(2,3)^ / 0 / 0 / 1 / _
(2,10)^ / _ / 0 / 1 / 0
(8,9)^ / 1 / 0 / 0 / _
(8,10) ^ / 1 / 0 / _ / 0
(3,7)^ / 0 / _ / 1 / 1
(3,11)^ / _ / 0 / 1 / 1
(9,11)^ / 1 / 0 / _ / 1
(10,11)^ / 1 / 0 / 1 / _
(10,14) ^ / 1 / _ / 1 / 0
(7,15) ^ / _ / 1 / 1 / 1
(11,15)^ / 1 / _ / 1 / 1
(14,15)^ / 1 / 1 / 1 / _

_ denotes the differing variable position