Sobre o significado geométrico dos códigos Gray

Os códigos cinza têm um parentesco próximo com a curva de Hilbert .

No entanto, ao se comunicar com os colegas, descobriu-se que esse vício simples parece aos seus olhos algo não trivial. Uma pesquisa na Internet não deu nada além de uma frase enlameada no wiki: “As curvas de Hilbert em espaços de maior dimensão são representantes de generalizações dos códigos de Gray”. Portanto, havia um desejo de abrir o tópico - brevemente, em linguagem simples.

Como resultado, sob o corte - "escândalos, intrigas, investigações".

A principal característica do código Gray é que dois valores lexicograficamente adjacentes diferem apenas em uma categoria. Por outro lado, a curva de Hilbert é contínua - a distância entre dois pontos adjacentes é sempre uma. Isso por si só sugere sua conexão interna.

O código Gray descreve as ocorrências de uma curva de Hilbert em um único hipercubo. De fato, se pegarmos um código de 3 bits e o desenharmos no espaço tridimensional (pegando cada bit para a coordenada correspondente), obteremos


Figura 1 Código cinza de 3 bits como um cubo tridimensional

A imagem familiar é o simplex tridimensional da curva de Hilbert! Substituindo sucessivamente cada nó do simplex pelo mesmo simplex (levando em consideração rotações e reflexões para manter a continuidade), obtemos uma curva de Hilbert 4x4x4.

Continuando essas iterações, podemos preencher continuamente uma estrutura cúbica de qualquer tamanho.


Figura 2 várias iterações do simplex da curva de Hilbert.

Mas como isso aconteceu?

Sabe-se que o código Gray é auto-semelhante. Às vezes, é chamado de espelho “devido ao fato de que a primeira metade dos valores ao alterar a ordem é equivalente à segunda metade, com exceção do bit alto. A parte mais significativa é simplesmente invertida. ” Para maior clareza, o código de 3 bits é o bit mais significativo - o mais à esquerda:



Como estamos falando de auto-similaridade, vamos começar do começo - com um código de um bit. A rigor, seria possível começar com uma dimensão zero - pontos, isso fundamentalmente não muda nada, apenas as palavras teriam que ser escritas mais.

O código de um dígito de Gray é ainda mais simples que um rifle de três linhas, é 0 ou 1.

Geometricamente, isso corresponde a um cubo unitário unidimensional - um segmento. Você pode mover-se ao longo de um segmento do começo ao fim ou do começo ao fim - até a simetria, esse é o mesmo. Mas, no entanto, chamaremos o início de local onde o valor é menor (lembre-se de que os lados do cubo são dígitos do número) e o final - onde é mais.

Passamos ao caso bidimensional. Um cubo bidimensional é um quadrado. Considerando a auto-similaridade, clonamos o cubo unidimensional (0,1) e obtemos dois segmentos - (0,0 -> 1,0) e (0,1 -> 1,1). Agora você precisa conectar esses segmentos para contornar o quadrado. E aqui surgem duas opções:

• conectamos o início da iteração anterior - o cubo unidimensional com o início de seu clone. Até simetria, é o mesmo que conectar o fim ao fim. O tipo de simetria é espelho. Esta opção é chamada condicionalmente de “missionário”.
  
• conectamos o final da iteração anterior ao início de seu clone. Até simetria, é o mesmo que unir o início de uma linha ao final de um clone. O tipo de simetria é central. Chamamos essa opção de "trem".

Agimos de maneira semelhante ao passar para três ou mais casos dimensionais.


Figura 3 As duas primeiras iterações da versão “missionária”

Aqui a iteração anterior é destacada em vermelho, seu clone é em azul e sua conexão é em turquesa.

Observe que a conexão sempre passa por uma única dimensão - a recém adicionada, portanto, o principal recurso do código Gray aparece devido à auto-similaridade. E como o final da iteração anterior está conectado ao final do seu clone, ocorre o "espelhamento" - ao dar a volta, somos forçados a passar pelo clone na ordem inversa. Independentemente da dimensão. Aqui você pode ver a origem e os recursos da curva de Hilbert - não importa o tamanho da rede (de qualquer dimensão), no nível de base ainda é o mesmo cubo de unidade com transições de comprimento um.


Figura 4 As duas primeiras iterações da opção “treinar”, as mesmas cores

Mas essa música também é familiar para nós - temos uma curva Z simples. A palavra simplex aqui também significa que, se pegarmos cada um de seus pontos e substituí-lo por um simplex, obteremos um cubo 4x4x4, com iterações contínuas - podemos preencher uma estrutura cúbica arbitrariamente grande.

É engraçado que, neste caso, a conversão do caminho passado da origem para o código, que pode ser analisado em bits, seja trivial.
Enquanto o caso do código Gray é G = W ^ (W >> 1), onde W é o comprimento passado, G é o código Gray.


Figura 5 primeiras duas iterações da curva Z (wiki)


6 para comparação, as duas primeiras iterações da curva de Hilbert (wiki)

Mas não há outras opções (naturais) para contornar um único hipercubo.
Acontece que, onde quer que você jogue, em torno de Hilbert, Lebesgue ... e vazio .

PS : na figura do título, um codificador circular com um código Gray de oito dígitos.
PPS : aqui eles me corrigem que o termo simplex é um termo bem estabelecido, não é bom com ele. Bem, este artigo não é apenas um simplex, mas um simplex de uma curva de Hilbert ou um simplex de uma curva Z. Que os matemáticos fiéis me perdoem.