Проект "Twcad"

В. Ф. Звягин, В. Н. Голыничев, О, Ф. Немолочнов

МЕТОД СИНТЕЗА КОРРЕКТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ ЛОГИЧЕСКИХ СХЕМ

Будем рассматривать комбинационные и последовательностные асинхронные схемы, построенные из логических элементов И, ИЛИ, И—НЕ, ИЛИ—НЕ. Описанием схемы служит схемный список, в котором заданы типы элементов и структура связей между ними. Корректными последовательностями для асинхронных логических схем считаются последовательности, свободные от критических состязаний сигналов и генерации. В работе рассматриваются логические схемы, корректное функционирование которых не основывается на соотношении задержек в схеме. Основное внимание уделено вопросу синтеза корректных последовательностей для асинхронных схем с памятью. Особенностью предлагаемого метода является то, что синтезированные последовательности корректны по построению и не требуют последующего анализа по методике троичного моделирования. В работе описывается принятая модель логической схемы, вводятся в рассмотрение обобщенные кубические покрытия, предлагается модель переключения схемы, формулируется и доказывается критерий корректности перехода.

1.Модель схемы. Принята модель основывается на применении аппарата исчисления кубических комплексов [1]. Переключательная функция, реализуемая схемой, отображается кубическими покрытиями С(z₀=0) и С(z₀=1), позволяющими в компактной векторной форме задать все множество входных воздействий, требующихся для получения искомого логического значения z₀ на выходе схемы. Каждой координате куба покрытия поставлен в соответствие вход схемы. Формат покрытия С(z₀) есть упорядоченный список входов, сопоставленный координатам покрытия С(z₀). Каждая координата куба c из С(z₀) может принимать логическое значение из множества {0, 1, x}, где под x понимается значение, не используемое в данном кубе для получения z₀ . Понятие кубического покрытия С(z₀) можно распространить на последовательностные и многовыходные схемы.

Покрытие С(z₀) дл одновыходной схемы может быть построено по

* -алгоритму [1, 2]. В случае многовыходной схемы состояние выходов будем описывать вектором логических значений Z₀=(z₀₁,z₀₂,…,z_0n), где п -- число выходов. Всего возможно 3ⁿ -1 комбинаций Z₀,Z₀ (хх ... х); соответственно может быть построено 3ⁿ —1 покрытий С(Z₀). Координаты вектора Z₀ принимают значения из множества {0, 1, х}. Куб

С(Z₀) задается в виде ХZ', где X - вектор входных логических значений. Z’=Z’(X) - вектор выходных логических значений, Z’Z₀. Покрытие С(Z₀) может быть получено путем подстановки и пересечения кубов покрытий С(z_0k),, X и Z' называются в дальнейшем подкубами куба ХZ'.

Простейшая последовательностна схема соответствует элементу памяти. Текущее состояние у' элемента памяти определяется значением входов X и y - состоянием элемента памяти в предыдущий момент времени, у' = у'(Х, у). Покрытие С (y₀) можно построить по

*-алгоритму, добавив псевдовход у в формат покрытия. Кубы покрыти С (у_а) записываются в формате Хуу'. Покрытие С (y₀) подразделяется на две области: C(y₀) = C_x(y₀)

C_p(y₀), y₀=p, p{0, 1}.

Кубы из области С_х соответствуют установке схемы в текущее состояние у' = р независимо от предыдущего состояния y. В наборе, соответствующем cC_x(y₀), все петли обратной связи элемента памяти разомкнуты. Набором считается любое двоичное доопределение куба с.

Кубы из области С_р соответствуют хранению значения у' = у = р. В наборе, соответствующем сС_p(y₀), замкнута петля обратной связи элемента памяти. В работе [3] исследовались свойства покрытия С(у₀), там же было показано, что

*-алгоритм сохраняет информацию о состзательных свойствах схемы. Куб c

C(Y₀) для многовыходной последовательностной схемы имеет вид с=ХУУ'. В данном случае X - вектор логических значений на входах схемы, У- вектор логических значений на выходах элементов памяти в предыдущий момент времени, У'=- У' (Х, У) - вектор логических значений на выходах элементов памяти в текущий момент времени, X, У, У' - подкубы куба с

С(Y₀). Покрытие С (Y₀) можно подразделить на две области:

Области С_p соответствует У'=У. Кубы из С_р обеспечивают хранение состояния У', на графе переходов [4] такие кубы сопоставляются петлям при вершине У'. При подаче на схему набора, соответствующего кубу c

C_p(Y₀), c = ХУ'У', замкнуты петли обратной связи элементов памяти у'_0kx . Области С_х соответствует У'У. Это означает, что кубы из С_х обеспечивают выработку состояния У' при условии хранени состояния У; на графе переходов такие кубы сопоставляются дугам, направленным из У в У' . При У=(хх...х) куб c

C_x(Y₀) обеспечивает начальную установку схемы. Дл корректного переключения, соответствующего кубу c

C_x(Y₀), на схему действуют одновременно две составляющие X* и X:

Таким образом, У'=УУ*, где У*— вектор значений элементов памяти, устанавливающихся под воздействием входов X* при условии хранения значений элементов памяти из Y. Элементы памяти из У' разбиваются на две области:

В эвристическом алгоритме синтеза, предложенном в [5], не накладывается ограничений на взаимосвязь элементов памяти, и это приводит к получению некорректных наборов и переходов. В предлагаемом методе синтеза производится динамический выбор ациклической области У* и замкнутой области Y отдельно для каждого набора. Теоремы, приведенные ниже, обосновывают этот выбор и позволяют избавиться от некорректных последовательностей, характерных дл итеративных комбинационных схем [5].

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

С(Y₀) может быть получен из покрытий С (z₀), С (y₀) по методу простых кубов, предложенному в работе [6].

Рис. 1. Логическая схема. Выходы элементов памяти y₁,y₂,y₃.

Пример представлени последовательностной схемы (рис. 1) приведен в таблице. Схема содержит 3 элемента памяти и поэтому состоит из трех подсхем. Области С_х(у₀) и С_p(у₀) в таблице разделены горизонтальной чертой.

Подсхемы	Кубические покрытия
Подсхемы	единичное	нулевое

2. Свойства кубических покрытий. В данном разделе рассматриваются свойства кубических покрытий и условия корректности переходов по покрытиям С(z₀), С(Z₀),

С(y₀) и С(У₀). Входной вектор X может принимать 3^m-1 значений, где m- число входов схемы. В реальном эксперименте на схему может подаваться произвольное двоичное доопределение вектора X. Координаты у'_k=p в кубе с = ХУУ' при любом двоичном доопределении X вырабатываются корректно. Это будет показано в дальнейшем.

Переход от набора А к набору В будет корректным для комбинационной схемы, если логическое значение z(В)=p выработано без риска сбоя. Определим условия корректности через троичную функцию. В терминах троичного пространства (0,1,x) удается сформулировать условия корректности поведения схемы в пространстве (0,1). Введем в рассмотрение три кубических комплекса:

Определим троичную функцию g(A)=^.z*(A) троичного аргумента A следующим образом

Основным свойством троичной функции явлется монотонность, из АВ следует, что g(А)g(В). Доказательство монотонности, как и доказательство всех последующих утверждений, вынесено в приложение. Определим векторную покоординатную операцию D = А/В следующим образом:

Операция А/В в геометрической интерпретации соответствует поиску куба D наименьшей размерности, содержащего кубы А и В. Операцию D = А/В назовем операцией вычислени переходного вектора D. В результате выполнения этой операции будут найдены координаты, постоянные на переходе от набора А к набору В. Взаимосвязь троичной функции g(A) и двоичной функции, реализуемой схемой и заданной в виде покрытий С(z₀ = 0) и С(z₀=1), описывается следующей теоремой.

Теорема 1. Выход схемы, заданной покрытиями С(z₀ = 0) и С(z₀=1), может измениться при переходе от набора А к набору В тогда и только тогда, когда g(A/В)=х.

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

Теорема 2. Статический риск сбоя на выходе схемы может появиться на переходе от набора А к набору В тогда и только тогда, когда g(A/В)=x.

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

Если A

B, то говорят, что A является гранью В, а В когранью A. Переход с грани A на ее когрань В и наоборот происходит без статического риска сбоя.

Нетрудно убедиться в том, что критерий отсутствия статического риска сбоя остается справедливым и для многовыходных схем Z*(А/В) =Z*(А)/Z*(В).

