Математические модели и методы построения контролепригодных схем для ранних стадий проектирования цифровых систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГБ ОН 1 1 ШР 1355

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

Тимошкин Андрей Иванович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ 'Л МЕТОДЫ ПОСТРОЕНИЯ КОНТРШ1ЕПРИГОДНЫХ СХЕМ ДЛЯ РАННИХ СТАДИЙ ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ СИСТЕМ

Специальность: 01. 01.09. - Математическая кибернетика.

Авторе ф.е р а т диссертации на соискание ученой степени кандидата физика математических наук

С а р. а.т с в

- 1996

Диссертационная работа выполнена в Саратовском государственном университете им. К. Г- Чернышевского.

Научный руководитель. - доктор технических наук,

член - корреспондент РАЕН, профессор В.А. Твердохлебов

Официальные оппоненты - доктор технических наук,

профессор А.А. Сытник - кандидат физико - математических наук, доцект В. В. Печенки1

Ведущая организация - Институт проблем управления

. РАН

Зашита диссертации состоится ' 1 \ ддег.

час., на заседании .Диссертационного Совета К Об: 74.04 по присуждению ученой степени кандидата физико - матг матических наук по специальности 01.01.09 - Математическая "кибернетика: при Саратовском государственном университете иг Н.Г\ .Чернышевского по.адресу: 410026, г. Саратов, ул. Астрг ханская, 83, Саратовский государственный, университет. Мех; нико - математический факультет.

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

Автореферат разослан с^Ф^/у&са996 г.

Ученый секретарь Диссертационного Совета кандидат физико - математических наук, доцент П.Ф. Недорезс

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

.Актуальность темы, разработка и использование мате-атйческих моделей сложных технических систол, а такие метс-ов анализа, синтеза и распознавания составляют теорётичес-ую основу приложения математики в техническом диагностиро-ании, теории упрааления;• проектировании и т.п.

Развитие технической базы,- изменение требований к ехническим "системам и условий их эксплуатации приводят к огниккозенню новых задач технического диагностирования. Ма^ ематический аппарат стал необходимым средством тестирова-ия, разработки койт'релепрягрдных схем и повышения . контро-епригодности технических систем.

3' созданий математического аппарата технического й^ностировйния, в направлении, когорсму соответствует Teil диссертации работает большое число отечественных и зару-ежных ученых, в той числе ■ • С. В. Яблонский, 3. Б. Кудрявцев, .П. Пархоменко, В.Л. Казначеев, Ё.С. Согошнян. S.A. Твер-зхлзбвВ, Д. В. Сперанский, А. Д. Фридман, X: Постхоф, Д». П. эйес, р. Убар. с.м. Редяи, гл. Шульц и др.

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

1) организация .контрольных точек и LSS0 - цепей, в зтовых проектах схем, а такяз их модификация

2) обеспечение контролепригодности на ранних этапах '

проектирования ( синтез контролепригодных схем ).

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

