Código binário de Golay

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Código Binário de Golay)
Ir para: navegação, pesquisa
Código binário estendido de Golay
BinaryGolayCode.svg
A matriz geradora do código
Origem do nome Marcel J. E. Golay
Classificação
Tipo Código de bloco linear
Comprimento do bloco 24
Comprimento da mensagem 12
Taxa 12/24 = 0.5
Distância 8
Tamanho do alfabeto 2
Notação código
Código perfeito binário de Golay
Origem do nome Marcel J. E. Golay
Classificação
Tipo Código de bloco linear
Comprimento do bloco 23
Taxa 12/23 ~ 0.522
Distância 7
Tamanho do alfabeto 2
Notação código

Em matemática e engenharia eletrônica, um código binário de Golay é um tipo de código corretor de erros linear utilizado na comunicações digitais. O código binário de Golay, juntamente com o código ternário de Golay, está intimamente relacionado à teoria de grupos finitos esporádicos em matemática.[1] Estes códigos são assim denominados em homenagem a Marcel J. E. Golay que os introduziu em um trabalho de 1949,[2] o qual foi considerado por E. R. Berlekamp, a "melhor página única publicada" em teoria de códigos.[3]

Há dois códigos de Golay binários intimamente relacionados. O código binário estendido de Golay, G24 (algumas vezes chamado apenas de "código de Golay" na teoria de grupos finitos) codifica 12 bits de dados em uma palavra de 24-bits, de tal forma que qualquer erro de 3-bits pode ser corrigido ou qualquer erro de 7 bits pode ser detectado. O outro, o código binário perfeito de Golay, G23, tem palavras-código de comprimento 23 e é obtido a partir do código binário estendido de Golay pela exclusão da posição de uma coordenada (reciprocamente, o código binário estendido de Golay é obtido a partir do código binário perfeito de Golay pela adição de um bit de paridade). Na notação padrão de códigos os códigos possuem parâmetros [24, 12, 8] e [23, 12, 7], correspondendo ao comprimento das palavras-código, a dimensão do código, e a distância de Hamming mínima entre duas palavras-código, respectivamente.

Definição matemática[editar | editar código-fonte]

