Разработка функциональной схемы конечного автомата

Елабужский Филиал Казанского Государственного Технического Университета им. А. Н. Туполева Курсовая работа по дисциплине:

" Схемотехника"

на тему:

" Разработка функциональной схемы конечного автомата"

Выполнила: студентка 3 курса группы 22 304 Шакирова Г. Р.

Проверила: Калганова Е.С.

Елабуга 2009

• Абстрактный синтез
• Автомат Мили
• Структурный синтез
• Кодирование состояний автомата
• Таблица кодирования входных сигналов
• Таблица кодирования выходных сигналов
• Таблица переходов и выходов абстрактного автомата

Абстрактный синтез

Товары стоимостью 3 и 7 рублей, принимаемые монеты достоинством 1 и 2 рубля.

1-й товар:

1+1+1

1+1+2 (сдача 1 руб.)

1+2

2+1

2+2 (сдача 1 руб.)

2-й товар:

1+1+1+1+1+1+1

2+1+1+1+1+1

1+2+1+1+1+1

1+1+2+1+1+1

1+1+1+2+1+1

1+1+1+1+2+1

1+1+1+1+1+2

2+2+1+1+1

2+1+2+1+1

2+1+1+2+1

2+1+1+1+2

1+2+2+1+1

1+1+2+2+1

1+1+1+2+2

1+2+1+2+1

2+2+2+1

1+2+2+2

2+1+2+2

2+2+1+2

2+2+2+2 (сдача 1 руб.)

1+1+1+1+1+1+2 (сдача 1 руб.)

1+1+1+2+1+2 (сдача 1 руб.)

1+1+2+1+1+2 (сдача 1 руб.)

1+2+1+1+1+2 (сдача 1 руб.)

2+1+1+1+1+2 (сдача 1 руб.)

1+1+1+1+2+2 (сдача 1 руб.)

X= (x₁, x₂, x₃, x₄) — множество входных сигналов

x₁ — выбор 1-го товара

x₂ — выбор 2-го товара

x₃ — бросок 1 рубля в монетоприемник

x₄ — бросок 2 рублей в монетоприемник

Y= (y₀, y₁, y₂, y₃; y₄, y₅) — множество выходных сигналов

y₀ — ожидание выбора товара, щель монетоприемника закрыта

y₁ — идет прием денег

y₂ — выдача 2-го товара без сдачи

y₃ — выдача 2-го товара со сдачей 1 руб.

y₄ — выдача 1-го товара

y₅ — выдача 1-го товара со сдачей 1 руб.

A= (a₀, a₁, a₃, a₄, a₅, a₆, a₇, a₈, a₉, a₁₀, a₁₁, a₁₂, a₁₃, a₁₄) — множество состояний

a₀ — начальное состояние

a₁ — выбран 1-ый товар, в автомате 0 руб.

a₂ — выбран 1-ый товар, в автомате 1 руб.

a₃ — выбран 1-ый товар, в автомате 2 руб.

a₄ — выбран 1-ый товар, в автомате 3 руб. — выдача 1-го товара

a₅ — выбран 1-ый товар, в автомате 4 руб. — выдача 1-го товара со сдачей 1 руб.

a₆ — выбран 2-ой товар, в автомате 0 руб.

a₇ — выбран 2-ой товар, в автомате 1 руб.

a₈ — выбран 2-ой товар, в автомате 2 руб.

a₉ — выбран 2-ой товар, в автомате 3 руб.

a₁₀ — выбран 2-ой товар, в автомате 4 руб.

a₁₁ — выбран 2-ой товар, в автомате 5 руб.

a₁₂ — выбран 2-ой товар, в автомате 6 руб.

a₁₃ — выбран 2-ой товар, в автомате 7 руб. — выдача 2-го товара

a₁₄ — выбран 2-ой товар, в автомате 8 руб. — выдача 2-го товара со сдачей 1 руб.

Автомат Мили

Запишем алгоритм работы автомата Мили в табличном виде.

a_{i -} состояния абстрактного автомата, x_j — входные сигналы абстрактного автомата

Запишем алгоритм работы автомата Мили, используя графический способ задания автомата.

Рисунок № 1

Структурный синтез

R =] log215 [=4 — количество элементов памяти

L=] log₂4 [=2 — количество входных каналов

N=] log₂6 [=3 — количество выходных каналов

Синтез автомата Мили будем проводить на Т-триггерах.

Т-триггер (триггер со счетным входом) имеет один вход. Он «переворачивается», изменяя свое состояние, каждый раз, когда на его вход поступает сигнал, соответствующий логической единице.

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

Кодирование состояний автомата

Q_k — состояния элементарного автомата, a_i — состояния абстрактного автомата

Таблица кодирования входных сигналов

б_m — входные сигналы структурного автомата, x_j — входные сигналы абстрактного автомата

Таблица кодирования выходных сигналов

z_p — выходные сигналы структурного автомата, y_s — входные сигналы абстрактного автомата

Таблица переходов и выходов абстрактного автомата

a_i — состояния абстрактного автомата, x_j — входные сигналы абстрактного автомата

Записываем выражения для функции возбуждения и выходов.

T1=б1 б2Q1Q2Q3+ б1Q1Q2Q3Q4+Q1Q2Q4+Q1Q2Q3=

=Q2 (б1Q1 (Q3 (б2+Q4)) +Q1 (Q4+Q3))

T2= б1Q1Q2Q3Q4+ б1 б2 Q1Q3+ +б1Q1Q2Q4+Q1Q2Q3+Q1Q2Q4+Q1Q2Q3+ б1 б2Q1Q3+

+б1 Q1Q2Q3Q4=

=б1 Q3 (б2+Q2Q4) +Q2

T3= б1 б2Q1Q2Q3Q4+ б1Q1Q2Q4+ б1 б2Q1+ +б1Q1Q2Q3Q4+ б1 б2Q1Q2Q3Q4+Q1Q2Q3+ б1 б2Q1Q2+ +б1Q1Q2Q4=

=б1Q1 (б2+Q2Q3Q4) + б2Q3Q4+Q1 (б1Q2 (б2+Q4) +Q2Q3)

T4= б1 б2Q1Q2Q3Q4+ б1 б2Q1+ б1 б2Q1+Q1Q2Q3Q4+ +б1 б2Q1Q2Q3+Q1Q2Q4+ б1 б2Q1Q2=

= б1 б2Q1 (Q2Q3+Q2) + б2Q1 (б1Q2Q3Q4+ +б1) +Q2Q4 (Q1Q3+Q1)

z1= б1Q1Q2Q3Q4+ б1 б2Q1Q2Q3=

= б1Q1Q2 (Q3 (Q4+ б2))

z2= б1Q1Q2Q2Q4

z3= б1Q1Q2+ б2Q1Q2Q4+ б1 б2Q1Q3Q4+Q1Q2Q3+

+ б1Q1Q2Q3Q4+ б2Q1Q2Q3Q4=

=Q1Q2Q3Q4 (б1+б2) + Q1 (Q2 (б1+ б2Q4)) +Q3 (б1 б2Q4+Q2)