Logické obvody - sekvenční Formy popisu, konečný automat Příklady návrhu

MIKROPROCESORY PRO VÝKONOVÉ SYSTÉMY MIKROPROCESORY PRO VÝKONOVÉ SYSTÉMY

Logické obvody - sekvenční

Formy popisu, konečný automat Příklady návrhu

České vysoké učení technické Fakulta elektrotechnická A1B14MIS Mikroprocesory pro výkonové systémy 03

Ver.1.20

J. Zděnek, 2013 1

Logický sekvenční obvod • •

Logický sekvenční obvod (LSO) popsán stavovým diagramem, rovnicemi, tabulkami, HDL jazykem Vstupní, výstupní i vniřní (qi) proměnné nabývají pouze hodnot 0 nebo 1 Vstupní stav

x1 xn

Výstupní stav

O

I

LSO q1 qk

y1

S

ym Vnitřní stav

•

Hodnoty všech výstupních proměnných jsou v každém časovém okamžiku určeny hodnotami vstupních proměnných ve stejném okamžiku ale též hodnotami vstupních proměnných předcházejících (LSO má vnitřní paměť)

A7B14SAP Struktura a architektura počítačů

2

Konečný automat (FSA), přechodová a výstupní funkce • • •

•

Abstraktní model sekvenčního obvodu – konečný automat (FSA – Finite State Automaton nebo také FSM – Finite State Machine) Konečný automat – konečný počet vstupních, vnitřních a výstupních stavů Danou kombinaci vstupních, vnitřních a výstupních proměnných nazveme vstupní, vnitřní a výstupní stav a označíme I i , S k , O j Přechodová funkce:

S t 1  f (S t , I t ) •

S t 1 , S t , I t

•

Výstupní funkce:

– vnitřní následující, vnitřní a vstupní současný stav

Ot  g ( S t , I t ) •

Ot , S t , I t

– výstupní, vnitřní a vstupní současný stav

A1B14MIS Mikroprocesory pro výkonové systémy 03

3

Obecný model logického sekvenčního obvodu (Huffmann)

LSO - Logický sekvenční obvod

I x1,… ,xi

Logický kombinační obvod

S q1,… ,qk

Ot  g ( S t , I t ) O y1,… ,yj

S t 1  f (S t , I t ) Paměťová část


4

Rozdělení LSO •

Podle časové reakce na změnu vstupních proměnných • Asynchronní – změna stavu LSO po změně vstupních proměnných ihned (resp. s malým zpožděním v důsledku reakce vnitřních obvodů LSO). • Synchronní – změna stavu LSO synchronizována vnějšími synchronizačními impulsy (tzv. hodiny, clock). LSO jsou navrhovány většinou jako synchronní – snadnější kontrola vnitřních signálů LSO.

•

Podle způsobu výpočtu přechodové a výstupní funkce

LKO

• Automat typu Mealy

S t 1  f (S t , I t ) Ot  g (S t , I t )

• Automat typu Moore

S t 1  f (S t , I t )

Ot  g ( S t )

• Autonomní automat (např. čítače,… )

S t 1  f (S t )

Ot  g ( S t )


5

Synchronní FSA – typu Mealy

S t 1  f (S t , I t )

Budicí funkce

Ot  g ( S t , I t )

Stavový registr

D LKO1

Logika výstupů

Q LKO2

O

C

I clk


6

Synchronní FSA – typu Moore

S t 1  f (S t , I t )

Budicí funkce

Ot  g ( S t )

Stavový registr

D LKO1

Logika výstupů

Q LKO2

O

C

I clk


7

Synchronní FSA – autonomní

S t 1  f (S t )

Budicí funkce

Ot  g ( S t )

Stavový registr

D LKO1

Logika výstupů

Q LKO2

O

C clk


8

Forma popisu LSO (FSA) •

Stavovým diagramem (State diagram) – forma orientovaného grafu

•

Soustavou rovnic

•

Tabulkami přechodů a výstupů

•

Některým programovacím jazykem

