Разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга

применение разработанных методов синтеза для реализации модулей сигнатурного мониторинга на ПЛИС.

РАЗДЕЛ 2. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА СР С ЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

2.1 Анализ методов генерации тестов на сдвиговых регистрах с обратной связью

2.1.1 Сдвигово - регистровые последовательности, основные определения и анализ

Внедрение нанометровых технологий в процесс производства интегральных схем и ДУ на их основе, повышение быстродействия логических элементов и сложности современных устройств на СБИС определяет актуальность использования встроенных средств диагностирования их исправности на рабочей частоте. В качестве генераторов тестов и схем сжатия выходных последовательностей ДУ находят широкое применение сдвиговые регистры с линейными и нелинейными обратными связями [4, 17, 20, 63, 64, 112].

Определение 2.1. Сдвиговый регистр (СР) размерности n с функцией f обратной связи - это цепь из n последовательно соединенных триггеров , состояния которых в момент времени t определяют значение функции в последующий момент времени , где - выходы соответствующих разрядов СР (рис. 2.1).

Известно, что СР с обратной связью (СРОС) генерируют периодические последовательности, длина которых может принимать значения от 1 до 2n, а последовательность состояний СР с циклом максимальной длины порождает множество всех двоичных n - мерных векторов [65]. Функция обратной связи СРОС , , индуцирует отображение F: , для которого , где и .

СРОС есть конечный автомат, заданный уравнениями:

где - вектор состояния СР,

- множество выходов СР, - длина СР,

- логическая функция ОС,

Рис. 2.1. n - разрядный сдвиговый регистр с функцией обратной связи .

Поэтому поведение СРОС также, как поведение любого конечного автомата, может представляться в трех формах: графом переходов, таблицей переходов - выходов и в матричной форме [65].

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

Определение 2.2. Циклом длиной в графе есть последовательность различных вершин таких, что и , где - отображение вершин, индуцируемое графом .



Для анализа свойств циклов в СР и способов их построения введём следующие определения.

Определение 2.3. Пусть - вектор состояний СР длиной n. Будем называть вектор левосопряженным, а вектор правосопряженным вектору состояний X, если выполняется:

(2.1)

Определение 2.4. Сдвиговый регистр, у которого функция обратной связи будем называть СР с петлевой обратной связью или циркулирующим сдвиговым регистром (ЦСР).

Определение 2.5. Весом будем называть число единиц в двоичном векторе начального состояния ЦСР.

ЦСР длиной n обладает очевидным свойством: циклический сдвиг его начального состояния порождает циклические последовательности двоичных векторов одного веса.

Определение 2.6. Пусть и - множество вершин в двух циклах и в графе . Два цикла и являются смежными, если и существует вершина в такая, что .

В [65] были определены необходимые и достаточные условия объединения ЦСР с различными весами в один цикл.

Теорема 2.1 [65]. Два смежных цикла и в графе можно объединить в один цикл, если в существует такая вершина такая, что , а в существует вершина такая, что .

Пример 2.1. В графе с функцией обратной связи имеется четыре цикла (рис. 2.3а):

Циклы являются смежными. Применяя теорему 2.1 можно объединить эти циклы в один, как показано на рис. 2.3в и 2.3с.

Рис. 2.3. Циркулирующий СР длиной 3 и циклы в графе .

Определение 2.7. Эйлеров цикл в графе - путь, проходящий через каждую из дуг только один раз.

Определение 2.8. Гамильтонов цикл в графе - путь, проходящий через каждую из вершин только один раз.

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

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

Минимальная дизъюнктивная нормальная форма этой функции

(2.2)

Однако простейшей аппаратной реализацией этой функции является форма ее представления в виде

(2.3)

Известно, что в графе число k гамильтоновых циклов равно[39]

(2.4)

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

Так как функция обратной связи СР равна 1 на наборах n - мерных двоичных векторов, то ее всегда можно представить в виде разложения:

(2.5)

В этом случае задача простейшей реализации функции обратной связи сводится к нахождению минимальных форм представления функции g.

2.1.2 Синтез ГПТ на сдвиговых регистрах с линейной обратной связью

Как было показано в разделе 1, ограничения, связанные с экспоненциальным ростом числа тривиальных тестов с увеличением размерности ДУ и числа его входов, преодолеваются применением псевдоисчерпывающего тестирования, а требования стандарта IEEE 1149.1 при проектировании ДУ, а также правила тестопригодного проектирования позволяют свести процедуру диагностирования к проверке исправности комбинационной части ДУ. Анализ современных разработок ДУ показывает, что комбинационная схема (КС) с n входами и m выходами обладает конусной зависимостью m выходов от входных переменных. Число входов , от которых зависит каждый выход схемы, называют показателем зависимости соответствующего конуса.

Пусть - максимальное значение показателя зависимости всех m выходов КС. Тогда схема с n входами, m выходами и k - максимальным показателем зависимости может быть проверена исчерпывающим тестом длиной .

Проблема генерации оптимальных псевдоисчерпывающих тестов исследуется в ряде работ [20, 63, 66] . Универсальные генераторы для схем можно использовать для всех классов и структур логических схем с одинаковыми значениями n и k. Такие генераторы формируют n - мерные двоичные векторы, которые накрывают все k - мерные двоичные подпространства, т.е. любые k столбцов в последовательностях n - мерных двоичных векторов содержат все возможных двоичных наборов. Построение универсальных генераторов тестов основано на использовании СРЛОС и кодов с постоянным весом [20], линейных кодов [67, 68] или циклических кодов [69]. Теория кодирования позволяет определить необходимые полиномы обратной связи в СР, однако для специфических схем, не требующих соблюдения принципа универсальности, размерность тестовых последовательностей и аппаратурные затраты на реализацию встроенных генераторов намного меньше, чем у универсальных.

