Fondements

a question que se pose peut-être l’étudiant en ouvrant cet ouvrage est : Pourquoi circuits logiques ?
La logique réfère d’usage à la pensée, alors que les circuits sont à priori des dispositifs physiques obéissant à des règles précises dont on ne perçoit aucune émanation de pensée…

Il est d’usage de vulgariser le fonctionnement des ordinateurs en disant que ce sont des machines qui représentent et traitent l’information sous forme de zéros et de uns (0/1). Aussi, si on associe respectivement à ces zéro et un le sens de FAUX et VRAI, on peut relever un prélude de signification au mot logique dans « circuits logiques »… Mais est-ce tout ?

Les circuits logiques, que nous appellerons également circuits numériques, ne se retrouvent pas uniquement dans les ordinateurs. À l’ère de l’information qui est la nôtre, ils envahissent le domaine de la technologique jusqu’à le dominer presque intégralement. Aussi, il importe de comprendre les notions relatives à leur fonctionnement, conception, et la manière dont on y encode l’information. L’objet du cours de circuits logiques est d’introduire les notions qui sous-tendent la technologie numérique. Cependant, avant d’attaquer de plein fouet les chapitres théoriques et techniques de cet ouvrage, nous avons cru bon de revenir sur le sens qu’auront pour nous les qualificatifs logique et numérique.

Ces termes puisent leurs origines dans une multitude de disciplines, lesquelles se croisent de façon étonnamment filandreuse et féconde, réunissant des domaines de la connaissance tels que la philosophie, la cybernétique, les sciences cognitives, les mathématiques, etc.… Nous essayerons donc d’exposer — sans aucune prétention d’exhaustivité toutefois — ces racines étymologiques, en revenant sur des éléments historiques jugés d’importance. Cet exposé s’étalera des sections 1.1 à 1.3, et sa lecture reste facultative bien qu’elle soit fortement suggérée.

Finalement, et afin de confronter rapidement l’étudiant à son objet d’étude, nous conclurons le chapitre par une section de vulgarisation des notions de base des circuits logiques. Ces notions seront exposées avec davantage de rigueur dans les chapitres subséquents. L’intention ici est de permettre à l’étudiant de démarrer son apprentissage et de s’initier en laboratoire à la manipulation de circuits logiques simples. Aussi, la lecture de la section 1.4 est indispensable.

1.1                La logique, un formalisme de la pensée

La philosophie grecque fut l’une des premières à poser la problématique de la validité du raisonnement en termes systématiques. Aristote fut l’instigateur de ce projet qui consistait à établir les règles que suit le raisonnement humain. Ce faisant, Aristote énonça une partie importante des règles de la logique que nous connaissons aujourd’hui, et ces règles furent considérées valides et complètes durant plus de vingt siècles. Ce n’est qu’au début du XX^e siècle que ces règles furent interrogées en profondeur, et il fallut pour cela que se mêle à la philosophie d’autres disciplines de la connaissance, principalement les mathématiques.

Le lien avec les mathématiques put être établi grâce aux travaux de George Boole. À la fin du XIX^e siècle, ce mathématicien britannique autodidacte propose d’écrire les propositions logiques sous forme d’équations algébriques. Il en simplifie ainsi la manipulation et crée un heureux pont entre l’algèbre et la philosophie.

1.1.1     Notions de logique aristotélicienne

Aristote (384-322 av. J.-C.) avait entre autres ambitions de théoriser de manière systématique les processus de la pensée. Ses travaux sur la logique sont réunis dans un ouvrage appelé Organon. Ce travail est d’une actualité manifeste puisque l’on rencontre encore des références importantes qui considèrent les théories d’Aristote sur la pensée humaine comme point de départ aux leurs[1]. Afin de donner un aperçu sur la nature de la logique aristotélicienne, nous allons nous intéresser au syllogisme.

Le syllogisme est un raisonnement logique menant à une conclusion fondée sur l’accord de deux propositions (appelées prémisses). La forme générique du syllogisme est présentée dans l’exemple suivant :

            Tous les hommes sont mortels

            Je suis un homme

            Je suis mortel

Pour que le syllogisme soit valide, il faut que les prémisses comportent un terme majeur (Tous les hommes sont mortels) et un terme mineur (Je suis un homme). Ces deux unités sont liées par un moyen terme (homme) qui permet d’aboutir à la conclusion (Je suis mortel).

En exposant une formalisation du mécanisme de pensée, le syllogisme permet d’éviter les abus de langage qui pourraient faussement mener à des paradoxes étonnants. Un exemple ludique est connu sous le nom de paradoxe du gruyère :

            Plus il y a de gruyère, plus il y a de trous

            Plus il y a de trous, moins il y a de gruyère

            Plus il y a de gruyère, moins il y a de gruyère

Plus sérieusement, grâce au syllogisme il devient possible de démasquer les aberrations du type :

Tous les chats ont des moustaches

            J’ai des moustaches

            Je suis un chat

1.1.2     Sujet et prédicat dans la logique aristotélicienne

Les prémisses contiennent le sujet, le prédicat et le moyen terme qui les unit. Le prédicat est la qualité (la propriété) du sujet considéré. Dans le premier exemple sur le syllogisme :

            Tous les hommes sont mortels

            Je suis un homme

            Je suis mortel

Homme(s) est le moyen terme, le prédicat est être mortel, tandis que le sujet est Je.

Le syllogisme se présente donc sous la forme :

            {Le moyen terme est prédicat} or {le sujet est moyen terme} donc {le sujet est prédicat}

