# Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (a)

Algebre booleane e progetto logico dei calcolatori digitali
Copertina Tutti i moduli · Sviluppo
Parte prima: Algebre booleane
    1.1 IntroduzioneAlgebre booleane e progetto logico dei calcolatori digitali/Introduzione
    1.2 Sistemi di numerazione, aritmetica binariaAlgebre booleane e progetto logico dei calcolatori digitali/Sistemi di numerazione, aritmetica binaria
    1.3 CodiciAlgebre booleane e progetto logico dei calcolatori digitali/Codici
    1.4 Teoria della commutazioneAlgebre booleane e progetto logico dei calcolatori digitali/Teoria della commutazione
    1.5 Algebra delle classi - Algebra della logicaAlgebre booleane e progetto logico dei calcolatori digitali/Algebra delle classi - Algebra della logica
    1.6 Algebre booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Algebre booleane
    1.7 Funzioni booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane
    1.8 Rappresentazione geometrica delle funzioni booleane e loro minimizzazioneAlgebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione
Parte seconda: Circuiti logici e calcolatori digitali
    2.1 Circuiti logici e di memoriaAlgebre booleane e progetto logico dei calcolatori digitali/Circuiti logici e di memoria
    2.2 Circuiti di un calcolatore digitale (a)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (a)
    2.3 Circuiti di un calcolatore digitale (b)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (b)
    2.4 Progetto logico di un calcolatore digitaleAlgebre booleane e progetto logico dei calcolatori digitali/Progetto logico di un calcolatore digitale
Modifica il sommario

## Addizionatore e sottrattore binario

Siano le variabili x$_i$, y$_i$, r$_i$, s$_i$ e r$_{{i+1}}$ definite nel capitolo Sistemi di numerazione, aritmetica binaria, a proposito della somma e della sottrazione di due numeri binari.
Assumendo 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 capitolo Sistemi di numerazione, aritmetica binaria le tavole di verità che definiscono, per un singolo rango, la somma e la sottrazione.

### Semiaddizionatore (half-adder)

Questo circuito è un blocco fondamentale costituito da 3 porte di AND e una porta di OR. Il suo funzionamento viene stabilito mediante la tavola di verità:
| X$_i$ | Y$_i$ | S$_i$ | R$_{i+1}$ |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
È da notare che questo circuito presenta due output separati: uno per la somma e l'altro per il riporto.
Le due funzioni booleane descritte dalla tavola sono:
             $S_{i}=Y_{i}{\bar {X}}_{i}+X_{i}{\bar {Y}}_{i}=X_{i}\oplus Y_{i}$
                $r_{i+1}=X_{i}\cdot Y_{i}$
Il diagramma logico di un semiaddizionatore sarà quindi:
Il circuito che genera la funzione S$_i$ viene anche impiegato come porta di ⊕ (OR esclusivo)

### Addizionatore elementare (Full Adder)

Il processo della somma binaria consiste in questo caso nella addizione contemporanea delle due variabili X$_i$ e Y$_i$ e del riporto r$_i$ ottenuto durante la somma parziale precedente. La tabella della verità relativa S$_i$ e r$_{i+1}$ sarà quindi:
| X$_i$ | Y$_i$ | r$_{i+r}$ | S$_i$ | r$_{i+r}$ |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |

#### Equazione booleana di un addizionatore
##### Forma canonica

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

##### Altre espressioni

Per S$_i$, si può scrivere:
             $S_{i}=({\bar {X}}_{i}{\bar {Y}}_{i}+X_{i}Y_{i})r_{i}+({\bar {X}}_{i}Y_{i}+X_{i}{\bar {Y}}_{i})r_{i}$
                $={\overline {(X_{i}\oplus Y_{i})}}+(X_{i}\oplus Y_{i}){\bar {r}}_{i}$
                $=(X_{i}\oplus Y_{i})\oplus r_{i}$
                $=X_{i}\oplus Y_{i}\oplus r_{i}$
La funzione r$_{i+1}$ essere semplificata:
             $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}$
                $=({\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}$
                =$=X_{i}Y_{i}+Y_{i}r_{i}+r_{i}X_{i}$
                $=X_{i}Y_{i}\oplus Y_{i}r_{i}\oplus r_{i}X_{i}$
Per comodità, possiamo scrivere ulteriormente:
             $S_{i}=(X_{i}\oplus Y_{i})\oplus r_{i}$
             $r_{i+1}=X_{i}Y_{i}(r_{i}+{\bar {r}}_{i})+r_{i}(X_{i}{\bar {Y}}_{i}+{\bar {X}}_{i}Y_{i})$
                $=X_{i}Y_{i}+r_{i}(X_{i}\oplus Y_{i})$
Quindi S$_i$ e r$_{i+1}$ possono essere ottenuti mediante due reti: la prima sarà $X_{i}\oplus Y_{i}$ e $X_{i}Y_{i}$, la seconda $(X_{i}\oplus Y_{i})\oplus r_{i}$ e $(X_{i}\oplus Y_{i})r_{i}$.
Ciascuna di queste reti è un semiaddizionatore.
Connettendole come da figura e utilizzando una porta supplementare OR per formare $r_{i+1}$, si ottiene un addizionatore elementare a tre ingressi $X_{i},Y_{i},r_{i}$.
Mediante altre trasformazioni algebriche, si possono ovviamente ottenere altri schemi.
Per esempio, considerando le espressioni:
             $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}$
             $r_{r+1}=X_{i}Y_{i}+X_{i}r_{i}+X_{i}r_{i}$
si avrà il seguente schema:
L'addizionatore elementare che realizza le funzioni S$_i$ e r$_{i+1}$ può essere utilizzato sia in un addizionatore in serie sia in un addizionatore in parallelo.

### Addizionatore in serie-Addizionatore in parallelo

Nell'addizionatore in serie le cifre degli operandi X e Y (X$_i$,Y$_i$) si presentano negli istanti successivi i.
Una memoria M (per esempio una linea di ritardo con ritardo di un bit) conserva il riporto r$_{i+1}$, elaborato all'istante i, fino all'istante i+1 (vedi figura).
Nell'addizionatore in parallelo, le cifre X$_i$ e Y$_i$ (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$_i$,Y$_i$) 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 e n stadi costituiti da addizionatori elementari del tipo descritto in (2.1.2) (rango i>0).
Il riporto elaborato al rango i (r$_{i+1}$) 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$^{n+1}$-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.

### Sottrazione binaria

Mediante la tabella della verità a fianco si può definire il funzionamento di un blocco chiamato semi-sottrattore (half-subtractor) binario. Si fa l'ipotesi che il minuendo Xe il sottraendo Y siano positivi e tali che X≥Y.
| X$_i$ | Y$_i$ | d$_i$ | r$_{i+1}$ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
Le equazioni booleane che definiscono la differenza e la ritenuta in una sottrazione binaria sono dunque:
             $d_{i}={\bar {X}}_{i}Y_{i}+X_{i}{\bar {Y}}_{I}=X_{i}\oplus Y_{i}$
             $r_{i+1}={\bar {X}}_{i}Y_{i}$
Solo la seconda equazione differisce da quella ottenuta per l'addizione: essa si può dedurre da quella del par. 2.1.1 sostituendo $X_{i}$ con ${\bar {X}}_{i}$.
Un semisottrattore genera la differenza d e la ritenuta r$_{i+1}$ mediante il minuendo X$_i$ e il sottraendo Y$_i$.
| X$_i$ | Y$_i$ | r$_i$ | d$_i$ | r$_{i+1}$ |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Volendo invece ottenere la differenza d$_i$ e la ritenuta r$_{i+1}$ considerando il sottraendo X$_i$, il minuendo Y$_i$ e la ritenuta r$_i$ del passo precedente, si ottiene la tabella della verità annessa al fianco.
Le equazioni booleane corrispondenti sono:
             $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}$
             $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})$
Uno dei possibili modi di realizzare un sottrattore elementare completo consiste nel considerare due semisottrattori.
Il semi-sottrattore e il sottrattore completo possono essere utilizzati per costruire sottrattori in serie e in parallelo, sempre con l'ipotesi che 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$_{n-1}$ X$_{n-2}$...X$_0$, il suo complemento a 1 è il numero $C_{1}(X)$ che ha per rappresentazione ${\bar {X}}$:
             $C_{1}(X)={\bar {X}}={\bar {X}}_{n-1}{\bar {X}}_{n-2}...{\bar {X}}_{k}...{\bar {X}}_{1}{\bar {X}}_{0}$
Si suppone X intero:
                $Es.\qquad X=010110$
                   $C_{1}(X)=101001$
       $Si\ ha\qquad X+C_{1}(X)=X+{\bar {X}}=2^{n}-1$
Infatti, se si costruisce la somma, cifra dopo cifra, si ha:
                ${\begin{cases}S_{k}=X_{k}\oplus {\bar {X}}_{k}\oplus r_{k}=r_{k}\oplus 1={\bar {r}}_{k}\\r_{k+1}=X_{k}{\bar {X}}_{k}+r_{k}(X_{k}\oplus {\bar {X}}_{k})=r_{k}\end{cases}}$
da cui, essendo r$_0$=0,
    ${\begin{cases}S_{k}=1\\r_{h}=0\end{cases}}\qquad \qquad per\ ogni\ k\ (k=0,...,n-1)$
                $S={\begin{matrix}\overbrace {111...11} ^{n\ cifre}\end{matrix}}=2^{n}-1$
Un circuito complementatore (a 1) converte un numero binario avuto in input, in un output che ne è il complemento a 1.
Un complementatore può essere costruito in modo da ricevere un input seriale oppure uno in parallelo.
In figura sono mostrati due complementatori che forniscono in output il valore $P\oplus x$, essendo P il valore di un opportuno segnale di controllo: si ottiene il complemento a 1 quando P=1, infatti:
                   ${\bar {X}}=X\oplus 1$
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 input. 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 numero binario.

## Circuito di complementazione a 2

Sia il numero binario X, si chiama complemento vero o complemento a 2 la quantità $C_{2}(X)=2^{n}-X$.
Si ha dunque:
                $C_{2}(X)=C_{1}(X)+1$
          $con\qquad \qquad X=(X_{n-1}X_{n-2}...X_{k}...X_{1}X_{0})$
                      $C_{1}(X)=({\bar {X}}_{n-1}...{\bar {X}}_{k}...{\bar {X}}_{0})$
