The 01-swap operation, b, on a binary string S, permutes all occurences of 01 within the...

Transcribed Image Text:

The 01-swap operation, b, on a binary string S, permutes all occurences of 01 within the original string to 10 (the process is not recursive). For instance: b(0) = 0, b(1) = 1, 6(00) = 00, b(01) = 10,6(11) = 11 b(000) = 000, b(001) = 010, 6(010) = 100, b(100) = 100 b(0 01 01 1 01 0) = 0 10 10 1 10 0 (spacing added for clarity). Design a circuit using 2-1 multiplexers that can be used to perform the 01-swap on a k-bit string S = Sk-1Sk-2 So where each S is a bit. (a) First, show the circuit, built using the 2:1 MUX, whose output is the ith bit of b(S) where 0 < i < k 1. YOU DO NOT NEED ANY AND, OR, OR NOT GATES, only a single 2:1 MUX. This is somewhat challenging so think what input information you need. (b) Use contraction to solve the edge cases when i = 0, k - 1. You do not have to simplify the internals of the MUX, just explain why you "contracted" as you did. The 01-swap operation, b, on a binary string S, permutes all occurences of 01 within the original string to 10 (the process is not recursive). For instance: b(0) = 0, b(1) = 1, 6(00) = 00, b(01) = 10,6(11) = 11 b(000) = 000, b(001) = 010, 6(010) = 100, b(100) = 100 b(0 01 01 1 01 0) = 0 10 10 1 10 0 (spacing added for clarity). Design a circuit using 2-1 multiplexers that can be used to perform the 01-swap on a k-bit string S = Sk-1Sk-2 So where each S is a bit. (a) First, show the circuit, built using the 2:1 MUX, whose output is the ith bit of b(S) where 0 < i < k 1. YOU DO NOT NEED ANY AND, OR, OR NOT GATES, only a single 2:1 MUX. This is somewhat challenging so think what input information you need. (b) Use contraction to solve the edge cases when i = 0, k - 1. You do not have to simplify the internals of the MUX, just explain why you "contracted" as you did.