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

На правах рукописи

АКИНИНА Юлия Сергеевна

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ИНЖЕНЕРНОГО СИНТЕЗА САМОТЕСТИРУЮЩИХСЯ ЛОГИЧЕСКИХ ПРЕОБРАЗОВАТЕЛЕЙ С ПЕРЕСТРАИВАЕМЫМ ЭЛЕМЕНТНЫМ БАЗИСОМ

Специальности: 05.13.18 - Математическое моделирование,

численные методы и комплексы программ 05.13.15- Вычислительные машины и системы

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2006

Работа выполнена в Воронежском государственном техническом университете

Научный руководитель

заслуженный деятель науки РФ, доктор технических наук, профессор Подвальный Семен Леонидович

Официальные оппоненты:

доктор технических наук Акулинин Станислав Алексеевич; доктор технических наук Ирхин Валерий Петрович

Ведущая организация

ФГУП «Научно-исследовательский институт электронной техники»

Защита состоится «20» апреля 2006 г. в Ю00 в конференц-зале на заседании диссертационного совета Д 212.037.01 Воронежского государственного технического университета по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного технического университета

Автореферат разослан «19» марта 2006 г.

Ученый секретарь лА^ ^ ^ (и, ¿(/(

диссертационного совета / У ^ Питолин В. М.

2,00 Gf\

вЪ 72-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Быстродействие логических элементов в современных больших интегральных схемах (БИС) достигло нескольких тысяч мегагерц даже для средств вычислительной техники (СВТ) коммерческого назначения. Данные обстоятельства приводят к тому, что возможности соответствующих внешних средств технического диагностирования БИС и СВТ постоянно отстают от технологических достижений их производства, что стимулирует развитие новых контрольно-диагностических технологий, направленных на решение трех фундаментальных задач технической диагностики:

- определение правильного или неправильного функционирования;

- диагностирование и локализация источника неисправности;

- прогнозирование работоспособного состояния.

За рубежом и в России ведутся интенсивные исследования новых подходов к совершенствованию testability (готовности к тестированию) и BIST (Built-In-Self-Test - встроенное самотестирование) технологиям, как на уровне БИС, так и на уровне СВТ. В настоящее время широко известны технологии встроенного самотестирования, ориентированные на решение только двух первых задач технической диагностики. Эти технологии преимущественно базируются на использовании в различных комбинациях двух типов дополнительных узлов - псевдослучайного генератора тестовых воздействий и сигнатурного анализатора выходных реакций.

Известен также оригинальный, но малоизученный (как с теоретической, так и с практической точек зрения), вариант технической реализации самотестирующихся логических преобразователей с перестраиваемым элементным базисом, ориентированным на решение всех трёх основных задач технической диагностики, и базирующийся на использовании специальных программируемых логических матриц с перестраиваемым элементным базисом. В режиме работы в матрицах используется двухвходовый функционально-полный базис Жегалкина, а в режиме диагностирования — специфический элементный базис, содержащий только двухвходовые логические элементы неравнозначности и равнозначности. В связи с этим математическое и натурное моделирование подобных самотестирующихся логических преобразователей с перестраиваемым элементным базисом представляются весьма актуальными с точки зрения развития перспективных технологий встроенного самотестирования.

Тематика диссертационной работы соответствует одному из научных направлений Воронежского государственного технического университета «Вычислительные системы и программно-аппаратные комплексы».

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

Для достижения поставленной цели в работе определены следующие за-

дачи исследования:

РОС. НАЦиин БИБЛИОТЕК СПетербург О» M£»i

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

разработка метода и алгоритма автоматизированного преобразования дизъюнктивных нормальных форм логических функций к полиномиальным нормальным формам (в базис Жегалкина);

разработка метода и алгоритма автоматизированного преобразования полиномиальных нормальных форм к модифицированным полиномиальным нормальным формам (в базис «равнозначность», «неравнозначность»);

разработка алгоритма автоматизированного расчёта эталонных выходных реакций синтезируемого логического преобразователя в режиме самотестирования псевдослучайными последовательностями максимальной длины (М-последовательностями), принадлежащими одному и тому же классу;

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

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

Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы методы технической диагностики, алгебры логики, дискретной математики, конечных алгебраических полей, математического и имитационного моделирования, объектно-ориентированного программирования.

Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:

структурная и математическая модели самотестирующихся логических преобразователей, основу которых составляет генератор псевдослучайных М-последовательностей и программируемая логическая матрица с возможностью автоматической перестройки элементной базы (в зависимости от режима работы или диагностирования);

метод и алгоритм автоматизированного описания закона функционирования логического преобразователя в полиномиальной нормальной форме (ПНФ), отличающиеся тем, что ПНФ автоматически может быть получена на основе произвольных дизъюнктивных нормальных форм (ДНФ) при минимальных требованиях к ресурсу инструментальной ЭВМ;

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

метод и алгоритм автоматизированного расчёта любой из 2" -1 эталонных М-последовательностей как суммы по модулю 2 некоторой комбинации из п исходных М-последовательностей, отличающиеся расчетом конечного ре-

зультата в численном виде, используя полиномиальное (векторное) представление М-последовательностей.

Практическая значимость. Разработаны и зарегистрированы в ФАП ВНТИЦ программные модули: «Преобразователь булевых полиномов», «Эмулятор программируемой логической матрицы», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ», реализующие основные процедуры инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом. Перечисленные программные модули составляют основу для разрабатываемой системы автоматизированного проектирования самотестирующихся логических преобразователей с перестраиваемым элементным базисом.

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использовались в Военном институте радиоэлектроники (г.Воронеж) при проведении в 2005 году приоритетной НИР «Полоса ВИРЭ» для оценки влияния мощных электромагнитных излучений на изменение внутренней структуры различных типов цифровых микросхем.

Структурная и математическая модели самотестирующихся логических преобразователей используются в учебном процессе ВГТУ в курсе «Схемотехника ЭВМ» при обучении студентов специальности 230101.

Апробация работы. Основные положения диссертационной работы докладывались на 2-й Всероссийской науч.-техн. электронной конференции «Электроника 2003» (Москва, МИЭТ, 2003), IX Международной открытой научной конференции «Современные проблемы автоматизации в непромышленной сфере и экономике» (Воронеж, 2004), IX Международной научной конференции «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2004).

Публикации. Основные результаты диссертационной работы опубликованы в 12 печатных работах, из них 4 без соавторов. В работах, опубликованных в соавторстве, лично соискателем предложены: в [6,7] - математические модели логических преобразователей на ПЛМ с перестраиваемым логическим базисом, в [8] - формализованный подход к разработке трех основных методик, необходимых для инженерного применения ПЛМ с перестраиваемым элементным базисом, в [5,9] - использование М-последовательностей в качестве тестовых, а также новый метод нахождения произвольной их совокупности, в [10, 11, 12] - алгоритмы для программных модулей, реализующих последовательную процедуру синтеза структуры самотестирующихся логических преобразователей.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 146 страницах, списка литературы из 87 наименований, содержит 68 рисунков, 18 таблиц, приложения.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертационной рабо-

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

В первой главе осуществлен системный анализ особенностей самотестирующихся средств вычислительной техники (СВТ), как объектов технической диагностики, рассмотрены традиционные подходы к обеспечению тесто-пригодности двухуровневых программируемых логических матриц (ПЛМ) с типовой структурой и выявлены их недостатки.

Подробно рассмотрены структурная модель (рис.1) и математические модели (1-3) легкодиагностируемой ПЛМуаг. Её отличительной особенностью является возможность работы в двух режимах: режиме работы (сигнал управления г = 1) и режиме контроля/диагностирования (г = 0). В каждом из режимов работы в ПЛМ автоматически перестраивается её элементный базис за счет использования специального логического элемента УАИ, математической моделью которого является логическое уравнение (1). Как видно из уравнения (1) элемент УАЯ при г =1 реализует бинарную логическую функцию «И», а при г = 0 - бинарную логическую функцию «равнозначность». Соотношение (2) является математической моделью ПЛМуаг в рабочем режиме (г = 1), соотношение (3) - математической моделью ПЛМуаг в режиме контроля/диагностирования (г = 0).

х,

V,

Рис. 1. Структурная модель легкодиагностируемой ПЛМуагс перестраиваемым элементным базисом

X].. .х, - входные логические переменные;

Р„, 01к, - плавкие перемычки, определяющие структуру ПЛМуаг и/или частично удаляемые при её программировании; У, - реализуемые логические функции.

УАК = V хг_! V х, Vг , (1)

Ук =ьк'

_ /=1 I <=1

М I у

, * = и,«' = 1.« ,./' = 1,<7 , (2) ,к = ,1 = 1,5 ,у = 1,</. (3)

В (1-3) используются следующие обозначения: «V» - логическое сложение; «Л, П» - логическое умножение; - равнозначность; — неравнозначность; сц, с1|у, Ьк - логические переменные, такие, что

=

с„ =

Ьк

если перемычка присутствует,

если перемычка отсутствует.

если перемычка Ри присутствует,

если перемычка отсутствует.

если перемычка присутствует,

если перемычка отсутствует.

Матрицы С, Б, векторы В и А являются таблицами настройки (прошивки) ПЛМуаг для реализации выходных функций в режиме работы и самотестирования:

Х!...Х2 XI

С =

Ьх «1

4|"4г 4, Ь, А = а*

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

Предложена исходная для дальнейшего исследования структурная модель (рис.2) самотестирующихся логических преобразователей с перестраиваемым элементным базисом (ЛП„аг). На рис.2 обозначено: хь х2,..., х,- входные переменные, М,, М2,..., М, - тестовые и эталонные М-последовательности, у} -выходные сигналы, 5 - переменная, показывающая наличие или отсутствие неисправностей в ПЛМуаг, Б* - переменная, которая выполняет функцию фла-

