Основные понятия и определения

Лекция 1 Основные понятия и определения В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления, т.е. информация представлена в виде комбинации нулей и единиц. Поэтому работу любой схемы ЭВМ можно рассматривать как функциональный преобразователь с большим числом входов и выходов. При этом поступление на входы некоторой последовательности входных сигналов, состоящих из нулей и единиц, вызывает появление на выходах вполне определенной последовательности выходных сигналов, также состоящей из нулей и единиц. Все схемы ЭВМ можно разделить на два больших класса: 1. Класс логических или комбинационных схем (КС). 2. Класс конечных автоматов (КА). В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1≤t. Выходные сигналы в схемах второго класса определяются не только значениями входных сигналов в данный момент времени, но и состоянием схемы, которое, в свою очередь, зависит от значения сигналов, поданных на её входы в предшествующие моменты времени. Эти схемы обязательно содержат в своем составе элементы памяти, в качестве которых используется триггера различных типов. Технические вопросы синтеза комбинационных схем решаются с помощью аппарата математической логики. При этом используется самая простая часть математической логики, а именно, алгебра логики или булева алгебра. Основным понятием в алгебре логики, на котором основывается её приложение к синтезу КС, является понятие булевой или переключательной функции (ПФ). Переключательной или булевой функцией называется функция f(x1, x2, …, xn), способная принимать как и ее аргументы x1, … , xn только два значения 0 или 1. Таким образом, аргументы и функции от них могут быть либо истинными, либо ложными. Ввиду того, что аргументы ПФ могут принимать только два значения, область определения любой ПФ конечна. Поэтому любая ПФ может быть задана таблицей ее значений в зависимости от значений ее аргументов. Эту таблицу называют таблицей истинности ПФ. Пример 1.1. Зададим ПФ трех аргументов f(x1, x2, x3). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), …, (111). Для получения следующего набора прибавляют 1 к правому разряду – применяется как бы сложение чисел. Наборам присваивается номер, равный двоичному числу, соответствующему данному набору. Сопоставляя каждому набору одно из двух значений ПФ, мы и получим таблицу истинности (например, представленную в табл. 1.1). Таблица 1.1 x1 x2 x3 f 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Свойства переключательных функций 1. Любая ПФ n аргументов определена на 2 n наборов. 2. Число различных ПФ n аргументов конечно и равно 2²n. При n = 1, число различных ПФ равно 4, при n = 2 – 16, при n = 3 – 256, при n = 4 – 65536, при n = 5 – примерно 4,3´109. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно лишь для небольшого числа аргументов. Мы будем использовать аппарат алгебры логики для синтеза схем ЭВМ. Это использование основано на следующем: будем отождествлять значение ПФ с выходными сигналами КС, а ее аргументы – с входными сигналами. Тогда ПФ будет описывать процесс преобразования КС входных сигналов в выходные и аппарат Булевой алгебры можно применять при синтезе таких схем. Под синтезом КС будем понимать определение таких способов соединения нескольких простейших схем, называемых логическими элементами, при которых построенные схемы реализуют заданный алгоритм преобразования сигналов при заданном критерии качества. В качестве критерия оценки качества технической реализации заданного алгоритма обычно используют критерий сложности или быстродействия схем. Возьмем какую-либо комбинационную схему (рис.1.1): Рис.1.1. Комбинационная схема Схема имеет n входов и m выходов и следовательно реализуют m ПФ от n аргументов: y1=f1(x1,x2,...xn); y2=f2(x1,x2,...xn); . . . . . . . . . ym=fm(x1,x2,...xn); Любая сколь угодно сложная КС строится из более простых схем, называемых логическими элементами. Логическим элементом называется электронная схема, реализующая элементарную ПФ, имеющая количество входов, равное числу аргументов ПФ и только один выход. В ЭВМ в основном используются логические элементы с одним или двумя входами, реализующие ПФ одного или двух аргументов. Поэтому задача синтеза КС заключается в том, чтобы из логических элементов построить любую сколь угодно сложную схему, реализующую заданный набор ПФ. Математически в алгебре логики этой задачи соответствует задача представления любой сложной ПФ через элементарные ПФ. При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов I и II показано на рис.1.2. f3(x1, x2, x3) Рис.1.2. Последовательное соединение логических элементов Последовательное соединение двух логических элементов позволяет получить функцию f3 трех аргументов. Подстановка в функцию вместо ее аргументов других функций называется суперпозицией. Перестановка входов логических элементов показана на рис.1.3. f4(x1, x2, x3) Рис.1.3. Перестановка входов логических элементов В общем случае функция f4(x1, x2, x3) отличается от функции f3(x1, x2, x3). В математическом плане мы заменили одни аргументы ПФ другими. Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов. В алгебре логики доказывается, что из ПФ одного и двух аргументов с помощью операций суперпозиции и подстановки можно получить все ПФ от большого числа аргументов. Практически это означает, что из логических элементов с одним и двумя входами можно построить любую сколь угодно сложную комбинационную схему. Переключательные функции одного и двух переменных В табл. 1.2 представлены все 4 функции одного аргумента. Таблица 1.2 x f0(x) f1(x) f2(x) f3(x) 1 1 1 1 1 Функция f0(x) равно 0 (константа нуля), f3(x) равна 1 (константа единицы), функция f1(x) повторяет значение аргумента, т.е. f1(x) = x. Наиболее интересной является функция f2(x), которая принимает значения, обратные значению аргумента – логическое отрицание или функция НЕ: =ù х (читается не х). Черта, стоящая над аргументом, имеет смысл определенного функционального преобразования и называется знаком отрицания. Логический элемент НЕ (инвертор) в схемах изображается следующим образом (рис.1.4). Рис.1.4. Обозначение логического элемента НЕ Все ПФ двух аргументов приведены в табл.1.3. Таблица 1.3 x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Функции f0(x1, x2) и f15(x1, x2) не зависят от значений аргументов: f0(x1, x2)=0 и f15(x1, x2) = 1. Функции f3(x1, x2), f5(x1, x2), f10(x1, x2) и f12(x1, x2) являются фактически функциями одного аргумента: f3(x1, x2) = x1, f5(x1, x2) = x2, f10(x1, x2) = и f12(x1, x2) = . Рассмотрим оставшиеся десять ПФ от двух аргументов. Функция f1(x1, x2) реализует операцию конъюнкции или логического произведения. Как видим из табл.1.3 , функция f1(x1, x2) равна 1, когда и x1 и x2 равны 1. Конъюнкция (рис. 1.5) обозначается следующим образом: f1(x1, x2) = x1 & x2= x1 Ù x2 = x1 x2 (читается x1 и x2). Рис.1.5. Обозначение логического элемента И Конъюнкция легко обобщается на случай n аргументов, когда реализуется функция вида . Функция конъюнкция n аргументов равна 1 тогда, когда все аргументы равны 1. Функция f7(x1, x2) реализует операцию дизъюнкцию или логического сложения. Функция равна 1, когда или x1 или x2 равны 1. Дизъюнкция (рис. 1.6) обозначается как f7(x1, x2) = x1 Ú x2. Рис.1.6. Обозначение логического элемента ИЛИ Дизъюнкция также обобщается на случай n аргументов, когда реализуется функция вида . Функция дизъюнкция n аргументов равна 1 тогда, когда хотя бы один аргумент равен 1. Функция f14(x1, x2) реализует операцию отрицания конъюнкции. Из табл.1.3 видно, что когда конъюнкция f1(x1, x2) равна 0, то функция f14(x1, x2) равна 1, а если f1(x1, x2) равна 1, то f14(x1, x2) равна 0, т.е. f14(x1, x2) = . Эта операция получила название “штрих Шеффера” и обозначается различными способами. Логический элемент, реализующий эту функцию, называется И-НЕ (рис. 1.7). Рис.1.7. Обозначение элемента И-НЕ Функция f8(x1, x2) реализует операцию отрицания дизъюнкции. По аналогии с функцией отрицания конъюнкции, из табл.1.3 видно, что f8(x1, x2)= . Эта операция также получила отдельное название – “стрелка Пирса” и обозначается следующим образом: . Логический элемент, реализующий эту функцию, называется ИЛИ-НЕ (рис. 1.8): Рис.1.8. Обозначение элемента ИЛИ-НЕ Функция f6(x1, x2) реализует операцию логической неравнозначности. ПФ равна 1, если аргументы x1 и x2 не равны между собой: Эту функцию называют еще суммой по модулю два. Второе название этой функции объясняется тем, что ее таблица истинности совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю 2, т.е. 0 + 0 = 0, 1+ 0 = 1, 0 + 1 = 1, 1 + 1 = 0. Обобщим эту функцию на случай n аргументов: она принимает единичное значение тогда, когда число аргументов, равных 1, нечетно, и равна нулю, если число аргументов четно. Функция равна 1 тогда, когда оба аргумента равны между собой. Это функция носит название логической равнозначности. Поскольку значения функции . . . . . инверсны значению функции . . . . . , то для функции используют и другое обозначение: . Функции и называются импликациями. Функция f11 читается как если х2, то x1, а функция f13 – если x1, то х2. Функция f11 принимает нулевое значение только тогда, когда х2 = 1, а x1 = 0, а функция f13 равна 0, если x1 = 1, а х2 = 0. Функции и – функции запрета по аргументам х2 и x1 соответственно. Для реализации сколь угодно сложной ПФ не обязательно использовать все 16 ПФ двух аргументов. Можно ограничиться некоторым набором, с помощью которого можно строить любые ПФ. Система ПФ, из которых с помощью операций суперпозиции и подстановки можно получить любую сколь угодно сложную ПФ, называется функционально полной системой (ФПС) ПФ или базисом. Существует несколько ФПС ПФ: - дизъюнкция, конъюнкция и отрицание (булев базис); - отрицание конъюнкции (универсальный базис); - отрицание дизъюнкции (универсальный базис); - логическая неравнозначность, конъюнкция и константа 1 (базис Жегалкина) и другие. Возникает вопрос: какие ПФ представляют наибольший практический интерес? Оказывается, что наиболее удобный для решения задач синтеза схем ЭВМ является ФПС ПФ, содержащая операции конъюнкция, дизъюнкция и отрицание, т.е. булев базис. Этот набор ПФ обладает замечательным свойством: можно построить любую КС так, что она будет содержать наименьшее количество элементов, в крайнем случае, равное. Поэтому эта система называется основной функционально полной системой ПФ. Логические элементы характеризуются коэффициентами объединения и разветвления. 1. Коэффициент объединения J. Из-за взаимных наводок в цепях передачи сигналов возникают помехи, которые суммируются при объединении нескольких цепей на одном элементе. Поэтому для исключения возможности появления недопустимо больших помех налагаются ограничения на предельное число входных сигналов в одном элементе. Это число входов и называется коэффициентом объединения J. Если требуемое число входов элементов больше значения J, то производится так называемое разделение входов с помощью дополнительных элементов. Покажем процедуру разделения входов на примерах. Пример 1.1. Пусть необходимо реализовать в булевом базисе функцию от четырёх аргументов при J = 2. Используя скобочную форму записи, получим: . Схема показана на рис. 1.9: Рис.1.9. Схема, реализующая функцию Пример 1.2. Пусть необходимо реализовать функцию в базисе И-НЕ при J =2. Преобразуем функцию f следующим образом: . Схема показана на рис. 1.10: Рис.1.10. Схема, реализующая функцию Разделение входов всегда сопровождается уменьшением быстродействия т.к. увеличивается суммарная задержка сигналов. 2. Коэффициент разветвления обозначается F. Всякий реальный элемент обладает конечной нагрузочной способностью, не позволяющей подсоединить выход одного элемента к неограниченному числу входов других элементов. Нарушение нагрузочной способности приводит к искажению сигналов в схеме. Нагрузочная способность элемента характеризуется коэффициентом разветвления F, т.е. наибольшим количеством входов других элементов, которые можно подсоединить к выходу данного элемента. Если число входов элементов, подключаемых к выходу данного элемента, больше F, то принимаются меры к разгрузке данного элемента. Разгрузка может выполняться двумя способами: дублированием выходного сигнала и дублированием элемента. Покажем, как производится разгрузка элементов на примерах. Пример 1.3. Пусть F = 4 и к выходу некоторого элемента необходимо подключить 7 входов других элементов. Тогда для дублирования сигнала можно использовать два инвертора (рис. 1.11): Рис.1.11. Дублирование выходного сигнала Недостатком этого метода является увеличение задержки сигнала в схеме. От этого недостатка свободен способ разгрузки за счет дублирования элемента (рис. 1.12): Рис.1.12. Дублирование элемента Лекция 2 Общая задача структурного синтеза комбинационных схем Будем рассматривать синтез КС, реализующей одну ПФ. Процесс синтеза КС на элементах заданного базиса разбивается на следующие этапы: 1) Аналитическая запись ПФ в булевом базисе: в совершенной дизъюнктивной нормальной форме (СДНФ) или в совершенной дизъюнктивной нормальной форме (СКНФ). 2) Минимизация ПФ в булевом базисе. 3) Представление полученного после минимизации выражения в заданном базисе (переход к заданному базису). 4) Аналитическая запись ПФ в булевом базисе (запись в виде СДНФ или в СКНФ).  Минимизация ПФ в булевом базисе Совершенные ДНФ и КНФ используются лишь для первоначального представления ПФ. Дело в том, что эти формы записи в ПФ не удобны для построения КС, поскольку при их реализации получаются схемы, содержащие элементы, которые можно исключить, если исходить из других форм ПФ. Поэтому при синтезе КС встает задача упрощения записи выражения для ПФ. Эта задача называется минимизацией ПФ. В процессе минимизации СДНФ получается последовательно в начале сокращенная ДНФ, далее тупиковая и минимальная. Существуют различные методы минимизации ПФ, из которых чаще всего используются методы Квайна, Мак-Класки, Блейка-Порецкого, диаграмм Вейча и карт Карно. В принципе все эти методы являются разновидностями метода Квайна. Метод минимизации Блейка-Порецкого Недостатком метода Квайна является то, что для его применения необходимо представить функцию в СДНФ. Процесс такого представления для функции с большим числом аргументов зачастую является весьма громоздкой задачей, т.е. было бы желательно найти возможность построения сокращенной ДНФ не по СДНФ, а по произвольной ДНФ данной функции. Идея построения сокращенной ДНФ по произвольной ДНФ была предложена в работах А. Блейка и П.С. Порецкого. Суть метода состоит в том, что в произвольной ДНФ осуществляют все операции обобщенного склеивания. Если в ДНФ для данной функции f(А, В, С) входят две конъюнкции вида АС и B, то имеет место следующее равенство: Запишем функцию f (А, В, С) в следующем виде: Из этого вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что если в ПФ есть конъюнкции с переменными С и , то не изменяя исходную функцию необходимо пополнить ее новыми членами вида АВ. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока не будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ. Пример 2.3. Найти сокращенную ДНФ для функции 3-х аргументов: Метод минимизации Мак-Класки В методе Квайна есть одно существенное неудобство. Оно связано с необходимостью полного попарного сравнения всех членов СДНФ ПФ на этапе нахождения всех простых импликант (при выполнении всевозможных операций неполного склеивания). При большом числе переменных применение метода Квайна становится затруднительным. Мак-Класки предложил модернизацию метода Квайна, дающую уменьшение числа сравнений. Идея метода Мак-Класки заключается в следующем: конституенты 1 в СДНФ представляются не в буквенном виде, а виде условных чисел – номеров соответствующих конституент. Пример 2.4. = = 0000 0001 0010 0111 1001 1010 1110 1111 = = 0 1 2 7 9 10 14 15 = (0, 1, 2, 7, 9, 10, 14, 15). При этом оказывается, что переменные имеют вес: ABCD 8421. Давайте посмотрим, какие конституенты 1 склеиваются. Мы говорили, что могут склеиваться те, у которых число отрицаний отличается на 1. = 0000 0001 = 0 1= ; 0 1 = (0, 1), (1), т.е. склеиваются конституенты 0 и 1, а в скобках указывается разность, какая переменная исключается (D). Еще пример: 0100 0110 = 4 6 = (4, 6), (2) – склеиваются по C. Вводится понятие индекса. Индексом целого числа называется количество 1 в двоичном представлении этого числа: 7 = 0111 – индекс равен 3, 0000 – индекс равен 0 и т.д. Если конституенты 1 склеиваются, то их индексы отличаются на 1, а в скобках должно быть число (их разности), равное целой степени 2 (по какой переменной склеиваются). Правило. Для того чтобы два числа m и n являлись номерами двух склеивающихся между собой конституент 1, необходимо и достаточно, чтобы их индексы отличались точно на 1, чтобы сами числа отличались друг от друга на степень 2, и чтобы число с большим индексом было больше числа с меньшим индексом. Так конституенты 1 с номерами 4 и 3, равными 0100 и 0011, не склеиваются, хотя их разности равны 1. Все конституенты 1 разбиваются на группы в соответствии с индексом и располагаются в порядке их возрастания. Группы отделяются друг от друга чертой. Склеиваться могут конституенты только соседних групп. Пример 2.5. (0, 1, 3, 4, 5, 6, 10, 11, 12, 14, 15). Минимизировать методом Мак-Класки. Прежде всего группируем номера конституент в порядке роста их индексов. В нулевую группу попадает номер 0. В 1 группу – конституенты с индексом 1 (1 и 4), во 2 группу – конституенты с индексом 2 (3 = 0011, 5 = 0101, 6 = 0110, 10 = 1010 и 12 = 1100), в 3 группу – конституенты с индексом 3 (11 = 1011 и 14 = 1110), в 4 группу – конституенты с индексом 4 (15 = 1111). В результате имеем следующее разбиение конституент функции на группы: 1 1 4 2 3 5 6 10 12 3 11 14 4 15 В силу рассмотренного правила, склеивание возможно между номерами конституент соседних групп, т.е. 0 и 1, 1 и 2, 2 и 3 и 3 и 4. Никакие другие склеивания невозможны. Необходимо также, чтобы число, стоящее в следующей группе, было больше соответствующего числа в предыдущей группе, причем больше на целую степень 2. Например, 0 склеивается с 1, записывается пара (0,1) и рядом их разность: 1 – 0 = 1. Запись выглядит так: (0, 1), (1). Около склеенных номеров ставятся звездочки, показывающие, что эти члены участвовали хотя бы в одном склеивании. Такие члены, как известно, в сокращенную ДНФ уже не войдут. После завершения склеивания групп отделяем горизонтальной чертой полученные выражения. Дальше осуществляется та же процедура, но теперь склеиваются между собой полученные пары. Под парой подразумевается трехбуквенное выражение. (0,1), (1) *   (0,1,4,5), (1,4) (с) (0,4), (4) *   (0,1,4,5), (4,1) (1,3), (2) (а)   (4,6,12,14), (2,8) (d) (1,5), (4) *   (4,6,12,14), (8,2) (4,5), (1) *   (10,11,14,15) (1,4) (e) (4,6) , (2) *   (10,11,14,15) (4,1) (4,12), (8) *       (3,11), (8) (в)       (6,14), (8) *       (10,11), (1) *       (10,14), (4) *       (12,14), (2) *       (11,15), (4) *       (14,15), (1) *       Для склеивания пар применяются те же правила, но добавляется еще одно условие: разности у склеиваемых пар должны быть одинаковы. При этом оказывается, что в парах переменные в выражении одинаковы. Возьмем, например, пары (0, 1),(1) и (1, 3), (2). 0 и 1 склеиваются, 1 и 3 тоже, но разности у них не одинаковы – поэтому склеивание невозможно (у первой пары нет переменной D, у второй пары нет переменной С – они, конечно, и не могут склеиваться). В результате склеивания пишем уже четверки (0, 1, 4, 5) и две разности (1, 4), т.е. в результирующем выражении нет 2-х переменных B и D. После завершения этих склеиваний получают, если возможно, восьмерки, при этом должны совпадать уже разности в скобках у четверок и т.д. Обозначим пары и четверки, которые не участвовали в склеивании, латинскими буквами. Тогда . При получении выражения для импликант а, в, с и т.д., поступают следующим образом: берут любую из конституент 1, участвующих в операции склеивания, и исключают переменные, указанные в разностях. Например, для импликанты а получим: 0001= (разность 2). Эта разность говорит о том, из выражения необходимо исключить переменную с весом 2, т.е. С. Тогда а =. Аналогично получим: для в : 0011= (разность 8), в = , для с: 0001= (разности 1 и 4), с = , для d : 0100 = (разности 2 и 8), d = , для e: 1111=AВCD (разности 1 и 4), e = АС. В результате получим: . Метод диаграмм Вейча или карт Карно Методы Квайна и Блейка-Порецкого являются аналитическими. В этих методах наиболее трудоемким является процесс отыскания склеивающихся между собой конъюнкций. Существуют методы, которые позволяют упростить поиск склеивающихся членов. Один из наиболее удобных методов минимизации ПФ от небольшого числа переменных основан на использовании диаграмм Вейча или карт Карно. Диаграмма Вейча представляет собой фактически таблицу истинности ПФ, которая представляется не в виде столбцов, а в виде специальных карт. Каждой клетке диаграммы соответствует определенный набор значений аргументов. Поэтому диаграммы можно рассматривать как графическое представление совокупности всех конституент единицы. При этом диаграмма строится таким образом, что склеивающиеся между собой конституенты оказываются расположенными в соседних клетках, т.к. отличаются значением только одной переменной. Приведем примеры построения диаграммы Вейча и карт Карно для ПФ от разного числа аргументов. Переключательные функции трех аргументов Пример 2.7. . Диаграмма Вейча состоит из 8 клеток и имеет следующий вид: Тогда .  В этой карте соседними клетками являются также крайние клетки каждой строки, т.к. расположенные в них конституенты отличаются друг от друга значением только одной переменной. Такую диаграмму следует рассматривать как свернутую в цилиндр. Минимизация ПФ с помощью диаграмм Вейча и карт Карно сводится к такому объединению соседних единиц в группы, при котором каждая группа содержит максимальное число единиц, а количество таких групп минимально. При этом все единицы диаграммы Вейча данной функции накрываются наименьшим числом наиболее коротких произведений (импликант). Переключательные функции четырех аргументов В диаграммах Вейча и картах Карно для четырех аргументов соседними клетками являются крайние клетки каждого столбца и строки. Поэтому такую диаграмму следует рассматривать как свернутую в тор. Пример 2.8. (0, 1, 4, 5, 9, 10, 11, 13, 14, 15). Диаграмма Вейча состоит из 16 клеток и имеет следующий вид: Построим схему в булевом базисе (рис. 2.1): Рис. 2.1 Построим схему, реализующую функции в базисе И-НЕ (штрих Шеффера). Для этого осуществим переход от булевого базиса к базису И-НЕ: Схема, реализующая функцию в базисе И-НЕ, приведена на рис. 2.2. Рис. 2.2 Построим схему, реализующую функции в базисе ИЛИ-НЕ (стрелка Пирса). Для этого осуществим переход от булевого базиса к базису ИЛИ-НЕ: Схема, реализующая функцию в базисе ИЛИ-НЕ, приведена на рис. 2.3. Рис. 2.3 Лекция 3 Преобразование функции в минимальную конъюнктивную нормальную форму (КНФ) Для того, чтобы получить выражение заданной ПФ в форме, содержащей минимальное количество букв, следует, кроме минимальной ДНФ, получить также минимальную КНФ, и выбрать ту из них, которая содержит меньшее число букв. Существуют различные методы минимизации КНФ. Рассмотрим один из таких методов, основанный на минимизации функции и в переходе с помощью формулы де Моргана к функции f. При минимизации можно использовать все методы, которые применялись ранее при нахождении минимальной ДНФ. После получения минимальной ДНФ функции с помощью формул де Моргана переходят к минимальной КНФ функции f. Пример 3.1. Найти минимальную КНФ функции . Диаграмма Вейча имеет вид: Из диаграммы получим: . Тогда:– минимальная КНФ. Минимизация не полностью определенных переключательных функций В ЭВМ иногда применяются КС, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называются запрещенными. Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е. функциями, значения которых определены не на всех наборах аргументов. Поэтому минимизация не полностью определенных ПФ с помощью карт Карно сводится к такому доопределению ПФ, при котором получаются группы с максимальным числом соседних единиц в каждой группе, а число таких групп минимально. При этом ПФ будет содержать минимум букв. Пример 3.2. Найти минимальную ДНФ и минимальную КНФ не полностью определенной ПФ: ,. На остальных наборах функция не определена. –– минимальная ДНФ, ; – минимальная КНФ. Минимизация систем переключательных функций Работа КС, имеющей n входов и m выходов, описывается системой m переключательных функций, каждая из которых определяет закон функционирования схемы по одному выходу (рис. 3.1). Если провести минимизацию ПФ, входящих в систему независимо друг от друга, то получится схема, содержащая m изолированных цепей, в общем случае не минимальная. Однако эту схему можно существенно упростить за счет объединения участков схемы, реализующих одинаковые члены. Рис.3.1. Комбинационная схема Общая идея минимизации схем со многими выходами сводится к получению выражений для системы ПФ, в которых наилучшим образом используются конъюнкции, общие для нескольких функций. Покажем, как производится минимизация системы ПФ. Пример 3.3. Пусть дана система из трех ПФ от 4-х аргументов:   Схема, реализующая систему ПФ, приведена на рис. 3.2. Рис. 3.2 Лекция 4 Основные понятия и определения В вычислительной технике используются схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью КС является наличие функциональной зависимости между входными и выходным сигналами: y(t) = f(x(t)). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии КС схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения. Автомат – это дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать различные выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом. Понятие состояния введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходные сигналы которых зависят не только от состояния входов в данный момент времени, но и от некоторых предысторий, то есть от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени. Кодирование информации Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д. Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой. Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 4.1): X(x1, …, xF) ---> A(a0, ..., aM) ---> Y(y1, …, yG). Рис. 4.1. Абстрактный автомат Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T≠const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, … , имеющими смысл номера такта. Для задания любого КА S необходимо задавать совокупность из пяти объектов : S{A, X, Y, d, l}, где A = {a0, a1, a2, ..., am, ..., aM} – множество состояний автомата, X = {x1, x2, …, xf ,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], l – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Если множества А, Х и У конечны, то автомат называется конечным. Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными. Условия преобразования информации в детерминированных автоматах 1. Любое входное слово длиною l букв преобразуется в выходное слово той же длины. 2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l1 букв, в выходных словах первые l1 букв также совпадут. Кроме детерминированных автоматов существуют вероятностные автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое. Нами будут рассмотрены, в основном, детерминированные автоматы. Применяемые на практике автоматы принято разделять на два класса – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Законы функционирования автоматов описываются следующими системами уравнений: Автомат Мили:   Автомат Мура: a(t + 1) = d [a(t), x(t)],   a(t + 1) = d [a(t), x(t)], y(t) = l[a(t), x(t)]..   y(t) = l[a(t)]. Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала. Способы задания автоматов Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l}, т.е. необходимо описать входной и выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a0, a1, ... aM} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический. Табличный способ При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов: Таблица переходов Таблица выходов xj/ a1 a0 … aM x1 d(a0, x1) … d(aM, x1) … … … … xF d(a0, xF) … d(aM, xF) xj/ a1 a0 … aM x1 l(a0, x1) … l(aM, x1) … … … … xF l(a0, xF) … l(aM, xF) Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai, xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj, а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[ai, xj]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов: xj/ a1 a0 … aM x1 d(a0, x1) / l(a0, x1) … d(aM, x1) / l(aM, x1) … … … … xF d(a0, xF) / l(a0, xF) … d(aM, xF) / l(aM, xF) Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура: yg l(a0) … l(aM) xj/ a1 a0 … aM x1 d(a0, x1) … d(aM, x1) … … … … xF d(a0, xF) … d(aM, xF) В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Рассмотрим примеры табличного задания автоматов Мили и Мура: Автомат Мура: Автомат Мили: yg y2 y1 y1 y3 y2 xj/ ai a0 a1 a2 a3 a4 x1 a2 a1 a3 a4 a2 x2 a3 a4 a4 a0 a1 xj/ ai a0 a1 a2 a3 x1 a1 / y1 a2 / y3 a3 / y2 a0 / y1 x2 a0/y2 a0 / y1 a3 / y1 a2 / y3 Для автомата Мура: x1 x2 x2 x2 x1 … a0 a2 a4 a1a4 y2 y1 y2 y1y2 Для автомата Мили: x1 x2 x2 x2 x1 … a0 a1 a0 a0 a0 a1 y1 y2 y2 y1 По этим таблицам можно найти реакцию автомата на любое входное слово. Графический способ При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, то есть as = d(ai, xj). В автомате Мили (рис. 4.2) дуга отмечается входным сигналом xj, под действием которого происходит этот переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние автомата. В автомате Мура (рис. 4.3) в вершинах графа кроме состояния автомата отмечается соответствующий выходной сигнал, а дуга отмечается только входным сигналом xj, под действием которого происходит этот переход.   Рис. 4.2. Граф для автомата Мили   Рис. 4.3. Граф для автомата Мура Частичные автоматы В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат – частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai , xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще. Пример таблицы переходов и выходов частичного автомата Мили: xj/ ai a0 a1 a2 a3 x1 a1 / y1 a2 / y2 a3 / y3 a2 / y1 x2 - / - - / - a0 / y4 a0 / y2 Лекция 5 Элементарные автоматы Структурным синтезом занимается структурная теория автоматов. Основная цель этой теории – нахождение общих приемов построения сложных структурных схем автоматов из более простых автоматов, называемых элементарными автоматами. На практике в большинстве случаев применяют элементарные автоматы с двумя внутренними состояниями. В процессе синтеза элементарные автоматы соединяют между собой с помощью логических элементов. Первая задача, решаемая при структурном синтезе, заключается в выборе системы элементов, из которых должны строиться заданные автоматы. Для того чтобы можно было построить схему любого конечного автомата, эта система элементов должна быть структурно полной. Теорема о структурной полноте формулируется следующим образом: - Для того чтобы система элементов была структурно полной, необходимо и достаточно, чтобы она содержала какую-либо функционально полную систему логических элементов и хотя бы один элементарный автомат с двумя устойчивыми состояниями, обладающий полной системой переходов и выходов. Полнота переходов в автомате означает, что для любой пары состояний ai и aj существует хотя бы один входной сигнал, который переводит автомат из состояния ai в состояние aj, причем i = j и , т.е. в каждом столбце таблицы переходов должны встречаться все состояния. Полнота выходов автомата означает, что в каждом состоянии автомат выдает выходной сигнал, отличный от сигналов, выдаваемых в других состояниях. Требование полноты системы выходов связано с необходимостью различать внутренние состояния элементарных автоматов, так как в автомате, не обладающем полной системой выходов, различить состояния невозможно и, следовательно, невозможно обеспечить заданные условия функционирования схемы, построенной на его основе. Если элементарный автомат не имеет полной системы переходов, то это значит, что отсутствует переход хотя бы одного вида. Поэтому построить на основе такого элементарного автомата схему, в которой бы осуществлялись все возможные переходы из одного состояния в другое, нельзя. Таким образом, для построения любого конечного автомата необходимо иметь элементарные автоматы, обладающие полной системой, как переходов, так и выходов. Рассмотрим конкретные типы элементарных автоматов, имеющих полную систему переходов и выходов и нашедших применение в вычислительной технике. В настоящее время в вычислительной технике, как правило, используются элементарные автоматы, имеющие следующие особенности: 1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями. 2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1. 3. Элементарные автоматы могут иметь в общем случае несколько физических входов. В качестве элементарных автоматов в вычислительной технике используются триггеры различных типов (рис. 5.1). Рассмотрим некоторые из них. Рис. 5.1 Т-триггер Т-триггером называют автомат Мура с двумя устойчивыми состояниями и одним входом Т, который изменяет свое состояние на противоположное всякий раз, когда на вход Т поступает единичный сигнал. Таблица переходов Т-триггера: yg 1 xj /ai 1 T = 0 1 T = 1 1 Из таблицы переходов видно, что Т-триггер обладает полной системой переходов и выходов, поскольку для каждой пары состояний (0-0, 0-1, 1-0,1-1) имеется входной сигнал, обеспечивающий переход из одного состояния в другое. Кроме того, каждое состояние автомата отмечено отличным от других выходным сигналом. На практике более удобно вместо отмеченных таблиц переходов пользоваться так называемыми матрицами переходов элементарных автоматов. Матрица переходов T Q(t) Q(t+1) 1 1 1 1 1 1 Она определяет значения сигналов на входах элементарного автомата, обеспечивающих каждый их четырех возможных переходов. Здесь Q(t) и Q(t + 1) – состояния автомата в моменты времени t и t + 1 соответственно. Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки. Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча: T\Q(t) 1 1 1 1 Из диаграммы имеем: . Поскольку эта формула совпадает с аналитической записью ПФ логической неравнозначности (сложение по модулю два), то Т-триггер часто называют триггером со счетным входом, а входной сигнал, поступающий на вход Т, счетным сигналом. На практике кроме асинхронного Т-триггера, работу которого мы рассмотрели, используют так же и синхронный Т-триггер, который меняет свои состояния только при Т = 1 и С = 1. Если хотя бы один из этих сигналов равен нулю, то триггер сохраняет свое состояние. Вход С называют входом синхронизации. Поясняющая работу комбинационная схема и обозначение синхронного Т-триггера представлены на рис. 5.2: Рис.5.2. D-триггер D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что Q(t + 1) = D(t). Название D-триггера происходит от английского слова “delay” – задержка. Из определения следует, что состояние триггера в момент времени t + 1 повторяет значение входного сигнала D(t) в момент времени t (отсюда и название триггера задержки). Матрица переходов D-триггера: D Q(t) Q(t + 1) 1 1 1 1 1 1 Рис. 5.3 Обозначение синхронного D-триггера В синхронном D-триггере при С = 0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть . Граф D-триггера (рис. 5.4): Рис. 5.4 RS-триггер RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S. При S = 1 триггер устанавливается в состояние 1, а при R = 1 – в состояние 0. Одновременная подача двух сигналов, равных 1, запрещена, т.е. R S = 0. В соответствии с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R – нулевым. Матрица переходов RS-триггера: R S Q(t) Q(t+1) b1 1 1 1 1 b2 1 1 Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R = 0, S = 0 и R = 1, S = 0. Поэтому в первой строке матрицы переходов в столбце R поставлен неопределенный коэффициент b1 = 0 v 1. Аналогично переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R = 0, S = 0 и R = 0, S = 1. Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записан коэффициент b2. По матрице переходов можно построить граф RS-триггера. Автоматы, которые могут переходить из одного состояния в другое под действием нескольких комбинаций входных сигналов, называются автоматами с избыточной системой переходов. Избыточность можно использовать в процессе синтеза для упрощения схемы, придавая коэффициентам b1 и b2 такие значения, которые позволяют минимизировать число элементов. Поэтому, если схемы двух элементарных автоматов равноценны по сложности, то предпочтение отдают автомату, имеющему большую избыточность системы переходов. Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча: SQ(t) R 00 01 11 10 1 1 1 1 - - Запрещенные комбинации входных сигналов при минимизации заполним единичными значениями. Тогда имеем: JK-триггер JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K. При JK = 1 триггер меняет свое состояние на противоположное. В остальных случаях он функционирует в соответствии с таблицей истинности RS-триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Таблица истинности JK-триггера: J K Q(t) Q(t+1) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Построим диаграмму Вейча и матрицу переходов: KQ(t) J 00 01 11 10 1 1 1 1 1 J K Q(t) Q(t+1) b1 1 b2 1 b3 1 1 b4 1 1 Тогда: . В интегральной схемотехнике применяются только синхронные JK-триггера, которые при C = 0 сохраняют свое состояние, а при C = 1 работают как асинхронные JK-триггера. JK-триггер относится к разряду универсальных триггеров, поскольку на его основе можно построить RS-, D- и T-триггера. RS-триггер получается наложением ограничения на комбинацию входных сигналов J = K = 1, так как эта комбинация является запрещенной для RS-триггера. Т-триггер получается путем объединения входов J и K (рис. 5.5). Т-триггер получается путем объединения входов J и K (рис. 5.5). D-триггер строится путем подключения к входу K инвертора, на который подается тот же сигнал, что и на вход J. В этом случае вход J выполняет функцию входа D (рис. 5.6). Рис. 5.5 Рис. 5.6 Лекция 6 Структурная схема конечного автомата В структурной теории автомат представляют в виде композиции двух частей: запоминающей части, состоящей из элементов памяти, и комбинационной части, состоящей из логических элементов: Комбинационная схема строится на логических элементах, образующих функционально полную систему, а память – на элементарных автоматах, обладающих полной системой переходов и выходов. Каждое состояние абстрактного автомата ai , где i = {0, М}, кодируется в структурных автоматах набором состояний элементов памяти Qr, r = {1, R}. Поскольку в качестве элементов памяти используются триггера, то каждое состояние можно закодировать двоичным числом . Здесь ai = {0, 1}, a Q – состояние автомата. Отсюда: Общее число необходимых элементов памяти можно определить из следующего неравенства: , где (М + 1) – число состояний автомата. В отличие от абстрактного автомата, имеющего один входной и один выходной каналы, на которые поступают сигналы во входном X = {x1, x2,..., xf,…, xF} и выходном Y = {y1, y2,..., yg, ..., yG} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата: , . Здесь и – значения двоичных входных и выходных сигналов соответственно. Число каналов L и N можно определить аналогично формуле для определения R: Изменение состояния элементов памяти происходит под действием сигналов U = (U1 , U2 , ..., UR), поступающих на их входы. Эти сигналы формируются комбинационной схемой КС1 и называются сигналами возбуждения элементарных автоматов. На вход КС1, кроме входных сигналов, по цепи обратной связи поступают сигналы Q = (Q1 , Q2 , ..., Qr,..., QR) с выходов элементов памяти автомата. Комбинационная схема КС2 служит для формирования выходных сигналов Y = {y1, y2,..., yg, ..., yG}, причем в случае автомата Мили на вход этой схемы поступают входные сигналы, а в случае автомата Мура – входные сигналы не поступают. Табличный метод структурного синтеза конечных автоматов Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении функции возбуждения каждого элементарного автомата и функций кодированных выходов заданного автомата. На этапе структурного синтеза выбираем способ кодирования состояний, входных и выходных сигналов автомата, в результате чего составляют кодированные таблицы переходов и выходов. Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов. Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов. Пример 6.1. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов: xj /ai a0 a1 a2 x1 a1/y1 a1/y2 a1/y2 x2 a2/y3 a2/y3 a0/y1 В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. A = {a0, a1, a2}; X = {x1, x2}; Y = {y1, y2, y3}. Здесь M + 1 = 3; F = 2, G = 3. 1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов: = 2, = 1, =2. Таким образом необходимо иметь два элементарных автомата Q1 и Q2, один входной канал a и два выходных канала z1 и z2 (каналы a и z называют еще физическими входами и выходами автомата соответственно). 2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов. Таблицa кодирования состояний автомата aj Q1 Q2 a0 a1 1 a2 1 Таблицa кодирования входных сигналов xf O1 x1 x2 1 Таблицa кодирования выходных сигналов yg z1 z2 y1 y2 1 y3 1 Поскольку автомат имеет 3 состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата. xj /ai 00 01 10 01/00 01/01 01/01 1 10/10 10/10 00/00 3. Построим кодированные таблицы переходов и выходов. Эти таблицы определяют зависимости состояний элементарных автоматов и выходных сигналов в момент времени (t + 1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t, т.е.: Кодированная таблица переходов и выходов имеет следующий вид: t t + 1 a O1 Q2 z1 z2 O1 Q2 1 1 1 1 1 1 1 1 1 - - - - 1 1 1 1 1 1 1 1 1 1 1 1 - - - - 4. Основная задача, решаемая в процессе структурного синтеза – построение таблицы функций возбуждения элементарных автоматов, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построении этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK-триггера. С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках этой таблицы записываются значения J и K, обеспечивающие нужный переход. Ниже представлена таблица функций возбуждения. Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени. t t + 1 a O1 Q2 J1 K1 J2 K2 O1 Q2 b 1 b 1 1 b b 1 1 b 1 1 b 1 1 1 - - - - - - 1 1 b b 1 1 1 1 b b 1 1 1 1 b 1 b 1 1 1 - - - - - - Поскольку функции возбуждения J(t) и K(t) определенны в тот же момент времени, что и их аргументы O1(t), Q2(t) и a(t), то эти функции являются переключательными. В результате мы получим систему переключательных функций z1(t), z2(t), J1(t), K1(t), J2(t) и K2(t), заданных в виде таблиц их истинности. 5. Следующий этап – синтез комбинационной части конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, а переход к заданному базису осуществляют после. В нашем случае мы имеем 6 переключательных функций трёх аргументов, для каждой из которых построим диаграмму Вейча. , , , , , . Обычно полученную систему ПФ минимизируют совместно. Однако совместная минимизация всех ПФ представляет собой достаточно трудоемкую и длительную операцию, применимую, в общем случае, при использовании машины. В результате минимизации мы получим следующую схему конечного автомата: Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе ЭВМ. Например, в схеме регистра сдвига информации добавляется цепь «установка в 0». Другие изменения связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов. Лекция 7 Технические особенности конечных автоматов В схемах ЭВМ все сигналы изменяются и воспринимаются, как правило, в дискретные моменты времени, обозначаемые числами натурального ряда t = 0, 1,…. Для отметки моментов дискретного времени ЭВМ содержит специальный блок, вырабатывающий синхронизирующие импульсы (СИ), следующие через равные интервалы времени Т. Этот интервал времени Т определяет такт работы устройства. Поэтому первая техническая особенность связана с необходимостью синхронизации работы конечного автомата, причем синхронизации подлежат не только выходные сигналы, но и функции возбуждения. В связи с этим в автомат обычно вводят две серии синхроимпульсов СИ1 и СИ2, сдвинутых на половину периода друг против друга (рис. 7.1). Рис. 7.1 Под действием СИ1 формируются выходные сигналы, а под действием СИ2 автомат переводится в новое состояние. В результате структурная схема автомата имеет следующий вид: Рис. 7.2 Согласно приведенной схеме на входах каждого из триггеров стоят двухвходовые элементы И. На практике триггера часто выполняются в синхронном варианте (синхронные триггера), когда упомянутые элементы И включают в схему триггера. Например, схему синхронного RS-триггера можно рассматривать как состоящую из асинхронного RS-триггера, ко входам R и S которого подключены двухвходовые элементы И. На эти элементы кроме входных сигналов поступает синхронизирующий сигнал, обозначаемый буквой C: Очевидно, синхронные триггера будут сохранять свои состояния при С = 0, а переходы в них возможны при С = 1. Применение синхронных триггеров в качестве элементов памяти конечного автомата облегчает организацию синхронизации таких автоматов. Вторая техническая особенность конечного автомата связана с возможностью возникновения неустойчивых состояний и так называемых «гонок» в автомате. Понятие устойчивости заключается в следующем. Пусть в графе автомата мы имеем такой участок (рис. 7.4): Рис. 7.4 Здесь оба перехода выполняются под действием одного и того же входного сигнала xо. Если длительность сигнала СИ2 больше времени перехода автомата из состояния ai в состояние as, то сразу после перехода автомата в as может начаться переход в следующее состояние af под действием того же входного сигнала xj. Таким образом, автомат может перескочить состояние as и к моменту времени t + 1 оказаться не в as, как это требуется по графу, а в af. Состояние as в данном случае будет неустойчивым. Другой неприятный момент заключается в том, что при работе автомата могут возникать так называемые «гонки» (состязания). Дело в том, что триггера в схеме имеют различные времена срабатывания, а также различные времена задержек сигналов обратной связи, которые поступают с выходов триггеров на их входы через КС1. По этим причинам, если при переходе автомата из состояния ai в as должны измениться состояния нескольких триггеров, то между их выходными сигналами начинаются гонки. Тот триггер, который выиграет гонку, то есть изменит свое состояние раньше других триггеров, может через цепь обратной связи изменить сигналы возбуждения на входах других триггеров до того момента, как они изменят свои состояния. Это, очевидно, может вызвать переход автомата совсем не в то состояние, которое нужно по графу. Пусть, например, ai = 101, as = 010. Тогда при переходе из ai в as под действием входного сигнала xj меняются состояния всех триггеров. Допустим, что первый триггер изменил свое состояние раньше других. В этом случае автомат окажется в некотором промежуточном состоянии ah = 001, и если из этого состояния есть переход под действием сигнала xj в состояние, например, al = 011, то автомат в момент времени t + 1 может оказаться в al , а не в состоянии as, т.е. совсем в другом состоянии. Для устранения описанного эффекта гонок и неустойчивых состояний часто используют дублирование памяти в автомате. Структурная схема автомата выглядит при этом следующим образом (рис. 7.5). Рис. 7.5 Здесь под действием синхронизирующего сигнала СИ1 формируются выходные сигналы zl(t) … zN(t) и переключаются в новое состояние триггера первого ряда. Под действием СИ2 состояния триггеров первого ряда переписываются в соответствующие триггера второго ряда. Поскольку СИ2 сдвинуты относительно СИ1 на половину периода, а сигнал обратной связи о состоянии автомата снимается с триггеров второго ряда, то в момент поступления входного сигнала, то есть в СИ1, состояние автомата не изменяется и продолжает оставаться прежним до прихода СИ2. Поэтому в такой схеме полностью обеспечивается устойчивость состояний и устраняется влияние гонок. Действительно, гонки сигналов с выходов триггеров второго ряда возможны в момент СИ2, то есть в момент переключения этих триггеров. Но в момент СИ2 = 1, СИ1 = 0 и следовательно эти гонки никак не могут повлиять на состояния триггеров первого ряда, которые переключаются в момент СИ1 = 1. Также не будет и неустойчивых состояний, поскольку автомат не может проскочить за один такт через одно состояние и перейти в следующее, ибо в момент перехода триггеров первого ряда в новое состояние, то есть в СИ1, состояние триггеров второго ряда не меняется (СИ2 = 0) и, следовательно, не могут измениться и сигналы возбуждения триггеров первого ряда, которые зависят от состояния триггеров второго ряда. Поэтому автомат не может проскочить состояние. С целью упрощения построения схем автоматов, имеющих двойную память, выпускаются специальные двухступенчатые триггера. Рассмотрим работу такого триггера на примере двухступенчатого JK-триггера (рис. 7.6). Двухступенчатый триггер Рис. 7.6 Особенностью двухступенчатого триггера является то, что он меняет свое состояние в момент окончания синхронизирующего сигнала С. В результате этого во время действия сигнала С выходные сигналы триггера не меняются, а происходит запись информации в триггер Т1. В момент С = 0 состояние триггера Т1 переписывается в триггер Т2. Эквивалентные автоматы Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными. Для любого автомата Мили существует эквивалентный ему автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура. Пусть дан конечный автомат Мили Sa = {Aa, Xa, Ya, da, la}, имеющий множество состояний Aa = {a0, a1,…, an,…,aM}, множество входных и выходных сигналов Xa = {x1, x2,…, xf,…, xF} и Y = {y1, y2, …, yg, …, yG}, а также функции переходов da(a, x) и выходов la(a, x). Требуется построить эквивалентный ему автомат Мура Sb = {Ab, Xb, Yb, db, lb}, у которого Xb = Xa, Yb = Ya, так как множества входных и выходных сигналов у эквивалентных автоматов должны совпадать. Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида (am, yg), где yg – выходной сигнал, приписанный к дуге, входящей в состояние am. Например, для вершины am имеем пары (am, y1), (am, y2), (am, y3) рис.7.7. y1 y2 y3 Рис. 7.7 Если такие пары мы образуем для всех вершин, то получим множество пар, которое является множеством состояний автомата Мура: Ab = {(a0, y1), (a0, y2), …, (aM, yG)} = {b1, b2, …, bM}, где bl = (ai, yg). Функции выходов lb и переходов db определим следующим образом. Каждому состоянию автомата Мура, представляющему собой пару вида (ai, yg) поставим в соответствие выходной сигнал yg, то есть функция выходов равна yg = lb[(ai, yg)] = lb[bl]. Если в автомате Мили Sa был переход da(ai, xj) = as и при этом выдавался выходной сигнал la(ai, xj) = yp, то в эквивалентном автомате Мура будет переход из множества состояний (ai, yg), где g принадлежит G, G – множество номеров выходных сигналов, приписанных к входящей ai дуге, в состояние (as, yp) под действием входного сигнала xj.   Рис. 7.8. Автомат Мили (фрагмент)   Рис. 7.9. Автомат Мура, эквивалентный автомату Мили Автомат Мили рис.7.8 имеет 2 состояния, а автомат Мура рис.7.9 – 3: (ai, yf), (ai, yh), (ai, yp). Если автомат Мили был в состоянии ai и пришел входной сигнал xj, то должен выработаться выходной сигнал yp. Поэтому в автомате Мура из состояний, порождаемых ai, то есть из состояний (ai, yf) и (ai, yh) при поступлении xj переход должен идти в состояние, отмеченное выходным сигна; лом yp, то есть в (as, yp). В качестве начального состояния автомата Мура можно взять любое состояние из множества (a0, yr). Преобразование автомата Мили в автомат Мура Рассмотрим пример 7.1. Пусть необходимо преобразовать автомат Мили в автомат Мура.Граф автомата Мили имеет следующий вид: Рис. 7.10 В автомате Мили Xa = {x1, x2}, Ya = {y1, y2}, Aa = {a0, a1, a2}. В эквивалентном автомате Мура Xb = Xa = {x1, x2}, Yb = Ya = {y1, y2}. Построим множество состояний Ab автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата Sa. Состояние Порождаемые пары a0 {(a0, y1), (a0, y2)} = {b1, b2} a1 {(a1, y1)} = {b3} a2 {(a2, y1), (a2, y2)} = {b4, b5} Отсюда имеем множества Ab состояний автомата Мура Ab = {b1, b2, b3, b4, b5}. Для нахождения функции выходов lb с каждым состоянием, представляющим собой пару вида (ai, yg), отождествим выходной сигнал, являющийся вторым элементом этой пары. В результате имеем: lb(b1) = lb(b3) = lb(b4) = y1; lb(b2) = lb(b5) = y2. Построим функцию переходов db. Так как в автомате Sa из состояния a0 есть переход под действием сигнала x1 в состояние a2 с выдачей y1,то из множества состояний {b1, b2}, порождаемых a0, в автомате Sb должен быть переход в состояние (a2, y1) = b4 под действием сигнала x1. Аналогично, из {b1, b2} под действием x2 должен быть переход в (a0, y1) = b1. Из (a1, y1) = b3 под действием x1 переход в (a0, y1) = b1, а под действием x2 – в (a2, y2) = b5. Наконец из состояний {(a2, y1), (a2, y2)} = {b4, b5} под действием x1 в (a0, y2) = b2, а под действием x2 – в (a1, y1) = b3. В результате имеем граф (рис. 7.11) и таблицу переходов эквивалентного автомата Мура. Рис. 7.11. Граф эквивалентного автомата Мура В качестве начального состояния автомата Sb можно взять любое из состояний b1 или b2, так как оба порождены состоянием a0 автомата Sa. Переход от автомата Мура к автомату Мили Переход от автомата Мура к автомату Мили решается чрезвычайно просто. Пусть дан автомат Мура Sb ={Ab, Xb, Yb, db, lb}. Необходимо построить эквивалентный ему автомат Мили Sa = {Aa, Xa, Ya, da, la}. По определению эквивалентности имеем Xa = Xb; Ya = Yb. Кроме того, Aa = Ab, da= db. Остается только построить функцию выходов. Если в автомате Мура db(ai, xj) = as, а lb(as) = yg, то в автомате Мили la(ai, xj) = yg. Другими словами: l(ai, xj) = lb(db(ai, xj)). Таким образом, таблица переходов автоматов Мили и Мура совпадают. А таблица выходов эквивалентного автомата Мили строится так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке. Пример 7.2. Пусть дан автомат Мура: xj\yi y1 y1 y3 y2 y3 xj\ai a0 a1 a2 a3 a4 x1 a1 a4 a4 a2 a2 x2 a3 a1 a1 a0 a0 Тогда эквивалентный ему автомат Мили имеет следующую совмещенную таблицу переходов и выходов: xj\ai a0 a1 a2 a3 a4 x1 a1\ y1 a4\ y3 a4\ y3 a2\ y3 a2\ y3 x2 a3\ y2 a1\ y1 a1\ y1 a0\ y1 a0\ y1 Лекция 8 Регистры К типовым узлам ЭВМ, предназначенным для хранения и преобразования двоичной информации, относятся различные виды регистров, счетчиков, сумматоров и дешифраторов. Регистром называется устройство, предназначенное для приема, хранения и передачи информации. Информация в регистре хранится в виде двоичного числа, причем каждому разряду числа, записанного в регистр, соответствует свой разряд регистра. Регистры используются также для выполнения некоторых операций над числами, такими как сдвиг числа влево или вправо на заданное число разрядов, образование обратного кода числа, преобразование последовательного кода в параллельный и обратно и т.д. В зависимости от способа ввода и вывода информации различают регистры параллельного, последовательного и параллельно-последовательного действия. Регистры параллельного действия В регистрах параллельного действия запись числа осуществляется параллельным кодом, т.е. во все разделы регистра одновременно. Регистр строится на триггерах, число которых равно числу разрядов в хранимом слове, т.е. каждый триггер предназначен для запоминания одного разряда числа. В качестве триггеров в таких регистрах используется, как правило, RS- и D-триггера. В зависимости от количества каналов, по которым поступает информация на входы регистра, различают регистры парафазного и однофазного вида. Парафазные регистры характеризуются тем, что информация на каждый разряд поступает по двум каналам (прямому и инверсному), а в однофазных регистрах – по одному каналу (прямому или инверсному). Приведем схему парафазного регистра на синхронных RS-триггерах с асинхронными и установочными входами R и S (рис. 8.1). Пусть в n-разрядный регистр необходимо записать n-разрядное двоичное число X = xn-1xn-2…x1x0. Прямой и обратный коды каждого разряда числа поступают одновременно на входы S и R триггера. Запись числа осуществляется по синхронизирующему сигналу С. Если необходимо прочитать прямой код числа, хранящегося в регистре, необходимо в схему подать сигнал Чтпр (чтение прямое). Тогда на выходах конъюнкторов первой группы появится число в прямом коде, поскольку входы этих конъюнкторов соединены с прямыми выходами триггеров. Аналогично, при подаче сигнала Чтобр (чтение обратное), на выходах конъюнкторов второй группы появится число в обратном коде, а при одновременной подаче сигналов Чтпр и Чтобр будет прочитано число из регистра в парафазном параллельном коде. Схема однофазного регистра на синхронных RS-триггерах с установочными R и S входами отличается от рассмотренной лишь тем, что на вход R регистра инверсный код числа не подается. В этом случае этапу приема числа в регистр предшествует этап сброса регистра в нулевое состояние, который осуществляется по сигналу Уст «0», поступающему одновременно на асинхронные входы R всех триггеров. Далее по сигналу С те триггера, на входы S которых подается единичный сигнал, перейдут в единичное состояние, а остальные останутся в нулевом состоянии. Таким образом, однофазный регистр на RS-триггерах является двухтактным, тогда как парафазный регистр – однотактным. Поэтому для увеличения быстродействия однофазные регистры строятся на D-триггерах, сбрасывать которые в нулевое состояние нет необходимости. Регистр последовательного действия В ЭВМ на ряду с параллельным используется также последовательный способ представления двоичной информации, при котором код числа передается по одному каналу последовательно разряд за разрядом в дискретные моменты времени, задаваемые синхроимпульсами. Для приема и выдачи чисел, представленных в последовательном коде, и используются регистры последовательного действия, основу которых составляют регистры сдвига. Регистр сдвига осуществляет операцию сдвига записанного в него двоичного числа влево или вправо на один или несколько разрядов при подаче специального управляющего сигнала «сдвиг». Рассмотрим синтез двухразрядного сдвигающего регистра на D-триггерах. Регистр должен работать следующим образом: в момент прихода синхронизирующего сигнала С число сдвигается в регистре вправо на один разряд. При этом разряды числа, сдвигаемые вправо, поступают на выход регистра, а в освобождающиеся слева разряды вводятся разряды числа, поступившего в последовательном коде на его вход. Имеем следующую кодированную таблицу переходов и функции возбуждения (таблица выходов не строится, ибо выходами регистра являются выходы самих триггеров). Кодированная таблица переходов и функций возбуждения: Используя диаграммы Вейча, получаем следующие минимальные дизъюнктивные нормальные формы функций возбуждения триггеров: Отсюда получаем следующую схему сдвигающего регистра (рис.8.2). С целью устранения гонок и неустойчивых состояний используются двухступенчатые D-триггера. Рис. 8.3 Аналогично строится и n-разрядный регистр сдвига, который содержит n последовательно соединенных D-триггеров, причем вход первого триггера является входом регистра. По приведенной методике можно построить регистр сдвига информации влево или вправо и на другой элементной базе, например на RS или JK триггерах. Заметим, что в случае сдвига информации, хранящейся в регистре, и отсутствии входного сигнала, в освобождающиеся разряды регистра вводятся нули. Например, регистр сдвига вправо на один разряд на синхронных JK триггерах имеет вид (рис. 8.4). Если в такой регистр занести число в параллельном коде, а потом осуществлять сдвиг этого числа вправо на один разряд, то число, первоначально представленное в параллельном коде, будет преобразовано в последовательный код. Рис. 8.4 После n сдвигов в регистр будет находиться код нуля. Если схему регистра дополнить схемой ввода информации, то такой регистр может осуществить преобразования числа из последовательного кода в параллельный (рис.8.5): Рис. 8.5 Заполнение регистра в этом случае будет происходить в течение n тактов, после чего число, находящееся в регистре, может быть прочитано в параллельном коде. Цепи ввода и вывода числа в такой регистр в параллельном коде такие же, как и у параллельного регистра. Регистр сдвига на функциональных схемах обозначается следующим образом (рис. 8.6): Рис. 8.6 Для указания направления сдвига используется стрелка: ® сдвиг в сторону старших разрядов, ¬ сдвиг в сторону младших разрядов. Счетчики Счетчиком называется типовой узел ЭВМ, предназначенный для подсчета числа входных сигналов (импульсов). По целевому назначению счетчики подразделяются на суммирующие, вычитающие и реверсивные. Суммирующий счетчик предназначен для выполнения счета импульсов в прямом направлении, т.е. для сложения. С приходом очередного импульса на вход счетчика его содержимое увеличивается на единицу. Вычитающий счетчик предназначен для выполнения счета в обратном направлении, т.е. в режиме вычитания. Каждый импульс, поступающий на вход такого счетчика, уменьшает его содержимое на единицу. Реверсивными называются такие счетчики, которые могут работать как в режиме сложения, так и в режиме вычитания. По способу построения цепей сигналов переноса различают счетчики с одновременным, групповым, сквозным и последовательным переносами. Основными характеристиками счетчиков являются: 1. Быстродействие, оцениваемое максимальной частотой поступления входных импульсов F = 1/T , T – период следования счетных импульсов. 2. Модуль счета или коэффициент пересчета К. Коэффициент пересчета К характеризует число устойчивых состояний счетчика, т.е. предельное число импульсов, которое может быть сосчитано счетчиком. Например, при К = 12 счетчик имеет 12 состояний: от 0 до 11. И каждый двенадцатый импульс будет возвращать его в начальное состояние. Если счетчик имеет n разрядов, то Kmax = 2n. Каждому состоянию соответствует n разрядное двоичное число (от 0 до 2n –- 1), а всего таких чисел 2n. Суммирующий счетчик В простейшем случае двоичный счетчик может быть образован из асинхронных Т-триггеров, соединенных последовательно. При этом сигналы счета a поступают на вход Т-триггера младшего разряда счетчика. Выход Q триггера каждого разряда соединен со входом Т соседнего триггера более старшего разряда. Поскольку в процессе счета переключение триггеров отдельных разрядов в этом счетчике осуществляется последовательно разряд за разрядом, такой счетчик носит название счетчика с последовательным переносом. Для ликвидации неустойчивых состояний используются двухступенчатые триггера. Схема счетчика имеет следующий вид (рис. 8.7): Рис. 8.7 Числа, формируемые счетчиком, могут быть выведены из него в параллельной форме посредством одновременного опроса состояния всех разрядов счетчика. Счетчики обычно строятся на синхронных или асинхронных двухступенчатых Т-триггерах. В асинхронном Т-триггере смена состояний происходит по заднему фронту входного сигнала, поскольку двухступенчатый триггер можно рассматривать как схему, состоящую из двух триггеров (рис. 8.8): Рис. 8.8 В синхронном триггере смена состояний происходит по заднему фронту синхроимпульсов С (рис. 8.9): Рис. 8.9 Временная диаграмма работы 3-х разрядного асинхронного суммирующего счетчика с последовательным переносом имеет следующий вид (рис. 8.10): Рис. 8.10 Максимальная частота работы этого счетчика определяется максимально допустимой частотой переключения его младшего разряда. Для двухступенчатых триггеров частота счетных импульсов определяется из условия , где tсч – длительность счетных импульсов, tn – время переключения второй ступени триггера. Поскольку опрос состояния всех разрядов может происходить только в паузе между сигналами счета, т.е. после того, как завершился переходной процесс, связанный с переключением всех триггеров, имеем: Здесь n- разрядность счетчика, tопр – длительность сигнала опроса, ntn – время полного переключения n разрядов счетчика. Вычитающий счетчик. Реверсивный счетчик Вычитающий счетчик также может быть построен из последовательно соединенных Т-триггеров. На вход младшего разряда счетчика поступают сигналы счета, а входы последующих разрядов соединены с обратными выходами предшествующих триггеров. В результате получается асинхронный вычитающий счетчик с последовательным переносом (рис. 8.11). Рис. 8.11 Для построения реверсивного счетчика необходимо объединить схемы суммирующего и вычитающего счетчиков. Схема асинхронного реверсивного счетчика с последовательным переносом имеет следующий вид (рис. 8.12): Рис. 8.12 Здесь при наличии единичного сигнала на управляющей шине I счетчик работает как суммирующий, а при наличии единичного сигнала на управляющей шине II – как вычитающий. Обычно счетчики имеют цепи установки в нулевое и единичное состояния. Нарисуем схему асинхронного реверсивного счетчика на синхронных JK-триггерах, имеющих асинхронные инверсные установочные входы R и S (рис.8.13). Счетчики с последовательным переносом наиболее просты, но имеют невысокое быстродействие. Для увеличения быстродействие усложняют схему формирования сигналов переноса. Рис. 8.13 Лекция 9 Счетчики с одновременным, сквозным и групповым переносом Для ускорения процесса счета в счетчике необходимо, чтобы изменения состояний отдельных разрядов происходило не последовательно, а непосредственно вслед за приходом очередного сигнала счета. Такие счетчики обычно строят на синхронных двухступенчатых Т-триггерах. При этом счетные сигналы подаются по шине α на синхронизирующие входы триггеров всех разрядов одновременно. Сигнал на входе Т каждого триггера формируется логической схемой в зависимости от состояний всех триггеров счетчика. Синтез такого счетчика можно провести на основании кодированной таблицы переходов трехразрядного счетчика и таблицы функций возбуждения. На основании этой таблицы построим диаграммы Вейча для сигналов возбуждения триггеров, рассматривая их как функции состояний триггеров Q1(t), Q2(t) и Q3(t) при α = 1. Имеем: Из диаграмм получаем следующие выражения для сигналов возбуждения триггеров: T1 = α, T2 = Q1 α, T3 = Q1Q2 α. При синтезе n-разрядного счетчика по аналогии получим следующие выражения для сигналов возбуждения триггеров: T1 = α, T2 = Q1α, T3 = Q1Q2α, T4 = Q1Q2Q3α, …, Tn = Q1Q2Q3…Qn-1α . Счетчик, построенный в соответствии с этими уравнениями, носит название счетчика с одновременным или параллельным переносом. Т.к. во всех функциях возбуждения присутствует входной сигнал a, то такой счетчик целесообразно строить на синхронных Т-триггерах, подавая счетные сигналы на входы синхронизации всех триггеров. В результате получим следующую схему (рис. 9.1). В таком счетчике изменение состояния всех триггеров происходит одновременно. Частота работы такого счетчика определяется из следующего выражения: Рис. 9.1 Здесь Δt – время задержки сигнала коньюнктором. Разрядность счетчика с параллельным переносом ограничивается возможностями логических элементов: коэффициентами разветвления и объединения. Поэтому иногда бывает целесообразно строить менее быстродействующую схему, но с использованием только двухвходовых логических элементов. При синтезе такого счетчика достаточно переписать функции возбуждения, полученные ранее, в виде T1 = α; T2 = Q1T1; T3 = T2Q2; T4 = T3Q3; … Tn = Tn-1Qn-1. Счетчик, построенный по этим уравнениям, называется счетчик со сквозным переносом (рис. 9.2). Максимальная частота работы такого счетчика равна Существует тип счетчиков с так называемым групповым переносом. Эти счетчики занимают промежуточное место по быстродействию и сложности между счетчиками с одновременным и сквозным переносом, и используются в случае, когда число разрядов велико. В таких случаях счетчик разбивается на группы разрядов, в пределах каждой из которых строят цепи одновременного переноса. Перенос между группами реализуется обычно методом сквозного переноса. Рассмотрим процесс построения такого счетчика. Пусть n разрядов счетчика делятся на группы по k разрядов. Введем обозначения Tl гр – перенос на вход l -ой группы Tl гр j – перенос на вход j-го разряда в l-ой группы . Примем для простоты n = 9, k = 3. Тогда формулы, полученные ранее для функций возбуждения, можно представить в виде: T1 гр = T1 = 1; T2 гр = Tl гр(Q3Q2Q1) = Q3Q2Q1 = T4; T3 гр = T2 гр(Q6Q5Q4) = T7; T4 гр = T3 гр(Q9Q8Q7) = T10. Из этих формул видно, что между группами разрядов можно организовать цепи сквозного переноса, а внутри каждой группы одновременный перенос. Организация цепей сквозного переноса (рис. 9.3). Т.е. в этой схеме каждый из трехразрядных счетчиков с одновременным переносом может быть выполнен не только на Т-триггерах, но и на других типах триггеров, например, на JK- триггерах со сложной входной логикой. Здесь группы входов по J и K связаны внутри каждой из групп по элементам И. Синтез счетчиков с коэффициентом пересчета, не равным 2n Рассмотренные схемы n-разрядных счетчиков имеют коэффициент пересчета k, равный целой степени двух (k=2n). Для многих устройств ЭВМ необходимы счетчики с коэффициентом . Такие счетчики называют еще пересчетными схемами. Эти счетчики получают за счет введения в схему обратной связи, управляющей переходом двоичного счетчика из состояния, соответствующего числу k – 1, в нулевое состояние. Синтезируем счетчик с коэффициентом пересчета равным пяти на Т-триггерах и элементах булева базиса. Такой счетчик имеет пять состояний (от 0 до 4). В исходном состоянии счетчик находится в нуле. После поступления на его вход пяти импульсов он снова должен оказаться в нулевом состоянии. Количество триггеров определяется согласно формуле , где k = 5 – число состояний. Отсюда R=3. Выходной сигнал z = 1 должен формироваться на каждый пятый входной сигнал. В результате получаем кодированную таблицу переходов и выходов, а также сигналы возбуждения: При a = 1 построим следующие диаграммы Вейча: Из диаграмм Вейча получаем следующие выражения для трех функций возбуждения и функции выходов: , , , . Построим схему счетчика (рис. 9.4). Рис. 9.4 Аналогичным образом может быть синтезирован вычитающий и реверсивный счетчики с различными коэффициентами пересчета. При синтезе реверсивного счетчика появится дополнительный входной сигнал y, управляющий режимом работы счетчика. При сигнале y = 0 синтезируем, например, суммирующий счетчик, а при y = 1 – вычитающий. Кодированную таблицу переходов строим одну. Проведем синтез вычитающего счетчика с коэффициентом пересчета, равным 9, и реверсивный счетчик с коэффициентом пересчета, равным 7 при сложении и вычитании (синтез проводят студенты). Лекция 10 Счетчики на сдвигающих регистрах Эти счетчики строятся на регистрах сдвига, охваченных цепями обратных связей, и применяются, в основном, при построении схем с небольшим коэффициентом пересчета k. Простейшим счетчиком такого типа является счетчик, построенный на основе кольцевого сдвигающего регистра, один из разрядов которого предварительно устанавливается в единичное состояние. После каждого счетного импульса осуществляется сдвиг этой единицы на один разряд, и получается переход счетчика в новое состояние. Такой счетчик осуществляет подсчет сигналов по модулю n, т.е. k = n, где n – число разрядов счетчика. Такой счетчик называют еще электронным коммутатором. Основным преимуществом такого счетчика является простота дешифрации его состояний и высокое быстродействие. Недостаток заключается в том, что при больших значениях k требуется большое число триггеров. Эти счетчики обычно строятся на D-, RS- и JK-триггерах. Построим схему такого счетчика на синхронных двухступенчатых RS-триггерах при k = n = 5 (рис. 10.1): Рис. 10.1 Такой счетчик имеет 5 состояний: 10000 – исходное состояние, затем: 01000, 00100, 00010, 00001 и вернулись в исходное состояние 10000. Кодовое кольцо Если в приведенной схеме счетчика на кольцевом регистре прямой выход последнего триггера соединить со входом R первого триггера, а инверсный выход – со входом S, то получится счетчик на регистре с перекрестными связями или счетчик Джонсона. Такой счетчик будет иметь число состояний в два раза больше, чем число разрядов, т.е. k = 2n. В нашем примере это состояния: 10000, 11000, 11100, 11110, 11111, 01111, 00111, 00011, 00001, 00000, 10000 и т.д., т.е. 5-ти разрядный счетчик имеет коэффициент пересчета, равный 10. Путем исключения из схемы одного «избыточного» состояния, за счет введения элемента И, можно сделать счетчик Джонсона и с нечетным коэффициентом пересчета k = 2n – 1. Например, счетчик Джонсона с k = 9 на D-триггерах имеет вид (рис.10.2): Рис. 10.2 00000 – исходное состояние, затем 10000, 11000, 11100, 11110, 01111, 00111, 00011, 00001, 00000 – вернулись в исходное состояние. Полиномиальные счетчики Полиномиальные счётчики строятся на основе n-разрядного регистра сдвига с линейными обратными связями (с сумматорами по модулю два в цепи обратной связи). В качестве примера рассмотрим схему счётчика при n = 4 (рис. 10.3): Рис. 10.3 Последовательность состояний регистра сдвига представлена на рис. 10.4 (состояние 0 0 0 0 запрещено). Рис. 10.4 Работа схемы описывается с помощью квадратной матрицы С, связывающей данное и последующее состояния. Для нее состояния триггеров q1, q2, q3 и q4 в момент времени (t + 1) определятся следующим образом: или в матричной форме или , где Первая строка в матрице C определяется видом обратной связи регистра сдвига, остальные единичные элементы матрицы определяют операцию сдвига содержимого регистра. Периодические свойства последовательностей на выходах счетчика определяются характеристическим многочленом , который является определителем матрицы (Е – единичная матрица). Если многочлен неприводим и примитивен, то счетчик будет формировать последовательность максимальной длины или М-последовательность. Для данного примера характеристический многочлен j (х) неприводим, примитивен и имеет следующий вид: = x4 x 1. Вероятности появления символа 1 и символа 0 для М-последовательности определяются следующим образом: , . Известен оригинальный метод построения счетчика на регистре с s-шаговым сдвигом за один рабочий такт (). Запишем следующие соотношения: , и т.д. Пусть s = 2. Тогда матрица имеет вид: По матрице построим схему счетчика: Рис. 10.5 Последовательность состояний регистра сдвига при s = 2 (пунктирные линии) и при s = 1 (сплошные линии) показаны на рис. 10.6: Рис. 10.6 Как видно из рисунка, счетчик также формирует М-последовательность. Возьмем s = 3. Матрица функционирования счетчика в этом случае имеет вид: Рассмотрим схему счетчика при s = 3 (рис. 10.7): Рис. 10.7 В данном случае D-триггер и сумматор по модулю два в его обратной связи представляют собой T-триггер. Поэтому эту схему можно преобразовать следующим образом (рис. 10.8), и она может быть построена только на D- и T-триггерах, соединенных в кольцо: Рис. 10.8 Рис. 10.9 Здесь необходимо отметить, что для того, чтобы каждый выходной разряд счетчика также формировал последовательности максимальной длины, необходимо, чтобы число шагов s и период последовательности M были взаимно простыми числами, т.е. (M, s) = 1. Поскольку в данном примере это условие не выполняется, диаграмма последовательности состояний регистра разбивается на несколько периодов меньшей длины (рис. 10.10): Рис. 10.10 Пусть s = 4. Матрица в этом случае имеет вид: Схема счетчика: Рис. 10.11 Эта схема может быть построена только на Т-триггерах и одном сумматоре по модулю два (рис. 10.12): Рис. 10.12 В общем случае схема полиномиального счетчика на основе n-разрядного регистра сдвига с линейными обратными связями представлена на рис. 10.13: Рис. 10.13 Если коэффициент Ci = 1, то выход i-го триггера подается на вход сумматора по модулю 2, если же Ci = 0, то – не подается. В соответствии с коэффициентами многочлена однозначно определяется структура обратной связи регистра сдвига. Есть таблица всех неприводимых многочленов, из которой находят многочлены, представленные в 8-ричной форме. Например, характеристический многочлен = x4 x 1 в этой таблице будет иметь следующий вид: = . В двоичном виде этом многочлен запишется как: 10 011, или в 8-ричном виде – 23. По такой записи многочлена однозначно строится схема полиномиального счетчика. Лекция 11 Дешифраторы Дешифратор представляет собой комбинационную схему с n входами и m выходами. Назначение дешифраторов – обеспечить на каждом из выходов сигнал, равный единицы, только при вполне определенной комбинации входных сигналов. Пусть входные шины дешифратора пронумерованы целыми числами, начиная с нуля. Тогда при подаче на входы дешифратора сигналов, соответствующих n-разрядному двоичному числу L, единичный выходной сигнал появится на L-ом выходе. Например. Пусть на входы дешифратора подается комбинация сигналов 1100(2) = 12(10). Тогда единичный сигнал появится только на 12-ом выходе дешифратора, а на остальных выходах будут нулевые сигналы. Максимальное число выходов дешифратора равно m = 2n. Такие дешифраторы называются полными. Дешифраторы ставятся на выходах регистров и счетчиков. Они преобразуют двоичный код числа на регистре в управляющий сигнал на одном из своих выходов. Причем код числа может подаваться как в однофазном коде, так и в парафазном. В последнем случае с выхода регистра (счетчика) на входы дешифратора поступают как прямые, так и инверсные сигналы. На структурных схемах дешифратор обозначается следующим образом (с парафазными входами) (рис.11.1). Дешифратор представляет собой комбинационную схему со многими выходами и описывается следующей системой переключательных функций (11.1): Рис. 11.1 Каждая переключательная функция уj представляет собой конституэнту единицы и поэтому равна единице на одном наборе, номер которого равен j. По способам реализации системы переключательных функций различают линейные, прямоугольные (матричные) и пирамидальные дешифраторы. Линейные дешифраторы Линейные дешифраторы являются наиболее быстродействующими. Они представляют собой одну ступень логических элементов, которая непосредственно реализует систему (11.1) ПФ. Такой дешифратор содержит 2n конъюнкторов с числом входом n у каждого. В качестве примера приведем схему дешифратора с парафазными входами при n = 3, m=8 (рис.11.2). Количество разрядов дешифрируемого слова в линейном дешифраторе ограничено максимально допустимым числом входов у логических элементов и нагрузочной способностью элементов входного регистра. Чаще всего фактором, ограничивающим число разрядов в линейном дешифраторе, является допустимая нагрузка на элементы входного регистра (2n = требуемая нагрузка). Поэтому такие дешифраторы не используются при больших n. Параметры линейного дешифратора: быстродействие: tзадержки = t&, число логических элементов 2n, число входов у элементов n, общее число входов логических элементов вл = n2n. Рис. 11.2 Прямоугольные дешифраторы При большом числе разрядов дешифрируемого слова более удобным и экономичным оказывается прямоугольный дешифратор, который является многоступенчатым. Количество ступеней зависит от числа групп, на которое разбивается многоразрядное дешифрируемое слово. В первой ступени такого дешифратора содержатся несколько линейных дешифраторов, число которых зависит от числа ступеней. На второй ступени дешифратора, которая может быть оконечной или промежуточной, образуются произведения сигналов, поступающих из линейных дешифраторов первой ступени. В качестве примера рассмотрим прямоугольный двухступенчатый дешифратор на 4-е разряда. Все четырехразрядное слово в таком дешифраторе разбивается на 2 группы по 2 разряда в каждой группе. Каждая группа разрядов числа дешифрируется линейным дешифратором. Во второй ступени формируются выходные сигналы дешифратора (рис. 11.3). Рис. 11.3 Для двухступенчатого прямоугольного дешифратора справедливы следующие соотношения (11.2): Рис (11.2) где при нечетном n, при четном n. При таком разбиении общее число элементов И в первой и второй ступени равно (n – четное), а общее число входов у этих элементов равно --- , т.к. в первой ступени элементы имеют n/2 входов (формула справедлива при n > 2). Быстродействие: tзадержки = 2t&, число элементов в выходном каскаде (ступени) 2n, число входов у элементов в выходном каскаде равно 2, общее число входов во второй ступени равно 2n+1. Для прямоугольного дешифратора фактором, ограничивающим число разрядов дешифрируемого слова, чаще всего является нагрузочная способность элементов входного регистра или элементов первого каскада. При достаточно большом числе разрядов дешифрируемого слова (n ³ 6) и ограниченной нагрузочной способности элементов (F £ 10) полный прямоугольный дешифратор строится с числом ступеней больше двух. При этом на элементы оконечной ступени подаются сигналы с 2-х прямоугольных дешифраторов предоконечной ступени, на каждый из которых подаются сигналы с двух предшествующих прямоугольных дешифраторов и т.д. 1-й каскад дешифратора строится из линейных дешифраторов. В большинстве случаев оказывается достаточным использовать 3 каскада. На рис. 11.4 приведена схема трехступенчатого прямоугольного дешифратора на 9 входов и 512 выходов. Рис. 11.4 На рис. 11.5 приведена схема трехступенчатого дешифратора на 12 входов, имеющего 4096 выходов. Рис. 11.5 Прямоугольные дешифраторы При большом числе разрядов дешифрируемого слова более удобным и экономичным оказывается прямоугольный дешифратор, который является многоступенчатым. Количество ступеней зависит от числа групп, на которое разбивается многоразрядное дешифрируемое слово. В первой ступени такого дешифратора содержатся несколько линейных дешифраторов, число которых зависит от числа ступеней. На второй ступени дешифратора, которая может быть оконечной или промежуточной, образуются произведения сигналов, поступающих из линейных дешифраторов первой ступени. В качестве примера рассмотрим прямоугольный двухступенчатый дешифратор на 4-е разряда. Все четырехразрядное слово в таком дешифраторе разбивается на 2 группы по 2 разряда в каждой группе. Каждая группа разрядов числа дешифрируется линейным дешифратором. Во второй ступени формируются выходные сигналы дешифратора (рис. 11.3). Рис. 11.3 Для двухступенчатого прямоугольного дешифратора справедливы следующие соотношения (11.2): Рис (11.2) где при нечетном n, при четном n. При таком разбиении общее число элементов И в первой и второй ступени равно (n – четное), а общее число входов у этих элементов равно --- , т.к. в первой ступени элементы имеют n/2 входов (формула справедлива при n > 2). Быстродействие: tзадержки = 2t&, число элементов в выходном каскаде (ступени) 2n, число входов у элементов в выходном каскаде равно 2, общее число входов во второй ступени равно 2n+1. Для прямоугольного дешифратора фактором, ограничивающим число разрядов дешифрируемого слова, чаще всего является нагрузочная способность элементов входного регистра или элементов первого каскада. При достаточно большом числе разрядов дешифрируемого слова (n ³ 6) и ограниченной нагрузочной способности элементов (F £ 10) полный прямоугольный дешифратор строится с числом ступеней больше двух. При этом на элементы оконечной ступени подаются сигналы с 2-х прямоугольных дешифраторов предоконечной ступени, на каждый из которых подаются сигналы с двух предшествующих прямоугольных дешифраторов и т.д. 1-й каскад дешифратора строится из линейных дешифраторов. В большинстве случаев оказывается достаточным использовать 3 каскада. На рис. 11.4 приведена схема трехступенчатого прямоугольного дешифратора на 9 входов и 512 выходов. Рис. 11.4 На рис. 11.5 приведена схема трехступенчатого дешифратора на 12 входов, имеющего 4096 выходов. Рис. 11.5 Сумматоры Сумматор является основным узлом арифметического устройства ЭВМ и предназначается для выполнения операции арифметического суммирования двух чисел с фиксированной запятой. В дальнейшем будем считать, что все числа, поступающие на входы сумматора, меньше единицы, т.е. запятая фиксирована после знакового разряда. Слагаемые и сумму будем обозначать соответственно буквами A, B и S, где A = amam-1…ai…a1; B = bmbm-1…bi…b1; S = smsm-1…si…s1 Классификация сумматоров 1. В зависимости от основания системы счисления и принятой системы кодирования различают двоичные, троичные, десятичные, двоично-десятичные и др. сумматоры. 2. По способу организации процесса суммирования различают сумматоры комбинационного и накапливающего типов. Сумматор комбинационного типа – это логическое устройство, обеспечивающее получение сигналов суммы и переноса при одновременной подаче кодов слагаемых. При снятии сигналов хотя бы одного слагаемого значение суммы на выходе комбинационной схемы исчезает, т.к. такой сумматор не имеет памяти. Сумматор накапливающего типа строится на основе Т-триггеров. Исходные числа (слагаемые), поданные на вход сумматора одно за другим, накапливаются в сумматоре в виде суммы и сохраняются после прекращения подачи входных сигналов. 3. По способу обработки многоразрядных чисел различают сумматоры последовательного, параллельного и параллельно-последовательного действия. В последовательном сумматоре производится поразрядная обработка слагаемых А и В. Пары разрядов аi и вi этих чисел поступают в сумматор последовательно от младших разрядов к старшим. В параллельном сумматоре числа А и В поступают одновременно и поэтому обработка всех разрядов слагаемых производится также одновременно. В параллельно-последовательном сумматоре все числа разбиваются на a групп по b разрядов в каждой группе. Внутри групп числа суммируются параллельно, а сами группы разрядов подаются на входы сумматора последовательно. 4. По способу организации цепей переноса различают многоразрядные сумматоры с последовательным, сквозным, групповым и одновременным переносами. Одноразрядные двоичные сумматоры Сумматор SM служит для образования сигнала суммы Si по сигналам трех цифр ai, bi и рi i-го разряда и формирования сигнала переноса рi+1 в следующий старший разряд. Одноразрядный сумматор принято обозначать на схемах в следующем виде (рис. 11.7). Кроме сумматоров существуют полусумматоры, которые осуществляют сложение двух чисел (рис. 11.8). Рис. 11.7 Рис.11.8 Лекция 12 Одноразрядный комбинационный сумматор Закон функционирования сумматора при сложении трех цифр определяется следующей таблицей истинности: На основе таблицы строятся диаграммы Вейча и получаются минимальные ДНФ функций si и pi+1 .  ,  По полученным уравнениям можно построить двухуровневую схему одноразрядного комбинационного сумматора (рис. 12.1). Рис. 12.1 Эта схема, имеющая парафазные входы, обладает большим быстродействием, т.к. число уровней здесь r = 2, а суммарное число входов у логических элементов равно 25. Полученную схему можно упростить, если рассматривать si как функцию 4-х переменных si = f(аi, вi, pi, pi+1). Отсюда имеем: Схема представлена на рис. 12.2. Эта схема, имеющая однофазные входы, обладает худшим быстродействием, т.к. r = 6. Суммарное число входов равно здесь 17, т.е. последняя схема несколько проще. Рис. 12.2 Схема с однофазными входами на элементах И-НЕ и ИЛИ-НЕ Преобразуем выражения для сигналов переноса и суммы: следующим образом: ,  =  . Рис.12.3 Одноразрядный накапливающий сумматор Одноразрядным сумматором накапливающего типа является схема, суммирующая поочередно поступающие на ее вход цифры слагаемого и переноса с запоминанием результата суммирования. Для запоминания результата сложения на выходе рассмотренных комбинационных сумматоров можно установить триггеры (триггера R-S и D-типов). Совместно с триггером комбинационный сумматор будет выполнять функции накапливающего сумматора. Роль накапливающего сумматора может выполнять и счетный триггер со схемой формирования переноса, на счетный вход которого все слагаемые должны подаваться последовательно во времени. В этом случае суммирование трех слагаемых будет проходить за 3 такта (рис. 12.4): Рис. 12.4 Рассмотрим работу устройства. В первый момент времени t1 через схему ИЛИ1 на вход Т-триггера, который был предварительно установлен в нулевое состояние, поступает цифра ai и запоминается. После завершения переходных процессов в триггере в момент времени t2 через схему ИЛИ1 поступает цифра вi второго слагаемого. При этом Т-триггер реализует функцию  . Наконец в следующий момент времени t3 через схему ИЛИ1 подается цифра переноса из более младшего разряда рi и триггер реализует функцию: которая совпадает с функцией si, полученной ранее по таблице истинности одноразрядного сумматора. Таким образом по истечении трех тактов в триггере будет находится значение i-го разряда суммы слагаемых А и В, т.е. si. Сигнал переноса pi+1 формируется комбинационной схемой, стоящей на выходе триггера. В момент времени t3, когда триггер еще находится в состоянии f1, приходит сигнал рi. На выходе И1 имеем: Если теперь к f3 добавить через дизъюнкцию aibi, то получится рi+1. Непосредственно aibi получить с помощью конъюнктора нельзя, т.к. они поступают в различные дискретные моменты времени. Поэтому aibiформируются с помощью элемента И2, реализующего функцию Окончательно сигнал переноса pi+1 на выходе ИЛИ2 равен: Этот сигнал совпадает с переносом, формируемом в комбинационном сумматоре на выходе рi+1 . Недостаток рассмотренного сумматора заключается в том, что он имеет малое быстродействие, поскольку в каждом цикле суммирования число срабатываний триггера может равняться четырем: Уст «0», ai(t1), bi(t2) и рi(t3). Достоинство накапливающего сумматора по сравнению с комбинационным состоит в более простой организации суммирования с накоплением результата. Полученная сумма сохраняется в сумматоре и после снятия входных сигналов. Комбинационно-накапливающий одноразрядный сумматор Положительные свойства сумматоров накапливающего и комбинационного типов сочетает в себе сумматор комбинационно-накапливающего типа, в котором сигнал переноса вырабатывается комбинационной схемой, а сумма образуется в Т-триггере, на счетный вход которого с помощью другой комбинационной схемы подается результат сложения по модулю два цифр второго слагаемого и переноса. Схема сумматора приведена на рис. 12.5. Сумматор работает следующим образом. Сигнал ai подается на вход S триггера, который был предварительно установлен в нуль (если ai вводится в триггер в парафазном коде, то установка триггера в нуль не делается). Рис. 12.5 Цифра bi второго слагаемого и перенос рi поступают в комбинационную схему, реализующую функцию сложения по модулю два, т.е  Сигнал f5 поступает на счетный вход триггера, в котором хранится цифра ai первого слагаемого. В результате в триггере образуется код суммы, т.е. При подаче синхроимпульсов в триггере образуется сумма si, которая появится на выходе в момент окончания действия синхроимпульса. Если ai будет поступать в триггер в парафазном коде, то операция сложения будет выполняться за один такт: вначале такта в триггер поступает ai (СИ = 0), а при СИ = 1 поступают bi и pi, т.е. такой сумматор обладает большим быстродействием по сравнению с сумматором накапливающего типа. Многоразрядные сумматоры В зависимости от того, каким образом в ЭВМ передаются числа, может быть два способа сложения: последовательный и параллельный. При последовательном способе сложения при передаче каждого слагаемого используется один канал, по которому код числа передается в виде временной последовательности цифр разряд за разрядом. Если для передачи каждого разряда числа предусмотрен отдельный канал, то применяется параллельный способ сложения. Последовательный сумматор Последовательный сумматор должен преобразовывать последовательные коды слагаемых в последовательный код суммы этих слагаемых. Такие сумматоры обычно строятся на основе одноразрядного комбинационного сумматора, в котором для запоминания сигнала переноса используется D-триггер (рис. 12.6): Рис. 12.6 При последовательном суммировании разряды ai и bi слагаемых А и В, начиная с младших, поступают на входы одноразрядного комбинационного сумматора SM с выходов сдвигающих регистров. Значения разрядов суммы Si заносятся в освобождающиеся разряды одного из сдвигающих регистров. На вход piсумматора SM поступает сигнал переноса, который был получен в предыдущем такте при суммировании ai - 1, bi - 1 и Pi - 1. Для запоминания сигнала переноса используется D-триггер. Очевидно, для сложения m разрядных чисел А и В используется m+1 такт (в последнем (m+1)-ом такте перенос из самого старшего разряда поступает на вход сумматора, где суммируется с нулевыми значениями цифр слагаемых). Поэтому такой сумматор обладает очень низким быстродействием. С целью ускорения процесса сложения используются параллельные сумматоры. Параллельные сумматоры с последовательным переносом При параллельном способе сложения необходимо иметь отдельные одноразрядные сумматоры для каждого разряда чисел. Параллельный сумматор может быть составлен из одноразрядных сумматоров путем соединения выхода, на котором получается сигнал переноса данного разряда, со входом для сигнала переноса соседнего, более старшего разряда. В зависимости от типа используемых одноразрядных сумматоров параллельные сумматоры могут быть комбинационными, накапливающими и комбинационно - накапливающими. Простейшим является параллельный комбинационный сумматор с последовательным переносом, схема которого приведена на рис. 12.7: Рис. 12.7 Здесь сигнал переноса, который возникает в каком либо разряде, распространяется к старшим разрядам по цепочке сумматоров, т.е. в таком сумматоре цепь переноса получается последовательной. Поэтому время сложения двух m-разрядных чисел будет равно m×tзр, где tзр – время задержки сигнала в цепях формирования переноса одноразрядного сумматора. Если на таком сумматоре числа А и В складываются в обратном коде, то в схеме добавляется цепь циклического переноса, связывающая выход переноса старшего (знакового) разряда со входом переноса младшего разряда. Недостатком рассмотренного сумматора является его сравнительно низкое быстродействие. Для увеличения быстродействия в сумматорах применяют сквозной, одновременный или групповой переносы. Параллельный сумматор с одновременным переносом Время формирования суммы может быть еще уменьшено, если использовать сумматоры с одновременным (параллельным) переносом. Принцип построения таких сумматоров заключается в том, что значение каждого разряда суммы получается в результате одновременного анализа данного и всех более младших разрядов слагаемых. Для вывода формулы одновременного переноса в (i+1)-й разряд представим все формулы сквозного переноса для каждого разряда:  , , …,  , . Подставив значение р2 в уравнение для р3, значение р3 – в р4 и т.д., получим логическое уравнение переноса в (i + 1) разряд, выраженное через значения разрядов слагаемых имеет вид: Из этого уравнения следует, что на выходе i-го разряда перенос рi + 1 возникает тогда, когда он образован в данном разряде, или если он был образован в некотором предыдущем разряде, а во всех последующих разрядах, включая данный, выполняется условие распространения переноса. Следовательно, перенос в каждом разряде может быть выработан одновременно с запуском переноса р1 в младший разряд. Из этого выражения может быть образована система уравнений для сумматора с одновременным переносом. Так система уравнений для трехразрядного сумматора имеет следующий вид:  ,  . На основании записанной системы уравнений построим схему сумматора с одновременным переносом (рис. 12.9): Рис. 12.9 Т.к. слагаемые А и В в такой схеме подаются параллельно, то и переносы формируются одновременно. Время суммирования чисел в таком сумматоре равно tå = tзå + tзр, где tзå – время задержки формирования сигнала суммы si, tзр – время задержки формирования сигнала переноса. Схема формирования сигнала переноса на элементах булевого базиса в каждом разряде трехуровневая (один уровень – вычисление Ti и Сi , второй и третий уровни получение pi + 1 по сформированным Ti и Сi ). Поэтому tзр=3Dt, где Dt – задержка сигнала в одном логическом элементе. Такие сумматоры являются самыми быстродействующими. Из приведенной схемы видно, что цепи формирования сигнала переноса с увеличением номера разряда i усложняются и сам сумматор, в отличие от ранее рассмотренных, построен на неоднотипных схемах разрядов, т.е. является не регулярным. Регулярными являются сумматоры, построенные на однотипных схемах, например сумматоры с последовательным и сквозным переносами. Поэтому существующие ограничения по нагрузочной способности и коэффициенту объединения не позволяют строить сумматоры с одновременным переносом на большое число разрядов. На практике используют в зависимости от требуемого быстродействия различные схемы сумматоров с групповым переносом. Параллельные сумматоры с групповым переносом В сумматорах с групповым переносом все разряды разбиваются на  групп по  разрядов в каждой группе (обычно  = 4¸6). В пределах каждой из групп организуется одновременный или сквозной перенос. Между группами перенос может быть либо одновременным, либо сквозным. Например, 12-ти разрядный сумматор с одновременным переносом между группами (в каждой группе 4 разряда) имеет следующий вид (рис. 12.10): Рис. 12.10 Здесь каждый 4-х разрядный сумматор с одновременным переносом строится так же, как это было рассмотрено ранее. Cjгр – сигнал переноса из j группы (собственный перенос). Tjгр – сигнал условия прохождения через j-ю группу (признак транзитного переноса). Tjгр =Tll-1jгр…Tk, где k – номер младшего разряда в группе, l – номер старшего разряда в группе. Ti – признак прохождения переноса через i-й разряд. Очевидно, такой сумматор будет иметь меньшую сложность, чем аналогичный сумматор с одновременным переносом от всех 12-ти разрядов, но будет и менее быстродействующим, т.к. добавляются цепи для формирования Сjгр и Tjгр, в которых будет дополнительная задержка сигнала. Лекция 13 Абстрактный синтез конечных автоматов При синтезе комбинационных схем можно составить таблицу зависимости значения выходного сигнала от комбинации входных. Такая таблица однозначно определяет систему переключательных функций, описывающую работу комбинационной схемы. Составить аналогичную таблицу, описывающую работу конечного автомата (КА), не представляется возможным, т.к. множество допустимых входных слов автомата, вообще говоря, бесконечно. Поэтому для задания КА и используются таблицы переходов и выходов, которые позволяют представить соответствие между бесконечными множествами входных и выходных слов конечными таблицами. В связи с этим, прежде чем приступить к синтезу схемы КА, необходимо составить таблицу переходов и выходов, что не всегда является простым делом особенно в тех случаях, когда алгоритм работы автоматов задан в описательной форме. Для того чтобы упростить и формализовать процедуру построения таблиц переходов и выходов, необходимо ввести такую исходную форму задания автоматов, переход к которой от алгоритмов, сформулированных в описательной форме, не представляет трудностей. Мы рассмотрим один из возможных способов формального задания автоматов, а именно, задание автомата на языке регулярных событий. Представление событий в автоматах В основе рассматриваемого способа задания автоматов, лежит понятие событий, представимых в автоматах. Пусть Y{y1, y2, …, yG} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a0. Тогда каждой букве yj выходного алфавита можно поставить в соответствие множество входных слов Sj (x1, x2,…, xF), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов Sj (x1, x2, …, xF) называют событием, представленным в автомате выходным сигналом yj. Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y1, y2, …, yG}, достаточно разбить множество всех возможных входных слов на G событий S1, S2, …, SG, представленных в автомате выходными сигналами y1, y2, …, yG соответственно. Для частичного автомата необходимо, кроме того, задать множество Sз запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий Sj, можно не пользуясь таблицами переходов и выходов найти реакцию автомата на любое входное слово, для чего достаточно определить  множество каких слов входного алфавита оно входит (т.е. какому событию принадлежит). Соответствие событий буквам выходного алфавита: Событие Буква S1 (x1, x2,…, xF) S2 (x1, x2,…, xF) … SG (x1, x2,…, xF) Sз  (x1, x2,…, xF) y1 y2 … yG –   Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, т.е. строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М. Операции в алгебре событий Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий. Дизъюнкцией событий называют событие S = S1 v S2 v …v SG, состоящее из всех слов, входящих в событияS1, S2, …, SG. Пример. Событие S1 содержит слова x1, x1x1, x2x1, т.е. S1 = (x1, x1x1, x2x1), а S2 = (x2, x1x2). Тогда S = S1 v S2 = (x1, x2, x1x1, x1x2, x2x1). Произведением событий называется событие  , состоящее из всех слов, полученных приписыванием к каждому слову события S1 каждого слова события S2, затем слова события S3 и т.д. Пример. При тех же событиях S1 и S2, = (x1x2, x1x1x2, x2x1x2, x1x1x2, x1x1x1x2, x2x1x1x2). Произведение событий не коммутативно, т.е. . Поэтому следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий   можно сказать, что событие S2 умножено на событие S1 справа, а событие S1 на S2 – слева. Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными. Итерацией события S называется событие {S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности, т.е.: {S} = e v S v SS v SSS v … Пример. S = (x2, x1x2). Тогда {S} = (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …) При синтезе конечных автоматов важнейшую роль играют регулярные события. Любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными. Теорема: Любые регулярные выражения и только они представимы в конечных автоматах. Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений. Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЭВМ. Пусть дан конечный алфавит X = (x1, x2, …, xm). Регулярное событие – это любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операций дизъюнкции, произведения и итерации. Регулярное выражение – любое выражение, составленное с помощью операций дизъюнкции, произведения и итерации. Система основных событий В эту систему мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений на практических занятиях и курсовой работе. Пусть дан алфавит X{x1, x2, …,xm}. 1. Событие, состоящее из всех слов входного алфавита (всеобщее событие): F = {x1 v x2 v …v xm} 2. Событие, содержащее все слова, оканчивающиеся буквой xi: S = {x1 v x2 v …v xi v …v xm} xi = Fxi. 3. Событие, содержащее все слова, оканчивающиеся отрезком слова l1: S = F l1. 4. Событие, содержащее все слова, начинающиеся с отрезка слова l1 и оканчивающиеся на l2: S = l1 F l2. 5. Событие, содержащее только однобуквенные слова входного алфавита: S = x1 v x2 v …v xm. 6. Событие, содержащее только двухбуквенные слова входного алфавита: S = (x1 v x2 v …v xm)( x1 v x2 v …v xm). 7. Событие, содержащее все слова длиной r: S = (x1 v x2 v…v xm)(x1v x2 v…v xm)…(x1 v x2 v…v xm) - r членов. 8. Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих комбинации букв x1x1 и оканчивающихся буквой x2:  S = {x2 v x1 x2}. S = {x2 v x1x2 v x1x1x2 v … v x1x1… x1x2} - (r – 1) членов. Рассмотрим пример составления регулярного выражения. Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно. Окончание чисел фиксируется подачей на вход автомата сигнала xs. Если число, поданное на первый вход автомата, меньше числа, поданного на второй вход, то КА выдает сигнал y1, если больше – то y2, если оба числа равны – то y3. Числа подаются на входы автомата младшими разрядами вперед. На входы автомата сравнения одновременно может поступить одна из четырех комбинаций сигналов 00, 01, 10, 11, которые закодируем следующим образом x00=00, x01=01, x10=10, x11=11. При этом будем считать, что первая цифра каждой комбинации относится к первому входу, а вторая – ко второму входу. Таким образом, входной алфавит автомата включает пять букв X{x00, x01, x10, x11, xs}, а выходной – три буквы Y{y1, y2, y3}: ------------------------- КА ----------à Х{x00, x01, x10, x11, xs} Y{y1, y2, y3}   Два двоичных числа равны, если равны цифры в любых одинаковых разрядах. Поэтому событие, заключающееся в поступлении на вход автомата равных чисел, состоит из всех возможных слов, содержащих буквы x00 и x11. То есть S3 = {x00 v x11} xs. События, представленные в автомате сигналами y1 и y2, можно записать соответственно в виде: S1 = {x00vx01vx10vx11}x01{x00vx11}xs,   S2 = {x00vx01vx10vx11}x10{x00vx11}xs.  События  S1, S2 и S3 не охватывают всего множества слов, которые могут быть записаны в алфавите X{x00,x01, x10, x11, xs}, т.к. в эти события входят только слова, оканчивающиеся буквой xs. Слова, не входящие вS1, S2 и S3, должны быть представлены в автомате пустой буквой e:  . Очевидно, что записанные выражения можно упростить, если входные сигналы 00 и 11 закодировать одной буквой, например xr. Такое кодирование возможно, т.к. КА одинаково реагирует на эти комбинации: S3 = {xr} xs, S1={xrvx01vx10}x01{xr}xs, S2 = {xrvx01vx10}x10{x00vx11}xs,  . Заметим, что одно и тоже регулярное событие может быть представлено различными регулярными выражениями. Поэтому встает задача отыскания таких регулярных выражений, которые позволяют представлять события наиболее простыми формулами. Рассмотрим несколько основных соотношений, которые используются при преобразовании регулярных выражений: 1. S1 v S2 = S2 v S1 – закон коммутативности; 2. (S1v S2) v S3 = S1 v (S2 v S3) = S1 v S2 v S3 – законы ассоциативности; 3.   – законы ассоциативности; 4.   – закон дистрибутивности; 5. {{S}} = {S}; 6.  ; 7. {{S1} v {S2}} = {S1 v S2}; 8. {e} = e; 9. eS = Se = S . Алгоритм синтеза автомата Мура Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x1, x2} и реализующий следующий алгоритм: S1 = x1x2 v x1x1x1, S2 = x1x2x2 v x2x2, Sзапр. = x1 v x2x2x2. При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, это самый простой, хотя и не очень экономный по числу используемых внутренних состояний автомата. Алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова, содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi. Для того, чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2: S1 = | x1 | x2 | v | x1 | x1 | x1 |     1   2     1   3   4 S2 = | x1 | x2 | x2 | v | x2 | x2 |     1   2   5     6   7. Поскольку первая буква второго слова x1x1x1, входящего в S1, также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4. Первые две буквы слова x1x2x2, входящего в S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений. Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать. Для размеченных регулярных выражений составляется отмеченная таблица переходов.  уg е е y1 e y1 y2 e y2 e x j/ai 1 2 3 4 5 6 7 * x1 1 3 * 4 * * * * * x2 6 2 5 * * * 7 * * Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 - 7 вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S1 и S2. Выходным сигналом y1 отмечены состояния 2 и 4, y2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e. Алгоритм синтеза усложняется, если регулярные выражения содержат итерационные скобки. При разметке регулярных выражений различают основные и предосновные места. Очевидно, некоторые места могут быть одновременно основными и предосновными. Все основные места отмечаются различными десятичными числами, при этом всем начальным местам приписывается индекс 0. Затем каждое предосновное место отмечается совокупностью индексов основных мест. В эту совокупность входят индексы внутренних состояний, находясь в которых автомат может принять букву, стоящую справа от предосновного места. Разметка регулярных выражений Разметка регулярных выражений проводится по правилам подчинения мест: 1. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками. 2. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки. 3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками. 4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки. 5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются. 6. В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедлив только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки. Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j. Рассмотрим эти правила на примере синтеза автомата, описываемого следующим регулярным выражением: В этом автомате сигнал y1 выдается после поступления подряд 3-х букв x1, а y2 – после x2, следующей за серией из 3-х и более букв x1. В остальных случаях выдается буква e. Индексы основных мест записываются непосредственно под регулярными выражениями, а индексы предосновных мест располагаются ниже индексов основных мест, под горизонтальной чертой. Выражение имеет 12 основных мест (от 0 до 11). Проведем разметку предосновных мест. В начале определим, какие буквы может принять автомат, если он находится в состоянии 0. Поскольку на вход автомата может поступить любое из трех слов, записанных в итерационных скобках, то индекс 0 распространяется на каждое из трех предосновных мест, расположенных в начале этих слов. Учитывая, что событие, соответствующее выражению, записанному в итерационных скобках, содержит пустое слово е, индекс 0 распространяется на предосновное место, расположенное сразу за скобками. Это означает, что в частном случае ни одно из трех слов, заключенных в итерационные скобки, на вход автомата не поступит и тогда первой буквой, которую принимает автомат, является буква x1, стоящая непосредственно за итерационными скобками. Таким образом, все эти предосновные места подчинены месту с индексом 0. Теперь найдем предосновные места, на которые распространяется индекс 1. Если автомат находится в состоянии 1, то он может принять букву x2, расположенную слева от места 1, так как эта буква находится в итерационных скобках и, следовательно, неоднократно может повторяться во входном слове автомата. Кроме того, в состоянии 1 автомат может принять начальные буквы других слов, расположенных в итерационных скобках, и букву x1, непосредственно следующую за этими скобками. Таким образом, месту с индексом 1 в данном случае подчиняются те же предосновные места, что и месту с индексом 0. Если автомат находится в состоянии 2, то он может принять только букву x2, расположенную справа от места с индексом 2. Поэтому индекс распространяется на единственное предосновное место, являющееся одновременно основным местом 2. Аналогично можно найти подчиненные места других основных мест. По окончании слова, входящего в событие S, автомат переходит в состояние 11, после чего на вход автомата может поступить второе слово этого события S, так как мы считаем, что автомат является автоматом многократного действия. Автоматами многократного действия называются такие автоматы, которые могут неоднократно принимать слова, входящие в события, представленные в автомате. В таких автоматах индекс конечного места распространяется на те же предосновные места, на которые распространяется индекс начального места, т.е. по окончании очередного слова на вход автомата этого слова может поступить вновь. По размеченному регулярному выражению теперь можно составить таблицу переходов автомата. Однако перед построением таблицы целесообразно уменьшить число индексов основных мест, а следовательно и число внутренних состояний автомата. Лекция 14 Минимизация внутренних состояний автомата На первом этапе минимизации внутренних состояний можно пользоваться следующим правилом: • Если несколько предосновных мест отмечено одинаковой совокупностью индексов и справа от этих мест записаны одинаковые буквы, то основные места, расположенные справа от этих букв, можно отметить одинаковыми индексами. В полученном нами выражении основные места 2, 4 и 7 можно отметить общим индексом, так как слева от каждого из этих мест записана буква x1, а предосновные места, предшествующие этой букве, имеют одинаковую совокупность индексов (0, 1, 3, 6, 11). Теперь с учетом этого проведем новую разметку: Проделанную процедуру можно повторить вновь, так как в полученном выражении есть два места (4 и 6), перед которыми стоит одинаковая буква x1, имеющая предосновное место, отмеченное одинаковым индексом 2. После этого получим окончательную разметку: Второй этап минимизации Составим отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x1. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x1. Таких мест в выражении 3. Все основные места, расположенные за этой буквой x1, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x1 переходит в состояние 2. Аналогично сигнал x2 переводит автомат из состояния 0 в состояние 1, так как за предосновным местом, содержащим индекс 0, после буквы x2расположено основное место с индексом 1. Таким же образом определяются переходы автомата их других внутренних состояний. Сигнал y1 выдается после поступления подряд трех букв x1, то есть в состоянии 6, а сигнал y2 – после x2, следующей за серией из трех и более букв, то есть в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов. yg e e e e e e y1 e y2 xj / ai 1 2 3 4 5 6 7 8 x1 2 2 4 2 6 2 7 7 2 x2 1 1 3 1 5 1 8 8 1   Из построенной таблицы видно, что из состояний 0, 1, 3 и 5 автомат сигналами x1 и x2 переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как a0. Введем обозначения: 2 – a1, 4 – a2, 6 – a3, 7 – a4, 8 – a5. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний a3 и a4 под действием входных сигналов х1 и х2 автомат переходит в одинаковые состояния a4 и a5. Но объединять эти состояния нельзя, так как они отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния a0 и а5. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов. yg e e e y1 e y2 xj /ai a0 a1 a2 a3 a4 a5 x1 a1 a2 a3 a4 a4 a1 x2 a0 a0 a0 a5 a5 a0   Второй пример абстрактного синтеза Рассмотрим еще один пример абстрактного синтеза автомата. Найдем таблицу переходов автомата сравнения чисел, функционирование которого заданы следующими регулярными выражениями: Регулярные выражения событий S1 и S2 содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, так как в автоматах многократного действия за словом любого события, например S1, может быть подано слово любого другого события, то есть S1 v S2 v S3. В размеченных выражениях можно объединить места с индексами  4, 6 и 5, 9: По размеченному выражению составим отмеченную таблицу переходов: yg е е y3 е е е е y1 е y2 е е е е xj/ai 1 2 3 4 5 6 7 8 9 1v3 3v6 3v8 * xr 1v3 1 1v3 3 3v6 3v8 6 1v3 8 1v3 1v3 3v6 3v8 * x01 4 * 4 4 4 4 * 3 * 4 4 4 4 * x10 5 * 5 5 5 5 * 5 * 5 5 5 5 * xs 2 2 2 * 7 9 7 2 9 2 2 7 9 * При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например, в событии S3 переход из состояния 0 в состояние 1 происходит под действием сигнала xr, а в S1 под действием этого же сигнала из состояния 0 автомат переходит в состояние 3. Поэтому внутреннее состояние, в которое автомат переходит под действием xr из состояния 0, будем обозначать множеством из двух индексов 1 v 3. Аналогично получается переход из состояний 2, 7 и 9 под действием xr, а также переход из состояния 4 и 5 в состояния 3 v 6 и 3 v 8 соответственно под действием xr. При заполнении таблицы получается свободные клетки там, где переходы в автомате не определенны. Такие клетки будем отмечать звездочкой *, которую следует рассматривать как индекс некоторого внутреннего состояния. Таблица переходов составляется не только для состояний, отмеченных индексами основных мест регулярного выражения, но и для состояний, отмеченных множеством индексов. Для заполнения колонок для таких состояний достаточно образовать дизъюнкцию таких индексов, которые расположены в колонках, отмеченных индексами, входящими в множества. Например, для заполнения колонки 1v3 образуем дизъюнкцию индексов расположенных в колонках 1 и 3. Поскольку состояния 1, 3, 6 и 8 отмечены пустой буквой e, то и состояния 1v3, 3v6, 3v8 также отмечаются буквой е. После построения таблицы проведем второй этап минимизации числа внутренних состояний автомата. Можно объединить состояния, отмеченные индексами: 0 и 1v3, 4 и 3v6, 5 и 3v8. При этом состояния, отмеченные звездочкой, обозначим через 10, а состояния 1v3 – 0, 3v6 – 4, 3v8 – 5.   yg e e y3 e e e e y1 e y2 e xj/ai 1 2 3 4 5 6 7 8 9 10 xr 1 3 4 5 6 8 10 х01 4 10 4 4 4 4 10 4 10 4 10 х10 5 10 5 5 5 5 10 5 10 5 10 xs 2 2 2 10 7 9 7 2 9 2 10   По построенной таблице проведем третий этап минимизации, исключив такие состояния, в которые автомат из нулевого состояния никогда перейти не может. В нашем случае такими состояниями являются 1, 3, 6, 8 и 10. Обозначив оставшиеся состояния 0 – b0, 2 – b1, 4 – b2, 5 – b3, 7 – b4, 9 – b5, получим окончательную таблицу переходов заданного автомата: yg e y3 e e y1 y2 xj /ai b0 b1 b2 b3 b4 b5 xr b0 b0 b2 b3 b0 b0 x01 b2 b2 b2 b2 b2 b2 x10 b3 b3 b3 b3 b3 b3 xs b1 b1 b4 b5 b1 b1 Четвёртый этап минимизации В некоторых случаях после получения отмеченной таблицы переходов автомата возможен четвертый этап минимизации. Правда этот этап не всегда приводит к уменьшению числа состояний и часто является проверочным. Алгоритм этого этапа рассмотрим на примере. Пусть есть автомат, заданный следующей отмеченной таблицей переходов: yg y1 y1 y1 y2 y1 y2 y2 y2 xj /ai 1 2 3 4 5 6 7 x1 2 5 2 2 4 4 5 2 x2 3 1 7 3 5 5 1 7 х3 1 6 1 1 1 1 6 1   Алгоритм минимизации заключается в следующем: 1. Все внутренние состояния разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y1 и y2 и, следовательно, будет две группы, которые мы обозначим буквами a иb. 2. По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0: 3.   Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв: 4. Пользуясь таблицей переходов автомата, вновь отмечают каждое состояние последовательностью букв. Разделение состояний на новые группы продолжают до тех пор, пока новые группы состояний появляться не будут. В нашем случае минимизация заканчивается на втором шаге, так как все состояния, входящие в группы а и с, отмечены одинаковыми последовательностями букв, а группа b иd содержат только по одному состоянию. Все состояния, входящие в каждую из этих групп, можно заменить одним состоянием той же группы. Взяв в качестве представителей групп состояния 0, 1, 3 и 6 и обозначив их символами a0, a1, a2 и a3соответственно, получим следующую таблицу переходов с минимальным числом внутренних состояний.    yg y1 y1 y2 y2 xj /ai a0 a1 a2 a3 x1 a0 a2 a0 a2 x2 a2 a1 a2 a1 x3 a1 a3 a1 a3   Для построения автомата Мили воспользуемся рассмотренным ранее алгоритмом, для чего в каждую клетку совмещенной таблицы переходов и выходов запишем значения выходного сигнала, которым отмечено, находящееся здесь состояние. xj /ai a0 a1 a2 a3 x1 a0/y1 a2/y2 a0/y1 a2/y2 x2 a2/y2 a1/y1 a2/y2 a1/y1 x3 a1/y1 a3/y2 a1/y1 a3/y2 В полученной таблице колонки, помеченные состояниями a0 и a2, a1 и a3 идентичны, что позволяет при минимизации исключить состояния a2 и a3. В результате получаем таблицу переходов и выходов автомата Мили, имеющего два состояния a0 и a1. xj /ai a0 a1 x1 a0/y1 a0/y2 x2 a0/y2 a1/y1 x3 a1/y1 a1/y2 Лекция 15 Вероятностные автоматы Детерминированные автоматы S мы задавали совокупностью из пяти объектов: S(A, X, Y, d, l), где A = {a0, a1, a2, ..., aM} – множество внутренних состояний автомата, X = {x1, x2,…, xF} – множество входных сигналов (входной алфавит), xi – буква входного алфавита, Y = {y1, y2,…, yG} – множество выходных сигналов (выходной алфавит), yg – буква выходного алфавита, d – функция переходов, обеспечивающая однозначный переход автомата в состояние as из состояния аm под действием входного сигнала xf, т.е.   as = d [am, xf], l – функция выходов, определяющая однозначное значение выходного сигнала yg в зависимости от состояния автомата аm и входного сигнала xf,  т.е.    yg  = l [аm , xf].          В работе Поспелова Д.А. «Вероятностные автоматы» рассмотрена более общая модель автомата, а именно: зная состояние автомата аm и входной сигнал xf, мы не можем с вероятностью равной 1 сказать, в каком состоянии окажется автомат в следующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. Однако мы можем указать вероятности наступления соответствующего события, а именно: зная состояние аm и входной сигнал xf, мы можем указать вероятности перехода автомата в состояния {а0, а1, …, аm, …, аM}, а также вероятности появления выходных сигналов  {y1, y2,…,yg, …, yG}, т.е. задаем закон распределения вероятностей. Законы распределения задаются в виде следующих таблиц: am, xf a0 a1 … am … aM a0, x1 р010 р011 … р01m … р01M a0, x2 р020 р021 … р02m … р02M … … … … … … … am, xF р0F0 р0F1 … р0Fm … р0FM a1, x1 р110 р111 … р11m … р11M … … … … … … … am, xf рmf0 рmf1 … рmfm … рmfM … … … … … … … aM, xF рMF0 рMF1 … рMFm … рMFM     am, xf y1 y2 … yg … yG a0, x1 q011 q012 … q01g … q01G a0, x2 q021 q022 … q02g … q02G … … … … … … … am, xF q0F1 q0F2 … q0Fg … q0FG a1, x1 q111 q112 … q11g … q11G … … … … … … … am, xf qmf1 qmf2 … qmfg … qmfG … … … … … … … aM, xF qMF1 qMF2 … qMFg … qMFG   Т.е. в каждом случае имеем закон распределения, заданный в виде гистограмм. Очевидно, т.к. автомат обязательно перейдет в одно из состояний, то ,  , где ,  . Автоматы, в которых зная состояние автомата аm и входной сигнал xf, мы можем указать лишь вероятности перехода в новое состояние и вероятности появления выходных сигналов, т.е. законы распределения, называются вероятностными автоматами (ВА). По аналогии с детерминированными автоматами, можно определить ВА Мили и Мура. ВА, у которых вероятности появления выходных сигналов (закон распределения) зависят лишь от состояний автомата, но не зависят от входных сигналов, называются ВА Мура. Если же вероятности появления выходных сигналов (закон распределения) зависят как от состояний автомата, так и от входных сигналов, имеем автомат Мили. Рассмотрим некоторые частные случаи вероятностных автоматов. Может быть, что выходные сигналы автомата определяются детерминировано, а переходы автомата – случайно. Такие автоматы называются Y -детерминированными вероятностными автоматами. Если состояния определяются детерминировано, то имеем А- детерминированный вероятностный автомат. Если в процессе функционирования автомата законы распределения вероятностей появления выходных сигналов и вероятности перехода автомата в новые состояния не меняются во времени, то такие ВА называются ВА с постоянной структурой. Очевидно, можно рассмотреть общий случай, когда эти законы распределения зависят от времени. Такие автоматы называются ВА с переменной структурой. ВА с переменной структурой в каждый фиксированный такт работы является некоторым обычным ВА, но в период между тактами ВА может изменять свои матрицы переходных вероятностей или таблицы выходных вероятностей, или и то и другое вместе. Часто при построении ВА изменение вероятностей производят по некоторому закону, причем закон зависит от истории функционирования автомата (т.е. зависит от входных сигналов, поданных на него и от выходных сигналов, т.е. реакции автомата). Такие ВА с переменной структурой называются автоматами компенсирующего типа. Их разработке и уделяется основное внимание. В этом случае можно сказать, что ВА работает в некоторой среде, в которую он выдает выходные сигналы и из которой он получает входные (рис. 15.1). Рис. 15.1  Входные сигналы условно можно разделить на поощрения («нештрафы») и наказания («штрафы»). При этом в зависимости от выходного сигнала на вход подается поощрение или штраф. Если в зависимости от этих сигналов менять вероятности перехода автомата из одного состояния в другое, то оказывается, что с течением времени автомат перестраивается таким образом, что он начинает с большой вероятностью получать сигналы поощрения, т.е. он в некотором смысле приспосабливается к той среде, в которой он находится. Проблема организации целесообразного поведения автомата в случайной среде тесно связана со способом изменения вероятностей перехода автомата. Возможно изменение вероятностей перехода автомата по строкам и по столбцам. Рассмотрим У-детерминированный вероятностный автомат. Пусть автомат в некоторый момент времени t находится в состоянии аm, выдал соответствующий этому состоянию выходной сигнал yg и получил на вход сигнал поощрения. Тогда вероятность рmm перехода из состоянии аm в состояние аmувеличиваются на некоторую величину  , а все остальные вероятности в строке уменьшаются  на  /М. Если же автомат получает сигнал штрафа, то вероятность рmm перехода из состоянии аm в состояние аmуменьшаются на некоторую величину  , а все остальные вероятности в строке  на увеличиваются на /М, чтобы сумма вероятностей осталась равной 1. Возможен и другой принцип изменения вероятностей, при котором происходит учет предыстории поведения автомата. Если автомат в момент времени t перешел из состояния аm в состояние ак и в момент времени t + 1 получил сигнал «штраф», то вероятность рmк заменяется на  рmк, где коэффициент больше 0 и меньше 1, а все остальные вероятности в строке изменяются на величину  . Если же получил сигнал «нештраф», то вероятность рmк величину  , а все остальные уменьшаются на величину  . Можно менять вероятности в матрице перехода не только по строкам, но и по столбцам. Например, возможен следующий алгоритм. Если в момент времени t под влиянием входного сигнала xf автомат перешел в состояние аm и в момент времени t + 1 получил сигнал «штраф», то независимо от того, из какого состояния он перешел, все элементы m-го столбца в матрице переходов заменяются на (рmm –  ) или  рmm , а все остальные вероятности изменяются аналогично тому, как это происходило при изменении вероятностей по строкам. Подобные автоматы  уже находят применение при управлении в сложных системах и дают больший эффект там, где раньше работали детерминированные автоматы. Рассмотрим пример, который приводит Д.А. Поспелов – регулирование движения через автомобильный перекресток. Обычно (мы с вами всегда сталкиваемся именно с таким светофором) задают жесткий режим переключения светофоров, при котором длительность включенных сигналов (красного и зеленого) – постоянны. Однако, как показывает практика работы таких светофоров, решение задачи получается малоэффективным, поскольку предполагается, что потоки машин постоянные, стационарные. Можно установить датчики на перекрестке, которые бы подсчитывали число машин (очередь), возникающее в данном направлении при красном свете светофора. Пусть на перекрестке стоит ВА компенсирующего типа, который имеет 2 состояния: включен красный свет вдоль главного направления и включен зеленый свет (рис. 15.2). Каждому состоянию однозначно соответствует выходной сигнал, т.е. автомат У-детерминированный. С датчиков поступают сигналы штрафа и нештрафа. Рис. 15.2 Матрица переходов выглядит следующим образом:  .   Пусть в начале все эти вероятности равны 0,5 и на главном направлении скопилось П1 машин, а на другом – П2. На вход автомата поступает сигнал  = П1 – П2. Пусть   > 0, т.е. на главном направлении больше машин. Тогда если автомат в момент времени t находился в состоянии «зеленом», перешел в состояние «зеленый» и получил сигнал нештраф, то вероятность     рзз (t+1) увеличивается, а вероятность рзк (t+1) уменьшается: рзк (t+1) = рзк (t), рзз (t+1) = 1– рзк (t+1).  Тем самым увеличивается вероятность состояния «зеленое» вдоль главного направления, т.е. автомат подстраивается под обстановку. Заметим, что если потоки одинаковы, то оптимальной является следующая матрица переходов:  . Лекция 16 Структура арифметико-логического устройства (АЛУ) и принцип микропрограммного управления Структура АЛУ состоит из двух основных частей: операционной (ОЧ) и управляющей (УЧ), представленных на рис. 16.1:   Операционная часть (ОЧ) состоит из сумматоров, регистров, счетчиков, устройств приема входных данных, устройств обработки и выдачи результатов обработки, т.е. ОЧ – это цифровой автомат. На вход ОЧ поступают операнды из оперативной памяти, которые участвуют в операции. Отдельные компоненты устройств (сумматор, регистры, шифраторы, мультиплексоры) соединены между собой согласно схемам выполнения предусмотренных операций. Эти соединения выполнены через вентили (логические схемы И). Управляющая часть (УЧ) вырабатывает управляющие сигналы  у1, у2, …, уn, которые поступают на определенные устройства ОЧ для выполнения элементарных операций по ее обработке. Элементарная операция, выполняемая за один такт машинного времени под воздействием одного управляющего сигнала, называется микрооперацией. Примерами микроопераций могут служить следующие элементарные действия: - сброс (очистка) регистра, - занесение числа в регистр, - сдвиг числа в регистре, - подача числа на вход сумматора, - передача результата с сумматора на регистр, - инвертирование числа в регистре и т.д. Один управляющий сигнал (уi) может одновременно поступать в несколько точек управления. Это также одна микрооперация. Реализация  многих арифметических и логических операций требует одновременного выполнения нескольких независимых элементарных действий. В этих случаях формируется несколько управляющих сигналов. Совокупность управляющих сигналов, формируемых и используемых одновременно, составляет микрокоманду (МК):  МК = Y = y1, y2,… yi,…, yn. Для выполнения большинства арифметических операций необходима подача в ОЧ серии микрокоманд, распределенных по времени. Последовательность микрокоманд, определяющих выполнение одной арифметической или логической операции, составляет микропрограмму (МП) выполнения соответствующей операции. Микрокоманды передаются в операционную часть из УЧ, которая служит для формирования МК. МК формируются в УЧ и передаются в ОЧ. В общем случае, микропрограмма может иметь последовательные участки МК и ветвления. Обработка ветвлений (выбор последующей МК) зависит от значений признаков р1, р2,  …, рк   в регистрах операционной части. Примерами таких  могут служить знаковые разряды или сигналы переносов. Признаки из ОЧ поступают в УЧ для обработки ветвлений в микропрограммах при формировании микрокоманд: Р = {р1, р2, …, рj, …, рк}. АЛУ проектируется на выполнение определенной совокупности арифметических и логических операций. Если количество операций, реализуемых АЛУ, больше одной, то УЧ содержит входы кода операции (КОп): (a1, … ak, …am). Код операции настраивает УЧ на выполнение определенной операции. Сигналом начала выполнения операции в АЛУ служит стартовый сигнал Z (смотри рисунок). По стартовому сигналу выполняется одна операция. Как правило, временные этапы выполнения микрокоманд синхронизируются временными сигналами СИ. Устройства обработки данных с синхронизацией выполнения отдельных этапов обработки называются синхронными. Язык микроопераций для представления алгоритмов выполнения арифметических операций Язык микроопераций (ЯМ) предназначен для описания функционирования цифровых устройств на уровне компонент: регистров, счетчиков, сумматоров. Он представляет собой соглашения по простому и наглядному описанию кодов, регистров, шин массивов данных в памяти и микрокоманд. Описание кода, регистров и шин. Описание кода (числа, микрокоманды), регистра и шин (совокупности электрически независимых сигналов для передачи кодов, объединенных общим функциональным назначением) содержит название и разрядный указатель. Название – это набор букв и цифр, начинающийся с буквы. Разрядный указатель – это указатель номеров разрядов кода, регистра или шины. Указатель разрядов в названии может опускаться, если это не приводит к разночтению. Например: · код А= a0, … ai, … an (или A [0÷n]), где аi – двоичные разряды, · регистр команд RGК [0÷31], · отдельные поля регистра  RGК [0÷7], · шина данных  ШД [0÷31] и т.д. Описание массива данных в памяти Массив данных одинаковой длины определяется двумя параметрами: количеством элементов и разрядностью элементов. В соответствии с этим, разрядный указатель  должен указывать размерность массива: количество строк и количество разрядов. Например: - страница данных в оперативной памяти:    СтОП [0÷4095, 0÷31], - i-й элемент массива (слово) в массиве:       СтОП [i, 0÷31], - j-й столбец в массиве                           СтОП [0÷4095, j]. Описание микроопераций Микрооперации осуществляют элементарные операции над данными. Это может быть передача слова в регистр, инвертирование разрядов, сдвиг слова, составление слова. Микрооперация описывается микрооператором и может сопровождаться меткой. Для примера рассмотрим схему получения суммы двух операндов, принятых на входные регистры RGА и RGВ с записью результата в регистр RGС. Микрооперация, соответствующая управляющему сигналу у, может быть представлен как: у: SM [0 ÷ n]: = RGА [0 ÷ n] + RG [0 ÷ n] или проще, как: у: RGС := SM (передача сигналов с выхода сумматора на регистр RGС). При проектировании АЛУ обычно используют запись микропрограммы в виде графа, отдельные вершины которого соответствуют микрокомандам. Граф МП – это совокупность вершин четырех видов  и однонаправленных связей между ними: 1. Начальная вершина имеет только один выход и определяет начало работы МП. 2. Конечная вершина может иметь любое количество входов и определяет окончание работы МП. 3. Операторная вершина может иметь любое количество входов и один выход. Она определяет микрокоманду (МК: Y = {y1, y2, …, yi, …, yn), выполняемую в текущем такте. 4. Условная вершина (вершина проверки условий) может иметь любое количество входов и не менее двух выходов, в зависимости от количества альтернатив условия. Она проверяет выполняемость условия ветвления МП или булева выражения, и по результатам проверки условия перехода передает управление МК одной из операторных вершин или конечной. Многоальтернативное условие       Основные требования к графу МП. 1. В графе МП должна быть только одна начальная и только одна конечная вершины. 2. В каждой вершины в графе МП должен быть хотя бы один путь, ведущий к конечной вершине. 3. Выход каждой вершины в графе МП должен соединяться только с одним входом другой вершины. 4. Вход каждой вершины  должен быть соединен, по крайней мере, с одним выходом другой вершины. 5. Граф МП должен сопровождаться схемой выполнения операции, например, структурной. В схеме выполнения операции должны быть указаны основные функциональные элементы, управляемые точки и связи между ними. Граф микропрограммы является основой для проектирования управляющей части АЛУ. Он проектируется параллельно с проектированием структурной схемы устройства. В процессе совместного проектирования и стыковки производятся коррекции структурной схемы и графа микропрограммы. Итак, УЧ формирует последовательность управляющих сигналов. УЧ – это автомат, функционирование которого определяется МП. Поэтому такой автомат называют микропрограммным автоматом. Проектирование управляющей части АЛУ на основе конечных автоматов. Общие вопросы проектирования устройств управления на основе конечных автоматов Любые устройства управления на основе конечных автоматов (микропрограммные автоматы (МПА)) имеют общую структурную схему, представленную на рис. 16.2. МПА содержит: · схему запуска (СЗ), · элементы памяти, · дешифратор состояний, · комбинационную схему формирования сигналов управления, · комбинационную схему формирования сигналов переходов. Рис. 16.2. Структурная схема микропрограммного автомата Схема запуска Все действия по обработке данных в АЛУ производятся по сигналам управления уi, которые формируются по синхросигналам С. Схема запуска по сигналу пуска Z формирует одиночные последовательности синхросигналов для формирования сигналов управления, которые требуются для выполнения одной операции обработки данных. Схема запуска содержит JK-триггер и элемент И. В исходном состоянии триггер схемы запуска находится в нулевом состоянии и его сигнал на выходе запрещает доступ синхросигналов в МПА. По сигналу пуска Z триггер переходит в единичное состояние и открывается доступ синхроимпульсов в МПА до поступления с комбинационной схемы сигнала окончания операции W на вход сброса K JK-триггера.  В схеме запуска используются или двухтактные триггеры (смотри рисунок) или триггеры с динамическим входом сигнала синхронизации. Триггер запуска должен переходить в новое состояние по заднему фронту сигнала Zили W. Это необходимо для формирования полноценных по длительности управляющих импульсов с первого до последнего. Элементы памяти Элементы памяти используют в качестве регистров состояния конечного автомата. Регистр состояния включен в цепь обратной связи МПА. Состояние автомата определяет выходные сигналы управления, а сигналы управления определяют следующее состояния МПА. Здесь возможен эффект гонок, когда изменения состояния МПА производятся асинхронно. Для устранения эффекта гонок, и чтобы триггеры переключались строго по синхроимпульсам, в качестве элементов памяти используются двухтактные JK-триггеры. Дешифратор состояния При хранении состояния МПА для сокращения оборудования обычно используют двоичное кодирование состояния. Для упрощения процедуры синтеза в структурную схему МПА вводят дешифратор. Дешифратор преобразует код состояния МПА в набор сигналов на соответствующих состоянию шинах. По единичному сигналу на выходе дешифратора судят о состоянии автомата. Комбинационная схема формирования сигналов управления Схема формирует серии сигналов управления. Отдельный сигнал управления yi соответствует отдельной микрооперации (МО). Совокупность сигналов управления в одном такте соответствует микрокоманде (МК). Серия МК, формируемых схемой от сигнала Z до сигнала W, составляет микропрограмму (МП). МПА могут строиться на основе автоматов Мура или Мили. В МПА на основе автомата Мура выходные сигналы являются функцией только состояний автомата. В МПА на основе автомата Мили выходные сигналы являются функцией состояний автомата и сигналов возбуждения элементарных автоматов (на рис. 16.2 подача сигналов возбуждения на комбинационную схему только для автомата Мили показана пунктирными линиями). Комбинационная схема формирования сигналов переходов реализует функцию переходов. Она в каждом такте выдает комбинацию сигналов переходов, под действием которых в регистре состояния автомата фиксируется следующее состояние. Сигналы переходов в автоматах Мили и Мура  являются функциями состояния и сигналов возбуждения. Количество формируемых сигналов переходов и схема формирования (логические выражения) зависят от используемых типов триггеров. На рис. 16.2 представлен вариант схем управляющего автомата с использованием JK-триггеров. Для простейших линейных микропрограмм можно использовать частный случай конечного автомата Мура – распределитель импульсов. Основой распределителя импульсов является счетчик, используемый в качестве регистра состояний. Он реализует линейную смену состояний конечного автомата. Счетчик не нужно проектировать, его можно просто выбрать. При использовании счетчика отпадает необходимость в использовании комбинационной схемы формирования сигналов переходов. Смена состояний производится внутренними цепями самого счетчика. При малом количестве состояний в качестве счетчика можно использовать регистр сдвига. В этом случае дешифратор не используется. Основные этапы проектирования МПА Проектирование МПА заключается в проектировании компонентов структурной схемы, представленной на рис. 16.2. Основными этапами проектирования МПА являются: 1. Проектирование графа микропрограммы. 2. Проектирование структурной схемы устройства. Эти два этапа взаимосвязаны и выполняется параллельно. 3. Выбор типа используемого конечного автомата. При выборе типа конечного автомата следует иметь в виду, что использование распределителя сигналов возможно в ограниченных случаях линейных микропрограмм или микропрограмм с длинными линейными участками и относительно малым количеством ветвлений. Автомат Мили по сравнению с автоматом Мура дает уменьшенное количество состояний, но более сложные комбинационные схемы. 4. Разметка графа микропрограммы и составление графа конечного автомата. Этот этап позволяет определить количество состояний, функции выходов и переходов автомата. 5. Определение параметров регистра состояний и дешифратора состояний. Параметры дешифратора определяются количеством состояний автомата M. Выбор типов триггеров регистра состояний. Сигналы переходов устанавливают следующее состояние автомата. При выборе D-триггеров установка нового состояния определяется только входным сигналом (на каждый триггер по одному). Нулевой сигнал устанавливает нулевое состояние, единичный – единичное состояние. Установка любого состояния производится по синхросигналу. При выборе JK-триггеров (с раздельными входами) активными, т.е. производящими переключение, являются только единичные сигналы. Для переключения триггера в единичное состояние требуется подача единичного сигнала на J-вход, для переключения триггера в нулевое состояние – на K-вход. Так как предусмотрена подача двух сигналов на каждый триггер, общее количество сигналов переходов возрастает, но возрастает и возможность минимизации комбинационных схем за счет совместного использования отдельных логических схем. 6. Кодирование состояний автомата. Кодирование состояний автомата заключается в нумерации состояний. При кодировании следует учитывать переходы из одного состояния в другое. Желательно, чтобы при переходах  изменяло свое значение минимальное количество разрядов в номере состояния автомата. Это уменьшает сложность комбинационных схем формирования сигналов переходов. Если количество состояний автомата не равно степени двух, для минимизации оборудования важен выбор используемых значений номеров состояний автомата. 7. Составление совмещенной таблицы выходов и переходов МПА. Это необязательный этап, который  облегчает проектирование комбинационных схем выходов и сигналов переходов. 8. Проектирование комбинационной схемы выходов. На этом этапе по совмещенной таблице выходов и переходов МПА составляются логические выражения для формирования двоичных сигналов на всех выходных линиях управления (микроопераций yi). 9. Проектирование комбинационной схемы сигналов переходов. На этом этапе по совмещенной таблице выходов и переходов МПА составляются логические выражения для формирования двоичных сигналов переходов на всех выходных линиях управления триггерами регистра состояния. 10. Составление функциональной схемы МПА. На этом этапе по логическим выражениям для формирования двоичных сигналов управления yi и сигналов переходов строится функциональная  схема и с учетом определенных параметров дешифратора и регистра состояния проектируется функциональная схема МПА. 11. Составление принципиальной схемы МПА. На этом этапе по функциональной схеме МПА с учетом выпускаемых промышленностью микросхем строится принципиальная схема МПА. Лекция 17 Разработка структурной схемы операционной части АЛУ Проектирование операционной части АЛУ рассмотрим на примере проектирования специализированного устройства алгебраического сложения/вычитания восьмиразрядных целых чисел со знаком, заданных в прямых кодах. Алгоритм операции использует как сложение, так и вычитание чисел. Для реализации вычитания в примере используется дополнительный код. В минимальном варианте операционная часть должна иметь: · семиразрядный сумматор SM; · два восьмиразрядных регистра RGА и RGВ (для фиксации результата можно использовать регистр одного из операндов); · триггер кода операции/переполнения T&/v (код операции и переполнение используются в разных тактах); · коммутирующие узлы (точки управления) и линии связи. Начальными действиями операции будем считать прием с 9-ти разрядной шины данных кода операции (КО: сложение/вычитание) и операндов(8-ми разрядных чисел: 7 разрядов чисел плюс знак) на входные регистры А и В, а концом – передачу результата операции на шину данных и формирование признака переполнения. Структурная схема ОЧ специализированного устройства алгебраического сложения/вычитания 8-ми разрядных целых чисел со знаком, заданных в прямом коде, приведена на рис. 17.1. Целью проектирования ОЧ АЛУ является оптимальный выбор компонент, точек управления и связей на основе анализа алгоритма выполнения операции. Проектирование структурной схемы – это творческая работа, в которой важно не только знание теории, но и практический опыт разработчика. Выбор и распределение компонент При вычитании чисел с одинаковыми знаками вместо вычитания второго операнда производят его прибавление с инвертированием разрядов и прибавлением единицы в младший разряд. Эти операции можно выполнить одновременно в одном такте. Для этого разряды второго операнда при вычитании подают на входы сумматора с инверсных выходов регистра RGВ, а на вход переносов младшего разряда (SM(р7)) подается единичный сигнал у5. При сложении чисел с одинаковыми знаками передача второго операнда происходит без смены знака и разряды второго операнда подают на входы сумматора в прямом коде. Для возможности подачи на вход сумматора второго операнда как в прямом, так и в дополнительном кодах, в схеме используется мультиплексор MSA, управляемый сигналом у5. Наличие сигнала у5 определяет подачу дополнительного кода, т.е. выполнение операции вычитания, отсутствие у5 – операцию суммирования. Соответственно, регистр RGВ должен иметь как прямые разрядные выходы, так и инверсные. Алгоритм предполагает возможную смену знака результата при вычитании большего операнда из меньшего. В этом случае производится коррекция результата – разряды результата инвертируются и к младшему разряду прибавляется единица. В данном примере для фиксации результата используется регистр не первого, а второго операнда (RGВ). Это сделано для того, чтобы не перегружать схему инверсными выходами и цепями передач с мультиплексорами. Согласно алгоритму подача разрядов первого операнда с RGА (без знака) на сумматор производится только в прямом коде. Если не надо управлять способом передачи информации на комбинационный сумматор, и передаваемая информация используется во всех операциях, то нет необходимости использовать в цепи связи точки управления в виде вентилей. Вентили в цепях связи ставятся для блокировки передачи информации. В данной схеме вентили нужны для блокировки передачи первого операнда в такте коррекции результата с использованием сумматора. Блокировка производится при отсутствии сигнала управления у4. Для разделения цепей приема второго операнда с шины данных и фиксации результатов с выхода сумматора SM(вых) используется второй мультиплексор MSB. Прием второго операнда с шины данных через сумматор производится по сигналам y2 и y6(tз). При подаче на входы сумматора разрядных значений операндов результат на выходах формируется с определенной задержкой на переходные процессы. По этой причине фиксацию результатов производят в конце такта, например, по заднему фронту управляющего сигнала с использованием синхронных триггеров, например, D-триггеров. На структурной схеме такая микрооперация отмечена пометкой tз – (у6(tз)). При заданной элементной базе длительность такта выбирают не меньше максимальной задержки в используемых схемах. При заданном быстродействии (длительности такта) подбирают соответствующую элементную базу. Для фиксации кода операции (a) и возможного переноса схема содержит D-триггер Ta/v (установка переноса производится по сигналу переноса с сумматора, сброс – по сигналу управления у7). В целях упрощения цепей коррекции знака результата, знак сохраняют в D-триггере с индивидуальным входом синхронизации. Инвертирование знака производится передачей значения сигнала с инверсного выхода триггера на его вход. Алгоритм предусматривает сброс переполнения и инвертирование знака результата в одинаковых ситуациях. Поэтому для сброса сигнала переноса и изменения знака результата используется управляющий сигнал  у7. Передача  результата на магистральную шину данных выполняется по сигналу управления у3. Схема содержит три контрольные точки, которые формируют оповещающие сигналы (признаки): · х1 – знак первого операнда и результата, · х2 – знак второго операнда, · х3 – заданный код операции, после использования – перенос из старшего разряда сумматора. Проектирование графа микропрограммы Граф микропрограммы отличается от блок-схемы алгоритма конкретностью указания действий, учетом особенностей работы, используемых логических схем и требований технического задания. Граф микропрограммы является основой для проектирования управляющей части АЛУ. Он проектируется параллельно с проектированием структурной схемы устройства. В процессе совместного проектирования и стыковки производятся коррекции структурной схемы и графа микропрограммы. Граф микропрограммы логического сложения/вычитания целых чисел со знаком в прямом коде представлен на рис. 17.2. Первая микрокоманда графа по сигналу y1 передает первый операнд с шины данных на первый регистр с дублированием знака на триггере знака/переполнения (T&/v). Вторая микрокоманда Y2 по сигналу y2  переключает вход мультиплексора MSB на шину данных  и заносит второй операнд с шины данных ШД с задержкой по заднему фронту сигнала y6(tз): Y2 = y2, y6(tз). Третья микрокоманда Y3   по сигналу y4 передает первый операнд на входы сумматора. Второй операнд при отсутствии сигнала y5. подается на входы сумматора в прямом коде. Фиксация суммы на регистре второго операнда производится по заднему фронту сигнала y6(tз). Переполнение определяется по факту переноса из старшего разряда сумматора. Если единица переноса возникает при сложении, то – это переполнение. Перенос сохраняется  как переполнение в триггере переполнения T&/v:  Y3 = y4, y6(tз).     Четвертая микрокоманда Y4  выполняет следующие действия: · по сигналу y4  передает на входы сумматора первый операнд в прямом коде без знака, · по сигналу y5  передает на входы сумматора второй операнд в дополнительном коде  без знака, · фиксирует сумму на регистре второго операнда по заднему фронту сигнала y6(tз), · фиксирует переполнение  в триггере переноса T&/v. Таким образом, микрокоманда Y4  производит вычитание без знаков  второго оператора из первого с сохранением результата в регистре второго операнда, а переноса — в триггере переполнения: Y4 = y4, y5,y6(tз). Пятая микрокоманда Y5 производит коррекцию знака результата. При выполнении операции вычитания переполнение не возникает. Но перенос из старшего разряда возможен, если |А| £ |В|. Это случай, когда знак результата сформирован неверно. Для нахождения верного результата нужна его коррекция. Коррекция результата заключается в его инверсии (вычитании из нуля): перенос результата. Сигнал переполнения фиксируется в триггере переполнения и проверяется после выполнения операции вычитания. При отсутствии переноса производится коррекция результата: триггер переполнения сбрасывается и производится инвертирование знака результата (y7): Y5 = y7. Это делается для упрощения сохранения знака результата. Априори результату присваивается знак первого операнда (А). Но на магистральную шину данных знак результата будет передаваться со знакового триггера второго операнда. Такая замена возможна, так как известно соотношение знаков. Микрокоманда Y6 изменяет знак результата, формирует дополнительный код результата и сбрасывает сигнал переполнения (у7): Y6 = y5, y6(tз), y7. Микрокоманда Y7 сохраняет результат на шине данных: Y7 = y3. Граф микропрограммы имеет четыре вершины проверки условий: · равенства знаков операндов х1 = х2 , · переноса из старшего разряда сумматора х3. Ниже приводится табл. 17.1 для всех используемых в МП микрокоманд с указанием всех составляющих микроопераций. Таблица 17.1 Микрокоманды устройства алгебраического сложения/вычитания целых чисел со знаком в прямом коде. МК Микрооперации Описание Y1 y1: RGА:= ШД[0÷7]; T/v := RGА [0]. Занесение первого операнда в регистр c дублированием знака в регистр знака/переполнения. Y2 у2:MSB:=ШД[0÷7]; y6(tз): RGВ[0÷7]:=SM(Вых) Переключение мультиплексора на шину данных; Занесение второго операнда в регистр с шины данных позднему фронту сигнала управления. Y3 у4: SM(B):= RGВ[1÷7]; SM(А):= RGА[1÷7]; y6(tз): RGВ[1÷7]:=SM(Вых) T/v := SM(р1). Подача на вход сумматора SM(В) 2-го операнда. Подача на вход сумматора SM(А) 1-го операнда. Подача с выхода сумматора результата на регистр второго операнда и знака на триггер знака/переполнения. Y4 y4: SM(А):= RGА[1÷7]; y5: SM(B):=  ; SM(р7):= 1 y6(tз): RGВ[1÷7]:=SM(Вых) T/v := SM(р1). Подача на вход сумматора SM(А) 1-го операнда Подача на вход сумматора SM(В) 2-го операнда с отрицательным знаком. Подача с выхода сумматора результата на регистр второго операнда и знака на триггер знака/переполнения. Y5 у7: T&v:= 0  RGА[0]:=  Сброс триггера переполнения (T&v) и изменение знака результата Y6 y5: SM(B):=  ; SM(р7):= 1 y6tз: RGВ[1÷7]:= SM(Вых) у7: RGА[0]:= 0   Коррекция результата (перевод результата в дополнительный код с изменением знака). Сброс триггера переполнения (T&v) Y7 у3: ШД[0÷8]:= := RGА[0]|RGВ[0÷7]|T&v Помещение на шину данных результата операции со знаком и признака результата (переполнение). Разработка функциональной схемы операционной части АЛУ Разработка функциональной схемы заключается в выборе конкретных функциональных элементов и соединений. Функциональная схема представлена на рис. 17.3. Входами схемы являются линии шины управляющих сигналов: y1 – y7 (семь линий) и линия кода операции (на вход триггера кода операции/переполнения) из схемы УЧ АЛУ. Кроме этого схема использует магистральную двунаправленную шину данных (семь разрядов числа и знак). Функции триггера кода операции и триггера признака переполнения объединяются в одном триггере кода операции/переполнения (Т/v). Это допустимо, так как код операции используется только в первых тактах, а признак переполнения только на последних тактах выполнения операции. Анализ структурной схемы и графа микропрограммы показывает, что для построения схемы требуется: • Два семиразрядных регистра на D-триггерах. Один из них должен иметь как прямые, так и инверсные выходы. Этот регистр (RGВ) предназначен для приема семи разрядов (с первого по седьмой) второго операнда. Второй регистр (RGА) может не иметь инверсных выходов. Он предназначен для хранения разрядов первого операнда. Для хранения результата можно использовать один из этих регистров. • Два D-триггера для приема и хранения знаков операндов. Один из них должен иметь инверсный выход для реализации инвертирования знака результата при коррекции. • Комбинационный семиразрядный сумматор (SM) с выходом переноса из старшего разряда SM(р1) и входом переноса на младший разряд SM(р7). • Семиразрядный мультиплексор MSA на два входа для коммутации входов сумматораSM(В) на прием разрядов второго операнда (или результата) в прямом или дополнительном кодах. • Семиразрядный мультиплексор MSB на два входа для коммутации входов регистра второго операнда/результата (RGВ) на прием второго операнда  с шины данных (ШД) или с выхода сумматора. • Семиразрядную схему И для разъединения выходов регистра первого операнда с  входами сумматора на время коррекции результата. • Восьмиразрядную схему И (на схеме обозначена как точка управления с входящей стрелкой) для разъединения выходов регистра результата (со знаком) с магистральной шиной данных. Синхронный D-триггер с входом сброса для фиксации кода операции в начале операции и хранения переноса с сумматора в такте суммирования Проектирование МПА на основе автомата Мура Разметка производится по графу микропрограммы. При разметке с каждой операторной вершиной графа отождествляется одно состояние автомата. Начальная и конечная вершины размечаются как начальное (нулевое) состояние автомата. Для примера возьмем граф МП устройства алгебраического сложения/вычитания целых чисел со знаком в прямом коде. Разметка графа МП представлена на рис. 17.4, наименования состояний обозначены в скобках (а0, а1 и т.д.).   Рис. 17.4. Разметка графа МП для автомата Мура Составление графа МПА При составлении графа МПА, как автомата Мура, каждое состояние автомата графически отображается в виде окружности. Взаимное расположение окружностей не имеет принципиального значения. Внутри окружности ставится идентификатор состояния (а0, а1 … аn.) и выходные сигналы (микрокоманды), которые должны формироваться в этом состоянии автомата. Начальным и конечным состоянием является а0. Переходы автомата из одного состояния в последующее на графе обозначаются стрелками. Ветвления в переходах обозначены стрелками с указаниями условий перехода. Состав микрокоманд (Y1 ÷ Y7) соответствует составу микрокоманд графа автомата Мура (рис. 17.5),  . Рис. 17.5. Граф автомата Мура Определение разрядности регистра состояний МПА Согласно графу МПА, проектируемый конечный автомат должен иметь 8 состояний (от нуля до семи). Следовательно, для кодирования любого его состояния достаточно трехразрядного регистра состояний и дешифратора на три входа и восемь выходов. Кодирование состояний автомата Состояния автомата пронумеруем символами a0, a1 и так далее. Нумерацию состояний автомата можно производить в произвольном порядке. Иногда использование произвольной нумерации приводит к упрощению схем формирования управляющих сигналов и сигналов перехода. Составление совмещенной таблицы выходов и переходов МПА Совмещенная таблица выходов и переходов – это запись графа автомата в табличной форме. Таблица содержит список, в котором для каждого перехода в автомате отводится отдельная строка. В строках таблицы фиксируются все возможные переходы из исходных состояний с указанием входных сигналов (сигналов возбуждения) и выходных сигналов (микрокоманд), а также сигналов переходов (условий перехода) для выбранных типов триггеров регистра состояний автомата. Совмещенная таблица выходов и переходов – это массив возможных путей переходов конечного автомата. Она представлена в таблице. Проектирование комбинационной схемы выходов В устройствах управления на основе автомата Мура выходные сигналы   (микрооперации  yi) определяются только текущим состоянием автомата ai. Следовательно, для определения функций выходных сигналов (микрокоманд) нужно отметить все состояния автомата, в которых они должны формироваться (рис. 17.5): y1 = a1, (17.1) y6 = а2 v a3 v a4 v a6, (17.6) y2 = a2, (17.2) y7 = a5, (17.7) y3 = a7, (17.3) y8 = a6, (17.8) y4 = a3 v a4, (17.4) W = a7. (17.9) y5 = a4 v a6, (17.5) Таблица 17.2. Совмещенная таблица переходов  и выходов автомата Мура Исходное состояние Код исходного состояния Состояние перехода Код состояния перехода Входные сигналы (оповещения) Выходные сигналы Сигналы переходов D-триг. Сигналы переходов JK-триг. а0 000 а1 001 – – D3 J3 а1 001 а2 010 – Y1=y1 D2 J2, K3 а2 010 а3 011 Y2=у2, y6(tз) D2, D3 J1 а2 011 а4 100 p D1 J1, K2 , K3 а3 011 а7 111 – Y3= y4, y6(tз) D1, D2,D3 J1 а4 100 а5 101 Y4=y4, у5, y6(tз) D1, D3, J3 а4 100 а6 110 х3 D1, D2 J2 а5 101 а7 111 – Y5=y7 D1, D2,D3 K2 а6 110 а7 111 – Y6=y5, y6(tз),y7 J3 а7 111 а0 000 – Y7=y3 – K1, K2 , K3 Формирование сигнала окончания цикла  W = а7. Проектирование комбинационной схемы сигналов переходов Сигналы переходов являются функциями состояния автомата и входных сигналов. Здесь возможны два варианта: · использование регистра состояния на D-триггерах, · использование регистра состояния на JK-триггерах. Вариант использования D- триггеров Для нахождения функций переходов по таблице для каждого сигнала перехода Di составляют дизъюнкцию из всех комбинаций состояния автомата аi и входных сигналов оповещения xi, а также производят простейшие преобразования уравнений: D1 = p a2 v a3 v  a4 v x3a4 v a5 v a6 (17.10) или учитывая, что  a4 v x3a4 = а4, получим: D1 = p a2 v a3 v a4 v a5 v a6, (17.11) где: р   , (17.12) D2 = a1 v  a2 v a3 v х3a4 v а5 v a6, (17.13) где:    =  ,  (17.14) D3 = a0 v  a2 v  a4 v a5 v a6. (17.15) Вариант использования JK- триггеров Для нахождения функций переходов по табл. 17.2 для каждого сигнала перехода Ji и Kiотмечают все комбинации состояния автомата аi и входных сигналов оповещения xi, а также, возможно, производят простейшие преобразования уравнений: J1 = J2 =  a1, (17.16) J3 = К1 =  a6, (17.17) K2 = a2, (17.18) K3 = a1 v a3, (17.19) W = a2. (17.20) По полученным уравнениям функционирования автомата Мили строятся функциональная, а затем и принципиальная схемы комбинационных частей устройства управления. Построение функциональных и принципиальных схем на основе автомата Мили, аналогично их построению на основе автомата Мура. Минимизация функциональной схемы формирования сигналов управления (микроопераций) и переходов Целями минимизации схем могут быть получение: · минимального схемного оборудования (критерий минимальной стоимости), · минимальных величин задержек сигналов в схемах их формирования (критерий максимальной производительности), · оптимальное соотношение этих критериев. В данном случае нужно учитывать то, что устройства управления являются только небольшой частью исполнительных устройств и большие задержки в них могут значительно снизить эффективность работы всего устройства в целом. По этой причине в качестве критерия минимизации схем устройств управления выбирают минимизацию задержек сигналов в схемах их формирования. Основным способом минимизации оборудования без увеличения задержек является групповое использование. Исходные уравнения функций переходов и выходов составляются в дизъюнктивной форме логических функций. В этой форме переключательная функция представляется в виде дизъюнкций минтермов. При этом различные функции могут использовать одинаковые минтермы. Например, в выражениях для функций разных переходов используются одинаковые минтермы (комбинации сигналов оповещения). Это:  a2 – используется для формирования сигналов переходов D2 и D3  при использовании D–триггеров (выражения 17.13 и 17.15), p a2 – используется для формирования сигналов переходов J1, K2 , K3. Проектирование функциональной схемы формирования сигналов управления (микроопераций) Функциональная схема формирования сигналов управления (рис. 17.6) строится согласно выражениям (17.1) - (17.9).    Рис. 17.6. Функциональная схема формирования сигналов управления на основе автомата МУРа   Проектирование функциональной схемы формирования сигналов переходов Рассмотрим случай использования регистра на основе D-триггеров. Функциональная схема формирования сигналов управления строится согласно выражениям (17.11) - (17.15). Для уменьшения оборудования в комбинационных схемах формирования сигналов переходов D2 и D3 использована общая схема формирования минтерма –  a2. Функциональная схема формирования сигналов переходов на основе автомата МУРа с использованием D-триггеров представлена на рис. 17.7. Рис. 17.7. Функциональная схема формирования сигналов переходов на основе автомата МУРа с использованием D-триггеров Функциональная схема формирования сигналов переходов на основе автомата МУРа с использованием JK-триггеров строится аналогично по выражениям (17.16)–(17.20). Проектирование МПА на основе автомата Мили Разметка графа микропрограммы При использовании МПА на основе автомата Мили, как и в случае автомата Мура, состояния автомата отображаются в виде окружностей, но каждое состояние автомата ассоциируется не с вершинами графа (точками формирования управляющих сигналов), а с переходами через эти вершины. Основные правила разметки графа микропрограммы для автомата Мили: 1. Начальное состояние а0 отмечается на выходе начальной вершины МП. Остальные состояния ставятся после операторной вершины. 2. Выход начальной и вход конечной вершины графа МП соответствуют состоянию а0 графа автомата Мили. 3. Вход вершины, следующей за операторной вершиной графа МП, соответствует определенному состоянию автомата Мили. 4. Отметка  состояния аi ставится на входе вершины ниже стрелок из операторных вершин и выше стрелок из условных вершин. На рис. 17.8 представлен пример, поясняющий правила разметки графа МП при построении графа автомата Мили и на рис. 17.9 – пример построения графа автомата Мили. Первая часть последнего правила применяется для сокращения числа состояний автомата, вторая часть – для исключения пустых тактов. Например, при отметке состояния графа МП ниже стрелки из условной вершины (точка b2) появляется пустой такт (без формирования сигналов управления) при переходе из вершины a0  на вершину b2. Соблюдение указанных правил позволяет для МП со сложными переходами составлять графы автоматов с уменьшенным количеством вершин, т.е. с меньшим количеством состояний. При этом могут использоваться более простой регистр и дешифратор состояний. По размеченному графу МП строится граф автомата Мили.   Состояния автомата Мили обозначены в вершинах графа. Вершины соединены путями возможных переходов. Рядом с каждым переходом (над чертой) указаны комбинации сигналов возбуждения, которые определяют эти переходы. Отсутствие сигналов возбуждения (безусловные переходы) обозначено прочерком. Рядом (под чертой) представлены микрокоманды  Yi (наборы формируемых сигналов управления). Пример проектирования МПА на основе автомата Мили Для примера возьмем граф МП (см. рис. 17.2) устройства алгебраического сложения/вычитания целых чисел со знаком в прямом коде. Разметка графа МП представлена на рис. 17.10, наименования состояний обозначены в скобках (а0, а1 и т.д.). Конкретные наборы микроопераций для каждой микрокоманды представлены в табл. 17.3 (совмещенная таблица выходов и переходов автомата Мили). Рис.17.10. Разметка графа МП алгебраического сложения/вычитания целых  чисел со знаком в прямом коде для построения автомата Мили. Проектирование комбинационной схемы выходов Для определения функций выходных сигналов (микрокоманд) нужно отметить все состояния автомата, в которых они должны формироваться c учетом входных сигналов, а также, если возможно, произвести простейшие преобразования уравнений: y1 = a0, (17.16) y2 = a1, (17.17) y3 = a2, (17.18) y4 = a6, (17.19) y5 =  a6 v a3 х3, (17.20) y6(tз) = а1 v a6 v a3 x3, (17.21) y7 = а3 v  a3 = a3, (17.22) W = a2. (17.23) Проектирование комбинационной схемы сигналов переходов Сигналы переходов являются функциями состояния автомата и входных сигналов (сигналов оповещения с операционной части). Здесь так же, как и для автомата Мура возможны два варианта: · использование регистра состояния на D – триггерах. · использование регистра состояния на JK – триггерах. Вариант использования D – триггеров Для нахождения функций переходов по таблице 17.3 для каждого сигнала перехода Diсоставляют дизъюнкцию из всех комбинаций состояния автомата аi и входных сигналов оповещения xi , а также, возможно, производят простейшие преобразования уравнений: D1 = a1, (17.24) D2 = a1 v (p a6 v   a6) v (a3 X3 + a3  ) или: D2= a1 v a6 v a3, (17.25) D3 =   a6. (17.26) Вариант использования JK – триггеров Для нахождения функций переходов по таблице 17.3 для каждого сигнала перехода Ji и Kiотмечают все комбинации состояния автомата аi и входных сигналов оповещения xi, а также, если возможно, производят простейшие преобразования уравнений: J1 = a1, (17.27) J2 = a1, (17.28) J3 = (p a6 v   a6) = a6, (17.29) K1 =(p a6 v   a6) = a6 = J3, (17.30) K2 = a2, (17.31) K3 = a1 v (a3 X3 v a3  ) = a1 v a3, (17.32) W = a2. (17.33) По полученным уравнениям функционирования автомата Мили строятся функциональная, а затем и принципиальная схемы комбинационных частей устройства управления. Построение функциональных и принципиальных схем на основе автомата Мили аналогично их построению на основе автомата Мура.