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

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

Курсовая работа

по дисциплине:

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

на тему:

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

Выполнила: студентка 3 курса

группы 22304 Шакирова Г.Р.

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

Елабуга 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

aixj

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

x1

a1y1

a1y1

a2y1

a3y1

a0y0

a0y0

a6y1

a7y1

a8y1

a9y1

a10y1

a11y1

a12y1

a0y0

a0y0

x2

a2y1

a1y1

a2y1

a3y1

a0y0

a0y0

a6y1

a7y1

a8y1

a9y1

a10y1

a11y1

a12y1

a0y0

a0y0

x3

a0y0

a2y1

a3y1

a4y4

a0y0

a0y0

a7y1

a8y1

a9y1

a10y1

a11y1

a12y1

a13y2

a0y0

a0y0

x4

a0y0

a3y1

a4y4

a5y5

a0y0

a0y0

a8y1

a9y1

a10y1

a11y1

a12y1

a13y1

a14y3

a0y0

a0y0

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

Рисунок № 1

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

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

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

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

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

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

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

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

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

Таблица № 2
Qkai	Q1	Q2	Q3	Q4
a0	0	0	0	0
a1	0	0	0	1
a2	0	0	1	0
a3	0	0	1	1
a4	0	1	0	0
a5	0	1	0	1
а6	0	1	1	0
а7	0	1	1	1
а8	1	0	0	0
а9	1	0	0	1
а10	1	0	1	0
а11	1	0	1	1
а12	1	1	0	0
а13	1	1	0	1
а14	1	1	1	0

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

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

Таблица № 3
αmxj	α1	α2
x1	0	0
x2	0	1
x3	1	0
x4	1	1

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

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

Таблица № 4
zpys	z1	z2	z3
y0	0	0	0
y1	0	0	1
y2	0	1	0
y3	0	1	1
y4	1	0	0
y5	1	0	1

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

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

Таблица № 5
aixj	a00000	a10001	a20010	a30011	a40100	a50101	a60110	a70111
00	0001001	0001001	0010001	0011001	0000000	0000000	0110001	0111001
01	0010001	0001001	0010001	0011001	0000000	0000000	0110001	0111001
10	0000000	0010001	0011001	0100100	0000000	0000000	0111001	1000001
11	0000000	0011001	0100100	0101101	0000000	0000000	1000001	1001001

Таблица № 5 (продолжение)
aiαm	a81000	a91001	a101010	a111011	a121100	a131101	a141110
00	1000001	1001001	1010001	1011001	1100001	0000000	0000000
01	1000001	1001001	110001	1011001	1100001	0000000	0000000
10	1001001	1010001	1011001	1100010	1101010	0000000	0000000
11	1010001	1011001	1100001	1101001	1110011	0000000	0000000

Таблица № 6
α1	α2	Q1	Q2	Q3	Q4	Q1 (t+1)	Q2 (t+1)	Q3 (t+1)	Q4 (t+1)	z1	z2	z3	T1	T2	T3	T4
0	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0	0	1	0	0	0	0
0	0	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0
0	0	0	0	1	1	0	0	1	1	0	0	1	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0
0	0	0	1	0	1	0	0	0	0	0	0	0	0	1	0	1
0	0	0	1	1	0	0	1	1	0	0	0	1	0	0	0	0
0	0	0	1	1	1	0	1	1	1	0	0	1	0	0	0	0
0	0	1	0	0	0	1	0	0	0	0	0	1	0	0	0	0
0	0	1	0	0	1	1	0	0	1	0	0	1	0	0	0	0
0	0	1	0	1	0	1	0	1	0	0	0	1	0	0	0	0
0	0	1	0	1	1	1	0	1	1	0	0	1	0	0	0	0
0	0	1	1	0	0	1	1	0	0	0	0	1	0	0	0	0
0	0	1	1	0	1	0	0	0	0	0	0	0	1	1	0	1
0	0	1	1	1	0	0	0	0	0	0	0	0	1	1	1	0
0	0	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-
0	1	0	0	0	0	0	0	1	0	0	0	1	0	0	1	0
0	1	0	0	0	1	0	0	0	1	0	0	1	0	0	0	0
0	1	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0
0	1	0	0	1	1	0	0	1	1	0	0	1	0	0	0	0
0	1	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0
0	1	0	1	0	1	0	0	0	0	0	0	0	0	1	0	1
0	1	0	1	1	0	0	1	1	0	0	0	1	0	0	0	0
0	1	0	1	1	1	0	1	1	1	0	0	1	0	0	0	0
0	1	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	1	1	0	0	1	1	0	0	1	0	0	1	0	0	0	0
0	1	1	0	1	0	1	0	1	0	0	0	1	0	0	0	0
0	1	1	0	1	1	1	0	1	1	0	0	1	0	0	0	0
0	1	1	1	0	0	1	1	0	0	0	0	1	0	0	0	0
0	1	1	1	0	1	0	0	0	0	0	0	0	1	1	0	1
0	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	0
0	1	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	1	0	0	1	0	0	0	1	0	0	1	1
1	0	0	0	1	0	0	0	1	1	0	0	1	0	0	0	1
1	0	0	0	1	1	0	1	0	0	1	0	0	0	1	1	1
1	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0
1	0	0	1	0	1	0	0	0	0	0	0	0	0	1	0	1
1	0	0	1	1	0	0	1	1	1	0	0	1	0	0	0	1
1	0	0	1	1	1	1	0	0	0	0	0	1	1	1	1	1
1	0	1	0	0	0	1	0	0	1	0	0	1	0	0	0	1
1	0	1	0	0	1	1	0	1	0	0	0	1	0	0	1	1
1	0	1	0	1	0	1	0	1	1	0	0	1	0	0	0	1
1	0	1	0	1	1	1	1	0	0	0	0	1	0	1	1	1
1	0	1	1	0	0	1	1	0	1	0	1	0	0	0	0	1
1	0	1	1	0	1	0	0	0	0	0	0	0	1	1	0	1
1	0	1	1	1	0	0	0	0	0	0	0	0	1	1	1	0
1	0	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-
1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	1	0	0	1	1	0	0	1	0	0	1	0
1	1	0	0	1	0	0	1	0	0	1	0	0	0	1	1	0
1	1	0	0	1	1	0	1	0	1	1	0	1	0	1	1	0
1	1	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0
1	1	0	1	0	1	0	0	0	0	0	0	0	0	1	0	1
1	1	0	1	1	0	1	0	0	0	0	0	1	1	1	1	0
1	1	0	1	1	1	1	0	0	1	0	0	1	1	1	1	0
1	1	1	0	0	0	1	0	1	0	0	0	1	0	0	1	0
1	1	1	0	0	1	1	0	1	1	0	0	1	0	0	1	0
1	1	1	0	1	0	1	1	0	0	0	0	1	0	1	1	0
1	1	1	0	1	1	1	1	0	1	0	0	1	0	1	1	0
1	1	1	1	0	0	1	1	1	0	0	1	1	0	0	1	0
1	1	1	1	0	1	0	0	0	0	0	0	0	1	1	0	1
1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	0
1	1	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-

Т1 Таблица № 7
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	0	0	0	0	0	0	0	0	0	1	-	1	0	0	0	0
01	0	0	0	0	0	0	0	0	0	1	-	1	0	0	0	0
11	0	0	0	0	1	1	0	0	0	1	-	1	0	0	0	0
10	0	0	0	0	0	1	0	0	0	1	-	1	0	0	0	0

Т2 Таблица № 8
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	0	0	0	0	0	0	1	1	0	1	-	1	0	0	0	0
01	0	0	0	0	0	0	1	1	0	1	-	1	0	0	0	0
11	0	0	1	1	1	1	1	1	0	1	-	1	1	1	0	0
10	0	0	1	0	0	1	1	1	0	1	-	1	0	1	0	0

Т3 Таблица № 9
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	0	0	0	0	0	0	0	0	0	0	-	1	0	0	0	0
01	1	0	0	0	0	0	0	0	0	0	-	1	0	0	0	0
11	0	1	1	1	1	1	0	0	1	0	-	1	1	1	1	1
10	0	1	1	0	0	1	0	0	0	0	-	1	0	1	1	0

Т4 Таблица № 10
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	1	0	0	0	0	0	1	0	0	1	-	0	0	0	0	0
01	0	0	0	0	0	0	1	0	0	1	-	0	0	0	0	0
11	0	0	0	0	0	0	1	0	0	1	-	0	0	0	0	0
10	0	1	1	1	1	1	1	0	1	1	-	0	1	1	1	1

Z1 Таблица № 11
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	0	0	0	0	0	0	0	0	0	0	-	0	0	0	0	0
01	0	0	0	0	0	0	0	0	0	0	-	0	0	0	0	0
11	0	0	1	1	0	0	0	0	0	0	-	0	0	0	0	0
10	0	0	1	0	0	0	0	0	0	0	-	0	0	0	0	0

Z2 Таблица № 12
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	0	0	0	0	0	0	0	0	0	0	-	0	0	0	0	0
01	0	0	0	0	0	0	0	0	0	0	-	0	0	0	0	0
11	0	0	0	0	0	0	0	0	1	0	-	0	0	0	0	0
10	0	0	0	0	0	0	0	0	1	0	-	0	0	0	0	0

Z3 Таблица № 13
Qkαm	0000	0001	0011	0010	0110	0111	0101	0100	1100	1101	1111	1110	1010	1011	1001	1000
00	1	1	1	1	1	1	0	0	1	0	-	0	1	1	1	1
01	1	1	1	1	1	1	0	0	1	0	-	0	1	1	1	0
11	0	1	1	0	1	1	0	0	1	0	-	0	1	1	1	1
10	0	1	0	1	1	1	0	0	0	0	-	0	1	1	1	1

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