Orientador: Reginaldo Palazzo Junior / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T22:23:13Z (GMT). No. of bitstreams: 1 Queiroz_CatiaReginadeOliveiraQuilles_D.pdf: 1560188 bytes, checksum: 2b21f95bbc77dac42e165eb38509518e (MD5) Previous issue date: 2011 / Resumo: Neste trabalho apresentamos a construção de códigos geometricamente uniformes derivados de grafos sobre anéis quocientes de inteiros e de ordens dos quatérnios. Inicialmente propomos um procedimento para a geração de códigos quase-perfeitos derivados de grafos sobre anéis quocientes de inteiros, que além de serem geometricamente uniformes, são capazes de corrigir mais padrões de erros que os códigos perfeitos, porém com uma menor cardinalidade. Além disso, observamos que os códigos perfeitos são um caso particular dos códigos quase-perfeitos. Os códigos geometricamente uniformes derivados de quocientes de ordens dos quatérnios foram obtidos de forma similar, porém a geometria relacionada é a hiperbólica e os códigos derivados estão no plano hiperbólico. A estrutura algébrica associada a essa classe de códigos não havia sido obtida até então para esta geometria. Apresentamos ainda um procedimento para o rotulamento de pontos gerados por tesselações do plano hiperbólico no disco de Poincaré, e obtemos a representação geométrica dos códigos obtidos / Abstract: In this work we present the construction of geometrically uniform codes derived from graphs over quotient rings of integers and quaternion orders. Initially we propose a procedure to generate quasi-perfect codes derived from graphs over quotient rings of integers, which in addition to preserving the property of being geometrically uniform codes they are able to correct more error patterns than the perfect codes, by decreasing its cardinality. Furthermore, we observe that the perfect codes are a particular case of the quasi-perfect codes. The geometrically uniform codes derived from quotient of the quaternion orders are obtained similarly as in the previous case, however the related geometry is the hyperbolic and the derived codes are on the hyperbolic plane. The algebraic structure associated with this class of codes had not been obtained so far for this geometry. We also present a procedure for labeling the points generated by tesselations of the Poincaré disk, and showing the geometric representation of the aforementioned codes / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientadores: Reginaldo Palazzo Junior, Eduardo Brandani da Silva / Tese (doutorado) - Universidade Estadula de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T12:13:26Z (GMT). No. of bitstreams: 1 Albuquerque_ClariceDiasde_D.pdf: 1059216 bytes, checksum: 2cecc7c883d512057587e36d3635e775 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho apresentamos um amplo estudo de códigos quânticos topológicos, trazendo inovação para esta área. Inicialmente geramos novos códigos quânticos teóricos, dentre os quais se destaca a classe [[d2,2,d]] cujos parâmetros são os melhores ate então apresentados para este tipo de código. Nesta proposta sistematizamos a construção de códigos teóricos baseados em teoria de grupos e também em analise combinatória. Com respeito aos códigos quânticos topológicos em superfícies com gênero g = 2, apresentamos uma construção baseada em geometria hiperbólica, generalizando a construção de Kitaev. Reproduzimos e ampliamos a classe de códigos quânticos com distancia 3 decorrentes de mergulhos de grafos completos em superfícies com gêneros específicos obtidos primeiramente por Bombin e Martin-Delgado, com o diferencial de descreve-los geometricamente e exibir claramente seus parâmetros. Obtemos uma classe de códigos MDS Maximum Distance Separable). Explicitamos em tabelas os melhores códigos para superfícies com gênero g = 2,3,4 e 5 obtidos a partir dessa construção, e analisamos esses resultados. / Abstract: In this work we present an extensive study of topological quantum codes. As a consequence, new promising ideas, concepts and results are also presented. First of all, new toric quantum codes are constructed among which the [[d2,2,d]] class stands out as the best known so far. This proposed construction of toric codes is realized based upon group theory and combinatorial analysis. Regarding the topological quantum codes in surfaces with genus g = 2, we consider a construction method based on hyperbolic geometry and so generalizing Kitaev's construction. We reproduce and enlarge the class of quantum codes with distance 3 as a consequence of the embedding of complete graphs in surface with specific genus. This class was first proposed by Bombin andMartin-Delgado. The latter class is geometrically described and its parameters are explicitly exhibited. We also obtain a class of MDS (Maximum Distance Separable) codes in surfaces with genus g = 2,3,4 and 5, obtained by the proposed construction are tabulated and analyzed. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Jaime Portugheis / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-08-11T22:42:49Z (GMT). No. of bitstreams: 1 Marinho_RafaeldeSousa_M.pdf: 804635 bytes, checksum: 4aa50f59603e3de640e8d2860980f3c6 (MD5) Previous issue date: 2007 / Resumo: Durante a última década foram desenvolvidas novas ferramentas para o projeto e análise da decodificação iterativa de códigos concatenados. Duas destas ferramentas são: o algoritmo de evolução de densidades de probabilidade (conhecido em inglês como density evolution) e as funções EXIT (do inglês, Extrinsic Information Transfer Functions). As curvas EXIT foram primeiramente desenvolvidas para códigos concatenados paralelos (PCC, do inglês, Parallel Concatenated Codes). Posteriormente, estas curvas foram utilizadas para analisar a decodificação da classe de códigos conhecida como LDPC (do inglês, Low-Density ParityCheck Codes). Como se sabe, o desempenho dos códigos LDPC pode se aproximar bastante da capacidade de canal. Neste trabalho utilizamos as funções EXIT para analisar um sistema de transmissão digital composto pela concatenação serial de um codificador LDPC, um modulador M-APSK e um codificador diferencial. O canal considerado é o AWGN não-coerente de bloco. O processo de decodificação/demodulação é descrito através de um algoritmo iterativo baseado em um grafo-fator. Da análise concluímos que códigos LDPC regulares possuem um bom desempenho, mas ainda estão afastados da capacidade de canal. / Abstract: Late 1990s, new tools for evalution and design of iterative decoding of concatenated codes were developed. Two of these tools are: the density evolution algorithm and the EXlT charts. The EXlT charts were first developed for Parallel Concatenated Codes (PCC) and then used for evaluating the decoding process of Low-Density Parity-Check codes (LDPC Codes). As already known, the LDPC codes perform dose to channel capacity limits. ln this work we use the EXlT Charts to evaluate a digital transmission system com posed by the concatenation of a LDPC encoder, a M-APSK modulator and a diferencial encoder. The channel considered is an AWGN block noncoherent channel and the decoding/demodulating process is described through an iterative algorithm based on a factor graph. The analisys of this system we condude that LDPC codes have good performance, but are still far from channel capacity. / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientador: Renato Baldini Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-24T14:17:23Z (GMT). No. of bitstreams: 1 Dantas_PamelaJoyceSilvaMelo_M.pdf: 584157 bytes, checksum: affc3041d38415e1af35e32a78ebd6e1 (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação apresentamos um estudo sobre a viabilidade de construção e de utilização de códigos LDPC (Low Density Parity Check) definidos sobre corpos finitos de inteiros módulo-p, onde p é um inteiro primo. A modulação utilizada para avaliar o desempenho dos códigos obtidos é a p ? PSK. Códigos LDPC definidos sobre corpos finito de inteiros possuem estrutura algébrica bem definida, são facilmente feitos invariantes a rotação de fase da portadora no processo de modulação e podem ser feitos mais curtos que os seus equivalentes binários. O método de decodificação iterativa utilizada na avaliação do desempenho destes códigos é uma adaptação do algoritmo SISO (Soft Input Soft Output) proposto por P. G. Farrell e J. Moreira [1] e [2] que utiliza a distância euclidiana como parâmetro de confiabilidade dos símbolos da palavra código recebida. Os códigos LDPC utilizados na simulação da codificação e decodificação do canal de comunicação são definidos para o campo de inteiros Z5. O canal de comunicação foi modelado com um ruído gaussiano branco aditivo (AWGN - Additive White Gaussian Noise) e com um desvanecimento Rayleigh. Ambos modelos de canal utilizam a modulação 5 ? PSK. O desempenho dos esquemas de codificação LDPC definidos sobre Z5 foram analisados de modo comparativo com sistemas equivalentes de codificação binários e quartenários. Palavras-chave: Códigos LDPC não binários, corpos de inteiros módulo-p, modulação p ? PSK, canal AWGN, desvanecimento Rayleigh / Abstract: On this disertation we present a study on the feasibility of constructions and use of LDPC (Low Density Parity Check) codes defined over finite fields of integers modulo p, where p is a prime integer. The modulation used to evaluate the performance of the codes is obtained from a p ? PSK. LDPC codes defined over finite field of integers have well defined algebraic structure, they can be easily made invariant to phase rotation in the carrier modulation process, and can be made shorter than its binary equivalent. The iterative decoding method used during the evaluating the performance of these codes is an adaptation of the algorithm SISO (Soft Input Soft Output) proposed by P. G. Farrell and J. Moreira [1] e [2] that uses the Euclidean distance as the reliability of the parameter code word symbols received. The LDPC codes used during the simulation of encoding and decoding of the communication channel are defined for the whole body of Z5. The communication channel was modeled as additive white Gaussian noise (AWGN) and Rayleigh fading. Both communication channel models used modulation 5 ? PSK. The performance of LDPC coding schemes defined over Z5 were analyzed comparatively with equivalent systems of binary and quaternary encoding. Key-words: LDPC codes nonbinary, Field of integers modulo-p, p ? PSK modulation, AWGN Channel,Rayleigh fading OBSERVAÇÃO Verificar meu nome, pois no mestrado tava na dac o nome de solteira(Pâmela Joyce Silva Melo), mas quando fiz a matricula do doutorado troquei para o de casada(Pâmela Joyce Silva Melo Dantas) / Mestrado / Telecomunicações e Telemática / Mestra em Engenharia Elétrica

