A modified, single error-correcting, and double error detecting Hamming code, hereafter referred to as modified SEC-DED Hamming code, is proposed in this research. The code requires fewer logic gates to implement than the SEC-DED Hamming code. Also, unlike the popular Hsiao's code, the proposed code can determine the error in the received word from its syndrome location in the parity check matrix. A detailed analysis of the area and power utilization by the encoder and decoder circuits of the modified SEC-DED Hamming code is also discussed. Results demonstrate that this code is an excellent alternative to Hsiao's code as the area and power values are very similar. In addition, the ability to locate the error in the received word from its syndrome is also of particular interest. Primitive polynomials play a crucial role in the hardware realizations for error-correcting codes. This research describes an implementation of a scalable primitive polynomial circuit with coefficients in GF(2). The standard cell area and power values for various degrees of the circuit are analyzed. The physical design of a degree 6 primitive polynomial computation circuit is also provided. In addition to the codes, a background of the already existing SPX GCD computation algorithm is provided. Its implementation revealed that the combinational implementation of the SPX algorithm utilizes a significantly lesser area than Euclid's algorithm. The FSMD implementation of the SPX algorithm reduces both dynamic and leakage power consumption. The physical design of the GCD computation using the SPX algorithm is also provided.

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.

Un code de permutations G(n,d) un sous-ensemble C de Sym(n) tel que la distance de Hamming D entre deux éléments de C est supérieure ou égale à d. Dans cette thèse, le groupe des isométries de (Sym(n),D) est déterminé et il est prouvé que ces isométries sont des automorphismes du schéma d'association induit sur Sym(n) par ses classes de conjugaison. Ceci mène, par programmation linéaire, à de nouveaux majorants de la taille maximale des G(n,d) pour n et d fixés et n compris entre 11 et 13. Des algorithmes de génération avec rejet d'objets isomorphes sont développés. Pour classer les G(n,d) non isométriques, des invariants ont été construits et leur efficacité étudiée. Tous les G(4,3) et les G(5,4) ont été engendrés à une isométrie près, il y en a respectivement 61 et 9445 (dont 139 sont maximaux et décrits explicitement). D’autres classes de G(n,d) sont étudiées. A permutation code G(n,d) is a subset C of Sym(n) such that the Hamming distance D between two elements of C is larger than or equal to d. In this thesis, we characterize the isometry group of the metric space (Sym(n),D) and we prove that these isometries are automorphisms of the association scheme induced on Sym(n) by the conjugacy classes. This leads, by linear programming, to new upper bounds for the maximal size of G(n,d) codes for n and d fixed and n between 11 and 13. We develop generating algorithms with rejection of isomorphic objects. In order to classify the G(n,d) codes up to isometry, we construct invariants and study their efficiency. We generate all G(4,3) and G(4,5)codes up to isometry; there are respectively 61 and 9445 of them. Precisely 139 out of the latter codes are maximal and explicitly described. We also study other classes of G(n,d)codes.

The Turán problem is a fundamental problem in extremal graph theory. It asks what the maximum number of edges a given graph G can have, not containing some forbidden graph H, and is solved using the Turán number ex(n,H), density π(H) and graph Tr(n). Turán's theorem tells us that the Turán graph Tr(n) is the largest Kr+1-free simple graph on n vertices. This paper is an overview of Turán problems for cliques Kn, hypercubes Qn and Hamming graphs H(s,d). We end it by proving a new result we call "the layer theorem", solving the Hamming-Turán problem using a method of creating layers of vertices in a graph. This theorem gives a lower bound for the Hamming-relative Turán density as follows: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> for the forbidden graph F stretching over t layers and r = χ(F). / Turán-problemet är det fundamentala problemet inom extremal grafteori. Det ställer frågan vad det maximala antalet kanter en given graf G kan ha utan att innehålla någon förbjuden graf H, och löses med hjälp av Turán-talet ex(n,H), -densiteten π(H) and -grafen Tr(n). Turáns sats säger oss att Turán-grafen Tr(n) är den största Kr+1-fria enkla grafen på n hörn. Denna uppsats är en överblick av Turán-problem i klickar Kn, hyperkuber Qn och Hamming-grafer H(s,d). Vi avslutar den med att bevisa ett nytt resultat som vi kallar "lagersatsen", vilket löser Hamming-Turán-problemet med hjälp av en metod som skapar lager av hörnen i en graf. Lagersatsen ger en undre gräns för den Hamming-relativa Turán-densiteten enligt följande: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> där <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> för den förbjudna grafen F som sträcker sig över t lager samt r = χ(F).

