Помощь в написании студенческих работ
Антистрессовый сервис

Операторы в полиномиальных представлениях булевых функций

Диссертация: Операторы в полиномиальных представлениях булевых функций
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И. И. Жегалкина. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики. И только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых… Читать ещё >

Операторы в полиномиальных представлениях булевых функций (реферат, курсовая, диплом, контрольная)

Содержание

  • Глава I. Основные определения и краткий обзор результатов
    • 1. Основные определения и обозначения
    • 2. Обзор результатов по полиномиальным представлениям булевых функций
  • Глава II. Операторы в булевых функциях и их свойства
    • 3. Свойства операторов и операторных пучков
    • 4. Два критерия существования базисных пучков
    • 5. Специальные классы базисных пучков
  • Глава III. Разложения булевых функций по операторным пучкам и невырожденным системам функций
    • 6. Разложения булевых функций по собственным образам операторного пучка
    • 7. Операторные разложения по образам нечетных функций
    • 8. Бинарные термы в разложениях
    • 9. Разложения по невырожденным системам функций
  • Глава IV. Операторные канонические формы
    • 10. Общий вид операторных полиномиальных форм
    • 11. Классы операторных форм
    • 12. Иерархия классов операторных форм
    • 13. Канонические формы с операторами других типов
  • Глава V. Сложность представлений и методы нахождения операторных полиномиальных форм
    • 14. Сложность операторных форм
    • 15. Методы нахождения полиномиальных представлений
    • 16. Компьютерные реализации алгоритмов

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

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

В теории булевых функций исследования, связанные с представлениями функций различными формами, интенсивно развиваются. Имеется большое количество работ по этому направлению, в частности [6, 20, 27, 28, 29, 47, 48, 52, 101, 109].

Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И. И. Жегалкина [17, 18]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики. И только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых функций. В работах Д. Маллера [74] и И. Рида [83] полиномы Жегалкина были переоткрыты и получено их обобщение для введения нового класса линейных кодов, получивших название «коды Рида-Маллера», а введенные полиномиальные формы стали называться «формами Рида-Маллера» .

Использование кодов Рида-Маллера для передачи изображений Марса американскими межпланетными станциями «Маринер» стимулировало широкие исследования этих кодов [26]. Однако все исследования проводились в направлении метрических свойств кодов, как подпространств. В обзоре [21] приведены более ста работ по этому направлению.

В это время ведутся исследования по различным направлениям теории булевых функций [45, 47, 50]. Появление интереса непосредственно к полиномиальным представлениям булевых функций, как объектам исследования, связано с практическими приложениями. Развитие электроники во второй половине двадцатого века в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привело к тому, что большая интеграция имеет теперь определяющее значение. Лучшей считается схема, имеющая меньшую площадь кристалла. Этот критерий плюс технологические требования регулярности структуры привели к требованию отображать на кристалл функцию или систему функций в виде дизъюнктивной, конъюнктивной или полиномиальной нормальной формы — матричной схемы. Такие схемы получили название программируемых логических матриц (ПЛМ) [7, 8, 11, 12, 69, 82, 84, 106].

Попытки напрямую перенести методы работы с ДНФ на ПНФ не принесли ощутимых результатов [44, 89]. Это стимулировало исследования по полиномиальным каноническим формам, так как имеется большое количество классов таких канонических представлений. По этому направлению имеется целый ряд публикаций и монографий [2, 4, 22, 39, 40, 41, 42, 49, 58, 66, 77, 78, 79, 80, 82, 91, 96, 98, 101, 104].

Внутренний стимул исследования этого направления — известные результаты О. Б. Лупанова по асимптотическим оценкам и разложениям булевых функций [23, 24, 25].

Методам минимизации полиномиальных представлений булевых функций и оценкам их сложности посвящены работы [9, 10, 13, 38, 44, 51, 53, 54, 55, 57, 59, 60, 62, 63, 64, 65, 68, 70, 73, 88, 90, 92, 93, 94, 99, 100, 102, 103, 105, 107, 108, 110].

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

Данная диссертация посвящена исследованиям по указанной проблематике.

Диссертация состоит из пяти глав, которые разбиты на 16 параграфов. Параграфы разбиваются на пункты.

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

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

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

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

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

