Este trabalho, elaborado por meio de pesquisa bibliográfica, apresenta um apanhado sobre os dígitos verificadores presentes no Cadastro de Pessoas Físicas (CPF), no código de barras, e no sistema ISBN; faz uma introdução sobre a métrica de Hamming e os códigos corretores de erros; cita a classe de códigos mais utilizada, que são os códigos lineares, e deixa a sugestão de uma proposta pedagógica para professores de matemática aplicarem no Ensino Fundamental, podendo ser ajustada também para o Ensino Médio. No apêndice A, são propostos alguns exercícios que podem ser trabalhados com os alunos em sala de aula. / This work, based on the attached references, presents an overview of the check digits that appear in the Brazilian document CPF, in the bar code and the ISBN system. Moreover, it makes an introduction to the Hamming metric and error-correcting codes. In particular, some considerations about linear codes are done and it makes a suggestion of a pedagogical approach to apply it in middle school and can also be adjusted to high school. In the Appendix A are proposed some exercises to students.

Primitivas criptografias assimétricas são essenciais para conseguir comunicação segura numa rede ou meio público. Essas primitivas podem ser instaladas como bibliotecas de software ou como coprocessadores de hardware. Coprocessadores de hardware são muito utilizados em cenários como Systems on Chip (SoC), dispositivos embarcados ou servidores de aplicações específicas. Coprocessadores existentes baseados em RSA ou curvas ellipticas (ECC) fazem um processamento intenso por causa da aritmética modular de grande precisão, portanto não estão disponíveis em plataformas com quantidade de energia mais restrita. Para prover primitivas assimétricas para esses dispositivos, será avaliado um esquema de cifração assimétrica que utiliza artimética de pequena precisão, chamado McEliece. McEliece foi proposto com códigos de Goppa binários durante o mesmo ano que o RSA, porém com chaves públicas 50 vezes maiores. Por causa de chaves tão grandes ele não ganhou muita atenção como RSA e ECC. Com a adoção de códigos Quase-Diádicos de Goppa binários é possível obter níveis de segurança práticos com chaves relativamente pequenas. Para avaliar uma implementação em hardware para esse esquema, foi proposto uma arquitetura escalável que pode ser configurada de acordo com os requisitos do projeto. Essa arquitetura pode ser utilizada em todos os níveis de segurança, de 80 até 256 bits de segurança, da menor unidade até as maiores. Nossa arquitetura foi implementada na família de FPGAs Spartan 3 para códigos de Goppa binários, onde foi possível decifrar em 5854 ciclos com 4671 Slices, enquanto que na literatura os melhores resultados obtidos são de 10940 ciclos para 7331 Slices. / Asymmetric cryptographic primitives are essential to enable secure communications on public networks or public mediums. These cryptographic primitives can be deployed as software libraries or hardware coprocessors. Hardware coprocessors are mostly employed in Systems on Chip (SoC) scenarios, embedded devices, or application-specific servers. Available solutions based on RSA or Elliptic Curve Cryptography (ECC) are highly processing intensive because of the underlying extended precision modular arithmetic, and hence they are not available on the most energy constrained platforms. To provide asymmetric primitives in those restricted devices, we evaluate another asymmetric encryption scheme implementable with lightweight arithmetic, called McEliece. McEliece was proposed with binary Goppa codes during same year of RSA with public keys 50 times larger. Because of such large keys it has not gained as much attention as RSA or ECC. With the adoption of binary Quasi- Dyadic Goppa (QD-Goppa) codes it is possible to attain practical security levels with reasonably small keys. To evaluate a hardware implementation of this scheme, we investigate a scalable architecture that can be reconfigured according to project requirements. This architecture is suitable for all usual security levels, from 80 to 256-bit security, from the smallest unit to bigger ones. With our architecture implemented on a Spartan 3 FPGA for binary Goppa codes it is possible to decrypt in 5854 cycles with 4671 Slices, whilst in literature best results were in 10940 cycles with 7331 Slices.

