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:
      $⌈ l o g_{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 c h a r + 2 c h a r \equiv o (m o d 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{matrix} 1 - p & p \\ p & 1 - p \end{matrix}]

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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}) = L o g_{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} L o g_{2} (p_{i})

Remarque:

$H (S)$ : Quantité d'information moyenne minimale pour chaque symbole de la source
$S$

Exemple:

X_{1} = [\begin{matrix} 0 & s i p a i r & \frac{1}{2} \\ 1 & s i p a i r & \frac{1}{2} \end{matrix}] X_{2} = [\begin{matrix} 0 & s i 1, 2 & \frac{1}{3} \\ 1 & s i 3, 4 & \frac{1}{3} \\ 2 & s i 5, 6 & \frac{1}{3} \end{matrix}] X_{3} = v a l e u r " t i e r c e "

H (X_{1}) = - \frac{1}{2} . l o g_{2} (\frac{1}{2}) - \frac{1}{2} . l o g_{2} (\frac{1}{2}) = - l o g_{2} (\frac{1}{2}) = 1

bit

H (H_{2}) = - 3. \frac{1}{3} . l o g_{2} (\frac{1}{3}) = - l o g_{2} (\frac{1}{3}) = l o g_{2} 3 = 1, 585

bits

H (X_{3}) = - 6. \frac{1}{6} . l o g_{2} (\frac{1}{6}) = l o g_{2} (6) = 2, 585

bits

\begin{array}{ccccc} 19 & A & B & C & D \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ 00 & 01 & 10 & 11 \\ 29 & A A A A & B B & 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} l o g_{2} (\frac{1}{4}) = l o g_{2} (4) = 2

H (S) = - \frac{1}{2} l o g_{2} (\frac{1}{2}) - \frac{1}{4} l o g_{2} (\frac{1}{4}) - \frac{1}{8} l o g_{2} (\frac{1}{8}) - \frac{1}{8} l o g_{2} (\frac{1}{8})

H (S) = 1, 75

bits

H (S) = | \begin{array}{l} - p . l o g_{2} (p) - (1 - p) l o g_{2} (1 - p) s i 0 < p < 1 \\ 0 (p = 0, p = 1) \end{array}

Entropie

H_{m a x} = l o g_{2} (r)

Redondance

R = \frac{H_{m a x} - H (r)}{H_{m a x}} = 1 - \frac{H (s)}{H_{m a x}}

H (X) = - \sum_{x \in X} P (X = x) l o g_{2} (P (X = x)) H (Y /_{Y = x}) = - \sum_{y \in Y} P (Y = y /_{X = x}) l o g_{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{matrix} 1 - p & p \\ p & 1 - p \end{matrix}] = [\begin{matrix} P (Y = 0 /_{X = 0}) & P (Y = 1 /_{X = 0}) \\ P (Y = 0 /_{X = 1}) & P (Y = 1 /_{X = 1}) \end{matrix}]

C = I (X, Y) = H (Y) - H (Y /_{X}) H (Y) = - \sum_{y \in Y} l o g_{2} (P (Y = y)) = - P (Y = 0) l o g_{2} (P (Y = 0)) - P (Y = 1) l o g_{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}{ccccccc} 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}{ccc} C o d a g e 1 & C o d a g e 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, 4 l o g_{2} - 0, 2 l o g_{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 = {c_{1}, c_{2}, . . ., c_{n}

l_{i} = l (c_{i})

Exercice :

\begin{array}{cccccc} s_{i} & p_{i} & C & I & I I & I I I \\ 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_{I I}, L_{I I I}$ ?
- $L_{I}$
$H (S)$ , code optimal ?
$K M_{I}, K M_{I I}, K M_{I I I}$ ?

Techniques primitives

RLE = Run Length Encoding
Codage des répétitions : successions d'octets identiques

Codage topologique
Codage relatif

Codage de Huffman

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Antécédents	$P_{i / j}$	Code
Sachant A	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →
Sachant B	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →
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{matrix} 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{matrix}]