ECE 2020-IE 1 - f23 - Test 3 Prep questions - solutions

ECE 2020 IE-1 Fall 2023 Test 3: Combinational Logic Circuits, Sequential Logic, & Finite State Machines Review & Practice Questions Partial Solutions Notes: This is a set of sample questions for your practice and review for Test 3. Please take note of what this list is NOT : 1) This is NOT an exhaustive bank of questions from which Test 3 will be created. 2) This list is NOT guaranteed to include the entire coverage for Test 3 . It is possible that there will be questions in the test covering topics and of types that might not be indicated by questions in this list. The topic coverage is based on what is announced in the class, on Piazza, and/or on Canvas. In preparation for the test, you should be familiar with all the course content sources, including the lecture notes, resource files on Canvas, textbook(s), course website, etc. 3) This list is NOT guaranteed to provide any specific hints about the nature of questions that might be given on the test. 4) This set is simply an indicative sample to help review some topics covered in the course so far. Solutions will NOT generally be provided for the questions in this document. It is impractical to prepare solutions for such a large number of problems. Please collaborate with your course mates to work on these solutions. If you require assistance, you are encouraged to contact me during office hours. In some cases, only the question numbers (and possibly, page number) are indicated, referring to questions in the prescribed textbook ( ‘ WAK ’ = Wakerly, Digital Design: Principles & Practices , 4 th Edition). Please refer to the textbook for the text of the questions. Please refer to the lecture slides and course schedule for a list of recommended reading sections from the textbook. In some topics, a recommended section might not be listed. You are expected to find the appropriate section in the textbook. If you are unable to find a specific section, please contact me to recommend reading resources for these topics.

A Non-exhaustive list of textbook sections & other topics for Test 3 coverage Textbook : Wakerly, 4 th ed. Legend : - BOLD text indicates significant or complete coverage of the section for this test. - Italicized text indicates that the section content is included in coverage at a very superficial level. Rely on the lecture slides to guide you on how much to read. - Section shown in red : means that only the subsections specified below it are covered, not the rest of the section. COVERAGE CHAPTER 2: Number Systems & Codes - 2.1 Positional Number Systems - 2.2 Octal & Hexadecimal Numbers - 2.3 General Positional Number System Conversions - 2.4 Addition & Subtraction of Non- decimal numbers - 2.5 Representation of Negative Numbers - 2.5.1 Signed-magnitude representation - 2.5.2 Complement Number Systems - 2.5.4 2’s complement number system - 2.5.6 1’s complement number system - 2.6 2’s complement Add & Subtract - 2.6.1 Addition Rules - 2.6.3 Overflow - 2.6.4 Subtraction Rules - 2.6.5 2’s complement & unsigned binary - 2.10 Binary Codes for Decimal Numbers 1 - 2.11 Gray (one-hot) Code 2 CHAPTER 6: Combinational Logic Design - 6.1 Documentation Standards 3 - 6.1.1 – 6.1.5 – Cursory review - 6.1.7 – 6.1.8 - 6.2 Circuit Timing - 6.2.1 Timing Diagrams - 6.2.2 Propagation Delay - 6.4 Decoders - 6.4.1 Binary Decoders - 6.4.3 The 74x138 3-to-8 Decoder - 6.4.4 Cascading Binary Decoders - 6.5 Encoders - 6.5.1 Priority Encoders - 6.5.2 The 74x148 Priority Encoder - 6.7 Multiplexers (6.7.1 – 6.7.3) - 6.10 Adders, Subtractors & ALUs - 6.10.1 Half-Adders & Full-Adders - 6.10.2 Ripple Adders - 6.10.3 Subtractors - Shifters: Arithmetic & Logical Shifters, Overflow & Underflow CHAPTER 7: Sequential Logic Design Principles - 7.1.1 Digital Analysis of Bistable Elements - 7.2 Latches & Flip-Flops - 7.3 Clocked Synchronous State-Machine Analysis - 7.4 Clocked Synchronous State-Machine Design - 7.5 Designing State Machines using State Diagrams - 7.6 State Machine Synthesis using Transition Lists 1 Only BCD will be covered in this section. 2 Very superficial coverage. You only need to know what Gray code is, how it differs from BCD and regular binary number representations. We covered this in K-Maps. 3 Review this so you’ll have familiarity with how to use the terminology, etc. effectively. You will not be extensively tested on this section, but it’ll help ensure that your answers are accurate and correctly described. Much of this was already tested in Tests 1 & 2 .

