Hi, please help me with this question, i'm preparing for my final here.

1. Euclids Algorithm Euclids 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. Euclids 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 = 21 12, 105 = 21 5), 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 = 36 - 6 = 30

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

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 Youll be working with 8-bit integers X = X0, . . . X7 and Y = Y0, . . . , Y7.

(a) Design a comparator unit. Given input bits Xi , Yi , Ain and Bin, it produces outputs Aout and Bout such that: If Ain 6= 0 or Bin 6= 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.

(b) 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.

(c) Design an 8-bit conditional subtractor unit. Given inputs X = X0, . . . X7 and Y = Y0, . . . , Y7, A and B, it produces outputs Z = Z0, ..., Z7 such that If A = 0, B = 1, Z = Y X. Else, Z = X Y . Use full adders and logic gates.

(d) Now design a full circuit that implements Euclids 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.