3:2 Compressor

In the world of high-speed digital computation, one of the most persistent bottlenecks is a concept we learn in elementary school: the carry. When adding large numbers, each column must often wait for a carry-in from the previous one, a sequential process called carry propagation that imposes a "time tax" on every operation. This raises a critical question for computer architects: how can we perform addition at incredible speeds without being chained to this slow, rippling dependency? The answer lies not in eliminating the carry, but in cleverly postponing it using a fundamental building block known as the 3:2 compressor.

This article explores the elegant strategy behind this essential circuit. In the first section, ​​Principles and Mechanisms​​, we will dissect the 3:2 compressor, revealing its identity as a full adder and explaining how it forms the basis of Carry-Save Adders and Wallace Trees. Following that, the ​​Applications and Interdisciplinary Connections​​ section will demonstrate how this simple component is scaled up to build high-speed multipliers and parallel counters, highlighting its connections to fields like computational complexity and signal processing.

To truly appreciate the genius behind modern high-speed computation, we must first confront a surprisingly familiar villain: the humble "carry." Think back to how you learned to add numbers in school. To compute $158 + 273$, you start on the right. $8 + 3$ is $11$. You write down the $1$ and carry a $1$ over to the tens column. Then you add $1 + 5 + 7$, which is $13$. You write down the $3$ and carry another $1$ to the hundreds column. Finally, you add $1 + 1 + 2$ to get $4$. The final answer is $431$.

This process feels natural, but notice a crucial dependency: you cannot solve the tens column until you know the carry from the ones column. You can't solve the hundreds column until the tens column is finished. This sequential dependency, where each step must wait for the one before it, is called ​​carry propagation​​. In the world of digital circuits, where time is measured in nanoseconds, this waiting is a form of tyranny. A simple circuit that mimics this method, a ​​Ripple-Carry Adder​​, becomes agonizingly slow for adding large numbers, as the carry signal must "ripple" across the entire length of the numbers, from the least significant bit to the most significant. The challenge, then, is to perform addition without paying this time tax. How can we possibly add numbers without waiting for the carry?

The solution is a piece of intellectual jujitsu. Instead of trying to eliminate the carry, we simply decide not to deal with it—at least, not right away. This is the central idea behind the ​​3:2 compressor​​, a fundamental building block of fast arithmetic circuits.

Imagine you have not two, but three numbers to add together. The conventional approach would be to add the first two, wait for the result, and then add the third number to that sum. This involves two sequential, time-consuming carry-propagation steps.

