Let's look at a negation example from a state machine perspective.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
State | 1 | 0 | |||||||||
Output |
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 Fn+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:
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
F11 |
F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output |
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:
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 1 |
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.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 | 0 |
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.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 |
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.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
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.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 | 1 |
0 |
We've seen this configuration before, so we know what to do: Subtract the yellow 1, then Type B, then Type A.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
0 |
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 | 1 |
0 |
0 |
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
Subtracting the 1 here would be too hard, so we just consume the 0 and make a Type B move.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
Now we can subtract and consume the 1. In this case we could consume the 0 as well, but there's no need.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 0 |
1 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
Now we make a Type A move.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
Then we make a Type B move to get
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
0 |
At this point we can consume both input bits, giving
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |||
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |||
State | 1 |
1 |
|||||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
0 |
Now all input has been consumed, so state 00 is allowed, and we can make two Type A move to give
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |||
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |||
State | 0 |
0 | |||||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
This gives an output that is not normalised, so we need to perform a
normalisation pass at the end to give the final result:
Decimal | 89 | 55 | 34 | 21 | 13 | 8 | 5 | 3 | 2 | 1 | |
Input | 73 |
0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
Output | 61 |
0 | 1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
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.
Last Input |
State |
Inputs | ||||||||
00 |
01 |
10 |
||||||||
No | 11 | B,A | 01 | 10 | A | 0 | 10 | |||
No | 10 | B | 0 | 11 | B | 0 | 11 | |||
Yes | 11 | A,A | 11 | 00 | ||||||
Yes | 10 |
Entry Fields | ||
Moves | Output | New State |
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.
Input | ... | 0 | 0 | ... |
State | 1 |
1 |
||
Output | ... |
Here we need to make a Type A move.
Input | ... | 0 | 0 | ... |
State | 1 |
0 |
||
Output | ... | 1 |
F3 | F2 | F1 | |
Input | ... | 0 | 1 |
State | 1 |
1 |
|
Output | ... |
Subtract the 1 and then make two Type A moves.
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 1 |
0 |
|||
Output | ... |
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 0 |
0 |
|||
Output | ... | 1 |
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 0 |
0 |
|||
Output | ... | 1 |
0 |
F3 | F2 | F1 | |
Input | ... | 1 | 0 |
State | 1 |
1 |
|
Output | ... |
Subtract the 1. Although not strictly necessary, the table will be simplified if we consume both input bits.
F3 | F2 | F1 | |||
Input | ... | 1 | 0 | ||
State | 0 |
1 |
|||
Output | ... |
Now make two Type A moves.
F3 | F2 | F1 | |||
Input | ... | 1 | 0 | ||
State | 1 |
0 |
|||
Output | ... | 0 |
F3 | F2 | F1 | |||
Input | ... | 1 | 0 | ||
State | 0 |
0 |
|||
Output | ... | 0 |
1 |
F3 | F2 | F1 | |
Input | ... | 0 | 0 |
State | 1 |
0 |
|
Output | ... |
Consume two input bits and make two Type A moves.
F3 | F2 | F1 | |||
Input | ... | 0 | 0 | ||
State | 0 | 0 | |||
Output | ... | 1 |
0 |
F3 | F2 | F1 | |
Input | ... | 0 | 1 |
State | 1 |
0 |
|
Output | ... |
This is something of a special case. If we made a Type B move here, we would end up with
F3 | F2 | F1 | F0 |
|
Input | ... | 0 | 1 | |
State | 1 |
1 | ||
Output | ... | 0 |
with a 1 in the state overhanging into the F0 position. Fortunately we don't need to do that, because in this case the subtraction is actually easy: F2 - F1 = 2 - 1 = 1 = F1.
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 0 |
1 |
|||
Output | ... |
followed by two Type A moves
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 1 |
0 |
|||
Output | ... | 0 |
F3 | F2 | F1 | |||
Input | ... | 0 | 1 | ||
State | 0 |
0 | |||
Output | ... | 0 |
1 |
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:
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.
Last Input |
State |
Inputs | ||||||||
00 |
01 |
10 |
||||||||
No | 11 | A |
1 |
10 |
B,A | 01 | 10 | A | 0 | 10 |
No | 10 | B | 0 | 11 | B | 0 | 11 | – |
– |
– |
Yes | 11 | A,A | 11 | 00 | A,A | 10 | 00 | A,A | 01 | 00 |
Yes | 10 | A,A | 10 | 00 | A,A |
01 |
00 |
– |
– |
– |
Entry Fields | ||
Moves | Output | New State |
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.
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,
Input | ... | 0 |
1 | ... |
State | ... | 1 |
1 |
... |
Output |
the first step is to subtract the 1 and then make a Type B move.
Input | ... | 0 |
1 |
... |
State | ... | 1 |
1 |
|
Output | 0 |
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.
Input | 0 |
1 |
... | ... |
State | 1 |
0 |
||
Output | 0 |
1 |
We can similarly split up the other double moves, leading to the following table.
D | Last Input |
State |
Input Bits | |||||||||||
00 |
01 |
10 |
||||||||||||
0 |
No | 11 | A |
1 |
10 |
0 | B | 0 | 11 | 1 | A | 0 | 10 | 0 |
0 |
No | 10 | B | 0 | 11 | 0 | B | 0 | 11 | 0 | – |
– |
– |
– |
0 |
Yes | 11 | A | 1 | 10 | 1 | A | 1 | 00 | 1 | A | 0 | 10 | 1 |
0 |
Yes | 10 | A | 1 | 00 | 1 | A |
0 |
10 |
1 | – |
– |
– |
– |
D | State | All
inputs |
|||
1 | 11 | A | 1 | 10 | 0 |
1 | 10 | A | 1 | 00 | 0 |
1 | 00 | A | 0 | 00 | 0 |
Entry Fields | |||
Move | Output | New State | New D |
Here's a diagram of the single-step version of the machine working on Example 7.
F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | ||||
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |||
Step
0 |
1 | 1 | 0 | ||||||||||
1 |
0 | 1 | 1 | 1 | Out | ||||||||
2 |
1 | 1 | 0 | 0 | State |
D |
|||||||
3 |
0 | 1 | 1 | 0 | |||||||||
4 |
0 | 1 | 1 | 1 | |||||||||
5 |
1 | 1 | 0 | 0 | |||||||||
6 |
0 | 1 | 1 | 0 | |||||||||
7 |
0 | 1 | 0 | 0 | |||||||||
8 |
0 | 1 | 1 | 0 | |||||||||
9 |
1 | 1 | 0 | 1 | |||||||||
10 |
1 | 0 | 0 | 0 | |||||||||
Output | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | |||
Norm | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
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:
Old
State |
Input
|
Output
|
New
State |
0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 1 |
Here's our example again with the E bits added.
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
E | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 | 0 | |||||||||
Output |
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:
The table is now:
D | E | State |
Input Bits | |||||||||||
00 |
01 |
10 |
||||||||||||
0 |
0 | 11 | A |
1 |
10 |
0 | B | 0 | 11 | 1 | A | 0 | 10 | 0 |
0 |
0 | 10 | B | 0 | 11 | 0 | B | 0 | 11 | 0 | – |
– |
– |
– |
0 |
1 | 11 | – | – | – | – | A | 1 | 00 | 1 | A | 0 | 10 | 1 |
0 |
1 | 10 | A | 1 | 00 | 0 | B |
0 |
11 |
0 | – |
– |
– |
– |
0 | 1 | 00 | A | 0 | 00 | 0 | – | – | – | – | – | – | – | – |
D | State | All
inputs |
|||
1 | 11 | A | 1 | 10 | 0 |
1 | 10 | A | 1 | 00 | 0 |
1 | 00 | A | 0 | 00 | 0 |
Entry Fields | |||
Move | Output | New State | New D |
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,
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
E | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
because there is a 1 in the E window, the next moves are
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
E |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
1 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
and then
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
E |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 1 |
0 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
and then
F11 | F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | |
E |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
State | 0 |
0 |
|||||||||
Output | 0 | 1 |
0 |
0 |
1 |
0 |
0 |
1 |
and all subsequent moves output zero. To summarise,
F10 | F9 | F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 | ||||
E | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
Input | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |||
Step
0 |
1 | 1 | 0 | ||||||||||
1 |
0 | 1 | 1 | 1 | Out | ||||||||
2 |
1 | 1 | 0 | 0 | State |
D |
|||||||
3 |
0 | 1 | 1 | 0 | |||||||||
4 |
0 | 1 | 1 | 1 | |||||||||
5 |
1 | 1 | 0 | 0 | |||||||||
6 |
0 | 1 | 1 | 0 | |||||||||
7 |
0 | 1 | 0 | 0 | |||||||||
8 |
1 | 0 | 0 | 0 | |||||||||
9 |
0 | 0 | 0 | 0 | |||||||||
10 |
0 | 0 | 0 | 0 | |||||||||
Output | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Now we need to look at the special terminating case again. It arises when we are in this position:
F3 | F2 | F1 | |
E |
... | ... | 1 |
Input | ... | 0 | 1 |
State | ... | 1 | 0 |
Output | ... |
Using the latest table gives
F3 | F2 | F1 | F0 | |
E |
... |
... |
1 |
1 |
Input | ... |
0 |
1 |
0 |
State | ... |
1 |
1 | |
Output | ... |
0 |
where we have assumed a virtual 1 bit for E and a virtual 0 input bit in the F0 position.
The next move gives
F3 | F2 | F1 | F0 |
||
E |
... |
... |
1 |
1 | 0 |
Input | ... |
0 |
1 |
0 | 0 |
State | ... |
1 |
0 | ||
Output | ... |
0 |
0 |
At this point we need to fold the 1 in the F0 position back into F1. 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.
---