Lecture notes on Digital principles and system design

digital principles and system design question bank with answer pdf, digital principles and system design textbook, digital principles and system design university questions pdf
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
CS6201 – DIGITAL PRINCIPLES AND SYSTEM DESIGN Lecture Notes SEMESTER-II Regulation 2013 www.annauniversityplus.comL T P C 3 1 0 4 UNIT I BOOLEAN ALGEBRA AND LOGIC GATES 9 Review of Binary Number Systems – Binary Arithmetic – Binary Codes – Boolean Algebra and Theorems – Boolean Functions – Simplifications of Boolean Functions Using Karnaugh Map and Tabulation Methods – Implementation of Boolean Functions using Logic Gates. UNIT II COMBINATIONAL LOGIC 9 Combinational Circuits – Analysis and Design Procedures - Circuits for Arithmetic Operations – Code Conversion – Hardware Description Language (HDL). UNIT III DESIGN WITH MSI DEVICES 9 Decoders and Encoders – Multiplexers and Demultiplexers – Memory and Programmable Logic – HDL for Combinational Circuits UNIT IV SYNCHRONOUS SEQUENTIAL LOGIC 9 Sequential Circuits – Flip flops – Analysis and Design Procedures - State Reduction and State Assignment – Shift Registers – Counters – HDL for Sequential Circuits. UNIT V ASYNCHRONOUS SEQUENTIAL LOGIC 9 Analysis and Design of Asynchronous Sequential Circuits - Reduction of State and Flow Tables – Race-Free State Assignment – Hazards – ASM Chart. L: 45 T: 15 Total: 60 TEXT BOOK 1. M. Morris Mano, ―Digital Design‖, 3rd Edition, Pearson Education, 2007. REFERENCES 1. Charles H. Roth, ―Fundamentals of Logic Design‖, 5th Edition, Thomson Learning, 2003. 2. Donald D. Givone, ―Digital Principles and Design‖, Tata McGraw-Hill, 2007. www.annauniversityplus.comUNIT I BOOLEAN ALGEBRA AND LOGIC GATES www.annauniversityplus.comSYLLABUS : Review of Binary Number Systems Binary Arithmetic Binary Codes Boolean Algebra and Theorems Boolean Functions Simplifications of Boolean Functions Using Karnaugh Map and Tabulation Methods Implementation of Boolean Functions using Logic Gates. www.annauniversityplus.comUNIT 1 BOOLEAN ALGEBRA AND MINIMIZATION 1.1 Introduction: The English mathematician George Boole (1815-1864) sought to give symbolic form to Aristotle‘s system of logic. Boole wrote a treatise on the subject in 1854, titled An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, which codified several rules of relationship between mathematical quantities limited to one of two possible values: true or false, 1 or 0. His mathematical system became known as Boolean algebra. All arithmetic operations performed with Boolean quantities have but one of two possible Outcomes: either 1 or 0. There is no such thing as ‖2‖ or ‖-1‖ or ‖1/2‖ in the Boolean world. It is a world in which all other possibilities are invalid by fiat. As one might guess, this is not the kind of math you want to use when balancing a checkbook or calculating current through a resistor. However, Claude Shannon of MIT fame recognized how Boolean algebra could be applied to on-and-off circuits, where all signals are characterized as either ‖high‖ (1) or ‖low‖ (0). His1938 thesis, titled A Symbolic Analysis of Relay and Switching Circuits, put Boole‘s theoretical work to use in a way Boole never could have imagined, giving us a powerful mathematical tool for designing and analyzing digital circuits. Like ‖normal‖ algebra, Boolean algebra uses alphabetical letters to denote variables. Unlike ‖normal‖ algebra, though, Boolean variables are always CAPITAL letters, never lowercase. Because they are allowed to possess only one of two possible values, either 1 or 0, each and every variable has a complement: the opposite of its value. For example, if variable ‖A‖ has a value of 0, then the complement of A has a value of 1. Boolean notation uses a bar above the variable character to denote complementation, like this: www.annauniversityplus.com In written form, the complement of ‖A‖ denoted as ‖A-not‖ or ‖A-bar‖. Sometimes a ‖prime‖ symbol is used to represent complementation. For example, A‘ would be the complement of A, much the same as using a prime symbol to denote differentiation in calculus rather than the fractional notation dot. Usually, though, the ‖bar‖ symbol finds more widespread use than the ‖prime‖ symbol, for reasons that will become more apparent later in this chapter. 1.2 Boolean Arithmetic: Let us begin our exploration of Boolean algebra by adding numbers together: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 The first three sums make perfect sense to anyone familiar with elementary addition. The Last sum, though, is quite possibly responsible for more confusion than any other single statement in digital electronics, because it seems to run contrary to the basic principles of mathematics. Well, it does contradict principles of addition for real numbers, but not for Boolean numbers. Remember that in the world of Boolean algebra, there are only two possible values for any quantity and for any arithmetic operation: 1 or 0. There is no such thing as ‖2‖ within the scope of Boolean values. Since the sum ‖1 + 1‖ certainly isn‘t 0, it must be 1 by process of elimination. 1.2.1 Addition – OR Gate Logic: www.annauniversityplus.comBoolean addition corresponds to the logical function of an ‖OR‖ gate, as well as to parallel switch contacts: There is no such thing as subtraction in the realm of Boolean mathematics. Subtraction Implies the existence of negative numbers: 5 - 3 is the same thing as 5 + (-3), and in Boolean algebra negative quantities are forbidden. There is no such thing as division in Boolean mathematics, either, since division is really nothing more than compounded subtraction, in the same way that multiplication is compounded addition. 1.2.2 Multiplication – AND Gate logic Multiplication is valid in Boolean algebra, and thankfully it is the same as in real-number algebra: anything multiplied by 0 is 0, and anything multiplied by 1 remains unchanged: www.annauniversityplus.com www.Vidy0 × 0 = 0 0 × 1 = 0 1 × 0 = 0 1 × 1 = 1 This set of equations should also look familiar to you: it is the same pattern found in the truth table for an AND gate. In other words, Boolean multiplication corresponds to the logical function of an ‖AND‖ gate, as well as to series switch contacts: www.annauniversityplus.com1.2.3 Complementary Function – NOT gate Logic Boolean complementation finds equivalency in the form of the NOT gate, or a normally closed switch or relay contact: 1.3 Boolean Algebraic Identities In mathematics, an identity is a statement true for all possible values of its variable or variables. The algebraic identity of x + 0 = x tells us that anything (x) added to zero equals the original ‖anything,‖ no matter what value that ‖anything‖ (x) may be. Like ordinary algebra, Boolean algebra has its own unique identities based on the bivalent states of Boolean variables. The first Boolean identity is that the sum of anything and zero is the same as the original ‖anything.‖ This identity is no different from its real-number algebraic equivalent: www.annauniversityplus.com No matter what the value of A, the output will always be the same: when A=1, the output will also be 1; when A=0, the output will also be 0. The next identity is most definitely different from any seen in normal algebra. Here we discover that the sum of anything and one is one: No matter what the value of A, the sum of A and 1 will always be 1. In a sense, the ‖1‖ signal overrides the effect of A on the logic circuit, leaving the output fixed at a logic level of 1. Next, we examine the effect of adding A and A together, which is the same as connecting both inputs of an OR gate to each other and activating them with the same signal: www.annauniversityplus.com In real-number algebra, the sum of two identical variables is twice the original variable‘s value (x + x = 2x), but remember that there is no concept of ‖2‖ in the world of Boolean math, only 1 and 0, so we cannot say that A + A = 2A. Thus, when we add a Boolean quantity to itself, the sum is equal to the original quantity: 0 + 0 = 0, and 1 + 1 = 1. Introducing the uniquely Boolean concept of complementation into an additive identity, we find an interesting effect. Since there must be one ‖1‖ value between any variable and its complement, and since the sum of any Boolean quantity and 1 is 1, the sum of a variable and its complement must be 1: Four multiplicative identities: Ax0, Ax1, AxA, and AxA‘. Of these, the first two are no different from their equivalent expressions in regular algebra: www.annauniversityplus.com The third multiplicative identity expresses the result of a Boolean quantity multiplied by itself. In normal algebra, the product of a variable and itself is the square of that variable (3x 3 = 32 = 9). However, the concept of ‖square‖ implies a quantity of 2, which has no meaning in Boolean algebra, so we cannot say that A x A = A2. Instead, we find that the product of a Boolean quantity and itself is the original quantity, since 0 x 0 = 0 and 1 x 1 = 1: The fourth multiplicative identity has no equivalent in regular algebra because it uses the complement of a variable, a concept unique to Boolean mathematics. Since there must be one ‖0‖ value between any variable and its complement, and since the product of any Boolean quantity and 0 is 0, the product of a variable and its complement must be 0: www.annauniversityplus.com 1.4 Principle of Duality: It states that every algebraic expression is deducible from the postulates of Boolean algebra, and it remains valid if the operators & identity elements are interchanged. If the inputs of a NOR gate are inverted we get a AND equivalent circuit. Similarly when the inputs of a NAND gate are inverted, we get a OR equivalent circuit. This property is called DUALITY. 1.5 Theorems of Boolean algebra: The theorems of Boolean algebra can be used to simplify many a complex Boolean expression and also to transform the given expression into a more useful and meaningful equivalent expression. The theorems are presented as pairs, with the two theorems in a given pair being the dual of each other. These theorems can be very easily verified by the method of ‗perfect induction‘. According to this method, the validity of the expression is tested for all possible combinations of values of the variables involved. Also, since the validity of the theorem is based on its being true for all possible combinations of values of variables, there is no reason why a variable cannot be replaced with its complement, or vice versa, without disturbing the validity. Another important point is that, if a given expression is valid, its dual will also be valid 1.5.1 Theorem 1 (Operations with ‗0‘ and ‗1‘) www.annauniversityplus.com(a) 0.X = 0 and (b) 1+X= 1 Where X is not necessarily a single variable – it could be a term or even a large expression. Theorem 1(a) can be proved by substituting all possible values of X, that is, 0 and 1, into the given expression and checking whether the LHS equals the RHS: • For X = 0, LHS = 0.X = 0.0 = 0 = RHS. • For X= 1, LHS = 0.1 = 0 = RHS. Thus, 0.X =0 irrespective of the value of X, and hence the proof. Theorem 1(b) can be proved in a similar manner. In general, according to theorem 1, 0. (Boolean expression) = 0 and 1+ (Boolean expression) =1. For example: 0. (A.B+B.C +C.D) = 0 and 1+ (A.B+B.C +C.D) = 1, where A, B and C are Boolean variables. 1.5.2 Theorem 2 (Operations with ‗0‘ and ‗1‘) (a) 1.X = X and (b) 0+X = X where X could be a variable, a term or even a large expression. According to this theorem, ANDing a Boolean expression to ‗1‘ or ORing ‗0‘ to it makes no difference to the expression: www.annauniversityplus.com• For X = 0, LHS = 1.0 = 0 = RHS. • For X = 1, LHS = 1.1 = 1 = RHS. Also, 1. (Boolean expression) = Boolean expression and 0 + (Boolean expression) = Boolean expression. For example, 1.(A+B.C +C.D) = 0+(A+B.C +C.D) = A+B.C +C.D 1.5.3 Theorem 3 (Idempotent or Identity Laws) (a) X.X.X……X = X and (b) X+X+X +···+X = X Theorems 3(a) and (b) are known by the name of idempotent laws, also known as identity laws. Theorem 3(a) is a direct outcome of an AND gate operation, whereas theorem 3(b) represents an OR gate operation when all the inputs of the gate have been tied together. The scope of idempotent laws can be expanded further by considering X to be a term or an expression. For example, let us apply idempotent laws to simplify the following Boolean expression: 1.5.4 Theorem 4 (Complementation Law) (a) X_X = 0 and (b) X+X = 1 www.annauniversityplus.com According to this theorem, in general, any Boolean expression when ANDed to its complement yields a ‗0‘ and when ORed to its complement yields a ‗1‘, irrespective of the complexity of the expression: Hence, theorem 4(a) is proved. Since theorem 4(b) is the dual of theorem 4(a), its proof is implied. The example below further illustrates the application of complementation laws: 1.5.5 Theorem 5 (Commutative property) Mathematical identity, called a ‖property‖ or a ‖law,‖ describes how differing variables relate to each other in a system of numbers. One of these properties is known as the commutative property, and it applies equally to addition and multiplication. In essence, the commutative property tells us we can reverse the order of variables that are either added together or multiplied together without changing the truth of the expression: Commutative property of addition A + B = B + A Commutative property of multiplication AB = BA 1.5.6 Theorem 6 (Associative Property) www.annauniversityplus.com The Associative Property, again applying equally well to addition and multiplication. This property tells us we can associate groups of added or multiplied variables together with parentheses without altering the truth of the equations. Associative property of addition A + (B + C) = (A + B) + C Associative property of multiplication A (BC) = (AB) C 1.5.7 Theorem 7 (Distributive Property) The Distributive Property, illustrating how to expand a Boolean expression formed by the product of a sum, and in reverse shows us how terms may be factored out of Boolean sums-of- products: Distributive property A (B + C) = AB + AC 1.5.8 Theorem 8 (Absorption Law or Redundancy Law) (a) X+X.Y = X and (b) X.(X+Y) = X The proof of absorption law is straightforward: www.annauniversityplus.comX+X.Y = X. (1+Y) = X.1 = X Theorem 8(b) is the dual of theorem 8(a) and hence stands proved. The crux of this simplification theorem is that, if a smaller term appears in a larger term, then the larger term is redundant. The following examples further illustrate the underlying concept: 1.5.9 Demorgan‘s Theorem De-Morgan was a great logician and mathematician. He had contributed much to logic. Among his contribution the following two theorems are important De-Morgan‘s First Theorem It States that ―The complement of the sum of the variables is equal to the product of the complement of each variable‖. This theorem may be expressed by the following Boolean expression. www.annauniversityplus.com De-Morgan‘s Second Theorem It states that the ―Complement of the product of variables is equal to the sum of complements of each individual variables‖. Boolean expression for this theorem is 1.6 Boolean Function www.annauniversityplus.com Z=AB‘+A‘C+A‘B‘C‘ www.annauniversityplus.com

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.