Теория автоматов

1. Основные понятия теории автоматов 1.1. Определение цифрового автомата Под цифровым автоматом будем понимать устройство, предназначенное для преобразования цифровой (дискретной) информации, способное переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Отличительные особенности цифровых автоматов заключаются в том, что они имеют дискретное множество внутренних состояний и переход из одного состояния в другое осуществляется скачкообразно. Дискретность информации, преобразуемой в автомате, проявляется в том, что она представляется посредством набора слов конечной длины в некотором алфавите. В частности, в двоичном алфавите, как это принято в ЭВМ, слова представляются в виде цепочки из нулей и единиц. Реальные цифровые автоматы конечны, т. е. множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны. Цифровые автоматы функционируют в дискретные моменты времени, временной интервал Т между которыми называется тактом. В зависимости от того, чем определяется время Т, различают автоматы синхронного и асинхронного действия. Для цифрового автомата синхронного действия входные сигналы действуют в строго определённые моменты времени при Т = const, определяемые генератором синхронизирующих импульсов, в которые возможен переход автомата из одного состояния в другое. Для цифрового автомата асинхронного действия Т  const и определяется моментами поступления входных сигналов, а переход автомата из одного состояния в другое осуществляется при неизменном состоянии входа. Для идеализированных цифровых автоматов, когда не учитываются переходные процессы в элементах схемы автомата, разница в фактических величинах Т для правильного функционирования автомата не имеет значения, поэтому для описания законов функционирования цифровых автоматов вводят абстрактное время, принимающее целые неотрицательные значения t = 0, 1, 2, ... . По степени детализации описания произвольных цифровых автоматов различают автоматы абстрактные и структурные. В соответствии с этими классами различают абстрактную и структурную теорию цифровых автоматов. В абстрактной теории цифровых автоматов изучаются наиболее общие законы их поведения без учёта конечной структуры автомата и физической природы информации. На уровне абстрактной теории понятие “работа автомата” понимается как преобразование входных слов в выходные слова. Можно сказать, что цифровой автомат рассматривается как “чёрный ящик” и основное внимание уделяется его поведению относительно внешней среды. Математической моделью конечного цифрового автомата является абстрактный автомат, определяемый как шестикомпонентный кортеж S = {A, z, w, , , a1}, у которого: 1) A = {a1, ..., am, ..., aM} - множество состояний (алфавит состояний); 2) Z = {z1, ..., zf, ...,zF} - множество входных сигналов (входной алфавит); 3) W = {w1, ...,wg, ...,wG} - множество выходных сигналов (выходной алфавит); 4) функция переходов  определяет правила перехода автомата из одного состояния в другое в зависимости от значений входных сигналов и состояния автомата:  (a, z); 5) функция выходов  определяет правила формирования выходных сигналов автомата:  (a, z); 6) a1 - начальное состояние автомата (a1  A). Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называют буквами, а конечная упорядоченная последовательность букв ‑ словом в данном алфавите. Пустое слово (последо­вательность нулевой длины) будем обозначать буквой e. Автомат имеет один вход и один выход (рис.1.1), и работает в некотором идеализированном дискретном времени, принимающим целые неотрицательные значения t = 0, 1, 2, ... . Рис. 1.1. Абстрактный автомат В каждый момент t дискретного времени автомат находится в некотором состоянии а(t)  A, причём в начальный момент t = 0 он всегда находится в начальном состоянии a(0) = a1. Будучи в момент времени t в состоянии a(t), автомат способен воспринимать на своём входе сигнал z(t)  Z. В соответствии с функцией выходов в этот же момент времени он выдает выходной сигнал w(t)  W и в следующий момент времени (t+1) согласно функции переходов перейдёт в состояние a(t+1)  A. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), ... – входное слово, то на выходе автомата будут после­до­вательно появляться буквы выходного алфавита w(0), w(1), w(2), ...– выходное слово. Относя к каждому входному слову, соответствующее ему выходное слово, получаем отображение, индуцированное абстрактным автоматом. Термин “абстрактный” используется в связи с идеализированным дискретным временем, а также потому, что в этой модели абстрагируются от реальной физической природы входных и выходных сигналов, рассматривая их как буквы некоторого алфавита. Исходя из изложенного можно отметить, что если два абстрактных автомата с общим входным и выходным алфавитом индуцируют одно и то же отображение множества слов во входном алфавите во множество слов в выходном алфавите, то такие автоматы эквивалентны. Структурный цифровой автомат учитывает структуру входных и выходных сигналов, а также его внутрен­нее устройство на уровне структурных схем. Это означает, что структурная теория цифровых автоматов изучает общие приёмы построения структурных схем автоматов на основе элементарных автоматов. 1.2. Варианты цифровых автоматов На практике наибольшее распространение получили два класса автоматов - автоматы Мили и Мура, названные по имени впервые исследовавших эти модели американских учёных G.H. Mealy и E.F. Moore. Автомат Мили. Закон функционирования автомата Мили задаётся уравнениями а(t+1) =  (a(t),z(t)); w(t) =  (a(t),z(t)); (1.1) a(0) = a1, t = 0,1,2, ... . Автомат Мура. Закон функционирования автомата Мура задаётся уравнениями. a(t+1) =  (a(t),z(t)); w(t) =  (a(t)); (1.2) a(0) = a1, t = 0,1,2, ... . Как видно из уравнений (1.1) и (1.2) эти автоматы различаются способом определения выходного сигнала. В автомате Мили функция  определяет выходной сигнал в зависимости от состояния автомата и входного сигнала в момент времени t, а в автомате Мура накладываются ограничения на функцию , заключающиеся в том, что выходной сигнал зависит только от состояния автомата и не зависит от значения входных сигналов. Отметим важное отличие в функционировании этих автоматов. Выходные сигналы автомата Мура отстают на один такт от выходных сигналов автомата Мили, эквивалентного ему. Совмещённая модель автомата (С - автомат). Под абстрактным С - автоматом понимают математическую модель цифрового устройства, определяемую восьмикомпонентным вектором S = {A, Z, W, U, , 1, 2, a1}, где А = {а1, ..., аМ} – множество состояний; Z = {z1, ..., zF} – входной алфавит; W = {w1, ..., wG} – выходной алфавит автомата Мили; U = {u1, ..., uH} – выходной алфавит автомата Мура;  = (а, z) – функция переходов автомата; 1 – функция выходов автомата Мили; 2 – функция выходов автомата Мура; а1  А - начальное состояние автомата. Абстрактный С - автомат можно представить в виде устройства (рис.1.2) с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Рис.1.2. Абстрактный С - автомат Отличие С - автомата в том, что он одновременно реализует две функции выходов 1 и 2 , каждая из которых характерна для модели Мили и модели Мура в отдельности. Закон функционирования С - автомата можно описать уравнениями: а(t + 1) =  (а(t), z(t)); w(t) = 1 (a(t), z(t)); (1.3) u(t) = 2 (a(t)); a(0) = a1; t = 0,1,2, ... . Выходной сигнал uh = 2 (am) выдаётся всё время, пока автомат находится в состоянии am. Выходной сигнал wg = 1(am, zf) выдаётся во время действия входного сигнала zf при нахождении автомата в состоянии am. Очевидно, что от С - автомата легко перейти к автоматам Мили и Мура с учетом возможных сдвигов выходных сигналов на 1 такт, ана­логично тому, как возможен переход от автомата Мили к автомату Мура и наоборот. Практически много реальных автоматов работает по модели С -автомата. Автомат без памяти (комбинационная схема). Алфавит состояний такого автомата содержит единственную букву, поэтому понятие функции переходов вырождается и становится ненужным для описания работы автомата. Автомат задается тремя объектами: Z , W, . Функция выходов принимает вид w (t) =  (z (t)), (1.4) т.е. выходной сигнал в данном такте зависит только от входного сигнала того же такта и никак не зависит от ранее принятых сигналов. Такое преобразование выполняется комбинационной логической схемой, в которой каждой входной комбинации соответствует определенная выходная комбинация. Описание работы таких схем осуществляется с использованием таблиц истинности и булевых функций. Автономный автомат. В таком автомате входной алфавит состоит из одной буквы. Автомат задается четырьмя объектами: А ,W, ,  с возможным выделением начального состояния а1. Функции переходов и выходов имеют вид a (t+1) =  (a(t)); w (t) =  (a(t)). (1.5) Эта пара выражений однозначно определяет единственную выходную последовательность, выдаваемую автоматом, и последовательность состояний. w(1) w(2) w(3) ... a(1) a(2) a(3) ... (1.6) Если автономный автомат конечен и число его состояний равно к, то среди значений а(1), а(2), ..., а(к) найдутся повторяющиеся состояния. Следовательно, каждая из последовательностей (1.6) окажется периодической с длиной периода не больше числа состояний автомата и, возможно, с некоторым предпериодом. Автономные автоматы используются для построения генераторов периодических последовательностей, генераторов синхросерий и в других задающих устройствах, применяемых в цифровой технике. Автомат без выхода. В таком автомате выходной алфавит содержит только одну букву. Автомат задается тремя объек­тами: А, Z, . Из функций, задающих поведение автомата, со­храняется лишь функция переходов a (t+1) =  (a(t), z(t)). Поведение автомата без выхода не может быть охарактеризовано в терминах операторов (отображений), перерабатывающих входные слова в выходные. Вместо этого можно было бы рассматривать операторы, перерабатывающие входные последовательности в последовательности внутренних состояний. Однако удобнее рассматривать поведение такого автомата, задавая настройку его путем выделения начального состояния и множества финальных состояний. После такой настройки автомат может рассматриваться как устройство, воспринимающее вопросы (входные последовательности) и выдающее ответы "да" или "нет" в зависимости от того, принадлежит ли слово интересующему нас языку или нет. Если после подачи на вход слова автомат окажется в одном из финальных состоянии, то ответ утвердителен, в противном случае - отрицателен. В лингвистической интерпретации вопросы, задаваемые автомату, приобретают следующий смысл: является ли данная цепочка символов грамматически правильным предложением в рассматриваемом языке или нет. Если поведение автомата без памяти и автономного автомата сравнительно просто, то поведение автомата без выхода оказывается столь же разнообразно, как и поведение автомата с выходом. Это следует из того, что из двух функций, задающих поведение автомата, функция переходов является наиболее информативной. Управляющие и операционные автоматы. По функциональному назначению цифровые автоматы можно подразделить на два класса: управляющие и операционные. Такое подразделение отражает структуру и функции любого устройства ЭВМ, предназначенного для обработки цифровой информации и называемого операционным устройством. Каждое такое операционное устройство можно представить моделью В.М. Глушкова, состоящей из двух тесно взаимодействующих между собой блоков (рис.1.3), один из которых выполняет функции операционного автомата (ОА), а другой - управляющего автомата (УА). Рис.1.3. Обобщенная структура операционного устройства На рис.1.3 представлена обобщенная структура произвольного операционного устройства, где D1 и D2 - шины, по которым поступает исходная информация и результаты ее обработки соответственно; Х-шины, по которым поступают сигналы, характеризующие состояние ОА (например, отрицательный результат, переполнение сумматора и т.д.). Эти сигналы часто называет осведомительными; Y-шины, по которым поступают управляющие сигналы из УА на ОА в соответствии с алгоритмом выполняемой в ОА операции; g-шины, по которым поступают сигналы, определяющие выполняемую операцию; СС - стартовый сигнал пуска операционного устройства; КР-сигнал, характеризующий конец работы алгоритма. Таким образом, можно отметить, что ОА реализует действия над исходной информацией (словами), т.е. является исполнительной частью операционного устройства, а управляющий автомат управляет работой ОА, т.е. вырабатывает необходимые последовательности управляющих сигналов в соответствии с алгоритмом выполняемой операции. Управляющие автоматы используются не только в операционных устройствах вычислительной техники в системе УА-ОА, но и в разнообразных системах автоматики по управлению технологическими процессами и объектами, которые обобщенно можно назвать объектами управления (ОУ). В этом случае УА, в соответствии с алгоритмом функционирования ОУ и в зависимости от значений осведомительных сигналов о состоянии ОУ, поступающих от датчиков ОУ, и возможных внешних сигналов, вырабатывает и подает на исполнительные механизмы ОУ последовательность управляющих сигналов, обеспечивающих выполнение операций или процедур, предусмотренных целями управления. Для сложных систем управления, когда требуется выпол­нять большой объем работ по обработке информации о состоянии ОУ и выработки управляющих воздействий на ОУ в зависимости от целевой функции управления, в качестве УА могут выступать ЭВМ соответствующего класса. Микропрограммные автоматы. Управляющий автомат, реализующий микро­программу выполнения операции обработки информации, часто называют микро­программным автоматом (МПА). Это вытекает из следующей интерпретации взаимодействия ОА и УА в процессе выполнения каких-либо операций по обработке информации: а) Любая операция, реализуемая операционным устройством, рассматривается в виде последовательности элементарных неделимых актов обработки информации, выполняемых в течение одного такта автоматного времени (одного шага алгоритма), называемых микрооперациями. Множество микроопераций и сигналов, инициирующих их выполнение, обозначают одними и теми же символами, кото­рые составляют выходной структурный алфавит УА Y = {y1, y2, ..., yN}. В случае, если несколько микроопераций реализуются в ОА одновременно, то это подмножество микроопераций называют микрокомандой. б) Для управления порядком следования микрокоманд используются логические условия (ЛУ), которые в зависимости от результатов преобразования информации в ОА могут принимать значения 1 или 0. Множество ЛУ (осведомительных сигналов) обозначают символами, которые составляют входной структурный алфавит X = {x1, x2, ..., xL}. в) Последовательность выполнения микрокоманд, определяемая функциями перехода УА, записывается в виде алгоритма, представленного в терминах микроопераций и ЛУ и называемого микропрограммой. В качестве начального языка для описания микропрограмм выполнения операций чаще всего используется язык операторных схем алгоритмов ГСА и ЛСА. Микропрограммные автоматы с жесткой и программируемой логикой. Управляющие микропрограммные автоматы аппаратно могут быть реализованы на основе так называемой жесткой логики и программируемой логики. Автомат с жесткой логикой строится на базе использования логи­ческих элементов (ЛЭ) и элементов памяти (элементарных автоматов с двумя внутренними состояниями). Изменить алгоритм работы такого автомата нельзя, не изменяя соединений между элементами. Для таких автоматов характерны высокое быстродействие, определяемое только задержками используемых ЛЭ и элементов памяти, пропорциональный рост объема оборудования в зависимости от сложности реализуемого алгоритма и малые удельные затраты оборудования при реализации, простых микропрограмм. Однако автоматы с жесткой логикой не обладают гибкостью при внесении изменений в алгоритм их функционирования, необходимость в которых особенно часто возникает в процесс проектирования цифровых устройств. Для автомата с программируемой логикой алгоритм работы записывается в управляющую память, в виде микропрограммы, состоящей из микрокоманд. Микрокоманда содержит информацию о микрооперациях, которые должны выполняться в данном такте работы устройства, и об адресе в управляющей памяти следующей микрокоманды, которая будет выполняться в следующем такте. Такие автоматы отличаются большой регулярностью структуры и возможностью оперативного внесения изме­нений в алгоритм работы проектируемого устройства. 1.3. Способы задания цифровых автоматов Можно выделить два класса языков для описания функционирования ЦА: - начальные, - стандартные или автоматные. Начальные языки описывают функцию переходов и выходов в неявном виде. К ним относятся язык регулярных выражений алгебры событий (РВАС), язык исчисления предикатов, язык логических схем алгоритмов (ЛСА), язык граф-схем алгоритмов (ГСА), а также языки ГСАП и ЛСАП, предназначенные для описания параллельных алгоритмических процессов. Задание ЦА на начальных языках будет рассмотрено в главе 5. Стандартные или автоматные языки задают функции переходов выходов в явном виде. К ним относятся таблицы, графы, матрицы переходов и выходов и их аналитическая интерпретация. Для того, чтобы задать автомат, необходимо описать все компоненты вектора S = (A, Z, W, , , a1). При табличном способе задания автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию  (табл.1.1.), таблица выходов функцию  (табл.1.2.). Каждому столбцу табл.1.1 и 1.2 поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца am и строки zf в табл.1.1 записывается состояние as , в которое должен перейти автомат из состояния am , под действием входного сигнала zf , т.е. as =  (am, zf). На пересечении столбца am и строки zf в табл.1.2 записывается выходной сигнал wg , выдаваемый автоматом в состоянии am при поступлении на его вход сигнала zf , т.е. wg = (am, zf). Таблица 1.1 Таблица 1.2 a1 a2 a3 a4 a1 a2 a3 a4 z1 a2 a2 a1 a1 z1 w1 w1 w2 w4 z2 a4 a3 a4 a3 z2 w5 w3 w4 w5 Для указанных таблиц А = {a1, a2, a3, a4}; Z = {z1, z2}; W = {w1, w2, w3, w4, w5}. Автомат Мили может быть задан также одной совмещенной таблицей переходов и выходов (табл.1.3), в которой каждый элемент as/wg, записанный на пересечении столбца am и строки zf, определяется следующим образом: as =  (am, zf); wg =  (am, zf). Таблица 1.3 Таблица 1.4 a1 a2 a3 a4 w3 w2 w3 w1 z1 a2/w1 a2/w1 a1/w2 a1/w4 a1 a2 a3 a4 z2 a4/w5 a3/w3 a4/w4 a3/w5 z1 a1 a3 a1 a4 z2 a2 a4 a4 a1 Автомат Мура задается одной отмеченной таблицей переходов (табл.1.4), в которой каждому столбцу приписаны не только состояния am , но еще и выходной сигнал wg , соответствующий этому состоянию, где wg =  (am). Для табл. 1.4 A = {a4, a2, a3, a4}; Z = {z1, z2}; W = {w1, w2, w3}. Одним из преимуществ этого способа задания является то, что любая таблица переходов и выходов задает конечный автомат. При этом должны удовлетворяться два условия : - условие однозначности (детерминированности), которое означает, что для любой пары am zf задано единственное состояние перехода as и единственный выходной сигнал wg , выдаваемый на переходе. - условие полной определенности, которое означает, что для всех возможных пар am zf всегда указано состояние и выходной сигнал. Автомат называется неполностью определенным или частичным, если либо функция  определена не на всех парах ( am zf )  A x Z, либо функция  определена не на всех указанных парах в случае автомата Мили и на множестве не всех внутренних состояний для автомата Мура. Для частных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк. Граф автомата - это ориентированный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am в вершину as , задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал zf  Z, вызывающий данный переход : as =  (am, zf). Для графа автомата Мили выходной сигнал wg  W, формируемый на переходе, записывается в конце дуги, а для автомата Мура рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Графы автоматов Мили и Мура, построенные по табл.1.3 и 1.4 приведены соответственно на рис.1.4. а, б. Рис.1.4 Применительно к графу условия однозначности и полной определенности будут заключены в следующем: - не существует двух ребер с одинаковыми входными пометками, выходящих из одной и той же вершины; - для всякой вершины am и для всякого входного сигнала zf имеется такое ребро, помеченное символом zf , которое выходит из am. При задании графов с большим числом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать этот граф в виде списка - таблицы переходов. Прямая таблица переходов - таблица в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл.1.5 - прямая таблица переходов автомата Мили, построенная по графу, приведенному на рис.1.4.а. В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала записываются все переходы в первое состояние, затем во второе и т.д. Табл.1.6 - обратная таблица переходов автомата Мура, построенная по графу, приведенному на рис.1.4,б. Как и граф таблицы переходов должны удовлетворять условиям однозначности и полноты переходов. В некоторых случаях для задания автомата используются матрицы переходов и выходов, которые представляют собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из am под действием zf в as с выдачей wg , то на пересечении строки am и столбца as записывается пара zf wg. Ясно, что не всякая матрица задает автомат. Как граф и таблица переходов и выходов она должна удовлетворять условиям однозначности и полноты переходов. Системы канонических уравнений (СКУ) и системы выходных функций (СВФ) являются аналитической интерпретацией таблиц переходов и выходов или графов автоматов. СКУ – определяет функции переходов ЦА, а СВФ – определяет функции выходов ЦА. Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние: (1.7) Для сокращения записи СКУ и СВФ будем в дальнейшем везде, где это возможно, опускать знаки конъюнкции и времени t в правой части уравнений типа (1.7). Для автомата Мили, заданного табл.1.1 запишем СКУ и СВФ (1.8 и 1.9. соответственно): a1(t+1) = z1a3  z1a4 = z1 (a3  a4); a2(t+1) = z1a1  z1a2 = z1 (a1  a2); (1.8) a3(t+1) = z2a2  z2a4 = z2 (a2  a4); a4(t+1) = z2a1  z2a3 = z2 (a1  a3). w1(t) = z1a1  z1a2 = z1 (a1  a2); w2(t) = z1a3; (1.9) w3(t) = z2a2; w4(t) = z1a4  z2a3; w5(t) = z2a1  z1a4 = z2 (a1  a4); 1.4. Связь между автоматами Мили и Мура Для любого автомата Мили можно построить эквивалентный ему автомат Мура и, обратно, для любого автомата Мура можно построить эквивалентный ему автомат Мили. Рассмотрим преобразование автомата Мили в автомат Мура. Пусть задан автомат Мили S = (A, Z, W, , , a1), построим автомат Мура S / = (A /, Z /, W /,  /,  /, a1 /), у которого Z / = Z; W / = W. Для определения множества A / необходимо выполнить расщепление состояний автомата Мили исходя из следующего. Если автомат Мили при переходе в некоторое состояние as может выдавать в разные моменты времени один из к выходных сигналов из алфавита W , то такое состояние as должно быть расщеплено на к состояний. То есть число элементов в множестве As равно числу различных выходных сигналов на дугах автомата S, входящих в состояние as : As = {(as, w1), (as, w2), (as, w3), ..., (as, wk)} (рис.1.5). Множество состояний автомата S / получим как объединение множеств As A /, где M - число состояний в автомате Мили S. Такое расщепление состояний автомата Мили необходимо потому, что все состояния эквивалентного ему автомата Мура должны быть отмечены только одним выходным сигналом из алфавита W. Функцию переходов  / и выходов  / определим следующим образом. Если в автомате Мили S был переход  (am, zf) = as и при этом выдавался выходной сигнал  (am, zf) = wg, то в автомате Мура S / (рис.1.6) будет переход из множества состояний Am, порождаемых am, в состояние (as, wg) под действием того же входного сигнала zf. Рис.1.6. Иллюстрация перехода от автомата Мили к автомату Мура В качестве начального состояния автомата Мура можно взять любое из состояний множества A1, порождаемого начальным состоянием a1. Пример 1.1. Преобразовать автомат Мили, изображенный на рис.1.4,а, в автомат Мура. Решение. Для автомата Мура Z / = Z = {z1, z2}; W / = W = {w1, w2, w3, w4, w5}. Построим множество А / для чего найдем множества пар порождаемых каждым состоянием автомата Мили S. Каждую пару обозначим символами b1, b2, ... : A1 = {(a1, w2),(a1, w4)} = {b1, b2}; A2 = {(a2, w1)} = {b3}; A3 = {(a3, w3),(a3, w5)} = {b4, b5}; A4 = {(a4, w4),(a4, w5)} = {b6, b7}. A / = {b1, b2, b3, b4, b5, b6, b7}. Для определения функции  / с каждым состоянием вида (as, wg), представляющим собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:  /(b1) = w2;  /(b2) =  /(b6) = w4;  /(b3) = w1;  /(b4) = w3;  /(b5) =  /(b7) = w5. Поясним построение функции  /. Так как в автомате Мили S есть переход из состояния a1 под действием сигнала z1, в состояние a2 с выдачей w1, то из множества состояний A1 = {b1, b2}, порождаемых а1 в автомате S / должен быть переход в состояние (a2, w1) = b3 под действием сигнала z1. Аналогично из состояний множества A1 = {b1, b2} должен быть переход в состояние (a4, w5) = b7 под действием сигнала z2 и т.д. В качестве начального состояния можно выбрать одно из состояний, порождаемых а1, например b1. На рис.1.7 приведен граф автомата Мура S /, эквивалентного автомату Мили S. Рис.1.7 Рассмотрим теперь переход от произвольного автомата Мура к эквивалентному ему автомату Мили. Этот переход при графическом способе задания иллюстрируется рис.1.8: выходной сигнал (wg), записанный рядом с вершиной (as), переносится на все дуги, входящие в эту вершину. Рис.1.8. Иллюстрация перехода от автомата Мура к автомату Мили При табличном методе задания выполняется преобразование отмеченной таблицы переходов исходного автомата Мура. При этом в совмещенную таблицу переходов автомата Мили вместе с состояниями записываются отмечающие их выходные сигналы. Затем выполняется минимизация числа состояний автомата Мили. 1.5. Минимизация полностью определенных автоматов 1.5.1. метод Ауфенкампа и Хона Основная идея этого метода состоит в разбиении всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замена каждого класса эквивалентности одним состоянием. Получающийся в результате минимизации автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата. Состояния и являются эквивалентными (am  as), если  am,  =  as,  для всевозможных входных слов . Состояния am и as k - эквивалентны (am  as), если  am,  =  as,  для всевозможных слов длины k. Минимизация автомата Мили Алгоритм минимизации автомата Мили S = {A, Z, W, , , а1} состоит из следующих шагов : 1. Находим последовательные разбиения  1,  2, ...,  k,  k+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что  k =  k+1 . Одноэквивалентными будут состояния с одинаковыми столбцами в таблице выходов. Состояния будут двухэквивалентными, если они одноэквивалентны и под действием одинаковых входных сигналов попадают в одинаковые одноэквивалентные классы. 2. В каждом классе эквивалентности разбиения  выбирается по одному состоянию, в результате чего полу­чаем множество A  состояний минимального автомата S  = { A , Z, W,   ,  , } эквивалентного автомату S. 3. Для определения функции переходов    и функции выходов    автомата S  в таблице переходов и выходов вычёркиваются столбцы, соответствующие не вошедшим в A  состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные. 4. В качестве начального состояния выбирается состояние, эквивалентное состоянию a1. В частности, удобно за принимать само состояние a1. Пример 1.2. Минимизировать полностью определённый автомат Мили S1, заданный таблицами переходов и выходов (табл.1.8 и 1.9). Решение. 1. По таблице выходов (табл.1.9) находим разбиение 1 на классы одноэквивалентных состояний, объединяя в одноэквивалентные классы одинаковые столбцы в таблице выходов:  1 = {B1, B2} = {{ а1, а2, а5, а6},{ а3, а4}} . Для сокращения числа скобок будем использовать надчёркивания, а элементы множества под чертой разделять точками.  1 = {B1, B2} ={}. Строим таблицу  1 (табл.1.10), заменяя состояния в таблице переходов исходного автомата (табл.1.8) соответствующими классами одноэквивалентности. Таблица 1.10 Разбиение  1 состояний автомата S B1 B2 а1 а2 а5 а6 а3 а4 z1 B2 B2 B1 B1 B2 B2 z2 B1 B1 B1 B1 B1 B1 По табл.1.10 получим разбиение  2 на классы 2-эквивалентных состояний (табл.1.11):  2 = {C1, C2, C3} = {}. Таблица 1.11 Разбиение  2 состояний автомата S C1 С2 С3 а1 а2 а5 а6 а3 а4 z1 C3 C3 C2 C2 C3 C3 z2 C2 C2 C1 C1 C2 C2 Разбиение  3 получаем аналогично (табл.1.11):  3 = {D1, D2, D3} = {} , оно полностью совпадает с  2 Процедура завершена. Разбиение  3 =  2 =  есть разбиение множества состояний автомата Мили S1 на классы эквивалентных между собой состояний. 2. Из каждого класса эквивалентности произвольно выбираем по одному состоянию: A  = {а1, а3, а6}. 3. Строим таблицы переходов и выходов минимального автомата (табл.1.13 и 1.14). Минимизация автомата Мура При минимизации полностью определённых автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы. 0-эквивалентными являются одинаково отмеченные состояния. Если два состояния автомата Мура 0-эквивалентны и под действием одинаковых входных сигналов попадают в 0-эквивалентные состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности для автомата Мура определяются аналогично рассмотренному выше для автомата Мили. Пример 1.3. Минимизировать полностью определённый автомат Мура S2, заданный отмеченной таблицей переходов (табл.1.15) Таблица 1.15 w1 w1 w3 w3 w3 w2 w3 w1 w2 w2 w2 w2 а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 z1 а10 а12 а5 а7 а3 а7 а3 а10 а7 а1 а5 а2 z2 а5 а7 а6 а11 а9 а11 а6 а4 а6 а8 а9 а8 Решение. 1. По таблице 1.15 находим разбиение  0 на классы 0-эквивалентных состояний, отыскивая одинаково отмеченные состояния  0 = {A1, A2, A3} = {} . Строим таблицу  0 (табл.1.16), заменяя состояния в таблице переходов (табл.1.15) соответствующими классами 0-эквивалентности. Таблица 1.16 Разбиение 0 состояний автомата S2 A1 A2 A3 а1 а2 а8 а6 а9 а10 а11 а12 а3 а4 а5 а7 z1 A2 A2 A2 A3 A3 A1 A3 A1 A3 A3 A3 A3 z2 A3 A3 A3 A2 A2 A1 A2 A1 A2 A2 A2 A2 По табл.1.16 получим разбиение  1 на классы 1-эквивалентных состояний (табл.1.17):  1 = {B1, B2, B3, B4} = {} . Таблица 1.17 Разбиение  1 состояний автомата S2 B1 B2 B3 B4 а1 а2 а8 а6 а9 а11 а10 а12 а3 а4 а5 а7 z1 B3 B3 B3 B4 B4 B4 B1 B1 B4 B4 B4 B4 z2 B4 B4 B4 B2 B2 B2 B1 B1 B2 B2 B2 B2 Из табл.1.17 видно, что  2 =  1 = . То есть поиск классов эквивалентности завершён. 2. Из каждого класса эквивалентности произвольно выбираем по одному элементу: A  = { а1, а6, а10, а3}. 3. Строим отмеченную таблицу переходов минимального автомата S2 (табл.1.18). Таблица 1.18 w1 w3 w2 w2 а3 а1 а6 а10 z1 а10 а3 а3 а1 z2 а3 а6 а6 а1 1.5.2. Минимизация цифровых автоматов с помощью треугольной таблицы Рассмотрим алгоритм минимизации состояний автоматов с помощью треугольной таблицы, предложенный М.Поллом и С.Ангером [3]. По таблицам переходов и выходов автомата составляется треугольная таблица, столбцы и строки которой сопоставляются с состояниями автомата. Рассмотрим минимизацию автомата S3, заданного табл.1.19 и 1.20. Табл.1.21 - треугольная таблица для автомата S3. Для упрощения записи в этой таблице вместо ai будем писать i. В треугольной таблице на пересечении строки m и столбца s ставятся: • + (крест), если в столбцах am и as таблицы выходов стоят разные выходные сигналы, например а1 и а2; • множество всех пар состояний, следующих за парой (am, as) и отличных от неё, эквивалентность которых необходима для эквивалентности пары (am, as). Например, для эквивалентности (а1, а8) необходима эквивалентность (а3, а6) и (а2, а5), так как (а3, а8) и (а2, а5) следуют за множеством (а1, а8) по входам z1 и z2 соответственно (см. табл. 1.19). • V (птичка), если за (am, as) не следуют пары, отличные от (am, as). В нашем примере это пара (а6, а7). Таблица 1.19 а1 а2 а3 а4 а5 а6 а7 а8 z1 а3 а8 а7 а2 а3 а2 а2 а6 z2 а2 а4 а5 а4 а2 а7 а6 а5 Таблица 1.20 а1 а2 а3 а4 а5 а6 а7 а8 z1 w1 w2 w1 w2 w1 w2 w2 w1 z2 w2 w1 w2 w1 w2 w1 w1 w2 Для нахождения неэквивалентных пар состояний треугольная таблица (табл.1.21) просматривается по столбцам. Находится первая клетка, отмеченная крестом. Пусть это будет клетка (i, j). Тогда во всех клетках, где есть пара (i, j) ставится крест, а уже рассмотренная клетка (i, j) отмечается вторым крестом. Эта процедура проводится для всех клеток, отмеченных крестом, включая новые, и заканчивается, когда таких клеток не останется. Очевидно, что в этом случае клетки без крестов соответствуют эквивалентным парам состояний, а клетки с крестами - неэквивалентным. В результате применения этой процедуры к табл.1.21 получим табл.1.22. Из этой таблицы видно, что: 1~5, 3~8, 4~6, 4~7, 6~7. Для нахождения разбиения  воспользуемся способом, предложенным С.Ангером. Алгоритм сводится к следующему. 1. Начинаем составление списка классов эквивалентных состояний с крайнего правого столбца треугольной таблицы, имеющего по крайней мере одну клетку без крестов. В примере Ф = {} . 2. Продвигаясь влево выписываем для каждого столбца множества состояний ~ , т.е. множества состояний, соответствующим клеткам без крестов в i-ом столбце таблицы. В нашем примере 4 ~ (в 4-м столбце табл.1.22 нет крестов в строках 6 и 7). Каждое Ai пересекаем с каждым членом текущего списка Ф. Если такое пересечение содержит более одного состояния, то добавляем в список объединение { ai } с результатом пересечения: ; Ф = {} . Далее проводится максимизация полученного множества Ф - удаление всех множеств, содержащихся в других множествах списка. Приведём полностью результат применения второго шага ко всем столбцам: 3. В список Ф, полученный после второго шага добавляются все одноэлементные множества, состоящие из состояний, не включенных ни в какие другие максимальные классы эквивалентности. В нашем примере - . Таким образом для автомата S3 множество всех классов эквивалентности – разбиение  имеет вид:  =. Построение минимального автомата S3 по разбиению  проводится аналогично пунктам 2 - 4 алгоритма, рассмотренного выше (см. 1.5.1). Из каждого класса эквивалентности выбираем по одному состоянию: A  = { а1, а2, а3, а4} . Строим таблицы переходов и выходов минимального автомата S3 (табл. 1.23 и 1.24). Таблица 1.23 Таблица 1.24 а1 а2 а3 а4 а1 а2 а3 а4 z1 а3 а3 а4 а2 z1 w1 w2 w1 w2 z2 а2 а4 а1 а4 z2 w2 w1 w2 w1 1.6. Задачи анализа и синтеза цифровых автоматов При решении задачи синтеза цифровых автоматов выделяются этапы абстрактного и структурного синтеза. На этапе абстрактного синтеза описывается закон функционирования (поведение) автомата на одном из начальных языков, а затем выполняется переход к описанию алгоритма на одном из стандартных языков. Заканчивается этап абстрактного синтеза минимизацией числа состояний автомата. В качестве стандартного языка используются прямые таблицы переходов, СКУ и СВФ. В ряде случаев язык СКУ и СВФ может быть использован и в качестве начального языка. На этапе структурного синтеза решается задача построения схемы автомата по заданному описанию на одном из стандартных языков. Проблема анализа автоматов обратна проблеме синтеза, ее решение заключается в описании для заданного конечного автомата его поведения средствами исходного языка. Обычно задача анализа проще, чем задача синтеза. Одна из основных задач теории автоматов заключается в том, чтобы задачу анализа и синтеза цифровых автоматов свести к задаче анализа и синтеза комбинационных схем. При этом в качестве основного математического аппарата используется аппарат алгебры логики. Задание для самоконтроля 1. Дайте определение цифрового автомата. 2. В чем отличие структурного цифрового автомата от абстрактного ? 3. Назовите важное различие в функционировании автоматов Мили и Мура . 4. Опишите поведение С-автомата. 5. Назовите функции операционного и управляющего автоматов. 6. Основные положения принципа микропрограммного управления. 7. Типы МПА. Сравнительная характеристика. 8. Способы задания цифровых автоматов. 9. Найдите автомат Мура, эквивалентный автомату Мили (табл. 1.25). Таблица 1.25 a1 a2 a3 a4 z1 a2/w1 a3/w2 a4/w1 a1/w1 z2 a3/w2 a2/w3 a1/w1 a3/w1 10. Какие события называются эквивалентными ? К-эквивалентными ? 11. Основные этапы минимизации полностью определенных автоматов методом Ауфенкампа и Хона . 12. Этапы минимизации СКУ с помощью треугольной таблицы. 13. Какие задачи решаются на этапе абстрактного синтеза ЦА ? 14. Какие задачи решаются на этапе структурного синтеза ЦА ? 2. Синтез автоматов без памяти 2.1. Основные этапы проектирования комбинационных схем Комбинационная схема (КС) - схема, состоящая из логических элементов, реализующая булеву функцию или совокупность булевых функций. Выходной сигнал КС в любой момент времени определяется совокупностью входных сигналов. Логический элемент (ЛЭ) - техническое устройство, реализующее одну элементарную булеву функцию. Обычно для построения КС используют ЛЭ, реализующие логические функции И, ИЛИ, НЕ: конъюнктор (схема И); дизъюнктор (схема ИЛИ); инвертор (схема НЕ). Стандартные обозначения этих элементов на схеме изображены на рис. 2.1. Рис. 2.1. Обозначения логических элементов: а - конъюнктор; б - дизъюнктор; в – инвертор Схема, показывающая связи между различными ЛЭ, где сами ЛЭ представлены условными обозначениями, называется функциональной схемой. Задача анализа заданной КС сводится к отыскиванию значений функции или (системы функций) на выходе этой схемы с помощью аппарата алгебры логики. Задача синтеза КС состоит в построении реальной схемы проектируемого узла, исходя из физического описания работы (технического задания на проектирование). Основные этапы синтеза: 1. Анализ технического задания и составление таблицы истинности. 2. Минимизация логических функций. 3. Преобразование минимальных логических функций для рациональной реализации логической схемы в заданном базисе. 4. Построение функциональной схемы. 5. Проверка работоспособности схемы и её корректировка. Минимизация логических функций выполняется методами Квайна и Мак-Класки или с помощью карт Карно. Этот этап является очень важным, так как решением одной и той же задачи может быть очень большое число вариантов, отличающихся по сложности и быстродействию. При реализации КС на интегральных схемах малой степени интеграции традиционные критерии минимизации - минимальное число букв и логических операций в реализуемой функции. Для комбинационных узлов БИС критерием сложности является не только число элементов на кристалле, необходимых для реализации функции узла. Большое значение приобретают морфологические свойства реализуемых схем такие, как регулярность структуры, повторяемость элементов и связей, занимаемая площадь, минимальная длина межсоединений и т.п. Необходимость следующего этапа обусловлена тем, что применяемые на практике комплексы ЛЭ имеют в своём составе комбинированные логические элементы (КЛЭ) такие, как И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ. Следовательно, минимальные функции, выраженные в базисе И, ИЛИ, НЕ, необходимо преобразовать к тому логическому базису, который отвечает выбранным элементам. На четвёртом этапе составляется функциональная схема в заданном базисе. При этом каждой преобразованной логической функции ставится в соответствии определённый КЛЭ заданного базиса. Связи между КЛЭ определяются логической функцией. На последнем этапе производится проверка правильности работы схемы на основе алгоритма её функционирования. Решаются вопросы временного согласования сигналов при обмене информацией между элементами КС. В случае необходимости функциональные схемы корректируется. При разработке КС за основные критерии качества технической реализации принимают сложность оборудования, минимум применяемых элементов, быстродействие и надёжность. На практике при реализации КС в заданном базисе количество оборудования оцениваются числом корпусов интегральных микросхем, используемых в схеме. На теоретическом уровне используется оценка сложности КС по Квайну. Сложность (цена) схемы по Квайну определяется суммарным числом входов ЛЭ в составе схемы. Быстродействие оценивается задержкой сигнала при прохождении его от входа схемы к выходу. Надёжность КС оценивается интенсивностью отказов:  = n / N  t (2.1) где n – количество элементов, вышедших из строя за период испытаний t, N – общее количество ЛЭ. Задача синтеза всегда имеет множество решений. Из этого множества выбираются схемы, критерии качества технической реализации которых удовлетворяют заданию на проектирование. 2.2. Синтез КЛС в булевом базисе, базисах И-НЕ, ИЛИ-НЕ ,И-ИЛИ-НЕ Разрабатываемые комбинационные функциональные узлы (КФУ), используемые в устройствах ЭВМ, могут иметь разнообразную конфигурацию. Задача реализации функциональной схемы КФУ состоит в преобразовании описывающих её логических функций в суперпозицию логических элементов заданного типа. Будем при этом предполагать, что исходная булева функция должна быть представлена в минимальной форме: МДНФ или МКНФ, а на входах проектируемой схемы вместе с переменными присутствует их инверсия. Сформулируем правила преобразования исходной булевой функции для рациональной реализации на элементах И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ. • Для реализации исходной булевой функции на элементах типа И-НЕ необходимо от МДНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана. • Для реализации исходной булевой функции на элементах типа ИЛИ-НЕ необходим от МКНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана. • Для реализации исходной булевой функции на элементах типа И-ИЛИ-НЕ необходимо найти МДНФ отрицания функции. Пример 2.1. Реализовать функцию f (x1, x2, x3, x4) =  (0, 2, 4, 6, 7, 10 ,11 ,14 ,15) на элементах серии К555: а) типа И-НЕ; б) типа ИЛИ-НЕ; в) типа И-ИЛИ-НЕ. Решение: а) Для реализации на элементах типа И-НЕ с помощью карты Карно (рис.2.2,а. ) получим МДНФ функции : Берём двойное отрицание от МДНФ функции и одно из них открываем по правилу де Моргана, получаем : . Реализация функции на элементах типа И-НЕ показана на рис. 2.3,а. б) Для реализации функции f на элементах типа ИЛИ-НЕ получаем МКНФ функции с помощью карт Карно (рис. 2.2, б): . Берём двойное отрицание от МКНФ и одно из них открываем по правилу де Моргана, получаем: . Реализация функции на элементах типа ИЛИ-НЕ показана на рис. 2.3,б. Рис. 2.2. Карта Карно функции к примеру 2.1 в) Для реализации функции f на элементах типа И-ИЛИ-НЕ находим с помощью карт Карно (см. рис. 2.2,б) МДНФ отрицания функции: . Реализация полученной функции приведена на рис. 2.3, в. Рис.2.3. Реализация схемы из примера 2.1: а - на элементах типа И-НЕ; б - на элементах типа ИЛИ-НЕ; в - на элементах типа И-ИЛИ-НЕ 2.3. Некоторые приемы преобразования функций для реализации на элементах заданного типа 1) При реализации довольно сложных булевых функций указанными приемами иногда получаются выражения, которые непосредственно не реализуются на КЛЭ заданного типа. В этом случае применяют метод тождественных преобразований с предварительной группировкой. Пример 2.2. Реализовать функцию Y (x1, x2, x3, x4, x5) на элементах типа И-ИЛИ-НЕ серии К555: . Решение. С помощью карты Карно ( рис. 2.4,а ) находим МДНФ отрицания функции Y, склеивая нули: . Полученное выражение не реализуется непосредственно на КЛЭ типа И-ИЛИ-НЕ, имеющихся в серии К555. Сгруппируем два последних терма и получим: , где . Рис. 2.4.Карты Карно (а, б) и схема (в) к примеру 2.2 Для A ( x2 x4 x5 ) еще раз применим карту Карно (рис. 2.4, б), с целью приведения этой булевой функции к форме отрицания ДНФ, получим: . В итоге получили булеву функцию, легко реализуемую на элементах типа И-ИЛИ-НЕ: К555 ЛР11 и К555 ЛР3 (рис. 2.4, в). 2) При синтезе КС на основе реальных КЛЭ необходимо учитывать их ограниченное число входов и нагрузочную способность. Такое ограничение иногда не позволяет реализовать исходную булеву функцию в виде структуры КЛЭ, состоящей только из двух уровней. Для синтеза КС на КЛЭ с меньшим числом входов, чем это требуется по исходной булевой функции, используется факторизационный метод синтеза КС. Этот метод базируется на преобразовании исходной булевой функции путем выноса за скобку общих логических переменных. В этом случае схема реализации булевой функции будет состоять из более, чем двух уровней, что приведет к уменьшению ее быстродействия. Пример 2.3. Реализовать функцию Y ( x1, x2, x3 ) на элементах типа 2И-НЕ (К555 ЛА3). Решение. Преобразуем функцию Y в суперпозицию заданных КЛЭ следующим образом: где . От функции Y и A берем двойное отрицание, одно их которых раскрываем по правилу де Моргана: Полученные выражения позволяют реализовать схему с использованием элементов ЛА3 серии К555 (рис. 2.5.). Рис. 2.5. Схема к примеру 2.3 3) В ряде случаев требуется построить КС, не используя инверсии входных переменных. С этой целью выполняются преобразования исходной функции, рассмотренные в примере 2.4. Пример 2.4. Реализовать функцию Y ( x1, x2 ) на элементах серии К555, не используя инверсии входных переменных. . Решение. Используя правила поглощения для элементарных дизъюнкций, можно записать: . Далее берем от функции Y двойное отрицание, одно из которых раскрываем по правилу де Моргана, получим: . Реализация этой функции на элементах ЛА3 серии К555 показана на рис. 2.6. Рис. 2.6. Схема к примеру 2.4 4) В том случае, если ДНФ функции содержит число элементарных конъюнкций  8, рекомендуется способ преобразования функции, рассмотренный в примере 2.5. Пример 2.5. Реализовать функцию Решение. Сгруппируем исходные термы так, чтобы число слагаемых в скобке было равно (или < ) числу схем И в КЛЭ типа И-ИЛИ-НЕ, а ранг соответствовал числу входов схем И: . Возьмем от функции Y двойное отрицание, одно из которых раскроем, не меняя выражения в скобках, получим: . Реализация этой функции показана на рис. 2.7. Рис. 2.7. Схема к примеру 2.5 2.4. Оценка результатов проектирования и выбор схемы для использования В качестве основных критериев качества технической реализации при синтезе комбинационных схем будем использовать: а) быстродействие схемы; б) сложность оборудования. Быстродействие или длительность работы КС оценивается самой длинной цепью из последовательно включенных микросхем. Будем называть глубиной схемы количество последовательно включенных микросхем. Например, схема, изображенная на рис. 2.3,в, имеет глубину, равную единице, схемы на рис. 2.3,а,б; 2.7, глубину, равную двум, а схема на рис. 2.5, ‑ глубину, равную пяти. Если известна глубина схемы k, то длительность ее работы оценивается как T = k, (2.2) где  - длительность задержки сигнала КЛЭ. Для микросхем серии К555 в качестве такой задержки можно принимать 20 - 25 мс. Для быстродействующего узла важно получить при проектировании минимальную глубину. Сложность оборудования оценивается количеством корпусов микросхем, необходимых для реализации данной схемы (с учетом незадействованных КЛЭ). Оценка проводится исходя из количества микросхем, расположенных на одном корпусе. Например, схема, изображенная на рис. 2.3,а, требует для реализации два корпуса (1 корпус для трех элементов ЛА3 и 1 корпус ЛА4) N = 2. Количество оборудования для реализации схем, изображенных на рис. 2.3,б,в; 2.4; 2.5; 2.7, соответственно N = 2, N = 2, N =2, N =2, N =4. Кроме рассмотренных критериев важной оценкой работоспособности схемы являются оценка степени нагруженности входных сигналов, в связи с тем, что выход КЛЭ серии К555 можно нагрузить не более чем на 14 входов без нарушений ее работоспособности. По результату оценки выясняют, достаточна ли нагрузочная способность поступающих сигналов для их использования в данной схеме. Выбор одного из спроектированных вариантов схемы должен делаться с учетом конкретных условий ее работы. В быстродействующем устройстве наибольшую роль играет скорость и этот критерий является самым важным, по нему ведется сравнение различных вариантов схемы и делается окончательный выбор. Если скорость не важна, самым важным может оказаться экономичность. Часто при проектировании схем выдвигается в качестве критерия оптимальное соотношение быстродействия и сложности КС. Задание для самоконтроля 1.Выполнить совместную минимизацию систем булевых функций четырех переменных и реализовать на элементах серии К555 : а) типа И-НЕ; б) типа ИЛИ-НЕ; в) типа И-ИЛИ-НЕ. Для каждого варианта определить основные критерии качества технической реализации. y1 =  ( 5, 6, 7, 8, 9 ) , * = ( 10 — 15 ) ; y2 =  ( 4, 6, 7, 8, 9 ) , * = ( 10 — 15 ) ; y3 =  ( 2, 3, 5, 8, 9 ) , * = ( 10 — 15 ) ; y4 =  ( 1, 3, 5, 7, 9 ) , * = ( 10 — 15 ) . 2. Реализовать функцию Y ( a, b, c ) на элементах 2И-НЕ, используя факторизационный метод синтеза. 3. Реализовать функцию Y ( a, b, c ) на элементах серии К555, не используя инверсии входных переменных. 4. Функцию Y ( a, b, c, d, f ) преобразовать в МКНФ и реализовать на элементах типа И-ИЛИ-НЕ, используя метод тождественных преобразований с предварительной группировкой. 5. Заданную функцию реализовать на элементах серии К555, используя в качестве критерия оптимальное соотношение быстродействия и сложности КС. 3. ПРОЕКТИРОВАНИЕ ФУНКЦИОНАЛЬНЫХ УЗЛОВ КОМБИНАЦИОННОГО ТИПА Задача синтеза функционального узла комбинационного типа заключается в построении оптимальной схемы проектируемого узла, моделирующей закон функционирования цифрового автомата без памяти, представленного одной булевой функцией или системой булевых функций. К требованиям оптимальности могут быть отнесены стоимость и сложность оборудования, быстродействие и надежность, однородность структуры и др. 3.1. Сумматоры Сумматор - это комбинационный функциональный узел (КФУ), предназначенный для выполнения операции суммирования двоичных чисел. С помощью сумматора можно выполнять также операции вычитания, умножения, деления, преобразования чисел в дополнительный код и другие дополнительные операции. Классифицируются сумматоры по трем основным признакам: 1) по числу входов (полусумматоры, одноразрядные и многоразрядные сумматоры); 2) по способу тактирования; 3) по системе счисления. По способу тактирования различают синхронные и асинхронные сумматоры. В синхронных сумматорах на суммирование любой пары чисел отводится максимальное время. В этом случае время, отводимое на суммирование используется в большинстве случаев неэффективно. Так, в ряде работ доказано, что средняя длина распространения переноса - , что , где n - количество разрядов в числе. В асинхронных сумматорах на суммирование любой пары чисел отводится необходимое время. В таких сумматорах имеются цепи, которые определяют момент окончания распространения переноса. По системе счисления различают сумматоры двоичные, двоично-десятичные и др. Двоично-десятичные сумматоры выполняют действия над десятичными числами, разряды которых закодированы двоичными тетрадами. Обычный способ построения двоично-десятичного сумматора предусматривает первичное суммирование тетрад обычным двоичным сумматором и последующую коррекцию результата. 3.1.1. Проектирование полусумматоров Полусумматором называют КФУ с двумя входами (a, b) и двумя выходами (S, P), на которых вырабатываются сигналы суммы и переноса. Условное графическое изображение и таблица истинности полусумматора приведены на рис. 3.1, а, б. Рис. 3.1. Полусумматор : а - условное графическое обозначение; б - таблица истинности Из таблицы истинности (рис. 1.1, б) следует: (3.1) Преобразуем выражение (3.1) к виду, удобному для реализации на элементах И-НЕ: (3.2) Функциональная схема полусумматора, построенная по выражениям (3.2) показана на рис. 3.2, а. Как показывает опыт, простая интерпретация минимальных форм булевых функций функциональными компонентами, показанными на рис. 3.2, а обычно не приводит к минимальным результатам. Чтобы минимизировать затраты оборудования в схеме необходимо минимизировать число инверсий над входными переменными. Для этого используем следующее правило : (3.3) Используя правило (3.3) преобразуем выражение (3.2) к виду : (3.4) По выражению (3.4) построена схема полусумматора на элементах типа И-НЕ, приведенная на рис. 3.2, б. Она содержит на два элемента меньше, чем эквивалентная ей схема на рис. 3.2, а. Рис. 3.2. Полусумматор. Функциональные схемы на элементах И-НЕ 3.1.2. Проектирование одноразрядных сумматоров Одноразрядным сумматором называют КФУ с тремя входами и двумя выходами. Это основной элемент многоразрядных сумматоров. Он обеспечивает арифметическое сложение одноразрядных двоичных чисел ai, bi и переноса из предыдущего разряда Pi-1 с образованием на выходах суммы Si и переноса в старший разряд Pi. Условное графическое обозначение и таблица истинности одноразрядного сумматора приведены на рис. 3.3, а, б. Рис. 3.3. Одноразрядный сумматор : а - условное графическое обозначение; б - таблица истинности; в - карта Карно Для минимизации функций Si, Pi отобразим их на карте Карно (рис. 3.3, в). Функция Si минимизации не подлежит, поэтому запишем ее в СДНФ. . (3.5) Функцию Pi после минимизации можно записать в виде . (3.6) При проектировании одноразрядных сумматоров учитываются особенности выбранной системы логических элементов. Рассмотрим пример синтеза одноразрядного сумматора на логических элементах типа И-НЕ. Для реализации функции Si выполним следующие преобразования выражения (3.5): где . Полученные выражения для Si, Ci, Pi преобразуем к виду, удобному для реализации на элементах типа И-НЕ: (3.7) Схема одноразрядного сумматора, реализующая уравнения (3.7), представлена на рис. 3.4. Для упрощения схемной реализации функции Si выполним следующие преобразования. Представим Si как функцию четырех переменных: ai, bi, Pi-1 и Pi. Для этого составим таблицу истинности (рис. 3.5, а), где на нереальных входных наборах функция Si принимает неопределенные значения (*). После минимизации с помощью карты Карно (рис. 3.5, б) запишем . (3.8) Рис. 3.4. Одноразрядный сумматор Используя полученные выражения для суммы (3.8) и переноса (3.6) легко построить схему одноразрядного сумматора, которая положена в основу микросхемы сумматора (рис. 3.5, в). Быстродействие одноразрядных сумматоров оценивают задержками распростра­нения сигналов по четырем трактам: «слагаемое - сумма» (c, s), «слагаемое - перенос» (c, p), «перенос - сумма» (p, s) и «перенос - перенос» (p, p). Рис. 3.5. Одноразрядный сумматор : а - табличное представление функции Si; б - минимизация функции Si; в - функциональная схема 3.1.3. Проектирование многоразрядных сумматоров Многоразрядные сумматоры делятся на последовательные и параллельные. В последовательном многоразрядном сумматоре (рис. 3.6) подача слагаемых начинается с младшего разряда. Образуется поразрядная сумма и перенос, который запоминается на один такт, а затем поступает на вход сумматора, вместе со слагаемыми следующего разряда. Такой процесс продолжается до окончательного формирования результата, выдаваемого последовательным кодом. Время выработки суммы n-разрядных чисел : , где tc - длительность суммирования в одноразрядном сумматоре. Рис. 3.6. Структура последовательного многоразрядного сумматора Наибольшее распространение получили парал­лельные многоразряд­ные сумматоры, которые строятся с использованием необходимого числа одноразрядных сумматоров, на которые входные переменные подаются параллельным кодом. По способу организации межразрядных переносов параллельные сумматоры делятся на схемы с последовательным и параллельным переносом и с групповой структурой. Условное графическое обозначение комбинационного парал­лельного сумматора приведено на рис. 3.7. Параллельный сумматор с последовательным переносом (рис.3.8) принимает слагаемые параллельно. После этого образуются предвари­тельные поразрядные суммы, а после появления и распространения переносов суммы принимают окончательное значение. Время сложения определяется по формуле : tc =tc, p + (n‑2)tp, p + tp, s  n tp, p , (3.9) где: tc, p – время выработки переноса в младшем разряде; tp, p – время распространения переноса через разряд; tp, s – время выработки суммы в старшем разряде после поступления на его вход переноса от предпоследнего разряда. Рис. 3.8. Схема параллельного сумматора с последовательным переносом Основную часть времени суммирования занимает распространение переноса через разряды сумматора, поэтому минимальность tp, p имеет большое значение. Рассмотренные выше схемы одноразрядных сумматоров (рис. 3.4, рис. 3.5) имеют время tp, p = 2, где  - время задержки логического элемента. 3.2. Проектирование дешифраторов и шифраторов Шифрация и дешифрация (сжатие данных и обратное преобразование) являются основными видами преобразования информации. 3.2.1. Дешифраторы Дешифратор - это КФУ, имеющий n входов и 2n выходов, осуществляющий преобразование входного двоичного n-разрядного кода в сигнал на одном из выходов. По каждому выходу дешифратора реализуется конституента единицы (или ее отрицание). Различают полные и неполные дешифраторы. Число выходов полного дешифратора Nвых = 2n , неполного ‑ Nвых  2n. Условное графическое обозначение полного дешифратора на два входа и его таблица истинности приведены на рис. 3.9, а, б. E - вход, на который подается сигнал, разрешающий дешифрирование. Рис. 3.9. Дешифратор : а - условное графическое изображение; б - таблица истинности Аналитическое описание дешифратора в форме СДНФ : Yi = i  E, i = 0, 1, ..., n. (3.10) где  i ‑ i-ый минтерм n входных переменных , E ‑ сигнал, разрешающий дешифрирова­ние. Для неполных дешифраторов имеются безразличные (неопределенные) входные наборы, которые можно использовать при минимизации выходных функций. Например, при проектировании дешифратора «1 из 10» безразличными являются входные наборы отмеченные знаком * на карте Карно (рис. 3.10 а, б). После совместной минимизации на рабочих и соседних к ним неопределенных наборах получим следующие логические уравнения: (3.11) Если при проектировании дешифратора не проводить совместной минимизации рабочих и неопределенных наборов, то схемная реализация будет иметь большую стоимость и топологические размеры будут значительно большими. В схемах ЭВМ дешифраторы устанавливаются на выходах регистров или счетчиков и служат для преобразования кода слова, находящегося в регистре (в счетчике) в управляющий сигнал на одном из выходов дешифратора. 3.2.2. Использование дешифраторов Рассмотрим некоторые области применения дешифраторов в разрабатываемых устройствах. 1. Для реализации логических функций. Пример 3.1. Реализовать на основе дешифратора логическую функцию вида : Решение. Исходная функция задана в форме ДНФ. Преобразуем ее в СДНФ : . Полученное выражение реализу­ется логической схемой, представлен­ной на рис. 3.11. Для получения схемы достаточно определить выходы де­шифратора, соответствующие входя­щим в функцию конституентам едини­цы и соединить их с входами дизъюнктора. Если на входы дешиф­ратора будут поданы входные пере­менные, то на выходе дизъюнктора сформируется значение функции. Рис. 3.11. Реализация логической функции на основе дешифратора 2. В качестве преобразователя двоично-десятичного кода в семисегментный код в устройствах визуальной индикации десятичных цифр на световом табло (рис. 3.12, а). Проектирование таких преобразователей осуществляется на основе таблицы истинности (рис. 3.12, б) дешифратора «1 из 10» и системы уравнений: где y0y9 – выходные шины дешифратора «1 из 10» (рис. 3.12 в). Cхема дешифратора-преобразователя приведена на рис. 3.12, в. 3. Для преобразования кодов. В качестве примера приведена таблица ис­тинности преобразователя двоично-десятичного кода 8-4-2-1 в код 2-4-2-1 (табл. 3.1.). Из таблицы истинности записываются уравнения выходных функ­ций для реализации пре­образователя (3.12) : Дес. входы DC выходы число x1 x2 x3 x4 а б в г д е ж y0 1 1 1 1 1 1 1 1 y1 1 1 2 1 y2 1 1 1 1 1 3 1 1 y3 1 1 1 1 1 4 1 y4 1 1 1 1 5 1 1 y5 1 1 1 1 1 6 1 1 y6 1 1 1 1 1 1 7 1 1 1 y7 1 1 1 8 1 y8 1 1 1 1 1 1 1 9 1 1 y9 1 1 1 1 1 1 б) в) Рис. 3.12. Дешифратор преобразователь двоично-десятичного кода в семисегментный код A = y5  y6  y7  y8  y9 , B = y4  y6  y7  y8  y9 , (3.12) C = y2  y3  y5  y8  y9 , D = y1  y3  y5  y7  y9 , 3.2.3. Шифраторы Шифратор ‑ это КФУ, преобразующий сигнал на одном из 2n входов в n-разрядный двоичный код на выходах. Если число входов меньше, чем 2n , то шифратор неполный. Одно из основных применений шифратора ‑ ввод данных с клавиатуры, при котором нажатие на клавишу с десятичной цифрой должно приводить к передаче в устройство этой цифры в двоичном коде. Данная функция реализуется неполным шифратором «10-4» (рис. 3.13). Из таблицы истинности (табл. 3.2) получаем логические уравнения для шифратора «10-4» : (3.13) Таблица 3.2 Дес. Входы Выходы число x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2 y3 y4 1 1 1 1 2 1 1 3 1 1 1 4 1 1 5 1 1 1 6 1 1 1 7 1 1 1 1 8 1 1 9 1 1 1 Рис. 3.13. Шифратор «10-4». Условное графическое обозначение 3.3. Проектирование мультиплексоров и демультиплексоров 3.3.1. Мультиплексоры Мультиплексор – это КФУ, служащий для последовательного опроса состояний большого числа переменных и передачи их на единственный выход. Входы мультиплексора разделяются на информационные (входы данных), и адресные (управляющие). Код (адрес), поступающий на управляющие входы, определяет информационный вход, сигнал с которого передается на выход. Чаще всего используют мультиплексоры на 4, 8, 16 входов. Условное графическое изображение мультиплексора на четыре входа («4-1») и его таблица истинности приведены на рис. 2.14, а, б, где Е - сигнал, разрешающий мультиплексирование; x0, x1, x2, x3 - информационные входы; A2, A1 ‑ управляющие входы; Y ‑ выход. Из таблицы истинности (рис. 3.14, б) получим СДНФ функции Y: . (3.14) СДНФ выходной функции мультиплексора на 2n входов имеет вид: (3.15) где  i ‑ минтерм (конституента 1), соответствующий i-му адресному набору. Данная функция далее может быть реализована в заданном базисе элементов. а) б) Рис. 3.14. Мультиплексор «4-1» Мультиплексор можно рассматривать как преобразователь параллельной информации в последовательную. Мультиплексор на большое число входов, как правило, приходится строить из мультиплексоров меньшей размерности. 3.3.2. Применение мультиплексоров Пример 3.2. Реализовать на мульти­плексоре типа «8-1» логическую функцию трех переменных: Решение. Функция задана в СДНФ. Используется мультиплексор типа «8-1». На адресные входы пода­ются входные переменные, а инфор­мационные входы, соответствующие входящим в функцию конституентам единицы соединяются с шинами питания (1), остальные информа­ционные входы соединяются с шина­ми земли (0). На выходе мультиплек­сора формируется значе­ние функции (рис. 3.15). Пример 3.3. Реализовать на мультиплексоре типа «8-1» логическую функцию четырех переменных : . Решение. В качестве управляющих сигналов используются переменные a, b, и c, которые подаются на адресные входы мультиплексора. На информационные входы поступают переменные d, , 0, 1 : x0 = 0, x3 = d, x6 = 0, x1 = 1, x4 = 0, x7 = , x2 = 0, x5 = 1. Пример 3.4. Реализовать с помощью мультиплексора типа «4-1» функцию трех переменных Y = f (a, b, c) : Y = (0, 2, 3, 8) Сначала выбирается любое сочетание двух переменных ab, ac, bc, которые являются управляющими и подаются на адресные входы мультиплексора. На информационные входы в этом случае могут быть поданы четыре функции одной (третьей) переменной. На рис. 3.16. показано соответствие информационных входов мультиплексора x0, x1, x2, x3 определенным адресным (управляющим) входам мультиплексора «4-1». Например, если в качестве управляющих применить сигналы a и b, то входу x0 будут соответствовать две клетки карты Карно, для которых a = b = 0; входу x1 – a = 0, b = 1; x2 – a=1, b=0; x3 – клетки с a = b =1 (рис. 3.16, а). Таким образом, карта Карно на три переменные разбивается как бы на четыре двухклеточные карты на одну переменную. Затем минимизируется набор из четырех функций одной переменной и получаются необходимые значения сигналов на информационных входах мультиплексора для реализации заданной логической функции. Рис. 3.16. Соответствие информационных входов мультиплексора «4-1» управляющим сигналам a и b (а), а и с (б), b и с (в) Решение. Выберем в качестве управляющих сигналов переменные a и b. Функция Y =  (0, 2, 3, 6) представлена на карте Карно (рис. 3.17, а). Минимизируем набор из четырех функций от одной переменной c, соответствующих каждому информа­ционному входу (x0, x1, x2, x3). Обе клетки, соответствующие x1, помечены единицей и, следовательно на вход x1 подается сигнал . Оставшиеся входные функции получаем с помощью карты Карно (рис. 3.17, а) : x0 = ; x2 = 0; x3 = . Подавая на входы мультиплексора найденные значения xi, реализуем заданную функцию (рис. 3.17, б). Если в качестве управляющих выбрать сигналы a и c или b и c, то получаются новые реализации (соответственно рис. 3.17, в, г). Рис. 3.17. Применение мультиплексора для реализации функции Y =  (0, 2, 3, 6) Пример 3.5. Реализовать на мультиплексоре типа «4-1» логическую функцию четырех переменных : Y (a, b, c, d)=  (0, 1, 6, 7, 9, 10, 11, 12, 13). В качестве управляющих сигналов принять переменные a и b. Решение. Покажем на карте Карно для функции четырех переменных (a, b, c, d) расположение информационных сигналов (x0, x1, x2, x3) мультиплексора «4-1» (рис. 3.18, а). Для каждого из четырех xi получим свою четырехклеточную карту Карно для двух переменных c и d. Например, x0 соответствуют четыре клетки с координатами a = b= 0; x1– a = 0, b = 1; x2 – a = 1, b = 0; x3 – a = b = 1 (рис. 3.18, а). Отобразим на карте Карно заданную функцию (рис. 3.18, б) и проведем для каждого xi минимизацию. Получим x0 = , x1 = c, x2 = c  d, x3 = . Это значит, что для реализации заданной функции на информационные входы мультиплексора «4-1» необходимо подать соответствующие значения переменных c и d (рис. 3.18, в). Рис. 3.18. Реализация функции Y (a, b, c, d)=  (0, 1, 6, 7, 9, 10, 11, 12, 13) на мультиплексоре «4-1» 3.3.3. Демультиплексоры Демультиплексор - это КФУ, выполняющий распределение входного сигнала X в соответствии с адресом на одну из N выходных шин. Условное графическое обозначение демультиплексора с четырьмя выходными шинами («1-4») приведено на рис. 3.19. Рис. 3.19. Условное графическое обозначение демультиплексора «1-4» Функционирование демультиплексора «1-4» описывается следующими логически­ми уравнениями : (3.17) Для демультиплексора с числом выходных шин N=2n, где n - число адресных входов, можно записать : (3.18) где  i – минтерм (конституента 1), соответствующий i-му адресному набору. Демультиплексоры широко используются для преобразования последовательного кода в параллельный. 3.4. Проектирование компараторов Компаратор - это КФУ, предназначенный для сравнения двух чисел (А,В) по различным признакам : равно (=), не равно (), больше (), меньше (), больше или равно (), меньше или равно (). Основные отношения равно и больше. Остальные можно получить через основные. Выходные функции компаратора определяются следующими выражениями : (3.19) Схемы сравнения на равенство A = B, где A = a1 a2 ... an и B = b1 b2 ... bn cтроятся на основе поразрядных операций над одноименными разрядами слов. Значения A и B равны, если одновременно равны их одноименные разряды ai, bi, i=1, 2, ..., n . Из таблицы истинности (табл. 3.3) следует признак равенства ‑ ri и признак неравенства ‑ одноименных разрядов : (3.20) Таблица 3.3 ai bi ri ri > ri < 1 1 1 1 1 1 1 1 1 1 Признак равенства двух n-разрядных чисел вычисляется как конъюнкция (3.21) Аналогично признак неравенства (YA B) вычисляется как конъюнкция . (3.22) В ряде случаев требуется построить компаратор не используя инверсии аргументов. С этой целью выражения (3.20) преобразуются к виду : , (3.23) . (3.24) Схемы сравнения на больше - меньше также строятся на основе поразрядных операций над одноименными разрядами чисел. Из таблицы истинности (табл. 3.3) можно записать : Сравнение выполняется, начиная со старших разрядов. Если a1>b1, то независимо от младших разрядов A > B и YA>B = 1. Если старшие разряды равны (r1=1), следует сравнивать младшие, применив то же условие и т.д. Таким образом, (3.27) где Аналогично можно получить выражение для YA