Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

&RGLILFD,QGLUHWWD

7 [ [ «[

DOIDEHWRRULJLQH

[ - . . /

0 - DEF DOIDEHWRLQWHUPHGLR

D E F % DOIDEHWRGHVWLQD]LRQH

! "# $

I l processo di codifica 132546 7 892::; < 8

19@ 1BA 1 9 C

76 =?>;

¾ Esempi di codici intermedi completi

2WWDOH 0 0 0 0

» 1 0 0 1

(VDGHFLPDOH

» 2 0 1 0

¾ 3 0 1 1

Esempio di codice intermedio incompleto 4 1 0 0

%&'

» d9e9d 5 1 0 1

fdVghVeNiFjVkmldVnl 6 1 1 0

W oVlpqgdVgne 7 1 1 1

XZY[\5] ^ DFEG5H I!JJ!K?L G J!I!H MNLO J

_ `_baF_c DR DS DT DFU DR DS DVT DU

I!H P QL I!H P QL

0 0000

1 0001 0 0 0 0 0 8 1 0 0 0

1 0 0 0 1 9 1 0 0 1

2 0010 2 0 0 1 0 A 1 0 1 0

3 0011 3 0 0 1 1 B 1 0 1 1

4 0100 4 0 1 0 0 C 1 1 0 0

5 0101 5 0 1 0 1 D 1 1 0 1

6 0 1 1 0 E 1 1 1 0

6 0110 7 0 1 1 1 F 1 1 1 1

7 0111

8 1000

9 1001 ! "# $

18

&RGLFL5LGRQGDQWL

8QFRGLFHDOXQJKH]]DILVVDOSHUODFRGLILFDGLXQGDWRGL

FDUGLQDOLWj1FRQXQDOIDEHWRFRGLFHGLFDUGLQDOLWjNVL

GLFHULGRQGDQWHVH

. !1

O

O!PFRQP. 1

&

8QDPLVXUDGHOODULGRQGDQ]Dq

U ± > ORJ 1 O@ >@

N

1 OPHQWUHWHQGHDGSHUOFKHWHQGHDG

UqXJXDOHDSHUORJ ˆ LQILQLWR

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

&RGLFL5LGRQGDQWL

&RGLFH&RPSOHWR

P

1 O 1RQ5LGRQGDQWH

. O P &RGLFH,Q&RPSOHWR

P

1

. ! 1

P O 1RQ5LGRQGDQWH

. O P &RGLFH,Q&RPSOHWR

P

1 O 5LGRQGDQWH

. O!P

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Rap presentazione d i Cod ici m ed iante tabelle

T = (x ,x ,… ,x ) alfabeto origine

1 2 n

E = (a ,a ,… ,a ) alfabeto destinazione

1 2 k

Es. Codice BCD (Binary Coded Decimal)

3 2 1 0

0 0 0 0

0 0 0 1

0 0 1 0

Parola Codice

0 0 1 1

Dato 0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Rap presentazione Decod ificata

¾ L’ insieme ha cardinalità N

¾ Le parole codice hanno lunghezza m = N

¾ Ad ogni parola codice è associato un solo bit 1

¾ Motivazioni rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Esem p io d i rapp resentazione Decod ificata

Dato Codice BDC Codice Decodificato

0 0000 1000000000

1 0001 0100000000

2 0010 0010000000

3 0011 0001000000

… … ….

9 1001 0000000001

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Transcodificatore

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Transcod ificatore

¾ In alcune circostanze si può verificare che lo stesso dato sia

rappresentato mediante codici diversi.

¾ Detti C1 e C2 due codici definiti sullo stesso insieme (cioè

costituito dallo stesso numero di parole codice), si dice

TRANSCODIFICATORE una macchina che consente di

associare a ciascuna parola del codice C1 la corrispondente

parola del codice C2.

» Transcodificatore per visualizzatore a 7 segmenti.

Transcodificatore C2

C1 rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Transcod ificatore p er visu alizzatore a 7 segm enti

¾ Uno degli indicatori visivi più comuni è l’LQGLFDWRUHDVHJPHQWL.

¾ Ogni simbolo è formato da sette segmenti ognuno dei quali è un

Led che può essere acceso da un segnale digitale.

%&'7R6HYHQ6HJPHQW'HFRGHU

¾ Un riceve in ingresso un

simbolo decimale in BCD e genera l’appropriata uscita

selezionando i segmenti che devono essere accesi per mostrare su

display il simbolo decimale.

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Transcod ificatore p er visu alizzatore a 7 segm enti

¾ Le 7 uscite le

indichiamo con

(a,b,c,d,e,f,g)

selezionando i

corrispondenti

segmenti. Si hanno:

LQSXW:

» A B C D.

RXWSXW:

» a b c d e f g.

¾ La tabella di verità

sarà pertanto rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Decoder ed Encoder

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Decod ificatore (d ecod er)

¾ Un decodificatore è una macchina che riceve in

ingresso una parola codice (C) e presenta in uscita la

sua rappresentazione decodificata (linee U , … U )

0 N-1

U

0

C o

C m-1 U

N-1

α

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Sintesi d ella trascod ifica d a binario a 1 su N

Abbiamo un insieme sorgente di 4 elementi. Sono necessari 2 bit

(A,B) per codificarlo. Nella rappresentazione decodificata servono

invece 4 bit (U U U U ).

0 1 2 3

8 % $

‰

(VHPSLR7UDQVFRGLILFD

8 % $

Š

% $ 8 8 8 8

8 % $

‰ Š ‹ Œ ‹

Š

8 % $

‹ Œ

Œ

 $

%

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Il circu ito integrato DECODER

8 Ž 61

8  06, 8

8 Ž

 8 

8 (1 8

‘

(1 

$ 8 ‘

$ %

%

4XDQGR(1 VHJQDOHGLDELOLWD]LRQH YDOHO¶XVFLWDLOFXLSHGLFHLQ

GHFLPDOHFRUULVSRQGHDOQXPHURELQDULRLQLQJUHVVR

A bit di minor peso

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Decod ificatore binario (1/ 2)

'HFRGHU %LQDULR

¾ P

» ingressi binari su cui è inviata la parola codice,

RS]LRQDOH

α

» ingresso di abilitazione

Q

» uscite (n”2 )

m Q-1 )L 7$%L

IRUL GR α

:= 0 .. := AND (C = )

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

Decod ificatore binario (2/ 2)

'HFRGHU %LQDULR &RPSOHWR

¾ » n=2 m

) 3 ) 3 ) 3

» ’ ’ “ “ ” •?“ ” •?“

(TXD]LRQH

» D‡ 3 L > @

) ” DWW

– –

» è indipendente dal particolare codice da decodificare

'HFRGHU%LQDULR,QFRPSOHWR

¾ » n<2 m

» Si pone n’ =2 e si realizza la rete come sottorete della rete

m

completa

» è dipendente dal particolare codice da decodificare

rs turv w x y z v {|} z ~vs } € ~y {x z v  x|tv ‚ z |{v ‚ z v  xuƒ }v „!|y ‚ v z v†xw ~‡ v

33

Decod ificatore incom p leto

¾ Decoder ad hoc per il codice 8-4-2-1 & &

Å Æ b

¿ ¿À¿ Á¶ÁÁ¶Á¿

& &

à  ­ ¯

® ­ °²±³­ ´

) & & & & ) & & && ) & & & Â Â

= = =

; ; ;

0 3 2 1 0 1 3 2 1 0 2 2 1 0 ­µ¶­·¸±³­ ¹

) & & ) & & & ) & & ÂÄÃ

= = =

C ; ; C ;

3 2 1 0 4 2 1 0 5 2 1 0 ­ º¯­ »²±¼±

ÃÃ

) & & & ) & && ) & & ) & &

= = = =

; ; ; ­ ½¯­ ¾²±¼±

6 2 1 0 7 2 1 0 8 3 0 9 3 0 ÃÂ

DQGuguale

La rete così ottenuta ha un numero di porte alla rete

realizzata come sottorete di rete completa, ma non tutte le sue

&Linferiore.

porte sono a 4 ingressi e quindi è di costo

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

34

Decod ificatori com p osti

¾ Più decoder possono essere composti…

» Semiselezione (4/16) (VGHFRGLILFDWRUL

GLPHWjDPSLH]]D

XVFLWH

SRUWD$1'SHU

FLDVFXQDGHOOHXVFLWH

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

35

Decod ificatori com p osti

» Schema ad albero E’ possibile realizzare un decoder di

• n uscite (Es. 16)

• log n ingressi (Es. 4)

2

attraverso decoder a

• m uscite (Es. 4)

• log m ingressi (Es. 2)

2

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

36

Com p osizione m od u lare d i Decod er 4:16

8 8

Ž Ž

8 8

'(&  

8 8

 

8 8

‘ ‘

8 8

Ž Ç

8

'(& 8

8  È

Ž 8

8

8 

'(& É

 8 8

8 ‘

& Ê

 8

8 Ž 8

' ‘ Ë

8

'(&  8 Ì

8

 8 Ž

8 ‘ 8 

8 8

Ž 

8

'(& 8

 ‘

8

$ 8

 Ç

8

% 8

‘ È

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

Esem p io (sem p lificato) d i u tilizzo d i Decod er (1/ 2)

,GHFRGHUVRQRXWLOL]]DWLLQPROWLVVLPHDSSOLFD]LRQL

• 8QHVHPSLRqODVHOH]LRQHGHOO LQSXWRXWSXWGDSDUWHGHO

SURFHVVRUH

2JQLSRUWDGL,2SRVVLHGHXQLQGLUL]]R XQLYRFR

• 4XDQGRLOSURFHVVRUHYXROHFRPXQLFDUHFRQXQDGHWHUPLQDWD

SHULIHULFDHVVRSURGXFHLOFRGLFHGHOO LQGLUL]]RGHOODSRUWDGL,2DO

TXDOHODSHULIHULFDqFRQQHVVD

/ LQGLUL]]R ELQDULR GHOODSRUWDqIRUQLWRLQLQSXWDOGHFRGHULO

TXDOHDWWUDYHUVRLOVXRRXWSXWDELOLWDODFRUULVSRQGHQWHSRUWDGL,2

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

Esem p io (sem p lificato) d i u tilizzo d i Decod er (2/ 2)

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

Cod ificatore (Encod er)

¾ Un codificatore è una macchina che riceve in ingresso una

rappresentazione decodificata (linee U , … U ) e fornisce in

0 N-1

uscita la parola codice associata a U se U =1 (più in generale se

i i

è attivo). U

0 C o

C m-1

U

N-1 α

—˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

Ret i di codifica ( codificat ori) ( 1/ 3)

¾ Rete di codifica binaria

Qingressi

» (ciascuno associato ad uno degli oggetti da codificare),

Puscite

» binarie (sulle quali è rappresentata la parola codice)

α

» un ingresso di abilitazione (opzionale).

Sche

» un'

uscita ausiliaria segnala la condizione "assenza di informazione da

codificatore“(opzionale). FRGLFHBGHFRGLILFDWR; FRGLFH);

PDFFKLQDFRGLILFDWRUH YDU&

() : :

EHJLQ Ï − 1

Ö Õ ÎÑÐÒÔÓ Î

=

: and

Î = 0

HQG × − 1

& ) 7$% M Q 7$%

= • = =

1... {0,1}

Ø Ù Ù Ø Ù Ø

Ù = 0

& ) L 7$%

= ∀ =

: 1

Ú Û Û Ú

Û

Í Il comportamento di una rete è descritto da una tabella in cui ad ogni ingresso si associa la

parola codice che lo rappresenta —˜ ™š—› œ  ž Ÿ › ¡¢ Ÿ £¤›˜ ¢ ¥ £ž  Ÿ › ¦ ¡™› § Ÿ ¡ › § Ÿ › ¦ š¨ ¢› ©!¡ž § › Ÿ ª¤›«œ £¬ ›

Reti d i cod ifica (cod ificatori) (2/ 3)

» Condizione di vincolo sugli ingressi

) ) L M

• = ≠

ô 0 per

M ò ,QJUHVVLDWWLYL

− 1

» Uscita p S )

= ó ÷ ø ø

∑ ∏

õ ö ö

= =

ó ö ö

= 1

ÜÝ ÞßÜà á â ã ä à åæç ä èéàÝ ç ê èã åâ ä à ë âæÞà ì ä æåà ì ä à ë âßí çà î!æã ì à ä ïéàðâá èñ à

42

Ret i di codifica ( codificat ori) ( 3/ 3) & 2 ' , & ( ' ( & , 0 $ / ,

F LI U D

¾ Codificatore 8-4-2-1

& ) ) 0 0000

= +

(8) ; 1 0001

3 8 9

& ) ) ) ) 2 0010

= + + +

(4) ;

2 4 5 6 7 3 0011

& ) ) ) )

= + + +

(2) ; 4 0100

1 2 3 6 7 5 0101

& ) ) ) ) )

= + + + +

(1) 6 0110

0 1 3 5 7 9 7 0111

8 1000

9 1001

ÜÝ ÞßÜà á â ã ä à åæç ä èéàÝ ç ê èã åâ ä à ë âæÞà ì ä æåà ì ä à ë âßí çà î!æã ì à ä ïéàðâá èñ à

Reti d i cod ifica a p riorità

‰ Un codificatore può essere preceduto da una “rete a priorità” che, in caso di più

ingressi contemporaneamente alti, filtra quello con priorità assegnata maggiore

) ;

=

ù Rete a priorità 1 1

Qingressi ;

» ú ) ; ;

Quscite ) =

» corrispondenti , che rappresentano

ú 2 2 1

gli ingressi del codificatore

» fra gli ingressi è definita una priorità, ad

esempio: ) ; ; ;

=

♦ per fissare le idee

©; ; L< Mª ý ý ý

û ü

è prioritario su se −

1 1

< ;

» L'

uscita è alta se e solo se è alto e tutti gli

ú ú

;

altri ingressi prioritari su sono bassi.

ú 44

CONTROLLO DI ERRORE

ÜÝ ÞßÜà á â ã ä à åæç ä èéàÝ ç ê èã åâ ä à ë âæÞà ì ä æåà ì ä à ë âßí çà î!æã ì à ä ïéàðâá èñ à

Controllo d i errori - 1

%LWGLSDULWjHFRQWUROOR

þ Nella trasmissione o nella memorizzazione di un’ informazione la “perdita” di un bit

(trasformazione da 0 a 1 o viceversa) è la più diffusa causa di errore

þ Le reti di parità/disparità si usano per effettuare un semplice controllo di errore

þ In fase d trasmissione (o memorizzazione) si aggiunge un bit tale che il numero

GLSDULWj

complessivo di bit “1” sia a parità assegnata (p.e. pari)- Il bit si dice

þ In fase di ricezione (o lettura) una rete di parità (o disparità) controlla la parità e, se diversa

da quella assegnata, segnala l’ errore, ponendo ad esempio ad 1 un segnale di controllo err

ed avendosi dunque:

Æ

HUU &(57(==$

» della sua presenza

Æ

HUU 352%$%,/,7$¶

» di assenza di errori

þ Il sistema si basa sulla massimizzazione di questa probabilità

ÜÝ ÞßÜà á â ã ä à åæç ä èéàÝ ç ê èã åâ ä à ë âæÞà ì ä æåà ì ä à ë âßí çà î!æã ì à ä ïéàðâá èñ à

46

Controllo d i errori - 3

'LVSDULWj H FRQWUROOR GL HUURUH

ƒ In partenza (o in scrittura), d(X) calcola il bit di parità

ƒ In arrivo (o lettura), d(X) calcola il segnale err

ƒ Si ricorda:

ƒ HUU o SUREDELOPHQWHq;¶ ;

ƒ HUU FHUWDPHQWHq;¶;

o

$ %'&( )+*,,*'-.0/210** 33 *2)+*5476 849%'*2)+/210:;+6 *2))+&)+*=<3+>;,? (@?+%'-)? ( AB C ( )+- 3 /2>)? -DE&=F>0* 3+( &G/- 3 &H%'*2)

3+? /2>)+* II -*3 *2D=%J; ? /2? ( ALK ÿ ÿ !"#

47

Rilevazione d egli errori

¾ Natura degli errori

¾ Codici ridondanti

¾ Rilevazione e correzione degli errori

¾ Esempio:

» Bit di parità: si aggiunge un bit in modo che il numero di 1 sia

pari: →

00101101 00101101 0

01101000 01101000 1

» L’ errore su un bit viene rilevato (non corretto)

011010001 011000001

ÿ ÿ !"#

Rilevazione e Correzione d egli errori

¾ Rilevazione (mediante bit di parità) e correzione

mediante aggiunta di informazioni ridondanti (bit di

parità + checksum)

&KHFN6XP %LWGLSDULWj

ÿ ÿ !"#

Controllo d i errori - 2

,ULIHULPHQWLWHRULFL± GLVWDQ]DGL+DPPLQJ

¾ L’ informazione da trasmettere o memorizzare è un “ codice a

lunghezza fissa” '

'LVWDQ]DGL+DPPLQJ

¾ numero di bit diversi tra due parole codice

'LVWDQ]D PLQLPD

• di un codice: la distanza minima fra 2 sue parole-codiice

6LQGURPH GL HUURUH:

• la parola-codice non appartiene al codice

ÿ ÿ !"#

50

Controllo d i errori - 3

ƒ ,ULIHULPHQWLWHRULFL7HRUHPDGL+DPPLQJ

ƒ Un codice a distanza minima

d+1 può individuare gli errori simultanei su d bit;

2c+1 può correggere gli errori simultanei su c bit.

ÿ ÿ !"#

51

Multiplexer e Demultiplexer

ÿ ÿ !"#

Mu ltip lexer lineare

0XOWLSOH[HUOLQHDUH $

¾ Un ML) è una %

macchina con: 08;/

» n ingressi-dati (A ,… ,A )

0 n-1

» n segnali binari di selezione ( ,… , ),

0 n-1 $

GHLTXDOLDOSLXQRqDWWLYR Q

» una uscita-dati B, che assume

♦ valore A se è attivo

i i

♦ neutro se nessuna delle selezioni è D D

attiva Q

¾ E’ una macchina che viene utilizzata

quando più linee devono essere

convogliate verso un’ unica linea di

uscita (bus) ÿ ÿ !"#

Mu ltip lexer binario

¾ Se i dati A e B sono quelli

i $ %

che viaggiano su un bus … 08;/

» si parla di multiplexer o

demultiplexer

¾ $

Se i dati A e B sono

i Q

semplici bit …

» si parla di multiplexer o

demultiplexer binario D D

Q

ÿ ÿ !"#

Mu ltip lexer com p osti

¾ Realizzazione di un MUX16 attraverso MUX4

Un MUX16 può essere

realizzato attraverso 5

MUX4.

Due degli ingressi di

selezione consentono di

scegliere il mux da leggere

mentre gli altri 2

consentono di selezionare

l’ ingresso per ciascun mux.

ÿ ÿ !"#

55

Mu ltip lexer Ind irizzabile

¾ E’ un Multiplexer Lineare i cui segnali di abilitazione

sono collegati con le uscite di un decodificatore

A

0 MUX B

A

N-1 α α

0 N-1

C

ÿ ÿ !"#

Dem u ltip lexer lineare

'HPXOWLSOH[HU/LQHDUH

¾ Un (DL) è una

macchina con:

» 1 ingresso-dati B $

» n segnali binari di selezione ( ,… , ),

0 n-1

dei quali al più uno è attivo % '08;/

» n uscite-dati (A ,… ,A ), con $

0 n-1

♦ A =B se è attivo Q

i

i

♦ neutro se nessuna delle selezioni è

attiva D D

Q

ÿ ÿ !"#

Dem u ltip lexer Ind irizzabile

• E’ un Demultiplexer Lineare i cui segnali di abilitazione

sono collegati con le uscite di un decodificatore

A

0

B DEMUX A

N-1

α α

0 N-1

C

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

COMPARATORI

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

Com p aratore

¾ Spesso accade che occorra confrontare due dati A e B in

quanto l'

unità di controllo dell'

architettura deve proseguire

con algoritmi differenti a seconda che i due dati siano eguali o

diversi.

,OFRPSDUDWRUHqXQDPDFFKLQDFKHKDLQLQJUHVVRGXHGDWL

¾ $% HGLQXVFLWDXQVHJQDOHERROHDQRHTFKHqVHq$ %

A eq

Comparatore

B MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

Com p aratori

(JXDJOLDQ]DELWDELWLQSDUDOOHOR

c Confronto tra due stringhe di bit (parole-codice o numeri)

6ROX]LRQHSDUDOOHOD

• per n bit, n porte EQ ed una AND ad n ingressi

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

61

COMPARATORI BIT-SERIALE (p er u n singolo bit)

¾ Per A = B la tabella della verità è:

n n

¾ Con il pedice n si vuole distinguere l'

n-esimo bit in una parola o numero

presentato con più bit in serie nel tempo. Da cui:

¾ Cioè E è alto quando A e B sono uguali. Mentre A è minore di B se

n n n n n

, viceversa A è maggiore di B se .

n n

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

COMPARATORI BIT-SERIALE (p er u n singolo bit)

¾ Il circuito comparatore per il singolo bit-serie nel suo insieme ha tre

uscite ed è schematizzato come in figura:

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

Com p aratore binario

EHJLQ

HJRXW: ;= < AND HJLQ;

=

PDJRXW: ;> < OR ;= < AND PDJLQ;

=

PLQRXW: ;< < OR ;= < AND PLQLQ

=

HQG; MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

64

Com p aratore binario HJRXW

¾ Deriviamo l’ espressione di

» partiamo dall’ eguaglianza X=Y:

g

d g

− −

1

1 1

; < ; <

; < ; < ∑

∏ = ⊕ = ⊕

= = ≡ ( ) ( )

( ) ( ) f f f f

e e f

f

e =

=

= 0

0

0 ricordiamo che la XOR è il complemento della EQ

¡ applicando De Morgan si ricavano due possibili espressioni:

 

h

k −

1

 

− ≡ ⋅

1  

HJRXW ; < HJLQ

∏ ( )

HJRXW ; < HJLQ

∑ =

= ⊕ + :

: ( ) i i

 

j j  

 

j =  

0 i

 

= 0

MN OPMQ RS T U Q VWX U YZQN X [ YT VSU Q \ SWOQ ] U WVQ ] U Q \ SP^ XQ _ WT ] Q U `ZQaSRYb Q

65

Com p aratore binario DQGRU QDQG non

¾ La realizzazione in logica a due livelli è

conveniente <)

¾ La funzione (; non presenta mintermini adiacenti

¾ Es.: ; ‚2‚ƒ‚ „ „„ „‚

< 0DSSDGL.DUQDXJKSHU

†† I ; < FRQ; H< LQJUHVVLGLGXHYDULDELOL

†+‡ FLDVFXQR

‡‡

‡† lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

66

Com p aratore binario

PDJRXW

ˆ Deriviamo l’ espressione di

ˆ Osserviamo che, per le singole cifre binarie, si ha

; < ; <

> ⇔ ⋅ = 1

Š Š Š Š

ˆ Quindi, per ottenere il confronto tra ingressi a più cifre è possibile “ partire”

confrontando le cifre da sinistra e procedendo via via verso destra fino a trovare

eventuali differenze ⋅

PDJRXW ; <

Q

= +

: ‰ −

1

1 ⋅ ⋅

; < ; <

Q

≡ +

( ) ( )

‰ ‰ ‰ − 2

− − −

1 1 2

⋅ ⋅ ⋅ ⋅ ⋅

; < ; < ; < ; < PDJLQ

...

≡ ≡ + =

( ) ( ) ( )

‰ ‰ 0

− −

1 1 1 1 0

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

67

Com p aratore binario PLQRXW,

¾ Per ottenere la terza uscita se necessaria, si può

PDJRXW

procedere analogamente a oppure semplicemente

osservare che HJRXW PDJRXW

=

minout : •

; <

¾ Si noti che la componente è ripetuta nelle tre

L L

funzioni e può essere calcolata una sola volta

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

68

Com p aratore binario N

¾ Un confronto tra stringhe di bit può essere effettuato con

N”Q ; <

un unico comparatore se (numero di bit di e

LQJUHVVLGHOFRPSDUDWRUH

¾ Altrimenti, possono essere collegati in catena {[NQ]}

comparatori, come in figura

k

; < ; < ; <

Q Q Q

HJLQ HJRXW

PDJLQ PDJRXW

PLQLQ PLQRXW

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

69 Adder

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

H alf Ad d er

ˆ Scrivere la tabella di verità relativa alla somma di due addendi. Riportare sia l’ uscita somma

che quella riporto. Disegnare anche il circuito equivalente.

‹ lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

Fu ll Ad d er (1/ 2)

ˆ Scrivere la tabella di verità relativa alla somma di due addendi più il riporto entrante.

Riportare sia l’ uscita somma che quella riporto. U

U

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

Fu ll Ad d er (2/ 2)

Le uscite valgono quindi:

5 ; <U ; < U ;< U ;<U ;< <U ;U

= + + + = + +

Œ

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

Ad d izionatore binario D† E

¾ E’ possibile isolare il fattore

¾ Rielaborando le precedenti espressioni è quindi possibile

ottenere le seguenti espressioni per l’ addizionatore

completo:

6 D E U + U

= ⊕ ⊕ = ⊕

( )

5 DE U D E * U+

= + ⊕ = +

( )

lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

75

Ad d izionatore binario

¾ Pertanto, un addizionatore completo può essere ottenuto a

partire da due semiaddizionatori:

6 D E U + U

= ⊕ ⊕ = ⊕

( )

5 DE U D E * U+

= + ⊕ = +

( )

* DÂ E *+ÂU

D +$

E + D† E + U

+$ D† E† U

U lm nolp qr s t p uvw t xypm w z xs urt p { rvnp | t vup | t p { ro} wp ~ vs | p t yp€rqx p

76

Ad d izionatore binario: il rip orto

¾ Le diverse componenti dell’ espressione ottenuta per

l’ addizionatore binario assumono un significato

particolare:

* DÂE ULSRUWRJHQHUDWR”

» “ : indica la creazione di un

riporto all’ interno dell’ addizionatore binario

3 + D†E ULSRUWRSURSDJDWR”

» “ : indica se, in

presenza di un riporto in ingresso, lo stesso verrò

propagato in uscita

» Il riporto in uscita può quindi essere espresso come

5 *3U Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

77

Ad d izionatore binario: conclu sione

¾ Addizionatore completo (full-adder)

» ha il riporto entrante

¾ Semi-addizionatore (half-adder)

» non include il riporto entrante

a b a b

£

R r G H

H

S Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

78

Sottrattore binario 6 5 ;± <

¤ ¤

Sh Rh

X Y

0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0

X Y r S R

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0 65 ;± <± U

1 1 1 1 1

Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

79

Sottrattore binario

¾ Per ottenere la sottrazione può essere ripetuto lo stesso

procedimento usato per definire la struttura degli

addizionatori

¾ Per il semisottrattore si avrà:

6 ; < ; < ; <

= + = ⊕

¥

5 ; <

=

¦

‰Per il sottrattore completo :

6 ; < U ; < U ; < U ;<U ; < U

= + + + = ⊕ ⊕

5 ; < U ; < U ; <U ;<U ; < ; U <U

= + + + = + +

Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

80

Ad d izionatore binario

¾ Per il semiaddizionatore valgono le eguaglianze

+ D E G D E D E D

E

= ⊕ = = +

( , )

* D E

=

¾ Similmente per l’ addizionatore completo valgono le

eguaglianze

6 D E U G D E U D E

U D

E U D E U DEU

= ⊕ ⊕ = = + + +

( , , )

5 D

EU D E

U DE U DEU DE EU DU DE U D E

= + + + = + + = + +

( )

Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

81

Sottrattore binario

¾ Un sottrattore può essere ottenuto a partire da un

addizionatore negando opportunamente alcuni ingressi ed

uscite, come mostrato in figura

¾ Provatelo come esercizio.

X Y X Y

§ r

R G H

H

S Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

82

Ad d izionatori binari

‰Ulteriori condizioni di interesse:

QRQULSRUWR

QRQ

Q U

=

L L Indica assenza di riporto in ingresso

5LSRUWR³NLOOHG´

. D E

= ⋅

¨ ¨ ¨ Indica che, indipendentemente dalla presenza

di un riporto entrante, il riporto in uscita sarà

comunque zero

1 . 3 Q 3URSDJD]LRQHGHOQRQULSRUWR

3URSDJD]LRQHGHOQRQ

= + ⋅

© © © © Indica assenza di riporto in uscita

Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

83

Ad d izionatori seriali

¾ Usa un unico addizionatore operante sulla singola cifra

¾ Opera in momenti successivi su cifre diverse degli addendi

¾ Richiede un blocco “ con memoria”

¾ E’ lento rispetto ad addizionatori che lavorano in parallelo sulle

diverse cifre degli addendi X Y

i i

r i Add -

∆ mod - b

S

R i

i

Ž ‘ ’“ ” • ‘ –—˜ • ™š‘Ž ˜ › ™” –“• ‘ œ “—‘  • —–‘  • ‘ œ “ž ˜‘ Ÿ —”  ‘ • š‘¡“’™¢ ‘

84

Ad d izionatori p aralleli

¾ Opera sulle cifre degli addendi in parallelo

¾ … anche se il riporto deve propagarsi attraverso l’ intera struttura

¾ Richiede un numero maggiore di risorse rispetto all’ addizionatore

seriale

X Y X Y X Y

n-1 n-1 1 1 0 0

R r r R =c

n -1 2 1 0

Add - Add - Add -

mod -b mod -b mod -b

R R R

n -2 1 0

S S

C= R S

n-1 1

n -1 0

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

85

Ad d izionatori p aralleli Q

¾ Gli addizionatori ottenuti collegando in catena addizionatori di cifra

sono anche chiamati addizionatori a propagazione del riporto (FDUU\

ULSSOH FDUU\SURSDJDWH)

o

¾ H = tempo di risposta di uno stadio

JHQHUDWR XFFLVR SURSDJDWR

¾ Allo stadio i, il riporto uscente o è o è o è

/LPLWHLQIHULRUHH

¾ Tempo di ritardo complessivo: (in tutti gli stadi il

riporto è generato o ucciso) /LPLWHVXSHULRUHQH

¾ Tempo di ritardo complessivo: (un riporto

entrante nel primo stadio che è propagato in tutti gli stadi)

N Q), N

¾ ε ≤

Tempo di ritardo complessivo = (N dove è la

più lunga catena di condizioni di propagazione.

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

86

Ad d izionatori con anticip o d el rip orto

FDUU\ORRNDKHDG

¾ Normalmente chiamati addizionatori

L, N esimo NM U

¾ Per ogni stadio dal al -esimo, si ottiene

À

direttamente dai bit degli addendi X ed Y e dal riporto entrante

5

nella catena (invece che dal riporto uscente )

À ÁLÂ

U * U 3

= +

Ä Ä Ä Ä

+ 1

U * * 3 U 3 3

= + +

Ä Ä Ä Ä Ä Ä Ä

+ + + +

2 1 1 1

.......... .......... .......... ...

U * * 3 * 3 3 U 3 3 3

= + + + +

... ... ...

Ä Ä Ä Ä Ä Ä Ä Ä Ä Ä Ä

à à à à à Ã

+ + − + − + − + + − + + −

1 2 1 1 1 1 1

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

90

Ad d izionatori carry lookahead

U * * 3 * 3 3 U 3 3 3

= + + + +

... ... ...

Æ Æ Æ Æ Æ Æ Æ Æ Æ Æ Æ

Å Å Å Å Å Å

+ + − + − + − + + − + + −

1 2 1 1 1 1 1

U qDOWRVHqYHULILFDWDOD

ÈÉÊ

FRQGL]LRQHGLJHQHUD]LRQH «RSSXUH qSDULDOULSRUWR

QHOO¶XOWLPRVWDGLR HQWUDQWHU VHTXHVWRYLHQH

ËÍÌ Ç

SURSDJDWRLQWXWWLJOLVWDGL

ËÍÌ

«RSSXUH VHqYHULILFDWDOD

FRQGL]LRQHGLJHQHUD]LRQH* HVH