Primitivas criptografias assimétricas são essenciais para conseguir comunicação segura numa rede ou meio público. Essas primitivas podem ser instaladas como bibliotecas de software ou como coprocessadores de hardware. Coprocessadores de hardware são muito utilizados em cenários como Systems on Chip (SoC), dispositivos embarcados ou servidores de aplicações específicas. Coprocessadores existentes baseados em RSA ou curvas ellipticas (ECC) fazem um processamento intenso por causa da aritmética modular de grande precisão, portanto não estão disponíveis em plataformas com quantidade de energia mais restrita. Para prover primitivas assimétricas para esses dispositivos, será avaliado um esquema de cifração assimétrica que utiliza artimética de pequena precisão, chamado McEliece. McEliece foi proposto com códigos de Goppa binários durante o mesmo ano que o RSA, porém com chaves públicas 50 vezes maiores. Por causa de chaves tão grandes ele não ganhou muita atenção como RSA e ECC. Com a adoção de códigos Quase-Diádicos de Goppa binários é possível obter níveis de segurança práticos com chaves relativamente pequenas. Para avaliar uma implementação em hardware para esse esquema, foi proposto uma arquitetura escalável que pode ser configurada de acordo com os requisitos do projeto. Essa arquitetura pode ser utilizada em todos os níveis de segurança, de 80 até 256 bits de segurança, da menor unidade até as maiores. Nossa arquitetura foi implementada na família de FPGAs Spartan 3 para códigos de Goppa binários, onde foi possível decifrar em 5854 ciclos com 4671 Slices, enquanto que na literatura os melhores resultados obtidos são de 10940 ciclos para 7331 Slices. / Asymmetric cryptographic primitives are essential to enable secure communications on public networks or public mediums. These cryptographic primitives can be deployed as software libraries or hardware coprocessors. Hardware coprocessors are mostly employed in Systems on Chip (SoC) scenarios, embedded devices, or application-specific servers. Available solutions based on RSA or Elliptic Curve Cryptography (ECC) are highly processing intensive because of the underlying extended precision modular arithmetic, and hence they are not available on the most energy constrained platforms. To provide asymmetric primitives in those restricted devices, we evaluate another asymmetric encryption scheme implementable with lightweight arithmetic, called McEliece. McEliece was proposed with binary Goppa codes during same year of RSA with public keys 50 times larger. Because of such large keys it has not gained as much attention as RSA or ECC. With the adoption of binary Quasi- Dyadic Goppa (QD-Goppa) codes it is possible to attain practical security levels with reasonably small keys. To evaluate a hardware implementation of this scheme, we investigate a scalable architecture that can be reconfigured according to project requirements. This architecture is suitable for all usual security levels, from 80 to 256-bit security, from the smallest unit to bigger ones. With our architecture implemented on a Spartan 3 FPGA for binary Goppa codes it is possible to decrypt in 5854 cycles with 4671 Slices, whilst in literature best results were in 10940 cycles with 7331 Slices.

Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-04-24T11:48:05Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-04-24T16:57:51Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) / Made available in DSpace on 2017-04-24T16:57:51Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) Previous issue date: 2016-10-21 / Nesta tese são propostos procedimentos para a construção de matrizes de verificação de paridade para codificação e decodificação de códigos LDPC (low-density paritycheck) na recuperação de bits apagados no canal com apagamentos em rajada. As matrizes de verificação de paridade são produzidas por concatenação das matrizes bases binárias justapostas por matrizes circulantes sendo de fácil implementação e de menor aleatoriedade. As matrizes bases são desenvolvidas a partir de fundamentos da álgebra e da geometria. Para demonstrar o potencial da técnica foi elaborado um conjunto de simulações que usa codificação de baixa complexidade, bem como o uso dos algoritmos soma e produto para recuperar os apagamentos. Foram gerados vários códigos LDPC, a partir das matrizes, e os resultados obtidos foram comparados com outros códigos LDPC obtidos da literatura. São ainda apresentados os resultados da simulação da recuperação de apagamentos resultantes da transmissão de uma imagem através de um canal ruidoso.partir das matrizes, e os resultados obtidos foram comparados com outros códigos LDPC obtidos da literatura. São ainda apresentados os resultados da simulação da recuperação de apagamentos resultantes da transmissão de uma imagem através de um canal ruidoso. / This thesis proposed procedures for the construction of parity check matrices for encoding and decoding of LDPC codes in the recovery of deleted bits in Burst Erasure Channel. The parity check matrices are produced by concatenation of binary bases matrices juxtaposed by circulating matrices are easy to implement and lower randomness. The base arrays are developed from the foundations of algebra and geometry. To demonstrate the potential of the technique, we developed a number of simulations using low complexity encoding as well as the sum-product algorithm. Several LDPC codes (matrices) were generated and the results were compared with other approaches. We also present the outcomes of erasure recovery simulations that result from the transmission of an image through a noisy channel.

Made available in DSpace on 2010-04-20T20:15:28Z (GMT). No. of bitstreams: 0 Previous issue date: 2001-03-29T00:00:00Z / A proposta deste trabalho é contribuir com a literatura existente sobre estratégias de marketing utilizadas por instituições financeiras, particularmente as corretoras de valores, de forma que estudos futuros possam aprofundá-la.

Orientadores: Paulo Roberto Brumatti, Fernando Eduardo Torres Orihuela / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:44:44Z (GMT). No. of bitstreams: 1 Melo_Nolmar_M.pdf: 705654 bytes, checksum: b8ecfe0cc3ffd2dd2f63bc813a9c4a8d (MD5) Previous issue date: 2006 / Resumo: O objetivo central desta dissertação foi o de apresentar os Códigos Geométricos de Goppa via métodos elementares que foram introduzidos por J. H. van Lint, R. Pellikaan e T. Hfhold por volta de 1998. Numa primeira parte da dissertação são apresentados os conceitos fundamentais sobre corpos de funções racionais de uma curva algébrica na direção de se definir os códigos de Goppa de maneira clássica, neste estudo nos baseamos principalmente no livro ¿Algebraic Function Fields and Codes¿ de H. Stichtenoth. A segunda parte inicia-se com a introdução dos conceitos de funções peso, grau e ordem que são fundamentais para o estudo dos Códigos de Goppa via métodos elementares de álgebra linear e de semigrupos, tal estudo foi baseado em ¿Algebraic geometry codes¿ de J. H. van Lint, R. Pellikaan e T. Hfhold.A dissertação termina com a apresentação de exemplos que ilustram os métodos elementares que nos referimos acima / Abstract: The central objective of this dissertation was to present the Goppa Geometry Codes via elementary methods which were introduced by J. H. van Lint, R. Pellikaan and T. Hfhold about 1998. On the first past of such dissertation are presented the fundamental concepts about fields of rational functions of an algebraic curve in the direction as to define the Goppa Codes on a classical manner. In this study we based ourselves mainly on the book ¿Algebraic Function Fields and Codes¿ of H. Stichtenoth. The second part is initiated with an introduction about the functions weight, degree and order which are fundamental for the study of the Goppa Codes throught elementary methods of linear algebra and of semigroups and such study was based on ¿Algebraic Geometry Codes¿ of J. h. van Lint, R. Pellikaan and T. Hfhold. The dissertation ends up with a presentation of examples which illustrate the elementary methods that we have referred to above / Mestrado / Algebra / Mestre em Matemática

Orientador: Jaime Portugheis / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T20:11:55Z (GMT). No. of bitstreams: 1 Cunha_DanielCarvalhoda_D.pdf: 2995961 bytes, checksum: 3bbce0e569994999c363151f6510cef1 (MD5) Previous issue date: 2006 / Resumo: Em varios sistemas de transmissão passa-faixa, uma recepção coerente satisfatória é dificil de ser alcancada. Para alguns destes sistemas, é comum supor que a rotaçãoo de fase introduzida pelo canal é constante durante um bloco de L simbolos e que ela varia de maneira independente de bloco a bloco. Este canal é denominado canal não-coerente de bloco. Investigamos a capacidade de um canal não-coerente de bloco utilizando a modulação M-APSK (do inglês, M-ary Amplitude Phase Shift Keying). Apresentamos a caracterização da distribuição de entrada que atinge a capacidade e obtivemos limitantes superiores e inferiores para a mesma. Adicionalmente, desenvolvemos um algoritmo que simultaneamente fornece a distribuição de entrada e os parametros da modulação M-APSK que maximizam a informação mutua com recepção coerente. A investigação da capacidade mostrou que o aumento de L faz a capacidade não-coerente convergir para a coerente. Alem disso, o uso de codificação diferencial torna a convergência mais rapida. Motivados por este comportamento, apresentamos um esquema de codificação eficiente em faixa. Este esquema é formado pela concatenação serial de um codigo LDPC (do ingles, Low-Density Parity Check ), um entrela¸cador e um codificador diferencial. Para o esquema apresentado, o receptor iterativo é descrito por um grafo-fator. Os desempenhos do esquema com diferentes tamanhos de codigos LDPC são comparados / Abstract: Coherent reception is not possible for many bandpass transmission systems. In some of these systems, it is commonly assumed that the unknown carrier phase rotation is constant over a block of L symbols and it is independent from block to block. This channel is denominated blockwise noncoherent channel. The blockwise noncoherent channel capacity using M-ary Amplitude and Phase Shift Keying (M-APSK) modulation is investigated. The characterization of the input distribution achieving capacity is presented. Upper and lower bounds to this capacity are derived. In addition, an algorithm for simultaneously computing the input distribution and the M-APSK constellation parameters which maximizes the mutual information with coherent reception is developed. The investigation of the capacity showed that as L increases, the noncoherent capacity converges to the coherent one. Besides that, the use of differential encoding makes this convergence faster. Motivated by this fact, a bandwidth efficient coding scheme is presented. This scheme is composed of a serial concatenation of a Low-Density Parity Check (LDPC) code, an interleaver, and a differential encoder. For this scheme, the iterative receiver is described by a factor graph. The scheme performances for different lengths of LDPC codes are compared. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Reginaldo Palazzo Jr / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-21T08:02:03Z (GMT). No. of bitstreams: 1 Silva_AntoniodeAndradee_D.pdf: 3080578 bytes, checksum: 358a40d30d6d9095e60812b8a9e0129a (MD5) Previous issue date: 1996 / Resumo: Neste trabalho apresentamos extensões de construções de códigos pertencentes à classe dos códigos geometricamente uniformes. São consideradas duas caracterizações de constelações de sinais casadas com grupos. Uma das caracterizações vem do uso de grupos não comutativos que são obtidos via o produto semidireto de um grupo comutativo por um grupo cíclico de ordem par. A outra caracterização vem do emprego de um algoritmo baseado no conceito da d-cadeia. Apresentamos uma construção de códigos multicamadas sobre o grupo Zq. Esses códigos são usados na construção multicamadas de empacotamentos esféricos, a qual é uma extensão da construção binária proposta por Costa e Silva e Palazzo em [10]. Como resultados, novos códigos de espaço Euclidiano e empacotamentos esféricos mais densos são apresentados. Em dimensões 68 e 72, novo recorde de densidades parece ter sido alcançado / Abstract: In this research we present extensions oí code constructions whose codes belong to the class oí geometrically uniíorm codes. We consider two characterizations oí signal sets matched to groups. The first characterization is derived írom a noncommutative group which is the semidirect product oí a commutative group by a cyclic group oí even order. The second characterization is derived írom an algorithm based on the concept of a d-chain. We propose a multilevel construction oí codes over the group Zq. These codes are used in the multilevel construction oí sphere packings, which is an extension oí Costa e Silva and Palazzo's binary construction [10]. As a result, new Euclidean-space codes and sphere packings are presented. In dimensions 68 and 72, new record oí densities appear to have been achieved. / Doutorado / Eletronica e Comunicações / Doutor em Engenharia Elétrica

