1
1
Circuitos Lógicos e Organização de Computadores
Capítulo 8 –Circuitos Seqüenciais Síncronos
Ricardo [email protected]
http://docentes.puc-campinas.edu.br/ceatec/pannain/
2
Forma geral de um circuito seqüêncial
Combinational Circuito Flip-flops
Clock
Q
W Z
Combinational Circuito
Máquina de estados finitos (FSM – Finite StateMachine) ? o comportamento do circuito pode ser representado usando um número finito de estados.
Máquina de MOORE ? saídas dependem apenas do estado do circuito.
Máquina de MEALY ? saídas dependem do estado do circuito e de suas entradas primárias.
2
3
Clockcycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10w : 0 1 0 1 1 0 1 1 1 0 1 z : 0 0 0 0 0 1 0 0 1 1 0
Etapas Básicas de Projeto
Exemplo:
Supondo um circuito que tenha uma entrada w e uma saída z. • Todas as mudanças ocorrerão na subida do clock. • A saída z é igual a 1 se durante dois ciclos consecutivos imediatamente prescedente
a entrada w for igual a 1. Caso contrário o valor é zero.A tabela abaixo ilustra o funcionamento para um padrão de w qualquer.
4
PRIMEIRO PASSO ? Diagrama de estados
Determinar quantos estágios são necessários e quais transições são possíveis de um estado para outro.
No exemplo:
Supondo o estado inicial A (com saída z = 0) ? enquanto w = 0 ele permanece neste estado.Se w = 1, na subida do clock ele passará para o estado B (com z = 0). Uma vez no estado B, se w = 0 , ele passará para o estado A (z = 0) na subida do clock. Se w = 1, passará para um terceiro estado C (z = 1).No estado C, se w = 0, ele passará para o estado A (z = 0) na subida do clock. Se w = 1,Continuará no estado C (z = 1)
Etapas Básicas de Projeto
3
5
Diagrama de estados do exemplo anterior – Máquina de MOORE
C z 1 = ??
Reset
B z 0 = ??A z 0 = ??w 0 =
w 1 =
w 1 =
w 0 =
w 0 = w 1 =
6
Tabela de estados
Present Next state Outputstate w = 0 w = 1 z
A A B 0 B A C 0 C A C 1
SEGUNDO PASSO ? Tabela de Estados
4
7
Circuito seqüencial geral
Como temos 3 estados, precisaremos de 2 Flip-Flops e o circuito ficaria:
CombinationalCircuito
Combinational
Clock
y2
z
wy1Y1
Y2
Circuito
8
Tabela de estados assinalados
Present Next state
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 z
A 00 00 01 0
B 01 00 10 0
C 10 00 10 1
11 dd dd d
5
9
Derivando as expressões lógicas dos próximos estados e da saída
w 00 01 11 10
0
1
0
1 0
y 2 y
1
d
d
0
0
0
w 00 01 11 10
0
1
0 d
1 d
y 2 y 1
0
0
0
1
0 1
0
1
0
d
y 1
0
1
y 2
Ignorando don't cares Usando don't cares
Y 1 wy 1 y 2 =
Y 2
wy1
wy2
+ =
z y 2
=
w y 1 y 2 + ( ) =
Y 1 wy 1 y 2 =
Y 2
wy1
y 2 wy 1 y 2
+ =
z y 1 y 2
=
10
Circuito Seqüencial do exemplo anterior
D Q
Q
D Q
Q
Y 2
Y 1 w
Clock
z
y 1
y 2
Resetn
6
11
Diagrama de tempo do exemplo anterior
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 101
0
1
0
1
0
1
0
Clock
w
y 1
y 2
1
0 z
12
Sinais necessários
Control circuit
w
Clock
Done
R 1 out
R 2 out
R 1 in
R 2 inR 3 out
R 3 in
Exemplo – Troca de conteúdo entre dois registradores
Trocar o conteúdo dos registradores R1 e R2, utilizando o registador R3 com auxiliar
R3? R2R2? R1R1? R3
7
13
Diagrama de estados
D R 3 out 1 = R 1 in 1 = Done 1 = ?? ????
w 0 = w 1 =
C R 1 out 1 = R 2 in 1 = ????
B R 2 out 1 = R 3 in 1 = ????
w 1 =
A No??
w 0 = w 1 =
transfer
w 0 = w 1 =
Reset
w 0 =
14
Tabela de estados
Present Next state Outputs
state
A A B 0 0 0 0 0 0 0 B C C 0 0 1 0 0 1 0 C D D 1 0 0 1 0 0 0 D A A 0 1 0 0 1 0 1
w = 0 w = 1
8
15
Tabela de estados assinalados
Present Nextstate
state Outputs
A 00 00 0 1 0 0 0 0 0 0 0 B 01 10 1 0 0 0 1 0 0 1 0 C 10 11 1 1 1 0 0 1 0 0 0 D 11 00 0 0 0 1 0 0 1 0 1
16
Derivação da expressão do próximo estado
w 00 01 11 10
0
1
1
1 1
y 2 y 1
Y 1 wy 1 y 1 y 2 + =
w 00 01 11 10
0
1
1 1
1 1
y 2 y 1
Y 2 y 1 y 2 y 1 y 2 + =
9
17
Circuito seqüencial correspondente
D Q
Q
D Q
Q
Done
w
Clock
Y 2
Y 1
y 2
y 1
y 2
y 1
R 1 in
R 3 out
R 1 out
R 2 in
R 2 out
R 3 in
18
Problemas de assinalamento de estados
Present Next state
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 z
A 00 00 01 0 B 01 00 11 0 C 11 00 11 1
10 dd dd d
Suponha que, no primeiro exemplo, ao assinalar valores para os estados presentes, tenhamos escolhido conforma a tabela abaixo:
Y1 = D1 = wY2 = D2 = w y1z = y2
10
19
Circuito com a melhoria no assinalamento
D Q
Q
D Q
Q
Y 2
Y 1 w
Clock
z
y 1
y 2
Resetn
20
Tabela de estados com melhoria de assnalamento – exemplo 2
Present Nextstate
state Outputs
A 00 0 0 01 0 0 0 0 0 0 0 B 01 1 1 11 0 0 1 0 0 1 0 C 11 1 0 10 1 0 0 1 0 0 0 D 10 0 0 00 0 1 0 0 1 0 1
11
21
Derivação da expressão do próximo estado
w 00 01 11 10
0
1
1
1 1
y 2 y 1
Y 1 wy2 y 1 y 2 + =
w 00 01 11 10
0
1
1 1
1 1
y 2 y 1
Y 2 y 1 =
22
Present Nextstatestate w = 0 w = 1 Output
y 3 y 2 y 1 Y 3 Y 2 Y 1 Y 3 Y 2 Y 1 z
A 001 001 010 0 B 010 001 100 0 C 100 001 100 1
Exemplo 3 – One hot encoding
Podemos também ter tantas variáveis quantos forem os estados.Supor um circuito one hot enconding, representado pela tabela abaixo:
12
23
Assinalamento de estados - One-hot encoding
Present Nextstate
state Outputs
A 0 001 0001 0010 0 0 0 0 0 0 0 B 0 010 0100 0100 0 0 1 0 0 1 0 C 0 100 1000 1000 1 0 0 1 0 0 0 D 1 000 0001 0001 0 1 0 0 1 0 1
24
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10w : 0 1 0 1 1 0 1 1 1 0 1 z : 0 0 0 0 1 0 0 1 1 0 0
Máquina de Mealy
Nos exemplos anteriores, os circuitos seqüenciais onde cada estado tem valores dos sinais de saídas associados a eles,são chamadas Máquinas de MOORE.
Os circuitos seqüenciais onde os sinais das saídas estão associados tanto aos estadoscomo às entradas são chamadas de Máquina de MEALY
Tomando o primeiro exemplo visto anteriormente, que gerava z = 1 quando a ocorrência de w = 1 era detectada em dois períodos consecutivos de clock. Supondo agora que queiramos que z seja 1 no segundo ciclo que w = 1 seja detectado, como exemplifica a tabela abaixo:
13
25
Diagrama de estado
A
w 0 = z 0 = ??
w 1 = z 1 = ??B w 0 = z 0 = ??
Reset
w 1 = z 0 = ??
No exemplo:
Supondo o estado inicial A ? enquanto w = 0 ele permanece neste estado e produz a saída z = 0. Se w = 1 (z = 0 ), na subida do clock, ele passará para o estado B. Uma vez no estado B, se w = 0 (z = 0) , ele passará para o estado A na subida do clock. Se w = 1 produzirá a saída z = 1 e permanecerá neste estado..
26
Tabela de estados
Present Next state Output z
state w = 0 w = 1 w = 0 w = 1
A A B 0 0 B A B 0 1
14
27
Tabela de estados assinalados
Present Next state Outputstate w = 0 w = 1 w = 0 w = 1
y Y Y z z
A 0 0 1 0 0 B 1 0 1 0 1
28
Implementação da FSM
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 101 0
1 0
1 0
1 0
Clock
y
w
z
(b) Diagrama de tempo
Clock
Resetn
D Q
Q
w
z
(a) Circuito
y
15
29
Implementação da FSM incluíndo um atraso na saída
Clock
Resetn
D Q
Q
w
z
(a) Circuit
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 101 0
1 0
1 0
1 0
Clock
y
w
z
y
(b) Timing diagram
D Q
Q
Z
1 0
Z
OBS – Mesmo circuito do slide 19
30
Exemplo – troca de conteúdo de registradores
R3out 1= R1in 1= Done 1=? ?w 0=w 1=
R1out 1= R2in 1=?
w 1= R? 2out 1= R3in 1=?
A
w 0=w 1=
Reset
w 0=
B
C
16
31
Código VHDL para uma FSM simples
USE ieee.std_logic_1164.all ;
ENTITY simple ISPORT ( Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;END simple ;
ARCHITECTURE Behavior OF simple ISTYPE State_type IS (A, B, C) ;SIGNAL y : State_type ;
BEGINPROCESS ( Resetn, Clock )BEGIN
IF Resetn = '0' THENy <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THEN
con’t ...
32
CASE y ISWHEN A =>
IF w = '0' THENy <= A ;
ELSEy <= B ;
END IF ;WHEN B =>
IF w = '0' THENy <= A ;
ELSEy <= C ;
END IF ;WHEN C =>
IF w = '0' THENy <= A ;
ELSEy <= C ;
END IF ;END CASE ;
END IF ;END PROCESS ;z <= '1' WHEN y = C ELSE '0' ;
END Behavior ;
Código VHDL para uma FSM simples - continuação
17
33
(ENTITY declaration not shown)
ARCHITECTURE Behavior OF simple ISTYPE State_type IS (A, B, C) ;SIGNAL y_present, y_next : State_type ;
BEGINPROCESS ( w, y_present )BEGIN
CASE y_present ISWHEN A =>
IF w = '0' THENy_next <= A ;
ELSEy_next <= B ;
END IF ;WHEN B =>
IF w = '0' THENy_next <= A ;
ELSEy_next <= C ;
END IF ;
Alternativa de estilo para um código de uma FSM
34
WHEN C =>IF w = '0' THEN
y_next <= A ;ELSE
y_next <= C ;END IF ;
END CASE ;END PROCESS ;
PROCESS (Clock, Resetn)BEGIN
IF Resetn = '0' THENy_present <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THENy_present <= y_next ;
END IF ;END PROCESS ;
z <= '1' WHEN y_present = C ELSE '0' ;END Behavior ;
Alternativa de estilo para um código de uma FSM - continuação
18
35
(ENTITY declaration not shown)
ARCHITECTURE Behavior OF simple ISTYPE State_TYPE IS (A, B, C) ;ATTRIBUTE ENUM_ENCODING : STRING ;ATTRIBUTE ENUM_ENCODING OF State_type : TYPE IS "00 01 11" ;SIGNAL y_present, y_next : State_type ;
BEGIN
con’t ...
Uso de definição de ATTRIBUTE para assinalamento manual de estados
36
Uso de constantes para assinalamento manual de estados
LIBRARY ieee ;USE ieee.std_logic_1164.all ;
ENTITY simple ISPORT ( Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;END simple ;
ARCHITECTURE Behavior OF simple ISSIGNAL y_present, y_next : STD_LOGIC_VECTOR(1 DOWNTO 0);CONSTANT A : STD_LOGIC_VECTOR(1 DOWNTO 0) := "00" ;CONSTANT B : STD_LOGIC_VECTOR(1 DOWNTO 0) := "01" ;CONSTANT C : STD_LOGIC_VECTOR(1 DOWNTO 0) := "11" ;
BEGINPROCESS ( w, y_present )BEGIN
CASE y_present ISWHEN A =>
IF w = '0' THEN y_next <= A ;ELSE y_next <= B ;END IF ;
… con’t
19
37
WHEN B =>IF w = '0' THEN y_next <= A ;ELSE y_next <= C ;END IF ;
WHEN C =>IF w = '0' THEN y_next <= A ;ELSE y_next <= C ;END IF ;
WHEN OTHERS =>y_next <= A ;
END CASE ;END PROCESS ;
PROCESS ( Clock, Resetn )BEGIN
IF Resetn = '0' THENy_present <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THENy_present <= y_next ;
END IF ;END PROCESS ;z <= '1' WHEN y_present = C ELSE '0' ;
END Behavior ;
Uso de constantes para assinalamento manual de estados
38
Código VHDL máquina de Mealy
LIBRARY ieee ;USE ieee.std_logic_1164.all ;
ENTITY mealy ISPORT ( Clock, Resetn, w : IN STD_LOGIC ;
z : OUT STD_LOGIC ) ;END mealy ;
ARCHITECTURE Behavior OF mealy ISTYPE State_type IS (A, B) ;SIGNAL y : State_type ;
BEGINPROCESS ( Resetn, Clock )BEGIN
IF Resetn = '0' THENy <= A ;
ELSIF (Clock'EVENT AND Clock = '1') THENCASE y IS
WHEN A =>IF w = '0' THEN y <= A ;ELSE y <= B ;END IF ;
… con’t
20
39
WHEN B =>IF w = '0' THEN y <= A ;ELSE y <= B ;END IF ;
END CASE ;END IF ;
END PROCESS ;
PROCESS ( y, w )BEGIN
CASE y ISWHEN A =>
z <= '0' ;WHEN B =>
z <= w ;END CASE ;
END PROCESS ;END Behavior ;
Código VHDL máquina de Mealy - continuação
40
Exemplo – somador serial
Sum A B + =
Shift register
Shift register
Adder FSM Shift register
B
A
a
b
s
Clock
21
41
G
00 1 ??
11 1 ??10 0 ??01 0 ??
H 10 1 ??01 1 ??00 0 ??
carry-in 0 = carry-in 1 =
G:H:
Reset
11 0 ??
ab s ???? ??
Somador serial – diagrama de estados - Mealy
42
Present Next state Output sstate ab =00 01 10 11 00 01 10 11
G G G G H 0 1 1 0 H G H H H 1 0 0 1
Somador serial – Tabela de estados - Mealy
22
43
Present Next state Output
state ab =00 01 10 11 00 01 10 11
y Y s
0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1
Somador serial – Tabela de estados assinalados - Mealy
Y = a b + a y + b y
s = a b yFull adder
carry out
soma
44
Fulladder
ab
s
D Q
Q
carry-out
Clock
Reset
Y y
Somador serial – Mealy FSM
23
45
H 1 s 1 = ??
Reset
H 0 s 0 = ??
011011
11
0110
G 1 s 1 = ??
G 0 s 0 = ??
0110 00
01
00
10
11
00
00
11
Somador serial – diagrama de estados - Moore
46
Present Nextstate Outputstate ab =00 01 10 11 s
G 0 G 0 G 1 G 1 H 0 0 G 1 G 0 G 1 G 1 H 0 1 H 0 G 1 H 0 H 0 H 1 0 H 1 G 1 H 0 H 0 H 1 1
Somador serial – tabela de estados - Moore
24
47
Present Nextstate
state ab =00 01 10 11 Output
y 2 y 1 Y 2 Y 1 s
00 0 0 01 0 1 10 0 01 0 0 01 0 1 10 1 10 0 1 10 1 0 11 0 11 0 1 10 1 0 11 1
Somador serial – tabela de estados assinalados - Moore
Y1 = a b y2
Y2 = a b + a y2 + b y2
s = y1 carry out
soma
Full adder
48
Fulladder
a
b D Q
Q Carry-out
Clock
Reset
D Q
Q
s
Y 2
Y 1 Sum bit
y 2
y 1
Somador serial –Moore FSM
25
49
Código de um shift register left-to-right com enable
LIBRARY ieee ;USE ieee.std_logic_1164.all ;-- left-to-right shift register with parallel load and enableENTITY shiftrne IS
GENERIC ( N : INTEGER := 4 ) ;PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ;
L, E, w : IN STD_LOGIC ;Clock : IN STD_LOGIC ;Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ;
END shiftrne ;ARCHITECTURE Behavior OF shiftrne ISBEGIN
PROCESSBEGIN
… con’t
50
WAIT UNTIL Clock'EVENT AND Clock = '1' ;IF E = '1' THEN
IF L = '1' THENQ <= R ;
ELSEGenbits: FOR i IN 0 TO N-2 LOOP
Q(i) <= Q(i+1) ;END LOOP ;Q(N-1) <= w ;
END IF ;END IF ;
END PROCESS ;END Behavior ;
Código de um shift register left-to-right com enable - continuação
26
51
Código VHDL – somador serial
LIBRARY ieee ;USE ieee.std_logic_1164.all ;ENTITY serial IS
GENERIC ( length : INTEGER := 8 ) ;PORT ( Clock : IN STD_LOGIC ;
Reset : IN STD_LOGIC ;A, B : IN STD_LOGIC_VECTOR(length-1 DOWNTO 0) ;Sum : BUFFER STD_LOGIC_VECTOR(length-1 DOWNTO 0) );
END serial ;
ARCHITECTURE Behavior OF serial ISCOMPONENT shiftrne
GENERIC ( N : INTEGER := 4 ) ;PORT ( R : IN STD_LOGIC_VECTOR(N-1 DOWNTO 0) ;
L, E, w : IN STD_LOGIC ;Clock : IN STD_LOGIC ;Q : BUFFER STD_LOGIC_VECTOR(N-1 DOWNTO 0) ) ;
END COMPONENT ;SIGNAL QA, QB, Null_in : STD_LOGIC_VECTOR(length-1 DOWNTO 0) ;SIGNAL s, Low, High, Run : STD_LOGIC ;SIGNAL Count : INTEGER RANGE 0 TO length ;TYPE State_type IS (G, H) ;SIGNAL y : State_type ;
… con’t
52
BEGINLow <= '0' ; High <= '1' ;ShiftA: shiftrneGENERIC MAP (N => length)
PORT MAP ( A, Reset, High, Low, Clock, QA ) ;ShiftB: shiftrne GENERIC MAP (N => length)
PORT MAP ( B, Reset, High, Low, Clock, QB ) ;AdderFSM: PROCESS ( Reset, Clock )BEGIN
IF Reset = '1' THENy <= G ;
ELSIF Clock'EVENT AND Clock = '1' THENCASE y IS
WHEN G =>IF QA(0) = '1' AND QB(0) = '1' THEN y <= H ;ELSE y <= G ;END IF ;
WHEN H =>IF QA(0) = '0' AND QB(0) = '0' THEN y <= G ;ELSE y <= H ;END IF ;
END CASE ;END IF ;
END PROCESS AdderFSM ;
… con’t
Código VHDL – somador serial - continuação
27
53
WITH y SELECTs <= QA(0) XOR QB(0) WHEN G,
NOT ( QA(0) XOR QB(0) ) WHEN H ;Null_in <= (OTHERS => '0') ;ShiftSum: shiftrne GENERIC MAP ( N => length )
PORT MAP ( Null_in, Reset, Run, s, Clock, Sum ) ;Stop: PROCESSBEGIN
WAIT UNTIL (Clock'EVENT AND Clock = '1') ;IF Reset = '1' THEN
Count <= length ;ELSIF Run = '1' THEN
Count <= Count -1 ;END IF ;
END PROCESS ;Run <= '0' WHEN Count = 0 ELSE '1' ; -- stops counter and ShiftSum
END Behavior ;
Código VHDL – somador serial - continuação
54
Minimização de estados
Definição 1 – Sejam 2 estados Si e Sj. Eles são ditos equivalentes se somente se para todas as possíveis seqüências de entradas, a mesma seqüência de saída é produzida, independente de qual estado (Si ou Sj) seja produzido.OBS – É mais fácil mostrar os estados que não são equivalentes.
Procedimento de Particionamento
28
55
Tabela de Estados
Present Next state Outputstate w = 0 w = 1 z
A B C 1 B D F 1 C F E 0 D B G 1 E F C 0 F E D 0 G F G 0
Minimização de estados
56Figure 8.52 Minimized state table for Example 8.5
Present Next state Outputstate w = 0 w = 1 z
A B C 1 B A F 1 C F C 0 F C A 0
29
57Figure 8.53 Signals for the vending machine
D Q
Q
sense N D Q
Q Clock
N
sense N
sense D
Clock
N
D
(a) Timing diagram
(b) Circuit that generates N
58Figure 8.54 State diagram for Example 8.6
S1 0 ??
S7 1 ??
DN
D N
S3 0 ??
S6 0 ??
S9 1 ??S8 1 ??
S2 0 ??
S5 1 ??
S4 1 ??
DNDN
DNDN
DN
DN
DN
D
D N
D N
DN
N
Reset
30
59Figure 8.55 State table for Example 8.6
Present Next state Outputstate DN =00 01 10 11 z
S1 S1 S3 S2 0 S2 S2 S4 S5 0 S3 S3 S6 S7 0 S4 S1 1 S5 S3 1 S6 S6 S8 S9 0 S7 S1 1 S8 S1 1 S9 S3 1
––
–––
––
–––
–––––––––
60Figure 8.56 Minimized state table for Example 8.6
Present Next state Outputstate DN =00 01 10 11 z
S1 S1 S3 S2 0 S2 S2 S4 S5 0 S3 S3 S2 S4 0 S4 S1 1 S5 S3 1
–––
– – –– – –
31
61Figure 8.57 Minimized state diagram for Example 8.6
S1 0 ??
S5 1 ??
DNDN
DN
DN
DN
D
D
D
N
N
N
S3 0 ??
S2 ??0
S4 1 ??
62Figure 8.58 Mealy-type FSM for Example 8.6
S3
S2
D 0 ??
S1
D 1 ??
D 1 ??
N 1 ??
N 0 ??
N 0 ??
DN 0 ??
DN 0 ??
DN 0 ??
32
63Figure 8.59 Incompletely specified state table for Example 8.7
Present Next state Output z state w = 0 w = 1 w = 0 w = 1
A B C 0 0 B D 0 C F E 0 1 D B G 0 0 E F C 0 1 F E D 0 1 G F 0
–
–
–
–
64Figure 8.60 State diagram for a counter
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
A/0 B/1 C/2 D/3
E/4F/5G/6H/7
33
65Figure 8.61 State table for the counter
Present Next state Output
state w = 0 w = 1
A A B 0 B B C 1 C C D 2 D D E 3 E E F 4 F F G 5 G G H 6 H H A 7
66Figure 8.62 State-assigned table for the counter
Present Next state
state w = 0 w = 1 Count
y 2 y 1 y 0 Y 2 Y 1 Y 0 Y 2 Y 1 Y 0 z 2 z 1 z 0
A 000 000 001 000 B 001 001 010 001 C 010 010 011 010 D 011 011 100 011 E 100 100 101 100 F 101 101 110 101 G 110 110 111 110 H 111 111 000 111
34
67Figure 8.63 Karnaugh maps for D flip-flops for the counter
00 01 11 10
00
01
1
0 1
1
1
0
0
0
0
1 0
0
0
1
1
1 11
10
y 1 y 0
wy2 00 01 11 10
00
01
0
0 0
1
1
1
1
0
1
0 1
0
0
1
1
0 11
10
y 1 y 0
wy2
00 01 11 10
00
01
0
1 1
0
1
0
1
0
1
0 0
0
1
1
0
1 11
10
y 1 y 0
wy2
Y 2 wy2 y 0 y 2 y 1 y 2 w + + + y 0 y 1 y 2 =
Y 0 wy0 wy0 + = Y 1 wy1 y 1 y 0 wy0 y 1 + + =
68
Diagrama do circuito do contador
D Q
Q
D Q
Q
Clock
y 0 w
y 1
y 2
Y 0
Y 1
Y 2
Resetn
D Q
Q
35
69Figure 8.65 Excitation table for the counter with JK flip-flops
Present Flip-flop inputs
state w = 0 w = 1 Count
y 2 y 1 y 0 Y 2 Y 1 Y 0 J 2 K 2 J 1 K 1 J 0 K 0 Y 2 Y 1 Y 0 J 2 K 2 J 1 K 1 J 0 K 0 z 2 z 1 z 0
A 000 000 0d 0d 0d 001 0d 0d 1d 000 B 001 001 0d 0d d0 010 0d 1d d1 001 C 010 010 0d d0 0d 011 0d d0 1d 010 D 011 011 0d d0 d0 100 1d d1 d1 011 E 100 100 d0 0d 0d 101 d0 0d 1d 100 F 101 101 d0 0d d0 110 d0 1d d1 101 G 110 110 d0 d0 0d 111 d0 d0 1d 110 H 111 111 d0 d0 d0 000 d1 d1 d1 111
70
Mapa Karnaugh - contador
00 01 11 10
00
01
d
0 d
d
d
0
0
0
d
1 d
d
d
1
1
111
10
y1y0wy2
J0 w=
00 01 11 10
00
01
0
d 0
0
0
d
d
d
1
d 1
1
1
d
d
d11
10
y1y0wy2
K0 w=
00 01 11 10
00
01
0
0 0
d
d
d
d
0
1
0 1
d
d
d
d
011
10
y1y0wy2
J1 wy0=
00 01 11 10
00
01
d
d d
0
0
0
0
d
d
d d
1
1
0
0
d11
10
y1y0wy2
K1 wy0=
00 01 11 10
00
01
0
d d
0
d
0
d
0
d
0 0
d
1
d
0
d11
10
y1y0
wy2
J2 wy0y1=
00 01 11 10
00
01
d
0 0
d
0
d
0
d
0
d d
1
d
0
d
011
10
y1y0wy2
K2 wy0y1=
36
71
Diagrama do circuito usando flip-flop JK
Clock
Resetn
w J Q
Q K
y 0
y 1
y 2
J Q
Q K
J Q
Q K
72Figure 8.68 Factored-form implementation of the counter
Clock
Resetn
w y 0
y 1
y 2
J Q
Q K
J Q
Q K
J Q
Q K
37
73Figure 8.69 State table for the counterlike example
Present Next Outputstate state z 2 z 1 z 0
A B 000 B C 100 C D 010 D E 110 E F 001 F G 101 G H 011 H A 111
74Figure 8.70 State-assigned table
Present Next Outputstate state
y 2 y 1 y 0 Y 2 Y 1 Y 0 z 2 z 1 z 0
000 1 00 0 00100 0 10 1 00010 1 10 0 10110 0 01 1 10001 1 01 0 01101 0 11 1 01011 1 11 0 11111 0 00 1 11
38
75Figure 8.71 Circuit for the counterlike example
D Q
Q
z 0
D Q
Q
D Q
Q
z 1
z 2
w
76Figure 8.72 State diagram for the arbiter
Idle
000
1xx
Reset
gnt1 g 1 ?? 1 =
x1x
gnt2 g 2 ?? 1 =
xx1
gnt3 g 3 ?? 1 =
0xx 1xx
01x x0x
001 xx0
39
77Figure 8.73 Alternative style of state diagram for the arbiter
r 1 r 2
r 1 r 2 r 3
Idle
Reset
gnt1 g 1 ?? 1 =
gnt2 g 2 ?? 1 =
gnt3 g 3 ?? 1 =
r 1 r 1
r 1
r 2
r 3
r 2
r 3
r 1 r 2 r 3
78Figure 8.74a VHDL code for the arbiter
LIBRARY ieee;USE ieee.std_logic_1164.all;
ENTITY arbiter ISPORT ( Clock, Resetn : IN STD_LOGIC ;
r : IN STD_LOGIC_VECTOR(1 TO 3) ;g : OUT STD_LOGIC_VECTOR(1 TO 3) ) ;
END arbiter ;
ARCHITECTURE Behavior OF arbiter ISTYPE State_type IS (Idle, gnt1, gnt2, gnt3) ;SIGNAL y : State_type ;
BEGINPROCESS ( Resetn, Clock )BEGIN
IF Resetn = '0' THEN y <= Idle ;ELSIF (Clock'EVENT AND Clock = '1') THEN
CASE y ISWHEN Idle =>
IF r(1) = '1' THEN y <= gnt1 ;ELSIF r(2) = '1' THEN y <= gnt2 ;ELSIF r(3) = '1' THEN y <= gnt3 ;ELSE y <= Idle ;END IF ;
… con’t
40
79Figure 8.74b VHDL code for the arbiter (con’t)
WHEN gnt1 =>IF r(1) = '1' THEN y <= gnt1 ;ELSE y <= Idle ;END IF ;
WHEN gnt2 =>IF r(2) = '1' THEN y <= gnt2 ;ELSE y <= Idle ;END IF ;
WHEN gnt3 =>IF r(3) = '1' THEN y <= gnt3 ;ELSE y <= Idle ;END IF ;
END CASE ;END IF ;
END PROCESS ;g(1) <= '1' WHEN y = gnt1 ELSE '0' ;g(2) <= '1' WHEN y = gnt2 ELSE '0' ;g(3) <= '1' WHEN y = gnt3 ELSE '0' ;
END Behavior ;
80Figure 8.75 Incorrect VHDL code for the grant signals
.
.
.PROCESS( y )BEGIN
IF y = gnt1 THEN g(1) <= '1' ;ELSIF y = gnt2 THEN g(2) <= '1' ;ELSIF y = gnt3 THEN g(3) <= '1' ;END IF ;
END PROCESS ;END Behavior ;
41
81Figure 8.76 Correct VHDL code for the grant signals
.
.
.PROCESS( y )BEGIN
g(1) <= '0' ;g(2) <= '0' ;g(3) <= '0' ;IF y = gnt1 THEN g(1) <= '1' ;ELSIF y = gnt2 THEN g(2) <= '1' ;ELSIF y = gnt3 THEN g(3) <= '1' ;END IF ;
END PROCESS ;END Behavior ;
82Figure 8.77 Simulation results for the arbiter circuit
42
83Figure 8.78 Output delays in the arbiter circuit
a) Output delays using binary encoding
b) Output delays using one-hot encoding
84Figure 8.80 Circuit for Example 8.8
D Q
Q
D Q
Q
Clock
Resetn
y 2
y 1
Y 2
Y 1
w
z
43
85Figure 8.81 Tables for the circuit in Example 8.8
Present Next State
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 z
0 0 0 0 01 0 0 1 0 0 10 0 1 0 0 0 11 0 1 1 0 0 11 1
(a)State-assigned table
Present Next state Outputstate w = 0 w = 1 z
A A B 0 B A C 0 C A D 0 D A D 1
(b)State table
86Figure 8.82 Circuit for Example 8.9
J Q
Q
Clock
Resetn
y2
y1
J2
J1w
z
K
J Q
QKK2
K1
44
87Figure 8.83 Excitation table
Present Flip-flop inputs
state w = 0 w = 1 Output
y 2 y1 J 2 K 2 J 1 K 1 J 2 K 2 J 1 K 1 z
00 01 0 1 0 0 1 1 0 01 01 0 1 1 0 1 1 0 10 01 0 1 0 0 1 0 0 11 01 0 1 1 0 1 0 1
88Figure 8.84 Circuit for Example 8.10
Clock
Resetn
y 2
y 1 w
z
T 2
D 1 D Q
Q
T Q
Q
45
89Figure 8.85 Excitation table
Present Flip-flop inputs
state w = 0 w = 1 Output
y 2 y 1 T 2 D 1 T 2 D 1 z
0 0 0 0 01 0 0 1 0 0 10 0 1 0 1 0 01 0 1 1 1 0 01 1
90Figure 8.86 Elements used in ASM charts
Output signalsor actions
(Moore type)
State name
Condition expression
0 (False) 1 (True)
Conditional outputs or actions (Mealy type)
(a) State box (b) Decision box
(c) Conditional output box
46
91Figure 8.87 ASM chart for a simple FSM
Please see “portrait orientation” PowerPoint file for Chapter 8
92Figure 8.88 ASM chart for the FSM in Figure 8.23
w
w 0 1
0
1
A
B
Reset
z
47
93Figure 8.89 ASM chart for the arbiter
r 1
r 3 0 1
1
Idle
Reset
r 2
r 1
r 3
r 2
gnt1
gnt2
gnt3
1
1
1
0
0
0
g 1
g 2
g 3
0
0
1
94Figure 8.90 The general model for a sequential circuit
Combinational circuit
Y k
Y 1
y k
y 1
w 1
w n
z 1
z m
Outputs
Next-statevariables
Present-state variables
Inputs