Embed Size (px)
Citation preview
Fundamentos deTelecomunicações
LEEC_FT4,5&6: Teoria da Informação –Codificação de FonteProfessor Victor [email protected]
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 2
Lição 4§ Informação e Entropia§ Introdução
§ Incerteza, probabilidade e informação
§ Modelo de uma fonte discreta sem memória§ Medida de informação
§ Definição e unidade de medida§ Propriedades
§ Entropia§ Definição e unidade de medida§ Entropia da fonte binária
§ Função de entropia§ Propriedades
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 3
Introdução§ Acontecimento frequente§ “Grande” probabilidade de ocorrência § Baixa incerteza quanto à sua ocorrência
§ Acontecimento raro§ Baixa probabilidade de ocorrência § Elevada incerteza quanto à sua ocorrência
§ Ocorrência de um acontecimento raro ⇒ ganho de informação elevado§ Ocorrência de um acontecimento frequente ⇒
ganho de informação reduzido
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 4
Incerteza, Probabilidade & Informação
Incerteza ↑
Probabilidade ↓
Informação ↑
⇓
⇓
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 5
§ Fonte discreta M-ária§ Alfabeto A de M símbolos
§ Distribuição de probabilidade dos símbolos
§ Fonte sem memória
§ Símbolos estatisticamente independentes
Fonte Discreta sem Memória
{ }Mmmm ,,, 21 K=A
( ) 1 : ,,2,1 , Pr1
=== ∑=
M
kkkk pMkpm K
( ) ( ) ( ) jkjkkkjk ppmmpmmmMjk ⋅=⇒===∀ ,Pr PrPr : ,,2,1, K
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 6
Informação§ Definição (para uma fonte M-ária sem memória)
§ Variável aleatória
§ Unidade de medida§ 1 bit: informação associada à ocorrência de um símbolo binário
com probabilidade 1/2
§ Propriedades§
§
§
[ [ ( ) Mkp
mIIk
k ,,2,1 , 1
log , ,0 : 2 K=
=+∞→A
0≥I( ) ( )jkjk mImIpp <⇒>
( ) ( ) ( )jkjk mImImmI +=,
AI
0 1 Ap
1
5.0
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 7
Entropia de uma Fonte Discreta sem Memória§ Definição
§ Valor expectável (média) da variável aleatória I
§ Unidade de medida
§ bit/símbolo
( ) { } ∑∑==
−=
==
M
kkk
M
k kk pp
ppIE
12
12 log
1logH A
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 8
Entropia de uma Fonte Binária sem Memória§ Fonte binária
§ Função de entropia
§ Propriedades§ Mínima e igual a zero quando um dos símolos ocorre com
probabilidade 1
§ Máxima e igual a 1 quando os símbolos são equiprováveis
{ } ppppmm −=== 1 , : , 2121A
( ) ( ) ( ) ( )ppppp −−−−= 1log1logH 22
0 0.5 1
1
( )pH
p
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 9
Lição 5§ Propriedades da entropia de uma fonte M-ária
sem memória
§ Extenção da Fonte Discreta sem Memória§ Definição
§ Entropia da extensão de ordem K
§ Códigos de comprimento variável§ Comprimento médio
§ Exemplos
§ Desigualdade de Kraft
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 10
Entropia – Propriedades0 ≤ H (A ) ≤ log2 M
§ H (A ) é mínima (Hmin = 0) sse algum dos símbolos de A ocorrer com probabilidade 1 (todos os restantes M – 1 terão probabilidade de ocorrência 0)
§ H (A ) é máxima (Hmax = log2 M ) sse todos os símbolos de A forem equiprováveis, i.e.,
p1 = L = pM = 1/M
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 11
Extensão da Fonte Discreta sem Memória§ Alfabeto da “extensão de 1ª ordem ” (fonte
original): A = A 1
§ Alfabeto e distribuição de probabilidade da extensão de 2ª ordem (produto cartesiano de Acom A): A 2 = A × A§ Exemplo
=
= →
11100100
10
4
3
2
1
2
mmmm
AA
=====
=
∑∑
→
111100100
: 1
10
:2244
2133
1222
2111
2 2
1
m
m
qpqm
ppqmppqm
pqm
ppp
AA
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 12
Entropia da Extensão da Fonte Discreta sem Memória
§ H (A ): entropia de uma fonte discreta semmemória com alfabeto A.
§ A K : extensão de ordem K do alfabeto A.
A K = A × A × L × A
§ Entropia da extensão de ordem K :
H (A K ) = K H (A )
K
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 13
Extensão da Fonte, Entropia e Comprimento do Código
5.30
5.22
5.25
5.29
5.33
5.40
5.25
5.33
5.50
6
Lmed = L /K
5352.0952.0937 1010
4746.8946.8937 99
4241.6841.6837 88
3736.4736.4737 77
3231.2631.2637 66
2726.0526.0537 55
2120.8420.8437 44
1615.6315.6337 33
1110.4210.4237 22
65.215.2137 11
Llog2 M KH (A K )#A K = M KK
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 14
Códigos de Comprimento Variável – Comprimento Médio§ Codificação§ Símbolo fonte mk com probabilidade pk → palavra de
código ck com lk bits
§ Comprimento médio do código – Lmed = ∑ lk pk
§ Descodificação unívoca § ck → mk sem ambiguidade
§ Descodificação instantânea
M
k = 1
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 15
Exemplos
unívocounívoco
instantâneo
de prefixo
não unívoco
unívoco
instantâneoH (A )
Lmed1.8751.7501.2502.0001.750
011111111110.125m4
01111000100.125m3
01101010.250m2
000000.500m1
código
IV
código
III
código
II
código
I
probabilidade
de
ocorrência
símbolo
fonte
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 16
Desigualdade de KraftExiste um código binário com palavras de comprimento lk
sseξ = ∑ 2 –lk ≤ 1
§ Exemplo§ Dado o código de prefixo {0, 10, 110, 111}, verifica-se a
desigualdade de Kraft, ξ = 2 –1 + 2 –2 + 2×2 –3 = 1 ≤ 1
§ A distribuição de comprimentos {1, 2, 3, 3} verifica adesigualdade de Kraft. Então, existe um código unívocoinstantâneo.
M
k = 1
1
010
10
1
00011
010
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 17
Lição 6§ 1º Teorema de Shannon
§ Códigos de Huffman§ Algoritmo de Huffman
§ Codificação de Lempel – Ziv§ Algoritmo de Lempel – Ziv
§ Codificação, codebook (“dicionário”)
§ Descodificação
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 18
1º Teorema de Shannon
Teorema da Codificação de Fonte§ Seja H (A ) a entropia de uma fonte discreta sem
memória e Lmed o comprimento médio das palavras de um eventual código para a fonte A.§ Se, para qualquer ε > 0, Lmed = H (A ) + ε , então existe um
código unívoco e instantâneo para a fonte A.
§ Pelo contrário, se Lmed < H (A ), então não existe qualquer código unívoco e instantâneo para a fonte A.
§ Eficiência do código§ η = H (A ) / Lmed
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 19
Códigos de Huffman (1952) Códigos de Redundância Mínima
0.15m 51103
0.200.15m 41113
0.250.250.20m 3002
0.450.300.250.25m 2012
1.000.550.450.300.25m 1102
Distribuição de probabilidadeSímbolos fonte
Palavras de código
Comprimento das palavras de código
0
1 0
1 0
1 0
1
5
54
541
43
32
2 1
Lmed = 2.30 H (A ) = 2.29 η = 99.6 %
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 20
Codificação de Lempel – Ziv (1978)
§ O conhecimento da distribuição deprobabilidade da fonte não é necessário§ Faz uso da correlação entre símbolos
adjacentes § Constitui norma para compressão de ficheiros § Implementação§ Percorrer a sequência de dados dividindo-a em
segmentos constituídos pelas subsequências mais curtas ainda não detectadas
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 21
Algoritmo de Lempel – ZivIlustração com a sequência 000101110010100101...§ Os símbolos 0 e 1 estão inicialmente armazenados
§ Subsequências armazenadas: 0, 1§ Dados para analisar: 000101110010100101...
§ Analisando da esquerda para a direita, a subsequência mais curta ainda não detectada é 00§ Subsequências armazenadas: 0, 1, 00§ Dados para analisar: 0101110010100101...
§ Repetindo, a subsequência mais curta ainda não detectada é 01§ Subsequências armazenadas: 0, 1, 00, 01§ Dados para analisar: 01110010100101...
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 22
Algoritmo de Lempel – ZivCodificação3. 000101110010100101...
4. 0101110010100101...
5. 01110010100101...
6. 10010100101...
7. 010100101...
8. 100101...
9. 101...
1101110010000100100100110010Blocos binários codificados
62614121421211Representações numéricas
10110001010011010010subsequências
987654321Posições numéricas
LEEC_FT - Lições 4,5&6 Fundamentos de Telecomunicações Slide 23
Algoritmo de Lempel – ZivDescodificaçãoSequência original: 000101110010100101... Sequência codificada: 0010 0011 1001 0100 1000 1100 1101...
Descodificando: 1 0 1 1 4 1 2 0 4 0 6 0 6 1...
Indo ao code book:
inovaçãoapontador
10110001010011010010subsequências
987654321Posições numéricas
00 01 011 10 010 100 101
![l h j - ruthenia.ru · БИБЛИОГРАФИЯ ТРУДОВ С.Ю. НЕКЛЮДОВА K _ j ] _ v _ \ b q d e, i j h n _ k k h j, ^ h d l h j h e h ] b q _ k d b o m, \ l h j](https://img.document.onl/doc/110x75/5f9f1c65f4ec8f37725da03a/l-h-j-k-j-.jpg)
![b‚···{‚–– QL··⁄‚–t⁄ · ’q]¤·⁄ ƒ⁄'K dÄ⁄ ‹s ƒLs uNLo QKc QL⁄‚–t⁄ PflS…–K Kc„ ‹⁄mSfi.‹flü⁄‘–K‚’tNKd–K‘d‚b–K—K‚o—L⁄tSg](https://img.document.onl/doc/110x75/5c18b74209d3f27a578cd55b/b-qlt-q-fk-dae-s-fls.jpg)
![RQG 7RXULVP +(5,7$*( DV D %8,/'(5 RI 3($&( G : K E ? > B ? d Z d K L J H B L ? E V … · 2019-09-02 · : [ k l j Z d l u ^ h e ` g u [ u l v \ u k e Z g u g Z Z ^ j _ k VHFUHWDU\JHQHUDO#IRQGD]LRQH](https://img.document.onl/doc/110x75/5ec4067312714676cc4ad9fd/rqg-7rxulvp-57-dv-d-85-ri-3-g-k-e-b-d-z-d-k-l-j-h.jpg)
![G H L G : : ; ? L Dnv-imc.edukit.zt.ua/Files/downloadcenter/notnaabetka.pdf · 12 K I B K H D < B D H J B K L : G H 2 E 1 L ? J : L M J B 1. E m q m d 1. : g l h e h ] y m d j Z g](https://img.document.onl/doc/110x75/5f7bfca4d00b511cb177779c/g-h-l-g-l-dnv-imc-12-k-i-b-k-h-d-b-d-h-j-b-k-l-g-h-2-e-1-l-j-.jpg)
![Ú q | Ih )#$#h Ih ).$#h...y ó 7  ª 3 L i B O ´  Q 8 ÷ é ] q : ¥ ¨ q o  c N L ó 7  L c 3 ± n t L i B L i < ] H % ù k s k O ´ ± k k ÷ ¸ k ª B  L](https://img.document.onl/doc/110x75/5f9b0515a7a5554a215f3d8d/-q-ih-h-ih-h-y-7-3-l-i-b-o-q-8-q-.jpg)
![CG 4214 - Junho 2018 · 2018. 10. 3. · EdZK ^dh K^ W ^Yh/^ ^ ^ Z X :K K DKZ/D _ K P v ] Ì } ^ } ] o ' } ^ · KEdZ dK ' ^d K v Ñ ð î l î ì í ð r h ^ î ð, l d E K ^/ l^](https://img.document.onl/doc/110x75/60e9a2c2ce1e546aca0550a5/cg-4214-junho-2018-2018-10-3-edzk-dh-k-w-yh-z-x-k-k-dkzd-k-p.jpg)
