Cours 2 : Transistors, Fonctions arithmétiques, Additionneur, Multiplicateur

Chapitre 2

Fonctionnement d’un ordinateur

Architecture de l’IAS : modèle de programmation le plus bas aujourd’hui

  • En physique : tout est continu

VS

  • informatique : discret

⟶ continu VERS discret : la transition sera expliquée

  • transistors, portes logiques ⟶ fonctions arithmétiques et logiques
  • aspect dynamique (temps discret)

Transistor

Inventé en 1925, utilisé en info dès 1950

  • base : barre verticale
  • collecteur : flèche

∃ une couche isolante en émetteur (E) et collecteur (C) ⟶ flux d’électrons entre eux à partir d’un certain seuil de tension ⟶ logique du 0/1 discrète (principe binaire)

Si voltage :

  • en dessous : pas de flux E⟶C
  • au-dessus : ∃ flux

si voltage d’entrée =

  • bas ⟹ pas de connexion à la terre ⟹ voltage haut en sortie
  • haut ⟹ flux d’électrons ⟹ voltage bas en sortie (relié à la terre)

C_1 (à gauche), C_2 (à droite)

A B C_1 C_2 H H B B B B H H B H H B H B H B — – –

NB: On peut générer $\lnot, \lor, \land$ avec NAND (NON-ET)

Portes logiques

Convention diagrammes :

  • petit cercle final : NON-Opérateur
  • section droite : ET
  • section courbée : OU
  • double section : exclusif
  • triangle + petit cercle : NON

NB : on peut avoir plus de 2 entrées, tant que le nombre d’entrées ne dépend pas de $n$ (nb de transistors ≃ nb de diagrammes)

  • taille : nombre de transistors ⟶ objectif : $O(n)$
  • profondeur : taille (en nb de transistors) du chemin le plus long qu’un signal peut traverser (profondeur ≤ taille) ⟶ objectif : $O(log(n))$

Ex: essayer de créer le XOR avec des NON-OU

Fonctions arithmétiques

  1. Demi-additionneur
Entrée : deux bits
Sortie : deux bits, R la retenue, S la somme

A B R S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 – – – –

NB : Quand on dessine les multipôles : attention à bien indiquer entrée(s)/sortie(s)

  1. Additionneur complet

Résultat souhaité : \((r_1.s)_2 = x + y + r_0\)

($r_i$ : reste)

Addition de deux entiers
  • taille/profondeur : linéaire (/profondeur : à cause de la retenue à propager) ⟶ Pas satisfaisant ___ NB : Pratique à connaître par coeur :

$n$ $2^n$ 4 16 7 128* 8 256 10 1024** 15 32768 16 65536*** 20 1048576**** – –

* : cf. entiers signés sur 8 bits : de -128 à 127

** : cf. 1ko = 1024o

*** : short int

**** : 1Mo

32bits : 4 Go

Additionneur basé sur propagation/génération

Soient $i, j ∈ ⟦0,n⟧$ : on considère les bits aux positions $i$ à $j$ dans les vecteurs $x$ et $y$ en entrée.

Le bloc $i ⋯ j$ :

  • propage une retenue
  • génère une retenue (donc en partic. propage)

Circuit pour la multiplication

Soient $x= (x_{n-1}, ⋯, x_0)$ et $y= (y_{n-1}, ⋯, y_0)$ deux entiers naturels.

On souhaite construire un circuit efficace pour calculer $z = (z_{2n-1}, ⋯, z_0)$

Multiplication classique : \(z = \sum\limits_{0\leq i, j \leq n-1} x_i y_j 2^{i+j}\)

⟶ $n^2$ bits de poids différents.

(NB: multiplication de deux bits ⟶ AND)

Si on pose la multiplication à la main :

        0 1 1 0
        1 0 1 0
        _______
        0 0 0 0
      1 0 1 0
  0 0 0 0
1 0 1 0
  • on doit faire $n$ additions (taille : $O(n)$, profondeur : $O(\log(n))$) + taille = $n^2$
  • Mais MIEUX : on procède par dichotomie : on fait $O(\log(n))$ additions.

Amélioration : on réduit par un facteur de 2/3 chaque colonne en découpant la colonne par des groupes de 3 ($x, y, r$) qui deviennent groupe de 2 ($s, r$)

OU $\lor$ : par ex :

  • union d’ensembles
  • mettre certains bits à un (ex: demande de priorité des périphériques sur les actions de l’ordinateur)

ET $\land$ : par ex :

  • intersection d’ensembles
  • pour savoir si le $i$-ème bit vaut :
    • 1, en multipliant par 00⋯010⋯00
    • 0, en multipliant par 11⋯101⋯11

Décalage : 0110 << 1 vaut 1100 (on perd le bit tout à gauche + complété par des 0 à la fin)

Rotation : idem, mais rotation circulaire

Ex:

0101110011100001 ⟶ combien de 1 ? (ex: réponse : 8 = 1000)

  1. on test chacun des bits avec des $\land$ pour savoir si ce sont des 1 ou des 0 ⟹ en $O(n)$
  2. MEUX : diviser pour régner :
    • On découpe en 2, puis en 2, etc…
    • bloc de 1 bit : facile
    • PUIS : bloc de 2
0101110011100001
0101110011100001
⇓
_ 1 _ 1 _ 1 _ 0 _ 1 _ 0 _ 0 _ 1
0 _ 0 _ 1 _ 0 _ 1 _ 1 _ 0 _ 0 _

(avec des AND)

⇓

_ 1 _ 1 _ 1 _ 0 _ 1 _ 0 _ 0 _ 1
_ 0 _ 0 _ 1 _ 0 _ 1 _ 1 _ 0 _ 0

(shift à droite)

⇓

somme
  • bloc de 4
0101110011100001
0101110011100001
⇓
0 1 _ _ 1 1 _ _ 1 1 _ _ 0 0 _ _
_ _ 0 1 _ _ 0 0 _ _ 1 0 _ _ 0 1
⇓
etc...

⟹ complexité en $O(\log(n))$

Leave a comment