Universidade Federal de Viçosa - UFV
Centro de Ciências Exatas e Tecnológicas- CCE
Departamento de Matemática - DMA
Códigos Cı́clicos e Álgebra
Victor do Nascimento Martins
[email protected]
Marinês Guerreiro
[email protected]
RESUMO
A Teoria dos Códigos Corretores de Erros se apresenta de forma bastante dinâmica, envolvendo conhecimentos de várias áreas, o que torna motivador seu estudo. A Álgebra Abstrata é uma dessas áreas
e ao estudarmos os códigos sob o ponto de vista algébrico estamos mesclando conceitos da Matemática
Pura e da Aplicada. Neste trabalho objetivamos estudar a classe dos Códigos Cı́clicos. Para isso,
inicialmente, estudamos estruturas algébricas nas quais realizarı́amos estes. Fizemos um estudo da
teoria básica de códigos utilizando principalmente a Teoria dos Corpos Finitos. Em seguida passamos
pela Teoria dos Módulos a fim de compreendermos melhor a primeira estrutura que utilizarı́amos para
realizar os códigos cı́clicos: as Álgebras de Grupos. Finalizando as estruturas algébricas, vimos os
não-comutativos anéis de polinômios skew. Em posse de todo este conteúdo da Álgebra Abstrata
finalizamos nosso trabalho estudando códigos cı́clicos como ideais em álgebras de grupos e como ideais
em anéis de polinômios skew. Com isso vimos que os códigos skew-cı́clicos são uma generalização dos
mais comuns códigos cı́clicos e que existem ”mais”códigos do tipo skew.
INTRODUÇÃO
A utilização de informações digitalizadas, como assistir televisão, falar ao telefone ou ouvir
um CD mostram como os códigos corretores de erros participam do nosso cotidiano de inúmeras
formas. A Teoria dos Códigos é um campo de investigação atual e muito ativo, sendo pesquisado por
diversas áreas do conhecimento como Matemática, Computação, Engenharia Elétrica e Estatı́stica.
Essa teoria surgiu em 1948, com um trabalho do matemático C.E. Shanon do Laboratório Bell, uma
empresa norte americana de telefonia,
a partir principalmente de um questionamento do porquê das máquinas não localizarem a posição de um erro e corrigi-lo numa transmissão
de informações, já que essas podiam detectar um erro.
O que é um Código Corretor de Erros?
Um código corretor de erros é, em essência, um modo organizado de acrescentar algum dado
adicional a cada informação que se queira transmitir ou armazenar, que permita, ao recuperar a informação, detectar e corrigir erros.
O exemplo mais comum de um código corretor de erros é um idioma. Por exemplo, dado um
alfabeto A formado pelas 26 letras do alfabeto da Lı́ngua Portuguesa, o espaço em branco, o c cedilha
e as vogais acentuadas, uma palavra pode ser escrita como um elemento de A27 ( 27 é o comprimento
1
da palavra mais longa da Lı́ngua Portuguesa). Como o conjunto de todas as palavras da Lı́ngua
Portuguesa é um subconjunto próprio P de A27 , esse código é capaz de detectar e corrigir erros. Se,
por exemplo, ao escrevermos uma palavra emitimos a seqüência de letras “cathorro”, percebe-se que
houve um erro, pois esta seqüência não pertence a P e, dessa forma, a correção é feita substituindo
pela palavra de P que mais se assemelha a “cathorro”, que é “cachorro”.
EXEMPLO:
Vejamos um exemplo que ilustra a teoria. Suponhamos que temos um protótipo de um avião
controlado via um aparelho digital e que voe em oito direções distintas a saber: Leste, Oeste, Norte,
Sul, Nordeste, Sudeste, Noroeste e Sudoeste. As oito direçõ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 código à direita acima é o que chamamos de código
da
fonte.
Suponhamos que ao transmitirmos essa codificação o sinal no caminho sofra interferências. Por exemplo a mensagem 011 foi recebida como 010, ou seja, ao invés do avião ir na direção NORTE, ele vai
na direção NOROESTE. A teoria de Códigos Corretores de Erros trata de recodificar as palavras, de
modo a introduzir redundâncias que permitam detectar e corrigir erros. Assim, podemos modificar o
có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 código produzido na recodificação é chamado código
de
canal.
Suponhamos que ao tentarmos transmitir a palavra 110010 tenhamos introduzido um erro e a mensagem recebida seja 111010. Como esta palavra não pertence ao código detectamos o erro e daı́
procuramos a palavra do código “mais próxima”da recebida, que é a palavra enviada: 110010.
Esquema de Transmissão de Dados
Um exemplo importante da utilização de códigos é na transmissão de dados obtidos por satélites no
espaç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 pré-escolhidos e codificados como elementos de {0, 1}6, correspondente ao código da fonte. Esses vetores eram transmitidos sem nenhuma codificação de canal, pois o
2
transmissor era tão lento que levava oito horas para completar a transmissã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
resolução. O código da fonte foi mantido, mas, tirando-se partido do aumento da velocidade de transmissão de dados alcançada, foi possı́vel recodificar o código através de uma aplicação injetora de {0, 1}6
em {0, 1}32 , de modo que o código de canal resultante fosse capaz de detectar e corrigir até sete erros.
O sinal recebido era corrigido e decodificado utilizando-se a aplicação inversa, achando-se o elemento
de {0, 1}6 e, em seguida, o tom de cinza a ele correspondente. Este código é um membro particular
de uma famı́lia de códigos chamada de Códigos de Reed-Muller. Mais tarde, em 1979, a nave espacial
Voyager transmitiu imagens coloridas de Júpiter. O codificador da fonte usava 12 bits binários e o
codificador de canal usava 24 bits. Esse código foi chamado código de Golay e era capaz de corrigir
até três erros cometidos nos 24 bits de informação transmitidos.
Sabe-se atualmente que a utilização de mais estruturas algébricas sobre um código nos dá mais
informações a respeito do mesmo, bem como algoritmos de codificação e decodificação mais eficientes.
Neste trabalho estudamos um caso particular destes códigos: os códigos cı́clicos. Estes, por sua vez,
foram realizados sob duas perspectivas distintas: (i) como ideais em álgebras de grupo semisimples e
(ii) como ideais unilaterais em anéis de polinômios skew.
A fim de atingirmos nosso objetivo dividimos este trabalho em quatro partes:
No primeira fizemos uma breve revisão de conceitos básicos da Álgebra Abstrata, como anéis e corpos finitos. Na segunda vimos os conceitos iniciais da teoria de códigos. Nesta parte, além dos conceitos
vistos
na
primeira
parte
foi
necessário
um
conhecimento de conceitos básicos da Álgebra Linear. Na terceira etapa tratamos essencialmente do item
(i) citado acima. E na última etapa diz respeito ao item (ii).
OBJETIVOS E METODOLOGIA
Este projeto de iniciação cientı́fica teve como objetivo aprofundar o conhecimento do estudante
na área de Álgebra, especificamente estudando códigos cı́clicos como ideais em certas álgebras de grupo
semisimples e códigos skew cı́clicos como ideais em anéis de polinômios skew, além de compreender
métodos de codificação e decodificação dos mesmos.
Como metodologia de nosso trabalho foram dedicadas 16 horas semanais para desenvolver o estudo
orientado sobre os tópicos abordados no projeto, utilizando a bibliografia citada, e 4 horas semanais
para apresentar seminários a respeito de tópicos pré-selecionados pela orientadora.
REFERÊNCIAS BIBLIOGRÁFICAS
Referências
[1] A. Hefez e M.L.T. Vilela, Có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 , Anéis e Módulos, Publicações do IME-USP, São Paulo, 1972.
3
[6] T.Y. Lam, A First Course in Noncommutative Rings, Springer-Verlag New York, 1991.
[7] V. O. J. Luchetta, Códigos Cı́clicos como ideais em Álgebras de Grupos, Dissertação de
Mestrado, IME-USP, 2005.
4