Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 01 - Le codage des binaires

BUT DE L’ESSENTIEL

Ce document est un complément au cours mis à disposition des étudiants dans le cadre de l’enseignement du module d’architecture des ordinateurs (1CPA). Il a pour objectif premier de fournir aux étudiants des éléments d’informations et des références supplémentaires afin de leur permettre d’approfondir certains domaines selon les centres d’intérêt de chacun.

PLAN DU CHAPITRE

Ce chapitre va suivre trois grandes parties :

  • La première partie montre l’importance du numérique dans notre société. Nous expliquons d’abord l’évolution historique des techniques touchant au numérique depuis l’invention du tube à vide en 1904 jusqu’à nos jours. Un premier bilan et proposé l’utilisation du numérique ne peut parfois pas tout résoudre.

  • La seconde partie est la mise en place des interfaces entre l’ordinateur (le monde numérique) et l’extérieur. Nous décrivons quelques termes liés à la théorie du traitement du signal avant. Puis, nous nous intéressons à l’aspect pratique, illustré par des exemples.

  • La troisième partie est la découverte du monde binaire en essayant de répondre à la question : "Pourquoi faire du binaire ?". Ensuite, les algorithmes de conversions et les opérations avec les binaires seront étudiés et détaillés.

LE TRAITEMENT DU NUMERIQUE

LA PLACE DU NUMERIQUE

Il faut bien comprendre que le numérique est avant tout un moyen pour mieux stocker des informations. Malgré des environnements changeants les méthodes de stockage numérique ont finalement peu évoluées et la notion de binaire reste prédominante.

L'EVOLUTION DU NUMERIQUE AU COURS DES SIECLES

Télévision numérique terrestre en haute définition, économie numérique, appareil photo numérique, tablette, 4K, 4G, … sont autant de termes qui prouvent de l’importance du numérique (et ses architectures les utilisant) dans notre quotidien. Pour bien juger de cette évolution qui nous concerne tous, nous allons donner quelques dates clefs pour mesurer le chemin parcouru pour obtenir nos appareils et outils d’aujourd’hui.

LA PREMIERE GENERATION DE MACHINE

Le numérique est apparu, il y a un siècle, d’abord avec l’invention du tube à vide (l’équivalent de la diode) par l’anglais John Ambrose FLEMING (29 novembre 1849 – 18 avril 1945) en 1904 :

Figure 1.1. Figure 1 : John Ambrose FLEMMING et le premier tube à vide

Figure 1 : John Ambrose FLEMMING et le premier tube à vide

Puis de la mise au point de la triode (équivalent du transistor) par Lee DE FOREST (26 août 1873 – 30 juin 1961) en 1906 :

Figure 1.2. Figure 2 : Lee DE FOREST, la première triode et les triodes utilisées sur les postes radio

Figure 2 : Lee DE FOREST, la première triode et les triodes utilisées sur les postes radio

Ces innovations technologiques permit à John Vincent ATANASOFF (4 octobre 1903 – 15 juin 1995) et Clifford BERRY (19 avril 1918 – 30 octobre 1963) de construire le premier ordinateur électronique numérique en 1939 :

Figure 1.3. Figure 3 : John Vincent ATANASOFF, Clifford BERRY et une réplique de la machine ABC

Figure 3 : John Vincent ATANASOFF, Clifford BERRY et une réplique de la machine ABC

La machine ABC (Atanasoff Berry Computer) est le premier ordinateur de la première génération de machines.

La machine la plus emblématique de l’époque est l’ENIAC (Electronic Numerical Integrator and Computer) qui fut mise au point entre 1943 et 1946 pour l’Armée Américaine :

Figure 1.4. Figure 4 : L’ENIAC

Figure 4 : L’ENIAC

  • 18 000 tubes à vide

  • 70 000 résistances

  • 10 000 capacités

  • 6 000 commutateurs manuels (pour programmer la machine)

  • Dimensions : 24 m de long, 6,25 m de large et 2,5 m de haut

  • Poids : 30 tonnes

  • Consommation électrique : 150kW

Cette machine fut construite par Presper ECKERT et John MAUCHLY de l'Université de Pennsylvanie sous la direction de Herman GOLDSTINE de la BRL.

Le mathématicien John VON NEUMANN un peu plus tard fit alors une critique structurelle de l’ENIAC ce qui aboutit à la construction de l’EDVAC (Electronic Discrete Variable Automatic Computer), basée sur une nouvelle architecture, connue comme étant l’architecture de VON NEUMANN.

Figure 1.5. Figure 5 : (de gauche à droite) Presper ECKERT, John MAUCHLY, Herman GOLDSTINE et John VON NEUMANN

Figure 5 : (de gauche à droite) Presper ECKERT, John MAUCHLY, Herman GOLDSTINE et John VON NEUMANN

LA DEUXIEME GENERATION DE MACHINE

L’invention du transistor, en 1947 par John BARDEEN (23 mai 1908 – 30 janvier 1991), William Bradford SHOCKLEY (13 février 1910 – 12 août 1989) et Walter Houser BRATTAIN (10 février 1902 – 13 octobre 1987), permet de construire des machines de deuxième génération plus petites, plus fiables et plus puissantes.

Ces trois ingénieurs des laboratoires Bell recevront le prix NOBEL de physique en 1956 pour leur découverte qui eut de très grandes conséquences.

Figure 1.6. Figure 6 : John BARDEEN, William SHOCKLEY, Walter BRATTAIN et le premier transistor

Figure 6 : John BARDEEN, William SHOCKLEY, Walter BRATTAIN et le premier transistor

Si nous comparons l’IBM 704, développée par Gene AMDAHL (16 novembre 1922 – 10 novembre 2015) en utilisant des tubes à vide et des triodes, avec son équivalent développé avec des transistors, l’IBM 7094, nous constatons que la puissance de calcul a été multipliée par un facteur 40. En effet, l’IBM 704 développait une puissance de 5kFLOPS alors que l’IBM 7094 culminait à 200 kFLOPS.

FLOPS: Floating-point Operations Per Second. Unité de mesure pour évaluer la puissance de calcul d’une machine basé sur le nombre d’opérations en une seconde, manipulant des nombres réels.

Figure 1.7. Figure 7 : L’IBM 704 (à gauche) et l’IBM 7094 (à droite)

Figure 7 : L’IBM 704 (à gauche) et l’IBM 7094 (à droite)

LA TROISIEME GENERATION DE MACHINE

L’invention du circuit intégré, ou nommée puce électronique (chip), en 1958 fut un nouveau saut technologique donnant la création et à la commercialisation des ordinateurs de troisième génération.

Figure 1.8. Figure 8 : La première puce de Jack KILBY

Figure 8 : La première puce de Jack KILBY

Découvert quasiment en même temps par Sir Jack SAINT CLAIR KILBY (8 novembre 1923 – 20 juin 2005) de la société Texas Instrument et Robert NOYCE (12 décembre 1927 – 3 juin 1990) de la société Fairchild Semiconductor, cela a donné lieu à une bataille judiciaire, dont la paternité de l’invention fut finalement fait à KILBY (cette découverte lui valut le prix NOBEL de physique en 2000).

Figure 1.9. Figure 9 : Jack KILBY (à gauche) et Robert NOYCE (à droite)

Figure 9 : Jack KILBY (à gauche) et Robert NOYCE (à droite)

Cette invention permettant de placer plusieurs transistors dans un même boîtier, elle permit de concevoir des machines encore plus petites et encore plus en plus puissantes. L’informatique commence alors à se démocratiser avec l’apparition des mini-ordinateurs (le PDP-1 (Programmed Data Processor) est commercialisé par la société DEC (Digital Equipment Corporation) vers 1960) qui permettent aux universités de se doter de moyens informatiques à des prix « raisonnables ».

Figure 1.10. Figure 10 : Le PDP-1 commercialisé par la société DEC

Figure 10 : Le PDP-1 commercialisé par la société DEC

LA QUATRIEME GENERATION DE MACHINE

En 1971, Dr. Marcian Ewdard HOFF dit Ted HOFF (28 octobre 1937 – …) de la start-up Intel met au point le premier microprocesseur, baptisé le 4004. Ce composant fonctionnait sur 4 bits et développait une puissance de 60000 instructions par seconde. La technologie de l’époque avait permis d’intégrer 2300 transistors au sein de la puce. Cette nouvelle avancée technologique permis l’avènement de la quatrième génération d’ordinateur : les micro-ordinateurs.

Figure 1.11. Figure 11 : Ted HOFF et le premier microprocesseur

Figure 11 : Ted HOFF et le premier microprocesseur

En 1973, le premier micro-ordinateur à être vendu fut le Micral, une machine construite en France par André TRUONG TRONG THI (30 janvier 1936 – 29 mars 2005) et François GERNELLE (20 décembre 1944 – …) pour répondre à une commande de l’institut INRA qui n’avait pas les moyens de s’acheter un PDP-8.

Figure 1.12. Figure 12 : André TRUONG TRONG THI, François GRENELLE et le Micral N

Figure 12 : André TRUONG TRONG THI, François GRENELLE et le Micral N

Dès lors l’informatique commence à s’inviter dans les foyers en tant qu’ordinateur domestique (Texas Instrument, Atari, Amiga, IBM PS2 …) mais également en tant que composants dans des machines du quotidien (lave-linge, cafetière programmable, magnétoscope, télévision …).

Figure 1.13. Figure 13 : Le TI 99/4A, l’Atari 2600, l’Amiga et l’IBM PS/2

Figure 13 : Le TI 99/4A, l’Atari 2600, l’Amiga et l’IBM PS/2

En 1976, Steve WOZNIAK construit l’Apple I et Steve JOBS propose de le commercialiser pour 666,66 $.

En 1977, création d’Apple Computer, Inc qui connaît des succès commerciaux avec l’Apple II et le macintosh.

En 1981, IBM commercialise le PC tout en rendant publique les spécifications de cette machine, ce qui permet le développement des clones et du marché des PC.

Le 28 octobre 2010, dans la course aux performances des supercalculateurs, la Chine a vraisemblablement détrôné, les Etats-Unis. Conçu par deux cents ingénieurs, le Tianhe-1A ("voix lactée") est un superordinateur hébergé au National Center for Supercomputing, dans la ville de Tianjin, dans le nord-est de la Chine. …. ».

En 2013, la Chine détient le plus gros calculateur avec le Tianhe-2.

NOUS ET LE NUMERIQUE

Alors que le numérique, en tant qu’outil de calcul (et de contrôle), s’est progressivement implanté dans notre quotidien, des éléments connexes sont également passé dans le monde du numérique. D’abord, les moyens de stockage de l’information sont naturellement devenus de plus en plus numériques.

Dès 1978, nous pouvons citer par exemple le LD (laser disc) avec un son en analogique et numérique.

Puis en 1980, le CD (Compact Disc), dont le standard est proposé par Philips et Sony.

Depuis le 17 août 1982, date où le premier CD fut gravé à Eindhoven (Pays-Bas). Le CD a supplanté peu à peu les cassettes audio et les disques vinyles.

Dès 1995, le LD et la cassette vidéo suivent la même destinée avec l’apparition du DVD (Digital Versatile Disc).

En Octobre 2000, nous avons les premiers prototypes de BD (Blu-ray Disk), dont le standard et breveté et commercialisé par Sony. Il faut attendre Avril 2003 pour avoir les premiers prototypes de lecteurs de BD.

En 2008, le HD DVD de Toshiba est arrêté dû à la trop forte concurrence du BD.

En fin 2009, la BDA (Blu-ray Disc Association) livre un standard BD 3D (Blu-ray 3D), pour visionner des films en trois dimensions.

Figure 1.14. Figure 14 : La surface du CD comporte des creux et des bosses pour stocker l’information

Figure 14 : La surface du CD comporte des creux et des bosses pour stocker l’information

Les moyens de transmission de l’information (et de communication en général) sont également touchés par cette vague numérique. A titre d’exemple, nous pouvons citer la téléphonie analogique classique qui est progressivement remplacée par la « voix sur IP » (Voice over IP ou VoIP) dans le cadre d’offres « triple-play » proposées par des fournisseurs d’accès à Internet ou dans le cadre d’utilisation de logiciels tels que Skype.

Figure 1.15. Figure 15 : Les offres triple-play

Figure 15 : Les offres triple-play

Nous pouvons évoquer l’arrivée (trop tardive en 2015) de la TNT (Télévision Numérique Terrestre) avec le tout TNT HD (Télévision Numérique Terrestre Haute Définition le 5 avril 2016) en France qui permet d’améliorer la qualité de transmission des programmes TV et d’élargir le panel de chaînes disponibles. Maintenant tout se décline au numérique, montre, téléphone, domotique, maison intelligente … mais attention à la pérennité des supports et des espaces de stockage. Il est dit que ces supports numériques ne sont pas éternels soit par un changement de norme soit tout simplement dû aux pannes irréversibles.

Le numérique s’implante :

  • Les prothèses auditives sont devenues des produits « relativement » courants et beaucoup de sociétés se sont créées autour de la commercialisation de ces prothèses.

  • Les prothèses biomécaniques permettent désormais d’améliorer la vie des personnes amputées d’un membre. Les avancés sont constantes et les réalisations nombreuses. En 2005, Jesse Sullivan et en 2006, Claudia MITCHELL sont munis de bras bioniques pour « remplacer » leurs membres perdus dans des accidents.

  • En Décembre 2013 et Août 2014, implantation des premiers cœurs artificiels.

Figure 1.16. Figure 16 : Le bras artificiel de Claudia MITCHELL

Figure 16 : Le bras artificiel de Claudia MITCHELL

LE MONDE TOUJOURS PLUS NUMERIQUE

Le numérique a son vocabulaire :

  • SSI (Small Scale Integration) : Technologie utilisée depuis l’invention du circuit intégrée, elle permet d’incorporer moins d’une centaine de transistors dans un boîtier.

  • MSI (Medium Scale Integration) : Technologie pour créer des circuits comportant plus de 3000 transistors vers le milieu des années 60.

  • LSI (Large Scale Integration) : Procédé utilisé dans les années 70 pour construire des composants comportant plusieurs dizaines de milliers de transistors.

  • VLSI (Very Large Scale Integration) : Technologie employée pour construire les composants pendant les années 1980 et 1990 en intégrant jusqu’à un million de transistors.

  • ULSI (Ultra Large Scale Integration) : Technologie employée depuis les années 2000 pour fabriquer les composants électroniques comme les microprocesseurs.

L’accroissement de la capacité à intégrer des transistors double tous les 18 mois, selon la loi établie empiriquement par Gordon Earl MOORE (3 janvier 1929 – …), l’un des co-fondateurs d’Intel. Selon ses prévisions, le phénomène devrait continuer pendant encore quelques années avec l’apparition de circuits de plus en plus petits, d’une taille de l’ordre du nanomètre : c’est l’avènement de la nanoélectronique. Mais encore pour combien de temps ?

Nano (grec nannos signifie nain) est un préfixe correspondant à 10–9. Un nanomètre correspond à un milliardième de mètre.

Figure 1.17. Figure 17 : Le doublement annuel de la capacité d’intégration selon Gordon Earl MOORE

Figure 17 : Le doublement annuel de la capacité d’intégration selon Gordon Earl MOORE

Cette nanoélectronique et plus généralement ces nanotechnologies en sont encore à leurs débuts , mais elles ouvrent de grandes perspectives :

  • Plus grande densité dans les moyens de stockage.

  • Possibilité de fabriquer des prothèses plus petites, mieux acceptée par le corps humain.

  • Diagnostiques plus précoces et guérison de maladies telles que le cancer. Le microscope à effet tunnel a été inventé en 1982 et le microscope à force atomique a été inventé en 1986, 2 instruments indispensables pour voir et manipuler des éléments de dimensions nanométriques.

  • Elaboration de matériaux plus résistants et plus légers comme les nanotubes

Parmi toutes ces perspectives, nous trouvons la fabrication de puces électroniques de dimension nanométriques toujours plus puissantes. A l’instar des sauts technologiques précédents, qui ont apporté des nouveaux moyens de calculs plus puissants, la généralisation des nanotechnologies engendre elle aussi l’apparition d’une nouvelle génération de machines ce qui entraînera l’apparition de nouveaux besoins dans le domaine du numérique.

Figure 1.18. Figure 18 : L'encyclopédie Britannica stocké sous forme de milliards de nano-perforations

Figure 18 : L'encyclopédie Britannica stocké sous forme de milliards de nano-perforations

Figure 1.19. Figure 19 : Ecriture de « Kanji » (atome) en assemblant des atomes de fer sur une surface de cuivre

Figure 19 : Ecriture de « Kanji » (atome) en assemblant des atomes de fer sur une surface de cuivre

LE BILAN DU NUMERIQUE

Pour tenter de dresser un état des lieux, nous allons essayer de lister les domaines où les technologiques numériques sont utilisées et celles où elles en sont absentes.

AVANTAGES ET INCONVENIANTS DU NUMERIQUE

Le monde numérique est créé par l’Homme où chaque élément qui le constitue ne connaît que deux états (le 0 et le 1). Il s’oppose au monde « naturelle » dont les éléments peuvent prendre une infinité d’état.

Nous évoluons dans ce monde naturel. Pour accéder à ce monde numérique, nous devons mettre en place des interfaces (au minimum deux : une allant du monde naturel vers le monde numérique pour introduire des informations dans ce monde numérique et une autre du monde numérique vers le monde naturel pour retirer des résultats.

La construction de ces interfaces obéissent à une théorie appelée théorie du signal que nous allons exposer brièvement dans la partie suivante.

Ce monde numérique doit être mis en relation avec ce monde naturel dans lequel nous évoluons afin que nous puissions l’utiliser. Ces connexions du monde numérique vers le monde naturel d’une part et du monde naturel vers le monde numérique nécessitent la mise en place de chaîne de traitements.

REPARTITION ENTRE LE NUMERIQUE ET LE NON NUMERIQUE

La fabrication de ce monde numérique s’appuie sur des transistors fonctionnant en mode commuté (ils se trouvent soit dans un état bloqué, soit dans un état passant, donc transposable en numérique par 0 ou 1) mais ces mêmes transistors peuvent aussi fonctionner en mode amplificateur et peuvent prendre une infinité d’états. Il est à noter qu’un monde en numérique constitué de 0 et 1 sera assimilé à un monde discret. Par conséquent, le monde naturel s’appuie sur des composants (les transistors) qui appartiennent au monde continu (monde réel humain) mais que nous faisons fonctionner en mode commuté pour créer un monde discret (monde artificiel numérique constitué de 0 et 1).

Figure 1.20. Figure 19 : Place du transistor

Figure 19 : Place du transistor

Nous considérons le transistor en mode commuté comme appartenant au monde discret. Nous allons étudier la répartition entre le monde numérique et le monde non-numérique en partant du microprocesseur de l’ordinateur.

Le microprocesseur possède naturellement un fonctionnement numérique. Il est implanté sur une carte mère qui comporte d’autres composants d’électroniques numérique comme la mémoire, les processeurs vidéo … Ces différents composants sont reliés par des bus où chaque élément peut prendre deux niveaux de tension pour transporter l’information.

Si nous nous éloignons du microprocesseur, nous tombons sur les moyens de stockage de masse comme le disque dur ou les CD ROM. Ces moyens de stockage se trouvent à la frontière entre les deux mondes. En effet, ces systèmes enregistrent des informations sous la forme de 0 et de 1, donc en monde discret, mais leur principe de fonctionnement sous-jacent appartient au monde continu. Dans le cas du disque dur, l’information est stockée à l’aide d’une bobine qui induit un champ électromagnétique pour orienter les bâtonnets de ferrites (monde continu), présent sur la surface des plateaux du disque dur dans un sens (pour représenter le 0, monde discret) ou dans l’autre (pour représenter le 1, monde discret).

Dans le cas du CD ROM, nous nous éloignons encore du processeur pour sortir du boitier du PC (Personal Computer). Là, nous devons mettre en place des interfaces pour permettre à l’Homme de communiquer avec la machine. D’autres interfaces pour permettre à la machine de capter des infos sur le monde externe.

Vient enfin tous les éléments électriques totalement déconnectés de l’informatique qui ont un fonctionnement naturellement non-numérique.

La mesure de données physiques externes :

  • Les capteurs de températures.

  • Les capteurs de pression (basés sur des cristaux aux des propriétés piézoélectriques).

  • Les microphones (déplacements d’air qui font bouger une membrane solidaire d’un aimant dans le micro).

  • Les capteurs de lumières (capteurs CCD des appareils photo numériques).

  • …etc.

Figure 1.21. Figure 20 : Exemple de fil et connecteurs

Figure 20 : Exemple de fil et connecteurs

L’électronique de puissance :

  • L’alimentation et le contrôle des moteurs.

  • L’alimentation et le contrôle des électrovannes.

  • Les transformateurs.

  • Les amplificateurs.

  • … etc.

La restitution des informations :

  • Les écrans à tube cathodique.

  • Les haut-parleurs.

  • … etc.

La transmission des signaux à longue distance par modulation-démodulation :

  • Signaux électriques dans les câbles.

  • Signaux lumineux dans les fibres optiques.

  • Signaux hertziens dans l’air et dans l’espace.

  • … etc.

LA MISE EN OEUVRE DU NUMERIQUE

Nous devons passer d’un monde continu vers un monde discret et inversement d’un monde discret vers un monde continu sans perdre d’informations, ou en limitant la perte en estimant les erreurs. Donc en plus des données présentes, il faut les datées. Nous pouvons faire de l’instantané par datation de fichiers ou faire évoluer la donnée par fonctions temporelles. Ces considérations sont à prendre en compte si nous voulons être précis.

QU'EST-CE QUE LE TEMPS ?

Le temps est une notion qui a probablement été introduite par l’Homme après avoir observé des phénomènes naturels comme l’alternance du jour et de la nuit, la course du soleil dans le ciel … La « définition du temps » a beaucoup varié selon les époques et les cultures. Par exemple, dans l’hindouisme et le bouddhisme, le temps s’écoule de façon cyclique (de l’Age d’Or jusqu’à l’Apocalypse où l’humanité corrompue est quasiment détruite pour renaître dans un nouvel Age d’Or) alors que dans le judaïsme, le christianisme et l’islam, le temps s’écoule de façon linéaire (de la Genèse au Jugement Dernier).

Figure 1.22. Figure 21 : Deux conceptions du temps

Figure 21 : Deux conceptions du temps

[Note]

La « définition du temps » est également liée au progrès scientifiques :

  • Les techniques, mises en œuvre pour mesurer l’écoulement de ce temps, nous permettent de dater les événements de façon de plus en plus précise (cadrans solaires, clepsydres, sabliers … jusqu’aux horloges atomiques).

  • La régularité dans l’écoulement du temps a été bouleversée par la théorie de la Relativité énoncée par Einstein (le temps s’écoule plus lentement à l’intérieur d’un mobile en mouvement qu’à l’extérieur).

Figure 1.23. Figure 22 : Différents appareils de mesure du temps

Figure 22 : Différents appareils de mesure du temps

Selon la citation de Saint-Augustin, nous sommes finalement impuissants à formuler une « définition du temps » correcte.

[ Saint Augustin, Confessions, XI, 14, 17 : « Qu'est-ce que en effet que le temps ? Qui saurait en donner avec aisance et brièveté une explication ? ... Si personne ne me pose la question, je le sais ; si quelqu'un pose la question et que je veuille expliquer, je ne sais plus. » ]

Pour Pascal, cette définition est d’ailleurs inutile car c’est une tautologie qui implique l’existence du temps (le temps fait partie des notions fondamentales qu’il est inutile de définir).

Cependant, beaucoup de philosophes s’accordent sur l’aspect continu du temps.

[ Henri Bergson, La Perception du Changement : « C'est justement cette continuité indivisible de changement qui constitue la durée vraie. […] la durée réelle est ce que l'on a toujours appelé le temps, mais le temps perçu comme indivisible. Que le temps implique la succession, je n'en disconviens pas. Mais que la succession se présente d'abord à notre conscience comme la distinction d'un « avant » et d'un « après » juxtaposés, c'est ce que je ne saurais accorder. » ]

A notre niveau, si nous observons le fonctionnement des appareils de mesure de la figure 22, nous constatons que le temps évolue de façon continue. Nous ne passons pas directement de 12h à 13h mais nous subdivisons et passons par des intermédiaires : la minute, la seconde, le dixième de seconde, le centième de seconde …

Cette continuité est difficile à appréhender d’un point de vue intellectuel : nous avons plutôt l’habitude de manipuler des données avec une précision en rapport avec leur utilisation. La plupart du temps, une précision de l’ordre de la minute est suffisante mais des activités comme le chronométrage sportif requièrent des précisions de l’ordre du centième de seconde.

Cette continuité est également impossible à gérer d’un point de vue technique : les appareils de mesure ont une précision limitée, les moyens de stockage des informations sont limités …

La continuité étant impossible à gérer et inutile, nous nous contentons de manipuler des dates précises ce qui implique que le temps soit discrétisé.

LE TEMPS EN QUELQUES DEFINITIONS

Après cette présentation philosophique de la notion du temps, nous abordons une présentation plus formelle en proposant 3 définitions.

[Note]

Le temps continu :

Si nous notons t, une date marquée sur l’échelle du temps, nous avons : t ∈ R. Autrement dit, l’échelle du temps est assimilable à l’ensemble des réels.

[Note]

Le temps discret :

Par opposition au temps continu, nous définissons un temps discret où l’échelle du temps n’est constituée que de dates réelles isolées t0, t1 … ti telles que n ∈ N et tn ∈ R.

[Note]

La période :

Si les dates t0, t1 … ti définissent une suite arithmétique, nous avons la relation : ti = t0 + T × i avec T ∈ R. T est la raison de cette suite et elle correspond également à la période.

LE TEMPS VECTEUR DE VARIATIONS

Etant capables de mesurer le temps et de dater des événements, nous pouvons maintenant suivre l’évolution d’une quantité physique (température, volume, pression …) au cours du temps. La quantité physique est alors vue comme une fonction du temps et elle est appelée signal.

Comme nous avons défini deux types de temps, nous pouvons définir deux types de signaux :

  • Les signaux en temps continu.

  • Les signaux en temps discret.

Concernant la seconde catégorie, nous distinguons le cas particulier où le temps est discrétisé de façon périodique (les mesures physiques sont effectuées à intervalles réguliers), nous parlons alors de signal échantillonné.

LES SIGNAUX EN QUELQUES DEFINITIONS

Comme précédemment, nous proposons 4 définitions afin de formaliser les propos de la partie précédente.

[Note]

Le signal :

Un signal est une fonction s qui associe une quantité physique (température, volume, pression…) à une date t. La quantité physique est une grandeur réelle.

[Note]

Le signal en temps continu :

Un signal s en temps continu est tel que la date t ∈ R. Nous avons :

s : R → R

t → s(t)

[Note]

Le signal en temps discret :

Un signal s en temps discret est tel que la date t appartient à un ensemble de réels isolés. Nous avons :

s : {t0, t1 … tn} → N

t → s(t)

[Note]

Le signal échantillonné :

Si les dates t0, t1 … tn forment une suite arithmétique de raison T, nous disons alors que le signal est échantillonné avec une période T. Nous avons :

s : N → R

n → s(t0+nT)

LA QUANTIFICATION ET L'INTERPOLATION

La quantité physique évolue de façon continue. Pour des raisons pratiques, nous manipulons des signaux en temps discrets voire des signaux échantillonnés. Cependant, la valeur des différentes mesures appartiennent à l’ensemble des réels : la quantité physique est donc une donnée continue.

Les instruments de mesure ne permettent pas de capter des valeurs avec une précision infinie. Les quantités physiques sont mesurées avec une précision moindre mais jugées acceptables au regard de l’utilisation qui en est faite.

Les valeurs vraies sont approximées par des valeurs quantifiées. Comme plusieurs valeurs vraies peuvent être représentées par la même valeur quantifiée, cette transformation (cette injection) provoque une perte d’information (le signal perd de sa qualité). L’ensemble de ces mesures approchées forme alors une donnée discrète.

Figure 1.24. Figure 23 : Le processus de quantification

Figure 23 : Le processus de quantification

Lorsque les informations sont traitées, il est parfois nécessaire de reconstruire des données manquantes à partir des données dont nous disposons. Par exemple, certains scanners proposent une résolution de 2400 dpi alors que leurs capteurs ne leurs permettent d’obtenir qu’une résolution de 600 dpi : l’application d’acquisition d’images est donc amenée à « reconstruire » les données manquantes (les pixels manquants).

Ce processus est appelé interpolation. Elle consiste le plus souvent à tirer des traits entre des points connus et à placer des points supplémentaires sur ces traits : nous parlons alors d’interpolation linéaire.

Il existe d’autres types d’interpolations :

  • Lorsque nous remplaçons 3 traits par des courbes définies des équations du 3ème degré (spline) nous faisons une interpolation cubique.

  • Lorsque nous remplaçons l’ensemble de traits par une courbe définie par des polynômes (souvent de degré supérieur à 3), nous faisons une interpolation polynomiale.

Figure 1.25. Figure 24 : Un exemple d’interpolation linéaire

Figure 24 : Un exemple d’interpolation linéaire

Figure 1.26. Figure25 : Un exemple d’interpolation cubique (remplacement des 3 premiers traits)

Figure25 : Un exemple d’interpolation cubique (remplacement des 3 premiers traits)

L’ensemble de ces notions peut être résumé par :

Figure 1.27. Figure26 : de continu à discret et inversement

Figure26 : de continu à discret et inversement

DEFINITIONS

Nous proposons ci-dessous 4 définitions afin de décrire de façon plus formelle les notions présentées dans la partie précédente.

[Note]

La donnée continue :

Une donnée continue (une date, une température, un volume …) est une information ayant une valeur appartenant à l’ensemble R.

[Note]

La donnée discrète :

Une donnée discrète (une date, une température, un volume …) est une information ayant une valeur appartenant à un ensemble contenant des valeurs isolées de R.

[Note]

La quantification :

La quantification est le processus qui vise à associer une représentation numérique (sous forme de données discrètes) à une grandeur physique (sous forme de données continues). D’un point de vue formel, il s’agit d’une injection car plusieurs données continues peuvent être représentées par la même donnée discrète.

[Note]

L’interpolation :

C’est le processus qui vise à construire une donnée continue en créant les informations manquantes à partir de quelques données discrètes. Pour cela, des valeurs cohérentes sont construites entre deux valeurs discrètes ou à la suite de ces valeurs.

EN PRATIQUE

MISE EN OEUVRE ELECTRONIQUE

En complément de ces notions théoriques, rattachée à la théorie du signal, nous devons introduire d’autres termes qui sont utilisés dans le domaine de l’électronique.

En électronique, nous avons l’habitude d’utiliser d’autres termes :

  • Un signal analogique est un signal de nature électrique qui peut prendre théoriquement une infinité de valeur.

  • Un signal numérique est un signal de nature électrique qui ne peut prendre que des valeurs prédéterminées.

  • CAN (ADC) est l’acronyme de « Convertisseur Analogique Numérique », il s’agit d’un boîtier qui effectue la quantification d’un signal analogique. Le résultat est une valeur numérique.

  • CNA (DAC) est l’acronyme de « Convertisseur Numérique Analogique », il s’agit d’un autre boîtier qui transforme une suite de valeurs numériques en un signal analogique.

[Note]

La transduction :

C’est le processus qui vise à transformer un signal électrique en un signal d’une autre nature (luminosité sur un écran, rotation d’un moteur …) ou l’inverse.

PASSAGE DU CONTINU AU DISCRET

Nous allons décrire l’acquisition par un ordinateur d’une mesure physique telle que la température. Pour obtenir cette donnée sous une forme numérique exploitable, il est nécessaire d’effectuer (d’enchaîner) un certain nombre de traitements. La température est une donnée continue qui évolue en temps continu. Pour être traité ou enregistré, ce signal doit passer par plusieurs blocs pour être transformé en un signal numérique exploitable. Il faut utiliser un capteur basé sur une résistance variant en fonction de la température. La variation continue de température se traduit par une variation continue de la tension. La variation de tension a potentiellement une largeur de bande infinie et elle est imparfaite (bruitée). L’utilisation d’un filtre permet de limiter la largeur du signal et diminue le bruit. Nous regardons de façon périodique l’état du signal (T étant la période d’échantillonnage) : nous ne gardons donc que le signal qu’à certains instants t0+nT et nous supprimons le reste. Pour des raisons électriques, le CAN ne peut pas traiter directement le signal échantillonné (le signal n’a une valeur que pendant un court instant). Nous bloquons la valeur du signal à chaque période. Pour chaque instant t0+nT, nous arrondissons la valeur du signal à des valeurs quantifiées. Il y a une perte de précision acceptable au vue du traitement à effectuer. Nous enregistrons, dans une mémoire, la valeur quantifiée du signal à chaque instant t0+nT pour effectuer un traitement ultérieur.

Figure 1.28. Figure 27 : Etape du passage du continu au discret

Figure 27 : Etape du passage du continu au discret

PASSAGE DU DISCRET AU CONTINU

Lorsque l’ordinateur traite une donnée cela induit généralement une action en sortie (un affichage à l’écran, un son sur le haut-parleur, l’actionnement d’un moteur …). Pour accomplir cette action, nous devons repasser du monde numérique (discret) de l’ordinateur vers le monde externe qui est continu. Nous allons prendre l’exemple d’un morceau musical qui a été numérisé. Ce morceau est présent en mémoire sous la forme de nombre qui symbolisent des niveaux d’énergie des différentes fréquences au cours du temps. Nous allons faire en sorte que ce morceau soit joué, autrement dit qu’il provoque des vibrations aux niveaux de nos tympans. Il faut convertir le signal numérique en un signal analogique (une tension) qui va provoquer le son. Nous disposons d’un ensemble de données discrètes issues d’un traitement numérique. Nous reconstruisons une courbe continue en interpolant (en reliant) ces points. Le signal interpolé n’est pas "lisse" ce qui peut provoquer quelques problèmes d’un point de vue électrique. Nous lissons le signal en le faisant passer dans un filtre. Le signal filtré a généralement une faible puissance (petite tension et petite intensité). Nous construisons une copie amplifiée du signal filtré. Le passage du signal par un bloc de traitement introduit toujours des erreurs : le rendu n’est donc pas fidèle à l’information enregistrée. Il est donc souvent nécessaire d’étalonner les appareils. Le capteur assure la traduction d’un signal physique en un signal électrique par une fonction de transfert qui lui est propre. Cette dernière n’est pas nécessairement linéaire et est associée à un domaine d’utilisation précis (gamme de température, de mesure …). Lorsque nous échantillonnons, nous supprimons de l’information. La fréquence d’échantillonnage est un compromis entre la quantité de données à traiter et la conservation de « l’allure du signal » : c’est l’erreur d’échantillonnage, phénomène étudié par Harry Nyquist et Claude Shannon. Si le signal physique est périodique alors, il faut une période d’échantillonnage au moins deux fois plus petite pour conserver l’allure du signal. Le CAN introduit par construction une erreur puisqu’il vise à approximer un signal : c’est l’erreur de quantification. Le CAN est caractérisé par un pas de quantification. Les ordinateurs peuvent commettre des erreurs d’arrondis qui sont dues à leur manière de coder et de traiter les nombres. A l’instar du CAN, le CNA introduit également une erreur car il reconstruit de manière approximative un signal continu à partir de données discrètes : nous parlons alors d’erreurs de linéarité. A l’instar du capteur, le transducteur traduit un signal électrique en un signal physique selon une courbe de transfert qui n’est pas parfaite (pas linéaire).

Figure 1.29. Figure 28 : Etape du passage du continu au discret

Figure 28 : Etape du passage du continu au discret

LE CODAGE DES INFORMATIONS NUMERIQUES - LE MONDE BINAIRE

Ce chapitre a pour objectif de présenter la manière de représenter les informations à l’intérieur de l’ordinateur.

Figure 1.30. Figure 29 : Place du numérique

Figure 29 : Place du numérique

Figure 1.31. Figure 30 : Les données informatiques

Figure 30 : Les données informatiques

Dans cette partie, le codage des informations numériques s’appuie sur les nombres binaires car les nombres 0 et 1 peuvent facilement être transcris d’un point de vue électrique comme la présence ou l’absence d’un courant, la présence ou l’absence d’une tension. Et comme les ordinateurs (et autres appareils diffuseur d’information) sont constitués de circuits électriques, la transposition est des plus simple.

Ce chapitre est consacré au codage des nombres entiers (décimaux), positifs et négatifs, en nombre entiers binaires (en base 2). Elle présente également l’arithmétique propre à cette base (comme additionner deux nombres binaires, de quelle manière multiplions-nous deux nombres binaires, ….). Avant d’aborder le thème des nombres binaires, nous allons effectuer un rappel historique des faits qui ont amené Gottfried Wilhelm LEIBNIZ a énoncé sa théorie. Une fois ce rappel effectue, nous traitons du codage des entiers et de l’arithmétique binaire.

LES TRIGRAMMES

Fu Shi (Fuxi) est un personnage de la mythologie chinoise. Il s’agirait du premier empereur chinois qui aurait gouverné il y a 5000 avant Jésus-Christ (il faisait partie de la dynastie des 3 Augustes).

Figure 1.32. Figure 31 : L’empereur Fu Shi montrant les 8 trigrammes dans l’ordre du ciel antérieur

Figure 31 : L’empereur Fu Shi montrant les 8 trigrammes dans l’ordre du ciel antérieur

Selon une légende, ce souverain aurait aperçu une tortue qui sortait du fleuve Lo et dont les dessins de la carapace lui auraient inspiré les 8 trigrammes. Ces dessins sont la première étape dans la rédaction du « Yi King » ou « Livre des mutations », un ouvrage de divination orientale . Ces 8 trigrammes sont disposés dans un bāguà (un diagramme octogonal) selon un ordre appelé « ordre du ciel antérieur ».

Figure 1.33. Figure 32 : Les 8 trigrammes dans l’ordre du ciel antérieur

Figure 32 : Les 8 trigrammes dans l’ordre du ciel antérieur

Un peu avant l’an -1000 avant Jésus Christ, le duc Wen aurait été fait prisonnier par le roi Di Xin (encore appelé Zhou Wang, le dernier roi de la dynastie Shang). Di Xin fut renversé et le fils du duc Wen, qui devint roi, fonda alors le dynaste Zhou (qui allait régner pendant un millénaire sur la Chine). Le duc Wen fut alors élevé au rang de roi à titre posthume.

Figure 1.34. Figure 33 : Le roi Wen

Figure 33 : Le roi Wen

Pendant sa captivité, il aurait imaginé une disposition des trigrammes dans un autre ordre, appelé l’ordre du ciel postérieur. L’énigme concernant le lien entre ces deux séquences aurait été résolue beaucoup plus tard par un moine tibétain qui l’a transcrit de la manière suivante :

[« Le roi se rend au nord-ouest. La reine se rend au sud-ouest. Le nouveau sud va au nord-est. Le nouveau nord va au sud-est. Les axes de la crois finale échangent leurs positions. »]

Figure 1.35. Figure 34 : Les 8 trigrammes dans l’ordre du ciel postérieur

Figure 34 : Les 8 trigrammes dans l’ordre du ciel postérieur

La création des 64 hexagrammes serait également attribuée au roi Wen. Il s’agirait de la combinaison de deux trigrammes, l’un placé au-dessus de l’autre.

Figure 1.36. Figure 35 : Les 64 hexagrammes

Figure 35 : Les 64 hexagrammes

L'APHABET BILITERE DE FRANCIS BACON

Francis BACON est né à Londres en 1561. Il étudia à l’université de Cambridge avant de devenir avocat et de s’intéresser à la jurisprudence. Il entama ensuite une carrière politique qui lui permit d’être nommé garde des sceaux et grand chancelier. Ayant de nombreux ennemis, il tomba en disgrâce pour une affaire de corruption. Il consacra alors les dernières années de sa vie à la physique et à la philosophie avant de mourir en 1926 . Nous lui devons quelques citations restées célèbres.

[ « Natura enim non nisi parendo vincitur. » : On ne commande à la nature qu’en lui obéissant. ]

[ « Scientia et potentia humana in idem coincidunt, quia ignoratio causæ destituit effectum » dans Novum Organum en 1620, « Nam et ipsa scientia potestas est. » dans Meditationes Sacrae, De Haeresibus en 1957 : Savoir c’est pouvoir ou En effet le savoir lui-même est pouvoir. ]

Figure 1.37. Figure36 : Francis BACON

Figure36 : Francis BACON

Francis BACON est également connu pour avoir créé un système sténographique permettant de chiffrer les messages diplomatiques, lors de son séjour en France, de 1576 à 1578, auprès de l’ambassadeur de la reine Elizabeth .

Ce système fut appelé par son auteur, l’alphabet bilitère et il fut décrit dans un article intitulé « De augmentis Scientiarum » et paru en 1623.

Ce système consistait à utiliser deux écritures légèrement différentes pour cacher des messages secrets dans des textes d’apparence anodine (le message de couverture). Nous appelons ces deux formes d’écriture les polices de caractères α et β.

Pour coder son message, Francis BACON associe d’abord à chaque lettre de l’alphabet un quintuplet de symboles α et β. Cela signifie qu’une lettre du message secret est codée avec 5 lettres dans le message de couverture.

Figure 1.38. Figure 37 : La correspondance entre les lettres et le quintuplet de symboles

Figure 37 : La correspondance entre les lettres et le quintuplet de symboles

Une fois que la correspondance entre les lettres et le code est établi, il reste à trouver un texte de couverture comportant 5 fois plus de caractères pour cacher le texte secret.

Si le texte secret est « Fuyez » et le texte de couverture est « Ne partez surtout pas sans moi », le codage et le décodage s’effectuent comme indiqué dans les schémas ci-dessous.

Figure 1.39. Figure 38 : Le processus de codage

Figure 38 : Le processus de codage

Figure 1.40. Figure 39 : Le processus de décodage

Figure 39 : Le processus de décodage

L'ALGEBRE BINAIRE DE GOTTFRIED WILHELM LEIBNIZ

Gottfried Wilhelm LEIBNIZ est né le 1er juillet 1646 à Leipzig (Allemagne). Orphelin de sa mère à 6 ans, il est élevé par son père qui est professeur de philosophie. Il décroche un baccalauréat de philosophie puis un doctorat en droit. A l’occasion d’une mission diplomatique en France, il rencontre divers savants de l’époque. A son retour, il est nommé bibliothécaire à Hanovre, ce qui lui permet de se consacrer à ses travaux dans les domaines des mathématiques, de la philosophie, de la physique et de la religion. Reconnu comme un grand intellectuel en Europe, il meurt à Hanovre le 14 novembre 1716.

Figure 1.41. Figure 40 : Gottfried Wilhelm LEIBNIZ

Figure 40 : Gottfried Wilhelm LEIBNIZ

Les apports de LEIBNIZ pour la physique et les mathématiques sont très importants pour l’époque. Nous lui devons notamment la construction d’une machine à calculer capable d’effectuer la multiplication. La conception de cette machine s’inspire vraisemblablement d’une autre machine de l’époque, la Pascaline de Blaise Pascal, qui ne permettait d’effectuer que les additions.

Figure 1.42. Figure 41 : La machine à calculer de LEIBNIZ, la seule capable d’effectuer des multiplications

Figure 41 : La machine à calculer de LEIBNIZ, la seule capable d’effectuer des multiplications

Gottfried Wilhelm LEIBNIZ est également à l’origine de l’étude formelle des nombres binaires. Il s’intéresse très tôt à la logique et cherchera toute sa vie à définir un langage symbolique, et dès 1666, à 20 ans il publie un document sur le sujet, « Dissertatio de arte combinatoria ».

Ayant étudié les œuvres de ses prédécesseurs (René DESCARTES, Francis BACON, GALILE …), nous pouvons supposer qu’il ait pris connaissance de l’article intitulé « De augmentis Scientiarum » où Francis BACON décrit les principes de son alphabet bilitère. Cet article aurait suscité chez LEIBNIZ les premiers travaux concernant les nombres binaires qui ont été consignés dans un écrit intitulé « De progressione dyadica » (de la progression par deux) en 1679.

Cependant, il semblerait l’intérêt du philosophe allemand pour les nombres binaires soit davantage due à sa correspondance avec le père Joachim Bouvet. En effet, à cette époque, LEIBNIZ était fasciné par la Chine et a consacré beaucoup d’écrits à ce sujet. Sa réflexion le fait militer pour un échange culturel entre l’Europe et la Chine et il écrit en 1697 un traité en ce sens (Novissima Sinica).

Le père Joachim BOUVET fait partie d’un groupe de 6 jésuites envoyés par Louis XIV en Chine en 1688. La mission de ces « mathématiciens du roi » était d’effectuer des mesures géodésiques pour cartographier l’empire chinois et, sous couvert de cette activité, de propager la foi chrétienne.

Figure 1.43. Figure 42 : Les missions chinoises des jésuites

Figure 42 : Les missions chinoises des jésuites

A son retour de Chine, BOUVET prend connaissance du traité Novissima Sinica. Il adresse une lettre à LEIBNIZ dans laquelle il décrit le Yi king et plus particulièrement les trigrammes et les hexagrammes. LEIBNIZ reconnaît dans ces formes la progression des entiers naturels en numération binaire.

Figure 1.44. Figure 43 : La correspondance entre les trigrammes chinois et les nombres binaires

Figure 43 : La correspondance entre les trigrammes chinois et les nombres binaires

LEIBNIZ continue ses travaux afin de mettre au jour les méthodes pour effectuer des opérations en base 2 ce qui donne lieu à la rédaction d’un article intitulé « Explication de l'arithmétique binaire (1703). Il expose ses travaux devant l’académie des sciences de Paris.

Figure 1.45. Figure 44 : Les opérations en base 2

Figure 44 : Les opérations en base 2

Fier de sa découverte, il demande à son protecteur de l’époque, de frapper une médaille illustrant cette découverte.

[Il y fait graver la devise : « Iner hat talles aus nichts gemacht » qui se traduit par « Tout est créé à partir de l’unité (1, Dieu) et du néant (0) » .]

Figure 1.46. Figure 45 : La médaille illustrant les travaux de LEIBNIZ

Figure 45 : La médaille illustrant les travaux de LEIBNIZ

POURQUOI LE BINAIRE ?

En informatique, nous manipulons des mots mémoires. Ces mots sont numériques, ils représentent le codage de l’information (nos programmes) et ils sont constitués, pour le moment, uniquement de 1 et de 0. Tous les organes d’un ordinateur sont conçus pour utiliser, manipuler, véhiculer, calculer des mots binaires. Le regroupement de 8 chiffres binaires est nommé octet (Byte). Plus précisément, un octet, c’est 8 bits et un bit signifie binary digit c’est-à-dire 0 ou 1 (deux états possibles pour un bit).

Table 1.1. Figure 46 : Un octet = One Byte, table de 8 cases

0 1 0 1 1 1 0 1

Dans un nombre binaire, la valeur d’un bit est appelée poids. Le nom du poids dépend de son positionnement dans le nombre. Par convention dans ce cours, les bits de gauche dans le nombre seront appelés, bits de poids fort, ceux de droite, bits de poids faible.

Table 1.2. Figure 47 : Bit de poids fort (à gauche), bit de poids faible (à droite)

0 1

Table 1.3. Figure 48 : Bits de poids fort (à gauche), bits de poids faible (à droite)

0 0 0 0 1 1 1 1

Il est à noter également que les opérations binaires seront utiles pour construire et comprendre les réseaux informatiques.

DU BINAIRE ENTIER POSITIF VERS LE DECIMAL ENTIER POSITIF

Figure 1.47. Figure 49 : Les données informatiques

Figure 49 : Les données informatiques

Comme nous l’avons évoqué dans la partie précédente, nous avons le monde discret, nos binaires maintenant et le monde continue, prenons par exemple les nombres décimaux.

Pour que la machine puisse manipuler rapidement les nombres décimaux sans perdre de précision ni de valeur, elle doit les traduire sous le format binaire. Pour cela nous appliquons différents algorithmes pour faire le passage d’un monde à l’autre et inversement.

[Note]

Note : Comme nous allons travailler dans deux bases différentes, nous devons différencier les valeurs en lecteur en fonction de la base. C’est pour cela que nous allons indicer toutes nos valeurs pour indiquer la base. Ainsi, par exemple, la valeur 10 en base 10 sera écrite 1010 et la valeur 10 en base 2 sera écrite 102

ALGORITHME DE LA TABLE DE CONVERSION

[Note]

Nom de l’algorithme : Table de conversion d’un nombre entier binaire en un nombre entier décimal

Donnée d’entrée : B un nombre entier binaire quelconque

Donnée produite : N un nombre entier décimal

But : Traduction numérique du nombre binaire B en une valeur N entière.

D’abord faisons la méthode de la conversion d’un entier décimal positif vers un binaire positif, grâce à une table de correspondance. Pour manipuler cet algorithme, il est plus simple de passer par la structure de données qui est une table et de dérouler les correspondances.

Les tables que nous allons prendre se lisent de droite à gauche. Donc l’indice de droite est 0 puis 1 puis 2 …. . Il est important de travailler avec les indices puisqu’ils vont déterminer les valeurs de correspondances.

Voici une table des indices sur 5 cases :

Table 1.4. Figure 50 : Table des valeurs des indices

4 3 2 1 0

La base binaire en entier décimpal est 2. Cela indique que nous pouvons avoir deux valeurs possibles 02 ou 12 mais aussi de calculer la correspondance entre binaire et décimal entier et ce en fonction des indices. Entre la base 2 et les indices, nous fabriquons des puissances de 2 pour faire notre transformation d’une base à l’autre.

Table 1.5. Figure 51 : Table de la base 2 à la puissance des indices

24 23 22 21 20

Effectivement, maintenant que nous avons établi les puissances, nous pouvons les transformer en entiers décimaux :

Table 1.6. Figure 52 : Table des valeurs des entiers décimaux, valeurs calculées en fonction des puissances de la base 2

16 8 4 2 1

La table de correspondance entre le mot binaire et la production de l’entier peut donc se faire :

Table 1.7. Figure 53 : Algorithme et résultat décimal en utilisant la table de conversion

Mot Binaire 1 1 1 0 1
Opérateur * * * * *
Valeur décimale 16 8 4 2 1
Résultat 16 8 4 0 1
29 16 + 8 + 4 + 0 + 1

La taille des mots que nous utilisons n’est pas importante pour le moment. Comme nous manipulons des valeurs entières positives, nous pouvons utiliser l’intégralité des cases. Les zéros du début des mots binaires ne sont pas significatifs. Inutile de compléter au début des mots binaires une suite de zéros.

Le seul zéro significatif est le mot d’une case :

Table 1.8. Figure 54 : Algorithme et résultat décimal en utilisant la table de conversion pour la plus petite valeur positive

Plus petit mot binaire positif 0
Opérateur *
Valeur décimale du plus petit mot 1 = 20
Résultat 0

[Note]

: Nous verrons ensuite que la taille des mots a une réelle importance dès que nous manipulerons des mots négatifs et positifs.

ALGORITHME DU POLYNOME

[Note]

Nom de l’algorithme : Construction d’un polynôme

Donnée d’entrée : B un nombre entier binaire quelconque

Donnée produite : N un nombre entier décimal

But : Traduction du nombre binaire B en une valeur décimale N.

En base 10, l’algorithme utiliser pour écrire un nombre N de la forme abc10 est :

N = a * 100 + b * 10 + c * 1

N = a * 102 + b * 101 + c * 100

Nous procédons de la même méthode algorithmique pour un binaire B de la forme abc2 :

B = a * 22 + b * 21 + c * 20

Par exemple, si nous voulons passer d’un nombre binaire B = 10012 à vers un décimal nous avons :

Partons du polynôme :

B = a * 23 + b * 22 + c * 21 + c * 20

Appliquons les valeurs de B= 10012 :

B = 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20

Evaluons les puissances de 2 :

B = 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1

Additionnons les différents monômes :

B = 910

DU DECIMAL ENTIER POSITIF VERS LE BINAIRE ENTIER POSITIF

Nous poursuivons notre étude des algorithmes en faisant le passage des nombre décimaux vers des nombres binaires.

METHODE DES DIVISIONS SUCCESSIVES PAR DEUX

[Note]

Nom de l’algorithme : Division par 2

Donnée d’entrée : N un nombre entier décimal quelconque

Donnée produite : B un nombre entier binaire

But : Traduction du nombre entier N en un nombre binaire.

Le principe de l’algorithme par division est positionné sur la construction du polynôme du nombre B, en partant d’un nombre décimal N.

Nous savons que pour un nombre B = abc2, nous avons B = a * 22 + b * 21 + c * 20. Prenons le cas général de B = abc2 en fonction des indices de B, nous : B = v2 * 22 + v1 * 21 + v0 * 20, pour a = v2, b = v1, c = v0. Généralisons pour un nombre B quelconque, nous avons : B = vn * 2n + vn-1 * 2n-1 + … + v0 * 20. B représente bien N dans le cas précédent. L’algorithme par division va reproduire se résultat.

Une fois les conditions posées, nous pouvons appliquer l’algorithme de la division par 2 :

  • Si nous divisons le nombre décimal N par 2, nous avons :

    • Un reste correspond à v0

    • Un quotient qui devient B1 (ce B1 devient le nouveau nombre binaire à diviser par 2)

  • La fin de l’algorithme de la division par 2 est lorsque le binaire produit par la division vaut 1 ou 0.

  • Après la fin de la division, il y a une reconstitution du nombre binaire produit en lisant et concaténant les restes dans l’ordre inverse de leur fabrication. Ainsi le dernier reste produit devient le bit de poids fort et le premier bit produit devient le bit de poids faible.

Exemple pour trouver le binaire B à partir du nombre N = 1610

Figure 1.48. Figure 55 : Mise en œuvre graphique d’un déroulement de l’algorithme par division

Figure 55 : Mise en œuvre graphique d’un déroulement de l’algorithme par division

A partir de la figure 55, le nombre binaire B est le résultat de la lecture des restes (chiffre rouge) : B = 100002. Le dernier 1 produit en reste devient le bit de poids fort du nombre B binaire et la lecture se fait de droite à gauche en fonction des restes.

ALGORITHME DE CONVERSION D'UN NOMBRE DECIMAL ENTIER EN UN NOMBRE BINAIRE ENTIER

[Note]

Nom de l’algorithme : Conversion d’un nombre Décimal entier en un nombre Binaire

Donnée d’entrée : N un nombre entier décimal quelconque (Il est à noter qu’un mMax peut être donné)

Donnée produite : B un nombre entier binaire

But : Traduction du nombre entier N en un nombre binaire par soustractions successives de puissance de 2 favorables.

Nous partons d’une valeur N décimale entière donnée par un utilisateur. Nous supposons dans cet algorithme que la valeur N saisie correspond à la demande, du coup il n’y a pas de vérification de cette valeur et correspond à l’hypothèse de la spécification. Le nombre binaire B est initialement vide. Un calcul de la puissance de 2 est effectué pour initier B à zéro. A savoir, il faut un mMax tel que 2mMax > N. soit le mMax est donné et il faut le vérifier soit il est calculé en fonction de N.

Figure 1.49. Figure 56 : Algorithme de conversion entier décimal vers entier binaire

Figure 56 : Algorithme de conversion entier décimal vers entier binaire

Nous allons voir par l’exemple comment fonctionne l’algorithme de la figure 53. Prenons N = 12710 et plaçons nos valeurs pour N, m et B, en proposant mMax à 7. La valeur 7 donne 27 = 128 valeur suffisante et nécessaire pour être plus que N = 127. Tant que m est positif ou nul, soustraire à N les puissances de 2 possibles en ajoutant 1 au nombre B binaire à construire et jouant 0 si pas de soustraction.

Table 1.9. Figure 57 : Mise en œuvre d’un déroulement de l’algorithme de conversion

m TEST N B
Début 127 " "
7 27 = 128 > 127 127 " 0 "
6 26 = 64 ≤ 127 63 = 127 - 64 " 01 "
5 25 = 32 ≤ 63 31 = 64 - 32 " 011 "
4 24 = 16 ≤ 31 15 = 31 - 16 " 0111 "
3 23 = 8 ≤ 15 7 = 15 - 8 " 01111 "
2 22 = 4 ≤ 7 3 = 7 - 4 " 011111 "
1 21 = 2 ≤ 3 1 = 3 - 2 " 0111111 "
0 20 = 1 ≤ 1 0 = 1 - 1 " 01111111 "

A partir du déroulement de la figure 57, nous pouvons conclure que la valeur entière N = 12710 est équivalente à la valeur binaire 11111112.

L'ARITHMETIQUE BINAIRE

Lors de la manipulation des nombres, nous sommes amenés à faire des calculs avec. Tous les calculs sont sujets à des algorithmes précis qui devront prendre en compte la taille des mots binaires et la place réservée pour produire le calcul. Il faut savoir que toutes les informations concernant le résultat ne sont pas obligatoirement stockées au même endroit dans une machine. Il y aura par exemple des stockages spécifiques pour dénoter un dépassement, un débordement de résultat. Toute cette partie a donc pour but de présenter les algorithmes et conséquences sur les résultats.

ADDITION ENTRE BINAIRES

[Note]

Nom de l’algorithme : Addition entre binaires

Donnée d’entrée : Deux nombres entiers binaires B1 et B2

Donnée produite : Un nombre entier binaire avec une retenue potentielle

But : Additionner deux nombres binaires pour en produire un résultat et une retenue potentielle en fonction de la place disponible pour le résultat.

Les calculs d’additions entre binaires utilisent les mêmes algorithmes que toutes les autres additions. L’addition se positionne sur les valeurs des bits en fonction du rang d’indice. Et comme tout algorithme d’addition, il faut maintenant considérer les tailles des mots. En effet, si nous avons des mots de taille 1 alors le résultat est de taille 1. Si le résultat ne peut pas tenir sur une case alors nous avons une retenue positive. En informatique la retenue (positive ou négative) est également nommée dépassement (Carry). Le phénomène de la retenue se propage en fonction de la taille n et s’applique sur le bit d’indice n+1.

Prenons deux binaires B1 et B2 de taille 1. Si nous respectons le polynôme nous avons :

Pour B1, deux valeurs possibles :

B1 = 0 * 20

B1 = 1 * 20

Pour B2, deux valeurs possibles :

B2 = 0 * 20

B2 = 1 * 20

Et nous faisons l’addition de B1 + B2 selon toutes les valeurs possibles :

B1 + B2 = 0 * 20 + 0 * 20 = 0 * 20

B1 + B2 = 0 * 20 + 1 * 20 = 1 * 20

B1 + B2 = 1 * 20 + 0 * 20 = 1 * 20

B1 + B2 = 1 * 20 + 1 * 20 = 1 * 21 + 0 * 20

Nous constatons donc que lorsque B1 = B2 = 12 nous produisons une retenue positive sur 21. Il est évident que lorsque nous allons manipuler les additions, il sera inutile de répéter à chaque fois les valeurs de puissance de 2 selon les indices. Mais, il ne faudra pas oublier de bien respecter les dépassements les cas échéants.

Prenons un exemple avec B1 = 10012 additionné à B2 = 1112. L’ordre importe peu B1 + B2 est équivalent B2 + B1. Nous prenons l’hypothèse que nous sommes sur des tailles fixées, nous devons rajouter les 0 significatifs à B2 = 01112.

Table 1.10. Figure 58 : Mise en œuvre d’un déroulement de l’algorithme d’addition

Retenue 1 1 1 1 0
B1 1 0 0 1
B2 + 0 1 1 1
Résultat 1 1 0 0 0

Si nous reprenons l’exemple de la figure 58, nous constatons que la première retenue positive sera à 0. Elle d’ailleurs toujours à 0 (nous pourrons le constater lors du cours matériel que cette retenue initiale sera branchée à la masse électrique). Ensuite, nous faisons le calcul de droite à gauche, bit par bit, en appliquant les concepts de l’addition et de la retenue. Donc 1 + 1 donne 0 avec une retenue positive à 1, cette retenue est distribuée aux bits suivants des nombres B1 et B2 et le calcul est donc 1 + 0 + 1 donnant 0 en résultat avec 1 en retenue positive puis et le calcul est 1 + 0 + 1 donnant 0 en résultat avec 1 en retenue positive puis 1 + 1 + 0 donnant 0 puis 1 bit de retenue positive. Nous pouvons donc conclure que la valeur est 1000 (en fonction de la taille du nombre additionné) avec 1 bit de retenue positive. Ou, nous pourrions tolérer 11000, si nous avions une capacité plus grande de résultat. Il est donc important de manipuler les tailles correctes des mots binaires utilisés pour conclure entre résultat et retenue.

SOUSTRACTION ENTRE BINAIRES

[Note]

Nom de l’algorithme : Soustraction entre binaires

Donnée d’entrée : Deux nombres entiers binaires B1 et B2

Donnée produite : Un nombre entier binaire avec une retenue négative potentielle

But : Soustraire deux nombres binaires pour en produire un résultat et une retenue négative potentielle en fonction de la place disponible pour le résultat.

Les calculs de soustraction entre binaires utilisent les mêmes algorithmes que toutes les autres soustractions. La soustraction se positionne sur les valeurs des bits en fonction du rang d’indice. Et comme tout algorithme de soustraction, il faut maintenant considérer les tailles des mots. En effet, si nous avons des mots de taille 1 alors le résultat est de taille 1. Si le résultat ne peut pas tenir sur une case alors nous avons une retenue négative. Le phénomène de la retenue négative se propage en fonction de la taille n et s’applique sur le bit d’indice n+1.

Prenons deux binaires B1 et B2 de taille 1. Si nous respectons le polynôme nous avons :

Pour B1, deux valeurs possibles :

B1 = 0 * 20

B1 = 1 * 20

Pour B2, deux valeurs possibles :

B2 = 0 * 20

B2 = 1 * 20

Et nous faisons la soustraction de B1 - B2 selon toutes les valeurs possibles :

B1 - B2 = 0 * 20 - 0 * 20 = 0 * 20

B1 - B2 = 1 * 20 - 0 * 20 = 1 * 20

B1 - B2 = 1 * 20 - 1 * 20 = 0 * 20

B1 - B2 = 0 * 20 - 1 * 20 = -1 * 21 + 0 * 20

Prenons un exemple avec B2 = 1112 soustrait à B1 = 10012. Attention, la soustraction ne donne pas le même résultat (sauf cas particuliers) si nous faisons B1 – B2 ou B2 – B1. Nous prenons l’hypothèse que nous sommes sur des tailles fixées, nous devons rajouter les 0 significatifs à B2 = 01112.

Table 1.11. Figure 59 : Mise en œuvre d’un déroulement de l’algorithme de la soustraction

Retenue négative 0 -1 -1 0 0
B1 1 0 0 1
B2 - 0 1 1 1
Résultat 0 0 0 1 0


Si nous reprenons l’exemple de la figure 59, nous constatons que la première retenue sera à 0 (même position initiale que précédemment décrite). Ensuite, nous faisons le calcul de droite à gauche, bit par bit, en appliquant les concepts de la soustraction et de la retenue négative. Donc 1 - 1 donne 0 pas de retenue. Ensuite, nous avons 0 – 1.

En l’état, il n’est pas possible de faire le calcul directement, nous avons donc besoin d’une base pour en réalité faire 10 – 1, ce qui donne 1 en résultat et -1 en retenue négative. Le fait d’ajouter une base peut aussi se dire, descendre une base. La retenue négative est aussi appelée propagation de la base du fait d’avoir eu recours à l’ajout d’une base pour faire le calcul aux bits précédents.

Cette retenue négative est distribuée aux bits suivants des nombres B1 et B2. Ainsi le calcul devient 0 – 1 – 1, soit 0 – 10 ce qui nécessite de faire appel à une base pour obtenir 10 – 10, donnant 0 en résultat et provoquant la diffusion de -1, une retenue négative, aux bits suivants. Nous obtenons ensuite 1 – 0 – 1 soit 0 en résultat et pas de retenue.

Nous n’avons pas de retenue négative finale à propager. Pour le moment, nous ne faisons pas l’étude des nombres négatifs et leurs calculs, cela nécessite plus d’algorithmes et de considérations. Nous verrons dans la suite du cours les nombres négatifs et nous reprendrons les concepts de dépassements et débordements pour obtenir en toutes circonstances le résultat des opérations.

MULTIPLICATION ENTRE BINAIRES

[Note]

Nom de l’algorithme : Multiplication binaire avec une base

Donnée d’entrée : Deux nombres entiers binaires B1 et B2, dont au moins une base

Donnée produite : Un nombre entier binaire

But : Multiplication deux nombres binaires pour en produire un résultat. Il y a au moins une base binaire parmi B1 et/ou B2.

Il est très simple de mettre en place cette multiplication, car au niveau architecture et algorithme il s’agit d’un simple ajout de zéros en bits de poids faible.

Rappelons qu’une base est un 1 suivi de N zéro. Donc 10, 100, 1000, 10000, … sont des bases. Donc, il suffit de compter les zéros de la base pour les ajouter au deuxième nombre à multiplier.

Ainsi 101010102 * 100002 = 1010101000002.

Nous considérons que nous avons assez de place pour produire le résultat. Attention cependant, dans une architecture hardware les tailles des mots sont limitées. Par exemple, vous avez du 64 bits. Donc soit il faut plusieurs mots pour produire un résultat, soit il y aura une erreur de dépassement. Pour garantir la taille des stockages rentre en jeu les logiciels de pilotage du matériel comme les outils avec les langages typés.

[Note]

Nom de l’algorithme : Multiplication binaire quelconque

Donnée d’entrée : Deux nombres entiers binaires B1 et B2 quelconque

Donnée produite : Un nombre entiet binaire

But : Multiplication deux nombres binaires pour en produire un résultat.

Pour faire une multiplication de nombres binaires quelconques, nous devons faire de la recopie, du décalage et de l’addition.

Par exemple, nous voulons multiplier B1 = 11012 et B2 = 1012. L’ordre importe peu et B1 * B2 est équivalent à B2 * B1. La vraie différence est que pour l’un ou pour l’autre, nous aurons plus de calculs à faire.

Table 1.12. Figure 60 : Mise en œuvre d’un déroulement de l’algorithme de la multiplication

B1 1 1 0 1
B2 * 1 0 1
Retenue 1 1 1 1 0 0 0
1 1 0 1
0 0 0 0
1 1 0 1
Résultat 1 0 0 0 0 0 1


Pour cet algorithme, nous fixons nos binaires, et faisons B1 * B2. A partir du bit de poids faible de B2, nous recopions B1 car il s’agit d’un 1. Puis il faut établir un décalage et faire à partir du bit suivant de B2 un série de zéro équivalent au nombre de bit de B1, car il s’agit d’un 0. Et enfin après un décalage nous faisons une recopie de B1 car il y a un 1. Une fois notre addition construite, il faut additionner colonne par colonne en propageant le cas échéant la retenue positive. Ainsi nous obtenons 1 = 0 + 1, puis 0 = 0 + 0 + 0, puis 0 + 1 + 0 + 1 donnant 0 en résultat et une retenue à 1. Ensuite 1 + 1 + 0 + 0 donnant 0 en résultat et 1 en retenue, puis 1 + 0 + 1 donnant 0 en résultat et 1 en retenue, puis 1 + 1 donnant 0 en résultat et une retenue. Soit B1 * B2 = 10000012.

DIVISIONS ENTRE BIANIRES

[Note]

Nom de l’algorithme : Division entière binaire avec une base

Donnée d’entrée : Deux nombres entiers binaires B1 et B2, dont au moins une base

Donnée produite : Deux nombres entiers binaires

But : Diviser deux nombres binaires pour en produire un résultat d’un nombre entier avec un reste éventuel. Il y a au moins une base binaire parmi B1 et/ou B2. Il est possible de provoquer une troncature et la perte de valeurs.

Il est très simple de mettre en place cette division, car au niveau architecture et algorithme, il s’agit d’un simple décalage à droite en perdant les bits de poids faible.

Rappelons qu’une base est un 1 suivi de N zéro. Donc 10, 100, 1000, 10000, … sont des bases. Donc, il suffit de compter les zéros de la base pour trouver la longueur du décalage à faire.

Ainsi 101010102 / 100002 = 10102

[Note]

Nom de l’algorithme : Division euclidienne entière binaire quelconque

Donnée d’entrée : Deux nombres entiers binaires B1 et B2 quelconque

Donnée produite : Deux nombres entiers binaires

But : Diviser deux nombres binaires pour en produire un résultat d’un nombre entier avec un reste éventuel. Il est possible de provoquer une troncature et la perte de valeurs.

Pour aborder cet algorithme, il faut en redonner le principe. Une division euclidienne est faite de dividende, diviseur, quotient et reste en utilisant : quotient * diviseur + reste = dividende.

Les hypothèses sont que dividende et diviseur sont fixés, ce sont les données d’entée. Nous cherchons les valeurs du quotient et du reste. Dans cet algorithme, nous faisons de la division entière, donc notre quotient sera un entier, tout comme le reste à partir du dividende et diviseur entiers donnés.

Pour commencer, le diviseur sera plus grand que le dividende, sinon l’entier du quotient sera toujours l’entier 0 avec le dividende égal au reste.

Si nous avons un dividende plus grand que le diviseur, nous allons devoir faire des étapes de multiplications et de soustractions jusqu’à obtenir le plus grand entier possible pour le quotient.

A partir du diviseur, nous regardons et ajustons combien de fois il peut-être de dedans. Pour cela, nous utilisons des indices sur le dividende pour en demander juste une sur-approximation du diviseur. Ensuite, et comme nous sommes en binaire, nous multiplions par 1 pour obtenir le diviseur qui sera soustrait à la partie du dividende sélectionné.

S’il reste des bits au niveau du dividende, alors il sera ajouté en bit de poids faible du résultat obtenu par soustraction. Si le chiffre ainsi reconstitué est plus petit que le diviseur et si il reste des bits au niveau du dividende alors il y aura un 0 dans le quotient et le processus de sur approximation sera refait avec le nouveau bit donné en bit de poids faible sur le résultat précédent. S’il y a plus de possibilité de soustraire le diviseur au dividende restant alors le dividende restant sera le reste de la division.

Figure 1.50. Figure 61 : Algorithme de division euclidienne

Figure 61 : Algorithme de division euclidienne

Dans le détail, les éléments de l’algorithme de la figure 61 sont :

na et nb les tailles en nombre de chiffres des nombres A / B. b1 et b2 les indices calculés déterminant la longueur de A, puis A', puis A", … le nombre A qui sera divisé par B.

Pour illustrer et utiliser l’algorithme de la division euclidienne, prenons B1 / B2, avec B1 = 101101112 et B2 = 11002 :

Figure 1.51. Figure 62 : Division euclidienne binaire

Figure 62 : Division euclidienne binaire

LE CODAGE DES ENTIERS BINAIRES NEGATIFS

Figure 1.52. Figure 63 : Les données informatiques

Figure 63 : Les données informatiques

Il existe plusieurs méthodes pour coder des binaires négatifs. Il faut considérer tout d’abord la taille des mots de codage. Effectivement tout le sens de la négation sera porté par les bits de poids fort du mot. Donc, il est obligatoire de fixer la taille des mots binaires pour manipuler et identifier les bits de poids fort. Les 3 algorithmes de codage que nous allons étudier sont :

Les 3 algorithmes de codage que nous allons étudier sont :

  1. La valeur absolue signée

  2. Le complément à 1

  3. Le complément à 2

ALGORITHME DE LA VALEUR ABSOLUE SIGNEE

[Note]

Nom de l’algorithme : Valeur absolue signée

Donnée d’entrée : Un nombre entier binaire B, dont la taille est fixée

Donnée produite : Un nombre entier binaire –B, dont la taille est fixée

But : Reserve et inverse le bit de poids fort du nombre binaire B. Le binaire positif devient négatif et inversement le nombre binaire négatif devient positif

Il est plus simple de passer par un exemple pour dérouler cet algorithme de la valeur absolue signée. Nous fixons un nombre binaire B positif de taille 8 bits sur un octet : B = 0011 11102.

Le Bit de poids fort de B est celui de gauche. Il est réservé exclusivement au signe de l’entier codé. Il vaut 1 si le binaire codé est négatif et 0 sinon.

Donc Pour avoir la valeur négative de B, il suffit de rajouter un 1 en bit de poids fort : -B = 1011 11102

Soit B un nombre binaire négatif de taille 12 bits : 1000 0011 11102

Pour avoir la valeur positive de B, il suffit d’inverser le 1 du bit de poids fort en 0 : - B = 0000 0011 11102

ALGORITHME DU COMPLEMENT A 1

[Note]

Nom de l’algorithme : Complément à 1

Donnée d’entrée : Un nombre entier binaire B, dont la taille est fixée

Donnée produite : Un nombre entier binaire –B, dont la taille est fixée

But : Reserve et inverse tous les bits du nombre binaire B. Le binaire positif devient négatif et inversement le nombre binaire négatif devient positif

Nous sommes toujours avec des nombres binaires, dont la taille est fixée au départ. Pour cet algorithme du complément à 1, l’entrée peut être un nombre binaire positif, la sortie sera un nombre binaire négatif ou inversement l’entrée peut être un nombre binaire négatif, la sortie sera un nombre binaire positif. Le but de l’algorithme est d’inverser les 1 en 0 et les 0 en 1 du nombre binaire B entré. Attention, l’étape d’inversion se fait en lisant bit par bit le nombre binaire entré, en inversant les bits directement dès la lecture.

Soit B un nombre binaire de taille 12 bits : 0000 0001 11102 Pour avoir la valeur négative de B, il suffit de rajouter un 1 en bit de poids fort : - B = 1111 1100 00012

Soit B un nombre binaire de taille 12 bits : 1111 1100 00012

Pour avoir la valeur négative de B, il suffit de rajouter un 1 en bit de poids fort : - B = 0000 0001 11102

ALGORITHME DU COMPLEMENT A 2

[Note]

Nom de l’algorithme : Complément à 2

Donnée d’entrée : Un nombre entier binaire B, dont la taille est fixée

Donnée produite : Un nombre entier binaire –B, dont la taille est fixée

But : Reserve et inverse tous les bits du nombre binaire B. Le binaire positif devient négatif et inversement le nombre binaire négatif devient positif

Nous sommes toujours avec des nombres binaires, dont la taille est fixée au départ. Pour cet algorithme, l’entrée est un nombre binaire positif ou négatif, la sortie est un nombre binaire négatif ou positif.

Première méthode :

A partir du nombre binaire, faire le complément à 1 puis ajouter 1.

Soit B un nombre binaire de taille 12 bits : 0000 0001 11102

Pour avoir la valeur négative de B, il suffit de rajouter un 1 en bit de poids fort : - B = 1111 1100 00012 + 1 = 1111 1100 00102

Deuxième méthode :

A partir du nombre binaire, recopier tous les zéros de bit de poids faible. Recopier le premier 1 des bits de poids faible puis inverser les 1 en 0, ou les 0 en 1.

Soit B un nombre binaire de taille 12 bits : 0000 0001 11102

Pour avoir la valeur négative de B, il suffit de rajouter un 1 en bit de poids fort : - B = 1111 1100 00102

COMPRENDRE LE COMPLEMENT A 2 ET LE DEBORDEMENT PAR CALCUL

Il est à noter qu’il faut bien respecter les codages, les algorithmes utilisés et les résultats obtenus pour bien comprendre les méthodes et les mots binaires stockés. Ainsi en fonction des codages négatif ou positif, nous pourrons utiliser le complément à 2 pour connaitre les valeurs stockées. Il faut faire confiance à la machine, mais c’est un bon moyen de vérifier son travail.

Etudions le principe de débordement :

B1 et B2 des binaires entiers négatifs.

Table 1.13. Figure 64 : Addition avec débordement

B1 1 1 0 1
B2 + 1 0 0 0
Résultat 1 0 1 0 1

A partir de la figure 64, le zéro en bit de poids fort dénote une anomalie brute de résultat, en notifiant également le dépassement, le résultat est faux, car il s’agit d’un nombre positif en additionnant 2 nombres négatifs. En réalité, il s’agit de la taille des mots binaires qui ont une dynamique de codage trop petite pour coder le résultat. Pour pallier à cette erreur, il faut augmenter la taille des mots ou tout simplement tolérer l’erreur et dire qu’il y a une erreur. Cela peut correspondre aux différents messages d’erreur des langages compilés.

Table 1.14. Figure 65 : Addition sans débordement

B1 1 1 0 0
B2 + 1 1 1 0
Résultat 1 1 0 1 0


A partir de la figure 65, le un en bit de poids fort dénote une correspondance avec les uns de bits de poids fort des nombres. Malgré le dépassement le résultat est correct car il est négatif et donc la taille de codage est acceptable pour obtenir le résultat.

LE REGISTRE DES ETATS

Nous avons manipulé les Retenues (Carry), les Débordements (Over flow), les nombres négatifs. A partir de ces résultats obtenus, la machine garde en mémoire ces informations dans un registre (un espace de stockage particulier) appelé registre d’états. Vu comme un ensemble de drapeau (flag) chaque case aura comme valeur 0 ou 1. Par exemple, prenons le registre Z N V C, si il y a des 1 dans les cases cela notifiera que le résultat est : Zero, Negative, avec Over Flow et Carry, si il y a des 0 cela indiquera l’absence de ces informations.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels