Функции 4 страница

Аналогично кодированию входных и выходных сигналов каждому состоянию абстрактного автомата в структурном автомате сопоставляется вектор компонента, которого равна 0 или 1, а число компонент равно числу элементов памяти, причем для кодирования состояний абстрактного автомата различными векторами должно быть выполнено условие:

Закодируем состояния абстрактного автомата, заданного табл.23 и табл.24. Т.к. число его состояний равно пяти, в структурном автомате должно быть, по крайней мере, три элемента памяти Сопоставим каждому состоянию автомата двоичный код следующим образом:

Если в абстрактном автомате, заданном табл.23, 24 каждое состояние, входной и выходной сигналы заменить их кодами, то получим таблицы переходов (табл. 25) и выходов (табл. 26) структурного автомата. В этом автомате три элемента памяти два входных и три выходных полюса.

Изменение состояний элементов памяти происходит под действием сигналов называемых функциями возбуждения памяти автомата. Таким образом, после выбора элементов памяти и кодирования состояний, синтез структурного автомата сводится к синтезу комбинационной схемы, реализующей функции:

где - функции обратной связи от памяти автомата к комбинационной схеме (КС).

4.8. Канонический метод структурного синтеза

Из таблиц 25 и 26 легко видеть, что при переходе автомата из состояния 000 в состояние 010 под действием входного сигнала 01 с выдачей выходного сигнала 001 происходит переключение триггеров: первого и третьего из нуля в нуль и второго из нуля в единицу, т.е. на входы триггеров необходимо подать сигналы: D₁=D₂=0, D₂=1.

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

Аргументами функций возбуждения будут Таблица 25 задает булевы функции от указанных аргументов, являясь при этом "свернутой": часть набора отмечает столбец, а часть строку таблицы 25. СДНФ для функций запишется:

Таблица 26 дает булевы функции зависящие от пяти аргументов СДНФ функций выхода имеют вид:

Не останавливаясь на вопросах минимизации можно построить по (1), (2) логическую схему. Заметим, что для минимизации полученных выражений можно было бы использовать наборы переменных, на которых соответствующие функции не определены. Эта неопределенность возникает вследствие того, что не все наборы используются для кодирования состояний (101, 110, 111) и входных сигналов (11), а так же из-за того, что синтезируемый автомат - частичный. Логическая схема, её сложность зависят от кодирования входных и выходных сигналов и состояний абстрактного автомата. Алгоритм кодирования состояний, минимизирующий число термов в функциях: следующий:

- упорядочить состояния в порядке уменьшения числа их появлений в таблице переходов абстрактного автомата;

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

Схема структурного автомата имеет вид, показанный на рис.37

Рис. 37

4.9. Графический метод структурного синтеза

При графическом методе синтеза структурный автомат представляется в виде графа.

При этом состояния структурного автомата записываются соответствующими кодами (для автомата, заданного табл. 25 и табл. 26 это коды: 000 – а₁ 001 - а₂, 011 – а₃, 010 - а₄, 100 – а₅ ); вместо входных сигналов 00, 01 и 10 на дугах графа записываются: соответственно. Вместо выходных сигналов 100, 010 и 011 на дугах графа будем записывать и соответственно, а вместо выходного сигнала 000 ставить прочерк (-), т.к. ни одна его компонента не равна единице. Граф структурного автомата представлен на рис. 38.

Рис. 38

Контрольные вопросы

1. Понятие комбинационной схемы (КС).

2. Приведите алгоритм анализа КС.

3. Назовите основные этапы синтеза КС.

4. Понятие цифрового автомата.

5. Из каких основных частей состоит теория проектирования автоматов?

6. Определение и способы задания абстрактных автоматов.

7. Какие два класса абстрактных автоматов получили наибольшее распространение на практике?

8. Поясните термины: частичный автомат, полностью определенный автомат.

9. Приведите пример задания автомата Мили.

10. Приведите пример табличного задания автомата Мура.

11. Чем отличает граф автомата Мура от графа автомата Мили?

12. Какие абстрактные автоматы называются эквивалентными?

13. Поясните, как выполняется переход от автомата Мили к автомату Мура и обратно.

14. В чем суть алгоритма Ауфенкампа и Хона?

15. Каковы особенности задания структурного автомата?

16. Поясните суть канонического метода структурного синтеза.

17. Каковы особенности графического метода структурного синтеза?

ЛИТЕРАТУРА

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 415 с.

2. Горбатов В.А. Основы дискретной математики. М.: Наука, 1986. 311 с.

3. Яблонский СВ. Введение в дискретную математику. М.: Наука, 1986.384 с.

4. Баранов СИ. Синтез микропрограммных автоматов. Л.: Энергия, 1974.216 с.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992. 262 с.

6. Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высшая школа, 1987. 272 с.

7. Мелихова З.А. Методические указания к практическим занятиям и выполнению контрольных работ по курсу «Математические основы дискретной техники». Таганрог: ТРТИ, 1993.16 с.

. НОРМАЛЬНЫЕ И КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ 3

1.1 Разложение булевых функций по переменным.................... 3

1.2 Совершенные дизъюнктивная и конъюнктивная
нормальные формы булевой функции......................................... 4

1.3 Каноническая форма булевой функции в алгебре

Жегалкина................................................................................................ 7

Контрольные вопросы....................................................................... 9

2. ПОЛНОТА СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ................................ 9

Контрольные вопросы.......................................................................... 14

3. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ...................................... 14

3.1. Постановка задачи минимизации булевых функций в классе ДНФ (КНФ) 14

3.2. Алгоритм минимизации булевых функций по методу Квайна-Мак-Класки,. 16

3.3. Минимизация булевых функций с помощью диаграмм Вейча (карт Карно) 19

3.4. Минимизация не полностью определённых (частичных)

булевых функций.................................................................................... 24

Контрольные вопросы....................................................................... 27

4. КОМБИНАЦИОННЫЕ СХЕМЫ И КОНЕЧНЫЕ

АВТОМАТЫ................................................................................................ 28

4.1. Понятие комбинационной схемы.............................................. 28

4.2. Задачи анализа и синтеза КС.................................................... 29

4.3. Понятие цифрового автомата..................................................... 35

4.4. Определение и способы задания абстрактных
автоматов................................................................................................ 35

4.5. Преобразования моделей абстрактных автоматов........... 41

4.6. Минимизация полностью определенных автоматов

Мили.......................................................................................................... 50

4.7. Структурный автомат................................................................ 54

4.8. Канонический метод структурного синтеза.......................... 59

4.9. Графический метод структурного синтеза.......................... 62

Контрольные вопросы.......................................................................... 63

ЛИТЕРАТУРА................................................................................................ 64

Мелихова Зинаида Александровна

Мелихова Оксана Аскольдовна