Turing Trains

 

computational train track layouts

menu

2's Complement

Two's complement is a method of representing negative binary numbers. It allows arithmetic operations to work correctly with negative values, in a similar manner as positive numbers. The MSB (most significant bit) of each register is reserved to hold the sign of the number. A 0 denotes a positive value, so positive values remain unchanged. A leading 1 denotes a negative value.

Normally, a 3 bit binary number ranges from 0 (000) to 7 (111). With 2's complement the range is from plus 3 (011) to minus 3 (101).

Note that binary zero (all 0's) has a single representation.

Applying the 2's complement function a second time reverts back to the original number.

Dec Binary   Dec 2's Comp
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
  +3
+2
+1
 0
-1
-2
-3
011
010
001
000
111
110
101
 

Both these layouts calculate the value of A minus B using the 2's complement method of invert and add 1. The result is held in register B, so the original value of B is 'lost'. Three functions are used:

  1. Inverter function, to invert B.
  2. Incrementor function, to increment (add 1) to B.
  3. Add function, to add A to B.

Operation

Enter the values of A and B and start the train from the station. When the train halts, the result can be read from register B.

Train track layout to calculate A Minus B
subtract function
Click grass to pause/run train Click points to switch 0/1 Click start to reset train/points
lazy point Lazy points switch between upper 0 or lower 1 branch lines.
Trains arriving on a branch line switch the point to that line.
sprung point Sprung points allow branch line trains to join the main line.
All main line trains go straight ahead and never 'branch off'.

How it works

The lower Inverter and Incrementor functions calculate the 2's complement of B. The Inverter uses compact flip-flops. The Adder then adds the value of A to B.


This second layout is more compact as the Incrementor is not needed. Instead, a 'first return' latch ensures the train returns to the Adder to add the final 1. The operation is the same as the layout above.

Train track layout to calculate A Minus B
subtract function
Click grass to pause/run train Click points to switch 0/1 Click start to reset train/points
lazy point Lazy points switch between upper 0 or lower 1 branch lines.
Trains arriving on a branch line switch the point to that line.
sprung point Sprung points allow branch line trains to join the main line.
All main line trains go straight ahead and never 'branch off'.

How it works

From the station, the train enters the Inverter function which inverts the value of B. It then passes up to the Adder, resetting the 'first return' latch to 0 on the way. Therefore there is no need to reset this latch before each new calculation.
The Add function adds A to B. As the train returns, it uses the top set of latches to set A to 1. The 'first return' latch returns the train to the Adder, so that the 1 is added to B.
On its second visit, the 'first return' latch lets the train pass through, so the train returns to the 'Halt' siding to end the calculation.

Note

  1. The 2's complement method only works when all registers are of the same size. Add and Incrementor overflows are simply 'lost', so there are no overflow error lines.
  2. If B is greater than A, then the result of A-B is negative, and is read as a 2's complement value.

Turing Trains | cr31.co.uk | 2017

 

use your browsers 'zoom' option to enlarge layouts