Orientador: Yuzo Iano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T10:52:38Z (GMT). No. of bitstreams: 1 Leite_RicardoBarroso_D.pdf: 5004138 bytes, checksum: d3b1d6c9ea113cae9462605ed91a70ca (MD5) Previous issue date: 2014 / Resumo: Muitas áreas de pesquisa utilizam imagens digitais e outros arranjos multidimensionais de dados, que para serem transmitidos e armazenados de forma mais eficiente passam por um processo de filtragem e compressão. A transformada wavelet isotrópica é tradicionalmente usada e considerada um método rápido e eficiente para compressão. Por agregar as vantagens de representação multirresolução e a localização dos contornos, as bandelets têm sido consideradas estado-da-arte em várias aplicações de processamento de imagens. Neste trabalho é apresentado um novo método para processamento e compressão de imagens baseado na transformada bandelet. Em nosso método, uma estimativa é feita de forma a reduzir o espaço de busca e tornar o processamento da imagem assintoticamente mais rápido. Os resultados mostram que pode ser feito um compromisso entre qualidade da imagem e tempo computacional, tornando o esquema mais atrativo para uma ampla gama de aplicações. Dentre as áreas beneficiadas por esse método estão transmissão de imagens e vídeo (TV digital e dispositivos móveis), imagens médicas e modelagem 3D / Abstract: Many research areas use digital images and other multi-dimensional arrays of data which to be transmitted and stored more efficiently pass through a filtering process and compression. The isotropic wavelet transform is traditionally used and considered a fast and efficient method for compression. By adding the advantages of multi-resolution representation and location of edges, the bandelets have been considered state of the art in several image processing applications. This work presents a new method for processing and compression based on bandelet transform images. In our method, an estimation is made to reduce the search space and make the image processing asymptotically faster. The results show that a compromise can be made between image quality and computational time, which makes it a more attractive scheme for a wide range of applications. Among the areas benefited by this method are image and video transmission (digital TV and mobile devices), medical imaging and 3D modeling / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientadores: Fernando Eduardo Torres Orihuela, Cícero Fernandes de Carvalho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T03:11:40Z (GMT). No. of bitstreams: 1 Peixoto_Rafael_D.pdf: 876847 bytes, checksum: ae0f5d0ea0f2c3e3d550bc60eb1ac66a (MD5) Previous issue date: 2011 / Resumo: Definidas sobre uma F-álgebra, os conceitos de função peso e função peso fraco foram introduzidos de forma a simplificar a teoria dos códigos corretores de erros que utilizam ferramentas da geometria algébrica. Porém, todos os códigos suportados por estes conceitos estão intimamente ligados à códigos provenientes de curvas algébricas, ou seja, os códigos geométricos de Goppa. Uma modificação da noção de função peso foi apresentada permitindo assim construir códigos lineares sobre variedades algébricas. Nesta tese, apresentamos uma generalização da teoria de funções pesos fracos que possibilitou a construção de códigos sobre variedades de dimensão arbitrária. Determinamos uma cota para a distância mínima destes códigos, e finalmente, apresentamos uma caracterização tanto para as álgebras munidas de funções pesos quanto para as álgebras munidas de um conjunto especial de funções pesos fracos / Abstract: Defined on a F-algebra, the concepts of weight and near weight function were introduced to simplify the theory of error correcting codes using tools from algebraic geometry. However, all codes supported by these theories are geometric Goppa codes. The concept of weight function was generalized and used to construct linear codes on algebraic varieties. In this thesis, we present a generalization of near weights theory able to construct codes on higher dimensional varieties, and we define a formula for the minimum distance of such codes. Finally, we characterize the algebras with a weight function and the algebras admitting a special set of two near weight functions / Doutorado / Matematica / Doutor em Matemática