Для простейшей последовательностной схемы переходы с постоянным значением p задаются кубами из области С_Р(y₀ = р). Критерий отсутствия статического риска сбоя записывается как A/B

c,c

C_p(y₀=p). В работе [3] показано, что критерий отсутствия критических состязаний сигналов имеет следующий вид: z(А)=p, z(В)=р, Вd,dC_x(у₀ = р). В том случае, когда Вd,dС_х(у₀ = р), элемент памяти работает в режиме установки, а это означает, что петли обратной связи разомкнуты.

Переключением схемы с несколькими элементами памяти назовем переход из состояния У'_i-1 в состояние У'_i такой, что У'_i-1 У'_i. Будем считать переход корректным, если он свободен от генерации, критических состязаний сигналов и риска сбоя. Обычно граф корректного перехода описывается следующим образом: У'_i-1 и У'_i -устойчивые состояния, исходное и после окончания переходного процесса. Переход из состояния У'_i-1 под воздействием X_i в У'_i происходит однозначно и не зависит от порядка переключения сигналов.

Граф корректного перехода. У — состояние схемы, X— входное воздействие.

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

Вектор входных переменных имеет следующие составляющие:

В пределах переключающего набора должны быть обеспечены хранение У_i, установка У*_iи хранение У'_i, что может быть выполнено, только если справедливо соотношение X_iX*_i Х'_i. Здесь не исключается, что один и тот же вход схемы может участвовать как в установке У*_i, так и в любом из хранений У_i или У'_i. Предлагаемая модель переключения с учетом введенных обозначений представлена на рис.3; переключение в общем случае происходит в два набора.

Нейтральный набор. Входное воздействие Х'_i-1 на протяжении переходного процесса устойчиво хранит состояние У'_i-1. Входное воздействие Х_i хранит состоние У_i, причем У'_i-1

У_i. Набор назван нейтральным, так как в нем действуют два момента хранения, а состояние схемы физически не изменяется и остается равным У'_i-1, достигнутому в предыдущем наборе. Нейтральный набор осуществляет подготовку к последующему переключению за счет формального перехода к более свободному состоянию У_i.

Переключающий набор. Входное воздействие Х_i на протяжении переходного процесса устойчиво хранит состояние У_i. Входное воздействие Х*_i при участии хранящихся сигналов У_i устанавливает элементы памяти у*_ik = р. Схема оказывается в состонии У_i У*_i, а затем переходит в окончательное устойчивое состояние У'_i, У_i У*_i

У'_i , устойчивость У'_i обеспечивается входным воздействием Х'_i. Набор назван переключающим, поскольку в нем вырабатываются элемент памяти из У*_i.

Рис.3. Модель корректного перехода - пояснение см. в тексте

Диаграмма переходов по состоянию в принятой модели переключения представлена на рис.4.

Переключения входов и соответствующие им изменения состояния схемы можно сопоставить с помощью следующей схемы:

Сформулируем правила формировани переключающего и нейтрального наборов.

Правило 1. Нейтральный набор образуется следующим образом:

Правило 2. Переключающий набор образуется следующим образом:

Чтобы можно, было получить наборы в соответствии со сформулированными правилами, необходимо выполнение следующих условий:

Отметим, что если выполнено условие Х'_i-1Х_i, то нейтральный набор не нужен.

В случае У_i У*_i = У'_i условия корректного переключения имеют следующий вид:

Сформулируем критерий корректности переключения состояния, когда последовательность состоит из наборов, построенных по правилам 1 и 2.

Теорема 3. Переход от состояния У'_i-1 к состоянию У'_i корректен тогда и только тогда, когда выполнены условия 1)—4).

При У_i У*_i У'_i дл у*_ik = р достаточно переписать условие 4) в виде X_iУ_i(У_iУ*_i)e,eC_x(У_iУ*_i). Все рассуждения остаются справедливыми. Для y_ik=p в соответствии с условием 2) обеспечена устойчивость на переходе, а по правилу 2 входное воздействие содержит составляющую Х_i, что обеспечивает устойчивость y_ik =p в наборе.

Пример. Рассмотрим схему, представленную на рис. 1. Запишем два переключающих набора в формате

тогда составляющие набора 1 имеют следующий вид:

Из того, что У'₂/У'₁ = У₂, Х'₁

