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

Registri di scorrimento

Un registro in un calcolatore digitale è un circuito di memorizzazione di ampiezza, in generale, pari a una parola (o voce) di macchina.

Poiché una parola di macchina consiste di un numero determinato di bit, e poiché un flip-flop è un elemento di memorizzazione binario, un registro è costituito da un insieme di flip-flop.

In figura 3.1.1 viene data la rappresentazione simbolica di un registro: ogni quadrato rappresenta un flip-flop.

La lettera A indica il registro A e la lettera A_i il flip-flop i-esimo.

Un registro a scorrimento (o shift rergister) permette di fare scorrere il proprio contenuto sulla destra, o sulla sinistra o in entrambe le direzioni; in fig. 3.1.2_a compare la rappresentazione simbolica di un registro di shift. Un registro di shift a n bits fa scorrere un bit alla volta richiedendo quindi n operazioni di shift per inserire o estrarre una parola seriale di n bits.

Circuiti addizionali sono richiesti nel registro di shift se una parola deve essere inserita o prelevata in parallelo: infatti un registro può convertire una parola seriale in una parallelo (3.1.2b) o una parallela in una seriale (3.1.2c).

Connettendo l'output all'input di un registro di shift, quest'ultimo un circulating register (3.1.2d)

Equazioni logiche di un registro di shift

Un registro di shift richiede una memorizzazione temporanea tra due flip-flop adiacenti in modo che venga conservata l'informazione di un flip-flop che sta per cambiare e utilizzare tale memorizzazione come input per il flip-flop successivo. In fig. 3.1.3 compare un registro di shift in cui l'elemento base è costituito da flip-flop SR.

L'output di questo flip-flop SR viene indicato con lettera maiuscola A_n o il complemento ${\bar {A}}_{n}$; gli input sono indicati con lettere minuscole, a_nr e a_ns, e rappresentano gli input reset e set del n-simo flip-flop.

La lettera p rappresenta il segnale di clock che determina l'operazione di shift. Come si è già visto a proposito dei contatori, anche per i registri di shift vi sono due tipi di equazioni logiche.

Il primo tipo descrive lo stato del registro : gli stati dei singoli flip-flop di un registro a scorrimento sono rappresentati nella tabella affiancata, da cui si deduce l'equazione di stato

$A_{n}(t)=A_{n-1}\cdot p$

Questa equazione indica che lo stato dello n-esimo flip-flop dopo l'intervallo temporale τ è lo stato del flip-flop (n-1)-esimo.

Il secondo tipo di equazioni logiche descrive l'input del flip-flop. I valori che devono essere assunti dagli impulsi Set e Rersetdel flip-flop n-desimo sono rappresentati nella figura adiacente.

Da cui si deducono le equazioni di input dei flip-flop di un registro di shift:

$a_{nr}={\bar {A}}_{n-1}\cdot p$

$a_{ns}=A_{n-1}\cdot p$

Da queste considerazioni è stato dedotto il circuito di fig. 3.1.3

Trasferimento dell'informazione

L'informazione conservata in un registro costituisce una parola: mediante un trasferimento di informazione, cerchiamo di realizzare il trasferimento della una parola da un registro ad un altro o un trasferimento multiplo da uno o più registri ad altri registri.

L'importanza di una operazione di trasferimento consiste non solo nel trasferimento stesso, ma nella possibilità di compiere operazioni logiche sulla parola durante il trasferimento. Il trasferimento dell'informazione tra vari registri è l'operazione base mediante la quale possono essere realizzati la elaborazione dei dati, le decisioni logiche, ecc., in un calcolatore: inizialmente le informazioni sono conservate in una unità di memoria da cui vengono trasferite nei vari registri secondo una certa sequenza.

Sono stati sviluppati dei metodi simbolici per poter rappresentare questo processo di trasferimento delle informazioni: in primo luogo un trasferimento viene espresso mediante una istruzione simbolica.

Le equazioni logiche e i diagrammi logici possono essere quindi ottenuti dalle istruzioni simboliche.

Per poter descrivere un tale procedimento simbolico si sono mostrati nel seguente elenco i simboli utilizzati.

Simboli	Descrizione dei simboli
Lettere maiuscole	indicano i registri
Indice i	Denota lo iesimo bit di un registro
Parentesi ()	Indicano il contenuto di un registro
Doppia freccia $\Longrightarrow$	Indica il trasferimento di una parola da un registro all'altro
Parentesi []	Porzione di registro il cui contenuto ha una dipendenza funzionale del registro stesso
Due punti :	Due punti (preceduti da una variabile booleana) indicano il verificarsi dell'istruzione segujente quando la variabile ha il valore 1
Freccia semplice $\longrightarrow$	Indica una sequenza di stati
Segno +	Questo simbolo ha due significati: 1) una operazione logica OR quando esso è usato tra variabili booleane; 2) un'addizione aritmetica quando è usato tra numeri
Segno -	Questo simbolo indica una operazione aritmetica

Per esempio (A) indica il contenuto del registro (A) e (A_i) indica il contenuto dell'i^simo bit del registro A; (A,B) indica il contenuto dei registri A e B che vengono usati insieme come un unico registro.

Con (A)$\Longrightarrow$ B si indica che il contenuto del registro A viene trasferito in B e $0\Longrightarrow$ A significa che degli zeri vengono inseriti in A. L'operazione di shift a sinistra viene indicata con $(A_{i})\Longrightarrow A_{i+1}$, supponendo che l'indice i incrementato indichi un bit significativo di rango superiore.

L'operazione di shift a destra sarà allora:

$(A_{i})\Longrightarrow A_{i-1}$

Le espressioni simboliche $S_{n}[A]$ e $N_{m}[A]$, indicano la parte segno e la parte numerica del registro A. L'espressione $P_{i}:0\Longrightarrow A$ indica che, quando p_i ha il valore 1, viene eseguita l'istruzione che azzera il registro A.

