| Logic Circuit Synthesis |
| Synthesizing Switching Functions |
| Ways to Specify Switching Functions |
| Logic circuit | |||
| Functional expression | |||
| SOP form | |||
| Minterm expansion | |||
| Truth table | |||
| Compressed truth table | |||
| BDD (Binary Decision Diagram) | |||
| Index number | |||
| Plot on a hypercube | |||
| Plot on a Karnaugh map | |||
| Note the Connection |
| Definition of ÒmintermÓ |
| In the context of an n-variable switching function, a minterm is a function that is a conjunction (ÒandÓ) of each variable or its complement (but not both). | |
| Minterm Examples (4 variables: u, v, w,
x): uvÕwÕx uÕvwÕx |
|
| Non-Minterm Examples (4
variables): uv x uvw uÕuvw |
| Note the Connection |
| Shorthands |
| These are Equal |
| The number of switching functions of
n variables. |
|
| The number of ways to assign 0 or 1 to the 2n rows of the truth table. | |
| The number of subsets of {0, 1, 2, É, 2n -1} |
|
| 2 |
| Number of Switching Functions |
| 2 | |
| n = 1: 22 = 4 | |
| n = 2: 24 =16 | |
| n = 3: 28 = 256 | |
| n = 4: 216 = 65,536 | |
| n = 5: 232 = 4,294,967,296 | |
| n = 6: 264 = 18,446,744,073,709,551,616 | |
| The 16 switching functions
of 2 variables |
| Implication Lattice of
2-variable functions |
| Logic Synthesis: Abstraction to Implementation |
| From: Verbal problem description | |
| To: Implementation as a network of
basic switching functions |
| Logic Synthesis: Stages |
| Provide verbal problem description. | |
| Tabulate description as function on finite sets. | |
| Encode finite sets into bits. | |
| Transcribe the encoded tables. | |
| Split into individual switching functions. | |
| Realize as a network of basic gates. |
| Example |
| Provide verbal description: Implement a Òmod 3 adder using logic gatesÓ | |
| A definition of mod3 addition: f(a, b) = (a+b)%3; where a, b ë {0, 1, 2} |
| Tabulate definition of function |
| Encode sets into bits |
| Set to be encoded: {0, 1, 2} | |
| Chosen encoding (among many): 0 ¨ 00 1 ¨ 01 2 ¨ 10 |
| Transcribe the Function to the Encoded Values |
| Split the Encoded
Function into individual switching functions |
| The resulting switching functions generally will only be partially specified; some combinations donÕt occur. |
| As the unspecified values will never occur, we can give the function either value 0 or 1. |
| Exercise: Òread offÓ the expression for f2. |
| Exercise: Òread offÓ the expression for f2. |
| Realize each function by gates |
| Check by ÒReverse
EngineeringÓ (Try all combinations; one combination is shown) |
| Rex Program for Checking all Combinations |
| The Testing Code |