Midterm Exam II Outline ---------------------- Midterm II will cover lectures 9 through 17. The exam will not intentially be comprehensive of all material from the beginning of the semester, but by necessity may cover some material from lectures 1 through 8. As with midterm I, homework problems are typical of exam questions. Midterm will not be substantially different in style from midterm I, so once again expect the exam questions to go into more depth than most quizes and in some cases more depth then the homework questions. You should understand the basic concepts sufficiently well to apply them in new situations. In addition to the material from class, any of the material from the reading may possibibly appear on exam. However, priority will be given to the material covered in class. Lecture 9: Formal design process for Moore style FSMs: Translating from English language problem description to state transition diagram (STD). STD to state transition table (STT). STT to logic equations for next state and outputs. Circuit implementation with combinational logic and flip-flops. Motivation for one-hot encoding FSMs. One-hot encoded FSM circuit derivation directly from STT. Lecture 10: Implementation of subraction based on addition. Three important combinational carry-propagate adder architectures: Carry-ripple Carry-select Carry-look-ahead For each: General circuit-structure (for all values of n). Cost/performance (delay) analysis (both asymptotically with n and for specific values of n). Bit-serial Adder: Similar coverage as combinational adders. Lecture 11: Idea and motivation of dedicated carry-chains in FPGAs. Hardware Multipliers: Basics of "long-hand" multiplication. Shift-and-Add method: Circuit structure. Control algorithm. cost/performance analysis. modification for signed-numbers. Combinational (Array) Multipliers: Basic circuit structure. Performance enhancement with carry-save addition principle and application of carry-save technique. Performance enhancement with Wallace-tree technique. Lecture 12: Combinational Logic circuits from Mano Book: Magnitude comparator: Motivation and difference from CS61C style comparison by subtraction. circuit details (see Mano for correct logic equations). Multiplexors: Circuits details for entire family of implementations. See notes for list. cost/delay analysis for each. Decoders: Binary to one-hot. Any code to one-hot (we didn't cover in class, but since every code is a subset of a binary code, a sub-circuit of a complete binary decoder can decode any code). Using hierarchy to make large decoders. Encoders: one-hot to binary. priority encoders. Lecture 13: The exam will not directly the project lecture topics. Lecture 14: The principles and circuits for SR latches. Asynchrounous STD and how they are used to describe simple asynchrounous circuits. Converting from asynch. SR latch to level-sensitive latch. Converting SR latch to D-type latch. Building flip-flops from D-latches (master/slave). Building flip-flops from SR latch. The function of JK flip-flops. Implemenation of JK from D-type. Implementation of Toggle-type flip-flops from JK, and D-type. Design of a bit-serial adder using JK (or RS). Adding resets and presets to RS and D-type latches and flip-flops. Lecture 15: Mealy FSMs: Versus Moore, differences in STD. Difference in output behavior (and timing diagrams). Conversion from Mealy to Moore and vis versa. FSM state reduction using row-matching. FSM state assignment using heuristics. Lecture 16&17: Using counters in conjunction with FSMs for controller design and implementation. Implementation and characteristics of binary ripple counters. Synchronous binary counters: basic circuit. modular version. scaling to large size with "parallel prefix". implemenation with JK FFs. Principal and circuits of up/down counters. Counters with un-used states ("odd counts" in the notes). Ring Counters: basic. self-starting version. Johnson counter. Shift-registers: basic circuit. with parallel load. with parallel outputs. Bidirectional shifting.