Четырехзначное логическое моделирование

Современные системы проектирования цифровых схем с применением программируемых логических интегральных схем (ПЛИС) контролируют их работоспособность тестированием.

Такие языки проектирования (HDL — hardware description language), как Verilog и VHDL', содержат соответствующие средства поддержки временного моделирования и опираются на четырехзначные логические вычисления.

В языке Verilog рассматриваются значения сигналов 0, 1 для уровней L и Н, X — неопределенный уровень.

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

Z — плавающий уровень на входах — вызывает неопределенное значение X на выходе.

Таблица истинности для определения логических связок с четырехзначными сигналами следующая:

В системах с языком VHDL при моделировании рассматриваются пять значений сигналов. К перечисленным для Verilog сигналам добавляется значение U — неинициализированное значение:

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

Рассмотренный выше пример (см. рис. 6.4) позволяет предложить алгебраическое обобщение, которое может быть представлено алгоритмом,^[1]

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

Пусть значения реализуемой булевской функции / заданы в виде таблицы истинности. Обозначим значение выхода построенной схемы Z. Построим метамодель схемы для значений выхода Z, равных 0 и 1, в виде кубического покрытия КС = C°(Z) u C*(Z), в котором совмещена логика переключения значения выхода 0/1 и, соответственно, 1/0. Покрытие имеет отношение к представлению булевых функций в виде я-мерных кубов для функции от п переменных².

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

Основные типы двухвходовых логических элементов приведены на рис. 6.5.

Рис. 6.5. Двухвходовые вентили ИЛИ (а)> И (б), ИЛИ-HE (в), НЕ-И (г) Таблицы покрытия, описывающие логику работы двухвходовых логических элементов, представленных на рис. 6.5, следующие.

Покрытия наборов для единичных значений соответствующих элементарных функций:

Покрытия наборов для нулевых значений соответствующих элементарных Функций:

• 1 Алгебраический синтез тестов логических схем с использованием трехзначной логики на основе покрытий см. в работах: Зыков А. Г., Немолочнов О. Ф., Поляков В. И. Построение комплексного покрытия последовательностных схем методом пересечения покрытий систем булевых функций // Научно-технический вестник СПб ГИТМО (ТУ). Вып. 6. Информационные, вычислительные и управляющие системы / гл. ред. В. Н. Васильев. СПб.: Изд-во СПб ГИ’ГМО (ТУ), 2002. С. 109—112; Проектирование цифровых вычислительных машин / С. А. Майоров [и др.]; под ред. С. А. Майорова. М.: Высшая школа, 1972.
• 2 Миллер Р. Теория переключательных схем. Т. 1. Комбинационные схемы: пер. с англ. М.: Мир, 1970.
• 1

Например, набор из (б) х_хх₂г = 0×0 — результат склеивания двух смежных наборов входных переменных, сохраняющий значение нуль на выходе элемента.

Кубические покрытия двухвходовых вентилей легко обобщить для «-входовых вентилей.

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

Исходными данными для алгоритма являются одновыходная логическая схема, заданная в виде соединения логических элементов, а также кубические покрытия этих элементов. Результат работы алгоритма — кубическое покрытие С^[2] или С°, координатам кубов которого сопоставлены входы логической схемы. Вычисление кубического покрытия одновыходной комбинационной схемы производится по шагам.

