Digitální obvody. Doc. Ing. Lukáš Fujcik, Ph.D

Digitální obvody

Doc. Ing. Lukáš Fujcik, Ph.D.

Stavové automaty – enkódování „ „

Proces, který rozhoduje kolik paměťových prvků bude využito v paměťové části. Binární enkódování jje nejpoužívanější. jp j počet stavů

počet KO typu D

enkódovací kombinace

1

1

0a1

2 až 4

2

00,01,10 a 11

5 až 8

3

000,001,010,011, 100,101,110,111

9 až 16

4

0000 … 1111

17 až 32

5

00000 … 11111

33 až 64

6

000000 … 111111

Stavové automaty „

Enkódování stavových automatů

„

Existuje několik typu enkódování – binární, twohot, one-hot a další

Stav

Binární

One-hot

Two-hot

state0

000

00000001

00011

state1

001

00000010

00101

state2

010

00000100

01001

state3

011

00001000

10001

state4

100

00010000

00110

state5

101

00100000

01010

state6

110

01000000

10010

state7

111

10000000

01100

Stavové automaty „

Enkódování stavových automatů Defaultní nastavení - binární styl enkódování … Binárního enkódování „ Výhoda - nejmenší počet KO, KO 2N stavů „ Nevýhoda - vyžaduje více doplňkové logiky, je pomalejší „ Pro ASIC … One-hot enkódování „ Výhoda – nevyžaduje velké množství doplňkové logiky (téměř žád á llogika žádná ik – posuvný ý registr), i t ) je j rychlejší hl jší než ž bi binární á í enkódování „ Nevýhoda ý – největší j množství KO, pro každý ý stav vyžaduje y j 1 KO „ Pro FPGA … Two-hot enkódování „ Kompromis mezi binárním a one-hot stylem „ Pomocí N KO je možné vytvořit N(N-1)/2 stavů …

Stavové automaty „

Definování enkódování stavových automatů

type STATE_TYPE is (S1, S2, S3, S4, S5, S6); attribute ENUM_ENCODING: ENUM ENCODING: STRING; attribute ENUM_ENCODING of STATE_TYPE:type is "0000 0100 1000 1001 1010 1011"; signal present_state, next_state: STATE_TYPE;

Stavové automaty – nevyužité stavy „ „ „ „ „ „

„ „

Ne vždy jsou všechny stavy využity Binární enkódování - např. např 6 stavů => 23-6=2, 6=2 2 stavy nevyužity One-hot enkódování – např. 6 stavů => 26-6=58, 58 stavů nevyužito Může vzniknout problém, že se systém vlivem šumu, vnějších okolností dostane d nevyužitého do žitéh stavu t a užž se nikdy ikd nedostane d t z ttohoto h t stavu t – nepřípustné ří t é !!!! Stavový automat s ošetřením nevyužitých stavů se nazývá bezpečný stavový automat (Safe Finite-State-Machine) Návrh bezpečného stavového automatu „ Je potřeba přejít z nevyužitého stavu do definovaného stavu a definovat všechnyy výstupní ý p signály g y v nevyužitém y stavu when others => next_state <= st0; vystup1 <= …; ; vystup2 <= …; Jelikož typ state je výčtový, pak může být s tímto popisem v některých návrhových systémech problém Řešení – použít jiný popis stavového automatu

Stavové automaty – nevyužité stavy „

Jiný popis stavového automatu – explicitně definované signály present_state a next state next_state

Architecture … … constant idle : std std_logic_vector(3 logic vector(3 constant write: std_logic_vector(3 constant readl: std_logic_vector(3 constant idle : std_logic_vector(3 constant write: std_logic_vector(3 constant readl: std_logic_vector(3 signal present_state, next_state : Begin „

downto 0):="0000"; 0): 0000 ; downto 0):="0100"; downto 0):="1000"; downto 0):="1001"; downto 0):="1010"; downto 0):="1011"; std_logic_vector(3 downto 0);

Tímto zápisem je rovněž explicitně určen způsob enkódování stavového automatu

Stavové automaty – synchronní výstupy „ „

Někdy bývá problém s výstupní logikou G – výstupní hazardy – nutná synchronizace Dva možné způsoby řešení 1) Zpoždění o jeden hodinový takt navíc

2) B Bez výstupního ý t íh zpoždění ždě í

Příklad: Nápojový automat Vlastnosti: 1) Blokové schéma nápojového automatu je zobrazeno na obrázku. 2) Po vhození částky 5 korun dojde vydání kávy 3) Automat vrací mince – koruny a dvoukoruny j_in – vstup: koruna d_in – vstup: dvoukoruna p_in – vstup: pětikoruna kava_out – signalizace, že má být káva vydána j_out – signalizace, že má být koruna vrácena d_out – signalizace, že má být dvoukoruna vrácena

Možnosti realizace: 1) Diskrétní dig. součástky – ruční odvození vycházející z metodiky stavových automatů, obtížnější řešení, jedná se o komplexnější obvod 2) Obvod CPLD nebo FPGA – popis systému stavovým automatem, realizace v návrhovém systému ISE WebPack v jazyce VHDL do obvodu CPLD nebo FPGA (návrhový systém má v sobě zabudované minimalizační a optimalizační algoritmy)

Příklad: nápojový p j ý automat na kávu Bezpečný stavový automat nápojového automatu d_in=1

st1

j_in=1

kava a a_out out=0 0 j_out=0 d_out=0 p_in=1

st0

j_in=1

st2 kava_out=0 j_out=0 d_out=0 p_in=1

d_in=1

d_in=1

d_in=1

j_in=1

st3 kava_out=0 j_out=0 d_out=0 p_in=1

j_in=1

st4 kava_out=0 j_out=0 d_out=0 p_in=1

p in=1 p_in=1

st5

kava_out=0 j_out=0 d_out=0

st10...st15

j_in=1

kava_out=1 j_out=0 d_out=0

st6

st7

st8

st9

kava_out=1 j out=1 j_ d_out=0

kava_out=1 j out=0 j_ d_out=1

kava_out=0 j out=1 j_ d_out=0

kava_out=0 j out=0 j_ d_out=1

kava_out=0 j_out=0 d out=0 d_out=0 d_in=1

Kolik vstupů by měla kombinační logika F v případě ručního návrhu?

Příklad: nápojový automat na kávu VHDL popis nápojového automatu: entity automat is Port ( clk, rst: in STD_LOGIC; -- vstup j_in : in STD_LOGIC; -- vstup d_in : in STD_LOGIC; -- vstup p_in : in STD_LOGIC; -- vstup kava_out: out STD_LOGIC; -- vystup j_out : out STD_LOGIC; -- vystup d d_out : out STD_LOGIC); ) -- vystup end automat; architecture Behavioral of automat is type state is (st0, st1, st2, st3, st4, st5, st6, st7, st8, st9); signal i l present_state, next_state : state; begin -- sekvencni cast stavoveho automatu process (clk, rst) b i begin if rst='1' then present_state <= st0; elsif rising_edge(clk) then present_state t t t <= < next_state; t t t end if; end process; Programovatelné logické obvody

Příklad: nápojový automat na kávu --kombinacni cast F a G stavoveho automatu (budici signaly pro klopne obvody) process (present_state, j_in, d_in, p_in) begin case present_state is when st0 => kava_out <= '0'; -- kava neni vydana j_out <= '0'; -- koruna neni vracena d d_out <= '0'; 0 -- dvojkoruna d jk neni i vracena if (j_in='1') then next_state <= st1; elsif (d_in='1') then next_state <= st2; elsif (p_in='1') then next_state <= st5; else l next_state <= st0; 0 -- prechod h d d do stavu st0 0 end if; when st1 => kava_out <= '0'; -- kava neni vydana j j_out t <= '0' '0'; -- koruna k neni i vracena d_out <= '0'; -- dvojkoruna neni vracena if (j_in='1') then next_state <= st2; elsif (d_in='1') then next_state <= st3; elsif l if ( (p_in='1') i '1') th then next_state t t t < <= st6; t6 else next_state <= st1; -- prechod do stavu st1 end if; Programovatelné logické obvody

