ECE HW 2

1 ECE 2020 IE-1 Fall 2023 Homework 2 Assigned: Tuesday, 12 September, 2023 Due: Sunday, 24 September 2023, 11:59 PM (ET) Total Points: 6 questions, 100 points QUESTION 1 (4 x 5 pts = 20 points) Find minimized logic expressions for the following functions using K-Maps. Perform K-Map minimization in the specified POS or SOP form (If not specified, you may use either form). Show your steps. In each case, specify whether it is better to implement the circuit as a SOP or a POS form. Justify your answer. (a) 𝑭𝑭 𝟏𝟏 = 𝑨𝑨𝑩𝑩 ′ 𝑪𝑪 + 𝑨𝑨 ′ 𝑩𝑩𝑪𝑪 ′ + ( 𝑨𝑨 ′ 𝑩𝑩 + 𝑪𝑪 ) ′ + 𝑨𝑨′𝑩𝑩′𝑪𝑪′ (POS Form) (b) 𝑭𝑭 𝟐𝟐 = ∑ 𝒎𝒎 ( 𝟎𝟎 , 𝟐𝟐 , 𝟑𝟑 , 𝟕𝟕 , 𝟏𝟏𝟎𝟎 , 𝟏𝟏𝟏𝟏 ) 𝑾𝑾 , 𝑿𝑿 , 𝒀𝒀 , 𝒁𝒁 (c) 𝑭𝑭 𝟑𝟑 = ∏ 𝑴𝑴 ( 𝟓𝟓 , 𝟔𝟔 , 𝟖𝟖 , 𝟏𝟏𝟏𝟏 ) 𝑨𝑨 , 𝑩𝑩 , 𝑪𝑪 , 𝑫𝑫 ⋅ 𝒅𝒅 ( 𝟏𝟏 , 𝟑𝟑 , 𝟕𝟕 , 𝟏𝟏𝟎𝟎 ) (d) See truth table below. Also write the canonical minterm sum ( ∑ 𝑚𝑚 (__) 𝐴𝐴 , 𝐵𝐵 , 𝐶𝐶 , 𝐷𝐷 ) expression for this function, using 𝑑𝑑 (__) notation for the don’t-care conditions: A B C D 𝑭𝑭 𝟏𝟏 A B C D 𝑭𝑭 𝟏𝟏 0 0 0 0 0 1 0 0 X 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 X 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 X 1 1 1 0 1 0 1 1 X 0 1 1 1 1 X QUESTION 2 (5 x 3 pts = 15 points) Prove the following theorems & identities using K-map minimization (i.e., show that the minimized K-maps of both LHS and RHS are identical, or that the K-map minimization of LHS gets you the RHS expression) : (a) 𝑋𝑋 + 𝑋𝑋 ′ 𝑌𝑌 = 𝑋𝑋 + 𝑌𝑌 (b) Covering Law : 𝑋𝑋 + 𝑋𝑋 . 𝑌𝑌 = 𝑋𝑋 (c) Both De Morgan’s Laws for 2 variables (You may use a 2 variable K-Map). Hint : You need to use both the POS & SOP approaches for this solution. (d) Consensus Law : 𝑋𝑋𝑌𝑌 + 𝑋𝑋 ′ 𝑍𝑍 + 𝑌𝑌𝑍𝑍 = 𝑋𝑋𝑌𝑌 + 𝑋𝑋 ′ 𝑍𝑍 (e) Combining Law : ( 𝑋𝑋 + 𝑌𝑌 ) ⋅ ( 𝑋𝑋 + 𝑌𝑌 ′ ) = 𝑋𝑋

