Certains circuits électroniques peuvent être décrit comme des fonctions booléennes, c'est-a-dire des fonctions qui prennent en entrée un ou plusieurs bits et qui produisent en sortie un unique bit.

Par exemple, les portes logiques que nous avons vues précédemment peuvent être vues comme des fonctions booléennes élémentaires.

Ainsi, si on note —i(x) la fonction associee a la porte NOT, A(x, y) celle associee a la porte AND et enfin V(x, y) celle de la porte OR, ces trois fonctions sont definies par les tables de verites rappelees ci-dessous.\n\t-,(x)\tx\ty\tA(x,y)\tx\ty\tV(x,y)\n\t1\t0\t0\t0\t0\t0\t0\n1\t0\t0\t1\t0\t0\t1\t1\n1\t\t0\t0\t1\t0\t1\n1\t\t1\t1\t1\t1\t1\nPlus generalement, la table de verite d'une fonction avec n bits en entrée aura 2' lignes correspondant aux 2' combinaisons possibles des entrées. Par exemple, une fonction booleenne f avec trois entrées x, y et z sera entierement &Male par une table de verite a 23 = 8 lignes, de la forme suivante.\nx\ty\tz\tf (x, y, z)\n0\t0\t0\tf (0, 0, 0)\n0\t0\t1\tf (0, 0, 1)\n0\t1\t0\tf (0, 1, 0)\n0\t1\t1\tf(0,1, 1)\n1\t0\t0\tf(1,0,0)\n1\t0\t1\tf(1,0,1)\n1\t1\t0\tf(1,1,0)\n1\t1\t1\tf (1, 1, 1)\nComme pour les portes NAND et NOR, les trois fonctions booleennes\nelementaires\tA(x, y) et V(x, y) forment une base complete pour la\nconstructions des autres fonctions booleennes, c'est-a-dire que toute fonction booleenne pent etre definie a l'aide d'une combinaison de ces trois fonctions sur ses entrées. Aussi, pour simplifier la definition des fonctions booleennes, on utilisera plutot ces trois fonctions elementaires comme des operateurs (unaire ou binaires). Ainsi, on ecrira et dira que\nest la negation de x,\nx A y est la conjonction de de x et y,\nCes operateurs sont appeles operateurs booleens pour rendre hommage au mathematicien et philosophe Georges Boole qui inventa au 19e siècle ce calcul (on dit aussi algebre) base sur ces operateurs et ces chiffres binaires, qu'on appelle aussi des chiffres booleens.\nParmi les operateurs elementaires que nous n'avons pas encore presentes figure le on exclusif qui est frequemment utilise dans les definitions de fonctions. Cet operateur binaire, note x G y, est defini par la table de verite ci-dessous (on donne egalement la representation symbolique americaine et europeenne de la porte nominee XOR en anglais). Ii correspond au on de la carte d'un restaurant, quand il est indique dans un menu que l'on peut prendre fromage on dessert. Comme chacun sait, cela vent dire que l'on peut prendre soit un fromage, soft un dessert, mais pas les deux en meme temps. Cela se traduit par une porte logique dont le resultat est a, 1 quand une et une settle de ses entrées vaut 1, et qui renvoie 0 dans les deux autres cas.\nx y\n1\n1\n0 1 0 1\n= 1\n1\t\n1\t\nExpressions booleennes. En utilisant ces operateurs, on peut definir n'importe quelle fonction booleenne comme une expression booleenne sur ses entrees. Par exemple, l'egalite suivante definit une fonction f avec trois parametres x, y et z a l'aide d'une expression booleenne sur ces variables :\nf(x,y,z)= (xAy)EBI(yVz)\nPour calculer la table de verite associee a la fonction f, ii suffit alors de proceder comme pour un calcul arithmetique ordinaire en calculant les resultats pour toutes les sous-expressions, en commencant par les calculs en profondeur puis en remontant. Sur notre exemple, cela revient tout d'abord\ncalculer les resultats des expressions x A y et y, puis\tV z et enfin le\nresultat final.\nx\ty\tz\t(x A y)\t---,y\tHy V z)\t(x, A y) e (---,y V z)\n0\t0\t0\t0\t1\t1\t1\n0\t0\t1\t0\t1\t1\t1\n0\t1\t0\t0\t0\t0\t0\n0\t1\t1\t0\t0\t1\t1\n1\t0\t0\t0\t1\t1\t1\n1\t0\t1\t0\t1\t1\t1\n1\t1\t0\t1\t0\t0\t1\nLL.\tI.,514LIt^\nUne expression booleenne pent aussi etre manipulee comme n'iinporte quelle expression arithmetique. Pour cela, le calcul avec les operateurs booleens obeit a quelques identites elementaires dont certaines sont donnees dans le tableau ci-dessous.\ninvolutif : neutre : absorbant : idempotence : complement : commutativite : associativite : distributivite : De Morgan :\n—Hx) = x\nlAx=x\n0Ax=0\nxAx=x\nx A x -= 0\nxAy=yAx\nx A (y A z) = (x A y) Az\nx A (y V z) = (x A y) V (x A z)\n=(x A y) = x V =y\nOVX=X\n1 V x = 1\nxVx=x\nx V -a = 1\nxVy=yVx\nx V (y V z) = (x V y) V z\nx V (y A z) = (x V y) A (x V z)\n-1(x V y) = -rx A =y\nPar exemple, en utilisant ces lois, on pent montrer l'egalite suivante.\n—i(y A (x V my)) = (--ix V —,y)\nPour cela, on applique successivement les identites indiquees a droite.\n-1(y A (x V =y)) =\ty V -,(x V -,y)\tDe Morgan De Morgan distributivite complement neutre commutativite\n-\tV (—ix A y)\t\n-\t(-ry V -Ix) A (-1y V y)\t\n-\t(-ly V -Ix) A 1\t\n-\t(=y V =x)\t\n-\t

