Intro Electrical & Comp Engin
Intro Electrical & Comp Engin ENGIN 112
Popular in Course
verified elite notetaker
Popular in Engineering and Tech
This 574 page Class Notes was uploaded by Tony Gutkowski on Friday October 30, 2015. The Class Notes belongs to ENGIN 112 at University of Massachusetts taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/232298/engin-112-university-of-massachusetts in Engineering and Tech at University of Massachusetts.
Reviews for Intro Electrical & Comp Engin
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/30/15
ENGINllZ Introduction to Electrical and Computer Engineering Fall 2003 Prof Russell Tessier Understanding Sequential Circuit Timing Perhaps the two most distinguishing characteristics of a computer are its processor clock speed and the size of its main memory While it is relatively easy to understand the concept of main memory size the number of storage bits in the computer the concept of processor clock speed is a little more dif cult to grasp In this document we will explain what is meant by sequential circuit clock speed and more importantly how to calculate it using the timing parameters of combinational and sequential circuit components I 1 lt per gt c Figure 1 Periodic Clock Signal As we have discussed this term edgetrigged ip ops such as the D ip op are controlled by a clock signal such as the signal labeled Clk in Figure l A clock signal is a periodic square wave which alternates between logic high 1 and logic low 0 values at predictable times The amount of time between rising clock edges is called the clock period Tim of the clock In modern computers the clock period is usually under 10 nanoseconds 10 us The inverse of the clock period T is the clock frequency 1 Since the clock is used as the control input to edge triggered ip ops the clock frequency measures how often the data is transfered or clocked into edgetriggered ip ops A bigger clock frequency indicates that data is being stored more quickly and the sequential circuit is generating results at a faster rate Typical clock frequencies for modern computer systems range from 1 megaHertz MHZ to around 5 gigaHertz GHZ 1 Timing Parameters for Combinational Logic When implemented physically combinational circuits such as AND and OR gates eXhibit certain timing characteristics When a binary value 0 or 1 is applied at the input to a combinational circuit the change at the circuit output is not instantaneous due to electrical constraints Circuit inputtooutput delay in combinational circuits can be expressed with two parameters tpd and ted de ned as follows 0 Propagation delay tpd This value indicates the amount of time needed for a change in a logic input to result in a permanent change at an output Combinational logic is guaranteed not to show any further output changes in response to an input change after tpd time units have passed Figure 2 Combinational Propagation and Contamination Delay 0 Contamination delay ted This value indicates the amount of time needed for a change in a logic input to result in an initial change at an output 1 Combinational logic is guaranteed not to show any output change in response to an input change before ted time units have passed An example of combinational propagation and contamination delay appears in Figure 2 When in put X changes the change in Y is not instantaneous The inverter output maintains its initial value until time ted has passed After this time the Y output of the inverter may be at an intermediate value for a While indicated by the crosshatched area before the nal output value is created After the propagation delay tpd the inverter output is stable and is guaranteed not to change again until another input change Combinational propagation delays are additive It is possible to determine the propagation delay of a larger combinational circuit by adding the propagation delays of the circuit components along the longest path For example the propagation delay of the combined circuit in Figure 3 is 5 ns since the longest delay from a circuit input w m y to the output 2 is the sum of the component propagation delays through gates A and B 3 ns 2 ns 5 ns The 4 ns propagation delay path through gates C and B can be ignored in determining the overall propagation delay of the circuit since it is shorter than 5 ns In contrast the determination of the contamination delay of the combined circuit requires identifying the shortest path of contamination delays from input to output In Figure 3 the contamination delay of the combined circuit is 2 ns since the shortest sum of contamination delays from an input y to an output 2 is tcdC tcdB 1 ns 1 ns 2ns Note that this value is smaller than the contamination delay path through gates A and B 2 ns lns 3 ns tcd 1 ns tpd 2 ns Figure 3 Combined Combinational Circuit Dealy 2 Timing Parameters for Sequential Logic Like combinational circuits when sequential circuits such as edgetriggered ip ops are phys ically implemented they exhibit certain timing characteristics Unlike combinational circuits these characteristics are speci ed in relation to the clock input Since ip ops only change value in response to a change in the clock value timing parameters can be speci ed in relation to the rising for positive edgetriggered or falling for negativeedge triggered clock edge The fol lowing parameters specify sequential circuit behavior Unless otherwise speci ed the following descriptions pertain to positive edgetriggered circuits Similar de nitions can be made for nega tive edgetriggered circuits 0 Propagation delay talkQ This value indicates the amount of time needed for a change in the ip opclock input eg rising edge to result in a permanent change at the ip op output Q When the clock edge arrives the D input value is transfered to output Q Note from Figure 4 that the output of the ip op may be at an intermediate value for a while indicated by the crosshatched area before the nal output value is created After talkQ the output is guaranteed not to change value again until another clock edge trigger eg rising edge arrives o Contamination delay ted This value indicates the amount of time needed for a change in the ip op clock input to result in the initial change at the ip op output Q Note from Figure 4 that the output of the ip op maintains its initial value until time ted has passed The ip op is guaranteed not to show any output change in response to an input change until after ted has passed Setup time 255 This value indicates the amount of time before the clock edge that data input D must be stable As shown in Figure 4 D is stable 255 time units before the rising telk m Figure 4 Setup and Hold Time for Sequential Circuits clock edge 0 Hold time 25 This value indicates the amount of time after the clock edge that data input D must be held stable As shown in Figure 4 the hold time is always measured from the rising clock edge for positive edgetriggered to a point after the edge Setup and hold times are restrictions that a ip op places on combinational or sequential circuitry that drives a ip op D input The circuit must be designed so that the D ip op input signal arrives at least 259 time units before the clock edge and does not change until at least 25 time units after the clock edge If either of these restrictions are violated for any of the ip ops in the circuit the circuit will not operate correctly These restrictions limit the maximum clock frequency at which the circuit can operate If the rising clock edges in Figure l are too close together data will not have enough time to propagate through the circuit to the ip op input and arrive 255 time units before the rising clock edge 3 Determining the Max Clock Frequency for a Sequential Circuit Most digital circuits contain both combinational components gates muxes adders etc and sequential components ip ops These components can be combined to form sequential circuits that perform computation and store results By using combinational and sequential component parameters it is possible to determine the maximum clock frequency at which a circuit will operate and generate correct results This analysis can best be examined through use of an example A sample sequential cicuit is shown in Figure 5 Before starting timing analysis consider the ow of data in this circuit in response to a rising clock tckQ 10 ns t 2ns cd tclkQ 10ns ts2ns tcd2quots tcd2quots th2ns tpd5ns X Y D D Q D Q Out A B Clk Figure 5 An Example Sequential Circuit edge starting at ip op A 1 Following the rising clock edge on Clk a valid output appears on signal X after th 10 ns 2 A valid output Y appears at the output of inverter F tpd 5 ns after a valid X arrives at the gate 3 Signal Y is clocked into ip op B on the next rising clock edge This signal must arrive at least 259 2ns before the rising clock edge As a result the minimum clock period Tmm of the circuit is Tmm t01k7QAtpdF t5B 10713 5713 2713 17713 1 and the maximum clock frequency of the circuit is Tim 171m 588 MHZ Waveforms that show the determination of the minimum clock period are show in Figure 6 Since the Clk input is attached to both ip ops both will change value at the same time On each clock edge the same three steps starting from ip op A are repeated On the next edge a new value is clocked into ip op B that is a result of the previous clock edge on ip op A In a typical sequential circuit design there are often millions of ip op to ip op paths that need to be considered in calculating the maximum clock frequency This frequency must be determined by locating the longest path among all the ip op paths in the circuit For example consider the circuit shown in Figure 7 In this example there are three ip op to ip op paths op A to op Figure 6 Timing Waveforms for the Circuit in Fig 5 B op A to op C op B to op C Using an approach similar to Equation 1 the delay along all three paths are 0 TAB talkQA t9B 9 ns 2 ns 11 ns 0 TAO t01k7QA tpdZ 7550 9 118 4 118 2ns 15 IIS 0 T30 2501164203 tpdZ 2590 10 ns 4 ns 2 ns 16 ns Since the T30 is the largest of the path delays the minimum clock period for the circuit is Tmm 16 ns and the maXimum clock frequency is 625 MHZ Twin 4 Validating FlipFlop Hold Time Unfortunately simply designing a circuit for a speci c maXimum clock frequency is not enough to ensure that the circuit will work properly As mentioned earlier the hold time 25 must be satis ed for each ip op input indicating that each D input cannot change until 25 time units after the clock edge Fortunately the contamination delays of combinational circuitry and ip ops help prevent ip op inputs from changing instantaneously This observation can be illustrated by reexamining Figure 5 The hold time requirement on ip op B indicates that the Y input to ip op B should not change until at least 2 ns after the rising clock edge of Clk By examining the circuit it can be seen that the earliest the signal can start to change is equal to the sum of the contamination delays of ip op A and inverter X Therefore if telk09quots telk09quots tcd2ns tcd2ns ts2ns tpd4ns ts2ns th1ns tcd2ns th1ns gt A C gt gt tclkQ1Dns ted 2ns ts2ns th1ns Figure 7 Multipath Sequential Circuit 75MB g tcdA tcdX 2 the circuit is guaranteed to work correctly Since th 2 ns is less than tcdA tcdB 4 ns the hold time is satisifed and the circuit will work correctly A similar analysis can be performed along each ip op to ip op path in Figure 7 These three paths lead to the following relationships for the A to B A to C and B to C paths respectively MB S tcdA A to B path MC S MM tcdZ A to Cpathl MC S 25MB tcdZ B to Cpathl plugging in the values from Figure 7 gives 1713 g 2713 A to Bpath 1713 g 2713 2713 A to Cpath 1713 g 2713 2713 B to Cpath 3 4 5 6 7 8 It is apparent that even the fastest ip op to ip op path 2 ns is slower that the required hold time 1 ns None of the ip op input values will change until at least 2 ns following the clock edge due to the contamination delays along the paths For each circuit in the path the contamination delay guarantees that a change in the circuit input will not be shown at the circuit output until ted time units 5 Conclusion Sequential circuits rely on a clock signal to control the movement of system data Given a set of combinational and sequential components and their associated timing parameters it is possible to determine the maximum clock frequency that can be used with the circuit This analysis includes the examination of every ip op to ip op path in the circuit The examination includes both the propagation delays along the paths and the data setup time at the destination ip op Following the calculation of the maximum clock frequency each ip op to ip op path can be examined to ensure that ip op hold times are satis ed If the contamination delays along each path are greater than or equal to the destination ip op hold time the circuit will operate as designed References 1 S Ward and R Halstead Computation Structures McGrawHill Boston Ma 1991 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 9 More Kamaugh Maps and Don 39t Cares 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z L9 Mm szzugh Maps Sememherzunna Overview Karnaugh maps with four inputs Same basic rules as three input Kmaps Understanding prime implicants Related to minterms Covering all implicants Using Don t Cares to simplify functions Don t care outputs are undefined Summarizing Karnaugh maps ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh Maps for Four Input Functions Represent functions of 4 inputs with 16 minterms Use same rules developed for 3input functions Note bracketed sections shown in example yz y wx 0 0 0 1 11 10 00 wxlylzi WleZ wxlyz Wxlyzi m0 m1 ma m2 01 w39xy z w39xy z w xyz w xyz m4 m5 m7 m6 x 11 wxy z wxy z wxyz wxyz m12 m1 m15 mill w 10 WXyZ wxyZ wxlyz wxyzl m8 m9 mll mIO Z a b Fig 3 8 Four variable Map ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh map 4variable example FABCD Zm023567810111415 F C A39BD B39D39 oooo39quotquot SoluTion 361 can be considered as a coordinaTe System ENGN112 L9 More Karnaugh Maps September 22 2003 Design examples Kmap for LT Kmap for EQ Kmap for GT LTA39B39DA39CB39CD EQ A39B39C39D39 A39BC39D ABCD AB39CD39 GT BC39D39AC39ABD39 Can you draw The Tr39uTh Table for These examples ENGN112 L9 More Karnaugh Maps September 22 2003 Physical Implementation Step 1 Truth table Step 2 Kmap Step 3 Minimized sumof products Step 4 Physical EQ implementation with gates 1 O O Kmap for EQ ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh Maps Four variable maps CD 00 01 11 10 00 O O O 01 11 10 O 1 FA39BC 39A39CD 39ABC AB 39C D 39ABC39AB 39C FBC39CD 39 AC AD39 Need to make sure all 1 s are covered Try to minimize total product terms Design could be implemented using NANDs and NORs ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh maps Don t cares In some cases outputs are undefined We don t care if the logic produces a 0 or a 1 This knowledge can be used to simplify functions AB A CD 00 O1 11 10 00 0 0 X 0 Treat X s like either 1 s or O s Very useful 01 1 1 X 1 D OK to leave some X s uncovered 111100 C 1Ooxoo T ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh maps Don t cares fABCD 2 m13579 d61213 f A39DC D AB CD 00 01 11 10 OO O X 0 0111 x 1 C 11 1 o o 10 o o o T without don39t cares ENGN112 L9 More Karnaugh Maps AAA A x xaoooooooolgt oooox oooow AAOOAAOOAAOOAAOOO Ao xo xo xo xo xo xo xoU ooxxoo xo xx xo xo xol39 September 22 2003 Don t Care Conditions n sorne situations we don t care about the vaue of a function for certaIn combInatIons of the varIables these combinations may be impossible in certain contexts or the value of the function may not matter in when the combinations occur In such situations we say the function is incompletely specified and there are multiple completely specified logic functions that can be used in the deSIgn so we can select a function that gives the simplest circuit When constructing the terms in the simplification procedure we can choose to either cover or not cover the don t care conditions ENGN112 L9 More Karnaugh Maps September 22 2003 Map Simplification with Don t Cares D AB 00 01 11 10 00 0 10 0 01 X EX 1 FA39C39DBAC l x 10 x 0L1 1 Alternative covering CD 00 01 11 10 A0 00 01 A x x FA39B39C39DABC BCAC 1111 1 x 10 x 0L1 1 ENGN112 L9 More Karnaugh Maps September 22 2003 Karnaugh maps don t cares cont d fABCD 2 m13579 d61213 f AD B39C39D without don39t cares f with don39t cares AD CD by using don39t care as a quot1quot a 2cube can be formed rather than a 1cube to cover this node don39t cares can be treated as Is or Os depending on which is more advantageous ENGN112 L9 More Karnaugh Maps September 22 2003 Definition of terms for twolevel simplification Implicant Single product term of the ONset terms that create a logic 1 Prime implicant Implicant that can39t be combined with another to form an implicant with fewer literals Essential prime implicant Prime implicant is essential if it alone covers a minterm in the Kmap Remember that all squares marked with 1 must be covered Objective Grow implicant into prime implicants minimize literals per term Cover the Kmap with as few prime implicants as possible minimize number of product terms ENGN112 L9 More Karnaugh Maps September 22 2003 Examples to illustrate terms 6 prime implicanTs A39B39D BC39 AC A39C39D AB B39CD D essenTIal minimum coverz AC BC39 A39B39D 5 prime implicanTs BD ABC39 ACD A39BC A39C39D essenTial minimum cover 4 essenTial implicanTs ENGN112 L9 More Karnaugh Maps September 22 2003 Prime Implicants Any single 1 or group of ls in the Karnaugh map of a function F is an implicant of F A product term is called a prime implicant of F if it cannot be combined with another term to eliminate a variable If a function F is represented by this Karnaugh Map Which of the following terms are implicants of F and which ones are prime Example implicants of F a AC D b BD 0 A B C D cl AC Hlllla llnlpllcanp 9 ECU Ml la ENGN112 L9 More Karnaugh Maps September 22 2003 Essential Prime Implicants A product term is an essential prime implicant if there is a minterm that is only covered by that prime implicant The minimal sumof products form of F must include all the essential prime implicants of F CD C CD C AB 00 01 11 10 AB 00 01 11 10 00 00 1 1 1 01 01 B B 11 11 A A 10 10 D D a Essential prime implicants b Prime implicants CD B C BD and B D AD and AB Fig 3 11 Simplification Using Prime Implicants ENGN112 L9 More Karnaugh Maps September 22 2003 Summary Kmaps of four literals considered Larger examples exist Don t care conditions help minimize functions Output for don t cares are undefined Result of minimization is minimal sumofproducts Result contains prime implicants Essential prime implicants are required in the implementation ENGN112 L9 More Karnaugh Maps September 22 2003 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 12 Registers and Counters I Registers An nbit register is just a set of n flipflops that are connected to a common clock and are used to store n bits A register may also include other circuitry to control the values that are stored Example 4bit D flipflop register IO I3 data bits input A0 stored bits D l l V 0 030 l L 3 l I l D gtC R E 0 03 0 i When Clear 0 all flipflops are reset to 0 When Clear1 the inputs are transferred to the flipflop outputs at the next positive clock edge This is called parallel loading all the data are transferred at the same time One problem with the simple register design is that the inputs are transferred to the register that is stored at the flipflop outputs on each clock cycle If we want to maintain the stored values we must either make sure that the inputs don t change or have some circuitry that prevents the transfer One way to control the loading of new data into the register is to use a 2 x 1 multiplexer for each flipflop that connects either the new data input or the currently stored bit to the flipflop input depending on the value of a load control bit When Load 0 the input to the flipflop is set to the current output AK when Load 1 the flipflop input is the new data input Ik 2X 1 N K Load Ak o A shift register is a connection of flipflops that shift data from one register to the next on a clock edge Serial Input 8 D D Serial Output 80 D gtc R I 0 030 0 030 om clear At a clock edge A new bit of data 8 is transferred into the leftmost flipflop Each flipflop except for the rightmost transfers its current stored bit to the next flipflop to the right The current output bit 80 is replaced by the value currently at the rightmost flipflop s input Note we can also add load control to each flipflop s input if we want to prevent data transfer on some clock cycles Example Suppose the four flipflops in the shift register diagram are all loaded with 0 s initially Asequence of input bits 101010 synchronized with the clock enters the shift register at 8 Let the clock transition times be denoted T0 initial time T7 etc What values are stored in the flipflops during the clock cycles Time Input Values Stored in First Output SI Three FlipFlops SO After To 1 0 0 0 0 After T1 0 1 0 0 0 After T2 1 0 1 0 0 After T3 0 1 0 1 0 After T4 1 0 1 0 1 After T5 0 1 0 1 0 When bits are transferred one at a time from a source register to a destination register we say we have serial data transfer as opposed to the parallel transfer in the first register that we saw Serial data transfer makes use of shift registers Typical system for serial data transfer using two 4bit shift registers Feedback loop keeps data Shift Register Shift Register Circulating In A B RegisterA SA SOA SIB A A clock Shift CLK control gt 805 Shift control selects four clock pulses to perform data transfer Example Suppose we want to transfer four bits 1 0 1 0 stored in RegisterA to Register B which initially stores bits 0 1 0 1 llllllllllllCock T1 T2 Ts T4 Shift Control Time Register A Register B Initial 1010 0101 AfterT1 0101 0010 AfterT2 1010 1001 AfterT3 0101 0100 AfterT4 1010 1010 Many operations can be done with either parallel or serial data transfers parallel operations are faster but serial designs are often simpler that is require fewer components to implement One example is an adder circuit Recall the 4bit adder circuit that we saw previously A33 A2 32 A1 B1 A0 Bo fc lC ll ll c4lt FA lt 3 FA lt 2 FA lt07 FA lt Co l l l l s3 s2 31 so This circuit works essentially in parallel it requires a separate Full Adder block for each bit position Note that this is a combinational circuit Now suppose that we want to construct a serial adder operation implies that we must consider time as a parameter so we must design this adder as a sequential circuit Let s use a D flipflop to Serial store the current carry bit let the circuit output be the current sum bit and let input bits X y denote the current two bits to be summed along with the current carry bit Current Current Inputs Output Next State StateQ x y S Qt1 O O O O 0 State Table 0 O 1 1 O O 1 O 1 O O 1 1 O 1 1 O O 1 O 1 O 1 O 1 1 1 O O 1 1 1 1 1 1 Notice that we can take advantage of the Full Adder block to generate the sum and carry bits while the inputs can be stored in shift registers In fact to add two fourbit numbers we can use the following circuit Serial input Shift Register B Shift Register Sum bit A l FA Output Input carry I carry Not shown but included in circuit Common I a D Q clock and shift control for registers and flip op and Clear input for flipflop gt CLK Example Go through steps for serial addition of 4bit numbers A0111 and B 1010 Assume that the serial inputs to the B register are all US Note that the addition starts with the flipflop cleared so QT00 39 Time Register Register Q FAlnputs FAOutputs A B ABQ SumCarry To 0111 1010 0 100 1 0 T1 1011 0101 0 110 0 1 T2 0101 0010 1 101 0 1 T3 0010 0001 1 011 0 1 T4 0001 0000 1 end 80 After 4 clock cycles stored sum isl 0001 Carry out bit stored in flip op Sum bits stored in RegisterA Note that data entered serially into a shift register can be taken out in parallel just by tapping into the flipflop outputs Also parallel loading capability can be added then data entrydata removal can be any choice from serialserial serialparallel parallelserial or parallelparallel Also the register can be constructed so it can shift either left or right A register with all these capabilities is called a universal shift register Circuit Parallel outputs A A A Cl C C ear D D C D CLK I I I Control Mode Control Register 81 I 80 Operation 51 4 X1 h 4 X 1 4 X1 4 1 0 O No change SH MUX MUX MUX MUX 0 1Shmright 3210 321i 3210 3210 1 O Shift left I I I I I I I 1 1 Parallel load in igr Serial input for shiftright I 1 h In ShifHeft Parallel inputs II Counters A counter is a register that goes through a specified set of states as transition pulses from a clock or some other source are applied If an n bit register cycles through the binary numbers from 0 000 to 2 1 111 it is called a binary counter If the counter cycles through BCD representations for 01 it is called a BCD counter If all counter transitions are governed by a common clock we have a synchronous counter If instead the pulses governing transitions in some flipflops are generated by the outputs of other flipflops we have a ripple counter Let s design a 3bit binary ripple counter Assume that there are input pulses called Count into one flipflop that trigger the transition of the least significant bit LSB We have 3 flipflops call their outputs A B C and 8 states 000 001 111 Say that we want to initiate a count state transition on the negative edge of the Count pulse The state table is Current State Next State ABC ABC 000 001 001 010 010 011 011 100 100 101 101 110 110 111 Note that on every state transition the least significant bit C is complemented Bit B changes when C changes from 1 to 0 Bit A changes when B changes from 1 to 0 Consider circuit count 0 gt C Note that the pulse edges for transitions from 1 to 0 in each flipflop output are used to initiate data transfer from input to output in the succeeding flipflop n l HUDUl Note that it takes some very small but not zero time for the flipflop output to respond to transitions on the clock input So we can think of the state changes as rippling through the flipflops A negative puse edge in Count causes a change in C a very short time later if that change in C is from 1 to 0 it creates a negative puse edge that in turn triggers a transition in B a very short time later etc Example Say we are in state 010 Consider timing of transitions to succeeding states Example How could we design a BCD ripple counter Note that a BCD counter should have state table using 4 flipflops Current State Next State ABCD ABCD 0000 0001 0001 0010 0010 0011 0011 0100 0100 0101 0101 0110 0110 0111 0111 1000 1000 1001 1001 0000 Note that the pattern is the same as the binary ripple counter a transition from 1 to 0 in a bit triggers a change in the next most significant bit except for state 1001 in that state the next transition must set all registers to 0 That is it must clear all the registers So we can use a 4bit binary ripple counter with a Reset line that 0 when A1 D1 and Count0 D Count Reset A When transition is made to state 1001 the next Count transition to zero sets the Reset to 0 this clears all flipflops and gets us back to state 0000 Ripple counters are examples of asynchronous systems the timing of transitions between state is not controlled by a clock but instead by the possibly irregular timing of the Count pulses Now suppose we want to build a synchronous counter whose transitions are controlled by a clock Let s go through the design procedure for a 3bit synchronous binary counter start with the state table Current State Next State ABC ABC 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 000 Note that Cz 1 C Bz 1 BC BC Az 1 ABC ABC Circuit Clock gtC gtC gtC ENGIN 112 Intro to Electrical and Computer Engineering Lecture 12 Circuit Analysis Procedure 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z L12 CircuitAnalysis Prncedum Septemh2r292 3 Overview Important concept analyze digital circuits Given a circuit Create a truth table Create a minimized circuit Approaches Boolean expression approach Truth table approach Leads to minimized hardware Provides insights on how to design hardware Tie in with Kmaps next time ENGN112 L12 Circuit Analysis Procedure September 29 2003 The Problem How can we convert from a circuit drawing to an equation or truth table Two approaches Create intermediate equations Create intermediate truth tables hi ENGN112 L12 Circuit Analysis Procedure September 29 2003 owgt Label Gate Outputs 1 Label all gate outputs that are a function of input variables 2 Label gates that are a function of input variables and previously labeled gates 3 Repeat process until all outputs are labelled owgt III E o E ENGN112 L12 Circuit Analysis Procedure September 29 2003 Approach 1 Create Intermediate Equations CI Step 1 Create an equation for each gate output based on Its input RABC SAB TC S OutRT ENGN112 L12 Circuit Analysis Procedure September 29 2003 Approach 1 Substitute in subexpressions CI SteEZ Form a relationship based on input variables A C RABC SAB TC SC AB Out RT ABC C AB ENGN112 L12 Circuit Analysis Procedure September 29 2003 Approach 1 Substitute in subexpressions CI Step 3 Expand equation to SOP final result Out ABC C AB ABC AC BC OEDgt 2 l ENGN112 L12 Circuit Analysis Procedure September 29 2003 Approach 2 Truth Table CI Step 1 Determine outputs for functions of input variables A B C R S 000 00 00100 010 01 01101 100 01 10101 110 01 A R 11111 eh C l Out ENGN112 L12 Circuit Analysis Procedure September 29 2003 Approach 2 Truth Table CI Step 2 Determine outputs for functions of intermediate variables ABCC RS 000100 TSC 001000 010101 011001 100101 101001 110101 A R111011 B C Out A S d ENGN112 L12 Circuit Analysis Procedure September 29 2003 Odo OAOO I Approach 2 Truth Table CI Step 3 Determine outputs for function ABCRSTOut 0000000 0010000 RTOut 0100111 0110100 1000111 1010100 1100111 A R1111101 B C Out ENGN112 L12 Circuit Analysis Procedure September 29 2003 More Difficult Example El Step 3 Note labels on interior nodes Fig 4 2 Logic Diagram for Analysis Example ENGN112 L12 Circuit Analysis Procedure September 29 2003 More Difficult Example Truth Table CI Remember to determine intermediate variables starting from the inputs CI When all inputs determined for a gate determine output CI The truth table can be reduced using Kmaps ABCI239 2T1T2T3F1 000010000 001011011 010011011 011101000 100011011 101101000 110101000 111101101 ENGN112 L12 Circuit Analysis Procedure September 29 2003 Summary Important to be able to convert circuits into truth table and equation form WHY leads to minimized sum of product representation Two approaches illustrated Approach 1 Create an equation with circuit output dependent on circuit inputs Approach 2 Create a truth table which shows relationship between circuit inputs and circuit outputs Both results can then be minimized using Kmaps Next time develop a minimized SOP representation from a high level description ENGN112 L12 Circuit Analysis Procedure September 29 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 34 Datapath Analysis 39 ELECTRICAL 9 quot EN GIN EERING UNIVERSITY OF MASSACHUSETTS unvemherzmnna ENGN1 12 L36 szpzlh Analysis Overview Datapaths must deal with input and output data values Implement with tristate buffers Necessary to control external interfaces Perform repetitive operations Some datapaths require decision making Control outputs implemented in ROM Moving towards software Control implemented as a series of instructions Understanding the data and control path ENGN112 L34 Datapath Analysis November 24 2003 Datapath IIO O A wire can be driven by only one tristate at a time If lnPass is active AluPass must be inactive If AluPass is active lnPass must be inactive lnPass OutPass LoadX LoadY Function gt ALU AluPass amp l ENGN112 L34 Datapath Analysis November 24 2003 Datapath IIO ENGN112 L34 Datapath Analysis Two values enter from the left A and B Need to perform ABA In gt X Load A In gt Y Load B AB gt Y ABA gt Out lnPass Four steps and then repeat OutPass In L Out V LoadX A LoadY Function p ALU Alupass amp November 24 2003 Implementing the Control ROM Two values enter from the left A and B Need to perform ABA ROM In gt X Load A State 00 Addr 0100010100 00 In gt Y Load B State 01 1000001100 01 ABgtY State 10 1101101010 10 ABA gt Out State 11 PS 0001100011 11 NS Control outputs PS NS Function LoadX LoadY InPass AluPass OutPass OO O1 000 1 O 1 O 0 O1 10 000 O 1 1 O 0 1O 11 011 O 1 O 1 O 11 00 011 O O O 1 1 ENGIN112 L34 Datapath Analysis November 24 2003 More Complicated Example Can we compute AB AB Currently no place for intermediate storage Solution Add RAM to datapath lnPass OutPass V Load ENGN112 L34 Datapath Analysis November 24 2003 LoadY More Complicated Example Can we compute AB AB Need to add intermediate storage Typical sizes 1 MB ZGB Add RAM to the Datapath OutPass LoadY Function Ampass ENGN112 L34 Datapath Analysis November 24 2003 Implementing the Control ROM Two values enter from the left A and B Need to perform AB AB In gt X Load A State 000 In gt Y Load B State 001 AB gt RAM4 State 010 AB gt X State 011 RAM4 gtY State 100 ABABgtOut State 101 PS NS Function LoadX LoadY InPass AluPass OutPass Addr Read Write 000 001 000 1 0 1 0 0 000 0 0 001 010 000 0 1 1 0 0 000 0 0 010 011 011 0 0 0 1 0 100 0 1 011 100 010 1 0 0 1 0 000 0 0 100 101 000 0 1 0 0 0 100 1 0 101 000 110 0 0 0 1 1 000 0 0 ENGIN112 L34 Datapath Analysis November 24 2003 Does the Value of the Data Matter 0 Problem Add A to itself until overflow occurs Amount of steps depends on A OutPass How can we determine if overflow occurred ENGN112 L34 Datapath Analysis November 24 2003 Implementing the Control ROM using Conditions One value enters from the left Add A to itself until overflow occurs In gt X Y Load A B State 0 Next state 1 XY gt Out X State 1 Next state 1 if no overflow 0 if overflow Include overflow OF bit as a ROM input Note that it doubles the size of the ROM PS OF NS Function LoadX LoadY lnPass AluPass OutPass Addr Read Write 0 0 1 000 1 1 1 0 0 000 0 0 0 1 1 000 1 1 1 0 0 000 0 0 1 0 1 011 1 0 0 1 1 000 0 0 1 1 0 011 1 0 0 1 1 000 0 0 Bits in the ROM Each row indicates a ROM word ENGN112 L34 Datapath Analysis November 24 2003 Implementing the Control ROM with Conditionals Control path may have ROM many Inputs Overflow carry out zero Usedto perform 1o condItIonal operations 00110101100000 11 Addr If statements and loops in programming languages OF Control outputs PS OF NS Function LoadX LoadY lnPass AluPass OutPass Addr Read Write 0 0 1 000 1 1 1 0 0 000 0 0 0 1 1 000 1 1 1 0 0 000 0 0 1 0 1 011 1 0 0 1 1 000 0 0 1 1 0 011 1 0 0 1 1 000 0 0 ENGN112 L34 Datapath Analysis November 24 2003 One More Example 0 Read two values from RAM locations 0 and 1 and store to location 2 Very common operation for microprocessor OutPass LoadY Function Aupass ENGN112 L34 Datapath Analysis November 24 2003 Implementing the Control ROM 0 Perform memory reads and writes RAMO gt x State 00 RAM1 gt Y State 01 XYgt RAM2 State 10 No interaction with outside interfaces In Out is required Very Similar to microprocessor operations PS NS Function LoadX LoadY lnPass AluPass OutPass Addr Read Write 00 01 000 1 0 0 0 0 000 1 0 01 10 000 0 1 0 0 0 001 1 0 10 00 011 0 0 0 1 0 010 0 1 This slide marks the end of required material for this lecture ENGN112 L34 Datapath Analysis November 24 2003 Processor Construction Kit bproblem 1 DATA PATHS Ksprromem 2 CONTROL Inputs from Data Path Fn gt 003 t 9 MM STATIC Sel Data Path Contro Signals RAM QW 1 f 339 ENGN112 L34 Datapath Analysis November 24 2003 Processor Compilation 0 Software engineer writes C program 0 Compiler software converts C to assembly code 0 Assembler converts assembly code to binary format C program Assembly program main Compile LD R1 A load A to Reg R1 int A B 0 LD R2 B load B to Reg R2 ADD R3 R1 R2 Add R1 R2 gt R3 C A 3 ST R3 C Store result in C A B and C are storage locations in main memory DRAM ENGN112 L34 Datapath Analysis November 24 2003 A Microprocessor Architecture Instruction A Memory Similar to HP Alpha D 39 Ra lt2016gt Rb lt1511gt Rbc lt2521gt I I WRAZSEL C3 lt25 gt RA1 Register RA2 lt RC lt2521gt 39VA File WD R31 R32 va 0 Z ltPCgt4 J C 1501 39 BT ASEL A BSEL A B Op Fn lt2926gt ALU Rw Data Memory J m RD 0 1 Z WDSEL l Summary Datapaths are important components of computer systems Interaction between control and data path determines execution time Each sequence of operations can be represented with a ROM program Each row in the state table corresponds to a word in the ROM Multiple rows for each state if the ROM has a control Input eg ALU overflow Next time Notation to represent the data and control paths ENGN112 L34 Datapath Analysis November 24 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 25 State Reduction and Assignment ENGIN112 LE State Reduction and Assignment oemberu 2003 Overview Important to minimize the size of digital circuitry Analysis of state machines leads to a state table or diagram In many cases reducing the number of states reduces the number of gates and flops This is not true 100 of the time In this course we attempt state reduction by examining the state table Other more advanced approaches possible Reducing the number of states generally reduces complexuty ENGN112 L25 State Reduction and Assignment October 31 2003 Finite State Machines Example Edge Detector Bit are received one at a time one per cycle gt such as 000111010 time CLK IN OUT Design a circuit that asserts its output for one cycle when the input bit stream changes from 0 to 1 two different solutions ENGN112 L25 State Reduction and Assignment October 31 2003 State Transition Diagram Solution A IN PS NS OUT ZERO0 oo oo o oo 01 o CHANGEO 01 00 1 1 01 11 1 ONE0 11 oo o 1 11 11 o ENGN112 L25 State Reduction and Assignment October 31 2003 Solution A circuit derivation IN PS NS OUT ZERJ o oo oo 0 IN 99 9 9 CHANGE 0 01 00 1 9 11 J ONE 0 11 oo o 1 11 11 o 39N ENGN112 L25 State Reduction and Assignment NS1 IN PS0 008 N30 IN A A O A I 008 A 39 OUTFS1PSO 1 0 October 31 2003 Solution B Output depends non only on PS but also on input IN N0 OUT0 LetZEROO IN PS NS OUT ONE1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 N1 OUT1 N0 NS IN OUT IN PS OUT0 NS IN FF Ps OUT0 OUT What s the intuition about this solution ENGN112 L25 State Reduction and Assignment October 31 2003 Edge detector timing diagrams CLMLm IN OUT solution A I L l m OUT solution B l Solution A output follows the clock Solution B output changes with input rising edge and is asynchronous wrt the clock ENGN112 L25 State Reduction and Assignment October 31 2003 FSM Comparison Solution B Mealy Machine output function of both PS amp Solution A Moore Machine output function only of PS input maybe more state maybe fewer states synchronous outputs asynchronous outputs no glitching if input glitches so does output one cycle delay output immediately available full cycle of stable output output may not be stable long enough to be useful ENGN112 L25 State Reduction and Assignment October 31 2003 FSM Recaj Moore Machine Mealy Machine input value input valueoutput values STATE output values inputs outputs CL present state next slate next state outputs Both machine types allow onehot implementations ENGINHZ L25 sum Reduclinn and Assignment 0dnher31 znna FSM Optimization State Reduction Motivation lower cost fewer flipflops in one hot implementations possibly fewer flip flops in encoded implementations more don t cares in next state logic fewer gates in next state logic Simpler to design with extra states then reduce later ENGN112 L25 State Reduction and Assignment Example Odd parity checker A as eeg October 31 2003 Moore machine State Reduction Row Matching is based on the statetransition table If two states have the same output and both transition to the same next state or both transition to each other or both selfloop then they are equivalent Combine the equivalent states into a new renamed state Repeat until no more states are combined State Transition Table NS output PS x0 x1 I SO SO S1 0 S1 S1 82 1 SZ 82 S1 0 ENGN112 L25 State Reduction and Assignment October 31 2003 FSM Optimization Merge state 32 into SO Eliminate 32 New state machine shows same IIO behavior State Transition Table NS PS I x0 x1 I E SO S1 0 S1 S1 80 1 output ENGN112 L25 State Reduction and Assignment Example Odd parity 1 checken 0 1 1 October 31 2003 1 RowMatchin Exam le um State Transition Table 00 NS output quotU I X H o X H X H o X H b d d f f f f mmmmwom O nhu 31 2m EMGIMHZ L25 Side Rmu lnn mu ASInnmml Row Matchin Exam le NS output PS X4 X4 X4 X4 Reduced State Transition Dia ram a a b 0 0 b c d 0 0 c a d 0 0 00 d e f 0 1 00 00 e a f 0 1 1m f e f 0 1 l NS output 0 PS x0 x1 x0 x1 a a b 0 0 b c d 0 0 c a d 0 0 d e d 0 1 e a d 0 1 mom 112 L25 5m Rmudmn Ind A mmml 0mm M 2m State Reduction 0 The row matching method is not guaranteed to result in the optimal solution in all cases because it only looks at pairs of states For example 0 Another more complicated method guarantees the optimal solution Implication table method See Mano chapter 9 not responsible for chapter 9 material ENGN112 L25 State Reduction and Assignment October 31 2003 Encoding State Variables Option 1 Binary values 000 001 010 011 100 Option 2 Gray code 000 001 011 010 110 Option 3 One hot encoding One bit for every state Only one bit is a one at a given time For a 5state machine 00001 00010 00100 01000 10000 ENGN112 L25 State Reduction and Assignment October 31 2003 State Transition Diagram Solution B IN PS NS OUT ZERO0 01 01 o 1 01 10 o IN1 CHANGEO 10 01 1 1 1o 00 1 ONE0 oo 01 o 1 oo oo o How does this change the combinational logic ENGN112 L25 State Reduction and Assignment October 31 2003 Summary Important to create smallest possible FSMs This course use visual inspection method Often possible to reduce logic and flip flops State encoding is important Onehot coding is popular for flip flop intensive designs ENGIN112 L25 State Reductlon and Asslgnment October312003 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 3 Binary Logic and Boolean Algebra I Binary Codes With n bits we can represent up to 2 objects The scheme for using bits to represent objects is called a binary code For example with n bits and the standard binary code we represent the integers O 1 2 1 Alternatively with a signed 2 scomplement code we represent the integers 2 391 O 2 391 1 Other binary codes for representing integers are sometimes used In particular it is sometimes convenient to directly encode the digits in a decimal number this is called a binary coded decimal BCD representation Since there are 10 decimal digits we need to use 4 bits for each that is 0000 for 0 0001 for 1 0010 for 2 1000 for 8 and 1001 for 9 Note that the six binary patterns 1010 1011 1100 1101 1110 1111 are unused in this code Example The BCD representation for 237410 is 0010 0011 0111 0100 Important this is not the same thing as the binary representation for 237410 because it uses a different code It is possible to do addition directly in BCD the idea is to do binary addition of the codes for each digit If the sum is one of the patterns 0000 1001 we leave the sum as is If it is one of the unused patterns 1010 1111 we add binary6 0110 to the result to generate the correct digit and carry to the next digit Example Do BCD addition ofthe decimal numbers 84 and 57 1 1 8410 1000 0100 5710 0101 0111 14110 1110 1011 0110 0110 0001 0100 0001 Check BCD code for 14110 is 0001 0100 0001 Now suppose that we want a code that can represent text To represent the 10 decimal digits 52 upper and lowercase English letters and various punctuation marks symbols and control characters Need at least 7 bits because there are 27 128 different 7bit sequences The standard way to use bits to represent these characters is the American Standard Code for Information Interchange ASCII system shown in Table 17 in the book An 8th bit called a paritycheck bit is often placed as the leftmost bit of each ASCII symbol this bit is chosen so that the total number of 1 s in the 8bit symbol is even This helps detect any errors in the transmission of ASCII symbols Example The 7bit ASCII codes for H e I p and are as follows 39 1001000 1100101 1101100 1110000 0100001 T39QTQI Using 8bit symbols for even parity what is the ASCII code for Help Ans 39 01001000 01100101 01101100 11110000 00100001 Example What is represented by the eight bits 10010110 if our binary code is i Standard 8bit binary representation Ans 2724 2221 128 164 2 15010 i 8bit signed 2 s complement Ans 28 150 256 150 10610 i 4 bit BCD Ans 1001 0110 9610 i 8 bit ASCII with even parity Ans parity bit 7bit ASCII 0010110 SYN synchronous idle control character II Binary Logic Bits are stored in registers for example by using different voltage levels to represent quot0 and quot1 Binary processing converts some set of bits from input registers into a new bit value that is stored in an output register The processing that converts input bits to an output bit is based on binary logic There are three fundamental binary logic operations AN D OR and NOT The circuits that implement these operations and others that are based on them are called logic gates The action of a logic gate can be described using a truth table that shows what output bit results from each possible combination of input bits AND Let X and y denote input bits and let 2 denote the output bit operation quotX AND y is equal to z is denoted by x39 y z or xy z This operation has truth table X y z Xy O O O O 1 O 1 O O 1 1 1 AND gate symbol 2 X The 0R Let X and y denote input bits and let 2 denote the output bit The operation quotX OR y is equal to z is denoted by Xyz This operation has truth table X V Z X y 0 O 0 Important This is not the O 1 1 same as a binary sum 1 O 1 1 1 1 OR gate symbol 1 NOT Let X denote an input bit and let 2 denote the output bit The operation quotNOTX is equal to z is denoted by X z This operation has truth table x z x 50 X is the complement or O 1 inverse of X 1 O NOT gate symbol also called inverter X X39 More complicated functions are formed by combinations of the basic logic operations Example Say that a patient undergoes three medical tests Tests A B and C The result of each test may be quothighquot or quotlowquot The patient is diagnosed as having condition D if a 39 b a 39 6 Test A is quothighquot and Test B is quothighquot or Test A is quothighquot and Test C is quothigh Or b 39C a Test B is quothighquot and Test C is quothighquot and Test A is quotlow and is diagnosed as not having condition D otherwise Leta b and c be binary values representing the outcomes of Tests A B and C respectively with a 1 denoting Test A is quothighquot and a O denoting Test A is quotlowquot etc Let d be a binary variable denoting the diagnosis with d 1 denoting quotdiagnosed as having condition Dquot Find a logic function logic gate implementation and the truth table for the diagnosis a b Function f1abc a 39b a 39C b 39C 39a d Logic Gate Implementation H J L 3 ID gt U Truth Table abc a39b Q o h 5 o h a39ba39c b 39c 39a 000 O O 001 010 011 100 101 110 111 I I OOOOOO I OI OOOOO I OOOI OOO OOOOI I I I Q I I I OOOO OOOOI OO Now consider a new function f2abc 0 Truth table 39bcb 39cd abc h a 39 bc 5 I h 000 001 010 011 100 101 110 111 I I I OI I I Ol I I I OOOOO I OOOI OOO I l l OI OOOQ But This is exactly the same as the truth table for functioan looking at the input and output columns So f1a bl C f2ab C Logic Gate Implementation for f2abc 41 quot1P 3 This is much simpler than the implementation forf1abc but it does exactly the same thing U In general How do we know how to nd equivalent logic functions and simpli ed implementations By using the principles of Boolean Algebra III Boolean Algebra An algebra just a set of elements and mathematical operations on those elements that satisfy some number of rules or postulates We are interested in twovalued Boolean algebra for which the elements are the two values in the set B 0 1 and the operations are 0 AND and OR along with the complement operator The rules that these operators obey are called the Huntington Postuates There are six postulates listed on p 38 The most important for simplifying logic functions are postulates 2 3 4 and 5 Let X y and 2 denote elements of B that is bits Then 2 XOX X 391X 3 XyyX39X 39yy 39X 4 X 39yz X 39yX 39239Xy 39zXy 39XZ 5 XX 139X 39X O Many other properties can be derived from these postulates some ofthese are given in Sec 24 One important property is Duality it says that any true logical expression remains true if all 0 s and s are interchanged and all 0 s and 1 s are interchanged Example Verify DellIorgan s Laws i X 39y X y ii X y X 39y Verify i by using truth table X y X yy XIyI O O 1 1 So for each possible pair of values for x y we have 0 1 1 1 X39y X y V 10 1 1 1 1 O O To verify ii Just apply duality to i interchange and A term in a logic function is an expression that can be evaluated by one logic gate A literal is a variable inside a term In general we try to implement a function using as few terms and literals as possible since this means reduced system complexity For example we saw previously that f16LbC a 39b a 39C b 39C 39a 7 literals 6 terms is equivalent to f2abc a b cgt1 b 39c 5 literals 4 terms Example Find an ef cient implementation of fxyz X y39X y Z 39 y 5 terms 6 literals by nding an equivalent expression that has only three literals Ans x y 0 x x y 0 x x Post 4 x y 0 1 Post 5 xy Post 2 Similarlyyz y VZ YY W Xyyz Thm4 xyz Thm 1 So fxyz x y V 2 So fxyz x y z using DeMorgan s Law this is also equal to x y z College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 4 Canonical Forms I Logic Gates Binary logic is based on three operations AND OR and NOT We ve discussed the logic gates that implement those operations Three other types of gates are commonly used in design NAND not AND NOR not OR and XOR exclusive OR To describe the operation of these gates let X and y denote input bits and let 2 denote the output bit NAND The operation quotX NAND y is equal to z is denoted by x yz This operation is de ned by x y x 39y and has truth table x y zx y O O 1 NAND gate symbol 0 1 1 1 O 1 X 1 1 O QR NOR The operation quotX NOR y is equal to z is denoted by X yz This operation is de ned by x 4 y x y and has truth table NOR gate symbol x y zxby O O 1 O 1 O 1 O O 1 1 O X D z y XOR The operation quotx XOR y is equal to z is denoted by X eayz This operation is de ned by x y x y y x and has truth table zx 9y XOR gate symbol HHOOX HOHOV OHHO 13D All of these gates can be de ned for more than two inputs X1 1 X2 1 1XN X1 39X2 39 39XN x1 D x2 w XN x1 x2xN x1 EB x2 EB EB XN 1 if the number of 1 s in x1 XN is odd 0 if the number of 1 s in x1 XN is even NAND and NOR gates are especially easy to implement with transistor circuits so through the use of DeMorgan s Laws logic functions are often put in a form that can be computed using NAN D s or NOR s along with inverters Example For the function Fvvltyz WquotX y 392 i Find an implementation that uses only NAND gates and inverters Ans FW X V Z i Find an implementation that uses only NOR gates and inverters Ans FW X y z There are some systematic ways for representing logic functions that are useful for nding different types of implementations Canonical Forms 1 Minterms Suppose we have N bits x1 XN Let s consider all possible AN D s quotproductsquot of these variables or their complements That is m0 X1quotX2quot 39XN1quotXN 69 OOOO m1 X1quotX2quot XN1quotXN 69 0001 m2 X1quotX2quot 39XN1 39XN 69 OO1O mZquot 2 X1 39X2 39 39XN1 39XN 69 111O m2N1 X1 39X2 39 39XN1 39XN 69 1111 Each ofthese patterns is called a minterm Every logic function of xi XN can be expressed by a sum that is OR s of some set of minterms To nd the minterms in a function Draw the truth table Every combination of inputs that gives a 1 as output corresponds to a minterm Example Say we have 4 input variables wxyz Consider the function F w 39x y 392 With 4 variables there are 24 16 minterms m0 wquotxquoty 392 0000 to m15w39x39y 39z 1111 Truth Table I l l I I I l l OOOOOOOOE I l l I OOOOI I I l OOOOX I l OOI I OOI I OOI I OO I Ol OI Ol OI OI OI OI ON HOOOI OOOHOOOI I I H H m0 m1 m2 m3 quot397 So F m0mlm2m3m7mllm15 w X y z w X y zw X yz w x yzw xyzwx yz wxyz We write this in shorthand notation as F Z O12371115 This quotsum of minterms is one canonical form Example Write the function FXyz X y 39 y 2 as a sum of minterms Ans F ZO 137 X y z X y z X yz xyz 2 Maxterms Again suppose we have N bits X1 XN Now let s consider all possible OR s quotsumsquot of these variables or their complements That is llIO X1X2XN1XN 69 M1 X1X2XN1XN 69 I2 X1X2XN1 XN 69 llI2N 2 X139X2 XN139XN 69 llI2N 1 X1 X2 XN1 XN 69 00 00 00 11 11 Each of these patterns is called a maxterm convention for numbering maxterms is the opposite of minterms that is a 1 in the kth position ofthe binary index indicates that we have xk in the minterm and xk in the maxterm OO 01 10 10 11 Note that the Also note By applying DeMorgan s Law we can see that I Mk39mk Example Consider 4bit terms I I I I I I II II I I X1x2x3 x4 I I I I I I II I I I M13 V Now Suppose we have a function F that is written as a sum of minterms The complement of the function F is de ned by F 1whenFO F OwhenF1 Note that this implies that F is equal to a sum of the minterms that are not in F Example Say that FXyz ZO 137 x y z x y z x yz xyz Then F Xyz Z2456 X yz xy z xy z Xyz So F Z minterms not in F which implies that F F Z minterms not in F Z minterms in F But By DeMorgan s Law 2 minterms H minterms where H abc denotes a39b 39c As we ve just seen mk IVIk So we can write F H complements of minterms in F H maxterms in F where maxterm in F means a maxterm with an index whose minterm is not in F So every logic function can be written as a quotproduct of maxterms This is another canonical form Example Say that FXyz ZO 137 x y z x y z x yz xyz Then FXyz H 2456 VIZVI4IVI5M6 Xy zx yzx yz x y z check with x y z Z0137 l39l 2456 truth table 0 o o 1 1 o o 1 1 1 o 1 o o 0 V o 1 1 1 1 1 o o o o 1 o 1 o o 1 1 o o o 1 1 1 1 1 As we ll see Expressing a function in canonical form as a sum of minterms or product of maxterms will be a helpful rst step in developing methods for nding ef cient implementations However the canonical forms are not themselves ef cient for implementation since every term contains every possible literal Better forms for direct implementation are the standard forms of sum of products or product of sums in which each term can have any number of literals In the sum of products form the overall function is written as a sum OR s of terms formed by products AND s In the product of sums form the function is written as a product AND s of terms formed by sums OR s Either type of standard form leads to a twolevel logic gate implementation AND gates followed by an OR gate for sum of products and OR gates followed by an AND gate for product of sums Example Implement the function Fxyz z xyxy in standard forms i Sum of products F zxy xyxy x2 yz xy ii Product of sums F z xzyxy Postuate 4 XZ 39y2 39Xy Finally the standard forms can be converted to twolevel NAND or NOR implementations by applying DeMorgan s Laws Example Implement the function FXyz z xyxy using i Only NAND gates and inverters Use sum of products form F x2 yZXy XZyZXy XZ 39yz 39Xy M2 y39rz My ii Only NOR gates and inverters Use product of sums form F XZ 39yz 39Xy XZ yz Xy N ZNOIWZNMJ WJ Example Find implementations for the function i i FX yz xyyzzxxy As a sum of products Ans Fxyyz As a product of sums Ans F x yz Using only NAND gates and inverters Ans Fx y x z Using only NOR gates and inverters Ans Fx y z ENGIN 112 Intro to Electrical and Computer Engineering Lecture 3 More Number Systems 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L3 Mum Number Systems Sep12mhernznn3 Overview Hexadecimal numbers Related to binary and octal numbers Conversion between hexadecimal octal and binary Value ranges of numbers Representing positive and negative numbers Creating the complement of a number Make a positive number negative and vice versa Why binary ENGN112 L3 More Number Systems September 8 2003 Understanding Binary Numbers Binary numbers are made of binary digits bits 0 and 1 How many items does an binary number represent 10112 1x23 0x221x211x2 1110 What about fractions 110102 1x22 1x210x20 1x21 0x22 Groups of eight bits are called a byte 11oo1oo12 Groups of four bits are called a nibble 1101 2 ENGN112 L3 More Number Systems September 8 2003 Understanding Hexadecimal Numbers Hexadecimal numbers are made of digits 01234567895A B C D E How many items does an hex number represent 3A9F16 3x163 10x162 9x16115x16 1499910 What about fractions 203516 2x162 13x161 3x160 5x16391 72331251o Note that each hexadecimal digit can be represented with four bits 1110 2 E16 Groups of four bits are called a nibble 1110 2 ENGN112 L3 More Number Systems September 8 2003 Putting It All Together DCL imul O 1 Z 5 ENGINHZ L3 More Number Systems mum 0cm Hexadecimal j m pmxumwawmwo o Binar octal anq hexa eCImal sImIIar Easy to build circuits to operate on these representations Possible to convert between the three formats September a zoos Converting Between Base 16 and Base 2 3A9F16 0011 10101001 11112 3 A 9 F Conversion is easy gt Determine 4bit value for each hex digit shite that there are 24 16 different values of four I s Easier to read and write in hexadecimal Representations are equivalent ENGN112 L3 More Number Systems September 8 2003 Converting Between Base 16 and Base 8 3A9F16 0011 10101001 11112 3 A 9 F i 352378 m 1m m w 1112 3 5 2 3 7 Convert from Base 16 to Base 2 Regroup bits into groups of three starting from right Ignore leading zeros PPNT Each group of three bits forms an octal digit ENGN112 L3 More Number Systems September 8 2003 How To Represent Signed Numbers Plus and minus sign used for decimal numbers 25 or 25 16 etc For computers desirable to represent everything as bits Three types of signed binary number representations signed magnitude 1 s complement 2 s complement In each case leftmost bit indicates sign positive 0 or negative 1 Consider signed magnitude 0000110021210 100011002 4210 Sign bit Magnitude Sign bit Magnitude ENGN112 L3 More Number Systems September 8 2003 One s Complement Representation The one s complementof a binary number involves inverting all bits 1 scompof00110011is11001100 1 scompof10101010is01010101 For an n bit number N the 1 s complement is Zn1 N Called diminished radix complement b Mano since 1 s complement for base radix To find negative of 1 s complement number take the 1 s complement 0000110021210 111100112 1210 Sign bit Magnitude Sign bit Magnitude ENGN112 L3 More Number Systems September 8 2003 Two s Complement Representation The two s complementof a binarynumber Involves InvertIng all bIts and addIng 1 2 s comp of 00110011 is 11001101 2 scompof10101010is01010110 For an n bit number N the 2 s complement is 2 4 N 1 Called radix complement by Mano since 2 s complement for base radix 2 To find negative of 2 s complement number take the 2 s complement 0000110021210 111101002 4210 Sign bit Magnitude Sign bit Magnitude ENGN112 L3 More Number Systems September 8 2003 Two s Complement Shortcuts Algorithm 1 Simply complement each bit and then add 1 to the result Finding the 2 s complement of 011001012 and of its 2 s complement N 01100101 N 10011011 10011010 01100100 1 1 10011011 01100101 Algorithm 2 Starting with the least significant bit copy all of the bits up to and including the first 1 bIt and then complementing the remaining bIts N o11oo1o1 N 1oo11o11 ENGN112 L3 More Number Systems September 8 2003 Finite Number Representation Machines that use 2 s complement arithmetic can represent integers in the range 2quot1 lt N lt 2n11 where n is the number of bits available for representin N Note that 2n11 011112 and 2quot1 00002 oFor 2 s complement more negative numbers than posmve oFor 1 s complement two representations for zero oFor an n bit number in base radix 2 there are zn different unsigned values 0 1 1 ENGN112 L3 More Number Systems September 8 2003 1 s Complement Addition Using 1 s complement numbers adding numbers IS easy For example suppose we wish to add 1100 and ooo12 2 Let s compute 1210 110 121o 11002 011002in1 s comp 11o ooo12 000012in 1 s comp Add Step 1 Add binary numbers Step 2 Add carry to loworder bit 0 O l l O l ENGN112 L3 More Number Systems September 8 2003 1 s Complement Subtraction Usin 1 scompement numbers subtracting num ers IS also easy For exam le suppose we wish to subtract 00012 rom 1 002 1 Let s compute 121o 110 1210 11002 011002 in 1 s comp 110 00012 111102in 1 s comp 1 s comp Step 1 Take 1 s complement of 2nd operand Add Step 2 Add binary numbers Step 3 Add carry to low order bit 1 O l O l 0 Add carry 1 Final Result ENGN112 L3 More Number Systems September 8 2003 2 s Complement Addition is easy and 00012 Let s compute 1210 110 121o 11002 011002 in 2 s comp 11o 00012 Step 1 Add binary numbers Step 2 Ignore carry bit ENGN112 L3 More Number Systems 000012 in 2 s comp Add Final Result Using 2 s complement numbers adding numbers For example suppose we wish to add 11002 Ignore September 8 2003 2 s Complement Subtraction Using 2 s complement numbers follow steps for subtraction For exam le suppose we wish to subtract 00012 rom 1 002 1 Let s compute 121o 110 1210 11002 011002 in 2 s comp 110 00012 111112in 2 s comp 2 s comp Step 1 Take 2 s complement of 2nd operand Add Step 2 Add binary numbers Step 3 Ignore carry bit Final Result 1 O l O l l Ignore Carry ENGN112 L3 More Number Systems September 8 2003 2 s Complement Subtraction Example 2 Let s compute 1310 510 131o 11o12 o11o12 51o o1o12 11o112 Adding these two 5bit codes 1 carry l l O l O l O O 0 Discarding the carry bit the si n bit is seen to be zero indicating a correct resul Indeed 010002 10002 810 ENGN112 L3 More Number Systems September 8 2003 2 s Complement Subtraction Example 3 Let s compute 510 12 1210 11002 1o1002 510 o1o12 oo1o12 Adding these two 5bit codes 0 O 1 O 1 11001 Here there is no carry bit and the sign bit is 1 This indicates a negative result which is what we expect 110012 710 ENGN112 L3 More Number Systems September 8 2003 Summary Bina numbers can also be represented in octal and hexa ecumal Easy to convert between binary octal and hexadecimal Signed numbers represented in signed magnitude 1 s complement and 2 s complement 2 s com lement most important only 1 representation for zero Important to understand treatment of sign bit for 1 s and 2 s complement 34 ENGN112 L3 More Number Systems September 8 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 6 More Boolean Algebra Bi 2 ET AB ENGN112 L6 More Boolean Algebra September 15 2003 Overview Expressing Boolean functions Relationshi s between algebraic equations symbols and truth ta les Simplification of Boolean expressions Minterms and Maxterms ANDOR representations Product of sums Sum of products ENGN112 L6 More Boolean Algebra September 15 2003 Boolean Functions Boolean algebra deals with binary variables and logic operations Function results in binary 0 or1 x 2 F o o o o o 01 o X 1 1 1 1 z l gto lz yzv Fxltyz39gt 1 01 o 1 1o 1 1 1 1 1 Fxltyz39gt Euclimz L5 Nhre nnlun upquot swimu152nna Boolean Functions Boolean algebra deals with binary variables and logic operations Function results in binary 0 or1 XZX 0000 0100 x xy 0000 y 0101 Gxyyz 1000 2 z 1100 y 1010 1111 We will learn howto transition between equation symbols and truth table Euclimz L5 Nhre nnlun upquot swimmmnna Representation Conversion 0 ENGN112 L6 More Boolean Algebra Need to transition between boolean expression truth table and circuit symbols Converting between truth table and expression is easy Converting between expression and circuit is easy More difficult to convert to truth table f 39 Truth September 15 2003 Truth Table to Expression Converting a truth table to an expression Each row with output of 1 becomes a product term Sum product terms together Any Boolean Expression can be represented in sum of products form oooogtlt oo oolt O O O ON Adooaooom xyz xyz x yz ENGN112 L6 More Boolean Algebra September 15 2003 Equivalent Representations of Circuits All three formats are equivalent Number of 1 s in truth table outBut column equals AND terms for Sumof Products SO F O O O ON A xoo xooolc G xyz xyz x yz ENGN112 L6 More Boolean Algebra September 15 2003 O ENGN112 L6 More Boolean Algebra Reducing Boolean Expressions Is this the smallest possible implementation of expreSSion G xyz Xyz X yz Use Boolean Algebra rules to reduce complexity while preserving functionality Step 1 Use Theorum 1 a a a o So xyz xyz x yz xyz xyz xyz x yz Step 2 Use distributive rule ab c ab ac So xyz xyz xyz x yz xyz z yzx x Step 3 Use Postulate 3 a a 1 So xyz z yzx x xy1 yz1 Step 4 Use Postulate 2 a 1 a Soxy1 yz1 xy yz xyz xyz x yz September 15 2003 Reduced Hardware Implementation Reduced equation requires less hardware Same function implemented YX 2 0000 0010 i 0100 lgt gtG 0111 1000 1010 I 1101 1111 x y z Gxyzxyz x yzxyyz ENGN112 L6 More Boolean Algebra September 15 2003 Minterms and Maxterms Each variable in a Boolean expression is a literal Boolean variables can appear in normal x or complement form x Each AND combination of terms is a minterm Each OR combination of terms is a maxterm For example For example Minterms Maxterms x y z Minterm x y z Maxterm O O O xyz m0 0 O O XyZ M0 0 O 1 xyz m1 0 O 1 Xyz M1 1 o o xy z m4 391quot o o x yz M4 1 1 1 xyz m7 1 1 1 x y Z M7 ENGN112 L6 More Boolean Algebra September 15 2003 Representing Functions with Minterms Minterm number same as row position in truth table starting from top from 0 Shorthand way to represent functions F ON G xyz xyz x yz Gm7m6 m3 23 6 7 oooo oo oo A xoo xooolc ENGN112 L6 More Boolean Algebra September 15 2003 Complementing Functions Minterm number same as row position in truth table starting from top from 0 Shorthand way to represent functions x y z G G 0 00 01 Gxzxz x z o o 1 o 1 y y y 0 1 0 0 1 0 1 1 1 0 G xyz xyz x yz 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 Can we findasimpler representation 1 1 1 1 0 ENGN112 L6 More Boolean Algebra September 15 2003 Complementing Functions Step 1 assign temporary names bCgtZ Gabc az G G abc Step 2 Use DeMorgans Law az a z Step 3 Resubstitute bc for z a z a bc Step 4 Use DeMorgans Law G a b C 3 b C a b C G a b c a b c Step 5 Associative rule a b c a b c ENGN112 L6 More Boolean Algebra September 15 2003 Complementation Example Find complement of F x z yz F x z yz DeMorgan s F x z yz DeMorgan s F xZyZ Reduction gt eliminate double negation on x F xz y z This format is called product of sums ENGN112 L6 More Boolean Algebra September 15 2003 Conversion Between Canonical Forms Easy to convert between minterm and maxterm representations For maxterm representation select rows with 0 s y 0 2 OG G xyz xyz X yz 0 0 1 0 lt l 0 1 0 0 lt 0 1 1 1 Gm7m6m32367 1 0 0 0 4 1 0 1 0 1 1 0 1 G M0M1M2M4M5 l39l01245 1 1 1 1 G XyZXyZ XY ZX yZX yZ ENGN112 L6 More Boolean Algebra September 15 2003 Representation of Circuits 0 All lo ic expressions can be represented in 2 level orma Circuits can be reduced to minimal 2level representation Sum of products representation most common in Industry y x x y y F1 F 2 Z z x x y 3 y z 21 Sum of Products b Product of Sums Fig 2 3 TWO level implementation ENGN112 L6 More Boolean Algebra September 15 2003 Summary Truth table circuit and boolean expression formats are equwalent Easy to translate truth table to SOP and POS representation Booean algebra rules can be used to reduce circuit Size while maIntaInIng function girogic functions can be made from AND OR and Easiest way to understand Do examples Next time More logic gates ENGN112 L6 More Boolean Algebra September 15 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 21 Analyzing Sequential Circuits 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z LZ1AnzIyzing Sequenliz Eu 5 omnherzunna Overview Understanding flip flop state Stored values inside flip flops Clocked sequential circuits Contain flip flops Representations of state State equations State table State diagram Finite state machines Mealy machine Moore machine ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Flip Flop State Behavipr of clocked sequential circuit can be determined from Inputs outputs and FF state Clk W XtQ1tQot Qot1 Dot XtQ1t Q1t1 D1t Xt Qot ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Output and State Equations Next state dependent on previous state Clk Output equation 3 1Xt813Q0t2tQ t 39 0 0 X 1 State equations lt Q1t1 D1t Xt Q0t ENGN112 L21 Analyzing Sequential Circuits October 22 2003 State Table Sequence of out uts in uts and flip flop states enumerated in s ate tab e Present state indicates current value of flip flops Next state indicates state after next rising clock edge Output is output value on current clock edge Present Next State Output State X20 X21 x20 x1 0 0 00 10 0 0 State Table 0 1 10 10 0 0 1 0 00 11 0 0 1 1 10 1 1 0 1 Q1 Q0 ENGN112 L21 Analyzing Sequential Circuits Q1t1 Q0t1 October 22 2003 State Table 0 0 Next State x0 x1 All possible input combinations enumerated All possible state combinations enumerated Separate columns for each output value Sometimes easier to designate a symbol for each Output x0 x1 state Present State Let s0 00 s0 S1 01 s1 82 32 S3 11 S3 ENGN112 L21 Analyzing Sequential Circuits S0 S2 S0 S2 S2 S2 S3 S3 0 0 0 0 0 H00 October 22 2003 State Diagram Circles indicate current state Arrows point to next state For xy x is input and y is output Present Next State Output State x0 x1 x0 x1 0 0 00 10 0 0 0 l l 0 10 0 0 l 0 00 ll 0 0 l 1 10 l l 0 1 ENGN112 L21 Analyzing Sequential Circuits October 22 2003 State Diagram 0 Each state has two arrows leaving Oneforx0and oneforx1 0 Unlimited arrows can enter a state 0 Note use of state names in this example Easier to identify ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Flip Flop Input Equations 0 Boolean expressions which indicate the input to the flip flops Clk DQO XQ1 DQl X Qo Format implies type of flop used ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Analysis with D FlipFlops Identify flip flop input equations 0 Identify output equation Present Next state Inputs state A x y A 0 O O 0 x D A 0 O 1 1 y 0 1 0 1 0 1 1 0 gtC 1 0 0 1 1 O 1 0 1 1 0 0 CLK 1 1 1 1 a Circuit diagram b State table 0011 0110 0011 0110 Note this example c State diagram has no output Fig 5 17 Sequential Circuit with D Flip Flop ENGIN112 L21 Analyzing Sequential ircuits UCIODer zz zuua Mealy Machine Output based on state and present input Qt 1 Qt X p535 Y present input L r ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Moore Machine Output based on state only Qt1 my Yt Xt present input clk ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Mealv versus Moore Mealy Model Inputs Input gt Output Outputs Logic Logic Combina Memory Combina tional gt Element tional Moore Model Inputs gt Input Output Outputs Logic Logic Combina MemOIy Combina tional gt Element tional ENGN112 L21 Analyzing Sequential Circuits October 22 2003 State Diagram with One Input amp One Mealy Output O Mano text focuses on Mealy machines 0 State transitions are shown as a function of inputs and current outputs e g 1 O InputsOutputs shown 0 Iquot 1n transmon 11 K lt 00 A DOO ENGN112 L21 Analyzing Sequential Circuits October 22 2003 State Diagram with One Input amp a Moore Output Moore machine outputs only depend on the current state Outputs cannot change during a clock pulse if the input variables change Moore Machines usually have more states No direct path from inputs to outputs Can be more reliable ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Clocked Synchronous Statemachine Analysis next class Given the circuit diagram of a state machine 1 Analyze the combinational logic to determine flipflop input excitation equations Di Fi Q inputs The input to each flipflop is based upon current state and circuit inputs 2 Substitute excitation equations into flipflop characteristic equations giving transition equations Qit1 Hi Di 3 From the circuit find output equations Z G Q inputs The outputs are based upon the current state and possibly the inputs 4 Construct a state transitionoutput table from the transition and output equations Similar to truth table Present state on the left side Outputs and next state for each input value on the right side Provide meaningful names for the states in state table if possible 5 Draw the state diagram which is the graphical representation of state table ENGN112 L21 Analyzing Sequential Circuits October 22 2003 Summary Flip flops contain state information State can be represented in several forms State equations State table State diagram Possible to convert between these forms Circuits with state can take on a finite set of values Finite state machine Two types of machines Mealy machine Moore machine ENGN112 L21 Analyzing Sequential Circuits October 22 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 1 7 Encoders and Decoders 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z L17 Encndels and Decade39s 0dnher1 2 3 Overview Binary decoders Converts an nbit code to a single active output Can be developed using ANDOR gates Can be used to implement logic circuits Binary encoders Converts one of 2quot inputs to an nbit output Useful for compressing data Can be developed using ANDOR gates Both encoders and decoders are extensively used in digital systems ENGN112 L17 Encoders and Decoders October 10 2003 Binary Decoder Black box with n input lines and 2n output lines Only one output is a 1 for any given input quot Binary 2quot outputs 39quotpUts Decoder ENGN112 L17 Encoders and Decoders October 10 2003 2to4 Binary Decoder Truth Table From truth table circuit for F XY39 2x4 decoder is HD 2 Note Each output is a 2 variable minterm X39Y39 X39Y D F3 XY XY39 or XY x lD lt lgt F0 X 2t04 F1 Y Decoder F2 F3 ENGN112 L17 Encoders and Decoders October 10 2003 3to8 Binary Decoder lelzl 0 F F1 x39y39z F2 x39yz39 F3 x39yz F4 xy39z39 F5 xy39z F6 xyz39 F7 xyz Truth Table 1 x y le0 F1 F2 F3 F4 Flt F6 F7 0 000 0 000 0 0 0 1 0 1 0 0 0000 0 1 0 1 0 000 0 0 0 0 F0 F1 F2 F3 F4 F5 F6 F7 3t08 Decoder Y z 0ctober10 2003 ENGN112 L17 Encoders and Decoders Implementing Functions Using Decoders Any nvariable logic function can be implemented using a smgle nto2quot decoder to generate the minterms OR gate forms the sum The output lines of the decoder corresponding to the minterms of the function are used as inputs to the or gate Any combinational circuit with n inrputs and m outputs ca be implemented with an nto2 decoder with m OR ga es Suitable when a circuit has man outputs and each output function is expressed wi h few minterms ENGN112 L17 Encoders and Decoders October 10 2003 Implementing Functions Using Decoders Example Full adder Sx y z 2 MM Cx y z 2 3563 r H H H OOOOVG r H OOr H OO lt Hor OHOr ON 3to8 Decoder 1 ENGN112 L17 Encoders and Decoders October 10 2003 r r r Or OOOO Hoooom Standard MSI Binary Decoders Example 74138 3to8 decoder a a Logic circuit b Package pin configuration c Function table ENGN112 L17 Encoders and Decoders VCC Dara outputs A Y Ell Ing Y3 Y4 mm Y0 Y1 Y3 Y4 B C 02A 028 01 1 77 1 2 a m m Lil m m A B C El 671 or Y7 GND k V J 39 Output Sclch Enable b Inputs Outputs Enable Select 0165 c B A re 1 Y2 r3 r4 5 re 7 H L L L L L H H H H H H H H L L L H H L H H H H H H H L L H L H H L H H H H H H L L H H H H H L H H H H H L H L L H H H H L H H H H L H L H H H H H H L H H H L H H L H H H H H H L H H L H H H H H H H H H H L x H x x x H H H H H H H H L x x x x H H H H H H H H 335 623 c October 10 2003 Building a Binary Decoder with NAND Gates Start with a 2bit decoder Add an enable signal E NOte use Of NANDS only one 0 active B D0 D1 D2 D3 X 1 1 1 1 0 O 1 1 1 1 1 0 1 1 O 1 1 O 1 1 1 1 1 0 a Logic diagram b Truth table Fig 4 19 2 t04 Line Decoder with Enable Input ENGN112 L17 Encoders and Decoders October 10 2003 Use two 3 to 8 decoders to make 4 to 16 decoder Enable can also be active high In this example only one decoder can be active at a tIme x y z effectively select output line for w x 3 X 8 decoder E y Z D0 to D7 3 X 8 decoder E D8 tOD15 Fig 4 20 4 X 16 Decoder Constructed with Two 3 X 8 Decoders ENGN112 L17 Encoders and Decoders October 10 2003 Encoders If the a decoder39s output code has fewer bits than the input code the device is usually called an encoder eg 2nton The simplest encoder is a 2quotton binary encoder One of 2quot inputs 1 Output is an nbit binary number Emmi 2n n inputs outputs ENGN112 L17 Encoders and Decoders October 10 2003 8to3 Binary Encoder At any one time only one input line has a value of 1 ENGN112 L17 Encoders and Decoders Inputs Outputs I 11121314151617 372371370 1 O O O O O O O 0 0 0 O 1 O O O O O O 0 0 1 O O 1 O O O O O 0 1 0 O O O 1 O O O O 0 1 1 O O O O 1 O O O 1 0 0 O O O O O 1 O O 1 O 1 O O O O O O 1 O 1 1 O O O O O O O O 1 1 1 1 hhkkh hbhkh MLBEL October 10 2003 8to3 Priority Encoder o What if more than one input line has a value of 1 o Ignore lower priorityquot inputs Idle indicates that no input is a 1 0 Note that polarity of Idle is opposite from Table 48 in Mano Inputs Outputs 1011121314151617 yzylyoldle O O O O O O O O X XX 1 1 O O O O O O O O O 0 O X 1 O O O O O O O O 1 O X X 1 O O O O O O 1 O O X X X 1 O O O O O 1 1 O X X X X 1 O O O 1 O O O X X X X X 1 O O 1 O 1 O X X X X X X 1 O 1 1 O O X X X X X X X 1 1 1 1 O ENGN112 L17 Encoders and Decoders October 10 2003 Priority Encoder 8 to 3 encoder Assign priorities to the inputs When more than one in ut are asserted the output generates the code of the input with t e highest priority Prioritly Encoder H7 Highest Priority H667 H5I5I6 I7 Priority encoder H445 6 7 Priority Circuit Binary encoder 13131111211211 H11 2345l6 7 10 10 H0 10 H001 2 3 4 5 6 7 11 11 H1 11 DLE 0 1 2 3 4 5 6 7 12 12 H2 12 YO Y0 Encoder 13 13 H3 13 Y1 Y1 Y01357 Y1 12 13 l6 I 14 14 H4 14 Y2 Y2 Y24567 15 15 H5 15 I6 16 H6 16 17 17 H7 17 IDLE IDLE ENGN112 L17 Encoders and Decoders October 10 2003 Encoder Application Monitoring Unit Encoder identifies the requester and encodes the value Controller accepts digital inputs Contoller Response Machine 1 Action Machine 2 Machine Code Machine 11 ENGN112 L17 Encoders and Decoders October 10 2003 Summary Decoderallowsfor generation of a single binary output from an Input binary code For an ninput binary decoder there are 2n outputs Decoders are widely used in storage devices eg memories We will discuss these in a few weeks Encoders all for data compression Priority encoders rank inputs and encode the highest priority input Next time storage elements ENGN112 L17 Encoders and Decoders October 10 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 1 9 Sequential Circuits Latches 39 ELECTRICAL wquot ENGIN11Z L19 Sequential 0dnher172 3 Overview Circuits require memory to store intermediate data Sequential circuits use a periodic signal to determine when to store values A clock signal can determine storage times Clock signals are periodic Single bit storage element is a flip flop A basic type of flip flop is a latch Latches are made from logic gates NAND NOR AND OR Inverter ENGN112 L19 Sequential Circuits Latches October 17 2003 The story so far Logical operations which respond to combinations of inputs to produce an output Call these combinational logic circuits For example can add two numbers But No way of adding two numbers then adding a third a sequential operation No way of remembering or storing information after inputs have been removed To handle this we need sequential logic capable of storing intermediate and final results ENGN112 L19 Sequential Circuits Latches October 17 2003 Seguential Circuits Inpms Combinational OUtPUtS circuit Next State Present state Timing signal clock Clock a iii sii y m xi n synchronizes when current state changes happen keeps system wellbehaved makes it easier to design and build large systems ENGN112 L19 Sequential Circuits Latches October 17 2003 Crosscoupled Inverters O A stable value can be stored at inverter outputs State 1 State 2 ENGN112 L19 Sequential Circuits Latches October 17 2003 SR Latch with NORs Rreset 39Q S R Q Q l l 0 0 Unde ned l O 1 0 Set a 0 1 0 1 Reset Sset 5 S 39 0 0 2 5 Stable SR latch made from crosscoupled NORs If Q 1 set state If Q 0 reset state Usually S0 and R0 S1 and R1 generates unpredictable results ENGN112 L19 Sequential Circuits Latches October 17 2003 SR Latch With NANDs S Q S R Q 0 O 1 1 Disallowed O l 1 0 Set Q1 1 0 0 1 Reset R l l E 6 Store 0 Latch made from crosscoupled NANDs Sometimes called S R latch Usually S1 and R1 o S0 and R0 generates unpredictable results ENGIN11Z L19 Sequential Circulls Latches 0dnher172 3 SR Latches R Reset Q 6 5591 6 Logic diagram S Set Q 6 R Reset a Logic diagram ENGN112 L19 Sequential circuits Latches s R Q 6 1 0 1 0 Selstate 0 0 1 0 O 1 0 1 O 0 0 1 Reselstate 1 1 0 0 Undefined 1 Function table s R Q 6 O 1 1 0 Setstme 1 1 1 0 1 0 0 1 1 1 0 1 Resetstaie 0 0 1 1 Undefined b Function table October 17 2003 SR Latch with control input Next state of Q No change No change Q 0 Reset state Q 1 set state Indeterminate chox En HOHOX be G HHHi OQ a Logic diagram b Function table Fig 5 5 SR Latch with Control Input Occasionally desirable to avoid latch changes C 0 disables aquot latch state changes Control signal enables data change when C 1 Right side of circuit same as ordinary SR latch ENGN112 L19 Sequential Circuits Latches 06t0b6r17 2003 NOR SR Latch with Control Input Latch is levelsensitive in regards to C Only stores data if C 0 R Latch peat t urtpu mange Wham C 7 11 Qitihixwrw a HOLE ENGN112 L19 Sequential Circuits Latches October 17 2003 D Latch Q0 indicates the previous state the previously stored value D S Store Reset Set Disallowed QO Store ENGIN11Z L19 Sequential Circuils Latches 0dnher172 3 D Latch D X S Q Q Y R D C Q Q 0 l 0 l l l l 0 X 0 Q0 Q0 Input value D is passed to output Q when C is high Input value D is ignored when C is low ENGIN11Z L19 Sequential Circuils Latches 0dnher172 3 D Latch Latches on following edge of clock Z only changes when E is high If E is high Z will follow X ENGN112 L19 Sequential Circuits Latches October 17 2003 D Latch Latches on following edge of clock The D latch stores data indefinitely regardless of input D values if C 0 Forms basic storage element in computers ENGN112 L19 Sequential Circuits Latches October 17 2003 Symbols for Latches SR ER D Fig 5 7 Graphic Symbols for Latches SR latch is based on NOR gates S R latch based on NAND gates O D latch can be based on either 0 D latch sometimes called transparent latch ENGN112 L19 Sequential Circuits Latches October 17 2003 Summary Latches are based on combinational gates eg NAND NOR Latches store data even after data input has been removed SR latches operate like crosscoupled inverters with control inputs S set R reset With additional gates an SR latch can be converted to a D latch D stands for data D latch is simple to understand conceptually When C 1 data input D stored in latch and output as Q When C 0 data input D ignored and previous latch value output at Q Next time more storage elements ENGN112 L19 Sequential Circuits Latches October 17 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 1 Course Overview Russell Tessier KEB 309 G tessierecsumassedu ENGN112 L1 Overview September 3 2003 Welcome Engineering Designing building and testing systems Fastmoving practical This semester computers Learn how computers represent information How computers perform computations Understand how hardware and software work together Impress your friends and family ENGN112 L1 Overview September 3 2003 Electrical and Computer Engineering Computer Engineering Hardware system design Software design and development Electrical Engineering Communications Power and electromagnetic systems 5 iconductor devices and circuits Why do you want to be an engineer Euclimz L10vuvew swlamu a 2m En ineers in P0 ular Culture Doc Brown Flux Cagacitor Dr Myles Dyson Sk Dr Spock Time warg other stuff ENGIN112 L1 Overvlew September32003 Administration Teaching assistants Web site wwwecsumasseduleceengin112 Lecture and lecture slides Available the day before lecture Print out and bring to class TA office hours TBA Discussion sections ENGN112 L1 Overview September 3 2003 Homework and Projects Due before class every Wednesday Put in box at back of lecture hall Handin policy No exceptions Easiest way to get a good grade in ENGIN112 Come to class and do the homework Four computer projects Attendance is required LOG INTO YOUR COMPUTER ACCOUNT TODAY ENGIN112 L1 Overview September 3 2003 Course Grading and Coming Attractions Two exams 25 each Final 30 Homework 10 Projects 10 Next Time Binary Number Systems Coming Attractions J Logic gates J Data storage J Processors J Data transmission ENGN112 L1 Overview September 3 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 14 Binary Adders and Subtractors 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN1 12 L16 Binary Adder Suhlrzdnr O nher 3 znna Overview Addition and subtraction of binary data is fundamental Need to determine hardware implementation Represent inputs and outputs Inputs single bit values carry in Outputs Sum Carry Hardware features Create a singlebit adder and chain together Same hardware can be used for addition and subtraction with minor changes Dealing with overflow What happens if numbers are too big ENGN112 L14 Binary Adder Subtractor October 3 2003 Half Adder Add two binary numbers A0 B0 gt single bit inputs SD gt single bit sum C1 gt carry out C1 ENGN1 12 L16 Binary Adder Suhlrz nr O nher 3 znna Multiplebit Addition Consider singlebit adder for each bit position A3 A2 A1A0 33 32 B130 A0101 130111 111 Ci1Ci A0101 Ai B0111 1100 Si Each bit position creates a sum and carry ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder O O Ci Ai Bi Si Ci1 O O O O O O O l l O O l O l O O l l O l l O O l O l O l O l l l O O l l l l l l ENGN112 L14 Binary Adder Subtractor Full adder includes carry in Ci Notice interesting pattern in Karnaugh map A1131 Ci 00 01 11 10 o 1 1 1 1 October 3 2003 Full Adder 0 Full adder includes carry in Ci Alternative to XOR implementation Ci Ai Bi Si Ci1 Si Ci amp lAi amp Bi 00000 iiCiampAiampBi 001 1 0 CiampAiampBi 010 1 0 CiampAiampBi 011 O 1 100 1 O 101 O 1 110 O 1 111 1 1 ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder Reduce andor representations into XORs Ci amp lAi amp Bi Ci amp Ai amp 113i ci amp lAi amp 113i 2 amp Ai amp Bi 1 S l HHH S Ci amp Ai zs tBianAi amp Bi C amp lAi amp BiAi amp Bi 1 s Bi 2 amp Ai Bi 3 0 9w CD H ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder Now consider implementation of carry out Two outputs per full adder bit CH1 Si ENGN112 L14 Binary Adder Subtractor Ci Ai Bi Si Ci1 O O O O O O O l l O O l O l O O l l O l l O O l O l O l O l l l O O l l l l l l A1131 Ci 00 01 11 10 o 1 1 1 1 1 Cm Note 3 inputs October 3 2003 Full Adder O O ENGN112 L14 Binary Adder Subtractor CiAiBiSiCi1 00000 00110 01010 01101 10010 10101 11001 11111 Ci 0 1 Now consider implementation of carry out Minimize circuit for carry out Ci1 13i A1 00 01 11 10 October 3 2003 Full Adder C AampB 11 1 l Ci Ai amp Bi Ci amp Ai amp Bi Cil A1 5 Bi Ciamp lAiampBiAiamp Bi 3 c Ai Bi i l A ampBiCiamp AiBi l O l ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder Full adder made of several half adders Si 2 Ci Ai Bi Ci1 Ai amp Bi Ci amp Ai Bi Ci Ai r Tgti si Bi IL L 1 D WDCM Halfadder Halfadder ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder Hardware repetition simplifies hardware design halfadder A i S C halfadder C B i C D7 391 A full adder can be made from two half adders plus an OR gate ENGN112 L14 Binary Adder Subtractor October 3 2003 Full Adder 0 Putting it all together Singlebit full adder Common piece of computer hardware Ai Bi H Ci14 Full Adder 4 Ci t s Block Diagram ENGN112 L14 Binary Adder Subtractor October 3 2003 4Bit Adder Chain singlebit adders together What does this do to delay A B A2 32 A1 B1 A0 BO W H H H Full Adder A Full Adder Full Adder Full Adder lt 0 t t t t c4 s3 32 81 so mwgt0 l OQH 39 OI ol OI HO ENGN112 L14 Binary Adder Subtractor October 3 2003 Negative Numbers 2 s Complement O Subtracting a number is the same as 1 Perform 2 s complement 2 Perform addition If we can augment adder with 2 s complement hardware 1N 01M 00000001 1m FFM 11111111 128m 80M 10000000 128m 80M 10000000 ENGN112 L14 Binary Adder Subtractor October 3 2003 4bit Subtractor E 1 A3 B3 A2 82 A1 B1 A0 B0 V V V Full Adder Fun Adder Full Adder FullAdder I C3 C2 C1 C4 SD3 SD2 SD1 SDo Add A to B one s complement plus 1 That is add A to two s complement of B DA ENGN112 L14 Binary Adder Subtractor October 3 2003 Adder Subtractor Circuit E3 5 3 BE A2 B1 A1 30 An S 3 22 31 FA FA FA FA Ca Ca 33 32 8391 ENGN112 L14 Binary Adder Subtractor October 3 2003 Overflow in two s complement addition Definition When two values of the same signs are added Result won t fit in the number of bits provided Result has the opposite sign ANl BN1 DOverflow CN1 Assumes an Nbit adder with bit Nl the M83 ENGN112 L14 Binary Adder Subtractor October 3 2003 Addition cases and overflow 00 01 0010 0011 0011 0110 0101 1001 2 3 3 6 5 7 DFL 10 00 11 1110 1101 0010 21110 1101 1010 1100 0100 1011 0111 1110 0010 2 3 2 2 3 6 4 4 5 7 2 2 DFL OOOOOOOOOOO 03 Summary Addition and subtraction are fundamental to computer systems Key create a single bit addersubtractor Chain the singlebit hardware together to create bigger designs The approach is call ripplecarry addition Can be slow for large designs Overflow is an important issue for computers Processors often have hardware to detect overflow Next time encodersdecoder ENGN112 L14 Binary Adder Subtractor October 3 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 7 More Logic Functions NAND NOR XOR 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L7 Mum Lngic Fundinns Septemh2r172 3 Overview More 2input logic gates NAND NOR XOR Extensions to 3input gates Converting between sumofproducts and NANDs SOP to NANDs NANDs to SOP Converting between sumofproducts and NORs SOP to NORs NORs to SOP Positive and negative logic We use primarily positive logic in this course ENGN112 L7 More Logic Functions September 17 2003 Logic functions of N variables Each truth table represents one possible function eg AND OR N If there are N inputs there are 22 For example is N is 2 then there are 16 possible truth tables So far we have defined 2 of these functions 14 more are possible Why consider new functions Cheaper hardware more flexibility ENGN112 L7 More Logic Functions September 17 2003 The NAND Gate A lY B quot I This is a NAND gate It is a combination of an AND gate followed by an inverter Its truth table shows this NAND gates have several interesting properties NANDaaaa a NOTa NAND abab ab ANDab NANDa b a b ab ORab ENGN112 L7 More Logic Functions September 17 The NAND Gate These three properties show that a NAND gate with both foitrs in uts driven by the same signal is equivalent to a ga e A NAND gate whose out ut is com lemented is equivalent to an AND ga e and a AND gate with complemented inputs acts as an OR gate Therefore we can use a NAND ate to implement all three of the elementary operators A DORNO Therefore ANY switching function can be constructed using only NAND gates Such a gate is said to be primitive or functionally complete ENGN112 L7 More Logic Functions September 17 2003 NAND Gates into Other Gates what are these circuits Aiv Y NOT Gate A h H D Y A I AND Gate B 1 OR Gate ENGN112 L7 More Logic Functions September 17 2003 Y Q 39 T The NOR Gate 2 Jgt Y This is a NOR ate It is a combination of an OR gate followed y an inverter lt s truth table shows this NOR gates also have several interesting properties NORaaaa a NOTa NOR abab ab ORab NORa b a b ab ANDab ENGN112 L7 More Logic Functions September 17 Functionally Complete Gates Just like the NAND gate the NOR gate is functionally comple ean logic function can be implemented using just N R gates Both NAND and NOR ates are very valuable as any design can be rea ized using either one It is easier to build an IC chip usin all NAND or NOtR gates than to combine AND R and NOT ga es NANDNOR gates are typically faster at switching and cheaper to produce ENGN112 L7 More Logic Functions September 17 2003 NOR Gates into Other Gates what are these circuits A ED Y NOT Gate A x B 0 A OR Gate Y AND Gate ENGN112 L7 More Logic Functions September 17 2003 The XOR Gate ExclusiveOR jD Y This is a XOR gate XOR gates assert their output when exactly one of the inputs is asserted hence the name The switching algebra symbol for this operation is 6 Le 1 10and1 01 ENGN112 L7 More Logic Functions September 17 2003 The XNOR Gate A a B ZED Y This is a XNOR gate This functions as an exclusiveNOR gate or simply the complement of the XOR gate The switching algebra symbol for this operation is 6 Le 11and1 00 ENGN112 L7 More Logic Functions September 17 2003 NOR Gate Equivalence NOR Symbol Equivalent Circuit Truth Table ENGIN11Z L7 Mum Lngic Fundinns Septemh2r172 3 DeMorgan s Theorem A key theorem in simplifyinlgLBoolean al ebra expression is DeMorgan s eorem It s ates a b a b ab a b Complement the expression ab zx a and simplify abzX a a b zx a a b zX a a b z X a a b9Z9 X a a b z X a ENGN112 L7 More Logic Functions September 17 2003 Example Determine the outgmt expression for the below circuit and simpli y it usmg DeMorgan s Theorem ENGIN11Z L7 Mum Lngic Fundinns Septemh2r172 3 Universality of NAND and NOR gates A x iAK m D I Ao gtO l 6 quotWE STE ENGN112 L7 More Logic Functions September172003 Universality of NOR gate Euivalent representations of the AND OR and N Tgates ENGiNiiZ Li More Logic Functions September 112003 Example xAB4CD Anev enmmanng uoums mversmns 74LSGO ct ENGINHZ L7 More Logic Functions September 17 2003 Interpretation of the two NAND gate symbols A B activerHiGH A B activeLOW AB Output goes LOW only when ail inputs are HiGH LDW slate Is the active state a 7 E E Out Lit is HIGH when any input is LOW HIGH slate IS the active state 3 Determine the output expression for circuit via DeMorgan s Theorem ENGiNitZ Li More Logic Functions September 112003 Interpretation of the two OR gate symbols A A B Output goes HIGH when E any input is HIGH HiGH state is adivamGH active state a A EVE A B Output goes LOW orl B when all inputs are LOW LOW state is actiV5LoW active state b Determine the output expression for circuit via DeMorgan s Theorem EilGIiliiZ L1 More Lngit Functions Septeniterii ZliliCi Summary Basic logic functions can be made from NAND and NOR functions The behavior of digital circuits can be represented with waveforms truth tables or symbols Primitive gates can be combined to form larger circuits Boolean algebra defines how binary variables with NAND NO can be combined DeMorgan s rules are important Allow conversion to NANDNOR representations ENGN112 L7 More Logic Functions September 17 2003 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 11 FSM Examples Example 1 Say that a sequence of bits arrives at some node Develop a circuit that outputs a 1 if the number of 1 s that have arrived up to the current time is even and outputs a 0 if the number is odd 1 How many states Set two states 80 to mean number of 1 s is even S7 to mean number of 1 s is odd 2 Draw state table and state diagram as a Mealy model Recall key point In a Mealy model outputs are sampled immediately before clock edge Current Current Next State Current State Input X Output y So 0 So 1 So 1 S1 0 S1 0 S1 0 S1 1 So 1 3 Assign code to represent states and draw Meay model implementation Let 0 represent 80 and 1 represent 8 A D X clock gt CLK O X7 4 Now draw state table state diagram and implementation as a Moore Model Recall For a Moore model outputs are synchronized with clock edges 80 the input does not change the output until the next clock edge Current Current Next State Current State Input X Output y 80 0 So 1 So 1 S1 1 S1 0 S1 0 S1 1 So 0 State diagram Implementation clock gt CLK O y Example 2 Design a circuit that counts the number of 1 s in arriving bits and resets to O on every fourth 1 Use a Moore model Define states 800 811 822 833 Encode the states with 2 bits A B so SO is encoded by A0 B0 S7 is encoded by A0 B1 etc State table Current Next State Next State Output State x0 x1 OO 00 01 OO 01 O1 10 O1 1O 1O 11 1O 11 11 OO 11 State diagram O To design circuit Draw Karnaugh maps for the next states Az 1 and Bz 1 Az 1AB X AXA B DA Map forAt 1 X AB 00 O1 11 1O 0 1 1 1 1 I Bz 1X B XB DB Map for Bt1 gt D rgt CLK O l A D L clock gt CLK Example 3 Suppose that we again want to keep a count the number of 1 s that have arrived but now we want to count up to 1023 before resetting to 0 How many states how many ipflops We have 1024 states we index these with flipflop output bits so we need ten flipflops How many rows in the state table 1024 states one current input bit so we have 2048 rows in the state table and enormous Karnaugh maps Can you think of an alternative approach using modular design Consider using full adders recall that a onebit full adder sums two input bits and a carry bit to form a sum bit and an output carry and that we can string together n full adders to make an nbit adder We want the sum bits to represent the current count of 1 s so the sum bits should be stored on flipflops When a new 1 arrives it should be summed with the stored previous sum We have 1024 states denote them 0 1 2 1023 These are encoded by strings of 10 bits state 0 is encoded as 0000000000 state 1 as 0000000001 state 1023 as 1111111111 State diagram implemented as Moore machine 0 0 o 1 1 Note Outputs are also encoded with ten bits just like the states ENGIN 112 Intro to Electrical and Computer Engineering Lecture 4 Number Codes and Registers 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z U Number Cndes and Reg39slels Overview 2 s complement numbers Addition and subtraction Binary coded decimal Gray codes for binary numbers ASCII characters Moving towards hardware Storing data Processing data ENGN112 L4 Number Codes and Registers 2 s Complement Subtraction Let s compute 1310 510 131o 11o12 o11o12 51o o1o12 11o112 Adding these two 5bit codes 1 carry l l O 1 Discarding the carry bit the si n bit is seen to be zero indicating a correct resu Numbers in hexadecimal ENGN112 L4 Number Codes and Registers 2 s Complement Subtraction Let s compute 510 12 1210 11002 1o1002 510 o1o12 oo1o12 Adding these two 5bit codes 11001 Here there is no carry bit and the sign bit is 1 This indicates a negative result which is what we expect 110012 710 Numbers in hexadecimal ENGN112 L4 Number Codes and Registers Binary Coded Decimal Db BCD Db BCD Code Code 0 0000 5 0101 1 0001 6 0110 2 0010 7 0111 3 0011 8 1000 4 0100 9 1001 Binary coded decimal BCD represents each decimal digit with four bits Ex 001100101001 32910 3 2 9 This is NOTthe same as 0011001010012 Why do this Because people think in decimal ENGN112 L4 Number Codes and Registers Putting It All Together Dccimul Binary Octal 0 O 0 1 1 1 2 10 Z 3 11 3 4 100 1 5 101 3 0 110 6 7 111 7 8 1000 10 9 1001 11 10 1010 I 11 1011 13 12 391 100 1 I H 1101 15 1 1110 16 15 1111 17 ENGN112 LA Number Codes and Registers Hexadecimal QwAwNHO m3nmgtomi 100 0001 0000 0001 0001 0001 0010 0001 0011 0001 0100 0001 0101 BCD not very efficient Used in early computers 40s 505 Used to encode numbers for seven segment displays Easier to read Gray Code Digit Binary Gra CO 9 Gra code is notanumber 0 0000 0000 sys em 1 0001 0001 It is an alternate way to represent 2 0010 0011 four bit data 3 0011 0010 o 4 0100 0110 Only one bit cban es from 5 0101 0111 one deCImal digit 0 the next 6 0110 0101 Useful for reoucing errors in 7 0111 0100 communication 8 1000 1100 o 9 1001 1101 Can be scaled to larger numbers 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 14 1110 1001 15 1111 1000 ENGN112 L4 Number Codes and Registers ASCII Code American Standard Code for Information Interchange ASCII is a 7bit code frequently used with an 8th bit for error detection more abou that in a bit bin hex 1000001 41 65 101 1000010 42 66 102 1000011 43 67 103 ENGIN112 L4 Number Codes and Registers Transmitter gt quota V Receiver quot1 A 09 10 codes others quotamp Complete listing in Mano text Transmission susceptible to noise Typical transmission rates 1500 Kbps 566 Kbps How to keep data transmission accurate ENGN112 L4 Number Codes and Registers Parity Codes Parilty codes are formed b concatenating a parity bit to each code word 0 C In an oddparity code the parity bit is specified so that the total number of ones is odd In an evenparity code the parity bit is specified so that the total number of ones is even 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 T T Added even parity bit Added odd parity bit ENGN112 L4 Number Codes and Registers Parity Code Example 0 Concatenate a parit bit to the ASCII code for the characters 0 X an to produce both oddparity and evenparity codes Character ASCII OddParity EvenParity ASCH ASCH 0 0110000 10110000 00110000 X 1011000 01011000 11011000 0111100 10111100 00111100 ENGIN112 L4 Number Codes and Registers Binary Data Storage Binary cells store individual bits of data Multiple cells form a register Data in registers can indicate different values Hex decimal BCD ASCII l00l1l01l0l11l Binary Cell ENGN112 L4 Number Codes and Registers Register Transfer 0 Data can move from register to register 0 Digital logic used to process data 0 We will learn to design this logic ENGN112 L4 Number Codes and Registers Transfer of Information MEMORYUNIT o I J I O I H I N I Data mPUt at keyboard 3901001016010011113911001000391100111039 Shifted into place 0 Stored in memory PROCESSORUNIT H H H 2232 NOTE Data input in ASCII INPUT UNIT 1 va IE Reglster Keyboard CONTROL Fig 1 1 Transfer of information with registers ENGIN112 L4 Number Codes and Registers Building a Computer Operand 1 MEMORY UNIT Sum 0000000000 Operand 0011100001 2 0001000010 gt 0001000010 R1 1 Digital Logic Circuits for binary addition gt0100100011 R3 0011100001 R2 PROCESSOR UNIT Fig 1 2 Example of binary information processing ENGN112 L4 Number Codes and Registers We need processing We need storage We need communication You will learn to use and deSIgn these components Summary Although 2 s complement most important other number codes exist ASCII code used to reJoresent characters including those on the keyboar Registers store binary data Next time Building logic circuits ENGN112 L4 Number Codes and Registers College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 6 NAND and NOR Implementations Combinational Logic I NAND Circuits As we ve seen NAND circuits are easy to implement in CMOS Also as we ve seen the basic logic operations are AND OR and NOT NAND gates are universal in the sense that they can implement each of these basic operations i NOT Note that the operation y X can be implemented as a 2 input NAND gate with X at both inputs X X ii M z X39y X39y NOT X NAND y z W2 y 80 iii OR So 2 Xy XY XquotY X NAND Y 301 ZX gtol DJ 3H Twolevel NAND implementations for any function can be derived from the sumofproducts representation for the function using DeMorgan s Rule Example Consider the function FvmxyzWXyZW XZ By using a Karnaugh Map we saw in Discussion 5 that the function simplifies to F xz xy wz Now apply DeMorgan s Rule F Xz xy wz XZquot XYquot WZ x NAND z NAND x NAND y NAND w NAND z So we get the NAND implementation We can also derive a simple graphical method for converting AND OR logic diagrams into NAND implementations by noting that by DeMorgan s Rule X39y X y that is NAND ANDinvert is equivalent to invertOR Do z 13 Z Then to convert a general AND OR logic diagram to NAND form we 1 Replace all AND gates with NAND AN Dinvert Replace all OR gates with invertOR Important note any inputs into invertOR gates that do not come from the outputs of NAND gates must be inverted 3 Replace the invertOR gates with NAND gates Example Consider a function having the following logic gate implementation This is converted first to EgD F need inverter and then to 2 F PM II NOR Circuits NOR circuits are also easy to implement in CMOS Like NAND gates NOR gates are universal in the sense that they can implement each of the basic logic operations AND OR and NOT 0 NOT Note that the operation y X can be implemented as a 2 input NOR gate with X at both inputs X 0 XX X X yzx X Y ii M z X39y X39y X y NOTX NOR NOTy So iii OR Z xy XY X NOR Y 80 z LDJDH Twolevel NOR implementations for any function can be derived from the productofsums representation for the function using DeMorgan s Rule Example i Consider the function FvmxyZWXyzW XZ ln Discussion 5 we saw that F Z567911131415 so F 20 1234810 12 Using a Karnaugh map we see that this simplifies to F w X y z X z WX yz Xz 80 F WX yZ XZ W NOR X NOR y NOR z NOR X NOR 2 Then we have the NOR gate implementation W DO Do Do F y 33 We can also derive a simple graphical method for converting OR AND logic diagrams into NOR implementations by noting that by DeMorgan s Rule Xy X y that is NOR ORinvert is equivalent to invertAND j 2 2 2 y y Then to convert a general OR AND logic diagram to NOR form we 1 Replace all OR gates with NOR ORinvert Replace all AND gates with invertAND Important note any inputs into invertAND gates that do not come from the outputs of NOR gates must be inverted 3 Replace the invertAND gates with NOR gates Example Consider the function having the logic gate implementation This is converted first to A B F l 2 c be need inverter and then to III Combinational Circuits So far we ve looked at logic circuits that convert a number of inputs into a single output but in general circuits can use the same set of inputs to generate a number of different outputs Some circuits have memory that is they store outputs from one time to use as inputs at another time These are called sequential circuits we ll consider them later in the course For now we will consider circuits that have multiple inputs and outputs but no memory these are called combinational circuits ll combinational n inpUtS circuit 11 m outputs Suppose first that we are given a combinational circuit diagram how do we determine the output functions The answer is the same as for circuits with one output we trace through gates in the circuit to find the logical functions at each step Since combinational logic can get complicated it is often helpful to use internal variables which are themselves functions of inputs to describe the actions of the gates inside the circuit and at the end make substitutions to put everything in terms of input variables Example Find expressions for the outputs F1 and F2 of the following circuit A B cY TD Introduce internal variables T1 AB T2 T C T3 BC A T7 B T2 c D F F2 Then F1 T2T3 T1 CBC ABCBC F2 AT3 ABC Of course Can also describe the inputoutput relations for each of the functions using truth tables Now suppose that we are given functions that we want to implement how do we design a combinational circuit to perform those functions Again the basic approach is the same as for one function we use Karnaugh maps to find simplified expressions for the functions and then connect the logic gates needed for the operations Example Suppose we want to implement a circuit that forms the arithmetic sum of two 2bit binary numbers Let the two input numbers be denoted wx and yz Note that because of a carry the sum has up to three bits denote these AB C For example wx 10 and yz 10 gives AB C 100 Design a combinational circuit that has wxyz as inputs and ABC as outputs First draw the truth table for the necessary functions 1110 101 wxyz wxyz A B C 0000 000 0 0 0 0001 001 0 0 1 0010 010 0 1 0 0011 011 0 1 1 0100 001 0 0 1 0101 010 0 1 0 0110 011 0 1 1 0111 100 1 0 0 1000 010 0 1 0 1001 011 0 1 1 1010 100 1 0 0 1011 101 1 0 1 1100 011 0 1 1 1101 100 1 0 0 1 0 1 1 1 0 1111 110 Now draw Karnaugh maps to find the function needed to generate each output variable K map for A yz 80 A wy WXZ Xyz K map for B yz W oo 01 11 1o 00 1 1 11 1 1 1o 1 1 80 B wy z WX y W X y W yz W Xy z nyz K map for C yz WX 00 01 11 1O 00 1 O1 1 1 11 1 1O 1 80 C XZ X Z Combinational Circuit for generating A and C 3 Note The circuit for generating B is quite complicated y D 12 We ll soon see a better alternative for implementing an adder in the lecture ENGIN 112 Intro to Electrical and Computer Engineering Lecture 8 Minimization with Karnaugh Maps 39 ELECTRICAL wquot ENGN11Z LB Mi zmzugh Maps September 19 ms Overview Kmaps an alternate approach to representing Boolean functions Kmap representation can be used to minimize Boolean functions Easy conversion from truth table to Kmap to minimized SOP representation Simple rules steps used to perform minimization Leads to minimized SOP representation Much faster and more more efficient than previous minimization techniques with Boolean algebra ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Karnaugh maps Alternate way of representing Boolean function All rows of truth table represented with a square Each square represents a minterm Easel to convert between truth table Kmap and O Unoptimized form number of 1 s in Kmap equals number of minterms products in SOP Optimized form reduced number of minterms F Sm0m1 x y x y 0 W X39y X y X 1 xy39 xy 0 HO H 1 O O ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Karnaugh Maps A Karnaugh map is a graphical tool for assisting in the general sumplification procedure Two variable maps B B A A I I 11 O 11 1 AB C F Threevarabe maps 0 o o o 00 1 1 C 01 o 1 A 00011110 01 1 o 00 1 0 1 13 2 1 11 0 1 11 1 1 1 11 1 1 FAB C AB 39CABC ABC 39 A B C A BC ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Rules for KMaps We can reduce functions by circling 1 s in the Kmap Each circle represents minterm reduction Following circling we can deduce minimized andor form Rules to consider ZbEvery cell containing a 1 must be included at least once The largest possible power of 2 rectangle must be enclosed The 1 s must be enclosed in the smallest possible number of rectangles Example ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Karnaugh Maps A Karnaugh map is a graphical tool for assisting in the general sumplification procedure Two variable maps AB 0 1 AB 0 1 0 O 1 IAIB O A39B AB39 1 1 O FAB Three variable maps C 00 01 11 10 O O A FAB 39CBC39 FAB C AB 39CABC ABC 39 A B C A BC ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Karnaugh maps Numbering scheme based on Gray code eg 00 01 11 10 Only a single bit changes in code for adjacent map cells This is necessary to observe the variable transitions A CABOO 01 11 10 A o c 1 0 0 1 1 GABC A Cool W A 1 1 C FABC Zmo457 AC B39C o Cooi 3 ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 More Karnaugh Map Examples Examples a b 01 a01 001 b 10W DEE fa 100 gb39 ab ab 0 00011r110 0 00011110 00010 00011 10 100M1 coutabboao fa 1 Circle the largest groups possible 2 Group dimensions must be a power of 2 3 Remember what circling means ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin 9 3 How to use a Karnaugh Map instead of the Algebraic simplification oooogt AGO OA Om Adoo x xoow Avo xo xo Cout s A B Cin A BCin A BCin ABCin Cout A BCin A B Cin ABCin ABCin ABCin ABCin AB CIin ABCin ABCin mi ABCin A A wcm B Bi t in Cin gamete iBem i mm H AB BCin ACin AB ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin S 0 0 0 0 0 0 0 1 1 0 A H o 1 o 1 o lt Adder S 01 1 0 1 lt B 1 o o 1 o lt 1 0 1 0 1 1 1 0 0 1 Cout 1 1 1 1 1 lt A 390 0 1 0 Nowwe haveto coverall the1sin the Karnaugh Map using the largest rectangles and as few rectangles as we can BltJO 391 1 1 Karnaugh Map for Cout ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A Adder S B Cout A 390 0 o BltJO 391 W Cin Karnaugh Map for Cout ENGN112 L8 Minimization with Karnaugh Maps oooogt 9 3 Adoo x xoow Avo xo xo AGO OAAOU Now we have to cover all the 13 in the Karnaugh Map using the largest rectangles and as few rectangles as we can Cout ACin September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin S 0 0 0 0 0 0 0 1 1 0 A o 1 o 1 o S 0 1 1 0 1 B 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 Cout 1 1 1 1 1 A r H Now we have to cover all the 1s in the O 1 0 Karnaugh Map using the largest I rectangles and as few rectangles 1 as we can 390 B 10 Cin Karnaugh Map for Cout Cout Acin AB ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin S 0 0 0 0 0 0 0 1 1 0 A o 1 o 1 o S 0 1 1 0 1 B 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 Cout 1 1 1 1 1 A r H Now we have to cover all the 1s in the O 1 0 Karnaugh Map using the largest I rectangles and as few rectangles 1 as we can 390 B 10 Cin Karnaugh Map for Cout Cout ACin AB BCin ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin S 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Cout r H a DJ 1 H W Cin S A BCin Karnaugh Map for S ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin s o o o o o oo 1 1 o A 01 o 1 o Adder S 01 1 0 1 B 10 o 1 0 1o 1 o 1 11 o o 1 11 1 1 1 Cout A f 390 39039 1 Blt O 1 o W Cin S A BCin A B Cin Karnaugh Map for S ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Cin A B Cin s o o o o o oo 1 1 o A 01 o 1 o Adder S 0 1 1 o 1 B 10 o 1 0 1o 1 o 1 11 o o 1 11 1 1 1 Cout A 201039 1 Bide o W Cin S A BCin A B Cin ABCin Karnaugh Map for S ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Application of Karnaugh Maps The Onebit Adder Can you draw the Circuit diagrams Cin A B Cin s o o o o o o o 1 1 o A o 1 o 1 o Adder S 0 1 1 0 1 B 1 o o 1 o 1 o 1 o 1 1 1 o o 1 1 1 1 1 1 Cout A r 7 o 0 Bi on w o Cin S A BCin A B Cin ABCin AB Cin Kamaugh Map for S No Possible Reduction ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 Summary Karnau hmap allows us to represent functions with new no atIon Representation allows for logic reduction Implement same function with less logic Each square represents one minterm Each circle leads to one product term Not all functions can be reduced Each circle represents an application of Distributive rule xy z xy xz Complement rule x x ENGN112 L8 Minimization with Karnaugh Maps September 19 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 27 Counters 39 ELECTRICAL gt9 E N GIN E E RI N G UNIVERSITY OF MASSACHUSETTS ENGIN11Z L27 Cnunlers Nnvemher J Overview Counters are important components in computers The increment or decrement by one in response to input Two main types of counters Ripple asynchronous counters Synchronous counters Ripple counters Flip flop output serves as a source for triggering other flip flops Synchronous counters All flip flops triggered by a clock signal Synchronous counters are more widely used in Industry ENGN112 L27 Counters November 5 2003 Counters Counter A register that goes through a prescribed series of states Binary counter Counter that follows a binary sequence N bit binary counter counts in binary from n to 2quot1 Ripple counters triggered by initial Count signal Applications Watches Clocks Alarms Web browser refresh ENGN112 L27 Counters November 5 2003 Binary Ripple Counter Reset signal sets all outputs to 0 Count signal tog les output of loworder fle op Loworder fli flop provides trigger for a jacent flip flop Not all flops change value simultaneously Lowerorder flops change first Focus on D flip flop implementation ENGN112 L27 Counters Reset T as A0 D R A0 Count c C R Count c C R F J 7 T a A1 D A 4c CR 4c CR 3 77 T as A2 D A2 0 CR 4c CR T J 7 T 7 A3 D A3 c CR 46 CR j i Logic l Reset a With T ip ops b With D flip flops Fig 6 8 4 Bit Binary Ripple Counter November 5 2003 Another Asynchronous Ripple Counter 39AII J and K inputs assume 0 e L Recycle to 0000 Similar to T flop example on previous slide 0 ENGN1 12 L27 Counters NovemberS 2003 Asynchronous Counters lglgch FF output drives the CLK input of the next FFs do not change states in exact synchronism with the applied clock pulses There is dela between the responses of successwe Fs Ripple counter due to the wa the FFs respond one after another In a kind 0 rIppIIng effect 9 9 03gt lp aOt AOt dot Ol 9 3 2 1 OOOOOO ENGN112 L27 Counters November 5 2003 Synchronous counters Synchronousparallel counters All of the FFs are triggered simultaneously by the clock input pulses All FFs change at same time Remember lf JK0 flop maintains value lf JK1 flop toggles Most counters are synchronous in computer systems Can also be made from D ops Value increments on posmve edge ENGN112 L27 Counters Count enable A2 To next stage CLK Fig 6 12 4 Bit Synchronous Binary Counter November 5 2003 Synchronous counters O Synchronous counters Same counter as previous slide except Count enable replaced by JK1 Note that clock signal is a square wave Clock fans out to all clock inputs MC k H C 1 D J gl r n J 39JJZFh h ELKCl D F 39 L 39n v i 1 J LJ l Inpm ENGN112 L27 Counters November 5 2003 Circuit operation b um D D A Cl C Ci IZI C 1 r I n 1 2 f I39JI 1 D 3 c u 1 1 I III I D l 15 I 1 III I E El I I D Tquot I 1 1 1 3 1 U 339 E 9 39l 39339 El 1 1O 1 393 1 E 1 1 quotI O 1 1 12 1 1 3 1 1393 1 1 CI 1 11 1 39I 1 l 15 1 1 1 39I r r ft I39j l1 E tI 1 Count value Increments on each negative edge 0 Note that loworder bit A toggles on each clock cyc e ENGN112 L27 Counters November 5 2003 Synchronous UPDown counters Up own T iAO UplDown Counter can either D C count up or down on each clock cycle Up counter counts from 0000 U to 1111 and then changes 9 W A1 back to 0000 m Down counter counts from 1111 to 0000 and then back 39 to 1111 L j T 7A2 Counter counts up or down c each clock cycle Output changes occur on clock rising edge A3 C CLK Fig 613 4 Bit Up Down Binary Counter ENGIN112 L27 Counters November 52003 Counters with Parallel Load Counters with parallel load can have a preset value Load signal indicates that data I lo should be loade into the counter Clear resets counter to all zeros Carry output could be used for higherorder bits ENGN112 L27 Counters Count Load 0 A0 11 A1 2 A2 Clear CLK Carryoutput Fig 6 14 4 Bit Binary Counter with Parallel Load November 5 2003 Counters with Parallel Load Count Clear Clk Load Count Function 0 X X Clear toO LOad Load inputs 10 1 Count 0 No Change 11 A0 gtltgtlt 1 1 1 O 1 0 A1 Function Table If Clear is asserted 0 the 12 counter is cleared If Load is asserted data inputs are loaded If Countasserted counter Clear value IS Incremented CLK A2 A3 Carryoutput Fig 6 14 4 Bit Binary Counter with Parallel Load ENGN112 L27 Counters November 5 2003 Binary Counter with Parallel Load and Preset Frese aEle parallel counier w asynchronous preset Parallel data inputs P2 CLOCK Parallel load iPL U lgtcgt If PL 0 load P into flops Binary Counter with Parallel Load and Preset Commercial version of binary counter PT P3 P2 P1 P0 T7711 1 74AL5193 CPD MOD16 tipdown T CD MR 03 Q2 0 Q0 3 Mode Select MR PT CPU CPD Mode H X X X Asynch reset L L X X Asynch preset L H H H No change L H T H Count up 1 H H 1 Countdown H HIGH L LOW X Don t care T PGT c ENGIN112 L27 Counters POPS QDQG n Eu Description Count up clock Input active nsing edge Countdown clock input active rising edge Asynchronous master reset input active HlGH Asynchronous parallel load input actlve LOW Parallel data inputs Flipflop outputs Terminal countdown borrow output active LOW Terminal countup carry output active LOW b November 5 2003 Summary Binary counters can be ripple or synchronous Ripple counters use flip flop outputs as flop triggers Some delay before all flops settle on a final value Do no require a clock signal Synchronous counters are controlled by a clock All flip flops change at the same time UpDown counters can either increment or decrement a stored binary value Control signal determines if counter counts up or down Counters with parallel load can be set to a known value before counting begins ENGN112 L27 Counters November 5 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 1 5 Magnitude Comparators and Multiplexers 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L15 Magnilude Cnmpzrmnr and Multiplexers 0dnher62 3 Overview Discussion of two digital building blocks Magnitude comparators Compare two multibit binary numbers Create a single bit comparator Use repetitive pattern Multiplexers Select one out of several bits Some inputs used for selection Also can be used to implement logic ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Magnitude Comparator O The comparison of two numbers outputs AgtB AB AltB 0 Design Approaches the truth table 22 entries too cumbersome for large n use inherent regularity of the problem reduce design efforts reduce human errors A3O B3O ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Magnitude Comparator A0 CO A1 AEQB A3 How can we find A gt B How many rows would a truth table have 28 256 ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Magnitude Comparator C0 A0 D01 A1 C1 B1 AEQB Find A gt B A2 C2 32 A3 C D23 33 Because A3 gt B3 IfA 1001 and ie A3 3339 1 B 0111 Therefore one term in the IS A gt B logic equation for A gt B is Why A3 B3 ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 WWW IfAlOlOand AgtBA3B339 B1001 C3A2B2 isAgtB Why Because A3 B3 and A2 82 and A1 gt Bl ie C3 1 and C2 1 and A1 B1 1 Therefore the next term in the logic equation for A gt B is C3C2A1Bl ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Magnitude Comparison Algorithm gt logic A A3A2A1Ao B 33323130 AB if A3Bs A2Bz A1B1and A1B1 Test each bit equality xi AiBiAi39Bi39 AB x3x2x1xo More difficult to test less thangreater than AgtB A3B339x3Asz39x3x2A1B139x3x2x1AoBo39 AltB A339B3x3A239Bzx3x2A139B1x3x2x1AO39B0 Start comparisons from highorder bits 0 Implementation xi AiBil39I39Ai39Bi ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Dal mums Cascarlm mDuLs magmm e compmw DA Ll r a Cmpurs mum rAeLL COMPAR NG NF UTS CASCAD NG NPUTS 9mm ALB An 51 Av Bu n Am A u 0 h 0n L 0A 0 A33 x gtlt x x H L L Ay E x x x x L H L A3433 x x x x H L L AraJ x x x x L H L A a AVE x x x H L L A4B AKE x x x L H L A3 Eg Ara x x x H L L A778 Ara x x x L H L r8 M By H L L H L L A3433 AVEV L H L L H L A a A E x X H L I H Area Ara L L L H H L K7L2 A eB H H L L L L n MGH wage Levev L e LDW IDhage Lem x 7 mmaiena ENGN112 L15 Magnitude Comparator and Multiplexers Octobers 2003 Magnitude Comparator Realworld application Thermostat controller 74H0855 as in Fig 937 Temp sensor A0 Analog gt to digital 8 OAgtB CLR F converter 39 urnace A7 controller OAB Keypad Keypad Bo encoder l8 0 SET and lt5 registers B7 ENGIN112 L15 Magnitude Comparator and Multiplexers October 6 2003 Multiplexers 0 Select an input value with one or more select bits Use for transmitting data 0 O Allows for conditional transfer of data 0 Sometimes called a mux 10 10 0 y MUX y 11 1 11 S 39 r gt07 S 21 Logic diagram b Block diagram Fig 4 24 2 t0 1 Line Multiplexer ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 5 2003 4 to 1 Line Multiplexer Functinn tame 31 33 ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Quadruple 2 to 1Line M ultiplexer A W N Vi V2 Va Eo E 0 D V a i a 55W y i saw 52 a H Notice enable bit D D Notice select bIt saint 4 bit inputs E ianabie Euclimz L15 mamme Cnnurlnr Ind Mmmlmus omnhus2nn1 Multiplexer as combinational modules Connect input variables to select inputs of multiplexer n1 for n variables Set data inputs to multi exer equal to values of function for correspon ing assignment of select variables Using a variable at data inputs reduces size of the multiplexer 4gtlt1MUX y 50 x 51 x y z F 0 0 0 0 0 0 1 1 FZ z 0 0 1 0 1 r O 1 1 0 Fz Z 1 1 0 0 0 0 2 1 0 1 0 FZO 1 1 0 1 1 3 1 1 1 1 F21 a Truth table Fig 427 Implementing a Boolean Function with a Multiplexer ENGIN112 L15 Magnitude Comparator and Multiplexers b Multiplexer implementation October 6 2003 Implementing a Four Input Function with a Multiplexer Bx lMUK DJ wmmhmm LD dd nInd tnDDDDDDDQ L ocQOd DQoom d dddUCGGD39Ud Ed II D ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Typical multiplexer uses RE R Ell R2 RE R4 Cl 1 b 1 2 3 J Sam I MUK A MUM B 1 Hill Fur nbil operands Mun A 4 H and MuxB replicated n times 39 1 and CDHI39IEGIECJ to the curresponding bit 5 of the input vectnrs FUNCTIONAL f quot UNIT Example SelA 39l Sella 2 Z lH1Fl3J l lBl Flynn 931 Multiplexer example allquot use ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 Th reestate gates A multiplexer can be constructed with threestate gates Output state 0 1 and highimpedance open ckts If the select input E is 0 the threestate gate has no t outpu 74L8125 74L8125 A x A x Opposite true here E E No output ifE is 1 ENGN112 L15 Magnitude Comparator and Multiplexers October 62003 Threestate gates A multiplexer can be constructed with threestate gates Output state 0 1 and highimpedance open ckts If the select input is low the threestate gate has no output 10 11 13 S O 1 3 Select S 2 X 4 1 decoder 2 Select J Enable EN 3 a 2to1 line mux b 4 to 1 line mux ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 5 2 03 Summary Magnitude comparators allow for data comparison Can be built using andor gates Greaterless than requires more hardware than equality Multiplexers are fundamental digital components Can be used for logic Useful for datapaths Scalable Tristate buffers have three types of outputs 0 1 highimpedence Z Useful for datapaths ENGN112 L15 Magnitude Comparator and Multiplexers OCtOber 6 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 2 Number Systems Russell Tessier KEB 309 G tessierecsumassedu ENGN112 L2 Number Systems September 5 2003 Overview The design of computers It all starts with numbers Building circuits Building computing machines Digital systems Understanding decimal numbers Binary and octal numbers The basis of computers Conversion between different number systems ENGN112 L2 Number Systems September 5 2003 Digital Computer Systems Digital systems consider discrete amounts of data Examples 26 letters in the alphabet 10 decimal digits Larger quantities can be built from discrete values Words made of letters Numbers made of decimal digits eg 23987532 Computers operate on binary values 0 and 1 Easy to represent binary values electrically Voltages and currents Can be implemented using circuits Create the building blocks of modern computers ENGN112 L2 Number Systems September 5 2003 Understanding Decimal Numbers Decimal numbers are made of decimal digits 0 1 2 3 4 5 6 7 8 9 But how many items does a decimal number represent 8653 8x103 6x102 5x101 3x10o What about fractions 9765435 9x104 7x103 6x102 5x1o1 4x100 3x10391 5x102 In formal notation gt 976543510 Why do we use 10 digits anyway ENGN112 L2 Number Systems September 5 2003 Understanding Octal Numbers Octal numbers are made of octal digits 01234567 How many items does an octal number represent 45358 4x83 5x82 3x816x8 136210 What about fractions 465278 4x82 6x81 5x80 2x8391 7x82 Octal numbers don t use digits 8 or 9 Who would use octal number anyway ENGN112 L2 Number Systems 7 7 September 5 2003 Understanding Binary Numbers Binary numbers are made of binary digits bits 0 and 1 How many items does an binary number represent 10112 1x23 0x221x211x2 1110 What about fractions 110102 1x22 1x210x20 1x21 0x22 Groups of eight bits are called a byte 11oo1oo12 Groups of four bits are called a nibble 1101 2 ENGN112 L2 Number Systems September 5 2003 Why Use Binary Numbers Volts 0 Easy to represent 0 and 1 using electrical values Possible to tolerate noise Range Easy to transmit data for logic1 0 Easy to build binary circuits Transition occurs between these limits AND Gate Range for logic0 Fig 13 Example of binary signals ENGN112 L2 Number Systems September 5 2003 Conversion Between Number Bases Octalbase 8 Decimalbase 10 Binarybase 2 Hexadecimal base16 Learn to convert between bases Already demonstrated how to convert from binary to decimal Hexadecimal described in next lecture ENGN112 L2 Number Systems September 5 2003 Convert an Integer from Decimal to Another Base For each digit position 1 Divide decimal number by the base eg 2 2 The remainder is the lowestorder digit 3 Repeat first two steps until no divisor remains Example for 13 Integer Remainder Coefficient Quotient 132 6 12 a0 1 62 3 0 a1 32 1 12 a2 1 12 O 12 a3 Answer 131o a3 a2 a1a02 11012 ENGN112 L2 Number Systems September 5 2003 Convert an Fraction from Decimal to Another Base For each digit position 1 Multiply decimal number by the base eg 2 2 The integer is the highestorder digit 3 Repeat first two steps until fraction becomes zero Example for 0625 Integer Fraction Coefficient 0625 X 2 1 025 a1 1 0250 X 2 O 050 a2 O 0500X2 1 O a3 1 ENGN112 L2 Number Systems Answer 062510 0a1 a2 a3 2 01012 September 5 2003 The Growth of Binagy Numbers n 2quot n 2quot 0 201 8 28256 1 212 9 29512 2 224 10 21 1024 3 238 11 2112048 4 2416 12 2124096 5 2532 20 22 1 M Mega 6 2364 30 23 1G Giga 7 27128 40 24 1 T Tera ENGN112 L2 Number Systems September 5 2003 Binary Addition Binary addition is very simple This is best shown in an example of adding two binary numbers 1 1 1 1 1 1 carries 1 1 1 O 1 1 O 1 1 1 ENGN112 L2 Number Systems September 5 2003 Binary Subtraction We pan also perform subtraction with borrows in place of carrIes Let s subtract 101112 from 10011012 borrows ENGN112 L2 Number Systems September 5 2003 Binary Multiplication Binary multiplication is much the same as decimal multiplication except that the multIpIIcatIon operations are muc simpler X 010 00000 10111 00000 10111 ENGN112 L2 Number Systems September 5 2003 Convert an Integer from Decimal to Octal For each digit position 1 Divide decimal number by the base 8 2 The remainder is the lowestorder digit 3 Repeat first two steps until no divisor remains Example for 17510 Integer Remainder Coefficient Quotient 1758 21 78 a0 7 218 2 58 a1 5 28 O 28 a2 2 Answer 1751o a2 a1 a02 2578 ENGN112 L2 Number Systems September 5 2003 Convert an Fraction from Decimal to Octal For each digit position 1 Multiply decimal number by the base eg 8 2 The integer is the highestorder digit 3 Repeat first two steps until fraction becomes zero Example for 03125 Integer Fraction Coefficient 03125X8 2 5 a12 05000 X 8 4 0 a2 4 Answer 0312510 024s ENGN112 L2 Number Systems September 5 2003 Summary Binary numbers are made of binary digits bits Binary and octal number systems Conversion between number systems Addition subtraction and multiplication in binary ENGN112 L2 Number Systems September 5 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 38 Programmable Logic ELECTRICALgt UNIVERSITY or MASSACHUSETTS AMHERST ENGIN11Z L33 Prngrzmmzhle Lngic Decemh2r52 3 Overview Programmable logic offers designers opportunity to cus omIze chIps Programmable logic devices have a fixed logic structure Programmable array logic contain ANDOR circuits First introduced in early 1980 s Field programmable gate arrays FPGAs contain small blocks that implement truth tables First introduced in 1985 Xilinx Corporation Software used to convert user designs to programming information ENGN112 L38 Programmable Logic December 5 2003 Design Implementation Chip creation is a long and difficult process Millions of dollars required to create custom silicon Simulation synthesis fabrication lots ofjobs for eng I nee rs gt HDL description Valld Synthesis r Netllst gt Of desrgn des1gn tools v v Simulate Simulate Test bench gt RTL de gn gate level design it Result Result Good Good Needs Needs correction correction r v Compare Fabricate No match Match 1C Fig 8 1 Process of HDL Simulation and Synthesis ENGN112 L38 Programmable Logic December 5 2003 Programmable Logic Design Generic chip created and then customized by deSIgner Programming information used Like a ROM Analogy sign making Custom sign more expensive customized by manufacturer difficult to change Sign built by consumer from individual letters less expensive not quite as nice easier to change remix letters ENGN112 L38 Programmable Logic December 5 2003 Programmable Array Logic Implements sumofproducts expressions Four external inputs and complements Feedback path from output F1 Product term connections made via switches ENGIN112 L38 Programmable Logic AND gates inputs Product 12345678910 term 11 12 13 4 10 Fig 7 16 PAL with Four Inputs Four Outputs and Three Wide AND OR Structure December 5 2003 Programmable Array Logic AND gates inputs Consider implementing the P d t 1 2 3 4 5 6 7 8 910 following expression t e m ic i i i 1232 3 414F1 Note that only functions of up to three product terms can be 12 implements Larger functions need to be chained together via the feedback path 13 4 10 Fig 7 16 PAL with Four Inputs Four Outputs and Three Wide AND OR Structure ENGN112 L38 Programmable Logic December 5 2003 Reconfigurable Hardware Logic Element 4 Out UCWgt ABCD out Each logic element operates on four onebit inputs Output is one data bit Can perform y Boolean function of four inputs 224 64K functions ENGN112 L38 Programmable Logic December 5 2003 FieldPro rammable Gate Array Logic Element j m 5 in in ELE ELE i ELE ELE ELE ELE t ELE ELE ELE ELE Each logic element outputs one data bit Interconnect programmable between elements Interconnect tracks grouped into channels ENGN112 L38 Programmable Logic December 5 2003 FPGA Architecture Issues i x Logic x Element IX 1 Need to explore architectural issues How much functionality should go in a logic element How many routing tracks per channel Switch population ENGN112 L38 Programmable Logic December 5 2003 Translating a Design to an FPGA C program Circuit Array 39 gtB C quot DEE CIAB DEE DEE CAD to translate circuit from text description to physical implementation well understood CAD to translate from C program to circuit not well understood Very difficult for application designers to successfully write high performance applications Need for design automation ENGN112 L38 Programmable Logic December 5 2003 Circuit Compilation 1 Technology Mapping 339 gt LUT quot 2 Placement DEEZ E 1 2 7 Assign a logical LUT to a D C 21 39 physical location 3 ROUting Select wire segments And switches for a El Interconnection Cl C E December 5 2003 Two Bit Adder Made of Full Adders A AB D co ci S Logic synthesis tool reduces circuit to SOP form S ABCi A39B39Ci AB Ci A BCi I I Ci LUT C0 C1 LUT Co ABCi A BCi AB Ci ABCi ENGN112 L38 Programmable Logic December 5 2003 Dynamic Reconfiguration HIDE D IIDD DEED DEED What if I want to exchange part of the design in the device with another piece Need to create architectures and software to incrementally change designs Effectively a configuration cache ENGN112 L38 Programmable Logic December 5 2003 Xilinx XC4000 Cell Figural EMGIMHZ m Prnummrmhle unit 24 Decenter 5 2m Xilinx XC4000 Routing Small boxes represent switches Eymmx ENGIMHZ us Prnnrzmmzhle anc Decenter 5 2m Summary Programmable logic allows for designers to easily create custom deSIgns Programmable array logic contains ANDOR structures to implement SOP equations FPGAs contain small memories and numerous wires for routing Designers create designs in Verilog Design translated to the chip via software Hands on experience in ECE353 ECE354 ENGN112 L38 Programmable Logic December 5 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 31 Read Only Memory ROM 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L31 Read Only Memnry Nnvemher172 3 Overview Readonly memory can normally only be read Internal organization similar to SRAM ROMS are effective at implementing truth tables Any logic function can be implemented using ROMS Multiple singlebit functions embedded in a single ROM Also used in computer systems for initialization ROM doesn t lose storage value when power is removed Very useful for implementing FSMs ENGN112 L31 Read Only Memory November 17 2003 ReadOnly Memory ROM An array of semiconductor devices diodes transistors field effect transistors 2N words by M bits Data can be read but not changed normal operating conditions ENGN112 L31 Read Only Memory November 17 2003 ReadOnly Memory ROM N input bits 2 words by M bits 0 Implement M arbitrary functions of N variables Example 8 words by 5 bits A ROM 3 Inpuf B 8 words quot65 c x 5 bits F Fo F F 5 Output Lines F 1 4 2 3 ENGN112 L31 Read Only Memory November 17 2003 ROM Implementation ROM quotRead Only Memoryquot values of memory locations are fixed ahead of time 0 A ROM can be used to implement a truth table if the address is mbits we can address 2m entries in the ROM our outputs are the bits of data that the address points to 0000011 0011100 m n 0101100 7 0111000 1000000 1010001 1100110 1110111 m is the quotheightquot and n is the quotwidthquot ENGN112 L31 Read Only Memory November 17 2003 ROM Implementation 0 Suppose there are 10 inputs 10 address lines ie 210 1024 different addresses Suppose there are 20 outputs ROl is 210 x 20 20K bits and a rather unusual slze Rather wasteful since lots of storage bits For functions doesn t take advantage of Kmaps other minimization ENGN112 L31 Read Only Memory November 17 2003 ReadOnly Memory ROM Each minterm of each function can be specified 3Inpus A B c F0 F1 F2 F3 F4 Lines A o o o o 1 o 1 o B 83 o o 1 1 1 1 1 o C 5 o 1 o o o o 1 1 x 395 o 1 1 1 1 1 o 1 1 o o o 1 o 1 o I I 1 o 1 o 1 1 1 1 1 1 o 1 o 1 o 1 F0 F1F2 F3 F4 1 1 1 1 1 o 1 o 5 OquuTs Lines ENGN112 L31 Read Only Memory November 17 2003 ROM Internal Structure n Inpufs Lines n biT decoder Memory Array 2n words x m bi rs HW m OquuTs Lines ENGN112 L31 Read Only Memory November 17 2003 ROM Memory Array A 3To8 B decoder c ENGN112 L31 Read Only Memory m0A B C39 m1A B C m2A39BC39 m3A39BC m4AB C39 m5AB C m6ABC m7ABC November 17 2003 Inside the ROM Alternate view Each possible horizontalvertical intersection indicates a possible connection Or ghates at bottom output the word selected by e decoder 32 x 8 5 X 32 decoder A7 A6 A5 A4 A3 A2 A1 A0 Fig 7 10 Internal Logic of a 32 X 8 ROM ENGN112 L31 Read Only Memory November 17 2003 ROM Example Specify a truth table for a ROM which implements F AB A BC39 G A B39C C H AB39C ABC A B39C OOOO gt OO OO W O O O O O ENGN112 L31 Read Only Memory November 17 2003 ROM Example Specify a truth table for a ROM which implements F AB A BC39 G A B39C C H AB39C ABC A B39C OOOO gt dO O O O C d OOO OO 39I39I ENGN112 L31 Read Only Memory November 17 2003 ROM Example Specify a truth table for a ROM which implements F AB A39BC G A39B C C A B C F G H H AB C ABC A39B C 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 ENGN112 L31 Read Only Memory November 17 2003 Function Implementation Each column is a new function Note two outputs unused F G H ENGN112 L31 Read Only Memory November 17 2003 ROM Implementation of a Moore Machine ROMs implement combinational logic Note that ROMs do not hold state How would you determine the maximum clock frequency of this circuit Look at the FF to FF path NS to PS Present Next Inputs State State Outputs ENGN112 L31 Read Only Memory November 17 2003 ROM Implementation of a Mealy Machine ROMS implement combinational logic Note that ROMS do not hold state How would you determine the maximum clock frequency of this circuit Look at the FF to FF path NS to PS Present Next State State Outputs Inputs ENGN112 L31 Read Only Memory November 17 2003 Summary ROMS provide stable storage for data ROMS have address inputs and data outputs ROMs directly implement truth tables ROMs can be used effectivelgjn lllleal and Moore machines to Implement com InatIona logic In normal use ROMs are readonly They are only read not written ROMs are often used by computers to store critical information Unlike SRAM they maintain their storage after the power is turned off ENGN112 L31 Read Only Memory November 17 2003 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 5 Digital Circuits and Karnaugh Maps I Digital Integrated Circuits Logic circuits are constructed from transistors For digital circuits metaloxide semiconductor MOS transistors are most commonly used In digital circuits transistors act like voltagecontrolled switches The voltage level on a node called the gate determines whether or not current flows between two nodes called the source and drain Current flow closed switch between source and drain no current flow open switch between source and drain Typically we set some high voltage level say 5 V to represent logical 1 and some low voltage say 0 V to represent 0 We set a voltage source at each of those levels the high voltage source is often denoted VDD and the low voltage as ground Then we implement logic functions by using input bits to determine a set of gate voltages that open and close switches as needed to connect the output node to the appropriate source voltage again high for 1 and low for O nchannel MOS D Symbol G Also G S D Simplified operation Gate voltage high Gate voltage low Drain connected NO to Source connection pchannel MOS Symbol Also G 4 G l 8 Simplified Operation Gate voltage Gate voltage low high Drain connected No connection to source CMOS Complementary MOS CMOS circuits have both nchannel and p channel MOS transistors connected to form logic circuits Examples i CMOS Inverter 5 V VDD5 V X21 L 5 V 39 y0 O V X y 0 V GNDO v 5 V x0 y1 O V 80 y X 5 V OV ii CMOS NAND Gate V00 0 A1B0 Y1AB39 1 A1 B1 0 iii CMOS NOR Gate l39nn Y0 Example Draw a CMOS implementation of the function FABC A B C A BC A BC A BC A NAND B NOR C So can just connect the CMOS NOR with B and C as inputs and CMOS NAND with A and and the NOR gate output as inputs gates shown previously II Karnaugh Maps To save on circuit complexity power requirements space on an integrated circuit etc it is desirable to implement logic functions with as few and as simple logic gates as possible To do this we need to minimize the numbers of terms and literals used to represent logic functions One relatively simple method that has been developed for simplifying functions of up to four variable is the use of Karnaugh maps The map is a table with squares that correspond to minterms The function is expanded as a sum of minterms for every minterm in the function a 1 is placed in the map in the corresponding square Then the function can be simplified by summing the minterms that correspond to adjacent 1 s in the map this eliminates a term and a literal Twovariable map y X 0 1 m0 39 X y m1 39 X y O A m2 39 xy m3 39 xy Example Simplify the function FX y Xyx yx y m0m1m3 X y F o o 1 m X y 0 1 Truth 0 Karnaugh O m01 m11 Table 0 1 1 quot71 map 1 O O 1 m3 1 1 1 1 m3 803 F m0m1m1m3 X y X YX yX X y Threevariable map Now say have three variables Xyz We set up the map so that the rows are indexed by X and the columns by yz For yz we use Grey Code ordering that is 00 O1 11 10 yz X 00 O1 11 10 0 m0 X y z m1X y z m3 X yz m2 X yz 1 m4 xy z m5 xy z m7 xyz m6 xyz We can group adjacent squares of 1 s in blocks of two or four Note that leftmost and rightmost columns are treated as being adjacent as if table were wrapped on a cylinder Sum of any block of ones is equal to the variables that do not change in that block Examples i Simplify the function f1abc ab ac a bc Truth table for this function was given in Discussion 3 it shows that f1 2 356 7 So K map is bio a 00 O1 11 10 0 m3 1 1 I35 1 m7 1 m6 1 So f1 m3m7m5m7m6m7 a bcabcab cabcabc abc bcacab ii Simplify the function f2xyz 20 124 6 lelzIlelzlezlXylzlXyzl yz X 00 O1 11 10 0 m0 1 m1 1 m2 K map 803 f2 m0m1 m0m4m2m6 Xiyiz Xyz Xiyizi Xyz lel z Terminology An implicant is a block of ones in a K map A prime implicant is a block that contains the maximum possible number of adjacent squares An essential prime implicant is a prime implicant that includes a square that is not covered by any other prime implicant To minimize the number of terms in a function representation find a representation solely in terms of essential prime implicants Examples i In previous example Essential prime implicants are ZO246 and ZO1 yz 0m01 m1z1 m21 ii What are the essential prime implicants of F 20 1245 6 7 yz X 00 O1 11 10 0 m0 1 m1 1 m2 1 Essential prime implicants are Z0145 and Z024 6 So Fy z Note that we do not decompose F into 20 145 and 22 6 why not Because 22 6 is not an essential prime implicant in fact it is not even a prime implicant because it is not the largest possible block covering the 1 s at m2 and ms If we did write F 20 145 22 6 we would get F y yz which is not the simplest possible representation Fourvariable map Now say we have four variables WXyz We set up the map so that the rows are indexed by WX and the columns by yz We use Grey Code ordering for both WX and yz yz WX OO 01 11 1O 00 m0 39 W X y z m1 W X y z m3 W X yz m2 39 W X yz 01 m4 39 W Xy z m5 W Xy z m7 W Xyz m6 39 W Xyz 11 m12 wxy z m13 wxy z m15 wxyz m14 wxyz 10 m8 39 WX y z m9 39 WX y z m11 39 WX yz mm 39 WX yz Now blocks implicants can have size 2 4 or 8 Also note that we treat top and bottom rows as being adjacent Example Simplify the function FWXyzWXyzW Xz Truth Table wxyz 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 OOOOOOOOn m5 m6 m7 me So F 25 6 7911 13 1415 K map yz OO 01 11 1O 80 F 2571315 Z671415 29111315 xzxywz Further Notes We can use Karnaugh maps for more than 4 variables but it gets increasingly complicated and difficult to do by hand for more than 4 variable we usually use a computer program to do the minimization Sometimes there are certain combinations of inputs that are not allowed to occur so the value of the function for those inputs is not specified Those inputs are called don tcare conditions it s as if for those inputs we don t care whether the output is a O or a 1 In the K map boxes for don tcare conditions are marked with X s They can be grouped with blocks of 1 s if that leads to larger essential prime implicants that is simpler terms Example Say we have the function Fabc Z145 The inputs 000 and 111 never occur so we have the don tcare conditions 20 7 Simplify the function So F 20 145 b College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 7 Adders Subtractors and Multipliers I BinaryAdders We talked about combinational circuits last week One very important application is to implement circuits that perform binary arithmetic that is addition subtraction and multiplication First consider the problem of adding two 1bit inputs X and yto generate an output sum bit 8 and a carry bit C We have the combinational circuit truth table xy S C 00 O O Sowehave S XXORy 01 1 o C Xy 1O 1 O 11 O 1 These give us the half adder circuit Half Adder Circuit Block Symbol gtS gtC Example Draw a NAND gate implementation of a half adder S X XOR y Xy X y 00 X y Xy 39 X y x NAND y NAND x NAND y C Xy XY X NAND y So half adder has NAND gate implementation Do D D WW Now if we consider adding multiplebit numbers then the addition for each bit position but the rightmost bit potentially involves three inputs the two bits being added at that position and a carry bit from the position to the right Then the adder forthat bit has three inputs the two bits being added and the carry from the previous bit position and two outputs the sum bit and new carry bit Suppose we want to build an adder for bit position i Let A and B denote the two bits being summed at the ith position and let C denote the carry from position i1 that is the position to the right of position I Let 8 denote the sum bit generated at position iand et C1 denote the carry bit that is generated for carry to position i1 Then we have the truth table Ai Bi Ci Si Ci1 o o o o o This truth tabe generates a combinational circuit known as a full 0 O 1 1 O adden O 1 O 1 O O 1 1 O 1 1 O O 1 O 1 O 1 O 1 1 1 O O 1 1 1 1 1 1 Karnaugh map for 8 30 So 3 C A BAB CA B AB C AXOR B CAXOR B C XOR AXOR 3 BiICi Karnaugh map for CM A 00 O1 11 1O SO Ci1 BC AB AC We can directly implement a combinational circuit using the functions found from the Karnaugh maps Alternatively we can make use of the half adders that were already designed Note that if we do not restrict ourselves to prime implicants in the Karnaugh map for CH1 we can get an alternative expression in the form Bi Ci OO 01 11 10 O I 1 I Cm AiBi AiBCi AIBICI 1 1 1 1 AB C A XOR B So We need 8 CXOR AXOR 8 CM AB C A XOR B Consider the half adder connection AXOR B C XOR AXOR 3 s Ai gt HA HA 3 3 I a a gt E AiBi C C A XOR 3 AB C A XOR 3 C So this combinational Circuit is a full adder for the ith bit Block symbol A B l l C lt FA lt C i U These 1bit full adder blocks can be connected in turn to form multibit adders For example a 4bit adder for summing binary input words A3 A2A1A0 and B3 323130 possibly with an input carry bit Co to generate the sum 83 82 S180 and output carry bit C4 is as shown below A3 Ba A2 B2 A1 B1 A0 B0 l l l l l l l l 03 C2 C1 C4 lt FA FA lt FA lt FA lt co l l l l 83 82 81 so This is called a ripple carry adder since the carry bits have to ripple through the stages in order to calculate the sum bits A3A2A1Ao B3323130 Block symbol for 4bit l l l l l l l l adder circuit C4 lt 4bit adder lt Co Example Show the computation steps in using a 4bit ripple carry adder for summing 0111 and 1100 1A01BO0C00 9801C70 1 o H olt FA lt o t 1 2A11B10C10 9 1 0 1 0 H H 0lt FA 1 FA lt0 t l 3A21B21C20 9 s2oc31 4A30 B3 1 C31 9 S3 0 C4 1 80 result 410011 Output carry VV 0 7ltFAlt V 0 1 11 VV VV 1ltFAlt FA V V 0 0 V V FA lt V V FAlt0 FAlt0 Note that some time is required for the carry bits to ripple through the adder stages this carry propagation time limits the speed at multi bit adders can work The carry propagation time can be reduced through the use of carry lookahead logic Idea Consider the full adder as a connection of two halfadders P AXOR B A I HA HA I I I C CXORPS GiCiPi Ci1 G is called the carry generator and P the carry propagate Note that these do not depend on the input carry bit C In terms of these internal variables the equations for generating the carry bits in the 4bit adder are C GO POCO lt depends only on inputs C2 G P1C1 G P1GO POCO lt depends only on inputs not carry bit C1 C3G2P2C2GzP2G1P1C1 GzPzG1P2P1GoP0C0 depends only on inputs not carry bit C2 C4G3P3C362P362P2C2 GzP3G2P3P2G1P1C1 G2 P362 P3P2 G1 P3P2F 7 GO POCO depends only on inputs not carry bit C3 So at the expense of more complex circuitry the carry bits can all be generated directly from the input binary words and input carry bit without having to wait for carry propagation II Binary Subtractors Recall that ifA and B are binary words the subtraction A B can be calculated as A B A 2 s complement of B A 1 s complement of B 1 bitbybiz inverse of B input carry bit This leads to the 4bit subtractor circuit A3 33 A2 32 A1 37 A0 30 llc llc i ll C C4lt FAlt3FAlt2FAlt1FAlt 7 l l l l 83 82 S1 80 Example Consider the 4bit binary circuit for the operation 41O 51O A 0100 B 0101 We have 00 M Q xx 01 10 H H 0 0 0 0 lt FA lt FA lt FA lt FA lt1 l l l l 1 1 1 1 Result is 1111 signed 2 s complement representation for 110 Finally note that an adder and subtractor can be implemented in a single circuit by defining a mode bit M with M 0 denoting adder and M 1 denoting subtractor We replace the input carry bit 0 for addition and 1 for subtraction with M and replace each B with B XOR M B when M0 addition and B when M1 subtraction 4bitAdderSubtractor with mode bit III Binary Multiplier To see how to construct a binary multiplier using adders consider the problem of multiplying the 4bit number 83828780 by the 4bit number A3A2A1A0 We have B3 32 B1 BO A3 A2 A1 A0 A033 A032 A031 A030 A133 A132 1413114130 A233 A232 A231 A230 A333 A332 A331 A330 R7 R6 R5 R4 R3 R2 R1 R0 Now Define the binary numbers P4 P3 P2 P1 Po A033 A032 AoB1 A133 A132 A131 A130 Q4 Q3 Q2 Q1 Q0 P4 P3 P2 P1 AZB3 A282 AZB1A2BO Then R0 AOBO R7 P0 R2 Q0 R7 R6 R5 R4 R3 Q4 Q3 Q2 Q1A3B3 A382 A381 A380 80 We have the multiplier circuit A1B3A1BZA1B1A1BO OAOB3AOBZAOB1 A030 H l i l l 4bit adder lt 0 P4 1P3 P2 P1 V P0 AZB3A252AZB1AZBO i i i V V V V 4bitadder 0 L loo Q4 Q3 Q2 Q1 v V continued from last page Q4 Q3 Q2 Q1 A3B3A3BZA3B1A3BO i i i l V V V V 4bit adder lt 0 R7 R6 R5 R4 R3 Note We have considered four different scales or levels of detail in discussing the design of digital systems 1 Block Diagrams This is the level at which systems designers develop complex systems as interconnected blocks for example a binary multiplier as a connection of 4bit adders blocks a 4bit adder as a connection of full adder blocks or a full adder as a connection of half adder blocks Example Full adder block diagram Ai 3 HA I HA 77 gt s i gt Ci1 2 Logic dates OR AND NAND etc This is the level that we use in designing logic circuits to perform desired operations Example NAND gate implementation of half adder block 3 C 30 y 3 Transistor level This is the level that shows how physical devices transistors are connected to form logic gates Example CMOS NAND gate 2 y may 4 Semiconductor level This is the level at which transistors and other devices are actually constructed using semiconductors and metal depos s Example NMOS transistor construction Polysilicon psuhstrate Electrical and computer systems engineers work at each of these different levels to design the systems that we need ENGIN 112 Intro to Electrical and Computer Engineering Lecture 32 Hazards 39 ELECTRICAL gt9 E N GIN E E RI N G UNIVERSITY OF MASSACHUSETTS ENGN11Z L32 Hazards Nnvemher192 3 Overview Minimum sum of products implementation reduces cos s Propagation delays in circuits can lead to output glitches Hazards can be determined from Kmap Technique using Kmaps to avoid hazards Look for neighboring circles Hazards are less of a concern for sequential circuits Combinational outputs settle prior to rising clock edge ENGN112 L32 Hazards November 19 2003 Combinational Delay Logic gates do not produce an output simultaneously with a change In Input There is a finite propagation delay through all gates input output input output time propagation delay ENGN112 L32 Hazards November 19 2003 Example of Combinational Hazards Eg Q AB BD if B amp D are 1 then Qshould be 1 but because of ropagation dela s if B changes state then Q wil become unstab e for a short time as follows A C 4lgt0 13 Q D A High D High B C I Q glitch ENGN112 L32 Hazards November 19 2003 HazardsGlitches Hazardsglitches unwanted switching at the outputs Occur when different paths through circuit have different propagation delays Dangerous if logic causes an action while output is unstable May need to guarantee absence of glitches Usual solutions 1 Wait until signals are stable by using a clock preferable easiest to design when there is a clock synchronous design 2 Design hazardfree circuits ENGN112 L32 Hazards November 19 2003 Types of Hazards Static 1hazard Input change causes output to go from 1 to 0 to 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 Static Ohazard Input change causes output to go from 0 to 1 to 0 Dynamic hazards Input change causes a double change from0to1toOto1ORfrom1toOto1toO ENGIN112 L32 Hazards November 19 2003 Hazard Elimination Hazards like these are best eliminated ogicay The Karnaugh Map of the required functlon glves one method D Ii 00 01 11 10 0 0 0 0 N o BD AD AB Covering the hazard causin the transition with a redundant product term AD will eliminate the hazard The hazard free oolean equation is Q AB BDAD ENGN112 L32 Hazards November 19 2003 Static Hazards Due to a literal and its complement momentarily taking on the same value Thru different paths with different delays and reconverging May cause an output that should have stayed at the same value to momentarily take on the wrong value Example A B s l s F s39 m T hazard static0 hazard static1 hazard ENGN112 L32 Hazards November 19 2003 Dynamic Hazards Due to the same versions of a literal taking on opposite values Thru different paths with different delays and reconverging May cause an output that was to change value to change 3 times instead of once Example A c A 3 F Bl B 2 32 1 B3 c ILl l dynamic hazards ENGN112 L32 Hazards November 19 2003 hazard Hazard Example 0 Logic gates do not produce anoutput simultaneously WIth a change In Input 0 There is a finite propagation delay through all gates a AND OR circuit b NAND circuit Fig 9 33 Circuits with Hazards ENGN112 L32 Hazards November 19 2003 Hazard Removal for Static 0 Locate boundaries between circles Add an extra circle product term to eliminate hazard Note addition of term does not lead to minimum sum of products implementation XZX3 XZX3 00 01 11 10 aYx1x2x 2x3 bYx1x2x 2x3x1x3 Fig 9 35 Maps Demonstrating a Hazard and its Removal ENGIN112 L32 Hazards November 19 2003 Hazard Removal Result Addition of extra AND gate and extra OR gate input 0 Generally does not slow down circuit 0 Not as important for sequential circuits X1 9 Fig 9 36 Hazard Free Circuit ENGN112 L32 Hazards November 19 2003 Summary When inputs change intermediate values created Could lead to incorrect circuit behavior Hazards can be determined from Kmap Technique using Kmaps to avoid hazards Use additional implicants Hazards not as important for sequential design Hazard removal requires additional hardware ENGN112 L32 Hazards November 19 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 5 Boolean Algebra 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z L5 Ennlezn Algebra Septemh2r1ZZ 3 Overview Logic functions with 1 s and 0 s Building digital circuitry Truth tables Logic symbols and waveforms Boolean algebra Properties of Boolean Algebra Reducing functions Transforming functions ENGN112 L5 Boolean Algebra September 12 2003 Digital Systems 0 Analysis problem Inputs Outputs Determine binary outputs for each combination of inputs Design problem given a task develop a circuit that accompllshes the task Many possible implementation Try to develop best circuit based on some criterion size power performance etc ENGN112 L5 Boolean Algebra September 12 2003 Toll Booth Controller Consider the design of a toll booth controller Inputs quarter car sensor Outputs gate lift signal gate close signal 25 Car Raise gate Close gate If driver pitches in quarter raise gate When car has cleared gate close gate ENGN112 L5 Boolean Algebra September 12 2003 Describing Circuit Functionality Inverter Truth Table A Y A igt0 Y 0 1 1 0 Symbol Input Output Basic logic functions have symbols The same functionality can be represented with truth tables Truth table completely specifies outputs for all input combinations The above circuit is an inverter An input of 0 is inverted to a 1 An input of 1 is inverted to a 0 ENGN112 L5 Boolean Algebra September 12 2003 The AND Gate A a B Y This is an AND gate So if the two inputs signals Truth Table are asserted high the output will also be asserted Otherwise the output will be deasserted low ENGN112 L5 Boolean Algebra September 12 2003 The OR Gate B This is an OR gate So if either of the two input signals are asserted or both of them are the output will be asserted ENGN112 L5 Boolean Algebra September 12 2003 Describing Circuit Functionality Waveforms x 0 1 1 0 0 AND Gate y 0 0 1 1 0 AND2X y 0 0 1 0 0 ORZx y 0 1 1 1 0 NOsz 1 0 0 1 1 Fig 1 5 Input output signals for gates Waveforms provide another approach for representing functionality Values are either high logic 1 or low logic 0 Can you create a truth table from the waveforms ENGN112 L5 Boolean Algebra September 12 2003 Consider threeinput gates 3 Input OR Gate A XABC B C ENGN112 L5 E Output A B C XABC O 0 0 O 0 O 1 1 0 1 0 1 O 1 1 1 1 0 O 1 1 0 1 1 1 1 O 1 1 1 1 1 Ordering Boolean Functions How to interpret AoBC Is it AoB ORed with c Is it A ANDed with BC Order of Igrecedence for Boolean algebra AND before 0 Note that parentheses are needed here A AB B XABC oo ENGN112 L5 Boulean Algema ocylclllucl m 2003 Boolean Algebra A Boolean algebra is defined as a closed a ebraic system containing a set K or two or more e ements and the two operators and Useful for identifying and minimizing circuit functionality Identity elements a0a a 1 a 0 is the identity element for the operation 1 is the identity element for the operation ENGN112 L5 Boolean Algebra September 12 2003 Commutativity and Associativity of the Operators The Commutative Property For every aand b in K abba abba The Associative Property For every a b and c in K abcabc abcabc ENGN112 L5 Boolean Algebra September 12 2003 Distributivity of the Operators and Complements The Distributive Property For every a b and c in K abcabac abcabac The Existence of the Complement For every a in K there exists a unique element called a complement of a such that ad1 ad0 To simglitxl notation the o erator is frequently omitte hen two elemen s are written next to each other the AND operator is implied abcabLac abcabXac ENGN112 L5 Boolean Algebra September 12 2003 Duality The princi e of duality is an important conce t This says hat if an expression Is valid in Boo ean algebra the dual of that expression is also valid To form the dual of an expression replace all operators With operators all operators wuth operators all ones With zeros and all zeros wuth ones Form the dual of the expression a bc a ba c Following the replacement rules abcabac Take care not to alter the location of the parentheses if they are present ENGN112 L5 Boolean Algebra September 12 2003 Involution This theorem states a a Remember that aa 0 and aa 1 Therefore a is the complement of a and a is also the complement of a As the complement of a is unique it follows that a a Taking the double inverse of a value will give the initial value ENGN112 L5 Boolean Algebra September 12 2003 Absorption This theorem states aaba aaba To prove the first half of this theorem aab a1ab a1b ab1 a1 aaba ENGN112 L5 Boolean Algebra September 12 2003 DeMorgan s Theorem A key theorem in simplifyinlgLBoolean a ebra expression is DeMorgan s eorem It s ates a b a b ab a b Complement the expression ab zx a and simplify abzX a a b zx a a b zX a a b z X a a b9Z9 X a a b z X a ENGN112 L5 Boolean Algebra September 12 2003 Summary Basic lo ic functions can be made from AND OR and NO invert functions The behavior of digital circuits can be represented with waveforms truth tables or symbols Primitive gates can be combined to form larger circuits Boolean algebra defines how binary variables can be combined Rules for associativity commutativity and distribution are similar to algebra DeMorgan s rules are important Will allow us to reduce circuit sizes ENGN112 L5 Boolean Algebra September 12 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 28 Timing Analysis 39 ELECTRICAL gt9 E N GIN E E RI N G UNIVERSITY OF MASSACHUSETTS ENGIN11Z LG Timing Analysis unvemher7znn3 Overview Circuits do not respond instantaneously to input changes Predictable delay in transferring inputs to outputs Propagation delay Sequential circuits require a periodic clock Goal analyze clock circuit to determine maximum clock frequency Requires analysis of paths from flipflop outputs to flipflop inputs Even after inputs change output si nal of circuit maintains orIginal output for short Ime Contamination delay ENGN112 L28 Timing Analysis November 7 2003 Sequential Circuits Sequential circuits can contain both combinational logic and edgetriggered flip flops t clock signal determines when data is stored in flip ops Goal How fast can the circuit operate MinimumclockperiodTn n Maximum clock frequency f max Maximum clock frequency is the inverse of the minimum clock period 1lein fmax CIOCk Penod 0mg M i i W ENGN112 L28 Timing Analysis November 7 2003 Combinational Logic Timing Inverter A tcd tppl I Combinational logic is made from electronic circuits An input change takes time to propagate to the output The output remains unchanged for a time period equal to the contamination delay tccl The new output value is guaranteed to valid after a time period equal to the propagation delay tpcl ENGN112 L28 Timing Analysis November 7 2003 Combinational Logic Timing XNOR Gate A 33gt 0 sh C gtltX XX tcd l lH 1de H l l The output is guaranteed to be stable with old value until the contamination delay Unknown values shown in waveforms as Xs The output is guaranteed to be stable with the new value after the propagation delay ENGN112 L28 Timing Analysis November 7 2003 Combinational Logic Timing complex circuits lpd f 12 Circuit X Gd ns Tpd 3ns T 1ns A 39 cd 0 C A B C T d 5ns B T 1ns Propagation delays are additive Locate the longest combination of tpd Contamination delays may not be additive Locate the shortest path of tcd Find propagation and contamination delay of new combined circuit ENGN112 L28 Timing Analysis November 7 2003 Clocked Device Contamination and Propagation Delay D Q 7 M D Clk Igt Q I fiequot tCIkQ Timing parameters for clocked devices are specified in relation to the clock input rising edge Output unchanged for a time period equal to the contamination delay tccl after the rising clock edge New output guaranteed valid after time equal to the propagation delay tckQ Follows rising clock edge ENGN112 L28 Timing Analysis November 7 2003 Clocked Devices Setup and Hold Times 5 th DQ rx D Clk gt I Q PW Timing parameters for clocked devices are specified in relation to the clock input rising edge D input must be valid at least ts setup time before the rising clock edge D input must be held steady th hold time after rising clock edge Setup and hold are input restrictions Failure to meet restrictions causes circuit to operate incorrectly ENGN112 L28 Timing Analysis November 7 2003 EdgeTriggered Flip Flop Timing D X X CLK T th hold time tS setup time The logic driving the flip flop must ensure that setup and hold are met Timing values tccl tpd tkQ tS th ENGN112 L28 Timing Analysis November 7 2003 Analyzing Sequential Circuits TCIkQ 5ns Tpd 5ns ICIkQ 5 n5 5 D X Comb Y D Q Logic D Q 2 FFA 39 FFB gt G gt CLK F F What is the minimum time between rising clock edges 0 Tmin TCIKQ FFA Tpd G T5 FFB Trace propagation delays from FFA to FFB Draw the waveforms F ENGN112 L28 Timing Analysis November 7 2003 Analyzing Sequential Circuits Tpd 4ns D Q 2 FFA CLK Fgt Tc39k39Q sns TCIkQ 4 ns T5 2 ns What is the minimum clock period Tmin of this circuit Hint evaluate all FF to FF paths Maximum clock frequency is 1Tmin ENGN112 L28 Timing Analysis November 7 2003 Analyzing Sequential Circuits Tpd 4ns D Q 2 FFA CLK Fgt Tpd 5ns Fgt Tc39k39Q 5ns TCIkQ 4 ns T 2 ns S 0 Path FFA t0 FFB 39 TCIkQFFA TpdH TSFFB 5ns 5ns 2ns 12ns Path FFB to FFB TCLKQFFB TpdF TPdH TsFFB 4ns 4ns 5ns 2ns ENGN112 L28 Timing Analysis November 7 2003 Analyzing Sequential Circuits Hold Time Violation Tcol 1ns Tcol 2ns Th 2 5 D Q FFA CLK Fgt One more issue make sure Y remains stable for hold time Th after rising clock edge Remember contamination delay ensures signal doesn t change How long before first change arrives at Y TcdFFA Tc G gt Th 1ns 2ns gt ns ENGN112 L28 Timing Analysis November 7 2003 Analyzing Sequential Circuits Hold Time Violations Tcol 1ns All Qaths must satisfy requirements D Q 2 FFA FFB gt Tcol 2ns gt CLK F F TC39D mg TCID 1 ns Th 2 ns Path FFA to FFB TCDFFA TCDH gt ThFFB 1 ns 2ns gt 2ns 0 Path FFB t0 FFB 39 TcpFFB TcpF TCdH gt ThFFB 1ns 1ns 2ns gt 2ns ENGN112 L28 Timing Analysis November 7 2003 Summary Maximum clock frequency is a fundamental parameter In sequential computer systems Possible to determined clock frequency from propagation delays and setup time The longest path determines the clock frequenct All flipflop to flipflop paths must be checked Hold time are satisfied by examining contamination delays The shortest contamination delay path determines if hold times are met Check handout for more details and examples ENGN112 L28 Timing Analysis November 7 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 1 3 Combinational Design Procedure 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGN11Z L13 Cnmhinminnzl Dvsign Prncedure 0dnher12 3 Overview Design digital circuit from specification Digital inputs and outputs known Need to determine logic that can transform data Start in truth table form Create Kmap for each output based on function of inputs Determine minimized sumofproduct representation Draw circuit diagram ENGN112 L13 Combinational Design Procedure October 1 2003 Design Procedure Mano Design a circuit from a specification 1 Determine number of required inputs and outputs 2 Derive truth table 3 Obtain simplified Boolean functions 4 Draw logic diagram and verify correctness ABCLS 00000 00101 SABC 01001 RABC 01101 10001 10101 11001 11111 ENGN112 L13 Combinational Design Procedure October 1 2003 Previously we have learned 0 Boolean algebra can be used to simplify expressmns but not obVIous how to proceed at each step or if solution reached is minimal 0 Have seen five ways to represent a function Boolean expression truth table logic circuit mintermsmaxterms Karnaugh map ENGN112 L13 Combinational Design Procedure October 1 2003 Combinational logic design Use multiple representations of logic functions Use graphical representation to assist in simplification of function Use concept of don t care conditions Example encoding BCD to seven segment display Similar to approach used by designers in the field ENGN112 L13 Combinational Design Procedure October 1 2003 BCD to Seven Segment Display Used to display binary coded decimal BCD numbers using seven illuminated segments BCD uses 0 s and 1 s to represent decimal digits 0 9 Need four bits to represent required 10 digits Binary coded decimal BCD represents each decimal digit with four bits 0 0000 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 ENGN112 L13 Combinational Design Procedure October 1 2003 BCD to seven segment display List the segments that should be illuminated for each digit abcdef bc abdeg abcdg bcfg acdfg quot acdefg abc abcdefg abcdfg 0010UlIgtUJNl O ENGN112 L13 Combinational Design Procedure October 1 2003 BCD to seven segment display Derive the truth table for the circuit Each output column in one circuit Dec W 0 0 1 0 2 0 7 0 8 1 9 1 ENGN112 L13 Combinational Design Procedure Inputs X 0 0 0 Oi i Y 0 0 1 Oi ON iA i iOi m Outputs HHi tc C i ain tQ 1 1 0 A i O October 1 2003 i ain ka BCD to seven segment display Find minimal sumofproducts representation for each output For segment a yz W 00 01 11 10 Note Have only 00 1 0 1 1 lled in ten 01 0 1 1 1 squares corresponding to 11 the ten numerical 10 1 1 digits we Wish to represent ENGN112 L13 Combinational Design Procedure October 1 2003 Don t care conditions BCD display Fill in don t cares for undefined outputs Note that these combinations of inputs should never happen Leads to a reduced implementation For segment a yz 00 01 11 10 WX 00 01 11 10 ENGN112 L13 Combinational Design Procedure 1 O 1 O i x 1 X X 1 gtltgtlt Put in don t care and interpret as either 1 or O as desired October 1 2003 Don t care conditions BCD display Circle biggest group of 1 s and Don t Cares Leads to a reduced implementation CC 939 For segment a yz WX 00 01 11 10 00 1 0 01 O 1 11 X X 10 1 1 ENGN112 L13 Combinational Design Procedure October 1 2003 Don t care conditions BCD display Circle biggest group of 1 s and Don t Cares Leads to a reduced implementation CC 939 For segment a yz 00 01 11 10 1 1 00 O 1 F 010 1 1 1 11 X X 10 1 1 WX gtltgtlt gtlt ENGN112 L13 Combinational Design Procedure October 1 2003 Don t care conditions BCD display Circle biggest group of 1 s and Don t Cares All 1 s should be covered by at least one implicant CC 939 For segment a YZ yz wx 00 01 11 10 W 00 01 11 10 001 O 1 1 001 0 1 1 01 O 1 1 1 01 0 1 1 1 11 X X X X 11 X X X X 101 X X 10 1 1 X X F262 Fa4XZ ENGN112 L13 Combinational Design Procedure October 1 2003 Don t care conditions BCD display Put all the terms together Generate the circuit C 939 For segment a Z wx yOO 011110 F yw 2xz 00 1 0 1 1 01 0 1 1 1 11 X X X X 10 1 1 X X ENGN112 L13 Combinational Design Procedure October 1 2003 Example of seven segment display decoding Col to reset counter to Zero after 9 wt Decoded seven segment otsotay Segment 5 of segment otsotay Logtc oot to decode segment a as per notes Hmt Seteot a component and tnen ousn 7 from mam menu bar to get We on wnat tnat oomoonent does and now t We ENGN11Z L13 Cnmhinminnzl Dvsign Prncedure O nher 1 znna BCD to seven segment display Derive the truth table for the circuit Each output column in one circuit Dec W 0 0 1 0 2 0 7 0 8 1 9 1 ENGN112 L13 Combinational Design Procedure Inputs X 0 0 0 Oi i Y 0 0 1 Oi ON iA i iOi m Outputs HHi tc C i ain tQ 1 1 0 A i O October 1 2003 i ain ka BCD to seven segment display Find minimal sumofproducts representation for each output For segment b yz WX 00 01 11 10 See if you 00 1 1 1 1 complete this 01 1 o 1 0 example 11 1011 ENGN112 L13 Combinational Design Procedure October 1 2003 Summary 0 Need to formulate circuits from problem descriptions 1 2 3 4 Determine number of inputs and outputs Determine truth table format Determine Kmap Determine minimal SOP 0 There may be multiple outputs per design 0 Solve each output separately 0 Current approach doesn t have memory 0 This will be covered next week ENGN112 L13 Combinational Design Procedure October 1 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 33 Arithmetic Logic Unit ALU quot ELECTRICAL wquot ENGINEERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L33 Arilhmelic Lngic Llnils NnvemherZLZ Overview Main computation unit in most computer systems ALUs perform a vaiety of different functions Add subtract OR AND Example ALU chip 74LS382 Has data and control inputs KildliJvidual chips can be chained together to make larger s ALUs are important parts of datapaths ROMs often are usd in the control path Build a data and control path ENGN112 L33 Arithmetic Logic Units November 21 2003 ROMbased Moore Machine Timing What is the maximum clock frequency of this circuit Does this circuit satisfy hold time constraints ENGN112 L33 Arithmetic Logic Units November 21 2003 Arithmetic Logic Unit Arithmetic logic unit DataA DataB functions Two multibit data inputs Function indicates action Fumtioquot eg add subtract OR cond39tlons DataOut is same bit width as multibit inputs DataA and DataB Think of ALU as a number of other ALU is combinational arithmetic and logic blocks in a single box Function selects the block DataOut Conditions indicate special conditions of arithmetic activity eg overflow ENGN112 L33 Arithmetic Logic Units November 21 2003 ALU Integrated Circuit Integrated circuit offtheshelf components Examine the functionality of this ALU chip Inputs Aa A A2 39 A1 Outputs A0 0 0 F3 F2 F 3 74L5382 F 2 B t31 74H0382 F0 B0 CN 39 CNA 52 o 8 S1 o OVR so ALU A 4bit input number F 4 bit output number B 4bit input number ON carry out of MSB position CN carry into LSB position OVH over ow indicator S 3bit operation select i1puts a Function Table 32 S1 so Operation Comments 0 o 0 CLEAR F3F2F1Fc 0000 O 0 1 B minus A O 1 0 A minus B N55ds 0 1 o 1 1 A plus 5 Needs cN o 1 0 0 A a B ExclusiveOR 1 0 1 A E OF 1 1 0 AB AND 1 1 1 PRESEF F3F2F1Fo 1111 Notes S inputs select operatic OVFi n 1 or signednumber overflow b Performs 8 functions Example Determine the 74HC382 ALU out uts for the following in uts SZS So010 A3 2A1A00100 B3BZB1B00 01 and cN1 Function code indicates subtract o1oo 0001 0011 Change the select code to 101 and repeat Function code indicates OR 0100 OR 0001 0101 Synchronize ALU with a clock Function gt Conditions DataOut ENGN112 L33 Arithmetic Logic Units November 21 2003 Expanding the ALU Multibit ALU created by connecting carry output of loworder chip to carry In of high order B7 56 B4 A7 A6 A5 A4 74HCSB2 74H0332 F OVR F F Notes 2 adds lower order bits 2ddj9i392 r rde39 WS EIght blt ALU formed from 2 fourbit ALUs ENGIN o7vnom 22 is emitoverch indicator Datapath components Tristate buffer n Out If Enable asserted Out In Otherwise Out openCircuit Enable Loadable register C Ik Load Data stored on rising edge if Load is asserted eg Load 1 ENGN112 L33 Arithmetic Logic Units November 21 2003 Computation in a Typical Computer Control logic often imglemented as a finite state machine Including R Ms Datapath contains blocks such as ALUs registers tri state buffers and RAMs In a processor chip often a 5 to 1 ratio of datapath to control logic mlm mullinth quotx unmn nits Control Datapath logic llinil mm lulpui gt mlnlh mm dam Fig 572 Control and Dalzlpalli Interaction ENGIN11Z L33 Arilhmelic Lngic Llnils NnvemherZL znna Using a Datapath ENGN112 L33 Arithmetic Logic Units Consider the following computation steps 1 2 3 ADD A B and put result in A Subtract A B and put result in B OR A B put result in A Repeat starting from step 1 l i Determine values for Function LoadA LoadB LoadA LoadB ALU Function gt November 21 2003 Modeling Control as a State Machine Consider the following computation steps 1 ADD A B and put result in A 2 Subtract A B and put result in B 3 OR A B put result in A Determ39 e va39ues for Function LoadA LoadB Repeat starting from step 1 Model control as a state machine Determine control outputs for each state ENGN112 L33 Arithmetic Logic Units November 21 2003 Modeling Control as a State Machine Consider the following computation steps 1 ADD A B and put result in A 2 Subtract A B and put result in B Eatzego 3 OR A B put result in A 31 01 Repeat starting from step 1 82 10 Present State Next State Function LoadA LoadB OO O1 011 1 0 O1 10 010 O 1 10 00 101 1 0 We know how to implement this using an SOP Can we use a ROM ENGN112 L33 Arithmetic Logic Units November 21 2003 ROM Implementation of State Machine Present State Next State 00 O1 01 1O 10 CD ROM 00 1001001 01 0010110 10 ENGN112 L33 Arithmetic Logic Units Function LoadA LoadB 1 O O 1 1 0 States SO 00 S1 01 82 10 Note No minimization One line in ROM for each state Function LoadA LoadB November 21 2003 Putting the Control and Datapath Together RCMM OO 01 1001001 0010110 Func on ENGN112 L33 Arithmetic Logic Units November 21 2003 What if we replaced the ROM with RAM RAM 0101110 00 Looks like software 1001001 01 0010110 10 PS NS LoadB LoadA Func on Possible to implement different functions Program the RAM to perform different sequences ENGN112 L33 Arithmetic Logic Units November 21 2003 Summary ALU circuit can perform many functions Combinational circuit ALU chips can be combined together to form larger ALU chips Remember to connect carry out to carry in ALUs form the basis of datapaths ROMS can form the basis of control paths Combine the two together to build a computing circuit Next time more data and control paths ENGN112 L33 Arithmetic Logic Units November 21 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lecture 37 Register Transfer Level 39 ELECTRICAL wquot EN GIN EERING UNIVERSITY OF MASSACHUSETTS ENGIN11Z L37 Register Transler Level Decemh2r32 3 Overview System design must be modular Easier to represent designs with systemlevel blocks Register transfer level represents transfers between clocked system registers Shifts arithmetic logic etc Algorithmic state machine Alternate approach to representing state machines Status signals from datapath used for control path Algorithmic state machine chart shows flow of computation ENGN112 L37 Register Transfer Level December 3 2003 Systemlevel Design Difficult to represent a design with just one state machine A series of control and data paths used to build computer systems Helps simplify design and allow for design changes ENGN112 L37 Register Transfer Level December 3 2003 Registers and Data Operations Activity and performance in computers defined on reglstertoregIster paths Digital system at register transfer level specified by three components The set of registers in the system Operations to be performed on registers Control that is applied to registers and sequence of operations gt Function ENGN112 L37 Register Transfer Level December 3 2003 Representation of Register Transfer Flow Arrow indicates transfer from one register to another R2 2 R1 Conditional statements can help in selection lfT1 1then R2 R1 Clock si nal is not generally included in register transfer evel statement Sequential behavior is implied Multiple choices also possible lfT1 1then R2 2 R1 R2 2 R2 How could these statements be implemented in hardware ENGN112 L37 Register Transfer Level December 3 2003 Other representative RTL operations Addition R1 R1 R2 Increment R3 R3 1 Shift right R4 R4 Clear R5 0 Transfer doesn39t change value of data begin moved How could these statements be implemented in hardware ENGN112 L37 Register Transfer Level December 3 2003 Algorithmic State Machines ASM Flowchart specifies a sequence of procedural steps and decision steps for a state machine Translates word description into a series of operations with conditions for execution Allows for detailed description of control and datapath Status conditions Commands Control Datapath loglc External Input Output gt gt gt inputs data data Fig 8 2 Control and Datapath Interaction ENGN112 L37 Register Transfer Level December 3 2003 Algorithmic State Machines State Box ASM describes o eration of a sequential curcuu ASM contains three basic N l Bingry T i on elements we CO 6 Re istero eration R 0 State box gorougjm STXRT Decision box Condition box l l o M a General description b Specific example state Box also indicates operation to be performed Fig 8 3 State BOX Binary code and state name also included ENGN112 L37 Register Transfer Level December 3 2003 Decision Box Describes the impact of input on control system Contains two exit paths which indicate result of condition More complicated conditions possible Implemented in hardware with a magnitude comparator Exit path Exit path Fig 8 4 Decision Box ENGN112 L37 Register Transfer Level December 3 2003 Conditional Box 0 O From exit path of decision box i Register operation or output a General description Indicates assignments following a decision box Generally indicates data transfer T1 001 T211010 b Example With conditional box Fig 8 5 Conditional Box ENGN112 L37 Register Transfer Level December 3 2003 ASM Block O Paths exist between state boxes 0 Each state box equivalent to one state Fig 8 6 ASM Block ENGIN112 L37 Register Transfer Level December 3 2003 ASM Block 0 Equivalent to State Diagram Fig 8 7 State Diagram Equivalent to the ASM Chart of Fig 8 6 Fig 8 6 ASM Block ENGN112 L37 Register Transfer Level December 3 2003 Concept of the State Machine Example Odd Parity Checker Assert output whenever input bit stream has odd of 139s gset Present State In ut Next State Out ut 0 0 Even 1 Odd 0 1 1 1 Symbolic State Transition Table 0 Present State In ut Next State Out ut 0 0 0 0 0 1 1 0 1 0 1 1 State 1 1 o 1 Diagram Encoded State Transition Table 0 Note Present state and output are the same value Moore machine ENGN112 L37 Register Transfer Level December 3 2003 ASM for Odd Parity Checker Example Odd Parity Checker Assert output whenever input bit stream has odd of 139s gset 0 1 State Diagram 1 ENGN112 L37 Register Transfer Level December 3 2003 Verilog Representation for RTL Conditional assignment statements assign Y S 10 Statement evaluation always l1 or l2 or S if S Y l1 else Y l0 Perform evaluation only when an input changes always posedge clk q d Verilog description of a flip flop ENGN112 L37 Register Transfer Level December 3 2003 Typical Design Flow Fig 8 1 Process of HDL Simulation and Synthesis o I I I I It all starts WIth Verllog descrlptlon gt HDL description Valld Synthesis Nethst gt Of design design tools I V Simulate Simulate 4 Test bench gt RTL 163191 gate level design l Result Result Good Good Needs Needs correction correction V V Compare Fabricate No match Match IC Summary Register transfer level provides a simple way to descrIbe deSIgns A series of operations take place between registers Algorithmic state machine another way to represent a state machine Direct correspondence between state diagram and algorithmic state machine Possible to implement state machines in Verilog Also in VHDL Next time programmable array logic ENGN112 L37 Register Transfer Level December 3 2003 ENGIN 112 Intro to Electrical and Computer Engineering Lectu re 23 Finite State Machine Design Procedure 39 ELECTRICAL 9 quot EN GINEERING UNIVERSITY OF MASSACHLlSETI39S ENGN11Z L23 Finile Sim Machine Design Prncedure omnher27znn3 Overview Desi n ofsystems that input flip flops and com InatIonal logic Specifications start with a word description Create a state table to indicate next states Convert net states and outputs to output and flip flop InputequaUOns Reduce logic expressions using truth tables Draw resulting circuits Lots of opportunities for interesting design ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Concept of the State Machine Computer Hardware Datapath Control g zualifier8 Registers FSM generating sequences Combinational Functional of control signals Units eg ALU Instructs datapath what to Busses do next Control Qualifiers Control and Signal Inputs Outputs ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Designing Finite State Machines Specify the problem with words eg Design a circuit that detects three consecutive 1 inputs 0 Assign binary values to states Develop a state table Use Kmaps to simplify expressions Flip flop input equations and output equations Create appropriate logic diagram Should include combinational logic and flip flops ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Example Detect 3 Consecutive 1 inputs quot State S0 zero 1s detected 39 State S1 one 1 detected State S2 two 1s detected State S3 three 1s detected Fig 5 24 State Diagram for Sequence Detector Note that each state has 2 output arrows Two bits needed to encode state ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2 03 State Table for Sequence Detector Present Next Se uence of outputs inputs State Input State Output an flip flop states enumerated A B X A B y In state table 0 0 0 0 0 0 Present state indicates current 0 o 1 o 1 0 value of flip flops 0 1 0 0 0 0 o 0 1 1 1 0 0 Next state Indicates state after 1 0 0 0 0 0 next rising clock edge 1 0 1 1 1 0 Output is output value on 1 1 0 0 0 1 current clock edge 1 1 1 1 1 1 ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Finding Expressions for Next State and Output Value Create Kmap directly from state table 3 columns 3 Kmaps Minimize Kmaps to find SOP representations Separate circuit for each next state and output value Bx 0 0 0 1 11 10 DAAxBx DBAxB39x yAB Fig 5 25 Maps for Sequence Detector ENGN112 L23 Finite State Machine Design Procedure October 27 2003 O O 0 Circuit for Consecutive 1s Detector x D Note location of state flip flops Output value y is function of state This is a Moore machine CLK Fig 5 26 Logic Diagram of Sequence Detector ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 DEDJ D Concept of the State Machine Example Odd Parity Checker Assert output whenever input bit stream has odd of 139s gset Present State In ut Next State Out ut 0 0 Even 1 Odd 0 1 1 1 Symbolic State Transition Table 0 Present State In ut Next State Out ut 0 0 0 0 0 1 1 0 1 0 1 1 State 1 1 o 1 Diagram Encoded State Transition Table 0 Note Present state and output are the same value Moore machine ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Concept of the State Machine Example Odd Parity Checker Next StateOutput Functions NS PS xor Pl OUT PS 5M Input D CLK Q PSOutput I39L39 gt R Q Reset 1 D FF Implementation ll Input 1 O O 1 1 O 1 O 1 1 1 O Output111011001011 Timing Behavior Input 1 0 01 1 0 1 01 1 1 0 ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Mealy and Moore Machines Solution 2 Moore Solution 1 Mealy 0 00 Reset Input Output OP is dependent 10 ll on current state and 1In ut Output input in Mealy p Transition Output is Arc dependent only 01 on current state Mealy Machine Output is associated With the State transition Moore Machine Output 1s ass001ated Appears before the state transition is Wlth the State Appears after the state trans1t10n completed by the next clock pulse takes place ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Vending Machine FSM Step 1 Specify the problem EIDeliver package of gum after 15 cents deposited EISingle coin slot for dimes nickels EINo change EIDesign the FSM using combinational logic and flip flops N Coin Vending sensor D gt Machine Reset FSM Open Clk ENGN112 L23 Finite State Machine Design Procedure Gum Release Mechanism October 27 2003 Vending Machine FSM State Diagram Raw Present Inputs Next Output 6 State D N State Open o o o o o N o 1 5 o a D 1 0 10 o 1 1 x x 5 o o 5 o o 1 10 o D 6 1 0 15 o 1 1 x x 10 o 0 10 0 15 0 1 15 0 open 1 0 15 o 1 1 x x Reuse states I 15 X X 15 1 whenever ossible p 39 Symbollc State Table ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Vending Machine FSM State ENCOdan How many flipflops are needed Present State Inputs Next State Output Q1 Q0 D N D1 D0 Open 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 X X X 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 X X X 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 X X X 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 X X X ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Vending Machine FSM Determine FF implementation Q1 Q1 man man D on m 11 111 D 01101 1111 on n n 1 1 on n 1 1 0 m a 11 1 N m 1 n 1 i 11 X xx x 11 x x x 1m 1 1 1 1 1n n 1 1 a39o 39 ao 39 Kmap for D1 Kmap for DO ENGN11Z L23 Finile Slate Machine Design Prncedure omnherzmnna Minimized Implementation Q1 70 CO is N Reset OPEN OW Q1 D Vending machine FSM implementation based on D flipflopsMoore ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003 Summary Finite state machines form the basis of many digital systems Designs often start from clear specifications Develop state diagram and state table Optimize using combinational design techniques Mealy or Moore implementations possible Can model approach using HDL ENGN112 L23 Finite State Machine Design Procedure OCtOber 27 2003