Il suffit de modifier cette écriture pour voir un rapport (confirmé plus tard par la logique mathématique et les travaux de Boole) entre la logique aristotélicienne et la théorie des ensembles :

                {Le moyen terme est dans prédicat} or {le sujet est dans moyen terme} donc {le sujet est dans prédicat}

Ainsi, le premier raisonnement s’avérait juste pour la simple raison que l’ensemble des Hommes est une sous partie de l’ensemble des Mortels. « Je » est un élément de l’ensemble des Hommes, et devient du même geste un élément des Mortels.

Cela n’est pas vrai pour le troisième (faux) syllogisme :

Tous les chats ont des moustaches

            J’ai des moustaches

            Je suis un chat

Dans ce cas, le sujet « Je » n’est pas un élément de l’ensemble des chats et le raisonnement s’avère faux. La figure suivante illustre cette différence :

 

1.1.3     Raisonnement, déduction et inférence

En logique, on dira d’une proposition qu’elle est vraie ou fausse. Ainsi, des propositions vraies ou fausses génèrent par combinaison d’autres propositions au moyen d’opérateurs logiques, et ces nouvelles propositions deviennent, à leur tour, vraies ou fausses suivant les tables de vérité définissant les opérateurs impliqués. On considère les opérateurs de conjonction (ET), de disjonction (OU), de négation (NON) et d’implication. On considérera également l’équivalence qui permet de dire si deux propositions ont la même valeur. L’ensemble de ces outils sera respectivement noté Ù, Ú, ¬,  É et º.

Les tables de vérités associées à ces opérateurs sont :

A B A Ù B FAUX FAUX FAUX FAUX VRAI FAUX VRAI FAUX FAUX VRAI VRAI VRAI	A B A Ú B FAUX FAUX FAUX FAUX VRAI VRAI VRAI FAUX VRAI VRAI VRAI VRAI	A ¬A FAUX VRAI VRAI FAUX
Opérateur Ù (conjonction)	Opérateur Ú (disjonction)	Opérateur ¬ (négation)
A B A  É B FAUX FAUX VRAI FAUX VRAI VRAI VRAI FAUX FAUX VRAI VRAI VRAI	A B A  º B FAUX FAUX VRAI FAUX VRAI FAUX VRAI FAUX FAUX VRAI VRAI VRAI
Opérateur É (implication)	º (équivalence)

On peut utiliser ces opérateurs pour illustrer l’invalidité d’un raisonnement a priori évident mais faux. Prenons l’exemple suivant :

La mère (ou le père) d’un enfant dit à sa désinvolte progéniture :

« Si tu ne fais pas tes devoirs, tu n'iras pas au cinéma. »

L’enfant naïf comprend :

« Si tu fais tes devoirs, tu iras au cinéma. »

Or le raisonnement est faux. Il s’avère en effet que :

Si tu ne fais pas tes devoirs, tu n'iras pas au cinéma.

n'équivaut pas à :

Si tu fais tes devoirs, tu iras au cinéma

La preuve est aisée. Soient A et B deux propositions, telles que : A : Tu fais tes devoirs ; B : Tu iras au cinéma.
Il est facile de démontrer que

(A  É B  ≡ ¬A É ¬B) est FAUX

Prenons un contre exemple : Soit A VRAI et B FAUX. Le côté gauche de l’équivalence donne FAUX, alors que celui de droite donne VRAI. On constate comment l’introduction d’opérateurs logiques permet de cautionner un raisonnement en manipulant des équations. C’est selon le même principe que George Boole va proposer une notation algébrique de la logique.

1.1.4     L’avènement de l’algèbre de Boole

George Boole (1815-1864) était un mathématicien anglais qui voyait dans les outils algébriques une écriture élégante permettant de manipuler simplement les propositions logiques de la philosophie aristotélicienne. Boole développe ses théories dans deux ouvrages : 1) Mathematical Analysis of Logic, 1847; 2) An Investigation Into the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities, 1854.

Cette algèbre de la logique, que l’on appelle depuis algèbre de Boole, remplace les valeurs VRAI et FAUX par les éléments 1 et 0 et les opérateurs logiques (ET, OU) par les opérations arithmétiques de multiplication et d’addition ( ∙ , + ). L’opérateur unaire NON, servant à la négation, est également introduit (  ). Elle permet ainsi d’écrire toute proposition logique à l’aide de variables logiques (booléennes) et de manipuler de manière systématique le raisonnement par le développement d’équations mathématiques. L’algèbre de Boole n’allait cependant pas seulement outiller la philosophie d’une notation compacte, elle allait d’une part donner aux mathématiques le corpus dont elles allaient avoir besoin pour reconstruire leurs fondements ; et, sous forme appliquée, l’algèbre de Boole allait prendre de l’ampleur et bouleverser le XX^e siècle grâce aux travaux en télécommunication de l’ingénieur américain Claude E. Shannon.

1.2                La logique mathématique

Contrairement à la philosophie, les mathématiques restreignent le champ d’application de la logique pour leurs fins utiles. La logique mathématique ne prétend donc pas refléter les mécanismes de la pensée humaine, elle se contente de l’utiliser pour valider l’exactitude de ses propositions et ses théorèmes. Le mathématicien grec Euclide (325-265 av. J.-C.) fut un pionnier sur ce chemin, faisant usage de la logique mathématique comme fondement systématique de sa formulation axiomatique de la géométrie. C’est donc très tôt que la logique fut approchée en mathématiques en tant qu’outil permettant de systématiser le raisonnement. Ce faisant, les mathématiques, cantonnées au rang d’art de la mesure des distances se sont élevées à celui de discipline scientifique purement déductive où les théorèmes se déduisent les uns des autres par une suite d’enchaînement logiques.

L’expression logique mathématique est cependant relativement contemporaine. Ce n’est qu’à partir du XX^e siècle qu’elle apparut, et elle s’est depuis imposée comme discipline à part entière des mathématiques.  La chose fut rendue possible par la conjonction de deux évènements historiques, à savoir l’avènement de l’algèbre de Boole, qui retranscrivait les opérateurs logiques comme des opérateurs algébriques, et les travaux de Cantor, un mathématicien allemand, qui, voulant donner une base axiomatique à l’arithmétique.

1.2.1  Théorie des ensembles

Dans la section 1.1.2, nous avons vu de manière illustrative qu’il était possible d’énoncer le syllogisme sous une forme ensembliste. C’est ainsi que la théorie des ensembles et la logique ne pouvaient que finir par se rencontrer. La théorie des ensembles fut introduite par le mathématicien allemand, Georg Cantor (1845-1918), dans une approche tout à fait novatrice. Les concepts de base étaient les ensembles et leurs éléments. Un ensemble se définit comme une collection d’objets appelés éléments. Un ensemble peut aussi être l’élément d’un autre ensemble.

Méprisé par ses contemporains et par ses confrères, chercheur tourmenté et rongé par les angoisses de son ambition mathématique, Cantor a été un mathématicien révolutionnaire. Son projet était de reconstruire les mathématiques sur une base axiomatique dont les fondements devaient être l’arithmétique. Pour ce faire, Cantor utilisa une abstraction difficile à comprendre. Le plus choquant pour ses contemporains était sa manipulation « hasardeuse » de l’infini et ses résultats étonnants qui s’avéraient souvent contre-intuitifs.

Cantor introduisit le concept de cardinalité d’un ensemble — le nombre de ses éléments en quelque sorte. Quand un ensemble est infini, des résultats aux semblants paradoxaux surgissent. Par exemple l’ensemble des entiers ℕ a le même cardinal (nombre d’éléments) que l’ensemble des entiers pairs 2ℕ.  Tout élément de 2ℕ est effectivement dans ℕ, or il existe au moins un élément de ℕ (par exemple 1) qui n’appartient pas à 2ℕ. Cette conception de l’infini avait du mal à être acceptée dans le contexte de l’époque, celui-là même qui faisaient dire à Leibniz deux siècles plus tôt: « Si le nombre de tous les nombres n’est pas plus grand que le nombre des nombres pairs, c’est que le tout n’est pas plus grand que la partie, ce qui est absurde. »

David Hilbert (1862-1943), mathématicien allemand de grande renommée, avait eu une très large influence sur son époque. Il fut parmi les premiers à saisir les développements de Cantor et à les valoriser auprès de la communauté scientifique. On lui doit une sympathique parabole qui permet de comprendre la cardinalité:

« Un homme, Hilbert, tient un hôtel avec un nombre infini de chambres. Un client arrive à la réception et veut louer une chambre pour une nuit. Hilbert aimerait aider ce visiteur. Malheureusement, son hôtel est plein. Hilbert demande alors aux clients de la chambre i de s’installer dans la chambre i+1. La chambre n°1 se libère et le client y prend place. Un peu plus tard dans la soirée, un car de voyageurs avec un nombre infini de passagers arrive à la porte de l’hôtel. Hilbert se frotte les mains en pensant à la manne que voilà. Mais son hôtel est plein ! Cette fois, Hilbert demande aux clients de la chambre i de s’installer dans la chambre 2[JP1] ∙2i; il libère du même geste une infinité de chambres prêtes à accueillir les touristes arrivés. »

C’est sur la base de ce type de raisonnement que Cantor démontre que la cardinalité de ℕ est égale à celle de 2ℕ,  on établit une bijection entre les éléments des deux ensembles : f (x) = 2x. Si une telle bijection existe, les cardinaux des deux ensembles sont égaux. Ainsi, Cantor démontre que l’ensemble des rationnels ℚ a le même cardinal que ℕ. On dit de ce type d’ensembles qu’ils sont infinis dénombrables. Cette bijection est impossible à établir par exemple entre l’ensemble des nombres réels ℝ et ℕ. Cantor prouve que le cardinal de ℝ est supérieur à ℕ, c’est-à-dire qu’il existe infiniment plus de réels que d’entiers. Il établit de la sorte qu’il existe différentes infinités et que celles-ci pourraient être hiérarchisées. L’ensemble ℝ est infini et indénombrable. À force de taquiner les paradoxes, et malgré l’hostilité des pairs qui lui aura nui de son vivant, Cantor ouvrit de larges brèches dans le domaine des mathématiques. Hilbert aura cette phrase remarquable à l’égard de son travail : « Nul ne doit nous exclure du paradis que Cantor a créé. » [2]

1.2.2  Paradoxe de Russell

Bertrand Russell (1872-1970) fut un des plus importants hommes de science et des arts du XX^e siècle ; mathématicien, philosophe, logicien et épistémologue, il fut aussi érudit que prolifique. En 1901, Russel énonce le paradoxe éponyme qui dévoile une lacune importante dans la définition dite « naïve » des ensembles, c’est-à-dire tels qu’on les entendait depuis les travaux de Georg Cantor. Ce paradoxe s’exprime de la façon suivante : « L’ensemble des ensembles ne se contenant pas eux-mêmes se contient-il lui-même ? » Si on répond oui à la question, on contrevient à la définition puisque les éléments de l’ensemble sont des ensembles qui ne se contiennent pas eux-mêmes ; si au contraire on répond non, l’ensemble des ensembles ne contenant pas eux-mêmes devrait se contenir, d’où contradiction encore une fois.

