State Machines for Sign Testing and Comparison

Unsigned comparison

We can compare the magnitude of two unsigned BF numbers using a left-to-right lexicographic comparison. This is easily done with a simple state machine having three states, E (Equal), G (Greater) and L (Less). We start in state E, and stay there as long as the input bits from the two numbers are equal. As soon as we find a difference, we switch to state G or L, and stay there until all the input is processed. The final state gives us the result of the comparison.

Comparison State Transitions
Old State Input X,Y New State
E 0,0 E
E 1,1 E
E 1,0 G
E 0,1 L
G
G
L
L

Here's an example.

Example 8
Input X 0 1 0 0 1 0 0 1 0 1 0 0 0
Input Y 0 1 0 0 1 0 1 0 0 1 0 1 0
State E E E E E E E L L L L L L L

The final state L means that X < Y.

Sign testing

If we're using the convention for signed numbers suggested earlier that the boundary between positive and negative numbers is Fn+1/2, in order to find out the sign of a number we need to compare it with Fn+1/2. We've just discovered how to do comparison, so all we need is a way to compute Fn+1/2.

We found before that Fn+1/2 consists of every third bit starting from Fn-1, with a few terminating conditions. To compute this using a state machine, we just need a state that cycles through three different values, and output a 1 whenever it reaches one of those states.

The state transition table will look like this:

Old State Output New State
0 0 1
1 1 2
2 0 0

Here's what running this machine produces for n = 10.


 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1 F0
State 0
 1
 2
 0
 1
 2
 0
 1
 2
 0
 1
Output
 0
 1
 0
 0
 1
 0
 0
 1
 0
 0
 1

As with some of our earlier machines, we need to "or" the outputs for the F1 and F0 positions together to produce the final result:


 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1
Result 0
 1
 0
 0
 1
 0
 0
 1
 0
 1

Signed comparison

To perform a signed comparison, we first need to test the signs of the operands. If they have different signs, we immediately know the result – the positive one is greater than the negative one. If they have the same sign, the result is the same as an unsigned comparison of the operands.

We can implement this logic by prepending the sign bits to the operands and then performing an unsigned comparison of the resulting n+1 bit operands.



---