Universidade do Minho lem mat[ens;apl] lmcc

Departamento de Matemática

Teoria de Códigos

exercícios 2005:2006

1. $^{{{\mathtt{\mu}}}}$ Calcule o digito de controlo, segundo o ISBN¹-10, de:
   1. 0-19-853803-
   2. 3-540-66336-
   3. 84-9789-613-
   4. 84-7658-486-

2. $^{{{\mathtt{\mu}}}}$ Verifique a validade, segundo o ISBN-10, de:
   1. 972-25-1375-3
   2. 972-8839-21-9
   3. 972-8839-06-5
   4. 972-41-3663-9

3. $^{{{\mathtt{\mu}}}}$ Verifique a validade, segundo o EAN²-13, de:
   1. 5601405001101
   2. 5601522469075
   3. 5601038100202
   4. 5601537332739
   5. 5601370031127
   6. 8003410344315
   7. 5000265090209

4. $^{{{\mathtt{\mu}}}}$ Crie os ISBN³-13 dos ISBN-10 da questão 2, com o prefixo 978-.

5. $^{{{\mathtt{\mu}}}}$ Construa um procedimento que teste o código ISBN-10 recebido.

6. $^{{{\mathtt{\mu}}}}$ Construa um procedimento que gere o digito de controlo (checksum) para o ISBN-10.

7. $^{{{\mathtt{\mu}}}}$ Construa um procedimento que teste o código EAN-13 recebido.

8. $^{{{\mathtt{\mu}}}}$ Construa um procedimento que gere o digito de controlo (checksum) para o EAN-13.

9. $^{{{\mathtt{\mu}}}}$ Construa um procedimento que teste o código usado nos cheques bancários⁴.

10. $^{{{\mathtt{\mu}}}}$ Encontre uma base para o espaço nulo das matrizes seguintes:
    1. $\left(\begin{array}{ccccc} 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 0\end{array}\right)$, matriz sobre ${\mathbb{Z}}_2$.
    2. $\left(\begin{array}{ccccccc} 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 1 & 0 & 0\end{array}\right)$, matriz sobre ${\mathbb{Z}}_2$.
    3. $\left(\begin{array}{ccccc} 0 & 0 & 2 & 2 & 0\\ 0 & 1 & 0 & 2 & 0\\ 1 & 0 & 2 & 2 & 0\end{array}\right)$, matriz sobre ${\mathbb{Z}}_3$.
    4. $\left(\begin{array}{ccccc} 9 & 12 & 12 & 33 & 9\\ 24 & 29 & 18 & 9 & 5\\ 5 & 15 & 17 & 16 & 19\end{array}\right)$, matriz sobre ${\mathbb{Z}}_{37}$.
    5. $\left(\begin{array}{cccc} 110416 & 31572 & 554310 & 604695 \\ 462290 & 192626 & 378018 & 389981 \\ \end{array}\right)$, matriz sobre ${\mathbb{Z}}_{877651}$.

11. $^{{{\mathtt{\mu}}}}$ Use o mupad para gerar uma matriz aleatória⁵ sobre um ${\mathbb{Z}}_p$ à sua escolha, calcula a nulidade e uma base para o seu espaço nulo.

12. $^{{{\mathtt{\mu}}}}$ De forma aleatória,
    1. crie corpos de Galois ${\mathbb{F}}_q$ de ordem
       1. $q=8$
       2. $q=9$
       3. $q=343$
       4. $q=14641$
       5. $q=531441$
       6. $q=1220703125$
    2. matrizes, e determine a nulidade e uma base para o espaço nulo, sobre os corpos da alínea anterior.

13. Sejam $D={\mathbb{Z}}_3[x],f(x)=x^2+x+2,g(x)=x^2+1$. Calcule:
    1. $(x+2)+(2x+2)$ em $D/(f(x))$ e em $D/(g(x))$;
    2. $(x+2)(2x+2)$ em $D/(f(x))$ e em $D/(g(x))$;

14. Seja $f(x)=x^2+x+2$.
    1. Mostre que $f(x)$ é primitivo em ${\mathbb{Z}}_3[x]$.
    2. Mostre que $f(x)$ é primitivo em ${\mathbb{Z}}_5[x]$.
    3. Mostre que $f(x)$ não é primitivo em ${\mathbb{Z}}_{11}[x]$.

