How to compute a division operation on a basic adder/subtractor?

I can't remember how to do division or multiplication on an adder subtracter. Use of a shift unit is required I'm fairly certain. I am trying to solve this problem:


R8%26lt;- M[R28]/256 AND 0x00FF, assume logic AND is logic function 9.





This is a problem on a PRACTICE exam from last semester that my professor has given out for practice for my upcoming final.





Please explain the division process and if your feeling generous maybe an example of a multiplication operation. I don't actually need to see this particular problem solved I am truly concerned with performing multiplication and division on an arithmetic unit only capable of signed addition and subtraction.





Additional information: This is being done on a Single Cycle Datapath with triple bus internal architecture, with a 32x32bit register file. This datapath is similar but simpler than ones found in today's PCs.


32-bit datapath elements: Register File,


Arithemtic Unit, Logical Unit, and Shift UnitHow to compute a division operation on a basic adder/subtractor?
Yeah.. it's been awhile since I cracked my digital design book, but here is a good site that shows the algorithm very well:


http://courses.cs.vt.edu/~cs1104/Divisio鈥?/a>





I think you'll see how it is applicable to your architecture.How to compute a division operation on a basic adder/subtractor?
If you are dividing by a fixed decimal 256, that's just a right shift operation by 8 binary places... If that function is all you need to do, just copy the one register to another while mapping the bits so they are shifted by 8 places.





Multiplication and division, in their simplest forms, are iterative processes similar to one another.





When you multiply numbers A x B, you take one of them, say A, and AND every bit with the LSB of the number B. Store the result in accumulator register. In the next cycle, you shift A one bit to the left, AND it with the next bit of the number B and add it to the accumulator. You continue this process until you get to MSB.





Division A/B is similar, but you start by shifting B by the maximum number of bits to the left and subtracting it from A. If the result is less than zero, you put 0 in the MSB, otherwise you take the reminder and subtract B, but shifted 1 bit to the right. The number of cycles is equal the number of bits in your result.





If you want speed, modern multipliers use pipelining and look-up blocks. It is also possible to simply combinatorially wire up the 32x32 mattrix to get you the result in a single cycle, but that's typically too much hardware for an operation that's not used often (unless you're building a DSP).

hidden myspace

internet explorer