По результатам, изложенным в диссертации, имеется 28 публикаций [111 — 138]. Результаты докладывались на международных конференциях по алгебре, дискретной математике, математическом и прикладной логике, теоретической и технической кибернетике, в том числе было сделано несколько пленарных докладов (конференция по прикладной логике, Новосибирск, 1992; конференция по математической логике, Казань, 1992; 4-й семинар по дискретной математике и ее приложениям, Москва, 1993; школа-семинар «Дискретные модели в теории управляющих систем», Москва, 1993; X конференция по проблемам теоретической кибернетики, Саратов, 1993; III конференция по алгебре, Красноярск, 1993; школа-семинар «Сложность и синтез управляющих систем», Минск, 1993; школа-семинар «Сложность и синтез управляющих систем», Н. Новгород, 1994; конференция по математической логике, Новосибирск, 1994; конференция по прикладной логике, Иркутск, 1995; школа-семинар «Сложность и синтез управляющих систем», Минск, 1995; конференция «Автоматизация проектирования дискретных систем», Минск, 1995; конференция по проблемам теоретической кибернетики, Ульяновск, 1996; конференция «Мальцевские чтения», Новосибирск, 1997; Международная Сибирская конференция по исследованию операций, Новосибирск, 1998; конференция «Мальцевские чтения», Новосибирск, 1998; конференция «Математика и ее приложения», посвященная памяти профессора А. И. Кокорина и 275-летию РАН, Иркутск, 1999; Международная конференция «Логика и приложения», Новосибирск, 2000; Международная конференция по дискретному анализу и исследованию операций, Новосибирск, 2000; Международная конференция «Математика, информатика и управление», Иркутск, 2000; Международная конференция по проблемам в булевых функциях, Фрайберг (Германия), 2000; Международная конференция «Мальцев ские чтения», Новосибирск, 2000; XI Межгосударственная школа-семинар «Сложность и синтез управляющих систем», Нижний Новгород, 2000; 7-й Международный семинар «Дискретная математика и ее приложения», Москва, 2001).

Были сделаны доклады в ведущих научных центрах: Московский государственный университет (факультет вычислительной математики и кибернетики), Институт математики СО РАН (г. Новосибирск), Институт кибернетики им. В. М. Глушкова (г. Киев), Институт технической кибернетики (г. Минск), Институт динамики систем и теории управления СО РАН (г. Иркутск), Институт прикладной матаматики и кибернетики (г. Нижний Новгород) Институт информатики (г. Фрайберг, Германия), Иркутский государственный университет.

В диссертации принята двойная нумерация теорем и предложений, первая часть номера — номер главы, нумерация лемм идет по параграфам.

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

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

Заключение

.

На защиту выносятся следующие результаты:

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

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

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

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

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

