UNIT I/LECTURE 1                                                              

INTRODUCTION

In science, technology, business, and, in fact, most other fields of endeavor, we are constantly dealing with quantities. Quantities are measured, monitored, recorded, manipulated arithmetically, observed, or in some other way utilized in most physical systems. It is important when dealing with various quantities that we be able to represent their values efficiently and accurately. There are basically two ways of representing the numerical value of quantities: analog and digital.

Advantages of digital System

1.      Easier to design. Exact values of voltage or current are not important, only the range (HIGH or LOW) in which they fall.

2.      Information storage is easy.

3.      Accuracy and precision are greater.

4.      Operation can be programmed. Analog systems can also be programmed, but the variety and complexity of the available operations is severely limited.

5.      Digital circuits are less affected by noise. As long as the noise is not large enough to prevent us from distinguishing a HIGH from a LOW.

6.      More digital circuitry can be fabricated on IC chips. 

Limitations

There is really only one major drawback when using digital techniques:The real world is mainly analog.Most physical quantities are analog in nature, and it is these quantities that are often the inputs and outputs that are being monitored, operated on, and controlled by a system.To take advantage of digital techniques when dealing with analog inputs and outputs, three steps must be followed:

1. Convert the real-world analog inputs to digital form. (ADC)
2. Process (operate on) the digital information.
3. Convert the digital outputs back to real-world analog form. (DAC)

Number systems & codes

Many number systems are in use in digital technology. The most common are the decimal, binary, octal, and hexadecimal systems. The decimal system is clearly the most familiar to us because it is a tool that we use every day. Examining some of its characteristics will help us to better understand the other systems.

Decimal System

Decimal System The decimal system is composed of 10 numerals or symbols. These 10 symbols are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; using these symbols as digits of a number, we can express any quantity. The decimal system, also called the base-10 system because it has 10 digits.

Binary System

In the binary system, there are only two symbols or possible digit values, 0 and 1. This base-2 system can be used to represent any quantity that can be represented in decimal or other number system.

HEXADECIMAL NUMBER SYSTEM

In mathematics and computing, hexadecimal (also base 16, or hex) is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F (or alternatively a–f) to represent values ten to fifteen. Hexadecimal numerals are widely used by computer systems designers and programmers. In computing, hexadecimal numerals are usually written with a prefix, "0x" (in reference to the abbreviated pronunciation of "hexadecimal"). Alternately, some authors denote hexadecimal values using a suffix or subscript. For example, one could write 0x2AF3 or 2AF3₁₆, depending on the choice of notation.

OCTAL NUMBER SYSTEM

The octal numeral system, or oct for short, is the base-8 number system, and uses the digits 0 to 7. Octal numerals can be made from binary numerals by grouping consecutive binary digits into groups of three (starting from the right). For example, the binary representation for decimal 74 is 1001010, which can be grouped into (00)1 001 010 – so the octal representation is 112.

Converting from either Hexadecimal, Binary or Octal to Decimal [ DEC 2014(2)]

A binary, a hexadecimal or an octal number can be expressed as the sum of the successive powers of the base (either 2, 16, or 8, respectively), with the coefficients being the digits.

For example,

Converting from Decimal to Binary

To convert a decimal number into a binary number, divide it by 2 repeatedly and note the remainders. The remainders are the bits of the binary number. The last remainder is the most significant bit, and the first remainder is the least significant bit.

For example,

Converting from Decimal to Hexadecimal

There are two different ways to convert a decimal number into a hexadecimal number.

1.  The first method is similar to converting a decimal to a binary and involves dividing the number by decimal 16 and noting the remainders. The first remainder is the least significant digit and the last remainder is the most significant digit.

For example,

2.  The second method involves converting the decimal number into a binary, then convert the binary into a hexadecimal number. To change the representation of the binary number to hexadecimal, separate the digits into 4-bit groups beginning with the least significant bit. Then write the hexadecimal equivalent of each group.

For example,

Converting from Decimal to Octal

To convert a decimal number into an octal number, divide it by 8 repeatedly and note the remainders. The remainders are the digits of the octal number. The last remainder is the most significant digit, and the first remainder is the least significant digit.

For example,

Converting between Binary and Hexadecimal

From Binary to Hexadecimal:  To convert a binary number into its hexadecimal form, start by grouping the digits into 4-bit groups. Beginning with the least significant bit (all the way to the right of the number), write the hexadecimal equivalent of each group.

For example,

