Universidade Federal de Viçosa - UFV Centro de Ciências Exatas e Tecnológicas- CCE Departamento de Matemática - DMA Códigos Cı́clicos e Álgebra Victor do Nascimento Martins [email protected] Marinês Guerreiro [email protected] RESUMO A Teoria dos Códigos Corretores de Erros se apresenta de forma bastante dinâmica, envolvendo conhecimentos de várias áreas, o que torna motivador seu estudo. A Álgebra Abstrata é uma dessas áreas e ao estudarmos os códigos sob o ponto de vista algébrico estamos mesclando conceitos da Matemática Pura e da Aplicada. Neste trabalho objetivamos estudar a classe dos Códigos Cı́clicos. Para isso, inicialmente, estudamos estruturas algébricas nas quais realizarı́amos estes. Fizemos um estudo da teoria básica de códigos utilizando principalmente a Teoria dos Corpos Finitos. Em seguida passamos pela Teoria dos Módulos a fim de compreendermos melhor a primeira estrutura que utilizarı́amos para realizar os códigos cı́clicos: as Álgebras de Grupos. Finalizando as estruturas algébricas, vimos os não-comutativos anéis de polinômios skew. Em posse de todo este conteúdo da Álgebra Abstrata finalizamos nosso trabalho estudando códigos cı́clicos como ideais em álgebras de grupos e como ideais em anéis de polinômios skew. Com isso vimos que os códigos skew-cı́clicos são uma generalização dos mais comuns códigos cı́clicos e que existem ”mais”códigos do tipo skew. INTRODUÇÃO A utilização de informações digitalizadas, como assistir televisão, falar ao telefone ou ouvir um CD mostram como os códigos corretores de erros participam do nosso cotidiano de inúmeras formas. A Teoria dos Códigos é um campo de investigação atual e muito ativo, sendo pesquisado por diversas áreas do conhecimento como Matemática, Computação, Engenharia Elétrica e Estatı́stica. Essa teoria surgiu em 1948, com um trabalho do matemático C.E. Shanon do Laboratório Bell, uma empresa norte americana de telefonia, a partir principalmente de um questionamento do porquê das máquinas não localizarem a posição de um erro e corrigi-lo numa transmissão de informações, já que essas podiam detectar um erro. O que é um Código Corretor de Erros? Um código corretor de erros é, em essência, um modo organizado de acrescentar algum dado adicional a cada informação que se queira transmitir ou armazenar, que permita, ao recuperar a informação, detectar e corrigir erros. O exemplo mais comum de um código corretor de erros é um idioma. Por exemplo, dado um alfabeto A formado pelas 26 letras do alfabeto da Lı́ngua Portuguesa, o espaço em branco, o c cedilha e as vogais acentuadas, uma palavra pode ser escrita como um elemento de A27 ( 27 é o comprimento 1 da palavra mais longa da Lı́ngua Portuguesa). Como o conjunto de todas as palavras da Lı́ngua Portuguesa é um subconjunto próprio P de A27 , esse código é capaz de detectar e corrigir erros. Se, por exemplo, ao escrevermos uma palavra emitimos a seqüência de letras “cathorro”, percebe-se que houve um erro, pois esta seqüência não pertence a P e, dessa forma, a correção é feita substituindo pela palavra de P que mais se assemelha a “cathorro”, que é “cachorro”. EXEMPLO: Vejamos um exemplo que ilustra a teoria. Suponhamos que temos um protótipo de um avião controlado via um aparelho digital e que voe em oito direções distintas a saber: Leste, Oeste, Norte, Sul, Nordeste, Sudeste, Noroeste e Sudoeste. As oito direções podem ser codificadas como elementos de {0, 1} × {0, 1} × {0, 1}, da seguinte forma: LESTE OESTE NORTE SUL - 000 - 001 - 011 - 100 NORDESTE - 110 SUDESTE - 101 NOROESTE - 010 SUDOESTE - 111 O código à direita acima é o que chamamos de código da fonte. Suponhamos que ao transmitirmos essa codificação o sinal no caminho sofra interferências. Por exemplo a mensagem 011 foi recebida como 010, ou seja, ao invés do avião ir na direção NORTE, ele vai na direção NOROESTE. A teoria de Códigos Corretores de Erros trata de recodificar as palavras, de modo a introduzir redundâncias que permitam detectar e corrigir erros. Assim, podemos modificar o código para: LESTE − 000 − 000000 OESTE − 001 − 001011 NORTE − 011 − 011100 SUL − 100 − 100101 NORDESTE − 110 − 110010 SUDESTE − 101 − 101110 NOROESTE − 010 − 010111 SUDOESTE − 111 − 111001 O novo código produzido na recodificação é chamado código de canal. Suponhamos que ao tentarmos transmitir a palavra 110010 tenhamos introduzido um erro e a mensagem recebida seja 111010. Como esta palavra não pertence ao código detectamos o erro e daı́ procuramos a palavra do código “mais próxima”da recebida, que é a palavra enviada: 110010. Esquema de Transmissão de Dados Um exemplo importante da utilização de códigos é na transmissão de dados obtidos por satélites no espaço. Em 1965, a nave espacial Mariner 4 transmitiu 22 fotos em preto e branco de Marte usando o seguinte sistema: cada foto foi decomposta em 200 × 200 elementos de imagem e, a cada elemento, foi atribuı́do um dos 64 tons de cinza pré-escolhidos e codificados como elementos de {0, 1}6, correspondente ao código da fonte. Esses vetores eram transmitidos sem nenhuma codificação de canal, pois o 2 transmissor era tão lento que levava oito horas para completar a transmissão de uma foto. Em 1972, a nave espacial Mariner 9 transmitiu novas imagens de Marte. Dessa vez cada imagem foi decomposta em 700 × 832 elementos, aumentando consideravelmente a resolução. O código da fonte foi mantido, mas, tirando-se partido do aumento da velocidade de transmissão de dados alcançada, foi possı́vel recodificar o código através de uma aplicação injetora de {0, 1}6 em {0, 1}32 , de modo que o código de canal resultante fosse capaz de detectar e corrigir até sete erros. O sinal recebido era corrigido e decodificado utilizando-se a aplicação inversa, achando-se o elemento de {0, 1}6 e, em seguida, o tom de cinza a ele correspondente. Este código é um membro particular de uma famı́lia de códigos chamada de Códigos de Reed-Muller. Mais tarde, em 1979, a nave espacial Voyager transmitiu imagens coloridas de Júpiter. O codificador da fonte usava 12 bits binários e o codificador de canal usava 24 bits. Esse código foi chamado código de Golay e era capaz de corrigir até três erros cometidos nos 24 bits de informação transmitidos. Sabe-se atualmente que a utilização de mais estruturas algébricas sobre um código nos dá mais informações a respeito do mesmo, bem como algoritmos de codificação e decodificação mais eficientes. Neste trabalho estudamos um caso particular destes códigos: os códigos cı́clicos. Estes, por sua vez, foram realizados sob duas perspectivas distintas: (i) como ideais em álgebras de grupo semisimples e (ii) como ideais unilaterais em anéis de polinômios skew. A fim de atingirmos nosso objetivo dividimos este trabalho em quatro partes: No primeira fizemos uma breve revisão de conceitos básicos da Álgebra Abstrata, como anéis e corpos finitos. Na segunda vimos os conceitos iniciais da teoria de códigos. Nesta parte, além dos conceitos vistos na primeira parte foi necessário um conhecimento de conceitos básicos da Álgebra Linear. Na terceira etapa tratamos essencialmente do item (i) citado acima. E na última etapa diz respeito ao item (ii). OBJETIVOS E METODOLOGIA Este projeto de iniciação cientı́fica teve como objetivo aprofundar o conhecimento do estudante na área de Álgebra, especificamente estudando códigos cı́clicos como ideais em certas álgebras de grupo semisimples e códigos skew cı́clicos como ideais em anéis de polinômios skew, além de compreender métodos de codificação e decodificação dos mesmos. Como metodologia de nosso trabalho foram dedicadas 16 horas semanais para desenvolver o estudo orientado sobre os tópicos abordados no projeto, utilizando a bibliografia citada, e 4 horas semanais para apresentar seminários a respeito de tópicos pré-selecionados pela orientadora. REFERÊNCIAS BIBLIOGRÁFICAS Referências [1] A. Hefez e M.L.T. Vilela, Códigos Corretores de Erros, Rio de Janeiro, IMPA, 2002. [2] C. P. Milies and S. K. Sehgal, An Introduction to Group Rings, Kluwer Academic Publishers, Dordrecht, 2002. [3] D. Boucher, F. Ulmer, Coding with skew polynomial rings, Preprint. 2007 [4] D. Boucher, W. Geiselmann, F. Ulmer, Skew - cyclic codes, Applied Algebra in Engineering, Communication and Computing 18, 379 - 389. 2007. [5] F. C. P. Milies , Anéis e Módulos, Publicações do IME-USP, São Paulo, 1972. 3 [6] T.Y. Lam, A First Course in Noncommutative Rings, Springer-Verlag New York, 1991. [7] V. O. J. Luchetta, Códigos Cı́clicos como ideais em Álgebras de Grupos, Dissertação de Mestrado, IME-USP, 2005. 4
Download
