O limite de Gilbert-Varshamov para códigos lineares está relacionado com o limite geral de Gilbert-Varshamov, que fornece um limite inferior para o número máximo de elementos num código corretor de erros de um dado comprimento de bloco e peso de Hamming mínimo sobre um corpo . Isto pode ser traduzido numa afirmação sobre a taxa máxima de um código com um dado comprimento e distância mínima. O limite de Gilbert-Varshamov para códigos lineares assegura a existência de códigos lineares q-ários para qualquer distância mínima relativa inferior ao limite dado que simultaneamente possuam uma alta taxa. A prova de existência utiliza o método probabilístico e, por conseguinte, não é construtiva.

O limite de Gilbert-Varshamov é o melhor conhecido em termos de distância relativa para códigos sobre alfabetos de tamanho inferior a 49. Para alfabetos maiores, os códigos de geometria algébrica alcançam por vezes um compromisso assintoticamente melhor entre taxa e distância do que o estabelecido pelo limite de Gilbert-Varshamov.

Teorema do limite de Gilbert-Varshamov

Teorema: Seja . Para todo o e existe um código linear -ário com taxa e distância relativa

Aqui é a função de entropia q-ária definida da seguinte forma:

O resultado acima foi provado por Edgar Gilbert para códigos gerais utilizando o método guloso. Rom Varshamov refinou o resultado para demonstrar a existência de um código linear. A prova utiliza o método probabilístico.

Ideia da demonstração:

Para mostrar a existência do código linear que satisfaz estas restrições, o método probabilístico é usado para construir um código linear aleatório. Especificamente, o código linear é escolhido selecionando uma matriz geradora cujas entradas são elementos de escolhidos aleatoriamente. A distância de Hamming mínima de um código linear é igual ao peso mínimo de uma palavra de código não nula, de modo que, para provar que o código gerado por tem distância mínima , basta mostrar que para qualquer . Provaremos que a probabilidade de existir uma palavra de código não nula de peso inferior a é exponencialmente pequena em . Então, pelo método probabilístico, existe um código linear que satisfaz o teorema.

Demonstração formal:

Usando o método probabilístico para mostrar que existe um código linear que tem uma distância de Hamming superior a , mostraremos que a probabilidade de o código linear aleatório ter uma distância inferior a é exponencialmente pequena em .

O código linear é definido pela sua matriz geradora, que escolhemos ser uma matriz geradora aleatória ; ou seja, uma matriz de elementos que são escolhidos de forma independente e uniforme sobre o corpo .

Recorde-se que, num código linear, a distância é igual ao peso mínimo de uma palavra de código não nula. Seja o peso da palavra de código . Então

A última igualdade decorre da definição: se uma palavra de código pertence a um código linear gerado por , então para algum vetor .

Pela Desigualdade de Boole, temos:

Agora, para uma dada mensagem queremos calcular

Seja a distância de Hamming entre duas mensagens e . Então, para qualquer mensagem , temos: . Portanto:

Devido à aleatoriedade de , é um vetor uniformemente aleatório de . Logo

Seja o volume de uma Bola de Hamming com o raio . Então:A desigualdade posterior provém do limite superior do Volume da bola de Hamming

Ao escolher , a desigualdade acima torna-se

Finalmente , que é exponencialmente pequeno em n, que era o que queríamos demonstrar. Então, pelo método probabilístico, existe um código linear com distância relativa e taxa de pelo menos , o que conclui a demonstração.

Comentários

A construção de Varshamov descrita acima não é explícita; ou seja, não especifica um método determinístico para construir o código linear que satisfaz o limite de Gilbert-Varshamov. Uma abordagem ingénua consiste em procurar em todas as matrizes geradoras de tamanho sobre o corpo para verificar se o código linear associado a atinge a distância de Hamming prevista. Esta pesquisa exaustiva requer um tempo de execução exponencial no pior dos casos. Existe também uma construção de Las Vegas que toma um código linear aleatório e verifica se este código tem uma boa distância de Hamming, mas esta construção também tem um tempo de execução exponencial. Para um q suficientemente grande não primo e para certas gamas da variável δ, o limite de Gilbert-Varshamov é superado pelo Limite de Tsfasman-Vladut-Zink.

Ver também

Limite de Gilbert-Varshamov devido à construção de Gilbert para o código geral Limite de Hamming Método probabilístico

Referências

Bibliografia

Aula 11: Limite de Gilbert–Varshamov. Curso de Teoria de Códigos. Professor Atri Rudra Aula 9: Limites sobre o Volume da Bola de Hamming. Curso de Teoria de Códigos. Professor Atri Rudra Notas de Teoria de Códigos: Limite de Gilbert-Varshamov. Venkatesan Guruswami