Implementing a Divider Circuit - A Guide

[EvLer]

How can i implement a divider circuit?
we have covered adders and multipliers, but I'm not sure how to implement a divider... i know from programming that i would be shifting to the opposite side of multiplication, but... how...?
basically i need to divide the result (a sum of binary digits for which i have a series of adders) by 4 (taking average of 4 3-bit wide binary strings)

 

[berkeman]

Divide by 4 is easy, it's just a right shift by 2 bits. Divide by 7 or other non-binary numbers would require a K-map optimization.

 

[EvLer]

in multiplication circuit, in my notes, they also take into account the carry-bit, but is it necessary in division, i don't see the need for the carry (in/out) bit. It seems to work out fine w/t carry, but in my case i divide by 4 only, so would i have to care about carry bit for general case?

 

[Kenneth Mann]

Multiplying and dividing in binary is, in general, done in the same way that we learned to do it in the third (or whatever) grade. The only difference is the fact that we don't have to remember any lengthy multiplication tables. Otherwise, it is the same. Look at what you learned those years ago and apply the same to binary. To multiply, we continually add values (when multiplying by "1", otherwise ignore it) then shift (right to left) and repeat it. If you are dividing, subtract then shift (left to right), and repeat until finished. Obviously we have to use the carry, because we are adding (or subtracting). [If you have hardware "subtractors" you need to use a borrow; otherwise you just 'complement and add'.]

Just FYI: The above is the way we normally multiply (and divide) in software. Some processors and controllers also have 'microinstructions' to do it this way. The drawback here is the fact that this process is slow; it involves a lot of sequential steps. For that reason, high-end processors generally have 'coprocessors' and the like, to do the operations faster. Here, we get back to multiplying by amounts wider than one bit at a time. It could be by four-bit 'nibbles', or eight-bit 'bytes' or whatever. This, however gets us back to having to know our multiplication tables again (in hex or whatever). This can be done with 'ROM' tables or hard logic - - - but the circuitry gets complex. We trade that for speed. As an example, if we wanted to map out a hardware circuit to multiply two four-bit nibbles (at a time), we would need to use eight, eight-term K-Maps (yes, you can make them that big). [Four output bits would be the product, and four would be the carry.] Then, we would need what is essentially a new two-level adder, because the carry is wider.

KM

 

[EvLer]

thanks for explanation and some extra info!
fortunately all we had to do is to omit 2 LSBs, which meant they did not expect us to implement a general case of division.