2 QUESTION 3 (15 points) Answer the following using either TRUE / FALSE, multiple-choice, or by filling in the blanks: (a) A don’t-care condition gate can only be used as a ‘0’ when minimizing in a K-Map (CIRCLE ONE) TRUE / FALSE (b) Which minterm is indicated by the cell X & which maxterm by cell Y in the K-map below? Give the Boolean expression for these terms and the values in these K-map cells if these terms are present in a function. (2 points) AB CD . 00 01 11 10 00 01 X 11 10 Y . ANSWER X: __________ value: _______ Y: __________ value: _______ (c) An OR & a NOT gate together form a universal / complete set. TRUE / FALSE (d) How many cells does a 5-variable K-Map have? ANSWER __________ (e) A 7400 IC has 4 NOR gates. TRUE / FALSE (f) How many cells in the K-Map are valued ‘1’ for the 4-variable logic expression: 𝑭𝑭 = 𝑨𝑨𝑩𝑩 ′ 𝑪𝑪 + 𝑪𝑪𝑫𝑫 ′ + 𝑨𝑨𝑩𝑩𝑫𝑫 (2 points) ANSWER __________ (g) A self-dual logic function is a function 𝐹𝐹 such that 𝐹𝐹 = 𝐹𝐹 𝐷𝐷 , where 𝐹𝐹 𝐷𝐷 is the dual of 𝐹𝐹 . Which of the following are self-dual functions? (Circle all that apply) (2 points) A) 𝐹𝐹 = 𝑋𝑋 B) 𝐹𝐹 = 𝐴𝐴 ⊕ 𝐵𝐵 C) 𝐹𝐹 = 𝑋𝑋𝑌𝑌 + 𝑌𝑌𝑍𝑍 + 𝑍𝑍𝑋𝑋 D) 𝐹𝐹 = ∑ 𝑚𝑚 (0,2,4,5) 𝑋𝑋 , 𝑌𝑌 , 𝑍𝑍 ANSWER __________

4 The circuit below has a gate delay of 2 μs for the inverter, 3 μs for the NOR gate, and 4 μs for the OR gate. This means that there’s a delay from when the inputs reach the input of a gate, and the time that output is ready to pass to the next gate (or to the output). (2 points) What is the maximum propagation delay for the circuit? ( hint: think about all the possible pathways for signals from A , B , and C to the output, and trace how long each takes to get to F ). (2 points) Both A & B change from 0 to 1 at time t = 0 μs, w hile C = 0 throughout. Which of the following timing waveforms is observed? ANSWERS: Max. Propagation Delay: __________ Timing Waveform: __________ . A) C) B) D)

5 QUESTION 4 (15 points) PRIORITY CIRCUIT: The space crunch at a certain ‘University’ is getting unmanageable! Conference rooms are at a premium. Often, three meetings are scheduled for the same room. The new Dean, after being locked out of a room he thought he’d reserved, decides to investigate the matter, and realizes the problem – the reservation system is broken because there are no good engineers available in-house. This isn’t surprising – after all, this is a university that requires 3 pillars to build an arch. Desperate, the Dean calls Georgia Tech’s ISyE Chair for help. The chair has tasked our class with fixing this problem. Your mission, should you choose to accept it, is to design a circuit that will reserve a room according to a priority system. The system has the following specifications: • There are two types of rooms : Conference Rooms and Classrooms. • There are 8 types of users, who are given a specific number : You may represent each of these types by a single-bit Boolean variable ( 𝐴𝐴 7 to 𝐴𝐴 0 ). The eight user types are: a. Deans (type 1, denoted by variable 𝐴𝐴 7 ), b. Chairs (type 2, variable: 𝐴𝐴 6 ), c. Faculty (Type 3, variable: 𝐴𝐴 5 ), d. Staff (Type 4, variable: 𝐴𝐴 4 ), e. Grad Students (Type 5, variable: 𝐴𝐴 3 ), f. TAs (Type 6, variable: 𝐴𝐴 2 ), g. Undergrads (Type 7, variable: 𝐴𝐴 1 ), and h. Student Clubs (Type 8, variable: 𝐴𝐴 0 ). • When a reservation request is received, based on the room type, the system outputs a number from 1 to 8 denoting the user type whose reservation has been accepted. Only one output is given by the system for each room, based on the highest priority requester for that room. This number is output using the 4- bit binary value of that number (e.g., type #7 = ‘0111’). You may represent this using the 4-bit output, 𝑅𝑅 3 𝑅𝑅 2 𝑅𝑅 1 𝑅𝑅 0 . For easy reference, I have attached a table of these values at the end of this homework. • Conference Room priority : Deans > Chairs > Faculty > Staff > TAs > Graduate Students > Student Clubs > Undergraduates. • Classroom priority : Deans > Chairs > Faculty > TAs > Student Clubs> Staff. Neither undergrad nor grad students are allowed to reserve classrooms. A. Write truth tables for the reservation priority function for the two room types. Since there are 8 inputs, the table will be far too large (256 row) to show exhaustively. Instead, use don’t- care conditions to shrink the table to a manageable size. ( 10 points ) B. Then, using the truth table, design priority circuits for the classrooms (no need to design circuits for conference rooms) . Provide Boolean expression(s) for each circuit. Each output bit will have a circuit of its own, using all the input bits. You do NOT need to draw the circuits . Just provide the Boolean expressions. ( 5 points ) Remember that all user types might not reserve a room at the same time, so you need to also consider cases where a higher priority user is not requesting a room.

7 7-SEGMENT DISPLAY DECODER CIRCUIT This circuit will be used with the priority circuit we designed in question 3 to indicate above each room the user type (Types 1 through 8) who has been granted the room reservation. If the room is not reserved, the display shows ‘0’; if the room is under maintenance, the display shows ‘9’. Let’s start with some simple questions: ( 4 x 1 point = 4 points) (a) What is the smallest number of bits, ‘ K ’ that the data signal needs to have to display digits from 0 to 9 on the 7-segment display? (We call ‘ K ’ the ‘ bus size ’) (b) What is the output bus size required to drive the 7-segment display (‘ N ’ in the diagram) (c) For the output bus size calculated in part (b), how many output combinations are possible? (d) What should be the data bus size if we wanted to use every single combination supported in the output bus? Now, let’s get to the real work. Choose any TWO of the seven segments (A-G) in the seven-segment display. Indicate which two segments you’ve chosen. (e) Using K-Maps, design driver circuits to drive the two segments you’ve chosen on the 7-segment display. The input to this circuit is the 4-bit data from the input bus, where the 4 bits represent the decimal digit in binary code (i.e., 5 = 0101, 7 = 0111, etc.). Show the Karnaugh maps for both circuits, and indicate the prime implicants, and the minimized Boolean expression (you may use either sum or product form). Show the schematic for the circuits. ( Hint : Since we are only using input numbers from 0 to 9, the input values from 1010 to 1111 are not used and can be marked as don’t-care conditions). (6 points) (f) You try and create this circuit and order parts from the local Radio Sha… oh wait!...alright, the local electronics hobby store. Unfortunately, they inform you that they only have 7400 IC Chip which contains 2-input NAND gates. Choose ONE of your two segments , and using mixed-logic manipulation, convert your driver circuit for this segment to use NAND gates only. Draw the NAND-only circuit diagrams. (3 points) (g) In point (e), I mentioned that you could use don’t-care conditions to simplify the circuit design by ignoring inputs combinations 1010 to 1111. Can you identify how this might be a problem if we were implementing our circuit in real life? How would you prevent this from occurring? (2 points)

8 QUESTION 6 (4 x 5 pts = 20 points) a) Express the function computed by this circuit (do NOT simplify this circuit or the Boolean expression): For parts (b) – (d), using mixed logic notations, convert the circuits or Boolean expressions to the appropriate forms. Show an intermediate state of the circuit in your working steps. b) Convert to NAND-only implementation: 𝑭𝑭 = 𝑨𝑨𝑩𝑩 + 𝑪𝑪 ′ 𝑫𝑫 ( 𝑨𝑨 + 𝑩𝑩 ′ ) ′ + ( 𝑩𝑩𝑪𝑪 ′ ) ′ + ( 𝑨𝑨 + 𝑫𝑫 ′ ) ′ c) Convert to NOR-only implementation: d) The mixed-logic schematic below uses only NAND gates & inverters. Redraw the circuit using mixed-logic methods to use only NAND & NOR gates, eliminating the need for inverters.

10 BONUS QUESTION 2 (15 points) This is a cool little proof for the mathematically inclined. You can receive up to 15 bonus points (to make up for any points lost in the previous questions) for a correct answer to this question, with partial credit for partially correct answers / approaches or attempts. Prove that the POS form of any 𝑛𝑛 -variable Boolean function, 𝐹𝐹 is the product of the set complement of indexed minterms. That is, prove that if: 𝐹𝐹 = � 𝑚𝑚 𝑖𝑖 𝑖𝑖 ∈ 𝐼𝐼 Where 𝐼𝐼 is an index set of minterms, 𝑚𝑚 𝑖𝑖 that make up the POS representation of 𝐹𝐹 , then 𝐹𝐹 = � 𝑀𝑀 𝑗𝑗 𝑗𝑗 ∈ 𝐼𝐼 𝑐𝑐 Where 𝐼𝐼 𝑐𝑐 = 𝑆𝑆 \ 𝐼𝐼 is the complement of the index set 𝐼𝐼 with respect to the sample set of all possible indices, that is 𝑆𝑆 = { 0, 1, 2, 3, … , 2 𝑛𝑛 − 1 } , and ′ \ ′ represents a set subtraction. Hints: 1) Apply the generalized De Morgan’s laws. 2) Remember that the sum of ALL minterms = 1, and the product of ALL maxterms = 0. Think about how that interacts with the complementarity law. 3) Consider what the complement of a minterm for a specific index, 𝑖𝑖 is in terms of the maxterms.

11 BRAIN TEASER QUESTIONS NOT FOR POINTS The two questions below are a brainteasers that might interest the mathematically-inclined among you. There is no need submit solutions to these with your homework submission (If you’d like, you can indicate in the homework if you tried them & want to discuss the solution / approach). These questions are for your amusement and curiosity only but do feel free to discuss them during office hours. BRAIN TEASER #1 If a logic function 𝐹𝐹 of 𝑛𝑛 -variables is described in its SOP form as 𝐹𝐹 = � 𝑚𝑚 𝑖𝑖 𝑖𝑖 ∈ 𝐼𝐼 And its dual is denoted as 𝐹𝐹 𝐷𝐷 , can you find a quick rule to find the SOP form of its dual function without having to expand or simplify the logic expression? That is, if the dual function is expressed as 𝐹𝐹 𝐷𝐷 = � 𝑚𝑚 𝑗𝑗 𝑗𝑗 ∈ 𝐽𝐽 find a rule to connect the indices 𝑖𝑖 ∈ 𝐼𝐼 with the dual indices 𝑗𝑗 ∈ 𝐽𝐽 . What should the constraints be on 𝐼𝐼 and 𝐽𝐽 for 𝐹𝐹 to be a self-dual function? If you are provided with an array of size 2 𝑛𝑛 , containing the truth table values for the function, can you write a simple procedure to check if the function is self-dual? Hint : You can apply a similar approach to that in bonus question 2. BRAIN TEASER #2 How many non-trivial logic functions are there of 𝑁𝑁 variables? Here, “non-trivial” (also called a ‘non- degenerate’ function) means that all the variables affect the function output . Hint : This requires either a recursion formula or a sum expression. The list of all logic functions of n-variables includes every single logic function of (n-1) variables, which itself includes every single logic function of (n-2) variables, and so on and so forth. Since you have ‘n’ variables, you’d need think about how many combinations of choices you have of (n-1), (n-2), etc. variables from that set of ‘n’ variables. But beware, there’s some double-counting involved here. Every set of (n-1) variable functions includes common elements. For e.g., F = 1, and F = 0 are included in all of these lists, and the set of functions of variables A & B are included in both the set of functions of variables (A, B, C) and (A,B,D). You need to account for these when you’re calculating the number. The inclusion-exclusion principle might help here.