Provided Information: (in addition to Boolean expressions from Tests 1 & 2) Number Conversions Decimal Binary Hex 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Powers of 2 2 10 1024 2 9 512 2 8 256 2 7 128 2 6 64 2 5 32 2 4 16 2 3 8 2 2 4 2 1 2 2 0 1 2 −1 0.5 2 −2 0.25 2 −3 0.125 2 −4 0.0625 2 −5 0.03125 8-channel MUX S2 S1 S0 Q 0 0 0 A0 0 0 1 A1 0 1 0 A2 0 1 1 A3 1 0 0 A4 1 0 1 A5 1 1 0 A6 1 1 1 A7 SR NOR Latch (Also, for gated SR-NAND latch when en = 1) Inputs Outputs S R Q Q’ 0 0 Q Q’ 0 1 0 1 1 0 1 0 1 1 Forbidden SR NAND Latch Inputs Outputs S’ R’ Q Q’ 0 0 Forbidden 0 1 1 0 1 0 0 1 1 1 Q Q’ . 3-to-8 Line Decoder with Enable En A2 A1 A0 D7 D6 D5 D4 D3 D2 D1 D0 0 X X X 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 8-channel Demultiplexer S2 S1 S0 Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0 0 0 0 0 0 0 0 0 0 0 A 0 0 1 0 0 0 0 0 0 A 0 0 1 0 0 0 0 0 0 A 0 0 0 1 1 0 0 0 0 A 0 0 0 1 0 0 0 0 0 A 0 0 0 0 1 0 1 0 0 A 0 0 0 0 0 1 1 0 0 A 0 0 0 0 0 0 1 1 1 A 0 0 0 0 0 0 0 8-to-3 priority Encoder (Priority A7 → A0) A7 A6 A5 A4 A3 A2 A1 A0 E2 E1 E0 1 X X X X X X X 1 1 1 0 1 X X X X X X 1 1 0 0 0 1 X X X X X 1 0 1 0 0 0 1 X X X X 1 0 0 0 0 0 0 1 X X X 0 1 1 0 0 0 0 0 1 X X 0 1 0 0 0 0 0 0 0 1 X 0 0 1 0 0 0 0 0 0 0 1 0 0 0 J-K Flip Flop Inputs Outputs J K Q(n+1) 0 0 Q(n) 0 1 0 1 0 1 1 1 Q (n)’

TOPIC: Combinational Logic Design Adders & Subtractors: 1. A 32-bit ripple-carry adder has a gate delay of 1.5 ns . What is the critical path delay for the adder? Solutions: Critical path delay = 2(N-1) + 3 gate delays = 2N + 1 gate delays = 2*32 + 1 = 65 gate delays Delay time = 65*1.5 ns = 97.5 ns 2. What are the SUM and Cout values of the circuit shown to the right when: (a) A = 0110, B = 1011, Cin = 0 (b) A = 1000, B = 0111, Cin = 1 (c) A = 0111, B = 0111, Cin = 0 (d) A = 0000, B = 1010, Cin = 1 Solutions: When Cin = 1, we implement A – B. Else, A+B. (a) S = 0001, Cout = 1 (b) S = 0001, Cout = 1 (c) S = 1110, Cout = 0 (d) S = 0110, Cout = 0 3. Suppose an adder circuit adds 12-bit numbers. How many bits will the sum contain? 13 bits (12 bits of S, 1 bit Cout) 4. Why is the maximum delay of an N-bit ripple-carry adder 2(? − 1) + 3 gate delays? That is, why is the delay caused by the non-LSB adders in the ripple-carry adder only 2 gate delays and not 3? Because the carry out only ripples through two gates on higher bits, and 3 gates in the LSB bit adder circuit.

