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.