This thesis focuses on the re-generation of sound from a spike based coding system. Three different types of spike based coding system have been analyzed. Two of them are biologically inspired spike based coding systems i.e. the spikes are generated in a similar way to how our auditory nerves generate spikes. They have been called AN (Auditory Nerve) spikes and AN Onset (Amplitude Modulated Onset) spikes. Sounds have been re-generated from spikes generated by both of those spike coding technique. A related event based coding technique has been developed by Koickal and the sounds have been re-generated from spikes generated by Koickal's spike coding technique and the results are compared. Our brain does not reconstruct sound from the spikes received from auditory nerves, it interprets it. But by reconstructing sounds from these spike coding techniques, we will be able to identify which spike based technique is better and more efficient for coding different types of sounds. Many issues and challenges arise in reconstructing sound from spikes and they are discussed. The AN spike technique generates the most spikes of the techniques tested, followed by Koickal's technique (54.4% lower) and the AN Onset technique (85.6% lower). Both subjective and objective types of testing have been carried out to assess the quality of reconstructed sounds from these three spike coding techniques. Four types of sounds have been used in the subjective test: string, percussion, male voice and female voice. In the objective test, these four types and many other types of sounds have been included. From the results, it has been established that AN spikes generates the best quality of decoded sounds but it produces many more spikes than the others. AN Onset spikes generates better quality of decoded sounds than Koickal's technique for most of sounds except choir type of sounds and noises, however AN Onset spikes produces 68.5% fewer spikes than Koickal's spikes. This provides evidences that AN Onset spikes can outperform Koickal's spikes for most of the sound types.

Orientador: Jaime Portugheis / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T15:49:19Z (GMT). No. of bitstreams: 1 PujaicoRivera_Fernando_M.pdf: 2105653 bytes, checksum: f62384ffbf5226353eba3406ba7735b8 (MD5) Previous issue date: 2011 / Resumo: Desde que Gallager introduziu o algoritmo de decodificação Bit-Flipping (BF) com decisão abrupta para códigos Low Density Parity Check (LDPC), outras duas variantes foram propostas por Sipser e Spielman para os códigos conhecidos como "Expander Codes". Posteriormente, uma versão da decodificação BF por decisão suave conhecida como decodificação Modified Weighted BF (MWBF), foi investigada. Esta tese propõe versões modificadas dos algoritmos de Sipser e Spielman. Resultados de simulações para códigos Low Density Generator Matrix (LDGM) sistemáticos, com comprimento longo mostraram um melhor desempenho da versão proposta. Adicionalmente, para um comprimento médio dos códigos LDGM, resultados de simulações mostraram um desempenho similar à decodificação MWBF com a vantagem de não ser necessário o uso de operações em ponto flutuante / Abstract: Since Gallager introduced Bit-Flipping (BF) decoding with hard-decision for Low-Density Parity- Check Codes (LDPC), other two variants were proposed by Sipser and Spielman for expander codes. Later, a soft-decision version of BF decoding, known as Modified Weighted BF (MWBF) decoding, was investigated. This thesis proposes modified versions of Sipser and Spielman algorithms. Simulation results for long systematic Low-Density Generator Matrix (LDGM) codes show a better performance of the proposed versions. Moreover, for moderate length systematic LDGM codes, simulation results show performance similar to that of MWBF decoding with the advantage of not requiring floating-point operations / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

