codificação conjunta fonte-canal utilizando codificadores

Figura 1
Tese apresentada à Pró-Reitoria de Pós-graduação e Pesquisa do Instituto
Tecnológico de Aeronáutica, como parte dos requisitos para obtenção do título
de Mestre em Ciências no Curso de Pós-Graduação em Engenharia Eletrônica e
Computação, Área de Concentração em Telecomunicações.
Mariana Olivieri Caixeta Altoé
CODIFICAÇÃO CONJUNTA FONTE-CANAL UTILIZANDO
CODIFICADORES UNIVERSAIS ADAPTATIVOS
Tese aprovada em sua versão final pelos abaixo assinados:
Prof. Dr. Marcelo da Silva Pinho
Orientador
Prof. Dr. Homero Santiago Maciel
Pró-Reitor de Pós-Graduação e Pesquisa
Campo Montenegro
São José dos Campos, SP - Brasil2007
ii
Dados Internacionais de Catalogação-na-Publicação (CIP)
Divisão Biblioteca Central do ITA/CTA
Altoé, Mariana Olivieri Caixeta
Codificação conjunta fonte-canal utilizando codificadores universais adaptativos / Mariana Olivieri
Caixeta Altoé
São José dos Campos, 2007.
90f.
Tese de mestrado – Curso de Engenharia Eletrônica e Computação – Área de Telecomunicações –
Instituto Tecnológico de Aeronáutica, 2007. Orientador: Prof. Dr. Marcelo da Silva Pinho.
1. Codificação conjunta fonte-canal. 2. Codificadores universais. 3. Compressão de fonte. 4. Embutindo
informação extra. I. Centro Técnico Aeroespacial. Instituto Tecnológico de Aeronáutica. Divisão de
Engenharia Eletrônica e Computação. II.Título
REFERÊNCIA BIBLIOGRÁFICA
ALTOÉ, Mariana Olivieri Caixeta.
Codificação conjunta fonte-canal utilizando
codificadores universais adaptativos. 2007. 90f. Tese de mestrado – Instituto Tecnológico
de Aeronáutica, São José dos Campos.
CESSÃO DE DIREITOS
NOME DO AUTOR: Mariana Olivieri Caixeta Altoé
TÍTULO DO TRABALHO: Codificação conjunta fonte-canal utilizando codificadores universais
adptativos
TIPO DO TRABALHO/ANO: Tese / 2007
É concedida ao Instituto Tecnológico de Aeronáutica permissão para reproduzir cópias desta
tese e para emprestar ou vender cópias somente para propósitos acadêmicos e científicos. O
autor reserva outros direitos de publicação e nenhuma parte desta tese pode ser reproduzida
sem a sua autorização do autor.
___________________________
Mariana Olivieri Caixeta Altoé
Rua Francisca Maria de Jesus, 67, Ap. 11 – Jardim Satélite
12246-021 – São José dos Campos – SP
iii
CODIFICAÇÃO CONJUNTA FONTE-CANAL UTILIZANDO
CODIFICADORES UNIVERSAIS ADAPTATIVOS
Mariana Olivieri Caixeta Altoé
Composição da Banca Examinadora:
Prof. Dr.
David Fernandes
Presidente
-
ITA
Prof. Dr.
Marcelo da Silva Pinho
Orientador
-
ITA
Prof. Dr.
Waldecir João Perrella
Membro Interno
-
ITA
Prof. Dr.
Antônio Cândido Faleiros
Membro Interno
-
ITA
Prof. Dr.
Jaime Portugheis
Membro Externo
-
UNICAMP
ITA
iv
Aos meus pais
Marisa e Celso
v
Agradecimentos
À minha família, sempre presente e incentivadora.
Ao meu marido pelo apoio e paciência.
Aos amigos do ITA.
Ao Professor Pinho pela confiança e orientação.
À FAPESP pelo apoio financeiro (Processo 03/09625-1).
vi
Resumo
Tradicionalmente, codificação de fonte e codificação de canal são tratados
independentemente, no que se denomina sistema de codificação em dois passos. Isso ocorre
porque o teorema da separação das codificações de fonte e canal garante que não há perdas
em termos de confiabilidade da transmissão em assim fazê-lo quando o volume de dados
gerados pela fonte cresce indefinidamente. No entanto, para seqüências finitas, foi mostrado
que pode ser mais eficiente realizar a codificação em apenas um passo, denominada
codificação conjunta fonte-canal, que faz uso das características da fonte ou do codificador de
fonte para prover proteção contra erros. Este trabalho propõe uma técnica de codificação
conjunta utilizando codificadores de fonte e canal consagrados e encontrados em aplicações
práticas. São eles o codificador universal adaptativo LZW e o codificador de canal ReedSolomon. O método proposto utiliza o fato do codificador de fonte não remover
completamente a redundância dos arquivos originais para adicionar bits extras, sem perda de
desempenho e sem distorção dos dados originais. A redundância remanescente no código é
então utilizada para embutir os bits de paridade do código de canal. O desempenho do método
é medido através de sua aplicação em arquivos dos corpos de Calgary e Canterbury. A
exploração da redundância remanescente no código gerado pelo LZW pode ser aplicada aos
codificadores universais LZ78 e suas variações que se baseiam no mesmo princípio de
atualização do dicionário.
vii
Abstract
Traditionally, source and channel coding have been treated independently, in what is
called separate coding system. This is because the source-channel coding separation theorem
guarantees that there is no loss in terms of reliable transmissibility provided that the volume
of source generated data increases indefinitely. Nevertheless, for finite sequences, it has been
shown that it may be more efficient to perform joint source-channel coding, which makes use
of source or source coder characteristics to provide error protection. This work proposes a
joint source-channel coding method that makes use of well-known and widely-adopted source
and channel coders. They are the LZW adaptative, universal coder and the Reed-Solomon
channel coder. The proposed method is based on the fact that LZW does not completely
remove all source redundancy to add extra bits in the codeword, with no penalty in
compression rate nor distortion in original data. The codeword remaining redundancy is then
used to embed the parity bits of the channel code. The performance of the method is measured
using the files of Calgary and Canterbury corpora. The exploration of the remaining
redundancy in LZW codeword can be applied to the LZ78 universal coder and its variants
whose dictionaries are built based in the same principle.
viii
Sumário
LISTA DE FIGURAS .........................................................................................................................................IX
LISTA DE TABELAS.......................................................................................................................................... X
LISTA DE SÍMBOLOS ......................................................................................................................................XI
1
INTRODUÇÃO ............................................................................................................................................ 14
2
CODIFICAÇÃO DE FONTE...................................................................................................................... 20
2.1 CODIFICAÇÃO COM CONHECIMENTO DA MEDIDA DE PROBABILIDADE DA FONTE ............24
2.2 CODIFICAÇÃO UNIVERSAL ................................................................................................28
2.3 CÓDIGOS DE LEMPEL-ZIV .................................................................................................31
2.3.1 Codificador LZ77..........................................................................................................32
2.3.2
Codificador LZ78..........................................................................................................35
2.3.3
Codificador LZW ..........................................................................................................39
3
CODIFICAÇÃO DE CANAL ..................................................................................................................... 43
3.1 CÓDIGOS EM BLOCO LINEARES ........................................................................................48
3.2 CÓDIGOS REED-SOLOMON ...............................................................................................49
4
CODIFICAÇÃO CONJUNTA FONTE-CANAL...................................................................................... 52
4.1 TEOREMA DA SEPARAÇÃO E VELOCIDADE DE CONVERGÊNCIA ........................................53
4.2 CODIFICADOR LZRS77 .....................................................................................................56
5
CODIFICAÇÃO CONJUNTA FONTE-CANAL UTILIZANDO LZW E RS ........................................ 59
5.1 EMBUTINDO INFORMAÇÃO EXTRA NO LZW .....................................................................60
5.2 CODIFICAÇÃO CONJUNTA .................................................................................................64
6
RESULTADOS............................................................................................................................................. 68
7
CONCLUSÕES ............................................................................................................................................ 88
REFERÊNCIAS BIBLIOGRÁFICAS .............................................................................................................. 90
ix
Lista de Figuras
FIGURA 1 – DIAGRAMA ESQUEMÁTICO DE UM SISTEMA DE COMUNICAÇÃO DIGITAL .......................... 14
FIGURA 2 – CANAL BINÁRIO SIMÉTRICO ............................................................................................... 16
FIGURA 3 – CODIFICAÇÃO DE FONTE .................................................................................................... 20
FIGURA 4 – ÁRVORE REPRESENTANDO O DICIONÁRIO DO EXEMPLO DO CODIFICADOR LZW ............... 42
FIGURA 5 – CODIFICAÇÃO DE CANAL .................................................................................................... 44
FIGURA 6 – CODIFICAÇÃO CONJUNTA FONTE-CANAL ........................................................................... 52
FIGURA 7 – EFEITOS DA SEGMENTAÇÃO DOS ARQUIVOS ...................................................................... 72
FIGURA 8 – COMPORTAMENTO DA RECUPERAÇÃO DE BITS AO LONGO DOS ARQUIVOS ....................... 75
FIGURA 9 – AUMENTO DA TAXA DE COMPRESSÃO QUANDO O CÓDIGO DE CANAL NÃO É EMBUTIDO .. 77
FIGURA 10 – TAXA DE ACERTO NA RECUPERAÇÃO DOS ARQUIVOS ...................................................... 86
FIGURA 11 – RESULTADOS OBTIDOS COM LZRS77 ............................................................................... 87
x
Lista de Tabelas
TABELA 1 – PROCESSO DE CODIFICAÇÃO DO LZ77 ............................................................................... 34
TABELA 2 – PROCESSO DE CODIFICAÇÃO DO LZ78 ............................................................................... 37
TABELA 3 – PROCESSO DE CODIFICAÇÃO DO LZW................................................................................ 41
TABELA 4 – EMBUTINDO BITS EXTRAS NO LZW ................................................................................... 63
TABELA 5 – BITS RECUPERADOS ........................................................................................................... 69
TABELA 6 – BITS RECUPERADOS NOS ARQUIVOS DO CORPO DE CALGARY .......................................... 70
TABELA 7 – EFEITOS DA SEGMENTAÇÃO DOS ARQUIVOS NA MÉDIA .................................................... 71
TABELA 8 – e MÁXIMO PERMISSÍVEL ................................................................................................... 76
TABELA 9 – TAXAS DE COMPRESSÃO DE BIBLE.TXT .............................................................................. 77
TABELA 10 – COMPRIMENTO MÁXIMO DO ARQUIVO COMPRIMIDO, EM BYTES, PARA TAXA DE ACERTO
IGUAL A 0,99.................................................................................................................................
79
TABELA 11 – COMPRIMENTO MÁXIMO DO ARQUIVO COMPRIMIDO, EM BYTES, PARA TAXA DE ACERTO
IGUAL A 0,90.................................................................................................................................
80
TABELA 12 – SEGMENTAÇÃO DOS AQUIVOS PARA SIMULAÇÃO ........................................................... 80
TABELA 13 – TAXA DE ACERTO NA RECUPERAÇÃO DE BIBLE.TXT DIVIDIDO EM 8 SEGMENTOS ............ 81
TABELA 14 – TAXA DE ACERTO NA RECUPERAÇÃO DE E.COLI DIVIDIDO EM 4 SEGMENTOS................. 81
TABELA 15 – TAXA DE ACERTO NA RECUPERAÇÃO DE KENNEDY.XLS DIVIDIDO EM 2 SEGMENTOS ...... 82
TABELA 16 – TAXA DE ACERTO NA RECUPERAÇÃO DE WORLD192.TXT DIVIDIDO EM 4 SEGMENTOS .... 82
TABELA 17 – MARGENS DE ERRO PARA N = 150 E COEFICIENTE DE CONFIANÇA DE 0,95..................... 83
xi
Lista de Símbolos
X 1n
Saída da fonte de informação
S
Alfabeto da fonte de informação
α
Cardinalidade do alfabeto da fonte
p
Medida de probabilidade da fonte de informação
σ
Fonte de informação
u1n
Seqüência de entrada do canal
V1n
Saída do canal
Cout
Alfabeto de saída do canal
Cin
Alfabeto de entrada do canal
perro
Probabilidade de erro de bit do BSC
c
Codificador de fonte
c( X 1n )
Palavra-código gerada pelo codificador c para X 1n
Csc
Alfabeto do código de fonte
C*sc
Conjunto de todas as seqüências finitas de símbolos de Csc
Sn
Conjunto de todas as seqüências com n símbolos de S
lc ( X 1n )
Comprimento da palavra código c( X 1n )
x1n
Realização de X 1n
xii
H ( X 1n )
Entropia de X 1n
H (σ )
Entropia da fonte de informação σ
rc (σ , n)
Redundância média do codificador c com relação à fonte σ
l
Comprimento do match nos algoritmos do tipo LZ
lw
Comprimento da janela do algoritmo LZ77
ls
Comprimento máximo do match no algoritmo LZ77
mLZ 77 ( x1n )
Número de partições geradas pelo LZ77 para a seqüência x1n
Di
Dicionário de padrões dos codificadores do tipo LZ78 no i -ésimo passo
βi
Cardinalidade do dicionário Di
mLZ 78 ( x1n )
Número de partições geradas pelo LZ78 para a seqüência x1n
mLZW ( x1n )
Número de partições geradas pelo LZW para a seqüência x1n
w
Mensagem a ser codificada pelo código de canal
v1n
Realização de V1n
l
w
Mensagem estimada pelo decodificador de canal
CCanal
Capacidade do canal
I (U1n ;V1n )
Informação mútua entre U1n e V1n
Cnin
Conjunto de todas as seqüências com n símbolos em Cin
n
Cout
Conjunto de todas as seqüências com n símbolos em Cout ,
H (U1n | V1n )
Entropia condicional de U1n dado V1n
(n, k )
Código de canal com taxa de transmissão
k
n
xiii
d*
Distância mínima
N
Número de possíveis partições de x1n com mesmo mLZW ( x1n )
Ns
Subconjunto de N
pi
i -ésima partição de x1n
li
Comprimento de ( pi , pi +1 )
Ni
Número de possíveis partições de ( pi , pi +1 )
t
Número de segmentos de x1n
CAPÍTULO 1
14
Capítulo 1
1
Introdução
O objetivo de um sistema de comunicação é transmitir informação de um ponto a
outro através de um canal de comunicação de forma eficiente e confiável. A Figura 2
apresenta o diagrama esquemático simplificado de um sistema de comunicação digital.
Figura 2 – Diagrama esquemático de um sistema de comunicação digital
A fonte de informação gera a mensagem a ser transmitida. O estudo aqui realizado
leva em consideração que a fonte de informação é a tempo discreto e sua saída é modelada
como uma seqüência de variáveis aleatórias discretas, X 1n = X 1 X 2 ... X n , onde n representa o
número de variáveis na seqüência, também denominado comprimento da seqüência. Cada
variável aleatória X i , 1 ≤ i ≤ n , pode assumir valores em um conjunto fixo finito S (com
CAPÍTULO 1
15
cardinalidade α ), denominado alfabeto da fonte, segundo uma medida de probabilidade, p ,
que é usualmente chamada de medida de probabilidade da fonte de informação. Sendo assim,
uma fonte de informação, σ , é totalmente caracterizada pelo seu alfabeto e por sua medida de
probabilidade e é usual representar a fonte através da seguinte notação σ = ( S, p ) . Quando
X 1n é uma seqüência de variáveis aleatórias estatisticamente independentes, i.e., quando a
fonte emite símbolos estatisticamente independentes, esta é dita sem memória.
O transmissor processa a mensagem de forma a produzir um sinal apropriado para a
transmissão através do canal de comunicação. Este processamento pode envolver codificação
de fonte, codificação de canal e modulação. Dependendo da fonte de informação e do canal de
comunicação identifica-se a necessidade de realizar apenas um dos possíveis processamentos
ou uma combinação deles, incluindo a realização dos três em seqüência. O objetivo do
codificador de fonte é representar de forma eficiente os dados gerados pela fonte, o que ocorre
pela redução da redundância presente nestes. O objetivo do codificador de canal é proteger os
dados contra erros introduzidos pelo canal de comunicação, o que é feito inserindo
redundância aos dados de entrada do codificador. A diferença entre a redundância retirada
pelo codificador de fonte e a inserida pelo codificador de canal é que a última segue uma
lógica que permite identificar e até corrigir erros na decodificação. O modulador representa
cada símbolo na saída do codificador de canal como um sinal analógico correspondente,
apropriadamente selecionado de um conjunto finito de possíveis sinais analógicos. Como o
objetivo deste trabalho é o estudo da codificação conjunta fonte-canal, serão considerados
apenas os processamentos relativos a codificação de fonte e codificação de canal,
isoladamente e em conjunto.
O canal é simplesmente o meio utilizado para transmissão do sinal. Para realizar o
estudo da codificação de fonte e da codificação de canal, este trabalho utilizou o modelo do
canal discreto sem memória (DMC – Discrete Memoryless Channel). Para estudar códigos de
CAPÍTULO 1
16
controle de erro, em geral, considera-se que o canal é um sistema estocástico que aceita em
sua entrada seqüências de símbolos, u1n = u1...un , ui ∈ Cin , 1 ≤ i ≤ n , e gera como saída uma
seqüência de variáveis aleatórias V1n = V1...Vn , que podem assumir valores em um alfabeto
Cout , segundo uma medida de probabilidade que depende da entrada. O conjunto Cin é dito
ser o alfabeto de entrada do canal e Cout é chamado de alfabeto de saída do canal. Estes dois
alfabetos em conjunto com a medida de probabilidade caracterizam totalmente o canal. Um
canal é dito discreto quando Cin e Cout são finitos. Um canal é dito ser sem memória quando
Vi só depende de ui , 1 ≤ i ≤ n . O canal binário simétrico (BSC – Binary Symmetric Channel),
representado na Figura 3, é um dos modelos mais simples de um DMC, mas ilustra a
complexidade do problema geral. O modelo é caracterizado pelo alfabeto binário de entrada
Cin = {0,1} , pelo alfabeto binário de saída Cout = {0,1} e por uma medida de probabilidade,
que estabele a probabilidade de erro de bit, perro .
Figura 3 – Canal binário simétrico
O receptor realiza os processamentos inversos aos do transmissor reconstruindo a
mensagem através do sinal obtido na saída do canal e entrega-a ao seu destino.
As duas questões fundamentais a cerca de um sistema de comunicação são [1]:
•
Qual a complexidade irredutível abaixo da qual um sinal não pode ser
comprimido?
CAPÍTULO 1
•
17
Qual é a maior taxa de transmissão para comunicação confiável sobre um canal
ruidoso?
Estas questões foram respondidas por Shannon em 1948, quando da publicação da sua
teoria da informação [2]. As respostas são, respectivamente, entropia da fonte e capacidade do
canal. Entropia, definida em termos do comportamento probabilístico de uma fonte de
informação, corresponde à menor taxa de símbolos necessária para representar a fonte de
informação sem que haja qualquer distorção nos dados. Capacidade do canal, estabelecida em
função do comportamento estatístico do canal, equivale à máxima taxa de símbolos que pode
ser transmitida através do canal tal que a probabilidade de erro seja arbitrariamente pequena.
Os processos pelos quais se busca atingir estas representações são chamados codificação de
fonte e codificação de canal, respectivamente. A codificação de fonte visa representar a saída
da fonte de forma eficiente, ou seja, aproximar a taxa de símbolos da entropia, enquanto a
codificação de canal visa reduzir o número de erros produzidos pelo canal, com uma taxa de
transmissão que se aproxime da capacidade do canal.
Quando se conhece a medida de probabilidade da fonte, é possível projetar
codificadores de fonte cuja taxa se aproxima da entropia. Em geral, a medida de probabilidade
não é conhecida a priori e precisa ser estimada sobre realizações da saída da fonte. Esta
estimação é um ponto importante, pois se o codificador for projetado com base em uma
medida de probabilidade incorreta, o código deixa de ser eficiente, ou seja, a taxa de
compressão se distancia da entropia da fonte. Em muitas aplicações, no entanto, a única
informação disponível é a seqüência de dados que se deseja comprimir, como acontece
geralmente com equipamentos que utilizam o mesmo código para comprimir diferentes tipos
de dados. Daí o interesse em codificadores universais, que se mostram eficientes para todas as
fontes pertencentes a uma determinada classe, i.e., codificadores que quando são utilizados
para comprimir a saída de uma fonte qualquer, dentro desta classe, possuem taxa de
CAPÍTULO 1
18
compressão que converge para a entropia desta fonte específica, quando o comprimento da
seqüência cresce indefinidamente.
Na prática, não se conhecem codificadores de canal que sejam capazes de atingir o
limitante da taxa de transmissão representado pela capacidade do canal com probabilidade de
erro arbitrariamente pequena. Entretanto, existe uma grande variedade de códigos eficientes,
ou seja, capazes de reduzir o número de erros produzidos pelo canal, utilizados em sistemas
de comunicação e armazenamento de dados.
A utilização de códigos (de fonte e canal) em aplicações práticas tem como objetivo
melhorar a relação de compromisso entre recursos utilizados, que pode ser a largura de banda,
a potência de transmissão ou a quantidadade de memória disponível em um dispositivo de
armazenamento, e qualidade do sistema, que no caso mais geral é dada pela taxa de erros.
É comum tratar a codificação em dois passos, como apresentado até então, pois existe
um resultado teórico que mostra que não há perda em separar o problema em codificação de
fonte e codificação de canal. Entretanto, o resultado é assintótico e, para seqüências finitas,
pode ser mais eficiente realizar a codificação em apenas um passo, ou seja, realizar uma
codificação conjunta fonte-canal, dado que a velocidade com que a probabilidade de erro
converge para zero, em alguns casos, é mais rápida quando se realiza uma codificação
conjunta.
Este trabalho propõe uma técnica de codificação conjunta utilizando o algoritmo LZW
(Lempel-Ziv-Welch) [3], que é uma variação do famoso codificador universal proposto por
Ziv e Lempel em 1978, conhecido como LZ78 [4]. Nesta proposta, a redundância
remanescente do LZW é utilizada para embutir símbolos de paridade de códigos de controle
de erro. A técnica proposta explora uma particularidade do LZW, existente na maioria das
versões do LZ78 e sendo assim, pode ser estendida para grande parte destas versões.
Diferentes códigos de controle de erro podem ser utilizados na técnica proposta. Este trabalho
CAPÍTULO 1
19
utilizou o codificador de canal Reed-Solomon [5] para avaliar o desempenho do sistema
proposto na transmissão de dados através de um canal BSC.
O trabalho está organizado da seguinte maneira. Os capítulos 2, 3 e 4 apresentam a
teoria relativa a codificação de fonte, codificação de canal e codificação conjunta fonte-canal,
respectivamente, além de soluções práticas para estes problemas. A contribuição deste
trabalho, que consiste na técnica de codificação conjunta baseada no LZW, é apresentada no
capítulo 5. Os resultados são expostos no capítulo 6 e as conclusões no capítulo 7.
CAPÍTULO 2
20
Capítulo 2
2 Codificação de Fonte
A quantidade de informação que trafega pelas redes de comunicação vem aumentando
imensamente com a expansão rápida destas redes e o aumento do número de usuários. Por
isso torna-se cada vez mais importante o aprimoramento da técnica de compressão de dados,
realizada pelo codificador de fonte, permitindo transmitir e armazenar informação de forma
mais eficiente.
A Figura 4 ilustra o problema tratado pela codificação de fonte. O codificador de fonte
codifica a seqüência de n variáveis aleatórias X 1n em uma palavra-código, c( X 1n ) , que, após
armazenamento ou transmissão por um meio de comunicação, são disponibilizadas ao
decodificador. Este tem como objetivo encontrar a melhor aproximação, Xˆ 1n , da saída da
fonte, dada a palavra código c( X 1n ) . Assume-se que as palavras-código não são alteradas por
ruído entre a saída do codificador e a entrada do decodificador.
Figura 4 – Codificação de fonte
Há casos em que a informação apresenta algumas distorções na saída do
decodificador, i.e., Xˆ 1n ≠ X 1n , sem, contudo, prejudicar o seu entendimento por parte do
usuário, que pode até mesmo não percebê-las. É a chamada codificação com perdas, ou
CAPÍTULO 2
21
codificação segundo um critério de fidelidade. Imagem e voz são exemplos de aplicações que
aceitam pequenas distorções. Para aplicações em que distorções não são toleradas, como em
arquivos de texto, deve-se realizar a codificação sem perdas, caso em que Xˆ 1n = X 1n . Assim, a
codificação é dita sem perdas quando a representação da saída da fonte permite que os dados
originais sejam reconstruídos sem perda de informação. Neste trabalho o estudo e o
desenvolvimento são focados em codificação sem perdas.
Um código de fonte c para uma seqüência de variáveis aleatórias X 1n irá representar
possíveis realizações de X 1n através de seqüências de símbolos pertencentes a um conjunto,
Csc . Na maior parte dos trabalhos em codificação de fonte, este conjunto, denominado por
alfabeto do código, é tomado por C sc = {0,1} . Neste caso, o código é chamado de código
binário. Seja C*sc o conjunto de todas as seqüências finitas de símbolos pertencentes a C sc (se
C sc = {0,1} , C*sc é o conjunto de todas as seqüências finitas de bits). Seja S n o conjunto de
todas as seqüências com n símbolos em S . Neste caso, é possível definir um código de fonte
c para X 1n como um mapa de S n em C*sc . Como na prática a fonte pode emitir uma
quantidade de símbolos muito grande, em geral, o código de fonte é projetado para seqüências
de comprimento reduzido e o código final é dado pela concatenação destes códigos. Quando a
concatenação de códigos permite uma decodificação perfeita, o código para seqüências
reduzidas é chamado de unicamente decodificável.
Como um código fonte, c , é um mapa de S n em C*sc , é possível definir uma função
lc , associada ao código, que mapeia as seqüências de S n no comprimento de suas palavras-
código. Neste caso, lc é um mapa de S n em `* (conjunto dos naturais positivos), e lc ( X 1n )
representa o comprimento da palavra-código de X 1n . É usual definir a taxa do código através
CAPÍTULO 2
da razão
l
22
c
( X ) , que é a razão do número de símbolos do código pelo número de símbolos
n
1
n
da fonte (no caso de um código binário, a unidade é bits por símbolo da fonte).
A função do codificador de fonte é aumentar a eficiência do sistema de comunicação
através da redução da forma de representar a saída da fonte. Na maior parte das aplicações, os
símbolos emitidos pela fonte de informação não se distribuem uniformemente pelo alfabeto
da fonte. Sendo assim, um bom modelo probabilístico para estas fontes não deve gerar
variáveis aleatórias equiprováveis. Por exemplo, em textos da língua portuguesa, a ocorrência
da letra “a” é muito mais freqüente que a ocorrência da letra “z”. Sendo assim, codificar a
letra “a” usando menos símbolos que a quantidade usada para a letra “z” é uma estratégia que
torna a representação do texto mais compacta. Além disso, também é comum que um bom
modelo para a fonte de informação considere uma dependência estatística entre os símbolos
da fonte. Voltando ao exemplo da língua portuguesa, é possível observar que após uma letra
“q” sempre aparece a letra “u”, o que obviamente não ocorre com as outras letras. Isto
significa que existe também uma redundância entre os símbolos da fonte. Aumentar a
eficiência de transmissão do sinal significa retirar toda ou parte da redundância presente nos
dados provenientes da fonte de informação, fazendo com que a representação da saída da
fonte seja a mais compacta possível. Retirar o máximo da redundância da saída da fonte é
equivalente a buscar um código, c , que minimize a média de lc ( X 1n ) . Quando toda a
redundância é removida, atinge-se a entropia da seqüência X 1n , no caso de codificação sem
perdas, e neste caso, o código é dito ótimo para esta fonte de informação.
A entropia pode ser entendida como uma medida da quantidade de informação média
contida na seqüência X 1n [1]. Definindo quantidade de informação como a informação obtida
após a observação do evento
X 1n = x1n ,
x1n ∈ S n ,
como a função logarítmica
CAPÍTULO 2
23
− log ( p( X 1n = x1n ) ) , onde p( X 1n = x1n ) denota a probabilidade do evento X 1n = x1n , a entropia
de X 1n é obtida através do operador valor esperado, i.e.,
( ( ))
H ( X 1n ) = E  − log p X 1n 


(
) ( (
))
= − ∑ p X 1n = x1n log p X 1n = x1n ,
x1n ∈S n
(1)
A base do logaritmo é igual à cardinalidade do alfabeto do código e neste trabalho, quando
não for especificada, é assumida igual a 2. Neste caso, a entropia é dada em bits. Usualmente
a entropia da fonte de informação σ é definida por
1
H (σ ) = lim H ( X 1n ) ,
n →∞ n
(2)
se o limite existir. É possível mostrar que se σ for estacionária, i.e., se o processo estocástico
X 1 X 2 ... for estacionário, o limite existe pois pode-se provar que a seqüência
1
H ( X 1n ) é
n
limitada inferiormente e é monótona não crescente. Por esta razão,
1
H ( X 1n ) ≥ H (σ ) ,
n
(3)
para todo n .
Outra forma de interpretar entropia é como a medida da incerteza de X 1n . O valor da
entropia representa a quantidade média de informação necessária para descrever esta
seqüência. Sabendo que a cardinalidade de S n é α n , é possível mostrar que a entropia de X 1n
satisfaz
0 ≤ H ( X 1n ) ≤ log (α n ) ,
(4)
sendo que o valor mínimo é atingido se e somente se p ( X 1n = x1n ) = 1 para algum x1n ∈ S n
(não há qualquer incerteza) e o valor máximo é atingido se e somente se p ( X 1n = x1n ) = α − n
CAPÍTULO 2
24
para todo x1n ∈ S n (caso em que todas as seqüências em S n são equiprováveis, indicando o
máximo de incerteza).
Um importante resultado da teoria da informação, vide [6], afirma que a entropia
fornece um limitante inferior para a média da taxa de qualquer código unicamente
decodificável, i.e.,
 lc ( X 1n )  1
 ≥ H ( X 1n ) .
E
 n  n
A
desigualdade
(
acima
lc ( x1n ) = − log p ( X 1n = x1n )
)
se
transforma
em
igualdade
(5)
se
e
somente
se
para todo x1n ∈ S n . Para uma fonte estacionária σ , uma
conseqüência direta da equação (3) é que
 lc ( X 1n ) 
 ≥ H (σ ) .
E
 n 
(6)
Os projetos de codificadores de fonte sem perda de informação são divididos entre os
que utilizam o modelo probabilístico da fonte (e sendo assim dependem do conhecimento a
priori do modelo) e os que não a utilizam, chamados codificadores universais. As seções a
seguir apresentam a relação entre a taxa de compressão e a entropia para os dois casos. O
princípio de funcionamento de alguns codificadores universais é apresentado na seqüência.
2.1 Codificação com Conhecimento da Medida de Probabilidade
da Fonte
Conforme pode ser observado através da equação (5), a entropia da seqüência X 1n
fornece um limitante inferior para o comprimento médio das palavras-código de qualquer
código unicamente decodificável. Para facilitar a busca por bons códigos de fonte, é comum
restringir a análise a um subconjunto dos códigos unicamente decodificáveis, chamado de
CAPÍTULO 2
25
códigos instantêneos ou códigos livres de prefixo. Um código é dito livre de prefixo se
nenhuma palavra código é prefixo de outra palavra código. Além de possuir uma estrutura que
facilita a busca por bons códigos, o decodificador de um código livre de prefixo possui uma
complexidade reduzida. É interessante observar que a restrição do conjunto de busca da
solução ótima, em princípio, poderia provocar uma perda de desempenho. No entanto,
existem diferentes algoritmos capazes de gerar códigos livres de prefixo cujas taxas atingem a
entropia da seqüência, a menos de um erro de arredondamento. Por esta razão, grande parte
dos trabalhos de codificação de fonte adota esta restrição. É importante ressaltar que tais
algoritmos necessitam do conhecimento a priori da medida de probabilidade da fonte.
Entre os códigos construídos com conhecimento da medida de probabilidade da fonte
encontram-se os códigos de Shannon, Huffman, Shannon-Fano-Elias e o código aritmético,
entre outros [6].
Analisando a desigualdade apresentada em (5) e a condição necessária e suficiente
para que ela se transforme em uma igualdade, é fácil observar que a solução ótima seria criar
(
um codificador tal que lc ( x1n ) = − log p ( X 1n = x1n )
)
para todo x1n ∈ S n . No entanto, o
resultado do logaritmo nem sempre é inteiro e como o comprimento da palavra código é o
número de bits utilizados para codificar a seqüência x1n , esta não é uma solução possível. O
código de Shannon, apresentado em [6], é um código livre de prefixo que produz palavras-
(
)
código tais que lShannon ( x1n ) =  − log p ( X 1n = x1n )  para todo x1n ∈ S n , onde t  representa o


menor inteio maior ou igual a t ∈ \ . Sendo assim, é possível afirmar que
CAPÍTULO 2
26
 lShannon ( X 1n )  1
 = ∑ p ( X 1n = x1n )  − log p ( X 1n = x1n ) 
E


n

 n x1n ∈Sn
1
≤ ∑ p ( X 1n = x1n ) − log p ( X 1n = x1n ) + 1
n x1n ∈Sn
(
=−
=
(
(
)
(
) )
(7)
)
1
1
p ( X 1n = x1n ) log p ( X 1n = x1n ) + ∑ p ( X 1n = x1n )
∑
n x1n ∈Sn
n x1n ∈Sn
1
1
H ( X 1n ) + .
n
n
Com a equação (5) e com o resultado da equação (7), é possível afimar que
 lShannon ( X 1n )  1
1
1
n
 ≤ H ( X 1n ) + .
H ( X1 ) ≤ E 
n
n
n

 n
(8)
O algoritmo apresentado por Huffman em 1952 possibilita construir um código livre
de prefixo que é ótimo, ou seja, um código cuja média do comprimento das palavras-código é
menor ou igual à média do comprimento das palavras-código de qualquer código livre de
prefixo. Sendo assim, é possível afimar que E lHuffman ( X 1n )  ≤ E lShannon ( X 1n )  e com este
resultado e os resultados apresentados em (5) e (7), é possível concluir que
 lHuffman ( X 1n )  1
1
1
n
 ≤ H ( X 1n ) + .
H ( X1 ) ≤ E 
n
n
n

 n
(9)
O esquema de codificação aritmético, baseado no código de Shannon-Fano-Elias,
permite a construção de códigos quase ótimos que apresentam comprimento médio que
satisfaz
 lAritmético ( X 1n )  1
1
2
 ≤ H ( X 1n ) + .
H ( X 1n ) ≤ E 
n
n
n

 n
(10)
O código aritmético, apesar de se basear em técnicas que datam de 1963, tornou-se
prático a partir de 1976 e desde então surgiram várias de suas versões. Apesar de apresentar
maior comprimento médio, o código aritmético é preferível ao código de Huffman quando o
alfabeto da fonte é pequeno. Nesse caso, o código de Huffman somente apresenta boa taxa de
CAPÍTULO 2
27
compressão para blocos longos de símbolos da fonte. No entanto, a metodologia de
construção do código de Huffman exige o cálculo das probabilidades de todas as seqüências
da fonte com um comprimento de bloco particular, mesmo que já se tenha construído um
código de Huffman para comprimento de bloco menor. Já o código aritmético pode ser
facilmente expandido para comprimentos de bloco maiores sem a necessidade de refazer
todos os cálculos.
Se a fonte de informação σ for estacionária, tomando o limite quando n → ∞ nas
equações (8), (9) e (10), é possível notar que as médias das taxas do código de Shannon, do
código de Huffman e do código aritmético convergem para a entropia da fonte, H (σ ) . Isto
mostra que o limite fundamental (dado pela entropia da fonte) é alcançado quando se codifica
um número suficientemente grande de símbolos da fonte por vez.
A diferença entre a média da taxa do código e a razão
H ( X 1n )
n
representa a
redundância do código que não foi removida pela codificação. Portanto, através das equações
(8) e (9) é possível notar que as redundâncias do codificador de Shannon e do codificador de
Huffman são menores ou iguais a
1
e através da equação (10) é possível observar que a
n
redundância do codificador aritmético é menor ou igual a
2
. É importante ressaltar que estes
n
valores de redundância são atingidos quando os codificadores operam em blocos de
comprimento n . Como em geral, o codificador aritmético consegue trabalhar com blocos de
comprimento elevado, na prática, existe vantagem em se utilizar este método de codificação.
Quando é considerada uma medida de probabilidade incorreta para a fonte de
informação, a eficiência destes códigos é comprometida. Considerando que uma medida de
probabilidade q seja utilizada para construção do código no lugar da distribuição correta p , é
possível mostrar que o comprimento médio de um código perfeito (i.e., um código tal que
CAPÍTULO 2
28
(
lc ( x1n ) = − log p ( X 1n = x1n )
D( p & q) =
∑
x1n ∈S n
)
para todo x1n ∈ S n ) , será acrescido de D( p & q) , onde
 p ( X 1n = x1n ) 
 é a entropia relativa, que, embora não seja
p ( X 1n = x1n ) log 
 q ( X 1n = x1n ) 


uma métrica, é freqüentemente utilizada para indicar uma distância entre duas distribuições. A
entropia relativa pode ser entendida como uma medida da ineficiência ao se assumir uma
distribuição equivocada. Na prática, muitas vezes não se conhece um bom modelo
probabilístico para a fonte que se deseja comprimir ou até mesmo um único codificador é
utilizado para comprimir diferentes tipos de dados. Este problema deu origem à teoria da
codificação universal, cujo objetivo é desenvolver códigos bons para todas as fontes
pertencentes a uma determinada classe.
2.2 Codificação Universal
Códigos universais são freqüentemente utilizados quando não se conhece a
distribuição de probabilidade da fonte. Tais codificadores são eficientes para todas as fontes
pertencentes a uma classe. De fato, um codificador é definido como universal com relação a
uma classe de fontes se, para todas as fontes desta classe, a taxa do codificador converge para
a entropia da fonte, segundo algum critério de convergência. Seja Σ uma classe de fontes
(p.ex., a classe de fontes sem memória). Um codificador c é dito universal para a classe Σ se
lc ( X 1n )
n
→ H (σ ) , segundo algum critério de convergência, para toda fonte σ em Σ . Como o
critério de convergência não é estabelecido, este deve ser explicitado quando determinado
codificador é considerado universal.
A partir da definição de codificador universal, é possível notar que assintoticamente,
não existe penalidade em codificar uma fonte de informação utilizando um codificador
CAPÍTULO 2
29
universal ao invés de se utilizar um codificador que faz uso da medida de probabilidade da
fonte. Contudo, deve-se observar a velocidade com a qual a taxa de compressão atinge
(assintoticamente) a entropia da fonte, uma vez que, na prática, codifica-se seqüências finitas.
Se a velocidade de convergência da taxa de compressão de um determinado codificador for
muito lenta, este produzirá resultados ruins para seqüências finitas. Como qualquer
codificador unicamente decodificável satisfaz a condição estabelecida em (5), o conceito de
redundância pode ser utilizado para analisar a velocidade de convergência da taxa. Conforme
apresentado na seção 2.1, a redundância de um codificador é a diferença entre a taxa média do
código e a razão
H ( X 1n )
n
. Sendo c um codificador para a classe de fontes Σ , a redundância
de c com relação à fonte de informação σ ∈ Σ é definida por
rc (σ , n ) =
E l ( X 1n )  − H ( X 1n )
n
.
(11)
Como o objetivo de um codificador universal é comprimir de forma eficiente todas as fontes
de uma determinada classe, é preciso que a redundância definida em (11) seja reduzida para
toda fonte σ ∈ Σ . Sendo assim, um parâmetro muito utilizado para avaliar o desempenho de
um codificador universal é a máxima redundância sobre todas as fontes em Σ . Um importante
resultado da teoria da informação [7], afirma que para a classe de fontes markovianas (i.e., o
conjunto de todas as fontes tais que X 1 X 2 ... é um processo estocástico de Markov)
 log ( n ) 
min max {rc (σ , n )} = O 
,
c∈Γ
σ ∈Σ
n


{
}
(12)
onde Γ é a coleção de todos os códigos univocamente decodificáveis e O (.) é a função
conhecida como big-O1. Sendo assim, o melhor código universal para fontes sem memória
1
(
)
Seja n ∈ ` e sejam f ( n ) e g ( n ) duas funções reais. É dito que f ( n ) = O g ( n ) se existem uma
constante k e um inteiro n0 tais que f ( n ) ≤ k × g ( n ) , ∀n ≥ n0 .
CAPÍTULO 2
30
 log ( n ) 