Mediante questo simbolismo, si può descrivere una operazione di trasferimento: supponiamo di avere una parole di 3 bit nel registro A e di trasferirla in B al momento in cui viene dato il via da un segnale P₁ proveniente dall'unità di controllo del calcolatore.

Tale operazione si esprimerà nella forma

$P_{1}:(A)\Longrightarrow B\ \ \ \ (3.2.2)$

Supponendo che i registri siano costituiti da flip-flop T, dalla (3.2.2) si deduce la tavola della verità (3.2.3).

In questa tabella, il trasferimento inizia quando l'impulso p dell'orologio è uguale ad 1: $b_{it}$ indica il valore d'ingresso del flipo-flop rappresentativo dell'$i^{esimo}$ bit nel registro B.

$b_{it}=(A_{i}\oplus B_{i})\cdot P_{1}\cdot P\ \ \ \ per\ \ i=1,2,3$

Queste equazioni indicano che l'0perazione di trasferimento in un registro B costituito da flip-flop T viene realizzato mediante un XOR. Nella figura collocata di fianco compare il diagramma logico (trasferimento in parallelo di una parola dal registro A al registro B) che descrive la connessione dei due registri.

L'esempio presente si riferisce ad un trasferimento in parallelo di una parola: una informazione può essere però trasferita in forma sequenziale.

Come esempio, consideriamo la somma aritmetica tra due numeri binari entrambi di cinque bit: siano essi conservati nei registri di shift A e B (fig. 3.2.5). L'addizione avviene quando P₁, proveniente dall'unità di controllo, assume il valore 1.

Nella addizione seriale, coppie di bits corrispondenti dei due numeri vengono sommati allo stesso istante, quindi i due numeri vengono fatti scorrere del registro a trasferimento dagli impulsi di orologio P₁, P₂, P₃, P₄ e P₅.

Il trasferimento può essere espresso dalla seguente formula simbolica:

$P_{1}P_{i}:\ \ \ \ (B_{i})\Longrightarrow B_{i-1}$

$0\Longrightarrow B_{5}$

$(A_{i})\Longrightarrow A_{i-1}\ \ \ \ \ \ \ \ \ \ per\ i=1,....,5$

$\ \ \ \ \ \ S_{i}\Longrightarrow A_{5}$

C_{i+1} = $\triangle C_{i}$

dove S_i e C_i sono le funzioni descritte nel cap.II parte II.

Le prime tre istruzioni simboliche indicano lo shift a destra dei registri A e B.

Le ultime due istruzioni descrivono la connessione del bit di riporto e la memorizzazione del bit somma nel flip-flop A₅.

Il diagramma logico di questo addizionatore binario seriale è mostrato in (3.2.5)

Il metodo simbolico visto ora può essere utilizzato sia per costruire i diagrammi logici di un circuito, sia le equazioni logiche di quest'ultimo. Nella figura compare il diagramma logico di un accumulatore binario seriale. Esso consiste in un addizionatore seriale per eseguire la somma e in un registro a scorrimento per conservare uno degli addendi prima della addizione o la somma dopo l'addizione.

Accumulatori binari

Per accumulatore binario, si intende un circuito in cui un registro memorizza un numero binario e appena ne riceve un'altr4o, quest'ultimo viene sommato (o sottratto) dal primo numero e quindi viene memorizzata la somma (o la differenza). Un accumulatore può essere costruito per operazioni in parallelo o in serie.

Nella figura compare il diagramma logico di un accumulatore binario seriale. Esso consiste in un addizionatore seriale per eseguire la somma e in un registro a scorrimento per conservare uno degli addendi prima della della addizione o la somma dopo l'addizione.

La sottrazione può essere ottenuta mediante la somma del complemento a 2 del numero.

Se l'addizionatore seriale di fig. 3.3.1 viene sostituito con un sottrattore seriale o con un addizionatore-sottrattore seriale, l'accumulatore può eseguire la sottrazione o entrambe le operazioni di somma e sottrazione.

In figura 3.3.2 viene mostrato un accumulatore binario parallelo.

Ogni flip-flop dell'accumulatore funziona come un contatore modulo 2.

Il primo addendo è inizialmente conservato in questi contatori

Durante l'addizione ogni contatore contenga gli impulsi rappresentativi del bit di addendo o di riporto, e genera un segnale di riporto quando il suo stato cambia da 1 a 0.

Il diagramma logico di un accumulatore binario parallelo relativo all'addizione viene ora descritto mediante il metodo simbolico.

In fig. 3.3.3 consideriamo l'i-esimo stadio: l'addizione può essere decomposta in due passi; durante il primo vengono sommati i bits A_i e B_i, durante il secondo vengono addizionate la somma risultante dal primo passo e il bit di riporto dovuto all'operazione di somma compiuta sui bit di rango inferiore.

Le istruzioni simboliche di questi due passi sono:

$P_{1}p_{1}:B_{i}\cdot ({\bar {A}}_{i})+{\bar {B}}_{i}(A_{i})\Longrightarrow A_{i}$

$P_{1}p_{1}:\ C_{i-1}({\bar {A}}_{i})+{\bar {C}}_{i-1}\ (A_{i})\Longrightarrow A_{i}$

In queste istruzioni la somma di A_i e B_i avviene al clock pulse p₁; la somma del risultante bit A_ie del riporto C_i-1 avviene all'impulso seguente p₂. Entrambe le addizioni hanno luogo durante lo stato P₁ che dà l'ordine di addizionare da parte dell'unità di controllo.

Il bit di riporto può essere formato in più modi.

Per esempio:

$C_{i}=B_{i}{\bar {S}}_{i}+C_{i-1}S_{i}$