Х₂, Х'₁ Х₂, следует, что переход от набора 1 к набору 2 через нейтральный набор, сформированный по правилу 1, корректен. Окончательно корректна последовательность, записанная в формате F, имеет следующий вид:

Использование доказанной в работе теоремы 3 при синтезе наборов теста гарантирует отсутствие риска сбоя, гонок и критических состязаний в последовательностях. Услови теоремы легли в основу машинноориентированного регулярного метода синтеза теста. Синтезированные последовательности не требуют последующего анализа на корректность, как это делается в случайных и эвристических методах синтеза.

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

Процедура синтеза корректных последовательностей реализована в системе проектирования тестов на ЕС ЭВМ.

Доказательство монотонности функции g. ЕслиB

N^p, p

{0,1}, то из определени комплексов N⁰,N¹ можно заключить, что A

N^p и, следовательно, g(В)=g(A)=p. Если B

N^x, то либо A

N^x и тогда g(В)=g(A)=x, либо A

N^pи тогда g(В) =х, g(А)=р и, следовательно, g(А)g(В). Таким образом, если A

B, то и g(А)

g(В), что и требовалось доказать.

Доказательство необходимости теоремы 1. Предположим, что выход схемы изменяется, но g(A/В) =р и функция g монотонна. Вследствие этого если g(А/В)=р, то g(А)=р, g(В)=p, что противоречит сделанному предположению.

Доказательство достаточности теоремы 1. Изменение выхода схемы означает, что g(А)=р, g(В)=р. Из монотонности g и определения покоординатной операции вычислени переходного вектора следует, что g(А/В)=х.

Доказательство теоремы 2. По условиям теоремы g(А)=р и g(В)=р. Статический риск сбоя означает, что выход схемы изменяется на переходе от набора А к набору В. По теореме 1 изменение выхода имеет место тогда и только тогда, когда g(А/В) =х, а по определению функции g это означает, что А/В

N^x , что и требовалось доказать.

Для доказательства теоремы 3 понадобится следующая лемма.

Доказательство: АВ

A, НL

H, откуда следует, что НL

А. По определению покоординатной операции вычислени переходного вектора (АВ)/(НL)

A, что и требовалось доказать.

Доказательство достаточности теоремы 3. Рассмотрим переход из состояния У'_i-1 в состояние У'_i. Пусть для Х'_i-1 и Х_i справедливо соотношение Х'_i-1

Х_i. Формируем последовательность, состоящую из двух переключающих наборов:

Вычислим переходный вектор. Так как Х'_i-1

Х_i, то в соответствии с леммой (Х_i-1 Х*_i-1 Х'_i-1)/( Х_iХ*_iХ'_i)

Х_i, а в соответствии с условием 1) У'_i-1/У'_i = У_i. Так как условие 2) выполнено, то согласно следствию 2 из теоремы 2 сигналы обратной связи хранятся на переходе без статического риска сбоя. Согласно условию 4) и теореме 5 работы [3] любой y*_ik =p вырабатывается без критических состязаний. Устойчивость конечного состояния У'_i следует из выполнения условия 3). Пусть для Х'_i-1 и Х_i справедливо соотношение Х'_i-1X_i , тогда формируем последовательность, состоящую из трех наборов:

Вычислим переходный вектор дл первого перехода. В соответствии с леммой (Х'_i-1Х_i)/(Х_i-1Х*_i-1Х'_i-1)

Х'_i-1, а У'_i-1/ У'_i-1 = У'_i-1 . По условию 3) и согласно следствию 2 из теоремы 2 У'_i-1 хранится на переходе без статического риска сбоя. Для второго перехода по лемме и условию 1) переходный вектор включен в Х_i У_i и, следовательно, доказательство сводится к уже рассмотренному случаю. Таким образом, доказана достаточность условий 1)—4).

Доказательство необходимости теоремы 3. Рассмотрим переключающий набор. Из того, что сигналы обратной связи должны храниться на переходе без статического риска сбоя, следует необходимость условий (1) и (2). Выработанное состояние должно устойчиво храниться, что обусловливает необходимость условия (3). Наконец, при выработке значений сигналов обратной связи должны отсутствовать критические состязания; из этого положени следует необходимость условия (4). Для случая с нейтральным набором нетрудно провести аналогичные рассуждения.