гает вентиля ИЛИ после того, как изменение 1->-0 сигнала а достигло его (что обусловлено большей паразитной задержкой в траектории Ь, чем в траектории а), то оба входа на логическом элементе ИЛИ могут быть в состоянии О в течение достаточно долгого времени, чтобы получить О на выходе. Этот риск сбоя может быть устранен введением в реализацию дополнительного логического элемента И, обеспечивающего выполнение XzXs- Терм л;2л:з-должен иметь значение I для обоих входных состояний 111 и 011 (рис. 4.32,6).

а б

Рис. 4.32. Комбинационная цепь со статическим риском сбоя (пример 4.16)

Другой метод устранения переходного процесса во время перехода 111->-011 заключается в том, чтобы задержать изменение 1-0 сигнала а (возможно, путем установки элемента задержки) так, чтобы изменение О->-1 сигнала b первым достигло логического элемента ИЛИ. Однако это приведет к переходному процессу в течение перехода от 011 к 111.

Лемма 4.4. Для комбинационной функции f положим, что h и /г являются входными состояниями, которые отличаются только в одной переменной Хи, и положим, что /(Л) =jf{h). Реализация двухуровневой функции / суммы произведений имеет динамический риск сбоя при переходе между 1\ и /г тогда и только тогда, когда схема имеет логический элемент И с обоими входами X я Хи, а остальные входы этого элемента имеют значение 1 для обоих h и h.

Доказательство. Достаточность. Из доказательства леммы 4.2 следует, что логический элемент И, удовлетворяющий условиям леммы, может привести к переходному процессу О->-1->-0 в течение перехода между /i и /g- Если /(/i) = 0 и /(/г) = 1, то выход некоторого другого логического элемента И должен подвергнуться изменению О-v 1 в течение перехода h-/г. Если это изменение задерживается по отношению к переходному процессу О->-1->-0, то на выходе цепи будет происходить переход О-1->-0->-1. Аналогичным образом, при переходе h-если все изменения 1->-0 на выходах логического

1--0.

элемента И происходят до переходного процесса 0-то на выходе будет происходить переход 1->0-I

Необходимость. Так как логический элемент ИЛИ сам по себе не может привести к переходному процессу, то этот процесс произойдет только в том случае, если логический элемент И создаст переходные процессы О->-1->0 или I->-0->1. Последнего нельзя достигнуть с помощью элемента И, и прежнее состояние может быть получено только в том случае, если условия леммы удовлетворяются (см. доказательство леммы 4.2).

Из леммы 4.4 следует, что устранение статического риска сбоя является также достаточным для устранения динамических рисков сбоя при однократных

Рис. 4.33. Комбинационная функция с функциональным риском сбоя.

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

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

Если вход в цепь, реализующую эту функцию, изменяется от а = 0101 до b = 1111, то вследствие паразитных задержек цепь может проходить через 0111 или 1101. Для получения О на выходе требуется входное состояние 0111, и, следовательно, эта функция не может быть реализована без некоторого риска сбоя при переходе от а к Ь. С другой стороны, переход от а к с может проходить через 0001 или 1I0I, каждая из которых является единичной точкой функции. Риск сбоя в течение этого перехода может быть устранен при включении в эту реализацию импликанты покрывающей как а, так и с.

Теперь рассмотрим переход от d = 0000 к е = 1101, требующий изменения на выходе О->-1. В зависимости от относительных значений паразитных задержек цепь может реагировать на следующую последовательность входных состояний: 0000->-

->-0100->-1100->-1101. Так как при входном состоянии 0100 на выходе цепи требуется получить состояния 1, а при входном состоянии 1100 получить на выходе О, любая цепь, реализующая эту функцию, может привести к выходной последовательности О-)-1-0-> 1 вместо О->-1. Такой риск сбоя является внутренне присущим функции и не может быть устранен, если допускается изменение входных переменных в любом произвольном порядке при допущении, которое делалось о задержках.

Риски сбоя, которые являются внутренне присущими функции, называются функциональными рисками сбоя в противоположность логическим рискам сбоя, которые могут быть устранены надлежащей структурой [4]. Такие риски сбоя могут рассматриваться как статические и динамические риски сбоя аналогично случаю однократного изменения входных сигналов.