dove $S_{i}$ e math>\bar S_i</math> sono le uscite del flip-flop A_i dopo il clock pulse P₁

La linea di ritardo assicura che il cambio di stato dello flip-flop A_iavvenga dopo che si sia formato il nuovo riporto.

Un accumulatore può essere anche predisposto ad eseguire una sottrazione. In questo caso le istruzioni simboliche relative alla differenza sono le stesse di quelle relative alla somma mentre cambia l'espressione booleana che dà il riporto.

Chiameremo inoltre P₂ lo stato del calcolatore che indica l'operazione di sottrazione.

$P_{2}p_{1}:B_{i}({\bar {A}}_{i})+{\bar {B}}_{1}(A_{i})\Longrightarrow A_{i}$

$P_{2}p_{2}:R_{i-1}({\bar {A}}_{i})+{\bar {R}}_{i-1}(A_{i})\Longrightarrow A_{i}$

dove R_i è la ritenuta:

$R_{i}=D_{i}B_{i}+{\bar {D}}_{i}R_{i-1}$

essendo D_i la differenza allo i^simo stadio.

Nella figura 3.3.4 compare il diagramma logico di un accumulatore-sottrattore.

Nella figura 3.3.4 compare il diagramma logico di un accumulatore-sottrattore.

Si può ora formare un accumulatore relativo sia all'addizione che alla sottrazione.

Esaminando infatti i diagrammi 3.3.3 e 3.3.4 si vede che l'unica differenza tra i due consiste nella connessione della uscita del flip-flop A_i.

Un accumulatore per addizione e sottrazione può allora essere costruito usando quattro addizionali porte di AND e due addizionali circuiti OR. (fig-3.3.5)

Quando lo stato è P₁, l'accumulatore somma, quando lo stato è P₂, avviene la sottrazione.

Matrici di commutazione

Un importante circuito di un elaboratore digitale è costituito dalle matrici di commutazione, descritte nel seguito del paragrafo mediante l'ausilio delle matrici booleane.

Circuiti di commutazione con uscita multipla

Un circuito di commutazione con output multiplo può essere descritto mediante un certo numero di funzioni booleane.

Prendiamo come esempio il full-adder relativo ad un singolo bit.

Le tavole della verità sono date nel capitolo II° parte II^da e da queste si ottengono le formule per la somma S e il riporto C₀:

$S={\bar {X}}<br/>{\bar {Y}}C_{i}+{\bar {X}}Y{\bar {C}}_{i}+x{\bar {Y}}{\bar {C}}_{i}+XYC_{i}$

$C_{0}={\bar {X}}YC_{i}+X{\bar {Y}}C_{i}+XY{\bar {C}}_{i}+XYC_{i}$

dove X, Y e C_isono rispettivamente gli addendi, e il bit di riporto.

Queste funzioni possono essere scritte mediante i prodotti fondamentali:

$S=m_{1}+m_{2}+m_{4}+m_{7}$

$C_{0}m_{3}+m_{5}+m_{6}+m_{7}$

Le due funzioni S e C_0 possono però essere espresse anche come:

$S=(0\times m_{0})+(1\times m_{1})+(1\times m_{2})+(0\times m_{3})+(1\times m_{4})+(0\times m_{5})+(0\times m_{6})+(1\times m_{7})\ \ (3.4.1)$ $C_{0}=(0\times m_{0})+(0\times m_{1})+(0\times m_{2})+(1\times m_{3})+(0\times m_{4})+(1\times m_{5})+(1\times m_{6})+(1\times m_{7})\ \ (3.4.2)$

Queste due ultime equazioni possono essere rappresentate mediante matrici booleane, come segue:

o con notazione matriciale:

${\begin{bmatrix}0\end{bmatrix}}={\begin{bmatrix}B\end{bmatrix}}\times {\begin{bmatrix}m\end{bmatrix}}$

dove [0], [B] e [m] sono rispettivamente la matrice di uscita, la matrice booleana B e la matrice dei prodotti fondamentali.

La moltiplicazione della matrice B per la matrice m segue le regole ordinarie della moltiplicazione dell'algebra matriciale.

In altre parole, gli elementi della matrice 0 sono la somma dei prodotti dei termini di m per i corrispondenti bit della matrice B, come mostrato nella 3.4.1 e 3.4.2.

La matrice B è costituita da due righe e otto colonne: ogni riga rappresenta una uscita mentre ogni colonna rappresenta un minterm.

Gli 1 della riga 01101001 rappresentano i termini m₁, m₂, m₄ m₇ mentre quelli della riga 00010111 rappresentano i termini m₃, m₅, m₆, m₇: cioè la matrice booleana B rappresenta un insieme dei vettori caratteristici delle finzioni booleane S e C₀.

Le espressioni booleane per S e C₀ possono essere scritte mediante i maxterm (somme fondamentali).

$S=M_{0}\ M_{3}\ M_{5}\ M_{6}$

$C_{0}=M_{0}\ M_{1}\ M_{2}\ M_{4}$

espressioni equivalenti a:

$S=(0+M_{0})(1+M_{1})(1+M_{2})(0+M_{3})(1+M_{4})(0+M_{5})(0+M_{6})(1+M_{7})\ \ \ \ (3.4.4)$

$C_{0}=(0+M_{0})(0+M_{1})(0+M_{2})(1+M_{3})(0+M_{4})(1+M_{5})(1+M_{6})(1+M_{7})\ \ \ \ (3.4.5)$

Rappresentando le formule (3.4.3) e (3.4.4) mediante matrici booleane, si ha:

${\begin{bmatrix}S\\C_{0}\end{bmatrix}}={\begin{bmatrix}0&1&1&0&1&0&0&1\\0&0&0&1&0&1&1&1\end{bmatrix}}\times {\begin{bmatrix}M_{0}\\M_{1}\\M_{2}\\M_{3}\\M_{4}\\M_{5}\\M_{6}\\M_{7}\end{bmatrix}}\ \ \ \ (3.4.6)$

