AMAZON multi-meters discounts AMAZON oscilloscope discounts
And now, let's do some design. In this section we present several detailed examples of digital design, from the small, yet important, to the substantial project. The goals are two: to illustrate good design methodology and to introduce important design problems and their treatment. There is repetition of some aspects of design, particularly the use of ASM charts, yet each example has fresh material. We will indulge in some excursions into interesting topics as they occur in the context of design. We hope that in this way the concepts will be more meaningful to you than they would be as separate, isolated subjects.
Examples 1 and 2 illustrate some basic design issues related to human interaction with a digital device. In examples 3 and 4 we develop circuits to support the conversion of information from a serial bit stream to a sequence of bytes and vice versa, common operations in data communications (in Section 11 we use these circuits as a part of a larger microcomputer-based project). The traffic-light controller and combination lock examples, 5 and 6, provide more practice in design. In example 7, a Black Jack Dealer, we bring together several design problems and techniques (this example reappears in a different design mode in Section 10).
DESIGN EXAMPLE 1: A SINGLE PULSER
Our first illustration of design is the development of a circuit for handling a common situation involving a human operator of a machine. Most real systems involve humans, usually at switches, pushbuttons, and lights. Digital systems generally (but not always) run at speeds many thousands of times faster than human reactions. When a machine operator presses a button to initiate some action, the digital device must detect this signal and perform the appropriate steps. In the typical case, the machine completes the actions in a flash, and is back interrogating the pushbutton signal again long before the operator can release the button. We must develop a scheme so that the machine processes a particular button depression only once. A circuit for this is called a single pulser; it delivers a pulse only a single clock cycle long when a button is pressed.
If we have such a circuit, our digital machine may test the single-pulser output instead of dealing directly with the pushbutton signal and may thereby detect only one event as long as the button is down.
We will study this problem and its solution in several ways. First, we develop the most fundamental solution.
Algorithmic Solution of the Single Pulser
Statement of the problem. We have a debounced pushbutton, on (true) in the down position, off (false) in the up position. Devise a circuit to sense the depression of the button and assert an output signal for one clock pulse.
The system should not allow additional assertions of the output until after the operator has released the button.
Approach. We will develop an ASM solution to the problem. Since the problem is stated in terms of clock pulses, we know we are dealing with a synchronous system (for which we are grateful). Let us name the important inputs and outputs. Clearly, the position of the pushbutton is of great importance to the algorithm. The pushbutton signal can change at any time, independently of the state of the system clock, so the signal is asynchronous, and our name for it should have a terminal *: for instance, PB*. Call the output of the single pulser circuit PB.PULSE.
We know to be cautious about allowing asynchronous test inputs to creep into our ASM charts. To avoid testing PB*, we should synchronize the signal using a clocked D flip-flop. This flip-flop, with input PB* and output PB.SYNC, becomes part of the architecture of our solution.
Control algorithm. Now we may write an ASM chart to describe the algorithm. The algorithm will test PB.SYNC and produce an output PB.PULSE. The algorithm has two states: one for detecting the first moment that PB.SYNC becomes true (button goes down), and the other to wait until PB.SYNC becomes false (button goes up). FIG. 1 is the ASM.
Implementing the design. The equation for the output PB.PULSE is PB.PULSE = FIND·PB.SYNC
FIG. 1 A single-pulser ASM.
Once we have a way of producing the variable FIND, our problem is solved.
To obtain the value of FIND, we must implement a state generator for our ASM. We will use the multiplexer method of state generation. The two-state ASM will require one flip-flop to record the state, and one two-input multiplexer to develop the next-state input to the flip-flop. In systems with more states, the state flip-flops hold an encoding of the current state and, in order to obtain logic variables for each individual state, we must decode the state code. However, in our present design, the output of one flip-flop has two distinct states, and this is sufficient to produce signals for the two states WAIT and FIND directly, without decoding.
Look at FIG. 1. Formally, the flip-flop output is a state variable A, A o representing the FIND state and A = 1 the WAIT state. Thus:
WAIT = A
FIND = A
So we may just call the flip-flop output WAIT, and then we have
FIND = WAIT
What are the two inputs to the next-state multiplexer? If the system is in state 0 (FIND), the condition for a true input to the flip-flop is the same as for moving next into state 1, namely, PE.SYNC. If the present state is 1 (WAIT), a true flip-flop input for the next state again requires that the next state be 1.
The condition from the ASM chart is again PE.SYNC. Here is a multiplexer whose inputs are all the same! We can eliminate the mux from the state generator and run the signal PE.SYNC directly into the flip-flop input. Now, our complete circuit consists of the synchronizing flip-flop PE.SYNC, the state flip-flop WAIT, and the logic to form PE.PULSE. FIG. 2 is the single-pulser circuit.
FIG. 2 A single-pulser circuit.
A Combined Architecture-Algorithm Solution
Although the foregoing derivation is our most fundamental solution of the single pulser problem, there is another approach that illustrates an important connection between the architecture and the algorithm in digital design. Suppose we reason as follows. Our architecture consists of a synchronizing flip-flop for PB*, with output PB.SYNC, and another D flip-flop whose function is to delay the PB.SYNC signal by one clock time. The second flip-flop has input PB.SYNC and output PB.DELAYED. Then our single-pulser output signal PB.PULSE should be true only when PB.SYNC is true and PB.DELAYED is still false. As soon as PB.DELAYED becomes true, we must stop asserting PB.PULSE. Can we formalize these thoughts with an ASM? Of course; FIG. 3 is a one-state solution. This ASM requires no flip-flops for state generation, since there is only one state.
The equation for PB.PULSE is PB.PULSE = PB.SYNC·PB.DELAYED
The implementation looks identical to our original circuit in FIG. 2 except for a trivial change in the names in the interior of the circuit.
FIG. 3 A single-pulser ASM in one state.
Implications. This is an interesting phenomenon. We first had a two state system with minimal architecture (one flip-flop), and now we have a one-state system with more inputs and more architecture (two flip-flops). Both solutions yield the same hardware.
This reflects an important concept in digital design. The distinction between architecture and algorithm is arbitrary. In general, by enlarging the architecture, we may convert any ASM into one with fewer but more complex states. At the limit, it is always possible to describe any algorithm in a single state. For complex systems, this yields such a messy ASM that it is not useful; nevertheless, it is technically correct. The vital point is that architectures and ASMs are tools to assist us to understand our problem and to produce a clear, correct implementation.
The tools are to serve us, not control us! Whereas we prefer the first solution to our example as more fundamental, there is merit in the second solution also. Both result in equivalent (in this case, identical) hardware.
A Single-PulserBuilding Block
Having developed a circuit for producing a single pulse from a long input signal, we may package the circuit in a black box and treat it as one of our design building blocks. The single-pulser black box has an input PB* from an asynchronous source, and produces a one-clock-cycle true output PB.PULSE when the input becomes true. Whenever we need this type of behavior, we may mentally plug in our black box, and when we build our circuit, we use hardware similar to FIG. 2 in the box. It would be nice if the single-pulser box were available in a single chip, but it is not. However, we still treat the single-pulser operation as a building block in our work.
Generalizing the Single Pulser
Think about the human-machine interaction implied by our single-pulser problem.
When the operator presses the button, the single pulse promptly appears (and disappears). The machine must have been ready to act on the pulse signal. How did the operator know when it was okay to press the button? Somehow, the operator must infer the correct time from the condition of the machine. Usually this would mean a light or some combination of lights on the control panel. The circuit controls these lights, indicating its readiness to process a button depression.
The single pulser works well in this common situation.
Now suppose we treat the operator-machine interaction differently. Let the operator press a button at will but require the operator to hold the button down until there is some indication that the machine has received the signal.
Then the machine may be in any state when the button is depressed, and only when the circuit is ready to respond to the button will the light come on.
The single pulser will not work in this case, but we can handle the situation with an ASM structure that looks for the pushbutton depression, then lights the light until the operator releases the button, and then performs the desired operation.
FIG. 4 is a typical form of this ASM. (In Design Example 7 in this section, we discuss an additional variation of the single-pulser algorithm.)
FIG. 4 Diagram of an ASM if the operator may press a pushbutton at any
time. In this algorithm, the ma chine waits until the operator releases the
button before it responds to the pushbutton.
DESIGN EXAMPLE 2: A SYSTEM CLOCK
The clock is the master pacer in digital systems, and we must design it carefully.
A good clock is perhaps the most potent debugging tool a designer can put into a system. At the least, the clock must have an automatic mode whose frequency may be fixed at some high value and a manual mode that generates one hazard free active clock edge when a pushbutton is depressed. To do this, there must be a mode switch to select automatic or manual status. Throwing the mode switch must not shorten a clock cycle in the automatic mode. If the mode switch were flipped 10 percent of the way into a clock cycle, thereby truncating the cycle at that point, our circuit could suffer from timing problems. We must let the last cycle run its normal course before the clock system enters the manual mode.
Our approach to design requires that we move difficult, universal concepts up front so that we can solve them once and then apply them to all projects.
The system clock is an important concept, so let's design a circuit for it.
Statement of the Problem
(a) Design a hazard-free system clock that runs in two modes, automatic and manual. The automatic mode is a fixed-frequency mode derived from a continuously running clock or oscillator. (Section 12 shows ways of fabricating clock signals from oscillators.) The manual mode should produce a true clock output when a pushbutton is depressed, and a false output otherwise.
(b) Activating the mode switch must never cause truncation of a clock cycle.
(c) In the automatic mode, the clock circuit should ignore the manual pushbutton.
Digesting the Problem
There are two inputs, from a debounced mode switch and from a debounced pushbutton. We may formalize the variables in the problem. Let the mode switch output be MAN, and let MAN = T in the manual mode and MAN = F in the automatic mode. Let the manual pushbutton's output be PB, and let PB = T when the button is down and PB = F when the button is up. Let the clock output be eLK. Since we are dealing with a clock for synchronous edge triggered systems, it is natural to let eLK = T be the high voltage level and eLK = F be the low voltage level, although this choice is not essential to the design.
In digesting the problem, we uncover a crucial point: the clock output must be free of hazards. In Section 4, you learned about the catastrophes that will occur when clocks deliver spurious edges. The most general way to avoid hazards is to avoid gates on the lines that must be hazard-free. How can we build something without gates? Commercial flip-flops are designed to have hazard free outputs, and using a flip-flop output is the most convenient way to avoid gates. We will produce the clock output eLK directly from a flip-flop.
Now we are ready to derive an ASM chart for our system clock circuit.
Algorithm for the System Clock
Our system is a synchronous circuit clocked by a continuously running oscillator that will drive the system clock ASM. The output eLK has two levels, T and F, so we might use two ASM states, one for eLK = T and the other for eLK = F. In the automatic mode, we would expect to flip back and forth between the states constantly. Our design problem is to fit the manual-mode operations into this framework. FIG. 5 is the ASM chart.
This ASM ignores the pushbutton unless the mode switch is in the manual mode. In the automatic mode, the active state alternates between LO and HI, producing a eLK output of half the ASM clock frequency, as shown in the following timing diagram:
In the manual mode, the ASM moves to whichever state reflects the PB position.
FIG. 5 An ASM of a system clock.
The ASM formulation clearly demonstrates that the automatic mode overrides the pushbutton and that, whenever we switch from the automatic to the manual mode, the last automatic clock phase exists for its full duration, without any shortening.
But the inputs MAN and PB in the ASM are asynchronous to the ASM clock. In Section 5, you were told to avoid such signals in the ASM, since they introduce many dangers, and even when they are not dangerous, it is usually difficult to establish that their use is safe. Must we synchronize these signals to protect our ASM from harm? In this case, we can quickly demonstrate that we do not need to. FIG. 5 is a two-state ASM with no conditional outputs.
The machine is always either in one state or in the other. When the mode switch is changed from automatic to manual, the ASM either detects the change during the present ASM state, or it doesn't. If it does, at the next state transition it moves into the manual mode; if the ASM misses the change, it remains in the automatic mode for one more clock cycle before entering manual mode. In either event, in this simple ASM there is nothing to go wrong as a result of the asynchronous nature of the MAN signal. A similar argument applies to PB. Implementing the Circuit
Let's use the multiplexer controller method for implementing the state generator.
One flip-flop will encode the two states in our ASM. The purpose of the design is to produce the system clock output eLK. We have already decided to produce the system clock signal eLK as the output of a flip-flop. According to the ASM, eLK is true in state HI and false in state LO. In FIG. 5, we chose to represent LO by 0 and HI by 1. This is the same behavior as the eLK output: false in LO and true in HI. In this case, we get our desired eLK output from the same flip-flop used in the state generator. Very convenient.
For the state generator, we set up a table of next-state conditions:
Both voltage signal forms will be available for the debounced switch and pushbutton variables. In FIG. 6, we show a multiplexer controller for our clock machine.
This completes our solution to the design problem.
FIG. 6 A circuit for a system clock.
Critique
All three individual gates in FIG. 6 come from a single 74LSOO Quad Two Input Nand Gate chip, since a spare Nand gate will implement the voltage inversion conveniently. Our solution costs one chip for gates, one chip for the two-input multiplexer, and one chip for the flip-flop. To be sure, there are unused components in these packages, but for a fundamental module such as a system clock you probably don't want to share the chips with other parts of the system.
In the unshared mode, the cost is three chips; sharing with other circuits, the
cost is i + i + ! = H chips.
Advantages of using the mux controller are its simplicity of construction (synthesis) and its ability to display the original ASM structure in the circuit (analysis). The mux method seldom takes more chips than alternative solutions.
In this simple case, using a JK flip-flop for the state generator can yield a solution requiring one flip-flop and two OR gates-a cost of two unshared chips or one shared chip. We have not taught you this JK method because it results in obscure circuits that bear little detectable relation to the original design and because any change in the design requires a complete recalculation of the entire state generator.
Also, in most complex designs, the JK method and the multiplexer method require comparable numbers of components.
The statement of the problem was the key step in its solution. Once we phrased the problem properly, the ASM chart followed naturally. In turn, the hardware followed easily from the ASM chart. The smoothness of the process is gratifying and is a sign that we are doing things right.
The original goal seemed deceptively simple. Our natural urge, and probably yours also, was to rush to the lab bench and try a few circuits. Almost surely we would have wound up with a circuit that appeared to work but contained undetected hazards. In earlier days, we tried various bottom-up approaches.
This top-down circuit looks very different from our bottom-up designs, and it is unlikely that we would have stumbled onto it by random experimentation.
Now we stay out of the lab until we have mastered the problem!
DESIGN EXAMPLE 3: A SERIAL BIT CLOCK
For our third example of digital design, let's look at a different type of clock.
In the transmission of serial data, bits arrive at the receiving station one at a time on a single signal line, at some nominal rate. Typical rates are 1200, 9600, and 19,200 bits per second. The data transmitter uses a clock of the appropriate frequency to regulate the serial transmission of the data bits. The receiver, a completely separate device, has no knowledge of the transmitter clock other than the agreed-upon nominal bit rate.
The receiver picks off the incoming data bits by sampling the serial data line at points about midway into the interval for each data bit. Sampling at the midpoint avoids the problem of sampling while the data stream is undergoing a transition. To accomplish this midpoint sampling, the receiver needs a clock that delivers its active edge in the middle of each data-bit interval. FIG. 7 shows a typical bit stream and the required waveform of the receiver's bit clock.
FIG. 7 Deriving a receiver bit clock from the data stream.
Approaching the Problem
Our design problem is to produce a clock signal for use by a serial data receiver.
How can we create a clock for such a bit stream? What information do we have?
(a) We know the nominal bit rate.
(b) We can sense the incoming bits as voltage levels on the input line.
Item (a) tells us the basic frequency of the bit clock but not exactly when the clock edges should occur. Item (b) tells us where bit boundaries are by the voltage transitions on the input.
We will develop an ASM that will sample the incoming stream of bits often enough so that we will not miss any action. It will be simplest if the ASM samples the bits at a rate that is some multiple of the nominal bit rate. We choose a speed for our ASM that is 16 times the stated bit rate; call this ASM clock signal X16CLK. The sole output of our circuit will be a receiver bit clock signal BIT. CLOCK. Every time we detect a change in voltage level on the serial input, we will reset the bit clock to its false (inactive) level. After eight ASM clock cycles, we will change BIT. CLOCK to its true (active) level. At that point we have created a F --> T edge on BIT.CLOCK that a data receiver can use to sample a data bit.
If, in the absence of a transition in the input data stream, we execute 16 ASM clock cycles after resetting the bit clock, we must again reset BIT. CLOCK to false, completing a bit-clock cycle. We use each transition of the input bit stream to create an inactive clock edge, and then after half a bit time, we create the active bit clock edge. If there is not another bit transition, then after a whole bit time elapses, we reset the bit clock and begin again.
There is one hitch: Whenever a string of 0's or a string of 1's arrives, the data stream will contain no transitions. In this case, there is no information in the input data stream to keep our bit clock aligned with the transmitted bit boundaries. Our method (and any method) will work only if the nominal bit clock frequencies of the transmitter and receiver are similar, so that the active edges of the generated receiver bit clock do not wander far from the center of each incoming bit. Designers of data-transmission systems are aware of this problem and usually avoid it by making sure that their message protocol produces some change in the values of the data at frequent intervals. Therefore, we will not worry further about this problem.
The Initial Architecture
In line with our general practices, we do not test the incoming stream of bits directly, since it changes asynchronously to our ASM clock. We will place a synchronizing D flip-flop into our architecture, with input DATA* and output DATA.SYNC. The output of the bit clock circuit will be used as a clock by other systems, so we must be sure that the output is free of hazards. Therefore, we use a flip-flop to produce the output BIT. CLOCK. Since we must exert control over the value of BIT. CLOCK at several points in our algorithm, we will use a controlled (JK) flip-flop.
The Control Algorithm
At this point, the designer has a choice. We can create a 16-state ASM chart, or we can develop a one-state ASM that manipulates a 16-count counter in the architecture. We choose the latter, because we must always be on the lookout for a transition in the incoming data stream and putting such a test into each state of a 16-state ASM would require rather tiresome drafting. So we add a 4 bit binary counter to our architecture.
We know we are looking for transitions in the input data. How do we detect a transition? This requires a knowledge of the present value of DATA.SYNC and of its value during the ASM's previous state. To save the old value, we will need a D flip-flop with the input DATA.SYNC and the output OLD.DATA. Now, how do we tell if DATA.SYNC and OLD.DATA are different? The EX CLUSIVE OR logical operator is ideal for this. The function EOR is true if and only if its two inputs are different. Thus the condition required for a transition on the input data line is
DATA.SYNC EB OLD.DATA
Now we may write our ASM to embody the analysis in the preceding paragraphs. FIG. 8 is the one-state ASM for the receiver bit clock. Before implementing this ASM, however, we should ask a question. We should be suspicious of a clock circuit that has two different ways of creating one of the clock edges. Can the BIT.CLOCK output have any undesirable short clock phases? In the ASM, a data transition will preempt all other events. What if a data transition occurs when the ASM count is at 14 or 15, at 0 or I?
FIG. 8 An ASM for a serial bit clock.
Transitions at 14 are okay, since BIT.CLOCK has been true since the 7 count. A transition at 14 makes the T --> F edge come slightly early, but that is necessary to keep BIT.CLOCK synchronized with the incoming bit stream.
It is for exactly this purpose that we selected an ASM clock with a considerably faster frequency than the bit frequency, so that early or late bit transitions will still result in rather even clock intervals. A transition at 15 is fine and is the most probable case since it means that the bit transitions and the ASM count are synchronized. Transitions at 0 or 1 will cause BIT. CLOCK to be set to false, whereas BIT. CLOCK underwent a T -? F move just one or two ASM cycles earlier. Again, this is okay, because clearing an already-cleared flip-flop causes no change in the output. The inactive phase of BIT.CLOCK will last a little longer than usual but, again, this is proper to maintain synchronization.
If transitions occur at intermediate counts far from the normal time, then there is trouble in the input data stream and all we can do is try to follow the input data, which the ASM will surely do. Noise on the line-"glitches" -will cause problems. Our assumption about this circuit must therefore be that the data stream is free of noise. There are more sophisticated techniques involving phase-locked loops that help alleviate the problem of noisy lines, but these methods are beyond the scope of this book. The technique proposed in this example is quite acceptable for data transmission at moderate speeds over clean lines.
Implementing the ASM
Since we have a one-state machine, we need no state generator. Most of the detail is in the architecture. The 4-bit binary counter performs several operations: clearing to zero, counting, and testing for counts of 7 and 15. A fine choice for our counter building block is the 74LS163 Four-Bit Programmable Binary Counter, which has synchronous clear, count, and load inputs, and a "terminal count" status output to report a count of 15. With this knowledge, we may write the equations for the ASM outputs. Define an auxiliary variable DATA. TRANS as follows:
Then:
To complete the specification of the logic equations, we need expressions for (COUNT= IS) and (COUNT = 7). The terminal count output COUNT(TC) of the 74LS163 gives us the former term directly; we will build the (COUNT= 7) term with gates. Calling the data outputs of the counter C3 through CO, with C3 being the most significant bit, we have
Look at the equation BIT.CLK(SET). Our intuition tells us that if the count is 7, then it certainly is not 15, and so we should be able to toss out the term (COUNT=15) from the equation. We may confirm our intuition by expanding the meaning of the two terms
In the second step we use De Morgan's Law [Eq. (1-6)], and in the third Eq. (1-5), A-A = F.
Now we may draft circuit diagrams. Figures 9 and 10 show the architecture and the control signals. We have assumed that on the data line T = H, although the choice does not affect the result.
Now we have a serial bit clock. In the next example, we will use this clock in a circuit for a data receiver that converts a serial stream of bits into a sequence of bytes.
FIG. 9 The architecture of a serial bit clock.
FIG. 10 Control signals for a serial bit clock.
DESIGN EXAMPLE 4: SERIAL-PARALLEL DATA CONVERSIONS
Serial data transmission is a practical and economical way to move information between distant points. Each bit moves in serial fashion over a single signal path, according to some agreed-upon protocol. This method is conservative of signal wires but slower than if more bits were transmitted in parallel. Within a computer system, serial bit transfers are inefficient, since the basic unit of manipulation is the byte or word; within computers, data is transferred in parallel.
To accommodate these different modes of moving data, we need the ability to convert serial data into parallel form and parallel data into serial form.
In this example, we design circuits for serial-parallel conversions. (We will use the designs in Section 11 to support a more complex microcomputer-based data multiplexing scheme.) Our example has two independent circuits: a serial to-parallel converter and a parallel-to-serial converter. Both converters deal with 9-bit parallel bytes, an unusual byte size dictated by the structure of the hardware at the other end of our serial data lines. (LSI chips are available to assist the serial-parallel conversions of the more common byte sizes, such as 8 bits. You will see an example in Section 9. For this 9-bit application, no LSI chip is available.)
Specifying the Problem
Parallel-to-serial conversion. The parallel-to-serial (P --> S) converter accepts 9-bit bytes from some source (in Section 11, this source will be a microcomputer) and transmits the bits serially on a serial-out line (SO) at a specified bit rate. As long as the system is running, the serial bit rate is constant, and the P --> S process never stops. In our example, we may use a rate of 9600 bits per second.
The need to maintain a valid serial stream of data at this fixed rate places a severe constraint on the device that supplies the 9-bit bytes: whenever the P --> S converter needs a new byte, the new byte must be present. But the byte supplier is running at its own speed, engaged in its own duties, only one of which is to supply bytes to the P --> S converter. A simple way to handle such a situation is to provide a one-byte buffer register in the converter to hold the incoming byte whenever the sending device supplies it. Then our converter can move the data to another spot when it is ready to process the byte, thus freeing the buffer to hold another byte.
(The term buffer has two meanings in digital design. Previously in this book, the word has meant a source of power for a logic signal. Here, we use the term in the software sense of a temporary storage area to accommodate differences in the operating characteristics of a source and a destination.) We need some way to notify the supplier of bytes when it is time to fill the converter's buffer with a new byte. The byte supplier must not provide a new byte too soon, lest the new byte destroy the previous byte in the buffer before the P --> S converter has processed it. On the other hand, a basic presumption of this system is that the byte supplier must not fail to supply a byte on time; otherwise, we cannot supply the continuous stream of bits required by the serial-out line. We may use a simple one-way signal to tell the byte supplier to fill up the buffer. No response from the byte supplier (other than filling the buffer!) is necessary, since we cannot tolerate any slippage and our converter could do nothing about a failure if one occurred. Let's use a variable FILLIT as a signal to the byte supplier; whenever the converter accepts a new byte from its buffer, the converter will toggle (complement) FILLIT. At a time safely before the converter needs the next byte, the byte supplier must sense this change in FILLIT, and provide a new byte into the buffer. FILLIT behaves like a modulo-2 counter.
Serial-to-parallel conversion. The serial-to-parallel (S --> P) converter captures the bits arriving serially on the serial-in line (S1), accumulates 9 bits into a byte, and places the 9-bit byte into a buffer register. An external byte receiver (again, in Section 11, the microcomputer) will accept the bytes for further processing. We insist that the byte receiver keep up with the incoming stream of bytes. The receiver must accept the buffer data before the converter puts the next byte into the buffer. In analogy with the P --> S case, the S --> P converter can toggle a variable READIT to announce to the byte receiver that a new byte is available. Since the byte receiver is committed to keep up, it need not reply to the READIT signal, except to empty the buffer.
There are two complications in serial-to-parallel conversion:
(a) How do we find the serial bits in the incoming voltage waveform on the serial-in line?
(b) How do we locate byte boundaries among the stream of bits? The devices at the two ends of the serial line will be set to an agreed-on nominal rate of incoming serial bits; in our example it is 9600 bits per second. With this information, we may use the serial bit clock produced in Design Example 3 to signal the S --> P converter when to accept a bit.
Locating byte boundaries requires that the incoming serial bit stream have some special characteristic that our system can recognize. In our protocol, we assume that a special 9-bit pattern, SYNC, will periodically arrive in the serial input stream. Our S --> P converter must detect this SYNC pattern and use it to establish the byte boundaries. We will defer to the byte receiver the decision as to when to seek out this SYNC pattern. With this division of responsibilities, we can add an input signal RESET to the S --> P converter. Whenever the byte receiver asserts this signal, the S --> P converter will suspend normal byte transfers until it locates a SYNC pattern among the incoming bits, at which time it will resume placing bytes into the byte buffer and toggling READIT.
Building the P --> S Converter
Design. The architecture will have a 9-bit buffer register to hold a byte from the byte supplier, and a 9-bit shift register to hold a byte while it is being disassembled and shipped out bit by bit over the serial-out line. Also, there will be a controlled flip-flop FILLIT to tell the byte supplier when to deliver another byte.
The basic timing element for parallel-to-serial conversion is the serial bit time, so a clock operating at the P --> S bit rate (9600 Hz) is a natural system clock for our synchronous design. (To assist in debugging, we would probably use the system clock of Design Example 2, which has both automatic and manual modes; the automatic clock frequency would be fixed at 9600 Hz.) There are two approaches to the design of the control algorithm. We could draw a nine-state ASM chart that produces a serial bit for SO in each state.
This ASM could load a byte from the buffer into the shift register in one state and shift the byte one position to the right in each of the other eight states.
Alternatively, we can view the ASM as having a single state, with the architecture containing a binary counter capable of counting from 0 through 8, to distinguish the nine activities per byte. Let's adopt this latter view and add a counter to our architecture. The ASM in FIG. 11 is then self-explaining; Fig. 12 shows the supporting architecture.
FIG. 11 An ASM for parallel-to-serial conversion,
FIG. 12 The logical structure of a parallel-to-serial converter.
Implementation. The ASM yields the following equations for the P --> S control outputs:
Realizing the P --> S converter is straightforward. Here are some hints for selecting the chips. Nine-bit registers are not available in standard MSI, so we must form them from other units. We may make the byte buffer in several ways, perhaps with two 74LS378 Hex Enabled D-Register chips; the buffer register will be clocked and loaded by the byte supplier. There are also several ways to fabricate the 9-bit shift register. For this parallel-to-serial conversion, we need a parallel-in serial-out register. Although not quite the most economical in chip count, two 74LS165 Parallel-Load Eight-Bit Shift Register chips form an easily understood arrangement. In addition to the loading and shifting controls and the 8 data inputs, these chips have a serial input into the most significant data bit and a serial output from the least significant bit. This allows for the cascading of units to form longer registers. (As usual, you should consult a TTL data book for the exact specifications.) The output from bit 0 (the least significant bit) is the serial data signal used to produce SO from the P --> S converter.
FILLIT can be a 74LSI09 Dual JK Flip-Flop. Our faithful 74LS163 Four Bit Programmable Binary Counter can be the counter required by the ASM. With the 74LS163 counter, we note that the (COUNT~8) variable is just the most significant bit of the counter output; the "counter compare" box in Fig. 12 is therefore trivial.
Building the S --> P Converter
Design. The architecture requires a 9-bit shift register to accumulate a byte from the serial-in line, and a 9-bit buffer register to hold a byte for the byte receiver. The signal READIT will require a flip-flop with its output available to the byte receiver. At this stage, it is not clear if the incoming RESET signal line from the byte receiver also requires a flip-flop.
The S --> P architecture has a "SYNC byte identifier" black box that constantly compares the 9-bit pattern currently in the shift register with the fixed SYNC pattern and produces a true output only when the patterns match.
Timing of the serial-to-parallel conversion is provided by the serial bit clock in Design Example 3, which produces a clock signal that is synchronized with the incoming bit stream.
Our ASM will have two states: RUN, for the normal serial-to-parallel byte assembly analogous to the P --> S ASM; and START, for locating the SYNC pattern in response to a RESET signal from the byte receiver. The RESET signal arrives as an asynchronous signal from the byte receiver; it signals a precipitous retreat from normal operations. As the S --> P converter ASM in FIG. 13 shows, we enter the START state as soon as we receive a RESET signal; we remain (synchronously) in START until SYNC appears. Once the algorithm locates the SYNC pattern, we move to RUN for regular accumulations and transfers of bytes.
FIG. 13 An ASM for serial-to-parallel conversion.
To help protect the asynchronous RESET* signal from noise, we will capture the byte receiver's RESET signal in a flip-flop, and use the flip-flop output as the S --> P converter's RESET* signal. The RESET signal will cause an immediate transition to the START state, where the S --> P system will remain until after the receiver has transmitted RESET to clear the flip-flop. The architecture of the S --> P converter is shown in FIG. 14.
Implementation. Once in state RUN, the ASM remains there until a reset signal causes a precipitous transfer to state START. The state generator for this two-state machine is a JK flip-flop with output R UN. The reset signal must perform a direct (asynchronous) clear function on the flip-flop, and is thus labeled RESET*. In FIG. 13, we have labeled each conditional output oval. These labels are not state names, but just represent positions within the parent state. For the conditional output term CD in state START, we will create a logic variable START.]; similarly, the notations CD and @ in state RUN will result in variables R UN.] and R UN.2. Conditional output labels are excellent aids in the systematic implementation of complex ASM charts.
From the S --> P ASM chart in FIG. 13, we derive the following equations:
FIG. 14 The logical structure of a serial-to-parallel converter.
Here are some suggestions for chips to implement the S --> P converter.
The 9-bit buffer register may be two 74LS378 Hex Enabled D-Register chips.
The shift register is a serial-in, parallel-out variety; two 74LSI64 Eight-Bit Parallel~ Out Serial Shift Register chips would serve. The counter may be the 74LS163 Four-Bit Programmable Binary Counter, and once again the determination of (COUNT;38) for this device is trivial, just as it was in the similar P --> S circuit.
The flip-flop for READIT should be a 74LS109 JK Flip-Flop.
The SYNC byte detector must produce truth whenever the current 9-bit data pattern matches the fixed SYNC pattern. In Section 3, we showed how to compare a fixed quantity with a variable one. For this circuit, we need a 9 bit AND function; a 74LS133 Thirteen-Input Nand Gate would do the job. Note that although the SYNC byte detector constantly checks for the SYNC pattern, the result is used only when the ASM is in the START state.
Critique
This completes our design of serial-to-parallel and parallel-to-serial converters.
We have left unspecified the detailed nature of the devices on the serial and the parallel ends of our converters. (In Section 11, we will incorporate the converter circuits into their larger environment.) Our protocol is a rather strange one, with its 9-bit byte. For the more ordinary 8-bit conversions, available complex LSI chips perform many of the same activities as our circuits. When appropriate, we would use these single chip solutions in preference to building a multiple-chip MSI circuit. In this case, the available LSI chips were not suitable, and the exercise gives you an understanding of serial-parallel conversion.
DESIGN EXAMPLE 5: A TRAFFIC-LIGHT CONTROLLER
This example was inspired by a similar problem in Carver Mead and Lynn Conway's pioneering book, Introduction to VLSI Systems. We will solve the problem with our structured design techniques.
Statement of the Problem
A busy highway is intersected by a little-used farm road, as shown in Fig. 15. The farm road contains sensors that cause the signal CARS to go true when one or more cars are on the farm road at the positions labeled 'C.' We wish to control the traffic signals at the intersection so that, in the absence of cars waiting on the farm road, the highway light will be green. If a car activates the sensor at either position C, we wish the highway light to cycle through yellow to red and the farm-road light then to turn green. The farm-road light is to remain green only while the sensors indicate the presence of one or more cars, but never longer than some fraction of a minute, after which it is to cycle through yellow to red and the highway light is to turn green. The highway signal is not to be interrupted again for farm-road traffic until some fraction of a minute has elapsed.
FIG. 15 The location of the traffic signal and the sensors in Design Example
5.
Preliminary Considerations
The highway traffic is given priority, but not to the extent that the farm-road traffic can be stalled indefinitely. Since the default condition is a green light on the highway, we do not need any sensors in the highway lanes. To keep the example uncluttered, we will assume that the outputs of the sensors are combined external to our design to produce the single signal CARS, and that this signal satisfactorily indicates the presence of cars desiring to enter or cross the highway.
We might ask what signals the traffic lights must receive to activate their three colors, but we defer such inquiries because we would like our solution to be independent of any particular brand of traffic signal until we are ready to specify one.
The control of the traffic signals involves four intervals: the minimum time the highway light will be green, the maximum time the farm-road light will be green, the duration of the highway's yellow signal, and the duration of the farm road's yellow signal. For simplicity, we assume that the first two intervals are the same and that both yellow-light intervals are the same. To generate signals representing these two intervals, we plan to have a timer, driven by a (high speed) master clock and initiated by a starting signal START. TIMER. Whenever the timer is started, two output signals, THOLD and TYEL, are negated. If the timer is not interrupted, the two signals will be asserted after their respective intervals have elapsed; the signals will remain asserted until the timer is restarted with START. TIMER. The same timing unit and the same enabling signal will suffice for both timings, since the two intervals do not overlap.
Our preliminary architecture is shown in FIG. 16.
The Control Algorithm
The control of the traffic signals breaks naturally into four events, which will result in four ASM states:
State HG: Highway light green (and farm-road light red).
FIG. 16 The preliminary architecture of the traffic-light controller.
State HY: Highway light yellow (and farm-road light red).
State FG: Farm-road light green (and highway light red).
State FY: Farm-road light yellow (and highway light red).
When the highway light is green (state HG), the controller must be alert for farm-road traffic, and, if cars are on the farm road and sufficient time has elapsed, must cycle the lights through state HY to state FG. In state FG, when the farm road light is green, the controller must be prepared to cycle through state FY to state HG whenever no cars remain on the farm road or if the stipulated time has elapsed. These observations lead quickly to the A5M in FIG. 17. Each state tests one of the two intervals THOLD or TYEL, and so, as we enter each state, we must start the timer unit.
In state HG, the ASM describes the mutual requirement of farm-road cars and it sufficiently long interval, using a single test of the product of THOLD and CARS. In state FG, the ASM uses separate tests of THOLD and CARS to describe the logic resulting in the escape to the next state. These constructions seem natural to us, so we used them. Other ways of representing the test conditions will lead to exactly the same output equations and state generator; for instance, follow the synthesis below, and then repeat the synthesis with these tests:
FIG. 17 The ASM for the traffic light controller.
Realizing the ASM
From the ASM chart, we derive equations for the outputs and we tabulate information that will lead to the construction of a state generator. The natural parameters to describe the condition of a traffic signal are, of course, the colors of the signal. We derive
HL.GRN = HG
HL.YEL = HY
HL.RED = FG + FY
The signal for starting the timer unit is:
START.TIMER = FL.GRN = FG FL.YEL = FY FL.RED = HG + HY
HG·THOLD·CARS + HY·TYEL + FG·(THOLD + CARS) + FY·TYEL
Let's use the multiplexer method to implement the state generator. In this method, we assume an encoded state generator, which will require two D flip flops. The encoding is arbitrary: we use B and A as the state variables, and the following assignment:
State
For such a simple ASM, we could write down the state generator by· inspection. Nevertheless, in almost every design we find it useful to tabulate the conditions for changes in state. Table 1 shows the next-state conditions for our traffic light controller. FIG. 18 shows the state generator.
Table 1 CONDITIONS FOR STATE TRANSITIONS IN THE TRAFFIC-LIGHT CONTROLLER
FIG. 18 A multiplexer state generator for the traffic-light controller.
Choosing a Particular Traffic Signal
The ASM's outputs that are to control the traffic signals are expressed in terms of the active color of the lights. Now suppose we select a particular traffic signal and, reading the instructions, find that each signal is controlled by a 2-bit code that specifies which of the three colors is active. In FIG. 19 we show this particular choice of a traffic light, adopting T = H for the code. Now we may derive logic equations that express the bits of the manufacturer's code in terms of our traffic-light variables:
HLl = HL.YEL HLO = HL.RED FLl = FL.YEL FLO = HL.RED
Now that the behavior of the particular traffic signal has been expressed in our nomenclature, there remains only to plug in the particular expressions for each light's colors to complete the implementation. Using the ASM output equations,
we get: HLl = HY HLO = FG + FY FLl = FY FLO = HG+HY
Our refusal to commit ourselves to a particular traffic signal left us with an incomplete early statement of the architecture in FIG. 16 but allowed us to form a solution independent of the brand. When we finally settled on a brand, in FIG. 19, we completed the solution without altering our original work. This is an important technique, and represents good top-down design.
FIG. 19 A particular traffic light for Design Example 5.
DESIGN EXAMPLE 6: A SIMPLE COMBINATION LOCK
Now let's use our design tools to build an electronic combination lock. Combination locks come in two varieties, parallel and serial. An example of a parallel lock is a bicycle-chain lock with four disks that we must rotate to the correct combination.
We can change each disk independently without having to start over if we have a wrong number. A serial lock is the common dial type: we rotate a single dial to three or more preset numbers in sequence. Any wrong number requires us to start over.
There are electronic equivalents of most components of locks. Rotary 10 position switches replace the disks and dial. These switches are available as side-by-side stackable units called thumbwheel switches, which look like the individual disks of a parallel bicycle lock. As we rotate a thumbwheel switch, numbers from 0 through 9 appear in a small window and appropriate contacts close on four lines to represent the decimal number in binary form. We can use a pushbutton switch to replace the manual pull test of a correct lock combination.
We can then use a lamp driver to light a lamp if the try was successful. (In Section 12, we show how to take a low-power logic signal such as the lamp input and amplify it to do useful work, for example to drive the lamp or to provide power to a solenoid to pull the latch on a door.) Let's build a simple lock to explore the design principles. Since we are digital designers, we will enter the lock's combination in binary form, one digit at a time. In this way we can build up the combination a bit at a time, starting from either end. A wrong digit should abort the entire procedure and send us to an error state, where the system waits for a reset signal to send it back to the start.
Stating the Problem
Build a 3-bit serial combination lock that lights a light when the correct combination is entered.
Digesting the Problem
We should have several questions. For instance:
(a) How is the data entered? (b) What is the combination? (c) How do we reset the lock to start a new sequence? (d) How do we enter the combination-left to right or right to left? (e) How do we know when we have made an error? We might answer these questions in the following way: (a) Binary data (0 or 1) is set on a toggle switch. The operator will signal that the switch data is ready to enter by pressing a pushbutton switch Read.
(b) Assume that the combination is 0112 •
(c) We will need a Reset switch of some sort.
(d) Right to left.
(e) We can do clever things with the error condition. The worst thing would be to light a Wrong light the first time the machine detected a bad digit.
This would allow a thief to build up the correct combination a digit at a time by writing down the preceding correct string of bits and experimenting with the current bit. The best procedure is to wait until all 3 bits are entered before signaling that an error was made.
We do not have to tell the thief how many bits to enter, and someone trying to use our lock might therefore try 5, 6, or more digits. We can add this feature with a Try pushbutton to test the combination already entered. If Try is pressed any time except when the machine has processed 3 correct bits, we should terminate the operation in an error state. NEXT>>
Related Articles -- Top of Page -- Home