461 lines
11 KiB
TeX
461 lines
11 KiB
TeX
% !TeX encoding = UTF-8
|
|
\documentclass[10pt,a4paper]{beamer}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage{csquotes}
|
|
\usepackage[french]{babel}
|
|
\usepackage{tabularx}
|
|
\usepackage{amsmath}
|
|
\usepackage{amssymb}
|
|
\usepackage{amsthm}
|
|
\usepackage{calrsfs}
|
|
\usepackage{setspace}
|
|
\usepackage{stmaryrd}
|
|
\usepackage{svg}
|
|
|
|
\usepackage{bashful}
|
|
|
|
\usepackage{pdfpages}
|
|
|
|
\uselanguage{French}
|
|
\languagepath{French}
|
|
|
|
\lstset{
|
|
numbers=left,
|
|
breaklines=true,
|
|
tabsize=2,
|
|
basicstyle=\ttfamily,
|
|
}
|
|
|
|
% Racourcis
|
|
\newcommand{\FD}{\mathbb{F}_2}
|
|
\newcommand\fsign[3]{\item \textbf{#1} : \textit{#2} \hfill Complexité~en~$\mathcal{O}(#3)$\\}
|
|
\newcommand\fsignz[2]{\item \textbf{#1} : \textit{#2}\\}
|
|
\newcommand{\into}{\textrightarrow\:}
|
|
|
|
|
|
%\newtheorem{definition}{Définition}[section]
|
|
%\newtheorem{theoreme}{Théorème}[section]
|
|
%\theoremstyle{remark}
|
|
\newtheorem*{remarque}{Remarque}
|
|
|
|
\renewcommand\unskip\relax
|
|
|
|
|
|
\usetheme{Madrid}
|
|
|
|
%\hypersetup{pdfpagemode=FullScreen}
|
|
|
|
% Transition en fade-in par défaut
|
|
%\addtobeamertemplate{background canvas}{\transfade[duration=0.4]}{}
|
|
|
|
|
|
\author{Samy AVRILLON}
|
|
\title{Étude des codes correcteur d'erreurs}
|
|
\begin{document}
|
|
\begin{frame}
|
|
\maketitle
|
|
\end{frame}
|
|
|
|
|
|
|
|
\section*{Introduction}
|
|
\begin{frame}
|
|
\frametitle{Introduction}
|
|
\pause
|
|
\begin{figure}[h]
|
|
\begin{center}
|
|
\includegraphics[width=.2\linewidth]{gaussV0-llow.png}
|
|
\includegraphics[width=.2\linewidth]{gaussVH-llow.png}
|
|
\hspace{.1\linewidth}
|
|
\includegraphics[width=.2\linewidth]{gaussV0-low.png}
|
|
\includegraphics[width=.2\linewidth]{gaussVH-low.png}
|
|
|
|
\small
|
|
\end{center}
|
|
\caption{Exemple d'application de codes correcteurs}
|
|
\label{gaussEx}
|
|
\end{figure}
|
|
\end{frame}
|
|
|
|
\section*{Sommaire}
|
|
\begin{frame}
|
|
\frametitle{Sommaire}
|
|
\pause
|
|
\tableofcontents[pausesections]
|
|
\end{frame}
|
|
\addcontentsline{toc}{section}{Principe}
|
|
\begin{frame}
|
|
\frametitle{Transmission simple}
|
|
\includesvg[width=0.98\textwidth]{diagramme_transmission_simplet_path.svg}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Transmission avec code correcteur}
|
|
\includesvg[width=0.98\textwidth]{diagramme_transmission_corrige_path.svg}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\centering\Huge Contexte mathématique
|
|
\end{frame}
|
|
\section{Contexte mathématique}
|
|
\subsection{Codes}
|
|
|
|
\begin{frame}
|
|
\frametitle{Codes sur $\FD$}
|
|
\begin{definition}[Code, Codage]
|
|
\pause
|
|
Code $(n,k)$: partie de $\FD^n$
|
|
\pause
|
|
|
|
Codage: application $\FD^k \rightarrow \FD^n$ injective.
|
|
\pause
|
|
|
|
Codage systématique
|
|
\end{definition}
|
|
\pause
|
|
\begin{definition}[Distance de Hamming, Poids d'un mot]
|
|
$$ d(v,w) = \operatorname{card}(i\in \llbracket1,n\rrbracket,v_i \neq w_i)$$
|
|
\pause
|
|
$$ w(v) = d(v,0) = \operatorname{card}(i\in \llbracket1,n\rrbracket,v_i = 0)$$
|
|
|
|
\end{definition}
|
|
\end{frame}
|
|
|
|
\begin{frame}
|
|
|
|
\[
|
|
\scalebox{1.7}{
|
|
$
|
|
\begin{bmatrix}
|
|
1\\0\\0\\1\\1\\0\\1\\1\\0\\0\\1
|
|
\end{bmatrix}
|
|
\begin{bmatrix}
|
|
0\\1\\0\\1\\0\\0\\1\\1\\1\\1\\1
|
|
\end{bmatrix}
|
|
$
|
|
}\]
|
|
|
|
\end{frame}
|
|
\begin{frame}
|
|
|
|
\[
|
|
\scalebox{1.7}{
|
|
$
|
|
\begin{bmatrix}
|
|
\color{blue}1\\\color{blue}0\\0\\1\\\color{blue}1\\0\\1\\1\\\color{blue}0\\\color{blue}0\\1
|
|
\end{bmatrix}
|
|
\begin{bmatrix}
|
|
\color{blue}0\\\color{blue}1\\0\\1\\\color{blue}0\\0\\1\\1\\\color{blue}1\\\color{blue}1\\1
|
|
\end{bmatrix}
|
|
$
|
|
}\]
|
|
|
|
\end{frame}
|
|
|
|
\begin{frame}
|
|
|
|
\[
|
|
\scalebox{1.7}{
|
|
$
|
|
\begin{bmatrix}
|
|
\color{red}1\\0\\0\\\color{red}1\\\color{red}1\\0\\\color{red}1\\\color{red}1\\0\\0\\\color{red}1
|
|
\end{bmatrix}
|
|
\begin{bmatrix}
|
|
0\\\color{red}1\\0\\\color{red}1\\0\\0\\\color{red}1\\\color{red}1\\\color{red}1\\\color{red}1\\\color{red}1
|
|
\end{bmatrix}
|
|
$
|
|
}\]
|
|
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}
|
|
\frametitle{Propriétés des codes}
|
|
\begin{definition}
|
|
\pause
|
|
Capacité de détection $e_d$ et capacité de correction $e_c$.
|
|
\pause
|
|
|
|
La distance minimale.
|
|
|
|
$$d_C = \min_{x,y\in C\times C,x\neq y}\left(d(x,y)\right)$$
|
|
\end{definition}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Distance minimale}
|
|
\begin{theorem}[Distance minimale]
|
|
\pause
|
|
$$ e_d = d_C - 1 \qquad\pause e_c = \left\lfloor\frac{d_C - 1}{2}\right\rfloor$$
|
|
\end{theorem}
|
|
|
|
\end{frame}
|
|
|
|
\begin{frame}
|
|
\frametitle{Code parfait}
|
|
\begin{definition}[Code Parfait]
|
|
\pause
|
|
Jamais d'ambigüité sur la façon de décoder un mot érroné.
|
|
\end{definition}
|
|
\pause
|
|
\textit{Exemple: Code de répétition (n,1)}
|
|
$$C = \left\{\begin{bmatrix}
|
|
0\\\vdots\\0
|
|
\end{bmatrix},
|
|
\begin{bmatrix}
|
|
1\\\vdots\\1
|
|
\end{bmatrix}\right\}$$
|
|
\pause
|
|
$$d_C = n\pause,e_d = n-1\pause,e_c = \left\lfloor \frac{n-1}{2} \right\rfloor$$
|
|
|
|
\pause\centering
|
|
parfait \underline{si et seulement si} $n$ impair
|
|
\end{frame}
|
|
|
|
|
|
\subsection{Codes linéaires}
|
|
\begin{frame}
|
|
\frametitle{Codes linéaire}
|
|
|
|
\begin{definition}
|
|
\pause
|
|
$C$ sous-espace vectoriel de $\FD^n$
|
|
|
|
\pause
|
|
Codage linéaire
|
|
\end{definition}
|
|
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Matrices du code linéaire}
|
|
\begin{definition}[Matrice génératrice]
|
|
\pause
|
|
$$G \in \mathcal{M}_{n,k}(\FD)$$
|
|
|
|
$$Im(G) = C$$
|
|
\end{definition}
|
|
\pause
|
|
\begin{definition}[Matrice de contrôle]
|
|
$$H \in \mathcal{M}_{n-k,n}(\FD)$$
|
|
|
|
$$H\cdot X = 0 \quad\text{\underline{ssi}}\quad X \in C$$
|
|
\end{definition}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Calcul de distances}
|
|
\begin{theorem}[Calcul de distances]
|
|
\pause
|
|
$$d_C = \min_{X\in C, X\neq 0}(w(X))$$
|
|
\pause
|
|
Borne de Singleton:
|
|
$$d_C \leqslant n+1-k$$
|
|
\end{theorem}
|
|
\pause
|
|
\begin{definition}[Erreur et syndrome]
|
|
\pause
|
|
$$E = Z' - Y'$$
|
|
\pause
|
|
$$S(Z) = H \cdot Z$$
|
|
\pause
|
|
$$S(E) = S(Z)$$
|
|
\end{definition}
|
|
\end{frame}
|
|
|
|
\subsection{Codes cycliques}
|
|
|
|
\begin{frame}
|
|
\frametitle{Codes cycliques}
|
|
\begin{definition}[Code cyclique]
|
|
\pause
|
|
$w_1w_2w_3\ldots w_n \in C \implies w_2w_3w_4\ldots w_{n-1}w_nw_1 \in C$.
|
|
\end{definition}
|
|
\pause
|
|
\begin{definition}[Mot binaire associé à un polynôme]
|
|
\pause
|
|
\[
|
|
\begin{bmatrix}
|
|
1\\0\\0\\1\\1\\0\\1\\1\\0\\0\\1
|
|
\end{bmatrix}\mapsto 1 + X^3+X^4+X^6 + X^7 + X^{10} \]
|
|
\end{definition}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Des polynômes bien utiles}
|
|
\begin{theorem}[Théorème fondamental des codes cycliques]
|
|
\pause
|
|
\underline{Unique} polynôme $g$ tel que le mot associé à $g$ engendre $C$ et $g|X^n-1$.
|
|
\vspace{0.4cm}
|
|
|
|
$g$ de degré $n-k$
|
|
\vspace{0.4cm}
|
|
|
|
$(\sigma^i(w))_{i\in \llbracket 0,k-1\rrbracket}$ base de $C$
|
|
\vspace{0.4cm}
|
|
\pause
|
|
Codage naturel associé au polynôme.
|
|
\end{theorem}
|
|
|
|
\end{frame}
|
|
|
|
|
|
\section{Réalisation informatique}
|
|
|
|
\begin{frame}
|
|
\centering\Huge Réalisation Informatique
|
|
\end{frame}
|
|
\subsection{Des structures de données}
|
|
|
|
\begin{frame}
|
|
\frametitle{Créer les structures}
|
|
\pause
|
|
Temps constant :
|
|
\begin{itemize}
|
|
\item\texttt{lor,land,lxor,lsl,lsr,=,<,>}
|
|
\item\texttt{if, for, match, \&\&}
|
|
\end{itemize}
|
|
|
|
\end{frame}
|
|
|
|
\subsubsection{Matrices et vecteurs}
|
|
|
|
\begin{frame}
|
|
\frametitle{Matrices et vecteurs}
|
|
\pause
|
|
\centering\texttt{type vecteur = int}
|
|
|
|
\centering\texttt{type matrice = int list}
|
|
\pause
|
|
\begin{itemize}
|
|
\item Calculs binaires rapides
|
|
\pause
|
|
\item Limitation par l'architecture
|
|
\pause
|
|
\item Possibilité de dépasser virtuellement.
|
|
\end{itemize}
|
|
\pause
|
|
\underline{Fonctions dévelopées: }
|
|
\pause
|
|
\begin{itemize}
|
|
\fsign{produit}{matrice \into vecteur \into vecteur}{k}
|
|
\pause
|
|
\fsign{identite}{int \into matrice}{n}
|
|
\pause
|
|
\fsign{print\_matrice}{int \into matrice \into unit}{nk}
|
|
\fsign{print\_vecteur}{int \into vecteur \into unit}{n}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
|
|
\subsubsection{Polynômes}
|
|
\begin{frame}
|
|
\frametitle{Polynômes}
|
|
\pause
|
|
\centering\texttt{type polynome = int}
|
|
|
|
\pause
|
|
\vspace{0.4cm}
|
|
Mêmes remarques.
|
|
|
|
\pause
|
|
\vspace{0.5cm}
|
|
\underline{Fonctions dévelopées: }
|
|
\pause
|
|
\begin{itemize}
|
|
\fsign{degre}{polynome \into int}{p}
|
|
\pause
|
|
\fsign{polmul}{polynome \into polynome \into polynome}{\min(p,q)}
|
|
\pause
|
|
\fsign{poldiveuc}{polynome \into polynome \into polynome $\times$ polynome}{p^2}
|
|
\pause
|
|
\fsign{print\_polynome}{polynome \into unit}{p}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}
|
|
\frametitle{Fonctions d'affichages}
|
|
\begin{figure}[h]
|
|
\begin{center}
|
|
\includesvg[scale=.3]{print_output_path.svg}
|
|
\caption{Exemple d'affichage de vecteur,matrice et polynômes}
|
|
\end{center}
|
|
\end{figure}
|
|
\end{frame}
|
|
\subsubsection{Codes}
|
|
\begin{frame}
|
|
\frametitle{Structures des codes}
|
|
\pause
|
|
\texttt{type code\_lineaire = \{\\\hspace{0.4cm}
|
|
k : int;\\\hspace{0.4cm}
|
|
n : int;\\\hspace{0.4cm}
|
|
g : Math.matrice;\\\hspace{0.4cm}
|
|
h : Math.matrice; \\\}
|
|
}
|
|
\pause
|
|
\vspace{0.4cm}
|
|
|
|
|
|
\texttt{type code\_cyclique = \{\\\hspace{0.4cm}
|
|
k : int;\\\hspace{0.4cm}
|
|
n : int;\\\hspace{0.4cm}
|
|
pol : Math.polynome;\\ \}
|
|
}
|
|
|
|
|
|
\pause
|
|
\vspace{0.4cm}
|
|
\begin{itemize}
|
|
\fsign{systematiqueFromRedondance}{int \into int \into matrice \into code\_lineaire}{k}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\subsection{Liste des fonctions}
|
|
|
|
\begin{frame}
|
|
\frametitle{Fonctions de codage/décodage}
|
|
\pause
|
|
\begin{itemize}
|
|
\fsign{encoder}{code\_lineaire \into vecteur \into vecteur}{k}
|
|
\pause
|
|
\fsign{appartenir}{code\_lineaire -> vecteur -> bool}{n}
|
|
\pause
|
|
\fsign{distance\_minimale}{code\_lineaire -> int}{n2^{d_C}}
|
|
\pause
|
|
\fsignz{decoder}{code\_lineaire \into vecteur \into Math.vecteur}
|
|
\pause
|
|
\fsign{genererClasses}{code\_lineaire \into classes\_latérales}{n\cdot2^k}
|
|
\pause
|
|
\fsign{decoder2}{classes\_latérales \into vecteur \into vecteur}{n}
|
|
\end{itemize}
|
|
|
|
\end{frame}
|
|
|
|
|
|
\begin{frame}
|
|
|
|
\end{frame}
|
|
\begin{frame}
|
|
\frametitle{Annexes}
|
|
\end{frame}
|
|
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,language=Caml,frame=single,linerange={1-26}]{../Math.mli}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,language=Caml,frame=single,linerange={29-34}]{../Math.mli}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,language=Caml,frame=single,linerange={1-27}]{../Code.mli}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,language=Caml,frame=single,linerange={29-39}]{../Code.mli}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,linerange={48-59},language=Caml,frame=single]{../Math.ml}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,linerange={105-128},language=Caml,frame=single]{../Math.ml}
|
|
\end{frame}
|
|
\begin{frame}
|
|
\lstinputlisting[basicstyle=\scriptsize,breaklines=true,linerange={140-166},language=Caml,frame=single]{../Code.ml}
|
|
\end{frame}
|
|
|
|
|
|
\end{document}
|