Ç

TXHVWDYLHQHSURSDJDWDGDJOLVWDGL

GDO N HVLPRILQRDOO¶XOWLPR

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

91

Ad d izionatori carry lookahead

¾ L’ espressione precedente può essere realizzata nella

maniera riportata in figura

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

92

Ad d izionatori carry lookahead

¾ L’ idea di base negli addizionatori carry lookahead è quella di

U

U ed separatamente per ogni gruppo di

calcolare la relazione tra Î ÎÏ Ð

N…

cifre .NM

¾ Una rete a livello superiore valuta la propagazione del carry tra

JUXSSLdi cifre

¾ Ad esempio, per un adder a 64 bit suddiviso in blocchi di quattro

ORRN´

cifre (bit), la parte di “ lungo cui si propaga il riporto è lunga

64/4=16 stadi Adder 4-7 Adder 0-3

Adder 60-63 G -G G -G

r -r r -r

G -G

r -r 4 7 0 3

4 7 0 3

60 63

60 63 P -P P -P

P -P 4 7 0 3

60 63 r =R

R r =R

8 7

63 4 3

r Look 4-7 Look 0-3

Look 60-63 60 EORFFKL

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

93

Ad d izionatori carry lookahead

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

94

Ad d izionatori carry lookahead

¾ La rete di lookahead può a sua volta essere realizzata a più livelli,

