По системе формул переходов (СФП) граф-схемы алгоритмов (ГСА) с отметками для автоматов Мили и Мура
1. По ГСА построить графы автоматов (ГА) Мили и Мура
2. Закодировать состояния автоматов, выбрать следующий метод кодирования:
3.1. Кодирование, уменьшающее число переключений триггеров.
3. Построить таблицы истинности возбуждения триггеров автоматов Мили и Мура
4. По таблицам получить аналитические выражения для входной части автоматов Мили и Мура, пригодные для построения схем, содержащих только следующие логические элементы:
5.2. . «ИЛИ-НЕ».
5. Построить схемы входной части автоматов Мили и Мура по выражениям из п.5
6. Провести моделирование схем входной части
7. Построить схему запоминающей части, в качестве элемента памяти использовать
8.2 T -триггер.
8. Провести моделирование схем запоминающей части
9. Получить аналитические выражения для выходной части автоматов Мили и Мура, пригодные для построения схем, содержащих только следующие логические элементы:
10.1. «И», «ИЛИ», «НЕ»
Построить схемы выходной части автоматов Мили и Мура
10. Провести моделирование схем выходной части
11. Построить полные схемы автоматов Мили и Мура
12. Провести моделирование полных схем
13. Провести тестирование одной из полученных комбинационных схем применяя следующие методы:
14. Синтезировать самопроверяемую комбинационную схему, применяя следующие методы:
16.1. Синтез схемы с однонаправленным проявлением неисправностей (из элементов с тремя входами и нагрузочной способностью равной двум) и кодирование выходов кодом Бергера.
автомат кодирование триггер
1.1 Система формул переходов
1.2 Переход от системы формул переходов к граф-схеме алгоритмов
ГСА, соответствующая данной СФП, имеет следующий вид:
Рис. 1. Граф-схема алгоритма
1.3 Переход от ГСА к автомату Мура
Расставим на ГСА отметки состояний:
- отметка S 0 ставится на дуге, исходящей из начальной вершины, и на дуге, заходящей в конечную вершину;
- отметки S 1 ,…, St ставятся около операторных вершин;
- отметки S t +1 ,…, Sk ставятся на дугах, заходящих в ждущие вершины.
Рис. 2. Граф- схема алгоритма автомата Мура
1.4 Переход от ГСА к автомату Мили
Синтез цифрового автомата
... ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые обладают памятью. В настоящее время в классе синхронных автоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура. Закон функционирования автоматов Мили может быть ...
В случае автомата Мили отметки состояний ставятся:
- отметка ставится на дуге, исходящей из начальной вершины, и на дуге, заходящей в конечную вершину;
- отметки ставятся на дугах, исходящих из операторных вершин;
- отметки ставятся на дугах, заходящих в ждущие вершины.
Рис.3 Граф- схема алгоритма автомата Мили
1.5 Граф переходов автомата Мура
Рис. 4. Граф переходов автомата Мура
1.6 Граф переходов автомата Мили
Рис 5. Граф переходов автомата Мили
2.1 Синтез входной части автомата Мура
2.1.1 Кодирование состояний автомата
Выпишем в таблицу все переходы. Закодируем состояния автомата Мура следующим методом: Кодирование, упрощающее функции возбуждения триггеров.
|
q 0 |
100 |
|||
|
q 1 |
000 |
|||
|
q 2 |
011 |
|||
|
q 3 |
110 |
|||
|
q 4 |
001 |
|||
|
q 5 |
010 |
|||
|
q 6 |
101 |
|||
2.1.2 Таблица истинности возбуждения T-триггера автомата Мура
Составим, используя кодирование, таблицу истинности возбуждения T-триггера
Таблица 1
Таблица истинности возбуждения T-триггера автомата Мура
|
q |
U |
q’ |
T0 |
T1 |
T2 |
|||
|
q0 |
100 |
x1 |
q0 |
100 |
0 |
0 |
0 |
|
|
q0 |
100 |
x1 |
q1 |
000 |
1 |
0 |
0 |
|
|
q1 |
000 |
x2 |
q2 |
011 |
0 |
1 |
1 |
|
|
q1 |
000 |
x2x3 |
q4 |
001 |
0 |
0 |
1 |
|
|
q1 |
000 |
x2x3 |
q5 |
010 |
0 |
1 |
0 |
|
|
q2 |
011 |
1 |
q3 |
110 |
1 |
0 |
1 |
|
|
q3 |
110 |
x5x2 |
q1 |
000 |
1 |
1 |
0 |
|
|
q3 |
110 |
x2x5 |
q5 |
010 |
1 |
0 |
0 |
|
|
q3 |
110 |
x5 |
q6 |
101 |
0 |
1 |
1 |
|
|
q4 |
001 |
x4 |
q0 |
100 |
1 |
0 |
1 |
|
|
q4 |
001 |
x4x2 |
q2 |
011 |
0 |
1 |
0 |
|
|
q4 |
001 |
x4x2x3 |
q4 |
001 |
0 |
0 |
0 |
|
|
q4 |
001 |
x4x2x3 |
q5 |
010 |
0 |
1 |
1 |
|
|
q5 |
010 |
1 |
q1 |
000 |
0 |
1 |
0 |
|
|
q6 |
101 |
x2 |
q4 |
001 |
1 |
0 |
0 |
|
|
q6 |
101 |
x2 |
q5 |
010 |
1 |
1 |
1 |
|
2.1.3 Функции возбуждения триггеров
По таблице получим аналитические выражения для входной части автомата Мура. Преобразуем формулы для построения схемы, содержащей только элементы «ИЛИ-НЕ».:
2.1.4 Схема входной части автомата Мура
Построим логическую схему по полученным функциям возбуждения триггеров. Схема показана на рисунке 6.
Проверим правильность построения схемы с помощью моделирования ее работы. После моделирования сравним значения T 0 , T1 , T2, со значениями, полученными аналитически.
Рис. 6. Схема входной части автомата Мура
Построим таблицу тестовых значений для проверки правильности работы схемы (таблица 2).
В качестве тестовых наборов будем брать тесты, соответствующие конъюнкциям функций возбуждения триггеров.
Таблица 2
Тестовые наборы для проверки работы схемы
|
№ |
Коньюнкция |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
x1 |
x2 |
x3 |
x4 |
x5 |
T0 |
T1 |
T2 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
— |
— |
— |
1 |
— |
— |
||
|
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
— |
— |
— |
— |
1 |
— |
1 |
||
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
— |
— |
— |
— |
0 |
1 |
— |
— |
||
|
4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
— |
— |
0 |
— |
1 |
— |
1 |
||
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
— |
— |
— |
— |
1 |
— |
— |
||
|
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
— |
1 |
— |
— |
— |
— |
1 |
1 |
||
|
7 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
— |
0 |
0 |
— |
— |
— |
1 |
— |
||
|
8 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
— |
1 |
— |
— |
0 |
— |
1 |
— |
||
|
9 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
— |
— |
— |
— |
1 |
— |
1 |
1 |
||
|
10 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
1 |
— |
1 |
— |
— |
1 |
— |
||
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
0 |
0 |
1 |
— |
— |
1 |
1 |
||
|
12 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
— |
— |
— |
— |
— |
1 |
— |
||
|
13 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
0 |
— |
— |
— |
— |
1 |
1 |
||
|
14 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
— |
0 |
1 |
— |
— |
— |
— |
1 |
||
Доопределим недостающие значения таким образом, чтобы сократить как можно большее число строк и получить кратчайшее покрытие (таблица 3).
Таблица 3
Доопределение тестовых наборов
|
№ |
Коньюнкция |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
x1 |
x2 |
x3 |
x4 |
x5 |
T0 |
T1 |
T2 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
||
|
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
||
|
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
||
|
5 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
||
|
6 |
и |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
||
|
8 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
||
|
9 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
||
|
10 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
||
|
11 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
||
|
12 |
и |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
Проведем моделирование работы схемы (рис. 7).
Сравним полученные значения с таблицей 3. Значения совпадают, следовательно, схема построена правильно.
Рис. 7. Моделирование входной части автомата Мура
2.2 Синтез запоминающей части автомата Мура
2.2.1 Синтез схемы дешифратора
|
q 0 |
100 |
|||
|
q 1 |
000 |
|||
|
q 2 |
011 |
|||
|
q 3 |
110 |
|||
|
q 4 |
001 |
|||
|
q 5 |
010 |
|||
|
q 6 |
101 |
|||
Построим дешифратор согласно кодам состояний (рисунок 8)
Рис. 8. Дешифратор автомата Мура
2.2.2 Схема запоминающей части автомата Мура
Построим запоминающую часть автомата Мура. В качестве элементов памяти будем использовать синхронные T-триггеры. Схема запоминающей части автомата Мура представлена на рисунке 9.
Рис 9. Схема запоминающей части автомата Мура
Проведем моделирование работы схемы (рис.10).
На рисунке видно, что диаграмма отражает правильные значения сигналов состояний, причем изменение выходных значений происходит только при положительном фронте счетного входа.
Рис 10. Моделирование работы запоминающей части автомата Мура
2.3 Синтез выходной части автомата Мура
2.3.1 Функции выхода автомата Мура
2.3.2 Схема выходной части автомата Мура
По функциям выхода построим схему выходной части автомата Мура в базисе «И», «ИЛИ», «НЕ» Схема представлена на рис. 11.
Рис. 11. Схема выходной части автомата Мура
Проведем моделирование работы схемы. Так как в автомате одновременно только одно состояние является активным, в качестве тестовых возьмем наборы с последовательной активизацией состояний.
Таблица 4
Тестовые наборы для проверки работы схемы
|
Вход |
Выход |
||||||||||
|
q 1 |
q 2 |
q 3 |
q 4 |
q 5 |
q 6 |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
||||||
|
0 |
1 |
0 |
0 |
0 |
0 |
||||||
|
0 |
0 |
1 |
0 |
0 |
0 |
||||||
|
0 |
0 |
0 |
1 |
0 |
0 |
||||||
|
0 |
0 |
0 |
0 |
1 |
0 |
||||||
|
0 |
0 |
0 |
0 |
0 |
1 |
||||||
Проведем моделирование работы схемы по данным таблицы 4. Значения полученные аналитически и опытным путем совпадают, следовательно схема построена верно.
Рис. 12. Моделирование работы выходной части автомата Мура
2.4 Объединение частей автомата Мура
Рис. 13. Структурная схема автомата Мура
Объединим полученные части в одну схему, согласно структурной схеме автомата Мура (рис. 13).
Получим схему автомата Мура (рис. 14).
Рис. 14. Схема объединенного автомата Мура
Рис. 15. Граф автомата Мура с отметками перехода
Проведем моделирование работы автомата, используя полученную последовательность переходов. На рис. 16 представлена диаграмма моделирования работы автомата, моделирование проведено по указанным в графе переходам. Значения выходов совпадают с соответствующими значениями на графе, следовательно, схема функционирует правильно.
Рис. 16. Диаграмма моделирования автомата Мура
3.1 Функции возбуждения триггеров и функции выхода автомата Мили
Рассмотрим теперь автомат Мили. Выпишем в таблицу все переходы. Закодируем состояния автомата Мили следующим методом: Кодирование, упреждающее функции возбуждения триггеров.
|
q 0 |
0 |
0 |
1 |
|
|
q 1 |
1 |
0 |
0 |
|
|
q 2 |
1 |
1 |
1 |
|
|
q 3 |
0 |
0 |
0 |
|
|
q 4 |
0 |
0 |
1 |
|
|
q 5 |
1 |
0 |
0 |
|
Таблица 5
Таблица значений входов запоминающей части и выходов автомата
|
q |
U |
q? |
T 0 |
T 1 |
T 2 |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
|
|
q 0 |
q 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
q 0 |
q 1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
||
|
q 1 |
q 2 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
||
|
q 1 |
q 3 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
||
|
q 1 |
q 5 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
||
|
q 2 |
1 |
q 4 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
q 3 |
q 1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
||
|
q 3 |
q 5 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
||
|
q 3 |
q 3 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
||
|
q 3 |
q 4 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
||
|
q 4 |
q 3 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
||
|
q 4 |
q 5 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
||
|
q 4 |
q 0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
q 5 |
q 4 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
||
Получим формулы для функций возбуждения T-триггеров и функций выходов. Формулы для входной части преобразуем так, что бы они содержали только операции «ИЛИ-НЕ»:
- y= ;
y=;
y=;
y=;
y=.
3.2 Схема входной части автомата Мили
Построим схему входной части автомата Мили (рис. 17) по выражениям, полученным в п. 3.1.
Далее построим таблицу тестовых значений для проверки правильности работы схемы (таблица 6).
В качестве наборов будем брать конъюнкции функций возбуждения триггеров.
Рис. 17. Схема входной части автомата Мили
Таблица 6
Тестовые наборы для проверки работы схемы
|
№ |
конъюнкция |
q 0 |
q 1 |
q 2 |
q 3 |
q 4 |
q 5 |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
T 0 T1 T2 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
— |
— |
— |
— |
0— |
||
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
— |
— |
— |
1— |
||
|
3 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
1 |
— |
— |
— |
-1- |
||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
0 |
1 |
— |
— |
1-1 |
||
|
5 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
0 |
0 |
— |
— |
—1 |
||
|
6 |
0 |
0 |
1 |
0 |
0 |
0 |
— |
— |
— |
— |
— |
1— |
||
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
1 |
— |
1 |
— |
1-1 |
||
|
8 |
0 |
0 |
0 |
1 |
0 |
1 |
— |
0 |
0 |
— |
— |
1— |
||
|
9 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
0 |
1 |
1 |
— |
— |
||
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
— |
— |
0 |
— |
-11 |
||
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
0 |
— |
— |
0 |
-11 |
||
|
12 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
— |
— |
— |
1 |
111 |
||
|
13 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
1 |
— |
— |
0 |
-1- |
||
|
14 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
0 |
— |
— |
— |
111 |
||
Доопределим недостающие значения таким образом, чтобы сократить как можно большее число строк и получить кратчайшее покрытие.
В таблице 7 представлены тестовые наборы для проверки входной части автомата Мили.
Таблица 7
Доопределение тестовых наборов
|
№ |
конъюнкция |
q 0 |
q 1 |
q 2 |
q 3 |
q 4 |
q 5 |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
T 0 T1 T2 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
000 |
||
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
100 |
||
|
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
010 |
||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
101 |
||
|
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
001 |
||
|
6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
100 |
||
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
101 |
||
|
8 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
100 |
||
|
9 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
000 |
||
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
011 |
||
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
011 |
||
|
12 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
111 |
||
|
13 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
010 |
||
|
14 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
111 |
||
Рис. 18. Диаграмма моделирования работы входной части автомата Мили
3.3 Схема выходной части автомата Мили
По таблице 5 построим схему выходной части автомата Мили используя элементы «И», «ИЛИ», «НЕ» (рис. 19).
Рис. 19. Выходная часть автомата Мили
Построим таблицу проверки конъюнкций выходной части автомата, соединив одинаковые конъюнкции.
Таблица 8
Тестовые наборы для проверки работы схемы
|
№ |
конъюнкция |
q 0 |
q 1 |
q 2 |
q 3 |
q 4 |
q 5 |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
y 1 y 2 y 3 y 4 y 5 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
— |
— |
— |
— |
— — — — — |
||
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
— |
— |
— |
1 — — — 1 |
||
|
3 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
1 |
— |
— |
— |
1 — 1 — 1 |
||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
0 |
1 |
— |
— |
— 1 — — — |
||
|
5 |
0 |
1 |
0 |
0 |
0 |
0 |
— |
0 |
0 |
— |
— |
— 1 — — 1 |
||
|
6 |
0 |
0 |
1 |
0 |
0 |
0 |
— |
— |
— |
— |
— |
1 — — 1 — |
||
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
1 |
— |
1 |
— |
1 — — — 1 |
||
|
8 |
0 |
0 |
0 |
1 |
0 |
1 |
— |
0 |
0 |
— |
— |
— 1 — — 1 |
||
|
9 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
0 |
1 |
1 |
— |
— 1 — — — |
||
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
— |
— |
— |
0 |
— |
1 — — 1 — |
||
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
0 |
— |
— |
0 |
— 1 — — — |
||
|
12 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
— |
— |
— |
1 |
— 1 — — 1 |
||
|
13 |
0 |
0 |
0 |
0 |
1 |
0 |
— |
1 |
— |
— |
0 |
— — — — — |
||
|
14 |
0 |
0 |
0 |
0 |
0 |
1 |
— |
0 |
— |
— |
— |
1 — — 1 — |
||
Таблица 9
Доопределение тестовых наборов
|
№ |
конъюнкция |
q 0 |
q 1 |
q 2 |
q 3 |
q 4 |
q 5 |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
y 1 y 2 y 3 y 4 y 5 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 0 0 0 0 |
||
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 0 0 0 1 |
||
|
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 0 1 0 1 |
||
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 1 0 0 0 |
||
|
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 0 0 1 |
||
|
6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 0 0 1 0 |
||
|
7 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 0 0 0 1 |
||
|
8 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 1 0 0 1 |
||
|
9 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 1 0 0 0 |
||
|
10 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 0 0 1 0 |
||
|
11 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 0 0 0 |
||
|
12 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 1 0 0 1 |
||
|
13 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 0 0 0 0 |
||
|
14 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 0 0 1 0 |
||
Диаграмма моделирования, построенная по тестовым наборам из таблицы 9, представлена на рис. 20.
Рис.20. Моделирование работы выходной части автомата Мили
Значения в таблице 9 и на диаграмме моделирования (рис. 20) совпадают, значит схема построена правильно.
3.4 Схема запоминающей части автомата Мили
Запоминающая часть выглядит следующим образом (рис. 21)
Рис. 21. Запоминающая часть автомата Мили
На рисунке 22 показана диаграмма моделирования работы схемы запоминающей части автомата Мили.
Рис. 22. Моделирование работы схемы запоминающей части автомата Мили
Проведя моделирование работы запоминающей части, мы видим, что диаграмма моделирования отражает правильные значения сигналов состояний, причем изменение выходных значений происходит только при положительном фронте счетного входа.
3.5 Объединение частей автомата Мили
Объединим полученные части в одну схему, согласно структурной схеме автомата Мили (рис. 23).
Рис. 23. Структурная схема автомата Мили
Получим схему автомата Мили (рис. 24).
Рис. 24. Схема автомата Мили
Проверим правильность работы автомата по графу (рис. 5).
Построим путь, содержащий все возможные переходы. Проведем моделирование работы автомата, используя полученную последовательность переходов.
На рисунке 25 представлен обход графа для построения последовательных тестовых наборов., Рис. 25. Граф Мили с отметками переходов
На рисунке 26 представлена диаграмма моделирования работы автомата, моделирование проведено по указанным в графе переходам.
Рис. 26. Моделировние работы автомата Мили
4.1 Метод псевдослучайной генерации тестов
Внесем в схему выходной части автомата Мура (рис.11) пять неисправностей (рис.27).
Пронумеруем неисправности, далее будем рассматривать пять схем, в каждой из которых есть только одна из указанных неисправностей. Согласно алгоритму псевдослучайной генерации тестов, подадим на каждую из имеющихся схем, включая исправную, один и тот же случайный набор.
Рис. 27. Схема выходной части автомата Мура с неисправностями
Подадим на все схемы случайный набор из 5 тестов:
|
№ |
q 1 q2 q3 q4 q5 q6 |
|
|
1 |
100000 |
|
|
2 |
010000 |
|
|
3 |
001000 |
|
|
4 |
000100 |
|
|
5 |
000010 |
|
На рис.28 показана диаграмма моделирования работы исходной схемы. На рис.29 показана диаграмма моделирования работы схемы с неисправностью 1, на диаграмме выделен набор, обнаруживающий эту неисправность (константа 0 на входе дизъюнктора).
Следовательно, этот набор вносим в список тестирования.
Рис. 28. Моделирование работы исходной выходной части автомата Мура, Рис. 29. Диаграммы моделирования неисправной схемы №1
На рис.30 показана диаграмма моделирования работы исходной схемы. На рис.31 показана диаграмма моделирования работы схемы с неисправностью 2, на диаграмме выделен набор, обнаруживающий эту неисправность (константа 0 на входе дизъюнктора).
Следовательно, этот набор вносим в список тестирования.
Рис. 30. Моделирование работы исходной выходной части автомата Мура, Рис. 31. Диаграммы моделирования исходной и неисправной схемы №2
На рис.32 показана диаграмма моделирования работы исходной схемы. На рис.33 показа…
