 |
www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com |
|
|
|
A practical use
The last page talked about continuous time state machines, and
menioned that they are useful in hardwares and softwares that interact
directly with hardwares. In this page we shall see an example of the
latter.
A phone line decoder
Many phone companies offer a caller id facility: the caller's number is
sent to the callee during the ringing. The callee's phone can read
this number from the line and display it suitably (or do something
more exotic, like provide selective answers or just hang up if the
number is in some black list). The phone company sends the information
using a encoding scheme called DTMF (Dual Tone Multi-Frequency) and
there are specialised chips (very inexpensive) that decode the
information and output the digits via its pins. We shall consider phone
numbers that is made of only the digits 0 to 9 (and not *'s or
#'s). So there are 10 distict digits to consider, and since 10 is
between 23 and 24, we need 4 bits to represent
these digits. So it is only natural that a typical DTMF decoder chip
has 4 pins (Q0,Q1,Q2 and Q3) dedicated for this purpose. Now there is also another
configuration (other than the 10 digits) that the chip needs to
report: the situation when there is no number in the line. DTMF
decoder chips have a fifth pin (STD) for this, which remains low during the
idle period. Everytime a digit is detected
in the phone line, the digit is output via the 4 Q-pins, and
the STD pin goes high. Thus each rising edge (i.e., 0 to 1 transition) of the STD pin denotes a digit. The states of the Q-pins at that moment gives the digit. Here is a typical
timing diagram that you may get if the caller's number is 23.
Notice that the Q-pins are meant to be read only at the rising edges of the STD pin.
Also, there is a little gap between the consecutive
digits. There is another point of importance: the end of the number is
not signalled by any special character. So we have to deduce that the
end has been reached when the STD line remains low for period longer
than the inter-digit gap. Typically inter-digit gaps are much less
than 1 sec. So if the STD line remains 0 for more than 1 sec after a
digit, we may safely deduce that this was the last digit of the phone number.
Our job is to program a microcontroller in such a way that it can pick
up the complete phone number (and possibly do interesting things with
it). This is a very typical example of software interacting directly
with hardware, and the principles that we shall illustrate here find
application everywhere in robotics.
The set up
This is not a tutorial on microcontrollar projects. So we shall not go
into the details of what microcontroller to use and how to set up the
circuit. It suffices to know that the microcontroller is a computer
that can read the 5 pins Q0-Q3 and STD. We shall use the generic form
read(pin) to denote a function that reads a specified pin
(and returns 0 or 1).
Designing the DFA
Before we go into the details of the DFA let us informally think of
the flow of action. We have no way of knowing when the phone rings (we
shall not discuss the possibility of hooking up a separate
ring-detector circuit to the microcontroller, as it will not change
the underlying principle of DFA design), so we have to continuously
monitor (or "poll", to use a technical term) the STD line. The moment
it becomes 1, we have to read Q0-Q3 to get the digit. This will be
over much before the STD line goes low. So we have to now poll the STD
line again, this time waiting for it to go low. When it does go low,
we basically do nothing, except start waiting for it go high again.
When it goes high eventually we repeat the same process to get the
next digit.
There is, however, a little catch in it. If we merely follow the above
prcedure we shall never know when we come to the end of the number. So
everytime we wait for the next digit we must time our wait. If the
wait duration exceeds a threshold we should consider that as the end
of the number. We should then stop waiting, and do whatever we want
with the number. After that we have to return to polling for the next number.
Now we are in a position to turn this vague description into a formal
DFA. You have no doubt noticed the numerous "wait"s or "polling"s that
are strewn throughout the description. It should not be difficult to see
that these will translate into the self-loops that are the trademark
of a continuous time DFA. In fact, it will help if we name each state
of our DFA as "waiting for this or that".
One state is obviously "waiting for a digit" (i.e.,
for STD to go high). We shall abbreviate the name to just "digit".
We come to this state whenever STD goes low. So
we must have a self-loop accordingly (we shall ignore the outputs for
the time being). When we get STD=1, we exit this state.
We now finish reading the digit, and go into the next state: "nodigit"
(which means "waiting for the digit to go away"). This state has its
trademark selfloop.
Where do we go when STD becomes low again? Well, we go back to "waiting
for a digit", which is also the initial state (assuming that
the entire process did not start right in the midst of an incoming call!)
This looks like a pretty simple continuous time DFA. But we have to
remember that little point about timing our wait in order to detect
the end of the number. Making timed waits at various points is a
very common requirement in robotics (and sometimes a
contributor of confusion).
We need a way to incorporate the concept of a timed wait within the
framework of a continuous time DFA. We shall use a "timer" that we can
start, and which will "time out" after a specific amount of time. Those of you who know some microcontroller
programming may be tempted to think about timer interrupts and all
that. But often a much simpler expedient works quite well.
Of course, we may use a hardware timer built into the
microcontroller (or even an external timer chip), but a counter
incremented in a
simple C loop will be enough for most purposes, since the exact length
of the delay is not very critical as long as it is within a
permissible range. Most external devices (including phone lines and
human operators)
are much slower than the microcontroller itself. So the permissible
range is usually very wide.
The timer contributes a new output, "Timer on", and a new input "Timed
out". In fact, there is another output that is also needed: "Stop
timer". Imagine waking up one morning before the alarm clock goes
off. Then we must switch off the alarm to prevent it from going off
unnecessarily. Forgetting to turn off unused timers may cause all
sorts of wierd things to happen.
This is all
the change we need to our traditional concept of a DFA in order to
accommodate timed waits.
The DFA for our example now looks like this.
Here X denotes the action that we want to take when we become aware of
the presence of a digit, and Y denotes the action to be taken at the
end of a complete number. Notice that we allow the (ineffectual)
possibility of stopping a timer before it is started.
So far our exposition has been quite abstract. We have used the DFA
formalism to express our ideas. In the next page we shall learn
ways to implement the DFA using C.
|
