com101.md

COM101

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2014: Sciences de l'Information

[TOC]

I. Codage de Source

Préliminaires de Probabilités

• source : ensemble fini composé de symboles provenant d'un alphabet $A$ avec une densité de probabilité $p:A\to [0,1]$ satisfiant toujours $\sum_{s\in A} p(s)=1$
• bits ($\log_2$) / nats ($\log_e$) / bans ($\log_{10}$)
• source équiprobable = source uniforme : $p(s)=\frac{1}{card(A)}$
• événements $E$ : sous-ensembles de $A$ où $P(E)=\sum_{s\in E}p(s)$
• indépendance : $P(B \cap C)=P(B)P(C)$
• probabilité conditionnelle : $P(B|C)=\frac{P(B \cap C)}{P(C)}$
• source composée : si son alphabet $A=A_1\times\ldots\times A_n$
• sources marginales : composantes individuelles d'une source composée $S=(S_1,\ldots,S_n)$
• sources indépendantes : si $p(s_1,\ldots,s_n)=p(s_1)\ldots p(s_n)$
• densité conditionnelle : $p(s_2|s_1)=\frac{p(s_1,s_2)}{p(s_1)}$

Information et Entropie

• information $I$ de l'événement $E$ : $I(E)=-\log_2 P(E)$
• unité d'information : $1:bit=1:shannon$
• entropie d'une source $S$ : $H(S)=-\sum_{s\in A} p(s) \log_2 p(s)$ (si $p(s)=0$ alors $p(s)\log_2 p(s) =0$)
• inégalité de Jensen : $\log_2(\alpha_1 x_1+\ldots+\alpha_m x_m) \ge \alpha_1 \log_2 x_1 +\ldots + \alpha_m \log_2 x_m$
• $0 \le H(S) \le \log_2(m)$ où $H(S)=0$ si la source est certaine et $H(S)=\log_2(m)$ si les symboles de la source sont equiprobables
• $H(S_1,\ldots,S_n) \le H(S_1)+\ldots+H(S_n)$ où l'égalité est respectée si les sources marginales sont indépendantes

Codage de Source

• dictionnaire $C$ est un ensemble de suites construites grâce à l'alphabet A, un élément de $C$ est appelé un mot de code
• encodage/code de source : $ \Gamma : A \to C$
• longueur d'un mot $l(c)$ est le nombre de symboles, si toutes les mots ont la même longueur, il s'agit d'un code à longueur constante (sinon longueur variable)
• arbre complet du code : $D$ branches où $D$ est le nombre de symboles de code et $D^{L_{max}}$ noeuds possibles
• décodage unique : s'il l'application est bijective
• code instantané/code sans préfixe : s'il est à décodage unique et si les mots de code peuvent être décodé sans attendre la fin du message
• théorème de Kraft-McMillan : si le code est à décodage unique alors il satisfait l'inégalité de Kraft $D^{-l_1}+\ldots+D^{-l_m}\le 1$ (réciproquement si les nombres $l_1,\ldots,l_m$ satisfont l'inégalité alors il existe un code instantanée correspondant )

Efficacité d'un Code de Source

• longueur moyenne d'un code : $L(\Gamma)=\sum_{s\in A}p(s)l(\Gamma (s))$ (unité : symbole de code par symbole de source)
• inégalité de l'entropie : $L(\Gamma) \ge \frac{H(S)}{\log_2 D}$
• code de Shannon-Fano : code dont la longueur $l_i=\lceil -\log_D p_i \rceil \ge -\log_D p_i$
• inégalité de l'entropie pour Shannon-Fano : $\frac{H(S)}{\log_2(D)} \le L(\Gamma_{SF}) < \frac{H(S)}{\log_2(D)}+1$
• code optimal (code de Huffman) : partant des noeuds on regroupe les poids les plus faibles ensemble, et ainsi de suite, puis on réparti le codage depuis le noeud parent commun
• $L(\Gamma_H) \le L(\Gamma)$

Entropie Conditionnelle

