People rely on the ability to transmit information over channels of communication that aresubject to noise and interference. This makes the ability to detect and recover from errorsextremely important. Coding theory addresses this need for reliability. A fundamentalquestion of coding theory is whether and how we can correct the errors in a message thathas been subjected to interference. One answer comes from structures known as errorcorrecting codes.A well studied parameter associated with a code is its covering radius. The coveringradius of a code is the smallest radius such that every vector in the Hamming space of thecode is contained in a ball of that radius centered around some codeword. Covering radiusrelates to an important decoding strategy known as nearest neighbor decoding.The multicovering radius is a generalization of the covering radius that was proposed byKlapper [11] in the course of studying stream ciphers. In this work we develop techniques forfinding the multicovering radius of specific codes. In particular, we study the even weightcode, the 2-error correcting BCH code, and linear codes with covering radius one.We also study questions involving the complexity of finding the multicovering radius ofcodes. We show: Lower bounding the m-covering radius of an arbitrary binary code is NPcompletewhen m is polynomial in the length of the code. Lower bounding the m-coveringradius of a linear code is Σp2-complete when m is polynomial in the length of the code. IfP is not equal to NP, then the m-covering radius of an arbitrary binary code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time. Note that the case when m = 1 was also previouslyunknown. If NP is not equal to Σp2, then the m-covering radius of a linear code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time.

Made available in DSpace on 2014-07-29T16:02:17Z (GMT). No. of bitstreams: 1 SILVANA DA SILVA RODRIGUES.pdf: 983315 bytes, checksum: 17ccfa7762b3ec7758b0c81b7ca259bf (MD5) Previous issue date: 2011-01-28 / The main purpose of this dissertation was to construct lower and upper bounds for the cardinality of the error correcting codes for constant-weight, contained in the vector space Fn 3 , where F3 is a field with three elements, knowing parameters such as length and minimum distance code. We present the main results of linear algebra necessary to develop the theory of codes and then the fundamental concepts of more practical class of codes, the linear error correcting codes. We state the Totobola problem and the Football problem, relating them to the theory of codes and present some bounds for the "covering radius problem"for r = 1 , some values of n. In the last chapter, we conclude the work with some examples that illustrate bounds of coverings for Fn 3 , with r = 2 and 3, and the generalization of the problem, where we present the binary covering radius problem, the case of multiple coverages and the extension of the idea, citing bounds for the cardinality of the codes contained in the vector space over a finite field with any arbitrary number of elements. / O principal objetivo desta dissertação foi construir limitantes inferiores e superiores para o número de elementos de um código corretor de erros de peso constante, contido no espaço vetorial Fn 3 , onde F3 é um corpo contendo três elementos, a partir de parâmetros como comprimento e distância mínima do código. Apresentamos os principais resultados da álgebra linear necessários ao desenvolvimento da teoria de códigos e em seguida, os conceitos fundamentais da classe de códigos mais conhecida na prática: os códigos lineares. Definimos os problemas do totobola e da piscina de futebol e a relação de ambos, com a teoria de códigos e com o problema do raio de cobertura. Construímos limitantes para o problema do raio de cobertura para r = 1, a partir da variação de n, e no último capítulo o trabalho é finalizado com a apresentação de exemplos que ilustram limitantes de cobertura para Fn 3 , com r = 2 e 3 e a generalização do assunto, onde apresentamos o problema binário do raio de cobertura, o caso das múltiplas coberturas e a extensão da idéia, citando limitantes para o número de elementos de códigos contidos em espaços vetoriais sobre um corpo finito contendo uma quantidade qualquer de elementos.