Orientador: Hugo Enrique Hernández Figueroa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T09:35:55Z (GMT). No. of bitstreams: 1 Duplat_DanielNascimento_M.pdf: 6130170 bytes, checksum: a8ec6733cbf973341a611dbeb5f31f55 (MD5) Previous issue date: 2010 / Resumo: Este trabalho trata do desenvolvimento teórico e computacional de um arranjo de antenas de grande comprimento elétrico com grande aplicabilidade em radares e sistemas de sensoriamento que utilizam distribuições de potência específicas. São abordados a síntese do padrão de radiação do arranjo, a escolha do número de antenas e o desenvolvimento da rede de alimentação do sistema. De maneira geral, o projeto pode ser dividido em duas partes: cálculo dos parâmetros do arranjo de antenas e desenvolvimento do sistema de alimentação do arranjo. Na primeira parte, a partir da escolha de um diagrama de radiação específico, determina-se o número de antenas e a amplitude e fase de campo eletromagnético que cada antena do arranjo deve receber a fim de gerar o diagrama de radiação necessário. Para tal, adota-se uma distribuição de amplitudes do tipo Hamming adaptada às especificações do projeto e uma distribuição de fase uniforme. Na segunda parte, desenvolve-se um sistema de alimentação para o arranjo de antenas que possibilita a distribuição da energia obedecendo à distribuição de amplitude e fase do campo determinada na fase anterior. O sistema proposto utiliza tecnologia de linhas de fita montada num substrato de poliestireno expandido, que agrega não somente baixas perdas ao sistema de distribuição, mas também baixos custo e peso. É possível verificar, portanto, que o desenvolvimento de um arranjo de antenas com comprimento elétrico muito maior do que o comprimento de onda de operação é um projeto que agrega conhecimentos não somente de antenas e suas características, mas também o conhecimento de arranjos de antenas e ponderação de amplitudes, bem como seus efeitos no diagrama de radiação do arranjo. Contudo, o desenvolvimento deste sistema implica na utilização de sistemas de guiamento eletromagnético que possibilitem a transmissão de energia agregando baixo custo, baixas perdas, e alta eficiência. / Abstract: This work deals with theoretical and computational development of an antenna array of large electrical length with wide application in radar and sensing systems using specific power distribution. The project describes the process from the synthesis of radiation pattern, the choice of the number of antennas and the development of the power supply system. Overall, the project can be divided into two parts: calculation of parameters of the antenna array and development of the power system. In the first part, the number of antennas and the amplitude and phase of the electromagnetic field that each antenna needs are calculated to generate the required radiation pattern. To this end, we adopt a distribution of amplitudes of Hamming type (Hamming weighting) adapted to the project specifications and a uniform phase distribution. In the second part, the power system to the antenna array is developed. This supply system enables the distribution of energy obeying the distribution of amplitude and phase of the field specified in the previous part. The proposed system uses striplines mounted on a substrate of expanded polystyrene, which combines low-losses, low-cost and lightweight. / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

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.

