Logique combinatoire

Dans un système combinatoire, chaque sortie S_k de k=0 à k=m-1 est une expression booléenne des entrées e_j de j=0 à j=n-1.

Les expressions booléennes peuvent être simplififiées, ce qui fait que certaines variables d'entrée peuvent ne pas apparaître dans l'expression booléenne des sorties.
A chaque combinaison des variables d'entrées correspond une valeur et une seule pour chaque sortie.
Le nombre de combinaison des entrées est égale à 2ⁿ
Le nombre de sorties est défini par la fonction combinatoire à réaliser.

Si on affecte un poids binaire aux sorties par rapport à l'indice, alors la valeur binaire des sorties correspond au numéro de l'indice de l'entrée activée.

On peut remarquer que la table de vérité est imcomplète car elle ne représente que les combinaisons des entrées utilisées. Pour les expressions booléennes des sorties, on peut soit écrire l'expression en fonction de toutes les sorties et faire en sorte que toute autre combinaison que celle de la table donne 0, ou encore simplifier les expressions booléennes, ce qui fait que les combinaisons des entrées non prévues donneront un résultat inattendu.

Dans ce cas toutes les combinaisons des entrées sont définies. Le code en sortie correspond à l'entrée de plus grand indice qui est activée.

Exemple :
si les entrées e₁ et e₂ sont activées le code en entrée est 01100000, code qui correspond au code de sortie 010 (2₁₀), ce code indique que l'entrée de plus haut niveau activée est 2.

Si l'on affecte un poids binaire aux entrées par rapport aux indices, l'exemple précédent montre que l'image de la valeur 6 est 2

Plus généralement, la fonction mathématique réalisée par ce circuit est : $y=\lfloor {\log }_2(x)\rfloor$

Ici on a 3 entrées et 8 combinaisons, toutes les combinsaisons sont donc définies.

Comme pour le codeur, si on affecte un poids binaire aux entrées pour obtenir une valeur décimale, le numéro de la sortie activée correspond à la valeur décimale des entrées.

Exemple
avec la combinaison d'entrée e₂=1, e₁=0 et e₀=0 qui donne 0100₂=4₁₀, c'est la sortie d'indice 4 qui est activée. Si on affecte également une valeur décimale à la sortie en utilisant les indices comme références des poids binaires, avec la valeur 4 en entrée, on obtient 2⁴=16 en sortie.

Plus généralement, la fonction mathématique réalisée par cette fonction est : S=2^E avec S qui représente la valeur décimale équivalente des sorties de poids binaire de 0 à 7, et E qui représente la valeur décimale équivalente des entrées de poids binaire de 0 à 2.

La table de vérité complète comporte 11 entrées et 1 sortie, ce qui donne 2048 combinaisons. La table de vérité proposée est simplififiée en donnant l'entrée qui est connectée à la sortie en fonction des valeurs binaires des adresses.

Si on prend la valeur de l'adresse a₂=1, a₁=0, a₀=0 qui donne A=100₂=4₁₀, on peut lire que la sortie S est reliée à l'entrée e₄. Ce qui signifie que si e₄=0 alors S=0 et si e₄=1 alors S=1.

La table de vérite comporte 4 entrée et 8 sorties. On aurait pu la représenter complètement, mais on préfère utiliser la même représentation que pour le multiplexeur.

Si on prend la valeur de l'adresse a₂=1, a₁=0, a₀=0 qui donne A=100₂=4₁₀, on peut lire que la sortie S₄ est reliée à l'entrée e. Ce qui signifie que si e=0 alors S₄=0 et si e=1 alors S₄=1, les autres sorties étant toutes à 0 quelue soit la valeur de l'entrée e.

La sortue Eg est vraie si a=b, la sortie Sup est vraie si a>b et la sortie Inf est vraie si a<b.

Cela donne les équations :

• Eg = a ⊕ b
• Sup = ab̅
• Inf = a̅b

On ne va pas donner la table de vérité avec 5 entrées et 3 sorties.
Les règles de la mise en cascade sont les suivantes :

• Si l'entrée eSup est vraie alors la sortie Sup est vraie quelque soit les valeurs a et b
• Si l'entrée eInf est vraie alors la sortie Inf est vraie quelque soit les valeurs a et b
• Si l'entrée eEg est vraie alors l'état des sorties est défini en fonction des valeurs de a et b en respectant la règle du comparateur 1 bit précédent.

Exemple avec la comparaison de deux mots de 4 bits (n=4) non signés.

Le schéma représente un additionneur 4 bits avec retenue d'entrée C₀ et retenue de sortie C₃.

Le résultat est négatif si S_n-1=1 ce qui implique que Rs_n-2=1 et Rs_n-1=0.

On a donc un dépassement $\mathrm{O}=\overline{{\mathrm{Rs}}_{\mathrm{n-1}}}.{\mathrm{Rs}}_{\mathrm{n-2}}$

Le résultat est positif si S_n-1=0 ce qui implique que Rs_n-2=0 et Rs_n-1=1.

On a donc un dépassement $\mathrm{O}={\mathrm{Rs}}_{\mathrm{n-1}}.\overline{{\mathrm{Rs}}_{\mathrm{n-2}}}$

Exemple 1

Soit à comparer les valeurs A=12 et B=7 exprimés sur 4 bits non signes

1. Additionner A et le complément à 2 de B
2. Déduire les valeurs des bits Z,N,C,O
3. Donner le résultat de la comparaison

Eléments de solution

1. Le complément à 2 de B qui vaut :

   0

   1

   1

   1

   est :

   1

   0

   0

   1

   
   Le résultat de l'opération est :

   0

   1

   0

   1

   
   Les retenues sont Rs₃ = 1 et Rs₂ = 1
2. Les valeurs des bits sont :

   Z	=	0
   N	=	0
   C	=	1
   O	=	1

3. Le résultat de la comparaison est 12 > 7

Exemple 2

Soit à comparer les valeurs A=2 et B=8 exprimés sur 4 bits non signes

1. Additionner A et le complément à 2 de B
2. Déduire les valeurs des bits Z,N,C,O
3. Donner le résultat de la comparaison

Eléments de solution

1. Le complément à 2 de B qui vaut :

   1

   0

   0

   0

   est :

   1

   0

   0

   0

   
   Le résultat de l'opération est :

   1

   0

   1

   0

   
   Les retenues sont Rs₃ = 0 et Rs₂ = 0
2. Les valeurs des bits sont :

   Z	=	0
   N	=	1
   C	=	0
   O	=	1

3. Le résultat de la comparaison est 2 < 8

Exemple 3

Soit à comparer les valeurs A=-5 et B=-4 exprimés sur 4 bits signes

1. Additionner A et le complément à 2 de B
2. Déduire les valeurs des bits Z,N,C,O
3. Donner le résultat de la comparaison

Eléments de solution

1. Le complément à 2 de B qui vaut :

   1

   1

   0

   0

   est :

   0

   1

   0

   0

   
   Le résultat de l'opération est :

   1

   1

   1

   1

   
   Les retenues sont Rs₃ = 0 et Rs₂ = 0
2. Les valeurs des bits sont :

   Z	=	0
   N	=	1
   C	=	0
   O	=	0

3. Le résultat de la comparaison est -5 < -4

La fonction est S=f(0,4,6,7).

La fonction est S=f(3,5,6,7).

La fonction est S=f(0,2,8,10,12,13,14,15).

La fonction est S=f(0,2,8,10,12,13,14,15).

• Calcul et technologies
• Un peu de géométrie
• Plus de mathématiques
• Jeux mathématiques
• Systèmes informatiques
• Réseaux et télécommunications