Código binário de Golay

Código binário estendido de Golay
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 $[24,12,8]_{2}$

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 $[23,12,7]_{2}$

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₂₄ (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₂₃, 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₂₄ consiste em um subespaço vetorial W de dimensão 12 do espaço V=F₂²⁴ 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¹² 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₂₄ 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⁴*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₂₃ é 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₂₃ é um subespaço de dimensão 12 do espaço F₂²³.

O grupo de automorfismos do código binário perfeito de Golay, G₂₃, é 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¹⁰*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₁ = 0, defina w₂, w₃, ..., w₁₂ 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₁, ..., w₁₂.
• 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₂₃ 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₃ de um subgrupo trio de M₂₄ é útil para gerar uma base. PSL(2,7) permuta as octads internamente, em paralelo. S₃ 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₃, 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 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

• Sanguessuga lattice

Referências

• Conway, John Horton; Sloane, Neil J. A. (1999), Sphere Packings, Lattices and Groups, ISBN 978-0-387-98585-5, Grundlehren der Mathematischen Wissenschaften, 290 3rd ed. , Berlin, New York: Springer-Verlag, MR 0920369 
• Curtis, R. T. (1976). «A new combinatorial approach to M₂₄». Mathematical Proceedings of the Cambridge Philosophical Society. 79: 25–42. doi:10.1017/S0305004100052075 
• Golay, Marcel J. E. (1949). «Notes on Digital Coding». Proc. IRE. 37. 657 páginas 
• Greferath, Marcus (2003). «Golay Codes». In: Proakis, John G. Encyclopedia of Telecommunications. [S.l.]: Wiley. doi:10.1002/0471219282 
• Griess, Robert L. (1998). Twelve Sporadic Groups. [S.l.]: Springer. 167 páginas. ISBN 978-3-540-62778-4 
• Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes, ISBN 978-0-471-19047-9 3rd ed. , John Wiley & Sons 
• Roman, Steven (1996), Coding and Information Theory, ISBN 0-387-97812-7, Graduate Texts in Mathematics #134, Springer-Verlag 
• Thompson, Thomas M. (1983). From Error Correcting Codes through Sphere Packings to Simple Groups. Col: Carus Mathematical Monographs. 21. [S.l.]: Mathematical Association of America. ISBN 978-0-88385-023-7 
• Turyn, Richard J.; et al. (1967). Research to Develop the Algebraic Theory of Codes (Section VI) (PDF) (Relatório). Air Force Cambridge Research Laboratories