Fundação de Amparo a Pesquisa do Estado de Minas Gerais / In this work, we study geometric Goppa codes and present several results on the so-called generalized Hamming distances. In the particular case of Hermitian codes we present precise results for the first, second and third generalized distances, for almost all Goppa codes supported on one point. / Neste trabalho estudamos códigos de Goppa e apresentamos diversos resultados sobre as assim chamadas distâncias generalizadas de Hamming. No caso particular de códigos Hermitianos, apresentamos resultados exatos para a primeira, segunda e terceira distâncias generalizadas de Hamming, considerando quase todos os códigos suportados em um ponto. / Mestre em Matemática

Orientador: Marcelo Firer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-23T13:47:51Z (GMT). No. of bitstreams: 1 Lemes_LeandroCruvinel_D.pdf: 1250342 bytes, checksum: e1a6a639b2a96ae11f0c70d7507040aa (MD5) Previous issue date: 2013 / Resumo: Considerando canais discretos, sem memória e com apagamento, obtemos limitantes superiores e inferiores para as probabilidades de erro de decodificação e de ocorrências de ambiguidade de códigos corretores de erro lineares. Os limitantes dependem da hierarquia de pesos e dos espectros generalizados e melhoram os limitantes conhecidos. Encontramos expressões exatas para essas probabilidades nos casos em que o código é AMDS ou MDS / Abstract: Considering an erasure channel, we improve upper and lower bounds for error decoding and ambiguity probabilities of linear error-correcting codes. The given bounds depend on the generalized weight hierarchy and spectrum of a code. We find explicit formulae in the case of AMDS and MDS codes / Doutorado / Matematica / Doutor em Matemática

Orientador: Paulo Roberto Brumatti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T19:35:36Z (GMT). No. of bitstreams: 1 Negreiros_DiogoBrunoFernandes_M.pdf: 5674415 bytes, checksum: bdd28225d3cc5505f91fd61e797f2794 (MD5) Previous issue date: 2011 / Resumo: Este texto tem como objetivo o estudo de um tipo de código que possui relações com as teorias de curvas algébricas e de formas quadráticas. Começaremos introduzindo as definições e resultados sobre as três teorias que serão necessárias a este estudo. Depois apresentaremos os códigos a serem estudados bem como as relações entre seus sub-códigos e curvas algébricas e entre suas palavras e formas quadráticas. Observando que sub-códigos de peso mais baixo correspondem a curvas com mais pontos, nos dedicaremos a obter um processo para a descoberta de sub-códigos de peso mínimo dentro deste tipo de código. Tal processo será possível através de investigações sobre as formas quadráticas associadas a palavras. Finalizaremos com exemplos de aplicações do processo em alguns códigos, o que permite também calcular seus pesos de Hamming generalizados de ordem mais baixa / Abstract: This text's objective is the study of a kind of code wich has relations with the theories of algebraic curves and quadratic forms. We start by introducing definitions and results about the three theories we will need in such study. Later, we present the codes wich will be studied along with relations between its subcodes and algebraic curves and between its words and quadratic forms. Noting that lower weight subcodes correspond to curves with more points, we research a process to find minimum weight subcodes in this kind of code. This process will be possible through investigations on the quadratic forms related to words. Finally we set examples of applications of the process on some codes, and that gives us their lower order generalized Hamming weights / Mestrado / Matematica / Mestre em Matemática

The hardware as well as software communities have recently experienced a shift towards mitigating bit flips issues in software, rather than completely mitigating only in hardware. For this software error mitigation, arithmetic error coding schemes like AN coding are increasingly applied because arithmetic operations can be directly executed without decoding and bit flip detection is provided in an end-to-end fashion. In this case, each encoded data word is computed by multiplying the original data word with a constant integer value A. To reliably detect b bit flips in each code word, the value A has to be well-chosen, so that a minimum Hamming distance of b + 1 can be guaranteed. However, the value A depends on the data word length as well as on the desired minimum Hamming distance. Up to now, a very expensive brute force approach for computation of the value for A is applied. To tackle that in a more efficient way, we present a lower bound-oriented approach for this calculation in this paper.