Boolean circuit - 4 bits divisible by 3

Question

I need to draw a circuit taking a number on 4 bits that will return 1 only if that number is divisible by 3.

My initial steps were to draw a truth table from which I got a Boolean expression that cannot be simplified. I then drawn a Karnaugh Map, same result. It seems as though such Boolean expression would be really annoying to draw as is, I'm pretty sure they're an easier way.

My second thought was to use 4 "1 bit adder" in series, outputting the alternating sums; the last sum must be 0 in order to be divisible by 3. How would that work exactly? Would I need to carry the result of the addition even though it is pretty irrelevant to the whole circuit?

Answer 1

General approach for \$m\$ bits

The general solution for a test for division by 3 is to sum up the even-numbered bits and separately sum up the odd-numbered bits, take the difference between these sums, and then see if the difference itself is divisible by 3. (There are a variety of approaches for this operation, but the one encountered first is usually via carry-save adders.)

For a binary value with \$m\$ bits, where \$m\$ is even, the difference will require at most \$\lceil\operatorname{ln}_2\frac{m}{2}\rceil\$ bits. For a binary value with \$m\$ bits, where \$m\$ is odd, the difference will require at most \$\lceil\operatorname{ln}_2\frac{m+1}{2}\rceil\$ bits. This difference result could itself then be submitted to a much smaller tier for, once again, computing the difference between the sums of even and odd numbered bits. (And repeat.)

---

Specific case where \$m=4\$

At this point it is pretty easy to see that the even and odd sums can be computed using a simple half-adder, each. The resulting table is:

$$ \begin{smallmatrix}\begin{array}{r|cccc} &\overline{C_\text{odd}}\:\overline{S_\text{odd}}&\overline{C_\text{odd}}\:S_\text{odd}&C_\text{odd}\:\overline{S_\text{odd}}\\ \hline \overline{C_\text{even}}\:\overline{S_\text{even}}&Y&N&N\\ \overline{C_\text{even}}\:S_\text{even}&N&Y&N\\ C_\text{even}\:\overline{S_\text{even}}&N&N&Y \end{array}\end{smallmatrix} $$

In this case, there is no need to worry about "divisibility by 3" of the difference. Instead, it's sufficient to compare the two sums for "equal," as shown in the above table.

This should be very easy to implement:

^{simulate this circuit – Schematic created using CircuitLab}

The half-adders are easily recognized above. In addition, their associated outputs are directly compared using a pair of XORs. The results of these two comparisons are then considered using a NOR for the final output.

Answer 2

The other answers are just brute-forcing the answer by writing all the true cases. It will get much more complex the more bits you add (approximately doubles the amount of cases every bit).

Alternatively, you could think of it as a modulo cycle

0->1->2->0

The first bit, if true adds 1, therefore moves it right by 1

The second adds 2. (+2 / -1)

Continuing this, you have

|bit|num|mod|
| 1 | 1 |+1 |
| 2 | 2 |-1 |
| 3 | 4 |+1 |
| 4 | 8 |-1 |

So, you have the answer as

A-B+C-D=0

or

A+C=B+D

This solution is much easier to expand to an arbitrary amount of input bits.

Answer 3

Your function can be easily written as a sum of products notation:

$$F(A,B,C,D) = \Sigma(0,3,6,9,12,15)$$

Such a representation is trivially converted to a MUX implementation, which I assume you are allowed to use (as you mention using adders). Just connect all of the inputs corresponding to the listed numbers to logical 1, and the others to 0:

^{simulate this circuit – Schematic created using CircuitLab}

Answer 4

I cannot come up with anything else but the boolean expression $$ \bar{A}\bar{B}\bar{C}\bar{D} + AB\bar{C}\bar{D} + \bar{A}BC\bar{D} + \bar{A}\bar{B}CD + A\bar{B}\bar{C}D + ABCD $$

This implementation requires 12 AND, 6 NAND and 5 OR Gates. Don't think that's too complicated to build. The good thing is that it linearly scales with the input size as in case of modulo 3 you can compute it bytewise. So for a 8 Bit number you'd need twice the amount of gates altough your input range has been multiplied by 16.

Answer 5

A 4 bit number divisible by 3 implementation is pretty simple. I found a direct way as shown in the image:

I used 2 XOR gates and 1 XNOR gate.