8 Novembre 2000
Sistemi di numerazione
Codici
Introduzione Max Plus II
http://www.ingce.unibo.it/documents/Didattica/MaterialeDidattico/Current/RL/IndiceMateriale.htm
http://labvisione.deis.unibo.it/~smattoccia/retilogiche.html
Macchine per l’elaborazione
dell’informazione
segnali Convertitore
analogici
A/D
segnali binari
Elaborazione
di
segnali
binari
Convertitore segnali
analogici
D/A
segnali binari
Segnali binari: esempi
levetta:
alta/bassa
tensione elettrica:
High/Low
contatto:
aperto/chiuso
cristallo liquido:
trasparente/opaco
lampadina:
accesa/spenta
corrente elettrica:
presente/assente
Variabili binarie
Bit (binary digit) - Variabile x tale che:
x  B0,1
Un bit può rappresentare un segnale binario.
Bisogna però decidere quale valore “fisico” è rappresentato dal
simbolo “matematico” 1. Esistono infatti due diverse possibilità
usualmente denominate logica positiva e negativa
I Interruttore I
0
alto
1
1
basso
0
C
0
1
logica negativa logica positiva
Contatto
aperto
chiuso
C
1
0
L
0
1
Lampada
accesa
spenta
L
1
0
Configurazioni binarie
Configurazione binaria di n bit - E’
n bit
una stringa di n 0 e 1.
Con una configurazione di n bit si
Bn-1
B2 b1 b0
n
possono codificare 2 informazioni
• n bit hanno 2n configurazioni binarie diverse.
• Una configurazione di n bit può rappresentare
i valori di n segnali binari ad un certo istante.
Es:
• Una configurazione di n bit può rappresentare
cba
i valori di un segnale binario in n istanti.
000
100
010
c
0
001
x
110
1
0 0
b
0
101
ta tb tc
011
a
0
111
Codice binario
Codice binario - Funzione dall’insieme delle 2n configurazioni
di n bit ad un insieme di M informazioni (simboli alfanumerici,
colori, eventi, stati interni, ecc.).
Condizione necessaria per la codifica: 2n  M
0 0 0 ……..0
1 0 0 ……..0
0 1 0 ……..0
2n config.
1 1 0 ……..0
0 0 1 ……..0
0 0 1 ……..1
0 1 1 ……..1
1 1 1 ……..1
z
n.u.
1
5
a
M
informazioni
?
m
Proprietà di un codice
Il codice è una rappresentazione convenzionale dell’informazione.
La scelta di un codice è condivisa da sorgente e destinazione
ed ha due gradi di libertà:
• il numero di bit (qualsiasi, a patto che sia 2n  M )
• l’associazione tra configurazioni e informazioni;
a parità di n e di M le associazioni possibili sono
N = 2n! / (2n-M)!
Codice standard - Codice fissato da norme internazionali ( de iure )
o dal costruttore di una macchina utile per tutti gli altri ( de facto ).
• L’uso di codici standard nelle unità di I/O consente di collegare
macchine fatte da costruttori diversi
Esempi: Stampanti e Calcolatori, Calcolatori e Calcolatori
Codici ridondanti e non ridondanti
Codici ridondanti
n > nmin
8
7
6
n: n° di bit
nmin =  lg2 M
non ridondanti
Codici
5
4
3
2
1
0
2
4
8
16
22
42
M: n° di informazioni
62
00 01 11 10
0
1
più
meno
segno
1
0
0
Esempi
n.u.
1
colori
Cifre decimali
Altri
29
miliardi
di
codici
a
4 bit
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
BCD
zero
uno
due
tre
quattro
cinque
sei
sette
otto
nove
1111110
0110000
1101101
1111001
0110011
1011011
0011111
1110000
1111111
1110011
7 segmenti
N.B. 1= acceso
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
uno su dieci
Sistemi di numerazione
Sistemi di numerazione
Posizionali
il valore di un simbolo dipende dalla posizione che esso
occupa all’interno della configurazione, seguendo una
legge nota. I vari sistemi di numerazione posizionale
differiscono per la scelta della base B. La base B indica
il numero di simboli usati. (Es: decimale, binario,
ottale, esadecimale)
Non posizionali
Il valore di un simbolo non dipende dalla posizione che
esso occupa all’interno della configurazione. (es:
Numeri Romani)
Come interpretare i simboli in un sistema posizionale ?
Nei sistemi posizionali, i simboli di una configurazione
possono essere interpretati come i coefficienti del seguente
polinomio [1]
n 1
V  d i  B i
i  m
B = base
di = i-esima cifra  [0..B-1]
n = numero di cifre parte intera
m = numero di cifre parte frazionaria
La virgola e’ posta tra le cifre di posizione 0 e –1.
Esempio: sistema decimale
Il numero 135.2 decimale può essere rappresentato come segue:
B = 10
n=3
m=1
base
numero cifre parte intera
numero cifre parte frazionaria
cifra
1
3
5
2
posizione
2
1
0
-1
10 2
10 1
10 0
10 -1
peso
1•10 2 + 3•101 +5•100 + 2•10-1 = 135.2
Il sistema di numerazione binario
Il sistema di numerazione binario (sistema di numerazione in base 2) si
compone di due simboli di  {0,1} e (quindi) di una base B di dimensione 2.
Ogni simbolo, denominato bit (binary digit ),
rappresentati dai simboli logici 0 e 1.
può assumere due valori
Quando una variabile assume più di due possibili valori si ricorre ad una
configurazione formata da più cifre binarie (configurazione binaria)
Essendo un sistema di numerazione posizionale, data una cifra binaria e’
possibile determinarne il valore (ad esempio) decimale interpretando i
simboli che la compongono come i coefficienti del polinomio [1].
Esempio: Quale è il valore decimale corrispondente al numero
binario 11012 ?
cifra2
1
1
0
1
peso
23
22
21
20
valore
1•8
1 •4
0 •2
1•1
11012 =
1• 23 + 1• 22 + 0• 21 + 1• 20 = 1310
Come derivare il codice Binario da quello Decimale: numeri interi
Per ottenere il valore binario, di un numero intero codificato nel
sistema decimale si procede utilizzando un metodo iterativo di
successive divisioni per 2.
2610
26
Cifra a destra
(meno significativa) 0
2
13
1
2
6 2
0
26)10 = 11010)2
3 2
1
1
Cifra a sinistra
(più significativa)
Come derivare il codice Binario da quello Decimale: numeri frazionari
Si separa la parte intera da quella frazionaria, La parte intera si calcola
come nel caso precedente La parte frazionaria si ottiene come segue:
1. Si moltiplica la parte frazionaria per 2
2. Se il numero ottenuto è maggiore di 1, si sottrae 1 e si considera come prima
cifra dopo la virgola un ‘1’.
3. Se invece il numero è nella forma 0,….. => la cifra da inserire è uno ‘0’.
4. Si ripete dal passo 1 fino a che il numero di partenza non è zero.
Esempio: 0.625
10 =0.101 2
0.625 * 2 = 1.25 1
=
0.25 * 2 = 0.5 0 =
0.5 * 2 = 1 1=
0
0, 1 0 1
Sistemi di numerazione Ottale ed Esadecimale
Quando per la rappresentazione di un numero si utilizzano molte
cifre binarie può convenire usare altri sistemi di numerazione.
I sistemi ottale ed esadecimale sono utilizzati principalmente per
rappresentare in modo più compatto i numeri binari.
I simboli del sistema Ottale sono 8:
{ 0, 1, 2, 3, 4, 5, 6, 7}
I simboli del sistema Esadecimale sono 16:
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
Cambiamenti di base
Binario -> Ottale
Per passare dalla codifica Binaria a quella Ottale, si raggruppano le cifre
binarie a gruppi di 3 (a partire da destra) e le si sostituiscono con una
cifra del sistema ottale.
Esempio : 1110010102 = 7128
Ottale -> Binario
Per passare dalla codifica Ottale a quella Binaria, si sostituisce ad ogni
cifra ottale la corrispondente codifica binaria (composta da 3 cifre).
Esempio : 3028 = 0110000102
Binario -> Esadecimale
Per passare dal codice Binario a quello Esadecimale, si raggruppano le
cifre a gruppi di 4 (a partire da destra) e le si sostituiscono con una cifra
del sistema esadecimale.
Esempio : 1001000111112 = 91F16
Esadecimale -> Binario
Per passare dal codice Esadecimale a quello Binario, si sostituisce ad
ogni cifra esadecimale la corrispondente configurazione binaria
(composta da 4 cifre).
Esempio : A7F16 =1010011111112
Esempio 1
Codifica del numero 12510 = 11111012
In codice Ottale:
1 111 101
In codice Esadecimale:
1101
111
7D
175
Esempio 2
Decimale
5
12
78
149
Binario
101
1100
1001110
10010101
Ottale
5
14
116
225
Esadecimale
5
C
4E
95
Codifica dei primi 16 numeri nei quattro
sistemi di numerazione
Decimale
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Binario
dcba
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Ottale
Esadecimale
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Relazione tra diversi i codici della tabella precedente
utilizzando le mappe di Karnaugh
Binario <-> Esadecimale
Binario <-> Decimale
dc\ba
00
01
11
10
00
0
4
12
8
01
1
5
13
9
11
3
7
15
11
10
2
6
14
10
Binario <-> Ottale
dc\ba
00
01
11
10
00
0
4
14
10
01
1
5
15
11
11
3
7
17
13
10
2
6
16
12
dc\ba
00
01
11
10
00
0
4
C
8
01
1
5
D
9
11
3
7
F
B
10
2
6
E
A
Codici
Reti di trascodifica
La codifica binaria è efficiente per svolgere operazioni aritmetiche.
Spesso però accade che all’interno di una macchina digitale vengano usati
diversi tipi di codifica per codificare le stesse informazioni.
Ad esempio per:
Facilitare l’interazione (visualizzazione di informazioni,
inserimento di dati, etc)
Efficienza (compressione di informazioni, velocità di
elaborazione, etc)
Le trasformazioni di codice sono affidati a reti denominate
TRASCODIFICATORI.
Codice A
Codice B
Trascodificatore
N1
N2
La trascodifica sul percorso dei dati
Trascodifica
Unità di
Codice elaborazione
interno
e
di memoria
Codici
esterni
Trascodifica
Il codice interno è di norma non ridondante per minimizzare il n° di bit
da elaborare e da memorizzare.
Il codice esterno è di norma ridondante, per semplificare la generazione
e la interpretazione delle informazioni, e standard, per rendere possibile
la connessione di macchine (o unità di I/O) fatte da Costruttori diversi.
Il Codice BCD (Binary Coded Decimal)
Ad ogni cifra decimale sono associati 4 bit, secondo la
tabella seguente:
Cifra Decimale
0
1
2
3
4
5
6
7
8
9
Cifra BCD
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Dalla tabella è possibile osservare che esistono delle
configurazioni non usate dal codice BCD ([1010..1111]).
Utilizzando il codice BCD si ha una corrispondenza
biunivoca fra il numero di cifre decimali e binarie.
Questo codice consente di avere dei circuiti di
visualizzazione dei numeri decimali piu’ semplici.
Esempio : La codifica del numero decimale 27 con il
codice BCD è la seguente.
27
0010 0111
Codice 1 su N
E’ un codice che associa ad ognuna delle n possibili configurazioni
una stringa di n bit avente un solo bit a 1.
Esempi:
Calcolatori tascabili: utilizzato per immettere dati attraverso la tastiera
numerica.
Negli ascensori: è utilizzato per visualizzare la posizione dei piani raggiunti e
per selezionare il piano da raggiungere (vedi figura).
Pusanti ascensore
Codifica 1 su N
1000
3
2
1
T
0100
0010
0001
Codice a sette segmenti
Codice utilizzato nei display per consentire la rappresentazone
grafica di cifre decimali (esteso anche per la rappresentazione
degli ulteriori 6 simboli del codice esadecimale).
Impiega 7 bit (a,b,c,d,e,f,g ) per codificare i 10 simboli decimali
a
f
g
1
b
abcdefg
0110000
c
e
a
f
g
b
c
e
d
a
d
9
abcdefg
1111011
f
g
b
c
e
d
Codice a matrice di punti
Impiega MxN bit per consentire la rappresentazione di simboli grafici
su una matrice di punti di M righe e N colonne.
Utilizzato per la visualizzazione dei caratteri nei monitors, nei
display dei telefonini, nei display delle calcolatrici,...
N
0000000
0000000
0011000
0100100
0100100
0111100
………..
0000000
M
Codice Gray
E’ usato per la codifica della posizione angolare di alberi
rotanti. E' un codice a distanza 1.
Angolo
0-45
45-90
90-135
135-180
180-225
225-270
270-315
315-360
ABC
000
001
011
010
110
111
101
100
Codice ASCII
Il codice ASCII è non ridondante, perchè i simboli che vengono codificati
sono in numero pari alle configurazioni ottenibili con 7 cifre binarie.
Ampiamente utilizzato in computer, stampanti,…
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
000
NUL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
LF
VT
FF
CR
SO
SI
001
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
010
!
“
#
$
%
&
‘
(
)
*
+
,
.
/
011
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
100
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
101
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
110
°
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
111
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
DEL
Esempio: Sequenza di codici impiegati in una calcolatrice tascabile
Numero Tastiera
Cifra Digitata
0
1
2
3
4
5
6
7
8
9
Codice A
Codice 1 su 10
t0 t1 t2 ……. t9
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
Codice B
Codice BCD
X3 X2 X1 X0
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Codice C
Codice 7 segm.
Abcdefg
1111110
0110000
1101101
1111001
0110011
1011011
1011111
1110000
1111111
1111011
Elaborazione e trascodifica
nell’orologio digitale
1
2
0
9
1s
Rete logica
sequenziale
con 10 stati
codificati
in BCD
tempo
Trascodifica
da BCD
a 7 segmenti
0000
1 Hz
Oscillatore
0001 0010 ….
1001 0000
Situazioni di errore nei sistemi digitali
A
10011 => 10111
B
 Malfunzionamento di uno dei blocchi
 Rumore sulle linee di trasmissione
Quale è la probabilità che si verifichi un errore ?
Detta p la probabilità che un singolo bit venga accidentalmente
alterato, si può calcolare la probabilità che in un blocco di n bit vi
siano contemporaneamente e errori:
1
n=8, p=0,05
n=16, p=0,05
n=32, p=0,05
0,8
n
n e
Pe    p e  1  p 
e
0,6
0,4
0,2
0
0
1
2
3
4
Principio di base per la rilevazione e la correzione degli errori
Il codice alla sorgente deve contenere configurazioni non utilizzate,
disposte in modo che un errore agente su di una configurazione
valida la trasformi in una non utilizzata, e quindi sia riconoscibile in
ricezione. E’ necessaria la ridondanza, ma non è sufficiente.
Distanza di due configurazioni binarie
il numero di bit per cui le due configurazioni differiscono.
Distanza minima di un codice:
la minima distanza tra due qualunque delle configurazioni del codice.
Esempi di codifica di un set di due informazioni:
on 0
off 1
on 00
off 01
on 00
off 11
codice
irridondante
cod. ridondante ma
con distanza min. 1
cod. ridondante
con distanza min. 2
0
00
01
00
01
10
11
10
11
1
Codice a rilevazione di errore (singolo) basato sul bit di parità.
Data una sequenza di n bit, si definisce bit di parità quel bit che
aggiunto alla sequenza rende pari il numero di 1.
Il bit di parità puo’ essere calcolato sfruttando le proprietà della
somma modulo 2 (OR-Esclusivo- ).
00=0
01=1
10=1
11=0
A
B


