Computer Architecture: Digital Logic Circuits PDF

Computer Architecture Eng. Mohammad N. Olaimat Unit-03: Computer Digital-Logic Circuits Objective The function of the computer is based on the storage and processing of binary digits. What is needed to achieve this function is storag...

Computer Architecture Eng. Mohammad N. Olaimat Unit-03: Computer Digital-Logic Circuits Objective The function of the computer is based on the storage and processing of binary digits. What is needed to achieve this function is storage nodes and electronic circuits that operate on the data regulated by control signals. The objective of this unit is presenting the techniques by which the storage nodes and the circuits are implemented in digital logic circuits. 1. Boolean Algebra Boolean algebra consists of logical variables and operations. A variable value is either 1 (TRUE) or 0 (FALSE). The basic logical operations are AND, OR, and NOT. Boolean algebra is tool employed in two areas: Digital Circuit Analysis: Describing the function of a digital circuit. Digital Circuit Design: Developing an implementation of a function by a digital circuit. Figure-1 : Boolean Operations of Two Logical Variables Figure-2 : Boolean Operations of Multiple Logical Variables Figure-3 : Boolean Operations of a Set of Logical Variables Figure-4 : Properties of Boolean Algebra Figure-1 : Boolean Operations of Two Logical Variables Figure-2 : Boolean Operations of Multiple Logical Variables 1  Figure-3 : Boolean Operations of a Set of Logical Variables Figure-4 : Properties of Boolean Algebra Boolean Functions & Their Properties The Boolean functions represent computer digital operations. The properties of the Boolean functions may simplify the design of electronic circuits through reducing the complexity of the Boolean functions themselves. Examples follow: Example-1 F = A + ̅̅̅̅ ̅+𝐀 𝐁𝐀 = A + 𝐁 ̅ F=A+𝐀 ̅+𝐁 ̅=1+ 𝐁 ̅=1 Example-2 F=𝐀 ̅.𝐁 ̅. C + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝐀. 𝐁 + 𝐀. 𝐂) F=𝐀 ̅.𝐁 ̅. C + ̅̅̅̅̅̅̅̅̅ (𝐀. 𝐁). ̅̅̅̅̅̅̅̅ (𝐀. 𝐂) ̅ ̅ ̅ ̅ F = 𝐀. 𝐁. C + (𝐀 + 𝐁). (𝐀 ̅ + 𝐂̅) F=𝐀 ̅.𝐁 ̅. C + ((𝐀 ̅+𝐁 ̅). 𝐀 ̅ ) + ((𝐀 ̅+𝐁 ̅ ). 𝐂̅)) F=𝐀 ̅.𝐁 ̅. C + (𝐀 ̅.𝐀 ̅+𝐁 ̅.𝐀 ̅ ) + (𝐀 ̅. 𝐂̅ + 𝐁̅. 𝐂̅) F=𝐀 ̅.𝐁 ̅.C+𝐀 ̅ +̅ 𝐁.𝐀 ̅ + 𝐀 ̅. 𝐂̅ + 𝐁 ̅. 𝐂̅ ̅ ̅ ̅ ̅ ̅ F = 𝐀. (𝐁. C + 1 + 𝐁 + 𝐂) + 𝐁. 𝐂 = 𝐀 ̅ ̅.1 + 𝐁 ̅. 𝐂̅ = 𝐀 ̅. 𝐂̅ ̅ + 𝐁 2 2. Logic Gates The computer's digital-logic circuits are built by a network of logical gates. The computer's operations are designed by constructing Boolean functions to be implemented by interconnecting the basic logical gates to produce an output signal. The basic gates used in digital logic are illustrated in Figure-5 by graphical symbols, algebraic notations, and truth tables: Figure-5 : Computer Logic Gates Notes:  All of the gates except NOT can have more than two inputs (Figure-2).  A gate may be implemented with two outputs, one output is the NOT of the other output.  To simplify logical circuit engineering, not all gate types are used in circuit implementation; thus, functionally- complete sets of logical gates are defined: {AND, OR, NOT}, {AND, NOT}, {OR, NOT}, {NAND}, {NOR}.  A functionally-complete set consists of one or more logical gates that can implement any logical function. Examine Figure-6 and Figure-7 to validate the functionally-complete sets of the logical gates: {NAND}, {NOR}.  For instance, the {AND, NOT} is a functionally-complete set because it can construct the OR gate: A + B = NOT ((NOT A). (NOT B)) 3  Figure-6 : NAND Gate Figure-7 : NOR Gate 3. Combinational Circuits Combinational Circuit: It is a logical circuit whose output at any time is a function only of the current input at that time. Combinational circuits do not provide memory or state information. Combinational Circuits Representation Combinational circuits are defined in three ways:  Truth-Table: For each of the 2n combinations of input signals, the binary value of each of the m output signals is written. Lookup Table-1.  Boolean Equations: Each output signal is expressed as a Boolean function of its input signals. Lookup Equation.1 & 2.  Graphical Symbols: The interconnected layout of gates is depicted. Lookup Figure-8 and Figure-9. A. Truth-Table Representation Example: Table-1 : Boolean Function by Truth-Table 4 B. Boolean Equation Representation Boolean Equations: A sum of products (SoP) equation of the Boolean function of Table-1 is as follows. ……………………………. [Equation.1]. Boolean Equations: A product of sums (PoS) equation of the Boolean function of Table-1 is as follows. ……………………………. [Equation.2]. C. Graphical Symbols Representation: Figure-8 and Figure-9. Figure-8 : SoP logical circuit of the function in Table-1 Figure-9 : PoS logical circuit of the function in Table-1 Implementation of Boolean Functions A Boolean equation must be simplified so that fewer gates will be required to implement the function. Three methods that can be used to achieve simplification are: A. Algebraic Simplification Algebraic simplification involves the application of the identities of Figure-4 (Properties of Boolean Algebra) to reduce the Boolean expression to a simpler form so that fewer logic gates would be employed to implement it. For example, consider Example-2 whose Boolean expression is: F = 𝐀 ̅.𝐁̅. C + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝐀. 𝐁 + 𝐀. 𝐂) …………………… Equation-3. This Boolean expression could be reduced into the equation: 𝐀 + 𝐁̅ ̅. 𝐂̅ ……………………. Equation-4. This expression can be implemented as shown in Figure-10. 5  Figure-10 : Logical Circuit Implementation of Equation-4 B. Karnaugh Mapping (K-Map) The Karnaugh Map (KM) is a tool to simplify a Boolean function consisting of 4 input variables or less. The KM is an array of 2^n squares, representing all possible combinations of n input binary variables. In the case of 3 input variables, the representation is a matrix of 8 squares: With one of the variables to be placed on the left and for the other two variables placed above the squares; for 4 variables, 16 squares are needed. The Karnaugh Map (KM) can reduce any Boolean function by applying the following scheme: 1. For each combination of values of input variables that produce an output of 1 in the Boolean truth table, fill in the corresponding square of the KM with 1; 2. Each square would correspond to a unique product of the input variables such that a 1 corresponds to the variable value and a 0 to the negation of that variable value; 3. Adjacency rule enables wrapping around the edge of the map. The top square of a column is adjacent to the bottom square, and the leftmost square of a row is adjacent to the rightmost square. 4. The grouping rule of adjacency applies to any of 2^n adjacent squares (2, 4, 8, etc.), depending on the count of the input variables; 5. Every marked square should be included in the selection process at least once. It is allowed to include the same square more than once to form larger blocks with other variables; 6. Among the marked squares with a 1, find those squares that construct a unique largest block of 1, 2, 4 input variables and circle those blocks; 7. Continue selecting additional squares or blocks of marked squares that are as large as possible and as few in number as possible provided that all squares were included; 8. If two adjacent squares both have an entry of 1, then the corresponding algebraic product terms differ in only one variable; the two terms can be merged by eliminating that input variable from the calculated algebraic term. This rule applies to any adjacent 2^n squares: 4 squares (2 variables to be eliminated), 8 squares (3 variables); 9. Eliminate any block of 1 squares that is completely overlapped by other blocks from inclusion in the final Boolean function; 10. Each algebraic term produced by the KM is a product of the input variables. Combine those term products to produce a sum-of-products (SoP) equation. 6  Figure-11 : Karnaugh Maps of Boolean Functions (Part (b) of Table-1) (a) (b) (c) Figure-12: Karnaugh Maps of Boolean Functions (a) (b) (c) Figure-13: Karnaugh Maps of Boolean Functions 7  (a) (b) (c) Figure-14: Karnaugh Maps of Boolean Functions Boolean equations of the Karnaugh Maps: ̅ BD Figure-12 (a) == 𝐀 ̅𝐁 Figure-13 (a) == 𝐀 ̅ ̅ Figure-14 (a) == 𝐀 ̅ 𝐂̅D Figure-12 (b) == 𝐁 Figure-13 (b) == 𝐁𝐂̅ ̅ Figure-14 (b) == 𝐃 ̅ B𝐃 Figure-12 (c) == 𝐀 ̅ ̅ Figure-13 (c) == B𝐃 Figure-14 (c) == C Table-2 : Boolean Functions of Karnaugh Maps (Figures: 12, 13, 14) Combinational Circuit Components Multiplexers Multiplexers are used in digital circuits to enable routing or blocking control signals and data. The multiplexer connects multiple digital inputs to a single digital output. At any time, a single input signal is selected to be passed to the output port of the Multiplexer. Figure-15 represents a block diagram of 4-to-1 multiplexer. A 4-to-1 multiplexer indicates that there are 4 input lines, labeled D0, D1, D2, and D3 and one of the four input lines is selected to provide the output signal F. To select one of the four possible inputs, a 2-bit selection signal is required, and that is implemented as two select signal lines labeled as S1 and S2. Table-2 represents the truth-table of the multiplexer depicted in Figure-15. Figure-16 presents an implementation of the 4-1 MUX using AND, OR, and NOT gates by which three of the AND gates will output 0 whereas the fourth AND gate will output the value of the selected input line. Thus, three of the inputs to the OR gate are always 0, and the output of the OR gate will equal the value of the selected input gate. The construction of multiplexers of 8-to-1, 16-to-1, 32-to-1, and 64-to-1 configurations follows the same design logic. A practical use-case of a MUX is determining the value stored in the program counter (PC) as presented in Figure-17. Various inputs feed the input ports of a multiplexer, with the PC connected to the output line. The select-signals determine the ultimate value that is loaded into the PC. As the PC stores multiple bits, multiple multiplexers are required, one multiplexer per bit. What is the address size of this multiplexer? 8 Figure-15: 4-to-1 Multiplexer Representation Table-2: Truth-Table of the Multiplexer in Figure-15 Figure-16: A 4-1 Multiplexer Implementation Figure-17: Multiplexer Use-Case with Program Counter 9 Decoders A decoder is a combinational circuit that has n input ports and 2^n output lines only one of which is asserted at a time depending on the digital pattern of the input ports. Figure-18 shows a 3-to-8 decoder and Figure-19 shows a 2-to-4 decoder. Decoders find multiple use-cases in digital computers one of which is address-decoding. Decoder Use-case: Suppose we wish to construct a 1K-byte memory using four 256 * 8-bit RAM chips. The chips' address- space is subdivided as presented in Table-3. Each chip requires 8 address lines that are supplied by the lower-order 8 bits of the address. The higher-order 2 bits of the 10-bit address are used to select one of the four RAM chips. To achieve this objective, two decoders are used: The first is a 2-to-4 decoder for selecting one of the four chips and the second decoder is a 3-to-8 decoder to determine the local address in a chip, as demonstrated in Figure-18 and Figure-19. Address Chip No. 0000–00FF 0 0100–01FF 1 0200–02FF 2 0300–03FF 3 Table-3: Chip Memory Address-Range Figure-18: A 3-to-8 Decoder: 8-bit Address-Decoding 10  Figure-19: A 2-to-4 Decoder & a 3-to-8 Decoder: 1Kb Memory-Address Decoding Adders Binary addition differs from Boolean algebra standard functions in that the result includes a carry term. Table-4 demonstrates the logic for adding 2 input bits to produce a 1-bit sum and a carry bit. We may extend performing addition on n-bit numbers by providing the carry input and output lines for each addition stage. Table-5 illustrates this technique and the Boolean functions of the sum and the carry functions are embodied in the following equations: Sum = A̅B ̅C + A̅BC̅ + ABC + ABC ̅̅̅̅ Carry = AB + AC + BC Figure-20 depicts the organization of the 4-bit Adder representing the Boolean equations by assembling a set of adders so that the carry from one adder is provided as input to the next. The 4-bit Adder's Boolean gates implementation is shown in Figure-21. Table-4: Truth-Tabe of 2-bit addition Table-5: Truth-Tabe of extended 2-bit addition 11  Figure-20: 4-bit Adder Figure-21: 4-bit Adder Logic Design 12