Electronic – 4-bit decrementer using four Half Adders

Summary of Understanding

I had originally misunderstood your question and attempted to help you find a way to add combinatorial logic to a set of FFs that held a prior state. I then analyzed that circumstance without bothering to include the low-order FF situation, as that was too easy.

Now that I follow your question better and understand it to be a merely combinatorial one of subtracting one using only half-adders, it really doesn't change my answer much. However, I've since edited in the necessary tables for all four wires. It still includes all that is necessary for FFs (because I feel there may be a benefit for others to keep it here.) But when reading below, all you need to do is to focus on the D excitation columns. That's sufficient to get the combinatorial job done.

Excitation Table

Excitation tables often used to work out the combinatorial logic needed to transition a set of FFs holding the current state into the next desired state for some arbitrary (usually circular) sequential series of states. They aren't hard to make, though they may take a little persistence. Once produced, they are usually turned into k-maps for minimization purposes.

Most often, these tables are meant to help when using JK-type (JKFF), toggle-type (TFF), or D-type (DFF) flip flops. The JK-type has two inputs and the others have just one input. Their transitions are represented in the following table:

$$\begin{array}{c|c|c} \text{Transition} & \text{JK FF} & \text{T FF} & \text{D FF}\\\hline {\begin{smallmatrix}\begin{array}{c} \text{start }\to\text{ end}\\\\ 0 \quad \to \quad 0\\ 1 \quad \to \quad 1\\ 0 \quad \to \quad 1\\ 1 \quad \to \quad 0 \end{array}\end{smallmatrix}} & {\begin{smallmatrix}\begin{array}{cc} J & K \\\\ 0&x\\ x&0\\ 1&x\\ x&1 \end{array}\end{smallmatrix}} & {\begin{smallmatrix}\begin{array}{c} T\\\\ 0\\ 0\\ 1\\ 1 \end{array}\end{smallmatrix}} & {\begin{smallmatrix}\begin{array}{c} D\\\\ 0\\ 1\\ 1\\ 0 \end{array}\end{smallmatrix}} \end{array}$$

(Obviously, the DFF just wants the next state fed to its input.)

In your case, you want the last column above -- the one for the D FF. I know you aren't using flip flops, at all. You just want the combinatorial minimization to produce the next state (the current state minus one.) But that's just the D FF column. So please don't be overwhelmed by the following table, which includes excitations for all three flip flop types. I'm just doing it for completeness.

A subtraction (or down-counter) excitation table is as follows:

$$\begin{array}{c|c} \text{States} & \text{Excitations}\\\hline\\ {\begin{smallmatrix}\begin{array}{cccc} Q_D & Q_C & Q_B & Q_A\\ \vphantom{\left.\overbrace{\begin{array}{ccc}J & K & T & D\end{array} } \right.}\\ 0&0&0&0\\ 1&1&1&1\\ 1&1&1&0\\ 1&1&0&1\\ 1&1&0&0\\ 1&0&1&1\\ 1&0&1&0\\ 1&0&0&1\\ 1&0&0&0\\ 0&1&1&1\\ 0&1&1&0\\ 0&1&0&1\\ 0&1&0&0\\ 0&0&1&1\\ 0&0&1&0\\ 0&0&0&1 \end{array}\end{smallmatrix}} & {\begin{smallmatrix}\begin{array}{cccc} Q_D & Q_C & Q_B & Q_A\\ \left.\overbrace{\begin{array}{cccc}J & K & T & D\\ 1&x&1&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0 \end{array} } \right. & \left.\overbrace{\begin{array}{cccc}J & K & T & D\\ 1&x&1&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0\\ 1&x&1&1\\ x&0&0&1\\ x&0&0&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 0&x&0&0\\ 0&x&0&0 \end{array} } \right. & \left.\overbrace{\begin{array}{cccc}J & K & T & D\\ 1&x&1&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 1&x&1&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 1&x&1&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0\\ 1&x&1&1\\ x&0&0&1\\ x&1&1&0\\ 0&x&0&0 \end{array} } \right. & \left.\overbrace{\begin{array}{cccc}J & K & T & D\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0\\ 1&x&1&1\\ x&1&1&0 \end{array} } \right. \end{array}\end{smallmatrix}} \end{array}$$

K-Maps

