Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local) notions of information, has there been a study to utilize Kolmogorov complexity for these results (or atleast to replace the source coding part in source channel separation results)?
2
-
$\begingroup$ Have you taken a look at the 3rd edition of the Li & Vitanyi book? If I'm not mistaken, the 8. chapter in the book was added in the newest edition, and contains a chapter on Information Theory. It features Shannon entropy, mutual information, rate distortion etc. analyzed in the sense of Kolmogorov complexity. $\endgroup$– JuhoMar 31, 2012 at 14:51
-
$\begingroup$ Hi that is true. But there is no application to the noisy coding theorem of Shannon! $\endgroup$– v sMar 31, 2012 at 17:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy. Using the Shannon entropy gives the right formula for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula, and so it would be the wrong answer.
If you want to send a string with Kolmogorov complexity $K$ through a channel with capacity $C$ using only slightly more than $K/C$ channel uses, this is very easy. Find the description of the Turing machine that produces the string. Then encode it with an error-correcting code so this description can be sent through the noisy channel with only a small probability of error.
The hard part of the source-channel separation theorem is showing that you can't do better than the obvious method (described in the previous paragraph) of first compressing and then encoding. I don't know whether anybody has proved this for Kolmogorov complexity and channel capacity, but it's a reasonable question to investigate.
answered Jul 25, 2013 at 11:27
-
$\begingroup$ Am I missing something subtle, or does it follow from the definition of Kolmogorov complexity? I.e. any scheme for sending the string with asymptotically fewer than $K$ bits could be, with constant overhead, turned into a TM of size asymptotically smaller than $K$ (that is, the decoder plus the message) that reproduces the original string? $\endgroup$– usulJul 27, 2013 at 19:13
-
1$\begingroup$ @usul: for channels which transmit bits, $C \leq 1$. On the other hand, I suspect it should be fairly easy to prove using the tools of information theory. $\endgroup$ Jul 27, 2013 at 20:06
-
$\begingroup$ @PeterShor"......If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula....". How different would this formula be? Usually Kolmogorov compression provides an $\Omega(\log^{*}n)$ extra multiplicative factor in compression if the optimal number of bits is $n$ (For instance, the KC version of prime number theorem gives $\log\log{n}$ factor in the denominator). Say the capacity is $r$, then even if KC gave $\frac{r}{\log^{*}r}$, it would be interesting. Do you have any calculations? Also SE and KC are same is known. $\endgroup$– TurboSep 14, 2013 at 23:55
$\begingroup$
$\endgroup$
1
I am not sure what you are talking about when you use the local/global qualifiers on Shannon's entropy and Kolmogorov's complexity.
So correct me if I am wrong.
Shannon's entropy is computable. Kolmogorov's complexity is not. Therefore they do not describe the same problem.
You could see Shannon's entropy as an upper bound to Kolmogrov's complexity.
-
$\begingroup$ How is Shannon entropy an upper bound? I believe it is proven both are the same. $\endgroup$– TurboSep 15, 2013 at 0:01