Patterns in Numbers

THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

PATTERNS IN NUMBERS

Technically Speaking A State Machine Design for Binary Pattern Recognition

by James Antonakos

Start ı The Problem ı Enumeration ı State Diagram Approach ı A Little Synchronous Logic ı State Transition Table ı Let Karnaugh Maps Find the Patterns ı A Hotshot One-Shot ı The Real Thing ı Other Implementations ı I Challenge Youı ı Sources and PDF

STATE DIAGRAM APPROACH

The digital machine will have four states. One state, zero, is where the input number is evenly divisible by four. The other three states (one, two, and three) indicate an unrecognized pattern. Figures 1aıi show the development of the state diagram for the machine capable of recognizing the evenly-divisible numbers.

Figure 1aıHere you can see the initial state diagram. b) Zero divided by four equals zero, remainder zero. c) One divided by four equals zero, remainder one. d) Two (10) divided by four equals zero, remainder two. e) Three (11) divided by four equals zero, remainder three. f) Four (100) divided by four equals one, remainder zero. g) Five (101) divided by four equals one, remainder one. h) Six (110) divided by four equals one, remainder two. i) Seven (111) divided by four equals one, remainder three.

The last bit in the input sequence always takes you to the correct remainder state. The eight links between states are all added one by one as the input number is enumerated from zero to seven. Bits are entered from MSB to LSB, so beginning in Figure 1d, you must move between states as the input bits are entered, adding a new link each time so that you always reach the remainder state on the last bit. If you carefully examine the progression of adding links in Figures 1aıi, youıll see the simplicity of this design method.

Does the final state diagram in Figure 1i do what you want it to? Letıs test it with a large number that we know is evenly divisible by four:

12345 ı 4 = 49380

which is C0E4 hexadecimal, or 1100000011100100 binary. Enter each bit of the number one by one into the state diagram in Figure 1i. You should end up in state zero. Note that you may pass through state zero one or more times before entering all the input bits.

PREVIOUS • NEXT

Circuit Cellar provides up-to-date information for engineers. Visit www.circuitcellar.com for more information and additional articles.
For subscription information, call (860) 875-2199, subscribe@circuitcellar.com or subscribe online. ıCircuit Cellar, the Magazine for Computer Applications. Posted with permission.