Digital Design and Computer Organization Module 1 PDF

Digital Design and Computer Organization 23CSI32 Module 1 Introduction to Digital Design Binary Logic Binary logic deals with variables that take on two...

Digital Design and Computer Organization 23CSI32 Module 1 Introduction to Digital Design Binary Logic Binary logic deals with variables that take on two discrete values and with operations that assume logical meaning. The two values the variables assume may be called by different names (true and false, yes and no, etc.), but for our purpose, it is convenient to think in terms of bits and assign the values 1 and 0. Definition of Binary Logic Binary logic consists of binary variables and a set of logical operations. The variables are designated by letters of the alphabet, such as A, B, C, x, y, z, etc., with each variable having two and only two distinct possible values: 1 and 0. There are three basic logical operations: AND, OR, and NOT. Each operation produces a binary result, denoted by z. 1. AND: This operation is represented by a dot or by the absence of an operator. For example, x⋅y=z or xy=z is read “x AND y is equal to z.” The logical operation AND is interpreted to mean that z=1 if and only if x=1 and y=1; otherwise z=0. (Remember that x, y, and z are binary variables and can be equal either to 1 or 0, and nothing else.) The result of the operation x⋅y is z. 2. OR: This operation is represented by a plus sign. For example, x+y=z is read “x OR y is equal to z,” meaning that z=1 if x=1 or if y=1 or if both x=1 and y=1. If both x=0 and y=0, then z=0. 3. NOT: This operation is represented by a prime (sometimes by an overbar). For example, x′=z (or x¯=z) is read “not x is equal to z,” meaning that z is what x is not. In other words, if x=1, then z=0, but if x=0, then z=1. The NOT operation is also referred to as the complement operation, since it changes a 1 to 0 and a 0 to 1, that is, the result of complementing 1 is 0, and vice versa. Theorems and Properties of Boolean Algebra The switching algebra is also called Boolean Algebra. Basically, it is used to analyse digital gates along with the circuits. It is logical to perform a mathematical operation on the binary numbers, namely on ‘1’ and ‘0’. Boolean Algebra consists of various basic operators such as AND, OR, NOT etc. The given operations are represented using the ‘.’ for AND along with ‘+’ for OR. We can perform the operations on variables that are represented using capital letters, for example, ‘A’, ‘B’, ‘C’, etc. Properties of Boolean Algebra The primary aim of a logic design is the simplification of the logic as much as possible. We do this so that the final implementation becomes comparatively easy. To simplify the logic, all the Boolean equations along with expressions that represent the logic have to be simplified. ,Prof. Likhitha, CSE, NCET 1 Digital Design and Computer Organization 23CSI32 Here are a few laws that define the various properties present in a boolean algebra: Annulment Law It states that a variable that has been ANDed with 0 gives us a 0, while a variable that has been ORed with 1 gives us a 1, i.e., X.0 = 0 X+1=1 Identity Law This law states that a variable would remain unchanged when it is ANDed with ‘1’ or ORed with ‘0’, i.e., X.1 = X X+0=X Idempotent Law This law states that a variable would remain unchanged when it is ANDed or ORed with itself, i.e., X+X=X X.X = X Complement Law This law states that in case a complement is added to any variable, then it would give one, whereas when we multiply this variable with its own complement, then it would result in ‘0’, i.e., X + X’ = 1 X.X’ = 0 Double negation Law This law states that whenever a variable is with two negations, then its symbol would ultimately get cancelled out while the original variable is obtained with it, i.e., ((X)’)’ = X Commutative Law The order of the variable or two different terms does not matter according to this law. It can be represented as follows, X+Y=Y+X ,Prof. Likhitha, CSE, NCET 2 Digital Design and Computer Organization 23CSI32 X.Y = Y.X Associative Law According to this law, the order of an operation does not matter when the priority of the given variables are similar, such as ‘*’ and ‘/’, i.e., X + (Y + Z) = (X + Y) + Z X.(Y.Z) = (X.Y).Z Distributive Law Using this law, we try to understand how the opening up of the brackets available in an operation, i.e., X.(Y+Z) = (X.Y) + (X.Z) X + (Y.Z) = (X + Y).(X + Z) Absorption Law Using this law, we absorb similar variables, i.e., X.(X + Y) = X X + XY = X De Morgan’s Law or De Morgan’s Theorem This law states that the operation of an OR or an AND logic circuit stays unchanged whenever all inputs are inverted, while the operator actually changes from AND to OR whenever the outputs are inverted, i.e., (X.Y)’ = X’ + Y’ (X + Y)’ = X’.Y’ De-Morgan's First Theorem: According to the first theorem, the complement result of the AND operation is equal to the OR operation of the complement of that variable. Thus, it is equivalent to the NAND function and is a negative-OR function proving that (A.B)' = A'+B' and we can show this using the following table. A B A.B (A.B)’ A’ B’ A’+B’ 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 ,Prof. Likhitha, CSE, NCET 3 Digital Design and Computer Organization 23CSI32 De-Morgan's Second Theorem: According to the second theorem, the complement result of the OR operation is equal to the AND operation of the complement of that variable. Thus, it is the equivalent of the NOR function and is a negative-AND function proving that (A+B)' = A'.B' and we can show this using the following truth table. A B A+B (A+B)’ A’ B’ A’.B’ 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 Logic Gates ,Prof. Likhitha, CSE, NCET 4 Digital Design and Computer Organization 23CSI32 A logic gate is a building block of a digital circuit. Most logic gates have two inputs and one output and are based on Boolean algebra. At any given moment, every terminal is in one of the two binary conditions false (low) or true (high). False represents 0, and true represents 1. Depending on the type of logic gate being used and the combination of inputs, the binary output will differ. A logic gate can be thought of like a light switch, wherein one position the output is off (0), and in another, it is on (1). Logic gates are commonly used in integrated circuits (IC). Basic Logic gates AND gate An AND gate can have two or more inputs, its output is true if all inputs are true. The output Q is true if input A AND input B are both true: Q = A. B Input Input Output Q A B 0 0 0 0 1 0 1 0 0 1 1 1 Logical symbol OR gate An OR gate can have two or more inputs, its output is true if at least one input is true. The output Q is true if input A OR input B is true (or both of them are true): Q = A + B Input A Input B Output Q 0 0 0 0 1 1 1 0 1 ,Prof. Likhitha, CSE, NCET 5 Digital Design and Computer Organization 23CSI32 1 1 1 NOT gate (inverter) A NOT gate can only have one input and the output is the inverse of the input. A NOT gate is also called an inverter. The output Q is true when the input A is NOT true: Q = 𝐴 Logical symbol Universal Gates: NAND gate This is an AND gate with the output inverted, as shown by the 'o' on the symbol output. A NAND gate can have two or more inputs, its output is true if NOT all inputs are true. The output Q is true if input A AND input B are NOT both true: Q = 𝐴. 𝐵 Input A Input B Output Q 0 0 1 0 1 1 1 0 1 1 1 0 ,Prof. Likhitha, CSE, NCET 6 Digital Design and Computer Organization 23CSI32 Logical symbol NOR gate This is an OR gate with the output inverted, as shown by the 'o' on the symbol output. A NOR gate can have two or more inputs, its output is true if no inputs are true. The output Q is true if NOT inputs A OR B are true: Q = 𝐴 + 𝐵 Input A Input B Output Q 0 0 1 0 1 0 1 0 0 1 1 0 Exclusive gates EX-OR gate EXclusive-OR. This is like an OR gate but excluding both inputs being true. The output is true if inputs A and B are DIFFERENT. EX-OR gates can only have 2 inputs. The output Q is true if either input A is true OR input B is true, but not when both of them are true: Q = A ⊕ B Input A Input B Output Q 0 0 0 0 1 1 1 0 1 1 1 0 ,Prof. Likhitha, CSE, NCET 7 Digital Design and Computer Organization 23CSI32 Logical symbol EX-NOR gate EXclusive-NOR. This is an EX-OR gate with the output inverted, as shown by the 'o' on the symbol output. EX-NOR gates can only have 2 inputs. The output Q is true if inputs A and B are the SAME (both true or both false): Q = 𝐴 ⊕ 𝐵 Input A Input B Output Q 0 0 1 0 1 0 1 0 0 1 1 1 NAND and NOR Implementation Why NAND and NOR gates are called Universal gates? NOR gates and NAND gates have the particular property that any one of them can create any logical Boolean expression if appropriately designed. Meaning that you can create any logical Boolean expression using ONLY NOR gates or ONLY NAND gates. Other logical gates do not have this property. ,Prof. Likhitha, CSE, NCET 8 Digital Design and Computer Organization 23CSI32 NOR Gate Operations ,Prof. Likhitha, CSE, NCET 9 Digital Design and Computer Organization 23CSI32 The Map Method (Karnaugh Map): The Karnaugh Map also called as K Map is a graphical representation that provides a systematic method for simplifying the boolean expressions. For a boolean expression consisting of n-variables, number of cells required in K Map = 2n cells. Two Variable K Map- Two variable K Map is drawn for a boolean expression consisting of two variables. The number of cells present in two variable K Map = 22 = 4 cells. So, for a boolean function consisting of two variables, we draw a 2 x 2 K Map. Two variable K Map may be represented as- Here, A and B are the two variables of the given boolean function. Three Variable K Map- Three variable K Map is drawn for a boolean expression consisting of three variables. The number of cells present in three variable K Map = 23 = 8 cells. So, for a boolean function consisting of three variables, we draw a 2 x 4 K Map. Three variable K Map may be represented as- Prof. Likhitha, CSE, NCET 10 Digital Design and Computer Organization 23CSI32 Here, A, B and C are the three variables of the given boolean function. Four Variable K Map- Four variable K Map is drawn for a boolean expression consisting of four variables. The number of cells present in four variable K Map = 24 = 16 cells. So, for a boolean function consisting of four variables, we draw a 4 x 4 K Map. Four variable K Map may be represented as- Prof. Likhitha, CSE, NCET 11 Digital Design and Computer Organization 23CSI32 Karnaugh Map Simplification Rules- To minimize the given boolean function, We draw a K Map according to the number of variables it contains. We fill the K Map with 0’s and 1’s according to its function. Then, we minimize the function in accordance with the following rules. Rule-01: We can either group 0’s with 0’s or 1’s with 1’s but we can not group 0’s and 1’s together. X representing don’t care can be grouped with 0’s as well as 1’s. Rule-02: Groups may overlap each other. Rule-03: We can only create a group whose number of cells can be represented in the power of 2. In other words, a group can only contain 2n i.e. 1, 2, 4, 8, 16 and so on number of cells. Prof. Likhitha, CSE, NCET 12 Digital Design and Computer Organization 23CSI32 Rule-04: Groups can be only either horizontal or vertical. We can not create groups of diagonal or any other shape. Rule-05: Each group should be as large as possible. Rule-06: Opposite grouping and corner grouping are allowed. The example of opposite grouping is shown illustrated in Rule-05. The example of corner grouping is shown below. Prof. Likhitha, CSE, NCET 13 Digital Design and Computer Organization 23CSI32 PROBLEMS BASED ON KARNAUGH MAP- Problem-01: Minimize the following boolean function- F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15) Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C, D) = (A’B + AB)(C’D + CD) + (A’B’ + A’B + AB + AB’)C’D + (A’B’ + AB’)(C’D’ + CD’) = BD + C’D + B’D’ Prof. Likhitha, CSE, NCET 14 Digital Design and Computer Organization 23CSI32 Thus, minimized boolean expression is- F(A, B, C, D) = BD + C’D + B’D’ Problem-02: Minimize the following boolean function- F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15) Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C, D) = (A’B’ + A’B + AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D) = D + B’C’ Thus, minimized boolean expression is- F(A, B, C, D) = B’C’ + D Problem-03: Minimize the following boolean function- F(A, B, C, D) = Σm(1, 3, 4, 6, 8, 9, 11, 13, 15) + Σd(0, 2, 14) Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Prof. Likhitha, CSE, NCET 15 Digital Design and Computer Organization 23CSI32 Then, we have- Now, F(A, B, C, D) = (AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D) + (A’B’ + A’B) (C’D’ + CD’) = AD + B’D + B’C’ + A’D’ Thus, minimized boolean expression is- F(A, B, C, D) = AD + B’D + B’C’ + A’D’ Problem-04: Minimize the following boolean function- F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 5) Solution- Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C) = A'(B’C’ + B’C) + A(BC + BC’) = A’B’ + AB Prof. Likhitha, CSE, NCET 16 Digital Design and Computer Organization 23CSI32 Thus, minimized boolean expression is- F(A, B, C) = AB + A’B’ NOTE- It may be noted that there is no need of considering the quad group. This is because even if we consider that group, we will have to consider the other two duets. So, there is no use of considering that quad group. Problem-05: Minimize the following boolean function- F(A, B, C) = Σm(1, 2, 5, 7) + Σd(0, 4, 6) Solution- Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C) = (A + A’)(B’C’ + B’C) + A(B’C’ + B’C + BC + BC’) + (A + A’)(B’C’ + BC’) = B’ + A + C’ Thus, minimized boolean expression is- F(A, B, C) = A + B’ + C’ Problem-06: Minimize the following boolean function- F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 4, 5) Prof. Likhitha, CSE, NCET 17 Digital Design and Computer Organization BCS302 Solution- Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C) = (A + A’)(B’C’ + B’C) + A(B’C’ + B’C + BC + BC’) = B’ + A Thus, minimized boolean expression is- F(A, B, C) = A + B’ Problem-07: Minimize the following boolean function- F(A, B, C, D) = Σm(0, 2, 8, 10, 14) + Σd(5, 15) Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- VVIET, Mysore 18 Digital Design and Computer Organization 23CSI32 Now, F(A, B, C, D) = (AB + AB’)CD’ + (A’B’ + AB’)(C’D’ + CD’) = ACD’ + B’D’ Thus, minimized boolean expression is- F(A, B, C, D) = ACD’ + B’D’ Problem-08: Minimize the following boolean function- F(A, B, C, D) = Σm(3, 4, 5, 7, 9, 13, 14, 15) Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(A, B, C, D) = A’B(C’D’ + C’D) + (A’B’ + A’B)(CD) + (AB + AB’)(C’D) + AB(CD + CD’) = A’BC’ + A’CD + AC’D + ABC Thus, minimized boolean expression is- F(A, B, C, D) = A’BC’ + A’CD + AC’D + ABC Problem-09: Consider the following boolean function- F(W, X, Y, Z) = Σm(1, 3, 4, 6, 9, 11, 12, 14) Prof. Likhitha, CSE, NCET 19 Digital Design and Computer Organization 23CSI32 Solution- Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function. Then, we form the groups in accordance with the above rules. Then, we have- Now, F(W, X, Y, Z) = (W’X + WX)(Y’Z’ + YZ’) + (W’X’ + WX’)(Y’Z + YZ) = XZ’ + X’Z =X⊕Z Thus, minimized boolean expression is- F(W, X, Y, Z) = X ⊕ Z Prof. Likhitha, CSE, NCET 20 Digital Design and Computer Organization 23CSI32 HDL What is HDL? HDL stands for Hardware Description Language. It is a programming language that is used to describe, simulate, and create hardware like digital circuits (ICS). HDL is mainly used to discover the faults in the design before implementing it in the hardware. The main advantage of HDLs is that it provides flexible modeling capabilities and can express the large complex designs (>107gates). Today, there are many HDLs available in the market, but VHDL and Verilog are the most popular HDLs. What is VHDL? VHDL stands for Very High-Speed Integration Circuit HDL (Hardware Description Language). It is an IEEE (Institute of Electrical and Electronics Engineers) standard hardware description language that is used to describe and simulate the behavior of complex digital circuits. The most popular examples of VHDL are Odd Parity Generator, Pulse Generator, Priority Encoder, Behavioral Model for 16 words, 8bit RAM, etc. VHDL supports the following features: Design methodologies and their features. Sequential and concurrent activities. Design exchange Standardization Documentation Readability Large-scale design A wide range of descriptive capability What is Verilog? Verilog is also a HDL (Hardware Description Languages) for describing electronic circuits and systems. It is used in both hardware simulation and synthesis. The most popular examples of Verilog are network switch, a microprocessor, a memory, a simple flip-flop, etc. When we think of any digital circuit, either it is a combinational or a sequential circuit, we have three aspects in our mind. They are:- Prof. Likhitha, CSE, NCET 21 Digital Design and Computer Organization 23CSI32 1. Circuit diagram or schematic, 2. Logical Expression, 3. and Truth table. Syntax of Verilog module (Port_List) //Statement endmodule Here module and endmodule are pair of the compiler directives. So, when comes to Verilog HDL or any HDL, there are three aspects of Modelling: 1. Structural or Gate-level modelling, 2. Dataflow modelling, 3. Behavioral modelling. These three modelling aspects in Verilog HDL relate to those three aspects of a digital circuit respectively. Let’s glide into the next section… Structural/Gate-level Modelling: The Circuit diagram of a digital circuit shows the logic gates present in it. Likewise in Structural modelling, we model a circuit by using Primitive gates, and predefined modules. When we design a Verilog code entirely using Primitive Logic Gates, it is called “Gate Level Modelling“. This is Lowest level abstraction, and it is hard to understand the intent of the code by the human, but is easy and guaranteed for machine compiling and logical synthesis. If we create smaller modules using Logic gates, and then we use those small modules to create a big circuit, it is called “Structural Modelling“. We connect Gates and modules using wires here. Example:- module andgate(a,b,y); Prof. Likhitha, CSE, NCET 22 Digital Design and Computer Organization 23CSI32 input a,b; output y; and(y,a,b); endmodule Dataflow Modelling: Dataflow modelling is completely done by the logical expression of the digital circuit. We have logical and arithmetic operators in Verilog, which we can use to create logical expressions of the digital circuit. This is a medium level abstraction. This type of modelling along with structural modelling is Highly Recommended in ASIC design. Example module andgate(a,b,y); input a,b; output y; assign y = a & b; endmodule Behavioral Modelling: The behavioural modelling completely depends on the truth table or behaviour of the circuit. In this modelling, we can design hardware without even knowing the components present in it, because it doesn’t care. If we know the behaviour of the circuit, we can design it. This is the highest level abstraction. This modelling is recommended for FPGA prototyping and other Reconfigurable devices. Example module AND_Gate_tb; reg A; reg B; Prof. Likhitha, CSE, NCET 23 Digital Design and Computer Organization 23CSI32 wire Y; AND_Gate uut(.A(A),.B(B),.Y(Y)); initial begin A = 0; B = 0; #5; A = 0; B = 1; #5; A = 1; B = 0; #5; A = 1; B = 1; #5; end endmodule *** Prof. Likhitha, CSE, NCET 24