15. Mostre que $f(x)=x^3+x+1$ é primitivo em ${\mathbb{Z}}_ 2[x]$.
16. Mostre que $f(x)=x^3+x^2+1$ é primitivo em ${\mathbb{Z}}_ 2[x]$.
17. Mostre que $f(x)=x^4+x+1$ é primitivo em ${\mathbb{Z}}_ 2[x]$.

18. Para $f(x)=x^4+x^3+x^2+x+1$, $g(x)=x^4+x^3+x^2+1$, $h(x)=x^4+x^3+1$, mostre, em ${\mathbb{Z}}_ 2[x]$, qual deles é primitivo, irredutível e não primitivo, e não irredutível. Para o que é irredutível e não primitivo, calcule a ordem do polinómio $x$.

19. Construa o elementos não nulos de um corpo de Galois com 128 elementos.

20. Construa o elementos não nulos de um corpo de Galois com 127 elementos.

21. Dado um código $(15, 16,8)$ binário, calcule o número de erros que são corrigíveis e o número de vectores corrigíveis. Sendo o canal simétrico binário, com $p=0.1$ a probabilidade de um símbolo ser recebido erradamente, calcule a probabilidade de uma palavra ser corrigível.

22. Dado um código $(8, 16,4)$ binário, calcule o número de erros que são corrigíveis e o número de vectores corrigíveis. Sendo o canal simétrico binário, com $p=0.1$ a probabilidade de um símbolo ser recebido erradamente, calcule a probabilidade de uma palavra ser corrigível.

23. Construa um procedimento bin2dec:=proc(v) que escreva na representação decimal a entrada $(v_1v_2\cdots v_k)_2$, onde $v=(v_1,\dots ,v_k)$.

24. Construa um procedimento hamming:=proc(numero:Type::PosInt) onde $n$ é um argumento de entrada, número inteiro positivo, e cujo resultado final é uma matriz $n\times (2^n-1)$, cuja coluna $j$ é a representação do número natural $j$ na sua escrita binária. A matriz resultante chama-se matriz de Hamming. Por exemplo,
    » hamming(3);
    $$\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 \end{array}\right]$$

25. Verifique se a mensagem recebida é uma palavra-código, onde os códigos usados são de Hamming:
    1. r=(1,1,1,1,1,1,1)$^T$ no código $[7,4]$;
    2. r=(1,0,1,0,1,1,1)$^T$ no código $[7,4]$;
    3. r=(1,0,1,0,1,1,1,0,0,1,1,1,0,0,0)$^T$, no código $[15,11]$;
    4. r=(0,0,1,1,0,0,0,0,1,0,0,0,0,1,0)$^T$, no código $[15,11]$;
    5. r=(1,0,1,0,0,0,1,0,1,1,1,1,0,0,0)$^T$, no código $[15,11]$;
    6. r=(1,1,0,0,1,0,1,1,1,0,0,0,0,0,0)$^T$, no código $[15,11]$;
    7. r=(1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1)$^T$ no código $[31,26]$;
    8. r=(1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,0,0,1,0)$^T$ no código $[31,26]$;

26. Calcule as matrizes geradoras dos códigos de Hamming $[7,4]$ e $[15,11]$.

27. Seja $C$ o código de Hamming $[31,26]$.
    1. Construa a matriz de paridade e uma matriz geradora do código $C$.
    2. Codifique, em $C$, o vector
       $$w=(10110101110110111110111000).$$

    3. Corrija os erros e descodifique⁶ os vectores recebidos:
       1. $r=(1101011100110110110101011110111)$
       2. $r=(0001011100111110110101011110111)$
       3. $r=(0000000001110010010101010101010)$

28. Corrija e descodifique os vectores recebidos referentes à questão 25.

29. Considerando o código de Hamming $[63,57]$, e depois de gerar aleatoriamente um vector $r$ que se assume recebido, corrija o erro em $r$.

30. Averigue se é possível construir um código linear binário
    1. $[6,2]$ que seja c.c. 2-erros.

    2. $[8,3]$ que seja c.c. 2-erros.

    3. $[6,2]$ que seja c.c. 2-erros.

    4. $[10,3]$ que seja c.c. 3-erros.

    5. $[12,4]$ que seja c.c. 3-erros.

