Algorithme Compression et de Décompression

Bonjour tout le monde :mrgreen:

Je viens vers vous car dans le cadre de mon stage, on me demande de créer une I.H.M afin d'afficher des données. Ces données proviennent d'un MODEM relié au PC via une RS-232. Jusqu'ici tout va bien.
Le problème, c'est que pour afficher ces données en temps réel, je dois faire transiter 4331 bits/13.33 ms (en effet toutes les 13.33ms je reçois les nouvelles données) via la RS-232 qui a un débit max de 1535 bits/13.33 ms :oops:. Vous voyez ou se situe le problème ? Mon tuteur de stage m'a dit qu'il serait possible d’implémenter directement un bout de code en C ou Java dans le MODEM afin de compresser les données, et ainsi respecter ce débit binaire de 1535 bits/13.33 ms. Il me resterai donc plus qu'à décompresser les données pour ainsi les afficher. Je fais donc appel à vous afin de savoir si vous connaissiez un alogorithme facilement codable en C ou Java, possible de compresser/décompresser un flux binaire.


Merci à vous :ccool:, bonne journée ;)

ben ces données c'est quoi ??

Des entiers, des shorts, des bytes ?

Ces données sont stockées sur 32 bits au niveau du MODEM, mais vont véhiculer au format RS-232 à travers la liaison RS-232. Soit 8 bits de data + 1 bit de start + 1 bit d'arrêt + 1 bit de parité = 11 bits.

et tes 8 bits de data représentent quoi ?

Tu as d'abord les algos de compressions usuels (LZW etc), et puis après il peut y avoir une compression dépendante des données et de leur type - distribution (par exemple du style GIF pour des images)

Ces données représentent des amplitudes de puissances.
Le problème c'est qu'il me faudrait un algo simple à coder, et qui ne prenne pas beaucoup de temps, afin que les infos affichées correspondent bien aux données "actuelles".

Comme je dis, ça dépend des propriétés des données...

Si tu as plusieurs (voire beaucoup de) fois les mêmes valeurs, tu peux compresser en faisant des listes indexées.. (comme GIF)

Tu peux aussi, si tes valeurs sont dans un certain "range", stocker le "range" une fois et ensuite ne stocker que les différences, qui nécessitent moins de bits. (très efficace quand beaicoup de valeurs réelles (le format GRIB (principalement utilisé en météo) est comme ceci)). : taux de compression record.


Si tu n'as pas d'a-priori particulier, une comprssion style LZW ou autre (algos et programmes dispos librement, comme zip, tar, etc..)

Merci de la réponse.

J'ai vu effectivement qu'il y avait des algos basés sur la récurrence des valeurs. Le problème avec cette méthode, c'est qu'il faut certainement stocké, et donc perte du "temps réel". Oui car j'ai aussi une contrainte sur le temps.

Schématiquement voila ce que je souhaiterais obtenir:

Donnée sur 32 bits -> compression -> donnée sur 16 bits -> transfert via RS-232 -> décompression -> donnée initiale sur 32 bits -> affichage.

Mais comme il faut que la donnée affichée corresponde bien à la donnée du tout début, dans le temps imparti (13.33 ms), il ne faut pas que je stocke des données afin de les comparer lors de la phase de compression.

Je sais pas si j'ai été clair :oops:

je ré-itère :

on peut avoir un exemple de tes données ? Varient-elles peu autour d'une valeur médiane, ou entre 2 bornes ? Quelle est leur précision ?

Citation:

---

Envoyé par DjÔsh Nash

Schématiquement voila ce que je souhaiterais obtenir:

Donnée sur 32 bits -> compression -> donnée sur 16 bits -> transfert via RS-232 -> décompression -> donnée initiale sur 32 bits -> affichage.

Mais comme il faut que la donnée affichée corresponde bien à la donnée du tout début, dans le temps imparti (13.33 ms), il ne faut pas que je stocke des données afin de les comparer lors de la phase de compression.

---

Un taux de compression de 35% avec une latence de 0, je ne pense pas que ce soit possible avec un codage dynamique. Peut-être avec un codage statique (huffman ?) sur un ensemble de données caractéristiques.

Vue les contraintes, les meilleures options sont de diminuer le volume de données ou d'augmenter la bande passante. :P

Citation:

---

Envoyé par pseudocode

Un taux de compression de 35% avec une latence de 0, je ne pense pas que ce soit possible avec un codage dynamique. Peut-être avec un codage statique (huffman ?) sur un ensemble de données caractéristiques.

Vue les contraintes, les meilleures options sont de diminuer le volume de données ou d'augmenter la bande passante. :P

---

Comme je dis, ça dépend des données...

Si il a des valeurs réeles osicllant entre 2 bornes, il peut qssez facilement ne paser en réel que les 2 bornes et un facteur, et passer les valeurs comme delta au facteur près... Ce qui fait un taux de compression assez sensationnel..


Mais il faudrait voir ses données..

Bonjour,

Effectivement, il serait possible de ne transmettre qu'un "delta" qui représenterai la différence entre la valeur "normale, ou une moyenne" et la valeur actuelle. Le problème c'est que je ne connais pas cette valeur "normale" (étant donné que ces données représentent la puissances des ton composants un signal composite, je ne sais pas si cette puissance est "constante" à l'émission). Mais c'est une bonne idée, qui mérite réflexion.

j'aimerais savoir ce que vous pensez de cette idée:

Il est possible de passer simplement de 32 bits à 16 bits en associant 65537 valeurs du mot codé sur 32 bits à 1 valeur du mot correspondant codé sur 16 bits. Pour cela, je divise le mot codé sur 32 bits par 35537, et je tronque le résultat (pour ne garder que la partie entière) ce qui donne la valeur correspondante du mot de 32 bits codé sur 16 bits.

Avec cette technique, il y aura une perte de précision. Ceci n’est pas important au vu de notre application. En effet, ce mot codé sur 32 bits contient les données concernant l’amplitude de la puissance d’un ton. 32 bits correspond à 4294967296 valeurs possibles, ce qui n’est pas nécessaire, car l’I.H.M ne pourra pas afficher tant de valeurs différentes (Cf. le nb de pixels verticaux sur un écran de PC), dans le cas d’un histogramme évolutif en temps réel.

:cry:

je ré-itère : pourrait-on avois un exepmple de tes données ?????

Raisonner dans l'absolu, on peut faire tout et n'importe quoi, et proposer n'importe quel algo..

En fontion de tes données, on peut peu-être trouver un truc efficace...

Quand je disiais un delta, c'est surtout si le facteur mutliplicatif peut donner un entier compris entre 2 bornes "petites", suffisamment pour être enregistré sur N bits, n << 32..

Donc, tant quon ne sait pas de quel style sont tes données, on peut rien dire de précis...

Je vais paraître débile, mais c'est à dire un exemple de mes données ?
Je vais essayer d'être plus claire: ces données codées sur 32 bits représentent l'amplitude de puissance d'un ton du signal composite. Ce signal composite est constitué de différent ton, et sera émis comme signal radio, réceptionné par le MODEM. Donc 1 mot de 32 bits = amplitude puissance d'un ton. Je peux pas savoir à l'avance ce que vont être ces données, ça va être aléatoire :oops:

Citation:

---

Envoyé par DjÔsh Nash

Je vais paraître débile, mais c'est à dire un exemple de mes données ?
Je vais essayer d'être plus claire: ces données codées sur 32 bits représentent l'amplitude de puissance d'un ton du signal composite. Ce signal composite est constitué de différent ton, et sera émis comme signal radio, réceptionné par le MODEM. Donc 1 mot de 32 bits = amplitude puissance d'un ton. Je peux pas savoir à l'avance ce que vont être ces données, ça va être aléatoire :oops:

---

L'idée serait de savoir si les données ont une structure ou une caractéristique qui permettrait de trouver un mécanisme de compression : répétitions, plateaux, motifs, entropie, ...

J'imagine que cette puissance va être plus ou moins constante, mais encore une fois rien de certain !

Citation:

---

Envoyé par DjÔsh Nash

J'imagine que cette puissance va être plus ou moins constante, mais encore une fois rien de certain !

---

Dans ce cas, comme le disait souviron34, un codage de type DPCM serait sans doute une bonne idée.

Oui, par contre avec cette méthode difficile de prédire d'un éventuel débordement. En effet, sinon l'échantillon xn-1 = 0 base 10 et que l'échantillon xn = 2000000, je suis dans les choux. Mais à tenter au vu de mon application.

Citation:

---

Envoyé par DjÔsh Nash

Oui, par contre avec cette méthode difficile de prédire d'un éventuel débordement. En effet, sinon l'échantillon xn-1 = 0 base 10 et que l'échantillon xn = 2000000, je suis dans les choux. Mais à tenter au vu de mon application.

---

ce sont les VALEURS dont j'aimerais avoir une idée...

que-ce-que c'est 'l'échantillon n-1"... ????

Et même avec ton exemple, QUELLE EST LA PRECISION ????

C'est pour ça que je demande une xepmle de données .PAs c "c'est du 32 bits".. je m'en tape.. Un exemple de la VARIETE DES VALEURS ....

Dans le cas que tiu donnes, si ce sont des enties, on peut très bien imaginer de passer en log, et donc de transferrer 9 comme facteur, et 0 puis 2 comme valeurs...

Ce que je veux dire, c'est :

si tu peux définir le delta, d'une manière ou d'une autre, comme <= 255, tu peux sotcker tes valeurs sur 8 bits, si <= 10 sur 4 bits, etc etc ..

Voila mon problème, c'est que je n'ai aucune idée sur les valeurs que je vais recevoir. Et effectivement c'est un gros problème, c'est d'ailleurs pour ça que je n'ai pas pu rep.

Je crois que je vais rester sur l'idée de Division -> Transmission -> Multiplication.

Salut!

Citation:

---

je n'ai aucune idée sur les valeurs que je vais recevoir

---

Comme l'écrivait très justement Georg Polya, pour résoudre un problème, il faut d'abord le comprendre, c'est-à-dire, entre autres connaître les données, ce qui ne semble pas être le cas ici. Pour le moment, ton problème semble donc insoluble.
Jean-Marc Blanc

Citation:

---

Envoyé par DjÔsh Nash

Voila mon problème, c'est que je n'ai aucune idée sur les valeurs que je vais recevoir. Et effectivement c'est un gros problème, c'est d'ailleurs pour ça que je n'ai pas pu rep.

---

:calim2:

y'a kke chose que je comprend pas..

Dans ton premier post, tu dis que tu dois faire une IHM pour afficher des données.. Là tu nous dis que tu sais pas ce que sont tes données...

Soit tu as un gros problème de conception, soit un gros problème de communication...

Non c'est juste que je n'ai pas toutes les données nécessaires à la bonne réalisation de ma partie du projet. Moi je me charge seulement de l'IHM. je n'ai pas une connaissance globale sur la totalité du projet. Du coup ce n'est pas très transparent.
Comme je l'ai dit, je connais certaines généralités sur les données, comme le fait que ça soit des données standards qui vont être émises par radio, réceptionnées, traitées par un MODEM, stockées en RAM sur 32 bits. Mais je ne connais pas, par exemple, la puissance des différents tons lors de l'émission. Et j'avoue ne pas avoir les connaissances nécessaires en télécom pour me pencher sur tout cela. Je ne sais pas si la puissance mesurée des différents tons à la réception peut varier en fonction de différents paramètres, comme la distance, les obstacles ect ect...Il m'est donc impossible de donner valeur autour de laquelle on va varier ect ect...

Si ce sont des ondes radio, il doit bien y avoir un domaine de fréquences..

De l'odre du kHz, Mhz, Ghz..

Et une précision associée..

Tu ne reçois pas la télé en Ghz avec une précision du Hz...

C'est ce que je veux dire plus haut...

Même si ta mesure est en Ghz, donc 10^9 Hz, tu as un certain domaine (de x à y Ghz) avec une certaine précision.

Tu ne remplis donc pas aléatoirement tes 32 bits, même si les valeurs en elles-mêmes sont 32 bits..

Tu as donc les conditions pour diminuer facilement le nombre de bits associé à chaque valeur..

Selon le type du signal, tu peux aussi utiliser une échelle logarithmique ou qqchose du style.

Cf. ne pas utiliser une échelle linéaire mais logarithmique ou exponentielle afin de pouvoir y privilégier les grands chiffres ou les petits chiffres et/ou en utilisant une autre fonction ou une table de conversion 32 -> 16 bits plus adaptées)