secondo lo stesso principio visto prima

Adder 4-7 Adder 0-3

Adder 12-15 G -G G -G

r -r r -r

G -G

r -r 4 7 0 3

4 7 0 3

12 15

12 15 P -P P -P

P -P 4 7 0 3

12 15 Look 4-7 Look 0-3

Look 12-15

G P r r G P r r

G P

12,15 12,15 12 8 4,7 4,7 4 0

0,3 0,3

R 15 r

Look di 2° livello (0-3)-(12-15) 0

G P

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

95

Ad d izionatore Carry Skip

¾ Valuta localmente la condizione di propagazione e generazione

del carry

¾ In caso di propagazione “ aggira” (skip) la condizione di

generazione

¾ Aggiunge dei multiplexer al cammino critico

A B A B A B A B

16:13 16:13 12:9 12:9 8:5 8:5 4:1 4:1

P P P P

16:13 12:9 8:5 4:1

1 1 1 1

C C C

C 12 8 4 C

out in

0 + 0 + 0 + 0 +

S S S S

16:13 12:9 8:5 4:1

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

96

Ad d izionatore Carry Skip

¾ Cammino critico

Bit 0–3 Bit 4–7 Bit 8–11 Bit 12–15

Ò ÓÔ Õ Ö× Ò ÙÚ×Û ÓÓ

