ECE HW 5

ECE 2020 IE-1 Fall 2023 Homework 1 Assigned: Monday, 28 August 2023 Due: Sunday, 10 September 2023, 11:59 PM (ET) Total Points: 7 questions, 100 points QUESTION 1 (3 x 5 pts = 15 points) Draw switching circuits for the following Boolean expressions. Do not simplify these expressions. (a) ( 𝑨𝑨 ⋅ 𝑩𝑩 ) + 𝑪𝑪 ⋅ ( 𝑨𝑨 + 𝑩𝑩 ) (b) ( 𝑨𝑨 ⋅ 𝑩𝑩 + 𝑩𝑩 ⋅ 𝑪𝑪 ) ⋅ 𝑫𝑫 + 𝑨𝑨 (c) 𝑨𝑨 ′ + 𝑨𝑨𝑩𝑩 + 𝑪𝑪 ′ 𝑫𝑫 Applying the laws of Boolean Algebra, can either of these networks be simplified? If so, provide the Boolean expressions for the simplified network, and the working steps. You do NOT need to draw the simplified switching circuits, just provide the simplified expressions. For part (c), do not use complemented variables (i.e., 𝑨𝑨 ′ ) to control the switch(es). Instead, wherever required, use normally-closed switches to implement the complement operation. QUESTION 2 (3 + 3 + 4 + 5 pts = 15 points) Prove the following Boolean identities. Where specified, solve them only in the manner requested. (a) 𝑿𝑿 + 𝑿𝑿 ′ ⋅ 𝒀𝒀 = 𝑿𝑿 + 𝒀𝒀 . Prove this using either the truth tables or the 5 fundamental axioms only. (b) ( 𝑿𝑿 ⨁ 𝒀𝒀 ) ′ = 𝑿𝑿𝒀𝒀 + 𝑿𝑿 ′ 𝒀𝒀 ′ . (c) Transposition Theorem : 𝑨𝑨𝑩𝑩 + 𝑨𝑨′𝑪𝑪 = ( 𝑨𝑨 + 𝑪𝑪 ) ( 𝑨𝑨′ + 𝑩𝑩 ) . Prove this by manipulating basic Boolean relations only (not truth tables). (d) Redundancy Theorem: 𝑨𝑨𝑩𝑩 + 𝑩𝑩𝑪𝑪′ + 𝑨𝑨𝑪𝑪 = 𝑨𝑨𝑪𝑪 + 𝑩𝑩𝑪𝑪′ . Also provide a short (2-3 sentence) explanation of the implication / significance of this theorem.

QUESTION 3 (10 points) Prove De Morgan’s Laws for two Boolean variables, 𝐴𝐴 1 and 𝐴𝐴 2 . From this, prove the generalized De Morgan’s Laws for an arbitrarily large number of inputs: ( 𝐴𝐴 1 𝐴𝐴 2 𝐴𝐴 3 … 𝐴𝐴 𝑛𝑛 ) ′ = 𝐴𝐴 1 ′ + 𝐴𝐴 2 ′ + 𝐴𝐴 3 ′ + ⋯ + 𝐴𝐴 𝑛𝑛 ′ 𝑎𝑎𝑎𝑎𝑎𝑎 ( 𝐴𝐴 1 + 𝐴𝐴 2 + 𝐴𝐴 3 + ⋯ + 𝐴𝐴 𝑛𝑛 ) ′ = 𝐴𝐴 1 ′ ⋅ 𝐴𝐴 2 ′ ⋅ 𝐴𝐴 3 ′ ⋅ … ⋅ 𝐴𝐴 𝑛𝑛 ′ Hint: Use mathematical induction (which you learned in discrete math or high school) to prove the general case. If you aren’t familiar with induction, reach out to me and I’d be happy to explain it to you.

(f) What hierarchical level is associated with circuit descriptions using block diagrams? A) System Level B) Register-Transfer Level C) Logic Level D) Circuit Level ANSWER __________ (g) What aspect of a switching network (rather than a gate circuit) does the Boolean expression describe? A) The input(s) to the network B) The output of the network C) The network itself D) None of the above ANSWER __________ (h) Connect the left and right columns: 𝐴𝐴𝐴𝐴𝐴𝐴′ PoS form 𝐴𝐴𝐴𝐴𝐴𝐴 ′ + 𝐴𝐴𝐴𝐴′𝐴𝐴 Maxterm 𝐴𝐴 + 𝐴𝐴′ + 𝐴𝐴 SoP form ( 𝐴𝐴 + 𝐴𝐴 + 𝐴𝐴 ′ )( 𝐴𝐴 + 𝐴𝐴′ + 𝐴𝐴 ) Minterm . (i) What is the minimum number of 2-input AND, OR, and NOT gates required to implement the following Boolean function: 𝐹𝐹 = 𝐴𝐴𝐴𝐴 ′ 𝐴𝐴 + 𝐴𝐴 ′ 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐴𝐴 ′ + 𝐴𝐴′𝐴𝐴𝐴𝐴′ ANSWER __________ (j) If an analog signal is only sampled in time, it is converted to a digital signal. (1 point) TRUE / FALSE (k) How many Boolean functions are possible with 4 variables? ANSWER __________

