Electronic – Need help with RTL (Register Transfer Level) circuit implementation – Euclidian GCD algorithm

designdigital-logic

I'm looking for help regarding the following algorithm and implementing the logic circuit. Here it is in pseudocode:

if b = 0
    swap values of a and b.  b has the GCD. done. 
if a = 0
    b has the GCD. done.
if a < b
    swap values of a and b.

Loop: a = a - b
    if a >= b
        go back to Loop.
    if a > 0
        swap values of a and b
        go back to Loop

b has the GCD. done.

I've written some RTL code and it doesn't seem to be an issue; the real issue is my circuit design!

I suppose one would use a shift-subtract division implementation? I suppose I really just need help deciding what registers and arithmetic chips I'd use. Going to use Logisim.

Best Answer

Because this algorithm involves a loop, it will be much easier to implement in a microcontroller or microprocessor than in digital logic.

However, if you have some good reason to do it in digital logic, like you need absolute control over the speed of the implementation, or you want to have dozens or hundreds of processors executing the algorithm in parallel, it can of course be done in digital logic.

Rather than use individually packaged "registers and arithmetic chips" it would be much preferable to use a programmable logic device. Most likely you'd use an FPGA; but a CPLD would also be possible, particularly with the new CPLD families that are really small FPGA's in disguise.

If you use an FPGA, you'll simply use a synthesis tool to convert your RTL code into a configuration file for the device. You'll load the configuration file into the device and it will begin operation.

There's no need to translate the RTL to the gate level manually --- it's done for you by the synthesis tool.

Related Topic