I am trying to figure out how to create an efficient way to divide 5 bit numbers in hardware (using registers, Shift Registers, Comparators, Muxes, basic logic
gates, bit shifters, bit extenders, and Subtractors).
I know i can just iteratively subtract the divisor from the dividend until the result is less than the dividend but that takes an unknown number of clock ticks. I am looking for a way to have the entire division done in 6 clock ticks (assuming the above circuits all do their job on a single tick).
I am having trouble getting started because the only methods i come up with use a looping method.
Any advice on how to approach this problem is greatly appreciated.
Best Answer
A nice approach is to start with the dividend in a register whose width equals the combined widths of the divisor and intended quotient. Then repeatedly compare the upper portion of that register against the divisor. If it's greater than or equal, subtract the divisor and shift the register left, putting a "1" in the LSB. If it's less, shift left, putting a "0" in the LSB. Iterate that once for each bit of the quotient. The lower part of the dividend register will be left holding the quotient, while the upper part will be left holding the remainder.
Depending upon how exactly you do things, it may be necessary to handle the first or last iteration specially, but the above approach is pretty straightforward.