31. Considere as matrizes, sobre ${\mathbb{Z}}_2$,
    $$G_1=\left[\begin{array}{c\vert c} \begin{array}{cc} 1&1\ 1&1... ...cc} 1&1&0\ 1&1&1\ 1&1&0\ 1&0&1 \end{array}\end{array}\right]$$
    Para cada uma delas,
    1. determine o número de elementos do código de que a matriz é geradora;
    2. indique uma base para o espaço nulo.
    3. encontre uma matriz de paridade para cada um dos códigos gerados pelas matrizes;
    4. verifique se os códigos corrigem erros singulares.

32. Calcule as matrizes de paridade das seguintes matrizes geradoras:

    (a) $\left[\begin{array}{c\vert c} I_3 & \begin{array}{ccc} 1&1&0\ 0&1&1\ 1&1&1\end{array}\end{array}\right]$	(b) $\left[\begin{array}{c\vert c} I_3 & \begin{array}{ccc} 1&1&1\ 0&1&1\ 1&1&0\end{array}\end{array}\right]$	(c) $\left[\begin{array}{c\vert c} I_3 & \begin{array}{ccc} 0&1&1\ 1&1&1\ 1&1&0\end{array}\end{array}\right]$
    (d) $\left[\begin{array}{c\vert c} I_4 & \begin{array}{cccc} 1&1&0\ 0&1&1\ 1&0&1\ 1&1&1\end{array}\end{array}\right]$	(e) $\left[\begin{array}{c\vert c} I_4 & \begin{array}{ccc} 1&1&1\ 0&1&1\ 1&0&1\ 1&1&1\end{array}\end{array}\right]$

33. Seja $C$ um código linear $[n,k]$.
    1. Considere a relação binária $\sim$ definida am ${\mathbb{Z}}_2^n$ por
       $$a \sim b$$    se $$a-b\in C.$$
       1. Verifique se $\sim$ é uma relação de equivalência.
       2. Mostre que $u \sim v$ se e só se $Hu^T = Hv^T$, onde $H$ é a matriz de paridade do código $C$.

    2. Verifique se a distância de Hamming é uma métrica.

34. Construa um código binário linear auto-dual em ${\mathbb{Z}}_2^6$.

35. Construa um código binário linear auto-dual em ${\mathbb{Z}}_2^8$.

36. Seja $H=\left[\begin{array}{cccccccc} 1&1&1&1&1&1&1&1\\ 0&1&0&1&0&1&0&1\\ 0&0&1&1&0&0&1&1\\ 0&0&0&0&1&1&1&1 \end{array}\right]$ a matriz de paridade de um código linear. Calcule o número de posições corrigíveis nesse código.

37. Seja $G=\left[\begin{array}{cccccc} 1&1&1&0&1&0\\ 0&0&1&1&1&1 \end{array}\right]$ e suponha que
    $$r_1=(100011), r_2=(101010), r_3=(111100).$$
    1. Construa o código linear gerado por $G$.
    2. Calcule o número de posições corrigíveis.
    3. Liste os líderes e respectivos síndromes.
    4. Corrija, se possível, os vectores recebidos $r_1$, $r_2$ e $r_3$.

38. Se $G=\left[\begin{array}{cccccc} 1&1&0&0&1&1\\ 0&0&1&0&1&1 \end{array}\right]$ é a matriz geradora de um código linear $C$, encontre:
    1. os parâmetros $[n,k]$;
    2. a matriz de paridade;
    3. a distância mínima do código e o número de posições corrigíveis;
    4. a correcção dos vectores recebidos $r_1=(100010)$ e $r_2=(001100)$.

39. Seja $W=RS(G)$ com $G=\left[\begin{array}{cccccc } 1&0 &0&1&1&0\\ 0&1 &0&1&0&1\\ 0&0&1&0&1&0 \end{array}\right]$.
    1. Encontre a matriz de paridade $H$ de $W$ e os parâmetros $[n,k,d]$.
    2. Verifique se $W$ é auto-dual.
    3. Corrija os vectores recebidos $r_1=(111111)$ e $r_2=(101111)$

