Combining Shannon Entropy with a notion of bit-rate

89 Views Asked by At

If you have a sequence of samples from a finite alphabet where the $i$th symbol has probability $p_i$ the shannon entropy of each symbol $H = \sum_i p_i \log_2(p_i)$. That is each symbol carries $H$ bits of data, and you would expect $k$ symbols to be expressible with $Hk$ bits. If each symbol has an amount of transmission time $t_i$ associated with it, how do I describe the bit-rate of this stream of samples? My guess would be $R = \sum_i \frac{p_i}{t_i} \log_2(p_i)$ since it behaves as expected in a couple of ways:

  • If you scale the time each symbol takes its rate scales by the reciprocal.
  • If all the times are equal to $t$, it becomes $H/t$ which is correct

What is $R$ technically called? What field studies it? What is a good text on that field?

1

There are 1 best solutions below

0
On

I am not aware of the notion you are trying to identify (and not sure of its practical value), but here is one way you could think about it.

Let $b_i$ and $i_t$ denote the bits required to represent and the transmission time of symbol $i$, respectively. Then, one could define the bit-rate of this symbol as $b_i/t_i$ and, in turn, the bit rate of this stream of samples as $\mathbb{E}(b_i/t_i)$. Since $b_i$ and $t_i$ are independent, this expression becomes $\mathbb{E}(b_i)\mathbb{E}(1/t_i)$. By approximating $\mathbb{E}(b_i)=H$, the final expression is $H\mathbb{E}(1/t_i) = H\sum_{i}p_i/t_i$. Note that this expression also behaves as you expect it should.

A more accurate approach would be to consider a stream of $K$ symbols that are jointly encoded by $N(K)$ bits with a total transmission time $\sum_{i=1}^{K}t_i$. Then the bit rate should be defined as $\lim_{K\rightarrow \infty}\frac{N(K)}{\sum_{i=1}^{K}t_i}=\lim_{K\rightarrow \infty}\frac{N(K)/K}{\sum_{i=1}^{K}t_i/K}=\frac{\lim_{K\rightarrow \infty}N(K)/K}{\lim_{K\rightarrow \infty}\sum_{i=1}^{K}t_i/K}=\frac{H}{\mathbb{E}(t_i)}=\frac{H}{\sum_{i}p_i t_i}$.

Note that this formula also behaves as you expect it should.