Next, you turn the above excitation table columns into k-maps. (It's often easier to minimize the required logic when in this form.)

Again, for completeness, I'm providing all of them. But there's no need to worry -- just refer to the k-maps related to the DFF. (One fourth of the following maps, as shown all nicely boxed up for you. Just ignore the others for your case.)

$$\begin{array}{rl} \begin{smallmatrix}\begin{array}{r|cccc} Q_D\text{ }J&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C &0&0&0&0\\ Q_D\: Q_C &x&x&x&x\\ Q_D\:\overline{Q_C} &x&x&x&x \end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cccc} Q_D\text{ }K&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&x&x&x&x\\ \overline{Q_D}\:Q_C&x&x&x&x\\ Q_D\: Q_C&0&0&0&0\\ Q_D\:\overline{Q_C}&1&0&0&0 \end{array}\end{smallmatrix}\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_D\text{ }T&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C&0&0&0&0\\ Q_D\: Q_C&0&0&0&0\\ Q_D\:\overline{Q_C}&1&0&0&0 \end{array}\end{smallmatrix} & \boxed{ \begin{smallmatrix}\begin{array}{r|cccc} Q_D\text{ }D&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C&0&0&0&0\\ Q_D\: Q_C&1&1&1&1\\ Q_D\:\overline{Q_C}&0&1&1&1 \end{array}\end{smallmatrix} }\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_C\text{ }J&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C&x&x&x&x\\ Q_D\: Q_C&x&x&x&x\\ Q_D\:\overline{Q_C}&1&0&0&0 \end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cccc} Q_C\text{ }K&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&x&x&x&x\\ \overline{Q_D}\:Q_C&1&0&0&0\\ Q_D\: Q_C&1&0&0&0\\ Q_D\:\overline{Q_C}&x&x&x&x \end{array}\end{smallmatrix}\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_C\text{ }T&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C&1&0&0&0\\ Q_D\: Q_C&1&0&0&0\\ Q_D\:\overline{Q_C}&1&0&0&0 \end{array}\end{smallmatrix} & \boxed{ \begin{smallmatrix}\begin{array}{r|cccc} Q_C\text{ }D&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&0\\ \overline{Q_D}\:Q_C&0&1&1&1\\ Q_D\: Q_C&0&1&1&1\\ Q_D\:\overline{Q_C}&1&0&0&0 \end{array}\end{smallmatrix} }\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_B\text{ }J&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&x&x\\ \overline{Q_D}\:Q_C&1&0&x&x\\ Q_D\: Q_C&1&0&x&x\\ Q_D\:\overline{Q_C}&1&0&x&x \end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cccc} Q_B\text{ }K&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&x&x&0&1\\ \overline{Q_D}\:Q_C&x&x&0&1\\ Q_D\: Q_C&x&x&0&1\\ Q_D\:\overline{Q_C}&x&x&0&1 \end{array}\end{smallmatrix}\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_B\text{ }T&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&1\\ \overline{Q_D}\:Q_C&1&0&0&1\\ Q_D\: Q_C&1&0&0&1\\ Q_D\:\overline{Q_C}&1&0&0&1 \end{array}\end{smallmatrix} & \boxed{ \begin{smallmatrix}\begin{array}{r|cccc} Q_B\text{ }D&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&1&0\\ \overline{Q_D}\:Q_C&1&0&1&0\\ Q_D\: Q_C&1&0&1&0\\ Q_D\:\overline{Q_C}&1&0&1&0 \end{array}\end{smallmatrix} }\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_A\text{ }J&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&x&x&1\\ \overline{Q_D}\:Q_C&1&x&x&1\\ Q_D\: Q_C&1&x&x&1\\ Q_D\:\overline{Q_C}&1&x&x&1 \end{array}\end{smallmatrix} & \begin{smallmatrix}\begin{array}{r|cccc} Q_A\text{ }K&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&x&1&1&x\\ \overline{Q_D}\:Q_C&x&1&1&x\\ Q_D\: Q_C&x&1&1&x\\ Q_D\:\overline{Q_C}&x&1&1&x \end{array}\end{smallmatrix}\\\\ \begin{smallmatrix}\begin{array}{r|cccc} Q_A\text{ }T&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&1&1&1\\ \overline{Q_D}\:Q_C&1&1&1&1\\ Q_D\: Q_C&1&1&1&1\\ Q_D\:\overline{Q_C}&1&1&1&1 \end{array}\end{smallmatrix} & \boxed{ \begin{smallmatrix}\begin{array}{r|cccc} Q_A\text{ }D&\overline{Q_B}\:\overline{Q_A}&\overline{Q_B}\: Q_A&Q_B \:Q_A&Q_B \:\overline{Q_A}\\ \hline \overline{Q_D}\:\overline{Q_C}&1&0&0&1\\ \overline{Q_D}\:Q_C&1&0&0&1\\ Q_D\: Q_C&1&0&0&1\\ Q_D\:\overline{Q_C}&1&0&0&1 \end{array}\end{smallmatrix} } \end{array}$$

If \$X\$ is your input and \$Y\$ is your output and you only want combinatorial logic then below find your resulting logic. I've attempted to keep this as close as possible to using XOR and AND gates so that you can better examine your question:

$$\begin{align*} Y_A&=\overline{X_A}\\\\ Y_B&=\overline{X_A}\oplus X_B\\\\ Y_C&=\left(\overline{X_A}\cdot \overline{X_B}\right)\oplus X_C\\\\ Y_D&=\left(\overline{X_A}\cdot \overline{X_B}\cdot \overline{X_C}\right)\oplus X_D \end{align*}$$

Assuming only 2-input devices, this can be done with three XORs, two ANDs, and three NOTs. I'm not sure how you'd achieve it with only four HA sections.

The Half-Adder Solution

Well, as I said above, I don't know how you achieve the logic with only four HA sections. That said, I do know how to do it with four special HA sections. Let's call these HA' sections.

Note that these are probably no more complex than an HA. But they are slightly different, just the same. If you use these special kinds, then you can do it with just four of them. Just like you asked.

By the way, if you get rid of the superfluous stuff, the above simplifies to:

Which as I said requires three XORs, two ANDs, and three NOTs.

Summary

That's the entire process. You can almost write crazy-simple software to generate all this for you, in fact. Just type in a series of bit patterns of the same bit-width, let the software generate the excitation table, then the k-maps from that, and then simply print those out for you. (You could select which you want: JKFF, TFF, or DFF.) Once those are printed out, you'd just use your imagination to work out the optimal logic (or ask Espresso to do the work for you, added as a library to your code.) Then it is just a piece of cake. You just enter the values, press the bake button, and out comes minimized logic for you.

It's too easy. In fact, I think I'll just go and write something that does all this and then generates all the needed Latex that this site supports so I can almost auto-generate most of the answer for future questions like this.