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

   

Transcribed Image Text:

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 = 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 r = 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 y > x so - x = 30 - 6 = 24 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 You'll be working with 8-bit integers X = Xo,...X7 and Y = Yo,...,Y7. (a) Design a comparator unit. Given input bits Xi, Y;, Ain and Bin, it produces outputs Aout and Bout such that: • If Ain +0 or Bin + 0, then Agut = Ain and Bout = Bin- %3D Otherwise • If Xin = Yin, Aout = 0, Bout = 0. • If Xin > Yin, Aout = 1, Bout = 0. • If Xin < Yin, Aout = 0, Bout = 1. %3D 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. = Xo, ...X7 and (c) Design an 8-bit conditional subtractor unit. Given inputs X Y = Y,...,Y7, A and B, it produces outputs Z = Zo, ., Z7 such that • If A = 0, B = 1, Z = Y - X. • Else, Z = X - Y. Use full adders and logic gates. 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 = 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 r = 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 y > x so - x = 30 - 6 = 24 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 You'll be working with 8-bit integers X = Xo,...X7 and Y = Yo,...,Y7. (a) Design a comparator unit. Given input bits Xi, Y;, Ain and Bin, it produces outputs Aout and Bout such that: • If Ain +0 or Bin + 0, then Agut = Ain and Bout = Bin- %3D Otherwise • If Xin = Yin, Aout = 0, Bout = 0. • If Xin > Yin, Aout = 1, Bout = 0. • If Xin < Yin, Aout = 0, Bout = 1. %3D 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. = Xo, ...X7 and (c) Design an 8-bit conditional subtractor unit. Given inputs X Y = Y,...,Y7, A and B, it produces outputs Z = Zo, ., Z7 such that • If A = 0, B = 1, Z = Y - X. • Else, Z = X - Y. Use full adders and logic gates.

Answer rating: 100% (QA)

An... View the full answer