Генераторы псевдоисчерпывающих тестов (ГПТ) для заданной схемы можно спроектировать путем использования двух подходов. В основе первого подхода используется структура СРЛОС/Сдвиговый регистр (СРЛОС/СР) (рис. 2.4а) [17]. Во втором подходе псевдоисчерпывающие тестовые последовательности длиной, приближающейся к нижней границе, можно генерировать комбинацией СРЛОС и логических элементов Исключающее ИЛИ (СРЛОС/XOR) как показано на рис. 2.4в.

Рис. 2.4 Структуры генераторов тестов на основе: а) СРЛОС/СР, в) СРЛОС/XOR

В структуре СРЛОС/СР (рис. 2.4а) первые триггеров СР замкнуты линейной обратной связью в соответствии с примитивным полиномом степени . Остальные триггеров соединены последовательно, образуя цепь СР. Триггеры СРЛОС генерируют - мерные тестовые сигналы, представляющие собой остатки от деления на полином входной последовательности. Остаток , представляющий тестовый сигнал, генерируемый триггером , равен 1. Следовательно, множество остатков, формируемых триггерами представляется как , и соответствует независимым тестовым сигналам, генерируемым триггерами СРЛОС.

Для триггеры СР генерируют - мерные двоичные наборы, линейно зависимые от - мерных тестовых последовательностей СРЛОС. Для триггера остаток определяется как . Если равен , то остаток является линейной комбинацией остатков и , формируемых на выходах триггеров и . Поэтому тестовые последовательности на выходе являются линейной комбинацией последовательностей на выходах триггеров и .

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

Теорема 2.2 [17]. Выходной конус, который зависит от входов , проверяется исчерпывающим тестом тогда и только тогда, когда остатки являются линейно независимыми.

Псевдоисчерпывающие тесты, генерируемые структурой СРЛОС/СР, чаще всего имеют длину значительно превышающую нижнюю границу . Для исключения этого недостатка используются генераторы со структурой СРЛОС/XOR (рис. 2.4в) [64, 113]. Это позволяет снизить длину тестовой последовательности для заданной схемы, но требует повышения аппаратурных затрат.

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

Генераторы такого типа, как правило, позволяют формировать псевдоисчерпывающие тесты минимальной длины на основе анализа информации о зависимости выходных конусов, но при этом требуют больших аппаратурных затрат по сравнению с СРЛОС/СР [64].

В следующем разделе представлен метод синтеза генераторов псевдоисчерпывающих тестов (ГПТ), основанный на структурах типа СРЛОС/СР, и предложен метод модификации этой структуры путем формирования линейно независимых остатков, как это выполняется в структурах ГПТ типа СРЛРОС/XOR. Это позволяет предельно приблизиться к минимальной нижней границе длины проверяющей последовательности при минимальных аппаратурных затратах на реализацию ГПТ.

2.2 Синтез ГПТ на основе структуры модифицированного СРЛОС/СР

В структуре генератора модифицированного СРЛОС/СР (МСРЛОС/СР) входы схемы запитываются выходами триггеров СРЛОС/СР. При формировании остатков, соответствующих каждому разряду СР, и анализе сочетаний зависимостей выходных конусов схемы может оказаться, что некоторые остатки являются линейно зависимыми для некоторых выходов. В структуре СРЛОС/СР разряды СР, соответствующие этим остаткам, не используются для формирования тестовых последовательностей, но входят в состав генератора, увеличивая при этом аппаратурную избыточность (разряды на рис. 2.5а). Оставшиеся разряды СРЛОС/СР обеспечивают линейную независимость остатков в соответствии с Теоремой 2.2. Избыточные разряды в этой структуре и соответствующие триггеры СР можно исключить из схемы ГПТ, используя вентили Исключающее ИЛИ, как показано на рис. 2.5в. Остатки, генерируемые триггером , формируются путем свертки по mod2 линейных комбинаций остатков . Структуру генератора, полученную в результате выполнения этих процедур, будем называть модифицированным СРЛОС/СР.

Рис. 2.5 Структура ГПТ на основе модифицированного СРЛОС/СР:

а) остатки от деления, соответствующие входам схемы;

в) структура МСРЛОС/СР.

Процесс формирования разрядов ГПТ продолжается до тех пор, пока не завершится формирование разряда с линейно независимыми остатками, который запитывает последний вход схемы . Если для формирования тестовых последовательностей используется примитивный полином степени k, то область циклически повторяющихся остатков в цепи СРЛОС/СР равна [114].

В том случае, когда комбинации линейно независимых остатков, соответствующих комбинациям входных переменных для всех выходных конусов схемы, превышают область , необходимо увеличить на 1 степень примитивного полинома. Вычисляются остатки для цепи СРЛОС/СР, генерируемые с помощью полинома степени , и затем повторяется процедура формирования разрядов ГПТ для этой схемы. При этом возрастает длина проверяющей последовательности до тестовых наборов.

Аппаратурные затраты на реализацию ГПТ на основе МСРЛОС/СР определяются количеством используемых вентилей XOR, а также вектором начальной установки. Так как СРЛОС не формирует тестового набора из всех нулей , то для его формирования необходимо использовать мультиплексоры 2 на 1 в тех разрядах СР, которые в соответствии с вектором начальной установки равны 1.

Пример 2.2. Пусть задана комбинационная схема (6, 5, 3), имеющая 6 входов и 5 выходных конусов , как показано на рис. 2.6.

