The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as

$$ (S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in S_A,s_B\in S_B $$

and the MinAveCodeLen is the minimum average codeword length which is equal to the average codeword length of a Huffman coding.

The problem is to prove

$$ \mathrm{MinAveCodeLen}(P)\leq\mathrm{MinAveCodeLen}(P_A)+\mathrm{MinAveCodeLen}(P_B) $$

The original problem is quite confusing. I am asked to prove $H(P_A)+H(P_B)=H(P)$ in the previous part, so I was trying to relate the problem with $H$ at first with no progress.


It's so wired that again, I'm answering my own question... I have to admit I am not confident at all when confronted with constructive proof problems.

An encoding scheme for ${P}$ could be described graphically as follows: Suppose $T_A$, $T_B$ are 2 Huffman trees for ${P}_A$ and ${P}_B$ respectively. For each leaf $s_{Ai}$ in $T_A$ replace it with $T_B$, i.e. enter image description here Letting $|S_A| = q,|S_B| = q$, the average code word length of this coding scheme is $$C = \frac{\sum l_{Ai}+l_{Bj}}{pq} = \frac{q\sum l_{Ai}+p\sum l_{Bj}}{pq} = \mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}\mathbb{P}_B)$$ where $l_{Ai}$, $l_{Bj}$ are the codeword length of $s_{Ai}$ and $s_{Bj}$ in the Huffman code corresponding to $T_A$, $T_B$. Therefore, $$\mathrm{MinAveCodeLen}({P})\leq C\leq\mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}({P}_B)$$

| cite | improve this answer | |

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.