\documentclass[12pt]{report}
\usepackage{kbexo}
\course{Arithmétique -- M1MA7W01}
\formation{Master 1 CSI}
\num{7}
\def\exoskip{5pt plus 15pt minus 1pt}

\begin{document}
\exotitle

\exo[Borne de Singleton] Soit $C\subset (\FM_q)^n$ un code linéaire de
paramètres $(n,k,d)$.
\Q Montrer que les mots (de longueur $n - (d-1)$) obtenus en supprimant les
$d-1$ premières coordonées des mots de $C$ sont distincts.

\Q En déduire que $n \geq k + d - 1$.

\Q Plus généralement, si on ne suppose plus $C$ linéaire, mais simplement
$C\subset (\FM_q)^n$ de distance minimale $d$, montrer que $\#C \leq
q^{n-d+1}$.

\exo[Borne de Hamming] Soit $C\subset (\FM_q)^n$ un code de distance
minimale $d$. On sait que $C$ est $t$-correcteur, où $t = \floor{(d-1)/2}$.

\Q Montrer qu'une boule de Hamming de rayon $t$ possède
$\displaystyle m := \sum_{k=0}^t \binom{n}{k} (q-1)^k$
éléments.

\Q Montrer que $\#C \leq q^n / m$.

\exo On définit sur $(\FM_q)^n$ le produit
$$(x_1,\dots,x_n)\cdot (y_1,\dots,y_n) := \sum_{i=1}^n x_i y_i.$$
On définit le code dual $C^\bot$ d'un code linéaire $C\subset (\FM_q)^n$ par
$$ C^\bot := \set{x\in(\FM_q)^n \colon x\cdot y = 0
~\text{pour tout $y\in C$}}$$

\Q Montrer que $C^\bot$ est un code linéaire.

\Q Montrer que si $C$ est cyclique, alors $C^\bot$ l'est aussi.

\Q Montrer que si $C$ est de dimension $k$, alors $C^\bot$ est de dimension
$n-k$.

\Q Montrer que $\big(C^\bot\big)^\bot = C$.

\exo Soient $C_1$ et $C_2$ deux codes linéaires sur $\FM_q$, de paramétres
respectifs $(n_i,k_i,d_i)$, pour $i=1,2$. On définit
$$ C_1 \oplus C_2 = \set{(x,y)\in (\FM_q)^{n_1} \times (\FM_q)^{n_2}\colon
x\in C_1, y\in C_2},$$
ainsi que si $n_1 = n_2 = n$,
$$ C_1 * C_2 = \set{(x,x+y)\in (\FM_q)^n \times (\FM_q)^n\colon
x\in C_1, y\in C_2},$$

\Q Montrer que $C_1\oplus C_2$ est un code linéaire, de paramètres
$$\big(n_1+n_2,k_1+k_2,\min(d_1,d_2)\big).$$
\Q Montrer que $C_1 * C_2$ est linéaire, de paramètres
$\big(2n,k_1+k_2,\min(2d_1,d_2)\big)$.

\exo[Code de Hamming] Soit $g(X)\in \FM_2[X]$ un polynôme primitif
(irréductible) de degré $m$. Il définit un code cyclique $\gen{g}$ de longeur
$n = 2^m-1$ dans $\FM_2[X]/(X^n-1)$, vu comme $\FM_2$-espace vectoriel de
dimension $n$. On note $\alpha$ la classe de $X$ dans $\FM_2[X]/(g)$.

\Q Montrer que le code $C$ est constitué des polynômes modulo $X^n-1$
qui s'annulent en $\alpha$.

\Q Montrer que la dimension de $C$ est $n - m$.

\Q On suppose que $m > 1$. Montrer que la distance minimale de $C$ est $3$.

\Q Écrire la matrice génératrice d'un tel code pour $m = 3$. Écrire une
matrice génératrice de son code dual.

\end{document}

\exo[Un tour de prestidigitation] Un spectateur $A$ choisit un nombre entre
$0$ et $15$, disons $b_3b_2b_1b_0$ en base $2$. Le prestidigitateur
pose les 7 questions suivantes à $A$ pour essayer de deviner le nombre
choisi. $A$ doit y répondre par oui $(1)$
ou par non $(0)$, et peut mentir au plus \emph{une} fois:
\begin{enumerate}
  \item A-t-on $b_3 = 1$ ?
  \item A-t-on $b_2 = 1$ ?
  \item A-t-on $b_1 = 1$ ?
  \item A-t-on $b_0 = 1$ ?
  \item Est-il dans $\set{1,2,4,7,9,10,12,15}$ ?
  \item Est-il dans $\set{1,2,5,6,8,11,12,15}$ ?
  \item Est-il dans $\set{1,3,4,6,8,10,13,15}$ ?
\end{enumerate}
Soit $(m_1,\dots,m_7)\in (\FM_2)^7$ le vecteur des réponses fournies par $A$.

