Name: 1CSE 240 Autumn 2005DUE: Fri. 30 September 2005Intro. to Computer Architecture Homework 3Write your answers on these pages. Additional pages may be attached (with staple) if necessary. Please ensure thatyour answers are legible. Please show your work. Due at the beginning of class. Total points: 37.1. [8 Points] Muxes and Memory.(a) A 1-bit 4-to-1 mux (below, left) selects among four inputs using two selector lines. Specifically, the muxoutputs A when the selectors have the value 00 (with S1being the high-order bit), B when they have thevalue 01, C when they have the value 10, and D when they have the value 11. Construct a 1-bit 4-to-1 mux(i.e., build a circuit with the behavior of a 1-bit 4-to-1 mux) using three 1-bit 2-to-1 muxes (below, right).Be sure to label the inputs (A, B, C, D, S0, and S1) and output (Y ).00 01 10 110 1A B C DY YA BS0S1S(b) How many 1-bit 2-to-1 muxes are required to build a 1-bit 2k-to-1 mux (for k > 0)?2(c) Memories come in many shapes and sizes. If we need a memory of a particular size and addressability,we can often construct it out of other, differently-structured memories. Construct a 24-by-1-bit memory(below, left) using a mux and a 22-by-4-bit memory (below, right), as well as any gates you might need.Assume that the memories are read-only memories (ROMs), so you need only be concerned with reading.Be sure to label the inputs (A[0] - A[3]) and output (D).A[3]A[2]A[1]A[0]A[1]A[0]D[3] D[2] D[1] D[0]DName: 32. [8 Points] Finite State Machines. The circuit below implements a finite state machine M. The one bit registerlabeled S stores the current state, I is the input, and O is the output.SOIClock(a) How many states does M have? Draw a state diagram for M (similar to that in the diagram on page 75 ofthe textbook).4(b) The circuit below is a programmable finite state machine. The components of this circuit are labeledaccording to the following key: (A) A 22-by-1-bit memory. (Z) A 21-by-1-bit memory. (S) A 1-bitregister.SClockIA[1]A[0]DataAddr DataAZOWhat should the contents of the memories be so that this circuit implements M (from the previous prob-lem)?Address Contents of A0 00 11 01 1Address Contents of Z01Name: 53. [8 Points] Sequential Logic Circuits. Consider the following circuit.AClockCDBGFE01AddrData1884488The components of this circuit are labeled according to the following key: (A) A 4-bit register representing anunsigned integer (initially set to 0). (B) A 4-bit incrementer. (C) An 8-bit register storing a 2’s complementinteger (initially set to 127). (D) An 8-bit 2-to-1 mux. (E) A circuit whose output is true when the 8-bit 2’scomplement input is positive. (F) An 8-bit adder. (G) A 24-by-8-bit memory. Assume the memory has thefollowing contents.Address Contents Address Contents0 31 8 271 47 9 952 5 10 883 16 11 674 112 12 635 3 13 546 59 14 807 8 15 110(a) Determine the values stored in the A and C registers at the end of each clock cycle for 8 cycles. Completethe following table with this information.Clock Cycle A C0 0 127123456786(b) In a simple sentence, what does this circuit do?4. [4 Points] Reasoning About Numbers.(a) Draw a gate-level circuit that has a 1 output, O, only when the 5-bit 2’s complement input, S[0] − S[4],represents 0.(b) Using your circuit from (a), draw a gate-level circuit that has a 1 output, O, only when the 5-bit 2’scomplement input, S[0] − S[4], represents a positive integer. You don’t need to redraw the circuit from (a);just draw it as a box labeled Z.Name: 75. [9 Points] More Sequential Circuits.Consider the incomplete circuit, below. The components of this circuit are labeled as follows: (A) A 5-bit adder.(B) A 5-bit 2-to-1 mux. (C) A 4-bit 2-to-1 mux. (D) A 4-bit 2-to-1 mux. (E) A 4-bit incrementer. (F) A 5-bitregister. (G) A 4-bit register. F stores a positive 2’s complement integer less than or equal to 10, and G stores a2’s complement integer between 1 and 4, inclusive. The input I is a 5-bit 2’s complement integer between 0 and10, inclusive.This incomplete circuit is intended to implement the following logic. In each cycle, except in the circumstancesdescribed below, (i) F is updated to contain F − I, (ii) G is updated to contain G + 1, and (iii) the output O is 0.If I is greater than or equal to F or G is equal to 5 (after the increment), 10 is written into F (instead of F − I)and 1 is written into G (instead of G + 1). If G is equal to 5 (after the increment), the output O is also set to 1(instead of 0).Unfortunately, the circuit is incomplete because the mux selector lines are missing as is the logic for computingthe output O. It is your job to fill in the missing pieces of this circuit to achieve the intended functionality. (Notethat while this circuit seems completely arbitrary, it is actually implementing a simplified version of the rules ofAmerican football. If it still seems completely arbitrary, well that’s because the rules of American football arecompletely arbitrary!)D010101BAECGFClock11110I555444455O544(a) Let’s do this one step at a time. Using your positive-testing circuit from the previous problem (draw it as abox labeled P), augment the given circuit (above) with the logic for the D mux selector. Hint: The D muxdetermines whether to reset the value in G to 1 due to the input I being greater than or equal to the valuestored in F.8(b) Using a 4-bit adder and the zero-testing circuit from the previous problem (draw it as a box labeled Z),augment the given circuit (below) with the logic for the C mux selector and the output O. Feel free toinclude the logic from the previous problem (but you don’t have to). Make sure the output is connected tothe line labeled O. Hint: The C mux determines whether to reset the value in G to 1 due to it being equalto 5 after incrementing.D010101BAECGFClock11110I555444455O544Name: 9(c) Augment the given circuit (below) with the logic for the B mux selector. You may find it helpful to redrawsome or all of the logic from the previous steps.D010101BAECGFClock11110I555444455O544106. [No Points] Last and Most Important Question! Please complete this question, and give us your feedback!(a) How many hours did you spend on this assignment?(b) On a scale of 1-5, how difficult did you find this assignment? (1-easiest, 5- most difficult)(c) Do you have any other comments on your experience completing this assignment? What are