Problem Set 3 Released Monday 02-14-2005 Due Wednesday 02-23-2005 at 5 p.m. (1) A multiplexer is a logic device that lets you interleave ("multiplex") 2 or more input channels over a single output channel. By means of certain "selector lines," we can control which input channel's data is passed on to the output channel at a given time. A] Consider the 2:1 mux (short for multiplexer) below: -------- i0 ----| | i1 ____| 2 : 1 |---- out |________| | s This device behaves as follows: 'out' is equal to 'i0' when 's' is 0 and 'out' is equal to 'i1' when 's' is 1. Construct a truth table for this device ('i0', 'i1' and 's' are the inputs and 'out' is the output). Draw a logic diagram for the device using AND, OR and NOT gates. B] A 4:1 mux has 4 inputs and (as usual) 1 output. However, there are 2 select lines 's0', and 's1' which help choose one of the four inputs. i.e. For s1=0 and s0=0, out = i0 For s1=0 and s0=1, out = i1 For s1=1 and s0=0, out = i2 For s1=1 and s0=1, out = i3 Your task now is to construct a 4:1 mux using three 2:1 muxes. C] Extra Credit: Describe a 8:1 mux. Show how you will implement a 8:1 mux using one or more 2:1 muxes. (2) In class we saw how strings of bits could be used to represent types of information. In some situations, we want to make the representation as efficient as possible (i.e. to use the minimum number of bits needed to represent certain types of information). Consider here the representation of the alphabet. Suppose you wanted to represent all upper and lower case letters (i.e., a, b, ... z, A, B, ... Z). Suggest a representation and tell how many bits it requires. How does your answer change if you are only representing the capital letters? (3) (i) Decimal addition: 786 + 687 = ? (ii) Hexadecimal addition: 786 + 687 = ? (iii) Binary Subtraction: 11100010 - 11001011 = ? (iv) Give the hexadecimal and binary representations for the decimal number 45. (v) Give the decimal and binary representations for the hexadecimal number 45. (4) In the 1st assignment, you determined that your computer could do an incredibly large number of instructions during a COS 111 lecture. You calculated this number by counting the number of times your computer can do multiplications during the 80 minutes of a lecture. In this assignment, we will extend this analysis to trying to solve a real problem. Imagine that you are using your computer to try and determine my password. You do so, by taking a guess at my password and then performing a test to see if you have guessed correctly. The test you do is very complicated for reasons you will (hopefully) understand by the end of the semester. Testing one password takes about 1 million ticks of your computer's clock (Note: ticks not instructions). How many passwords can you check during a COS 111 lecture? The number seems incredibly large, doesn't it ? Does it seem like figuring out someone's password is simpler than sitting through a cos 111 lecture ? Lets do some more analysis. Passwords on many unix systems are (still) limited to 8 characters. We will assume the passwords are based on a scheme called DES. A password is a string of characters and as far as your computer is concerned, and it is ultimately a string of bits (a sequence of 0s and 1s). For your computer to guess a password based on DES (and composed of 8 characters), it has to guess 56 bits. Ignore the time the computer has to spend in making the guess, ie, assume the time to make a guess and test to see if it works is 1 million clock cycles as assumed earlier. Also assume that you won't be so unlucky as to have to test all possible guesses before you guess the correct password. Assume, you will get lucky midway, ie, you will only need to guess half the possible values before you hit the right one. How many lectures will you have to sit through before you find my password ? Again, don't let the above answer make you think DES is safe enough. One can always build specialized machines which do this calculation much faster. See http://news.com.com/2100-1017-220333.html?legacy=cnet