Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА) - Коммуникации, связь, цифровые приборы и радиоэлектроника дипломная работа
![](/file/c17a668ccb7333e986a5a.jpg)
Главная
Коммуникации, связь, цифровые приборы и радиоэлектроника
Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Основные понятия теории клеточных автоматов, анализ программных и аппаратных реализаций. Разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга. Программа моделирования сетей клеточных автоматов на языке Delphi.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Записка ____ сторінка; 22 малюнка; 16 таблиць; 35 використаних джерел; додатків 2.
У роботі запропоновано новий метод синтезу генераторів детермінованих тестів на сітях клітинних автоматів (СКА). Для заданої множини тестових векторів з необхідним покриттям несправностей синтезується генератор, що алгоритмічно формує цю множину тестів за найменший час. Генератори, що синтезовані запропонованим методом, мають високу швидкодію, регулярну та тестопридатну структуру, а їх реалізація здійснюється з невеликими апаратними витратами.
Ключові слова: КЛІТИННИЙ АВТОМАТ, ГЕНЕРАТОР ТЕСТІВ, СХЕМИ ВБУДОВАННОГО САМОТЕСТУВАННЯ, ЛОГІЧНА СХЕМА ЩО ПРОГРАМУЄТЬСЯ, ДИСКРЕТНИЙ ПРИСТРІЙ
The report contains: 121 p., 22 fig., 16 tab., 35 sources, 2 appendices.
This paper presents a new approach for designing cost-effective test vector generator (TVG). Given a set of precomputed test vector with a predetermined fault coverage, a simple test vector generator is synthesizes to apply the given test. To achieve, cellular automata structure have been used. The resulting TVG is very efficient in terms of hardware size and speed performance, and is very regular and testable. Simulation of various benchmark combinational circuits has given good results when compared to alternative solutions.
Index words: CELLULAR AUTOMATA, TEST VECTOR GENERATOR, BUILT-IN SELF-TEST, PROGRAMMABLE LOGIC ARRAY, DISCRETE DEVICE.
Аналогично вычисляется численное значение для любого правила.
Правило функционирования КА может быть записано в виде булевого выражения. Например, для правила 144, соответствующее выражение будет иметь вид:
где 'x' и '+' операции конъюнкции и дизъюнкции соответственно.
Определение 1. Диаграмма состояний КА.
Диаграмма состояний КА с двумя состояниями представляет собой вектор-столбец, состоящий из нулей и единиц. Обозначим состояние i-й ячейки в момент времени t - , тогда диаграмма состояний i-клетки за m-шагов может быть записана в виде:
где Т - оператор транспонирования матрицы
Определение 2. Диаграмма состояний ячейки СКА.
Диаграмма состояний ячейки, входящей в состав одномерной СКА записывается в виде матрицы, состоящей из трех столбцов (Х i-1 , X i , X i +1 ). Х i - диаграмма на выходе интересующей ячейки, а Х i -1 , X i +1 - диаграммы на выходах левой и правой ячеек соответственно.
Определение 3. Диаграмма состояний СКА.
Диаграмма состояний СКА длины n может быть записана в виде совокупности из n триплет
Каждая совокупность из трех столбцов (Х i -1 , Х i Х i +1 ) представляет диаграмму состояний i-й ячейки сети. Нужно заметить, что столбцы Х 0 и Х n+1 - это столбцы, состоящие из нулей. Эти столбцы соответствуют нулевым граничным условиям.
Определение 4. Детерминизм правил КА.
В данной работе рассматриваются только детерминированные правила. Это значит, что любая пара идентичных состояний окрестности КА приводит его в одно и тоже последующее состояние.
Обозначим состояние окрестности i-й ячейки СКА на шаге t, как
Рассмотрим состояние i - ячейки СКА на шаге t j и t k , t j ?t k , если
Вышеприведенное выражение дает возможность определить, является ли двоичная последовательность, состоящая из трех столбцов, частью диаграммы состояний ячейки СКА.
Определение 5. Универсальная окрестность.
где F представляет правило функционирования КА, а - это состояние окрестности i-й ячейки СКА в момент времени t. Параметр r - это положительное целое число, характеризующее размер окрестности, а, следовательно, и диапазон правил КА [5].
Универсальная окрестность, , ячейки x i , в одномерной СКА длинны n, может быть представлена в следующем виде:
Таким образом, окрестность Фон Неймана является частным случаем универсальной окрестности.
На рис.1.6 показаны два варианта окрестности с г = 1 и г = 2. Как можно заметить, при r =1, на последующее состояние ячейки влияет три переменные, а при r =2 - пять.
Рисунок 1.6 - Универсальная окрестность с r=1 и r=2
Окрестность определяется диапазоном правил КА [6] в зависимости от параметра r следующим образом , где (2r+1) - количество соседних с рассматриваемой ячеек, участвующих в вычислении последующего.
Окрестность Фон Неймана, рассматриваемая в данной работе, позволяет использовать =256 правил. Этот класс КА называют "элементарный КА Вольфрама" [6].
Диаграмма состояний ячейки СКА с универсальной окрестностью состоит из совокупности (2г+1) столбцов (Х i - r ,.,X i ,… X i + r ), где - диаграмма состояний КА. При этом столбцы (X - r +1 , X - r +2 ,…, X 0 ) и (X n+1 , X n +2 ,…, X n + r ) обеспечивают заданные граничные условия.
Увеличение r > 1 и, следовательно, расширение окрестности влечет за собой ряд проблем, одна из которых состоит в кодировании правил, возможное число которых значительно возрастает, в этом случае правила рассматриваются в виде таблицы истинности и соответствующей логической функции. Кроме того, из-за такого расширения окрестности значительно усложняется проектирование СКА с заданными свойствами.
Определение 6. Детерминированность субпоследовательности.
Детерминированность для субпоследовательности S, состоящей из k строк, длины n, на основании (2.1) можно сформулировать следующим образом:
пусть - i-й элемент строки t, тогда субпоследовательность (СП) детерминирована, если
Рисунок 3.1 - Отличительное дерево автомата А-1
Отображение множества допустимых начальных состояний, принадлежащих начальному - множеству, в группы - множеств, которыми отмечены вершины отличительного дерева, полностью определяется функцией переходов-выходов автомата. Например, для автомата А-1
({ } X 1 ) = { 2, 1, 4 }, { 5, 2 }. (3.3)
Блоки разбиения 1 ={} множества состояний A-1 определяют отношение эквивалентности состояний в том смысле, что состояния, принадлежащие каждому блоку разбиения 1 X 1 - неразличимы, а сами блоки разбиения 1 являются X 1 - различимыми. Вершине отличительного дерева (рисунок 3.1), отмеченной разбиением 1 , поставлена в соответствие группа - множеств 1 : {2, 1, 4 },{ 5, 2}, включающих состояния, которые являются преемниками соответствующих состояний блоков разбиения 1 .
В отличительном дереве автомата A-1 каждому - множеству вершины дерева поставлено в соответствие - разбиение множества начальных состояний, для которых состояния - множеств являются конечными состояниями при приложении к входу автомата последовательности входных символов, соответствующих меткам дуг отличительного дерева. Путь в отличительном дереве от его корня до вершины, отмеченной группой простых -множеств, определяет отличительную последовательность минимальной длины. Отличительная последовательность X 0 = ( X 1 , X 1 , X 1 , X 2 , X 1 ) автомата А-1 определяет следующую последовательность - разбиений начальных состояний
Основные понятия теории клеточных автоматов. Анализ подходов встроенного самотестирования цифровых схем. Модули сигнатурного мониторинга на сетях клеточных автоматов. Программа моделирования одномерной сети клеточных автоматов на языке Borland Delphi. дипломная работа [1,9 M], добавлен 31.08.2011
Разработка и совершенствование моделей синтеза и логического проектирования унифицированных модулей сигнатурного мониторинга для повышения эффективности тестового и функционального диагностирования микроконтроллерных устройств управления на их частоте. диссертация [2,3 M], добавлен 29.09.2012
Основные понятия абстрактных детерминированных автоматов Мили и Мура, как монофункциональных так и многофункциональных, реализуемых на триггерах. Понятия многофункциональных детерминированных автоматов 1-го, 2-го и 3-го рода на схемах автоматной памяти. контрольная работа [495,3 K], добавлен 28.03.2018
Знакомство с табличными и графическими способами задания многофункциональных абстрактных детерминированных автоматов. Рассмотрение сфер использования абстрактных автоматов с памятью. Анализ особенностей многофункциональных автоматов Мараховского. контрольная работа [787,5 K], добавлен 28.03.2018
Изучение истории развития теории конечных автоматов. Методы логического проектирования дискретных устройств. Алфавитный способ преобразования информации. Кодирование информации в двоичном алфавите. Многофункциональные автоматы Мараховского с памятью. контрольная работа [103,6 K], добавлен 28.03.2018
Изучение основных понятий теории автоматов. Анализ работы цифровых машин с программным управлением на примере автоматов Мили и Мура. Устройство преобразователей дискретной информации (RS-триггера). Разработка схемы цифрового автомата для сложения чисел. курсовая работа [449,2 K], добавлен 16.09.2017
Принципы организации управляющих автоматов. Разработка и проектирование автомата с жесткой и программируемой логикой. Разработка таблицы прошивки ПЗУ для УА с естественной адресацией микрокоманд. Структурный и абстрактный синтез управляющего автомата. курсовая работа [508,5 K], добавлен 16.03.2011
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА) дипломная работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Дипломная работа: Экономическая безопасность в системе национальной безопасность государства
Реферат На Тему Механизм Аварии На Аэс
Реферат по теме Современные зарубежные концепции воспитания и развития детей
Курсовая работа по теме Болота та необхідність їх збереження
Реферат по теме Возникновение греческой культуры и ее периодизация, культура греческого полиса
Практическая Работа На Тему Экстремизм В Молодежной Среде
Сочинение Рассуждение На Тему День Рождения
Образ Вітовта В Пахвале Князю Сочинение
Реферат по теме Духовные и конструктивные основы византийской певческой системы
Характеристики Человеческого Голоса Реферат
Курсовая работа: Значення правосвідомості в сучастному середовищи
Шпаргалка: Бухгалтерский учет в торговле и строительстве
Контрольная работа по теме Сітьовий метод планування науково-дослідної роботи
Контрольная Работа По Теме Обмен Веществ
Сочинение По Рассказу Золотистый Золотой
Открой Курсовая Работа
Сочинение На Тему Дорогая Елена Сергеевна
Курсовая работа: Коррекционная работа направленная на исследование влияния самооценки старших подростков в учебной
Реферат: История развития товарных отношений
Диссертация Где Заказать
Expressive means and stylistic Devices - Иностранные языки и языкознание дипломная работа
Присоединение финансовых организаций - Государство и право реферат
Грамматика русского языка - Иностранные языки и языкознание контрольная работа