Ir ao conteúdo principal

Exercícios 8.9 Exercícios em Sage

1.

Construa o código (binário) Golay com o construtor codes.GolayCode(). Leia a documentação para assegurar-se de construir a versão binária (e não a ternária), e não construa a versão estendida (que é a default).

  1. Use métodos Sage para calcular o comprimento, a dimensão e a distância mínima do código.

  2. Quantos erros podem ser detectados neste código? Quantos pode corrigir?

  3. Encontre uma palavra distinta de zero no código e introduza três erros somando um vetor com três 1's (de sua escolha) para criar uma mensagem recebida. Mostre que a mensagem se decodifica corretamente.

  4. Recicle suas escolhas da parte anterior, mas agora adicione um outro erro. A mensagem recebida é decodificada corretamente?

2.

Uma técnica que permita melhorar as características de um código é adicionar um bit de paridade geral, tal como o bit de paridade do código ASCII descrito no Exemplo 8.1.3. Tais códigos são conhecidos como versões estendidas do código original.

  1. Construa o código de Golay binário e obtenha a matriz verificadora. Use comandos Sage para estender esta matriz criando uma nova matriz de paridade que considere um bit de paridade global adicional. Os métodos .augment() e .stack() para matrizes podem ser úteis, assim como os construtores zero_vector() e ones_matrix() (recordando que especificamos as entradas binárias como pertencentes ao corpo GF(2).)

    Crie o código estendido entregando a matriz de paridade aumentada ao construtor codes.from_parity_check_matrix() e calcule o comprimento, dimensão e distância mínima de código estendido.

  2. Em que sentido são melhores as características deste código novo? A que custo?

  3. Agora crie o código Golay binário estendido com codes.GolayCode() e a opção apropriada para obter a versão estendida. Com alguma sorte, as listas ordenadas de suas palavras e as do código implementado em Sage, serão as mesmas. Senão, o método .is_permutation_equivalent() deverá retornar True indicando que seu código e Sage são simplesmente rearranjos um do outro.

3.

O dual de um código de blocos \((n,k)\) é formado pelo conjunto dos vetores binários ortogonais a todos os vetores do código original. O Exercício 8.5.25 descreve esta construção e pergunta por algumas de suas propriedades.

Podemos obter o dual de um código em Sage com o método .dual_code(). Construa os códigos de Hamming binários, e seus duais, com o parâmetro r variando desde 2 até 5. Construa uma tabela com seis colunas (possivelmente usando a função html.table()) que liste \(r\text{,}\) o comprimento do código, a dimensão do código original, a do seu dual, a distância mínima do código e de seu dual.

Conjecture fórmulas para a dimensão e distância mínima do dual de um código de Hamming em termos do parâmetro \(r\text{.}\)

4.

Um código com distância mínima \(d\) se chama perfeito se todo vetor possível está a uma distância menor ou igual a \((d-1)/2\) de alguma palavra do código. Se expandimos nossa ideia de geometria para incluir a noção de distância de Hamming como a métrica, então podemos falar de uma esfera de raio \(r\) em torno de um vetor ou palavra. Para um código de comprimento \(n\text{,}\) uma esfera deste tipo contém

\begin{equation*} 1 + {n\choose 1} + {n\choose 2} + \cdots + {n\choose r} \end{equation*}

vetores em seu interior. Para um código perfeito, as esferas de raio \((d-1)/2\) centradas nas palavras do código particionam exatamente o espaço de todos os vetores possíveis. (Isto é o que estabelece uma relação entre a teoria de códigos e os problemas de empacotamento de esferas.)

Uma consequência de que um código de dimensão \(k\) seja perfeito é que

\begin{equation*} 2^k\left({n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose \frac{d-1}{2}}\right) = 2^n \end{equation*}

Reciprocamente, se um código tem distância mínima \(d\) e cumpre a condição anterior, então o código é perfeito.

Escreva uma função em Sage, chamada is_perfect() que tome um código linear como entrada e retorne True ou False se o código for ou não perfeito. Demonstre sua função verificando que o código de Golay binário é perfeito, e use um loop para verificar que os códigos de Hamming binários são perfeitos para longitudes menores que \(32\text{.}\)