9. A full-adder is constructed for which the XOR gate has a 5 ns delay, the AND and OR gates have a 2 ns delay each. What is the maximum delay for the full-adder? If two of these full-adders are connected to create a 2-bit full adder, what is the maximum delay for the 2-bit adder circuit? 10. Each gate in a 2-bit adder, whose circuit is shown to the right has a delay of 5 ns. Complete the timing diagram below. Values for A = A 1 A 0 and B = B 1 B 0 are shown in the timing diagram as bus signals. The signals might look weird compared to what you are used to, but just remember that A has two bits, and the points where these values change are shown by the cross- over. You can redraw these bus signals into their individual bits for your convenience, if you’d like. SOLUTION : The delay for the carry-out of the LSB bit is 3*5 = 15 ns. The sum delay for S0 is 10 ns. The carry-in comes into the MSB bit adder at t = 15 ns. and takes another 10 ns to come out to C OUT on the LSB adder, while the sum S1 comes out at 15 + 5 = 20 ns. This is only 5 ns rather than the expected 10 ns, because the first XOR gate output between A1 and B1 is already ready at t = 5 ns, and is only waiting on the carry-in from the LSB adder to complete processing to get S1. Thus, S1 is ready at t = 20 ns, while Cout is ready at t = 25 ns, since it has to go through the AND and OR gates. Once A and B change at t = 30 ns, we need to look at how the changes propagate. In the timing diagram below, the LSB carry-out is always 0 in both cases ( 0 + 1 = 1 + 0 = 0 , with carry = 0). Thus, S1 and Cout change only in response to A1 and B1, which means the second bit output takes only 10 ns after A1 and B1 change, rather than 25 ns if A0 and B0 resulted in a change in the LSB carry-out. The second carry-out takes 15 ns takes to be ready after A1 & B1 change, i.e. at t = 45 ns. In this case, this is quicker than the expected 25 ns response it would’ve required if Cin changed. This demonstrates the non-uniform response time for a full-adder. The timing waveform is shown below. Please note that it is possible the carry-in might have a temporary static-0 hazard, depending on how A0 and B0 switch. If for example, the A0-B0 switch is not simultaneous (i.e. 01 to 10), but goes through a transition state ( either 01 → 11 → 10 or 01 → 00 → 10 ), there might be a momentary glitch on the carry bit. This is shown in the plot below as the small glitch, BUT it isn’t necessary to show this in the answer – I’m only providing it for clarity and completeness . The glitch, if it does occur, will be seen on the S0 bit at t = 30 + 10 = 40 ns, and at the LSB carry-out bit at t = 30 + 15 = 45 ns. This then takes another 5 ns to be seen at S1 (i.e., at t = 50 ns), and 10 ns to be seen at Cout (i.e, at t = 55 ns).

13. A designer wants to create a circuit to reverse the bits in a 3-bit number, so that A2 becomes A0, A2 becomes A1, and A0 becomes A2. He uses a 3-to-8 line decoder connected to an 8-to-3 line encoder to create this circuit. The input-output table is shown to the right, as well as the circuit blocks. Connect the outputs of the decoder to the correct inputs of the encoder to ensure that the circuit works as designed. Solutions: Shown below: 14. Which circuit (from 1 to 4 in the right column) would be most appropriate for the problems listed below in (A) to (C)? (A) A stadium wants to open only one turnstile gate at a time, out of 7 gates, based on a 3-bit number provided as input. (B) The White House switchboard circuit (during the Cold War) connects calls to the Oval office based on how important they are, on a scale of 1 to 5. The Red Hotline to Moscow gets patched through immediately, calls from the Pentagon are next in importance while regular calls to the switchboard are considered least important. (C) A rotary dial at a factory can be turned to one of 16 different positions (from 0 to 15) around the circle. The factory wants to display the number based on the position the dial is set to. For each of these options, choose one of the following: (1) 16-to-4 priority encoder (2) 3-to-8 line decoder (3) 8-to-3 priority encoder (4) 16-to-4 line encoder SOLUTIONS: (A) 3-to-8 line decoder (B) 8-to-3 priority encoder (16-to-4 priority encoder is also possible, but will be overkill, since the priority scale is only 1 to 5) (C) 16-to-4 line encoder Input Output 000 000 001 100 010 010 011 110 100 001 101 101 110 011 111 111

15. TRUE / FALSE : A line decoder without an enable will always have one line providing an output ‘1’ 16. TRUE / FALSE : Each output of a line decoder represents a minterm. 17. TRUE / FALSE : An encoder with 128 input bits will have 6 output bits. 18. TRUE / FALSE : An 3-to- 8 line decoder with enable input ‘En’ and line inputs A2, A1, A0 is functionally identical to an 8- channel Multiplexer with input ‘En’ and select lines A2, A1, A0. SOLUTION: A 3-8 Line Decoder with an enable is identical to an 8-channel DEMUX, not MUX. 19. TRUE / FALSE: It is possible to have an ? -input decoder with fewer than 2 𝑛 outputs: 20. How many 2-to-4 line decoders are required to implement a 4-to- 16 line decoder? Assume that each decoder also has an enable input SOLUTION: This requires multiple layers of decoders. The first layer has a single 2-to-4 line decoder with A3 A2 as inputs, while the second layer has four 2-to-4 line decoders with A1 A0 as inputs, and the corresponding outputs of the first layer as the enable. Thus, FIVE (5) 2-to-4 line decoders are required. The block diagram is shown to the right. 21. Which of the following have more output bits than input bits? (Select all that apply) (a) Line Decoder (b) Line Encoder (c) Priority encoder (d) Multiplexer (e) Demultiplexer (f) 8-bit Adder 22. A Line Decoder converts n inputs to ________ outputs: (a) ? 2 (b) 2? (c) 2 𝑛 (d) 2 2 𝑛 23. How many inputs will a Decimal-to-BCD encoder have? (a) 4 (b) 6 (c) 10 (d) 12