Setup Setup Setup Setup

Carry Carry Carry Carry

propagation propagation propagation propagation

Ò ÓÖ+Ø

Sum Sum Sum Sum

Ñ bits ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

97

Ad d izionatore Carry-Select

¾ Per ogni gruppo di cifre, calcola in parallelo somme “ locali” per i

due possibili valori del carry in ingresso

¾ Un multiplexer seleziona il risultato corretto in base al valore

effettivo del carry in ingresso

Æ maggiore dispendio di risorse hardware per minore tempo di

propagazione

A B A B A B A B

16:13 16:13 12:9 12:9 8:5 8:5 4:1 4:1

0 0 0

+ + +

C C C C

out 12 8 4

1 1 1 C

+ + + + in

1 1 1

0 0 0

S S S S

16:13 12:9 8:5 4:1

ª« ¬­ª® ¯° ± ² ® ³´µ ² ¶·®« µ ¸ ¶± ³°² ® ¹ °´¬® º ² ´³® º ² ® ¹ °­» µ® ¼ ´± º ® ² ½·®¾°¯¶¿ ®

98

Ad d izionatore Carry-Select

¾ Cammino critico

Bit 0–3 Bit 4–7 Bit 8–11 Bit 12–15

Setup Setup Setup Setup

0 0-Carry 0 0-Carry 0 0-Carry 0 0-Carry

1 1-Carry 1 1-Carry 1 1-Carry 1 1-Carry

ò ó ò'ô òô ò'ô ò'ô

Multiplexer Multiplexer Multiplexer Multiplexer

,0 ,3 ,7 ,11 ,15

Sum Generation Sum Generation Sum Generation Sum Generation

õ õ õ õ

0–3 4–7 8–11 12–15

ÜÝ ÞßÜà áâ ã ä à åæç ä èéàÝ ç ê èã åâä à ë âæÞà ì ä æåà ì ä à ë âßí çà î æã ì à ä ïéàðâáèñ à

99

Ad d izionatori carry-save

¾ Adatti per somme di più di due operandi (ad es., quando occorre

sommare i prodotti parziali in una moltiplicazione)

¾ Mantengono una rappresentazione ridondante delle somme parziali

ÜÝ ÞßÜà áâ ã ä à åæç ä èéàÝ ç ê èã åâä à ë âæÞà ì ä æåà ì ä à ë âßí çà î æã ì à ä ïéàðâáèñ à

100

Ad d izionatori Carry-Save

¾ Z=A+B+C+D &6 $%&

&6 &6

'

$%&'

= &6

&6'

ÜÝ ÞßÜà áâ ã ä à åæç ä èéàÝ ç ê èã åâä à ë âæÞà ì ä æåà ì ä à ë âßí çà î æã ì à ä ïéàðâáèñ à

101

Su p p orto Did attico

&DSLWRORH&DSLWROR0DFFKLQHSHU

O¶HODERUD]LRQHGHOOH,QIRUPD]LRQL

)DGLQL ± 'H&DUOLQL

ÜÝ ÞßÜà áâ ã ä à åæç ä èéàÝ ç ê èã åâä à ë âæÞà ì ä æåà ì ä à ë âßí çà î æã ì à ä ïéàðâáèñ à

Dom and e? ÜÝ ÞßÜà áâ ã ä à åæç ä èéàÝ ç ê èã åâä à ë âæÞà ì ä æåà ì ä à ë âßí çà î æã ì à ä ïéàðâáèñ à

Corso di Reti Logiche

La Tempificazione delle Macchine

Dipartimento di Informatica e Sistemistica

Università Degli Studi di Napoli Federico II 1

I limiti delle macchine reali

7HPSRGLULVSRVWD

Š Una rete ideale reagisce “istantaneamente” ad ogni

sollecitazione in ingresso, ovvero U(t)=ω (I(t))

Š In una rete reale la variazione dell’uscita a fronte di una

WHPSRGL

'

variazione degli ingressi avviene con un ritardo

ULVSRVWD ω(I(t))

: U(t+∆)= Ritardo puro

Z

, 8

E 2 1

Il Tempo di risposta

Il Tempo di risposta di una macchina è il ritardo d=t – t con il

f i

quale una variazione sull’ingresso è seguita da una

variazione sull’uscita X1

1

0 y

X2

1

0 3

Il Ritardo Inerziale (1/2)

5LWDUGRLQHU]LDOH

Š Una rete reale tende a permanere nello stato precedente se non è

Æ

sufficientemente sollecitata INERZIA

Š Æ

Sensibilità all’ingresso durata minima E

Un input è “sentito” dalla rete se dura almeno E E

L’output ritarda di E

Š Ritardo effettivo R

R=E+

Š Vincoli sulla frequenza di variazione dell’ingresso

f 1/2E 4 2

Il Ritardo Inerziale (2/2)

Si chiama ritardo inerziale E un elemento il cui ingresso I(t) e la

cui uscita U(t) rispettino le seguenti condizioni: , W FRQ ! H

• supposto che l'

ingresso vari al tempo t (I(t–

posto, t” < t+EW” '

< t + k, k < E,

VH,

si ha: =I(t) (variazione dura E),

8

allora8 )=I(t - t+E)=I(t) (segue dopo E)

VH, , W (variazione

=I(t), I(t+k non dura E),

allora: U(t+k)= I(t- ) (ignora variazione)

E 5

Ritardo Inerziale e frequenza massima

• Come detto, i ritardi dei dispositivi influenzano la frequenza

massima con la quale un segnale in ingresso può cambiare.

• Se E è il ritardo della macchina, la frequenza massima è:

5LWDUGR:

1

) 25 ms=0.025s

= ( ,QJUHVVR

2 X T = 10 ms =0.01s;

Y F=1/0.01=100 Hz 6 3

Il Ritardo Inerziale

Š Dovuto a fenomeni dinamici nella realizzazione

delle porte che “smussano” le transizioni 7

Sequenze di valori

Š Avendo considerato il tempo un fattore determinante,

non è più possibile considerare l’ingresso semplicemente

come un singolo valore fornito in ingresso alla macchina.

Š Gli Ingressi delle macchine sono delle “VHTXHQ]H” di

valori:

Costituite da impulsi e livelli

Š Diversi tipi di sequenze:

A livelli

Impulsiva Autosincronizzata

Impulsiva a sincronizzazione esterna

Puramente Impulsiva 8 4

Livelli ed impulsi

Š Un valore astratto in una sequenza può essere

,PSXOVLYR, se la sua durata è idealmente nulla

$OLYHOOL, se non impulsivo

Š Di conseguenza una sequenza può essere:

,PSXOVLYD, se contiene valori impulsivi

$OLYHOOL, se contiene solo valori a livelli

Sequenza a livelli Sequenza impulsiva

v v

t t

(a) (c) 9

Le sequenze v

6HTXHQ]H

Š Le sequenze astratte sono in generale costituite da L t

(a)

segnali binari a livelli, K impulsivi

Š v

Le sequenze astratte a livelli hanno k=0

Š Le sequenze astratte impulsive possono essere: t

(c)

a sincronizzazione esterna: k=1 v

autosincronizzata: k>1

puramente Impulsiva se L=0 v t

(b)

t

(d) 10 5

Classificazione delle Sequenze

v v

t t

Sequenza a livelli Sequenza Impulsiva

autosincronizzata

v

v t

t Sequenza puramente

Sequenza Impulsiva a Impulsiva

Sincronizzazione esterna 11

Un esempio

6HTXHQ]HGLLQJUHVVR

i

6

i

5

i

4

i

3

i

2

i

1 W

7 7

t

t t

3

1 2 6

Il Clock

Š Un particolare tipo di

sequenza molto v

utilizzato è il “Clock”

Š E’ una sequenza …

puramente impulsiva t

Š Clock Ideale

Gli impulsi hanno tutti la v

stessa altezza

Š Gli impulsi avvengono …

con una frequenza t

Clock Reale

costante 13

Clock e Sequenze

Š Si noti come è possibile avere una sequenza a

sincronizzazione esterna con un clock ed una

sequenza a livelli v

v t

v Sequenza a livelli

t

Sequenza Impulsiva a …

Sincronizzazione esterna t

Clock Reale 14 7

Il Clock a n Fasi

Š Non sempre è possibile v

tempificare la macchina

con un solo clock

Š …

Si può ottenere un clock t

Clock 1

a più fasi aggiungendo v

un ritardo

Š Si hanno due clock …

“sfasati” tra loro con lo t

Clock 2

stesso periodo 15

Macchine a livello ed impulsive

0DFFKLQHDOLYHOOR

Š Ingressi ed uscite sono sequenze a

livelli

Problema: la durata del livello

0DFFKLQH,PSXOVLYH

Š Ingressi ed uscite sono sequenze

impulsive

Problema: la frequenza degli impulsi 16 8

