State Machine for Normalisation

The normalisation process described earlier is easy to perform by hand, but it is not well suited to implementation in hardware, as it requires looking ahead by some unknown amount before deciding what to do with a given bit. It would be useful if we could find a state machine based algorithm that makes some fixed number of passes over the input.

Let's look at the following example.

Starting at the left required us to do a lot of looking ahead and backtracking, so let's see what happens if we start at the right. We can immediately tell what to do with the last bit – since it's zero we can just copy it to the output.

To determine the next output bit we need to look at a window of two input bits. We see that the output must be 1.

Then we have another zero, which we copy to the output as before.

The next step is a bit tricky, because we can't tell what the output bit should be by looking at any fixed size window.

To see why, consider that 0111 normalises to 1001, whereas 01111 normalises to 10100. But what we can say is that if a 11 is preceded by an even number of 1s,  it will normalise to something ending in 0; whereas if it is preceded by an odd number of 1s, it will normalise to something ending in 1.

So suppose we make a preliminary pass from left to right and assign a "parity" bit to each position indicating whether it is preceded by an even or odd number of consecutive 1s.

We can do this with a simple state machine that scans the input from left to right and uses a state bit to track the number of consecutive 1 bits seen so far mod 2. When we see a 0 we reset the state to 0, and when we see a 1 we complement it. The output is just the current state before we update it.

Here are the parity bits we get from running this machine.

We can now see from the parity bit that the 11 we're looking at is at the end of an odd-length run of 1s (because the preceding run has even length), so the output should be 1.

Moving one place to the left, we now have another 11 in the window, but this time the parity bit is 1, so it's at the end of an even-length run of 1s. When that happens, we need to output 00 and remember to carry a 1 to the next place. Now we advance two places to the left.

We have an input of 00 with a carry of 1 added to it, giving 1.

Input 0 with no carry gives 0.

Input 11 with parity 1 gives 00 with carry 1, and advance 2.

Input 11 with parity 0 and carry 1 gives 01 with carry.

We're starting to get the pattern now, so let's fast-forward the next few steps. The next time we see something new is here:

Input 10 with carry 1 gives 11. Because the parity is 0, this then gets normalised to 00 with carry 1 and we advance 2.

And the same thing again.

Input 0 with carry 1 gives 1.

There are no more input bits, but we need to run the machine for one more step in case there was a carry to flush out. In this case there isn't.

We've seen enough cases now that we can start building a state transition table.

An empty entry in the Parity column means we don't care about the parity in that case.

Note that there are some unreachable combinations. These eliminate the cases where we would have to add a carry to a 1 and generate more carries.

Improving the normalisation state machine

While this scheme works, it's a little inconvenient that we sometimes have to advance by one bit and sometimes two. It would be more straightforward if we could always advance one bit at each step. We can do this by introducing another state bit, let's call it N, that is 1 when we are in the middle of normalising a 11 pair, and 0 otherwise.

Whenever we would have output 00 and advanced by 2 before, we set N and output 0. Then whenever N is set, we ignore all the inputs, output 0 with carry 1 and reset N.

Here's the new state machine in action, laid out in a single table.