1
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ 5 bit numbers? A lookup table. \$\endgroup\$ – Brian Drummond Feb 18 '15 at 23:19
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thanks for the reply! To elaborate, lets say my dividend is 10101 and divisor is 00110, and we want the quotient and remainder to always be five bits. We start out with the dividend in the leftmost or right most portion of a shift register? I assume you want it to be leftmost so the MSB of the shift register is the MSB of the dividen. So our shift register is 1010100000 (the left most 5 bits is the dividend and rightmost is the divisor). Then compare the divisor to the upper part (10101) of the register. If its greater or equal subtract the divisor (00110) from ONLY the upper part (10101). \$\endgroup\$ – user8363 Feb 18 '15 at 22:12
  • \$\begingroup\$ (continued) after you subtract the divisor from only the upper part we then move the result of the subtraction back into the upper part of the register (so it would now be 01111) back into the shift registers upper half and then left shift a 1 into the register so the register now looks like 111100001. Then continue until we have shifted 5 times? after all that is through the lower part has the quotient and upper part has the remainder? I feel like those should be switched (lower part has remainder and upper part has quotient). \$\endgroup\$ – user8363 Feb 18 '15 at 22:14
  • \$\begingroup\$ @user8363: If the value to be used as the dividend is shorter than the aforementioned register, it should be left padded with zeroes. The initial value of the shift register should be 00000 10101, so 00000 is the value to be compared against the divisor (it's less). Then 00001, 00010, and 000101. Finally, 01010 will be bigger than the divisor, so subtract and yield 00100. Shift that left (01001) and compare again. Still greater, so subtract (yielding 00011). As noted, first and last iteration may need tweaking, but that's the general idea. \$\endgroup\$ – supercat Feb 18 '15 at 22:19
  • \$\begingroup\$ @user8363: The bottom part of the dividend register is where the results of the comparison are getting placed, while the upper part is where the residue from the lower bits of the dividend will eventually end up. \$\endgroup\$ – supercat Feb 18 '15 at 22:21
  • \$\begingroup\$ So i am following up until you get a number greater than the divisor, then you subtract our the divisor from that number and shift that number left (with a 1 not a zero), where do you store that number? Since you aren't shifting the register anymore (you are shifting the result from subtraction). \$\endgroup\$ – user8363 Feb 18 '15 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.