0
$\begingroup$

The entropy of a source $H(S)$, gives you the average codeword length to encode a given source alphabet. i.e. it is the average number of bits per symbol required to encode the information in the source. If: $p_0=3/5$ and $p_1=2/5$ (close probabilities) with $H=0.971 \textrm{ bits/symbol}$, then there's more information than compared to the 2nd case where $p_0=3/4$ and $p_1=1/4$ yielding $H = 0.8113 \textrm{ bits/symbol}$ to encode. Following are the problems that I am facing and I will be very grateful for a detailed answer.

  1. In general, if the source entropy is $H$ then what should be the minimum number of bits if the alphabet is $0,1$ ?
  2. In case of discrete chaotic map say Logistic map, the entropy is $\log \lambda$ where $\lambda$ is the largest Lyapunov exponent. What should be the length of the time series in binary or what should be the length of the symbolic representation in binary of the initial condition?
$\endgroup$
2
$\begingroup$

I can try to answer your first question (but I'm not sure I understand exactly what you mean).

A source produces messages with average information $H$. You seem to have a binary source, with two messages $m_1$ and $m_2$.

Now you want to encode the messages to a sequence of 1s and 0s (subsequently called "bits"). This is called "source coding". Even though we know that, in principle, we should be able to encode $N$ messages using $NH$ bits (for large $N$), it is not always obvious how to do so. There are algorithms such as Huffman and Lempel-Ziv that can find good (even optimal) encodings. Note that all good coding algorithms encode messages in groups, not individually, and they approach $NH$ only when $N$ is large.

If your question is "what's the smallest number of bits that I need to encode $N$ messages from a source with entropy $H$", the answer is $NH$ (in theory), and somewhat more in practice, depending on the optimality of your encoding algorithm and the value of $N$.

Example 1: A source produces 8-bit messages $b_7b_6b_5b_4b_3b_2b_2b_1b_0$ uniformly at random, but $b_7$ is always 0. The entropy is 7 bits/message. Let's say we want to transmit 100 messages. Even though the source produced 800 bits, we only need 700 to transmit the messages.

Example 2: You flip a biased coin with $p(\text{heads})=0.3$ 1000 times. The entropy of the experiment is 0.88 bits/flip. To convey the result of the 1000 flips, you'll need on average 880 bits. Some particular results will need more bits, some will need less. To figure out how many bits you need for a particular sequence of flips you need to specify your encoder algorithm.

Example 3: You have a biased 3-sided die with probability distribution $p(1)=0.5$, $p(2)=0.25$, $p(3)=0.25$. The entropy is 1.5 bits/throw. It's pretty easy to come up with an encoder:

result  encoding
1    -> 0
2    -> 10
3    -> 11

You should be able to convince yourself that, on average, this encoding results in 1.5 bits per throw. However, let's say that you're unlucky and you get 1000 '3' in a row. That particular sequence will need 2,000 bits to transmit. That's why the entropy can only predict the average sequence length, not the length you'll get for a particular set of messages.

$\endgroup$
  • $\begingroup$ THank you for your reply. $N$ denotes the length of the message in my question. I have a binarized time series each of length $N$ (dimension) and I found the entropy for each time series. Then, I need to find the minimum number of bits to represent the entire database. If for a database of $k=100$ time series, each of same dimension/length $N$, yields $H = 1,2,..,k$ entropy values, then is there a way to determine the code length? $\endgroup$ – SKM May 12 '16 at 16:34
  • $\begingroup$ Only the source has entropy. Messages have information. What is the entropy of your source? $\endgroup$ – MBaz May 12 '16 at 17:23
  • $\begingroup$ The objective is to compress each of the binarized time series across their dimensions. So, when dimension, $N = 960$ entropy H = 0.9995. Then how do I decide what should be the reduced dimension i.e., the new length of this time series based on its entropy? Can entropy be applied? $\endgroup$ – SKM May 12 '16 at 18:36
  • $\begingroup$ Entropy should be sensitive to the choice of $N$. So, what is the criteria to select $N$ ? $\endgroup$ – SKM May 12 '16 at 18:42
  • $\begingroup$ SKM, I'll insist: entropy is a property of the source, and the source only. You know that your source produces messages $m_1$ and $m_2$ with probabilities $p(m_1)$ and $p(m_2)$, so you should be able to find its entropy $H$. Once you know the entropy, you know that on average, a sequence of $N$ messages will require $NH$ bits to encode. $\endgroup$ – MBaz May 12 '16 at 19:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.