Показать весь текст

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

  1. Дискретная математика и математические вопросы кибернетики/ Под ред. Яблонского С. В. и Лупанова О.Б.-М: Наука, 1974.- Т1- 312 с.
  2. Л. Б. Супрун В.П. Обобщенные полиномиальные разложения симметрических булевых функций// Кибернетика.- 1991.- № 1.- С. 122−125.
  3. Г. С. Брайловский Г. С. Представление логических функций в виде полиномов Жегалкина// Автоматика и вычислительная техника.- 1975.- № 6.- С. 6−10.
  4. Г. С. Обобщенные полиномиальные формы булевых функций и синтез многовыходных логических схем// Автоматика и Телемеханика.- 1983.- № 11.- С. 111−119.
  5. Г. С. Представление булевых функций суммой по модулю 2 импликацией аргументов// Автоматика и вычислительная техника.- 1977.- № 1.- С. 8—11.
  6. Александров С Г. Разложения специального вида булевых функций// Международная конференция по дискретному анализу и исследованию операций. Материалы конференции.- Новосибирск, 2000.- С. 70.
  7. В.JI., Копейкин Г. А., Шалыго А. А. Настраиваемые модули для управляющих логических устройств.-Ленинград: Энергоиздат, 1981.- 166 с.
  8. С.М. Алгоритмы синтеза автоматов на программируемых матрицах.- М.: Радио и связь, 1987.- 135 с.
  9. А.С. Сложные в полиномиальных поляризованных формах симметричные булевы функции // XII Международная конференция по проблемам теоретической кибернетики: Тезисы докл.- Нижний Новгород, 1999.-С.17.
  10. А.С. Сложные в полиномиальных поляризованных формах функции алгебры логики / / Международной конференции по математической логике: Тезисы докл.-Новосибирск, 1999.- С. 9- 10.
  11. С.И., Скляров В. А. Цифровые устройства на программируемых СБИС с матричной структурой.- М.: Радио и связь, 1986.- 270 с.
  12. П.Н. Синтез комбинационных ПЛМ структур для СБИС — Мн: Навука i тэхшка, 1992 — 232 с.
  13. Д., Постхоф X. Двоичные динамические системы.- М: Энергоатомиздат,
  14. Г. П. Функциональные системы дискретной математики М: Изд-во Московского ун-та, 1985.- 40 с.
  15. В.И. Введение в кибернетику.- Киев: Изд-во АН УССР, 1964.- 324 с.
  16. P.M., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств.- Киев: На-укова думка, 1987.- 264 с.
  17. И.И. Арифметизация символической логики // Мат. сборник.- 1928.- Т.35 С.311−373.
  18. И. И. Арифметизация символической логики // Мат. сборник.- 1929.- Т.36 С.305−338.
  19. А.Д. Минимизация систем булевых функций в полиномах Жегалкина// Докл. Белорусской АН.- 1995, т.39, № 6.- С.11−14.
  20. О.В. Представление функций алгебры логики суммами специального вида // Межд. конф. «Логика и приложения», 4−6 мая 2000 г., Новосибирск., С. 52.
  21. Ю.В., Шкарин С. А. Коды Рида-Маллера (обзор публикаций)// Математические вопросы кибернетики.-1996.- № 1- С. 5−50.
  22. А.В. Разложение булевых функций с оператором векторная производная// В сб."Алгебра, логика и приложения". Иркутск, 1994. — С. 116−124.
  23. О.Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования// Проблемы кибернетики. Вып. 14 М.: Наука, 1965.- С. 31−110.
  24. О.Б. О сложности реализаций функций алгебры логики формулами// Проблемы кибернетики. Вып. 3. г из, 1963.- С. 61−80.
  25. О.Б. Асимптотические оценки сложности управляющих систем М.: Из-во МГУ, 1984 — 137 с.
  26. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки М.: Связь, 1979.- 477 с.
  27. С.С. О равномерном id-разложении булевых функций// Дискретная математика.- 1990.- Т. 2, № 3.-С. 29−41.
  28. С.С. Замкнутые классы булевых функций. -М.: Физматлит, 2000. 128 с.
  29. С.С., Угольников А. Б. Замкнутые классы булевых функций.- М.: Ин-т прикл математики АН, 1990 — 147 с.
  30. Э.К., Супрун В. П. О полиномиальном разложении булевых функций // Изд-во Белорусской АН, физмат. лит-ра, Минск.- 1988.- 31 с.
  31. Р.Г. Сложность булевых функций.- М.: Наука, 1991.- 240 с.
  32. В.И., Перязев Н. А. Об операторах булевых функций// Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем», Нижний Новгород, 2000. Из-во МГУ, Часть II. — С. 141 146.
  33. Н.А. Сложность булевых функций в классе полиномиальных поляризованных форм// Алгебра и логика.-1995.- Т. 34, № 3.- С. 323−326.
  34. Н.А. Основы теории булевых функций. М.: Физматлит, 1999. — 112 с.
  35. Г. Н. Математико-логическое исследование синтеза контактных схем с одним входом и к выходами// Логические исследования. Изд-во АН СССР.- 1959.- С.379−405.
  36. А.А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм// ВИНИТИ. Итоги науки и техники. Теоретическая кибернетика.- 1987.- Вып. 25.- С. 68−116.
  37. А.А., Караханян Л. М. Об отрицательных эффектах, связанных с удалением несущественных переменных// Автоматика и телемеханика. 1981. — № 3. — С. 28−35.
  38. М.В., Кириченко К. Д. Некоторые стратегии при минимизации булевых функций// Материалы Международной научной студенческой конференции. Новосибирск. 1994. — С.38.
  39. В.П. Преобразования булевых функций на основе симметрической разности// Изв. АН СССР. Техническая кибернетика. 1983. — № 5. — С. 199−202.
  40. В.П. Табличный метод полиномиального разложения булевых функций// Кибернетика.- 1987.- № 1.- С. 116−117.
  41. В.П. Декомпозиция булевых функций на основе полиномиального разложения// Изв. АН СССР. Техническая кибернетика. 1989. — № 3. — С. 187−191.
  42. В.П. Об одном методе полиномиального разложения булевых функций// Кибернетика.- 1989.- № 5.-С. 122−124.
  43. В.П. Сложность булевых функций в классе канонических поляризованных полиномов// Дискретная математика.- 1993.- Т. 5, Вып.2.- С.111−115.
  44. . Полиномиальные представления булевых функций и их минимизация// Известия АН СССР. Техн. кибернетика.- 1967.- № 3.- С. 141−143.
  45. К.Э. Работы по теории информации и кибернетике.- М: ИЛ., 1963.- 829с.
  46. С.В. Введение в дискретную математику.- М: Наука, 1986.- 384 с.
  47. С.В. О суперпозициях функций алгебры логики// Мат. сборник.- 1952.- Т. 30, № 2.- С. 329−345.
  48. С.В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста.- М: Наука, 1966.- 120 с.
  49. Akers S.B. A rectangular logic array. // Trans. IEEE.- 1972, vol. C-21.- P.848−857.
  50. Akers S.J. On theory of Boolean functions // JSoc Industr and ApplMath.- 1959.- V.7, No 4.- P. 487−498.
  51. Besslich Ph.W. and Riege M.W. An Efficient Program for Logic Synthesis of Mod-2 Sum Expressions // Proc. EU-ROASIC, Paris, France, 1991.- P.136−141.
  52. Bochmann D. Boolean Differential Calculus — an Overview // in: Abel D., Lemmer K. Theory of discrete Systems.-Oldenbourg Verlag, 1998.- P. 161−201
  53. Brand D. and Sasao T. Minimization of AND-EXOR expressions using rewrite rules // IEEE Transactions on Computers, 1993.- No 42(5).- P.568−576.
  54. Bryant R.E. Graph-based algorithms for boolean function manipulation // IEEE Trans. Сотр.- 1986, vol. C-35, No. 8. P.667−691.
  55. Brayton R.K. Factoring logic functions// IBM JRes and Dev.- 1987.- V.31, No 2.- P. 187−198.
  56. Butler J.T., Herscovici D.S., Sasao Т., Barton III R.J. Average and worst case number of nodes in decision diagrams of symmetric multiple-valued funcsions// IEEE Trans, on Computers.- 1997.- V. 46, No 4.- P. 491−494.
  57. Csansky L., Perkovsky M., Schaefer I. Canonical Restricted Mixed-Polatity Exclusive Sums of Products and Efficient Algorithm for Thier Minimization // Proc. IEEE International Symposumon Circuits and Systems. San Diego, 1992.- P.17−20.
  58. Davio M. Taylor expansions of symmetric Boolean function// Philips Res. Repts.- 1973, No 28.- P. 466−474.
  59. Debnath D., Sasao T. GRMIN: A Heuristic Simplification Algorithm for Generalized Reed- Muller Expressions // Proc. RM'95. P.257−264.
  60. Drechsler R., Sarabi A., Theobald M., Becker В., and Perkowski M. Efficient representation and manipulation of switching functions based on Ordered Kronecker Functional Decision Diagrams // Proc. DAC'94.- P.415−419.
  61. Drechsler R. Pseudo Kronecker Expressions for Symmetric Functions // Proc. VLSI Design, 1997.- P.511−513.
  62. Drechsler R., Theobald M. and Becker B. Fast OFDD-based minimization of fixed polarity Reed-Muller expressions //
  63. EE Trans. Comput., 1996.- Vol. C-45, No. 11- P.1294−1299.
  64. Drechsler R. Evolutionary Algorithms for VLSI CAD. Kluwer Academic Publishers, 1998.- 350 p.
  65. Drucker B.T., Files C.M., Perkowski M.A. and Chrzanows-ka-Jeske M. Polarized Pseudo-Kronecker Symmetry with an Application to the Synthesis of Lattice Decision Diagrams // Proc. ICCIMA'98, 1998.- P.123−132.
  66. Even S., Kohavi J., Paz A. On minimal modulo-2 sums of products for switching functions // IEEE Trans. Electron. Comput.- 1967.- V.16, No 10.- P.671−674.
  67. Fujita M.,(eds.) Representations of Discrete Function. Kluwer Academic Publishers, 1996.- 450 p.
  68. Green D.H. Families of Reed-Muller Canonical Forms // Intern. J. of Electr 1991, No 2.- P.259−280.
  69. Helliwell M. and Perkowski M.A. A fast algorithm to minimize mixed polarity generalized Reed-Muller forms // IEEE Computer Society Press, 1988.- P.427−432.
  70. Ho P., and Perkowski M. A. Free Kronecker Decision Diagrams and their Application to ATMEL 6000 FPGA Mapping // Proc. Euro-DAC'94/Euro-VHDL'94.- P.8−13.
  71. Kozlowsky T. Heuristic Minimization of ESOP’s // Proc. Reed-Muller Colloquium. UK, 1995.- P. 4/1−4/5.
  72. Lester N.L.K. and Saul J.M. Technology mapping of mixed polarity Reed-Muller representations //In Proceedings of the European Conference on Design Automation. IEEE Computer Society Press, 1993.
  73. Mantsivoda J., Peryazev N. The Complexity of Symmetric Functions in the Polynomial Forms // 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Oxford/UK.- 1997.- FZI report 5/97.- P. 166−173.
  74. Muller D.E. Application of Boollean algebra to switching circuit desing and error detectio// IEEE Trans. Electron. Comput.- 1954.- V.3, No 3.- P. 6−12.
  75. Perkowski M., Johnson P. Canonical multi-valued input Reed-Muller Trees and Forms // Proc. 3rd NASA Symp. on VLSI Design. Oct. 1991, Moscow, Idaho.- P.ll.3.1−11.3.13.
  76. Perkowski M.A. The Generalized Orthonormal Expansion of Functions with Multiple-Valued Inputs and Some of its Applications // Proc. ISM’L'92 P.442−450.
  77. Perkowski M.A. A Fundamental Theorem for Exor Circuits // Proc. RM'93 P.52−60.
  78. Perkowski M.A., Sarabi A., Beyl F. XOR Canonical Forms of Switching Functions // Proc. RM'93 P.27−32.
  79. Perkowski M.A., Pierzchala E. and Drechsler R. Layout-Driven Synthesis for Submicron Technology: Mapping Expansions to Regular Lattices // Proc. ISIC-97, Singapur, 1997.- P. 29−37.
  80. Reed I.S. A class of multiple-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory.- 1954.- V. 4, N 9.- R 38−49.
  81. Sarabi A., Song N., Chrzanowska-Jeske M. and Perkowski M.A. A Comprehensive Approach to Logic Synthesis and Physical Design for Two-Dimensional Logic Arrays // Proc. DAC'94.- San Diego, 1994.- P.321−326.
  82. Sasao T. Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexyty of Programmable Logic Arrays// IEEE Trans, on Comput.- 1981.- V. 30, No 9.- P. 633−645.
  83. Sasao T. Input variable assignment and output phase optimization of PLA’s // IEEE Trans. Comput., 1984.- Vol. C-33, No. 10.- P.879−894.
  84. Sasao Т., Besslich P. On the complexity of mod-2 sum PLA’s// IEEE Trans, on Comput.- 1990.- V. 39, No 2.-P. 262−266.
  85. T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993 320 p.
  86. Sasao Т. AND-EXOR expressions and their Optimization //in: Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- P. 289−300.
  87. Sasao T. Represeintation of Logic Functions using EXOR Operators // Proc. IFIP WG 10.5 Workshop on Applic. of the Reed Muller Expansion in Circuit Design.- Tokyo, 1995.- P. 11−20.
  88. T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- 320 p.
  89. Sasao T. An Exact Minimization of AND-EXOR Expressions Using BDDs // Proc. Reed-Muller'93, P.91−98.
  90. Sasao T. Complexity Measures for AND-EXOR Expressions // Proc. 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.- Oxford/UK, 1997.- P. 145−156.
  91. Sasao T. Switching Theory for Logic Synthesis.- Kluwer Academic Publishers.- 1999.- 355 p.
  92. Schaefer I., Perkowski M.A. Multiple-Valued Input Generalized Reed-Muller Forms // IEE Proc., 1992.- Vol.139, No.6.-P.519−527.
  93. Saul J.M., Eschermann B. and Juergen Froessl. Two-level logic circuits using EXOR sums of products // Combinational networks, 1993. In IEE Proceedings Part E, Computers and Digital Techniques U0(6).- P.348−356.
  94. Saul J.M. An improved algorithm for the minimization of mixed polarity Reed-Muller representations // IEEE Computer Society Press, 1990.- P.372−375.
  95. Saul J.M. An algorithm for the multi-level minimization of Reed-Muller representations // IEEE Computer Society Press, 1991.- P.634−637.
  96. Saul J.M. Towards a mixed exdusive-/indusive-or factored form. In IFIP Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1993.- P. 1−5.
  97. Saul J.M. An efficient data structure for the minimization of EXOR sums. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 116−121.
  98. Steibach В., Zhang Z. Synthesis for full testability of partitioned combinational circuits using Boolean differential calculus // Proc. of IEEE/ACM Int. Workshop in Logic Synthesis, USA, 1997.- P. 1−4.
  99. Suprun V. Fixed polarity Reed-Muller Expansion of symmetric Boolean function // Proc. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 246−249.
  100. Thomson P. and Miller J.F. Symbolic method for simplifying AND-EXOR representations of Boolean functions using a binary decision technique and a genetic algorithm // IEE Proceedings-Computers and Digital Techniques.-1996.- Vol.143, No.2 P. 151−155.
  101. Wood R.A. A Higt Density Programmable Logic Array Chip// IEEE Trans 1979.- V. 29, N 9.- P. 602−608.
  102. Wu X., Chen X. and Hurst S.L. Mapping of Reed-Muller Coefficients and the Minimization of Exclusive-OR Switching Functions // IEE Proc.- 1982.- vol.129, No. l P.5−20.
  103. Wu X., Perkowski M. Generalized Partially-Mixed-Polarity Reed-Muller Expansion and its Fast Computation // IEEE Trans, on Computers.- V.45, No.9.- P.1084−1088.
  104. Yanushkevich S. Arithmetical Canonical Expansions of Boolean and MVL Functions as generalized Reed-Muller Forms // Proc. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 300 307.
  105. Zeng X., Perkowski M.A., Dill K., Sarabi A. Approximate Minimization of Generalized Reed-Muller Forms // Proc. RM'95, P.221−230.
  106. Работы автора по теме диссертации
  107. С. Ф. Перязев Н.А. Полиномиальные разложения булевых функций по невырожденным функциям// Алгебра и логика.- 1991.- Т. 30, № 6.- С. 631−637.
  108. С.Ф. Полиномиальные операторные разложения и канонические формы булевых функций. Из-во Иркутского ун-та.- 1992.- 26 с.
  109. С. Ф. Перязев Н.А. Представление булевых функций полиномиальными формами// Кибернетика и системный анализ.- 1992.- № 2.- С. 210−213.
  110. С.Ф., Манцивода Ю. В., Перязев Н. А. Система автоматического синтеза частичных конечных автоматов на программируемых логических матрицах с памятью // Вычислительные системы, 146, — Новосибирск, 1992.- С. 142−143
  111. С. Ф. Перязев Н.А. Полиномиальная декомпозиция булевых функций // Математические заметки.-1993.- Т. 53, вып. 2. С. 25−29.
  112. С. Ф. Перязев Н.А. Разложение булевых функций на сумму произведений подфункций //Дискретная математика.- 1993 Т. 5, вып. 3. — С. 102−104.
  113. С. Ф. Перязев Н.А. Полиномиальные разложения булевых функций // Кибернетика и системный анализ, — 1993.- № 6.- С. 34−47.
  114. С. Ф. Манцивода Ю.В. Перязев Н. А. Минимизация булевых функций в классах нормальных форм методом разложения //В кн. Методы и системы технической диагностики. Из-во Саратовского университета.1993, вып. 18.- С. 39−40.
  115. С.Ф., Корсуков А. В. Полиномиальное разложение булевых функций по оператору векторной производной // III Международная конференция по алгебре. Сборник тезисов. Красноярск, — 1993.- С. 74.
  116. С.Ф., Перязев Н. А. Полиномиальные разложения булевых функций по неоднородным операторам / / Фундаментальные проблемы математики и механики. Математика М.: Изд-во Моск. ун-та, 1994 — С. 317−318.
  117. С.Ф., Гайдуков А. И. Класс стягиваемых булевых функций // XII Международная конференция по математической логике. Тезисы докладов.- Новосибирск, 1994.- С. 38−39.
  118. С.Ф., Манцивода Ю. В., Перязев Н. А. Минимизация булевых функций в классах нормальных форм методом разложения // Фундаментальные проблемы математики и механики. Математика.- М.: Изд-во Моск. ун-та. 1994. С. 316−317.
  119. С.Ф., Гайдуков А. И., Корсуков А. В. Библиотека классов булевых функций // Сб. трудов Иркутского ГУ.- Иркутск, 1995.- Т.З.- С. 228−229.
  120. С.Ф., Манцивода Ю. В., Перязев Н. А. Система синтеза конечных автоматов // Тезисы докл. Международной конференции «Автоматизация проектирования дискретных систем», — Минск, 1995 С. 56.
  121. С.Ф., Гайдуков А. И., Корсуков А. В. Автоматизированная система для исследования булевых функций // Тезисы докл. Международной конференции «Автоматизация проектирования дискретных систем».-Минск, 1995.- С. 55.
  122. С.Ф., Гайдуков А.И. BOOLEARN — система для работы с булевыми функциями / / Международная конференция по прикладной логике: Тезисы докладов.-Иркутск, 1995.- С. 17−18.
  123. С.Ф. Некоторые оценки сложности булевых функций в классе полиномов // Синтез и сложностьуправляющих систем, VII Межгосударственная школа-семинар.- Минск, 1995.- С. 4−5.
  124. С. Ф. Перязев Н.А. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций // Изв. ВУЗов. Математика.- 1996.- № 1 С. 17−21.
  125. С.Ф. Об одном классе полиномиальных форм булевых функций //XI Международная конференция по проблемам теоретической кибернетики. Тезисы докл-Ульяновск, 1996.- С. 220.
  126. С.Ф. Классификация булевых функций по оператору кратного минимума / / Международная Сибирская конференция по исследованию операций. Материалы конференции. Новосибирск, 1998.- С. 121.
  127. С.Ф. Представление операторных форм булевых функций последовательностями / / Материалы Международной конференции по математической логике. Новосибирск, 1999.- С. 12−14.
  128. С.Ф., Перязев Н. А. Полиномиальные разложения булевых функций по образам неоднородных операторов // Кибернетика и системный анализ.- 2000, № 4.- С. 40−55.
  129. А.С., Винокуров С. Ф. Функция Шеннона для некоторых классов операторных полиномиальных форм //
  130. Оптимизация, управление, интеллект.- 2000.- Вып 5.- С. 167−180.
  131. Gaidukov A.I., Vinokurov S.F. Operator polynomial expansions of Boolean functions / / 4th International Workshop on Boolean Problems. Freiberg, Germany, 2000.- P.63−69.
  132. С.Ф. Смешанные операторы булевых функций и их свойства // Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 12.- Иркутск, 2000.36 с.
  133. С.Ф. Разложения булевых функций по собственным операторным образам и термам над бинарными функциями // Оптимизация, управление, интеллект.- 2000.- Вып 4.- С. 167−180.
  134. С.Ф. Разложения булевых функций по операторам сплетения // Международная конференция «Логика и приложения». Тезисы докл. Новосибирск, 2000.- С. 31−32.
  135. С.Ф. Операторные полиномиальные представления булевых функций // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем».- М.: Изд-во Центра прикладных исследований МГУ, 2001.- С. 41−46.
Заполнить форму текущей работой

Сессия? Спокойно!