One-week intensive course on
Hardware Description Languages for Synchronous Circuits

Gordon Pace, Koen Claessen

Exercises: Designing Small circuits

Monday 4th September

1. Gate Design
In the lecture today, we saw how gates can be implemented using transistors. A NOR gate is a gate that gets two inputs a and b, and has one output c. The output c is high if and only if both inputs a and b are low.

Exercise
Describe a NOR gate using 4 transistors.

2. Majority
The majority3 circuit is a combinational circuit with 3 inputs x1, x2, x3, and one output y. The circuit outputs high if at least 2 of the inputs are high, and outputs low if at least two of the inputs are low.

Exercises
a. Design the majority3 circuit in terms of logical gates. You may use block diagrams, textual notation, or any other description method you are familiar with.

b. (*) What is the general scheme to design a majorityk circuit, that has k inputs?

3. Always
The always circuit is a stateful circuit with one input in, and one output out. The circuit monitors its input in. As long as the input is high, the output out is also high. But as soon as in is low, then out becomes low and stays low forever.

Exercise
Design the always circuit in terms of logical gates and delay components. Again, you may use block diagrams, textual notation, or any other description method you are familiar with.

4. A Stack
In software, a stack is datastructure which supports three operations: push, pop and top. In this assignment, you are going to design a simple stack in hardware.

For simplicity, the data elements that are going to be stored in the stack are booleans (or, if you want, bits). The stack is implemented as a stateful circuit with three inputs, called push, pop, and data, and one output, called top.

The behaviour of the stack is as follows. If push is high, then the data element is pushed on the stack. If pop is high, then the top of the stack is taken away, and the data input is ignored. If neither push nor pop is high, nothing happens. At all times, the output top reflects the value of the top of the stack, so no special request to see the top of the stack is required.

It is unspecified what happens when push and pop are high at the same time, when the stack is empty and pop is high, and when the stack is full and push is high.

Exercises
a. Design a stack which can store at least 4 data elements. Again, you may use block diagrams, textual notation, or any other description method you are familiar with.

Hint: a possible stack design consists of four identical cells, each cell corresponding to a place in the stack. Cells keep track of the data stored in them and whether they are at the top of the stack or not.

b. Add two extra outputs, called empty and full, which are high if the stack is respectively empty or full.

c. Add one extra output, called error, which becomes high if something has gone wrong.

d. (*) What invariants hold for the delay elements in your design? (An invariant is a property which is true at all times).

5. (*) A Queue
Adapt your stack implementation to obtain a queue. Think of the interface to the queue you would like to have. Again, you can use any description method you like.