УНИВЕРСАЛЬНАЯ МОДЕЛЬ ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ В САПР

А.Г. Зыков, О.Ф. Немолочнов, В.И. Поляков

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

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

На основании проведенных исследований и практики проектирования и анализа цифровых систем в качестве модели логической схемы предлагается модель, представленная на рисунке. В отличие от классической модели Хаффмана [1, 2], предлагаемая модель учитывает современные тенденции в схемо- и системотехнике, в частности, применение двухступенчатых триггеров (M-S) [3]; синхронизацию (при этом если синхросигнал не отличать от других входов схемы, то модель будет отображать основной класс асинхронных схем); понятие сигнала системного сброса (начальной установки) и др. Это значительно уточняет модель при использовании машинно-ориентированных методов проектирования и анализа схем.

Модель схемы условно разбита на комбинационную и последовательностную (П) части. Здесь вектор Х есть независимые входы схемы, из которых особо выделены сигнал синхронизации Т и сигнал начальной установки элементов памяти R, который может быть как асинхронным сбросом, так и синхронизированным тактом Т, что в общем случае не является принципиальным. Значения Y’ определены как булевы функции Y’ = Y’(X,Y). Значение сигналов обратной связи Y разбито на два

подмножества YM и YS, соответственно Y’ = Y’M U Y’S. Значения выходных сигналов также определены как Z = Z( X,Y ) для автомата Мили и как Z = Z(Y) для автомата Мура. Для схемы также определены некоторые промежуточные сигналы Zj как выходы КС, которые являются вспомогательными и введены как следствие разбиения КС на одновыходные комбинационные подсхемы или с целью уменьшения размерности решаемых задач. Значение вектора сигналов Y определяет предыдущее значение состояния схемы, а значение вектора Y’ – последующее состояние. В общем случае векторы Y и Y’ задают некоторые классы состояний. Любой сигнал y и y’ может принимать три значения: 0, 1 и х, где х есть безразличное состояние, которое произвольным образом можно доопределить в значение 1 или 0, если это не вызывает противоречия при переходе схемы из состояния Y в состояние Y’.

Соответствие между значениями сигналов Y и Y’ определяется по интервальным кубическим покрытиям C(y’ ) = Cx(y’ ) UCp(y’ ), где Cx(y’ ) есть область установки, а Cp( y’ ) – область хранения. Если некоторое значение y’ вычислено кубом С Сх( y’ ), то y = x и y’ = p, если же значение y’ вычислено кубом C Cp( y’ ), то значение y = y’ = p.

107

В соответствии с предложенной универсальной моделью схемы введём понятие куба единого формата Ф0 = X YM YS ZК Y’ M Y’ S Z. Данный формат в векторном виде описывает все значения сигналов и их разбиение на функциональные классы. Если не делать различия между классами YM, YS, Y’ М и Y’ S, то можно ограничиться форматом Ф1 = X Y ZК Y’ Z. Далее, если ZК отсутствуют, можно ограничиться форматом Ф2 = X Y Y’ Z. Наконец, для случая, когда рассматриваются только переходы схемы, можно перейти к формату Ф3 = X Y Y’, что является вполне допустимым при теоретическом рассмотрении состояний и переходов схемы, так как значения ZК и Z являются импликациями от независимых входов Х и сигналов обратной связи Y или Y’, и их можно вычислить после построения переходов.

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

•моделирование;

•анализ состязаний;

•построение переходов схемы в прямом и в обратном направлении;

•верификации иерархических моделей;

•другие задачи анализа.

Литература

1.Huffman D. The design and use of hazard tree switching network // J. Of ACM. 1957. V. 4. №1. Р. 37–40.

2.Чжен Г., Меннинг Е., Метц Г. Диагностика отказов цифровых вычислительных систем. М.: Мир, 1972.

3.Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Л.: Энергия, 1979.

4.Немолочнов О.Ф. Щупак Ю.А. Модель функциональных неисправностей для автоматного представления первичных элементов логической схемы // Автоматика и телемеханика. 1993. №5. С. 167–-179.

108

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

А.Г. Зыков, О.Ф. Немолочнов, В.И. Поляков

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

Процесс проектирования логических схем представляет собой последовательность этапов синтеза и анализа иерархических моделей вплоть до конкретной реализации схемы в заданном элементном базисе. Важным фактором достоверной реализации проекта является соблюдение адекватности иерархических моделей на различных стадиях проектирования, что достигается решением задач анализа и верификации. Для решения задач анализа закон функционирования схемы описывается тем или иным способом. Для систем автоматизированного проектирования одним из наиболее компактных и информационных является описание схем в виде кубических покрытий [1–3]. Схема декомпозируется на одновыходные подсхемы, каждая из которых описывается вырожденными покрытиями C(fi) в локальном формате Фл = {X, Y, Y’, Z}, где Х – независимые входы, Y – сигналы обратной связи, определяющие исходное состояние схемы, Y’– сигналы обратной связи, определяющие последующее состояние схемы, Z – выходные или внутренние значения комбинационных элементов (подсхем) схемы. Так как значения Z являются импликациями от независимых входов Х и сигналов обратной связи Y и Y’, то их можно вычислить после построения переходов схемы. Поэтому можно перейти к локальному формату Фл1 = {X, Y, Y’}, что является допустимым при теоретическом рассмотрении состояний и переходов схемы.

Построение комплексного покрытия всей схемы позволяет получить полную модель исправной схемы для решения требуемых задач анализа, что выгодно отличает её от моделей, предложенных в [2]. Комплексное покрытие (КС) строится в глобальном формате Фкс = {X, Y, Y’, Z}. Любой куб комплексного покрытия кi KC трактуется как некоторое состояние логической схемы. КС строится методом пересечения множеств кубов покрытий подсхем на основе полного перебора, т.е. всех возможных сочетаний. Таким образом:

n

КС = IC( f i) −{a | a b;a,b KC},

i =1

где n – количество покрытий подсхем.

Само КС есть множество простых кубов, адекватно отображающих все состояния и переходы последовательностной схемы. Простой куб ксi есть такой куб, в котором ни одну координату со значением p = 1 или 0 нельзя заменить на х без нарушения импликации y’i=pi и zj = pj.

Сокращение перебора может быть достигнуто методами импликации значений С(y’i) и C(Z), а также методами локальной и глобальной оптимизации на основе операции поглощения кубов.

Рассмотрим на примере построение КС последовательностной схемы с глобальной обратной связью.

Пусть имеется схема пересчёта (рис. 1), состоящая из двух триггеров: DT1 – синхронный DT триггер и DT2 – синхронный DT – триггер со сбросом, после декомпозиции и являющиеся одновыходными подсхемами.

109