Aggiungendo 1 a C$_1$(X) si ottiene:
                $C_{2}(X)=(Y_{n}-1Y_{n}-2...X_{k}...Y_{0})=Y$
Ricordando come si esprimono in algebra booleana le somme e i riporti di una addizione dell'aritmetica booleana, si ha:
                $Y_{0}={\bar {X}}_{0}\oplus 1\qquad \qquad \qquad$
                $Y_{1}={\bar {X}}_{1}\oplus r_{1}={\bar {X}}_{1}\oplus {\bar {X}}_{0}\qquad \qquad r_{2}={\bar {X}}_{\ }{\bar {X}}_{0}$
                $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}$
                $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}=$
                $X_{k}\oplus {\overline {(\prod _{i=0}^{i=k-1}{\bar {X}}_{i})}}=X_{k}\oplus \sum _{i=0}^{i=k-1}X_{i}$
Ponendo:
                $Z_{k}=\sum _{i=0}^{i=k-1}X_{i}$
si ottengono le seguenti equazioni di un circuito complementare a 2 seriale:
                ${\begin{cases}Y_{k}=X_{k}\oplus Z_{k}\\Z_{k+1}=Z_{k}+X_{k}\end{cases}}$
Tenendo presente l'equazione booleana di un flip-flop SR, si può pensare di realizzare l'equazione $Z_{k+1}=Z_{k}+X_{k}$ mediante un SR con l'ingresso R sempre mantenuto a 0 e con lo stato interno iniziale Z$_0$=0.
Nella figura è descritto un complementatore a 2 di tipo seriale per numeri binari senza segno.
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 bit delle cifre significative in ordine di peso crescente.
Quando il bit del segno, arriva in input, esso passa attraverso la via a e compare invariato in output.
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 flip-flop S viene messo nello stato 1. La via a viene interdetta e la via b viene permessa.
I bit 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.
          $Esempio\ \ \ \ X=0110100$
                   $C_{2}(X)=1001100$
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 interdice la porta 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 ${\bar {Z}}=0$ interdisce la porta AND relativa ai bits di X.
Si ha inoltre:
                $X+C_{2}(X)=2^{n}=0\ mod\ 2^{n}$
Si vede quindi che, facendo le operazioni modulo 2$^n$, si ottengono gli stessi risultati sia operando con X-Y che con X+C$_2$(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:
                $C_{2}(Y)=Y'=(Y'_{n-1}Y'_{n-2}...Y'_{0})$
Le operazioni X-Y e X+C$_2$(Y)=X+Y' sono definite in forma ricorrente dalle equazioni:
                $(X-Y)\ \ \ {\begin{cases}S_{k}=X_{k}\oplus Y_{k}\oplus r_{k}\\r_{k+1}={\bar {X}}_{k}Y_{k}\oplus Y_{k}r_{k}\oplus {\bar {X}}_{k}r_{k}\end{cases}}$
                $(X+Y')\ \ \ {\begin{cases}S'_{k}=X_{k}\oplus Y'_{k}\oplus r'_{k}\\r_{k+1}=X_{k}Y'_{k}\oplus Y'_{k}r'_{k}\oplus X_{k}r'_{k}\end{cases}}$
Supponiamo che al rango k si abbia S'$_k$=S$_k$: Si ha allora:
                $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}$
cioè
                $r'_{k}=r_{k}\oplus (\sum _{i=0}^{i=k-1}Y_{i})$
Si deduce immediatamente:
          $r'_{k+1}=X_{k}[Y_{k}\oplus (\sum _{i=0}^{k-1}Y_{i})]\oplus [Y_{k}\oplus (\sum _{i=0}^{k-1}Y_{i})]\cdot [r_{k}\oplus (\sum _{i=0}^{k-1}Y_{i})]\oplus X_{k}[r_{k}\oplus (\sum _{i=0}^{k-1}Y_{i})]=$
          $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)$
da cui
          $r'_{k+1}=r_{k+1}\oplus Y_{k}\oplus (\sum _{i=0}^{k-1}Y_{i})(Y_{k}\oplus r_{k}\oplus 1=$
          $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})=$
          $r_{k+1}\oplus (\sum _{i=0}^{i=k}Y_{i})\oplus r_{k}(\coprod _{i=0}^{k-1}{\bar {Y}}_{i})$
Consideriamo l'ultimo termine: si ha:
          $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})=$
          ${\bar {X}}_{k-1}{\bar {Y}}_{k-1}r_{k-1}(\coprod _{i=0}^{k-2}{\bar {Y}}_{i})$
e quindi iterando il procedimento, si ha:
          $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$
Da cui:
          $r'_{k+1}=r_{k+1}\oplus (\sum _{i=0}^{i=k}Yi)$
di conseguenza
                $S'_{k+1}=S_{k+1}$
E quindi se S'$_k$= S$_k$ si ha S'$_{k+1}$=S$_{k+1}$
Poiché S'$_0$=S$_0$=(X$_0$⊕Y$_0$), la relazione di uguaglianza sussiste per ogni rango K: S'$_k$=S$_k$.
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$_2$(X)=C$_1$(X)+1]
L'addizione di 1 al bit meno significativo la si ottiene ponendo inizialmente il flip-flop C dello stato 11; 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:
                $X=X_{n}X_{n-1}....X_{1}$
