Algebre booleane e progetto logico dei calcolatori digitali/Codici: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m fix |
m refusi e modifiche minori |
||
Riga 1:
{{Algebre booleane e progetto logico dei calcolatori digitali}}
== Generalità ==
I calcolatori elettronici, per motivi di realizzazione, utilizzano una rappresentazione interna sia delle grandezze
In generale, stabilire una corrispondenza biunivoca tra i simboli di un insieme '''E<sub>1</sub>''' (insieme dei messaggi da codificare) e quelli di un insieme '''E<sub>2</sub>''' (insieme delle parole-codice) è per definizione ''codificare'' gli elementi di ''E<sub>1</sub>'' mediante gli elementi di ''E<sub>2</sub>''.
In pratica si dice ''codice'' la corrispondenza (cioè l'insieme delle regole di traduzione) tra gli insiemi ''E<sub>1</sub>'' e ''E<sub>2</sub>''. Il seguito del capitolo tratta i codici (essenzialmente binari) utilizzati per la rappresentazione delle informazioni. Seguirà una descrizione dei metodi per l'addizione, la sottrazione, la moltiplicazione e la divisione decimale.
Verrà inoltre trattata l'aritmetica [[w:numero in virgola mobile|floating-point]], i [[w:bit di parità|cheks di parità]] e i [[w:codice di Hamming|codici autocorrettori]].
=== Codice binario puro ===
Il sistema di numerazione binario, descritto nei paragrafi precedenti, costituisce uno dei procedimenti mediante i quali si può rappresentare un numero sotto forma binaria.
Si è visto però che le conversioni binario-decimali richiedono un procedimento relativamente complesse e quindi, per evitare o semplificare il più possibile questa operazione di conversione tra dati esterni e rappresentazioni interne, si ricorre in certi casi a un altro tipo di codifica binaria fornita dai codici di tipo ''B.C.D.'' (binary-coded-decimal).
=== Codici di tipo B.C.D. ===
Il principio consiste nel codificare il numero rappresentato in base decimale, cifra decimale per cifra decimale ottenendo la rappresentazione binaria cercata accostando la codifica binaria delle varie cifre. La tabella '''3.1''' fornisce un esempio di codifica delle cifre decimali: si utilizza semplicemente la loro rappresentazione in binario puro prendendo il numero minimo di simboli binari, e cioè '''4'''.
[[File:Un codice B.C.D..png]]
Mediante questo codice il numero decimale 1358 sarà rappresentato da: :::::<math>0001\quad 0011\quad 0101\quad 1000</math>
Per codificare in binario le 10 cifre da 0 a 9 sono necessarie almeno quattro posizioni binarie, che permettono di fornire 2<sup>4</sup>=16 combinazioni. Se si considera quindi un codice a quattro posizioni, si può definire un codice particolare scegliendo 10 combinazioni tra le sedici permesse per attribuirle alle cifre 0.1.2..9, in un certo ordine. Si ha che il numero dei codici di 10 cifre decimali mediante 4 posizioni binarie è dato dal numero di disposizioni di classe 10 di 16 oggetti, cioè:
:::::<math>D=\frac{16!}{6!}=2.9 10^10</math>
In pratica però non tutti i codici così formati sono effettivamente distinti, nel senso che non consideriamo distinti due codici i quali differiscano solamente per la permutazione delle variabili, e nel circuito a uno scambio di fili.
Inoltre, nel caso che tutte le variabili siano disponibili sotto le due forme complementata e non complementata (uscita dei flip-flop, per esempio) possono ancora essere considerati equivalenti due codici che differiscono solo per la complementazione di una o più delle quattro posizioni.
Comunque, malgrado ciò, il numero dei codici distinti resta dell'ordine dei milioni.
=== Codici B.C.D. pesati a 4 posizioni ===
Il codice utilizzato in precedenza (tabella 3.1) e cioè quello binario puro, è di tipo pesato. Se si pone:
:::::::<math>X=x_3 x_2 x_1 x_0 \ \ \ \ (1)</math>
per la cifra decimale, x<sub>0</sub> x<sub>1</sub> x<sub>2</sub> x<sub>3</sub> simboli binari della corrispondente parola-codice, si ha:
:::::<math>X=x_3 2^3+x_2 2^2 x_1 2^1 x_0 2^0=\sum_{i=0}^{i=3}x_i 2^i</math
:::<math>(1)\qquad X=8 x_3+4 x_2+2 x_1+x_0</math>.
Le cifre 8, 4, 2, 1 costituiscono i pesi (cioè i coefficienti da attribuire a x<sub>3</sub>, x<sub>2</sub>, x<sub>1</sub>, x<sub>0</sub> quando si ricostruisce X mediante la (1)). Il codice della tabella 3.1, detto codice (8,4,2,1) non è che un esempio fra i tanti di codice pesato a 4 posizioni. In un tale codice, ogni cifra decimale da 0 a 9 è rappresentata da una espressione del tipo
::::::<math>\sum_{i=0}^{i=3}x_i J_{P_i}\qquad\qquad (x_i=0\quad oppure\quad 1 ;i=0,1,2,3;J=0.1..9.</math>
I coefficienti P<sub>i</sub> costituiscono i '''pesi''' caratteristici del codice considerato e si usa indicare il codice mediante la successione ordinata dei P<sub>i</sub>: si avrà quindi il codice 8421, il codice 2421, ecc. Si hanno nella tabella 3.2 cinque esempi di codici a pesi positivi.
[[File:Tabella 5 codic B.C.D.png]]
Notiamo che nel codice pesato (a quattro o più posizioni) ogni gruppo decimale codificato in binario può essere facilmente convertito in un segnale analogico a dieci livelli: sommando correnti proporzionali ai pesi si ottiene una corrente proporzionale alla cifra decimale considerata.
=== Codici B.C.D. non pesati a quattro posizioni ===
Non tutti i codici sono pesati. Tra i codici non pesati a quattro
In questa rappresentazione, alla cifra decimale X (0≤x≤9) si fa corrispondere la rappresentazione binaria pura di X+3 (tabella 3.3)
[[File:ImmagineCodice B.C.D. non pesato.png]]
Questo tipo di codice è di lettura meno immediata rispetto al codice 8421 per un operatore umano e si presta meno bene alla conversione numerica analogica delle cifre decimali: ma dal punto di vista della realizzazione dei circuiti aritmetici esso possiede notevoli proprietà di simmetria: in particolare il fatto di essere ''autocomplementare''. Infatti per ogni X=(x<sub>3</sub>x<sub>2</sub>x<sub>1</sub>x<sub>0</sub>) si ha
:::::<math>C_9 (x)=9-x=(1-x_3), (1-x_2), (1-x_1),(1-x_0)</math>
ove '''C<sub>9</sub>(x)''' è il complemento a 9 di x: per ottenere il complemento a 9 di una cifra è sufficiente complementare in binario, cifra dopo cifra, la rappresentazione '''x<sub>3</sub>x<sub>2</sub>x<sub>1</sub>x<sub>0</sub> di X. Nel caso del codice 8421 ad es., le cifre binarie di '''9-x''' non dipendono in maniera così diretta da quelle di X.
=== Codici B.C.D. a più di quattro posizioni ===
Codice ''2 su 5''. Per questi tipi di codici B.C.D., si utilizzano 5 posizioni binarie per rappresentare le 10 cifre da 0 a 9.
A tale scopo si scelgono le 10 combinazioni
La tabella 3.4 dà un esempio di codice di questo tipo, corrispondente a una permutazione delle dieci parole binarie in oggetto.
Questo non è un codice pesato. La nozione di codice pesato si generalizza facilmente al caso di qualunque numero di cifre binarie. Inoltre, affinché un codice sia autocomplementare, è necessario (ma non sufficiente) che la somma dei pesi sia uguale a 9. Anche la nozione di codice ad eccesso di 3 può essere esteso a codici di eccesso di E.
== Codici a distanza unitaria ==
Si dice codice a [[w:distanza di Hamming|distanza unitaria]] un codice binario che possiede la seguente proprietà: le rappresentazioni in questo [[w:codice di Hamming|codice]] di due numeri consecutivi differiscono per una sola posizione. Se si definisce distanza di [[w:Codice di Hamming|Hammimg]] D(X,Y) fra le due parole-codice X e Y il numero di posizioni differenti, si ha che dati due numeri x<sub>{i+1}</sub> e x<sub>i</sub> aventi per parole codice
:::::::<math>[(x_{i+1}-x_i)=1]\quad \Rightarrow \quad [D(X_i,X_{i+1})=1]</math>
{| class="wikitable"
|-
Line 65 ⟶ 90:
|-
| 8 || 1000
|}
Si ha:
:::::::<math>D(X_7,X_8)=4</math>
=== Codice riflesso (Codice Gray) ===
Scrivete al di sotto di '''(b<sub>2</sub>)''' un blocco '''(b'<sub>2</sub>)'''simmetrico e completate il rango a sinistra (rango 2) con degli '''0''' di fronte a '''(b<sub>2</sub>)''' e degli '''1''' di fronte a '''(b'<sub>2</sub>)'''. Si ottiene così un blocco '''(b<sub>3</sub>)''' a 3 colonne e 2<sup>3</sup> righe.
Ripetere l'operazione di volta in volta, ecc.
Questo codice è un codice a distanza unitaria. Infatti, se un blocco '''(b<sub>n</sub>)''' è ottenuto in tale modo e possiede tale proprietà, il blocco '''(b<sub>(n+1)</sub>)''' la possiede anch'esso, perché:
: la cifra di sinistra cambia solo attorno all'asse di simmetria '''n''' mentre il resto della parola (parte destra) non cambia.
Là ove non cambia la cifra di sinistra si hanno solo i cambiamenti propri del blocco '''(b<sub>n</sub>)''' che è per ipotesi un codice a distanza unitaria.
Quindi '''(b<sub>n</sub>)''' possiede la proprietà di distanza unitaria essendo costruito a partire da '''(b<sub>1</sub>)''' per cui tale proprietà è verificata.
[[File:Codice Gray.png|thumb|Figura 3.5]]
''Formule di conversione Binario puro-Binario riflesso'': si verifica facilmente che le cifre '''B<sub>k</sub>''' in binario puro sono ottenute dalle cifre '''R<sub>k</sub>''' in binario riflesso mediante la relazione:
::::::::<math>(1)\qquad B_k=|\sum_{i=k}^{i=n}R_i|_2\qquad per.ogni.k</math>
mentre inversamente si ha:
::::::::<math>R_k=|B_{k+1}+B_k|_2</math>
''Esempio'': conversione del Binario puro 10110.
Con invarianza del valore scriviamo 010110, e operiamo come segue:
R3 = B4 XOR B3 = 1 XOR 0 = 1
R2 = B3 XOR B2 = 0 XOR 1 = 1
R1 = B2 XOR B1 = 1 XOR 1 = 0
R0 = B1 XOR B0 = 1 XOR 0 = 1
ottenendo 11101 come conversione di 10110.
Queste formule di conversione mostrano che il calcolo dei simboli di rango '''k''' fa intervenire le quantità di rango superiore, ciò implica che la conversione ha inizio dai pesi maggiori. Questo costituisce un inconveniente in pratica in quanto negli organi di calcolo in binario puro, a causa della struttura del codice binario, le operazioni il più delle volte vengono fatte a partire dai pesi più piccoli.
La formula (1) si può però mettere sotto una forma che si presta a un trattamento per ranghi crescenti:
::::::::<math>B_0=|\sum_{i=0}^{i=n}R_i|_2</math>
::::::::<math>B_1=|\sum_{i=1}^{i=n}R_i|_2=||\sum_{i=0}^{i=n}R_i|_2+R_0|_2</math>
::::::::<math>B_2=||\sum_{i=0}^{i=n}R_i|_2+|R_0+R_1|_2|_2</math>
................................................
::::::::<math>B_k=||\sum_{i=0}^{i=n}R_i|_2+|\sum_{i=0}^{i=k-1}R_i|_2|_2</math>
Nel caso che l'operazione di conversione sia eseguita con un procedimento in serie, questa formula da luogo a una semplice realizzazione: è sufficiente infatti far circolare due volte la parola in codice riflesso in un [[w:flip-flop|'''flip-flop''' di tipo '''T''']] al cui ingresso arrivano successivamente le cifre: in uscita del flip-flop di tipo '''T''' (inizialmente a zero) si avrà la somma modulo 2 dei valori d'ingresso. La prima circolazione permette la determinazione del valore '''B<sub>0</sub>''', mentre durante la seconda circolazione il '''flip-flop''' darà come uscite successive i simboli '''B<sub>k</sub>'''.
=== Utilità dei codici a distanza unitaria ===
I codici a distanza unitaria sono molto utili ogni qualvolta si vogliono evitare transizioni contemporaneamente su più posizioni. Consideriamo, ad
:::::::<math>0111\longrightarrow 0011\longrightarrow 0001\longrightarrow 0000\longrightarrow 1000</math>
Quindi gli errori, riferiti al valore finale '''1\000''' sono rispettivamente per ogni stadio pari a 1,5,7,8,0. I codici a distanza unitaria non sono quindi soggetti a questo tipo di inconveniente.
== Controllo degli errori ==
I circuiti di commutazione elettronici
[[Categoria:Algebre booleane e progetto logico dei calcolatori digitali|Codici]]
{{avanzamento|100%|9 giugno 2018}}
| |||