Il existe une forme plus imagée du paradoxe de Russell que l’on doit à Russell lui-même. Elle est connue comme le paradoxe du barbier : « Un roi décide de condamner à mort tout barbier de son royaume qui ne rase pas un homme qui ne se rase pas lui-même, et ordre est donné aux barbiers de ne raser personne d’autre. Le barbier se trouve dans une situation paradoxale : 1) S’il ne se rase pas lui-même, il enfreint le décret royal en ne rasant pas un homme qui ne se rase pas lui-même ; 2) Si, au contraire, il se rase lui-même, le barbier enfreint le décret royal en rasant un homme qui se rase lui-même. »

Ce faisant, Russell mit en lumière une faille inhérente dans la définition naïve des ensembles et appelait à une formalisation de la théorie des ensembles. Au début du XX^e siècle, les mathématiques devenaient suspectes et l’on tâchait de redéfinir leurs fondements. C’est ce que proposera Hilbert dans son énonciation des 23 plus importants problèmes mathématiques du XX^e siècle.

1.2.3  Programme de Hilbert

Lors du deuxième congrès international des mathématiques, tenu en 1900 à Paris, Hilbert énonçait 23 problèmes que les mathématiques n’avaient pas encore résolus et qui devaient en consolider les fondements. La découverte de paradoxes dans les théories de Cantor laissait planer un pessimisme scientifique ambiant où les mathématiques étaient perçues comme incohérentes et fragiles.

Hilbert n’était pas de cet avis. Selon lui, une construction axiomatique des mathématiques était possible. Au  « Nous ne savons pas et nous ne saurons jamais » de la doctrine pessimiste Ignorabimus, il opposait son « Nous devons savoir et nous pourrons savoir » qu’il martela à la radio de Königsberg. [3]

Parmi les 23 problèmes que Hilbert proposa pour sauver les mathématiques, certains furent abandonnés (c’est le cas du sixième problème portant sur l’axiomatisation de la physique), d’autres demeurent irrésolus aujourd’hui (huitième problème, doté d’un prix d’un million de dollars par l’Institut de Mathématiques Clay). Quant au second problème, qui demandait que soit démontrée la consistance (absence de contradiction) axiomatique de l’arithmétique, il allait aboutir à des résultats pour le moins inattendus.

Kurt Gödel (1906-1978) mathématicien autrichien naturalisé américain, établit en 1929, dans sa thèse de doctorat[4], que le calcul logique était complet, c’est-à-dire que toute formule valide était démontrable par les axiomes et que le système ne souffrait d’aucune contradiction. On crut que ce premier pas positif allait mener au succès du programme de Hilbert. Mais voilà que le logicien prouvait quatre ans plus tard que le programme de Hilbert est voué à l’échec.

Gödel énonce en 1931 le théorème d’incomplétude. Un premier théorème démontrait qu’un ensemble fini d’axiomes ne pouvait prouver l’entièreté des théorèmes d’un système formel non contradictoire tel que l’arithmétique. Autrement dit, certains énoncés sont indécidables, c’est-à-dire que l’on ne peut dire s’ils sont vrais ou faux. Mais Gödel allait plus loin avec un second théorème où il exprime l’incomplétude d’un système formel en ce que sa cohérence (absence de contradiction) ne peut être démontrée à l’intérieur des formules dont le système dispose, et ce ne peut être fait qu’en requérant à un système qui lui est supérieur. Les mathématiques poussaient la logique dans ses derniers retranchements.

1.3                La naissance de l’âge numérique

La conjoncture qui aboutit à l’émergence des ordinateurs — et à l’ère de l’information qui s’en est suivie — n’a pas été un long chemin tranquille. Dans le sillon du programme de Hilbert, une cohorte de scientifiques issus de différents domaines firent la synthèse de leurs savoirs, et ce travail de concertation allait changer la face du monde en nous donnant l’ordinateur.

Alors que les mathématiques, dans ses développements sur la logique, avaient délaissé l’investigation de l’esprit humain, la problématique allait devenir centrale quand se posa la question d’exprimer le vivant sous forme mathématique, et l’assimilation qui s’en est suivi du cerveau humain à une machine. Les mathématiciens, les biologistes et les ingénieurs commençaient de se parler, et le fruit de leur travail n’a pas fini de nous étonner.

Nous tenterons ici d’illustrer l’étendue et la diversité des contributions scientifiques qui ont créé une conjonction entre la modélisation mathématique du fonctionnement du cerveau, les systèmes automatiques et les modèles de machines de calcul. Cela nous permettra de comprendre progressivement l’exigence qui s’est fait sentir d’une représentation unifiée des instructions de contrôle et de calcul.

1.3.1  La machine de Turing

Pour démontrer qu’un système formel non contradictoire était incomplet, Gödel introduisit un système de numération où il associa un nombre différent à chaque symbole du système formel, puis un nombre différent à chaque proposition et un nombre différent à chaque prédicat. La déduction d’un théorème à partir d’un ensemble d’axiomes était alors transposée à son expression par un nombre de Gödel, obtenu par le produit des premiers nombres premiers élevés à la puissance des termes qu’ils font intervenir. Il ne restait plus qu’à démontrer qu’il existait un nombre de Gödel associé à un théorème qu’il était impossible d’exprimer par les nombres associés aux axiomes…

Aussi, avec Gödel, le raisonnement mathématique devient un calcul, et le concept de démontrabilité devient celui de calculabilité. Cette idée allait progressivement germer dans l’esprit du mathématicien britannique Alan Turing (1912-1954) qui se donnait pour défi d’automatiser le raisonnement mathématique en automatisant le calcul. Il formalisa donc ce qu’il est convenu d’appeler la machine de Turing et démontra qu’une telle machine pouvait servir pour répondre au dixième problème de Hilbert[5].