•

Vyjmenováním všech posloupností vstupů a výstupů (TO NE) nepraktické – nepoužívá se, vstupní posloupnost může být i nekonečné délky


9

Formy popisu FSA – typu Mealy Stavový diagram

Přechodová a výstupní funkce

„ “ Přechod ze stavu v čase t do t+1 – „  “ Okamžité vytvoření výstupu – „:“ Současný výskyt stavu a vstupu –

I0/00 = 0/0

Přechod S0

I1/00 = 1/0

I0/01= 0/1 I0/00 = 0/0 I1/00 = 1/0

S2

S1

I1/00 = 1/0

Stav

Vstup

Výstup (umístěn u hran)


Si  I j  S k

Si  I j : Ok

S0  I 0  S0

S0  I 0 : O0

S0  I1  S1

S0  I1 : O0

S1  I 0  S0

S1  I 0 : O0

S1  I1  S2

S1  I1 : O0

S2  I1  S2

S2  I1 : O0

S 2  I 0  S0

S2  I 0 : O1 10

Formy popisu FSA – typu Mealy Stavový diagram

Tabulky přechodů a výstupů

I0/00 = 0/0

Tabulka přechodů

Přechod S0

I1/00 = 1/0

I0/01= 0/1 I0/00 = 0/0 I1/00 = 1/0

S2

I0

I1

S0

S0

S1

S1

S0

S2

S2

S0

S2

S1

Tabulka výstupů I1/00 = 1/0

Stav

Vstup

Si

Výstup (umístěn u hran)


Si

I0

I1

S0

O0

O0

S1

O0

O0

S2

O1

O0

11

Formy popisu FSA – typu Moore Přechodová a výstupní funkce

Stavový diagram

„ “ Přechod ze stavu v čase t do t+1 – „  “ Okamžité vytvoření výstupu – „:“

I0

I0

01

S3

Vstup

00 I1

I0

S1

I1 I0

Stav

S0

Současný výstkyt stavu a vstupu –

S2

00

I1 00

I1

Výstup (umístěn u uzlu)


Si  I j  S k

Si : Ok

S0  I 0  S0 S0  I1  S1 S1  I 0  S0 S1  I1  S2 S2  I1  S2 S 2  I 0  S3 S3  I1  S1 S3  I 0  S 0

S0 : O0 S1 : O0 S 2 : O0 S3 : O1

12

Formy popisu FSA – typu Moore Stavový diagram

Tabulky přechodů a výstupů

I0

I0

01

S3

Vstup

00 I1

I0

S1

I1 I0

Stav

S0

Tabulka přechodů

S2

00

Si

I0

I1

S0

S0

S1

S1

S0

S2

S2

S3

S2

S3

S0

S1

Tabulka výstupů

I1 00

I1

Výstup (umístěn u uzlu)


Si

Oi

S0

O0

S1

O0

S2

O0

S3

O1 13

Postup návrhu logického sekvenčního obvodu (schema) •

Návrh obvodového řešení zápisem schematu • Formulace zadání – slovní popis • Stavový diagram (orientovaný graf přechodů a výstupů) • Tabulky přechodů a výstupů • Kódování vnitřních stavů a výstupů • Zakódované tabulky přechodů a výstupů • Budící funkce a funkce výstupů • Minimalizace budící funkce a funkce výstupů (K–mapy) • Návrh z hradel (z požadovaných typů) – schema • [Logická simulace] • Realizace z hradel • [Časová simulace po realizaci (umístění do hradlového pole)] • Výpočet (ověření) maximální povolené frekvence synchronizačního signálu (následující přednáška) • Ověření v aplikaci


14

Postup návrhu logického sekvenčního obvodu (HDL) •

Návrh obvodového řešení zápisem v HDL (VHDL, Verilog) • Formulace zadání – slovní popis • Stavový diagram (orientovaný graf přechodů) • Zápis programu v HDL (Hardware Description Language) • Syntéza zapojení (překlad programu v HDL) • [Logická simulace] • Realizace z hradel (z prostředků hradlového pole)(Place & Route) • [Časová simulace po realizaci (umístění do hradlového pole)] • Výpočet (ověření) maximální povolené frekvence synchronizačního signálu (následující přednáška) • Ověření v aplikaci


