МЕТОДИКА ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ «СИНТЕЗ АВТОМАТА-РАСПОЗНАВАТЕЛЯ КОДА»
- Авторы: Тюрин С.Ф1, Аляев Ю.А2
- Учреждения:
- Пермский национальный исследовательский политехнический университет
- Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации
- Выпуск: № 24 (2017)
- Страницы: 79-90
- Раздел: Статьи
- URL: https://ered.pstu.ru/index.php/elinf/article/view/2621
- DOI: https://doi.org/10.15593/вестник%20пермского%20национального%20исследовательского%20политехнического%20университета.%20электротехника,%20информационные%20технологии,%20системы%20управления.v0i24.2621
- Цитировать
Аннотация
Одной из «учебно-ёмких» задач дискретной математики является задача синтеза конечного автомата, например автомата-распознавателя. В ней аккумулируются практически все темы: теория множеств, элементы общей алгебры, комбинаторика, теория графов, кодирование. Эта задача может использоваться в качестве комплексной при оценке знаний, умений и владений. Она хороша ещё и тем, что легко сформировать достаточное количество вариантов, что позволяет предложить каждому студенту свой вариант. Варианты хорошо масштабируются, причём уменьшение длины распознаваемой последовательности создаёт условия для решения задачи в рамках 15-минутной контрольной работы, а при увеличении - сложность достаточна для курсовой работы. Кроме того, результаты решения могут быть использованы в дисциплине «Схемотехника», изучаемой в том же семестре. Описывается методика синтеза и моделирования синхронного автомата-распознавателя заданной последовательности с повторяющимися символами для курсовой работы по дисциплине «Схемотехника» на основе схем-шаблонов, как продолжения лабораторного занятия. Показывается, что в шаблоне блок формирования кода клавиши может быть реализован на базе кодера, а логика переходов и выходов - на основе дешифраторов. Выполняется моделирование в системе схемотехнического моделирования NI Multisim 10 фирмы National Instruments Electronics Workbench Group. Делается вывод о целесообразности использования предложенного подхода для простой последовательности в лабораторных работах и усложнённых версий синхронного автомата во время курсовой работы студентов. Предлагаемая методика может обеспечить масштабирование заданий и времени их выполнения (контроля), что вносит существенный вклад в дело повышения качества подготовки отечественных специалистов в области электронной компонентной базы.
Полный текст
Введение. В современных условиях высшего образования при реализации учебных программ бакалавриата в России преподаватели часто сталкиваются с катастрофическим дефицитом времени. Это приводит как к невозможности в полной мере реализовать полноценные эксперименты на лабораторных занятиях, так и к угасанию интереса обучаемых, на которых буквально сваливаются горы информации и валы различных заданий, отчётов и пр. В связи с этим предлагается своего рода масштабирование учебных заданий с использованием шаблонов, за счет чего сокращается время на проведение эксперимента, так как требуется провести незначительную коррекцию шаблона в соответствии с вариантом задания. В крайнем случае, если изменения не были сделаны, студент может продемонстрировать хотя бы работу шаблона, что свидетельствует о каком-то низком, но уровне знаний. Эта методология также упрощает преподавателю проверку знаний, умений и владений студента. Вместе с тем небольшое увеличение размерности задачи может привести к изменению шаблона так, что задание может быть использовано в качестве курсовой работы. Уменьшение размерности задания вполне годится для использования на зачёте (экзамене). Одной из «инженерообразующих» дисциплин является дискретная математика [1-3]. Важной задачей дискретной математики является задача синтеза автоматов [4-6]. Рассмотрим особенности предлагаемого подхода на примере синтеза синхронного автомата-распознавателя [7-9] кода (кодового замка-распознавателя PIN-кода) в рамках дисциплины «Схемотехника» [10, 11]. Блоки шаблона автомата-распознавателя кода. Рассмотрим пример синтеза синхронного автомата, распознающего последовательность на входах ав: «0022» (PIN код). На правильную последовательность срабатывает индикатор z1, что может быть интерпретировано как команда «замок открыть». Для всех неверных наборов срабатывает z2, что означает «подать сигнал тревоги» или «замок заблокировать». Мы не будем подсчитывать, сколько раз формируются неверные последовательности. Не будем учитывать внешний сигнал общего сброса - его будем осуществлять по штатным входам сброса триггеров. В отличие от входных сигналов, реализуемых статическими ключами с двумя положениями «0» и «1», необходимы динамические ключи, поэтому нужны блок формирования кода ключа (клавиши) и формирователь сигнала активирования одного из ключей (клавиш). Проведём блочный синтез шаблона автомата-распознавателя кода (рис. 1). Рис. 1. Блочный синтез шаблона автомата-распознавателя кода При нажатии кнопки блок формирования кода ключа - кодопреобразователь x/y формирует код аb и активирует одновибратор, синхронизирующий синхронный дискретный автомат ДА. Переход осуществляется при нажатии очередной кнопки: кнопку нажали - срабатывает одновибратор и формирует один синхроимпульс. Реализацию кодопреобразователя выполним в системе схемотехнического моделирования NI Multisim 10 фирмы National Instruments Electronics Workbench Group [12] на микросхеме кодера (кодопреобразователя) 74148 (рис. 2). Рис. 2. Реализация кодопреобразователя Поскольку этот кодопреобразователь имеет выходы фиксации активации одного из входов Е0 и GS (см. рис. 2), то необходимость в одновибраторе отпадает - будем использовать GS для синхронизации триггеров памяти автомата. Абстрактный синтез автомата-распознавателя с повторяющимися символами. Приступим к этапу абстрактного синтеза автомата. Построим граф переходов для синхронного автомата Мили (рис. 3). Рис. 3. Граф переходов автомата 0022 На рис. 3 стрелками обозначены переходы из одного состояния в другое. Дробные значения над стрелками: в числителе условия переходов в последующее состояние, в знаменателе - получаемое выходное значение. Цветом обозначены конечные состояния автомата, зеленый - для разрешенной последовательности 0022, красный, соответственно, - для запрещенных. Используя рис. 3, строим таблицу переходов автомата (рис. 4). Рис. 4. Таблица переходов автомата Мура 0022 В состоянии 5 формируется сигнал z1- открытие «замка», а в состоянии 6 - z2 - «тревога» («подбор кода»). Построим таблицу переходов-выходов автомата Мура (рис. 5). Рис. 5. Таблица переходов-выходов автомата Мура 0022 На рис. 5: y3y2y1(t) - текущее состояние автомата, y3y2y1(t+1) - следующее состояние, z1z2 - выходные значения. Структурный синтез автомата-распознавателя с повторяющимися символами. Реализацию логических функций выполним на основе дешифраторов 74 154. Память построим на синхронных триггерах D-типа. Шаблон для схемы управления памятью показан на рис. 6. Рис. 6. Реализация логических функций y3(t+1)y2(t+1)y1(t+1) Построим подсхему реализации z1 z2 для соответствующего автомата Мура: в состоянии 4 (100) активируется z1, в состоянии 5 (101) - активируется z2. Исходное состояние показано на рис. 7. Рис. 7. Реализация логических функций z1 z2 Методика тестирования автомата-распознавателя с повторяющимися символами. Проверяем реакцию автомата на правильную последовательность 0022 по таблице, показанной на рис. 5. Проводим общий сброс - состояние автомата 000. Нажимаем 0, автомат переходит в состояние 001 (рис. 8). Рис. 8. Реакция автомата на нажатие клавши «0» - переход в состояние 001 Ещё раз нажимаем 0, автомат переходит в состояние 010 (рис. 9). Рис. 9. Реакция автомата на повторное нажатие клавши «0» - переход в состояние 010 Далее два раза нажимаем 2 - автомат переходит в состояние 4 (100) и формируется сигнал z1 (рис. 10). Рис. 10. Правильная последовательность - переход в состояние 100 При нарушении последовательности, например 0023, автомат переходит в состояние 5(101) и формируется сигнал z2 (рис. 11). Рис. 11. Реакция автомата на последовательность 0023 - переход в состояние 101, формирование сигнала z2 Выводы. Таким образом, синтез автомата-распознавателя с повторяющимися символами может быть осуществлён без минимизации логических функций в системе Electronics Workbench по заданному шаблону (он может быть в библиотеке схем) на базе кодера и дешифраторов. Кодер 74148 позволяет формировать код одной из восьми нажатой клавиши и сигнал активации клавиш, который может быть использован для синхронизации триггеров [13]. В рамках 4-часовой лабораторной работы по дисциплине «Схемотехника» целесообразна реализация автомата, реагирующего на последовательности нажатий 4 клавиш. Более сложный автомат с 8 клавишами может быть вынесен на курсовую работу студентов. Реализация синхронного автомата-распознавателя позволяет сформировать существенно большее число вариантов, чем для автомата с неповторяющимися символами. Предлагаемая методика может обеспечить масштабирование заданий и времени их выполнения (контроля), что в условиях дефицита времени вносит существенный вклад в дело повышения качества подготовки отечественных специалистов в области электронной компонентной базы, в том числе разрабатываемой на кафедре «Автоматика и телемеханика» [14, 15], а также в кооперации с ИПИ РАН [16, 17].Об авторах
С. Ф Тюрин
Пермский национальный исследовательский политехнический университет
Ю. А Аляев
Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации
Список литературы
- Коршунов Ю.М. Математические основы кибернетики: учеб. пособие для вузов. - М.: Энергия, 1972. - 376 с.
- Коршунов Ю.М. Математические основы кибернетики: учеб. пособие для вузов. - 3-е изд., перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.
- Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М: Энергоатомиздат, 1988. - 450 с.
- Новиков Ф.А. Дискретная математика для программиста. - СПб.: Питер, 2001. - 502 с.
- Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: учеб. пособие для вузов. - М.: Наука, 2000. - 540 с.
- Дискретные устройства автоматизированных систем управления / под ред. Г.Н. Тимонькина, В.С. Харченко / МО СССР. - М., 1990. - 486 с.
- Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. - М.: Финансы и статистика, 2006. - 368 с.
- Тюрин С.Ф., Аляев Ю.А. Дискретная математика: практическая дискретная математика и математическая логика. - М.: Финансы и статистика, 2010. - 394 с.
- Тюрин С.Ф., Аляев Ю.А. Дискретная математика: тест-драйв по дискретной математике и математической логике. - Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2014. - 231 с.
- Тюрин С.Ф., Громов О.А., Греков А.В. Реализация цифровых автоматов в системе Quartus фирмы Altera: лаб. практикум. - Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2011. - 133 с.
- Угрюмов Е.П. Цифровая схемотехника: учеб. пособие. - 2-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2007. - 782 с.
- Сайт разработчика National Instruments [Электронный ресурс]. - URL: http://www.ni.com/multisim/ (дата обращения: 08.06.2017).
- Quartus II. Download Center [Электронный ресурс]. - URL: https://www.altera.com/downloads/download-center.html (дата обращения: 11.05.17).
- Посягин А.И., Южаков А.А. Разработка двухслойной нейронной сети для самомаршрутизирующегося аналого-цифрового преобразователя на основе нейронной сети // Электротехника. - 2013. - № 11. - С. 10-13.
- Хижняков Ю.Н., Южаков А.А. Нейронечеткий регулятор частоты газотурбинного двигателя // Приборы. - 2010. - № 5. - С. 17-21.
- Самосинхронный вычислитель для высоконадежных применений / Ю.А. Степченков [и др.] // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС): сб. тр. всерос. науч.-техн. конф. / Ин-т проблем проектир. в микроэлектронике РАН. - М., 2010. - № 1.
- Библиотека самосинхронных элементов для технологии БМК / Ю.А. Степченков [и др.] // Проблемы разработки перспективных микроэлектронных систем - 2006: сб. науч. тр. / под общ. ред. А.Л. Стемпковского. - М.: Изд-во ИППМ РАН, 2006. - С. 259-264.
Статистика
Просмотры
Аннотация - 42
PDF (Russian) - 16
Ссылки
- Ссылки не определены.