1 of 65

Кінцеві автомати

Іванець С.А., Кафедра БРАС, ЧНТУ. 2021.

Sergey.Ivanets@gmail.com

2 of 65

Література

  • Дэвид М. Харрис, Сара Л. Харрис Цифровая схемотехника и архитектура компьютера. Elsiver, 2013-2022. Розділ 3.4
  • Clifford E. Cummings, "Synthesizable Finite State Machine Design Techniques Using the New SystemVerilog 3.0 Enhancements," SNUG'03 (Synopsys Users Group San Jose, CA, 2003) Proceedings, March 2003.
  • Clifford E. Cummings, "State Machine Coding Styles for Synthesis," SNUG'98 (Synopsys Users Group San Jose, CA, 1998) Proceedings, section-TB1 (3rd paper), March 1998.
  • Clifford E. Cummings, “Coding And Scripting Techniques For FSM Designs With Synthesis-Optimized, Glitch-Free Outputs,” SNUG (Synopsys Users Group Boston, MA 2000) Proceedings, September 2000

​

2023-02-03

2

3 of 65

Визначення

  • Кінцевий автомат (КА), Цифровий Автомат (ЦА) - це пристрій, який здійснює прийом, зберігання і перетворення дискретної інформації за певним алгоритмом і може перебувати в одному з декількох стійких станів.
  • КА ≠ ЦА

2023-02-03

3

4 of 65

Типи кінцевих автоматів

  • Автомат Мура (Edward Forrest Moore, 1956) – вихідний сигнал цифрового автомата залежить лише від поточного стану
  • Автомат Мілі (George H. Mealy, 1955) – вихідний сигнал залежить від поточного стану і вхідних сигналів

2023-02-03

4

5 of 65

Модель Хаффмана

  • Модель Хаффмана – це зручна абстракція для опису послідовних схем та перетворення їх у HDL код.
  • Модель складається із чотирьох складових частин:
    • входи,
    • виходи,
    • комбінаційна логіка
    • елементи зберігання станів, реалізовані за допомогою D-тригерів.
  • Первый шаг к аппаратным ускорителям нейронных сетей для программистов лежит через изучение основ HDL, RTL и лаб на FPGA https://habr.com/ru/post/349750/

2023-02-03

5

6 of 65

Кінцевий автомат Мура

2023-02-03

6

7 of 65

Кінцевий автомат Мілі

2023-02-03

7

8 of 65

Граф кінцевого автомата

  • Стан
    • вершина
    • позначення

​

  • Перехід між станами
    • дуга
    • петля
    • умови переходу
    • сигнал скидання

​

  • Формування вихідного сигналу

2023-02-03

8

9 of 65

Граф кінцевого автомата Мура

  • Автомат Мура – вихідний сигнал залежить лише від поточного стану КА
  • Вихідне значення записують або біля вершини або всередині

2023-02-03

9

10 of 65

Граф кінцевого автомата Мілі

  • Автомат Мілі – вихідний сигнал залежить від поточного стану КА та вхідного сигналу
  • Вихідне значення записують над дугами у знаменнику

2023-02-03

10

11 of 65

Таблиця переходів

2023-02-03

11

Поточний стан

Наступний стан

Умови переходу

S0

S0

a=0 АБО c=0

S0

S1

a=1

S1

S1

a=1 АБО b=1

S1

S0

a=0 І b=0

S0

S2

c=1

S2

S2

c=1 АБО b=1

S2

S0

c=0 І b=0

12 of 65

Таблиця виходів

2023-02-03

12

Поточний стан

Вихід

S0

00

S1

01

S2

10

13 of 65

Реалізація кінцевого автомата. Комбінаційні виходи

2023-02-03

13

14 of 65

Реалізація кінцевого автомата. �Синхроннні виходи

2023-02-03

14

15 of 65

Приклади

2023-02-03

15

16 of 65

Кінцевий автомат керування мікросхемою динамічної пам'яті IS42S32800J

2023-02-03

16

17 of 65

PCI Express

PCIe Link Training State Machine

​

​

​

​

​

​

​

​

PCIe Specification 5.0, Figure 4-24

2023-02-03

17

18 of 65

​

​

​

  • Traffic light controller
    • Traffic sensors: TA, TB (TRUE when there’s traffic)
    • Lights: LA, LB

FSM Example

Chapter 3 <18>

SEQUENTIAL LOGIC DESIGN

19 of 65

​

​

