17 Jan

La division euclidienne

Publié par Nain0nain ,

La division euclidienne

Hey salut tout le monde c'est parti pour faire de la division :

  • C'est quoi la division
  • Comment on fait un division
  • Et c'est parti pour un circuit

1. C'est quoi la division ? :

Aujourd'hui la division fait partie des opérations de base en math : elle sert à trouver un nombre x tel que n*x = m, donc m/n = x, où m est le dividende n le diviseur et x le quotient. En faite c'est juste une multiplication inversée. Mais on apprend aussi qu'il existe la division dite euclidienne : avec un reste, c'est à dire que x(le quotient) = q+ r; où q ∈ ℕ et r ∈ ℕ, ils sont des entiers naturels, donc sans virgule.

C'est forcément celle là que l'on va utiliser, parce que on à toujours pas vu les nombres à virgule en binaire actuellement !

2. Comment on fait cette division :

Bon bah comme en primaire !

La division euclidienne

Ici on regarde combien de fois 12 "rentre" dans 35, ici 2 : 2*12 = 24, alors 35 - 24 = 11, sauf que maintenant 12 ne rentre pas dans 11. Q = 2 et r = 11 : 2*12 + 11 = 35.

En binaire c'est la même chose : Ici comme on est en binaire il suffit de regarder la différence de l'étage (ici par exemple le premier étage la différence est 110 - 101) si elle est positive, "on met" 1 au quotient. Sinon la différence est négative donc "on met" 0 au quotient. Puis dans tout les cas on réutilise la différence du premier étage (110 - 101 = 1) puis on descend (flèche en rouge) le chiffre binaire suivant pour refaire la différence... ainsi de suite jusqu'à plus rien à descendre qui nous donne le reste

Un dessin est toujours mieux

Un dessin est toujours mieux

Attention il faut s'aider de l'image pour mieux comprendre : Soit 1101011(A)/101(B); ici c'est tout simple :

1er étage : on commence par faire 110(A) - 101(B) > 0 alors on rajoute 1 au quotient (q = 1). Ensuite 110(A) - 101(B) = 1, on le descend avec l'autre 1(flèche rouge).

2ème étage : la prochaine opération est 11(A) - 101(B) < 0 alors on rajoute 0 à q (maintenant q = 10), et donc au lieu de soustraire pour passer à l'opération suivante on descend directement le 0(flèche rouge) tout en gardant le 11 : ça donne 110...et ainsi de suite jusqu'à avoir tout fait, et le quotient sera donc 10101(q) et le reste 10(r)

Ce qu'il nous faut : un soustracteur qui donne le signe, et une méthode pour utiliser les bons chiffres, c'est à dire descendre les termes de A quand il faut ! Et c'est ce qu'on fera plus tard en "pratique"

3. Un circuit :

Bon on est parti pour un méga circuit qui ressemble beaucoup à la multiplication. Je vais pas trop rentrer dans le détail parce que c'est bornant et que si on a compris tout le reste c'est facile à comprendre par soit même.

Comme dans le circuit en parallèle de la multiplication, le circuit est fait de "capsule" de base imbriquées ensembles :

La division euclidienne

La capsule est tous simplement composé d'un soustracteur et de trois autres portes pour choisir le bit à faire passer quand le descend (correspond pas à la flèche rouge du schéma plus haut, mais à la différence des termes). puis le circuit entier correspond à ça :

Hop

Hop

Soit les entrées A0 - A3 et B0 - B3, où les A sont les dividendes et les B sont les diviseurs.

1er : On commence toujours part B0 - A3 ==> le circuit fait la différences et passe la retenue (Li) à celui d'à côté qui fait la différence B1 - 0 (0 parce que on est au premier étage) et fait passer la retenue ainsi de suite. Si la retenue est de 0 à la fin c'est que forcément B0B1B2B3 - A3 > 0 donc le quotient doit se voir prendre 1, comme vu plus haut, Q3 = 1; et l'inverse si la retenue vaut 1 à la fin, c'est que la différence est négative donc Q3 = 0, c'est pour cela qu'il y a un inverseur. Ensuite OS vaut soit 0 soit 1 en fonction de la retenue et passe dans les circuits pour choisir le bon bit à faire descendre.

2ème : Cette fois pareil; mais avec B0B1B2B3 - A2; et les différence successive ne sont plus B1 - 0 mais B1 - D' qui vient du premier étage (correspond pas au flèche rouge sur les schéma plus haut, mais au résultat de la différence) ainsi de suite.

Jusqu'à arriver au dernier étage où les bits restants sont les restes. Encore une fois ce circuit est très rapide vu le nombre de portes logiques. Il faut savoir que maintenant le nombre de portes logiques n'importe plus car les transistors sont de l'ordre de quelques nanomètres, et bien au contraire c'est la vitesse qui importe.

Sur ce portez vous bien.

Sommaire

Nain0nain

Nain0nain

Retour au menu : fonctionnement du processeur
Commenter cet article

unefilletropconne 05/10/2015 17:51

ahhhh.. Mark Zuckerberg is inside!

MArco 05/10/2015 17:51

Clique sur mon nom tu vas voir ce que je sais faire

Ta mere 05/10/2015 17:50

Salut Pierrot

Ta mere 05/10/2015 17:49

Encore un mec qui prend les autres pour des tdc...

Suivez nous sur :