га при наличии хотя бы одной неисправности, Сь С2, С3 - сигналы синхронизации, г - управляющий сигнал, ГТЭП - генератор тестовых и эталонных последовательностей, MUX - s двухканальных мультиплексоров, ФЭП - формирователь эталонной последовательности.

Рис.2. Структурная модель самотестирующегося логического преобразователя (ЛПуаг) с перестраиваемым элементным базисом.

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

Для практического применения самотестирующегося логического преобразователя с перестраиваемым элементным базисом необходима разработка математических моделей перечисленных задач. Пусть требуется найти формальные отображения между алгебраическими структурами 8Ь 82, 83, 84, которые отличаются природой своих элементов и наборами операций. Рассмотрим множества В,Р,М и операции в них, образующие следующие структуры (4), (5), (6), (7):

=(Я,л,У,-,), Я = {*,,..., хДдс, = {0,1},/ = й\ (4)

52 = (Лл,®,1), Р = {*,,..., х,},х, = {0,1},/ = 17. (5)

53 = (М,<8>,©,1), М = {Мр..., М5}, (6) £4 = (М,®,1), М - {ММ$ }. (7)

Тогда однозначные отображения /,:/)-> Р, /2:Р М, /3:М ~*М

математически описывают три основные задачи методики автоматизированного синтеза самотестирующихся логических преобразователей: преобразование исходных дизъюнктивных нормальных форм, реализуемых логических функций к полиномиальным нормальным формам - отображение ^ ; преобразование полиномиальных форм к модифицированным полиномиальным нормальным формам - отображение определение эталонных М-последовательностей в режиме самотестирования при замене входных переменных на тестовые М-последовательности - отображение ^ .

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

Рис. 3. Схема проведения экспериментальных исследований для проверки корректности полученных в работе результатов

Исходными данными является описание закона функционирования синтезируемого логического преобразователя в виде дизъюнктивных нормальных форм в соответствии с (4). В инструментальной ЭВМ реализуются разработанные в работе алгоритмы в соответствии с (5), (6), (7), выходными данными которых являются матрицы С, Б и векторы А, В с найденными двоичными значениями элементов. В системе схемотехнического моделирования создается модель синтезируемого логического преобразователя, которая исследуется в режиме работы и в режиме самотестирования. Результаты имитационного моделирования визуализируются имеющимися средствами системы моделирования.

Во второй главе решаются следующие задачи: автоматизация перехода от дизъюнктивных нормальных форм, которыми изначально задается закон функционирования ЛПуаг, в полиномиальные нормальные формы; оптимизация исходной структуры ПЛМУаг; разработка методик автоматического формирования модифицированных полиномиальных нормальных форм, описывающих закон функционирования ЛПуаг в режиме самотестирования; алгоритмизация восстановления таблицы истинности логических функций по их

ДНФ.

Задача преобразования ДНФ в ПНФ ставится и решается как задача изо-или гомоморфного отображения одной алгебраической структуры (двоичной алгебры Буля) на другую структуру (алгебру Жегалкина).

Исследованы и алгоритмизированы два метода автоматического преобразования в полиномиальные нормальные формы: известный в дискретной математике «метод неопределенных коэффициентов» и впервые предложенный метод, который назван «методом частных ПНФ».

Разработан алгоритм (А1) формирования ПНФ методом неопределенных коэффициентов. Недостатком данного алгоритма (как и метода) является то, что логическая функция должна быть исходно представлена в СДНФ, по которой строится таблица истинности, а сама таблица истинности до окончания вычислений должна храниться в памяти вычислительной машины.

Существо нового метода частных ПНФ состоит в следующем. Полиномиальная нормальная форма формируется путём преобразования каждого мин-терма СДНФ в частные ПНФ (ЧПНФ) в виде векторного представления и последующего поэлементного суммирования по модулю 2 (с накоплением результата) сформированных двоичных векторов частных ПНФ.

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

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

Исследование алгоритма А2 показало, что его возможности могут быть существенно расширены, если модифицировать исходную структуру ПЛМ„аг таким образом, что для её настройки (прошивки) будет достаточно лишь матрицы О и вектора А. Это возможно при условии, что структура ПЛМуаг является фиксированной для определенного числа входных переменных пив ней реализован булеан входных переменных на двухвходовых элементах УАЯ. При такой модификации структуры ПЛМуаг представляется возможным совместить алгоритмы формирования ПНФ (алгоритм А2) с алгоритмом нахождения модифицированной ПНФ (алгоритм АЗ, рис.5). Модифицированная ПНФ необходима для формирования эталонной М-последовательности, формируемой подсистемой генерации тестовых и эталонной М-последовательностей самотестирующегося логического преобразователя.

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

У

Задание количества аргументов (п) преобразуемой логической функции Задание символьных имен аргументов логической функции и закрепление этих имен за разрядами двоичного п-разрадного числа 5.

Ввод очередного минтерма К,, увеличение на 1 счетчика введенных миитермов

