---
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}$


### 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


| Antécédents | $P_{i/j}$ | Code |
| -------- | -------- | -------- |
| Sachant A |  |  |
| Sachant B |  |  |
| Sachant C | A: 1 | 0 |
| Sachant D |  |  |

# 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}$$