Среди различных концепций второго подхода видне место занимает концепция синтеза С - контролепригодных схе ( т. е. схем, обладающих провсрящш тестом постоянной длинь не зависящей от их сложности ). Данную концепцию порода/ работы А.. Л- Фридмана а Дж. П. Хейеса . В дальнейшей она бш развита в работах К. К. QanyM и С.М. Редди •( Salидa \ -К., Reddy S.И,- On.minimally testable logic networks // IEEE Trans, on computers, 1974, N 5, pp. 552 - 554 ), X. Элху! А. Вергиса и Л. Кинкей ( Elhuni Н., Vergis A., Kinney L. С testability of two- dimensional iterative arrays // IEEi Trans, on cbmput. aided design, 1986, vol. CAD - 5; N ■ pp. 573 - 581 )., Ф. Ломбарди и В. К. Хуанга ( Lombardi' F Huang W.K. Fault detection and design complexity in C- tes .able VLSI arrays // IEEE Trans, on computers, 1990, v.3 N 12, pp. 1477 - 1481; Huang-W.K.. Lombardi F. On the con tant diagnosability of baseline interconnection networks IEEE Trans, on computers, 1990, v. 39, К 12, pp. 1485- 148

3 работах С. швнга и 0. Джейни ( Shcng С.С., Jeuny O.S. Testability crtarcenen: in digital system design // IEEE Intercom Cor.:.. New Ycrk, 1375 ), А.П. Горяшко ( Горяшко А.П. Некоторые результаты теории синтеза легко тестируемых схем // Изв. АН СССР. Техническая кибернетика. - 1982. - N 2. --с. :3S - 15С ;, В. И. Пезченкс Í Шевченко В. И. Синтез схем с минимальной трудоемкостью тестирования // VII Всесоюзн. конф. " Проблемы теоретической кибернетики. " Тез. докл. Ч. 1, Иркутск, î935. - с. 202 - 203- ). В. А. Варданяна ( Варданян 3. А. С5 одном методе синтеза легко тестируемых схем // Автоматика и телемеханика^ -1587. - N 7.-е. 136 - 139 ) рассматривается задача построения схем, обладающих проверяющим тестом длины 2 относительно константных неисправностей на сигнальных линиях. Однако эти исследователи ограничиваются рассмотрением ряда достаточных условий существования проверяющего теста длины. 2 для функциональных элементов и логических схем. Методы синтеза логических схем, обладающих про-оеряпцим тестом длины 2 относительно константных неисправностей на сигнальных линиях, у отмеченных исследователей базируются на нежелательной для практики процедуре диагностического расширения входных и выходных алфавитов..

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

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

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

Методы и средства исследований. При разработке пред' латаемых моделей и методов.автор использовал математические аппарат теории функциональных систем, теории множеств и отно шений, алгебраических систем, теории автоматов, а также пето ды теории графов.

. Научная новизна результатов. ■ Предложены новые матема тические модели ксктролспригодных схем ; математические, моде ли 2 - проверяемых схем, реализующих линейные булевы Функции существенным образом, зависящие от всех своих переменных, ма тематические модели 2 - проверяемых, двухканальных древовидны схем. Предложен •метод построения . контролепригодной функцио нально - логической схемы п - разрядного 1ь<°° ) сумма тора. Разработан новый метод построения контролепригодных ■двухканальных древовидных. схем. Разработаны математические модели 2 - проверяемых ЙБ - триггеров двухканальной логики Предложены способы построения 2 - проверяемых асинхронных ав томатов Мили и Мура. В работе развивается системный подход

к проблеме разработки эффективных математических моделей и методов синтеза контролепригодных схем.

, Практическая и теоретическая ценность. Полученные результаты будут использованы в дальнейших исследованиях по теории синтеза контролепрйгодных' и самопроверяемых схем из Функциональных элементов и в учебного процессе. Возможными областями применения предлагаемых математических моделей и методов построения контролепригодных логических схем являются : 1) разработка базовых матричных кристаллов нового поколения 2! разработка базспасных и легко диагностируемых цифровых систем различного назначения.

Апробация работы и публикации. Результаты, представленные в диссертации, докладывались и обсуждались на научных семинарах в Днепропетровской СКБ автоматизации проектирования ( 1990 - 1995 г.г.), з Таганрогском НИИ Многопроцессорных вычислительных систем ( 1995. г.), в Ростовском НИИ Радиосвязи ( 1995 г.), в Ростовском государственном университете ( 1995 г.) и- з Саратовском государственном университете ( 1994 - 1995 г. г.).

•По теме диссертации опубликовано в работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы ("109 наименований ) и 2-х приложений. Общий обьем диссертации - 184 страницы машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ.'

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

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

Б £ 1.2 определены необходимые и достаточные условия существования проверяющего теста длины 2 ( или 2 - проверяемости ) для одновыходных функциональных элементов относительно одиночных константных неисправностей входов и выхода.

В ^1.3 определены необходимые и достаточные условия, существования проверяющего теста длины 2 для функциональных элементов двухканальной логики относительно одиночных константных неисправностей на их входах и выходах.

В рассматривается множество функциональных

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

Л® (141)

При этом булевы функции £существенным образом зависят от всех своих А аргументов.

Теорема 1.4.1 Функциональный т. - выходной элемент

/- из ^ обладает проверяющим тестом длины 2 относительно одиночных константных.неисправностей на входах, и выходах тогда и только тогда, когда существуют входные вектора ^ =

(fif'-rfi.) . и ■ гле для кая-лого /е Jif^fe. {й, i} . удовлетворяющие.

следующим условиям :' л . ■

¿ln-,j£)D > oi

(1.4.3)

Б § 1.5 определены необходимые и достаточные, условия существования проверяющего теста длины 2 для одновыходных функциональных элементов относительно кратных константных неисправностей на входах и выходе.

Б § 1. 6 определены необходимые и достаточные условия существования проверяющего теста длины 2 для функциональных элементов из <-5 относительно кратных константных неисправностей на входах и выходах.

В §1.7 рассмотрен класс J) булевых функций, обладающих проверяющими тестами длины 2 относительно одиночных замен входных и выходной переменных константами 0 и 1.

Определение 1.7.1 Пару двоичных векторов ¿¿—(ft*?

"'ffh.) и "V./'Ji ) ' обнаРУХ11ваю!511Х tv&uz

одиночные замену любых входных и выходной переменных булевой функции •«/ ) константами 0 и 1, назовем

парой £"<5 - векторов функции ^п-)

Булева функция , если £ обладает хотя бы од-

ной парой - векторов.

Теорема 1.7.1 Згыыкание|^У| класса ^ относительно операции суперпозиции совпадает со шожеством всех булевых функций :

[1)1

\

Определение .1.7.2 Бесповторной - суперпозицией /ж,4«; из класса Т) назо-

