Digital Design and Computer Organization Notes PDF

Digital Design and Computer Organization(BCS302) MODULE-1 Introduction to Digital Design Syllabus Introduction to Digital Design: Binary Logic, Basic Theorems And Properties Of Boolean Algebra, Boo...

Digital Design and Computer Organization(BCS302) MODULE-1 Introduction to Digital Design Syllabus Introduction to Digital Design: Binary Logic, Basic Theorems And Properties Of Boolean Algebra, Boolean Functions, Digital Logic Gates, Introduction, The Map Method, Four-Variable Map, Don’t-Care Conditions, NAND and NOR Implementation, Other Hardware Description Language – Verilog Model of a simple circuit. Text book 1: 1.9, 2.4, 2.5, 2.8, 3.1, 3.2, 3.3, 3.5, 3.6, 3.9 Text book 1: M. Morris Mano & Michael D. Ciletti, Digital Design With an Introduction to Verilog Design, 5e, Pearson Education. BINARY LOGIC 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 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. Example, x.y = z or xy = z is read “x AND y is equal to z.” If z = 1 if and only if x = 1 and y = 1; otherwise z = 0. The result of the operation x.y is z. x, y, and z are binary variables and can be equal either to 1 or 0 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 (or by an overbar). For example, x’= z (or x = z ) is read “not x is equal to z,”. If x = 1, then z = 0, and 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. Truth table  A truth table is a table of all possible combinations of the variables, showing the relation between the values that the variables may take and the result of the operation.  The truth tables for the operations AND and OR with variables x and y are obtained by listing all possible values that the variables may have when combined in pairs. Page 1  Digital Design and Computer Organization(BCS302) Gates: “A digital circuit having one or more input signals but only one output signal is called a gate”. Logic Gates: “The gates which perform logical operation is called logic gates”. It take binary input and gives binary outputs. The output of the logic gates can be understood using truth table, which contains inputs, outputs of logic circuits. Logic gates are electronic circuits that operate on one or more input signals to produce an output signal. Fig: Symbols for digital logic circuits The timing diagrams illustrate the idealized response of each gate to the four input signal combinations. The horizontal axis of the timing diagram represents the time, and the vertical axis shows the signal as it changes between the two possible voltage levels. The low level represents logic 0, the high level logic 1. The AND gate responds with a logic 1 output signal when both input signals are logic 1. The OR gate responds with a logic 1 output signal if any input signal is logic 1. The NOT gate is commonly referred to as an inverter. The output signal inverts the logic sense of the input signal. Page 2  Digital Design and Computer Organization(BCS302) Gates with multiple inputs Input-Output Signals for gates Timing Diagram BASIC THEOREMS AND PROPERTIES OF BOOLEAN ALGEBRA: Duality:  The important property of Boolean algebra is called the duality principle and states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged.  In a two‐valued Boolean algebra, the identity elements and the elements of the set B are the same: 1 and 0. The duality principle has many applications.  If the dual of an algebraic expression is desired, we simply interchange OR and AND operators and replace 1’s by 0’s and 0’s by 1’s. Basic Theorems  Table 1 lists out six theorems of Boolean algebra and four of its postulates. The theorems and postulates listed are the most basic relationships in Boolean algebra.  The theorems, like the postulates, are listed in pairs; each relation is the dual of the one paired with it. The postulates are basic axioms of the algebraic structure and need no proof.  The theorems must be proven from the postulates. Page 3  Digital Design and Computer Organization(BCS302) THEOREM 1(a): x + x = x. Statement Justification x + x = (x + x). 1 postulate 2(b) = (x + x)(x + x') 5(a) = x + xx' 4(b) =x+0 5(b) =x 2(a) THEOREM 1(b): x. x = x. Statement Justification x. x = xx + 0 postulate 2(a) = xx + xx' 5(b) = x(x + x') 4(a) =x.1 5(a) =x 2(b) Note that theorem 1(b) is the dual of theorem 1(a) and that each step of the proof in part (b) is the dual of its counterpart in part (a).. THEOREM 2(a): x + 1 = 1. Statement Justification x + 1 = 1. (x + 1) postulate 2(b) = (x + x')(x + 1) 5(a) = x + x'. 1 4(b) = x + x' 2(b) =1 5(a) THEOREM 2(b): x. 0 = 0 by duality. THEOREM 3: (x')' = x. From postulate 5, we have x + x' = 1 and x. x' = 0, which together define the complement of x. The complement of x' is x and is also (x')'. Therefore, since the complement is unique, we have (x')' = x. The theorems involving two or three variables may be proven algebraically from the postulates and the theorems that have already been proven. THEOREM 6(a): x + xy = x. Statement Justification x + xy = x. 1 + xy postulate 2(b) = x(1 + y) 4(a) Page 4  Digital Design and Computer Organization(BCS302) = x(y + 1) 3(a) =x.1 2(a) =x 2(b) THEOREM 6(b): x(x + y) = x by duality.  The theorems of Boolean algebra can be proven by means of truth tables.  In truth tables, both sides of the relation are checked to see whether they yield identical results for all possible combinations of the variables involved.  The following truth table verifies the first absorption theorem: The truth table for the first DeMorgan’s theorem, (x + y)' = x'y', is as follows: The operator precedence for evaluating Boolean expressions is (1) parentheses, (2) NOT, (3) AND, and (4) OR BOOLEAN FUNCTIONS  Boolean algebra is an algebra that deals with binary variables and logic operations.  A Boolean function described by an algebraic expression consists of binary variables, the constants 0 and 1, and the logic operation symbols.  For a given value of the binary variables, the function can be equal to either 1 or 0. Consider the Boolean function F1 = x + y'z The function F1 is equal to 1 if x is equal to 1 or if both y' and z are equal to 1. F1 is equal to 0 otherwise. Therefore, F1 = 1 if x = 1 or if y = 0 and z = 1. Page 5  Digital Design and Computer Organization(BCS302)  A Boolean function expresses the logical relationship between binary variables and is evaluated by determining the binary value of the expression for all possible values of the variables.  A Boolean function can be represented in a truth table. The number of rows in the truth table is 2n, where n is the number of variables in the function.  Table 1 shown below represents the truth table for the function F1. There are eight possible binary combinations for assigning bits to the three variables x, y, and z.  The table shows that the function is equal to 1 when x = 1 or when yz = 01 and is equal to 0 otherwise. Table 1  A Boolean function can be transformed from an algebraic expression into a circuit diagram composed of logic gates connected in a particular structure. o The logic‐circuit diagram for F1 is shown in Fig. 2.1. There is an inverter for input y to generate its complement. There is an AND gate for the term y'z and an OR gate that combines x with y'z. Consider, for example, the following Boolean function:F2 = x'y'z + x'yz + xy'  A schematic of an implementation of this function with logic gates is shown in Fig. 2.2(a).  Input variables x and y are complemented with inverters to obtain x' and y'. The three terms in the expression are implemented with three AND gates. The OR Page 6  Digital Design and Computer Organization(BCS302) gate forms the logical OR of the three terms. The truth table for F2 is listed in Table 2.2. Now consider the possible simplification of the function by applying some of the identities of Boolean algebra: F2 = x'y'z + x'yz + xy' = x'z(y' + y) + xy' = x'z + xy'  The function is reduced to only two terms and can be implemented with gates as shown in Fig. 2.2(b). It is obvious that the circuit in (b) is simpler than the one in (a), yet both implement the same function.  By means of a truth table, it is possible to verify that the two expressions are equivalent. The simplified expression is equal to 1 when xz = 01 or when xy = 10.  In general, there are many equivalent representations of a logic function. Finding the most economic representation of the logic is an important design task. x’ Y’ ’ Page 7 Digital Design and Computer Organization(BCS302) Page 8  Digital Design and Computer Organization(BCS302) DIGITAL LOGIC GATES  Since Boolean functions are expressed in terms of AND, OR, and NOT operations, it is easier to implement a Boolean function with these type of gates.  Factors to be weighed in considering the construction of other types of logic gates are (1) the feasibility and economy of producing the gate with physical components, (2) the possibility of extending the gate to more than two inputs, (3) the basic properties of the binary operator, such as commutativity and associativity, and (4) the ability of the gate to implement Boolean functions alone or in conjunction with other gates.  The graphic symbols and truth tables of the eight gates are shown in Fig. 2.5. Each gate has one or two binary input variables, designated by x and y, and one binary output variable, designated by F.  The inverter circuit inverts the logic sense of a binary variable, producing the NOT, or complement, function. The small circle in the output of the graphic symbol of an inverter (referred to as a bubble) designates the logic complement.  The NAND function is the complement of the AND function, as indicated by a graphic symbol that consists of an AND graphic symbol followed by a small circle.  The NOR function is the complement of the OR function and uses an OR graphic symbol followed by a small circle.  NAND and NOR gates are used extensively as standard logic gates and are in fact far more popular than the AND and OR gates. This is because NAND and NOR gates are easily constructed with transistor circuits and because digital circuits can be easily implemented with them.  The exclusive‐OR gate has a graphic symbol similar to that of the OR gate, except for the additional curved line on the input side. The equivalence, or exclusive‐NOR, gate is the complement of the exclusive‐OR, as indicated by the small circle on the output side of the graphic symbol. Page 9  Digital Design and Computer Organization(BCS302) THE MAP METHOD  The map method provides a simple, straightforward procedure for minimizing Boolean functions. This method may be regarded as a pictorial form of a truth table. The map method is also known as the Karnaugh map or K-map.  A K-map is a diagram made up of squares, with each square representing one minterm of the function that is to be minimized.  Since any Boolean function can be expressed as a sum of minterms, it follows that a Boolean function is recognized graphically in the map from the area enclosed by those squares whose minterms are included in the function.  Map represents a visual diagram of all possible ways a function may be expressed in standard form. By recognizing various patterns, the user can derive alternative algebraic expressions for the same function, from which the simplest can be selected. Page 10  Digital Design and Computer Organization(BCS302)  The simplified expressions produced by the map are always in one of the two standard forms: sum of products or product of sums.  The simplest algebraic expression is an algebraic expression with a minimum number of terms and with the smallest possible number of literals(variable) in each term. This expression produces a circuit diagram with a minimum number of gates and the minimum number of inputs to each gate. FOUR-VARIABLE K-MAP  The map for Boolean functions of four binary variables (w, x, y, z) is shown in Fig. 3.8. In Fig. 3.8(a) are listed the 16 minterms and the squares assigned to each.  In Fig. 3.8(b), the map is redrawn to show the relationship between the squares and the four variables. The rows and columns are numbered in a Gray code sequence, with only one digit changing value between two adjacent rows or columns.  The minterm corresponding to each square can be obtained from the concatenation of the row number with the column number. For example, the numbers of the third row (11) and the second column (01), when concatenated, give the binary number 1101, the binary equivalent of decimal 13. Thus, the square in the third row and second column represents minterm m13.  One square represents one minterm, giving a term with four literals. Two adjacent squares represent a term with three literals.  Four adjacent squares represent a term with two literals. Eight adjacent squares represent a term with one literal. Page 11  Digital Design and Computer Organization(BCS302)  Sixteen adjacent squares produce a function that is always equal to No other combination of squares can simplify the function. 1)Simplify the Boolean function F (w, x, y, z) = Σm (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) Since the function has four variables, a four-variable map must be used. The minterms listed in the sum are marked by 1’s in the map of Fig. 3.9. Eight adjacent squares marked with 1’s can be combined to form the one literal term y'. The remaining three 1’s on the right cannot be combined to give a simplified term; they must be combined as two or four adjacent squares. The larger the number of squares combined, the smaller is the number of literals in the term. In this example, the top two 1’s on the right are combined with the top two 1’s on the left to give the term w'z'. These squares make up the two middle rows and the two end columns, giving the term xz'. The simplified function is Page 12  Digital Design and Computer Organization(BCS302) 2) Simplify the Boolean function F = A'B'C' + B'CD' + A'BCD' + AB'C' F=A’B’C’(D+D’)+B’CD’(A+A’)+A’BCD’+AB’C’(D+D’) F=A’B’C’D’+A’B’C’D+AB’CD’+A’B’CD’ +A’BCD’+AB’C’D+AB’C’D’ 2 quad 1 quad B’D’ The simplified function is Page 13  Digital Design and Computer Organization(BCS302) F = B'D' + B'C' + A'CD' 3) Solve S= F(A,B,C)=Σ m(0, 1, 3, 5, 6, 7, 11, 12, 14) using Kmap and implement using basic gates. OR OR 4) Solve S=Σ M(0,1, 2, 4, 5,6, 8,9,10,12,13) using Kmap Page 14  Digital Design and Computer Organization(BCS302) 5) Solve S= F(A,B,C,D)=Σm(7,9,10,11,12,13,14,15) using K map to get minimum SOP expression. Solve S=F(A,B,C,D)=Σm(1,2,3,6,8,9,10,12,13,14) using K map to get minimum SOP expression. Page 15  Digital Design and Computer Organization(BCS302) Prime Implicants In choosing adjacent squares in a map, we must ensure that (1) all the minterms of the function are covered when we combine the squares. (2) the number of terms in the expression is minimized, and (3) there are no redundant terms (i.e., Minterms already covered by other terms). A prime implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map. The prime implicants of a function can be obtained from the map by combining all possible maximum numbers of squares. prime implicants are the building blocks used in the simplification of Boolean functions Essential Prime Implicant: An essential prime implicant is a prime implicant that covers at least one minterm that no other prime implicant covers. essential prime implicants are a subset of prime implicants that are necessary to cover specific minterms in order to achieve a minimal representation of the Boolean function. 1) Simplify following four-variable Boolean function: F( A, B, C, D) = Σm (0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15) The simplified expression is obtained from the logical sum of the two essential prime implicants and any two prime implicants that cover minterms m3, m9, and m11.. Essential Prime Implicants are BD and B’D’ Prime Implicants are B’D’,CD,BD,AD There are four possible ways that the function can be expressed with four product terms of two literals each: F = BD + B'D' + CD + AD = BD + B'D' + CD + AB' = BD + B'D' + B'C + AD Page 16  Digital Design and Computer Organization(BCS302) = BD + B'D' + B'C + AB' DON’T-CARE CONDITIONS  The logical sum of the minterms associated with a Boolean function specifies the conditions under which the function is equal to 1. The function is equal to 0 for the rest of the minterms. This pair of conditions assumes that all the combinations of the values for the variables of the function are valid.  In some applications the function is not specified for certain combinations of the variables.  Functions that have unspecified outputs for some input combinations are called incompletely specified functions.  In most applications, we simply don’t care what value is assumed by the function for the unspecified minterms. For this reason, it is customary to call the unspecified minterms of a function don’t-care conditions. These don’t-care conditions can be used on a map to provide further simplification of the Boolean expression.  A don’t-care minterm is a combination of variables whose logical value is not specified. Such a minterm cannot be marked with a 1 in the map, because it would require that the function always be a 1 for such a combination. Likewise, putting a 0 on the square requires the function to be 0. To distinguish the don’t- care condition from 1’s and 0’s, an X is used.  Thus, an X inside a square in the map indicates that we don’t care whether the value of 0 or 1 is assigned to F for the particular minterm.  In choosing adjacent squares to simplify the function in a map, the don’t-care min- terms may be assumed to be either 0 or 1. When simplifying the function, we can choose to include each don’t-care minterm with either the 1’s or the 0’s, depending on which combination gives the simplest expression. Simplify the Boolean function F (w, x, y, z) = (1, 3, 7, 11, 15)which has the don’t-care conditions d (w, x, y, z) = (0, 2, 5) The minterms of F are the variable combinations that make the function equal to 1. The minterms of d are the don’t-care minterms that may be assigned either 0 or 1. The map simplification is shown in Fig. 3.15. The minterms of F are marked by 1’s, those of d are marked by X’s, and the remaining squares are filled with 0’s. To get the simplified expres- sion in sum-of-products form, we must include all five 1’s in the map, but we may or may not include any of the X’s, depending on the way the function is simplified. The term yz covers the four minterms in the third column.The remaining minterm, m1, can be combined Page 17  Digital Design and Computer Organization(BCS302) OR with minterm m3 to give the three-literal term w'x'z. However, by including one or two adjacent X’s we can combine four adjacent squares to give a two-literal term. In Fig. 3.15(a), don’t-care minterms 0 and 2 are included with the 1’s, resulting in the simpli- fied function F = yz + w'x' In Fig. 3.15(b), don’t-care minterm 5 is included with the 1’s, and the simplified function is now F = yz + w'z Either one of the preceding two expressions satisfies the conditions stated for this example. Solve S=F(A,B,C,D)=Σm(7)+d(10,11,12,13,14,15) using K map to get minimum SOP expression Solve S =F(A,B,C,D)=Σm(2,3,5,7,10,12)+d(11,15) using K map to get minimum SOP expression Page 18  Digital Design and Computer Organization(BCS302) Solve S=F(A,B,C,D)=Σm(6,7,9,10,13)+d(1,4,5,11) using K map to get minimum SOP expression. NAND AND NOR IMPLEMENTATION  Digital circuits are frequently constructed with NAND or NOR gates rather than with AND and OR gates.  NAND and NOR gates are easier to fabricate with electronic components and are the basic gates used in all IC digital logic families. NAND Circuits  The NAND gate is said to be a universal gate because any logic circuit can be implemented with it. To show that any Boolean function can be implemented with NAND gates, we need only show that the logical operations of AND, OR, and complement can be obtained with NAND gates alone. This is indeed shown in Fig. 3.16.  The complement operation is obtained from a one-input NAND gate that behaves exactly like an inverter. The AND operation requires two NAND gates. The first produces the NAND operation and the second inverts the logical sense of the signal. The OR operation is achieved through a NAND gate with additional inverters in each input.  A convenient way to implement a Boolean function with NAND gates is to obtain the simplified Boolean function in terms of Boolean operators and then convert the function to NAND logic.  The conversion of an algebraic expression from AND, OR, and complement to NAND can be done by simple circuit manipulation techniques that change AND– OR diagrams to NAND diagrams.  Two equivalent graphic symbols for the NAND gate are shown in Fig. 3.17. The AND-invert symbol has been defined previously and consists Page 19  Digital Design and Computer Organization(BCS302) of an AND graphic symbol followed by a small circle negation indicator referred to as a bubble.  It is possible to represent a NAND gate by an OR graphic symbol that is preceded by a bubble in each input. The invert-OR symbol for the NAND gate follows DeMorgan’s theorem and the convention that the negation indicator (bubble) denotes complementation. The two graphic symbols’ representations are useful in the analysis and design of NAND circuits. When both symbols are mixed in the same diagram, the circuit is said to be in mixed notation. Two-Level Implementation  The implementation of Boolean functions with NAND gates requires that the functions be in sum-of-products form. To see the relationship between a sum- of-products expression and its equivalent NAND implementation, consider the logic diagrams drawn in Fig. 3.18. All three diagrams are equivalent and implement the function F = AB + CD  The function is implemented in Fig. 3.18(a) with AND and OR gates. In Fig. 3.18(b), the AND gates are replaced by NAND gates and the OR gate is replaced by a NAND gate with an OR-invert graphic symbol. Remember that a bubble denotes complementation and two bubbles along the same line represent double complementation, so both can be removed. Page 20  Digital Design and Computer Organization(BCS302)  Removing the bubbles on the gates of (b) produces the circuit of (a). Therefore, the two diagrams implement the same function and are equivalent.  In Fig. 3.18(c), the output NAND gate is redrawn with the AND-invert graphic symbol. In drawing NAND logic diagrams, the circuit shown in either Fig. 3.18(b) or (c) is acceptable.  The one in Fig. 3.18(b) is in mixed notation and represents a more direct relationship to the Boolean expression it implements. The NAND implementation in Fig. 3.18(c) can be verified algebraically.  The function it implements can easily be converted to sum-of- products form by DeMorgan’s theorem: F = ((AB)'(CD)')' = AB + CD Implement the following Boolean function with NAND gates: F (x, y, z) = (1, 2, 3, 4, 5, 7)  The first step is to simplify the function into sum-of-products form. This is done by means of the map of Fig. 3.19(a), from which the simplified function is obtained: F = xy' + x'y + z  The two-level NAND implementation is shown in Fig. 3.19(b) in mixed notation. Note that input z must have a one-input NAND gate (an inverter) to compensate for the bubble in the second-level gate. An alternative way of drawing the logic diagram is given in Fig. 3.19(c).  Here, all the NAND gates are drawn with the same graphic symbol. The inverter with input z has been removed, but the input variable is complemented and denoted by z' Page 21  Digital Design and Computer Organization(BCS302)  The procedure described in the previous example indicates that a Boolean function can be implemented with two levels of NAND gates. The procedure for obtaining the logic diagram from a Boolean function is as follows: 1. Simplify the function and express it in sum-of-products form. 2. Draw a NAND gate for each product term of the expression that has at least two literals. The inputs to each NAND gate are the literals of the term. This procedure produces a group of first-level gates. 3. Draw a single gate using the AND-invert or the invert-OR graphic symbol in the second level, with inputs coming from outputs of first-level gates. 4. A term with a single literal requires an inverter in the first level. However, if the single literal is complemented, it can be connected directly to an input of the second- level NAND gate. Multilevel NAND Circuits  The standard form of expressing Boolean functions results in a two-level implementation. There are occasions, however, when the design of digital systems results in gating structures with three or more levels.  The most common procedure in the design of multilevel circuits is to express the Boolean function in terms of AND, OR, and complement operations. The function can then be implemented with AND and OR gates. After that, if necessary, it can be converted into an all-NAND circuit. Page 22  Digital Design and Computer Organization(BCS302) Consider, for example, the Boolean function F = A (CD + B) + BC'  The AND–OR implementation is shown in Fig. 3.20(a). There are four levels of gating in the circuit. The first level has two AND gates. The second level has an OR gate followed by an AND gate in the third level and an OR gate in the fourth level.  A logic diagram with a pattern of alternating levels of AND and OR gates can easily be converted into a NAND circuit with the use of mixed notation, shown in Fig. 3.20(b).  The procedure is to change every AND gate to an AND-invert graphic symbol and every OR gate to an invert-OR graphic symbol. The NAND circuit performs the same logic as the AND–OR diagram as long as there are two bubbles along the same line.  The bubble associated with input B causes an extra comple- mentation, which must be compensated for by changing the input literal to B'. The general procedure for converting a multilevel AND–OR diagram into an all-NAND diagram using mixed notation is as follows: 1. Convert all AND gates to NAND gates with AND-invert graphic symbols. 2. Convert all OR gates to NAND gates with invert-OR graphic symbols. 3. Check all the bubbles in the diagram. For every bubble that is not compensated by another small circle along the same line, insert an inverter (a one- input NAND gate) or complement the input literal. As another example, consider the multilevel Boolean function Page 23  Digital Design and Computer Organization(BCS302) F = (AB' + A'B)(C + D')  The AND–OR implementation of this function is shown in Fig. 3.21(a) with three levels of gating. The conversion to NAND with mixed notation is presented in Fig. 3.21(b) of the diagram.  The two additional bubbles associated with inputs C and D' cause these two literals to be complemented to C' and D.  The bubble in the output NAND gate complements the output value, so we need to insert an inverter gate at the output in order to complement the signal again and get the original value back. NOR Implementation  The NOR operation is the dual of the NAND operation. Therefore, all procedures and rules for NOR logic are the duals of the corresponding procedures and rules developed for NAND logic.  The NOR gate is another universal gate that can be used to implement any Boolean function. The implementation of the complement, OR, and AND operations with NOR gates is shown in Fig. 3.22.  The complement operation is obtained from a one- input NOR gate that behaves exactly like an inverter.The OR operation requires two NOR gates, and the AND operation is obtained with a NOR gate that has inverters in each input.  The two graphic symbols for the mixed notation are shown in Fig. 3.23. The OR- invert symbol defines the NOR operation as an OR followed by a complement. The invert-AND symbol complements each input and then performs an AND Page 24  Digital Design and Computer Organization(BCS302) operation. The two symbols designate the same NOR operation and are logically identical because of DeMorgan’s theorem.  A two-level implementation with NOR gates requires that the function be simplified into product-of-sums form.  Remember that the simplified product-of-sums expression is obtained from the map by combining the 0’s and complementing. A product-of-sums expression is implemented with a first level of OR gates that produce the sum terms followed by a second-level AND gate to produce the product.  The transformation from the OR–AND diagram to a NOR diagram is achieved by changing the OR gates to NOR gates with OR-invert graphic symbols and the AND gate to a NOR gate with an invert-AND graphic symbol.  A single literal term going into the second-level gate must be complemented. Figure 3.24 shows the NOR implementation of a function expressed as a product of sums: F = (A + B)(C + D)E The OR–AND pattern can easily be detected by the removal of the bubbles along the same line. Variable E is complemented to compensate for the third bubble at the input of the second-level gate. The procedure for converting a multilevel AND–OR diagram to an all-NOR diagram is similar to the one presented for NAND gates. For the NOR case, we must convert each OR gate to an OR-invert symbol and each AND gate to an invert-AND symbol. Any bubble that is not compensated by another bubble along the same line needs an inverter, or the complementation of the input literal. NOR implementation for the following function F = (A + B)(C + D)E in Fig3.24 NOR implementation for the following Boolean function is Page 25  Digital Design and Computer Organization(BCS302) F = (AB' + A'B)(C + D') in Fig:3.25 The equivalent AND–OR diagram can be recognized from the NOR diagram by removing all the bubbles. To compensate for the bubbles in four inputs, it is necessary to complement the corresponding input literals. Hardware Description Language A hardware description language (HDL) is a computer-based language that describes the hardware of digital systems in a textual form. It resembles an ordinary computer programming language, such as C, but is specifically oriented to describing hardware structures and the behavior of logic circuits. It can be used to represent logic diagrams, truth tables, Boolean expressions, and complex abstractions of the behavior of a digital system. One way to view an HDL is to observe that it describes a relationship between signals that are the inputs to a circuit and the signals that are the outputs of the circuit. For example, an HDL description of an AND gate describes how the logic value of the gate’s output is determined by the logic values of its inputs. Page 26  Digital Design and Computer Organization(BCS302) HDL is used to represent and document digital systems in a form that can be read by both humans and computers and is suitable as an exchange language between designers. Companies that design integrated circuits use proprietary and public HDLs. In the public domain, there are two standard HDLs that are supported by the IEEE: VHDL and Verilog. Verilog is an easier language than VHDL to describe, learn, and use, we have chosen it for this book. A Verilog model is composed of text using keywords, of which there are about 100. Keywords are predefined lowercase identifiers that define the language constructs. Examples of keywords are module, endmodule, input, output, wire, and, or, and not. Any text between two forward slashes ( // ) and the end of the line is interpreted as a comment and will have no effect on a simulation using the model Multiline comments begin with / * and terminate with * /. Verilog is case sensitive, which means that uppercase and lowercase letters are distinguishable (e.g., not is not the same as NOT). A module is the fundamental descriptive unit in the Verilog language. It is declared by the keyword module and must always be terminated by the keyword endmodule. There 3 types of modelling: Dataflow modeling describes a system in terms of how data flows through the system. Behavioral modeling describes a system’s behavior or function in an algorithmic fashion. Structural modeling describes a system in terms of its structure and interconnections between components. Page 27  Digital Design and Computer Organization(BCS302) Write a Verilog program for OR gate using i)dataflow modelling ii)Behavioral modelling and iii)structural modelling. 2)write a Verilog code for the following circuit. Page 28  Digital Design and Computer Organization(BCS302) HDL describes a circuit that is specified with the following two Boolean expressions: Page 29  Module-2 Combinational Logic Syllabus: Combinational Logic: Introduction, Combinational Circuits, Design Procedure, Binary Adder- Subtractor, Decoders, Encoders, Multiplexers. HDL Models of Combinational Circuits – Adder, Multiplexer, Encoder. Sequential Logic: Introduction, Sequential Circuits, Storage Elements: Latches, Flip-Flops. Introduction Logic circuits for digital systems may be combinational or sequential. A combinational circuit consists of logic gates whose outputs at any time are determined from only the present combination of inputs. A combinational circuit performs an operation that can be specified logically by a set of Boolean functions. sequential circuits employ storage elements in addition to logic gates. Their outputs are a function of the inputs and the state of the storage elements Because the state of the storage elements is a function of previous inputs, the outputs of a sequential circuit depend not only on present values of inputs, but also on past inputs, and the circuit behavior must be specified by a time sequence of inputs and internal states. combinational circuit A combinational circuit consists of an interconnection of logic gates. Combinational logic gates react to the values of the signals at their inputs and produce the value of the output signal, transforming binary information from the given input data to a required output data.  The n input binary variables come from an external source; the m output variables are produced by the internal combinational logic circuit and go to an external destination. Each input and output variable exists physically as an analog signal whose values are interpreted to be a binary signal that represents logic 1 and logic 0. If the registers are included with the combinational gates, then the total circuit must be considered to be a sequential circuit. For n input variables, there are 𝟐𝒏 possible combinations of the binary inputs. For each possible input combination, there is one possible value for each output variable. Thus, a combinational circuit can be specified with a truth table that lists the output values for each combination of input variables. Design procedure The procedure to design combinational circiut involves the following steps: 1. From the specifications of the circuit, Determine the required number of inputs and outputs and assign a symbol to each. 2. Derive the truth table that defines the required relationship between inputs and outputs. 3. Obtain the simplified Boolean functions for each output as a function of the input variables. 4. Draw the logic diagram and verify the correctness of the design (manually or by simulation). Example for design Procedure Code Conversion (Convert BCD to Excess-3 Code) A code converter is a circuit that makes the two systems compatible even though each uses a different binary code. Since each code uses four bits to represent a decimal digit, there must be four input variables and four output variables. We designate the four input binary variables by the symbols A, B, C, and D, and the four output variables by w, x, y , and z. ADD 3 to BCD to get Excess -3 Code Note that four binary variables may have 16 bit combinations, but only 10 are listed in the truth table. The six bit combinations not listed for the input variables are don’t- care combinations. Binary Adder- Subtractor A combinational circuit that performs the addition of two bits is called a half adder. The addition of three bits (two significant bits and a previous carry) is a full adder. A binary adder–subtractor is a combinational circuit that performs the arithmetic operations of addition and subtraction with binary numbers. The half adder design is carried out first, from which we develop the full adder. Connecting n full adders in cascade produces a binary adder for two n -bit numbers. Half Adder  Half Adder circuit needs two binary inputs and two binary outputs.  output variables produce the sum and carry. We assign symbols x and y to the two inputs and S (for sum) and C (for carry) to the outputs.  The C output is 1 only when both inputs are 1. The S output represents the least significant bit of the sum.  The truth table for the half adder is listed in Table 4.3.  The simplified Boolean functions for the two outputs can be obtained directly from the truth table. The simplified sum-of-products expressions are The logic diagram of the half adder implemented in sum of products is shown in Fig. 4.5(a). It can be also implemented with an exclusive-OR and an AND gate as shown in Fig. 4.5(b) Full Adder A full adder is a combinational circuit that forms the arithmetic sum of three bits. It consists of three inputs and two outputs. Two of the input variables, denoted by x and y , represent the two significant bits to be added. The third input, z , represents the carry from the previous lower significant position. The two outputs are designated by the symbols S for sum and C for carry.  The logic diagram for the full adder implemented in sum-of-products form is shown in Fig. 4.7  Implementation of Full adder using 2 half adder : We know that S=xy’z’ + x’yz’ + xyz + x’y’z C=xy+xz+yz =z’(xy’+x’y)+z(xy+x’y’) =xy+xz(y+y’)+yz(x+x’) =z’(xy’+x’y)+z(x’y+xy’)’ =xy+xyz+xy’z+xyz+x’yz =z’(x ⊕ y)+z(x ⊕ y)’ =xy+xyz+z(xy’+x’y) =z’A+zA’ =xy(1+z)+z(x^y) =z ⊕ A C=xy+z(x⊕y) S=z ⊕ x ⊕y Binary Adder: A binary adder is a digital circuit that produces the arithmetic sum of two binary numbers. It can be constructed with full adders connected in cascade, with the output carry from each full adder connected to the input carry of the next full adder in the chain. n-bit numbers requires a chain of n full adders or a chain of one-half adder and n-1 full adders. Eg:4bit numbers requires a chain of 4 fulladders or one HA and 3FAs. interconnection of four full-adder (FA) circuits to provide a four-bit binary ripple carry adder The augend bits of A and the addend bits of B are designated by subscript numbers from right to left, with subscript 0 denoting the least significant bit. The carries are  connected in a chain through the full adders. The input carry to the adder is C0, and it ripples through the full adders to the output carry C4. The input carry C0 in the least significant position must be 0. The value of Ci+1 in a given significant position is the output carry of the full adder. The carry propagation time is an important attribute of the adder because it limits the speed with which two numbers are added.  1. write Verilog code for 4 bit parallel adder using full adder as component. 2. Write Verilog code for 4 bit adder. There are several techniques for reducing the carry propagation time in a parallel adder. The most widely used technique employs the principle of carry lookahead logic. Carry Propagation Carry Propagation The addition of two binary numbers in parallel implies that all the bits of the augend and addend are available for computation at the same time. Consider the circuit of the full adder shown in Fig. 4.10. If we define two new binary variables.  Gi is called a carry generate , and it produces a carry of 1 when both Ai and Bi are 1, regardless of the input carry Ci. Pi is called a carry propagate , because it determines whether a carry into stage i will propagate into stage i + 1 Binary ADDER-Subtractor The addition and subtraction operations can be combined into one circuit with one common binary adder by including an exclusive-OR gate with each full adder. A four-bit adder–subtractor circuit is shown in Fig. 4.13. The mode input M controls the operation. When M = 0, the circuit is an adder, and when M = 1, the circuit becomes a subtractor. Each exclusive-OR gate receives input M and one of the inputs of B. When M = 0, we have B ⊕0 = B. The full adders receive the value of B , the input carry is 0, and the circuit performs A plus B. When M = 1, we have B ⊕ 1 = B’ and C0 = 1. The B inputs are all complemented and a 1 is added through the input carry. The circuit performs the operation A plus the 2’s complement of B. (The exclusive-OR with output V is for detecting an overflow.) Binary Addition Example: Binary Subtraction Example:  DECODERS A Decoder is a combinational circuit that converts binary information from n input lines to a maximum of 2𝑛 unique output lines. The decoders presented here are called n -to- m -line decoders, where m … 2𝑛. Their purpose is to generate the 2𝑛 (or fewer) minterms of n input variables. Each combination of inputs will assert a unique output. The name decoder is also used in conjunction with other code converters, such as a BCD-to-seven-segment decoder. 2:4 decoder ( 1 of 4 decoder) A 2 to 4 decoder is a combinational logic circuit that takes two input lines, typically labeled A and B, and generates four output lines, usually labeled Q0, Q1, Q2, and Q3. The decoder analyzes the input combination and activates the corresponding output line 3:8 Decoder  A 3 to 8 decoder has three inputs (x,y,z) and eight outputs (D0 to D7).  Based on the 3 inputs one of the eight outputs is selected.  The truth table for 3 to 8 decoder is shown in the below table.  From the truth table, it is seen that only one of eight outputs (D0 to D7) is selected based on three select inputs.  From the truth table, the logic expressions for outputs can be written as follows: Decoders with enable inputs can be connected together to form a larger decoder circuit. Implement 4:16 decoder using 2 3:8 decoder. two 3-to-8-line decoders with enable inputs connected to form a 4-to-16-line decoder. When w =0, the top decoder is enabled and the other is disabled. The bottom decoder outputs are all 0’s, and the top eight outputs generate minterms 0000 to 0111. When w =1, the enable conditions are reversed: The bottom decoder outputs generate minterms 1000 to 1111. Combinational Logic Implementation Implement the following boolean function using 3:8 decoder S(x, y, z) = ∑(1, 2, 4, 7) C(x, y, z) = ∑(3, 5, 6, 7) Since there are three inputs and a total of eight minterms, we need a three-to-eight-line decoder. The decoder generates the eight minterms for x , y , and z. The OR gate for output S forms the logical sum of minterms 1, 2, 4, and 7. The OR gate for output C forms the logical sum of minterms 3, 5, 6, and 7. Exemplify(Implement) the following function using 3:8 decoder i) f(a,b, c,d)=∑m (L,2, 3,4) ii) f(a,b, c, d)=∑m (3,5,7 ) Encoder An encoder is a digital circuit that performs the inverse operation of a decoder.  An encoder has 2𝑛 (or fewer) input lines and n output lines. 4:2 Encoder(n=2) 4:2 Encoder 8:3 Encoder an encoder is the octal-to-binary encoder whose truth table is given in Table 4.7 It has eight inputs (one for each of the octal digits) and three outputs that generate the corresponding binary number. It is assumed that only one input has a value of 1 at any given time. The encoder can be implemented with OR gates whose inputs are determined directly from the truth table Output z is equal to 1 when the input octal digit is 1, 3, 5, or 7. Output y is 1 for octal digits 2, 3, 6, or 7, and output x is 1 for digits 4, 5, 6, or 7.  The encoder defined in Table 4.7 has the limitation that only one input can be active at any given time. If two inputs are active simultaneously, the output produces an undefined combination. For example, if D3 and D6 are 1 simultaneously, the output of the encoder will be 111 because all three outputs are equal to 1. To resolve this ambiguity, encoder circuits must establish an input priority to ensure that only one input is encoded. The output 111 does not represent either binary 3 or binary 6. To resolve this ambiguity, encoder circuits must establish an input priority to ensure that only one input is encoded. If we establish a higher priority for inputs with higher subscript numbers, and if both D3 and D6 are 1 at the same time, the output will be 110 because D6 has higher priority than D3. Another ambiguity in the octal-to-binary encoder is  that an output with all 0’s is generated when all the inputs are 0; but this output is the same as when D0 is equal to 1. The discrepancy can be resolved by providing one more output to indicate whether at least one input is equal to 1. Priority Encoder A priority encoder is an encoder circuit that includes the priority function. The operation of the priority encoder is such that if two or more inputs are equal to 1 at the same time, the input having the highest priority will take precedence. The truth table of a four-input priority encoder is given in Table 4.8 In addition to the two outputs x and y , the circuit has a third output designated by V ; this is a valid bit indicator that is set to 1 when one or more inputs are equal to 1.. If all inputs are 0, there is no valid input and V is equal to 0. The other two outputs are not inspected when V equals 0 and are specified as don’t-care conditions. Input D3 has the highest priority, so, regardless of the values of the other inputs, when this input is 1, the output for xy is 11 (binary 3). D2 has the next priority level. The output is 10 if D2 = 1, provided that D3 = 0, regardless of the values of the other two lower priority inputs. The output for D1 is generated only if higher priority inputs are 0. D0 D1 D2 D3 X Y V 0 0 0 0 X X 0 0 0 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 Multiplexer A multiplexer is a combinational circuit that selects binary information from one of many input lines and directs it to a single output line The selection of a particular input line is controlled by a set of selection lines normally, there are 2𝑛 input lines and n selection lines whose bit combinations determine which input is selected.  Design 2:1 Multiplexer S Y 0 1 Truth Table 𝑦 = 𝑠′𝐼0 + 𝑠𝐼1 Boolean Expression A 2-to-1 multiplexer consists of two inputs I0 and I1, one select input S and one output Y. Depending on the select signal, the output is connected to either of the inputs. Since there are two input signals, only two ways are possible to connect the inputs to the outputs, so one select is needed to do these operations.  4:1 Multiplexer Above figures represents block diagram ,truth table and implementation using basic gates of 4:1 multiplexer. 4x1 Multiplexer has four data inputs I0, I1, I2 & I3, two selection lines S0 & S1 and one output Y. One of these 4 inputs will be connected to the output based on the combination of inputs present at these two selection lines. 8:1 multiplexer  Multiplexer circuits can be combined with common selection inputs to provide multiple-bit selection logic. As an illustration, a quadruple 2-to-1-line multiplexer is shown in Fig. 4.26. The circuit has four multiplexers, each capable of selecting one of two input lines. Output Y0 can be selected to come from either input A0 or input B0. Similarly, output Y1 may have the value of A1 or B1, and so on. Input selection line S selects one of the lines in each of the four multiplexers. The enable input E must be active (i.e., asserted) for normal operation. As shown in the function table, the unit is enabled when E = 0. Then, if S = 0, the four A inputs have a path to the four outputs. If, by contrast, S = 1, the four B inputs are applied to the outputs. The outputs have all 0’s when E = 1, regardless of the value of S. Design 4:1 MUX using only 2:1 MUX Implement 8:1 Mux using 4:1mux and 2:1mux 8:1 MUX Truth Table Implement using multiplexer F (x, y, z) = (1, 2, 6, 7) n=3 n- 1=2 select lines 𝟐𝒏−𝟏 =4 data inputs Implement using multiplexer F (A, B, C, D) = (1, 3, 4, 11, 12, 13, 14, 15) Three-State Gates A multiplexer can be constructed with three-state gates—digital circuits that exhibit three states. Two of the states are signals equivalent to logic 1 and logic 0 as in a conventional gate. The third state is a high-impedance state in which (1) the logic behaves like an open circuit, which means that the output appears to be disconnected, (2) the circuit has no logic significance, and (3) the circuit connected to the output of the three-state gate is not affected by the inputs to the gate. Three-state gates may perform any conventional logic, such as AND or NAND. However, the one most commonly used is the buffer gate. The graphic symbol for a three-state buffer gate is The buffer has a normal input, an output, and a control input that determines the state of the output. When the control input is equal to 1, the output is enabled and the gate behaves like a conventional buffer, with the output equal to the normal input. When the control input is 0, the output is disabled and the gate goes to a high-impedance state, regardless of the value in the normal input. The high-impedance state of a three-state gate provides a special feature not available in other gates. Because of this feature, a large number of three-state gate outputs can be connected with wires to form a common line without endangering loading effects. The construction of multiplexers with three-state buffers is demonstrated in Fig. 4.30. Figure 4.30(a) shows the construction of a two-to-one-line multiplexer with 2 three-state buffers and an inverter. The two outputs are connected together to form a single output line. (Note that this type of connection cannot be made with gates that do not have three- state outputs.) When the select input is 0, the upper buffer is enabled by its control input and the lower buffer is disabled. Output Y is then equal to input A. When the select input is 1, the lower buffer is enabled and Y is equal to B. Y=AS’+BS HDL models of combinational circuits The logic of a module can be described in any one (or a combination) of the following modeling styles: Behavioral modeling using procedural assignment statements with the keyword always.  Gate-level (structural) modeling describes a circuit by specifying its gates and how they are connected with each other. Gate-level modeling using instantiations of predefined and user-defined primitive gates Dataflow modeling is used mostly for describing the Boolean equations of combinational logic, Dataflow modeling using continuous assignment statements with the keyword assign. Write a Verilog Program For Binary Adder(4bit ) Write a Verilog code for 2:1 mux(multiplexer) Using cond itional operator 𝑦 = 𝑠′𝐼0 + 𝑠𝐼1 Using Data flow Model Behavioral modelling for 2:1 Mux Using Case Statement using If else statement Write Verilog program for 4:1mux using CASE STATEMENT Timing Diagram Write a Verilog code for below figure Sequential Logic ▶ Sequential logic refers to a type of digital logic circuit that uses memory elements to store information. ▶ It consists of a combinational circuit to which storage elements are connected to form a feedback path. The storage elements are devices capable of storing binary information. ▶ a sequential circuit is specified by a time sequence of inputs, outputs, and internal states. Differentiate between combinational logic and sequential logic ▶ The storage elements (memory) used in clocked sequential circuits are called flipflops. ▶ A flip-flop is a binary storage device capable of storing one bit of information. Storage Elements: 1)Latches: ▶ Latches are digital circuits that serve as basic building blocks in the construction of sequential logic circuits. ▶ They are bistable, meaning they have two stable states and can be used to store binary information. Latches are often used for temporary storage of data within a digital system. ▶ There are several types of latches, with the most common being the  1)SR latch (Set-Reset latch), 2)D latch (Data latch),3) JK latch. Storage elements that operate with signal levels (rather than signal transitions) are referred to as latches ; those controlled by a clock transition are flip-flops.Latches are said to be level sensitive devices; flip-flops are edge-sensitive devices.The two types of storage elements are related because latches are the basic circuits from which all flip- flops are constructed. SR Latch (Set-Reset Latch): The SR latch has two inputs, S (Set) and R (Reset).It has two outputs, Q and ~Q (complement of Q). When S is asserted, Q is set to 1, and when R is asserted, Q is reset to 0.The SR latch is sensitive to the input conditions, and having both S and R asserted simultaneously can lead to unpredictable behavior. SR Latch with nor gates where S and R stand for set and reset. It can be constructed from a pair of cross-coupled NOR logic gates. The stored bit is present on the output marked Q. While the S and R inputs are both low, feedback maintains the Q and Q outputs in a constant state, with Q the complement of Q. If S (Set) is pulsed high while R (Reset) is held low, then the Q output is forced high, and stays high when S returns to low; similarly, if R is pulsed high while S is held low, then the Q output is forced low, and stays low when R returns to low. SR latch with control input It consists of the basic SR latch and two additional NAND gates. The control input En acts as an enable signal for the other two inputs. The outputs of the NAND gates stay at the logic-1 level as long as the enable signal remains at 0. This is the quiescent condition for the SR latch. When the enable input goes to 1, information from the S or R input is allowed to affect the latch. The set state is reached with S = 1, R = 0, and En = 1 active-high enabled). To change to the reset state, the inputs must be S = 0, R = 1, and En = 1. In either case, when En returns to 0, the circuit remains in its current state. The control input disables the circuit by applying 0 to En, so that the state of the output does not change regardless of the values of S and R. Moreover, when En = 1 and both the S and R inputs are equal to 0, the state of the circuit does not change. These conditions are listed in the function table accompanying the diagram. D latch(transparent latch) A D latch can store a bit value, either 1 or 0. When its Enable pin is HIGH, the value on the D pin will be stored on the Q output. The D Latch is a logic circuit most frequently used for storing data in digital systems. It is based on the S-R latch, but it doesn’t have an “undefined” or “invalid” state problem. One way to eliminate the undesirable condition of the indeterminate state in the SR latch is to ensure that inputs S and R are never equal to 1 at the same time. This is done in the D latch, shown in Fig. 5.6. This latch has only two inputs: D (data) and En (enable). The D input goes directly to the S input, and its complement is applied to the R input. As long as the enable input is at 0, the cross-coupled SR latch has both inputs at the 1 level and the circuit cannot change state regardless of the value of D. The D input is sampled when En = 1.  If D = 1, the Q output goes to 1, placing the circuit in the set state. If D = 0, output Q goes to 0, placing the circuit in the reset state. The graphic symbols for the various latches are shown in Fig. 5.7. A latch is designated by a rectangular block with inputs on the left and outputs on the right. One output designates the normal output, and the other (with the bubble designation) designates the complement output STORAGE ELEMENTS : FLIP – FLOPS ▶ Flip-flops are fundamental building blocks in digital electronics and sequential logic circuits. ▶ They are bistable multivibrators, like latches, but they are edge- triggered and use a clock signal to control the timing of state changes. ▶ Flip-flops are widely used for storing binary information in electronic systems. Edge triggered DFF The construction of a D flip-flop with two D latches and an inverter is shown in Fig. 5.9. The first latch is called the master and the second the slave. The circuit samples the D input and changes its output Q only at the negative edge of the synchronizing or controlling clock (designated as Clk ). When the clock is 0, the output of the inverter is 1. The slave latch is enabled, and its output Q is equal to the master output Y. The master latch is disabled because Clk = 0. When the input pulse changes to the logic-1 level, the data from the external D input are transferred to the master. The slave, however, is disabled as long as the clock remains at the 1 level, because its enable input is equal to 0. Any change in the input changes the master output at Y, but cannot affect the slave output. When the clock pulse returns to 0, the master is disabled and is isolated from the D input. At the same time, the slave is enabled and the value of Y is transferred to the output of the flip-flop at Q. Thus, a change in the output of the flip-flop can be triggered only by and during the transition of the clock from 1 to 0. Comparison between Latch and Flipflop  construction of an positive edge-triggered D flip-flop uses three SR latches Clk D S R Q Q’ 0 1 Assume(previous output) 0 0 1 1 0 1 No Change 0 1 1 1 No Change 1 1 0 1 1 0 0 0 1 1 No change 1 0 1 0 0 1 JK FLIPFLOP When J = 1 and K = 0, D = Q’ + Q = 1, so the next clock edge sets the output to 1. When J = 0 and K = 1, D = 0, so the next clock edge resets the output to 0. When both J = K = 1 and D = Q, the next clock edge complements the output. When both J = K = 0 and D = Q, the clock edge leaves the output unchanged. T Flipflop T Flipflop using JK Flipflop T = 0 (J = K = 0), a clock edge does not change the output. When T = 1 (J = K = 1), a clock edge complements the output. The complementing flip-flop is useful for designing binary counters. Implementation of TFF using DFF The T flip-flop can be constructed with a D flip-flop and an exclusive-OR gate as shown in Fig. (b). The expression for the D input is D = T ⊕ Q = T’Q + TQ’ When T = 0, D = Q and there is no change in the output. When T = 1, D = Q’ and the output complements. D=T^Q D=T’Q+TQ’  ▶ Characteristic tablesA characteristic table defines the logical properties of a flip-flop by describing its operation in tabular form. They define the next state (i.e., the state that results from a clock transition) as a function of the inputs and the present state ▶ Q(t) denotes the state of the flip-flop immediately before the clock edge, and ▶ Q(t + 1) denotes the state that results from the clock transition. Characteristic equation ▶ It is the Boolean expression in terms of its input and output which determines the next state of the flipflop. T FF DFF JKFF Write Verilog code for Flipflops SR flipflop JK Flipflop D flipflop T Flipflop ------------------------**************************************************--------------  Digital Design and Computer Organization (BCS302) Module 3 MODULE – 3 Basic Structure of Computers, Instructions &Programs Topics: Functional Units Basic Operational Concepts Bus Structures Performance –Processor Clock Basic Performance Equation Clock Rate Performance Measurement. Memory Location and Addresses Memory Operations Instructions and Instruction Sequencing Addressing Modes Introduction Computer Organization explains the function and design of the various units of digital computers that store and process information. It also deals with the input units of the computer which receive information from external sources and the output units which send computed results to external destinations. The input, storage, processing, and output operations are governed by a list of instructions that constitute a program. It deals about computer hardware and computer architecture. Computer hardware consists of electronic circuits, magnetic and optical storage devices, displays, electromechanical devices, and communication facilities. Computer architecture encompasses the specification of an instruction set and the functional behavior of the hardware units that implement the instructions Dr. Ajay V G, Dept. of CSE, SVIT 1  Digital Design and Computer Organization (BCS302) Module 3 Functional Units  A computer consists of five functionally independent main parts: input, memory, arithmetic and logic, output, and control units, as shown in Figure 1.1.  The input unit accepts coded information from human operators using devices such as keyboards, or from other computers over digital communication lines.  The information received is stored in the computer‟s memory, either for later use or to be processed immediately by the arithmetic and logic unit.  The processing steps are specified by a program that is also stored in the memory.  Finally, the results are sent back to the outside world through the output unit.  All of these actions are coordinated by the control unit.  An interconnection network provides the means for the functional units to exchange information and coordinate their actions. Input Units  Computers accept coded information through input units.  The most common input device is the keyboard.  Whenever a key is pressed, the corresponding letter or digit is automatically translated into its corresponding binary code and transmitted to the processor.  Many other kinds of input devices for human-computer interaction are available,including the touchpad, mouse, joystick, and trackball.  These are often used as graphic input devices in conjunction with displays. Dr. Ajay V G, Dept. of CSE, SVIT 2  Digital Design and Computer Organization (BCS302) Module 3  Microphones can be used to capture audio input which is then sampled and converted into digital codes for storage and processing.  Similarly, cameras can be used to capture video input.  Digital communication facilities, such as the Internet, can also provide input to acomputer from other computers and database servers.  The function of the memory unit is to store programs and data.  There are two classes of storage, called primary and secondary. Primary Memory :  Primary memory, also called main memory, is a fast memory that operates at electronic speeds.  Programs must be stored in this memory while they are being executed.  The memory consists of a large number of semiconductor storage cells, each capable of storing one bit of information. These cells are rarely read or written individually.  Instead, they are handled in groups of fixed size called words.  The memory is organized so that one word can be stored or retrieved in one basic operation.  The number of bits in each word is referred to as the word length of the computer, typically 16, 32, or 64 bits.  To provide easy access to any word in the memory, a distinct address is associated with each word location.  Addresses are consecutive numbers, starting from 0, that identify successive locations.  A particular word is accessed by specifying its address and issuing a control command to the memory that starts the storage or retrieval process.  Instructions and data can be written into or read from the memory under the control of the processor.  It is essential to be able to access any word location in the memory as quickly as possible.  A memory in which any location can be accessed in a short and fixed amount of time after specifying its address is called a random-access memory (RAM). The time required to access one word is called the memory access time. This time is independent of the location of the word being accessed.  It typically ranges from a few nanoseconds (ns) to about 100 ns for current RAM units. Dr. Ajay V G, Dept. of CSE, SVIT 3 Digital Design and Computer Organization (BCS302) Module 3 Cache Memory  As an adjunct to the main memory, a smaller, faster RAM unit, called a cache, is used to hold sections of a program that are currently being executed, along with any associated data.  The cache is tightly coupled with the processor and is usually contained on the same integrated-circuit chip.  The purpose of the cache is to facilitate high instruction execution rates.  At the start of program execution, the cache is empty.  All program instructions and any required data are stored in the main memory.  As execution proceeds, instructions are fetched into the processor chip, and a copy of each is placed in the cache.  When the execution of an instruction requires data located in the main memory, thedata are fetched and copies are also placed in the cache. Secondary Storage  Primary memory is essential, it tends to be expensive and does not retain information when power is turned off.  Thus additional, less expensive, permanent secondary storage is used when large amounts of data and many programs have to be stored, particularly for information that is accessed infrequently.  Access times for secondary storage are longer than for primary memory.  A wide selection of secondary storage devices is available, including magnetic disks, optical disks (DVD and CD), and flash memory devices. Arithmetic and Logic Unit o Most computer operations are executed in the arithmetic and logic unit (ALU) of the processor. o Any arithmetic or logic operation, such as addition, subtraction, multiplication, division, or comparison of numbers, is initiated by bringing the required operandsinto the processor, where the operation is performed by the ALU. o For example, if two numbers located in the memory are to be added, they are brought into the processor, and the addition is carried out by the ALU. o The sum may then be stored in the memory or retained in the processor for immediate use. o When operands are brought into the processor, they are stored in high-speed storage elements called registers. o Each register can store one word of data. o Access times to registers are even shorter than access times to the cache unit on the processor chip. Dr. Ajay V G, Dept. of CSE, SVIT 4 Digital Design and Computer Organization (BCS302) Module 3 Output Unit o The output unit is the counterpart of the input unit. o Its function is to send processed results to the outside world. o A familiar example of such a device is a printer. o Most printers employ either photocopying techniques, as in laser printers, or ink jetstreams. o Such printers may generate output at speeds of 20 or more pages per minute. o However, printers are mechanical devices, and as such are quite slow compared tothe electronic speed of a processor. o Some units, such as graphic displays, provide both an output function, showing text o and graphics, and an input function, through touchscreen capability. Control Unit  The memory, arithmetic and logic, and I/O units store and process information and perform input and output operations.  The operation of these units must be coordinated in some way.  This is the responsibility of the control unit.  The control unit is effectively the nerve center that sends control signals to other units and senses their states.  I/O transfers, consisting of input and output operations, are controlled by program instructions that identify the devices involved and the information to be transferred.  Control circuits are responsible for generating the timing signals that govern the transfers and determine when a given action is to take place.  Data transfers between the processor and the memory are also managed by the control unit through timing signals.  A large set of control lines (wires) carries the signals used for timing and synchronization of events in all units. Dr. Ajay V G, Dept. of CSE, SVIT 5 Digital Design and Computer Organization (BCS302) Module 3  The operation of a computer can be summarized as follows:  The computer accepts information in the form of programs and data through an input unit and stores it in the memory.  Information stored in the memory is fetched under program control into anarithmetic and logic unit, where it is processed  Processed information leaves the computer through an output unit  All activities in the computer are directed by the control unit Dr. Ajay V G, Dept. of CSE, SVIT 6  COMPUTER ORGANIZATION (21CS34) Module 3 1. BASIC OPERATIONAL CONCEPTS: The program to be executed is stored in memory. Instructions are accessed from memory to the processor one by one and executed. STEPS FOR INSTRUCTION EXECUTION Consider the following instruction Ex: 1 Add LOCA, R0 This instruction is in the form of the following instruction format Opcode Source, Destination Where Add is the operation code, LOCA is the Memory operand and R0 is Register operand This instruction adds the contents of memory location LOCA with the contents of Register R0 and the result is stored in R0 Register. The symbolic representation of this instruction is R0 [LOCA] + [R0] The contents of memory location LOCA and Register R0 before and after the execution of this instruction is as follows Before instruction execution After instruction execution LOCA = 23H LOCA = 23H R0 = 22H R0 = 45H The steps for instruction execution are as follows 1. Fetch the instruction from memory into the IR (instruction register in CPU). 2. Decode the instruction 1111000000 10011010 3. Access the Memory Operand 4. Access the Register Operand 5. Perform the operation according to the Operation Code. 6. Store the result into the Destination Memory location or Destination Register. Ex:2 Add R1, R2, R3 This instruction is in the form of the following instruction format Opcode, Source-1, Source-2, Destination Where R1 is Source Operand-1, R2 is the Source Operand-2 and R3 is the Destination. This instruction adds the contents of Register R1 with the contents of R2 and the result is placed in R3 Register. The symbolic representation of this instruction is R3 [R1] + [R2] The contents of Registers R1,R2,R3 before and after the execution of this instruction is as follows. Before instruction execution After instruction execution R1 = 24H R1 = 24H R2 = 34H R2 = 34H R3 = 38H R3 = 58H Dr. Ajay V G, Dept. of CSE, SVIT 7 COMPUTER ORGANIZATION (21CS34) Module 3 The steps for instruction execution is as follows 1. Fetch the instruction from memory into the IR. 2. Decode the instruction 3. Access the First Register Operand R1 4. Access the Second Register Operand R2 5. Perform the operation according to the Operation Code. 6. Store the result into the Destination Register R3. CONNECTION BETWEEN MEMORY AND PROCESSOR The connection between Memory and Processor is as shown in the figure. The Processor consists of different types of registers. 1. MAR (Memory Address Register) 2. MDR (Memory Data Register) 3. Control Unit 4. PC (Program Counter) 5. General Purpose Registers 6. IR (Instruction Register) 7. ALU (Arithmetic and Logic Unit) Dr. Ajay V G, Dept. of CSE, SVIT 8 COMPUTER ORGANIZATION (21CS34) Module 3 The functions of these registers are as follows 1. MAR  It establishes communication between Memory and Processor  It stores the address of the Memory Location as shown in the figure. MAR Memory 5000h 5000 23h 5001 43h 5002 78h 5003 65h 2. MDR  It also establishes communication between Memory and the Processor.  It stores the contents of the memory location (data or operand), written into or read from memory as shown in the figure. MDR Memory 23h 23h 5000 43h 5001 78h 5002 65h 5003 3. CONTROL UNIT  It controls the data transfer operations between memory and the processor.  It controls the data transfer operations between I/O and processor.  It generates control signals for Memory and I/O devices. Dr. Ajay V G, Dept. of CSE, SVIT 9 COMPUTER ORGANIZATION (21CS34) Module 3 4. PC (PROGRAM COUNTER)  It is a special purpose register used to hold the address of the next instruction to be executed.  The contents of PC are incremented by 1 or 2 or 4, during the execution of current instruction.  The contents of PC are incremented by 1 for 8 bit CPU, 2 for 16 bit CPU and for 4 for 32 bit CPU. 4. GENERAL PURPOSE REGISTER / REGISTER ARRAY The structure of register file is as shown in the figure R0 R1 R2. Rn-1  It consists of set of registers.  A register is defined as group of flip flops. Each flip flop is designed to store 1 bit of data.  It is a storage element.  It is used to store the data temporarily during the execution of the program(eg: result).  It can be used as a pointer to Memory.  The Register size depends on the processing speed of the CPU  EX: Register size = 8 bits for 8 bit CPU 5. IR (INSTRUCTION REGISTER It holds the instruction to be executed. It notifies the control unit, which generates timing signals that controls various operations in the execution of that instruction. 6. ALU (ARITHMETIC and LOGIC UNIT)  It performs arithmetic and logical operations on given data. Steps for reading the instruction. PC contents are transferred to MAR and read signal is sent to memory by control unit. The data from memory location is read and sent to MDR. The content of MDR is moved to IR. [PC]  MAR Memory  MDR  IR CU ( read signal) Dr. Ajay V G, Dept. of CSE, SVIT 10 COMPUTER ORGANIZATION (21CS34) Module 3 2. BUS STRUCTURE Bus is defined as set of parallel wires used for data communication between different parts of computer. Each wire carries 1 bit of data. There are 3 types of buses, namely 1. Address bus 2. Data bus and 3. Control bus1. 1. Address bus :  It is unidirectional.  The processor (CPU) sends the address of an I/O device or Memory device by means of this bus. 2. Data bus  It is a bidirectional bus.  The CPU sends data from Memory to CPU and vice versa as well as from I/O to CPU and vice versa by means of this bus. 3. Control bus:  This bus carries control signals for Memory and I/O devices. It generates control signals for Memory namely MEMRD and MEMWR and control signals for I/O devices namely IORD and IOWR. The structure of single bus organization is as shown in the figure.  The I/O devices, Memory and CPU are connected to this bus is as shown in the figure.  It establishes communication between two devices, at a time. Features of Single bus organization are  Less Expensive  Flexible to connect I/O devices.  Poor performance due to single bus. There is a variation in the devices connected to this bus in terms of speed of operation. Few devices like keyboard, are very slow. Devices like optical disk are faster. Memory and processor are faster, but all these devices uses the same bus. Hence to provide the synchronization between two devices, a buffer register is attached to each device. It holds the data temporarily during the data transfer between two devices. Dr. Ajay V G, Dept. of CSE, SVIT 11 COMPUTER ORGANIZATION (21CS34) Module 3 3. PERFORMANCE  The performance of a Computer System is based on hardware design of the processor and the instruction set of the processors.  To obtain high performance of computer system it is necessary to reduce the execution time of the processor.  Execution time: It is defined as total time required executing one complete program.  The processing time of a program includes time taken to read inputs, display outputs, system services, execution time etc.  The performance of the processor is inversely proportional to execution time of the processor. More performance = Less Execution time. Less Performance = More Execution time. The Performance of the Computer System is based on the following factors 1. Cache Memory 2. Processor clock 3. Basic Performance Equation 4. Instructions 5. Compiler CACHE MEMORY: It is defined as a fast access memory located in between CPU and Memory. It is part of the processor as shown in the fig The processor needs more time to read the data and instructions from main memory because main memory is away from the processor as shown in the figure. Hence it slowdown the performance of the system. The processor needs less time to read the data and instructions from Cache Memory because it is part of the processor. Hence it improves the performance of the system. PROCESSOR CLOCK: The processor circuits are controlled by timing signals called as Clock. It defines constant time intervals and are called as Clock Cycles. To execute one instruction there are 3 basic steps namely 1. Fetch Dr. Ajay V G, Dept. of CSE, SVIT 12 COMPUTER ORGANIZATION (21CS34) Module 3 2. Decode 3. Execute. The processor uses one clock cycle to perform one operation as shown in the figure Clock Cycle → T1 T2 T3 Instruction → Fetch Decode Execute The performance of the processor depends on the length of the clock cycle. To obtain high performance reduce the length of the clock cycle. Let „ P ‟ be the number of clock cycles generated by the Processor and „ R „ be the Clock rate. The Clock rate is inversely proportional to the number of clock cycles. i.e R = 1/P. Cycles/second is measured in Hertz (Hz). Eg: 500MHz, 1.25GHz. Two ways to increase the clock rate –  Improve the IC technology by making the logical circuit work faster, so that the time taken for the basic steps reduces.  Reduce the clock period, P. BASIC PERFORMANCE EQUATION Let „T „be total time required to execute the program. Let „N „be the number of instructions contained in the program. Let „S „be the average number of steps required to one instruction. Let „R‟ be number of clock cycles per second generated by the processor to execute one program. Processor Execution Time is given by T=N*S/R This equation is called as Basic Performance Equation. For the programmer the value of T is important. To obtain high performance it is necessary to reduce the values of N & S and increase the value of R Performance of a computer can also be measured by using benchmark programs. SPEC (System Performance Evaluation Corporation) is an non-profitable organization, that measures performance of computer using SPEC rating. The organization publishes the application programs and also time taken to execute these programs in standard systems. 𝑅𝑢𝑛𝑛𝑖𝑛𝑔 𝑡𝑖𝑚𝑒 𝑜𝑓 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑐𝑒 𝐶𝑜𝑚𝑝𝑢𝑡𝑒𝑟 𝑆𝑃𝐸𝐶 = 𝑅𝑢𝑛𝑛𝑖𝑛𝑔 𝑡𝑖𝑚𝑒 𝑜𝑓 𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝑟 𝑢𝑛𝑑𝑒𝑟 𝑡𝑒𝑠𝑡 Dr. Ajay V G, Dept. of CSE, SVIT 13 COMPUTER ORGANIZATION (21CS34) Module 3 DIFFERENCES MULTIPROCESSOR AND MULTICOMPUTER MULTIPROCESSOR MULTICOMPUTER 1. It is a process of interconnection of two or It is a process of interconnection of two or more processors by means of system bus. more computers by means of system bus. 2. It uses common memory to hold the data It has its own memory to store data and and instructions. instructions. 3. Complexity in hardware design. Not much complexity in hardware design. 4. Difficult to program for multiprocessor Easy to program for multiprocessor system system. 4. MEMORY LOCATIONS AND ADDRESSES 1. Memory is a storage device. It is used to store character operands, data operands and instructions. 2. It consists of number of semiconductor cells and each cell holds 1 bit of information. A group of 8 bits is called as byte and a group of 16 or 32 or 64 bits is called as word. World length = 16 for 16 bit CPU and World length = 32 for 32 bit CPU. Word length is defined as number of bits in a word.  Memory is organized in terms of bytes or words.  The organization of memory for 32 bit processor is as shown in the fig. The contents of memory location can be accessed for read and write operation. The memory is accessed either by specifying address of the memory location or by name of the memory location. Dr. Ajay V G, Dept. of CSE, SVIT 14 COMPUTER ORGANIZATION (21CS34) Module 3  Address space : It is defined as number of bytes accessible to CPU and it depends on the number of address lines. 5. BYTE ADDRESSABILITY Each byte of the memory are addressed, this addressing used in most computers are called byte addressability. Hence Byte Addressability is the process of assignment of address to successive bytes of the memory. The successive bytes have the addresses 1, 2, 3, 4………….2 n-1. The memory is accessed in words. In a 32 bit machine, each word is 32 bit and the successive addresses are 0,4,8,12,… and so on. Address 32 – bit word 0000 0th byte 1st byte 2nd byte 3rd byte 0004 4th byte 5th byte 6th byte 7th byte 0008 8th byte 9th byte 10th byte 11th byte 0012 12th byte 13th byte 14th byte 15th byte ….. ….. ….. ….. ….. n-3 n-3th byte n-2th byte n-1th byte nth byte BIG ENDIAN and LITTLE ENDIAN ASSIGNMENT Two ways in which byte addresses can be assigned in a word. Or Two ways in which a word is stored in memory. 1. Big endian 2. Little endian BIG ENDIAN ASSIGNMENT In this technique lower byte of data is assigned to higher address of the memory and higher byte of data is assigned to lower address of the memory. Dr. Ajay V G, Dept. of CSE, SVIT 15 COMPUTER ORGANIZATION (21CS34) Module 3 The structure of memory to represent 32 bit number for big endian assignment is as shown in the above figure. LITTLE ENDIAN ASSIGNMENT In this technique lower byte of data is assigned to lower address of the memory and higher byte of data is assigned to higher address of the memory. The structure of memory to represent 32 bit number for little endian assignment is as shown in the fig. Eg – store a word “JOHNSENA” in memory starting from word 1000, using Big Endian and Little endian. Bigendian - 1000 J O H N 1000 1001 1002 1003 1004 S E N A 1004 1005 1006 1007 Little endian - 1000 J