QUESTION 5 (15 points) A designer is trying to create an error detection circuit for a data communications system. The data arrives in ‘packets’ that are 4-bits long. You can denote these bits as 𝐴𝐴 3 , 𝐴𝐴 2 , 𝐴𝐴 1 , and 𝐴𝐴 0 , where 𝐴𝐴 3 is the leftmost (4 th ) bit, and 𝐴𝐴 0 is the rightmost (1 st ) bit. The communications protocol used imposes certain conditions on the data packets. If any of these rules are broken, the data is in error: 1) There must be at least one ‘1’ in the data packet. 2) ‘1’s must NOT occur on neighboring bit positions. 3) 𝐴𝐴 3 must be a ‘0’, UNLESS either 𝐴𝐴 2 or 𝐴𝐴 1 is ‘1’, but not both at the same time. In the case where exactly one among 𝐴𝐴 2 or 𝐴𝐴 1 is ‘1’, 𝐴𝐴 3 can take any value without error. (a) Using only basic logic gates (i.e., 1-input NOT gate and 2-input AND / OR gates), design error- detection logic circuits that test if each of these rules have been broken. Provide the Boolean expressions and logic diagrams for these circuits. You will have one circuit for each of these rules. Explain your design process as you complete the solution. (b) How many gates are used in each circuit? Provide a split of these by gate type (i.e., number of AND, OR, NOT, or other types of gates). (Hint: Don’t overthink this too much. Think about it like a puzzle. If you are struggling with designing the circuits, or creating the Boolean Expressions, reach out to me, and I’ll be happy to help)

QUESTION 7 (5 + 7 + 3 = 15 points) One of the theorems that was not mentioned in the lectures is Shannon’s expansion theorem: 𝐹𝐹 ( 𝑋𝑋 1 , 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 ) = 𝑋𝑋 1 ⋅ 𝐹𝐹 (1, 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 ) + 𝑋𝑋 1 ′ ⋅ 𝐹𝐹 (0, 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 ) 𝐹𝐹 ( 𝑋𝑋 1 , 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 ) = [ 𝑋𝑋 1 + 𝐹𝐹 (0, 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 )] ⋅ [ 𝑋𝑋 1 ′ + 𝐹𝐹 (1, 𝑋𝑋 2 , … , 𝑋𝑋 𝑛𝑛 ) ] These theorems essentially “pull out” a variable from a logic function. (a) Prove Shannon’s expansion theorem. ( Hint : Don’t overthink this. It’s much simpler than you’d think. If you’re using up anything more than a page — let alone a small forest worth of paper — to solve it, you’re doing it wrong. You might want to look up ‘Perfect Induction’ in the textbook or online) . (b) Shannon’s expansion theorems can be generalized to pull out not one but ‘i’ variables, so that a logic function can be expressed as a sum or product of 2 𝑖𝑖 terms. Figure out and state the generalized Shannon’s expansion theorems. Also show some working steps. (c) Can you think of the significance of Shannon’s expansion theorem in terms of advantages it might offer when implementing (complicated) Boolean functions using digital circuits? I do not expect a “correct” answer for this part (if one even exists). What I am looking for is some explanation or ideas that demonstrate critical thinking and engagement with larger concepts discussed in class.

BONUS QUESTIONS You can make up points lost in the main part of the homework by attempting bonus questions below. Bonus credit will be given based on level of detail in and/or the correctness of the solution. BONUS QUESTION 1 (5 points) Can you think of instances in real life where one might encounter quantization and sampling; situations where these effects are noticeable if the quantization or sampling is done incorrectly? You could either give a list of a few examples or choose one or two examples and explain how they involve quantization & sampling. BONUS QUESTION 2 (15 points) Are XNOR gates a universal gate? That is, do they form a complete set of logic gates? It is possible to conclusively prove or disprove this. I’ve provided hints below on how to do that. If you can’t find the rigorous proof (or disproof), you can instead provide a short explanation (or demonstration) of why you think they might or might not form a complete set, for partial bonus. Hint: If you suspect the XNOR cannot be a universal gate, one approach to prove this explicitly could be to consider all possible combinations that can occur when a 2-input XNOR gate is fed with combinations of inputs ‘0’, ‘1’, ‘A’, and ‘B’, then see which new output expressions emerge. Thereafter, you could iteratively figure out combinations of all these possible outputs until you have no new expressions on subsequent iterations. After the last iteration, check if you get the NOT, OR, AND functionality (or another universal gate expression) from within the set of these possible outputs. Please feel free to reach out to me if you are getting stuck on this.