• entropie conditionnelle : $H(S_2|S_1=s_1)=-\sum_{s_2\in A_2}p(s_2|s_1)\log_2 p(s_2|s_1)$ et $H(S_2|S_1)=\sum_{s_1\in A_1}H(S_2|S_1=s_1)p(s_1)$
• $H(S_1,S_2)=H(S_1)+H(S_2|S_1)=H(S_2)+H(S_1|S_2)$ et $H(S_1)\le H(S_1,S_2)$
• conditionner réduit l'entropie : $H(S_2|S_1)\le H(S_2)$ et l'égalité est valide si les sources sont indépendantes
• $H(S_3|S_1,S_2)\le H(S_3|S_2)$ si $S=(S_1,S_2,S_3)$
• règle d'enchainement : $H(S_1,S_2,\ldots,S_n)=H(S_n|S_1,S_2,\ldots,S_{n-1})+H(S_{n-1}|S_1,S_2,\ldots,S_{n-2})+\ldots+H(S_3|S_1,S_2)+H(S_2|S_1)+H(S_1)$
• $S_2$ est fonction de $S_1$ ssi $H(S_2|S_1)=0$ : $H(S_1,S_2)=H(S_1)$ et $H(S_2)\le H(S_1)$

Théorème du Codage de Source

• source étendue : $S^n=(S_1,\ldots,S_n)$ à $n$ composantes
• source étendue régulière : si $H(S)=\lim_{n\to\infty}H(S_n)$ (entropie d'un symbole) et $H^*(S)=\lim_{n\to\infty}H(S_n|S_1,S_2,\ldots,S_{n-1}$ (entropie par symbole) existent et sont finies
• entropie par symbole $\le$ entropie d'un symbole : égalité si les sources marginales sont indépendantes
• entropie d'un bloc : $H^*(S)=\lim_{n\to\infty}\frac{H(S_1,\ldots,S_n)}{n}$
• théorème de Césàro : si une suite $u_n$ converge vers une limite quand $n\to\infty$ alors la moyenne $\frac{u_1+\ldots+u_n}{n}$ converge aussi vers la même limite
• théorème du codage de source : $\lim_{n\to\infty}\frac{L_H^n}{n}=\lim_{n\to\infty}\frac{L_{SF}^n}{n}=\frac{H^*(S)}{\log_2 D}$
• source stationnaire (régulière) : si la source ne veilli pas, c'est-à-dire que $(S_{K+1},\ldots,S_{n+k})$ et $(S_1,\ldots,S_n)$
• entropie par symbole $\le$ entropy d'un symbole (si régulière)
• rapport de compression : $\frac{L^n}{n\lceil \log_2 card(A) \rceil}\le 1$
• bits par symbole : $\frac{L^n}{n}$

II. Cryptographie

La Cryptographie

• texte clair : $P$
• clé : $K$
• texte chiffré : $C=E_K(P)$
• déchiffrement : $P=D_K(C)$
• symétrique si les clés de chiffrement est la même sinon asymétrique
• chiffre de César : rotation de $K$ lettres
• chiffrement par subsitution (monoalphabétique) : remplacement d'un caractère par un autre
• chiffre de Vigenère (polyalphabétique) : subsitution d'un mot repété autant de fois qu'il faut
• le chiffre de Vernam (masque à usage unique) : $C=P\oplus K$ et $P = C\oplus K$
• cryptographie symétrique : $H(P)\le H(C)$
• confidentialité parfaite : si les sources qui délivrent les messages $P$ et $C$ sont indépendantes $H(P)\le H(C) \le H(K)$

Arithmétique

• division euclidienne : $a=bq+r$ et $0\le r \le |b|-1$
• factorisation : $a=p_1^{\alpha_1}\ldots p_k^{\alpha_k}$ où $p$ sont des nombres premiers
• PGCD : plus grand commun diviseur
• premiers entre eux : si $pgcd(a,b)=1$
• congruence : $a$ est congru à $b$ modulo $m$ si $a\equiv b\mod m$ ($m$ est appelé le module)
• $a\equiv b \mod m$ ssi $m$ divise $b-a$
• relation d'équivalence (réflexivitié, symétrie, transitivité)
• arithmétique modulaire : si $a\equiv a'\mod m$ et $b\equiv b' \mod m$ alors $a+b \equiv a'+b' \mod m$, $ab\equiv a'b'\mod m$ et $a^n\equiv a'^n\mod m$

Arithmétique Modulaire

• classe de congruence : l'ensemble $[a]_m$ des entiers tels que $a\equiv a' \mod m$
• représentant : nombre appartenant à la classe $+kM$
• il y a $m$ classe de congrence modulo $m$
• ensemble des classes de congruence : $\mathbb Z/m\mathbb Z$ (somme, multiplication et puissance y sont définis)
• forme réduite : $0\le r \le m-1$
• somme, multiplication défini
• diviseur de zéro : si $ab=0$
• décomposition de l'exposant pour faciliser le calcul
• inverse : $aa'=[1]_m$ (si $a$ et $m$ sont premiers entre eux, $a$ est toujours inversible)
• algorithme d'Euclide : $pgcd(a,b)=pgcd(b,r)$ récursif
• identité de Bézout : $au+bv=pgcd(a,b)$
• indicatrice d'Euler : $\varphi (m)$ est le nombre d'éléments inversible dans $(\mathbb Z/m\mathbb Z,\cdot)$

Élements d'Algèbre Asbtraite

• groupe : ensemble muni d'une opération binaire $(G,\star)$
  • fermeture
  • associativité : $a\star (b\star c)=(a\star b)\star c$
  • neutre : $\exists e\in G; a \star e = e\star a = a$
  • symétrique (inverse/opposé) : $\exists a' \in G; a\star a'=e$
  • commutativité : $a \star b =b \star a$ (groupe commutatif ou abélien)
• $\mathbb Z/m\mathbb Z^*$ est l'ensemble des éléments inversibles de $\mathbb Z/m\mathbb Z$
• $(\mathbb Z/m\mathbb Z^*,\cdot)$ est un groupe commutatif
• opération produit : deux groupes $G\times H=(a,b)\star (a',b')=(a\star a', b\star b')$
• période : nombre d'opération pour devenir neutre $a\star \ldots \star a=e$
• isomorphisme : une application entre deux groupes (de même période) $(G,\star)$ et $(H,\oplus)\quad\varphi : G \to H$ telle que $\varphi$ bijective et $\varphi (a\star b)=\varphi (a) \oplus \varphi(b)$
• cardinal d'un groupe : la période divise le cardinal
• théoreme de Fermat : si $p$ est premier, alors $a^p\equiv a \mod p$ pour tout $a$

Cryptographie Asymétrique

• théoreme des Restes Chinois : si deux entiers sont premiers entre eux alors l'application $[k]{m_1 m_2} \to [k]{m_1}[k]_{m_2}$ est bijective et c'est un isomorphisme pour les addition et la multiplication, sinon ni injective ni surjective
• RSA : messages considérés comme des entier modulo $K$ répartis en bloc d'une longueur entre $0$ et $K-1$
  • clé publique : module $K=pq$ où $p$ et $q$ sont des nombres premiers
  • clé privé : $k=ppcm(p-1,q-1)$
  • chiffrement : $C=[P]_K^e$ où $e$ est un exposant public qui doit être premier avec $K$ (souvent $e=65537$)
  • déchiffrement : grâce à l'inverse $[f]_k=[e]_k^{-1}$, alors $[P']_K=[C]_K^f$
• nombres premiers sûrs : $p=2p'+1$ où $p'$ est aussi premier

III. Codes Correcteurs

Les Codes Correcteurs ou Détecteurs

• rendement d'un code de longueur $n$ : défini sur un alphabet $A$ et un sous-ensemble $C$ de $A^n$, le rendement vaut $r=\frac{1}{n}\log_{card(A)}card(C)=\frac{k}{n}$
• distance de Hamming : soit deux mots de même longueur, la distance de Hamming est le nombre de positions où les symboles diffèrent $d(x,y)$
  • $d(x,y)\ge 0$ et égalité seulement si les deux mots sont égaux
  • symétrie
  • inégalité triangulaire $d(x,z) \le d(x,y)+d(y,z)$
• distance minimale d'un code : $d_{min}(C)=min_{x,y\in C,x\not = y} d(x,y)$
• poids d'un effacement : nombre de positions effacées dans un canal à effacements
• poids d'une erreur : nombre de positions erronées dans un canal à erreurs
• détection d'erreurs : erreurs de poids $p< d_{min}(C)$
• correction d'effacements : effacements de poids $p< d_{min}(C)$
• correction d'erreurs : erreurs de poids $p< \frac{d_{min}(C)}{2}$
• borne de singleton : $d_{min}(C)\le n(1-r)+1$

Corps Finis et Espaces Vectoriels

