Lecture Summary
Spring 2005
(Readings listed below in the entry for a lecture may actually correspond to multiple lectures in the vicinity of that lecture. Not all topics listed for reading may be covered in class. Some readings may be assigned ahead of the corresponding lectures.)

  1. 1/19/05: Handout distributed. Introduction to the course. Truth table. Don't care notation. Decimal notation. Designation number. Fundmental product, minterms.
    Reading: Sections 2.1 through 2.8 (much of this will be covered in the next lecture)

  2. 1/21/05: Instructional objectives handout distributed. Switching algebra. De Morgan's Law. Duality. Canonical sum. Fundmental sum, maxterms. Canonical product. Complete sets {AND,OR,NOT}, {AND,NOT}, {OR, NOT}. Reed-Muller form using XOR and AND (first method using "non-overlapping" terms).

  3. 1/24/05: Perfect induction. Second method (using fundamental sum) to obtain Reed-Muller representation. Proof of De Morgan's Law using induction. Generalized De Morgan's law. Set algebra to prove identities/theorems (example: consensus). Analysis of circuits with NAND/NOR gates ("moving bubbles"), impact of fanouts.

  4. 1/26/05: Switch networks. Definitions of minimal sum and products. Two-level implementations. Karnaugh maps. Definition of "f implies g". Implicants and Prime implicants. Distinguished 1-cells. Essential prime implicants. Complete sum. Finding minimal cost expressions from K-maps. Prime implicant theorem.
    Reading: Sections 3.1 through 3.5, Definition of "g includes f" or "f implies g" from page 171, Sections 6.1 through 6.4

  5. 1/28/05: Homework 1 assigned. Prime implicants for functions with don't care terms. Prime implicates (need to obtain these to determine minimal products). Quine-McCluskey tabulation to obtain prime implicants.  Prime implicant (P.I.) table for functions with or without don't care terms. Distinguished columns. Essential rows.
    Reading: Sections 6.6 and 6.7

  6. 1/31/05: Using P.I. table to determine minimal sum. Equal rows. Row and column dominance. Removing dominated rows if appropriate based on the costs. Removing dominating columns. Secondary essential rows. Branching method. Petrick's method (discussion incomplete).
    Reading: Sections 6.5 and 6.8

  7. 2/2/05: Petrick's method. Definition of "f includes g" (page 206). Consensus. Iterative Consensus -- First Tison method for determining prime implicants using consensus (handout for Tison method distributed in class) -- only the first method discussed on pages 1 and 2 of the handout required for the tests in ECE 462 this semester. Minimal sum for incompletely specified functions (i.e., with don't cares) using Quine-McCluskey tabulation (or Karnaugh maps) and P.I table. Started discussion on two-level minimization of multiple output functions.
    Reading: Handout on First Tison method (distributed in class). Sections 6.5 and 6.8.

  8. 2/4/05: Multiple output prime implicants (MOPI).  Using K-maps to find MOPIs. Using Quine-McCluskey tabulation to find MOPIs (identifiers and tags). Homework 2 assigned.

  9. 2/7/05: Multiple output minimal two-level AND-OR implementation using prime implicant table.

  10. 2/9/05: Multiple output minimal two-level AND-OR implementation using prime implicant table. Totally and partially symmetric functions. S notation for symmetric functions. Functions positive or negative with respect to a given variable. Unate functions.
    Reading: Chapter 5

  11. 2/11/05: Functions positive, negative, and mixed in their variables. Unate, frontal and backal functions. Residues. Threshold functions. Homework 3 assigned.

  12. 2/14/05: Threshold functions, determining whether a function is a threshold function or not. Boolean difference. Simple disjoint decomposition.

  13. 2/16/05: Simple disjoint decomposition. Transient analysis. Static and dynamic hazards. Function and logic hazards. Timing diagram to show how a static hazard occurs.
    Reading: Section 3.6
     
  14. 2/18/05: 1-sets and 0-sets. Stable and unstable 1-sets and 0-sets. Active 1-sets and 0-sets. Plotting stable and unstable 1-sets and 0-sets on Karnaugh maps. Identifying static logic 0-hazards and 1-hazards using 1-sets and 0-set. Timing diagram to show how a static hazard occurs.

  15. 2/21/05: Static 0-hazards and 1-hazards. Dynamic 0-hazards and 1-hazards. Marked logic diagram. P-sets and S-sets.

  16. 2/23/05: Finding dynamic hazards using P-sets and S-sets. Timing diagram to show how a dynamic hazard occurs in a circuit.

  17. 2/25/05: Logic hazard-free design. Transient, permanent, intermittent faults. Stuck-at-0 and stuck-at-1 faults. Exhaustive testing.
    Reading: Section 6.10, 6.11, 6.12

  18. 2/28/05: Bridging faults. Equivalence classes of faults. Minimal test sets. Boolean difference method.

  19. 3/2/05: TEST 1 in class today. Material covered in class through February 24 (and associated reading material) is included for this test. You may bring 1 two-sided sheet  (standard 8.5 inch x 11 inch size) of handwritten notes to the test. See the Lecture Summary page for the reading material listing.

  20. 3/4/05: Tests for stuck at faults in combinational circuits: path sensitization. Moore and Mealy machines.
    Reading: Handout on Moore and Mealy machines (filename: fsm0.pdf)

  21. 3/7/05: Converting between Moore and Mealy machines. Indistinguishable states. Equivalence classes. Minimizing the number of states. Reduced machine.

  22. 3/9/05: Prof. Hadjicostis' lecture: Binary decision diagrams (BDD). Ordered BDD. Reduced BDD.
    Reading: Notes from Prof. Hadjicostis
    OPTIONAL reading : Graph-Based Algorithms for Boolean Function Manipulation
    3/11/05: NO CLASS due to Engineering Open Hous

  23. 3/14/05: Prof. Michael Loui's lecture: Machine M1 contained in machine M2.; determination using Direct Sum. Equivalent machines. Experiments. Preset and adaptive experiments. Synchronizing sequence. Preset homing sequence. Preset distinguishing sequence.
    Reading: Handout on finite state machines (filename: fsm1.pdf)

  24. 3/16/05: Prof. Matt Frank lectures today

  25. 3/18/05: Adaptive distinguishing sequence. Adaptive homing sequence. Machine identification. (Graded test 1 returned today.)
    NOTE: Checking experiment was NOT covered in class. Checking experiments will be covered later in the semester, and will NOT be included in the material for Test 2. But it WILL be included for the final exam.
    Reading: Another handout on finite state machines (filename: fsm2.pdf) (see above note)

    3/21/05 -- 3/25/05 Spring Break

  26. 3/28/05: Fundamental mode circuits. S-R latch. Set-dominant latch. Reset-dominant latch. Symbols for set/reset dependence. D-latch. Gated latch. Symbol for gated latch. Static hazards in D-latch.
    Reading: Sections 7.1 through 7.5 (except section 7.5-1)

  27. 3/30/05: Analysis of sequential circuits using latches. Input state, latch variables, input variables, internal state, total state, excitation functions, excitation table. Transition table, output table. state table, flow table. Stable state. Race, critical race.
    Reading: Sections 7.5, 7.6  (except section 7.5-1)
    Handwritten notes from last year's class: set 1, set 2. Note that there is an error in the table in set 1 on the page numbered 11 at the bottom. The last row with SR = 11 should have Qbar = 0 because this table is for a set-dominant latch.

  28. 4/1/05: Discussion of sequential circuits using latches continued from last class. Analysis of sequential circuits with feedback loops. Insertion of amplifiers (and minimum number of amplifiers).

  29. 4/4/05: D-flip flop, JK flip-flop, T flip-flop. Essential hazards.
    Reading: Sections 7.6, 7.7. 7.8 
    Handwritten notes from previous year: Set 1, Set 2

  30. 4/6/05: Essential hazards. Removing a critical race from the transition table (without making the circuit behave differently than intended) -- see example in Tables 7.6-1 and 7.6-2.

  31. 4/8/05: Test 2 in class.

  32. 4/11/05: Fundamental-mode circtuis with latches. Differnt ways of implementing sequential circuits including two-phase latch machines. Analysis of ynchronous ("pulse-mode") sequential circuits with flip-flops.
    Readings: Sections 8.1, 8.2-1, 8.2-2

  33. 4/13/05: Analysis of synchronous sequential circuits. Synthesis of sequential circuits. Impossible specifications. Converting verbal specifications to state diagrams.
    Readings: Sections 9.1, 9.2

  34. 4/15/05: Equivalence classes of states. Pair table method to determine equivalence classes. Synthesis of synchronous sequential circuits using D flip flops. Internal variable assignment.
    Readings: Section 9.3

  35. 4/18/05: Pair table (or "array") method to obtain equivalence classes of states for completely specified flow tables.
    Readings: Section 9.4

  36. 4/20/05: Incompletely specified flow tables: compatibility classes, obtaining compatibility classes using pair table (or "array" method)

  37. 4/22/05: Incompletely specified flow tables: maximal compatibility classes, obtaining reduced flow tables. Internal variable assignment for fundamental mode tables.
    Readings: Section 9.5

  38. 4/25/05: Internal variable assignment for fundamental mode tables. Testing of digital circuits.

  39. 4/27/05: Built-in-self-test. Linear feedback shift registers (LFSR). Multiple input shift-register (MISR). Scan chains.
    Readings: Sections 10.4-1, 10.6-1 (pages 455-460), 10.6-2

  40. 4/29/05: Checking experiment. Built-in self-test.
    Handout on finite state machines (filename: fsm2.pdf) --  this handout was distributed previousl, but the material on checking experiment was not covered previously. Checking experiment is now covered, and included for the final exam.

  41. 5/2/05: Regular expressions (synthesis and analysis)
    Regular expressions will NOT be included for the final exam

  42. 5/4/05: Review lecture



Related Information: