Probabilità P(1) e P(0) con sequenza binaria e quantizzatore non uniforme
Ciao a tutti,
Mi trovo leggermente in panne con un esercizio sulla codificazione di messaggi binari, il cui non capisco come risolvere e mi farebbe piacere ricevere qualche suggerimento e capire come modellare il problema per appunto risolverlo.
Il testo del problema è il seguente:
Dati i possibili valori/messaggi in uscita ad un quantizzatore \(Q(x) = \mathrm{sgn(x)}\),
\( \begin{aligned}
m_0 &= 0 \\
m_{+1} &= +1 \\
m_{-1} &= -1 \\
\end{aligned}\)
con le rispettive probabilità:
\( \begin{aligned}
p(m_0) &= 0.4 \\
p(m_{+1}) &= 0.3 \\
p(m_{-1}) &= 0.3 \\
\end{aligned}\)
si desidera costruire un codificatore entropico di Huffman, in maniera tale che i messaggi vengono codificati nella seguente forma:
\(\begin{array}{c c c c}\hline
\text{Messaggio} & -1 & 0 & +1\\\hline
\text{Seq. binaria} & 11 & 0 & 10\\\hline
\end{array}\)
Si richiede di dimostrare che la PDF dei bit codificati non è uniforme, perché si avranno più bit a 1 che a 0, esattamente \(P(1) = 0.5625\) e \(P(0) = 0.4375\).
Evidentemente la teoria della probabilità non è il mio forte perché se non fosse per il risultato finale proposto, io avrei detto banalmente che \(P(1) = 0.6\) e \(P(0) = 0.4\).
Ragionando un pò di più, ho pensato di usare il teorema di Bayes:
\(\displaystyle \begin{aligned}
P(0) & = P(0|m_0) + P(0|m_1)\\
P(1) & = P(1|m_{+1}) + P(1|m_{-1})\\
\end{aligned} \)
però non ottengo un risultato attendibile (almeno secondo il mio ragionamento - evidentemente - sbagliato):
\(\displaystyle \begin{aligned}
P(0) & = P(0|m_0) + P(0|m_1)\\
& = 0.4 + \frac{P(m_1|0)P(0)}{P(m_1)}\\
\end{aligned} \)
Dato che la probabilità di ottenere un messaggio \(m_1\) non è condizionata dall' avere un bit a 0, scrivo:
\(\displaystyle P(m_1|0) = P(m_1) \)
da cui però risulta:
\(\displaystyle P(0) = 0.4 + P(0) \)
risultato che ovviamente è assurdo.
Non riesco quindi a modellare correttamente il problema o a capire cosa sto trascurando. Diciamo che sono bloccato.
Potreste gentilmente aiutarmi a schiarire le idee ?
Ringrazio in anticipo.
Saluti,
Simo
Mi trovo leggermente in panne con un esercizio sulla codificazione di messaggi binari, il cui non capisco come risolvere e mi farebbe piacere ricevere qualche suggerimento e capire come modellare il problema per appunto risolverlo.
Il testo del problema è il seguente:
Dati i possibili valori/messaggi in uscita ad un quantizzatore \(Q(x) = \mathrm{sgn(x)}\),
\( \begin{aligned}
m_0 &= 0 \\
m_{+1} &= +1 \\
m_{-1} &= -1 \\
\end{aligned}\)
con le rispettive probabilità:
\( \begin{aligned}
p(m_0) &= 0.4 \\
p(m_{+1}) &= 0.3 \\
p(m_{-1}) &= 0.3 \\
\end{aligned}\)
si desidera costruire un codificatore entropico di Huffman, in maniera tale che i messaggi vengono codificati nella seguente forma:
\(\begin{array}{c c c c}\hline
\text{Messaggio} & -1 & 0 & +1\\\hline
\text{Seq. binaria} & 11 & 0 & 10\\\hline
\end{array}\)
Si richiede di dimostrare che la PDF dei bit codificati non è uniforme, perché si avranno più bit a 1 che a 0, esattamente \(P(1) = 0.5625\) e \(P(0) = 0.4375\).
Evidentemente la teoria della probabilità non è il mio forte perché se non fosse per il risultato finale proposto, io avrei detto banalmente che \(P(1) = 0.6\) e \(P(0) = 0.4\).
Ragionando un pò di più, ho pensato di usare il teorema di Bayes:
\(\displaystyle \begin{aligned}
P(0) & = P(0|m_0) + P(0|m_1)\\
P(1) & = P(1|m_{+1}) + P(1|m_{-1})\\
\end{aligned} \)
però non ottengo un risultato attendibile (almeno secondo il mio ragionamento - evidentemente - sbagliato):
\(\displaystyle \begin{aligned}
P(0) & = P(0|m_0) + P(0|m_1)\\
& = 0.4 + \frac{P(m_1|0)P(0)}{P(m_1)}\\
\end{aligned} \)
Dato che la probabilità di ottenere un messaggio \(m_1\) non è condizionata dall' avere un bit a 0, scrivo:
\(\displaystyle P(m_1|0) = P(m_1) \)
da cui però risulta:
\(\displaystyle P(0) = 0.4 + P(0) \)
risultato che ovviamente è assurdo.
Non riesco quindi a modellare correttamente il problema o a capire cosa sto trascurando. Diciamo che sono bloccato.
Potreste gentilmente aiutarmi a schiarire le idee ?
Ringrazio in anticipo.
Saluti,
Simo
Risposte
Spannometricamente. Mediamente ogni dieci messaggi ne abbiamo: quattro del tipo $ 0 $ per codificare i quali si useranno 4 zeri; tre del tipo $ -1 $, che richiederanno 6 uno e tre del tipo $+1$, per i quali serviranno 3 zeri e 3 uno. Sempre in media occorreranno, quindi, 7 zeri e 9 uno ogni dieci messaggi; con frequenze attese $ 7/16 $ per lo zero e $ 9/16 $ per l'uno.
Ciao
Ciao
Ciao orsolux,
OK mi sento un cretino. Effettivamente il ragionamento regge.
Io avevo ottenuto il risultato contrario perché, siccome l'esercizio è basato su un codificatore DPCM, attraverso una simulazione con una segnale sinusoidale, avevo ottenuto appunto 9 bit a 0 e 7 a 1.
Mi sono poi fissato sulla PDF ed ho tralasciato i dettagli più banali.
Ti ringrazio.
Simo
OK mi sento un cretino. Effettivamente il ragionamento regge.
Io avevo ottenuto il risultato contrario perché, siccome l'esercizio è basato su un codificatore DPCM, attraverso una simulazione con una segnale sinusoidale, avevo ottenuto appunto 9 bit a 0 e 7 a 1.
Mi sono poi fissato sulla PDF ed ho tralasciato i dettagli più banali.
Ti ringrazio.
Simo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo