Анализ состязаний

Явление состязания сигналов

Состязания сигналов в реальных ДУ возникают вследствие того, что смена входных сигналов при подаче следующего набора происходит не одновременно и существует разброс задержек элементов в схеме , . Схема, реализующая булеву функцию $$f(X)$$, содержит статическое (динамическое) состязание на переходе между двумя двоичными наборами $$A=(a_1,…a_n)$$ и $$B=(b_1,…,b_n)$$, если $$f(A)=f(B),(f(A)\not =f(B))$$ и во время перехода на выходе схемы может возникнуть один или несколько кратковременных импульсов. Статистическое состязание называется $$1$$-состязанием, если $$f(A)=f(B)=1$$ и $$0$$-состязанием, если $$f(A)=f(B)=0$$. Динамическое состязание называется $$1-0$$ – состязанием, если $$f(A)=1, f(B)=0$$ и $$0-1$$ – состязанием, если $$f(A)=0, f(B)=1$$. Как статистические, так и динамические состязания могут быть двух типов: функциональные и логические.

Фукциональные состязания

Рассмотрим пример функционального состязания для булевой функции, представленной на карте Карно (таблица 6.1). Напомним, что каждая клетка карты соответствует двоичному входному набору. Рассмотрим переход между следующими двоичными наборами $$\underbrace{x_3=0,x_1=x_2=0}_{1^a}\to x_3=0,\underbrace{x_1=x_2=1}_{1^c}$$ отмеченными на карте Карно $$1^a$$ и $$1^c$$. Если значение $$x_2$$изменяется раньше чем $$x_1$$, то на данном переходе возможно кратковременное появление набора $$x_1=0,x_2=1,x_3=0$$ (попадание в клетку $$0^b$$карты Карно). Это вызывает появление на выходе cхемы, реализующей данную булеву функцию, кратковременного $$0$$-импульса, то есть происходит статическое $$0$$ состязание. Аналогично при переходе из клетки $$1^a$$ в $$1^d$$карты Карно происходит динамическое состязание $$1\to 0$$.

