T63. Fonaments de calculadores i ordinadors

Desarrollo del tema

# FONAMENTS DE CALCULADORES I ORDINADORS

## 1. Introducció

Les **calculadores** i els **ordinadors** són màquines que processen informació mitjançant operacions lògiques i aritmètiques. Des de l'àbac fins als supercomputadors actuals, la humanitat ha buscat automatitzar el càlcul per accelerar la resolució de problemes matemàtics, científics i pràctics.

Aquest tema explora els fonaments matemàtics i tecnològics d'aquestes màquines: l'àlgebra de Boole, els circuits lògics, l'arquitectura dels computadors i els sistemes de representació numèrica.

## 2. Àlgebra de Boole

### 2.1 Definició

L'**àlgebra de Boole**, desenvolupada per George Boole (1854), és un sistema algebraic que opera amb valors lògics: **vertader (1)** i **fals (0)**.

Un **àlgebra de Boole** $(B, +, \cdot, ', 0, 1)$ és un conjunt $B$ amb dues operacions binàries ($+$, $\cdot$), una operació unària ($'$) i dos elements distingits ($0$, $1$) que satisfan:

### 2.2 Axiomes

Per a tot $a, b, c \in B$:

**Commutativitat:** $$a + b = b + a, \quad a \cdot b = b \cdot a$$

**Associativitat:** $$(a + b) + c = a + (b + c), \quad (a \cdot b) \cdot c = a \cdot (b \cdot c)$$

**Distributivitat:** $$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$$ $$a + (b \cdot c) = (a + b) \cdot (a + c)$$

**Elements neutres:** $$a + 0 = a, \quad a \cdot 1 = a$$

**Complementació:** $$a + a' = 1, \quad a \cdot a' = 0$$

### 2.3 Operacions Lògiques Fonamentals

**NOT (negació):** $\overline{A}$ o $A'$ | A | NOT A | |---|-------| | 0 | 1 | | 1 | 0 |

**AND (conjunció):** $A \cdot B$ o $A \land B$ | A | B | A AND B | |---|---|---------| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

**OR (disjunció):** $A + B$ o $A \lor B$ | A | B | A OR B | |---|---|--------| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

### 2.4 Altres Operacions

**NAND:** $\overline{A \cdot B}$ (NOT AND) - Universalment complet **NOR:** $\overline{A + B}$ (NOT OR) - Universalment complet **XOR:** $A \oplus B = A\overline{B} + \overline{A}B$ (O exclusiva) **XNOR:** $\overline{A \oplus B}$ (Equivalència)

### 2.5 Teoremes Importants

**Lleis de De Morgan:** $$\overline{A + B} = \overline{A} \cdot \overline{B}$$ $$\overline{A \cdot B} = \overline{A} + \overline{B}$$

**Idempotència:** $A + A = A$, $A \cdot A = A$

**Absorció:** $A + A \cdot B = A$, $A \cdot (A + B) = A$

**Involució:** $\overline{\overline{A}} = A$

## 3. Funcions Lògiques i Formes Canòniques

### 3.1 Taula de Veritat

Una funció booleana de $n$ variables té $2^n$ files a la seva taula de veritat i $2^{2^n}$ funcions possibles.

**Exemple:** Funció de 2 variables que detecta si almenys una entrada és 1: | A | B | f(A,B) | |---|---|--------| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

$f(A,B) = A + B$

### 3.2 Forma Normal Disjuntiva (SOP)

Suma de productes. Cada terme (minterm) correspon a una fila amb sortida 1.

$$f(A,B,C) = \overline{A}\overline{B}C + \overline{A}BC + AB\overline{C}$$

### 3.3 Forma Normal Conjuntiva (POS)

Producte de sumes. Cada terme (maxterm) correspon a una fila amb sortida 0.

### 3.4 Simplificació: Mapes de Karnaugh

Mètode gràfic per simplificar funcions booleanes agrupant 1s adjacents en grups de $2^k$ cel·les.