Построить ГПТ (3, 6) на основе МСРЛОС/СР, который на шести входах схемы (6, 5, 3) формирует 23 различных векторов для всех пяти выходных конусов схемы.

Рис. 2.6. Комбинационная схема (6,5,3).

Так как k = 3, то для генерации тестовых наборов выбираем примитивный полином третьей степени . Остатки, формируемые цепью СРЛОС/СР с полиномом в обратной связи, приведены на рис.2.7а. Выходы триггеров можно приложить ко входам , так как остатки, соответствующие этим разрядам, являются линейно независимыми для всех выходных конусов схемы. Выход триггера не может запитывать вход так как множество остатков для выходного конуса являются линейно зависимыми. Пропуская разряд , запитаем входы и выходами триггеров и соответственно, как показано на рис. 2.7а. Такое отображение выходов ГПТ на входы проверяемой схемы обеспечивает линейную независимость множеств остатков для всех пяти выходных конусов схемы.

В структуре генератора СРЛОС/СР пропущенный триггер создает дополнительную аппаратную избыточность, которую можно сократить путем использования 2 - входового вентиля XOR, заменяющего триггер в цепи СРЛОС/СР. Так как выход формирует остаток , который определяет формирование остатков в разрядах и , то функция возбуждения триггера в виде обеспечивает генерирование остатков разрядами и , как показано на рис. 2.7в. Такой МСРЛОС/СР генерирует (23-1) исчерпывающих тестов для всех пяти конусов схемы (6,5,3).

Теорема 2.3. Для схемы существует ГПТ со структурой МСРЛОС/СР степени тогда и только тогда, когда существует ГПТ со структурой СРЛОС/СР той же степени .

Доказательство. Необходимость. Пусть существует генератор на основе СРЛОС/СР степени для схемы. Тогда схему СРЛОС/СР можно преобразовать в схему генератора МСРЛОС/СР следующим образом. Остатки, генерируемые разрядами СРЛОС/СР, которые являются линейно зависимыми в комбинации с некоторыми другими разрядами для заданной схемы, можно сформировать с помощью элементов XOR, как было рассмотрено выше в примере 2.2. В результате такого преобразования схему СРЛОС/СР всегда можно трансформировать в схему МСРЛОС/СР.

Достаточность. Любой генератор на основе МСРЛОС/СР можно преобразовать в эквивалентный генератор со структурой СРЛОС/СР путем замены элементов XOR триггерами СР, генерирующими соответствующие остатки, которые в структуре СРЛОС/СР не запитывают входы схемы. Теорема доказана.

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

Рис. 2.7. Генераторы тестов:

а) на основе структуры СРЛОС/СР;

в) на основе МСРЛОС/СР

Процедура синтеза ГПТ на основе МСРЛОС/СР для тестирования заданной схемы, который обеспечивает генерацию псевдоисчерпывающих тестов минимальной длины с минимальными аппаратурными затратами, предполагает выполнение следующих шагов:

вычисление остатков, генерируемых цепью СРЛОС/СР на основе примитивного полинома степени k и выше;

анализ множеств остатков, соответствующих m выходным конусам схемы с целью нахождения конусов с линейно зависимыми остатками;

исключение линейной зависимости множеств остатков путем соответствующего выбора разрядов сдвигово - регистрового сегмента генератора;

минимизация числа исключаемых разрядов СР;

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

Для реализации алгоритма и программы используются неприводимые полиномы степени n. В качестве примера в таблице 2.1 приведены неприводимые полиномы степени [70].

Таблица 2.1

Неприводимые полиномы.

N	Формула полинома	N	Формула полинома
3		10
4		11
5		12
6		13
7		14
8		15
9		16

Алгоритм определения линейной зависимости остатков для синтеза ГПТ на МСРЛОС/СР.

Шаг 1.Инициализация массива остатков (СРЛОС).

Шаг 2.Ввод n-степени полинома, ввод неприводимого полинома .

Шаг 3. Формирование диапазона остатков полинома СР. .

Шаг 4.Ввод интересующих остатков полинома СРЛОС и СР на предмет определения линейной зависимости;

Шаг 5.Проверка количества введенных остатков полинома . Если количество , то вернуться к шагу 4, в противном случае перейти к шагу 6.

Шаг 6. Преобразование введенных остатков СРЛОС в элементы массива . Функция READPOL.

Шаг 7. Формирование массива остатков и заполнение элементов “-1”.

Шаг 8. Начало цикла деления многочленов. От до выполнять деление.

Шаг 9.Формирование массива делителя .

Шаг 10.Запуск функции - деление полиномов. Формирование массива остатков .

Если , то перейти к шагу 8, в противном случае перейти к шагу 11.

Шаг 11. Считывание остатка СР и выполнение Шейкер-сортировки по убыванию степени остатка.

Шаг 12. Цикл поэлементного сравнения остатков СРЛОС и СР . Совпадение каждого следующего элемента увеличивает переменную результат rez на 1. Если , то вывод результата rez, в противном случае , выполнение сравнения следующего элемента.

Шаг 13. Если количество совпадений в шаге 12 , то вывод сообщения о линейной зависимости интересующих остатков. В противном случае вывод сообщения о линейной независимости заданных оператором остатков. Вывод времени работы программы.

Шаг 14.Конец алгоритма.

По вышеуказанному алгоритму составлена программа, которая осуществляет определение линейной зависимости остатков для схемы на основе МСРЛОС/СР. Листинг программы приведен в приложении В.1.

2.3 Синтез ГПТ на основе параллельно функционирующих СРЛОС/СР

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