Вычисление значения N=2°-! Создание и обнуление двоичного массива В={Ьо,Ьи. ,Ьц} Переменным-счетчикам и J присваивается значение 1. Вводятся временные нулевые вектора Э и АУ размерностью п

По полученному массиву В и переменной 8 формируется ПНФ логической функции в символьном виде

ОСТАНОВ

Рис.4. Алгоритм (А2) формирования ПНФ на основе метода частных ПНФ.

Рис. 5. Алгоритм (АЗ) формирования модифицированной ПНФ

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

Рис. 6. Обобщенная структура подсистемы генерации тестовых и эталонной М-последовательностей

На рис. 6 г - внешний сигнал, который управляет режимом работы/диагностирования логического преобразователя, сь с2 - сигналы синхронизации, М^..., М„ - тестовые М-последовательности, Х],..., хп - входные переменные ЛП, У!,..., У, - выходные сигналы, С - сигнал ошибки в режиме самотестирования, Б - переменная, формируемая в ПЛМ при расхождениях с эталонной М-последовательностью.

Любая М-последовательность представляет собой периодическую И-разрядную двоичную последовательность, содержащую (Ы+1)/2 единичных значений и 1 )/2 -1) нулевых значений, причем N - всегда нечетное число. С увеличением N чередование единичных и нулевых значений приближается к случайному распределению. М-последовательности, принадлежащие одному и тому же классу, отличаются друг от друга только величиной циклического сдвига. Если какую-либо последовательность выбрать в качестве опорной и присвоить ей некоторый номер (например М^, то все остальные М-последовательности будут отличаться от М, величиной сдвига, и тогда их можно соответствующим образом пронумеровать - М2, М3 ... и т.д., и различать друг от друга.

Выходные и эталонная М-последовательности, в конечном счете, определяются на основе соответствующих модифицированных ПНФ, общий вид которых, как было найдено во второй главе, определяется соотношением (8):

где ц = У] в режиме диагностирования ЛП, ао^{0,1}, ау={0,1},3=[1Д],

¡=[1,п], М,—индексированные тестовые М-последовательности, подаваемые на ¡-ые входы логического преобразователя при формировании ]-ой выходной функции.

Л/э =£©//,, /л,еМ. (9)

7=1

Из (8),(9) следует, что для нахождения выходных и эталонной М-последовательностей, достаточно располагать методами логического умножения тестовых М-последовательностей на бинарную переменную и сложения

по модулю 2 произвольной совокупности тестовых М-последовательностей. Но известно, что суммирование по модулю 2 произвольной совокупности М-последовательностей из одного и того же класса порождает М-последовательность, из этого же класса. Тогда отыскание решений уравнений вида (8),(9) эквивалентно определению номера результирующей М-после-довательности как некоторой функции от номеров суммируемых М-последовательностей.

Для детализации подсистемы генерации, а также с целью алгоритмизации еб функционирования осуществлен анализ диагностических свойств М-последовательностей и рассмотрены основы их математического описания в полях Галуа. Элементы поля могут иметь следующие представления, образующие изоморфные поля - целочисленное, степенное, логарифмическое, векторное, полиномиальное. При векторном представлении элементов поля сложение выполняется самым простым образом: как поразрядная сумма по модулю 2. Однако известные методы нахождения номера результирующей М-последовательности либо плохо формализуемы, либо требуют выполнения дополнительных операций умножения/деления и, как следствие, смешанных способов представления М-последовательностей как элементов полей Галуа. Установлено, что сложность известных методов решения данной задачи обусловлены её исходной постановкой: индексы М-последовательностей должны быть эквивалентны величинам их относительного сдвига относительно опорной М-последовательности. Отказавшись от этого требования, которое в данной работе является несущественным, разработан новый метод и алгоритм нахождения суммы произвольной совокупности М-последовательностей из одного класса, который базируется только на векторном представлении М -последовательностей и потому легко реализуется с помощью средств вычислительной техники. Предложенный новый метод (метод порождающего полинома) заключается в таком способе нумерации М-последовательностей, который согласован с нумерацией бит в опорной последовательности Мр Поясним существо метода порождающего полинома. На рис.7 представлена структурная схема многоканального генератора М-последовательностей, число каналов которого равно п, где п =3 - количество разрядов циклического регистра сдвига, физически генерирующего опорную М-последовательность. Период повторения такого генератора определяется величиной 2п-1. Битовая структура опорной последовательности М1 определяется порождающим полиномом х Ф * © 1, который реализуется линейной обратной связью в виде сумматора по модулю 2 (Е).

Рис.7. Структурная схема генератора М-последовательностей на трехразрядном регистре сдвига с порождающим полиномом *3 ® * <

Из рис.7 следует, что сущность метода порождающего полинома заключается в таком согласованном выборе значений 1 и 3, чтобы в конечном счёте, 1 = ] , но при этом должны сохраняться закономерности, определяемые порождающим полиномом, как относительно бит в опорной последовательности (М,), так и относительно одноиндексных М-последовательностей, формируемых на выходах бит опорной последовательности. Следует отметить, что формирование бит опорной последовательности М] осуществляется «по горизонтали», а формирование соответствующих М-последовательностей - «по вертикали». На основе порождающего полинома имеем следующий закон формирования значений бит опорной последовательности М^.

О; £>,+1=£>у 0]+2=01+1. (10)

Если задаться некоторыми начальными значениями бит опорной последовательности М[ (например, 0;+2 =1; =1; =0), то на основании (10) её можно развернуть в ленту, с циклическим повторением значений своих бит, а также развернуть и все сдвинутые М-последовательности данного класса. После таких действий удаётся решить поставленную задачу и получить системы уравнений на основе порождающего полинома, справедливую как для отдельных бит опорной М-последовательности, так и для всего множества М-последовательностей из их замкнутого класса. В таблице представлены все 2°-1 сдвинутые М-последовательности, порождаемые генератором, представленном на рис.7. Последовательность М[ является опорной.

__Таблица

М1 м2 Мз м, м5 м6 м7

Ц+2 0]+1 О,

М| 1 1 0 1 0 0 1

М2 1 0 1 0 0 1 1

Мз 0 1 0 0 1 1 1

М, 1 0 0 1 1 1 0

М5 0 0 1 1 1 0 1

Мб 0 1 1 1 0 1 0

м7 1 1 1 0 1 0 0

Если рассматривать таблицу как матрицу, то данные в ней симметричны относительно главной диагонали. Отсюда следует, что бит Б] +2 следует нумеровать как Оь бит 01+, - как и2, бит - как Е)2. Тогда на основании порождающего полинома имеем две истинных системы уравнений (11).

д,=дед, м4 = м3ел/,,

/>5=£>2®Д,, М5=Мг®Мл,

£>6=£>,@/)5, М6 = МХ®М,, (И)

£>7 = £>6 Ф Д, • М7 = М6 © Л/4 •

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

