2.5. Синтез комбинационных схем, свободных от состязаний

В § 2.2 была показана возможность появления на выходах КС кратковременных ложных значений сигналов из-за состязаний ЛЭ. Эти ложные значения могут привести к неправильной работе других ЛС, в которых выходные сигналы КС используются в качестве входных. Воздействие кратковременных

ложных сигналов на ЛС с низким быстродействием не опасно, так как они не успевают на них отреагировать. Однако поступление ложных значений сигналов, хотя и кратковременных, на быстродействующие ЛС может вызвать ошибки в их работе. Покажем, что если допускаются только соседние изменения состояний входа, то можно синтезировать КС, на выходах которой ложные значения сигналов будут отсутствовать [5, 10].

Комбинационная схема называется свободной от состязаний, если в ней при соседних изменениях состояний входа отсутствуют критические состязания ЛЭ. Пусть функция задана в некоторой нормальной форме в базисе И-НЕ:

где

Если в каждый момент времени может изменяться только один входной сигнал то для ЛЭ, реализующих инверсии контермов, можно использовать модель с виртуальной задержкой (см. рис. 2.4,в). Использовав для ЛЭ И-НЕ второго яруса общую модель (см. рис. 2.4,а), получим схему на рис. 2.15 (паразитные задержки на входах ЛЭ второго яруса просуммированы с задержками ЛЭ первого яруса и перемещены на их входы).

Рис. 2.15

Итак, при соседних изменениях состояний входа динамическая модель КС состоит из статической (безынерционной) части и паразитных элементов задержки, включенных на входах и выходе КС. Для исследования статической части модели форма представления функции не имеет значения, так как в статических моделях изменения всех сигналов происходят мгновенно. Поэтому для анализа статической части модели можно производить любые тождественные преобразования функции в соответствии с правилами алгебры логики.

Поведение КС в переходных режимах определяется ее структурой, задаваемой выражением (2.22), и динамической моделью ЛЭ. Динамическая модель КС, представленная на рис. 2.15, позволяет довольно просто определить условия, при которых могут возникнуть критические состязания ЛЭ. Пусть изменяется только один входной сигнал и в функцию (2.22) входит как

переменная так и ее инверсия Поскольку в общем случае величины задержек не равны между собой, то некоторое время на статическую часть модели КС могут поступать одинаковые значения сигналов или 1) даже при одновременном изменении их в противоположных направлениях на входах динамической модели КС. Таким образом, в переходном режиме сигналы следует считать независимыми сигналами которые могут принимать также значения

На основании выражения (2.22) статическую модель КС можно представить в виде

где функции, не зависящие от и представляющие собой дизъюнкцию некоторого числа контермов;

Тогда поведение КС в переходных режимах можно описать функцией:

Если изменяется только один входной сигнал то некоторое из состояний входа или изменяется на соседнее состояние 1) или соответственно, где так как остальные сигналы сохраняют свои значения. Пусть функция при изменении сигнала сохраняет значение 0, т.е. Тогда из выражения (2.23) следует, что

Подставим эти значения функций в выражение (2.24): т.е. в данном случае в КС вообще отсутствуют изменения каких-либо сигналов.

Рассмотрим второй случай, когда а значит, как это следует из выражения (2.23), должны выполняться следующие соотношения:

Подставим эти значения функций в выражение (2.24):

Из последних соотношений можно сделать вывод, что выходной сигнал (рис. 2.15) изменяется с 1 на 0 (с 0 на 1), как только новое значение сигнала поступит на входы статической части всех тех ЛЭ (хотя бы одного от которых зависит значение функции а значит, в данном случае состязания ЛЭ являются некритическими. Аналогично этому доказывается, что состязания ЛЭ являются некритическими и при

Пусть теперь функция при изменении сигнала сохраняет значение 1, т.е. Тогда из выражения (2.23) следует, что

Предположим, что Тогда Подставив эти значения функций в выражение (2.24), получим Если то а если то т.е. в данном случае значение функции в переходном режиме в зависимости от соотношений задержек может измениться два раза (сначала с 1 на 0, а затем с 0 на 1). Это означает, что в КС имеют место критические состязания ЛЭ. если при

Таким образом, критические состязания ЛЭ при соседних изменениях состояний входа могут возникнуть только в том случае, когда при этих состояниях входа функция сохраняет значение 1.

Из выражений (2.25) видно, что возможен также случай, когда Подставив это значение функции в выражение (2.24), получим независимо от значений Из этого следует, что независимо от соотношений задержек и способов получения сигналов критические состязания ЛЭ будут отсутствовать, если при Если это условие соблюдается для всех сигналов то КС будет свободна от состязаний.

Из доказанного условия, при выполнении которого критические состязания ЛЭ отсутствуют, легко вывести правила синтеза КС, свободных от состязаний. Рассмотрим эти правила для синтеза КС с помощью диаграмм Вейча.

Если то это означает, что в диаграмме Вейча имеются две соседние 1-клетки, для которых переменная имеет различные значения, а все остальные переменные не изменяются. Если покрыть эти 1-клетки 1-кубом, то получим контерм такой, что а это и означает, что получена функция Очевидно, что для покрытия 1-клеток можно использовать m-кубы и большего размера. Если покрыть все соседние 1-клетки m-кубами и взять дизъюнкцию соответствующих им контермов, то функция будет представлена в форме (2.23), причем такой, что если то для любых и

Таким образом, одной из основных задач синтеза КС, свободных от состязаний, является отыскание таких минимальных покрытий 1-клеток функции -кубами, в которых любые соседние 1-клетки покрыты по меньшей мере одним m-кубом. Соответствующая этим покрытиям форма представления функции называется минимальной дизъюнктивной нормальной формой, свободной от состязаний (МДНФС). Используя закон двойного отрицания (1.14) и закон двойственности (1.25), из МДНФС можно получить минимальную нормальную форму в базисе И-НЕ, свободную от состязаний (МНФС в базисе И-НЕ).

Рис. 2.16

Рассмотрим несколько примеров. На рис. 2.16 приведены диаграммы Вейча, в которых m-кубы, необходимые для получения МДНФ, отмечены сплошными контурами. Для получения МДНФС функции, представленной на рис. 2.16,а, необходимо добавить два 1-куба и один -куб (штриховые контуры), чтобы покрыть m-кубами соседние 1-клетки с номерами 1 и 9, 3 и 7, 13 и 15. Для функции, представленной на рис. число 1-кубов для получения МДНФС удваивается по сравнению с МДНФ. Рис. 2.16,в поясняет отыскание МДНФС функции пяти переменных. В качестве примера запишем МДНФ и МДНФС

этой функции:

Аналогичным образом можно показать, что в КС, построенных в соответствии с КНФ или нормальными формами в базисе ИЛИ-НЕ, критические состязания ЛЭ могут возникнуть только в тех случах, когда функция выхода при двух соседних состояниях входа сохраняет значение 0, т.е., если Из вывода выражения (1.74) следует, что минимальная конъюнктивная нормальная форма, свободная от состязаний (МКНФС), функции может быть получена из МДНФС инверсной функции т.е. для получения МКНФС необходимо найти такое минимальное покрытие 0-клеток диаграммы Вейча для функции в котором любые две соседние 0-клетки покрыты по крайней мере хотя бы одним m-кубом. С помощью закона двойного отрицания (1.14) и закона двойственности (1.25), из МКНФС можно получить минимальную нормальную форму в базисе ИЛИ-НЕ, свободную от состязаний (МНФС в базисе ИЛИ-НЕ).

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

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