Computer Architecture: Logic Design Problem Set Solution

Problem 1:

Simplify the following equations using Boolean theorems. Check the correctness using a truth table and a K-Map. (3 points each for the Boolean simplifications, 1 point for the truth table, 3 points for the K-map, 3 point for the resultant circuit)
    1. =   +

    2. =   ++(  +  )


Problem 2:

Write the sum of products canonical representation (minterms) for each of the following truth tables. Y is the output of the circuits.
















0

0

0

1
















0

0

0

1
0

0

1

0
















0

0

1

0
0

1

0

0
















0

1

0

1
0

1

1

0
















0

1

1

0
1

0

0

0
















1

0

0

1
1

0

1

0
















1

0

1

0
1

1

0

0
















1

1

0

1
1

1

1

1
















1

1

1

0
















Problem 3:

Minimize each of the circuits in Problem 2 and implement them using a simple combinational circuit using two-input AND and OR gates, and/or a NOT gate.

Problem 4:

Design the simplest sum of products circuit that implements: ( !, !, !) =    (0,1,2,3,4,6,7). Use Boolean algebra to simplify the function and confirm your solution using K-Maps.



Problem 5:

Consider the following truth table:

!

!

!

  (  !, !, !)
0

0

0

0
0

0

1

1
0

1

0

0
0
1
1
0
1

0

0

1
1

0

1

1
1

1

0

1
1

1

1

0

Show its sum of products (SoP) and product of sums (PoS). Also, use Boolean algebra to find the minimum-cost SoP form.
Consider the following truth table:

!

!

!

  (  !, !, !)
0

0

0

1
0

0

1

×
0

1

0

1
0

1

1

1
1

0

0

1
1

0

1

×
1

1

0

0
1

1

0

0

Use K-Maps to design the simplest sum of products circuit.

Problem 6:

Find a minimal Boolean Equation for the truth table given below. Remember to take advantage of the don’t care entries. Draw the resultant circuit.











0

0

0

0

×
0

0

0

1

×
0

0

1

0

×
0

0

1

1

0
0

1

0

0

0
0

1

0

1

×
0

1

1

0

0
0

1

1

1

×
1

0

0

0

1
1

0

0

1

0
1

0

1

0

×
1

0

1

1

1
1

1

0

0

1
1

1

0

1

1
1
1
1
0
×

I 1


I 1

1

1

1
Problem 7:

Consider the following circuit. What is its truth table?












What is the minimal-cost expression for this true table? Find the simplest SoP and confirm your solution using K-Maps.


Problem 8:

The following circuit (with NOT and 2-input AND gates) implements the 2-4 decoder.












d3    d2    dl    dO

Design a 3-8 decoder circuit with NOT and 2-input AND gates. How many gates (NOT and 2-input AND gates) are needed to build the n-2n decoder?


Problem 9:

Give the Boolean expression for the function performed by the following circuit:


C  D



A B

1
00
1



01
~----1  01
y




0
10
1 ---- t




' -----10j





0

0
11

--=---- t -  11
----1




Problem 10:

Implement the following truth table as described below:









0

0

0

1
0

0

1

0
0

1

0

0
0

1

1

0
1

0

0

0
1

0

1

0
1

1

0

0
1

1

1

1

    1. Using a 3:8 decoder and one other logic gate

    2. Using a 8:1 multiplexer
    3. Using a 4:1 multiplexer and one inverter
    4. A 2:1 multiplexer and two other logic gates


Problem 11:

Identify the Boolean equation performed by the circuit below and minimize the circuit and implement it using simple gates.


C    D




A

1


0
01

0
---, 10
y

0

1



1---,  1





Problem 12:

Design a 4-to-16 decoder using five 2-to-4 decoder

Problem 13:

Design a 32-to1 multiplexer (MUX) using
    1. 8-to-1 MUX and 2-to-4 decoders.
    2. 4-to-1 MUX and 2-to-4 decoders.

Problem 14:
Given a 3-input Boolean expression    (  !,    !, !) =    (0,2,4,6,7).

    1. Implement this expression using only 2-4 decoders and OR gates.

    2. Implement this expression using only 4-1 MUX.

Problem 15:

Implement the function ( !, !, !, !, !) = ! ! ! ! + ! ! + ! ! + ! ! + ! ! ! by using a 4-to-1 multiplexer and as few other gates as possible.

Problem 16:
Consider the Boolean function    (  !,    !, !) =  !  ! + !  ! + !  !  !.

    1. Use a 3-to- 8 decoder plus logic gates to implement this function.
    2. Use an 8-input multiplexer to implement this function.


Problem 17:

Gray codes have a useful property in that consecutive numbers differ in only a single bit position. The 3-bit gray code is given below.

0
0
0
0

0

1
0

1

1
0

1

0
1

1

0
1

1

1
1

0

1
1

0

0


Design a 3-bit modulo 8 Gray code counter FSM that has no inputs but produces three outputs. When reset the output should be 000. On each clock edge the output should advance to the next Gray code. After reaching 100, it should repeat with 000. Implement the circuit using combinational logic and D-flip flops.





Problem 18:

Design an FSM that detects a stream of two consecutive 1’s in a stream of 0’s and 1’s. Implement it using a combination of sequential and combinational logic.

INPUT:0110111010....

OUTPUT:0010011000....