ны две конкурирующие структуры подсистемы генерации тестовых и эталонной М-последовательносгей: на основе л разрядного регистра сдвига с линейной обратной связью и ТЧ-разрядного циклического регистра сдвига с предварительно записываемой опорной М-последовательностью (N=2" - 1).

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

Уточняется существо предлагаемой методики инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом, которая базируется на разработанных моделях и алгоритмах, реализованных в виде программных модулей, зарегистрированных в ФАП ВНТИЦ: «Преобразователь булевых полиномов», «Эмулятор программируемой логической матрицы», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ». Данные программные модули реализуют автоматическое формирование таблицы истинности булевой функции, заданной в виде произвольного булевого многочлена, и на её основе - формирование полиномиальной нормальной формы логической функции по разработанному в работе алгоритму А2 , модифицированных полиномиальных нормальных форм по алгоритму АЗ, а также расчет номера эталонной М-последовательности для обеспечения свойства самотестируемости. Структура разработанного программного комплекса показана на рис.8.

Основной модуль «Эмулятор ПЛМ»

7\

Ввод исходных данных

-N

Преобразователь булевых полиномов

С

Расчет и генерация эталонной М-последовательности

Вывод выходных данных

Визуализация программной модели ПЛМ„„ и моделирование процесса ее функционирования в режимах работы / диагностирования

Рис. 8. Структура разработанного программного комплекса.

Инструментальной является IBM-совместимая ЭВМ с установленной операционной системой Windows 98/Ме/2000/ХР. Программы написаны на языках MS Visual С++ 7.1 и Delphi 7, для их функционирования необходимо не менее 1.3 Мб на жестком диске и не менее 8 Мб оперативной памяти.

Программа «Эмулятор ПЛМ» написана в среде программирования Delphi 7.0, что значительно упростило реализацию удобного пользовательского ин-

терфейса. Все модули проекта разделены на три категории: модули обработки пользовательского интерфейса (название файлов начинается с буквы «Б»); модули описания СОМ-компонентов (название файлов начинается с «1п1ег5>); модули, реализующие различные объекты программы (название файлов начинается с буквы «и»). Программа «Преобразователь булевых полиномов» состоит из СОМ-компонента модуля разбора формул (\lDip), который реализует методы трансляции и преобразования булевых многочленов. На рис.9 представлено главное окно программного модуля «Эмулятор программируемой логической матрицы».

* - ] П - , I

?«блнв*ияг*идат< Упршнтш Оии

ЖтШ'Ш

сЩмЯр*

я f* v ^Этг-«*«'

щ 1* л «Vc ^Vfev*

г VcD**»«»

& Ouwn» чкт»

(щ) (Я) (S) (S) («1») <£)

11 21 31 11 5J 61 7.1 © ф © © © © © ©

12 22 32 12 5.2 ВД 72

© Ф С' # © © ©

1.Э 23 33 13 5.3 Б.З 73

© ® <5* © © % © ©

И 2.1 34 11 И 6.1 71

© Ъ © Ф © © Ф ©

15 25 3.5 45 53 Б.5 7 5

О®®®®®©®"