From Hexadecimal to Binary:  To convert a hexadecimal number into a binary, just reverse the above process; starting all the way to the right, convert each digit into a 4-bit binary number.

Converting between Binary and Octal

From Binary to Octal:  To convert a binary number into its octal form, start by grouping the digits into 3-bit groups. Beginning with the least significant bit (all the way to the right of the number), write the octal equivalent of each group.

For example,

DECIMAL TO BCD CONVERSION[ DEC 2014(2)]

Decimal Number: 29₁₀

Calculating BCD Equivalent. Convert each digit into groups of four binary digits equivalent.

UNIT 2/ LECTURE 2

BINARY ARITHMATIC

Rules of Binary Addition

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0, and carry 1 to the next more significant bit

For example,

Note:  The rules of binary addition (without carries) are the same as the truths of the XOR gate.

Rules of Binary Subtraction

• 0 - 0 = 0
• 0 - 1 = 1, and borrow 1 from the next more significant bit
• 1 - 0 = 1
• 1 - 1 = 0

For example,

Rules of Binary Multiplication

• 0 x 0 = 0
• 0 x 1 = 0
• 1 x 0 = 0
• 1 x 1 = 1, and no carry or borrow bits

For example,

Note:  The rules of binary multiplication are the same as the truths of the AND gate.

Another Method:  Binary multiplication is the same as repeated binary addition; add the multicand to itself the multiplier number of times.

For example,

Binary Division

Binary division is the repeated process of subtraction, just as in decimal division.For example,

UNIT 1 /LECTURE 3

Boolean Algebra

A Boolean algebra is an algebra consisting of a set B (which contains at least two elements 0 and 1) together with three operations : AND, OR, NOT defined on the set, such that for any element x and y of B, x . y (the product of x and y), x + y (the sum of x and y ) and x’ (the complement of x ) are in B.

Axioms of Boolean Algebra

If x = 0, then x’ = 1 and If x = 1, then x’ = 0.

Single-Variable Theorems

If x is a Boolean variable in set B, then we have:

Note the principle of duality

Two - and Three – Variable Properties

UNIT 1 / LECTURE 4

Minimization of switching function

Karnaugh map method

A Karnaugh Map is a graphical way of minimizing a Boolean expression based on the rule of complementation.  It works well i there are 2, 3, or 4 variables, but gets messy or impossible to use for expressions with more variables than that. The idea behind a Karnaugh Map (Karnaugh, 1953) is to draw an expression’s truth table as a matrix in such a way that each row and each column of the matrix puts minterms that differ in the value of a single variable adjacent to each other.  Then, by grouping adjacent cells of the matrix, you can identify product terms tha eliminate all complemented literals, resulting in a minimized version of the expression.

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem. 

The values inside the squares are copied from the output column of the truth table, therefore there is one square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two input variable. A is along the top and B is down the left hand side. The diagram below explains this:

The values around the edge of the map can be thought of as coordinates. So as an example, the square on the top right hand corner of the map in the above diagram has coordinates A=1 and B=0. This square corresponds to the row in the truth table where A=1 and B=0 and F=1. Note that the value in the F column represents a particular function to which the Karnaugh map corresponds.

Example 1:

Consider the following map. The function plotted is: Z = f(A,B) = A  + AB 
 

• Note that values of the input variables form the rows and columns. That is the logic values of the variables A and B (with one denoting true form and zero denoting false form) form the head of the rows and columns respectively.
• Bear in mind that the above map is a one dimensional type which can be used to simplify an expression in two variables.
• There is a two-dimensional map that can be used for up to four variables, and a three-dimensional map for up to six variables.

Using algebraic simplification,

Z = A  + AB

Z = A(  + B)

Z = A

Variable B becomes redundant due to Boolean Theorem T9a.

Referring to the map above, the two adjacent 1's are grouped together. Through inspection it can be seen that variable B has its true and false form within the group. This eliminates variable B leaving only variable A which only has its true form. The minimised answer therefore is Z = A.

UNIT I /LECTURE 5

Example 2:

Consider the expression Z = f(A,B) =   + A   +  B plotted on the Karnaugh map: 
 
Pairs of 1's are grouped as shown above, and the simplified answer is obtained by using the following steps: 

Note that two groups can be formed for the example given above, bearing in mind that the largest rectangular clusters that can be made consist of two 1s. Notice that a 1 can belong to more than one group.  The first group labelled I, consists of two 1s which correspond to A = 0, B = 0 and A = 1, B = 0. Put in another way, all squares in this example that correspond to the area of the map where B = 0 contains 1s, independent of the value of A. So when B = 0 the output is 1. The expression of the output will contain the term 

