Álgebra Abstrata: Teoria e Aplicações

1.

Por que o seguinte sistema de codificação não é aceitável?

2.

Sem realizar nenhuma soma, explique porquê o seguinte conjunto de 4-tuplas em ${\mathbb{Z}}_2^4$ não pode ser um código de grupo.

3.

Calcule as distâncias de Hamming entre os seguintes pares de $n$-tuplas.

1. ${\displaystyle (011010),(011100)}$

2. ${\displaystyle (11110101),(01010100)}$

3. ${\displaystyle (00110),(01111)}$

4. ${\displaystyle (1001),(0111)}$

4.

Calcule os pesos das seguintes $n$-tuplas.

1. ${\displaystyle (011010)}$

2. ${\displaystyle (11110101)}$

3. ${\displaystyle (01111)}$

4. ${\displaystyle (1011)}$

5.

Se um código linear $C$ tem peso mínimo 7, quais são as capacidades de detecção e correção de erros de $C\text{?}$

6.

Para cada um dos seguintes códigos, qual é a distância mínima do código? Qual é a melhor situação que podemos esperar em relação a detecção e correção de erros?

1. ${\displaystyle (011010)(011100)(110111)(110000)}$

2. $(011100)(011011)(111011)(100011)$ \; $(000000)(010101)(110100)(110011)$

3. ${\displaystyle (000000)(011100)(110101)(110001)}$

4. $(0110110)(0111100)(1110000)(1111111)$ \; $(1001001)(1000011)(0001111)(0000000)$

7.

Calcule o espaço nulo de cada uma das seguintes matrizes. Que tipo de códigos de blocos $(n,k)$ são os espaços nulos? Podemos encontrar uma matriz (não necessariamente uma matriz geradora padrão) que gere cada código? São únicas suas matrizes geradoras?

1. $$\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right)$$
2. $$\left(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 1& 1& 0& 0& 0& 1\end{array}\right)$$
3. $$\left(\begin{array}{ccccc}1& 0& 0& 1& 1\\ 0& 1& 0& 1& 1\end{array}\right)$$
4. $$\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1\end{array}\right)$$

8.

Construa um código de blocos $(5,2)\text{.}$ Discuta as capacidades de detecção e correção de erros de seu código.

9.

Seja $C$ o código obtido como espaço nulo da matriz

Decodifique a mensagem

se possível.

10.

Suponha que é transmitida uma mensagem de 1000 bits, que a probabilidade de erro em um bit é $p$ e que os erros que possam ocorrer em bits diferentes são independentes entre eles. Se $p=0.01\text{,}$ qual é a probabilidade de que ocorra mais de um erro? Qual é a probilidade de que ocorram exatamente dois erros? Repita o problema para $p=0.0001\text{.}$

11.

Que matrizes são matrizes verificadoras canônicas? Para essas matrizes, quais são as correspondentes matrizes geradoras padrão? Quais são as capacidades de detecção e correção de erros de cada uma dessas matrizes?

1. $$\left(\begin{array}{ccccc}1& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\end{array}\right)$$
2. $$\left(\begin{array}{cccccc}0& 1& 1& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 1& 1& 0& 0& 0& 1\end{array}\right)$$
3. $$\left(\begin{array}{cccc}1& 1& 1& 0\\ 1& 0& 0& 1\end{array}\right)$$
4. $$\left(\begin{array}{ccccccc}0& 0& 0& 1& 0& 0& 0\\ 0& 1& 1& 0& 1& 0& 0\\ 1& 0& 1& 0& 0& 1& 0\\ 0& 1& 1& 0& 0& 0& 1\end{array}\right)$$

12.

Liste toda as possíveis síndromes para os códigos gerados por cada uma das matrizes do Exercício 8.5.11.

13.

Seja

Calcule a síndrome causada por cada um dos seguintes erros de transmissão.

1. Um erro no primeiro bit.

2. Um erro no terceiro bit.

3. Um erro no último bit.

4. Erros no terceiro e quarto bits.

14.

Seja $C$ o código de grupo em ${\mathbb{Z}}_2^3$ definido pelas palavras $(000)$ e $(111)\text{.}$ Calcule as classes laterais de $H$ em ${\mathbb{Z}}_2^3\text{.}$ Por que não é necessário especificar se tratamos de classes laterais direitas ou esquerdas? Encontre o erro singular de transmissão, se existir, diga a qual classe lateral corresponda.

15.

Para cada uma das seguintes matrizes, encontre as classes laterais para o código $C$ correspondente. Encontre uma tabela de decodificação para cada código se for possível.

1. $$\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right)$$
2. $$\left(\begin{array}{ccccc}0& 0& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 1\end{array}\right)$$
3. $$\left(\begin{array}{ccccc}1& 0& 0& 1& 1\\ 0& 1& 0& 1& 1\end{array}\right)$$
4. $$\left(\begin{array}{ccccccc}1& 0& 0& 1& 1& 1& 1\\ 1& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\\ 1& 1& 1& 0& 0& 1& 0\end{array}\right)$$

16.

Sejam $\mathbf{x}\text{,}$ $\mathbf{y}$ e $\mathbf{z}$ $n$-tuplas binárias. Demonstre cada um dos seguintes enunciados.

