Block Conversion from Binary to Octal We have learned that we can block-convert a binary number to octal by grouping the binary number into blocks of 3 digits (going from right to left, perhaps padding the binary number with one or two leading zeros to complete the leftmost block of three) and converting each 3 digit binary number into one octal digit. The following is a proof that this procedure works as advertised. Suppose is a nonnegative integer and its binary expansion is given by = 2 =0 where each {0,1} and m is a nonnegative integer. We can assume without loss of generality that the number of terms in this sum is a multiple of 3,i.e. + 1 = 3 for some natural number q. We now group the sum into blocks of 3 terms each, as follows: 1 2 1 1 2 = 3+ 23+ = 23 3+ 2 = 8 (3 + 23+1 + 43+2 ) =0 =0 =0 =0 =0 We now set = 3 + 23+1 + 43+2 for all i and get 1 = 8 =0 Since each is 0 or 1, the satisfy 0 7, i.e., there are octal digits. We have found the octal expansion of , and it is obtained by block-converting three binary digits at a time to octal, from right to left. Questions for you to consider. 2015 R. Boerner, School of Mathematical and Statistical Sciences, Arizona State University 1. What is the meaning of \"without loss of generality\"? What is the specific purpose here of employing that device? How can the number of terms in the sum, an arbitrary integer, always be a multiple of 3? 2. What does the quantity q represent? 3. Why is the single sigma sum equal to the double sigma sum? How would you rigorously prove that? 4. What algebraic laws were used in simplifying the sigma sum? Why was it possible to factor 23 out of the inner sigma sum, but not the outer one? 5. Fill in a detail that the given proof omits, namely why the satisfy the inequality 0 7. 6. Rewrite the given proofs to demonstrate how and why block conversion from octal to binary works. 7. Write a similar proof to demonstrate how and why block conversion from binary to hexadecimal works. 8. You can't block convert from binary to decimal. At which specific point(s) would a proof that follows the lines of the proof given here fail? 9. For which numbers can binary numbers be block converted to base-b? Write a general proof that block conversion always works for those numbers. If you wish to get feedback on your answers, post them on piazza. 2015 R. Boerner, School of Mathematical and Statistical Sciences, Arizona State University