©2015 R. Boerner, School of Mathematical and Statistical Sciences, Arizona State University 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

©2015 R. Boerner, School of Mathematical and Statistical Sciences, Arizona State University 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: 𝑛 = ∑∑𝑑3𝑖+𝑗2 3𝑖+𝑗 2 𝑗=0 𝑞−1 𝑖=0 = ∑2 3𝑖 ∑𝑑3𝑖+𝑗2 𝑗 2 𝑗=0 𝑞−1 𝑖=0 = ∑8 𝑖 (𝑑3𝑖 + 2𝑑3𝑖+1 + 4𝑑3𝑖+2) 𝑞−1 𝑖=0 We now set 𝑜𝑖 = 𝑑3𝑖 + 2𝑑3𝑖+1 + 4𝑑3𝑖+2 for all i and get 𝑛 = ∑𝑜𝑖8 𝑖 𝑞−1 𝑖=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 2 3𝑖 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.

Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"