27. How many select lines are required for a 200-channel Multiplexer? SOLUTION: ⌈log 2 200⌉ = 8 28. A circuit which gates one input of data line to one of 2^n output lines is defined as a: (a) MUX (b) DEMUX (c) Encoder (d) Decoder 29. Which of the following is the correct output expression for an 8-to-1 MUX? (a) 𝑌 = ?(? 0 + ? 1 + ? 2 +. . . + ? 7 ) (b) 𝑌 = (? 0 ? 0 + ? 1 ? 1 + ? 2 ? 2 + ⋯ + ? 7 ? 7 ) (c) 𝑌 = ? 0 ′ + ? 1 ′ + ? 2 ′ + ⋯ + ? 7 ′ (d) 𝑌 = (? 0 ? 0 ′ + ? 1 ? 1 ′ + ? 2 ? 2 ′ + ⋯ + ? 7 ? 7 ′ ) (e) 𝑌 = ? 0 ? 0 + ? 1 ? 1 + ? 2 ? 2 + ⋯ + ? 7 ? 7 30. An 8-to-1 MUX is connected as shown below. What Boolean function does this MUX implement? SOLUTION: 𝐹 = ∑ ?(0,3,4,7) ?,?,? = ? ′ ? ′ + ?? = (? ⊕ ?) ′ 31. Which of the following best describes how to construct a 1-to-8 Demux with select inputs A, B, C, and data input, D from a 3-to-8 line decoder: (a) Connect A, B, C to the decoder input lines. (b) Connect D to the decoder enable and A, B, C to the decoder line-inputs (c) Connect A, B, C to the decoder line inputs. Set the decoder enable = 1 (d) Since a decoder has 3 inputs, but a DEMUX has only 1 input, it is impossible to create a 1-to-8 DEMUX from a 3-to-8 line decoder 32. Create an 8-to-1 MUX using 2-to-1 MUXes. You can use as many 2-to- 1 MUXes as you’d like.

Shifters 33. Find the results of the following shifts: (A) 1100_0101 – logical left shift by 3 bits Solution: 0010_1000 (B) 1100_0101 – logical right shift by 2 bits Solution: 0011_0001 (C) 1100_0101 – arithmetic left shift by 2 bits Solution: 0001_0100 (D) 1100_0101 – arithmetic right shift by 4 bits Solution: 1111_1100 (E) 0101_1100 – arithmetic right shift by 2 bits Solution: 0001_0111 (F) 0110_0101 – barrel left shift by 4 bits Solution: 0101_0000 34. Which of these numbers are at risk of overflow or underflow when left shifted by 1, 2 or 3 bits? The number form is indicated in the second column. Circle the appropriate choices of risk type and number of bits to cause overflow or underflow in each column. SOLUTIONS: HIGHLIGHTED IN TABLE Number Number Type Risk Type Number of bit shifts to cause over/underflow Overflow Underflow No risk 1 2 3 0010 Unsigned Overflow Underflow No risk 1 2 3 1111_0101 Signed Overflow Underflow No risk 1 2 3 101 Signed Overflow Underflow No risk 1 2 3 0110 Signed Overflow Underflow No risk 1 2 3 0000_1101 Signed Overflow Underflow No risk 1 2 3 0010_1101 Unsigned Overflow Underflow No risk 1 2 3 NOTE : Once there is a single instance of over or underflow, then all further bit shifts will have overflow/underflow, even if they have the same sign bit. For example, if we left shift 1010, then the first shift causes underflow, but a 2 bit barrel shift would not appear as underflow, since the sign bit stays at 1. However, because the first bit shift has already caused underflow, we should consider the 2 nd and subsequent bit shifts too as underflow. 35. TRUE / FALSE : Overflow and underflow occur during left shift 36. Using an arithmetic shifter, how many clock cycles are required to perform a multiplication by 8? SOLUTION: 3 clock cycles 37. Using a barrel shifter, how many clock cycles are required to perform a division by 8? SOLUTION: 1 clock cycle (Barrel Shifter)

