I've been given a proof of the following:

If $q\geq2$, then there is a source $S$ with $q$ symbols, and an instantaneous $r$-ary code $C$ satisfying $L(C)=H_r(S)$ if and only if $q\equiv 1 \mod{(r-1)}$.

I've looked at the proof in one direction, but I'm having a hard time making sense of it.

I understand that if $L(C)=H_r(S)$ then every $p_i$ is in the form of $r$ to the power of some negative integer (i.e., $p_i=r^{e_i}$, where $e_i$ is less than or equal to zero).

This tells me that the $\sum\limits_{i=1}^q p_i=1=\sum\limits_{i=1}^q r^{e_i}$.

In the proof I have been given, the next step is to remove the smallest probability (i.e., the $r$ with the smallest $e_i=e$), whence we have $q-1$ probabilities, and we know that $\sum\limits_{i=1}^q r^{e_i-e}=r^{-e}$.

This all makes sense to me. I would think the next part of the proof would go on to show that $q-1$ is a multiple of $r-1$, but I honestly don't follow the rest, which is shown below:

So if $e = \min e_i$, then $\sum\limits_{i=1}^{q}r^{e_i-e}=r^{-e}$ with $e_i-e$ and $-e$ $\geq 0$ ; each term $r^{e_i-e}$ and $r^{-e}\equiv1 \mod{(r-1)}$, so that $q\equiv1 \mod{(r-1)}$.

Can someone please explain why knowing $\sum\limits_{i=1}^{q}r^{e_i-e}=r^{-e}$ automatically implies that each term $r^{e_i-e}$ and $r^{-e}\equiv1 \mod{(r-1)}$?

  • $\begingroup$ For $n\ge 0$, $r^n\equiv1\mod{(r-1)}$ always, right? For $n=0,1$, it's obvious; for $n\ge 2$, write $r^n=((r-1)+1)^n$ and expand using binomial theorem. Every term except the last contains $r-1$. $\endgroup$ – Ashok Oct 14 '13 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.