Design of Digital Systems II Combinational Logic Design Practices (1) Moslem Amiri, Vaclav Prenosil Embedded Systems Laboratory Faculty of Informatics, Masaryk University Brno, Czech Republic amiriOmail.muni.cz prenosilOfi.muni.cz November, 2012 Circuit Timing • Outputs of real circuits take time to react to their inputs • Most digital systems are sequential circuits • Operate step-by-step under control of a periodic clock signal • Speed of clock is limited by the worst-case time that it takes for operations in one step to complete • The greatest challenge in completing a board-level or an ASIC design is achieving required timing performance Moslem Amiri, Václav Přenosil Design of Digital Systems II 2/35 Circuit Timing: Timing Diagrams • Timing diagram • Illustrates logical behavior of signals in a digital circuit as a function of time • Arrows are drawn to show causality • Which input transitions cause which output transitions • The most important information is a specification of delay between transitions • Different paths through a circuit may have different delays • Delay through any given path may vary depending on whether output is changing from LOW to HIGH or from HIGH to LOW • Since delays can vary depending on voltage, temperature, and manufacturing parameters, delay is seldom specified as a single parameter • Minimum, typical, and maximum values Moslem Amiri, Vaclav Přenosi Design of Digital Systems II 3/35 Circuit Timing: Timing Diagrams (a) GO -ENB ■ READY ■ DAT (b) GO READY GO READY \ — *RDY —- - tRDY - "-t DAT-- --Wt-*- _m www 'RDYmin --tRDYmax —- ->- ^DATmin-- "-^DATma>! WWW /////// Figure 1: Timing diagrams for a combinational circuit: (a) block diagram of circuit; (b) causality and propagation delay; (c) minimum and maximum delays. Moslem Amiri, Václav Přenosi Design of Digital Systems II 4/35 Circuit Timing: Timing Diagrams • For any signal that carries a bit of data, timing diagram needn't show whether signal changes from 1 to 0 or from 0 to 1 at a particular time, only that a transition occurs then • A group of data signals in a bus is often processed by identical circuits • Hence, all signals in bus have same timing, and can be represented by a single line in timing diagram Moslem Amiri, Václav Přenosi Design of Digital Systems II 5/35 Circuit Timing: Timing Diagrams (a) WRITEL DATA IN DATAOUT must be stable old new data 'setup T 'oUTmin ~" 'oUTmax L 'hold (b) CLEAR P\_ _A_A_ÍY COUNT STEP[7:0] FF || 00 ]| 01 ]( 02 ](" 03 Figure 2: Timing diagrams for data signals: (a) certain and uncertain transitions; (b) sequence of values on an 8-bit bus. Moslem Amiri, Václav Přenosí Design of Digital Systems II November, 2012 6/35 Circuit Timing: Propagation Delay • Propagation delay of a signal path is time that it takes for a change at input of path to produce a change at output of path • A combinational circuit with many inputs and outputs has many different paths • Each one may have a different propagation delay • Propagation delay when output changes from LOW to HIGH (tpLH) may be different from delay when it changes from HIGH to LOW (tPHL) 7/35 Combinational Programmable Logic Devices (PLDs) • There are a large variety of ICs that can have their logic function "programmed" into them after they are manufactured • Most of these devices use technology that also allows function to be reprogrammed • If you find a bug in your design, you may be able to fix it without physically replacing or rewiring device Moslem Amiri, Václav Přenosi Design of Digital Systems II 8/35 Combinational PLDs: Programmable Logic Arrays (PLAs) • Historically, first PLDs were PLAs • A PLA is a combinational, two-level AND-OR device that can be programmed to realize any sum-of-products logic expression, subject to size limitations of device • Limitations are » Number of inputs (n) • Number of outputs (m) • Number of product terms (p) • In general, p is far less than number of n-variable minterms (2") • Thus, a PLA cannot perform arbitrary n-input, m-output logic functions • Its usefulness is limited to functions that can be expressed in SOP form using p or fewer product terms • An n x m PLA with p product terms contains p 2n-input AND gates and m p-input OR gates Moslem Amiri, Václav Přenosil Design of Digital Systems II 9/35 Combinational PLDs: Programmable Logic Arrays (PLAs) 11 -Cs: "2 —05= 13 —05= 14 —^5= ) .) .) ,) P1 P2 P3 P4 P5 P6 01 02 03 Figure 3: A 4 x 3 PLA with six product terms. 10 / 35 Combinational PLDs: Programmable Logic Arrays (PLAs) • Each input connects to a buffer/inverter that produces both a true and a complemented version of signal for use within array • Potential connections in array are indicated by X's • Device is programmed by keeping only connections that are actually needed • Selected connections are made by fuses, which are not actually fuses, but nonvolatile memory cells that can be programmed to make a connection or not Moslem Amiri, Václav Přenosi Design of Digital Systems II 11 / 35 Combinational PLDs: Programmable Logic Arrays (PLAs) 11 -\X 12 —bs= 13 —Ds= 14 —PS= 000000 P1 P2 P3 P4 P5 P6 01 02 03 Figure 4: Compact representation of a 4 x 3 PLA with six product terms. Moslem Amiri, Václav Přenosi Design of Digital Systems II 12 / 35 Combinational PLDs: Programmable Logic Arrays (PLAs) • PLA in Fig. 4 can perform any three 4-input combinational logic functions that can be written as SOPs using a total of six or fewer distinct product terms, e.g. 01 = 11-12 + II' ■ 12' ■ 13' ■ 14' 02 = II- 13' + II' ■ 13- 14 + 12 03 = II- 12 + II-13' + II' ■ 12' ■ 14' • These equations have a total of eight product terms, but first two terms in 03 are same as first terms in 01 and 02 • Programmed connection pattern in Fig. 5 matches these logic equations Moslem Amiri, Vaclav Přenosi Design of Digital Systems II 13 / 35 Combinational PLDs: Programmable Logic Arrays (PLAs) 11 -\X i3-b= 000000 P1 *S-SS- P2 P3 P4 P5 *s-ä í-ss- P6 D- 01 02 03 Figure 5: A 4 x 3 PLA programmed with a set of three logic equations. Moslem Amiri, Václav Přenosi Design of Digital Systems II 14 / 35 Combinational PLDs: Programmable Logic Arrays (PLAs) 11 -Cs: "3 —bs= 14 —pS= j i-äŕ Ji-ä 5- 000000 P1 P2 P3 P4 P5 P6 01 1 02 O 03 O Figure 6: A 4 x 3 PLA programmed to produce constant 0 and 1 outputs. Moslem Amiri, Václav Přenosi Design of Digital Systems II 15 / 35 Combinational PLDs: Programmable Array Logic (PAL) • A special case of a PLA, and basis of today's most commonly used PLDs, is PAL device • Unlike a PLA, a PAL device has a fixed OR array • PAL devices also use bidirectional input/output pins • One of today's most commonly used combinational PLD structures is " PAL16L8" Moslem Amiri, Václav Přenosil Design of Digital Systems II 16 / 35 Combinational PLDs: Programmable Array Logic (PAL) Figure 7: Logic diagram of the PAL16L8. 17 / 35 Combinational PLDs: Programmable Array Logic (PAL) PAL16L8 1 11 12 01 13 I02 14 I03 15 I04 16 I05 17 I06 18 I07 19 08 110 19 2 3 18 4 17 5 16 6 15 7 14 8 13 9 12 11 Figure 8: Logic symbol for the PAL16L8. 18 / 35 Combinational PLDs: Programmable Array Logic (PAL) • PAL16L8 • Its programmable AND array has 64 rows and 32 columns and 64 x 32 = 2048 fuses • Each of 64 AND gates in array has 32 inputs, accommodating 16 variables and their complements • Eight AND gates are associated with each output pin • Seven of them provide inputs to a fixed 7-input OR gate • The eighth (called output-enable gate) is connected to three-state enable input of output buffer • Buffer is enabled only when output-enable gate has a 1 output • An output can perform only logic functions that can be written as sums of seven or fewer product terms • Each product term can be a function of any or all 16 inputs • Although PAL16L8 has up to 16 inputs and up to 8 outputs, it is housed in a dual in-line package with only 20 pins, including two for power and ground (pins 10 and 20) » This is result of six bidirectional pins (13-18) that may be used as inputs or outputs or both Moslem Amiri, Vaclav Přenosi Design of Digital Systems II 19 / 35 Combinational PLDs: Programmable Array Logic (PAL) • PAL16L8 • Six of output pins, called I/O pins, may also be used as inputs • If an I/O pin's output-control gate produces a constant 0, then output is always disabled and pin is used strictly as an input • If input signal on an I/O pin is not used by any gates in AND array, then pin may be used strictly as an output • Depending on programming of output-enable gate, output may always be enabled, or it may be enabled only for certain input conditions • If an I/O pin's output-control gate produces a constant 1, output is always enabled, but pin may still be used as an input too • In this way, outputs can be used to generate first-pass "helper terms" for logic functions that cannot be performed in a single pass with limited number of AND terms available for a single output • With an I/O pin always output-enabled, output may be used as an input to AND gates that affect the very same output • That is, we can embed a feedback sequential circuit Moslem Amiri, Václav Přenosi Design of Digital Systems II 20 / 35 Combinational PLDs: Generic Array Logic Devices • Sequential PLDs are programmable logic devices that provide flip-flops at some or all OR-gate outputs • One type of sequential PLD is called generic array logic or a GAL device • GAL16V8 • Can be configured to emulate AND-OR, flip-flop, and output structure of any of a variety of combinational and sequential PAL devices • Can be erased and reprogrammed • Its fuses are nonvolatile memory cells • When configured as a combinational device (similar to PAL16L8) is called GAL16V8C Moslem Amiri, Václav Přenosil Design of Digital Systems II 21 / 35 Combinational PLDs: Generic Array Logic Devices Figure 9: Logic diagram of the GAL16V8C. 22 / 35 Combinational PLDs: Generic Array Logic Devices • GAL16V8C • An XOR gate is inserted between each OR output and three-state output driver • One input of XOR gate is pulled up to a logic 1 value but connected to ground via a fuse • If fuse is intact, XOR gate passes OR-gate's output unchanged • If fuse is blown, XOR gate inverts OR-gate's output • Fuse controls output polarity of corresponding output pin • Given a logic function to minimize, we find minimal SOP expressions for both function and its complement • If complement yields fewer product terms, it can be used if GAL16V8's output polarity fuse is set to invert Moslem Amiri, Václav Přenosi Design of Digital Systems II 23 / 35 Combinational PLDs: CPLDs • Complex programmable logic device (CPLD) • A collection of individual PLDs on a single chip, accompanied by a programmable interconnection and input/output structure • Individual PLDs have at least functionality of GAL devices • CPLD fitter • Starting with an HDL description of desired function, a synthesis tool fits the function into an available CPLD device, often the smallest possible • The synthesis tool is called a fitter • Fitter minimizes equation for each PLD output • It also partitions function into individual PLD blocks, and then tries to find the smallest possible device that has enough PLD blocks, product terms, internal connections, and external input/output pins • Fitters allow designer to specify constraints, such as "put these outputs together in the same PLD block" Moslem Amiri, Václav Přenosi Design of Digital Systems II 24 / 35 Combinational PLDs: CPLDs □□□□□□□□□□□□□□□ □ □ □ □ □ □ □ □ □ □ □ □ Programmable Interconnect □□□□□□□□□□□□□□□ □ = input/output block Figure 10: General CPLD architecture. Moslem Amiri, Vaclav Prenosil Design of Digital Systems II 25 / 35 Combinational PLDs: Bipolar PLD Circuits • Early PLA and PAL devices used bipolar circuits 11 —D§= 12 —[S: '3 — 14 -|>I P1 vcc —T—vW- V V V V V V P2' P3' P4' P5' P6' .12 ■12' ■ 13 '13' .14 '14' H>— 01 H>-02 -zd i4 —1>: ./ir -/n ./I2' -/I2 -/I3' "/I3 -/I4' "/I4 V V V V V V P1 vcc —rVW--^AAA--^AAA- P2 P3 P4 P5 P6 4' ■<>—01 -j-' H>— 02 H^—03 Figure 12: A 4 x 3 PLA built using CMOS logic. 28 / 35 Combinational PLDs: CMOS PLD Circuits • In Fig. 12 • An n-channel transistor with a programmable connection is placed at each intersection between an input line and a word line • If input is LOW, transistor is off, but if input is HIGH, transistor is on, which pulls AND line LOW o Overall, an inverted-input AND (NOR) function is obtained • Effects of using an inverted-input AND gate are canceled by using complemented input lines for each input • Outputs of first-level AND functions are combined by another set of NOR functions with programmable connections • Output of each NOR function is followed by an inverter, so an OR function is realized • Overall, PLA performs an AND-OR function as desired • In CMOS PLD technologies, programmable links are not normally fuses • In non-field-programmable devices, such as custom VLSI chips, presence or absence of each link is established as part of metal mask pattern for manufacture of device • The most common programming technology is electrical Moslem Amiri, Václav Přenosí Design of Digital Systems II 29 / 35 Combinational PLDs: CMOS PLD Circuits • Electrically erasable programmable logic device (EEPLD) • An EEPLD can be programmed with any desired link configuration electrically, as well as erased to its original state • EEPLDs use a technology called "floating-gate MOS" 30 / 35 Combinational PLDs: CMOS PLD Circuits floating gate nonfloating gate J* "H " * " t' * " t' t ^ -v,-' v active-low input lines active-high AND lines Figure 13: AND plane of an EEPLD using floating-gate MOS transistors. Moslem Amiri, Václav Přenosi Design of Digital Systems I November, 2012 31 / 35 Combinational PLDs: CMOS PLD Circuits • A floating-gate MOS transistor has two gates • Floating gate is unconnected and is surrounded by extremely high-impedance insulating material • In manufactured state, floating gate has no charge on it and has no effect • Hence, all transistors are connected • To program, we apply a high voltage to non-floating gate at each location where a logical link is not wanted • This causes a temporary breakdown in insulating material and allows a negative charge to accumulate on floating gate • When high voltage is removed, negative charge remains on floating gate • Negative charge prevents transistor from turning "on" when a HIGH signal is applied to nonfloating gate » Transistor is disconnected from circuit Moslem Amiri, Václav Přenosi Design of Digital Systems II 32 / 35 Combinational PLDs: CMOS PLD Circuits • EEPLDs can also be erased • Floating gates in an EEPLD are surrounded by an extremely thin insulating layer and can be erased by applying a voltage of opposite polarity as the charging voltage to nonfloating gate • The same piece of equipment used to program a PLD can be used to erase an EEPLD before programming it » Most CPLDs also use floating-gate programming and erasing technology • FPGAs use read/write memory cells to control state of each connection • Read/write memory cells are volatile • When power is first applied to FPGA, all of its read/write memory must be initialized to a state specified by a separate, external nonvolatile memory • This memory is either a programmable read-only memory (PROM) chip attached to FPGA or is part of a microprocessor subsystem that initializes FPGA as part of overall system initialization Moslem Amiri, Václav Přenosi Design of Digital Systems II 33 / 35 Combinational PLDs: Device Programming and Testing • A PLD programmer or a PROM programmer is a special piece of equipment used to vaporize fuses or charge up floating-gate transistors • It includes sockets that physically accept devices to be programmed • To download desired programming patterns into programmer, it is connected to a PC • Many PLDs feature in-system programmability • Device can be programmed after it is soldered into system • Fuse patterns are applied to device serially using four extra signals and pins called JTAG port, defined by IEEE standard 1149.1 • These signals are defined so that multiple devices on same printed-circuit board can be "daisy chained" and selected and programmed during board manufacturing process using just one JTAG port on a special connector • Fuse patterns are verified as they are programmed into a device • Verifying fuse pattern does not prove that device will perform logic function specified by those fuses • Device may have unrelated internal defects • The only way to test for all defects is to put device into its normal operational mode, apply test-vector inputs, and check outputs against expected results 34 / 35 References ^ John F. Wakerly, Digital Design: Principles and Practices (4th Edition), Prentice Hall, 2005. 35 / 35