TOPIC: Sequential Logic Design – Latches & Flip-Flops 40. What is the difference between a latch and a flip-flop? See class notes & lectures 41. TRUE / FALSE : A latch is an edge triggered circuit 42. TRUE / FALSE : A D-Flip flop has a forbidden state. 43. TRUE / FALSE : We can force the state of a T-flip flop to be either 0 or 1 using only the T bit and the clock. 44. TRUE / FALSE : Propagation delay is required for sequential circuits to function correctly 45. TRUE / FALSE : Latches require synchronization using a clock signal 46. TRUE / FALSE : Sequential circuits require a feedback path 47. How does an SR- NOR latch differ from the S’ - R’ NAND latch? Provide at least 2 points of difference. 48. Which of the following are essential components of synchronous circuits? (A) Flip-flops (B) Enable signals (C) Clock signals (D) All of the above 49. Which of the following will convert a D-flip flop to a T-flip flop? (A) Connect the output Q to the input, D (B) Connect the output Q to the clock input (C) Connect the clock and the D input together (D) Connect the output Q’ to the input D 50. Draw the transition table for the circuit shown, and determine which states (if any) are forbidden? Are there any reset states achieved within this circuit? i.e., is there any combination of inputs that can force Q to be = 0 in a non-forbidden state?

51. Specify the type of circuit shown by the symbols below. Please provide specific details that indicate whether the circuit is level or edge-triggered, and if so, which edge the circuit is triggered by: Symbol Answer (A) Level-triggered D-latch (B) Positive-edge-triggered J-K Flip Flop (C) Negative-edge triggered D flip-flop (D) Positive edge triggered master-slave D flip-flop (E) S’ - R’ NAND Latch (level triggered circuit) 52. Using a timing diagram, analyze the output of the following circuit when a clock signal is provided as the input This was done in homework & class. This will be a falling-edge triggered circuit. 53. For the previous circuit, draw the timing diagram if the inverters had no delay. Will be 0 always, because (A + A’)’ = 1’ = 0.

58. In a J-K flip flop connected as shown, ? = 𝑄’ and ? = 1 . If the flip- flop was initially cleared, what is the sequence of outputs, Q for the first six clock pulses after the flip-flop has been cleared? (A) 010000 (B) 011001 (C) 010010 (D) 010101 Initially, if flip- flop is cleared, Q = 0, Q’ = 1. Thus, with J = Q’ = 1, and K= 1, the J -K flip-flop operates in toggle mode for the first clock cycle, resulting in Q(1) = 1, Q’(1) = 0 . This causes the next input state to become JK = 01, causing the flip- flop to reset. Thus, Q(2) = 0, Q’(2) = 1. We can follow this chain to create the entire sequence of states and outputs: Step J K Q(n) Q’(n) State Q(n+1) Q’(n+1) Init 1 1 0 1 Toggle 1 0 1 0 1 1 0 Reset 0 1 2 1 1 0 1 Toggle 1 0 3 0 1 1 0 Reset 0 1 4 1 1 0 1 Toggle 1 0 5 0 1 1 0 Reset 0 1 6 1 1 0 1 Toggle 1 0 59. A characteristic of Master-slave flip-flops is that: (A) A change in the input is immediately reflected in the output (B) Change in the output occurs when the state of the slave latch is affected (C) Change in the output occurs when the state of the master is affected (D) Both the master and slave latches are affected at the same time 60. When will a race condition occur in the circuit to the right? (A) Does not occur (B) Occurs when clk = 0 (C) Occurs when clk = 1, A = 1, B = 1 (D) Occurs when clk = 1, A = 0, B = 0 61. Three D-flip flops are connected in a series as shown below. Complete the timing diagram below.

62. An S-R Latch is a: (A) Combinational Circuit (B) One clock delay element (C) Synchronous sequential circuit (D) One-bit memory element. 63. Analyze the circuit and show whether it can perform essential latching functions, i.e., if the circuit can ‘hold’ the state, and whether it can be ‘set’ and ‘reset (to 1 and 0 respectively). Solution: Check for all conditions on A and B, for both Q = 1 & Q = 0 to create an output table. Then see if the ‘set’, ‘reset’, and ‘hold’ behaviour are possible to achieve. See what the state change behaviour is when you start analyzing from Q’ and what it is when you start analyzing it from Q. If they both result in the same output state, then this is a stable state. Else, it results in a race condition that makes the input combination forbidden. The first four rows of the table are shown below. You are encouraged to fill out the rest: A B Q(n) Q’(n) Q(n+1) Q’(n+1) Behaviour 0 0 0 1 0 0 Forbidden 1 0 1 1 Forbidden 0 1 0 1 1/0 1/0 Constant race-conditioned switching – Forbidden 1 0 0/1 1/0 Constant race-conditioned switching – Forbidden 1 0 0 1 1 0 1 1 0 1 1 0