**Exemple:** Per $f(A,B) = \overline{A}B + AB$ ``` B=0 B=1 A=0 0 1 A=1 0 1 ``` Agrupant la columna B=1: $f(A,B) = B$

## 4. Circuits Lògics

### 4.1 Portes Lògiques

Les operacions booleanes s'implementen amb **portes lògiques**:

- **Porta NOT:** Un transistor inversor - **Porta AND:** Sortida alta només si totes les entrades són altes - **Porta OR:** Sortida alta si almenys una entrada és alta - **Porta NAND:** Universal (qualsevol funció es pot construir només amb NANDs) - **Porta NOR:** Universal - **Porta XOR:** Alta si les entrades són diferents

### 4.2 Circuits Combinacionals

La sortida depèn només de les entrades actuals.

**Semisumador (Half Adder):** Suma dos bits - Suma: $S = A \oplus B$ - Arrossegament: $C = A \cdot B$

**Sumador complet (Full Adder):** Suma dos bits més carry d'entrada - $S = A \oplus B \oplus C_{in}$ - $C_{out} = AB + C_{in}(A \oplus B)$

**Multiplexor:** Selecciona una de $2^n$ entrades segons $n$ línies de selecció.

**Decodificador:** Converteix codi binari a una de $2^n$ sortides actives.

### 4.3 Circuits Seqüencials

La sortida depèn de les entrades i de l'**estat anterior** (memòria).

**Flip-Flop SR:** Biestable bàsic amb entrades Set i Reset.

**Flip-Flop D:** Emmagatzema un bit (el valor de D quan arriba el senyal de rellotge).

**Registres:** Conjunt de flip-flops per emmagatzemar paraules de bits.

**Comptadors:** Circuits que incrementen el seu estat amb cada pols de rellotge.

## 5. Arquitectura d'Ordinadors

### 5.1 Model de Von Neumann

Proposat per John von Neumann (1945), és la base de la majoria d'ordinadors:

**Components:** 1. **Unitat Central de Procés (CPU):** - Unitat de Control (UC): Coordina operacions - Unitat Aritmètico-Lògica (ALU): Realitza càlculs 2. **Memòria:** Emmagatzema dades i programes (mateixa memòria) 3. **Dispositius d'Entrada/Sortida (E/S)** 4. **Bus de dades:** Connecta els components

**Cicle d'instrucció:** 1. **Fetch:** Obtenir instrucció de memòria 2. **Decode:** Descodificar la instrucció 3. **Execute:** Executar l'operació 4. **Store:** Emmagatzemar el resultat

### 5.2 Arquitectura Harvard

Memòries separades per a dades i instruccions. Permet accés simultani (més ràpid).

### 5.3 Components Principals

**Processador (CPU):** - Rellotge: Marca el ritme d'execució (GHz) - Registres: Memòria ultra-ràpida dins la CPU - Cache: Memòria ràpida entre CPU i RAM

**Memòria:** - **RAM (Random Access Memory):** Volàtil, accés aleatori - **ROM (Read Only Memory):** No volàtil, només lectura - **Memòria secundària:** Disc dur, SSD (persistent)

**Jerarquia de memòria:** Registres > Cache L1 > L2 > L3 > RAM > Disc (Velocitat ↓, Capacitat ↑, Cost per byte ↓)

## 6. Representació de la Informació

### 6.1 Sistemes Numèrics (repàs)

- **Binari (base 2):** $1011_2 = 11_{10}$ - **Octal (base 8):** $17_8 = 15_{10}$ - **Hexadecimal (base 16):** $FF_{16} = 255_{10}$

### 6.2 Representació d'Enters

**Sense signe:** $n$ bits representen $0$ a $2^n - 1$

**Amb signe - Complement a 2:** - Rang: $-2^{n-1}$ a $2^{n-1} - 1$ - Per obtenir $-x$: invertir bits i sumar 1 - Exemple (8 bits): $5 = 00000101$, $-5 = 11111011$

**Avantatge:** La suma funciona igual per a positius i negatius.

### 6.3 Representació de Reals: Coma Flotant

Estàndard **IEEE 754**:

$$(-1)^s \times 1.m \times 2^{e-bias}$$

**Simple precisió (32 bits):** - 1 bit de signe - 8 bits d'exponent (bias = 127) - 23 bits de mantissa

**Doble precisió (64 bits):** - 1 bit de signe - 11 bits d'exponent (bias = 1023) - 52 bits de mantissa

**Exemple:** Representar $-6.5$ - $6.5 = 110.1_2 = 1.101 \times 2^2$ - Signe: 1 (negatiu) - Exponent: $2 + 127 = 129 = 10000001_2$ - Mantissa: $10100000..._2$

**Valors especials:** - Zero: exponent i mantissa = 0 - Infinit: exponent tot 1s, mantissa = 0 - NaN: exponent tot 1s, mantissa ≠ 0

### 6.4 Errors de Representació

**Overflow:** Resultat massa gran per representar.

**Underflow:** Resultat massa petit (proper a zero).

**Error de truncament:** Per la precisió finita de la mantissa.

**Exemple:** $0.1_{10}$ no té representació exacta en binari (periòdic).

### 6.5 Codificació de Caràcters

- **ASCII:** 7 bits, 128 caràcters (anglès) - **ISO-8859-1:** 8 bits, inclou accents europeus - **Unicode (UTF-8):** 1-4 bytes, tots els alfabets

## 7. Història de la Computació

### 7.1 Precursors Mecànics

**Àbac (2500 a.C.):** Primer instrument de càlcul.

**Pascalina (1642):** Calculadora mecànica de Blaise Pascal per a sumes.

**Màquina de Leibniz (1694):** Podia multiplicar i dividir.

**Màquina analítica de Babbage (1837):** Primer disseny de computador programable. **Ada Lovelace** va escriure el primer algorisme.

### 7.2 Era Electromecànica

**Tabuladores de Hollerith (1890):** Targetes perforades per al cens dels EUA.

**Z3 de Zuse (1941):** Primer ordinador programable funcional (electromecànic).

### 7.3 Era Electrònica

**ENIAC (1946):** Primer ordinador electrònic de propòsit general. 18.000 vàlvules.

**UNIVAC (1951):** Primer ordinador comercial.

**Transistor (1947):** Substitueix les vàlvules. Més petit, ràpid i fiable.

**Circuit integrat (1958):** Múltiples transistors en un xip.

**Microprocessador (1971):** Intel 4004, tot el CPU en un xip.

### 7.4 Llei de Moore

Gordon Moore (1965) va observar que el nombre de transistors en un xip es duplica aproximadament cada 2 anys. Ha guiat l'evolució tecnològica durant dècades.

## 8. Aplicacions Didàctiques

### 8.1 ESO

- **Àlgebra de Boole:** Relacionar amb conjunts (unió = OR, intersecció = AND) - **Conversions binari-decimal:** Jocs de "endevinar el nombre" - **Portes lògiques:** Simuladors online (Logic.ly, CircuitVerse) - **Història:** Projecte sobre precursors del computador

### 8.2 Batxillerat

- **Simplificació:** Mapes de Karnaugh per a 3-4 variables - **Representació de nombres:** Complement a 2, IEEE 754 - **Errors numèrics:** Per què 0.1 + 0.2 ≠ 0.3 en ordinadors? - **Arquitectura:** Simular cicle fetch-decode-execute

### 8.3 Projectes

- Construir un sumador de 4 bits amb portes lògiques - Programar operacions booleanes en Python - Investigar l'evolució dels processadors

## 9. Conclusions

Els fonaments dels ordinadors es basen en l'àlgebra de Boole i la teoria de circuits. L'arquitectura de Von Neumann ha dominat el disseny d'ordinadors durant dècades. La representació binària de la informació, tot i ser eficient, introdueix limitacions i errors que cal comprendre. L'estudi d'aquests fonaments permet entendre com les màquines realitzen càlculs i per què apareixen certs comportaments inesperats en programes numèrics.