Introdução à TelemáticaTeoria da Informação

M.Sc. Engenharia de SistemasProf. Sérgio Campello

Informação

• O que é informação?

2

Informação

• Não há definição formal.• Capacidade de alterar: o ambiente, as

propriedades, as reações, etc.

3

Entropia

• Da química, mede o grau de desorganização do meio.

• Função para medir a quantidade de informação.

4

• Fonte de informação X. Valores {x1, x2,...,xN} e probabilidades {p1, p2, ... ,pN}.

•

• Se a fonte é binária temos:

• e

Entropia, ,

HሺXሻ = pn log 1pnN

n=1

HሺXሻ = p0 log 1p0 + p1 log 1p1

HሺXሻ = p log1p+ (1− p) log 11− p

• A entropia é máxima quando p = 1/2

Gráfico da entropia para uma fonte binária.

HሺXሻ = p log1p+ (1− p) log 11− p

Entropia

• A entropia é máxima quando p = 50%.• O que isso significa?• Fornecer uma informação com

probabilidade de ocorrência de 50% causa máxima entropia. O que isso quer dizer?

7

Entropia

• Se fornecemos uma informação que tem probabilidade zero de ocorrer não causamos nenhuma alteração no estado pois já se sabia que aquilo não ocorreria.

• Se fornecemos uma informação que tem probabilidade UM de ocorrer não causamos nenhuma alteração no estado pois já se sabia que aquilo IRIA ocorrer.

8

• Sugestão com p = 1/2 , extrai mais informação

• P{Xa = 1} = 0,19815 -> H(Xa) = 0,7182 bits

• P{Xb = 1} = 0,52132 -> H(Xb) = 0,9987 bits

Exemplo

Transporte da Informação

Transporte da Informação

11

• Modulação – adequação ao meio para o correto transporte da equação.

Informação

“onda” Modulada

Transporte da Informação

12

• AM – Modulação em amplitude• FM – Modulação em frequência

Transporte da Informação

13

• PM – Modulação em Fase

Modulação

• A modulação depende do meio físico de transmissão e dos objetivos da transmissão.

• Fibras ópticas, cabos metálicos, ar, água, etc.

• Digital x Analógica

14

Digital x Analógica

• O que quer dizer analógica?• O que quer dizer digital? Quando um sinal

é considerado digital?• Qual é mais preciso?• Qual é mais imune a ruídos?• Qual dá a melhor qualidade final?

15

Transmissão da informação digital

• Agora que sabemos que o formato digital é melhor para transmitir informações à distância, como proceder para transmitir a informação?

16

Codificação

• Vamos criar um código para transmitir a palavra: CAFÉ

• Regras– Símbolos com até 4 dígitos– Símbolos com até 4 dígitos binários– Os códigos são unicamente decifráveis?– Os códigos são ótimos?– Se conhecermos as probabilidades podemos

melhorar o código?

17

Código de huffman

• Ordenam-se os símbolos por ordem decrescente de probabilidade

• Agrupam-se os dois símbolos com menor probabilidade em um “super símbolo” com probabilidade igual a soma das probabilidades

• Se o alfabeto restante possuir dois ou mais símbolos volta-se ao primeiro passo.

• Percorre-se a árvore ordenada de símbolos atribuindo aleatoriamente 0 ou 1 a cada folha da árvore

18

Código de huffman - Exemplo

• {a,b,c,d} – {0.1, 0.25, 0.2, 0.45}• {d, b, c, a} - {0.45, 0.25, 0.2, 0.1} – ord.• {d, b, (a,c)} - {0.45, 0.25, 0.3}• {d, (a,c), b} - {0.45, 0.3, 0.25} – ord.• {d,((a,c),b)} - {0.45, 0.55}• Reordenando e reagrupando:• {((a,c),b,d)} – {1}

19

Código de huffman - Exemplo

• Os super símbolos vão sendo agrupados em árvore.

20

Código de huffman - Exemplo

• Atribui-se 1 ou 0 aleatoriamente a cada ramo ou folha.

21

Código de huffman - Exemplo

• Código final• D – 1• B – 00• C – 011• A - 010

22

Código de huffman - Exemplo

• Qual a vantagem deste código?• Ele é único?• É decodificável Unicamente?

23

Obtenção das probabilidades de uma língua

• Como obter a probabilidade de uma língua?

• O cálculo sempre retornará os mesmos resultados?

24

Proteção da informação

• Como proteger uma informação?• Como é a proteção atual da informação?• Como ela funciona?• É indecifrável?• Por que é segura?

25

Aplicação de Teoria da Informação

Ambiente de uso para comunicação e entretenimento.

• T9• Aplicativo Facilitador de Escrita (AFE)• Jogo da Memória• RSS

Funcionalidades

• 12 Botões grandes• Permite mudar a baseDo dicionário• Funciona com e sem previsão• 3 modos de funcionamento:

– Manual (SRO)– Automático– Joystick

• Possui teclado numérico•

