Richard's Controller
From Wikipedia, the free encyclopedia
 |
This article has been nominated to be checked for its neutrality. Discussion of this nomination can be found on the talk page. |
The Richard’s Controller is a clever method of implementing a finite state machine using simple integrated circuits and combinational logic. The method has been named after its inventor, Charles L. Richards. One of the distinct advantages of this method over conventional finite state machine design methods is that it allows for easier design of complex finite state machines than the traditional techniques of state diagrams, state transition tables and Boolean algebra offer. Using Richard’s technique it becomes relatively easy to implement machines with many hundreds or even thousands of states.
Contents |
[edit] History
The Richard’s Controller was made because of the need for an easier method of designing finite state machines than using the traditional method of state diagrams, state transition tables, and logic minimization. At the time many of the computer based logic minimization tools that we have today did not exist. Hence logic minimization was for the most part limited to the use of Karnaugh Maps and DeMorgan's Law. Because of this Charles L. Richards invented a method of implementing a finite state machine that did not need an explicit state transition table. He published his findings in the February 1973 issue of Electronics. His generalized implementation became popular and by the 1980’s was considered a classic design method. While it is unlikely that commercial products found today contain a classic Richard’s Controller, (since there are faster designs now than ones that use loadable counters,) there is a good chance of a modified Richard’s Controller or a design derived from the Richard’s Controller being used.
[edit] Applications
Because of the Richard’s Controller’s ability to scale to use many states easily, it can be used in many practical applications. A few examples of devices that need a complex controller are CPUs, Graphics Cards, Network Interfaces, Hard Drives, Bus Controllers (USB, PCI, Firewire…) The modern information age would not be possible without complex controller designs like the Richard’s Controller.
[edit] The Richards Flowchart
The Richard’s controller is a Mealy machine since its output is dependent on both the current state and the input. However Richards designed his own method of representing states using a flowchart diagram, instead of the state diagram. Each state is represented as a transfer condition on the flowchart. Each condition has two control paths leading out of it, a YES or a NO. The condition is YES or NO (TRUE or FALSE) based upon a single bit input to the machine. (Richards 108) Depending on what the input for a condition is, one of the two transfer functions associated with that condition will be executed. The machine considers executing a function to be setting the output of a single pin on the device, this can be used to trigger combinational logic. After a transfer function is executed, the machine will enter a new state, each transfer function will either implicitly or explicitly define a new state to transition to. An implicit state definition could also be called the default, since it will occur without any additional circuitry from the designer, if the condition is YES then it will transition to the next state numerically. For example if you are at state 0 and a YES occurs then you will transition to state 1. If the condition is NO, then the machine will remain at its current state. Using this behavior it is possible to create a machine with a simple sequential flowchart. Of course a sequential machine is usually not very useful, thankfully there is a way to transition to states out of order, using a so called jump. In order to implement a jump, additional hardware is required in order to select the destination state, which depends on what function is being executed.
[edit] Kernel of the Controller
The Richards Controller’s core kernel can be boiled down into four parts, a counter, a multiplexer, and two decoders. A simple controller can be built using the classic 7400 series of TTL logic integrated circuits. The counter used is the 74163, the multiplexer is the 74151 and the two decoders are the 7442 part. (Richards 108) The output from the counter selects what bit from the multiplexer input should be sent to the output Y, (the inverse of which is sent to the output WN.) If Y is high, then the counter is allowed to increment, otherwise it is not. Likewise, Y must be high in order to enable YES function outputs since the D input on the decoder is connected to WN, while it must be low to enable the NO function outputs, since the D input on that decoder is set to Y. In order to perform a jump, you must set the LDN bit on the counter, and the A, B, C and D inputs. LDN tells the counter to load the value on the A, B, C and D inputs. Using some combinational logic, you can load a value into the counter for certain functions but not others, as well as specifying the state address to be loaded, given what function is active. Doing this is a simple matter of building a table of functions and the states that they should transition to, then finding the Boolean Algebra expression for each bit that makes up the address of the state to be jumped to.
[edit] References
Richards, Charles. “An easy way to design complex program controllers.” Electronics 1 February 1973: 107-113.
Wakerly, John F. Digital Design – 3rd Edition. Upper Saddle River, NJ: Prentice-Hall Inc. 2001.