Příklad: nápojový automat na kávu when st2 => kava_out <= '0'; -- kava neni vydana j_out <= '0'; -- koruna neni vracena d_out <= '0'; -- dvojkoruna neni vracena if (j_in='1') then next_state <= st3; elsif (d_in='1') then next_state <= st4; elsif (p_in='1') then next_state <= st7; else l next_state <= st2; 2 -- prechod h d d do stavu st2 2 end if; when st3 => kava_out <= '0'; -- kava neni vydana j j_out <= '0' '0'; -- koruna k neni i vracena d_out <= '0'; -- dvojkoruna neni vracena if (j_in='1') then next_state <= st4; elsif (d_in='1') then next_state <= st5; elsif l if ( (p_in='1') i '1') th then next_state t t t <= st8; t8 else next_state <= st3; -- prechod do stavu st3 end if;

Příklad: nápojový automat na kávu when st4 => kava_out <= '0'; -- kava neni vydana j_out <= '0'; -- koruna neni vracena d_out <= '0'; -- dvojkoruna neni vracena if (j_ (j in='1') ) then next_state <= st5; ; elsif (d_in='1') then next_state <= st6; elsif (p_in='1') then next_state <= st9; else next_state <= st4; -- prechod do stavu st4 end if; when st5 => kava_out <= '1'; -- kava je vydana j_out <= '0'; -- koruna neni vracena d_out <= '0'; -- dvojkoruna j neni vracena next_state <= st0; -- prechod do stavu st0 when st6 => kava_out <= '1'; -- kava je vydana j out <= '1'; -- koruna j j_ je vracena d_out <= '0'; -- dvojkoruna neni vracena next_state <= st0; -- prechod do stavu st0 when st7 => kava_out <= '1'; -- kava j je vydana y j_out <= '0'; -- koruna neni vracena d_out <= '1'; -- dvojkoruna je vracena next_state <= st0; -- prechod do stavu st0

Příklad: nápojový automat na kávu when st8 => k kava_out t < <= '0' '0'; -- kava k neni i vydana d j_out <= '1'; -- koruna je vracena d_out <= '0'; -- dvojkoruna neni vracena next_state <= st7; -- prechod do stavu st7 when st9 => kava_out <= '0'; -- kava neni vydana j_out <= '0'; -- koruna neni vracena d out <= '1'; -- dvojkoruna je vracena d_out next_state <= st7; -- prechod do stavu st7 when others => -- osetreni nevyuzitych stavu kava out <= '0'; -- kava neni vydana kava_out j_out <= '0'; -- koruna neni vracena d_out <= '0'; -- dvojkoruna je vracena next_state <= st0; -- prechod do stavu st0 end case; end process; end Behavioral;

Příklad: nápojový automat na kávu when st8 => k kava_out t < <= '0' '0'; -- kava k neni i vydana d j_out <= '1'; -- koruna je vracena d_out <= '0'; -- dvojkoruna neni vracena next_state <= st7; -- prechod do stavu st7 when st9 => kava_out <= '0'; -- kava neni vydana j_out <= '0'; -- koruna neni vracena d out <= '1'; -- dvojkoruna je vracena d_out next_state <= st7; -- prechod do stavu st7 when others => -- osetreni nevyuzitych stavu kava out <= '0'; -- kava neni vydana kava_out j_out <= '0'; -- koruna neni vracena d_out <= '0'; -- dvojkoruna je vracena next_state <= st0; -- prechod do stavu st0 end case; end process; end Behavioral;

Příklad: Nápojový automat Obvody y CPLD, FPGA, jjazyk y VHDL

- Simulace

Příklad: Signalizace na křižovatce Vlastnosti: 1) 2) 3) 4) 5)

Blokové schéma křižovatky je zobrazeno na obrázku. P dobu Po d b 8 sekund k d svítí ítí červená č á na semaforu f 1 a zelená l á na semaforu f 2 2. Oranžová svítí po dobu 2 sekund na obou semaforech. Po dobu 8 sekund svítí zelená na semaforu 1 a červená na semaforu 2. Hodinový kmitočet clk clk=1 1 Hz.

