### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computer Architecture CPSC 5155G

GPA 3.91

### View Full Document

## 55

## 0

## Popular in Course

## Popular in ComputerScienence

This 39 page Class Notes was uploaded by Earlene Cremin III on Sunday October 11, 2015. The Class Notes belongs to CPSC 5155G at Columbus State University taught by Edward Bosworth in Fall. Since its upload, it has received 55 views. For similar materials see /class/221207/cpsc-5155g-columbus-state-university in ComputerScienence at Columbus State University.

## Similar to CPSC 5155G at

## Popular in ComputerScienence

## Reviews for Computer Architecture

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/11/15

Chapter 7 Analysis and Design of Sequential Circuits Chapter Overview Up to this point we have considered two types of circuits the basic set of combinational circuits and the simple sequential circuits called ip ops This chapter will discuss more complex sequential circuits fabricated from these basic elements We have seen the four basic types of ip ops We now use them in design problems Chapter Assumptions Again the presumption is that the student is familiar with Boolean logic and basic combinational circuitry Although many students will have had a previous introduction to ip ops no familiarity with the devices is assumed Int 39 quot to S quot 39 Circuits We have spent some time considering combinational circuits Combinational circuits are the basis of all digital devices yet they do not suffice for any but the simplest devices The one significant weakness of combinational circuits is that they do not have memory The inadequacy of pure combinational logic can be illustrated by considering a simple device 7 the soft drink machines in every campus building Currently the price of a soft drink is 090 A machine controlled by only combinational logic would have 2 options 1 If a dollar bill or dollar coin is inserted return a drink and 010 in change 2 If a smaller coin is inserted return the coin and indicate that it is not big enough Clearly the behavior of the combinational logic soft drink machine is not acceptable One expects the machine to have a memory to store the amount of money to be applied to the next purchase What we want is for the soft drink machine to be controlled by sequential logic specifically by a FSM Finite State Machine In this example the SDM Soft Drink Machine is initialized to a state called 0 7 there has been no money deposited for a drink When one places a quarter into the machine it enters a state called 25 7 there has been 025 deposited In state 25 the machine waits for a money deposit in excess of 065 total before it will dispense a drink and possibly change If the SDM accepts nickels dimes quarters and dollar coins it is easy to show that the number of states is finite 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 and 100 7 atotal of 21 states Finite state machines are studied in most courses in computer architecture We note in passing that all stored program computers are theoretically nite state machines although it is not profitable to view them as such Consider a computer with 64 KB of memory 7 an extremely small value This corresponds to 512K bits 524 288 bits The memory alone of such a computer is a FSM with 2524288 m 25010157826 states 7 that is a 25 followed by 157285 zeroes We might as well call that an infinite number Page 1 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis andDeslgn of Sequentaal circuits terms 39 delayed for some amount oftrme and then fed back as input to the circuit engineering discipline but most of us will prefer to think of memory as bit boxesquot 7 stor containers thathold one bit of binary information These brtbones ealled ip ops were discussedln the previous chapter circuits and sequentaal erreurts Cnmhinztinnal Circuits Segusntial Circuits No Memory Mem ory No ip ops Fllpr ops may be used only eombrnataonal gates Combinataonal gates may be used No feedback Feedback is allowed Output for aglven set of The order oflnput ehange Inputs is independent of is quite important and may order in which these inputs produce signi cant differences were ehanged alter output output stabilizes in the The following gure shows away to eonsrder sequential erreurts Cnmhinztinnal Lngic AND OR NOT gates and any MSI circuits suale incrncluces a time lay The memnry state dues nnt change instantly Figure Sequential Lngic Includes Cnmhinztinnal Lngic and Msmnry Sequential circuits can be eharaetenzedrnto two broad elasses e synchronous and asynchronous As ageneral rule asyneh onous circuits are faster butmueh harder to design We shall focus totally on synehronous erreurts Page 2 of 28 LastReyrsed on July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits By QT we denote the state of a sequential circuit at time T 7 this is basically its memory We watch the state of the circuit change from QT to QT l as the clock ticks The constraint on synchronous circuits is that the state of the circuit changes after the input thus we have a typical sequence as follows 1 At time T we have input denoted by X and state QT 2 As a result of the input X and state QT a new state is computed This becomes available to the input only at time T l and so is called QT l The fact that the new state computed as a result of X and QT is not available to the input of the sequential circuit until the next time step greatly facilitates the design and analysis of the speci c circuit We do not have endless feedback loops to worry about We shall consider two N 39 to J J39 quot 39 circuits 1 Analysis of sequential circuits 2 Design synthesis of sequential circuits Circuit analysis begins with a circuit diagram or a black box and ends with an identi cation of the sequential circuit implemented by the device 7 normally a truth table The steps are 1 Identify the inputs and the outputs 2 Express each output as a Boolean function of the inputs and the present state QT 3 Identify the circuit if possible Circuit design begins with a complete description of the circuit and ends with a design Introduction to Finite State Machines gFS 31 Strictly speaking a nite state machine FSM is a device that can exist in one of a nite number of states Associated with an FSM is a memory that is used to store an identi er of the state so that the machine may process its input if any and move to the next state Due to this coincidence nite state machines are often studied in conjunction with ip ops We are all familiar with nite state machines although we rarely think of them as such Consider a washing machine The states for this machine are off ll with water wash spin and rinse The control unit for the FSM is the knob on the washer that we turn to start it A traf c light is also a nite state machine We normally think of a traf c light as having only three states Green Yellow and Red The truth is a bit more complex in that the physical unit must display at least two sets of lights one for each intersecting street Nevertheless a standard traf c light can be modeled with no more than eight states although the introduction of advanced green lights and turn signals complicates things a bit A standard digital clock that displays only hour minute and second can be said to have 24 o 60 o 60 86400 states 7 still a nite number Normally the FSM construct is used to model systems with far fewer states in our work we shall normally limit a FSM to either eight or sixteen states that is N S 23 or N S 24 Page 3 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Ana1ysrs andDesrgn of Sequenua1 Crreurts state diagram The followmg 15 a state dAagram for a erreurt ea11ed a sequence deteetor For a 11011 A L states beeause rtrs deteeung a verbxt sequence Figure State Diagram fur a 11011 Sequence Deteetnr 1n terrns of dASErete rnathernaues rtrs a duected graph wrth1oops Thus rt 15 not a srrnp1e graph 1n srrnp1e graphs ares do not eonneet avertex wrth xtself 2 of e o FS aeung to rnput by movmg between states and produerng output In the XZ labelmg seherne er the b1narymput0 or 1andZ1s the bmary output ssoerated wrth the transrtrons Not all FSM have output ted wrth the transruons between states Ihrs one does 4 TM wd H mm 1 3H 5 E p E dependmg on the xpr ops usedto rrnp1ernent the erreurt Not all nrte state rnaehrnes have sueh complex state dAagrams The gure at leftxs the state dAagram for arnoduloA uprcounter Itjust eounts 0 1 2 3 andrepeats ont ountrn rno u o e rnuanye gup d 1 4 There 15 no rnput other than e1o we a1rn stne tr and no output duecdy assoerated wrth the transrtrons For thr fFSM th trs assoerated wrth the st Figure State Diagram fur a Marblan UprCnlInter LastRevrsed on July 20 2010 Page 4 of 28 Copynght 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Many mathematical models of FSM focus on the state diagram For most of our work it is more convenient to work with the state table of the FSM a tabular representation of the state diagram Translation between the state diagram and state table is automatic The state table presents the data in terms of present state QT and next state QTl using the labeling that most naturally ts the problem Here are the state tables for the two FSM above Note that eh state table contains exactly the same information as the state diagram Present State Next State Figure State Table for 11011 Sequence Detector Showing Output Figure State Table for a Modulo Four Up Counter One notes immediately that the second state table is simpler than the rst this is expected it represents a simpler state diagram Speci cally there is no input so there is only one column for the next state In general for K inputs there are 2K next state columns in the table Another tool in the design and analysis of sequential circuits is the transition table It contains the same information as the state table except that all labels have been replaced by binary numbers There are many creative ways to assign binary numbers to state labels here we just do the obvious For the sequence detector let A 000 B 001 C 010 D 011 and E 100 as there are ve states The following is the sequence detector transition table D011 000 0 100 0 Figure TransitionOutput Table for the 11011 Sequence Detector Page 5 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits What we have in the above gure is a special type of truth table We shall now investigate the table in a bit more detail Note that the state of the machine is represented by a 3bit binary number We shall use the notation YzYlYo for that number Given this notation we write the table as shown below Figure The TransitionOutput Table as a Modi ed Truth Table The table above can be viewed as a truth table that has been folded over Another way to represent this table is as a standard truth table depending on Y2 Y1 Y0 and X Figure The TransitionOutput Table as a Standard Truth Table Students are invited to use either form of the transition output table that suit them This instructor prefers to use the foldedover version but that is not necessary We now have three equivalent representations of a FSM l the state diagram 2 the state table and 3 the transitionoutput table probably not a standard name As we shall soon see a full design or analysis uses a few additional tables but the three given above suffice to understand the finite state machines Page 6 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysls andDeslgn of Sequenual ctreutts CIrElII rnr Analysts We ftrst study the analysts of dtgttal etreutts then we study thetr deslgn There are anurnber o steps tn analysts ofa etreutt Where to begm depends on what one has When gtyen a etreutt dlagram the followlng steps are usedto begm the analysts l 2 Deterrntne the tnputs and outputs of the lpr ops 3 Con truet the Next State and OutputTables 4 Construet the State Dtagrarn 5 prosslble ldennfy the etreutt There are no goodrules forthts step Constder the followtng etreutt We want to dtseoverwhattt does X 1 Figure Circuittn Be Analyled Step 1 Identity and Label the Inputs Outputs and Internal States We use the followlng varlables tn the analysts othls etreutt wtth a smgle lpr op x denotes the tnput 1 denotes the output of the lpr op 139 also andz the output ofthe e eutt Ifwe hadrnore than one lpr op we wouldlabel the lpr op wtth anurn er begtnntng at 0 and use that as a subsenpt so lpr op 0 wouldhaye output Yn ete Step 2 Determine the Inputs and Outputs nrthe Flipr nps tttnut ndn h h n n wt the By tnspeeuon we deterrntne the followmg for the equattons DXY Step 3 Cnnstruetthe Next State and Output Tables deslgn p p Page7 of28 LastReytsedonJuly 20 2010 Copyrtght 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Noting that QT Y the state of a ip op is also its output we construct the following NextState diagram for the ip op based on the characteristic table of a D ip op and the equation we derived for the D input D X Y One simple caution here is that the input to a ip op is a function of the present state only having nothing to do with the next state as we have no crystal balls Thus Y QT Here is the present state PS next state NS diagram for the circuit The output table is similarly constructed using the equation Z X EB Y Z X EB QT Again note that the output is not a function of the next state These two tables are combined to form the transition output table At this point we should produce a state table in the standard format This involves assigning labels to each of the two states currently identified only as QT 0 and QT 1 For lack of anything more imaginative we label the states 0 and l Figure State Table for Circuit to be Analyzed Page 8 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Aha1ysrs audDesrgh of Sequehua1 Crreurts Step 4 Cnnslnlct the State Diagram The ha1 step m the proeess may be the ereauoh othe state dJagram 10 Atthrs porht we have a eorhp1ete desehpuoh othe erreurt Itrhay be possrb1e to proeeed from thrs dJagram to obtarh an understandmg ofwhat the erreurt does Step 5 Hpussihle identify the circuit 0 from the start uhtxl a 1 15 mput at whxch ume 1ttransmohs to state 1 andremams there Luput QCT Output 0 0 0 For QCT 0 the output 15 x 1 0 1 0 1 1 For QCT the output 15 x39 1 1 0 A verbal A 1 H Mk V m 39 or m d the eorhp1erhehto ahurhber Frrst eohsrderahurhberehduhgrh 1 say x x 1 The ones eorhp1erhehto t1ushurhberrs xn39xner xa39xr390 Ad hg1tothrsproo1uees the numberxh39xhrr a Xr391rh whreh the 1east srgru eaut 1 15 eopred audthe temuha 51 he or more zeroes 1 erts 1east s t h a o rgru eautbrts are 10 0 where the eouht ofzeroes 15 hotrrhportaut The one39srcomple h of 15 number wru ehd wrth 01 w e a zero hgrha1 has turhedto a1 But 01 1 1 10 0 andup to the 1east sxgmfxcant 1 the two39 orhp1erhehtrs a eopy of the brts m the rhteger rtse1 Note that there 15 no earry out ofthe addmon that produeed the nghtrmost 1 so the remamder othe v t 1 t erreurt 1t 15 a seha1 two39srcomplementer Page 9 of 28 LastRevrsed or July 20 2010 Copyrrght 2005 by Ed Bosworth Chapter 7 Analysis andDeslgn of Sequenual cireuits Design at Seguen ial cireui s Having seen howto analyze digital eireuits we nowmyestigate howto design digital cults b At this level topies modulorNcounters and sequence deteetors Here is an oyeryiew of the design proeedure for a sequential eireuit nye the state agram and state table for the eireuit 2 Count the number of states in the state diagram eall it N and ealeulate the number of lpr ops needed eall it P by solving the equauon 2quotquot lt N 2quot This is best solved by guessing the value of 3 Assign a unique Prbltblnary number state yeetor to eaeh state he next statel e e output table 5 Separate the state transiuon table into P tables one for eaeh lpr op WARNJNG Thin s ean getmessy here neatness eounts 8 Denye the input equations for eaeh lpr op based as funeuons ofthe input lpr ops 9 Summarize the equauons by writing them in one plaee as the eireuit diagrams are hardto draw neatly Design Problem AModulo 4 Counter As ourfirst design problem let s eonsider amodulorfour eounter When the direetion is not speeified we usually intendto build amodulorfouruprcounter 0 1 2 3 0 1 2 3 ete We e ve Step 1 Derive the state diagram and state table fur the circuit Here is the state diagram Note thatitis quite simple andinyolyes no input Figure The State Diagram fur a Mnilulnat Up chunter Page 100f28 LastReyisedonJuly 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits The state table is simply a rearrangement of the state diagram into a tabular form Step 2Count the number of states in the state diagram call it N and calculate the number of ip ops needed call it P by solving the equation 21 1 lt N S 21 The number of states on a moduloN counter is simply N these are labeled 0 through N 7 1 Speci cally a modulo4 counter has four states labeled 0 l 2 and 3 We solve the equation 21quot1 lt 4 S 2P by noting that 21 2 and 22 4 so we have determined that 21 lt 4 S 22 hence P 2 We shall see later that there are valid solutions with more than two ip ops but there are none with fewer Step 3 Assign a unique P bit binary number state vector to each state Often the rst state 0 the next state 1 etc Some sequential circuits suggest an innovative numbering system but moduloN counters never do We go with the obvious labeling generated by assigning each decimal number its twobit binary equivalent as an unsigned integer in the range from 0 to 3 Step 4 Derive the state transition table and the output table There is no output table for any moduloN counter as the output associated with this type of table is the output on a transition as is seen in a sequence detector The transition table is a direct translation of the state table using the assignments from the previous step Page 11 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Step 5 Separate the state transition table into P tables one for each ip op Here we separate the state transition table into 2 tables one for each ip op Note that the ip ops will be numbered 0 and 1 with ip op 0 storing the least signi cant bit of the state information Thus we shall refer to the state information as Y1Y0 Present Next Present Next State Step 6 Decide on the types of ip ops to use When in doubt use all JK s Up to this point we have made no assumptions about the type of ip op to use In order to proceed any farther with the design we must now commit to a specific type In line with this author s preferences he chooses to use two JK ip ops The excitation table for a JK ip op is shown at right Recall that the d stands for Don t Care For example if we have QT 0 and want QT1 0 we can use either J 0 K 0 or J0K 1 SimilarlyeitherJ 1 andK00rJ 1 andK1 will take QT 0 to QT 1 1 Step 7 Derive the input table for each ip op using the excitation tables for the type First look at ip op 1 representing the highorder bit Note that we compare the present state of Y1 to its next state in order to determine J1 and K1 Note that in deciding on the input we must match only the 0 s and 1 s We ignore the don t cares Note that the d for don tcare is not a variable to be assigned a value It is a value that does not need to be matched At the moment Y0 is included in the table for future use only It plays no part in determining the values of J1 and K1 Page 12 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Here is the table for Y0 ll 0 Again Y1 is included in the table for future use only It plays no part in determining the values of Jo and K0 Step 8 Derive the input equations for each ip op based as functions of the input and current state of all ip ops At this point we try to derive an expression that matches each column Formal methods can be used but generally are more trouble than they are worth Here is this author s set of rules to match an expression to a given column If a column does not have a 0 in it match it to the constant value 1 If a column does not have a l in it match it to the constant value 0 2 If the column has both 0 s and 1 s in it try to match it to a single variable which must be part of the present state Only the 0 s and 1 s in a column must match the suggested function 3 If every 0 and l in the column is a mismatch match to the complement of a function 4 If all the above fails try for simple combinations of the present state Let s look at the input table for Y1 YY Y 11 0 Note that the column for J1 has a 0 and a l in it as does the column for K1 Each column has two don t cares in it but we ignore these Because each column has both a 0 and a l in it neither is a match for a constant function We now try to match J1 J1 does not match Y1 because Y1 is 0 in the same row 0 l as J1 is 1 J1 matches Y0 In row 0 0 both Y0 and J1 are 1 In row 01 both Y0 and J1 are 1 In rows 1 0 and l 1 J1 is a don t care so we do not need to match it Similar logic shows that K1 matches Y0 also Page 13 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits So now we have the following matches for J1 and K1 J1Y0 K1Y0 We now examine Y0 ll 0 1 Note that there are no 0 s in either the J 0 or K0 column The simplest and best match is J0landK0l Step 9 Summarize the equations by writing them in one place Here they are J1 Y0 K1 Y0 J0 1 K0 1 This is a counter so there is no Z output Step 10 Draw the circuit diagram J Yl JQIJQYO Clock 1 l Page 14 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Aha1ysrs audDesrgh of Sequehua1 Crreurts 1 w 11 m t followmg rhteresuhg property G1venth15we ear rep1aee eaeh J39K xpr op wrth aT xpr op arnvmg at thrs desrgh Y1 Clock The modu1oA counterjust desrghed outputs bmary eodes for the tame pu1ses Spem cally we assume that rt 15 rrutrahzedto YrYu 00 and ther outputs 01101100011011ete so that rst Tu 1 and all others are 0 then T11 and all others are 0 ete In order to produee L 39quotT1T2andT3 Pag2150f28 LastRevrsedohJu1y 202010 Copyrrght 2005 by Ed Bosworth Chapter 7 Analysxs andDesxgn of Sequenha1 chemts Note that the above desxgn 15 sxmplexed by the fact that the outputs Y and Yu39 are avat1ab1e dneeuy from the xpr ops and do not needto be synmesxzed usmg NOT gates 15 stonng a1 Th1s desxgn a1so works as amodu1oA counter and ska5 the decoder de1ays T0 T1 T2 T3 When the eonnter ts mmahzed we set YD 1 and Y1 Y2 Y3 0 As the e1oekaeks the smgle WnC AnotherDesx n Problem The ModuloA U o ounter For the next desxgn we mtroduce aproblem thatuses mput Th1s1s amodu1oA uprdown counter The mput X15 usedto control the dneehon ofcounung EX0 the demeeeounts up 01230123ete EX 1 the demee eounts down 0 3 2 1 0 3 2 1 ete Step 1 Derive the state diagram and state table fur the circuit The state dtagnam for the modu1oA uprdown eountems shown atnght Nohee that the x mput 15 use determme the eountmg ddrecuon Agam Lhst e ofcxrcmt does not have any on ut assomated wnh the hans1t1onsthe outputjust re ects whmh ofthe four states the maehme nds xtselfm atthe moment a e 00 Page 16 of28 LastRemsedothdy 202010 Copynght 2005 by Ed Boswonh Chapter 7 Analysis and Design of Sequential Circuits We now produce the sate table by translating the state diagram As an aside some students might prefer to begin the design process with the state table and omit the state diagram That is certainly acceptable practice whatever works should be used Here the state table depends on X 7 the input used to specify the counting direction Step 2C0unt the number of states in the state diagram call it N and calculate the number of ip ops needed call it P by solving the equation 21 1 lt N S 21 The number of states on a moduloN counter is simply N these are labeled 0 through N 7 1 Speci cally a modulo4 counter has four states labeled 0 l 2 and 3 We solve the equation 21quot1 lt 4 S 2P by noting that 21 2 and 22 4 so we have determined that 21 lt 4 S 22 hence P 2 We shall see later that there are valid solutions with more than two ip ops but there are none with fewer Step 3 Assign a unique P bit binary number state vector to each state Often the rst state 0 the next state 1 etc Some sequential circuits suggest an innovative numbering system but moduloN counters never do We go with the obvious labeling generated by assigning each decimal number its twobit binary equivalent as an unsigned integer in the range from 0 to 3 Step 4 Derive the state transition table and the output table There is no output table for any moduloN counter as the output associated with this type of table is the output on a transition as is seen in a sequence detector The transition table is a direct translation of the state table using the assignments from the previous step Page 17 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits The transition table for the modulo4 updown counter is as follows Step 5 Separate the state transition table into P tables one for each ip op Here we separate the state transition table into 2 tables one for each ip op Note that the ip ops will be numbered 0 and l with ip op 0 storing the least signi cant bit of the state information Thus we shall refer to the state information as Y1Y0 The student who is paying attention at this point will notice an interesting feature concerning ip op 0 specifically that its next state does not depend on X This is due to the fact that in considering a moduloN counter one moves from odd numbers to even numbers and from even numbers to odd numbers in both counting up and counting down Step 6 Decide on the types of ip ops to use When in doubt use all JK s Up to this point we have made no assumptions about the type of ip op to use In order to proceed any farther with the design we must now commit to a specific type In line with this author s preferences he chooses to use two JK ip ops The excitation table for a JK ip op is shown at right Recall that the d stands for Don t Care For example if we have QT 0 and want QTl 0 we can use either J 0 K 0 or J0K l SimilarlyeitherJ l andK00rJ l andKl will take QT 0 to QT l l Page 18 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Step 7 Derive the input table for each ip op using the excitation tables for the type Here is the input table for ip op 1 Note that the arrangement of the table has been altered to re ect the fact that we now have a binary input Here is the input table for ip op 0 X0 Step 8 Derive the input equations for each ip op based as functions of the input and current state of all ip ops At this point we try to derive an expression that matches each column Formal methods can be used but generally are more trouble than they are worth Here is this author s set of rules to match an expression to a given column If a column does not have a 0 in it match it to the constant value 1 If a column does not have a l in it match it to the constant value 0 2 If the column has both 0 s and 1 s in it try to match it to a single variable which must be part of the present state Only the 0 s and 1 s in a column must match the suggested function 3 If every 0 and l in the column is a mismatch match to the complement of a function 4 If all the above fails try for simple combinations of the present state The reader will note that there are two columns for each variable for which an equation is desired one column for X 0 and one column for X 1 For example consider the table for ip op 0 just above If we work on a columnby column basis we shall arrive at four equations One for J 0 when X 0 one for K0 when X 0 one for Jo when X l and one for K0 when X 1 However we need a single equation for J 0 and a single equation for K0 Page 19 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits The Combine Rule There are many ways to produce the single equations for J 0 and K0 including algebraic simpli cation and Karnaugh Maps The method preferred by this author for producing a single equation for an entity such as J 0 or K0 is as follows 1 Use the least complexity matching rule as described above for each column of the expression Thus for J 0 we shall have two expressions one for X 0 and one for X l 2 Use this author s combine rule to produce a single expression The rule for combining expressions derived separately for X 0 and X l is X oexpression for X 0 X0expression for X 1 The origin of the combination rule is the following observation Consider the Boolean expression F X oA XoB where A and B are any Boolean expressions When X 0 this becomes F loA 00B A and when X 1 this becomes F 00A 10B B We then see that F X oA XoB ifand only ifF A when X 0 and F B when X 1 This simple observation is the source of the combination rule It will always produce a correct result and usually produce the simplest result There are quite a few simplifications of the combine rule all of which should be noted 1 AB ThenFX oAXoAA 2 A0 ThenF X OO XOBXOB B0 ThenFX oAX00X oA Then F X ol XoB X B by the Absorption Theorem Then F X oA Xol A X also by the Absorption Theorem 1 03gt l l The last two statements seem somewhat surprising so we prove them a X X0BX B IfX0then X XoBl00Bl X B1Bl IfXlthen X XOB010BB X B0BB b X oAXAX HX0JMn XuAx1ux0A AXA0A HXme XuAxmA11 AXA11 So we get to work with the combine rule Page 20 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits The table for ip op l is as follows l 0 J1Y0 J1Y0 K1Y0 K1Y0 We arrived at the matches for X 0 by noting that each column had both a 0 and a l The next step is to try matches against the variables Y1 is not a match but Y0 is We arrived at the matches for X l by noting that each column also had both a 0 and a 1 None of the simple variables matched but we noted that Yo matched both We now apply the combine rule X Oexpressi0n for X 0 Xexpression for X 1 ForX0 J1Y0 andforXlJ1Y0 so J1X 0Y0 X0Y0 XCBYO ForX 0 K1 Y0 and forX 1 K1 Yo so K1X 0Y0 X0Y0 X EB Y0 The table for ip op 0 is as follows J0l J0l K0l K0l We now apply the combine rule X oexpressi0n for X 0 X0expressi0n for X 1 This iseasy J0X olXolX Xl This iseasy K0X olXolX Xl Step 9 Summarize the equations by writing them in one place Here they are J1X BYO K1X Y0 J0 1 K0 1 This is a counter so there is no Z output Page 21 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysls andDeslgn of Sequenual Crreurts Step 10 Drawthe circuit diagram Agam r K p p the onerhot solutlon m whleh the X lnput eontxols the shlft dueetron X 0 for shlft nght and X l for sth left Students are lnvrtedto examlne these solutlons at Lhelrlelsure The Prim Prnhlem For several semesters Ihave had a pnze problem that nobody rneludng myselo ean solye does not produee the srmplest soluuon Here ls the problem Do a deslgn wrth one ormore J39K lpr ops note 7 one should be enough Use the methods b p andK Demonstrate amethod that produees slmpler Boolean expresslons forJ andK Any student problem to avold wastrng trme ln solvlng the Wrong problem Page 22 of 28 LastReyrsed on July 20 2010 Copynght 2005 by Ed Bosworth chapter 7 Analysis and Design of Sequential circuits The Traf c Li l Problem As amorecomplex i ital design problem we shall considerthe controller forasimple tm ic light 39 39 39 oftw s 39 39 than r l as lights onecalledLl m h Mr L 39 pair ofquotL quot 39 39 39 39 sequence Red Green Yellow More complex tra ic lights such as those with turn signals or advanced green lights can be similarly modeled a but let s keep it simple We see that there are six states in the system In line with standard binary notation I begin the labeling with state 0 It will be convenient to have state 0 be aRed Red state Thus ht 39 in t d i n 0 and3 with the alias RR We use this fact to comment on an alternate design one which I decline to use A Sixrslale Design A Fiverslale Design At rst look the design on the right appears simpler only having ve states The diagram at right hides one speci c di iculty a the state that follows RR Is it GR or RG7 The design at right calls for the transition RR gt RG to alternate with the transition RR gt GR thus we would need a ip op to rememberwhich transition ms t en last time Each ofthe two designs requires at least three ip ops We go with the easier design on the left At this point r39 r 1 mom 39 39 39 39 39 39 39 quot the L circuit v L inpnununxeth l r Page 23 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits The table at right is the state table with the state number and alias given for both the present and next state We keep the alias for convenience only as we have not resolved the duplicate RR alias At this point we note that we have siX states and are ready for Step 2 Count the FlipFlops We need to use three ip ops P 3 YR Step 3 Assign a Binarv Number to Each State The solution here is obvious 7 we treat each number as a threebit unsigned integer and assign the binary numbers 000 001 010 011 100 and 101 At this point we have two binary patterns that are not assigned 110 state 6 and 111 state 7 Although these states are supposedly unreachable in our design I propose to handle them anyway as we are designing a device that is safetycritical This design specifies that the next state following either state 6 or state 7 will be state 0 As a safety consideration we further specify that both states 6 and state 7 display Red on each of the two lights as we consider these to be failure states Following our standard design practice we label the ip ops with the integers 2 l and 0 and call the outputs of the ip ops Q2 Q1 and Q0 as Y is taken to stand for Yellow Step 4 Derive the State Transition Table and Output Table The first step in deriving the output table is to define the output The design calls for two coupled traffic lights each with the standard colors Red Green and Yellow The circuit will thus have siX outputs Rl Gl Yl R2 G2 and Y2 7 the first three outputs to light 1 and the second three outputs to light 2 The output table is somewhat complicated It may seem that we have siX signals to generate based on the three binary values Y2 Y1 and Y0 but we take a shortcut We note that each light is either Red Green or Yellow and when it is not either Green or Yellow it must be Red Thus the only signals we generate directly are Gl Yl G2 and Y2 Here are the output equations G1 Q2 Q1 Q0 G2 Q2 Q1 Q0 Y1Q2 Q1 Q0 Y2Q2 Q1 Qo Rl G1 Yl R2 G2 Y2 Page 24 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits If we wanted to provide extra fault tolerance we would demand that when one light is either green or yellow the other must be red thus generating the equations R1 G1 Yl G2 Y2 and R2 G2 Y2 G1 Y1 A bit of re ection will show that even with this design it is possible for one light to show more than one color Here we assume a person seeing both red and green on a traffic light would assume something is very wrong We now consider the state transition table expressed in terms of Q2 Q1 and Q0 Before breaking this into three tables one for each ip op we note the handling of the supposedly nonreachable states 6 and 7 The design here is based on fault tolerance the idea that the circuit should have some ability to restore itself from faulty operation Admittedly the strategy re ected in this design may not be realistic It is shown mostly to draw the student s attention to the concepts and not to present an optimal solution 000 Step 5 Separate the Table into Three Tables One for Each FlipFlop Remember that each table must have a complete description of the present state PS NS PS NS PS Page 25 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysis and Design of Sequential Circuits Step 6 7 Select the FlipFlop Type and Copy Its Excitation Table Since the JK ip ops seem to be the QT QT 1 most useful type I have selected to use JK s in the design As a reminder 0 I have written the excitation table for l l J 0 l d this ip op to the right d 070 0794171 Step 7 7 Derive the Input Table for Each FlipFlop 2 l Step 8 7 Derive the Input Equation for Each FlipFlop J2Q139Q0 J1Q2quotQ0 J0Q2 Q1 K2Q1Q0 K1Q2Qo K01 Step 9 7 Summarize the Equations Not needed 7 there are no other equations Step 10 7 Draw the Circuit The circuit is shown on the next page of the notes The diagram has three parts 1 The middle part is the design from steps 8 and 9 of the above work It shows the design of what is essentially a modulo6 counter 2 The top part contains the circuits that implement the equations for R1 Yl G1 etc as found in the first part of step 4 of the design This is essentially the output of the circuit 7 six signals that control six traffic lights 3 The bottom part of the circuit is what provides clock pulses to the modulo6 counter Note that the circuit is a shift register used to provide a clock pulse at irregular intervals at T l T 6 and T 8 providing for unequal length of light phases Page 26 of 28 Last Revised On July 20 2010 Copyright 2005 by Ed Bosworth Chapter 7 Analysls and Deslgn of Sequenual clmulls R1 GZ Y2 CLOCK In thS deslgn the lnput CLOCK IS a regular slgial say oneuek per second The shl l l m l causlng an output aLT l T o andT 8 or o It 15 ths lrregularoutpuLLhaL causes the modulor6 beglns m slale 0 RR and moves as follows State Aha Duvahan u RR l l as 5 2 w 2 3 RR l 4 on 5 5 w 3 Page 27 of28 LBSLReVlSed OnJuly 20 2010 Copynght 2005 by Ed Bomonh What does the following circuit do More speci cally analyze the circuit and produce its state table and state diagram Assume that the circuit starts at Y1Y0 00 Q Y Q Y1 Output 1 T T l Cluck 1 ANSWER The best way to do this is to proceed mechanically l The rst step is to identify all of the inputs and outputs giving a label to each This gure has done that Note that this is not a circuit with output in the sense that a sequence detector has output It is some sort of counter 2 Characterize the inputs and outputs of the ip ops Show as Boolean expressions T0 17 T1 Q03 3 Construct the Next State and Output Tables There is no output in the sense of a sequence detector so we just do the next state tables Present Input Next State Input Next State State Y0 Y1 T0 Y0t 1 T1 Y1t l O O l l l l O l 1 l l O l O 1 O O O l l l O O l In this form the table is completely puzzling We need to produce the nal table Here is a direct reading of the information Present Next State State Y0 Y1 Y0 Y1 O O 1 1 O 1 1 O 1 O O O 1 1 O 1 But note what happens when we do this table backwards Present Next State State Y1 Y0 Y1 Y0 O O 1 1 O 1 O O 1 O O 1 11 10 6 Assemble the Boz 5 instruction XOR R3 R2 R1 Show the machine language as eight hexadecimal digits Here is the format of the XOR instruction 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 O Op Code Destination Source Source Not used Register Register 1 Register 2 Opcode 11001 XOR Logical Exclusive OR Here is the instruction 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 O 11001 0 011 010 001 Not used Thecodeis 11001 0 011 010 001 00000 1100 1001 1010 0010 0000 C9A2 0000 A given computer design calls for an 18 bit MAR and an 8 bit MBR a How many addressable memory elements can the memory contain b How many bits does each addressable unit contain c What is the size of the address space in bytes Comment The MBR Memory Buffer Register is often called the MDR Memory Data Register a The memory can contain 218 256K addressable memory elements b Each element contains 8 bits because the MBR has size of 8 bits The memory contains 256 KB c The size of the address space in bytes is 256 KB Suppose a computer using direct mapped cache has 232 words of main memory and a cache of 1024 blocks Where each cache block contains 32 words a How many blocks of main memory are there b What is the format of a memory address as seen by the cache that is What are the sizes of the tag block and word elds c To Which cache block Will the memory reference 0000 63FA map Recall that 1024 210 and 32 25 a The size of a cache block cache line is 32 words The size of a main memory block is also 32 words The number ofblocks is 232 25 227 b Memory tag Will be 27 bits Offset in the cache line is 5 bits The memory tag is split into two parts 10 bit cache line number 17 bit cache tag The format of the address is Tag Cache Line Offset The tag contains 17 bits The cache line is 10 bits The offset is 5 bits Bits 31 15 14 5 4 0 Cache View Tag 1 Line Offset Address View Block Number Offset To Which cache block Will the memory reference 0000 63FA map The cache line number is contained in bits 14 5 of the address We need the low order 15 bits of the address Examine the low order 16 bits 4 hexadecimal digits 63FA 0110 0011 1111 1010 0 1100011111 11010 Thecachelineis 1100011111 or 0011 0001 1111 31F This memory is low order interleaved With its 22 bit address formatted as Bits21 4 Bits3 O Address to chips Bank select a What is the size of each chip in bytes b How many banks does the memory have Assume that the memory is byte addressable The question does not specify the addressability and it must be stated The size of the memory is 222 bytes a 18 bits are sent to each chip so the chip size is 218 bytes b 4 bits select the bank so the memory has 24 16 banks 18 Given the Boz 5 design write out the complete microcode sequence for the following instructions ANDI STR SUB For each instruction do the following 1 Show the complete microcode for the fetch sequence 2 Place the rst micro word for execution at its proper address 3 Place the rest of the microcode if any at any appropriate location Be sure to set the next address elds appropriately Always begin with control signals The common fetch sequence F TO PC gt B1 tral B3 gt MAR READ MAR lt PC READ F T1 PC gtB11 gtB2 add B3 gtPC PClt PC1 F T2 MBR gt B2 tra2 B3 gt IR IR lt MBR ANDI AND Immediate F T3 IR gt B1 R gt B2 and B3 gt R Copy IR190 as 20 bits ANDI Microcode The common fetch microcode is as follows Address MicroOp B1 B2 B3 ALU M1 M2 s2 0 s2 1 0x20 0 1 0 2 1 0 8 0x21 0x21 0x21 0 1 1 1 5 0 0 0x22 0x22 0x22 0 0 6 4 2 0 0 0x23 0x23 0x23 1 0 0 0 0 0 0 0x20 0x20 The opcode for ANDI is 0X02 ANDI OpCode 00010 1R gtB1 R gtB2 and B3 gtR iAddressiMicroOp B1 Bzi B3 ALUM1 M2 B0 B1 0x02 0 4337000x200x20 STR Microcode Begin With the common start up microcode Which ends in the dispatch to the microprogram at the correct address The common fetch microcode is as follows Address MicroOp B 1 B2 B3 ALU M1 M2 S2 0 S2 1 0X20 O l O 2 l O 8 OX2 l OX2 l OX2 l O l l l 5 O 0 0X22 OX22 OX22 O O 6 4 2 O 0 0X23 OX23 OX23 l O O O O O 0 0X20 OX2O The next thing to do is to process the indirection This requires selection of some addresses other than the obvious OXOD I have selected 0X32 for the start of the microprogram for STR This requires that the S2 0 option have address 0X35 Assuming that the opcode for STR is OXOD we have this at that address Address MicroOp B1 B2 B3 IALU M1 M2 sz0 sz1 OXODI 0 4325000x350x32 Here is the defer code READ Address MicroOp B1 B2 B3 IALU M1 M2 s20 s21 0x32 0 0000 0 80X2D0X2D WAIT Address MicroOp B1 B2 B3 IALU M1 M2 s20 s21 0X33 0 0000 0 00X2E0X2E MBR gtB2tra2B3 gtMAR Address MicroOp B1 B2 B3 ALU M1 M2 s20 s21 0X34 0 0 6 2 2 0 0 0X2F 0X2F

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.