Coder sur 6 bits un maximum d'événements en limitant les conflits

bonjour,

j'ai un programme qui envoie sur une carte d'acquisition une série de codes. Chaque code représente un événement particulier. Ces événements sont codés sur 6 bits.

Logiquement avec 6 bits je peux coder 2^6 = 64 événements. L'ennui est certains événements ont lieu en même temps, par conséquent le code envoyé à la carte d'acquisition est la somme de ces codes (le programme fonctionne comme ça, je ne peux rien changer à ce niveau).

Exemple :

Code:

---

1 2	Event_1 = 2^4 + 2^5 = 48 Event_2 = 2^3 = 8

---

Si Event_1 et Event_2 ont lieu en même temps, la carte reçoit 8+48 = 56.

Ensuite au moment du traitement des données, je réalise l'opération inverse (utilisation de masques) pour retrouver Event_1 et Event_2.

Ce chevauchement des événements a une conséquence : le nombre d'événements que je peux coder n'est plus de 64.

En reprenant l'exemple ci-dessus, je ne peux pas coder un Event_3 tel que :

Code:

---

Event_3 = 2^3 + 2^4 + 2^5

---

car dans ce cas si je reçoit 56, je ne sais pas si c'est Event_3 que j'ai reçu ou (Event_1 + Event_2).


Donc voici ma problématique :
- Je cherche à savoir combien d'événements je peux coder sur 6 bits tout en limitant les conflits, sachant que je peux avoir au maximum 4 événements qui se chevauchent.
- Bien sûr, je souhaite pouvoir coder un maximum d'événements ;)
- De plus, je cherche à déterminer les codes de ces événements.


Après avoir pris des renseignements, on m'a parlé d'algorithmes d'optimisation, de l'algorithme de branch et bound, et de simplexe (pour la programmation linéaire).
Etant totalement incompétent dans ces domaines, je sollicite votre aide pour résoudre ce casse-tête :)

:merci:

Citation:

---

Envoyé par Auteur

Logiquement avec 6 bits je peux coder 2^6 = 64 événements. L'ennui est certains événements ont lieu en même temps, par conséquent le code envoyé à la carte d'acquisition est la somme de ces codes (le programme fonctionne comme ça, je ne peux rien changer à ce niveau).

---

le code envoyé est la "somme arithmétique" ou un "OR binaire" ?

Event_A = 2^4 + 2^5 = 110000 = 48
Event_B = 2^3 + 2^4 = 011000 = 24
-----------------------------------
Result = 72 ou 56 ?

Citation:

---

Envoyé par pseudocode

le code envoyé est la "somme arithmétique" ou un "OR binaire" ?

---

À mon avis, les deux à la fois : chaque événement doit déja correspondre à un bit particulier.

Citation:

---

Envoyé par Auteur

En reprenant l'exemple ci-dessus, je ne peux pas coder un Event_3 tel que :

Code:

---

Event_3 = 2^3 + 2^4 + 2^5

---

car dans ce cas si je reçoit 56, je ne sais pas si c'est Event_3 que j'ai reçu ou (Event_1 + Event_2). ...

- Je cherche à savoir combien d'événements je peux coder sur 6 bits tout en limitant les conflits, sachant que je peux avoir au maximum 4 événements qui se chevauchent. - Bien sûr, je souhaite pouvoir coder un maximum d'événements ;)
- De plus, je cherche à déterminer les codes de ces événements.

---

Avant toute chose, es-tu vraiment sûr qu'un même événement puisse être codé sur plusieurs bits différents ? Est-ce qu'un événement ne peut pas en impliquer un autre ?

Combien d'événements différents ta carte peut-elle déclencher en tout (important) ?

Comme l'a dit Pseudocode, es-tu certain qu'il ne s'agit pas d'un OU logique plutôt que d'une somme ?

Peux-tu déterminer toi-même la valeur des codes ? Si oui, il suffit de coder chaque événement sur un bit pour être sûr qu'il ne se chevauchent jamais. Tu pourras ainsi coder six événements différents.