o con la notazione matriciale:

${\begin{bmatrix}0\end{bmatrix}}={\begin{bmatrix}B\end{bmatrix}}\times {\begin{bmatrix}M\end{bmatrix}}$

dove [M] è la matrice M dei maxterm.

In questo caso la moltiplicazione della matrice B per la matrice M non segue le regole ordinarie della moltiplicazione dell'algebra matriciale.

Infatti, come si vede dalle (3.4.4) e (3.4.5) il generico elemento della matrice prodotto è definito come il prodotto delle somme dei singoli termini di M con il corrispondente bit della matrice B.

Le funzioni (3.4.3) e (3.4.6) ottenute mediante notazioni matriciali, risultano espresse nelle due forme canoniche e le matrici booleane B delle due forme risultano identiche.

Quindi, quando di un circuito a più uscite, si conosce la matrice B della notazione matriciale booleana e quest'ultima è data in forma canonica, sono conosciute immediatamente anche le equazioni booleane di tutti gli output, sia nella forma canonica disgiuntiva che in quella congiuntiva.

Ovviamente si possono trovare immediatamente le espressioni ${\bar {S}}$ e ${\bar {C}}_{0}$. Infatti:

${\bar {S}}=m_{0}+m_{3}+m_{5}+m_{6}$

${\bar {C}}_{0}=m_{0}+m_{1}+m_{2}+m_{4}$

oppure

${\begin{bmatrix}{\bar {0}}\end{bmatrix}}={\begin{bmatrix}{\bar {B}}\end{bmatrix}}\times {\begin{bmatrix}m\end{bmatrix}}$

Da cui le espressioni matriciali booleane:

${\begin{bmatrix}{\bar {S}}\\{\bar {C}}_{0}\end{bmatrix}}={\begin{bmatrix}0&1&1&0&1&0&0&1\\0&0&0&1&0&1&1&1\end{bmatrix}}\times {\begin{bmatrix}m_{0}\\m_{1}\\m_{2}\\m_{3}\\m_{4}\\m_{5}\\m_{6}\\m_{7}\end{bmatrix}}\ \ \ \ (3.4.7)$

oppure

${\begin{bmatrix}{\bar {0}}\end{bmatrix}}={\begin{bmatrix}{\bar {B}}\end{bmatrix}}\times {\begin{bmatrix}m\end{bmatrix}}$

dove [${\bar {0}}$] è la matrice di uscita complementare e [${\bar {B}}$] è la matrice B complementata.

È da notare che ogni bit di ${\bar {B}}$ è il complemento a 1 del corrispondente bit della matrice B

La moltiplicazione della matrice <magth>\bar B</math> per la matrice m segue le regole della moltiplicazione dell'algebra matriciale.

Usando i maxterms, si ha invece:

${\bar {S}}=M_{1}\ M_{2}\ M_{4}\ M_{7}$

${\bar {C}}_{0}=M_{3}\ M_{5}\ M_{6}\ M_{7}$

da cui, le forme matriciali sono:

${\begin{bmatrix}{\bar {S}}\\{\bar {C}}_{0}\end{bmatrix}}={\begin{bmatrix}1&0&0&1&0&1&1&0\\1&1&1&0&1&0&0&0\end{bmatrix}}\times {\begin{bmatrix}M_{0}\\M_{1}\\M_{2}\\M_{3}\\M_{4}\\M_{5}\\M_{6}\\M_{7}\end{bmatrix}}\ \ \ \ (3.4.8)$

oppure:

${\begin{bmatrix}{\bar {0}}\end{bmatrix}}={\begin{bmatrix}{\bar {B}}\end{bmatrix}}\times {\begin{bmatrix}M\end{bmatrix}}$

La moltiplicazione della matrice B con la matrice M non segue le regole ordinarie dell'algebra matriciale ma è definita da (3.4.4) e (3.4.5).

Matrici di commutazione rettangolari

La matrice di commutazione è un circuito con output multiplo: essa realizza una matrice booleana.

Le matrici più comuni sono quelle rettangolari, ad albero e a doppio albero.

Esistono però anche altri tipi di matrici.

Una matrice rettangolare che utilizza solo porte di AND è rappresentata in fig. 3.4.1.

Tale matrice è relativa a tre variabili booleane e coinvolge nella sua realizzazione tre coppie di input e otto output.<br7> Per ogni prodotto delle tre variabili di input esiste uno e uno solo output.

Le funzioni booleane dei 8 output sono:

$f_{0}\ =\ m_{0}\ =\ {\bar {A}}{\bar {B}}{\bar {C}}\ \ \ \ \ \ \ \ \ f_{1}\ =\ m_{1}\ =\ {\bar {A}}{\bar {B}}\ C$

$f_{2}\ =\ m_{2}\ =\ {\bar {A}}\ B{\bar {C}}\ \ \ \ \ \ \ \ \ f_{3}\ =\ m_{3}\ =\ {\bar {A}}\ B\ C$

$f_{4}\ =\ m_{4}\ =\ A{\bar {B}}{\bar {C}}\ \ \ \ \ \ \ \ \ f_{5}\ =\ m_{5}\ =\ A{\bar {B}}\ C$

$f_{6}\ =\ m_{6}\ =\ A\ B{\bar {C}}\ \ \ \ \ \ \ \ \ f_{7}\ =\ m_{7}\ =\ A\ B\ C$

Il circuito può anche essere espresso mediante una forma matriciale:

In questa matrice booleana compare un solo 1 in ogni riga e tutti gli 1 si vengono a trovare sulla diagonale principale.

Per la realizzazione del circuito non sono necessarie porte di OR. Questa è la forma più semplice che può assumere una matrice B relativa ad una matrice di commutazione avente tre coppie di input ed otto output.

