Implicit carry bits

The other implementation does not represent c_i explicitly. This means we have to expand c_i−1 as C(x_i−1,y_i−1) + C(R(x_i−1,y_i−1)),c_i−2).

Using this new representation, we can compute the following:

c₀ = C(x₀,y₀) = x₀y₀
c₁ = C(x₁,y₁) + C(R(x₁,y₁),c₀) = x₁y₁ + (x₁y₁′ + x₁′y₁)(x₀y₀) = x₁y₁ + x₁y₁′x₀y₀ + x₁′y₁x₀y₀ = x₁y₁ + x₁x₀y₀ + y₁x₀y₀
- the optimization is made possible because
  $pq+ pq′r+ p′qr = pq + pqr+ pq′r +pqr + p′qr (1) ′ ′ = pq + p(q + q)r+ (p+ p )qr (2) = pq + pr+ qr (3)$
c₂ = C(x₂,y₂) + C(R(x₂,y₂),c₁) = x₂y₂ + (x₂ + y₂)(x₁y₁ + x₁x₀y₀ + y₁x₀y₀) = …

Then, we can compute the sum values:

s₀ = R(x₀,y₀) = x₀y₀′ + x₀′y₀
s₁ = R(R(x₁,y₁),c₀) = (x₁y₁′ + x₁′y₁)′(x₀y₀) + (x₁y₁′ + x₁′y₁)(x₀y₀)′ = (x₁′ + y₁)(x₁ + y₁′)x₀y₀ + (x₁y₁′ + x₁′y₁)(x₀′ + y₀′) = (x₁′y₁′x₀y₀) + (x₁y₁x₀y₀) + (x₁y₁′x₀′) + (x₁′y₁x₀′) + (x₁y₁′y₀′) + (x₁′y₁y₀′)

You can see that the SOP (sum of products) representation can get ugly very quickly.