WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     || 2 | 3 | 4 | 5 |   ...   | 23 |
Н. Г. Захаров, В. Н. Рогов СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ Ульяновск 2003 1 Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет Н. Г. Захаров, В. Н. Рогов СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ Учебное пособие Ульяновск 2003 2 УДК 519. 713 (075) ББК 32. 972 я 7 З-38 Утверждено редакционно-издательским советом университета в качестве учебного пособия.

Рецензенты: кафедра математической кибернетики и информации Ульяновского государственного университета, заведующий кафедрой доктор технических наук, профессор И. В. Семушин;

директор Ульяновского филиала института радиотехники и электроники Академии Наук Российской Федерации А. А. Широков.

Захаров Н. Г., Рогов В. Н.

З-38 Синтез цифровых автоматов: Учебное пособие / Н. Г. Захаров, В. Н. Рогов. – Ульяновск: УлГТУ, 2003.

ISBN 5-89146-300-0 Изложены основные понятия формальных грамматик, приведены синтез абстрактного и структурного конечных цифровых автоматов. Рассмотрены работы машин Тьюринга и сетей Петри. Предназначена для студентов специальности 200700 «Радиотехника», 220100 «Вычислительные машины, комплексы и системы связи», 200900 «Сити связи и системы коммутации».

УДК 519.713(075) ББК 32.927 я 7 © Н. Г. Захаров, В. Н. Рогов, 2003 ISBN 5-89146-300-0 © Оформление. УлГТУ, 2003 3 ОГЛАВЛЕНИЕ Введение.......................................................................…….................................….... 5 1. Основы теории формальных грамматик....................................................…... 6 1.1. Основные понятия теории автоматов................................................ …............ 6 1.2. Основные понятия теории формальных грамматик..........................……........ 8 1.3. Классификация языков по Хомскому...................................................……....... 1.4. Распознающие устройства и автоматы.................................................……....... 1.4.1. Концепция порождения и распознавания...........................................……... 1.4.2. Распознающие, порождающие и преобразующие формальные грамматики.. 1.5. Автоматы и формальные языки.....................................................……............. 1.5.1. Понятие об информации и ее преобразованиях............................................ 1.5.2. Преобразование алфавитной информации....................................……......... 1.5.3. Способы задания автоматов..............................................................……...... Контрольные вопросы...................................................................................……….. 2. Машины Тьюринга...............................................................……......................... 2.1. Основные понятия.........................................................................……............... 2.2. Машины Тьюринга с двумя выходами..........................................……............. 2.3. Машины Тьюринга и линейно-ограниченные автоматы.................................. 2.4. Автоматы с магазинной памятью и бесконтекстные языки..............….......... 2.4.1. Автоматы с магазинной памятью........................................…….................... 2.4.2. Бесконтекстные (контекстно-свободные) языки.......................................... Контрольные вопросы..............................................................……........................... 3. Абстрактный конечный автомат.....................................................……........... 3.1. Абстрактная теория автоматов......................................................…….............. 3.1.1. Модель дискретного преобразователя Глушкова В.М................................. 3.1.2. Понятие об абстрактном автомате и индуцируемом им отображении....... 3.2. Представление событий в автоматах........................................……................... 3.2.1. Автоматные отображения и события........................................…….............. 3.2.2. Представление событий в автоматах...........................................……........... 3.2.3. Регулярные языки и конечные автоматы....................................…......……. 3.3. Алгоритм синтеза конечных автоматов.............................……........................ 3.3.1. Основной алгоритм синтеза конечных автоматов.................……............... 3.3.2. Усовершенствованный основной алгоритм синтеза конечных автоматов.. 3.4. Автоматы Мили и Мура.......................................................……........................ 3.4.1. Автомат Мили..................................……......................................................... 3.4.2. Автомат Мура....................................................................……....................... 3.4.3. Получение неполностью определенных (частичных) автоматов................