possui uma taxa que converge para a entropia com uma velocidade igual a O 
.
 n 
Comparando este valor com as redundâncias obtidas para os codificadores construídos com o
conhecimento da medida de probabilidade, é possível notar que a convergência da taxa de um
codificador universal é mais lenta.
Na prática, grande parte dos codificadores universais procura estimar uma medida de
probabilidade para codificar os dados, que pode ser feita a partir de uma base de dados fixa ou
de forma adaptativa ao longo da seqüência de dados que está sendo codificada. Neste trabalho
são estudados codificadores universais adaptativos que utilizam a técnica de recorrência de
padrões para comprimir a informação.
Em geral, a seqüência de dados a ser comprimida por um codificador de fonte possui
determinados padrões que se repetem ao longo desta seqüência. Sendo assim, uma forma de
se comprimir dados é através da utilização de padrões recorrentes. Para realizar a compressão,
basta identificar padrões repetidos e codificar cada padrão através de um ponteiro para sua
ocorrência anterior. Esta técnica é conhecida como recorrência de padrões.
O princípio do codificador via recorrência de padrões é criar um dicionário de padrões
a partir de uma parcela da seqüência de dados que já foi codificada e codificar o restante da
seqüência utilizando este dicionário, que é atualizado a cada passo da codificação. No início
da codificação, em que não há padrões para constituir o dicionário, existe um dicionário
inicial que pode ser formado por uma seqüência fictícia ou pelo alfabeto da fonte, por
exemplo, dependendo do codificador.
O funcionamento de um codificador via recorrência de padrões é explicado em linhas
gerais a seguir. Seja x1n uma realização da saída da fonte que se deseja comprimir. Seja xkj ,
1 ≤ k ≤ j ≤ n , a subseqüência xk xk +1...x j , onde xkk = xk . Sendo assim, x1j corresponde a
prefixos de x1n e xkn corresponde a sufixos de x1n . Em um passo genérico, supondo que os
CAPÍTULO 2
31
primeiros k − 1 símbolos de x1n tenham sido codificados, x1k −1 representa a parte da seqüência
que já foi codificada e xkn a parte que falta ser codificada. O dicionário que será utilizado
neste passo é gerado a partir de x1k −1 . O codificador encontra o bloco de símbolos xkk +l que
será codificado neste passo utilizando o dicionário. Este bloco é então representado por uma
palavra código que referencia de alguma forma o bloco de símbolos xkk +l à sua ocorrência no
dicionário. O dicionário é atualizado com o bloco de símbolos que acabou de ser codificado e
o processo de codificação segue na busca pelo prefixo de xkn+l +1 que será codificado no passo
seguinte.
É importante notar que a compressão de um codificador via recorrência de padrões
surge a partir do dicionário, cuja construção realiza uma medida indireta da estatística da
fonte, pois o dicionário contém blocos que aparecem freqüentemente e, em geral, não contém
blocos que nunca aparecem.
Os primeiros codificadores universais adaptativos via recorrência de padrões foram
criados por Ziv e Lempel em 1977 e 1978 – LZ77 [8] e LZ78 [4], respectivamente – baseados
em resultados obtidos em [9]. No decorrer dos anos, vários algoritmos derivados destes foram
criados com o objetivo de melhorar seus desempenhos. Alguns destes algoritmos, por
apresentarem baixa complexidade computacional e bom desempenho, tornaram-se padrões
para compressão de arquivos em computadores.
2.3 Códigos de Lempel-Ziv
Os códigos de Lempel-Ziv são a base de uma boa parte dos algoritmos de compressão
de dados sem perdas utilizados na prática. Isso ocorre porque eles atingem empiricamente
boas taxas de compressão e são eficientes computacionalmente. Os algoritmos LZ77 [8], LZ78
[4] ou uma de suas variações são utilizados, entre outras aplicações, pelos codificadores de
CAPÍTULO 2
32
fonte pkzip, arj, compress e gzip e pelos algoritmos de compressão de imagens sem perdas
embutidos nos padrões png e tiff.
Dentre as variações do LZ78, a versão mais popular é o codificador LZW [3], que foi
apresentado em 1984 quando da publicação do trabalho de Terry Welch, que propôs uma
modificação ao LZ78, melhorando seu desempenho.
Os esquemas de codificação propostos por Ziv e Lempel fazem a estimativa da medida
de probabilidade da fonte de forma adaptativa via recorrência de padrões. Nestes algoritmos
universais, a partição da seqüência de dados a ser codificada é feita de acordo com o método
do maior prefixo, ou seja, a cada passo da codificação identifica-se o maior padrão possível
que possa ser relacionado a uma ocorrência prévia que pertença ao dicionário. O desempenho
é função direta da quantidade de partições encontradas, ou seja, quanto menor o número de
partições necessário para codificar a seqüência de dados, menor o código gerado para
representar a saída da fonte e, conseqüentemente, melhor a compressão.
Os codificadores LZ77, LZ78 e LZW são apresentados a seguir.
2.3.1 Codificador LZ77
Em um passo genérico da codificação, o codificador LZ77 examina a seqüência de
símbolos anteriores presente no dicionário para encontrar o match com o maior prefixo da
subseqüência que começa na posição atual. O maior prefixo é substituído por um ponteiro
com três informações: (posição, comprimento, símbolo de inovação). O funcionamento do
algoritmo é apresentado a seguir.
Supondo que os primeiros k − 1 símbolos de x1n tenham sido codificados, a
codificação segue realizando a busca pelo maior match entre o prefixo de xkn e uma
subseqüência que comece no intervalo x1k −1 . Se x jj +l −1 , j < k , é a subseqüência que começa
CAPÍTULO 2
33
em x1k −1 que possibilita o maior match, a próxima subseqüência é xkk +l −1 . O algoritmo gera o
ponteiro (j, l, xk +l ), que irá produzir a palavra código para codificação de xkk +l , e atualiza a
posição atual k para k + l + 1 . A razão de transmitir o símbolo de inovação xk +l é garantir a
continuação da codificação quando l = 0 , o que é muito comum no começo do processo.
A busca pelo maior match pode se tornar muito complexa, já que o dicionário x1k −1
cresce muito rapidamente. É comum, então, utilizar apenas o passado mais recente, isto é,
uma janela de comprimento lw da seqüência já codificada: xkk−−l1w . Além disso, também se
costuma limitar o comprimento máximo do match a uma constante l s , ou seja, a busca pelo
maior match é restringida à porção da seqüência ainda não codificada xkk +ls −1 .
Considerando o alfabeto de saída do codificador binário, o número de bits necessários
para transmitir o ponteiro (posição, comprimento, símbolo de inovação) é dado por
 log lw  + log ls  +  log α  , onde α é o número de elementos do alfabeto da fonte S . Como
