Содержание к диссертации
Введение
1. Основные понятия 16
1.1. Булевы функции, конечные автоматы, логические схемы 16
1.2. Программируемые логические элементы 18
1.3. Методы тестового и функционального диагностирования 22
1.4. Обзор методов проектирования дискретных систем 24
1.4.1. Методы проектирования самопроверяемых схем 24
1.4.2. Обзор методов проектирования детекторов кодов 27
1.5. Выводы по главе 35
2. Проектирование самопрорверяемых схем 36
2.1. Однонаправленные неисправности самопроверяемой синхронной последовательностной схемы 36
2.2. Получение интервального описания 38
2.3. Монотонные и частично-монотонные системы 41
2.4. ПЛБ реализация синхронной последовательностной схемы, представленной системой BDD - графов 42
2.5. Однонаправленное проявление неисправностей класса WB комбинационной схеме 55
2.6 Результаты экспериментов 60
2.7. Выводы по главе 60
3. Проектированрее самотестируемого детектора (m,n)- кодов 62
3.1. Метод разложения множества кодовых слов (т,п) - кода 63
3.2. Реализация самотестируемого детектора кодовых слов (т,п) - кода для 70
3.3. Обоснование самотестируемости схемы С 78
3.4. Реализация (1,п)-детекторов 86
3.5. Результаты сравнения с другими известными реализациями детекторов
(т,п) -кодов 90
3.6. Выводы по главе 90
4. Оценка сложности детектора 92
4.1. Подсчет числа ПЛБ 92
4.2. Неупорядоченные коды 101
4.2.1. Построение детекторов неупорядоченных кодов 102
4.2.2. Обсуждение свойства самотестируемости детектора 103
4.3. Сокращение дерева формулы А 104
4.4. Выводы по главе 105
Заключение 106
Список литературы 108
- Программируемые логические элементы
- Получение интервального описания
- Метод разложения множества кодовых слов (т,п) - кода
- Подсчет числа ПЛБ
Введение к работе
Актуальность проблемы.
Увеличивающаяся сложность и значимость дискретных (цифровых) систем требуют их высокой надежности. Сложность систем повышает вероятность возникновения неисправностей в них. С ростом уровня интеграции схем возрастает доля кратковременных и перемежающихся неисправностей по отношению к неисправностям, не меняющимся во времени. Обнаружение неисправности в первый же момент ее проявления на выходах устройства позволяет защитить систему, в которую устройство встроено, как от не меняющихся во времени неисправностей, так и перемежающихся и кратковременных. Такое обнаружение неисправности может достигаться, например, за счет использования самопроверяемых схем, позволяющих обнаруживать неисправности в режиме нормального функционирования схемы. Обнаружение осуществляется с помощью детектора кодов, который обычно является самотестируемым. Самопроверяемая схема вместе с таким детектором кодов образует полностью самопроверяемую дискретную систему.
Проектирование дискретных устройств, их производство и тестирование требуют все больших временных затрат. Подталкиваемые конкуренцией разработчики вынуждены искать пути для их сокращения. Один из способов решения данной проблемы - использование новой элементной базы, в частности, программируемых элементов и программируемых связей между элементами. Для новой элементной базы необходимы новые методы синтеза схем, учитывающие ее специфику.
Разработка методов проектирования самопроверяемых дискретных систем, ориентированных на использование новой элементной базы является, безусловно, актуальной.
Целью настоящей работы является разработка методов проектирования полностью самопроверяемых дискретных систем, ориентированных на использование программируемых логических блоков (ПЛБ). Для ее достижения решены две задачи.
1. Выполнено исследование известного метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства на возможность его применения к синтезу комбинационной составляющей самопроверяемого синхронного последовательностного устройства. Метод основан на покрытии системы BDD-графов, представляющей функции переходов-выходов синтезируемого синхронного автомата, программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирование неупорядоченными кодами (в частности, равновесными) символов выходного алфавита и состояний автомата и наблюдения выходов синхронного самопроверяемого устройства и его линий обратных связей.
2. Разработан метод синтеза самотестируемых комбинационных детекторов равновесных кодов.
Поставленные задачи решаются в предположении, что каждый ПЛБ реализует либо одну (любую) булеву функцию от к+\ переменной, либо две (любые) булевы функции от к переменных.
Методы исследования. В работе используется методы дискретной математики, в частности, алгебры логики, теории автоматов и теории графов.
Научную новизну полученных в работе результатов определяют:
- Обоснование возможности применения метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства к синтезу комбинационной с» • (V составляющей самопроверяемого синхронного последовательного устройства. Речь идет о методе, основанном на покрытии системы BDD-графов, представляющей функции переходов-выходов автомата, программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирования символов выходного алфавита автомата и его состояний неупорядоченными кодами (например, равновесными) и наблюдения выходов самопроверяемого устройства и его линий обратных связей.
- Декомпозиционный метод проектирования самотестируемых комбинационных детекторов равновесных кодов в базисе ПЛБ. Детектор кодов является самотестируемым относительно кратных константных неисправностей на полюсах ПЛБ. Проблема синтеза самотестируемых детекторов в базисе ПЛБ исследуется впервые.
- Алгоритмы сокращения числа допустимых кодовых слов на входах самотестируемых детекторов.
- Формула оценки сложности детектора кодов, то есть числа ПЛБ, необходимых для реализации детектора.
Достоверность полученных результатов. Все научные положения и выводы, содержащиеся в диссертации, доказаны с использованием аппарата дискретной математики. Эффективность предложенных методов синтеза подтверждена компьютерными экспериментами и теоретическими расчетами.
Практическая значимость работы.
Предложенные в работе методы синтеза самопроверяемых комбинационных схем и самотестируемых комбинационных детекторов равновесных кодов могут быть применены на этапе логического проектирования дискретных устройств. Синтезированные этим методом устройства являются полностью самопроверяемыми в классе одиночных Ч константных неисправностей на входах и выходах, а так же одиночных функциональных неисправностей ПЛБ для проверяемого устройства и в классе кратных константных неисправностей на полюсах ПЛБ для детектора кодов. Данное множество неисправностей является довольно широким и покрывает большую часть реально возникающих неисправностей.
Разработанные методы синтеза самопроверяемых устройств ориентированы на реализацию в базисе программируемых элементов, в частности ПЛБ Xilinx 3000. Проектирование может также быть выполнено в базисе ПЛБ любых производителей, удовлетворяющих описанным ниже требованиям, предъявляемым к ПЛБ.
Полученная формула подсчета числа ПЛБ позволяет оценить сложность детектора до проектирования устройства и, следовательно, выяснить целесообразность такого проектирования.
Реализация полученных результатов.
Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.
1. Госбюджетная тема Сибирского физико-технического института при ТГУ, программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".
2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95 1 21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".
3. Научный проект Минобразования России «Решение логических уравнений на BDD-графах в задачах диагностики».
Результаты работы также используются в курсе лекций "Диагностика дискретных устройств" на факультете прикладной математики и кибернетики Томского государственного университета (ТГУ).
Апробация работы и публикации.
Научные результаты, составляющие основу данной работы, по мере их получения обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования, кафедры защиты информации факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ.
Результаты работы представлялись на следующих научных конференциях:
1. Третья всероссийская конференция с международным участием «Новые информационные технологии в исследовании дискретных структур» (Россия, Томск 2000);
2. The Fourth International Conference on Computer-added Design of Discrete Devices (CAD DD 2001) (Minsk, Republic of Belarus, November 14-16,2001);
3. Международная конференция «Компьютерные науки и информационные технологии» (Россия, Саратов 14-18 мая 2002г.).
4. 7th IEEE International On-Line Testing Workshop (Taormina, Italy, July 9-11,2001);
5. 9th IEEE International On-Line Testing Workshop, Greece, Kos, July 7-9, 2003.
По результатам выполненных исследований опубликовано 7 печатных работ.
Структура и объем диссертации
Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 33 рисунка и 14 таблиц. Объем диссертации составляет 115 стр., в том числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 104 стр., библиография из 90 наименования - 8 стр.
Краткое содержание работы.
Во введении дается обоснование актуальности работы, изложены цель, научная новизна и практическая ценность работы.
Первая глава содержит основные определения, используемые в дальнейшей работе - определения булевых функций, конечных автоматов, логических схем и элементов логических схем.
Описываются принципы FPGA технологии. Эта технология является довольно новой и активно развивается в настоящее время, в то время как методы синтеза дискретных устройств в рамках этой технологии недостаточно развиты. Основу FPGA технологии составляют конфигурируемые логические блоки - CLB (Configurable Logic Block). CLB - это конфигурация логических элементов, которые могут быть программируемы пользователем. Существуют реализации CLB (в частности Xilinx 3000), где каждый CLB может выполнять одну или две (любые) булевы функции от заданного числа переменных. Если CLB реализует две функции, то эти функции должны зависеть от одних и тех же переменных.
Поскольку исследования не ориентированы на конкретную реализацию FPGA технологии, в работе используется понятие программируемого логического блока (ПЛБ). Каждый ПЛБ имеет к +1 вход и один выход или к входов и два выхода. Если ПЛБ имеет один выход, то на этом выходе может быть реализована одна (любая) булева функция, зависящая от к + \ переменных. В случае, если ПЛБ имеет два выхода, то он может реализовать любые две булевы функции, каждая из которых зависит от одних и тех же к входных переменных.
В первой главе также дается обзор методов тестового и функционального диагностирования. Использование самопроверяемых схем относят к методам функционального диагностирования.
Если при появлении неисправности из некоторого класса неисправностей в процессе нормального функционирования схемы (в рабочей области функционирования) данная неисправность либо обнаружится на выходах схемы в момент ее первого проявления, либо никак не влияет на функционирование схемы (остается необнаружимой в рабочей области функционирования), то такую схему будем называть самопроверяемой относительно рассматриваемого класса неисправностей. Если же в рабочей области функционирования детектора кодов неисправность из рассматриваемого класса обязательно проявится на выходах схемы, то такой детектор кодов будем называть самотестируемым.
В первой главе проводится обзор известных методов проектирования самопроверяемых дискретных устройств и самотестируемых детекторов кодов.
Во второй главе рассматривается метод синтеза самопроверяемой синхронной последовательностнои схемы. Метод основан на описании функционирования схемы BDD-графами и последующем покрытии этого описания программируемыми логическими блоками (ПЛБ). Программируемые логические блоки имеют один выход и к входов.
Вводится понятие BDD-графа, приводится алгоритм построения BDD-графа для булевой функции, обсуждаются основные свойства графов.
Одной из важнейших операций манипулирования BDD-графами является сокращение графа. Граф может быть сокращен без изменения представляемой им функции путем удаления лишних вершин и совпадающих подграфов с целью получения его канонической формы при выбранном порядке разложения по переменным.
На первом этапе выполняется кодирование выходов и состояний самопроверяемого синхронного автомата кодовыми словами равновесного кода.
Имея интервальное описание системы булевых функций переходов-выходов автомата, получаем представление комбинационной схемы автомата в виде системы BDD-графов.
Предложен алгоритм покрытия системы BDD-графов программируемыми логическими блоками (ПЛБ). Рассмотрен следующий класс неисправностей W: одиночные константные неисправности на входных полюсах синхронной последовательностной схемы, одиночные константные неисправности на ее выходных полюсах и линиях обратных связей и одиночные функциональные неисправности функций, реализуемых ПЛБ. На выходе ПЛБ в случае возникновения функциональной неисправности может быть реализована любая другая функция того же множества переменных (только один ПЛБ может быть неисправен). В синхронной последовательностной схеме возможна единственная неисправность из W.
Доказывается, что любая неисправность w,weW, является однонаправленной (и выходы, и линии обратных связей являются наблюдаемыми).
Неисправность называется однонаправленной, если ее проявление на наблюдаемых выходах приводит к замене значений некоторых переменных только с «О» на «1» или с «1» на «О», но не в обоих направлениях одновременно. Обеспечение этого свойства для всех неисправностей рассматриваемого класса делает синхронную последовательную схему самопроверяемой.
В заключение главы приводятся результаты компьютерных экспериментов.
В третьей главе предлагается метод проектирования самотестируемого детектора равновесных кодов (или (т,я)-кодов), ориентированный на использование программируемых логических блоков (ПЛБ). Любое кодовое слово (т,я)-кода содержит т единичных компонент и п-т нулевых.
Рассматривается множество неисправностей детектора V, которое включает в себя все кратные неисправности на входах и выходах ПЛБ. Только один ПЛБ в детекторе может быть неисправен, в неисправном ПЛБ кратная неисправность присутствует либо на входах, либо на выходах.
К детектору предъявляются следующие требования.
При появлении в момент времени t на выходе схемы некодового слова, детектор в тот же момент t выдает сигнал, свидетельствующий о неисправности схемы, к выходам которой он подключен. В самом детекторе может произойти неисправность из рассматриваемого множества неисправностей V, которая должна быть обнаружима в рабочей области функционирования детектора. Это значит, что на выходах самопроверяемой исправной схемы должно существовать кодовое слово (ти, л)-кода, на котором эта неисправность проявляется.
Возможна либо неисправность самопроверяемой схемы, либо самотестируемого детектора.
Самотестируемый детектор имеет два выхода. Комбинации значений сигналов:
a) (01) или (10) означают, что выходной набор самопроверяемой схемы является кодовым словом и детектор кодов исправен;
b) (00) или (11) означают, что либо выходной набор самопроверяемой схемы не является кодовым словом, либо детектор неисправен.
Доказывается теорема:
D:(X) = D0k(Xl)D (r)vDl(Xl)D:;l(r)vD2k(X )D::k\r)v...v УІ);(І!Й4(Ґ)
Здесь D™(X) — дизъюнкция конъюнкций, представляющих всевозможные кодовые слова (т,п)- кода. Если п-к к, то выполним • следующий шаг данного разложения для каждой DJn_k(X ), и так далее. Полученное разложение обозначается формулой Л.
Все кодовые слова (т,и)-кода разделяются на два подмножества, и формула А представляется следующим образом: A = A vA2. Здесь А1 реализует кодовые слова первого подмножества, А2 — оставшиеся кодовые слова (т,п)-кода. А1 и А2 соответствуют двум выходам детектора.
Предложен алгоритм покрытия схемы ПЛБ. При разработке данного алгоритма учтена специфика ПЛБ, а именно возможность реализации ПЛБ любой булевой функции от заданного числа переменных, а также возможность реализации двух функций одним ПЛБ.
Доказано, что детектор является самотестируемым относительно множества неисправностей К
Предложена специальная реализация (1,«)-детекторов. Доказано, что построенные детекторы являются самотестируемыми относительно • множества неисправностей V.
В заключение главы 3 приведены результаты сравнения с другими известными реализациями детекторов равновесных кодов.
В четвертой главе предлагаются оценки сложности детекторов, описанных в главе 3. Выведены формулы для подсчета числа ПЛБ, необходимых для реализации самотестируемого детектора при следующих предположениях относительно параметров детектора:
a) рассматривается детектор (2п,п)-кодов;
b) число входов ПЛБ равно к, и п делится иг. к, пА \.
Полученные формулы позволяют подсчитать число ПЛБ при различных . значениях к, и п для четного или нечетного числа входов ПЛБ.
п-к + 2 п п + 2к + 2 fn_ \к j
2 к 2
п — к + 2 п п + 2к + 2 (п
к
N =3
1 у чет • N... =3
•
Из формул следует, что сложность детектора растет пропорционально квадрату длины его кодовых слов (квадрату п). Эти формулы могут служить оценкой сложности детекторов (т, п) -кодов в широком диапазоне значений тип.
Обычно свойства самотестируемости детектора доказываются в предположении, что все кодовые слова некоторого равновесного кода достигаются на его входах. Множество этих кодовых слов будем называть допустимым на входах детектора. На практике это не всегда возможно: число кодовых слов на выходах самопроверяемой схемы меньше числа всевозможных кодовых слов равновесного кода. В этом случае желательно обеспечение свойства самотестируемости на подмножестве кодовых слов, близком к подмножеству кодовых слов, достижимых на выходах самопроверяемой схемы. Чем ближе два подмножества, тем больше вероятность того, что неисправность из рассматриваемого класса будет обнаружена.
Один из способов решения этой проблемы - построение детекторов неупорядоченных кодов на основе детекторов различных (т,п) -кодов. Код называется неупорядоченным, если любые два его кодовых слова не сравнимы.
Доказано, что при использовании неупорядоченного кода специального вида детектор кода остается самотестируемым при сокращении числа допустимых кодовых слов по сравнению с подходящим детектором (т,п)-кодов. При этом число ПЛБ, необходимых для реализации детектора неупорядоченных кодов, не увеличивается.
Второй подход заключается в сокращении числа кодовых слов (т,п)-кода, достижимых на входе детектора путем исключения в формуле А подформул. Самотестируемость детектора в классе рассматриваемых неисправностей сохраняется.
Основные положения, выдвигаемые на защиту.
1. Обоснование возможности применения метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства к синтезу комбинационной составляющей самопроверяемого синхронного последовательностного устройства. Речь идет о методе покрытия программируемыми логическими блоками (ПЛБ) системы BDD-графов, представляющей функции переходов-выходов автомата. Состояния и символы выходного алфавита синхронного автомата кодируются при синтезе самопроверяемого устройства неупорядоченными кодами. Наблюдаются выходы и линии обратных связей устройства. Допускаются функциональные неисправности ПЛБ и одиночные константные неисправности на полюсах триггеров и входных полюсах.
2. Метод проектирования самотестируемых комбинационных детекторов равновесных кодов, ориентированный на использование ПЛБ. Допускаются кратные неисправности на полюсах одного ПЛБ. Проблема синтеза детекторов такого типа рассмотрена впервые.
3. Формула подсчета числа ПЛБ, необходимых для реализации детектора равновесных кодов.
4. Алгоритмы сокращения числа допустимых кодовых слов, поступающих на вход детектора, при сохранении свойств самотестируемости детектора.
Программируемые логические элементы
Специализированные БИС, в свою очередь, делятся на три класса: заказные, полузаказные и программируемые.
Разработка полностью заказных БИС включает все циклы проектирования, что влечет за собой значительное удорожание изделия. Затраты на разработку и изготовление оправданы только при относительно больших объемах производства - не менее 150-750 тыс. шт. в год. Стоимость разработки - до $100000 в течение 8-10 месяцев [2]. Полностью заказные БИС позволяют достичь наибольшей производительности и наибольшей экономии места на кристалле.
Полузаказные БИС производятся массовыми тиражами на основе базовых матричных кристаллов (Standart Cells and Gate Arrays). Данная технология экономически оправдана только в сочетании с системами автотматизированного проектирования (САПР), содержащих систему моделирования высокой адекватности, с помощью которой можно было бы решить все проблемы работоспособности готового изделия до того, как результат проектирования будет передан на технологическую линию. Затраты на разработку и изготовление оправданы при объеме производства от 1000 до 30000 корпусов в год.
Для минимизации времени, необходимого на проектирование и производство схем используются программируемые пользователем БИС, которые обладают наибольшей гибкостью использования и оперативностью Компоненты такого аппаратного оборудования (логические блоки и связи) находятся на уже произведенном чипе и могут быть запрограммированы, чтобы реализовать любой вид цифровой схемы.
В последние годы большое развитие получила FPGA (Field of Programmable Gate Array) технология. Существует несколько FPGA архитектур - Xilinx, AT&T, Actel, и т.д. [6-9]. Хотя эти архитектуры и представлены различными производителями и имеют различные характеристики, тем не менее все они представляют собой матрицы идентичных логических блоков. Логические блоки - это гибкая конфигурация логических элементов, которые могут быть программируемы пользователем. Поэтому такие логические блоки называются программируемыми логическими блоками. В дальнейшем для их обозначения будем пользоваться английской аббревиатурой — CLB (Configurable Logic Block).
Архитектура CLB, в частности, может быть основана на таблицах соответствия - LUT (Look-Up Table). LUT может реализовать любую булеву функцию, зависящую от определенного числа входных переменных — т (га 2), где т - фиксированное число. В коммерческих архитектурах m обычно находится в интервале от 3 до 9. На рисунке 1.2 изображен га-входной LUT, в дальнейшем будем обозначать m-LUT. m-LUT обычно реализуется статическим ОЗУ (SRAM), который имеет т адресных линий и 1 линию передачи данных.
Следующий пример показывает, как с помощью m-LUT реализовать любую булеву функцию, зависящую от m входных переменных (Рис. 1.3). Пусть т=Ъ, /{хх,х2,хг) = ххх2хг vххх2х3 vх,х2х3. Рассмотрим SRAM, имеющий три адресных линии. Адресные линии сопоставляются переменным хх,х2,х3, а выходная линия передачи данных сопоставляется функции /. Если/ принимает значение 1 на наборе д:, =0,д:2 =0,д:3 =0, то по адресу 2 3 хранится значение 1. Для других наборов значение переменных единицы хранятся аналогично. Таким образом, линия данных SRAM задает значение / в соответствии с входной комбинацией, представленной на линиях адреса. В коммерческих архитектурах, основанных на LUT, каждый CLB может содержать один или более LUT. Мы будем рассматривать CLB, содержащие один или два LUT. Таким образом, каждый CLB реализует одну или две любые булевы функции от заданного числа переменных. Основными неисправностями, имеющими место в CLB такого типа являются одиночные и кратные функциональные неисправности. Под одиночной функциональной неисправностью понимается неисправность одного LUT, такая, что сопоставляемая исправному LUT функция может быть в случае неисправности заменена на любую функцию того же множества переменных. В случае кратной неисправности допускается неисправность нескольких LUT, в том числе и относящихся к различным CLB. Функциональные неисправности представляют широкое множество неисправностей, покрывающее большинство реально возникающих неисправностей. Существуют FPGA-технологии, где CLB основаны не на LUT. Например, в серии Xilinx ХС5200 элементы памяти не используются, и здесь уже можно говорить об одиночных и кратных неисправностях на входных и выходных полюсах CLB.
Получение интервального описания
BDD-графом булевой функции называется ориентированный граф с корнем, имеющий множество вершин V. Vсодержит два типа вершин: нетерминальные и терминальные. Нетерминальная вершина v, veV, имеет в качестве атрибутов индекс аргумента indexiy) є {1,...,я} и две дочерние вершины high(v),low(y) є V. Терминальная вершина v имеет один атрибут - value(y) є {0,1}. Для любой нетерминальной вершины v, если low(y) также является нетерминальной, необходимо выполнение условия indexiy) index{low(v)). Аналогично, если high(y) - нетерминальная вершина, то должно выполняться 9 условие: indexiy) index(high(v)). Из этого условия следует ацикличность BDD-графа, так как индексы дочерних вершин каждой нетерминальной вершины строго больше индекса этой вершины. Функция fv, соответствующая вершине v BDD - графа, определяется рекурсивно следующим образом: 1. Если v является терминальной вершиной, и a. value(y) = 1, то fv = 1, b. value(v) = 0, то /v = 0. 2. Если v - нетерминальная вершина с индексом indexiy) = і, то fv является функцией следующего вида: Из определения BDD — графа следует, что пути в графе, который начинается от корня и продолжается вплоть до концевой вершины, соответствует интервал, представленный троичным вектором, так что если некоторая вершина v пути имеет indexiy) = /, и путь продолжается к вершине low{v), то xt = 0, к вершине - high(v), то х, = 1. Здесь xt - компонента представляющего интервал троичного вектора. Значение функции на интервале равно значению терминальной вершины в конце пути. Построение BDD-графа Пусть задана булева функция f(xx,...xn), для которой необходимо построить BDD-граф. Необходимо заранее выбрать порядок разложения функции по переменным. После выбора порядка переменных: xt ,хІ2,...,хіп начинается построение графа. 1. Создается нетерминальная вершина с номером х, . 2. Для нее строятся дочерние вершины low{xt ) и highix ). Для этого выполняется замена переменной xt в булевой функции константой О для левого поддерева (low) и константой 1 для правого поддерева ( high ). 3. Если булева функция в результате подстановки обращается в константу, то в качестве дочерней вершины добавляется терминальная вершина, значение которой равно значению функции. 4. Если булева функция после подстановки в константу не обращается, то в качестве дочерней для очередной вершины добавляется нетерминальная вершина с ближайшем к упорядоченном ряду номером переменной, например, Xj , от которой зависит функция после подстановки в нее константы вместо х, . Для новой нетерминальной вершины выполняется достраивание дочерних вершин, как указано выше, заменой переменной ,. на константу 0 или 1. Построение завершается, когда все концевые вершины графа являются терминальными. При построении BDD-графа порядок разложения по переменным (в каждой внутренней вершине графа имеет место разложение Шеннона по переменной, отмечающей вершину) существенно влияет на размеры получающегося графа. Ниже приводятся графы, иллюстрирующие этот факт. На рисунке 2.3 изображены два BDD-графа для одной и той же функции, при построении которых были выбраны различные порядки разложения функции по переменным. Известны различные методы выбора порядка разложения по переменным, в частности, использующие представление функции в виде ДНФ, в виде произвольных формул над множеством {-!,A,V} функций и др..
Метод разложения множества кодовых слов (т,п) - кода
Рассмотрено множество W неисправностей, которое включает в себя одиночные константные неисправности на входных полюсах синхронной последовательностной схемы, одиночные константные неисправности на ее выходных линиях и линиях обратных связей и одиночные функциональные неисправности ПЛБ. Доказано, что предлагаемое в этой главе покрытие системы BDD - графов, представляющее функции переходов-выходов синхронной схемы, состояния и выходы которой закодированы неупорядоченными кодами (в частности равновесными), обеспечивает однонаправленное проявление неисправностей из рассматриваемого множества, то есть доказана самопроверяемость синхронной последовательностной схемы относительно множества W неисправностей в условиях наблюдения ее выходов и линий обратных связей. 2. Предлагаемый подход к покрытию системы BDD-графов программируемыми логическими блоками (ПЛБ) допускает различные модификации, ориентированные на оптимизацию структуры синхронной последовательностной схемы. Доказано, что любое покрытие ПЛБ BDD-графа сохраняет свойства однонаправленного проявления неисправностей множества W.
Во второй главе был предложен метод проектирования комбинационной части самопроверяемого конечного автомата. В случае исправного функционирования схемы на выходе реализуются кодовые слова некоторого неупорядоченного кода, например равновесного. В данной главе предлагается метод проектирования самотестируемого детектора (т,п)-кодов, основанный на использовании программируемых логических блоков (ПЛБ) [85,87-90].
Рассматривается множество неисправностей детектора V, которое включает в себя все кратные неисправности на входах и выходах ПЛБ. Только один ПЛБ в детекторе может быть неисправен, в неисправном ПЛБ кратная неисправность присутствует либо на входах, либо на выходах.
К детектору предъявляются следующие требования. Во-первых, при появлении на выходе схемы (или на входе детектора) некодового набора, он должен немедленно выдать соответствующий сигнал. Во-вторых, в самом детекторе может произойти неисправность из рассматриваемого множества неисправностей V, которая должна быть обнаружима в рабочей области функционирования детектора, т.е. на выходах исправной схемы должен существовать кодовый набор (кодовое слово (т, п) -кода), на котором эта неисправность проявится на выходах детектора.
Самотестируемый детектор имеет два выхода. Комбинации значений сигналов: a) (01) или (10) означают, что входной набор является кодовым (является (т#,я)-кодом) и детектор кодов исправен; b) (00) или (11) означают, что входной набор не является кодовым или детектор неисправен. Именно такие детекторы будут рассмотрены в данной главе. Пусть М - множество кодовых слов (/я,и)-кода, Fv - система двух булевых функций, реализуемых детектором в присутствии неисправности из рассматриваемого множества неисправностей V. Тогда для всякой неисправности v,veV существует тестовый набор а,аеМ такой, что неисправность монотонно проявляет себя на выходах детектора, т.е. либо F(a) Fv(а), либо F\a) F(a). Заметим, что число всевозможных кодовых слов (т,п)- кода равно С, то есть числу сочетаний из п по т. Кодовые слова могут быть представлены дизъюнкцией конъюнкций ранга п. Обозначим эту дизъюнкцию Dnm (X), где X = {xv...,xn} - множество переменных. Уже при « = 10, АИ = 5 Df0(X) состоит из 252 конъюнкций ранга 10 и содержит 2520 букв. Это выражение не может быть сокращено в результате минимизации ДНФ, ДНФ D„(X) является совершенной и сокращенной одновременно, поскольку любые две конъюнкции из Dnm{X) ортогональны по крайней мере по двум переменным. Для представления всевозможных («?,и)-кодов предложена специальная формула разложения А. Формула включает скобки, символы л, v и ДНФ Dp(Xr). Функция разложения Dqp{Xr) - это дизъюнкция конъюнкций, соответствующих всем (q, р) -кодам, р к, q p, ГсІ, X - {хх,...,хп}. В частности, к может быть равно числу входов двухвыходного ПЛБ. Каждый ПЛБ либо реализует одну произвольную булеву функцию от к + \ переменных, либо две произвольные булевы функции от к переменных, и Dqp - функция, сопоставляемая одному из выходов ПЛБ.
Подсчет числа ПЛБ
В данной работе, учитывая специфику программируемых элементов, удалось добиться упрощения схем, алгоритмов их построения и расширения множества неисправностей при проектировании самопроверяемых дискретных систем, в частности, синхронных последовательностных схем и детекторов кодов, подключенных к их выходам.
Известные методы проектирования таких систем ориентированы прежде всего на вентильную реализацию, хотя и могут быть перенесены на ПЛБ. Эти методы не учитывают специфику программируемых элементов, а именно возможность одним блоком реализовать одну или две любые булевы функции от фиксированного числа переменных. Использование таких свойств позволило бы сократить как сложность схем (число элементов, необходимых для реализации), так и алгоритмы проектирования.
Предложен подход к синтезу самопроверяемых синхронных последовательных схем, основанный на покрытии системы BDD-графов программируемыми логическими блоками (ПЛБ). Данный подход допускает различные модификации, ориентированные на оптимизацию структуры синхронной последовательностной схемы. Множество неисправностей W, включает в себя одиночные константные неисправности на входных полюсах синхронной последовательностной схемы, одиночные константные неисправности на ее выходных линиях и линиях обратных связей и одиночные функциональные неисправности ПЛБ. Доказано, что покрытие системы BDD - графов, представляющее функции переходов-выходов синхронной схемы, состояния и выходы которой закодированы неупорядоченными кодами (в частности равновесными), обеспечивает однонаправленное проявление неисправностей из рассматриваемого множества, то есть доказана самопроверяемость синхронной последовательностной схемы относительно множества неисправностей W в условиях наблюдения ее выходов и линий обратных связей.
Предложен метод проектирования универсального самотестируемого детектора (ш,и)-кодов, ориентированный на реализацию из программируемых логических элементов. Самотестируемость обеспечивается для множества неисправностей V, которое включает в себя кратные константные неисправности на входах и выходах ПЛБ. Доказано, что полученный детектор является самотестируемым относительно данного множества неисправностей. Множество V представляет широкий класс реальных неисправностей. Несмотря на то, что полученный детектор является универсальным, то есть не ориентированным на какой-либо конкретный равновесный код, его реализация в рамках FPGA-технологии довольно компактна. Предложен метод подсчета числа ПЛБ, необходимых для реализации самотестируемого детектора (т,и)-кодов. Получены формулы для подсчета числа ПЛБ для некоторых частных случаев детекторов. Формулы позволяют оценить сложность самотестируемых детекторов для произвольных (т,п)-кодов. Установлено, что сложность детекторов, реализуемых предложенным в работе декомпозиционным методом, растет пропорционально квадрату длины п (т,я)-кода. Предложены алгоритмы сокращения числа допустимых кодовых слов, поступающих на вход детектора, при сохранении свойств самотестируемости детектора. Один из алгоритмов основан на композиции различных (т,п)-кодов, другой - на исключении подмножеств кодовых слов выбранного (т,и)-кода.