​

  • Traffic light controller
    • Traffic sensors: TA, TB (TRUE when there’s traffic)
    • Lights: LA, LB

FSM Example

Chapter 3 <19>

SEQUENTIAL LOGIC DESIGN

20 of 65

​

​

​

  • Inputs: CLK, Reset, TA, TB
  • Outputs: LA, LB

FSM Black Box

Chapter 3 <20>

SEQUENTIAL LOGIC DESIGN

21 of 65

​

​

​

  • Moore FSM: outputs labeled in each state
  • States: Circles
  • Transitions: Arcs

FSM State Transition Diagram

Chapter 3 <21>

SEQUENTIAL LOGIC DESIGN

22 of 65

Current State

Inputs

Next State

S

TA

TB

S'

S0

0

X

​

S0

1

X

​

S1

X

X

​

S2

X

0

​

S2

X

1

​

S3

X

X

​

​

​

​

FSM State Transition Table

Chapter 3 <22>

SEQUENTIAL LOGIC DESIGN

23 of 65

Current State

Inputs

Next State

S

TA

TB

S'

S0

0

X

S1

S0

1

X

S0

S1

X

X

S2

S2

X

0

S3

S2

X

1

S2

S3

X

X

S0

​

​

​

FSM State Transition Table

Chapter 3 <23>

SEQUENTIAL LOGIC DESIGN

24 of 65

Current State

Inputs

Next State

S1

S0

TA

TB

S'1

S'0

0

0

0

X

​

​

0

0

1

X

​

​

0

1

X

X

​

​

1

0

X

0

​

​

1

0

X

1

​

​

1

1

X

X

​

​

State

Encoding

S0

00

S1

01

S2

10

S3

11

​

​

​

FSM Encoded State Transition Table

Chapter 3 <24>

SEQUENTIAL LOGIC DESIGN

25 of 65

Current State

Inputs

Next State

S1

S0

TA

TB

S'1

S'0

0

0

0

X

0

1

0

0

1

X

0

0

0

1

X

X

1

0

1

0

X

0

1

1

1

0

X

1

1

0

1

1

X

X

0

0

State

Encoding

S0

00

S1

01

S2

10

S3

11

​

​

​

S'1 = S1 ⊕ S0

S'0 = S1S0TA + S1S0TB

FSM Encoded State Transition Table

Chapter 3 <25>

SEQUENTIAL LOGIC DESIGN

26 of 65

Current State

Outputs

S1

S0

LA1

LA0

LB1

LB0

0

0

​

​

​

​

0

1

​

​

​

​

1

0

​

​

​

​

1

1

​

​

​

​

Output

Encoding

green

00

yellow

01

red

10

FSM Output Table

Chapter 3 <26>

SEQUENTIAL LOGIC DESIGN

27 of 65

Current State

Outputs

S1

S0

LA1

LA0

LB1

LB0

0

0

0

0

1

0

0

1

0

1

1

0

1

0

1

0

0

0

1

1

1

0

0

1

Output

Encoding

green

00

yellow

01

red

10

LA1 = S1

LA0 = S1S0

LB1 = S1

LB0 = S1S0

FSM Output Table

Chapter 3 <27>

SEQUENTIAL LOGIC DESIGN

28 of 65

FSM Schematic: State Register

Chapter 3 <28>

SEQUENTIAL LOGIC DESIGN

29 of 65

FSM Schematic: Next State Logic

Chapter 3 <29>

SEQUENTIAL LOGIC DESIGN

30 of 65

FSM Schematic: Output Logic

Chapter 3 <30>

SEQUENTIAL LOGIC DESIGN

31 of 65

FSM Timing Diagram

Chapter 3 <31>

SEQUENTIAL LOGIC DESIGN

32 of 65

Кодування станів. �Двійкове кодування (binary)

  • Мінімальна кількість біт.
  • При переходах між станами можуть перемикатися всі тригери, у яких зберігається стан КА.
  • Це призводить до росту споживання та може призводити до помилок.
  • Приклад коду:
    • 00, 01, 10, 11

2023-02-03

32

33 of 65

Кодування станів. �Пряме кодування (one-hot)

  • Використовуєть 1 біт для одного стану.
  • Кількість тригерів дорівнює кількості станів КА.
  • Використовується як режим за замовчуванням для КА до 32 станів.
  • Може використовуватись 0 або 1 для позначення стану.
    • 0001, 0010, 0100, 1000 – 1 для позначення стану
    • 1110, 1101, 1011, 0111 – 0 для позначення стану
  • one-hot with zero-idle
      • 0000, 0001, 0010, 0100
  • Краще використовувати для збільшення швидкості роботи КА.

2023-02-03

33

34 of 65

Кодування станів. Код Грея (Grey)

  • Тільки один біт перемикається при переходах між двома сусідніми кодами.
  • Гарно працює при послідовних переключеннях, наприклад, у лічильниках.
  • Мінімізація кількості переключень при переходах між станами.
  • Зменшення споживаної потужності.
  • Приклад:
    • 000, 001, 011, 010, 110…

​

2023-02-03

34

35 of 65

Кодування станів. Код Джонсона (Johnson)

  • При переходах між сусідніми кодами змінюється 1 біт.
  • Тільки один біт перемикається при переходах між двома сусідніми кодами.
  • Завадозахищине кодування. Дозволяє детектувати помилки при перемиканнях між станами.
  • Надлишковий код – є зайві стани, які не задіяні при кодуванні станів КА. Тому потрібно ними керувати окремо.
  • Приклад:00000
    • 00001, 00011, 00111, 01111, 11111

​

​

​

2023-02-03

35

36 of 65

Кодування станів автомата – порівняння методів

2023-02-03

36

Двійковий код

Код Грея

Код Джонсона

Код «one-hot»

000

000

00000

0000 0001

001

001

00001

0000 0010

010

011

00011

0000 0100

011

010

00111

0000 1000

100

110

01111

0001 0000

101

111

11111

0010 0000

110

101

11110

0100 0000

111

100

11100

1000 0000

37 of 65

Кодування станів у Quartus

  • auto
  • one-hot
  • gray
  • Johnson
  • minimal bits
  • sequential
  • user-encoded
  • Глобальне визначення стилю:
  • Settings / Analysis & Synthesis Settings / More Settings / State Machine Processing
  • Локально для окремого автомата у Assignment Editor

​

2023-02-03

37

38 of 65

FSM Timing Diagram

Chapter 3 <38>

SEQUENTIAL LOGIC DESIGN

39 of 65

  • Binary encoding:
    • i.e., for four states, 00, 01, 10, 11
  • One-hot encoding
    • One state bit per state
    • Only one state bit HIGH at once
    • i.e., for 4 states, 0001, 0010, 0100, 1000
    • Requires more flip-flops
    • Often next state and output logic is simpler

FSM State Encoding

Chapter 3 <39>

SEQUENTIAL LOGIC DESIGN

40 of 65

  • Alyssa P. Hacker has a snail that crawls down a paper tape with 1’s and 0’s on it. The snail smiles whenever the last two digits it has crawled over are 01. Design Moore and Mealy FSMs of the snail’s brain.

Moore vs. Mealy FSM

Chapter 3 <40>

SEQUENTIAL LOGIC DESIGN

41 of 65

​

​

​

​

​

​

​

​

​

​

​

​

Mealy FSM: arcs indicate input/output

State Transition Diagrams

Chapter 3 <41>

SEQUENTIAL LOGIC DESIGN

42 of 65

Current State

Inputs

Next State

S1

S0

A

S'1

S'0

0

0

0

​

​

0

0

1

​

​

0

1

0

​

​

0

1

1

​

​

1

0

0

​

​

1

0

1

​

​

State

Encoding

S0

00

S1

01

S2

10

​

​

​

Moore FSM State Transition Table

Chapter 3 <42>

SEQUENTIAL LOGIC DESIGN

43 of 65

Current State

Inputs

Next State

S1

S0

A

S'1

S'0

0

0

0

0

1

0

0

1

0

0

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

0

State

Encoding

S0

00

S1

01

S2

10

​

​

​

Moore FSM State Transition Table

S1’ = S0A

S0’ = A

Chapter 3 <43>

SEQUENTIAL LOGIC DESIGN

44 of 65

Current State

Output

S1

S0

Y

0

0

​

0

1

​

1

0

​

Moore FSM Output Table

Chapter 3 <44>

SEQUENTIAL LOGIC DESIGN

45 of 65

Current State

Output

S1

S0

Y

0

0

0

0

1

0

1

0

1

Y = S1

Moore FSM Output Table

Chapter 3 <45>

SEQUENTIAL LOGIC DESIGN

46 of 65

Current State

Input

Next State

Output

S0

A

S'0

Y

0

0

​

​

0

1

​

​

1

0

​

​

1

1

​

​

State

Encoding

S0

00

S1

01

​

​

​

Mealy FSM State Transition & Output Table

Chapter 3 <46>

