FINAL EXAM REVIEW NOTES CS150 Exam Date: Thursday, December 13, 2001 Exam Time: 12:30 - 3:30pm Exam Loct: 10 & 60 Evans - For some of you who didn't make it to the review session, these notes are a helpful guideline for you guys who didn't make it to the review session. - Again I'd like to mention these are just guidelines to what you should or might need to know. I have no idea what the professor is exactly going to test you on, but these are my suggestion as to what I think he might test. 1. State Machines and State Diagrams - Know the difference between MOORE, MEALY, and SYNCHRONOUS MEALY. - Moore: Next State based on Current State and Inputs Outputs based on Current State (Synchronous Outputs) - Mealy: Next State based on Current State and Inputs Outputs based on Inputs (Asynchronous Outputs) - Synch Mealy: Same as Mealy, however output is synched by clocking the outputs with a register or a flip-flop. - The behavior of the Moore and Synchronous Mealy is the same in transition of state and outputs, both clocked. However, outputs in a Synchronous Mealy are delayed by one clock cycle compared to Moore Machine. ** This I leave to you to figure out. - Know how to draw State Machines correctly. - Draw Moore and Mealy correctly, don't mix and match. - Important for understanding in a high level sense how the state machine will work or controller. - Process of creating a State Machine/Controller. - First produce a high level state diagram, with bubbles and all. - Move to a transition table after you finalize your State Diagram. - Begin reduction using either simple Theorems and Axioms, Karnaugh Maps, Implication Charts, etc. - Encoding the states. Know the different types of encoding, One-Hot, Gray Code, Sequential, etc. 2. Simple Logic and Reduction - Understand Basic Axioms and Theorems of Logic - Closure a + b (in the same set B) - Commutativity a + b = b + a - Associativity a + (b + c) = (a + b) + c - Identity a + 0 = a - Distributivity a + (b * c) = (a + b) * (a + c) - Complementory a + a' = 1 - More, study them all briefly to refresh your memory. - Karnaugh Maps - Useful reduction technique. \ AB CD \ 00 01 11 10 |---------------| 00| 1 | 1 | 0 | X | |---------------| 01| 1 | X | X | 0 | |---------------| 11| X | 1 | 1 | 0 | |---------------| 10| X | 0 | 0 | X | |---------------| - Implication Charts - Review Implication Charts from Midterm 2. - Easy. Easy. Easy. 3. Advanced Combinational Logic - Bubble Pushing - 2-Input AND Gate with both inputs inverted, can be bubble-pushed into 2-Input NOR Gate. - 2-Input NAND Gate can be bubble-pushed into a 2-Input OR Gate with both inputs inverted. - The idea of bubble pushing is important, it allows the gate logic to be simplified with fewer gates, or allows you to create logic with certain gates in mind. Useful because in the real world, the only available gates you have are NOR, NAND, and INV. - Hazards and Timing Issues - Like the previous Midterm II, refresh your mind on timing, gate delays, hazards, etc. that might affect the timing diagram or even critical path. - Static Hazards: Hazards due to delay because if input A and it's complement A' are suppose to be opposite value, except delay causes the inputs to be the same value for an instance. This is static hazard. - Dynamic Hazards: A output is fanned-out to multiple inputs. However due to wire delays, or length, creating a longer propagation delay, one Input A might have a differnt value of a second Input A. This is cause of Dynamic Hazards. - Multiplexors and DeMuxes - Know the basic design of the Mux and DeMux. - Should be able to construct a simple 2-to-1 Mux (1-bit) from two NAND gates and an OR gate. A ---|-------| | AND |-----| SEL ---|-------| | |->|------| | OR |---- OUT |->|------| B ---|-------| | | AND |-----| SEL --O|-------| - PLAs and PALs - Programmable Logic Arrays - Unconstrained full-general plane of ANDs and ORs. - Programmable Array Logic - Constrained portions/planes of ORs. 4. Tri-State Buffers and Inverters - Know them, building blocks of system with multiple drivers and buses. - Not much to say but know how to use them wisely. 5. Arithmetic Logic - Representing Negative Numbers - 2's Complement: By inverting all the bits, and then adding one. - Most negative numbers in computer architecture or logic is represented in 2's complement form. - Adders - Half and Full Adders (Full has a carry-in) - Ripple Adder, Carry-Look Ahead Adder - Ripple Adder Equations: Sum = A xor B xor Ci Co = ((A or B) and Ci) or (A and B) - Carry-Look Ahead Adder Sum = Ai xor Bi xor Ci = Pi xor Ci Pi = Ai xor Bi (Propagate Signal) Gi = Ai and Bi (Generate Signal) Ci+1 = Gi + Ci*Pi The propagate signal and generate signals are used to setup and send the next carry-in to the next block without having to wait for the first unit to calculate carry-out. The generate signal is self explantory, it generates the next carry-in. Since binary 1 plus binary 1 will have a carry-out. The propagate signal "propagates" the carry bit only if A = 1 and B = 0. Or vice versa. 6. Programming - Microprogramming - An easier way to organize control signals. For register transfer operations. - Vertical Microprogramming - Encoded control signals in ROM, decoded externally, with some mutually exclusive signals, and helps reduce ROM length - Horizontal Microprogramming - Fully decoded control signals that access the datapath, and can be accessed in parallel. 1 ROM output for each control signal. ** These are just suggestion from one TA. This DOES NOT MEAN that these subjects will be tested or in the final on Thursday. These are just suggested materials to study for. GOOD LUCK EVERYONE! Randy