Published Mar 6th, 2012, 3/6/12 7:18 pm
- 2,429 views, 2 today
- 132 downloads, 0 today
34
Lately I've been exploring large division and multiplication circuitry using combinational logic, sequential logic, and a hybrid combinational/sequential approach.
Combinational logic refers to logic where the output is dependent solely on the input. This means that each step of the algorithm you're implementing in the circuit is wired. This results in a circuit that is fast, but large.
Sequential logic refers to logic where the output is dependent on both the current input and the history of the input. This means that the circuit has memory, resulting in a circuit that is compact, but not necessarily fast because you're saving the output after each step of the algorithm.
My approach to building large arithmetic circuits is to use a hybrid combinational/sequential approach to find a sort of midpoint (though thanks to insta-repeaters and insta-wire, it's not so much a midpoint as it is slightly slower than a purely combinational version would be).
This divider uses restoring division, meaning that in each iteration it subtracts the divisor from the dividend and based on whether the output is positive or negative it either outputs the difference (if positive) or the input you're subtracting from (if negative). The difference is then right-shifted and the process is repeated. For a 16 bit divider you need to do this 16 times. Now, onto the divider.
The divider I've built performs has 4 iterations wired combinationally and this circuit is run 4 times sequentially, for a total of 16 iterations. The schematic I've uploaded has a 38 tick clock, meaning the total run time is approximately 152 ticks. It may be possible to clock it faster without any issues, but I consider this a "safe" speed. Also, note the the schematic I've uploaded is *slightly* different than the screenshots because I did some rearranging to make it a little faster. If you're trying it out you should note that the dividend goes into the inputs beneath the shift register (the levers that are farthest back) and the divisor goes into the inputs that are bussed across the top of the entire circuit. I've marked the button that starts the clock with a sign on blue wool and the reset button is marked by a sign on red wool. Enjoy!
Combinational logic refers to logic where the output is dependent solely on the input. This means that each step of the algorithm you're implementing in the circuit is wired. This results in a circuit that is fast, but large.
Sequential logic refers to logic where the output is dependent on both the current input and the history of the input. This means that the circuit has memory, resulting in a circuit that is compact, but not necessarily fast because you're saving the output after each step of the algorithm.
My approach to building large arithmetic circuits is to use a hybrid combinational/sequential approach to find a sort of midpoint (though thanks to insta-repeaters and insta-wire, it's not so much a midpoint as it is slightly slower than a purely combinational version would be).
This divider uses restoring division, meaning that in each iteration it subtracts the divisor from the dividend and based on whether the output is positive or negative it either outputs the difference (if positive) or the input you're subtracting from (if negative). The difference is then right-shifted and the process is repeated. For a 16 bit divider you need to do this 16 times. Now, onto the divider.
The divider I've built performs has 4 iterations wired combinationally and this circuit is run 4 times sequentially, for a total of 16 iterations. The schematic I've uploaded has a 38 tick clock, meaning the total run time is approximately 152 ticks. It may be possible to clock it faster without any issues, but I consider this a "safe" speed. Also, note the the schematic I've uploaded is *slightly* different than the screenshots because I did some rearranging to make it a little faster. If you're trying it out you should note that the dividend goes into the inputs beneath the shift register (the levers that are farthest back) and the divisor goes into the inputs that are bussed across the top of the entire circuit. I've marked the button that starts the clock with a sign on blue wool and the reset button is marked by a sign on red wool. Enjoy!
Progress | 100% complete |
Tags |
tools/tracking
645191
2
16-bit-combinationalsequential-divider-rdf
Create an account or sign in to comment.
You are an Idol of the Redstone builder, all your projects are very clean and interesting; and you have a good mental apparatus which i think would help you build very large circuits.
I just hope you get more appreciation at the RDF then here at PMC.
Great Work !