Codifica delle sequenze sorgente

Codifica delle sequenze sorgente
Sorgente emette sequenza di simboli appartenenti ad
un alfabeto X che vengono codificati come sequenze di
simboli di un alfabeto D-ario.
. – p.1/??
Codifica delle sequenze sorgente
Sorgente emette sequenza di simboli appartenenti ad
un alfabeto X che vengono codificati come sequenze di
simboli di un alfabeto D-ario.
L’alfabeto di codifica binario è l’insieme {0, 1}.
. – p.1/??
Legge debole dei grandi numeri
Teorema (Legge dei grandi numeri – versione debole)
Se X1 , . . . , Xn sono n v.c. i.i.d., allora
n
X
1
Xi ≈ E [X], per n → ∞.
n
i=1
. – p.2/??
Proprietà di equipartizione asintotica
Teorema Proprietà di Equip. Asintotica (PEA)
Se X1 , X2 . . . , sono v.c. i.i.d. con d.d.p. P (X), allora
1
− lg P (X1 , X2 , ..., Xn ) → H (X) in probabilità,
n
P (X1 , X2 , ..., Xn ) = prob. di osservare sequenza
X1 , X2 , ..., Xn .
limite in probabilità ≡ ∀ε > 0 e ∀δ > 0, ∃n0 t.c. ∀n ≥ n0 ,
1
Pr − lg P (X1 , ..., Xn ) − H (X) < ε > 1 − δ
n
. – p.3/??
Dim. Le variabili lg P (X1 ), . . . , lg P (Xn ) sono i.i.d. e quindi
1
− lg P (X1 , X2 , ..., Xn )
n
i.i.d.
=
=
1
− lg (P (X1 ) P (X2 ) ...P (Xn ))
n
n
X
1
−
lg P (Xi ) → E [− lg P (X)]
n
i=1
=
per
la legge
dei grandi numeri
1
E lg
= H (X) .
P (X)
. – p.4/??
Conseguenze della PEA: Compressio
S : sorgente modellata con una sequenza di n v.c.
X1 , . . . , Xn i.i.d. con alfabeto X
. – p.5/??
Conseguenze della PEA: Compressio
S : sorgente modellata con una sequenza di n v.c.
X1 , . . . , Xn i.i.d. con alfabeto X
X n : insieme sequenze di lunghezza n emesse da S .
L’insieme X n può essere partizionato in:
. – p.5/??
Conseguenze della PEA: Compressio
S : sorgente modellata con una sequenza di n v.c.
X1 , . . . , Xn i.i.d. con alfabeto X
X n : insieme sequenze di lunghezza n emesse da S .
L’insieme X n può essere partizionato in:
Anε : insieme delle sequenze tipiche (insieme tipico),
costituito da tutte le sequenze (x1 , . . . , xn ) ∈ X n t.c.
2−n(H(X)+ε) ≤ P (x1 , . . . , xn ) ≤ 2−n(H(X)−ε)
. – p.5/??
Conseguenze della PEA: Compressio
S : sorgente modellata con una sequenza di n v.c.
X1 , . . . , Xn i.i.d. con alfabeto X
X n : insieme sequenze di lunghezza n emesse da S .
L’insieme X n può essere partizionato in:
Anε : insieme delle sequenze tipiche (insieme tipico),
costituito da tutte le sequenze (x1 , . . . , xn ) ∈ X n t.c.
2−n(H(X)+ε) ≤ P (x1 , . . . , xn ) ≤ 2−n(H(X)−ε)
Ānε : complemento di Anε in X n
. – p.5/??
Dimostreremo
L’insieme Anε ha probabilità ≈ 1,
. – p.6/??
Dimostreremo
L’insieme Anε ha probabilità ≈ 1,
NON contiene quasi tutte le sequenze: Per codificare
sequenze sorgente, non servono lg |X |n bits, sono
sufficienti ≈ nH(X) ≈ |Anε | bits
. – p.6/??
Proprietà delle sequenze tipiche
Teorema
(n)
1. (x1 , ..., xn ) ∈ Aε
⇒ H(X) − ε < − n1 lg P (x1 , . . . , xn ) < H(X) + ε
2. P (Aεn ) > 1 − ε, per n suff. grande
(n)
3. |Aε | < 2n(H(X)+ε)
(n)
4. |Aε | > (1 − ε) · 2n(H(X)−ε) , per n suff. grande
. – p.7/??
Dim. 2 (P (Aεn ) > 1 − ε, per n suff. grande):
1
PEA ⇒ − lg P (X1 , . . . , Xn ) → H(X) per n → ∞
n
⇒ ∀δ > 0 ∃ n0 t.c. ∀n > n0
1
Pr − lg P (x1 . . . , xn ) − H (X) < ε > 1 − δ.
n
Prendendo
δ = ε abbiamo
1
Pr − n lg P (x1 , ..., xn ) − H (X) < ε > 1 − ε
⇒ P (Anε ) > 1 − , per n suff. grande.
. – p.8/??
Dim. 3 (P (Aεn ) > 1 − ε):
1 =
X
x∈X n
P (x) ≥
X
P (x) ≥
(n)
x∈A
X
2−n(H(X)+ε)
(n)
x∈A
(n) = Aε · 2−n(H(X)+ε)
⇒
(n) −n(H(X)+ε)
≤1
Aε · 2
⇒
(n) Aε ≤ 2n(H(X)+ε)
. – p.9/??
Dim. 4 (|Aε(n) | > (1 − ε) · 2n(H(X)−ε) , per n suff. grande):
Per n suff. grande abbiamo
(n)
1 − ε < P (Aε ) dalla 2
(n) −n(H(X)−ε)
≤ Aε · 2
dalla def. di sequenze tipiche
⇒
(n) Aε ≥ (1 − ε) · 2n(H(X)−ε)
. – p.10/??
Sequenze tipiche e Compressione dat
Vediamo come utilizzare l’insieme tipico per la codifica.
Partizioniamo l’insieme di tutte sequenze negli insiemi
Anε e Ānε
. – p.11/??
Sequenze tipiche e Compressione dat
Vediamo come utilizzare l’insieme tipico per la codifica.
Partizioniamo l’insieme di tutte sequenze negli insiemi
Anε e Ānε
Ordiniamo ciascuno dei due insiemi Anε e Ānε (ad es. in
modo lessicografico)
. – p.11/??
Sequenze tipiche e Compressione dat
Vediamo come utilizzare l’insieme tipico per la codifica.
Partizioniamo l’insieme di tutte sequenze negli insiemi
Anε e Ānε
Ordiniamo ciascuno dei due insiemi Anε e Ānε (ad es. in
modo lessicografico)
(n)
Rappresentiamo ciascuna sequenza x ∈ Aε con il suo
rango nell’ordinamento.
. – p.11/??
Sequenze tipiche e Compressione dat
Vediamo come utilizzare l’insieme tipico per la codifica.
Partizioniamo l’insieme di tutte sequenze negli insiemi
Anε e Ānε
Ordiniamo ciascuno dei due insiemi Anε e Ānε (ad es. in
modo lessicografico)
(n)
Rappresentiamo ciascuna sequenza x ∈ Aε con il suo
rango nell’ordinamento.
Il numero di bit necessari per codificare le sequenze
tipiche è
l
m
dlg |Anε |e ≤ lg 2n(H(X)+ε) < n(H(X) + ε) + 1.
. – p.11/??
Sequenze tipiche e Compressione dat
Vediamo come utilizzare l’insieme tipico per la codifica.
Partizioniamo l’insieme di tutte sequenze negli insiemi
Anε e Ānε
Ordiniamo ciascuno dei due insiemi Anε e Ānε (ad es. in
modo lessicografico)
(n)
Rappresentiamo ciascuna sequenza x ∈ Aε con il suo
rango nell’ordinamento.
Il numero di bit necessari per codificare le sequenze
tipiche è
l
m
dlg |Anε |e ≤ lg 2n(H(X)+ε) < n(H(X) + ε) + 1.
. – p.11/??
(n)
Rappresentiamo ciascuna sequenza y ∈ Āε con il suo
rango nell’ordinamento.
. – p.12/??
(n)
Rappresentiamo ciascuna sequenza y ∈ Āε con il suo
rango nell’ordinamento.
Il numero di bit necessari per codificare le sequenze
non tipiche è
m
l
(n)
lg |Āε | ≤ dlg(|X |n )e ≤ n lg(|X |) + 1.
. – p.12/??
(n)
Rappresentiamo ciascuna sequenza y ∈ Āε con il suo
rango nell’ordinamento.
Il numero di bit necessari per codificare le sequenze
non tipiche è
m
l
(n)
lg |Āε | ≤ dlg(|X |n )e ≤ n lg(|X |) + 1.
. – p.12/??
CODICE
Codifica sequenze tipiche: alla sequenza binaria
corrispondente aggiungiamo 0 come prefisso
. – p.13/??
CODICE
Codifica sequenze tipiche: alla sequenza binaria
corrispondente aggiungiamo 0 come prefisso
Codifica sequenze non tipiche: alla sequenza binaria
corrispondente aggiungiamo 1 come prefisso
. – p.13/??
CODICE
Codifica sequenze tipiche: alla sequenza binaria
corrispondente aggiungiamo 0 come prefisso
Codifica sequenze non tipiche: alla sequenza binaria
corrispondente aggiungiamo 1 come prefisso
A ciascuna sequenza sorgente sia associata una parola
codice distinta.
. – p.13/??
CODICE
Codifica sequenze tipiche: alla sequenza binaria
corrispondente aggiungiamo 0 come prefisso
Codifica sequenze non tipiche: alla sequenza binaria
corrispondente aggiungiamo 1 come prefisso
A ciascuna sequenza sorgente sia associata una parola
codice distinta.
Lunghezza parole codice é ≤:
n(H(X) + ε) + 2
per ogni sequenza tipica
n lg |X | + ∈ per ogni sequenza non tipica
. – p.13/??
CODICE
Codifica sequenze tipiche: alla sequenza binaria
corrispondente aggiungiamo 0 come prefisso
Codifica sequenze non tipiche: alla sequenza binaria
corrispondente aggiungiamo 1 come prefisso
A ciascuna sequenza sorgente sia associata una parola
codice distinta.
Lunghezza parole codice é ≤:
n(H(X) + ε) + 2
per ogni sequenza tipica
n lg |X | + ∈ per ogni sequenza non tipica
Lunghezza media del codice?
. – p.13/??
Teorema di Codifica Sorgente
Teorema
Sia X n sequenza di v.c. i.i.d. con d.d.p. P (x).
Sia ε > 0
Esiste un codice che mappa sequenze sorgente di
lunghezza n in stringhe binarie in modo che la codifica sia
1-1 e
1
E
l (X n ) ≤ H (X) + ε,
n
per n sufficientemente grande.
. – p.14/??
Dim. Teorema di Codifica Sorgente
Sia l(xn )= lunghezza codifica seq. sorgente xn
n
E[l(X )] =
X
P (xn )l(xn )
xn
=
X
P (x )l(x ) +
X
P (xn )[2 + n(H(X) + ε)]
n
n
(n)
P (xn )l(xn )
(n)
xn ∈Aε
≤
X
xn ∈Āε
(n)
xn ∈Aε
+
X
P (xn )[2 + n lg |X |]
(n)
xn ∈Āε
= [2 + n(H(X) + ε)]P
(n)
Aε
(n) + [2 + n lg |X |]P Aε
. – p.15/??
Dim. Teorema di Codifica Sorgente
(n) E[l(X n )] ≤ [2 + n(H(X) + ε)]P
+ [2 + n lg |X |]P Aε
(n) (n)
= 2 + n(H(X) + ε)P Aε
+ n lg |X |P Aε
(n)
Aε
Con
n
o
(n)
P Aε
≤1
n
o
n
o
(n)
(n)
P Āε
= 1 − P Aε
< 1 − (1 − ε) = ε
Allora
E [l (X n )] ≤ n (H (X) + ε) + n lg |X | ε + 2
. – p.16/??
Da
E [l (X n )] ≤ n (H (X) + ε) + n lg |X | ε + 2
dividendo per n si ottiene:
1
2
n
E
l (X ) ≤ H (X) + ε + ε lg |X | + .
n
n
Ponendo ε0 = ε + ε lg |X | + n2 si ha
1
E
l (X n ) ≤ H (X) + ε0 .
n
. – p.17/??
Il Teorema Codifica Sorgente implica che possiamo
codificare le sequenze sorgente di lunghezza n usando
in media nH(X) bit.
Quindi, H(X) bit per simbolo sorgente
In seguito vedremo che non è possibile fare di meglio
. – p.18/??
Codifica Sorgente: parte inversa
Teorema di Codifica Sorgente: possiamo codificare le
sequenze X n usando in media nH(X) bit.
. – p.19/??
Codifica Sorgente: parte inversa
Teorema di Codifica Sorgente: possiamo codificare le
sequenze X n usando in media nH(X) bit.
Possiamo fare di meglio?, Esiste un insieme più piccolo
dell’insieme tipico che concentra la massa
probabilistica?
. – p.19/??
Codifica Sorgente: parte inversa
Teorema di Codifica Sorgente: possiamo codificare le
sequenze X n usando in media nH(X) bit.
Possiamo fare di meglio?, Esiste un insieme più piccolo
dell’insieme tipico che concentra la massa
probabilistica?
Def. Dato δ > 0, sia Bδ(n) ⊆ X n un insieme con
Pr
n
(n)
Bδ
o
>1−δ
. – p.19/??
Codifica Sorgente: parte inversa
Teorema di Codifica Sorgente: possiamo codificare le
sequenze X n usando in media nH(X) bit.
Possiamo fare di meglio?, Esiste un insieme più piccolo
dell’insieme tipico che concentra la massa
probabilistica?
Def. Dato δ > 0, sia Bδ(n) ⊆ X n un insieme con
Pr
(n)
Dimostreremo: Bδ
n
(n)
Bδ
o
>1−δ
deve avere un’intersezione
(n)
(n)
(n)
significativa con Aε ⇒ |Bδ | ≈ |Aε |
. – p.19/??
Codifica Sorgente: parte inversa
Teorema Siano X1 , . . . , Xn i.i.d. con d.d.p P (x). Per ogni
δ < 1/2 e δ 0 > 0 si ha
n
o
1
(n)
(n)
Pr Bδ
> 1 − δ ⇒ lg |Bδ | > H(X) − δ 0 ,
n
per n suff. grande.
Dim.
n
(n)
(n)
1 ≥ Pr Aε ∪ Bδ
o
n
n
o
n
o
(n)
(n)
(n)
(n)
= Pr Aε
+ Pr Bδ
− Pr Aε ∩ Bδ
n
o
(n)
(n)
> 1 − ε + 1 − δ − Pr Aε ∩ Bδ
n
(n)
o
(n)
⇒ Pr Aε ∩ Bδ
o
>1−ε−δ
. – p.20/??
Inoltre risulta
n
o
(n)
(n)
Pr Aε ∩ Bδ
=
≤
X
(n)
P (xn )
(n)
xn ∈Aε ∩Bδ
X
(n)
2−n(H(X)−ε)
(n)
xn ∈Aε ∩Bδ
(n)
(n)
= |Aε ∩ Bδ | · 2−n(H(X)−ε)
(n)
≤ |Bδ | · 2−n(H(X)−ε) .
. – p.21/??
Codifica Sorgente: parte inversa
Quindi
(n)
(n)
(n)
1 − ε − δ < P (Aε ∩ Bδ ) < |Bδ | · 2−n(H(X)−ε)
(n)
⇒ |Bδ | > (1 − ε − δ) 2n(H(X)−ε)
⇒
1
n
(n)
lg |Bδ | > (H (X) − ε) +
lg(1−ε−δ)
n
Scegliendo ε suff. piccolo ed n suff. grande si ha
ε − n1 lg (1 − ε − δ) = δ 0
⇒
1
n
(n)
lg |Bδ |
> H (X) − δ 0 .
. – p.22/??