Cse 140 Homework 10-2

Course Policies

Collaboration

Students are encouraged to talk to each other, to the course staff, or to anyone else about any of the assignments. Assistance must be limited to discussion of the problem and sketching general approaches to a solution. Each student must write out his or her own solutions to the homework.

Each student is responsible for knowing and abiding by UCSD's policies on Integrity of Scholarship and the Jacobs School Student Honor Code. Any student violating UCSD's Academic Dishonesty or UCSD's Student Conduct policies will earn an 'F' in the course and will be reported to their college Dean for administrative processing. Committing acts that violate Student Conduct policies that result in course disruption are cause for suspension or dismissal from UCSD.

Late Policy

  • The deadline for any assignment can be extended by one day with a 10% penalty.

Last updated: Mon Feb 03 13:06:40 -0800 2014 [validate xhtml]

Unformatted text preview: Homework #1 Solution and Rubric CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. Solve the following problems: I. Convert the following decimal numbers to binary numbers A. 32 B. 23 II. Convert the following binary numbers to decimal numbers A. 1011 B. 10101 III. Convert the following hexadecimal numbers to binary numbers A. F002 B. BEEF IV. Convert the following hexadecimal numbers to decimal numbers A. FF B. 100 Solution: 1. a. 100000 b. 10111 2. a. 11 b. 21 3. a. 1111 0000 0000 0010 b. 1011 1110 1110 1111 4. a. 255 b. 256 2. The following CMOS circuits implements a boolean function. Vdd represent the supply voltage and GND represent the ground voltage. a. Complete the table below. Specify whether transistors are ON or OFF and the circuit output. b. Describe the circuit (either by words or with a boolean expression) a b N1 P1 N2 N3 P2 P3 f 0 0 0 1 1 0 1 1 Solution: a) Truth table: a N1 P1 N2 N3 P2 P3 f 0 0 OFF ON ON OFF OFF ON 0 0 1 OFF ON ON ON OFF OFF 0 1 0 ON OFF OFF OFF ON ON 1 1 b 1 ON OFF OFF ON ON OFF 0 b) Examples of correct answers: ­ Inverter driving a nor gate ­ CMOS version of the following function: f=(a’ + b)’ 3. Implement the Boolean equation F = (a AND b’) OR c OR d’ using only NOR gates and inverters. Your NOR gates can have more than 2 inputs. Solution: Use 3­input gate: Only use 2­input gates: 4. Concisely describe the following problem using a Boolean equation. We want to fire a football coach (by setting F = 1) under at least one of two conditions: a. if he is mean (represented by M = 1) b. if he is not mean but has a losing season (represented by L = 1). Solution: F = Coach is fired M = Coach is mean L = Coach has a losing season F = M + M’L For a coach to be fired, either the coach is mean ‘or’ he is not mean and has a losing season. If someone simplifies, the expression reduces to F = (M + M’) (M + L) = M + L Homework #2 Solutions CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. Solve the following: a. Draw a circuit using AND, OR and NOT gates for the following equation: F(a,b,c) = (ab) (b’ + c) b. Convert the circuit using only NAND gates (INV are ok) c. Convert the circuit using only NOR gates (INV are ok) Solution: PLEASE NOTE:​ solutions including NOT gates (instead of NORs or NANDs connected with both inputs to the same wire) are fine as well. a. Draw a circuit using AND, OR and NOT gates for the following equation: F(a,b,c,d) = (ab) (b’ + c) b. Convert the circuit using only NAND gates and INV c. Convert the circuit using only NOR gates and INV 2. a. Use DeMorgan’s Law to find the ​ inverse​ of the following equation: F = abc + a’b. Reduce to minimal number of product­terms (SOP form). Hint: Start with F’ = (abc + a’b)’. b. Use DeMorgan’s Law to find the inverse​ ​ of the following equation: F = a’c+a’b’d+cd’. Reduce to minimal number of sum­terms (​ product­of­sums form). ​ Solution: a. F = abc + a’b => F’ = (abc + a’b)’ = (abc)’(a’b)’ =(a’+b’+c’)(a+b’) = a’b’ + ab’ + b’ + ac’ + b’c’ = b’ + ac’ b. F = a’c+a’b’d+cd’ => F’ = (a’c+a’b’d+cd’)’ = (a’c)’(a’b’d)’(cd’)’ = (a+c’)(a+b+d’)(c’+d) 3. Given the following function:​ F = (A’. B’. C’)’. C + (A’. B’. C’)’ + D Using Boolean Algebra, prove that the logic equation above can be implemented by a 4­input OR gate: ​ F = A + B + C + D Show ALL the steps of your proof AND state the name of the axiom or theorem used in each step. Apply only one axiom/theorem at each step. Solution: F = (A’B’C’)’C + (A’B’C’)’ + D = (A’’ + B’’ + C’’)C + (A’’ + B’’ + C’’) + D ​ = (A + B + C)C + (A + B + C) + D = AC + BC + CC + A + B + C+ D = AC + BC + C + A + B + C + D ​ = AC + BC + C + C + A + B + D ​ = AC + BC + C + A + B + D ​ = C (A + B + 1) + A + B + D ​ = C.1 + A + B + D = C + A + B + D = A + B + C + D DeMorgan’s Involution Distributivity Idempotency Commutavity Idempotency Distributivity Null Element Identity Commutavity OR F = (A’B’C’)’C + (A’B’C’)’ + D = (A’’ + B’’ + C’’)C + (A’’ + B’’ + C’’) + D = (A + B + C)C + (A + B + C) + D = (A + B + C) (C + 1) + D ​ = (A + B + C).1 + D ​ = (A.1 + B.1 + C.1 ) + D ​ = (A + B + C) + D ​ = A + B + C + D DeMorgan’s Involution Distributivity Null Element Distributivity Identity Associativity 4. A museum has three rooms each with a motion sensor (m0, m1, and m2) that outputs 1 when motion is detected. At night, the only person in the museum is one security guard who walks from room to room. Create a function that sounds an alarm (by setting an output A to 1) if motion is detected in more than one room at a time( i.e in two or three rooms), meaning that there must be one or more intruders in the museum. a. Specify the truth table b. formulate canonical sum of products implementation for A c. Minimize A using K­maps and write the minimum implementation of A d. Draw the circuit Solution: m0 m1 m2 A 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 In canonical SOP form, A = ∑m(3,5,6,7) m2 \ m0,m1 00 01 11 10 0 0 0 1 0 1 0 1 1 1 Minimal form: A = m1m2 + m0m1 + m0m2 Homework #3 CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. a. Perform two­level logic optimization for F(a,b,c) = a + a’b’c + a’c using a Kmap b. Perform two­level logic optimization for F (a,b,c,d) = a’bc’d +ab’cd’, assuming that a and b can never be both 1 at the same time, and that c and d can never be both 1 at the same time (those conditions are “don’t care”) Solution: a. The solution is F = a + c a \ bc 00 01 11 10 0 1 1 0 1 1 1 1 1 b. The solution is F = ac + bd ab \ cd 00 01 11 10 00 0 0 X 0 01 0 1 X 0 11 X X X X 10 0 0 X 1 Grading: a. 5 points maximum (­1 point for mistakes on Kmaps and optimization) b. 5 points maximum (­1 point for mistakes on Kmaps and optimization) 2. There are two functions, F = ab’ + c and G = (a’ +ab)’ + ab’c’ + c. Represent each function with a K­map, and minimize each using SOP. Are F & G equivalent to each other? Solution: a. K­Map for F a \ bc 00 01 11 10 0 0 1 1 0 1 1 1 1 0 00 01 11 10 0 0 1 1 0 1 1 1 1 0 F = ab’ + c K­Map for G a \ bc G = ab’ + c F and G are equivalent to each other Grading: Max +10 a. +2 for correct K­map for F and grouping +1 for correct SOP equation for F +4 for correct K­map for G and grouping +1 for correct SOP equation for G +2 for stating that F and G are equivalent. 3. Use Karnaugh map to simplify the following functions and write ALL possible solutions. (1) f(a, b, c, d) = ᵫm(0, 1, 8, 14, 15) + ᵫd(2, 5, 10) Write the answer in SOP (sum­of­products) form. (2) f(a, b, c, d) = ∏M(1, 6, 9, 11, 14, 15) + ᵫd(3, 4, 5, 12) Write the answer in POS (product­of­sums) form. Solution: (1) Two possible solutions: b’d’ + abc + a’b’c’ b’d’ + abc + a’c’d (2) Two possible solutions: (b’+d)(b+d’)(a’+b’+c’) (b’+d)(b+d’)(a’+c’+d’) Grading: Each truth table for 1 point, each possible answer for 2 points, total 10 points. 4. Given f(a, b, c, d) = ∑m(1, 2, 5, 7, 8, 12, 14) + ∑d(3, 6), implement the function using a minimal network of 2:1 multiplexers, minimum number of inverters and NO gates. Solution: Grading: +2.5 for each correct multiplexer. Deduct ­2 for additional multiplexers used. There can be multiple solutions depending on the order in which inputs are applied to select lines. Homework #4 CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. Design an ALU with two 8­bit inputs A and B, and control inputs x, y and z. The ALU should support the operations described in the table below. You may use an 8­bit adder and a minimum number of other elements. Inputs x y z Operation 0 0 0 S = A ­ B 0 0 1 S = A + B 0 1 0 S = A * 8 0 1 1 S = A/8 1 0 0 S = A NAND B (bitwise NAND) 1 0 1 S = A XOR B (bitwise XOR) 1 1 0 S = Reverse A (bit reversal) 1 1 1 S = NOT A (bitwise complement) Solution: SHIFT LOGIC: REVERSE LOGIC: Rewiring A7 to C0, A6 to C1….A0 to C7 Grading: Total 10 points + 1 for NAND, XOR and NOT each 3*1 = 3 + 2 for addition/subtraction 2 +3 for multiplication/division 3 +2 for reverse 2 No partial credits if implementation of mult/div or reverse is not shown ­1 if notation not used for 8 bits ­1 if incorrect inputs/control to the mux 2. a) Analyze the behavior of a level­sensitive SR latch for the given input patterns. Assume S1, R1, and Q are initially 0. Complete the timing diagram. Solution: Grading: 5 points each for correct S1 and R1. 10 points for correct Q. For each part, deduct 2 points for anything wrong, until 0 points. 2. b) Compare the behavior of the D latch and D flip­flop by completing the timing diagram below. D is input, C is the clock. Assume that each device initially stores a 0. Provide a brief explanation of the behavior of each device. Solution: Grading: +5 for D latch, +5 for D flip flop. 3. Design a sequential pattern recognizer with a single input x and a single output y that outputs a logic 1 when a pattern “01011” is observed, and otherwise outputs a zero. Solution: Grading: 10 points, deduct 2 points for each mistake. 4. Design a 4­bit carry­ripple­style magnitude comparator that has two outputs, a greater­than or equal­to output GTE, and a less­than or equal­to output LTE. In your solution report: a. The equations for GTE and LTE for the​ individual 1­bit comparator​ . Assume you have two inputs a and b. Write the two equations GTE=f(a,b) and LTE=g(a,b). b. The circuit implementation (with logic gates) of the 1­bit comparator, with both outputs GTE[i] and LTE[i] at step i. Also, ​ highlight the carry­ripple inputs GTE[i­1] and LTE[i­1] (that are used to build a chain of 1­bit comparators). c. The final design of the 4­bit carry­ripple­style magnitude comparator, which uses the circuit in (b) as a building block. In the final design, highlight the final outputs GTE and LTE. Solution: a. GTE = a + b’, LTE = a’ + b truth table: a b GTE LTE 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 Now for part b and c there may be different solutions. Below there are two possible that I have found, but different ones may be have to be tested before grading. SOLUTION #1 (MSB to LSB) b. The following circuit: c. The following design: SOLUTION #2 (LSB to MSB) b. the following equations and circuit L = LTE[i­1] G = GTE[i­1] a \ b G 00 01 11 10 0 0 1 0 0 1 1 1 1 0 a \ b L 00 01 11 10 0 0 1 1 1 1 0 0 1 0 GTE[i] = b G + a b’ + a G LTE[i] = b L + a’ b + a’ L c. the following design Grading: a. 2 points (+1 for each correct equation, GTE and LTE) b. 4 points (­1 for each gate mistake. ­2 for missing carry­ripple inputs) Note that points are given based on whether the circuit is a correct implementation of the function provided (or function extended with carry ripple inputs). c. 4 points : 1 point for each of the following test cases: i. a = 1010, b = 1010, LTE=1, GTE=1 ii. a = 0100, b = 1010, LTE=1, GTE=0 iii. a = 1010, b = 0100, LTE=0, GTE=1 iv. a = 1001, b = 0001, LTE=0, GTE=1 Do not take points away if some input names in the blocks are not 100% correct. What is important is that the structure of the design is clear. Homework #5 CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. Problem 1 A wristwatch display can show one of four items: time, alarm, stopwatch or date, controlled by two signals s1 and s0 ( 00 for time, 01 for alarm, 10 fo stopwatch and 11 for date. Assume s1 and s0 control an N­bit MUX that passes through the appropriate register. Pressing a button B (which sets B = 1) sequences the display to the next item. For example, if the presently displayed item is the date, the next item is the current time. a. Create a state diagram for an FSM describing this sequencing behavior, having an input bit B, and two outputs bits s1 and s0. Use short but descriptive names for each state. Displaying time should be the initial state. b. Is your design a Mealy or a Moore machine? Provide an explanation. c. Using the process for designing a controller, convert the FSM to a controller, implement the controller using a state register and logic gates. Provide all the steps to get credit. Solution: a. The following FSM: b. It is a Moore machine, because the output only depends on the current state c. The following circuit (together with tables) Q​ 0​ Q​ 1​ \ B 1 0 00 01 00 01 10 01 10 11 10 11 00 11 Q​ 0​ Q​ 1​ B D​ 1 D​ 0 000 0 0 001 0 1 010 0 1 011 1 0 100 1 0 101 1 1 110 1 1 111 0 0 Kmap for D​ 1 B \ Q​ 0 Q​ 1​ 00 01 11 10 0 0 0 1 0 1 1 1 0 1 D​ = B*Q​ ’ + B*Q​ ’ + B’*Q​ 0 *Q​ 1​ 1​ 0​ 1​ Kmap for D​ 0 B \ Q​ 0 Q​ 1​ 00 01 11 10 0 0 1 0 1 1 0 1 0 1 D​ 1​ 0​ 1​ 0​ = Q​ + Q​ ’ ’*Q​ *Q​ 0​ Circuit: 2. Problem 2 Design a 3­bit counter, which can count either up or down. The input has a clock, and a signal U. When U = 1, the counter will count up; when U = 0, the counter will count down. For example, assume the current counter Q(t) = 011. If U(t) = 0, then Q(t+1) = 010; if U(t) = 1, then Q(t+1) = 100. a. Write the excitation table for this finite state machine. b. Use K­Map to find the minimal cover. (The output of these gates are the inputs for D flip­flops.) c. Draw the circuit of your design, including combinational circuits and D flip­flops. Solution: a. b. c. 3. Problem 3 Design a Mealy, non­resetting finite state machine that has one binary input X and one binary output Z. The output Z = 1 occurs whenever the last five bits on input X have been 11101; otherwise, the output Z = 0. This machine recognizes overlapping sequences also. For example, if the input sequence is X = 11101110111110111010, then the output sequence is Z = 00001000100000100010. Draw a state diagram that implements this machine using minimum number of states (~5). Design the circuit that implements the FSM with D­FFs and minimum number of other gates. Solution: We use binary encoding for the above states. For 5 states, we need at least 3 bits. “0” ­> 000 “1” ­> 001 “11” ­> 010 “111” ­> 011 “1110” ­> 100 State transition and activation table Q​ 2 Q​ 1 Q​ 0 X D​ 2 D​ 1 D​ 0 Z 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 K maps for finding minimal expressions D​ 2 D​ 1​ 0​ = Q​ X’ Q​ 2​ D​ 1 D​ 1​ = Q​ X + Q​ X 1​ 0​ D​ 0 D​ 0​ = Q​ ’X + Q​ X 0​ 1​ Z Z = XQ​ 2 We obtain the activation logic from the K maps : D​ 1​ 0​ = Q​ X’ Q​ 2​ D​ 1​ = Q​ X + Q​ X 1​ 0​ D​ 0​ = Q​ ’X + Q​ X 0​ 1​ Z = XQ​ 2 Using these next­state equations, we can design the circuit from D flip flops. 4. Problem 4 You are designing an adder, built from three full adders such that the carry out of the first adder is the carry into the second adder, and the carry out of the second adder is the carry into the third adder, as shown in the figure. Your adder has input and output registers and must complete the addition in one clock cycle. Each full adder has the following propagation delays: 20 ps from C​ to C​ or to Sum(S), 25 ps from A or B to C​, and 30 ps from A or B to in​ out​ out​ S. The adder has a contamination delay of 15 ps from C​ to either output and 22 ps from A or in​ B to either output. Each flip­flop has a setup time of 30 ps, a hold time of 10 ps, a clock­to­Q propagation delay of 35 ps, and a clock­to­Q contamination delay of 21 ps. (a) If there is no clock skew, what is the maximum operating frequency of the circuit? (b) How much clock skew can the circuit tolerate if it must operate at 6 GHz? (c) How much clock skew can the circuit tolerate before it might experience a hold time violation? Solution: (a) (b) 1 6GHz ≥ 130ps + tskew tskew ≤ 36.66 ps (c) Homework #6 CSE140 Spring 2015 Prof. Tajana Simunic Rosing 1. Problem 1 Capture the following system behaviour as an HLSM. The system counts the number of events on a single­bit input B and always outputs that number unsigned on a 6­bit output C, which is initially 0. An event is a change from 0 to 1 or from 1 to 0. Assume that system count rolls over when the maximum value of C is reached. Solution: 2. Problem 2 Use the RTL design process to design a system that outputs the average of the most recent two data input samples. The system has an 8­bit unsigned data input I and an 8­bit unsigned output. The data input is sampled when a single bit input S changes from 0 to 1. Choose the internal bit widths that prevent overflow. Solution: Grading: Step 1: 3 points Step 2: 3 points Step 3: 2 points Step 4: 2 points 3. Problem 3 Create a high­level state machine for a digital bath­water controller. The system has a 3­bit input ​ ​ ratio indicating the desired ratio of cold water to hot water, and a bit input ​ on indi​ cating that the water should flow. The system has two 4­bit outputs ​ ​ hfIow and cfIow​ , controlling the hot water flow rate and the cold water flow rate. The sum of these two rates should always equal 16. Your high­level state machine should determine the output values for ​ ​ cflow​ hflow and ​ such that the ratio of hot water to cold water is as close as possible to the desired ratio. while the total flow is always l6. Hint: ​ As there are only 8 possible ratios. a rea​ sonable solution may use one state for each ratio. Solution: Note: Multiple solutions are possible but the basic idea is the use of an Init state to route transitions. More than one clock cycle is required to change the ratio. 4. Problem 4 Convert the following C­like code, which calculates the greatest common divisor (GCD) of the two 8­bit numbers, ​and ​ into a high­level state machine. Then, use a ​ b , ​ the RTL design process to convert the high­level state machine to a controller and a datapath. Design the datapath to structure, but design the controller to the point of an FSM only. Ipt:bt ,bt ,btg nus yea yeb i o Otus yegd i oe upt:bt c,btdn wie1 hl(){ wie g ; hl(!o) dn ; oe=0 wie =b){ hl(a! i(a>b){ f a=a­b ; }es le{ b=b­a ; } } gd=a c ; dn ; oe=1 } Solution: Grading: Step 1: 3 points Step 2: 3 points Step 3: 2 points Step 4: 2 points ...
View Full Document

0 thoughts on “Cse 140 Homework 10-2

Leave a Reply

Your email address will not be published. Required fields are marked *