40. Seja $C$ um código linear com matriz de paridade
    $$\left[\begin{array}{c\vert c} I_4 & \begin{array}{ccc} 1 & 0 ... ... 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 1 \end{array}\end{array}\right].$$
    Corrija e descodifique, se possível, cada um dos seguintes vectores recebidos:
    1. $(1101011)$;
    2. $(0110111)$;
    3. $(0111000)$.

41. Encontre os completamentos de $H=\left[\begin{array}{ccc} ?&1&0\\ ?&0&1\end{array}\right]$ de forma a que seja a matriz de paridade de uma código linear com correcção de 1 bit.

42. Para $\pi(x)=x^4+x+1\in {\mathbb{Z}}_2[x]$,
    1. mostre, via MuPad, que $\pi(x)$ é irredutível

    2. mostre que $\pi(x)$ é primitivo
       1. usando matrizes;
       2. via MuPad.

    3. Para cada um dos polinómios em ${\mathbb{Z}}_ 2[x]$ apresentados, construa, se possível, o código BCH e os respectivos parâmetros $[n,k,d]$ e número de p.c.:
       1. $\pi(x)=x^3+x^2+1$ c.c. 1-erro,
       2. $\pi(x)=x^3+x^2+1$ c.c. 2-erros,
       3. $\pi(x)=x^3+x^2+1$ c.c. 3-erros,
       4. $\pi(x)=x^4+x+1$ de forma a que seja $[15,7]$,
       5. $\pi(x)=x^4+x^3+1$ c.c. 2-erros,
       6. $\pi(x)=x^4+x^3+1$ c.c. 3-erros,
       7. $\pi(x)=x^6+x^5+1$ c.c. 3-erros.

    4. Seja $C$ o código BCH obtido do polinómio primitivo $\pi(x)=x^4+x+1\in {\mathbb{Z}}_2[x]$, considerando as primeiras 6 potências de $\alpha$. Corrija, em $C$, os seguintes vectores recebidos por um canal com ruído:
       1. $r_1=(100011011001010)$;
       2. $r_2=(011111010011010)$;
       3. $r_3=(101000011101100)$;
       4. $r_4=(111011001010100)$.

43. Seja $C$ o código BCH obtido do polinómio primitivo $\pi(x)=x^4+x+1\in {\mathbb{Z}}_2[x]$, considerando as primeiras 4 potências de $\alpha$.
    1. Mostre que $g(x)=x^8+x^7+x^6+x^4+1$ é polinómio gerador de $C$.
    2. Corrija, em $C$, o seguinte vector recebido por um canal com ruído:
       $$r=\left[\begin{array}{ccccccccccccccc} 1 & 0 &1 &1 &0 &0 &1 &1 &1 & 0&0&1&0&0&0\end{array}\right].$$

44. Considere o polinómio irredutível $\pi(x)=x^4+x^3+1\in {\mathbb{Z}}_2[x]$.
    1. Verifique que $\pi(x)$ é primitivo.
    2. Encontre os polinómios minimais aniquiladores das 6 primeiras potências de $\alpha$.
    3. Seja $C$ o código BCH obtido do polinómio primitivo $\pi(x)$ corrector de 2 erros. Corrija, em $C$, o seguinte vector recebido por um canal com ruído:
       $$r=\left[\begin{array}{ccccccccccccccc} 1 & 0 &1 &0 &1 &0 &0 &0 &1 & 0&0&0&0&0&0\end{array}\right].$$

45. Seja $C$ o código BCH obtido do polinómio primitivo $\pi(x)=x^4+x+1\in {\mathbb{Z}}_2[x]$ corrector de 2 erros.
    1. Codifique, em $C$, o vector
       $$r=\left[\begin{array}{ccccccc} 1 & 0 &0 &1 &0 &0 &0 \end{array}\right],$$
       apresentando o resultado final como um vector linha sobre ${\mathbb{Z}}_2$.
    2. Corrija, em $C$, o seguinte vector recebido por um canal com ruído:
       $$r=\left[\begin{array}{ccccccccccccccc} 0 & 0 &0 &0 &1 &0 &1 &0 &1 & 1&1&1&0&0&0\end{array}\right].$$