Conversion from octal numerical system to binary numerical system

Question

I know that in order to convert a numeral in base-8 to a numeral in base-2 I can write each octal digit as a binary word of 3 bits.

I know that 2^3 = 8 that is exactly the dimension of the base of the octal system.

I just cannot understand the fundamental reason why it works. Is it just a coincidence?

Answer 1

Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its base $b$ representation starting from the least significant digit to the most significant digit.

Take base $10$ for example.

$427428$ in base $10$ is $(4,2,7,4,2,8)$.
$427428$ in base $10^2$ is $(42,74,28)$.
$427428$ in base $10^3$ is $(427,428)$.

You can now find an analogy to your problem.

Edit: Proof for the above claim

Let a number $n$ be represented in base $b$ positional system as

$n = (a_{m-1},a_{m-2},\space...\space,a_1,a_0)$ such that $0 \le a_i \lt b \space \forall i\in\{0,1,\space...\space,m-1\}$

where $m$ represents the number of digits $n$ has in the base $b$ representation. We wish to represent $n$ in base $B = b^k$ for some positive integer $k$.

For the sake of simplicity of the argument, let $m$ be a multiple of $k$, i.e. $m = c k$ for some integer $c$. (If $m$ is not a multiple of $k$, the representation of $n$ in base $b$ can be prefixed by $0$'s untill the number of digits are a multiple of $k$)

From the representation in base $b$, we can write $n$ as follows

$n = a_{m-1} b^{m-1} + a_{m-2} b^{m-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space= a_{ck-1} b^{ck-1} + a_{ck-2} b^{ck-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space = a_{ck-1}b^{ck-1} + a_{ck-2}b^{ck-2} + \space ... \space + a_{(c-1)k+1} b^{(c-1)k+1} + a_{(c-1)k} b^{(c-1)k}$

$\space\space\space + a_{(c-1)k-1}b^{(c-1)k-1} + a_{(c-1)k-2}b^{(c-1)k-2} + \space ... \space + a_{(c-2)k+1} b^{(c-2)k+1} + a_{(c-2)k} b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + a_{2k-1}b^{2k-1} + a_{2k-2}b^{2k-2} + \space ... \space + a_{k+1} b^{k+1} + a_k b^k$

$\space\space\space + a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0$

We can rearrange the last expression by taking out powers of $b^k$ from each sequence of $k$ terms as follows

$\space\space\space + \{\space a_{ck-1}b^{k-1} + a_{ck-2}b^{k-2} + \space ... \space + a_{(c-1)k+1} b + a_{(c-1)k} \space\}.b^{(c-1)k}$

$\space\space\space + \{\space a_{(c-1)k-1}b^{k-1} + a_{(c-1)k-2}b^{k-2} + \space ... \space + a_{(c-2)k+1} b + a_{(c-2)k} \space\}.b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + \{\space a_{2k-1}b^{k-1} + a_{2k-2}b^{k-2} + \space ... \space + a_{k+1} b + a_k b \space\} . b^k$

$\space\space\space + \{\space a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0 \space\}$

$\space\space = p_{c-1} B^{c-1} + p_{c-2} B^{c-2} + \space ... \space + p_1 B + p_0$

Where, $p_i = a_{(i+1)k-1} b^{k-1} + a_{(i+1)k-2} b^{k-2} \space ... \space + a_{ik+1} b + a_{ik} \space$ $\space\space\forall i \in \{0,1,\space ...\space ,c-1\}$

We can see that this is a representation of $n$ in base $B$ i.e. base $b^k$, with $c$ digits.

$n = (p_{c-1},p_{c-2},\space ... \space, p_1,p_0)$.

For the above to a valid representation in base $B$, $\forall i:\space0 \le p_i \lt B$

We can verify this by finding the maximum value of any of the group of terms in the above expressions.

Since, $\forall i:\space 0 \le a_i \lt b$, maximum value of $a_i$ is $b-1$.

Now we get for any $i$,

$a_{(i+1)k-1}b^{k-1} + a_{(i+1)k-2}b^{k-2} + \space ... \space + a_{i+1} b + a_i$

$= (b-1)b^{k-1} + (b-1)b^{k-2} + \space ... \space + (b-1)b + b$

$= (b-1)(b^{k-1}+b^{k-2}+\space...\space+b+1)$

$= (b-1)\frac{b^k-1}{b-1}$

$= b^k - 1 $

which is strictly less than $b^k$ or $B$.

Hence, we prove the claim.