Говорят, что функция / имеет статический функциональный риск сбоя при изменении на входе /i-h, если f(Ii) -f{h) и существует некоторый вход h, содержащийся в подкубе перехода T{Iuh), такой, что f{Is) = f{h). Если такого входа /з не существует, но конкретная реализация может привести в течение изменения на входе к ложному импульсу при некотором распределении паразитных задержек, то говорят, что реализация содержит статический логический риск сбоя. Если f{Ii) ф ¥=/(/2), существуют входы hT(lx, /2) и UT{h, /2), а ){1гФ ф]{1 =/(/,), то функция имеет динамический функциональный риск сбоя для перехода между 1\ и 1% Цепь может проходить через /3 и /4 в течение перехода /1->-/2. Если f{fi)=fih) и f(h)=f{h), то выход будет изменяться три раза вместо однократного изменения. Риск сбоя не может быть устранен самой структурой. Если функция не имеет динамических функциональных рисков сбоя, но при некотором распределении паразитных задержек выход реализуемой функции может изменяться более чем один раз, то реализация содержит динамический логический риск сбоя. Таким образом, функциональные риски сбоя являются свойствами реализуемой функции, а логические риски сбоя зависят от реализации функции.

Из лемм 4.2 и 4.3 следует, что двухуровневая реализация функции / в виде суммы произведений будет иметь только статические риски сбоя в единице при однократных изменениях входных переменных, если существуют две смежные единичные точки функции, которые не покрываются общим термом произведения. Такой риск сбоя может быть предотвращен путем добавления терма произведения, который покрывает при реализации обе эти единичные точки. Можно показать, что при реализации функции / в виде суммы произведений все статические логические риски сбоя могут быть предотвращены за счет включения в реализацию каждой простой импликанты функции и

исключения из нее термов, содержащих переменную и ее инверсию [4]. При однократных изменениях входных переменных включение всех простых импликант является достаточным, но не необходимым условием того, что каждая пара смежных единичных точек, покрывается общим терм-произведением, и, следовательно, предотвращаются все статические риски сбоя (см. задачу 4.9).

Статические функциональные риски сбоя не могут быть устранены путем введения дополнительных терм-произведений. Некоторые из этих рисков сбоя могут быть предотвращены за счет введения задержек таким образом, чтобы цепь не проходила через какое-либо входное состояние, требующее изменения значения функции. Например, если гарантируется переход из а в b (рис. 4.33) через е, который требует задержки изменения Хз, то цепь не будет проходить через входное состояние f, требующее 0-точку на выходе. Однако в течение перехода Ь- -а будет происходить переходный процесс на выходе, так как теперь будет осуществляться переход через нулевую точку функции f. Если й асинхронной цепи переход инициируется при однократном изменении входной переменной, то можно использовать должным образом спроектированную комбинационную схему, реализующую функцию возбуждения, свободную от риска сбоя, но это может привести к изменению значения одной или более переменных состояния. Задержки обычно вставляются в контуры обратных связей для того, чтобы обеспечивать заверщение реакции комбинационных цепей возбуждения на изменение входного воздействия прежде, чем произойдет изменение у. (В следующем разделе будет показано, что иногда задержки могут вообще не потребоваться.) Переменные состояния либо изменяются один раз за время, в течение которого обеспечивается функционирование цепи, свободной от риска сбоя, либо не происходит критических состязаний. В этом случае весь подкуб перехода, определяемый изменением переменных состояния, генерирует те же самые комбинационные схемы возбуждения и может и должен быть покрыт одним терм-произведением (при этом допускается, что возбуждение определяется состоянием 1) для того, чтобы гарантировать работу цепи без риска сбоя.

Предотвращение динамических логических рисков сбоя представляет более затруднительную задачу, но пока какого-либо систематического метода ее рещения не существует. Хотя динамические риски сбоя могут быть неизбежными, представляется возможным спроектировать последовательностные цепи, состояния переходов которых не подвержены их влиянию за счет использования инерционных задержек или определенных типов триггеров, которые нечувствительны к таким переходным процессам. Использование таких элементов устраняет необходи-

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