For group labelled II corresponds to the area of the map where A = 0. The group can therefore be defined as  . This implies that when A = 0 the output is 1. The output is therefore 1 whenever B = 0 and A = 0 
Hence the simplified answer is Z =   + 

Larger 4-variable Karnaugh maps

Knowing how to generate Gray code should allow us to build larger maps. Actually, all we need to do is look at the left to right sequence across the top of the 3-variable map, and copy it down the left side of the 4-variable map. See below.

The following four variable Karnaugh maps illustrate reduction of Boolean expressions too tedious for Boolean algebra. Reductions could be done with Boolean algebra. However, the Karnaugh map is faster and easier, especially if there are many logic reductions to do.

The above Boolean expression has seven product terms. They are mapped top to bottom and left to right on the K-map above. For example, the first P-term A'B'CD is first row 3rd cell, corresponding to map location A=0, B=0, C=1, D=1. The other product terms are placed in a similar manner. Encircling the largest groups possible, two groups of four are shown above. The dashed horizontal group corresponds the the simplified product term AB. The vertical group corresponds to Boolean CD. Since there are two groups, there will be two product terms in the Sum-Of-Products result of Out=AB+CD.

Example 3:  [ June 2014 (7)],[june 2011(10)]

Simplify the Boolean expression

F(w,x,y,z) = Σ(0,1,2,4,5,6,8,9,12,13,14)

Sol:                                w x       y z

The reduced function will be given by

Out = y’ + w’ z’ + x z’

