State Machine for Negation

Let's look at a negation example from a state machine perspective.

This is our starting configuration. There are two state bits (orange) and a 2-bit input window (yellow). We consider there to be a virtual 0 bit to the left of the first input bit, shown here in grey.

The positioning of the state bits in the diagram, which we will call the state window, indicates the weights currently associated with the state bits. With this initial state window position, the state bits represent a value of F_n+1, where n is the number of output bits required. In this example, n = 10.

The basic steps performed by the machine will be subtracting some input bits from the state, and then shifting the state window to the right. When shifting the state window, we will want to maintain the invariant that the value of the state (i.e. the sum of its current weights), plus the value of the output bits generated so far, remains the same.

This leads to a limited set of moves we can make to shift the state window by one place:

• In any state XY, we can output X and set the state to Y0. Call this a Type A move.
• In state 10, we can also replace the 1 with 011, output 0 and set the state to 11. Call this a Type B move.

We will want to choose moves that make all the subtractions "easy", meaning that there is a 1 in the state wherever we have a 1 in the input to subtract. So we want to avoid any moves that would lead to subtractions that are not easy.

A consequence of this is that as long as there are input bits remaining to be processed, we cannot let the state become 00. Then the state would never have any 1 bits in it again, and any subnsequent subtractions would be hard.

In the initial state, a Type A move would leave the state zero, so the only move available is Type B, giving

Because we only want an n-bit result, the output bit from the first move can be discarded.

To choose the next move, we might consider subtracting the first bit in the input window from the state (leaving it unchanged) and then making a Type A move. That would leave us in this position:

Now we must subtract the 1 in the input window from the state, because it's our last chance to do so. But that would leave the state zero, which we can't do yet.

Instead we must subtract the second bit in the input window from the state. Since we've used up two input bits, we move the input window by two places.

Here the input bits we just consumed have been struck out, to remind us that they've been used.

Now we are forced to make a Type B move to avoid a zero state.

We need to shift the state window one more place so that it catches up with the input window. The only move available for this is Type A.

There is nothing in the input window to subtract here, so we only need to shift. We are forced to make a Type B move.

We've seen this configuration before, so we know what to do: Subtract the yellow 1, then Type B, then Type A.

Subtracting the 1 here would be too hard, so we just consume the 0 and make a Type B move.

Now we can subtract and consume the 1. In this case we could consume the 0 as well, but there's no need.

Now we make a Type A move.

Then we make a Type B move to get

At this point we can consume both input bits, giving

Now all input has been consumed, so state 00 is allowed, and we can make two Type A move to give

This gives an output that is not normalised, so we need to perform a normalisation pass at the end to give the final result:

State transition table

So far we've been thinking of shifting the input window and shifting the state window as separate steps, but in the actual machine we will merge them into a single operation that shifts both windows together.

With that in mind, we can start filling out a state transition table for the rules we've discovered.

The Last Input column indicates whether we are processing the last 2 bits of the input. The move types shown in the grey cells are just for information, they don't affect the operation of the machine.

There are some cases that we haven't seen in our example, so we need to work out what to do with them.

• State 11, input 00:

Here we need to make a Type A move.

• State 11, input 01, two input bits remaining:

Subtract the 1 and then make two Type A moves.

• State 11, input 10, two input bits remaining:

Subtract the 1. Although not strictly necessary, the table will be simplified if we consume both input bits.

Now make two Type A moves.

• State 10, input 00, two input bits remaining:

Consume two input bits and make two Type A moves.

• State 10, input 01, two input bits remaining:

This is something of a special case. If we made a Type B move here, we would end up with

with a 1 in the state overhanging into the F₀ position. Fortunately we don't need to do that, because in this case the subtraction is actually easy: F₂ - F₁ = 2 - 1 = 1 = F₁.

followed by two Type A moves

The two remaining entries in the table above are unreachable. State 10 with input 10 cannot occur, because the only ways to reach state 10 are to have been in state 11 and either:

1. seen input 00 and consumed 1 bit
2. seen input 01 and consumed 2 bits
3. seen input 10 and consumed 1 bit

In case 1, the next input bit is 0. In cases 2 and 3, the last input bit consumed was 1, and since we're assuming the input is normalised, the next input bit cannot also be 1.

We can now fill in the rest of the table entries. Here the unreachable ones are marked with dashes.

We don't need a row for state 01, since it is never reached. We also don't need a row for state 00, because it is only reached once all the input bits have been consumed.

Eliminating double moves

As with normalisation, we would prefer to have a machine that only advances one place per step. We can do this the same way, by introducing a new state bit D that is 1 when we are in the middle of a double advancement. Since the second move is always Type A in such a case, the output bit is determined by the first bit of the state, so we don't need to keep any additional information.

For example, in state 11, input 01,

the first step is to subtract the 1 and then make a Type B move.

The state is coloured light orange here to indicate that the D bit is set. The second move is Type A, ignoring the input bits.

We can similarly split up the other double moves, leading to the following table.

Single-step example

Here's a diagram of the single-step version of the machine working on Example 7.

Producing normalised output

An irritating feature of the machine we've designed so far is that it almost, but not quite, produces normalised output. As long as there are more that two input bits remaining, the only transition producing output 1 is from state 11 with input 00 to state 10, after which the next transition must produce output 0.

The only time unnormalised output can be produced is at the end of the input, when state 11 with input 00 results in output 11. It is a nuisance that we have to perform an entire normalisation operation, which requires another two full passes over the data, just to deal with this case.

The reason this case occurs is that we are unable to look ahead in the input to see whether there are any 1 bits remaining, so we need to maintain a non-zero state just in case we encounter another 1. This makes it possible to reach the end with a pair of 1s in the state that we can't get rid of other than by dumping them out.

If we could look ahead to see whether there are any remaining 1s in the input,  we could avoid this situation. If we redefine the "last input" condition to be that all input bits to the right of the input window are zero, then we will never enter state 00 with 00 in the input window, which is the only case that produces output 11.

We can enable this lookahead by performing a preliminary pass from right to left generating an auxiliary input bit, let's call it E for "end of input", that is 1 whenever all input bits further to the right are 0. We can do this with another simple state machine:

Here's our example again with the E bits added.

We now have an E window that moves along with the input window and takes the place of the "Last Input" condition.

We will need to make a few other changes to the table:

• D = 0, E = 1, state 10, input 00 will no longer set D.  There is little point in doing so, since any number of further moves could be needed before the end of the input is reached.
• Add an entry for D = 0, E = 1, state 00. This entry will be looped over while processing a string of trailing zeroes.
• The special move we made at the end of input for state 10, input 01 cannot be used now; we will have to handle it the general way for both E = 0 and E = 1. We will take care of that case in a different way later.

The table is now:

Note that the entry for E = 1, state 00, input 00 is now unreachable.

If we run this new machine on our example, when we get to here,

because there is a 1 in the E window, the next moves are

and then

and then

and all subsequent moves output zero. To summarise,

Terminating case

Now we need to look at the special terminating case again. It arises when we are in this position:

Using the latest table gives

where we have assumed a virtual 1 bit for E and a virtual 0 input bit in the F₀ position.

The next move gives

At this point we need to fold the 1 in the F₀ position back into F₁. But this is easy, because the last output bit will always be 0 in this case. So we just need to "or" the last output bit with the left bit of the state as a final step.

---