Microelettronica -...

61
S. Salvatori - Microelettronica – marzo 2015 – (1 di 61) Microelettronica Richiami di elettronica digitale per i sistemi a microprocessore Dentro la CPU: registri e macchine sequenziali prof. Stefano Salvatori A.A. 2015/2016 Eccetto dove diversamente specificato, i contenuti di questo documento sono rilasciati sotto Licenza Creative Commons Attribuzione 3.0 Italia. Corso introduttivo di progettazione di sistemi embedded

Transcript of Microelettronica -...

Page 1: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (1 di 61)

Microelettronica

Richiami di elettronica digitaleper i sistemi a microprocessore

Dentro la CPU:registri e macchine sequenziali

prof. Stefano Salvatori

A.A. 2015/2016

Eccetto dove diversamente specificato, i contenuti di questo documento sono rilasciati sotto Licenza Creative Commons Attribuzione 3.0 Italia.

Corso introduttivo di progettazione di sistemi embedded

Page 2: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (2 di 61)

Sommario

● CPU come sistema

– schema a blocchi● Registri

● Macchine sequenziali

– Mealy

– Moore

– diagramma degli stati

Page 3: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (3 di 61)

Macchina di calcolo automatica

● la CPU esegue le diverse istruzioni attuando una sequenza di operazioni elementari– fetch– decode– execute

● essa stessa saràuna macchina ditipo sequenziale

● vediamo i blocchifondamentali di cuisarà composta

ADD M3, M2, M1

Page 4: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (4 di 61)

Schema a blocchi

di una generica

CPU

Page 5: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (5 di 61)

Elementi fondamentali di una CPU

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

BU

S I

NT

ER

NO

...

SE

GN

AL

I D

I C

ON

TR

OL

LO

SR

incrementer

Page 6: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (6 di 61)

Elementi fondamentali di una CPU

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

...

SR

incrementer

● Unità di calcolo– operazioni logiche, aritmetiche e shift di operandi

● Unità di controllo– decoder– multiplexer

● Registri– per i dati– per l'istruzione– per puntare

all'istruzione succ.

Page 7: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (7 di 61)

Concentriamoci sui registri

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

...

SR

incrementer

● Unità di calcolo– operazioni logiche, aritmetiche e shift di operandi

● Unità di controllo– decoder– multiplexer

● Registri– per i dati– per l'istruzione– per puntare

all'istruzione succ.

Page 8: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (8 di 61)

Concentriamoci sui registri

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

...

SR

incrementer

● Come minimo– Program Counter– Registro per il codice operativo dell'istruzione– registri per la ALU– interfaccia per

i bus esterni● con buffer

Page 9: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (9 di 61)

Registri

Page 10: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (10 di 61)

Registri

● Un registro è un elemento di memoria

– in grado di memorizzare un insieme di n bit

– composto da una serie di elementi bistabili

– l'informazione memorizzata in un registro prende il nome di parola

● 4 bit: nibble● 8 bit: byte● 16 bit: half word● 32 bit: word● 64 bit: double word● ...

clockenable

Din

Dout

regi

ster

E' spesso necessario avere un ingresso di abilitazione perché il clock è comune

Page 11: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (11 di 61)

Registri

● Modalità di lettura e scrittura dei dati

– parallelo

– seriale

● Operazioni sui dati

– scorrimento a destra

– scorrimento a sinistra

– rotazione

scrittura

lettura

letturascrittura

Page 12: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (12 di 61)

Registro parallelo

● Un registro parallelo è composto da più flip/flop di tipo D a cui giunge il medesimo segnale di clock

clock

D

Q

tempo di risposta

Page 13: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (13 di 61)

Registro parallelo

● Ricordiamo i principali parametri dinamici di un flip/flop

tempo di risposta

clock

Data in

Data out

generalmente 0

Page 14: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (14 di 61)

Registro parallelo

● Abilitazione per la lettura

Se è necessario il segnale di abilitazione basterà usare una AND quale “interruttore” logico

clockenable

clock-out

Page 15: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (15 di 61)

Registro a scorrimento

● In uno shift register l'ingresso di un flip/flop dipende dall'uscita del precedente

scorrimento a destra

Page 16: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (16 di 61)

Registro a scorrimento

scorrimento bidirezionale

per rotazione (e programmabilità) lo schema si complica ulteriormente

Page 17: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (17 di 61)

Operazione di shift

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

...

SR

incrementer

● Gli operandi in ingresso alla ALU possono essere elaborati con operazioni di shift (moltiplicazione o divisione per potenze di 2)

ALU

shifter

Page 18: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (18 di 61)

Shift logico e shift aritmentico

● Logical Shift Left:

● Logical Shift Right:

0

b7 b6 b5 b4 b3 b2 b1 b0 0

b7 b6 b5 b4 b3 b2 b1 b0

a sinistra

a destra

C

C

LSL

LSR

Page 19: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (19 di 61)

Shift logico e shift aritmentico

● Arithmetic Shift Left:

● Arithmetic Shift Right:

0 a sinistraC≡ LSL

ASR b7

conserva il segno

a destraC

b7 b6 b5 b4 b3 b2 b1 b0

b6 b5 b4 b3 b2 b1 b0

Page 20: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (20 di 61)

Rotazione

● Senza carry:

● Con carry: C a sinistra

a destra

a sinistra

a destra

b7 b6 b5 b4 b3 b2 b1 b0

b7 b6 b5 b4 b3 b2 b1 b0

b7 b6 b5 b4 b3 b2 b1 b0

b7 b6 b5 b4 b3 b2 b1 b0C

Page 21: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (21 di 61)

La soluzione col

Barrel shifter

Page 22: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (22 di 61)

Barrel shifter

D3

D2

D1

D0

Q3

Q2

Q1

Q0

right 3 bit

right 2 bit

right 1 bit

no shift (copy)

left1 bit

left2 bit

left3 bit

D3D

2D

1D

0

Q3Q

2Q

1Q

0

Page 23: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (23 di 61)

Barrel shifter

D3

D2

D1

D0

Q3

Q2

Q1

Q0

right 3 bit

right 2 bit

right 1 bit

no shift (copy)

left1 bit

left2 bit

left3 bit

D3 D2 D1 D0

Q3 Q2 Q1 Q0

shift left1 bit

Page 24: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (24 di 61)

Barrel shifter

D3

D2

D1

D0

Q3

Q2

Q1

Q0

right 3 bit

right 2 bit

right 1 bit

no shift (copy)

left1 bit

left2 bit

left3 bit

D3 D2 D1 D0

Q3 Q2 Q1 Q0

shift right2 bit

Page 25: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (25 di 61)

Barrel shifter

D3

D2

D1

D0

Q3

Q2

Q1

Q0

right 3 bit

right 2 bit

right 1 bit

no shift (copy)

left1 bit

left2 bit

left3 bit

D3 D2 D1 D0

Q3 Q2 Q1 Q0

rotate1 bit

come vanno scelte le diagonali per una rotazione?

Page 26: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (26 di 61)

Un esempio

come vanno scelte le diagonali per una rotazione?

● ADD r1, r0, r0 LSL#2

– r1 := r0 + r0 * 4

– r1 := 5 x r0 ALU

shifter LSL 2 bit

ADD

r0

r0

Moltiplicazione per 5!

Che istruzione aggiungiamo per avere x10?

Page 27: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (27 di 61)

Un esempio

● ADD r0, r0 LSL#2

– r0 := r0 + r0 * 4

– r0 := 5 x r0

come vanno scelte le diagonali per una rotazione?

ALU

shifter LSL 2 bit

ADD

r0

r0

Con un Cortex-M (istruz. a 2 indirizzi) :

Page 28: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (28 di 61)

Interfacciamento

su bus

Page 29: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (29 di 61)

Interfacciamento su bus

ALU

REG

REG

MDR

PC

MAR

FUNZ

AI BUSESTERNI

DECODER

IR

R0

R1

Rn

BANCODIREGISTRI

...

SR

incrementer

● Diversi registri devono essere interfacciati in scrittura ai bus sia esterni che interni → att.ne al conflitto

Page 30: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (30 di 61)

Buffer

● TristateTM è un marchio della National Semiconductors (oggi acquisita da TI)

IN OUT

enable

tempo

stato L o H stato L o Hstato adalta impedenza

Page 31: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (31 di 61)

Buffer

BU

S

OE

OE

OE

OEclock

OutputEnable

Page 32: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (32 di 61)

Interfacciamento su bus

QD

QD

QD

QD

QD

OE

Page 33: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (33 di 61)

Schema buffer

● Occorre modificare il pilotaggio di un inverter CMOS

OE

data

VDD

VSS

OUT

Page 34: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (34 di 61)

Schema buffer bidirezionale

OE

data

VDD

VSS

IN/OUT

datain

non serve il buffer: è la logica di controllo ad acquisire o meno il dato

Page 35: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (35 di 61)

Macchine

sequenziali

Page 36: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (36 di 61)

Macchine sequenziali

● Il valore dell'uscita dipende dalla sequenza di ingressi ricevuti fino all'istante corrente

a) → serve una memoria (stato)

b) l'uscita è ottenuta elaborando gli ingressi unitamente allo stato della macchina

Page 37: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (37 di 61)

Esempio: sommatore seriale “bit a bit”

● Stato: riporto d'uscita (all'inizio '0')

All'i-esimo fronte di clock, arriva in ingresso una coppia di bit del numero da sommare;

l’uscita è pari al bit i-esimo della somma

sommatore

1 bit

ai

bi

si

cout

cin

M

ck

a0

a1

a2

a3

a4

a5

b0

b1

b2

b3

b4

b5

s0

s1

s2

s3

s4

s5

ck

Page 38: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (38 di 61)

Schema di una macchina generica

● La rete combinatoria

– calcola l'uscita

– e lo stato futuro

rete

combinatoria

x0..n

y'0..k

M

ck

z0..m

y0..k

stato attualestato futuro

La macchina cambia stato ad ogni fronte di clock → sincrona

Page 39: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (39 di 61)

Macchina di Mealy

● Con questo tipo, in pratica la rete combinatoria sarà composta da due sezioni di “calcolo”:

– uscita

– stato

x0..n

y'0..k

M

ck

z0..m

y0..k

L'uscita cambia “immediatamente” al variare dell'ingresso

calcolo uscitacalcolo

stato

Macchina di Mealy

Page 40: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (40 di 61)

Macchina di Mealy

● Caratteristiche:

– reazione rapida agli ingressi

– l'uscita si ha nel medesimo ciclo di clock senza dover attendere la sua fine

x0..n

y'0..k

M

ck

z0..m

y0..k

CL

CL

questo può causare problemi quando si pensa a circuiti sincroni connessi in reazione

Page 41: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (41 di 61)

Macchine di Moore

● Per questo possiamo pensare a una macchina in cui l'uscita dipenda solo dallo stato

x0..n

y'0..k

M

ck

z0..m

y0..k

CL

CL

calcolo uscita

calcolo stato

Macchina di Moore

Page 42: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (42 di 61)

Mealy versus Moore

● Una macch. di Mealy tende ad avere meno stati

