You may work with your classmates on these problems. If you work closely with another person,
feel free to submit your work jointly. Submit as PDF via Moodle.
You may use a digital logic simulator, but neat, hand-written diagrams are just as good, and often better
(note, for example, that some of the simulators don't have objects to represent multiplexers, decoders, etc.).
Goals
- Practice assembling low-level components like multiplexers and flipflops into
more complex circuits that do things that could be useful.
- Get more comfortable with those components (you're going to need that comfort
when we study datapaths.
Background
Imagine you have a clock line connected to an oscillator, so the clock line goes steadily up and down
from 0 to 1 to 0 to 1.... Each of the scenarios below describes a system whose state changes
each time the clock line drops from 1 to 0. For each scenario, your job is to draw a digital logic diagram that takes
the clock line as input, and whose behavior is as described in the scenario.
To do this, you may use any of the basic digital logic elements we have discussed in class:
multiplexers, decoders, adders, shifters, D-flipflops, 2-dimensional memory arrays, and of course
the individual gates NOT, AND, OR, NAND, NOR, and XOR. You may also include as many LEDs
as you wish (each LED has a 1-bit input line, and lights up if and only if the input line's value is 1).
You may not, however, include multipliers or dividers unless you draw them out in full and make sure
the clocking works as intended. (But if you find yourself doing so, you might want to think about whether there's
a better way to solve your problem. Hint: yes.)
Unless otherwise directed by a scenario, you may assume that you can preset the values of all
the latches and flipflops in your circuit
to whatever value you want them to have at the start. All zeros is nice, but if you need some other
initial values, go ahead and say so.
You may also assume that the clock line's cycle time is long enough to allow all the elements
in your circuit to stabilize between drops of the clock. The issue of clock cycle time will occupy
much of our attention in the coming weeks, but for now, just assume it's long enough for whatever you need.
Since most of these scenarios involve the behavior of lights which we're imagining a human being will
observe, I'll be imagining a cycle time of something like 1 second.
There are many ways to implement each of these scenarios. Think about how to do so
simply and elegantly, when possible. Sometimes a problem just requires brute force, but other times,
a bit of cleverness can yield a beautiful solution.
The scenarios
- There is a circle of eight LEDs. Initially, the topmost LED is lit and the others are dark.
At each drop of the clock, the next LED in a clockwise direction lights up, and the other seven
go dark. From the viewer's point of view, it looks like the light is moving around in a circle.
- Same story as #1, but now there are ten LEDs instead of eight.
- Same story as #1, but whenever an LED goes on, it stays on forever. That is, the clock may keep
ticking, but once the lights have filled the circle, they just stay on with no change.
- Now imagine there's an additional input line (call it S) connected to a toggle switch
that remains either on (1) or off (0) throughout the running of your circuit.
If S is 0, things go as in #1. If S is 1, things go as in #1, but counter-clockwise.
- Suppose you have a display device L that takes a 5-bit line as input, and displays
the corresponding letter in the Latin alphabet. So if L's input is 00000, L displays A,
00001 → B, 11001 → Z, etc. As the clock ticks, L should display the letters
of a message of your choosing, like "FREE THE MOOSE" or "NANDS ARE UNIVERSAL".
(Don't worry about what L displays for 11010 through 11111.
Maybe punctuation? Numbers? Fragments of
Bob Dobbs's face (as
on the Atari ST)?)
- Suppose there's a row of 32 LEDs, representing a 32-bit non-negative binary number. Initially,
the LEDs are all dark (i.e. the number represented is zero). With each drop of the clock, the
number displayed shows the next perfect square. So the numbers displayed are 0, 1, 4, 9, 16, 25, etc.
until the squares get too big for 32 bits and wrap around.
- Suppose there's 32-bit register R that is initialized to some non-negative integer N.
Consider the Collatz Conjecture,
also known as the 3n + 1 problem. At each fall of the clock, a row of 32 LEDs
shows the current number in the Collatz sequence starting at N. (If the conjecture is
correct, then eventually your lights will cycle between 4, 2, 1, 4, 2, 1, 4, 2, 1... (or more
accurately 100, 010, 001, 100, 010, 001,...). Don't worry about overflow. If it happens, it
happens.