$/(( 17

Le Alee

Š La presenza di ritardi nei dispositivi utilizzati

può avere l’effetto di modificare il comportamento

delle uscite in alcuni casi.

$OHH

Š Si chiamano quei fenomeni per i quali le

uscite, anche se solo per brevi intervalli di tempo,

assumono dei valori imprevisti. 18 9

Classificazione delle Alee

Š Alee Transitorie

Le uscite della rete assumono valori diversi da quelli

progettati soltanto nel transitorio conseguente alle

variazioni degli ingressi. «L L L «

Ad una sequenza di ingressi

«I L 6 I L 6 I L «

Corrisponde un’uscita

Š Alee di Regime

L’uscita assume un valore diverso da quello progettato

anche dopo il transitorio. L L «

«L

Ad una sequenza di ingressi

«I L I L 6 «

Corrisponde un’uscita 19

Alee Tipiche

$OHH7UDQVLWRULH $OHHGL5HJLPH

$OHD0XOWLSOD

Š $OHH(VVHQ]LDOL

Š

Variazione simultanea di due Dovute alle caratteristiche

o più variabili di ingresso. della rete.

$OHDSHU,PSXOVL

Š $OHHSHU&RUVH&ULWLFKH

Š

&RQFRPLWDQWL A causa della codifica le

Presenza di due o più impulsi. variazioni delle uscite

$OHD6WDWLFD

Š dipendono dall’ordine degli

Variazione temporanea ingressi.

dell’uscita che dovrebbe $OHHSHUIUHTXHQ]DHOHYDWD

Š

rimanere costante.

$OHD'LQDPLFD

Š Gli ingressi variano troppo

rapidamente.

Oscillazione temporanea

dell’uscita. 20 10

Alee Multiple (1/2)

Š Valori adiacenti di una codifica:

Data una codifica di due stati di ingresso, due

rappresentazioni si dicono adiacenti se differiscono di

una sola variabile

0 0 0 0 1 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1 0 0 0 0

Valori Non Adiacenti

Valori Adiacenti 21

Alee Multiple (2/2)

Si ha un’Alea Multipla se due ingressi consecutivi nel tempo i e i

1 2

non sono adiacenti

(V

8QLFD6ROX]LRQH

Eliminare ingressi

non adiacenti 22 11

Impulsi Concomitanti (1/2)

Se si suppone che due impulsi avvengano

contemporaneamente i ritardi possono cambiare il

comportamento della funzione

(V X Y

Y = X X

1 2 23

Impulsi Concomitanti (2/2)

a

a

b b

a⋅b

a⋅b

a⋅+b a⋅+b

D E 24 12

Alee Statiche (1/2)

Si ha un’Alea Statica se avendo due ingressi i e i adiacenti

1 2

I I L I L

con uscite uguali , l’uscita assume nel transitorio

127 I

il valore .

(V

Y = aa + aa Si manifesta anche

per transizioni tra

ingressi adiacenti! 25

Alea Statica (2/2)

Š Manifestazione

Variazione temporanea dell’uscita che dovrebbe rimanere costante

Š Cause Æ

Alee multiple interne diverse durate dei ritardi nelle singole porte

7UDQVL]LRQHWUDGXHLPSOLFDQWLGLVWLQWLGHOO¶XVFLWD

G

G 13

Alea Statica - Soluzione

Š Il problema è legato ad una

doppia variazione dei valori

interni della rete a partire dalla

variazione di un singolo

ingresso

Š C C

Aggiungendo gli implicanti 0 1

C

2 00 01 11 10

ridondanti si “coprono” le 1 1

0

variazioni che determinano

l’alea (è possibile dimostrarlo) 1 1

1

Š Non è una buona idea,

invece, cercare di bilanciare i Implicante

ritardi circuitali !!! Ridondante

27

Alee Dinamiche

Si ha un’Alea Dinamica se avendo due ingressi i e i

1 2

α β,

adiacenti con uscite uguali f(i ) = e f(i )= la sequenza di

1 2

α β α β

uscita è del tipo ... ... ... .

(VL L [[[

Y = (X X + X X )(X + X )

1 3 2 3 1 3 !

X

a 3 t !!!

1 b

0 X z

!!

1 y

1

0 c

X

2 29 14

Alee Dinamiche

Š Si verificano solo in reti a più di due livelli.

Š Sono dovute ad alee statiche nei livelli

precedenti e ritardi.

Š Si eliminano eliminando le alee statiche

nelle sottoreti componenti. 30

Codifica degli ingressi

LQIOXHQ]D

Š La presenza di alee il progetto

delle reti logiche

Aggiunta di ridondanza (alee statiche)

Codifica degli ingressi (alee multiple)

Forzare transizioni tra stati adiacenti

Eventualmente aggiungendo variabili (e quindi stati

di ingresso) 31 15

Grafo di transizione degli ingressi

L L L L

L L L L

D E 32

Aggiunta di stati

Assegnazione priva di Alee Multiple (da 4 stati a 7, con

l’aggiunta di una variabile binaria)

L L

L L

D E 33 16

Impulsi e livelli

l l

x $&%

x

y δ ∆

!#"

y’ PRQRVWDELOH

GHULYDWRUH (

' ,

( +

)* -&.

4

1

/ )OLSIORS

7

0 1

23 Q 5&6 34

5HWL8QLYHUVDOL 35 17

Reti universali - 1

5HWLFRQPXOWLSOH[HU

Š Un multiplexer convoglia sulla uscita

y quello fra gli m=2 “ingressi primari”

n

A selezionato dagli n “ingressi

i

secondari” C Bit di

j specificazione Variabili indipendenti

• Ma questa è la forma normale di una funzione delle C con P mintermini

i i

e A bit che specificano la funzione. Si ottiene allora una rete universale

i

per funzioni di n variabili ponendo:

ƒ Ingressi primari = bit di specificazione

ƒ Ingressi secondari = variabili indipendenti

Reti universali - 2

/RJLFD³IROGHG´

Š Nella forma normale della funzione, mettendo in evidenza i mintermini

nelle C .C ….C ciascuno di questi risulta moltiplicato per:

0 1 n-2,

8 C se non esiste il mintermine in tutte le variabili con C

n-1 n-1

8 C se non esiste il mintermine con C

n-1 n-1

8 1, se esistono entrambi

8 0, se non esistono né l’uno né l’altro

Š n-1 ingressi secondari per

È allora possibile usare un multiplexer con

generare funzioni di n variabili

9 I bit di specificazione sono uno dei valori (0,1,C , C )

n-1 n-1 18

Reti universali - 3

/RJLFD5205HDG 2QO\ 0HPRU\

Š Una ROM implementa la funzione

0% 0 0$

Š Se MA è di n bit

Š e la memoria ha parallelismo di m bit

Š Si realizzano m funzioni di n variabili

Š I contenuti della memoria (colonne di tabelle

di verità) sono

8 specificati dall’utente

8 realizzati dal costruttore “bruciando” i

collegamenti fra linee orizzontali e verticali 38

Reti universali - 4

3/$± 3URJUDPPDEOH /RJLF $UUD\

Š Fanno parte della più ampia classe dei “Dispositivi Logici Programmabili”

Š Realizzare k funzioni di n variabili in forma and-or a 2 livelli

n

• 2 sezioni

: AND: realizza le m clausole

: OR: realizza le k sommatorie m

: Le specifiche (χ e a )

i ij

• fornite da utente

• realizzate dal costruttore attivando i k

collegamenti per le AND e le OR 19

Corso di Reti Logiche

Macchine Sequenziali

Dipartimento di Informatica e Sistemistica

Università degli Studi di Napoli Federico II 1

Macchine sequenziali

Š Includono il fattore tempo nel funzionamento logico della macchina

Š le uscite sono funzione della storia della macchina

Š in macchine fisicamente realizzabili, le uscite in un dato istante

ILQRD

sono funzione degli ingressi che sono stati applicati

quell’istante

VWDWRLQWHUQR

Š uno mantiene memoria della storia della macchina

Š le uscite dipendono dallo stato (ed eventualmente dagli ingessi)

Š il modello si può particolarizzare al caso di tempo continuo o

discreto

Š in macchine di interesse pratico il numero dei valori possibili degli

PDFFKLQHDVWDWLILQLWL

stati, ingressi e uscite è finito:

(VWDWR)

ingressi uscite 2 1

Macchine Sequenziali

Š Frullatore ?

Š Ascensore?

Š Contatore? 3

Modello Matematico: Mealy

Definizione di macchina sequenziale a stati finiti secondo Mealy:

8QDPDFFKLQDVHTXHQ]LDOHqXQD

TXLQWXSODRUGLQDWDGLHQWL0 4,8WZ

GRYH

• Q è un insieme finito di “Stati Interni”

• I è un insieme finito di “Stati di Ingresso”

• U è un insieme finito di “Stati di Uscita”

W 4 , 4

× →

• t è una funzione Z 4 , 8

× →

• w è una funzione

Æ Le uscite dipendono da stato e ingresso 4 2

Modello Matematico: Moore

Definizione di macchina sequenziale a stati finiti secondo Moore:

8QDPDFFKLQDVHTXHQ]LDOHqXQD

TXLQWXSODRUGLQDWDGLHQWL0 4,8WZ

GRYH

• Q è un insieme finito di “Stati Interni”

• I è un insieme finito di “Stati di Ingresso”

• U è un insieme finito di “Stati di Uscita”

W 4 , 4

× →

• t è una funzione Z 4 8

• w è una funzione

Æ Le uscite dipendono solo dallo stato

Si può dimostrare l’equivalenza dei due modelli 5

Modello realizzativo

Š In termini realizzativi, i due modelli di Mealy e Moore si

possono tradurre in uno schema in cui:

“tutta la storia precedente” della macchina (ovvero lo stato) è

inclusa in un componente con memoria

W Z

le funzioni stato prossimo e uscita sono realizzate da una

macchina combinatoria

stato elemento di memoria

stato prossimo

Macchina

ingressi uscite

combinatoria 6 3

Descrizione della macchina

Š Se la macchina è a stati finiti, il suo

comportamento può essere descritto

attraverso una tabella oppure un grafo 7

Tabella degli stati

Š Tabella Stato/Ingresso

le righe sono relative agli stati, le

colonne agli ingressi 6

ogni cella associa ad una coppia S /0 S /0

0 1

6

ingresso/stato l’uscita ed il S /0 S /0

2 1

prossimo stato

6 S /0 S /1

0 0

Mealy: le uscite sono riportate nelle

celle (dipendono da stato ed ad esempio, trovandosi nello

ingresso) 6

stato , nel caso sia applicato

,

Moore: le uscite possono essere

il valore di ingresso la

riportate in una colonna a parte macchina si posta nel nuovo

6

(dipendono solo dagli stati, c’è stato producendo come

quindi un’uscita per ogni riga)

uscita il valore 8 4

Grafo degli stati

Š stato corrente

1 / 0

Grafo degli stati

ogni nodo corrisponde S

1/0

1

ad uno stato S 0 / 0

0

ogni transizione (arco)

indica il prossimo stato 0 / 0 0/ 0

S

in corrispondenza di un 1 / 1 2 uscita prodotta

determinato ingresso stato prossimo ingresso applicato

Mealy: uscita associata

6 ,

ad esempio, trovandosi nello stato

all’arco

nel caso sia applicato il valore di

,

Moore: uscita associata ingresso la macchina si posta nel

6

al nodo (stato) nuovo stato producendo come

uscita il valore 9

Tabelle e grafi degli stati 8

6

6 S S 0

S /0 S /0 0 1

0 1

6

0HDO\

6 S S 0

S /0 S /0 2 1

2 1

6

6 S S 1

S /0 S /1 0 0

0 0

0RRUH

1 / 0 1

S S /0

S S /0

1/0

1 1

1

0 0

0 / 0 0

0

0 / 0 0 / 0 0

S 1 S /1

2

1 / 1 2 10 5

Esempio

Š Vogliamo realizzare una macchina in grado

di riconoscere la sequenza 101

,

la macchina avrà un ingresso su cui arriva

una sequenza di 1 o 0

8

una uscita che si alza solo quando in ingesso

è appena arrivata una sequenza 101

4

, 8

0 1 0 0 0 1 0 1 11

Esempio

Š potremo usare una macchina a stati finiti con tre stati S ,

0

S , S con i seguenti significati

1 2

S è lo stato in cui non è stato riconosciuto ancora niente in

0

ingresso

S è lo stato in cui ci si trova se è stata riconosciuta una sequenza

1

di un bit uguale a “1”

S è lo stato in cui ci si trova se è stata riconosciuta la sequenza

2

“10”. A questo punto, se arriva un ‘1’ si sarà riconosciuta la

sequenza “101”, se arriva ‘0’ non si è riconosciuto niente. In ogni

caso, si ritorna in S , ma con uscite diverse a seconda che si sia

0

riconosciuta o meno la sequenza 12 6

Esempio

$XWRPDLQJUDGRGLULFRQRVFHUHODVHTXHQ]DLQLQJUHVVR

1/0

S 1/0

6 1

S /0 S /0 S 0/0

0 1 0

6 S /0 S /0

2 1

6 0/0 0/0

S

S /0 S /1 1/1 2

0 0

descrizione tramite tabella descrizione tramite grafo 13

Modello generale

8QD0DFFKLQD6HTXHQ]LDOH

SXzHVVHUHUHDOL]]DWD

FRQ d

Š Una macchina

Combinatoria Stato

Š Macchina

Un ritardo Stato Prossimo

Combinatoria

Ingresso Uscita 14 7

Le Parti della Macchina

Š L’ingresso della macchina combinatoria è

SL

l’ingresso della macchina sequenziale

l’uscita del ritardo (lo stato precedente).

Š L’uscita della macchina combinatoria è

SL

l’uscita della macchina sequenziale il

prossimo stato della macchina. 15

Macchine asincrone VWDWR

Š Una macchina con ingressi a livelli ha uno

VWDELOHT L

sotto un ingresso se

TL T( funzione prossimo stato)

Š In altre parole, applicando in maniera continua

L T

l’ingresso la macchina permane nello stato

Š Se partendo da qualsiasi stato ed applicando

qualsiasi ingresso è sempre possibile arrivare in

DVLQFURQD

uno stato stabile, la macchina si dice 16 8

Stati stabili i

3

i

i 2

q2

1 q3

q1 Stato stabile

i i i …

1 2 3

q1 q2 … … …

q2 … q3 … …

q3 … … q3 …

… … … … … 17

Macchine asincrone

La macchina è asincrona:

partendo da qualsiasi stato ed

L L L applicando una qualsiasi

T sequenza fissa in ingresso si

q1 q2 q3

T perviene ad uno stato stabile.

q4 q2 q3

T Es.:

q1 q4 q3

T T L

q4 q4 q3 Partendo da ed applicando

T(purché L

si rimane in sia

applicato per un tempo

sufficiente a far arrivare la

macchina nello stato q2) 18 9

Macchine asincrone

Applicando una sequenza di due ingressi in una macchina asincrona, la

transizione tra uno stato stabile e l’altro avviene mediante una

transizione orizzontali e poi k transizioni verticali verso lo stato stabile

(ciclo lungo k) L’unica condizione necessaria a garantire il

L L L passaggio da uno stato stabile ad un

nuovo stato stabile noto è che il nuovo

T SHUXQWHPSR

q1 q2 q3 ingresso sia applicato

VXIILFLHQWHa

T permettere la transizione

q4 q2 q3

T attraverso gli stati intermedi

q1 q4 q3

T q4 q4 q3 Le uscite possono essere assegnate ai soli

stati stabili 19

Macchine asincrone

ritardo puro della macchina ritardo inerziale

combinatoria ( ) più ritardo della macchina

c combinatoria E

delle linee ( ) c

l La transizione tra

s due stati stabili

avviene soltanto se

G

la durata

l c dell’ingresso che

genera la transizione

N

E

stato attraverso stati

Macchina c consecutivi è tale

Combinatoria che

uscite

ingressi G!N (

20 10

Modello di rete asincrona (fondamentale)

'

Y Y’

0DFFKLQD

FRPELQDWRULD

WZ Z

X D 21

Limiti di reti asincrone:alee multiple e corse

Corse (critiche) NO

Alee multiple NO

Y Y’

5HWH

FRPELQDWRULD

WZ Z

X D 22 11

Domande? 12

Corso di Reti Logiche

Macchine Sequenziali

Dipartimento di Informatica e Sistemistica

Università degli Studi di Napoli Federico II 1

Funzioni uscita e stato prossimo

Š L’uscita e lo stato prossimo sono funzioni della

sequenza di ingressi applicata a partire da uno

“stato iniziale”:

X T -

N

k T -

T N N 1

Macchine complete e incomplete

$SSOLFDELOLWjGLXQDVHTXHQ]D DSSOLFDELOH VLGLFH

Š Una sequenza di ingressi J è a M in q -

D0 T - X T- ODIXQ]LRQHFKHIRUQLVFH

se è definita

O¶XVFLWDXFKHVLRWWLHQHDSSOLFDQGRDOODPDFFKLQDOD

VHTXHQ]DGLLQJUHVVL-DSDUWLUHGDXQR³VWDWRLQL]LDOH´T

Š Se la funzione di uscita è definita ovunque, la macchina

FRPSOHWD, LQFRPSOHWD

si dice altrimenti

3HUOHPDFFKLQHLQFRPSOHWHHVLVWRQRVHTXHQ]HQRQ

Š DSSOLFDELOL - QRQDSSOLFDELOH

Sequenza in q : non definita

0

Potrebbe essere applicabile una sequenza più lunga 3

Equivalenza

Š Occorre formalizzare il fatto che due macchine

possano avere lo stesso funzionamento

Æ reagire nello stesso modo (con le stesse

uscite) alle stesse sequenze di ingressi

Š VWDWLHTXLYDOHQWLin

Definizione di macchine

complete

3URGXFRQRODVWHVVDVHTXHQ]DGLXVFLWHSHU

TXDOVLDVLVHTXHQ]DGLLQJUHVVL 4 2

Equivalenza

Š Un modo per riconoscere stati equivalenti

(fondamentale negli algoritmi che vedremo)

è usare la proprietà ricorsiva degli stati

equivalenti:

'XHVWDWLVRQRHTXLYDOHQWLVHORVRQR

WXWWHOHSRVVLELOLFRSSLHGLVWDWL

VXFFHVVLYLHVRQRXJXDOLWXWWHOH

SRVVLELOLXVFLWHVXFFHVVLYH 5

Equivalenza: riassumendo

Š Concetto di equivalenza: avere lo stesso

funzionamento “esterno”

Reagire nello stesso modo (con le stesse uscite) alle

stesse sequenze di ingressi

Due stati sono equivalenti se, per ciascun ingresso:

sono eguali le uscite

sono equivalenti gli stati successivi FRPSOHWH

VWDWLHTXLYDOHQWLin

Definizione di macchine

Producono la stessa sequenza di uscite per qualsiasi sequenza di

ingressi 3

Equivalenza

Š I due stati possono appartenere anche alla

stessa macchina

FRPSOHWH

Š Due macchine M e M’ sono

equivalenti se per ciascuno stato q di M

esiste almeno uno stato q’ di M’ ad esso

equivalente e, viceversa 7

Equivalenza e macchine incompete

Š La definizione precedente non può essere

applicata così com’è

Æ non tutte le possibili sequenze sono

applicabili a tutti gli stati

Š Si introducono i concetti di:

&RPSDWLELOLWj tra stati

,QFOXVLRQH tra macchine

8 4

Equivalenza: ricapitolando

6WDWLHTXLYDOHQWL PDFFKLQHFRPSOHWH

Š Due stati (della stessa macchina o di macchine diverse) sono equivalenti se

producono la stessa sequenza di uscite per qualsiasi sequenza di ingressi

Š Definizione ricorsiva

Due stati sono equivalenti se, per ciascun ingresso sono eguali le uscite e sono

equivalenti gli stati successivi

0DFFKLQHHTXLYDOHQWL FRPSOHWH

Š Due macchine complete M e M’ sono equivalenti se per ciascuno stato q di M

esiste almeno uno stato q’ di M’ ad esso equivalente e viceversa

0DFFKLQHHTXLYDOHQWL LQFRPSOHWH n

on tutte le sequenze di ingresso

sono applicabili

ƒ &RPSDWLELOLWjtra ,QFOXVLRQH

il concetto è sostituito da quelli di stati ed tra

macchine 9

Stati compatibili

FRPSDWLELOLse SHURJQLsequenza

Š Due stati sono di

HQWUDPELle

ingressi applicabili ad uscite prodotte sono

identiche

Š A differenza della relazione vista prima per macchine

121è

complete, la compatibilità una relazione di

equivalenza:

Gode delle proprietà

Riflessiva

Simmetrica

Ma NON di quella transitiva

λ(q1,J)=a, λ(q2,J)=-, λ(q3,J)=b

p.e.: q1~q2, q2~q3, ,

Š Ciò complica la ricerca di macchine equivalenti minime 10 5

Compatibilità

Š Così come l’equivalenza, anche la compatibilità può

essere definita ricorsivamente

'XHVWDWLVRQRFRPSDWLELOLVHWXWWLLSRVVLELOLVWDWL

Š SURVVLPLVRQRFRPSDWLELOLHWXWWHOHSRVVLELOLXVFLWH

SURVVLPHVRQRXJXDOL

Š Non essendo una relazione di equivalenza, non è

possibile utilizzare le proprietà delle classi di equivalenza.

IDPLJOLDGLLQVLHPLGLVWDWL

Š Si generalizza con il concetto di

FRPSDWLELOLPDVVLPL 11

Compatibilità

Š Per le macchine incomplete, non si parla quindi di

equivalenza, ma di inclusione: LQXQDFRSSLDGLVWDWLT

Una macchina M’ ne include una M,

T¶se

e tutte le sequenze di ingressi applicabili ad M a

partire da q lo sono anche per M’ a partire da q’

producendo la stessa uscita

Se è possibile trovare per ciascuno stato di M uno q che

soddisfa la precedente definizione, allora M’ include M

Æ è possibile usare M’ in luogo della M

M ed M’ possono includersi l’un l’altra

Æ diremo in questo caso che le due macchine sono

equivalenti 12 6

Compatibilità: formalmente

,QFOXVLRQHIUDPDFFKLQH

&RQFHWWXDOPHQWH

Š una macchina include un’altra se “fa qualcosa in più”

)RUPDOPHQWH

Š M’(q’) include M(q):

ƒ M

M’ include ‘ 13

Compatibilità ed equivalenza

Š Nel caso di macchine complete le due definizioni

coincidono.

Š Tra due macchine equivalenti, conviene scegliere

quella con meno stati

Š Æ problema di minimizzazione

individuare la macchina con il minor numero di

stati tra tutte le possibili macchine equivalenti 14 7

Minimizzazione degli stati

0LQLPL]]D]LRQHHFODVVLGLHTXLYDOHQ]D

Š Data una macchina M se ne vuole trovare una equivalente, M’, con un

numero minimo di stati.

/DIDPLJOLDGHOOHFODVVLGLHTXLYDOHQ]DGHJOLVWDWLGL0qODVROX]LRQH:

Š M’ ha uno stato per ogni elemento C della famiglia con:

XVFLWD

pari alla uscita degli elementi di C, tutti eguali per essere

questi equivalenti fra loro,

VWDWRVHJXHQWH

quello determinato da C stesso; essendo infatti gli

stati di C equivalenti fra loro, devono avere tutti per seguenti stati

i

equivalenti e quindi appartenere ad un unico elemento C’ della

famiglia delle classi di equivalenza.

0¶KDXQQXPHURGLVWDWLPLQLPRSHUOHSURSULHWjGHOOHFODVVLGL

HTXLYDOHQ]D. 15

Minimizzazione degli stati

0LQLPL]]D]LRQHHFODVVLGLFRPSDWLELOLWjPDVVLPH

Š Per le macchine incomplete, proprietà analoghe a quelle delle classi di

equivalenza, ma più complesse, hanno le classi di compatibilità massime

Š Si procede analogamente, con le seguenti peculiarità:

M’ include M (non è equivalente)

La soluzione potrebbe non essere minima, ma in generale presenta

una macchina a “stati ridotti”

Si possono avere più soluzioni, potendo uno “stato seguente” essere

incluso in più elementi distinti della famiglia di compatibilità massima 16 8

Problema della Minimizzazione

0 4,8

Š Partendo da una macchina ,

ne vogliamo trovare a macchina

0¶ 4¶,8 ¶ ¶ equivalente ad M e con il

minor numero di stati

Š Partiamo dalla famiglia di insiemi di stati

) 6 6 6

compatibili massimi Q 17

Problema della Minimizzazione

Š La F gode delle seguenti proprietà, essenziali nei metodi

di minimizzazione:

Gli elementi S di F sono disgiunti

Gli elementi S di F coprono l’insieme degli stati Q

Tutti gli stati di un elemento S di F portano alla stessa uscita

(eventualmente non definita)

F è chiusa: da due stati di uno stesso elemento S di F si arriva a

due stati che appartengono ad una stessa S’

0 ),8 ¶

Š Ricerchiamo la

Æ M’ ha un numero di stati non superiore a M 18 9

Ricerca della famiglia F

Š Algoritmo del partizionamento

Š Metodo tabellare di Paull-Unger

Š Procedono per “eliminazione”

Partono da una presunta F (inizialmente

coincidente con Q) e cercano di individuare

incompatibilità fin quando è possibile 19

Algoritmo del partizionamento

Š Si individuano gli stati incompatibili rispetto

alle uscite per ciascun ingresso

Š Le partizioni individuate si esaminano

rispetto allo stato prossimo

Š Si itera fintantoché tutte le partizioni non

verificano la definizione di compatibilità 20 10

Algoritmo del partizionamento 21

Metodo di Paull-Unger

Š Riorganizza il procedimento visto prima in

forma di matrice diagonale incompatibilità

Possibili coppie di

stati stati prossimi 22 11

Metodo di Paull-Unger

Š Si marcano come incompatibili le coppie di

stati che portano ad uscite differenti per

almeno un ingresso

Š Si indicano le coppie di possibili stati

prossimi in ogni casella

Š Si continua iterativamente il procedimento

partizionando rispetto agli stati 23

Metodo di Paull-Unger

Ogni elemento della Tabella delle Implicazioni

contiene:

Il simbolo di non equivalenza (X)

Il simbolo di equivalenza (~)

FRQGL]LRQDQWL

La coppia di stati se non è possible stabilire

immediatamente l’equivalenza (o non equivalenza) 12

Esempio – Paull-Unger 25

“e” ed “a” hanno le stesse

uscite per ogni ingresso

“g” ed “f” sono equivalenti

se lo sono “a” e “d”

“g” e “b” hanno uscite

differenti (con rif ad uno

stesso ingresso)

Esempio - cont 26

‡ Procedendo iterativamente si giunge a determinare

le classi di equivalenza 13

Metodo di Paull-Unger Ogni stato è confrontato con

L L tutti gli altri, ma solo una volta:

1 è confrontato con 2…6

2 è confrontato con 3…6

2/A 4/B etc etc.

3/B 5/A

5/A 4/B

2/B 2/B

2/B 5/A

3/A 5/B 27

Esempio: Riconoscitore di codice 8-4-2-1

Š Costruire una rete nella quale entrano

serialmente i bit di un codice decimale 8-4-2-

1 a partire dal bit meno significativo e dalla

quale esce un segnale impulsivo che

individua se i quattro bit costituiscono o meno

una delle 10 parole-codice previste

5LIHULPHQWR“Reti logiche-Complementi ed Esercizi” CAP 5, es n.6 14

Esempio: Riconoscitore di codice 8-4-2-1

Š Procediamo per elencazione di tutti le possibili sequenze

Individuiamo tutti i possibili stati

Partizioniamo rispetto alle uscite

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

Esempio: Riconoscitore di codice 8-4-2-1

Š Eliminiamo le righe uguali

ne resta soltanto una e lo stato non eliminato (ad es. 7)

viene sostituito a tutti quelli eliminati nella colonna degli

stati futuri non 8!!*

non 14!!

* Lo stesso vale per 9, 11, 12 e 13 15

Esempio: Riconoscitore di codice 8-4-2-1

‡ Tracciamo la tabella delle implicazioni

Esempio: Riconoscitore di codice 8-4-2-1

Š Classi di equivalenza

Ricordando anche gli stati “fusi” in precedenza

Tabella degli

stati ridotti 16

Riconoscitore di due sequenze

Š Rete sincrona con un solo ingresso X e in grado di riconoscere le due

sequenze: 0110010 e 0110110

Š Le uscite devono essere codificate in modo da distinguere i tre casi di

possibile riconoscimento di sequenze:

1) 0110010; 2) 0110110; 3) tutte le altre

- Y=0, Z=0: non è stata trovata nessuna sequenza;

- Y=1: Z=0 riconosciuta la sequenza 0110010;

- Z=1: Y=0 riconosciuta la sequenza 0110110;

- Y=Z=1: uscita non utilizzata 33

Riconoscitore di due sequenze

• q0 stato iniziale; L

• qi (i < 5): riconosciuto un numero di caratteri della seq. 0110---

• L

• q i (i 5): riconosciuto un numero di caratteri della seq.

0 0110010

• L

• q i (i 5): riconosciuto un numero di caratteri della seq.

1 0110110

0/ 10

1/ 00

1/ 00 0

q

0

0/ 00 6

q 5

0/ 00

1/ 00 1/ 00 0/ 00

0/ 00 1/ 00 q q

q q q 3 4

0 1 2

0/ 00

0/ 00 1/ 00 1

q

1

q 6

5 1/ 00

0/ 00

1/ 00 0/ 01 34 17

Riconoscitore di due sequenze

X X

stati 0 1 stati 0 1

q q / 00 q / 00 q q q

0 1 0 0 1 0

q q / 00 q / 00 q q q

1 1 2 1 1 2

q q / 00 q / 00 q q q

2 1 3 2 1 3

q q / 00 q / 00 q q q

3 4 0 3 4 0

0 1 0 1

partizione

q q

q q q q

/ 00 / 00

4 4

5 5 5 5

0 0 0 0

q q q q

q / 00 q

/ 00

1 1

5 6 5 6

1 1 1 1

q q q q

q / 00 q

/ 00

1 1

5 6 5 6

0 0

q q / 10 q / 00 q q q

0 3 0 3

6 6

1 q / 01 q / 00

q 1

q q q

0 0 0 0

6 6 35

Riconoscitore di due sequenze

q q

q q

1 - q q

1

0 3 -

0 3

q q

q q q q

2 - - q q q q

2

0 2 2 3 - -

0 2 2 3

q q q q q q

-

- - q q q q q q

q 1 4 1 4 1 4 -

- -

q 1 4 1 4 1 4

q q

3 q q

- - q q

3 q q

0 2 0 3 - -

0 2 0 3

q q

0 0 0

q q 0

q q q q

- - -

- q q

0 0 0

q q 0

1 4 q q

0 q q

- - -

1

q -

5 5 5 5 1 4

1 0

1 1 1 1

q

q q q q 5 5 5 5

q q q

4 q

- 1

- - 1 1 1

- q q q q

q q q

4

0 2 5 q

-

3 0

5 5 - -

5 -

0 2 5

3 0

5 5

5

q q q 0

q

- - q

0 q q 0

0 0 0 1 1

q q q q

4

q q - -

q

q 5

- 0 0 0 0

- 1 1

- q q q 4

0 0 1 q q

q

q q

5 0 2 5

6 6 -

6 q q -

3 q -

- - 0 0 1

q

5 0 2

6 6

6 q q

3

0 q

-

6 6 -

5 0 6 6 5

0

q q q q

-

1 1

1 - 0

q q q q

1 1

q 0 q

q

q q 1 4 4

q -

1 1

5

q q 1 -

- - q q 1 1

- - q 4 0

1 q

1 q q 1 4

0 q

1

2 q 5

6 6 q q

- -

3 q

q

5 6 q - -

1

6 6

q 1

0

- - 1

2 q

6 6 3 q

5 6 q

0 6 6

q

5 - -

6 6 0 5

6 6

0

q 0

q

6 6

1

q 1

q

6 6

q q 0

q q 0

q 1 q

q q q q 0

q q 0

q

1 3 1 q

0 4

2 q

6 q

5 1 3

5 0 4

2 6

5 5

Non esistono stati compatibili! La tabella di flusso è già minima 36 18

0DFFKLQH,QFRPSOHWDPHQWH6SHFLILFDWH 37

Macchina incompletamente specificata

Š Compatibilità: si ricorda che…

VL VM

Due stati e si dicono compatibili se partendo da essi ed

,

applicando ogni possibile sequenza di ingresso applicabile si

ottengono le stesse sequenze d’uscita, ovunque queste siano

specificate.

La relazione di compatibilità non è transitiva!!!

Le classi di compatibilità NON sono disgiunte

Non è possibile applicare il metodo della fusione delle righe (row

merging) 19

Macchina incompletamente specificata

‡ Costruzione della macchina minima o a stati ridotti

„ E’ più complessa che nel caso delle macchine

completamente specificate.

„ Gli insiemi di F non sono disgiunti!

„ Un insieme T può essere incluso in più di un insieme di

F

la macchina che si ottiene associando uno stato ad

ogni distinto insieme della famiglia F non è

necessariamente una macchina a numero minimo di

.

stati

Esempio (1/2)

Š Esempio: Stato seguente Incluso in uscita

i

i i i i 1 (1,2,3,4,6) (1,1,3,1,3) (1,2,3,4,6) 1

1 2 3 4 2 (1,2,3,4,6) (2,2,4,4,-) (1,2,3,4,6) 2

q /u q /- -/- q /-

q 3 (1,2,3,4,6) (-,5,-,5,5) (5,6,7) 4

1 1 1 2 6 4 (1,2,3,4,6) (6,-,6,-,6) (5,6,7) e (1,2,3,4,6) -

q q /- q /u q /- -/- 1 (5,6,7) (-,3,3) (1,2,3,4,6) -

2 1 2 2 5 2 (5,6,7) (7,-,7) (5,6,7) 4

q q /u q /- -/- q /- 3 (5,6,7) (5,5,5) (5,6,7) 3

3 3 1 4 6 4 (5,6,7) (6,6,-) (5,6,7) e (1,2,3,4,6) 4

q q /- q /u q /- -/-

4 1 4 2 5

q -/- q /- q /u q /-

5 7 5 3 6 T 6 T 6

⊆ ⊆

q q /- -/- q /- q / u

6 3 5 6 4

q q /- q /u q /- -/-

7 3 7 4 5

) 66

6 TTTTT 6 TTT 20

Esempio (2/2)

Š Esempio (continua)

LQFRUULVSRQGHQ]DGL 6L H 6L FLDVFXQD

Indeterminazioni

con 2 alternative e quindi 4 possibili soluzioni.

i i i i

1 2 3 4

S o S

1 2

S S /u S /u S /-

1 1 1 1 2 2 /u 4

S o S

1 2

S S /- S /u S / u

2 1 2 4 2 3 /u 4

La tecnica di perseguire insiemi disgiunti è

! impropria per macchine incomplete

In particolare può accadere che la macchina cui si

" perviene non mantenga la proprietà di chiusura

Algoritmo della suddivisione degli elementi

della famiglia di presunta compatibilità

Š Analogo al metodo del partizionamento visto per reti

complete

Š Data una famiglia, si esaminano singolarmente gli insiemi

presumibilmente compatibili

# se in uno di questi, S , si identificano due stati incompatibili, qi e qi,

k

Sk viene sostituito da due nuovi insiemi, l’uno contenente tutti gli

elementi tranne q e l’altro tutti tranne q , dando così luogo ad una

i j

nuova famiglia

Š Ad es.

# S = (q , q , q , q ) ; q q incompatibili

k l 2 3 4 1 e 2

S = (q , q , q ) ; S = (q , q , q )

k1 l 3 4 k2 2 3 4 21

Algoritmo della suddivisione degli elementi della

famiglia di presunta compatibilità

Š TRE PASSI:

3DVVR

# $ Si eliminano le incompatibilità immediatamente evidenti, ( per tutti gli

