Test completo per Architettura degli Elaboratori
Anteprima
ESTRATTO DOCUMENTO
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 informazioni8Bit(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
proposizionali2 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.
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher martini.enrico1997 di informazioni apprese con la frequenza delle lezioni di Architettura degli elaboratori e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Verona - Univr o del prof Fummi Franco.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato