Euclid$$s Algorithm

Euclid$$s algorithm is an efficient method for computing the greatest common divisor $($GCD$).$

It is named after the ancient Greek mathematician Euclid, who first described it in Books

VII and X of his Elements.

The GCD of two numbers is the largest number that divides both of them without leaving a

remainder. Euclid$$s algorithm is based on the principle that the greatest common divisor of

two numbers does not change if the smaller number is subtracted from the larger number.

For example, $21$ is the GCD of $252$ and $105(252=2112,105=215),$ which is the

same as the GCD of $147$ and $105,$ since $252-105=147.$ Since the larger number is reduced,

repeating this process gives successively smaller numbers until one of them is zero. When

that occurs, the GCD is the remaining nonzero number.

For instance, consider the inputs x $=66$ and y $=30.$

x $=66$

y $=30$

x $>$ y so

x $=$ x $-$ y $=66-30=36$

x $>$ y so

x $=$ x $-$ y $=36-30=6$

y $>$ x so

y $=$ y $-$ x $=30-6=24$

y $>$ x so

y $=$ y $-$ x $=24-6=18$

y $>$ x so

y $=$ y $-$ x $=18-6=12$

y $>$ x so

EE $2301,$ Fall $242$

y $=$ y $-$ x $=12-6=6$

x $>=$ y so

x $=$ x $-$ y $=6-6=0$

now

x $=0$

y $=6$

so GCD of $66$ and $30$ is $6$

Problem

You$$ll be working with $8-$bit integers X $=$ X$0,...$ X$7$ and Y $=$ Y$0,...,$ Y$7.$

$1.$ Design a comparator unit. Given input bits Xi

$,$ Yi

$,$ Ain and Bin, it produces outputs

Aout and Bout such that:

$$ If Ain $=0$ or Bin $=0,$ then Aout $=$ Ain and Bout $=$ Bin.

Otherwise

$$ If Xin $=$ Yin, Aout $=0,$ Bout $=0.$

$$ If Xin $>$ Yin, Aout $=1,$ Bout $=0.$

$$ If Xin $<$ Yin, Aout $=0,$ Bout $=1.$

Produce a full design with logic gates.

$2.$ Using your comparator units, design a full comparator. Given $8-$bit inputs X and

Y $,$ it produces outputs A and B such that:

$$ If X $=$ Y $,$ A $=0,$ B $=0.$

$$ If X $>$ Y $,$ A $=1,$ B $=0.$

$$ If X $<$ Y $,$ A $=0,$ B $=1.$

$3.$ Design an $8-$bit conditional subtractor unit. Given inputs X $=$ X$0,...$ X$7$ and Y $=$

Y$0,...,$ Y$7,$ A and B$,$ it produces outputs Z $=$ Z$0,...,$ Z$7$ such that

$$ If A $=0,$ B $=1,$ Z $=$ Y $$ X$.$

$$ Else, Z $=$ X $$ Y $.$

Use full adders and logic gates.

$4.$ Now design a full circuit that implements Euclid$$s algorithm. Have the circuit load

X and Y when a Load signal is set to $1$; have the computation begin when the Load

signal is set to $0$; have the circuit set a Done signal when the computation is complete;

have it produce an output Z equal to the GCD of X and Y when the Done signal is

set.

EE $2301,$ Fall $243$

Your solution must be specified down the level of logic gates and D flip$-$flops. $($Of course,

you are encouraged to first specify how to build small boxes, such as half and full$-$adders;

then combine these into large boxes; then those into even larger boxes.$)$

You are encouraged to code up your solution in Verilog and test it with Vivado. Simulate

your circuit for at least three pairs of input values, including $66$ and $30.$

For a problem like this, you must explain and annotate your circuit schematics, as well as

your simulation results. The grading will be somewhat subjective. If the grader cannot

understand your scribbles, you will not get full points, even if you can argue afterwards

that the circuit works.

Note that much of the challenge of this problem is the iterative nature. The circuit first

computes a set of outputs, then uses these as a new set of input values, and so on$.$ You

must include circuitry for starting the computation, i$.$e$.,$ loading initial values of X and Y $,$

and stopping the calculation when the final value is present on Z