ECE 120 Midterm 2 HKN Review Session Overview of Review CMOS logic, Boolean expressions, Boolean Algebra K-maps, SOP, POS 2-level networks Adders, ALUs, and Bit Slice Design Multiplexers, Decoders Flip-Flops and Latches (S-R & D) FSM Design, Moore Machines Practice Exams! (The not so secret sauce in success) CMOS logic Metal Oxide Semiconductor Field Effect Transistors (MOSFET) N-type: pull-down, voltage applied (1) means it conducts, voltage absent (0) means it is off P-type: pull-up, voltage applied (1) means it is off, voltage absent (0) means it is on

Complementary layout Prevents floating / short-circuited outputs Requires p-type on top (connected to V dd), requires that the top is the dual of the bottom NAND Gate Boolean Expressions and Algebra * indicates AND + indicates OR identity 1*A=A 0 +A=A null

1+A=1 0*A=0 idempotence A+A=A A*A=A complementarity A * A = 0 A + A = 1 DEMORGAN (A + B) = AB

(AB) = A + B involution (x) = x Distribution (A + B)C = AC + BC AB + C = (A + C)(B + C) Consensus (A + B)(A + C)(B + C) = (A + B)(A + C) AB + AC + BC = AB + AC

Duality Principle, Ex. Demorgans Law Duality: swap 1s and 0s, swap ANDs and ORs, maintain precedence using parentheses Complement: find dual, complement each variable m(a,b,c,d) = a + bc + bd Dual: n(a,b,c,d) = a(b+c)(b+d) 1) m(a,b,c,d) = ((a + bc + bd)) 2) m(a,b,c,d) = (a(bc)(bd)) Logical Equivalence 2 ways to prove that two boolean functions are equivalent 1. Use truth tables: if they have the same output over all input combinations then they are logically equivalent 2. Use boolean algebra properties to show equality. Lets prove deMorgans law: (A + B): So, we can see in this truth table that (A+B) is logically equivalent to AB. QED. A

B (A+B) AB 0 0 1 1 0 1 0

0 1 0 0 0 1 1 0 0 Logical Completeness

A set of gates is said to be logically complete if it can implement any boolean expression with exclusively those set of gates. For example, NAND and NOR are individually logically complete as well as AND, OR, and NOT together. How? What about NOT? Is NOT logically complete? What about XOR? K(arnaugh)-maps A way to represent the outputs of a logical design with respect to its inputs Should arrange inputs along row and columns in gray code order. 00 01 11 10 Should be able to form whether asked to from a circuit, problem statement, or a design goal. Can accommodate up to 4 inputs, more requires more than a 2d representation. A, BC-> 01 AND, f(A,B,C): 11

10 Simple example00for a 3-input 0 0 0 0 0 1 0 0 1

0 SOP, POS SOP- Sum of Products A group of products (ANDs) which are being summed (ORd). Example: f(A,B) = AB+AB (XOR) AB and AB are the products, which are summed. POS- Product of Sums A group of sums (ORs) which are being multiplied (ANDd). Example: f(A,B) = (A+B)(A+B) (Still XOR) (A+B) and (A+B) are the sums, which are ANDd. Minimal vs. Canonical A B

0 0 Minimal - Listing terms as efficiently as possible (no redundancy) Can find through the bubbling method on kmaps. Example: f(A,B,C) = A+BC C F 0 0 0 0 1

0 0 1 0 0 Canonical - Listing every term of the function with every input. 0 1 1 1 0

1 Can find through writing out a truth table. 1 0 Canonical SOP: A listing of every set that makes the function return true (ORd) 1 0 1 Example for above f: f(A,B,C) = ABC+ABC+ABC+ABC+ABC 1 1 0 Canonical POS: A listing of every set that makes the function return false 1 1 1

Example for above: f(A,B,C) = (A+B+C)(A+B+C)(A+B+C) 1 1 1 Converting SOP/POS to 2-level NAND or NOR Any 2 level POS circuit can also be converted quickly to a NOR-NOR implementation. Optimized Boolean Expressions When trying to find the Boolean expression for the outputs of an FSM consider both the POS and SOP forms Check which of these minimises the total number of gates Prime implicants The largest grouping of 1s not fully contained by another grouping of 1s (with

power of 2 dimensions, ie. 2,4,8) Uniqueness Look for other prime implicants of equal size that are not currently being used in your minimal expression If you can write another function with the same number of terms, then it is not unique Dont Cares Symbol: X, used if the output can be a 0 or a 1 Can be included in any kmap circling Latches (S-R & D) This SR latch above is active High for S (set) and R (reset) functionality. This SR latch is made from 8 transistors D - Latch C is the enable bit for this

This D - latch is made from 18 transistors How to build Flip-Flops from latches Rising edge triggered flip flop on top, Falling edge triggered flip flop on the bottom. Looking at the top picture we have a rising edge triggered flip flop. How? When the clock is 0, master latch is write enabled, slave latch is write disabled. This way once the edge rises, the master latch becomes write disabled storing/holding the

value of the input Dm from right before the rising edge. The WE of the slave (second) latch goes high allowing the value stored in the master to be written to and stored into the slave latch. Multiplexers and Decoders Multiplexers: n select bits 2n input options 1 output Decoders: 1 enable bit n select bits (input lines specify which output to raise) 2n possible outputs (one high at a time)

Multiplexers and Decoders Implement g(a,b,c,d)=ab+ab+abc+abcd using a 4:1 MUX and no more than one extra gate. A/B/0 B/1 C ~D A/B/1 A B Adders and Bit Slice Design Bit Slice Adder Circuit: broken down into repeated operations on individual bits, this design extends to any # of bits bc slices pass information between them ALUs Combinational logic circuit that performs arithmetic & logic operations on integers

FSMs (Probably Not on Test) An FSM is composed of a set of states, (# of state bits = ceiling( log_2( # states ) ) )