[JP2] 

Illustration d’une machine de Turing

Une machine de Turing est aussi étonnante de simplicité que sont impressionnantes ses capacités. Elle se compose d’un ruban infini (divisé en des cases individuelles) et d’une tête de lecture/écriture pouvant se mouvoir le long du ruban, ruban sur lequel la tête de lecture lit et écrit l’information. Il est ainsi possible de contrôler les tâches de la tête de lecture, et cette dernière peut retranscrire une réponse lisible sur le ruban.

1.3.2  La cybernétique

Les travaux de Turing allaient avoir un impact important sur la suite des développements scientifiques. De l’entre deux-guerres jusqu’aux années soixante, une communauté de chercheurs s’organisa et prit progressivement de l’importance en s’articulant autour de grandes personnalités, telles que Warren McCulloch, Walter Pitts et Frank Rosenblatt. À compter de 1946, ce groupe organisa régulièrement à New York ce qu’on appela les Conférences Macy qui réunissaient entre autres des économistes, des psychologues, des physiologistes, des anthropologues, des logiciens et des mathématiciens. Une nouvelle école résultat de ces rencontres et de ces échanges et s’appropria dès 1950 le nom de cybernétique. Le sens étymologique du mot cybernétique vient du grec et signifie ce qui dirige.

Le point commun entre les travaux des chercheurs participants était leur recours à la rétroactivité. La rétroactivité consiste en une propagation circulaire de l’information à des fins régulatrices. On propage donc la sortie[6]  vers l’entrée afin d’obtenir un effet correcteur. Ce concept avait été mis en application en 1859 dans des vaisseaux fonctionnant à la vapeur. En effet, l’ingénieur Joseph Farcot (1824-1906) inventa le servomoteur permettant de contrôler le gouvernail et de le manœuvrer à l’aide de l’énergie de la vapeur.

La motivation de ces scientifiques était de réunir l’intérêt des ingénieurs qui travaillaient à construire des systèmes permettant d’exercer un asservissement (contrôle), celui des autres scientifiques qui tentaient de modéliser de la même façon des systèmes complexes (marché financier, organismes vivants) au moyen de modèles usant de rétroaction. Les travaux de Turing ayant crédibilisé le concept de machine en tant qu’entité pouvant effectuer des tâches complexe, l’idée de ramener les mécanismes du cerveau à un niveau calculable allaient largement animer les débats des conférences Macy.

1.3.3  Le neurone artificiel

Fondateurs de l’école de cybernétique, le neurophysiologiste Warren McCulloch (1899-1969) et le logicien Walter Pitts (1923-1969) publient en 1943 l’un des deux articles clés de leur école. Entre autres développements, ils proposent un modèle mathématique du neurone biologique. L’information véhiculée dans le cerveau étant électrique, ils proposent que les interconnections des neurones se transmettent des pulses. Un neurone répond éventuellement si la stimulation de ses voisins est suffisante, étant donnée leur importance respective.

Les auteurs proposent que le neurone somme des entrées x_i pondérées par des coefficients w_i. Cette somme définit son état d’excitation. Les coefficients  positifs agissent de manière excitatrice, tandis que les coefficients négatifs ont un rôle inhibiteur. Le résultat de la somme pondérée est ensuite traduit en code binaire (0/1). Si la somme est négative, la sortie vaut zéro, ce qui signifie que le neurone ne produit pas de pulse. Si au contraire la somme est positive, la sortie vaut un et le neurone produit un pulse. Un biais est ajouté pour améliorer les capacités du neurone.

Une curiosité propre à cette cellule est sa capacité d’apprendre. Si on y adjoint un système rétroactif de régulation  des coefficients de pondération, un algorithme d’apprentissage simple peut être mis au point et la cellule passe du statut de modèle mathématique à celui d’objet dynamique capable d’extraire automatiquement des connaissances suite à un processus d’apprentissage.

Les réseaux de neurones — neurones artificiels interconnectés — ont des applications potentielles dans différents domaines : optimisation des paramètres dynamique de la forme des ailes d’un avion, pilotage automatique d’aéronefs, reconnaissance de formes, classification de données empiriques. Aussi, leur implémentation physique a longtemps suscité un intérêt certain. Frank Rosenblatt (1929-1969), un informaticien issu de l’école cybernétique, fut le premier à simuler sur un ordinateur[7] un neurone artificiel, appelé le perceptron. Son succès draina un grand intérêt parmi ses contemporains et on vit se diversifier les tentatives de mise en application. Les réseaux de neurones trouvent diverses applications industrielles :
1) Sur les ordinateurs PDA où ils servent à la reconnaissance des caractères écrits à l’aide d’un stylet; 2) Dans le domaine postal où ils servent à décoder les codes régionaux; 3) Dans le système bancaire — la plus lucrative des applications — où ils servent à la détection de fraude sur les cartes de crédit.

1.3.4 La machine de von Neumann

John von Neumann (1903-1957) fut sans conteste un des cerveaux les plus féconds du XX^e siècle. D’origine hongroise, il suivit, selon le souhait de son père des études d’ingénieur chimiste et mena en même temps des études en mathématiques. Il obtient son doctorat en mathématiques à l’âge de 23 ans. Il se fit remarquer très tôt en publiant des papiers de grande envergure. En 1930, il fut invité à se joindre aux États-Unis, à Princeton, comme membre du nouveau Institute of Advanced studies, où  œuvrent Einstein et Gödel.