SEQUENTIAL LOGIC DESIGN

47 of 65

Current State

Input

Next State

Output

S0

A

S'0

Y

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

State

Encoding

S0

00

S1

01

​

​

​

Mealy FSM State Transition & Output Table

Chapter 3 <47>

SEQUENTIAL LOGIC DESIGN

48 of 65

​

​

​

Moore FSM Schematic

Chapter 3 <48>

SEQUENTIAL LOGIC DESIGN

49 of 65

Mealy FSM Schematic

Chapter 3 <49>

SEQUENTIAL LOGIC DESIGN

50 of 65

Moore & Mealy Timing Diagram

Chapter 3 <50>

SEQUENTIAL LOGIC DESIGN

51 of 65

  1. Identify inputs and outputs
  2. Sketch state transition diagram
  3. Write state transition table
  4. Select state encodings
  5. For Moore machine:
    1. Rewrite state transition table with state encodings
    2. Write output table
  6. For a Mealy machine:
    • Rewrite combined state transition and output table with state encodings
  7. Write Boolean equations for next state and output logic
  8. Sketch the circuit schematic

FSM Design Procedure

Chapter 3 <51>

SEQUENTIAL LOGIC DESIGN

52 of 65

Робота у пакеті Quartus

2023-02-03

52

53 of 65

State Machine Viewer

  • Tools ⇒ Netlist Viewer ⇒ State Machine Viewer

2023-02-03

53

54 of 65

State Machine Wizard

2023-02-03

54

55 of 65

2023-02-03

55

56 of 65

2023-02-03

56

57 of 65

Вкладки вікна редагування цифрового автомата

2023-02-03

57

Назва

закладки

Призначення таблиці

General

Вказується тип сигналу скидання (reset) – синхронний або асинхронний та його активний рівень – високий або низький.

States

Перераховуються стани ЦА

Inputs

Перераховуються вхідні порти та їх сигнали керування

Outputs

Перераховуються вихідні порти

Transitions

Перераховуються попередні стани та результуючі стани, а також умови переходів

Actions

Перераховуються вихідні порти, їх значення та стани ЦА, які відповідають цим вихідним значенням. Також тут можуть перераховуватись додаткові умови.

58 of 65

Інструменти редактора цифрових автоматів

2023-02-03

58

Іконка інструменту

Назва інструменту

Призначення інструменту

​

State Tool

Інструмент для рисування станів ЦА

​

Transition Tool

Інструмент для рисування переходів ЦА

​

Input Port Tool

Додавання вхідних портів

​

Output Port Tool

Додавання вихідних портів

​

Rubberbanding Tool

Перемикання гнучкості ліній зв’язку

59 of 65

Світлофор з кнопкою

2023-02-03

59

60 of 65

Умови роботи

  • Світлофор на перехресті з пішоходним переходом
  • Пішоходний перехід має кнопку для включення
    • Вхід автомату керування but
  • Є таймер знаходження у кожному стані
    • Вхід автомату керування cnt
  • Вхід скидання – перехід в стан Init
  • Виходи:
    • 3 кольори основного світлофора
    • 2 кольори пішохідного світлофора
    • Скидання регістра кнопки
    • Код тривалості наступного стану

2023-02-03

60

61 of 65

Кнопка

  • Дві кнопки з різних сторін вулиці
  • Тригер для запису значення з асинхронним скиданням

2023-02-03

61

62 of 65

2023-02-03

62

63 of 65

Таблиця переходів

2023-02-03

63

rst

Кнопка but

cnt

Поточний стан

Майбутній стан

1

X

X

X

Init

0

X

!cnt

Init

Init

0

X

cnt

Init

R

0

X

!cnt

R

R

0

X

cnt

R

RG

0

X

!cnt

RG

RG

0

X

cnt

RG

G

0

X

!cnt

G

G

0

!but

cnt

G

G

0

but

Cnt

G

GR

0

X

!cnt

GR

GR

0

X

cnt

GR

R

64 of 65

Таблиця виходів

2023-02-03

64

Стан

R

Y

G

R_ped

G_ped

but_rst

count_value

Init

1

0

0

1

0

0

Init_val

R

1

0

0

0

1

0

R_val

RG

0

1

0

1

0

0

RG_val

G

0

0

1

1

0

0

G_val

GR

0

1

0

1

0

1

GR_val

65 of 65

Кодування станів

2023-02-03

65

Стан

Код

Init

0000

R

0001

RG

0010

G

0100

GR

1000