Si usa trasmettere la parola ad n+1 posizioni :
                $X'=X_{n}X_{n-1}....X_{1}P$
dove P è tale che il numero totale degli 1 della parola X' sia pari.
Esempio:
                   ${\begin{cases}X=11010110\\X'=110101101\end{cases}}$
                   ${\begin{cases}X=10010110\\X'=100101100\end{cases}}$
Si può 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:
                $P=1$, $\sum _{i=1}^{n}X_{i}$ è dispari
                $P=0$, $\sum _{i=1}^{n}X_{i}$ è pari
e quindi:
                   $P=|\sum _{i=n}^{n}X_{i}|_{2}$
dove P e X$_i$ sono variabili aritmetiche. Con la convenzione già usata, considerando P e X$_i$ variabili booleane, si ha:
                $P=X_{i}\oplus X_{2}\oplus ....\oplus X_{i}\oplus ....\oplus X_{n}=\oplus \sum _{i=1}^{n}X_{i}$
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$_0$ iniziale è posto a zero.
                $P=Q_{0}\oplus \sum _{i=1}^{n}x_{i}$

### Addizione di 2 numeri con bit di parità

Consideriamo 2 numeri binari X e Y ad n cifre:
             ${\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}}$
alle n cifre siano stati aggiunti i bit di parità P$_x$ e P$_y$:
             ${\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}}$
chiamiamo P$_s$ la cifra di parità x+y.
Calcoliamo l'espressione di P$_s$ mediante le equazioni che danno la somma s$_k$ e il riporto r$_{k+1}$ di rango K in funzione di x$_k$, y$_k$, r$_k$.
Poniamo:
                $S=s_{n-1}s_{n-2}....s_{0}$
(Supponiamo quindi che S sia anch'essa di n cifre).
Si ha allora:
                $P_{s}=s_{n-1}\oplus s_{n-2}\oplus ....\oplus s_{0}=\oplus \sum _{k=0}^{n-1}s_{k}$
                $=\oplus \sum _{k=0}^{n-1}(x_{k}\oplus y_{k}\oplus r_{k})$
                $=(\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})$
                $=P_{x}\oplus P_{y}\oplus (\oplus \sum _{k=0}^{n-1}r_{k})\ \ \ \ \ \ \ \ \ (1.7.1)$
La cifra di parità P$_s$ di S=X+Y è quindi la somma modulo 2 delle cifre dparità P$_x$ e P$_y$di X e Y e dei riporti r$_k$ (k=0, ..., n-1).
Nota. Quando la cifra P$_s$ calcolatamediane la somma effettivamente ottenuta e la cifra P$_s$ 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:
                $X=x_{n-1}x_{n-2}....x_{k}.....x_{1}x_{0}$
chiameremo con X(k) la parola tronca formata dalle k+1 cifre di peso più debole (ranghi da 0 a k).
| S$_k$ | x(k)-y(k) |
| 0 | ≥0 |
| 1 | <0 |
| S$_{k-1}$ | x$_k$ | v$_k$ | S$_k$ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
                $X(k)=x_{k}x_{k-1}....x_{0}$
Consideramo quindi due numeri X e Y e la variabile binaria definita dalla corrispondenza
Da queste condizioni segue che:
                                     $Se\ \ \ \ \ \ x_{k}=y_{k}$
                                     $Allora\ \ \ S_{k}=S_{k-1}$
d'altra parte, se x$_k$≠y$_k$, la diseguaglianza tra x$_k$ e y$_k$ da una parte, x(k) y(k) sono definite nello stesso verso.
quanto detto può, può essere riassunto dalla tabella seguente.
Si ha dunque:
          $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}=$
          $(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})=$
          $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}$
Si riconosce per S$_k$ l'espressione della ritenuta ottenuta durante l'operazione Y-X.
          $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}=$
Si vede quindi che S$_{n-1}$=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$_{n-1}$ della ultima ritenuta di questa differenza. Per costruire il circuito, conviene però mettere la equazione.
          $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}$
sotto la forma seguente:
          $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}=$
          ${\bar {S}}_{k-1}x_{k}{\bar {y}}_{k}\oplus S_{k-1}{\bar {x}}_{k}(y_{k}\oplus 1)\oplus S_{k-1}x_{k}(y_{k}\oplus 1)\oplus S_{k-1}x_{k}y_{k}=$
          ${\bar {S}}_{k-1}x_{k}{\bar {y}}:k\oplus S_{k-1}{\bar {x}}_{k}y:k\oplus S_{k-1}=$
          $({\bar {S}}_{k-1}x_{k}{\bar {y}}_{k}\oplus S_{k-1}{\bar {x}}_{k}y_{k})\oplus S_{k-1}=$
          $({\bar {S}}_{k-1}x_{k}{\bar {y}}_{k}+S_{k-1}{\bar {x}}_{k}y_{k})\oplus S_{k-1}$
Per realizzare questo circuito, è sufficiente considerare un flip-flop di tipo T in cui S$_{k-1}$ 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.
| X | Y | X=Y | X>Y | X<Y |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
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.
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$_i$ e y$_i$ (i=n-1,n-2,...,0) che differisce, determina l'uscita finale del comparatore, a prescindere dal valore di x$_{i-1}$, y$_{i-1}$,...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$_1$ x$_0$ e Y=y$_1$ y$_0$.
La tabella della verità relativa al problema del confronto in parallelo sarà:
    $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}$
Semplificando la funzione mediante un diagramma di Karnaugh si ha:
          $S_{1}=x_{1}{\bar {y}}_{1}+x_{0}{\bar {y}}_{1}{\bar {y}}_{0}+{\bar {y}}_{0}x_{1}x_{0}=$
             ${\overline {\overline {x_{1}{\bar {y}}_{1}+x_{0}{\bar {y}}_{0}(x_{1}+{\bar {y}}_{1})}}}=$
             ${\overline {{\overline {x_{1}{\bar {y}}_{1}}}\cdot {\overline {x_{0}{\bar {y}}_{0}{\overline {\overline {(x_{1}+{\bar {y}}_{1})}}}}}}}=$
             ${\overline {{\overline {x_{1}{\bar {y}}_{1}}}\cdot {\overline {x_{0}{\bar {y}}_{0}({\overline {{\bar {x}}_{1}\cdot y_{1}}})}}}}$
    $2)-x+y\quad S_{2}={\bar {x}}_{1}{\bar {x}}_{0}{\bar {y}}_{1}y_{0}+{\bar {x}}_{1}{\bar {x}}_{0}y_{1}{\bar {y}}_{0}+{\bar {x}}_{1}{\bar {x}}_{0}y_{1}y_{0}+{\bar {x}}_{1}x_{0}y_{1}{\bar {u}}_{0}+{\bar {x}}_{1}x_{0}y_{1}y_{0}+x_{1}{\bar {x}}_{0}y_{1}y_{0}$
Semplificando la funzione mediante un diagramma di Karnaugh si ha:
          $S_{2}={\bar {x}}_{1}y_{1}+{\bar {x}}_{0}y_{1}y_{0}+{\bar {x}}_{1}{\bar {x}}_{0}y_{0}=$
             ${\overline {\overline {{\bar {x}}_{1}y_{1}+y_{0}{\bar {x}}_{0}(y_{1}+{\bar {x}}_{1})}}}=$
             ${\overline {{\overline {{\bar {x}}_{1}y_{1}}}\cdot {\overline {y_{0}{\bar {x}}_{0}{\overline {\overline {(y_{1}+{\bar {x}}_{1})}}}}}}}=$
             ${\overline {{\overline {{\bar {x}}_{1}y_{1}}}\cdot {\overline {y_{0}{\bar {x}}_{0}{\overline {({\bar {y}}_{1}\cdot x_{1})}}}}}}$
    $3)-\quad X=Y$
Dalla tabella della verità si deduce che:
             $S_{3}={\overline {S_{1}+S_{2}}}$
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:
                   $in\ binaro\ puro\ X\ sia\qquad B=(B_{n}B_{n-1}....B_{0})$
                   $in\ binario\ riflesso\ X\ sia\qquad R=R_{n}R_...R_{0}).$
Le formule di conversione (Cap.3 parte I) sono:
                $(R\longrightarrow B):\qquad \oplus B_{p}=\sum _{j=p}^{j=n}R_{j}$
                $(B\longrightarrow R):\qquad R_{p}=B_{p}\oplus B_{p+1}\ ;\ R_{n}=B_{n}$
Le conversioni si fanno più facilmente dalle cifre di peso più forte.
In queste condizioni, poniamo, per la conversione binario riflesso-binario puro:
                   ${\begin{cases}Z_{p}=B_{n-p}\\Q_{p}=B{n-p-1}\ \ \ \ \ (p\geq 1),Q_{B}=0\\E_{p}=R_{n-p}\end{cases}}$
Si ha:
                   ${\begin{cases}Q_{p}=Q_{p}\oplus E_{p}\\Z_{p}=Q_{p}\oplus E_{p}\end{cases}}$
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$_p$ è sufficiente una porta di XOR mentre per l'uscita Q$_{p+1}$ è necessario utilizzare un flip-flop T.
Per la conversione binario puro-binario riflesso, si pone:
                ${\begin{cases}Q_{k}=B_{n-k+1}\\E_{k}=B_{n-k}\\Z_{k}=R_{n-k}\end{cases}}$
si ha quindi
                ${\begin{cases}Q_{k+1}=E_{k}\\Z_{k}=Q_{k}\oplus E_{k}\qquad \qquad \ con\ Q_{0}=0\end{cases}}$
Da cui il circuito nella figura accanto:

## Contatori

Si chiama 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 arrivano 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.

### Primo modo per la determinazione booleana di un contatore binario
#### Incremento in codice binario puro

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:
                $x_{0}^{'}=x_{0}\oplus 1={\bar {x}}_{0}\ \ \ \ \ \ \ \ \ \ \ \ r_{1}=x_{0}\cdot 1$
                $x_{1}^{'}=x_{1}\oplus r_{1}=x_{1}\oplus x_{0}\ \ \ \ \ r_{2}=x_{1}x_{0}$
                $x_{2}^{'}=x_{2}\oplus r_{2}=x_{2}\oplus x_{1}x_{0}\ \ r_{3}=x_{2}x_{1}x_{0}$
                $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}$
                ${\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}}$
Le relazioni che rappresentano il numero x+1 in funzione di x sono:
                ${\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)$

#### 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:
                $x_{0}^{''}=x_{0}\oplus 1={\bar {x}}_{0}\ \ \ \ \ \ \ \ \ \ \ \ r_{1}={\bar {x}}_{0}$
                $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}$
                $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}$
                $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}$
                ${\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)$
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:
                            ${\bar {x}}_{k}^{''}={\bar {x}}_{k}\oplus \coprod _{i=0}^{k-1}{\bar {x}}_{i}$