Т (-/Г* ^ УМ / f >/ • '"V,

гЛ

Рис. 9. Главное окно программного модуля «Эмулятор программируемой логической матрицы»

Верификация разработанных методов, алгоритмов и программного комплекса осуществлялась методом имитационного схемотехнического моделирования программно генерируемых структур самотестирующихся логических преобразователей с перестраиваемым элементным базисом. Средством имитационного моделирования выбрана система схемотехнического моделирования Electronics Workbench (EWB) версий 5.Х.

Отличительной особенностью программы EWB является наличие виртуальных контрольно-измерительных приборов (генератора слов, 16-канального логического анализатора, двухканального осциллографа), по внешнему виду, характеристикам и способам управления приближенных к их промышленным аналогам. Кроме того, реализован виртуальный прибор (логический преобразователь), который не имеет приборных аналогов, но весьма эффективен для построения таблиц истинности логических функций, реализуемых моделями логических преобразователей при произвольном их схемотехническом исполнении.

С помощью имитационного моделирования подтверждена достоверность

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана и оптимизирована структурная модель новой вычислительной структуры - самотестирующегося логического преобразователя с перестраиваемым элементным базисом, предлагаемого для широкого инженер- » ного использования. Его основу составляют генератор псевдослучайных М-последовательностей и программируемая логическая матрица, отличающаяся

от известных тем, что в режиме работы её элементным базисом является базис Жегалкина, который в режиме самотестирования электронно перестраивается в базис из двухвходовых элементов «равнозначность» и «неравнозначность». В режиме самотестирования М-последовательности используются в качестве тестовых и эталонных последовательностей.

2. На основе разработанных математических моделей самотестирующегося логического преобразователя с перестраиваемым элементным базисом предложена обобщенная процедура его инженерного синтеза.

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

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

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

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

7. Предложены две конкурирующие структуры подсистемы генерации тестовых и эталонной М-последовательностей: на основе п разрядного регистра сдвига с линейной обратной связью и ^разрядного циклического регистра сдвига с предварительно записываемой опорной М-последовательностью (N=2* - 1). Величины п и N имеют примерно равные значения, но должны

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

8. На основе разработанных методов и алгоритмов реализованы программные модули, зарегистрированные в ФАП ВНТИЦ: «Преобразователь булевых полиномов», «Эмулятор программируемой логической матрицы», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ», интегрированные в программный комплекс и автоматизирующие основные этапы инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым эле-

Ч ментным базисом.

9. Проведена верификация средствами системы схемотехнического моделирования Electronics Workbench 5.Х. разработанных методов, алгоритмов и программных модулей путем схемотехнического моделирования программно генерируемых структур самотестирующихся логических преобразователей с перестраиваемым элементным базисом, функционирующих как в режиме работы, так и в режиме самотестирования.

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

Основные результаты диссертации опубликованы в следующих работах:

1. Акинина Ю.С. Оптимистическая оценка сложности алгоритма восстановления совершенной дизъюнктивной нормальной формы // Техника машиностроения. 2002. №5. С. 74-75.

2. Акинина Ю.С. Анализ принципов построения и формализация модели легкодиагностируемых ПЛМ с перестраиваемым логическим базисом

, // Электроника - 2003: Тез докл. 2-я Всерос. научн.-техн. дистанционная

конф.- М.: МИЭТ, 2003. С. 102-103

3. Акинина Ю.С. Анализ принципов построения и формализация , модели легкодиагностируемых ПЛМ с перестраиваемым логическим базисом

// Современные проблемы автоматизации в непромышленной сфере и экономике: Сб. тр. IX Междунар. открытой науч. конф. Воронеж. 2004. Вып. 9. С. 57-58.

4. Акинина Ю.С. Разработка метода преобразования дизъюнктивных нормальных форм в полиномиальную нормальную форму // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. IX Междунар. науч. конф. Воронеж. 2004. Вып.9. С. 271.

5. Акинина Ю.С., Панявин В.В., Тюрин С.В. Об одном подходе к сравнительной оценке эффективности контрольно-диагностических тестов для цифровых модулей ОЗУ // Вестник Воронеж, гос. техн. ун-та. - 2002. Вып. 8.2, С. 49-52.

6. Акинина Ю.С., Тюрин С.В. Альтернативный подход к обеспече-

17

нию легкодиагностируемости двухуровневых программируемых пользователем логических матриц // Вестник Воронеж, гос. техн. ун-та. Сел. Вычислительные и информационно-телекоммуникационные системы. 2003. Вып 8.3. С. 32-35.

7. Акинина Ю.С., Тюрин C.B. Разработка и исследование моделей легкодиагностируемых логических преобразователей на ПЛМ с перестраиваемым логическим базисом // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. IX Междунар. открытой науч. конф. Воронеж. 2004. Вып. 9. С.270.

8. Акинина Ю.С., Подвальный C.JL, Тюрин C.B. Особенности практического применения программируемых пользователем логических матриц с перестраиваемым элементным базисом // Информационные технологии моделирования и управления. - Воронеж: Изд-во «Научная книга», 2005. 3(21). С. 407- 412.

9. Акинина Ю.С., Подвальный С.Л., Тюрин C.B. Метод нахождения суммы произвольной совокупности М-последовательносгей из одного класса // Информационные технологии моделирования и управления,- Воронеж: Изд-во «Научная книга», 2005. 3(21). С. 358- 363.

10. Акинина Ю.С., Тюрин C.B., Тютин М.В. Программный модуль «Преобразователь булевых полиномов» // ФАП ВНТИЦ № 50200400714 от 06.07.2004

11. Акинина Ю.С., Тюрин C.B., Тютин М.В. Программа «Эмулятор программируемой логической матрицы» // ФАП ВНТИЦ № 50200400711 от от 06.07.2004

12. Акинина Ю.С., Моргунов Ю.М., Тюрин C.B. Программный модуль «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ» // ФАП ВНТИЦ № 50200400701 от 06.07.2004

*

Подписано в печать 14.03.2006 Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ №

Воронежский государственный технический университет 394026 Воронеж, Московский просп., 14

¿

X

«

i

¿СШ

8372

ВВЕДЕНИЕ

СОДЕРЖАНИЕ

1. ПРОБЛЕМЫ СИНТЕЗА И ОБОЩЕННЫЕ МОДЕЛИ

САМОТЕСТИРУЮЩИХСЯ СРЕДСТВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ф 1.1. Особенности самотестирующихся средств вычислительной техники как объектов технического диагностирования.

1.2. Структурные модели традиционных самотестирующихся средств вычислительной техники.

Ф 1.3 .Типовая структура двухуровневых программируемых логических матриц и особенности их тестирования. ^

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

1.5. Обобщенный подход к инженерному синтезу самотестирующихся логических преобразователей с перестраиваемым 40 элементным базисом.

Цель работы и задачи исследования.

• 2. РАЗРАБОТКА МЕТОДИК АВТОМАТИЗИРОВАННОГО ПРЕОБРАЗОВАНИЯ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ В ПОЛИНОМИАЛЬНЫЕ ФОРМЫ.

2.1. Особенности задачи автоматизированного преобразования дизъюнктивных нормальных форм в полиномиальные формы.

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

2.3. Методика автоматического формирования полиномиальных нормальных форм с использованием разложения на биномиальные коэффициенты.

2.4. Методика автоматического формирования модифицированных полиномиальных нормальных форм.

2.5. Автоматизация восстановления произвольных дизъюнктивных нормальных форм в таблицы истинности.

Выводы.

3. РАЗРАБОТКА МЕТОДИКИ АВТОМАТИЗИРОВАННОГО РАСЧЁТА ЭТАЛОННЫХ ВЫХОДНЫХ РЕАКЦИЙ В КЛАССЕ

М-ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

3.1. Диагностические свойства и теоретические основы М-последовательностей.

3.2. Методика расчёта конечной суммы произвольной совокупности М-последовательностей из одного и того же класса.

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

Выводы.

4. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ДОСТОВЕРНОСТИ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЯ.

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

4.2. Общая характеристика экспериментальных исследований метода синтеза самотестирующихся логических преобразователей. ф 4.3. Методика и результаты экспериментальных исследований метода синтеза самотестирующихся логических преобразователей.

Выводы.

Актуальность темы. Быстродействие логических элементов в современных больших интегральных схемах (БИС) достигло нескольких тысяч мегагерц даже для средств вычислительной техники (СВТ) коммерческого назначения. Данные обстоятельства приводят к тому, что возможности соответствующих внешних средств технического диагностирования БИС и СВТ постоянно отстают от технологических достижений их производства. Это стимулирует создание и совершенствование теоретической и технической базы средств вычислительных машин и систем, использующих технологию встроенного самотестирования по крайней мере, на уровне технической базы -многовходовых программируемых логических преобразователей, реализующих произвольную систему логических функций в больших интегральных схемах. При этом новые контрольно-диагностические технологии должны ориентироваться на решение всех трех фундаментальных задач технической диагностики: -определение правильного или неправильного функционирования; -диагностирование и локализация с некоторой точностью источника неисправности;

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

За рубежом и в России ведутся интенсивные исследования новых подходов к совершенствованию testability (готовности к тестированию) и BIST (Built-In-Self-Test - встроенное самотестирование) технологиям, как на уровне БИС, так и на уровне СВТ. В настоящее время широко известны технологии встроенного самотестирования, ориентированные на решение только двух первых задач технической диагностики. Эти технологии преимущественно базируются на использовании в различных комбинациях двух типов дополнительных узлов - псевдослучайного генератора тестовых воздействий и сигнатурного анализатора выходных реакций.

Известен также оригинальный, но малоизученный (как с теоретической так и с практической точек зрения), вариант технической реализации самотестирующихся логических преобразователей с перестраиваемым элементным базисом, ориентированным на решение всех трёх основных задач технической диагностики, и базирующийся на использовании специальных программируемых логических матриц с перестраиваемым элементным базисом. В режиме работы в матрицах используется двухвходовый базис Жегалкина, а в режиме диагностирования - специфический элементный базис, содержащий только двухвходовые логические элементы неравнозначности и равнозначности. В связи с этим математическое и натурное моделирование подобных самотестирующихся логических преобразователей с перестраиваемым элементным базисом представляется весьма актуальными с точки зрения развития перспективных технологий встроенного самотестирования.

Таким образом, разработка моделей и алгоритмов инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом представляется весьма важной и актуальной тематикой с точки зрения развития В18Т-технологий в вычислительной технике.

Тематика диссертационной работы соответствует одному из научных направлений Воронежского государственного технического университета «Вычислительные системы и программно-аппаратные комплексы».

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

Для достижения поставленной цели в работе определены следующие задачи исследования: разработка структурной и математической моделей самотестирующихся логических преобразователей на программируемых логических матрицах с перестраиваемым элементным базисом, предлагаемых для инженерного использования; разработка метода и алгоритма автоматизированного преобразования дизъюнктивных нормальных форм логических функций к полиномиальным нормальным формам (в базис Жегалкина); разработка метода и алгоритма автоматизированного преобразования полиномиальных нормальных форм к модифицированным полиномиальным нормальным формам (в базис «равнозначность», «неравнозначность»); разработка алгоритма автоматизированного расчёта эталонных выходных реакций синтезируемого логического преобразователя в режиме самотестирования псевдослучайными последовательностями максимальной длины (М-последовательностями), принадлежащими одному и тому же классу; разработка программных модулей, реализующих разработанные алгоритмы для автоматизации процедур инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом; экспериментальная проверка на основе имитационного моделирования пригодности разработанных автоматизированных процедур инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом.

Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы методы технической диагностики, алгебры логики, дискретной математики, конечных алгебраических полей, математического и имитационного моделирования, объектно-ориентированного программирования.

Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной: структурная и математическая модели самотестирующихся логических преобразователей, основу которых составляет генератор псевдослучайных М-последовательностей и программируемая логическая матрица с возможностью автоматической перестройки элементной базы (в зависимости от режима работы или диагностирования); метод и алгоритм автоматизированного описания закона функционирования логического преобразователя в полиномиальной нормальной форме (ПНФ), отличающиеся от известных тем, что полиномиальная нормальная форма автоматически может быть получена не только на основе совершенной дизъюнктивной нормальной формы (СДНФ) или таблицы истинности, но и на основе дизъюнктивных нормальных форм (ДНФ) с их предварительным восстановлением до совершенных форм при минимальных требованиях к ресурсу инструментальной ЭВМ; формальные подходы к количественной оценке вычислительной сложности различных алгоритмов восстановления таблиц истинности логических функций по их ДНФ и алгоритмы восстановления: тривиальный (пессимистическая оценка сложности) и вычислительный (оптимистическая оценка), обеспечивающие возможность реализации логических преобразователей предварительно заданных как в СДНФ, так и в ДНФ, что расширяет область практического применения самотестирующихся логических преобразователей; метод и алгоритм автоматизированного расчёта любой из 2" - 1 эталонных М-последовательностей как суммы по модулю 2 некоторой комбинации из п исходных М-последовательностей, отличающиеся от известных тем, что расчет конечного результата осуществляется в численном виде, используя полиномиальное (векторное) представление М-последовательностей.

Практическая значимость. Разработаны и зарегистрированы в ФАП ВНТИЦ программные модули: «Преобразователь булевых полиномов», «Эмулятор программируемой логической матрицы», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ», реализующие основные процедуры инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом.

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использовались в Военном Институте Радиоэлектроники (г.Воронеж) при проведении в 2005 году приоритетной НИР «Полоса ВИРЭ» для оценки влияния мощных электромагнитных излучений на изменение внутренней структуры различных типов цифровых микросхем. Структурная и математическая модели самотестирующихся логических преобразователей используются в учебном процессе ВГТУ в курсе «Схемотехника ЭВМ» при обучении студентов специальности 230101.

Апробация работы. Основные положения диссертационной работы докладывались на 2-ой Всероссийской н/т электронной конференции «Электроника 2003» (Москва, МИЭТ, 2003), IX Международной открытой научной конференции «Современные проблемы автоматизации в непромышленной сфере и экономике» (Воронеж, 2004), IX Международной научной конференции «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2004).