Q. write the minterm of ACD+AB and implement it  [June 2014(2)

Sol:- filling the k-map

F= AB

IMPLEMENTATION

UNIT I/LECTURE 6

DON’T CARE CONDITION

Up to this point we have considered logic reduction problems where the input conditions were completely specified. That is, a 3-variable truth table or Karnaugh map had 2ⁿ = 2³ or 8-entries, a full table or map. It is not always necessary to fill in the complete truth table for some real-world problems. We may have a choice to not fill in the complete table.

For example, when dealing with BCD (Binary Coded Decimal) numbers encoded as four bits, we may not care about any codes above the BCD range of (0, 1, 2...9). The 4-bit binary codes for the hexadecimal numbers (Ah, Bh, Ch, Eh, Fh) are not valid BCD codes. Thus, we do not have to fill in those codes at the end of a truth table, or K-map, if we do not care to. We would not normally care to fill in those codes because those codes (1010, 1011, 1100, 1101, 1110, 1111) will never exist as long as we are dealing only with BCD encoded numbers. These six invalid codes are don't cares as far as we are concerned. That is, we do not care what output our logic circuit produces for these don't cares.

Don't cares in a Karnaugh map, or truth table, may be either 1s or 0s, as long as we don't care what the output is for an input condition we never expect to see. We plot these cells with an asterisk, *, among the normal 1s and 0s. When forming groups of cells, treat the don't care cell as either a 1 or a 0, or ignore the don't cares. This is helpful if it allows us to form a larger group than would otherwise be possible without the don't cares. There is no requirement to group all or any of the don't cares. Only use them in a group if it simplifies the logic.

Above is an example of a logic function where the desired output is 1 for input ABC = 101 over the range from 000 to 101. We do not care what the output is for the other possible inputs (110, 111). Map those two as don't cares. We show two solutions. The solution on the right Out = AB'C is the more complex solution since we did not use the don't care cells. The solution in the middle, Out=AC, is less complex because we grouped a don't care cell with the single 1 to form a group of two. The third solution, a Product-Of-Sums on the right, results from grouping a don't care with three zeros forming a group of four 0s. This is the same, less complex, Out=AC.

Example1: Simplify the Boolean function  [june 2014(7)]

F(w,x,y,z) = Σ(1,3,7,11,15) +dc Σ(7,2,5)

SOL:-

Output = w’x’+yz

UNIT 1/ LECTURE 7

Quine & McCluskey's method[june2011(10)]

The Quine-McCluskey method is an exact algorithm which finds a minimum-cost sum-of-products implementation of a Boolean function. This handout introduces the method and applies it to several examples.

There are 4 main steps in the Quine-McCluskey algorithm:

1. Generate Prime Implicants

2. Construct Prime Implicant Table

3. Reduce Prime Implicant Table

(a) Remove Essential Prime Implicants

(b) Row Dominance

(c) Column Dominance

4. Solve Prime Implicant Table

In Step #1, the prime implicants of a function are generated using an iterative procedure. In Step #2, a prime implicant table is constructed. The columns of the table are the prime implicants of the function. The rows are minterms of where the function is 1, called ON-set minterms. The goal of the method is to cover all the rows using a minimum-cost cover of prime implicants.

In particular, ’minimum-cost’ for this handout means to have fewest prime implicants (i.e. AND gates) in

the final solution. However, the algorithm has been extended to consider more complex cost functions, such as minimizing the total number of gate inputs, power optimization, and so on.

The reduction step (Step #3) is used to reduce the size of the table. This step has three sub-steps which are iterated until no further table reduction is possible. At this point, the reduced table is either (i) empty or (ii) non-empty. If the reduced table is empty, the removed essential prime implicants form a minimum-cost solution. However, if the reduced table is not empty, the table must be “solved” (Step #4).

The table can be solved using either “Petrick’s method” or the “branching method”. This handout focuses on Petrick’s method. The branching method is discussed in the books by McCluskey, Roth, etc., but you will not be responsible for the branching method. The remainder of this handout illustrates the details of the Quine-McCluskey method on 3 examples. Example #1 is fairly straightforward, Examples #2 is more involved, and Example #3 applies the method to a function with “don’t-cares”. But first, we motivate the need for column dominance and row dominance.

Karnaugh map with set of prime implicants: illustrating "column dominance"

Column Dominance

Consider the following Karnaugh map of a 4-input Boolean function: There are 5 prime implicants, each of which covers 2 ON-set minterms.

First, we note that two implicants are essential prime implicants: A′C′D′ and ACD. These implicants must be added to the final cover. There are 3 remaining prime implicants. We must pick a minimum subset of these to cover the uncovered ON-set minterms.

Here is the prime implicants table for the Karnaugh map. The 5 prime implicants are listed as columns, and the 6 ON-set minterms are listed as rows.

Karnaugh map with set of prime implicants: illustrating "row dominance"

We cross out columns A′C′D′ and ACD and mark them with asterisks, to indicate that these are essential. Each row intersected by one of these columns is also crossed out, because that minterm is now covered. At this point, prime implicant BC′D covers 2 remaining ON-set minterms (5 and 13). However, prime implicant A′BC′ covers only one of these (namely, 5), as does ABD (namely, 13). Therefore we can always use BC′D instead of either A′BC or ABD, since it covers the same minterms. That is, BC′D column-dominates A′BC, and BC′D column-dominates ABD. The dominated prime implicants can be crossed out, and only column BC′D remains.

UNIT 1 /LECTURE 8

Row Dominance

Consider the following Karnaugh map of a 4-input Boolean function: There are 4 prime implicants: A′B′, C′D, A′D and A′C. None of these is an essential prime implicant. We must pick a minimum subset of these to cover the 5 ON-set minterms. Here is the prime implicant table for

the Karnaugh map. The 4 prime implicants are listed as columns, and the 5 ON-set minterms are listed as rows.

Note that row 3 is contained in three columns: A′B′, A′D, and A′C. Row 2 is covered by two of these three columns: A′B′ and A′C, and row 7 is also covered by two of these three columns: A′D and A′C. In this case, any prime implicant which contains row 2 also contains row 3. Similarly, any prime implicant which contains row 7 also contains row 3. Therefore, we can ignore the covering of row 3: it will always be covered as long as we cover row 2 or row 7. To see this, note that row 3 row dominates row 2, and row 3 rows dominates row 7. The situation is now the reverse of column dominance: we cross out the dominating (larger) row. In this case, row 3 can be crossed out; it no longer needs to be considered. Similarly, row 1 row dominates row 5. Therefore row 1 can be crossed out. We are guaranteed that row 1 will still be covered, since any prime implicant which covers row 5 will also cover row 1.

Example #1:  (

F(A,B,C,D) = _m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)

The Notation. The above notation is a shorthand to describe the Karnaugh map for F. First, it indicates

that F is a Boolean function of 4 variables: A, B, C, and D. Second, each ON-set minterm of F is listed

above, that is, minterms where the function is 1: 0, 2, 5, . . .. Each of these numbers corresponds to one

entry (or square) in the Karnaugh map. For example, the decimal number 2 corresponds to the minterm ABCD = 0010, (0010 is the binary representation of 2). That is, ABCD = 0010 is an ON-set minterm of F; i.e., it is a 1 entry. All remaining minterms, not listed above, are assumed to be 0.

Step 1: Generate Prime Implicants.

Note: You should learn this basic method for generating prime implicants (Step #1), but I will not ask you to reproduce it. See Roth book on reserve for more details. (Instead, you will soon learn the more advanced fast recursive algorithm for prime generation.)

Combine Pairs of Minterms from Column I

A check (√) is written next to every minterm which can combined with another minterm.

Combine Pairs of Products from Column II

A check (√) is written next to every product which can combined with another product.

UNIT I/ LECTURE 9

Column III contains a number of duplicate entries, e.g. (0,2,8,10) and (0,8,2,10). Duplicate entries appear because a product in Column III can be formed in several ways. For example, (0,2,8,10) is formed by combining products (0,2) and (8,10) from Column II, and (0,8,2,10) (the same product) is formed by combining products (0,8) and (2,10).

Duplicate entries should be crossed out. The remaining unchecked products cannot be combined with other products. These are the prime implicants: (0,2,8,10), (2,6,10,14), (5,7,13,15), (6,7,14,15), (8,10,12,14) and (12,13,14,15); or, using the usual product notation: B′D′, CD′, BD, BC, AD′ and AB.

Step 2: Construct Prime Implicant Table.

Step 3: Reduce Prime Implicant Table.

Iteration #1.

(i)                 Remove Primary Essential Prime Implicants

* indicates an essential prime implicant

◦ indicates a distinguished row, i.e. a row covered by only 1 prime implicant

In step #1, primary essential prime implicants are identified. These are implicants which will appear in any solution. A row which is covered by only 1 prime implicant is called a distinguished row. The prime implicant which covers it is an essential prime implicant. In this step, essential prime implicants are identified and removed. The corresponding column is crossed out. Also, each row where the column contains an X is completely crossed out, since these minterms are now covered. These essential implicants will be added to the final solution. In this example, B′D′ and BD are both primary essentials.

(ii)               Row Dominance

The table is simplified by removing rows and columns which were crossed out in step (i). (Note: you do not need to do this, but it makes the table easier to read. Instead, you can continue to mark up the original table.)

Row 14 dominates both row 6 and row 12. That is, row 14 has an “X” in every column where row 6 has an “X” (and, in fact, row 14 has “X”’s in other columns as well). Similarly, row 14 has in “X” in every column where row 12 has an “X”. Rows 6 and 12 are said to be dominated by row 14. A dominating row can always be eliminated. To see this, note that every product which covers row 6 also covers row 14. That is, if some product covers row 6, row 14 is guaranteed to be covered. Similarly, any product which covers row 12 will also cover row 14. Therefore, row 14 can be crossed out.

(iii)             Column Dominance

Column CD′ dominates column BC. That is, column CD′ has an “X” in every row where column BC has an “X”. In fact, in this example, column BC also dominates column CD′, so each is dominated by the other. (Such columns are said to co-dominate each other.) Similarly, columns AD′ and AB dominate each other, and each is dominated by the other.

A dominated column can always be eliminated. To see this, note that every row covered by the dominated column is also covered by the dominating column. For example, C′D covers every row which BC covers. Therefore, the dominating column can always replace the dominated column, so the dominated column is crossed out. In this example, CD′ and BC dominate each other, so either column can be crossed out (but not both). Similarly, AD′ and AB dominate each other, so either column can be crossed out.

Iteration #2.

(i)                 Remove Secondary Essential Prime Implicants

** indicates a secondary essential prime implicant

◦ indicates a distinguished row

In iteration #2 and beyond, secondary essential prime implicants are identified. These are implicants which will appear in any solution, given the choice of column-dominance used in the previous steps (if 2 columns co-dominated each other in a previous step, the choice of which was deleted can affect what is an “essential” at this step). As before, a row which is covered by only 1 prime implicant is called a distinguished row. The prime implicant which covers it is a (secondary) essential prime implicant.

Secondary essential prime implicants are identified and removed. The corresponding columns are crossed out. Also, each row where the column contains an X is completely crossed out, since these minterms are now covered. These essential implicants will be added to the final solution. In this example, both CD′ and AD′ are secondary essentials.

Step 4: Solve Prime Implicant Table.

No other rows remain to be covered, so no further steps are required. Therefore, the minimum-cost solution consists of the primary and secondary essential prime implicants B′D′, BD, CD′ and AD′:

F = B′D′ + BD + CD′ + AD′