2.3 Combinatorial multi-bit subtractor

Let us now consider a multi-bit subtraction. Let x and y both have n bits, and x_i denote bit i of x. We will use d to represent the difference d = x - y. d also has n bits.

First, d₀ = R(x₀,y₀) as there is no borrow from a less significant digit.

Second, d₁ = R(R(x₁,y₁),B(x₀,y₀)) because if the subtraction of bit 0 yields a borrow of 1, then d₁ is affected by it.

Third, d₂ = R(R(x₂,y₂),B(x₁,y₁) + B(R(x₁,y₁),B(x₀,y₀))) because there are two possible sources of the borrow that affects d₂. The first source is B(x₁,y₁), and the second source is B(R(x₁,y₁),B(x₀,y₀)). Although only up to one of these sources can be a 1, they still need to be combined to become the borrow that affects the computation of d₂.

You can see how these equations are similar to the computation of R(x_i,y_i) in an addition. Just like with the case of a combinatorial multi-bit adder, the complexity of computing d_i increases as the square of i.