% !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}