Test completo per Architettura degli Elaboratori

L’evoluzione del sistema digitale dipende dall’informazione di base.

numeri manipolati informazioni

Informazioni di discretizzazione e codifica decodifica

dal sistema intelleggibili

base campionamento digitale dall'uomo

I numeri sono rappresentati in NOTAZIONE POSIZIONALE. I sistemi digitali usano il codice binario (noi

usiamo il sistema decimale). I numeri vengono quindi convertiti in BIT per essere manipolati dal

sistema digitale.

CODIFICA

Processo che associa informazioni a codici binari.

Quanti BIT è necessario usare?

- n = Bit

- M = informazioni n = log M

2

Il processo di codifica tiene conto di:

1) Velocità di codifica/ decodifica

2) Impatto sul sistema digitale

CODIFICHE STANDARD

Usate per interpretare il codice binario allo stesso modo e non perdere il significato. Per i caratteri

alfanumerici esistono i CARATTERI ASCII (256 informazioni8Bit(1Byte)). Per i numeri esistono codifiche

diverse: 

- INTERI ASSOLUTI “modulo”



- INTERI RELATIVI “modulo + segno” , “complemento a 2”



- RAZIONALI “standard a virgola mobile” , “standard a virgola fissa”

CODIFICA MODULO

Es: n = 57

nBit = 6 5 4 3 2 1 0

2 2 2 2 2 2

Numero Bit 32 16 8 4 2 1

Codice 1 1 1 0 0 1

binario

57 = 111001

TAVOLA PER LE CONVERSIONI DI BASE

BASE 2 BASE 8 BASE 10 BASE 16

0000 00 0 0

0001 01 1 1

0010 02 2 2

0011 03 3 3

0100 04 4 4

0101 05 5 5

0110 06 6 6

0111 07 7 7

1000 10 8 8

1001 11 9 9

1010 12 10 A

1011 13 11 B

1100 14 12 C

1101 15 13 D

1110 16 14 E

1111 17 15 F

CODIFICA MODULO + SEGNO

- Poco usata perché è presente sia il “-0” e “+0”;

CODIFICA DEL COMPLEMENTO A 2

- Per fare il contrario bisogna calcolare l’opposto-1

0 111 7 - Se il numero da compilare è maggiore del campo di esistenza, il

0 110 6 sistema va in overflow.

0 101 5

0 100 4

0 011 3

0 010 2

0 001 1

0 000 0

1 111 -1

1 110 -2

1 101 -3

1 100 -4

1 011 -5

1 010 -6

1 001 -7

1 000 -8

CODIFICA A VIRGOLA FISSA (numeri razionali)

- Compromesso tra grandezza dei numeri e precisione

- Utile per i sistemi EMBEDDED

- Nella maggioranza dei casi il numero convertito viene approssimato.

CODIFICA A VIRGOLA MOBILE (floating point)

Codifica di riferimento: IEEE754-1985 ± m ⋅ b

n = ±e

Simboli: m=mantissa b=base e=esponente

QUALE BASE

Si voluto usare la base 2 per facilitare lo SHIFT a sx e dx della mantissa (*2 o /2).

è

CODIFICA DELLA MANTISSA

La forma normalizzata della mantissa consiste in:

- La prima cifra significativa a sx deve essere 1 (1.xxxxxxxxx)

- Codifica a virgola fissa

- Shift a sx -1 all’esponente, Shift a dx +1 all’esponente

 

Il segno della mantissa un bit da aggiungere a sx del bit più significativo (0/+,1/-)

è

CODIFICA DELL’ESPONENTE

Codifica per 127”

“eccesso ∞

00000000 -127 ≈ -



QUANTI BIT UTILIZZARE

Viene codificato per primo il segno, poi l’esponente e la mantissa. Della mantissa si omette la

parte intera (1.) e si codifica solo la parte frazionaria. I comuni sono:

più

AMPIEZZA PRECISIONE NOME IN C MANTISSA ESPONENTE

32 Singola Float 23 8

64 Doppia Double 52 11

CODICI ERRORE E NUMERI PARTICOLARI

1/0 + 31 ZERI ±0 ∞

1/0 + ESPONENTE 8 UNO + MANTISSA 23 ZERI ± Not a Number)

1/0 + ESPONENTE 8 UNO + MANTISSA CON ALMENO UN 1 NaN (

SPECIFICHE (algoritmi)

MODELLO = ambiente semplificato della realtà in cui ci si concentra sugli aspetti

fondamentali. MODELLO BOOLEANO

Modello perfetto per riuscire a compilare in binario l’algoritmo. Qualsiasi funzione può essere

ridotta agli operatori + e * .

< B , * , + , { 0 , 1 } >

n

OPERATORI FONDAMENTALI

Prodotto (AND)

0 0 0

0 1 0

1 0 0

1 1 1

Somma (OR)

0 0 0

0 1 1

1 0 1

1 1 1

MINTERMINE = coppia di valori booleani che danno come risultato 1.

ON SET = insieme di mintermini. Realizzando l’ON SET con gli operatori di base (somma di

prodotti) si può avere una funzione booleana.

OFF SET = insieme di valori che non sono mintermini.

METODO ELETTRICO PER LA RAPPRESENTAZIONE DEGLI OPERATORI LOGICI

Uso dei transistor a tecnologia CMOS:

Transistor n: in conduzione con ΔV, in interdizione senza ΔV

Transistor p: in conduzione senza ΔV, in interdizione con ΔV

Porta logica: rappresentatori elettrici degli operatori

ESEMPIO DI TRANSISTOR PER NOT:

TABELLA RIASSUNTIVA DELLE PORTE LOGICHE FONDAMENTALI

CRITERI DI OTTIMABILITA’

- Area (circuito con dimensioni inferiori)

- Ritardo (circuito più veloce)

- Potenza (economicità)

RIDURRE LE DIMENSIONI DI UN CIRCUITO

Per avere circuiti più piccoli si deve ridurre il numero degli ingressi BISOGNA RIDURRE I LETTERALI

REGOLA DI ASSORBIMENTO

Usata da tutti gli algoritmi di risoluzione. (A*B) + (¬ A*B) = B*(¬ A + A) = B*(1) = B

Come scegliere dove semplificare? Usando lo spazio booleano

trigonometrico. Quando ci sono 3 variabili infatti si possono unire i

mintermini più vicini per usare la regola dell’assorbimento. Tutti i

mintermini devono essere coperti almeno una volta.

IMPLICANTE: mintermine o insieme di mintermini (sottocubo).

IMPLICANTE PRIMO: implicante che non è contenuto in altri

implicanti (sottocubo massimo).

IMPLICANTE PRIMO ESSENZIALE: implicante primo che copre un implicante che nessun’altro

implicante primo copre. METODO DI KARNAUGH

- Non deve essere vista come una semplice tabella ma come un cilindro;

- Bisogna cercare tutti i sottocubi adiacenti;

- Non viene usato dai calcolatori perché non segue un algoritmo.

METODO QUINE-McCLUSKEY

1) TROVARE GLI IMPLICANTI PRIMI

Per trovarli senza occupare memoria eccessiva si usano i BDD.

X Y Z V O M L’andamento delle tavole di verità è infatti esponenziale (n variabili

0 0 0 0 0 n

proposizionali2 configurazioni). Con i BDD si passa da un andamento

0 0 0 1 1 M1

0 0 1 0 0 esponenziale a un andamento polinomiale, occupando meno memoria.

0 0 1 1 0 Solo in qualche caso i BDD non funzionano.

0 1 0 0 1 M4 Quando due mintermini differiscono per 1 Bit solo hanno una distanza di

0 1 0 1 1 M5 Hamming = 1. Bisogna associare i mintermini di distanza 1 , mettendo in

0 1 1 0 1 M6 ordine di Bit i mintermini e associando i mintermini (n) con quelli (n-1).

0 1 1 1 1 M7

1 0 0 0 0

1 0 0 1 1 M9 0-01 M1,M5 P1

11

S

1 0 1 0 0 -001 M1,M9 P2

1 0 1 1 1 M11 010- M4,M5

1 1 0 0 0 01-0 M4,M6

1 1 0 1 0 01-1 M5,M7

1 1 1 0 1 M14 12

S

1 1 1 1 1 M15 011- M6,M7

-110 M6,M14

00

S 10-1 M9,M11 P3

0001 M1

01 -111 M7,M15

13

S S

0100 M4 1-11 M11,M15 P4

0101 M5

02 111- M14,M15

S 0110 M6

1001 M9

0111 M7

03

S 01-- M4,M5,M6,M7 P5

21

S

1011 M11

1110 M14 -11- M6,M7,M14,M15 P6

22

S

1111 M15

04

S - La mole di dati aumenta e poi diminuisce iterazione dopo iterazione;

- Viene ridotta almeno una riga dopo ogni passaggio;

- Il ciclo finisce massimo dopo n passi, dove n è il numero di variabili;

- Se un mintermine ha un “don’t care” (-) deve associarsi per ridursi solo con un altro

mintermine con un “don’t care” nella stessa sua posizione e con un valore diverso dagli

altri.

2) TROVARE LA COPERTURA MINIMA

Ci sono delle regole da seguire per selezionare gli implicanti

P1 P2 P3 P4 P5 P6 da utilizzare:

M1 1 1 1) RIGHE ESSENZIALI

M4 1 2) DOMINANZA TRA COLONNE

M5 1 1 3) DOMINANZA TRA RIGHE

M6 1 1

M7 1 1 RIGHE ESSENZIALI

M9 1 1

M11 1 1 Bisogna cercare i mintermini che hanno un solo 1 per ogni

M14 1 riga. Così facendo si trovano gli implicanti primi essenziali.

M15 1 1

O = P5 + P6 + […]

A questo punto elimino i mintermini che sono coperti dagli implicanti

P1 P2 P3 P4 primi essenziali. Adesso per criterio di dominanza tra colonne bisogna

M1 1 1 eliminare gli implicanti che hanno meno mintermini.

M9 1 1

M11 1 1

O = P5 + P6 + P2 + P3

O = (01--) + (-11-) + (-001) + (10-1)

Nel caso che con il criterio di dominanza delle colonne non si riesca a ottimizzare, bisogna

passare al criterio di dominanza delle righe. Quest’ultimo funziona al contrario, infatti

viene eliminata la riga con il maggior numero di 1, al contrario delle colonne.

In alcuni casi non è possibile determinare un’ottimizzazione dell’area usando i criteri di

dominanza. In questo caso si parla di problemi NP (non polinomiali), dei quali non si può appunto

trovare una soluzione esatta.

IL DC-SET

Anche nell’output ci può essere un “don’t care”. Avviene solo quando:

- Non verrà mai utilizzato con determinati valori di input;

- Non è possibile praticamente ottenere quei valori di input;

La creazione del DC-SET porta ad avere un circuito con prestazioni migliori, in quanto ricopre un

area minore.

Utilizzo del DC-SET nel metodo espresso(SIS)

1. TROVARE GLI IMPLICANTI PRIMI

Il DC-SET deve essere considerato come ON-SET per aumentare la probabilità di trovare implicanti

primi più grandi, che costano meno in termini di spazio.

N.B : se viene trovato un implicante primo con soli elementi del DC-SET, non deve essere

considerato.

2. TROVARE LA COPERTURA MINIMA

Il DC-SET viene considerato come OFF-SET.