# Boolean circuit - 4 bits divisible by 3

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?

• This is an interesting question as perhaps I don't know the answer either. However, we can try to think about this, firstly, on a software perspective because at the end of the day, all software eventually leads to logic gates and 1's and 0's. I know for software, there exists a mathematical operation called, modulo, where you take value and find the remainder. So for instance, 6 mod 3 = 0 because if you divide 6 by 3, you get 2 but there's no remainder. But 5 mod 3 would be 2 because there's two left over. Hence if you say "NUMBER mod 3 = 0", it means the number is divisible by 3. – KingDuken Dec 18 '18 at 16:48
• Where I'm going with this is that it would be good if you could research how to implement modulo into logic design and see how it's done. I know with binary subtraction, it requires a binary adder (which seems contradictory but it's true!) – KingDuken Dec 18 '18 at 16:50
• It seems as though such Boolean expression would be really annoying to draw as is, I'm pretty sure they're an easier way. - No. Circuits are implementing functions. If you can't get simpler function, you won't get a simpler circuit. – Eugene Sh. Dec 18 '18 at 16:58
• Can you use a MUX? Then the ask is trivial. – Eugene Sh. Dec 18 '18 at 17:10

## 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.

• Just to remove a possible confusion one might have - this solution is equivalent to the one that is derived using the straightforward approach through truth table and Boolean algebra. It can be derived from the same truth table and formula by performing certain transformation to get the XOR and NOR operations. – Eugene Sh. Dec 18 '18 at 21:41
• Good expansion of my idea. I'm glad to see this resulted in a much more efficient answer than the brute force methods. – bxk21 Dec 18 '18 at 22:05
• @bxk21 As I said in my previous comment - it is not more efficient. It is the same. – Eugene Sh. Dec 18 '18 at 22:09
• @EugeneSh. This flows from a very powerful generalization towards an implementation that is easily understood in a specific case here. I think the "brute force" words used by bxk21 would be well understood by any mathematician. An infinite-input mux can be used to solve many problems. Of course. But it provides no insight about those problems. I think that's all that bxk21 meant. Your solution says nothing about understanding broader cases of this kind of problem. (Not that it needed to do so.) – jonk Dec 18 '18 at 22:21
• Don't know how I could have missed the pattern, but that's a really nice answer. Wondering if this is the way a modulo operation is implemented in an FPGA? – po.pe Dec 19 '18 at 7:52

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.

• It's not my background, so I don't really know how to write my answer as a boolean expression. If anyone wants to edit it in, feel free. – bxk21 Dec 18 '18 at 17:32
• I don't see what you are proposing. Is it a sequential circuit? – Eugene Sh. Dec 18 '18 at 17:33
• I guess it's not really a full answer right now. I'm just shortening the logic to a very simple check: A+C=B+D – bxk21 Dec 18 '18 at 17:36
• That's actually an interesting observation. Do you mind if I write another answer based on it? Update: actually I won't... it's more complicated than I though initially – Eugene Sh. Dec 18 '18 at 17:50
• @bxk21 Great observation. It generalizes as follows: "If the number of even bits minus the number of odd bits is a multiple of three then the number is divisible by three." – jonk Dec 18 '18 at 20:25

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

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.

• This misses two values: 0x0 and 0xC – DonFusili Dec 18 '18 at 17:03
• ... thanks for that! ... 0xC was there – po.pe Dec 18 '18 at 17:10
• I like this overview because it is close to my initial results and that'd be the most coherent solution to give at this time in my training. How would you go about designing such though? I tried to draw that but I am not sure how to optimize the drawing, is there a good resource I could read from? – InTheMoodForNow Dec 18 '18 at 17:40
• @Humpawumpa should I have tagged you here – InTheMoodForNow Dec 19 '18 at 8:31
• To me, the implementation suggested by jonk seems to be way more practical than mine. But if you like to implement it that way it depends on the size of your logic gates. Assuming you have 2-input gates just combine them pairwise e.g. if you start from the left it would be A and B to a NAND and C and D to a NAND and the two outputs combined with an AND. – po.pe Dec 19 '18 at 8:56

As with decimal numbers, if you add together all the individual digits and find that the sum is exactly divisible by 3 then the whole number was also exactly divisible by 3: -

351 (dec) is divisible by 3 because 3+5+1 = 9 and 9 is divisible by three.

For binary, split the 4 bit number into two 2-bit numbers i.e 12 (decimal) is 1100 (binary) and the addition of the two pieces is 11+00 = 11 = 3 (decimal). 6 (decimal) is 0110 (binary) and 01+10 = 3 (decimal).

Fifteen (decimal) is 1111 and 11+11 is 0110. This number is greater than 3 (6) and can be reduced again by adding 01 and 10 to produce 3.

If you tried this with (say) 7 (0111) the first add would be 100 and the 2nd add would be just 01 and this clearly doesn't equal 3. It's basic number theory.

• "If you divide by 2" - how this can be done by a simple circuit? This approach doesn't seem good to me. – Al Kepp Dec 18 '18 at 23:53
• @AlKepp Division by 2 is done by shifting to right. It can be done with wires only, not even gates. Yet this answer doesn't seem clear to me. – Eugene Sh. Dec 19 '18 at 0:43
• Guys, hopefully I've made this clearer so if the down-voter would reconsider their action that would be appreciated or, maybe further clarification is required? – Andy aka Dec 19 '18 at 8:09