Aplicativo T9

• Para cada botão é atribuídoum número. • Ao iniciar o ambiente é carregada a lista palavras em 2,1 segundos.• Para cada palavra é atribuídauma chave.• Um dicionário guarda o Mapeamento (Chave -> Palavra)

Implementação T9

Chave Palavra (valor)2272 Casa78376 Quero266432 Comida24672 Agora2272 Abra

Botão NúmeroABC 2DEF 3

GHI 4

... ...

WXYZ 9

• Com previsão, ao clicar em um botão é feita uma busca pela chave e retornado as palavras prováveis.

• Sem previsão (modo ditar), o usuário efetua vários cliques.

Funcionamento

Botão Letra Clique(com previsão)

Cliques (sem previsão)

Abc A 1 1Ghi G 1 1mnO O 1 3pqRs R 1 3Abc A 1 (Opcional) 1

• Feita na tela de opções: a seguir exemplo da palavra “casa” que possui a mesma chave de “abra” que é 2272.

Desambiguação

• Resultados satisfatórios• Fornecida interface para resolução de

problemas de ambiguidade• Dificuldades de utilização por pessoas

com redução do campo visual.

Análise do T9

• Denominado Aplicativo Facilitador de Escrita - AFE.

• Utiliza teoria da informação para diminuir o tempo de escrita

• Letras são sugeridas apenas no local central da tela

• Usuários apenas capazes de emitir um “sim” podem utilizar o aplicativo.

• O aplicativo adapta-se ao usuário, as palavras mais usadas passam a ser mais sugeridas.

Aplicativo de escrita com previsão de texto baseado em árvore

Árvore de busca

• Árvore ->

• Adição da palavra,“elastico” ->

• Configurações:– Modo automático ou Assistido– Fator de aprendizado

• Atalhos: K -> confirma, J-> desiste e L -> próxima palavra.

• A -> Digita a primeira letra• B -> Previsão com sugestão única• C -> Previsão com sugestão em grupo• D -> Busca no dicionário• E -> Modo ditar

Estados do aplicativo

B

A

C

D E

• A árvore seguinte é percorrida até escolher a letra.

• Pode ter a escolha automática

Estado A – primeira letra

• Neste teste teórico a quantidade de passos para escrita de uma palavra é diretamente proporcional a posição da letra no alfabeto

Escrita de palavras utilizando o modo Grupo-Subgrupo

Letra Passos Letra Passos Letra Passos Letra PassosB 3 C 4 Q 8 X 10A 2 A 2 U 9 I 6B 3 S 10 E 4 C 4A 2 A 2 R 9 A 2

O 8 R 9A 2

Total/Média

10/2,5 18/4,5 38/7,6 33/5,5

• Para a escrita de uma palavra é necessária uma quantidade média entre 4 e 5 passos.

Escrita de palavras utilizando árvore sem previsão

Letra Passos

Letra Passos

Letra Passos

Letra Passos

B 5 C 4 Q 5 X 5A 5 A 5 U 5 I 4B 5 S 4 E 5 C 4A 5 A 5 R 5 A 5

O 5 R 5A 5

Total/Média 20/5 19/4,5 25/5 28/4,6

• As palavras “CASA” e “QUERO”, por estarem na árvore de previsão necessitam de poucos passos para a escrita

Escrita de palavras utilizando árvore com previsão e sugestão de uma letra

Letra Passos Letra Passos Letra Passos Letra PassosB 5 C 4 Q 5 X 5A 1 A 2 U 1 I 2B 12 S 2 E 1 C 9A 5 A 1 R 2 A 5

O 3 R 5A 5

Total/Média 23/5,7 9/2,2 11/2,2 31/5,2

• Comparado com o método anterior, fica claro que, caso não seja possível a previsão, não ocorre perda de tempo com a sugestão de 5 letras (passos)

Escrita de palavras utilizando árvore com previsão e sugestão em grupo

Letra Passos Letra Passos Letra Passos Letra PassosB 5 C 4 Q 5 X 5A 4 A 2 U 1 I 3B 6 S 3 E 1 C 6A 3 A 2 R 4 A 5

O 2 R 5A 5

Total/Média 18/4,5 11/2,7 14/2,8 29/4,8

• Na primeira vez que apalavra foi digitada, pelo fato de não estar presente na árvore, sua digitação foi bastante custosa.

• Porém pelo aplicativo ir aprendendo, na 6º vez só é necessário 6 passos.

Previsão com aprendizado e sugestão de palavra

Letra Passos Letra Passos Letra Passos Letra Passos

1º Vez 2º Vez 5º Vez 6º Vez

X 5 X 5 X 5 X 5

I 3 I 2 I 1 I 1

C 6 C 3 C 3 C 0

A 5 A 1 A 1 A 0

R 5 R 0 R 0 R 0

A 5 A 0 A 0 A 0

Total/Média 29/4,8 11/1,8 10/1,6 6/1

Aplicativo