Autrement, si tu es sûr de ne jamais dépasser le chiffre de quatre événements simultanés, tu peux calculer le nombre de combinaisons possibles : avec six événements en tout, qui peuvent avoir lieu ou non, tu atteins exactement 64 cas de figures différents (univers : 𝟚⁶). Il suffit de retrancher à ce nombre les cas ou il y a cinq événements simultanés sur 6 - il n'y a que six cas possibles, ceux correspondant à l'événement manquant - ainsi que celui où tout les événements ont lieu en même temps (un seul cas). Cela fait donc 64-7 = 57 cas différents, ce qui tient quand même sur six bits. Avec sept événements différents, cela fait 2⁷ = 128 combinaisons possibles en tout. En enlevant les cas avec 5, 6 et 7 événements simultanés, soit respectivement 1, 7 et 7×6 cas, ça donne 128 - 1 - 7 - 42 = 78, ce qui tient sur 7 bits.

Ça veut donc dire que - dans le cas ou 0 à 4 évenements peuvent avoir lieu à un instant donné - même en économisant les cas, tu ne peux pas gagner de bits en économisant les événements, et tu ne peux pas non plus coder plus de 6 événements avec six bits.

Le plus simple, le plus efficace et le plus naturel que tu aies donc à faire est d'affecter chaque événement à un bit particulier, et examiner individuellement leur état.

Je dois avouer que vous me poser une colle en me demandant si un OU logique ou une somme arithmétique est réalisée si deux événements se chevauchent :oops:

Demain je ferai un programme de test pour vérifier ce point. Mais en toute logique, je pense que c'est un ou logique qui est réalisé.

Citation:

---

Envoyé par Obsidian

Citation:

---

Envoyé par pseudocode

le code envoyé est la "somme arithmétique" ou un "OR binaire" ?

---

À mon avis, les deux à la fois : chaque événement doit déja correspondre à un bit particulier.

---

C'est presque ça Obsidian : jusqu'à présent je me suis débrouillé pour que les codes des événements qui se chevauchent n'aient pas de bits à 1 en commun (dans ce cas le OU logique est équivalent à la somme arithmétique).

Ainsi j'arrive à coder 8 événements avec ces 6 bits.

Voici un exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10

1 2 4 8 16 32 E1 X E2 X E3 X E4 X X E5 X E6 X E7 X X E8 X

---

E3 ; E4 ; E5 ne peuvent pas se chevaucher (c'est pour ça qu'ils ont des bits en commun), de même que E6, E7 et E8. Sinon entre les autres événements il y a un risque de chevauchement (E1, E2, E4 et E8 par exemple).

Citation:

---

Avant toute chose, es-tu vraiment sûr qu'un même événement puisse être codé sur plusieurs bits différents ?

---

Oui un événement peut être codé sur plusieurs bits.

Citation:

---

Est-ce qu'un événement ne peut pas en impliquer un autre ?

---

Les événements sont complètement indépendants c'est sûr.

Citation:

---

Peux-tu déterminer toi-même la valeur des codes ? Si oui, il suffit de coder chaque événement sur un bit pour être sûr qu'il ne se chevauchent jamais. Tu pourras ainsi coder six événements différents.

---

Oui je peux déterminer le code de chaque événement. C'est vrai que l'idéal serait de coder 1 événement par bit. Mais là je suis limité par le matériel (carte 8 bits). Sur ces 8 bits 2 sont réservés donc je dois coder mes événements sur 6 bits.

Je recherche ainsi la possibilité d'augmenter le nombre d'événement à coder sans risque de confusion tout en gardant le matériel que j'ai.

Citation:

---

Envoyé par Obsidian

Il suffit de retrancher à ce nombre les cas ou il y a cinq événements simultanés sur 6 - il n'y a que six cas possibles, ceux correspondant à l'événement manquant - ainsi que celui où tout les événements ont lieu en même temps (un seul cas). Cela fait donc 64-7 = 57 cas différents, ce qui tient quand même sur six bits. Avec sept événements différents, cela fait 2⁷ = 128 combinaisons possibles en tout. En enlevant les cas avec 5, 6 et 7 événements simultanés, soit respectivement 1, 7 et 7×6 cas, ça donne 128 - 1 - 7 - 42 = 78, ce qui tient sur 7 bits.

Ça veut donc dire que - dans le cas ou 0 à 4 évenements peuvent avoir lieu à un instant donné - même en économisant les cas, tu ne peux pas gagner de bits en économisant les événements, et tu ne peux pas non plus coder plus de 6 événements avec six bits.

