# Código binário de Golay

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. Estes códigos são assim denominados em homenagem a Marcel J. E. Golay que os introduziu em um trabalho de 1949, o qual foi considerado por E. R. Berlekamp, a "melhor página única publicada" em teoria de códigos.
Há dois códigos de Golay binários intimamente relacionados. O código binário estendido de Golay, G$_{24}$ (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, G$_{23}$, 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

Em termos matemáticos, o código binário estendido de Golay G$_{24}$ consiste em um subespaço vetorial W de dimensão 12 do espaço V=F$_2$$^{24}$ 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 = 2$^{12}$ 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 G$_{24}$ 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 = 2$^4$*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, G$_{23}$ é 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. G$_{23}$ é um subespaço de dimensão 12 do espaço F$_2$$^{23}$.
O grupo de automorfismos do código binário perfeito de Golay, G$_{23}$, é o grupo de Mathieu $M_{23}.$ O grupo de automorfismos do código binário estendido de Golay é o grupo de Mathieu$M_{24},$ de ordem 2$^{10}$*3$^3$*5*7*11*23. $M_{24}$ é transitivo em octads e em dodecads. Os outros grupos de Mathieu ocorrem como estabilizadores de um ou vários elementos de W.

## Construções

* 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 w$_1$ = 0, defina w$_2$, w$_3$, ..., w$_{12}$ pela regra segundo a qual w$_n$ é 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 w$_1$, ..., w$_{12}$.
* 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 S$_t$ 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 S$_t$ 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 G$_{23}$ pode ser construído através da fatoração de $x^{23}-1$ sobre o corpo binário GF(2): $x^{23}-1=(x-1)(x^{11}+x^{9}+x^{7}+x^{6}+x^{5}+x+1)(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1).$ Ele é o código gerado por $\left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right).$ Qualquer um dos fatores irredutíveis de grau 11 pode ser usado para gerar o código.
* 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.
* 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 $\mathbb {F} _{2}^{4}$ em 4 planos. 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

É 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 S$_3$ de um subgrupo trio de M$_{24}$ é útil para gerar uma base. PSL(2,7) permuta as octads internamente, em paralelo. S$_3$ 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 S$_3$, 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
### Missões da NASA no espaço profundo

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).
* 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

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.