EECS 31/CSE 31/ICS 151 Homework 4 Questions with Strategies

View Questions Only
View Questions with Solutions

Problem 1

Question

(Adders) Design a 2-bit adder slice that will combine the functions of two FAs. Using the library presented in Table 3.14, compare the delay of your design with that of the design shown in Figure 5.1.

  1. Write out sum and carry equations for S1, S2 and C1, C2 from X2, Y2, X1, Y1 and C0.
  2. Substitude C1 in S2 and C2 equations with its correspondent expression.
  3. Draw the correspondent logic schematic with AND, OR and XOR gates.
  4. Compute input/output delays.

Strategy

  1. Write out sum and carry equations for S1, S2 and C1, C2 from X2, Y2, X1, Y1 and C0.
  2. Substitude C1 in S2 and C2 equations with its correspondent expression.
  3. Draw the correspondent logic schematic with AND, OR and XOR gates.
  4. Compute input/output delays.

Problem 2

Question

(Carry-look-ahead generators) Design a 64-bit CLA adder, using:

  1. One level of CLA
  2. Two levels of CLA
  3. Three levels of CLA

Strategy

  1. Serially connect sixteen 4-bit CLA adders (Figure 5.2 (c)) together.
  2. Serially connect four 16-bit two level CLAs adders (Figure 5.3 (b)) together.
  3. Connect four 16-bit two level CLAs adders with a CLA generator

Problem 3

Question

(Logic units) Design a logic unit that will perform the following combinations of operations.

  1. NAND, NOR, transfer, and complement
  2. XOR and XNOR

Strategy

  1. Develop truth tables for the required functions.
  2. Assign encoding of the control lines S1 and S0 to each function.
  3. Generate Boolean expression.
  4. Draw logic schematic.

Problem 4

Question

(ALUs) Design an ALU that can perform add, subtract, NAND, and NOR operations.

Strategy

  1. Assign control encoding for each operation, develop truth table for AE and LE.
  2. Develop Boolean expressions for AE and LE.
  3. Implement the expressions with gates.

Problem 5

Question

(Decoders) Design a 4-to-16 decoder, using:

  1. 1-to2 decoders
  2. 2-to-4 decoders

Strategy

  1. Draw 4 rows with 1, 2, 4 and 8 1-to-2 decoders.
  2. Connect the input MSB to the input in the top row, next to MSB to the input in the second row and so on.
  3. Connect E to the enable of the decoder in the first row, and the ouptuts from the first row decoder to the enables of the most significant decoders in the second row, the outputs of the decoders in the second row to enables of the third row decoders and so on.

Problem 6

Question

(Comparators) Design the serial and parallel verions of a comprator that can compare the following types of number representation.

  1. Sign-magnitude
  2. Two's complement
  3. Floating point

Strategy

  1. Develop the algorithms for the comparisons (pseudocode )
    1. Sign-magnitude numbers: 
      
if (MSB(X) < MSB(Y)) then        Output (X > Y)
else
       if (MSB(X) > MSB(Y)) then Output (X < Y)
       else
              if (MSB(X) = MSB(Y) = 0) then      
                     if (X > Y) then         Output (X > Y)
                     if (X < Y) then         Output (X < Y)
                     if (X = Y) then         Output (X = Y)
              else                                               
                     if (X > Y) then         Output (X > Y)
                     if (X < Y) then         Output (X < Y)
                     if (X = Y) then         Output (X = Y)
end
    2. Two's complement 
      
if (MSB(X) < MSB(Y)) then        Output (X > Y)
else
       if (MSB(X) > MSB(Y)) then Output (X < Y)
       else                                                      
              if (X > Y) then                Output (X > Y)
              if (X < Y) then                Output (X < Y)
              if (X = Y) then                Output (X = Y)
end
    3. Floating point 
      
if (MSB(X) < MSB(Y)) then        Output (X > Y)
else
       if (MSB(X) > MSB(Y)) then Output (X < Y)
       else
              if (MSB(X) = MSB(Y) = 0) then
                     if (X > Y) then         Output (X > Y)
                     if (X < Y) then         Output (X < Y)
                     if (X = Y) then         Output (X = Y)
              else                                              
                     if (X > Y) then         Output (X > Y)
                     if (X < Y) then         Output (X < Y)
                     if (X = Y) then         Output (X = Y)
end
  2. Make normal magnitude comparator (serial or parallel version, pg. 196 on textbook) to compare all bits except sign bits
  3. Try to design a logic for the sign bits and the output of magnitude comparator to implement different comparisons (This is the only difference of these three comparisons). The final outputs are G1 and L1
    1. Take the sign bits and the outputs of magnitude comparator as the inputs of the final outputs logic
    2. Develop truth table for the algorithm and get the output functions for G1, L1
    3. Develop logic schematic for the final outputs

Problem 7

Question

(Shifters) Design an 8-bit barrel:

  1. Left rotator
  2. Left shifter
  3. Left and right shifter
  4. Left and right shifter/rotator

Strategy

  1. Left rotator
    1. Draw a row of selectors for the first level. The first row of selectors shift to the left by 1 bit
    2. Draw a row of selectors for the second level. The second row of selectors shift to the left by 1 bit
    3. Draw a row of selectors for the third level. The third row of selectors shift to the left by 1 bit

  2. Left shifter

    The left shift is similar to that of the left rotator shown in part (a). The differences between the two architectures are that in a shifter, there is no "wrap-around" for each of the levels. Thus, shift inputs for d0 on the first level, d0 and d1 on the second level, and d0, d1, d2, d3 on the third level are connected to the value 0

  3. Left and right shifter
    1. The left and right shifter operation can be performed by combining the left shifter and right shifter with the according shifts of input bits for the appropriate direction
    2. To differentiate between whether to shift left or shift right, a new input bit (eg. L/R) can be used
    3. For each level, there should be two rows of selector to describe either the left shifter or right shifter
  4. Left and right shifter/rotator
    1. The shifter implementation should include zeros for "wrap-around" while the rotator implementation make d7 = d0 or d0 = d7
    2. For the first level, two additional selectors can be used to differentiate between choosing a selector or rotator
    3. For the second level, four additional selectors can be used to differentiate between choosing a selector or rotator
    4. For the third level, six additional selectors can be used to differentiate between choosing a selector or rotator

Problem 8

Question

(ROMs) Using a 16x4 ROM, implement a 2-bit comparator that can generate "greater than," "less than," and "equal to" functions.

Strategy

  1. Make 4-variable truth table for 2-bit comparison function.
  2. To implement the truth table with 16x4 ROM, connect the decoder outputs to the OR gate every time the functional output is equal to 1 for the corespondent minterm.

Design Synthesis Example

Question

Design a Polite & Stupid Elevator

Assumptions:

  1. There are three floors
  2. Door opens on every floor
  3. One button at any time

Strategy

Not available.