Генераторы на параллельных СРЛОС/СР (ПСРЛОС/СР) для заданной схемы можно построить путем анализа остатков в цепи СРЛОС/СР [115]. Предположим, что остатки, формируемые разрядами СРЛОС/СР, которые запитывают входы схемы, являются линейно независимыми, как показано на рис. 2.8а.

Пусть и - степени примитивного полинома, а сумма . Разряды СРЛОС с остатками запитывают входы проверяемой схемы, соответственно. Выходы разрядов СР с линейно зависимыми остатками не используются для генерации тестов, а выходы разрядов СР с остатками запитывают входы . Поэтому ГПТ на основе СРЛОС/СР содержит дополнительных (избыточных) триггеров, заштрихованных на рис. 2.8а, которые не запитывают входы проверяемой схемы. Эти избыточные разряды можно исключить, если использовать структуру параллельно функционирующих СРЛОС/СР.

Триггеры образуют цепь СРЛОС/СР, как показано на рис. 2.8в. Обе схемы генерируют псевдоисчерпывающие тестовые последовательности с помощью СРЛОС, имеющих одну и ту же степень примитивного полинома.

Пусть разряды первого СРЛОС формируют остатки при некотором начальном состоянии триггеров, исключая вектор состояний из всех 0. Вектор начального состояния триггеров определяет начальные состояния последующих разрядов ПСРЛОС/СР. Например, если вход проверяемой схемы запитывает разряд с линейными комбинациями остатков (где ), то начальное состояние триггера определяется из выражения , где - начальные состояния триггеров с соответствующими номерами разрядов.

Пример 2.3. Спроектировать ГПТ на основе ПСРЛОС/СР для схемы (6,5,3), заданной на рис. 2.6. Выходы триггеров цепи СРЛОС/СР и соответствующие им остатки приведены на рис. 2.9а. Если исключить разряд , заштрихованный на рис. 2.9а, то обеспечивается линейная независимость остатков, которые формируются на входах всех пяти конусов проверяемой схемы.

В соответствии с вышеизложенной методикой синтезируется схема ПСРЛОС/СР, состоящая из двух (3,3) СРЛОС/СР, как показано на рис. 2.9в. Обе схемы СРЛОС/СР основаны на примитивном полиноме . Разряд первого СРЛОС генерируют остатки . Пусть начальное состояние первых трех разрядов равно . Тогда начальные состояния триггеров определяются путем суммирования по mod2 начальных состояний триггеров первого СРЛОС/СР, что позволяет генерировать (23-1) псевдоисчерпывающих тестов на входах всех пяти конусов схемы в соответствии с рис. 2.9в.

Следующая ниже теорема определяет взаимосвязь между двумя структурами ГПТ на основе МСРЛОС/СР и ПСРЛОС/СР.

Теорема 2.4. Для схемы существует генератор тестов на основе структуры ПСРЛОС/СР тогда и только тогда, когда для этой схемы существует генератор тестов на основе МСРЛОС/СР, у которого длина каждого сдвигово - регистрового сегмента по крайней мере не меньше .

Рис. 2.9. Генератор псевдоисчерпывающих тестов на основе ПСРЛОС/СР:

а) вычисление остатков в цепи СРЛОС/СР;

в) структура ПСРЛОС/СР для (6,5,3) схемы.

Доказательство. Необходимость. Пусть существует МСРЛОС/СР, который генерирует псевдоисчерпывающие тесты для схемы, состоящий из сдвигово - регистровых сегментов длиной не менее разрядов. Тогда схему генератора можно заменить отдельными параллельно функционирующими схемами СРЛОС/СР с одними и теми же примитивными полиномами степени , которые генерируют тестовые последовательности длиной в схеме МСРЛОС/СР. При этом начальные состояния отдельных СРЛОС/СР остаются такими же, как в сдвигово - регистровых сегментах генератора МСРЛОС/СР, что обеспечивает линейную независимость остатков в разрядах параллельно функционирующих СРЛОС/СР.

Достаточность. Пусть имеется ПСРЛОС/СР для схемы. Отдельно функционирующие СРЛОС/СР в таком генераторе можно преобразовать в структуру МСРЛОС/СР путем последовательного соединения сдвиговых регистров в единую сдвигово - регистровую сеть, обеспечивая исключенные разряды формирователями остатков с помощью элементов XOR. Это позволяет последующим разрядам МСРЛОС/СР генерировать остатки, соответствующие разрядам генератора на ПСРЛОС/СР. Построенная схема МСРЛОС/СР будет состоять из сдвигово - регистровых сегментов, имеющих по меньшей мере разрядов. Теорема доказана.

Из теоремы 2.3 следует, что генераторы на основе структуры ПСРЛОС/СР по аппаратурным затратам на их реализацию и по длине генерируемых тестовых последовательностей практически совпадают с генераторами МСРЛОС/СР в том случае, когда сдвигово - регистровые сегменты МСРЛОС/СР кратны степени примитивного полинома. Если это условие не выполняется, то предпочтительнее использовать генераторы на основе структуры МСРЛОС/СР.

Пример 2.4. Пусть задана (6,7,3) схема, которая является расширением схемы рис. 2.6 путем добавления двух выходных конусов и . Необходимо построить схему генератора псевдоисчерпывающих тестов минимальной длины.

Так как , то для построения генератора (3,6) на основе МСРЛОС/СР необходимо устранить разряды с линейно зависимыми остатками. Используя остатки, представленные на рис. 2.9а, находим, что выходы и не могут запитывать входы и (6,7,3) схемы, так как множество остатков и для выходных конусов и , соответственно, являются линейно зависимыми. Следовательно, необходимо увеличить степень примитивного полинома на 1, что приводит к увеличению длины проверяющей последовательности: . Генератор тестов для этой схемы представлен на рис.2.10.

Рис. 2.10. ГПТ для (6,7,3) схемы.

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

2.4 Синтез самотестируемых сигнатурных анализаторов

Широкое распространение 16 и 32 разрядных микропроцессоров и устройств управления на их основе приводят к необходимости повышения достоверности обнаружения ошибок в процессе выполнения управляющих программ. Увеличение объема информации в процессе сигнатурного мониторинга, анализируемой многоканальными сигнатурными анализаторами (МСА), а также времени анализа повышает вероятность ошибок как устройств управления, так и схем встроенного самотестирования. В связи с этим возникает задача синтеза МСА, которые самотестируются в процессе сжатия последовательностей, поступающих на их входы.

В работах [16, 71] предложены методы обнаружения ошибок с помощью встроенных средств на основе объединения процедур функционального и тестового диагностирования сложных дискретных устройств. Получены оценки вероятностей обнаружения ошибок при использовании встроенных схем контроля на четность функциональных схем и сигнатурных анализаторов.

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

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

Рис. 2.11. Сигнатурный мониторинг МК.

Схема СА, сохраняющего четность состояний, представлена на рис. 2.12.

Выходы комбинационного устройства, соединенные с входами анализатора, закодированы паритетным кодом по четности. Выходы также закодированы паритетным кодом по четности и при отсутствии ошибок .

Сохраняющий четность сигнатурный анализатор содержит D - триггеров и один дополнительный D - триггер . Дополнительный триггер гарантирует, что четность содержимого D - триггеров остается постоянной до тех пор, пока входы анализатора остаются элементами паритетного четного кода. Если паритет вектора состояний является четным, то .

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

(2.6)

(2.7)

Сложив равенства (2.6) по модулю два получаем:

(2.8)

Так как и

являются элементами паритетного четного кода, то выполняются равенства:

(2.9)

(2.10)

и следовательно

(2.11)

Согласно равенствам (2.9) - (2.11) четный паритет состояния анализатора сохраняется, если входные векторы имеют четный паритет.

Паритет вектора состояний изменяется согласно (2.8), если на вход анализатора поступает вектор с нечетным паритетом.

Из (2.6) и (2.7) можно заключить, что

(2.12)

и

(2.13)

до тех пор, пока выполняется (2.11).

Покажем синтез многоканального сигнатурного анализатора сохраняющего четность на примере 2.5.

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

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

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

Дополнительный триггер обеспечивает сохранение четности сигнатурного анализатора.

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

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

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

Таблица 2.2.

Значения функций в контрольных точках самопроверяемого МСА.

№ такта
1	1	0	0	0	1	0	0	0	0	0	0	0
2	1	0	1	1	1	1	0	0	0	1	0	0
3	0	1	1	1	1	1	1	1	1	0	0	0
4	1	1	0	0	0	0	0	0	0	0	0	0
5	0	0	1	0	1	1	1	0	0	0	0	0
6	1	1	0	1	1	0	1	0	0	1	0	0
7	1	0	1	0	0	1	1	1	1	0	0	0
8	0	1	0	0	1	1	1	0	1	1	1	1
9	0	0	1	1	0	1	0	1	0	0	1	1
10	1	1	1	0	1	1	1	1	0	1	1	1
11	0	0	0	1	1	0	0	0	1	1	1	1
12	1	1	1	1	0	1	0	0	1	0	1	1
13	1	0	0	1	0	0	0	1	1	0	1	1
14	0	1	0	1	0	1	0	0	0	1	0	0
15	0	1	1	0	0	0	0	0	1	1	1	1
16	1	0	0	0	1	1	1	1	0	1	1	1

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

2.5 Синтез самопроверяемого сигнатурного анализатора на основе схемы потактного сравнения значений выходных переменных

В основу контроля правильности функционирования многоканального сигнатурного анализатора положено аддитивно - циклическое свойство М - последовательностей, т.е. сумма mod 2 циклических сдвигов М - последовательности является циклическим сдвигом той же М - последовательности. Следовательно, операцию сумма mod 2 можно использовать в качестве операции контроля правильности функционирования многоканального сигнатурного анализатора [112].

Проиллюстрируем этот метод на примере сигнатурного анализатора с порождающим многочленом [70].

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

(2.14)

Складывая равенства (2.14) по модулю два, получаем

(2.15)

Обозначив левую часть равенства через , а правую через , получаем уравнение самоконтроля: А = В

Схема синтезированного таким образом самопроверяемого многоканального сигнатурного анализатора приведена на рис. 2.14.

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



2.6 Выводы

Проведен анализ методов генерации псевдоисчерпывающих тестов на сдвиговых регистрах с обратной связью для проверки исправности схем. Показано, что учет специфических особенностей конусной зависимости проверяемых схем от входных переменных позволяет реализовать ГПТ на основе использования двух структур генераторов СРЛОС/СР и СРЛОС/XOR с минимальными аппаратурными затратами и минимальной длиной псевдоисчерпывающих тестовых последовательностей.

Предложен новый метод синтеза ГПТ на основе структуры МСРЛОС/СР, который обеспечивает более простую реализацию ГПТ по сравнению с известными структурами. Для класса схем определены необходимые и достаточные условия существования ГПТ со структурой МСРЛОС/СР степени .

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

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

РАЗДЕЛ 3 ГЕНЕРАТОРЫ ТЕСТОВ НА СР С НЕЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

3.1 Методы генерации полных циклов на сдвиговых регистрах

Известно, что СР с нелинейной обратной связью (СРНОС) широко используются для генерации псевдослучайных последовательностей в технике связи, в системах диагностирования дискретных устройств, в системах защиты информации и т.д. [72 - 75]. СРНОС длиной в n разрядов позволяет генерировать полные циклические двоичные последовательности, состоящие из n - мерных двоичных векторов, которые называются последовательностями Де Брейна. Нахождение последовательности Де Брейна эквивалентно решению задачи нахождения гамильтонова цикла в графе СР, которая была рассмотрена в разделе 2.1.1.

Различные алгоритмы нахождения этих последовательностей приведены в [65, 72]. Алгоритмы, представленные в этих работах, по своей эффективности оцениваются сложностью программных реализаций в битовых операциях и объемах памяти, необходимых для машинной генерации гамильтоновых циклов. Для реализаций этих вычислений требуется выполнить побитовых операций и память бит для вычисления значения функции ОС на каждом шаге генерации полной последовательности [67, 72]. В [74] предложен алгоритм генерации последовательностей Де Брейна, основанный на использовании рекурсивного метода [72], специального языка программирования NESL [73], обеспечивающего простоту сканирования примитивов и механизмов распараллеливания операций. Как отмечает автор этой работы, трансляция этого алгоритма с языка NESL на язык Си позволяет генерировать последовательность Де Брейна длиной за 5 сек на Spartstation IPC [74].

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

Известно, что в графе разрядного СР число различных гамильтоновых циклов равно числу остовных деревьев графа [65]. Остовное дерево графа есть связный ориентированный граф без циклов с числом вершин и числом дуг .

Определение 3.1. Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень исхода каждой вершины, за исключением одной вершины (например, ) равна 1, а полустепень исхода вершины , называемой корнем этого дерева равна 0. Такое дерево часто называют входящим [76].

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

Теорема 3.1. Пусть - n - вершинный граф без петель и - его матрица инциденций с одной удаленной строкой. Пусть - транспонированная матрица к . Тогда определитель равен числу различных остовных деревьев графа .

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

Пусть - граф СР, в котором исключены петли в вершинах и . Построим матрицу смежности графа размерности следующим образом: пересечение i-й строки и i-го столбца матрицы отмечаем числом - полустепень захода вершины ; пересечение i-й строки и j-го столбца - числом дуг из вершины в вершину . В таблице 3.1 представлена матрица смежности графа - трехразрядного СР, которая позволяет определить число остовных деревьев путем вычисления минора - го порядка элемента матрицы смежности . Вычисление определителя D минора элемента дает величину . Таким образом, существует 16 остовных деревьев в графе с корнем в вершине .

Таблица 3.1

Матрица смежности графа

Вершины
	1	-1	0	0	0	0	0	0
	0	2	-1	-1	0	0	0	0
	0	0	2	0	-1	-1	0	0
	0	0	0	2	0	0	-1	-1
	-1	-1	0	0	2	0	0	0
	0	0	-1	-1	0	2	0	0
	0	0	0	0	-1	-1	2	0
	0	0	0	0	0	0	-1	1

С ростом n число остовных деревьев растет с ростом числа его дуг. В теории графов решению проблемы порождения всех остовных деревьев уделялось значительное внимание, так как выбор “наилучшего” дерева, являлось важным оптимизационным критерием при решении сложных технических задач (в теории управления, при прокладке дорог, газопроводов, линий электропередач, при вычислении определителей матриц в макроэкономической теории и т.д.) [77 - 79].

Один из таких способов состоит в использовании элементарных преобразований деревьев для последовательного порождения остовов, начиная с некоторого начального [80]. Однако процедурам, основанным на элементарных преобразованиях деревьев, присущ следующий недостаток: для порождения нового дерева необходимо привлекать все найденные ранее деревья, что приводит к значительному возрастанию времени вычисления и объема оперативной памяти.

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

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

Таблица 3.2

Таблица переходов автоматных моделей 16-ти остовных деревьев графа .

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

По автоматным моделям остовных деревьев графа можно найти множество Гамильтоновых циклов в графе n - разрядного СР по предложенному ниже алгоритму.

Алгоритм 3.1

1. В таблице переходов остовного дерева графа в столбце текущих состояний введем состояние и переход .

Например, для остовного дерева №1 из таблицы 3.2 построим таблицу переходов в соответствии с шагом 1 (Таблица 3.3)

Таблица 3.3

Таблица переходов.

2. Построить ТПВ автоматной модели разрядного СР. Для 3 - разрядного СР ТПВ представляется в виде (Таблица 3.4):

Таблица 3.4

3. В таблице 3.4 отметим кружком все переходы, соответствующие таблице, полученной на шаге 1. Для наглядности остовное дерево (таблица 3.3) и граф с отмеченными дугами представлен на рис.3.1

4. Начальным состоянием выбрать состояние .

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

6. На каждом шаге п. 5 определяется состояние n - разрядного СР, последовательность которых образует Гамильтонов цикл в графе по следующему правилу: , где - состояние - разрядного СР, причем .

Процесс завершается при достижении первоначального состояния .

Возвращаясь к рассматриваемому примеру, из таблицы 3.4 последовательность состояний, образующих гамильтонов цикл в графе четырехразрядного СР, в соответствии с предложенным алгоритмом получается в виде: , , , , , и далее в соответствии с п.п.5,6,7 алгоритма.

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

(3.1)

которая должна формироваться схемой обратной связи СР.

Из последовательности (3.1) СДНФ функции обратной связи СР определяется в виде:



(3.2)

где - выходы триггеров СР; - младший разряд.

Минимальная форма функции находится из карты Карно:

(3.2а)

Использование метода синтеза комбинационных схем, основанного на простой дизъюнктивной декомпозиции, позволяет упростить схемную реализацию функции (3.3) по сравнению с МНДФ, представив её в виде [77]:

(3.3)

;

Выражению (3.3) соответствует схема, представленная на рис. 3.2

Рис. 3.2. Схема, соответствующая выражению (3.3)

Анализ функции (3.2) обратной связи 4 - разрядного СР, порождающий Гамильтонов цикл в графе переходов , показывает, что эта функция удовлетворяет условиям реализуемости ее сетью Майтра [77], т.е. представляется в виде:

(3.4)

Выражению (3.4) соответствует схемная реализация функции обратной связи СР, на рис. 3.3.

Рис. 3.3. Реализация ОС сетью Майтра.

Для оценки аппаратурных затрат на реализацию встроенных схем диагностирования воспользуемся оценочной методикой фирмы Synopsys Inc., которая была разработана для КМОП технологии производства интегральных схем (0,6 мкм, 2 - слойная металлизированная подложка, 5V питание) [78]. В качестве единичного вентильного эквивалента (в.э.) используется 2 - входовый И-НЕ (ИЛИ-НЕ) элемент. Аппаратурные затраты оцениваются, исходя из технологических затрат на реализацию различных схемных элементов, представленных в вентильных эквивалентах (Табл. 3.5)

Таблица 3.5

Методика оценки аппаратурных затрат Synopsys Inc.

2-вх. И(ИЛИ)	1,3в.э.
2-вх. ИСКЛ.-ИЛИ	2,0в.э.
2 на 1 мультиплексор	1,7в.э.
D-триггер	3,6в.э.
3-вх. И- НЕ(ИЛИ-НЕ)	1,5в.э.
Инвертор	0,7в.э.

Представляя выражение (3.2а) и (3.4) в базисах И-НЕ элементов с целью сравнения затрат на реализацию функций обратной связи СР, порождающих Гамильтонов цикл в графе , и используя данные таблицы 3.5, получим:

Реализация по МДНФ -7,0 в.э.

Реализация декомпозиционным методом -5,7 в.э.

Реализация сетью Майтра -3,5в.э.

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

Существующие процедуры синтеза произвольных логических функций сетью Майтра основаны на последовательном переборе всех переменных для определения условий тривиальной декомпозиции относительно каждой из них, что с ростом числа переменных приводит к экспоненциальному росту времени вычисления. Поэтому ниже предложен метод синтеза ЛФ, позволяющий решить задачу для числа переменных c меньшей трудоемкостью.

3.2 Реализация логических функций однородной сетью Майтра

Однородными сетями Майтра называют одномерную структуру, состоящую из последовательно соединенных двухвходовых ячеек-вентилей, которые настраиваются на реализацию логической функций И, ИЛИ, Исключающее ИЛИ, И-НЕ, ИЛИ-НЕ [81]. На рис. 3.4 представлена одномерная сеть Майтра, которая настраивается на реализацию функции путем приложения к вертикальным входам входных переменных , а на крайний слева боковой вход подается 0(1).

Рис. 3.4. Одномерная сеть Майтра.

Различают бесповторные и повторные сети Майтра [82]. В бесповторных сетях каждая переменная запитывает вход только одной ячейки сети, в противном случае сеть называют повторной. Наиболее подробно свойства таких сетей и методы их настройки для реализации различных логических функций представлены в [81 - 84].

Известно, что любая функция двух переменных реализуется бесповторной сетью Майтра, состоящей по крайней мере из двух ячеек [81].Однако не все логические функции с реализуемы бесповторными сетями Майтра. Для анализа реализуемости функций такими сетями и настройки и настроек ячеек сети чаще всего используются аналитические методы. Наиболее подробно и обоснованно эти методы представлены в [82]. Процедуры анализа реализуемости произвольной ЛФ и методы синтеза в этих подходах основаны на анализе ЛФ декомпозиционными методами, что требует на каждом шаге выполнения синтеза схемы применять разложение Шеннона относительно каждой переменной для исходной ЛФ и всех остаточных функций.

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

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

Например, для ЛФ минтермная матрица представлена в табл.3.6.



Таблица 3.6

	x1	x2	x3
4	1	0	0
6	1	1	0
7	1	1	1

Совершенная дизъюнктивная нормальная форма функции (СДНФ) равна:

(3.5)

Выражение (3.5) можно представить в виде:

(3.6)

Из (3.6) следует, что последним элементом сети Майтра является элемент И, вход которого необходимо запитать переменной , как показано на рис. 3.5.

Рис. 3.5. Конечная ячейка сети Майтра для функции .

Выражение (3.6) и реализацию функции, как показано на рис. 3.5, можно получить путем анализа минтермной матрицы Табл. 3.6. Этот анализ осуществляется следующим образом: пусть - число минтермов заданной ЛФ, а - число единиц в столбце . Для рассматриваемой функции .

Утверждение 3.1. Пусть задана ЛФ . Если число минтермов ЛФ и в минтермной матрице существует по меньшей мере один столбец , у которого или , то крайним правым элементом сети Майтра , реализующим заданную ЛФ, является элемент И.

Доказательство. Если крайний правый элемент сети - элемент И, то ЛФ представляется в одной из двух форм:

(3.7)

Или

(3.8)

Следовательно, столбец в минтермной матрице для выражения (3.7) состоит из единиц и , а для выражения (3.8) - из одних нулей и . Если число , то заданная ЛФ является тривиальной функцией - переменной . Если , то единичных значений покрывается и последним элементом не может быть И, так как функция представляется в виде