вей такуя - бесповторную суперпозиций £ ? £ £ Л Функций 5 из ¿0 ' при К0Г°Р°Й сРеДи пар -векто-роз функций найдутся пары {¿^

где е *е -г^ >

' Теорема 1-7-2 Класс Д) замкнут относительно операции бесповтарнойТ.2 - суперпозиции :

Теорема 1.7.'3 Класс 1Г) замкнут относительно опера ции бесповторной суперпозиции -:

Б классе Д) выделим подкласс Д) такой, что^£ 'Т) если произвольная пара противоположных векторов для функции £ является парий ее Г.® - векторов. Рассмотрим вопрос о соотношении этого подкласса с классами Поста.

Теорема 3.7.4 ПодклассД)*" классасовпадает с

классом ¿, . о

Для данного подкласса справедлива■также следующая

теорема.

Теорема 1.7.5 Любая замена кратности г=£¡¿+1 , где

к = входных и выходной переменных- функции

•Х^г-у-Хл.) изД)* константами 0 и 1 может быть обнаружена

любой парой сЪтд - векторов.

Пусть имеется линейная булева функция £(х^у.^х^

из!_ \ ¿, { где - класс всех линейных функций ), сущест-/ £

венным образом зависящая от всех своих аргументов. Тогда , имеет место

Теорема 1.7.6 Если существенным образом зависящая от всех своих аргументов булева функция £ Ь{ \ , - то минимальная длина теста, обнаруживающего любые одиночные замены входных и выходной переменных функции - константами 0 и 1, равна 3. В § 1.8 предложен алгоритм нахождения всех пар^ -векторов заданной булевой функции и оценена его временная сложность.

В § 1.9 производится оценка снизу мощности класса ^Г) на основе построения системы непересекающихся подмножеств из класса |).

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

Обозначим через множество всех древовидных логических схем из одновыходных функциональных элементов таксе, что любая схема Э содержит хотя бы один функциональ-

ный элемент, 'причем любой функциональный элемент /* схемы 5 £ £ имеет существенные и только существенные входы. Необходимое и достаточное условие существования проверявшего теста длины 2 для схемы 5 из О относительно одиночных константных неисправностей на ее сигнальных линиях дает следующая теорема :

