АСИНХРОННЫЙ S-ТРИГГЕР
Основные типы асинхронных триггеров строятся, как правило, на основе триггера типа R-S. Метод их построения рассмотрим на примере S-триггера. Обозначим буквами S и R входы создаваемого S-триггера, а функции возбуждения R-S-триггера, используемого в качестве элемента памяти, обозначим символами q’R и q’S. Вначале построим таблицу переходов S-триггера, исходя из его реакции на входные сигналы (рис. 11,а ). Затем построим таблицы функций возбуждения q’R и q’S
триггера R-S, который используется в качестве основного элемента памяти (рис. 11,б ).
Особенностью рассмотренных триггеров является то, что изменение их состояния начинается одновременно с подачей входного сигнала, поэтому реализация асинхронных триггеров типа T и J-K оказывается невозможной.
Пред.Страница
След.Страница Раздел Содержание
АСИНХРОННЫЙ ТРИГГЕР
На входе обычного триггера, построенного из элементов потенциального типа, подаются потенциальные сигналы, поэтому его назвают асинхронным триггером. Такие триггеры строят как обыкновенные асинхронные автоматы, используя в качестве элемента памяти асинхронный триггер типа R-S. В отличие от всех остальных триггеров построение R-S-триггера производится по характеристическому уравнению. Это уравнение имеет вид:
qt+1 = (qR V S)t.
Построим по приведенному уравнению триггер вначале на элементах ИЛИ-НЕ, а затем на элементах И-НЕ. Для этого опустим верхние индексы и преобразуем хто уравнение так, чтобы оно не содержало операции конъюнкции:
Полученное выражение определяет схему с обратной связью, которая приведена на рис. 9,а. Пользуясь равенством
получаем схему триггера типа R-S на элементах И-НЕ, изображенную на рис. 9,б. Кружки на входах условного обозначения триггера показывают, что изменение состояния триггера должно происходить при действии сигнала, соответствующего
нулю.
Для того чтобы лучше представить работу триггера, проанализируем схему на рис. 9,а. Обозначим выход первой логической схемы буквой w и вычислим выходные сигналы логических элементов для различных значений входных сигналов.
Действуя описанным способом, нетрудно построить и проверить работу R-S-триггеров с дополнительными входами установки в нуль и единицу. Например, работа триггера с дополнительным входом R1 описывается характеристическим уравнением:
Схема триггера, построенная по этому уравнению на элементах И-НЕ, приведена рис. 10.
Пред.Страница
След.Страница Раздел Содержание
АСИНХРОННЫЙ ТРИГГЕР J-K С ЗАДЕРЖКОЙ
На выходе асинхронного триггера с задержкой изменение сигнала может произойти только после окончания действия входного сигнала х, звавшего такое изменение. Если после сигнала х подать сигнал, вызывающий переход в первоначальное состояние, то ожидаемое изменене сигнала на выходе может не произойти: выходной сигнал будет потерян. Чтобы избежать подобных ситуаций, на практике вводят ограничения на последовательности сигналов, подаваемых на вход триггера. Например, для асинхронного триггера J-K последовательности 11 01, 10 01, 01 10, 11 10 являются запрещенными, поскольку каждая из них приводит к потере выходного сигнала. Рассмотрим, как реагирует триггер на одну из эти х последовательностей. Пусть триггер находится в состоянии 0, которому соответствует выходной сигнал 0, и на вход поступает сигнал 11. Под действием этого сигнала триггер должен перейти в состояние, отмеченное выходным сигналом 1. Если же после 11 на вход подать сигнал 01, то триггер вернется в состояние 0 и выходной сигнал, соответствующий входному сигналу 11, окажется потеренным.
Диаграмма и таблица переходов асинхронного J-K-триггера с задержкой, построенные с учетом перечисленных ограничений, приведены на рис. 17. Таблицы функций возбуждения R-S-триггеров изображены на рис. 18, а схема триггера - на рис. 19.
Пред.Страница
След.Страница Раздел Содержание
Асинхронным
. Следует заметить, что в дальнейшем при более детальном анализе процесса работы автомата придется отказаться от этого определения и допустить наличие неустойчивых состояний.
Пред.Страница
След.Страница Раздел Содержание
Дискретного времени
. Входные сигналы такого автомата подобны сигналам импульсного типа (рис. 1,а). При этом были приняты следующие ограничения:
- сигналы могут поступать на вход автомата только в строго определенные моменты времени, задаваемые тактирующей последовательностью СИ с постоянным периодом Т;
- длительность входных сигналов t пренебрежимо мала (t ® 0);
- в промежутках между тактирующими сигналами на входе автомата сигнал отсутствует.
Модель автомата, построенная для токого сигнала, соответствует схемам, работающим с сигналами импульсного типа, элементы которых не имеют гальванической связи.
Входные сигналы асинхронного автомата подобны сигналам потенциального типа (рис. 1,б ). Такие сигналы должны обладать следующими свойствами:
- сигнал присктствует на входе автомата в каждый момент времени;
- длительность входного сигнала не ограничена и превышает некоторую минимальную величину t0;
- изменения входного сигнала могут происодить в произвоьные моменты времени.
Перечисленные свойства позволяют считать, что асинхронный автомат работает в непрерывном времени.
Ограничимся, так же как и для синхронного автомата, рассмотрением только двоичных входных сигналов. При этом модель асинхронного автомата может быть использована для описания работы схем, построенных из элементов потенциального типа. Допустим, что под действием входного сигнала pk синхронный автомат А переходит в состояние si. Согласно приведенным свойствам сигналов потенциального типа, pk присутствует на входе автомата и после того, как свершится переход, причем момент его окончания заранее не известен. Следовательно, выполнив такой переход, автомат должен оставаться в состоянии si до следующего изменения сигнала на входе. Описанную ситуацию можно обобщить в виде следующего определения. Если автомат совершает переход из некоторого состояния sj под действием сигнала pk в состояние si, т. е. j(sj, pk) = si, и остается под действием сигнала pk в этом же состоянии j(sj, pk) = si, то такое состояние называетсяустойчивым.
Приведенное определение позволяет нам уточнить понятие асинхронного автомата. Автомат, все состояния которого устойчивы, называется
Функциями возбуждения
. В качестве элементов памяти на практике чаще всего используют элементарные автоматы.
В приведенной схеме наборы значений входных переменных x1, x2, ..., xn соответствуют буквам входного алфавита Р абстрактного автомата, наборы выходных переменных z1, z2, ..., zm - буквам выходного алфавита W, y1, y2, ..., yh
- состояниям абстрактного автомата. Пред.Страница След.Страница Раздел Содержание
Функциямиями выходов
автомата.
Рассматриваемая схема состоит из двух частей: комбинационной схемы (КС) и набора элементов памяти (ЭП). Переменные y1, y2, ..., yh, соответствующие выходным сигналам элементов памяти, называют внутренними переменными автомата. Переменные y1', y2', ... , yh' используются в схеме для обозначения входных сигналов, изменяющих состояние элементов памяти, и называют
Гонками
элементов памяти. При этом говорят, что состязание выигрывает элемент, обладаюший наименьшей задержкой.
Состязания элементов памяти приводят к тому, что автомат при зменении состояния не сразу оказывается в том состоянии, которое запланировано условиями работы, а переходит в него через несколько нпредусмотренных транзитных состояний. В результате такого перехода, независимо от соотношений задержек элементов памяти, авомат достигает того состояния, в которое он должен перейти, то состязания называются
некритическими. Если же существует жотя бы одно сочетание значений задержек элементов памяти, при котором автомат не достигает запланированного состояния, то состязания называются критическими.
Рассмотрим, как происходят состязания на примерах, используя таблицу переходов, приведенную на рис. 3. В клетках таблицы, соответствующих сходным состояниям, находятся кружки с цыфрой. Каждая цыфра является номером рассматриваемого примера. Точками в таблице отмечены клетки, соответствующие транзитным состояниям, а кружочками с точкой - состояния, в которых оказывается автомат после завершения перехода. Горизонтальные линии со стрелкой определяют изменения входных сигналов, вертикальные сплошные линии - переходы автомата, а пунктирные линии - переходы обусловленные состязаниями.
Первый пример показывает как совершаются переходы в приведенной таблице. При этом автомат проходит последовательность состояний 000-001-101-111. Заметим, что в этой последовательности каждый переход в новое состояние совершается с изменением значения только одной внутренней переменой (одного элемента памяти), поэтому состязания отсутствуют.
Во втором примере первый переход в последовательности состояний 101-110 выполняется с изменением значений двух внутренних переменных y2
и y3. Если время задерхки элементов памяти, соответствующим этим переменным, одинаково t32 = t33, то состязания отсутствуют и автомат проходит последовательность состояний 101 - 110-100-000.
Если же t32 < t33, то состязание выигрывает второй элемент памяти и из состояния 101 автомат попадает в состояние 111, совершая незапланированный переход. В этом случае автомат проходит последовательность состояний 101-111-110-100-000, заканчивающуюся устойчивым состоянием 000, в которое автомат должен попасть при отсутствии состязаний. Если t32
> t33, то автомат проходит последовательность состояний 101-100-000 и так же достигает заданного устойчивого состояния 000. Следовательно, в рассматриваемом случае имеют место некритические состязания. Пример показывает также, что некритические состяния огут изменять время, затрачиваемое автоматом на смену состояния, поскольку автомат может совершать различное число переходов в зависимости от соотношения между задежками.
В третьем примере (при отсутствии состязаний) автомат должен из состояния 111 перейти в состояние 100. Если же t32 > t33, то состязани выигрывает третий элемент памяти, и автомат вместо состония 100 оказывается в состоянии 110, которое является устойчивым. В этом случае имеют место критические состязания, поскольку автомат не достигает заплпнированного состояния 100.
Четвертый пример, приведенный в таблице, не связан с состязаниями элементов памяти. Он представляет собой иллюстрацию явления, встречающегося в асинхронных автоматах, которое называется генерацией. Это явление заключается в том, что автомат последовательно совершает переходы между транзитными состояниями, возвращаясь каждый раз в исходное состояние. Генерация прерывается при изменении входных сигналов. Однако при этом сосояние, в котором окажется автомат, зависит от того, с каким транзитным состоянием совпало изменение входного сигнала.
В заключение отметим, что одной из основных задач стадии структурного синтеза асинхронных автоматов является построение схемы без критических состязаний. Эта задача решается обычно на этапе кодирования состояний автомата.
Пред.Страница
След.Страница Раздел Содержание
ЭВРИСТИЧЕСКИЙ СПОСОБ КОДИРОВАНИЯ
Универсальный способ кодирования редко используется на практике для реализации автоматов с большим числом состояний, поскольку схемы в этом случае получаются весьма сложными за счет большого чсисла элементов памяти. Чаще всего при решении практических задач применяют эвристический способ, основанный на последовательном введении дополнительных состояний и увеличении числа внутренних переменных. В качестве иллюстрации этого способа рассмотрим два примера.
Прежде всего попытаемся реализовать автомат А1 с использованием двух внутренних переменных. Для этого воспользуемся графом связи этого автомата, изображенным на рис. 4,б. Нетрудно убедиться в том, что закодировать такой граф и помощью четырех кодов таким образом, чтобы при каждом переходе изменялось значение только одной переменной, невозможно. Выберем вариант кодирования, при котором наибольшее число переходов выполняется с изменением одной переменной (в нашем примере два перехода), и введем дополнительное состояние для перехода, при котором изменяются две переменные. В результате получаем граф, приведенный на рис. 5. Таблица переходов автомата при таком кодировании изображена в виде табл. 4.
,
В качестве второго примера рассмотрим кодирование автомата А2, заданного табл. 5. Граф связей этого автомата приведен на рис. 6. Для однозначного кодирования четырех состояний достаточно двух внутренних переменных. Однако выполнить кодирование без состояний с помощью двух переменных оказывается невозможно. Увеличим число внутренних переменных до трех и снова попытаемся произвести кодирование без введения дополнительных состояний.
Рассматривая различные варианты, нетрудно убедиться, что получить кодирование без состояний в этом случае также невозможно. Выберем вариант кодирования, позволяющий получить наибольшее число переходов с изменением одной переменной и введем дополнительные состояния. В результате получаем граф автомата, изображенный на рис. 6,б. Используя этот граф, нетрудно построить кодированную таблицу переходов автомата А2 (табл. 6).
В заключение отметим, что описанный универсальный способ кодирвания не является единственным. Например, в работах [1, 3] можно найти описание способа Хаффмэна, который позволяет закодирвать любой автомат, имеющий m состояний, используя 2]log2m[ - 1 элементов памяти, где ]a[ означает ближайшее целое не меньше а. На практике же для построения схем без состояний чаще всего применяют структурный способ, основанный на использовании удвоенного числа элементов памяти. Этот способ будет рассмотрен подробнее в параграфе, посвященном построению элементов памяти, а также в следующем выпуске.
Пред.Страница
След.Страница Раздел Содержание
Кодирование с числом элементов памяти, равным числу состояний
Этот способ кодирования заключается в том, что каждому из l состояний автомата ставится в соответствие один элемент памяти. В каждый момент времени только один элемент памяти должен находиться в состоянии “1”, а остальные - в состоянии “0”, поскольку автомат может находиться только в одном состоянии. Пример кодирования пяти состояний описанным способом приведен в табл. 11. Используемый способ часто называют кодированием с применением кодов “один из l”. Следует отметить, что этот способ кодирования позволяет упростить процедуру построения функций возбуждения и функций выходов за счет исключения этапа минимизации. Остановимся на этом вопросе подробнее.
Если для кодирования состояний используются l двоичных переменных у1, y2
, ..., yl, то существует 2l
различных двоичных наборов значений этих переменных. Обозначим множество всех двоичных наборов Н. Разобьем это множество на l пересекающихся подмножеств H1, H2, ..., Hl
таким образом, чтобы в каждое подмножество Hl входили 2l-1 двоичных наборов, определяющих переключательную функцию вида yi. В каждое подмножество Hi
входит только один набор ~xi, используемый при кодировании. Он состоит из l - 1 нуля и одной единицы, стоящей на i-м месте. При этом множество Hi ' = Hi - ~xi, представляет собой совокупность неиспользованных двоичных наборов.
Пусть автомат переходит из состояния s', которому приписан код ~xi , в состояние s”, которому приписан код ~xi, под действием набора входных сигналов d1, d2, ...,dn. Если в качестве элемента памяти используется триггер D, то функция возбуждения, реализующая такой переход , имеет вид :
Представим эту функцию следующим образом: yk' = x1d1 x2d2
... xndnc(у1, y2, ..., yl). Функция c(у1, y2, ..., yl). является неполностью определенной переключательной функцией. Доопределим ее единицами на всех наборах, входящих в множество Hi'. В результате получаем функцию, совокупность единичных наборов которой совпадает с множеством Hi. Согласно построению, такая функция является переменной yi, поэтому имеем yk' = x1d1 x2d2
... xndn уi
Приведенные рассуждения показывают, что при выбранном способе кодирования каждый дизъюнктивный член функций возбуждения (функций выхода) содержит только одну внутреннюю переменную, определяющую соответствующее состояние автомата. Пред.Страница След.Страница Раздел Содержание
КОДИРОВАНИЕ СОСТОЯНИЙ
Состязания возникают в схемах, построенных на реальных элементах памяти с задержками, только в тех случаях, когда срабатывают одновременно несколько элементов памяти. Следовательно, для того, чтобы построить схему без состязаний, необходимо закодировать состояния автомата таким образом, чтобы при каждом переходе изменялось состояние только одного элемента памяти. Например, если в автомате определен переход из состояния si в состояние sj, то их следует кодировать соседними кодами. Напомним, что соседними называются коды, отличающиеся значением только одного разряда.
Если автомат имеет l состояний, то кодирование соседними наборами при использовании h = ]log2l[ внутренних переменных в большинстве случаев выполнить невозможно, поэтому в процессе кодирования расширяют алфавит состояний автомата и вводят дополнительные неустойчивые состояния, которые обеспечивают реализацию всех переходов в схеме с изменением только одного элемента памяти.
Пред.Страница
След.Страница Раздел Содержание
Кодрование состояний с использованием соседей первого и второго рода
Метод кодирования состояний, основанный на применении соседей, не имеет строгого обоснования. С его помощью, как правило, удается получить некоторое уменьшение сложности блока комбинационной схемы, реализующего функции возбуждения. При изложении основ этого метода мы будем предполагать, что в качестве элемента памяти используется триггер Д. Однако на практике его применяют и для элементов памяти других типов.
| Определение. Если два состояния sk иsj под действием одного и того же входного сигнала х переходят в одно и то же состояние s1 , то они называются соседями первого рода. |
На рис. 18 приведен фрагмент графа автомата. иллюстрирующий это определение. Закодируем соседей первого рода показано на рис. 18. Тогда элементарные соседними кодами a1, a2, ..., ah-1, ah и a1, a2, ..., ah-1, щ ah, как это конъюнкции, определяющие состояния sk и sj
, войдут во все функции возбуждения yi ', для которых соответствующий компонент di = 1. Найдем аналитическое выражение для части функций возбуждения, содержащей эти элементарные конъюнкции
Пред.Страница След.Страница Раздел Содержание
Обобщенная структурная схема автомата
На стадии абстрактного синтеза обычно пользуются представлением автомата в виде одного блока, имеющего один вход и один выход. На стадии структурного синтеза автомат изображают в виде обобщенной структурной схемы, приведенной на рис. 1 т n входных и m выходных каналов, по которым в подавляющем большинстве случаев передаются двоичные сигналы x1, x2, ..., xn
и z1, z2, ..., zm. Переменные x1, x2, ..., xn
называют
ОБЩИЕ ПОЛОЖЕНИЯ
Особенности асинхронного автомата, или точнее асинхронной модели автомата, определяются свойствами входных сигналов. Напомним, что при построении модели автомата синхронного типа мы пользовались понятием
ОПИСАНИЕ РАБОТЫ АСИНХРОННОГО АВТОМАТА
Работа асинхронного автомата, так же как и автомата синхронного типа, может быть описана с помощью таблицы переходов и выходов или с помощью графа. Однако переход к сигналам, обладающим ненулевой длительностью, несколько усложняет такое описание.
Остановимся вначале на способе построения графа асинхронного автомата по заданному графу синхронного автомата. Пусть задан синхронный автомат, граф которого приведен на рис. 2,а. При построении этого графа длительность входных сигналов не учитывалась. Если же считать, что импульсные сигналы, подаваемые на вход, обладают конечной длительностью, то необходимо уточнить, в каком состоянии должен находиться автомат в момент действия каждого сигнала. Это можно сделать путем введения дополнительных состояний в заданный граф для каждого перехода, как это показано на рис. 2,б. Полученный граф определяет асинхронный автомат, поскольку все состояния автомата являются устойчивыми
В асинхронном автомате все переходы осуществляются между устойчивыми состояниями, что создает дополнительные сложности при построении таблицы переходов. Если состояние si является устойчивым, то в клетке таблицы переходов, определяемой строкой, отмеченной состоянием si, и столбцом, отмеченным входным сигналом pk, должен быть записан символ состояния si, поскольку j(si, pk) = si. Таким образом, для устойчивых состояний в таблице переходов асинхронного автомата необходимы дополнительные средства, указывающие, в какое состояние должен перейти автомат при изменении входного сигнала. Это затруднение решается следующим образом. Процесс изменения состояния автомата разбивается на два этапа, полагая, что вначале происходит изменение входных сигналов, а состояние автомата остается неизменным, а затем уже происходит изменение состояния при новых значениях входных сигналов.Первому этапу этого процесса соответствует перемещение по строке таблицы переходов, отмеченной старым состоянием, в столбец отмеченный новыми значениями входных сигналов. Итак, первый этап однозначным образом определяет новую клетку таблицы, которая соответствует переходному состоянию автомата.
Такие состояния будем называть транзитивными. Запишем в этой клетке символ того состояния, в которое должен перейти автомат. При этом второму этапу изменения состояния соответствует перемещение по столбцу, определяемому новыми входными сигралами, в строку, отмеченную тем состоянием, в которое автомат должен перейти. Для того чтобы не путать устойчивые состояния с указателями перехода, используемыми на втором этапе, условимся заключать символы, соответствующие устойчивым состояниям, в круглые скобки. Примером таблицы переходов и выходов асинхронного автомата является табл. 1. Эта таблица построена по графу, приведенному на рис. 2,б.
Рассмотрим, как выполняются переходы в табл. 1 на примере. Допустим, что автомат находится в состоянии 3 под действием входных сигналов 00. Согласно таблице переходов, это состояние является устойчивым. Если теперь значение входных сигналов изменится на 10, то для того, чтобы найти в какое состояние перейдет автомат, необходимо выполнять перемещение по третьей строке в столбец, отмеченный сигналами 10. В определенной таким образом клетке таблицы находится номер состояния, в которое переходит автомат - это состояние 5*. Перемещаясь по вертикали в столбце 10 до строки 5*, находим, что это состояние является устойчивым. Следовательно, переход завершен. В рассмотренном примере при переходе из одного устойчивого состояния в другое автомат миновал одно транзитное состояние. В общем случае изменение состояния автомата может происходить с переходом через несколько транзитных состояний, которые, конечно, должны быть расположены в одном и том же столбце таблицы переходов. Примеры таких переходов будут приведены в следующем параграфе.
Пред.Страница
След.Страница Раздел Содержание
Основные этапы структурного синтеза
Процедуру структурного синтеза удобно рассматривать расчленив ее предварительно на несколько связанных между собой этапов.
1. Выбор структурной схемы автомата. Этот этап синтеза во многом определяет последовательность построения схемы. Примеры того, как заданная система элементов влияет на структурную схему автомата, были приведены в предыдущем параграфе. Структурные схемы автомата, применяемые при построении схемы на потенциальных элементах, будут рассмотрены в п. 9, а структурные схемы, использующие типовые блоки, будут описаны в п. 10. Основная трудность этого этапа заключается в отсутствии формальных критериев для выбора структурной схемы. Одним из главных факторов, определяющих выбор структурной схемы, является опыт разработчика.
2. Кодирование входных и выходных сигналов . Кодирование входных сигналов заключается в том, что каждой букве pi входного алфавита абстрактного автомата однозначным образом ставится в соответствие набор значений двоичных переменных х1, х2, ..., хn. Очевидно, что кодирование является однозначным, если число букв входного алфавита не превышает числа различных двоичных наборов переменных х1, х2, ..., хn. Исходя из этого, количество двоичных переменных n, необходимое для кодирования r букв входного алфавита, можно определить из условия r Ј 2n. Кодирование выходных сигналов состоит в том, что буквам выходного алфавита wi абстрактного автомата аналогичным образом ставятся в соответствие наборы значений выходных переменных z1, z2, ..., zm. Результаты кодирования обычно заносятся в таблицы кодирования входных и выходных сигналов.
В некоторых задачах кодирования входных и выходных сигналов задается в качестве условий работы схемы на этапе абстрактного синтеза. В таких случаях в структурную схему автомата могут быть включены преобразователи кодов. При этом кодирование заключается в том, что каждому набору значений переменных х1, х2, ..., хn однозначным образом ставится в соответствие набор переменных х1', х2', ..., хq', а каждому набору переменных z1, z2, ..., zm - набор переменных z1', z2', ..., zs'. Заметим, что в качестве преобразователей кодов на практике часто используют дешифраторы. Необходимо иметь в виду, что кодирование входных и выходных сигналов может существенно влиять на сложность комбинационной части схемы так же, как и кодирование состояний автомата.
Пред.Страница След.Страница Раздел Содержание
PART
Пред.Страница След.Страница Раздел Содержание
Синхронизирующие импульсы, подаваемые на вход счетчика, вызывают последовательное изменение его состояний. Выходные сигналы счетчика, определяющие его состояния, подаются на вход дешифратора. Код каждого состояния дешифратор преобразует в единичный сигнал на единственном выходе. Таким образом, последовательность состояний счетчика преобразуется в последовательность сигналов на выходах дешифратора a1 , a2 , ..., an ,a1 ', a2 ', ..., an '.
Эти сигналы осуществляют последовательную запись букв входного слова в соответствующие элементы памяти и считывание букв выходного слова.
Заметим, что используемый способ построения распределителя не является единственно возможным. Например, в качестве распределителя может быть применен регистр со сдвигом, в котором записана одна единица.
Приведенная на рис. 25 схема предназначена для переработки слов двоичного алфавита. Если же для представления каждой буквы входного алфавита используется k двоичных символов, то в рассматриваемой схеме потребуется использовать k элементов памяти для хранения каждой буквы входного слова.
В заключении отметим, что применение описанной схемы существенно упрощает процедуру синтеза, которая в этом случае сводится к реализации комбинационной схемы для системы переключательных функций. Пред.Страница След.Страница Раздел Содержание
Построение функции выхода
Пред.Страница След.Страница Раздел Содержание
5. Построение функции выхода . В автомате Мили каждая функция выхода zi
определяет соответствующий компонент набора выходных сигналов. Функции выхода при структурном синтезе соответствуют функции выхода абстрактного автомата. Они зависят от внутренних переменных y1, y2, ..., yh и входных переменных х1, х2, ..., хn
. Существенно, что значения переменных, определяющих zi, относятся всегда к одному и тому же моменту времени, поэтому функции выхода являются переключательными функциями:
Функции выхода автомата Мура в каждый момент времени определяют совокупность выходных сигналов:
6. Реализация функций выхода и функций возбуждения. Этот этап включает в себя действия, связанные с построением аналитического представления для переключательных функций, входящих в системы (2) и (3), их минимизацию, факторизацию и преобразования в операторную форму для заданной системы элементов. Заметим, что на этом этапе целесообразно также выполнять построение преобразователей кодов, которые обычно реализуются либо как система переключательных функций, либо в виде схемы “дешифратор - шифратор”.
7. Графическое изображение полной схемы автомата. Пред.Страница След.Страница Раздел Содержание
Построение функций возбуждения
Вначале остановимся на построении функций возбуждения и выходов для автомата, заданного в виде графа. Согласно последовательности структурного синтеза, описанного в п. 2, этапу построения функции возбуждения должен предшествовать этап кодирования состояний, поэтому полагаем, что каждому узлу автомата приписан код состояния. Фрагмент такого графа приведен на рис. 11.
Автомат, задаваемый этим фрагментом, переходит из состояния
ПОСТРОЕНИЕ ЭЛЕМЕНТОВ ПАМЯТИ
Настоящий параграф посвящен построению элементов памяти - триггеров на элементах потенциального типа. Такие триггеры выпускаются промышленностью в виде интегральных микросхем и широко применяются для постоения узлов и блоков ЦВМ. На практике используется большое число триггеров различного вида. В основном они отличаются логикой работы, наличием синхронизации и задержки при установлении входных сигналов.
Логика работы триггера определяется его реакцией на входные сигналы. При этом различают следующие типы триггеров.
Построить схему для автомата, описанного
Построить схему для автомата, описанного в примере 1, используя в качестве элемента памяти триггер R-S.
Если оставить кодирование входных сигналов и состояний таким же как и в предыдущем примере, то функции выхода в новой схеме не изменятся. Диаграммы для функций возбуждения триггера R-S изображены на рис. 16. На этом же рисунке приведены дизъюнктивные нормальные формы функций: y'1R, y'1S, y'2R, y'2S. Полная схема автомата изображена на рис. 17.
Пред.Страница
След.Страница Раздел Содержание
СОСТЯЗАНИЕ ЭЛЕМЕНТОВ ПАМЯТИ
Переход к асинхронной модели автомата связан, прежде всего, с изменнием ограничений, накладываемых на характер входных сигналов. Использование сигналов, присутствующих на входе в каждый момент времени, позволяет учитывать реальные процессы, происходящие при изменении состояний автомата, и связанные с задержками срабатывания элементов памяти. Такие задержки обусловлены как физическими прицессами, протекающими в реальных элементах, так и распределенными параметрами соединений. Величина задержки срабатывания каждого конкретного элемента памяти, как правило, неизвестна. Эта величина обычно характеризуется максимальной задержкой tзm, которая принимается пстоянной для элментов опредленного типа. При этом предполагают, что величина задержки каждого конкретного элемента tзm заключена в прделах 0 < tзi <= tзm.
Наличие различных задержек элементов памяти приводит к тому, что при переходе автомата из одного состояния в другое возникают ситуации, когда жлементы памяти срабатывают не одновременно. Последовательность срабатывания элементов памяти определяется соотношением их задержек. Очевидно, что первым должен срабатывать элемент, обладающийнаименьшей задержкой. Такое явлее называется состязаниями, или
Структурная схема на элементах импульсного типа
При построении схемы из логических элементов импульсного типа, работающих с импульсными сигналами длительностью t, и элементов памяти с выходными сигналами потенциального типа в структурную схему необходимо включить цепи синхронизации и линии задержки (ЛЗ), как это показано на рис. 4. Линии задержки в такой схеме
осуществляют задержку входных сигналов элементов памяти. Если время задержки (tз) этих линий немного больше величины t, то состояние элементов памяти остается неизменным на время действия синхронизирующего сигнала (СИ). Пред.Страница След.Страница Раздел Содержание
Структурная схема с преобразователями входных и выходных сигналов
В общем случае комбинационная схема в приведенной структурной схеме автомата может решать несколько различных задач. Если эту схему разбить на подсхемы так, чтобы каждая задача решалась отдельной подсхемой, то структурная схема автомата может быть представлена в виде, изображенном на рис. 2. В этой схеме комбинационная схема КС1 вырабатывает функции выхода, КС2 - функции возбуждения, преобразователь кодов ПК1 используется для перекодирования входных сигналов, а преобразователь кодов ПК2 - для преобразования выходных сигналов. Наличие преобразователей кодов ПК1 и ПК2 не является обязательным в структурной схеме автомата, но в некоторых случаях их включение в схему позволяет добиться уменьшения сложности, упростить процесс построения или контроля работы схемы автомата.
Необходимо отметить, что вид структурной схемы автомата в сильной степени зависит от используемой системы логических элементов. Например, при построении схемы на элементах с синхронизацией, сохраняющих результат логической операции до момента прихода считывающего сигнала, необходимость в элементах памяти часто отпадает. В этом случае структурная схема автомата может быть изображена в виде, приведенном на рис. 3.
Пред.Страница
След.Страница Раздел Содержание
Структурная схема с удвоенным числом элементов памяти
В структурной схеме автомата, выполненного на элементах импульсного типа (рис. 4), линии задержки используются для сохранения схемы, относящегося к моменту прихода входного сигнала, на время действия синхронизирующего сигнала. Такая задержка изменения состояния гарантирует отсутствие состязаний в схеме , которые могли бы возникнуть во время действия синхронизирующего сигнала.
Применение линий задержки в схемах в настоящее время ограничивается трудностями их изготовления в виде микроэлектронных интегральных схем. Последнее обстоятельство привело к тому, что на практике начали заменять линии задержки элементами памяти, которые в потенциальных системах элементов, обычно строятся на основе логических элементов и не нарушают технологической целостности схемы.
Структурная схема автомата с двумя ярусами элементов памяти изображена на рис. 24. Первый ярус элементов памяти используется в схеме для хранения кода состояния, относящегося к моменту прихода входного сигнала. Выходные сигналы элементов памяти этого яруса подаются на вход комбинационной схемы. Второй ярус элементов памяти предназначен для хранения кода состояния, в которое переходит автомат в рассматриваемом такте. Этот код должен передаваться в элементы памяти первого яруса либо в момент изменения входного сигнала, либо в момент его отсутствия.
В схеме используется два синхронизирующих сигнала t1 и t2. Сигнал t2
должен быть несколько сдвинут во времени относительно момента подачи входного сигнала. Такой сдвиг позволяет исключить влияние на элементы памяти переходных процессов, обусловленных риском в комбинационной части схемы. Сигнал t2 подается на элементы конъюнкции и разрешает прохождение сигналов, соответствующих значениям функций возбуждения, на входы элементов памяти второго яруса. Сигнал t1 осуществляет передачу кода состояния из элементов памяти второго яруса в элементы памяти первого яруса. Этот сигнал должен подаваться в схеме обязательно после окончания действия сигнала t2 и входного сигнала.
Необходимо отметить, что приведенная структурная схема широко используется на практике при построении как типовых блоков цифровых вычислительных устройств: счетчиков, регистров, делителей и т. п., так и управляющих схем.
Пред.Страница
След.Страница Раздел Содержание
Структурные схемы с дешифратором
На рис. 22 приведена структурная схема автомата с двумя дешифраторами. Дешифратор ДС1 служит в схеме для преобразования входных сигналов, а дешифратор ДС2 - для преобразования кодов состояний.
Число выходов каждого дешифратора определяется числом различных наборов значений его входных переменных. Каждых входной набор возбуждает единственный сигнал, соответствующий единице, на выходе дешифратора. Таким образом, в каждый момент времени на одном из выходов дешифратора имеется сигнал, соответствующий единице, а на остальных выходах - сигналы, соответствующие нулю. Это обстоятельство позволяет нам считать схемы с дешифратором состояний разновидностью схем с кодированием “один из l” и использовать свойства таких кодов и способы построения функций возбуждения и выходов, описанные в предыдущем параграфе, для рассмотрения схем.
Включение дешифратора входных сигналов в схему позволяет применить для описания переходов двухместные конъюнкции. При этом функции возбуждения и функции выходов могут быть представлены в виде: yi' = Ъ gkxs';
zj = Ъ gpxq'.
Принцип реализации таких функций показан на рис. 22 в поле комбинационной схемы. Пред.Страница След.Страница Раздел Содержание
СВЯЗЬ АСИНХРОННОГО АВТОМАТА С ВНЕШНЕЙ СРЕДОЙ
Использование сигналов потенциального типа, длительность которых не ограничена и время изменения не фиксировано, осложняет работу с кодами, поступающими последовательно на вход асинхронного автомата. Основная трудность заключается в том, что с помощью одного потенциального сигнала с неопределенной длительностью нельзя закодировать последовательность из одинаковых цифр. Например, пусть требуется передать на вход автомата последовательный код, состоящий и четырех единиц. Если используется двоичный потенциальный сигнал, то каждой единице будет соответствовать одно и то же значение напряжения на входе, и автомат воспримет такую последовательность как один сигнал равный единице. В общем случае такая неоднозначность при передаче последовательных двоичных кодов будет возникать для любой группы стоящих рядом одинаковых цифр.
Для того чтобы сделать возможной передачу последовательных кодов при потенциальном характере сигналов, расширяют входной алфавит автомата. Такое расширение соответствует введению одной дополнительной линии передачи x’ (рис. 7), которая используется для сихронизации или для пересылки указателя при передаче последовательности одинаковых цифр. В зависимости от того, как используется линия x’, возможны несколько способов организации передачи. Рассмотрим три основных способа, которые приведены на рис. 8.
Первый способ предполагает использование линии x’ для передачи импульса определенной длительности t, который формируется для каждой позиции кода, где расположена цифра, совпадающая с предыдущей (рис. 8,а ). Этот способ соответствует преобразованию входных слов автомата, при котором между каждыми двумя одинаковыми цифрами вводится дополнительный символ-разделитель. На рис. 8,а используется даже два разделителя: один применяется в последовательности единиц, а другой - в последовательности нулей. Если обозначить r1 - разделитель единиц, а r0 - разделитель нулей, то входная последовательность 0110010 может быть записана следующим образом 01r110r0010.
В рассматриваемом случае входной алфавит должен состоять из четырех букв P = {00, 01, 10, 11}, где буквы 00 и 10 соответствуют нулю, а буквы 01 и 11 - разделителю нулей и разделителю единиц. При этом входная последовательность имеет вид: 00 10 11 10 00 01 00 10 00. Следует отметить, что использование разделителей приводит к необходимости выравнивания длины входных слов, а также к увеличению времени передачи каждого слова.
При втором способе по линии x’ передается синхронизирующая последовательность импульсов с длительностью t и периодом 2t (рис. 8,б ). Такой способ предплагает использование для каждого символа, подаваемого на основной вход автомата, двух различных кодов. Например, в случае двоичных кодов, единице ставятся в соответствие коды 10 и 11, а нулю - коды 00 и 01. При этом кодирование соседних букв в каждом входном слове должно выполняться таким образом, чтобы коды таких букв имели различные значения в позиции, соответствующей синхронизирующему сигналу. Например, последовательность 0110010, для рассматриваемого случая можно представить так: 00 11 10 01 00 11 00.
Существенно, что описанный способ построения последовательного кода не приводит к изменению длины входной последовательности и увеличению времени ее передачи.
Третий способ, изображенный на рис. 8,в отличается от предыдущего только тем, что в дополнительной линии x’ вместо импульсного сигнала используется сигнал потенциального типа. При этом кодирование выполняется таким же образом, как и в предыдущем случае.
В заключении следует отметить, что при работе с сигналами потенциального типа на стадии абстрактного синтеза автомата приходится вводить доплнительный этап, связанный с перекодированием слов заданного оператора в соответствии с выбранным способом построения последовательного кода. Если автомат должен вырабатывать также последовательный код, то необходимо предусмотреть и соответствующее кодирование выходных слов заданного оператора.
Пред.Страница
След.Страница Раздел Содержание
T - ТРИГГЕР С ЗАДЕРЖКОЙ
В качестве примера рассмотрим построение асинхронного Т-триггера с задержкой по М-S-схеме. Диаграмма переходов такого триггера изображена на рис. 15,а. Состояния на диаграмме закодированы таким образом, чтобы при каждом переходе изменялась только одна переменная. Таблица переходов, соответствующая этой диаграмме, приведена на рис. 15,б. Функции возбуждения триггеров типа R-S, построенные по этой таблице, приведены на рис. 15,в, а схема Т-триггера - на рис. 16.
Пред.Страница
След.Страница Раздел Содержание
Типы элементов памяти
В качестве элементов памяти на стадии структурного синтеза чаще всего используют элементарные автоматы с двумя выходными сигналами. Однако в последнее время в связи с разработкой больших интегральных схем представляет интерес использование в качестве элементов памяти широко применяемых в цифровых устройствах типовых схем: счетчиков и регистров.
Элементы памяти с двумя выходными сигналами обычно называются триггерами. В большинстве случаев триггер является автоматом Мура. Он может иметь один или несколько входов. Работа триггера, как и любого автомата, описывается с помощью таблицы переходов.
На практике часто возникает задача построения триггеров из элементов заданной системы. Для этой цели используют характеристическое уравнение триггера, которое определяет состояние, в которое должен перейти триггер qt+1 в зависимости от входного сигнала xt
и состояния qt, в котором находится триггер
ТРИГГЕР D-V С ЗАДЕРЖКОЙ И СИНХРОНИЗАЦИЕЙ
В качестве примера рассмотрим построение D-V-триггера с задержкой и синхронизацией. Диаграмма и таблица переходов такого триггера изображена на рис. 21. Таблицы функций возбуждения приведены на рис. 22, а схема триггера на рис. 23.
Пред.Страница
След.Страница Раздел Содержание
ТРИГГЕР J-K С ЗАДЕРЖКОЙ И СИНХРОНИЗАЦИЕЙ
Применение асинхронных триггеров с задержкой позволяет устранить состязания в схемах, но не исключает влияния задержек сигналов, подаваемых на разные входы триггера, и риска в комбинационной части схемы автомата. Чтобы устранить влияние этих факторов, используем триггер с задержкой и синхронизацией. При этом длительность синхронизирующего сигнала выбирается, как правило, меньшей, чем длительность сигналов, подаваемых на управляющие входы. Временная даграмма, приведенная на рис. 20, поясняет работу триггера с задержкой и синхронизацией. На диаграмме изображены коды, определяющие состояние входных сигналов в различные моменты времени. Анализируя эти коды, нетрудно заметить, что принятое соотношение длительности сигналов х и С равносильно ограничению допустимых последовательностей входных сигналов. Например, в рассмааемом случае за сигналом 11 должен обязательно следовать сигнал 10, но никак не сигнал 00. Эти ограничения, так же как и ограничения, возникающие вследствие задержки выходного сигнала, обычно учитывают при построении диаграмм переходов триггеров с задержкой и синхронизацией.
Пред.Страница
След.Страница Раздел Содержание
ТРИГГЕРЫ С СИНХРОНИЗАЦИЕЙ
В реальных схемах в результате действия паразитных задержек сигналы, подаваемые на различные входы триггера, могут приходить одновременно. Если, например, сигнал на вход R триггера типа S, находящегося в состоянии 1, придет раньше сигнала на входе S, то триггер может успеть перейти в состояние 0 на время задержки сигнала, подаваемого на вход S. Чтобы избежать таких ложных срабатываний, обусловленных задержками входных сигналов, используют синхронизирующие или, как их называют, тактирующие сигналы. При этом длительность синхронизирующих сигналов выбирается меньшей, чем длительность сигналов, подаваемых на управляющие входы. Временная диаграмма, поясняющая использование синхронизирующий сигналов, приведена на рис. 12.
Триггеры с синхронизацией должны иметь дополнительный вход С, на который подаются тактирующие сигналы. Работу такого триггера можно описать следующим образом. При отсутствии сигнала на входе С, триггер не изменяет своего состояния. Если же сигнал на входе С равен 1, то он работает как соответствующий триггер без синхронизации. Триггеры рассматриваемого типа строятся обычно на основе асинхронного R-S-триггера. Пример построения S-триггера с синхронизцией приведен на рис.13.
Пред.Страница
След.Страница Раздел Содержание
ТРИГГЕРЫ С ЗАДЕРЖКОЙ
Для того чтобы устранить состязания в схемах асинронных автоматов, используют специального вида триггеры с задержой. Выходной сигна q такого триггера изменятся в момент окончания действия входного сигнала, как показано на рис. 14. В схема, построенных на триггера с задержкой, сигналы обратной связи остаются неизменными во время действия входных сигналов, поэтому состязания в таких схемах, так же, как и схемах с двойной памятью, должны отсутствовать. Задержка выходного сигнала может быть реализована за счет увеличения числа внутренних состояний триггера. При этом необходимо ввести по крайней мере два дополнительных состояния: одно для запоминания новых входных сигналов при переходе из 0 в 1, а другое - для запоминания входных сигналов при переходе из 1 в 0. Следовательно, триггер с задержкой должен иметь не менее четырех состояний.
В зависимости от того, как закодировать эти состояния, можно получить различные виды триггеров. Например, если выполнить кодирование с помощью трех переменных, то можно получить триггер с задержкой на основе трех R-S-триггеров. Если же кодирование производить с использоваием двух внутренних переменных, то можно получить триггеры, построенные по M-S-схеме (сокращение от английский слов Master - Slave). При построении по M-S-схеме используют два асинхронных R-S-триггера, один из которых является главным, а второй вспомогательным.
Пред.Страница
След.Страница Раздел Содержание
УПРАЖНЕНИЯ
Пред.Страница
След.Страница Раздел Содержание
Выбор числа элементов памяти и кодирование состояний автомата
Пред.Страница След.Страница Раздел Содержание
3. Выбор числа элементов памяти и кодирование состояний автомата. Кодирование состояний заключается в том, что каждому состоянию si
О S однозначным образом ставится в соответствие набор внутренних переменных у1, у2, ..., уh. Состояния и соответствующие им коды обычно представляют в виде таблицы, которая называется таблицей кодирования состояний автомата.
Если автомат имеет l состояний, то, для того, чтобы получить однозначное соответствие, необходимо иметь не менее l различных двоичных кодов. Последнее условие можно записать в виде l Ј 2h. Откуда находим
] log2l [ Ј
h, (1)
где ] a [ означает ближайшее целое, не меньшее а.
Из неравенства (1) следует, что минимальное число элементов памяти, необходимое для получения однозначного кодирования,
h = ] log2 l [.
Кодирование состояний существенно влияет на сложность комбинационной части схемы автомата. Для того, чтобы упростить комбинационную схему, часто используют избыточное кодирование, выбирая h большим, чем это необходимо для получения однозначного кодирования. Избыточное кодирование используется также для построения схем без состязаний. Кодирование состояний кажется целесообразным выполнять совместно с кодированием входных и выходных сигналов, однако такая задача оказывается весьма сложной и практически не реализуется.
4. Построение функций возбуждения.Функция возбуждения yi' определяет, какой сигнал нужно подать на вход i-го элемента памяти, чтобы получить код состояния, в которое автомат должен перейти. Функции возбуждения при структурном синтезе соответствуют функциям перехода абстрактного автомата. Это соответствие показывает, что функции возбуждения должны зависеть от внутренних переменных y1, y2, ..., yh, определяющих состояние автомата, и входных переменных х1, х2, ..., хn, относящихся к одному и тому же моменту времени. Последнее обстоятельство позволяет нам рассматривать функции возбуждения как
переключательные функции:
Пред.Страница След.Страница Раздел Содержание
Задача структурного синтеза
Процесс построения схемы автомата обычно разделя ют на две относительно независимых стадии: абстрактный и структурный синтез. На стадии абстрактного синтеза, исходя из заданных условий работы, выполня ется построение таблиц перех одов и выходов автомата. Задачей структурного синтеза является построение функциональной схемы автомата. Исходными данными для стадии структурного синтеза являются таблицы переходов и выходов автомата, система логических элементов, тип элемента памяти, а также дополнительные условия, накладываемые на качество и на работу схемы, например: время работы, допустимость риска, условия связи с внешней средой, стоимость и т. п.
Следует отметить, что исходные данные и круг вопросов, решаемых на стадии структурного синтеза, могут существенно изменяться. Например, в некоторых случаях при структурном синтезе решают задачу выбора т ть искомой схемы. В дальнейшем изложении совокупность исходных данных и задач а структурного синтеза предполагаются такими, как они описаны в начале насто ящего параграфа.
Пред.Страница
След.Страница Раздел Содержание
