Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (a): differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
ortografia |
wikifico |
||
Riga 1:
{{Algebre booleane e progetto logico dei calcolatori digitali}}
== Addizionatore e sottrattore binario ==
Siano le variabili '''x<sub>i</sub>''', '''y<sub>i</sub>''', '''r<sub>i</sub>''', '''s<sub>i</sub>''' e '''r<sub>{i+1} </sub>''' definite nel cap.2 Parte I<sup>a</sup>, a proposito della somma e della sottrazione di due numeri binari.
Facendo la convenzione di rappresentate '''l'i''' aritmetico mediante l''''!''' della logica booleana, lo '''0''' aritmetico mediante lo '''0''' booleano, e utilizzando gli stessi simboli di variabile per i due tipi di grandezza - si possono estrarre dalle tavole del Cap. 2 Parte I le- tavole della verità che definiscono - per un singolo rango la somma e la sottrazione.
[[File:Truth Table of Half Adder.png|right]]
=== Semiaddizionatore (half-adder) ===
Questo circuito è un blocco fondamentale costituito da 3 porte di '''AND''' ed una porta di '''OR'''. Il suo funzionamento viene stasabilito mediante la adiacente tavola della verità
[[File:Half-Adder logic diagram.png|right]]
Le due funzioni booleane descritte dalla tavola sono:
::::<math>S_i=Y_i \bar X_i+X_i \bar Y_i=X_i \oplus Y_i</math>
:::::<math>r_{i+1}=X_i\cdot Y_i</math
Il diagramma logico di un semi addizionatore sarà quindi quello evidenziato a lato
Il circuito che genera la funzione '''S<sub>i</sub>''' viene anche impigato come porta di '''⊕''' (or esclusivo)
[[File:Full Adder Truth Table (2).png|right]]
=== Addizionatore elementare (Full Adder) ===
Il processo della somma binaria consiste in questo caso nella addizione contemporanea delle due variabili '''X<sub>i</sub>''' e '''Y<sub>i</sub>''' edel riporto '''r<sub>i</sub>''' ottenuto durante la somma parziale precedente . La tabella della verità relativa '''S<sub>i</sub>''' e '''r<sub>i+1</sub>''' sarà quindi quella qui adiacente:
;Forma canonica:
::::<math>S_i=\bar X_i\bar Y_i r_i+\bar X_i Y_i \bar r_i+X_i \bar Y_i \bar r_i \bar r_i+X_i Y_i r_i</math>
Per '''S<sub>i</sub>''', si può scrivere:
:::::<math>=\overline {(X_i\oplus Y_i)}+(X_i\oplus Y_i)\bar r_i</math>
:::::<math>=(
:::::<math>=X_i
La funzione '''r<sub>i+1</sub>''' essere semplificata:
::::<math>r_{i+1}=\bar X_i Y_i r_i+X_i \bar Y_i r_i+X_i Y_i \bar r_i+x_i Y_i r_i+X_i Y_i r_i+X_i Y_i r_i</math>
:::::<math>=(\bar X_i+X_i)Y_i r_i+(\bar Y_i+ Y_i)X_i r_i+(r_i +\bar r_i)X_i Y_i</math>
:::::=<math>=X_i Y_i+Y_i r_i+r_i X_i</math>
:::::<math>=X_i Y_i\oplus Y_i r_i\oplus r_i X_i</math>
Per comodità , possiamo scrivere ulteriormente:
::::<math>S_i=(X_i\oplus Y_i)\oplus r_i</math>
::::<math>r_{i+1}=X_i Y_i(r_i +\bar r_i)+r_i(X_i \bar Y_i+\bar X_i Y_i)</math>
:::::<math>=X_i Y_i+r_i(X_i\oplus Y_i)</math>
Quindi '''S<sub>i</sub>''' e '''r<sub>i+1</sub>''' possono essere ottenuti mediante due reti: la prima sarà '''<math>X_i\oplus Y_i</math>''' e '''<math>X_i Y_i</math>''', la seconda '''<Math>(X_i\oplus Y_i)\oplus r_i</math>''' e '''<math>(X_i\oplus Y_i) r_i</math>'''.
[[File:Full Adder with 3 inputs.png|right]]
Ciascuna di queste reti è un semiaddizionatore.
Connettendole come da figura ed utilizzando una porta supplementare '''OR''' per formare '''<math>r_{i+1}</math>''', si ottiene un addizionatore elementare a tre ingressi '''<math>X_i, Y_i, r_i</math>'''.
Mediante altre trasformazioni algebriche, si possono ovviamente ottenere altri schemi.
Per esempio, considerando le espressioni:
::::<math>S_i=\bar X_i \bar Y_i r_i+\bar X_i Y_i \bar r_i+X_i \bar Y_i \bar r_i+X_i Y_i r_i</math
::::<math>r_{r+1}=X_i Y_i+X_i r_i+X_i r_i</math>
[[File:Full Adler with 3 entries.png|right]]
si avrà il seguente schema:
Line 62 ⟶ 90:
L'addizionatore elementare che realizza le funzioni '''S<sub>i</sub>''' e '''r<sub>i+1</sub>''', può essere utilizzato sia in un addizionatore in serie che in un addizionatore in parallelo.
[[File:Addizionatore in serie.png|right]]
=== Addizionatore in serie-Addizionatore in parallelo ===
Nell'addizionatore in serie le cifre degli operandi '''X''' e '''Y''' (X<sub>i</sub>,Y<sub>i</sub>) si presentano negli istanti successivi '''i'''.
Una memoria '''M''' (per esempio una linea di ritardo con ritardo di un bit) conserva il riporto '''r<sub>i+1</sub>''', elaborato all'istante '''i''', fino all'istante '''i+1''' (vedi figura)
[[File:Parallel Adder Logic Diagram (2).png|right]]
Nell'addizionatore in parallelo, le cifre '''X<sub>i</sub>''' e '''Y<sub>i</sub>''' '''(i=0,...,n)''' degli operandi '''X''' e '''Y''' si presentano in entrata in parallelo (simultaneamente
Con '''n+1''' cifre, il circuito possiede '''2(n+1)''' ingressi '''(X<sub>i</sub>,Y<sub>i</sub>)''' e '''n+1''' uscite.
Nella versione più classica (forma iterativa) esso possiede '''n+1''' blocchi o '''stadi''': uno stadio di rango '''0''' che è un semiaddizionatore ed '''n''' stadi costituiti da addizionatori elementari del tipo descritto in (2.1.2) (rango i>0). Il riporto elaborato al rango '''i''' (r<sub>i+1</sub>) costituisce uno degli ingressi dello stadio '''i+1'''.
Nella figura posta accanto '''n=3'''.
Si noterà che la lunghezza massima che i segnali devono attraversare è di '''n+1''' stadi , ossia di '''2(n+1)''' livelli se i blocchi sono appunto a 2 livelli.
Per certe condizioni (X=2<sup>n+1</sup>-1, Y=1 per es.) la lunghezza di propagazione del riporto è effettivamente uguale a questo valore..
Un addizionatore in parallelo completa l'addizione in un tempo che è determinato dal tempo di arrivo di un digit più il tempo di propagazione dell'eventuale riporto, mentre un addizionatore seriale richiede '''n''' intervalli di tempo (digit times). Quindi l'addizionatore parallelo ha il vantaggio di essere veloce, mentre quello seriale ha il vantaggio di avere meno circuiti.
[[File:Tabella della verità per la sottrazione binaria.png|right]]
Mediante la tabella della verità affiancata si può definire il funzionamento di un blocco chiamato '''semi-sottrattore (half-subtractor)''' binario.Si fa l'ipotesi che il minuend0 '''X'''e il sottraendo '''Y'''siano positivi e tali che '''X≥Y'''.
Le equazioni booleane che definiscono la differenza e la ritenuta in una sottrazione binaria sono dunque:
::::<math>d_i=\bar X_i Y_i+X_i \bar Y_I=X_i \oplus Y_i</math
::::<math>r_{i+1}=\bar X_i Y_i</math>
Line 92 ⟶ 132:
[[File:TrueTable for Full Subtractor.png|right]]
Solo la seconda equazione differisce da quella ottenuta per l'addizione: essa si può dedurre da quella del par.2.1.1 sostituendo '''<math>X_i</math>''' con '''<math>\bar X_i</math>'''.
Un semisottrattore genera la differenza '''d''' e la ritenuta '''r<sub>i+1</sub>''' mediante il minuendo '''X<sub>i</sub>''' e il sottraendo '''Y<sub>i</sub>'''.
Volendo invece ottenere la differenza '''d<sub>i</sub>'''e la ritenuta '''r<sub>i+1</sub>''' considerando il sottraendo '''X<sub>i</sub>''', il minuendo '''Y<sub>i</sub>''' e la ritenuta '''r<sub>i</sub>''' del passo precedente, si ottiene la tabella della verità annessa al fianco.
Le equazioni booleane corrispondenti sono:
::::<math>d_i=\bar X_i \bar Y_i r_i+\bar X_i y_i \bar r_i+X_i \bar Y_i \bar r_i+X_i Y_i r_i=X_i\oplus Y_i\oplus r_i</math>
::::<math>r_{i+1}=\bar X_i \bar Y_i r_i+\bar X_i Y_i \bar r_i+\bar X_i Y_i r_i+X_i Y_i r_i=\bar X_i Y_i+r_i(\bar X_i\oplus Y_i)</math
Uno dei possibili modi di realizzare un sottrattore elementare completo consiste nel considerare due semisottrattori.
Line 112 ⟶ 148:
[[File:Full Subtractor logic diagram.png|center]]
Il semi-sottrattore ed il sottrattore completo possono essere utilizzati per costruire sottrattori in serie e in parallelo, sempre con l'ipotesi xhe '''X''' e '''Y''' siano senza segno e con '''X≥Y'''.
In seguito vedremo la realizzazione della sottrazione mediante l'uso dei complementi ad 1 e a 2. Infatti un circuito costruito per sommare numeri rappresentati con segno e modulo è molto più completo di quello che utilizza una rappresentazione complementata di numeri negativi.
== Circuito di complementazione (ad 1) ==
Sia il numero '''X=X<sub>n-1</sub> X<sub>n-2</sub>...X<sub>0</sub>''', il suo complemento ad 1 è il numero '''<math>C_1 (X)</math>''' che ha per rappresentazione '''<math>\bar X</math>''':
Line 139 ⟶ 176:
:::::<math>S=\begin{matrix}\overbrace{1 1 1...1 1}^{n\ cifre}\end{matrix}=2^n - 1</math>
Un cirfcuito complementatore (ad 1) converte un numero binario avuto in input in un output che ne è il complemento ad 1.
Un complementatore può essere costruito in modo da ricevere un input seriale oppure uno in parallelo.
[[File:Complementatori seriale e in parallelo.png|right]]
Line 147 ⟶ 186:
::::::<math>\bar X=X\oplus 1</math>
se la variabile di controllo è '''P=0''' in output si ha la stessa variabile di ingresso '''X'''.
La figura a sinistra delle due mostra un complementatore seriale nel cui '''input''' X compare una sequenza binaria rappresentante un numero binario.
Questo circuito può essere usato come complementatore parallelo: è necessario allora avere un numero di circuiti pari al numero di bit del numero binario.
L'altra figura rappresenta un complementatore in parallelo: i due output del Flip-Flop '''X''' costituiscono i due inputs. Ovviamente ci devono essere tanti di questi circuiti quanti sono i bits del numero binario.
Questo circuito a sua volta può essere utilizzato come complementatore seriale: sarà allora richiesto un solo circuito e lo stato del Flip-Flop cambierà ad ogni digit time generando così una sequenza binaria rappresentante il nujmero binario.
Sia il numero binario '''X''' si chiama complemento vero o complemento a 2, la quantità <math>C_2(X)=2^n - X</math>.
Si ha dunque:
:::::<math>C_2(X)=C_1(X)+1</math>
::: <math>con \qquad\qquad X=(X_{n-1} X_{n-2}...X_k...X_1 X_0)</math>
::::::: <math>
Aggiungendo '''1''' a '''C<sub>1</sub>(X) si ottiene:
:::::<math>
Ricordando come si esprimono in algebra booleana le somme e i riporti di una addizione della aritmetica booleana, si ha:
:::::<math>Y_0=\bar X_0\oplus 1\qquad\qquad\qquad</math>
:::::<math>Y_1=\bar X_1\oplus r_1=\bar X_1\oplus \bar X_0\qquad\qquad r_2=\bar X_\ \bar X_0</math>
:::::<math>X_2=\bar X_2\oplus r_2=\bar X_2\oplus \bar X_1\bar X_0\qquad\qquad r_3=\bar X_2 \bar X_1 \bar X_0</math>
:::::::::.
:::::::::.
:::::<math>Y_k=\bar X_k\oplus \prod_{i=0}^{i=k-1} \bar X_i=X_k\oplus 1\oplus \prod_{i=0}^{i=k-1}\bar X_i=</math>
:::::<math>X_k\oplus \overline {(\prod_{i=0}^{i=k-1} \bar X_i)}=X_k\oplus \sum_ {i=0}^{i=k-1}X_i</math>
Ponendo:
:::::<math>Z_k=\sum_{i=0}^{i=k-1}X_i</math>
si ottengono le seguenti equazioni di un circuito complementare a 2 seriale:
[[File:Complementatore a 2 di tipo seriale.png|right]]
:::::<math>\begin{cases}Y_k=X_k\oplus Z_k\\Z_{k+1}=Z_k+X_k\end{cases}</math>
Tenendo presente l'equazione booleana di un Fip-Flop SR, si può pensare di realizzare l'equazione <math>Z_{k+1}=Z_k+X_k</math> mediante un '''SR''' con l'ingresso '''R''' sempre mantenuto a '''0''' e con lo stato interno iniziale '''Z<sub>0</sub>=0'''.
Nella figura è descritto un complementatore a 2 di tipo seriale per numeri binari senza segno.
[[File:Complementatore a 2 seriale per numeri binari con segno.png|right]]
Nella seguente figura è descritto invece un complementatore seriale a 2 per numeri binari con segno: la sua caratteristica è determinata dal fatto che se il numero è negativo (bit del segno uguale ad 1), esso esce in output complementato a 2, se l'input invece è positivo , il numero uscirà nella forma vera.
Si fa l'assunzione che il bit del segno arrivi come primo bit nella sequenza di input: gli seguiranno i bits delle cifre significative in ordine di peso crescente.
Nel frattempo un segnale di controllo del segno selezione la '''via c'''.
Se il bit del segno è '''0''' (numero positivo), il Flip-Flop '''S''' rimane nello stato '''0''' e i bit successivi del numero passano attraverso la '''via a''' ed appaiono in output.
Se il bit del segno è '''1''' (numero negativo), il Flipo-Flop '''S''' viene messo nello '''stato 1'''. La '''via a''' viene interdetta e la '''via b''' viene permessa.
I bits successivi del numero passeranno allora per la '''via b''' e verranno complementati nella maniera descritta per numeri senza segno.
Osservando la figura del diagramma logico del complementate a 2 di tipo seriale si verifica la regola pratica per ottenere il complemento a 2 (detto anche complemento vero) di un numero binario. Essa consiste nel lasciare inalterati tutti gli zeri prima del primo '''1''' incontrato nel risalire la parola '''X''' partendo dai pesi più deboli e procedendo verso quelli più forti, nel lasciare inalterato questo '''1''', e nel complementare tutte le cifre a sinistra di questo '''1'''.
:::<math>Esempio\ \ \ \ X=0110100</math>
::::::<math> C_2(X)=1001100</math>
Se consideriamo il circuito dell'accennata figura notiamo che il Flip-Flop interviene in due porte di AND: in una i bits di '''X''' entrano in forma negata e nell'altra no.
Ora, consideriamo un input seriale a partire dai pesi più deboli, i bit '''0''' non cambiano lo stato iniziale del Flip-Flop la cui uscita Z=0 interdcde la pota AND relativa negata dei bits di X, e questo fino all'arrivo del primo bit 1, dopo il quale lo stato del Flip-Flop cambia; si ha la situazione inversa della precedente , in cui l'uscita <math>\bar Z=0</math> interdisce la porta AND relativa ai bits di X.
Si ha inoltre:
:::::<math>X+C_2(X)=2^n=0\ mod\ 2^n</math>
Si vede quindi che, facendo le operazioni modulo 2<sup>n</sup>, si ottengono gli stessi risultati sia operando con '''X-Y''' che con '''X+C<sub>2</sub>(Y).
Quanto affermato sopra, è già stato dimostrato con l'ausilio del calcolo dei residui nel Cap.2 parte I.
Dimostriamo ora la veridicità mediante l'algebra di Boole.
Poniamo:
:::::<math>C_2(Y)=Y'=(Y'_{n-1}Y'_{n-2}...Y'_0)</math>
Le operazioni '''X-Y''' e '''X+C<sub>2</sub>(Y)=X+Y'''' sono definite in forma ricorrente dalle equazioni: :::::<math>(X-Y)\ \ \ \begin{cases}S_k=X_k\oplus Y_k\oplus r_k\\r_{k+1}=\bar X_kY_k\oplus Y_kr_k\oplus \bar X_kr_k\end{cases}</math>
:::::<math>(X+Y')\ \ \ \begin{cases}S'_k=X_k\oplus Y'_k\oplus r'_k\\r_{k+1}=X_kY'_k\oplus Y'_kr'_k\oplus X_kr'_k\end{cases}</math
Supponiamo che al rango '''k''' si abbia '''S'<sub>k</sub>=S<sub>k</sub>''':
Si ha allora:
:::::<math>X_k\oplus Y_k\oplus r_k=X_k\oplus [Y_k\oplus (\sum_{i=0}^{i=k-1}Y_i)]\oplus r'_k</math>
cioè
:::::<math>r'
Si deduce immediatamente:
:::<math>
:::<math>X_k Y_k\oplus Y_k r_k\oplus X_k r_k\oplus (\sum_{i=0}^{k-1}Y_i)(Y_k\oplus r_k\oplus 1)</math>
:::<math>r'_{k+1}=r_{k+1}\oplus Y_k \oplus (\sum_{i=0}^{k-1}Y_i)(Y_k\oplus r_k \oplus 1=</math>
:::<math>r_{k+1}[Y_k \oplus Y_k (\sum_{i=0}^{k-1}Y_i)\oplus (\sum_{i=0}^{k-1}Y_i]\oplus r_k(\coprod_{i=0}^{k-1}\bar Y_i)=</math>
:::<math>r_{k+1}\oplus (\sum _{i=0}^{i=k}Y_i)\oplus r_k (\coprod_{i=0}^{k-1}\bar Y_i)</math>
Consideriamo l'ultimo termine: si ha:
:::<math>r_k(\coprod_{i=0}^{k-1}\bar Y_i)=(\bar x_{k-1}Y_{k-1}\oplus Y_{k-1}r_{k-1}\oplus \bar x_{k-1}r_{k-1})(\coprod _{i=0}^{k-1} \bar Y_i)=</math>
:::<math>\bar X_{k-1}\bar Y_{k-1}r_{k-1}(\coprod_{i=0}^{k-2}\bar Y_i)</math>
e quindi iterando il procedimento, si ha:
:::<math>r_k(\coprod _{i=0}^{k-1}\bar Y_i)=(\coprod_{i=0}^{k-1} \bar X_i \bar Y_i) r_0=0\ \ \ \ in\ quanto\ r_0=0</math>
Da cui:
:::<math>r'_{k+1}=r_{k+1}\oplus (\sum_{i=0}^{i=k}Yi)</math>
di conseguenza
:::::<math>S'_{k+1}=S_{k+1}</math>
E quindi se '''S'<sub>k</sub>=''' '''S<sub>k</sub>''' si ha '''S'<sub>k+1</sub>=S<sub>k+1</sub>'''
Poiché '''S'<sub>0</sub>=S<sub>0</sub>=(X<sub>0</sub>⊕Y<sub>0</sub>)''', la relazione di uguaglianza sussiste per ogni rango K: S'<sub>k</sub>=S<sub>k</sub>.
[[File:Complementatore a 2 in parallelo.png|right]]
Per quanto riguarda un complementatore a 2 parallelo, esso consiste in '''n''' complementatori ad 1, in un addizionatore parallelo ad '''n''' bit e in un Flip-Flop '''C'''. Con '''n''' si è indicato il numero dei bit che compongono il numero binario. Il bit del segno passa inalterato nel circuito. Per ottenere il complemento a 2 del numero, se ne trova prima il complemento ad 1 e quindi si somma 1 al bit meno significativo '''[C<sub>2</sub>(X)=C<sub>1</sub>(X)+1]'''
L'addizione di '''1''' al bit meno significativo la si ottiene ponendo inizialmente il '''Flip-Flop C''' ello stato '''1'''1; in tal modo questa operazione consiste nell'addizionare due addendi di cui uno nullo, ma con un riporto iniziale di '''1''', e quindi sostanzialmente ogni adder dell'addizionatore parallelo lavora com un '''half-adder'''.
== Controlli di parità ==
Si chiama '''Bit di Parità''', una cifra binaria che si aggiunge talvolta ad una parola binaria in modo da scoprire eventuali errori di trasmissione.
Data una parola '''X''' ad '''n''' posizioni:
:::::<math>X=X_n X_{n-1}....X_1</math>
Si usa trasmettere la parola ad '''n+1''' posizioni :
:::::<math>X'=X_n X_{n-1}....X_1 P</math>
dove '''P''' è tale che il numero totale degli '''1''' della parola '''X'''' sia pari.
Esempio:
::::::<math>\begin{cases}X=1 1 0 1 0 1 1 0\\X'=1 1 0 1 0 1 1 0 1\end{cases}</math>
::::::<math>\begin{cases}X=1 0 0 1 0 1 1 0\\X'=1 0 0 1 0 1 1 0 0\end{cases}</math>
Si piò fare un'altra convenzione e definire un bit di disparità, tale che il numero totale degli 1 sia dispari.
Con questa nuova convenzione , non vi può essere un numero '''X'''' formato da zeri.
Questa combinazione risulta essere proibita, e la sua presenza può servire a mettere in evidenza certi difetti di funzionamento (come per esempio un difetto di alimentazione).
Si ha la corrispondenza:
:::::<math>\begin{cases}P=1\ \ \ \ \sum_{i=1}^n X_i \ \ \ e'\ dispari \\P=0\ \ \ \ \sum_{i=1}^n X_i \ \ \ e'\ pari\end{cases}</math>
e quindi:<br>
::::::<math>P=|\sum_{i=n}^n X_i|_2</math
dove '''P''' e '''X<sub>i</sub>''' sono variabili aritmetiche. Con la convenzione già usata, considerando '''P''' e '''X<sub>i</sub>''' variabili booleane, si ha:
:::::<math>P=X_i\oplus X_2\oplus....\oplus X_i\oplus....\oplus X_n=\oplus \sum_{i=1}^n X_i</math>
Il bit di parità indica gli errori di trasmissione su di un numero dispari di posizioni.
Come circuito di controllo, si può pensare un Flip-Flop di tipo '''T''' dove lo stato interno '''Q<sub>0</sub>''' iniziale è posto a zero.
:::::<math>P=Q_0\oplus\sum_{i=1}^n x_i</math>
=== Addizione di 2 numeri con bit di parità ===
Consideriamo 2 numeri binari '''X''' e '''Y''' ad '''n''' cifre:
::::<math>\begin{cases}X=x_{n-1} x_{n-2}...x_0 \ \ \ P_0\\Y=y_{n-1} y_{n-2}...y_0\ \ \ P_y\end{cases}</math>
alle '''n''' cifre siano stati aggiunti i bit di parità '''P<sub>x</sub>''' e '''P<sub>y</sub>''':
::::<math>\begin{cases}P_x=\oplus \sum_{k=0}^{k=n-1} x_k\\P_y=\oplus \sum_{k=0}^{k=n-1} y_k\end{cases}</math>
chiamiamo '''P<sub>s</sub>''' la cifra di parità '''x+y'''.
Calcoliamo l'espressione di '''P<sub>s</sub>''' mediante le equazioni che danno la somma '''s<sub>k</sub>''' e il riporto '''r<sub>k+1</sub>''' di rango '''K''' in funzione di '''x<sub>k</sub>, y<sub>k</sub>, r<sub>k</sub>'''.
Poniamo:
:::::<math>S=s_{n-1} s_{n-2}....s_0</math>
(Supponiamo quindi che '''S''' sia anch'essa di '''n''' cifre).
Si ha allora:
:::::<math>P_s=s_{n-1}\oplus s_{n-2}\oplus....\oplus s_0=\oplus \sum_{k=0}^{n-1}s_k</math>
:::::<math>=\oplus \sum_{k=0}^{n-1} (x_k\oplus y_k \oplus r_k)</math>
:::::<math>=(\oplus \sum_{k=0}^{n-1} x_k)\oplus (\oplus \sum _{k=0}^{n-1} y_k)\oplus (\oplus \sum _{k=0}^{n-1}r_k)</math>
:::::<math>=P_x\oplus P_y\oplus (\oplus \sum_{k=0}^{n-1} r_k) \ \ \ \ \ \ \ \ \ (1.7.1)</math>
La cifra di parità '''P<sub>s</sub>''' di '''S=X+Y''' è quindi la somma modulo 2 delle cifre dparità '''P<sub>x</sub>''' e '''P<sub>y</sub>'''di '''X''' e '''Y''' e dei riporti '''r<sub>k</sub> (k=0, ..., n-1).
:''Nota''-Quando la cifra '''P<sub>s</sub>'' calcolatamediane la somma effettivamente ottenuta e la cifra '''P<sub>s</sub>''' calcolata mediante la (1.7.1) sono differenti, vi è errore. Poiché tutte le operazioni aritmetiche in un calcolatore sono effettuate, in ultima analisi, mediante addizioni , il procedimento sopra esposto può essere, in teoria, esteso come verifica di una qualunque operazione aritmetica.
== Circuito per il confronto di 2 numeri binari ==
Il problema che ci si propone di risolvere è quello di effettuare una operazione di confronto tra due numeri binari ad n bit in modo da determinare quale dei due ha valore maggiore in modulo.
In un primo tempo costruiremo un comparatore seriale nel cui input arrivano i bits da confrontare secondo la sequenza determinata dal crescere del rango. Sia dunque la parola binaria:
:::::<math>X=x_{n-1}x_{n-2}....x_k.....x_1x_0</math>
chiameremo con '''X(k)''' la parola tronca formata dalle '''k+1''' cifre di peso più debole (ranghi da 0 a k).
[[File:Variabile binaria.png|right]]
[[File:Tabella riassuntiva delle diffrenze.png|right]]
:::::<math>X(k)=x_k x_{k-1} ....x_0</math>
Consideramo quindi due numeri '''X''' e '''Y''' e la variabile binaria definita dalla corrispondenza
Da queste condizioni segue che:
::::::::::::<math>Se \ \ \ \ \ \ x_k=y_k</math>
::::::::::::<math>Allora \ \ \ S_k=S_{k-1}</math>
d'altra parte, se '''x<sub>k</sub>≠y<sub>k</sub>''', la diseguaglianza tra '''x<sub>k</sub>''' e '''y<sub>k</sub>''' da una parte, '''x(k)''' '''y(k)''' sono definite nello stesso verso.
quanto detto può, può essere riassunto dalla tabella seguente.
Si ha dunque:
:::<math>S_k=\bar S_{k-1} x_k \bar y_k+S_{k-1}\bar x_k\bar y_k+S_{k-1}x_k\bar y_k+S_{k-1}x_k y_k=</math>
:::<math>(x_k\bar y_k+x_k y_k S_{k-1})+(\bar x_k \bar y_k S_{k-1}+x_k \bar y_k)=</math>
:::<math>x_k \bar y_k+x_k S_{k-1}+x_k \bar y_k+\bar y_k S_{k-1}=x_k \bar y_k+x_k S_{k-1}+\bar y_k S_{k-1}</math>
Si riconosce per '''S<sub>k</sub>''' l'espressione della ritenuta ottenuta durante l'operazione '''Y-X'''.
:::<math>S_k=\bar S_{k-1} x_k \bar y_k+S_{k-1}\bar x_k\bar y_k+S_{k-1}x_k\bar y_k+S_{k-1}x_k y_k=</math
Si vede quindi che '''S<sub>n-1</sub>=1''' quando l'operazione '''Y-X''' produce una ritenuta al rango '''n-1''', situazione che si deve verificare quando '''x>y'''. Per confrontare i due numeri però non è necessaqrio determinare la differenza : infatti è sufficiente il valore '''S<sub>n-1</sub>''' della ultima ritenuta di questa differenza. Per costruire il circuito, conviene però mettere la equazione.
:::<math>S_k=\bar S_{k-1} x_k \bar y_k+S_{k-1}\bar x_k\bar y_k+S_{k-1}x_k\bar y_k+S_{k-1}x_k y_k</math
sotto la forma seguente:
:::<math>S_k=\bar S_{k-1} x_k \bar y_k\oplus S_{k-1}\bar x_k\bar y_k\oplus S_{k-1}x_k\bar y_k\oplus S_{k-1}x_k y_k=</math
:::<math>\bar S_{k-1} x_k \bar
:::<math>
:::<math>(\bar S_{k-1}x_k\bar y_k\oplus S_{k-1}\bar x_ky_k)\oplus S_{k-1}=</math>
:::<math>(\bar S_{k-1}x_k\bar y_k + S_{k-1}\bar x_ky_k)\oplus S_{k-1}</math>
[[File:Circuito per il confronto di due numeri binari..png|right]]
Per realizzare questo circuito, è sufficiente considerare un '''Flip-Flop''' di tipo '''T''' in cui '''S<sub>k-1</sub>''' rappresenta lo stato interno ed il resto dell'espressione costituisce l'ingresso del '''Flip-Flop''' mentre l'uscita determina la funzione di confronto tra i due numeri '''X''' e '''Y'''.
L'operazione realizzata da l circuito ha termine ovviamente quando in input si sono presentati tutti gli '''n''' bits di ''X''' e '''Y'''.
[[File:Tabella di un comparatore seriale.png|right]]
Supponiamo invece che i bits di '''X''' e '''Y''' si presentino nell'ordine determinato dai pesi decrescenti: il circuito in questo caso sarà molto più semplice in quanto non ci sarà bisogno di utilizzare un circuito sequenziale.
La tabella di un comparatore seriale in cui l'input sia costituito da bits di peso decrescente sarà come quella affiancata.
[[File:Comparatore sertiale a peso decrescente.png|right]]
Da tale tabella si deduce il circuito a lato.
Appena '''x_k≠y_k''' si arrestano i confronti.
=== Comparatore parallelo ===
Un comparatore parallelo sarà costituito da '''n''' circuiti comparatori in cui gli '''n''' bitsdi '''X''' e '''Y''' verranno confrontati separatamente e contemporaneamente.
La prima coppia di bits '''x<sub>i</sub>''' e '''y<sub>i</sub>''' (i=n-1,n-2,...,0) che differisce , determina l'uscita finale del comparatore, a prescindere dal valore di '''x<sub>i-1</sub>''', '''y<sub>i-1</sub>''',...ecc.
Nel seguito viene costruito un circuito comparatore in parallelo di 2 numeri di 2 bit: un circuito relativo a parole a '''n''' bits, avrà l'uscita uguale a quello di figura 2.5.2 e 2 circuiti '''NAND''' in più per ogni coppia di bit addizionale.
Siano quindi da confrontare i due numeri; '''X=x<sub>1</sub> x<sub>0</sub>''' e '''Y=y<sub>1</sub> y<sub>0</sub>'''.
La tabella della verità relativa al problema del confronto in parallelo sarà:
:<math>1) x > y\quad S_1=\bar x_1 x_0 \bar y_1 \bar y_0+x_1 \bar x_0 \bar y_1 \bar y_o+x_1 \bar x_0 \bar y_1 y_0+x_1 x_0 \bar y_1 \bar y_0+x_1 x_0 y_1 \bar y_1 y_0+x_1 x_0 y_1 \bar y_0</math>
[[File:Diagramma di Karnaugh di X maggiore di Y.png|right]]
Semplificando la funzione mediante un diagramma di Karnaugh si ha:
Line 343 ⟶ 509:
:::<math> S_1=x_1 \bar y_1+x_0 \bar y_1 \bar y_0+\bar y_0 x_1 x_0=</math><br>
::::<math>\overline {\overline {x_1\bar y_1+x_0\bar y_0(x_1+\bar y_1)}}=</math>
::::<math>\overline {\overline {x_1\bar y_1}\cdot \overline {x_0\bar y_0 \overline {\overline {(x_1+\bar y_1 )}}}}=</math>
::::<math>\overline {\overline {x_1 \bar y_1}\cdot \overline {x_0 \bar y_0(\overline {\bar x_1\cdot y_1})}}</math>
:<math>2)-x+y\quad S_2=\bar x_1\bar x_0\bar y_1y_0+\bar x_1\bar x_0 y_1\bar y_0+\bar x_1 \bar x_0 y_1 y_0+\bar x_1x_0 y_1\bar u_0+\bar x_1 x_0y_1y_0+x_1\bar x_0y_1y_0</math>
Line 368 ⟶ 531:
[[File:Comparatore parallelo a 2 numeri.png|right]]
:<math>3)-\quad X=Y</math>
Dalla tabella della verità si deduce che:
Line 378 ⟶ 539:
Utilizzando alloa delle porte di '''NAND (/)''' si costruirà il circuito a latere
== Convertitore codice binaio puro-binario riflesso e viceversa ==
Sia il numero binario '''X''' e siano le sue due rappresentazioni binarie:
::::::<math>in\ binaro\ puro\ X\ sia\qquad B=(B_n B_{n-1}....B_0)</math
::::::<math>in\ binario\ riflesso\ X\ sia\qquad R=R_n R_{}...R_0).</math>
Le formule di conversione (Cap.3 parte I) sono:
:::::<math>(R\longrightarrow B):\qquad \oplus B_p= \sum_{j=p}^{j=n}R_j</math
:::::<math>(B\longrightarrow R):\qquad R_p=B_p\oplus B_{p+1}\ ;\ R_n=B_n</math>
Le conversioni si fanno più facilmente dalle cifre di peso più forte.
In queste condizioni, poniamo, per la conversione binario riflesso-binario puro:
::::::<math>\begin{cases}Z_p=B_{n-p}\\Q_p=B{n-p-1}\ \ \ \ \ (p\ge 1), Q_B=0\\E_p=R_{n-p}\end{cases}</math
Si ha:
::::::<math>\begin{cases}Q_p=Q_p\oplus E_p\\Z_p=Q_p\oplus E_p\end{cases}</math>
[[File:Convertitore codice riflesso -binario puro.png|right]]
Mediante le equazioni trovate possiamo dedure lo schema del circuito che realizza la conversione da un codice riflesso ad uno binario puro: per avere la uscita '''Z<sub>p</sub>''' è sufficiente una porta di '''XOR''' mentre per l'uscita '''Q<sub>p+1</sub>''' è necessario utilizzare un '''Flip-Flop T'''.
Per la conversione binario puro-binario riflesso, si pone:
:::::<math>\begin{cases}Q_k=B_{n-k+1}\\E_k=B_{n-k}\\Z_k=R_{n-k}\end{cases}</math
[[File:Convertitore binario puro-binario iflesso.png|right]]
si ha quindi
:::::<math>\begin{cases}Q_{k+1}=E_k\\Z_k=Q_k\oplus E_k\qquad\qquad \ con\ Q_0=0\end{cases}</math>
Da cui il circuito nella figura accanto:
== Contatori ==
Si chiama [[w:contatore|contatore]] un circuito capace di prendere nota del numero di impulsi che arrivano in '''input''' e conservare il risultato dell'operazione di conteggio.
Se un contatore somma ogni qual volta arriva un impulso in input, esso pende il nome di '''forward counter''' o '''up counter'''. Se un contatore assume inizialmente una certa configurazione rappresentante un numero ed ad ogni impulso in input sottrae da questo numero, esso viene chiamato '''reverse counter''' o '''down counter'''.
Se un contatore è provvisto di due terminali di input in modo da addizionare se gli impulsi arrivano ad uno dei terminali di input e da sottrarre per gli impulsi che arivano all'altro input , esso viene chiamato '''reversible counter''' o '''up-down counter'''.
I contatori vengono classificati anche in base alla maniera di memorizzare il numero del conteggio.
Se il numero memorizzato è un numero binario, in codice binario puro il contatore è un contatore binario.
Se il numero memorizzato è un numero decimale è un contatore decimale.
Se il digit decimale viene rappresentato mediante un codice binario il contatore è un ''' binay-codet decimal digit counter'''.
Vi sono inoltre contatori capaci di esprimere il conteggio in altri codici binari (p.es.codice Gray). Pe ottenere le equazioni booleane di un contatore binario puro si può pocedee in due modi.
==== Incremento in codice binario puro ====
[[File:Addizione.png|right]]
Il passaggio da un numero '''X''' al numero '''X+1''' può essere rappresentato mediante certe relazioni booleane che legano la rappresentazione dei numeri '''X''' e '''X+1'''. Consideriamo infatti l'addizione:
Si ha:
:::::<math>x_0^
:::::<math>
:::::<math>
:::::<math>- - - - - - - - - - - \ \ - - - - - </math>
:::::<math>x_k^'=x_k\oplus r_k=x_k\oplus \coprod_{i=0}^{i=k-1} x_i\ ;\ r_{k+1}=\coprod_{i=0}^{i=k} x_i</math>
:::::<math>\begin{cases}x_k^'=x_k\oplus\coprod_{i=0}^{i=k-1}x_i\\r_{k+1}=\coprod_{i=0}^{i=k}x_i\end{cases}</math>
Le relazioni che rappresentano il numero '''x+1''' in funzione di '''x''' sono:
:::::<math>\begin{cases}x_k^'=x_k\oplus\coprod_{i=0}^{i=k-1}x_i\\r_{k+1}=\coprod_{i=0}^{i=k}x_i\end{cases}\ \ \ \ (2.7.2)</math>
==== Decremento in codice binario puro ====
Le relazioni che danno la rappresentazione del numero '''X-1''' in funzione di quella di '''X''' possono essere ottenute con il seguente procedimento: [[File:Decremento in codice binario puro.png|right]]
:::::<math>x_0^{''}=x_0\oplus 1=\bar x_0\ \ \ \ \ \ \ \ \ \ \ \ r_1=\bar x_0</math>
:::::<math>x_1^{''}=x_1\oplus r_1=x_1\oplus \bar x_0\ \ \ \ \ r_2=\bar x_1 r_1=\bar x_1\bar x_0</math>
:::::<math>x_2^{''}=x_2\oplus r_2=x_2\oplus {\bar x_1\bar x_0}\ \ r_3=\bar x_2 r_2=\bar x_2\bar x_1</math>
:::::<math>- - - - - - - - - - - \ \ - - - - - </math>
:::::<math>x_k^{''}=x_k\oplus r_k=x_k\oplus \coprod_{i=0}^{i=k-1} \bar x_i\ ;\ r_{k+1}=\coprod_{i=0}^{i=k} \bar x_i</math>
:::::<math>\begin{cases}x_k{''}=x_k\oplus\coprod_{i=0}^{i=k-1}\bar x_i\\r_{k+1}=\coprod_{i=0}^{i=k}\bar x_i\end{cases}\ \ \ \ \ (2.7.3)</math>
Le relazioni (2.7.2) rappresentano il meccanismo di un '''u-counter''' e le (2.7.3) quelle di un '''down-counter), entrambi un codice binario puro. Si noterà che si passa dall'incremento al decremento complementando le variabili che compaiono nella ritenuta.
Complementando ambo i membri della relazione (2.7.3) si ottiene:
:::::::::<math>\bar x_k^{''}=\bar x_k\oplus \coprod_{i=0}^{k-1}\bar x_i</math
che insieme alla:
::::::::::<math>r_{k+1}=\coprod_{i=0}^k \bar x_i</math>
dà la relazione di incremento per i numeri corrispondenti alle parole binarie complementate. Infatti chiamiamo [[w:valore assluto||A|]] il valore rappresentato dal nome '''A''', si ha:
::::::<math>|x^'|=|x|+1</math>
::::::<math>|x^{''}=|x|-1</math>
::::::<math>|\bar x^'|=2^n-1-|x^'|=2^n-1-|x|-1=|\bar x|-1</math>
::::::<math>|\bar x^{''}|=2^n-1-|x^{''}|=2^n-1-|x|+1=|\bar x|+1</math>
Se si chiama con '''E''' la variabile d'entrata del circuito, con l'indice '''n''' si indica il tempo dell'orologio '''(n≥0)''', si ottengono le seguenti equazioni:
::<math>\ \ up -counter:\ \ \ \ \ x_k^{n+1}=x_k^n\oplus E^n (\coprod_{i=0}^{k-1}x_i)_n</math>
::<math>\ \ down- counter:\ \ x_k^{n+1}=x_k^n\oplus E^n (\coprod_{i=0}^{k-1}\bar x_i)_n</math>
[[File:Contatore a 16 stadi (up-counter).png|right]]
[[File:Up counter in binario puro.png|right]]
Le figure '''A''' e '''B''' rappresentano degli '''up-conter''' a 16 stadi interni quattro stadi binari). L'orologio non viene indicato).
La generalizzazione al caso di '''m''' stadi (2<sup>m</sup> stadi interni) è immediata.
Si noterà che per '''m''' elevato non è possibile connettere i '''Flip-Flop''' mediante una logica ad '''1''' livello come in figura '''A''' in quanto per il rango '''k''' è necessari una porta a '''k''' entrate.<br7>
Si possono allora realizzare i prodotti '''π x<sub>i</sub>''' mediante funzioni di funzioni come in figura '''B'''.
Nella configurazione data, sono sufficienti delle porte '''AND''' a due entrate: risulta essere più lungo però il tempo di propagazione del riporto.
Per il rango '''k''' ci vuole un tempo '''k''' volte maggiore di quello necessario per il contatore '''A'''.
[[File:Up- down counte.png|right]]
Le cifre '''x<sub>k</sub>''' di rango '''k''' ad un certo istante '''n''' sono ovviamente rappresentate dagli stati interni dei '''Flip.Flop T''' di rango corrispondente mentre le uscite complimentate rappresentano le '''<math>\bar x_k</math>.'''
Le '''x<sub>k</sub>''' fanno parte della rappresentazione di '''x+1''' mentre le '''<math>\bar x_k</math>''' sono la rappresentazione binaria di '''<math>\bar x-1</math>.
La costruzione di un '''down-counter''' risulta ovvia e la si può vedere facilmente nel grafico sovrastante dove e rappresentato un '''up-down counter'''
Nello schema sono state aggiunte delle linee di ritardo: esse stanno ad indicare che l'input delle porte di '''AND''' che proviene dai '''Flip-Flop''' è lo stato dei '''Flip-Flop''' prima che essi vengano commutati.
Se i '''Flip-Flop''' posseggono un loro ritardo sufficiente, questi ritardi aggiuntivi non sono necessari.
Comde si è appunto supposto nelle figure A e B).
Il disegno logico di un contatore binario può essere ricavato utilizzando una tavola della verità. La tavola mostra non solo le relazioni tra i successivi stati dei '''Flip-Flop''' ma anche gli stati di imput dei '''Flip-Flop''' che causano una commutazione di questi Flp-Flop. Consideriamo un up-counter binario a tre stadi e proponiamoci di costruirlo con Flip-Flop di tipo '''T'''.
[[File:Tvola della verita di un up-counter.png|right]]
La tavola della verità di questo contatore è mostrata nella figura '''D'''.
In questa tavola i tre flip-flop e le loro uscite sono rappresentati con le variabili '''A<sub>3</sub>,A<sub>2</sub>,A<sub>1</sub>''' rappresentano i loro rispettivi '''input'''; '''p''' rappresenta gli impulsi in input da conteggiare; '''t<sub>0</sub>, t<sub>1</sub>..ecc.''' rappresentano la sequenza temporale degli impulsi.
Le tre colonne relative agli '''A''' mostrano la sequenza desiderata degli stati dei tre flip-flop. Le ultime tre colonne mostrano i valori veri richiesti per gli '''input''' '''a<sub>3t</sub>''', '''a<sub>2t</sub>''', '''a<sub>1t</sub>''', capaci di cambiare lo stato del contatore.
In queste tte colonne , lo '''0''' significa che non è richiesto alcun impulso nell'input del flipo-flop , mentreun '''1''' significa che è necessario un impulso nell'imput del flip-flop.
Questi '''0''' e questi '''1''' sono ottenuti dalla commutazione dello stato dei '''Flip-Flop''' indicata nelle tre colonne relative agli '''A'''.
Per esempio, quando lo stato del contatore viene cambiato da '''000''' a '''001''', gli stati di '''A<sub>3</sub>''' e '''A<sub>2</sub>''' non cambiano, quindi i valori di '''a<sub>3t</sub>''' e '''a<sub>2t</sub>'''sono entrambi '''0''' nella prima riga delle colonne relative a '''a<sub>3t</sub>''' e '''a<sub>2t</sub>'''.
Però lo stato di '''A<sub>1</sub>''' cambia da '''0''' a '''1'''; quindi il valore di '''a<sub>1t</sub>''' è '''1''' nella prima riga dell'ultima colonna. Gli altri valori delle ultime tre colonne vengono ottenuti nella stessa maniera.
Da notare che all'istante '''t<sub>8</sub>'''lo stato del contatore è '''000''' lo stesso che all'istante '''t<sub>0</sub>'''
Il contatore quindi ha un compotamednto ciclico.
Le equazioni di input per i tre '''Flip-Flop''' dedotte dalla tabella della verità '''D''' sono:
:::::::<math>a_{1t}=p</math
:::::::<math>2_{2t}=A_1\cdot p</math>
:::::::<math>3_{3t}=A_2\cdot A_1\cdot p</math>
che possono essere anche scritte come:
:::::::<math>a_{1t}=p</math>
:::::::<math>2_{2t}=A_1\cdot a_{1t}</math>
:::::::<math>3_{3t}=A_2\cdot a_{2t}</math>
Quando le equazioni di input vengono sostituite nell'equazione di stato di un '''Flip-Flop T''' '''(Q<sub>n+1</sub>=Q<sub>n</sub> ⊕ E<sub>n</sub>)''' si ottiene:
:::::::<math> A_1 (\pi)=A_1 \oplus p</math
:::::::<math> A_2 (\pi)=A_2 \oplus A_1 p</math>
:::::::<math>A_3(\pi)=A_3\oplus A_2 A_1 p</math>
Queste sono le equazioni di stato di un contatore e descrivono lo stato dei tre '''Flip-Flop'''.
[[File:Tavola della verità per flip-flop SR.png|right]]
Al posto di un '''Flip-Flop T''', si può pensare di utilizzare un '''SR''' per costruire un contatore binario. Nella tavola '''E''' compaiono le condizioni necessarie per costruire un '''up-counter''' binario mediante '''Flip-Flop SR'''.
In questa tabella '''a<sub>3r</sub>''', '''a<sub>2r</sub>''', '''a<sub>1r</sub>''', rappresentano gli input di riset (R) nei tre '''Flip-Flop''' ed '''a<sub>3s</sub>''', '''a<sub>2s</sub>''', '''a<sub>1s</sub>''', i tre set inputs, '''p''' rappresenta gli impulsi di input da conteggiare; '''t<sub>0</sub>''', '''t<sub>1</sub>''', ecc. rappresentano la sequenza temporale degli impulsi di input.
Gli '''0''' e gli '''1''' delle ultime sei colonne sono anche qui ottenuti mediante i cambiamenti di stato dei '''Flip-Flop''' indicati nelle tre prime colonne. Essi però differiscono da quelli della tabella '''D'''. Nella tabella '''E''' l' '''1''' nella colonna dell' '''input reset''' (colonne sei, otto, dieci) indica il cambiamento di stato del '''Flip-Flop''' da '''1''' a '''0''', mentre lo '''0''' indica tutti gli altri casi (da 0 a0, da 1 a 1, da 0 a 1).
L'1 nella colonna dell' '''input reset''' (colonne sette, nove, undici) indica il cambiamento dello stato del '''Flip-Flop''' da '''0''' a '''1''' mentre lo '''0''' indica tutti gli altri casi (da 0 a 0, da 1 a 1, da 1 a 0). Per esempio, quando lo stato del contatore cambia da '''000''' a '''001''', gli stati di '''A<sub>3</sub>''' e '''A<sub>2</sub>''' rimangono immutati, per cui i valori di '''a<sub>3r</sub>''', '''a<sub>3s</sub>''', '''a<sub>2r</sub>''', '''a<sub>2s</sub>''' sono '''0''' nella prima riga delle colonne sei, sette, otto e nove.
Lo stato '''A<sub>1</sub>''' però deve cambiare da '''0''' a '''1''', quindi il valore di '''a<sub>1r</sub>''' è '''0''' mentre il valore di '''a<sub>1s</sub>''' è '''1''' nella prima riga delle due ultime colonne rispettivamente. I valori degli altri input '''set''' e '''reset''' sono ottenuti nella stessa maniera.
Dalla tabella '''E''' possiamo ottenere le equazioni di input dei tre '''Flip-Flop''':
::::::<math>a_{1s}=\bar A_1\cdot p</math>
::::::<math>a_{2s}=\bar A_2\cdot A_1\cdot p=\bar A_2\cdot a_{1r}</math>
::::::<math>a_{3s}=\bar A_3\cdot A_2\cdot A_1\cdot p=\bar A_3\cdot a_{2r}\ \ \ \ \ \ 2.7.10</math>
::::::<math>a_{1r}=A_1\cdot p</math>
::::::<math>a_{2r}=A_2\cdot A_1\cdot p=A_2 \cdot a_{1r}</math>
::::::<math>a_{3r}=A_3\cdot A_2\cdot A_1\cdot p=A_3\cdot a_{2r}</math>
Se si sostituiscono le equazioni di input nella equazione di stato di un '''Flip-Flop SR''' (<math>Q_{n+1}=Q_n \bar R_n + S_n</math>), si ottengono le equazioni '''2.7.8''', cioè le equazioni di stato di un '''up-counter''' binario.
[[File:Contatore binario con half-adders e flip-flop SR.png|right]]
Le equazioni 2.7.10 si possono scrivere in un altro modo.
Alle prime tre equazioni di 2.7.10 si aggiungono rispettivamente i termini '''<math>A_1\cdot \bar p, A_2\cdot \bar a_{1r}, A_3\cdot \bar a_{2r}</math>'''; queste somme logiche non cambiano il valore delle espressioni di partenza.
Le sei equazioni diventano allora:
::::::<math>a_{1s}=A_1\oplus p\ \ \ \ \ \ \ a_{1r}=A_1\cdot p</math>
::::::<math>a_{2s}=A_2\oplus a_{1r}\ \ \ \ \ a_{2r}=A_2\cdot a_{1r}</math>
::::::<math>a_{3s}=A_3\oplus a_{2r}\ \ \ \ \ a_{3r}=A_3\cdot a_{2r}</math>
Si noti che queste sono le equazioni delle somme e del riporto in output di un '''half-adder'''.
Quindi '''a<sub>1s</sub>''' e '''a<sub>1r</sub>''' sono rispettivamente la somma e il riporto di un '''half-adder''' i cui input sono '''A_1''' e '''p'''.
In modo equivalente , si ha che '''a<sub>2s</sub>''' e '''a<sub>2r</sub>''' come '''a<sub>3s</sub>''' e '''a<sub>3r</sub>''' sono le uscite di '''half-addeers'''.
Il contatore binario utlizzante degli '''half-adder''' e dei '''flip-flop SR''', viene mostrat in figura '''F'''.
== Contatori decimali ==
I contatori decimali sono circuiti che accettano degli impulsi in input, li contano e ogni volta che la somma totale risulti essere '''10''', ritornano allo stato iniziale emettendo sulla linea di uscita un impulso di riporto (dettom carry o overflow).
Tali contatori di capacità '''10''' vengono chiamati '''decadi'''.br/>
Interconnettendo '''m''' elementi decimali di conteggio di questo tipo, in modo che l'uscita di un elemento '''J-1''' serva come ingresso all'elemnto '''J''', si può realizzare un contatore di capacità '''10<sup>m</sup>.
Per codificare i 10 stati interni si usano generalmente codifiche di tipo binario con almeno '''4''' digit binari.
[[File:Codice 8421.png|right]]
Si è visto (cap.III°, parte I<sup>a</sup>) che quando la cifra decimale corrispondente deve essere convertita in analogico, può essere utile considerare un codice ponderato. Infatti nel caso di una conversione in tensione sarà sufficiente fare la somma ponderata delle correnti corrispondenti ai 4 digit binari.
Nella tabella posta accanto compaiono il codice '''8421''' '''(I)''' e quello ad '''eccesso di 3''' '''(II)'''
Ci proponiamo nel seguito di costruire un contatore relativo al codice '''8421''' e quello relativo al codice '''ad eccesso di tre'''.
[[File:Rappresentazione contatore decimale in codice 8421.png|right]]
La configurazione generale di un contatore decimale relativo al codice '''8421''' sarà:
Il numero rappresentato dallo stato interno dei Flip-Flop '''A<sub>4</sub>, A<sub>3</sub>, A<sub>2</sub> A<sub>1</sub>''', raggiungeà al massimo '''1001''', equivalente al digit decimale '''9'''.
Appena arriva un nuovo impulso, il contatore assume lo stato '''0000''' (equivalente al digit decimale 0), e produce un riporto che servirà come input per incrementare la seconda decade.
[[File:Tabella 2.8.2.png|right]]
Queste considerazioni e la conoscenza delle proprietà dei '''Flip-Flop T''' che vogliamo utilizzare per realizzare il circuito , ci permettono di scrivere ls seguente tabella (2.8.2):
Possiamo scrivere le equazioni di input '''a<sub>4t</sub>, a<sub>3t</sub>, a<sub>2t</sub>, a<sub>1t</sub>''' direttamente dalla tabella '''2.8.2'''.
[[File:Diagrammi di Kanaugh per contatore digitale.png|right]]
Possiamo semplificare le espressioni boolea
ne mediante diagrammi di Karnaugh; in questa semplificazione si può far uso anche degli stati non esistenti '''1010, 1011, 1100, 1101, 1110, 1111 (segnati con crocetta).
La variabile '''p''' è una variabile d'ingresso ma poiché vale sempre '''1''', è inutile prenderla in considerazione durante la semplificazione.
Dai digrammi si esplicano:
::::::<math>a_{1t}=p</math>
::::::<math>a_{2t}=A_1 \bar A_4\cdot p</math>
::::::<math>a_{3t}=A_1 A_2\bar A_4\cdot p</math>
::::::<math>a_{4t}=\bar A_4 A_3 A_2 A_1 \cdot p+A_4 A_1\cdot p </math>
Sostituendo questi valori di input nella equazione di stato di un Flip-Flop si ottengono le equazioni di stato di una decade relativa al codice 8421:
::::::<math>A_1()=A_1\oplus p</math>
::::::<math>A_2()=A_2\oplus A_1 \bar A_4 p</math>
Line 581 ⟶ 850:
::::::<math>A_4()=A_4 \oplus (\bar A_4 A_3 A_2 A_1 p +A_4 A_1 p)</math>
[[File:Decade relativa al codice 8421.png
Nella figura viene dato il diagramma logico di una realizzazione di questo circuito.
[[File:Tabella relativa a contatore codice accesso tre.png]]
Supponiamo ora di voler costruire un contatore per un codice a accesso di tre.
La tabella della verità relativa viene data in figura 2.8.4
Semplificando con Karnaugh si ottengono le equazioni di input seguenti:
::::::<math>a_{1t}=p</math>
::::::<math>a_{2t}=A_1 p+A_4 A_3 p</math>
::::::<math>A_{3t}=a_1 a_2 P+a_4 a_3 p</math>
::::::<math>a_{4t}=A_1 A_2 A_3 p+A_4 A_3 p</math>
[[File:Decade per codici ad eccesso di tre.png|right]]
Per le semplificazioni si sono considerate anche le combinazioni che non compaiono nel codice ad eccesso di tre.
Dalle equazioni di input si deduce una possibile realizzazione del circuito (2.8.5): decadi per codici ad eccesso di tre.
== Contatori in codice binario riflesso ==
Determiniamo per prima cosa le relazioni che legano due parole codice '''<math>y_i</math>''' e '''<math>y_{i+1}</math>''' rappresentanti in codice rilflesso due numeri '''<math>x_i</math>''' e '''<math>x_{i+1}</math>''' consecutivi, cioè tali che '''<math>x_{i+1}-x_i=1</math>.
Si è visto (cap.3 parte I) che <math>y_1</math> e <math>y_{i+1}</math> devono essere adiacenti.
Si possono avere due e si può scrivere cosìcasi.
:- primo caso:<math>x_i pari</math>
Si ha allora:
::::::<math>\begin{cases}x_i=x_nx_{n-1}..x_k..x_1 0\\ e\ quindi \\x_{i+1}=x_nx_{n-1}..x_k..x_1 1\end{cases}</math>
a questi due numeri corrispondono le seguenti rappresentazioni in codice Gray:
::::<math>y_i=x_n(x_{n-1}\oplus x_n)(x_{n-2}\oplus x_{n-1})..(x_{k}\oplus x_{k+1})..(x_1\oplus x_2)(0\oplus x_1)</math>
:::<math>\bar y_{i+1}=x_n(x_{n-1}\oplus x_n)(x_{n-2}\oplus x_{n-1})..(x_{k}\oplus x_{k+1})..(x_1\oplus x_2)(1\oplus x_1)</math>
Si ha quindi:
:::::<math>y_i\oplus y_{i+1}=000..0..0 1\ \ \ \ (2.9.1)</math>
Quindi se <math>y_i</math> rappresenta in codice Gray un intero pari, si ottiene <math>y_{i+1}</math>, complemetando il digit più a destra.
:-Secondo caso: <math>x_i</math> dispari:
<math>x_i</math> comincia a destra con un '''1''' e si può scrvere così:
::::::<math>x_i=x_nx_{n-1}..x_{k+1}..0\ 1\ 1..1\ 1</math>
::::::<math>x_{i+1}=x_nx_{n-1}..x_{k+1}..1\ 0\ 0..0\ 0</math>
Da cui:
::::::<math>y_i=x_n(x_{n-1}\oplus x_n)..(x_{k+1}\oplus x_{k+2})x_{k+1}1\ 0\ 0.. 0\ 0</math>
::::::<math>y_{i+1}=x_n(x_{n-1}\oplus x_n)..(x_{k+1}\oplus x_{k+2})\bar x_{k+1}1\ 0\ 0.. 0\ 0</math>
e:
::::::<math>y_i\oplus y_{i+1}=0\ 0\ ..0\ 1..0\ 0..0\ 0\ \ \ \ \ \ (2.9.2)</math
Quindi, quando <math>y_i</math> rappresenta in codice Gray un numero dispari, si ottiene la rappresentazione del numero successivo complementando la prima cifra a sinistra del primo '''1''' incontrato partendo da destra.
Consideriamo ora un contatore '''R=(R<sub>m</sub>...R<sub>k</sub>...R<sub>0</sub>)''' binario riflesso in cui '''R<sub>k</sub>''' sono gli stati interni di '''Flip-Flop T''' ed indicano il valore delle cifre di rango '''K''' in codice Gray.
Chiamiamo con <math>r^n_k</math> l'ingesso del '''Flip-Flop T''' di rango '''k''' all'istante '''n'''; si avrà:
Line 642 ⟶ 931:
::::::<math>R^{n+1}_k\oplus R^n_k=r^n_k</math>
Conoscendo lo stato di parità del numero <math>R^n</math>, si possono dedurre dalla '''(2.9.1)''' e '''(2.9.2)''', le <math>r^n_k</math>, cioè i valori di ingresso da dare ai singoli '''Flip-Flop''' in modo da ottenere il numero <math>R^{n+1}</math>.
Ora, la parità del numero '''<math>R^n</math>''' consideerato è dato dal digit '''<math>B_0</math>''' della rappresentazione in binario puro.
::::::<math>B_0=\oplus \sum_{k=0}^k=m R_k</math>
::::::<math>B_0=0\ per\ R^n\ pari</math>
::::::<math>B_0=1\ per\ R^n\ dispari</math>
Si deducono le seguenti relazioni:
::::::<math>r^n_0=R^n_0\oplus R^{n+1}_0=\bar B^n_0 E^n\ \ \ \ \ (k=0)</math>
::::::<math>r^n_k=R^n_k\oplus R^{n+1}_k=R^n_{k-1}\bar R^n_{k-2}...\bar R^n_1\ \bar R^n_0\ B^n_0\ E^n\ \ \ (1=k=m)</math>
dove '''E''' rappresenta la variabile d'ingresso del contatore.
[[File:Contatore in binario riflesso.png
[[File:Contatore in binario riflesso (bis).png]]
Ponendo:
::<math>R^n_{-1}=\bar B^n_0\ \ \ \ \begin{cases}R^n_{-1}=0, R^n\ e'\ dispari\\R^n_{-1}=1, R^n\ e'\ pari\end{cases}</math>
Si ha allora per <math>0\le k \le m</math>
<math>r^n_k=R^n_k\oplus R^{n+1}_k=R^n_{k-1}\bar R^n_{k-2}\bar R^n_{k-3}...\bar R^n_1\bar R^n_0\bar R^n_{-1}E^n\ \ (2.9.3)</math
<math>\bar R^n_{-1}=\oplus \sum_{k=0}^m\ R^n_k</math>
Nelle figure (2.9.4 e 2.9.4bis)sono rappresentati 2 contatori in codice binario riflesso ottenuti applicando le formule '''(2.9.3)''' o considerando una decomposizione analoga a quella fatta nel caso dei contatori in binario puro.
Questo Flip-Flop di rango '''-1''', commuterà ogni volta che si applicherà un '''1''' al suo ingresso.
== Diagrammi di stato ==
Consideriamo a titolo di esempio, un addizionatore binario seriale (fig.2.1.3) ed assumiamo che la configurazione della memoria '''M''', che conserva fino all'istante '''i+1''' il valore del riporto <math>r_{i+1}</math> ottenuto all'istante '''i''', sia rappresentativa dello stato interno del circuito.
[[File:Diagramma di stato.png]]
A partire da uno stato iniziale '''<math>r_i=0</math>''' risulta che le tre combinazioni di ingresso di '''<math>x_i\ y_i</math>''' (cfr.§2.1.2) '''00,01,10''' il valore di <math>r_i</math>, e cioè lo stato interno del circuito non cambia; mentre per la combinazione '''<math>x_i=y_i=1</math>''' lo stato interno passa dal valore '''0''' al valore '''1'''. Analogamente si può considerare per quali combinazioni delle variabili d'ingresso lo stato interno rimane uguale ad '''1''' e per quale valore cambia invece nuovamente da '''1''' a '''0'''. Si può quindi riscrivere la tavola della verità di '''§ 2.1.2''' sotto la forma di diagramma di stato, in cui '''<math>x_i y_i</math>''' rappresenta la combinazione dei valori d'ingresso, '''<math>r_i</math>''' lo stato interno; ed in funzione dei valori di <math>r_i</math> e di '''<math>x_i y_i</math>''' sono riportati in ogni casella, separati da una '''/''', il nuovo stato interno '''<math>r_{i+1}</math>''' ed il valore di uscita '''<math>s_i</math>'''.
[[File:Diagamma di stato a vertici rappresentativi.png]]
[[File:Grafo di stato 2.10.1 a.png]]
Si può equivalentemente rappresentare il comportamento del circuito per mezzo di un grafo composto da vertici rappresentativi dello stato interno e da archi orientati tra le coppie di vertici.
Gli archi orientati sono rappresentativi dei valori di ingresso che determinano il passaggio dello stato interno dasl vertice di partenza a quello di arrivo, e recano, separati da una barra, oltre a questi valori , anche i corrispondenti valori di uscita.
Nell'esempio in esame si ha quindi il grafo posto di fianco:
Il grafo di una rete sequenziale contiene dunque le stesse informazioni della tabella della verità; con esso però si mette in particolare evidenza la connessione logica degli stati che il sistema può assumere. Una altra rappresentazione molto usata ha nome di diagramma di stato ed indica gli stati successivamente assunti dal sistema.
Un semplice esempio riguarda il diagramma di stato di un contatore binario modulo 2<sup>3</sup> in (2.10.1 a). Il nujmero binario racchiuso nel circolo indica lo stato dei tre Flip-Flop, e le frecce indicano la sequenza dei cambiamenti di stato (cnf:§2.7).
[[File:Diagramma di stato di un contatore decimale.png]]
Un contatore decimale ,o decade, richieder invece 10 stati distinti. Il diagramma di stato. Il diagramma di stato di un tale contatore con codice '''8.4.2.1''' è riportato in (2.10.1 b).
Se come visto nel '''§ 2.7.3''' con <math>a_{it}</math> (i=1,2,3,4) si rappresentano i valori di input capaci di cambiare lo stato dei quattro rispettivi Flip-Flop , dal diagramma di statosi possono ottenere, senza costruire la tabella della verità, le equazioni di input ricavate nel '''§2.8'''. Ad esempio , infatti, considerando che i numeri racchiusinel circoletto rappresentano i valori assunti di volta in volta dall'insieme ordinato <math>A_4\ A_3\ A_2\ A_1</math> e se consideriamo in particolare lo stato <math>A_2</math>, inizialmente posty a '''0''', notiamo che detto stato commuta sempre e solo a partire da una configurazione del tipo '''0\ -\ - 1''' e quindi l'equazione di input relativa al Flip-Flop di stato <math>A_2</math> tenuto conto della variabile d'ingesso '''p''', deve essere:
| |||