Реализация функций на полурешетках переключательными схемами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Панкратова, Ирина Анатольевна

• Панкратова, Ирина Анатольевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Панкратова, Ирина Анатольевна

Введение.

Глава 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), реализующих функции на полурешётках и обладающих свойством функциональной устойчивости к состязаниям: а) на заданном множестве переходов, б) на наибольшем подмножестве всех возможных или только заданных переходов.

Список литературы диссертационного исследования кандидат физико-математических наук Панкратова, Ирина Анатольевна, 2006 год

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.