Comunicação e redes

Informação Mútua
 I(X; Y) – Informação mútua --> I(X; Y) = 0 se X e Y não tem nenhuma relação.
 Ou seja, se X e Y são independentes.
Se I(X; Y) > 0, como comparamos H(X) e H(X|Y)?
 H(X) > H(X|Y)
 Conhecer Y reduz a incerteza sobre X.
Definição: I(X; Y) = H(X) – H(X|Y)
Transmissão com erros
Códigos de correção garantem corrigir erros em um numero determinado de bits tanto nos dados originais quanto nos bits de redundância inseridos.
Dado canal com arbitrariamente grande probabilidade de erro:
• Conseguimos uma probabilidade arbitrariamente grande de transmissão correta (mas não
100%)
• Com palavras código arbitrariamente grandes, ou seja, redundância arbitrariamente grande
• Restrição 1: Quanto tempo demora para transmitir???
• Prova que existe um código, mas não qual código
• Prova teórica e um limite mínimo
• Restrição 2: Há que descobrir o código!
Quanto mais erros, mais lento é a transmissão, porque precisamos de mais redundância.
Codificador de fonte
Representar eficientemente os símbolos de uma fonte por cadeias de bits. Se alguns símbolos da fonte forem conhecidamente mais prováveis que outros, podemos atribuir palavras-código menores a símbolos freqüentes e palavras-código longas a símbolos raros.
Exemplo: Algoritmo de Huffman
•

Cada símbolo é representado por uma palavracódigo Ci (array de bits) diferente de tamanho li • Códigos de tamanho fixo: mesmo li para todos
• Códigos de tamanho variável: li em geral diferentes

Entropia é o limite teórico para a média dos comprimentos das palavras código
H(S) > Crg
Conexões fortes e fracas
•
•

As ligações fortes (amigos) fecham sobre si mesmas, reduzindo as oportunidades
São as ligações fracas (ou de conhecidos) que possibilitam que a rede de contatos se expanda e amplie as oportunidades