CPSC 121 - Models of Computation

Lab 03

1 Important Information (no marks)

• Pre-labs must be submitted on PrairieLearn one hour before the start of
your designated lab session. Labs must be completed during the session, not
beforehand

• Pre-labs are to be completed and submitted individually. You may discuss general
ideas partners but you may not work together on the same pre-lab.

• Each lab is comprised of numbered TODOs. Raise your hand for TA’s to check off
each TODO as you complete them. You should continue to work on the rest of the lab
while waiting, or you will run out of time.

• The labs in CPSC 121 have a standard marking scheme.

• Your lowest lab grade is dropped. There are no make-up labs.

• All labs are worth 10 marks.

– 2 marks for correctly doing the pre-lab.

– 5 marks for TODO: in red bold. (completion mark).
– 1 mark for TODO (Further Analysis): (discussion with TA).
– 1 mark for lab survey (done individually).
– 1 mark for clean-up for labs that use the Magic Box, otherwise another TODO.

• 1 bonus mark can be earned at the TA’s discretion for completing the Challenge Ques-
tion, which can carry over to your overall course mark.

• Labs end 10 minutes before the next hour. Students are expected to complete the lab
and clean up in 1 hour and 50 minutes. Do not expect TODOs to be checked off during
the spare 10 minutes, it will be at the TA’s discretion.

• You will not be allowed to complete a lab if you are more than 7 minutes late.

1
PreLab Solutions

Solution:

1. (Auto-graded: 0.50) There are 2 potential solutions:

MUXs should be the only gates used (it should not be terribly convoluted).

2. (Auto-graded: 1.50)

• (0.50) Correct truth table for both chain and tree

• (0.50) Correct answer to whether they are equivalent. Any of
AND/OR/XOR/XNOR are equivalent, NAND/NOR are not equivalent.
• (0.50) Correct circuit diagram for both chain and tree

2
2 Working with Multiplexers (1 mark)
1. Look up the LS157 chip in The Magic Box User’s Manual (you can find it in at the
Handouts Module on Canvas or here). The LS157 chip contains four 1-of-2 multiplexers
(with a single shared select input). Be sure that you read the documentation on the
ENABLE input carefully!

2. TODO 1: Wire up a multiplexer in the LS157 chip on your breadboard, and verify
that it has the same truth table as a 1-of-2 multiplexer.

Solution:

Students should walk their TA through the wiring. Demo of the IC should show that the
truth table matches that of a MUX from pre-lab. When select is 0, the output value should
match input A. When select is 1, the output value should match input B.

3 Subcircuits (1 mark)
1. Circuit design is done much like software design. In code, we break our programs up
into functions or methods: these can then act as self-contained modules, which can be
reused easily. This modularity is also a principle of good circuit design. Download the
file [Link] on Canvas (go to the Labs page on Canvas and search for Lab 3 files),
and open it in Logisim (File, then Open)(Note: Students using MacOS may need to
move [Link] to their home folder or desktop). Modules in Logisim are represented
by rectangles. You will see a program that has six identical modules wired up in a
chain:

3
2. Our goal with this activity is to edit the P module to implement what is called a
priority chain. In this priority chain, the only light that will be turned on is the one
at the leftmost module where b is on. All other lights remain turned off. This module
of the chain is said to have the priority. We also say that stages to the left have higher
priority than stages to the right. Here is an example:

3. We see in this image that the first module where b = TRUE has x illuminated, but
later modules with b on do not. Also, note that the first a of the circuit is connected
to ground (FALSE). Therefore, we want a circuit which has the properties:

• x is only on if a is off and b is on.

• y is only on if a is on or x is on.

4. TODO 2: Fill in the P module in our Logisim circuit so that main has a working
priority chain like in the example described above. Test whether the circuit works as
expected. To edit the module, right-click P in the upper left-hand menu (underneath
main) and select Edit Circuit Layout. You will get a circuit like this (Note: Don’t
move the pins in the layout! You do not need to use a multiplexer):

5. Once you’ve filled in this circuit, switch back to the main module by right-clicking it in
the upper left-hand menu and selecting Edit Circuit Layout. Verify the priority chain
works as expected, and then show it to your TA.

4
 Note: On the bottom left-hand of your Logisim screen is the Attributes Panel. This
allows you to change certain attributes of various components. For example, you can
change the number of inputs to a gate, or the number of data bits to each input or
output. You can also change the size of a gate, or the direction it faces.

Solution:

Should be implemented exactly how the instructions say to:

• x is only on if a is off (0) AND b is on (1).

• y is only on if a is on (1) OR x is on (1).

4 Chains and Trees (3 marks)

1. Download the file [Link] on Canvas (go to the Labs page on Canvas and search
for Lab 3 files) and open it in Logisim. It will look like the image below:

5
2. TODO 3: Add the gates and connections for the NOR chain and XOR tree following
the pattern of the file. Then, answer the following questions:

• Which of the chains and/or trees compute the function that is true if and only if
an odd number of the inputs A, B, C, and D are true?
• Which chains and/or trees compute the function (A ∧ B) ∨ (C ∧ D)?
• How did you determine these? How many different strategies can you think of
to analyze circuits like this? What are the advantages/disadvantages of these
strategies and of the one(s) you used?

6
Solution:

• IF AND ONLY IF an odd number of inputs are True - XOR Chain & XOR Tree

• (A ∧ B) ∨ (C ∧ D) - NAND Tree