che insieme alla:
                               $r_{k+1}=\coprod _{i=0}^{k}{\bar {x}}_{i}$
dà la relazione di incremento per i numeri corrispondenti alle parole binarie complementate. Infatti chiamiamo |A| il valore rappresentato dal nome A, si ha:
                   $|x^{'}|=|x|+1$
                   $|x^{''}=|x|-1$
                   $|{\bar {x}}^{'}|=2^{n}-1-|x^{'}|=2^{n}-1-|x|-1=|{\bar {x}}|-1$
                   $|{\bar {x}}^{''}|=2^{n}-1-|x^{''}|=2^{n}-1-|x|+1=|{\bar {x}}|+1$
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:
       $\ \ up-counter:\ \ \ \ \ x_{k}^{n+1}=x_{k}^{n}\oplus E^{n}(\coprod _{i=0}^{k-1}x_{i})_{n}$
       $\ \ down-counter:\ \ x_{k}^{n+1}=x_{k}^{n}\oplus E^{n}(\coprod _{i=0}^{k-1}{\bar {x}}_{i})_{n}$
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$^m$ 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$_i$ 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.
Le cifre x$_k$ 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 ${\bar {x}}_{k}$.
Le x$_k$ fanno parte della rappresentazione di x+1 mentre le ${\bar {x}}_{k}$ sono la rappresentazione binaria di ${\bar {x}}-1$.
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 input 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.
Figura D :
| Tempo | p | A$_3$ | A$_2$ | A$_1$ | a$_{3t}$ | a$_{2t}$ | a$_{1t}$ |
| t$_0$ | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| t$_1$ | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| t$_2$ | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| t$_3$ | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| t$_4$ | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| t$_5$ | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| t$_6$ | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| t$_7$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| t$_8$ | 1 | 0 | 0 | 0 | - | - | - |
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$_3$,A$_2$,A$_1$ rappresentano i loro rispettivi input; p rappresenta gli impulsi in input da conteggiare; t$_0$, t$_1$..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$_{3t}$, a$_{2t}$, a$_{1t}$, 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'input 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$_3$ e A$_2$ non cambiano, quindi i valori di a$_{3t}$ e a$_{2t}$sono entrambi 0 nella prima riga delle colonne relative a a$_{3t}$ e a$_{2t}$.
Però lo stato di A$_1$ cambia da 0 a 1; quindi il valore di a$_{1t}$ è 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$_8$lo stato del contatore è 000 lo stesso che all'istante t$_0$
Il contatore quindi ha un compotamednto ciclico.
Le equazioni di input per i tre flip-flop dedotte dalla tabella della verità D sono:
                      $a_{1t}=p$
                      $2_{2t}=A_{1}\cdot p$
                      $3_{3t}=A_{2}\cdot A_{1}\cdot p$
che possono essere anche scritte come:
                      $a_{1t}=p$
                      $2_{2t}=A_{1}\cdot a_{1t}$
                      $3_{3t}=A_{2}\cdot a_{2t}$
Quando le equazioni di input vengono sostituite nell'equazione di stato di un flip-flop T (Q$_{n+1}$=Q$_n$ ⊕ E$_n$) si ottiene:
                      $A_{1}(\pi )=A_{1}\oplus p$
                      $A_{2}(\pi )=A_{2}\oplus A_{1}p$
                      $A_{3}(\pi )=A_{3}\oplus A_{2}A_{1}p$
Queste sono le equazioni di stato di un contatore e descrivono lo stato dei tre flip-flop.
Applicando queste equazioni a quelle precedenti di input si ottengono i circuiti di fig.A e B.
Figura E :
| Tempo | p | A$_3$ | A$_2$ | A$_1$ | a$_{3r}$ | a$_{3s}$ | a$_{2r}$ | a$_{2s}$ | a$_{1r}$ | a$_{1s}$ |
| t$_0$ | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| t$_1$ | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| t$_2$ | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| t$_3$ | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| t$_4$ | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| t$_5$ | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| t$_6$ | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| t$_7$ | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| t$_8$ | 1 | 0 | 0 | 0 | - | - | - | - | - | - |
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$_{3r}$, a$_{2r}$, a$_{1r}$, rappresentano gli input di riset (R) nei tre flip-flop ed a$_{3s}$, a$_{2s}$, a$_{1s}$, i tre set inputs, p rappresenta gli impulsi di input da conteggiare; t$_0$, t$_1$, 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$_3$ e A$_2$ rimangono immutati, per cui i valori di a$_{3r}$, a$_{3s}$, a$_{2r}$, a$_{2s}$ sono 0 nella prima riga delle colonne sei, sette, otto e nove.
Lo stato A$_1$ però deve cambiare da 0 a 1, quindi il valore di a$_{1r}$ è 0 mentre il valore di a$_{1s}$ è 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:
                   $a_{1s}={\bar {A}}_{1}\cdot p$
                   $a_{2s}={\bar {A}}_{2}\cdot A_{1}\cdot p={\bar {A}}_{2}\cdot a_{1r}$
                   $a_{3s}={\bar {A}}_{3}\cdot A_{2}\cdot A_{1}\cdot p={\bar {A}}_{3}\cdot a_{2r}\ \ \ \ \ \ 2.7.10$
                   $a_{1r}=A_{1}\cdot p$
                   $a_{2r}=A_{2}\cdot A_{1}\cdot p=A_{2}\cdot a_{1r}$
                   $a_{3r}=A_{3}\cdot A_{2}\cdot A_{1}\cdot p=A_{3}\cdot a_{2r}$
Se si sostituiscono le equazioni di input nella equazione di stato di un flip-flop SR ($Q_{n+1}=Q_{n}{\bar {R}}_{n}+S_{n}$), si ottengono le equazioni 2.7.8, cioè le equazioni di stato di un up-counter binario.
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 $A_{1}\cdot {\bar {p}},A_{2}\cdot {\bar {a}}_{1r},A_{3}\cdot {\bar {a}}_{2r}$; queste somme logiche non cambiano il valore delle espressioni di partenza.
Le sei equazioni diventano allora:
                   $a_{1s}=A_{1}\oplus p\ \ \ \ \ \ \ a_{1r}=A_{1}\cdot p$
                   $a_{2s}=A_{2}\oplus a_{1r}\ \ \ \ \ a_{2r}=A_{2}\cdot a_{1r}$
                   $a_{3s}=A_{3}\oplus a_{2r}\ \ \ \ \ a_{3r}=A_{3}\cdot a_{2r}$
Si noti che queste sono le equazioni delle somme e del riporto in output di un half-adder.
Quindi a$_{1s}$ e a$_{1r}$ 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$_{2s}$ e a$_{2r}$ come a$_{3s}$ e a$_{3r}$ 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$^m$.
Per codificare i 10 stati interni si usano generalmente codifiche di tipo binario con almeno 4 digit binari.
| - | I | II |
| Q$_0$ | 0000 | 0011 |
| Q$_1$ | 0001 | 0100 |
| Q$_2$ | 0010 | 0101 |
| Q$_3$ | 0011 | 0110 |
| Q$_4$ | 0100 | 0111 |
| Q$_5$ | 0101 | 1000 |
| Q$_6$ | 0110 | 1001 |
| Q$_7$ | 0111 | 1010 |
| Q$_8$ | 1000 | 1011 |
| Q$_9$ | 1001 | 1100 |
Si è visto (cap.III°, parte Ia) 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.
La configurazione generale di un contatore decimale relativo al codice 8421 sarà:
Il numero rappresentato dallo stato interno dei flip-flop A$_4$, A$_3$, A$_2$ A$_1$, 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.
Figura 2.8.2 :
| p | stato | A$_4$ | A$_3$ | A$_2$ | A$_1$ | a$_{4t}$ | a$_{3t}$ | a$_{2t}$ | a$_{1t}$ |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 4 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 5 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 6 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 9 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
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$_{4t}$, a$_{3t}$, a$_{2t}$, a$_{1t}$ direttamente dalla tabella 2.8.2.
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:
                   $a_{1t}=p$
                   $a_{2t}=A_{1}{\bar {A}}_{4}\cdot p$
                   $a_{3t}=A_{1}A_{2}{\bar {A}}_{4}\cdot p$
                   $a_{4t}={\bar {A}}_{4}A_{3}A_{2}A_{1}\cdot p+A_{4}A_{1}\cdot p$
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:
                   $A_{1}=A_{1}\oplus p$
                   $A_{2}=A_{2}\oplus A_{1}{\bar {A}}_{4}p$
                   $A_{3}=A_{3}\oplus A_{1}A_{2}{\bar {A}}_{4}p$
                   $A_{4}=A_{4}\oplus ({\bar {A}}_{4}A_{3}A_{2}A_{1}p+A_{4}A_{1}p)$
Nella figura viene dato il diagramma logico di una realizzazione di questo circuito.
Figura 2.8.4 :
| p | stato | A$_4$ | A$_3$ | A$_2$ | A$_1$ | a$_{4t}$ | a$_{3t}$ | a$_{2t}$ | a$_{1t}$ |
| 1 | 0 | 0 | 0 | 1 | 10 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 2 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 4 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 6 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 7 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 8 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 9 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
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:
                   $a_{1t}=p$
                   $a_{2t}=A_{1}p+A_{4}A_{3}p$
                   $A_{3t}=a_{1}a_{2}P+a_{4}a_{3}p$
                   $a_{4t}=A_{1}A_{2}A_{3}p+A_{4}A_{3}p$
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 $y_{i}$ e $y_{i+1}$ rappresentanti in codice riflesso due numeri $x_{i}$ e $x_{i+1}$ consecutivi, cioè tali che $x_{i+1}-x_{i}=1$.
Si è visto (cap.3 parte I) che $y_{1}$ e $y_{i+1}$ devono essere adiacenti.
Si possono avere due e si può scrivere cosìcasi.
    - primo caso:$x_{i}pari$
Si ha allora:
                   ${\begin{cases}x_{i}=x_{n}x_{n-1}..x_{k}..x_{1}0\\e\ quindi\\x_{i+1}=x_{n}x_{n-1}..x_{k}..x_{1}1\end{cases}}$
a questi due numeri corrispondono le seguenti rappresentazioni in codice Gray:
             $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})$
          ${\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})$
Si ha quindi:
                $y_{i}\oplus y_{i+1}=000..0..01\ \ \ \ (2.9.1)$
Quindi se $y_{i}$ rappresenta in codice Gray un intero pari, si ottiene $y_{i+1}$, complemetando il digit più a destra.
    -Secondo caso: $x_{i}$ dispari:
$x_{i}$ comincia a destra con un 1 e si può scrvere così:
                   $x_{i}=x_{n}x_{n-1}..x_{k+1}..0\ 1\ 1..1\ 1$
                   $x_{i+1}=x_{n}x_{n-1}..x_{k+1}..1\ 0\ 0..0\ 0$
Da cui:
                   $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$
                   $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$
e:
                   $y_{i}\oplus y_{i+1}=0\ 0\ ..0\ 1..0\ 0..0\ 0\ \ \ \ \ \ (2.9.2)$
Quindi, quando $y_{i}$ 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$_m$...R$_k$...R$_0$) binario riflesso in cui R$_k$ sono gli stati interni di flip-flop T ed indicano il valore delle cifre di rango K in codice Gray.
Chiamiamo con $r_{k}^{n}$ l'ingesso del flip-flop T di rango k all'istante n; si avrà:
                   $R_{k}^{n+1}=R_{k}^{n}\oplus r_{k}^{n}$
da cui:
                   $R_{k}^{n+1}\oplus R_{k}^{n}=r_{k}^{n}$
Conoscendo lo stato di parità del numero $R^{n}$, si possono dedurre dalla (2.9.1) e (2.9.2), le $r_{k}^{n}$, cioè i valori di ingresso da dare ai singoli flip-flop in modo da ottenere il numero $R^{n+1}$.
Ora, la parità del numero $R^{n}$ consideerato è dato dal digit $B_{0}$ della rappresentazione in binario puro.
                   $B_{0}=\oplus \sum _{k=0}^{k}=mR_{k}$
                   $B_{0}=0\ per\ R^{n}\ pari$
                   $B_{0}=1\ per\ R^{n}\ dispari$
Si deducono le seguenti relazioni:
                   $r_{0}^{n}=R_{0}^{n}\oplus R_{0}^{n+1}={\bar {B}}_{0}^{n}E^{n}\ \ \ \ \ (k=0)$
                   $r_{k}^{n}=R_{k}^{n}\oplus R_{k}^{n+1}=R_{k-1}^{n}{\bar {R}}_{k-2}^{n}...{\bar {R}}_{1}^{n}\ {\bar {R}}_{0}^{n}\ B_{0}^{n}\ E^{n}\ \ \ (1=k=m)$
dove E rappresenta la variabile d'ingresso del contatore.
Ponendo:
       $R_{-1}^{n}={\bar {B}}_{0}^{n}$
       $R_{-1}^{n}=0$, $R^{n}$ è dispari
       $R_{-1}^{n}=1$, $R^{n}$ è pari
Si ha allora per $0\leq k\leq m$
$r_{k}^{n}=R_{k}^{n}\oplus R_{k}^{n+1}=R_{k-1}^{n}{\bar {R}}_{k-2}^{n}{\bar {R}}_{k-3}^{n}...{\bar {R}}_{1}^{n}{\bar {R}}_{0}^{n}{\bar {R}}_{-1}^{n}E^{n}\ \ (2.9.3)$
${\bar {R}}_{-1}^{n}=\oplus \sum _{k=0}^{m}\ R_{k}^{n}$
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. È da notare inoltre il segno - su tutte le $R_{i}$ salvo quella di rango k-1 e la presenza della variabile $R_{-1}$ rappresentata da un flip-flop supplementare di parità.
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 $r_{i+1}$ ottenuto all'istante i, sia rappresentativa dello stato interno del circuito.
A partire da uno stato iniziale $r_{i}=0$ risulta che le tre combinazioni di ingresso di $x_{i}\ y_{i}$ (cfr.§2.1.2) 00,01,10 il valore di $r_{i}$, e cioè lo stato interno del circuito non cambia; mentre per la combinazione $x_{i}=y_{i}=1$ 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 $x_{i}y_{i}$ rappresenta la combinazione dei valori d'ingresso, $r_{i}$ lo stato interno; ed in funzione dei valori di $r_{i}$ e di $x_{i}y_{i}$ sono riportati in ogni casella, separati da una /, il nuovo stato interno $r_{i+1}$ ed il valore di uscita $s_{i}$.
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$^3$ 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).
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 $a_{it}$ (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 $A_{4}\ A_{3}\ A_{2}\ A_{1}$ e se consideriamo in particolare lo stato $A_{2}$, 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 $A_{2}$ tenuto conto della variabile d'ingesso p, deve essere:
                   $a_{2t}=A_{1}\ A_{2}\ p$.