--- title: I4 Chaine de transmission numérique tags: ESIEE --- Chaine de transmission numérique === Auteur: Rémi Maubanc Professeur: M. Dewaghe Emploi du temps - 1ère partie: - 6h de CM - 2h de TD - 4h de TP (Contrôle TP 0,5 ECTS) - 1h de Contrôle (0,75 ECTS) # Codage source ## Introduction au codage source-canal Codage : On a des données initiales que l'on veut adapter à une transmission. On les transfome en données utiles et vice-versa (bijection). L'idée c'est d'avoir une correspondance entre les deux ensembles. - Des informations - Interne au système - Code de représentation : Binaire, Décimal, Héxadécimal, Base n, ASCII, Unicode... **Remarque** : - $p$ places binaire: $2^{p}$ mots - $k$ mots: $⌈log_{2}(k)⌉$ places binaire - Code de communications: MORSE (les symbole les plus fréquents ont les codes les plus court) - Détection des erreurs (et correction): On ajoute une règle et de la redondance - Bit de parité : Redondance structurelle - Sécurité Sociale : $13 char + 2 char \equiv o(mod~97)$ - CRC : Code Cyclique - Cryptage : Protéger l'information d'un tier. - Code symétrique : César, Vigenère, AES... - Code asymétrique : SSL, GPG... - Compression - Avec perte: mp3, mp4... - Sans perte: Huffman, LZ78... - Du signal - Adaptation au support: Filaire, Aérien... ### Canal de transmission Canal discret sans mémoire = 3 éléments suivants : - Entrée du canal : va $X$, n'admettant que les symboles d'un alphabet $C = \{c_{1}, c_{2},...,c_{r}\}$ - Sortie du canal : va $Y$, délivrant des symboles d'un alphabet $D = \{d_{1}, d_{2},...,d{k}\}$ - Matrice de transition définie par : $P=(p_{i,j})$ et $p_{i,j} = p_{j/i}$ CBS (Canal Binaire Symétrique): $p =$ Probabilité d'erreur du canal $p = \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix}$ ![](https://i.imgur.com/o2koX4n.png) ### Source d'information Une source d'information $S$ délivre des symboles $S_{i}$ d'un alphabet $S = \{s_{1}, s_{2},...,s_{r}\}$ avec une probabilité $p_{i}$ d'occurrence. On modélise cette source par la variable aléatoire $S$ avec les probabilités : $p_{i} = P(S=s_{i})$ **Code :** Un code $C = \{c_{1}, c_{2},...,c_{r}\}$ est un sous-ensemble de $A*$ (A = Alphabet). Les éléments $c_{i}$ sont les mots du code. On note par $l_{i}$ la longueur du mot $c_{i}$. Code binaire, en bloc (tous les mots ont la même longueur), à préfixe, uniquement décodable (décodage déterministe), longueur moyenne... Exemple: | Codage 1 | Codage 2 | | -------- | -------- | | $A \leftrightarrow 00$ | $A \leftrightarrow 0$ | | $B \leftrightarrow 01$ | $B \leftrightarrow 10$ | | $C \leftrightarrow 10$ | $C \leftrightarrow 110$ | | $D \leftrightarrow 11$ | $D \leftrightarrow 111$ | - **Source équiprobable :** $P(A) = P(B) = P(C) = P(D) = \frac{1}{4}$ - $L_{1} = 2$ bits - $L_{2} = \frac{1}{4}.1 + \frac{1}{4}.2 + \frac{1}{4}.3 + \frac{1}{4}.3 = \frac{9}{4} = 2,25$ bits - **Source :** $P(A) = \frac{1}{2}$, $P(B) = \frac{1}{4}$, $P(C) = P(D) = \frac{1}{8}$ - $L_{1} = \frac{1}{2}.2 + \frac{1}{4}.2 + \frac{1}{8}.2 + \frac{1}{8}.2 = 2$ bits - $L_{2} = \frac{1}{2}.1 + \frac{1}{4}.2 + \frac{1}{8}.3 + \frac{1}{8}.3 = 1,75$ bits ### Shannon - Information: Ce qui est nouveau - Reste: Redondant - Quantité d'information (Shannon): - Source - Canal - Quantité d'information d'un symbole $s_{i}$: $$I(s_{i}) = Log_{2}(1/p_{i})$$ ### Information et entropie L'entropie de la source d'information $S$ est définie par : $$H(S) = E(I(S)) = -\sum_{i=1}^{r}p_{i}Log_{2}(p_{i})$$ Remarque: - $H(S)$ : Quantité d'information moyenne minimale pour chaque symbole de la source $S$ **Exemple**: $$ X_{1} = \begin{bmatrix} 0 & si~pair & \frac{1}{2} \\ 1 & si~pair & \frac{1}{2} \end{bmatrix} \\ X_{2} = \begin{bmatrix} 0 & si~1,2 & \frac{1}{3} \\ 1 & si~3,4 & \frac{1}{3} \\ 2 & si~5,6 & \frac{1}{3} \end{bmatrix} \\ X_{3} = valeur~"tierce" $$ $H(X_{1}) = -\frac{1}{2}.log_{2}(\frac{1}{2}) -\frac{1}{2}.log_{2}(\frac{1}{2}) = -log_{2}(\frac{1}{2}) = 1$ bit $H(H_{2}) = -3.\frac{1}{3}.log_{2}(\frac{1}{3}) = -log_{2}(\frac{1}{3}) = log_2{3} = 1,585$ bits $H(X_{3}) = -6.\frac{1}{6}.log_{2}(\frac{1}{6}) = log_{2}(6) = 2,585$ bits $$ \begin{array}{c c c c c} 19 & A & B & C & D \\ & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ & 00 & 01 & 10 & 11 \\ 29 & AAAA & BB & C & D \\ & \frac{4}{8} & \frac{2}{8} & \frac{1}{8} & \frac{1}{8} \\ \end{array} $$ $H(S) = -\sum_{i=1}^{4} \frac{1}{4}log_{2}(\frac{1}{4}) = log_{2}(4) = 2$ $H(S) = -\frac{1}{2}log_{2}(\frac{1}{2}) - \frac{1}{4}log_{2}(\frac{1}{4})-\frac{1}{8}log_{2}(\frac{1}{8})-\frac{1}{8}log_{2}(\frac{1}{8})$ $H(S) = 1,75$ bits $$ H(S) = \Bigg|\begin{array}{l} -p.log_{2}(p) - (1 - p)log_{2}(1 - p)~si~0 < p < 1 \\ 0~(p = 0, p = 1) \end{array} $$ Entropie $H_{max} = log_{2}(r)$ Redondance $R = \frac{H_{max} - H(r)}{H_{max}} = 1 - \frac{H(s)}{H_{max}}$ $$ H(X) = -\sum_{x \in X} P(X = x) log_{2}(P(X = x))\\ H(Y/_{Y=x}) = -\sum_{y \in Y} P(Y = y/_{X=x}) log_{2}(P(Y = y/_{X=x})) \\ H(Y/_{X})= \sum_{x \in X} H(Y/_{X = x}) P(X=x)\\ $$ incertitude sur $Y$ lorsque l'on connaît $X$ $$ H(X) = H(Y) - H(Y/_{X}) = H(X) - H(X/_{Y}) **Ex:** Capacité du CBS $$ P=\begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix} = \begin{bmatrix} P(Y=0/_{X=0}) & P(Y=1/_{X=0}) \\ P(Y=0/_{X=1}) & P(Y=1/_{X=1}) \end{bmatrix} $$ $$ C = I(X,Y) = H(Y) - H(Y/_{X})\\ H(Y) = -\sum_{y \in Y}log_{2}(P(Y=y)) = -P(Y=0)log_{2}(P(Y=0)) - P(Y=1)log_{2}(P(Y=1)) \\ P(Y=0) = P(Y=0/_{X=0}).P(X=0) + P(Y=0/_{X=1})P(X=1)\\ P(Y=0) = (1 - p)\frac{1}{2} + p.\frac{1}{2} = \frac{1}{2} $$ ### Théorème de Shannon #### Théorème de codage de source $H(S) \leq L < H(S) + \frac{1}{k}$ La compression maximale est minoré par la source. Autrement, on ne représente pas bien la source (perte) #### Théorème de codage canal $H(S).D_{S} \leq C.D_{C}$ La quantité d'information produite par la source doit être inférieur à la capacité du canal de transmission. On pourra construire un code de détection et de correction d'erreur. **Ex:** $$\begin{array}{c c c c c c c} A & B & C & D & E & F & G \\ 0.4 & 0.2 & 0.15 & 0.1 & 0.05 & 0.05 & 0.05 \\ \end{array}\\ $$ $$ \begin{array}{c c c} &Codage 1 & Codage 2 \\ A & 00 & 0 \\ B & 01 & 100 \\ C & 100 & 101 \\ D & 101 & 110 \\ E & 1100 & 1110 \\ F & 1101 & 11100 \\ G & 111 & 11111 \end{array} $$ $L_{1} = 2*0,4+2*0,2+3*0,15...=2,5$ bits $L_{2} = 1*0,4+3*0,2+3*0,15...=2,45$ bits $H_{S} = -0,4log_{2}-0,2log_{2}(0,2)...=2,38$ bits ## Le codage de source Inégalité de K.M $C =$ Décodable déterministe $\leftrightarrow \sum_{i=1}^{r} 2^{-l_{i}} < 1$ $C = \Big\{c_{1}, c_{2},...,c_{n}$ $l_{i} = l(c_{i})$ **Exercice :** $$ \begin{array}{c c c c c c} s_{i} & p_{i} & C & I & II & III \\ s_{1} & \frac{1}{2} & c_{1} & 0 & 0 & 0 \\ s_{2} & \frac{1}{4} & c_{2} & 1 & 10 & 01 \\ s_{3} & \frac{1}{8} & c_{3} & 00 & 110 & 011 \\ s_{4} & \frac{1}{8} & c_{4} & 11 & 111 & 0111 \\ \end{array} $$ - A préfixe ? Uniquement décodable ? - non, non (OO -> s1, s2, s3) - oui, oui - non, oui - $L_{I}, L_{II}, L_{III}$ ? - $L_{I}$ - $H(S)$, code optimal ? - $KM_{I}, KM_{II}, KM_{III}$ ? ### Techniques primitives RLE = Run Length Encoding Codage des répétitions : successions d'octets identiques Codage topologique Codage relatif Codage de Huffman ![](https://i.imgur.com/7Ihe6FE.png) | Antécédents | $P_{i/j}$ | Code | | -------- | -------- | -------- | | Sachant A | ![](https://i.imgur.com/Mp16vM2.png) | ![](https://i.imgur.com/Za2lP7V.png) | | Sachant B | ![](https://i.imgur.com/pV2fAlN.png) | ![](https://i.imgur.com/4UmZpA5.png) | | Sachant C | A: 1 | 0 | | Sachant D | ![](https://i.imgur.com/2FxjlKG.png) | ![](https://i.imgur.com/DoXZYmN.png) | # Codage canal ## Codes détecteurs et correcteurs d'erreurs ### Code Hamaring $C~[7,4]$ **Remarque**: $C~[n,k,d]$ où $d =$ distance du code $c=(u_{1},u_{2},u_{3},u_{4},v_{1},v_{2},v_{3})$ - $u =$ information - $v =$ redondance Tel que $$ \begin{bmatrix}{l r]}v_{1} = & u_{2} + u_{3} + u_{4} \\ v_{2} = u_{1} & + u_{3} + u_{4} \\ v_{3} = u_{1} + u_{2} & + u_{4} \end{bmatrix}$$