Contents > Functions

Increment

The increment function adds one to its argument:

f(x) = x + 1

Its circuit consists of chain of half adders, devices capable of single-digit addition. Each half adder accepts two 1-bit addends, X and Y, and it outputs their sum, a 2-bit value composed of the twos bit, C, and the ones bit, S. The table below shows the outputs for all possible inputs.

From the table, C and S are:

C = XY = X + Y

S = X ⊕ Y = (X ≠ Y) = XY + XY = XX + XY + XY + YY = (X + Y)(X + Y) = C(X + Y) = C + X + Y

That implies the following circuit.

In the code below, which is based on that schematic, the swap (line 14) enables the output of the bottom NOR (line 13) to hop over the input of the Y inverter (line 17). The X inverter (line 16) feeds into the middle NOR (line 18), which, in turn, feeds into the top NOR (line 25).

halfAdder.t
ih -1
sh -4
sh -6
jl -7
iv -7
iv -7
iv -7
iv -7
iv -7
iv -7
jl 2
jr 2
nor 0 1
swap 2 6
ih -2
notRight -7 28
notLeft -3 28
nor -5 33
lr 4
iv 4
iv 4
sh 3
sh 1
sh -1
nor -3 38
ju -7
iv -8
ih -1

in x -3..0 0
in y 1..2 0
out c -8 44
out s -3..0 44

The following image, which depicts the responses to all input combinations, reveals the swap circuit makes the half adder significantly larger than the half subtractor.

In the full circuit, half adders are chained in the configuration below, where each Ii is an input digits, and each Qi is an output digit.

The circuit is a binary odometer that counts up. When a digit rolls over—when it transitions from 1 to 0—the digit to its left is incremented. The signal to increment a digit is referred to as the carry. The initial carry-in is 0 (far right). Its effect ripples right-to-left. For each half adder, if both the input digit and the carry-in is 1, then the output digit is 0 and the carry-out is 1. Otherwise, the carry-out is 0 and all digits to its left remain the same.

The image below depicts a Tetris realization of an 8-bit increment function that calculated 42 + 1. A 1-bit constant function at the bottom-right supplied the initial carry-in. The final carry-out was discarded.

The following image shows a Tetris realization of a 16-bit increment function. The input is all ones, the two's complement representation of −1 or the maximum unsigned integer value. The function rolled over to all zeros, in agreement with −1 + 1.