Contents > Functions

Decrement

The decrement function subtracts one from its argument:

f(x) = x − 1

Its circuit consists of chain of half subtractors, devices capable of single-digit subtraction. Each half subtractor accepts a 1-bit minuend, X, and a 1-bit subtrahend, Y, and it returns their signed difference, a 2-bit value composed of the sign bit, B, and the ones bit, D. The table below shows the outputs for all possible inputs.

The table reveals B and D are:

B = XY

D = X ⊕ Y = (X ≠ Y) = XY + XY = B + XY

From De Morgan's laws:

XY = XX + XY = X(X + Y) = X + X + Y = X + T, T = X + Y

XY = XY + YY = Y(X + Y) = Y + X + Y = Y + T, T = X + Y

Cleaning up:

T = X + Y

B = X + T

D = B + Y + T

That implies the following circuit.

In the code below, which is based on that schematic, a horizontal I-tetromino functions as the upper OR.

halfSubtractor.t
ih 0
ih 4
jl -1
iv -2
lr 3
iv 4
nor nor1 1 1
nor nor2 -1 6
nor nor3 3 6
ih -3
ih 1
ju -1
ju -4

in x -2..1 0
in y 2..5 0
out b -5 14
out d -2 14

Here is its response to all input combinations:

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

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

The image below depicts a Tetris realization of an 8-bit decrement function that calculated 42 − 1. The sequence in which components were built determined the evaluation order. It started with a 1-bit constant function in the bottom-right, which supplied the initial borrow-in. From there, digits were evaluated right-to-left and bottom-up. The final borrow-out was discarded.

The following image shows a Tetris realization of a 16-bit decrement function that calculated 0 − 1. It rolled back to all ones, the two's complement representation of −1 or the maximum unsigned integer value.