Публикации. Основные результаты диссертационной работы опубликованы в 12 печатных работах, из них 4 без соавторов. В работах, опубликованных в соавторстве, лично соискателем предложены: в [36,41] -математические модели логических преобразователей на ПЛМ с перестраиваемым логическим базисом, в [42] - формализованный подход к разработке трех основных методик, необходимых для инженерного применения ПЛМ с перестраиваемым элементным базисом, в [66,72] — использование М-последовательностей в качестве тестовых, а также новый метод нахождения произвольной их совокупности, в [75, 76, 77] -алгоритмы для программных модулей, реализующих последовательную процедуру синтеза структуры самотестирующихся логических преобразователей

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 146 страницах, списка литературы из 87 наименований, содержит 68 рисунков, 18 таблиц, приложения.

Выводы:

1. На основе разработанных структурных и математических моделей самотестирующихся ЛП созданы программные модули «Преобразователь булевых полиномов», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ», интегрированные в модуль «Эмулятор программируемой логической матрицы».

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

3. Проанализированы методы имитационного моделирования с использованием пакетов схемотехнического моделирования цифровых и аналоговых устройств, и выявлена целесообразность использования пакета Electronics Workbench (EWB 5.XX) для экспериментальных исследований метода инженерного синтеза самотестирующихся ЛП.

4. Средствами пакета моделирования Electronics Workbench (EWB 5.XX) создана и исследована имитационная модель логического преобразователя.

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

6. Произведен сравнительный анализ результатов, полученных при эксплуатации программного модуля «Эмулятор программируемой логической матрицы» и экспериментальных исследований с использованием имитационной модели, который показал корректность разработанных и реализованных методов и алгоритмов.

144

ЗАКЛЮЧЕНИЕ

1. Разработана и оптимизирована структурная модель новой вычислительной структуры - самотестирующегося логического преобразователя с перестраиваемым элементным базисом, предлагаемого для широкого инженерного использования. Его основу составляют генератор псевдослучайных М-последовательностей и программируемая логическая матрица, отличающаяся от известных тем, что в режиме работы её элементным базисом является базис Жегалкина, который в режиме самотестирования электронно перестраивается в базис из двухвходовых элементов «равнозначность» и «неравнозначность». В режиме самотестирования М-последовательности используются в качестве тестовых и эталонных последовательностей.

2. Разработаны математические модели самотестирующегося логического преобразователя с перестраиваемым элементным базисом на основе чего предложена обобщенная процедура его инженерного синтеза, включающая:

• новые метод и алгоритм автоматизированного преобразования дизъюнктивных нормальных форм логических функций к полиномиальным нормальным формам, отличающиеся от известных тем, что полиномиальная нормальная форма формируется путём преобразования каждого отдельного минтерма в частные полиномиальные нормальные формы в виде их векторного представления и последующего поэлементного суммирования по мудулю2 (с накоплением результата) сформированных двоичных векторов частных полиномиальных нормальных форм;

• метод и алгоритм автоматического формирования модифицированных полиномиальных нормальных форм совместно с формированием полиномиальных нормальных форм;

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

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

4. Предложены две конкурирующие структуры подсистемы генерации тестовых и эталонной М-последовательностей: на основе п разрядного регистра сдвига с линейной обратной связью и N-разрядного циклического регистра сдвига с предварительно записываемой опорной М-последовательностью (N=2K - 1). Величины п и N имеют примерно равные значения, но должны быть не меньше, чем количество рабочих переменных самотестирующегося логического преобразователя.

5. На основе разработанных методов и алгоритмов реализованы программные модули, зарегистрированные в ФАП ВНТИЦ: «Преобразователь булевых полиномов», «Эмулятор программируемой логической матрицы», «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ», интегрированные в программный комплекс и автоматизирующие основные этапы инженерного синтеза самотестирующихся логических преобразователей с перестраиваемым элементным базисом.

6. Проведена верификация средствами системы схемотехнического моделирования Electronics Workbench 5.Х. разработанных методов, алгоритмов и программных модулей путем схемотехнического моделирования программно генерируемых структур самотестирующихся логических преобразователей с перестраиваемым элементным базисом, функционирующих как в режиме работы, так и в режиме самотестирования.

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

147

Условные обозначения

АНФ - антивалентная нормальная форма БИС (СБИС) - большие (сверхбольшие) интегральные схемы ГГТТЭ - генератор тестовых и эталонных последовательностей ДНФ - дизъюнктивная нормальная форма логической функции ЛП - логический преобразователь

МПНФ - модифицированная полиномиальная нормальная форма

ПЛМуаг - программируемая логическая матрица с перестраиваемым элементным базисом ПНФ - полиномиальная нормальная форма ПЭБ - перестраиваемый элементный базис СВТ - средства вычислительной техники СДНФ — совершенная дизъюнктивная нормальная форма ЧПНФ - частная полиномиальная нормальная форма EWB - пакет схемотехнического моделирования Electronics Workbench VAR - электронно перестраиваемый логический элемент

148

1. Байда Н.П. Микропроцессорные системы поэлементного диагностирования РЭА / Байда Н.П., Кузьмин И.В., Шпилевой В.Т. М.: Радио и связь, 1987. 256 с.

2. Байда Н.П. Самообучающиеся анализаторы производственных дефектов РЭА / Байда Н.П., Месюра В.И., Роик A.M. M.: Радио и связь, 1991. 256 с.

3. Горлов М.И., Королёв С.Ю. Физические основы надежности интегральных микросхем. Воронеж: Издательство Воронежского университета, 1995.-200 с.

