Código binário de Golay - Binary Golay code

Código binário de Golay estendido
Matriz geradora
Nomeado após	Marcel JE Golay
Classificação
Modelo	Código de bloco linear
Comprimento do bloco	24
Comprimento da mensagem	12
Avaliar	24/12 = 0,5
Distância	8
Tamanho do alfabeto	2
Notação	${\ displaystyle [24,12,8] _ {2}}$ -código
v t e

Código binário perfeito de Golay
Nomeado após	Marcel JE Golay
Classificação
Modelo	Código de bloco linear
Comprimento do bloco	23
Comprimento da mensagem	12
Avaliar	23/12 ~ 0,522
Distância	7
Tamanho do alfabeto	2
Notação	${\ displaystyle [23,12,7] _ {2}}$ -código
v t e

Em matemática e engenharia eletrônica , um código de Golay binário é um tipo de código de correção de erros linear usado em comunicações digitais . O código binário de Golay, junto com o código ternário de Golay , tem uma conexão particularmente profunda e interessante com a teoria dos grupos esporádicos finitos na matemática. Esses códigos foram nomeados em homenagem a Marcel JE Golay, cujo artigo de 1949 os apresentou foi considerado, por ER Berlekamp , a "melhor página única publicada" na teoria da codificação.

Existem dois códigos binários de Golay intimamente relacionados. O código binário de Golay estendido , G ₂₄ (às vezes chamado apenas de "código de Golay" na teoria dos grupos finitos) codifica 12 bits de dados em uma palavra de 24 bits de tal forma que quaisquer erros de 3 bits podem ser corrigidos ou qualquer 7 erros de bit podem ser detectados. 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 de uma posição coordenada (inversamente, o código binário estendido de Golay é obtido a partir do código binário perfeito de Golay adicionando um bit de paridade ). Na notação de codificação padrão, os códigos têm 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 linear 12-dimensional W do espaço V = F ²⁴
₂ de palavras de 24 bits, de modo que quaisquer dois elementos distintos de W difiram em pelo menos 8 coordenadas. W é chamado de código linear porque é um espaço vetorial. Ao todo, W compreende 4096 = 2 ¹² elementos.

• Os elementos de W são chamados de palavras de código . Eles também podem ser descritos como subconjuntos de um conjunto de 24 elementos, em que a adição é definida como a obtenção da diferença simétrica dos subconjuntos.
• No código binário estendido de Golay, todas as palavras de código têm pesos de Hamming de 0, 8, 12, 16 ou 24. As palavras de código de peso 8 são chamadas de octads e as palavras de código de peso 12 são chamadas de dodecads .
• Octads do código G ₂₄ são elementos do sistema S (5,8,24) Steiner . Existem 759 = 3 × 11 × 23 octads e 759 complementos dos mesmos. Segue-se que existem 2576 = 2 ⁴ × 7 × 23 dodecads.
• Duas octads se cruzam (têm 1s em comum) em 0, 2 ou 4 coordenadas na representação vetorial binária (esses são os tamanhos de intersecção possíveis na representação de subconjunto). Um octade e um dodecad cruzam-se em 2, 4 ou 6 coordenadas.
• Até as coordenadas de reclassificação, W é único.

O código binário de Golay, G _23, é um código perfeito . Ou seja, as esferas de raio três em torno das palavras de código formam uma partição do espaço vetorial. G ₂₃ é um subespaço 12-dimensional do espaço F ²³
₂ .

O grupo de automorfismo do código binário perfeito de Golay, G ₂₃ , é o grupo Mathieu . O grupo de automorfismo do código binário estendido de Golay é o grupo Mathieu , da ordem 2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23 . é transitivo em octads e em dodecads. Os outros grupos Mathieu ocorrer como estabilizadores de um ou vários elementos de W . ${\ displaystyle M_ {23}}$ ${\ displaystyle M_ {24}}$${\ displaystyle M_ {24}}$

Construções

• Código lexicográfico : ordene os vetores em V lexicograficamente (ou seja, interprete-os como inteiros binários sem sinal de 24 bits e siga a ordem usual). Começando com w ₀ = 0, defina w ₁ , w ₂ , ..., w ₁₂ pela regra de que w _n é o menor inteiro que difere de todas as combinações lineares de elementos anteriores em pelo menos oito coordenadas. Então W pode ser definido como o intervalo de w ₁ , ..., w ₁₂ .
• Grupo Mathieu : Witt em 1938 publicou uma construção do maior grupo Mathieu que pode ser usado para construir o código binário estendido de Golay.
• Código de resíduo quadrático : Considere o conjunto N de não-resíduos quadráticos (mod 23). Este é um 11-elemento subconjunto do grupo cíclico Z / 23 Z . Considere a tradução t + N deste subconjunto. Aumente cada translação para um conjunto de 12 elementos S _t adicionando um elemento ∞. Em seguida, rotular os elementos de base de V por 0, 1, 2, ..., 22, ∞, W pode ser definido como o intervalo das palavras S _t junto com a palavra consistindo de todos os vetores de base. (O código perfeito é obtido omitindo ∞.)
• Como um código cíclico : O código G ₂₃ perfeito pode ser construído através da fatoração de sobre o campo binário GF (2) : ${\ displaystyle x ^ {23} -1}$

${\ displaystyle 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).}$

É o código gerado por . Qualquer um dos fatores irredutíveis de grau 11 pode ser usado para gerar o código. ${\ displaystyle \ left (x ^ {11} + x ^ {10} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {2} +1 \ right)}$

