Slide Codificação de Fonte Teoria de Informação-2021 1

2021-1 IF65F – Transmissão de Dados Prof. Eduardo Alves Hodgson hodgson@utfpr.edu.br Codificação de Fonte Teoria de Informação UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Câmpus Cornélio Procópio IF65F Transmissão de Dados 2 Tópicos ❑ Codificação de fonte ❑ Teoria de informação e entropia ❑ Código de prefixo ❑ Codificação de Huffman IF65F Transmissão de Dados 3 Codificação Nas aulas passadas vimos os blocos abaixo: Transmissor digital IF65F Transmissão de Dados 4 Codificação Hoje vamos ver Codificação de Fonte: Transmissor digital IF65F Transmissão de Dados 5 Revisão -Pulse Code Modulation Modulação por codificação de pulso (PCM - Pulse code modulation) Em PCM, um sinal de mensagem é 1) amostrado, 2) quantizado em 𝐿 níveis de amplitude, 3) codificado em 𝑹 bits, onde 𝑹 = 𝐥𝐨𝐠𝟐(𝑳) 4) estes bits são convertidos em sinais elétricos para transmissão em um canal. Transmissor digital Transmissor Digital (1) (2) (3) (4) IF65F Transmissão de Dados 6 Codificação Porém, este modelo PCM é simplificado. A etapa (3) codificação de bits é dividida em duas etapas importantes em transmissão digital prática: 1) Codificação de fonte : Reduz ao máximo o número de bits por amplitude discreta, ou seja, um valor menor que 𝑹 = 𝐥𝐨𝐠𝟐(𝑳). 2) Codificação de canal: Adiciona bits redundantes para detectar e corrigir erros de bits no receptor (próxima aula). Transmissor digital Transmissor Digital (1) (2) (3) (4) IF65F Transmissão de Dados 7 Codificação de fonte O processo de representação eficiente de dados gerados por uma fonte discreta (quantizada) é denominado codificação de fonte. Ao invés de alocar 𝑅 bits para todos símbolos da fonte... 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 Histograma do sinal de áudio do lab02 101001 010111 011101 010011 IF65F Transmissão de Dados 8 Codificação de fonte O processo de representação eficiente de dados gerados por uma fonte discreta (quantizada) é denominado codificação de fonte. Ao invés de alocar 𝑅 bits para todos símbolos da fonte, a codificação de fonte consiste em atribuir: • palavras-código curtas (poucos bits) a símbolos fonte frequentes e • palavras-código longas a símbolos raros. 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 0 001 011 010 101 110 000 100 111 1 Histograma do sinal de áudio do lab02 1 01 011101 010011 IF65F Transmissão de Dados 9 Codificação de fonte O objetivo da Codificação de Fonte é: O desenvolvimento de um codificador de fonte eficiente que satisfaça dois requisitos funcionais: 1. palavras-código (codeword) produzidas na forma binária; 2. código fonte unicamente decodificável, de modo que a sequência original possa ser reconstruída a partir da sequência binária codificada. Ou seja, o decodificador precisa entender quando termina uma palavra- código, já que podem ter tamanhos diferentes de palavras-códigos (em quantidade de bits). Objetivos 5 4 3 2 1 0 - 0 001 011 010 101 110 000 100 111 1 IF65F Transmissão de Dados 10 Codificação de fonte O objetivo da Codificação de Fonte é: O desenvolvimento de um codificador de fonte eficiente que satisfaça dois requisitos funcionais: 1. palavras-código (codeword) produzidas na forma binária; 2. código fonte unicamente decodificável, de modo que a sequência original possa ser reconstruída a partir da sequência binária codificada. Ou seja, o decodificador precisa entender quando termina uma palavra- código, já que podem ter tamanhos diferentes de palavras-códigos (em quantidade de bits). Objetivos 5 4 3 2 1 0 - 0 001 011 010 101 110 000 100 111 1 No exemplo ao lado, por exemplo, se o decodificador receber o bit 0, ele não vai saber se recebeu a palavra-código 0, ou o início de 001, 011, 010 ou 000. Logo, não é unicamente decodificável. IF65F Transmissão de Dados 11 Codificação de fonte Suponha uma fonte discreta (quantizada) com 𝑲 símbolos discretos 𝒔𝒌 diferentes. O tamanho médio de palavra código ത𝐿 de uma fonte é ത𝐿 = ෍ 𝑘=0 𝐾−1 𝑝𝑘𝑙𝑘 bits • 𝑝𝑘 é a probabilidade de ocorrer cada símbolo 𝑠𝑘 é, sendo 𝑘 de 0 a 𝐾 − 1. • 𝒍𝒌 é o tamanho da palavra código de cada símbolo 𝑠𝑘 em bits. Exemplo: Tamanho médio da palavra código ത𝐿 do código fonte abaixo: 𝑠0 → 01, 𝑝0 = 0,6 𝑠1 → 001, 𝑝1 = 0,2 𝑠2 → 011, 𝑝2 = 0,2 ത𝐿 = 𝑝0𝑙0 + 𝑝1𝑙1 + 𝑝2𝑙2 = 0,6 2 + 0,2 3 + 0,2(3) = 2,4 bits Tamanho médio da palavra código IF65F Transmissão de Dados 12 Codificação de fonte Eficiência da codificação A eficiência da codificação é dada por: 𝜂 = 𝐿𝑚𝑖𝑛 ത𝐿 Onde 𝐿𝑚𝑖𝑛 é o menor tamanho possível de ഥ𝑳. Como obter 𝐿𝑚𝑖𝑛? A resposta está no primeiro teorema de Shannon, chamado de teorema da codificação de fonte: Teorema 1: Dada uma fonte discreta sem memória, o tamanho médio de palavra-código ത𝐿 para qualquer codificação de fonte sem distorção é limitado por ത𝐿 ≥ 𝐻(𝒮) Onde 𝐻(𝒮) é a entropia da fonte discreta. Ou seja: 𝐿𝑚𝑖𝑛 = 𝐻(𝒮) IF65F Transmissão de Dados 13 Tópicos ❑ Codificação de fonte ❑ Teoria de informação e entropia ❑ Código de prefixo ❑ Codificação de Huffman IF65F Transmissão de Dados 14 Teoria da Informação No contexto de telecomunicações, a teoria da informação de Shannon (1948) responde duas questões fundamentais: 1. O número mínimo de bits 𝐿𝑚𝑖𝑛 de uma fonte discreta por meio da entropia de Shannon 𝐻(𝒮). 2. Em um canal ruidoso, qual a taxa máxima de informação em bps à qual a transmissão de informação pode ocorrer sem erros, conhecida como capacidade do canal (aula 15). IF65F Transmissão de Dados 15 Teoria da Informação Entropia de Shannon Considere uma fonte de informação discreta sem memória (os símbolos são estatisticamente independentes) com 𝐾 símbolos: 𝒮 = {𝑠0, 𝑠1, … , 𝑠𝑘−1} Por exemplo, um sinal de áudio quantizado em 𝐾 símbolos discretos. Cada símbolo possui uma probabilidade 𝑝𝑘 de ocorrer, onde a soma de todas probabilidades é igual a 1: ෍ 𝑘=0 𝐾−1 𝑝𝑘 = 1 Informação e entropia IF65F Transmissão de Dados 16 Teoria da Informação Logo, a entropia 𝐻 𝒮 é definida como o conteúdo médio de informação por símbolo da fonte: 𝐻 𝒮 = ෍ 𝑘=0 𝐾−1 𝑝𝑘 𝐼(𝑠𝑘) Onde 𝐼(𝑠𝑘) é considerado a quantidade de informação que obtenho ao ver o símbolo 𝑠𝑘 na saída da fonte (ex: quantizador): 𝐼 𝑠𝑘 = log2 1 𝑝𝑘 Quanto maior a probabilidade 𝑝𝑘, menor a quantidade de informação. Logo, a entropia é: 𝐻 𝒮 = ෍ 𝑘=0 𝐾−1 𝑝𝑘log2 1 𝑝𝑘 Informação e entropia IF65F Transmissão de Dados 17 Teoria da Informação Exemplos de quantidade de informação de duas notícias lidas no jornal: 1. “Amanhã ficará escuro depois do pôr do sol.” • Probabilidade de ocorrer ≈ 100% (𝑝0≈ 1). • Logo 𝐼 ≈ log2 1 𝑝0 ≈ log2 1 1 ≈ 0. Ou seja, zero informação. 2. “Foto de um buraco negro é revelada pela primeira vez na história.” • Probabilidade de ouvir antes de 2019? Perto de zero 𝑝1 ≈ 0 . • Logo, 𝐼 ≈ log2 1 𝑝1 ≈ ∞. Ou seja, muita informação. Informação e entropia IF65F Transmissão de Dados 18 Codificação de fonte Eficiência da codificação A eficiência da codificação é dada por: 𝜂 = 𝐿𝑚𝑖𝑛 ത𝐿 𝐿𝑚𝑖𝑛 = 𝐻 𝒮 = ෍ 𝑘=0 𝐾−1 𝑝𝑘log2 1 𝑝𝑘 Portanto, a entropia de uma fonte discreta estabelece um limite fundamental para a remoção de redundância de dados (bits redundantes). Existem códigos de fonte chamados de entropy codes justamente porque eles atingem a entropia, com uma eficiência 𝜂 = 1. IF65F Transmissão de Dados 19 Tópicos ❑ Codificação de fonte ❑ Teoria de informação e entropia ❑ Código de prefixo ❑ Codificação de Huffman IF65F Transmissão de Dados 20 Código de prefixo Código de prefixo é o código em que nenhuma palavra-código é prefixo de qualquer outra palavra código. • O “Código I” abaixo não é um código de prefixo porque 𝑠0 (0) é prefixo de 𝑠2 (00), e 𝑠1 (1) é prefixo de 𝑠3 (11), • O decodificador não vai conseguir distinguir se 0 é o símbolo 𝑠0 (0) ou parte da palavra-código de 𝑠2 (00). Incerteza, informação e entropia IF65F Transmissão de Dados 21 Código de prefixo Código de prefixo é o código em que nenhuma palavra-código é prefixo de qualquer outra palavra código. • Já no “Código II” nenhuma palavra-código é prefixo de outra. • O decodificador sempre vai saber quando terminou uma palavra- código neste caso. Tamanho médio de palavra-código de um código de prefixo: H 𝒮 ≤ ത𝐿 < H 𝒮 + 1 Incerteza, informação e entropia IF65F Transmissão de Dados 22 Código de prefixo Incerteza, informação e entropia Árvore de decisão no decodificador de prefixo para o “Código II”. • Se receber bit 0, já sabe que é 𝑠0. • Se receber bit 1, pode ser 𝑠1, 𝑠2 ou 𝑠3. • O decodificador espera por mais bits para decidir qual símbolo veio. IF65F Transmissão de Dados 23 Tópicos ❑ Codificação de fonte ❑ Teoria de informação e entropia ❑ Código de prefixo ❑ Codificação de Huffman IF65F Transmissão de Dados 24 Código de Huffman A codificação de Huffman atribui a cada símbolo discreto 𝑠𝑘 uma sequência de bits (palavra-código) de tamanho aproximadamente igual à quantidade de informação (ou ao inverso da probabilidade 𝑝𝑘) transportada pelo símbolo em questão. IF65F Transmissão de Dados 25 Código de Huffman Exemplo de criação de código de Huffman (dicionário do código): Considere um alfabeto (fonte discreta) com cinco símbolos 𝑠0 a 𝑠4 cujas probabilidades são dadas por: ALGORITMO IF65F Transmissão de Dados 26 Código de Huffman ALGORITMO 1. Os símbolos da fonte são listados em ordem decrescente de probabilidade. Aos dois símbolos com menor probabilidades são atribuídos a um “0” e a outro “1” (etapa de divisão). IF65F Transmissão de Dados 27 Código de Huffman ALGORITMO 1. Os símbolos da fonte são listados em ordem decrescente de probabilidade. Aos dois símbolos com menor probabilidades são atribuídos a um “0” e a outro “1” (etapa de divisão). 2. Combinamos estes dois símbolos em um “novo símbolo” com probabilidades somadas (0,1 + 0,1 = 0,2). A probabilidade no “novo símbolo” é colocada na lista de acordo com a ordem. IF65F Transmissão de Dados 28 Código de Huffman ALGORITMO 1. Os símbolos da fonte são listados em ordem decrescente de probabilidade. Aos dois símbolos com menor probabilidades são atribuídos a um “0” e a outro “1” (etapa de divisão). 2. Combinamos estes dois símbolos em um “novo símbolo” com probabilidades somadas (0,1 + 0,1 = 0,2). A probabilidade no “novo símbolo” é colocada na lista de acordo com a ordem. 3. Repetir até sobrar apenas 2 símbolos 0 e 1. IF65F Transmissão de Dados 29 Código de Huffman 1. Os símbolos da fonte são listados em ordem decrescente de probabilidade. Aos dois símbolos com menor probabilidades são atribuídos a um “0” e a outro “1” (etapa de divisão). 2. Combinamos estes dois símbolos em um “novo símbolo” com probabilidades somadas (0,1 + 0,1 = 0,2). A probabilidade no “novo símbolo” é colocada na lista de acordo com a ordem. 3. Repetir até sobrar apenas 2 símbolos 0 e 1. 4. A palavra-código de cada símbolo 𝑠𝑘 é o reverso dos bits vindo do estágio I seguindo as setas até o último estágio. ALGORITMO IF65F Transmissão de Dados 30 Código de Huffman • O tamanho médio da palavra-código é: ത𝐿 = ෍ 𝑘=0 𝐾−1 𝑝𝑘(𝑙𝑘) = ത𝐿 = 0,4 2 + 0,2 2 + 0,2 2 + 0,1 3 + 0,1 3 = 2,2 bits ALGORITMO IF65F Transmissão de Dados 31 Código de Huffman • O tamanho médio da palavra-código é: ത𝐿 = ෍ 𝑘=0 𝐾−1 𝑝𝑘(𝑙𝑘) = ത𝐿 = 0,4 2 + 0,2 2 + 0,2 2 + 0,1 3 + 0,1 3 = 2,2 bits • A entropia 𝐻 𝒮 , ou 𝐿𝑚𝑖𝑛 é: 𝐻 𝒮 = ෍ 𝑘=0 𝐾−1 𝑝𝑘log2 1 𝑝𝑘 = 0,4 log2 1 0,4 + 0,2 log2 1 0,2 + 0,2 log2 1 0,2 +0,1 log2 1 0,1 + 0,1 log2 1 0,1 = 2,12193 bits ALGORITMO log2x = log10x log102 IF65F Transmissão de Dados 32 Código de Huffman A eficiência é 𝜂 = 𝐿𝑚𝑖𝑛 ത𝐿 = 2,12193 2,2 = 0,9645 Outra informação de códigos de fonte é a variância 𝜎2 nos tamanhos da palavra- código, dado por: 𝜎2 = ෍ 𝑘=0 𝐾−1 𝑝𝑘 𝑙𝑘 − ത𝐿 2 ALGORITMO Ainda neste exemplo, 𝜎2 = 0,4 2 − 2,2 2 + 0,2 2 − 2,2 2 + 0,2 2 − 2,2 2 +0,1 3 − 2,2 + 0,1 3 − 2,2 2 = 0,16 IF65F Transmissão de Dados 33 Código de Huffman Exemplo 2: Se jogarmos o novo símbolo combinado na posição mais baixa, ao invés de mais alta, temos outro código: ALGORITMO ത𝐿 e 𝐻 𝒮 continuam iguais. Mas a variância do tamanho da palavra- código será bem maior: 𝜎2 = 0,4 1 − 2,2 2 + 0,2 2 − 2,2 2 + 0,2 3 − 2,2 2 +0,1 4 − 2,2 + 0,1 4 − 2,2 2 = 1,36 IF65F Transmissão de Dados 34 Código de Huffman Desvantagens do código de Huffman: 1. É necessário o conhecimento da probabilidade de cada símbolo (modelo probabilístico da fonte), o que nem sempre é de simples determinação. 2. Se tanto o transmissor quanto o receptor não possuírem o mesmo dicionário, este precisa ser enviado antes do início da comunicação, o que pode consumir banda de transmissão. Existem diversos padrões de codificação de fonte na literatura que contornam tais desvantagens. Porém, ao custo da redução da eficiência 𝜂 do código. Desvantagens IF65F Transmissão de Dados 35 Código de Huffman Exercício 10.11 Haykin: (a) A palavra-código média ത𝐿 do código da tabela abaixo pode ser reduzida? Compare com a entropia. (b) Se sim, construa um código de Huffman e (c) calcule o novo ത𝐿 e a eficiência 𝜂. (d) Codifique a sequência [𝑠1 𝑠3 𝑠0] em bits no seu novo código. (e) Se amostrar um fonte com 𝑓𝑠 = 20 kHz, qual será a taxa de transmissão média em bps para o código da tabela abaixo e para o código de Huffman da letra (b)? ത𝐿 = ෍ 𝑘=0 𝐾−1 𝑝𝑘(𝑙𝑘) = a 2; c 1,75 bits 𝐻 𝒮 = ෍ 𝑘=0 𝐾−1 𝑝𝑘log2 1 𝑝𝑘 = a 1,75 bits 𝜂 = 𝐻 𝒮 ത𝐿 = 1,0 𝑠𝑘 codeword 𝑝𝑘 𝑠0 00 0,5 𝑠1 01 0,125 𝑠2 10 0,125 𝑠3 11 0,25 e Código da tabela: 𝑅𝑏 = 𝑓𝑠ത𝐿 = 20.000 2 = 40 kbps, na média. Novo código 𝑅𝑏 = 𝑓𝑠ത𝐿 = 20.000 1,75 = 35 kbps, na média.