Combinatorial Division?

Frist a little bit of information before my question.  I don't know
where the best place is for this question.  I'm building a 64bit ALU
using standard TTL devices.  I made a 4bit adder with fast carry,
combined 4 of those with 16 AND gates (ends up as a 4x4=8bit
multiplier), and then combined 64 groups to provide 15 partial products
to a wallace tree (which I also had to make a model for).  A final
summing adder takes the two partial products from the wallace tree and
adds them together.  This final summing adder is built using 181 and
182  TTL devices, so I can also subtract and preform basic logic
operations if necessary.

I basically followed the datasheet from Texas Instruments from 1975.
;)  I had to make models of the 74274 and 74275 because they weren't
included as standard Altera macros I guess (which is very
understandable...  ;)  )

Anyway, my schematic program produces an EDIF netlist which I'm able to
import into Altera's software and compile and simulate my schematic for
their FPGA devices.  I've been simulating my project with great
success.  So we are on topic with the whole FPGA thing.  :)

Now on to my question.  Is there a simple combinatorial design for
division?  So far the whole schematic is made using "Combinatorial
logic"?  I'm not sure that's the right word.  The ALU can perform any
function without clock inputs, its also faster than a lot of the other
methods I've found.  For example, calculating one partial product at a
time for multiplication.

For more info on the multiplication circuit I've described you can look
at the datasheet below.  On page 7-398 through 7-400 is a schematic for
a 16x16 bit multiplier.  Mine is pretty much the same, except mine is
4x larger.  This is the first time I've used D size schematic layout.
:)  For more informatio

http://www.tech-systems-labs.com/booksdata/TI-DATA-1976.pdf

Any hints for what I should be looking for or links would be great.
Searching for combinatorial division I found what looked like to be
some good hits, but the website was in the CGI error mood.  :(

logjam wrote:
> Now on to my question.  Is there a simple combinatorial design for
> division?

No that I've ever heard of.  If there was, everyone would be using it.

All of the conventional division algorithms (hardware or software) are
sequential, producing one or more bits of result per cycle.  For one bit
per cycle, a simple shift-and-subtract method is easy.  Beyond that,
typically a small ROM is involved.

Some high-speed dividers work by instead multiplying by the reciprocal,
presumbaly because a high-speed reciprocal unit is a either easier to
build or faster than a high-speed divider.  But it still only gets you
a few bits of your result every cycle.

There are a lot of books on computer arithmetic, and a lot of published
papers.

"Eric Smith" <eric@brouhaha.com> wrote in message 
news:qhy80169ru.fsf@ruckus.brouhaha.com...
> logjam wrote:
>> Now on to my question.  Is there a simple combinatorial design for
>> division?
>
> No that I've ever heard of.  If there was, everyone would be using it.
>


Sure there is, one can do a division by cascading stages together without 
using registers and clock. However it a) is really, really, slow for 
propagation delay. And b) uses a lot of hardware (2 to 3 times as much as 
for multiplication). Since division is rarely used most designers seem to go 
with a clocked divider.


Why not use use the built in multiply operation of most HDL's ? One can 
usually code something like a = b * c, and it will generate an optimal 
design for any given architecture.

rob<remove>@birdcomputer.ca 

I want the ability to build the whole computer using TTL logic, but
also put it in an FGPA.  I'm learning VHDL as I go.  Since the code is
generated from my TTL schematic, I can test the giant circuit before I
produce a PCB and solder hundreds of chips.

Just a thought, but wouldn't the delay using cascading stages without a
clock take just as much time as if you used a clock?  Instead of using
the same stage over and over again its just duplicated?  I think what I
will do is use the 64bit ALU that supports subtraction and addition,
throw in two shift registers, and a state machine to control timing.

logjam wrote:
> I want the ability to build the whole computer using TTL logic, but
> also put it in an FGPA.  I'm learning VHDL as I go.  Since the code is
> generated from my TTL schematic, I can test the giant circuit before I
> produce a PCB and solder hundreds of chips.
>
> Just a thought, but wouldn't the delay using cascading stages without a
> clock take just as much time as if you used a clock?  Instead of using
> the same stage over and over again its just duplicated?  I think what I
> will do is use the 64bit ALU that supports subtraction and addition,
> throw in two shift registers, and a state machine to control timing.

The thing is though, that this method will use an exorbitant amount of
hardware. This will also result in a long path and will be very slow
due to propogation delay. On top of that it will depend on your logic
family, I believe the 74F series is the fastest? Anyway the TTL chips
will either be fairly slow or consume power like crazy. Given the
amount of chips you will need I wouldnt be surprised if the current
draw of your divider alone hit into the amp range.
A clocked division (using the shift and subtract method) is fairly
simple to implement in an FSM. Not only that you will be a bit a clock,
and all you need is a some registers, some combinatorial logic to
determine the next state and the D FF's to hold the current state. That
will be easier for you to solder and consume far less power too! A
remainder in a few clock cycles I think isnt too much of a compromise.