• corps commutatif : ensemble muni de deux opérations binaires $(K,+,\cdot)$
  • addition est un groupe commutatif avec comme élément neutre $0$
  • multiplication sans $0$ est un groupe commutatif avec comme élément neutre $1$ (tous les éléments sauf $0$ sont inversibles)
  • distributitivé : $a\cdot (x+y) = a\cdot x+a\cdot y$
• caractéristique : nombre premier tel que $p\cdot 1 = 0$
• cardinal
  • puissance de sa caractéristique
  • tous les corps finis de même cardinal sont isomorphes
  • pour tout nombre premier $p$, il exite un corps fini de cardinal $p^m$
• espace vectoriel
  • associativité pour la multiplication scalaire : $\lambda(\mu \vec v)=(\lambda\mu )\vec v$
  • identité : $1\cdot \vec v = \vec v$
  • distributitivé : $\lambda(\vec u + \vec v)=\lambda \vec u + \lambda \vec v$ et $(a+b)\vec u = a\vec u + b\vec u$
• combinaison linéaire : $\vec u = \sum_{i=1}^m \lambda_i \vec v_i$
• independance linéaire : ssi $0 = \sum_{i=1}^m \lambda_i \vec v_i$
• base : les vecteurs sont une base s'ils sont linéairement indépendants et engendre l'espace vectoriel
• dimension (rang) : cardinal des bases
• espace vectoriel fini de dimensions $n$ : $card(V)=card(K)^n$

Codes Linéaires

• code linéaire : si l'alphabet est un corps fini $K$ et le code est un sous-espace vectoriel de $K^n$
• dimension du code linéaire $k$ : nombre de mot de code $card(K)^k$ ainsi le rendement $\frac{k}{n}$
• poids de Hamming : c'est le nombre de composant non nulle $\vec w = d(\vec 0, \vec x)$
• distance minimal : $d_{min}(C)=min_{\vec c \in C, \vec x \not = \vec 0}w(\vec x)$
• matrice génératrice : matrice formé de base
• encodage des mots : $\vec x = \vec u G$
• forme systématique : matrice génératrice $G=[I_k P]$
• contrôle de parité : équations permettant la vérification du mot de code
• syndrome : $\vec s = \vec y H^T$ si cela est égal à zéro, pas d'erreur
• matrice de contrôle : $H=[-P^T I_{n-k}]$

Codes de Reed-Solomon

• code de Reed Solomon de paramètres (longueur $n$, dimensions $k$)
• polynôme : $x\to P(x)=a_1+a_2x+\ldots + a_{m+1}x^m$
• Reed-Solomon : alphabet est un corps fini $K$ de cardinal $\ge n$ avec $n$ éléements distincts de $K$, $a_1,\ldots, a_n$, une suite de symbole $\vec u =(u_1,\ldots,u_k)\in K^k$ est encodée par $\vec x_i = P_{\vec u}(a_i)$
• racine : s'il existe $k$ éléments tous disctints satifaisant $P_{\vec u}(a_i)=0$, alors $\vec u = \vec 0$
• polynome d'interpolation de Lagrange : $Q_i(x)=\frac{(x-a_1)\ldots(x-a_{i-1})(x-a_{i+1})(x-a_k)}{(a_i-a_1)\ldots(a_i-a_{i-1})(a_i-a_{i+1})\ldots (a_i-a_k)}$ et $P(x)=x_1Q_1(x)+\ldots+x_kQ_k(x)$
• linéarité : un code RS est un code en bloc linéaire de taille $n$ et dimensions $k$
• distance minimale : $d_{min}=n-k+1$ (atteint la borne de Singleton)

Annexes

Mod97-10

1. ajouter $00$ à la fin du nombre
2. calculer le reste $r$ de la division par $97$ du nombre obtenu
3. le complément à 98 du reste $r$ et les ajouter à la fin du nombre
4. vérification : la division par $97$ doit donner $1$

Calcul de l'inverse

$$ \begin{align} bezout(21,122)& &[21]{122}^{-1}=[93]{122}\ euclide(21,122)& &u=-29,v=5\ euclide(122,21)&q=5,r=17 &u=5,v=-29\ euclide(21,17)&q=1,r=4 & u-4,v=5\ euclide(17,4)&q=4,r=1 & u=1,v=-4\ euclide(4,1)&q=4,r=0 & u=0,v=1\ euclide(1,0)&d=1\to & u=1,v=0 \end{align} $$