auto

semafor f 2

auto

semafor 1

Možnosti realizace: 1) Diskrétní dig. součástky – ruční návrh vycházející z metodiky stavových automatů, obtížnější řešení, jedná se o komplexnější obvod 2) Obvod CPLD nebo FPGA – popis systému stavovým automatem, realizace v návrhovém systému ISE WebPack v jazyce VHDL do obvodu CPLD nebo FPGA (návrhový systém má v sobě zabudované minimalizační a optimalizační algoritmy)

Příklad: Signalizace na křižovatce „

Proces, který rozhoduje kolik paměťových prvků bude využito v paměťové části.

Příklad: Signalizace na křižovatce „

„

„

Blok časovač slouží k odpočítání příslušného časového intervalu. V našem případě máme dva časové intervaly: „ 8 sekund k d – v digitální di itál í bi binární á í reprezentaci t i se jjedná d á o čí číslo l 111 „ 2 sekundy – v digitální binární reprezentaci se jedná o číslo 001 Výstupy z časovače budou představovat vstupy do kombinační logiky F stavového automatu a b d ovlivňovat budou li ň t následující á l d jí í stav. t Výstupy Vý t z časovače č č b bude d 3 3-bitové bit é číslo čí l V a rozdělíme dělí jjejj na V2, V1 a V0. Blok N generuje signál EN, který povolí, že vstup X (binární hodnota 000) se přepíše na výstup V V. Signál EN bude závislý jak na hodnotě předcházejícího stavu stavového automatu automatu, tak i na aktuální hodnotě časovače. Pokud dojde k dosažení požadovaného časového intervalu (8 sekund nebo 2 sekundy) a časový interval bude korespondovat se současným stavem stavového automatu, tak bude výstup EN=1

současný vstupy stav V2 V1 ? 0 0 ? 1 1 ostatní kombinace

V0 1 1

výstup EN 1 1 0

Příklad: Signalizace na křižovatce „

Návrh 3-bitového časovače/čítače

Příklad: Signalizace na křižovatce Stavový diagram signalizace na křižovatce

