## Description

## Exercise 1. [6 marks]

Re-write the following Boolean expression using only NAND operations. Show your step-by-step process. You do not need to simplify.

(𝑝 + 𝑞) ⋅ 𝑟

## Exercise 2. [10 Marks]

Prove that NOR is functionally complete. You should give formulas as well as truth tables to support those formulas. You can use the symbol ↓ for NOR.

Exercise 3. [10 marks]

Draw a 4-bit Serial In, Serial Out register using SR flip-flops.

For example, the below diagram represents a Parallel In, Parallel Out 𝑛-bit register using D

flip-flops.

clock

2

## Exercise 4. [20 marks]

In this exercise you are to construct an ALU with the following

specification:

• The ALU takes 3 different 32-bit inputs: A, B, C; and has one 32-bit output: D.

• The ALU supports 8 different operations:

– A + B (addition)

– A – B (subtraction)

– MAX(A,B,C)

– MIN(A,B,C)

– A & B (bitwise AND)

– B & C (bitwise AND)

– A | B (bitwise AOR)

– B | C (bitwise OR)

To construct this ALU you will follow a modular design. Assume you have an unlimited

number of the following gates and combinational circuits at your disposal, but no others:

• 2-arity AND gate,

• 2-arity OR gate,

• NOT gate,

• 2-way MUX,

• bit-wise AND circuit: it takes two 32-bit inputs and has a 32-bit output which is the

bit-wise AND of its inputs.

• bit-wise OR circuit: it takes two 32-bit inputs and has a 32-bit output which is the

bit-wise OR of its inputs.

• 32-bit ADDER: it takes two 32-bit inputs, a 1-bit control signal, and has a 32-bit

output. If the control signal is 0, the circuit outputs the sum of its inputs. If the

control signal is 1, the circuit outputs the difference of its inputs. The inputs and

outputs are assumed to be 32-bit two’s complement numbers.

• COMAPRATOR: it takes two 32-bit inputs, a 1-bit control signal, and has a 32-bit

output. If the control signal is 0, it outputs the minimum of its two inputs. If the

control signal is 1, it outputs the maximum of its two inputs. The inputs and outputs

are assumed to be 32-bit two’s complement numbers.

(a) Give the specification of the ALU by determining the number of control signals needed

and then:

(𝑖) present a table specifying the control signal values and the operation the ALU performs

given those control signal values;

(𝑖𝑖) draw a schematic diagram (Lec. 7, pg. 5) for your ALU; include bit-widths and labels.

(b) Using a modular design and the previously stated circuits and gates, draw a circuit which

fulfills the specification of your ALU given in part (a). (Hint: you can have multiple input

wires with the same label; you can have control signal “stubs”; see Lecture 7, page 25.)

3

## Exercise 5. [10 + 8 + 8 + 8 = 34 marks]

In this exercise we will explore designing

an integrated circuit for use within a microwave. Not the whole thing (that’s too complex),

but just a small piece of it.

Consider that the microwave already has a circuit which controls the timer and the magnetron

(the thing that produces the microwaves). Your goal is to design a simple circuit which

controls the turntable. The turntable is powered by a gear box which takes two input bits:

• 𝑅. If 𝑅 ≡ 1, the gear box rotates. If 𝑅 ≡ 0 the gear box does not rotate.

• 𝐶. If 𝐶 ≡ 1 and 𝑅 ≡ 1, the gearbox turns clockwise. If 𝐶 ≡ 0 and 𝑅 ≡ 1, the gearbox

turns counterclockwise.

The manufacturer of this microwave requests a synchronous circuit which will control the

gearbox to alternate between clockwise and counterclockwise rotation each time

the microwave is turned on. The circuit to be designed will receive a single input bit 𝐼

from the circuit controlling the magnetron.

• When 𝐼 ≡ 1, the turntable should rotate.

• When 𝐼 ≡ 0, the turntable should not rotate.

To guide your design process, complete parts (a) to (d) below.

(a) Draw a Finite State Machine which describes this state circuit. Since this circuit has

4 possible combinations of outputs, it should have 4 states. Be sure to include the inputs

and outputs in the FSM. Order the outputs as 𝑅𝐶.

Hence, a transition in the FSM will be

labelled as 𝐼⇑𝑅𝐶. The change in direction should be triggered by the microwave turning on.

(b) Create a truth table to describe the inputs, outputs, and transitions of your FSM. That

is, create a truth table describing the combinational logic of your eventual state circuit.

Since

there are 4 states, you must have 2 bits of “input” to encode the current state, and 2 bits of

“output” to encode the next state. (Hint: your table should have 8 rows and 7 columns.)

(c) Give the DNF for each output of the combinational part of your state circuit (there are

4 of them; recall that the “next state” is part of the combinational logic output). Then,

simplify each DNF into a reduced sum of products.

For this particular question, you do not

need to specify the Boolean law being applied at each step of the simplification.

(d) Draw a circuit which implements the combinational logic of your turntable controller

circuit.

That is, draw a circuit implementing your 4 simplified formulas from part (c). Use

gates with arity at most 2. For clarity (and to avoid crossing too many lines), you may draw

4 independent circuits, one for each output bit.

4