Appunti riguardanti il corso di Architettura dei calcolatori elettronici

E

ovvero le coppie di vertici. Quindi rispettivamente:

{ } ( ) ⊆V

=

V 1,2 , … , n n∈ N ; E ×V ;

Di seguito è riportato un esempio sulla rappresentazione

grafica: 8

Il digrafo può anche essere rappresentato tramite la sua

G

matrice di adiacenza: .

( ) ( ) ∈

=1, =1⇔

A= A … ,n : A i, j E

i , j i , j

i , j

Nei digraf sono anche presenti dei gradi, che possono essere

di uscita o di entrata in un vertice. Si afferma quindi:

- Grado in Uscita (out-degree): rappresenta il numero di

rami distinti che originano in i

- Grado in Entrata (in-degree): rappresenta il numero di

rami distinti che incidono su i

Sono anche presenti dei cammini, che hanno una certa

lunghezza ed una sequenza determinata da di

+1

l

( ) ∈V

l i , … , i

l l+1

vertici distinti.

l+ l

Di seguito è rappresentato un esempio:

9

Il cammino è propenso a diventare un ciclo solo se risulta:

, i cammini di una stessa riga formano un ciclo.

( ) ∈

i ,i E

l+1 l

Inoltre un digrafo è connesso solo se per ogni coppia di vertici

esiste almeno un cammino che li unisce.

Di seguito alcune tipologie di graf e digraf.

I. Digrafi Hamiltoniani:

Un cammino (in questo caso ciclo) in un grafo è detto

Hamiltoniano se esso tocca tutti i vertici del grafo una

e una sola volta. Un esempio di Ciclo Hamiltoniano:

come è possibile notare, i vertici vengono attraversati

una sola volta dal cammino.

II. Digrafi Pesati: 10

Un digrafo si dice pesato solamente se è dotato di una

funzione (che sarebbe il peso) che associa valori

numerici reali ai rami di .

E

III. Grafi Non Orientati:

Un grafo non orientato (o non direzionato) è

defnito come un digrafo tranne per il fatto che i suoi

rami sono coppie non ordinate di vertici; comunemente

è interpretato come Digrafo Simmetrico.

IV. Sottografi:

Un sottografo è defnibile come un grafo ottenibile da

un altro considerandone solo alcuni spigoli e vertici e si

indica con la lettera (considerando il grafo

G' G

originale).

2.2 GLI ALBERI

Un albero (radicato) è un grafo non orientato, connesso,

aciclico che ha:

- Una radice al livello zero;

x

- Vertice al livello se e solo se esiste un cammino

i h ≥ 0

di lunghezza che origina in e termina in .

h x h

11

CAPITOLO 3: TEORIA DEI SEGNALI

3.1 SEGNALI ANALOGICI

Un segnale rappresenta una qualsiasi grandezza fsica che

varia nel tempo in maniera deterministica o aleatoria.

Tipicamente può essere un segnale acustico, un segnale

elettrico o un segnale elettromagnetico e si propaga

tipicamente in un mezzo trasmissivo che ne costituisce il

canale di propagazione o comunicazione e che può essere lo

spazio libero, un cavo o una struttura guidante.

Esistono essenzialmente due tipi di segnali: Analogico e

Digitale. I segnali analogici sono segnali che è possibile

trovare in natura ed hanno la particolarità di avere infniti

valori. I segnali digitali, invece, posseggono solo due valori: 0

e 1 (oppure On e Of), possono essere visti come dei “Segnali

Artifciali”. È possibile convertire un segnale dalla forma

analogica in quella digitale, il che lo vedremo più avanti.

I sistemi elettronici analogici elaborano segnali che variano

con continuità nel tempo, formalmente esprimibili attraverso

funzioni più che numerabili a valori reali.

12

Un tipico segnale sinusoidale, limitato tra un valore massimo

ed uno minimo (rispettivamente e ). Questo tipo di

−A

A

segnale è anche detto segnale periodico, poiché continua ad

intervalli regolari , chiamato anche periodo. I segnali

T

interessati nei sistemi di elaborazione subiscono normalmente

delle variazioni di potenziale elettrico. Questo viene

misurato su punti tipici rispetto alla massa. Come detto in

precedenza, i segnali analogici sono presenti in natura, ciò

implica, quindi, che è possibile convertire le varie grandezze

fsiche in segnali. In effetti è possibile attraverso dispositivi

specifci in grado di trasformare la percezione dei fenomeni

fsici in segnali elettrici: i trasduttori.

3.2 CONVERSIONE ANALOGICO-DIGITALE

3.2.1 FREQUENZA

La frequenza indica quante oscillazioni compie il segnale nel

periodo, signifca che possiamo considerarla come il reciproco

del periodo :

T

[ ]

1 1

=

f u . m. Hz=

T s

Solitamente si utilizzano i multipli e quindi si parla di e,

MHz

molto più comunemente, di . Al contrario, per il periodo si

GHz

13

utilizzano i sottomultipli, andando a parlare di millisecondi.

Vediamo un esempio:

Questo concetto è fondamentale per comprendere al meglio

Campionamento, Discretizzazione e la conversione

Analogico-Digitale.

Il Campionamento è il primo passo da effettuare per la

conversione del segnale; come ben sappiamo i segnali

analogici hanno infniti valori e sarebbe impensabile poterli

prendere tutti quanti, per questo si è deciso di campionare solo

alcuni valori ad istanti di tempo consecutivi ed equidistanti tra

loro.

Successivamente si passa alla Discretizzazione, serve

principalmente ad andare a defnire in modo più preciso il

segnale campionato, defnendo un’approssimazione del

segnale analogico. Ovviamente si procede con un elevato

Grado di Accuratezza, facendo decrescere il passo di

campionamento per andare a defnire le linee del segnale.

3.2.2 CODIFICA BINARIA

Quando si effettua la discretizzazione del segnale analogico,

notiamo che il segnale digitale inizia a prendere la forma di un

Segnale a Gradino, di conseguenza può essere convertito

ancora una volta, ma, questa volta, in stringhe di bit (si

prendono in considerazione solo i valori 0 e 1) secondo un

principio ben defnito: quando il nostro segnale assume valori

positivi si considera come valore 1 (ON), altrimenti si

considera il valore 0 (OFF). Di seguito vi è un esempio su un

segnale digitale per comprendere meglio il concetto.

14

Come è possibile notare, i livelli di tensione dei gradini sono

compresi tra una soglia massima (5 Volt) ed una minima (0

Volt). Questo intervallo è suddiviso a sua volta in altri due sotto

intervalli: ( )

min+max

{ }

[ ] [ ] in cui

si assumono gli intervalli V ,V e V ,V av=

min av av MAX 2

In logica positiva, nel primo sotto intervallo si considera il bit

0 mentre nel secondo corrisponde il valore 1. In logica

negativa, invece, si adotta la convenzione duale; ovvero

anziché assegnare il valore 1 alla tensione maggiore, a

quest’ultima viene assegnata il valore 0. In questo modo le

variazioni dei livelli di tensione sono esprimibili attraverso

stringhe di bit, che formano le onde a gradino. Questo è il

processo che avviene per effettuare la conversione da un

segnale analogico ad uno digitale a due soli valori, ovvero 0 ed

1.

Inoltre, un sistema che elabora segnali interpretabili in stringhe

binarie è in grado di distinguere due oggetti diversi, ovvero è in

grado di distinguere la combinazione tra due possibili stringhe

di bit. Come è stato possibile intuire, la capacità di codifca si

misura in bit o, preferibilmente, in byte; che non è

nientedimeno che un suo multiplo (1 byte = 8 bit).

15

Ovviamente da qui seguono altri multipli del byte:

CAPITOLO 4: ELABORAZIONE

COMBINATORIA

4.1 FUNZIONI BOOLEANE

Una funzione booleana associa parole (come stringhe o

sequenze) binarie a parole binarie. La funzione è defnita

fssando la lunghezza delle parole, dichiarando la legge

associativa tra gli elementi del dominio e del codominio.

Le funzioni elementari (o di base) sono:

16

- Il NOT, complemento di un bit

- L’AND, prodotto di due bit

- L’OR, somma di due bit

- Il NOR (o il NAND), complemento dell’OR

- Lo XOR, comma modulo due di due bit

Adesso vediamole più approfonditamente.

La porta logica NOT si effettua su una sola variabile. L’uscita

assume il valore logico opposto a quello applicato in ingresso.

Detta A la variabile di ingresso, la negazione si scrive:

Il prodotto logico AND si effettua su due o più variabili,

l’uscita assume lo stato logico 1 solo se tutte le variabili di

ingresso sono allo stato logico equivalente a 1. Nel caso di due

variabili di ingresso A e B, detta Y la variabile di uscita, si scrive

la funzione logica:

(e si legge A and B)

=

Y A∗B

La somma logica OR si effettua su due o più variabili, l’uscita

assume lo stato logico 1 se almeno una variabile di ingresso è

allo stato logico 1. Nel caso di due variabili di ingresso A e B,

detta Y la variabile di uscita, si scrive:

(e si legge A or B)

=

Y A+ B 17

La somma logica negata NOR si effettua su due o più

variabili, l’uscita assume lo stato logico 0 se almeno una

variabile di ingresso è allo stato logico 1. In tutti gli altri casi

. Corrisponde ad una OR con in cascata una NOT. Per due

=1

Y

variabili di ingresso A e B la funzione logica è:

(e si legge A nor B)

=

Y A+ B

Il prodotto logico negato NAND si effettua su due o più

variabili, l’uscita assume lo stato logico 0 se tutte le variabili di

ingresso sono allo stato logico 1. In tutti gli altri casi .

=1

Y

Corrisponde ad una AND con in cascata una NOT. La funzione

logica si scrive:

(e si legge A nand B)

=

Y A∗B

La porta logica XOR (o OR esclusivo) ha un meccanismo

davvero semplice: se rileva due bit uguali in ingresso (ad es. 1

1), ritorna come risultato 0; se i bit sono diversi (ad es. 0 1)

restituisce come risultato 1. Ovviamente vi è anche la

complementare di quest’ultima, ovvero la XNOR ma è molto

meno comune rispetto a quelle citate in precedenza.

4.2 I CIRCUITI

Gli elementi per la realizzazione delle operazioni sono i circuiti

combinatori. I circuiti combinatori di base sono associati alle

18

principali operazioni e sono identifcati dalle porte logiche

sopracitate.

Il seguente schema utilizza collegamenti in serie ed in parallelo

sfruttando 2 NOT, 3 AND ed una sola OR.

I circuiti si distinguono per la profondità (ossia il tempo di

calcolo), lo spazio e il costo. Il tutto è riducibile al numero di

porte che stiamo utilizzando. I circuiti danno come risultato

fnale un bit, ciò signifca che la nostra rete esegue delle

operazioni che sono, naturalmente, esprimibili in espressioni

formate da variabili binarie che sono defnite da:

n

- Un valore costante (0 oppure 1)

- Una variab