Algebre booleane e progetto logico dei calcolatori digitali/Codici

Generalità

I calcolatori elettronici, per motivi di realizzazione, utilizzano una rappresentazione interna sia delle grandezze sia dei simboli di tipo binario. A ogni numero o simbolo viene fatta corrispondere una parola binaria, cioè una successione di 0 e 1 definendo quindi un codice binario.

In generale, stabilire una corrispondenza biunivoca tra i simboli di un insieme E₁ (insieme dei messaggi da codificare) e quelli di un insieme E₂ (insieme delle parole-codice) è per definizione codificare gli elementi di E₁ mediante gli elementi di E₂.

In pratica si dice codice la corrispondenza (cioè l'insieme delle regole di traduzione) tra gli insiemi E₁ e E₂. 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 floating-point, i cheks di parità e i 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.

Mediante questo codice il numero decimale 1358 sarà rappresentato da:

$0001\quad 0011\quad 0101\quad 1000$

Per codificare in binario le 10 cifre da 0 a 9 sono necessarie almeno quattro posizioni binarie, che permettono di fornire 2⁴=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è:

$D={\frac {16!}{6!}}=2.910^{1}0$

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:

$X=x_{3}x_{2}x_{1}x_{0}\ \ \ \ (1)$

per la cifra decimale, x₀ x₁ x₂ x₃ simboli binari della corrispondente parola-codice, si ha:

$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}$

$(1)\qquad X=8x_{3}+4x_{2}+2x_{1}+x_{0}$.

Le cifre 8, 4, 2, 1 costituiscono i pesi (cioè i coefficienti da attribuire a x₃, x₂, x₁, x₀ 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

$\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.$

I coefficienti P_i costituiscono i pesi caratteristici del codice considerato e si usa indicare il codice mediante la successione ordinata dei P_i: si avrà quindi il codice 8421, il codice 2421, ecc. Si hanno nella tabella 3.2 cinque esempi di codici a pesi positivi.

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 posizioni, quello che viene più usato è il codice a eccesso di 3.

In questa rappresentazione, alla cifra decimale X (0≤x≤9) si fa corrispondere la rappresentazione binaria pura di X+3 (tabella 3.3)

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₃x₂x₁x₀) si ha

$C_{9}(x)=9-x=(1-x_{3}),(1-x_{2}),(1-x_{1}),(1-x_{0})$

ove C₉(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₃x₂x₁x₀ 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 binarie che hanno 2 cifre su cinque uguali a 1.

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

Generalità (caso binario)

Si dice codice a distanza unitaria un codice binario che possiede la seguente proprietà: le rappresentazioni in questo codice di due numeri consecutivi differiscono per una sola posizione. Se si definisce distanza di Hammimg D(X,Y) fra le due parole-codice X e Y il numero di posizioni differenti, si ha che dati due numeri x_{i+1} e x_i aventi per parole codice X_{i+1}, X_i e tali che x_{i+1}-x_i=1, questa proprietà è espressa dalla relazione

$[(x_{i+1}-x_{i})=1]\quad \Rightarrow \quad [D(X_{i},X_{i+1})=1]$

x	X
7	0111
8	1000

Si ha:

$D(X_{7},X_{8})=4$

Codice riflesso (Codice Gray)

Costruzione di un codice riflesso a n ranghi binari. Questo codice è rappresentato (per 4 posizioni) nella tabella 3.5 e può essere costruito come segue:

Considerate il blocco verticale (b₁) a una colonna e due righe. Scrivete al di sotto un blocco (b'₁) simmetrico rispetto all'asse b₁/b'₁. Per il rango binario a sinistra (rango 1) porre degli zeri di fronte al blocco (b₁) e degli 1 di fronte al blocco (b'₁). In tal modo si ottiene un blocco (b₂) a 2 colonne e 2² righe.

Scrivete al di sotto di (b₂) un blocco (b'₂)simmetrico e completate il rango a sinistra (rango 2) con degli 0 di fronte a (b₂) e degli 1 di fronte a (b'₂). Si ottiene così un blocco (b₃) a 3 colonne e 2³ righe.

Ripetere l'operazione di volta in volta, ecc.

Questo codice è un codice a distanza unitaria. Infatti, se un blocco (b_n) è ottenuto in tale modo e possiede tale proprietà, il blocco (b_(n+1)) 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_n) che è per ipotesi un codice a distanza unitaria.

Quindi (b_n) possiede la proprietà di distanza unitaria essendo costruito a partire da (b₁) per cui tale proprietà è verificata.

Figura 3.5

Formule di conversione Binario puro-Binario riflesso: si verifica facilmente che le cifre B_k in binario puro sono ottenute dalle cifre R_k in binario riflesso mediante la relazione:

$(1)\qquad B_{k}=|\sum _{i=k}^{i=n}R_{i}|_{2}\qquad per.ogni.k$

mentre inversamente si ha:

$R_{k}=|B_{k+1}+B_{k}|_{2}$

Esempio: conversione del Binario puro 10110.

Con invarianza del valore scriviamo 010110, e operiamo come segue:

R4 = B5 XOR B4 = 0 XOR 1 = 1

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:

$B_{0}=|\sum _{i=0}^{i=n}R_{i}|_{2}$

$B_{1}=|\sum _{i=1}^{i=n}R_{i}|_{2}=||\sum _{i=0}^{i=n}R_{i}|_{2}+R_{0}|_{2}$

$B_{2}=||\sum _{i=0}^{i=n}R_{i}|_{2}+|R_{0}+R_{1}|_{2}|_{2}$

................................................

$B_{k}=||\sum _{i=0}^{i=n}R_{i}|_{2}+|\sum _{i=0}^{i=k-1}R_{i}|_{2}|_{2}$

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 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₀, mentre durante la seconda circolazione il flip-flop darà come uscite successive i simboli B_k.

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 esempio, il passaggio da 0111 a 1000 e cioè fra cifre che pur differendo di una sola unità, comportano la variazione di tutte e quattro le posizioni della rappresentazione binaria. Il passaggio, percome sono costruiti i codificatori, non avviene simultaneamente, ma attraverso gli stati scaglionati:

$0111\longrightarrow 0011\longrightarrow 0001\longrightarrow 0000\longrightarrow 1000$

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 e in particolare quelli dei calcolatori digitali non sono dotati di perfetto grado di affidabilità: si possono generare errori dovuti a cause diverse quali elementi parassiti, perdite di alimentazione, errori casuali dati da componenti oscillanti al di fuori della tolleranza, errori sistematici dovuti al cattivo funzionamento di un componente, per usura o per guasto.