Si vede da fig. 3.4.1, che per tre variabili sono necessarie otto porte di AND a tre ingressi. All'input di ogni AND led tre variabili di input possono comparire sia in forma diretta che in forma complimentata.

Per n coppie di variabili di input, il numero di input relativi alla porta di AND diventa di n 2_n; cioè un numero molto elevato per un valore grande di n.

Matrici più economiche si ottengono mediante strutture ad albero 0 a doppio albero (vedi fig. 3.4.3).

Una matrice rettangolare con tre variabili di input e utilizzante porte di OR risulta essere uguale a quella di fig. 3.4.1, dove le porte di AND sono sostituite con porte di OR.

Le funzioni booleane delle otto uscite sono:

$f_{0}\ =\ M_{0}\ =\ A+B+C\ \ \ \ \ \ \ \ \ f_{1}\ =\ M_{1}\ =\ A+B+{\bar {C}}$

$f_{2}\ =\ M_{2}\ =\ A+{\bar {B}}+C\ \ \ \ \ \ \ \ \ f_{3}\ =\ M_{3}\ =\ A+{\bar {B}}+{\bar {C}}$

$f_{4}\ =\ M_{4}\ ={\bar {A}}+B+C\ \ \ \ \ \ \ \ \ f_{5}\ =\ M_{5}\ ={\bar {A}}+B+{\bar {C}}$

$f_{6}\ =\ M_{6}\ ={\bar {A}}+{\bar {B}}+C\ \ \ \ \ \ \ \ \ f_{7}\ =\ M_{7}\ ={\bar {A}}+{\bar {B}}+{\bar {C}}$

La matrice di commutazione si può allora rappresentare nella forma logica:

Il numero di input per le porte OR risulta essere anche esso 2ⁿ

Matrici di commutazione ad albero

In figura 3.4.2 è rappresentata una matrice di commutazione ad albero costruita da circuiti AND e con quattro variabili booleane per input.

Vi sono quindi quattro coppie di input e 16 output.

Le equazioni booleane dei 16 output sono:

$f_{0}=[({\bar {A}}{\bar {B}}){\bar {C}}]{\bar {D}}\ \ \ f_{5}=[({\bar {A}}B){\bar {C}}]{\bar {D}}\ \ \ \ \ f_{10}=[(A{\bar {B}})C]{\bar {D}}$

$f_{1}=[({\bar {A}}{\bar {B}}){\bar {C}}]D\ \ \ f_{6}=[({\bar {A}}B)C]{\bar {D}}\ \ \ \ \ f_{11}=[(A{\bar {B}})C]D$

$f_{2}=[({\bar {A}}{\bar {B}})C]{\bar {D}}\ \ \ f_{7}=[({\bar {A}}B)C]D\ \ \ \ \ f_{12}=[(AB){\bar {C}}]{\bar {D}}\ \ \ \ (3.4.9)$

$f_{3}=[({\bar {A}}{\bar {B}})C]D\ \ \ f_{8}=[(A{\bar {B}}){\bar {C}}]{\bar {D}}\ \ \ \ \ f_{13}=[(AB){\bar {C}}]D$

$f_{4}=[({\bar {A}}B){\bar {C}}]{\bar {D}}\ \ \ f_{9}=[(A{\bar {B}}){\bar {C}}]D\ \ \ \ f_{14}=[(AB)C]{\bar {D}}\ \ \ f_{15}=[(AB)C]D$

Le precedenti equazioni booleane possono essere scritte in forma matriciale. In questo caso, la matrice booleana è a livello multiplo ed i diversi livelli vengono indicati dalle precedenti parentesi tonde e quadre.

Vedremo in seguito tali rappresentazioni matriciali.

La seguente (3.4.2) è la rappresentazione di una matrice di commutazione ad albero con circuiti AND.

Nelle equazioni (3.4.9), le parentesi tonde e quadre indicano anche la maniera di connettere i blocchi di AND di fig. 3.4.2.

Per n=2, sono necessari 2₃'input per gli AND-

Per n=3, sono richiesti per gli AND 2₃ + 2₄ inputs.

Per n coppie di variabili, è richiesto un numero N di inputs per ogni AND, dove N è dato da:

$N=\sum _{r=2}^{n}2^{r+1}$

Rispetto alla matrice rettangolare, la matrice ad albero richiede un minor numero di inputs di AND.

Funzioni booleane di matrici di matrici ad albero aventi blocchi di OR hanno espressioni simili a quelli di (3.4.9), in termini però di somme fondamentali e la loro realizzazione circuitale si ottiene da quella di fig. 3.4.2 sostituendo alle porte di AND quelle di OR.

In fig. 3.4.3 viene mostrata una matrice a doppio albero con porte di AND, quattro coppie di variabili di input e 2⁴ outputs.

Questa configurazione richiede un numero di input di AND'inferiore a quello delle configurazioni ad albero o rettangolari.

Le equazioni booleane dei 16 output del circuito sono:

$f_{0}=({\bar {A}}{\bar {B}})({\bar {C}}{\bar {D}})\ \ \ f_{5}=({\bar {A}}B)({\bar {C}}D)\ \ \ \ \ f_{10}=(A{\bar {B}})(C{\bar {D}})$

$f_{1}=({\bar {A}}{\bar {B}})({\bar {C}}D)\ \ \ f_{6}=({\bar {A}}B)(c{\bar {D}})\ \ \ \ \ \ f_{11}=(A{\bar {B}})(CD)$

$f_{2}=({\bar {A}}{\bar {B}})(C{\bar {D}})\ \ \ f_{7}=({\bar {A}}B)(CD)\ \ \ \ \ f_{12}=(AB)({\bar {C}}{\bar {D}})\ \ \ \ (3.4.10)$

$f_{3}=({\bar {A}}{\bar {B}})(CD)\ \ \ f_{8}=(A{\bar {B}})({\bar {C}}{\bar {D}})\ \ \ \ \ f_{13}=(AB)({\bar {C}}D)$

$f_{4}=({\bar {A}}B)({\bar {C}}{\bar {D}})\ \ \ f_{9}=(A{\bar {B}})({\bar {C}}D)\ \ \ \ \ f_{14}=(AB)({\bar {D}})\ \ \ \ f_{15}=(AB)(CD)$

Le funzioni precedenti possono essere scritte mediante una formulazione matriciale: la matrice booleana è anche in questo caso a livelli multipli.

Le parentesi delle equazioni (3.4.10) indicano il modo di connettere i blocchi di AND di fig. 3.4.3.

In figura 3.4.4 viene mostrato come si può realizzare una matrice con otto coppie di input e 256 output.

Gli otto input vengono divisi in due gruppi di quattro variabili ciascuno.

Se n non è multiplo di quattro, si può seguire lo stesso procedimento, solo che la configurazione risultante non sarà simmetrica.

Confronto tra i vari tipi di matrici

I tre tipi di matrici di commutazione (rettangolare, ad albero, a doppio albero) realizzano le stesse operazioni logiche ma richiedono un numero differente di input per le porte di AND (o di OR).

In tavola 3.4.5 vengono rappresentati i valori assunti dal numero di input per un n compreso tra 2 e 12.

Si noterà il rapido crescere degli input delle porte di AND in una matrice rettangolare, all'aumento di n.

In una matrice ad albero, ogni volta che l'input aumenta di una coppia, il numero richiesto di input diventa più del doppio mentre in una matrice a doppio albero il numero risulta minore del doppio.

Queste differenze diventano molto sensibili quando n è, per es., dell'ordine di 12.

Ma lo studio degli input delle porte di AND non è sufficiente per la scelta della particolare matrice di commutazione.

Un'altra considerazione da fare è quella relativa al numero di livelli che un segnale deve attraversare dall'input all'output.

In una matrice rettangolare, il segnale passa attraverso un solo livello; per una matrice ad albero, esso deve passare attraverso n-1 livelli.

In una matrice a doppio albero il segnale passa attraverso un livello per n=2, due livelli per n=3 e 4, tre livelli per n=5 fino a 8, e quattro livelli per n che va da 9 a 16.

Applicazioni delle matrici di commutazione

In figura 3.4.6 (Matrici di commutazione usate come decodificatori e codificat0ri) e 3.4.7 (Matrici di commutazione usate come selettori e distributori) sono illustrate alcune applicazioni delle matrici di commutazione.

In fig. 3.4.6 (a) appare un decodificatore.

Vi sono n coppie di input e 2ⁿ uscite. Come si vedrà nei capitoli seguenti, una porzione di una parola di istruzione di un calcolatore digitale costituisce un codice operativo ed il decodificatore utilizza tale codice per identificare l'istruzione da seguire e dare inizio alla sua esecuzione.

L'uscita di un decodificatore può essere inferiore a 2ⁿ terminali, se lo si desidera.

Una variante di un decodificatore può essere un traduttore che traduca, per esempio, un numero in codice binario decimale nella corrispondente cifra decimale.

In questo caso vi sono quattro coppie di input (nel caso di un codice a quattro bit) e 10 uscite che rappresentano le 10 cifre decimali.

In fig. 3.4.6(b) viene mostrato un codificatore: in esso vi sono 2ⁿ input e n coppie di output.

Per esempio, le ventisei lettere dell'alfabeto possono essere codificate mediante ventisei combinazioni di cinque variabili booleane.

In fig. 3.4.7.(a) viene mostrata una matrice di selezione . In questa matrice vi sono due gruppi di input e una uscita.

Un gruppo, costituito da 2ⁿ terminali di input, è connesso alla sorgente dei segnali, e l'altro grippo, costituito ds da n coppie di input, viene attivato da un codice selezionato.

In uscita, ad ogni istante, compare un solo segnale. Per esempio, una parola seriale può essere letta dal dispositivo di un canale selezionato su tamburo magnetico.

In questo caso le n coppie di input di fig. 3.4.7(a) rappresentano l'indirizzo del canale, i 2ⁿ input provengono dal dispositivo di lettura e l'output dà la parola letta.

Viceversa, un distributore, come da fig. 3.4.7(b), ha 2ⁿ uscite, un segnale sorgente ed n coppie di input.

Il segnale viene distribuito nelle varie uscite mediante una data combinazione delle n coppie di entrata.

Per esempio, una parola seriale che arriva da una sorgente di segnali viene distribuita al canale selezionato su tamburo magnetico.

Se le n coppie di fig. 3.4.6(a) provengono da un contatore binario che conteggia una sequenza di impulsi di orologio, il circuito risultante si dice commutatore (fig. 3.4.8):

In un commutatore, le uscite sono selezionate una dopo l'altra, secondo la sequenza degli stati del contatore.

Per esempio, un commutatore può essere usato per inviare segnali ai vari canali secondo una particolare sequenza temporale.

Le matrici possono essere anche usate come generatori di sequenza o come filtri di sequenze.

Esempi di matrici di commutazione

(.a)- Un Full-adder può essere considerato una matrice di commutazione: le equazioni 3.4.2 e 3.4.2, ne danno la rappresentazione booleane.

In fig. 3.4.9 compare il diagramma logico: la porzione di sinistra del circuito è costituito da una matrice rettangolare di porte di AND.

vi sono solo sette porte di AND in quanto nelle equazioni 3.4.1, 3.4.2, compaiono solo sette prodotti fondamnetali (sugli otto possibili determinati dalle tre variabili booleane).

Le linee orizzontali aggiuntive costituiscono gli input dei due circuiti OR i cui output sono S e C₀: la disposizione delle connessioni degli input per le porte OR corrisponde alla disposizione dei bit 1 e 0 delle righe nella matrice booleana B che compare in 3.4.3 per la rappresentazione matriciale del Full-adder.

La matrice rappresentativa di un Full-adder viene chiamata una AND-OR matrix.

Se la sintesi del circuito viene fatta partendo dalle operazioni 3.4.4, la matrice risultante viene chiamata OR-AND matrix (fig.4.4.10)

(.b)- La matrice rettangolare di fig. 3.4.11 è la sintesi della tabella della verità posta qui sul lato destro.

La matrice rappresenta un traduttore che converte un digit codificato nel codice binario 8.4.2.1, nel corrispondente digit decimale.

Poiché delle sedici combinazioni possibili dovute alle quattro variabili booleane solo le prime 10 vengono prese in considerazione, la matrice di fig. 3.4.11, è il diagramma logico delle matrici booleane seguenti

Analogamentesi possono costruire matrici di conversione relative ai codici tipo ad eccesso ditre. etc.

(.c)- Le matrici a) e b) sono rappresentate in forma booleana da matrici booleane di tipo elementare.

Volendo usare matrici a più livelli, si possono usare matrici booleane di forma non elementare.

Un circuito di confronto tra due numeri binari è anch'esso un circuito a più uscite: siano A e B le due parole binarie da confrontare. Il modo di operare del comparatore è descritto dalle seguenti equazioni booleane (supponendo che A e B siano costituite da tre bit ciascuna):

$f=f_{1}f_{2}f_{3}$

$f_{1}={\bar {A}}_{1}{\bar {B}}_{1}+A_{1}B_{1}$

$f_{2}={\bar {A}}_{2}{\bar {B}}_{2}+A_{2}B_{2}$

$f_{3}={\bar {A}}_{3}{\bar {B}}_{3}+A_{3}B_{3}$

Le funzioni f₁, f₂, f₃ diventano rispettivamente uguali ad 1 quando la prima, la secondas e la terza coppia di bit corrispondenti sono uguali e la funzione f diventa 1 quando le f₁, f₂, f₃ sono tutte uguali ad 1.

Le quattro funzioni possono essere scritte mediante la forma matriciale non elementare rappresentata a destra::

Questa funzione viene realizzata dalla matrice di fig. 3.4.12. Questa è una matrice AND-OR-AND con 21 input. Se la funzione ì viene scritta mediante prodotti fondamentali la corrispondente matrice rettangolare richiede 56 inputs.

Generatori di sequenze binarie

Per sequenza binaria si intende una sequenza temporale di bit 1 e 0., L'intervallo di tempo che intercorre tra due bit adiascenti viene chiamato bit time o digit time.

Un numero decimale codificato in BCD può essere rappresentato con diverse sequenze binarie. Per esempio, consideriamo il numero decimale 159. Nel codice 8.4.2.1 esso diventa 001,0101,10001.

In fig. 3.5.1 vengono fatti vedere quattro possibili modi di rappresentare questo numero.

In fig. 3.5.1(a), tutti i digits e i bits appaiono in una sequenza binaria. essa è una rappresentazione del tipo serial digit-serial bit.

Se i digit arrivano sequenzialmente mentre i bit sono in parallelo (fig. 3.5.1(b)), si ha una rappresentazione serial digit-parallel bits

In fig. 3.5.1(c) i digits sono in parallelo e i bits in serie: si ha quindi una rappresentazione parallel digit-serizal bits

In fig. 3.5.1(d) sia i bits che i digits sono in parallelo. avremo così una rappresentazione parallel digit.parallel bits.

In un calcolatore digitale lascelta della rappresentazione dipende da diverse considerazioni quali la velocità di calcolo, il numero dei componenti ect.

Una matrice di commutazione può essere considerata come un filtro di sequenza o un generatore di sequenza.

Se la matrice filtra secondo un certo criterio una sequenza di input, viene detta binary sequence filter: tali sono ad esempio il full adder ed il traduttore. Per ogni insieme di input viene prodotto come output un altro insieme di sequenze binarie.

Se viene considerato come input di una matrice solo una certa scelta di sequenze binarie e l'uscita è uconosciuta sequenza, si dice che la matrice è un binary sequence generator.

In fig. 3.5.2 viene mostrato un generatore di sequenze binarie: un contatore binario conteggia gli impulsi di un orologio: per ogni stato del contatore, la matrice produce un output costituito da un digit BCD

Quindi mentre un contatore binario conteggia, viene generato un numero decimale del tipo serial-digit parallel bit.

La matrice descritta in tav.3.5.3 permette di generare la costante π: l'output del contatore binario è rappresentato mediante le lettere A,B,C,D e l'output della matrice dalle lettere W,X,Y,Z.

Entrambi gli output sono espressi in numeri binari. il contenuto delle colonne W,X,Y,Z rappresenta il numero decimale 3141592653589793, dove si assume che la virgola sia posta tra i primi due bit più significativi.

Le quattro funzioni di output possono essere scritte partendo dalla tavola 3.5.3. Se queste funzioni vengono minimizzate, si ottiene la matrice booleana di tav.3.5.4.

La matrice booleana è in forma elementare: in fig. 3.5.5 compare un generatore della costante π sotto forma di AND-OR MATRIX.

Semplificazione delle matrici booleane

Nei paragrafi precedenti è stato mostrato come un circuito di commutazione con output multiplo può essere rappresentato mediante una matrice booleana d forma canonica, di forma elementare o non.

Nel seguito verranno riassunte le caratteristiche di una matrice booleana:

1. Ogni riga della matrice rappresenta una funzione booleana ovvero un output della matrice di commutazione.
   Il numero delle righe nella matrice non può essere ridotto a meno che una riga non sia composta da soli zeri oppure due o più righe siano identiche.
