# Finite-state Machine

## Chapter 16 - Principles Of Digital Computing

Feedback is a fascinating engineering principle. It can turn a rather simple device or process into something substantially more complex. We’ve seen the effects of feedback intentionally integrated into circuit designs with some rather astounding effects:

• Comparator + negative feedback—————-> controllable-gain amplifier
• Comparator + positive feedback—————-> comparator with hysteresis
• Combinational logic + positive feedback—> multivibrator

In the field of process instrumentation, feedback is used to transform a simple measurement system into something capable of control:

• Measurement system + negative feedback—-> closed-loop control system

Address  -----> Data          Gray Code count sequence:
0000   -------> 0001                 0   0000
0001   -------> 0011                 1   0001
0010   -------> 0110                 2   0011
0011   -------> 0010                 3   0010
0100   -------> 1100                 4   0110
0101   -------> 0100                 5   0111
0110   -------> 0111                 6   0101
0111   -------> 0101                 7   0100
1000   -------> 0000                 8   1100
1001   -------> 1000                 9   1101
1010   -------> 1011                10   1111
1011   -------> 1001                11   1110
1100   -------> 1101                12   1010
1101   -------> 1111                13   1011
1110   -------> 1010                14   1001
1111   -------> 1110                15   1000


Address  -----> Data            Address  -----> Data
00000  -------> 0001            10000  -------> 0001
00001  -------> 0010            10001  -------> 0011
00010  -------> 0011            10010  -------> 0110
00011  -------> 0100            10011  -------> 0010
00100  -------> 0101            10100  -------> 1100
00101  -------> 0110            10101  -------> 0100
00110  -------> 0111            10110  -------> 0111
00111  -------> 1000            10111  -------> 0101
01000  -------> 1001            11000  -------> 0000
01001  -------> 1010            11001  -------> 1000
01010  -------> 1011            11010  -------> 1011
01011  -------> 1100            11011  -------> 1001
01100  -------> 1101            11100  -------> 1101
01101  -------> 1110            11101  -------> 1111
01110  -------> 1111            11110  -------> 1010
01111  -------> 0000            11111  -------> 1110


If A4 is 0, the FSM counts in binary; if A4 is 1, the FSM counts in Gray Code. In either case, the counting sequence is arbitrary: determined by the whim of the programmer. For that matter, the counting sequence doesn’t even have to have 16 steps, as the programmer may decide to have the sequence recycle to 0000 at any one of the steps at all. It is a completely flexible counting device, the behavior strictly determined by the software (programming) in the ROM. We can expand on the capabilities of the FSM even more by utilizing a ROM chip with additional address input and data output lines. Take the following circuit, for example: Here, the D0 through D3 data outputs are used exclusively for feedback to the A0 through A3 address lines. Date output lines D4 through D7 can be programmed to output something other than the FSM’s “state” value. Being that four data output bits are being fed back to four address bits, this is still a 16-state device. However, having the output data come from other data output lines gives the programmer more freedom to configure functions than before. In other words, this device can do far more than just count! The programmed output of this FSM is dependent not only upon the state of the feedback address lines (A0 through A3), but also the states of the input lines (A4 through A7). The D-type flip/flop’s clock signal input does not have to come from a pulse generator, either. To make things more interesting, the flip/flop could be wired up to clock on some external event, so that the FSM goes to the next state only when an input signal tells it to. Now we have a device that better fulfills the meaning of the word “programmable.” The data written to the ROM is a program in the truest sense: the outputs follow a pre-established order based on the inputs to the device and which “step” the device is on in its sequence. This is very close to the operating design of the Turing Machine, a theoretical computing device invented by Alan Turing, mathematically proven to be able to solve any known arithmetic problem, given enough memory capacity.

• Share
Published under the terms and conditions of the Design Science License