Orientador: Marcelo Muniz Silva Alves / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-12T16:23:24Z (GMT). No. of bitstreams: 1 Ritter_Donizete_M.pdf: 621556 bytes, checksum: 2bf0368b784f3a2be59ca3c2552f4908 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho abordamos a teoria dos Códigos Corretores de Erros clássica e também os códigos sobre ordens parciais, com algumas comparações entre os dois casos. Enfocamos, particularmente, a definição de Alfabeto, a distância de Hamming, os códigos lineares e a definição de matriz geradora de um código; o estudo dos limitantes de Singleton e de Hamming, além de tratar dos Códigos de Hamming. Em relação aos Códigos em Conjuntos Parcialmente Ordenados, apresentamos a definição de ordens parciais, métricas sobre conjuntos ordenados, contagem dos elementos da "bola", resultados sobre Ideais e o Código de Hamming Estendido; estudamos o caso da ordem cadeia ("chain poset"), analisando os códigos de uma cadeia e os códigos de duas cadeias de mesmo comprimento e, por fim, nos dedicamos ao estudo das "Métricas POSET", que admitem códigos binários perfeitos de codi-mensão m, caracterizando assim os Códigos Posets m-corretores de erros. Nosso objetivo é apresentar um texto, acessível a alunos de graduação, que contemple a teoria básica dos Códigos Corretores de Erros, no entanto, forneça uma noção sobre os códigos sobre ordens parciais. / Abstract: In this work, we address the classical theory of error-correcting codes and the theory of codes over poset spaces, also known as poset codes, establishing comparisons between these two cases. In particular, we present the definition of alphabet, the Hamming distance, linear codes and the definition of a generating matrix for a linear code; we also present the Singleton and Hamming bounds, alongside with the Hamming codes. With respect to poset codes, we present the definitions of partial orders and of the poset metric, the counting of the number of elements in a ball in a poset space, some results on ideals in posets and the extended Hamming code; we study the chain poset case, analysing the cases of codes over a chain poset and codes over a union of two chains of the same length and, finally, we study the poset metrics that allow m-perfect binary codes of codimension m, thus characterizing these codes. Our aim is to present a text, accessible for undergraduates, that encompasses the basic theory of error-correcting codes and, nonetheless, also provides some notions on poset codes. / Mestrado / Teoria dos Erros / Mestre em Matemática

Orientador: Marcelo Firer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T06:58:11Z (GMT). No. of bitstreams: 1 Spreafico_MarcosViniciusPereira_M.pdf: 558857 bytes, checksum: a9d033bd1132fd1bc42fcb1aa2296ef5 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho fazemos uma apresentação dos espaços poset, introduzidos por Brualdi (1995), apresentamos os conceitos necessarios da teoria de conjuntos parcialmente ordenados e da teoria de codigos. Trabalhamos com uma questão de caráter amplo e estrutural deste contexto, o problema da determinação da ordem atraves da distribuição de pesos. A distribuição de pesos é essencialmente o conjunto das cardinalidades das esferas métricas e a pergunta que se coloca é em que medida este invariante determina a métrica em questão. Demonstramos que para as classes de codigos, cadeia, anticadeia, coroa e hierárquico, classes importantes no contexto da teoria de codigos, o problema possui uma resposta positiva e justificamos algumas conjecturas que relacionam este problema ao da reconstrução de grafos. / Abstract: In this work, we introduce the concept of poset codes (Brualdi - 1995) and in this context we study the weight distribution problem, presenting the necessary concepts of the partially ordered set and error correcting codes theory. The weight distribution is the cardinality of metric-spheres in finite dimensional vector space over a finite field endowed with a poset metric. The weight distribution problem asks for conditions to ensure that the weight distribution determines the metric. In this work we show that the weight distribution of some families of posets, namely the classes of anti-chain, chain, crown and hierarchical posets, determines the metric. We also show that the weight distribution determines some known invariants of posets. Finally, we present some conjectures relating the weight distribution problem and the reconstruction problem of graphs. / Mestrado / Mestre em Matemática