\documentclass[11pt,a4paper]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage{a4wide}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[isolatin]{inputenc}
\usepackage[portuges]{babel}

\setlength{\oddsidemargin}{-0.5cm} \setlength{\textwidth}{ 500pt}
\topmargin = -1cm \headheight = 0cm \headsep = 0cm
%\pagestyle{empty}
\textheight 26cm \textwidth 17.cm

\linespread{1.2}
%\textwidth15cm
%\textheight25cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\ZZ{{\mathbb{Z}}}
\def\FF{{\mathbb{F}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cM{\mathcal{M}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\l({\left(}
\def\r){\right)}
\def\lsqbr{\left[}
\def\rsqbr{\right]}
\def\lbr{\left[}
\def\rbr{\right]}
\def\ZZ{{\mathbb{Z}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cMmn{\mathcal{M}_{m\times n}}
\def\cMrp{\mathcal{M}_{r\times p}}
\def\cMrn{\mathcal{M}_{r\times n}}
\def\cMm{\mathcal{M}_{m}}
\def\cMn{\mathcal{M}_{n}}
\def\cMp{\mathcal{M}_{p}}
\def\cMq{\mathcal{M}_{q}}
\def\cMk{\mathcal{M}_{k}}
\def\cM{\mathcal{M}}
\def\cLT{\mathcal{LT}}
\def\cLTn{\mathcal{LT}_n}
\def\parR{\left( \RR \right)}
\def\parC{\left( \CC \right)}
\def\parK{\left( \KK \right)}
%\def\epf{\hfill \rule{2mm}{4mm}}
\def\epf{\endproof}
\def\iff{\Leftrightarrow}
\def\imply{\Rightarrow}
\def\beqn{\begin{eqnarray*}}
\def\eeqn{\end{eqnarray*}}
\def\barr{\begin{array}}
\def\earr{\end{array}}
\def\vN{\l(1\r)}
\def\para{\rightarrow}

\def\mp{^{{{\mathtt{\mu}}}}}


\newtheorem{theorem}{Teorema}[section]
\newtheorem{definition}[theorem]{Defini\c{c}\~{a}o}
\newtheorem{lemma}[theorem]{Lema}
\newtheorem{proposition}[theorem]{Proposi\c{c}\~{a}o}
\newtheorem{corollary}[theorem]{Corol\'{a}rio}
\newtheorem{exemplo}[theorem]{Exemplo}
\newtheorem{obs}[theorem]{Observa\c{c}\~{a}o}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\pagestyle{empty}
\noindent
{\sf Universidade do Minho}
\hfill {\sf lem mat[ens;apl] lmcc}

\noindent{\small {\sf Departamento de Matem\'{a}tica}}


\vskip 0.3cm \centerline{{\large{\sf Teoria de C\'odigos}}}


\vskip 0.3cm
 \noindent\rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{exerc\'{\i}cios}}}} \hrulefill \rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{2005:2006}}}} \rule{1.5cm}{0.2mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\

\begin{enumerate}

\item $\mp$ Calcule o digito de controlo, segundo o ISBN\footnote{$x_1x_2\dots x_{10}$ é tal que $(x_1,x_2,\dots,x_{10})\cdot (10,9,8,7,6,5,4,3,2,1) \equiv 0 \mod 11$, onde $x_i=0..9$, se $i=1..9$, e $x_{10}=0..10$. $10$ é representado por $X$.}-10, de:
\ben
\item 0-19-853803-
\item 3-540-66336-
\item 84-9789-613-
\item 84-7658-486-
\een

\item $\mp$ Verifique a validade, segundo o ISBN-10, de:
\ben
\item 972-25-1375-3
\item 972-8839-21-9
\item 972-8839-06-5
\item 972-41-3663-9
\een



\item $\mp$ Verifique a validade, segundo o EAN\footnote{$x_1x_2\dots x_{13}$ é tal que $(x_1,x_2,\dots,x_{13})\cdot (1,3,1,3,1,3,1,3,1,3,1,3,1) \equiv 0 \mod 10$, onde $x_i=0..9$, se $i=1..13$. Pode obter mais informações em {\sf http://www.barcodeisland.com/ean13.phtml}.}-13, de:
\ben
\item 5601405001101
\item 5601522469075
\item 5601038100202
\item 5601537332739
\item 5601370031127
\item 8003410344315
\item 5000265090209 
\een


\item  $\mp$ Crie os ISBN\footnote{A conversão para -13 dos ISBN-10 é feita, ao não se considerar o digito de controlo deste último, concatenando o prefixo 978 ou o 979, e ao resultante aplicar o EAN-13. Veja mais em {\sf http://en.wikipedia.org/wiki/ISBN-13}.}-13 dos ISBN-10 da questão  2, com o prefixo 978-.

\item  $\mp$ Construa um procedimento que teste o código ISBN-10 recebido.

\item  $\mp$ Construa um procedimento que gere o digito de controlo (\textit{checksum}) para o ISBN-10.

\item  $\mp$ Construa um procedimento que teste o código EAN-13 recebido.

\item  $\mp$ Construa um procedimento que gere o digito de controlo (\textit{checksum}) para o EAN-13.


\item  $\mp$ Construa um procedimento que teste o código usado nos cheques bancários\footnote{Além do número do cheque e o número de conta, em alguns bancos é usado ainda um outro número com 9 dígitos $a_1a_2\dots a_9$ que identifica o banco emissor, e é tal que $(a_1,a_2,\dots ,a_9)\cdot (7,3,9,7,3,9,7,3,-1) \equiv 0 \mod 10$.}.


\item  $\mp$ Encontre uma base para o  espaço nulo das matrizes seguintes:
\ben
\item $ \left(\begin{array}{ccccc}
                    0 & 1 & 0 & 0 & 1\\
                    0 & 0 & 0 & 1 & 1\\
                    1 & 1 & 1 & 1 & 0\end{array}\right)$, matriz sobre $\ZZ_2$.
\item $  \left(\begin{array}{ccccccc}
                1 & 0 & 0 & 1 & 0 & 1 & 1\\
                1 & 1 & 1 & 0 & 1 & 0 & 0\end{array}\right) $, matriz sobre $\ZZ_2$.
\item $ \left(\begin{array}{ccccc}
                    0 & 0 & 2 & 2 & 0\\
                    0 & 1 & 0 & 2 & 0\\
                    1 & 0 & 2 & 2 & 0\end{array}\right)$, matriz sobre $\ZZ_3$.
\item $\left(\begin{array}{ccccc}
                  9 & 12 & 12 & 33 & 9\\
                  24 & 29 & 18 & 9 & 5\\
                  5 & 15 & 17 & 16 & 19\end{array}\right)$, matriz sobre $\ZZ_{37}$.
\item $\left(\begin{array}{cccc}
       110416 & 31572 & 554310 & 604695 \\
       462290 & 192626 & 378018 & 389981 \\
       \end{array}\right)$, matriz sobre $\ZZ_{877651}$.
\een

\item  $\mp$ Use o \textit{mupad} para gerar uma matriz aleatória\footnote{Use o comando {\tt linalg::randomMatrix}.} sobre um $\ZZ_p$ à sua escolha, calcula a nulidade e uma base para o seu espaço nulo.

\item $\mp$ De forma aleatória,
\ben 
\item crie corpos de Galois $\FF_q$  de ordem
\ben
\item $q=8$ \item $q=9$
\item $q=343$ \item $q=14641$ \item $q=531441$  \item $q=1220703125$\een
\item matrizes, e determine a nulidade e uma base para o espaço nulo, sobre os corpos da alínea anterior.
\een

\item Sejam $D=\ZZ_3[x],f(x)=x^2+x+2,g(x)=x^2+1$. Calcule:
\ben
\item $(x+2)+(2x+2)$ em $D/(f(x))$ e em $D/(g(x))$;
\item $(x+2)(2x+2)$  em $D/(f(x))$ e em $D/(g(x))$;
\een

\item Seja $f(x)=x^2+x+2$.
\ben
\item Mostre que $f(x)$ é primitivo em $\ZZ_3[x]$.
\item Mostre que $f(x)$ é primitivo em $\ZZ_5[x]$.
\item Mostre que $f(x)$ não é primitivo em $\ZZ_{11}[x]$.
\een

\item Mostre que $f(x)=x^3+x+1$ é primitivo em $\ZZ_ 2[x]$.
\item Mostre que $f(x)=x^3+x^2+1$ é primitivo em $\ZZ_ 2[x]$.
\item Mostre que $f(x)=x^4+x+1$ é primitivo em $\ZZ_ 2[x]$.

\item 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 $\ZZ_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$. 

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

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


\item 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.


\item 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.

\item Construa um procedimento {\tt 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)$.


\item Construa um procedimento {\tt
  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 {\it matriz de Hamming}. Por exemplo,\\
{\tt >> hamming(3);}
$$\lbr\barr{ccccccc}
 0& 0& 0& 1& 1& 1& 1  \\
  0& 1& 1& 0& 0& 1& 1 \\
  1& 0& 1& 0& 1& 0& 1 \earr\rbr$$


\item Verifique se a mensagem recebida é uma palavra-código, onde os
  códigos usados são de Hamming:
\ben
\item r=(1,1,1,1,1,1,1)$^T$ no código $[7,4]$;
\item r=(1,0,1,0,1,1,1)$^T$  no código $[7,4]$;
\item r=(1,0,1,0,1,1,1,0,0,1,1,1,0,0,0)$^T$, no código $[15,11]$;
\item r=(0,0,1,1,0,0,0,0,1,0,0,0,0,1,0)$^T$,  no código $[15,11]$;
\item r=(1,0,1,0,0,0,1,0,1,1,1,1,0,0,0)$^T$,  no código $[15,11]$;
\item r=(1,1,0,0,1,0,1,1,1,0,0,0,0,0,0)$^T$,  no código $[15,11]$;
\item 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]$;
\item 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]$;
\een

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

\item Seja $C$ o código de Hamming $[31,26]$.
\ben
\item Construa a matriz de paridade e uma matriz geradora do código
  $C$.
\item Codifique, em $C$, o vector
$$w=(10110101110110111110111000).$$
\item Corrija os erros e descodifique\footnote{O sistema $Ax=b$ é
  resolvido, no MuPAD, por {\tt linalg::matlinsolve(A,b);}.}  os vectores recebidos:
\ben
\item $r=(1101011100110110110101011110111)$
\item $r=(0001011100111110110101011110111)$
\item $r=(0000000001110010010101010101010)$
\een
\een

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

\item 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$.


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

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

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


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

\item  $[12,4]$ que
  seja c.c. 3-erros.
\een

\item Considere as matrizes, sobre $\ZZ_2$,
$$G_1=\lbr\barr{c|c}
\barr{cc} 1&1\\1&1\\0&1 \earr & I_3 \earr\rbr, \,G_2=\lbr\barr{c|c} I_3 &
\barr{cc} 0&1\\1&1\\1&1 \earr \earr\rbr, \, G_3=\lbr\barr{c|c} I_4 &
\barr{ccc} 1&1&0\\1&1&1\\1&1&0\\1&0&1 \earr  \earr\rbr$$
Para cada uma delas,
\ben
\item determine o número de elementos do código de que a matriz
  é geradora;
\item indique uma base para o espaço nulo.
\item encontre uma matriz de paridade para cada um dos códigos gerados pelas matrizes;
\item verifique se
  os códigos corrigem erros singulares.
\een

\item Calcule as matrizes de paridade das seguintes matrizes
  geradoras:

\begin{tabular}{lll}
(a) $\lbr \barr{c|c}
I_3 & \barr{ccc} 1&1&0\\0&1&1\\1&1&1\earr\earr\rbr$&
(b) $\lbr \barr{c|c}
I_3 & \barr{ccc} 1&1&1\\0&1&1\\1&1&0\earr\earr\rbr$ &
(c) $\lbr \barr{c|c}
I_3 & \barr{ccc} 0&1&1\\1&1&1\\1&1&0\earr\earr\rbr$ \\ \\
(d) $\lbr \barr{c|c}
I_4 & \barr{cccc} 1&1&0\\0&1&1\\1&0&1\\1&1&1\earr\earr\rbr$ &
(e) $\lbr \barr{c|c}
I_4 & \barr{ccc} 1&1&1\\0&1&1\\1&0&1\\1&1&1\earr\earr\rbr$
\end{tabular}

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

\item Verifique se a distância de Hamming é uma métrica.
\een


\item Construa um código binário linear auto-dual em $\ZZ_2^6$.

\item Construa um código binário linear auto-dual em $\ZZ_2^8$.

\item Seja $H=\lbr\barr{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 \earr\rbr$ a matriz de paridade de um código
linear. Calcule o número de posições corrigíveis nesse código.

\item Seja $G=\lbr \barr{cccccc}
1&1&1&0&1&0\\
0&0&1&1&1&1 \earr\rbr$ e suponha que
$$r_1=(100011),\, r_2=(101010), \, r_3=(111100).$$
\ben
\item Construa o código linear gerado por $G$.
\item Calcule o número de posições corrigíveis.
\item Liste os líderes e respectivos síndromes. 
\item  Corrija, se possível,
  os vectores recebidos $r_1$, $r_2$ e $r_3$.
\een

\item Se $G=\lbr \barr{cccccc}
1&1&0&0&1&1\\
0&0&1&0&1&1 \earr\rbr$ é a matriz geradora de um código linear $C$,
encontre:
\ben
\item os parâmetros $[n,k]$;
\item a matriz de paridade;
\item a distância mínima do código e o número de posições corrigíveis;
\item a correcção dos vectores recebidos $r_1=(100010)$ e $r_2=(001100)$.
\een

\item Seja $W=RS(G)$ com  $G=\lbr \barr{cccccc }
1&0 &0&1&1&0\\
0&1 &0&1&0&1\\
0&0&1&0&1&0 \earr\rbr$.
\ben
\item Encontre a matriz de paridade $H$ de $W$ e os parâmetros
  $[n,k,d]$.
\item Verifique se  $W$ \'e auto-dual.
\item Corrija os vectores recebidos $r_1=(111111)$ e $r_2=(101111)$
\een

\item Seja $C$ um código linear com matriz de paridade
$$\lbr\barr{c|c}
I_4 &
\barr{ccc}
1 & 0 & 1\\
1 & 0 & 1\\
0 & 1 & 1\\
0 & 1 & 1
\earr
\earr\rbr.$$
Corrija e descodifique, se possível, cada um dos seguintes vectores recebidos:
\ben
\item $(1101011)$;
\item $(0110111)$;
\item $(0111000)$.
\een

\item Encontre os completamentos de
$H=\lbr\barr{ccc}
?&1&0\\
?&0&1\earr\rbr$ de forma a que seja a matriz de paridade de uma código
  linear com correcção de 1 {\em bit}.


\item Para $\pi(x)=x^4+x+1\in \ZZ_2[x]$,
\ben
\item mostre, via MuPad,  que $\pi(x)$ é irredutível

\item mostre  que $\pi(x)$ é primitivo
\ben
\item usando matrizes;
\item  via MuPad.
\een


\item Para cada um dos polinómios em $\ZZ_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.:
\ben
\item $\pi(x)=x^3+x^2+1$ c.c. 1-erro,
\item $\pi(x)=x^3+x^2+1$ c.c. 2-erros,
\item $\pi(x)=x^3+x^2+1$ c.c. 3-erros,
\item $\pi(x)=x^4+x+1$ de forma a que seja $[15,7]$,
\item $\pi(x)=x^4+x^3+1$ c.c. 2-erros,
\item $\pi(x)=x^4+x^3+1$ c.c. 3-erros,
\item $\pi(x)=x^6+x^5+1$ c.c. 3-erros.
\een

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

\item  Seja $C$ o código BCH obtido do polinómio primitivo
  $\pi(x)=x^4+x+1\in \ZZ_2[x]$, considerando as primeiras 4 potências
  de $\alpha$. 
\ben
\item Mostre que $g(x)=x^8+x^7+x^6+x^4+1$ é polinómio gerador de $C$.
\item Corrija, em $C$, o seguinte vector recebido por um
  canal com ruído:
$$r=\lbr\barr{ccccccccccccccc}
1 & 0 &1 &1 &0 &0 &1 &1 &1 & 0&0&1&0&0&0\earr\rbr.$$
\een

\item  Considere o polinómio irredutível  $\pi(x)=x^4+x^3+1\in
  \ZZ_2[x]$.
\ben
\item Verifique que $\pi(x)$ é primitivo.
\item Encontre os polinómios minimais aniquiladores das 6 primeiras
  potências de $\alpha$.
\item 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=\lbr\barr{ccccccccccccccc}
1 & 0 &1 &0 &1 &0 &0 &0 &1 & 0&0&0&0&0&0\earr\rbr.$$
\een

\item Seja $C$ o código BCH obtido do polinómio primitivo $\pi(x)=x^4+x+1\in \ZZ_2[x]$  corrector de 2 erros.
\ben
\item Codifique, em $C$, o vector
$$r=\lbr\barr{ccccccc}
1 & 0 &0 &1 &0 &0 &0 \earr\rbr,$$ apresentando o resultado final como
um vector linha sobre $\ZZ_2$. 
\item Corrija, em $C$, o seguinte vector recebido por um
  canal com ruído:
$$r=\lbr\barr{ccccccccccccccc}
0 & 0 &0 &0 &1 &0 &1 &0 &1 & 1&1&1&0&0&0\earr\rbr.$$

\een

\een
\end{document}