The whole ALU with multiplier will take around 2.5 amps.  :)

logjam wrote:
> The whole ALU with multiplier will take around 2.5 amps.  :)

WOW, ~13W ALU!!!

Why not use an FSM based divider?

Logjam, it is hard for a rader of this newsgroup to understand why you
are doing what you are doing.
Why a combinatorial divider, when division is a rare operation, and
sequential circuits are more efficient?
And why insist on a 30-year old technology?
If you had picked a 50-year old technology, you would use Germanium
transistors, diodes, resistors, and capacitors, and you would really
learn the very details of circuit design. (I did, it was fun while
there was nothing better available!)
Or a 20-year old technology, using AMD bit-slice (2900) chips?
Or a 10-year-old original FPGA technology (XC3000), where all logic is
implemented in LUTs and flip-flops?

If you absolutely want to make life tough for yourself, what is so
special about 1975-vintage circuits? Just nostalgia, and those lovely
yellow books?

Peter Alfke, Xilinx Applications
=======================
logjam wrote:
> Frist a little bit of information before my question.  I don't know
> where the best place is for this question.  I'm building a 64bit ALU
> using standard TTL devices.  I made a 4bit adder with fast carry,
> combined 4 of those with 16 AND gates (ends up as a 4x4=8bit
> multiplier), and then combined 64 groups to provide 15 partial products
> to a wallace tree (which I also had to make a model for).  A final
> summing adder takes the two partial products from the wallace tree and
> adds them together.  This final summing adder is built using 181 and
> 182  TTL devices, so I can also subtract and preform basic logic
> operations if necessary.
>
> I basically followed the datasheet from Texas Instruments from 1975.
> ;)  I had to make models of the 74274 and 74275 because they weren't
> included as standard Altera macros I guess (which is very
> understandable...  ;)  )
>
> Anyway, my schematic program produces an EDIF netlist which I'm able to
> import into Altera's software and compile and simulate my schematic for
> their FPGA devices.  I've been simulating my project with great
> success.  So we are on topic with the whole FPGA thing.  :)
>
> Now on to my question.  Is there a simple combinatorial design for
> division?  So far the whole schematic is made using "Combinatorial
> logic"?  I'm not sure that's the right word.  The ALU can perform any
> function without clock inputs, its also faster than a lot of the other
> methods I've found.  For example, calculating one partial product at a
> time for multiplication.
>
> For more info on the multiplication circuit I've described you can look
> at the datasheet below.  On page 7-398 through 7-400 is a schematic for
> a 16x16 bit multiplier.  Mine is pretty much the same, except mine is
> 4x larger.  This is the first time I've used D size schematic layout.
> :)  For more informatio
>
> http://www.tech-systems-labs.com/booksdata/TI-DATA-1976.pdf
>
> Any hints for what I should be looking for or links would be great.
> Searching for combinatorial division I found what looked like to be
> some good hits, but the website was in the CGI error mood.  :(

I want to do all sorts of things.  After this I want to build an 8bit
computer using transistors.  I saw one on the internet, but it didn't
look like it ran any decent software.

I have no idea if I will ever actually build it.  Right now I'm
learning a lot about FPGAs and binary math, so its worth it just for
that.  :)

I want a combinational multiplication circuit becase its a ton faster
than sequential as far as I've been able to figure out.  I don't mind
if the schematic contains tons of parts and takes up 1.5 square feet of
board.  ;)  But I'm not going to do division with that many parts.

I guess the reason I came up with 75 is because that's the year of the
Altair and other computers becoming "popular"?  It will be fun to see
what kind of computer I can design out of commonly available parts,
what it would have cost, and how fast it is.  So far my initial
calculations are 4-4.5 million 32x32bit multiplications per second.
That is pretty fast, comparable to a 50MHz 486.

For a while I wanted to build a computer out of relays, but I'm not
that brave yet.  That's a LOT of time.  :)

I've just completed the soldering on a 19,008 LED display.  Talk about
current, the thing draws 130A!  So, yes...I am crazy.  :)

http://www.stockly.com/images2/060129-LED_Display_Front_2718.jpg

http://www.stockly.com/images2/060129-LED_Display_Back_2716.jpg

On a sunny day (23 Feb 2006 19:27:04 -0800) it happened "Peter Alfke"
<alfke@sbcglobal.net> wrote in
<1140751624.632774.85380@u72g2000cwu.googlegroups.com>:
>
>If you absolutely want to make life tough for yourself, what is so
>special about 1975-vintage circuits? Just nostalgia, and those lovely
>yellow books?
>
>Peter Alfke, Xilinx Applications

Yes Peter, way to go, use the best of teh old and new technology:
 http://www.neoseeker.com/Articles/Hardware/Reviews/aopenax4btube/