4. Надёжность и эффективность в технике: Справочник. В ЮТ. / Ред. совет: B.C. Авдуевский (пред.) и др. М.: Машиностроение, 1987. Т. 9. Техническая диагностика / Под общ. ред. В.В. Клюева, П.П. Пархоменко. - 352 с.

5. Гуляев В.А. Автоматизация наладки и диагностирования микроУВК / Гуляев В.А., Кудряшов В.И. М.: Энергоатомиздат. 1992. 256 с.

6. Williams T.W., Parker K.P. Design for testability a survey / IEEE Trans, on Comput. 1982. Vol. C-31. № 1. P 2-5.

7. Mc Clusskey E.J. Built-in self-test techniques / IEEE Design and Test of Computers. Aprl. 1985. V. 2(2). P.21-28.

8. Agarwal V.K. Easily testable PLAS // VISI Testing. Amsterdam: Norsh Holland, 1986. P. 65-94.

9. Паршина H.A. Синтез легкодиагностируемых комбинационных схем методом факторизации тупиковых ДНФ // Автоматика и вычислительная техника. 1980. - № 4.С.69-74.

10. Матросова А.Ю., Байда В.Д., Сафронов В.В. Синтез легкодиагностируемых автоматов // Методы и системы технической диагностики. 1980. - Вып. 1, С. 17-26.

11. Гессель M., Согомонян Е.С. Построение самотестируемых и самопроверяемых комбинационных устройств со слабонезависимыми выходами// АиТ,№8, 1992. С. 150-159.

12. Литиков И.П. Синтез самопроверяемых схем компактного диагностирования // АиТ, №3, 1991. С. 153-160.

13. Романкевич A.M., Стукач Н.Д. Об одном способе обеспечения лекготестируемости логических схем // АиТ, №3, 1991. С. 160-167.

14. Долинский М. Тенденция развития методов и средств автоматизации проектирования встроенных цифровых систем по материалам DATE'2003 // Компоненты и технологии, № 4. 2003. С. 166-171.

15. Лобанов В. Заметки о проектировании современных цифровых систем управления на отечественной элементной базе // CHIP NEWS, № 3, 2003. С.36-43.

16. Горяшко А.П. Синтез легкодиагностируемых схем вычислительных устройств. М.: Наука. -1987. - 288 с.

17. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой / Баранов С.И., Скляров В.А. М. Радио и связь, 1986. 272 с.

18. Угрюмов Е.П. Цифровая схемотехника: Учеб. пособие для вузов. СПб.: БХВ-Петербург, 2004. 800 с.

19. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.-467с.

20. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М.: Наука. Гл. ред. физ.-мат. лит., 1985. - 320с.

21. Беннеттс Р. Дж. Проектирование тестопригодных логических схем. М.: Радио и связь, 1990. - 176 с.

22. Курейчик В.М., Родзин С.И. Контролепригодное проектирование и самотестирование СБИС: проблемы и перспективы. М.:, Радио и связь, 1994. 176 с.

23. Литиков И.П. Кольцевое тестирование устройств. М.: Энергоатомиздат, 1990. 160 с.

24. Волынский М.Б. Классы проверяемых неисправностей программируемых логических матриц / Волынский М.Б., Новоселов В.Г. // Респ. межвед. научн.-техн. сб. М.: Приборостроение, 1983. Вып. 35.С.37- 41.

25. Волынский М.Б., Новоселов В.Г. Обнаружение и поиск неисправностей программируемых логических матриц / Волынский М.Б., Новоселов В.Г. // Микроэлектроника. 1983. Т.12. №4. С.306-312.

26. Бутаков Е.А. Диагностика программируемых логических матриц / Бутаков Е.А., Волынский М.Б., Новоселов В.Г. М.: Радио и связь. 1991. 160 с.

27. Закревский А.Д. К построению проверяющих тестов ПЛМ// Автоматика и вычислительная техника. 1982. №2. С. 73-76.

28. Люлькин А.Е. Синтез тестов для программируемых логических матриц / Люлькин А.Е., Павлова Т.Г.//Микроэлектроника. 1983. Т.12.№ 4.С. 299 305.

29. Соменци Ф. Обнаружение неисправностей в программируемых логических матрицах / Соменци Ф., Гай С. // ТИИЭР. 1986. Т. 74. № 5. С. 41-57.

30. Уткин A.A. Построение проверяющих тестов для программируемых логических матриц // Алгоритмы логического проектирования. Минск. 1983. С.83 -96.

31. Киносита К. Логическое проектирование СБИС / Киносита К., Асада К., Карацу О. М.: Мир. 1988. 309 с.

32. Fujiwara Н. A design of programmable logic arrays with universal tests / Fujiv/ara H., Kinoshita K. // IEEE Trans, on Comput. 1981. Vol. № 11. P. 823 -828.

33. Fujiwara H. A new PLA design for universal testability // IEEE Trans, on Comput. 1984. Vol. № 8. P. 745 750.

34. Усатенко C.T. Выполнение электрических схем по ЕСКД: Справочник / Усатенко С.Т., Коченюк Т.К., Терехова M.B. М.: Издательство стандартов, 1992. 316 с.

35. Логическое проектирование БИС / Под ред. В.А. Мищенко. М.: Радио и связь, 1984. 312 с.

36. Гольдман P.C. Техническая диагностика цифровых устройств / Гольдман P.C., Чипулис В.П. М.: Энергия, 1976. 224 с.

37. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2002. 224 с.

38. Акинина Ю.С. Анализ принципов построения и формализация модели легкодиагностируемых ПЛМ с перестраиваемым логическим базисом // Электроника 2003: Тез докл. 2-я Всероссийская н/т дистанционная конф.-Москва, МИЭТ, 2003.

39. Гаврилюк Д. Внутрисхемное программирование // Компоненты и технологии. 2003. № 8. С. 114-117.

40. Бохманн Д., Постхоф X "Двоичные динамические системы". М.: Энергоатомиздат, 1986.-400с.

41. Кофман А. "Введение в прикладную комбинаторику". Издательство "Наука", главная редакция физико-математической литературы, Москва 1975.-523с.

42. Акинина Ю.С., Тюрин C.B. Тютин М.В. Программный модуль «Преобразователь булевых полиномов» // ФАП ВНТИЦ № 50200400714 от 06.07.2004

43. Акинина Ю.С. Оптимистическая оценка сложности алгоритма восстановления совершенной дизъюнктивной нормальной формы // Техника машиностроения, №5, 2002. С.74-75.

44. Ахмед Н., Pao К.Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Радио и связь, 1980. - 248 с.

45. Садыхов Р.Х., Чеголин П.М., Шмерко В.П. Методы и средства обработки сигналов в дискретных базисах. Минск: Наука и техника, 1987. -296 с.

46. Тоценко В.Г. Алгоритмы технического диагностирования дискретных устройств. М.: Радио и связь, 1985. - 240 с.

47. Дискретная математика и математические вопросы кибернетики, т. 1 / Под ред. С. В. Яблонского и О. Б. Лупанова- М.: Наука, 1974. 312 с.

48. Баранов С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Л.: Энергия, 1979. - 232 с.

49. Лысиков Б. Н. Арифметические и логические основы цифровых автоматов. Минск: Высшая школа, 1980. - 230 с.

50. Автоматизация проектирования БИС. В 6 кн.: Практ. пособие. Кн. 2. П. В. Савельев, В. В. Коняхин Функционально-логическое проектирование БИС // Под ред. Г. Г. Казанова- М.: Высшая школа., 1990. 156 с.