Circuits combinatoires\t\nD'une maniere generale, les circuits electroniqucs possedent plusieurs entrées et plusieurs sorties. Quand les sorties dependent directement et uniquernent des entrees, on pane de circuits combinatoires. Ils existent d'autres types de circuits, comme les circuits sequentiels, oil les sorties peuvent dependre egalement des valeurs precedentes des entrées (recues dans le passé). Ces circuits, que nous n'aborderons pas dans ce livre, possedent donc une capacite de memorisation (appelee etat du circuit) qui est utilisee pour construire des composants memoires (RAM, registres, etc.).\nLa construction des circuits (combinatoires ou autres) ressemble a un jeu de Lego dans lequel on assemble des circuits elementaires pour former des circuits plus complexes. En general, on ne part pas des portes logiques elementaires vues precedemment, mais de circuits d'un peu plus haut niveau, qui sont concus a partir de portes logiques. Parmi ces circuits, il y a par exemple des decodeurs (pour selectionner une sortie a partir des en-\ndes entrees de controle), des circuits pour comparer les entrées entre elle, ou bien encore des circuits arithmetiques (addition, soustraction, decalage, etc.). Nous presentons dans la suite deux de ces circuits.\nDecodeur. Un decodeur n bits possede n entrees et 272 sorties. Les n bits en entree sont utilises pour mettre a 1 la sortie dont le numero est egal au nombre code (en base 2) par les entrées et mettre les autres sorties a 0.\nPar exemple, un decodeur 2 bits, avec 2 entrees (60 et 61) et 4 sorties (so, 81, s2, s3), correspond a la table de verite suivante.\nentrees\t\t\tsorties\t\t\nel\teo\tSo\tSi\tS2\t83\n0\t0\t1\t0\t0\t0\n0\t1\t0\t1\t0\t0\n1\t0\t0\t0\t1\t0\n1\t1\t0\t0\t0\t1\nLe fonctionnement d'un decodeur peut aussi se definir a l'aide des quatre expressions booleennes suivantes :\nso = --leo A —lei\nSi = eo A '—'el\n32 = —ieo A el\n33 =\teo A ei\nAinsi, on peut construire un decodeur en assemblant des portes NOT et AND comme decrit dans la figure 22.1.\nAdditionneur. Le circuit pour additionner des nombres binaires de n bits est construit en mettant en cascades des additionneurs 1 bit qui realisent chacun l'addition de deux nombres de 1 bit. Ces additionneurs 1 bit sont eux-memes construits it partir d'un circuit encore plus simple appele demiadditionneur.\nUn demi-additionneur 1 bit prend en entree deux bits 60 et el et il envoie sur une sortie s la somme 60 + el. Si ce calcul provoque une retenue, il positionne alors a 1 une autre sortie c, qui indique la retenue eventuelle. La table de verite d'un demi-additionneur 1 bit est donnee ci-dessous.\nentrées\tsorties\t\t\t\neo\tCi\t8\tC\n0\t0\t0\t0\n0\t1\t1\t0\n1\t0\t1\t0\nLVL\tLUIL.7 Cl. It%IL4UC UIJI.JICCIIIIC\nCl\nso\tSi\t82\ts3\nFigure 22.1 — Schema d'un decodeur 4 bits.\neo ei\t\nFigure 22.2 — Schema d'un demi-additionneur lbit.\nComme on peut le voir sur cette table, le fonctionnement d'un demiadditionneur peut aussi se definir a l'aide des deux expressions booleennes suivantes.\n= co ED ci\n= eo A ei\nEn utilisant ces expressions, on peut facilement deduire le schema de construction d'un demi-additionneur en assemblant deux portes XOR et AND, comme decrit dans la figure 22.2.\nPour realiser un additionneur 1 bit complet, il faut prendre en compte la retenue eventuelle de l'addition de deux bits precedents. Ainsi, un additionneur 1 bit est un circuit qui prend en entrees deux bits eo, el et une retenue co, qui produit le resultat s = eo + el + co, en positionnant eventuellement la retenue c finale.\nOn construit cet additionneur 1 bit en utilisant deux demi-additionneurs. Le premier demi-additionneur calcule la somme so = eo +el, en positionnant\neo\t\t\t\t\n\t\t\t\t\n\t\t\t\t\n\t\t\t\t\nFigure 22.3 — Schema d'un additionneur lbit.\nsomme s = co ± so, en positionnant eventuellement a 1 une retenue c2. La retenue finale c vaut 1 si l'une des deux retenues Cl ou c2 est a 1. La table de verite d'un additionneur 1 bit complet est donnee ci-dessous.\n\tentrees\tsorties\t\t\t\n60\t61\tCo\t5\tC\n0\t0\t0\t0\t0\n0\t0\t1\t1\t0\n0\t1\t0\t1\t0\n0\t1\t1\t0\t1\n1\t0\t0\t1\t0\n1\t0\t1\t0\t1\n1\t1\t0\t0\t1\n\t111\t\t\t11\nEn utilisant deux schemas de demi-additionneur 1 bit, on peut facilement deduire le schema de construction d'un additionneur 1 bit complet comme decrit dans la figure 22.3.\nOperations sur les bits en Python. Python dispose de nombreux operateurs qui agissent directement sur les nombres au niveau des bits. Ces operateurs sont appeles operateurs bit-a-bit (operateurs bitwise en anglais). Par exemple, l'operateur & realise un et logique entre les bits de deux nombres.\n>>> bin (0b0101 & Ob1100) 'Ob100'\nComme on le voit dans cet exemple, Python n'affiche les bits d'un nombre binaire qu'a partir du premier bit non nul. Cela est dfi au fait que les nombres binaires sont infinis en Python.\nLes autres operateurs logiques bit-a-bit de Python sont x I y et x\ty\npour respectivement le on logique et le on exclusif entre x et y, ainsi que le complement a 1 note -x qui inverse les bits d'un nombre x.\nPython propose egalement des operateurs pour decaler les bits d'un nombre vers la droite ou vers la gauche. Ces operateurs de decalage, notes << et >> prennent deux arguments : le premier est le nombre dont il faut decaler les bits et le deuxieme est le nombre de position a decaler. Par exemple, pour decaler les bits d'un nombre de 2 positions vers la gauche, on ecrira\n>» bin (0b0001010 << 2) Ob101000'\nII est interessant de noter que ces operations de decalage sont des operateurs extremement efficaces pour multiplier ou diviser un nombre par une puissance de 2.\nA retenir. Les circuits d'un ordinateur sont fabriques iL partir de portes logiques elementanes, elles-mernes construites ii part ir de transistors on les vateurs booleennes 0 et 1 sont materiallsees par des con-rants electriques. Les portes logiques perrnettent de construire des fonctions booleennes arbitraires, tales quo des deoodeurs on des additionneurs. Le langa.ge Python perrnet d'appliquer des operations bit-a-bit sin la representation en base 2 des entiers.\n