devices the techniques were tailored to gate networks of the type described above. The term gate was alread in use in the forties to denote the logical elements discussed earlier. There are very many good references on Boolean algebra and we may quote only a selected few of them. Suffice it to mention the texts by Hill and Peterson [1974], Kohavi [ 1978], and Hohn [1966]. These books give sufficiently rigorous formulation of the subject, tailored to the analysis and the design of combinational the Boolean techniques used in connection with relay circuits. (Some of the s also contain a discussion of omit this topic, which has been but totally overshadowed by the impressive development of electronic networks. The reader interested in studying the relation of switching algebra to Boolean algebras in general is referred to Preparata and Yeh 1973] for an eler Defining Terms Boolean algebra: The algebra of logical values enabling the logical designer to obtain expressions for digital Boolean expressions: Expressions of logical variables constructed using the connectives and, or, and not Boolean functions: Common designations of binary functions of binary variables. Combinational logic: Interconnections of memory-free digital elements. Switching theory: The theory of digital circuits viewed as interconnections of elements whose output can switch between the logical values of 0 and 1 Related Topic 79.2 Logic Gates(IC) References G Boole, An Investigation of the Laws of Thought, New York: Dover Publication, 1954 E J. Hill and G.R. Peterson, Introduction to Switching Theory and Logical Design, New York: Wiley, 1974. F.E. Hohn, Applied Boolean Algebra, New York: Macmillan, 1966 Z. Kohavi, Switching and Finite Automata Theory, New York: McGraw-Hill, 1978. E.P. Preparata and R.T. Yeh, Introduction to Discrete Structures, Reading, Mass. Addison C.E. Shannon,A symbolic analysis of relay and switching circuits, Trans. AIEE, vol. 57, 3-723,1938. 81.2 Logic circuits Richard S. Sandie Section 81.2 deals with two-state(high or low, I or 0, or true or false) logic circuits. Two-state logic circuits can be broken down into two major types of circuits: combinational logic circuits and sequential logic circuits. By definition, the external output signals of combinational logic circuits are totally dependent on the external input signals applied to the circuit. In contrast, the output signals of sequential logic circuits are dependent on all or part of the present state output signals of the circuit that are fed back as input signals to the circuit as well as any external input signals if they should exist. Sequential logic circuits can be subdivided into synchro nous or clock-mode circuits and asynchronous circuits. Asynchronous circuits can be further divided into fundamental-mode circuits and pulse-mode circuits. Fig 81.15 is the graphic classification of logic circuits Combinational logic circuits The block diagram in Fig. 81.16 illustrates the model for combinational logic circuits. The logic elements inside ock entitled combinational logic circuit can be any configuration of two-state logic elements such that the signals are totally dependent on the input signals to the circuit as indicated by the functional relationships in the figure e 2000 by CRC Press LLC
© 2000 by CRC Press LLC devices the techniques were tailored to gate networks of the type described above. The term gate was already in use in the forties to denote the logical elements discussed earlier. There are very many good references on Boolean algebra and we may quote only a selected few of them. Suffice it to mention the texts by Hill and Peterson [1974], Kohavi [1978], and Hohn [1966]. These books give a sufficiently rigorous formulation of the subject, tailored to the analysis and the design of combinational networks. In addition, like most of the earlier books, Hohn’s and Kohavi’s texts also contain a discussion of the Boolean techniques used in connection with relay circuits. (Some of the more recent works completely omit this topic, which has been but totally overshadowed by the impressive development of electronic networks.) The reader interested in studying the relation of switching algebra to Boolean algebras in general is referred to Preparata and Yeh [1973] for an elementary introduction. Defining Terms Boolean algebra: The algebra of logical values enabling the logical designer to obtain expressions for digital circuits. Boolean expressions: Expressions of logical variables constructed using the connectives and, or, and not. Boolean functions: Common designations of binary functions of binary variables. Combinational logic: Interconnections of memory-free digital elements. Switching theory: The theory of digital circuits viewed as interconnections of elements whose output can switch between the logical values of 0 and 1. Related Topic 79.2 Logic Gates (IC) References G. Boole, An Investigation of the Laws of Thought, New York: Dover Publication, 1954. F.J. Hill and G.R. Peterson, Introduction to Switching Theory and Logical Design, New York: Wiley, 1974. F.E. Hohn, Applied Boolean Algebra, New York: Macmillan, 1966. Z. Kohavi, Switching and Finite Automata Theory, New York: McGraw-Hill, 1978. F.P. Preparata and R.T. Yeh, Introduction to Discrete Structures, Reading, Mass.: Addison-Wesley, 1973. C.E. Shannon, “A symbolic analysis of relay and switching circuits,” Trans. AIEE, vol. 57, pp. 713–723, 1938. 81.2 Logic Circuits Richard S. Sandige Section 81.2 deals with two-state (high or low, 1 or 0, or true or false) logic circuits. Two-state logic circuits can be broken down into two major types of circuits: combinational logic circuits and sequential logic circuits. By definition, the external output signals of combinational logic circuits are totally dependent on the external input signals applied to the circuit. In contrast, the output signals of sequential logic circuits are dependent on all or part of the present state output signals of the circuit that are fed back as input signals to the circuit as well as any external input signals if they should exist. Sequential logic circuits can be subdivided into synchronous or clock-mode circuits and asynchronous circuits. Asynchronous circuits can be further divided into fundamental-mode circuits and pulse-mode circuits. Fig. 81.15 is the graphic classification of logic circuits. Combinational Logic Circuits The block diagram in Fig. 81.16 illustrates the model for combinational logic circuits. The logic elements inside the block entitled combinational logic circuit can be any configuration of two-state logic elements such that the output signals are totally dependent on the input signals to the circuit as indicated by the functional relationships in the figure
Logic circuits or clock mode Fundamental Pulse mode FIGURE 81.15 Graphic classification of logic circuits (Ideal components. hat is, no delays F2=#F31号::12=F2:2 Fm = Fm(1, 12,..., In) fm=Fm after Atm FIGURE 81.16 Block diagram model for combinational logic circuits. The logic elements can be anything from relays with their slow on and off switching action to modern off- the-shelf integrated circuit(IC) transistor switches with their extremely fast switching action. Modern ICs exist in various technologies and circuit configurations such as transistor-transistor logic(TTL), complementary metal-oxide semiconductor(CMOS), emitter-coupled logic (ECL), and integrated injection logic(FL), just to lame a The delays in the outputs of the model in Fig. 81.16 represent lumped delays, that is, worst-case dela through the longest delay path from the inputs to each respective output of the combinational logic circuit. e 2000 by CRC Press LLC
© 2000 by CRC Press LLC The logic elements can be anything from relays with their slow on and off switching action to modern offthe-shelf integrated circuit (IC) transistor switches with their extremely fast switching action. Modern ICs exist in various technologies and circuit configurations such as transistor-transistor logic (TTL), complementary metal-oxide semiconductor (CMOS), emitter-coupled logic (ECL), and integrated injection logic (I2 L), just to name a few. The delays in the outputs of the model in Fig. 81.16 represent lumped delays, that is, worst-case delays through the longest delay path from the inputs to each respective output of the combinational logic circuit. FIGURE 81.15 Graphic classification of logic circuits. FIGURE 81.16 Block diagram model for combinational logic circuits
小m FIGURE 81.17 Gate-level logic circuit for binary to seven-segment hexadecimal character generator. The lumped delays provide an approximate measure of circuit speed or settling time(the time it takes an output ignal to become stable after the input signals have become stable) Figure 81.17 illustrates the gate-level method(random logic method) of implementing a binary to seven- segment hexadecimal character generator suitable for driving a seven-segment common cathode led display like the one in Fig. 81.18. The propagation delays of logic circuits are seldom shown on logic circuit diagrams; however, these delays are inherent in each logic element and must be considered in systems designs. This gate-level combinational logic circuit converts the binary input code 0000 though 11l1 represented on the signal inputs D(MSB)C B A(LSB)to the binary code on the signal outputs OA through OG. These outputs generate the hexadecimal haracters 0 through F when applied to a seven-segment common cathode LEd display. Each of the signal lines D, D, through A, A must be capable of driving the number of gate inputs shown in the brackets(fan-out requirement) to both the high-level and low-level required voltages. The output equations for the circuit in Fig 81.17 are the minimum sum of products(SOP)equations for the 1s of the functions OA though OG, respectively, represented by the truth table in Table 81.4 A more efficient way(in terms of package count)to implement the same combinational logic function would be to use a medium-scale integration(MSI)4-to 16-line decoder with gates as illustrated in Fig. 81.19. The tildes are used as in-line symbols for the logical complements of Do through D15 as recommended by ieee. e 2000 by CRC Press LLC
© 2000 by CRC Press LLC The lumped delays provide an approximate measure of circuit speed or settling time (the time it takes an output signal to become stable after the input signals have become stable). Figure 81.17 illustrates the gate-level method (random logic method) of implementing a binary to sevensegment hexadecimal character generator suitable for driving a seven-segment common cathode LED display like the one in Fig. 81.18. The propagation delays of logic circuits are seldom shown on logic circuit diagrams; however, these delays are inherent in each logic element and must be considered in systems designs. This gate-level combinational logic circuit converts the binary input code 0000 though 1111 represented on the signal inputs D(MSB) C B A(LSB) to the binary code on the signal outputs OA through OG. These outputs generate the hexadecimal characters 0 through F when applied to a seven-segment common cathode LED display. Each of the signal lines D, , through A, must be capable of driving the number of gate inputs shown in the brackets (fan-out requirement) to both the high-level and low-level required voltages. The output equations for the circuit in Fig. 81.17 are the minimum sum of products (SOP) equations for the 1’s of the functions OA though OG, respectively, represented by the truth table in Table 81.4. A more efficient way (in terms of package count) to implement the same combinational logic function would be to use a medium-scale integration (MSI) 4- to 16-1ine decoder with gates as illustrated in Fig. 81.19. The tildes are used as in-line symbols for the logical complements of D0 through D15 as recommended by IEEE. FIGURE 81.17 Gate-level logic circuit for binary to seven-segment hexadecimal character generator. D A
Q0 FIGURE 81. 18 Seven-segment common cathode led display TABLE814 Truth Table for Binary to Seven-Segment Hexadecimal Character Generator Seven-Segment Output DCB AOA O OD OE OF OG Display Character 0 0 00011110000 00 1010101010101 10110111111010 010001010l11l 23456789Abcd 0 The decoder circuit in Fig. 81.19 requires only 8 IC packages compared to the gate-level circuit in Fig. 81.17 which requires 18 IC packa ges. Functio onally, both circuits perform the same. The output equations for the circuit in Fig. 81.19 are the canonical or standard SoP equations for the 0s of the functions OA though OG, respectively, represented by the truth table(Table 81.4). The gates shown in Fig. 81. 19 with more than four inputs are eight-input NAND gates with each unused input tied to Vac via a pull-up resistor (not shown on the logic diagram). An even more efficient way to implement the same combinational logic function would be to utilize part of a simple programmable read only memory(PROM)circuit such as the 27$19 fuse programmable PROM in Fig 81.20. An equivalent architectural gate structure for a portion of the PROM is shown in Fig. 81.21. The Xs in Fig. 81.21 represent fuses that are left intact after programming the device. The code for programming the PROM or generating the truth table of the function can be read either from the truth table(Table 81.4)or directly from each line of the circuit diagram in Fig. 81.21(expressed in hexadecimal: 7E, 30, 6D, 79, 33, 5B, 5F, 70, 7E, 7B, 77, IF, 4E, 3D, 4F, and 47)beginning with the first line, which represents binary input 0000, e 2000 by CRC Press LLC
© 2000 by CRC Press LLC The decoder circuit in Fig. 81.19 requires only 8 IC packages compared to the gate-level circuit in Fig. 81.17 which requires 18 IC packages. Functionally, both circuits perform the same. The output equations for the circuit in Fig. 81.19 are the canonical or standard SOP equations for the 0’s of the functions OA though OG, respectively, represented by the truth table (Table 81.4). The gates shown in Fig. 81.19 with more than four inputs are eight-input NAND gates with each unused input tied to VCC via a pull-up resistor (not shown on the logic diagram). An even more efficient way to implement the same combinational logic function would be to utilize part of a simple programmable read only memory (PROM) circuit such as the 27S19 fuse programmable PROM in Fig. 81.20. An equivalent architectural gate structure for a portion of the PROM is shown in Fig. 81.21. The X’s in Fig. 81.21 represent fuses that are left intact after programming the device. The code for programming the PROM or generating the truth table of the function can be read either from the truth table (Table 81.4) or directly from each line of the circuit diagram in Fig. 81.21 (expressed in hexadecimal: 7E, 30, 6D, 79, 33, 5B, 5F, 70, 7F, 7B, 77, 1F, 4E, 3D, 4F, and 47) beginning with the first line, which represents binary input 0000, FIGURE 81.18 Seven-segment common cathode LED display. TABLE 81.4 Truth Table for Binary to Seven-Segment Hexadecimal Character Generator Binary Inputs Seven-Segment Outputs D C B A OA OB OC OD OE OF OG Displayed Characters 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 2 0 0 1 1 1 1 1 1 0 0 1 3 0 1 0 0 0 1 1 0 0 1 1 4 0 1 0 1 1 0 1 1 0 1 1 5 0 1 1 0 1 0 1 1 1 1 1 6 0 1 1 1 1 1 1 0 0 0 0 7 1 0 0 0 1 1 1 1 1 1 1 8 1 0 0 1 1 1 1 1 0 1 1 9 1 0 1 0 1 1 1 0 1 1 1 A 1 0 1 1 0 0 1 1 1 1 1 b 1 1 0 0 1 0 0 1 1 1 0 C 1 1 0 1 0 1 1 1 1 0 1 d 1 1 1 0 1 0 0 1 1 1 1 E 1 1 1 1 1 0 0 0 1 1 1 F
D(56,11,1214,15 D(2,12,1415) ND上 -D(1,47,10,15) 15b D(1,34,579) 8-input NAND gate D(1,2,3,7,13) FIGURE 81. 19 Decoder logic circuit for binary to seven-segment hexadecimal character generator. circuit is optimum since it represents a maximum efficiency by requiring only a single IC package Programmable logic devices(PLDs), such as PROM, programmable array logic(PAL), and programmable logic array(PLA)devices, are fast becoming the preferred devices when implementing combinational as well sequential logic circuits. This is true because these devices(a)use less real estate on a pc board, (b)shorten design time, (c)allow design 27s19 changes to be made more easily, and (d) improve reliability because Figure 81.22 shows a PAL16L8 implementation for the binary to even-segment hexadecimal character generator that also requires just a single IC package. The fuse map for this design was obtained using the software program PLDesigner-XL. Karnaugh maps are handy tools that allow a designer to easily obtain minimum SOP equations for either the 1s or Os of Boolean functions of up to four or five variables; however, [7JAV A not use there are a host of commercially available software programs that pro. map generation for PLDs and field programmable gate arrays(FPGidsz vide not only Boolean reduction but also equation simulation and fus FIGURE 81.20 PROM implementation PLDesigner-XL(trademark of Min, Incorporated)is an example of for binary to seven-segment hexadecimal a premier commercial software package available for logic synthesis character generator. for PLDs and FPGAs, for both combinational logic and sequential logic circuits. e 2000 by CRC Press LLC
© 2000 by CRC Press LLC down to the last line, which represents binary input 1111. The PROM solution for the combinational logic circuit is optimum since it represents a maximum efficiency by requiring only a single IC package. Programmable logic devices (PLDs), such as PROM, programmable array logic (PAL), and programmable logic array (PLA) devices, are fast becoming the preferred devices when implementing combinational as well as sequential logic circuits. This is true because these devices (a) use less real estate on a pc board, (b) shorten design time, (c) allow design changes to be made more easily, and (d) improve reliability because of fewer connections. Figure 81.22 shows a PAL16L8 implementation for the binary to seven-segment hexadecimal character generator that also requires just a single IC package. The fuse map for this design was obtained using the software program PLDesigner-XL. Karnaugh maps are handy tools that allow a designer to easily obtain minimum SOP equations for either the 1’s or 0’s of Boolean functions of up to four or five variables; however, there are a host of commercially available software programs that provide not only Boolean reduction but also equation simulation and fuse map generation for PLDs and field programmable gate arrays (FPGAs). PLDesigner-XL (trademark of Minc, Incorporated) is an example of a premier commercial software package available for logic synthesis for PLDs and FPGAs, for both combinational logic and sequential logic circuits. FIGURE 81.19 Decoder logic circuit for binary to seven-segment hexadecimal character generator. FIGURE 81.20 PROM implementation for binary to seven-segment hexadecimal character generator