Talk:Shannon's source coding theorem

Reorganised/Merged

I suggest the 'Shannon noiseless source coding theorem' article be merged with this 'Source coding' article.

--Hpalaiya 22:54, 19 May 2006 (UTC)[reply]

this is a separate large article. maybe a summary of this article might be appropriate on the source coding page - strong disagree

—Preceding unsigned comment added by 81.104.79.141 (talk • contribs) 16:18, 21 December 2006

Merge carried out, having first:

renamed article from source coding to Shannon's source coding theorem
redirected source coding to point to data compression
moved material on variable length codes to variable length codes
removed tag suggesting merger with entropy encoding

Some more clean-up to do, to blend the presentation of the two theorems more closely. (Detailed editing not yet started).

-- Jheald 22:00, 6 March 2007 (UTC).[reply]

I don't think that the $\mathbb {E}$ that keeps showing up is ever explained/defined in this article. A quick explanation as to what it is would go a long way for someone that is not familiar with the material already.

Jeejaw (talk) 02:24, 11 September 2009 (UTC)[reply]

An alternative proof for the symbol code case

Applying the Jensen's inequality for the expression $\sum _{i=1}^{n}p_{i}\ log_{2}(a^{-s_{i}}/p_{i})$ we can have a direct proof without using any $q_{i}$ 's:

\sum _{i=1}^{n}p_{i}\log _{2}{\frac {a^{-s_{i}}}{p_{i}}}\leq \log _{2}\sum _{i=1}^{n}a^{-s_{i}}

Using the Kraft's inequality $\sum _{i=1}^{n}a^{-s_{i}}\leq 1$ on the right side:

{\begin{matrix}&&\\\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}&\leq &\log _{2}1\\&&\\\sum _{i=1}^{n}p_{i}s_{i}\log _{2}a-\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}&\geq &0\\&&\\\mathbb {E} (S)\log _{2}a-H(X)&\geq &0.\\&&\\\end{matrix}}

--Vamos (talk) 20:12, 18 November 2009 (UTC)[reply]

Source coding theorem for symbol codes is wrong?

As far as I can see, Source coding theorem for symbol codes is wrong or at least is not accurate. Here is the counterexample: let $\Sigma _{1}=\Sigma _{2}=\{0,1\}$ , $f(\epsilon )=0$ , $f(0)=\epsilon$ , $f(x)=x$ for other $x$ ( $\epsilon$ is the empty word), X is 0 or 1 with equal probability. Then, it is clear that f is decipherable code, but $\mathbb {E} S=0.5<H(X)=1$ . There is also a counterexample that does not use the empty word. Could someone help to state this theorem more accurate? Alexei Kopylov (talk) 17:30, 5 May 2010 (UTC)[reply]

Well Alexei, Using any zero cost symbol (empty symbol), a message longer than a single symbol will not be uniquely decodable. It contradicits to the Kraft's inequality which is a necessary condition for decodability. Vamos (talk) 17:19, 12 May 2010 (UTC)[reply]

Oh, thanks! The problem was that the statement was about decipherable code, and there were no definition what decipherable code was. I changed it to uniquely decodable code, with the wiki link. See my change Alexei Kopylov (talk) 01:06, 14 May 2010 (UTC)[reply]