15

Paměťový člen – záchytný registr (Latch) S

Q

R

Q

R

Q

S

Q

R–S Latch (NOR)

R–S Latch (NAND)

Ri

Si

Qi 1

Ri

Si

Qi 1

0

0

!!!

0

0

Qi

0

1

1

0

1

1

1

0

0

1

0

0

1

1

Qi

1

1

!!!

!!! – zakázaný stav A1B14MIS Mikroprocesory pro výkonové systémy 03

16

Paměťový člen – záchytný registr (Latch) S

Q

Q

R Clk R–S Latch (Clock enable)

X – nezáleží

Ri

Si

Clk

0

0

1

Qi 1 Qi

0

1

1

1

1

0

1

0

1

1

1

!!!

X

X

0

Qi


!!! – zakázaný stav 17

Paměťový člen – záchytný registr (D – Latch) Symbol

D

Q

Q

D

Q

C

Q

Clk D Latch (Clock enable)

Qi 1

Di

Clk

0

1

0

1

1

1

X

0

Qi

X – nezáleží


18

Paměťový člen – D klopný obvod (D – Flip-Flop) Symbol

D

Q

Q Q

Q D Flip-Flop

Qi 1

Di

Clk

D

0

0

Clk

1

 

X

0

X

1

Qi Qi

1

 – zápis řízený náběžnou hranou A1B14MIS Mikroprocesory pro výkonové systémy 03

19

Paměťový člen – D klopný obvod (D – Flip-Flop) Set

Symbol D

SET

Q

Q CLR

Q

Q D – Flip-Flop

Qi 1

Reset i

Set i

Di

Clk

0

0

0



0

0

0

1



1

0

0

X

0

0

0

X

1

Qi Qi

 – zápis řízený náběžnou hranou

0

1

X

X

1

asynchronní nulování/nastavení

1

0

X

X

0

D Clk Reset


20

Synchronní 2bitový binární čítač Navrhněte synchronní konečný automat (FSA – Finite State Automaton) typu čítač. Čítač čítá v binárním kódu a je 2bitový. Automat navrhněte s asynchronním nulováním.

FSA Si clk

q1 O (Outputs) q0

clk q0 q1 0 1 2 3 0 1 2 3 0 1 2 3 A1B14MIS Mikroprocesory pro výkonové systémy 03

21

Synchronní 2bitový binární čítač Co máme navrhnout?

Budicí funkce

Stavový registr

D LKO1 I

Logika výstupů

Q LKO2

0

C

clk


22

Synchronní 2bitový binární čítač clk

Stavový diagram I – Vstupy (Inputs) (nemá) O – Výstupy (Outputs) Si – i-tý stav

1

03

q0

00 S0

S3

q1

1

S1

0 1 2 3 0 1 2 3 0 1 2 3

01 Tabulka výstupů

Tabulka přechodů

Si

Oi

S0

O0

S1

O1

S3

S2

O2

S0

S3

O3

Si

Si+1

S0

S1

S1

S2

S2 S3

1


S2

02

1

23

Synchronní 2bitový binární čítač Tabulka přechodů

Si

Si+1

S0

S1

S1

S2

S2

S3

S3

S0

Budicí funkce

d0

q0

Si+1

Kódování stavů

Stavový registr d1

q1

Si

D

Q

q1

D

Q

q0

Si

q1

q0

d1

d0

Si+1

S0

0

0

0

1

S1

S1

0

1

1

0

S2

S2

1

0

1

1

S3

S3

1

1

0

0

S0

clk Zpětná vazba


24

Synchronní 2bitový binární čítač Tabulka výstupů Si

OI

S0

O0

S1

O1

S2

O2

S3

O3

Stavový registr d1 d0

