Subtractors#
Definition: Subtractor
A subtractor is a digital circuit which can perform the subtraction of binary numbers.
Integer Subtractors#
Half Subtractor#
Definition: Half Subtractor
A half subtractor is a digital circuit which implements the subtraction of two bits:
- Inputs: a minuend bit \(x\) and a subtrahend bit \(y\);
- Outputs: a difference bit \(d\) and a borrow out bit \(b_{\text{out}}\).
- Functionality: The \(d\) bit is equal to the difference \(x - y\). The \(b_{\text{out}}\) is set when the operation would require a borrow from a previous bit.
A half subtractors essentially computes the following Boolean function:
| \(x\) | \(y\) | \(d\) | \(b_{\text{out}}\) | |
|---|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) | |
| \(0\) | \(1\) | \(1\) | \(1\) | |
| \(1\) | \(0\) | \(0\) | \(1\) | |
| \(1\) | \(1\) | \(0\) | \(0\) |
From the above truth table, we can derive expressions for \(d\) and \(b_{\text{out}}\):
Example: Logic Gate Implementation
Using the above expressions, we can construct a half subtractor via logic gates:
Full Subtractor#
Definition: Full Subtractor
A full subtractor is a digital circuit which implements the subtraction of bits, accounting for a borrow from a lower significant position:
- Inputs: a minuend bit \(x\), a subtrahend bit \(y\), and a borrow in bit \(b_{\text{in}}\);
- Outputs: a difference bit \(d\) and a borrow out bit \(b_{\text{out}}\).
- Functionality: The \(d\) bit is the result of \(x - y - b_{\text{in}}\). The \(b_{\text{out}}\) is set when the operation requires a borrow from the next higher bit.
A full subtractor essentially computes the following Boolean function:
| \(x\) | \(y\) | \(b_{\text{in}}\) | \(d\) | \(b_{\text{out}}\) | |
|---|---|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | |
| \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | |
| \(0\) | \(1\) | \(0\) | \(1\) | \(1\) | |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | |
| \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | |
| \(1\) | \(0\) | \(1\) | \(0\) | \(0\) | |
| \(1\) | \(1\) | \(0\) | \(0\) | \(0\) | |
| \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
From the above truth table, we can derive expressions for \(d\) and \(b_{\text{out}}\). Note that \(d\) is high when an odd number of inputs are high, and \(b_{\text{out}}\) logic can be constructed by combining two half subtractors:
Example: Logic Gate Implementation
Using the above expressions, we can construct a full subtractor via logic gates:
Ripple-Borrow Subtractor#
A ripple-borrow subtractor is a digital circuit which can calculate the difference \(x - y\) of two \(n\)-bit numbers either in unsigned integer representation or in two's complement representation. It is constructed by chaining \(n\) full subtractors:
When \(x\) and \(y\) are unsigned integers:
- If the final \(b_{\text{out}}\) is \(0\), then \(x \ge y\) and \(d\) is the unsigned integer representation of the difference \(x - y\).
- If the final \(b_{\text{out}}\) is \(1\) (underflow), then \(x \lt y\) and \(d\) is the two's complement representation of the difference \(x - y\).
When \(x\) and \(y\) are two's complement integers:
- If \(b_{\text{in}}\) and \(b_{\text{out}}\) of the most-significant full subtractor are different, then overflow has occurred and \(d\) is invalid.
- If \(b_{\text{in}}\) and \(b_{\text{out}}\) of the most-significant full subtractor are equal, then \(d\) is the the difference \(x - y\) as a two's complement integer.
Adder Implementation#
When using two's complement, the subtraction \(a - b\) is equivalent to the addition of the two's complement of \(b\) to \(a\). This means that we can easily implement a subtractor by slightly modifying a full adder:
When \(\overline{\text{add}}/\text{sub} = 0\), the multiplexer forwards \(b\) to the adder and the addition \(a + b\) is performed. When \(\overline{\text{add}}/\text{sub} = 1\), the multiplexer forwards the bitwise negation \(\overline{b}\) of \(b\) to full adder. Furthermore, \(c_{\text{in}}\) is set to \(1\) which is equivalent to adding \(1\) to \(\overline{b}\). This means that the adder essentially adds the two's complement of \(b\) to \(a\), resulting in the subtraction \(a - b\).