
\chapter{\bf Sistemi Logici}

\newcommand{\xbar}{\overline{X}}
\newcommand{\ybar}{\overline{Y}}
\newcommand{\zbar}{\overline{Z}}
\newcommand{\wbar}{\overline{W}}
\newcommand{\abari}{\overline{a}_i}
\newcommand{\bbari}{\overline{b}_i}
\newcommand{\rbar}{\overline{R}_{i-1}}


\section{Sistemi di numerazione}

Nella vita quotidiana siamo abituati ad usare il sistema decimale. In tale 
sistema la ''base'' \'e 10, ci\'o che 
vuol dire l'uso di 10 simboli diversi per rappresentare i numeri da 0 a 9.
I calcolatori elettronici, e con essi tutti i moderni sistemi di 
elettronica digitale, sono basati 
sull'uso di ''celle di memoria'' che possono memorizzare solo due simboli 
diversi, convenzionalmente 
chiamati 0 ed 1.
Per vedere come, a partire da questi due soli simboli, sia possibile 
''costruire'' un intero generico, 
torniamo un attimo al sistema decimale e vediamo di analizzare le operazioni 
mentali che istintivamente 
effettuiamo nello scrivere un numero intero decimale. Vediamo ci\'o con un 
esempio.
Prendiamo il numero 23. Esso implica:
\begin{description}
\item[a]{scrivere la cifra 2}
\item[b]{moltiplicarla per 10}
\item[c]{aggiungere al risultato un 3}
\end{description}

Se aggiungiamo al 23, a destra, un'ulteriore cifra, ad esempio un 7, ci\'o che 
facciamo \'e:
\begin{description}
\item[d]{moltiplicare il risultato delle operazioni a), b), c) precedenti per 
10}
\item[e]{aggiungere al risultato un 7}
\end{description}
Nel sistema adoperato nei calcolatori, detto sistema binario, il meccanismo 
adoperato per costruire un numero \'e il medesimo appena descritto, con la 
differenza che ora i simboli sono solo 0 ed 1 e che 
l'operazione ''moltiplicazione per 10'' diviene ''moltiplicazione per 2''.
Vediamo un esempio. Prendiamo il numero 101. Effettuiamo le operazioni a), b), 
c), d), e) descritte, con 
la modifica menzionata:
\begin{description}
\item[a']{scriviamo un 1}
\item[b']{moltiplichiamo questo per 2}
\item[c']{aggiungiamo al risultato la seconda cifra (0)}
\item[d']{moltiplichiamo il risultato per 2}
\item[e']{aggiungiamo al risultato la terza cifra}
\end{description}
Quindi il numero binario scritto \'e, in decimale, un 5.

E' immediato vedere che, aggiungere al numero precedente uno 0 (a destra) 
equivale a moltiplicare per 2 il 5 ottenuto, ottenendo cos\'i un 10.
Vediamo quindi che, come nel sistema decimale l'aggiunta di uno 0 a destra di un 
numero equivale a 
moltiplicare questo per 10, cos\'i nel sistema binario l'aggiunta di uno 0 a 
destra di un numero equivale a moltiplicare questo per 2.
Proviamo a convertire in decimale il seguente numero binario:
\[
1\;0\;1\;1\;0\;1\;0\;1\;1
\]
Scriveremo:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{|l l l |}
\hline
$1 \times 2$&=&2\\
$2 + 0 $&=&2\\
$2 \times 2$&=&4\\
$4 + 1 $&=&5\\
$5 \times 2$&=&10\\
$10 + 1 $&=&11\\
$11 \times 2$&=&22\\
$22 + 0 $&=&22\\
$22 \times 2$&=&44\\
$44 + 1 $&=&45\\
$45 \times 2$&=&90\\
$90 + 0 $&=&90\\
$90 \times 2$&=&180\\
$180 + 1 $&=&181\\
$181 \times 2$&=&362\\
$362 + 1 $&=&363\\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}




Seguendo il procedimento indicato riusciamo a convertire in decimale, 
mentalmente ed in modo rapido, un numero binario non eccessivamente grande.


Possiamo, in modo equivalente, esprimere il numero decimale (o binario) dato, facendo uso
del metodo delle potenze di 10 (o di 2). Cos\'i ad esempio, il numero decimale 314159 pu\'o
\'e esprimibile come:



\vspace{0.5 cm}
\begin{center}
\begin{tabular}{|c  c |}
\hline
$9 \times 10^0$ & + \\
$5 \times 10^1$ & + \\
$1 \times 10^2$ & + \\
$4 \times 10^3$ & + \\
$1 \times 10^4$ & + \\
$3 \times 10^5$ & = \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}

Vale a dire che ogni cifra che compone il numero dato viene ad essere moltiplicata per una
potenza di 10 pari alla posizione che essa occupa nel numero dato, contando le posizioni
da destra a sinistra ed attribuendo alla cifra posta all'estrema destra la posizione 0.
Il numero \'e la somma di tutti i termini in tal modo ottenuti.

In modo analogo, nel sistema binario si scrive il dato numero come somma delle singole cifre
binarie, moltiplicate ciascuna per una potenza di 2, corrispondente alla posizione che essa
occupa nel numero. Ad esempio, il numero binario 100111010 si esprime come:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c |}
\hline
$0 \times 2^0$&  + \\
$1 \times 2^1$&  + \\
$0 \times 2^2$&  + \\
$1 \times 2^3$&  + \\
$1 \times 2^4$&  + \\
$1 \times 2^5$&  + \\
$0 \times 2^6$&  + \\
$0 \times 2^7$&  + \\
$1 \times 2^8$&  = \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}

Questo metodo, facile da implementare in un computer, \'e meno agevole per effettuare
il calcolo mentalmente in modo rapido.

Pur essendo il sistema binario quello adoperato nei sistemi digitali, altri 
sistemi diversi da quello binario sono spesso adoperati nello sviluppo del 
software che utilizza i sistemi digitali. I pi\'u comuni sono quello 
ottale (base 8) e quello esadecimale (base 16).
Nel sistema ottale si dispone di 8 simboli (da 0 a 7) e si ''costruiscono'' i 
numeri maggiori di 7 seguendo i 
passi indicati ai punti a) ..... e), con la modifica del 10 in 8. Vediamo un 
esempio:
\[
72_8\:=\:58_{10}
\]
Cio\'e:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{|l l l |}
\hline
$7 \times 8$&=&56\\
$56 + 2 $&=&58\\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}



Ovviamente, in tale sistema il numero 8 si scriver\'a ''10'', cio\'e $1\times 
8$.

Nel sistema esadecimale si dispone di 16 simboli (i numeri decimali da 0 a 9, e 
le lettere A, B, C, D, E, F). Abbiamo:
\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| l l l|}
\hline
A & $\rightarrow$ & $10_{10}$ \\
B & $\rightarrow$ & $11_{10}$ \\
C & $\rightarrow$ & $12_{10}$ \\
D & $\rightarrow$ & $13_{10}$ \\
E & $\rightarrow$ & $14_{10}$ \\
F & $\rightarrow$ & $15_{10}$ \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}

I numeri maggiori di 15 vengono ''costruiti'' seguendo la ricetta delineata ai 
punti a) ..... e), con la 
sostituzione del 10 con il 16. Ad esempio il numero esadecimale ''1A'' in 
decimale \'e:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{|l l l l l|}
\hline
1 & $\times$ & 16 & = & 16 \\
16 & + & A & = & 26\\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}




Il numero esadecimale ''FF'' \'e uguale a $(15 \times 16)\, + \,15\: =\: 255$.

\'E facile convertire in ottale un numero binario.
Basta tener presente che un insieme di tre bit binari pu\'o rappresentare i 
numeri base del sistema ottale, cio\'e i numeri tra 0 e 7. Possiamo allora 
raggruppare tre a tre i bit che costituiscono il numero binario dato 
(a partire dalla destra) per ottenere il numero in ottale.
Cos\'i ad esempio:
\[
[\underbrace{110}_6 \underbrace{101}_5 \underbrace{001}_1 
\underbrace{111}_7]_2\:=\:[6517]_8
\]


In modo analogo, \'e possibile convertire in esadecimale un generico numero 
binario. Questa volta si dovranno raggruppare quattro alla volta i bit che 
costituiscono il numero binario dato e sostituire a ciascun gruppo il 
corrispondente numero esadecimale. Ad esempio, il numero prima convertito in 
ottale, diventa:

\[
[\underbrace{1101}_D \underbrace{0100}_4 \underbrace{1111}_F]_2\:=\:[D4F]_{16}
\]


E' facile vedere poi come si possa agevolmente convertire un numero ottale o 
esadecimale in un numero binario. A tale scopo \'e sufficiente convertire in 
binario ciascuna delle cifre che costituiscono il numero ottale o esadecimale.

Ci si pu\'o chiedere ora come si possa convertire viceversa un numero decimale 
dato in una base 2. La procedura \'e la seguente:
\begin{description}

\item[(a)] {si divide per 2 il numero decimale assegnato, ottenendo un quoziente 
ed un resto. Notiamo che il resto sar\'a 0 (se il numero era pari) o 1 (se era 
dispari)}
\item[(b)] {si divide per 2 il quoziente ottenuto. Si ottiene un nuovo quoziente 
ed un nuovo resto}
\item[(c)] {si continua l'operazione, fino a che il quoziente non sia nullo}
\item[(d)] {la serie dei resti ottenuti, letta in ordine inverso, fornir\'a il 
numero binario richiesto.}
\end{description}

Vediamo ci\'o con un esempio

\[
[374]_{10}\:=\:[?]_2
\]

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| r r r|}
\hline
Divisione & Quoziente & Resto \\
374/2 & 187 & 0 \\
187/2 & 93 & 1 \\
93/2  & 46 & 1 \\
46/2  & 23 & 0 \\
23/2  & 11 & 1 \\
11/2  & 5  & 1 \\
5/2   & 2  & 1 \\
2/2   & 1  & 0 \\
1/2   & 0  & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}



Il numero binario \'e quindi:
\[
	1\: 0\: 1\: 1\: 1\: 0\: 1\: 1\: 0
\]

Cos\'i come nel sistema decimale le cifre dopo la virgola decimale (o il punto 
decimale) vengono ad essere moltiplicate per potenza negative e crescenti 
di 10, cos\'i nel sistema binario le cifre dopo la virgola (binaria) vengono ad 
essere moltiplicate per potenze negative e crescenti 
di 2. Ad esempio:
\[
[101.1101]_2\:=\:[5.\left(\frac{1}{2}+\frac{1}{4}+\frac{0}{8}+\frac{1}{16}\right
)]_{10}
\]
Se vogliamo convertire un numero decimale frazionario in un numero binario, 
potremo procedere secondo le linee del seguente esempio.

Supponiamo di dover convertire il numero decimale 0.8125. Moltiplichiamo il 
numero per 2 e chiediamoci se il risultato \'e $\ge 1$.
\[
0.8125 \times 2 \:=\:1.625\:\:\:\ge 1
\]
 

Poich\'e la disuguaglianza \'e soddisfatta, scriviamo un 1, sottraiamo 1 dal 
risultato e moltiplichiamo per 2 (se non lo fosse scriveremmo 0 e 
moltiplicheremmo ancora per 2):

\[1.625\:-\:1\:=\:0.625
\]

Moltiplichiamo 0.625 per 2 e verifichiamo nuovamente se il numero ottenuto \'e   
$\ge 1$. Se lo \'e scriviamo un altro 1 e sottraiamo 1 dal numero dato.

\[
0.625 \times 2 \:=\:1.25 \: \ge 1
\]
\[
1.25 \:-\:1\:=\:0.25\]

Moltiplichiamo ancora 0.25 per 2 e verifichiamo:
\[
0.25 \times 2 \: = \: 0.5 \:\: < 1
\]

Poich\'e questa volta la disuguaglianza non \'e soddisfatta, scriviamo uno zero 
anzich\'e un 1. 

Moltiplichiamo nuovamente per 2:
\[
0.5 \times 2 \:=\:1 \:\ge\:1
\]
\[
1\:-\:1\:=\:0\:\:\:\:fine\:del\:processo
\]

La sequenza di 1 e 0 scritta, letta dall'alto verso il basso, rappresenta il 
numero frazionario desiderato. Nel nostro caso esso \'e:
\[
0.1101\
\]
Verifichiamo:
\[
0.1101\:=\:\frac{1}{2}+\frac{1}{4}+\frac{0}{8}+\frac{1}{16}\:=\:0.8125
\]

In una macchina a 32 bit, il pi\'u grande numero intero che \'e possibile 
rappresentare, tenendo conto del fatto che un bit \'e usato per il segno, \'e:
\[
N\:=\:2147483648
\]
Si tratta di un numero grande, ma non abbastanza per tutte le situazioni. Per 
rappresentare numeri molto pi\'u grandi (o anche numero molto minori di 1) si 
ricorre alla rappresentazione che fa uso della caratteristica e della parte 
frazionaria. Ci\'o \'e in fondo analogo a quanto facciamo nel sistema decimale per 
rappresentare numeri molto grandi o molto piccoli, ricorrendo alla notazione 
esponenziale. Ad esempio, per il numero di Avogadro scriviamo:
\[
N_A\:=\:6.022045\:10^{23}
\]

e per la costante di Boltzmann:
\[
K\:=\:1.380662\:10^{-23}
\]
Cos\'i, nei computer, un numero pu\'o essere rappresentato dal prodotto di un numero 
binario per una potenza di 16, dove l'esponente \'e specificato da un secondo 
numero binario. Ad esempio, nel vecchio sistema IBM/370, un ''parola'' di 32 bit 
era divisa in due gruppi di bits, come mostrato di seguito:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| l | l | l|}
\hline
S& caratteristica (7 bits) & parte frazionaria (24 bits) \\
\hline
0&1~~~~~~~~~~~~~~~~~~~~~~~~~7&8~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~31 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}





Il bit 0, all'estrema sinistra, \'e adoperato per il segno. I successivi 7 bit 
sono adoperati per la caratteristica. 
I rimanenti 24 costituiscono la parte frazionaria. Il punto decimale 
va immaginato alla sinistra del bit pi\'u significativo della parte frazionaria.

La caratteristica \'e ottenuta in realt\'a aggiungendo 64 all'esponente vero e 
proprio. Ci\'o vien fatto allo scopo di riuscire a rappresentare anche esponenti 
molto minori di zero.

Notiamo che i 7 bits della caratteristica possono rappresentare i numeri 
decimali che vanno da 0 a 127. 
Ad esempio, la rappresentazione di un numero che in notazione decimale fosse:

\[
N_D\:=\:F_D\:10^{C_D}
\]

dove $F_D$ \'e la parte frazionaria (.6022045 nel caso del numero di Avogadro) e 
$C_D$ la caratteristica nello stesso esempio (cio\'e 24), si otterrebbe nel modo 
seguente:


a) si converte in binario la parte frazionaria, conservando solo 24 bits

b) si converte $10^{C_D}$   in $16^{C_H}$ , cio\'e in una potenza di 16

c) al valore di $C_H$ ottenuto si somma 64 (decimale). Questa sar\'a la 
caratteristica del numero in esame.

La rappresentazione descritta \'e quella dei numeri detti ''floating point'' 
(ovvero, in italiano, ''in virgola mobile'') quando si adotti la ''singola 
precisione''. Per calcoli pi\'u accurati \'e possibile usare ''parole'' 
costituite da gruppi di 2 parole singole (ovvero 64 bit) o anche di 4 parole 
singole (ovvero 128 bit). 

Poich\'e un gruppo di 8 bits costituisce quello che \'e chiamato un ''byte'', 
una parola ''singola precisione'' \'e costituita da 4 bytes, una in ''doppia 
precisione'' da 8 bytes, ed una in ''precisione estesa'' da 16 bytes.


\section{Il codice Grey}

Sempre restando nell'ambito di una logica di tipo binario, occorre notare che la 
costruzione che abbiamo descritto della corrispondenza tra numeri binari e 
numeri decimali, suggerita dall'analogia con il sistema decimale, non \'e unica. 
Infatti si pu\'o altrettanto facilmente ipotizzare una generica corrispondenza tra 
numeri binari e numeri decimali ed adottarla come ''sistema di numerazione 
binaria''. Tale corrispondenza deve essere implementabile tramite una precisa 
''ricetta''. Ci\'o \'e fatto ad esempio dal codice Grey.
In tale codice, i numeri binari 0 ed 1 corrispondono allo 0 ed 1 decimale 
rispettivamente:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| l  l  l  l |}
\hline
0000& $\rightarrow$ & 0 &~~~~~~~~~~~ \\
0001& $\rightarrow$ & 1 &~~~~~~~~~~~ \\
$----$&$---$&$-----$&prima riflessione \\
0011& $\rightarrow$ & 2 &~~~~~~~~~~~ \\
0010& $\rightarrow$ & 3 &~~~~~~~~~~~ \\
$----$&$---$&$-----$&seconda riflessione \\
0110& $\rightarrow$ & 4 &~~~~~~~~~~~ \\
0111& $\rightarrow$ & 5 &~~~~~~~~~~~ \\
0101& $\rightarrow$ & 6 &~~~~~~~~~~~ \\
0100& $\rightarrow$ & 7 &~~~~~~~~~~~ \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}




Per ''costruire'' la configurazione binaria corrispondente al 2 ed al 3 
decimali, effettuiamo una ''riflessione'' delle prime due righe nello specchio 
rappresentato dalla prima linea tratteggiata e contemporaneamente cambiamo in 1 
gli zeri che vengono a comparire nella seconda colonna a partire dalla destra.
Per ''costruire'' ora la configurazione binaria corrispondente al 4, 5, 6, 7 
decimali, effettuiamo una nuova riflessione delle prime quattro righe nello 
specchio rappresentato dalla seconda linea tratteggiata, e contemporaneamente 
cambiamo in 1 gli zeri che compaiono nella terza colonna, a partire dalla 
destra, delle quattro nuove righe.

Il processo pu\'o esser proseguito quanto si vuole. Notiamo che una caratteristica 
del sistema Grey \'e che nel passare da un numero al successivo, uno solo dei 
bit cambia. Cos\'i, nel passare dal 2 al 3 cambia solo il bit meno significativo, 
nel passare dal 3 al 4 cambia solo il terzo bit, etc. 
Ci\'o non accade nel sistema binario ''convenzionale'' dove, nel passaggio da un 
valore a quello adiacente possono cambiare un numero arbitrario di bits.
Ci\'o \'e un indubbio vantaggio del codice Grey in applicazioni elettroniche, dove 
i tempi di commutazione degli elementi che memorizzano i diversi bit possono 
differire leggermente.

\section{Porte logiche}

L'informazione elementare alla base del funzionamento di un qualsiasi sistema 
digitale \'e il bit. I due valori che questo pu\'o acquistare, che 
convenzionalmente chiamiamo 0 ed 1, sono nella pratica associati a 
due possibili valori di tensione (ad esempio 0V e 5V) o di corrente. La 
convenzione che pu\'o essere adottata nello stabilire la corrispondenza tra stato 
logico (0 o 1) e livello di tensione (0V o 5V) stabilisce il tipo di logica. Se 
allo 0 logico facciamo corrispondere il pi\'u basso dei valori di tensione ed 
all'1 il pi\'u alto, diremo che stiamo lavorando in logica positiva. Viceversa, 
possiamo far corrispondere allo 0 logico il livello alto di tensione ed all'1 
logico il livello basso; diremo che in tal caso stiamo lavorando in logica 
negativa.

Una variabile binaria pu\'o acquistare o il valore 0 o il valore 1. A partire da 
una o pi\'u variabili binarie possiamo poi, come vedremo tra un attimo, costruire 
delle funzioni di questa/e variabile/i.
Se una variabile, o funzione di variabili, acquista il valore 1, diremo anche 
che essa \'e vera (True = T). Se acquista il valore logico 0, diremo che \'e 
falsa (False = F). Ovviamente, come una variabile, cos\'i anche una funzione 
logica di variabili logiche pu\'o assumere solo i valori 1=T o 0=F.

La pi\'u semplice delle funzioni (logiche) di variabile logica \'e il NOT, o 
invertitore.
Se A \'e la variabile, l'applicazione della funzione NOT fornisce una nuova 
variabile che \'e il complemento 
(logico) di A. Cio\'e, se A = 0, il NOT di A vale 1; se A = 1, il NOT vale 0.
Il simbolo per indicare la negazione (cio\'e il NOT) \'e:

\[
NOT(A)\:=\:\overline{A}
\]

Il simbolo del circuito elettronico che implementa tale operazione \'e quello 
mostrato in figura~\ref{not_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=not_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{not_symbol}
\end{figure}

Una funzione logica pu\'o esser caratterizzata scrivendo esplicitamente il valore 
assunto dalla funzione per ogni possibile valore del/degli ingressi. In genere 
si fa ci\'o sotto forma di una tabella, detta ''tabella delle verit\'a''. Nel caso 
della funzione NOT questa \'e:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c | c |}
\hline \
A& $Y=\overline{A}$ \\
\hline
0& 1 \\
1& 0 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}


La funzione OR a due ingressi \'e definita dalla seguente tabella delle 
verit\'a:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c | c |}
\hline
A& B& $Y=A\:+\:B$ \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}



Cio\'e l'OR di A e B assume il valore 1 se almeno uno dei due ingressi A e B 
assume il valore 1.
L'operatore che indica la funzione OR \'e il +:

Il simbolo del circuito logico che implementa la funzione OR \'e mostrato in 
figura~\ref{or_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=or_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{or_symbol}
\end{figure}


La funzione AND a due ingressi \'e definita dalla seguente tabelle delle 
verit\'a:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c | c |}
\hline
A& B& $Y=A\:\cdot\:B$ \\
\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}



Vediamo dalla tabella che l'AND vale 1 se e solo se entrambi gli ingressi 
valgono 1.
Il simbolo del circuito logico che implementa la funzione AND \'e mostrato
in figura~\ref{and_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=and_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{and_symbol}
\end{figure}


L'operatore che indica la funzione AND \'e quella della moltiplicazione: 
$A \cdot B$: 

Porte NOR e NAND a pi\'u di due ingressi sono possibili. L'uscita di una funzione 
OR a pi\'u ingressi vale 1 se almeno uno degli ingressi vale 1. L'uscita di una 
funzione AND a pi\'u ingressi vale 1 se tutti gli ingressi valgono 1.
E' ovviamente possibile combinare due o pi\'u funzioni logiche per definire 
nuove funzioni.
Cos\'i ad esempio, un AND seguito da un NOT realizza la funzione nota come NAND 
(= NOT.AND). La tabella delle verit\'a di un NAND \'e:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c | c |}
\hline
A& B& $Y=\overline{A\:\cdot\:B}$ \\
\hline
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}


Il simbolo del circuito elettronico che implementa la porta NAND \'e mostrato in
figura~\ref{nand_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=nand_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{nand_symbol}
\end{figure}


Un OR seguito da un NOT realizza la funzione nota come NOR (= NOT.OR), la cui 
tabella delle verit\'a \'e:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c | c |}
\hline
A& B& $Y=\overline{A\:+\:B}$ \\
\hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}


Il simbolo del circuito elettronico che implementa la porta NOR \'e mostrato in
figura~\ref{nor_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=nor_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{nor_symbol}
\end{figure}


La funzione ''OR esclusivo'', indicata con XOR, ha la medesima tabella delle 
verit\'a della funzione OR, ad eccezione della riga con A = B = 1, in cui l'XOR 
vale 0. Possiamo pensare all'XOR come un ''OR con esclusione dell'AND''. Infatti 
la riga con A = B = 1 \'e quella per la quale \'e soddisfatto l'AND di A e B.
Il simbolo del circuito che implementa la funzione XOR \'e mostrato in 
figura~\ref{xor_symbol}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=xor_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{}
\protect\label{xor_symbol}
\end{figure}


Il simbolo per l'XOR \'e il $\bigoplus$.

\section{Algebra di Boole}
\subsection{Identit\'a Booleane}

A partire da due o pi\'u variabili logiche A, B, C etc., \'e possibile costruire 
espressioni logiche di varia complessit\'a. Tali espressioni possono essere 
semplificate facendo uso delle regole dell'algebra di Boole. 
Tali regole sono nella pi\'u gran parte dei casi immediatamente ovvie; in altri 
possono essere dimostrate costruendo la relativa tabella delle verit\'a per 
evidenziare l'uguaglianza dei due membri dell'equazione.

Elenchiamo le pi\'u frequenti:

\begin{enumerate}
\item{$A+B+C\:=\:(A+B)\: + \:C \:=\: A\: +\: (B+C)$ \hfill\ (propriet\'a 
associativa)}
\item{$A \cdot B \cdot C \:=\: (A \cdot B) \cdot C \:=\:A \cdot (B \cdot C)$ \hfill\ (propriet\'a associativa)}
\item{$A+B\:=\:B+A$ \hfill\ (propriet\'a commutativa)}
\item{$A \cdot B \:=\: B \cdot A$ \hfill\ (propriet\'a commutativa)}
\item{$A+A\:=\:A $ \hfill\ (identit\'a)}
\item{$A \cdot A \:=\:A$ \hfill\ (identit\'a)}
\item{$A+1 \:=\:1 $}
\item{$A+0\:=\:A $}
\item{$A \cdot 1 \:=\:A$}
\item{$A \cdot 0 \:=\:0$}
\item{$A \cdot (B+C)\:=\:A \cdot B + A \cdot C $ \hfill\ (propriet\'a distributiva)}
\item{$A + (A \cdot B) \:=\:A$ \hfill\ (ridondanza)}
\item{$A \cdot (A+B)\:=\:A$ \hfill\ (ridondanza)}
\item{$A+(B \cdot C)\:=\:(A+B) \cdot (A+C)$}
\item{$\overline{\overline{A}}\:=\:A$}
\item{$A \cdot \overline{A}\:=\:0$}
\item{$A + \overline{A}\:=\:1$}
\item{$A +(\overline{A} \cdot B) \:=\:A + B$}
\item{$A \cdot (\overline{A} + B) \:=\: A \cdot B$}
\end{enumerate}
Dimostriamo, facendo uso del metodo della tabella della verit\'a, la (14):

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c c c | c  c | c  c | c |}
\hline
A& B& C & $(B \cdot C)$ & $A+(B \cdot C)$ & $(A+B)$ & $(A+C)$ & $(A+B) \cdot 
(A+C)$ \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}




Notiamo che se A = 1 in logica positiva, allora A = 0 in logica negativa. 
Consideriamo ora la tabellina dell'AND (in logica positiva):


\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c  c | c  c | c | c |}
\hline
$\overline{A}$ & $\overline{B}$ & $A$ & $B$ & $A \cdot B$ & $\overline{A \cdot 
B} \:=\:\overline{A}+\overline{B}$ \\
\hline
1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}




Cambiare logica vuol dire complementare tutto, cio\'e scambiare 0 con 1 nella 
tabellina. Abbiamo indicato ci\'o nelle prime due colonne e nell'ultima. Notiamo 
che l'ultima colonna coincide con l'OR delle prime due. 
Possiamo allora dire che: ''un AND in logica positiva diviene un OR in logica 
negativa''. Questo risultato \'e anche conseguenza delle leggi di De Morgan, che 
esamineremo tra poco.


Esaminiamo ora la tabella delle verit\'a della funzione XOR ($Y\:=\:A\bigoplus 
B$).

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c c | c |}
\hline
$A$ & $B$ & $Y \:=\: A \bigoplus B$ \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}

La tabella ci permette di scrivere diverse espressioni della funzione XOR, 
facendo uso di funzioni OR, NOT ed AND. Una prima espressione si pu\'o ottenere 
esaminando le due righe in corrispondenza delle quali \'e Y = 1. La prima di 
queste corrisponde a A falso e B vero, cio\'e all'AND: $\overline{A} \cdot B$; 
la seconda corrisponde ad $A \cdot \overline{B}$. Poich\'e Y vale 1 sia nel 
primo caso che nel secondo, potremo scrivere:
\begin{equation}
1)\:A \bigoplus B \:=\: \overline{A} \cdot B + A \cdot \overline{B} \label{eq:xor_prima}
\end{equation}

Una seconda espressione dell'XOR pu\'o essere ottenuta notando che l'XOR \'e vero 
quando \'e vero l'OR a condizione che sia falso l'AND. Cio\'e:

\begin{equation}
2)\: A \bigoplus B \:=\:(A+B)\cdot (\overline{A \cdot B})  \label{eq:xor_seconda}
\end{equation}

Una terza espressione si pu\'o ottenere notando che l'XOR \'e vero se \'e vero A 
o B: $(A + B)$ purch\'e uno dei due sia falso ($\overline{A}+\overline{B}$):

\begin{equation}
3)\: A \bigoplus B \:=\:(A+B) \cdot (\overline{A} + \overline{B})  \label{eq:xor_terza}
\end{equation}

Infine notiamo che il complemento dell'XOR \'e vero (cio\'e l'XOR \'e falso) 
nella prima e quarta riga della tabella delle verit\'a.

Queste corrispondono a $\overline{A} \cdot \overline{B}$ (la prima) e a $A \cdot 
B$ l'ultima. Quindi:

\[
\overline{A \bigoplus B} \:=\: \overline{A} \cdot \overline{B} + A \cdot B
\]
Cio\'e:

\begin{equation}
4) \: A \bigoplus B \:=\:\overline{\overline{A} \cdot \overline{B} + A \cdot B }  \label{eq:xor_quarta}
\end{equation}

L'implementazione  dei quattro modi indicati per realizzare la funzione XOR
\'e indicata in figura~\ref{xor_prima},~\ref{xor_seconda},~\ref{xor_terza} ed~\ref{xor_quarta}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=xor_prima,width=13.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{xor_prima}
\end{figure}


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=xor_seconda,width=12.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{xor_seconda}
\end{figure}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=xor_terza,width=12.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{xor_terza}
\end{figure}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=xor_quarta,width=12.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{xor_quarta}
\end{figure}



\section{Leggi di De Morgan}

L'equivalenza delle quattro diverse implementazioni della funzione XOR, mostrata 
nella sezione 
precedente, pu\'o esser dimostrata in modo rigoroso facendo uso delle leggi di De 
Morgan. Esse sono:

\begin{description}
\item{$\overline{A \cdot B \cdot C \cdots}\:=\:\overline{A} + \overline{B} + \overline{C} + \cdots$}
\item{$\overline{A + B + C + \cdots}\:=\:\overline{A} \cdot \overline{B} \cdot \overline{C} \cdots $}
\end{description}

La prima di queste ci dice che il complemento dell'AND di pi\'u variabili logiche 
\'e uguale all'OR dei 
complementi delle singole variabili. La seconda dice che il complemento dell'OR 
di pi\'u variabili logiche 
\'e uguale all'AND dei complementi delle singole variabili.
Le leggi di De Morgan sono utilissime nel semplificare o trasformare espressioni 
logiche in pi\'u variabili.

Vediamo ora come, facendo uso di tali leggi, si possa facilmente dimostrare 
l'equivalenza delle quattro diverse espressioni che abbiamo fornito per la funzione XOR.
Partiamo ad esempio dall'espressione~\ref{eq:xor_prima}:
\[
A \bigoplus B \:=\: \overline{A} \cdot B + A \cdot \overline{B}
\]

Complementandola due volte, otteniamo:

\[
\cdots \overline{\overline{\overline{A} \cdot B + A \cdot \overline{B}}}\:=\:\overline{\overline{\overline{A}\cdot B}\cdot \overline{A \cdot \overline{B}}}\:=\:
\overline{(A + \overline{B}) \cdot (B + \overline{A})}\:=\:\overline{A \cdot B + \overline{A} \cdot \overline{B}}
\]

ci\'o troviamo la~\ref{eq:xor_quarta} data in precedenza.

Sviluppando quest'ultima troviamo poi:

\[\overline{A \cdot B + \overline{A} \cdot \overline{B}} \:=\:\overline{A \cdot B} \cdot \overline{\overline{A} \cdot \overline{B}}\:=\:(\overline{A} + \overline{B}) \cdot (A + B)
\]

Cio\'e la forma~\ref{eq:xor_terza} dell'XOR.

Infine, complementando due volte il primo termine nell'ultimo membro dell'espressione appena scritta:

\[
\overline{\overline{(\overline{A} + \overline{B})}} \cdot (A + B)\:=\:(\overline{A \cdot B})\cdot ( A + B)
\]

che \'e la forma~\ref{eq:xor_seconda} dell'XOR. E' cos\'i dimostrata l'equivalenza delle quattro 
forme.

Facendo uso dell'algebra di Boole e delle leggi di De Morgan \'e possibile 
semplificare proposizioni logiche complete. 
E' inoltre possibile ottenere delle realizzazioni concrete di funzioni logiche, facendo 
uso di pochi componenti base. Ad esempio, \'e facile vedere come la funzione OR 
possa esser ottenuta facendo uso di sole porte NAND.
Consideriamo infatti un OR con due ingressi A e B:
\[
A + B
\]


Negando due volte otteniamo:

\[
\overline{\overline{A + B}}\:=\:\overline{\overline{A} \cdot \overline{B}}
\]

cio\'e il simbolo circuitale mostrato in figura~\ref{or_da_nand}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=or_da_nand,width=8.0 cm,
height=4 cm}}\end{center}
\caption{}
\protect\label{or_da_nand}
\end{figure}


\section{Forme standard di funzioni logiche}



Nel seguito, per semplificare la notazione, ometteremo il simbolo $\cdot$ che indica il prodotto
logico di cue variabili.

Esistono due diverse forme standard per le funzioni logiche. Esse sono 
rispettivamente la \emph{somma di prodotti} ed il \emph{prodotto di somme}. 
Un esempio del primo tipo di funzione \'e:
\[
X   Y + \overline{W}   X + \overline{W}   Y   Z + X   Y   Z
\]


dove compaiono le quattro variabili X,Y,Z,W.

Facciamo vedere ora come questa possa essere riscritta nella forma di un 
\emph{prodotto di somme}. 
L'espressione pu\'o essere riscritta nella forma:


\begin{eqnarray*}
\lefteqn{X   Y   X + \overline{W}   X + \overline{W}   Y   Z + X   Y   Y   Z = } \\ 
& & (\overline{W} + X   Y)   X + (\overline{W} + X   Y)   Y   Z = \\
& & (\overline{W} + X   Y)  (X + Y   Z)	
\end{eqnarray*}
che \'e un prodotto di somme.

Si dice che una somma di prodotti \'e in forma estesa se ciascun termine della 
somma contiene tutte le variabili. Tale forma emerge in modo naturale se la funzione logica \'e 
ottenuta da una tabella delle verit\'a. 
Vediamo ci\'o con un esempio.

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c c c | c |}
\hline
$X$ & $Y$ & $Z$ & $L$ \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}


cio\'e:

\[
L\:=\: \xbar   Y  \zbar +  \xbar   Y   Z + X    \ybar    \zbar + X   Y    \zbar + X   Y   Z
\]


Ciascuno dei termini della somma va sotto il nome di ''minterm''. Notiamo che 
l'espressione scritta pu\'o esser semplificata:
\[
L\:=\: \xbar   Y   ( \zbar + Z) + X    \ybar    \zbar +
X   Y  (Z +  \zbar) \:=\: \xbar   Y + X    \ybar    \zbar
+ X   Y =
\]
\[
= Y   (X +  \xbar) + X    \ybar    \zbar\:=\:Y +  \ybar   X    \zbar\:=\:Y + X    \zbar
\]



Un esempio di prodotto di somme \'e:

\[
L\:=\:(\wbar + X Y)(X + YZ)
\]

Ciascuno dei termini del prodotto \'e un ''maxterm''.
La funzione scritta pu\'o facilmente esser trasformata in una nuova espressione 
dove ciascun termine del prodotto contiene solo due delle variabili.
Facendo uso della relazione:

\[
A+(BC)\:=\:(A+B)\cdot (A+C)
\]

troviamo:

\[
L\:=\:(\wbar + X)(\wbar + Y)(X + Y)(X + Z)
\]


Diremo che il prodotto di somma \'e in \emph{forma estesa} se ciascuna somma contiene 
tutte le variabili. Tale forma pu\'o facilmente essere ottenuta nel caso in cui la funzione L sia definita da una tabella della verit\'a. 
Ad esempio, facendo uso della medesima tabella usata sopra, calcoliamo $\overline{L}$:

\[
\overline{L}\:=\:\xbar \ybar \zbar + \xbar \ybar Z + X \ybar Z
\]


da cui:

\[
\overline{\overline{L}}\:=\:L\:=\:\overline{\xbar \ybar \zbar + \xbar \ybar Z + X \ybar Z}\:=\:
\overline{\xbar \ybar \zbar} \cdot \overline{\xbar \ybar Z} \cdot{X \ybar Z}=
\]

\[
(X + Y + Z)(X + Y + \zbar)(\xbar Y \zbar)
\]


che \'e un prodotto di somme in forma estesa.


\section{Operazioni aritmetiche}

Vediamo ora come, facendo uso di circuiti elementari che realizzino delle 
funzioni logiche, sia possibile effettuare la somma o la differenza di numeri binari.
Immaginiamo di voler effettuare la somma di due bit a  e  b. Indichiamo con $\Sigma$ la 
somma e con  $R$  il riporto. \'E facile verificare che essi sono dati dalla seguente
tabella delle verit\'a:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c c | c c |}
\hline
$a$ & $b$ & $\Sigma$ & $R$ \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}


Vediamo facilmente che $\Sigma$ coincide con $a \bigoplus b$ , mentre R coincide con $a \cdot b$.

Immaginiamo di avere due numeri, di n bit ciascuno e contiamo i bit di ciascuno 
dei numeri a partire dal bit meno significativo (il pi\'u a destra di tutti) 
da 0 ad (n-1). 
Cio\'e:
\[
\underline{a}\:=\:a_{n-1} a_{n-2} \cdots a_3 a_2 a_1 a_0
\]
\[
\underline{b}\:=\:b_{n-1} b_{n-2} \cdots b_3 b_2 b_1 b_0
\]

La somma del bit $i^{emo}$ di a e del corrispondente di b potr\'a essere ottenuto tramite 
un circuito che calcoli l'OR esclusivo e l'AND di $a_i$ e $b_i$. 
Un tale circuito va sotto il nome di ''semisommatore''o ''Half Adder''~(HA). 
In termini circuitali avremo quanto mostrato in figura~\ref{half_adder}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=half_adder,width=7.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{half_adder}
\end{figure}

Per effettuare la somma dei numeri a e b occorrer\'a un circuito che sommi alla 
somma dei due bit $a_i$ e $b_i$, il riporto $R_{i-1}$ dalla somma dei due bit precedenti 
(meno significativi).
Tale circuito pu\'o in linea di principio essere ottenuto da due H.A., nel modo 
indicato in figura~\ref{full_adder}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=full_adder,width=8.0 cm,
height=4 cm}}\end{center}
\caption{}
\protect\label{full_adder}
\end{figure}

E' facile verificare che il riporto finale $R_i$ \'e l'XOR del riporto $R_{i}'$  dal 
primo semisommatore e di quello $R_{i}''$  dal secondo.


Un modo pi\'u pratico di effettuare la somma dei due bit e del riporto della somma 
dei due bit  precedenti  \'e ottenibile analizzando la tabella delle verit\'a per 
i termini $a_i$, $b_i$, $R_{i-1}$, $\Sigma_i$, $R_i$ mostrata qui di seguito.

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{| c c c | c c |}
\hline
$a_i$ & $b_i$ & $R_{i-1}$ & $\Sigma_i$ & $R_i$ \\
\hline
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vspace{0.5 cm}



Dalla tabella delle verit\'a si ottiene:
\[
\Sigma_i\:=\:\abari b_i \rbar + a_i \bbari \rbar + \abari \bbari R_{i-1} + a_i b_i R_{i-1}
\]
\[
R_i \:=\: a_i b_i \rbar + \abari b_i R_{i-1} + a_i \bbari R_{i-1} + a_i b_i R_{i-1}
\]


Notiamo che $R_i$ pu\'o essere semplificato in:
\[
R_i\:=\:b_i R_{i-1} + a_i b_i + a_i R_{i-1}
\]


$\Sigma_i$ ed $R_i$ possono facilmente essere realizzati utilizzando porte logiche 
elementari.


\section{Sottrazione binaria}

Ammettiamo di voler sottrarre un numero binario A  da un numero binario B, con $B>A$. 
Possiamo illustrare il procedimento da seguire se fissiamo il numero di bit di cui A e B 
sono costituiti. Ammettiamo ad esempio di dover adoperare numeri di 4 bit. 
Notiamo intanto che la somma di A e del suo complemento   \'e:

\[
A + \overline{A} \:=\:1111
\]


ci\'o che di solito si esprime dicendo che  $\overline{A}$  \'e il \emph{complemento ad 1} 
di A.

Nel seguito di questa sezione, per evitare di confondere il simbolo di somma con quello (+) 
adoperato per la funzione OR, adopereremo la lettera greca $\Sigma$  per indicare la somma e la 
lettera  $\Delta$ per indicare la differenza.

Notiamo che la relazione:

\begin{equation}
A \Sigma \overline{A} \:=\: 1111  \label{asigmaabar}
\end{equation}

implica:
\begin{equation}
A \Sigma \left( \overline{A} \Sigma 1 \right) \:=\: 10000   \label{asigmaplus}
\end{equation}

Si dice anche che ($\overline{A} \Sigma 1$) \'e il complemento a 2 di A.
Dalla~\ref{asigmaplus} segue che:
\[
A\:=\:10000 \Delta \overline{A} \Delta 1
\]

e quindi:
\begin{equation}
B \Delta A \:=\: \left(B \Sigma \overline{A} \Sigma 1 \right) \,\Delta 10000   \label{bminusa}
\end{equation}
Dalla~\ref{bminusa} segue che per sottrarre A da B occorre:

\begin{description}
	\item[a] complementare A, ottenendo $\overline{A}$
	\item[b] sommare B ad $\overline{A}$
	\item[c] sommare 1 al risultato
	\item[d] lasciar cadere il quinto bit (il pi\'u significativo)
\end{description}

Vediamo quindi che, con il metodo suggerito, riusciamo a realizzare l'operazione 
differenza effettuando operazioni che abbiamo gi\'a appreso, cio\'e il complemento 
(NOT) di ogni bit di un numero e la somma $\Sigma$.
E' facile verificare che, con il procedimento indicato, se $B>A$, il 
quinto bit c'\'e sempre (cio\'e il numero ottenuto effettuando la somma: 
$B \Sigma \overline{A} \Sigma 1$ vale sempre 1).
Possiamo ora verificare che, nel caso in cui il quinto bit sia 0, B \'e minore 
di A. Verificheremo anche che in tal caso la differenza (negativa) ha un valore 
assoluto pari al complemento di ($B\Sigma \overline{A}$).

Riscriviamo infatti la~\ref{bminusa} nella forma:

\[
B \Delta A \:=\:B \Sigma \overline{A} \Delta 1111 \:=\: \Delta \left[1111 \Delta \left( B \Sigma \overline{A}\right)\right] \:=\: \Delta \overline{\left[B \Sigma \overline{A}\right]}
\]
Poich\'e, se  n  \'e un numero binario di quattro bit, 1111-n \'e il 
complemento di n.

Vediamo un esempio, cominciando dal caso $B>A$:

\[
B\:=\:12\:=\:1100 \:\:\: ; \:\:A\:=\:9\:=\:1001
\]

\[
B \Delta A \:=\:B \Sigma \overline{A} \Sigma 1
\]


dove: $\overline{A}=0110$.

	
\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r | r }
$B$  &  1100 \\
$\overline{A}$  &  0110 \\
\hline
$B \Sigma \overline{A}$ & 10010 \\
$B \Sigma \overline{A} \Sigma 1$ &  1 \\
\hline
   & 10011\\
\end{tabular}
\end{center}
\vspace{0.5 cm}
	
	
Lasciamo ora cadere il bit pi\'u significativo (il quinto) ed otteniamo:

\[
B \Sigma \overline{A} \Sigma 1 \:=\: 10011\:\rightarrow 0011 \:=\:3
\]

Notiamo per inciso che se B \'e maggiore di A, la somma di B e di $\overline{A}$ 
avr\'a sempre il bit pi\'u significativo uguale ad 1. 
Ci\'o suggerisce di usare tale bit come addendo (cio\'e come l'1 da 
aggiungere nella terza delle operazioni sopra descritte (la (c)). 
Infatti, nel caso in cui B sia maggiore di A, il quinto bit varr\'a 
1 e ci\'o \'e quel che occorre per realizzare la sequenza di operazioni sopra 
descritte. Se invece B \'e minore di A, la somma $B \Sigma \overline{A}$ avr\'a 
il bit pi\'u significativo uguale a 0 ed aggiungerlo quindi alla soma 
$B \Sigma \overline{A}$ non cambier\'a nulla.

Vediamolo nel caso concreto in cui:


\[
B\:=\:9 \:=\:1001 \;\;\; ; \;\;\; A\:=\:12\:=\:1100
\]

Avremo:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r | r  c}
$B$  &  1001 & \\
$\overline{A}$  &  0011 & \\
$B \Sigma \overline{A}$ & 01100 & il 5 bit \'e zero \\
   & 0 & \\
\hline
$B \Sigma \overline{A} \Sigma 0$ &  01100 & \\
\end{tabular}
\end{center}
\vspace{0.5 cm}

Se complementiamo tale numero, troviamo:
\[
\overline{B \Sigma \overline{A}}\:=\:0011
\]

da interpretare come numero negativo (cio\'e dobbiamo immaginare di aver 
aggiunto un segno meno).

Quanto detto ci suggerisce un metodo generale per effettuare la differenza di 
due numeri B ed A valido sempre (cio\'e per B maggiore, uguale o minore di  A).
Il metodo consiste nel:
\begin{description}
	\item[a] complementare A
  \item[b] sommare B ad $\overline{A}$
  \item[c] sommare al risultato il quinto bit della somma (b5)
  \item[d] se b5=1, il risultato ottenuto al punto (c), dopo aver lasciato cadere il bit 
pi\'u significativo, rappresenta la differenza (positiva) $B \Delta A$
  \item[e] se invece b5=0, il complemento del risultato ottenuto al punto (c) rappresenta 
il valore assoluto della differenza (negativa) $B \Delta A$.
\end{description}

Tutto ci\'o \'e riassunto schematicamente in figura~\ref{sottrattore}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sottrattore,width=8.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{sottrattore}
\end{figure}

Il circuito contenuto nella scatolina riceve in ingresso  $\overline{A}$, B ed il quinto bit 
della somma di B ed $\overline{A}$ . Se tale bit vale 0, la differenza $B \Delta A$ \'e negativa 
ed il suo valore assoluto \'e  $\overline{S}$. Se invece c3=1, la differenza $B \Delta A$
(positiva) \'e data da S.

\section{Rappresentazione dei numeri negativi}

Come visto, per ottenere il complemento ad 1 di un numero binario, si 
complementano tutti i suoi bits. Una regola altrettanto semplice pu\'o essere adoperata 
per ottenere il complemento a 2: si esaminano i bit di cui il numero \'e costituito, 
a partire dalla destra. Si copiano i bit fino ad incontrare un bit uguale ad~1. 
A partire da quel punto si ricopia l'1 ed i complementi dei bit che seguono. 
Esempio:
\[
C_2\left(100110100\right) \:=\:01001100
\]

Verifichiamo che $C_2(N) + N\:=\:100000000$:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r  c }
10110100 & + \\
01001100 & = \\
\hline
100000000 & \\
\end{tabular}
\end{center}
\vspace{0.5 cm}



Cos\'i, se il primo bit sulla destra \'e un 1, il complemento a 2 pu\'o essere 
ottenuto inserendo alla sinistra di tale 1 i complementi di tutti i rimanenti bit.

E' ovvio da quanto detto che per rappresentare un numero negativo occorrer\'a 
aggiungere ai bit che rappresentano il numero, un ulteriore bit che ne rappresenti 
il segno.
Le due convenzioni comunemente adoperate sono quella del ''complemento a due'' e 
quella del ''complemento ad uno''. Esaminiamo la prima di questa, ammettendo, per 
semplicit\'a, di voler rappresentare numeri il cui valore assoluto sia al massimo 
il decimale 15 (1111 in binario).
I numeri da 0 a 15 saranno i numeri binari di cinque bit, con il bit pi\'u 
significativo (il quinto, che ora indicher\'a il segno) uguale a 0 e con i quattro 
meno significativi che vanno da 0000 a 1111. 

Il numero negativo corrispondente ad un dato numero binario positivo si costruisce facendo 
il complemento a 2 del numero dato. Cos\'i:
\[
+11\:=\:01011
\]
\[
-11\:=\:10101
\]

Notiamo che, in tale sistema, la differenza di due numeri si ottiene prendendo 
la somma del primo e del complemento a 2 del secondo in tutti i casi! 
Cio\'e sia nel caso in cui A sia maggiore di B che in quello in cui A \'e 
minore di B. Vediamo ci\'o con un esempio, cominciando dal caso in cui sia A che
B sono positivi.
La somma \'e data da:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r  c  r  r  r }
 &  &  binario & decimale \\
A & = & 00110 & 6 & + \\
B & = & 00101 & 5 & = \\
$A \Sigma B$ & = & 01011 & 11 \\
\end{tabular}
\end{center}
\vspace{0.5 cm}
 
 
Calcoliamo ora la differenza $A \Delta B$:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r  c  r  r  r }
 &  &  binario & decimale \\
A & = & 00110 & 6 & + \\
$-B=C_2(B)$ & = & 11011 & 5 & = \\
$A \Sigma C_2(B)$ & = & 100001 & 1 \\
\end{tabular}
\end{center}
\vspace{0.5 cm}



Vediamo che ora il quinto bit \'e zero, mentre un 1 compare in sesta posizione. Ci\'o 
non crea alcun problema poich\'e nel caso specifico i nostri registri hanno solo 5 bit. 
La differenza \'e positiva ed \'e uguale ad 1.
Calcoliamo ora $B \Delta A$:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ r  c  r  r  r }
 &  &  binario & decimale \\
B & = & 00101 & 5 & + \\
$-A=C_2(A)$ & = & 11010 & 6 & = \\
$B \Sigma C_2(A)$ & = & 11111 & -1 \\
\end{tabular}
\end{center}
\vspace{0.5 cm}

Vediamo che il risultato \'e negativo (1 in quinta posizione) e che il modulo 
vale:
\[
C_2(11111)\:=\:00001 \:=\:1
\]

Un sistema analogo \'e quello della rappresentazione in ''complemento ad 1.

Esamineremo pi\'u avanti l'implementazione delle altre operazioni aritmetiche.


\section{Comparatori digitali}

Ammettiamo di voler comparare due semplici bit A e B. Le possibili 
configurazioni sono:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ c  c  |  c  c }
 A & B & Test & Y \\
\hline
0 & 0 & $A=B$ & $\overline{A} \cdot \overline{B}$ \\
0 & 1 & $A<B$ & $\overline{A} \cdot B$  \\
1 & 0 & $A>B$ & $A \cdot \overline{B}$  \\
1 & 1 & $A=B$ & $A \cdot B$ \\
\end{tabular}
\end{center}
\vspace{0.5 cm}


La variabile Y nell'ultima colonna definisce in modo univoco lo stato di A e B.
Notiamo che l'uguaglianza $A = B$, \'e espressa da:

\[
Y \:=\:A \cdot B + \overline{A} \cdot \overline{B}
\]

cio\'e:


\[
Y \:=\:\overline{\overline{Y}}\:=\:\overline{\overline{A \cdot B + \overline{A} \cdot \overline{B}}}\:=\:
\overline{\overline{A \cdot B} \cdot \overline{\overline{A} \cdot \overline{B}}}=
\]
\[
=\overline{\left(\overline{A} + \overline{B}\right) \cdot \left(A + B \right)}\:=\:\overline{A \cdot \overline{B}
+ B \cdot \overline{A}}
\]

In definitiva abbiamo:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ c   c }
$A>B$ & $Y \:=\:A \cdot \overline{B}\:=\:1$  \\
$A<B$ & $Y\:=\: B \cdot \overline{A}\:=\:1$  \\
$A=B$ & $E\: \equiv \: Y\:=\:\overline{A\cdot \overline{B}+ B \cdot \overline{A}}\:=\:1$ \\
\end{tabular}
\end{center}
\vspace{0.5 cm}


Un circuito che fornisce in uscita la variabile Y \'e quello di figura~\ref{comparatore}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=comparatore,width=8.0 cm,
height=4 cm}}\end{center}
\caption{}
\protect\label{comparatore}
\end{figure}


Se vogliamo comparare dei numeri costituiti da pi\'u bit, il circuito dovr\'a 
comparare i singoli bit ed un po' di logica aggiuntiva sar\'a necessaria per ottenere 
la risposta.
Ammettiamo ad esempio di voler comparare due numeri di 4 bit. L'uguaglianza dei 
due numeri richieder\'a ovviamente l'uguaglianza due a due dei bit corrispondenti. 
Cos\'i, indicando con $A_3,\:A_2,\: A_1,\: A_0$ i bit del primo numero e con 
$B_3,\:B_2,\: B_1,\: B_0$  quelli del secondo, l'uguaglianza richieder\'a:
\[
A_3=B_3; \:\:A_2=B_2;\:\:A_1=B_1;\:\:A_0=B_0
\]


cio\'e:
\[
E_3 \cdot E_2 \cdot E_1 \cdot E_0\:=\:1
\]

A sar\'a maggiore di B se:

\begin{description}
	\item[a] $A_3 > B_3$ oppure:
	\item[b] $A_3=B_3$ e $A_2 > B_2$  oppure:
	\item[c] $A_3=B_3$ e $A_2 = B_2$ e $A_1 > B_1$  oppure:
	\item[d] $A_3=B_3$ e $A_2 = B_2$ e $A_1 = B_1$ e $A_0 > B_0$
\end{description}

Cio\'e:

\[
Y\:=\:A_3 \cdot \overline{B_3} + E_3 \cdot A_2 \cdot \overline{B_2} + E_3 \cdot E_2 \cdot A_1 \cdot \overline{B_1} + E_3 \cdot E_2 \cdot E_1 \cdot A_0 \cdot \overline{B_0}
\]


La condizione $A < B$ si realizza scambiando A con B.


\section{Parit\'a di un numero binario}

Dato un numero binario, si definisce \emph{parit\'a} la parit\'a della somma dei bit. 
Cos\'i ad esempio: $1101$ ha parit\'a dispari (numero dispari di 1); mentre $1001$ ha
parit\'a pari.

L'uso della parit\'a \'e utile per controllare se un numero binario \'e stato 
trasmesso correttamente da un elemento di circuito ad un altro elemento, o anche 
da un sito ad un sito distante. Infatti il rumore che \'e inevitabilmente 
presente sulle linee usate per la trasmissione pu\'o far s\'i che un 
bit cambi valore.
Se ammettiamo che la probabilit\'a che, per effetto del rumore in una medesima 
parola (e.g. di 8 bit), 2 bit cambino valore, sia trascurabile, possiamo verificare 
l'eventuale presenza di errori aggiungendo alla parola un ulteriore bit che ci dica 
quale deve essere la parit\'a del numero.
Cos\'i, se i numeri hanno 8 bit ed il numero in questione ha parit\'a dispari, 
potremo aggiungere un nono bit di valore 1 che renda la parit\'a complessiva pari. 
Se il numero di 8 bit aveva parit\'a pari, aggiungeremo un nono bit di valore 0, 
con che la parit\'a complessiva rimane pari.
In ricezione, adopereremo un circuito che controlli la parit\'a e verifichi che
sia sempre pari. Se essa risulter\'a dispari il sistema denuncer\'a l'errore 
al circuito da cui l'informazione proviene, il quale invier\'a nuovamente il dato.
Ovviamente, \'e possibile adottare la convenzione di parit\'a dispari, anzich\'e 
pari come nell'esempio fatto.

Esaminiamo ora un semplice circuito che genera il bit di parit\'a per una parola 
di 4 bit.

Se avessimo solo due bit, la parit\'a sarebbe:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ c   c  | r | c }
A & B & parit\'a del numero & bit da aggiungere \\
\hline
0 & 0 & pari & 0 \\
0 & 1 & dispari & 1 \\
1 & 0 & dispari & 1 \\
1 & 1 & pari & 0 \\
\end{tabular}
\end{center}
\vspace{0.5 cm}

Vediamo che il ''bit da aggiungere'' altro non \'e che l'XOR di A e B.

Se il sistema ha quattro bit $(A B C D)$, potremo definire la parit\'a della 
coppia $(AB)$, quella della coppia $(CD)$ ed infine quella dei due bit di parit\'a cos\'i 
ottenuti. Occorrer\'a cio\'e una cascata di XOR, come mostrato in figura~\ref{parity_bit}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=parity_bit,width=8.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{parity_bit}
\end{figure}

\section{Codificatori/Decodificatori}

Un codificatore \'e un circuito che converte in un codice un'informazione 
corrispondente al verificarsi di uno tra n possibili eventi.
Ad esempio, un codificatore \'e l'insieme dei circuiti presenti in un personal 
computer, che generano un numero binario (codice) quando si pigia un determinato tasto.
Un decodificatore \'e viceversa un circuito che riceve in ingresso un codice 
(cio\'e un numero binario, codificato in modo opportuno) ed attiva una di n 
possibili linee (o eventi).

Esaminiamo come esempio di decodificatore un circuito per la conversione BCD-Decimale.
BCD sta per ''Binary Coded Decimal'' ed \'e un modo per rappresentare (codificare) i 
numeri decimali. In tale sistema i numeri da 0 a 9 sono rappresentati da 4 bit:

\vspace{0.5 cm}
\begin{center}
\begin{tabular}{ c   c   c}
0 & = & 0000 \\
1 & = & 0001 \\
2 & = & 0010 \\
3 & = & 0011 \\
4 & = & 0100 \\
5 & = & 0101 \\
6 & = & 0110 \\
7 & = & 0111 \\
8 & = & 1000 \\
9 & = & 1001 \\
\end{tabular}
\end{center}
\vspace{0.5 cm}

Un decodificatore BCD-Decimale ricever\'a in ingresso i quattro bit ed 
attiver\'a una di dieci possibili linee di uscita, corrispondenti ai numeri 
decimali da 0 a 9.
Notiamo per inciso che nel codice BCD un numero decimale di pi\'u cifre \'e 
rappresentato da tanti gruppi di quattro bit quante sono le cifre decimali che 
lo costituiscono. Ad esempio:


\begin{table}[h]
	\begin{center}
		\begin{tabular}{| l | r | r | r | r | }
		\hline
371 = & 0011 & 0111 & 0001 \\
\hline
 & 3 & 7 & 1 \\
 \hline			
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_prima}
\end{table}
Se indichiamo con $(a_3,a_2,a_1,a_0)$ i bit che costituiscono il codice BCD (con $a_0$  il meno 
significativo) e con  $(\overline{a}_3,\overline{a}_2,\overline{a}_1,\overline{a}_0)$  i loro 
complementi, avremo:
\[
\overline{a}_3 \cdot \overline{a}_2 \cdot \overline{a}_1 \cdot \overline{a}_0 \: \Rightarrow \: 0\;decimale
\]
\[
\overline{a}_3 \cdot \overline{a}_2 \cdot \overline{a}_1 \cdot a_0 \: \Rightarrow \: 1\;decimale
\]
\[
\overline{a}_3 \cdot \overline{a}_2 \cdot a_1 \cdot \overline{a}_0 \: \Rightarrow \: 2\;decimale
\]
\[
\cdots
\]
\[
a_3 \cdot a_2 \cdot a_1 \cdot a_0 \: \Rightarrow \: 0 \;decimale
\]

Un circuito che realizza tale funzione logica \'e quello mostrato in figura~\ref{decod_4_10}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=decod_4_10,width=8.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{decod_4_10}
\end{figure}

Tale circuito \'e noto anche come \emph{decodificatore da 4 a 10 linee}.


Esaminiamo ora la struttura di un codificatore.
Ammettiamo di voler generare un carattere (codice) BCD in uscita pigiando uno di 
10 tasti possibili.
Siano i tasti $T_0 \cdots T_9$. La tabella delle verit\'a che realizza la funzione di 
codifica \'e la~\ref{logici_seconda}.



\begin{table}[h!]
	\begin{center}
		\begin{tabular}{| c c c c c c c c c c | c c c c |}
		\hline
$T_9$ & $T_8$ & $T_7$ & $T_6$ & $T_5$ & $T_4$ & $T_3$ & $T_2$ & $T_1$ & $T_0$ & $Y_3$ & $Y_2$ & $Y_1$ & $Y_0$  \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 &  0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 &  0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 &  0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 &  0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 &  0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 &  0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &  0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &  1 & 0 & 0 & 1 \\
\hline
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_seconda}
\end{table}





Un tasto pigiato corrisponde alla variabile T uguale ad 1.
Il tasto non pigiato corrisponde alla variabile T uguale a 0.
Dalla tabella vediamo subito la corrispondenza tra le variabili Y e le T:
\[
Y_0\:=\:T_1 + T_3 + T_5 + T_7 + T_9
\]
\[
Y_1\:=\:T_2 + T_3  + T_6 + T_7
\]
\[
Y_2\:=\:T_4 + T_5 + T_6 + T_7
\]
\[
Y_3 \:=\: T_8 + T_9
\]


Un circuito che realizza tale codifica pu\'o esser ottenuto da un integrato a 
matrice di diodi, come mostrato in figura~\ref{matrice}. 


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=matrice,width=13.0 cm,
height=11 cm}}\end{center}
\caption{}
\protect\label{matrice}
\end{figure}

Se uno degli interruttori $T_0-T_9$ \'e chiuso, la corrispondente linea orizzontale
viene a trovarsi a 5~V. Con ci\'o i diodi ad essa collegati avranno l'anodo a 5~V ed
il catodo collegato alle resistenze R, a loro volta collegate a massa. In tali condizioni,
la tensione sul catodo sar\'a 5-0.6=4.4~V, cio\'e ancora al livello alto. L'uscita (O le
uscite) collegate alla linea verticale cui \'e connesso il catodo del diodo in questione
sar\'a quindi anch'essa al livello logico 1. Ci\'o implementa la funzione voluta.


Se in tale circuito due o pi\'u tasti vengono premuti contemporaneamente, il 
risultato pu\'o non essere quello desiderato. 
Un ''codificatore con priorit\'a'' elimina tale problema. In 
un codificatore dd questo tipo, se due o pi\'u tasti sono pigiati insieme, 
l'azione che ha luogo \'e quella che si avrebbe pigiando solo il tasto pi\'u 
alto nella sequenza $T_0 \cdots T_9$.
Per ottenere tale funzione dobbiamo modificare la tabella delle verit\'a come 
segue:

\begin{table}[h]
	\begin{center}
		\begin{tabular}{| c c c c c c c c c c | c c c c |}
		\hline
$T_9$ & $T_8$ & $T_7$ & $T_6$ & $T_5$ & $T_4$ & $T_3$ & $T_2$ & $T_1$ & $T_0$ & $Y_3$ & $Y_2$ & $Y_1$ & $Y_0$  \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 &  0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & x &  0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & x & x &  0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & x & x & x &  0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & x & x & x & x &  0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & x & x & x & x & x &  0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & x & x & x & x & x & x &  0 & 1 & 1 & 0 \\
0 & 0 & 1 & x & x & x & x & x & x & x &  0 & 1 & 1 & 1 \\
0 & 1 & x & x & x & x & x & x & x & x &  1 & 0 & 0 & 0 \\
1 & x & x & x & x & x & x & x & x & x &  1 & 0 & 0 & 1 \\
\hline
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_terza}
\end{table}


Dove la x sta ad indicare che \'e irrilevante se quel tasto sia pigiato o no. 
Se ora si pigia il tasto $T_2$  ma per errore si pigia contemporaneamente il tasto $T_3$,  
allora  $T_3 \neq 0$   ed anche se $T_2=1$  , diverranno ''alti'' i bit $Y_1$ ed $Y_0$.
Vediamo come le variabili $Y_3 \cdots Y_0$   possano essere espresse in funzione 
di $T_9 \cdots T_0$. Esaminiamo $Y_0$:

\newcommand{\tbar}[1]{\overline{T}_#1}


\[
Y_0 \:=\:T_1 \tbar{2} \tbar{3} \tbar{4} \tbar{5} \tbar{6} \tbar{7} \tbar{8} \tbar{9}\:+\:T_3 \tbar{4}
\tbar{5} \tbar{6} \tbar{7} \tbar{8} \tbar{9} \:+
\]
\[
+ T_5 \tbar{6} \tbar{7} \tbar{8} \tbar{9} \:+\: T_7 \tbar{8} \tbar{9} \:+\: T_9
\]

Questa si pu\'o semplificare in:

\[
Y_0 \:=\: \tbar{9} \tbar{8} \left( T_7 + \tbar{7} B \right) \:+\:T_9
\]


con:

\[
B\:=\:\tbar{6} \tbar{5} \tbar{4} \tbar{3} \tbar{2} T_1 \:+\: \tbar{6} \tbar{5} \tbar{4} T_3 \:+\: \tbar{6} T_5\:=\:
\tbar{6} \left( T_5 + \tbar{5} C \right)
\]

dove:

\[
C\:=\:\tbar{4} \tbar{2} T_1 \:+\: \tbar{4} T_3 \:=\: \tbar{4} \left(\tbar{2} T_1 + T_3 \right)
\]
Ed infine:

\[
Y_0 \:=\:T_9 \:+ \: \tbar{8} \left(T_7 + \tbar{6}\left(T_5 + D \right) \right)
\]
con:
\[
D\:=\: \tbar{4} \left(\tbar{1} T_1 + T_3 \right)
\]



Un decodificatore svolge un ruolo opposto; esso attiva una tra  N linee d'uscita 
secondo l'informazione che riceve da due o pi\'u linee d'ingresso.


\section{Multiplexer/Demultiplexer}

Ammettiamo di voler ''incanalare'' su di un'unica linea dati che provengono da 
una di N linee diverse.
Si pu\'o utilizzare a tale scopo un multiplexer. Il multiplexer ha N ingressi 
''dati'', un ingresso ''indirizzo'', che specifica quale degli ingressi dati 
si vuol selezionare, ed un'unica uscita, sulla quale viene convogliato il dato.
Un esempio di multiplexer \'e quello mostrato in figura~\ref{multiplexer}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=multiplexer,width=8.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{multiplexer}
\end{figure}



Vediamo che se gli ingressi ''indirizzo'' A e B sono entrambi uguali a 0, 
$\overline{A}=1$ e $\overline{B}=1$ e la prima porta AND sar\'a 
abilitata~\footnote{si dice che una porta \'e abilitatata se essa \'e in grado
di rispondere a variazioni dei segnali presenti sugli ingressi diversi da
quello/quelli considerati di abilitazione. Ad esempio, se uno degli ingressi 
(considerato \emph{di abilitazione}) di una porta AND a quattro ingressi \'e uguale a 0
l'uscita sar\'a 0 qualunque siano i valori presenti sugli altri ingressi. Si dice che
in tal caso la porta \'e disabilitata}.

Quindi il segnale presente sulla linea d'ingresso $X_0$  sar\'a convogliato in 
uscita non appena l'ingresso di abilitazione S (Strobe) sia alto. 
Se A=1 e B=0, sar\'a abilitata la seconda porta e sar\'a quindi convogliato in 
uscita il segnale presente sulla linea $X_1$ , e cos\'i via.


Un multiplexer pu\'o esser utilizzato per effettuare la conversione parallelo-
seriale. Ammettiamo infatti che ad un circuito arrivino dei bit, costituenti 
una ''parola'', su n linee parallele e che esso debba poi convogliare tali 
informazioni su di un'unica linea, come mostrato in figura~\ref{multiplex_out}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=multiplex_out,width=10.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{multiplex_out}
\end{figure}


Si potr\'a usare un multiplexer che riceve sulle linee $x_0$, $x_1$,...,$x_n$ i bit da 
convogliare in uscita; gli ingressi di controllo (o di indirizzo) $c_0,\: c_1,\cdots,c_n$, 
dovranno ricevere in successione temporale regolare i valori 000, 100,...,010,...,110,... etc..
(con $c_0$ il bit meno significativo). In tal modo il bit presente sulla linea $x_0$  sar\'a 
convogliato per primo in uscita, seguir\'a poi $x_1$, poi $x_2$ etc. Ovviamente il numero 
degli ingressi n dovr\'a esser legato al numero di ingressi di controllo N dalla relazione 
$n = 2^N$. Cos\'i, per $n = 4$ avremo $N = 4$, per $n = 8$, $N = 3$ etc.

Un demultiplexer convoglia invece su una di n possibili linee di uscita i 
segnali che riceve su di una linea d'ingresso, facendo uso dell'informazione (indirizzo) 
che riceve su N linee di controllo.
E' utile far presente che qualsiasi decodificatore pu\'o essere usato come 
demultiplexer utilizzando tutte le linee d'ingresso meno una per la funzione di selezione 
delle uscite.
Inoltre possiamo far vedere come un multiplexer possa essere adoperato per implementare una 
funzione logica.
Consideriamo il multiplexer di figura~\ref{funzione_logica}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=funzione_logica,width=9.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{funzione_logica}
\end{figure}



Gli ingressi sono  $x_0, x_1, x_2, x_3$. A e B sono gli ingressi di controllo (con A il meno 
significativo. S \'e lo Strobe. La tabella delle verit\'a \'e la seguente:

\begin{table}[h]
	\begin{center}
		\begin{tabular}{| c c | c | c |}
		\hline
		B & A & S & Y \\
		\hline
		0 & 0 & 1 & $x_0$ \\
		0 & 1 & 1 & $x_1$ \\
		1 & 0 & 1 & $x_2$ \\
		1 & 1 & 1 & $x_3$ \\
		\hline	
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_quarta}
\end{table}


Y pu\'o anche essere scritto come:
\newcommand{\abar}{\overline{A}\:}
\newcommand{\bbar}{\overline{B}\:}
\newcommand{\cbar}{\overline{C}\:}
\begin{equation}
Y\:=\:x_0 \abar \bbar + x_1 A \bbar + x_2 \abar B + x_3 A B   \label{x0abar}
\end{equation}


Se ora volessimo implementare la seguente funzione logica:

\[
Y \:=\: C \bbar  \abar + \cbar  \bbar  \abar + C \bbar A + \cbar B A
\]

notando che i primi due termini si possono semplificare in $\bbar \abar$, cio\'e:

\[
Y\:=\:\bbar \abar + C \bbar A + \cbar B A
\]

possiamo confrontare questa espressione con la~\ref{x0abar}, imponendo l'uguaglianza dei 
coefficienti che moltiplicano i termini $\bbar \abar$, $\bbar A$, $B A$ ottenendo:

\[
x_0=1; \:\:\:x_1=C; \:\:\:x_2=0; \:\:\:x_3=\cbar
\]

Baster\'a quindi utilizzare il moltiplexer indicato, assegnando agli ingressi 
$x_0, x_1, x_2, x_3$ i valori trovati, per implementare la funzione logica indicata.


I multiplexer/demultiplexer svolgono un ruolo di fondamentale importanza nei 
microprocessori e pi\'u in generale in tutti i sistemi digitali. 
Esistono in commercio numerosi integrati dedicati allo scopo. 
In figura~\ref{74ls151} \'e illustrato il multiplexer 74LS151.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=74ls151,width=8.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{74ls151}
\end{figure}


Gli ingressi sono indicati con $I_0 - I_7$ . L'indirizzo, cio\'e il numero binario che 
rappresenta l'ingresso da selezionare, \'e impostato sui piedini $S_0 - S_2$ . 
L'uscita Z ed il suo complemento sono disponibili sui piedini 5/6. 
Il piedino indicato con $E$ (accompagnato da un'inversione), che in condizioni normali 
va tenuto basso, \'e l'ingresso di \emph{enable}. 
Se si vuole inibire il trasferimento occorrer\'a portare tale ingresso al livello alto.

L'integrato 74LS138, il cui schema logico \'e mostrato in figura~\ref{74ls138} \'e 
utilizzabile come demultiplexer da 1 ad 8. 

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=74ls138,width=8.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{74ls138}
\end{figure}


\section{Registri e memorie: i Flip-Flop}

Perch\'e un numero possa essere elaborato da un processore, esso deve essere 
preventivamente immagazzinato in un insieme di celle elementari o registri. 
Un tipico registro pu\'o contenere ad esempio un byte (8 bit), una parola di 
16 bit o una parola di 32 bit etc. Alla base 
di un generico registro \'e la cella elementare di memoria,  spesso costituita 
da un \emph{bistabile}, o flip-flop (FF). Un FF \'e un circuito con due ingressi 
(detti ingressi di Set e di Reset) e due uscite, convenzionalmente chiamate Q e  
$\overline{Q}$, una complementare dell'altra. 
Esiste in realt\'a un'ampia variet\'a di FF. 
Quello che abbiamo sommariamente descritto \'e il flip-flop di tipo RS. Un FF 
pu\'o assumere due 
stati: nello stato di \emph{Set}, le uscite sono: $Q=1,\:\overline{Q}=0$. Nello stato 
di \emph{Reset} esse sono: $Q=0, \overline{Q}=1$. Vediamo cos\'i 
che un FF pu\'o essere adoperato per memorizzare un bit. 
I valori delle uscite sono determinati dai valori dei segnali presenti sugli ingressi 
R, S, secondo la seguente tabella delle verit\'a:

\begin{table}[h]
	\begin{center}
		\begin{tabular}{| c | c | c | c | }
		\hline
 R & S & $Q_n$ & $\overline{Q}_n$ \\
 \hline
 0 & 0 & \multicolumn{2}{c |}{non consentito} \\
 \hline
 0 & 1 & 1 & 0 \\
 \hline
 1 & 0 & 0 & 1 \\
 \hline
 1 & 1 & $Q_{n-1}$ & $\overline{Q}_{n-1}$ \\
 \hline
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_quinta}
\end{table}

Notiamo che lo stato in cui entrambi gli ingressi sono nello stato logico basso 
(R=0, S=0) \'e proibito. Lo stato in cui entrambi gli ingressi sono nello stato 
logico alto (R=1, S=1) \'e uguale a quello precedente l'applicazione di tali segnali 
sugli ingressi $(Q_n = Q_{n-1})$.

Il FF di tipo RS considerato \'e di tipo ''asincrono'' dove si intende che la 
transizione da uno stato all'altro \'e determinata esclusivamente dall'applicazione 
di determinati segnali sugli ingressi R ed S ed indipendente da eventuali impulsi 
di clock presenti nel sistema.
Per veder ci\'o pi\'u chiaramente, cominciamo con l'esaminare la struttura interna 
di un FF di tipo RS, che utilizza due porte NAND:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=r_s_flip_flop,width=7.0 cm,
height=4 cm}}\end{center}
\caption{}
\protect\label{r_s_flip_flop}
\end{figure}


Vediamo che se S=0 ed R=1, avremo $Q=0$ e  $\overline{Q}=1$. Se S=1 ed R=0, si ha invece $Q=1$ 
e $\overline{Q}=0$. Se R ed S sono entrambi uguali ad 1, le uscite $Q_n$  e $\overline{Q}_n$  
dipendono soltanto da $Q_{n-1}$  e $\overline{Q}_{n-1}$, cio\'e dai valori che 
$Q$ e $\overline{Q}$  avevano prima dell'applicazione dei segnali su S ed R.
In particolare, se era $Q_{n-1}=0$ e $\overline{Q}_{n-1}=1$, le uscite saranno 
$Q_n=0$, $\overline{Q}_n=1$. Se viceversa era  $Q_{n-1}=1$, $\overline{Q}_{n-1}=0$, 
si avr\'a  $Q_n=1$, $\overline{Q}_n=0$.   
Vediamo cos\'i che lo stato con R=S=1 non modifica le uscite $Q$ e $\overline{Q}$.

Vediamo invece cosa accade nello stato ''proibito'' con R=S=0. Se un ingresso di 
una porta NAND \'e 0, l'uscita sar\'a 1 qualunque sia il segnale presente 
sull'altro ingresso (in tale situazione la porta \'e disabilitata).
Vediamo quindi che, con R=S=0 avremmo $Q\:=\:\overline{Q}\:=\:1$.
Tale situazione \'e anomala, poich\'e vogliamo limitarci a due stati: $(Q=1\:;\overline{Q}=0$,  
$(Q=0\:;\overline{Q}=1$.
C'\'e inoltre l'ulteriore problema costituito dal fatto che, in una eventuale 
successiva transizione allo stato con S=R=1, lo stato delle uscite $Q$ e 
$\overline{Q}$  verrebbe a dipendere dal ritardo relativo tra i segnali applicati agli 
ingressi S ed R. Se la transizione di S avviene prima di quella di R, il sistema 
andr\'a nello stato di Set $(Q=1)$, altrimenti andr\'a in quello di Reset ($\overline{Q}=1$). 
Poich\'e il ritardo relativo \'e un elemento aleatorio \'e chiaro 
come tale situazione non sia accettabile. 
Vedremo in seguito come in alcuni tipi di FF (ad esempio i JK) non esista alcun stato proibito.

Si pu\'o ottenere un circuito con la medesima tabella delle verit\'a di quello 
precedente, facendo precedere ciascuno dei due gates NAND da un ulteriore NAND e scambiando 
i ruoli di $Q$ e $\overline{Q}$ come mostrato in figura~\ref{pr_clear_f_f}:


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=pr_clear_f_f,width=8.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{pr_clear_f_f}
\end{figure}

Ammettiamo che gli ingressi di \emph{Preset} e di \emph{Clear} siano entrambi alti.
Se l'enable \'e alto, le porte NAND, in ingresso saranno ''abilitate'' (cio\'e 
le loro uscite, S' ed R', dipenderanno dai segnali presenti sugli ingressi S ed R). 
Ci\'o \'e mostrato nella tabella che segue. 

\begin{table}[h]
	\begin{center}
		\begin{tabular}{| c | c | c | c | c | c |}
		\hline
 R & S & R' & S' & $Q_n$ & $\overline{Q}_n$ \\
 \hline
 0 & 0 & 1 & 1 & $Q_{n-1}$ &  $\overline{Q}_{n-1}$ \\
 \hline
 0 & 1 & 1 & 0 & 1 & 0 \\
 \hline
 1 & 0 & 0 & 1 & 0 & 1 \\
 \hline
 1 & 1 & \multicolumn{4}{c |}{non consentito} \\
 \hline
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_sesta}
\end{table}



Vediamo che ora lo stato ''proibito'' \'e quello che corrisponde ad R=S=1.
Se l'ingresso di enable \'e basso, le porte in ingresso risulteranno 
disabilitate (cio\'e non risponderanno pi\'u ai segnali presenti sugli 
ingressi R ed S. Avremo in tale situazione R'=S'=1 e $Q_n=Q_{n-1}$,  $\overline{Q}_n=\overline{Q}_{n-1}$. Con gli ingressi di Preset e Clear 
entrambi alti, le due porte poste a valle risponderanno solo ai valori 
dei rimanenti ingressi.

L'ingresso che abbiamo chiamato ''Enable'' pu\'o essere utilizzato per un 
funzionamento ''sincrono'' di tale FF. Se cio\'e immaginiamo di aver applicato 
agli ingressi R ed S due valori (ad esempio R=1, S=0), ed applichiamo 
all'ingresso di Enable un impulso di clock, finch\'e questo \'e 
basso le uscite $Q$  e $\overline{Q}$ rimangono inalterate, mentre 
esse acquisteranno i valori $Q=0$, $\overline{Q}=1$ non appena il clock sia 
divenuto alto. L'impulso (positivo) del clock abilita cio\'e il trasferimento 
dei segnali presenti sugli ingressi R ed S, verso le uscite $Q$ e $\overline{Q}$
rispettivamente. Gli ingressi di Preset e Clear che, come si \'e detto, vanno 
normalmente tenuti alti, possono essere adoperati per fissare dei valori 
iniziali prestabiliti delle uscite. 
Immaginiamo infatti di tenere basso l'impulso di clock, con che S'=R'=1.
Se ora poniamo Preset=1 e Clear=0 avremo $ \overline{Q}=1$, $Q=0$. 
Se invece poniamo Preset=0 e Clear=1, avremo  $\overline{Q}=0$, $Q=1$.

Se tra gli ingressi S ed R di un FF di tipo RS poniamo un invertitore (NOT) come 
mostrato in figura, otteniamo un FF di tipo D (DATA).

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=d_type_f_f,width=5.5 cm,
height=4 cm}}\end{center}
\caption{}
\protect\label{d_type_f_f}
\end{figure}




La presenza dell'invertitore fa s\'i che se S=1, sar\'a R=0 e viceversa. Tale 
FF ha un solo ingresso (D) al posto dei due ingressi separati S ed R. 
Il dato presente sull'ingresso D viene trasferito in Q quando l'impulso di 
clock diviene alto.
Un esempio di FF di tipo D \'e quello mostrato in figura~\ref{sn74ls74}. 

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls74,width=10.0 cm,
height=15 cm}}\end{center}
\caption{}
\protect\label{sn74ls74}
\end{figure}



Questo (SN74LS74) \'e un chip che contiene 2 FF di tipo D. 
Ciascuno dei due FF contenuti nel chip ha, oltre all'ingresso D, gli 
ingressi di Preset e Clear, l'ingresso di clock e le uscite $Q$ e $\overline{Q}$. 
\footnote{Nella sigla che identifica il chip, le ultime due cifre (74) specificano la 
funzione effettuata (FF di tipo D nel nostro caso). Le prime due cifre numeriche 
(nuovamente 74, ma \'e un caso!) si riferiscono al range di temperatura 
in cui pu\'o operare: 74 implica un'applicazione ''commerciale'', per un range 
di temperatura che va da $0^oC$ a $70^oC$. Se trovassimo un 54 al posto di tali 
due cifre, ci\'o implicherebbe un dispositivo adatto ad applicazioni ''militari'', 
in un range di temperature compreso tra $-55^oC$ e $+125^oC$. La sigla LS sta poi 
ad indicare la classe o tipo del chip. LS sta per ''Low power Schottky''.}



Un tipo di FF che ha un ampio campo di applicazioni \'e il JK. Questo differisce 
da quello di tipo RS nel fatto che ora lo stato in cui entrambi gli ingressi 
(che ora si chiamano J e K) sono alti \'e consentito.
In tale stato, l'arrivo di un impulso di clock fa passare le uscite del FF negli 
stati complementari di quelli in cui erano prima: $Q_n=\overline{Q}_{n-1}$, 
$\overline{Q}_n=Q_{n-1}$.
Ci\'o pu\'o essere ottenuto facendo precedere ciascuno dei due ingressi di un FF RS, da 
una porta AND, come mostrato in figura~\ref{j_k_simple_ff}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=j_k_simple_ff.eps,width=8.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{j_k_simple_ff}
\end{figure}



\newcommand{\qbar}{\overline{Q}}

Se J=1 e K=0, esaminiamo i due possibili stati di $Q$ e $\qbar$:

a) $Q=1$,  $\qbar=0$

In tal caso avremo S=0, R=0 e quindi lo stato del FF non cambier\'a all'arrivo 
dell'impulso di clock.

b) $Q=0$, $\qbar=1$

Ora avremo R=0, S=1. In tal caso, all'arrivo dell'impulso di clock le 
uscite acquisteranno i valori:
 
$Q=1$, $\qbar=0$

Se era J=0, K=1 possiamo anticipare, data la simmetria del circuito, che le 
uscite saranno $Q=0$,$\qbar=1$ dopo l'applicazione di un impulso di clock. 
Verifichiamolo, esaminando i due possibili stati del FF:

a) $Q=1$,  $\qbar=0$

In tal caso avremo: S=0, R=1; da cui seguir\'a $Q=0$, $\qbar=1$.

b) $Q=0$,  $\qbar=1$

In tal caso avremo: R=0, S=0 e quindi $Q_n=Q_{n-1}$.

Esaminiamo infine lo stato J=K=1. In tal caso, se era $Q_n=1$,  $\qbar_{n-1}=0$ 
avremo che la porta AND inferiore \'e abilitata (Q=1, K=1) mentre \'e disabilitata 
quella superiore (poich\'e  $\qbar=0$). Ne segue che, con l'arrivo 
dell'impulso di clock sar\'a $Q=0$, $\qbar=1$, cio\'e il sistema passer\'a nello stato 
complementare di quello in cui era. 
Il successivo impulso di clock trover\'a ora abilitata la porta superiore e 
disabilitata quella inferiore. Di conseguenza, con tale impulso di clock $Q$ 
diventer\'a 1 e $\qbar$ 0.

Il sistema cambia quindi stato ad ogni impulso di clock (fintantoch\'e J e K 
vengono mantenuti fissi al livello alto). Ci\'o \'e mostrato nel grafico di 
figura~\ref{jk_ff_out}:

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=jk_ff_out,width=10.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{jk_ff_out}
\end{figure}



Notiamo che la frequenza dell'onda rettangolare $Q(\qbar)$ \'e la met\'a di quella del 
clock. Un FF di tipo JK con J=K=1 effettua quella che vien chiamata la funzione ''TOGGLE'' 
ed \'e adoperato come divisore di frequenza. Ponendone due o pi\'u in cascata si 
pu\'o realizzare una divisione della frequenza del clock per 4 o per potenze di 
2 pi\'u elevate.
L'operazione di questo circuito potr\'a presentare dei problemi, poich\'e 
l'uscita (Q) tender\'a ad oscillare tra 0 ed 1 nell'intervallo di tempo $t_c$  
in cui il clock \'e alto. Per esempio, se J=K=1 e Q=0, all'arrivo di un 
impulso di clock Q diverr\'a 1 dopo un piccolo ritardo  $\Delta t$ (dipendente dalla 
struttura interna del dispositivo). 
A questo punto avremo J=K=1, CK=1 e Q=1. Ora Q tender\'a a divenire 0, a meno 
che il CK non sia nel frattempo sceso a 0.
L'uscita Q altrimenti osciller\'a a lungo tra 0 ed 1 ed alla fine dell'impulso 
di clock il suo stato sar\'a casuale. 
Tale fenomeno va sotto il nome di ''race-around-condition'' ed ha luogo 
se  $\Delta t\ll t_c$.
Esso pu\'o essere eliminato facendo uso di:
\begin{itemize}
\item {FF di tipo Master-Slave}
\item{FF di tipo Edge-Triggered}
\end{itemize}

Il principio su cui sono basati i primi \'e illustrato in figura~\ref{master_slave_f_f} 
(dove ammetteremo che sia J=K=1).

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=master_slave_f_f,width=10.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{master_slave_f_f}
\end{figure}




Il primo dei due FF RS effettua la transizione quando il clock \'e alto. 
Tuttavia in tale intervallo di tempo lo stato di $Q$ e $\qbar$ (uscita del secondo FF) 
non pu\'o cambiare. Infatti, la presenza dell'invertitore prima del $CK_2$  
fa s\'i che in tale intervallo di tempo il secondo FF sia disabilitato.
La transizione di $Q_2$ e $\qbar_2$  avviene solo quando il segnale di clock diviene basso.
Il comportamento di questo FF differisce da quello di un normale JK, per il 
fatto che la transizione dell'uscita avviene sull'impulso negativo del clock.

I FF del tipo edge-triggered non rispondono al livello del clock, ma al fronte 
di discesa di questo. In questo caso gli ingressi non sono letti se non in corrispondenza della 
transizione negativa dell'impulso di clock. 
In maniera analoga, le uscite devono attendere le successive transizioni negative del 
clock per poter variare. 

La figura~\ref{master_slave_ff_out} mostra un esempio di forme d'onda 
per un FF JK del tipo Master-Slave.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=master_slave_ff_out,width=6.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{master_slave_ff_out}
\end{figure}



Come esempi di FF Master-Slave JK possiamo menzionare il modello SN74LS76 della Motorola. 
Questo chip ha due FF JK, come mostrato in figura~\ref{sn74ls76}. Ciascuno dei due FF ha,
oltre agli ingressi J e K, due ingressi di Set e Reset asincroni, denotati con $\overline{S}$
ed $\overline{C}$ nella tabella di figura.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls76,width=10.0 cm,
height=15 cm}}\end{center}
\caption{}
\protect\label{sn74ls76}
\end{figure}



\section{Shift-Registers}

Gli \emph{shift-registers} (SR) (o registri a scorrimento), sono essenzialmente delle 
catene di FF, opportunamente collegati tra loro ed utilizzati per memorizzare 
una ''stringa'' di bits. Esiste una grande variet\'a di SR. 
Consideriamo come primo esempio uno SR seriale realizzato con FF di tipo D.
Ricordiamo che in tale tipo di FF il dato presente sull'ingresso D viene 
trasferito in uscita (Q) all'arrivo di un impulso di clock. 
Uno SR costituito da FF di tipo D \'e mostrato in figura~\ref{d_shift_reg}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=d_shift_reg,width=10.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{d_shift_reg}
\end{figure}

Ammettiamo che un 1 (livello alto) sia applicato all'ingresso ($D_0$) del primo FF, mentre
gli ingressi di Preset e Clear di tutti i FF vengono mantenuti alti. 
L'applicazione di un segnale di clock trasferir\'a tale dato in $Q_0 = D_1$. 
Il successivo segnale di clock trasferir\'a il dato in $Q_1 =D_2$, il terzo 
lo trasferir\'a in $Q_2 =D_3$  ed infine il quarto in $Q_3$ . Alla fine (ammettendo
che $D_0$ sia messo a zero dopo il primo impulso di Clock) le uscite 
$Q_0 , Q_1 , Q_2 , Q_3$  conterranno nell'ordine i bits (0,0,0,1).
Se applicassimo in ingresso la sequenza di bit (1001) ed in fase con tale 
applicazione gli impulsi di clock, avremmo la situazione illustrata in figura~\ref{d_shift_reg_out}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=d_shift_reg_out,width=10.0 cm,
height=10 cm}}\end{center}
\caption{}
\protect\label{d_shift_reg_out}
\end{figure}


Vediamo che, dopo l'applicazione del quarto impulso di clock, nei registri 
$Q_0,\cdots Q_3$ sono contenuti i bit $1 0 0 1$. 
Abbiamo cos\'i trasformato una distribuzione seriale di bits, applicati 
sequenzialmente in ingresso, in una parallela, sulle 4 linee d'uscita $Q_3 - Q_0$.

Notiamo che, se vogliamo che il numero rimanga nel registro dobbiamo, dopo il 
quarto impulso di clock, arrestare quest'ultimo. 
I dati possono alternativamente esser prelevati in forma seriale applicando altri 
quattro impulsi di clock. Questo tipo di registro, che ha un ingresso seriale ed 
un'uscita parallela, \'e chiamato ''Serial-In-Parallel-Out'' (o SIPO).

Il circuito che ora esamineremo pu\'o essere utilizzato indifferentemente per 
immettere dei dati in parallelo ed estrarli in modo seriale, o viceversa. 
Esso pu\'o anche essere adoperato per leggere i dati in serie ed estrarli in serie, 
o per leggerli in parallelo ed estrarli in parallelo. A tale scopo si fa uso di una linea di 
controllo per l'abilitazione dell'input in parallelo. Un esempio di tale circuito (SN74LS195A) 
\'e mostrato in figura~\ref{sn74ls195}. Esso \'e noto come ''Universal Shift Register''.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls195,width=14.0 cm,
height=10 cm}}\end{center}
\caption{}
\protect\label{sn74ls195}
\end{figure}



Tale dispositivo \'e utilizzabile in un'ampia classe di applicazioni, che vanno da
operazioni di ''shift'' al conteggio ed all'imagazzinamento dei dati. Esso, operando a
velocit\'a elevate (dell'ordine di 40 MHz), pu\'o effettuare trasferimento dei dati 
parallelo/seriale, seriale parallelo e shift seriale.

La tabella delle verit\'a mostrata in figura~\ref{sn74ls195_truth} illustra le
caratteristiche di funzionamento.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls195_truth,width=14.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{sn74ls195_truth}
\end{figure}

I dati sono immagazzinati nei quattro FF mostrati in figura.
Se l'ingresso indicato con $\overline{PE}$ (Preset Enable) \'e alto, i dati possono essere
caricati in modo seriale attraverso gli ingressi $J$ e $\overline{K}$ che sono in genere
uniti insieme. Se infatti $J=\overline{K}=1$, ammettendo che sia $Q_0=0$ ($\overline{Q}_0=1$)
la prima delle tre porte AND nel primo blocco a sinistra in figura avr\'a l'uscita alta e, a
causa della doppia inversione presente all'uscita della porta OR sottostante ed all'ingresso
Set del primo FF, avremo $Set=1$. Se $Q_0$ fosse stato uguale ad 1 ($\overline{Q}_0=0$),
sarebbe stata abilitata la seconda anzich\'e la prima delle due porte AND associate al primo
blocco e l'uscita della porta OR sarebbe stata comunque uguale ad 1. Quindi, con $J=\overline{K}=1$
l'ingresso di Set del primo FF sar\'a uguale all'ingresso J. Di conseguenza l'uscita $Q_0$
diverr\'a 1 con il successivo impulso di Clock (pi\'u esattamente, sul fronte di salita di questo).

Notiamo per inciso che, con il $\overline{PE}$ alto, la terza porta AND associata al primo blocco
\'e disabilitata. In tali condizioni l'uscita della porta sar\'a uguale a 0, qualunque sia
il valore presente in $P_0$.

In modo analogo, se $J=\overline{K}=0$, l'ingresso di Set del primo FF sar\'a uguale a 0 e 
quello di Reset 1. Con ci\'o, l'uscita $Q_0$ diverr\'a uguale a 0 in corrispondenza al fronte
di salita del prossimo impulso di Clock. Tale caricamento seriale del dato \'e quello indicato
nella seconda e terza riga della tabella (Shift-Set First Stage - Shift-Reset) di figura~\ref{sn74ls195_truth}.

Esaminiamo ora ci\'o che accade con l'arrivo dei successivi impulsi di Clock. Notiamo che,
con l'ingresso $\overline{PE}$ alto, la prima porta AND di ciascuno dei blocchi mostrati
in figura \'e abilitata (e la seconda disabilitata). Se esaminiamo la porta AND associata
al secondo blocco, vediamo che essa ha come ingresso $Q_0$. Il collegamento della porta
OR sottostante \'e tale che il Set del relativo FF \'e anch'esso uguale a $Q_0$. Vediamo
cos\'i che il successivo impulso di Clock far\'a si che $Q_1$ divenga uguale a $Q_0$ (che
era 1 nel nostro esempio iniziale). In modo analogo vediamo che il collegamento dell'uscita
$Q_1$ del secondo FF alla porta AND del terzo blocco far\'a si che l'uscita $Q_2$ divenga
uguale a $Q_0$ con l'arrivo del terzo impulso di Clock. Infine, il quarto impulso di Clock
far\'a si che $Q_3$ divenga uguale a $Q_0$. Lo shift di quattro posizioni del dato impostato 
in J \'e cos\'i completato con l'applicazione di quattro impulsi di Clock.


Se il $\overline{PE}$ \'e basso, i dati possono essere caricati in parallelo facendo uso degli
ingressi $P_0,P_1,P_2,P_3$. Infatti, con $\overline{PE}=0$, delle porte AND presenti in 
ciascuno dei quattro blocchi, solo quelle all'estrema destra saranno abilitate. Ammettiamo
ora ad esempio che sia: $P_0=1,P_1=0,P_2=1,P_3=0$. Ci\'o implicher\'a: $S_0=1, S_1=0, S_2=1, 
S_3=0$.

 
Questi dati saranno trasferiti in $Q_0$, $Q_1$, $Q_2$, $Q_3$ sul fronte di salita del successivo
impulso di Clock. Si \'e in tal modo effettuato il \emph{caricamento} dei dati impostati sugli 
ingressi ($P_0 \cdots P_3$) in ($Q_0 \cdots Q_3$). Ci\'o \'e indicato nell'ultima riga della
tabella di figura~\ref{sn74ls195_truth}.

Se ora si vuole effettuare lo shift dei dati verso destra, occorre mettere alto il 
$\overline{PE}$. In tal modo il successivo impulso di Clock trover\'a abilitata
la prima porta AND di ciascun blocco, collegata all'uscita Q del blocco precedente.
Il dato sar\'a cos\'i trasferito da $Q_i$ a $Q_{i+1}$.

L'ingresso indicato con $\overline{MR}$ (Master Reset) pu\'o, come mostrato nella prima
riga della medesima tabella, essere adoperato per porre uguali a zero le uscite $Q_0 \dots Q_3$
di tutti i FF della catena. 

Esaminiamo infine il funzionamento del circuito quando $J$ \ $\overline{K}$ assumono i
valori (0,1) o (1,0), con $\overline{PE}$ alto (quinta riga della tabella delle verit\'a).

Se $J=1$ e $\overline{K}=0$, la prima delle porte AND presenti nel primo blocco di figura
sar\'a abilitata, mentre la seconda \'e disabilitata. In tali condizioni l'uscita del
primo AND dipender\'a dal valore di $\qbar_0$ e quindi di $Q_0$. Se $\qbar_0$ \'e alto
($Q_0$ basso) l'uscita dell'AND sar\'a alta e tale risulter\'a quindi l'ingresso di Set
del primo FF. Con ci\'o $Q_0 \rightarrow 1$ e $\qbar \rightarrow 0$ con il successivo
impulso di Clock. Se fosse stato $Q_0=1$ la transizione causata dall'arrivo dell'impulso di
Clock sarebbe stata opposta. Vediamo cos\'i che con $J=1$ e $\overline{K}=0$ il primo FF effettua
la funzione ''TOGGLE'' caratteristica di un JK. 

Il secondo FF, come \'e facile verificare, acquister\'a il valore di $Q_0$ (cio\'e 1) con
il secondo impulso di Clock, il terzo FF con il terzo impulso di Clock etc.

Se invece \'e $J=0$ e $\overline{K}=1$, vediamo che verr\'a ad essere abilitata la seconda
delle porte AND presenti nel primo blocco. Poich\'e questa ha come terzo ingresso $Q_0$, vediamo
che se $Q_0=0$ l'uscita di tale porta, e quindi l'ingresso di Set del FF, sar\'a bassa. Con
ci\'o sar\'a alto l'ingresso di Reset del FF e $Q_0$ rimarr\'a uguale a 0. Se $Q_0$ fosse
stato uguale ad 1 sarebbe invece stato alto l'ingresso di Set del FF e $Q_0$ sarebbe
rimsasto uguale ad 1. Tale funzione \'e indicata con ''Shift, Retain First Stage'' nella
quinta colonna della tabella.

Un registro a scorrimento simile per molti rispetti al precedente, ma con la possibilit\'a
di shift sia a destra che a sinistra, \'e il SN74LS194, la cui struttura \'e mostrata in
figura~\ref{sn74ls194} e la cui tabella delle verit\'a \'e illustrata in 
figura~\ref{sn74ls194_truth}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls194,width=14.0 cm,
height=9 cm}}\end{center}
\caption{}
\protect\label{sn74ls194}
\end{figure}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls194_truth,width=14.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{sn74ls194_truth}
\end{figure}

Un ulteriore tipo di registro che \'e ampiamente adoperato \'e il cosiddetto 
''First-In, First-Out'' (FIFO). Lo schema \'e mostrato in 
figura~\ref{fifo_sr}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=fifo_sr,width=14.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{fifo_sr}
\end{figure}

Come vediamo, esso consiste di un normale SR con possibilit\'a di ingressi 
paralleli. Il dato in input \'e applicato alla porta AND $G_D$ (in modo seriale). 
Le porte $G_0 -G_3$  sono abilitate dagli ingressi $Q_0 \cdots Q_3$ , uno solo 
dei quali \'e normalmente alto. Un opportuno circuito di comando fa s\'i che gli 
ingressi $Q_0,Q_1,Q_2,Q_3$  siano abilitati consecutivamente in corrispondenza ai 
quattro impulsi di clock che agiscono su $G_D$  abilitando l'immissione sulla linea 
L del dato corrispondente. Vediamo ci\'o pi\'u in dettaglio:

\begin{description}
\item[(a)] il primo impulso di clock abilita $G_D$  e manda $Q_0 \rightarrow 1$. 
Simultaneamente (o poco prima) il dato (primo bit) \'e immesso sulla linea L. 
L'abilitazione di $G_0$  fa s\'i che il dato sia caricato in $Q_0$. 
\item[(b)] il secondo bit \'e immesso in ingresso ed il secondo impulso di clock 
applicato. Questo abilita $G_D$  e manda $Q_0 \rightarrow 0$  e $Q_1 \rightarrow 1$. 
In tal modo $G_1$  viene ad essere abilitato ed il dato (secondo bit) caricato in $Q_1$ .
\item[(c)] il terzo bit \'e immesso in ingresso ed il terzo impulso di clock applicato. 
Questo abilita $G_D$   e manda $Q_0, Q_1 \rightarrow 0$ e $Q_2 \rightarrow 1$. 
Ora $G_2$  sar\'a abilitato ed il terzo bit caricato in $Q_2$. 
\item[(d)] il quarto bit \'e immesso in ingresso ed il quarto impulso di clock 
applicato. Questo abilita $G_D$  e manda $Q_0, Q_1, Q_2 \rightarrow 0$ e 
$Q_3 \rightarrow 1$. Ora $G_3$  sar\'a abilitato ed il quarto bit caricato in $Q_3$.
\end{description}

Notiamo che i FF adoperati sono di tipo D, con ingressi di preset e clear. 
L'ingresso di clear \'e quello indicato in figura mentre quello di preset \'e 
ottenuto complementando questo mediante un invertitore (non indicato in figura).

La lettura \'e effettuata applicando impulsi di clock alla linea indicata da $Ck_{out}$. 
Ciascun impulso di clock genera uno shift a destra, di una posizione, di tutti i 
bit memorizzati. 
Da notare che il contatore (non indicato) che abilita in successione le porte 
AND $G_3 - G_0$  viene decrementato durante l'applicazione degli impulsi  $Ck_{out}$. 
In altre parole ammettendo che dopo il quarto impulso di $Ck_{in}$ avessimo 
$Q_0=Q_1=Q_2=Q_3=0$, l'applicazione di un impulso di clock ($Ck_{out}$ pone $Q_0=Q_1=Q_2=0$ e
$Q_3=1$. Se a questo punto immettiamo un nuovo dato, questo sar\'a caricato in FF3. 
Il dispositivo che effettua tale operazione \'e un ''up-down'' counter, che ''conta'' 
gli impulsi di clock che gli arrivano e mette degli opportuni 1 su quattro linee 
d'uscita, in sequenza crescente (cio\'e  $0000, 0001, 0010, 0011, \cdots$) se il clock 
in arrivo \'e $Ck_{in}$; decrescente (cio\'e, $ \cdots 0011, 0010, 0001, 0000$) se il 
clock in ingresso \'e $Ck_{out}$. Ci\'o \'e mostrato schematicamente in 
figura~\ref{up_down_cntr}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=up_down_cntr,width=8.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{up_down_cntr}
\end{figure}


\section{Applicazioni degli Shift-Registers e dei Flip-Flop}

\subsection{Applicazioni degli shift-registers}

Come accennato, questi possono essere adoperati per memorizzare stringhe di 
bits, quali ad esempio bytes o parole di 16/32 bits. 
Essi hanno tuttavia molte altre applicazioni, non meno importanti.
Notiamo intanto che se facciamo scorrere verso destra (right-shift) il contenuto 
di un registro, perdiamo il bit meno significativo. 
Se questo era uguale a 0, il numero immagazzinato viene ad essere diviso per due 
come conseguenza di tale operazione. Se esso era invece 1, allora il numero 
originario meno 1 viene ad essere diviso per 2. Viceversa, uno spostamento a sinistra 
(left-shift) moltiplica per 2 il numero che era stato inizialmente caricato nel registro. 
Vediamo quindi che, con successivi shift-left/shift-right possiamo moltiplicare/dividere 
per potenze di 2 un dato numero. Ovviamente, nel corso di uno shift-right perdiamo 
i bit meno significativi, mentre perdiamo quelli pi\'u significativi nel corso di 
uno shift-left. Questo non \'e un problema se il registro \'e molto lungo.

Un'altra applicazione degli SR \'e la conversione serie/parallelo e viceversa. 
Se carichiamo un numero, ad esempio di 8 bit, in uno SR e lo facciamo in 
parallelo sugli 8 FF di cui il registro \'e costituito, possiamo 
estrarre poi gli 8 bit in serie, applicando 8 impulsi di clock. Viceversa, 
possiamo caricare gli 8 bit in modo seriale e leggerli in parallelo sulle 8 linee 
collegate ai piedini $Q_i$ degli 8 FF.

Gli SR possono inoltre essere convenientemente utilizzati per generare sequenze 
predeterminate di impulsi, dove ciascun impulso pu\'o poi esser utilizzato per 
dar inizio ad una sequenza  di operazioni. 
Immaginiamo infatti di collegare l'uscita dell'ultimo FF di uno SR come quello 
mostrato in figura~\ref{scocca_scintilla}, con l'ingresso di Set del primo FF.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=scocca_scintilla,width=6.0 cm,
height=3.5 cm}}\end{center}
\caption{}
\protect\label{scocca_scintilla}
\end{figure}

Se nei FF  A, B, C, D abbiamo inizialmente caricato i bit (0,0,0,1) 
rispettivamente, l'applicazione di successivi impulsi di clock far\'a ''viaggiare'' 
l'1 da $Q_D$ in $Q_A$, poi da $Q_A$ in $Q_B$, etc. Vediamo cos\'i che dopo 4 
impulsi di clock l'1  \'e tornato in $Q_D$. Le linee $Q_A, Q_B, Q_C, Q_D$, assumeranno 
consecutivamente i valori mostrati nella tabella, dopo il numero di impulsi di clock 
indicato.

\begin{table}[h]
	\begin{center}
		\begin{tabular}{ c | c | c | c | c }
impulsi di Ck & $Q_A$ & $Q_B$ & $Q_C$ & $Q_D$ \\
\hline
0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 \\
2 & 0 & 1 & 0 & 0 \\
3 & 1 & 0 & 1 & 0 \\
4 & 0 & 0 & 0 & 1 \\
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_settima}
\end{table}



Con tale dispositivo possiamo anche abilitare, a comando (tramite gli impulsi di 
clock) una delle quattro linee A, B, C, D (ad esempio, far scoccare la scintilla 
in una delle candele del motore di un'automobile).
 
Ma \'e anche possibile, con tale sistema, generare una sequenza predeterminata di bits.
Ad esempio, se nei quattro FF avessimo inizialmente memorizzato la sequenza 
1001, dopo l'applicazione di successivi impulsi di clock avremmo le sequenze indicate 
nella tabella che segue.

\begin{table}[h]
	\begin{center}
		\begin{tabular}{ c | c | c | c | c }
impulsi di Ck & $Q_A$ & $Q_B$ & $Q_C$ & $Q_D$ \\
\hline
0 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 \\
2 & 0 & 1 & 1 & 0 \\
3 & 0 & 0 & 1 & 1 \\
4 & 1 & 0 & 0 & 1 \\
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_ottava}
\end{table}


Notiamo ancora che, nel primo degli esempi visti, $Q_D$ vale 1 ogni 4 impulsi di 
clock. Un tale sistema pu\'o quindi essere anche adoperato come ''divisore di frequenza'' 
(per 4 nell'esempio considerato, ma si pu\'o ottenere una divisione per potenze 
pi\'u elevate di 2, con registri a molti bit). 
Un tale tipo di utilizzo, dove l'uscita dell'ultimo FF \'e collegata all'ingresso del 
primo, va sotto il nome di ''generatore di sequenze'' o anche ''contatore ad anello'' (ring counter).

Se i FF di cui il registro \'e costituito sono di tipo RS o JK, \'e possibile 
collegare l'uscita dell'ultimo FF della catena con l'ingresso R (o K) del primo. 
Si ottiene cos\'i quello che \'e noto come ''Johnson Counter'' o 
''Twisted-Ring Counter''. Si pu\'o verificare che con tale sistema si pu\'o ottenere 
una divisione di frequenza per 2N, dove N \'e la lunghezza del registro 
(anzich\'e per N come in un normale Ring Counter).

\subsection{Applicazioni dei FF}

I FF sono ampiamente usati per realizzare dei contatori.
Consideriamo come primo esempio quello di figura~\ref{ff_counter} (noto come ripple counter)
che utilizza quattro FF di tipo JK.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=ff_counter,width=12.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{ff_counter}
\end{figure}


Ammettiamo che tutti gli ingressi J e K, come pure quelli di Preset e Clear, siano fissi ad 1.
In tal caso i quattro FF effettueranno la funzione TOGGLE, cio\'e cambieranno stato ad ogni impulso 
presente sull'ingresso di clock. Pi\'u precisamente, la transizione delle uscite avverr\'a sul fronte di discesa dell'impulso di clock. Notiamo ora che per il secondo FF fa da clock l'uscita 
del primo; per il terzo, l'uscita del secondo etc. 
Di conseguenza le forme d'onda sulle uscite $Q_0-Q_3$ saranno quelle mostrate in figura~\ref{ff_counter_out}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=ff_counter_out,width=8.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{ff_counter_out}
\end{figure}


Vediamo che la frequenza di $Q_0$ \'e la met\'a di quella del clock, quella di $Q_1$ 
un quarto etc. Inoltre notiamo che la sequenza dei bit ($Q_3,Q_2,Q_1,Q_0$) inizia con (0,0,0,0) 
poi (0,0,0,1), diviene poi (0,0,1,0), (0,0,1,1) etc, cio\'e il registro $Q_3 \cdots Q_0$ 
''conta'' gli impulsi di clock in arrivo al primo FF. 
Ovviamente, dopo il $15^{mo}$ impulso di clock il contatore si ''resetta'', cio\'e le uscite saranno (0,0,0,0), per poi ricominciare a crescere. 
Se colleghiamo ciascuna delle uscite ad un LED potremo vedere il conteggio (binario) del 
numero di impulsi di clock ricevuto dal FF0.

Il contatore, con una piccola modifica, pu\'o contare ''all'indietro''. E' 
sufficiente a tale scopo che il clock di ciascun FF sia collegato al $\qbar$ (anzich\'e al Q) 
del FF che lo precede. Ci\'o \'e facile da verificare.

E' possibile realizzare anche una catena di FF che, con un opportuno comando di 
controllo, possa contare in entrambi i versi. 
E' sufficiente collegare l'uscita di un FF al clock del successivo come mostrato in 
figura~\ref{conta_indietro}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=conta_indietro,width=9.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{conta_indietro}
\end{figure}


Se l'ingresso X \'e alto, la porta AND  B \'e disabilitata, mentre \'e abilitata 
la A. Il contatore esegue il ciclo in ordine crescente. Se invece l'ingresso X \'e basso, sar\'a abilitata (notare l'invertitore) la porta B e disabilitata la A. 
Il contatore eseguir\'a il ciclo in ordine decrescente. 

E' possibile modificare i collegamenti nel circuito di figura~\ref{ff_counter}, 
in modo da realizzare un contatore che, anzich\'e resettarsi ogni 16 impulsi, si resetti ogni 10. 
Si ottiene in tal modo quello che \'e noto come un ''contatore decimale'' o Binary Coded Decimal (BCD).


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=contatore_base_10,width=13.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{contatore_base_10}
\end{figure}

La modifica \'e illustrata in figura~\ref{contatore_base_10} dove, come nel caso precedente, 
tutti i terminali J e K sono posti al livello logico alto. La presenza della porta AND, con ingressi collegati a Q1 e Q3 e con uscita collegata al Clear, fa s\'i che il 
contatore si resetti non appena Q1=Q3=1. 
Come si pu\'o vedere dalla figura~\ref{ff_counter_out}, ci\'o accade dopo il decimo impulso di clock.


I contatori fin qui esaminati sono noti come ''contatori asincroni''. Ci\'o 
poich\'e la transizione del secondo FF della catena avviene soltanto dopo la transizione del primo (essendo l'ingresso di clock del secondo alimentato dall'uscita 
($Q$ o $\qbar$) del primo, ed analogamente per i successivi. Ci\'o costituisce uno svantaggio, 
poich\'e il tempo di propagazione \'e lungo. Se tutti i FF sono nello stato 
logico 1, tale tempo \'e massimo, poich\'e il successivo intervallo di clock manda 
il primo FF da 1 a 0, questo a sua volta manda il secondo da 1 a 0 (con un ritardo $\tau$), 
il secondo manda il terzo da 1 a 0 (con uguale ritardo) e cos\'i via. Il ritardo 
complessivo sar\'a in tal caso $N\tau$, se N \'e il numero di FF della catena. Per 
ridurre il tempo di propagazione conviene adottare uno schema in cui tutti i FF 
effettuano la transizione simultaneamente. Tale tipo di contatore va sotto il nome di 
''contatore sincrono''. Un esempio di questo \'e mostrato in figura~\ref{contatore_sincrono}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=contatore_sincrono,width=11.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{contatore_sincrono}
\end{figure}


Qui il primo FF (quello relativo alla cifra meno significativa) ha J=K=1, in 
modo da cambiare stato in corrispondenza ad ogni impulso di clock. 
Il secondo FF (B) ha J=K=A, in modo da commutare (in corrispondenza all'arrivo 
di un segnale di clock) solo quando A=1. Il terzo FF (C) commuta quando sia 
A che B sono uguali ad 1. Infine D commuta se \'e verificata la condizione A=B=C=1. 
Come possiamo facilmente verificare (vedasi la tabella che segue) la presenza delle 
porte AND soddisfa la logica insita nella successione dei numeri binari crescenti 
con ($D,C,B,A$) = (0,0,0,0), (0,0,0,1), (0,0,1,0), (0,0,1,1), ... .


\begin{table}[h]
	\begin{center}
		\begin{tabular}{ c  c  c  c  c }
Clock & A & B & C & D \\
\hline
0 & 0 & 0 & 0 & 0  \\
1 & 1 & 0 & 0 & 0  \\
2 & 0 & 1 & 0 & 0  \\
3 & 1 & 1 & 0 & 0  \\
4 & 0 & 0 & 1 & 0  \\
5 & 1 & 0 & 1 & 0  \\
6 & 0 & 1 & 1 & 0  \\
7 & 1 & 1 & 1 & 0  \\
8 & 0 & 0 & 0 & 1  \\
9 & 1 & 0 & 0 & 1  \\
10 & 0 & 1 & 0 & 1  \\
11 & 1 & 1 & 0 & 1  \\
12 & 0 & 0 & 1 & 1  \\
13 & 1 & 0 & 1 & 1  \\
14 & 0 & 1 & 1 & 1  \\
15 & 1 & 1 & 1 & 1  \\
\hline
16 & 0 & 0 & 0 & 0  \\
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_nona}
\end{table}

Infatti, se associamo il bit meno significativo al primo FF(A) e quello pi\'u 
significativo all'ultimo (D), la tabella ci dice che:
\begin{description}
\item[a] il primo FF deve commutare ad ogni impulso  di clock
\item[b] il secondo FF deve commutare in corrispondenza ad un impulso di clock se 
l'uscita di A valeva 1
\item[c] il terzo FF deve commutare in corrispondenza ad un impulso di clock se sia 
l'uscita A che l'uscita B valgono 1
\item[d] l'ultimo FF deve commutare in corrispondenza ad un impulso di clock se tutte 
e tre le uscite A, B, C valgono 1
\end{description}

I collegamenti sono quindi quelli necessari per un conteggio crescente. Vediamo 
che, dopo il il quindicesimo impulso di clock il contatore si resetta automaticamente 
e ricomincia il conteggio.

I contatori sincroni offrono vantaggi di velocit\'a rispetto a quelli asincroni 
esaminati in precedenza, anche se un ritardo aggiuntivo \'e causato dalle porte NAND.
Un contatore sincrono binario a 4 bit, di uso abbastanza generale \'e il 
74LS191. Esso pu\'o eseguire il conteggio in avanti o indietro a seconda del valore 
logico presente sull'ingresso di controllo ''up/down''.
Il 74LS190, la cui struttura interna \'e mostrata in figura~\ref{74ls190} e le cui caratteristiche sono mostrate in figura~\ref{sn74ls190}, \'e praticamente equivalente al 74LS191, con la sola differenza che esso \'e predisposto per il conteggio decimale (BCD).


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=74ls190,width=11.0 cm,
height=8 cm}}\end{center}
\caption{}
\protect\label{74ls190}
\end{figure}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls190,width=11.0 cm,
height=15 cm}}\end{center}
\caption{}
\protect\label{sn74ls190}
\end{figure}

E' possibile, collegando due o pi\'u contatori in serie, realizzare conteggi fino a 
potenze pi\'u elevate di 2 (o di 10). Ad esempio, collegando in serie tre contatori 
BCD 74LS190 \'e possibile, come mostrato in figura~\ref{contatore_mod_1000}, 
realizzare un contatore modulo 1000.


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=contatore_mod_1000,width=11.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{contatore_mod_1000}
\end{figure}

Vediamo che l'ingresso DN/UP (Down/Up) \'e collegato a massa, il che implica un 
conteggio crescente (massa=logico 0).
L'ingresso di clock di tutti e tre i contatori riceve il medesimo segnale 
d'ingresso (cio\'e gli impulsi da contare). 
Il 74LS190 \'e costruito in modo tale che sul piedino con la sigla RC (Ripple Clock Output) 
compaia un impulso ''basso'' (cio\'e uno 0) di durata uguale alla porzione ''bassa'' del clock d'ingresso, quando si verifichi un ''overflow'', cio\'e quando i quattro FF abbiano superato 
il massimo conteggio consentito (9 nel caso del 74LS190). 
Tale livello basso, collegato all'Enable (E) del contatore successivo, 
fa s\'i che questo cominci a contare. Cos\'i, quando il primo contatore (da sinistra) sia 
passato dal 9 allo 0, il secondo inizia a contare. 
Poich\'e per\'o l'Enable ha la durata uguale a quella del livello ''basso'' del clock 
d'ingresso, esso conter\'a solo fino ad 1, mentre il primo contatore ripartir\'a 
da 0, arrivando fino a 9 e poi a 0. A questo punto il primo contatore genera un nuovo RC ed 
invia quindi un'Enable al secondo, che ora passer\'a a 2, e cos\'i di seguito.
Quando anche il secondo contatore sia arrivato a 9 e poi a 0, esso generer\'a un RC e 
quindi invier\'a un'Enable al terzo, che inizier\'a a contare la centinaia.



\section{Alcune applicazioni pratiche di registri e contatori in esperimenti di 
fisica}

Abbiamo gi\'a visto come una catena di FF possa essere utilizzata come divisore 
di frequenza. Un contatore pu\'o essere utilizzato, ovviamente, per contare. 
Ad esempio, se in un processo industriale si vuol contare il numero di oggetti 
che sono passati su di un nastro trasportatore in un certo tempo sar\'a 
sufficiente far uso di un dispositivo (un diodo emettitore di luce (LED) ed una 
cellula fotoelettrica) per generare un impulso ogni volta che la luce emessa dal LED \'e 
interrotta dal passaggio di uno degli oggetti e non arriva quindi alla cellula fotoelettrica. 
Un contatore opportuno incrementer\'a di un'unit\'a il conteggio 
ogni volta che gli arrivi un impulso. Un contatore separato conter\'a il numero 
di impulsi che gli pervengono, generati da un opportuno oscillatore (clock) previamente 
calibrato, che fornir\'a l'informazione temporale.
Possiamo utilizzare un dispositivo simile per misurare l'intervallo di tempo tra 
due eventi. La figura~\ref{misura_intervallo} illustra un sistema di questo tipo. 

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=misura_intervallo,width=9.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{misura_intervallo}
\end{figure}


Gli ''eventi'' in questo caso sono costituiti dal passaggio di un oggetto 
attraverso due traguardi A e B (come nel caso del nastro trasportatore). Un 
primo impulso viene generato al tempo $t_A$ dal passaggio dell'oggetto davanti 
al traguardo A ed un secondo al tempo $t_B$ in cui l'oggetto passa davanti al traguardo B.

L'impulso $t_A$ sia inviato all'ingresso di Set di un FF di tipo RS (in cui era 
inizialmente $Q=0$,  $\qbar=1$) mentre l'impulso generato all'istante $t_B$ sia inviato 
all'ingresso di Reset. Il gate AND che segue \'e collegato a valle ad un contatore 
(opportunamente calibrato), mentre dei due ingressi, uno \'e collegato al Q del FF e 
l'altro riceve una sequenza di impulsi di clock, di frequenza nota. 

Il funzionamento del circuito \'e il seguente: quando l'impulso generato al tempo $t_A$ arriva al FF, questo avr\'a S=1, R=0 e quindi Q=1. Subito dopo sar\'a S=R=0 e quindi lo stato del FF rimane invariato fino al tempo $t_B$, quando R diventa 1 e quindi Q va a 0. Nell'intervallo di tempo $t_B-t_A$ in cui Q=1, la porta AND \'e abilitata e quindi essa lascia passare gli impulsi di 
clock in arrivo. Il contatore che segue conta tali impulsi di clock, il cui numero \'e 
proporzionale all'intervallo di tempo $t_B-t_A$.

Il sistema andr\'a ovviamente calibrato preventivamente. Un dubbio che pu\'o 
venire \'e il seguente. Sia l'impulso generato al tempo $t_A$ che quello generato al 
tempo $t_B$ sono prodotti dal medesimo dispositivo (cellula fotoelettrica seguita 
da monostabile). Come possiamo far s\'i che dei due segnali generati su di una 
stessa linea, uno vada all'ingresso S e l'altro all'ingresso R? Ci\'o \'e semplice 
se sostituiamo il FF RS con un JK in cui J=K=1, come mostrato in figura~\ref{j_k_misura_intervallo}.


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=j_k_misura_intervallo,width=9.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{j_k_misura_intervallo}
\end{figure}


Se inizialmente era Q=0, l'arrivo del segnale generato al tempo $t_A$  manda Q in 
1, mentre il successivo arrivo del segnale generato al tempo $t_B$ manda 
Q in 0 e $\qbar$ in 1.
Un dispositivo molto simile a questo pu\'o essere adoperato se si vuole misurare 
una frequenza, cio\'e il numero di impulsi/sec. Tale dispositivo \'e mostrato in figura~\ref{j_k_conta_impulsi}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=j_k_conta_impulsi,width=9.0 cm,
height=5 cm}}\end{center}
\caption{}
\protect\label{j_k_conta_impulsi}
\end{figure}


Gli impulsi in arrivo (di forma generica, ad esempio sinusoidale) vengono 
trasformati in impulsi rettangolari ed inviati ad uno degli ingressi di una porta AND.
L'altro ingresso della porta \'e collegato all'uscita Q di un FF JK con J=K=1, 
che riceve sull'ingresso di clock un segnale ottenuto demoltiplicando per un 
fattore $10^6$ un segnale di 1 MHZ. In tale circostanza Q \'e uguale ad 1 per un 
tempo di 1s. La porta AND sar\'a quindi abilitato per 1~s 
ed il contatore conter\'a il numero di impulsi che in tale tempo gli arrivano, 
cio\'e la frequenza voluta. 
Naturalmente occorrer\'a aggiungere qualcosa al circuito per far s\'i che alla fine dell'intervallo
di tempo (di 1~s), il sistema si arresti e consenta la lettura del contatore.
Anche se non specificamente relativo ad applicazioni in esperimenti di fisica, 
incontra ampio utilizzo il contatore decimale illustrato a pag. 66. 
Ad esempio, nel contatore BCD (Binary Coded Decimal) il numero \'e espresso come una sequenza 
di cifre decimali. Ad esempio, il numero 3702 \'e memorizzato come:

\begin{table}[htbp]
	\begin{center}
		\begin{tabular}{ c c c c }
		0011 & 0111 & 0000 & 0010 \\
		3 & 7 & 0 & 1 
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_decima}
\end{table}

I dati provenienti dalla tastiera di un computer sono normalmente espressi in 
BCD, anche se si tratta di caratteri. 
Infatti, a ciascuno di questi \'e possibile associare, mediante un codice (ad esempio 
il codice ASCII - American Standard Code Ser Information Exchange), in maniera del tutto 
analoga ai numeri, una stringa di bit. 
Il codice ASCII \'e a 7 bit. I principali caratteri ed i codici corrispondenti sono 
mostrati nella tabella di figura~\ref{ascii_codes}. L'integrato 74LS93, che consente il conteggio 
fino a 16, pu\'o essere azzerato, come si \'e visto, in corrispondenza della cifra binaria corrispondente al numero 9. E' per\'o pi\'u conveniente usare un contatore predisposto 
per contare in base 10, come il 74LS90.

Nella tabella dei codici ASCII mostrata in figura~\ref{ascii_codes}, la prima colonna contiene il numero in decimale, la seconda il corrispondente valore esadecimale, la terza il corrispondente
simbolo.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=ascii_codes,width=12.0 cm,
height=18 cm}}\end{center}
\caption{}
\protect\label{ascii_codes}
\end{figure}





Un'alternativa spesso adoperata \'e quella di un contatore con uscita esadecimale (base 16). 
Come visto, in tale rappresentazione, un numero e.g. di 2 bytes (16 bit) \'e rappresentato da 
una stringa di 4 carattere esadecimali. Ad esempio, il numero binario: 
$1010\;1101\;0110\;0011$ \'e rappresentato in esadecimale da: $AD63$.


\section{Decodificatori e  Display}

Per visualizzare un numero binario abbiamo varie alternative. La prima \'e 
quella, ovvia, di visualizzare ogni singolo bit mediante un LED. Se il LED \'e acceso il bit corrispondente vale 1, se esso \'e spento vale 0.
Tale soluzione non \'e pratica per la visualizzazione di numeri con molti bit. 
Essa inoltre non offre una lettura immediata del numero, pi\'u comoda se fatta in 
decimale o in esadecimale.

Utilizzando una decodifica BCD, dove occorre decodificare soltanto i numeri da 0 
a 9 (in binario da (0,0,0,0) a (1,0,0,1)) si pu\'o far uso del chip 74LS42, 
che \'e un integrato a 16 pin. Il display pu\'o essere effettuato utilizzando dei 
''display a 7 segmenti'', in cui a ciascun numero BCD (tra 0 e 9) corrisponde l'accensione 
degli opportuni segmenti luminosi (LED), come mostrato in figura~\ref{seven_segments}.


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=seven_segments,width=10.0 cm,
height=6 cm}}\end{center}
\caption{}
\protect\label{seven_segments}
\end{figure}


L'identificazione dei segmenti \'e quella mostrata in corrispondenza dell'8, in basso
nella figura. Il decodificatore BCD a sette segmenti 74LS48, mostrato in figura~\ref{74ls48r}, 
\'e un  decoder/driver adatto a comandare i segmenti di un LED.
Esso contiene sia la circuiteria che fornisce la decodifica dei quattro bit d'ingresso 
nelle 7 linee d'uscita, sia quella di alimentazione dei singoli segmenti.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=74ls48r,width=10.0 cm,
height=12 cm}}\end{center}
\caption{}
\protect\label{74ls48r}
\end{figure}

L'indicatore pu\'o essere spento portando a 0 l'ingresso di blanking ($\overline{BI}$: pin 4).

La tabella delle verit\'a di tale circuito \'e mostrata, insieme al display riassuntivo e
ad altre caratteristiche, in figura~\ref{sn74ls48r}

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=sn74ls48r,width=12.0 cm,
height=12 cm}}\end{center}
\caption{}
\protect\label{sn74ls48r}
\end{figure}


La decodifica per gruppi di 4 dal binario all'esadecimale pu\'o essere effettuata 
utilizzando l'integrato 74LS154,le cui caratteristiche sono mostrate in figura~\ref{dm74ls154}. 
Questo ha 16 uscite, corrispondenti ciascuna ad uno dei 16 simboli da 0 a 15 (F esadecimale). 
Ciascuna delle 16 uscite pu\'o essere collegata ad un opportuno LED, che si accende quando l'uscita 
corrispondente assuma il livello basso.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=dm74ls154,width=12.0 cm,
height=15 cm}}\end{center}
\caption{}
\protect\label{dm74ls154}
\end{figure}

Un circuito che effettua sullo stesso chip sia la decodifica che il display 
esadecimale \'e il TIL311. Questo riceve sui piedini (3,2,13,12) il carattere esadecimale 
(con il 3 il bit meno significativo ed effettua un display esadecimale del relativo carattere 
(cio\'e da 0 ad F). Questo display \'e quello adoperato in alcune delle esperienze di 
laboratorio.
Le caratteristiche di tale integrato sono mostrate nelle figure~\ref{til_311} e~\ref{til_311_details}.

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=til_311,width=7.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{til_311}
\end{figure}


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=til_311_details,width=10.0 cm,
height=12 cm}}\end{center}
\caption{}
\protect\label{til_311_details}
\end{figure}




La figura~\ref{til_311_blocchi} mostra uno schema a blocchi del TIL311.


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=til_311_blocchi,width=9.0 cm,
height=9 cm}}\end{center}
\caption{}
\protect\label{til_311_blocchi}
\end{figure}

Notiamo la presenza di un ''Latch'' in ingresso. Questo \'e essenzialmente un 
insieme di 4 FF di tipo D. 
Questo ha lo scopo di ''mantenere'' i dati presentati in ingresso, per il tempo 
necessario alla decodifica ed al successivo display a lettura. Pi\'u precisamente, 
finch\'e il segnale presente sul piedino 5 \'e basso, le uscita del Latch seguono 
l'ingresso (piedini 3,2,13,12). Quando il segnale \'e alto, le uscite non cambiano pi\'u.
Si noti la presenza di due terminali d'ingresso (4 e 10) per l'accensione del 
punto decimale a destra ed a sinistra rispettivamente. 
Questi LED sono accesi attraverso gli invertitori indicati in figura.


\section{Moltiplicazione e divisione in binario}

L'operazione di moltiplicazione in binario tra due bit equivale all'AND di essi:

\begin{table}[htbp]
	\begin{center}
		\begin{tabular}{ c c c c c }
0 & $\times$ & 0 & = & 0 \\
1 & $\times$ & 0 & = & 0 \\
0 & $\times$ & 1 & = & 0 \\
1 & $\times$ & 1 & = & 1 \\		
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_undicesima}
\end{table}

La moltiplicazione tra numeri di pi\'u bit pu\'o essere effettuata con una semplice 
estrapolazione dell'analogo processo nel sistema decimale. Mostriamo alcuni esempi.

\begin{table}[htbp]
	\begin{center}
		\begin{tabular}{ c c c c c c c c r c}
 & & & 1 & 0 & 1 & 1 & = & 11 & $\times$ \\
 & & & 0 & 1 & 0 & 1 & = & 5 &  \\
\hline
 & & & 1 & 0 & 1 & 1 &  &  &  \\
 & & 0 & 0 & 0 & 0 & & & &\\
 & 1 & 0 & 1 & 1 & & & & &\\
0 & 0 & 0 & 0 & & & & & &\\
\hline
 & 1 & 1 & 0 & 1 & 1 & 1 & = & 55 &\\
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_dodicesima}
\end{table}



\begin{table}[htbp]
	\begin{center}
		\begin{tabular}{ c c c c c c c c r c}
 & & & 1 & 1 & 0 & 1 & = & 13 & $\times$ \\
 & & & 1 & 0 & 0 & 1 & = & 9 &  \\
\hline
 & & & 1 & 1 & 0 & 1 &  &  &  \\
 & & 0 & 0 & 0 & 0 & & & &\\
 & 0 & 0 & 0 & 0 & & & & &\\
1 & 1 & 0 & 1 & & & & & &\\
\hline
1 & 1 & 1 & 0 & 1 & 0 & 1 & = & 117 &\\

			
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_tredicesima}
\end{table}

Vediamo che ciascun bit del secondo numero (a partire dalla destra) deve essere 
moltiplicato per i bit del primo. A tali ''moltiplicazioni'' potranno provvedere 
delle porte AND. Il risultato ottenuto dalla moltiplicazione del primo bit 
andr\'a sommato al risultato della moltiplicazione del secondo, shiftato a 
sinistra di una posizione; questo andr\'a sommato al risultato della 
moltiplicazione del terzo bit, shiftato a sinistra di due posizioni ... etc.
Vediamo cos\'i che un ''moltiplicatore'' pu\'o esser ottenuto effettuando 
sequenzialmente degli AND, degli shift e delle somme. 
Il circuito mostrato in figura~\ref{multiplier_4bit} illustra una possibile implementazione di un 
moltiplicatore di due numeri a 3 bit. 


\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=multiplier_4bit,width=15.0 cm,
height=9 cm}}\end{center}
\caption{}
\protect\label{multiplier_4bit}
\end{figure}



Per il risultato della moltiplicazione \'e ovviamente necessario un 
registro a 6 bit. Il circuito comprende uno SR a 5 bit per il 
moltiplicando, uno SR a 3 bit per il moltiplicatore ed un accumulatore a 6 bit, 
oltre ad un sommatore a 6 bit.
Inizialmente si azzera il registro accumulatore, si caricano i tre bit del 
moltiplicatore nel relativo registro (con $Q_0$ corrispondente al bit meno significativo) 
ed i tre bit del moltiplicando nei registri $Q_0-Q_2$ corrispondenti. 
Le uscite delle cinque porte NAND contengono a questo punto i prodotti del bit meno 
significativo del moltiplicatore ($Q_0$) per i tre bit del moltiplicando. Pi\'u in 
particolare, la porta indicata con \emph{e} fornisce il prodotto dei due bit meno 
significativi dei due numeri, la porta \emph{d} fornisce il prodotto del bit $Q_0$ 
del moltiplicatore per il bit $Q_1$ del moltiplicando, la porta \emph{c} fornisce 
il prodotto del bit $Q_0$ del moltiplicatore per il bit $Q_2$ del moltiplicando. 
Le porte \emph{a} e  \emph{b} sono per il momento al livello logico 0. 
I prodotti parziali cos\'i ottenuti sono ora disponibili agli ingressi del 
sommatore, in $B_0, B_1, B_2$. Essi sono anche disponibili all'uscita del 
sommatore ($S_0, S_1, S_2$) essendo gli altri ingressi ($A_0, A_1, A_2$) per il 
momento nulli. Al primo impulso di clock, il prodotto parziale ($S_0, S_1, S_2$) 
viene trasferito nei tre FF all'estrema destra del registro accumulatore e 
contemporaneamente agli ingressi ($A_0, A_1, A_2$) del sommatore. 
Il medesimo impulso di clock agisce sul registro moltiplicatore e sul registro 
moltiplicando nel modo seguente:

\begin{enumerate}
\item I bit del registro moltiplicatore vengono spostati in alto di una posizione,
con che $Q_1$ viene trasferito in FF0
\item i tre bit del moltiplicando vengono spostati a sinistra di una posizione.
\end{enumerate}

Notiamo che ora il registro all'estrema destra del moltiplicando \'e a livello 
logico 0.
E' facile vedere che l'uscita della porta AND indicata con \emph{e}  \'e a livello 
logico 0, mentre le uscite dalle porte (\emph{d}, \emph{c}, \emph{b}) contengono i prodotti del secondo bit del moltiplicatore per i tre bit del moltiplicando. 
Notiamo anche che con tale metodo, i tre bit ottenuti sono presenti agli 
ingressi ($B_1, B_2, B_3$) del sommatore e quindi risultano gi\'a shiftati a 
sinistra di una posizione, che \'e proprio quel che si fa nella moltiplicazione binaria. 
Ora all'uscita del sommatore comparir\'a, in ($S_0, S_1, S_2, S_3, S_4$) la somma del risultato
della prima moltiplicazione e di quello della seconda. 
Il successivo impulso di clock trasferisce tali uscite nei corrispondenti FF dell'accumulatore e quindi agli ingressi ($A_0, ..., A_4$) del sommatore.

Il medesimo impulso di clock causa uno shift del bit pi\'u significativo del registro 
moltiplicatore (che era a questo punto in FF1) nel registro FF0 e simultaneamente 
sposta di una posizione a sinistra i bit del registro moltiplicando. 
Notiamo che ora i registri FF0 ed FF1 del moltiplicando saranno a livello logico 0.
Le uscite delle porte AND (\emph{c}, \emph{b}, \emph{a}) forniscono ora i prodotti del 
bit pi\'u significativo del moltiplicatore per i tre bit del moltiplicando. 
Tali prodotti sono ora disponibili agli ingressi ($B_2, B_3, B_4$) del sommatore. 
Questo fornir\'a ora alle uscite ($S_0 - S_5$) la somma finale richiesta. 
Sar\'a sufficiente un ulteriore impulso di clock per trasferirla nell'accumulatore e 
simultaneamente azzerare il registro moltiplicatore.

Il processo, effettuato come si \'e visto in modo seriale, \'e intrinsecamente 
lento. Esistono per\'o in commercio dei moltiplicatori che effettuano le operazioni in 
parallelo, con un notevole guadagno in velocit\'a.

\section{La divisione in binario}

L'idea base di un circuito digitale che effettua l'operazione di divisione tra 
due numeri interi (positivi) pu\'o essere illustrata con un semplice esempio, relativo 
al caso di numeri decimali. Ammettiamo infatti di voler dividere 33 per 7. 
Possiamo sottrarre il 7 dal 33 e verificare che la differenza (26) sia maggiore di 7. 
In tal caso sottraiamo da tale differenza ancora una volta il 7, ottenendo: 
\[
26-7=19
\]
Procedendo ancora troviamo: 
\[
19-7=12
\]
\[
12-7=5
\]

Poich\'e l'ultima differenza trovata \'e minore di 7, dobbiamo arrestare il 
processo e potremo dire che la parte intera del numero che esprime il rapporto 
\'e pari al numero delle sottrazioni effettuato, cio\'e 4.
Dobbiamo ora calcolare la parte frazionaria del rapporto. A tale scopo sottraiamo 
ora 0.7 dall'ultima differenza trovata (5), tante volte quante ne occorrono per 
ottenere un resto inferiore a 0.7:
\begin{table}[htbp]
	\begin{center}
		\begin{tabular}{ r c r c r r }
		5& -& 0.7 & = & 4.3 & (1) \\
		4.3& - & 0.7 & = & 3.6 & (2) \\
		3.6& - & 0.7 & = & 2.9 & (3) \\
		2.9& - & 0.7 & = & 2.2 & (4) \\
		2.2& - & 0.7 & = & 1.5 & (5) \\
		1.5& - & 0.7 & = & 0.8 & (6) \\
		0.8& - & 0.7 & = & 0.1 & (7) \\			
		\end{tabular}
	\end{center}
\caption{}
\protect\label{logici_quattordicesima}
\end{table}

Poich\'e il numero di sottrazioni effettuate \'e 7, concludiamo che 7 \'e la prima cifra decimale. 
Il rapporto desiderato, con la precisione di una cifra decimale \'e quindi 4.7. Per ottenere la successiva cifra possiamo procedere in modo analogo: sottraiamo 0.07 da 0.1 tante volte 
quante ne occorrono per trovare un resto inferiore a 0.07.

Troviamo cos\'i che la successiva cifra decimale \'e un 1, ed il rapporto \'e, a 
questo livello di precisione, 4.71. 
Il processo pu\'o essere ripetuto fino al livello di precisione voluto.


Ci proponiamo ora di vedere come il conteggio necessario per ottenere \emph{la parte 
intera} del rapporto voluto possa essere implementato in logica binaria.
Ammettiamo, per esemplificare, che divisore N e dividendo D abbiano 4 bit, e che 
il dividendo sia maggiore del divisore. Ad esempio sia D=$14_D=1110_B$  ed N=$4_D=0100_B$.
La prima sottrazione, effettuata con il metodo del complemento a 2, fornisce:



\vspace{0.5 cm}
\begin{center}
		\begin{tabular}{ l c c c c c c }
& & 1 & 1 & 1 & 0 & + \\
& & 1 & 1 & 0 & 0 & = \\
\hline
$carry \rightarrow$ & 1 & 1 & 0 & 1 & 0  \\
			
		\end{tabular}
	\end{center}
\vspace{0.5 cm}


Abbiamo cio\'e un bit di riporto (o di overflow), il quale indica che la 
differenza (uguale a $1010_B=10_D$) \'e positiva. Sottraendo ancora abbiamo:

\vspace{0.5 cm}
\begin{center}
		\begin{tabular}{ l c c c c c c }
& & 1 & 0 & 1 & 0 & + \\
& & 1 & 1 & 0 & 0 & = \\
\hline
$carry \rightarrow$ & 1 & 0 & 1 & 1 & 0  \\
			
		\end{tabular}
	\end{center}
\vspace{0.5 cm}



Abbiamo ancora una differenza positiva (come evidenziato dalla presenza del bit 
di riporto) uguale a  $6_D$.
Un'ulteriore sottrazione fornisce:

\vspace{0.5 cm}
\begin{center}
		\begin{tabular}{ l c c c c c c }
& & 0 & 1 & 1 & 0 & + \\
& & 1 & 1 & 0 & 0 & = \\
\hline
$carry \rightarrow$ & 1 & 0 & 0 & 1 & 0  \\
			\end{tabular}
	\end{center}
\vspace{0.5 cm}


cio\'e un numero positivo ($2_D$). Successivamente si ottiene:

\vspace{0.5 cm}
\begin{center}
		\begin{tabular}{ l c c c c c c }
& & 0 & 0 & 1 & 0 & + \\
& & 1 & 1 & 0 & 0 & = \\
\hline
$carry \rightarrow$ & 0 & 1 & 1 & 1 & 0  \\
		\end{tabular}
	\end{center}
\vspace{0.5 cm}

Vediamo che ora il bit di riporto \'e 0, cio\'e la differenza \'e negativa. La 
parte intera del rapporto desiderato \'e pari al numero di volte che la differenza 
ha fornito un bit di riporto uguale ad 1, cio\'e $3_D$.
Un circuito che realizza la funzione desiderata \'e quello mostrato in figura~\ref{divisore_4bit}. 

\begin{figure}[h]
  \begin{center}\mbox{\epsfig{file=divisore_4bit,width=15.0 cm,
height=7 cm}}\end{center}
\caption{}
\protect\label{divisore_4bit}
\end{figure}



Il dividendo \'e caricato in un registro, costituito da quattro FF di tipo D. 
Il sommatore indicato effettua la somma del contenuto di questo registro e del 
complemento a 2 del divisore, indicato in figura con $\hat{N}_3,\hat{N}_2,\hat{N}_1,\hat{N}_0$.
Il dividendo \'e caricato inizialmente nel registro.
Dopo che la prima somma sar\'a stata effettuata, il riporto $C_3=1$, mentre i 
registri $Q_3, Q_2, Q_1, Q_0$ conterranno il risultato della differenza tra dividendo 
e divisore.
Poich\'e $C_3=1$, il prossimo impulso di clock far\'a avanzare il contatore di una 
unit\'a. Ora il sommatore effettuer\'a la differenza tra il nuovo contenuto del registro ed il divisore. 
Se $C_3$ \'e ancora uguale ad 1, la porta AND continuer\'a ad essere abilitata ed il contatore avanzer\'a di una unit\'a al prossimo impulso di clock. 
Il processo si ripete fino a quando $C_3$ non sia divenuto uguale a 0, al qual punto 
il contatore si arresta.
\newpage