D D

Q Q

Si Kódování výstupů Si

q1

q0

y1

y0

Oi

S0

0

0

0

0

O0

S1

0

1

0

1

O1

y1

S2

1

0

1

0

O2

y0

S3

1

1

1

1

O3

Logika výstupů q1 q0

Oi

clk

S i = Oi


25

Synchronní 2bitový binární čítač d1

q0 1

q1

0

11

2

3

d0

q1

Minimalizace

d1  q1 q0  q1 q0  XOR

q0 10

1

12

3

d 0  q0

y1  q1 y0  q0


26

Synchronní 2bitový binární čítač Realizace

d1

D

SET

CLR

d0

D

SET

CLR

Q

q1

y1

Q

Q

q0

y0

Q

clk reset


27

Synchronní 2bitový binární čítač Co jsme navrhli?

Budicí funkce

Stavový registr

D LKO1

Logika výstupů

Q LKO2

C

clk


28

Synchronní 2bitový binární čítač Co jsme navrhli? Budící funkce

Stavový registr

d1

D

SET

CLR

d0

D

SET

CLR

Q

Logika výstupů

q1

y1

Q

Q

q0

y0

Q

clk reset

LKO1 A1B14MIS Mikroprocesory pro výkonové systémy 03

LKO2 29

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Navrhněte synchronní konečný automat (FSA – Finite State Automaton), který v proudu vstupních bitů detekuje posloupnost ‘110’. Při detekci každé takové posloupnosti automat vyšle na výstupu impuls. Automat navrhněte s asynchronním nulováním.

I (Inputs) x

FSA Si

O (Outputs) y

clk

(Moore)

clk

x y


30

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Co máme navrhnout?

Budicí funkce

Stavový registr

D LKO1 I

Logika výstupů

Q LKO2

0

C

clk


31

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) clk

Stavový diagram

I0

x

I – Vstupy (Inputs) O – Výstupy (Outputs)

I0

Si – i-tý stav

01

S3

I0

I1

S0

S0

S1

S1

S0

S2

S2

S3

S2

S3

S0

S1

00

I1

I0

S1

I1

Tabulka přechodů Si

S0

I0


S2

I1

y

00 Tabulka výstupů

I1 00

Si

Oi

S0

O0

S1

O0

S2

O0

S3

O1

32

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Tabulka přechodů Si

I0

I1

S0

S0

S1

S1

S0

S2

S2

S3

S2

S3

S0

S1

Si Kódování stavů Si S0

Budicí funkce

S1

Stavový registr

x d1

q1

d0

q0

Si+1

I

D

Q

q1

D

Q

q0

clk

S2 S3

q1

q0

x

d1

d0

Si+1

0

0

0

0

0

S0

0

0

1

0

1

S1

0

1

0

0

0

S0

0

1

1

1

0

S2

1

0

0

1

1

S3

1

0

1

1

0

S2

1

1

0

0

0

S0

1

1

1

0

1

S1

Zpětná vazba


33

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Tabulka výstupů Si

OI

S0

O0

S1

O0

S2

O0

S3

O1

Stavový registr d1 d0

D D

Q Q

Kódování Výstupů

Logika výstupů

Si

y

S0

0

S1

0

S2

0

S3

1

q1 q0

y

clk


34

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) q1 q0

d1 0 4

x

1

1

3

12

5

7

16

d1  q1 q0  q1 q0 x

q1 q0

d0

x

Minimalizace

1

0

1

4

5

1

3

12

7

6


d 0  q1 q0 x  q1 q0 x  q1 q0 x   x (q1 q0  q1 q0 )  q1 q0 x

y  q1 q0

35

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Realizace

d1

D

SET

CLR

x

d0

D

SET

CLR

Q

q1

Q

Q

q0

y

Q

clk reset


36

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Co jsme navrhli?

Budicí funkce

Stavový registr

D LKO1 I

Logika výstupů

Q LKO2

0

C

clk


37

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) Co jsme navrhli? Budící funkce

