Ir ao conteúdo principal

Exercícios 8.5 Exercícios

1.

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

Informação 0 1 2 3 4 5 6 7 8
Palavra do Código 000 001 010 011 101 110 111 000 001

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.

\begin{equation*} (0110) \quad (1001) \quad (1010) \quad (1100) \end{equation*}
Dica.

Não pode ser um código de grupos pois \((0000) \notin C\text{.}\)

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)\)

Dica.

(a) 2; (c) 2.

4.

Calcule os pesos das seguintes \(n\)-tuplas.

  1. \(\displaystyle (011010)\)

  2. \(\displaystyle (11110101)\)

  3. \(\displaystyle (01111)\)

  4. \(\displaystyle (1011)\)

Dica.

(a) 3; (c) 4.

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)\)

Dica.

(a) \(d_{\min} = 2\text{;}\) (c) \(d_{\min} = 1\text{.}\)

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. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 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{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 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{pmatrix} \end{equation*}
Dica.

  1. \((00000), (00101), (10011), (10110)\)

    \begin{equation*} G = \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}

  2. \((000000), (010111), (101101), (111010)\)

    \begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}

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

\begin{equation*} H = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}. \end{equation*}

Decodifique a mensagem

\begin{equation*} 01111 \quad 10101 \quad 01110 \quad 00011 \end{equation*}

se possível.

Dica.

Múltiplos erros ocorrem em uma das palavras recebidas.

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. \begin{equation*} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 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{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 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{pmatrix} \end{equation*}
Dica.

(a) É matriz verificadora canônica com matriz geradora padrão

\begin{equation*} G = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

(c) É matriz verificadora canônica com matriz geradora padrão

\begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ 1 & 0 \end{pmatrix}. \end{equation*}

12.

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

Dica.

(a) Todas as possíveis síndromes ocorrem.

13.

Seja

\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}. \end{equation*}

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. \begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 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{pmatrix} \end{equation*}
Dica.

(a) \(C\text{,}\) \((10000) + C\text{,}\) \((01000) + C\text{,}\) \((00100) + C\text{,}\) \((00010) + C\text{,}\) \((11000) + C\text{,}\) \((01100) + C\text{,}\) \((01010) + C\text{.}\) Não existe tabela de decodificação para \(C\text{,}\) pois este é somente um código detector de um erro.

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 \rightarrow {\mathbb R}\) que satisfaz as seguintes condição.

  1. \(d( {\mathbf x}, {\mathbf y}) \geq 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}) \leq 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.

Dica.

Seja \({\mathbf x} \in C\) uma palavra de peso ímpar e defina uma função e defina uma função do conjunto de todas as palavras de peso ímpar ao conjunto das palavras de peso par como \({\mathbf y} \mapsto {\mathbf x} + {\mathbf y}\text{.}\) Mostre que esta função é uma bijeção.

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?

Dica.

Para 20 posições de informação, são necessárias ao menos 6 bits para assegurar um código de correção de um erro.

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

\begin{equation*} C^\perp = \{ {\mathbf x} \in {\mathbb Z}_2^n : {\mathbf x} \cdot {\mathbf y} = 0 \text{ para todo } {\mathbf y} \in C \}. \end{equation*}

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

    \begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}. \end{equation*}

  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

    \begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{equation*}

    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.