Теорема 2.2.1 Схема- 5 из (э обладает проверяющим . г

тестом длины 2 относительно одиночных константных неисправностей на сигнальных линиях тогда и только тогда, когда

(2.2.18)

где £ - множество всех функциональных элементов схемы 5 . ^ - функция, реализуемая функциональным элементом Р .

В § 2.3 определено необходимое и достаточное условие существования проверяющего теста длины 2 для любой древовидной двухканальной комбинационной схемы относительно одиночных константных неисправностей на сигнальных линиях.

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

ных константных неисправностей на сигнальных линиях.

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

В ^ 3.2 предложены математические модели обладающих проверяющим'тестой длины .2 древовидных схем, реализующих линейные булевы функции. Приведен алгоритм построения описываемых данными моделями древовидных схем минимальной глубины в базисе {ц/^Ф^е,х]т

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

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

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

тами длины 2 относительно одиночных константных .неисправностей на их входах и'выходах. .На основе этих моделей построены структурно-логические модели древовидных двухкачальных схем, обладающих проверяющим тестом длины 2 относительно одиночных• константных неисправностей на сигнальных линиях, проанализированы и;: диагностические .возможности.

В §3.6 рассмотрен метод построения контролепригод-ных дву-хканальных древовидных схем, сложность которых незначительно превышает сложность обычных двухкгнальных схем,

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

Четвертая глава посвящена построению-математических моделей контролепригодных последовательностных схем.

В ^ 4.1 осуществляется формальная постановка задачи существования конечных детерминированных автоматов,, обладающих проверяющим тестом длины 2 относительно одиночных константных неисправностей на полюсах, соответствующих входным, внутренним и выходным переменным систем канонических уравнений данных автоматов.

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

- 1э -

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

В § 4.3 сформулированы и доказаны теоремы о необходимых и достаточных условиях существования проверяющих тестов длины 2 для асинхронных автоматов Мили и Мура относительно одиночных константных неисправностей, соответствующих заменам любых переменных систем канонических уравнений этих автоматов константами 0 и 1.

В § 4. 4 рассмотрены математические модели ЙБ - триггеров двухканальной логики, обладающих проверяющим тестом длины 2 относительно одиночных константных неисправностей на их входах и выходах, проанализированы их диагностические возможности.

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

^ дн)= я ан)я(ш)у5(^о $(¿+0 V

(4.4.1)

Входные вектора ( Я = ¿ = 0, 5 = 0> 5 = I ) и £ =г 5 = I, 5 = 0 ) устанавливают этот триггер

соответственно в нулевое (г. —0.2, — £ ) » единичное 2 —

А

А

z = 0) состояния. Входной вектор (fc^flj R. = if S = 5 = i ) ■ сохраняет предыдущее состояние триггера.

3 заключении суммируются полученные результаты..

Список опубликованных по теме диссертации работ.

1. Тимошин А. И. Об одном классе комбинационных схем из гп. - выходных функциональных элементов, проверяемых двумя тестовыми наборами // Изв. АН Эстонии Физ., Матем. - 1992.- т. 41, К" 2. - с. 118 - 124.

2. Тимоекин к.'А. О некоторых классах структурных автоматов, тестируемых двумя - входными наборами // Изв. АН Эстонии. Физ., Матем. - 1992. - т. 41, N0 3. - с. 199 - 20в.

3. -Гимошкин A.M. Тестопрйгодная реализация функций двухканагшной логики - // Радиопромышленность. - 1994. - № 2. - с. 43 - 44.

4. Тимсшкин А. И. О реализации некоторых функций двух-канальной логики 2 - проверяемыми древовидными схемами // Радиопромышленность. - 1994^ - N^'i. - с. 52 - 58.

5.- Тимошин-А: И: 0 реализации линейных булевых функций 2 - проверяемыми древовидными схемами // Радиопромышленность. - 1995. - 3/4. - с. 90 - 95.

6. Тимошкин А. И. Способ реализации 2 - проверяемых асинхронных RS - триггеров двухканзльной логики // Радиопро-

мышленность. - 1995. - Nfl3/4. - С. 96.-101.

Заказ 50' Подписано к печати S~. 03.36* Объем 1 печ. лист. Тираж 100 экз. Типография -издательства. СГУ