Stavový registr d1

D

SET

CLR

d0

x

D

SET

CLR

Q

Logika výstupů

q1

Q

Q

y

q0

Q

clk reset


LKO2 38

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) “C” int cBitStream3Decoder(int x_in, int reset){ // Moore type FSA, // Inputs: x_in, reset, Outputs: y_out enum {s0,s1,s2,s3}; static int stateReg=s0, nextState=s0, y_out; if(reset == TRUE){ stateReg = s0; nextState = s0; x_in = 0; } y_out = 0; stateReg = nextState; switch(stateReg){ case s0: if(x_in == 0); if(x_in == 1) nextState = s1; break; case s1: if(x_in == 0) nextState = s0; if(x_in == 1) nextState = s2; break; A1B14MIS Mikroprocesory pro výkonové systémy 03

case s2: if(x_in == 0) nextState = s3; if(x_in == 1); break; case s3: y_out = 1; if(x_in == 0) nextState = s0; if(x_in == 1) nextState = s1; break; default: // Error section y_out = 0; nextState = s0; }// switch() END return(y_out); }// cBitStream3Decoder() END

39

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) class JBitStream3Decoder { final int s0 = 0, s1 = 1, s2 = 2, s3 = 3; int stateReg = s0, nextState = s0; int yOut = 0; public JBitStream3Decoder() {// Constructor // empty } void setFsaReset (boolean reset){ stateReg = s0; nextState = s0; yOut = 0; } int jBitStream3Decoder(int xIn) { // Moore type FSA // Inputs: xIn, reset, Outputs: y_out yOut = 0; stateReg = nextState; switch (stateReg) { case s0: if (xIn == 0); if (xIn == 1) nextState = s1; break; A1B14MIS Mikroprocesory pro výkonové systémy 03

case s1: if (xIn == 0) nextState = s0; if (xIn == 1) nextState = s2; break; case s2: if (xIn == 0) nextState = s3; if (xIn == 1); break; case s3: yOut = 1; if (xIn == 0) nextState = s0; if (xIn == 1) nextState = s1; break; default: // Error section yOut = 0; nextState = s0; }// switch() END return (yOut); }// jBitStream3Decoder() END

Java

}// JBitStream3Decoder class END 40

Detektor posloupnosti bitů ‘110’ (FSA typu Moore) VHDL entity vBitStream3Decoder is Port ( clk : in STD_LOGIC; x_in : in STD_LOGIC; y_out : out STD_LOGIC; reset : in STD_LOGIC; q : out std_logic_vector(1 downto 0) ); end vBitStream3Decoder; architecture Behavioral of vBitStream3Decoder is type states is (s1,s2,s3,s4); signal stateReg, nextState: states:= s1; begin -- FSA - Finite State Machine process(clk, reset) begin if reset = '1' then stateReg <= s1; elsif clk'event and clk = '1' then stateReg <= nextState; end if; end process;

process(stateReg, x_in) -- State diagram definition begin nextState <= stateReg; case stateReg is when s1 => if x_in = '1' then nextState <= s2; end if; when s2 => if x_in = '0' then nextState <= s1; elsif x_in = '1' then nextState <= s3; end if; when s3 => if x_in = '1' then nextState <= s3; elsif x_in = '0' then nextState <= s4; end if; when s4 => if x_in = '1' then nextState <= s2; elsif x_in = '0' then nextState <= s1; end if;


when others => nextState <= stateReg; end case; end process; process(stateReg) -- Output function begin case stateReg is when s1 => y_out <= '0'; when s2 => y_out <= '0'; when s3 => y_out <= '0'; when s4 => y_out <= '1'; when others => null; end case; end process; end Behavioral;

41

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Navrhněte synchronní konečný automat (FSA – Finite State Automaton), který v proudu vstupních bitů detekuje posloupnost ‘110’. Při detekci každé takové posloupnosti automat vyšle na výstupu impuls. Automat navrhněte s asynchronním nulováním.

I (Inputs) x

FSA Si

O (Outputs) y

clk

(Mealy)

clk

x y A1B14MIS Mikroprocesory pro výkonové systémy 03

42

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Co máme navrhnout?

Budicí funkce

Stavový registr

D

Logika výstupů

Q

LKO1

LKO2

0

C

I clk

Budicí funkce

FSA Mealy

D LKO1 I

Srovnej vs FSA Moore A1B14MIS Mikroprocesory pro výkonové systémy 03

Stavový registr

Logika výstupů

Q LKO2

0

C

clk

43

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) clk