todas as partições necessitam transmitir a mesma quantidade de bits, uma vez que lw , l s e α
são constantes, e o código cLZ 77 ( x1n ) é formado pela concatenação dos ponteiros que
representam cada partição, o comprimento do código é dado por
lLZ 77 ( x1n ) = mLZ 77 ( x1n ) (  log lw  + log ls  + log α  ) ,
(13)
onde mLZ 77 ( x1n ) é o numero de partições necessárias para codificar x1n com o LZ77.
O dicionário inicial pode ser construído com uma seqüência fictícia x−0lw +1 composta
por lw símbolos iguais ( lw zeros, por exemplo), desde que este símbolo pertença ao alfabeto
da fonte.
A seguir encontra-se um exemplo do codificador LZ77.
Seja 'abacabcbaabcbaabca' a seqüência a ser codificada sobre um alfabeto binário.
CAPÍTULO 2
34
Seja S = {a, b, c} e, então, α = 3 . Definindo lw = 8 e ls = 8 , cada palavra código terá
comprimento  log lw  +  log ls  +  log α  = 8 bits. O dicionário inicial é formado por 8
símbolos 'a' .
No primeiro passo da codificação, tem-se a seguinte estrutura: x−07 = 'aaaaaaaa' e
x18 = 'abacabcb' . O maior match é formado por 'a' e, assim, l = 1. A posição j em que o maior
match começa em xkk−−l1w = x−07 pode ser qualquer valor entre 1 e 8. Escolhendo j = 8, o ponteiro
para o maior match encontrado quando k = 1 é (j, l, xk +l ) = (111, 001, 01), sendo o símbolo de
inovação xk +l = x2 = 'b' , representado por 01. A posição k = 1 é atualizada para k + l + 1 = 3 e
a codificação segue conforme apresentado na Tabela 1. Cada linha representa um passo do
proceso de codificação, incluindo o primeiro, detalhado acima.
Tabela 1 – Processo de codificação do LZ77
k
xkk−−l1w
xkk +ls −1
j
l
xk +l
(j, l, xk +l )
1
'aaaaaaaa'
'abacabcb'
8
1
b
111 001 01
3
'aaaaaaab'
'acabcbaa'
7
1
c
110 001 10
5
'aaaaabac'
'abcbaabc'
5
2
c
100 010 10
8
'aabacabc'
'baabcbaa'
3
2
a
010 010 00
11
'acabcbaa'
' bcbaabca'
4
7
a
111 111 00
Ao final do processo, o código é obtido pela concatenação dos ponteiros (ou palavrascódigo): 11100101 11000110 10001010 01001000 11111100. A taxa de codificação para essa
seqüência é
lLZ 77 ( x118 ) 40
=
= 2, 22 bits por símbolo da fonte.
18
18
CAPÍTULO 2
35
O processo de decodificação é o inverso da codificação. Faz-se a leitura dos ponteiros
(posição, comprimento, símbolo de inovação) e remonta-se a seqüência de dados original.
O LZ77 é um código universal, pois sua taxa de compressão converge em
probabilidade para a entropia da fonte para toda fonte estacionária. Com relação à
redundância, Savari mostrou em [10] que a redundância do código LZ77 para fontes
markovianas é tal que
 log ( log ( n ) ) 
rLZ 77 (σ , n ) ≤ O 
.
 log ( n ) 


(14)
Na verdade, é possível mostrar que para um grande número de fontes markovianas, a
redundância do LZ77 é da ordem de
log ( log ( n ) )
log ( n )
. Comparando-se este resultado com a
equação (12), é possível notar que a redundância deste codificador não atinge o melhor valor
possível. Isto significa que existe uma margem para melhorar a compressão, o que pode ser
feito através da exploração da redundância remanescente no código gerado pelo LZ77.
2.3.2 Codificador LZ78
O codificador LZ78 examina os padrões (símbolos ou seqüências de símbolos em que
a parte inicial da seqüência de dados já codificada foi particionada) que compõem um
dicionário, Di , que varia de acordo com a parte já codificada, para encontrar o match com o
maior prefixo da subseqüência que começa na posição atual. O maior prefixo é codificado
como o número correspondente à posição no dicionário, Di , do padrão que proporcionou o
maior match. Ao dicionário, Di , são acrescentados novos padrões, formados pelo maior
match concatenado com cada um dos símbolos da fonte, gerando o dicionário, Di +1 , que será
utilizado no próximo passo o algoritmo. O funcionamento do algoritmo é apresentado a
seguir.
CAPÍTULO 2
36
Supondo que no i -ésimo passo, os primeiros k − 1 símbolos da seqüência de dados x1n
tenham sido codificados, a codificação segue realizando a busca pelo maior match entre o
prefixo de xkn e os padrões do dicionário Di . Se o padrão na posição j do dicionário Di ,
composto por l símbolos, é o que possibilita o maior match, o algoritmo codifica xkk +l −1 como
j e atualiza a posição atual k para k + l . O número de bits necessário para transmitir j é
log ( β i ) , onde β i é o número de elementos do dicionário Di . O dicionário é atualizado pela
adição dos α padrões formados por xkk +l −1 concatenado com cada um dos símbolos de S , o
alfabeto da fonte. A forma como o dicionário é atualizado no LZ78 provoca um desempenho
ruim por incluir neste, padrões que não ocorreram e podem não vir a ocorrer. O dicionário
inicial é composto pelo alfabeto S .
O código cLZ 78 ( x1n ) é formado pela concatenação das palavras código correspondentes
à posição, no dicionário, de cada padrão que proporcionou o maior match, em cada passo.
Como o dicionário inicial contém α símbolos e como a cada passo, o LZ78 inclui α padrões
novos ao dicionário, é possível observar que o comprimento da palavra-código gerada pelo
LZ78 é dado por
lLZ 78 ( x1n ) =
mLZ 78
∑ log ( iα ),
(15)
i =1
onde mLZ 78 ( x1n ) é o número de partições necessárias para codificar x1n com o LZ78.
A seguir encontra-se um exemplo do codificador LZ78.
Seja 'abacabcbaabcbaabca' a seqüência a ser codificada sobre um alfabeto binário.
Seja S = {a, b, c} e, conseqüentemente, α = 3 . O dicionário inicial é D 1 = {a,b,c} .
No primeiro passo da codificação, k = 1, o maior match entre o prefixo de x1n e os
padrões do dicionário é dado por 'a ' , cuja posição no dicionário é j = 1 e o comprimento é
l = 1. O número de bits necessários para representar a palavra código para codificar j é
CAPÍTULO 2
37
1
 log D1  = log 2 α  = 2 bits e assim a palavra-código para codificar a subseqüência x1 = a é
00. O dicionário é atualizado pelo acréscimo dos três novos padrões formados pela
concatenação de x11 com os símbolos da fonte, resultando em D2 = {a,b,c,aa,ab,ac} . A
posição k = 1 é atualizada para k + l = 2 e a codificação segue conforme apresentado na
Tabela 2. Cada linha representa um passo do proceso de codificação, incluindo o primeiro,
detalhado acima.
Tabela 2 – Processo de codificação do LZ78
i
Di
Maior match
j
Código
1
a,b,c
a
1
00
2
a,b,c,aa,ab,ac
b
2
001
3
a,b,c,aa,ab,ac,ba,bb,bc
ac
6
0101
4
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc
ab
5
0100
5
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc
c
3
0010
6
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc,ca,cb,cc
ba
7
00110
abc
15
01110
baa
19
10010
bc
9
00111
a
1
00000
7
8
9
10
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc,ca,cb,cc,
baa,bab,bac
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc,ca,cb,cc,
baa,bab,bac,abca,abcb,abcc
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc,ca,cb,cc,
baa,bab,bac abca,abcb,abcc,baaa,bab,baac
a,b,c,aa,ab,ac,ba,bb,bc,aca,acb,acc,aba,abb,abc,ca,cb,cc,
baa,bab,bac,abca,abcb,abcc,baaa,bab,baac,bca,bcb,bcc
A Tabela 2 mostra que a seqüência foi particionada em 10 subseqüências. O código na
saída do codificador é obtido pela concatenação dos códigos: 00 001 0101 0100 0010 00110
CAPÍTULO 2
38
01110 10010 00111 00000. A taxa de codificação para essa seqüência é dada por
lLZ 78 ( x118 ) 42
=
= 2,33 bits por símbolo da fonte.
18
18
O processo de decodificação segue os passos inversos aos da codificação. Lê-se os bits
correspondentes a  log ( βi )  , a cada passo, e identifica-se no dicionário o(s) símbolo(s)
transmitido(s) pelo codificador. Adiciona-se ao dicionário os padrões compostos pelo(s)
símbolo(s) decodificado(s) concatenado(s) com cada um dos símbolos do alfabeto da fonte.
O LZ78 é um código universal, pois sua taxa de compressão converge com
probabilidade 1 para a entropia da fonte para toda fonte ergódica. De acordo com [11], a
redundância do código LZ78 para fontes markovianas é tal que
 1 
rLZ 78 (σ , n ) ≤ O 
 .
n
log
(
)


(16)
Na verdade, é possível afirmar que para um grande número de fontes markovianas, a
redundância do LZ78 é da ordem de
1
. Apesar da redundância do LZ78 ser menor que a
log ( n )
redundância do LZ77, ela ainda é maior que a redundância apresentada em (12), e mais uma
vez, existe margem para explorar a redundância do código.
Uma característica interessante ressaltada em [10] é que o número de partições em que
a seqüência de dados é dividida pelo LZ77 em geral é menor que o número de partições
gerado pelo LZ78. No entanto, como o codificador LZ78 não precisa codificar o comprimento
das partições, seu código costuma apresentar comprimento menor que o do código gerado
pelo LZ77.
CAPÍTULO 2
39
2.3.3 Codificador LZW
O codificador LZW é uma versão do LZ78, que busca melhorar o desempenho do
algoritmo original através da alteração na forma de atualizar o dicionário. O dicionário inicial
do LZW também é composto pelo alfabeto da fonte S .
O codificador LZW examina os padrões (símbolos ou seqüências de símbolos em que a
parte inicial da seqüência de dados já codificada foi particionada) que compõem o dicionário
Di para encontrar o match com o maior prefixo da subseqüência que começa na posição
atual. O maior prefixo é codificado como o número correspondente à posição, no dicionário
Di , do padrão que proporcionou o maior match. Até aqui o procedimento é idêntico ao
realizado pelo LZ78. A diferença está na atualização do dicionário, ao qual é acrescentado
apenas um novo padrão, ao invés dos α padrões adicionados pelo LZ78. O novo padrão é
composto pelo maior prefixo encontrado concatenado com o símbolo consecutivo na
seqüência ainda não codificada, que equivale ao símbolo de inovação. Supondo que xkk +l −1
seja o maior prefixo encontrado no i -ésimo passo da codificação, o novo padrão adicionado
ao dicionário é xkk +l .
O número de bits necessário para transmitir a palavra código que representra a posição
do match no dicionário é dado por log ( β i ) , assim como no LZ78. Contudo, como neste caso
o algoritmo só inclui um novo padrão a cada passo, β i = α + i − 1 . Assim, o comprimento do
código LZW é dado por
lLZW ( x
n
1
)=
( )
mLZW x1n
∑
i =1
log (α + i − 1) ,
onde mLZW ( x1n ) é o numero de partições necessárias para codificar x1n com o LZW.
(17)
CAPÍTULO 2
40
Embora α + i − 1 < iα para i ≥ 2 , não é possível comparar os desempenhos do LZ78 e
do LZW porque mLZ 78 ( x1n ) ≠ mLZW ( x1n ) e, em geral, mLZ 78 ( x1n ) < mLZW ( x1n ) .
A seguir encontra-se um exemplo do codificador LZW.
Seja 'abacabcbaabcbaabca' a seqüência a ser codificada sobre um alfabeto binário.
Seja S = {a, b, c} e, então, α = 3 . O dicionário inicial é D1 = {a,b,c} , como no LZ78.
No primeiro passo da codificação, i = 1 , o maior match entre o prefixo de x1n e os
padrões do dicionário é dado por 'a ' , cuja posição no dicionário é j = 1 e o comprimento é
l = 1. O número de bits necessário para representar a palavra código para codificar j é
 log ( β1 )  = log (α + i − 1)  = 2 bits e assim a palavra-código para codificar a subseqüência
x11 = a é 00. O dicionário é atualizado pelo acréscimo de um novo padrão formado pela
concatenação de x11 com o símbolo seguinte da seqüência de dados, resultando em
D2 = {a,b,c,ab} . A posição k = 1 é atualizada para k + l = 2 e a codificação segue conforme
apresentado na Tabela 3. Cada linha representa um passo do proceso de codificação, incluindo
o primeiro, detalhado acima.
A seqüência foi particionada em 11 subseqüências. A saída do codificador é dada pela
concatenação dos códigos: 00 01 000 010 011 010 0100 0111 1001 0001 0110. Portanto, a
taxa de codificação é
lLZW ( x118 ) 36
=
= 2 bits por símbolo da fonte.
18
18
Uma possível forma de representar o dicionário, tanto para o LZW quanto para o LZ78,
é através de uma estrutura em árvore cujos nós iniciais são os que compõem o dicionário
inicial. Os novos padrões que são adicionados ao dicionário correspondem a novos nós na
árvore. No LZW, a cada passo é criado um nó “filho” do nó que corresponde ao maior match,
representando o símbolo inovador. No LZ78, a cada passo são criados α nós “filhos” do nó
que coresponde ao maior match. A busca pelo maior match começa sempre no nível mais
CAPÍTULO 2
41
baixo da árvore (nós iniciais). Cada nó recebe o número correspondente à sua posição no
dicionário. Ao final da codificação do exemplo acima, a estrutura apresentará a forma
representada na Figura 5. Esta estrutura permite uma implementação mais eficiente tanto do
codificador quanto do decodificador.
Tabela 3 – Processo de codificação do LZW
i
Di
Maior match
j
Código
1
a,b,c
a
1
00
2
a,b,c,ab
b
2
01
3
a,b,c,ab,ba
a
1
000
4
a,b,c,ab,ba,ac
c
3
010
5
a,b,c,ab,ba,ac,ca
ab
4
011
6
a,b,c,ab,ba,ac,ca,abc
c
3
010
7
a,b,c,ab,ba,ac,ca,abc,cb
ba
5
0100
8
a,b,c,ab,ba,ac,ca,abc,cb,baa
abc
8
0111
9
a,b,c,ab,ba,ac,ca,abc,cb,baa,abcb
baa
10
1001
10
a,b,c,ab,ba,ac,ca,abc,cb,baa,abcb,baab
b
2
0001
11
a,b,c,ab,ba,ac,ca,abc,cb,baa,abcb,baab,bc
ca
7
0110
O processo de decodificação segue os passos inversos aos da codificação. Lê-se os bits
correspondentes a  log ( βi )  e identifica-se no dicionário o(s) símbolo(s) transmitido(s) pelo
codificador. Adiciona-se ao dicionário o padrão composto pelo(s) símbolo(s) decodificado(s)
mais o símbolo de inovação, que será conhecido apenas na decodificação do(s) próximo(s)
símbolo(s). Atualiza-se o símbolo de inovação do padrão adicionado ao dicionário na
decodificação anterior como o primeiro símbolo decodificado no passo atual.
CAPÍTULO 2
42
Nó 1
a
Nó 4
b
Nó 8
c
Nó 11
b
Nó 6
c
Nó 2
b
Nó 5
a
Nó 10
a
Nó 12
b
Nó 13
c
Nó 7
a
Nó 3
c
Nó 9
b
Figura 5 – Árvore representando o dicionário do exemplo do codificador LZW
O LZW, assim como o LZ78, é um código universal, pois sua taxa de compressão
converge com probabilidade 1 para a entropia da fonte para toda fonte ergódiga. A
redundância do código LZW é a mesma do LZ78, i.e., rlzw (σ , n ) é da ordem de
1
para
log n
fontes markovianas [11]. Com isso, este codificador também é ineficiente se for comparado
com o resultado apresentado na equação (12). A contribuição deste trabalho consiste
justamente em explorar a redundância remanescente no código gerado pelo LZW, não para
melhorar a taxa de compressão, mas para embutir informação extra. Mais especificamente,
parte da redundância remanescente neste código é utilizada para embutir um código para
correção de erros introduzidos pelo canal. É importante mencionar que a técnica proposta
neste trabalho também pode ser estendida para o codificador LZ78 e para outras versões deste
método.
As observações feitas para o LZ78 em comparação ao LZ77 na seção 2.3.2 também
são válidas para o LZW, que em geral gera mais partições que o LZ77, mas o comprimento do
seu código costuma ser menor.
CAPÍTULO 3
43
Capítulo 3
3 Codificação de Canal
Sinais recebidos em sistemas de comunicação são sempre contaminados por
imperfeições do processo de comunicação, tais como o ruído térmico, as interferências, o
desvanecimento e a dispersão do sinal no meio de comunicação. Para garantir confiabilidade
na recepção dos sinais, faz-se uso da codificação de canal, que introduz redundância de forma
lógica aos dados. Apesar da taxa de dados aumentar, a largura de banda e a potência de
transmissão podem ser mantidas pequenas dado o aumento na confiabilidade proporcionado
pela estrutura elaborada das mensagens em sistemas de comunicação e armazenamento
modernos. Isto é obtido a troco de maior esforço computacional no transmissor e no receptor,
o que, contudo, é considerado factível com a tecnologia eletrônica moderna.
A Figura 6 ilustra o problema tratado pela codificação de canal. O codificador de canal
codifica uma mensagem w , que pode assumir valores em um conjunto com 2k elementos, em
uma seqüência, u1n , com n símbolos do alfabeto de entrada do canal, Cin . Esta seqüência é
aplicada na entrada do canal dando origem na saída a uma seqüência aleatória, V1n , de acordo
com a medida de probabilidade do canal. A função do decodificador é estimar qual a
mensagem w foi transmitida a partir de uma seqüência observada v1n , que é uma realização
de V1n . Dependendo da medida de probabilidade do canal e do código, irá existir uma
l , ser diferente da mensagem original, w . Transmitir
probabilidade da mensagem estimada, w
uma mensagem que assume valores em um conjunto com 2k elementos é equivalente a
CAPÍTULO 3
44
transmitir k bits. Sendo assim, a taxa de transmissão atingida pelo código de canal é definida
pela razão
k
e é dada em bits por utilização do canal.
n
Figura 6 – Codificação de canal
A função do codificador de canal é aumentar a confiabilidade do sistema de
comunicação através da redução da taxa de erros ao mesmo tempo em que busca maximizar a
taxa de transmissão de símbolos por utilização do canal. Shannon mostrou em [2] que se a
taxa de transmissão é menor que a capacidade do canal, CCanal , então existe uma técnica de
codificação que possibilita projetar um sistema de comunicação para este canal com
probabilidade de erro tão baixa quanto desejada. Este teorema é conhecido como teorema da
codificação de canal e é demonstrado em [6].
Para calcular a capacidade de um dado canal, é necessário utilizar o conceito de
informação mútua. Sejam U1n e V1n duas seqüências de variáveis aleatórias que podem
assumir valores nos conjuntos Cin e Cout , respectivamente. A informação mútua entre estas
duas seqüências é definida por
I (U1n ;V1n ) =
∑ ∑
u1n ∈Cnin
v1n ∈Cnout
 p (U1n = u1n ,V1n = v1n ) 
,
p (U1n = u1n , V1n = v1n ) log 
 p (U1n = u1n ) p (V1n = v1n ) 


(18)
n
onde Cnin e Cout
são os conjuntos de todas as seqüências com n símbolos em Cin e Cout ,
respectivamente. A partir da definição da informação mútua, é possível encontrar o
relacionamento desta com a entropia das seqüências U1n e V1n . De fato, as seguintes relações
podem ser obtidas a partir de (18):
CAPÍTULO 3
45
I (U1n ;V1n ) = H (U1n ) + H (V1n ) − H (U1n , V1n )
= H (U1n ) − H (U1n | V1n )
,
(19)
= H (V1n ) − H (V1n | U1n )
onde H (U1n | V1n ) é a entropia condicional de U1n dado V1n .
Considerando um canal discreto sem memória com entrada U1n e saída V1n , a entropia
da entrada do canal, H (U1n ) , depende apenas de U1n e representa a incerteza em relação a que
seqüência de símbolos u1n ∈ Cnin será transmitida. A entropia da saída do canal, H (V1n ) ,
depende de U1n e dos erros de transmissão e representa a incerteza em relação à seqüência de
n
que será recebida. Conhecendo as estatísticas da entrada U1n e do canal
símbolos v1n ∈ Cout
ruidoso conhece-se a entropia conjunta H (U1n , V1n ) , que representa a incerteza sobre a
transmissão de u1n e a recepção de v1n .
Supondo a seqüência u1n conhecida, a entropia condicional H (V1n |U1n ) representa a
incerteza de receber v1n quando u1n é enviada, ou seja, é a incerteza média do emissor em
relação ao que será recebido. Por simetria, supondo a seqüência v1n conhecida, a entropia
condicional H (U1n |V1n ) representa a incerteza sobre u1n ter sido enviada quando se recebe v1n ,
ou a incerteza média do receptor da mensagem em relação ao que foi realmente enviado. Em
outras palavras, é a incerteza sobre a entrada que resta depois da saída ter sido observada. A
diferença H (U1n ) − H (U1n |V1n ) representa, então, a incerteza sobre a entrada que é eliminada
após a observação da saída. Assim, a informação mútua I (U1n ;V1n ) = H (U1n ) − H (U1n |V1n )
pode ser interpretada como uma redução na incerteza de U1n devido ao conhecimento de V1n .
A capacidade do canal, que representa a quantidade de informação que um canal pode
transferir, para um canal discreto sem memória é definida como
CAPÍTULO 3
46
 I (U1n ;V1n ) 
CCanal = max


p ( u1n )
n


