NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : 1ère générale, enseignement de spécialité NSI

 
Chapitre 1 : Représentation des données Chapitre 2 : Logique combinatoire et séquentielle Chapitre 3 : Les réseaux : adresses IP Chapitre 4 - Interactions entre l’homme et la machine Chapitre 5 - Les formulaires sur le web Chapitre 6 - Machine learning - KNN Chapitre 7 - Algorithmes gloutons
 
Chapitre 1 - Variables, types et opérateurs Chapitre 2 - Les conditions (instructions if, elif, else) Chapitre 3 - Les boucles (instructions for, while) Chapitre 4 - Les fonctions Chapitre 5 - Mini projet Jeu Chapitre 6 - Communiquer en réseau Chapitre 7 - Algorithmes et complexité Chapitre 8 - Système d'exploitation Linux Chapitre 9 - Jeu codé de nim en php Chapitre 10 - Jeu du 2048 codé en Javascript
 
TP Chapitre 1 TP Chapitre 2 TP Chapitre 3 TP Chapitre 4
 

D
É
C
O
N
N
E
C
T
É

CHAPITRE 2 - AU COEUR DE L'ORDINATEUR

C'est en 1847, que le mathématicien Georges Boole publia son livre "sort Mathematical Analysis of Logic". C'est de cette série de travaux que l'algèbre de Boole vit le jour.

En 1966, dans le centre de calcul de La Gaude (IBM), le directeur présente un ordinateur, machine de grande taille, qui permet d'effectuer des calculs et des opérations logiques de façon extrêmement rapide (souce ina.fr).

1 - Les fonctions logiques combinatoires :

FonctionSymbolesymbole IECTable de vérité

NON

Elle inverse l'état logique de son entrée :

S= a

aS
0
?
1
?

ET

La sortie est vraie que si a et b sont vrais :

S = a.b

abS
00
?
01
?
10
?
11
?

OU

La sortie est vraie si a ou b sont vrais :

S = a+b

abS
00
?
01
?
10
?
11
?

OU Exclusif ou XOR

La sortie est vrai si a ou b sont vrais mais pas si a et b sont vrai :

S = a⊕b

abS
00
?
01
?
10
?
11
?

1.1 - Association de portes logiques

Exercice : placez les portes logiques pour réaliser la fonction S = a.(b+c)

aS

b

c

Remplir la table de vérité ci-dessous :

cbaS1S2S
000
?
?
?
001
?
?
?
010
?
?
?
011
?
?
?
100
?
?
?
101
?
?
?
110
?
?
?
111
?
?
?

On peut faire le parallèle en programmation, avec l'instruction if en python contenant plusieurs conditions :

Exemple : les variables contiennent les entiers suivant : a=5, b=10 et c=-5. Indiquer dans le tableau le résultat du test : vrai =1 faux = 0

Test ifRésultat
a>3 and b<10 or c<0
?
a==5 and b<0 or c==0
?
a>3 and b>5 or c<0
?
a>3 and (b<5 or c>0)
?

Le microprocesseur possède une UAL (unité arithmétique et logique) qui lui permet de faire des calculs.

Un code opération binaire, va définir s'il s'agit d'un calcul arithmétique (+, -, *, etc..) ou d'une opération logique (ou, et, décalage à gauche, etc...).

Le résultat de l'opération pourra être stocké dans la mémoire RAM ou dans des registres internes du microprocesseur. Des drapeaux sont positionnés selon que le résultat de l'opération est nul, négatif, ou qu'il présente un débordement ou une retenue

1.2 Exercices :

Ex1 : Déterminer les opérations logiques réalisées sur deux octets

Octet 1 11110101
Opération 1
Octet 2 01011101
Résultat01010101
Octet 1 11110101
Opération 2
Octet 2 01011101
Résultat10101000
Octet 1 11110101
Opération 3
Octet 2 01011101
Résultat11111101
Octet 1 11110101
Opération 4
Résultat00001010

Ex2 : Additionneur binaire logique

Remplir la la table de vérité ci-dessous pour réaliser une addition binaire avec retenue

b1b0SommeRetenue
00
?
?
01
?
?
10
?
?
11
?
?



b0

b1

S






R

Ex3 : Transcodage UTF-8 -> ISO-8859-1

ISO-8859-1caractèreUTF-8
7Az7A
7FDEL (Delete)7F
A3£C2 A3
BC¼C2 BC
BD½C2 BD
BE¾C2 BE
BF¿C2 BF
C0ÀC3 80
C1ÁC3 81
C2ÂC3 82
E6æC3 A6

L'extrait de la table montre que le code UTF-8 est codé sur 2 octets pour les caractères étendus (supérieurs à 0x7F) alors que le code ISO-8859-1 est codé sur 1 octet

Methode de transcodage :

Prenons le code UTF-8 du caratère ½ codé C2 BD, il suffit de recopier l'octet de droite.

Pour les caractères commençant par C3 voici la méthode :

On masque le quatet de poids faible de C3 en effectuant une fonction ET logique avec 0xF0, avec ce résultat obtenu, on fait une fonction OU logique avec le deuxième octet

Exemple pour transcoder en ISO-8859-1 le caractère æ codé C3 A6 en UTF-8

code hexaBinaire
C311000011
F011110000
C3 et F0 =
?
?
?
?
?
?
?
?
ou A610100110
?
?
?
?
?
?
?
?

Ex4 : On donne le tableau suivant permettant de connaître le code opération de l'UAL :

b2b1b0opération
000NON
001OU
010ET
011XOR
100+
101-
110/
111*

Résoudre les calculs proposés à l'UAL et positionner les drapeaux :

  • N = 1 si le résultat est négatif (Negative)
  • Z = 1 si le résultat est nul (Zero)
  • C = 1 s'il y a une retenue après le 8ème bit (Carry)
  • V = 1 s'il y a un dépassement de capacité : le signe des opérandes diffère du résultat (Overflow)

    • Octet 1 11010000
    Octet 2 11011101
    Opération 1 : 100(2)
    Résultat 1
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    NZCV
    Drapeaux 1
    ?
    ?
    ?
    ?
    Octet 2 00100010
    Octet 3 11011101
    Opération 2 : 010(2)
    Résultat 2
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    NZCV
    Drapeaux 2
    ?
    ?
    ?
    ?
    Octet 4 10100010
    Octet 5 11011101
    Opération 3 : 100(2)
    Résultat 3
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    ?
    NZCV
    Drapeaux 3
    ?
    ?
    ?
    ?

    2 - Logique séquentielle

    En logique combinatoire, la sortie ne dépend que des entrées, en logique séquentielle, l'entrée peut dépendre de l'état précédent d'une sortie.

    2.1 - La bascule RS

    Animation bascule RS

    En observant l'animation, remplir compléter la table de vérité

    RSQQ
    10
    ?
    ?
    00
    ?
    ?
    01
    ?
    ?
    00
    ?
    ?
    11
    ?
    ?

    Que remarque-t-on ?


    Ce type de bascule permet de mémoriser l'état d'un bit, on l'appelle mémoire unitaire. Avec 8 bascules on pourrait mémoriser un octet

    2.2 - Additionneur 2 bits avec retenue :

    Le schéma logique ci-dessous permet d'additionner E1+E2+Cin

    Remplir la table de vérité

    E1 E2 Cin S Cout
    0 0 0
    ?
    ?
    0 0 1
    ?
    ?
    0 1 0
    ?
    ?
    0 1 1
    ?
    ?
    1 0 0
    ?
    ?
    1 0 1
    ?
    ?
    1 1 0
    ?
    ?
    1 1 1
    ?
    ?

    A l'aide du logiciel Logisim, reproduire le schéma logique puis simuler le fonctionnement pour vérifier la table de vérité

    2.3 - Additionneur binaire de 2 quartets

    Charger le fichier Additionneur4bits et simuler le fonctionnement

    Remplir la table ci-dessous

    B1 Hexa B2 Hexa Cout3 S3 S2 S1 S0 Affichage
    0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 02
    0 1 1 1 0 0 1 0
    ?
    ?
    ?
    ?
    ?
    1 1 1 1 1 1 0 1
    ?
    ?
    ?
    ?
    ?

    Expliquer comment on est passé du schéma de l'additionneur deux bits avec retenue à l'additionneur de 2 quartets


    Le microprocesseur est composé de ces portes logiques, réalisées avec des transistors : c'est l'architechture de von Neuman, matématicien et physicien américono-hongrois. Cette structure permet d'effectuer les calculs mathématiques et logiques sur plusieurs octets. Selon l'article du site 01net.com, IBM a développé une puce composée de 30 milliards de transistors sur une surface aussi grande qu'un ongle. Le premier microprocesseur d'Intel, le 4004, intégrait en 1971 seulement... 2300 transistors !

    En 1969, dans l'usine IBM de Corbeil-Essonnes, le directeur technique montre les différentes étapes de miniaturisation des composants de l'ordinateur franchies en dix ans, avec l'utilisation du transistor et du circuit intégré.


    2.4 - Mémorisation d'un état logique

    Le microprocesseur utilise la mémoire RAM pour y stocker les résultats des calculs sous forme binaire. La bascule D, dont le schéma est donné ci-dessous, permet de mémoriser l'état d'un bit par validation d'une horloge H.

    Complétez la table de vérité ci-dessous sans simuler le montage :

    DHQ
    01
    ?
    00
    ?
    10
    ?
    11
    ?
    10
    ?
    00
    ?
    01
    ?

    Saisir le schéma dans Logisim, simuler le fonctionnement et vérifier la table de vérité.

    REMARQUE : Lorsque l'entrée H est à 0, la sortie Q mémorise l'état précédent.

    Ce principe est utilisé par la mémoire du microprocesseur (RAM) pour y stocker les informations binaires. Pour mémoriser un octets, il faut 8 bascules D actionnés par la même horloge H.

    2.5 - Accès mémoire

    Les octets de la mémoire RAM sont empilés et accessibles par une adresse unique. C'est le microprocesseur qui va placer un mot binaire sur son bus d'adresse afin d'accéder aux cases mémoire souhaitées.

    Télécharger le fichier Ram.circ et ouvrez-le avec Logisim

    Pour écrire la donnée 01 dans la case mémoire se trouvant à l'adresse 00, procédez comme suit :

  • Mettre tous les bits du bus d'adresse à 0
  • Mettre la broche Select à 1
  • Mettre sur le bus de données 0000 0001
  • Donner un coup d'horloge H : 0 à 1 puis 1 à 0

    • Continuez ainsi pour remplir La RAM avec les octets de l'image ci-dessus

    Mettre la RAM en lecture pour parcourir les données de la mémoire

    Quelle donnée se retrouve dans RAM[4]= 0x ça vous rappelle quelque chose ?

    Ajouter un compteur 8 bits (Memory - Counter) actionné par deux boutons poussoirs H et RESET

    Mettre les broches select et Lire à 1 puis actionner H et RESET pour comprendre le fonctionnement

    Compléter le programme en langage Python qui aurait le même comportement que notre schéma : lire la RAM de 0 à 0x0B


     
				
      

											
    
						

			
		
    Remarque : dans la RAM du PC il peut probable que les données seront stockées à l'adresse 0, mais il suffit de connaitre l'adresse du pointeur de départ de notre liste pour incrémenter le compteur.
    
	
    

    


    3 - Langage assembleur
    

    
	
    Le langage assembleur est un langage de bas niveau et se limite à un jeu d'instructions réduit : RISC (Reduced instruction set computing). C'est tout l'opposé d'un langage 
	comme python qui est un langage de haut niveau et fait abstraction de tous les registres et drapeaux d'états lors de la programmation. Le but de cet 
	exercice est dedérouler l'exécution d'une suite d'instructions simple en langage machine.
    
	
    Nous allons utiliser un simulateur en ligne développé par Peter L Higginson. Il va permettre d'exécuter les instructions et est basé sur l'architecture de von Neumann  (portes logiques à transistors) : Simulateur
    





	
    
	
    On y trouve une mémoire RAM, une UAL (Unité Arithmétique et Logique) des registres permettant de stocker des valeurs temporaires, un décodeur d'opérations et un registre d'état statut (N:Négatif, Z:Zéro, V:débordement, C:retenue).
    
	
	
	
    3.1 - Simulation d'une addition entre deux registres
    
	
    
		
    Copier-coller le code suivant dans la fenêtre accueillant le code assembleur
    

		
				
			   		
		
    Cliquer sur la liste déroulante option et sélectionner hex, cliquez ensuite sur le bouton submit puis RUN
    
		
    Relever les valeurs de R0=  
								  R1= 
								  R2= , le résultat doit être R2 = R0 + R1
    
		
    Mofifier le programme afin de faire un ET logique (AND) entre R0 et R1 puis relever les valeurs suivantes:
    
							   
    R0=  
								  R1= 
								  R2= 
								  Flag NZCV=  
		
    
		
    Pourquoi le drapeau Z est-il à 1 ? 


		 
								
    
														
    
						


		
    On peut simuler les instructions input et print de python avec le code suivant :
    

			 
				
			   	


		
    Dans la partie cours nous avons positionné des drapeaux selon le calcul effectué sur un octet. 
		Or le simulateur fonctionne avec une UAL et une mémoire RAM de 16 bits. 
		Pour les vérifier nos résultats, on décale l'octet de 8 bits vers la gauche en complétant l'octet de le poids faible par des 0.
    
		
    ex : 1101 0000 (0xD0) devient  1101 0000 0000 0000 (0xD000)
      
		
    Pour accélérer l'exécution du simulateur sélectionner "def execute" dans la liste des options. 
		
    
		
				
    Effectuer les calculs suivants avec le simulateur :  
    
		
    
		
    
		Calcul RésultatFlags NZCV
		
    
		
    
		0xD000 + 0xDD000x
							0b
		
    
		
    
		0xA200 + 0xDD000x
							0b
		
    
		
    
		0x2200 ET 0xDD000x
							   0b
		
    
		
    					

		
     

											
    
						
	
    
	
	
	
    3.2 - Ecriture et lecture dans la RAM de plusieurs octets
    
	
    
		
		
	   	

		
    Modifier ce programme pour stocker à partir de l'adresse 200 les codes ascii des lettres composant votre prénom, puis le faire afficher entièrement.
    
				 
    
			   	
		
						
						


		
    Chalenge : Réaliser un programme qui compte le nombre de fois qu'une lettre déterminée à l'avance se trouve dans votre prénom
    
		
    Exemple : le programme doit afficher 2 si je compte le nombre de A qu'il y a dans PASCAL
    
	
    

    



    



    



Fond :   
Texte :    
Tables :