Discussion :

[Auteur]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pseudocode]

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 ?

[Obsidian]

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.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Auteur]

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

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é.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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).

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.

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.

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.

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

[Obsidian]

- 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.

-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

Je vais développer (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.

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.

[Auteur]

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).

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

| {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 :

Sélectionner tout - Visualiser dans une fenêtre à part

| {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 ?