Florian Mircea Boian

De la aritmetică la calculatoare

Cluj University Press

1996

C U P R I N S

PREFATA. . . . . . . . . . . . . . . . . . . . . . . . . . 6

Capitolul 0 PRELIMINARII. . . . . . . . . . . . . . . . . 8

0.1 Elemente de aritmetică. . . . . . . . . . . . . . . . 8

0.1.1 Câteva proprietăţi ale funcţiei modulo . . . . 8

0.1.2 Funcţii de tip parte întreagă. . . . . . . . . 9

0.2 Elemente de algebră Booleană. . . . . . . . . . . . . 11

0.2.1 Mulţimea B₂; operaţii. . . . . . . . . . . . . 11

0.2.2 Funcţii Booleene şi reprezentări ale lor . . . 13

0.3 Structura şi funcţiile unui sistem de calcul. . . . . 15

0.3.1 Principiile lui von Neumann de construire a unui

calculator. . . . . . . . . . . . . . . . . . 15

0.3.2 Modelul formal al unui calculator. . . . . . . 16

0.3.3 Structura şi componentele unui SC. . . . . . . 17

0.3.3.1 Structura şi funcţiile hardware . . . 17

0.3.3.2 Memoria . . . . . . . . . . . . . . . 17

0.3.3.3 Componenta de prelucrare. . . . . . . 19

0.3.3.4 Periferice; clasificări . . . . . . . 19

0.3.3.5 Componenta de control . . . . . . . . 20

0.3.3.6 Caracteristicile hard ale suportului

de tip disc. . . . . . . . . . . . . 20

0.3.3.7 Videoterminale. . . . . . . . . . . . 23

Capitolul 1 SISTEME SI BAZE DE NUMERATIE. . . . . . . . . 25

1.1 Tipuri de sisteme de numeraţie. . . . . . . . . . . . 25

1.1.1 Sistemul de numeraţie aditiv (roman) . . . . . 25

1.1.2 Sistemul de numeraţie poziţional (arab). . . . 26

1.2 Sisteme poziţionale de numeraţie în diverse baze. . . 27

1.2.1 Reprezentarea numerelor naturale într-o bază b 27

1.2.2 Reprezentarea numerelor reale într-o bază b. . 29

1.2.3 Conversii între baze de numeraţie. . . . . . . 32

1.2.3.1 Conversia întregilor prin împărţiri

succesive. . . . . . . . . . . . . . 32

1.2.3.2 Conversia părţilor fracţionare prin

înmulţiri succesive. . . . . . . . . 34

1.2.3.3 Conversia prin metoda substituţiei. . 37

1.2.3.4 Sumar al conversiilor între baze. . . 38

1.2.3.5 Conversie rapidă între bazele 8 şi 10 39

1.3 Relaţii între bazele 2, 8 şi 16 . . . . . . . . . . . 40

1.3.1 Cifre binare, octale, zecimale, hexazecimale . 40

1.3.2 Conversii binar - octal. . . . . . . . . . . . 41

1.3.3 Conversii binar - hexazecimal. . . . . . . . . 43

1.3.4 Conversii octal - hexazecimal. . . . . . . . . 44

Capitolul 2 CELE PATRU OPERATII CU BAZE MARI DE NUMERATIE 45

2.1 Adunarea în baza P. . . . . . . . . . . . . . . . . . 45

2.2 Scăderea în baza P. . . . . . . . . . . . . . . . . . 47

2.3 Inmulţirea în baza P. . . . . . . . . . . . . . . . . 48

2.4 Impărţirea în baza P. . . . . . . . . . . . . . . . . 49

2.5 Implementări ale unor aritmetici. . . . . . . . . . . 53

2.5.1 Unitatea B2E16 . . . . . . . . . . . . . . . . 53

2.5.2 Unitatea B2TOZ . . . . . . . . . . . . . . . . 53

Capitolul 3 CODIFICAREA INFORMATIEI . . . . . . . . . . . 57

3.1 Noţiunea de cod; exemple . . . . . . . . . . . . . . . 57

3.1.1 Definirea codului . . . . . . . . . . . . . . . 57

3.1.2 Exemple simple de coduri. . . . . . . . . . . . 58

3.1.3 Problema decodificării. . . . . . . . . . . . . 59

3.2 Codificarea datelor în calculator . . . . . . . . . . 61

3.2.1 Codificarea caracterelor . . . . . . . . . . . 61

3.2.2 Codificări zecimale ale numerelor întregi. . . 64

3.2.2.1 Codificarea zecimal - externă . . . . 64

3.2.2.2 Codificarea binar - zecimală. . . . . 65

3.2.3 Reprezentări binare ale numerelor reale. . . . 66

3.2.3.1 Reprezentarea în virgulă fixă . . . . 66

3.2.3.2 Reprezentarea în virgulă flotantă . . 68

3.2.3.3 Standarde de reprezentare în virgulă

flotantă . . . . . . . . . . . . . . 72

3.2.3.4 Conceptul de depăşire . . . . . . . . 77

3.2.3.5 Compararea numerelor reale. . . . . . 79

Capitolul 4 CODIFICARI BINARE SI ARITMETICA BINARA A

NUMERELOR INTREGI. . . . . . . . . 80

4.1 Dimensiuni şi tipuri de reprezentări. . . . . . . . . 80

4.2 Aritmetica numerelor întregi fără semn. . . . . . . . 81

4.2.1 Convenţia de reprezentare fără semn. . . . . . 81

4.2.2 Adunarea şi scăderea fără semn . . . . . . . . 82

4.2.3 Inmulţirea întregilor fără semn. . . . . . . . 84

4.2.4 Impărţirea întregilor fără semn. . . . . . . . 85

4.3 Reprezentări ale întregilor cu semn . . . . . . . . . 87

4.3.1 Particularizări ale reprezentării în virgulă

fixă. . . . . . . . . . . . . . . . . . . . . 87

4.3.2 Coduri de reprezentare a întregilor cu semn. . 88

4.3.2.1 Codul direct. . . . . . . . . . . . . 88

4.3.2.2 Codul invers. . . . . . . . . . . . . 89

4.3.2.3 Codul complementar. . . . . . . . . . 91

4.4 Operaţiile aritmetice în cod complementar . . . . . . 93

4.4.1 Suma algebrică în cod complementar . . . . . . 93

4.4.2 Inmulţirea în cod complementar . . . . . . . . 96

4.4.3 Impărţirea în cod complementar . . . . . . . . 98

4.5 Reprezentarea în memorie a datelor numerice . . . . . 100

4.5.1 Un program "ciudat". . . . . . . . . . . . . . 100

4.5.2 Reprezentări numerice în implementări de

limbaje . . . . . . . . . . . . . . . . . . . 103

4.5.3 Ordinea de plasare la diverse maşini . . . . . 103

Capitolul 5 CODURI DETECTOARE DE ERORI. . . . . . . . . . 109

5.1 Problema transmiterii informaţiei . . . . . . . . . . 109

5.2 Coduri liniare binare . . . . . . . . . . . . . . . . 110

5.2.1 Control prin bit de paritate . . . . . . . . . 110

5.2.2 Definirea codului liniar binar . . . . . . . . 112

5.2.3 Relaţii de control în coduri liniare binare. . 113

5.2.4 Evaluarea capacităţii de detecţie în codurile

liniare binare. . . . . . . . . . . . . . . . 116

5.2.5 Coduri iterative . . . . . . . . . . . . . . . 117

5.3 Structura unui bloc de informaţie pe un suport

magnetic . . . . . . . . . . . . . . . . . . . . . . 118

Capitolul 6 CIRCUITE COMBINATIONALE . . . . . . . . . . . 122

6.1 Circuite poartă şi realizarea lor fizică. . . . . . . 122

6.2 Implementarea funcţiilor booleene folosind circuite

poartă . . . . . . . . . . . . . . . . . . . . . . . 124

6.3 Câteva circuite remarcabile . . . . . . . . . . . . . 125

6.3.1 Circuite de însumare binară. . . . . . . . . . 125

6.3.1.1 Sumator binar cu o poziţie. . . . . . 125

6.3.1.2 Sumator binar cu n poziţii. . . . . . 127

6.3.1.3 Sumator binar pentru reprezentarea

în cod invers. . . . . . . . . . . . 128

6.3.2 Circuite de deplasare. . . . . . . . . . . . . 128

6.3.3 Circuit multiplexor. . . . . . . . . . . . . . 130

6.3.4 Circuit selector . . . . . . . . . . . . . . . 131

6.3.5 Gestiunea bitului de paritate. . . . . . . . . 132

Capitolul 7 MODELAREA FUNCTIONARII PROCESORULUI . . . . . 133

7.1 Maşina cu trei adrese . . . . . . . . . . . . . . . . 134

7.1.1 Formatul instrucţiunilor . . . . . . . . . . . 134

7.1.2 Tipuri de instrucţiuni şi lista acestora . . . 134

7.1.3 Rezolvarea ecuaţiei de gradul 2 la maşina cu

trei adrese . . . . . . . . . . . . . . . . . 136

7.1.4 Codificare simbolică şi numerică a programelor

(limbaj de asamblare şi limbaj maşină). . . . 138

7.2 Maşina cu o adresă. . . . . . . . . . . . . . . . . . 140

7.2.1 Arhitectura maşinii cu o adresă. . . . . . . . 140

7.2.2 Tipuri de instrucţiuni şi lista acestora . . . 142

7.2.3 Relaţii între maşinile cu trei adrese şi cu

o adresă. . . . . . . . . . . . . . . . . . . 145

7.3 Scheme de adresare. . . . . . . . . . . . . . . . . . 148

7.4 Exemple de programe şi completări la maşina cu o

adresă . . . . . . . . . . . . . . . . . . . . . . . 149

7.4.1 Codificarea simbolică şi numerică. . . . . . . 149

7.4.1.1 Principiile scrierii numerice . . . . 149

7.4.1.2 Rezolvarea ecuaţiei de gradul 2 . . . 151

7.4.2 Folosirea variabilelor cu indici . . . . . . . 151

7.4.2.1 Suma a 100 de numere. . . . . . . . . 151

7.4.2.2 Ordonarea unui şir prin metoda

bulelor. . . . . . . . . . . . . . . 153

7.4.3 Exemplu de folosire a subprogramelor . . . . . 155

7.4.3.1 Rezolvarea unei ecuaţii f(x)=0 prin

metoda coardei şi a tangentei. . . . 156

7.4.3.2 Structura unui program format din mai

multe secţiuni . . . . . . . . . . . 157

7.4.3.3 Comunicarea între secţiuni. . . . . . 159

7.4.3.4 Programul de rezolvare a unei ecuaţii

f(x)=0 . . . . . . . . . . . . . . . 162

BIBLIOGRAFIE . . . . . . . . . . . . . . . . . . . . . . . 165

ANEXA 1 Sursele Pascal ale unităţii B2TOZ . . . . . . . . 166

ANEXA 2 Sursele Pascal ale unităţii ARITMBIN. . . . . . . 173

ANEXA 3 Utilizări ale unităţilor B2TOZ şi ARITMBIN. . . . 176

P R E F A T A

Deşi tehnologia construcţiei calculatoarelor a evoluat fantastic de mult, mai ales în ultimii 10-15 ani, principiile fundamentale după caresunt construite sunt aceleaşi ca şi acum 40 de ani. Funcţionarea unui calculator, cu toată complexitatea lui,are ca suport matematic o serie de concepte aritmetice şi algebrice simple: bazele de numeraţie, cele patru operaţii în aceste baze, noţiunea de funcţie, elemente de calculul propoziţiilor etc. Suportul electronic al unui calculator are la bază materializarea fizică a cifrelor binare 0 şi 1, iar la nivelul imediat superior are la bază circuitele poartă, cele care materializează fizic operaţiile SI, SAU, NU şi SUMA modulo 2, cunoscute din calculul propoziţiilor.

Lucrarea de faţă are ca scop principal fundamentarea matematică a tehnologiei de construcţie a calculatoarelor, deci prezentarea modului în care sunt combinate suportul matematic şi cel electronic în vederea implementării principalelor funcţiuni ale unui sistem de calcul. In acest scop se prezintă "drumul" parcurs de cercetarea ştiinţifică de a direcţiona şi dezvolta unele concepte şi tehnici proprii aritmeticii, spre a putea fi implementate şi realizate fizic cât mai eficient. Această eficienţă este urmărită numai la nivel conceptual! Deci faptul că circuitele sunt realizate cu relee ca acum 50 de ani, cu tuburi electronice ca acum 40 de ani, cu tranzistori ca acum 25 de ani sa cu circuite integrate pe scară foarte largă cum sunt realizate în prezent, nu face decât să crească în mod spectaculos viteza sau capacitatea componentei electronice respective, prelucrarea informaţiei rămânând în esenţă aceeaşi.

Capitolul 0 prezintă o serie de rezultate clasice din aritmetică şi calculul propoziţiilor ce vor fi folosite în capitolele următoare. Tot aici este prezentată structura şi funcţiile unui sistem de calcul, pe de o parte ca un sistem matematic formal, iar pe de altă parte într-o abordare intuitivă descriindu-se principalele lui componente.

Capitolul 1 abordează problematica bazelor de numeraţie: reprezentarea numerelor într-o anumită bază şi conversii între diverse baze. Este pus un accent deosebit pe bazele 2, 8 şi 16, ca baze de largă utilizare în informatică. Capitolul 2 este dedicat bazelor mari de numeraţie, care au multiple aplicaţii acolo unde sunt necesare efectuarea unor calcule cu precizie foarte mare, de ordinul a sute sau mii de cifre semnificative. Sunt prezentate în acest scop o serie de consideraţii asupra algoritmilor de efectuare a celor patru operaţii în astfel de baze. Toată lumea ştie, încă din clasa I-a primară, să efectueze, cifră cu cifră, operaţia de împărţire. Oare câţi programatori de calculatoare au reuşit să scrie un program care să implementesze acelaşi algoritm?

Capitolul 3 se ocupă de codificarea şi reprezentarea informaţiei în calculator. Sunt prezentate cele mai actuale principii de reprezentare a caracterelor şi a numerelor. Capitolul 4 este destinat în mod special reprezentării numerelor întregi. Aici sunt descrise funcţiile de reprezentare binară a numerelor întregi, precum şi algoritmii specifici folosiţi în construcţia calculatoarelor pentru efectuarea celor patru operaţii. Cunoaşterea modurilor de reprezentare a informaţiei în calculator este esenţială pentru orice programator. Mulţi dintre aceştia au întâlnit situaţii în care au fost nevoiţi să "vâneze" săptămâni sau chiar luni o eroare într-un program. De foarte multe ori cauza ei a fost necunoaşterea corectă a reprezentării datelor. Stiind modurile de reprezentare a datelor, se pot face evaluări asupra nivelului de propagare a erorilor de trunchiere şi rotunire ce apar la calculele cu numere reale.

Capitolul 5 prezintă câteva metode de codificare a informaţiei prin care să se asigure detectarea posibilelor alterări de informaţii în timpul prelucrărilor. Deoarece problematica codurilor detectoare şi corectoare de erori este deosebit de vastă, aici sunt prezentate doar tehnicile folosite cel mai frecvent în construcţia calculatoarelor.

Capitolul 6 "Circuite combinaţionale" abordează problematica realizării fizice a principalelor funcţiuni a unităţii aritmetice a unui calculator, folosind cirfcuitele poartă. Se prezintă sumatorul binar, circuite de paritate, circuite selectoare, circuite multiplexoare etc.

Capitolul 7 modelează funcţionarea procesorului unui calculator. In acest scop se foloseşte mecanismul clasic al maşinilor cu trei şi cu o adresă. Maşina cu o adresă este astfel concepută încât funcţionează, principial, la fel ca cel mai performant microprocesor. Simplitatea acestor modele, care lasă la o parte toate detaliile tehnice nerelevante, permite o prezentare simplă şi accesibilă a funcţionării procesorului.

Anexele conţin texte sursă Pascal ce implementează o aritmetică ce lucrează până la baza 35, folosind până la 250 de cifre. De asemenea, sunt prezentate programe care simulează algoritmii de aritmetică binară prezentaţi în lucrare.

Lucrarea se adresează în primul rând studenţilor atât celor informaticieni, cât şi tuturor celor care au, într-un fel sau altul, contact cu informatica şi cu calculatoarele. Pentru specialiştii deja formaţi, în primul rând pentru programatori, ea se constituie într-un bun ghid în problematica abordată. Prin nivelul matematic de la care se pleacă ea este accesibilă într-o mare măsură şi elevilor din liceele de matematică - fizică, precum şi a celor din clasele speciale de informatică.