Design Feature: September 2, 1996
A
few weeks ago, I was wrestling with a cunning conundrum in the wee hours of the
morning, when my e-mail beeped in a threatening way. "Good grief," I
thought. "What sort of a lunatic would be playing on his computer at 3 am?
Don't people have lives anymore?" On perusing the ensuing message, I found
a plaintive plea for help from one of my loyal readers (the other one being on
vacation at the time).
Promptly parsing the preamble, I reached the first
paragraph of substance, whereupon I was informed that this young man's manager
had tasked him with creating some logic to transmogrify a master clock signal
into three subclocks with certain requirements of a phase-relationship nature.
Unfortunately, I'm an engineer, not a literature major, which means that I think
in pictures and equations, not those little squiggly black whatchamacallits...
words. What we needed here was a picture, so I closed my eyes and envisioned
Figure
1.
Ah, all became clear. The problem was obviously to take
a master clock and generate three subclocks. Why couldn't the boy bring himself
to say so in the first place? Reading on, I discovered that the master-clock
generator, which already existed, was some kind of VCO whose frequency you could
vary but whose duty-cycle you could not guarantee. However, the three outputs,
phases 1, 2, and 3, required a duty-cycle reasonably close to 50% (that is, an
equal mark-space ratio). Additionally, the Phase 2 output had to lag behind the
Phase 1 output by 60°, and the Phase 3 output had to lag behind the Phase 2
output by a further 60°. Obviously, another diagram was in order (
Figure
2). What on earth was he babbling on about?
Last but not least, he had to construct the entire thing from as few "cheap and cheerful," commercially available, off-the-shelf components as possible. (So, what else is new?) So, now I understood the problem, but did I really want this hot potato? Like most other engineers, I'm already putting in 26 hours a day at work, quite apart from trying to squeeze in a social life (or, at least, what passes for a social life in Huntsville, AL). So, I took the only sensible course of action, which was to put the problem on the back burner, eat some breakfast, and head to bed.
The following morning, I decided that my best course of
action for dealing with this poser was to forget all about it, which is my usual
mode of operation when my boss gives me something to do. But, you know what it's
like: Some problems just seem to keep on niggling away incessantly at the back
of your mind, and the only way to put them to sleep is to solve the gosh-darned
things. Initially, I started pondering some highfalutin ideas involving
sine-wave generators, but I quickly kicked that idea out the window. Next, I
began to have visions of PLLs, but I don't know anything about them, so that
horse was dead at the starting gate for sure. Eventually, I slapped myself
around the head to knock some sense into it and started from ground zero. First,
I redrew my waveforms to include the master clock, which seemed to drop out
naturally at six times the frequency of the phase clocks (
Figure
3).
After a few seconds, I realized that the obvious
solution was a classical synchronous state machine, so I immediately added the
binary values of the phase clocks to the bottom of the diagram. Furthermore, in
this case, the problem was crying out for a registered-output implementation, in
which the state-variable registers directly drive the outputs (
Figure
4) (Reference 1).
One reason that a registered output machine is so
attractive in this case is that the outputs from this type of machine all
transition simultaneously (or reasonably so), which usually doesn't happen if
you use combinational logic to generate the outputs by decoding the state
variables. Because there are six unique states, you need only three
state-variable registers to represent them using binary encoding. Assume that
you're using positive-edge-triggered, D-type flip-flops for your state
variables. Call the data inputs to these registers d1, d2, and d3, where these
inputs represent the machine's "next state." Also, call the outputs
from the registers p1, p2, and p3, where these outputs represent the machine's "current
state," and they also form the output clocks. (p1=Phase 1, p2=Phase 2, and
p3=Phase 3.) The next step is to draw a truth/state table for the combinational
logic and extract the Boolean equations (
Figure
5).
Because you use only six of the eight states that the three binary-encoded state variables can represent, you have to figure out what to do with the two unused states (the two bottom rows of the truth/state table in Figure 5). Because D-type flip-flops can power up containing random zeros and ones, your circuit could initialize in one of these unwanted states. Even worse, if you're careless, your machine could get hung up in a loop, cycling back and forth between these two states. One technique would be to use D-type flip-flops with clear inputs for state variables and then create a power-on reset circuit to initialize all the flip-flops to zero. However, to minimize the number of components and the complexity of the design as much as possible, you may want to use another alternative; which is to cause these states to jump into state 000 (Figure 5).
Argh! As soon as I'd extracted the Boolean equations, I
realized my mistake, which is that I hate trying to minimize Boolean equations.
On the one hand, I could have performed the minimization using a logic-synthesis
package, such as BOOL, which you can download from my Web pages for free (just
bounce over to http://ro.com/~bebopbb). On the other hand, throwing logic
synthesis at these piffling little equations seemed to be overkill, so I
promptly did the next best thing, which was to throw them all away. The next
line of attack was to use what we all learned at college in "Karnaugh Maps
101," which allows us to quickly and easily minimize and extract the
equations (
Figure
6).
A glance at these expressions tells you that certain
product terms appear more than once; that is, (p2 & p1) appears in the
equations for d3 and d2, and (~p3 & p1) appears in the equations for d2 and
d1. You can take the inverted inputs directly from the flip-flops' complementary
outputs, which means that you need not use any NOT gates. Thus, your penultimate
implementation of the combinational logic requires only four two-input AND gates
and three two-input OR gates (
Figure
7).
Why "penultimate"? Well, the maximum frequency that you can use to clock your state machine depends on the propagation delays through the feedback path formed by the combinational logic. Assuming minimalist CMOS implementations (but excluding weird pass-transistor configurations), each AND and OR gate requires six transistors and uses two internal levels of transistors, because AND and OR gates are formed by inverting the outputs of NAND and NOR gates, respectively. Thus, AND gates are slower than NAND gates, and OR gates are slower than NOR gates.
To make a long story even longer, all that remains is to perform a DeMorgan transformation on the OR gates driving the outputs and see what happens. (In this case, a DeMorgan transformation means that you swap the OR for a NAND and invert the inputs.) The end result is that the topology of the circuit stays as is, and the only thing that changes is that you replace all the slow AND and OR gates with fast NAND gates (Figure 7).
So, your final circuit requires three D-type flip-flops and seven two-input NAND gates. If I were implementing this circuit, I'd almost certainly use one of the smallest programmable devices that I could lay my hands on. However, you could also use a quad, D-type SN74xx175 flip-flop and two quad, two-input NAND SN74xx00 devices or components of that ilk.
And, there you have it, a swift 10 minutes with a cup of java and my trusty white board, and the problem was laid to rest. I'd managed to increase the sum total of happiness in the world, and I was free to get on with the rest of my life. All that remained was to triumphantly e-mail the solution back to its originator, which I promptly did with gusto and abandon and then awaited the response in dread anticipation.
Sad to relate, my joy was short-lived, because the following reply quickly came hurling my way over the Internet:
"Hmm, that's really very nice, but I actually meant to say 6° out of phase, not 60."
At this point, there was much gnashing of teeth and renting of garb in my office, let me tell you. Have you ever had one of those days?