@+
Yannoo

Sauf si je me trompe, je crois qu'il y a un flou dans ta conception du problème.
Ton objectif : passé de x bits/s à y bits/s, y<x.
Si tu n'as aucun pouvoir sur ton média, tu ne pourras pas l'influencer.
Donc si ta condition, c'est de transmettre x bits/s sur celui-ci, tu ne pourra pas en faire transité y bits/s, avec y<x. Autrement dit, si tu n'as pas d'influence sur le débit, tu ne pourras pas aller plus vite en te focalisant sur ton flux d'octet qui y transite. Autrement dit, les algos de compression à ce très bas niveau sont déjà au top (en tout cas, je pense que tu perds ton temps à investir ton temps dans ce problème).

Ton problème comme je le comprends, c'est que tu veux réduire la quantité d'information à transmettre, sans même parlé de média (j'entends par média le RS232, DSL, fibre optique, ...). Donc pour pouvoir réduire cette information, tu souhaite la compresser.

Et j'ai l'impression que ce que tu n'as pas assimilé (ou alors j'ai mal compris), c'est que la manière dont est transmise cette information n'est pas importante pour la compresser. Peu importe si tu reçois un flux d'octet aléatoire. Ton modem transmets les bits que tu lui demandes de transmettre à une vitesse fixe, et tu ne le changeras pas. Vu la manière dont tu en parles, c'est bien trop bas niveau pour que tu arrives à faire quoique ce soit en si peu de temps.

