% \documentclass[landscape,12pt,a4paper]{article}
% \textwidth 26cm
% \evensidemargin 0mm
% \oddsidemargin 0mm
% \topmargin 0mm
\documentclass{article}
\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight26.7cm
\parskip=3pt
\parindent=0pt

\usepackage{graphicx}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
\usepackage{ifpdf}
\usepackage{makeidx}
\ifpdf
 \usepackage[pdftex,colorlinks]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
 \fi

\newtheorem{rem}{Remarque}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\faux}{$\square\;$}
\newcommand{\vrai}{$\square\;$}
%\newcommand{\vrai}{$\boxtimes\;$}
\newcommand{\itemf}{\item\faux}
\newcommand{\itemv}{\item\vrai}

\newtheorem{exo}{Exercice}[section]


\begin{document}

\noindent M1 Alg\`ebre effective \hfill Codes correcteurs \hfill UGA

N.B.: les énoncés ci-dessous utilisent les conventions usuelles de
l'algèbre linéaire, i.e. on utilise des vecteurs colonnes pour représenter
des éléments de $K^n$ et on effectue le produit $Mv$ pour calculer
l'image de $v$ par l'application linéaire de matrice $M$. Les
conventions transposées sont souvent utilisées dans le domaine du codage.
%\Large

{\bf TD Exercice 1}
%Code auto-orthogonal
Déterminer le code linéaire dont la matrice de contrôle est
$$
\left(
\begin{array}{ccccccc}
  0 & 1 & 1 & 1 & 1 & 0 & 0 \\
  1 & 0 & 1 & 1 & 0 & 1 & 0 \\
  1 & 1 & 0 & 1 & 0 & 0 & 1
\end{array}
\right)
$$
Compléter le code en ajoutant un 8ème bit pour réaliser une parité paire.
Le code complété est-il auto-orthogonal~?
Quelle est sa distance de Hamming~?

{\bf TD Exercice 2}
Construire la matrice d'un code de Hamming binaire
en \'ecrivant en colonnes les entiers de 1 \`a 7 en base
2 et en permutant les colonnes de l'identit\'e en fin
de matrice. Coder un exemple de quartet (=4 bits).
Comment corrige-t-on une erreur de transmission~?

{\bf TD Exercice 3}
Code polynomial de polynome g\'en\'erateur $G(x)=x^4+x+1$
et param\`etres $m=4, n=2^4-1=15, k=n-m=11$.\\
On code 11 bits de donn\'ees par un polyn\^ome $P$ ayant $k=11$ coefficients
dans $\Z/2\Z$ (donc de degr\'e 10), on multiplie $P$ par $x^4$ et on
ajoute le reste de la division de $Px^4$ par $G$, le polynome
obtenu $Q$ a $n=15$ coefficients.
\begin{enumerate}
\item Montrer que $Q$ est divisible par $G$\\
On transmet $Q$. Le destinataire v\'erifie alors que le polyn\^ome re\c{c}u 
$\tilde{Q}$ est divisible par $G$, si oui il l'accepte, sinon il le
corrige en tenant compte du reste $R$ de la division de 
$\tilde{Q}$ par $G$.
\item D\'eterminer la liste des restes de division de $x^0$ \`a $x^{14}$
par $x^4+x+1$ dans $\Z/2\Z[X]$, v\'erifiez qu'ils sont distincts 2 \`a
2. En d\'eduire qu'un polynome multiple de $G$ a au moins 3
coefficients non nuls (indication~: consid\'erer le reste par $G$ de
la somme de 2 monomes).
\item Comment peut-on corriger au plus proche une erreur de transmission
sur un coefficient de $\tilde{Q}$~?
\end{enumerate}

{\bf TD Exercice 4}
Soit un code polynomial de polynome g\'en\'erateur
un polynome irr\'eductible primitif $P$ de $\Z/2\Z[X]$.
Montrer que la distance du code ne peut pas \^etre 1 ou 2.
\`A quelle condition a-t-on un code de Hamming binaire~?
Comment peut-on corriger une erreur en utilisant les puissances
d'un g\'en\'erateur de $\Z/2\Z[X]/P$~?

{\bf TD Exercice 5}
% Reed-Solomon, gf.tex?
On se donne un g\'en\'erateur $a$ 
de $F_q^*$ et le polyn\^ome $g(x)=(x-a)...(x-a^{2t})$ (donc $n-k=2t$). 
Montrer que la distance du code polynomial de g\'en\'erateur $g$
est $2t+1$.

{\bf TD Exercice 6}
%Code par interpolation
On travaille sur le corps $\Z/5$, on pose $x_1=2, x_2=-1, x_3=-2, x_4=1$.
On code un couple $y_1,y_2$ en déterminant la droite passant par $(x_1,y_1)$
et $x_2,y_2$, et on complète $y_1,y_2$ par $y_3$ et $y_4$ les
ordonnées des points d'abscisses $x_3,x_4$ de cette droite.
Coder un exemple non trivial ($y_1\neq y_2$).
Modifier un des $y_i$, puis décoder le message modifié
en cherchant deux polynômes $Q_0, Q_1$
non nuls de degrés au plus 2 et 1 tels que $Q_0(x_i)=y_iQ_1(x_i)$
(système linéaire
homogène de 4 équations en les 5 coefficients de $Q_0$ et $Q_1$). Puis
poser $P=Q_0/Q_1$ et en déduire $y_1$ et $y_2$.

% \item Parmi les octets suivants \'ecrits en base 16 lesquels sont-ils de parit\'e paire~:
% \verb|0x7f|, \verb|0x35|, \verb|0x45|, \verb|0xca|\\
% Pour l'un de ces octets qui n'est pas de parit\'e paire, d\'eterminer les octets
% de parit\'e paire qui ne diff\'erent que par un bit de cet octet
{\bf TP Exercice 1}
\'Ecrire un programme permettant de rajouter un bit de parité
à une liste composée de 7 bits. Puis un programme de vérification
qui accepte un octet selon sa parité. 
On représentera
l'octet par une liste de bits ou par un polyn\^ome (le délimiteur ouvrant \verb|poly1[|
permet d'effectuer des opérations arithmétiques polynomiales),
et on effectuera la vérification de deux manières, en comptant
le nombre de 1 ou avec l'instruction de reste de division euclidienne
polynomiale (\verb|rem|).

{\bf TP Exercice 2}
Créez une matrice $M$ de taille 7,4 injective sur le corps $\mathbb{Z}/2$. Puis
un programme qui teste si un vecteur est un mot de code et en
extrait alors la partie avant codage. Vérifiez votre programme
avec un vecteur $Mv$, on doit obtenir un mot de code.\\
Instructions utiles~: \verb|idn| (matrice identité),
\verb|ker| (noyau d'une application linéaire), \verb|rank| (rang),
\verb|tran| (tranposée), \verb|[op(A),op(B)]| (concat\'enation
de matrice), \verb|blockmatrix|.\\
Comparez avec le cas o\`u $M$ est une matrice de code
syst\'ematique.
%\pagebreak
\\
Quelle est la distance de votre code syst\'ematique~?\\
Si votre code linéaire n'est pas de distance 3, modifiez
les 3 dernières lignes pour réaliser un code de distance 3.
Peut-on r\'ealiser la borne de Singleton~? Votre code est-il 1-correcteur parfait~?\\
\'Ecrire un programme corrigeant une erreur \'eventuelle.

{\bf TP Exercice 3}
 \'Ecrire un programme de codage polynomial 
utilisant $g=X^7+X^3+1$\\
N.B. on obtient le polynôme $X^{n-k}$ sous forme
de polynome-liste dans Xcas par {\tt poly1[1,0\$(n-k)]}.

{\bf TP Exercice 4}
Cr\'eer un code de Hamming binaire (15,11) (syndrome,
fonction de codage, fonction de d\'ecodage avec correction)

{\bf TP Exercice 5}
Programmer un code de Hamming binaire (7,4) ou/et (15,11) en
utilisant un code polynomial de polyn\^ome g\'en\'erateur
irr\'eductible primitif de degr\'e 3 ou 4 sur $\mathbb{Z}/2$.

{\bf TP Exercice 6} Programmer le codage d'un code de Reed-Solomon
i.e. obtenu en ajoutant $P(x_{k+1}),...,P(x_n)$
où $P$ est le polynôme d'interpolation du message $y_1,..,y_k$
en $x_1,...,x_k$. Puis le
décodage avec correction d'erreur.
\end{document}