• 1. Фиксируем выход схемы в значении 1 для построения С^[2] или в значении 0 для построения С°.
• 2. Применяем подстановку, которая сопоставляет значению р, р е {0, 1}, на выходе элемента схемы i его кубическое покрытие С?. В кубе, содержащем р по координате, соответствующей элементу i, р заменяется на х, после чего куб заменяется его пересечением с С[.
• 3. Если подстановки выполнены не для всех элементов схемы, шаг 2 повторяется.

Рассмотрим процесс построения покрытия на примере.

Пример 6.1.

Пусть задана одновыходная комбинационная схема (рис. 6.6), реализующая булеву функцию z₃ = х_х & х₂ v х₂ & х₃, где х₂ и х₃ — независимые входы; z_t и z₂ — промежуточные переменные (выходы элементов схемы); z₃ — выход схемы и B_t, в₂ и в₃ — элементы схемы.

Рис. 6.6. Функциональная схема к примеру 6.1.

Для каждого элемента в соответствии с его типом (логической функцией) предварительно выпишем вырожденные покрытия по их входам и выходу. В данной схеме использованы две двухвходовые схемы И и одна ИЛИ. Их вырожденные покрытия (см. рис. 6.5): С], С$ для элементов Bj и в₂ (обозначим C](z,) и C^(2j) для элемента B_lf C](z₂) и C%(z₂) для элемента в₂) и С}, Cj* для элемента в₃ (обозначим Cj (2₃) и С{*(г₃)).

Построение покрытия начинается от выхода схемы z₃ заданием значений z₃ = 1 для построения единичного покрытия C^l(z₃) и z₃ = 0 для построения нулевого покрытия схемы C°(z₃). Значение z₃ — 1 обеспечивается объединением двух кубов C}(z₃), в первом из которых необходимо обеспечить z_x = 1, а во втором — z₂ = 1. Безразличное значение х не раскрывается. Значение z_t = 1 обеспечивается кубом C](z,), а значение z₂ = 1 — кубом C](z₂). Произведя соответствующие подстановки и пересечения с исходными кубами, где все нераскрытые координаты полагаются равными х, получим покрытие схемы в едином формате:

Аналогично, задавая значение z₃ = 0, построим нулевое покрытие схемы Cj⁰(z₃). Значение z₃ = 0 обеспечивается подстановкой куба C₃(z₃) и выполнением пересечения кубов C%(z_x) с кубами C₂(z₂). Выполнив требуемые подстановки и пересечения, получим нулевое покрытие схемы в едином формате:

В построенном покрытии C°(z₃) кубы С₃и С₆ покрываются кубом С₅. Это объясняется структурой схемы: переменная .г*₂ подается на два вентиля: по С₃ z_x = 0, а по С₆ z₂ = 0. Эти кубы будут использоваться при построении тестовых наборов для активизации путей.

Для верификации схемы требуется установить соответствие между покрытиями 0(f) и С°(/) и C°(Z) u O (Z), которое может быть выполнено с помощью операции вычитания (#) и пересечения (п) кубов покрытий. Операция вычитания из куба С_{ куба С. обозначается как С, # С и служит для убирания из куба С, общей части кубов Cj и Cj. Операция пересечения кубов Cj и С, обозначается С, n Cj и служит для выделения куба, являющегося общей частью кубов С, и Cj.

При использовании операции вычитания для верификации схемы необходимо, чтобы C^X(J) # C^l(Z) = 0, и достаточно, чтобы C^l(Z) # C^l(f) = 0. Аналогично для покрытий C°(f) и C). Из этого следует, что при использовании операции вычитания достаточно иметь только один тин покрытий: либо единичное С^!(/) и C^l(Z), либо нулевое C°(f) и C°(Z).

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

• 1) C^l(f) # C^l(Z) = 0 и C'(Z) # C^l(J) = 0, или C'(f) п C°(Z) = 0 и С°(/) п C'(Z) = = 0 — это условие полной верификации;
• 2) CMJ) # C^X(Z) Ф 0 и C) # С¹0) = 0, или С¹0) п C°(Z) ±0 и С°(/) п C) = = 0 — это необходимое, но нс достаточное условие верификации;
• 3) C'(f) # C^l(Z) = 0 и C^l(Z) # C^l(J) Ф 0, или C'(f) n C°(Z) = 0 и C°(f) n C'(Z) Ф Ф 0 — это достаточное, но не необходимое условие верификации;
• 4) C^l(f) # C) Ф 0 и C) # C'(J) Ф 0, или 0(J) п C) Ф0 и С°(/) n C*(Z) * * 0 — условия верификации отсутствуют.

Во втором и третьем случаях можно говорить о верификации частично определенных функций с использованием размытых множеств, иначе говоря, один объект «делает» больше, чем другой. Таким образом, получаем, что полная верификация существует только при выполнении соотношений первого случая¹.

Для приведенной в примере схемы получен следующий тест:

в котором Fj =f₄ и t₃ = t_A. Эти наборы можно объединить с целью минимизации длины текста.

• [1] Поляков А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры. М.:Солон-Пресс, 2003.
• [2] Миллер Р. Теория переключательных схем. Т. 1. Комбинационные схемы.
• [3] Миллер Р. Теория переключательных схем. Т. 1. Комбинационные схемы.
• [4] Миллер Р. Теория переключательных схем. Т. 1. Комбинационные схемы.