ВЛИЯНИЕ КОДИРОВАНИЯ СОСТОЯНИЙ УПРАВЛЯЮЩЕГО АВТОМАТА НА СЛОЖНОСТЬ КОМБИНАЦИОННОЙ СХЕМЫ

Авторы
Файлы

Кроткова М.А. Федосеева Л.И. Статья в формате PDF 576 KB

Задача кодирования состояний является одной из основных задач канонического метода структурного синтеза управляющих автоматов. Кодирование заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата А = {а₁, ..., а_m} и множеством R-компонентных векторов {К₁, ..., К_m), Кm = (е_m1, ..., emR}, где е_mR - состояние r-го элемента памяти r = 1, ..., R.

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния а_m с кодом 0101 в состояние а_s, с кодом 1001, то это означает, что триггер Т₁, переходит из состояния 0 в состояние 1, триггер Т₂ - из состояния 1 в состояние 0, а состояния триггеров Т₃, и Т₄ не изменяются.

Целью данной работы является анализ влияния кодирования состояний автомата на сложность комбинационной схемы. Большое число работ, начало которых было положено Хартманисом и Стирном, посвящено получению такого кодирования, при котором уменьшается зависимость функций возбуждения памяти от переменных обратной связи. Хартманис и Стирн показали, что этот подход тесно связан с существованием определенных разбиений множества состояний автомата. Как правило, нахождение вариантов кодирования состояний, которые обеспечивают ослабленную функциональную зависимость для функций возбуждения, дает более экономичную схему, чем при других типах кодирования. Методы кодирования состояний с ослаблением функциональной зависимости тесно связаны с декомпозицией автомата.

В процессе работы были исследованы два метода кодирования состояний автомата. В первом случае состояния автомата по возможности были закодированы соседними кодами. Во втором применялся эвристический алгоритм кодирования состояний, минимизирующий суммарное число изменений элементов памяти на всех переходах автомата [1]. При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, вследствие чего минимизируется комбинационная схема. Для данного способа кодирования состояний был разработан алгоритм (рисунок) и программа в среде Delphi 7.0.

Исследования проводились на примере нескольких структурных таблиц переходов автоматов Мили и Мура, задающих алгоритм работы управляющих автоматов с жесткой логикой. В примерах для построения памяти автомата были использованы RS-триггеры. Комбинационные схемы были реализованы на ПЛИС фирмы Xilinx. Для каждого способа кодирования состояний автомата был проведен подсчет количества логических блоков N, необходимых для реализации систем канонических уравнений функций возбуждения памяти φ_i.

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

Схема алгоритма

Список литературы

Бapaнов С.И. Синтез микропрограммных автоматов. - Л.: Энергия, Ленингр. отд-ние, 1979.
Федосеева Л.И. Элементы теории цифровых автоматов: учебное пособие. - Пенза: Изд-во Пенз. гос. ун-та, 2004.
Федосеева Л.И. Синтез управляющих автоматов: учебное пособие. - Пенза: Изд-во Пензенского технологического института, 2002.

Особенности применения математикостатистических методов обработки данных медицинских исследований и их учет при подготовке будущего врача

Статья в формате PDF 131 KB...

01 07 2026 10:11:42

МАТЕМАТИЧЕСКАЯ ГРАМОТНОСТЬ КАК УСЛОВИЕ РАЗВИТИЯ ОБЩЕСТВА

Статья в формате PDF 101 KB...

30 06 2026 12:33:20

МЕТОДОЛОГИЧЕСКИЕ ПОДХОДЫ СОВЕРШЕНСТВОВАНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ШКОЛЬНЫМ ОБРАЗОВАНИЕМ

Статья в формате PDF 96 KB...

29 06 2026 22:11:13

ИНФОРМАЦИОННЫЙ АНАЛИЗ СПЕРМЫ

Статья в формате PDF 164 KB...

28 06 2026 19:25:20

ОСОБЕННОСТИ ТЕХНОЛОГИЙ КОНТРОЛЯ В ПРОФЕССИОНАЛЬНОМ ОБРАЗОВАНИИ

Статья в формате PDF 122 KB...

27 06 2026 1:10:47

Состояние природной среды в условиях техногенной деятельности человека

Статья в формате PDF 103 KB...

26 06 2026 21:33:33

ОПЫТ ЛЕЧЕНИЯ И РЕАБИЛИТАЦИИ БОЛЬНЫХ КАРДИОЛОГИЧЕСКОГО ПРОФИЛЯ МЕТОДОМ КВАНТОВОЙ ТЕРАПИИ

Статья в формате PDF 108 KB...

25 06 2026 2:22:15

ПРОИЗВОДСТВО РЖАНО-ПШЕНИЧНОГО ХЛЕБА С ЯГОДАМИ

Статья в формате PDF 253 KB...

24 06 2026 14:25:28

Возрастная анатомия лимфатического русла толстой кишки у человека

Статья в формате PDF 103 KB...

23 06 2026 6:11:53

ЗНАЧЕНИЕ ОСВОЕНИЯ ДИСЦИПЛИН ХУДОЖЕСТВЕННОЭСТЕТИЧЕСКОГО ЦИКЛА СТУДЕНТАМИ ПЕДАГОГИЧЕСКОГО КОЛЛЕДЖА

Статья в формате PDF 199 KB...

22 06 2026 5:12:24

МОЛОЧНЫЙ КОКТЕЙЛЬ «ДИАБЕТИЧЕСКИЙ»

Статья в формате PDF 244 KB...

21 06 2026 22:51:30

ПРИОРИТЕТНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ В ОБЛАСТИ СОЗДАНИЯ РЕСУРСОСБЕРЕГАЮЩИХ ТЕХНОЛОГИЙ ЗАЩИТЫ САДОВ ОТ ВРЕДИТЕЛЕЙ

Статья в формате PDF 114 KB...

20 06 2026 3:23:51

О НАПРАВЛЕННОСТИ УСИЛИЙ ПО ОЗДОРОВЛЕНИЮ ДЕТЕЙ И МОЛОДЕЖИ В ХОДЕ РЕАЛИЗАЦИИ НАЦИОНАЛЬНЫХ ПРОЕКТОВ «ЗДОРОВЬЕ» И «ОБРАЗОВАНИЕ»

Статья в формате PDF 113 KB...

19 06 2026 12:10:27

Микробиологические и биофизические исследования трaнcпортируемой воды водовода Астpaxaнь-Мангышлак (оценка качества воды в зимний период)

Одной из наиболее актуальных проблем современности является проблема обеспечения населения качественной питьевой водой. Для решения проблемы деффицита воды Прикаспийского региона в 1989 году был построен водовод «Астpaxaнь-Мангышлак», общей протяженностью 1041 км который берет свое начало из протоки Кигач, расположенной в дельте р. Волга. Биотестирование на дафниях в исходной воде и в воде, трaнcпортируемой по водоводу показало, что процент погибших дафний по сравнению с контролем составляет в зимний период 14%, а в весенний – 20%. В летний период процент погибших дафний явлется наиболее выским – 31,8% и к осени этот показатель снижается до 23,8%. Эти значения меньше 50%, то есть в соответствии с п.3.1.5 РД – 118-02-90 тестируемая вода не оказывает острого токсического действия на дафний. ...