автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Реализация функций на полурешетках переключательными схемами

Томский государственный университет

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

РЕАЛИЗАЦИЯ ФУНКЦИЙ НА ПОЛУРЕШЕТКАХ ПЕРЕКЛЮЧАТЕЛЬНЫМИ СХЕМАМИ

Специальность 05.13.01 — системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

ТОМСК-2006

УДК 519.7

Работа выполнена в Томском государственном университете

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

доктор технических наук,

профессор Агибалов Геннадий Петрович

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

доктор физико-математических наук, профессор Шоломов Лев Абрамович

кандидат физико-математических наук, дтн, профессор Евтушенко Нина Владимировна

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

Саратовский государственный университет

Защита состоится 28 сентября 2006 г. в 10.30 на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина - 36.

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

Автореферат разослан июля 2006 г.

Ученый секретарь диссертационного совета,

д.т.н., профессор Смагин В. И.

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

Актуальность проблемы. Традиционно методы логического проектирования дискретных управляющих систем, или дискретных автоматов, базируются на таком разделе дискретной математики, как конечно-значная логика. Её средства позволяют описывать статическое поведение системы (при фиксированном входном состоянии), однако недостаточны для описания динамического поведения (при асинхронном изменении компонент входного состояния). В монографии [1] было показано, что динамическое поведение дискретного автомата может быть адекватно и с заданной точностью описано средствами полурешёточно упорядоченных алгебр. Для этого множество состояний в автомате представляется как конечная верхняя полурешётка, т. е. частично упорядоченное множество, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка в полурешётке интерпретируется как отношение сравнения состояний по степени их неопределённости, а сумма состояний а + Ь моделирует промежуточное состояние, возникающее в процессе асинхронного изменения а на Ь. Задача синтеза дискретного автомата, обладающего заданным динамическим поведением, сводится к синтезу схемы в некотором базисе, реализующей функцию на полурешётках, описывающую это поведение. В связи с этим представляет научный и практический интерес разработка методов схемной реализации функций на полурешётках.

Первые результаты в этом направлении получены в работе [1], где описан метод реализации функции на полурешётке подмножеств трёхэлементного множества схемой в произвольном базисе и сформулированы необходимые и достаточные условия полноты базиса для случая однокаскадных параллельно-последовательных схем. При проектировании реальных дискретных управляющих систем на базе БИС и СБИС чаще всего используется элементный Я^базис, состоящий из элементов двух типов — резистора, представляющего собой двухполюсник с постоянной конечной проводимостью (обозначаемой X) между по-

люсами, и переключателей, являющихся многополюсниками, в которых проводимости между полюсами принимают значения в полурешётке Р2 всех непустых подмножеств множества {0, 1} и являются функциями от состояний полюсов элемента. К сожалению, ни один из ЯЗ-базисов не удовлетворяет критериям полноты из [1], поэтому актуальной становится проблема реализуемости функций на полурешётках схемами в заданном (неполном) КЗ-базисе. Решение этой проблемы предполагает формулировку критериев (необходимых и достаточных условий) реализуемости, т. е. существования схемы в ИБ-базисе, реализующей заданную функцию, и методов реализации - синтеза такой схемы, если она существует.

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

Цель работы. Настоящая работа посвящена выяснению условий реализуемости и разработке методов реализации функций на полурешётках переключательными схемами, в которых проводимости цепей принимают значения в полурешётке Р3 всех непустых подмножеств множества {О, X, 1}, а состояния узлов — значения в полурешётке (Р3)2. Ставятся следующие задачи: (1) установить необходимые и достаточные условия реализуемости функций на полурешётках схемами в произвольном КЬ-базисе; (2) разработать методы синтеза в ЯБ-базисах

схем, реализующих функции на полурешётках; (3) формализовать понятие состязаний для функций на полурешётках и решить задачи (1), (2) для схем, обладающих свойством функциональной устойчивости к состязаниям на заданном множестве переходов.

Научная новизна и выносимые на защиту положения.

1. Для заданных функции на полурешётке/и произвольного элементного базиса В введено бинарное отношение Г/^, состоящее из всех пар (Дв, ЛаУ)> где а в — набор значений всевозможных функций элементов в В от входных переменных схемы на наборе а их значений, и показано, что квазимонотонность этого отношения является необходимым условием реализуемости функции / в базисе В.

2. Введено понятие (5, а)-разделимости пары (а, Ъ) элементов полурешётки множеством функций, означающее наличие в множестве функции, принимающей значения 5 и с на элементах а и Ь соответственно, и доказано, что необходимым и достаточным условием реализуемости функции / однокас-кадной схемой в ЯБ-базисе является (1, 0)-разделимость множеством базисных функций некоторых однозначно вычисляемых пар элементов из области определения функции/.

3. Введено отношение у — расширение отношения сравнения проводимостей по значению на подмножества проводимостей, и установлено, что необходимым и достаточным условием реализуемости функции f двухкаскадной схемой в Я8-базисе В является квазимонотонность отношения Г/в и наличие в В элемента, функция которого не сохраняет у.

4. Доказано, что классы функций на полурешётках, реализуемых в К^-базисе параллельно-последовательными схемами и схемами с мостиковыми соединениями, совпадают.

5. Предложены методы реализации функций на полурешётках и их систем переключательными схемами в ЯБ-базисах.

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

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

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