Savant génial, d’une vivacité d’esprit qui lui permettait d’établir une preuve en peu de temps, John von Neumann a laissé dans son sillage des anecdotes époustouflantes : 1) Lors d’un séminaire de mathématiques donné à Zurich où l’étudiant von Neumann était présent, un professeur présente un théorème en disant : « Ceci n’a pas été prouvé et la preuve est difficile. » Cinq minutes plus tard, von Neumann lève la main et monte au tableau pour écrire la preuve. Pólya, ledit professeur, dit qu’il aura toujours peur de von Neumann après cet incident[8]. 2) Avant de publier son article, Gödel présente le premier théorème d’incomplétude lors d’une conférence où John von Neumann est présent. Ce dernier est impressionné, d’autant plus qu’il travaillait lui-même sur l’axiomatisation de l’arithmétique. Après trois mois, von Neumann écrit une lettre à Gödel pour lui exposer une conséquence (et la preuve) de son premier théorème, qui sera énoncé comme le second théorème de Gödel.

Outre la logique et la théorie des ensembles, John von Neumann a également eu des contributions majeures en mécanique quantique, en économie (théorie des jeux) et dans le domaine militaire[9]. Celle qui retiendra notre attention ici sera sa contribution au domaine de l’informatique. John von Neumann, membre assidu des conférences Macy jusqu’en 1950, s’intéressa au fonctionnement des systèmes auto-réplicatifs en biologique. Ce qui attirait l’intérêt de John von Neumann, c’était la capacité d’un organisme vivant de générer un motif (sur sa coquille par exemple) alors que les cellules ne disposent que d’une information locale (les cellules voisines).

Von Neumann proposa donc un modèle d’automate cellulaire pouvant générer un motif à partir d’une information locale[10]. Nous allons considérer ici un exemple simple : Soit un automate cellulaire unidimensionnel (les cellules forment un segment de ligne) où chaque cellule peut prendre deux valeurs possibles, 0/1, que nous reproduirons de manière visuelle en utilisant (respectivement) les couleurs blanc et noir. Chaque cellule change périodiquement de couleur (toutes les secondes, par exemple) suivant une règle locale : sa couleur et celle de ses voisins. La table suivante présente la règle dit 30[11] que suit chaque cellule :

Les couleurs locales (011 par exemple) indiquent dans l’ordre la couleur du voisin de gauche, celle de la cellule considérée et finalement celle de droite (blanc, noir et noir dans l’exemple 011). La couleur à prendre indique celle que prendra la cellule étant donné la configuration correspondante. Considérons maintenant 21 cellules alignés et partons de l’état suivant :

Pour les cellules du bord (aux extrémités gauche et droite), on considère que le voisin manquant est blanc. Nous allons maintenons dérouler la règle sur une période de temps en superposant les séquences les unes sous les autres :

Comme on peut le constater, cette règle simple permet de générer un motif global à partir d’une information locale. L’approche de von Neumann s’inscrivait alors dans le sens de l’école de cybernétique qui cherchait à réunir la biologie, l’ingénierie et l’algorithmique en ce qu’elle suggérait de s’inspirer de la nature pour mettre au point des automates.

À compter de 1950, von Neumann s’éloigna de cette école et critiqua vigoureusement le neurone de McCulloch et Pitt. Il considérait que l’idée de ramener la neurologie à la logique (les entrées et sorties du perceptron sont binaires) limite malheureusement les capacités de calcul. Il suggéra au contraire que la logique s’inspirât de la biologie pour étendre ses capacités, et il proposa une logique probabiliste[12]. Cette critique semblait étonnante néanmoins, et du propre aveu de Marvin Minsky, étudiant de John von Neumann[13], car von Neumann utilisa une approche de logique usuelle quand il inventa l’architecture de nos processeurs.

Motif d’une coquille de Conus Textile

En 1945, l’Université de Pennsylvanie obtient de l’armée américaine un contrat pour construire un ordinateur permettant de calculer les trajectoires balistiques. Ce projet donnera naissance à L’EDVAC (Electronique Discrete Variable Automatic Computer) et l’Université de Pennsylvanie fit appelle à John von Neumann pour l’aider dans sa tâche. Dans une ébauche de rapport devenu célèbre depuis[14], von Neumann posa les bases de ce que sera l’architecture de nos microprocesseurs. Contrairement au neurone de McCulloch et Pitts, que von Neumann cite dans son rapport, les unités de l’ordinateur de von Neumann ne travaillent pas en parallèle mais effectuent le calcul de manière séquentielle, c’est-à-dire une opération à la fois. Autre innovation, et peut-être la plus marquante, la mémoire contient sur le même espace l’instruction (le code) et les données, ce qui n’est pas sans rappeler la machine de Turing[15].

1.4                La technologie au service de la science

La crédibilisation du concept de machine (en tant que système permettant d’effectuer des tâches complexes) et l’avènement de modèles théoriques de machines de calcul ne pouvait se concrétiser que par l’apport de moyens technologiques permettant de les réaliser et de les mettre en œuvre. Nous avons pu voir qu’un des concepts fondamentaux dans les modèles de calcul est l’information (les données). Celle-ci devait pouvoir être codée, et ce codage devait être encadré par une théorie forte.

C’est Claude Shannon (1916-2001) qui va apporter la réponse à cette question. À la fin des années trente, Shannon est étudiant à la maîtrise au Massachusetts Institute of Technology (M.I.T.) où il travaille sur l’automatisation des circuits à relais (interrupteurs) pour les besoins grandissants de la téléphonie. Au M.I.T., Shannon suit un cours de philosophie où il découvre l’algèbre de Boole, et c’est la révélation. Shannon comprend que l’écriture algébrique de prépositions prédicatives pourrait être mise à contribution pour ses besoins particuliers, et développe cette idée dans son mémoire qu’il termine en 1940[16].

1.4.1Circuits à relais

Aux premiers temps de la télécommunication, la téléphonie reposait sur un large réseau de relais permettant de mettre en communication les usagers. Un relais était un interrupteur qu’une opératrice raccordait suivant les besoins des clients des compagnies de téléphone pour créer les connexions. Quand le réseau commençait à s’élargir, le problème d’automatisation de ces réseaux s’est posé, et c’est Shannon qui allait y trouver une solution en apportant un cadre théorique issu de l’algèbre de Boole.

Pour ce faire, Shannon convient qu’un circuit ouvert est représenté par un 0, un circuit fermé par un 1 :

Shannon établit ensuite un ensemble d’opérateurs inspirés de l’algèbre de Boole :

[JP3] 

Shannon introduit également les opérateurs de négation et d’égalité : 1) Si on dispose d’un relais X, est un relais qui se ferme lorsque X est ouvert, et vice et versa; 2) On dit que X=Y si X et Y se ferment et s’ouvrent en même temps. Avec ces outils en main, on comprend qu’il devenait possible de manipuler logiquement un circuit à relais, et éventuellement de le simplifier. L’exemple suivant illustre l’exemple une telle manipulation où les circuits à relais (a) et (b) sont identiques :

Ce résultat découle du fait que A∙C+A∙D+B∙C+B∙D = (A+B)∙(C+D).

1.4.2Portes logiques

D’abord avec les tubes électroniques, et plus profondément encore avec l’invention du transistor, l’implémentation physique de composants jouant le rôle de relais contrôlés devint possible et les circuits logiques purent prendre forme. Avec l’algèbre logique de George Boole, on sait que toute fonction logique peut être exprimée en utilisant les opérateurs NON, ET et OU[17]. On introduit donc des composants, appelés portes logiques, qui correspondaient à ces opérateurs :

Les tables de vérités des trois opérateurs ont été données à la section 1.1.3, nous les reproduisons ici pour une facilité de lecture :

A 0 1 1 0	A B A∙B 0 0 0 0 1 0 1 0 0 1 1 1	A B A+B 0 0 0 0 1 1 1 0 1 1 1 1
Opérateur NON (Inverseur)	Opérateur ET (conjonction)	Opérateur OU (disjonction)

Pour réaliser un circuit contrôlant un relais dont la fermeture est actionnée lorsque (A+B)∙(C+D) est vrai, il suffit de considérer le circuit logique suivant :

Nous pourrions nous demander : Que se passe-t-il si A=1, B=1, C=0 et D=0 ? Nous allons injecter les valeurs des variables dans l’équation (A+B)∙(C+D) :

[ A+B | A=1, B=1  ] = 1+1 = 1

[ C+D | C=0, D=0 ] = 0+0 = 0

[ (A+B)∙(C+D) | A=1, B=1, C=0, D=0 ] = 1∙0 = 0

Dans ce cas là, nous comprenons que le relais sera ouvert.

À ces trois portes de base, nous allons ajouter deux autres, obtenues en inversant les portes ET et OU. Nous les appellerons respectivement NON-ET et NON-OU :

Les tables de vérités qui leur sont associées (déduites des précédentes) vont comme suit :

A B 0 0 1 0 1 1 1 0 1 1 1 0	A B 0 0 1 0 1 0 1 0 0 1 1 0
NON-ET	NON-OU

Un fait remarquable concernant ces deux portes : Si l’on disposait uniquement de NON-OU (respectivement NON-ET), il serait possible d’exprimer toute fonction logique à l’aide de ces portes. Comment est-ce possible ? Nous le verrons dans le chapitre suivant.

Le circuit suivant présente comment on peut réaliser le circuit (A+B)∙(C+D) avec des NON-OU :

Finalement, deux autres portes logiques sont ajoutées à notre boîte à outils, nous les appellerons
OU-EXLUSIF et NON-OU-EXCLUSIF.  Pour mieux comprendre le sens de OU-EXCLUSIF, revenons au langage usuel. Vous demandez à un ami de vous apporter un donut ou un muffin. Cette personne revient et vous apporte un donut et un muffin, ce qui n’est pas exactement ce que vous vouliez.

Si nous revenons à la table de vérité du OU, on se rend compte que votre ami a bien agi. Mais pourquoi y
a-t-il une différence entre le ou usuel et le ou logique. Ce que vous vouliez dire à votre ami, c’était : « Apporte-moi une sucrerie, un donut ou un muffin, mais pas les deux. » Cette proposition est exprimée par
le OU-EXCLUSIF. On veut l’un ou l’autre, mais pas les deux, ensemble. Le NON-OU-EXCLUSIF est simplement son inverse, comme l’illustrent les tables de vérité (qui indiquent également les symboles associés) :

A B AB 0 0 0 0 1 1 1 0 1 1 1 0	A B AB 0 0 1 0 1 0 1 0 0 1 1 1
OU-EXCLUSIF	NON-OU-EXCLUSIF

Notons ici que le NON-OU-EXCLUSIF correspond à l’équivalence logique (º).

Le lecteur est invité à faire l’exercice d’exprimer sous forme de ET, OU et NON le circuit de l’exemple suivant :

1.4.3Représentation binaire des entiers

Jusqu’ici, nous avons vu que nous disposions d’outils pour encoder l’information sous forme de 0 et de 1, et que nous avions une théorie permettant de manipuler très précisément ces 0 et ces 1. Mais que voulons-nous encoder ? À priori, nous voulons faire du calcul, aussi allons-nous vouloir représenter des quantités en 0 et en 1. Cet encodage va apporter la question de la quantification que nous aborderons dans la section 1.4.4. Mais nous allons commencer par voir comment cela se passe pour les entiers.