51. Новожилов О.П. Основы цифровой техники / Учебное пособие. М.: ИП РадиоСофт, 2004. - 528 с.

52. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.-416 с.

53. Закревский А. Д. Комбинаторика логического проектирования. // Автоматика и вычислительная техника. 1990. №2. - с. 68 - 79.

54. Уткин А. А. Экспериментальное исследование алгоритмов "выполнимость" // Автоматика и вычислительная техника. 1990. - №6. - с. 66-74.

55. Петрович Т.Н., Размахнин М.К. Системы связи с шумоподобными сигналами. М.: Сов. радио, 1969 - 232 с.

56. Лезин Ю.С. Оптимальные фильтры и накопители импульсных сигналов, М.: Сов. радио, 1963 - 319 с.

57. Корн Г.А. Моделирование случайных процессов на аналоговых и аналогово-цифровых машинах. М.: Мир 1968 - 315 с.

58. Алексеев А.И., Шереметьев А.Г., Тузов Г.И., Глазов Б.И. Теория и применение псевдослучайных сигналов. М.: Наука, 1969 - 368 с.

59. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля/ Под ред. П.М. Чеголина. Мн.: Наука и техника, 1986. - 200 с.

60. Тюрин C.B. Многоканальный генератор коррелированных М-последовательностей // Техника машиностроения, N4(38), 2002. — с. 77-78.

61. Акинина Ю.С., Тюрин C.B. Об одном подходе к формализации понятий «необходимость» и «достаточность» функциональных тестов ОЗУ // Вестник ВГТУ, Вып. 8.1, Воронеж, 2001. С.50-52.

62. Акинина Ю.С., Панявин В.В., Тюрин C.B. Об одном подходе к сравнительной оценке эффективности контрольно-диагностических тестов для цифровых модулей ОЗУ // Вестник ВГТУ, Вып. 8.2, Воронеж, 2002.

63. Владимирский М.М. Тестирование ОЗУ с помощью псевдослучайной двоичной последовательности // Микропроцессорные средства и системы, №4, 1990.-С.91-92

64. Свердлик М.Б. Оптимальные дискретные сигналы. М.: Сов. радио, 1975-200 с.

65. Самсонов Б.Б., Плохов Е.М., Филоненков A.M. Компьютерная математика (основания информатики). Ростов-на-Дону: «Феникс», 2002.-512 с.

66. Бобнев М.П. Генерирование случайных сигналов. Изд. 2-е перераб. и доп. М.: Энергия, 1971.- 240 с .

67. Тюрин C.B. Многоканальный генератор коррелированных М-последовательностей // Техника машиностроения, N4(38), 2002. с. 77-78

68. Акинина Ю.С., Подвальный C.JT., Тюрин C.B. Метод нахождения суммы произвольной совокупности М-последовательностей из одного класса // Информационные технологии моделирования и управления, 3(21), 2005. -Воронеж, Изд-во «научная книга». С. 358- 363.

69. Богданов В.В., Лупиков B.C. Устройство контроля генератора М-последовательностей. А.С. № 1278850, кл. G06, F11/00 // Б. И. 1988. №47.

70. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

71. Акинина Ю.С., Тюрин C.B. Тютин М.В. Программный модуль «Преобразователь булевых полиномов» // ФАП ВНТИЦ № 50200400714 от 06.07.2004

72. Акинина Ю.С., Моргунов Ю.М., Тюрин C.B. Программный модуль «Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ» // ФАП ВНТИЦ № 50200400701 от 06.07.2004

73. Акинина Ю.С., Тюрин C.B. Тютин М.В. Программа «Эмулятор программируемой логической матрицы» // ФАП ВНТИЦ № 50200400711 от от 06.07.2004

74. Микропроцессоры: системы программирования и отладки / В.А. Мясников, М.Б. Игнатьев, А.А. Кочкин, ЮЕ. Шейнин; Под ред. В.А. Мясникова, М.Б. Игнатьева. М.: Энергоатомиздат, 1985. - 272 с.

75. Корячко В.П. Конструирование микропроцессорных систем контроля радиоэлектронной аппаратуры. -М.: Радио и связь, 1987. 160 с.

76. Уильяме Г.Б. Отладка микропроцессорных систем. М.: Энергоатомиздат, 1988.-253 с.

77. Разевинг В.Д. Применение программ P-CAD и Pspice для схемотехнического моделирования на ПЭВМ: В 4 выпусках. М.: Высш. школа, 1989.

78. Разевинг В.Д. Система схемотехнического моделирования и проектирования печатных плат Design Center (PSpice). M.: CK Пресс, 1996.

79. Разевинг В.Д. Система схемотехнического моделирования Micro-Cap V. M.: «СОЛОН», 1997. - 280 с.

80. Разевинг В.Д. Универсальная программа проектирования электронных устройств APLAC // PC Week / Re, 1997, №26. С. 45-46.

81. Панфилов Д.И., Иванов B.C., Чепурин И.Н. Элетротехника и электроника в экспериментах и упражнениях: Практикум по Electronics Workbench: в 2 т./ Под общей ред. Д.И. Панфилова. М.: ДО ДЕКА, 1999.

82. Карлащук В.И. Электронная лаборатория на IBM PC. Лабораторный практикум на базе Electronics Workbench и MATLAB. Издание 5-е. М.: СОЛОН-Пресс, 2004. - 800с.

83. Кардашов Г.А. Цифровая электроника на персональном компьютере. Electronics Workbench и Micro-Cap.-M.: Горячая линия-Телеком, 2003.-311 с.1. УТВЕРЖДАЮ»1. АКТоб использовании результатов кандидатской диссертации Акининой Ю.С.

84. Разработка моделей и метода инженерного синтеза самотестирующихсялогических преобразователей с перестраиваемым элементным базисом"

85. Указанные результаты включены в учебный процесс на основании решения кафедры ABC, протокол №5 от « 24 » января 2006 г.1. Зав. кафедрой ABC1. Начальник УМУ

86. C.JI. Подвальный А.И. Болдырев1. ИКАП501. Sû£oy7839 Тип ЭВМ7902 Тип и версия ОС5715 Инструментальное ПО7848 Оперативная память1.M PC/AT1. MS Win 9х/2000/ХР1. MS VC7.155007965 Разновидность ПС Программный модуль46

87. Программа 64 Пакет программ 19 Комплект программ7884 Объем программы

88. Международный институт компьютерных технологий2358 Сокращенное наименование организации 2655 Адрес организации1. МИКТ

89. Сведения об организации-разработчике2988 Телефон 3087 Телефакс 2781 Город2187 Наименование организации6183 Авторы (разработчики ПС)

90. Акинина Ю.С., Моргунов Ю.В., Тюрин С.В.9045 Наименование программы

91. Программный модуль ""Расчет и генерация эталонных последовательностей для диагностирования неисправностей специализированных ПЛМ"9117 Реферат

92. В результате разработки создан программный модуль, обеспечивающий реализацию требований, поставленных перед авторами.5436в

93. Фамилия, инициалы Должность Учсгегкнь,зг^Е^ ^^доЩ^Ш?^

94. Руководит, организац. 6111 Кравец О.Я. 6311 Проректор 6210 д.т.ь щт «Р ^ЩШшЩ^. у

95. Библиотека программ 82 Программная система 91 Программный комплекс 28 Информационная структура 37 Прочее5679 Код программы по ЕСПД26499161.001421288