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

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

ENUMERATION

Suppose you enumerate all the patterns the hardware must recognize as being evenly divisible by four. Youýll have:

100 (4), 1000 (8), 10000 (16), 100000, 1000000ý

The first pattern, 100, is four. The second pattern is eight, the third 16, and so on. Notice that all of the numbers following the initial 100 pattern contain an additional trailing zero. You may recall that adding a trailing zero to a binary number causes its size to double.

Here are some additional sequences that will also work:

1100 (12), 11000 (24), 110000, 1100000ý

10100 (20), 101000 (40), 1010000, 10100000ý

11100 (28), 111000 (56), 1110000, 11100000ý

Now, you have a problem. There are already four different types of patterns that evenly divide by four. If you keep going, there will be plenty more (in fact, you could never list them all).

See how the problem just got a little more difficult to solve? Maybe a different approach should be taken. Think back to your grade school education when you first learned about remainder division. What is 14 divided by four? The answer is three with a remainder of two (three with two left over). When you apply this technique to your problem, consider only the remainder. If the remainder is zero, the input number was evenly divided by four. If the remainder is one, two, or three, the input number is not evenly divisible by four.

PREVIOUS • NEXT