(20)
Como o canal é fixo, a maximização é feita sobre todas as possíveis distribuições de entrada
p (u1n ) . Para um DMC, p(v1n | u1n ) = p(v1 | u1 )... p(vn | un ) , de forma que a capacidade do canal
pode ser expressa como
CCanal = max
I (U1 ;V1 )
n
p ( u1 )
(21)
O codificador de canal busca, então, maximizar a taxa de transmissão e minimizar os
efeitos do canal que deterioram a mensagem transmitida. Isto é feito pela inserção de
redundância aos dados.
Códigos que aumentam a redundância da seqüência de dados antes desta ser
transmitida pelo canal são divididos em duas classes: códigos em bloco e códigos em árvore.
Um código em bloco (n, k ) representa um bloco de k símbolos como uma palavra código de
n símbolos e taxa de transmissão
k
. Um código em árvore, apesar de também representar k
n
símbolos como uma palavra código de n símbolos, utiliza para isso uma memória que
armazena os últimos m segmentos de k símbolos. A palavra código é gerada por operações
entre os mk símbolos da memória, o que permite a representação do código em árvore,
caracterizando a dependência da palavra gerada com os símbolos de entrada anteriores. A
principal diferença entre estes códigos é que no código em árvore um segmento de k
símbolos pode influenciar todas as palavras código que o sucedem, enquanto no código em
bloco um bloco de k símbolos influencia apenas a próxima palava código de n símbolos.
Os códigos em árvore mais importantes são os códigos convolucionais. Estes códigos
satisfazem as propriedades de linearidade e invariância no tempo. Assim, um código em
árvore (n, k ) linear e invariante no tempo é um código convolucional (n, k ) . Códigos
convolucionais podem ser gerados por registradores de deslocamento lineares [5]. A
CAPÍTULO 3
47
seqüência de dados de entrada é quebrada em segmentos de k símbolos. Por considerações de
implementação, k é usualmente muito pequeno, geralmente igual a 1. O codificador
armazena m segmentos de dados de entrada e, a cada pulso do relógio de sincronismo, um
novo segmento de k símbolos é deslocado para dentro do codificador e o mais antigo é
deslocado para fora e descartado. Ou seja, a cada pulso do relógio de sincronismo o
codificador armazena os mk símbolos de entrada mais recentes. O codificador computa,
também a cada pulso do relógio de sincronismo, um segmento de códigos composto por n
símbolos. Assim que o próximo segmento de dados de k símbolos é deslocado para dentro do
codificador, o segmento de códigos de n símbolos é deslocado para fora e transmitido através
do canal de comunicação. Um algoritmo muito popular para decodificação seqüencial de
códigos convolucionais de complexidade moderada é o algoritmo de Viterbi [5], desenvolvido
em 1967. Devido às limitações de implementação, a taxa do código convolucional é limitada.
Não é possível implementar um código convolucional com taxa próxima a 1, o que pode ser
obtido utilizando um código em bloco.
Em geral, dá-se maior ênfase à análise de códigos lineares devido à sua simplicidade.
Esta classe de códigos é caracterizada por impor uma propriedade estrutural forte aos códigos,
o que facilita a busca por bons códigos e ajuda a tornar práticos os codificadores e
decodificadores. No entanto, os melhores códigos possíveis não são necessariamente lineares.
A busca por bons códigos em bloco normalmente se limita a códigos lineares porque grande
parte das técnicas teóricas mais fortes se aplica apenas a esta classe de códigos. Além disso,
ainda não foram encontrados métodos gerais para se encontrar bons códigos não lineares.
CAPÍTULO 3
48
3.1 Códigos em Bloco Lineares
A linearidade de um código em bloco garante que a soma (ou a diferença) de duas
palavras código resulta em uma outra palavra código. Em um código linear, a palavra
composta apenas por zeros é sempre uma palavra código.
A eficiência de um código de canal, ou o número de erros que este é capaz de corrigir,
é dada pela distância mínima deste código. A distância de Hamming entre duas seqüências de
n símbolos é dada pelo número de símbolos diferentes entre elas. A distância mínima d * de
um código de canal é dada pela menor distância de Hamming entre duas palavras código.
Para garantir que o código corrija e erros, é necessário que d * ≥ 2e + 1 [5]. Significa
que, para que um padrão recebido com erro seja detectado e corrigido por um código com
distância mínima d * , não mais que e símbolos podem ser diferentes da palavra código que
foi transmitida. Caso e + 1 símbolos sejam diferentes, a palavra código escolhida como sendo
a transmitida pode ou não ser a correta, uma vez que outra(s) palavra(s) código pode(m) distar
e do padrão recebido com erro. O mesmo vale para padrões que tenham mais de e + 1
símbolos diferentes da palavra transmitida, sendo que a probabilidade de se decodificar
corretamente certamente diminuirá com o aumento do número de símbolos diferentes, pois
aumentará a probabilidade do padrão recebido com erro apresentar menor distância de
Hamming em relação a outra palavra código que não a transmitida na codificação.
Um código é dito perfeito quando todas as palavras de comprimento n distam no
máximo e de uma palavra código e uma palavra que dista e de uma palavra código apresenta
maior distância em relação a qualquer outra palavra código. Códigos perfeitos são raros, o que
reduz sua importância em aplicações práticas.
Além disso, qualquer código linear (n, k ) satisfaz d * ≤ n − k + 1 , que significa que o
código deve ter no mínimo dois símbolos de paridade por erro a ser corrigido. Este limitante é
CAPÍTULO 3
49
conhecido como Singleton Bound [5]. No caso em que a distância mínima do código atinge o
limitante superior, ou seja, d * = n − k + 1 , o código é dito de distância máxima e possui
exatamente dois símbolos de paridade por erro a ser corrigido.
Pela forma como são geradas as palavras-código de um código linear, a distância
mínima do código de canal pode ser determinada pela distância de Hamming entre a palavra
formada por n zeros e a palavra código mais próxima a ela. Definindo o peso de um vetor
como o número de elementos diferentes de zero presentes neste, a distância mínima de um
código linear é dada pelo menor peso entre as palavras código, exceto a formada por n zeros.
Códigos de Hamming [5], primeiros códigos em bloco desenvolvidos e introduzidos
em 1950, são códigos em bloco lineares perfeitos capazes de corrigir um erro. São códigos
simples cujo principio serve de base para a construção da vários outros códigos lineares. Para
cada m existe um código de Hamming binário (2 m − 1, 2 m − 1 − m) com distância mínima
igual a 3.
Ainda dentro da classe de códigos em bloco lineares encontram-se os códigos cíclicos.
Estes levam a procedimentos de codificação e decodificação algoritma e computacionalmente
eficientes. Códigos BCH e Reed-Solomon [5] são exemplos de códigos cíclicos para correção
de múltiplos erros. Atenção especial é dada aos códigos Reed-Solomon por estes fazerem
parte da solução apresentada no capítulo 5.
3.2 Códigos Reed-Solomon
Códigos Reed-Solomon são muito utilizados na prática. Dentre as várias aplicações,
podem ser citadas a correção de erros em CDs (Compact Disks), DVDs (Digital Video Disks),
modems e nos três padrões de televisão digital implantados atualmente – americano (ATSC),
europeu (DVB) e japonês (ISDB).
CAPÍTULO 3
50
Códigos Reed-Solomon são um subconjunto do conjunto de códigos BCH em que o
comprimento da palavra-código é dado por n = q − 1 , onde q é o número de símbolos do
alfabeto. São também códigos de distância máxima ( d * = n − k + 1 ), o que significa que
possuem exatamente dois símbolos de paridade por erro a ser corrigido [5]. Portanto, para
(n, k ) fixos, nenhum código tem distância mínima maior que um código Reed-Solomon. O
número de símbolos de paridade é dado pela diferença entre o comprimento da palavra
código, n , e o número de símbolos na entrada do codificador que dá origem a uma palavra
código, k . Assim, para um código Reed-Solomon, n − k = 2e , onde e é o número de
símbolos com erro em um bloco que o código é capaz de corrigir e, conseqüentemente,
d * = 2e + 1 . Um código Reed-Solomon RS (n, k ) pode ser escrito como RS (n, n − 2e) .
Um codificador para um código Reed-Solomon pode ser sistemático ou não
sistemático, dado que todo código em bloco linear pode ser representado de forma
sistemática. Um código é dito sistemático quando os primeiros k símbolos da palavra código
de comprimento n são exatamente os símbolos que chegam ao codificador e os demais n − k
símbolos de paridade são escolhidos de forma a legitimar a palavra código. O código é não
sistemático quando os k símbolos da seqüência de dados que foi codificada não são
imediatamente reconhecidos no início da palavra código de comprimento n .
No caso em que o alfabeto é composto por q = 256 símbolos, que podem ter
representação binária, por exemplo, em que cada símbolo é composto por 8 bits, como é o
caso da tabela ASCII (American Standard Code for Information Interchange), tem-se
n = 255 . O código é então definido de acordo com o número de erros que se deseja corrigir
por bloco. Se e = 3 , tem-se RS (255, 249) , ou seja, a cada bloco de 249 símbolos que
chegam ao codificador de canal são adicionados 6 símbolos de paridade, resultando em uma
palavra código de 255 símbolos.
CAPÍTULO 3
51
Para decodificar um código Reed-Solomon pode-se utilizar qualquer decodificador de
códigos BCH ou códigos lineares, como o decodificador de Peterson-Gorenstein-Zierler, o
decodificador de Meggitt e o decodificador de Berlekamp-Massey [5].
CAPÍTULO 4
52
Capítulo 4
4 Codificação Conjunta Fonte-Canal
O estudo da codificação conjunta combina os conceitos de codificação de fonte e
codificação de canal apresentados nos capítulos anteriores. O problema é similar ao
apresentado na Figura 4 para codificação de fonte com a diferença de que o codificador e o
decodificador de fonte são conectados por um canal ruidoso e, neste caso, os blocos que
representam o codificador e o decodificador de fonte podem também considerar o codificador
e o decodificador de canal. A Figura 7 ilustra o problema tratado pela codificação conjunta
fonte-canal, em que a informação gerada pela fonte deve ser transmitida através de um canal
ruidoso.
Figura 7 – Codificação conjunta fonte-canal
A codificação pode ser feita em um ou dois passos, ou seja, com um código que
mapeia a saída da fonte diretamente em palavras código a serem transmitidas pelo canal ou
com o emprego de um codificador de fonte, que independe do canal, seguido de um
codificador de canal, que independe da distribuição da fonte. Independentemente de qual dos
métodos é empregado, o objetivo da codificação conjunta consiste em representar os dados na
saída da fonte da forma mais eficiente possível e garantir a confiabilidade da sua recepção,
permitindo que os dados sejam recuperados com probabilidade de erro extremamente baixa.
CAPÍTULO 4
53
4.1 Teorema da Separação e Velocidade de Convergência
O teorema da codificação conjunta fonte-canal apresentado em [6] afirma que, para
um processo estocástico X 1n = X 1 , X 2 ,..., X n , se
H (σ ) < CCanal ,
(22)
então existe um código fonte-canal que faz com que a informação da fonte seja transmitida
através do canal com uma probabilidade de erro arbitrariamente baixa. Reciprocamente, se
H (σ ) > CCanal , não é possível enviar a informação através do canal com baixa probabilidade
de erro. Este teorema foi primeiramente apresentado por Shannon em [2].
O teorema acima é válido para uma grande variedade de pares fonte-canal, mas
existem modelos bem particulares de fontes e canais não estacionários em que o teorema não
mais se aplica, como mostrado em [12]. Desde que a condição do teorema da codificação
conjunta seja satisfeita, tanto o esquema de codificação em um passo quanto o esquema em
dois passos podem ser empregados. Tradicionalmente, o esquema em dois passos é
empregado e os codificadores de fonte e canal são projetados separada e independentemente
para seqüências de n símbolos da fonte, com n suficientemente grande de forma que a
probabilidade de erro do canal convirja para zero quando n → ∞ . De fato, [2] e [6] mostram
que a codificação em dois passos é tão eficiente em termos de confiabilidade da transmissão
quanto qualquer outro método para transmissão da informação da fonte sobre um canal
ruidoso. Por isso o teorema da codificação conjunta é também conhecido como teorema da
separação.
Entretanto, quando a velocidade de convergência é considerada, a codificação em um
passo mostra-se mais eficiente que a codificação em dois passos. Csiszár mostrou em [13]
que, para fonte e canal discretos sem memória, a probabilidade de erro converge mais
rapidamente para zero quando n → ∞ quando a codificação é feita em apenas um passo do
CAPÍTULO 4
54
que quando codificadores de fonte e canal independentes são colocados em série. Vale
ressaltar que fonte e canal discretos sem memória constituem um caso muito simples de par
fonte-canal e, mesmo assim, há vantagem em se fazer a codificação conjunta.
Em [14], [15] e [16] são acrescentados alguns resultados a [13] para pares fonte-canal
arbitrários. Em [13], [14], [15] e [16] são feitas comparações entre os expoentes de erro para
codificação conjunta em um passo, EJ (Q, W ) , e em dois passos, ET (Q, W ) , que dependem
apenas da distribuição da fonte Q e da distribuição do canal W (são mantidas as
nomenclaturas usadas em [14], [15] e [16]). O expoente de erro E é um número com a
propriedade de que a probabilidade de decodificar erros de um código bom é
aproximadamente 2− En para códigos com grande comprimento de bloco n [16].
O resultado EJ (Q, W ) > ET (Q, W ) , quando aplicável, fornece suporte e justificativa
teóricos para o projeto da codificação conjunta em um passo ao invés da popular codificação
em dois passos, uma vez que a taxa de decaimento da probabilidade de erro é mais rápida para
a primeira. Isso também se traduz em redução de complexidade e redução de atraso para
sistemas de comunicação reais [16]. Em [16] também é mostrado que EJ (Q,W ) ≤ 2 ET (Q,W ) .
Assim, para uma mesma probabilidade de erro, o atraso provocado pela codificação conjunta
é em torno de metade do atraso provocado pela codificação em dois passos para pares fontecanal discretos sem memória.
É importante ressaltar que a codificação conjunta em um passo pode combinar os
processos de codificação de fonte e canal em um único passo realmente, mas também pode
realizar codificação de fonte e codificação de canal em seqüência. A diferença em relação à
tradicional (em dois passos) é que os dois processos de codificação não são independentes,
mas buscam se complementar a partir do momento que um codificador é projetado levando
em consideração características do outro. A partir deste ponto o termo codificação conjunta
fonte-canal será utilizado para representar a codificação conjunta realizada em um passo, ou
CAPÍTULO 4
55
seja, aquela em que os codificadores de fonte e canal são dependentes, não importando se são
combinados ou colocados em série.
Explorar a redundância remanescente na saída do codificador de fonte para prover
proteção contra erros inseridos pelo canal de transmissão de forma a permitir correta
decodificação no receptor, além de mais eficiente do ponto de vista teórico, também pode ser
mais interessante do ponto de vista prático. Isso porque utilizar um codificador de canal sem
considerar o codificador de fonte pode não proteger os dados adeqüadamente, uma vez que
erros em arquivos codificados por diferentes codificadores de fonte produzem efeitos
diferentes. Dependendo da localização do erro e do codificador de fonte utilizado, um erro
pode ser pouco notado ou pode inutilizar todo o arquivo.
Vários trabalhos foram publicados sobre implementação de codificação conjunta
fonte-canal empregando técnicas de codificação específicas. Dentre eles estão [17], [18] e
[19], sendo o último o que mais influenciou no desenvolvimento deste trabalho.
Em [17] são apresentas duas formas de se utilizar a estrutura na saída do codificador
de fonte para correção de erro. A primeira abordagem realiza uma combinação convencional
de codificador de fonte e codificador de canal convolucional, enquanto a segunda substitui o
codificador convolucional convencional por um codificador convolucional não binário, que
utiliza a redundância residual na saída do codificador de fonte com maior eficiência. Esta
abordagem é estendida a códigos de comprimento variável em [18]. Os codificadores
apresentados utilizam-se do conhecimento de propriedades da fonte ou do codificador de
fonte para detectar erros do canal e compensar seus efeitos.
Em [19] é apresentado um algoritmo para codificação conjunta denominado LZRS77
que permite corrigir erros no código gerado pelo codificador de fonte LZ77 com praticamente
nenhuma degradação na taxa de compressão. Para tal, a redundância remanescente no código
CAPÍTULO 4
56
gerado pelo LZ77 é explorada. O codificador de canal empregado é o Reed-Solomon. O
método é descrito a seguir.
4.2 Codificador LZRS77
Em [19], é primeiramente apresentado um método para explorar a redundância
remanescente no codificador LZ77 e recuperar os bits extras onde podem ser embutidos bits
de uma seqüência de dados qualquer, como seqüências para autenticação ou correção de erro.
Em seguida, é apresentado um método para realização da codificação conjunta fonte-canal,
onde os bits extras recuperados são utilizados para embutir o código de canal.
A redundância remanescente no codificador LZ77 é explorada pela possibilidade de
codificar os símbolos da seqüência de dados como mais de um ponteiro (posição,
comprimento, símbolo de inovação), ou seja, pode haver mais de uma subseqüência na
seqüência de dados já codificada que proporciona o maior match. Na prática, se existem r
subseqüências iguais aos símbolos da seqüência de dados, obtém-se  log 2 r  bits redundantes
pela escolha de um dos r ponteiros, onde t  representa o maior inteiro menor ou igual a
t ∈\ .
Para encontrar os bits adicionais a serem usados para codificação de canal, o LZ77 foi
levemente modificado. O algoritmo resultante, denominado LZS77, permite que alguns bits de
um texto T sobre o alfabeto {0,1} sejam embutidos no código. É possível embutir bits apenas
quando r > 1 . Especificamente, os próximos  log 2 r  bits de T determinam a escolha de um
dos r ponteiros.
Uma vez identificados os bits redundantes do LZ77, pode-se explorá-los para a
codificação de canal. Foram escolhidos os códigos Reed-Solomon RS (255 , 255 − 2e) ,
pertencentes à família de códigos BCH. Esse código acrescenta 2e bytes de paridade a
CAPÍTULO 4
57
255 − 2e bytes de dados, formando um bloco de 255 bytes. Erros até e bytes em qualquer
lugar do bloco podem ser detectados e corrigidos.
Os bits redundantes do LZS77 podem ser usados para embutir os 2e bytes extras. Se
for escolhido valor alto de e , pode não haver bits redundantes suficientes para embutir os bits
de paridade.
O codificador que realiza a codificação conjunta, LZRS77, comprime a seqüência de
dados de entrada usando o LZ77 padrão. Os dados são divididos em blocos de tamanho
255 − 2e . Depois, os blocos são processados na ordem reversa, começando pelo último.
Quando o bloco i está sendo processado, o codificador computa os bits de paridade do ReedSolomon para o bloco i + 1 e os embute nos bits redundantes do bloco i , utilizando o
algoritmo LZS77. Os bits de paridade do primeiro bloco não são embutidos, mas salvos no
começo do arquivo comprimido.
O decodificador LZRS77 recebe a seqüência de ponteiros precedida pelos bits de
paridade do primeiro bloco. A seqüência de entrada, retirados os bits de paridade do primeiro
bloco, é dividida em blocos de tamanho 255 − 2e bytes. Em seguida, os bits de paridade no
começo da seqüência comprimida são usados para checar, e possivelmente corrigir, o
primeiro bloco. Uma vez corrigido, o primeiro bloco é decodificado pelo LZS77, que além de
reconstruir a porção inicial do texto original, também recupera os bits extras embutidos pelas
escolhas de ponteiros específicos. Esses bits extras são os bits de paridade para o segundo
bloco e o decodificador pode corrigir possíveis erros neste bloco. O segundo bloco é então
decodificado e os bits de paridade para o terceiro bloco são recuperados. O processo continua
até que todos os blocos tenham sido decodificados.
O motivo de o codificador processar os blocos na ordem reversa é que os bits de
paridade do Reed-Solomon não podem ser computados antes que os ponteiros tenham sido
finalizados. Os bits de paridade do bloco atual são embutidos no bloco anterior, já que o
CAPÍTULO 4
58
decodificador precisa conhecer os bits de paridade de um bloco antes de tentar decodificá-lo.
Isto tem o efeito indesejável de tornar o codificador off-line, pois precisa que o codificador
mantenha todo o conjunto de buffers na memória principal.
CAPÍTULO 5
59
Capítulo 5
5 Codificação Conjunta Fonte-Canal Utilizando LZW e RS
A contribuição deste trabalho consiste em uma metodologia para codificação conjunta
fonte-canal que utiliza a redundância remanescente no código gerado pelo codificador de
fonte LZW para embutir os bytes de paridade do código de canal Reed-Solomon. O trabalho é
motivado pelos resultados teóricos apresentados no capítulo 4 que mostram que a taxa de
decaimento da probabilidade de erro é mais rápida quando é realizada a codificação conjunta.
A metodologia aqui proposta é possível porque os codificadores universais não
conseguem retirar toda a redundância presente em uma seqüência de dados finita, conforme
apresentado na seção 2.3. O LZW foi escolhido por apresentar, assim como o LZ78 e outras
variações deste, menor redundância que o LZ77 e suas variações. O objetivo é melhorar o
processo de codificação fonte-canal minimizando a taxa de dados por aproveitar parte da
informação inútil na saída de um bom compressor para proteger os dados contra imperfeições
do canal. O Reed-Solomon foi escolhido por ser um código de canal de distância máxima,
muito utilizado em aplicações práticas e de implementação relativamente simples.
A apresentação da metodologia começa por explicar como informação extra é
embutida no código LZW através da exploração de bits redundantes. Em seguida, explica-se
como realizar a codificação conjunta de fato.
É importante ressaltar que a exploração de bits redundantes apresentada para o LZW
pode ser estendida para o LZ78 e suas variações que mantém o princípio de atualização do
dicionário. O método não é válido para a variação do LZ78 criada por Gallager e apresentada
em [11].
CAPÍTULO 5
60
5.1 Embutindo Informação Extra no LZW
Parte da redundância remanescente neste código de fonte se deve ao fato do método do
maior prefixo, empregado pelo LZW, não fornecer a partição ótima. A partição ótima equivale
ao menor número possível de partições para codificar a seqüência de dados e,
conseqüentemente, à menor taxa de compressão possível. Como a função de um codificador
de fonte é retirar a redundância dos dados, se a partição encontrada não é ótima, significa que
ainda existe redundância neste código.
O método proposto encontra alternativas de partições de uma seqüência de dados de
entrada do codificador, utilizando os conceitos aplicados no algoritmo proposto em [20] para
melhorar o desempenho da partição.
O princípio do método é, dada uma seqüência x1n particionada em mLZW ( x1n )
subseqüências pelo codificador LZW padrão, encontrar todas as N partições possíveis de x1n
com a mesma quantidade de subseqüências, mLZW ( x1n ) . Dependendo de x1n e à medida que n
cresce, a quantidade de partições diferentes com o mesmo número de subseqüências, em
geral, também cresce. A determinação de todas as possíveis partições de x1n com mLZW ( x1n )
subseqüências é um problema complexo e, devido à semelhança deste problema com o
problema de se encontrar a partição ótima, talvez não exista nem mesmo um algoritmo
seqüencial capaz de solucionar esta questão. Assim, a solução implementada busca as N s ,
onde N s é um subconjunto de N , possíveis partições de duas subseqüências consecutivas a
partir do encurtamento da primeira, ou seja, relaxando o método do maior prefixo.
Sendo ( p1 ,..., pm
LZW
(x )
n
1
) a partição de x1n gerada pelo LZW padrão, para cada par de
( )
subseqüências ( pi , pi +1 ) , 1 ≤ i < mLZW x1n , de comprimento li são encontradas N i possíveis
CAPÍTULO 5
61
partições que produzem um par de subseqüências com comprimento li . Para computar N i , o
primeiro passo consiste em retirar o último símbolo de pi , caso esta subseqüência seja
formada por mais de um símbolo, e verificar a existência da nova subseqüência pi' +1 formada
pela concatenação do símbolo retirado de pi com pi +1 no dicionário. Caso este exista, N i ,
inicialmente igual a um, é incrementado e o novo par ( pi' , pi' +1 ) , onde pi' é pi encurtado de
um símbolo, é arquivado. pi' sempre existe no dicionário devido à forma como este é
construído, o que fica muito claro pela observação da árvore construída para representá-lo. O
passo seguinte consiste em repetir o procedimento para ( pi' , pi' +1 ) , começando por encurtar
pi' , e assim sucessivamente, até que a primeira subseqüência seja composta por apenas um
símbolo. Neste ponto, tem-se o valor final de N i e todos os possíveis pares de partições
derivados de ( pi , pi +1 ) que pertencem ao dicionário arquivados. Incrementa-se i e realiza-se
o mesmo procedimento para o par de partições seguintes, ( pi +1 , pi + 2 ) .
m −1
Ao final da seqüência x1n , tem-se N s = ∏ N i possibilidades de partições diferentes.
i =1
Isso permite que log 2 N s  bits, que representam os bits redundantes recuperados, de uma
seqüência de dados qualquer sejam embutidos no código LZW de x1n pela escolha adequada
das partições a serem transmitidas.
A atualização do dicionário continua sendo feita como no LZW padrão, ou seja, toda
subseqüência pi encontrada que representa o maior match pertencente ao dicionário é
concatenada ao símbolo de inovação que a segue e adicionada ao dicionário
independentemente de qual tenha sido a partição escolhida para transmissão, o que garante a
manutenção da taxa de compressão.
CAPÍTULO 5
62
Outra grande vantagem deste método, além de não alterar a taxa de compressão do
LZW padrão, é a capacidade de embutir bits de uma seqüência de dados qualquer sem
distorcer os dados originais, uma vez que a informação extra está no código LZW e não nos
dados de entrada do codificador.
A obtenção de partições diferentes se deve à forma de atualização do dicionário do
codificador. Como o dicionário do LZ78 e de suas variações, exceto a criada por Gallager e
apresentada em [11], se baseiam no mesmo princípio, o método para embutir informação
extra no LZW pode ser aplicado a estes compressores.
O exemplo seguinte ilustra o funcionamento do algoritmo para embutir bits extras no
código LZW:
Seja x1n = 0001001010010 .
O LZW padrão particiona x1n em ( p1 , p2 , p3 , p4 , p5 , p6 , p7 , p 8 ) = (0,00,1,001,0,10,01,0) .
O algoritmo apresentado procura outras possíveis partições para os pares ( pi , pi +1 ) ,
1 ≤ i < 8 , encurtando pi . Os pares ( p1 , p2 ) , ( p3 , p4 ) e ( p5 , p6 ) não podem ser particionados
de forma diferente, já que as subseqüências p1 , p3 e p5 não podem ser encurtadas. O par
( p2 , p3 ) também não permite outra partição, apesar da subseqüência p2 poder ser encurtada.
Isso porque, neste passo, o padrão 01 não pertence ao dicionário. O par ( p4 , p5 ) = (001, 0)
pode ser particionado em ( p4' , p5' ) = (00,10) . ( p6 , p7 ) permite a partição ( p6' , p7' ) = (1, 001) e
( p7 , p8 ) permite ( p7'' , p8' ) = (0,10) . Dessa forma, N 1 = 1, N 2 = 1, N 3 = 1, N 4 = 2, N 5 = 1, N 6 = 2
7
e N 7 = 2 . Então, N s = ∏ N i = 8 e log 2 N s  = 3 bits podem ser embutidos no código LZW
i =1
de x n através da escolha de uma das oito possíveis combinações obtidas com as partições
citadas. A Tabela 4 mostra uma classificação dessas opções em relação aos bits embutidos no
CAPÍTULO 5
63
código, os códigos correspondentes a cada partição, ou seja, as posições no dicionário dos
padrões que permitem os matches, e os respectivos códigos binários.
Tabela 4 – Embutindo bits extras no LZW
bits
embutidos
Partição de x1n
Código LZW
Código LZW binário
000
(0, 00,1, 001, 0,10, 01, 0)
1, 3, 2, 4, 1, 5, 7, 1
0 10 01 011 000 100 110 0000
001
(0, 00,1, 001, 0,10, 0,10)
1, 3, 2, 4, 1, 5, 1, 5
0 10 01 011 000 100 000 0100
010
(0, 00,1, 001, 0,1, 001, 0)
1, 3, 2, 4, 1, 2, 4, 1
0 10 01 011 000 001 011 0000
011
(0, 00,1, 001, 0,1, 00,10)
1, 3, 2, 4, 1, 2, 3, 5
0 10 01 011 000 001 010 0100
100
(0, 00,1, 00,10,10, 01, 0)
1, 3, 2, 3, 5, 5, 7, 1
0 10 01 010 100 100 110 0000
101
(0, 00,1, 00,10,1, 001, 0)
1, 3, 2, 3, 5, 2, 4, 1
0 10 01 010 100 001 011 0000
110
(0, 00,1, 00,10,10, 0,10)
1, 3, 2, 3, 5, 5, 1, 5
0 10 01 010 100 100 000 0100
111
(0, 00,1, 00,10,1, 00,10)
1, 3, 2, 3, 5, 1, 3, 5
0 10 01 010 100 001 010 0100
O decodificador LZW padrão deve ser ligeiramente modificado para decodificar a
palavra código gerada por este método. Como podem ser transmitidas subseqüências que não
representam o maior match, o decodificador deve fazer uma busca no dicionário para
identificar, a cada passo, o maior match presente nas duas últimas subseqüências recebidas e
acrescentar o novo padrão ao dicionário da mesma forma que o codificador. Além disso, deve
ser capaz de reconhecer os bits extras embutidos pelo codificador de acordo com as partições
recebidas, ou seja, deve buscar a cada duas subseqüências todas as possíveis partições que
possuam o mesmo comprimento. Identificando o par de partições recebido entre todos os
possíveis pares, recupera-se os bits embutidos.
CAPÍTULO 5
64
5.2 Codificação Conjunta
Após identificar a forma de embutir bits extras no código gerado pelo LZW, o objetivo
passa a ser embutir o código de canal. O código de canal escolhido é o Reed-Solomon
RS (255 , 255 − 2e) , para correção de até e símbolos errados por bloco de 255 símbolos.
Cada símbolo é representado por 8 bits, ou seja, um byte. Erro em um símbolo pode ser
ocasionado por erro em um bit ou em até 8 bits do byte. Os 2e bytes de paridade gerados pelo
codificador de canal para cada bloco de 255 − 2e bytes de dados devem ser embutidos no
código de fonte para que a taxa de compressão não seja diminuída.
A seqüência de dados a ser codificada é primeiramente dividida em grandes
segmentos. O último segmento é então comprimido pelo codificador de fonte LZW padrão ou
pela modificação deste apresentada acima que permite embutir bits extras. Neste momento,
contudo, não há dado algum a ser embutido e o codificador modificado opera como o LZW
padrão, escolhendo sempre a partição que equivale à encontrada pelo método do maior
prefixo.
Em seguida, este segmento comprimido é dividido em blocos de 255 − 2e bytes. O
codificador Reed-Solomon gera os 2e bytes de paridade para cada bloco de 255 − 2e . Os
bytes de paridade de todas as palavras-código de um segmento comprimido são concatenados
e formam um cabeçalho. Este cabeçalho é composto por mais uma informação, que representa
o comprimento do segmento comprimido. Os bytes que carregam esta informação são
concatenados ao início da seqüência de bytes de paridade. O conhecimento do comprimento
do segmento comprimido é muito importante para a decodificação.
O penúltimo segmento é então comprimido pelo LZW modificado e o cabeçalho do
último segmento é embutido no código de fonte resultante conforme descrito na seção 5.1. O
codificador de fonte comprime este segmento de forma independente da compressão do
CAPÍTULO 5
65
último segmento, começando uma nova árvore/dicionário. Em seguida, o segmento
comprimido é dividido em blocos de 255 − 2e bytes, o codificador Reed-Solomon gera os
bytes de paridade e o cabeçalho deste segmento é formado. O procedimento é repetido até o
primeiro segmento, sendo que o cabeçalho deste não é embutido. A seqüência codificada é
composta pela concatenação do cabeçalho do primeiro segmento e de todos os segmentos
codificados, começando pelo primeiro.
A codificação começa a ser feita pelo último segmento para que os bytes de paridade
dos blocos de um segmento estejam disponíveis antes da sua decodificação. Isso permite que
o decodificador decodifique os dados na ordem direta. A desvantagem do método, assim
como no LZRS77, é a necessidade de armazenar todos os segmentos comprimidos antes de
iniciar a transmissão dos dados, tornando o codificador off-line.
Quando um segmento está sendo codificado e o cabeçalho do segmento seguinte, que
está sendo embutido, é menor que o número de bits recuperados neste segmento, parte do
segmento comprimido seguinte é também embutida no código do segmento atual. Isto
melhora um pouco a taxa de compressão e aumenta a probabilidade de recuperação do
arquivo original.
A razão para aumentar a probabilidade de recuperação se deve ao fato de partes da
seqüência codificada, geralmente o começo de todos os segmentos comprimidos, exceto o
primeiro, não mais estarem susceptíveis a erro. O Reed-Solomon corrige erros em e símbolos
por bloco de comprimento n = 255 simbolos. Por embutir os 2e símbolos de paridade e
considerando que estes são corretamente recuperados pela decodificação do segmento
anterior, a capacidade de correção de erros aumenta para correção de e símbolos por bloco de
255 − 2e símbolos. Quando o começo do segmento comprimido é embutido, pode acontecer
de um ou mais blocos de 255 − 2e bytes serem completamente embutidos e/ou parte de um
bloco de 255 − 2e bytes de comprimento c ser embutida. No caso em que todos os bytes do
CAPÍTULO 5
66
bloco de 255 − 2e são embutidos, nenhum byte do bloco de comprimento n = 255 simbolos
será corrompido por erros e a proteção do código de canal passa a ser indiferente. Quando c
bytes do bloco de 255 − 2e símbolos são embutidos, a capacidade de correção de erros neste
bloco aumenta para correção de e símbolos por bloco de 255 − 2e − c símbolos.
O decodificador recebe a seqüência codificada e separa os bits correspondentes ao
cabeçalho do primeiro segmento. Como o cabeçalho carrega a informação relativa ao
comprimento do segmento comprimido, o número de blocos de 255 − 2e bytes e,
conseqüentemente, o número de bits de paridade são conhecidos. Os bits de paridade são
utilizados para checar e corrigir eventuais erros no primeiro segmento, desde que o número de
símbolos errados por bloco seja menor ou igual a e .
Em seguida, o primeiro segmento é decodificado pelo decodificador modificado
apresentado na seção 5.1, que, além de reconstituir a parte inicial da seqüência de dados
original, recupera os bits embutidos no código. Dos bits recuperados é extraído o cabeçalho
do segmento seguinte. Se o cabeçalho for menor que o número de bits recuperados, o começo
dos dados codificados do segundo segmento, que foi recuperado na decodificação do primeiro
segmento, é concatenado ao restante da seqüência de dados codificados para permitir a
continuação da decodificação.
Assim como para o primeiro segmento, o segundo segmento é checado e corrigido, se
necessário, e depois decodificado. O processo de decodificação de um segmento é
independente da decodificação dos demais, havendo construção de nova árvore. Os bits
embutidos no segundo segmento são recuperados e o processo se repete até o último
segmento, onde não há bits embutidos.
Apesar do processo de codificação conjunta proposto ser off-line por processar os
segmentos na ordem reversa e armazenar todos eles antes de iniciar a transmissão para
CAPÍTULO 5
67
permitir a decodificação na ordem direta, a seqüência de dados é codificada pelo codificador
de fonte uma única vez.
CAPÍTULO 6
68
Capítulo 6
6 Resultados
O codificador LZW foi implementado em software e em seguida modificado para
calcular o número log 2 N s  de bits redundantes recuperados nos arquivos comprimidos
através do método apresentado na seção 5.1. As medidas foram feitas para arquivos do Corpo
de Canterbury [21]. Este conjunto de dados é freqüentemente utilizado para avaliar o
desempenho de compressores. Os testes foram realizados com os arquivos do corpo que
apresentam maior comprimento. São eles: bible.txt, E.coli, world192.txt e kennedy.xls. Os três
primeiros pertencem ao Large Canterbury Corpus e o último pertence ao Standard
Canterbury Corpus.
A Tabela 5 apresenta o nome do arquivo, o tamanho n do arquivo em bytes, a taxa de
codificação
lLZW ( x1n )
em bits/bytes, o número de bits redundantes recuperados log 2 N s  e a
n
log N
razão entre o número de bits recuperados e o número de bytes do arquivo  2 s  .
n
A quantidade de bits que podem ser embutidos nestes arquivos seria suficiente para
incluir uma marca d’água, um código para verificar a autenticidade da informação, como uma
assinatura digital, ou um código para proteção contra erros introduzidos pelo canal, entre
outras aplicações. Em todos os casos, a informação adicional é embutida no código gerado
pelo codificador de fonte e não nos dados de entrada deste, o que significa que nenhuma
distorção é introduzida ao sinal original. Além disso, a taxa de compressão do codificador é
mantida inalterada.
CAPÍTULO 6
69
Tabela 5 – Bits recuperados
Arquivo
n
( x1n )
(bytes)
log 2 N s 
log 2 N s 
(bits/byte)
(bits)
(bits/byte)
lLZW ( x1n )
n
n
bible.txt
4.047.392
2,45
384.404
0,095
E.coli
4.638.690
2,12
181.475
0,039
kennedy.xls
1.029.744
2,49
93.930
0,091
world192.txt
2.473.400
2,57
251.848
0,102
2,41
227.914
0,082
Média
A quantidade de informação que pode ser embutida nos bits recuperados pelo método
proposto não pode ser comparada à quantidade de informação que se consegue embutir
através de métodos que introduzem distorções no sinal original. Como exemplo, existem
várias técnicas para embutir informações adicionais em imagens, como marca d’água e
esteganografia, mas quase todas elas provocam distorções no sinal original.
As medidas da quantidade de bits recuperados também foram realizadas para os
arquivos do Corpo de Calgary [22], utilizado para avaliar o desempenho de compressores
assim como o Corpo de Canterbury. Isto foi feito porque os resultados em [19] relativos à
quantidade de bits recuperados são apresentados para este conjunto de arquivos. A Tabela 6
mostra o tamanho do arquivo, a taxa de compressão e a razão entre o número de bits
log N
recuperados e o número de bytes do arquivo  2 s  para o método apresentado em [19],
n
LZS77, e para o método proposto aqui, que utiliza o LZW.
CAPÍTULO 6
70
Tabela 6 – Bits recuperados nos arquivos do Corpo de Calgary
Arquivo
n
( x1n )
(bytes)
lLZS 77 ( x1n )
n
log 2 N s 
n
LZS 77
lLZW ( x1n )
n
log 2 N s 
n
(bits/byte)
(bits/byte)
(bits/byte)
bib
111.261
2,84
0,124
3,35
0,126
book1
768.771
3,50
0,151
3,27
0,103
book2
610.856
2,99
0,136
3,15
0,111
geo
102.400
5,56
0,320
6,08
0,154
news
377.109
3,31
0,126
3,76
0,117
obj1
21.504
4,01
0,131
5,23
0,106
obj2
246.814
2,91
0,118
4,17
0,135
paper1
53.161
3,04
0,141
3,77
0,131
paper2
82.199
3,16
0,151
3,52
0,123
paper3
46.526
3,36
0,154
3,81
0,123
paper4
13.286
3,55
0,150
4,19
0,129
paper5
11.954
3,54
0,141
4,40
0,134
paper6
38.105
3,05
0,155
3,92
0,134
pic
513.216
0,95
0,047
0,97
0,040
progc
39.611
2,96
0,149
3,87
0,133
progl
71.646
2,06
0,123
3,03
0,127
progp
49.379
2,04
0,120
3,11
0,129
trans
93.695
1,89
0,103
3,26
0,134
3,04
0,141
3,71
0,122
Média
LZW
(bits/byte)
A ordem de grandeza das medidas realizadas para os dois métodos é a mesma. No
entanto, mais uma vez não é possível comparar os resultados diretamente, pois os métodos
operam em codificadores distintos, utilizando técnicas completamente diferentes. A técnica
utilizada pelo LZS77 não pode ser estendida ao LZW e vice-versa. Vale ressaltar que a taxa de
compressão atingida pelo codificador LZS77 é melhor que a taxa atingida pelo LZW porque o
CAPÍTULO 6
71
primeiro não se limita à codificação propiciada pelo LZ77 padrão, mas utiliza também outras
técnicas para melhorar a compressão.
Para implementar a codificação conjunta proposta na seção 5.2, os arquivos do Corpo
de Canterbury de maior comprimento foram divididos em segmentos. Os arquivos foram
divididos até que cada segmento apresentasse comprimento próximo a 150 kB. Os gráficos da
Figura 8 mostram a taxa de compressão,
lLZW ( x1n )
, e o número total de bits recuperados,
n
log 2 N s  , para os arquivos quando divididos em t segmentos.
A Tabela 7 mostra a média do aumento da taxa de compressão e do aumento do
número de bits recuperados a cada aumento do número de segmentos em que os arquivos
foram divididos, de acordo com os valores de t encontrados no eixo horizontal dos gráficos
da Figura 8 aplicáveis a cada arquivo.
Tabela 7 – Efeitos da segmentação dos arquivos na média
Arquivo
Média da variação de
lLZW ( x1n )
n
a cada segmentação
Média da variação de log 2 N s 
a cada segmentação
bible.txt
4,07 %
4,41 %
E.coli
0,93 %
6,34 %
kennedy.xls
-3,16 %
14,94 %
world192.txt
8,11 %
5,50 %
O número de bytes do arquivo original por segmento é aproximadamente
 log N 
número de bits recuperados por segmento é aproximadamente  2 s  .
t
n
e o
t
CAPÍTULO 6
72
Taxa de com pressão
bible.txt
3,6
E.coli
3,4
kennedy.xls
w orld192.txt
Taxa de compressão
3,2
3
2,8
2,6
2,4
2,2
2
1
2
4
8
16
32
t
Núm ero de bits recuperados
bible.txt
E.coli
600.000
kennedy.xls
w orld192.txt
Bits recuperados
500.000
400.000
300.000
200.000
100.000
0
1
2
4
8
16
32
t
Figura 8 – Efeitos da segmentação dos arquivos
A variação na taxa de compressão causada pela segmentação dos arquivos, que na
maioria das vezes corresponde a perdas (dentre os arquivos testados apenas o kennedy.xls
apresentou ganhos), não é relevante, uma vez que, em sistemas de comunicação reais, a
seqüência de dados a ser transmitida é segmentada por restrições de memória, em geral, e este
mesmo efeito é observado. Assim, o fato de se segmentar os arquivos apenas simula o que
CAPÍTULO 6
73
ocorre em sistemas de comunicação na prática. Em um satélite de sensoriamento remoto, por
exemplo, na medida em que os dados vão sendo capturados, estes são enviados para uma
estação para que sejam processados, ou seja, independentemente de ter-se chegado ao fim de
uma imagem, os dados são transmitidos porque o sistema não possui memória suficiente para
armazenar grande quantidade de informação, pois este não é seu objetivo. Outra limitação de
memória diz respeito à construção da árvore. Em algumas aplicações, a árvore que representa
o dicionário cresce até um limite pré-determinado e é então descartada e dá-se início a uma
nova codificação, baseada em um novo dicionário. Isto também equivale a segmentar o
arquivo, pois a cada segmento uma nova árvore é construída.
O número de bits recuperados aumentou em todos os arquivos testados quando
segmentados. Para analisar este fato, foram traçados os gráficos da Figura 9, onde as curvas
contínuas representam os dados reais e as retas pontilhadas, que unem o ponto inicial ao ponto
final de cada curva de dados reais, são traçadas apenas para facilitar a análise. Observando
estes gráficos, percebe-se que na parte inicial dos arquivos a derivada do número de bits
recuperados por bytes do arquivo original é maior que na parte final, ou seja, recupera-se mais
bits no começo da construção da árvore que representa o dicionário. Provavelmente,
segmentar os arquivos explora melhor esta característica, já que se tem uma nova árvore para
cada segmento. Este fenômeno, no entanto, precisa ser investigado com mais profundidade
em trabalhos futuros.
CAPÍTULO 6
74
5
4
bible.txt
x 10
3.5
3
bits recuperados
2.5
2
1.5
1
0.5
curva real
reta para referência
0
0
0.5
1
1.5
2
2.5
bytes do arquivo original
5
2
3
3.5
4
4.5
6
x 10
E.coli
x 10
1.8
1.6
1.4
bits recuperados
1.2
1
0.8
0.6
0.4
0.2
0
curva real
reta para referência
0
0.5
1
1.5
2
2.5
3
bytes do arquivo original
3.5
4
4.5
5
6
x 10
CAPÍTULO 6
75
4
10
kennedy.xls
x 10
9
8
7
bits recuperados
6
5
4
3
2
1
0
curva real
reta para referência
0
2
4
6
bytes do arquivo original
5
3
8
10
12
5
x 10
world192.txt
x 10
2.5
bits recuperados
2
1.5
1
0.5
curva real
reta para referência
0
0
0.5
1
1.5
2
bytes do arquivo original
Figura 9 – Comportamento da recuperação de bits ao longo dos arquivos
2.5
6
x 10
CAPÍTULO 6
76
Com o número de bits recuperados nos arquivos, foi calculado o número de bytes que
poderiam ser embutidos em cada um dos arquivos sem que a taxa de compressão fosse
alterada, desconsiderando-se o cabeçalho que é concatenado no começo da seqüência
comprimida no caso de se embutir o código de canal por segmentos. Como o objetivo é
embutir um código Reed-Solomon, o parâmetro utilizado para determinar a quantidade de
bytes a embutir foi o número de erros e que o código de canal é capaz de corrigir por bloco
de 255 bytes, uma vez que o número de bytes que deve ser embutido em um segmento é dado
pela multiplicação do número de blocos de 255 − 2e bytes do segmento seguinte por 2e
bytes. Independentemente do número de segmentos em que o arquivo foi dividido, o valor
máximo permissível de e para construção do código de canal para cada um dos arquivos
utilizados para teste é expresso na Tabela 8.
Tabela 8 – e máximo permissível
Arquivo
e máximo
bible.txt
E.coli
kennedy.xls
wold192.txt
4
2
5
4
Simulando a implementação do código de canal RS (255 , 255 − 2e) , foram verificadas
as taxas de compressão quando este código é embutido e quando ele é apenas concatenado à
seqüência de dados codificada, ou seja, quando não é feita a codificação conjunta. A média de
aumento da taxa de compressão para todos os valores de e permissíveis quando é realizada
codificação em dois passos em relação ao método de codificação conjunta proposto é ilustrada
na Figura 10 para todas as segmentações testadas. Para mesmo número de segmentos, códigos
de canal que corrigem de um erro até o valor máximo permissível apresentado na Tabela 8
para cada arquivo apresentam pouca variação na taxa de compressão. Para ilustrar este fato, a
CAPÍTULO 6
77
Tabela 9 mostra as taxas de codificação do arquivo bible.txt dividido em 4 e 16 segmentos
quando o código de canal RS (255 , 255 − 2e) é embutido e quando ele é concatenado, para e
variando de 1 a 4.
Aum ento da taxa de com pressão
bible.txt
6,0%
E.coli
Variação na taxa de compressão
5,5%
kennedy.xls
5,0%
w orld192.txt
4,5%
4,0%
3,5%
3,0%
2,5%
2,0%
1,5%
1,0%
0,5%
2
4
8
16
32
t
Figura 10 – Aumento da taxa de compressão quando o código de canal não é embutido
Tabela 9 – Taxas de compressão de bible.txt
t
4
16
lLZW ( x1n )
embutindo
n
lLZW ( x1n )
sem embutir
n
(bits/byte)
(bits/byte)
1
2
2,56
2,58
2,64
2,66
3,02 %
3,00 %
3
2,61
2,68
2,97 %
4
2,63
2,70
2,95 %
1
2,77
2,87
3,82 %
2
2,79
2,90
3,79 %
3
2,81
2,92
3,76 %
4
2,84
2,94
3,73 %
e
Aumento da taxa
de compressão
CAPÍTULO 6
78
A taxa de compressão é menor quando é feita a codificação conjunta porque os bytes
adicionados, correspondentes ao código de canal, são embutidos – a menos dos bytes do
código de canal referentes ao primeiro segmento, que são concatenados ao restante da
seqüência comprimida. Além disso, quando o número de bytes do código de canal obtido para
um segmento é menor que o número de bytes recuperados no segmento anterior, a parte
inicial da seqüência de dados deste segmento é também embutida no código do segmento
anterior. O aumento da taxa de compressão quando se realiza a codificação em dois passos
nos casos testados é de 3%, calculando-se a média entre todos os arquivos, chegando a 5,5%
para o arquivo que equivale ao melhor caso. Dependendo da aplicação, este valor é
significativo.
A manutenção da taxa de compressão do código de fonte após a implementação do
código de canal proporcionada pela codificação conjunta proposta traz vantagens aos sistemas
de comunicação reais. Para aplicações em que é realizada apenas codificação de fonte, podese proteger os dados sem custo adicional de potência ou banda de transmissão, já que a taxa
de compressão não é alterada. Para aplicações em que é realizada codificação de canal que
independe da codificação de fonte, a adoção da codificação conjunta pode proporcionar
economia em banda de transmissão ou potência, uma vez que a taxa de compressão é
melhorada.
Dada a probabilidade de erro de bit do canal BSC,
perro , e o código
RS (255, 255 − 2e) , é possível determinar o comprimento máximo da seqüência codificada à
qual são inseridos erros que permite recuperar o arquivo original com taxa de acerto
específica. Como a probabilidade de acerto de um bit é dada por pacerto = (1 − perro ) , a
probabilidade de acerto de um byte é pacerto _ byte = (1 − perro )8 e, conseqüentemente, a
probabilidade de erro de um byte é dada por perro _ byte = 1 − (1 − perro )8 . A probabilidade de
acerto de um bloco RS de 255 bytes capaz de corrigir até e erros é dada por
CAPÍTULO 6
79
e
 255 
255− i
pacerto _ bloco RS = ∑ 
( perro _ byte )i . A probabilidade de se recuperar um
 ( pacerto _ byte )
i
i =0 

arquivo formado por nb blocos RS de 255 bytes é pacerto _ nb blocos = ( pacerto _ bloco RS ) nb . Assim, temse
o
comprimento
n = 255nb = 255
máximo
log( pacerto _ nb blocos )
log( pacerto _ bloco RS )
da
seqüência
codificada
dado
por
. Definindo a taxa de acerto pacerto _ nb blocos , foi possível
construir a Tabela 10 ( pacerto _ nb blocos = 0,99 ) e a Tabela 11 ( pacerto _ nb blocos = 0,90 ) em função de
perro e e . Vale ressaltar que os comprimentos máximos encontrados nas tabelas representam
o pior caso, uma vez que são considerados blocos RS de 255 bytes, ou seja, nenhum byte é
embutido. Quando bytes são embutidos, o comprimento máximo do arquivo aumenta, pois
estes bytes não estão susceptíveis a erros.
Os dados das Tabela 10 e Tabela 11 permitem estabelecer sobre que canal, definido
por perro , determinado arquivo pode ser transmitido com sucesso e o número de segmentos
em que este deve ser dividido.
Tabela 10 – Comprimento máximo do arquivo comprimido, em bytes, para taxa de
acerto igual a 0,99
perro
e
2
3
4
5
0,001
6
15
45
146
0,0006
19
71
313
1.622
0,0003
105
725
6.151
62.407
0,0001
2.131
42.737
1,0 106
32,2 106
0,00006
9.292
309.180
12,8 106
645,7 106
0,00003
71.046
4,7 106
391,9 106
39,2 109
0,00001
1,8 106
369,5 106
92,0 109
27,6 1012
CAPÍTULO 6
80
Tabela 11 – Comprimento máximo do arquivo comprimido, em bytes, para taxa de
acerto igual a 0,90
perro
e
2
3
4
5
0,001
66
167
475
1.536
0,0006
201
748
3.288
17.004
0,0003
1.102
7.600
64.491
65.423
0,0001
22.342
448.020
11,2 106
338,4 106
0,00006
97.419
3,2 106
135,0 106
6,7 109
0,00003
744.800
49,4 106
4,1 109
411,4 109
0,00001
19,5 106
3,8 109
965,3 109
289,8 1012
Para testar a capacidade de decodificar os arquivos sem erro no receptor, foram feitas
simulações de transmissões dos arquivos por canais binários simétricos com diferentes
probabilidades de erro de bit perro , após terem passado pela codificação conjunta fonte-canal
utilizando LZW e RS (255 , 255 − 2e) . Os resultados das simulações são apresentados para
apenas uma segmentação de cada arquivo. A Tabela 12 mostra o número de segmentos em
que cada um dos arquivos foi dividido e o comprimento médio dos segmentos antes e após a
compressão.
Tabela 12 – Segmentação dos aquivos para simulação
Arquivo
Número de
segmentos
Comprimento
Comprimento médio do
médio do segmento
segmento comprimido
(bytes)
(bytes)
bible.txt
8
505.924
172.816
E.coli
4
1.159.673
312.113
kennedy.xls
2
514.872
159.341
world192.txt
4
618.350
232.665
CAPÍTULO 6
81
As Tabela 13, Tabela 14, Tabela 15 e Tabela 16 mostram a taxa de vezes em que os
arquivos foram decodificados sem erro no receptor, onde perro é a probabilidade de erro de bit
do canal e e é o número de erros que podem ser corrigidos por bloco de 255 bytes. Foram
feitas 150 simulações de transmissão de um mesmo arquivo, mantendo perro , e e t
constantes, para obtenção da média da taxa de acerto na recuperação apresentada nas tabelas.
Estes mesmos dados são utilizados para compor os gráficos da Figura 11, que ilustram o
comportamento da recuperação dos arquivos para diferentes perro e e .
Tabela 13 – Taxa de acerto na recuperação de bible.txt dividido em 8 segmentos
Perro
e=3
e=4
0,0001
80,67%
100,00%
0,0002
2,00%
78,00%
0,0003
0,00%
19,33%
0,0005
0,00%
0,00%
Tabela 14 – Taxa de acerto na recuperação de E.coli dividido em 4 segmentos
Perro
e=1
e=2
0,00001
44,00%
100,00%
0,00003
0,00%
86,67%
0,00006
0,00%
34,00%
0,00010
0,00%
0,00%
CAPÍTULO 6
82
Tabela 15 – Taxa de acerto na recuperação de kennedy.xls dividido em 2 segmentos
Perro
e=3
e=4
e=5
0,0001
97,33%
100,00%
100,00%
0,0003
2,00%
62,67%
94,67%
0,0006
0,00%
0,00%
15,33%
0,0010
0,00%
0,00%
0,00%
Tabela 16 – Taxa de acerto na recuperação de world192.txt dividido em 4 segmentos
Perro
e=3
e=4
0,0001
82,00%
98,67%
0,0003
0,00%
26,00%
0,0006
0,00%
0,00%
Para analisar a margem de erro dos resultados apresentados nas Tabela 13, Tabela 14,
Tabela 15 e Tabela 16, seja pa a probabilidade do arquivo ser recuperado sem erro.
Definindo a variável aleatória X i , que assume o valor 1 se o arquivo for recuperado
corretamente e o valor 0 se o arquivo não for recuperado corretamente, tem-se que
E[ X i ] = pa
Var (Y ) =
e
Var ( X i ) = pa (1 − pa ) .
Fazendo
Y=
1 n
∑ Xi ,
n i =1
tem-se
E[Y ] = pa
e
pa (1 − pa )
, onde n é o número de simulações ( n = 150 ). Aproximando Y de uma
n
variável aleatória gaussiana de média pa e variância
pa (1 − pa )
(aproximação motivada pelo
n
CAPÍTULO 6
83
teorema do limite central), tem-se que
Q(α ) =
1
2π
∫
α
−∞

p  Y − pa < α


pa (1 − pa ) 
 = 1 − 2Q(α ) , onde
n

2
e − z 2 dz .
Obtem-se α para determinado coeficiente de confiança, dado por 1 − 2Q(α ) , e
calcula-se os valores limites de
( y − pa )
2
=α2
pa , denominados
pa _1
e
pa _ 2 , pela equação
pa (1 − pa )
, onde y , uma realização de Y , é o resultado encontrado na
n
( 2 y + α n ) ± ( 2 y + α n ) − 4 y (1 + α n ) . A margem de erro é
=
2 (1 + α n )
2
simulação. Assim, pa _1,2
2
2
2
2
2
dada por pa _1 − pa _ 2 × 100% . A Tabela 17 mostra as margens de erro encontradas para
coeficiente de confiança igual a 0,95, sendo n = 150 e y variando de 0 % a 100 %.
Tabela 17 – Margens de erro para n = 150 e coeficiente de confiança de 0,95
y
Margem de erro de y
0%
2,50 %
10 %
9,69 %
20 %
12,73 %
30 %
14,52 %
40 %
15,49 %
50 %
15,80 %
60 %
15,49%
70 %
14,52 %
80 %
12,73 %
90 %
9,69 %
100 %
2,50 %
CAPÍTULO 6
84
Analisando a Tabela 10 (ou a Figura 11), vê-se que o comprimento máximo do
segmento comprimido que permite recuperar o arquivo com taxa de acerto de 0,99 (quando
não há bits embutidos) com perro = 0, 0001 e e = 4 é de 1 MB e para e = 3 é de 42,7 kB. O
comprimento do segmento comprimido do arquivo bible.txt é de aproximadamente 172,8 kB.
Como previsto, a recuperação do arquivo nas simulações com perro = 0, 0001 e e = 4 foi
realizada com sucesso em todas as 150 vezes (com margem de erro de 2,5%), conforme
apresentado na Tabela 13. Já para perro = 0, 0001 e e = 3 , como o comprimento do arquivo é
maior que o comprimento máximo indicado na tabela (e também o é no caso em que bits do
bloco RS são embutidos, já que a diferença entre eles não é tão significativa), a taxa de
sucesso na recuperação é inferior a 0,99. O mesmo pode ser verificado pela análise da Tabela
11. O comprimento máximo para perro = 0, 0003 e e = 4 é de 6,1 kB e para e = 3 é de 725 B
com taxa de acerto de 0,99. O segmento comprimido em questão é maior que os valores da
tabela para mesmo perro e e e, mais uma vez, as taxas de acerto na recuperação foram
inferiores a 0,99 nos dois casos. Quanto maior o comprimento do segmento comprimido em
relação ao máximo ilustrado na tabela, menor a taxa de recuperação com sucesso. Análise
similar para os demais arquivos permite validar os resultados encontrados nas simulações.
Quando os dados não são protegidos por um código de canal, a probabilidade de se
decodificar o arquivo sem erro após transmissão por canal ruidoso pode se tornar
extremamente baixa, dependendo da probabilidade de erro do canal e do comprimento do
arquivo. Por exemplo, para perro = 0, 0001 , a probabilidade de se decodificar corretamente o
arquivo bible.txt quando este é comprimido pelo LZW e o código de fonte transmitido é
composto por 1.241.873 bytes é igual a 0,99991.241.873 × 8 3 ×10−432 .
CAPÍTULO 6
85
Os resultados apresentados em [19] relativos à recuperação de arquivos codificados
pelo LZRS77 sem erro foram compilados nos gráficos da Figura 12. Os dois primeiros
gráficos mostram a probabilidade de se recuperar o arquivo sem erro para diferentes perro e e ,
sendo que no primeiro o arquivo testado tem 2,5 kB e no segundo, 25 kB. O terceiro gráfico,
construído com os dados relativos a e = 2 , permite a constatação de que quanto maior o
arquivo, menor a probabilidade de decodificá-lo corretamente. No entanto, é de se esperar que
exista um comprimento de arquivo a partir do qual a probabilidade de decodificar
corretamente não seja tão sensível ao aumento do comprimento. Isto foi observado nos testes
realizados com o método proposto neste trabalho, onde as probabilidades de recuperar os
arquivos corretamente não variaram para as segmentações apresentadas, que apresentavam o
menor comprimento próximo a 150 kB. Assim, as probabilidades de recuperação de arquivo
obtidas em [19] possivelmente serão reduzidas para arquivos de maior comprimento, como os
testados aqui.
CAPÍTULO 6
86
Recuperação de bible.txt dividido em 8 segm entos
100%
e=3
80%
e=4
60%
40%
20%
0%
0,0001
0,0002
0,0003
0,0004
0,0005
Recuperação de E.coli dividido em 4 segm entos
100%
e=1
80%
e=2
60%
40%
20%
0%
0,00001 0,00003 0,00005
0,00007 0,00009 0,00011
Recuperação de kennedy.xls dividido em 2 segm entos
e=3
100%
e=4
80%
e=5
60%
40%
20%
0%
0,0001
0,0003
0,0005
0,0007
0,0009
0,0011
Recuperação de world192.txt dividido em 4 segm entos
100%
e=3
80%
e=4
60%
40%
20%
0%
0,0001 0,0002 0,0003 0,0004 0,0005 0,0006 0,0007
Figura 11 – Taxa de acerto na recuperação dos arquivos
CAPÍTULO 6
87
Probabilidade do arquivo
ser recuperado
Recuperação de arquivo de 2,5 kB
100%
e=1
80%
e=2
60%
40%
20%
0%
0
0,0005
0,001
0,0015
0,002
0,0025
0,003
p
Probabilidade do arquivo ser
recuperado
Recuperação de arquivo de 25 kB
100%
e=1
e=2
80%
60%
40%
20%
0%
0
0,0001
0,0002
0,0003
0,0004
0,0005
p
Probabilidade do arquivo ser
recuperado
Recuperação de arquivos com diferentes com prim entos
100%
n = 2,5 kB
n = 25 kB
80%
60%
40%
20%
0%
0
0,0005
0,001
0,0015
0,002
0,0025
p
Figura 12 – Resultados obtidos com LZRS77
0,003
CAPÍTULO 7
88
Capítulo 7
7 Conclusões
Este trabalho apresentou uma técnica para embutir bits extras no código gerado pelo
codificador de fonte LZW, através da exploração da redundância remanescente no código
gerado por ele. Este algoritmo explora o fato de existirem diferentes formas de particionar
uma mesma seqüência de dados em padrões recorrentes sem alterar a taxa de compressão.
Escolhendo a partição de acordo com a seqüência de bits extras que se pretende embutir no
código, o algoritmo atinge o objetivo proposto sem reduzir o desempenho do codificador e
sem introduzir qualquer distorção nos dados originais. Este algoritmo também pode ser
aplicado ao LZ78 e aos demais algoritmos derivados deste que mantenham a forma de
atualização do dicionário.
Os testes mostraram que a quantidade de bits recuperados permite aplicações como
inclusão de marca d’água, código para verificar a autenticidade da informação ou um código
para proteção de erros introduzidos pelo canal. A quantidade de informação extra embutida
por este método não pode ser comparada à quantidade que se pode embutir com métodos que
introduzem distorções aos dados originais. Devido aos resultados que mostram que a taxa de
decaimento da probabilidade de erro é mais rápida quando é realizada a codificação conjunta,
este trabalho foi direcionado ao desenvolvimento de uma técnica de codificação conjunta
baseada na utilização dos bits recuperados no código gerado pelo LZW para embutir um
código de canal.
A técnica proposta para realização da codificação conjunta, faz uso do codificador de
canal Reed-Solomon RS (255, 255 − 2e) , onde e é o número de símbolos com erro que o
CAPÍTULO 7
89
código é capaz de corrigir por bloco de 255 bytes. A seqüência de dados codificada pelo
LZW é dividida em segmentos e o código de canal gerado para proteger um segmento é
embutido nos bits recuperados no segmento anterior. Para os arquivos testados, os bits
recuperados permitiram que códigos que corrigem até 5 erros fossem embutidos. Foi
verificada também a variação da taxa de compressão quando realizou-se a codificação
conjunta proposta ou a codificação em dois passos, em que a codificação de fonte é realizada
de forma independente da codificação de canal. Esta variação não foi muito expressiva, mas
pode ser significativa em algumas aplicações.
A manutenção da taxa de compressão do código de fonte após a implementação do
código de canal proporcionada pela codificação conjunta proposta traz vantagens aos sistemas
de comunicação reais. O objetivo da utilização de códigos de fonte e canal é melhorar a
relação de compromisso entre os recursos utilizados nestes sistemas, que pode ser a largura de
banda ou a potência de transmissão, e a sua qualidade, normalmente interpretada como a
confiabilidade na recepção dos dados. Para aplicações em que é realizada apenas codificação
de fonte, a adoção da codificação conjunta permite aumentar a confiabilidade do sistema sem
custo adicional de potência ou banda de transmissão, já que a taxa de compressão não é
alterada. Para aplicações em que as codificaçãoes de fonte e canal são realizadas
independentemente, a adoção da codificação conjunta pode proporcionar melhorias na relação
de compromisso entre os recursos utilizados no sistema, uma vez que a taxa de compressão é
melhorada.
Para trabalhos futuros, sugere-se investigar e mensurar a quantidade da redundância
remanescente nos códigos de fonte gerados por codificadores universais derivados do LZ78
que é explorada pelo método proposto.
REFERÊNCIAS BIBLIOGRÁFICAS
90
Referências Bibliográficas
[1]
HAYKIN, S. Communication Systems. [S.l.]: Wiley, 2001.
SHANNON, C. E. A mathematical theory of communication. Bell System Technical
Journal, v.27, p. 379-423, 1948.
[2]
[3]
WELCH, T. A. A technique for high-performance data compression. IEEE Computer,
v. 17, n. 6, p. 8-19, 1984.
ZIV, J.; LEMPEL, A. Compression of individual sequences via variable-rate coding.
IEEE Transactions on Information Theory, v. 24, p. 530-536, 1978.
[4]
[5]
BLAHUT, R. E. Algebraic Codes for Data Transmission. Cambridge: Cambridge
University Press, 2003.
[6]
COVER, T. M.; THOMAS, J. A. Elements of Information Theory. [S.l.]: Wiley, 1991.
RISSANEN, J. Complexity of strings in the class of Markov sources. IEEE
Transactions on Information Theory, v. 30, p. 629-636, 1984.
[7]
ZIV, J.; LEMPEL, A. A universal algorithm for sequencial data compression. IEEE
Transactions on Information Theory, v. 23, p. 337-343, 1977.
[8]
LEMPEL, A.; ZIV, J. On the complexity of finite sequences. IEEE Transactions on
Information Theory, v. IT-22, p. 75-81, 1976.
[9]
SAVARI, S. A. Redundancy of the Lempel-Ziv string matching code. IEEE
Transactions on Information Theory, v. 44, p. 787-791, 1998.
[10]
SAVARI, S. A. Redundancy of the Lempel-Ziv incremental parsing rule. IEEE
Transactions on Information Theory, v. 43, p. 9-21, 1997.
[11]
VEMBU, S. VERDÚ, S. The joint source-channel separation theorem revisited. IEEE
Transactions on Information Theory, v. 41, p. 44-54, 1995.
[12]
REFERÊNCIAS BIBLIOGRÁFICAS
91
CSISZÁR, I. On the error exponent of source-channel transmission with a distortion
threshold. IEEE Transactions on Information Theory, v. 28, p. 823-828, 1982.
[13]
ZHONG, Y.; ALAJAJI, F.; CAMPEL, L. L. When is joint source-channel coding
worthwhile: an information theoretic perspective. In: BIENNIAL SYMPOSIUM
COMMUNICATIONS., 22., Canadá, 2004. Proceedings... Canadá: [s.n.], 2004.
[14]
ZHONG, Y.; ALAJAJI, F.; CAMPEL, L. L. On the computation of the joint sourcechannel error exponent for memoryless systems. In: IEEE INTERNATIONAL
SYMPOSIUM INFORMATION THEORY (ISIT), Chicago, IL, July 2004.
Proceedings...Chicago: [s.n.], 2004.
[15]
ZHONG, Y. ; ALAJAJI, F.;. CAMPEL, L. L. On the joint source-channel coding error
exponent for discrete memoryless systems. IEEE Transactions on Information Theory, v. 52,
p. 1450-1468, 2006.
[16]
SAYOOD, K.; LIU, F.; GIBSON, J. D. A constrained joint source/channel coder
design. IEEE Journal on Selected Areas in Communications, v. 12, p. 1584-1593, 1994.
[17]
SAYOOD, K.; OUT, H. H.; DEMIR, N. Joint source/channel coding for variable
length codes. IEEE Transactions on Communications, v. 48, p. 787-794, 2002.
[18]
LONARDI, S.; SZPANKOWSKI, W. Joint source-channel LZ’77 coding. In: IEEE
DATA COMPRESS CONFERENCE, 2003. Proceedings... [S.l.]: IEEE, 2003.
[19]
PINHO, M. S.; FINAMORE, W. A.; PEARLMAN, W. A. Fast multi-match LempelZiv. In: IEEE DATA COMPRESS CONFERENCE, 1999. Proceedings... [S.l.]: IEEE, 1999.
[20]
ARNOLD, R.; BELL, T. A corpus for the evaluation of lossless compression
algorithms. In: IEEE DATA COMPRESS CONFERENCE, 1997. Proceedings... [S.l.]: IEEE,
1997. p. 201-210.
[21]
[22]
BELL, T. C.; CLEARY, J. G.; WITTEN, I. H. Text Compression. [S.l.]: PrenticeHall, 1990.
FOLHA DE REGISTRO DO DOCUMENTO
1.
5.
CLASSIFICAÇÃO/TIPO
2.
TM
DATA
13 de abril de 2007
3.
DOCUMENTO N°
4.
CTA/ITA-IEE/TM-002/2007
N° DE PÁGINAS
91
TÍTULO E SUBTÍTULO:
Codificação conjunta fonte-canal utilizando codificadores universais adaptativos
6.
AUTOR(ES):
Mariana Olivieri Caixeta Altoé
7.
INSTITUIÇÃO(ÕES)/ÓRGÃO(S) INTERNO(S)/DIVISÃO(ÕES):
Instituto Tecnológico da Aeronáutica. Divisão de Engenharia Eletrônica – ITA/IEE
8.
PALAVRAS-CHAVE SUGERIDAS PELO AUTOR:
Codificação conjunta fonte-canal; codificadores universais; compressão de fonte; embutindo informação
extra
9.PALAVRAS-CHAVE RESULTANTES DE INDEXAÇÃO:
Codificação concatenada; Codificadores; Codificação redundante; Compressão de dados; Códigos de
correção de erros; Transmissão de sinais; Telecomunicações; Engenharia eletrônica
10.
X Nacional
APRESENTAÇÃO:
Internacional
ITA, São José dos Campos, 2007, 91 páginas
11.
RESUMO:
Tradicionalmente, codificação de fonte e codificação de canal são tratados independentemente, no que se
denomina sistema de codificação em dois passos. Isso ocorre porque o teorema da separação das
codificações de fonte e canal garante que não há perdas em termos de confiabilidade da transmissão em
assim fazê-lo quando o volume de dados gerados pela fonte cresce indefinidamente. No entanto, para
seqüências finitas, foi mostrado que pode ser mais eficiente realizar a codificação em apenas um passo,
denominada codificação conjunta fonte-canal, que faz uso das características da fonte ou do codificador
de fonte para prover proteção contra erros. Este trabalho propõe uma técnica de codificação conjunta
utilizando codificadores de fonte e canal consagrados e encontrados em aplicações práticas. São eles o
codificador universal adaptativo LZW e o codificador de canal Reed-Solomon. O método proposto utiliza
o fato do codificador de fonte não remover completamente a redundância dos arquivos originais para
adicionar bits extras, sem perda de desempenho e sem distorção dos dados originais. A redundância
remanescente no código é então utilizada para embutir os bits de paridade do código de canal. O
desempenho do método é medido através de sua aplicação em arquivos dos corpos de Calgary e
Canterbury. A exploração da redundância remanescente no código gerado pelo LZW pode ser aplicada
aos codificadores universais LZ78 e suas variações que se baseiam no mesmo princípio de atualização do
dicionário.
12.
GRAU DE SIGILO:
(X ) OSTENSIVO
( ) RESERVADO
( ) CONFIDENCIAL
( ) SECRETO