Non, toi ce que tu veux, c'est réduire l'information à transmettre au modem (et du coup réduire le temps de transmission de cette information).

Tout ce beau discours pour te faire comprendre un truc. Lorsque que l'on te demande "quelles sont les données que tu transmets ?", la réponse n'est pas "un flux d'octets aléatoires définis par les caractéristiques de mon média", la réponse c'est "de l'information". (information = donnée + sens). Et donc la question qui aurais-dû t'être posé, c'est "quelle est l'information que tu souhaites transmettre ?".

Ainsi, je repose la question, après un bon nombre de post qui te demande la même chose, que transmets-tu ?
Des données de positions (compris entre tel et tel intervalle), des données comptables ? Du texte ASCII, de l'UTF ? (déjà compressé ? comment ?) ? Les données d'un capteur quelconques ? Bref, d'où viennent tes données et quelles sont leurs caractéristiques ?

Après ces questions, la suivante est : "Puis-je me permettre de perdre des données (redondance, précision, sensibilité, ....)".
Si non, alors tournes-toi vers LZW ou ses dérivés (compression sans perte).
Si oui, alors tu dois répondre aux premières questions, car c'est à mes yeux un prérequis à toutes formes de compression avec pertes.

En espérant t'avoir un peu éclairé.

ps: on est plus du tout dans une IHM. Mais bon...