Определим более точно функциональное статистическое состязание. Булева функция $$f$$ на переходе $$A\to B$$ (для определенности пусть изменяются значения первых $$r$$ переменных $$A=(a_1,…,a_r,a_{r+1},…,a_n),B=(\overline{a_1},…,\overline{a_r},a_{r+1},…,a_n)$$ содержит функциональное статистическое состязание $$f(A)=f(B)$$, если среди $$2^r$$ входных наборов с зафиксированными значениями $$x_{r+1}=a{r+1},…,x_n=a_n$$ найдутся хотя бы два набора $$C$$ и $$D$$ такие, что $$f(C) \not =f(D)$$.

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

Логические состязания

Логические состязания определяются структурой логической схемы, реализующей данную булеву функцию. Рассмотрим это явление на примере функции, представленной на карте Карно рис.6.1 .

Для перехода $$x_1=0,x_2=1,x_3=1\to x_1=1,x_2=1,x_3=1$$ у логической схемы, реализующей данную булеву функцию, которая представлена на рис.6.2 , значения выхода схемы $$f=1$$ одинаковы на начальном и конечном входных наборах этого перехода. Однако, если значение выхода нижнего вентиля $$И$$ изменится раньше чем верхнего, то на выходе схемы появится кратковременный нулевой импульс. Таким образом, здесь присутствует статическое логическое состязание .

Отметим, что поскольку на этом переходе изменяется значение только одной переменной, то функциональное состязание на нем в принципе невозможно. Кроме этого, данное логическое состязание присуще именно этой схемной реализации. Так, если в схеме рис.6.2 добавить в первом уровне третий элемент конъюнкции (соответствующий третьей простой импликанте данной булевой функции), то состязание в полученной схеме рис.6.3 (реализующей ту же булеву функцию) на рассматриваемом переходе отсутствует.

Определим более строго логическое состязание . Комбинационная схема, реализующая булеву функцию $$f$$, содержит статическое логическое состязание на переходе $$A\to B$$, если на всех $$2^r$$ наборах с зафиксированными значениями $$x_{r+1},…,x_n$$ значения функции одинаковы $$f(A)=f(B)$$, но во время перехода может появиться кратковременный импульс на выходе схемы. Аналогично определяется и динамическое логическое состязание для случая $$f(A) \not =f(B)$$. Известно, что если схема свободна от статистических состязаний, то она свободна и от динамических состязаний. Состязания сигналов особенно опасны для последовательностных схем, потому что могут в них вызвать непредсказуемые переключения элементов памяти. Такая ситуация показана на рис.6.4 , где состязание на выходе вентиля $$z$$ может привести к установке триггера в неправильное (и непредсказуемое) состояние. Разработана и более тонкая классификация состязаний (особенно для последовательностных схем) [48].

Анализ состязаний по методу Эйхельбергера

На практике большое распространение получили системы логического моделирования в троичном алфавите $$E_3$$. Моделирование в троичном алфавите последовательностных схем в простейшем случае используется для проверки, является ли данная входная последовательность установочной, т. е. переводит ли она схему из неопределенного начального состояния в некоторое определенное. Поскольку перед началом моделирования схема находится в произвольном состоянии, то сигнал на каждой линии может иметь значение как $$0$$, так и $$1$$. Поэтому перед началом моделирования всем линиям схемы присваивается неопределенное значение $$u$$. Далее выполняется моделирование на последовательности входных наборов (имеющих двоичные значения $$0, 1$$) с помощью одного из рассмотренных алгоритмов. При этом используются троичные модели логических элементов. Если по окончании моделирования все линии схемы принимают определенные значения ($$0,1$$), то входная последовательность является установочной (в терминах теории экспериментов с автоматами – синхронизирующей последовательностью см. лекцию 23 ). На практике часто надо получить определенные значения не на всех линиях, а только на некоторых. Очевидно, описанный метод позволяет проверить, является ли входная последовательность установочной для некоторого подмножества линий.

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

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

Для анализа состязаний широкое распространение получил метод Эйхельбергера, который основан на предположении, что соотношение задержек в элементах и линиях связей произвольно. Символ $$u$$ при этом означает не только неизвестный сигнал, но и смену сигналов $$0\to 1$$ или $$1 \to 0$$.

В методе Эйхельбергера моделирование входного набора $$X_t$$выполняется в два этапа. Сначала формируется промежуточный набор $$\delta X_t$$, в котором всем входным переменным, изменившим значение по сравнению с набором $$X_{t-1}$$, присваивается неопределенное значение $$u$$ (остальные значения остаются неизменными и равны $$0$$ или $$1$$) так, как это показано в табл.6.1 для схемы рис. 2.5 . Затем выполняется моделирование в троичном алфавите на промежуточном наборе $$\delta X_t$$ (при этом, естественно, используются троичные модели логических элементов). На этом этапе моделируется переходный процесс, во время которого всем линиям, которые существенно зависят от изменившихся входов на данном наборе, присваиваются неопределенные значения $$u$$. При этом неопределенные значения распространяются от внешних входов к выходам и переменным состояния до тех пор, пока значения сигналов не стабилизируются. Свойства троичных функций таковы, что значение сигнала на каждом элементе либо остается неизменным ($$0,1$$), либо изменяется (с $$0$$ или $$1$$ на $$u$$). Поэтому процедура имеет линейную сложность (пропорционально числу элементов $$n$$ в ДУ).

На втором этапе ДУ моделируется на основном наборе $$X_t$$ (значения всех входов которого двоичные). При этом от входов к выходам происходит "снятие" неопределенности. Вследствие свойства троичных функций на каждом логическом элементе сигнал либо остается постоянным, либо изменяется с $$u$$ на $$0$$ или $$1$$. Поэтому на втором этапе сложность процедуры также линейна.

Если по окончании второго этапа на некоторых линиях ДУ остались неопределенные значения $$u$$, то это свидетельствует о возможности опасных состязаний на этих линиях. На линиях, получивших после второго этапа определенные значения, состязания в схеме на данном наборе невозможны. Если все линии ДУ получили определенные значения, состязания в схеме на моделируемом переходе между двумя наборами заведомо отсутствуют.

Отметим, что в данном методе анализ выполняется чисто логическими средствами без задания каких-либо значений задержек элементов. Метод основан на анализе логической зависимости элементов схемы от изменившихся входов. Простота метода и линейная сложность обусловили его широкое применение на практике. Пример моделирования в троичном алфавите методом Эйхельбергера приведен для схемы на рис.6.5 .

Результаты моделирования, представленные в табл. 6.1 , показывают, что набор $$X_1$$ является установочным, на переходах между наборами $$X_1,X_2,X_3$$ состязания отсутствуют, а при переходе с $$X_3$$ на $$X_4$$ возникают опасные состязания. Доказано, что моделирование методом Эйхельбергера на обоих этапах сходится за конечное число итераций. Поэтому при реализации единственным критерием окончания моделирования на наборе (промежуточном и основном) является совпадение результатов двух соседних итераций. При этом результаты не зависят от порядка обработки элементов. Отметим, что троичное моделирование в данном методе может выполняться с помощью простейшей (и быстродействующей) модели элементов – нулевой задержки.

Троичное моделирование по методу Эйхельбергера позволяет обнаружить любые опасные состязания, которые могут быть в ДУ на данной входной последовательности. Однако этот метод имеет существенный недостаток — он может показывать наличие состязаний в тех случаях, когда их нет в реальном устройстве. Это обусловлено принятым допущением о произвольном соотношении задержек элементов и линий связи. В действительности обычно задержки в линиях связи существенно меньше задержек логических элементов. Соотношение между задержками элементов также не всегда произвольно. Ложные состязания метод Эйхельбергера может показывать в схемах, содержащих сходящиеся разветвления, искусственные линии задержки из цепочек элементов и, особенно, в счетных структурах, где любое переключение счетного входа приводит к обнаружению состязаний.

В какой-то мере этот недостаток устранен в методе моделирования, получившем название $$\Delta$$-троичного и являющегося модификацией предыдущего. Суть метода заключается в том, что моделирование на промежуточном наборе ограничивается сверху некоторым числом итераций $$q$$. Параметр $$q$$ задается заранее и косвенно отражает степень разброса задержек элементов в схеме. При этом распространение неопределенных значений $$u$$ искусственно прекращается, не дожидаясь, пока процесс сойдется. При $$\Delta$$-троичном моделировании используется модель единичной задержки. Сходимость этого метода не гарантирована, поэтому после выполнения максимального числа итераций всем линиям, на которых сигналы не установились, присваивается неопределенное значение.

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

Ключевые термины:

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

Логическое состязание - определяется на паре двоичных наборов свойствами логической схемы и заключается в появлении на выходе схемы кратковременного импульса.

Троичное моделирование – логическое моделирование в троичном алфавите $$\{0,1,u\}$$.

Краткие итоги

Лекция посвящена вопросам анализа состязаний сигналов в логических схемах.

В разделе 6.1 описано явление состязания сигналов. В разделе 6.1.1 рассмотрен и приведен на карте Карно пример функционального состязания . и схема,. Раздел 6.1.2 посвящен логическим состязаний .

В разделе 6.2 изложен метод Эйхельбергера анализа состязаний, который основан на троичном моделировании и имеет линейную сложность.

Вопросы и упражнения