The 3:2 compressor offers a radical alternative. It takes three input bits from the same column (let's call them $X$, $Y$, and $Z$) and, in a single, swift operation, "compresses" them into two output bits. One output bit, the ​​sum bit ($S$)​​, has the same place value as the inputs. The other output bit, the ​​carry bit ($C$)​​, has the next higher place value. We have effectively taken three bits and turned them into two, hence the name ​​3:2 compressor​​. The critical insight is that this compression happens for each column independently and simultaneously. There is no waiting, no rippling. We are not producing a final answer, but rather postponing the difficult part by reducing the number of things we need to add. This distinction is the secret to its speed. The slow, horizontal chain of carry propagation in a traditional adder is replaced by a vertical "rain" of carry bits that are simply handled in the next stage of computation.

So what is this magical device that performs a 3:2 compression? It’s something you may already know by another name: a ​​full adder​​. A full adder is a simple digital logic circuit designed to add three single bits ($X$, $Y$, $Z$). It produces two outputs, a sum ($S$) and a carry ($C$), that satisfy the basic arithmetic equation:

$X + Y + Z = 2C + S$

Let's look under the hood. The logic is beautifully simple. The sum bit $S$ is 1 if an odd number of inputs are 1. This is precisely what the XOR (exclusive OR) operation does. So, the Boolean expression for the sum is:

$S = X \oplus Y \oplus Z$

The carry bit $C$ is 1 if two or more of the inputs are 1. The most direct way to express this in Boolean logic is:

$C = (X \text{ AND } Y) \text{ OR } (Y \text{ AND } Z) \text{ OR } (X \text{ AND } Z)$

In more common notation, this is written as $C = XY + YZ + XZ$. This circuit is built from a handful of basic logic gates and is incredibly fast because the signals travel through only a few layers of logic. It takes three inputs and, without any need for information from other columns, produces its two outputs. It is the perfect engine for our "postponement" strategy.

A single 3:2 compressor works on one column of bits. But what if we want to add three large binary numbers, each with many bits? We simply line up a series of these 3:2 compressors (full adders), one for each column. This bank of parallel full adders is known as a ​​Carry-Save Adder (CSA)​​.

Imagine we have three 8-bit numbers to add: $A$, $B$, and $C$. A CSA takes these three numbers as input. For each bit position $i$, from 0 to 7, a separate full adder takes the bits $a_i$, $b_i$, and $c_i$ and produces a sum bit $s_i$ and a carry bit $c_{i+1}$. All the sum bits ($s_0, s_1, ..., s_7$) are collected to form a new number we can call the "Sum Vector". All the carry bits ($c_1, c_2, ..., c_8$) are collected to form the "Carry Vector".

Notice what happened. The carry-out from the adder at position $i$ ($c_{i+1}$) does not go into the adder at position $i+1$. Instead, it is simply placed into the $(i+1)$-th position of our Carry Vector. We have "saved" the carries instead of propagating them. In one swift, parallel step, we have reduced the problem of adding three numbers into the simpler problem of adding two numbers (the Sum Vector and the Carry Vector). We have successfully dodged the tyranny of the carry, at least for one stage.

This powerful reduction technique finds its ultimate expression in applications like high-speed multiplication. When you multiply two N-bit numbers, you generate N "partial products," which must all be added together. For an 8x8 multiplication, you have 8 numbers to sum. How can our 3:2 compressor help here?

We can apply our Carry-Save Adder technique repeatedly in a structure known as a ​​Wallace Tree​​. The strategy is simple: as long as you have three or more numbers (or rows of bits) to add, take three of them, run them through a CSA, and replace them with the resulting two (the sum and carry vectors).

Let's trace this reduction for a single, tall column of bits, perhaps one from the middle of a large multiplication problem. The goal is to reduce the number of operands (rows) from many down to two. Suppose a column starts with 11 bits to be added.

• ​​Stage 1:​​ We can group these 11 bits into three groups of 3, with 2 bits left over. The three groups go into three 3:2 compressors. After this stage, the number of bits to be added in the column is reduced from 11 to 5 (3 sum bits + 2 leftover bits).
• ​​Stage 2:​​ We now have 5 bits. We can make one group of 3, with 2 left over. One 3:2 compressor reduces the group of 3. Our column now has $1 + 2 = 3$ bits to sum.
• ​​Stage 3:​​ We have 3 bits. This is perfect for one last 3:2 compressor, which reduces them to a final sum bit and a final carry bit. These two bits become part of the two final numbers that will be added together.

The number of rows in our column has followed the sequence: $11 \rightarrow 5 \rightarrow 3 \rightarrow 2$. This rapid, logarithmic reduction in complexity is the source of the Wallace Tree's incredible speed. The entire matrix of partial products is compressed in this way, stage by stage. After just a few layers of these parallel compressions, the initial mountain of N partial products is reduced to just two numbers. Only then, at the very end, do we finally pay the piper and use a conventional (but highly optimized) adder to sum these last two numbers and produce the final result. The strategy is complete: we have confined the slow, sequential process of carry propagation to a single, final step, performing the vast majority of the work in a massively parallel, carry-free fashion. The humble 3:2 compressor, by cleverly saving the carry, makes this entire beautiful architecture possible.

After our deep dive into the principles of the 3:2 compressor, you might be left with a feeling similar to that of a child who has just been shown how a simple gear works. It's neat, it's clever, but what can you do with it? What grand machines can be built from this humble component? It turns out that the 3:2 compressor, this simple circuit that tidies up three bits into two, is not just a minor curiosity. It is the fundamental cog in the machinery of high-speed computation, a beautiful example of how a simple, elegant idea can be scaled up to solve monumental problems. Its applications stretch from the heart of every computer processor to the frontiers of computational science.

Let’s begin with one of the most fundamental tasks a computer performs: multiplication. If you multiply two large numbers using the schoolbook method, you create a whole series of intermediate numbers, or "partial products," that you then have to painstakingly add up. For a computer, this means adding a large pile of binary numbers. A naïve approach would be to add them two at a time, a slow and sequential process. This is like a juggler trying to handle a dozen balls by catching and throwing only one pair at a time. It’s clumsy and inefficient.

The 3:2 compressor offers a much more elegant solution. Instead of adding two numbers and waiting for the carries to propagate all the way across, we can use a bank of compressors to tackle the problem in parallel. This technique is called Carry-Save Addition (CSA). Imagine you have three numbers to add. Instead of adding the first two and then adding the third to their sum, a CSA layer—which is just a row of independent 3:2 compressors—takes all three numbers at once. For each column of digits, a compressor takes the three corresponding bits and, without conferring with its neighbors, produces a sum bit for that column and a carry bit for the next column over.

After one pass, you are left not with a single sum but with two new numbers: a "Sum vector," made of all the sum bits, and a "Carry vector," made of all the carry bits (shifted one position to the left, of course). You started with three numbers and, in a single, swift step, you have reduced the problem to adding just two. The magic here is the postponement of pain. We don't resolve the carries immediately; we "save" them into their own number and deal with them later.

This is a powerful trick, and it doesn't have to stop there. What if we start with more than three numbers, say, four? Simple. We use one layer of compressors to reduce the first three numbers to two. Now we have a total of three numbers again (the two new ones plus the one we left aside). We can then use a second layer of compressors to reduce these three down to a final pair. This leads to a beautiful, tree-like reduction scheme known as a ​​Wallace Tree​​.

Starting with a large pile of partial products—say, six of them—we can organize our compressors into stages. The first stage takes the six numbers, groups them into two sets of three, and reduces each set to two numbers. In one swift step, we’ve gone from six numbers to four. The next stage takes these four, reduces three of them to two, leaving one untouched. Now we have three numbers. One final stage reduces these three to our desired two. This cascade of 3-to-2 reductions is breathtakingly efficient. The number of stages required grows only logarithmically with the number of initial operands, a monumental leap in performance over linear, sequential addition. At the very end of this parallel reduction, we are left with just two numbers that must be added, a task for a more conventional, but now much less burdened, adder.

It's tempting to think of the 3:2 compressor solely in the context of arithmetic, but that would be missing a deeper truth. What does a full adder, our 3:2 compressor, really do? It takes three binary inputs and produces a two-bit binary output that represents the count of how many of its inputs were '1'. If zero inputs are '1', the output is 00. If one is '1', the output is 01. If two are '1', the output is 10. And if all three are '1', the output is 11. It is, in essence, a 1-bit, 3-input parallel counter.

This new perspective opens up a whole different world of applications. Imagine you have a stream of data arriving on many parallel wires, and you need to know, in an instant, how many of those wires are active. This is a common problem in signal processing, scientific instrumentation, and network data analysis. You can build a circuit to do this—a parallel counter—by wiring together a network of 3:2 compressors.

For instance, to count the number of '1's on seven input lines, you can build what's called a (7,3) counter, which produces a 3-bit binary output representing the count. You could start by feeding the seven inputs into two parallel compressors. This first level reduces the seven inputs into two sum bits and two carry bits (plus one original input left over). These resulting bits can then be fed into subsequent compressors until you are left with exactly three output bits representing the final count in binary: one bit for the 1s place, one for the 2s place, and one for the 4s place. The genius of this structure is that the speed of the count is not determined by the number of inputs, but by the number of compressor layers in the reduction tree—the critical path delay. A clever arrangement can produce the result in just a few gate delays, far faster than any sequential counting algorithm could hope for.

The principle of 3-to-2 reduction is the foundation, but in the relentless pursuit of performance, engineers rarely stop at the simplest implementation. If reducing three lines to two is good, might reducing more be even better? Absolutely. It is possible to build larger compressors from a network of 3:2 compressors. For example, a ​​4:2 compressor​​ takes four bits in a column (plus a carry-in from the next-lower-bit-position column) and reduces them to a single sum bit in the same column and two carry bits for the next column up.

Why bother? Because a single, more powerful compressor can reduce the height of a column of bits more aggressively. Consider a tall column in a partial product matrix, perhaps 11 bits high. Using our standard strategy, we would first use 3:2 compressors. A more advanced strategy might prioritize using as many 4:2 compressors as possible first. This allows for a more rapid reduction in the number of bits that need to be processed in the next stage, ultimately reducing the total number of stages required.

This leads to a fascinating trade-off. We can build even larger compressors, such as (7,3) counters that reduce seven bits to three, or even more exotic variants. Using these larger, more complex blocks can dramatically decrease the number of stages in a Wallace tree. For instance, reducing a column of 15 bits might take six stages using only 3:2 compressors, but only three stages if we strategically employ (7,3) compressors for the initial, taller stages. Fewer stages means a shallower logic depth and a much faster multiplier.

This brings us to the intersection of digital logic and ​​computational complexity theory​​. The size of a circuit, roughly the number of gates, tells us about its cost, while its depth, the longest chain of gates an input signal must pass through, tells us about its speed. For an $n$-bit multiplier, a simple schoolbook design has a size proportional to $n^2$ and a depth proportional to $n$. By using a Wallace tree of compressors, we keep the size at about $O(n^2)$ but can slash the depth of the reduction phase to $O(\log n)$. This asymptotic improvement is the difference between a calculation taking a few minutes or a few hours as the numbers get large. It is the theoretical underpinning that justifies the entire carry-save paradigm.

From the core of a CPU multiplying floating-point numbers to specialized hardware accelerating scientific simulations, the fingerprints of the 3:2 compressor are everywhere. It is a testament to the power of abstraction and parallelism—a simple rule, applied over and over, that allows us to tame an otherwise hopelessly complex calculation, turning a chaotic pile of numbers into an elegant and orderly result.