TP6-ThInfo-Correction
Posted on Mon 30 March 2020 in posts
TP6 : L'ensemble des codes aléatoires¶
Nous allons regarder ici un exemple de code particulier : l'ensemble de codes aléatoires. Ce code très simple, permet de saturer la borne de Shannon dans le théorème du codage de la source. Le principe est le suivant : soit un ensemble de symboles (à transmettre) de taille $2^M$. On va attribuer à chaque élément de cet ensemble un code aléatoire dans $\{0,1\}^N$. Par exemple, si on a l'ensemble de 4 lettres 'a', 'b', 'c', 'd' (donc $2^M=4$ ou $M=2$) on pourra obtenir pour N=6
symbole | code |
---|---|
'a' | 001100 |
'b' | 101010 |
'c' | 111001 |
'd' | 000011 |
Une fois le code créé, on peut l'envoyer dans un canal symmétrique binaire. Le décodage s'effectue de la façon suivante : une fois le messaege reçu, on va devoir trouver dans l'ensemble des mots-code (qui est ici un sous-espace de $\{0,1\}^N$) le mot-code le plus proche (i.e. celui pour lequel le nombre de bits retournés est le plus faible).
Question
Correction
Remarques
Sujet
Première partie : codage¶
On va faire une tentative d'implémentation d'un code aléatoire, avec transmission et décodage
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
%matplotlib inline
Commençons avec un cas facile : $f=0.1$, un ensemble de $2^3 = 8$ symboles codés dans un espace à $N=20$ dimensions.
Question
- Calculer le taux $R$
# TODO
Correction
M = 3
N = 20
R = M/N
print("rate=", R)
Remarques
Dans le cours on a : $\log_2(M)/N$ où M est le nombre de symbole.
Mais ici on préfère comparer la taille du message en nombre de bits. Donc dans ce TP M = nombre de bits pour coder les symboles ie log(#symbole)
Question
Commenez par générer un code aléatoire :
- on commence par attribuer un indice $i=1, ..., 2^3$ à chacun des symboles
- pour chaque élément $i$, on génère une séquence aléatoire de $N$ bits ($0$ ou $1$), chacun avec probabilité 1/2.
# TODO
Correction
encoded = np.random.randint(low=0, high=2, size=(2**M, N))
for i in range(2**M):
print("indice ",i," code=",encoded[i,:])
size = 2**M
distances = [ np.linalg.norm(encoded[i] - encoded[j])
for i in range(size) for j in range(size) if i !=j]
sns.distplot(distances)
plt.show()
Sujet
Pour la suite on reprendra la fonction de canal utilisée lors des tps précédent
# Fonction de transmission du canal (cf TP 3)
def Transmit(msg_enc, f):
noise_vector = (np.random.random(msg_enc.shape) < f) * 1
return (msg_enc + noise_vector) % 2
On peut maintenant utiliser la fonction Transmit pour récupérer le message altéré. Ici un exemple où l'on fait passer tous les symboles encodés par le canal:
f = 0.1
all_code_words = encoded
msg_received = Transmit(all_code_word, f=f)
for i in range(2**3):
print("indice ", i, " code=", all_code_word[i,:], " *** received=", msg_received[i,:])
Deuxième partie : inférence¶
Vous devez maintenant coder la fonction inference qui, à partir d'un message reçu et de l'ensemble des mots-code possibles, retourne le message inféré. On peut procéder de la façon suivante :
- on donne comme argument : le message reçu et l'ensemble des mots-code.
- il faut trouver parmi l'ensemble des mots-code, celui qui est le plus proche du message reçu.
Ensuite, écrire une fonction qui envoie tous les symboles possibles par le canal, les décoder et compter la proportion de messages correctement décodés.
Question
def Inference(recieved_msg, all_code_words):
# TODO
return None
Correction
def Inference(recieved_msg, all_code_words):
return all_code_words[np.argmin(np.linalg.norm(recieved_msg - all_code_words, axis=1)),:]
def ErrorAll(all_msg, all_code_words):
err = 0
recieved_msg = Transmit(all_msg, f=f)
for i in range(recieved_msg.shape[0]):
msg_dec = Inference(recieved_msg[i,:], all_code_words)
#print(i," ",all_msg[i,:]," ",recieved_msg[i,:]," ",msg_dec)
#print(i," ",(np.sum(msg_dec-all_msg[i,:])))
if(np.sum(msg_dec - all_msg[i,:]) != 0):
err += 1
return err/all_msg.shape[0]
ErrorAll(all_code_words, all_code_words)
Question
Afin d'avoir une statique plus précise, générer un ensemble de $1000$ mots-code valident, et regarder la proportion d'erreur
# TODO
Correction
Nmsg = 10000
idx = np.random.randint(low=0, high=2**M, size=(Nmsg))
msg = np.zeros((Nmsg, N))
for i in range(Nmsg):
msg[i,:] = encoded[idx[i], :]
ErrorAll(msg, all_code_words)
from collections import Counter
errors = Counter()
Nmsg = 10000
for j in range(2**M):
errors[j] = 0
for i in range(Nmsg):
msg = encoded[j]
transmited = Transmit(msg, f=f)
decoded = Inference(transmited, all_code_words)
if np.sum(msg - decoded):
errors.update([j])
errors
plt.bar(errors.keys(), errors.values())
plt.ylabel('#errors')
plt.xlabel('symbol')
plt.show()
print("Error rate :", sum(errors.values())/(Nmsg * (2**M)) )
Question
Tester quelques valeur de $M$ et $N$, en gardant $R$ fixé, afin comment évolue l'erreur lorsqu'on augmente les tailles des symboles et des mots-code dans une même proportion.
M = 3
N = 20
def compute_errors(N, M, Nmsg=1000):
encoded = np.random.randint(low=0, high=2, size=(2**M, N))
errors = Counter()
for j in range(2**M):
errors[j] = 0
for i in range(Nmsg):
msg = encoded[j]
transmited = Transmit(msg, f=f)
decoded = Inference(transmited, encoded)
if np.sum(msg - decoded):
errors.update([j])
error_rate = sum(errors.values())/(Nmsg * (2**M))
return error_rate
errors = {m : [compute_errors(n, m) for n in [10, 20, 30]] for m in [3, 5, 7]}
errors = pd.DataFrame(errors, index=[10, 20, 30])
errors
Correction
Question
Que conclure sur la faisabilité de ce code ?
Correction
Complexité du décodage : $\mathcal{O}(N\times 2^M)$
Troisième partie : théorie¶
Pour comprendre les performances du "Random Code Ensemble" (RCE), il faut se poser du nombre de mots-code présent à une certaine distance d'un mot-code donné. Considérons $x_0$, un mot-code. On cherche à calculer le nombre moyen de mots-code qui se trouverait à une distance $d$ de $x_0$.
Question
Pour simplifier la question, on prendra $x_0 = 00...00$.
- Quelle est la probabilité de générer une chaine de $N$ bits qui ont $k$ bits à 1.
Correction
Rép : $\text{binomial}(n, k, p) = C^k_N \times p^k (1-p)^k$
Question
- Sachant qu'on a au total $2^M$ mots-code, combien de mots-code ${\cal{N}(d)}$ (en moyenne) seront à une distance $d$ ($d$ bits retournés) de $x_0$ ?
Correction
Rép : $2^{M-1} C^k_N$
Question
- En utilisant l'approximation de Stirling pour $N$ grand : ${\cal{C}}^k_N \approx 2^{NH_2(\delta)}$, où $H_2(\delta) = -\delta \log_2(\delta) - (1-\delta)\log_2(1-\delta)$ et $\delta=k/N$, montrer que l'on obtient dans la limite où $N$ est grand le résultat suivant : $${\cal{N}(d)} = 2^{N\left[R-1+H_2(\delta)\right]}$$
Correction
Rép : remplacer dans l'éq du 2)
$${\cal{N}(d)} = 2^{M-1} \times 2^{NH_2(\delta)}$$$${\cal{N}(d)} = 2^{(M-1) + N H_2(\delta)}$$$$ R = M/N $$$${\cal{N}(d)} = 2^{N[(M/N-1/N) + H_2(\delta)]}$$$${\cal{N}(d)} = 2^{N\left[R-1+H_2(\delta)\right]}$$Question
- Tracer $R-1+H_2(\delta)$, en fonction de $\delta$ pour $R=0.5$. Que nous indique le fait que cette fonction soit négative ou positive ?
Correction
R = 0.5
def H_2(delta):
res = -delta * np.log(delta) - (1-delta) * np.log2(1-delta)
return res
x = np.linspace(0, 1, 50)
y = R - 1 + H_2(x)
plt.plot(x, y, label='~ nb voisin')
plt.hlines(0, 0, 1, label=0)
plt.xlabel('k/N')
plt.ylabel('')
plt.legend()
plt.show()
Rép : négative : un nombre de voisin exponentiellement faible is neg (pratique aucune chance d'en avoir un) au contraire, lorsque la courbe passe positive, on est pratiquement sûr d'en avoir un.
Question
- En déduire pour quelle valeur $f$ du canal, il est possible de décoder sans erreur à l'aide du RCE, lorsque $R=0.5$.
Correction
Rép : en gros, si $f<\delta_0$, où $\delta_0$ est la valeur de $\delta$ à laquelle la courbe passe négative, on peut décoder sans problème. Pourquoi ? le canal va flipper en moyenne $2^N * f$ bits, quand $N$ est grand les fluctuations sont petites par rapport à la valeur moyenne $m/\sigma \propto \sqrt{N}$ et donc si on risque de faire basculer un nombre de bits inférieur à la distance à laquelle on trouve un mot-code on est bon.