P
Errore ?
Codici a rilevazione e correzione d’errore:
Teoremi di Hamming
Un codice consente la rilevazione al più di R errori se la sua
distanza minima è R+1;
Un codice consente la correzione al più di C errori se la sua
distanza è minima 2C+1;
Esempio d’utilizzo della distanza: codice a correzione d’errore:
Codice ridondante con distanza minima 3:
ON
000
OFF
111
110
100
111
101
010
000
011
001
Altera Max Plus II
Ambiente software (CAD) per la progettazione e la simulazione di circuiti logici.
Consente di gestire la complessità attraverso l'approccio gerarchico.
La metodologia di progetto si basa sulla suddivisione del problema affrontato in
più livelli di blocchi interconnessi via via più semplici.
La progettazione assistita dal calcolatore è più rapida e affidabile della
progettazione verificata direttamente sulla realizzazione hardware.
L'ambiente di lavoro Max + Plus II consente di trasferire il progetto su circuiti
integrati programmabili detti Field Programmable Gate Array (FPGA).
Schema logico
Design Entry
Descrizione
Testuale
(VHDL)
Sintesi
(Compilazione)
Simulazione
Funzionamento
previsto ?
NO
SI
Trasferimento al Chip
(Target FPGA)
Strutturale
“Structural”
(Blocchi interconnessi)
Comportamentale
“Behavioural”
Progetto gerarchico
Un progetto gerarchico e' un progetto suddiviso su più livelli.
Ad ogni livello è associata una descrizione funzionale o una
struttura di blocchi interconnessi
I1
Livello 0
Z1
A
I2
Z2
I3
Livello 1
I1
I2
I3
Livello 2
Livello 3
B11
B2
Z1
Z2
Struttura & Comportamento
di una rete logica combinatoria
?
Tabella della verità
x1x2x3 … xn
z = F(x1,.., xn)
0 0 0 ……..0
1 0 0 ……..0
0 1 0 ……..0
1 1 0 ……..0
0 0 1 ……..0
0 oppure 1
0 oppure 1
0 oppure 1
0 oppure 1
0 oppure 1
Rete logica combinatoria
x1
x2
sintesi
x3
analisi
0 1 1 ……..1
1 1 1 ……..1
0 oppure 1
0 oppure 1
G3
Gk
xn
G2
G1
z
Mediante il principio di decomposizione è possibile scomporre la rete di
partenza in reti sempre più semplici fino ad arrivare ad una descrizione
basata esclusivamente sugli operatori logici fondamentali (AND, OR,
NOT).
AND
A
Za
Za = A·B
A
0
0
1
1
B
0
1
0
1
Za
0
0
0
1
Zo = A + B
A
0
0
1
1
B
0
1
0
1
Zo
0
1
1
1
B
OR
A
Zo
B
NOT
A
Zn
Zn = A
A
0
1
Zn
1
0
Verifica della Proprietà Associativa mediante simulazione
Ipotesi semplificativa:
Il comportamento degli operatori dell’algebra di commutazione coincide con
quello dei circuiti logici reali nell’ipotesi di considerare il ritardo di propagazione
degli operatori logici nullo.
Proprietà Associativa (I):
A+B+C = (A + B) + C
La verifica della Proprietà Associativa può essere ottenuta verificando con il
simulatore che le risposte delle due reti a tutte le possibili configurazioni di
ingresso siano uguali.
Proprietà Associativa (I):
A+B+C = (A + B) + C
Il risultato della simulazione è il seguente:
Per verificare che le uscite dei due circuiti sono
effettivamente uguali si può sfruttare l’operatore
OR-esclusivo (XOR).
Z= A  B
A B
Z
0
0
1
1
0
1
1
0
0
1
0
1
L’uscita dell’operatore XOR è ‘1’ se i due ingressi sono diversi.
Quindi può essere utilizzato per evidenziare le differenze tra i due segnali Z0 e Z1
come nello schema logico seguente.
L’uscita DIFF varrà ‘1’ se e solo se Z0 e Z1 sono diversi.
Nel caso esaminato l’uscita DIFF varrà ‘1’ se e solo se Z0 e Z1 sono diversi.
Come risulta dalla simulazione: DIFF rimane sempre a 0 con qualsiasi sequenza di simboli
di ingresso. E’ importante osservare che la verifica di un teorema con il simulatore è valida
se e solo si simula il comportamento della rete con tutte le possibili sequenze di ingresso
ammesse.
Si osservi inoltre che la proprietà associativa non vale con tutti gli operatori logici.
Ad esempio non vale per gli operatori logici NAND e NOR.
Verifica del Teorema di De Morgan mediante simulazione
Teorema di De Morgan (I):
AB = A +B
Anche la verifica del Teorema di De Morgn può essere
ottenuta verificando che le risposte delle due reti a tutte le
possibili configurazioni di ingresso sono uguali.
Risultato della simulazione:
Anche in questo caso per verificare che le uscite dei due circuiti sono
effettivamente identiche si utilizza l’operatore logico OR-esclusivo (XOR).
In questo schema l’uscita DIFF vale ‘1’ se e solo se Z0 e Z1 sono diversi.
Come risulta dalle forme d’onda le due reti producono la stessa uscita con
le stesse sequenze di ingresso.
Per esercizio: utilizzando il simulatore dimostrare la seconda forma del
teorema di De Morgan.