Supposons que nous voulions représenter des entiers positifs (0, 1, 2, …). Nous allons utiliser un nombre de N bits[18] a_N-1a_N-2…a₂a₁a₀. Chaque bit a_i peut prendre une valeur binaire (0/1), et nous obtenons la valeur de l’entier ainsi écrit en faisant usage du polynôme P :

P=a_N-12^N-1 + a_N-22^N-2 + …+ a₂2² + a₁2 + a₀

Par exemple, nous allons utiliser quatre bits. Nous pourrons alors représenter 16 nombres (0, 1, 2, 3, …, 15). Pour bien comprendre la chose, considérons le tableau suivant :

Si on y regarde de plus près, on se rend compte que cette écriture binaire des nombres n’est pas très différente de celle utilisée dans notre usage. Par exemple, 61 532 s’écrit :

61 532   = 6· 10 000 + 1· 1 000 + 5· 100 + 3· 10 + 2

             = 6· 10⁴  + 1· 10³ + 5· 10² + 3· 10 + 2

On dira que nous utilisons d’habitude la base 10 alors que nous utilisons la base 2 dans le monde des circuits logiques. En vérité, un entier peut être écrit dans n’importe quelle base b (b est un entier >1) et sa valeur est donnée par le polynôme P_b :

P_b=a_N-1b^N-1 + a_N-2b^N-2 + … +  a₂b² + a₁b¹ + a₀b⁰

1.4.4Discrétisation

Un signal est dit « analogique » si sa valeur évolue (à priori de façon continue) dans le domaine des nombres réels. L’ingénieur électrique dira que le signal analogique est un représentant du monde. Il entend par là qu’un nombre important de phénomènes physiques, pouvant être captés et convertis en tensions (ou courants) électriques, permettent un traitement électrique ou électronique faisant appel à ses talents. On citera à ce titre les signaux physiologiques (tels que l’électrocardiogramme — ECG — ou l’électroencéphalogramme — EEG —), les signaux sonores (voir figure plus bas) ainsi que des signaux plus complexes à plus d’une variable, comme les images (deux variables) ou les signaux vidéo (trois variables).

Les signaux numériques sont un avatar des signaux analogiques. Ils s’étendent sur une gamme numérale plus restreinte et ne connaissent pas la continuité. Ainsi, alors qu’il existe une infinité de valeurs réelles entre 24 et 34, le nombre de valeurs possibles dans cet intervalle est fini dans le pendant numérique. Cela est dû à ce qu’on appelle la discrétisation.

De la même manière qu’il est impossible (et inutile) de mémoriser toutes les décimales de pi dans un système numérique, il est impossible (et inutile) de mémoriser la valeur exacte de n’importe quel signal analogique. La discrétisation est une opération qui consiste à faire correspondre un intervalle continu (et donc infini) à une valeur unique. Par exemple, pi peut être approximé par la valeur 3.14, image de l’intervalle [3.135, 3.145[ dans un système numérique précis au centième.

Comme les signaux sont généralement fonction d’une ou plusieurs variables (le temps et/ou parfois l’espace), une deuxième discrétisation est nécessaire et consiste à ne mesurer le signal qu’en des valeurs discrétisées de ses variables. Les Disc Compacts (DC), par exemple, mémorisent la valeur de la pression acoustique 44100 fois par seconde. C’est ce qu’on appelle la fréquence d’échantillonnage. À priori, la valeur du signal n’est donc connue qu’à ces instants. Toutefois, si le signal évolue suffisamment lentement (par rapport à sa fréquence d’échantillonnage), sa valeur peut être extrapolée à n’importe quel moment par des techniques de reconstruction du signal.

Afin de mieux comprendre ces concepts, considérons l’enregistrement du signal électrique résultant du son de pizzicato.

Une fois échantillonné à 44100 Hz, il prend la forme suivante (zoom sur une petite partie du signal) :

Les valeurs des tensions (obtenues en ordonnée), sont alors discrétisées à l’aide d’un CAN (Convertisseur Analogique – Numérique). Le procédé de discrétisation consiste à diviser l’intervalle des tensions en paliers, comme présenté dans l’exemple de la figure suivante et à faire correspondre les valeurs en abscisse à celles se trouvant en ordonnée. Une valeur numérique est alors attribuée à chaque pallier.

 

Dans le domaine des images numériques, et par extension de la vidéo numérique, le principe de discrétisation est à peu près équivalent. Pour nous en convaincre, considérons la figure suivante :

 

L’image de gauche est capturée par une caméra conventionnelle sur un négatif permettant de reproduire la continuité du monde extérieur. L’image de droite représente un équivalent numérique avec une résolution de l’image fortement réduite.

On voit que l’image est divisée en petits carrés (discrétisation de l’espace image) et que chaque petit carré contient une couleur, un niveau de gris, qui s’étend en fait sur 256 valeurs, allant de 0 à 255 (discrétisation de la luminosité). Ces valeurs sont enregistrées en mémoire sous forme binaire, c’est-à-dire un ensemble de 0 et de 1.

Les images de couleur utilisent une représentation équivalente, c’est-à-dire une discrétisation de l’espace image, accompagnée d’une discrétisation des intensités lumineuses. La différence réside dans le fait que pour réaliser une image numérique de couleur, il convient d’utiliser trois matrices d’intensité, correspondant chacune à une longueur d’onde de la lumière, une pour le rouge, la seconde pour le bleu et la dernière pour le vert. La combinaison des trois couleurs donne un large spectre de couleurs possibles. Si on s’en tient à la division de l’intensité lumineuse en 256 niveaux, on obtient au final plus de 1,67 million de couleurs possibles (256 x 256 x 256).