|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[15] Пример 4.4. Необходимо минимизировать первоначальную таблицу переходов, полученную в примере 3.3 (см. табл. 3.9). Решение. Вначале попытаемся выявить эквивалентные или псесдоэкннвалентные состояния. Ими могли бы быть только устойчивые состояния (2) и (4), так как они находятся в одном и том же столбце. Однако этим состояниям соответствуют различные состояния выхода. Поэтому в табл. 3.9 эквивалентных и псевдоэквпвалентных состояний нет. Попытаемся теперь найти совместные внутренние состояния, используя метод, изложенный в [1, З]. Для этого составим треугольную таблицу (табл. 4.4).
Таблица 4.4 Таблица 4.5
XiX2l z
Исходя яз этой таблицы найдем максимальные группы совместных внутренних состояний: 1, 2; 3 4. Таким образом, можно объединить внутренние состояния xi и ms, а также у.з и Я4. После объединения этих внутренних состоянии получим минимизированную таблицу переходов (табл. 4.5) с двумя внутренними состояниями, т. е. требуется один элемент памяти. Пример 4.5. Необходимо минимизировать первоначальную таблицу переходов, полученную в примере 3.4 (см. табл. 3.13). Решение. Анализ табл. 3.13 показывает, что эквивалентных состояний в ней иет. Однако имеются псевдоэквивалентные состояния (2) и (7). После их объединения и замены состояния (7) на состояние (2) получим табл. 4.6. 12 3 4 5 Выявим теперь совместимые внутренние состояния, для чего построим треугольную таблицу (табл. 4.7). В табл. 4.7 в клетках* (2, 5), (2, 6) и (3, 5) указана пара внутренних состояний яз и Хб. Это означает, что внутренние состояния ха и x.s; v.i и Хо; xs ii у.5 могут быть объединены (т. е. будут совместимыми), если совместимы внутренние состояния Хз и хв. Однако внутренние состояния Хз и лл несовместимы-крест в клетке (3, 6). Значит, пары внутренних состояний Хг и у.ъ, у--!, и -х.з; у.з .ii X5 несовместимы. Поэтому в клетках (2,5), С2, 6) и (3,5) треугольной таблицы указаны кресты. Найдем теперь группы совместимых внутренних состояний: 1 23456 1, 2 3,44,55,6 1, 5 1, 6 1,5 ,6 Из них максимальными группами совместимых внутренних состоянии будут следующие: а=1,2; 6=1, 5, 6; с=3, 4; d=4, 5, три пары из которых (группы а и &, Ь и d) являются .пересекающимися. Остальные группы 5, 1, 6 5, 6, 1, 2, 3, 4, 5, 6) входят в максимальные группы и поэтому не являются максимальными. Теперь, строя таблицу покрытий (табл. 4.8), необходимо найти минимальное число максимальных групп совместимых внутренних состояний. По табл. 4.8 составим функцию Петрика [3]: F = (a\J b) ас (с V d) (b V d) b. Преобразуем ее в дизъюнктивную нормальную форму (ДНФ): F= (а у ab) (с \Jcd) (b V bd) = acb. * В клетке (i, j) номер I соответствует столбцу, а строке треугольной таблицы. i Таким образом, все максим ал ь;;ые группы, кроме d, должны быть использованы при построении минимальчои таблицы переходов (табл. 4.9) с тремя внутренними состояниями. При этом состояние автомата обозначаем буквой (номером) того внутреннего состояния, в котором оно устойчиво. Следует заметить, что выявлять и объединять эквивалентные и псевдоэквивалентные состояния перед выявлением и объединением совместимых внутренних состояний нет необходимости. Можно сразу начать выявление совместимых внутренних состояний с последующим их объединением. При этом объединятся, если они есть, эквивалентные и псевдоэквивалентные состояния автомата. К тому же в ряде случаев первоначальное объединение псевдоэквивалентных состояний недоопределенного автомата может ухудшить окончательное решение, т. е. будет получен автомат с большим числом внутренних состояний по сравнению с автоматом, для которого сразу выявлялись совместимые внутренние состояния. Пример 4.6. Необходимо минимизировать таблицу переходов (см. табл. 3.16), полученную в примере 3.5. Таблица 4.10
|
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||