Parlons un peu de codage ;)

Salut à tous,
Cela fait longtemps que je n'ai pas écris de petit dossier comme celui-là, cette fois on va parler de codage d'un point de vue théorique et non pas sortir la méthode de codage de la mort qui tue le poney... C'est-à-dire que l'on va mettre à plat tout ce qui nous permet de quantifié l'efficacité d'un code... Et ce tout, c'est formules


1) Quantité d'information

Donc nous considérons une source S de n événements aléatoires que l'on nom L(i) avec i = 1..n. Nous cherchons à enregistrer et transmettre ces n messages. Une telle source est dite discrète car elle émet un nombre fini de messages différents.
La quantité d'information Q(L(i)) de L(i) est supposé ne dépendre que de la probabilité d'apparition de l'événement L(i) [valeur affective mise au placard], plus un événement est récurent et plus, nous chercherons à minimisé le nombre de données à transmettre pour identifier le message...

La première formule vient du fait que l'on aimerez bien que s'il se produit deux événements aléatoires et bien la quantité Q d'informations à transmettre soit la somme des deux quantités d'informations de chaque événement... En gros s'il y a deux sources A et B et bien on veut que : Q( L(i,A) et L(j,B)) = Q(L(i,A)) + Q(L(j,B)) ensuite la probabilité que ces deux événements se passent est P(i,j) = P(i,A) x P(j,B) [événements indépendants => cours de proba au lycée]
Nous avons poser que la quantité d'information est décroissant est fonction de la probabilité : Q(L(i)) = -F(P(i)), où F est une croissante, le - sert à introduire une décroissance... Hors : Q( L(i,A) et L(j,B)) = Q(L(i,A)) + Q(L(j,B)) donc F(P(i) x P(j)) = F(P(i)) + F(P(j)) et là nous reconnaissons une équation caractéristique ! Celle du logarithme ! Donc la fonction Q la plus que nous pouvons trouver est Q = -log(P) ou le log est de base quelconque si on prend un log en base e, nous avons le log népérien, le classique ln et alors on mesure Q en nat, et si on prend un log en base 2, on mesure Q en bit [nom anglais] ou Shannon [si on veut faire du full french]

2) Entropie d'une source.

Alors de façon général en science, quand on parle d'entropie... Bref pour faire simple, l'entropie mesure la quantité de bordel... En codage, l'entropie E d'une source est la quantité moyenne d'information de la source, donc en utilisant la formule de la moyenne : E(S) = - somme de i =1..n P(i) x log(P(i))

On peut montrer par un simple étude de fonction (dérivation et annulation de la dérivée) que l'entropie est maximale quand tout les messages sont équiprobable.


1) Intro

L'objectif du codage est de pouvoir transmettre les messages de la source S sous la forme d'une suite d'élément d'un alphabet [depuis tout à l'heure je vous code ma pensée en code français qui utilise l'alphabet latin ] Un alphabet par définition est un ensemble dénombrable de signes (que l'on nome lettres). Par exemple l'alphabet binaire est constitué de deux lettres, 0 et 1.
Nous noterons q la longueur de cet alphabet...

A partir d'un alphabet A, on définie l'ensemble A* de tous les codes possibles. Le codage d'une source S consiste à associer à chaque événement un élément de A* . Les éléments de A* ainsi définis sont les mots du codage et une suite de mot constitue un texte [très littéraire la science du codage ]

2) Caractérisation des codages

Définitions :
Tous les codages ne peuvent pas être lus sans ambiguïté. Il faut ainsi que le codage satisfasse certaines conditions.
Un codage est dit régulier si deux messages différents implique deux mots différents.
Un code est dit déchiffrable si quelque soit deux textes distincts leurs codes doit être différents.
Un code est dit irréductible si le code d'un message ne peut pas être le début du code d'un autre message. Par exemple {0,10,110,111} est irréductible.

Premier théorème de Shannon :
Soit une source S d'événements aléatoires L(i) où i = 1..n, chaque événement est de probabilité P(i), on note l(i) la longueur du code de L(i). On note aussi la longueur moyenne du codage < l > (calculable par la formule de la moyenne : somme de i =1..n l(i) x P(i))
Le premier théorème de Shannon fournit une borne inférieur pour la longueur moyenne des codes déchiffrables de la source S. Il spécifie que pour chaque source S d'entropie E(S) dont les messages sont codés de façon déchiffrable par un alphabet de q lettres, on a :
et il existe au moins un code irréductible tel que :

Caractérisation de l’efficacité d'un code :
On appelle longueur minimale théorique d'un code de la source S d'entropie E(S) avec un alphabet de q lettres la grandeur :
Une source S codée avec un alphabet de q lettres et un codage de longueur moyenne < l > possède une efficacité :
et sa redondance est donnée par : R = 1 - eff

Interprétation : un codage peu redondant est pratique car il code en très peu de lettre. En effet, R = 0 => = min est on peut pas descendre en dessous, mais il est très sensible à la perte de donné qui peut être induit par un défaut de système d'acquisition. Un code redondant est plus long à transmettre et il est très facile de reconstituer l'information même s'il y a des pertes. Donc en gros si votre machine est peu fiable => code redondant et s'il est très fiable, privilégié un code peu redondant pour un gain de rapidité.

VOILA, j'ai fini
Pour ceux qui veulent des méthode pour créer des codages : il y a le codage de Fano et le codage de Huffman

J'ai pas trop compris ton intro sur la complexité (et dans l'absolu ta manière de la quantifier). Ensuite pour le codage, ben personnellement je suis mal à l'aise par rapport au mot codage. Tel que tu le décris, ça a l'air d'être de la compression alors que généralement il s'agit de crypto.
En tout cas coté compression j'ai dja testé Huffman et RLE. Coté crypto c'était RSA, les hachages, AES et surement d'autres dont je ne me souviens pas.

Après, je ne suis pas sur de l'utilité de ce genre d'intervention sur un forum de making 8D. Enfin pourquoi pas

Le codage comme il est présenté n'a rien avoir avec l'informatique ;-) c'est plutôt la façon de coder une information qui peut être physique ou alors une suite d'événements.

Pour la complexité, tu veux parler de l'efficacité eff ou de la quantification Q et par conséquent l'entropie ?

Pour l'intervention dans le making, je voie surtout l'utilité en évent making, notamment sur l'utilisation des phénomènes aléatoires multiples, si tu code plusieurs événements aléatoires simultanées, tu peux définir un codage efficace de tout ce qui se passe. Sinon après c'est surtout de la culture G sur le traitement de l'information pour ceux qui s'oriente vers des projets informatiques qui n'inclue pas forcement le making, donc des projets avec des capteurs, des enregistrements d'informations, transferts d'informations etc. Le seul enjeux ici, c'est quels sont les critères pour avoir un bon code suivant ce que je souhaite en faire. La crypto repose aussi dessus en comptant la probabilité d'apparition des lettres de l'alphabet, la fiabilité des moyens de transfert, la vitese de transfert, etc.

Le contexte de cette intro au codage de l'information, ce fait dans le cadre de la théorie de l'information et non dans un cadre info ;-). Le traitement du signal est la discipline qui développe et étudie les techniques de traitement, d'analyse et d'interprétation des signaux. Parmi les types d'opérations possibles sur ces signaux, on peut dénoter le contrôle, le filtrage, la compression de données, la transmission de données, le débruitage, la déconvolution, la prédiction, l'identification, la classification, etc.