Memory; Sequential & Clocked Circuits; Finite State MachinesPowerPoint PresentationRecap: Boolean LogicBoole’s reworking of Clarke’s “proof” of existence of God (see handout)Combinational circuit for binary addition?Modular designModular design for N-bit adder1-bit adderA Full Adder (from handout)Timing DiagramMemoryWhat do you understand by ‘memory”?Why combinational circuits have no “memory”Matt likes Sue but he doesn’t like changing his mindSequential CircuitsEnter RitaR-S Flip-FlopA more convenient form of memory“Register” with 4 bits of memoryWhat controls the “Write” signal?Slide 21Clocked Sequential CircuitsSynchronous Sequential Circuit (aka Clocked Sequential Circuit)ShorthandClock SpeedsWhat limits clock speed?Finite State MachinesExample: State diagram for automatic doorMemory; Sequential & Clocked Circuits; Finite State MachinesCOS 116: 3/25/2008Sanjeev AroraMidterm grade Criterion:58-65: A55-57: A-50-54: B+45-49: B40-44: B-33-39: C26--32: D25 and below: FRecap: Boolean LogicBoolean Expression E = S AND DTruth table:Value of E for every possible D, S. TRUE=1; FALSE= 0.001011110000ESDBoolean CircuitESDTruth table has rows ifthe number ofvariables is k€ 2kBoole’s reworking of Clarke’s “proof” of existence of God(see handout)General idea: Try to prove that Boolean expressions E1, E2, …, Ek cannot simultaneously be trueMethod: Show E1· E2 · … · Ek = 0Discussion: What exactly does Clarke’s “proof” prove? How convincing is such a proof to you?Also: Do Google search for “Proof of God’s Existence.”Combinational circuit for binary addition?Want to design a circuit to add any two N-bit integers.25 11001+ 29 11101 54 110110Is the truth table method useful for N=64?Modular designHave small numberof basic components.Put them together to achieve desired functionalityBasic principle of modern industrial design; recurring theme in next few lectures.Modular design for N-bit adderSuffices to use N 1-bit adders! cN-1 cN-2 … c1 c0 aN-1 aN-2 … a1 a0+ bN-1 bN-2 … b1 b0 sN sN-1 sN-2 … s1 s0Carry bits1-bit adder(Carry from previous adder)Do yourself: Write truth table, circuit.akbkck1-ADDck+1skCarry bit for next adder.A Full Adder (from handout)Timing Diagram5V0VTimeX5V0VTimeoutputNOT gatedelayMemoryRest of this lecture:How boolean circuits can have“memory”.What do you understand by ‘memory”?How can you tell that a 1-year old child has it?Behaviorist’s answer: His/her actions depend upon past events.Why combinational circuits have no “memory”Wires: transmit voltage(and hence value)Boolean gates connected by wiresImportant: no loops allowedOutput is determined by current inputs;no “memory” of past values of the inputs.Today: Circuits with loops; aka “Sequential Circuits”Matt likes Sue but he doesn’t like changing his mindRepresent with a circuit: Matt will go to the party if Sue goes or if he already wanted to goSMIs this well-defined?Sequential Circuits Circuits with AND, OR and NOT gates.Cycles are allowed (ie outputs can feedback into inputs)Can exhibit “memory”.Sometimes may have “undefined” valuesEnter RitaMatt will go to the party if Sue goes OR if the following holds: if Rita does not go and he already wanted to go.?MSRMR, S: “control” inputsWhat combination of R, S changes M?R-S Flip-FlopSRMA more convenient form of memory“Data Flip-Flop” or “D flip flop”;Can be implemented using R-S flip flop.No“undefined”outputs ever!“Register” with 4 bits of memoryWhat controls the “Write” signal?The “symphony” inside a computerClock Combinational circuitMemoryClockedSequentialCircuit(akaSynchronousCircuits)Clocked Sequential CircuitsSynchronous Sequential Circuit(aka Clocked Sequential Circuit)CLOCKINPUTSCombinational CircuitMemory(flip-flops)ShorthandCombinational CircuitMemory(flip-flops)CLKThis stands for “lots of wires”Clock SpeedsHeinrich Hertz1857-941974 Intel 8080 2 MHz(Mega = Million)1981 Original IBM PC 4.77 MHz1993 Intel Pentium 66 MHz2005 Pentium 4 3.4 GHz(Giga = Billion)What limits clock speed?Combinational CircuitMemory(flip-flops)CLKDelays in combinational logic (remember the adder)During 1 clock cycle of Pentium 4, light travels: 4 inchesFinite State MachinesRead handout (Brian Hayes article) for next time.Example: State diagram for automatic door ClosedOpenDetected PersonNo Person DetectedDetected PersonNo Person
View Full Document
Unlocking...