1 |
[pt] CODIFICADORES UNIVERSAIS VIA RECORRÊNCIA DE PADRÕES PARA FONTES COM NÚMERO DE ESTADOS FINITO / [en] UNIVERSAL STRING MATCHING ENCODERS BY RECURRENCE OF STANDARDS FOR SOURCES WITH FINITE NUMBER OF STATESMARCELO DA SILVA PINHO 01 December 2005 (has links)
[pt] Os codificadores universais via recorrência de padrões
surgiram nos anos 70, quando foram propostos os
codificadores lz77 e lz78. Devido a baixa complexidade
computacional e ao bom desempenho, quando aplicados na
compressão de arquivos de dados, estes codificadores se
tornaram extremamente populares. Embora estes
codificadores sejam universais, i.e., possuam taxas de
compressão que convergem para entropia, recentemente foi
mostrado que as taxas de compressão não convergem da forma
mais rápida possível, nem mesmo para a classe de fontes
sem memória. A redundância de um codificador universal C,
dada por R, mede a rapidez com que a taxa de compressão
converge para a entropia. Para fontes com número de
estados finito, enquanto os melhores resultados de
codificadores universais via recorrência de padrões
apresentam uma redundância da ordem de 1/{log n}, existem
codificadores que atingem uma redundancia de {log n} /n.
Portanto, os codificadores via recorrência de padrões não
são ótimos. Embora seja conhecido codificadores ótimos
segundo o critério da redundância, tais codificadores
possuem uma alta complexidade computacional e são pouco
úteis na prática. Dentre os codificadores via recorrência
de padrões, o codificador lz78 possui uma das mais baixas
redundâncias para a classe de fontes com número de estados
finito. De fato, não existe outro codificador desta
classe, tal que a redundância seja melhor que a do lz78.
Tomando como base o lz78, este trabalho propõe novas
técnicas para acelerar a convergência da taxa de
compressão (diminuir a redundância) dos codificadores
universais via recorrência de padrões, para fontes com
número de estados finito. Estas técnicas dão origem a
novas versões do lz78. As redundâncias das novas versões
são estabelecidas, considerando a classe de fontes com
número de estados finito. Estas versões são aplicadas na
compressão de arquivos de dados, e os resultados obtidos
são comparados com os resultados de versões anteriores. / [en] The string matching encoders were proposed about 20 years
ago, when the lz77 and lz78 were introduced. They became
extremely popular because of the relationship between
their low complexity and their good performance. Although
these encoders are universal, that is, their compression
rates converge to the source entropy, it was shown,
recently, that those rates do not converge as fast as
possible, even for the class of memoryless source. The
redundancy of an unversal encoder C, denoted by Rc,
measures how fast the compression rate converge to the
entropy. In the class of Finite State Machine (FSM)
source, while the best result of the string matching
encoders is O 1/ {log n}, there are encoders which achieve
a redundancy of O {log n}/n. Therefore, the string
matching encoders are not optimal. Even though optimal
encoders are known, in general, those encoders have a high
complexity and are not useful in practice. Considering the
class of string matching encoders, the lz78 has one of the
best results over the class of FSM source. In fact, there
is no encoder based on the string matching, which archives
a better redundancy. This work makes use of the lz78
encoder to propose new techniques to improve the
performance of sting matching encoders over the class of
FSM. These techniques bring up new versions of the lz78.
For the class of FSM, the redundancies of this versions
are stablished. These versions are used to compress data
files, and their perfoermances are compared to the
performances of older versions.
|
2 |
[en] PERMUTATION CODES FOR DATA COMPRESSION AND MODULATION / [pt] CÓDIGOS DE PERMUTAÇÃO PARA COMPRESSÃO DE DADOS E MODULAÇÃODANILO SILVA 01 April 2005 (has links)
[pt] Códigos de permutação são uma interessante ferramenta
matemática que
pode ser empregada para construir tanto esquemas de
compressão com perdas quanto esquemas de modulação em um
sistema de transmissão digital.
Códigos de permutação vetorial, uma extensão mais
poderosa
dos códigos de
permutação escalar, foram recentemente introduzidos no
contexto de compressão de fontes. Este trabalho
apresenta
novas contribuições a essa teoria
e introduz os códigos de permutação vetorial no contexto
de modulação.
Para compressão de fontes, é demonstrado matematicamente
que os códigos
de permutação vetorial (VPC) têm desempenho assintótico
idêntico ao do
quantizador vetorial com restrição de entropia (ECVQ).
Baseado neste desenvolvimento, é proposto um método
eficiente para o projeto de VPC s.
O bom desempenho dos códigos projetados com esse método
é
verificado
através de resultados experimentais para as fontes
uniforme
e gaussiana: são
exibidos VPC s cujo desempenho é semelhante ao do ECVQ e
superior ao de
sua versão escalar. Para o propósito de transmissão
digital, é verificado que
também a modulação baseada em códigos de permutação
vetorial (VPM)
possui desempenho superior ao de sua versão escalar. São
desenvolvidas as
expressões para o projeto ótimo de VPM, e um método é
apresentado para
detecção ótima de VPM em canais AWGN e com
desvanecimento. / [en] Permutation codes are an interesting mathematical tool
which can be used
to devise both lossy compression schemes and modulation
schemes for digital transmission systems. Vector
permutation codes, a more powerful extension of scalar
permutation codes, were recently introduced for the purpose
of source compression. This work presents new contributions
to this theory
and also introduces vector permutation codes for the
purpose of modulation.
For source compression, it is proved that vector
permutation codes (VPC)
have an asymptotical performance equal to that of an
entropy-constrained
vector quantizer (ECVQ). Based on this development, an
efficient method
is proposed for VPC design. Experimental results for
Gaussian and uniform
sources show that the codes designed by this method have
indeed a good
performance: VPC s are exhibited whose performances are
similar to that
of ECVQ and superior to those of their scalar counterparts.
In the context
of digital transmission, it is verified that also vector
permutation modulation (VPM) is superior in performance to
scalar permutation modulation.
Expressions are developed for the optimal design of VPM,
and a method is
presented for maximum-likelihood detection of VPM in AWGN
and fading
channels.
|
3 |
[en] JOINT SOURCE/CHANNEL CODING USING LAPPED TRANSFORMS / [pt] CODIFICAÇÃO CONJUNTA FONTE/CANAL UTILIZANDO TRANSFORMADASARTHUR LUIZ AMARAL DA CUNHA 15 July 2002 (has links)
[pt] Neste trabalho é feito um estudo sobre compressão de
imagens para canal ruidoso.Inicialmente, esquemas de
complexidade moderada sem a utilização do princípio da
separação de Shannon são investigados e simulados. Com
isso, mostra-se que esquemas eficientes de codificação
conjunta fonte/canal existem e podem eventualmente
apresentar melhor performance do que esquemas separados de
codificação e canal e fonte. São também investigados,
algoritmos de codificação de imagens visando a transmissão
num capital ruidoso. Nesse contexto, é proposto um esquema
utilizando transformadas com superposição com boa
performance, como mostram as simulações realizadas. O
esquema posteriormente estendido para imagens multi-
espectrais mostrando-se igualmente eficiente. / [en] In the present dissertation we investigate image
compression techniques for transmission over binary
symmetric channels poluted with noise. Frist we simulate
some known techniques for joint source/channel coding that
dispenses with the use of error correcting codes. These
techiniques may exhibit better performance when complexity
and delay constraits are at stake. We further propose an
image compression algorithm for noisy channels based on
lapped/block transforms and block source/channel coding. We
simulate the proposed scheme for various channel
situations. The algorithm is further extented to handle
compression and transmission of multiepectral remote
sensing satellite imagery. Results for natural and
multiespectral images are presented showing the good
performance attained by the proposed schemes.
|
Page generated in 0.0448 seconds