1. ${\displaystyle w(\mathbf{x})=d(\mathbf{x},\mathbf{0})}$

2. ${\displaystyle d(\mathbf{x},\mathbf{y})=d(\mathbf{x}+\mathbf{z},\mathbf{y}+\mathbf{z})}$

3. ${\displaystyle d(\mathbf{x},\mathbf{y})=w(\mathbf{x}-\mathbf{y})}$

17.

Uma métrica em um conjunto $X$ é uma função $d:X\times X\to \mathbb{R}$ que satisfaz as seguintes condição.

1. $d(\mathbf{x},\mathbf{y})\ge 0$ para todo $\mathbf{x},\mathbf{y}\in X\text{;}$

2. $d(\mathbf{x},\mathbf{y})=0$ si y solo si $\mathbf{x}=\mathbf{y}\text{;}$

3. $d(\mathbf{x},\mathbf{y})=d(\mathbf{y},\mathbf{x})\text{;}$

4. $d(\mathbf{x},\mathbf{y})\le d(\mathbf{x},\mathbf{z})+d(\mathbf{z},\mathbf{y})\text{.}$

Em outras palavras, uma métrica é simplesmente uma generalização da noção de distância. Demonstre que a distância de Hamming é uma métrica em ${\mathbb{Z}}_2^n\text{.}$ Decodificar uma mensagem na realidade corresponde a decidir qual é a palavra do código mais próxima em termos da distância de Hamming.

18.

Seja $C$ um código linear binário. Mostre que entre as $i$-ésimas coordenadas das palavras em $C$ são todas zeros ou exatamente metade são zeros.

19.

Seja $C$ um código linear binário. Mostre que ou todas as palavras tem peso par ou exatamente a metade delas tem o peso par.

20.

Mostre que as palavras de peso par em um código linear binário $C$ também formam um código linear.

21.

Se temos de usar um código linear corretor de erros para transmitir os 128 caracteres ASCII, que tamanho de matriz deve ser usada? Que tamanho de matriz deve ser usada para transmitir o conjunto ASCII estendido de 256 caracteres? E se só precisamos de detecção de erros em ambos casos?

22.

Encontre a matriz verificadora canônica que da o código de verificação de paridade com três posições de informação. Qual é a matriz para sete posições de informação? Quais são as matrizes geradoras padrões correspondentes?

23.

Quantas posições de verificação são necessárias para um código de correção de um erro com 20 posições de informação? Com 32 posições de informação?

24.

Seja ${\mathbf{e}}_i$ a $n$-tupla binária com um 1 na $i$-ésima coordenada e $0$ nas demais e suponha que $H\in {\mathbb{M}}_{m\times n}({\mathbb{Z}}_2)\text{.}$ Mostre que $H{\mathbf{e}}_i$ é a $i$-ésima coluna da matriz $H\text{.}$

25.

Seja $C$ um código linear $(n,k)\text{.}$ Vamos definir o código dual ou código ortogonal de $C$ como

1. Encontre o código dual do código linear $C$ donde $C$ está dado pela matriz

   $$\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right).$$

2. Mostre que $C^{\perp }$ é um código linear $(n,n-k)\text{.}$

3. Encontre as matrizes verificadora canônica e geradora padrão de $C$ e $C^{\perp }\text{.}$ O que acontece no geral? Demonstre sua conjectura.

26.

Seja $H$ uma matriz de $m\times n$ sobre ${\mathbb{Z}}_2\text{,}$ donde a $i$-ésima coluna é o número $i$ escrito em binário com $m$ bits. O espaço nulo de tal matriz se chama código de Hamming.

1. Mostre que a matriz

   $$H=\left(\begin{array}{cccccc}0& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 1& 0& 1& 0& 1& 0\end{array}\right)$$

   gera um código de Hamming. Quais são as propriedades de correção de erros de um código de Hamming?

2. A coluna correspondente a síndrome também marca o bit donde ocorreu o erro; isto é, a $i$-ésima coluna da matriz é $i$ escrito como número binário, e a síndrome imediatamente nos diz qual é o bit incorreto. Se a palavra recebida é $(101011)\text{,}$ calcule a síndrome. Em que bit ocorreu o erro neste caso, e qual era a palavra originalmente transmitida?

3. Entregue um matriz binária $H$ para o código de Hamming com seis posições de informação e quatro de verificação. Quais são as posições de verificação e quais são as de informação? Codifique as mensagens $(101101)$ e $(001001)\text{.}$ Decodifique as palavras recebidas $(0010000101)$ e $(0000101100)\text{.}$ Quais são as possíveis síndromes para este código?

4. Qual é o número de bits de verificação e o número de bits de informação em um código de Hamming de blocos $(m,n)\text{?}$ Encontre tanto uma cota superior como uma cota inferior para o número de bits de informação em termos do número de bits de verificação. Códigos de Hamming que tem o máximo número de bits possível de informação com $k$ bits de verificação se chamam perfeitos. Cada possível síndrome com exceção de $\mathbf{0}$ ocorre como uma coluna. Se o número de bits de informação é menor que o máximo, então o código se chama encurtado. Neste caso, dê um exemplo donde algumas síndromes possam representar múltiplos erros.