Em termos matemáticos, o código binário estendido de Golay G24 consiste em um subespaço vetorial W de dimensão 12 do espaço V=F224 das palavras de 24-bits tais que quaisquer dois elementos distintos de W diferem em pelo menos 8 coordenadas. W é chamado de um código linear, porque é um espaço vetorial. Ao todo, W compreende 4096 = 212 elementos.

  • Os elementos de W são chamados de palavras-código. Eles também podem ser descritos como subconjuntos de um conjunto de 24 elementos, onde a adição é definida tomando-se a diferença simétrica dos subconjuntos.
  • No código binário estendido de Golay, todas as palavras-código têm pesos de Hamming iguais a 0, 8, 12, 16 ou 24. As palavras-código de peso 8 são chamadas de octads e as palavras-código de peso 12 são chamadas de dodecads.
  • As octads do código G24 são elementos do sistema de Steiner S(5,8,24). Há 759 = 3*11*23 octads e 759 complementos das mesmas. Segue-se que há 2576 = 24*7*23 dodecads.
  • Duas octads se cruzam (têm 1's em comum) em 0, 2 ou 4 coordenadas de suas representações como vetores binários (estes são os possíveis tamanhos da intersecção na representação por subconjuntos). Uma octad e uma dodecad se intersectam em 2, 4 ou 6 coordenadas.
  • W é único, a menos de uma mudança nos nomes das coordenadas.

O código binário de Golay, G23 é um código perfeito. Isto é, as esferas de raio três em torno de palavras-código, formam uma partição do espaço vetorial. G23 é um subespaço de dimensão 12 do espaço F223.

O grupo de automorfismos do código binário perfeito de Golay, G23, é o grupo de Mathieu O grupo de automorfismos do código binário estendido de Golay é o grupo de Mathieu de ordem 210*33*5*7*11*23. é transitivo em octads e em dodecads. Os outros grupos de Mathieu ocorrem como estabilizadores de um ou vários elementos de W.

Construções[editar | editar código-fonte]

  • Código Lexicográfico: Ordene os vetores de V lexograficamente (isto é, interprete-os como inteiros binários de 24 bits sem sinal e utilize a ordem usual). Começando com w1 = 0, defina w2, w3, ..., w12 pela regra segundo a qual wn é o menor inteiro que difere de todas as combinações lineares dos elementos anteriores em, pelo menos, oito coordenadas. Então W pode ser definido como o espaço gerado por w1, ..., w12.
  • Código de resíduo quadrático: Considere o conjunto N dos não-resíduos quadráticos (mod 23). Este é um subconjunto de 11 elementos do grupo cíclico Z/23Z. Considere as translações t+N deste subconjunto. Complete cada translação com um elemento ∞, formando um conjunto St de 12 elementos. Então, chamando os elementos da base de V de 0, 1, 2, ..., 22 e ∞, W pode ser definido como o espaço gerado pelas palavras St junto com a palavra que consiste de todos os vetores da base. (O código perfeito é obtido deixando de fora o ∞.)
  • Como um código cíclico: o código perfeito G23 pode ser construído através da fatoração de  sobre o corpo binário GF(2):
    Ele é o código gerado por  [4] Qualquer um dos fatores irredutíveis de grau 11 pode ser usado para gerar o código.[5]
  • A construção de Turyn de 1967, "Uma Simples Construção do Código Binário de Golay," que começa a partir do código de Hamming de comprimento 8 e não usar os resíduos quadráticos mod 23.[6]
  • A partir do Sistema Steiner S(5,8,24), que consiste de 759 subconjuntos de um conjunto de 24 elementos. Se o suporte de cada subconjunto for interpretado como uma palavra-código binária de comprimento 24 (com peso e Hamming 8), estas são as "octads" no código binário de Golay. Todo o código de Golay pode ser obtido tomando repetidamente a diferença simétrica de subconjuntos, isto é, a adição binária. Uma maneira mais fácil de escrever o sistema Steiner (ou as octads) é o Miracle Octad Generator (MOG) de R. T. Curtis, que utiliza uma certa correspondência 1:1 entre as 35 partições de um conjunto de 8 elementos e as 35 partições do espaço vetorial finito em 4 planos. [7] Hoje em dia, muitas vezes é usada a abordagem compacta de Conway's hexacode, que usa uma matriz 4×6 de células quadradas.
  • As posições vencedoras no jogo matemático de Mogul: uma posição em Mogul é uma linha de 24 moedas. Cada rodada consiste de virar entre uma e sete moedas de tal forma que a moeda virada mais à esquerda vá de cara a coroa. As posições perdedoras são aquelas em que não há nenhum movimento permitido. Se as caras forem interpretadas como 1 e as coroas como 0, então a transição para uma palavra-código do código binário estendido de Golay garante que será possível forçar uma vitória.
  • Uma matriz geradora para o código binário de Golay é I A, onde I é a matriz identidade 12×12, e A é o complemento da matriz de adjacências do icosaedro.

Uma representação conveniente[editar | editar código-fonte]

É conveniente usar o formato MOG, com coordenadas em uma matriz de 4 linhas e 6 colunas. A adição é o cálculo da diferença simétrica. Todas as 6 colunas têm a mesma paridade, que é igual a da linha superior.

Uma partição das 6 colunas em 3 pares de colunas adjacentes constitui um trio. Esta é uma partição em 3 conjuntos de octads. Um subgrupo PSL(2,7) x S3 de um subgrupo trio de M24 é útil para gerar uma base. PSL(2,7) permuta as octads internamente, em paralelo. S3 permuta as 3 octads como um todo.

A base começa com octad T:

0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

e 5 octads semelhantes. A soma N de todas as 6 palavras-código consiste exclusivamente de uns. A adição de N com uma palavra-código produz o seu complemento.

Griess (p. 59) usa a rotulagem:

∞ 0 |∞ 0 |∞ 0
3 2 |3 2 |3 2
5 1 |5 1 |5 1
6 4 |6 4 |6 4

PSL(2,7) é, naturalmente, o grupo linear racional gerado por (0123456) e (0∞)(16)(23)(45). 7-o ciclo atua no T dar um subespaço incluindo também a base de elementos

0 1 1 0 1 0
0 0 0 0 0 0
0 1 0 1 0 1
1 1 0 0 0 0

e

0 1 1 0 1 0
0 1 0 1 0 1
1 1 0 0 0 0
0 0 0 0 0 0

O subespaço de dimensão 7 resultante tem um espaço quociente de dimensão 3 ignorando as últimas 2 octads.

Existem outras 4 palavras-código de estrutura semelhante que completam a base de 12 de palavras-código para esta representação de W.

Deve ser observado que W tem um subespaço de dimensão 4, simétrico sob PSL(2,7) x S3, gerado por N e 3 dodecads formadas de subconjuntos de {0,3,5,6}, {0,1,4,6}, e {0,1,2,5}.

Aplicações práticas dos códigos de Golay[editar | editar código-fonte]

Missões da NASA no espaço profundo[editar | editar código-fonte]

As naves espaciais Voyager 1 e 2 precisavam transmitir centenas de fotos coloridas de Júpiter e Saturno nos seus sobrevoos de 1979, 1980 e 1981 através de uma banda de telecomunicações restrita.

  • A transmissão de imagens coloridas exigia três vezes a quantidade de dados de imagens em preto e branco, por isso foi feita a troca do código de Hadamard, que era usado para transmitir as imagens em preto e branco, pelo código de Golay (24,12,8). [8]
  • Este código de Golay só corrige três erros, mas pode ser transmitido em uma taxa de dados bem mais alta do que o código de Hadamard que era usado durante a missão Mariner.

Comunicações de rádio[editar | editar código-fonte]

Os novos[quando?] padrões do governo americano para o estabelecimento automático de ligação em sistemas de rádio de alta frequência, especificam o uso de um código de bloco estendido de Golay (24,12) para correção antecipada de erros (FEC).

  • O código estendido de Golay (24,12) especificado é um bloco de código (24,12).
  • Este código codifica 12 bits de dados para produzir palavras-código de 24-bits.
  • Além disso, é um código sistemático, o que significa que os 12 bits de dados estão presentes de forma inalterada nas palavras-código.

A distância de Hamming mínima entre duas palavras-código (o número de bits em que qualquer par de palavras difere) é oito.

Ver também[editar | editar código-fonte]

  • Sanguessuga lattice

Notas[editar | editar código-fonte]

  1. See Thompson 1983
  2. Golay (1949)
  3. Berlekamp, E.R. (1974), Key Papers in the Development of Coding Theory, I.E.E.E. Press, p. 4 
  4. Roman 1992, p. 324 Example 7.4.3
  5. Pless 1998, p. 114
  6. Turyn 1967, Section VI
  7. http://finitegeometry.org/sc/24/MOG.html
  8. http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf

Referências[editar | editar código-fonte]