Диагностика автоматных сетей и недетерминированных автоматов
Проводимости цепей и состояния узлов в схеме принимают значения в полурешетках проводимостей и состояний соответственно. Первая представляет собой полурешетку подмножеств множества из трех элементов, обозначающих проводимости разомкнутой, замкнутой и резистивной электрических цепей, а вторая - полурешетку подмножеств декартовой степени первой, где показатель степени совпадает с числом различных полюсов питания схемы. Элементом полурешетки (проводимостей или состояний), являющимся одноэлементным подмножеством, моделируется статическое значение (соответственно проводимости цепи или состояния узла), а элементом, являющимся подмножеством большей мощности, - динамическое значение соответствующей величины.
Проводимости в наборе, представляющем состояние некоторого узла, - это проводимости схемы от полюсов ее питания до данного узла. Так представляются, в частности, такие статические состояния узлов, как высокий импеданс, комплементарные, низко-, средне- и высокоимпедансные логические нуль и единица и их любые динамические сочетания (всего для схемы с двумя полюсами питания - 511 значений).
Подчеркнем, что, в отличие от общепринятых подходов к моделированию интегральных схем на транзисторном уровне абстракции (Дж.М. Хейес, R.E.
Bryant, F.J. Ramming и др.), в нашей модели статические состояния узла схемы не постулируются изначально как нечто данное извне и моделирующее значение и силу сигнала в узле, но представляются тем, чем последние в сущности и определяются, - наборами проводимостей схемы от полюсов источника питания до этого узла, а любая компонента схемы (диод, транзистор, резистор, логический вентиль и т.п.) представляется изначально не как элемент для преобразования сигналов - функциональный элемент, но в соответствии с ее физической природой как элемент с управляемыми проводимостями - переключательный элемент, вследствие чего моделирование схемы сводится к вычислению не значения и силы сигнала в ее узле, но именно проводимостей схемы до узла от полюсов источника питания, в том числе через входы схемы. Этим достигается одновременно и однородность модели, обеспечивающая единообразие в моделировании схем из разнородных компонент - транзисторов, резисторов, ключей, вентилей и др., и ее адекватность схемам, выполненным по самым разным технологиям, чего не скажешь про другие модели.
Вычисление проводимостей и состояний в модели осуществляется средствами полурешеточно упорядоченных алгебр проводимостей и состояний.
Определяется понятие динамического поведения интегральной схемы как совокупность динамических переходов в ней, где каждый такой переход указывает границы, в которых находятся выходное и внутреннее состояния схемы во время и по завершению переходного процесса, вызванного асинхронным изменением входного состояния с одного на другое при заданном начальном внутреннем состоянии. В этом определении существенную роль играет операция сложения в полурешетке состояний, моделирующая асинхронное изменение состояния как промежуточное (переходное) состояние.
Вводятся элементарные операции над проводимостями и состояниями. Первые моделируют последовательное, параллельное и мостиковое соединения электрических цепей, а вторые - узловое соединение цепей и передачу состояния по цепи с заданной проводимостью. Вместе со сложением в по-лурешетке состояний этих операций достаточно, чтобы адекватно моделировать структуру и динамическое поведение любой интегральной схемы независимо от ее элементной базы и технологии производства.
Более того, задаваясь той или иной конгруэнцией на полурешетке состояний, можно моделировать схему адекватно с любой наперед заданной точностью.
В рамках данной модели поставлены и решены основные задачи проектирования асинхронных интегральных схем, не доступные в рамках других теорий: задача анализа - узнать динамическое поведение заданной схемы с заданной точностью; задача синтеза - построить схему, обладающую заданным динамическим поведением. Последнее задается системой команд, где каждая команда в отличие от динамического перехода в схеме не ограничивает внутреннего состояния во время переходного процесса и задана на полурешетках, не обязанных быть полурешеткой состояний.
Задача синтеза заключается в построении такой схемы, что каждая заданная команда вкладывается в подходящий динамический переход в схеме.
В отличие от задач синтеза статических, или синхронных, схем (с поведением в статике, т.е. при фиксированных входных состояниях) задача синтеза схем с заданным динамическим поведением может не иметь решения, так как не любая система команд допускает реализацию интегральной схемой без синхронизации каналов передачи информации в ней. Сформулированы необходимые и достаточные условия, при которых такая реализация возможна.
Они сводятся к проверке по установленным конструктивным тестам условий квазимонотонности индуцируемых заданной системой команд бинарных отношений и возможности 3-значного кодирования полурешеток, на которых заданы команды системы. При выполнении этих условий возможно построение требуемой схемы на любой элементной базе - из транзисторов, логических вентилей, базовых ячеек и др.
Следует заметить, что первое печатное изложение полурешеточной модели интегральных схем появилось в 1982 г. в статье автора и его коллег [59]. Годом позже вышла монография тех же авторов [58], где, кроме этой самой модели, изложены и методы анализа и синтеза схем, описываемых ею. В монографии [52] эти результаты повторены, но в более строгом изложении, использующем алгебраический аппарат теории полурешеток и полурешеточно упорядоченных алгебр. В ней наряду с необходимым математическим обоснованием изложены методы анализа динамического поведения произвольных схем из переключательных элементов, абстрактного и структурного синтеза таких схем с заданным динамическим поведением и их адекватного моделирования с наперед заданной точностью.
Статья [61] является извлечением из [52] описания модели. В [64] сообщается о компьютерной программе, реализующей данную модель.
Диагностика автоматных сетей и недетерминированных автоматов
Под неисправностью в автоматной сети (а.с.) понимается замещение некоторой одной компоненты сети любым автоматом из некоторого заданного класса автоматов с теми же входным и выходным алфавитами, что и у замещаемой компоненты. Проверяющий тест для а.с. - это такой эксперимент с ее автоматом, который распознает этот автомат в классе автоматов всех сетей, получающихся из данной всевозможными неисправностями в ней.
Установлено, что кратчайший проверяющий тест для автоматной сети нельзя построить, как это пытаются делать другие авторы, как проверяющий тест для ее автомата или как тест, который для каждого перехода в компоненте контролирует один из содержащих его переходов в сети.
Недетерминированный (нд-) автомат отличается от (детерминированного, или д-) автомата тем, что в нем вместо функций переходов и выходов задается одна функция, которая каждой паре (входной символ, состояние) ставит в соответствие подмножество из декартова произведения выходного алфавита и множества состояний. Если в каждом значении функции нд-автомата оставить по одной паре (выходной символ, состояние), то получится д-автомат, который называется редукцией данного нд-автомата. Проверяющий тест для нд-авто-мата A относительно д-автомата B определяется как эксперимент для B, распознающий B в классе всех редукций автомата A. Показано, что для любой компоненты B автоматной сети N существует такой нд-автомат A, называемый сетевым эквивалентом B в N, что множество всех проверяющих тестов д ля N с неисправностями в
B совпадает с множеством всех проверяющих тестов для A относительно B. Тем самым синтез тестов для автоматных сетей сводится к синтезу тестов для недетерминированных автоматов, открывая новое направление для фундаментальных исследований [65-83].
Диагностика логических схем
Логическая схема - это частный случай автоматной сети. В ней в качестве компонент используются логические элементы, представляющие собой комбинационные автоматы, и элементы памяти -автоматы с двумя состояниями.
При наличии последних или обратных связей схема называется последовательностной, а в их отсутствие - комбинационной.
Для контроля логических схем с двухзначными сигналами предложены эффективные процедуры синтеза проверяющих тестов [84, 85, 87], использующие описание комбинационной части схемы в виде системы дизъюнктивных нормальных форм (днф). Развит также вероятностный метод тестирования таких схем [88, 89, 96, 97]. Его идея следующая: распределения вероятности выходных сигналов у исправной схемы и у схемы с неисправностью разные и по факту этого различия можно судить о наличии неисправности в схеме. Требуемое для этого распределение вероятности выходных сигналов строится по известному распределению вероятности входных сигналов и системе ортогональных днф (ОДНФ) булевых функций, извлекаемых из структуры схемы.
Предложены методы построения ОДНФ для частичных функций и их минимизации [128].
Разработан алгебраический аппарат для вычисления проверяемых неисправностей и проверяющих тестов для схем с многозначными сигналами [86, 95], в том числе из полурешеток проводимостей или состояний [58].
Логический синтез
Безусловно выдающимся достижением в логическом синтезе дискретных автоматов является декомпозиционный метод синтеза комбинационных схем, принадлежащий В. Л. Павлову и изложенный им первоначально в [98] для схем из логических элементов ИЛИ-НЕ. В его основе лежит известная операция декомпозиции (разложения) заданной частичной функции на менее определенные компоненты по функции применяемого элемента. Принципиальная особенность, сделавшая метод В. Л. Павлова наиболее эффективным среди всех существовавших в последние 30 лет декомпозиционных методов синтеза, заключается в том, что каждая компонента разложения в нем определяется не явно, но с точностью до областей ее возможных значений и границ для количества последних в них. Фактически это означает, что результатом декомпозиции одной функции по другой является не один какой-то вариант, а множество всех возможных наборов компонент разложения.
Все такие варианты, возникшие на некотором шаге процесса синтеза, сохраняются на всех последующих шагах и используются для получения более простой схемы. Отсечение лишних вариантов происходит лишь в самый последний момент, когда некоторая из компонент на каком-либо шаге синтеза доопределяется до одной из функций, реализуемых построенной частью схемы, или становится всюду определенной по причине полной определенности всех компонент ее собственного разложения. В этом случае другие компоненты несколько уточняются путем сужения их областей возможных значений и границ для числа последних.
В последующих исследованиях этот метод был развит для синтеза схем в произвольном базисе, в том числе свободных от состязаний [99, 104, 105], устойчивых к неисправностям [101] и на полурешет-ке подмножеств 3-элементного множества [58, 106].
Теорема декомпозиции, выясняющая условия сходимости декомпозиционного метода синтеза комбинационных схем, установлена в [100] (см. также [30, С. 180-184]).
В [102] показана возможность реализации любой системы булевых функций каскадным соединением однотипных настраиваемых элементов, осуществляющих отображение, сопоставленное некоторым образом нормальной периодической последовательности ря(2), или некоторое транспозиционное отображение. В обоих случаях даны оценки сверху для числа каскадов.
Среди других результатов в области логического синтеза следует отметить методы синтеза комбинационных и последовательностных схем со свойствами контролепригодности [103, 108, 110, 111, 115] и самопрверяемости [113, 114, 116-118]. Первое свойство гарантирует возможность эффективного построения проверяющего теста, а второе - возможность контроля правильности выходных сигналов схемы.
Разработан метод обеспечения отказоустойчивости процессорной матрицы (ПМ) СБИС, создающий возможность для применения в производстве прорывной неразрезной технологии [119124]. Отказоустойчивость ПМ обеспечивается путем программного назначения резервных строк и столбцов по всей площади матрицы без применения, в отличие от других методов, абсолютно надежных средств коммуникации. Требуемый уровень отказоустойчивости достигается отображением логической структуры устройства в исправную часть физического пространства ПМ.
Даны оценки эффективности некоторых алгоритмов отображения и их схемная реализация.
ЛИТЕРАТУРА
1. Закревский А.Д. Алгоритмы синтеза дискретных автоматов.
М.: Наука, 1971. 512 с. 2. Логический язык для представления алгоритмов синтеза релейных устройств / Под ред.
М.А. Гаврилова.
М.: Наука, 1966. 342 с. 3. Синтез асинхронных автоматов на ЭВМ / Под общ. ред. А.Д. Закревского.
Минск: Наука и техника, 1975. 184 с. 4. Автоматизированное проектирование цифровых устройств / Под ред. С.С. Бадулина.
М.: Радио и связь, 1981. 240 с. 5. Панкратова И.А., Быкова С.В., Николаева Л.А., Оранов А.М. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины.
1991. 1. С. 3-9. 6. Агибалов Г.П., Иволга В.П., Комаров Ю.М., Кутугина Е.С. Система логического моделирования схем во времени // Обмен опытом в радиопромышленности.
1983. Вып. 4. С. 13-16.
7. Быкова С.В. Система алгоритмов кратчайшего покрытия // Труды Сибирского физ.-техн. ин-та. Проблемы кибернетики.
Томск: Изд-во Том. ун-та, 1973. Вып.
64. С. 3-11.
8. Быкова С.В., Иволга В.П. Оценка эффективности некоторых алгоритмов минимального разбиения // Вычислительная техника в машиностроении. Минск: ИТК АН БССР, июнь 1974.
С. 79-86.
ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ МАТЕМАТИКИ
9. Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска и его применение в синтезе интегральных схем // Управляющие системы и машины. 1977. 6. С. 99-103.
10. Агибалов Г.П., Беляев ВА.
Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Том. ун-та, 1981.
125 с. 11. Агибалов Г.П. Об одном подходе к размещению аппаратуры // Автоматика и вычислительная техника, 1971. 1. С. 56-61.
12. Беляев ВА., Томашев В.Ф. Об одной комбинаторнологической задаче, связанной с оптимальным размещением аппаратуры по линейно-упорядоченным отсекам // Труды Сибирского физ.-тех. ин-та.
Проблемы кибернетики. Томск: Изд-во Том. ун-та, 1971. Вып.
62. С.49-57.
13. Агибалов Г.П., Беляев В.А., Оранов А.М. Некоторые
алгоритмы разбиения, покрытия и размещения логических схем // Управляющие системы и машины. 1974. 5. С. 86-92.
14. Агибалов Г.П., Беляев В.А., Янковская А.Е.
Алгоритм компоновки схем в модули ограниченной вместимости // Управляющие системы и машины. 1976. 1. С. 84-89.
15. Беляев В.А.
Усовершенствованный алгоритм минимального разбиения системы чисел // Прикладная математика и кибернетика. Томск: Изд-во Том. ун-та, 1976. Вып.
1. С. 17-22. 16.
Агибалов Г.П., Оранов АМ. Алгоритмы покрытия схем свободными модулями // Автоматика и вычислительная техника. 1977.
4. С.15-16. 17.
Агибалов Г.П., Оранов АМ. О покрытии схем модулями // Вопросы автоматизации проектирования интегральных схем.
Киев: ИК АН УССР, 1978. С. 46-57. 18.
Агибалов Г.П. Задача выбора и декомпозиция схем с размещением и трассировкой в компоновочном пространстве // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987.
Вып. 2. С. 134-153.
19. Беляев В.А. Алгоритм раскраски графа методом сокращенного обхода дерева поиска // Алгоритмы решения задач дискретной математики.
Томск: Изд-во Том. ун-та, 1987. Вып. 2. С. 165-172.
20. Агибалов Г.П., Оранов А.М. Покрытие логических схем модулями некоторых серийных систем // Кибернетика.
1986. 2. С. 34-38, 43. 21. Оранов АМ., Андреева Л.Н.
Алгоритм минимального разбиения системы множеств // Автоматика и вычислительная техника. 1992. 2. С. 37-44. 22.
Оранов А.М., Андреева Л.Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах // Автоматика и вычислительная техника. 1992. 5. С. 57-63.
23. Оранов А.М., Андреева Л.Н.
Алгоритм минимального разбиения некоторого набора объектов // Автоматика и вычислительная техника. 1993.
2. С. 27-35. 24.
Оранов АМ. К синтезу комбинационных схем в базисе ПЛИС // Автоматика и вычислительная техника.
1996. 1. С. 27-35. 25. Андреева Л.Н., Оранов АМ.
О сложности некоторых задач разбиения //Известия РАН. Теория и системы управления.
1997. 2. С. 114-116. 26.
Оранов АМ. Алгоритм построения кратчайших монотонно-допустимых разбиений конечных множеств // Автоматизация проектирования дискретных систем. Материалы 2-й Международной конференции. Т. 3. Минск: ИТК АН Беларуси, 1997.
С. 221-227. 27.
Андреева Л.Н., Оранов АМ. Оценки погрешности двух приближенных алгоритмов разбиения // Автоматизация проектирования дискретных систем. Материалы 2-й Международной конференции.
Т. 3. Минск: ИТК АН Беларуси, 1997. С. 228-231.
28. Андреева Л.Н., Оранов А.М. Оценки погрешности двух приближенных алгоритмов разбиения // Известия РАН. Теория и системы управления.
1999. 1. С. 89-93. 29. Оранов А.М.
Кратчайшие допустимые разбиения в синтезе и компоновке схем на современной элементной базе // The third international symposium Application of the conversion research results for international cooperation (Sibconvers'99). Proceedings. Tomsk: Tomsk state university of control systems and radioelectronics.
1999. C. 192194.
ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ
30. Агибалов Г.П., Оранов А.М. Лекции по теории конечных автоматов.
Томск: Изд-во Том. ун-та, 1984. 185 с. 31. Агибалов Г.П. Распознавание операторов, реализуемых в линейных автономных автоматах // Известия АН СССР.
Техническая кибернетика. 1970. 3. С. 99-108. 32.
Агибалов Г.П. Распознавание операторов, реализуемых в автономных автоматах // Конференция по теории автоматов и искусственному интеллекту: Аннотации докладов и программа.
М.: ВЦ АН СССР, 1968. 33.
Агибалов Г.П., Юфит Я.Г. О простых экспериментах для линейных инициальных автоматов // Автоматика и вычислительная техника. 1972. 2. С. 17-19.
34. Агибалов Г.П., Ванина Н. В. Точная верхняя оценка степени различимости произвольной нормальной периодической последовательности // Известия АН СССР.
Техническая кибернетика. 1973. 1. С. 131-136.
35. Агибалов Г.П., Ванина Н.В. О кодовых свойствах нормальных периодических последовательностей // V конференция по теории кодирования и передачи информации.
II Теория кодирования. Москва-Горький, 1972.
С. 5-6. 36.
Агибалов Г.П. Отождествление нормальных периодических последовательностей начальными отрезками // Труды Сибирского физ.-тех. ин-та. Проблемы кибернетики.
Томск: Изд-во Том. ун-та, 1970. Вып.
49. С. 20-37. 37.
Агибалов Г.П. Распознавание операторов, вычисляющих нормальные периодические последовательности // Известия АН СССР. Техническая кибернетика.
1971. 6. С. 165-173.
38. Агибалов Г.П. Синтез автоматов по конечно-определенным словарным функциям // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1979.
С. 160-164. 39.
Евтушенко Н.В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и вычислительная техника. 1989. 3. С. 9-14.
40. Евтушенко Н.В. О принадлежности последовательности множеству контрольных последовательностей автомата // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987.
Вып. 2. С. 130-133.
ДЕКОМПОЗИЦИЯ АВТОМАТОВ
41. Агибалов Г.П., Ванина Н.В. О сложности декомпозиции автоматов методом Зейгера // Автоматика и вычислительная техника.
1974. 5. С. 6-11.
42. Агибалов Г.П., Евтушенко Н.В. К декомпозиции конечных автоматов // Автоматика и вычислительная техника.1976.
5. С. 15-21. 43. Агибалов Г.П., Евтушенко Н.В.
Характеризация, приводимость и другие задачи каскадной декомпозиции конечных автоматов // MTA SZTAKI Tanulmanyok. Budapest: Magyar Tudomanyos akademia, 99/1979. P. 181-197.
44. Евтушенко Н.В. К декомпозиции конечных автоматов в каскадное соединение стандартных компонент // Автоматика и вычислительная техника.
1979. 2. С. 50-54. 45.
Агибалов Г.П., Евтушенко Н.В. Каскадные сети автоматов и их характеризация в терминах кодирований и покрытий // VIII Всесоюзная конференция по теории кодирования и передачи информации.
ЧЛ Москва-Куйбышев, 1981. С. 11-17.46.
Агибалов Г.П., Евтушенко Н.В. Характеризация каскадных декомпозиций и приводимость конечных автоматов // Автоматика и вычислительная техника.
1982. 1. С. 57.
47. Агибалов Г.П., Евтушенко Н.В. Описание сетей конечных автоматов в терминах кодирований и покрытий // Проблемы передачи информации.
1982. Т. 18. Вып. 3. С. 74-84.
48. Агибалов Г.П., Евтушенко Н.В. Алгебраическая характеризация перестановочных автоматов, разложимых в каскадное соединение меньших компонент // Кибернетика.
1984. 1. С. 9-15. 49. Агибалов Г.П., Евтушенко Н.В.
Декомпозиция конечных автоматов. Томск: Изд-во Том. ун-та, 1985. 127 с. 50. EvtushenkoN.V.
Conditions for existence of nontrivial parallel decompositions of sequential machines // Lecture notes in computer science. springer-verlag, 1987. 278.
P. 123-126. 51. Дрягин Ю.С. Некоторые условия существования декомпозиции автомата // Алгоритмы решения задач дискретной математики.
Томск: Изд-во Том. ун-та, 1987. Вып.
2. С. 40-52.
52. Агибалов Г.П.
Дискретные автоматы на полурешетках. Томск: Изд-во Том. ун-та, 1993. 227 с. 53.
Агибалов Г.П. Функциональные системы на полурешетках // Алгоритмы решения задач дискретной математики. Вып.2.
Томск: Изд-во Том. ун-та, 1987. С. 3-39. 54.
Agibalov G.P. Functional systems on semilattices // Lecture Notes in Computer Science. Springer-Verlag, 1987. 278.
P. 5-9. 55. Агибалов Г.П.
Квазимонотонные функции и их минимизация // Кибернетика. 1989.
2. С. 111-113. 56. Агибалов Г.П.
К кодированию полурешеток и автоматов на полурешетках // Дискретная математика. 1991.
Т. 3. Вып.2. С. 74-87. 57. Agibalov G.P.
Finite automata on partially ordered sets // V. Utkin, U. Jaaksoo (Eds.). 11th IFAC world congress preprints. Tallinn, 1990.
Vol. 6. P. 264-266 (V. Utkin, U. Ja-aksoo (Eds.).
Automatic control. 11th IFAC world congress proceedings. Pergamon press, 1991. Vol.
3). 58. Агибалов ГЛ., Бузанов В А., Липский В.Б., Румянцев Б.Ф. Логическое проектирование переключательных автоматов.
Томск: Изд-во Том. ун-та, 1983. 154 с. 59.
Агибалов Г.П., Бузанов ВА., Липский В.Б., Румянцев Б. Ф. Математическая модель схем из элементов с управляемой проводимостью // Автоматика и телемеханика. 1982. 9. С. 89-98. 60.
Agibalov G.P. Parallel computations and finite automata on semilattices // Lecture notes in computer science. springer-verlag, 1995. 964.
P. 7-15. 61. Агибалов Г.П. Полурешеточная модель динамического поведения интегральных схем // Новые информационные технологии в исследовании дискретных структур.
Екатеринбург: УрО РАН, 1996. С. 96-101. 62. Агибалов Г.П.
О полных системах операций и синтезе схем для квазимонотонных функций на конечных полурешетках // Новые информационные технологии в исследовании дискретных структур. Екатеринбург: УрО РАН, 1998. С.149-152.
63. Агибалов Г.П. Адекватные модели полурешеток, функций и автоматов на полурешетках // Вестник Томского государственного университета.
2000. 271. С. 118-121. 64.
Панкратова ИА. О системе программ для имитационного моделирования и анализа динамического поведения переключательных схем с задаваемой точностью // The third international symposium Application of the conversion research results for international cooperation (Sibconvers'99).
Proceedings. Tomsk: Tomsk state university of control systems and radioelectronics.
1999. C. 227-229.
ДИАГНОСТИКА АВТОМАТНЫХ СЕТЕЙ И НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ
65. Евтушенко Н.В., Матросова А.Ю. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей // Автоматика и вычислительная техника. 1991.
2. С. 3-7. 66.
Petrenko A., Yevtushenko N. Test suite generation for FSM with a given type of implementation errors // Protocol specification, testing and verification, X11. North Holland: Elsivier science publishers, 1992. 67.
Petrenko A., Yevtushenko N., Lebedev A., Das A. Nondeterministic state machines in protocol conformance testing // Proc.