– diverse uscite (che dipendono dall'ingresso) a parità di stato

● Una macch. di Moore tende ad essere più sicura

– le uscite cambiano solo al fronte di clock

– buono per connessioni in retroazione

● Una macch. di Mealy reagisce più prontamente agli ingressi

– non bisogna attendere il fronte di clock di sincronismo

– la macch. di Moore richiede più logica per l'elaborazione dell'uscita in funzione dello stato e si avrà un ritardo ulteriore dovuto a tale logica

Page 43: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (43 di 61)

Macchina di Mealy sincronizzata

In realtà abbiamo una macch. di Moore ma spesso quest'ottica semplifica il progetto

x0..n

y'0..k

M

ck

y0..k

CL

My'

0..kz

0..mCL

Page 44: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (44 di 61)

Diagramma degli

stati

Page 45: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (45 di 61)

Diagramma degli stati

● Simbologia:

● ingressi & uscite

– sulle transizioni e/o stati a seconda della macchina

stato

transizione

Page 46: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (46 di 61)

Riassumendo

● Le macch. di Mealy hanno, per ogni arco, un simbolo di entrata e uno di uscita.

● Nelle macch. di Moore l’uscita è invece già codificata nel valore dello stato in cui si trova la macchina.

● È possibile trasformare una macchina di Mealy in una di Moore e viceversa, solitamente quelle di Moore hanno più stati.

● In una macch. di Mealy si ha una uscita durante ciascuna transizione.

● In una macch. di Moore si ha una uscita dopo che è avvenuta la transizione e questa uscita dipende solo dal nuovo stato della macchina.

● Moore produce quindi un primo output, associato allo stato iniziale, non presente in un automa di Mealy

Page 47: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (47 di 61)

Un esempio

S0

reset

Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Cerchiamo una soluzione di tipo Mealy

stato fondamentale

“attesa”

Page 48: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (48 di 61)

Un esempio

S0

reset a / 0

S1

Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Se arriva 'a' potrei avere l'inizio della sequenza → ho un cambiamento di stato

Mealy

“è arrivato” 'a'

Page 49: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (49 di 61)

Un esempio

S0

reset a / 0

S1

b || c / 0Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Viceversa, se arriva 'b' o 'c' aspetto la sequenza → rimango nello stesso stato

Mealy

Page 50: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (50 di 61)

Un esempio

S0

reset a / 0

S1

S2

b || c / 0Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

b / 0

Se in S1 arriva 'b' ho già parte della sequenza → cambio stato

“è arrivato” 'a-b'

Page 51: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (51 di 61)

Un esempio

S0

reset a / 0

S1

S2

b / 0

b || c / 0Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

Con 'c' la sequenza è “rotta” → ritorno in quello di “attesa”

c / 0

Page 52: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (52 di 61)

Un esempio

S0

reset a / 0

S1

S2

b / 0

b || c / 0Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

… o rimango con un nuovo 'a' (la sequenza può essere ricominciata)

a / 0c / 0

Page 53: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (53 di 61)

Un esempio

S0

reset a / 0

S1

S2

b / 0

b || c / 0

c / 1

Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

Se in S2 arriva 'c': sequenza OK:esce '1' e torno in “attesa” di una nuova

a / 0c / 0

Page 54: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (54 di 61)

Un esempio

S0

reset a / 0

S1

S2

b / 0

b || c / 0

c / 1

b / 0

Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

a / 0

Con 'b' la sequenza è interrotta

c / 0

Page 55: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (55 di 61)

Un esempio

S0

reset a / 0

S1

S2

b / 0

b || c / 0

c / 1

b / 0

Automa in grado di riconoscere una sequenza di simboli:

a → b → c : esce 1

altrimenti esce 0

ing. / usc.

Mealy

a / 0c / 0

Con 'a' torno a S1a / 0

FINE!

Page 56: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (56 di 61)

Un esempio

S00

reset a

S10

S20

b

b || c

c

a

c

Possiamo passare alla macchina equivalente di Moore

statousc.

Moore:4 stati

a

S31

c || b

a

b

Page 57: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (57 di 61)

Secondo esempio

Automa che riceve 3 possibili simboli: a, b, c.

Esce '1' se il simbolo attuale coincide col precedente;

'0' altrimenti.

Mealy

Fare per esercizio

Page 58: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (58 di 61)

Secondo esempio

Sf

reset

a / 0

A

B

b / 0a / 0

c / 0

Automa che riceve 3 possibili simboli: a, b, c.

Esce '1' se il simbolo attuale coincide col precedente;

'0' altrimenti.

Mealy

a / 1

b / 1

C

b / 0c / 1

a / 0

b / 0c / 0

c / 0

Page 59: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (59 di 61)

Secondo esempio

Automa che riceve 3 possibili simboli: a, b, c.

Esce '1' se il simbolo attuale coincide col precedente;

'0' altrimenti.

Quale sarebbe la soluzione di tipo Moore?

Page 60: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (60 di 61)

Secondo esempio con Moore

Sf0

reset

a

A00

A11

a

Automa che riceve 3 possibili simboli: a, b, c.

Esce '1' se il simbolo attuale coincide col precedente;

'0' altrimenti.

ho bisogno di cadere in uno stato che mi dia l'uscita pari a 0

a

b

b

B00

esercizio:completare il diagramma

Page 61: Microelettronica - ssalvatori.altervista.orgssalvatori.altervista.org/Microelettronica-files/Slide/4_Reg_Shift... · una macchina di tipo sequenziale ... di clock → sincrona. S.

S. Salvatori - Microelettronica – marzo 2015 – (61 di 61)

Domande?

[email protected]