Obligement - L'Amiga au maximum

Vendredi 24 novembre 2017 - 21:26  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


Dossier : La logique combinatoire
(Article écrit par Jean-François Pillou - 2003)


Note : ce document est issu de Comment Ça Marche et mis à disposition sous les termes de la licence Creative Commons.

Algèbre de Boole

Un processeur est composé de transistors permettant de réaliser des fonctions sur des signaux numériques. Ces transistors, assemblés entre eux forment des composants permettant de réaliser des fonctions très simples. A partir de ces composants il est possible de créer des circuits réalisant des opérations très complexes. L'algèbre de Boole (du nom du mathématicien anglais Georges Boole 1815 - 1864) est un moyen d'arriver à créer de tels circuits.

L'algèbre de Boole est une algèbre se proposant de traduire des signaux en expressions mathématiques. Pour cela, on définit chaque signal élémentaire par des variables logiques et leur traitement par des fonctions logiques. Des méthodes (table de vérité) permettent de définir les opérations que l'on désire réaliser, et à transcrire le résultat en une expression algébrique. Grâce à des règles appelées lois de composition, ces expressions peuvent être simplifiées. Cela va permettre de représenter grâce à des symboles un circuit logique, c'est-à-dire un circuit qui schématise l'agencement des composants de base (au niveau logique) sans se préoccuper de la réalisation au moyen de transistors (niveau physique).

Variable logique

Un ordinateur ne manipule que des données binaires, on appelle donc variable logique une donnée binaire, c'est-à-dire une donnée ayant deux états possibles: 0 ou 1.

Fonction logique

On appelle "fonction logique" une entité acceptant plusieurs valeurs logiques en entrée et dont la sortie (il peut y en avoir plusieurs) peut avoir deux états possibles : 0 ou 1.

En réalité ces fonctions sont assurées par des composants électroniques admettant des signaux électriques en entrée, et restituant un signal en sortie. Les signaux électroniques peuvent prendre une valeur de l'ordre de 5 Volts (c'est l'ordre de grandeur général) que l'on représente par un 1, ou 0 V que l'on représente par un 0.

Les portes logiques

Les fonctions logiques de bases sont appelées portes logiques. Il s'agit de fonctions ayant une ou deux entrées et une sortie :
  • La fonction OU (en anglais OR) positionne sa sortie à 1 si l'une ou l'autre de ses entrées est à 1.
  • La fonction ET (en anglais AND) positionne sa sortie à 1 si ses deux entrées sont à 1.
  • La fonction OU EXCLUSIF (en anglais XOR) positionne sa sortie à 1 si l'une ou l'autre de ses entrées est à 1 mais pas les deux simultanément.
  • La fonction NON (appelée aussi inverseur) positionne sa sortie à 1 si son entrée est à 0, et vice-versa.
On définit généralement les fonctions NON OU (couramment appelée NOR) et NON ET (NAND) comme étant la composition respective d'un NON avec un OU et un ET.

Chronogramme

Un chronogramme est un diagramme montrant l'évolution des entrées et des sorties en fonction du temps. Voici par exemple ce à quoi pourrait ressembler un chronogramme de l'opérateur ET :

Logique combinatoire

Ce chronogramme en un chronogramme idéal, en réalité les signaux électriques ne passent pas instantanément de 0 à 1, les pentes (ici verticales) sont obliques, et le traitement des entrées cause un retard sur les sorties :

Logique combinatoire

Expression algébrique

Le but de l'algèbre de Boole est de décrire le traitement de signaux sous forme d'expression algébrique. Comme nous l'avons vu, les signaux sont représentés par des noms de variables. Les fonctions logiques sont représentées par des opérateurs :
  • La fonction OU est représentée par un plus : +
  • La fonction ET est représentée par un point : .
  • La fonction NON est représentée par une barre au-dessus de la variable inversée : Logique combinatoire. Elle est parfois représentée par un / devant la variable inversée.
  • La fonction OU EXCLUSIF est représentée par un plus encerclé : Logique combinatoire.
Une expression algébrique sera donc une expression du type : Logique combinatoire

Table de vérité

Une table de vérité est un tableau permettant de décrire toutes les possibilités de sorties en fonction des entrées. On place donc les variables d'entrées dans les colonnes de gauche en les faisant varier de telle façon à couvrir l'ensemble des possibilités. La colonne (ou les colonnes si la fonction a plusieurs sorties) de droite décrit la sortie.

Voici par exemple les tables de vérités des portes logiques :

Nom de la porte Entrée Sortie
 AB
S
OU
00
0
01
1
10
1
11
1
ET
00
0
01
0
10
0
11
1
NON OU
00
1
01
0
10
0
11
0
NON ET
00
1
01
1
10
1
11
0
NON
0
1
1
0

Il est possible à partir de la table de vérité d'une fonction d'écrire l'expression algébrique de celle-ci. Soit la table de vérité suivante :

Entrée Sortie
AB
S
00
0
01
0
10
1
11
0

La sortie vaut 1 lorsque A vaut 1 et B vaut 0, l'expression algébrique de cette fonction est donc :

Logique combinatoire

Prenons maintenant la table de vérité suivante :

Entrée Sortie
ABC
S
000
0
001
0
010
1
011
0
100
0
101
0
110
1
111
0

La sortie vaut 1 lorsque :
  • A vaut 0
  • B vaut 1
  • C vaut 0
ou
  • A vaut 1
  • B vaut 1
  • C vaut 0
L'expression algébrique de cette fonction est donc : Logique combinatoire

Les lois de composition

Les lois de composition sont des règles logiques qui permettent de simplifier l'écriture des expressions algébriques.

Associativité

(A.B).C est équivalent à A.(B.C)
(A+B)+C est équivalent à A+(B+C)

Absorption

A.(A+B) est équivalent à A
A+A.B est équivalent à A

Commutativité

A.B est équivalent à B.A
A+B est équivalent à B+A

Distributivité

A+(B.C) est équivalent à (A+B).(A+C)
A.(B+C) est équivalent à A.B+A.C

Idempotence

A.A est équivalent à A
A + A est équivalent à A

Identité

1.A est équivalent à A
0+A est équivalent à A

Inversion

A./A est équivalent à 0
A+/A est équivalent à 1

Nullité

0.A est équivalent à 0
1+A est équivalent à 1

Théorème de De Morgan

Logique combinatoire est équivalent à Logique combinatoire
Logique combinatoire est équivalent à Logique combinatoire

Exemple de simplification d'expression

Soit la simplification suivante :

Logique combinatoire

Circuits logiques

Représentation des portes logiques

La représentation conventionnelle des portes logiques est la suivante :

Logique combinatoire Logique combinatoire

Réalisation de circuits logiques

On appelle circuit logique (ou circuit combinatoire) un ensemble de portes logiques reliées entre elles pour répondre à une expression algébrique. Il s'agit donc d'aller transcrire en schéma électrique (à l'aide des représentations ci-dessus) l'expression algébrique que l'on a simplifiée grâce aux lois de composition.

Par exemple l'expression algébrique
 (A+B).(A+/C)
sera schématisée comme suit :

Logique combinatoire

Additionneurs

Un additionneur est un circuit capable de faire la somme de plusieurs nombres. Une addition met en oeuvre deux sorties :
  • La somme, généralement notée S.
  • La retenue, généralement notée R.
Lorsque l'on fait une somme en décimal (base 10), on ajoute dans un premier temps les deux unités, puis si le résultat obtenu est supérieur à 10, on garde la dizaine restante en retenue, pour l'ajouter lors de la somme des dizaines des deux nombres. Ce procédé est le même en binaire.

Additionneur de deux nombres de 1 bit

Pour une addition de deux nombres A et B de 1 bit, 4 combinaisons sont possibles, et le résultat occupe 2 bits : un bit pour la somme (S) et un pour la retenue (R).

Voici la table de vérité de cette fonction :

Entrée Sortie
A B
R
S
00
0
0
01
0
1
10
0
1
11
1
0

L'expression logique de cette fonction est donc :

Logique combinatoire

Le circuit peut donc être représenté selon le schéma électrique suivant :

Logique combinatoire


[Retour en haut] / [Retour aux articles]