2. Ogni colonna della matrice rappresenta un prodotto (o una somma).
   Il numero delle colonne è riducibile e si deve cercare di renderlo minimo.
3. Se una riga della matrice consiste di tutti 0, la riga ed il suo output possono essere tolti dalla matrice.
4. Se una colonna nella matrice consiste di tutti 0, il termine corrispondente nella matrice [n] o [M] può essere eleminato.
5. Se vi è un solo 1 in ogni riga, la matrice di commutazione consiste di sole porte di AND (oppure di OR).
6. Se vi è più di un 1 in almeno una riga, la matrice di commutazione è una matrice AND-OR quando la matrice della funzione è della forma [m] oppure una matrice OR-AND se la matrice della funzione è della forma [M].
7. Quando un output di una matrice booleana, risulta essere una variabile di un prodotto (o di una somma) di un'altra rappresentazione matriciale, la risultante matrice di commutazione ha due o più livelli.

Con la semplificazione di una matrice booleana, si ottiene di conseguenza quella della matrice di commutazione risultante.

Il procedimento che si segue è quello di minimizzare le singole funzioni booleane con i soliti metodi.

Se la matrice data è in forma canonica e non può essere minimizzata e il numero di bit 1 è superiore a quelli 0, la matrice B booleana complementare risulta più semplice.

La semplificazione può essere ottenuta talvolta esprimendo la matrice in forma non elementare.

Generazione di segnali di controllo

Un calcolatore digitale opera per passi successivi e durante ogni passo viene eseguita una micro-istruzione. Esempi di micro-istruzioni sono gli schift, il conteggio, il trasferimento, la somma, l azzeramento, la complementazione. Una sequenza di micro-istruzioni costruita per raggiungere un determinato scopo costituisce una operazione.

Un calcolatore digitale è progettato per eseguire un certo insieme di operazioni. Queste operazioni son codificate mediante un certo numero di bits: specificando il codice operativo tramite i bits che fanno parte di una voce si può informare il calcolatore di eseguire la corrispondente operazione.Per le istruzioni semplici, ogni istruzione consiste in un codice operativo e in un indirizzo (vedere cap.IV parte II).

Il programmatore scrive una sequenza di istruzioni e questa costituisce un programma capace di risolvere un certo problema.

Quando un calcolatore riceve un'istruzione, il codice operativo contenuto in quest'ultima viene trasferito e memorizzato in un registro di operazioni. Sono necessari allora dei circuiti logici capaci di generare in corrispondenza al codice operativo dei segnali di controllo appropriati che comandano una sequenza di micro-operazioni.

La fig. 3.7.1 mostra una semplice configurazione per la generazione di segnali di controllo.

Essa è costituita da un registro, un decodificatore, un orologio, un distributore di livelli temporali, una matrice di controllo.

Supponiamo che in un calcolatore siano previste 16 operazioni e che queste siano codificate con un codice operativo a 4 bit. Siano f_i con i da 0... a 15.

Assumiamo che vi siano 10 micro-operazioni (con cui vengono formate 16 sequenze di micro operazioni rappresentative delle sedici operazioni) e che i segnali di controllo per queste micro-operazioni siano designate con m_j, j=0,...,9.

Il fine perseguito dal circuito di fig. 3.7.1 è quello di generare, per ogni codice operativo contenuto nel registro delle operazioni, una corrispondente sequenza di segnali di controllo di micro-operazioni.

Quando la parte del codice operativo di una istruzione viene memorizzata nell'Operation register, il decodificatore a 16 linee di uscita (ognuna per uno dei 16 codici operativi) attiva una e una sola linea.

Nello stesso istante, dei livelli temporali vengono generati mediante un orologio da un timing level generator.

Supponiamo che vi siano 5 linee di uscita del generatore di livelli ed indichiamole con t_k k=1,...,5: i livelli generati da tali linee vengono mostrati in fig. 3.7.2.

Questi livelli costituiscono una sequenza temporale chiamata ciclo temporale di base

Il numero di livelli in un ciclo base è scelto generalmente in modo da poter eseguire una istruzione (quindi controllare una sequenza di micro-operazioni).

Per certe istruzioni quali la moltiplicazione e la divisione spesso vengono usati più di un ciclo base e quindi viene aggiunto un contatore (che non figura in fig. 3.7.1) in modo da conteggiare il richiesto numero di cicli base. L'nput della matrice di controllo è costituito dalle 16 linee f_i, output del codificatore e dalle 5 linee t_k, outputs del generatore di livelli temporali.

La matrice ha 10 linee di uscita e il segnale di ciascuna di queste linee controlla una specifica micro-operazione.

Questi segnali sono rappresentati dalla lettera m_j Ogni mirco-operazione è realizzata DALLA COMBINAZIONE DEL SEGNALE DI CONGTROLLO E DA UN SEGNALE DI OROLOGIO.

Le funzioni relative alla matrice di controllo sono, per esempio, quelle del seguente sistema di equazioni logiche:

$m_{0}=(f_{3}t_{1}+f_{7}t_{3}+f_{9}t_{4})p$

$m_{1}=(f_{8}t_{1}+f_{4}t_{2}+f_{12}t_{5})p$

---------------

$m_{9}=(f_{11}t_{2}+f_{7}t_{4}+f_{15}t_{5})p$

dove p rappresenta il segnale dell'orologio. La prima equazione dice che la micro-operazione m₀ è controllata dal codice operativo al livello temporale t₁, o dal codice operativo f₇ al livello t₃, o dal codice operativo f₉ al livello t₄: la micro-operazione viene eseguita quando compare il segnale p dell'orologio. La matrice di controllo del sistema di equazioni logiche è essenzialmente una matrice di commutazione AND-OR.