Notes on homework assignment #3
			John Wawrzynek
			September 18, 2002


We hope these notes to help clear up some questions that have come up
regarding homework #3.


Problem #1.

Part b) asked for you to express the "delay in terms of 'gate delay'".
In this problem and throughout the semester we will sometimes use an
approximate way to characterize circuit delay.  When we refer to "gate
delay" we mean that we should assume that the input to output delay of
a single gate is one unit, regardless of the gate type and its fanout.
Of course, this assumption is wrong, but it is widely used, because it
gives us a quick and easy way to estimate the delay through a circuit.
What is really measures is the number of level of logic from input to
output.

For part b) of problem #1, assume that any type of gate
(for instance AND or OR) each contribute one unit of delay.


Problem #2.

From Mano: Problem 3-14.  The way to solve this problem is to first
simplify the Boolean function by using a K-map and than to reduce it
more by using factoring.  Remember that the K-map method leaves the
result in optimal 2-level form (either sum-of-products when grouping
1's or product-of-sums when grouping 0's), but not necessarily with
the minimal number of literals.  Often (and in this problem) it is
possible to further reduce a Boolean function by using more than 2
levels of logic.  The common method used to go from a 2-level form to
a 3- or more level form is by factoring.  Boolean algebra has two
factoring theorems:

xy + xz = x(y + z)
x + yz = (x + y)(x + z)

because AND distributes over OR and
OR distributes over AND.

To solve this problem you will need to use both of these theorems.
You will also need to use a K-map to generate both the sum-of-products
form and the product-of-sums form.



Problem #4.  Hint for part b): The Virtex block SelectRam (sometimes
called "block RAM") holds 4K bits total.  512 32-bit wide words
require 512 * 32 bits total.  The solve the problem, use simple 
arithmetic.



Problem #5.  This is a deep and interesting problem.  (Its a bit
of a trick problem that was designed to make you think hard.  If you
want to continue to think hard before you look at the answer consider
the following but don't read beyond this paragraph.  The given 
circuit can be implemented with only 3 CLBs!)

The given configurable logic block (CLB) structure is inspired by the
structure of the CLB slice in the Xilinx Virtex.  The Virtex slice has
two 4-LUTs followed by a 2-to-1 multiplexor.  This structure was
choosen by Xilinx because it permits the flexibility of using each LUT
independently to implement two separate functions of 4 inputs, can be
combined with the multiplexor to implement any single function of 5
inputs, or can be combined with the multiplexor to implement any
particular function from the subset of all functions of 9, 8, 7, or 6
inputs.

To understand how to use the two 4-LUTs together to implement any
function of 5 inputs (and why all functions of 6, 7, 8, and 9 inputs
is not possible), consider the following: A function of 5 inputs can
be represented with a truth table of 32 rows.  One-half of the
function, say the top half of the truth table, comprises 16 rows from
the truth table.  These 16 rows can be implemented in a 4-LUT and the
bottom half of the truth table implemented in a different 4-LUT.  4 of
the inputs to the 5 input function go to both LUTs and the 5th input
is reserved to choose between the two.  The 5th input essentially
distinguishes between the top half and bottom half of the 5-input
truth table.  Therefore the 5th input is used as the control input of
a multiplexor that chooses between the output of one 4-LUT and the
other.

One way to solve problem #5 is to consider the CLB in this problem as
a 4-LUT.  To do this, inputs b, c, and d would be wired to inputs e,
f, and g, respectively, resulting in 3 inputs.  The 4th 4-LUT input
would come from the CLB input labeled "a".  The FF option in the CLB
is not needed for this problem, because the given logic function
includes no flip-flops.  The given circuit can be "covered" using a
set of 4-LUTs.  Eight 4-LUTs can be used to map the left side of the
circuit, where the first 4-LUT has as input x0,x1,x2, and x3, and has
as output t9, the second 4-LUT has as input x0,x1,x2, and x4, and has
as output t10, etc.  This would leave the 8-input OR gate uncovered.
Obviously, this 8-input gate cannot be covered with a single 4-LUT.
Because the OR operation is associative and communtative, there are
many ways to cover this gate with 4-LUTs.  In all cases, at least 3
4-LUTs are needed.  One way would be to consider the 8-input OR as a
small tree with 2 4-input ORs leading to a 2-input OR.  In this case,
we would cover each OR with a 4-LUT, requiring 3 more 4-LUTs resulting
in a total of 11 CLBs to cover the entire circuit.

This solution to the problem is functionally correct but highly
non-optimal.

A more optimal solution can be arrived at by considering the special
structure and function of the given logic circuit and how it relates
to the structure of the CLB.  The given circuit is an 8-to-1
multiplexor.  Inputs x3 through x10 are the multiplexor data inputs
and inputs x0 through x2 are the control inputs.  Functionally an
8-to-1 input can be considered as a tree of 3 levels of 2-to-1 input
multiplexors.  The first level has 4 2-to-1 muxes (accepting a
total of 8 data inputs, x3 through x10), the next level has 2
2-to-1 muxes combining the 4 outputs of the first level, and the third
level has 1 mux combining the 2 outputs from the second level.
The control input x2 would be used to control the muxes in the first
level, x1 in the second level, and x0 the single mux in the third
level.

Now consider the given CLB.  Each 3-LUT can be used to implement a
2-to-1 mux.  The mux in the CLB can be used to implement a second
level mux in the multiplexor tree representation of the given circuit.
Therefore 2 CLBs are needed to implement the first 2 levels of the
muliplexor tree (a total of 6 2-to-1 muxes).  A third CLB is needed to
implement the third level of the muliplexor tree of the given circuit.
Therefor the given logic funtion can be implemented with only 3 of the
given CLBs.