---

J'avoue que je n'ai pas bien compris ton raisonnement :oops:

Citation:

---

Envoyé par Auteur

- Oui un événement peut être codé sur plusieurs bits.
- Les événements sont complètement indépendants c'est sûr.
- Oui je peux déterminer le code de chaque événement. C'est vrai que l'idéal serait de coder 1 événement par bit. Mais là je suis limité par le matériel (carte 8 bits). Sur ces 8 bits 2 sont réservés donc je dois coder mes événements sur 6 bits.

---

D'accord. Mais je ne sais toujours pas pourquoi certains événements sont codés sur plusieurs bits.

Citation:

---

-Je recherche ainsi la possibilité d'augmenter le nombre d'événement à coder sans risque de confusion tout en gardant le matériel que j'ai.
- J'avoue que je n'ai pas bien compris ton raisonnement :oops:

---

Je vais développer :P (c'est le cas de le dire) :

Pour faire simple, on va dire que, pour faire faire ce que tu veux faire, il faut énumérer tous les cas de figure possibles, et voir si ce nombre tient dans 6 bits, ce qui revient à vérifier qu'il soit inférieur à 64.

On part du principe qu'avec six bits, tu peux coder six événements indépendants, à raison d'un bit par événement. Ça, ok. L'idée est de voir si l'on peut - ou pas - ajouter des événements et les identifier de façon déterministe.

Donc, le fait que tu puisses associer un bit à un événement est dû au fait que celui-ci peut avoir exactement deux états : soit il se produit, soit il n'a pas lieu. Deux états, c'est le même nombre que les états d'un bit. Ça veut également dire que dans ces conditions, six évenements pouvant avoir lieu ou non, ça fait exactement 64 cas de figures différents.

Le plus sensé à ce stade est donc d'affecter un bit par événement, ce qui permet de détecter et identifier chacun d'eux directement, mais ce n'est pas une obligation : tu peux très bien affecter arbitrairement un numéro de 0 à 63 à chacun des cas possibles. À toi d'établir derrière la table de correspondance.

Dès lors, pour ajouter des événements, il faut faire de la place. Pour cela, il faut identifier et exclure tous les cas invalides, pour utiliser leur numéro de combinaison à autre chose. En l'occurence les cas invalides sont, pour toi, les cas où plus de quatre événements ont lieu en même temps. Cela correspond au cas (unique) où les six événements ont lieu simultanément et à ceux ou cinq événements sur six ont lieu, ce qui revient à dire qu'un événement est manquant, ce qui fait donc six cas possibles.

Tu passes donc de 64 cas à 64 - 1 - 6 = 57 cas. Tu gagnes donc sept combinaisons pour signaler ce qu'il te plaît. Cependant, tu ne gagnes pas un bit entier (il aurait fallu pour cela diviser 64 par deux, donc revenir à 32 cas). Est-ce néamoins suffisant pour intégrer un événement supplémentaire suivant les mêmes restrictions ?

Voyons maintenant combien de cas représenteraient sept événements distincts et indépendants. S'il n'y en a toujours que quatre qui peuvent avoir lieu en même temps, ça donnerait : 1 cas (aucun événement) + 7 cas (un événement) + (7×6)÷2 cas (deux événements) + (7×6×5)÷6 (trois événements) + (7×6×5×4)÷24 (quatre événements). Cela fait 1 + 7 + 21 + 35 + 35 = 99 combinaisons en tout (au passage, j'ai fait une erreur au-dessus : ce n'est pas « 127 - 1 - 7 - 42 = 78 » mais « 127 - 1 - 7 - 21 = 99 »).

« 99 », c'est en dessous de 127 (ou 2⁷), mais c'est quand même au-dessus de 64. Ça veut dire que tu ne peux pas coder sept évenements distincts avec six bits, même en les limitant à quatre événements simultanés.

Le seul moyen, à ce stade, de gagner encore de la place est de faire de la discrimination : il faut autoriser certains événements à avoir lieu en même temps et d'autres pas. Pas forcément deux à deux, mais aussi trois à trois. Tu peux également faire l'inverse : obliger certains événements à se produire en même temps, ou décider qu'un événement donné implique forcément un autre. Cependant il te faut éliminer 35 combinaisons pour tenir dans les 64 autorisées, ce qui reste très gros, ce qui me fait dire que globablement, ce n'est pas faisable, ou alors très difficilement.

UPDATE : Je viens de comprendre ce que tu veux dire par ne se chevauchent pas : ces événements sont mutuellements exclusifs.

Citation:

---

E3 ; E4 ; E5 ne peuvent pas se chevaucher (c'est pour ça qu'ils ont des bits en commun), de même que E6, E7 et E8. Sinon entre les autres événements il y a un risque de chevauchement (E1, E2, E4 et E8 par exemple).

---

Donc, là ou trois événements indépendants pourrrait représenter huit cas de figure, on n'en a plus que quatre, de 0 à 3, ce qui tient sur deux bits : autant garder alors un bit pour le premier événement, l'autre bit pour l'autre événement, et la combinaison des deux pour coder le 3ème événement, et c'est exactement ce que tu as fait. Combien, alors, de cas de figure représentent deux groupes de trois événements mutuellement exclusifs et deux événements indépendants ?

| {E1} × {E2} × {E3 + E4 + E5} × {E6 + E7 + E8} | = 2 × 2 × 4 × 4 = 64. Tu as donc rempli exactement toutes les combinaisons possibles et tu ne pourras pas faire plus efficace dans cette configuration. Si tu veux ajouter des événements, il te faut poser plus de restrictions encore.

Citation:

---

Envoyé par Obsidian

UPDATE : Je viens de comprendre ce que tu veux dire par ne se chevauchent pas : ces événements sont mutuellements exclusifs.

---

Oui c'est tout à fait ça. Je me suis mal exprimé en parlant d'événements qui ne se chevauchent pas. En reprenant mon exemple, E3 , E4 et E5 sont exclusifs. Il n'y a aucune probabilité qu'ils surviennent en même temps.


D'ailleurs, quand je regarde à nouveau le tableau des codes que j'ai posté que je crois que j'ai fait une erreur : en effet l'événement E6 peut être combiné avec E7 ou E8. Donc je dois supprimer un événement (E6 en l'occurrence, E7 et E8 étant exclusifs).

Citation:

---

Envoyé par Obsidian

Donc, là ou trois événements indépendants pourraient représenter huit cas de figure, on n'en a plus que quatre, de 0 à 3, ce qui tient sur deux bits : autant garder alors un bit pour le premier événement, l'autre bit pour l'autre événement, et la combinaison des deux pour coder le 3ème événement, et c'est exactement ce que tu as fait. Combien, alors, de cas de figure représentent deux groupes de trois événements mutuellement exclusifs et deux événements indépendants ?

| {E1} × {E2} × {E3 + E4 + E5} × {E6 + E7 + E8} | = 2 × 2 × 4 × 4 = 64. Tu as donc rempli exactement toutes les combinaisons possibles et tu ne pourras pas faire plus efficace dans cette configuration. Si tu veux ajouter des événements, il te faut poser plus de restrictions encore.

---

Ok. Comme je ne peux pas imposer plus de restrictions, je vais devoir garder cette configuration.

Si j'ai bien compris ton équation et en prenant le cas où je supprime E6 car il peut entrer en conflit avec E7 et E8, j'ai donc :

Code:

---

| {E1} × {E2} × {E3 + E4 + E5} × {E7 + E8} | = 2 × 2 × 4 × 3 = 48.

---

Et je ne peux pas rajouter E6 car dans ce cas j'aurais

Code:

---

| {E1} × {E2} × {E3 + E4 + E5} × {E7 + E8} + {E6} | = 2 × 2 × 4 × 3 × 2 = 96.

---

Ce qui ne tient pas sur 6 bits.

Est-ce que j'ai le bon raisonnement ? Ou je me trompe ?

Citation:

---

Envoyé par Auteur

Est-ce que j'ai le bon raisonnement ? Ou je me trompe ?

---

C'est comme ça que je vois les choses, en effet.

Il suffit donc de compter le nombre de combinaisons possibles lorsque les événements sont exclusifs :

Avec E3, E4 et E5, j'ai :
1 x 0 (E3)
1 x 1 (E4)
0 x 1 (E5)
0 x 0 (état bas)
donc 4 combinaisons codés sur 2 bits

Avec E7 et E8, j'ai
1 x 1 (E7)
0 x 1 (E8)
0 x 0 (état bas)
soit 3 combinaisons et une combinaison que je n'ai pas utilisé (1 x 0).

Pour les événements susceptibles de rentrer en conflit, ils ne peuvent être codés sur 1 bit sinon je perd des bits. Donc, j'ai
1 (état haut)
0 (état bas).
Soit 2 états.

Puis le produit du nombre de combinaisons me donne (indirectement) le nombre de bits pour coder tous mes événements.

Après ça en fonction du nombre d'événements exclusifs, il s'agit de coder ces événements également en un minimum de bits :
jusqu'à 3 événements exclusifs sur 2 bits ;
jusqu'à 7 événements exclusifs sur 3 bits etc.


Ok, il me semble bien j'ai bien compris le principe. Merci :D :ccool:

Citation:

---

Envoyé par Auteur

Avec E7 et E8, j'ai
1 x 1 (E7)
0 x 1 (E8)
0 x 0 (état bas)
soit 3 combinaisons et une combinaison que je n'ai pas utilisé (1 x 0).

---

C'est bien ça, mais pourquoi ne pas avoir utilisé plutôt 1-0 et 0-1 pour coder E7 et E8 respectivement, et gardé 1-1 en réserve ?

Citation:

---

Pour les événements susceptibles de rentrer en conflit, ils ne peuvent être codés sur 1 bit sinon je perd des bits. Donc, j'ai
1 (état haut)
0 (état bas).
Soit 2 états.

---

Ce qui revient au même. Tu multiplies par deux, donc tu ajoutes exactement un bit. Tu peux donc t'en servir pour coder directement l'événement en question.

Citation:

---

Puis le produit du nombre de combinaisons me donne (indirectement) le nombre de bits pour coder tous mes événements.

Après ça en fonction du nombre d'événements exclusifs, il s'agit de coder ces événements également en un minimum de bits :
jusqu'à 3 événements exclusifs sur 2 bits ;
jusqu'à 7 événements exclusifs sur 3 bits etc.

Ok, il me semble bien j'ai bien compris le principe. Merci :D :ccool:

---

Oui, c'est bien ça, mais pour que ce soit vraiment efficace, il faut raisonner d'un point de vue global : l'intérêt étant de faire le bilan de tous les états possibles de ta platine en entier. Il se peut, par exemple, que tu aies des configurations qui soient valides en elles-mêmes mais dont tu peux démontrer qu'en pratique, elles n'auront jamais lieu.

Citation:

---

Envoyé par Obsidian

C'est bien ça, mais pourquoi ne pas avoir utilisé plutôt 1-0 et 0-1 pour coder E7 et E8 respectivement, et gardé 1-1 en réserve ?

---

Euh oui c'est un fait. Sans doute parce que dans mon esprit E7 et E8 sont exclusifs et inconsciemment j'ai choisis ces combinaisons.

Citation:

---

Envoyé par Obsidian

Oui, c'est bien ça, mais pour que ce soit vraiment efficace, il faut raisonner d'un point de vue global : l'intérêt étant de faire le bilan de tous les états possibles de ta platine en entier. Il se peut, par exemple, que tu aies des configurations qui soient valides en elles-mêmes mais dont tu peux démontrer qu'en pratique, elles n'auront jamais lieu.

---

Je suis passé par cette étape : la succession des événements n'est (par chance) pas aléatoire, c'est à dire que lorsque E1 survient je sais que l'événement E2 va suivre puis soit E3 ou E4 ou E5 mais je ne sais jamais quand ils ont lieu. C'est la succession des événements dans un intervalle de temps qui provoque les conflits.

Par exemple si je passe à l'état haut sur le bit pendant un temps t, je ne pourrai pas utiliser ce bit 1 durant ce temps. Par contre, rien ne m'interdit de mettre le bit 2 à l'état haut à un moment quelconque.
Pour reprendre les termes de la documentation du logiciel, les lignes "sont indépendantes" : c'est à dire que tant qu'une ligne est à l'état haut elle est occupée et je dois attendre son retour à l'état bas pour à nouveau m'en servir. Mais rien ne m'interdit d'utiliser une autre ligne pendant que l'une est occupée.