I0/00 = 0/0

Stavový diagram

x

I – Vstupy (Inputs) O – Výstupy (Outputs) Si – i-tý stav

y

S0

I1/00 = 1/0

I0/01= 0/1 I0/00 = 0/0 I1/00 = 1/0

S2

S1

Tabulka výstupů

Tabulka přechodů

I1/00 = 1/0

Si

I0

I1

S1

S0

O0

O0

S0

S2

S1

O0

O0

S0

S2

S2

O1

O0

Si

I0

I1

S0

S0

S1

S2


44

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Tabulka přechodů Si

I0

I1

S0

S0

S1

S1

S0

S2

S2

S0

S2

Si

Si+1

I

Kódování stavů Si Budicí funkce

S0

Stavový registr

x d1

q1

d0

q0

D

Q

q1

D

Q

q0

clk

S1 S2

q1

q0

x

d1

d0

Si+1

0

0

0

0

0

S0

0

0

1

0

1

S1

0

1

0

0

0

S0

0

1

1

1

0

S2

1

0

0

0

0

S0

1

0

1

1

0

S2

Zpětná vazba


45

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Tabulka výstupů

Si

I0

I1

S0

O0

O0

S1

O0

O0

S2

O1

O0

Si

I

O

Kódování výstupů Si Stavový registr d1

D

Q

d0

D

Q

Logika výstupů

S0

q1 q0

y

S1

clk

x


S2

q1

q0

x

y

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

0

46

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) q1 q0

d1 0 4

x

1

1

–

3

2

5

–

7

16

1

0

1

–

3

2

4

5

–

7

6

d 0  q1 q0 x q1 q0

y

x

d1  q1 x  q0 x q1 q0

d0

x

Minimalizace

0

1

–

3

12

4

5

–

7

6


y  q1 q0 x

47

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Realizace

d1

D

SET

CLR

x

d0

D

SET

CLR

Q

q1

Q

Q

q0

y

Q

clk reset


48

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Co jsme navrhli?

Budicí funkce

Stavový registr

D LKO1

Logika výstupů

Q LKO2

0

C

I clk


49

Detektor posloupnosti bitů ‘110’ (FSA typu Mealy) Co jsme navrhli? Budící funkce

Stavový registr

d1

D

SET

CLR

d0

x

D

SET

CLR

Q

Logika výstupů

q1

Q

Q

y

q0

Q

clk reset


LKO2 50

Časování – výpočet maximální hodinové frekvence •

Ovlivněno: • Technologií • Typy hradel • Počtem vstupů u hradel • Zatížením výstupů hradel (větvením) • Typem klopných obvodů • Délkou propojovacích vodičů (na plošném spoji,…) • Vzájemnou polohou vodičů (kvalita návrhu plošného spoje) • Rozmístěním součástek • Počtem zemnících a napájecích vrstev • Způsobem rozvodu napájení • Rozmístěním blokovacích kondezátorů • Dalšími vlivy ….. Podrobnosti další přednášku


51

MIKROPROCESORY PRO VÝKONOVÉ SYSTÉMY MIKROPROCESORY PRO VÝKONOVÉ SYSTÉMY

Logické obvody - sekvenční Formy popisu, konečný automat Příklady návrhu KONEC

České vysoké učení technické Fakulta elektrotechnická A1B14MIS Mikroprocesory pro výkonové systémy 03

52

Logické obvody - sekvenční Formy popisu, konečný automat Příklady návrhu

Recommend Documents