До сих пор мы ограничивались обсуждением рисков сбоя в комбинационных цепях при двухуровневых реализациях сумм произведений. Следующая теорема обеспечивает метод определения любой комбинационной цепи, содержащей статические риски сбоя, посредством преобразования ее в двухуровневую форму цепи, реализующую сумму произведений. Можно показать, что каждый тип используемого преобразования не привносит или не устраняет статические риски сбоя [23].

Теорема 4,6. Если булево выражение, представляющее комбинационную цепь, преобразуется в выражение суммы произведений, полученное при использовании только ассоциативных или дистрибутивных законов или закона Де Моргана (который всегда можно выполнить), то результирующее выражение будет иметь те же самые статические риски сбоя, что и исходная цепь.

Из теоремы 4.6 и лемм 4.2 и 4.3 следует, что комбинационная цепь имеет статические риски сбоя тогда и только тогда, когда соответствующее выражение суммы произведений Е, полученное при использовании ассоциативных или дистрибутивных законов или закона Де Моргана, имеет терм-произведение Р, содержащее как X, так и х только для одной переменной, и если все другие литералы в Р являются множеством из 1, £ = хх или если для некоторого возможного перехода между единичными точками функции h и h терм-произведение Е пе покрывает ни /ь ни /g. Однако теорема 4.6 не справедлива для динамических рисков сбоя (см. упражнение 4.15). Допустим, Е является булевым выражением, соответствующим многоуровневой комбинационной цепи. Из леммы 4.4 следует, что если некоторому множеству переменных присвоить постоянные значения, то резуль-тирующее выражение принимает вид х + хх или х{х-{-х); тогда исходная цепь имеет при переходе динамический риск сбоя, вызванный изменением х, в то время как другие переменные остаются постоянными, что позволяет принять Е удобную форму. Таким образом, если

Е (xi, Хо, Хз, Х4,) = Xl (Х2 -f Хз) -f (xi + Хг) (хг + Х3Х4),

Е(0, Хо, 1, 0)=Х2 + Х2Х2

и, следовательно, имеется динамический риск сбоя при переходе, вызванный изменением Хг, если Xi = О, Хз =. 1 и Х4 = 0. Если при кодировании каждая переменная остается постоянной или идентифицируется с х или х, то результирующее выражение принимает вид х--хх или х(х--х), а цепь имеет динамическую

4.6.2. ПОСЛЕДОВАТЕЛЬНЫЙ РИСК СБОЯ

В модели асинхронных последовательностных цепей, которая рассматривалась нами ранее, в каждом контуре обратной связи введен элемент задержки. Наличие введенных задержек гарантирует, что комбинационная цепь, реализующая функцию возбуждения, откликнется на изменение входной переменной прежде, чем произойдет какое-либо изменение переменных состояния, которое связано с указанным изменением на входе цепи. Наряду с другими мерами предосторожности, которые учитываются при кодировании состояний в процессе проектирования комбинационных логических цепей, в которых отсутствует риск сбоя, вводится допущение, что однократное изменение входной переменной является достаточной гарантией необходимого функционирования цепи. При анализе таких цепей обычно предполагается, что на относительные величины паразитных задержек в цепи нет ограничений, что эти задержки неотрицательны и известна верхняя граница D. Нижняя граница величин введенных задержек D предполагается известной, и обычно считается, что DD. Минимальное время между последующими изменениями входных сигналов при основном режиме функционирования определяется при кодировании состояний; кроме того, определяются граничные значения величин паразитных и введенных задержек. В отдельных случаях цепь может функционировать должным образом без некоторых или всех из этих введенных элементов задержки. Однако, вообще огворя, их устранение может послужить причиной ложного срабатывания; о такой цепи говорят, что она имеет последовательный риск сбоя. Мы будем ограничиваться рассмотрением таблицы переходов нормального режима. Аналогичные методы применимы к таблицам ненормального режима.

Существуют два типа риска сбоя, которые могут присутствовать в асинхронных последовательностных цепях. Говорят, что цепь содержит установившийся риск сбоя, если существует некоторое распределение паразитных задержек, такое, что цепь может прийти в неправильное состояние при некотором переходном процессе изменения входных сигналов. Риск сбоя на выходе (иногда называемый переходным риском сбоя) присутствует в цепи, если может быть получен ложный выходной импульс в течение некоторого перехода при определенном распределении паразитных задержек.

задержку при многократном изменении переменных, причем в нее вовлекаются все переменные, идентифицированные с х или X.

O-t-l

i2 0 1 J I

О

Рис. 4.34. Таблица переходов и кодирование состояний (а); реализация таблицы переходов (б); карты Карнау для переменных г/i и г/г (е).

В результате Y\ может подвергаться переходу 1->-0-5-1.Если изменение О-у\ сигнала а достаточно задерживается по отношению к изменению 1->-0 сигнала а, то цепь может проходить через состояние 2, представленное г/i = О, y-i-l. Так как в столбце X = 1 имеется именно такое устойчивое состояние, то цепь может установиться в состояние 2 вместо достижения состояния 4, как это указано в таблице переходов. Это положение и представляет собой устойчивый риск сбоя, вызываемый

На рис. 4.34,6 показана реализация таблицы переходов, представленной на рис. 4.34, а, в которой используется показанное справа от нее кодирование состояний.

Рассмотрим переход из состояния 3 в состояние 4. Когда вход X изменяется от О к 1, выход а логического элемента И изменяется от О к 1, выход Ь этого элемента изменяется от 1 к 0.

статическим риском сбоя при реализации Уь Аналогичным образом, устойчивый риск сбоя существует в течение перехода из состояния 2 в состояние 3. Цепь может достигнуть состояния 1, а не состояния 3. Из карты Карнау, представленной на рис. 4.34, в, видно, что статический риск сбоя и, следовательно, устойчивый риск сбоя могут быть устранены введением терма У1У2 и У1У2 для реализации Yi и Уг соответственно.

В рассмотренной выше цепи имеется также риск сбоя иа выходе при переходе из состояния 3 в состояние 4. Переход 1-> ->-0->-1, происходящий в результате статического риска сбоя в Уь может привести к переходу О->-1->-0 на выходе z или неправильному изменению О-> 1 на выходе. В этой цепи устранение устойчивого риска сбоя будет также предотвращать риск сбоя на выходе.

Задержки, введенные в контуры обратной связи и/или в качестве элементов памяти, должны быть такими, чтобы влияние изменений входных сигналов достигло всех частей цепи прежде, чем произойдет какое-либо изменение, вызванное изменением переменных состояний. Если в некотором контуре обратной связи действие элемента задержки устраняется или оказывается недостаточным, то может произойти ложное срабатывание, даже если все простые импликанты функций следующего состояния используются при реализации.

Рассмотрим цепь, реализующую таблицу переходов, показанную, на рис. 4.34, й, и допустим, что цепь первоначально была устойчивой в состоянии 1 при входном сигнале л; = 0. Проанализируем теперь поведение цепи, когда входной сигнал изменился на 1, если задержка в элементах памяти не удовлетворяет вышеуказанным ограничениям. Цепь вначале перейдет в состояние 2 {у2 изменится на 1). Вследствие больших паразитных задержек цепи влияние изменения у2 может достигнуть некоторой части цепи прежде, чем произойдет изменение входа О-1. Следующим состоянием для состояния 2 при входе О является состояние 3, и, следовательно, цепь подвергается воздействию перехода состояния 2->-3 (yi изменяется на 1). Наконец, когда влияние изменения О->-1 в х достигнет всех частей схемы, цепь может оказаться в устойчивом состоянии 4 {у2 изменяется обратно на 0) вместо состояния 2.

Этот тип риска сбоя является свойством таблицы переходов. Допустим, что /1 и /2 должны быть двумя смежными состояниями входа и qi является внутре-нним состоянием таблицы переходов так, что N{qi, /1) = qt я N{qi, /г) = 9j. Таблица переходов содержит существенный риск сбоя при переходе /1-v/2 из состояния qi, если входная последовательность /2/1/2, применяемая к полному состоянию {qi, h), приводит в результате к конечному состоянию qh ф qj.

Положим, что цепь, реализующая таблицу переходов, приведенную на рис. 4.34, а, первоначально была устойчивой в состоянии 1 при входном сигнале л; = 0. Если вход изменяется на 1, то правильным следующим состоянием должно быть 2, однако состояние, достигаемое при применении входной последовательности 101, оказывается состоянием 4. Таким образом, таблица переходов имеет существенный риск сбоя. В представленной на рис. 4.34, а таблице переходов все переходы содержат существенные риски сбоя. В общем случае для произвольных таблиц это не является, вообще говоря, обязательным.

Реализация таблицы переходов, которая содержит существенный риск сбоя, может привести к ложному срабатыванию, если в некоторых переменных состояния не введены элементы задержек вследствие возможности критических состязаний между изменением входных переменных и переменной (переменных) состояния, вызываемых паразитными задержками. Эта проблема может быть разрешена путем введения элементов задержки в контуры обратных связей таким образом, чтобы гарантировать полное завершение реакции цепи на входное изменение прежде, чем могут произойти любые изменения в переменной состояния. Необходимость введения элементов задержки при реализации таблицы переходов, содержащей существенные риски сбоя, подтверждается в следующей теореме Ангера, доказанной им в [22, 23].

Теорема 4.7. Для предотвращения устойчивых рисков сбоя в последовательностной цепи введенные элементы задержки требуются тогда и только тогда, когда таблица переходов содержит по крайней мере один существенный риск сбоя.

Необходимо задерживать только те переменные, которые изменяются в течение переходов с риском сбоя. Ангером было также показано, что введение одного элемента задержки является достаточным для реализации любой нормальной таблицы переходов в предположении, что только одна входная переменная изменяется в течение любого перехода (см. упражнение 4.12). Позднее в этой главе будет приведен метод реализации, требующий только одного элемента задержки (но допускающий также многократные изменения входных переменных), а также обеспечивающий условие, что все изменения состояния входа полностью завершатся в пределах фиксированного интервала времени.

Таблицы переходов, в которых отсутствуют существенные риски сбоя, могут быть реализованы без введенных задержек, но в некоторых случаях может оказаться необходимым специальное кодирование состояний. Рассмотрим сегмент таблицы переходов, показанный на рис. 4.35.

Огг- А^е, tr а идентифицировано с кодом для состояния 2.

лгИС rt.oO. 1\ОНфИ~ д ггллт

гурация d-трио. Ангером [24] было показано, что возможно определить ОВП-кодирование, которое покрывает некоторые дополнительные дихотомии, обладающие этим свойством. Может быть также использовано кодирование состояний, при котором изменяется только одна переменная в течение перехода (такое, как присваивание кода Хэмминга). Конфигурация, показанная на рис. 4.35, называется d-трио [22].

Способ, примененный к вышеупомянутым таблицам переходов без существенных рисков сбоя, может быть реализован без введения элементов задержек. Такие реализации не будут содержать устойчивых рисков сбоя, но могут содержать риски сбоев на выходе (которые нельзя устранить).

Для таблиц переходов с существенными рисками сбоев необязательно вводить элементы задержки во все контуры обратных связей. Элементы задержки необходимы только для тех переменных состояния, которые изменяются в течение переходов, содержащих существенные риски сбоев.

Пример 4.18. Таблица переходов, представленная на рис. 4.36, а, не имеет существенных рисков сбоев и, следовательно, может быть реализована без введения элементов задержки. Используя кодирование состояний, показанное справа от таблицы, для того чтобы предотвратить ложное срабатывание при переходе (1, 11)->-(2,01), связанном только с d-тряо, мы должны идентифицировать содержимое в столбце 01 и строке 10 матрицы Y с кодом 01, связанным с состоянием 2. Это приводит

Переход из полного состояния (1, /i) к (2, /г) не содержит какого-либо существенного риска сбоя. Если используется ОВП-кодирование, то цепь может достигать любой точки в подкубе перехода Г (1, 2) в течение перехода из состояния 1 в состояние 2 прежде, чем изменение на входе достигнет некоторого логического элемента цепи. Поскольку Л/(2, /j) =3, то затем цепь может начать переход от состояния 2 к состоянию 3. Обозначим множество переменных состояния, которые изменяются при переходах от 1 к 2 и от 2 к 3, через Лий соответственно.

Если не вводятся элементы задержки, то можно допустить изменение в любом порядке множества переменных С - А [j В, и цепь может проходить через любой код, которого можно достигнуть таким способом из состояния 2. Для того чтобы обеспечить должное функционирование цепи, кодирование состояний должно быть таковым, чтобы для всех таких кодов содержимое следующего состояния в столбце /г матрицы Y могло бы быть