We design efficient algorithms for computational problems over strings in several models where the algorithms have limited access to the input. These models, and algorithms developed respecting these constraints, are becoming increasingly relevant due to the rapidly increasing size of datasets in myriad applications. Our first problem of interest is \emph{trace reconstruction}. This is an important problem in learning theory and coding theory, and has applications in computational biology. In this problem, the goal is to recover an unknown string given independent samples (\emph{traces}) of it generated via a probabilistic noise process called the deletion channel. We give state-of-the-art algorithms for this problem in several settings. Then we consider the problem of estimating the \emph{longest increasing subsequence (LIS)} of a given string in sublinear time, given query access to the string. While the LIS of a string can be computed exactly in near-linear time, the optimal complexity of approximating the LIS length, especially when the LIS is much less than the string length, is still open. We significantly improve upon prior work in terms of both approximation and time complexity in this regime. The runtime of our algorithm essentially matches the trivial query complexity lower bound as a function of the length of the LIS. Finally, we consider the problem of local decoding, or random access, on compressed strings. The Burrows-Wheeler Transform (BWT) is an important preprocessing step in lossless text compression that rearranges a string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings. However, the decoding process of the BWT is inherently sequential, and prevents fast random access to the original string. We design a succinct data structure for locally decoding short substrings (and answering several other queries) of a given string under its compressed BWT efficiently.

Syftet med detta examensarbete var att undersöka potentialen av TAKK (Tecken Som Alternativ och Kompletterande Kommunikation) i undervisningen av främmande språk i den svenska skolan. Genom en kvasiexperimentell utvärdering tillämpades TAKK under en lektion i spanska där 18 elever skulle lära sig 24 nya ord om mat. Eleverna gick i åk 6 och studerade nybörjarspanska. Orden lärdes ut på ett traditionellt sätt genom att säga och skriva dem men orden 1-12 ackompanjerades dessutom av ett TAKK tecken som eleverna uppmanades att härma. Eleverna förhördes skriftligt vid tre tillfällen på en period av två veckor; glosförhör 1 bestod av 24 ord utan bilder på tecknen, glosförhör 2 bestod av 24 ord och bilder på tecknen för orden 1-12. Glosförhör 3 bestod av endast 12 bilder på tecknen för ord 1-12. Orden skulle översättas till svenska förutom vid tredje tillfället där det skulle skrivas på spanska. I ljuset av Paivios (1971) Dual Coding Theory och The Additivity Hypothesis visade resultatet på glosförhören en positiv inverkan av gesterna/tecknen på inlärningen av orden. Alla elever fick ett högre antal rätt översatta ord vid glosförhör 2. Man kan försiktigt dra slutsatsen att tecknen från TAKK bidrog till en förbättrad memorering av orden då de lagrades i vårt multimodala minne där de lämnade två interrelaterade minnesspår.