Contents > Functions
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.
|0||0||0||0||0 − 0 = 0|
|0||1||1||1||0 − 1 = −1|
|1||0||0||1||1 − 0 = 1|
|1||1||0||0||1 − 1 = 0|
The table reveals B and D are:
B = XY
D = X ⊕ Y
From De Morgan's laws:
XY = XX + XY
XY = XY + YY
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.
© 2023 meatfighter.com