• A construção de Turyn de 1967, "Uma Construção Simples do Código Binário de Golay", que começa com o código de Hamming de comprimento 8 e não usa os resíduos quadráticos mod 23.
• Do Steiner System S (5,8,24) , consistindo em 759 subconjuntos de um 24-conjunto. Se interpretarmos o suporte de cada subconjunto como uma palavra-código 0-1 de comprimento 24 (com peso de Hamming 8), essas serão as "octades" no código binário de Golay. Todo o código de Golay pode ser obtido pegando repetidamente as diferenças simétricas de subconjuntos, ou seja, adição binária. Uma maneira mais fácil de escrever o resp do sistema Steiner. o octads é o Miracle Octad Generator de RT Curtis, que usa uma correspondência 1: 1 particular entre as 35 partições de um 8-conjunto em dois 4-conjuntos e as 35 partições do espaço vetorial finito em 4 planos. Hoje em dia, muitas vezes é usada a abordagem compacta do hexacódigo de Conway, que usa um array 4 × 6 de células quadradas. ${\ displaystyle \ mathbb {F} _ {2} ^ {4}}$
• Posições de vitória no jogo matemático do Mogul: uma posição no Mogul é uma linha de 24 moedas. Cada jogada consiste em lançar de uma a sete moedas, de modo que a mais à esquerda das moedas viradas vai da cabeça à cauda. As posições perdedoras são aquelas sem movimento legal. Se cara for interpretada como 1 e coroa como 0, mover para uma palavra-código do código binário de Golay estendido garante que será possível forçar uma vitória.
• Uma matriz geradora para o código binário de Golay é IA , onde I é a matriz de identidade 12 × 12 e A é o complemento da matriz de adjacência do icosaedro .

Uma representação conveniente

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

Uma partição das 6 colunas em 3 pares adjacentes constitui um trio . Esta é uma partição em 3 conjuntos de octad. Um subgrupo, o grupo linear especial projetivo PSL (2,7) x S ₃ de um subgrupo trio de M _24, é útil para gerar uma base. PSL (2,7) permeia as octades internamente, em paralelo. S ₃ permeia as 3 octads corporalmente.

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 dessas palavras de código consiste em todos os 1s. Adicionar N a uma palavra de código produz 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 fracionário linear gerado por (0123456) e (0∞) (16) (23) (45). O 7-ciclo atua em T para dar um subespaço incluindo também os elementos de base

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 7-dimensional resultante tem um espaço quociente tridimensional ao ignorar os últimos 2 octads.

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

W tem um subespaço de dimensão 4, simétrico sob PSL (2,7) x S ₃ , estendido por N e 3 dodecads formados por subconjuntos {0,3,5,6}, {0,1,4,6}, e {0,1,2,5}.

Aplicações práticas dos códigos de Golay

Missões do espaço profundo da NASA

A correção de erros foi vital para a transmissão de dados nas espaçonaves Voyager 1 e 2, particularmente porque as restrições de memória ditaram o descarregamento de dados virtualmente instantaneamente sem deixar nenhuma segunda chance. Centenas de fotos coloridas de Júpiter e Saturno em seus sobrevôos de 1979, 1980 e 1981 seriam transmitidas dentro de uma largura de banda de telecomunicações restrita. A transmissão de imagens coloridas exigia três vezes a quantidade de dados que as imagens em preto e branco, de modo que o código Reed-Muller de correção de 7 erros que tinha sido usado para transmitir as imagens Mariner em preto e branco foi substituído pela taxa de dados Golay muito mais alta (24, 12,8) código.

Radiocomunicação

Os padrões militares americanos MIL-STD-188 para estabelecimento de link automático em sistemas de rádio de alta frequência especificam o uso de um código Golay estendido (24,12) para correção de erros antecipada .

Veja também

• Malha de sanguessuga

Referências

Origens

• Conway, John Horton ; Sloane, Neil JA (1999), Sphere Packings, Lattices and Groups , Grundlehren der Mathematischen Wissenschaften, 290 (3ª ed.), Berlim, Nova York: Springer-Verlag , ISBN   978-0-387-98585-5 , MR   0920369
• Curtis, RT (1976). "Uma nova abordagem combinatória para M ₂₄ ". Mathematical Proceedings of the Cambridge Philosophical Society . 79 : 25–42. doi : 10.1017 / S0305004100052075 .
• Greferath, Marcus (2003). "Códigos Golay". Em Proakis, John G. (ed.). Enciclopédia de Telecomunicações . Wiley. doi : 10.1002 / 0471219282.eot371 . ISBN   0471219282 .
• Griess, Robert L. (1998). Doze grupos esporádicos . Springer. p. 167. ISBN   978-3-540-62778-4 .
• Pless, Vera (1998), Introdução à Teoria dos Códigos de Correção de Erros (3ª ed.), John Wiley & Sons, ISBN   978-0-471-19047-9
• Roman, Steven (1996), Coding and Information Theory , Graduate Texts in Mathematics # 134, Springer-Verlag, ISBN   0-387-97812-7
• Thompson, Thomas M. (1983). De códigos de correção de erros, passando por embalagens em esfera, até grupos simples . Carus Mathematical Monographs. 21 . Mathematical Association of America. ISBN   978-0-88385-023-7 .
• Turyn, Richard J .; et al. (1967). Pesquisa para desenvolver a teoria algébrica dos códigos (Seção VI) (PDF) (Relatório). Laboratórios de Pesquisa de Cambridge da Força Aérea. Arquivado do original (PDF) em 30 de outubro de 2018.