3.5. Синтез автоматов по индуцируемым ими отображениям................................ 3.5.1. Общий метод решения задачи..................................................……............... 3.5.2. Синтез автомата Мили................................................................……............. 3.5.3. Синтез автомата Мура………………………………………………………... Контрольные вопросы……………………………………………………………….. 4. Структурный конечный автомат........................................................................ 4.1. Основные понятия структурной теории автоматов..................…..................... 4.2. Композиция автоматов и структурные схемы.........................…...................... 4.3. Условия корректности и правильности построения схем........……................ 4.4. Канонический метод структурного синтеза автомата..................……............ 4.4.1. Основная задача теории структурного синтеза автоматов............…........... 4.4.2. Теорема о структурной полноте................................................…….............. 4.4.3. Комбинационная часть автомата. Синтез схемы автомата............….......... 4.5. Кодирование состояний. Гонки в автомате................................……................ 4.6. Построение комбинационной схемы автомата ……………………….………. Контрольные вопросы............................………………………………….................. 5. Микропрограммирование.................................................... ……........................ 5.1. Принципы микропрограммного управления..............................……............... 5.2. Система команд автоматов, реализующих выполнение алгоритма.…........... 5.3. Набор операций автомата...............................................................……............. 5.4. Состав и назначение элементов блок-схемы...............................…….............. 5.5. Общий алгоритм функционирования ………………………………...……….. 5.6. Основные характеристики автоматов.........................................……................ 5.7. Устройство управления микропрограммным автоматом.............. ….............. 5.8. Формирование адреса микрокоманд............................................……............... Контрольные вопросы………………………………………….……………………. 6. Проблемы отображения времени при проектировании..........…................... 6.1. Модель тактируемого дискретного автомата......................……...................... 6.2. Выбор параметров тактирующих сигналов................................……............... 6.3. Сравнение способов тактирования автоматов...........................……................ 6.4. Абсолютная и относительная шкала времени.............................……............. 6.5. Характеристики сигналов в абсолютной шкале времени..............……........... 6.6. Характеристики сигналов в относительной шкале времени...……................. Контрольные вопросы……………………………………………….………………. 7. Сети Петри.......................................................................................…..............….. 7.1. Назначение и общая характеристика сетей Петри............................................ 7.2. Структура и способы представления сетей Петри................................……… 7.2.1. Структура сетей Петри..................................................................................... 7.2.2. Графы сетей Петри........................................................................................... 7.2.3. Маркировка сетей Петри........................................…….................................. 7.2.4. Работа сетей Петри.....................................................……............................... 7.3. Анализ сетей Петри..…….................................................................................... 7.3.1. Безопасность сети Петри…............................................................................... 7.3.2. Анализ живучести (сохранения) сетей Петри …............................................ 7.3.3. Активность сети Петри.......................................……..................................... 7.3.4. Достижимость и покрываемость.............................……................................ 7.4. Моделирование алгоритмов с помощью сетей Петри......…............................ 7.5. Расширенные сети Петри....................................................……......................... 7.6. Сети Петри и регулярные языки.............................................…….................... 7.7. Преобразование конечного автомата в сеть Петри......................….…............ 7.8. Разработка модели сложения двух чисел с плавающей запятой..........…....... Контрольные вопросы……………………………………………………………….. Заключение…………………………………………………………………………... Приложение………………………………………………………………………….. Предметный указатель………………………………………………………………..

Библиографический список…………………………………………...…………… Введение Учебное пособие «Синтез цифровых автоматов» предназначено для более углубленного изучения студентами специальности 200700 «Радиотехника» дисциплины «Цифровые устройства и микропроцессоры».

В результате изучения дисциплины студент должен изучить: цифровые автоматы, представляемые как математические модели дискретных систем; связь автоматов с формальными языками и грамматиками; способы задания и принципы построения цифровых автоматов, а также методы и средства их разработки.

Создание современных автоматизированных средств и систем управления основывается на следующих двух научных направлениях: теории преобразования информации и теории построения различного рода преобразователей информации.

Первое направление включает в себя общую теорию алгоритмов, абстрактную теорию автоматов. В нем рассматриваются общие вопросы формализации процессов обработки информации.

Второе направление включает в себя элементы математической логики, структурную теорию автоматов. В нем рассматриваются принципы и методы построения автоматов, которые реализуют алгоритмы обработки информации, полученные на этапе абстрактного синтеза автоматов.

В соответствии с этими направлениями в теории автоматов выделяют два больших раздела: абстрактную теорию автоматов и структурную теорию автоматов.

В первом разделе пособия даны основные понятия теории формальных грамматик, классификация языков, понятие об информации и её преобразованиях.

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

В третьем разделе дано понятие об абстрактном аппарате и индуцируемом им отображении. Рассмотрено представление событий в автоматах, приведены модели автоматов Мили и Мура.

В четвертом разделе даны основные понятия структурной теории автоматов, рассмотрены вопросы композиции автоматов и построения структурных схем. Приведен канонический метод структурного синтеза автоматов, рассмотрены задачи кодирования состояний и способы устранения состязаний элементов памяти при изменении состояний автоматов. Дано построение комбинационной схемы автомата.

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

Шестой раздел посвящен проблемам отображения времени при проектировании дискретных автоматов. Рассмотрена модель тактируемого автомата, выбор и сравнение способов тактирования автомата. Дана характеристика сигналов в абсолютной и относительной шкале времени.

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

1. ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ГРАММАТИК 1.1. Основные понятия теории автоматов Термин «автомат», как правило, используется в двух аспектах. С одной стороны, автомат - это устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q1(t), q2(t),..., qn(t)}, в которые он под действием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.

Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов – конечные множества.

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

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

Устройства, служащие для преобразования дискретной информации, называются дискретными автоматами.

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 23 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.