\chapter{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}}
\newcommand{\aoverbar}{\overline{A}}
\newcommand{\boverbar}{\overline{B}}
\newcommand{\coverbar}{\overline{C}}
\newcommand{\doverbar}{\overline{D}}
\section{Introduzione}

Una delle prime esigenze che nel corso del processo di civilizzazione
l'uomo ha incontrato, \`e stata quella di \emph{contare} gli oggetti
ed adoperare una qualche \emph{rappresentazione grafica} per indicare
il risultato di tale conteggio. Legata a questa \`e stata l'esigenza
di \emph{operare} su tali conteggi (sommare, sottrarre etc.).

I Romani, che pure avevano realizzato progressi impressionanti nel
campo dell'Ingegneria, avevano adottato un sistema che, in analogia a
sistemi adottati in altre antiche civilt\`a, associava un simbolo a
ciascuno dei pi\`u importanti tra i numeri. Cos\`{\i}: I=1, V=5, X=10,
L=50, C=100, D=500, M=1000. Per rappresentare un numero generico si
ricorreva ad una opportuna combinazione di tali simboli. Ad esempio il
numero 27 si scriveva come: 10+10+5+2, ovvero: XXVII. Gi\`a in tale
sistema aveva una certa importanza un concetto che \`e fondamentale
nel \Index{sistema decimale}: il \emph{peso} attribuito alla
\emph{posizione} del simbolo all'interno della rappresentazione di un
dato numero. Cos\`{\i}: XI=11, ma IX=9.

Tale sistema non era certo il pi\`u adatto ad \emph{operare} su numeri
(sommare, moltiplicare etc.). Nell'antica Cina era stato invece
sviluppato un sistema interamente \emph{posizionale} ed un sistema di
calcolo basato su tale sistema.

Tuttavia, il passo fondamentale nello sviluppo di un sistema che si
prestava sia alla rappresentazione di numeri arbitrariamente grandi
che ad operazioni su di essi f\`u compiuto in Egitto nel 3400~AC ed in
Mesopotamia nel 3000~AC. Il passo consistette nell'associare al
sistema posizionale, l'uso dello ``zero''.

Tale sistema fu importato in Occidente attorno al 1200 dal Pisano
\emph{Leonardo Fibonacci\index{Fibonacci! Leonardo}}, figlio di un
mercante che viaggiava spesso nei paesi Africani e dell'Est. Egli, nel
suo ``Liber Abbaci'' introdusse le cifre decimali (''novem figurae
Yndorum'') ed il segno ``zephyrum'' (lo zero).

Il sistema, noto oggi come ``\Index{sistema Arabo}'', associava ad uno
``0'' posto alla destra di una cifra decimale (1-9) il significato di
``moltiplicare per 10''.  Inoltre, una cifra decimale posta alla
destra di un'altra cifra (o gruppo di cifre) implicava:
``\Index{moltiplicazione} per 10 seguita dalla somma del risultato
alla cifra posta a destra''. Cos\`{\i}:
\[
27=20 \times 10 + 7
\]

La ragione per l'uso di 10 simboli diversi (nove pi\`u lo zero) era
ovviamente legata all'associazione dei simboli con le dita delle mani
(da cui la dizione Inglese ``\Index{digit}'').

In un \Index{sistema elettronico digitale} l'equivalente delle 10 dita
sono i due stati in cui il sistema pu\`o trovarsi (transistor in
conduzione o interdizione, tensione accesa o spenta etc.). I simboli
divengono cos\`{\i} 2, ``0'' ed ``1''. Il ``digit'' diventa ora il
``\Index{bit}''.




\section{Sistemi di numerazione}

\subsection{Il sistema binario}
 
Nella vita quotidiana siamo abituati ad usare il \Index{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 ``\Index{celle di
memoria}\index{memoria! celle di}'' 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 \Index{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 ``\Index{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 \Index{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 \Index{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
\Index{convertire in decimale} il seguente \Index{numero binario}:
\[
1\;0\;1\;1\;0\;1\;0\;1\;1
\]
Seguiremo la procedura mostrata nella tabella~\ref{logici_tab_1}:

\renewcommand{\arraystretch}{1.2}

\begin{table}[htb!]  
\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}
\caption{Procedura di trasformazione del \Index{numero binario}
  101101011 in un numero decimale.}  \protect\label{logici_tab_1}
\end{center}
\end{table}





Seguendo il procedimento indicato riusciamo a \Index{convertire in
decimale}, mentalmente ed in modo rapido, un \Index{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 \`e esprimibile come
mostrato nella tabella~\ref{logici_tab_2}:

\begin{table}[htb!]  
\begin{center}
\begin{tabular}{|c r c r|}
\hline $9 \times 10^0$ & (9) & + & \\ $5 \times 10^1$ & (50) & + & \\
$1 \times 10^2$ & (100) & + & \\ $4 \times 10^3$ & (4000) & + & \\ $1
\times 10^4$ & (10000) & + & \\ $3 \times 10^5$ & (300000) & = &
314159 \\ \hline
\end{tabular}
\caption{Esempio di un numero decimale espresso facendo uso delle
  potenze di 10.}  \protect\label{logici_tab_2}
\end{center}
\end{table}

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
mostrato in tabella~\ref{logici_tab_3}:

\begin{table}[htb!] 
\begin{center}
\begin{tabular}{| c r c r |}
\hline $0 \times 2^0$& (0) & + & \\ $1 \times 2^1$& (2) & + & \\ $0
\times 2^2$& (0) & + & \\ $1 \times 2^3$& (8) & + & \\ $1 \times 2^4$&
(16) & + & \\ $1 \times 2^5$& (32) & + & \\ $0 \times 2^6$& (0) & + &
\\ $0 \times 2^7$& (0) & + & \\ $1 \times 2^8$& (256) & = & 314 \\

\hline
\end{tabular}
\end{center}
\caption{Esempio di un \Index{numero binario} espresso facendo uso
  delle potenze di 2.}  \protect\label{logici_tab_3}
\end{table}


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

\subsection{Il \Index{sistema ottale}}

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, come mostrato nella tabella~\ref{logici_tab_4}:

\begin{table}[htb!]
\begin{center}
\begin{tabular}{|l l l |}
\hline $7 \times 8$&=&56\\ $56 + 2 $&=&58\\ \hline
\end{tabular}
\caption{Procedura di trasformazione di un \Index{numero ottale} in un
decimale.}  \protect\label{logici_tab_4}
\end{center}
\end{table}



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

\subsection{Il \Index{sistema esadecimale}}

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 la situazione mostrata
nella tabella~\ref{logici_tab_5}:

\begin{table}[htb!]
\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}
\caption{Corrispondenza tra le lettere che costituiscono parte del
  \Index{sistema esadecimale}, e i numeri decimali.}
  \protect\label{logici_tab_5}
\end{center}
\end{table}

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 \Index{numero esadecimale} ``1A'' in decimale \`e
quello mostrato nella tabella~\ref{logici_tab_6}:

\begin{table}[htb!]
\begin{center}
\begin{tabular}{|l l l l l|}
\hline 1 & $\times$ & 16 & = & 16 \\ 16 & + & A & = & 26\\ \hline
\end{tabular}
\caption{Procedura di trasformazione di un \Index{numero esadecimale}
in uno decimale.}  \protect\label{logici_tab_6}
\end{center}
\end{table}




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

\subsection{\index{conversione tra sistemi diversi}Conversioni tra sistemi diversi}

\`E facile convertire in ottale un \Index{numero binario}.  Basta
tener presente che un insieme di tre \Index{bit} binari pu\`o
rappresentare i numeri base del \Index{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\index{numero 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 \Index{numero binario} dato e
sostituire a ciascun gruppo il corrispondente \Index{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
\Index{numero ottale} o esadecimale\index{numero esadecimale} in un
\Index{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 \Index{numero binario} richiesto.}
\end{description}

Vediamo ci\`o con un esempio

\[
[374]_{10}\:=\:[?]_2
\]
Le successive operazioni sono quelle mostrate nella
tabella~\ref{logici_tab_7}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r r r|}
\hline \index{divisione}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}
\caption{Procedura di conversione di un numero decimale in un
\Index{numero binario}.}  \protect\label{logici_tab_7}
\end{table}



Il \Index{numero binario} \`e quindi:
\[
        1\: 0\: 1\: 1\: 1\: 0\: 1\: 1\: 0
\]

\subsection{Numeri binari frazionari\index{numero binario! frazionario}}

Cos\`{\i} come nel \Index{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
\Index{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 e
sottraiamo un 1 dal risultato. Se non lo \`e scriveremo 0 e non
effettueremo la sottrazione:

\[
1.625\:-\:1\:=\:0.625 \Rightarrow \fbox{1}
\]

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

\[
0.625 \times 2 \:=\:1.25 \: \ge 1 \Rightarrow \fbox{1}
\]
\[
1.25 \:-\:1\:=\:0.25\]

Moltiplichiamo ancora 0.25 per 2 e verifichiamo:
\[
0.25 \times 2 \: = \: 0.5 \:\: < 1 \Rightarrow \fbox{0}
\]

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

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

La sequenza di 1 e 0 scritta, letta dall'alto verso il basso,
rappresenta il numero frazionario\index{numero binario! 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
\]

\subsection{\index{codifica di numeri binari}Codifica di numeri binari in un computer}

In una macchina a 32 \Index{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\:=\:2147483647
\]
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 \Index{parte frazionaria}. Ci\`o \`e in
fondo analogo a quanto facciamo nel \Index{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 \Index{IBM}/370, un ``parola'' di 32 bit era divisa in due
gruppi di bits, come mostrato nella tabella~\ref{logici_tab_8}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| l | l | l|}
\hline S& caratteristica (7 bits) & \Index{parte frazionaria} (24
bits) \\ \hline
0&1~~~~~~~~~~~~~~~~~~~~~~~~~7&8~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~31 \\
\hline
\end{tabular}
\caption{Rappresentazione standard dei numeri per il sistema
\Index{IBM}/370.}  \protect\label{logici_tab_8}
\end{center}
\end{table}





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 \Index{parte frazionaria}. Il punto decimale va
immaginato alla sinistra del bit pi\`u significativo della parte
frazionaria.\index{numero binario! frazionario}

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 \Index{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
``\Index{floating point}'' (ovvero, in italiano, ``in virgola
mobile'') quando si adotti la ``\Index{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
``\Index{byte}'', una parola ``singola precisione'' \`e costituita da
4 bytes, una in ``\Index{doppia precisione}'' da 8 bytes, ed una in
``precisione estesa'' da 16 bytes.


\subsection{Il \Index{codice Gray}}

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
\Index{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 Gray.  In
tale codice, i numeri binari 0 ed 1 corrispondono allo 0 ed 1 decimale
rispettivamente, come mostrato nella tabella~\ref{logici_tab_9}.

\begin{table}[htb!]
\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}
\caption{Regola di conversione tra i numeri ``binari'' del
  \Index{codice Gray} e quelli decimali.}
  \protect\label{logici_tab_9}
\end{center}
\end{table}




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 Gray \`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 \Index{codice Gray} in \Index{applicazioni}
elettroniche, dove i tempi di commutazione degli elementi che
memorizzano i diversi bit possono differire leggermente.

\section{Porte logiche\index{porte logiche}}

L'informazione elementare alla base del funzionamento di un qualsiasi
sistema digitale \`e il \Index{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 \Index{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\index{logica
negativa}.

Una \Index{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 \Index{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
\Index{NOT}, o invertitore.  Se A \`e la variabile, l'applicazione
della funzione NOT fornisce una nuova variabile che \`e il
\Index{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 \Index{simbolo del circuito} elettronico che implementa tale
operazione \`e quello mostrato in figura~\ref{not_symbol}:

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/not_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{NOT}.}  \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
\Index{NOT} questa \`e mostrata in figura~\ref{logici_tab_10}:


\begin{table}[htb!]
\begin{center}
\begin{tabular} {| c | c |}
\hline A& $Y=\overline{A}$ \\ \hline 0& 1 \\ 1& 0 \\ \hline
\end{tabular}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per la
funzione \Index{NOT}.}  \protect\label{logici_tab_10}
\end{center}
\end{table}


La funzione \Index{OR} a due ingressi \`e definita dalla tabella delle
verit\`a~\ref{logici_tab_11}.

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per la
funzione \Index{OR}.}  \protect\label{logici_tab_11}
\end{center}
\end{table}



Cio\`e l'\Index{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
\Index{OR} \`e il +:

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/or_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{OR}.}  \protect\label{or_symbol}
\end{figure}


La funzione \Index{AND} a due ingressi \`e definita dalla tabella
delle verit\`a~\ref{logici_tab_12}.

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per la
funzione \Index{AND}.}  \protect\label{logici_tab_12}
\end{center}
\end{table}



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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/and_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{AND}.}  \protect\label{and_symbol}
\end{figure}


L'operatore che indica la funzione \Index{AND} \`e quello della
moltiplicazione: $A \cdot B$.

Porte OR ed AND 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 \Index{funzioni logiche}
per definire nuove funzioni.  Cos\`{\i} ad esempio, un AND seguito da un
NOT realizza la funzione nota come \Index{NAND} (= NOT$\cdot$AND). La
tabella delle verit\`a di un NAND \`e quella data
nella~\ref{logici_tab_13}

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} della
funzione \Index{NAND}.}  \protect\label{logici_tab_13}
\end{center}
\end{table}


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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/nand_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{NAND}.}  \protect\label{nand_symbol}
\end{figure}


Un OR seguito da un NOT realizza la funzione nota come \Index{NOR} (=
NOT$\cdot$OR), la cui tabella delle verit\`a \`e
la~\ref{logici_tab_14}

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} della
funzione \Index{NOR}.}  \protect\label{logici_tab_14}
\end{center}
\end{table}


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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/nor_symbol,width=6.0 cm,
height=3.5 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{NOR}.}  \protect\label{nor_symbol}
\end{figure}


La funzione ``OR esclusivo'', indicata con \Index{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 \Index{simbolo del circuito}
che implementa la funzione XOR \`e mostrato in
figura~\ref{xor_symbol}:

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/xor_symbol,width=6.0 cm,
height=3 cm}}\end{center}
\caption{Simbolo del circuito elettronico che implementa la funzione
\Index{XOR}.}  \protect\label{xor_symbol}
\end{figure}

Il simbolo per l'\Index{XOR} \`e il $\oplus$.

Sono disponibili in commercio integrati che effettuano le
\Index{operazioni elementari} descritte: AND, OR, NOT, NAND, XOR
etc. I relativi \Index{chip} sono distinti da sigle che variano a
seconda della casa produttrice e che specificano caratteristiche
diverse del relativo dispositivo. Esiste tuttavia una convenzione in
base alla quale le ultime due cifre numeriche nella sigla indicano il
tipo di funzione eseguita dall'integrato. Ad esempio, la sigla
\Index{SN74LS00} indica un chip che esegue la funzione NAND a 2
ingressi. Le cifre numeriche che indicano la funzione \Index{NAND}
sono le ultime due (00). Pi\`u in particolare si tratta di quattro
porte NAND realizzate sul medesimo chip (\emph{QUAD} 2 input NAND
gate). Analogamente, il codice 02 indica una porta NOR etc. Alcuni
altri chip standard disponibili in commercio sono elencati nella
tabella~\ref{logici_chips}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| l | l |}
\hline Dispositivo & Funzione \\ \hline 00 & Quad 2 input \Index{NAND}
\\ 02 & Quad 2 input \Index{NOR} \\ 04 & Hex (6 in un chip)
\Index{NOT} \\ 08 & Quad 2 input \Index{AND} \\ 10 & Triple 3 input
NAND \\ 20 & Dual 4 input NAND \\ 27 & Triple 2 input NOR \\ 30 & 8
input NAND \\ 32 & Quad 2 input \Index{OR} \\ 86 & Quad exclusive OR
\\ 135 & Quad exclusive OR/NOR \\ 136 & Quad exclusive OR \\ \hline
\end{tabular}
\caption{Convenzione per l'identificazione delle \Index{funzioni
  logiche} implementate dai \Index{chip} disponibili in commercio.}
  \protect\label{logici_chips}
\end{center}
\end{table}

\subsection{Caratteristiche delle porte logiche}

Le descrizioni delle porte logiche che abbiamo dato nella sezione
precedente sono alquanto idealizzate ed \`e necessario a questo punto
fornire alcune precisazioni.

Prendiamo ad esempio il caso di una porta NOT. Se l'ingresso alla
porta vale 0, l'uscita vale 1. Nel caso particolare in cui la porta
sia di tipo TTL\footnote{TTL sta per Transistor-Transistor Logic.},
con livelli di tensione di 0~$V$ e +5~$V$, quando l'ingresso \`e a
0~$V$, l'uscita sar\`a vicina a +5~$V$, viceversa, quando l'ingresso
sar\`a vicino a +5~$V$, l'uscita sar\`a prossima a 0~$V$. L'andamento
realmente osservato sar\`a, qualitativamente, quello mostrato in
figura~\ref{ritardi}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/ritardi,width=10.0 cm,
height=6 cm}}\end{center}
\caption{Segnali di input ed output di una porta logica NOT, con
  relativi tempi di ritardo e propagazione.}  
\protect\label{ritardi}
\end{figure}


La transizione dell'ingresso da 0~$V$ a +5~$V$ non \`e istantanea, ma
avviene con un andamento caratterizzato da un ``\Index{tempo di
salita}''. Analogamente, il segnale non torner\`a istantaneamente a 0~$V$,
ma lo far\`a con un andamento caratterizzato da un certo
``\Index{tempo di discesa}''. L'uscita avr\`a un andamento analogo
(rovesciato) ma le transizioni che la caratterizzano avverranno con un
certo ritardo. Si definisce \Index{ritardo di propagazione}
\index{tempo di propagazione} (propagation delay) il tempo che
intercorre tra l'istante in cui l'ingresso passa per un valore di
tensione pari al $50\%$ del suo valore massimo ed il corrispondente  
istante in cui l'uscita passa per un valore di tensione pari al $50\%$
del suo valore massimo.  

Come si vede dalla figura, abbiamo in realt\`a due diversi tempi di
propagazione: il primo di questi caratterizza la transizione
dell'ingresso dal valore basso ($L$) a quello alto ($H$). Questo
ritardo \`e noto con $tp_{HL}$. L'altro tempo di propagazione,
relativo al passaggio dell'ingresso dal valore alto a quello basso,
\`e indicato con $tp_{LH}$. Il primo di questi ritardi di propagazione
vale tipicamente 20~$ns$, il secondo 15~$ns$, per un invertitore
standard TTL.

Analoghi ritardi di propagazione caratterizzano tutte le porte logiche
esaminate, nonch\'e i circuiti logici che discuteremo in seguito. Per
ciascun integrato la casa produttrice fornisce i valori tipici di tali
ritardi.

Una discussione dettagliata di questi aspetti, come pure delle
variazioni che i livelli di tensione considerati $High$ e $Low$
possono subire e delle relative tolleranze, sar\`a fatta nel secondo
volume.


\section{Algebra di Boole}
\subsection{\index{identit\`a booleane}Identit\`a Booleane}

A partire da due o pi\`u variabili logiche A, B, C etc., \`e possibile
costruire \Index{espressioni logiche} di varia complessit\`a. Tali
espressioni possono essere semplificate\index{funzioni logiche!
semplificazione di} facendo uso delle regole dell'\Index{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). Il procedimento \`e mostrato nella tabella~\ref{logici_tab_15}.

\begin{table}[htb!]
\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}
\caption{Dimostrazione della regola (14) dell'\Index{algebra di
Boole}.}  \protect\label{logici_tab_15}
\end{center}
\end{table}




Notiamo che se A = 1 in \Index{logica positiva}, allora A = 0 in
logica negativa\index{logica negativa}.  Consideriamo ora la tabellina
dell'AND (in logica positiva) (tabella~\ref{logici_tab_16}).


\begin{table}[htb!]
\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}
\caption{Verifica dell'uguaglianza tra un AND in logica positiva ed un
  OR in logica negativa.}  \protect\label{logici_tab_16}
\end{center}
\end{table}




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'\Index{OR}
delle prime due.  Possiamo allora dire che: ``un \Index{AND} in
\Index{logica positiva} diviene un OR in logica negativa\index{logica
negativa}''. Questo risultato \`e anche conseguenza delle leggi di De
Morgan, che esamineremo tra poco.


Esaminiamo ora la tabella delle verit\`a (tabella~\ref{logici_tab_17})
della funzione XOR ($Y\:=\:A\oplus B$).

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c c | c |}
\hline $A$ & $B$ & $Y \:=\: A \oplus B$ \\ \hline 0 & 0 & 0 \\ 0 & 1 &
1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline
\end{tabular}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} della
funzione \Index{XOR}.}  \protect\label{logici_tab_17}
\end{center}
\end{table}

La tabella ci permette di scrivere diverse espressioni della funzione
\Index{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 \oplus B \:=\: \overline{A} \cdot B + A \cdot \overline{B}
  \label{eq:xor_prima}
\end{equation}

Una seconda espressione dell'\Index{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 \oplus B \:=\:(A+B)\cdot (\overline{A \cdot B})
  \label{eq:xor_seconda}
\end{equation}

Una terza espressione si pu\`o ottenere notando che l'\Index{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 \oplus B \:=\:(A+B) \cdot (\overline{A} + \overline{B})
  \label{eq:xor_terza}
\end{equation}

Infine notiamo che il complemento dell'\Index{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 \oplus B} \:=\: \overline{A} \cdot \overline{B} + A \cdot
B
\]

cio\`e:

\begin{equation}
4) \: A \oplus 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
\Index{XOR} \`e indicata nelle
figure~\ref{xor_prima},~\ref{xor_seconda},~\ref{xor_terza}
ed~\ref{xor_quarta}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/xor_prima,width=13.0 cm,
height=7 cm}}\end{center}
\caption{Primo metodo per l'implementazione della funzione \Index{XOR}.}
\protect\label{xor_prima}
\end{figure}







\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/xor_seconda,width=12.0 cm,
height=6 cm}}\end{center}
\caption{Secondo metodo per l'implementazione della funzione \Index{XOR}.}
\protect\label{xor_seconda}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/xor_terza,width=12.0 cm,
height=6 cm}}\end{center}
\caption{Terzo metodo per l'implementazione della funzione \Index{XOR}.}
\protect\label{xor_terza}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/xor_quarta,width=12.0 cm,
height=6 cm}}\end{center}
\caption{Quarto metodo per l'implementazione della funzione \Index{XOR}.}
\protect\label{xor_quarta}
\end{figure}



\section{\Index{Leggi di De Morgan}}

L'equivalenza delle quattro diverse implementazioni della funzione
\Index{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 \Index{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\index{funzioni logiche!
semplificazione di} 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 \Index{XOR}.  Partiamo ad esempio
dall'espressione~\ref{eq:xor_prima}:
\[
A \oplus 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'\Index{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'\Index{XOR}. E' cos\`{\i} dimostrata
l'equivalenza delle quattro forme.

Facendo uso dell'\Index{algebra di Boole} e delle leggi di De Morgan
\`e possibile semplificare \Index{proposizioni logiche} complesse.  E'
inoltre possibile ottenere delle realizzazioni concrete di
\Index{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 \Index{NAND}.  Consideriamo infatti un
\Index{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}, che
usa solo porte \Index{NAND}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/or_da_nand,width=8.0 cm,
height=4 cm}}\end{center}
\caption{Implementazione della funzione \Index{OR} facendo uso solo
  delle porte \Index{NAND}.}  \protect\label{or_da_nand}
\end{figure}


\section{\index{funzioni logiche! forme standard di}Forme standard di funzioni logiche}



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

Esistono due diverse forme standard per le funzioni logiche. Esse sono
rispettivamente la \emph{\Index{somma di prodotti}} ed il
\emph{\Index{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 \Index{prodotto di somme}.

Si dice che una \Index{somma di prodotti} \`e in \Index{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
(tabella~\ref{logici_tab_18}).

\begin{table}[htb!]
\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}
\caption{Somma di prodotti\index{somma di prodotti} in \Index{forma
estesa} delle variabili $X$, $Y$ e $Z$.}
\protect\label{logici_tab_18}
\end{center}
\end{table}


Dalla tabella di vede subito che:

\[
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
``\Index{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 \Index{prodotto di somme} \`e:

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

Ciascuno dei termini del prodotto \`e un ``\Index{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{\Index{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 \Index{forma estesa}.

\section{Mappe di \Index{Karnaugh}\index{mappe di Karnaugh}}

Nel progettare un circuito che implementi una certa funzione logica,
si parte dalla definizione della funzione, analizzando tutte le
possibili combinazioni delle variabili logiche d'ingresso in
corrispondenza alle quali essa assume il livello logico 1. Questo \`e
certamente vero quando la funzione \`e espressa tramite i
\emph{\Index{minterm}}, cio\`e come \Index{somma di prodotti}. Se la
funzione \`e espressa come un \Index{prodotto di somme}, cio\`e
tramite i \emph{\Index{maxterm}}, \`e sempre possibile trasformarla in
una somma di prodotti.

\`E alternativamente possibile sviluppare un formalismo analogo a
quello che ora discuteremo, per funzioni espresse in termine dei
\Index{maxterm}. Per dettagli si consulti la
referenza~\cite{taub-schilling}.

Si ottiene in generale una struttura contenente combinazioni di
\Index{AND}, \Index{OR}, \Index{NAND} etc.. Non \`e per\`o detto che
la struttura cos\`{\i} progettata sia la pi\`u economica possibile.
Altre strutture equivalenti possono esser trovate che minimizzano il
numero dei componenti necessari e quindi il costo, la compattezza e la
velocit\`a.

Vediamo ci\`o con un semplice esempio. Si debba realizzare un circuito
con due ingressi $A$ e $B$ ed un'uscita $Y$, definita dalla tabella
delle verit\`a~\ref{tab_karnaugh_1}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c c | c |}
\hline $A$ & $B$ & $Y$\\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\
1 & 1 & 0 \\ \hline
\end{tabular}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per un
  circuito a due ingressi ed un'uscita definita da $Y=\overline{A}
  \cdot \overline{B} + A \cdot \overline{B}$.}
  \protect\label{tab_karnaugh_1}
\end{center}
\end{table}

Questa \`e esprimibile nella forma:
\[
Y=\overline{A} \cdot \overline{B} + A \cdot \overline{B}
\]
che richiederebbe due porte AND, due NOT ed un OR. Tale relazione
pu\`o per\`o esser facilmente semplificata:
\[
Y=(\overline{A} + A) \cdot \overline{B} = \overline{B}
\]

Vediamo cos\`{\i} che \`e sufficiente far uso di una singola porta NOT.

Il caso esaminato \`e di estrema semplicit\`a e siamo quindi riusciti
a minimizzare l'espressione facendo uso soltanto delle leggi
dell'algebra di Boole. In casi pi\`u complessi (ma purch\'e il numero
di variabili sia limitato) si pu\`o far ricorso ad un metodo grafico,
noto come ``metodo delle mappe di \Index{Karnaugh}\index{mappe di
Karnaugh}''.

Una mappa di Karnaugh (o semplicemente mappa K) \`e una matrice di
celle che fornisce una rappresentazione visiva immediata della tabella
delle verit\`a.

Iniziamo con l'illustrare tale metodo esaminando la sua applicazione
al semplice problema che abbiamo appena visto. Riportiamo su di un
asse i possibili valori della variabile $A$ e su di un asse ortogonale
quelli della variabile $B$, come mostrato in figura~\ref{karnaugh1}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh1,width=6.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per la
tabella delle verit\`a~\ref{tab_karnaugh_1}.}
\protect\label{karnaugh1}
\end{figure}

Le celle contenenti ``1'' o ``0'' corrispondono alle combinazioni di
valori di $A$ e $B$ in corrispondenza alle quali la $Y$ \`e
rispettivamente vera (1) o falsa (0). Nella pratica si indicano solo
gli ``1'', lasciando vuote le celle corrispondenti agli ``0''.

La prima delle regole relative alle mappe
K\index{Karnaugh}\index{mappe di Karnaugh} ci dice che due caselle
adiacenti (lungo una riga o una colonna) contenenti ``1'' possono
esser accorpate, come indicato in figura, essendo evidente che la $Y$
vale ``1'' in corrispondenza al valore della variabile d'ingresso che
\`e uguale nelle due caselle. Nel nostro esempio ci\`o significa che
la $Y$ \`e \emph{vera} se $B$ \`e $falso$:
\[
Y=\overline{B}
\]

In generale, nel caso di una funzione di due sole variabili, due
caselle adiacenti in cui \`e presente un ``1'' danno luogo ad un
termine che contiene la singola variabile che \`e \emph{vera} o
\emph{falsa} nelle due caselle. Se viceversa \`e presente un ``1''
isolato, questo dar\`a luogo ad un termine contenente entrambe le
variabili.

Esaminiamo ancora un esempio, dato dall'espressione:
\[
Y=\overline{A} \cdot \overline{B} + A \cdot \overline{B} + A \cdot B
\]

Questa \`e descritta dalla mappa K\index{Karnaugh}\index{mappe di
Karnaugh} di figura~\ref{karnaugh2}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh2,width=6.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per
  l'espressione $Y=\overline{A} \cdot \overline{B} + A \cdot
  \overline{B} + A \cdot B$.}  \protect\label{karnaugh2}
\end{figure}

Qui abbiamo due coppie di ``1'' adiacenti, come indicato dalle curve
in figura. La prima di queste (prima riga) corrisponde al termine
$\overline{B}$, la seconda (seconda colonna) ad $A$. Avremo quindi:
\[
Y=A + \overline{B}
\]
come d'altronde \`e facile verificare facendo uso dell'algebra di
Boole.

Esaminiamo ora un caso in cui le variabili d'ingresso siano tre: $A$,
$B$, $C$:

\[
Y=\aoverbar \cdot \boverbar \cdot \coverbar + \aoverbar \cdot
\boverbar \cdot C + \aoverbar \cdot B \cdot C + \aoverbar \cdot B
\cdot \coverbar + A \cdot B \cdot \coverbar
\]
  
In tal caso conviene riportare su di un asse (ad esempio quello
orizzontale) tutte le possibili combinazioni delle prime due variabili
e sull'altro i possibili valori della terza. Nel riportare le prime
due si proceder\`a in ordine tale che le due variabili, nel passare da
una cella a quella adiacente, cambino una alla volta, cio\`e la
sequenza sar\`a: 00,01,11,10. La matrice K\index{Karnaugh}\index{mappe
di Karnaugh} che cos\`{\i} si ottiene \`e del tipo mostrato in
figura~\ref{karnaugh3}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh3,width=14.0 cm,
height=5 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per un
caso con tre variabili in ingresso.}  \protect\label{karnaugh3}
\end{figure}

\`E importante notare che la mappa\index{Karnaugh}\index{mappe di
Karnaugh} v\`a sempre immaginata \emph{estesa}, nel senso che, nel
caso specifico, occorre immaginare che esistano, a destra ed a
sinistra di quella data, due mappe identiche ad essa, i cui elementi
contenenti ``1'' possono esser combinati con identici elementi
adiacenti presenti nella mappa originale.  Le estensioni sono indicate
in figura dalle matrici tratteggiate (dove non abbiamo riportato in
modo esplicito gli ``1'' presenti, che vanno sottintesi).

Nell'esempio di figura vediamo un raggruppamento di quattro celle
(indicato dalla linea tratteggiata) che corrisponde, come si pu\`o
facilmente verificare, a:
\[
Y = \aoverbar
\]
Abbiamo inoltre un ulteriore raggruppamento di due caselle, mostrato in
figura, corrispondente a:
\[
Y=B \cdot \coverbar
\]
Si ha in definitiva:
\[
Y = \aoverbar + B \cdot \coverbar
\]

Esaminiamo ora le regole generali per la \index{funzioni logiche!
semplificazione di}semplificazione di \Index{funzioni logiche} di tre
variabili, come quella appena esaminata:

\begin{enumerate}
\item Quattro celle adiacenti (in linea o quadrato) si combinano in
modo da fornire una funzione di una sola variabile.
\item Due celle adiacenti si combinano in modo da fornire una funzione
di due variabili.
\item Una cella isolata d\`a luogo ad un termine funzione di tutte e
tre le variabili.
\end{enumerate}

Esaminiamo ancora un esempio di sistema dipendente da tre
variabili. Si voglia realizzare un circuito che soddisfi la tabella
delle verit\`a~\ref{tab_karnaugh_2}:

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c c c| c | c | c |}
\hline $A$ & $B$ & $C$ & $Y_1$ & $Y_2$ & $Y_3$ \\ \hline 0 & 0 & 0 & 1
& 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1
& 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1
& 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \hline
\end{tabular}
\caption{Esempio di tabella delle verit\`a con tre variabili in
ingresso.}  \protect\label{tab_karnaugh_2}
\end{center}
\end{table}

In figura~\ref{karnaugh4} mostriamo le mappe
K\index{Karnaugh}\index{mappe di Karnaugh} per ciascuna delle funzioni
$Y_1$, $Y_2$, $Y_3$.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh4,width=10.0 cm,
height=13 cm}}\end{center}
\caption{Mappe di \Index{Karnaugh}\index{mappe di Karnaugh} per
  ciascuno degli esempi della tabella~\ref{tab_karnaugh_2}.}
  \protect\label{karnaugh4}
\end{figure}

Vediamo facilmente, applicando le regole date che:
\[
Y_1=\aoverbar \cdot \boverbar + A \cdot \coverbar
\]
\[
Y_2=\coverbar + \aoverbar
\]
\[
Y_3=\boverbar + \aoverbar
\]

dove nel caso di $Y_3$ si vede che la prima e l'ultima colonna si
combinano a dare il termine $\boverbar$.

Passiamo infine al caso di una mappa a quattro variabili, come quella
di figura~\ref{karnaugh5}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh5,width=6.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per un
sistema a quattro variabili in ingresso.}  \protect\label{karnaugh5}
\end{figure}

Anche in questo caso occorre ricordare che la mappa \`e da immaginare
\emph{estesa}, questa volta in tutte le direzioni, come schematizzato
in figura~\ref{karnaugh6}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh6,width=12.0 cm,
height=12 cm}}\end{center}
\caption{Schematizzazione \emph{estesa} della mappa di
  \Index{Karnaugh}\index{mappe di Karnaugh} di
  figura~\ref{karnaugh5}.}  \protect\label{karnaugh6}
\end{figure}

Le regole da ricordare, come si pu\`o facilmente verificare, sono
adesso:
\begin{enumerate}
\item Un rettangolo di otto celle adiacenti d\`a luogo ad un termine
in una singola variabile;
\item Quattro celle adiacenti (in linea o quadrato) danno luogo ad un
termine in due variabili;
\item Due celle adiacenti danno luogo ad un termine contenente tre
variabili;
\item Una cella singola corrisponde ad un termine contenente tutte e
quattro le variabili.
\end{enumerate}

Esaminiamo ad esempio l'espressione:
\[
Y=\aoverbar \cdot \boverbar \cdot \coverbar \cdot \doverbar + A \cdot
B \cdot \coverbar \cdot \doverbar + A \cdot B \cdot \coverbar \cdot D
+ \aoverbar \cdot \boverbar \cdot \coverbar \cdot D +
\]
\[
+ \aoverbar \cdot B \cdot \coverbar \cdot \doverbar + \aoverbar \cdot
B \cdot C \cdot \doverbar + A \cdot B \cdot C \cdot \doverbar + A
\cdot B \cdot C \cdot D
\]

La corrispondente mappa K \`e mostrata in figura~\ref{karnaugh7}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh7,width=7.0 cm,
height=7 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per
l'esempio considerato, a quattro variabili.}
\protect\label{karnaugh7}
\end{figure}

Che, come si pu\`o facilmente verificare, fornisce l'espressione
semplificata:

\[
Y= \aoverbar \cdot \boverbar \cdot \coverbar + B \cdot \doverbar + A
\cdot B
\]

Consideriamo ancora un esempio. Facendo uso di tre motori si vuol
comandare la rotazione e lo spostamento della punta di un trapano nel
piano x-y, nel modo seguente:
\begin{description}
\item[(a)]{Un deviatore P comanda l'accensione (P=1) e lo spegnimento
(P=0) del motore principale MP, che provoca la rotazione della punta}
\item[(b)]{Due deviatori di direzione Dx e Dy comandano l'accensione
(Dx=1 o Dy=1) e lo spegnimento (Dx=0 o Dy=0) di due motori Mx ed My
che fanno spostare la punta nelle due direzioni x ed y}
\item[(c)]{Un comando I seleziona i due versi per il movimento (I=0 in
avanti; I=1 indietro)}
\item[(d)]{Un pulsante di allarme A, se premuto, spegne tutti i motori
(A=1, altrimenti A=0)}
\item[(e)]{Il motore My deve essere spento (My=0) se il motore
principale MP \`e acceso}
\end{description}

Come si vede, abbiamo cinque variabili (P, Dx, Dy, I ed A). Per
ridurci a sole quattro variabili, eliminiamo la considerazione del
caso ovvio in cui il pulsante d'allarme \`e stato premuto, per cui
tutti i motori sono spenti. Ammettiamo quindi che sia sempre A=0.

La tabella delle verit\`a \`e allora quella mostrata nella
tabella~\ref{tab_karnaugh_3}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{|| c c c c | c | c | c ||}
\hline \hline $P$ & $Dx$ & $Dy$ & $I$ & $MP$ & $Mx$ & $My$ \\ \hline 0
& 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0
& 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0
\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1
& 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0
& 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1
& 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1
& 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \hline \hline
\end{tabular}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} relativa
  all'esempio per il controllo della punta di un trapano.}
  \protect\label{tab_karnaugh_3}
\end{center}
\end{table}

Le mappe K per MP, Mx, My sono mostrate nelle
figure~\ref{karnaugh8},~\ref{karnaugh9},~\ref{karnaugh10}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh8,width=7.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per la
variabile MP.}  \protect\label{karnaugh8}
\end{figure}


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh9,width=7.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per la
variabile Mx.}  \protect\label{karnaugh9}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh10,width=7.0 cm,
height=6 cm}}\end{center}
\caption{Mappa di \Index{Karnaugh}\index{mappe di Karnaugh} per la
variabile My.}  \protect\label{karnaugh10}
\end{figure}

Da queste otteniamo:
\[
MP=P
\]
\[
Mx=Dx
\]
\[
My=\overline{P} \cdot Dy
\]

Un'ultimo esempio che analizzeremo \`e quello del confronto di due
numeri $A$ e $B$, ciascuno di due bit. L'output $Y$ del circuito da
realizzare dovr\`a essere alto se $A > B$, basso nel caso opposto.  La
tabella delle verit\`a che riassume le situazioni in cui \`e $A > B$,
\`e la~\ref{tab_karnaugh_4}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c c | c c | c |}
\hline $ A$ & & $ B$ & & $Y$ \\ \hline 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0
& 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1
\\ 1 & 1 & 1 & 0 & 1 \\ \hline
\end{tabular}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per i
  casi in cui il numero A (a due bit) \`e maggiore del numero B (a due
  bit).}  \protect\label{tab_karnaugh_4}
\end{center}
\end{table}

La corrispondente mappa K \`e mostrata in figura~\ref{karnaugh11}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh11,width=5.0 cm,
height=7 cm}}\end{center}
\caption{Mappa di Karnaugh relativa alla tabella delle
  verit\`a~\ref{tab_karnaugh_4}.}  \protect\label{karnaugh11}
\end{figure}

Da questa, come \`e facile verificare, si ottiene:

\[
Y=\overline{B}_1 \cdot A_1 + A_0 \cdot \overline{B}_0 \cdot
\overline{B}_1 + A_0 \cdot A_1 \cdot \overline{B}_0
\]

Il circuito che implementa tale funzione \`e mostrato in
figura~\ref{karnaugh_schematics}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/karnaugh_schematics,width=8.0 cm,
height=5 cm}}\end{center}
\caption{Circuito relativo alla tabella di
verit\`a~\ref{tab_karnaugh_4}.}  \protect\label{karnaugh_schematics}
\end{figure}

\section{Operazioni aritmetiche\index{operazioni aritmetiche}}

Vediamo ora come, facendo uso di circuiti elementari che implementano
\Index{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 tabella delle
verit\`a mostrata nella~\ref{logici_tab_19}.

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per la
somma ed il riporto di due bit.}  \protect\label{logici_tab_19}
\end{center}
\end{table}


Vediamo facilmente che $\Sigma$ coincide con $a \oplus 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 $\underline{a}$ e del corrispondente di
$\underline{b}$ potr\`a essere ottenuta 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 ``\Index{semisommatore}'' o ``\Index{Half
Adder}''~(HA).  In termini circuitali avremo quanto mostrato in
figura~\ref{half_adder}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/half_adder,width=7.0 cm,
height=5 cm}}\end{center}
\caption{Circuito ``\Index{semisommatore}'' o ``\Index{Half Adder}''
(HA).}  \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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/full_adder,width=10.0 cm,
height=5 cm}}\end{center}
\caption{Circuito che effettua la somma dei due bit $a_i$, $b_i$ e del
  riporto dalla somma dei due bit precedenti.}
  \protect\label{full_adder}
\end{figure}

E' facile verificare che il riporto finale $R_i$ \`e l'OR del riporto
$R_{i}'$ dal primo \Index{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 nella tabella~\ref{logici_tab_20}.

\begin{table}[htb!]
\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}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per la
  somma di due bit e del riporto della somma dei due bit precedenti.}
  \protect\label{logici_tab_20}
\end{center}
\end{table}



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}\:=\:a_i b_i +
R_{i-1}\cdot(a_i + b_i)
\]

La somma $\Sigma_i$ \`e esprimibile come:
\[
R_{i-1}\cdot (a_i b_i + \abari \bbari) + \rbar \cdot (a_i \bbari +
\abari b_i)
\]

Il termine nella prima parentesi \`e: $\overline{a_i \oplus b_i}$,
quello nella seconda \`e: $a_i \oplus b_i$. Ne segue:
\[
\Sigma_i=R_{i-1} \cdot \overline{a_i \oplus b_i} + \rbar \cdot (a_i
\oplus b_i)
\]

\`E evidente allora che questa altro non \`e che:
\[
\Sigma_i = R_{i-1} \oplus (a_i \oplus b_i)
\]
La somma ed il riporto sono allora entrambi ottenibili dal circuito di
figura~\ref{bin_adder}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/bin_adder,width=10.0 cm,
height=7 cm}}\end{center}
\caption{Circuito che effettua la somma dei due bit $a_i$, $b_i$ e del
  riporto dalla somma dei due bit precedenti.}
  \protect\label{bin_adder}
\end{figure}

Vediamo in tal modo che $\Sigma_i$ ed $R_i$ possono facilmente essere
realizzati utilizzando \Index{porte logiche} elementari.


\section{Sottrazione binaria\index{sottrazione binaria}}

Ammettiamo di voler sottrarre un \Index{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 \Index{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
\emph{\index{complemento! a due}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 \Index{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$ ha il
quinto bit sempre uguale ad 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$.

Esaminiamo la tabella~\ref{logici_tab_21}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r | r |}
\hline $B$ & 1100 \\ $\overline{A}$ & 0110 \\ \hline $B \Sigma
\overline{A}$ & 10010 \\ & 1 \\ \hline $B \Sigma \overline{A} \Sigma
1$ & 10011\\ \hline
\end{tabular}
\caption{Sottrazione binaria\index{sottrazione binaria} nel caso in
cui $B > A$.}  \protect\label{logici_tab_21}
\end{center}
\end{table}
        
        
Lasciamo ora cadere il bit pi\`u significativo (il quinto) ed
otteniamo:

\[
B \Sigma \overline{A} \Sigma 1 - 10000 \:=\: 10011\,-\,10000\;=\; 0011
\:=\:3
\]

Come abbiamo gi\`a notato, se B \`e maggiore di A, la somma di B e di
$\overline{A}$ ha 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 somma $B \Sigma \overline{A}$ non cambier\`a
nulla.

Vediamolo nel caso concreto in cui:


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

Avremo la situazione mostrata nella tabella~\ref{logici_tab_22}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r | r  c |}
\hline $B$ & 1001 & \\ $\overline{A}$ & 0011 & \\ $B \Sigma
\overline{A}$ & 01100 & il 5 bit \`e zero \\ & 0 & \\ \hline $B \Sigma
\overline{A} \Sigma 0$ & 01100 & \\ \hline
\end{tabular}
\caption{Sottrazione binaria\index{sottrazione binaria} nel caso in
cui $A > B$.}  \protect\label{logici_tab_22}
\end{center}
\end{table}

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

da interpretare come \Index{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 (b5) della somma
  \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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sottrattore,width=8.0 cm,
height=6 cm}}\end{center}
\caption{Circuito che effettua la \Index{sottrazione binaria} tra A e
B.}  \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\index{numero negativo}}

Come visto, per ottenere il complemento ad 1 di un \Index{numero
binario}, si complementano tutti i suoi bits. Una regola altrettanto
semplice pu\`o essere adoperata per ottenere il \index{complemento! a
due}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$
(tabella~\ref{logici_tab_23}).

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r  c |}
\hline 10110100 & + \\ 01001100 & = \\ \hline 100000000 & \\ \hline
\end{tabular}
\caption{Verifica della regola per la costruzione del
  \index{complemento! a due}complemento a 2 di un numero.}
  \protect\label{logici_tab_23}
\end{center}
\end{table}



Cos\`{\i}, se il primo bit sulla destra \`e un 1, il \index{complemento!
a due}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 \Index{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 ``\index{complemento! a
due}complemento a due'' e quella del ``\index{complemento! ad
uno}complemento ad uno''. Esaminiamo la prima di queste, 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 \Index{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
ricavata come mostrato nella tabella~\ref{logici_tab_24}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r  c  r  r  r |}
\hline & & binario & decimale & \\ \hline A & = & 00110 & 6 & + \\ B &
 = & 00101 & 5 & = \\ $A \Sigma B$ & = & 01011 & 11 & \\ \hline
\end{tabular}
\caption{Somma dei due numeri A e B.}  \protect\label{logici_tab_24}
\end{center}
\end{table}
 
 
Calcoliamo ora la differenza $A \Delta B$
(tabella~\ref{logici_tab_25}).

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r  c  r  r  r |}
\hline & & binario & decimale & \\ \hline A & = & 00110 & 6 & + \\
 $-B=C_2(B)$ & = & 11011 & -5 & = \\ $A \Sigma C_2(B)$ & = & 100001 &
 1 & \\ \hline
\end{tabular}
\caption{Differenza dei due numeri: $A \Delta B$.}
\protect\label{logici_tab_25}
\end{center}
\end{table}



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
uguale a 1.  Calcoliamo ora $B \Delta A$
(tabella~\ref{logici_tab_26}).

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| r  c  r  r  r |}
\hline & & binario & decimale & \\ \hline B & = & 00101 & 5 & + \\
 $-A=C_2(A)$ & = & 11010 & -6 & = \\ $B \Sigma C_2(A)$ & = & 11111 &
 -1 & \\ \hline
\end{tabular}
\caption{Differenza dei due numeri: $B \Delta A$.}
\protect\label{logici_tab_26}
\end{center}
\end{table}

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 elementari.


\section{\index{comparatori digitali}Comparatori digitali}

Ammettiamo di voler comparare due semplici bit A e B. Le possibili
configurazioni sono quelle mostrate nella tabella~\ref{logici_tab_27}:

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c  c  |  c  c |}
\hline 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$ \\
 \hline
\end{tabular}
\caption{Comparazione tra due bit.}  \protect\label{logici_tab_27}
\end{center}
\end{table}


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, facendo uso delle leggi di De Morgan:


\[
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 la situazione mostrata in
tabella~\ref{logici_tab_28}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c  | c |}
\hline $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$ \\
\hline
\end{tabular}
\caption{Comparazione tra due bit.}  \protect\label{logici_tab_28}
\end{center}
\end{table}


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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/comparatore,width=8.0 cm,
height=4 cm}}\end{center}
\caption{Circuito che implementa la comparazione tra due bit.}
\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
\]

La prima di queste uguaglianze \`e espressa da $E_3=1$, la seconda da
$E_2=1$, etc.. Avremo quindi l'uguaglianza richiesta se \`e:

\[
E_3 \cdot E_2 \cdot E_1 \cdot E_0\:=\:1
\]

A sar\`a invece 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 nell'ultima espressione A
con B.


\section{Parit\`a\index{parit\`a} di un \Index{numero binario}}

Dato un numero binario, si definisce \emph{\Index{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 \Index{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, 2 bit in una
medesima parola (e.g. di 8 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
\Index{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 \index{generatore del bit di
parit\`a}genera il bit di parit\`a per una parola di 4 bit, ammettendo
una parit\`a pari.

Se avessimo solo due bit, la \Index{parit\`a} sarebbe quella mostrata
nella tabella~\ref{logici_tab_29}.

\begin{table}[htb!]
\begin{center}
\begin{tabular}{| c   c  | r | c |}
\hline A & B & \Index{parit\`a} del numero & bit da aggiungere \\
\hline 0 & 0 & pari & 0 \\ 0 & 1 & dispari & 1 \\ 1 & 0 & dispari & 1
\\ 1 & 1 & pari & 0 \\ \hline
\end{tabular}
\caption{Bit di \Index{parit\`a} per una parola a due bit.}
\protect\label{logici_tab_29}
\end{center}
\end{table}

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
\Index{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 \Index{XOR}, come mostrato in figura~\ref{parity_bit}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/parity_bit,width=8.0 cm,
height=5 cm}}\end{center}
\caption{Circuito\index{generatore del bit di parit\`a} che implementa
la parit\`a di una parola a quattro bit.}  \protect\label{parity_bit}
\end{figure}

\section{\index{codificatore}Codificatori/\index{decodificatore}Decodificatori}

Un \Index{codificatore} \`e un circuito che converte in un codice
l'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 \Index{numero
binario} (codice) quando si pigia un determinato tasto.  Un
\Index{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 \Index{BCD-Decimale}.  \index{Binary Coded Decimal}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 (tabella~\ref{logici_tab_30}).

\begin{table}[htb!]
\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}
\caption{Codifica per il sistema ``\Index{Binary Coded Decimal}''.}
\protect\label{logici_tab_30}
\end{center}
\end{table}

Un \Index{decodificatore} \Index{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 \index{Binary Coded Decimal}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}[htb!]
        \begin{center}
                \begin{tabular}{| l | r | r | r | r | }
                \hline 371 = & 0011 & 0111 & 0001 \\ \hline & 3 & 7 &
1 \\ \hline
                \end{tabular}
        \end{center}
\caption{Rappresentazione nel codice \index{Binary Coded Decimal}BCD
di un numero decimale a pi\`u cifre.}  \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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/decod_4_10,width=8.0 cm,
height=8 cm}}\end{center}
\caption{Circuito che implementa un \emph{\index{decodificatore! da 4
a 10 linee}decodificatore da 4 a 10 linee}.}
\protect\label{decod_4_10}
\end{figure}

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


Esaminiamo ora la struttura di un \Index{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}[htb!]
        \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{Tabella delle verit\`a\index{tabella delle verit\`a} che
  realizza la funzione di codifica per generare un carattere (codice)
  BCD.}  \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 \Index{matrice di diodi}, come mostrato in
figura~\ref{matrice}.


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/matrice,width=13.0 cm,
height=11 cm}}\end{center}
\caption{Circuito che implementa la codifica di
tabella~\ref{logici_seconda}.}  \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 ``\Index{codificatore! con priorit\`a}'' elimina tale problema. In
un codificatore di 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
mostrato nella tabella~\ref{logici_terza}.

\begin{table}[htb!]
        \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{Tabella di codifica con ``priorit\`a''.}
\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 \Index{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/\index{demultiplexer}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 \Index{multiplexer}. Il multiplexer ha N ingressi ``dati'',
un ingresso ``\Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/multiplexer,width=10.0 cm,
height=10 cm}}\end{center}
\caption{\index{multiplexer}Multiplexer con quattro ingressi.}
\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 abilitata 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
(\Index{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 \Index{multiplexer} pu\`o esser utilizzato per effettuare la
\Index{conversione parallelo-seriale}. Ammettiamo infatti che ad un
circuito arrivino dei bit, costituenti una ``parola'', su n'=n+1 linee
parallele e che esso debba poi convogliare tali informazioni su di
un'unica linea, come mostrato in figura~\ref{multiplex_out}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/multiplex_out,width=10.0 cm,
height=6 cm}}\end{center}
\caption{\index{multiplexer}Multiplexer che effettua la
  \Index{conversione parallelo-seriale}.}
  \protect\label{multiplex_out}
\end{figure}


Si potr\`a usare un \Index{multiplexer} che riceve sulle linee $x_0$,
$x_1$,...,$x_n$ i bit da convogliare in uscita; gli \index{ingresso di
controllo}ingressi di controllo (o di \Index{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'=n+1 dovr\`a esser legato
al numero di ingressi di controllo N'=N+1 dalla relazione $n' =
2^{N'}-1$. Cos\`{\i}, per $n' = 4$ avremo $N' = 2$, per $n' = 8$, $N' =
3$ etc.

Un \Index{demultiplexer} convoglia invece su una di n'=n+1 possibili
linee di uscita i segnali che riceve su di una linea d'ingresso,
facendo uso dell'informazione (indirizzo) che riceve su N'=N+1 linee
di controllo.  E' utile far presente che qualsiasi
\Index{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 \Index{multiplexer} possa essere
adoperato per implementare una funzione logica.  Consideriamo il
multiplexer di figura~\ref{funzione_logica}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/funzione_logica,width=9.0 cm,
height=6 cm}}\end{center}
\caption{\index{multiplexer}Multiplexer a quattro ingressi.}
\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 \Index{Strobe}. La
tabella delle verit\`a \`e quella di tabella~\ref{logici_quarta}.

\begin{table}[htb!]
        \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{Tabella delle verit\`a\index{tabella delle verit\`a} per il
  \Index{multiplexer} di figura~\ref{funzione_logica}.}
  \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 \Index{multiplexer} indicato,
assegnando agli ingressi $x_0, x_1, x_2, x_3$ i valori trovati, per
implementare la funzione logica indicata.


I \Index{multiplexer}/\Index{demultiplexer} svolgono un ruolo di
fondamentale importanza nei processori 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
\Index{74LS151}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74ls151,width=8.0 cm,
height=8 cm}}\end{center}
\caption{\index{multiplexer}Multiplexer di tipo commerciale
\Index{74LS151}.}  \protect\label{74ls151}
\end{figure}


Gli ingressi sono indicati con $I_0 - I_7$ . L'indirizzo, cio\`e il
\Index{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{\Index{Enable}}.  Se si vuole inibire
il trasferimento occorrer\`a portare tale ingresso al livello alto.

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74ls138,width=8.0 cm,
height=8 cm}}\end{center}
\caption{\index{demultiplexer}Demultiplexer di tipo commerciale
\Index{74LS138}.}  \protect\label{74ls138}
\end{figure}


\section{Registri\index{registro} e memorie\index{memoria}: i \Index{Flip-Flop}}

I circuiti logici esaminati finora, costituiti da porte AND, NOT,
NAND, etc., o da combinazioni pi\`u o meno complesse di queste, sono
comunemente noti come ``circuiti logici combinatori''. Essi
stabiliscono una corrispondenza univoca tra i segnali applicati agli
ingressi e quelli presenti in uscita.

Esiste una variet\`a di circuiti che funzionano invece in \index{modo
  sequenziale}modo \emph{sequenziale}, vale a dire che lo stato logico
  che parte del circuito acquista ad un dato istante \`e funzione
  dello stato presente in altre parti del circuito negli istanti
  precedenti.  Ci\`o consente, eventualmente in associazione a
  circuiti combinatori, di realizzare sequenze complesse di funzioni,
  che si verificano con una cadenza predeterminata da opportuni
  segnali di \emph{clock}.

L'elemento che \`e alla base di tutti i circuiti sequenziali \`e il
``\Index{Flip-Flop}'' (FF), il cui uso pi\`u ovvio \`e nella
realizzazione di memorie\index{memoria! per computer} per computer,
dove esso pu\`o immagazzinare l'informazione elementare costituita dal
\emph{bit}.

Perch\'e infatti un numero possa essere elaborato da un
\Index{processore}, esso deve essere preventivamente immagazzinato in
un insieme di celle elementari o registri\index{registro}.  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{\Index{bistabile}}, o Flip-Flop (FF). Un
FF \`e un circuito con due ingressi (detti ingressi di \Index{Set} e
di \Index{Reset}) e due uscite, convenzionalmente chiamate Q e
$\overline{Q}$, una complementare dell'altra.

Un bistabile \`e anche noto come ``binario'' o ``\Index{Latch}''. Esso
pu\`o, come vedremo, esser realizzato a partire da \Index{porte
logiche} (ad esempio porte \Index{NAND}) o acquistato in forma
integrata. Pi\`u FF possono poi esser collegati insieme per realizzare
registri, contatori, etc..

\subsection{\index{Flip-Flop! di tipo RS}Flip-Flop di tipo RS}

Esiste un'ampia variet\`a di FF.  Quello cui abbiamo accennato \`e il
flip-flop di tipo RS. Un FF RS pu\`o assumere due stati: nello stato
di \emph{\Index{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 tabella delle verit\`a mostrata
nella~\ref{logici_quinta}.

\begin{table}[htb!]
        \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{Tabella delle verit\`a\index{tabella delle verit\`a} di un
\index{Flip-Flop! di tipo RS}flip-flop di tipo RS.}
\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 \index{Flip-Flop! di tipo RS}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 (figura~\ref{r_s_flip_flop}).

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/r_s_flip_flop,width=7.0 cm,
height=4 cm}}\end{center}
\caption{Struttura interna di un \index{Flip-Flop! di tipo RS}FF di
tipo RS.}  \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 alcuno stato proibito.

Si pu\`o ottenere un circuito con una tabella delle verit\`a
sostanzialmente uguale a quell 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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/pr_clear_f_f,width=8.0 cm,
height=7 cm}}\end{center}
\caption{Struttura interna di un \index{Flip-Flop! di tipo RS}FF di
tipo RS.}  \protect\label{pr_clear_f_f}
\end{figure}

Ammettiamo che gli ingressi di \emph{\Index{Preset}} e di
\emph{\Index{Clear}} siano entrambi alti.  Se l'\emph{\Index{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~\ref{logici_sesta}, dove vediamo che ora lo stato ``proibito''
\`e quello che corrisponde ad R=S=1.

\begin{table}[htb!]
        \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{Tabella delle verit\`a\index{tabella delle verit\`a} di un
\index{Flip-Flop! di tipo RS}FF di tipo RS.}
\protect\label{logici_sesta}
\end{table}




Se l'ingresso di \Index{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 \Index{Preset} e \Index{Clear} entrambi alti, le due porte poste a
valle risponderanno solo ai valori dei rimanenti ingressi.

L'ingresso che abbiamo chiamato ``\Index{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
\Index{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 \Index{Preset} e \Index{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'\Index{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$.  Ponendo
successivamente Preset=Clear=1 il FF potr\`a nuovamente rispondere ai
livelli presenti sugli ingressi R, S.

\subsection{\index{Flip-Flop! di tipo D}Flip-Flop di tipo D}\label{dtypeflipflop}

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/d_type_f_f,width=5.5 cm,
height=4 cm}}\end{center}
\caption{Struttura di un FF di tipo D.\index{Flip-Flop! di tipo D}}
\protect\label{d_type_f_f}
\end{figure}




La presenza dell'invertitore fa s\`{\i} che se S=1, sia 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{philips_74ls74_reference}.  La
configurazione dei terminali (\emph{pins}) \`e mostrata in
figura~\ref{philips_74ls74_pins}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/philips_74ls74_reference,width=10.0 cm,
height=18 cm}}\end{center}
\caption{Specifiche di un \index{Flip-Flop! di tipo D}FF di tipo D
commerciale (74AHC74).}  \protect\label{philips_74ls74_reference}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/philips_74ls74_pins,width=10.0 cm,
height=11 cm}}\end{center}
\caption{Configurazione dei ``pins'' e diagramma logico per un FF di
  tipo D commerciale (74AHC74).}  
\protect\label{philips_74ls74_pins}
\end{figure}


Questo (74AHC74) \`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 \Index{Preset} e \Index{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 \Index{applicazioni}
``militari'', in un range di temperature compreso tra $-55^oC$ e
$+125^oC$. Le due lettere intermedie (LS nel nostro caso) stanno poi ad
indicare la classe o tipo del chip. LS sta per ``Low power
Schottky''. Altre sigle sono: S=Schottky; AS=Advanced Schottky;
HC=High-Speed CMOS; HCU=HCMOS unbuffered; HCT=HCMOS con inputs TTL. I
tipi 74-HC, 74HCU, 74HCT lavorano nel range di temperature che va da
$-40^oC$ a $+85^oC$.}

Notiamo che in questo FF la transizione avviene nell'istante in cui il
clock diviene alto. Una volta che tale livello del clock sia stato
raggiunto, le uscite non risentono pi\`u di eventuali variazioni
dell'ingresso D. Tale tipo di variazione dello stato di un FF \`e noto
con il nome di ``\Index{edge-triggering}''. Moltissimi dei FF
disponibili in commercio sono di questo tipo. Gli ingressi asincroni
($\overline{S}_D$ e $\overline{R}_D$) sono \emph{\Index{active low}},
cio\`e hanno un effetto solo se vengono tenuti bassi.  Durante il
normale funzionamento del FF con trasferimento del dato (D) effettuato
dal clock, essi vanno tenuti \emph{alti}.

In un normale \index{Flip-Flop! di tipo D}FF di tipo D, l'output segue
l'input in corrispondenza al \Index{fronte di salita}
dell'\Index{impulso di clock}. Esiste un tipo particolare di D~FF,
noto come \Index{Latch}, in cui l'output diviene una copia
dell'ingresso quando il clock \`e alto, e conserva tale valore quando
il clock diviene basso. In altre parole, la differenza tra i due tipi
\`e che un normale D~FF\index{Flip-Flop! di tipo Edge-Triggered} \`e
``\Index{edge-triggered}'' mentre un \Index{Latch} \`e ``level
triggered''. Data la similarit\`a con il D, si conserva la dizione
``registro di tipo D'' per il normale D e si usa quella di
``transparent \Index{Latch}'' per il nuovo registro (in cui l'output
``si aggancia'' all'ingresso per l'intera durata dell'impulso di
clock).

Un esempio di FF di tipo D \`e il '\Index{574}, mentre un
\Index{Latch} \`e il '\Index{573}. Questi, come mostrato in
figura~\ref{d_ff_latch} sono dei \Index{chip} con 8 FF in ciascuna
unit\`a (sono cio\`e di tipo ``octal''). Il '574 ha un ingresso di
clock indicato con \emph{cp} e con il simbolo $>$ che denota un
trigger sul \Index{fronte di salita} del clock. Il '573 ha l'analogo
ingresso indicato con LE (\Index{Latch} Enable).  Entrambi hanno un
ulteriore ingresso di abilitazione/disabilitazione, indicato con
$OEBAR$.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/d_ff_latch,width=7.0 cm,
height=6 cm}}\end{center}
\caption{FF commerciali di tipo D, il '\Index{574}, e \Index{Latch},
il '\Index{573}.}  \protect\label{d_ff_latch}
\end{figure}

Un tipo di latch adoperato nei microprocessori\index{microprocessore}
\`e il 74125\index{74LS125}, mostrato in figura~\ref{74LS125}. Questo
\`e un buffer quadruplo ``\Index{tri-state}''. Il 
singolo \Index{latch} tri-state contenuto in questo chip \`e mostrato in
figura~\ref{74LS125_detail} insieme alla sua tabella delle verit\`a.
Vediamo che, se l'\Index{ingresso di controllo} C \`e basso, l'uscita segue
l'ingresso dati; se invece esso \`e alto, l'uscita \`e in uno stato di
``\Index{alta impedenza}''. In tale stato il livello di tensione di
un'eventuale linea cui tale uscita sia collegata, dipende solo dagli
eventuali altri elementi cui la linea \`e collegata. In altre parole,
nello stato di ``alta impedenza'' l'uscita del latch \`e
sostanzialmente ``isolata'' (la sua impedenza verso massa \`e
teoricamente infinita). Il nome dato a tale latch (tri-state) deriva
appunto dal fatto che l'uscita pu\`o acquistare, oltre ai valori 0 ed
1, quello di ``alta impedenza''.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74LS125,width=4.0 cm,
height=6 cm}}\end{center}
\caption{Latch tri-state \Index{74LS125} adoperato nei microprocessori.}
\protect\label{74LS125}
\end{figure}


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74LS125_detail,width=7.0 cm,
height=6 cm}}\end{center}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} del
  latch tri-state 74LS125.}
\protect\label{74LS125_detail}
\end{figure}



\subsection{\index{Flip-Flop! di tipo JK}Flip-Flop di tipo JK}

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 \Index{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, a sua volta pilotata
dall'uscita complementare (la superiore da $\overline{Q}$, quella
inferiore da $Q$), come mostrato in figura~\ref{j_k_simple_ff}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/j_k_simple_ff.eps,width=8.0 cm,
height=6 cm}}\end{center}
\caption{Struttura di un FF di tipo JK.\index{Flip-Flop! di tipo JK}}
\protect\label{j_k_simple_ff}
\end{figure}



\newcommand{\qbar}{\overline{Q}} Cominciamo con l'esaminare il caso,
particolarmente semplice, in cui sia J che K siano uguali a zero.  \`E
evidente dalla figura~\ref{j_k_simple_ff} che con J=0 \`e
\emph{disabilitata} la porta AND superiore, mentre con K=0 \`e
\emph{disabilitata} quella inferiore. Entrambe le porte, e quindi gli
ingressi R ed S del FF, saranno uguali a zero. Con ci\`o lo stato
delle uscite del FF non cambier\`a all'arrivo dell'\Index{impulso di
clock}.

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 delle uscite 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$

Vediamo cio\`e che ponendo J=1 e K=0 noi \emph{settiamo} il FF.

Se fosse stato 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}$.

Vediamo cio\`e che ponendo J=0 e K=1 noi \emph{resettiamo} il FF.

Esaminiamo infine lo stato J=K=1. In tal caso, se era $Q_{n-1}=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 \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/jk_ff_out,width=10.0 cm,
height=6 cm}}\end{center}
\caption{Segnali di clock, ingresso ed uscita di un \index{Flip-Flop!
di tipo JK}FF di tipo JK.}  \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\index{Flip-Flop! di tipo
JK} con J=K=1 effettua quella che vien chiamata la funzione
``\index{toggle}TOGGLE'' ed \`e adoperato come divisore di
frequenza. Ponendone due o pi\`u in cascata si pu\`o realizzare una
\Index{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 {\index{Flip-Flop! di tipo Master-Slave}FF di tipo Master-Slave}
\item{\index{Flip-Flop! di tipo Edge-Triggered}FF di tipo
\index{edge-triggered}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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/master_slave_f_f,width=10.0 cm,
height=5 cm}}\end{center}
\caption{Struttura di un \index{Flip-Flop! di tipo Master-Slave JK}FF
JK di tipo Master-Slave.}  \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 \Index{edge-triggered} non rispondono al livello del
clock, ma al fronte di discesa di questo. In questo caso gli ingressi
non hanno effetto sulle uscite se non in corrispondenza della
transizione negativa dell'\Index{impulso di clock}.

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/master_slave_ff_out,width=6.0 cm,
height=5 cm}}\end{center}
\caption{Segnali di clock, ingresso ed uscita di un FF JK di tipo
  Master-Slave.\index{Flip-Flop! di tipo Master-Slave JK}}
  \protect\label{master_slave_ff_out}
\end{figure}



Come esempi di \index{Flip-Flop! di tipo Master-Slave JK}FF
Master-Slave JK possiamo menzionare il modello \Index{SN74LS76} della
\Index{Motorola}.  Questo \Index{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 \Index{Set} e \Index{Reset} asincroni, denotati con
$\overline{S}$ ed $\overline{C}$ nella tabella di figura.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls76,width=10.0 cm,
height=15 cm}}\end{center}
\caption{Specifiche tecniche del modello \Index{SN74LS76} di FF JK
Master-Slave.  \index{Flip-Flop! di tipo Master-Slave JK}}
\protect\label{sn74ls76}
\end{figure}

La tabella~\ref{logici_shift_list} mostra un elenco di alcuni dei
pi\`u comuni tipi di FF disponibili in commercio. Per ci\`o che
rigurda i simboli che vengono normalmente adoperati dai produttori
nelle specifiche dei FF, dobbiamo ricordare che un FF con transizione
sul \Index{fronte di salita} del clock \`e comunemente specificato con
un $>$ sull'ingresso del clock.  Un FF con transizione sul
\Index{fronte di discesa} del clock \`e indicato con un'inversione
``$\circ$'' prima del medesimo simbolo. Vedasi ad esempio la
figura~\ref{d_jk_ff_symbols}. Quello a sinistra \`e un FF di tipo D
con transizione sul fronte di salita del clock, quello a destra \`e un
JK con transizione sul fronte di discesa.


\begin{table}[htb!]
\begin{center}
\begin{tabular}{| l | l |}
\hline Dispositivo & Funzione \\ \hline 70 & JK con ingressi di
\Index{Preset} e \Index{Clear} \\ 71 & RS con ingressi di Preset e
Clear \\ 72 & JK con ingressi di Preset e Clear \\ 73 & Dual JK \\ 74
& Dual tipo D \index{Flip-Flop! di tipo D}\\ 76 & Dual JK \\ 105 & JK
con clock e con ingressi di Preset e Clear \\ 175 & Quad tipo D \\ 273
& Octal tipo D \\ 276 & Quad JK \\ 375 & Octal tipo D \\ \hline
\end{tabular}
\caption{Flip-flop disponibili in commercio.}
\protect\label{logici_shift_list}
\end{center}
\end{table}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/d_jk_ff_symbols,width=8.0 cm,
height=5 cm}}\end{center}
\caption{\emph{Sinistra:} simbolo di un FF di tipo D con transizione
  sul \Index{fronte di salita} del clock; \emph{destra:} simbolo di un
  FF JK con transizione sul \Index{fronte di discesa}.}
  \protect\label{d_jk_ff_symbols}
\end{figure}

\newpage


\section{Shift-Registers\index{shift-register}}

Gli \emph{shift-registers} (SR) (o registri a
scorrimento\index{registro! a scorrimento}), sono essenzialmente delle
catene di FF, opportunamente collegati tra loro ed utilizzati per
memorizzare una ``stringa'' di bits\index{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 \Index{impulso di clock} (in genere sul \Index{fronte
di salita} di questo).  Uno SR costituito da FF di tipo D \`e mostrato
in figura~\ref{d_shift_reg}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/d_shift_reg,width=10.0 cm,
height=5 cm}}\end{center}
\caption{\emph{Shift-register\index{shift-register}} costituito da
quattro FF di tipo D.}  \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 \Index{Preset} e \Index{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 \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/d_shift_reg_out,width=9.5 cm,
height=10 cm}}\end{center}
\caption{Segnali di clock, ingresso ed uscita per uno
  \emph{\Index{shift-register}} costituito da quattro FF di tipo D.}
  \protect\label{d_shift_reg_out}
\end{figure}


Vediamo che, dopo l'applicazione del quarto \Index{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 \Index{registro}, che
ha un ingresso seriale ed un'uscita parallela, \`e chiamato
``Serial-In-Parallel-Out'' (o SIPO).

\subsection{Universal Shift-Register}

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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls195,width=14.0 cm,
height=10 cm}}\end{center}
\caption{``Universal Shift Register\index{shift-register}''
SN74LS195A.}  \protect\label{sn74ls195}
\end{figure}



Tale dispositivo \`e utilizzabile in un'ampia classe di
\Index{applicazioni}, che vanno da operazioni di ``\Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls195_truth,width=14.0 cm,
height=8 cm}}\end{center}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per lo
``Universal Shift Register\index{shift-register}'' di figura
~\ref{sn74ls195}.}  \protect\label{sn74ls195_truth}
\end{figure}

I dati sono immagazzinati nei quattro FF mostrati in figura.  Se
l'ingresso indicato con $\overline{PE}$ (\Index{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 \Index{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 \Index{impulso di clock} (pi\`u esattamente, sul
\Index{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 terza nel primo blocco disabilitata).  Se esaminiamo la prima porta
AND associata al secondo blocco, vediamo che essa ha come ingresso
$Q_0$. Il collegamento della porta OR sottostante \`e tale che il
\Index{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 prima porta AND del terzo blocco far\`a si che l'uscita $Q_2$
divenga uguale a $Q_0$ con l'arrivo del terzo \Index{impulso di
clock}. Infine, il quarto impulso di Clock far\`a si che $Q_3$ divenga
uguale a $Q_0$. Lo \Index{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
\Index{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 (quarta e 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 \Index{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 ``\index{toggle}TOGGLE''
caratteristica di un JK. Ci\`o \`e indicato come ``Shift\index{shift},
Toggle First Stage'' nella quarta riga della tabella.

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\index{shift}, Retain First
Stage'' nella quinta colonna della tabella.

Un registro a scorrimento\index{registro! a scorrimento} simile per
molti aspetti al precedente, ma con la possibilit\`a di shift sia a
destra che a sinistra, \`e il \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls194,width=14.0 cm,
height=9 cm}}\end{center}
\caption{``Universal Shift Register\index{shift-register}''
SN74LS194A\index{SN74LS194}.}  \protect\label{sn74ls194}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls194_truth,width=14.0 cm,
height=7 cm}}\end{center}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per lo
``Universal Shift Register\index{shift-register}'' di figura
~\ref{sn74ls194}.}  \protect\label{sn74ls194_truth}
\end{figure}

\subsection{First-In, First-Out SR}

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/fifo_sr,width=14.0 cm,
height=7 cm}}\end{center}
\caption{Shift Register\index{shift-register} di tipo ``First-In,
First-Out'' (\index{First-IN First-OUT}FIFO).}
\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 \Index{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
\Index{Preset} e \Index{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
\Index{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, che \`e il FF appena ``liberato'' con l'applicazione
di $Ck_{out}$, mentre il dato presente all'uscita di FF3 viene
trasferito all'uscita di FF2.  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, 0100,
\cdots$) se il clock in arrivo \`e $Ck_{in}$; decrescente (cio\`e, $
\cdots 1000, 0100, 0010, 0001, 0000$) se il clock in ingresso \`e
$Ck_{out}$. Ci\`o \`e mostrato schematicamente in
figura~\ref{up_down_cntr}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/up_down_cntr,width=8.0 cm,
height=5 cm}}\end{center}
\caption{``Up-down'' counter.}  \protect\label{up_down_cntr}
\end{figure}


\section{Applicazioni degli Shift-Registers\index{shift-register} e dei \Index{Flip-Flop}}

\subsection{\index{applicazioni}Applicazioni degli shift-registers}

Come accennato, questi possono essere adoperati per memorizzare
stringhe di bits, quali ad esempio \Index{byte}s o parole di 16/32
bits.  Essi hanno tuttavia molte altre applicazioni, non meno
importanti.  Notiamo intanto che se facciamo scorrere verso destra
(right-\Index{shift}) il contenuto di un \Index{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 \index{conversione
serie-parallelo}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 serie 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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/scocca_scintilla,width=6.0 cm,
height=3.5 cm}}\end{center}
\caption{Shift-Register in cui l'uscita dell'ultimo FF \`e collegata
  al \Index{Set} del primo FF per generare sequenze predeterminate di
  impulsi.}  \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~\ref{logici_settima}, dopo il numero di
impulsi di clock indicato.

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c | c | c | c | c |}
                \hline 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 & 0 & 0 & 1 & 0 \\ 4 & 0 & 0 & 0 & 1 \\ \hline
                \end{tabular}
        \end{center}
\caption{Valori delle quattro uscite dello SR di
  figura~\ref{scocca_scintilla} dopo l'applicazione di vari impulsi di
  clock.}  \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~\ref{logici_ottava}. Un sistema analogo \`e quello, che
esamineremo in una delle prossime sezioni, che consente la generazione
di \emph{\index{sequenza pseudocasuale}sequenze pseudocasuali di
bits}, di lunghezza arbitraria.

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c | c | c | c | c |}
                \hline 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 \\ \hline
                \end{tabular}
        \end{center}
\caption{Sequenza predeterminata di bits che si pu\`o ottenere con lo
  SR di figura~\ref{scocca_scintilla}.}  \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 \Index{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 ``\Index{contatore ad anello}''
(\Index{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 ``\Index{Johnson Counter}'' o ``\Index{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 \Index{ring-counter}).

\subsection{\index{applicazioni}Applicazioni dei FF}

\subsubsection{\index{contatore asincrono}Contatori asincroni}

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. Questi sono del tipo
\emph{\Index{edge-triggered}}, con transizione sul \Index{fronte di
discesa} del segnale di clock (come evidenziato dal
cerchietto-inversione sull'ingresso di clock).

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/ff_counter,width=12.0 cm,
height=5.5 cm}}\end{center}
\caption{\emph{Ripple counter} realizzato con quattro FF JK.}
\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 \index{toggle}TOGGLE, cio\`e cambieranno stato ad ogni
impulso presente sul rispettivo ingresso di clock. Pi\`u precisamente,
la transizione delle uscite avverr\`a sul \Index{fronte di discesa}
dell'\Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/ff_counter_out,width=8.0 cm,
height=5 cm}}\end{center}
\caption{Segnale di clock ed uscite per il contatore di
figura~\ref{ff_counter}.}  \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 \Index{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, conti in entrambi i versi.  E' sufficiente
collegare l'uscita di un FF al clock del successivo nel modo
illustrato in figura~\ref{conta_indietro}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/conta_indietro,width=9.0 cm,
height=5 cm}}\end{center}
\caption{Parte di una catena di FF che pu\`o contare in entrambi i
versi.}  \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 (\index{Binary Coded Decimal}BCD).


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/contatore_base_10,width=13.0 cm,
height=5 cm}}\end{center}
\caption{``Contatore decimale\index{contatore decimale}'' o Binary Coded Decimal
(\index{Binary Coded Decimal}BCD).}  \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 \Index{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
\Index{impulso di clock}.

\section{\index{contatore sincrono}Contatori sincroni}

I contatori fin qui esaminati sono noti come ``\index{contatore
asincrono}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 \Index{tempo di propagazione}
(propagation delay) di un FF \`e relativamente lungo ($\tau \approx
20-30\,ns$ nel caso del '74). Se tutti i FF sono nello stato logico 1,
tale tempo \`e massimo, poich\'e il successivo impulso 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 ``\Index{contatore sincrono}''. Un esempio \`e
mostrato in figura~\ref{contatore_sincrono}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/contatore_sincrono,width=13.0 cm,
height=6 cm}}\end{center}
\caption{Schema di un \Index{contatore sincrono}.}
\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~\ref{logici_nona}) 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}[htb!]
        \begin{center}
                \begin{tabular}{| c  c  c  c  c |}
                \hline 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
\\ \hline
                \end{tabular}
        \end{center}
\caption{Tabella dei valori assunti dalle uscite del contatore
  sincrono di figura~\ref{contatore_sincrono} dopo ogni \Index{impulso
  di clock}.}  \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 del primo (A) vale 1
\item[c] il terzo FF deve commutare in corrispondenza ad un impulso di
clock se sia l'uscita del primo (A) che quella del secondo (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.

Esaminiamo il \Index{tempo di propagazione} in ciascuna delle
transizioni indicate nella tabella, ignorando in un primo tempo, per
semplicit\`a, i ritardi dovuti alle porte AND. Nel passaggio dalla
prima alla seconda riga il tempo di propagazione \`e solo quello
($\tau$) relativo alla commutazione del primo FF (gli altri non
cambiano stato). Analogamente, nella successiva transizione (passaggio
dalla seconda all terza riga della tabella) il tempo di commutazione
\`e solo quello relativo al secondo FF. Nella terza transizione
cambiano stato i primi tre FF (A,B,C).  Tuttavia il ritardo \`e ancora
$\tau$, poich\'e i tre cambiamenti di stato avvengono
contemporaneamente.  Proseguendo l'analisi \`e facile vedere che il
ritardo complessivo nel conteggio fino a 15 \`e pari a
$15\,\tau$. Questo risultato \`e da confrontare con quello che si
incontra nel caso di un \Index{contatore asincrono}, in cui il ritardo
\`e $15\,\tau$ nella sola transizione (1~1~1~1~$\rightarrow$~0~0~0~0).

In realt\`a, nel caso del \Index{contatore sincrono} occorre tener
conto del ritardo aggiuntivo ($\tau'$)dovuto alle porte AND, che \`e
dell'ordine di (10-20 ns) per ciascun FF che alimenta una porta AND.
Esaminiamo in dettaglio l'effetto del ritardo delle porte
AND. Consideriamo ad esempio la transizione associata all'arrivo del
quarto impulso di clock (quinta riga della
tabella~\ref{logici_nona}). Il passaggio dallo stato C=0 a C=1 pu\`o
aver luogo solo dopo che:
\begin{itemize}
\item[(i)] {A sia diventato 1 (ritardo $\tau$)}
\item[(ii)]{ B sia diventato 1 (lo era gi\`a)}
\item[(iii)]{ l'uscita della porta AND sia passata da 0 ad 1 (ritardo
$\tau'$)}
\end{itemize}

Vediamo cos\`{\i} che la transizione di C da 0 ad 1 pu\`o \emph{aver
inizio} solo dopo un tempo $\tau + \tau'$. Se gli impulsi di clock si
susseguono con un periodo $T < \tau + \tau'$, il sistema non potr\`a
funzionare nel modo desiderato.


Un \Index{contatore sincrono} binario a 4 bit, di uso abbastanza
generale \`e il \Index{74LS191}. Esso pu\`o eseguire il conteggio in
avanti o indietro a seconda del \Index{valore logico} presente
sull'\Index{ingresso di controllo} ``up/down''.  Il \Index{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 \Index{conteggio decimale} (BCD).


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74ls190,width=11.0 cm,
height=8 cm}}\end{center}
\caption{Struttura interna del \Index{contatore sincrono} binario a 4
bit \Index{74LS190}.}  \protect\label{74ls190}
\end{figure}

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls190,width=11.0 cm,
height=15 cm}}\end{center}
\caption{Specifiche tecniche del \Index{contatore sincrono} binario a
4 bit \Index{74LS190}.}  \protect\label{sn74ls190}
\end{figure}

E' possibile, collegando due o pi\`u \index{contatore in
serie}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 \Index{contatore modulo
1000}.


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/contatore_mod_1000,width=11.0 cm,
height=5 cm}}\end{center}
\caption{\Index{contatore modulo 1000} realizzato collegando in serie
  pi\`u contatori.}  \protect\label{contatore_mod_1000}
\end{figure}

Vediamo che l'ingresso \Index{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 (\Index{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
``\Index{overflow}'', cio\`e quando i quattro FF abbiano superato il
massimo conteggio consentito (9 nel caso del 74LS190).  Tale livello
basso, collegato all'\Index{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{Generazione di sequenze pseudocasuali\index{sequenza pseudocasuale}}

Un'applicazione interessante dei registri, che ha incontrato una
larghissima diffusione, \`e quella che consente la generazione di
sequenze di bits, anche molto lunghe, con distribuzione
\emph{casuale}. Per comprendere il concetto, pensiamo al problema
statistico associato al lancio di una moneta. Il risultato del lancio
pu\`o essere ``testa'' o ``croce'', con uguali probabilit\`a.

La statistica ci insegna che in una serie di lanci successivi, la
probabilit\`a che il $k^{mo}$ lancio dia un determinato risultato non
dipende dai risultati ottenuti nei lanci precedenti. Se associamo al
risultato ``croce'' il numero binario ``0'' ed al risultato ``testa''
il numero binario ``1'', in una successione di (k-1) lanci potremmo ad
esempio aver trovato la seguente sequenza:
\[
0\;0\;1\;0\;1\;1\;1\;0\;1\;0\;1\;0\;0\;1\;1\;....\;0
\]

Questa \`e una sequenza che pu\`o esser considerata casuale. Il fatto
di ``conoscerla'' non ci sar\`a di alcun aiuto nel tentare di
prevedere il risultato del $k^{mo}$ lancio.

Facendo uso di uno \Index{shift-register} con clock, \`e possibile
realizzare delle sequenze \emph{approssimativamente} casuali. Si
tratterebbe di sequenze realmente casuali se la lunghezza del
\Index{registro} fosse infinitamente lunga. Con un registro di
lunghezza finita k, il numero di possibili combinazioni distinte di
``1'' e ``0'' \`a pari a $2^k$ (cio\`e al numero di
\emph{disposizioni} di due elementi su k posizioni). Ci\`o fa si che
dopo un numero di bits pari a $2^k$, la sequenza cominci a ripetersi
in modo identico a se stessa; la sequenza ha una \emph{periodicit\`a}.
Un'osservatore che abbia la pazienza di osservarla tutta sar\`a in
grado di dire quali valori si succederanno a partire dal bit
$2^k+1$. Per un registro reale, diciamo di 33~bit, con un clock a
1~MHz, la sequenza inizia a ripetersi dopo circa 2 ore.

Vediamo con un esempio pratico come una tale sequenza possa esser
realizzata nel caso di un registro costituito da quattro FF. La
figura~\ref{sequenza_casuale_lunga_4} illustra il circuito.


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sequenza_casuale_lunga_4,width=10.0 cm,
height=5 cm}}\end{center}
\caption{Generatore di sequenze pseudocasuali\index{sequenza
pseudocasuale} realizzato con quattro FF.}
\protect\label{sequenza_casuale_lunga_4}
\end{figure}

Come si vede, \`e sufficiente prendere l'XOR di due dei FF di cui il
registro \`e costituito ed inviarlo in ingresso al primo. Possiamo
facilmente verificare che, ammettendo di partire dalla configurazione
1~1~1~1 delle uscite, i valori successivamente acquistati dai quattro
FF sono quelli mostrati nella
tabella~\ref{sequenza_casuale_lunga_4_tab}.


\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| l | l l l l |}
\hline clock & $FF_0$ & $FF_1$ & $FF_2$ & $FF_3$ \\ \hline - & 1 & 1 &
1 & 1 \\ $\uparrow$ & 0 & 1 & 1 & 1 \\ $\uparrow$ & 0 & 0 & 1 & 1 \\
$\uparrow$ & 0 & 0 & 0 & 1 \\ $\uparrow$ & 1 & 0 & 0 & 0 \\ $\uparrow$
& 0 & 1 & 0 & 0 \\ $\uparrow$ & 0 & 0 & 1 & 0 \\ $\uparrow$ & 1 & 0 &
0 & 1 \\ $\uparrow$ & 1 & 1 & 0 & 0 \\ $\uparrow$ & 0 & 1 & 1 & 0 \\
$\uparrow$ & 1 & 0 & 1 & 1 \\ $\uparrow$ & 0 & 1 & 0 & 1 \\ $\uparrow$
& 1 & 0 & 1 & 0 \\ $\uparrow$ & 1 & 1 & 0 & 1 \\ $\uparrow$ & 1 & 1 &
1 & 0 \\ $\uparrow$ & 1 & 1 & 1 & 1 \\ \hline
                \end{tabular}
\caption{Sequenza degli stati per un generatore \index{sequenza
pseudocasuale}di sequenze pseudocasuali a quattro bit.}
\protect\label{sequenza_casuale_lunga_4_tab}
        \end{center}

\end{table}
 
La sequenza dei valori assunti da uno qualsiasi dei FF, ad esempio da
$FF_0$, \`e pseudocasuale, nel senso appena detto. La sequenza dei
valori assunti da $FF_1$ differisce da quella di $FF_0$ solo per una
traslazione temporale (circolare). Quindi, dal punto di vista
statistico, essa \`e la medesima sequenza. Lo stesso dicasi per le
sequenze dei valori assunti da $FF_2$ e $FF_3$.

Si pu\`o dimostrare che, per un \Index{registro} di lunghezza 5, si
ottiene una sequenza pseudocasuale\index{sequenza pseudocasuale} di
lunghezza $2^5-1=31$ facendo uso come ingressi dell'XOR delle uscite
di $FF_2$ ed $FF_4$. Per registri di lunghezza maggiore, si dimostra
che si ottengono le sequenze pseudocasuali di lunghezza massima
($2^k-1$) utilizzando XOR a 2 o pi\`u ingressi, come mostrato nella
tabella~\ref{sequenze_casuali_ingressi_tab} (dove i registri sono
numerati a partire dallo 0).

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c | c | c |}
\hline k & lunghezza della sequenza $2^k-1$ & ingressi all'XOR \\
\hline 5 & 31 & 2,4 \\ 6 & 63 & 4,5 \\ 7 & 127 & 5,6 \\ 8 & 255 &
1,2,6,7 \\ 9 & 511 & 4,8 \\ 10 & 1023 & 6,9 \\ 11 & 2047 & 8,10 \\ 12
& 4095 & 1,9,10,11 \\ 13 & 8191 & 0,10,11,12 \\ 14 & 16383 &
1,11,12,13 \\ 15 & 32767 & 13,14 \\ 16 & 65535 & 3,12,14,15 \\ \hline
\end{tabular}
\caption{Generatori di sequenze pseudocasuali\index{sequenza
pseudocasuale}. La tabella fornisce, per tutti i registri di lunghezza
inferiore a 17, la massima lunghezza della sequenza e gli ingressi
all'XOR. Si noti che tali ingressi sono numerati a partire dallo
zero. Gli ingressi indicati non sono gli unici possibili: ad esempio,
nel caso di un registro di lunghezza 7, una sequenza di lunghezza
massima si ottiene anche adoperando come ingressi all'XOR le uscite 4
e 7.}  \protect\label{sequenze_casuali_ingressi_tab}
        \end{center}
\end{table}
 
\`E possibile generare sequenze pseudocasuali\index{sequenza
pseudocasuale} anche facendo uso, per gli ingressi degli XOR, di FF
diversi da quelli indicati. Non in tutti i casi tuttavia le sequenze
ottenute sono di lunghezza massima: esse possono avere delle
sottosequenze che si ripetono all'interno della sequenza.  Ulteriori
dettagli sono discussi nell'appendice a questo capitolo.


Notiamo anche che, se tutti i FF di cui il registro \`e costituito
assumessero il valore 0, lo stato successivo del sistema sarebbe
sempre il medesimo. \`E per questo motivo che la lunghezza della
sequenza \`e $2^k-1$ e non $2^k$: lo stato costituito di soli zeri non
\`e presente. Ne segue che se in un ciclo completo contiamo il numero
degli ``1'' e degli ``0'', il primo \`e sempre di una unit\`a maggiore
del secondo. Nel confronto con l'estrazione a sorte della monetina,
ci\`o equivarrebbe a dire che le probabilit\`a di ``testa'' o
``croce'' non sono esattamente uguali. La ``testa'' (0) \`e lievemente
pi\`u probabile della ``croce'' (0). Ovviamente la differenza \`e
tanto pi\`u piccola quanto maggiore la lunghezza della sequenza, e
quindi la lunghezza del registro. Ad esempio, un registro a 23 bit
darebbe 4194304 volte un risultato di ``1'' e 4194303 volte un
risultato di ``0''.

I generatori di sequenze pseudocasuali\index{sequenza pseudocasuale}
hanno numerosissime \Index{applicazioni}. Essi possono essere
adoperati come generatori di rumore, ma un uso ancora pi\`u importante
si ha nelle tecniche di protezione di dati da intrusioni. Una
opportuna \emph{chiave elettronica} fornita da un generatore di
sequenze prefissato, e noto solo a chi invia ed a chi riceve il
messaggio, pu\`o impedire ad altri di accedere all'informazione.

Una grandezza di notevole importanza nello studio delle sequenze
pseudocasuali (ma pi\`u in generale nello studio di processi
stocastici) \`e la \emph{\Index{funzione di autocorrelazione}}. Questa
\`e definita come:

\[
F(i) \:=\:\sum_{j=1}^{2^k-1} {Q(j) Q(j+i)}\;\;\;(i=0,2^k-1)
\]
dove Q(j) \`e il valore di uno qualsiasi dei FF dopo il $j^{mo}$
impulso di clock.

In altri termini, la \Index{funzione di autocorrelazione} \`e la somma
dei prodotti di ciascun bit della sequenza per il corrispondente della
medesima sequenza, traslata (circolarmente) di una quantit\`a i. I
valori di Q(j) sono 0 o 1. \`E per\`o pratica frequente, nel calcolare
la funzione di autocorrelazione per sequenze
pseudocasuali\index{sequenza pseudocasuale}, sottrarre
sistematicamente 0.5 e moltiplicare per 2, cio\`e:
\[
Q(j) = 1 \rightarrow 1
\]
\[
Q(j) = 0 \rightarrow -1
\]
Allora un generico prodotto varr\`a o -1 o +1. Per i=0 avremo che
tutti i prodotti valgono 1, per cui:
\[
F(0)=2^k-1
\]
mentre si dimostra che, per $i \ne 0$ si trova: $F(i)=-1$. La F(i) \`e
nuovamente uguale a $2^k-1$ per $i=2^k$, cio\`e se, nel calcolare i
prodotti, trasliamo la sequenza di una quantit\`a uguale al suo
periodo.

La \Index{funzione di autocorrelazione} pu\`o anche esser calcolata
facendo uso della ``forma d'onda'' del segnale all'uscita di uno dei
FF, ovvero dell'espressione analitica del segnale, anzich\'e dalla sua
rappresentazione ``discreta''. La funzione di autocorrelazione nel
caso continuo \`e data da:
\[
F(\tau)=\int_0^T Q(t) Q(t+\tau) d\tau
\]

dove T \`e la durata temporale (periodo) della sequenza.

\subsection{Generatori di sequenze casuali come sorgenti di
  rumore\index{sorgente di rumore}}

Se l'uscita di uno dei FF del \Index{registro} adoperato viene
trasformata in un segnale analogico compreso tra -a e +a Volts, si
ottiene un segnale la cui distribuzione in frequenza \`e
approssimativamente piatta, almeno fino ad una certa frequenza. Pi\`u
precisamente, la quantit\`a che interessa \`e la
\emph{\Index{densit\`a spettrale}}, cio\`e la potenza media per
unit\`a di intervallo di frequenza.

Si dimostra nello studio dei processi di rumore che la densit\`a
spettrale cos\`{\i} definita \`e legata alla \Index{funzione di
autocorrelazione} (nel caso continuo) attraverso il teorema di
\Index{Wiener-Khintchine}:

\[
S_v(f)=4 \int_0^{\infty} Q(t) Q(t+\tau) cos(\omega \tau) d\tau
\]
dove $S_v(f)$ \`e la \Index{densit\`a spettrale}, $Q(t)$ il segnale al
tempo t e $Q(t+\tau)$ quello al tempo $t+\tau$. Nel nostro caso la
$Q(t)$ \`e l'uscita del FF scelto, trasformata in modo da portarla
nell'intervallo (-a,a). Si dimostra che il risultato \`e una serie di
picchi molto stretti (funzioni $\delta$) che hanno inizio alla
frequenza $f_{clock}/n$ e si ripetono ad intervalli di $f_{clock}/n$,
dove $f_{clock}$ \`e la frequenza del clock inviato al registro ed n
la lunghezza della sequenza. Per n molto grande, i picchi saranno
molto vicini ed i nostri strumenti di misura effettueranno di fatto
una media su molti di questi picchi in strette zone di
frequenza. Vedremo cio\`e una curva praticamente continua, che
approssima l'inviluppo della distribuzione ``vera''. Si trova che la
forma di tale inviluppo \`e proporzionale a:

\[
\frac{\sin^2(\pi f/f_{clock})}{(\pi f/f_{clock})^2}
\]
Tale andamento \`e mostrato in
figura~\ref{densita_spettrale_pseudo_random_1}.

 

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/densita_spettrale_pseudo_random_1,width=10.0 cm,
height=7 cm}}\end{center}
\caption{\index{densit\`a spettrale}Densit\`a spettrale di un
generatore di sequenze casuali.}
\protect\label{densita_spettrale_pseudo_random_1}
\end{figure}

La distribuzione \`e tutt'altro che piatta se consideriamo l'intero
spettro di frequenze. Se per\`o ci limitiamo a considerare la parte di
bassa frequenza di questa distribuzione, diciamo $f < (0.1 \div 0.2)
\;f_{clock}$, la distribuzione \`e praticamente piatta, come si pu\`o
vedere nell'esempio di
figura~\ref{densita_spettrale_pseudo_random_2}. Il rumore \`e
praticamente \emph{bianco}. Per ottenere tale risultato sar\`a quindi
sufficiente far seguire al nostro generatore di rumore un opportuno
filtro passa-basso.

Sono disponibili in commercio integrati appositi, basati su questi
principi, che generano appunto del rumore bianco, nella zona di
frequenza che si preferisce.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/densita_spettrale_pseudo_random_2,width=10.0 cm,
height=7 cm}}\end{center}
\caption{\index{densit\`a spettrale}Densit\`a spettrale di un
  generatore di sequenze casuali a basse frequenze: $f < (0.1 \div
  0.2)\;f_{clock}$.}
  \protect\label{densita_spettrale_pseudo_random_2}
\end{figure}




\section{Alcune \Index{applicazioni} pratiche di
  registri\index{registro} 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 n 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 (\Index{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.

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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/misura_intervallo,width=9.0 cm,
height=5 cm}}\end{center}
\caption{Dispositivo per la misura dell'intervallo di tempo tra due
eventi.}  \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 \Index{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 la sequenza di impulsi di clock, di frequenza nota,
fornita dal contatore.

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\footnote{Un
``monostabile'' \`e un circuito che genera un impulso rettangolare di
altezza e durata prefissata, quando riceva in ingresso un impulso (di
forma arbitraria) che superi una soglia predeterminata}). 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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/j_k_misura_intervallo,width=9.0 cm,
height=5 cm}}\end{center}
\caption{Circuito che effettua la misura dell'intervallo di tempo tra
  due eventi nel caso in cui questi ultimi siano segnali prodotti dal
  medesimo dispositivo.}  \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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/j_k_conta_impulsi,width=9.0 cm,
height=5 cm}}\end{center}
\caption{Dispositivo che effettua una misura di frequenza.}
\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 abilitata 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 relativi ad applicazioni in esperimenti di
fisica, incontrano ampio utilizzo i contatori decimali.  Infatti, in
un contatore \index{Binary Coded Decimal}BCD (Binary Coded Decimal) un
numero \`e espresso come una sequenza di cifre decimali. Ad esempio,
il numero 3702 \`e memorizzato come mostrato nella
tabella~\ref{logici_decima}.

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c c c c |}
\hline 0011 & 0111 & 0000 & 0010 \\ 3 & 7 & 0 & 1 \\ \hline
                \end{tabular}
        \end{center}
\caption{Memorizzazione del numero 3702 in Binary Coded Decimal.}
\protect\label{logici_decima}
\end{table}

L'integrato 74LS93, che consente il conteggio fino a 16, pu\`o essere
azzerato, come si \`e visto, in corrispondenza del numero 9.  E'
per\`o pi\`u conveniente usare un contatore predisposto per contare in
base 10, come il 74LS90.

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
caratteri esadecimali. Ad esempio, il \Index{numero binario}:
$1010\;1101\;0110\;0011$ \`e rappresentato in esadecimale da: $AD63$.

\subsection{Codici adoperati nei computer}

I simboli non numerici usati nella scrittura (alfabeto, punteggiatura,
parentesi,...) nonch\'e i comandi standard provenienti dalla tastiera
di un computer o inviati ad una stampante, sono espressi nel codice
\Index{ASCII} (American Standard Code for Information
Interchange). Questo \`e un codice a 7 bit, che consente quindi 128
combinazioni diverse.  I principali caratteri ed i codici
corrispondenti sono mostrati nella tabella di
figura~\ref{ascii_codes}.

Nella tabella di 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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/ascii_codes,width=12.0 cm,
height=18 cm}}\end{center}
\caption{Tabelle delle corrispondenze tra caratteri e codice
\Index{ASCII}.}  \protect\label{ascii_codes}
\end{figure}

Un'estensione successiva, ad 8 bit, del codice ASCII f\`u sviluppata
dall'\Index{IBM} e prende il nome di codice \Index{EBCDIC} (Extended
Binary-Coded Decimal Interchange Code).  Questo non \`e molto
adoperato, all'infuori del mondo dei ``mainframes'' \Index{IBM}.




\section{\index{decodificatore}Decodificatori e  \index{display}Display}

Per visualizzare un \Index{numero binario} abbiamo varie
alternative. La prima \`e quella, ovvia, di visualizzare ogni singolo
bit mediante un \Index{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\index{numero esadecimale}.

Utilizzando una decodifica \index{Binary Coded Decimal}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 \Index{chip} 74LS42, che
\`e un integrato a 16 pin. Il \Index{display} pu\`o essere effettuato
utilizzando dei ``\Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/seven_segments,width=10.0 cm,
height=6 cm}}\end{center}
\caption{Visualizzazione dei numeri decimali con un \Index{display} a
7 segmenti.}  \protect\label{seven_segments}
\end{figure}


L'identificazione dei segmenti \`e quella mostrata in corrispondenza
dell'8, in basso nella figura. Il \Index{decodificatore} BCD a sette
segmenti 74LS48, mostrato in figura~\ref{74ls48r}, \`e un
decoder/driver adatto a comandare i segmenti di un \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/74ls48r,width=10.0 cm,
height=12 cm}}\end{center}
\caption{Specifiche del decoder/driver 74LS48 usato per decodificare i
quattro bit in ingresso e pilotare un diplay a 7 segmenti.}
\protect\label{74ls48r}
\end{figure}

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

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

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/sn74ls48r,width=14.0 cm,
height=13 cm}}\end{center}
\caption{Tabella delle verit\`a\index{tabella delle verit\`a} per
l'integrato 74LS48.}  \protect\label{sn74ls48r}
\end{figure}


La decodifica per gruppi di 4 dal binario all'esadecimale pu\`o essere
effettuata utilizzando l'integrato \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/dm74ls154,width=12.0 cm,
height=15 cm}}\end{center}
\caption{Specifiche dell'integrato \Index{74LS154} usato per la
  decodifica da binario ad esadecimale.}  \protect\label{dm74ls154}
\end{figure}

Un circuito che effettua sullo stesso \Index{chip} sia la decodifica
che il \Index{display} esadecimale \`e il \Index{TIL311}. Questo
riceve sui piedini (3,2,13,12) il carattere esadecimale (con il
piedino 3 corrispondente al 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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/til_311,width=7.0 cm,
height=7 cm}}\end{center}
\caption{Layout del \Index{TIL311} usato per la decodifica e
\Index{display} esadecimale.}  \protect\label{til_311}
\end{figure}


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/til_311_details,width=10.0 cm,
height=12 cm}}\end{center}
\caption{Specifiche tecniche del \Index{TIL311}.}
\protect\label{til_311_details}
\end{figure}




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


\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/til_311_blocchi,width=9.0 cm,
height=9 cm}}\end{center}
\caption{Schema a blocchi del \Index{TIL311}.}
\protect\label{til_311_blocchi}
\end{figure}

Notiamo la presenza di un ``\Index{Latch}'' in ingresso. Questo \`e
essenzialmente un insieme di 4 FF di tipo D.  Esso ha lo scopo di
``mantenere'' i dati presentati in ingresso, per il tempo necessario
alla decodifica ed al successivo \Index{display} e lettura. Pi\`u
precisamente, finch\'e il segnale presente sul piedino 5 \`e basso, le
uscita del \Index{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 \Index{LED} sono accesi attraverso i diodi
indicati in figura.  L'ingresso di ``\Index{blanking}'' (piedino 8)
\`e utilizzato per ``abbuiare'' il display.  Ci\`o \'e ottenuto
ponendo tale ingresso al livello alto. Se si vuole \emph{attivare} il
display, tale ingresso va messo al livello basso. Applicando a tale
ingresso una sequenza di impulsi si avr\`a una modulazione
dell'intensit\`a luminosa.


\section{Moltiplicazione e \Index{divisione} in binario}

L'operazione di \Index{moltiplicazione} in binario tra due bit
equivale all'AND di essi (tabella~\ref{logici_undicesima}).

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c c c c c |}
                \hline 0 & $\times$ & 0 & = & 0 \\ 1 & $\times$ & 0 &
= & 0 \\ 0 & $\times$ & 1 & = & 0 \\ 1 & $\times$ & 1 & = & 1 \\
\hline
                \end{tabular}
        \end{center}
\caption{Tabella relativa alla \Index{moltiplicazione} in binario tra
due bit.}  \protect\label{logici_undicesima}
\end{table}

La \Index{moltiplicazione} tra numeri di pi\`u bit pu\`o essere
effettuata con una semplice estrapolazione dell'analogo processo nel
\Index{sistema decimale}. Mostriamo alcuni esempi
(tabelle~\ref{logici_dodicesima} e~\ref{logici_tredicesima}).

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c c c c c c c c r c |}
                \hline & & & 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 &\\ \hline
                \end{tabular}
        \end{center}
\caption{Esempio di \Index{moltiplicazione} tra numeri a pi\`u bit.}
\protect\label{logici_dodicesima}
\end{table}



\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| c c c c c c c c r c |}
                \hline & & & 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 &\\ \hline

                        
                \end{tabular}
        \end{center}
\caption{Esempio di \Index{moltiplicazione} tra numeri a pi\`u bit.}
\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 \Index{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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/multiplier_4bit,width=15.0 cm,
height=9 cm}}\end{center}
\caption{Circuito che effettua la \Index{moltiplicazione} di due
numeri a 3 bit.}  \protect\label{multiplier_4bit}
\end{figure}



Per il risultato della \Index{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
\Index{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 (shiftata).  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 \Index{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 \Index{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 \Index{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 (tabella~\ref{logici_quattordicesima}).

\begin{table}[htb!]
        \begin{center}
                \begin{tabular}{| r c r c r r |}
                \hline 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) \\ \hline
                \end{tabular}
        \end{center}
\caption{Ricerca della prima cifra decimale del quoziente tra i numeri
  33 e 7.}  \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 \index{complemento! a
due}complemento a 2, fornisce il risultato mostrato nella
tabella~\ref{logici_quindicesima}.



\begin{table}[htb!]
\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}
  \caption{Primo passo nella procedura di \Index{divisione} tra i
    numeri $1110_B$ e $0100_B$: sottrazione del secondo dal primo col
    metodo del \index{complemento! a due}complemento a 2.}
    \protect\label{logici_quindicesima}
\end{center}
\end{table}


Abbiamo cio\`e un bit di riporto (o di \Index{overflow}), il quale
indica che la differenza (uguale a $1010_B=10_D$) \`e
positiva. Sottraendo ancora abbiamo il risultato mostrato nella
tabella~\ref{logici_sedicesima}.

\begin{table}[htb!]
\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}
  \caption{Seconda sottrazione nella procedura di divisione.}
  \protect\label{logici_sedicesima}
\end{center}
\end{table}



Abbiamo ancora una differenza positiva (come evidenziato dalla
presenza del bit di riporto) uguale a $6_D$.  Un'ulteriore sottrazione
fornisce quanto si pu\`o vedere nella
tabella~\ref{logici_diciassettesima}.
 
\begin{table}[htb!]
\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}
  \caption{Terza sottrazione nella procedura di divisione.}
  \protect\label{logici_diciassettesima}
\end{center}
\end{table}


cio\`e un numero positivo ($2_D$). Successivamente si ottiene quanto
mostrato nella tabella~\ref{logici_diciottesima}.

\begin{table}[htb!]
\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}
  \caption{Quarta sottrazione nella procedura di divisione.}
  \protect\label{logici_diciottesima}
\end{center}
\end{table}

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}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/divisore_4bit,width=15.0 cm,
height=7 cm}}\end{center}
\caption{Circuito che ralizza la \Index{divisione} tra due numeri
  binari a 4 bit e fornisce in uscita la parte intera del rapporto.}
  \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 \index{complemento! a due}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.

\section{Appendice: Sequenze pseudocasuali\index{sequenza pseudocasuale}}


Abbiamo visto come un \Index{registro}, con l'aggiunta di un feedback,
possa esser adoperato per generate sequenze pseudocasuali. Si parla in
tal caso di un \emph{Linear Feedback Shift
Register\index{shift-register}} o LFSR, dove l'aggettivo ``Linear''
sta ad indicare che il feedback \`e lineare.

I LFSR trovano \Index{applicazioni} che vanno dalla
\Index{criptografia} alla misura del rate di errori nelle
trasmissioni, a certi sistemi di comunicazione senza fili etc..

Discuteremo in questa appendice due aspetti collegati con i LFSR: il
modo in cui il feedback \`e introdotto quando si voglia generare una
sequenza pseudocasuale di lunghezza massima (m-sequenza) e la scelta
dei punti (taps) di feedback.

Per quel che concerne il primo punto, si distingue in genere tra
quella che \`e definita l'implementazione ``alla \Index{Fibonacci}'' e
l'altra, nota come l'implementazione ``alla \Index{Galois}''.

La prima di queste \`e indicata in
figura~\ref{appendice_sequenze_fibonacci}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/appendice_sequenze_fibonacci,width=15.0 cm,
height=4 cm}}\end{center}
\caption{Implementazione ``alla \Index{Fibonacci}'' di un \emph{Linear
    Feedback Shift Register\index{shift-register}}.}
    \protect\label{appendice_sequenze_fibonacci}
\end{figure}

Questa consiste in un registro in cui la somma pesata delle uscite
binarie dei singoli stadi \`e riportata in ingresso. La somma \`e
effettuata in ``modulo 2'', con che si intende che:
\[
0+0=0
\]
\[
0+1=1+0=1
\]
\[
1+1=0
\]

I pesi possono valere solo 0 o 1. I pesi $g_0$ e $g_m$ possono solo
valere 1.

L'implementazione ``alla \Index{Galois}'' \`e invece mostrata in
figura~\ref{appendice_sequenze_galois}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/appendice_sequenze_galois,width=15.0 cm,
height=3.5 cm}}\end{center}
\caption{Implementazione ``alla \Index{Galois}'' di un \emph{Linear
    Feedback Shift Register\index{shift-register}}.}
    \protect\label{appendice_sequenze_galois}
\end{figure}



Qui il contenuto del registro \`e modificato, ad ogni impulso di
clock, da un valore pesato in binario (con pesi 0 o 1) dell'output.
Un'analisi dettagliata mostra che l'ordine dei pesi nella
configurazione di \Index{Galois} \`e opposto a quello della
configurazione di \Index{Fibonacci}, come indicato nelle figure.  Se
si scelgono pesi identici nelle due configurazioni, le due
implementazioni del LFSR forniranno due sequenze che saranno uguali,
ma con \emph{fasi} diverse.

Nella realizzazione di un LFSR, la somma in modulo 2 viene effettuata
facendo uso di porte XOR. Nell'implementazione alla Fibonacci il
registro far\`a uso di uscite parallele e di un ingresso seriale. In
quella di \Index{Galois} far\`a invece uso di ingressi paralleli e di
un'uscita seriale.

Se indichiamo con \emph{m} la lunghezza del registro (cio\`e il numero
di FF di cui esso \`e costituito) esiste una forma abbreviata per
indicare i FF connessi nella rete di feedback. Nell'implementazione
alla Galois, tale forma \`e del tipo:
\[
\left[f_1,f_2,f_3,\cdots,f_j\right]_g
\]

dove $j+1$ \`e il numero totale di FF collegati nella rete di feedback
e con $g_0$ sempre uguale ad 1. $f_1=m$ \`e il FF di ordine pi\`u
elevato presente nella rete di feedback ed $f_j$ sono i rimanenti FF
presenti in tale rete. La sottoscritta $g$ sta ad indicare la
struttura di Galois.

L'analoga forma, nella struttura di \Index{Fibonacci}, si indica con:

\[
\left[f_1,m-f_2,m-f_3,\cdots,m-f_j\right]_f
\]

Anche in tale caso $g_0$ \`e sempre uguale ad 1 ed $f_1=m$.

Esaminiamo come esempio un LFSR di dimensione $m=8$, con collegamenti
di feedback a $g_8,g_6,g_5,g_4$ e con $g_0$ sottinteso. Nella forma di
\Index{Galois} questo sar\`a indicato con:
\[
\left[8,6,5,4\right]_g
\]
ed in quella di Fibonacci con:
\[
\left[8,8-6,8-5,8-4\right]_f=\left[8,2,3,4\right]_f
\]

Normalmente i FF coinvolti nella rete di feedback vengono scritti in
ordine decrescente. Inoltre il primo (quello con l'"'8"' nell'esempio)
\`e l'output del registro e la numerazione degli altri \`e decrescente
andando verso l'input seriale.

Nelle tabelle che specificano i collegamenti di feedback, non \`e
generalmente necessario specificare se si tratti dell'implementazione
di \Index{Fibonacci} o di \Index{Galois}.  Ci\`o poich\'e un dato set
di collegamenti funzioner\`a con una qualsiasi delle due
forme. L'unica differenza sar\`a costituita dal fatto che l'ordine
della sequenza ottenuta in una caso \`e l'inverso di quella ottenuta
nell'altro.

Veniamo ora alla determinazione dei collegamenti di feedback necessari
per ottenere una sequenza pseudocasuale\index{sequenza pseudocasuale}
di lunghezza massima. Come gi\`a visto, se il LFSR ha lunghezza $m$,
la lunghezza massima vale $N=2^m-1$. Con riferimento
all'implementazione di \Index{Galois} di
figura~\ref{appendice_sequenze_galois} un generico LFSR pu\`o essere
associato ad un ``polinomio generatore'' del tipo:

\[
G(X)=g_m X^m + g_{m-1} X^{m-1} + g_{m-2} X^{m-2} + \cdots +g_2 X^2 +
g_1 X +g_0
\]

dove i coefficienti $g_i$ rappresentano i ``pesi'' di
figura~\ref{appendice_sequenze_galois}. Ricordiamo che $g_1=1$ se
l'$i^{ma}$ connessione \`e presente; $g_1=0$ se essa \`e assente. A
questi polinomi si applicano le normali regole dell'algebra, con la
sola variante che ora tutte le operazioni algebriche sono effettuate
in ``modulo 2'', cio\`e:

(a) per la somma:

\[
0+0=0
\]
\[
0+1=1+0=1
\]
\[
1+1=0
\]

(b) per il prodotto:

\[
0 \cdot 0 = 0
\]
\[
0 \cdot 1 = 1
\]
\[
1 \cdot 1 = 1
\]

Consideriamo ad esempio il polinomio:

\begin{equation}
G(X)=X^3 + X^1 + 1 \label{eqn_logici_appendix_a1}
\end{equation}

dove: $g_3=1$, $g_2=0$, $g_1=1$, $g_0=1$.  Questo rappresenta il LFSR
mostrato in figura~\ref{appendice_sequenze_galois_example}.

\begin{figure}[htb!]
  \begin{center}\mbox{\epsfig{file=logici/appendice_sequenze_galois_example,width=10.0 cm,
height=3.5 cm}}\end{center}
\caption{LFSR che implementa l'esempio descritto.}
\protect\label{appendice_sequenze_galois_example}
\end{figure}

Con la notazione di sopra, questo \`e:

\[
\left[3,1\right]_g
\]

Veniamo ora alla regola generale per individuare i polinomi generatori
associati a sequenze di lunghezza massima. La regola dice che il
polinomio deve:

\begin{itemize}
\item{esser ``primo'' (cio\`e non fattorizzato)}
\item{essere un fattore di $X^N+1$, dove $N=2^m-1$}
\end{itemize}

dove tutte le operazioni vanno effettuate in modulo 2.

Consideriamo nuovamente l'esempio del
polinomio~\ref{eqn_logici_appendix_a1}. Notiamo che m=3 e che
$N=2^3-1=7$. Si pu\`o dimostrare che il
polinomio~\ref{eqn_logici_appendix_a1} \`e primo e che esso \`e un
fattore di $X^7+1$. Infatti \`e facile verificare che, modulo 2, \`e:
\[
X^7+1=(X+!)(X^3+X+1)(X^3+X^2+1)
\]
Dei tre polinomi a fattore nel secondo membro di quest'equazione, il
secondo fornisce appunto la sequenza:
\[
\left[3,1\right]_g
\]
Vediamo che una sequenza alternativa \`e fornita dal terzo polinomio a
secondo membro, che d\`a:
\[
\left[3,2\right]_g
\]
Il primo dei polinomi a secondo membro: $(X+1)$ non \`e di ordine 3 e
quindi non \`e un generatore per il nostro LFSR.

Notiamo ancora che, dato un LFSR di una certa lunghezza, il numero di
combinazioni diverse che forniscono sequenze di lunghezza massima \`e
sempre pari. Dato infatti l'insieme:
\[
\left[f_1,f_2,f_3,\cdots,f_j\right]_g
\]
esiste l'insieme alterantivo:
\[
\left[f_1,m-f_2,m-f_3,\cdots,m-f_j\right]_g
\]
che fornisce una sequenza speculare a quella fornita dal primo.

Le sequenze ottenute dalle diverse combinazioni di feedback
differiscono solo per una fase.

Nelle tabelle che seguono, diamo i valori delle combinazioni di
feedback per tutti i registri di lunghezza inferiore o uguale a 12.

\vspace{1 cm}



10 stadi, 2 taps: (1 combinazione)

[10,~7]

\vspace{0.5cm}

10 stadi,~4 taps: (10 combinazioni)

[10,~9,~8,~5] [10,~9,~7,~6] [10,~9,~7,~3] [10,~9,~6,~1] [10,~9,~5,~2] [10,
9,~4,~2] [10,~8,~7,~5]

[10,~8,~7,~2] [10,~8,~5,~4] [10,~8,~4,~3]

\vspace{0.5 cm}

10 stadi,~6 taps: (14 combinazioni)

[10,~9,~8,~7,~5,~4] [10,~9,~8,~7,~4,~1] [10,~9,~8,~7,~3,~2] [10,~9,~8,~6,
5,~1] [10,~9,~8,~6,~4,~3]

[10,~9,~8,~6,~4,~2] [10,~9,~8,~6,~3,~2] [10,~9,~8,~6,~2,~1] [10,~9,~8,~5,
4,~3] [10,~9,~8,~4,~3,~2]

[10,~9,~7,~6,~4,~1] [10,~9,~7,~5,~4,~2] [10,~9,~6,~5,~4,~3] [10,~8,~7,~6,
5,~2]

\vspace{0.5 cm}

10 stadi,~8 taps: (5 combinazioni)

[10,~9,~8,~7,~6,~5,~4,~3] [10,~9,~8,~7,~6,~5,~4,~1]

[10,~9,~8,~7,~6,~4,~3,~1] [10,~9,~8,~6,~5,~4,~3,~2]

[10,~9,~7,~6,~5,~4,~3,~2]

\vspace{0.5 cm}

11 stadi,~2 taps: (1 set)

[11,~9]

\vspace{0.5 cm}

11 stadi,~4 taps: (22 combinazioni)

[11,~10,~9,~7] [11,~10,~9,~5] [11,~10,~9,~2] [11,~10,~8,~6]
[11,~10,~8,~1] 
 
[11,~10,~7,~3] [11,~10,~7,~2] [11,~10,~6,~5]
[11,~10,~4,~3] [11,~10,~3,~2] 

[11,~9,~8,~6] [11,~9,~8,~4] [11,~9,~8,~3] [11,~9,~7,~4] [11,~9,~7,~2]

[11,~9,~6,~5] [11,~9,~6,~3] [11,~9,~5,~3] [11,~8,~6,~4] [11,~8,~6,~3]

[11,~7,~6,~5] [11,~7,~6,~4]

\vspace{0.5 cm}


11 stadi,~6 taps: (40 combinazioni)

[11,~10,~9,~8,~7,~4] [11,~10,~9,~8,~7,~1] [11,~10,~9,~8,~5,~4]

[11,~10,~9,~8,~4,~3] [11,~10,~9,~8,~3,~1] [11,~10,~9,~7,~5,~1]

[11,~10,~9,~7,~4,~1] [11,~10,~9,~6,~5,~4] [11,~10,~9,~6,~4,~2]

[11,~10,~9,~6,~3,~1] [11,~10,~9,~6,~2,~1] [11,~10,~9,~5,~4,~3]

[11,~10,~9,~5,~4,~1] [11,~10,~9,~5,~3,~1] [11,~10,~9,~4,~3,~2]

[11,~10,~8,~7,~6,~5] [11,~10,~8,~7,~6,~3] [11,~10,~8,~7,~5,~3]

[11,~10,~8,~7,~4,~1] [11,~10,~8,~6,~5,~4] [11,~10,~8,~6,~5,~1]

[11,~10,~8,~6,~4,~3] [11,~10,~8,~6,~4,~2] [11,~10,~8,~5,~3,~2]

[11,~10,~8,~4,~3,~2] [11,~10,~7,~6,~5,~3] [11,~10,~7,~6,~5,~1]

[11,~10,~7,~6,~4,~2] [11,~10,~7,~6,~4,~1] [11,~10,~7,~6,~3,~2]

[11,~10,~7,~4,~3,~2] [11,~9,~8,~7,~6,~3] [11,~9,~8,~7,~4,~2]

[11,~9,~8,~6,~5,~2] [11,~9,~8,~6,~4,~3] [11,~9,~7,~6,~5,~4]

[11,~9,~7,~6,~5,~3] [11,~9,~7,~6,~4,~2] [11,~9,~6,~5,~4,~3]

[11,~8,~7,~6,~4,~3]

\vspace{0.5 cm}


11 stadi,~8 taps: (25 combinazioni)

[11,~10,~9,~8,~7,~6,~5,~3] [11,~10,~9,~8,~7,~6,~5,~2]
[11,~10,~9,~8,~7,~6,~4,~1]

[11,~10,~9,~8,~7,~6,~3,~2] [11,~10,~9,~8,~7,~5,~4,~2]
[11,~10,~9,~8,~7,~5,~3,~2] 

[11,~10,~9,~8,~7,~5,~2,~1]
[11,~10,~9,~8,~7,~4,~3,~1] [11,~10,~9,~8,~7,~4,~2,~1]

[11,~10,~9,~8,~6,~5,~4,~2] [11,~10,~9,~8,~6,~5,~3,~2]
[11,~10,~9,~8,~6,~5,~3,~1] 

[11,~10,~9,~8,~6,~4,~3,~2]
[11,~10,~9,~8,~5,~4,~2,~1] [11,~10,~9,~7,~6,~5,~4,~3]

[11,~10,~9,~7,~6,~5,~4,~1] [11,~10,~9,~7,~6,~4,~3,~2]
[11,~10,~9,~7,~5,~4,~3,~1] 

[11,~10,~9,~6,~5,~4,~3,~2] [11,~10,~9,~6,~5,~4,~3,~1]
[11,~10,~8,~7,~6,~5,~4,~2] 

[11,~10,~8,~7,~6,~4,~3,~1]
[11,~10,~8,~7,~5,~4,~3,~2] [11,~9,~8,~7,~6,~5,~3,~2]

[11,~9,~8,~7,~6,~4,~3,~2] 

\vspace{0.5 cm}

12 stadi,~4 taps: (9 combinazioni)

[12,~11,~10,~4] [12,~11,~10,~2] [12,~11,~8,~6] [12,~11,~7,~4]
[12,~10,~9,~3]  

[12,~10,~5,~4] [12,~9,~8,~5] [12,~9,~7,~6] [12,~8,~6,~5]

\vspace{0.5 cm}


12 stadi,~6 taps: (43 combinazioni)

[12,~11,~10,~9,~8,~4] [12,~11,~10,~9,~6,~4] [12,~11,~10,~9,~6,~2] 

[12,~11,~10,~9,~4,~3] [12,~11,~10,~9,~4,~2] [12,~11,~10,~8,~7,~3] 

[12,~11,~10,~8,~7,~2] [12,~11,~10,~8,~6,~4] [12,~11,~10,~8,~6,~1]

[12,~11,~10,~8,~5,~1] [12,~11,~10,~8,~2,~1] [12,~11,~10,~7,~6,~3]

[12,~11,~10,~7,~6,~2] [12,~11,~10,~7,~5,~2] [12,~11,~10,~7,~2,~1]

[12,~11,~10,~6,~3,~2] [12,~11,~9,~8,~7,~6] [12,~11,~9,~8,~7,~4]

[12,~11,~9,~8,~4,~1] [12,~11,~9,~8,~3,~1] [12,~11,~9,~7,~6,~5]

[12,~11,~9,~7,~6,~4] [12,~11,~9,~7,~3,~1] [12,~11,~9,~6,~5,~3]

[12,~11,~9,~5,~4,~1] [12,~11,~8,~7,~6,~3] [12,~11,~8,~7,~5,~4]

[12,~11,~8,~6,~5,~2] [12,~11,~8,~5,~4,~2] [12,~11,~7,~5,~4,~3]

[12,~11,~6,~4,~3,~2] [12,~10,~9,~8,~7,~6] [12,~10,~9,~8,~7,~3]

[12,~10,~9,~8,~6,~2] [12,~10,~9,~8,~4,~3] [12,~10,~9,~8,~4,~2]

[12,~10,~9,~7,~5,~2] [12,~10,~9,~6,~4,~3] [12,~10,~9,~6,~4,~2]

[12,~10,~8,~7,~6,~2] [12,~9,~8,~7,~5,~3] [12,~9,~8,~7,~4,~3]

[12,~9,~8,~6,~5,~4] 

\vspace{0.5 cm}


12 stadi,~8 taps: (18 combinazioni)

[12,~11,~10,~9,~8,~7,~6,~3] [12,~11,~10,~9,~8,~7,~4,~3] 
[12,~11,~10,~9,~8,~6,~5,~4] 

[12,~11,~10,~9,~8,~5,~2,~1]
[12,~11,~10,~9,~8,~4,~3,~1] [12,~11,~10,~9,~7,~6,~5,~1]


[12,~11,~10,~9,~7,~3,~2,~1] [12,~11,~10,~9,~6,~5,~4,~1]
[12,~11,~10,~9,~6,~5,~2,~1] 

[12,~11,~10,~8,~6,~5,~4,~2]
[12,~11,~10,~8,~6,~4,~3,~1] [12,~11,~10,~7,~6,~5,~4,~1]

[12,~11,~10,~7,~5,~4,~3,~1] [12,~11,~9,~8,~7,~6,~4,~1]
[12,~11,~9,~7,~6,~5,~4,~2] 

[12,~11,~8,~7,~5,~4,~3,~2]
[12,~10,~9,~8,~7,~5,~3,~2] [12,~10,~9,~8,~6,~5,~4,~2] 

\vspace{0.5 cm}


12 stadi,~10 taps: (2 combinazioni)

[12,~11,~10,~9,~8,~7,~5,~4,~3,~2] [12,~11,~10,~9,~8,~7,~5,~4,~3,~1]


\newpage
