This preview shows page 1-2-3-4-5-6-7-8-9-10-11-12-13-89-90-91-92-93-94-95-96-97-98-99-100-179-180-181-182-183-184-185-186-187-188-189-190-191 out of 191 pages.
CS150 Midterm2 ReviewOverview of things to reviewSequential CircuitsSlide 4RS LatchMemory with Cross-coupled GatesTiming BehaviorState Behavior of R-S latchTheoretical R-S Latch BehaviorObserved R-S Latch BehaviorR-S Latch AnalysisGated R-S LatchClocksClocks (cont’d)Cascading LatchesMaster-Slave RS (flip flop??)Master-Slave StructureThe 1s Catching ProblemD Flip-Flops (Ah something that people actually use for a change)D Flip-FlopEdge-Triggered Flip-FlopsEdge-Triggered Flip-Flops (cont’d)Slide 23TimingTiming MethodologiesTiming Methodologies (cont’d)Comparison of Latches and Flip-FlopsNext slide important!Comparison of Latches and Flip-Flops (cont’d)Typical Timing SpecificationsCascading Edge-triggered Flip-FlopsCascading Edge-triggered Flip-Flops (cont’d)Summary of Latches and Flip-FlopsMetastability and Asynchronous inputsSlide 35Synchronization FailureDealing with Synchronization FailureHandling Asynchronous InputsHandling Asynchronous Inputs (cont’d)Flip-Flop FeaturesSlide 41RegistersShift RegisterUniversal Shift RegisterSlide 45Design of Universal Shift RegisterShift Register ApplicationSlide 48Pattern RecognizerBinary CounterFour-bit Binary Synchronous Up-CounterOffset CountersSequential Logic SummarySequential Logic ImplementationSlide 55Abstraction of State ElementsForms of Sequential LogicFinite State Machine RepresentationsHow Do We Turn a State Diagram into Logic?FSM Design ProcedureFSM Design Procedure: State Diagram to Encoded State Transition TableImplementationSlide 63Implementation (cont'd)Another ExampleMore Complex Counter ExampleMore Complex Counter Example (cont’d)Self-Starting Counters (cont’d)Self-Starting CountersState Machine ModelState Machine Model (cont’d)Example: Ant Brain (Ward, MIT)Ant BehaviorDesigning an Ant BrainSynthesizing the Ant Brain CircuitTransition Truth TableSynthesisSynthesis of Next State and Output FunctionsCircuit ImplementationDon’t Cares in FSM SynthesisState MinimizationAnt Brain RevisitedNew Improved BrainNew Brain ImplementationMealy vs. Moore MachinesSlide 86Arg… So many slides of examples!Specifying Outputs for a Moore MachineSpecifying Outputs for a Mealy MachineComparison of Mealy and Moore MachinesMealy and Moore ExamplesMealy and Moore Examples (cont’d)Registered Mealy Machine (Really Moore)Example: Vending MachineExample: Vending Machine (cont’d)Slide 96Slide 97Slide 98Slide 99Equivalent Mealy and Moore State DiagramsExample: Traffic Light ControllerExample: Traffic Light Controller (cont’)Slide 103Slide 104Slide 105Logic for Different State AssignmentsVending Machine Example (PLD mapping)Vending Machine (cont’d)Vending Machine (Retimed PLD Mapping)Finite State Machine OptimizationFinite State Machine OptimizationAlgorithmic Approach to State MinimizationState Minimization ExampleMethod of Successive PartitionsMinimized FSMMore Complex State MinimizationSlide 117Minimizing Incompletely Specified FSMsMinimizing States May Not Yield Best CircuitAnother Implementation of Edge DetectorState AssignmentState Assignment StrategiesOne-hot State AssignmentHeuristics for State AssignmentGeneral Approach to Heuristic State AssignmentOutput-Based EncodingCurrent State Assignment ApproachesSequential Logic Implementation SummarySequential Logic ExamplesGeneral FSM Design ProcedureFinite String Pattern Recognizer (Step 1)Finite String Pattern Recognizer (Step 2)Finite String Pattern Recognizer (Step 2, cont’d)Slide 134Finite String Pattern RecognizerComplex CounterComplex Counter (State Diagram)Traffic Light Controller as Two Communicating FSMsCommunicating Finite State MachinesDatapath and ControlDigital Combinational LockDetermining Details of the SpecificationDigital Combination Lock State DiagramDatapath and Control StructureState Table for Combination LockEncodings for Combination LockDatapath Implementation for Combination LockDatapath Implementation (cont’d)Tri-statesTri-State GatesTri-State and MultiplexingOpen-Collector Gates and Wired-ANDSlide 153Digital Combination Lock (New Datapath)Section SummaryComputer OrganizationStructure of a ComputerSlide 158Register TransferRegister FilesMemoriesThe rest is probably not too important for the testInstruction SequencingInstruction TypesElements of the Control Unit (aka Instruction Unit)Instruction ExecutionData Path (Hierarchy)Data Path (ALU)Data Path (ALU + Registers)Data Path (Bit-slice)Instruction PathData Path (Memory Interface)Block Diagram of ProcessorSlide 174A simplified Processor Data-path and MemoryProcessor ControlProcessor InstructionsTracing an Instruction's ExecutionTracing an Instruction's Execution (cont’d)Slide 180Slide 181Slide 182Register-Transfer-Level DescriptionRegister-Transfer-Level Description (cont’d)Review of FSM TimingFSM Controller for CPU (skeletal Moore FSM)FSM Controller for CPU (reset and inst. fetch)FSM Controller for CPU (decode)FSM Controller for CPU (Instruction Execution)FSM Controller for CPU (Add Instruction)FSM Controller for CPUCS150 Midterm2 ReviewJoy! Another midtermCS 150 - Fall 2000 - Introduction - 2Overview of things to reviewFlip-flop, LatchEdge triggered, level sensitive, completely transparentTiming analysis.Sync/Async Set ResetEnableFSMWord description -> implementationMealy, MooreState minimizationState Encoding OptimizationDatapath, ControlCS 150 - Fall 2000 - Introduction - 3Sequential CircuitsCircuits with historyThis is a General ConceptThings to looks over for midterm:Circuit Elements used in Sequential Circuits to keep track of the “history”Flip flops, Latches•Edge triggered, level sensitive, completely transparent•Timing analysisFSMUnderstanding word problemsIdentifying input, output to combinational part of FSMState assignment (optimization)Generating actual circuit implementationCS 150 - Fall 2000 - Introduction - 4C1 C2 C3comparatorvalueequalmultiplexerresetopen/closednew equalmux controlclockcomb. logicstateSequential CircuitsCircuits with FeedbackOutputs = f(inputs, past inputs, past outputs)Basis for building "memory" into logic circuitsDoor combination lock is an example of a sequential circuitState is memoryState is an "output" and an "input" to combinational logicCombination storage elements are also memoryCS 150 - Fall 2000 - Introduction - 5RS LatchNot really used much in real designsMainly used because it is simple and easy to understand.MAKE SURE that you know how timing
View Full Document