DIGITAL LOGIC SYSTEMS

PROJECT 4: STACK

The synchronous circuit Stack(m, n) implements a LIFO (Last in First

out) stack. The circuit is able to store at most m binary words, each word is

n-bits wide.

Specifications

Inputs: push, pop, CLK ∈ {0, 1}; Din ∈ {0, 1}

n

Outputs: Dout ∈ {0, 1}

n

; full, empty ∈ {0, 1}

Functionality:

(1) If push(t) = ‘1’ then Din[n − 1 : 0](t) will be stored at the head

of the stack: Dout[n − 1 : 0](t + 1) = Din[n − 1 : 0](t). All

the previously stored items are pushed downwards. If the stack

already holds m words, then the push won’t take place.

(2) If pop(t) = ‘1’ then the head item is removed from the stack,

and the next item takes its place.

(3) full = ‘1’ iff the stack holds m items.

(4) empty = ‘1’ iff the stack holds 0 items.

(5) Dout[n − 1 : 0] outputs the head-word of the stack. If the stack

is empty, then Dout[n − 1 : 0] = 0n

is outputted.

(6) Assume that the inputs push and pop may not be high simultaneously.

CLK

pop

push

Din Dout

3 3

full

empty

010

111

000

101

110

000

000

000

“head-word”

Figure 1. A schematic example of Stack(8, 3). The gray

cells represent the occupied cells. In this example, the values

that have been pushed to the stack are: ‘110’, ‘101’, ‘000’,

‘111’ and the last one was ‘010’. The current head-word is

‘010’. If pop = 1 is fed for one clock cycle, then ‘010’ will be

thrown out and ‘111’ will become the head-word.

1

DLS: PROJECT 4 2

Your Assignment

(1) Complete the circuit Stack from the template template stack.circ

to implement Stack(3, 3).

(2) The clock period of a synchronous circuit is defined according to the

longest path between two flip flops (assume that the IO ports are

also coming to/from flip-flops). Make sure that the clock period is

constant (O(1)) and doesn’t depend on n.

Submission Instructions

(1) Submit a single Logisim (“.circ”) file. No prints/screenshots. This

file must be named ID1 ID2 stack.circ with ID1 and ID2 replaced

by each partner’s 9 digit ID number.

(2) Use the provided template stack.circ file as a template, and implement your designs in the circuit named Stack. Do not move or

modify the input/output ports, the “blackbox” layout, and the names

of the circuits!

(3) Only one of the students in a pair needs to upload the submission.

Do not upload the same work twice!

(4) You may not use gates with fan-in larger than 2. Exception is for

Logisim’s MUX2:1, with a fan-in of 3, however is allowed to be used.

(5) You are allowed to use the data-bits attribute of the gates to perform

bitwise operations.

(6) You are allowed to use “Arithmetic” library of Logisim (Adder,Shifter

circuits). as well as the “Plexers” library.

(7) From the “Memory” Library you are allowed to use the “D Flip-Flop”

element as well as the “Register” element. The Register is a parallel

load register we studied, which has a clock enabled input.