Teoria dell'informazione: esercizio sulla compressione dati
Ciao community,
sto preparando l'esame di teoria dell'informazione e ho delle difficoltà su alcuni esercizi. Questo è uno di quelli, spero possiate aiutarmi.
Data la distribuzione di probabilità $p_1, ......, p_m$ con $p_i= 1/2^i$, $i=1,......, m-1$ e $p_m=1/2^(m-1)$, mostrare che un codice ottimo per tale sorgente ha la lunghezza media pari a $2-1/2^(m-2)$. (Suggerimento: utilizzare Huffman).
Io finora sono arrivato a queste conclusioni: utilizzando Huffman si crea un codice dove la parola più probabile a lunghezza 1, la seconda 2, la terza 3, e così via fino all'ultima parola $m$ che ha lunghezza $m-1$, quindi dato che la lunghezza di un codice è $sum_i p_i l_i$ in questo caso ho che $L=sum_(i=1)^(m-1) 1/2^i i+ 1/2^(m-1) (m-1)$. Come faccio a trovarmi $L=2-1/2^(m-2)$?
Grazie in anticipo.
sto preparando l'esame di teoria dell'informazione e ho delle difficoltà su alcuni esercizi. Questo è uno di quelli, spero possiate aiutarmi.
Data la distribuzione di probabilità $p_1, ......, p_m$ con $p_i= 1/2^i$, $i=1,......, m-1$ e $p_m=1/2^(m-1)$, mostrare che un codice ottimo per tale sorgente ha la lunghezza media pari a $2-1/2^(m-2)$. (Suggerimento: utilizzare Huffman).
Io finora sono arrivato a queste conclusioni: utilizzando Huffman si crea un codice dove la parola più probabile a lunghezza 1, la seconda 2, la terza 3, e così via fino all'ultima parola $m$ che ha lunghezza $m-1$, quindi dato che la lunghezza di un codice è $sum_i p_i l_i$ in questo caso ho che $L=sum_(i=1)^(m-1) 1/2^i i+ 1/2^(m-1) (m-1)$. Come faccio a trovarmi $L=2-1/2^(m-2)$?
Grazie in anticipo.
Risposte
La tua serie si calcola derivando la serie geometrica, si ha infatti che
[tex]\sum_{k=1}^n k x^{k-1} = \frac{d}{dx} \sum_{k=1}^n x^k = \frac{d}{dt} \frac{x - x^{n+1}}{1 - x} = \frac{nx^{n+1} - (n+1)x^n + 1}{(1 - x)^2}[/tex].
Tornando quindi al tuo caso si ha che
[tex]\sum_{i=1}^{m-1} \frac{i}{2^i} = \frac 12 \sum_{i=1}^{m-1} \frac{i}{2^{i-1}} = \frac 12 \frac{(m - 1)(1/2^m) - m(1/2^{m-1}) + 1}{1/4}[/tex]
da cui risolvendo i calcoli si ottiene
[tex]\frac{m - 1 - 2m + 2^m}{2^{m-1}} = \frac{2^m - m - 1}{2^{m-1}} = 2 - \frac{m+1}{2^{m-1}}[/tex].
Includendo quindi insieme anche l'ultimo termine si ottiene infine:
[tex]2 - \frac{m+1}{2^{m-1}} + \frac{m-1}{2^{m-1}} = 2 - \frac{2}{2^{m-1}} = 2 - \frac{1}{2^{m-2}}[/tex].
Ti consiglio ovviamente di rifare i calcoli, ma questi sono più o meno i passaggi da fare.
[tex]\sum_{k=1}^n k x^{k-1} = \frac{d}{dx} \sum_{k=1}^n x^k = \frac{d}{dt} \frac{x - x^{n+1}}{1 - x} = \frac{nx^{n+1} - (n+1)x^n + 1}{(1 - x)^2}[/tex].
Tornando quindi al tuo caso si ha che
[tex]\sum_{i=1}^{m-1} \frac{i}{2^i} = \frac 12 \sum_{i=1}^{m-1} \frac{i}{2^{i-1}} = \frac 12 \frac{(m - 1)(1/2^m) - m(1/2^{m-1}) + 1}{1/4}[/tex]
da cui risolvendo i calcoli si ottiene
[tex]\frac{m - 1 - 2m + 2^m}{2^{m-1}} = \frac{2^m - m - 1}{2^{m-1}} = 2 - \frac{m+1}{2^{m-1}}[/tex].
Includendo quindi insieme anche l'ultimo termine si ottiene infine:
[tex]2 - \frac{m+1}{2^{m-1}} + \frac{m-1}{2^{m-1}} = 2 - \frac{2}{2^{m-1}} = 2 - \frac{1}{2^{m-2}}[/tex].
Ti consiglio ovviamente di rifare i calcoli, ma questi sono più o meno i passaggi da fare.
Grazie apatriarca,
ti ringrazio per la risposta tempestiva anche perché non ricordavo proprio l'esistenza di questa serie geometrica
e quindi non ci sarei mai arrivato da solo. Adesso mi tocca rivedermi anche questo 
Ancrora grazie. Ciaooo
ti ringrazio per la risposta tempestiva anche perché non ricordavo proprio l'esistenza di questa serie geometrica
e quindi non ci sarei mai arrivato da solo. Adesso mi tocca rivedermi anche questo Ancrora grazie. Ciaooo
La serie geometrica è molto utile. Ti conviene proprio ripassarla..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo