Ви є тут

Методи синтезу модулів сигнатурного моніторингу для дискретних пристроїв, що самотестуються.

Автор: 
Темніков Ігор Миколайович
Тип роботи: 
Дис. канд. наук
Рік: 
2004
Артикул:
3404U003953
129 грн
Додати в кошик

Вміст

РАЗДЕЛ 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 при проектировании ДУ, а также правила тестопригодного проектирования позволяют свести процедуру диагностирования к проверке исправности комбинационной части ДУ. Анализ современных разработок ДУ показывае