Block Conversion from Binary to Octal We have learned that we can block-convert
ID: 3789865 • Letter: B
Question
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 n is a nonnegative integer and its binary expansion is given by d 2 where each dk E 10,13 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. m 1 3a for some natural number q We now group the sum into blocks of 3 terms each, as follows q-1 2 q-1 q-1 2J 8 3i 2d 3i+ 3i+ j 3i+1 3i +2 i 0 We now set o 3i 2d. +1 4d 3i+2 for a i and get 3i q-1 oi 8 i 0 Since each dk is 0 or 1, the oi satisfy 0 S oi S 7, i.e., there are octal digits. We have found the octal expansion of n, and it is obtained by block-converting three binary digits at a time to octal, from right to leftExplanation / Answer
1.) Loss of generality here refers to the fact while converting a non-negative integer into binary we are not loosing its value (magnitude). Number of terms in the sum can always be a multiple of 3 as we divide the binary digit into group of three bits and we pad extra zero bits if they are not.
2.) Quantity q represents the no. of octal digits in the resulting octal number.
3.) Because we have solved the inner sigma which is from j=0 to j=2; which leads to only one sigma function.
4.) First we take 2^(3i) out of inner sigma since inner sigma is not depending on values of i. But we can't take it out from the outer one as outer sigma is depending on values of i. After taking out the 2^(3i) from inner sigma we expand inner sigma for all values of j.