Методы исследования представляют собой сочетание методов дискретной математики, теории управляющих систем и общей алгебры (теории конечных полурешёток).

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

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

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

Апробация работы. Результаты диссертации обсуждались на совместных научных семинарах кафедр защиты информации и криптографии, программирования, информационных технологий в исследовании дискретных структур Томского государственного университета, докладывались на XV Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, 2004 г.), XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), Всероссийских конференциях «Новые информационные технологии в исследовании сложных структур» (Томск, 2000 и 2002 гг., Иркутск, 2004 г.), Сибирских школах-семинарах «Компьютерная безопасность и криптография» (Томск, 2003 и 2005 гг.).

Публикации. Основные результаты диссертации опубликованы в работах [1-13].

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и библиографии, включающей 64 наименования; её объём — 102 стр.

СОДЕРЖАНИЕ РАБОТЫ Глава 1. Состояние проблемы и основные понятия

В разделе 1.1 обсуждается состояние проблемы синтеза схем с заданным динамическим поведением.

Раздел 1.2 посвящен функциям на полурешётках. Пусть множество L вместе с определённым на нём отношением порядка < является конечной верхней полурешёткой. Точная нижняя и точная верхняя грани в полурешётке обозначаются ¡nf и sup соответственно. Множество точек (минимальных элементов) полурешётки L обозначается m(L); множество точек, содержащихся в элементе xeL — т(х). Будем рассматривать частичные функции на полурешётке /: U/ —> L, где

UjC.lT — область определения функции / Говорят, что функция % есть доопределение функции /, если С^с и =Ла) для любого ае С//. Говорят, что функция gреализует функцию/ и птауг g<f, если [//С иг и ^а) 2Да) для любого ае Ц/. Аналогично определяется реализация функцией отношения на полурешётках. Всюду определённая функция на полурешётке £ называется монотонной, если она сохраняет отношение порядка на Ь. Частичную функцию будем называть монотонной, если существует её всюду определённое монотонное доопределение. Функция называется квазимонотонной, если существует реализующая её монотонная функция.

В разделе 1.3 строго определяются понятия переключательных элементов, сетей, схем и их функций. Рассматриваются схемы с двухполюсным источником питания, проводимости в которых принимают значения из множества Р3= {О, 1, X}, где 0 — нулевая, 1 — бесконечная и X — конечная (резистивная) проводимости. Для описания процесса асинхронного изменения проводимостей и состояний строятся полурешётка проводимостей Р3= {О, 1,Х, 0', 1', X', Е} всех непустых подмножеств множества Р3 и полурешётка состояний 7 = (/>3)2. Здесь 0={0}, 1 = {1}, Х= {X}, 0'= {1,Х}, 1'= {0,Х}, Х'= {0, 1}, Е= {0,1,X}; операция сложения в Ръ есть объединение множеств, а в 1 — покомпонентное сложение значений из Р3. Динамическое поведение комбинационной переключательной схемы с п входами и т выходами описывается функцией на полурешётке состояний <р: Г-+Г.

Переключательный элемент е(хи ...,хк,а,Ь) есть пара (Х,/е), где Х= {.*1,..Хк} — множество управляющих полюсов элемента,/^ ^Рз — монотонная функция проводимости между исполнительными полюсами а и Ь, зависящая от состояний управляющих полюсов; для остальных пар полюсов проводимости между ними тождественно равны 0.

Переключательная сеть М(хи ...,хп,а,Ь) в базисе В есть пара (Х,0), где Х= {*!, ..., *„} - множество управляющих полюсов сети, С — параллельно-последовательный граф с двумя выделенными вершинами а и Ъ, каждому ребру которого сопоставлен переключательный элемент (Хь/!)еВ, ^с! Функция проводимости > Я3 сети N определяется следующим индуктивным обра-

зом:

а) если в содержит одно ребро (а, А), то /ц где е — соответствующий этому ребру элемент;

б) если в есть параллельное соединение графов С\ и С2, то /м = /Л,| V , где

/л,1, - функции сетей (Д б,) и {X, 02) соответственно, V — операция

дизъюнкции проводимостей;

в) если б есть последовательное соединение графов С?! и Сг2, то = л /у,

где а — операция конъюнкции проводимостей.