(3.9)

Следовательно, . Утверждение доказано.

Утверждение 3.2. Пусть задана ЛФ . Если число минтермов ЛФ и в минтермной матрице существует по меньшей мере один столбец , у которого или , то крайним правым элементом сети Майтра, реализующей заданную ЛФ, является элемент ИЛИ.

Доказательство. Если крайний правый элемент сети - ячейка ИЛИ, то ЛФ представляется двумя формами:

выражение (3.9), рассмотренное выше

или

(3.10)

В выражении (3.9) минтермов ЛФ в столбце должны иметь значение 1, чтобы обеспечить появление в правой части переменной . Следовательно, . В случае, когда в правой части выражения (3.10) появляется , то в столбце минтермной матрицы должно быть нулевых значений, а, следовательно, число единиц в столбце в этом случае равно . Утверждение доказано.

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

Утверждение 3.3. Если число минтермов ЛФ и в минтермной матрице найдется по меньшей мере один столбец , вычеркивание которого приводит к минтермной матрице размерности с различными строками, то крайним правым элементом сети Майтра является элемент Исключающее ИЛИ.

Доказательство. Если крайним правым элементом сети является элемент Исключающее ИЛИ, то ЛФ представляется в виде:

(3.11)

Или

(3.12)

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

Из доказательства Утверждений 3.2 и 3.3 следует, что остаточные функции после удаления столбца минтермной матрицы можно выбирать двумя способами: удалением строк минтермной матрицы с “1” или “0” значениями входных наборов в столбце . В первом случае на вертикальный вход последнего элемента следует подавать переменную , во втором случае . Выбор остаточной функции с минимальным числом минтермов этой функции упрощает дальнейшую процедуру синтеза всей однородной сети Майтра.

Пример 3.1. Реализовать одномерной бесповторной сетью Майтра функцию . Минтермная матрица этой функции представлена в Табл. 3.7.

Из анализа таблицы 3.7 следует, что число минтермов функции . Следовательно, в соответствии с Утверждением 3.2 крайним правым элементом сети Майтра может быть элемент ИЛИ. Так как только для столбца минтермной матрицы выполняется условие реализуемости , то на вертикальный вход элемента ИЛИ следует подать переменную . Остаточная функция представлена минтермной матрицей (Таблица 3.8), которая получена путем удаления из Таблицы 3.7 столбца и строк, соответствующих единичным значениям наборов в этом столбце.

Для остаточной функции и Таблица 3.8 содержит минтермов, что в соответствии с Утверждением 3.3 позволяет утверждать: крайним правым элементом для может быть только элемент Исключающее ИЛИ. Анализ Таблицы 3.8 показывает, что удаление столбца обеспечивает условие реализуемости функции сетью Майтра. При этом имеются два варианта для формирования остаточной функции : удаление строк минтермной матрицы для единичных и нулевых значений наборов в столбце (Таблицы 3.9 и 3.10 соответственно). Это дает два варианта реализации функции сетью Майтра, как это показано на рис. 3.6а,в.

Для сравнения рассмотрим схемную реализацию функции примера 3.1 классическим методом по минимальной дизъюнктивной нормальной форме ЛФ. Из карты Карно функции (Таблица 3.11) ее МДНФ представляется в виде:

(3.13)

Реализация схемы в соответствии с выражением (3.13) уступает схемным реализациям этой функции бесповторной сетью Майтра (рис. 3.6) по аппаратурным затратам.

Рис. 3.6. Два варианта реализации ЛФ примера 3.1 одномерной бесповторной сетью Майтра.

Таблица 3.11

Карта Карно функции примера 3.1

Применяя эти оценки к реализациям функции на рис. 3.6 и к схеме в соответствии с МДНФ (3.13), получаем:

затраты на реализацию бесповторной сетью Майтра составляют 4,0 в.э.;

затраты на реализацию по МДНФ - 9,1 в.э.

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

Ниже приведем обобщенный алгоритм процедуры синтеза одномерной бесповторной сети Майтра для реализации произвольной ЛФ переменных, который основан на доказанных выше теоремах.

Алгоритм 3.2 синтеза ЛФ одномерной бесповторной сети Майтра.

Шаг 1: Построить минтермную матрицу для заданной ЛФ переменных.

Шаг 2: Вычислить число минтермов заданной ЛФ. Если - перейти к шагу 3. Если - перейти к шагу 8.

Шаг 3: Вычислить для каждого столбца минтермной матрицы число единиц . Если перейти к шагу 4, если перейти к шагу 6.

Шаг 4: Найти в минтермной матрице столбец , для которого или . В этом случае крайним правым элементом сети является элемент И. Если , то на вертикальный вход подать , если . В противном случае перейти к шагу 11.

Шаг 5: Построить минтермную матрицу остаточной функции путем удаления столбца . Перейти к шагу 10.

Шаг 6: Найти в минтермной матрице столбец , для которого или . В этом случае крайним правым элементом сети является элемент ИЛИ. Если , то на вертикальный вход подать , если , то подать . В противном случае перейти к шагу 11.

Шаг 7: Построить минтермную матрицу остаточной функции путем удаления столбца и удаления строк исходной матрицы: если - удалить строки с единичным значением в столбце , если - строки с нулевым значением в столбце . Перейти к шагу 10.

Шаг 8: Найти в минтермной матрице столбец , удаление которого дает остаточную минтермную матрицу с различными строками. В этом случае крайним правым элементом является Исключающее ИЛИ, который следует запитать переменной . В противном случае перейти к шагу 11.

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