Name: 1CSE 240 Autumn 2004DUE: Fri. 1 October 2004Intro. 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: 34.1. [6 Points] Muxes and Memory.(a) A 2-bit 2-to-1 mux (below, right) is similar to a 1-bit 2-to-1 mux (below, left) except the former selectsamong 2-bit inputs rather than 1-bit inputs. More specifically, the output of 2 bit 2-to-1 mux is defined asfollows: if S = 0, Yi= Aiand if S = 1, Yi= Bi, for i = 0, 1. Construct a circuit with the behavior of a 2-bit2-to-1 mux using two 1-bit 2-to-1 muxes.1 bit 2−to−1 Mux2 bit 2−to−1 MuxSSA BYY[1]Y[0]B[1]A[0]A[1] B[0]2(b) 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 23-by-2-bit memory(below, right) using a 2 bit 2-to-1 mux and a 22-by-4-bit memory (below, left). Assume that the memoriesare read-only memories (ROMs), so you need only be concerned with reading.memory2^2−by−4 bitD[3] D[2] D[1]D[0]memory2^3−by−2bitD[0]D[1]Adr[1]Adr[0]Adr[2]Adr[1]Adr[0]Name: 32. [8 Points] Combinational Logic Circuits. Do you remember the game of tic-tac-toe? (See p. 73–74 in yourtextbook if you do not.) We can use bit vectors to represent the state of any tic-tac-toe game. Consider thefollowing game state (we use “*” instead of “O” to avoid confusion with zero).X * X*We can represent this state using two 9-bit vectors AX = (101 000 000) and A* = (010 010 000). The vectorAX indicates whether each cell contains an X (denoted with a 1) or a non-X (denoted with a 0). The first threebits represent the top three cells from left to right; the next three bits represent the middle three cells; and thelast three bits in the vector represent the bottom three cells. Vector A* is analogously defined.(a) Give the bit-vector representation (both AX and A* ) for the following game state.X * X* *X XAX :A* :4(b) Give the bit-vector representations (both AX and A* ) of all possible next states for the above game,assuming it is ∗ ’s turn next.(c) Construct a gate-level logic circuit to determine if the ∗ player has won (i.e., has three in a row). The inputto this circuit is the 9-bit A* vector (A* [0-8]). The output (W∗ ) should be 1 if only if the ∗ player haswon. You may assume the game state was arrived at through a succession of legal moves (i.e., both playerswill not have 3 in a row).Name: 53. [8 Points] Sequential Logic Circuits. Consider the following circuit.DataACDB4888444EClockAddressComponents are labeled according to the following key: (A) A 4-bit register representing an unsigned binarynumber (initially set to 0). (B) A 4-bit incrementer. (C) An 8-bit register (initially set to 0). (D) An 8-bit adder.(E) A 24-by-8-bit memory. Assume the memory has the following contents.Address Contents Address Contents0 2 8 51 1 9 22 1 10 13 4 11 14 2 12 35 3 13 46 2 14 17 2 15 1(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 012345678(b) In a sentence, what does this circuit do?64. [12 Points] Finite State Machines. It’s your first day at the Pretty Good Lock Co. Your boss knows you’re awhiz so she asks you to build a combination lock circuit. This lock takes a combination (i.e., a sequence of 0sand 1s on the 1-bit input X) and generates a 1-bit output Z, indicating whether the lock is closed (0) or open (1).The lock must accept two combinations: 1, 1, 0, 1 and 1, 0, 0, 0.(a) Where do you begin? First, you examine the state diagram (below) created by your predecessor (he gotfired; don’t ask why). Assume S0 is the initial state. Edges are labeled with the input that causes a statetransition. Nodes are labeled with the output (e.g., “Z=1”) of that state.Z=0S0Z=0S1Z=0S2Z=0S3Z=1S4Z=0S5Z=0S6Z=1S7000000,100111110,111Experiment with the finite state machine defined by this state diagram to determine if it actually accepts1, 1, 0, 1 and not, for example, 1, 1, 0, 1, 0 by completing the following table. (S-next represents the statereached when a transition is made from state S on input X. Z is the output in state S-next.)S X S-next Z0 11010Name: 7(b) So far so good. You start to build a circuit for the state diagram, but you suddenly realize that once youbuild the circuit, you will be unable to change the combination without building a new circuit. Maybethat’s why your predecessor got fired! You resolve to do better and build the following programmablecombination lock circuit.DataSMOutput33333333ZA0A1XClock01AddressAddressAddressDataDataComponents are labeled according to the following key: (A0) A 23-by-3-bit memory. (A1) A 23-by-3-bitmemory. (Z) A 23-by-1-bit memory. (S) A 3-bit register (initially containing 0). (M) A 3-bit 2-to-1 mux.Suppose the contents of memories A0, A1 and Z are initialized as follows.Address A0 A1 Z0 1 0 01 0 2 02 3 0 03 0 4 04 5 0 05 0 6 06 0 0 17 0 0 0Voila! You’ve built a programmable combination lock, and it’s currently programmed to accept the com-bination 0, 1, 0, 1, 0, 1. Try it out on 0, 1, 0, 1, 0, 1, 1 by completing the following table.Clock Cycle S X S-next Z0 0 0 1 01 1 12 03 14 05 16 18(c) Okay, cool. Program this circuit (i.e., provide the contents of the memories) to accept the two combinationsfrom part (a). Complete the following table.Address A0 A1 Z01234567(d) In fact, the above circuit can be used to implement any finite state machine with 1 input, 1 output, and up to8 states. (i) How would you modify your circuit to support more than 8 states? (ii) How would you modifyyour circuit to support 2-bit inputs? Don’t actually build the circuit; instead, describe what changes youwould make to the existing circuit.Name: 95. [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