Однокаскадная схема С(х,, ...,х„,у) в базисе В есть пара сетей в том же базисе (Л'оСхъ ...,х„,у, СЫО), Лг,(дг|.....хп, УОО,у)), где лгь ...,х„ — входные полюсы

схемы, у — выходной полюс, (7ЛГ/), КО£> — полюсы источника питания. Функция состояний <рс\ I схемы С определяется как пара функций сетей <Рс =(/*„>/*,)•

Двухкаскадная схема С(хъ ...,х„,у) есть совокупность однокаскадных схем (С,(*„ ... У}), Ск(хи ...

Ук)> С*+1(х,, ... Уъ ■■;Ук,у)), где Си .... Ск -схемы первого уровня, Ск+] — схема второго уровня с управляющими полюсами Х[, хп, у и ...,ук. Функция состояний схемы С определяется как суперпозиция

У = = <Рсм 0Ч'-'хп><РС1 (*1.....*„))•

г-Каскадная схема определяется аналогично, если С\, ..., Ск суть (г—1)-каскадные схемы. Поскольку (? — 1)-каскадную схему можно рассматривать как частный случай ¿-каскадной (при к — 0), то это определение допускает в качестве

управляющих полюсов схемы С*+] выходы схем первого, второго, ..., (г— 1)-го уровней.

Будем говорить, что переключательная сеть (схема) N реализует функцию проводимости (состояний) если для функции сети (схемы) /у имеет место

/ Назовём функцию проводимости$хх.....х„) \-реализуемой в базисе В, если

существует сеть Щхх, ...,х„,а,Ь) в том же базисе, реализующая/. Назовём её к-реализуемой в базисе В, если существуют функция проводимости g(x^, ...,х„, У\,

Ут) И функции состояний <рх(хх,...,х„), ..., <рт(хи ...,хп), такие, что X 1-реализуема в базисе В, ..., <р„ реализуемы (А— 1)-каскадными схемами в этом базисе, и я(Х|, ...,х„, <р\{хъ ...,х„),..., <рт(х,, ..., х„)) </ Наконец, назовём/реализуемой, если она ^-реализуема для некоторого к> 1.

Функции на полурешётках реальных физических элементов монотонны, и суперпозиция монотонных функций есть функция монотонная, следовательно, функции переключательных схем монотонны. Поэтому физически реализуемы только квазимонотонные функции.

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

Глава 2. Условия реализуемости функций на полурешётках

В разделе 2.1 устанавливается необходимое условие реализуемости функций проводимости и состояний в произвольном базисе.

Пусть заданы функция/: С/С Г—> со значениями в полурешётке ¿6 {/, Рз} и базис переключательных элементов В = {(Хх>/{), где \Х,\ = к{ для » = 1, ...,5. Для каждого элемента е, = (Х„/1)еВ рассмотрим всевозможные отображения /I/.{1.....А;} —» {1.....п} множества управляющих полюсов элемента в

множество номеров аргументов ДС], ..., х„ функции/. Их количество равно = пк>.

Каждой паре (е„ //,), i = 1, = 1, ..., ¿„ сопоставим функцию : > Я3

такую, что (*],..., х„) = Построим бинарное отношение

Гу_дс (Рз/хЛ, где г = + ¿2+."+ для каждого набора аезапишем вектор ая = (Хц,...,*,^ ) размерности г, где х,/= /¡''^ (а), и положим

(ав,Да))еГ/в. Всюду далее пусть Ов= {/(<"у): ' = 1, я, У = 1.....',}■ Будем

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

Теорема 2.1. Если функция/ С^-с; Г—> Ь реализуема в базисе В, то отношение Г/в квазимонотонно.

В разделе 2.2 устанавливаются необходимые и достаточные условия реализуемости однокаскадными и двухкаскадными схемами функций со значениями в полурешётке (Р2)2. Пусть 5, сте Р3. Пару наборов (а,Ь), где а, ЬеГ, назовём (5, а)-разделимой множеством функций проводимости (7, если существует функция geG, что g(b)) = (5, ст). Обозначим Е2 класс переключательных

элементов, функции проводимости которых принимают значения в полурешётке Р2.

Теорема 2.2. Функция состояний <р: £/,,—» (А)2, <Р — С/о,У!), реализуется одно-каскадной схемой в базисе В с Е2, если и только если для любой функции /е {[о,/\} выполняется условие: для любых а, Ье и9 таких, что (Да),ДА)) = (1, 0), пара (а, Ь) является (1, 0)-разделимой множеством Ов.

Введём в рассмотрение бинарное отношение у на /*3 как -¡1 = {(1,0), (1,Х), (1,1'), (Х,0), С0',0».

Теорема 2.3. Функция состояний <р\ с Г—> ( Р2)2, не реализуемая однокас-кадной схемой, реализуема в ЯЭ-базисе если и только если отношение

Г9в квазимонотонно и множество В содержит элемент, не сохраняющий отношения у; в этом случае <р реализуется двухкаскадной схемой в данном базисе.

Теорема 2.4. Функция состояний <pr. U^—> (Р2)1, не реализуемая однокаскад-ной схемой, реализуема в базисе В с. Е2> если и только если отношение Г^в квазимонотонно и множество В содержит элемент е — ({*ь ..., xk},fe), ограничение функции fe которого на множестве ((/у2)* не сохраняет отношения у.

В разделе 2.3 устанавливаются необходимые и достаточные условия реализуемости однокаскадными и двухкаскадными схемами функций со значениями в полурешётке /.

Теорема 2.5. Функция состояний <р: U9 ci Z1—> I, <р = (fa,f\), реализуема одно-каскадной схемой в RS-базисе Bkj{R], если и только если для любой функции /е{/о,/,} выполнены условия:

а) для любых a, beUv если fia) = 1 и fib) < Г, или Да) S 0' и fib) = 0, то пара (a, b) является (1,0)-разделимой множеством GB\

б) для любых a0,aube.Up таких, что J{a0) < Г, fia,) < 0' и fib) ~ X', хотя бы одна из пар (ai, а0), (а 1, b) или (b, а0) является (1,0)-разделимой множеством GB.

Теорема 2.6. Функция состояний <р\ Uv с Г—> I, не реализуемая однокаскад-ной схемой, реализуема в RS-базисе если и только если отношение Г^д

квазимонотонно и множество В содержит элемент, не сохраняющий отношения у; в этом случае (р реализуется двухкаскадной схемой в данном базисе.

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

Глава 3. Методы реализации функций на полурешётках

Доказательства достаточности условий теорем главы 2 конструктивны и дают методы схемной реализации функций на полурешётках. Будучи предназна-

ченными лишь для доказательства существования схем при выполнении достаточных условий, эти методы доставляют, как правило, избыточные схемы. В главе 3 приводятся методы синтеза с использованием эвристических приёмов, направленных на получение более простых схем. Описывается модификация декомпозиционного параметрического метода В.Л. Павлова, предназначенная для синтеза параллельно-последовательных сетей, реализующих функции проводимости со значениями в полурешётке Р2. Для данных функции/и множества функций б вводится понятие (/", <3)-дополняющей системы: множество функций назовём (/", С)-дополияющей системой, если:

1) все функции в (2 реализуемы формулами над й и

2) из (/(о),Д6)) = (1, 0) следует, что пара (а, Ь) является (1, 0)-разделимой множеством в или (0, 1)-разделимой множеством £>.

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

(/, Сд)-дополняющей системы.

Предлагается алгоритм реализации функции проводимости /еР2 двухкаскад-ной схемой в ЯЗ-базисе £и{/?}, одним из этапов которого является построение (/, С?я)-дополняющей системы. Формулируются два алгоритма построения (/, <7)-дополняющих систем, один из которых получает кратчайшую систему, а второй минимизирует верхнюю оценку сложности схемы, реализующей функцию/.

Предлагаются также метод реализации функции проводимости / со значениями в Рг и методы реализации систем функций со значениями в Р2 и в Ръ,

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

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

Глава 4. Реализация функций на полурешетках схемами, функционально устойчивыми к состязаниям

Пусть даны полурешётка состояний L, переключательная схема С с функцией fe: L"—> L и a, beL". В силу монотонности функции схемы имеем fda) +fc(b) < fc(a + b). Будем говорить, что переключательная схема С функционально устой' чива к состязанию на переходе (а, Ъ), если имеет место равенство feia + b) = /с(а) +/c(¿); в противном случае будем называть схему С функционально неустойчивой к этому состязанию. Функциональная устойчивость схемы к состязанию на переходе (а, Ъ) означает, что при любом распределении задержек элементов и любом порядке изменения компонент входного состояния выход схемы останется в пределах минимально возможного значения fdíct) +fc{b) в процессе изменения входного состояния с а на Ь.

Пусть дана функция f. U^c » L, a, beUfVi а + bíUf. Будем говорить, что функция f содержит функциональное состязание (ф-состязание) на переходе (а, Ь), если для любой монотонной определённой на а + b функции g из условия g <f следует -> (g(a + b) <J(a) +flb)). Функцию, не содержащую ф-состязания на переходе (а, Ь), будем называть также свободной от ф-состязания на этом переходе. Будем говорить, что функция f, свободная от ф-состязания на переходе (а, Ь), содержит логическое состязание (л-состязание) на этом переходе, если существует монотонная определённая на а + b функция g такая, что g </ и (¡da + Ь) <Ла) +ЛЬ))-

Построим для функции f и перехода (a, tí) расширение fab следующим обра-

зом: и= и^ {а + Ь), для всех х Ф а + Ь положим /ин(х) =Дх)> и /аь(а + Ь) =

Аа) +АЬ). Следующее утверждение является другим (конструктивным) определением понятия ф-состязания.

Утверждение 4.1. Функция / содержит ф-состязание на переходе (а, Ь), если и только если её расширение/аЬ не квазимонотонно.

Для квазимонотонной функции /: 1У/С Ьп—> Ь построим всюду определённую функцию /*: > £ следующим образом: для любого аеЬ" пусть

Построенная так функция /* является наибольшей монотонной реализацией функции/.

Теорема 4.1 (тест на наличие функционального состязания).

Квазимонотонная функция/содержит ф-состязание на переходе (a, tí), если и только если существует элемент сет(а + Ь) такой, что f\c)r\(J[a) +fib)) = 0.

Теорема 4.2 (тест на отсутствие состязаний).

Пусть функция f: U/—> L квазимонотонна,/* — её наибольшая монотонная реализация, a,beUf и а + b?iUf. Тогда/не содержит ни логического, ни функционального состязания на переходе {а, Ь), если и только если/'(а + b) <J[a) +Д£>).

Множество переходов Т назовём совместимым для функции /, если существует монотонная функция g такая, что g </ и для любого (а, 6)е Т функция g определена на а + b и g(a + tí) ¿Да) +Д6).

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

Теорема 4.3 (тест совместимости множества переходов).

Пусть заданы функция /: U/C. L"—> L и множество переходов Т и пусть М= U т(а + Ь) . Тогда множество переходов Г совместимо для функции/ если

и только если /свободна от ф-состязания на каждом переходе из Г и для любого хеМ существует нижняя грань множества {/аь(х)'- (а, b)еТ}.

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

Будем говорить, что состязание на переходе (а, Ь) в схеме С существенно для функции / если —i(/-(a + b) ¿fta) +j{b)), и схему С назовём /устойчивой к состязанию на переходе (а, Ь), если fcifl + Ъ) <J{a)

Для заданных функции /: Uycz L"—> L и множества переходов Т построим отношение Q/rс:L"yL следующим образом: 0./т= {(x,f(x)): xeUj) u {(a + b, Ла) +АЬ)У- {ft, Ь)еГ}. Будем говорить, что функция/: L^c L"-> L реализует отношение Г с L"xL, и писать /¿Г, если для любой пары (х, е Г выполняются условия xeUf ч_Дх) <у. Говорим, что схема С является реализацией отношения Г с L"xL, если /с ¿Г. Будем называть отношение Г реализуемым в базисе В, если существует его реализация в этом базисе.

Теорема 4.4. Функция /реализуема в базисе В схемой,/устойчивой к состязаниям на всех переходах из множества Т, если и только если отношение Cly т реализуемо в В\ в этом случае любая реализация Q.f T реализует/и является/ устойчивой к состязаниям на всех переходах из Т.

Из определения совместимого множества переходов следует, что множество Т совместимо для функции /, если и только если отношение Q/ т квазимонотон-но. В этом случае по тесту квазимонотонности [1] для любого (a, b)e Т существует нижняя грань множества Fab~ {Дс) +J(d)\ (c,d)eT& с + d — а + ¿>}, и можно построить расширение /г функции / на множество UfKJ {a + b: (а, Ь)еТ}, положив fj(a + b) = inf Fab.

Теорема 4.5. Функция /реализуема в базисе В схемой, ^устойчивой к состязаниям на всех переходах из совместимого для/множества Т, если и только если в базисе В реализуема функция/т-.

Теорема 4.6. Пусть множество переходов Г совместимо для функции / и множество В^Е2 содержит элемент, не сохраняющий отношения у. Тогда /г реализуется схемой в базисе В<и{Я}, если и только если для любого уеМ = и т(хв) существует нижняя грань множества Ту = {/?(*): хе и{ &

ует(хв)}.

Совместимое для функции / множество переходов Т будем называть В-совместимым для/, если расширение/Г реализуемо в базисе В.

Для случая, когда В есть ЯБ-базис, приводится алгоритм построения всех максимальных по включению ¿^-совместимых для функции / подмножеств множества переходов Т.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Панкратова И. А. Синтез комбинационных функциональных схем в много-

значной логике // Алгоритмы решения задач дискретной математики.

Вып.2. - Томск: Изд-во Том. ун-та, 1987. - С. 59 - 64.

2. Панкратова И. А., Быкова С. В., Николаева Л. А., ОрановА. М. Система авто-

матического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины. — 1991. - № 1. - С. 3 - 9.

3. Панкратова И. А. К проектированию РЭС методом вентильных матриц //

Труды третьей международной научно-технической конференции АПЭП — 96. - Новосибирск, 1996. - Т.6, ч.2. С. 53 - 54.

4. Панкратова И. А. Реализация функций на полурешетках переключательными

схемами Н Новые информационные технологии в исследовании дискретных структур. Доклады III всероссийской конференции. — Томск, 2000. - С. 257261.

5. Панкратова И. А. О системе программ моделирования динамического пове-

дения переключательных схем с задаваемой точностью // Вестник Томского государственного университета. - 2000. — № 271. - С. 105 - 107.

6. Панкратова И. А. Синтез комбинационных переключательных схем с задан-

ным динамическим поведением // Вестник Томского государственного университета.-2000.-№271.-С. 107-111.

7. Панкратова И. А. Синтез двухкаскадных переключательных схем, реализую-

щих функции на полурешётках И Вестник Томского государственного университета. Приложение. - 2002. - № 1 (II). - С. 108 - 110. S. Панкратова И. А. О статических состязаниях в переключательных схемах // Вестник Томского государственного университета. Приложение. — 2003. — №6. -С. 147-152.

9. Панкратова И. А. Синтез комбинационных переключательных схем без состя-

заний И Вестник Томского государственного университета. Приложение. -2004. - № 9 (I). - С. 245 - 249.

10. Панкратова И. А. Анализ состязаний в переключательных комбинационных схемах // Материалы XV Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 18-23 октября 2004 г.) — С. 61— 65.

11. Панкратова И. А. Условия реализуемости функций на полурешётках переключательными схемами // Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.) -С. ИЗ.

12. Панкратова И. А. Параллельно-последовательная реализация функции мос-тикового соединения на полурешётках // Вестник Томского государственного университета. Приложение. — 2005. — № 14. — С. 229 — 233.

13. Панкратова И. А. Реализация функций проводимости переключательными сетями глубины 2 // Вестник Томского государственного университета. Приложение. -2006.- № 18.-С. 14-19.

Список цитируемой литературы

1. Агибалов Г. П. Дискретные автоматы на полурешетках. — Томск: Изд-во Том. ун-та, 1993. - 227 с.

Размножено 120 экз. Копировальный центр Св-во ПД-Г № 526, выдано 23 апреля 1996г. г. Томск, ул. 19-й Гвардейской дивизии, 75 тел.: 41-34-47

Введение.

Глава 1. Состояние проблемы и основные понятия.

1.1. Краткая характеристика состояния проблемы.

1.2. Функции на полурешётках.

1.3. Переключательные схемы и их поведение.

1.4. Постановка задач реализации функций на полурешётках.

Глава 2. Условия реализуемости функций на полурешётках.

2.1. Необходимое условие реализуемости функции на полурешётках.

2.2. Необходимые и достаточные условия реализуемости функций со значениями в полурешётке (Р2)2.

2.3. Необходимые и достаточные условия реализуемости функций со значениями в полурешётке/.

2.4. Условия реализуемости функций проводимости сетями с мостиковыми соединениями.

Глава 3. Методы реализации функций на полурешётках.

3.1. Реализация функций проводимости со значениями в Р2.

3.1.1.1-реализаци я.

3.1.2.2-реализаци я.

3.2. Реализация функций проводимости со значениями в Р3.

3.3. Реализация систем функций на полурешётках.

3.3.1. Реализация систем функций со значениями в Pj.

3.3.2. Реализация систем функций со значениями в ?з.

Глава 4. Реализация функций на полурешетках схемами, функционально устойчивыми к состязаниям.

4.1. Определение состязаний.

4.2. Тесты на наличие состязаний.

4.3. Совместимость переходов.

4.4. Условия реализуемости со свойством функциональной устойчивости к состязаниям.

4.5. Синтез функционально устойчивых схем.

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

Актуальность проблемы. Изначально методы логического проектирования дискретных управляющих систем [43], или дискретных автоматов [15], базируются на таком разделе дискретной математики, как конечно-значная логика [44]. Её средства позволяют описывать статическое поведение системы (при фиксированном входном состоянии), однако недостаточны для описания динамического поведения (при асинхронном изменении компонент входного состояния). В дальнейшем в теории дискретных автоматов широкое распространение получили общеалгебраические методы [2, 4, 8, 48, 49]. На этом пути было показано, в частности, [2], что динамическое поведение дискретного автомата может быть адекватно и с заданной точностью описано средствами полурешёточно упорядоченных алгебр. Для этого множество состояний в автомате представляется как конечная верхняя полурешётка, т. е. частично упорядоченное множество, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка в полурешётке интерпретируется как отношение сравнения состояний по степени их неопределённости, а сумма состояний а + Ь моделирует промежуточное состояние, возникающее в процессе асинхронного изменения а на Ь. Задача синтеза дискретного автомата, обладающего заданным динамическим поведением, сводится к синтезу схемы в некотором базисе, реализующей функцию на полурешётках, описывающую это поведение. В связи с этим представляет научный и практический интерес разработка методов схемной реализации функций на полурешётках.

Первые результаты в этом направлении получены в работе [2], где описан метод реализации функции на полурешётке подмножеств трёхэлементного множества схемой в произвольном базисе и сформулированы необходимые и достаточные условия полноты базиса для случая однокаскадных па-раллелыю-последовательных схем. Проблеме полноты в классе функций на произвольной конечной полурешётке посвящена также работа [29], доказательства в которой конструктивны и доставляют методы реализации полурешёточных функций. При проектировании реальных дискретных управляющих систем на базе БИС и СБИС чаще всего используется элементный RS-базис, состоящий из элементов двух типов - резистора, представляющего собой двухполюсник с постоянной конечной проводимостью (обозначаемой X) между полюсами, и переключателей, являющихся многополюсниками, в которых проводимости между полюсами принимают значения в полурешётке Р2 всех непустых подмножеств множества {0,1} и являются функциями от состояний полюсов элемента. К сожалению, ни один из RS-базисов не удовлетворяет критериям полноты из [2,29], поэтому актуальной становится проблема реализуемости функций на полурешётках схемами в заданном (неполном) RS-базисе. Решение этой проблемы предполагает формулировку критериев (необходимых и достаточных условий) реализуемости, т. е. существования схемы в RS-базисе, реализующей заданную функцию, и методов реализации - синтеза такой схемы, если она существует.

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

Цель работы. Настоящая работа посвящена разработке критериев реализуемости и методов реализации функций на полурешётках переключательными схемами, в которых проводимости цепей принимают значения в полурешётке Рз всех непустых подмножеств множества {О, X, 1}, а состояния узлов - значения в полурешётке (Р3)2. Ставятся следующие задачи: (1) установить необходимые и достаточные условия реализуемости функций на полурешётках схемами в произвольном RS-базисе; (2) разработать методы синтеза в RS-базисах схем, реализующих функции на полурешётках; (3) формализовать понятие состязаний для функций на полурешётках и разработать методы синтеза схем, реализующих такие функции и обладающих свойством функциональной устойчивости к состязаниям на заданном множестве переходов.

Научная новизна и выносимые на защиту положения.

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

2. Введено понятие (8, а)-разделимости пары {а, Ъ) элементов полурешётки множеством функций, означающее наличие в множестве функции, принимающей значения 5 и а на элементах а и b соответственно, и доказано, что необходимым и достаточным условием реализуемости функции/ однокаскадной схемой в RS-базисе является (1, 0)-разделимость множеством базисных функций некоторых однозначно вычисляемых пар элементов из области определения функции/

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

4. Доказано, что классы функций на полурешётках, реализуемых в RS-базисе параллельно-последовательными схемами и схемами с мостико-выми соединениями, совпадают.

5. Предложены методы реализации функций на полурешётках и их систем переключательными схемами в RS-базисах.

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

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

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

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

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

Апробация работы. Результаты диссертации обсуждались на совместных научных семинарах кафедр защиты информации и криптографии, программирования, информационных технологий в исследовании дискретных структур Томского государственного университета, докладывались на XV Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, 2004 г.), XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), Всероссийских конференциях «Новые информационные технологии в исследовании сложных структур» (Томск, 2000 и 2002 гг., Иркутск, 2004 г.), Сибирских школах-семинарах «Компьютерная безопасность и криптография» (Томск, 2003 и 2005 гг.).

Публикации. Основные результаты диссертации опубликованы в работах [52 - 64].

Структура и объём работы. Диссертация состоит из введения, четырёх • глав, заключения и библиографии, включающей 64 наименования; её объём -102 стр.

Заключение

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

1. Сформулированы условия реализуемости функций на полурешётках переключательными схемами, в том числе:

1.1) необходимое условие реализуемости в произвольном базисе (теорема 2.1);

1.2) необходимые и достаточные условия реализуемости однокаскадны-ми схемами в RS-базисах (теоремы 2.2,2.5);

1.3) необходимые и достаточные условия реализуемости многокаскадными схемами в RS-базисах (теоремы 2.3,2.4,2.6).

2. Доказано, что классы функций на полурешётках, реализуемых в RS-базисах параллельно-последовательными схемами и схемами с мостиковыми соединениями, совпадают (теорема 2.7).

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

4. Исследована задача реализации функций на полурешётках схемами, устойчивыми к состязаниям (глава 4), в том числе

4.1) формализованы понятия состязаний для функций на полурешётках и функциональной устойчивости к состязаниям схем, реализующих такие функции (п. 4.1);

4.2) сформулированы тесты на отсутствие состязаний (теоремы 4.1,4.2);

4.3) сформулирован тест совместимости произвольного множества переходов (теорема 4.3);

4.4) сформулированы необходимые и достаточные условия реализуемости функции на полурешётках функционально устойчивой к состязаниям на заданном множестве переходов схемой в произвольном базисе (теоремы 4.4, 4.5) и RS-базисе (теорема 4.6);

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

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под ред. Варшавского В. И. - М.: Наука, 1986. - 400 с.

2. Агибалов Г. П. Дискретные автоматы на полурешетках. Томск: Изд-во Том. ун-та, 1993.-227 с.

3. Агибалов Г. П., Бузанов В. А., Липский В. Б., Румянцев Б. Ф. Логическое проектирование переключательных автоматов. Томск: Изд-во Том. унта, 1983.- 154 с.

4. Агибалов Г. П., Евтушенко Н. В. Декомпозиция конечных автоматов. -Томск: Изд-во Том. ун-та, 1985.-128 с.

5. Агибалов Г. П., Комаров Ю.М., Липский В. Б. Синтез комбинационных схем, свободных от статических состязаний // Автоматика и вычислительная техника. 1979. - № 1. - С. 1 - 6.

6. Ангер С. Асинхронные последовательностью схемы. М.: Наука, 1977. -400 с.

7. Бивол Л. Г. О реализации булевых функций на произвольных элементах // Абстрактная и структурная теория релейных устройств. М.: Наука, 1972.-С. 32-38.

8. Богомолов А. М, СалийВ.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. - 368 с.

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

10. БутаковЕ. А., РоткоВ. Ф. Синтез комбинационных схем с заданными динамическими характеристиками // Динамические системы. 1982. -№ 1. - С. 136-145.

11. Бутов А. А. Реализация систем не полностью определённых булевых функций в базисе схем малого и среднего уровней интеграции // Управляющие системы и машины. 1979. - № 6. - С. 97 - 103.

12. Гаврилов М. А., Девятков В. В., Пупырев Е. И. Логическое проектирование дискретных автоматов. М.: Наука, 1977. - 352 с.

13. Гаврилов М. А., Копыленко В. М. Метод «переходных таблиц» синтеза многовыходных комбинационных структур на произвольных элементах // Абстрактная и структурная теория релейных устройств. М.: Наука, 1972.-С. 7-32.

14. Дрягин Ю. С. Синтез комбинационных схем из элементов, реализующих симметрические булевы функции // Автоматика и телемеханика. 1975. -№ 7.-С. 120-126.

15. Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971.-512с.

16. Закревский А. Д. Логический синтез каскадных схем. М.: Наука, 1981. -416 с.

17. Закревский А. Д. Алгоритмы синтеза полиномов, реализующих слабоопределённые булевы функции и системы // Автоматика и телемеханика. -2004,-№6.-С. 158-176.

18. Закревский А. Д., Поттосин Ю. В., Черемисинова Л. Д. Основы логического проектирования. В трёх книгах. Книга 2: Оптимизация в булевом пространстве. Минск: ОИПИ НАН Беларуси, 2004. - 240 с.

19. Кармазинский А. Н. Синтез принципиальных схем цифровых элементов на МДП-транзисторах. М.: Радио и связь, 1983. - 256 с.

20. Левин В. И. Динамика логических устройств и систем. М.: Энергия, 1980.-224 с.

21. ЛипскийВ.Б. Синтез комбинационных схем без состязаний // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1979.-С. 132- 138.

22. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. 10. М.: Наука, 1963. - С. 63 - 97.

23. Лупанов О. Б. О сложности реализации функций алгебры логики релей-но-контактными схемами //Проблемы кибернетики. Вып. 11. — М.: Наука, 1964.-С. 25-49.

24. Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. Вып. 23. М.: Наука, 1970. - С. 43 - 81.

25. Миллер Р. Теория переключательных схем. Т. 2. М.: Наука, 1971. -304 с.

26. МурогаС. Системное проектирование сверхбольших интегральных схем. Книга 1. М.: Мир, 1985. - 288 с.

27. Павлов В. Л. О синтезе логических схем из элементов "ИЛИ-НЕ" с ограниченным числом входов // Вычислительная техника. Каунас: Каунасский политехнический институт, 1971. - Т. 2. - С. 219 - 223.

28. Павлов В. Л. Синтез комбинационных схем в произвольном базисе // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987. - С. 53 - 59.

29. Парватов Н. Г. Функциональная полнота и выразимость в классе квазимонотонных функций на конечной полурешетке. Дис. . канд. физ.-мат. наук. - Томск, 2001.

30. Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. - № 2. - С. 1451-162.

31. Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.-368 с.

32. РогинскийВ.Н. Основы дискретной автоматики. М.: Связь, 1975. -430 с.

33. СапоженкоА. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. -1983. Т. 12. - Вып. 1. - С. 42 - 47.

34. Синтез асинхронных автоматов на ЭВМ. Под ред. Закревского А. Д. -Минск: Наука и техника, 1975. 184 с.

35. Степаненко И. Р. Основы микроэлектроники. М.: Сов. радио, 1980. -424 с.

36. Фридман А., МенонП. Теория и проектирование переключательных схем. М.: Мир, 1978. - 584 с.

37. Чеботарев А. Н. Риск в асинхронных логических схемах // Кибернетика.- 1976.-№4.-С. 8-11.

38. Чеботарев А. Н. Схемы и автоматы. I, II // Кибернетика. 1976. - № 5. -С.5-9; 1979-№ 5.-С. 9-14.

39. Черемисинова Л. Д. Алгоритм комбинационного синтеза в базисе И-НЕ с перестройкой схемы // Алгоритмы решения логико-комбинаторных задач. Минск: ИТК АН БССР, 1980. - С. 37 - 49.

40. Черемисинова Л. Д. Экспериментальное исследование алгоритмов синтеза комбинационных схем из элементов И-НЕ // Автоматизация логического проектирования дискретных устройств. Вып. 2. Минск: ИТК АН БССР, 1980.-С. 78-85.

41. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.-827 с.

42. ШоломовЛ.А. О функционалах, характеризующих сложность систем недоопределённых булевых функций // Проблемы кибернетики. Вып. 19.- М.: Наука, 1967. С. 123 -139.

43. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. Вып. 2. М.: Наука, 1959. - С. 7 - 38.

44. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1979. -272 с.

45. Якубайтис Э. А. Асинхронные логические автоматы. Рига: Зинатне, 1966.-380 с.

46. Сету Е., Marin М. A Computer Algorithm for the Synthesis of Memoryless Logic Circuits //IEEE Transactions on Computers. 1974. - Vol. C-23. -№5.-P. 455-465.

47. Eichelberger E. B. Hazard Detection in Combinational and Sequential Switching Circuits // IBM Journal of Research and Development. 1965. -Vol. 9.-№2.-P. 90-99.

48. GinzburgA. Algebraic Theory of Automata. New York - London: Academic Press, 1968. -165 p.

49. Hartmanis J., Stearns R. E. Algebraic Structure Theory of Sequential Machines. Prentice-Hall, Englewood Cliffs, 1968. - 210 p.

50. Pal A., MukherjeeA. Synthesis of Two-level Dynamic CMOS Circuits // IWLS99 handouts. 1999. - P. 193 -196.

51. WuM.-Y., Shu W., ChanS.-P. A Unified Theory for MOS Circuit Design -Switching Network Logic // Int. J. Electronics. 1985. - Vol. 58. - № 1. -P. 1-33.

52. Панкратова И. А. Синтез комбинационных функциональных схем в многозначной логике // Алгоритмы решения задач дискретной математики. Вып.2. Томск: Изд-во Том. ун-та, 1987. - С. 59 - 64.

53. Панкратова И. А., Быкова С. В., Николаева Л. А., Оранов А. М. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины. 1991. - № 1. - С. 3 - 9.

54. Панкратова И. А. К проектированию РЭС методом вентильных матриц // Труды третьей международной научно-технической конференции АПЭП 96. - Новосибирск, 1996. - Т.6, ч.2. С. 53 - 54.

55. Панкратова И. А. Реализация функций на полурешетках переключательными схемами // Новые информационные технологии в исследовании дискретных структур. Доклады III всероссийской конференции. -Томск, 2000.-С. 257-261.

56. Панкратова И. А. О системе программ моделирования динамического поведения переключательных схем с задаваемой точностью // Вестник Томского государственного университета. 2000. - № 271. - С. 105 -107.

57. Панкратова К А. Синтез комбинационных переключательных схем с заданным динамическим поведением // Вестник Томского государственного университета. 2000. - № 271. - С. 107 -111.

58. Панкратова И. А. Синтез двухкаскадных переключательных схем, реализующих функции на полурешётках // Вестник Томского государственного университета. Приложение. 2002. - № 1 (И). - С. 108-110.

59. Панкратова И. А. О статических состязаниях в переключательных схемах // Вестник Томского государственного университета. Приложение. -2003.-№6.-С. 147-152.

60. Панкратова И. А. Синтез комбинационных переключательных схем без состязаний // Вестник Томского государственного университета. Приложение. 2004. - № 9 (I). - С. 245 - 249.

61. Панкратова И. А. Анализ состязаний в переключательных комбинационных схемах // Материалы XV Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 18-23 октября2004 г.)-С. 61-65.

62. Панкратова И. А. Условия реализуемости функций на полурешётках переключательными схемами // Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая2005 г.)-С. 113.

63. Панкратова И. А. Параллельно-последовательная реализация функции мостикового соединения на полурешётках // Вестник Томского государственного университета. Приложение. 2005. - № 14. - С. 229 - 233.

64. Панкратова И. А. Реализация функций проводимости переключательными сетями глубины 2 // Вестник Томского государственного университета. Приложение. 2006. - № 18. - С. 14 -19.