Strategies:

• Truth Table: Thorough, but it is long, tedious, and easy to make mistakes when
generating it. Can be efficient if using software that builds it automatically (such as
Logisim).

• Trial and Error: Efficient but can be easy to make mistakes and not be thorough
enough.

• Logical Equivalencies: It’s conditional - the NAND tree here can turn into (A ∧ B) ∨
(C ∧ D) with a single DeMorgan’s law application and is efficient and rigorous here.
However, this does not appear very often, and more often you cannot get from one
expression to another through logical equivalencies.

3. Scalability is a critical issue in computer science: Will a system slow “too much” as
we increase the number of inputs that it handles? For this lab’s prelab, you drew two
circuits - one of these was a tree and the other was a chain. Although they have the
same number of gates, one of these circuits takes a longer time to return its output.
In general, for a particular gate, the tree and chain implementations will differ in how
well they scale as the number of inputs increases.
TODO 4: Answer the following questions, assuming each gate takes 20 picoseconds
to produce its result.

• How long will it take for the 3-gate AND chain to produce its result? How long
for the 3-gate AND tree?
• To determine whether the digits of a 128-bit binary number are all 1s, we can
turn the 128 bits into individual Boolean values and put them through either the
AND chain or the AND tree, as inputs. Using the same assumption as before,
calculate how long it would take for the 128-bit AND chain, and for the AND
tree. What would be the difference in speed? (Hint: Draw out how the tree scales
up! Try to see how a 4 input tree compares to an 8 input tree.)

7
Solution:

3 Gate:

• 3-gate AND chain: 60 ps

• 3-gate AND tree: 40 ps

128-bit:

• 128-bit AND chain: (n-1) * time = (128-1) * 20 = 127 levels * 20 ps = 2540 ps

• 128-bit AND tree: log2 n * time = log2 128 * 20 = 7 levels * 20 ps = 140 ps

• The AND tree scales logarithmically according to the number of inputs. This is as
the number of levels the signal needs to pass through will scale logarithmically, as the
number of inputs to a given level will halve at each level.

5 Further Analysis Question (1 mark)

1. TODO 5 (further analysis): Answer the following questions:

(a) Consider the amount of time a circuit takes to produce an output for a given a
number of inputs. Which scales better as the number of inputs increases: trees
or chains? Why?
(b) Look back at your pre-lab on how to make a 1-of-4 multiplexer. This 1-of-4
multiplexer has a delay of 2 time units (1 time unit for each 1-of-2 multiplexer)
before the selected signal is propagated to the output. How many time units of
delay would a 1-of-8 multiplexer have? Now consider a 1-of-n multiplexer: how
does the propagation delay of this multiplexer scale as n increases? We are looking
for a formula that relates the number of time units in the delay to the size of the
multiplexer (n).

Solution:

• Trees are faster. This is as the number of levels/gates to pass through scales logarith-
mically rather than linearly as n (number of inputs) increases.

• t = Log2 (n). Note that a 1-of-n MUX takes the same form as the trees we’ve been
looking at all lab. The number of inputs is divided by two at each level (a logarithmic
relationship).

8
6 Survey (1 mark)
TODO 6: To help us improve these labs both this term and for future offerings, complete
the survey here1 . After you submit your survey, you will get a confirmation page; show that
to your TA.

7 Magic Box Cleanup (1 mark)

TODO 7: Return the Magic Box in proper conditions to your TA. Make sure that:

• All wires are placed back in the case relatively neatly.

• All components of the Magic Box are present (wires, breadboard, Magic Box Signal
Generator, power cable).

• The Power Cables should be wound up neatly.

8 Challenge Problem (Bonus Marks)

Think back to earlier in the course when we asked you how to design a light controlled by
switches. Here, we’ll expand on this problem by making you design and analyze a more
complicated light-switch problem - this time, we want to have an additional switch acting
as a "master switch" that alters the circuit’s behaviour.
Download the file light_switch.circ on Canvas (go to the Labs page on Canvas and search
for Lab 3 files) and open it in Logisim. It will look like the image below:

Remember that for a 3-switch problem, the circuit looked like this, designed using XOR
gates:

To get the mark for the challenge problem, complete the following two questions:
1
[Link]

9
 • TODO 8 (challenge): Complete the circuit according to the following specifications.

– There are three regular switches (a, b, c). This XOR circuit is ON if an odd
number of them are ON. This is already built for you in the XOR_Circuit
submodule.
– If M1 is OFF, then the output of the circuit is always OFF. Otherwise, M1 does
not affect the circuit.

• TODO 9 (challenge): Analyze your circuit. What is the propagation delay for this
circuit? Similarly, what would be the shortest possible propagation delay for an n-
input circuit, with a single master switch?
Hint: Consider:

– Is the propagation delay the same for every input?

– How would the XOR_Circuit scale up as n increases?
– Specifically, how would this circuit be structured? Are there multiple ways to
structure it?

Solution:

Circuit is simple enough, just requiring an AND gate.

Analysis:

• For this circuit, the propagation delay would be 3 time units (if we changed one of the
inputs a,b,c), or 1 time unit if we changed M1.

• For an n-input circuit, the propagation delay would be log2 n + 1 time units for any
of the XOR-inputs (as the XOR-circuit can follow a tree structure), and the delay for
M1 would be 1 time unit. Note that M1’s delay never changes as we’ve fully separated
these two parts of the circuit.

10