How to use NAND gates to divide (5bit) binary inputs by an integer (say 5)

digital-logic

Trying to sketch up a circuit which will divide, say a 5-bit binary number by 5 to produce a 4-bit binary quotient.
We can assume that the input doesn't actually reach 31, instead it's limited to 30, or 25.

I'd like to use only 2 ~ 4 input NAND gates. The inputs A, B, C, D, and E will be available from toggle switches. Any solution which uses 22 or fewer gates and inverters (not counting
the five inverters for the inputs) is acceptable.

Best Answer

Since you are dividing by a constant this is a trivial 5-bit -> 4-bit (actually 5-bit -> 3-bit as @OlinLathrop points out) combinational circuit.

If you are feeling too lazy to work the 5-variable Karnaugh maps by hand then get yourself a copy of the Espresso heuristic logic minimizer. (If you google "espresso logic minimizer" you may be able to find a precompiled binary (prefer the ones from .edu sites.)

Type in the truth table and run it through the tool. It will probably give you the results in sum of products form. The conversion to nand gates with 4 or fewer inputs is a trivial exercise.