Seção 8.8 Sage
Sage contém uma coleção importante de códigos lineares e uma variedade de métodos que podem ser usados para investigá-los.
Subseção 8.8.1 Construindo Códigos Lineares
O objeto codes pode ser usado para obter uma lista concisa dos códigos implementados disponíveis. Escreva codes. e pressione Tab. A maior parte das interfaces da Sage te entregarão uma lista. Você pode usar o sinal de interrogação ao final do nome de um método para aprender mais sobre seus parâmetros.
Usaremos o código binário de Hamming \((7,4)\) clássico como ilustração. “Binário” quer dizer que temos vetores com só zeros e uns, \(7\) é o comprimento e significa que os vetores tem \(7\) coordenadas, e \(4\) é a dimensão, o que significa que este código contém \(2^4=16\) vetores. A documentação supõe que sabemos umas poucos coisas de mais adiante no texto. Usamos GF(2) para especificar que o código é binário — isso terá mais sentido depois de ter sido estudado corpos finitos. Um segundo parâmetro é r e podemos ver as fórmulas na documentação que configuramos r=3 nos dará comprimento \(7\text{.}\)
Subseção 8.8.2 Propriedades dos Códigos Lineares
Podemos agora examinar o código que acabamos de construir. Primeiro sua dimensão.
O código é suficientemente pequeno para que possamos listar todas suas palavras.
A distância mínima é possivelmente uma de suas propriedades mais importantes. Os códigos de Hamming sempre tem distância mínima \(d=3\text{,}\) de maneira que sempre são corretores de um erro.
Sabemos que a matriz verificadora e a matriz geradora são úteis para a construção, descrição e análise dos códigos lineares. Os nomes dos métodos em Sage são um pouco enigmáticos. Sage tem rotinas para analisar matrizes com elementos de diferentes corpos, de maneiras que faremos boa parte da análise desta matriz dentro da Sage.
A matriz geradora do texto tem colunas que são palavras do código, e combinações lineares das colunas (o espaço de colunas da matriz) são palavras do código. Em Sage a matriz geradora tem linhas que são palavras do código e o espaço linha da matriz é o código. Temos aqui outro ponto em que devemos traduzir mentalmente entre uma seleção feita no texto e uma seleção feita pelos desenvolvedores da Sage.
Aqui temos um teste parcial que essas duas matrizes são corretas, exercitando o Lema 8.3.5. Note que necessitamos transpor a matriz geradora pelas razões expostas antes.
Notemos que a matriz verificadora pode não ser canônica e que a matriz geradora pode não ser padrão. Sage pode produzir uma matriz geradora que tenha um conjunto de colunas que formem a matriz identidade, mas não é garantido que estas colunas sejam as primeiras. (Colunas, não linhas.) Tal matriz se diz sistemática, e o método em Sage é .systematic_generator_matrix().
Subseção 8.8.3 Decodificando um Código Linear
Podemos decodificar mensagens recebidas originadas por um código linear. Suponha que recebemos o vetor binário de comprimento \(7\)r.
Podemos reconhecer que um ou mais erros ocorreram, pois r não pertence ao código, dado que o seguinte cálculo não resulta no vetor zero.
Um código linear tem um método .decode. Você pode escolher entre algoritmos distintos, mas os códigos de Hamming tem seu algoritmo particular. O algoritmo padrão faz o uso de síndromes.
Se estamos dispostos a supor que só ocorreu um erro (o que podemos, se a probabilidade de erro em uma entrada particular do vetor seja muito baixa), então vemos que ocorreu um erro na terceira posição.
Recorde que poderia ser que tivesse ocorrido mais de um erro. Por exemplo, suponha que a mensagem é a mesma de antes e ocorrem erros na terceira, quinta e sexta posições.
Então parece que recebemos uma palavras do código, então assumimos nenhum erro e decodificamos incorretamente.