Antik (Антик М.И. - Синхронные цифровые автоматы)

М.И. АНТИКСИНХРОННЫЕЦИФРОВЫЕ АВТОМАТЫМосква 2006ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТРАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)»М.И. АНТИКСИНХРОННЫЕЦИФРОВЫЕ АВТОМАТЫМосква 2006Автор:М.И. АнтикРедактор: А.М. РомановВ пособии исследуется логический этап проектированияцифровых синхронных схем.

При этом предполагается, что читатель знаком с основами логического проектирования комбинационных схем.Печатается по решению редакционно-издательского советаГосударственного образовательного учреждения высшего профессионального образования «московский государственный институт радиотехники, электроники и автоматики (техническийуниверситет)»Рецензенты: д.т.н. А.В. Гноевойк.т.н. А.В.

Киселёв© Государственное образовательное учреждение высшего профессионального образования «Московский государственный институт радиотехники, электроники иавтоматики (технический университет)», 2004Государственное образовательное учреждение высшего профессионального образования«Московский государственный институт радиотехники, электроники и автоматики (технический университет)»119454, Москва, просп. Вернадского, 783СОДЕРЖАНИЕВВЕДЕНИЕ ....................................................................................................... 5ГЛАВА I. ОСНОВНЫЕ МЕТОДЫ АНАЛИЗА И СИНТЕЗА .........................

61.Основные понятия................................................................. 61.1.1.2.1.3.Каноническая структура синхронного цифрового автомата .............. 6Абстрактный конечный автомат ........................................................... 6Соглашения… ........................................................................................ 82.Основные структурные составляющие ............................ 92.1.2.2.Комбинационная схема .........................................................................

9Память автомата.................................................................................. 103.Основные типы синхронных автоматов ......................... 103.1.3.2.3.3.3.4.СЦА полностью и частично определенные ....................................... 11Инициальные автоматы ...................................................................... 11Автомат Мура .......................................................................................

11Автомат Мили....................................................................................... 124.Способы описания автоматов .......................................... 124.1.4.2.4.3.4.4.Автоматная таблица ............................................................................ 13Автоматный граф (граф переходов) ..................................................

15Блок-схема............................................................................................ 16Блок-текст ............................................................................................. 175.Автономные автоматы ..................................................... 185.1.5.2.Параллельная композиция .................................................................

18Последовательная композиция .......................................................... 196.Эквивалентные автоматы ................................................ 196.1.6.2.6.3.Изоморфные и эквивалентные автоматы........................................ 19Минимальные автоматы...................................................................... 20Эквивалентность автоматов Мура автоматам Мили ........................ 237.Автоматы распознавания языков ..................................... 257.1. Регулярные языки ................................................................................ 267.2. Асинхронный язык................................................................................

317.3. Детерминизация источника................................................................. 34ГЛАВА II. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРОЕКТИРОВАНИЯ .................... 381.2.Декомпозиция автоматов .................................................. 38Автоматы на регистрах сдвига ....................................... 422.1.2.2.2.3.Автоматы без обратной связи ............................................................ 43Автоматы с бинарной функцией обратной связи..............................

47Независимость от состояний .............................................................. 523.4.Автоматы без потери информации................................. 52Условная синхронизация СЦА............................................. 54ГЛАВА III. ЛИНЕЙНЫЕ АВТОМАТЫ .......................................................... 551.Основные определения........................................................ 5542.3.4.5.6.7.8.Линейные автоматы без потери информации ...............

57Формула полной реакции ЛА............................................... 57Изоморфные и эквивалентные линейные автоматы .... 58Минимальные линейные автоматы.................................. 60Минимально-канонические и простые канонические формы........................................................................................... 62Независимость от состояний...........................................

62Автономные линейные автоматы (АЛА)......................... 638.1.8.2.Анализ АЛА........................................................................................... 64Синтез АЛА........................................................................................... 659.Линейные автоматы с нулевым начальным состоянием669.1.9.2.9.3.9.4.9.5.9.6.9.7.D–преобразование............................................................................... 67Передаточная функция .......................................................................

69Связь структуры ЛА и его передаточной функции............................ 70Канонические структуры...................................................................... 72Эквивалентные преобразования ........................................................ 73Вычисление выходных значений........................................................ 74Аннулирующие и аннигилирующие последовательности ................ 7510. Умножение и деление линейными автоматами .............. 7810.1.

Умножение............................................................................................ 7810.2. Деление ................................................................................................ 7911. Обобщения............................................................................

8111.1. Многоканальный аналог двухполюсного ЛА...................................... 8111.2. Линейные автоматы над конечным полем ........................................ 8211.3. Линейные автоматы над полем Галуа ............................................... 83ГЛАВА IV. УПРАВЛЯЮЩИЕ АВТОМАТЫ ................................................. 841.2.Варианты взаимодействия ОА и УА.............................. 86Основные способы адресации микрокоманд ........................ 882.1.2.2.2.3.2.4.2.5.2.6.Схема с адресным ПЗУ .......................................................................

90Схема с явным указанием альтернативных адресов ....................... 92Схема с частичной записью адреса ................................................... 93Схема с сокращенным тактом ............................................................ 94Схема с регулярной адресацией ........................................................ 96Схема с естественной адресацией и совмещенным назначениемразрядов ячейки ПЗУ...........................................................................

982.7. Функциональный переход и переход на микроподпрограмму с возвратом................................................................................................. 1002.7.1. Функциональный переход ................................................................. 1002.7.2. Переход к микроподпрограмме с возвратом ................................... 1013.Управление с предвосхищением ......................................

102БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................... 1035ВВЕДЕНИЕСинхронный цифровой автомат (СЦА) объединяет комбинационную схему и элементы памяти в единую структуру с относительно простой процедурой взаимодействия. В то же время,принципы такого взаимодействия являются базовыми для построения практически всей современной цифровой аппаратуры.Разработчик цифровой аппаратуры не может считаться достаточно грамотным, если он не владеет математическими методамианализа и синтеза синхронных автоматов. Применение таких методов гарантирует правильность и оптимальность решений посравнению с интуитивными методами, основанными на некотором, опыте, аналогиях и т.п.

Даже если решение получено на интуитивном уровне, то оно должно быть проверено, уточнено ипереработано на основе точных методов. Теория дает также ответна вопрос “что сделать нельзя?”, оставаясь в рамках структурсинхронных цифровых автоматов.Процесс проектирования цифрового устройства включаетэтапы логический и схемотехнический. В пособии исследуетсялогический этап проектирования. При этом предполагается, чточитатель знаком с основами логического проектирования комбинационных схем. Схемотехническое проектирование (реализацияв реально существующем элементном базисе, электрические параметры, нагрузки, помехи, быстродействие,...) в пособии не рассматривается.Математический аппарат используется в той мере, в которойон необходим в инженерной практике анализа и синтеза синхронных автоматов.6ГЛАВА I. ОСНОВНЫЕ МЕТОДЫ АНАЛИЗА И СИНТЕЗА1.Основные понятия1.1.Каноническая структура синхронного цифрового автоматаПредметом изучения являются устройства, структура которых может быть представлена в виде конструкции из модулейдвух типов - комбинационной схемы (КС), на рисунках обозначение – CL (combinational logic), и регистра – RG (register) с динамической синхронизацией (рис.1).asyns'CLC RGsQDbs'hРис.1.