ingressi i ).

k T  T

, i , i )

i k j k

3DVVR DJJLXQWRULVSHWWRDOSDUWL]LRQDPHQWR

# $ Si individua una famiglia di insiemi "presumibilmente compatibili",

) 6 6 6

1 2 m

eliminando gli elementi inclusi in altri

3DVVR

# $ Si eliminano le incompatibilità dovute ad incompatibilità negli stati seguenti.

6L T T T si

Per ciascun ingresso ik e ciascun insieme forma

il i2 in

l'

insieme degli stati seguenti

7 6 L T L T L T L

i k i1 k i2 k in k

7 6 L 6

$ ∉

Se , si individua l'

incompatibilità , si procede alla suddivisione di

6L i k j

e si ritorna al passo 2.

7 6 L 6per

$ ∈

Se tutti gli elementi di F e per tutti gli ingressi, il

i k

procedimento ha termine.

Algoritmo della suddivisione degli elementi della famiglia di

presunta compatibilità – Esempio 4

i i i i

1 2 3 4

q q /u q /- -/- q /-

1 1 1 2 6

q q /- q /u q /- -/-

2 1 2 2 5

q q /u q /- -/- q /-

3 3 1 4 6 PASSI 1 e 2

q q /- q /u q /- -/-

4 1 4 2 5

q -/- q /- q /u q /-

5 7 5 3 6

q q /- -/- q /- q / u

6 3 5 6 4

q q /- q /u q /- -/-

7 3 7 4 5

Elemento Analisi Suddivisione Famiglia

i in esame uscite elemento

Passo 1 (1,2,3,4,5,6,7)

a

& /

2 (1,2,3,4,5,6,7) u u 2 7 (1,2,3,4,5,6)(1,3,4,5,6,7) (1,2,3,4,5,6) (1,3,4,5,6,7)

%

2 4 a

& /

2 (1,3,4,5,6,7) u u 4 7 (1,3,5,6,7) (1,3,4,5,6) (1,2,3,4,5,6)(1,3,5,6,7)(1,3,4,5,6)

%

2 4

Non essendovi altre incompatibilità a causa delle uscite, il passo 1 è terminato

Passo 2 (1,3,4,5,6) (1,2,3,4,5,6) (1,2,3,4,5,6) (1,3,5,6,7) 44 22

Algoritmo della suddivisione degli elementi della famiglia

di presunta compatibilità – Esempio 4

PASSO 3 – da ripetere fino a che non siano più presenti

incompatibilità Stati Suddivisione

Stati seguenti Famiglia

i incompatibili elemento

Passo 3 (1,2,3,4,5,6) (1,3,5,6,7)

1 (1,2,3,4,5,6) (1,1,3,1,-,3) nessuna

'

1 (1,3,5,6,7) (1,3,-,3,3) nessuna

' / /

~ ~

2 7 1,2 5

' (

2 (1,2,3,4,5,6) (2,2,4,4,7,-)

' / /

~ ~ (1,2,3,4,6) (5,6)

4 7 3,4 5

'

Passo2 (5,6) (1,3,5,6,7) (1,2,3,4,6) (1,3,5,6,7)

Passo 3

3 (1,2,3,4,6) (-,5,-,5,5) nessuna

'

4 (1,2,3,4,6) (6,-,6,-,6) nessuna

' / /

~ ~

2 7 5,7 1

'

2 (1,3,5,6,7) (2,4,7,-,7) (5,6,7) (1,3,6)

' / /

~ ~

7 5,7 3

4 '

Passo2 (1,3,6) (1,2,3,4,6) (1,2,3,4,6) (5,6,7)

Passo 3

3 (5,6,7) (5,5,5) nessuna

'

4 (5,6,7) (6,6,-) nessuna

'

3 (1,3,6 (-,-,5) nessuna

'

4 (1,3,6) (6,6,6) nessuna

'

Algoritmo della suddivisione degli elementi della famiglia di

presunta compatibilità – Esempio 4

Š Famiglia degli insiemi compatibili massima

(1,2,3,4,6) (5,6,7)

Š Verifica Stato seguente Incluso in uscita

i

1 (1,2,3,4,6) (1,1,3,1,3) (1,2,3,4,6) 1

(

2 (1,2,3,4,6) (2,2,4,4,-) (1,2,3,4,6) 2

(

3 (1,2,3,4,6) (-,5,-,5,5) (5,6,7) 4

(

4 (1,2,3,4,6) (6,-,6,-,6) (5,6,7) e (1,2,3,4,6) -

(

1 (5,6,7) (-,3,3) (1,2,3,4,6) -

(

2 (5,6,7) (7,-,7) (5,6,7) 4

(

3 (5,6,7) (5,5,5) (5,6,7) 3

(

4 (5,6,7) (6,6,-) (5,6,7) e (1,2,3,4,6) 4

(

Š Sarebbe stato possibile procedere anche in altro ordine 46 23

Macchina incompletamente specificata

Š Paull Unger esteso

Le relazioni di compatibilità possono essere ricavate

) 7DEHOOD GHOOH LPSOLFD]LRQL

dalla

viene compilata come avviene nel caso delle macchine

* completamente specificate

Ogni elemento della tabella contiene:

) Il simbolo di compatibilità se gli stati corrispondenti sono

* compatibili

Il simbolo di non compatibilità se gli stati corrispondenti

* non sono compatibili

Le coppie di stati a cui si rimanda la verifica se non è

* possibile stabilire la compatibilità

Macchina incompletamente specificata

Š Passi:

Si barrano le caselle i cui stati seguenti sono

1. incompatibili (piuttosto che disequivalenti)

Si determinano le coppie compatibili come per le

2. macchine complete

6LFRVWUXLVFHODIDPLJOLDGHJOLLQVLHPLPDVVLPL )

+-, Si prendono in esame ordinatamente tutti gli stati della

1. macchina e, per ciascuno di essi (q):

. si aggiungono ad F tutte le coppie di compatibilità di q;

. q viene confrontato con tutti gli stati di ciascun elemento E di F e se

compatibile con tutti, E si accresce di q, se compatibile solo con

alcuni, si genera un nuovo elemento di F

. si eliminano da F gli elementi inclusi in altri 24

Esempio: macchina incompletamente specificata

Š Esempio

Ricerca degli stati compatibili

) Compatibili!

Esempio: macchina incompletamente specificata

Š Ricerca degli insiemi di compatibilità massimi

Costruzione del GRAFO DI COMPATIBILITA’

1. I nodi sono gli stati

/ Sugli archi sono specificati gli stati “condizionanti”

/ 25

Corso di Reti Logiche

Macchine Sequenziali

Dipartimento di Informatica e Sistemistica

Università Degli Studi di Napoli Federico II 1

Macchina Asincrona 1

Macchina Asincrona

Macchina Asincrona 2

Alee sequenziali

Š Affliggono le macchine sequenziali

Š Derivanti da alee combinatorie transitorie

$OHHSHU&RUVHFULWLFKH

Š Si creano alee multiple a causa della codifica adottata

$OHH(VVHQ]LDOL

Š Intrinseche in alcune reti sequenziali, dipendenti dalla

struttura matematica della rete

Alee di Regime 3

Alee di Regime

Alea essenziale - 1

Š Affligge molte reti asincrone

'HILQL]LRQH:

Š 3 variazioni consecutive dell’ingresso

x a partire dallo stato S portano la rete in uno stato S

i k

diverso da quello S in cui giunge dopo un'

unica

j

variazione di x.

&DXVH

Š la variazione di una variabile interna (stato),

conseguente ad una variazione di un ingresso, si

propaga nella rete più rapidamente del cambiamento

dell'

ingresso che l'

ha generata.

5LPHGL

Š Aggiunta di ritardi sulle linee di reazione

1RWH:

Š dipende dalla struttura della tabella, ecco perché

HVVHQ]LDOH;

si dice non si elimina, se ne eliminano gli

effetti 8 4

Alea essenziale - 2

8QHVHPSLR 9

Alea essenziale - 3

8QHVHPSLRVLPXOD]LRQH

Nella rete a fianco (si vedrà che trattasi

di un flip flop T) mancano ritardi su

linee di reazione (mancano anche su

flip flop RS, ma lì non c’è alea)

Š Dimensionamento

Tutti i ritardi = 5 u.t.

Ritardo di Tn = 20 u.t.

Š Dinamica

T sale, lo segue y2

y2 torna a 0 prima che scenda T n

È come se T=0 con stato 01 sale y1

quando Tn scende è tardi, y2 scende e quindi si

ottiene 10 10 5

Alea essenziale - 4

6ROX]LRQH 11

Alee di Uscita 12 6

Alee di Uscita 13

Macchine ad Ingressi Impulsivi

Richiamiamo la definizione: 14 7

Macchine ad Ingressi Impulsivi

,OSXQWRGL

• IXQ]LRQDPHQWR GL

PXRYHVXOOD

WDEHOODFRPH

LQGLFDWRLQILJXUD

/¶LPSXOVRGHYH

• FRPXQTXH DYHUH

GXUDWDVXIILFLHQWH

DJDUDQWLUH

O¶HYROX]LRQH 15

Macchine ad Ingressi Impulsivi

/¶LPSXOVR

• GHYH

DYHUHXQD

GXUDWD

DSSHQD

VXIILFLHQWH

DFKH

DYYHQJD

O¶DFTXLVL]L

RQHGHO

QXRYR

VWDWR 16 8

Macchine ad Ingressi Impulsivi 17

Macchine ad Ingressi Impulsivi 18 9

Macchine ad Ingressi Impulsivi 19

Registri e Flip-Flop 20 10

Registro fondamentale a sincronizzazione esterna

21

Registro fondamentale a sincronizzazione esterna

• Ipotesi di natura impulsiva degli ingressi

• Rimuovendo l’ipotesi di natura impulsiva… (segnale abilitante) 22 11

Registro fondamentale autosincronizzato

(puramente impulsivo) 23

Registro fondamentale autosincronizzato

(puramente impulsivo)

• La natura impulsiva dell’ingresso impedisce RS=1 e garantisce la

distanza di sicurezza tra i due impulsi. 24 12

Tempificazione nel caricamento dei registri 25

ODWFK

Tempificazione nel caricamento dei registri: 26 13

ODWFK

Tempificazione nel caricamento dei registri:

• Il funzionamento di un'

apparecchiatura con registro latch e

sequenza non impulsiva resta aleatorio per molte

applicazioni, in quanto, non essendo possibile prevedere

con esattezza l'

istante di variazione di un livello e la durata

effettiva dell'

impulso; V LOUHJLVWURFDWWXULXQLQJUHVVRGDWR

• E’ possibile che per

diverso da quello previsto in fase di progetto. Il modello

UHDOPHQWH

latch è pertanto valido solo per sequenze

LPSXOVLYHo per applicazioni particolari.

Vantaggi:

• È meno complesso dei modelli che seguono. 27

Problemi di tempificazione con i Latch

' 4 Y

4

&

Clock Clock

Y 28 14


PAGINE

249

PESO

3.45 MB

AUTORE

Sara F

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Reti logiche
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Sara F di informazioni apprese con la frequenza delle lezioni di Reti logiche e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Pescapè Antonio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Reti logiche

Reti logiche - Esercizi risolti e proposti di Reti Logiche
Esercitazione
Reti Logiche – Boole
Dispensa
Reti Logiche - prova d'esame 2004
Esercitazione
Reti Logiche - riconoscitore di codice 8-4-2-1
Esercitazione