ads:
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial
DISSERTAÇÃO
apresentada à UTFPR
para obtenção do grau de
MESTRE EM CIÊNCIAS
por
ZAQUEU CABRAL PEREIRA
ESQUEMA DE PROTEÇÃO DESIGUAL USANDO CÓDIGOS REED-SOLOMON
PARA DADOS COMPACTADOS COM LZSS
Banca Examinadora:
Presidente e Orientador:
Prof. Dr. RICHARD DEMO SOUZA UTFPR
Examinadores:
Prof. Dr. BARTOLOMEU FERREIRA UCHOA FILHO UFSC
Prof. Dr. MARCELO EDUARDO PELLENZ PUC-PR
Curitiba, 25 de maio de 2007.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ZAQUEU CABRAL PEREIRA
ESQUEMA DE PROTEÇÃO DESIGUAL USANDO CÓDIGOS REED-SOLOMON
PARA DADOS COMPACTADOS COM LZSS
Dissertação apresentada ao Programa de
Pós-Graduação em Engenharia Elétrica e Infor-
mática Industrial da Universidade Tecnológica
Federal do Paraná, como requisito parcial para
a obtenção do grau de "Mestre em Ciências"-
Área de Concentração: Telemática
Orientador: Prof. Dr. Richard Demo Souza
Curitiba
2007
ads:
Agradecimentos
Gostaria de agradecer primeiro a Deus pela inspiração, força e saúde.
A meu orientador, Prof. Richard Demo Souza, pela amizade, paciência, compreensão e
condução durante todo o mestrado e especialmente durante o desenvolvimento desta disserta-
ção.
Ao Prof. Marcelo Eduardo Pellenz, pela amizade e pelas contribuições neste trabalho.
Ao Prof. Natanael Rodrigues Gomes, pela incentivo inicial para a pesquisa.
Ao amigos do LASD e a todos os demais amigos e familiares.
À agência financiadora CAPES, pelo auxílio material.
Aos meus pais e minha irmã pelo amor e pelas constantes apostas em mim.
E por último, mas não menos importante à minha namorada Karoline Guerra pela compre-
ensão, amor e apoio incondicional durante todo o tempo do mestrado em que estive distante.
iii
Sumário
Lista de Figuras p.vi
Lista de Tabelas p.viii
1 Introdução p.11
1.1 Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.13
2 Compressão de Dados p.15
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.15
2.2 Compressão com Perdas . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
2.3 Compressão sem Perdas . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.17
2.3.1 Introdução à Teoria da Informação . . . . . . . . . . . . . . . . . . . p. 18
2.3.2 Teorema da Codificação de Fonte . . . . . . . . . . . . . . . . . . . p.20
2.3.3 Modelagem de uma Fonte . . . . . . . . . . . . . . . . . . . . . . . p. 21
2.4 Algoritmos de Compressão sem Perdas . . . . . . . . . . . . . . . . . . . . p. 21
2.4.1 LZ77 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
2.4.2 LZSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25
2.5 Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.27
3 Métodos de Proteção Desigual de Erros para LZSS p.28
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.28
3.1.1 Impacto dos Surtos de Erros no Processo de Descompressão . . . . . p. 29
3.2 Esquema Proposto por Kitakami e Kawasaki . . . . . . . . . . . . . . . . . . p. 32
3.2.1 Procedimento de Codificação . . . . . . . . . . . . . . . . . . . . . p.33
3.2.2 Procedimento de Decodificação . . . . . . . . . . . . . . . . . . . . p.34
3.2.3 Avaliações sobre o método . . . . . . . . . . . . . . . . . . . . . . . p. 35
3.3 Esquema Proposto por Siqueira . . . . . . . . . . . . . . . . . . . . . . . . . p.37
3.3.1 Método de Proteção Desigual . . . . . . . . . . . . . . . . . . . . . p. 37
3.3.2 Avaliações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 38
3.4 Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.38
4 Esquema de Proteção Desigual Usando Códigos Reed-Solomon p.39
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.39
4.2 Proposta do Método de Proteção Desigual de Erros para LZSS . . . . . . . . p. 41
4.3 Resultados de Simulações . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42
4.4 Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.48
5 Conclusão p.49
Apêndice A -- Calgary Corpus p.50
Apêndice B -- Códigos Reed-Solomon p.52
Referências p.54
v
Lista de Figuras
2.1 Exemplo das operações de compressão e reconstrução [8]. . . . . . . . . . . . . . p. 16
2.2 Exemplo de uma janela deslizante do codificador LZ77 [8]. . . . . . . . . . . . . p.23
2.3 Exemplo de codificação usando o método LZ77. . . . . . . . . . . . . . . . . . . p.24
2.4 Exemplo de codificação usando o método LZSS. . . . . . . . . . . . . . . . . . . p. 26
3.1 Exemplo dos casos de erros aleatórios e surto de erros [36]. . . . . . . . . . . . . p.29
3.2 Relação entre a taxa de compressão e número de bits de match para o arquivo ’pa-
4.3 Estrutura geral do arquivo compactado depois da aplicação da proteção desigual. . . p. 42
4.4 Efeito do surto de erros no processo de descompressão, em termos da SER em função
da posição do surto de erros, para o arquivo ’paper4.txt’ usando proteção uniforme
de erros com t = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.43
4.5 Efeito do surto de erros no processo de descompressão, em termos da SER em função
da posição do surto de erros, para o arquivo ’paper4.txt’ usando proteção uniforme
de erros com t = 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.44
4.6 Efeito do surto de erros no processo de descompressão, em termos da SER em fun-
ção da posição do surto de erros, para o arquivo ’paper4.txt’ usando o esquema de
proteção desigual de erros para os flags. . . . . . . . . . . . . . . . . . . . . . . p.45
4.7 Efeito do surto de erros no processo de descompressão, em termos da SER em fun-
ção da posição do surto de erros, para o arquivo ’paper4.txt’ usando o esquema de
proteção desigual de erros para os matches. . . . . . . . . . . . . . . . . . . . . p.46
4.8 Efeito do surto de erros no processo de descompressão, em termos da SER em fun-
ção da posição do surto de erros, para o arquivo ’paper4.txt’ usando o esquema de
proteção desigual de erros para os flags e os matches. . . . . . . . . . . . . . . . . p. 47
A.1 Estrutura de um dado codificado com código Reed Solomon . . . . . . . . . . . . p.52
vii
Lista de Tabelas
2.1 Classificação dos tipos de codificação de dados em função das características dos
dados de entrada e saída [29]. . . . . . . . . . . . . . . . . . . . . . . . . . . . p.22
3.1 Parâmetros do arquivo compactado a partir do arquivo ’paper4.txt’. . . . . . . . . . p.30
3.2 Comparação entre taxa de compressão do método proposto por Kitakami e Kawa-
saki, e as taxas de compressão do LZSS [6] e do LZ77 [5]. . . . . . . . . . . . . . p. 35
3.3 Comparação entre o esquema proposto por Siqueira [23] e uma proteção uniforme
usando códigos Reed-Solomon. . . . . . . . . . . . . . . . . . . . . . . . . . . p.38
4.1 SER média no arquivo descompactado e a redundância adicional inserida no arquivo
compactado pelo esquema de proteção desigual proposto para os arquivos paper1,
paper2, paper3, paper4, paper5 e paper6. . . . . . . . . . . . . . . . . . . . . . . p.45
4.2 SER média no arquivo descompactado e a redundância adicional inserida no arquivo
compactado pelo esquema de proteção desigual proposto para os arquivos progc,
progp e obj1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 46
4.3 Aumento no tamanho do arquivo compactado requerido para proteger os flags e os
matches contra um surto de erros de 20 bits. . . . . . . . . . . . . . . . . . . . . p. 47
A.1 Tipos dos arquivos da base de dados Calgary Corpus [24] . . . . . . . . . . . . . p. 51
A.2 Detalhes numéricos dos arquivos da base de dados Calgary Corpus [24] . . . . . . . p. 51
Resumo
A compressão de dados é muito utilizada em sistemas computacionais e de comunicações.
Técnicas de compressão sem perdas, em especial códigos Lempel-Ziv, são aplicadas para com-
pressão de texto. O efeito devastador dos erros na descompressão de dados Lempel-Ziv é um
problema em aberto há muito tempo. Como os dados compactados são muito sensíveis a er-
ros, vários métodos para controle de erros têm sido propostos. Este trabalho apresenta uma
estratégia de proteção desigual de erros para minimizar o impacto dos surtos de erros no ar-
mazenamento e na transmissão de dados compactados. A estratégia é feita para o algoritmo
LZSS, o qual é um método de compressão de dicionário adaptativo. Através de extensivas si-
mulações computacionais foram investigadas quais classes de informação dentro do LZSS são
mais sensíveis aos surtos de erros. Baseados nesses resultados, foi proposta uma estratégia de
proteção desigual de erros que reduz totalmente a propagação de erros durante o processo de
descompressão. Para validação dos resultados, são apresentados resultados numéricos usando
arquivos de texto de uma base de dados conhecida. Além disso, são apresentadas compara-
ções de desempenho com um esquema de proteção uniforme e com dois esquemas de proteção
desigual.
ix
Abstract
Data compression is often used in computer and communicatons systems. Lossless com-
pression, especially Lempel-Ziv coding, is commonly applied to text compression. The devas-
tating effect of errors in Lempel-Ziv data decompression is a long-standing open problem. In
fact, since compressed data are very sensitive to errors, several error control methods have been
proposed. This work proposes an unequal error protection strategy for minimising the impact of
error bursts in the storage or transmission of compressed data. The strategy is designed for the
LZSS algorithm, which is a dynamic dictionary compression method. Through extensive com-
puter simulations, we investigate which information classes within LZSS are more sensitive to
burst errors. Based on these results we propose an unequal error protection strategy that greatly
reduces the error propagation during the decompression process. Numerical results using text
files from a common database are presented. Comparisons of performance with a equal error
protection scheme and two unequal error protection schemes, are also presented.
x
11
1 Introdução
Para um melhor aproveitamento, dispositivos de armazenamento e recursos de comunica-
ções limitados requerem a utilização de técnicas poderosas de compressão de dados. No caso de
a informação ser texto [1], banco de dados [2] ou alguns tipos de imagens [3,4] , os algoritmos
de compressão sem perdas do tipo Lempel-Ziv são os mais utilizados [5–9]. Em sistemas mul-
timídia, eles são necessários para manipular, armazenar e transmitir uma grande quantidade de
informação de dados com maior eficiência [10]. Contudo, dados compactados são muito sensí-
veis a erros devido aos efeitos da propagação de erros durante o processo de descompressão.
Sistemas de armazenamento de dados em dispositivos semicondutores [11], magnéticos ou
óticos com grande capacidade e acesso rápido, são suscetíveis a erros na leitura e no armazena-
mento, onde surtos de erros podem ocorrer devido a regiões defeituosas [12,13]. Surtos de erros
também podem ocorrer devido a um desvanecimento profundo 1(t)-3.0509am18(r)12(d)-1.87464742.34941(m)-4.92563(a)2.36236(8(ã)2.3505(o)-2427468(o)-1.87468(e)-298.715(c)2.35254(o)-1.87468(m)-4.92563(u)-1.87468(n)-1.87468(i)-3.05095(ç1.87468(i-243.333(s)-2..46281(ã)2.3505(o)-252.669(t)-3.04686()-1.87468(1(t)1.7644]TJ-28r)-239.7n)-1.8746836(-3.04891(a)-258.612([41.76032(1)-1.18744(d))-258.612([571.1684(1)-1.87491(a)-14746867(D)1.3500452m)-255.81(d)-1.87468(ã)2.3505(o)-2.8787468(7.516 -19.4-245.786(p)-1.87468(o)-245.7867(1)-11.87409)-238.489(e)-23.92563(e)2.35254(n)42.34941(m-1.87491(aã)2.3505(o)-2.3.54321(r)1.76236(e)2.34948(q)-1.878747i)-3.878747i))1.34913o)-1.87468(u)-252.747()2.35254(n)4203.543(d)d2.34948(q)-1.878747irce-255.816(d)-1.87464(i)-3.0499724(c)2.3505(i)-3.04891(ê)2.3505(n)-1.87468(c)2.34948(r4203.543(d)e3.04891(l19458.591(t)]TJ280.e)2.34948(r)1.76236(r)1.3509592(d)-1.87468(a)2.3505(d)-1..466931)-1.87468(o)-232.685(r)1.76236(e)2.34948(q)-3.05095(t)-3.04891(i)17.0437(v)18.9669(e)2.35254(s)-2.4669(c)2.35254(o)-1.87468(m)-4.92563(p)-1.87468(a)2.34845(c)2.35254(t)-3.05095(a)2.35254(d)-1.82154(o)-1.91(l19452.46281]TJ-29e)2.3498osrerrr as lmaços pécnicão ocorzaçde a erroa [6-258.612([)1.76032(5) 871.1684(1)-1rtpain, armazen-3.05095(t)-242.724(s)-2.46281(e)2.35254(n)-1.8746701(i)17.0437(v-249249668(a)2.34845(c-258.604(g)-1.87468(r)1.76032(aa)2.3505(n)-1.87463(i)-3.04916(d)-1.87464(i)-2.46281(í)-3.899.79(t)1.7644]TJ-28-1.874643i-243.3991(i)12846286t)-3.05095(a)2.35254(d)-1.87354(d)-1.87468(e)-248.529(d)-1.87468(a)2.34948(d)-1.8835474)-1.87519(e)-248.529(c)2.34948(o)-1.87468(m)-248.542(e)-23519(e5.435 -19.5598 Td4t)-3.05095(u)-1.87468(d)-1.87464(i) oãoamrr-3.0499724((r)1.76441(z)2.3505(a)2.3505(ç)2846287)r dc-258.6.80á(a)7896705(ç)294680s efeivu mpropaç1.87468(i-243..3505(ç)284628o)-1.87468(s)-21378966oe errd graac-21378966oudaç1P1.76032(.)-1.87519(f)1.76236(o-208.404(t-1.87463(i))-1120806u)-1.87468(e)2.3505(m)-4.9250din m d-1.87468(i)mun çso de té03.174(d558.16854(e)]TJ205(n)-1.87468(i)-3.05095(c).4669(8(c)2.3505(o)-2528897(d)e)2.35254(s)-2.4669(ce)2.3505(m)-255.816(d)r)-239.091(e)2.5095()-1.87468(ç1.87468(i-243.333(s)-2874681(ã)2.34845(o)-212.543(d)f)2.35254(r)1.76032(rr)1.76032(aa)2.34845(c-213889776)-2528897(d)-1.87468(e)-248.536(d)-1.84(d558.)1.7644]TJ-28c243.3991(598 Td[(t402 Td[(i)598 Td4t)l1.76238(o)-1.87519(e)-248.529(cn-1.87468(aã)2.3505(o)-249.175(ta)2.3505(l)-3.04891(g)i.435 -19.5u))1276276(-3.04891(r)-249.1148(r)1.87468(1)u)-1.87468(e)2.3505(-4.92359(-3.04891(r)e)2.3505(m)-4.9250d)-1.87468(u)-1.87468(g)-1.87468(a)2.3505(ç).462o)-1.87468(m)-248.542(-258.6.80)-1.87468(a)2.34948(-1.87468(u)-7623917)-3.05095(u)-1.87468(d)-1.85254(i-248.542(-258.6.80r)1.76236(e)2.34948(q)-3.05095(t)-3.04891(i)17.0437(v)18.3505(o)-1.87468(e)-208.404(c)2.3505(o)-1.87468(m)aé03.1742(o)6t)-3.0509aei dade c errompidosprma lnicido
12
esses dados, pode-se concluir que este é um caso típico onde esquemas de proteção desigual
de erros (UEP) podem ser usados com sucesso [19]. Esquemas de proteção desigual de erros
para dados compactados podem ser encontrados na literatura [20–23], onde são comumente
aplicados para proteção contra surtos de erros, sendo alguns desses métodos [21,23] específicos
para proteção desigual contra erros em arquivo compactados com LZSS [6].
O algoritmo LZSS [6] foi desenvolvido por Storer e Syzmanski em 1982 [6], e é uma
variação do LZ77 [5]. O LZSS resolve alguns dos problemas do LZ77, proporcionando um
melhor desempenho. Desse modo, o LZSS é o algoritmo mais utilizado para compressão de
textos, pois tem uma grande eficiência para esse tipo de informação [1,6]. Por isso, o LZSS é a
ferramenta de compressão de dados escolhida neste trabalho.
Nesta dissertação é investigado o impacto de surtos de erros em arquivos de texto compac-
tados usando o algoritmo LZSS. Como já dito anteriormente, o surto de erros pode ser inserido
devido a problemas durante leitura ou gravação de dados, ou a desvanecimento em canais sem
fio. Para uma melhor investigação do impacto de surtos de erros para cada classe do arquivo
compactado, é utilizada a estrutura proposta para os dados após a compressão LZSS por Si-
queira em [23]. A partir desse estudo, é mostrado que algumas classes contribuem mais para
a propagação de erros no processo da descompressão que outras. Baseados nesses resultados é
proposta uma nova estrutura para o dado compactado que visa uma proteção maior nas classes
mais sensíveis com uma redundância particular para cada classe. Esta proteção é implementada
usando códigos Reed-Solomon. Os códigos Reed-Solomon são altamente eficientes na correção
de surtos de erros [16–18], e são tratados no Apêndice B.
Resultados de simulações mostrando a eficiência do esquema proposto, sua comparação
com proteção uniforme (EEP) e com outros esquemas de proteção desigual também são apre-
sentados. As simulações apresentadas nesse trabalho usam os arquivos da base de dadosCalgary
Corpus [24], que é apresentada em detalhes no Apêndice A. O esquema proposto difere-se do
introduzido por Kitakami e Kawasaki em [21] no sentido de que aqui é usada outra estrutura
para o dado compactado e é aplicado o código corretor de erros Reed-Solomon com a possi-
bilidade de diferentes capacidades de correção de erros para cada uma das classes do LZSS.
O esquema proposto em [21] é baseado em um tipo de código de repetição das classes mais
sensíveis. Os códigos Reed-Solomon, mesmo sendo mais exigentes computacionalmente, são
mais eficazes para correção de surtos de erros com uma inserção de redundância adicional muito
menor que os códigos de repetição utilizados em [21].
O esquema proposto pode ser aplicado em casos onde a entrega de textos compactados ou
arquivos de dados com poucos erros seja possível. Nesses casos alguns erros locais poderiam ser
13
aceitáveis, enquanto erros globais (como os causados devido à propagação de erros no processo
de descompressão) seriam inaceitáveis. Exemplos de tais casos são a compressão de grandes
volumes de dados [25], transmissão de dados com acompanhamento remoto [26], e ainda a
transmissão de texto em tempo-real em canais sem fio [27,28].
1.1 Estrutura da Dissertação
Esta dissertação encontra-se organizada da seguinte maneira:
Capítulo 2 - Compressão de Dados
Neste capítulo é apresentada uma visão geral sobre compressão de dados, com foco em
compressão de dados sem perdas. A fim de um melhor entendimento da compressão sem perdas,
14
Neste capítulo revisamos os principais resultados e contribuições deste trabalho.
Apêndice A - Calgary Corpus
Este apêndice discute a base de dados Calgary Corpus. São mostradas suas origens e seus
organizadores. A fim de permitir uma melhor escolha para simulações, são listados cada um
dos arquivos, seus tipos, tamanho em bytes, número de caracteres e número de palavras.
Apêndice B - Códigos Reed-Solomon
Este apêndice apresenta os códigos Reed-Solomon, mostrando suas principais aplicações,
sua estrutura, e seus parâmetros de codificação e capacidade de correção de erros. Além disso
são brevemente comentadas as estruturas do codificador e do decodificador.
15
2 Compressão de Dados
Este capítulo traz uma visão geral sobre compressão de dados, mais especificamente sobre
compressão sem perdas. Na Seção 2.1 é apresentada a definição geral de compressão de dados,
as motivações e alguns dos principais algoritmos. Na Seção 2.2 é apresentado o conceito de
compressão com perdas, suas vantagens e desvantagens. A Seção 2.3 traz as definições da
compressão sem perdas, além de apresentar uma base sobre teoria da informação. Na Seção 2.4
são apresentados alguns dos principais algoritmos de compressão de dados sem perdas, com
uma maior ênfase nos métodos de dicionário adaptativo como os algoritmos do tipo LZ.
2.1 Introdução
A compressão de dados é definida como o processo de codificação de informações digitais
em uma representação menor, da qual a original pode ser reconstituída em momento posterior
[29]. Existem três motivações básicas para usar compressão de dados:
• Eficiência de armazenamento;
• Melhor aproveitamento da largura de banda;
• Redução do tempo de transmissão.
A compressão pode ser feita reduzindo dois tipos de redundância: a redundância estatística,
que ocorre quando é possível representar uma certa mensagem com um número menor de bits;
e a redundância perceptual, a qual consiste na parte da mensagem que tem pouca relevância.
Esta redundância pode ser reduzida devido à falta de sensibilidade dos receptores de informação
como visão e audição [31].
Quando se fala em técnica de compressão ou algoritmo de compressão, refere-se a dois al-
goritmos. Um algoritmo de compressão que através de uma entrada X gera uma representação
X
c
que requer um número menor de bits, e um algoritmo de reconstrução que opera a represen-
16
tação comprimida X
c
para gerar a reconstrução Y [8]. Estas operações são ilustradas na Figura
2.1.
Reed-Solomon coding is a key
component of the compact disc .
It was the first use of strong
error correction coding in a
mass-produced consumer
product, and DAT and DVD use
similar schemes. In the CD, two
layers of Reed-Solomon coding
separated by a 28-way
convolutional interleaver yields
a scheme called Cross-
Interleaved Reed Solomon
Coding ( CIRC).
Original
Reed-Solomon coding is a key
component of the compact disc .
It was the first use of strong
error correction coding in a
mass-produced consumer
product, and DAT and DVD use
similar schemes. In the CD, two
layers of Reed-Solomon coding
separated by a 28-way
convolutional interleaver yields
a scheme called Cross-
Interleaved Reed Solomon
Coding ( CIRC).
Reconstruído
R5 coding 6 a key
component of the compact
disc. first use of strong
error correction coding in
a mass-produced product,
and use similar schemes.
In the CD, two d-Solomon
coding er yields a seaved
Reed Solomon Coding
(CIRC
C
o
m
p
r
e
s
s
ã
o
R
e
c
o
n
s
t
r
u
ç
ã
o
Figura 2.1: Exemplo das operações de compressão e reconstrução [8].
Os esquemas de compressão de dados podem ser divididos em duas grandes classes: i)
esquemas de compressão sem perdas, nos quais Y é sempre idêntico a X e, ii) esquemas de
compressão com perdas, os quais geralmente provêem uma taxa de compressão
1
maior que a
compressão sem perdas, porém nesse caso Y não é exatamente igual a X .
2.2 Compressão com Perdas
Técnicas de compressão com perdas, como o nome diz, envolvem sempre algum tipo de
perda, pois além de eliminarem redundância estatística ainda eliminam redundância perceptual.
Dados que foram compactados usando técnicas de compressão com perdas não podem ser re-
cuperados ou reconstruídos exatamente iguais aos dados originais. Em contrapartida pode-se
obter taxas de compressão muito maiores que nas técnicas sem perdas.
A forma de medir a fidelidade de uma seqüência reconstruída para a original depende de
que tipos de dados estão sendo compactados. Suponha que deve-se comprimir e reconstruir
com um esquema com perdas uma certa imagem. Se a imagem for uma obra de arte ou uma
foto, a melhor forma de medir sua fidelidade é perguntar a um perito que conhece bem a obra
original. Contudo, se a imagem for uma imagem de satélite e tiver que posteriormente ser
1
A taxa de compressão é definida como a relação entre o tamanho dos dados compactados pelo tamanho dos
dados originais.
17
processada por um computador deve-se fazer uma medida de melhor qualidade. Similarmente,
isso também acontece com o áudio e com o vídeo.
As duas medidas mais populares de distorção entre os valores originais x e os reconstruídos
y são a medida de erro quadrático d
2
e a medida de diferença absoluta d. Essas medidas são
dadas respectivamente pelas seguintes equações:
d
2
(x, y) = (x − y)
2
, (2.1)
d(x, y) = |x − y| . (2.2)
Em geral, há uma dificuldade de se examinar a diferença termo a termo. Por isso são
utilizadas medidas de média. A média mais utilizada é o erro quadrático médio σ
2
, que utiliza
uma média dos N termos da comparação. O erro quadrático médio σ
2
é descrito na equação
seguinte:
σ
2
=
1
N
N
n=1
(x
n
− y
n
)
2
. (2.3)
Com essas medidas de distorção, é possível determinar o quanto é tolerável de diferença
entre o original e a reconstrução. Por exemplo, quando armazenamos ou transmitimos voz,
pequenas variações no valor das amostras são toleráveis. Similarmente, quando visualizamos a
reconstrução de uma seqüência de vídeo, o fato de que a reconstrução não é exatamente igual a
original geralmente não é importante, enquanto as diferenças não resultem em falsos detalhes.
Por isso, em aplicações de vídeo geralmente se usa compressão com perdas [8].
2.3 Compressão sem Perdas
Técnicas de compressão sem perdas não envolvem perda de informação, nessas técnicas
acontece apenas a redução ou eliminação da redundância estatística. Se dados foram com-
pactados sem perdas, os dados originais podem ser recuperados totalmente a partir dos dados
compactados. Compressão sem perdas é geralmente usada para aplicações que não toleram
nenhuma diferença entre o dado original e o reconstruído.
Compressão de texto é uma área importante da compressão sem perdas. É muito importante
que o texto reconstruído seja idêntico ao texto original, pois pequenas diferenças podem resultar
em interpretações totalmente diferentes. Considerando as frases "João foi buscar um peixe do
tio" e "João foi buscar um peixe do rio", é possível ver claramente como um pequeno erro pode
18
afetar todo o sentido da mensagem. Nesse tipo de compressão é importante que a integridade
dos dados seja mantida.
Outro exemplo para compressão sem perdas é a sua utilização para imagens médicas. Su-
ponha que uma imagem radiológica tenha sido compactada com um esquema de compressão
com perdas, e que a diferença entre a reconstrução Y e o original X seja visivelmente imper-
ceptível. Caso a imagem reconstruída seja submetida a um processamento computacional, as
diferenças não detectadas visivelmente podem vir a ser detectadas como falsos detalhes que
comprometerão o diagnóstico médico [8].
Para entender a estrutura dos esquemas de compressão sem perdas, é necessário um co-
nhecimento prévio de alguns conceitos matemáticos básicos. Assim, serão introduzidos alguns
conceitos sobre teoria da informação para prover uma base que possibilitará a compreensão dos
esquemas de compressão de dados sem perdas.
2.3.1 Introdução à Teoria da Informação
A área que é atualmente chamada de teoria da informação nasceu em 1948 quando Shannon
definiu o conceito de quantidade de informação [33], o qual segue.
Suponha um evento A, o qual é um conjunto de resultados de algum experimento aleatório.
Se a probabilidade desse evento é baixa, a quantidade de informação associada a ele é alta, se a
probabilidade desse evento é alta, a quantidade de informação associada a ele é baixa [34]. Se
P é a probabilidade de um evento acontecer, então a quantidade de informação i associada é
dada por
i = log
b
1
P
= − log
b
P . (2.4)
Considerando que a unidade utilizada é o bit, então o logaritmo tem base 2. Assim, a capa-
cidade máxima de informação i
max
, em bits, que um símbolo de um alfabeto com n símbolos
distintos transporta é:
i
max
= log
2
n . (2.5)
Caso os símbolos sejam equiprováveis, ou seja P =
1
n
. Neste caso, a capacidade é máxima
e pode ser escrita por
i
max
= log
2
1
P
= − log
2
P . (2.6)
Um sistema com um alfabeto de n símbolos distintos, e que transmite por um certo tempo
N símbolos, é capaz de transmitir uma quantidade de mensagens diferentes nesse intervalo de
19
tempo igual a
A
N
n
= n
N
, (2.7)
onde A
N
n
define uma permutação sem repetição. Se a probabilidade de ocorrência de cada
um dos n símbolos for a mesma, ou seja P =
1
n
, encontra-se a quantidade de informação
transmitida pelos N símbolos I
max
, calculando o logaritmo com base 2;
I
max
= N log
2
n = N log
2
1
P
= −N log
2
P . (2.8)
Seja agora o caso de dois símbolos que tem probabilidades diferentes, e que ocorrem N
P
e N
Q
vezes em cada N símbolos. Agora, P é definido como a probabilidade de ocorrência do
primeiro símbolo e Q é definido como a probabilidade de ocorrência do segundo símbolo, ou
seja P =
N
P
N
e Q =
N
Q
N
. Desse modo, a quantidade de informação máxima transmitida pelos
N símbolos é:
I
max
= −N
P
log
2
P − N
Q
log
2
Q . (2.9)
A informação média H transmitida em cada seqüência de N símbolos é:
H =
I
max
N
= −P log
2
P − Q log
2
Q . (2.10)
Generalizando a equação 2.10 para n símbolos diferentes, cada um com probabilidade P
i
, tem-
se:
H = −
n
i=1
P
i
log
2
P
i
. (2.11)
Essa expressão define a entropia de primeira ordem de uma fonte independente e identicamente
distribuída (i.i.d.), isto é, o número médio de bits necessário para representar cada símbolo do
alfabeto de codificação. Além da entropia é possível ainda calcular a redundância R, que é a
diferença entre a capacidade máxima e a informação média efetivamente transportada:
R = i
max
− H = log
2
n − H . (2.12)
Para exemplificar o cálculo da redundância, pode-se supor o lançamento independente de duas
moedas desequilibradas. Cada um dos quatro símbolos tem uma probabilidade diferente, P
1
=
0, 5625; P
2
= P
3
= 0, 1875 e P
4
= 0, 0625. O cálculo da redundância é feito como segue:
H = −
n
i=1
P
i
log
2
P
i
= 1, 62;
R = i
max
− H = log
2
4 − 1, 62 = 0, 38.
A representação destes símbolos só requer, em média, 1,62 bits para cada um. Na prá-
20
tica, esta redução de 2 para 1,62 bits pode ser conseguida através de códigos de comprimento
variável, com um conhecimento estatístico prévio da fonte.
2.3.2 Teorema da Codificação de Fonte
Um problema importante em comunicações é a eficiência da representação dos dados ge-
rados por uma fonte. O processo em que essa representação é fe
21
De acordo com o teorema, a entropia H, tratada na seção anterior, representa o limite teórico
no comprimento médio das palavras-código
¯
L, ou seja, o limite teórico da compressão. Assim
com
¯
L
min
= H, a equação da eficiência pode ser reescrita como:
η =
H
¯
L
. (2.16)
2.3.3 Modelagem de uma Fonte
Considere a seqüência [1 2 3 2 3 4 5 4 5 6 7 8 9 8 9 10]. Assumindo que esta seqüência seja
gerada por uma fonte independente e identicamente distribuída pode-se estimar a probabilidade
de ocorrência dos símbolos:
P (1) = P (6) = P (7) = P (10) =
1
16
,
P (2) = P (3) = P (4) = P (5) = P (8) = P (9) =
2
16
.
A entropia estimada é 3, 25 bits, o que significa que o melhor esquema para codificar essa
seqüência é um código que usa 3, 25 bits/amostra. Contudo se a seqüência original for alterada
para uma representação mais eficiente, que relaciona a distância entre os vizinhos, tem-se a
seqüência [1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1] que possui entropia de 0, 70 bits, uma entropia
muito menor do que a anterior.
É claro que conhecendo apenas essa seqüência o receptor não seria capaz de reconstruir
a seqüência original. O processo depende do conhecimento da estrutura da seqüência. Esse
conhecimento é chamado de modelo. Nesse caso o modelo para essa fonte é x
n
= x
n−1
+ r
n
,
onde x
n
é o n-ésimo elemento da seqüência original e r
n
é o n-ésimo elemento da seqüência
residual. Esse tipo de modelo é chamado modelo estático porque seus parâmetros não mudam
com n. Um modelo que muda ou adapta com n é chamado de modelo adaptativo [32].
Basicamente, conhecendo a estrutura dos dados é mais fácil tentar reduzir a entropia da
fonte. Por isso modelar corretamente uma fonte de informação é um dos aspectos mais impor-
tantes na compressão de dados sem perdas.
2.4 Algoritmos de Compressão sem Perdas
Alguns algoritmos de compressão sem perdas exploram a redundância estatística R da
fonte, que é a diferença entre a capacidade máxima i
max
e a informação média H efetiva-
mente transportada pelo código. Quando não há um conhecimento estatístico prévio da fonte,
22
são usados algoritmos que podem se adaptar para comprimir os dados da fonte. Existem várias
classes de algoritmos de compressão sem perdas, por exemplo:
• Algoritmos de Huffman;
• Algoritmos Aritméticos;
• Algoritmos Preditivos;
• Algoritmos de Dicionário.
A compressão sem perdas é efetuada mediante a representação dos dados simbólicos por palavras-
códigos que têm comprimentos menores que os símbolos correspondentes que codificam. A
Tabela 2.1 mostra os tipos de codificação de dados em função das características dos dados de
entrada e saída.
Tabela 2.1: Classificação dos tipos de codificação de dados em função das características dos dados de
entrada e saída [29].
Método de Codificação Entrada Saída
Fixo → Variável Um símbolo Número variável de bits
Variável→ Fixo String de símbolos Número fixo de bits
Variável→ Variável String de símbolos Número variável de bits
Os métodos de comprimento fixo para variável foram os primeiros algoritmos de compres-
são desenvolvidos [29]. Os métodos de dicionário adaptativo, que foram desenvolvidos por Ziv
e Lempel em 1977 [5] e 1978 [7] são códigos de comprimento variável para fixo. O algoritmo
publicado em [5] ficou conhecido como LZ77 e o algoritmo publicado em [7] ficou conhecido
como LZ78. Após essas publicações surgiram várias variações para resolver algumas limita-
ções dos dois algoritmos, criando assim dois grupos de algoritmos de compressão de dados que
usam dicionário adaptativo [29,42].
Os métodos LZ77 e LZ78 guardam algumas similaridades e poucas diferenças, como as
que seguem:
• Ambos usam strings em seus dicionários, porém usam diferentes estruturas de dados nos
dicionários;
• O LZ77 inicia com poucos símbolos e se adapta mais rapidamente que o LZ78;
• O LZ78 tem uma maior compressão quando a entrada contém strings longas;
23
• O LZ78 é um método mais simétrico, suas velocidades de compressão e descompressão
são muito próximas. Quando comparado ao LZ77, a compressão do LZ78 é mais rápida
porque não é necessário fazer buscas no buffer; a descompressão é mais lenta pois o
dicionário do LZ78 deve ser constantemente atualizado.
Nesse trabalho o esquema de compressão utilizado é o LZSS, uma variação da família do LZ77.
Esse esquema é utilizado por ser muito eficiente com arquivos de texto [9, 35], sendo este o
foco do trabalho. Esses dois algoritmos serão tratados com maior profundidade nas próximas
subseções.
2.4.1 LZ77
O algoritmo LZ77 é um tipo de método de dicionário adaptativo. Os métodos de compres-
são baseados em dicionário adaptativo são caracterizados principalmente por:
• Não necessitam conhecer a estatística dos dados a comprimir;
• Não usam códigos de comprimento variável;
• Utilizam como entrada seqüência de símbolos de comprimento variável.
No método LZ77, o dicionário é simplesmente uma parte da seqüência previamente codi-
ficada. O codificador examina a seqüência de entrada através de uma janela deslizante como
visto na Figura 2.2 [8]. A janela consiste em duas partes, um buffer de busca, ou dicionário, que
contém uma parte da seqüência recentemente codificada, e um look-ahead buffer que contém
a próxima parte da seqüência a ser codificada. Na Figura 2.2, o buffer de busca contém oito
símbolos, enquanto o look-ahead buffer contém sete símbolos.
a x a b p xa a f a b ap p ax p p p a x
Ponteiro
Buffer de busca
(Dicionário)
Look- ahead Buffer
Figura 2.2: Exemplo de uma janela deslizante do codificador LZ77 [8].
Para codificar a seqüência no look-ahead buffer, o codificador move o ponteiro de busca
para trás através do buffer de busca até encontrar o primeiro símbolo do look-ahead buffer.
A codificação é feita utilizando a tripla (o
i
, m
i
, c
i
), onde (o
i
) é chamado offset e é a distância
do ponteiro até o look-ahead buffer. O match (m
i
) é o número de símbolos consecutivos no
24
dicionário que são idênticos aos símbolos consecutivos no look-ahead buffer, iniciando com
o primeiro símbolo referenciado no ponteiro, ou seja, o match especifica o comprimento da
seqüência de símbolos repetidos. O LZ77 ainda usa um terceiro elemento que é o primeiro
símbolo do look-ahead buffer subseqüente à frase ao offset e ao match. Por exemplo, na Figura
2.2 o ponteiro está apontando para o início da seqüência de match. O offset nesse caso é 7, o
comprimento de match é 4 e o símbolo no look-ahead buffer que segue a frase é p.
A motivação para enviar o terceiro elemento da tripla, ou token, é o cuidado para o caso
onde não é encontrada uma seqüência no look-ahead buffer. Nesse caso os valores do offset e
do match são iguais a 0, e o terceiro valor é o código do próprio símbolo. Para exemplificar
o método LZ77, pode-se supor a seguinte seqüência a ser codificada: acaacabcababac. Con-
forme a Figura 2.3, a janela deslizante tem 14 caracteres, o dicionário possui 10 caracteres e os
dados entram na janela da direita para a esquerda.
dicionário look-ahead buffer
a c a a ←− (0,0,a)
a c a a c (0,0,c)
a c a a c a (2,1,a)
a c a a c a b c (3,2,b)
a c a a c a b c a b a ...
a c a a c a b c a b a b a c (2,3,c)
Figura 2.3: Exemplo de codificação usando o método LZ77.
Como mostrado na Figura 2.3, na primeira linha os dados de entrada estão apenas no look-
ahead buffer, não existe nenhum dado no dicionário. Assim, a palavra-código tem os dois
primeiros componentes zerados e o terceiro componente é o símbolo subseqüente o look-ahead
buffer (a). Na segunda linha apesar de existir um símbolo no dicionário, não existe uma seqüên-
cia grande o suficiente para que seja representada com um símbolo de match e um de offset,
desse modo os dois primeiros elementos da palavra-código são zerados novamente e o símbolo
que segue o look-ahead buffer é adicionado na terceira posição.
A partir da terceira linha pode-se ver que acontece efetivamente o processo de compressão.
Existe no dicionário a seqüência a c que é igual a uma seqüência existente no look-ahead buffer,
o offset agora tem o valor de 2, pois é a distância da posição do ponteiro até o look-ahead buffer,
o match tem o valor de 1, que é a distância da posição do ponteiro até o fim da seqüência, ou
seja o seu comprimento. O terceiro símbolo é o caractere que segue o look-ahead buffer (a).
O processo de codificação segue até que toda a seqüência seja codificada em um conjunto de
palavras-código.
25
Como pode ser visto, o LZ77 é um esquema adaptativo muito simples que não requer
um conhecimento prévio da fonte. O LZ77 e suas variações são usados em vários aplicativos
de compressão como PKZip, Zip, LHarc, PNG, gzip e ARJ. Esse algoritmo apresenta alguns
problemas:
• Aumentandoo tamanho do dicionárioaumenta a probabilidade de se encontrarem seqüên-
cias. Porém com o aumento da eficiência de compressão, o tempo de processamento
também aumenta;
• Aumentando o tamanho do look-ahead buffer aumenta a probabilidade de formar seqüên-
cias mais longas. Nesse caso o aumento da eficiência de compressão também aumenta o
tempo de processamento;
• As palavras código com três componentes introduzem ineficiência, pois o caractere final
poderia ser incluído na seqüência seguinte.
O último problema ocorre quando não são encontradas seqüências no dicionário. Quando esse
é o caso, a compressão ainda tem que usar os três componentes da palavra-código para codifi-
car um único caractere. Para exemplificar o custo disso, pode-se supor codificar um caractere
simples de 8 bits. Suponha também 12 bits para representar a posição na janela, o offset, e 4
bits para representar o tamanho da frase, o match. Usando esse sistema, com a tripla (0,0,c)
seriam usados 24 bits para codificar um simples símbolo de 8 bits. Esse é um preço muito
alto a se pagar e também é a grande motivação para o desenvolvimento de muitas variações do
LZ77 [34].
2.4.2 LZSS
O método LZSS [6], é uma variação do LZ77 que procura evitar alguns dos gargalos e
problemas no LZ77 original. O LZSS também é usado por vários aplicativos de compressão
como PKZip, Zip, gzip. Ele faz duas principais mudanças no modo que o algoritmo trabalha. A
primeira é no modo que a janela deslizante é mantida. No LZ77, as frases que entram na janela
deslizante são armazenadas como um simples bloco de texto contínuo. O LZSS ainda armazena
o texto em janelas contínuas, porém ele cria uma estrutura de dados adicional que melhora a
organização da frase.
O LZSS adiciona à frase uma estrutura em árvore de busca binária. Por classificação as
frases são introduzidas na árvore, o tempo requerido para procurar a mais longa seqüência na
árvore é proporcional ao produto do tamanho da janela e do comprimento dessa seqüência.
26
Como a árvore é binária, o tempo corresponde ao logaritmo na base 2 desse produto. As econo-
mias de processamento criadas usando árvore não somente tornam o algoritmo mais eficiente
pelo lado da compressão, como também encoraja a aumentar o tamanho da janela deslizante.
Como exemplo, dobrando o tamanho da janela deslizante, o tempo de compressão tem um
crescimento menor do que teria no LZ77.
A segunda alteração encontra uma saída para reduzir o problema com a tripla do algoritmo
de compressão do LZ77 citado na Seção 2.4.1. Relembrando que o LZ77 gera na saída uma
tripla que consiste em um offset, um match e uma caractere que segue a frase. Quando o
algoritmo não encontra seqüências, não é mais enviada a tripla com os dois primeiros elementos
zerados. O LZSS usa um bit simples como prefixo. Quando a saída é apenas um caractere, o
prefixo chamado de flag tem o valor de 0, assim a saída é apenas o flag (f
i
) e o caractere (c
i
).
Quando existe uma seqüência o flag (f
i
) assume o valor 1, que vem acompanhado do offset (o
i
)
e do match (m
i
). A Equação 2.17 define a composição da palavra-código C
i
, que é a i-ésima
palavra-código gerada pelo codificador, no método LZSS [34]:
C
i
=
(f
i
, o
i
, m
i
) para f
i
= 1
(f
i
, c
i
) para f
i
= 0
. (2.17)
Para melhor entender as diferenças do LZSS para o LZ77, o exemplo da Figura 2.4 utiliza
os mesmos dados de entrada da subseção anterior.
dicionário look-ahead buffer
a c a a ←− (0,a)
a c a a c (0,c)
a c a a c a (0,a)
a c a a c a b (1,3,3)
a c a a c a b c a b a ...
a c a a c a b c a b a b a c (0,b)
Figura 2.4: Exemplo de codificação usando o método LZSS.
Como mostrado na Figura 2.4, na primeira linha os dados de entrada estão apenas no look-
ahead buffer, não existe nenhum dado no dicionário, assim o LZSS ajusta o valor do prefixo
flag para 0 e a palavra-código é formada apenas pelo flag e pelo caractere. Na segunda e na
terceira linha, apesar de existir símbolos no dicionário, não existe uma seqüência que justifique
a codificação com offset e match, dessa forma acontece como na primeira linha e a palavra-
código é formada pelo flag e pelo caractere.
Na quarta linha, existe no dicionário a seqüência a c a que se repete no look-ahead buffer.
27
Se o padrão for de 8 bits para representar um caractere, 12 bits para representar um offset e 4
bits para representar um match, a codificação nesse caso é compensatória. Então, o algoritmo
escolhe por representar essa seqüência com um prefixo flag em 1, com um offset de 3 e um
match de 3. A codificação segue até que todos os dados sejam codificados em conjuntos de
palavras-código dos dois tipos.
2.5 Comentários Finais
Neste capítulo foram apresentados os conceitos básicos sobre compressão de dados, suas
principais características e motivações. Além disso, foi feita uma breve introdução à teoria da
informação. Foram mostrados os esquemas de compressão de dados com perdas e sem perdas
aprofundando nos esquemas do tipo LZ, mais especificamente os algoritmos da família LZ77,
os quais são o foco desse trabalho.
28
3 Métodos de Proteção Desigual de
Erros para LZSS
Este capítulo aborda esquemas de proteção desigual de erros, em especial esquemas para
arquivos compactados com LZSS. Além disso, faz uma revisão da literatura recente sobre o
tema. Na seção 3.1 é feita uma descrição de um surto de erro e uma análise do seu impacto
em arquivos compactados, com uma ênfase em arquivos compactados com LZSS. Na seção
3.2 é tratado o método de proteção desigual para dados compactados com LZSS proposto por
Kitakami e Kawasaki [21], suas principais características, vantagens e desvantagens. Na seção
3.3 é apresentado o método de proteção desigual para dados compactados com LZSS proposto
por Siqueira [23], também suas principais características, vantagens e desvantagens.
3.1 Introdução
Durante o armazenamento ou transmissão de dados podem ocorrer vários tipos de padrões
de erros, sendo os erros aleatórios e os surtos de erros os tipos mais comuns [36]. Como mostra
a Figura 3.1, os erros aleatórios, como o nome já diz, ocorrem aleatoriamente no tempo ou
espaço. Esses erros podem ocorrer em todas as posições de bit de uma palavra com probabili-
dade quase uniforme. O erro aleatório é um tipo de erro imprevisível e tipicamente causado por
ruído branco. Também na Figura 3.1 é mostrado o padrão de erros em surto, que ocorrem con-
centrados em algumas regiões causando b bits consecutivos errados. Os surtos de erros podem
ocorrer, por exemplo, em canais sem fio com desvanecimento profundo [14, 15], ou por erros
em memórias de disco ou memória de semicondutores [16,17,36]. Uma proteção eficiente para
surto de m
29
Dados
recebidos
Ruídos externos e falhas que
ocorrem aleatoriamente
Erros Aleatórios
Erros em Surto
Defeitos
Gravação
contínua
b-Bits Surto de Erros
Dados
recebidos
Figura 3.1: Exemplo dos casos de erros aleatórios e surto de erros [36].
recuperados pelo código de canal podem causar uma propagação de erros em todo o restante do
arquivo. Como visto no capítulo anterior, osdados compactados tem sua representação alterada.
Assim, algumas classes de símbolos possuem uma importância ou um valor muito maior que
outras. Além disso, alguns símbolos interferem na ordem e no tamanho do arquivo, o que traz
grandes conseqüências para o processo de reconstrução do arquivo compactado na presença
de surtos de erros não recuperados. A fim de tornar claro o impacto dos surtos de erros nos
arquivos compactados com LZSS, a seguir serão feitas análises de simulações com arquivos
afetados por surtos de erros ao longo de sua estrutura.
3.1.1 Impacto dos Surtos de Erros no Processo de Descompressão
Durante o processo de descompressão do LZSS, o flag indica se a próxima informação é
um caractere não-codificado ou uma palavra-código, como já tratado no capítulo anterior. Se
o flag indicar um caractere não-codificado, o algoritmo simplesmente copia o próprio caractere
na seqüência decodificada. Se o flag indicar uma palavra-código, o algoritmo de descompressão
copia o símbolo indicado pelo ponteiro (offset) e todos os símbolos que seguem referenciados
pelo comprimento do match. Observando essas afirmações, pode-se concluir que se erros são
introduzidos durante o armazenamento ou transmissão do arquivo compactado, seus efeitos
no processo de descompressão podem ser muito grandes. Esses efeitos dependem do tipo de
informação que será afetada: bits de flag, bits de match, bits de offset ou bits de caractere. Por
exemplo, se os bits de matchsão afetados pelo surto de erros, o tamanho do arquivo reconstruído
será alterado em relação ao original. Porém se os bits de caractere são afetados, ocorrem apenas
30
mudanças no local do erro, sem nenhuma propagação de erros.
Para avaliar o impacto de um surto de erros ao longo do arquivo compactado com o al-
goritmo LZSS, foram feitos testes com arquivos de texto de uma base de dados comum, o
Calgary Corpus [24] mostrado no Apêndice A. Arquivos da mesma base de dados foram uti-
lizados em [20,21,23,37] para analisar esquemas de proteção desigual de erros para variantes
Lempel-Ziv; alguns desses métodos serão tratados nas próximas seções. A Tabela 3.1 mostra os
parâmetros resultantes da compressão do arquivo ’paper4.txt’, o qual tem um tamanho original
de 13286 bytes.
Tabela 3.1: Parâmetros do arquivo compactado a partir do arquivo ’paper4.txt’.
Parâmetros
Tamanho do arquivo (bytes) 7164
Tamanho do arquivo (bits) 57312
Taxa de Compressão 46,1%
Número de bits de flag 3796
Número de bits de caractere 14912
Número de bits de offset 30880
Número de bits de match 7724
O algoritmo de compressão LZSS foi implementado da maneira original [6], com os parâ-
metros definidos para compressão máxima: 8 bits para o símbolo de caractere não-codificado,
1 bit para o símbolo de flag, 16 bits para os símbolos de offset e 4 bits para os símbolos de
match. Para atingir a compressão máxima foram feitos testes com parâmetro match. A Figura
3.2 mostra a taxa de compressão conseguida em configurações com diferentes números de bits
de match.
A fim de demonstrar o impacto de um surto de erros no processo de descompressão, foi
utilizado um surto de erros de 48 bits, como em [20,23], em diferentes posições do arquivo
compactado. O surto de erros é aplicado para intervalos consecutivos de 48 bits, semelhante
a regiões deficientes em um dispositivo de armazenamento de dados [12, 16, 17,36], ou a um
canal sem fio com grande desvanecimento [14,15]. Na Figura 3.3 é mostrada a taxa de erro de
símbolos (SER) no arquivo reconstruído como uma função da posição do surto de erros. A SER
é definida como a distância de Levenshtein pelo número de símbolos na mensagem transmi-
tida. A distância de Levenshtein é o número mínimo de inserções, eliminações e substituições
de símbolos requerido para transformar a mensagem decodificada na mensagem original trans-
mitida [38]. De acordo com [39], a distância de Levenshtein é uma medida mais apropriada
que uma simples comparação símbolo a símbolo, a qual não detectaria o efeito de possíveis
inserções e eliminações.
31
2 4 6 8 10 12 14 16
50
55
60
65
70
75
80
Taxa de Compressão (%)
Número de Bits de Match
Figura 3.2: Relação entre a taxa de compressão e número de bits de match para o arquivo ’paper4.txt’.
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
32
Na Figura 3.3 pode-se ver que a propagação de erros é mais grave quando o surto de erros
está localizado no início do arquivo compactado. A SER média nesse cenário é 36, 82%.
Uma forma simples para combater a propagação dos erros é aplicar um código corretor de
erros em todo arquivo compactado que garanta a proteção para um surto de erros com compri-
mento l. Porém, dessa maneira dois objetivos serão contrapostos no processo. A codificação de
fonte ou compressão de dados tenta descorrelacionar o máximo possível a seqüência de entrada,
por remoção de redundância adicional; enquanto a codificação de canal introduz correlação aos
dados, por adição de redundância. Assim, com essa estrutura, a redundância adicional aplicada
ao arquivo compactado tornará inviável esse método, pois a taxa de compressão seria muito
reduzida.
Para evitar a propagação sem comprometer a taxa de compressão, foram desenvolvidos
vários esquemas de controle de erros específicos para dados compactados. Esses esquemas são
chamados esquemas de proteção desigual, devido à sua característica de aplicar uma proteção
contra erros nas partes mais sensíveis a propagação de erros do arquivo. Com esse arranjo
é possível conseguir que os dados sejam mais resistentes a erros sem grandes perdas em sua
compressão.
A aplicação de esquemas de proteção desigual de erros para técnicas de compressão pode
ser encontrada na literatura. Por exemplo, em [40] é apresentado um método de recuperação
de erros para dados compactados com códigos aritméticos, em [22] é introduzido um método
para códigos Huffman. Em [20] um esquema de proteção desigual de erros para as variantes
do Lempel-Ziv, LZ77 e LZW, é apresentado, onde o esquema de proteção desigual aumenta
consideravelmente a robustez do algoritmo de compressão para surtos de erros. Em [37] um
esquema para LZ77 é apresentado, sendo capaz de corrigir erros substituindo a redundância
residual existente no LZ77 pela redundância de um código corretor. Recentemente, em [21]
e [23] outros esquemas de proteção desigual para LZSS [6] foram aplicados com sucesso para
correção de erros. Nas próximas seções serão discutidos estes dois esquemas [21,23].
3.2 Esquema Proposto por Kitakami e Kawasaki
Em [21], Kitakami e Kawasaki propuseram um método de proteção de erros baseado na
repetição das partes mais sensíveis dos dados compactados nos dados LZSS, os flags e os
matches. O método proposto divide os dados, já compactados com LZSS, em vários blocos,
cada um contendo B palavras-código. Assim, o j-ésimo bloco inclui as B palavras-código
C
(j−1)B
, C
(j−1)B+1
, ..., C
jB−1
. O método coloca os flags e os matches no início do bloco. Para
33
detectar os erros com maior facilidade, os matches são codificados por codificação unária [1]
e uma seqüência de sincronização é alocada depois da parte que contém os flags e os matches.
Uma cópia dessa parte, os offsets e os caracteres são alocados depois da seqüência de sincroni-
zação. Os procedimentos de codificação e decodificação são descritos nas subseções seguintes.
3.2.1 Procedimento de Codificação
O procedimento de codificação pode ser descrito em três passos básicos como segue:
1. Os dados são compactados através do LZSS;
2. Os matches inclusos nas palavras-código LZSS são recodificados com codificação unária;
3. O conjunto de palavras-código LZSS é dividido em blocos, contendo B palavras-código.
O j-ésimo bloco é organizado pelo seguinte procedimento:
• Sejam F
j
, M
j
, O
j
e A
j
, todos os flags, matches, offsets e caracteres respectivamente
contidos nas palavras-código C
(j−1)B
, C
(j−1)B+1
, ..., C
jB−1
. Seja S a seqüência de
sincronização.
• A saída gerada para o bloco em questão é dada por (F
j
M
j
SF
j
M
j
O
j
A
j
). Ou seja, a
seqüência F
j
M
j
é repetida.
A Figura 3.4 ilustra um exemplo do procedimento de codificação para B = 5. Nesse exem-
plo um bloco contém cinco palavras-código LZSS, (0,"a"), (0,"b"), (1,6,2), (1,5,3) e (1,1,3); e
a seqüência de sincronização é "11011".
Expressão binária
(os matches são codifidados
na forma unária)
flags matches
flags
(cópia)
matches
(cópia)
offsets
caracteres
seqüência de
sincronização
Palavras-código LZSS
Os elementos são coletados
para formar a palavra-código
do método proposto
Figura 3.4: Exemplo do procedimento de codificação do método proposto por Kitakami e Kawasaki
[21].
34
3.2.2 Procedimento de Decodificação
No procedimento de decodificação a estrutura (F
j
M
j
SF
j
M
j
O
j
A
j
) é utilizada para a re-
cuperação dos dados transmitidos. Com a repetição dos flags e dos matches, e a alocação da
seqüência de sincronização, é possível recuperar os dados sem erros, até um certo limite que
será discutido posteriormente. A decodificação do j-ésimo bloco é descrita através dos passos
seguintes:
1. Os primeiros B bits do bloco recebido são retirados e considerados como F
′
j
.
2. As w(F
′
j
) palavras com codificação unária do início do restante do bloco são retiradas,
onde w(x) corresponde ao peso de Hammingde x. As palavras em código unário retiradas
do bloco são decodificadas e são consideradas como os matches no bloco de palavras-
código LZSS;
3. Se o início do restante do bloco for a seqüência de sincronização, ela é retirada junto com
os B bits + w(F
′
j
) palavras-código, que são as cópias dos flags e dos matches. Após isso
o algoritmo vai para o passo 6;
4. Se a seqüência de sincronização não for encontrada no passo 3, é feita uma busca no
restante do bloco. Caso encontrada, a seqüência de sincronização é retirada, e os bits
seguintes são considerados os flags e os matches da mesma maneira dos passos 1 e 2, e
vai para o passo 6;
5. Se a seqüência de sincronização também não for encontrada no passo 4 o algoritmo exe-
cuta o seguinte: Procura no restante do bloco obtido no passo 1 por uma parte igual à
primeira metade dos matches obtidos no passo 2. Se essa parte for encontrada, retira os
bits à frente da parte encontrada e lê os matches da mesma forma do passo 2, e usa os
flags obtidos no passo 1. Após esse procedimento vai para o passo 6. Se essa parte não
for encontrada, os dados são considerados irrecuperáveis e o procedimento termina.
6. Retira os offsets e os caracteres do restante do bloco, e executa o procedimento de des-
compressão por LZSS.
Analisando o procedimento de decodificação, o passo 4 corresponde a proteção para quando
o primeiro conjunto de flags e matches contém erros. O passo 5 é para o caso em que a parte
que inclui o primeiro conjunto de matches, a seqüência de sincronização e o segundo conjunto
de flags contém erros. A Figura 3.5 mostra um exemplo do procedimento de decodificação,
onde a seqüência de sincronização e o primeiro conjunto de matches estão errados.
35
flags 1 matches 2
matches 1
seq.
sinc.
flags 2 offsets
matches
bits errados usados na descompressão
Figura 3.5: Exemplo do procedimento de decodificação do método proposto por Kitakami e Kawasaki
[21].
3.2.3 Avaliações sobre o método
O esquema proposto por Kitakami e Kawasaki [21] pode recuperar surtos de erros ocor-
ridos na parte do bloco que inclui os flags, os matches e a seqüência de sincronização. O
máximo comprimento de surto de erros que o esquema pode recuperar é definido por [21]:
min(len(F
i
), len(M
i
), len(S)), onde len(x) denota o número de bits de x.
Tabela 3.2: Comparação entre taxa de compressão do método proposto por Kitakami e Kawasaki, e as
taxas de compressão do LZSS [6] e do LZ77 [5].
Nome do Arquivo obj1 paper1 progc progp
Compressão LZSS 57,6% 44,9% 42,6% 29,3%
Kitakami e Kawasaki 65,4% 52,7% 50,5% 37,1%
Em [21] o esquema foi avaliado por simulações computacionais utilizando arquivos da
base Calgary Corpus [24] e com os seguintes parâmetros: i) Tamanho do bloco com B = 200
palavras-código; ii) Tamanho da seqüência de sincronização com 13 bits. A Tabela 3.2 mostra
a comparação da taxa de compressão do método proposto com a taxa de compressão do LZSS
para alguns arquivos da base Calgary Corpus.
Durante o desenvolvimento desse trabalho foram feitas algumas simulações para o método
em questão. A Figura 3.6 mostra o impacto de um surto de erros de 20 bits no processo de
descompressão, em termos da taxa de erros de símbolos (SER) e como uma função da posição
do surto de erros para o arquivo ’paper4.txt’, considerando o esquema proposto em [21] para o
arquivo compactado. Nota-se que a média de erros nesse caso é de apenas 0, 20%.
Esse método, apesar de garantir uma proteção eficaz contra surtos de erros, apresenta algu-
mas desvantagens:
• A redundância é inserida como a repetição dos bits de flag e dos bits de match, isso cor-
36
0 20 40 60 80 100
0
0.02
0.04
0.06
0.08
0.1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 3.6: Impacto de um surto de erros de 20 bits no processo de descompressão, em termos da SER
e como uma função da posição do surto de erros para o arquivo ’paper4.txt’, considerando o esquema
proposto em [21] para o arquivo compactado.
responde a um código de repetição de taxa
1
2
, o que degrada muito a taxa de compressão
do LZSS;
• A definição da seqüência de sincronização é muito difícil, pois essa seqüência não deve
se repetir em nenhum momento no resto da estrutura do arquivo;
• A codificação unária dos matches aumenta o tamanho dos arquivos, o que é mais um fator
para degradação da taxa de compressão;
• A capacidade de correção é dada por min(len(F
i
), len(M
i
), len(S)), ou seja, para au-
mentar a capacidade de correção deve-se aumentar o tamanho da seqüência de sincroni-
zação, o que colaboraria também com a degradação da taxa de compressão;
• Se o surto de erro degradar uma parte da primeira metade do primeiro conjunto dos mat-
ches e a alguma parte da seqüência de sincronização, não há possibilidade de recuperação
do arquivo;
• Para que o método funcione de uma maneira ótima, os parâmetros de compressão do
LZSS precisam ser otimizados. Assim, em [21] os autores comparam o melhor caso para
37
o seu método com o caso do LZSS sem otimização. Isto maquia o impacto da redundância
adicional.
3.3 Esquema Proposto por Siqueira
Em [23], Siqueira propôs um esquema de proteção desigual baseado na adição de redun-
dância apenas na classe dos flags, através do uso de códigos Reed-Solomon. A classe dos flags
recebe a redundância por ser, considerada em [23], a classe mais sensível à propagação de erros.
3.3.1 Método de Proteção Desigual
Como já discutido anteriormente, através de análises de propagação de erros, em [23]
conclui-se que a classe mais sensível é a classe dos flags. A partir desse ponto, foi criada
uma nova estrutura para o arquivo compactado. A estrutura usual dos dados compactados com
LZSS é mostrada na Figura 3.7, onde f denota os símbolos de flag, c denota os símbolos de ca-
ractere, m denota os símbolos de match, e o denota os símbolos de offset. A Figura 3.8 mostra
a estrutura proposta em [23], onde os bits foram separados em quatro classes, seguindo uma
nova estrutura, onde F denota o conjunto de todos os bits de flag, C denota o conjunto de todos
os bits de caractere, M denota o conjunto de todos os bits de match, e O denota o conjunto de
todos os bits de offset. A razão dessa estrutura é a ter os bits da classe dos flags juntos para
adicionar redundância com o código Reed-Solomon.
f c f c
....
f o m f c f o m
....
Figura 3.7: Estrutura dos dados compactados pelo algoritmo LZSS.
F O M C
Figura 3.8: Estrutura nova proposta em [23].
Depois de organizados nesta estrutura, os flags são codificados com um código Reed-
Solomon (255,247), que provê correção para um surto de até 32 bits. Para testar, são inseridos
surtos de erros de 48 bits no arquivo compactado, com os flags protegidos.
38
3.3.2 Avaliações
Para avaliar o seu esquema, o autor faz uma comparação entre uma proteção em todo o
arquivo compactado, sem alterar sua estrutura, e o seu método. Essas simulações foram feitas
utilizando o arquivo ’paper4.txt’ [24]. Em ambas simulações o código utilizado é o mesmo.
A partir dos resultados o autor conclui que seu esquema é mais eficiente que uma proteção
uniforme em todo arquivo, conforme a Tabela 3.3.
Tabela 3.3: Comparação entre o esquema proposto por Siqueira [23] e uma proteção uniforme usando
códigos Reed-Solomon.
Método SER
Proteção Uniforme 45,28%
Método Siqueira 7,19%
Apesar da relevância para a literatura da área, o trabalho de Siqueira deixa muitas questões
em aberto:
• A proteção desigual aplicada à nova estrutura do arquivo não sana toda a propagação de
erros. Os bits de match não são protegidos, e ainda, o autor considera que a propagação
de erros nessa classe é menor que na classe dos offsets;
• A medida de erro utilizada pelo autor não é uma medida ideal. Uma média símbolo a
símbolo não considera o efeito de possíveis inserções ou eliminações de símbolos;
• Os resultados obtidos no trabalho se restringem a simulações feitas com apenas um ar-
quivo. Para melhor comprovação dos resultados deveriam ser feitas simulações com um
número maior de arquivos;
• Apesar de conseguir manter uma taxa de compressão bem próxima da taxa do LZSS, o
método não garante proteção total à propagação de erros.
3.4 Comentários Finais
Neste capítulo foram discutidos métodos de proteção desigual para arquivos compactados.
Através de uma revisão bibliográfica foi possível constatar a relevância e a atualidade do tema.
Em uma análise mais detalhada, foram mostrados dois métodos de proteção desigual específicos
para dados compactados com LZSS conhecidos na literatura.
39
4 Esquema de Proteção Desigual
Usando Códigos Reed-Solomon
Este capítulo apresenta uma proposta de um esquema de proteção desigual de erros para da-
dos compactados com LZSS usando códigos Reed-Solomon. Na seção 4.1 é feita uma análise
através de simulações da propagação de erros em cada uma das classes de símbolos do arquivo
compactado com LZSS. Na seção 4.2 é apresentado o esquema proposto para proteção desi-
gual de erros, além de uma nova estrutura para os arquivos compactados a qual engloba uma
redundância adicional. Na seção 4.3 são apresentados os resultados das simulações feitas com
o esquema proposto utilizando diferentes configurações. Nesta seção ainda são apresentadas
comparações com um outro método [21] e tabelas com resultados de simulações com vários
arquivos diferentes.
4.1 Introdução
Como mostrado no capítulo anterior, a estrutura proposta por Siqueira em [23] permite uma
análise melhor de cada uma das classes dos dados compactados com LZSS. Na nova estrutura
os bits são organizados em quatro classes diferentes, como mostrado na Figura 3.8 no capítulo
3, onde F, C, M e O correspondem aos bits de flag, de caractere, de match e aos de offset,
respectivamente.
Após simulações com os dados compactados e organizados na estrutura da Figura 3.8,
conclui-se que essa estrutura é consideravelmente menos sensível a surtos de erros que a es-
trutura original do LZSS, mostrada na Figura 3.7 no capítulo 3. Na Figura 4.1, tem-se a taxa
de erro de símbolo (SER) no arquivo descompactado em função da posição do surto de erros,
considerando a nova estrutura do arquivo compactado. A partir dessa figura, pode-se notar que
a propagação de erros é muito maior quando os surtos de erros são aplicados nas posições que
têm uma grande quantidade de flags e matches (primeiro e segundo picos, respectivamente).
Considerando essa nova estrutura para o arquivo compactado, a SER média depois da descom-
40
pressão é de 10, 68%. Um decréscimo considerável quando comparado com o caso da Figura
3.3 vista no capítulo 3, a qual considera a estrutura regular do arquivo compactado com LZSS
como visto na Figura 3.7, onde a SER média é de é 36, 82%.
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 4.1: Impacto de um surto de erros de 48 bits no processo de descompressão, em termos da SER e
como uma função da posição do surto de erros para o arquivo ’paper4.txt’, considerando a nova estrutura
do arquivo compactado.
Utilizando a estrutura proposta na Figura 3.8, pode-se analisar o efeito de um surto de erros
para cada classe separadamente. A Figura 4.2 mostra o efeito do surto de erros no processo de
descompressão, quando o surto de erros de 48 bits é aplicado em cada uma das quatro classes.
Analisando a figura, onde as curvas dos caracteres e dos offsets são muito coincidentes, pode-se
ver que as classes mais sensíveis são os flags e os matches. Certamente, se um bit de flag é
corrompido, então um caractere não-codificado é substituído por uma palavra-código, ou vice-
versa. Como resultado, os bits de offset apontarão para uma posição inicial errada, e os bits
de match indicarão um comprimento da seqüência errado para ser usado no dicionário. Assim,
erros nos bits de flags corromperão o tamanho do arquivo, rendendo um arquivo descompactado
com um tamanho diferente do arquivo original. Um efeito similar ocorre para o caso dos bits
de match, um erro nos matches rende um comprimento da seqüência no dicionário errado e
também causa erros graves no arquivo descompactado. Em contra partida, os erros nos bits de
offset e nos bits de caractere causam um impacto muito pequeno no processo de descompressão,
tendo impacto apenas na região do surto.
41
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
42
uniforme de erros (EEP) a redundância adicional é inserida no fim do arquivo compactado.
F
F
O
O
M
M
C
C
~
~
~ ~
Figura 4.3: Estrutura geral do arquivo compactado depois da aplicação da proteção desigual.
Uma desvantagem deste esquema UEP é que a estrutura proposta nas Figuras 3.8 e 4.3
requer que os dados sejam buferizados antes do armazenamento ou transmissão, o que não é
requerido pelo algoritmo LZSS original [6, 9, 35]. Contudo, a buferização é necessária tam-
bém para o caso de proteção uniforme de erros onde códigos de bloco como os códigos Reed-
Solomon são usados, pois, como já dito anteriormente, a redundância é inserida no fim do
arquivo compactado.
4.3 Resultados de Simulações
Nesta seção é investigado o desempenho do esquema de proteção desigual de erros pro-
posto, e comparado com o caso de proteção uniforme, considerando o mesmo surto de erros de
48 bits e o arquivo de texto ’paper4.txt’ como nas seções anteriores, a menos que indicado de
outra maneira. Os códigos Reed-Solomon usados neste método são definidos sobre GF(256) e
representados pela tripla (n, k, t), onde n é o número de símbolos de saída, k é o número de
símbolos de entrada, e t é a capacidade de correção do código.
Como comparação, foi considerado o caso de uma proteção uniforme de erros utilizando a
estrutura original da Figura 3.7, onde o código Reed-Solomon (255,251,2) é usado sobre todos
os bits do arquivo compactado. Na Figura 4.4 pode-se ver que o esquema é muito ineficiente,
pois a SER média é de 32, 93%, mesmo havendo um acréscimo de 1, 56% no arquivo com-
pactado devido à redundância adicional. O mau desempenho é devido ao fato de que as classes
mais sensíveis, os flags e os matches, não são bem protegidos. Um erro nos flags ou nos matches
provoca propagação de erros que corrompem o tamanho do arquivo descompactado.
O aumento da capacidade de correção de erros do código Reed-Solomon usado no esquema
de proteção uniforme para até t = 5 não rende uma melhora significativa de desempenho, pois
o surto de erros é mais longo que a capacidade de correção de erros do código Reed-Solomon,
como mostra a Figura 4.5. A SER média é ainda em torno de 31, 00%. A SER média somente
decresce em um esquema de proteção uniforme quando t = 6, onde seu valor é zero. O código
Reed-Solomon é definido sobre GF(256), isto significa que o código seria capaz de corrigir
43
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 4.4: Efeito do surto de erros no processo de descompressão, em termos da SER em função da
posição do surto de erros, para o arquivo ’paper4.txt’ usando proteção uniforme de erros com t = 2.
qualquer surto simples de até 6 × 8 = 48 bits, porém isto gera um custo de 4, 71% de acréscimo
no tamanho do arquivo. Um comportamento similar ocorre quando é considerado um esquema
de proteção uniforme com a estrutura de arquivo proposta na Figura 3.8. Somente com essa
diferença a SER média no arquivo descompactado é em torno de 10.00% para t = 1 até t = 5.
A SER média reduzida é devido ao fato de que a nova estrutura proposta na Figura 3.8 é menos
sensível à propagação de erros que a estrutura original.
O esquema de proteção desigual de erros proposto neste trabalho usa muito menos redun-
dância e é capaz de conseguir um desempenho quase livre de erros. Este esquema é baseado na
estrutura vista na Figura 4.3. Porém, inicialmente adicionamos proteção apenas para a classe
dos bits de flag. Foi utilizado o código Reed-Solomon (255,243,6), tal que t
f
= 6. Na Figura
4.6 pode-se ver que essa redundância adicional produz uma grande redução no efeito dos surtos
de erros no processo de descompressão. A SER média é reduzida para 7, 17%, com o preço de
um acréscimo de apenas 0, 31% no tamanho do arquivo compactado, pois os flags são somente
uma parte pequena do arquivo total. Na Figura 4.7 é mostrado o efeito da redundância para
os bits de match. Utilizando o mesmo código Reed-Solomon (255,243,6), com t
m
= 6, e sem
proteção nos flags, ou seja t
f
= 0. Neste caso houve também uma redução no efeito do surto
de erros no processo de descompressão. A SER média neste caso é reduzida para 3, 91 %, com
44
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 4.5: Efeito do surto de erros no processo de descompressão, em termos da SER em função da
posição do surto de erros, para o arquivo ’paper4.txt’ usando proteção uniforme de erros com t = 5.
uma redundância adicional de 0, 64%
A Figura 4.8 mostra o efeito de inserir redundância adicional para os bits de flag e também
para os bits de match. Neste caso também foi usado o código Reed-Solomon (255,243,6) para
proteger os matches e os flags, tal que t
m
= t
f
= 6. Com isto é claro que o efeito dos surtos de
erros decrescem ainda mais, onde a SER média é de apenas 0, 40% com um acréscimo total de
0, 95% no tamanho do arquivo. Como os erros nos caracteres e nos offsets não se propagam e
não rendem um tamanho de arquivo errado depois da descompressão, não foi aplicado nenhuma
proteção especial para estas classes, de modo que t
c
= 0 e t
o93724(o)-1.87468(l)-4(o)-280.993(u5095(4 -1.887468(11.3(u509á4.2 -1.85705(i)4 5805.91 l3685.29]TJ/R8 11.9552P)14.3505(l)-243.918(p)-1.874128.)4.0054(n)-1.87468(h))-3.0491(s)-4987468(h))-3.34948(r)1.l7519(r)1.7h22.66(d)-1.87468(e)2..413374.3.87468(u)-1a4948(r)1.l7519(r)1.73505(p)-1.8d05095(a)2.3505(s)-2ç505(s)-27468(,)-211.6936(a7404686(t)-3.05095(o)-252.8125.65 .87468(a)-218.435(d)-17468(d)-1.87468(o)-242.728(q)-282.893(t)-3..874128.a)2.3505(d)-1.8791(s)-2035254(o)-1.87468(m)-4.2154(o)-252.812(t44(a)2.3505(c)ç505(s)-27468(,(e)2.34809.4.05095(a)-258.591128.a)2.879(o)-1.87468(s)-283.467(e)2.3505(r)1.76461(a)2.3505962.-248.7468(r455.51]TJ/R7 11.9552 Tf259.2(p)-1.8746q)-282.824.48 848.585(o)-252.81q)-287468(s)-243.312(b)-1.8.87468(e)2.3505.657-3.04891(a)2.35254(s)-2.46281(c)-3.u7468(i)-213.824(a)2.3.87468(e)2ç5095(i)-3õ468(o)-242.728(q)-28.3505.6551.87468(e)2.3505(s)-2.46281(c)2..87468788..51.896(4)2.34845vTd[(p)-1.á]TJ-243.12 -19.43934948(m)-26ril p arqui6105095(a)-258.592336 Td[(m)-0.7034948(m)-26222.66(d)-1.87468(e)2.5-3.05095(a)-238.509ao 7468(m)-4.92563(p)-1n154(o)-252.812(t(e)2.3504891(e)2.3)5(i).34948(i)-3.049943 6s.8751988.591-282n5914aosspus5095(i)2(p)-1.2 l2 [3505(e)2.3505(d)-1.8(o)-1.87468]3505(e)2. -12 l8(i)A-1.869(é)2sao303.574(e)-288.6468(s)-2.-2.46281(c)2.3571 6112.35254(d)-1.873l4113-1.8746q eo93724042(u)45(d)593.892(q)-[(=)-278.6.95977 0 T pu095(a)-l4116e cadeo .9552P
45
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 4.6: Efeito do surto de erros no processo de descompressão, em termos da SER em função da
posição do surto de erros, para o arquivo ’paper4.txt’ usando o esquema de proteção desigual de erros
para os flags.
de 48 bits de comprimento, e (t
f
= t
m
= 12, t
c
= t
o
= 0) para um surto de erros de 96 bits
de comprimento. A partir das tabelas pode-se ver que o método de proteção desigual proposto
é capaz de decrescer consideravelmente – para menos que 0, 5% para o surto de 48 bits e para
menos de 1, 00% para o surto de 96 bits – a SER média no arquivo descompactado. O custo
para essa SER média muito reduzida é pequeno, sendo em torno de 1% e 2% de redundância
adicional para os casos de surtos de 48 bits e 96 bits, respectivamente.
Tabela 4.1: SER média no arquivo descompactado e a redundância adicional inserida no arquivo com-
pactado pelo esquema de proteção desigual proposto para os arquivos paper1, paper2, paper3, paper4,
paper5 e paper6.
Arquivo de Texto
Surto Desempenho paper1 paper2 paper3 paper4 paper5 paper6
SER Média 0,18% 0,16% 0,17% 0,40% 0,42% 0,28%
48 bits
Redundância 1,00% 1,02% 1,00% 0,95% 0,91% 0,98%
SER Média 0,39% 0,33% 0,34% 0,84% 0,83% 0,51%
96 bits
Redundância 2,16% 2,21% 2,17% 2,01% 2,00% 2,12%
Por fim, o método proposto foi comparado com o método introduzido em [21] em termos
de aumento no tamanho do arquivo compactado requerido para cada esquema com objetivo de
46
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
47
0 20 40 60 80 100
0
0.2
0.4
0.6
0.8
1
Posição do Surto de Erros em % do Tamanho do Arquivo
SER
Figura 4.8: Efeito do surto de erros no processo de descompressão, em termos da SER em função da
posição do surto de erros, para o arquivo ’paper4.txt’ usando o esquema de proteção desigual de erros
para os flags e os matches.
O método proposto por Kitakami e Kawasaki em [21] apresenta uma vantagem sobre o mé-
todo proposto nesse trabalho: o fato de que a sua estrutura requer uma buferização muito menor.
Com essa estrutura é possível inserir a redundância adicional durante o processo de compres-
são, a medida que os blocos de B palavras-código vão se formando a redundância adicional é
inserida. Porém, o método proposto garante a proteção contra surtos de erros utilizando uma
redundância muito menor. Além disso, a codificação unária utilizada para os matches em [21]
torna a taxa de compressão muito pouco eficiente para aquele esquema.
Em relação ao método proposto por Siqueira em [23], o método proposto apresenta uma
redundância adicional um pouco maior. Entretanto, a proteção contra propagação de erros que
o método proposto garante é muito maior, pois o método proposto em [23] ignora propagação
de erros na classe dos matches.
Tabela 4.3: Aumento no tamanho do arquivo compactado requerido para proteger os flags e os matches
contra um surto de erros de 20 bits.
Arquivo de Texto paper1 progp obj1
Método Kitakami e Kawasaki 14,80% 21,00% 11,92%
Esquema Proposto 0,51% 0,52% 0,40%
48
4.4 Comentários Finais
Neste capítulo foi apresentado um esquema de proteção desigual de erros que usa códigos
Reed-Solomon em arquivos compactados com LZSS. Foram feitas comparações de resultados
de simulações com resultados de outro método. Pode-se concluir que o método proposto é
capaz de proteger o arquivo compactado contra propagação de erros, sem comprometer a taxa
de compressão de maneira considerável.
49
5 Conclusão
Nesta dissertação foi proposto um novo esquema de proteção desigual de erros para dados
compactados com LZSS. O esquema proposto usa uma nova estrutura para o dado compactado,
aplicando uma redundância adicional. Essa redundância adicional é conseguida utilizando o
código corretor de erros Reed-Solomon, que é muito eficaz na correção de surtos de erros. São
aplicados diferentes níveis de proteção contra erro em cada uma das classes de símbolos do
LZSS.
Os resultados das simulações mostram que o esquema proposto é muito mais eficiente que
os esquemas de proteção uniforme de erros. Com uma redundância adicional em torno de 2%,
o esquema foi capaz de reduzir a SER média nos arquivos descompactados para menos que 1%
na presença de um surto de erros de 96 bits. O esquema ainda apresentou muitas vantagens em
relação ao esquema proposto por Kitakami e Kawasaki em [21], como um taxa de compressão
muito melhor e mais próxima da taxa do LZSS, garantia de resistência total a surtos de erro de
um certo comprimento nas classes protegidas, e seus parâmetros de configuração determinados
com muita facilidade. Além disso, o esquema apresentou vantagens sobre o esquema proposto
Siqueira em [23], o qual mesmo apresentando uma nova estrutura de classes para o arquivo
compactado com LZSS, não explora a proteção das duas classes mais sensíveis a erros, permi-
tindo uma propagação desses erros considerável. Por fim, o esquema proposto nesse trabalho é
submetido a testes com vários arquivos de uma base conhecida e com diferentes tamanhos para
os surtos de erros, além de que a medida utilizada para os resultados desses testes é muito mais
fiel que as medidas utilizadas em outros trabalhos como em [21] e [23]. Parte deste trabalho foi
publicado em [44].
É importante sugerir como trabalhos futuros, o aprimoramento deste esquema de proteção
desigual no que diz respeito ao tamanho do buffer exigido na inserção da redundância adicional.
Com essa melhora o sistema seria ainda mais eficaz para sistemas em tempo-real. Uma opção
é a utilização de uma estrutura em blocos com a proposta em [21], com uma proteção contra
erros com códigos BCH binários.
50
APÊNDICE A -- Calgary Corpus
A base de dados Calgary Corpus [24] foi fundada por Ian Witten e Tim Bell, dois pesquisa-
dores da Nova Zelândia que trabalharam por algum tempo na Universidade de Calgary, Canadá.
O objetivo foi o estabelecimento de uma série padrão de testes para pesquisas em compres-
são de texto. A base de dados Calgary Corpus [24] foi utilizada pela primeira vez em [1] e
em [41] para avaliar o desempenho prático de vários esquemas de compressão de texto. Desde
então vários outros pesquisadores estão utilizando a base de dados para avaliar o desempenho
de esquemas de compressão de texto.
Nove tipos diferentes de arquivos de texto são representados, isso ocorre para que seja con-
firmado que o desempenho dos esquemas é consistente para qualquer que seja o tipo do artigo.
Alguns dos tipos têm mais que um arquivo na base de dados. Textos de Inglês normal são repre-
sentados por dois livros e seis artigos. São encontradas também um arquivo com bibliografia e
um artigo com notícias. Três códigos-fonte em linguagens diferentes e uma transcrição de uma
sessão no terminal também estão na base de dados. Todos estes arquivos usam codificação AS-
CII. Na base de dados ainda estão incluídos arquivos sem codificação ASCII: dois arquivos de
código executável, um arquivo de dados geofísicos e uma imagem em mapa de bits. A Tabela
A.1 mostra com mais detalhes o tipo de cada um dos arquivos da base de dados. A Tabela A.2
lista o tamanho, o número de linhas e caracteres de todos os arquivos.
51
Tabela A.1: Tipos dos arquivos da base de dados Calgary Corpus [24]
Arquivo Tipo
bib Arquivos de Bibliografia
book1 Livro - Far from the madding crowd
book2 Livro - Principles of computer speech
geo Dados Geofísicos
news Arquivo contendo notícias
obj1 Código compilado para Vax: compilação de progp
obj2 Código compilado para Apple Macintosh
paper1 Artigo - Arithmetic coding for data compression
paper2 Artigo - Computer (in)security
paper3 Artigo - In search of "autonomy"
paper4 Artigo - Programming by example revisited
paper5 Artigo - A logical implementation of arithmetic
paper6 Artigo - Compact hash tables using bidirectional linear probing
pic Imagem em mapa de bits (Texto e Desenhos)
progc Código-fonte em C
progl Código-fonte em Lisp
progp Código-fonte em Pascal
trans Transcrição de uma sessão em um terminal
Tabela A.2: Detalhes numéricos dos arquivos da base de dados Calgary Corpus [24]
Arquivo Linhas Palavras Caracteres
bib 6280 19274 111261
book 116622 141274 768771
book 215634 101221 610856
geo 18 617 102400
news 10059 53939 377109
obj1 87 495 21504
obj2 1213 4600 246814
paper1 1250 8512 53161
paper2 1731 13829 82199
paper3 1100 7219 46526
paper4 294 2166 13286
paper5 320 2099 11954
paper6 1019 6753 38105
pic 0 49 513216
progc 1487 6313 39611
progl 2244 9235 71646
progp 1966 4847 49379
trans 2737 9255 93695
52
APÊNDICE B -- Códigos Reed-Solomon
Os códigos Reed-Solomon foram desenvolvidos por Irving Reed e Gustave Solomon em
1960 [18], e são códigos corretores de erros com uma vasta aplicação na comunicação digital
e no armazenamento de dados. São utilizados para correção de erros em vários sistemas de
armazenamento de dados, como CD, DVD, etc, e sistemas de comunicações digitais [17]. O
codificador Reed-Solomon insere bits de redundância no bloco de dados a ser codificado. O
decodificador Reed-Solomon processa cada bloco e procura recuperar os dados originais trans-
mitidos. O número de erros que podem ser corrigidos dependem dos parâmetros adotados para
o código Reed-Solomon.
Os códigos Reed-Solomon são um subconjunto dos códigos de bloco lineares BCH (Bose
Chaudhuri Hocquenghem). Um código Reed-Solomon é especificado com RS(n, k, t), onde
n é o número de símbolos de saída, k é o número de símbolos de entrada, e t é a capacidade
de correção do código. O código Reed-Solomon pode corrigir até t símbolos errados em uma
palavra código, onde 2t = n − k como mostrado na Figura A.1.
dados paridade
n n-k
Figura A.1: Estrutura de um dado codificado com código Reed Solomon
Como exemplo, para o código Reed-Solomon (255,223,16) com símbolos de 8 bits, cada
palavra código possui um comprimento de 255 bytes dos quais 223 são dados e 32 são bytes
de paridade. Nos códigos Reed-Solomon os bytes de paridade correspondem a 2t, onde t é a
capacidade de correção do código que nesse caso t = 16. Desse modo, o decodificador pode
corrigir até 16 erros na seqüência de 255 bytes. O comprimento máximo da palavra-código n é
definido em função do tamanho dos símbolos em bits s, ou seja n = 2
s
− 1. É pertinente citar
como exemplo o código usado neste trabalho, se os símbolos de uma palavra-código têm s = 8
bits, o comprimento máximo da palavra-código n é n = 2
8
− 1 = 255.
53
As palavras-código Reed-Solomon são geradas no codificador através de um polinômio
gerador [18,43]. No processo de decodificação, o decodificador Reed-Solomon procura identi-
ficar a posição e a magnitude de até t erros e corrigi-los. A decodificação é feita em dois passos,
encontrar o localizador polinomial e as raízes deste polinômio. Para encontrar o localizador po-
linomial é possível usar o algoritmo de Euclides ou Berlekamp-Massey [43]. Para encontrar as
raízes do polinômio, utiliza-se o algoritmo de busca de Chiem [43].
54
Referências
[1] T.C. Bell, J.G. Cleary, and I.H. Witten, Text compression, Prentice Hall, 1990.
[2] W. K. Ng, and C. V. Ravishankar, “Block-oriented compression techniques for large sta-
tistical databases”, IEEE Trans. on Knowledge and Data Engineering, vol. 9, no. 2, pp.
314–328, 1997.
[3] S. W. Chiang, and L. M. Po, “Adaptive lossy LZW algorithm for palettised image com-
pression”, IEE Electronics Letters, vol. 33, no.10, pp. 852–854, 1997.
[4] D. Greene, M. Vishwanath, F. Yao, and T. Zhang, “A progressiveZiv-Lempelalgorithmfor
image compression”, Proceedings of Compression and Complexity of Sequences, 1997.
[5] J. Ziv, and A. Lempel, “A universal algorithm for sequential data compression”, IEEE
Transactions on Information Theory, vol.23, pp.337-343, 1977.
[6] J. A. Storer, and T. G. Syzmanski, “Data Compression via Textual Substituion”, Journal
of the ACM, vol.29, pp.928-951, 1982.
[7] J. Ziv, and A. Lempel: “Compression of individual sequences via variable-rate coding”,
IEEE Transactions on Information Theory, vol.24, pp.530-536, 1978.
[8] K. Sayood: Introducion to Data Compression, Morgan Kaufmann Publishers, 2000.
[9] T. Bell, “Better OPM/L text compression”, IEEE Transactions on Communications, vol.
34, no.12, pp. 1176–1182, 1986.
[10] J. Hagenauer, and T. Stockhammer, “Channel coding and transmission aspects for wireless
multimedia”, Proceedings of the IEEE, vol.87, no.10, pp. 1764–1777, 1999.
[11] J. C. Lo, M. Kitakami, and E. Fujiwara, “Reliable Logic Circuits with Byte Error Control
Codes – A Feasibility Study”, Proceedings of IEEE International Symposium on Defect
and Fault Tolerance in VLSI Systems, November 1996.
[12] C. de Almeida, and R. Palazzo Jr., “Efficient two-dimensional interleaving technique by
use of the set partitioning concept”, IEE Electronics Letters, vol.32, no.6, pp. 538–540,
1996.
[13] W. Coene, H. Pozidis, M. Van Dijk, J. Kahlman, R. Van Woudenberg, and B.Stek, “Chan-
nel coding and signal processing for optical recording systems beyond DVD”, IEEE Tran-
sactions on Magnetics, vol. 37, no.2, pp.682–688, 2001.
[14] E. Biglieri, J. Proakis, and S. Shamai, “Fading channels: information-theoretic and com-
munications aspects”, IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2619–
2692, 1998.
55
[15] W. Zhu, and J. Garcia-Frias, “Stochastic context-free grammars and hidden Markov mo-
56
[33] C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Jor-
nal, vol.27, pp.379-423, 623-656, October, 1948.
[34] M. Nelson and J. Gailly: The Data Compression Book’, M&T Books, 1995.
[35] G. Held, Data and Image Compression: Tools and Techniques, John Wiley and Sons Ltd,
1996.
[36] E. Fujiwara, Code Design for Dependable Systems: Theory and Practical Applications,
John Wiley and Sons Ltd, 2006.
[37] S. Lonardi, W. Szpankowski and M. D. Wark: “Error Resilient LZ77 Data Compres-
sion: Algorithms, Analysis, and Experiments”, IEEE Transactions on Information Theory,
vol.53, 2007
[38] T. Okuda, E. Tanaka, and T. Kasai, “A method for correction of grabled words based on
the Levenshtein metric”, IEEE Transactions on Computer, vol.C-25, pp. 172–176, 1976.
[39] R. Bauer, and J. Hagenauer: “On variable length codes for iterative source/channel deco-
ding”, Proceedings of IEEE Data Compression Conference, 2001.
[40] H. Chen, M. Kitakami, and E. Fujiwara, “Burst error recovery for VF arithmetic coding”,
IEICE Transactions on Fundamentals, 2001, vol. E84-A, no. 4, pp. 1050–1063, 2001.
[41] T.C. Bell, I.H. Witten, and J.G. Cleary, “Modeling for text compression”, Computing
Surveys, vol. 21, no. 4, pp. 557–591, December 1989.
[42] R. Geldreich Jr, “Program Simple Hashing LZ77, Slifind Dictionary Compression”, Dis-
ponível em: http://www.programmersheaven.com, Acessado em abril/2006.
[43] Reed-Solomon Coding Tutorial, 4i2i Communications Ltd 2004, Disponível em:
http://www.4i2i.com/reed_solomon_codes.htm, Acessado em abril/2007.
[44] Z. C. Pereira, M. E. Pellenz, R.D. Souza and M. A. A. Siqueira: “Unequal Error Protection
for LZSS Compressed Data Using Reed-Solomon Codes”, Aceito para publicação na IET
Communications.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