01 s) 0 V= e=2 m (ti

V (ti =1 m 11 e= 8s )

V V≠001

V≠001 1

V ( ti = 1 m 11 e= 8s )

01 s ) 0 V= e=2 m (ti

Příklad: Signalizace na křižovatce Pravdivostní tabulka stavů

Příklad: Signalizace na křižovatce Návrh kombinačního bloku N vstupy současný stav st0 st1 st2 st3 -

současný stav Q1

Q0

0 0 1 1

0 1 0 1

V2

výstup V1

0 0 1 1 0 0 1 1 ostatní kombinace

V0

EN

1 1 1 1

1 1 1 1 0

EN = (Q 0 ⋅ V 2 ⋅ V 1 ⋅ V 0) + (Q 0 ⋅ V 2 ⋅ V 1 ⋅ V 0) = = (Q 0 ⋅ V 2 ⋅ V 1 ⋅ V 0) ⋅ (Q 0 ⋅ V 2 ⋅ V 1 ⋅ V 0)

Příklad: Signalizace na křižovatce Stavový diagram signalizace na křižovatce EN 0 EN=0

st0 00 r1 0,y1 1,g1 0 r1=0,y1=1,g1=0 r2=0,y2=1,g2=0

=1 s) N E e=2 m (ti

(ti EN m =1 e= 8s )

r1=1,y1=0,g1=0 r2=0,y2=0,g2=1

(ti EN m =1 e= 8s )

st2 10

st0 11 r1=0,y1=0,g1=1 r2=1,y2=0,g2=0

EN=0

=1 s) N E e=2 m (ti

r1 0,y1 1,g1 0 r1=0,y1=1,g1=0 r2=0,y2=1,g2=0

EN=0 0

E EN=0

st1 01

Příklad: Signalizace na křižovatce Návrh bloku kombinačního bloku F t výstupy ýt vstupy následují následující současný současný stav EN cí stav stav stav Q1 Q0 D1 D0 st0 0 0 1 0 1 st1 st1 0 1 1 1 0 st2 st2 1 0 1 1 1 st3 st3 1 1 1 0 0 st0 st0 0 0 0 0 0 st0 st1 0 1 0 0 1 st1 st2 1 0 0 1 0 st2 st3 1 1 0 1 1 st3

D1 = Q1 ⋅ Q0 + Q1 ⋅ EN + Q1 ⋅ Q0 ⋅ EN = Q1 ⋅ Q0 ⋅ Q1 ⋅ EN ⋅ Q1 ⋅ Q0 ⋅ EN

D0 = Q0 ⋅ EN + Q0 ⋅ EN = Q0 ⋅ EN ⋅ Q0 ⋅ EN

Příklad: Signalizace na křižovatce Návrh bloku kombinačního bloku G

Současný stav st0 st1 st2 st3

Vstupy Současný stav

Výstupy semafor 1

semafor 2

Q1

Q0

r1

y1

g1

r2

y2

g2

0 0 1 1

0 1 0 1

0 1 0 0

1 0 1 0

0 0 0 1

0 0 0 1

1 0 1 0

0 1 0 0

y1=y2 y1 y2, r1=g2 r1 g2 a g1=r2 g1 r2

y1 = Q 0

r1 = Q1 ⋅ Q0 = Q1 + Q0 g1 = Q1 ⋅ Q0 = Q1 + Q0

Příklad: Signalizace na křižovatce VHDL popis signalizace (stavový automat): entity digi_top is Port ( clk, rst : in STD_LOGIC; r1,r2,y1,y2,g1,g2 : out STD_LOGIC); end digi_top; architecture Behavioral of automat is type state IS (st0, st1, st2, st3); signal present_state, next_state : state; CONSTANT time1 i 1 : std_logic_vector(2 d l i (2 d downto 0) := "001"; 001 CONSTANT time2 : std_logic_vector(2 downto 0) := "101"; signal count_reg, count_int : std_logic_vector(2 downto 0); signal en : std_logic; b i begin -- pametova cast stavoveho automatu a citace process (clk,rst) begin if ( (rst='1') t '1') th then present_state <= st0; -- pocatecni stav po resetu count_reg <= "000"; -- vynulovani citace elsif (clk'event and clk='1') then -- detekce nabezne hrany present_state t t t <= < next_state; t t t count_reg <= count_int; end if; Programovatelné logické obvody end process;

Příklad: Signalizace na křižovatce -- kombinacni cast F citace count int <= "000" count_int 000 when en='1' else count count_reg+1; reg+1; -- kombinacni blok N en<='1' when ((present_state=st0 and count_reg=time1) or (present state=st1 and count_reg (present_state=st1 count reg =time2) or (present_state=st2 and count_reg=time1) or (present_state=st3 and count_reg=time2)) else '0'; -- kombinacni cast F a G stavoveho automatu process (present_state,en) begin case present_state is when st0 => next_state <= st0; r1<='0'; r2<='0'; y1<='1'; y2<='1'; g1<='0'; g2<='0'; if en='1' then next state <= st1; next_state end if; when st1 => next_state <= st1; r1<='1'; r1<= 1 ; r2<='0'; r2<= 0 ; y1<='0'; y1<= 0 ; y2<='0'; y2<= 0 ; g1<='0'; g1<= 0 ; g2<='1'; g2<= 1 ; if en='1' then next_state <= st2; end if;

Příklad: Signalizace na křižovatce when st2 => next state <= st2; next_state r1<='0'; r2<='0'; y1<='1'; y2<='1'; g1<='0'; g2<='0'; if en='1' then next_state <= st3; end if; when st3 => next_state <= st3; r1<='0'; r2<='1'; y1<='0'; y2<='0'; g1<='1'; g2<='0'; if en='1' en= 1 then next_state <= st0; end if; end case; end process; end Behavioral;

Příklad: Signalizace na křižovatce Stavový diagram signalizace na křižovatce

st1 01 re ti m g= er )

q_ re g=

r1=0,y1=1,g1=0 ,y ,g r2=0,y2=1,g2=0 timer=2

q_

st0 00

im =t g re q_

r1=1,y1=0,g1=0 r2=0,y2=0,g2=1 timer=8

) er

er tim )

st0 11

r1=0,y1=0,g1=1 r2=1,y2=0,g2=0 timer=8

q

st2 10

r1=0,y1=1,g1=0 ,y ,g r2=0,y2=1,g2=0 ) er m timer=2 i =t g e _r

