Introduction to Logic Circuit Design (University of Utah) - Shannon Expansion (Lecture 13)
Watch on YouTube →
Overview
The lecture develops multiplexer-based logic synthesis, showing how truth-table rows can be grouped by select variables and translated into multiplexer data inputs. It introduces Shannon expansion as the cofactor-based method behind this process, connects multiplexers to binary decision trees and universal logic implementation, and motivates reducing the resulting mux networks for efficiency.
Key takeaways
- A 4:1 multiplexer has two select inputs, so fixing the two select-variable values partitions a truth table into four data-input cofactors.
- Shannon expansion implements a Boolean function by selecting a variable and combining its two cofactors: f = x·f|x=1 + x'·f|x=0.
- Multiplexer data inputs need not be constants; they can be expressions such as W2 OR W3 or other functions of the variables not used as selects.
- A binary decision tree made of muxes can represent an arbitrary Boolean function, with variables controlling internal nodes and minterms or constants at the leaves.
- The number of muxes alone does not determine implementation quality; the complexity of the cofactor logic and the structure of the network also matter.
- A full mux decision tree is a systematic but potentially inefficient implementation, which motivates simplifying Shannon expansions and reducing mux count.
Chapters
- The quiz was scored out of 10 points with 2 bonus points, and the lowest of four quizzes will be dropped.
- The lecture continues combinational-logic synthesis, focusing on multiplexers, binary decision trees, and Shannon expansion.
- The stated design goal is to implement each Boolean function with the allowed mux count and as little additional logic as possible.
- A 4:1 multiplexer uses two control signals, so the example groups truth-table rows by W1 and W2.
- After fixing W1 and W2, the remaining rows define each mux data input as a function of W3.
- Different choices of control variables can produce equivalent circuits with different structures.
- The next implementation uses two 2:1 multiplexers and treats W1 as the select signal for the outer mux.
- The data inputs are derived by examining the function over the corresponding truth-table row groups.
- One cofactor in the worked discussion reduces to W2 OR W3, illustrating how a mux input can be a simpler Boolean expression rather than a single variable.
- The class compares mux-based implementations by checking the logic required to construct each data input, not just the number of mux symbols.
- For each selected-variable assignment, the remaining truth-table rows must share one consistent cofactor function.
- The discussion emphasizes that a cofactor may be a constant, a variable, or a compound function of the unselected inputs.
- A further example partitions the function by W1, then derives the corresponding input functions using W2 and W3.
- The lecture uses the same truth-table grouping procedure to translate each partition into a 2:1 mux data input.
- A more complicated cofactor, including an XOR-like case, can be implemented with an additional mux instead of being treated as an opaque input.
- The lecture generalizes from individual examples to the claim that arbitrary Boolean functions can be built from multiplexers and suitable data inputs.
- NAND is also recalled as a universal gate, with sum-of-products logic and De Morgan's law providing the implementation connection.
- The central synthesis procedure is to select a variable, split the function into cofactors, and recursively implement those cofactors.
- A binary decision tree represents each internal decision with a mux controlled by a Boolean variable such as A, B, or C.
- For a three-variable function, the tree's leaves correspond to minterms, including labels such as m2 and m3 in the worked diagram.
- The tree demonstrates universal mux implementation, while the lecture flags its potentially large mux count as an optimization problem for the next lecture.
Transcript excerpt
0:11 All right. I hope you had a good quiz sorry for the typo. I hope that was not disturbing. as mention if you have even written in max I'm going to give the point it's basically it would be as long as you are consistent that should be fine and as long as you have recognized the groups correctly then that should be to get the full credit anyway the quiz was out of 102 we had two bonus points so if we get consider max points in this quiz that would help you boosting your grade and
1:00 there were some questions regarding quiz one in general as we mentioned earlier we gna drop the lowest great quiz that basically if you didn't do a great job on quiz one that's something that you can use. So we have four quizes and we going to drop the one of the the list grade that you get. So I hope that helps. All right. So today we are going to continue our combination logic circuits. We gna talk more we gna solve more examples of how to synthesize logic circus using multiplexers. get familiar with binary decision a way that we can design all circuits using multiplexers
1:47 so multiplex is a universal block then we gna get no shanon expansion a way that we can little bit simplify this that binary decision tree again we still we are in the format of multiplexers then we gna see how we can reduce channel expion further simplify all right homework deadline would be this upcomingay at 1159 any questions regarding quiz regarding grades or anything again if you have any request for regading your quiz homework lab anything please submit it on grade scope
2:34 if you need to talk to me about that to
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
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.