Идея теоремы состоит в том, что одни и те же схемы можно организовать по-разному:
Очевидно, если изменить одновременно x1 и x3, то критических состязаний не возникнет, а если x3 и x2, то могут возникнуть.
Утверждение. Для того, чтобы комбинационная схема была свободна от критических состязаний необходимо чтобы для соседних изменений входных сигналов только один входной сигнал xt изменялся, а сама дискретная функция была представлена в виде выражения, свободного от критических состязаний, и такое выражение существует.
Доказательство.
A. Пусть задана дискретная функция f(xn-1,xn-2,…xt+1,xt,xt-1,…,x1,x0), xj?B, которая должна быть реализована в виде комбинационной схемы, свободной от критических состязаний. Предположим, что это булева функция B={0,1}
В соответствии с теоремой Шеннона о разложении булевых функций запишем:
Пусть
Тогда
(1)
B. Представим произвольную комбинационную схему, сгруппируем ЛЭ которой в соответствии с выражением (4).
Так как по условию теоремы изменяется какой-то сигнал xt, а величины задержек tзд2 и tзд3 не равны, то можно рассматривать комбинационную схему, зависящей от изменения двух сигналов: и , которые могут изменяться не одновременно, т.е. может существовать период времени, когда они оба равны 0 или 1.
Очевидно, можно подобрать такую форму функции f* чтобы неодновременные изменения и не внесли критических состязаний.
Т.о. выражение (4) следует рассматривать как:
(2)
Представим функцию f(x) зависящей от (n+1) переменной: и переменную не будем однозначно связывать с . Это позволит смоделировать ситуацию, когда возникают состязания элементов, только введя опережение или запаздывание сигнала относительно . Тогда функции f1, f2, f3. можно рассматривать как не вносящие задержку в распространение сигнала.
C. Возможны четыре случая, когда изменяется только один входной сигнал xt:
a) , — функция сохраняющая 0;
b) , — функция не сохраняющая ни 0, ни 1;
c) , — функция не сохраняющая ни 0, ни 1;
d) , — функция сохраняющая 1;
Рассмотрим случай a)
,
Из формулы (4) получаем:
Тогда формула (5) 0принимает вид:
Вывод: В случае a), при изменении сигнала , состязания ЛЭ в комбинационной схеме не возникает, т.к. значение функции не зависит от этого сигнала.
Рассмотрим случай b)
,
Из формулы (4) получаем:
Тогда формула (5) принимает вид:
В соответствии с этим выражением, при изменении переменной с 1 на 0 или с 0 на 1, значение функции зависит только от переменной и не зависит от .
Вывод: Т.к. в случае b) выходное значение комбинационной системы зависит только от сигнала , то возникают состязания ЛЭ, но они не критические.
Рассмотрим случай c)
,
Из формулы (4) получаем:
Тогда формула (5) принимает вид:
Вывод: Т.к. в случае c) выходное значение комбинационной системы зависит только от сигнала , то возникают состязания ЛЭ, но они не критические.
Рассмотрим случай d)
,
Из формулы (4) получаем:
(3)
Система (6) имеет несколько решений:
• Если , то значение функции не зависит от переменной и результат её вычисления схемой не зависит от переменных и , т.е. состязания ЛЭ не возникает.
• Очевидно, состязания могут возникнуть при , тогда решение системы (6):
Тогда формула (5) принимает вид:
Если и некоторое время одновременно равны 1, то , т.е. критические состязания не наступают. А если и некоторое время одновременно равны 0, то , т.е. на выходе появляется ложное значение.
Вывод: Т.о. критические состязания возникают только при условии:
(4)
Кроме того, эти условия должны выполняться одновременно.
D. Синтез формального представления булевой функции свободной от критических состязаний.
Условия (7) определяют, когда возможны критические состязания, приводящие к кратковременному появлению 0 на выходе комбинационной схемы.
Найдем все значения переменных из множества , которые обращают уравнение системы (7) в тождества. Очевидно, если система (7) имеет решение, то могут возникнуть критические состязания. А если система (7) не имеет решения, то критические состязания не возникают.
Представим решения системы (7) в виде:
Решения
0 … S-1
Где — значение переменной xj из при котором уравнение системы (7) обращается в тождество, а i номер решения, т.к. их может быть несколько.
Другими словами перед нами стоит задача вычислить, на каких наборах переменных возникают критические состязания.
Определим корректирующую функцию следующим образом:
(5)
где
(6)
Свойства функции :
• , если возникают критические состязания.
• , если критические состязания не возникают.
Корректирующая функция используется для реализации комбинационной схемы, свободной от критических состязаний.
С учетом функции выражение (5) принимает вид:
(7)
Тогда схема, реализующая эту функцию, принимает вид:
Критические состязания наступают только при значении функции равном 1, т. е. возможно кратковременное появление 0 на выходе, но в этот момент функция принимает значение =1, поэтому f(x)=1.
Очевидно, что функция тождественно равна исходной функции
E. Если допускается изменение более одного входного сигнала, то в общем случае невозможно синтезировать комбинационную схему, свободную от критических состязаний.
ч.т.д.
Пример 1. Реальная схема DL триггера.
Как видно, функция DL триггера зависит от L,Q,D, т.е. f(L,Q,D)
(8)
Рассмотрим случай, когда изменяется переменная Q, по формуле (11) и (5) имеем:
, т.к. именно LD независимо от переменной Q.
, т.к. нет такой части формулы (11), которая зависит от переменной .
, т.к. именно зависит от переменной Q.
Q:
Очевидно, при изменении переменной Q критические состязания не возникают, т.к. f2=0
Рассмотрим случай, когда изменяется переменная D, по формуле (5) имеем:
D:
Очевидно, при изменении переменной D критические состязания не возникают, т.к. f2=0
Рассмотрим случай, когда изменяется переменная L, по формуле (5) имеем:
L:
Очевидно, при изменении переменной L возникают критические состязания, т.к. f1=0 , f2?0 и f3?0.
Тогда по выражениям (9) и (8) имеем:
Схема DL триггера с учетом выражения (10) принимает вид:
Этот триггер работает без критических состязаний даже при различных временах задержки ЛЭ.
Синтез комбинационных схем, свободных от состязаний, с несколькими выходами
Рассмотрим комбинационную схему, повторяющую входные сигналы. Очевидно, если времена смены выходного сигнала tВН ? tНВ, то могут возникнуть критические состязания.
Основной метод синтеза таких комбинационных схем заключается в использовании кода Грея при кодировании выходных алфавитов, когда только один выходной сигнал меняется для каждой смены входных сигналов.
Вторым методом синтеза является синтез комбинационных схем апериодическим методом, когда задержки, вносимые ЛЭ, подбираются. Причем точность подбора задержек должна соответствовать времени реакции схемы, на которую эти сигналы воздействуют.
