Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 30-09-2019 14:50:27

Frédéric Meyer
Membre
Inscription : 30-09-2019
Messages : 3

Augmenter l'entropie informatique

Bonjour,

En premier lieu, quand je parle d'entropie, il s'agit de l'entropie selon Shannon.

De manière succinte, comme le suggère le titre, je cherche une application inversible (ou un algorithme inversible) pour augmenter l'entropie selon la théorie de l'information de Shanon. Mais l'entropie de Renyi convient aussi.

Formellement, on a une source d'information notée $X_m$ définie comme une suite de nombre définie dans $\mathbb{Z}_q$ ( noté aussi $\mathbb{Z}/q\mathbb{Z}$ ); $X_m = \{x_i \in \mathbb{Z}_q, i \in [|1, m|]\}$ avec $m \in \mathbb{N}^*, n \in \mathbb{N}^*, q > 1$.

Il me faudrait alors une application $f$ qui transforme $X_m$ en $Y_n$ que l'on peut définir ainsi $f:
\left|
  \begin{array}{rcl}
    \mathcal{P}(\mathbb{Z}_q) & \longrightarrow & \mathcal{P}(\mathbb{Z}_q) \\
    X_m & \longmapsto & Y_n \\
  \end{array}
\right.$

Avec $Y_n = \{y_i \in \mathbb{Z}_q, i \in [|1, n|]\}$.

Ce n'est pas la peine de me répondre que pour obtenir $Y_n$, il suffit d'ajouter à $X_m$ des éléments issus d'une combinaison linaire (par un produit de matrices par exemple) des éléments de $X_m$, car il faudrait que ces contraintes soient respectées:
$\left\{
\begin{array}{l l}
n \ \geqslant \ \frac{m}{2} \\
Card (\{ E \ | \subset X_m \ et \ E \subset Y_n \}) < \frac{m}{2} \\
H_b(X_m) \ \leqslant \ H_b(Y_n)
\end{array}
\right.$

Pour l'entropie $H_b$ on peut prendre celle de Shannon: $H_b(x) = - \sum_{s\in\mathbb{Z}_q} p_s(x) log_b(p_s(x)) $.

Où $x\in(\mathbb{Z}_q)^r, r\in\mathbb{N}^*$ et où $p_s(x) = \frac{Card(\{i | i \in [|1, r|], x_i = s\})}{r}$

Mais on peut prendre d'autres définitions tant qu'elle qualifie une entropie selon Shannon, et avec le paramètre $b$, avec $b\in\mathbb{N}$ et $b>1$.

Pour l'entropie de Shannon, on admet que $ 0 \times log(0) = 0 $ pour les cas où $s_j \notin X_n$ tel que $j \in [|1, n|]$ alors $p_s(x) = 0$

L'application $f$ que je cherche peut être un codage comme le codage de Hill mais il faut que ce codage puisse respecter les contraintes. Et donc étant un codage, il faut un décodage puisque $f$ est inversible.

Dernière modification par Frédéric Meyer (03-10-2019 07:23:17)

Hors ligne

#2 30-09-2019 15:14:40

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : Augmenter l'entropie informatique

Bonjour,

C'est un peu confus à plusieurs niveaux, pourquoi est-il évident que $m \leq n$ ? Parce que vous voulez augmenter l'entropie d'une source je suppose, ou alors je suppose mal et cela est il une conséquence de vos précédentes hypothèses ?
m et n sont ils des entiers quelconques (je suppose que oui, mais on ne sait jamais) ?
Hum, quand vous écrivez $[0, m[$ je suppose que vous voulez écrire $[|0,m-1|]$ ?

Et dans cette partie :

Frédéric Meyer a écrit :

Je ne veux pas nécessairement une application $f$ avec $m = n$ telle que $f:
\left|
  \begin{array}{rcl}
    X_n & \longrightarrow & Y_n \\
    x_i & \longmapsto & y_i \\
  \end{array}
\right. \nmid i \in [0, n[ $

Que veux dire $\nmid i \in [0, n[ $ ? parce que pour moi $\nmid$ veut dire "ne divise pas"...

Et la 1ère fonction f que vous définissez c'est elle que vous voulez être bijective ? ou la deuxième ?
La première fonction f que vous définissez est mal définie : son ensemble de départ et d'arrivé ne sont pas les bons, il faudrait plutôt prendre l'ensemble des parties de $\mathbb{Z}_{q}$, non ?
Et au passage $q$ c'est un entier quelconque ou un nombre premier ?

Pouvez vous donc préciser une bijection entre quoi et quoi ?

Cordialement

Hors ligne

#3 30-09-2019 18:05:51

Frédéric Meyer
Membre
Inscription : 30-09-2019
Messages : 3

Re : Augmenter l'entropie informatique

Bonjour Maenwe,

J'ai modifier le texte, dites moi s'il reste encore des confusions. J'ai par ailleurs précisé que la 2ème fonction n'était qu'un cas particulier de la première fonction simplement en restreignant les domaines de définition $\mathbb{Z}_q^{(\mathbb{N})}$ à $X_m$ pour antécédant et à $Y_n$ pour image.

Cordialement.

Hors ligne

#4 30-09-2019 18:25:26

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : Augmenter l'entropie informatique

Bonsoir,

Hum, il y en a encore deux (voir 3 mais c'est peut-être dû à mon incompréhension), $\mathbb{Z}_{q}^{\mathbb{N}}$ est l'ensemble des suites dans $\mathbb{Z}_{q}$, or $X_{m}$ est une partie de $\mathbb{Z}_{q}$ et non une suite d'éléments de celui-ci. L'ensemble des parties d'un ensemble A (quelconque) se note : $P(A)$.
Si la deuxième fonction $f$ est un cas particulier de la 1ère dans le cas où $n=m$ alors la deuxième fonction est mal définie car elle devrait être définie sur $P(\mathbb{Z}_{q})$ et à valeur sur $P(\mathbb{Z}_{q})$.
Et la 3ème confusion est que je ne comprends pas ce qu'est votre fonction ($f$), vous avez défini m et n en dehors de cette fonction, donc à moins que l'ensemble de définition de cette fonction soit le singleton $\{X_{m}\}$ je ne comprends pas comment votre fonction est définie, et ne vois d'ailleurs toujours pas quelle bijection vous voulez autrement dit : une bijection entre quelles ensembles ?
Si c'est entre $X_{m}$ et $Y_{n}$ je peux vous assurez qu'il n'y a qu'un seul cas où une telle bijection peut exister c'est celui où $n=m$ (car les ensembles sont finis).

Cordialement

Dernière modification par Maenwe (30-09-2019 18:26:03)

Hors ligne

#5 03-10-2019 07:17:53

Frédéric Meyer
Membre
Inscription : 30-09-2019
Messages : 3

Re : Augmenter l'entropie informatique

Bonjour Maenwe, je vois que mon formalisme a échoué, en clair je cherche un codage qui code $X_m$ en $Y_n$ qui fait que l'entropie augmente, et donc il faut que l'application de codage soit inversible pour avoir un décodage.
J'ai enlevé la bijectivité pour l'inversibilité, car ainsi on a bien $m$ qui peut être différent de $n$.

Hors ligne

Pied de page des forums