Příklad: Signalizace na křižovatce VHDL popis signalizace (lepší způsob zápisu): entity digi_top is Port ( clk, rst : in STD_LOGIC; r1,r2,y1,y2,g1,g2 : out STD_LOGIC); end digi_top; architecture Behavioral of automat is type state IS (st0, st1, st2, st3); signal present_state, next_state : state; CONSTANT time1 i 1 : std_logic_vector(2 d l i (2 d downto 0) := "001"; 001 CONSTANT time2 : std_logic_vector(2 downto 0) := "101"; signal count_reg, count_int : std_logic_vector(2 downto 0); signal timer : std_logic_vector(2 downto 0); b i begin -- pametova cast stavoveho automatu a citace process (clk,rst) begin if ( (rst='1') t '1') th then present_state <= st0; -- pocatecni stav po resetu count_reg <= "000"; -- vynulovani citace elsif (clk'event and clk='1') then -- detekce nabezne hrany present_state t t t <= < next_state; t t t count_reg <= count_int; end if; Programovatelné logické obvody end process;

Příklad: Signalizace na křižovatce -- kombinacni cast F a G stavoveho automatu a citace process (present (present_state,count_reg) state count reg) begin case present_state is when st0 => next state <= st0; next_state timer <=time1; r1<='0'; r2<='0'; y1<='1'; y2<='1'; g1<='0'; g2<='0'; if count_reg=timer then next state <= st1; next_state count_int <= "000"; else count_int <= count_reg+1; end if; when st1 => next_state <= st1; timer <=time2; r1<='1'; r1<= 1 ; r2<='0'; r2<= 0 ; y1<='0'; y1<= 0 ; y2<='0'; y2<= 0 ; g1<='0'; g1<= 0 ; g2<='1'; g2<= 1 ; if count_reg=timer then next_state <= st2; count_int <= "000"; else count_int <= count_reg+1; end if;

Příklad: Signalizace na křižovatce when st2 => next state <= st2; next_state timer <=time1; r1<='0'; r2<='0'; y1<='1'; y2<='1'; g1<='0'; g2<='0'; if count_reg=timer then next state <= st3; next_state count_int <= "000"; else count_int <= count_reg+1; end if; when st3 => next_state <= st3; timer <=time2; r1<='0'; r1<= 0 ; r2<='1'; r2<= 1 ; y1<='0'; y1<= 0 ; y2<='0'; y2<= 0 ; g1<='1'; g1<= 1 ; g2<='0'; g2<= 0 ; if count_reg=timer then next_state <= st0; count_int <= "000"; else count_int <= count_reg+1; end if; end case; end process; end Behavioral;

Ošetření zákmitů na tlačítku – obvodové schéma

Vcc in =1

gnd

main_clk

cclk

QN

dělička kmitočtu 2N

l d load

D0 D1 D2 D3

shift_in clk

shift_out

posuvný registr

out

Ukázka parametrizované paměti RAM – VHDL entity ram is GENERIC (x : integer := 32; y : integer :=4); port( clk,WR,RD : in std_logic; AddrWr,AddrRd : in std_logic_vector(y-1 downto 0); DataWr : in std_logic_vector(x std logic vector(x-1 1 downto 0); DataRd : out std_logic_vector(x-1 downto 0)); end ram; architecture Behavioral of ram is type RamType is array(0 to (2**y)-1) of std_logic_vector(x-1 downto 0); signal Ram: RamType; begin process(clk) is begin if rising_edge(clk) then if WR='1' then Ram(conv ( _integer(AddrWr))<= g ( )) DataWr; ; end if; if RD='1' then DataRd <= Ram(conv_integer(AddrRd)); end if; ; end if; end process; end Behavioral;