<p>I think it's just in the first inequality (the Kraft inequality): you sum over all the symbols $1/2^{\text{length of encoding}}$. There are 3 symbols of length $3$ bits and $d$ symbols of length $8$ bits, so that's how you get the first inequality. (Also, does your question have a typo? $a_4,a_5,\dots,a_{d+3}$ rather than $\dots,a_{d+1}$.) The $5/8$ comes from simplifying the inequality: you get $3/8 + d/256 \leq 1$, which is equivalent to $d/256 \leq 5/8$.</p>

CC BY-SA 3.0
2015-08-30T12:20:04.290Z
One more question, What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it @usul
John Sick
CC BY-SA 3.0
2015-08-30T16:27:43.450Z
@MuneebulHassan, in the first inequality, we sum over all the symbols. There are $d+3$ symbols total. $3$ of them have length $3$ and $d$ have length $8$. So that's $3\cdot(1/2^3) + d\cdot (1/2^8) \leq 1$. If we only had $d+1$ symbols, there would be $3$ with length $3$ and $d-2$ with length $8$. So the inequality would be $3\cdot(1/2^3) + (d-2)\cdot(1/2^8) \leq 1$.
usul
CC BY-SA 3.0
2015-08-31T01:26:23.103Z
@usul: He has already asked the same question on Math Stackexchange which I answered.
kodlu
CC BY-SA 3.0
2015-08-30T12:18:03.740Z
2015-08-30T16:22:53.577Z
2015-08-30T16:22:53.577Z
usul
<p>I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me.</p>

<p>We would like to encode a sequence of symbols that come from an alphabet with d+3 symbols. We want to encode symbols  a_1,a_2,and a_3 using code words that are three bits long and symbols a_4,a_5,…,a_(d+1) with code words that are eight bits long. What is the maximum value of d for which this will be possible, if the code must be uniquely decidable?</p>

<p>and the answer is:</p>

<p>The codeword lengths are possible if and only if they satisfy the Kraft-MacMillan inequality,which in this case is <br/>
1/2^3 +1/2^3 +1/2^3 +d/2^8 &lt;= 1 <br/>
This is equivalent to <br/>
d/256&lt;=5/8<br/>
which is equivalent to d&lt;=160. The maximum value possible value of d is therefore 160.<br/>
what is the function d+3 , and where we used it . How 5/8 appears in equation.<br/></p>

<p>What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it</p>

CC BY-SA 3.0
2015-09-01T07:11:58.810Z
Cross-posted on Math.SE: http://math.stackexchange.com/q/1414536/14578.  Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration.
D.W.
<it.information-theory>
Kraft Macmillan inequality explanation
John Sick
# Kraft Macmillan inequality explanation

(Asked by: username_0 on 2015-08-30)

I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me.

We would like to encode a sequence of symbols that come from an alphabet with d+3 symbols. We want to encode symbols a\_1,a\_2,and a\_3 using code words that are three bits long and symbols a\_4,a\_5,…,a\_(d+1) with code words that are eight bits long. What is the maximum value of d for which this will be possible, if the code must be uniquely decidable?

and the answer is:

The codeword lengths are possible if and only if they satisfy the Kraft-MacMillan inequality,which in this case is   
1/2^3 +1/2^3 +1/2^3 +d/2^8 <= 1   
This is equivalent to   
d/256<=5/8  
which is equivalent to d<=160. The maximum value possible value of d is therefore 160.  
what is the function d+3 , and where we used it . How 5/8 appears in equation.

What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it

**Tags:** it.information-theory

> **Comments:**
> **username_1**: Cross-posted on Math.SE: http://math.stackexchange.com/q/1414536/14578.  Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration.  

---

## 1 answers

### Answer by username_2 on 2015-08-30. Score: 2 | Accepted answer

I think it's just in the first inequality (the Kraft inequality): you sum over all the symbols $1/2^{\text{length of encoding}}$. There are 3 symbols of length $3$ bits and $d$ symbols of length $8$ bits, so that's how you get the first inequality. (Also, does your question have a typo? $a\_4,a\_5,\dots,a\_{d+3}$ rather than $\dots,a\_{d+1}$.) The $5/8$ comes from simplifying the inequality: you get $3/8 + d/256 \leq 1$, which is equivalent to $d/256 \leq 5/8$.

> **Comments:**
> **username_0**: One more question, What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it @username_2  
> **username_2**: @MuneebulHassan, in the first inequality, we sum over all the symbols. There are $d+3$ symbols total. $3$ of them have length $3$ and $d$ have length $8$. So that's $3\cdot(1/2^3) + d\cdot (1/2^8) \leq 1$. If we only had $d+1$ symbols, there would be $3$ with length $3$ and $d-2$ with length $8$. So the inequality would be $3\cdot(1/2^3) + (d-2)\cdot(1/2^8) \leq 1$.  
> **username_3**: @username_2: He has already asked the same question on Math Stackexchange which I answered.  

---

