Homework Combinatorial Logic

A Universal Function Generator

As an exercise, we would like to implement the controlled not (CNOT) function. The CNOT function takes to inputs $n$ and $i$ and produces a single output $o$, which corresponds to the value of $i$ or its negation if $n$ is 0 or 1, respectively.

Question 1: Complete the truth table of the CNOT function:

Question 2: Give a Boolean equation that realizes the CNOT function:

$CNOT(n,i)=$

Question 3: Based on you solution, draw a combinatorial circuit for CNOT using ony the basic gates AND, OR, NOT.

Recall the multiplexer circuit that has been introduced in the lecture:

It can be generalized to $N$ select inputs, selecting among $2^N$ data inputs. It turns out that we can use a multiplexer with $N$ select inputs in order to create any combinatorial Boolean function with $N$ inputs by setting the data inputs to appropriate constant values.

Question 4: Draw an alternative implementation of CNOT. This time, use only a 4-to-1 multiplexer with constant data input values.

Propagation Time

Carry-Ripple Adder

Consider the carry-ripple adder presented in the lecture:

We would like to determine the computation time of this operator for inputs (and outputs) of size $P$. We consider the following propagation times for a full adder cell:

• Propagation time from any input to the carry output: 1 ns
• Propagation time from any input to the sum output: 2 ns

We assume that all inputs are valid at the same time $t=0$.

Question 5: Find the computation time of the carry-ripple adder of size $P$.

A Faster (?) Addition

The principal problem with the carry-ripple adder is the length of its critical path (the carry chain). There are several alternative structures which have lower propagation time, but which need more logic gates. One of such designs – called carry-select adder – is shown in the figure below. It implements an 8-bit adder using several 4-bit (carry-ripple) adders and some multiplexers:

Question 6: Explain how the design works.

We consider the following propagation times for basic elements (full adder, multiplexer):

• Propagation time from any input to the carry output: 1 ns
• Propagation time from any input to the sum output: 2 ns
• Propagation time of a multiplexer: 1 ns

Question 7: With the above information, establish the computation time of the carry-select adder, and compare it to the carry-ripple adder of the same size.