Introduction to Logic Circuit Design (University of Utah) - Practice Midterm Exam (Lecture 16)
Overview
The University of Utah ECE/CS 3700 practice-midterm review works through Boolean identity testing, remainder-circuit design, Karnaugh maps, CMOS pull-up and pull-down duality, Shannon expansion, and a 4-bit adder. It emphasizes practical verification and implementation methods, including counterexamples, don’t-care conditions, mux decomposition, and two’s-complement subtraction; the final long question is left for a posted solution.
Key takeaways
- A Boolean identity is disproved by one input assignment with unequal outputs, while proving it requires showing agreement for every input combination or an equivalent algebraic derivation.
- For the two-bit remainder circuit, C=00 is a don’t-care condition because division by zero is undefined; those map cells can simplify the R1 and R0 logic.
- POS expressions are derived by grouping zero-valued maxterms, and minterm indices absent from both the minterm and don’t-care lists identify those zero cells.
- A CMOS pull-up network is the dual of its pull-down network: swap NMOS for PMOS and interchange series and parallel connections.
- Shannon expansion maps directly onto a 2-to-1 mux: the expanded variable is the select signal, and the zero and one cofactors become the two data inputs.
- For 4-bit two’s-complement arithmetic, X − Y is implemented as X + Y′ + 1; the XOR of the sign bits selects addition when signs differ and subtraction when they match.
Chapters
- The practice midterm is presented as a review of key material expected on the Thursday exam at 3:40 p.m.
- Students may bring one double-sided A4 cheat sheet, but calculators and cell phones are not allowed.
- Homework 7 is due November 1; office hours are scheduled for noon to 1:00 p.m. and an extra session from 5:00 to 6:00 p.m.
- For F(A,B,C) = AC + BC′, substitute A′, B′, and C′ into the function to form F(A′,B′,C′), and use De Morgan’s law to derive F′.
- A single input assignment where the two expressions differ disproves an identity; the lecture uses A=0, B=1, C=1 as a counterexample.
- For F = AB + AC + BC, the transformed expression simplifies to the same result as F(A′,B′,C′), demonstrating that the proposed equality holds for this function.
- A truth table with 2³ = 8 rows can confirm equality across every input combination.
- The circuit takes two-bit dividend D and divisor C inputs and produces a two-bit remainder R for D divided by C.
- When C=00, division is undefined, so all four corresponding input combinations are marked as don’t cares.
- The example 3 divided by 2 produces remainder 1, encoded as R1R0=01.
- The full truth table has 16 rows because the combined inputs contain four bits.
- R1 and R0 are treated as separate Boolean outputs, each with its own Karnaugh map.
- The don’t-care entries for C=00 can be used when forming larger K-map groups to simplify the output expressions.
- The resulting circuit uses a four-input AND for R1 and a two-input OR combining product terms for R0.
- Input complements such as D0′ and C0′ require explicit inverters because only the original input signals are assumed available.
- The task asks for a minimum-cost product-of-sums expression even though the function is initially specified using minterms and don’t cares.
- For a five-variable map, indices run from 0 through 31; indices not listed as minterms or don’t cares become maxterms, corresponding to zero cells.
- POS simplification groups zeros, while don’t-care cells remain available to help form larger groups.
- The variable ordering must remain consistent: A is the most significant bit and E is the least significant bit, regardless of the map’s layout.
- The pull-down network has C and D in series, that combination in parallel with B, and the result in series with A.
- The pull-up network is the dual: replace NMOS devices with PMOS devices and interchange series and parallel connections.
- The resulting pull-up topology places C and D in parallel, in series with B, with the branch in parallel with A.
- The pull-down network represents F′ = A(CD + B), so De Morgan’s law gives F = A′ + B′(C′ + D′).
- The function is specified by minterms, including M0 = A′B′C′ and M6 = ABC′; Shannon expansion is applied to the unsimplified minterm function.
- Expanding on A gives F|A=0 = B + C′ and F|A=1 = BC′.
- A single 2-to-1 multiplexer uses A as its select signal, with B + C′ on the A=0 input and BC′ on the A=1 input.
- The two data-input functions can be built from basic gates while preserving the Shannon-expansion structure.
- The B + C′ and BC′ data-input functions are each decomposed using another Shannon expansion on B.
- For B + C′, the mux data inputs are C′ and constant 1; for BC′, they are constant 0 and C′.
- Together with the outer mux controlled by A, the implementation uses three 2-to-1 multiplexers.
- One inverter produces C′, and constant 0 and 1 values are assumed available.
- The circuit accepts two 4-bit two’s-complement inputs, X and Y, and produces a 4-bit output Z.
- When the sign bits X3 and Y3 match, the required result is X − Y; when they differ, the result is X + Y.
- A 4-bit 2-to-1 mux selects between the two arithmetic results, and a 4-bit adder is provided as a reusable block.
- XNOR(X3,Y3) identifies matching sign bits, while XOR(X3,Y3) can serve as the mux control for selecting addition versus subtraction.
- The X + Y branch feeds X and Y to a 4-bit adder with carry-in set to 0.
- The X − Y branch uses X + Y′ + 1: invert all four bits of Y and set the adder carry-in to 1.
- The XOR of X3 and Y3 controls the output mux: XOR=0 selects subtraction, while XOR=1 selects addition.
- The design combines two 4-bit adder paths, a 4-bit 2-to-1 mux, sign-bit logic, and the required Y-bit inversions.
- The final long practice question is not worked through during class; its complete solution is to be uploaded after the lecture.
- The review closes by inviting questions about the circuit designs and the exam material.
Transcript excerpt
0:50 All right. Well, I hope everyone I hope you all are doing well. Okay, guys. We have started. So, today in our lecture 15, we're going to solve the practice midterm that I uploaded earlier on Canvas. I hope you guys could find time to go over it. So, because today we cannot spend time on giving you guys to solve and we're going to solve it all together here. There are multiple questions that we want to go over and it I think covers all the material the important materials at least what we're going to have for the midterm. Midterm is going to be on Thursday at class 3:40 p.m.
1:40 Homework 7 deadline is November 1st. I uploaded that. I changed the due date. It was supposed to be this week, but it seems we didn't cover the material for chapter 5. I moved that to the next week. No discussion session tomorrow, but I'm going to have an extra office hour from 5:00 to 6:00 p.m. at my office. Uh tomorrow I have another office hour, my usual office hour at noon to 1:00. If you have any questions regarding the midterm or any other thing in the class. Uh all homework uh homework 4, 5, and 6, lab two and quiz two are graded. Uh I uh wait until that Thursday, the one week after when we announce the when we release the grade to uh post the grade on Canvas.
2:28 Since basically I don't want to change any grades afterward. If you see any inconsistency between the grade on Gradescope uh and on Canvas, check for if you have been uh tagged as a late. Uh if you are late, uh whatever that you see on Gradescope is your actual grade. Whatever you're seeing the Canvas is basically after 25%
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MEDAL-Research.